張 然，覃少華

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

0 引 言

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

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

1 LEACH協(xié)議

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

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

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

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

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

2 LEACH－TE協(xié)議

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

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

2.2 LEACH－TE協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 LEACH－TE簇首選擇策略的改進(jìn)

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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