基于改進(jìn)蝙蝠算法的無(wú)線(xiàn)分簇路由算法

浦倩云，吳錫生

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫　214122）

基于改進(jìn)蝙蝠算法的無(wú)線(xiàn)分簇路由算法

浦倩云，吳錫生

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫214122）

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

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

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

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

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

1　改進(jìn)蝙蝠算法

1.1初始種群

本文采用K-means聚類(lèi)算法對(duì)種群進(jìn)行初始化，多樣化種群，采用如下步驟：

1）產(chǎn)生N個(gè)隨機(jī)的蝙蝠個(gè)體作為網(wǎng)絡(luò)的初始聚類(lèi)中心。

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

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

1.2自適應(yīng)變異控制概率

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

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

2　改進(jìn)協(xié)議

2.1基于改進(jìn)蝙蝠算法的分簇

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

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

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

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

基于改進(jìn)蝙蝠算法的路由分簇步驟如下：

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

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

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

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

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

步驟6 產(chǎn)生一個(gè)隨機(jī)數(shù)rand，如果rand的值大于Ai且f（xi）＜f（x*），則移動(dòng)到新的位置。

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

步驟8根據(jù)公式（3）對(duì)經(jīng)過(guò)變異后的蝙蝠群體中蝙蝠個(gè)體的適應(yīng)度函數(shù)值進(jìn)行評(píng)價(jià)，并以此值來(lái)更新最優(yōu)解。

步驟9完成一次迭代，而后檢查是否滿(mǎn)足終止的要求，若滿(mǎn)足則終止迭代，同時(shí)輸出結(jié)果；否則轉(zhuǎn)步驟4。

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

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

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

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

3　仿真及結(jié)果分析

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

表1　實(shí)驗(yàn)參數(shù)

為了驗(yàn)證本文算法的有效性，對(duì)文獻(xiàn)［13］算法、本文算法進(jìn)行仿真。首先利用改進(jìn)的蝙蝠算法得到基于最佳簇?cái)?shù)Kopt的網(wǎng)絡(luò)的簇頭并對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇，然后通過(guò)多跳動(dòng)態(tài)路由算法建立簇頭節(jié)點(diǎn)到基站的路由。

實(shí)驗(yàn)中在指定監(jiān)測(cè)區(qū)域內(nèi)為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)隨機(jī)生成100個(gè)傳感器節(jié)點(diǎn)，其分布如圖1所示。

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

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

表2　傳感器節(jié)點(diǎn)死亡時(shí)間

仿真得到的整個(gè)網(wǎng)絡(luò)存活節(jié)點(diǎn)隨仿真時(shí)間變化曲線(xiàn)如圖2所示。

圖2為文獻(xiàn)［13］算法和本文算法的比較，通過(guò)仿真實(shí)驗(yàn)可以看出，本文采用的改進(jìn)蝙蝠算法第一個(gè)死亡節(jié)點(diǎn)時(shí)間相對(duì)文獻(xiàn)［13］推遲60 s；第40個(gè)節(jié)點(diǎn)相對(duì)文獻(xiàn)［13］推遲74 s；監(jiān)測(cè)區(qū)域中所有節(jié)點(diǎn)的死亡時(shí)間相對(duì)文獻(xiàn)［13］推遲91 s。這是因?yàn)楸疚牟捎玫乃惴ㄔ诜执貢r(shí)充分考慮了網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)自身的剩余能量和簇頭節(jié)點(diǎn)之間的數(shù)據(jù)通信這兩個(gè)因素。這也使得本文采用的改進(jìn)蝙蝠算法可以有效提高網(wǎng)絡(luò)中節(jié)點(diǎn)能量的利用率，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存周期。

圖2　傳感器存活節(jié)點(diǎn)隨時(shí)間變化曲線(xiàn)

4　結(jié)　論

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

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

［3］劉健苗，許新忠，黃書(shū)廣，等.改進(jìn)的分布式無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法［J］.傳感技術(shù)學(xué)報(bào)，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］宋文.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京：電子工業(yè)出版社，2007.

［7］孫利民，李建中，陳渝.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005.

［8］任豐原，黃海寧，林闖.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2003，14（7）：1282-1291.

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

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

［11］劉園莉，李臘元，盧迪.節(jié)能的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23（12）：1792-1797.

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

［13］郭劍，孫力娟，王汝傳.基于最佳簇?cái)?shù)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)粒子群分簇協(xié)議［J］.南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，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í)延的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法［J］.電子設(shè)計(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稿件編號(hào)：201602033

國(guó)家自然科學(xué)基金（61103223）；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金項(xiàng)目（BY2013015-35）

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