嚴(yán)斌亨，劉 軍，劉廣斌，何楊炯

(武警工程大學(xué) 信息工程系，西安 710086)

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

嚴(yán)斌亨，劉 軍，劉廣斌，何楊炯

(武警工程大學(xué) 信息工程系，西安 710086)

針對(duì)LEACH協(xié)議在數(shù)據(jù)傳輸階段，簇首與匯聚節(jié)點(diǎn)之間采用單跳模式傳輸數(shù)據(jù)使得能量消耗快并且不均衡的問題，提出一種基于改進(jìn)蟻群算法的新型路由協(xié)議；該協(xié)議利用了能耗因子對(duì)蟻群轉(zhuǎn)移概率以及信息素更新進(jìn)行改進(jìn)，充分考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間距離，通過信息素的建立和更新，尋找簇首節(jié)點(diǎn)和基站之間的最優(yōu)傳輸路徑，進(jìn)行多跳傳輸模式，從而均衡簇首節(jié)點(diǎn)能量消耗；仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的ACO-BEC協(xié)議較之于LEACH協(xié)議，能夠有效降低了整個(gè)網(wǎng)絡(luò)能量消耗，延長了網(wǎng)絡(luò)壽命。

無線傳感器網(wǎng)絡(luò)；LEACH協(xié)議；蟻群算法；信息素；能量均衡

0 引言

20世紀(jì)五六十年代以來，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、無線通信技術(shù)、傳感器技術(shù)和分布式處理技術(shù)等高新技術(shù)的成熟發(fā)展，無線傳感器網(wǎng)絡(luò)[1](WSNs，Wireless Sensor Networks)逐步形成。WSNs是由大量體積小、成本低、電池供電的傳感器節(jié)點(diǎn)密集分布在一定范圍內(nèi)的自適應(yīng)系統(tǒng)[2]，這些傳感器節(jié)點(diǎn)在部署范圍內(nèi)協(xié)同進(jìn)行數(shù)據(jù)的采集、存儲(chǔ)、處理和傳輸，完成對(duì)整個(gè)區(qū)域的監(jiān)控。目前廣泛應(yīng)用于軍事、工業(yè)、農(nóng)業(yè)、醫(yī)學(xué)和搶險(xiǎn)救災(zāi)等領(lǐng)域[3-4]。

LEACH[5-10]是最早被提出來的經(jīng)典分簇路由協(xié)議，該協(xié)議通過隨機(jī)等概率的方式選舉簇首，以此達(dá)到均衡網(wǎng)絡(luò)能量，提高網(wǎng)絡(luò)壽命的目的，但LEACH協(xié)議隨機(jī)簇首選舉方式以及數(shù)據(jù)的單跳傳輸模式，使得能量消耗不均，加速個(gè)別節(jié)點(diǎn)死亡，影響整體網(wǎng)絡(luò)壽命[6]。因此，針對(duì)LEACH協(xié)議的缺陷，越來越多的改進(jìn)協(xié)議被提出來，文獻(xiàn)[7]考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)稀疏程度等因素來保證最優(yōu)簇頭，同時(shí)將優(yōu)化過的蟻群算法用于選擇最優(yōu)能量路徑完成簇頭間信息傳輸；文獻(xiàn)[8]提出的DSCT算法在以改進(jìn)的LEACH協(xié)議對(duì)WSN進(jìn)行分簇的基礎(chǔ)上，利用蟻群算法尋找出連接所有簇首的最優(yōu)路徑，使移動(dòng)sink沿著此路徑移動(dòng)并進(jìn)行數(shù)據(jù)收集；文獻(xiàn)[9]提出的基于最小生成樹的非均勻算法UCRAMST算法利用節(jié)點(diǎn)的剩余能量選舉簇首，通過建立最優(yōu)傳輸路徑減少能量消耗。但是以上一些改進(jìn)方法或在計(jì)算轉(zhuǎn)移概率以及更新信息素只考慮能量并未考慮節(jié)點(diǎn)及鏈路的其它狀況，或是過于復(fù)雜，這將不利于網(wǎng)絡(luò)節(jié)點(diǎn)能量的均衡和節(jié)省。因此，本文在LEACH協(xié)議的基礎(chǔ)上，提出一種基于蟻群算法的改進(jìn)協(xié)議ACO-BEC (balanced energy consumption based on ACO for LEACH)，該協(xié)議在數(shù)據(jù)傳輸時(shí)利用優(yōu)化后的蟻群算法尋找最優(yōu)路徑，采用多跳模式，在搜尋下一跳時(shí)考慮節(jié)點(diǎn)的剩余能量，避免節(jié)點(diǎn)過早死亡，從而延長網(wǎng)絡(luò)壽命。

1 LEACH協(xié)議分析

經(jīng)典LEACH協(xié)議采用分簇拓?fù)淇刂频墓芾頇C(jī)制，一組節(jié)點(diǎn)形成一個(gè)簇，簇成員與簇首通信，簇首匯聚并融合采集的數(shù)據(jù)并轉(zhuǎn)發(fā)至匯聚節(jié)點(diǎn)，協(xié)議引入了‘輪’的概念，每一輪包括兩個(gè)階段：簇的建立階段及數(shù)據(jù)穩(wěn)定傳輸階段[10]。

簇的建立階段可細(xì)分為兩步：第一步是各節(jié)點(diǎn)隨機(jī)等概率競(jìng)選簇首；第二步是簇首節(jié)點(diǎn)廣播消息，非簇首節(jié)點(diǎn)選擇加入相應(yīng)的簇。在簇首選舉時(shí)，各個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)介于0到1間的隨機(jī)數(shù)，并與確定的閾值T(n)相比較，判定是否擔(dān)任簇首。閾值T(n)計(jì)算公式見式(1)：

(1)

式中,p是節(jié)點(diǎn)中簇首的百分?jǐn)?shù)，r是當(dāng)前選舉的輪數(shù)，G是之前輪中未當(dāng)選過簇首的節(jié)點(diǎn)集合，rmod(1/p)是該輪循環(huán)中已當(dāng)選過簇頭的節(jié)點(diǎn)數(shù)量。

選舉完成后，簇首節(jié)點(diǎn)主動(dòng)廣播身份消息，非簇節(jié)點(diǎn)根據(jù)接收到的廣播信號(hào)的強(qiáng)度來選擇要加入的簇，并向簇首反饋加入信息，各簇內(nèi)節(jié)點(diǎn)采用TDMA方式與簇首通信；簇建立完成后，各成員節(jié)點(diǎn)若有數(shù)據(jù)要發(fā)送，就利用各自分配的時(shí)間片將數(shù)據(jù)發(fā)送到簇首，當(dāng)簇首節(jié)點(diǎn)接收到所有的數(shù)據(jù)后，對(duì)數(shù)據(jù)進(jìn)行融合處理，將有用的數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)；持續(xù)一段時(shí)間之后，整個(gè)網(wǎng)絡(luò)進(jìn)入下一輪重新進(jìn)行簇首選舉[11]。

研究表明，LEACH協(xié)議有效延長了網(wǎng)絡(luò)的整體壽命，較之前的平面多跳路由協(xié)議和靜態(tài)分簇協(xié)議可以將網(wǎng)絡(luò)的生存周期延長15%左右[5]。然而LEACH協(xié)議在數(shù)據(jù)傳輸階段中，簇首節(jié)點(diǎn)把收集到的數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)時(shí)，采用的是單跳通信，而由能耗模型可知，當(dāng)傳輸距離過大時(shí)，能耗量與距離的四次方成正比，將使節(jié)點(diǎn)的能量消耗過大，加速死亡。

2 基于改進(jìn)蟻群算法的ACO-BEC協(xié)議

蟻群算法[12](Ant Colony Optimization，ACO)是意大利學(xué)者Dorigo M受到螞蟻覓食這一生理習(xí)性的啟發(fā)所提出的算法。一方面，每個(gè)螞蟻可以探測(cè)到其它螞蟻留下的信息素，從而引導(dǎo)移動(dòng)方向規(guī)劃到達(dá)目的節(jié)點(diǎn)的路徑；另一方面，由于信息素具有揮發(fā)性，其濃度的大小也間接反映了該條路徑的長短及經(jīng)過的螞蟻數(shù)量，這在蟻螞蟻中構(gòu)成了一種信息素的正向反饋機(jī)制，因此，這個(gè)正反饋過程促使了在越短的路徑上殘留的信息素濃度越大。由于蟻群算法具有較強(qiáng)自適應(yīng)性、魯棒性、分布式等特點(diǎn)，具有十分廣闊的應(yīng)用前景。

2.1 協(xié)議網(wǎng)絡(luò)模型

所有傳感器節(jié)點(diǎn)被隨機(jī)布置在正方形區(qū)域，對(duì)該網(wǎng)絡(luò)做如下假設(shè)：

1)傳感器節(jié)點(diǎn)隨機(jī)部署后便不再移動(dòng)，且節(jié)點(diǎn)能量有限，能獲知坐標(biāo)信息和自身剩余能量；

2)所有節(jié)點(diǎn)具有相同的處理能力、通信能力、存儲(chǔ)能力，都能擔(dān)任活躍節(jié)點(diǎn)、簇頭或者普通節(jié)點(diǎn)；

3)基站位置固定，且能量不受限；

4)節(jié)點(diǎn)發(fā)射功率可控，且可通過信號(hào)的強(qiáng)度計(jì)算出節(jié)點(diǎn)之間的距離。

2.2 ACO-BEC協(xié)議簇首選舉

基于蟻群算法的ACO-BEC協(xié)議也采用LEACH的‘輪’的概念，每一輪包括兩個(gè)階段：簇的建立和穩(wěn)定數(shù)據(jù)傳輸。

在簇的建立階段，ACO-BEC協(xié)議同樣采用LEACH的選舉簇首方式，但對(duì)LEACH協(xié)議選舉時(shí)不考慮節(jié)點(diǎn)能量這一缺陷加以改進(jìn)，由此設(shè)定新的閾值T′(n)，具體定義為：

(2)

式中，Ei_current為節(jié)點(diǎn)i當(dāng)前的剩余能量，Einitial表示節(jié)點(diǎn)的初始能量。由式(2)可知，剩余能量越大的節(jié)點(diǎn)較之剩余能量少的節(jié)點(diǎn)，當(dāng)選為簇頭的概率更高。

2.3 穩(wěn)定數(shù)據(jù)傳輸

ACO-BEC協(xié)議的數(shù)據(jù)傳輸階段，不再是簇首與匯聚節(jié)點(diǎn)之間的直接單跳通信，而是利用蟻群算法自適應(yīng)啟發(fā)尋找一條在各簇首之間的最優(yōu)多跳路徑，進(jìn)而將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)。

2.3.1 蟻群算法的改進(jìn)

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)可以看作一個(gè)連通的無向加權(quán)圖G(N,V)，N為網(wǎng)絡(luò)的節(jié)點(diǎn)集合，V為節(jié)點(diǎn)間的鏈路。初始時(shí)，各鏈路上賦予相同的初始信息素濃度τij(0)，第k只螞蟻在行進(jìn)過程中，根據(jù)各鏈路的信息素濃度決定轉(zhuǎn)移方向，則從節(jié)點(diǎn)i出發(fā)選擇節(jié)點(diǎn)j作為下一跳的轉(zhuǎn)移概率為：

(3)

由式(3)可知，節(jié)點(diǎn)的下一跳轉(zhuǎn)移概率主要受節(jié)點(diǎn)間的距離影響，而無線傳感器網(wǎng)絡(luò)的主要性能指標(biāo)是網(wǎng)絡(luò)的生存壽命，這就必須要求節(jié)點(diǎn)能耗均衡，故應(yīng)使剩余能量多的節(jié)點(diǎn)作為下一跳的轉(zhuǎn)移概率大，故將節(jié)點(diǎn)剩余能量融入啟發(fā)函數(shù)中，改進(jìn)后的轉(zhuǎn)移概率為：

(4)

φij表示能耗因子，定義式如下：

(5)

式中，Ej為節(jié)點(diǎn)j的剩余能量，Eij-cost為節(jié)點(diǎn)i發(fā)送數(shù)據(jù)到下一跳節(jié)點(diǎn)j所需消耗的能量，dj-BS為節(jié)點(diǎn)j到基站的距離。由式(4)、(5)可看出，改進(jìn)后的蟻群算法模型應(yīng)用在無線傳感器網(wǎng)絡(luò)中，在簇首節(jié)點(diǎn)選擇下一跳時(shí)，轉(zhuǎn)移概率會(huì)依據(jù)節(jié)點(diǎn)間距離及下一跳節(jié)點(diǎn)的能量和距基站的距離關(guān)系共同選?。汗?jié)點(diǎn)間距離越短，下一跳距離匯聚節(jié)點(diǎn)越近，且能量越大的節(jié)點(diǎn)的成為下一跳的轉(zhuǎn)移概率越大。

2.3.2 信息素更新

基本的蟻群算法從更新信息素方法入手，提出了Ant-Cycle模型、Ant-Quantity模型和Ant-Density模型[12]。Ant-Cycle模型采用全局信息素更新策略，而后兩種模型則采用了局部信息素更新策略，即螞蟻?zhàn)哌^相鄰路徑后更新路徑信息素。本文為便于其他螞蟻根據(jù)信息素的濃度來判斷路徑，采用了局部信息素更新策略Ant-Quantity模型，及時(shí)對(duì)該路徑上的信息素進(jìn)行更新。

當(dāng)有螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的鏈路經(jīng)過，信息素做如下的更新：

(6)

(7)

式中，Q為體現(xiàn)信息素大小的一個(gè)常數(shù)，Ej代表了節(jié)點(diǎn)當(dāng)前的剩余能量，Hij代表該路徑的跳數(shù)，據(jù)此螞蟻就會(huì)傾向于選擇節(jié)點(diǎn)剩余能量較大、跳數(shù)較小的路徑。

3 仿真實(shí)驗(yàn)及性能分析

為了驗(yàn)證ACO-BEC協(xié)議的性能，本文采用MATLAB工具進(jìn)行仿真實(shí)驗(yàn)。在仿真過程中，數(shù)據(jù)的發(fā)送和接收模型仍采用LEACH協(xié)議的簡(jiǎn)單能耗模型。初始時(shí)，將能量為 2J 的 100 個(gè)節(jié)點(diǎn)隨機(jī)分布于 100 m×100 m 的覆蓋區(qū)域，匯聚節(jié)點(diǎn)位置為(0,0)，信道的帶寬是 2 Mb/s ，每個(gè)數(shù)據(jù)包長度為4 000 bit，控制消息長度為200 bit 。實(shí)驗(yàn)仿真的其它參數(shù)見表1。

表1 仿真參數(shù)

為了驗(yàn)證理論結(jié)果，通過仿真實(shí)驗(yàn)，分析了網(wǎng)絡(luò)生存周期、節(jié)點(diǎn)能耗情況在ACO-BEC協(xié)議和LEACH原協(xié)議以及文獻(xiàn)[8]改進(jìn)的DCST算法的對(duì)比關(guān)系。仿真分析如下：

由圖1可知，ACO-BEC協(xié)議的第一個(gè)節(jié)點(diǎn)死亡時(shí)間為150 s，在370 s左右節(jié)點(diǎn)基本死亡； LEACH協(xié)議在120 s左右就出現(xiàn)死亡，210 s左右節(jié)點(diǎn)全部死亡；而已改進(jìn)的DCST算法第一個(gè)死亡節(jié)點(diǎn)時(shí)間為140 s，在305 s左右節(jié)點(diǎn)基本死亡。這是由于ACO-BEC協(xié)議優(yōu)化路徑過程，并在網(wǎng)絡(luò)運(yùn)行時(shí)，考慮了節(jié)點(diǎn)的剩余能量及節(jié)點(diǎn)間的距離，使得其較LEACH協(xié)議以及DCST算法出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的時(shí)間分別延長了約25%、7%，網(wǎng)絡(luò)生命周期延長分別達(dá)到76%、23%。因此，ACO-BEC協(xié)議均衡了簇首的能量消耗，延長了網(wǎng)絡(luò)的生存時(shí)間。

圖1 網(wǎng)絡(luò)中剩余存活節(jié)點(diǎn)數(shù)目比較

圖2是網(wǎng)絡(luò)中節(jié)點(diǎn)的總能耗隨網(wǎng)絡(luò)的運(yùn)行周期的變化情況，可看出在網(wǎng)絡(luò)運(yùn)行的整個(gè)周期里，改進(jìn)協(xié)議ACO-BEC的總能耗一直低于LEACH協(xié)議及文獻(xiàn)[8]的DCST算法，這是由于在無線傳感器網(wǎng)絡(luò)中能量的消耗主要是由于數(shù)據(jù)的傳輸，原協(xié)議采用單跳通信傳輸數(shù)據(jù)，當(dāng)簇首節(jié)點(diǎn)與匯聚節(jié)點(diǎn)距離過大時(shí)，所需能耗更為明顯；改進(jìn)協(xié)議利用蟻群算法尋找一條最優(yōu)的多跳路徑，有效均衡了各節(jié)點(diǎn)的能耗，提高網(wǎng)絡(luò)壽命。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)總能耗比較

4 結(jié)論

路由協(xié)議是WSNs的核心關(guān)鍵技術(shù)，其性能的優(yōu)劣對(duì)網(wǎng)絡(luò)整體性能有著直接的影響。本文從提高網(wǎng)絡(luò)壽命和節(jié)省能耗兩個(gè)方面對(duì)LEACH 協(xié)議進(jìn)行了改進(jìn)，提出一種基于改進(jìn)蟻群算法的新型路由協(xié)議。該協(xié)議利用了蟻群算法的自適應(yīng)性，在選擇下一跳時(shí)考慮了節(jié)點(diǎn)的剩余能量和路徑距離對(duì)于轉(zhuǎn)移概率以及遺留信息素大小的影響，均衡了簇首節(jié)點(diǎn)的能耗。仿真實(shí)驗(yàn)結(jié)果表明，該協(xié)議能有效均衡網(wǎng)絡(luò)能量消耗，延長了網(wǎng)絡(luò)壽命。下一步研究的主要工作是：在確保網(wǎng)絡(luò)壽命的同時(shí)，對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)以及協(xié)議的安全性加以研究考慮。

[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] 任豐原,黃海寧,林 闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào), 2003, 14(7): 1282-1291.

[3] 崔遜學(xué),左從菊.無線傳感器網(wǎng)絡(luò)簡(jiǎn)明教程[M].北京:清華大學(xué)出版社,2009.

[4] 張曉玲,梁 煒,于海斌,等.無線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述[J].通信學(xué)報(bào),2012,33(5): 143-157.

[5] Heinzelman W R, Handrakasan A, Alakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[A]. HICSS 2000: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences[C]. Maui: IEEE Computer Society, 2000: 3005-3014.

[6] 趙菊敏,張子辰,李燈熬,等.基于LEACH路由協(xié)議的多跳節(jié)能路由算法[J].計(jì)算機(jī)測(cè)量與控制, 2014, 22(5):1506-1509.

[7] 董國勇,彭 力,吳 凡,等. 一種采用蟻群優(yōu)化的WSN能量均衡非均勻分簇路由算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(7):1565-1568.

[8] 劉林鋒,郭 平,趙 娟,等.無線傳感器網(wǎng)絡(luò)中一種基于改進(jìn)的LEACH協(xié)議的數(shù)據(jù)收集方案[J].計(jì)算機(jī)科學(xué), 2015 , 42(6):299-302.

[9] 張明才,薛安榮,王 偉.基于最小生成樹的非均勻分簇路由算法[J].計(jì)算機(jī)應(yīng)用,2012,32(3):787-790.

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

[11] 陳炳才,么華卓,楊明川,等.一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議[J].傳感技術(shù)學(xué)報(bào), 2014,27(3):373-377.

[12] Dorigo M, Blumb C. Ant colony optimization theory: A survey[J]. Theoretical Computer Science, 2005,344(2/3) :243-278．

Research on LEACH Protocol Based on Improved Ant Colony Algorithm

Yan Binheng, Liu Jun, Liu Guangbin, He Yangjiong

(Department of Information Engineering, Engineering College of PAP, Xi′an 710086,China)

In order to solve the problem of excessive energy consumption for transmitting to sink node directly from cluster heads in LEACH routing protocol, a routing protocol based on improved ant colony algorithm was proposed. This protocol introduced lead the energy consumption factor to improve the ant transition probability and the pheromone updating rule. And It would take full account of the residual energy of nodes and the distance between the nodes, through the establishment and update of pheromone, make sure to find the optimal path between cluster heads and base station, and use multi-hop transmission to balance the energy consumption of cluster nodes. Simulation results show that this improved routing protocol better than LEACH protocol on the cluster-head nodes selection, and it can extend the survival time of the network, and makes the energy consumption more balanced.

wireless sensor networks; LEACH protocol; ant colony algorithm; pheromone; energy balance

2016-06-20；

2016-07-17。

嚴(yán)斌亨(1993-)，男，福建仙游人，碩士研究生，主要從事無線傳感器網(wǎng)絡(luò)路由協(xié)議方向的研究。

劉 軍(1963-)，男，北京人，教授，碩士研究生導(dǎo)師，主要從事物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)、無線通信方向的研究。

1671-4598(2016)12-0136-03

10.16526/j.cnki.11-4762/tp.2016.12.039

TP393

A