張 然，覃少華

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

0 引 言

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

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

1 LEACH協(xié)議

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

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

式中：P——簇首節(jié)點占所有節(jié)點百分比的期望值；r——當(dāng)前輪數(shù)；G——最近的1／P輪中未擔(dān)任過簇首節(jié)點的節(jié)點集。

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

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

2 LEACH－TE協(xié)議

2.1 LEACH協(xié)議簇首選擇時存在的問題

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

2.2 LEACH－TE協(xié)議

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

2.2.1 新的最優(yōu)簇首數(shù)計算公式

LEACH協(xié)議中給出了最優(yōu)簇首數(shù)的計算公式，并根據(jù)仿真實驗推導(dǎo)出當(dāng)最優(yōu)簇首數(shù)Kopt＝5（即P＝5%）時，平均每輪的能耗最小。但在具體的應(yīng)用中，最優(yōu)簇首數(shù)應(yīng)根據(jù)被監(jiān)測區(qū)域的面積、傳感器節(jié)點的數(shù)目及基站的位置等因素來確定。

設(shè)A是一個邊長為M的正方形監(jiān)測區(qū)域，N是A中規(guī)則分布的傳感器節(jié)點數(shù)目。文獻 ［4］中指出傳感器節(jié)點與基站的距離期望為

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

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

在一個數(shù)據(jù)幀的傳送過程中，簇首節(jié)點消耗的能量為

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

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

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

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

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

因此，每一輪循環(huán)中整個網(wǎng)絡(luò)所消耗的總能量Etotal為

將Etotal對K求一階導(dǎo)數(shù)，并令其等于零，得到新的最優(yōu)簇首數(shù)Kopt的計算公式

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

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

步驟2 在步驟1的基礎(chǔ)上，為在剩余能量大于或等于平均能量的節(jié)點中選擇剩余能量較大的節(jié)點成為簇首，將節(jié)點的剩余能量和網(wǎng)絡(luò)的總能量等因素考慮進來，調(diào)整了簇首閾值T（n）的計算公式

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

3 仿真實驗

3.1 仿真場景及參數(shù)

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

3.2 仿真結(jié)果及分析

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

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

圖1 網(wǎng)絡(luò)存活節(jié)點數(shù)隨運行時間變化關(guān)系

表1 兩種協(xié)議的存活節(jié)點數(shù)統(tǒng)計

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

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

圖2 網(wǎng)絡(luò)能耗隨運行時間變化關(guān)系

表2 兩種協(xié)議的網(wǎng)絡(luò)能耗統(tǒng)計

圖3 基站接收的數(shù)據(jù)量隨運行時間變化關(guān)系

表3 兩種協(xié)議基站接收的數(shù)據(jù)量統(tǒng)計

4 結(jié)束語

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

［1］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster－h(huán)ead 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）. ［樂世成，王培康.無線傳感器網(wǎng)絡(luò)中的節(jié)能路由算法 ［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協(xié)議的研究及改進 ［J］.計算機應(yīng)用，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協(xié)議的改進路由算法 ［J］.計算機應(yīng)用，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）. ［孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，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）.［王殊，閻毓杰，胡富平，等.無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用 ［M］.北京：北京航空航天大學(xué)出版社，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）.［宋文，王兵，周應(yīng)賓，等.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用 ［M］.北京：電子工業(yè)出版社，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）.［王聲榮.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究與改進 ［D］.濟南：山東大學(xué)碩士學(xué)位論文，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.