基于改進蝙蝠算法的無線分簇路由算法

浦倩云，吳錫生

（江南大學 物聯網工程學院，江蘇 無錫　214122）

基于改進蝙蝠算法的無線分簇路由算法

浦倩云，吳錫生

（江南大學 物聯網工程學院，江蘇 無錫214122）

針對無線傳感器網絡節點能量有限的問題，給出了一種基于改進蝙蝠算法的分簇路由算法。利用K-means聚類算法通過迭代過程初始化蝙蝠種群，使種群更均勻地分布在監測區域中；為了使蝙蝠個體跳出局部最優解，避免早熟收斂，采用控制概率判斷算法進行高斯變異。該算法結合傳感器節點本身剩余能量和到基站距離建立適應度函數，通過改進蝙蝠算法實現適應度函數的最優求解，從而獲得合適的分簇，簇頭節點間采用多跳動態路由。仿真結果表明，使用本文提出的無線分簇路由算法使得所有節點死亡時間明顯推遲，能有效提高傳感器節點能量的利用率，降低網絡能耗，延長整個網絡的生存周期。

生存周期；蝙蝠算法；分簇路由算法；高斯變異；適應度函數；能耗

無線傳感器網絡（wireless sensor networks，WSN）［1-3］是由散布在不同區域的眾多傳感器節點構成的一個多跳網絡，其中運用到了傳感器技術、分布式處理方法、和無線通信技術等被廣泛應用于工農業、國防、醫藥等行業領域范疇。由于無線傳感器網絡中節點本身攜帶的電池能量是有限的且節點布置后因工作環境等客觀因素不易更換電池，所以減少均衡網絡中節點能量的消耗，延長網絡的生存周期是目前無線傳感器網絡研究的主要方向［4］。

經典的分簇路由協議有：EECS、PEGASIS和LEACHE［5-11］，LEACH協議將整個網絡劃分成兩層：簇頭節點和簇內節點，網絡含有多個簇，每個簇包含一個簇頭節點和其余普通節點，網絡運行的過程中周期性的輪換簇頭節點避免其能量消耗過多過早死亡。但由于簇頭產生的隨機性，此協議在選舉簇頭時并未將網絡中節點的剩余能量考慮在內，可能會導致最后分簇的不合理，造成部分節點的能量被過早的消耗，節點過早死亡，降低網絡的生存周期，且簇頭直接與基站通訊，若兩者之間的距離過大，網絡的整體能量消耗將因為距離的增大和快速增大［12］。文獻［13］按照一定的原則來計算網絡中最佳簇的數目，并采用粒子群優化算法，取得較好結果。文獻［14］文獻［15］中采用不同的競爭半徑進行非均勻分簇，文獻［16］中將網絡劃分成大小不等的若干層，文獻［17］根據節點的傳輸范圍，將每個簇中的節點均勻分布，但文獻［14-17］中均沒有討論非均勻分簇的最優化問題。

為了提高無線傳感器網絡中節點能量的利用率，使得網絡的能量均衡消耗，整個網絡的生存周期得以延長，本文提出了一種基于改進蝙蝠算法的無線分簇路由算法。該算法能克服蝙蝠算法易早熟收斂且依賴初始種群等缺陷；算法能根據控制概率進行高斯變異使蝙蝠個體能自適應克服局部最優解的限制。該算法通過改進的蝙蝠算法來實現網絡節點的適應度函數的最優求解，獲得網絡中各簇的相應簇頭，能有效延長整個網絡的生存周期。

1　改進蝙蝠算法

1.1初始種群

本文采用K-means聚類算法對種群進行初始化，多樣化種群，采用如下步驟：

1）產生N個隨機的蝙蝠個體作為網絡的初始聚類中心。

2）產生P個隨機的蝙蝠個體，并以其到初始聚類中心的距離為判斷依據將其歸類到最近的聚類中心。

3）重新計算N個聚類簇的中心點，以這N個中心點作為新的中心點。反復執行步驟2）、3），直到兩次計算得到的聚類簇中心點的變化范圍低于所要求的精度閾值。

1.2自適應變異控制概率

為防止蝙蝠算法［18］陷入早熟收斂，本文引入變異機制使得蝙蝠算法在跳出局部最優解方面的概率變大。根據迭代次數自適應控制變異概率的控制概率P如下：

式中，t是種群當前迭代次數，gen是種群最大迭代次數。由式（1）可以看出隨著種群迭代次數的增加，P的值越來越趨近于1，以更大的概率進行高斯變異，從而可以使算法跳出局部最優解。

2　改進協議

2.1基于改進蝙蝠算法的分簇

LEACH設定簇頭數目為網絡中節點總數的1/20。但是，實際的網絡分簇情況下，若此值太小，會導致簇內節點到簇頭節點的距離過大，造成能量的過度損耗，導致數據在傳輸過程中節點能量耗盡；反之，如果簇頭數目過多，則無法達到層簇式網絡結構的預期效果。故本文采用文獻［13］的最優簇頭數計算方法：

式中，εfs為自由空間傳播模型下功率放大所需要的耗能系數，εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數。根據1.1節所述，本文先利用K-means聚類方法對散布在網絡中的傳感器節點進行初步的聚類，先輸入N個傳感器節點，并隨機產生Kopt個初始聚類節點，根據1.1節中的步驟1至步驟3將網絡中的節點進行聚類劃分得到其分布圖。

在無線傳感器網絡中，節點所含的剩余能量、節點之間的距離都是影響分簇的重要因素，因此本文將節點的適應度函數設置為：

其中，a，b是權重因子且a+b=1。Ecur表示當前傳感器節點中因數據融合和數據傳輸的耗費而剩余的能量，E0表示初始狀態時傳感器節點所蘊含的能量，R0表示傳感器節點的通信半徑，d（n，BS）表示傳感器節點n到基站的距離。

基于改進蝙蝠算法的路由分簇步驟如下：

步驟1初始化分簇路由算法的基本參數。

步驟2根據公（2）計算得到的最優簇頭數和K-means聚類算法對蝙蝠種群進行初始化。

步驟3根據公式（3）計算得到每個蝙蝠的適應度函數值，并以此為依據找到最優蝙蝠的位置。

步驟4根據公式（4）、（5）和（6）更新網絡中各蝙蝠個體的速度跟位置。

步驟5產生一個隨機數rand，如果rand的值大于ri，為獲得新的位置算法要對當前種群中最佳蝙蝠的位置進行隨機的擾動并用擾動后獲得的新的位置取代當前最佳蝙蝠的位置。

步驟6 產生一個隨機數rand，如果rand的值大于Ai且f（xi）＜f（x*），則移動到新的位置。

步驟7產生一個隨機數rand，根據公式（1）計算控制概率P，如果P大于rand，則進行高斯變異。

步驟8根據公式（3）對經過變異后的蝙蝠群體中蝙蝠個體的適應度函數值進行評價，并以此值來更新最優解。

步驟9完成一次迭代，而后檢查是否滿足終止的要求，若滿足則終止迭代，同時輸出結果；否則轉步驟4。

2.2數據傳輸路由協議

層簇式網絡的數據傳輸主要分為簇內和簇間數據傳輸這兩個階段。其中簇內節點數據傳輸時，各個節點采用TDMA方式，在各自時隙內將本節點內的數據傳輸給本節點所屬的簇頭節點，簇頭節點接收到本簇內個節點發送的數據后將多個數據進行融合處理，壓縮成一個數據包后再進行簇間數據的傳輸，簇頭之間的數據傳輸采用多跳動態路由的方式。具體方式如下：

1）成為簇頭的節點si以相同的概率廣播其狀態信息，若其到基站的距離di_bs小于閾值TD_MIN，則將其與基站之間通訊設為直接通訊，否則轉至2）。

2）簇頭節點si向整個網絡廣播其狀態信息，廣播半徑從TD_MIN開始依次增加，若在此范圍內有其他簇頭節點sj回應廣播簇頭si且dj_bs小于，則將簇頭節點sj加入到此si的鄰居簇頭表中，并終止廣播。否則增大廣播的半徑，直到有簇頭回應，從而獲得這個簇頭的鄰居簇頭表。若各個簇頭的鄰居簇頭表非空，則將數據直接發送給表中的路由簇頭；反之，則將數據發送給鄰居簇頭，并循環路由。

3　仿真及結果分析

文中采用matlab對文中改進蝙蝠算法的無線路由協議進行仿真和評價。監測區域中無線傳感器網絡的參數設置，如表1所示。

表1　實驗參數

為了驗證本文算法的有效性，對文獻［13］算法、本文算法進行仿真。首先利用改進的蝙蝠算法得到基于最佳簇數Kopt的網絡的簇頭并對網絡中的節點進行分簇，然后通過多跳動態路由算法建立簇頭節點到基站的路由。

實驗中在指定監測區域內為無線傳感器網絡隨機生成100個傳感器節點，其分布如圖1所示。

圖1　傳感器節點初始分布圖

在不同的工作次數下，文獻［13］與本文的算法相比，其網絡中第1個節點死亡、第40個死亡以及所有節點死亡的時間，如表2所示。

表2　傳感器節點死亡時間

仿真得到的整個網絡存活節點隨仿真時間變化曲線如圖2所示。

圖2為文獻［13］算法和本文算法的比較，通過仿真實驗可以看出，本文采用的改進蝙蝠算法第一個死亡節點時間相對文獻［13］推遲60 s；第40個節點相對文獻［13］推遲74 s；監測區域中所有節點的死亡時間相對文獻［13］推遲91 s。這是因為本文采用的算法在分簇時充分考慮了網絡中傳感器節點自身的剩余能量和簇頭節點之間的數據通信這兩個因素。這也使得本文采用的改進蝙蝠算法可以有效提高網絡中節點能量的利用率，延長整個網絡的生存周期。

圖2　傳感器存活節點隨時間變化曲線

4　結　論

文中采用改進的蝙蝠算法，通過K-means聚類算法經多次迭代找到最優解并將網絡中的節點進行分簇，由于蝙蝠算法在迭代過程中可能會過早陷入局部最優解，導致算法找到的最優解其實是不準確的，故本文在子群局部搜索的過程中引入控制概率判斷算法進行高斯變異，是算法能自適應克服局部最優解的限制，防止算法過早收斂陷入局部最優。結合傳感器節點本身剩余能量和到基站距離建立適應度函數，通過改進的蝙蝠算法實現適應度函數的最優求解，從而獲得合適簇頭并進行分簇。仿真結果表明，本文提出的算法可以有效降低網絡能耗，延長整個網絡的生存周期。

［1］Kail A，Kanatas A G，Efthymoglou G P.A cooperative beam forming solution for eliminating multi-hop communications in wireless sensor［J］.IEEE Journal on Selected Areas in Communications，2010，28（7）：1055-1062.

［2］王濤春，秦小麟，劉亮，等.無線傳感器網絡中安全高效的空間數據聚集算法［J］.軟件學報，2014，25（8）：1671-1684.

［3］劉健苗，許新忠，黃書廣，等.改進的分布式無線傳感器網絡多維標度定位算法［J］.傳感技術學報，2014，27（5）：692-697.

［4］Kulkarni R V，Forster A，Venayagamoorthy G K.Computational intelligence in wireless sensor network：A survey［J］. Communications Surveys&Tutorials，IEEE，2011，13（1）：68-96.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［6］宋文.無線傳感器網絡技術與應用［M］.北京：電子工業出版社，2007.

［7］孫利民，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［8］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14（7）：1282-1291.

［9］陳志軍，李明.基于免疫退火的WSN簇首節點選擇方法研究［J］.重慶師范大學學報（自然科學版），2014，02（31）：72-76.

［10］何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協議的設計［J］.傳感技術學報，2009，22（10）：1510-1514.

［11］劉園莉，李臘元，盧迪.節能的無線傳感器網絡分簇路由協議的研究［J］.傳感技術學報，2010，23（12）：1792-1797.

［12］韓萬強，劉云.WSN中基于分簇的改進路由協議［J］.計算機工程，2012，38（5）：105-107.

［13］郭劍，孫力娟，王汝傳.基于最佳簇數的無線傳感器網絡粒子群分簇協議［J］.南京郵電大學學報：自然科學版，2010，30（2）：36-40.

［14］Ye Mao，Li Chengfa，Chen Guihai，et al.EECS：an energy efficient clustering scheme in wireless sensor networks［J］. Journal of Frontiers of Computer Science&Technology，2007，3（2-3）：535-540

［15］Li Chengfa，Ye Mao，Chen Guihai，et al.An energy-efficient unequal clustering mechanism for wireless sensor networks：MASS 2005，2005［C］.Washington：IEEE Press，2005.

［16］Tashtarian F，HaghighatAT，Honary M T，et al.A new energy-efficient clustering algorithm for wireles sensor networks：SoftCOM 2007，2007［C］.Split：IEEE Press，2007.

［17］王宏巖，李英順，王德彪，等.低能耗和低時延的無線傳感器網絡數據融合算法［J］.電子設計工程，2013，21（7）：47-50.

［18］Yang X S，Gandomi A H.Bat algorithm：a novel approach for global engineering optimization［J］.Neural Computing& Applications，2013，22（6）：1239-1225.

Wireless clustering routing algorithm based on improved bat algorithm

PU Qian-yun，WU Xi-sheng
（College of IoT Engineering，Jiangnan University，Wuxi 214122，China）

In accordance with the problem that the wireless sensor network node's energy is limited.A clustering routing algorithm based on improved bat algorithm is presented.K-means clustering algorithm was put forward to use the iterative procedure to initialize the bat population to make the population distribution more homogeneous in the monitor space and the control probability judgment algorithm was used to make gauss variation to make individual bat out of local optima and avoid premature convergence.A fitness function was set up combined the residual energy of the sensor nodes and the distance between the sensor nodes and the base station.The optimal solution of the fitness function was realized by the improved bat algorithm and the suitable clustering was gained.The multi hop dynamic routing was used among the cluster nodes.The simulation result shows that the wireless clustering routing algorithm put forward in this paper make the death time of all nodes obviously delayed，effectively improve the energy utilization of sensor nodes，reduce the network energy consumption and prolong the network life cycle.

life cycle；BA；clustering routing algorithm；gauss variation；fitness function；energy consumption

TP391

A

1674－6236（2016）09-0126-03

2016-02-14稿件編號：201602033

國家自然科學基金（61103223）；江蘇省產學研聯合創新資金項目（BY2013015-35）

浦倩云（1991—），女，江蘇無錫人，碩士研究生。研究方向：傳感器網絡和控制系統。