能耗最優的LEACH協議改進

周 萌，陳躍東，陳孟元

安徽工程大學 安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000

能耗最優的LEACH協議改進

周 萌，陳躍東，陳孟元

安徽工程大學 安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000

1 引言

無線傳感器網絡（Wireless Sensor Network，WSN）是一種新興的信息感知和數據采集網絡系統，能夠實現人與物理世界的通信和信息交互，在眾多領域具有廣闊的應用前景[1]。由于網絡節點采用電池供電，且往往部署于惡劣的、人類難以到達的環境中，節點電能耗盡后難以及時補充或更換，因此能耗問題是制約無線傳感器網絡應用和發展的首要問題。

路由協議是組網的基礎和數據傳輸的關鍵，改進適用于無線傳感器網絡的路由協議可以有效降低節點的能耗，延長網絡生命周期。LEACH協議（低功耗自適應集簇分層型協議，Low Energy Adaptive Clustering Hierarchy）是具有代表性的層次路由，采用區域集中控制的方法，從各區域節點中選出簇頭，通過簇頭向基站轉發簇內信息，與直接傳輸、最小傳輸能量等路由相比較，可以有效降低節點能耗[2-3]。

LEACH協議執行過程中，由于部分節點耗能過快、過早死亡會造成網絡不完全聯通，導致網絡性能急劇下降，因此網絡能耗不均是LEACH協議急需解決的首要問題。

2 LEACH協議

2.1 協議原理及分析

LEACH協議按“輪”周期執行，每輪包括簇頭選取、簇的形成和數據傳輸三個階段。在簇頭選取階段，各節點分配一個介于0～1的隨機數，若隨機數大于本輪的閾值，節點當選為簇頭。簇頭選取完成后，簇頭向周圍節點廣播通告自身的簇頭狀態、ID和本簇的分組頭。周圍節點根據接收信號的強度確定加入最近距離的簇，并將自身和簇頭的ID通知相應的簇頭節點。在數據傳輸階段，簇頭以TDMA方式安排簇內節點的時間調度，節點按分配的時隙將數據傳送給簇頭，簇頭將數據包去冗處理后，按照不同的CDMA代碼直接發送給基站。

LEACH協議中，簇內節點僅在分配的時隙內開啟無線發送裝置進行數據傳輸，其余時間進入休眠狀態，大量節省了節點能量；同時，簇頭在發送數據前經過去冗處理，減小了發送開銷。但LEACH協議的簇頭選取沒有考慮參選節點自身的因素，僅依靠隨機數產生，造成簇頭分布不均、簇的規模差異大、簇頭能耗不均；數據傳輸過程中，節點能耗與距離呈指數增長，距離基站遠處的簇頭需要消耗大量能量將數據直接發送至基站，造成能耗過快、過早死亡。

2.2 協議相關研究

針對LEACH協議的不足，近年來許多學者進行了研究和改進。針對簇頭選取、分布不合理，文獻[4]結合節點剩余能量和距離因素改進了閾值公式；文獻[5]將節點能耗比和度作為簇頭選擇依據；文獻[6]在閾值中考慮了節點密度和剩余能量；文獻[7]中的簇頭選取概率由局部區域節點的分布數量控制；文獻[8]綜合考慮了節點能量和位置信息，這些改進方法從一個方面或者多個方面優化了簇頭節點的當選條件，但是對影響因子歸納和定量的全面性存在一定不足。在簇的形成階段，文獻[9]提出了簇頭競爭半徑自適應調節成簇的方法；文獻[10]通過減小近基站節點的成簇半徑實現非均勻分簇，文獻[11]采用神經網絡進行分簇；文獻[12]采用遺傳模擬退火算法進行固定分簇，這些改進與簇頭選取方案相適應，共同達到均衡簇頭能耗的目的。在數據傳輸策略上，文獻[13]通過最優跳數路徑降低網絡能耗；文獻[14]將簇內節點的高度值形成樹，使簇內數據沿樹傳輸；文獻[15]利用位置信息選擇能耗最小的最優轉發簇頭，這些成果表明，LEACH協議的數據傳輸方式應該由單跳改進為多跳或者單多跳結合，轉發節點的選擇也要以能耗最小為目標。還有一些研究者討論了多跳路由中距離和能量的關系，文獻[16]提出能距比的概念并計算出節點的最佳發送距離，文獻[17]推導了單多跳節能的臨界距離。

AD-LEACH協議是在以上研究的基礎上，綜合考慮影響簇頭分布的因素，細分了節點的類型，進行閾值的改進。在簇的形成階段，節點根據自身坐標計算所屬簇的矩陣二維值，通過匹配方式將網絡分成若干個均勻的網格。數據傳輸采用單多跳結合的方式，轉發節點的選取結合了最佳轉發距離和剩余能量，可調轉發收斂的速度，較好地解決了簇頭分布和網絡能耗不均的問題。

3 AD-LEACH協議

3.1 簇頭選取過程

影響簇頭在網絡分布和能耗的因素主要有節點能量、和基站的距離、節點密度等。簇頭節點必須具有足夠高的能量，用以處理和轉發本簇數據，同時簇頭的分布需要考慮節點密度和多跳路由引入的“熱區”問題。AD-LEACH協議區分出三類特殊節點，包括：I型高能節點；II型“熱區”節點；III型密集區域節點，通過提高特殊節點的當選概率，均衡簇頭的負擔。

網絡中非特殊的節點為普通節點，閾值公式與LEACH協議相同，表示為：

對于特殊節點，做出以下定義：

定義1若節點能耗率與網絡平均能耗率的商差值?小于0，滿足公式：

定義4若節點滿足公式（1）、（2）、（3）中兩項或以上，則該節點為交集節點，其閾值公式T4(n)通過加權方式確定。ε、η、θ分別為I、II、III型節點的加權值：

與LEACH簇頭選取的目前改進方案相比，AD-LEACH從造成能耗失衡的根源出發，按照節點自身特點進行了分類，并有針對性地改進了簇頭當選概率，使簇頭選取更合理性、網絡能耗更均勻。

3.2 分簇過程

在簇頭選取過程中，AD-LEACH已經權衡了節點能量、位置等因素的影響，采用不均勻分簇的方法會造成因素之間影響失衡，并不適用于AD-LEACH。

AD-LEACH協議通過節點位置模糊匹配的方式將網絡分成若干個相同大小的網格。矩形網絡區域長為L，寬為W，將長邊劃分為a等分，寬邊劃分為b等分，網絡被等分為a×b個矩形網格。為了保證網格內節點可靠通信，a、b的選值滿足約束條件 4(W2a2+L2b2)＜a2b2d2，d為節點的通信半徑。如圖1所示，按照矩陣排列給所有網格分配一個二維值 (i，j)，i=1，2，…，L/a; j=1，2，…，W/b。

所有節點計算自身所屬網格的二維值，滿足位置匹配條件的節點劃分在同一網格。

3.3 數據傳輸過程

AD-LEACH協議采用基于最佳轉發距離的數據傳輸方式，包括以下過程：

圖1 網格二維值分布示意圖

（1）定義距離閾值d_limit，若簇頭節點n與基站的距離小于d_limit，節點采用單跳方式，直接與基站通信，完成數據傳輸。

（2）若簇頭節點n與基站的距離大于d_limit，先完成簇內數據處理。網格內的簇頭接收本簇節點的數據包，若一個網格包含多個簇頭，普通節點的數據包發送至距離最近的簇頭。

（3）簇內數據處理完成后，各個網格中的簇頭成為待轉發節點，進行簇外數據傳輸，采用多跳方式，選擇合適的轉發節點，將數據傳送至基站。

多跳方式的數據傳輸流程圖如圖2所示。

圖2 Ad-LEACH協議的數據傳輸流程圖

以簇頭節點n為圓心，dc+db和dc-dl為外徑和內徑作圓環，在圓環區域內選擇最佳轉發節點，其中，dc為最佳轉發距離，當節點選擇距離為dc的節點轉發數據時，節點的能量利用率最高，dc+db、dc-dl分別為外徑和內徑的增補量，控制節點搜索面積。

若圓環區域內有N個簇頭，剩余能量分別為E1、 E2、…、EN，和基站的距離分別為 d1、d2、…、dN，為了使數據盡快轉發到基站，通過距離條件加快收斂，距離條件為 di＜β1d0，其中，d0為待轉發節點與基站的距離，β1為距離衰減因子，調節轉發收斂的速度。

對于符合距離條件的M個簇頭，將它們與基站的距離值從大到小排序，分別計分1、2、…、M ；剩余能量值從小到大排序，分別計分1、2、…、M，定義距離的權重為w1，能量的權重為w2。若節點n的距離計分為Sn，能量計分為 En，則其總得分為Un=Sn×w1+En×w2(i= 1，2，…，M)，總得分最高的候選簇頭當選為轉發節點。

若圓環中不含簇頭或不含滿足距離條件的簇頭時，選擇圓環中的普通節點作為轉發節點。為了減少計算開銷，加快擺脫圓環無合適簇頭的狀況，，使當選節點盡量靠近基站，距離條件di＜β2d0中距離衰減因子取得較小些，β2＜β1。在滿足距離條件的普通節點中選取能量最高的作為最佳轉發節點。

4 仿真結果及分析

4.1 環境模型本文采用NS2平臺進行仿真，仿真環境為：節點總數為100，隨機分布于100 m×100 m的區域，基站位置為（0，0）（單位：m），節點初始能量均為2 J，最佳簇頭百分比為5%，仿真時間為600 s。能量模型與LEACH相同，Eelec=50 nJ/bit，εfs=10 pJ/bit·m2，εmp=0.001 3 pJ/bit·m4，d0=87 m。

4.2 對比協議選擇

在對改進前后的LEACH協議仿真的同時，添加了EEUC協議（Energy-Efficient Uneven Clustering，能量高效的非均勻分簇協議）作對比。EEUC在保留LEACH分簇思想的基礎上，簇頭選取過程中充分考慮到節點自身的能量，同時采用多跳方式解決離基站遠的簇頭過早死亡的問題，是對LEACH協議很大的改進[18-19]。在仿真平臺下對三種協議進行仿真實驗并對比分析。

4.3 結果與分析

圖3是分別采用三種協議的網絡中存活節點數n與時間t關系的仿真結果，圖4是網絡總能耗e與時間關系t的仿真結果，圖5是數據包發送總字節數 p與時間關系t的仿真結果。

由圖3可知，LEACH網絡中出現第一個死亡節點的時間為400 s左右，EEUC和AD-LEACH網絡分別為420 s和430 s左右；LEACH、EEUC和AD-LEACH網絡中最后一個節點死亡時間分別為530 s、560 s和590 s左右。從FND的角度，AD-LEACH的性能比LEACH提升了7.5%，比EEUC提升了2.38%；從LND的角度，ADLEACH比LEACH和EEUC分別延長了11.32%和5.36%。

圖3 網絡存活節點數目與時間關系

圖4 網絡總能耗與時間關系

圖5 數據包發送總數與時間關系

圖4中，AD-LEACH的能耗曲線比LEACH和EEUC更為平滑，反映能耗速率比較穩定。對比圖3和圖4，第400～530 s時間段，AD-LEACH網絡的總能耗與另外兩種網絡的差異并不大，但是AD-LEACH網絡中存活節點數目明顯高于LEACH網絡和EEUC網絡，反映了AD-LEACH的節點能耗更加均勻，有效解決了LEACH中部分節點過早死亡，導致網絡性能下降的問題。

圖5反映AD-LEACH網絡的吞吐量也有了較大提高，比LEACH網絡提高了約62.5%，比EEUC網絡提高了約22.17%。

通過與LEACH、EEUC網絡性能的對比，體現了AD-LEACH協議在降低和均衡節點能耗、延長網絡壽命方面取得了較好的改進效果。

5 結束語

AD-LEACH協議目的在于降低和均衡網絡能耗，實現能耗最優，為此針對LEACH工作機制的不足做出了改進，包括：（1）分析了節點的特點并進行分類，從造成簇頭選取不合理的客觀原因出發，有針對性地進行閾值的修正。（2）通過節點位置信息，采用匹配方式將網絡分為相同大小的網格。（3）在最佳轉發距離附近的圓環區域尋找轉發的中間節點，兼顧了轉發節點的剩余能量和轉發效率。

仿真結果表明，改進后的協議有效延長了網絡生命周期，均衡了節點能耗，改進效果較為明顯，但是對基站所處位置對網絡性能的影響以及數據傳輸的開銷分析尚未探究，將作為下一步工作的重點。

[1]鄭軍，張寶賢.無線傳感器網絡技術[M].北京：機械工業出版社，2012.

[2]Heinzelman W R，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.[S.1.]：IEEE Computer Society，2000：3005-3014.

[3]Handy M，Haase M，Timmerrnann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proceedingsofthe 4th IEEE Conference on Mobile and Wireless Communications Networks.Washington，DC：IEEE Computer Society，2002：368-372.

[4]劉玉華，趙永峰，許凱華，等.無線傳感器網絡LEACH協議的改進[J].計算機工程與應用，2010，46（17）：117-120.

[5]樊志平，金政哲，謝冬青.基于能量效率的無線傳感器網絡分簇算法[J].小型微型計算機系統，2013，34（3）：535-539.

[6]唐甲東，蔡明.基于LEACH協議的能耗均衡路由算法[J].計算機工程，2013，39（7）：134-136.

[7]錢開國，戴祖誠，申時凱.非均勻分布的無線傳感器網絡分簇路由算法[J].計算機應用，2013，33（12）：3415-3418.

[8]馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術學報，2013，8（8）：1147-1151.

[9]石為人，柏蕩，高鵬，等.無線傳感器網絡簇頭半徑自適應調節路由算法[J].儀器儀表學報，2012，33（8）：1779-1785.

[10]蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇協議[J].軟件學報，2012，23（5）：1222-1232.

[11]肖婧，鄭更生，方勇，等.基于自組織神經網絡的分簇成鏈協議[J].計算機工程，2013，39（7）：148-151.

[12]張世偉，張海濤，張士杰.基于固定分簇和能量均衡的無線傳感器網絡多跳路由算法[J].傳感器與微系統，2013，32（8）：117-124.

[13]柏蕩，石為人，高鵬，等.無線傳感器網絡跳數優化非均衡路由算法[J].計算機工程與應用，2012，48（32）：60-64.

[14]湯玉，汪學明.一種分層路由協議的改進與仿真分析[J].通信技術，2013，46（4）：42-46.

[15]張瑞華，賈智平，程合友.基于非均勻分簇和最小能耗的無線傳感網絡路由算法[J].上海交通大學學報，2012，46（11）：1774-1778.

[16]郭書誠，盧昱，許定根.基于無線分簇無線傳感器網絡的路由算法研究[J].通信學報，2010，31（8）：63-69.

[17]王林，趙紹英.無線傳感器網絡LEACH路由協議的研究與改進[J].計算機工程與應用，2012，48（2）：80-82.

[18]Younis O，Fahmy S.HEED：a hybrid energy-efficient distributed clustering approach for Ad hoc sensornetworks[J].IEEE Transactions on Mobile Computing，2004，3（4）：600-669.

[19]唐加山，王燕.無線傳感器網絡中改進的EEUC協議[J].重慶郵電大學學報，2013，25（2）：172-177.

ZHOU Meng,CHEN Yuedong,CHEN Mengyuan

Anhui Key Laboratory of Electric Drive and Control,Anhui Polytechnic University,Wuhu,Anhui 241000,China

To overcome the shortage of electing of cluster head and data transmission method in LEACH protocol, AD-LEACH protocol is proposed after improving.Based on different categories of nodes,the probability of being cluster head is modified to balance the influence of energy consumption,distance and node density.WSN is divided into several grids sharing the same size through fuzzy matching node positions.During the course of data transmission,the relaying node is selected with optimum distance and the minimum energy and consumption.The simulation results show that AD-LEACH protocol balances the energy consumption of WSN effectively and achieves the purpose of the optimal energy consumption.

wireless sensor networks;Low Energy Adaptive Clustering Hierarchy（LEACH）protocol;electing of cluster head;fuzzy matching;grids;relaying node;optimal energy consumption

針對LEACH協議在簇頭選取、數據通信方面的不足，提出改進后的AD-LEACH協議。根據節點的分類，修正簇頭當選概率，使簇頭選取均衡了能耗、距離、節點密度的影響。通過節點位置模糊匹配的方法將全網劃分為若干個均勻大小的網格。數據傳輸階段以能量利用率最高為目的，基于最佳轉發距離選擇轉發節點。仿真結果表明，AD-LEACH協議有效降低和均衡了網絡能耗，達到了能耗最優的目的。

無線傳感器網絡；低功耗自適應集簇分層型（LEACH）協議；簇頭選取；模糊匹配；網格；轉發節點；能耗最優

A

TP393

10.3778/j.issn.1002-8331.1403-0134

ZHOU Meng,CHEN Yuedong,CHEN Mengyuan.Improvement of LEACH route protocol based on optimal energy consumption.Computer Engineering and Applications,2014,50（23）：82-86.

安徽省自然科學基金（No.11040606M153）；安徽高校省級自然科學研究項目（No.KJ2013A041）。

周萌（1990—），男，碩士在讀，研究領域為無線傳感器網絡；陳躍東（1956—），通訊作者，男，教授，碩導，研究領域為運動控制系統與檢測技術；陳孟元（1984—），男，講師，研究領域為無線傳感器網絡。E-mail：76920395@qq.com

2014-03-12

2014-04-29

1002-8331（2014）23-0082-05

CNKI網絡優先出版：2014-07-11,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0134.html