摘  要： 無(wú)線傳感器網(wǎng)絡(luò)由大量能量有限的傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)一般都是靠電池供電。如何在這種情況下，盡量延長(zhǎng)網(wǎng)絡(luò)的生存周期是研究的熱點(diǎn)問(wèn)題?；诜执氐臒o(wú)線傳感器網(wǎng)絡(luò)路由算法不論是在網(wǎng)路生存周期方面，還是在數(shù)據(jù)融合方面都比自組織算法表現(xiàn)出了很大的優(yōu)勢(shì)。文中提出了一種基于能量和距離的ED-LEACH(Energy and Distance-LEACH)改進(jìn)算法，在簇頭的選舉和簇的生成兩個(gè)階段都綜合考慮了能量和距離這兩個(gè)因素。仿真表明該算法較LEACH算法顯著地延長(zhǎng)了網(wǎng)絡(luò)的生存期。
　

　關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)；ED-LEACH；分簇；能量；距離

     隨著微機(jī)電系統(tǒng)、無(wú)線通信等技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)在軍事國(guó)防、醫(yī)療衛(wèi)生、工農(nóng)業(yè)控制、空間和海洋資源勘探等諸多領(lǐng)域發(fā)揮了越來(lái)越重要的作用。無(wú)線傳感器網(wǎng)絡(luò)由大量靠電池供電的傳感器節(jié)點(diǎn)組成，由于電池不能更換，因此對(duì)該種網(wǎng)絡(luò)協(xié)議及傳輸機(jī)制的研究中，均衡網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的能量消耗成為延長(zhǎng)網(wǎng)絡(luò)生命周期的關(guān)鍵因素。LEACH(Low Energy Adaptive Clustering Hierachy)算法是一種可以隨機(jī)選擇簇頭，動(dòng)態(tài)成簇的能耗低、載荷均衡且易于實(shí)現(xiàn)的算法。
　　盡管如此，LEACH算法還是存在很多需要改進(jìn)的地方。本文基于對(duì)能量、距離兩方面的綜合考慮，提出了一種改進(jìn)的ED-LEACH算法。仿真表明該算法減少了傳感器節(jié)點(diǎn)的能量消耗，均衡了網(wǎng)絡(luò)負(fù)載，從而延長(zhǎng)了網(wǎng)絡(luò)的生命周期。
1 LEACH算法
　　Heinzelman等提出的LEACH^[1]算法是無(wú)線傳感器網(wǎng)絡(luò)成簇的經(jīng)典算法。算法中引入了“輪”的概念，每一輪由初始化和穩(wěn)定工作兩個(gè)階段組成。其中，初始化階段又可以分為簇頭選舉和成簇兩個(gè)階段。在選舉簇頭時(shí)，節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果該隨機(jī)數(shù)小于閾值T(n)，則廣播自己是簇頭的消息。T(n)可表示為：
　　
　　其中，p是簇頭數(shù)量的百分比，r是選舉的輪數(shù)，r mod(1/p)代表這一輪循環(huán)中當(dāng)選過(guò)簇頭的節(jié)點(diǎn)個(gè)數(shù)，G是這一輪循環(huán)中未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。成簇階段，接收到簇頭廣播消息的非簇頭節(jié)點(diǎn)根據(jù)所收到的信號(hào)的強(qiáng)弱加入就近的簇。在穩(wěn)定階段，簇頭節(jié)點(diǎn)將接收到的該簇成員節(jié)點(diǎn)的數(shù)據(jù)融合并發(fā)送給基站。
　　雖然LEACH算法比較容易實(shí)現(xiàn)，也初步解決了負(fù)載平衡的問(wèn)題，但是還有很多值得改進(jìn)的地方。簇頭選舉時(shí)，各節(jié)點(diǎn)隨機(jī)自行決定是否成為簇頭，導(dǎo)致簇頭的位置和簇內(nèi)包含的節(jié)點(diǎn)個(gè)數(shù)很不均勻，并且也沒(méi)有考慮到節(jié)點(diǎn)的剩余能量。在成簇階段，非簇頭節(jié)點(diǎn)采用就近原則，加入離自己最近的簇頭，也沒(méi)有考慮到簇頭的剩余能量。本文基于對(duì)能量和距離的綜合考慮，對(duì)初始化階段的簇頭選舉和成簇兩個(gè)子階段進(jìn)行改進(jìn)。
2 改進(jìn)的算法
2.1 網(wǎng)絡(luò)模型
　　由N個(gè)隨機(jī)部署的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)，其方形監(jiān)測(cè)區(qū)域的大小為M×M。對(duì)網(wǎng)絡(luò)作如下假設(shè)：
    (1)網(wǎng)絡(luò)中的節(jié)點(diǎn)是靜止的，且初始能量相同，并且有唯一的ID號(hào)，且節(jié)點(diǎn)的坐標(biāo)由定位算法可得，并且已知。
    (2)基站處于固定的位置，并可以認(rèn)為其能量是無(wú)限的(不靠電池供電)。
    (3)根據(jù)通信距離的遠(yuǎn)近，節(jié)點(diǎn)的發(fā)射功率動(dòng)態(tài)可調(diào)。節(jié)點(diǎn)間的通信鏈路可靠且雙向連通。
2.2 無(wú)線電能耗模型^[2]
　　傳感器節(jié)點(diǎn)的能量主要消耗在無(wú)線傳輸?shù)倪^(guò)程中，而且隨著通信距離的增加，節(jié)點(diǎn)能耗呈指數(shù)增長(zhǎng)。發(fā)送和接收1 bit數(shù)據(jù)且傳輸距離為d，節(jié)點(diǎn)消耗的能量分別為:
　　

其中：d_toBS為節(jié)點(diǎn)到基站的平均距離；E_DA為簇頭執(zhí)行數(shù)據(jù)融合的功耗；k為簇頭節(jié)點(diǎn)數(shù)目。
　　定義E_i和E_i(r)分別為傳感器節(jié)點(diǎn)的初始能量和在第r輪簇頭選舉時(shí)的剩余能量，E_total(r)為網(wǎng)絡(luò)當(dāng)前的總能量，則有:
　　
2.3 簇頭的選舉
　　從LEACH協(xié)議可知，簇頭節(jié)點(diǎn)的數(shù)目對(duì)網(wǎng)絡(luò)的生存期有一定的影響。若簇頭節(jié)點(diǎn)過(guò)少，那么一個(gè)簇所覆蓋的區(qū)域會(huì)過(guò)大，成員節(jié)點(diǎn)到簇頭的距離會(huì)較遠(yuǎn)，傳輸數(shù)據(jù)能耗會(huì)很大；若簇頭數(shù)目過(guò)多，由于簇頭節(jié)點(diǎn)的能耗遠(yuǎn)大于非簇頭節(jié)點(diǎn)，會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)在每輪路由中總的能耗增大，并且還會(huì)導(dǎo)致數(shù)據(jù)融合^[2]效率降低，產(chǎn)生過(guò)多不必要的數(shù)據(jù)融合。
　　通過(guò)選舉產(chǎn)生的最優(yōu)簇頭節(jié)點(diǎn)數(shù)，應(yīng)使網(wǎng)絡(luò)在每一輪的簇重構(gòu)中消耗能量最小^[3]，即使式(4)中E_round達(dá)到極小值的k值點(diǎn)。由(4)式可知，在其他網(wǎng)絡(luò)參數(shù)設(shè)定的前提下，當(dāng)k>0時(shí)Eround是關(guān)于k的連續(xù)函數(shù)。

　　根據(jù)極值定理可得k₀為最小值。k₀由計(jì)算能力很強(qiáng)的基站完成，并且每經(jīng)過(guò)事先設(shè)定的若干個(gè)周期重新計(jì)算一次，因?yàn)橥ㄐ胖袑⒉粩嘤泄?jié)點(diǎn)因能量耗盡而死亡。
　　本文在簇頭選舉時(shí)綜合考慮能量和距離兩個(gè)因素，為每個(gè)節(jié)點(diǎn)分配一個(gè)權(quán)值表示其適合充當(dāng)簇頭的程度。某個(gè)節(jié)點(diǎn)i在第r輪簇頭選舉中的競(jìng)選權(quán)值為：

　　由于ED-LEACH算法在簇頭選舉階段需要知道當(dāng)前網(wǎng)絡(luò)的平均剩余能量，采用的方法是簇內(nèi)節(jié)點(diǎn)將自身剩余能量信息嵌入每輪最后要發(fā)送的數(shù)據(jù)分組中，捎帶給簇頭；簇頭對(duì)簇內(nèi)剩余能量進(jìn)行匯總，并隨同融合后的數(shù)據(jù)信息發(fā)送給基站；最終由基站完成網(wǎng)絡(luò)平均剩余能量的計(jì)算，并嵌入在新一輪的簇重構(gòu)命令中，廣播至所有節(jié)點(diǎn)。由此，在沒(méi)有引入額外分組交換的條件下，完成了對(duì)網(wǎng)絡(luò)平均剩余能量的計(jì)算^[4]。
    在初始化階段，基站廣播競(jìng)選簇頭開(kāi)始消息，該消息包含當(dāng)前網(wǎng)絡(luò)的平均剩余能量。節(jié)點(diǎn)首先判斷自身剩余能量是否大于當(dāng)前網(wǎng)絡(luò)的平均剩余能量，若小于則直接放棄競(jìng)選，并在接下來(lái)的時(shí)間內(nèi)加入某一簇；若大于則向基站發(fā)送競(jìng)選簇頭消息，該消息包括本節(jié)點(diǎn)的ID和剩余能量等信息?；臼盏剿袇⒓痈?jìng)選節(jié)點(diǎn)發(fā)送的競(jìng)選簇頭消息后，根據(jù)(8)式確定的競(jìng)選權(quán)值選擇最大的k0個(gè)節(jié)點(diǎn)作為簇頭，并廣播任命簇頭消息，該消息包括選出的k0個(gè)簇頭節(jié)點(diǎn)的ID。接收到此消息的節(jié)點(diǎn)如果發(fā)現(xiàn)任命的簇頭中有自己，就當(dāng)選為簇頭。
2.4 簇的形成
　　在LEACH算法中，當(dāng)非簇頭節(jié)點(diǎn)收到多個(gè)簇頭的廣播消息后，僅考慮距離因素，加入離自己距離最近的簇。但是其并沒(méi)有考慮簇頭的當(dāng)前的剩余能量，即使離自己稍微遠(yuǎn)一點(diǎn)的簇頭當(dāng)前剩余能量很多時(shí)，該節(jié)點(diǎn)也不會(huì)選擇加入該簇，而會(huì)選擇加入離自己最近的簇。這樣就會(huì)造成網(wǎng)絡(luò)的負(fù)載很不平衡，不利于延長(zhǎng)網(wǎng)絡(luò)的生命周期。
　　本文在非簇頭節(jié)點(diǎn)加入簇時(shí)，綜合考慮了簇頭的當(dāng)前剩余能量和到該簇頭的距離兩個(gè)因素。假設(shè)某個(gè)非簇頭節(jié)點(diǎn)收到了n個(gè)簇頭的廣播消息，該消息包括簇頭的ID和當(dāng)前的剩余能量。定義選擇加入簇的權(quán)值為：
　　　　

　　其中：E_i(r)為第i個(gè)簇頭的當(dāng)前剩余能量，E_i為第i個(gè)簇頭的初始能量；d_i為該非簇頭節(jié)點(diǎn)到第i個(gè)簇頭的距離；d_max為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間的最遠(yuǎn)距離；α為加權(quán)系數(shù)，可以根據(jù)實(shí)際需要?jiǎng)討B(tài)調(diào)節(jié)能量和距離所占的比重。
    由(9)式可得非簇頭節(jié)點(diǎn)會(huì)綜合考慮能量和距離兩個(gè)因素，選擇當(dāng)前剩余能量多且距離近的簇頭加入，即使W取得最大值的簇頭。接下來(lái)非簇頭節(jié)點(diǎn)向選定的簇頭節(jié)點(diǎn)發(fā)送請(qǐng)求加入簇的消息，該消息包括本節(jié)點(diǎn)的ID和簇頭節(jié)點(diǎn)的ID。簇頭節(jié)點(diǎn)收到各成員節(jié)點(diǎn)的請(qǐng)求信息后，為成員建立TDMA時(shí)隙表，并把該時(shí)隙表發(fā)送給其成員節(jié)點(diǎn)。在簇內(nèi)所有成員收到TDMA時(shí)隙表后，建立簇階段完成，開(kāi)始進(jìn)入穩(wěn)定階段，各成員節(jié)點(diǎn)在分配的時(shí)間槽內(nèi)向簇頭發(fā)送數(shù)據(jù)，簇頭節(jié)點(diǎn)融合各成員節(jié)點(diǎn)的數(shù)據(jù)后，發(fā)送到基站。
3 仿真實(shí)驗(yàn)
    利用Matlab和C++對(duì)本文提出的ED-LEACH算法和LEACH算法進(jìn)行仿真比較。我們對(duì)第1個(gè)節(jié)點(diǎn)死亡，10個(gè)、20個(gè)、30個(gè)、40個(gè)、50個(gè)、60個(gè)、70個(gè)、80個(gè)、90個(gè)、全部節(jié)點(diǎn)死亡的輪數(shù)進(jìn)行比較。
　　在100 m×100 m的網(wǎng)絡(luò)中隨機(jī)分布了100個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的初始能量為0.5 J，基站的坐標(biāo)(50，50)。網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)的最遠(yuǎn)距離為×100 m。根據(jù)參考文獻(xiàn)[5]可得在通常情況下，無(wú)線傳輸?shù)膮?shù)為E_elec=50 nJ/bit，ε_fs=10 pJ/bit/m²，ε_mp=0.0013 pJ/bit/m⁴，數(shù)據(jù)融合消耗的能量系數(shù)E_DA=5 nJ/bit/signal。
　　對(duì)(9)式中權(quán)重因子α=0.6、0.5、0.4時(shí)ED-LEACH和LEACH算法比較結(jié)果如表1所示。

參考文獻(xiàn)
[1] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications.2002(1)：660-670.
[2] KARL H， WILLING A. Protocols and Architectures for Wireless Sensor Networks[M].Wiley，2005.
[3] SMARAGDAKIS G， BESTAVROS I M A. A Stable Election Protocol for clustered heterogeneous Wireless Sensor　Networks.
[4] 蘇瑩.無(wú)線傳感器網(wǎng)絡(luò)能量有效的分簇優(yōu)化算法研究.武漢：華中師范大學(xué)，2008.
[5] WANG A，HEINZELMAN W，CHANDRAKASAN A.Energy-Scalable Protocols for Battery-operated Microsensors Networks[C]//Proc. 1999 IEEE Workshop Singnal Processing Systems(SiPS’99)，Oct.1999：483-492.
[6] 俞黎陽(yáng).無(wú)線傳感器網(wǎng)絡(luò)網(wǎng)格狀分簇路由協(xié)議和數(shù)據(jù)融合算法研究.上海：華東師范大學(xué)，2008.

    由表1可得，ED-LEACH算法不論取0.6、0.5、還是0.4時(shí)，第一個(gè)節(jié)點(diǎn)、一半節(jié)點(diǎn)、全部節(jié)點(diǎn)死亡所經(jīng)過(guò)的輪數(shù)均比LEACH算法多。當(dāng)α=0.5時(shí)算法的性能最優(yōu)，第一個(gè)節(jié)點(diǎn)、一半節(jié)點(diǎn)、全部節(jié)點(diǎn)死亡輪數(shù)分別延長(zhǎng)了65.69%、86.15%、50.70%。將ED-LEACH算法(α=0.5)和LEACH算法利用matlab比較結(jié)果如圖1所示。

　　  本文在LEACH算法的基礎(chǔ)上，提出了一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)分簇算法ED-LEACH。由于本文在簇頭的選舉和非簇頭節(jié)點(diǎn)加入簇時(shí)都綜合考慮了能量和距離兩個(gè)因素，使網(wǎng)絡(luò)的負(fù)載比較均衡。理論分析和仿真實(shí)驗(yàn)一致表明ED-LEACH算法顯著延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)的生存周期。
　　  本文還有待改進(jìn)的地方，比如在考慮數(shù)據(jù)融合時(shí)，默認(rèn)為簇頭節(jié)點(diǎn)的數(shù)據(jù)融合能力是無(wú)限的，即無(wú)論該簇中非簇頭節(jié)點(diǎn)發(fā)送給簇頭節(jié)點(diǎn)多少數(shù)據(jù)，都能夠一次融合完成。但是實(shí)際情況是傳感器節(jié)點(diǎn)一次數(shù)據(jù)融合的能力是有限的^[6]，如果數(shù)據(jù)量比較大，不可能一次融合全部數(shù)據(jù)，必須多次融合多次發(fā)送，這樣才和現(xiàn)實(shí)比較接近。