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

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

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

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

　　根據(jù)極值定理可得k₀為最小值。k₀由計算能力很強的基站完成，并且每經(jīng)過事先設(shè)定的若干個周期重新計算一次，因為通信中將不斷有節(jié)點因能量耗盡而死亡。
　　本文在簇頭選舉時綜合考慮能量和距離兩個因素，為每個節(jié)點分配一個權(quán)值表示其適合充當簇頭的程度。某個節(jié)點i在第r輪簇頭選舉中的競選權(quán)值為：

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

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

參考文獻
[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ǎ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] 俞黎陽.無線傳感器網(wǎng)絡(luò)網(wǎng)格狀分簇路由協(xié)議和數(shù)據(jù)融合算法研究.上海：華東師范大學(xué)，2008.

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

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