嚴斌亨，劉 軍，劉廣斌，何楊炯

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

基于改進蟻群算法的LEACH協議研究

嚴斌亨，劉 軍，劉廣斌，何楊炯

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

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

無線傳感器網絡；LEACH協議；蟻群算法；信息素；能量均衡

0 引言

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

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

1 LEACH協議分析

經典LEACH協議采用分簇拓撲控制的管理機制，一組節(jié)點形成一個簇，簇成員與簇首通信，簇首匯聚并融合采集的數據并轉發(fā)至匯聚節(jié)點，協議引入了‘輪’的概念，每一輪包括兩個階段：簇的建立階段及數據穩(wěn)定傳輸階段[10]。

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

(1)

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

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

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

2 基于改進蟻群算法的ACO-BEC協議

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

2.1 協議網絡模型

所有傳感器節(jié)點被隨機布置在正方形區(qū)域，對該網絡做如下假設：

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

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

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

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

2.2 ACO-BEC協議簇首選舉

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

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

(2)

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

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

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

2.3.1 蟻群算法的改進

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

(3)

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

(4)

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

(5)

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

2.3.2 信息素更新

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

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

(6)

(7)

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

3 仿真實驗及性能分析

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

表1 仿真參數

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

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

圖1 網絡中剩余存活節(jié)點數目比較

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

圖2 網絡節(jié)點總能耗比較

4 結論

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

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

[2] 任豐原,黃海寧,林 闖.無線傳感器網絡[J].軟件學報, 2003, 14(7): 1282-1291.

[3] 崔遜學,左從菊.無線傳感器網絡簡明教程[M].北京:清華大學出版社,2009.

[4] 張曉玲,梁 煒,于海斌,等.無線傳感器網絡傳輸調度方法綜述[J].通信學報,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路由協議的多跳節(jié)能路由算法[J].計算機測量與控制, 2014, 22(5):1506-1509.

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

[8] 劉林鋒,郭 平,趙 娟,等.無線傳感器網絡中一種基于改進的LEACH協議的數據收集方案[J].計算機科學, 2015 , 42(6):299-302.

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

[10] 孫利民,李建中,陳 渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[11] 陳炳才,么華卓,楊明川,等.一種基于LEACH協議改進的簇間多跳路由協議[J].傳感技術學報, 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。

嚴斌亨(1993-)，男，福建仙游人，碩士研究生，主要從事無線傳感器網絡路由協議方向的研究。

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

1671-4598(2016)12-0136-03

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

TP393

A