基于能耗均衡的LEACH－DC協議的設計

劉智珺，李臘元，，楊少華

（1.武漢生物工程學院 計算機與信息工程系，湖北 武漢430415；2.武漢理工大學 計算機科學與技術學院，湖北 武漢430063）

0 引 言

在無線傳感器網絡中，路由算法的性能在很大程度上決定了網絡的整體性能［1－2］。作為無線傳感器網絡核心技術之一，無線傳感器網絡研究的熱點LEACH協議是第一個基于多簇結構的層次型路由算法［3］，也是一種低功耗自適應聚類路由算法［4］。

由于LEACH協議是基于多簇結構的路由算法，在協議中引入了 “輪”的概念，在通信過程中，將通信過程劃分成輪，將簇的建立和信息的穩定通信作為每輪的兩個階段。為了降低網絡能耗，穩定通信階段時間一般比簇建立階段要長［5］。在傳感器網絡中，節點通過自組織方式生成簇，采用一定的方法隨機選擇網絡內某些節點擔任簇頭［6］。在簇頭的選擇策略上LEACH協議采取對所有節點進行隨機選取的方式即輪換思想，這樣很大程度的提高了節點能量使用效率。但是網絡節點的分布隨機、不均衡，因而無線傳感器網絡中的各簇內部節點的數量也不均衡，文獻通過的實驗結果正是證明了這一問題［7－8］，因此對于LEACH協議的能耗問題可以從這點上進行考慮。

基于LEACH協議的問題，LEACH－C［9］是在 LEACH協議的基礎的一個改進協議。協議采用中心控制的機制，在建立簇的時候，對于簇頭的選取由中心控制生成，通過此方法來形成簇，其簇內節點數量相對比較均衡。有了中心控制后簇頭和非簇頭節點的通信距離縮短了，從而降低了由簇內節點與簇頭節點相互通信而產生的能量消耗，來達到降低網路能耗的目的［10］。

在LEACH－C協議中，選擇簇頭由中心控制，基站對所有節點的物理地址以及能量相關信息必須十分清楚，這樣對于完全自組織網絡不適用，因此LEACH－C協議的應用有局限。以LEACH協議作為基礎，以非均勻分簇和雙簇頭路由作為改進思路，提出了新的降低網絡總能耗控制的LEACH－DC路由協議。

1 LEACH－DC路由協議的設計

雙簇頭傳送數據協議LEACH－DC （LEACH doublecluster）是以LEACH協議作為基礎進行改進得到的協議，基本改進思想是：在簇頭選擇時引入雙簇頭 （即簇頭與備選簇頭節點），在簇頭選擇時以控制能量作為出發點采取一定措施進行限制。對于簇頭節點的選擇采用周期選擇的方式，由于非均勻分簇，因而對簇內節點、成簇規模有一定的限定，但從整體的網絡能耗角度上達到了均衡的效果，相應的也就延長了整體網絡的生存時間，對于整個無線傳感器網絡的穩定起到較好的效果。LEACH－DC協議整個工作過程仍然使用了LEACH協議的分輪思想，對于每輪將其分成簇頭的選擇和簇的穩定兩個階段。由于采用雙簇頭思想，在簇頭選擇階段中增加備選簇頭。備選簇頭是當前簇頭的傳送數據的輔助節點，通過備選簇頭的引入減輕了簇頭傳遞數據的能耗，延長了簇的生存時間提高了傳送數據的效率。

1.1 簇頭節點的選擇

雙簇頭傳送協議LEACH－DC對于簇頭節點的選擇方式是：在傳感器網絡節點中，對簇頭的候選節點提出一定的能量要求，同時對整個網絡的成簇數量也作出調整，提出簇頭和備選簇頭的概念。

在每輪的簇的穩定階段，也就是傳遞數據階段，網絡節點向簇頭節點傳送最后一數據的同時將本節點目前的剩余能量的信息同步傳送。簇頭節點收到能量信息后計算出本簇的剩余能量的平均值。基站則由接收到的各簇平均能量值可計算得出這個無線傳感器網絡的平均剩余能量值。由sink廣播通知，在下一輪的簇頭選擇時，將把能量值作為選擇的參考依據，在能量超過平均能量值的節點中，對應每個節點隨機的生成一個介于0－1之間的數據，再增加一個閾值T （n），若某個節點的隨機數小于閾值，則將其選定為新的簇頭節點［11］。閥值T （n）計算公式如下

式中：p——無線傳感器網絡中簇頭所占的比例，r——選擇簇頭時網絡已經進行的輪數，G′——節點能量值不超過平均能量值的集合。使用上述方式選擇簇頭節點后，使用廣播的方式來通知網絡中的其它傳感器節點，節點在接受到消息以后可以根據接收信號的強弱程度判斷出與簇頭節點的距離，從而決定所屬簇。節點向簇頭節點通信確定選擇，簇頭節點確定本簇的節點后將會為其分配一個數據傳遞的時間點，為信息傳遞做準備［12］。

1.2 備選簇頭的選擇

LEACH－DC協議在簇頭選擇中，引入備選簇頭的概念，即當前簇頭傳送數據的輔助節點。

備選簇頭的選取方式是：確定簇頭節點后，在進行分簇的過程中，無線傳感器網絡節點使用廣播消息的方式向簇頭節點提出加入請求。在提出請求的同時，對于比平均能量值高的節點可以在發送請求消息的同時附加一個申請備選簇頭的信息。當簇頭節點接受信息后采用時間優先的策略確定當前簇內的備選簇頭，同時把備選簇頭的確定消息通知給簇內的傳感器網絡節點。

在備選簇頭的選取以及消息廣播的過程中，由于傳遞申請成為備選簇頭消息時需要消耗能量，所以對于網絡節點而言此部分的能耗比LEACH協議要大，但是簇內的消息傳遞信息量很小并且通信距離短，因此能耗不大。對于整個備選簇頭的方案而言存在額外消耗的這部分能量，在很大程度上可以避免由于個別簇頭節點過早耗盡自身能量而導致的簇穩定時間減少的情況，因此對于無線傳感器網絡，從整體上延長了通信的時間、增加了網絡的穩定。

1.3 傳感器網絡成簇規模的限定

1.3.1 傳感器網絡的最優成簇數

簇內節點個數關系著簇內節點的能量消耗。假設N為無線傳感器網絡中節點的總數目，若網絡內的節點是被隨機分布，限定其區域為矩形區域設定為M×M，為確定出最優成簇數，設定簇數為K。對于每個簇的簇頭節點，其能量消耗分為3個部分：接收簇內的各個網絡節點信息所消耗的能量、簇首節點自身進行信息融合所消耗的能量、簇頭首節點向基站傳送信息所消耗的能量。考慮到簇頭節點能耗衰減為多路衰減模型，因此在一個幀內簇頭節點能量消耗為

式中：l——每個消息的比特數，dtoBS——簇首節點至基站的距離。普通節點單位幀內只傳輸一次信息給簇首，假定將傳感器網絡分成K個簇，則單個簇的區域面積約為M2／K，同時假定在簇內簇頭節點處于中心點，則通過計算得到ρ（x，y）是網絡節點在簇內分布的概率密度。將設簇內節點是均勻分布，簇的作用區域是半徑為R的圓，則簇首節點與簇內普通節點間的距離平方期望為

由普通節點的能量消耗以及簇首節點與簇內普通節點間的距離平方期望公式推導可得在單位幀內每個簇的總能量消耗為

單位幀內網絡總能量消耗為

把E對k求一階導數，并令其等于0，可求出最優簇首數為

由公式能明顯看出，若優簇首數k的取值取決于基站與傳感器網絡節點之間的距離dtoBS。假設令傳感器網絡面積定為：100×100，同時節點的分布方式是均勻分布，為方便計算假定基站的位置是位于平面坐標 （50，175）處，通過計算可以得基站與傳感器網絡節點距離的取值范圍是：75—185，由式 （6）可得出網絡生成的最優簇數的范圍為1＜kopt＜6。因此在LEACH－DC協議中，為了網絡節點的能耗最優，在確定簇頭節點后建立簇的過程中，對網絡的簇內節點數目進行嚴格的限定，簇頭占傳感器網絡節點總數的5%時為最優。

1.3.2 簇內節點數目的限定

在進入簇的穩定階段之前，一旦確定了簇頭節點，傳感器網絡中的其它節點根據接受簇頭節點廣播時信號的強弱程度，自由選擇其加入的簇。簇內節點的數量需要進行相應的控制。對于同一個簇，當簇內節點數太多時，節點間接收數據的相關性會變差，降低數據的融合度。隨著簇頭節點需要轉發的信息量增多，相應地其能量消耗也會增多。在簇的穩定階段，進行信息傳遞時，若簇內節點較多，那么簇頭節點分配給簇內網絡節點傳送數據的時間段相應就會減少，隨之而來的簇的內部節點通信的數據量也相應減少，那么形成了簇頭節點能耗過大，而簇內節點能耗小的不平衡的情況。所以在最優成簇數確定的前提下，通過簇頭對簇內節點數目進行一定的限定。簇內節點的數目依據簇頭節點與基站的距離而進行靈活的調整，在與基站節點距離較遠的簇中限定其簇內節點數目少些，反之亦然。

2 LEACH－DC協議路由算法

確定了最優成簇數以及最優成簇的簇內節點個數后，簇的規模基本形成。以能量作為選擇標準確定簇頭節點以及選出備選節點后，網絡路由算法思想是將簇的通信分成階段：

在簇的穩定階段，無線傳感器網絡中的各個簇的簇內節點，在簇頭所分配的時間段內將其采集到的信息數據傳遞給簇頭節點，簇頭節點通過對所接收到的數據進行融合后再傳送給基站節點。在此傳遞數據的過程中，將先設定的簇頭節點最低能量閾值作為警戒線，若簇頭節點的能量下降到這一閾值，表示不適合繼續向基站發送數據，那么簇頭節點將未傳遞給的基站的數據傳送給備選簇頭節點。備選簇頭開始執行本簇內的簇頭任務，負責承擔數據傳送，以此減輕簇頭負擔，降低簇頭能耗。

在簇的穩定階段持續一段時間后，整個傳感器網絡將進行新一輪的簇頭節點的選擇以及簇的重構。重新選擇簇頭、重新構造簇、選擇備選簇頭，然后進入穩定階段實現信息傳遞，依此方式，不斷循環。路由算法的具體流程圖如圖1所示。

圖1 LEACH－DC協議路由算法描述

簇內節點向簇頭傳遞信息以及簇頭向基站傳遞信息時，采用不同的CDMA代碼，使用此方式可以降低本簇內通信對其它簇的影響。

3 LEACH－DC協議仿真及結果分析

NS2是一個的網絡環境仿真器，它采用的是面向對象、同時離散事件驅動的方式［13－14］，使用NS2可以完整的模擬整個無線傳感器網絡環境［15］。LEACH－DC協議在 NS2 2.27軟件平臺進行仿真實驗。

協議仿真的環境系數分別是：WSNs面積為100m×100m，節點數量100，傳感器網絡中各節點初始能量為2J。在正常工作過程中，無線傳感器網絡的節點平均每一次發送信息的時間為1.2s，為了保證無線傳感器網絡節點在試驗中的一段時間內能有信息發送，設置發送數據的時間間隔為15s，即△T＝15s；傳感器網絡內部數據冗余的范圍值為1.2；簇頭節點發送的數據包長度為L：500bit＋25bit，其具體的數據包內數據的格式如圖2所示。

圖2 數據包的格式

在仿真過程中，使用隨機生成區間 ［1，10］內的數據來模擬傳感器網絡節點所采集到的信息。節點隨機分布圖如圖3所示，在LEACH－DC協議的設計中由于簇頭節點的確定使用了雙簇頭的方式，并且通過分析計算得到最優成簇數，然后對簇內節點數量進行相應的限定，同時對簇頭節點采用了融合數據技術，降低了發送的數據量。

圖3 仿真實驗節點分布

圖4 是每輪節點能量總消耗。由于LEACH－DC協議通過分析節點的能耗，在一定程度上限定了成簇規模，那么簇內節點的位置，雖然是隨機分布但離sink節點遠的簇節點較少。因此，簇內節點傳送信息的能耗較小，圖4能顯示出每輪消耗能量LEACH－DC要低于LEACH，并且衰減情況較平穩。

圖4 每輪能量總消耗

圖5 比較了網絡總消耗能量與時間的關系，網絡仿真的能耗與時間比的分析圖，反饋出LEACH－DC協議消耗的總能量要低于LEACH協議。LEACH－DC協議通過分析節點能耗，一定程度上限定了成簇規模，那么簇內節點的位置，雖然是隨機分布但離sink節點遠的簇節點較少。因此，簇內節點傳送信息的能耗較小，每輪消耗能量要低于LEACH，并且衰減情況較平穩。

圖5 傳感器網絡的總體能耗

圖6 反饋的是網絡時間與發送的數據包總數據量之間的關系。由于LEACH－DC協議在簇頭選擇以及簇內節點數目反面做了均衡處理，延長了簇的生存時間，因此在簇的穩定階段網絡發送數據包的數目比改進前的協議要多。但是從總體看，LEACH－DC協議由于在網絡能耗方面進行了均衡，延長了整個網絡的生存時間，傳遞的信息量比LEACH協議多。

圖6 網絡發送的數據包總量與時間的關系

4 結束語

以均衡能量控制作為目的，以雙簇頭和非均勻分簇作為手段設計的LEACH－DC協議是對LEACH協議的一種改進方法。LEACH－DC算法將節點剩余能量考慮進來，采用了新的簇頭首選擇方法，對網絡成簇數目以及簇內節點數進行了一定的限制，采用雙簇頭通信預防機制。通過仿真實驗以及對結果的分析，驗證了改進后的路由協議從成簇優化方面、簇內網絡節點生存時間等方面都得到了較有效的改善，因而提高了網絡能耗的均衡性，達到延長網絡生命周期的目的。當然本協議對于簇頭擔任時間還沒有做到精確測算，在此方面還能進一步完善研究。

［1］SUN Liming，LI Jianzhong，CHEN Yu.Wireless sensor networks［M］.Beijing：Tsinghua University Press，2005：3－24（in Chinese）.［孫利民，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版社，2005：3－24.］

［2］GENG Xiaoyi，CHAI Qiaolin，ZHANG Qin.A kind of energy balance of wireless sensor network clustering algorithm ［J］.Computer Engineering and Application，2007，43 （33）：141－143（in Chinese）.［耿曉義，柴喬林，張擎.一種能量均衡的無線傳感器網絡分簇算法 ［J］.計算機工程與應用，2007，43（33）：141－143.］

［3］ZHENG Zengwei.Some wireless sensor network routing protocols in the comparative study［J］.Computer Engineering and Design，2003，24 （9）：28－31 （in Chinese）.［鄭增威，吳朝暉.若干無線傳感器網絡路由協議比較研究 ［J］.計算機工程與設計，2003，24 （9）：28－31.］

［4］SHENG Bo，ZHANG Shiyong.Wireless sensor network clumping routing protocol［J］.Journal of Software，2006，17 （7）：1588－1600（in Chinese）.［沈波，張世永.無線傳感器網絡分簇路由協議 ［J］.軟件學報，2006，17 （7）：1588－1600.］

［5］REN Biao，LIU Lifeng，MA Jiang.In wireless sensor networks improved algorithm of directional diffusion agreement［J］.Journal of Electronic and Information，2006，28 （3）：562－566 （in Chinese）.［任彪，柳立峰，馬建.無線傳感器網絡中定向擴散協議的改進算法 ［J］.電子與信息學報，2006，28 （3）：562－566.］

［6］GU Xiangpin，SUN Yanjing，QIAN Jiansheng.An improvement in wireless sensor network LEACH－ED algorithm ［J］.Sensing Technology Journal，2008，21 （10）：1770－1774 （in Chinese）.［顧相平，孫彥景，錢建生.一種改進的無線傳感器網絡 LEACH－ED算法 ［J］.傳感 技術學 報，2008，21（10）：1770－1774.］

［7］YANG Mian，QIN Qianqin.Based on wireless sensor network routing protocol［J］.Computer Engineering and Application，2004，40 （32）：130－132 （in Chinese）.［楊冕，秦前清.基于無線傳感器網絡的路由協議 ［J］.計算機工程與應用，2004，40 （32）：130－132.］

［8］ WANG Ying，XIONG Mudi.Monte carlo simulation of leach protocol for wireless sensor networks ［C］.Dalian：Proceedings of the Sixth International Conference on Parallel and Distributed Computing，2005：85－88.

［9］Muruganathan S D，MA DCF，Bhasin PI，et al，A centralized energy－efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43 （3）：8－13.

［10］JIANG Hua，YUAN Xiaobin，SHEN Jie.Channel access in wireless sensor networks clustering algorithm research ［J］.Computer Engineering and Application，2006，42 （7）：22－27（in Chinese）.［姜華，袁曉兵，沈杰，等.無線傳感器網絡中信道接入分簇算法的研究 ［J］.計算機工程與應用，2006，42 （7）：22－27.］

［11］ZHAN Qiang，LIN Yaping.Based on grid clumps and routing algorithm ［J］.Zhongnan University of Forestry Science and Technology，2010，30 （4）：166－169 （in Chinese）.［占強，林亞平.一種基于網格的分簇路由算法 ［J］.中南林業科技大學學報，2010，30 （4）：166－169.］

［12］SUN Yugeng，ZHOU Yin，BIAN Guinian，et al.Wireless sensor network of an energy efficient clustering networking algorithm ［J］.Sensing Technology Journal，2007，20 （2）：377－381（in Chinese）.［孫雨耕，周寅，邊桂年，等.無線傳感器網絡中一種能量有效的分簇組網算法 ［J］.傳感技術學報，2007，20 （2）：377－381.］

［13］JI Yingying，ZHANG Jianwu.Based on cluster of wireless sensor network routing protocol improvement plan ［J］.Sensing Technology Journal，2008，21 （6）：1052－1054 （in Chinese）.［季瑩瑩，章堅武.基于簇的無線傳感器網絡路由協議改進方案［J］.傳感技術學報，2008，21 （6）：1052－1054.］

［14］TAO Xiaolin，WANG Guifeng，WANG Yong.Based on the wireless sensor network Dijkstra clumps and routing algorithms［J］.Computer Engineering and Design，2010，31 （17）：3807－3811（in Chinese）.［陶曉玲，王桂鳳，王勇.基于Dijkstra的無線傳感器網絡分簇路由算法 ［J］.計算機工程與設計，2010，31 （17）：3807－3811.］

［15］YU Lijuan，LI Simin.Wireless sensor network of LEACH improved algorithm design and simulation［J］.Optical Communication Research，2008，32 （5）：67－70 （in Chinese）.［于立娟，李思敏.無線傳感器網絡LEACH改進算法的設計與仿真 ［J］.光通信研究，2008，32 （5）：67－70.］