酈元宏 王澤民

（瑞利科技有限公司 新能源事業(yè)部，杭州，310023）

基于蟻群算法的LEACH協(xié)議在WSN中的研究

酈元宏 王澤民

（瑞利科技有限公司 新能源事業(yè)部，杭州，310023）

針對(duì)WSN中LEACH協(xié)議的簇頭選舉過程未考慮節(jié)點(diǎn)剩余能量，以及簇頭與Sink節(jié)點(diǎn)之間采用單跳通信造成某些節(jié)點(diǎn)因能量損耗過快從而造成網(wǎng)絡(luò)分割的問題，提出一種基于蟻群算法的 LEACH協(xié)議。該協(xié)議通過引入節(jié)點(diǎn)剩余能量的方法，降低了低能量節(jié)點(diǎn)當(dāng)選簇頭的概率，并實(shí)現(xiàn)了能量均衡的多跳路由。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)LEACH協(xié)議相比，新協(xié)議降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；LEACH協(xié)議；蟻群算法

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是一種自組織測(cè)控網(wǎng)絡(luò)系統(tǒng)，由大量隨機(jī)分布的具有特定功能的傳感器節(jié)點(diǎn)構(gòu)成，具有數(shù)據(jù)采集、感知、控制等多種功能，可廣泛用于軍事、工業(yè)和農(nóng)業(yè)等眾多領(lǐng)域[1]。網(wǎng)絡(luò)中的節(jié)點(diǎn)一般由電池提供能量，也可以由太陽能、風(fēng)能等新能源提供。由于節(jié)點(diǎn)能量的有限性，降低節(jié)點(diǎn)的能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期，成為無線傳感器網(wǎng)絡(luò)研究中的一個(gè)熱點(diǎn)[2]。

WSN中，LEACH（Low Energy Adaptive Clustering Hierarchy， LEACH）協(xié)議是一種典型的分層協(xié)議[3]，目前使用較為成熟廣泛。該協(xié)議通過分簇把網(wǎng)絡(luò)自組織起來。簇首負(fù)責(zé)把簇成員的信息收集起來，并將其發(fā)給Sink節(jié)點(diǎn)，這可以有效的減少簇成員的能量消耗。但是LEACH協(xié)議的多跳路由功能比較弱，在網(wǎng)絡(luò)的規(guī)模比較大時(shí)，沒有對(duì)多條路由進(jìn)行合理的優(yōu)化，在路由過程中造成了大量的能量浪費(fèi)，進(jìn)而縮短了網(wǎng)絡(luò)的生命周期。

文獻(xiàn)[4-6]對(duì)傳統(tǒng)的LEACH進(jìn)行了改進(jìn)，其中文獻(xiàn)[4]將 LEACH 協(xié)議和蟻群算法進(jìn)行了簡(jiǎn)單的組合，簇頭節(jié)點(diǎn)的選取規(guī)則未有更改，對(duì)簇頭之間的路由計(jì)算也只是簡(jiǎn)單套用蟻群算法。文獻(xiàn)[5]主要針對(duì) LEACH 協(xié)議中簇頭節(jié)點(diǎn)的選取規(guī)則進(jìn)行重新設(shè)計(jì)，在簇結(jié)構(gòu)形成階段選取簇頭時(shí)考慮各個(gè)傳感器節(jié)點(diǎn)的剩余能量、但是未對(duì)簇頭路由算法進(jìn)行優(yōu)化，導(dǎo)致路由過程整體能耗過高。文獻(xiàn)[6]對(duì)簇頭選取進(jìn)行了比較合理的規(guī)劃，充分考慮了節(jié)點(diǎn)剩余能力、平均能量等因素對(duì)簇頭選擇的影響，但是沒有將能量因子融入到簇頭路由選擇中，導(dǎo)致某些關(guān)鍵路由節(jié)點(diǎn)的能量消耗過快。

本文提出了一種改進(jìn)的LEACH協(xié)議，新協(xié)議在多跳路由選擇上采用了改進(jìn)的蟻群算法尋找最優(yōu)解，同時(shí)在簇首選舉中加入了節(jié)點(diǎn)剩余能量和局部網(wǎng)絡(luò)平均能量的影響因子。

1 LEACH協(xié)議分析

LEACH是第一種應(yīng)用于無線傳感器網(wǎng)絡(luò)的分層路由協(xié)議，很多后續(xù)的分層路由協(xié)議都是基于它改進(jìn)而來。LEACH協(xié)議的執(zhí)行過程是周期性的，每個(gè)周期成為一輪，每一輪分為兩個(gè)階段，分別為簇的建立和數(shù)據(jù)傳輸。

在簇的建立階段，每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)（0～1）之間的隨機(jī)數(shù)，當(dāng)這個(gè)隨機(jī)數(shù)小于預(yù)先設(shè)定的閾值Ti時(shí)，該節(jié)點(diǎn)當(dāng)選簇首。隨后，當(dāng)選為簇首的節(jié)點(diǎn)向四周廣播其當(dāng)選為簇首的消息，其它節(jié)點(diǎn)收到消息后，將根據(jù)一定的規(guī)則（比如根據(jù)無線電信號(hào)的強(qiáng)度），決定應(yīng)當(dāng)加入哪個(gè)簇，并回復(fù)消息以告知該簇首[7]。

閾值Ti定義如下：

式中，p為簇首節(jié)點(diǎn)數(shù)占節(jié)點(diǎn)總數(shù)的比例，r為當(dāng)前進(jìn)行的輪數(shù)，G為前rmod(1/p)輪中尚且沒有當(dāng)選簇首節(jié)點(diǎn)的集合。

在數(shù)據(jù)的傳輸階段，簇內(nèi)成員使用 TDMA（Time Division Multiple Access）機(jī)制，向簇首節(jié)點(diǎn)傳輸數(shù)據(jù)，簇首節(jié)點(diǎn)將收集到的各節(jié)點(diǎn)數(shù)據(jù)進(jìn)行數(shù)據(jù)融合，最后發(fā)送給Sink節(jié)點(diǎn)。穩(wěn)定傳輸一定流量的數(shù)據(jù)后，LEACH協(xié)議將重新進(jìn)行簇首選舉，開始下一個(gè)周期。

由于LEACH協(xié)議在簇首選舉的過程中只是簡(jiǎn)單采用了隨機(jī)的算法試圖均衡整個(gè)網(wǎng)絡(luò)的能量消耗，沒有考慮節(jié)點(diǎn)的剩余能量的情況，易使某些關(guān)鍵節(jié)點(diǎn)過多的當(dāng)選為簇首，并導(dǎo)致其能量耗盡而過早死亡。因此必須要引入一種充分考慮節(jié)點(diǎn)剩余能量的機(jī)制，避免能量低節(jié)點(diǎn)過多擔(dān)任簇首。

2 蟻群算法

蟻群算法(Ant colony algorithm)是一種擁有廣闊應(yīng)用前景的仿生算法，具有良好的分布式計(jì)算機(jī)制和較強(qiáng)的魯棒性，最初用來解決復(fù)雜的 TSP（Travelling Salesman Problem）最優(yōu)路徑問題[8-9]。蟻群算法的誕生，正是受自然界中蟻群的覓食行為的啟發(fā)。蟻群在覓食的過程中，會(huì)在經(jīng)過的路線上留下一些特殊的化學(xué)物質(zhì)，我們稱之為信息素(pheromone)。蟻群中的每個(gè)螞蟻都能感知到自己所處位置附近信息素的存在的多寡，會(huì)傾向于往信息素濃度高的方向移動(dòng)，并使該方向的信息素進(jìn)一步加強(qiáng)，如此大量積累，便可以找到最優(yōu)的路徑。

在蟻群算法中，第k只螞蟻，從i節(jié)點(diǎn)選擇到j(luò)節(jié)點(diǎn)路徑的概率為

第t輪結(jié)束，開始第t+1輪，其信息素更新

其中ρ表示信息素的揮發(fā)系數(shù)，取值區(qū)間為(0，1)，allowedk為螞蟻k下一步可以選擇的節(jié)點(diǎn)集合，表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的信息素濃度，表示i到j(luò)的能見度，一般取i至j的距離的倒數(shù)，α為信息啟發(fā)式因子，代表信息素的重要性，β為期望啟發(fā)式因子，代表距離的重要性。

顯然，蟻群算法對(duì)尋找最優(yōu)路徑（一般為最短路徑）非常有效，如果將其應(yīng)用到WSN中尋找最短路由也是很合適的。但該算法僅僅找到了最短的路由，沒有考慮節(jié)點(diǎn)剩余能量的情況。

3 基于蟻群算法的改進(jìn)LEACH協(xié)議

3.1 新協(xié)議的算法原理

基于以上對(duì)蟻群算法和LEACH協(xié)議在無線傳感器網(wǎng)絡(luò)應(yīng)用中存在的問題，本文提出了一種新的協(xié)議，名為ANT-LEACH協(xié)議。新協(xié)議從以下兩個(gè)方面對(duì)LEACH協(xié)議進(jìn)行了改進(jìn)。首先改進(jìn)LEACH協(xié)議的簇首選舉規(guī)則。修改閾值Ti的生成公式：

在簇首選舉公式中，通過引入能量因子，可降低低能量節(jié)點(diǎn)當(dāng)選簇首的概率，均衡整個(gè)網(wǎng)絡(luò)的能量；其次，將蟻群算法中的能見度系數(shù)更改為由距離和節(jié)點(diǎn)剩余能量共同決定；加入系數(shù) ，主要是由于無線電傳輸模型中信號(hào)的衰減反比于距離的三次方，這里系數(shù)可以在3～4間取值[10]。為矯正系數(shù)，表示無線電信號(hào)在信道中的傳播質(zhì)量，一般μ≤1。新的能見度系數(shù)

3.2 ANT-LEACH 協(xié)議實(shí)現(xiàn)

ANT-LEACH協(xié)議延續(xù)了傳統(tǒng)LEACH協(xié)議的流程，但改進(jìn)了簇首節(jié)點(diǎn)選舉算法和路由算法，具體流程如圖1所示。

圖1 ANT-LEACH協(xié)議的流程圖

4 仿真實(shí)驗(yàn)和結(jié)果分析

為了驗(yàn)證 ANT-LEACH協(xié)議的性能，使用OPNET網(wǎng)絡(luò)仿真工具對(duì)新協(xié)議進(jìn)行建模和仿真[11]。在200 m×200 m范圍內(nèi)，隨機(jī)布置50個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的初始能量為0.5 J，控制包/廣播包的長(zhǎng)度為64 bit，數(shù)據(jù)包的長(zhǎng)度為1024 bit，自由空間的信號(hào)放大器放大倍數(shù)En=1.0×10?11J/bit·m?2，多徑衰減模型中放大器的放大倍數(shù)Ef=1.0×10?15J/bit·m?4，收發(fā)器耗能 6.0×10?8J/bit，基站坐標(biāo)（48,180），α=1，β=1.8，γ=3，μ=0.9，ρ=0.2。設(shè)定仿真探頭為：節(jié)點(diǎn)存活個(gè)數(shù)、存活節(jié)點(diǎn)的平均能量。仿真結(jié)果如圖2和3所示。

圖2 點(diǎn)存活個(gè)數(shù)和時(shí)間的關(guān)系

圖3 存活節(jié)點(diǎn)的平均能量和時(shí)間的關(guān)系

從圖2可以看出，ANT-LEACH協(xié)議出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡的時(shí)間相比LEACH協(xié)議第一個(gè)節(jié)點(diǎn)死亡的時(shí)間推遲了至少10 min，即使用ANT-LEACH協(xié)議的網(wǎng)絡(luò)的穩(wěn)定期比LEACH協(xié)議提高35%左右。這主要是由于ANT-LEACH協(xié)議使得低能量節(jié)點(diǎn)當(dāng)選簇首的概率大為降低，從而避免了其過早死亡。由于新協(xié)議在簇頭和基站之間的數(shù)據(jù)通信采用了基于能量因子的改進(jìn)的蟻群算法的進(jìn)行多跳優(yōu)化策略，從而在獲得近似最短路由的前提下，避免了某些能量低節(jié)點(diǎn)過多地承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，從而進(jìn)一步延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存時(shí)間。從圖3 可以看出，ANT-LEACH協(xié)議對(duì)降低網(wǎng)絡(luò)平均能耗是有效的，相比LEACH協(xié)議，新協(xié)議的平均能耗曲線更為平滑，平均剩余能量提高明顯。

5 結(jié)束語

本文將具有良好魯棒性的蟻群算法應(yīng)用于LEACH協(xié)議，并且對(duì)兩種算法進(jìn)了針對(duì)性的改進(jìn)，最終使改進(jìn)后的蟻群算法在兼顧能量均衡的前提下，獲得近似最優(yōu)解。工程實(shí)踐也表明，該協(xié)議可以用于特別強(qiáng)調(diào)節(jié)能的傳感器自組網(wǎng)，對(duì)延長(zhǎng)網(wǎng)絡(luò)壽命有重要意義。但目前該研究只針對(duì)小規(guī)模的無線網(wǎng)絡(luò)，而且仿真中隨機(jī)布置的 30個(gè)節(jié)點(diǎn)也是以基站為中心隨機(jī)分布，因此下一步可以更大規(guī)模網(wǎng)絡(luò)和非基站為中心網(wǎng)絡(luò)進(jìn)行研究，并定量分析該協(xié)議的性能。

[1]PRAVEENA A,DEVASENA S.Achieving energy efficient and secure communication in wireless sensor networks[J].IEEE,2006,11(5):341-356．

[2]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[3]沈波,張世永,鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),2006,17(7):1587-1600.

[4]胡彧,王靜. 基于蟻群算法的LEACH協(xié)議研究[J].傳感技術(shù)學(xué)報(bào),2011,26(6):851-856.

[5]李虎雄,張克旺.基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由優(yōu)化算法[J]. 西北工業(yè)大學(xué)學(xué)報(bào),2012,19(1):34-36.

[6]王林,潘軍.無線傳感器網(wǎng)絡(luò)中基于能量?jī)?yōu)化的路由協(xié)議ANT-LEACH[J].計(jì)算機(jī)應(yīng)用, 2011,25(3):715-717

[7]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd HawaiiInternational Conference on System Sciences,2000.

[8]楊靖,林溢,熊偉麗,等.蟻群算法在無線傳感器網(wǎng)絡(luò)路由中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(22):13-15.

[9]王青正,閔林,郭拯危,等.基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)能耗均衡路由算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(12):4716-4718.

[10]張毅,梁艷春.蟻群算法中求解參數(shù)最優(yōu)選擇分析[J].計(jì)算機(jī)應(yīng)用研究,2007,24(8):70-71．

[11]王磊,施榮華.無線傳感器網(wǎng)絡(luò)路由算法的仿真研究[J].計(jì)算機(jī)仿真,2010,28(3):170-174.