基于LEACH的傳感器網絡分簇路由協議

張 然，覃少華

（廣西師范大學 計算機科學與信息工程學院，廣西 桂林541004）

0 引 言

低功耗自適應聚類路由協議 （low energy adaptive clustering hierarchy，LEACH）是無線傳感器網絡中一種經典的分層路由協議，其算法通過循環隨機地選舉簇首節點來提高網絡的能量利用率和延長系統的生命周期。相對于一般的平面靜態路由協議，LEACH可以將網絡生存時間延長近15%。然而，LEACH協議在進行簇首選擇時采用各節點等概率隨機成為簇首的選取方式，沒有考慮到節點的剩余能量等因素，可能導致所選的簇首不是最優，從而影響到整個無線傳感器網絡的存活時間。

針對LEACH協議在簇首選擇策略上存在的不足，文獻 ［1－3］中通過引入節點的能量因素，提高具有較多剩余能量的節點成為簇首的可能性對其進行優化，但尚未考慮到系統每輪的總能量和平均能量。由此，本文提出了一種簇首優化的改進算法——LEACH－TE。該算法在重新計算最優簇首數的基礎上，結合節點的剩余能量、每輪網絡的總能量和平均能量來優化簇首的選取。這些措施有效地提高了節點的能量利用率、均衡了網絡的能耗負載和延長了系統的生命周期。

1 LEACH協議

LEACH協議的工作過程被劃分為周期性的 “輪”，每輪包括成簇和數據傳輸兩個階段。在成簇階段，節點間首先按照一定的策略進行簇首選舉；待簇首節點確定后，將向全網廣播自己本輪擔任簇首的消息，其他節點根據接收到的廣播信號的強度來決定本輪所要加入的簇，并發送加入請求消息給相應的簇首；最后，簇首節點接收加入請求消息并創建TDMA和CDMA編碼機制。在數據傳輸階段，簇首節點首先接收簇內成員節點采集的監測數據，然后對其和自身數據進行融合處理，最終將融合后的數據發送給基站。

簇首的選舉是LEACH算法的核心組成部分，在整個LEACH協議中扮演著極為重要的角色，其具體的選擇策略描述如下：在成簇階段，各節點產生一個 ［0，1］之間的隨機數，若該數小于某一個閾值T（n），則向全網通告自己本輪擔任簇首的消息；若節點之前已經擔任過簇首，則將閾值T（n）設置為0，表明本輪自己不再會擔任簇首；反之，若節點之前未曾擔任過簇首，則在本輪中以閾值T（n）為概率競選簇首；當網絡中只剩下一個節點未擔任過簇首時，該節點將把閾值T（n）設置為1，表明自己本輪無條件地成為簇首。T（n）的計算公式如下

式中：P——簇首節點占所有節點百分比的期望值；r——當前輪數；G——最近的1／P輪中未擔任過簇首節點的節點集。

根據LEACH協議使用的無線能量損耗模型，傳感器節點在距離d上傳輸l比特數據，其發送和接收能耗分別為

式 中：Eelec——發送和接收電路的能量損耗；εfriss－amp、εtwo－ray－amp——自由空間模型和多路徑衰減模型中的功率放大損耗；dcrossover——距離閾值，文中為87m。當傳輸距離小于距離閾值時采用自由空間模型計算能耗，反之則采用多路徑衰減模型計算能耗。

2 LEACH－TE協議

2.1 LEACH協議簇首選擇時存在的問題

LEACH協議每輪的簇首選擇過程完全依賴于各節點產生的隨機數，沒有考慮節點的剩余能量。節點無論能量多少，擔任簇首的概率都大致相同。這樣可能導致剩余能量較低的節點仍被選為簇首，從而很快被耗盡失效。這不但不利于整個系統生存時間的延長，而且由于簇首節點的失效而導致整個聚類無法通信，也不利于網絡的健壯性。

2.2 LEACH－TE協議

本文基于原有的LEACH協議提出一種改進協議——LEACH－TE。首先根據節點的剩余能量和網絡的平均能量，篩選出剩余能量大于或等于網絡平均能量的節點，再通過調整簇首閾值T（n）的計算公式，提高已篩選出的節點里面剩余能量較大者成為簇首的概率，從而更有效地均衡各節點的能耗負載，進一步延長系統的生命周期。

2.2.1 新的最優簇首數計算公式

LEACH協議中給出了最優簇首數的計算公式，并根據仿真實驗推導出當最優簇首數Kopt＝5（即P＝5%）時，平均每輪的能耗最小。但在具體的應用中，最優簇首數應根據被監測區域的面積、傳感器節點的數目及基站的位置等因素來確定。

設A是一個邊長為M的正方形監測區域，N是A中規則分布的傳感器節點數目。文獻 ［4］中指出傳感器節點與基站的距離期望為

這個距離期望主要取決于基站的位置坐標 （x＊，y＊）。

假設有K個簇，則平均每個簇中有N／K個傳感器節點：一個簇首節點和 （N／K）－1個簇成員節點。簇首節點的能耗由3部分組成，分別為接收簇成員節點數據的能耗、融合處理的能耗以及將融合后的數據發送給基站的能耗?？紤]到基站和簇首節點之間的距離通常較遠 （大于距離閾值dcrossover），故采用多路徑衰減模型來計算能量消耗。

在一個數據幀的傳送過程中，簇首節點消耗的能量為

式中：l——每個數據消息的比特數，EDA——進行數據融合處理所消耗的能量，dtoBS——簇首節點到基站的距離。

設RCH為每個簇所占的面積，由上述可知其值約等于M2／K。設ρ（x，y）是每個簇中傳感器節點的分布密度，其值為K／M2。E［dtoCH］是簇成員節點到簇首節點的距離期望，由文獻 ［4］可得

這里假設RCH是一個圓形區域，由上述可知其半徑R＝令x＝rcosθ，y＝rsinθ，代入式 （6），得到簇成員節點到簇首節點的距離期望為

在傳送每一幀數據時，簇成員節點只需將自己的監測數據發送給簇首節點?？紤]到簇成員節點和簇首節點之間的距離通常較近 （小于距離閾值dcrossover），故采用自由空間模型來計算能量消耗。因此，簇成員節點發送l比特數據到簇首節點所消耗的能量為

由上述可知，在每一幀數據的傳送過程中，單個簇內消耗的能量Ecluster由簇首節點的能耗ECH和簇成員節點的能耗Enon－CH兩部分組成，即

因此，每一輪循環中整個網絡所消耗的總能量Etotal為

將Etotal對K求一階導數，并令其等于零，得到新的最優簇首數Kopt的計算公式

2.2.2 LEACH－TE簇首選擇策略的改進

步驟1 在進行簇首選擇前，每個節點的剩余能量記為Eres。Etotal是網絡中節點ID從0到N－1的節點的剩余能量之和 （N為網絡中存活節點數目）。在每一輪的初始階段，基站計算全網的平均能量，得到Eavg＝Etotal／N（當網絡中有節點死亡時，為其近似值）。只有剩余能量大于或等于平均能量的節點才有資格成為簇首，即

步驟2 在步驟1的基礎上，為在剩余能量大于或等于平均能量的節點中選擇剩余能量較大的節點成為簇首，將節點的剩余能量和網絡的總能量等因素考慮進來，調整了簇首閾值T（n）的計算公式

式中：Eres——節點的剩余能量，Etotal——網絡的總能量（當網絡中有節點死亡時，為其近似值），Kopt——最優簇首數。當Etotal＞0時，各節點采用式 （15）中的簇首閾值計算公式；當Etotal＝0時，各節點采用式 （1）中的簇首閾值計算公式。式 （15）可使剩余能量較大的節點具有更高的簇首閾值，從而提高其成為簇首的概率，能有效地改善網絡的健壯性，使得簇首的選擇更為合理。

3 仿真實驗

3.1 仿真場景及參數

本文基于NS2平臺對LEACH和LEACH－TE協議進行仿真實驗?？疾?00個節點隨機分布在100m×100m區域中的傳感器網絡?；疚挥?（50，140），由式 （4）可得E［dtoBS］＝94.86m。當N＝100時，根據式 （13）得到最優簇首數Kopt＝6。所有節點具有相同的初始能量2J。發送和接收電路能耗Eelec＝50nJ／bit，εfriss－amp和εtwo－ray－amp分 別 為10pJ／bit／m2、0.0013pJ／bit／m4。其他參數與文獻 ［5］相同。

3.2 仿真結果及分析

本文網絡仿真性能評價指標包括網絡生存時間、能量消耗和基站接收的數據量3個方面。其中，在網絡生存時間的評價標準中，引入文獻 ［1］中的3種評價方法：First Node Dies（FND），即第一個節點死亡；Half of the Nodes Alive（HNA），即一半節點存活；Last Node Dies（LND），即最后一個節點死亡。

圖1顯示的是原有的LEACH協議和改進后的LEACH－TE協議網絡中存活節點數隨運行時間變化的曲線。LEACH協議第一個節點死亡的時間為410輪，而LEACH－TE協議第一個節點死亡的時間為510輪，比LEACH協議提高了約25%；LEACH－TE協議一半節點死亡的時間比LEACH協議提高了約45%，最后一個節點死亡的時間比LEACH協議也提高了約45%，見表1的統計數據。這表明LEACH－TE協議能更有效地均衡網絡的能耗負載，進一步延長系統的生命周期。

圖1 網絡存活節點數隨運行時間變化關系

表1 兩種協議的存活節點數統計

圖2顯示的是原有的LEACH協議和改進后的LEACH－TE協議網絡能耗隨運行時間變化的曲線。LEACH協議在第200輪前消耗的能量為85.98J，而LEACH－TE協議此時的能耗僅為58.81J，在這一階段相對LEACH協議能耗降低了約46.20%。在第300輪，400輪前LEACH－TE的能耗也比LEACH分別降低了約25.83%，21.09%，見表2的統計數據。由此可見，在相同的時間里，LEACH－TE協議的能耗比LEACH協議要低，具有更高的能量利用率。

圖3顯示的是原有的LEACH協議和改進后的LEACH－TE協議基站接收的數據量隨運行時間變化的曲線。LEACH協議在第一個節點死亡時基站接收的數據量為0.891002×106bit，而LEACH－TE協議此時基站接收的數據量為1.28864×106bit，在這一階段相對LEACH協議基站接收的數據量增加了約44.63%。在一半節點死亡和全部節點死亡時LEACH－TE協議基站接收的數據量也比LEACH協議分別增加了約83.11%和79.01%，見表3的統計數據。由此可見，LEACH－TE協議在相應的時間段內要比LEACH協議轉發到基站的數據量大。

圖2 網絡能耗隨運行時間變化關系

表2 兩種協議的網絡能耗統計

圖3 基站接收的數據量隨運行時間變化關系

表3 兩種協議基站接收的數據量統計

4 結束語

本文針對LEACH協議簇首選擇策略的不足，提出了一種改進協議LEACH－TE。該協議在重新計算最優簇首數的基礎上，通過綜合考慮節點的剩余能量和網絡的平均能量等因素來優化簇首的選擇。仿真結果表明，改進后的協議在網絡生存時間、能量利用率和基站接收的數據量3個方面相對于LEACH協議都有較大的提高。在今后的工作中，可以考慮從簇首節點到基站的距離以及簇成員節點到簇首的距離方面對算法進行改進，使得簇首的選擇更為合理；也可以考慮對整個傳感器網絡進行區域劃分，在每個區域內部進行簇首的選擇和數據的傳輸，以保證每輪形成的簇的數目和簇內節點數都大致相同，進一步延長系統的生命周期。

［1］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster－head selection［C］.Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks. Stockholm，Sweden：IEEE Communications Society，2002：368－372.

［2］YUE Shicheng，WANG Peikang.Energy efficient routing algorithm for wireless sensor networks ［J］.Computer Engineering，2008，34 （7）：113－117 （in Chinese）. ［樂世成，王培康.無線傳感器網絡中的節能路由算法 ［J］.計算機工程，2008，34（7）：113－117.］

［3］CHEN Xuejiao，LI Xiangyang.Research and improvement of LEACH protocol in wireless sensor networks［J］.Journal of Computer Applications，2009，29 （12）：3241－3243 （in Chinese）.［陳雪嬌，李向陽.WSN中LEACH協議的研究及改進 ［J］.計算機應用，2009，29 （12）：3241－3243.］

［4］Edward J.An energy efficient hierarchical clustering algorithm for wireless sensor networks ［C］.Proceedings of the IEEE Wireless Communications and Networking Conference.New Orleans，LA，USA：IEEE，2003：1713－1723.

［5］Heinzelman W B，Chandrakasan A P，Balakrishnan H.Application－specific protocol architectures for wireless networks ［J］.IEEE Transactions on Wireless Communication，2002，1 （4）：660－670.

［6］LI Zhenke，CHEN Guoding，WANG Shuhua.Improved routing algorithm based on LEACH ［J］.Journal of Computer Applications，2009，29 （z2）：63－65 （in Chinese）.［李振科，陳國定，王淑華.基于LEACH協議的改進路由算法 ［J］.計算機應用，2009，29 （z2）：63－65.］

［7］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks：Communication clustering and aggregation ［J］.Ad Hoc Networks，2007，2 （1）：45－63.

［8］FAN Xiangning，SONG Yulin.Improvement on LEACH protocol of wireless sensor network ［C］.International Conference on Sensor Technologies and Applications.Washington，DC，USA：IEEE Computer Society，2007：260－264.

［9］SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless sensor network［M］.Beijing：Tsinghua University Press，2005 （in Chinese）. ［孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.］

［10］WANG Shu，YAN Yujie，HU Fuping，et al.The theory and applications of wireless sensor network ［M］.Beijing：Beihang University Press，2007 （in Chinese）.［王殊，閻毓杰，胡富平，等.無線傳感器網絡的理論及應用 ［M］.北京：北京航空航天大學出版社，2007.］

［11］SONG Wen，WANG Bing，ZHOU Yingbin，et al.The technology and applications of wireless sensor network ［M］.Beijing：Publishing House of Electronics Industry，2007 （in Chinese）.［宋文，王兵，周應賓，等.無線傳感器網絡技術與應用 ［M］.北京：電子工業出版社，2007.］

［12］YE M，LI C F，CHEN G H，et al.An energy efficient clustering scheme in wireless sensor networks ［J］.International Journal of Ad Hoc ＆ Sensor Wireless Networks，2007，3（2）：99－119.

［13］WANG Shengrong.The research and improvement of leach routing protocol in wireless sensor networks ［D］.Jinan：Shandong University Master’s Thesis，2008 （in Chinese）.［王聲榮.無線傳感器網絡LEACH協議的研究與改進 ［D］.濟南：山東大學碩士學位論文，2008.］

［14］LATIFF NMA，TSIMENIDIS C C，SHARIF B S.Energyaware clustering for wireless sensor networks using particle swarm optimization［C］.IEEE 18th International Symposium，2007：1－5.

［15］CHANG Ruayshiung，KUO Chiajou.An energy efficient routing mechanism for wireless sensor networks［C］.Proceedings of the 20th International Conference on Advanced Information Networking and Applications.Hualien，Taiwan：IEEE Computer Society，2006.