酈元宏 王澤民

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

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

酈元宏 王澤民

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

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

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

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

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

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

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

1 LEACH協(xié)議分析

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

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

閾值Ti定義如下：

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

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

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

2 蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗和結(jié)果分析

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

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

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

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

5 結(jié)束語

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

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

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

[6]王林,潘軍.無線傳感器網(wǎng)絡(luò)中基于能量優(yōu)化的路由協(xié)議ANT-LEACH[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].計算機工程與應(yīng)用,2008,44(22):13-15.

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

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

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