基于蟻群算法和能耗均衡的改進LEACH協議*

周智勇，陳　暉，王海濤，王世界

(1.解放軍理工大學 通信工程學院研三隊,江蘇 南京 210007；2.解放軍理工大學 訓練部, 江蘇 南京 210007)

?

基于蟻群算法和能耗均衡的改進LEACH協議*

周智勇1，陳暉2，王海濤2，王世界1

(1.解放軍理工大學 通信工程學院研三隊,江蘇 南京 210007；2.解放軍理工大學 訓練部, 江蘇 南京 210007)

摘要：在分布式傳感器網絡的場景下，結合傳統的LEACH協議提出了一種基于有限信道信息的蟻群優化(ACO)路由算法。該算法中傳感器節點只需要獲取與相鄰節點間的信道信息，而不需要了解網絡的全局信息，就能夠逐步逼近最優路徑。在此基礎上，提出了一種基于能耗均衡的路由傳輸方案，有效改善了LEACH協議中簇頭節點能耗不均衡的情況。仿真實驗表明：基于蟻群算法和能耗均衡的改進路由方案，能夠利用局部信息快速搜索到能耗最低的路徑，并在傳輸過程中有效地均衡簇頭能耗，從而有效提高了網絡生存時間。

關鍵詞：網絡生存時間；LEACH協議；蟻群算法；能耗均衡

0引言

近年來，無線傳感器網絡(wireless sensor networks, WSNs)技術在物聯網、戰場目標監控和信息收集等領域的得到了廣泛的應用[1]。傳感器網絡由分布在一定區域內的大量傳感器節點和負責收集信息的匯聚節點組成。通常情況下，傳感器節點由自身攜帶的電池供電，因而能量有限并且難以再次充電。如何降低傳感器網絡中的能量消耗已經成為了當前傳感器網絡的研究熱點，而路由協議的設計就是其能耗優化的關鍵技術之一。

文獻[2]提出的LEACH(low energy adaptive clustering hierarchy)協議是一種典型的分層路由協議，LEACH協議通過簇結構分層的方式,當傳感器節點有傳輸數據包的需求時固定向上層的簇頭節點發送數據包，少量的簇頭節點間通過接力等方式將數據包傳送到Sink節點處。這種分層的方式有效避免了節點在傳輸信息時的無方向和無序性，避免信息洪泛所造成的網絡冗余信息過多的現象。文獻[3-6]等對傳統的LEACH進行了改進，其中文獻[3-4]主要針對LEACH協議中簇頭節點的選取規則進行重新設計，在簇結構形成階段選取簇頭時考慮各個傳感器節點的剩余能量、與其他節點的平均距離等因素，文獻[5-6]則在不同限制條件下對于簇結構的形成和簇頭節點的形成進行了討論。可以看出，當前對于LEACH協議的改進主要集中在LEACH協議第一階段，也就是對于簇結構和簇頭節點選取的規則進行優化。而對于簇形成之后簇頭節點信息傳遞過程中的不同路由方式對于提升網絡生存時間的影響研究則比較少，尤其是對于沒有統一的管理節點，各個節點均不了解網絡全局信息的分布式傳感器網絡的場景的研究比較缺乏。

文獻[7]提出的定向擴散的方法，使距離Sink節點較遠的外層節點方向性地向距離Sink節點較近的節點傳送數據。文獻[8-10]提出在分布式傳感器網絡中基于搜索樹的路由方案。可以發現，當前對于簇結構形成之后路由的搜索主要以能耗最低的最優路由為目標。文獻[11]的NBEERP(negotiation-based energy efficient routing protocol)路由協議提出節點保留多條可以到達網絡匯聚節點Sink的路由，但其保留多條路徑的目的在于提高網絡的魯棒性，而沒有關注保留多條路徑對于均衡簇頭節點能耗、提升網絡生存時間的意義。針對這一研究現狀，本文提出了一種能夠綜合利用多條路徑均衡傳送信息的路由傳輸方案。

文章著重了研究基于蟻群算法和能耗均衡的LEACH路由方案，并對該方案的網絡生存時間和覆蓋性能進行了仿真和對比，具體的工作和章節安排如下所示：

(1)第二部分在接力傳輸方式下對傳感器網絡的能耗情況進行系統描述和公式建模，對與傳統的LEACH協議和蟻群算法的運行過程進行了簡要的描述；

(2)第三部分主要描述了本文提出的基于蟻群算法和能耗均衡的路由方案的運行過程，給出算法的細節，并對該方案的有效性進行了初步的分析；

(3)第四部分在分布式傳感器網絡中基于有限的信道信息條件下對于蟻群算法搜索最優路徑的有效性進行了仿真驗證，并對本文提出的基于蟻群算法和能耗均衡的路由方案與其他文獻中提出的路由方案進行了比較仿真。

(4)第五部分對實驗結果和本文的主要工作進行總結。

1模型描述

1.1通信模型

傳感器網絡采用傳統的LEACH分簇路由協議[2]。設定我們需要監控的區域為二維區域A，以匯聚節點Sink(0,0)為圓心，半徑為y=250 m的圓形區域。監控目標D在區域A內隨機出現。當監控目標D在傳感器節點m的感知距離內時，傳感器節點m生成可以傳輸的信息。生成的數據包將通過LEACH協議傳輸到匯聚節點Sink處。

1.2能耗模型

本文中點對點通信采用QPSK方式，根據文獻[12]，該通信方式的誤碼率特性為：

(1)

bQPSK=sin2(π/4)

(2)

式中，ρ表示接收端信噪比。若通信需要的最低誤碼率要求為ΨQPSK≤ρrequire時，通過查表的方式可以逆向得到最低接收信噪比為ρ0。發送功率與接收端信噪比滿足路徑損耗方程：

(3)式中，P、N0分別為發送功率、噪聲功率，h為理想瑞利信道的衰落系數，d為發送端和接收端的距離，α為路徑損耗系數，Gt、Gr分別為發送和接收天線增益。當ρ=ρ0時，可以計算出發送端需要的發送功率：

(4)

1.3LEACH協議

LEACH協議的運作過程可以準備階段和穩定階段，在準備階段進行簇頭節點的選取和簇的形成，在穩定階段進行數據的搜集和傳輸。網絡循環經歷準備階段和穩定階段。如圖1所示。

圖1　LEACH協議運行過程

在準備階段，節點隨機被選作簇頭節點，所有簇頭節點廣播通告信息ADV，其他傳感器節點根據接收到的不同的ADV信號強度選擇加入信號最強的簇頭所在的簇。

在穩定階段，當有傳感器節點需要向Sink節點傳輸數據，該節點首先將數據包發送至其所在的簇的簇頭節點，由簇頭節點通過其他簇頭節點將信息接力到Sink節點處。

1.4蟻群算法

蟻群算法(Ant Colony Algorithm, ACO)是一種新興的仿生算法，具有較強的魯棒性和優良的分布式計算機制，適合本文分布式傳感器網絡的場景中。蟻群算法用于解決本文路由搜索為的基本流程如圖2所示。

圖2　蟻群算法運行流程

1.5網絡生存時間

文獻[13-15]對網絡生存時間進行了不同的定義，其中文獻[13-14]將網絡生存時間定義為從網絡開始運行到出現能量耗盡的節點時所經歷的時間，而文獻[15]將網絡生存時間定義為從網絡開始運行到網絡對監控目標區域的覆蓋率下降到容忍值的時間。本文采取前一種的定義方式，這是因為一旦網絡中出現死亡節點，死亡節點周邊其他傳感器節點的能耗急劇增加，導致其他的傳感器節點很快耗盡電池的能量。能夠有效推遲第一個節點的死亡時間的節點分布模型具有很大可能能夠推遲大部分節點的死亡。

2基于蟻群算法和能耗均衡的LEACH路由方案

在本文提出的基于蟻群算法和能耗均衡的LEACH路由方案中，蟻群算法主要用于在LEACH協議中簇結構形成之后簇頭間的路由搜索過程。由于蟻群算法只需要各個簇頭間的信道信息而不需要了解網絡的全局信息，因而蟻群算法的路由搜索方案適用于不存在中心控制節點的分布式傳感器網絡當中。各個簇頭節點間的信道信息可以在簇頭節點選取和簇結構形成階段獲取，各簇頭節點根據其他簇頭節點廣播的ADV信息，獲取臨近的信道狀態，并將這些信道狀態作為初始的局部信息。

各簇首節點確定初始信道信息之后，向周圍簇頭發送少量數據，數據的在節點之間的接力傳輸過程遵循蟻群算法。各數據包每前進一步，所在的簇首節點即存儲并更新禁忌表(這里禁忌表即為數據包已經訪問過的簇首集合)，若發現禁忌表中已經包含了Sink節點，則立即停止該數據包的傳遞。將所有數據包均前進一步作為一個循環，每次循環之后需要進行信息素的更新，即各簇首節點根據自身發送功率分布情況，以節點間傳輸的功率信息類比作為蟻群算法中的信息素進行實時更新，進而獲得新的路由轉移概率值，為下一個循環中各數據的傳遞提供參考。至此，蟻群路由算法的一個運轉周期結束。經過足夠多個周期的運轉之后，各簇首節點能夠根據所存儲的轉移概率值和禁忌表信息，建立路由表。

為了找到與Sink之間的最優路徑，簇頭節點需要根據反饋信息不斷更新和存儲最優路徑。通過這一過程，能夠實現從局部最優路徑逐步逼近全局最優路徑。

能耗均衡的方案主要用于網絡穩定運行階段，其主要思想是當簇頭節點需要向Sink節點傳輸數據時，依概率選擇能耗最低和次最低的路徑進行傳輸。能耗均衡的主要目的是避免過度使用同一條路徑對該路徑上的傳感器節點造成過大的能耗壓力。本文設定選擇最優能耗路徑和次優能耗路徑的概率與其路徑能耗成反比，即能耗較低的路徑被選擇的概率大，而能耗較高的路徑被選擇的概率小。設定選擇最優路徑的概率為：

(5)

選擇次優路徑的概率為：

(6)

式中，Eoptimal和Esub_optimal分別表示最優路徑和次優路徑上的能耗。網絡經過足夠長時間的運行，最優和次優路徑上的能耗均為：

(7)

雖然能耗均衡的方法提升了每次傳輸所消耗的能量，但能耗均衡的方法能夠較好的分配數據傳輸所產生的傳輸能耗，降低只利用最優路徑進行傳輸對于最優路徑上的節點的能耗壓力。可以推測，當網絡規模較大，尤其是簇頭節點數量較多時，最優路徑和次優路徑能耗差值較小，此時能耗均衡的方案效果更佳明顯。本文提出的基于蟻群算法和能耗均衡的LEACH路由方案具體細節如下：

算法名稱：基于蟻群算法和能耗均衡的LEACH協議改進方案。

輸入：傳感器節點與鄰近節點間信道信息。

輸出：

步驟1：

根據LEACH協議，網絡中的節點選舉簇頭節點，簇頭節點向周圍節點等功率廣播被選作簇頭節點的信息ADV，其他節點依據接收信號ADV的強度加入各個簇，其他簇頭節點根據接收信號ADV得到信道信息。

步驟2：

整個論壇都炸開來，網友回帖回了十幾頁，有鼓勵，有驚嘆，有支持，惟獨沒有抨擊。太多人知道羅漠的寂寞，有人對他說，你們的愛情感動了所有人，可是逝者已矣，如果楚西有靈，她也必是不愿見你孤獨一生。

各簇頭節點根據先驗信息和功率信息素初始值，對各自狀態轉移概率進行初始化設置。隨后各簇頭根據初始轉移概率向Sink節點發送少量數據包，任意數據包在接力傳輸過程中每實現一跳，相應的簇頭節點立即對禁忌表進行修改并存儲，當全部數據包均前進一步完成一個周期之后，所有簇頭節點更新功率信息素，并計算存儲新的狀態轉移概率值，進入新的周期。經過充分迭代之后，蟻群算法實現收斂，輸出路由表信息。

步驟3：

根據步驟4輸出的路由表信息，各個簇頭節點都能搜索各自到Sink節點的能耗最優和次優路徑，并將最優和次優路徑保存。

步驟4：

步驟5：

經過一段時間的運行，網絡進行簇頭節點的重新選舉和簇的重構。

3仿真和數據分析

設定監控區域為二維區域A為以匯聚節點Sink(0,0)為圓心，半徑為y=250m的圓形區域。需要監控的目標隨機出現在區域A內，且目標的分布滿足均勻分布。區域A內傳感器總數為100個。其它仿真參數的設置如表1所示。

表1　仿真參數設置

圖3展示了傳統的以能耗最低路徑為搜索目標的方案和本文基于ACO和能耗均衡的方案網絡的生存時間的對比。這里的網絡生存時間指網絡從開始運行到網絡出現第一個節點因耗盡能量而死亡的時間。從圖中可以看到，在5次仿真中，本文提出的基于ACO和能耗均衡的LEACH算法能夠有效延長網絡的生存時間，提升的幅度最大可以達到12.5%。從而說明，能耗均衡能夠較好地均衡網絡中各個節點的傳輸能耗，從而推遲網絡中第一個節點死亡時間的到來。

圖3　網絡生存時間比較

本文進而仿真了網絡的覆蓋率隨著時間的變化情況。網絡覆蓋率定義為網絡中所有傳感器能夠探測到的區域面積占目標總區域的比例。選擇對于網絡的覆蓋率變化情況進行仿真的原因在于網絡覆蓋率的變化很大程度上反映了網絡中節點的死亡情況。網絡覆蓋率的下降說明網絡中死亡節點數量的增加。另外，網絡覆蓋率是網絡實現其功能最重要的指標，當覆蓋率下降到一定程度時網絡已經失去正常運行的功能。

圖4展示了在網絡達到網絡生存時間后，即出現第一個節點死亡后，網絡覆蓋率隨時間變化情況。仿真中每隔10 000輪進行網絡覆蓋率的測算，由于仿真采用蒙特卡洛方法，因而曲線呈現略微的抖動。從圖中可以看出，兩種方案的初始覆蓋率相當，并隨著時間的推移逐漸下降，說明不斷有節點因為能量耗盡而死亡。對比文獻[9]中的搜索樹的路由方法和本文中的基于ACO和能耗均衡的LEACH方案的覆蓋率情況，網絡在9×105輪之前，本文提出的方案覆蓋率較高，而在9×105之后，本文的方案覆蓋率較低。而網絡在9×105輪時網絡的覆蓋率為50%，即網絡只能對50%的區域實現有效的探測和信息感知，網絡已經基本失去其基本功能。因而可以總結：本文提出的基于蟻群算法和能耗均衡的LEACH方案在網絡正常運行的大部分時間覆蓋率較之前以能耗最優路徑為搜索目標的方案高，從而證明了本文提出的算法的優越性。

圖4　網絡覆蓋率隨時間變化的比較

4結語

針對傳感器網絡中較為關心的提升能量利用效率和網絡生存時間問題，本文就分布式傳感器網絡的場景設計了一種基于蟻群算法和能耗均衡的改進LEACH協議方案。通過引入蟻群算法實現了數據路由過程中局部最優向全局最優的逼近，從而解決了有限信息條件下的路徑搜索問題。在此基礎上進一步設計了能耗均衡的路由選路方案，平衡了各個節點的傳輸能耗。改進的LEACH協議更加貼近于實際應用場景，同時具有更優的能耗性能。仿真結果表明本文提出的方法在提升網絡生存時間和覆蓋率等方面的優勢。

參考文獻：

[1]Akyildiz I F, SU W, Cayirci E. A Survey on Sensor Networks[J]. Communications Magazine IEEE,2002,40(8):102-114.

[2]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]// Proceedings of the 33rd Hawaii International Conference on System Sciences,Hawaii:IEEE Press,2000:8020.

[3]Manjeshwar A, Agrawal D P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[J]. Proc Ipdps Workshops,2001:2009-2015.

[4]白永祥. 一種LEACH路由協議算法的改進與分析[J]. 通信技術: 2015, 48(09):1062-1067.

BAI Yong-xiang. Improvement and Analysis of LEACH Routing Protocol Algorithm. Communications Technology: 2015, 48(09):1062-1067.

[5]Heinzelman W B, Chandrakasan A P, Balakrishnan H. AnApplication-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[6]Tripathi M, Gaur M S, Laxmi V, et al. Energy Efficient LEACH-C Protocol for Wireless Sensor Network[C]// The 3rd International Conference on Computational Intelligence and Information Technology. CIIT 2013: IET Press, 2013:402-405.

[7]Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks[J]. Wireless Networks, 1999, 8(2/3):169-185.

[8]Gagarin A, Hussain S, YANG L T. Distributed Hierarchical Search for Balanced Energy Consumption Routing Spanning Trees in Wireless Sensor Networks [J]. Journal of Parallel & Distributed Computing, 2010, 70(9):975-982.

[9]Chang R Y,Chung W H. Best-First Tree Search with Probabilistic Node Ordering for MIMO Detection: Generalization and Performance-Complexity Tradeoff[J]. IEEE Transactions on Wireless Communications,2012,11(2):780-789.

[10]GUidoni D L,Boukerche A,Villas L A, et al. A Tree-based Approach to Design Heterogeneous Sensor Networks Based on Small World Concepts[C]// The 36th Conference on Local Computer Networks (LCN 2011). Bonn:IEEE,2011:666-672.

[11]王王春. 無線傳感器網絡路由協議的設計與仿真[D].成都：電子科技大學, 2004.

WANG Chun. Design and Simulation of Routing Protocol for Wireless Sensor Networks[D]. University of Electronic Science and Technology of China,2004.

[12]LIU K J R. Cooperative Communications and Networking[M]. Cambridge:Cambridge University Press,2009.

[13]CHENG P, CAI C N, LIU X. Energy-Aware Node Placement in Wireless Sensor Networks[C]//Global Telecommunications Conference, 2004. Dallas: IEEE Press, 2004: 3210-3214.

[14]ZHANG J, SONG C, Sharif H, et al. A Battery-Aware Deployment Scheme for Cooperative Wireless Sensor Networks[C]// Global Telecommunications Conference, 2009. Hawaii: IEEE Press, 2009:1-5.

[15]IShizuka M, Aida M. Performance Study of Node Placement in Sensor Networks[C]// International Conference on Distributed Computing Systems Workshops, 2004. Tokyo: IEEE Press, 2004: 598-603.

Modified LEACH Protocol based on Ant Colony Optimization and Energy Balance

ZHOU Zhi-yong1，CHEN Hui2，WANG Hai-tao2，WANG Shi-jie1

(1.Institute of Communications Engineering;2.Department of Training, PLA University of Science and Technology,Nanjing Jiangsu 210007,China )

Abstract：Under the scenario of distributed wireless sensor networks, and in combination with the traditional LEACH protocol, an ACO(Ant Colony Optimization) routing algorithm based on limited channel information is proposed. This algorithm,with only a limited neighbor channel information required for each node, and no need for global information,could generally approach the optimal route. In light of this, a route transmit scheme based on load balance is suggested, which could effectively solve the problem of energy consumption unbalance of between the cluster heads in LEACH. Simulation experiments show that the modified routing algorithm based on ACO and energy balance could search for the optimal route in a high speed with local message, and in addition, could effectively balance the energy consumption of between the cluster heads,and prolong the network lifetime.

Key words：network lifetime; LEACH protocol; ant colony optimization; energy balance

doi:10.3969/j.issn.1002-0802.2016.04.013

*收稿日期：2015-11-09；修回日期：2016-02-20Received date:2015-11-09；Revised date：2016-02-20

基金項目：國家自然科學基金(No.61301157)

Foundation Item:National Natural Science Foundation of China (No.61301157)

中圖分類號：TP393

文獻標志碼：A

文章編號：1002-0802(2016)04-0446-06

作者簡介：

周智勇(1990—)，男，碩士研究生，主要研究方向為網絡信息系統工程；

陳暉(1974—)，男，教授，主要研究方向為網絡信息系統工程；

王海濤(1976—)，男，副教授，主要研究方向為計算機應用；

王世界(1990—)，男，碩士研究生，主要研究方向為網絡信息系統工程。