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

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

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

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

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

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

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

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

0 引言

20世紀(jì)五六十年代以來，隨著計算機(jī)網(wǎng)絡(luò)技術(shù)、無線通信技術(shù)、傳感器技術(shù)和分布式處理技術(shù)等高新技術(shù)的成熟發(fā)展，無線傳感器網(wǎng)絡(luò)[1](WSNs，Wireless Sensor Networks)逐步形成。WSNs是由大量體積小、成本低、電池供電的傳感器節(jié)點密集分布在一定范圍內(nèi)的自適應(yīng)系統(tǒng)[2]，這些傳感器節(jié)點在部署范圍內(nèi)協(xié)同進(jìn)行數(shù)據(jù)的采集、存儲、處理和傳輸，完成對整個區(qū)域的監(jiān)控。目前廣泛應(yīng)用于軍事、工業(yè)、農(nóng)業(yè)、醫(yī)學(xué)和搶險救災(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ù)的單跳傳輸模式，使得能量消耗不均，加速個別節(jié)點死亡，影響整體網(wǎng)絡(luò)壽命[6]。因此，針對LEACH協(xié)議的缺陷，越來越多的改進(jìn)協(xié)議被提出來，文獻(xiàn)[7]考慮節(jié)點剩余能量、節(jié)點稀疏程度等因素來保證最優(yōu)簇頭，同時將優(yōu)化過的蟻群算法用于選擇最優(yōu)能量路徑完成簇頭間信息傳輸；文獻(xiàn)[8]提出的DSCT算法在以改進(jìn)的LEACH協(xié)議對WSN進(jìn)行分簇的基礎(chǔ)上，利用蟻群算法尋找出連接所有簇首的最優(yōu)路徑，使移動sink沿著此路徑移動并進(jìn)行數(shù)據(jù)收集；文獻(xiàn)[9]提出的基于最小生成樹的非均勻算法UCRAMST算法利用節(jié)點的剩余能量選舉簇首，通過建立最優(yōu)傳輸路徑減少能量消耗。但是以上一些改進(jìn)方法或在計算轉(zhuǎn)移概率以及更新信息素只考慮能量并未考慮節(jié)點及鏈路的其它狀況，或是過于復(fù)雜，這將不利于網(wǎng)絡(luò)節(jié)點能量的均衡和節(jié)省。因此，本文在LEACH協(xié)議的基礎(chǔ)上，提出一種基于蟻群算法的改進(jìn)協(xié)議ACO-BEC (balanced energy consumption based on ACO for LEACH)，該協(xié)議在數(shù)據(jù)傳輸時利用優(yōu)化后的蟻群算法尋找最優(yōu)路徑，采用多跳模式，在搜尋下一跳時考慮節(jié)點的剩余能量，避免節(jié)點過早死亡，從而延長網(wǎng)絡(luò)壽命。

1 LEACH協(xié)議分析

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

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

(1)

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

選舉完成后，簇首節(jié)點主動廣播身份消息，非簇節(jié)點根據(jù)接收到的廣播信號的強(qiáng)度來選擇要加入的簇，并向簇首反饋加入信息，各簇內(nèi)節(jié)點采用TDMA方式與簇首通信；簇建立完成后，各成員節(jié)點若有數(shù)據(jù)要發(fā)送，就利用各自分配的時間片將數(shù)據(jù)發(fā)送到簇首，當(dāng)簇首節(jié)點接收到所有的數(shù)據(jù)后，對數(shù)據(jù)進(jìn)行融合處理，將有用的數(shù)據(jù)發(fā)送到匯聚節(jié)點；持續(xù)一段時間之后，整個網(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é)點把收集到的數(shù)據(jù)傳輸至匯聚節(jié)點時，采用的是單跳通信，而由能耗模型可知，當(dāng)傳輸距離過大時，能耗量與距離的四次方成正比，將使節(jié)點的能量消耗過大，加速死亡。

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

(3)

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

(4)

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

(5)

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

2.3.2 信息素更新

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

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

(6)

(7)

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

3 仿真實驗及性能分析

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

表1 仿真參數(shù)

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

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

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

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

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

4 結(jié)論

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

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

[4] 張曉玲,梁 煒,于海斌,等.無線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述[J].通信學(xué)報,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ī)測量與控制, 2014, 22(5):1506-1509.

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

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

[9] 張明才,薛安榮,王 偉.基于最小生成樹的非均勻分簇路由算法[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é)報, 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