浦倩云，吳錫生

（江南大學 物聯(lián)網工程學院，江蘇 無錫　214122）

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

浦倩云，吳錫生

（江南大學 物聯(lián)網工程學院，江蘇 無錫214122）

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

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

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

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

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

1　改進蝙蝠算法

1.1初始種群

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

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

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

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

1.2自適應變異控制概率

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

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

2　改進協(xié)議

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

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

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

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

其中，a，b是權重因子且a+b=1。Ecur表示當前傳感器節(jié)點中因數(shù)據(jù)融合和數(shù)據(jù)傳輸?shù)暮馁M而剩余的能量，E0表示初始狀態(tài)時傳感器節(jié)點所蘊含的能量，R0表示傳感器節(jié)點的通信半徑，d（n，BS）表示傳感器節(jié)點n到基站的距離。

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

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

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

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

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

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

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

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

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

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

2.2數(shù)據(jù)傳輸路由協(xié)議

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

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

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

3　仿真及結果分析

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

表1　實驗參數(shù)

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

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

圖1　傳感器節(jié)點初始分布圖

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

表2　傳感器節(jié)點死亡時間

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

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

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

4　結　論

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

［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］王濤春，秦小麟，劉亮，等.無線傳感器網絡中安全高效的空間數(shù)據(jù)聚集算法［J］.軟件學報，2014，25（8）：1671-1684.

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

［4］Kulkarni R V，F(xiàn)orster 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］.北京：電子工業(yè)出版社，2007.

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

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

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

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

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

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

［13］郭劍，孫力娟，王汝傳.基于最佳簇數(shù)的無線傳感器網絡粒子群分簇協(xié)議［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］王宏巖，李英順，王德彪，等.低能耗和低時延的無線傳感器網絡數(shù)據(jù)融合算法［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）；江蘇省產學研聯(lián)合創(chuàng)新資金項目（BY2013015-35）

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