LEACH協(xié)議的簇首多跳與選擇優(yōu)化

付云虹等

摘要：針對WSN層次型路由協(xié)議中簇首單跳傳輸數(shù)據(jù)至匯聚節(jié)點(diǎn)、而部分簇首因傳輸距離過長導(dǎo)致能量過早耗盡從而影響整個網(wǎng)絡(luò)壽命問題，提出了基于剩余能量對簇首優(yōu)化選擇和簇首至匯聚節(jié)點(diǎn)間多跳數(shù)據(jù)傳輸?shù)母倪M(jìn)算法.對首個節(jié)點(diǎn)死亡輪數(shù)和能量圖像方面進(jìn)行了分析和仿真，結(jié)果表明該改進(jìn)算法可使全網(wǎng)負(fù)載更加均衡，并進(jìn)一步延長了網(wǎng)絡(luò)整體壽命.

關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；層次型拓?fù)洌淮厥走x擇；多跳

中圖分類號：TP391.9 文獻(xiàn)標(biāo)識碼：A

無線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是大型的信息采集網(wǎng)絡(luò)，傳感器節(jié)點(diǎn)通常依靠電池供電，而電池能量有限，從而影響到整個無線網(wǎng)絡(luò)的生存壽命，因此基于WSN的各種路由算法都會盡量節(jié)省能量，延長網(wǎng)絡(luò)的整體壽命[1].路由協(xié)議的任務(wù)是將數(shù)據(jù)分組從源節(jié)點(diǎn)（傳感器，sensor）通過無線網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)（匯聚節(jié)點(diǎn)，sink）[2-3].

無線傳感網(wǎng)絡(luò)中的路由協(xié)議從拓?fù)浞植紝用鎭砜纯煞譃槠矫嫘吐酚蓞f(xié)議和層次型路由協(xié)議.由于平面型路由協(xié)議需要維護(hù)一個很大的路由表，從而會占用較大的存儲空間與較多的計算資源，并不適用于規(guī)模巨大的無線傳感網(wǎng)絡(luò)，而層次型路由協(xié)議可以改善這一點(diǎn).文章基于層次型路由中的LEACH協(xié)議[4]，致力于深入研究已有的針對LEACH協(xié)議的算法優(yōu)化，以延長網(wǎng)絡(luò)壽命和節(jié)省能量為目的，對其進(jìn)一步優(yōu)化和改進(jìn).

層次型拓?fù)淇刂评梅执貦C(jī)制，選擇一些節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，由簇頭節(jié)點(diǎn)生成處理和轉(zhuǎn)發(fā)數(shù)據(jù)的骨干網(wǎng)，其余非骨干網(wǎng)節(jié)點(diǎn)可以暫時關(guān)閉通信信道，進(jìn)入休眠狀態(tài)以節(jié)省能量[5].層次型的拓?fù)鋮f(xié)議有LEACH，HEED，GAF等.無線傳感網(wǎng)絡(luò)拓?fù)淇刂浦饕芯康膯栴}是：在滿足網(wǎng)絡(luò)覆蓋度和連通度的前提下，通過功率控制和骨干網(wǎng)節(jié)點(diǎn)的選擇，剔除節(jié)點(diǎn)之間不必要的通信鏈路，生成優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)[6].LEACH協(xié)議是最初使用的協(xié)議，它的成簇思想對以后的協(xié)議改進(jìn)影響很大.但是LEACH也有一些缺點(diǎn)，例如網(wǎng)絡(luò)分簇不均勻、可擴(kuò)展性差和容錯性差等，因此后續(xù)的研究者根據(jù)其缺點(diǎn)進(jìn)行了多方面的改進(jìn)，下面是部分改進(jìn)算法：

HEED算法針對LEACH算法簇頭分布不均，以及簇的規(guī)模大小不均這一問題的改進(jìn)[7].在此算法中，節(jié)點(diǎn)以不同的概率發(fā)送消息，剩余能量越大當(dāng)選簇首的概率越大.非簇首節(jié)點(diǎn)使用簇內(nèi)最小可達(dá)能量來衡量簇內(nèi)節(jié)點(diǎn)的通訊成本并以此來選擇合適的簇頭，可以平衡簇內(nèi)節(jié)點(diǎn)的個數(shù)[8].

基于節(jié)點(diǎn)的剩余能量選擇簇首.考慮到無線傳感網(wǎng)絡(luò)的能耗問題，選取剩余能量較多的節(jié)點(diǎn)作為簇首.將節(jié)點(diǎn)的剩余能量作為選擇簇首的一個重要衡量標(biāo)準(zhǔn)，以保證區(qū)域內(nèi)剩余能量越多的節(jié)點(diǎn)，被選為簇首的概率越大.簇首與匯聚節(jié)點(diǎn)（Sink）或者說基站（Base Station， BS）之間的數(shù)據(jù)發(fā)送過程采用單跳的方式.由于匯聚節(jié)點(diǎn)距離數(shù)據(jù)采集區(qū)域距離不定，可能在區(qū)域內(nèi)，也可能在區(qū)域外.即使是在區(qū)域內(nèi)，根據(jù)成簇方式的不同，部分簇首離基站的距離也可能很遠(yuǎn)，因此這部分簇首將數(shù)據(jù)發(fā)送給基站時所消耗的能量較多[5].基于這一點(diǎn)，在簇首向基站發(fā)送數(shù)據(jù)的時候可考慮采用多跳的方式，這樣可以使簇首節(jié)點(diǎn)能量的消耗相對減少.

另一種改進(jìn)算法將原有的簇頭選舉分為兩種情況：全網(wǎng)簇頭選舉和簇內(nèi)簇頭選舉.在改進(jìn)的LEACH算法中設(shè)置了一個閥值Va.每個簇周期開始時，首先檢查簇頭能量，如果所有節(jié)點(diǎn)的簇頭能量中存在小于Va的簇頭，則進(jìn)行全網(wǎng)簇頭選舉，否則進(jìn)行簇內(nèi)選舉[9].

本文在已有的LEACH改進(jìn)協(xié)議基礎(chǔ)上基于剩余能量對簇首進(jìn)行優(yōu)化選擇和簇首至匯聚節(jié)點(diǎn)間多跳傳輸方面提出改進(jìn)措施，并對第一個節(jié)點(diǎn)死亡輪數(shù)和能量圖像開展分析和仿真，預(yù)期改進(jìn)措施有3點(diǎn)：

1）根據(jù)距離匯聚節(jié)點(diǎn)遠(yuǎn)近對節(jié)點(diǎn)進(jìn)行分類；

2）根據(jù)節(jié)點(diǎn)剩余能量不同進(jìn)行簇首優(yōu)化選擇；

3）簇首間數(shù)據(jù)多跳傳遞至匯聚節(jié)點(diǎn).

1簇首個數(shù)最優(yōu)化分析

采集區(qū)域內(nèi)簇頭最優(yōu)個數(shù)的確定是對層次型路由算法進(jìn)行改進(jìn)的基礎(chǔ).設(shè)在M×M的區(qū)域內(nèi)分布著N個節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)初始能量大小分為高級節(jié)點(diǎn)和普通節(jié)點(diǎn)兩類，其中存在C個簇頭，而C個簇頭決定了在該區(qū)域內(nèi)一共有C個簇，假定所有的節(jié)點(diǎn)均勻分布，因此每個簇內(nèi)有N/C個節(jié)點(diǎn)，其中一個是簇首節(jié)點(diǎn)，其余節(jié)點(diǎn)有（N/C-1）個.下面對兩類節(jié)點(diǎn)的能量消耗進(jìn)行分析，首先分析簇首節(jié)點(diǎn).

簇首能量消耗分為3部分：

1）接收非簇首節(jié)點(diǎn)傳輸數(shù)據(jù)的能量；

2）對接收到的數(shù)據(jù)進(jìn)行融合處理的能量；

3）將融合后數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)的能量.

用公式表示為：

下面對式（1），（2）進(jìn)行說明.由于傳感區(qū)域很大，不同的節(jié)點(diǎn)傳輸數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)的距離有大有小，因而傳輸過程中衰減分為自由空間衰減和多徑衰減[10].自由空間是一種理想介質(zhì)，它不會吸收能量，但是隨著傳播距離的增大，發(fā)射天線的輻射功率密度與距離的平方成反比，因此自由空間傳播損耗是一種擴(kuò)散式的自然能量損耗.在非簇首節(jié)點(diǎn)傳輸信息給簇首節(jié)點(diǎn)時，一般距離比較近，可以用表示自由空間能量損耗的式（2）表示.多徑衰落是指在微波信號的傳播過程中，由于受地面或水面反射和大氣折射的影響，會產(chǎn)生多個經(jīng)過不同路徑到達(dá)接收天線的信號，通過矢量疊加后合成時變信號.基于簡化模型的思想，可認(rèn)為遠(yuǎn)距離傳輸更容易發(fā)生多徑衰落的現(xiàn)象.相對而言簇首節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的距離較遠(yuǎn)，因此在后面計算中簇首節(jié)點(diǎn)的能量消耗用公式（1）.以上是針對最優(yōu)簇頭個數(shù)進(jìn)行計算，而決定其是屬于自由空間衰減還是多徑衰減具有一個臨界距離，在仿真模擬時可更精確地進(jìn)行判斷.根據(jù)上述描述得到總的能量消耗公式：

通過上述分析計算可以得到使數(shù)據(jù)采集區(qū)域總能量消耗最小的簇首最優(yōu)個數(shù)的大小.決定節(jié)點(diǎn)是否為簇首的算法描述如圖 1所示，其中R代表節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的距離，xm是傳感區(qū)域的邊長，其算法依據(jù)主要是考慮該節(jié)點(diǎn)離匯聚節(jié)點(diǎn)的距離以及是否是高級節(jié)點(diǎn).

2簇首選擇概率與多跳數(shù)據(jù)傳輸

根據(jù)距離大小可對節(jié)點(diǎn)進(jìn)行細(xì)化分類，如果傳感區(qū)域很大，使用單跳傳輸數(shù)據(jù)方式時，距離匯聚節(jié)點(diǎn)距離太大的簇首節(jié)點(diǎn)能量消耗將會非?？焖?經(jīng)典的LEACH算法采用的方式是每個節(jié)點(diǎn)不管距離匯聚節(jié)點(diǎn)的距離遠(yuǎn)近，其當(dāng)選簇首節(jié)點(diǎn)的概率大小相同.而如果距離匯聚節(jié)點(diǎn)近的節(jié)點(diǎn)當(dāng)選簇首的概率大，距離匯聚節(jié)點(diǎn)遠(yuǎn)的節(jié)點(diǎn)當(dāng)選簇首的概率小，就會使節(jié)點(diǎn)數(shù)據(jù)盡量向靠近匯聚節(jié)點(diǎn)的方向傳播，而不是先向遠(yuǎn)離匯聚節(jié)點(diǎn)的簇首傳播，簇首再向匯聚節(jié)點(diǎn)傳播.具體實(shí)現(xiàn)是以匯聚節(jié)點(diǎn)為圓心，以不同長度為半徑將數(shù)據(jù)采集區(qū)域劃分為多個區(qū)塊，每個區(qū)塊的節(jié)點(diǎn)當(dāng)選簇首的概率不同.處于不同半徑區(qū)域內(nèi)的節(jié)點(diǎn)當(dāng)選簇首的概率可通過設(shè)定不同的概率值進(jìn)行仿真，根據(jù)仿真結(jié)果進(jìn)行比對，以確定優(yōu)化值.

數(shù)據(jù)融合[11]方面，經(jīng)典LEACH算法是非簇首節(jié)點(diǎn)把數(shù)據(jù)傳輸給簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)接收到數(shù)據(jù)后進(jìn)行信息融合，再將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn).在這過程中，簇首節(jié)點(diǎn)如果距離匯聚節(jié)點(diǎn)很遠(yuǎn)，那么單跳數(shù)據(jù)傳輸過程中的能量衰減會相對較大.簇首節(jié)點(diǎn)可以先比較自身與其他簇首節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的距離哪個更近，如果是距離匯聚節(jié)點(diǎn)更近那么直接傳輸數(shù)據(jù)給匯聚節(jié)點(diǎn)；如果是距離另一個簇首節(jié)點(diǎn)更近則傳輸給該簇首節(jié)點(diǎn)，第二個接收到數(shù)據(jù)的簇首節(jié)點(diǎn)再將數(shù)據(jù)進(jìn)行融合，進(jìn)行比較，采用同樣的方式對數(shù)據(jù)進(jìn)行處理，直到傳輸給最后的匯聚節(jié)點(diǎn).

之前也有學(xué)者對簇首節(jié)點(diǎn)多跳算法開展研究，但是數(shù)據(jù)采集區(qū)域面積大小與多跳算法改進(jìn)效率的關(guān)系并未提及.簇首間采用多跳數(shù)據(jù)傳輸?shù)某霭l(fā)點(diǎn)，在于離匯聚節(jié)點(diǎn)距離較遠(yuǎn)的簇首節(jié)點(diǎn)單跳傳輸數(shù)據(jù)給匯聚節(jié)點(diǎn)所耗費(fèi)的能量太大，因此才考慮使用簇首間多跳.基于這一出發(fā)點(diǎn)，推測數(shù)據(jù)采集區(qū)域越大，其對整個網(wǎng)絡(luò)生存壽命的改善效果應(yīng)該越好.同時，中繼簇首如果接收其他簇首的數(shù)據(jù)進(jìn)行融合然后再傳輸也需要消耗能量，因此簇首多跳算法的改進(jìn)效果與數(shù)據(jù)采集區(qū)域的大小是有密切關(guān)系的.

3仿真結(jié)果與分析

使用Matlab工具開展仿真實(shí)驗(yàn).本文所述的改進(jìn)思路主要是在簇的建立階段，因此考慮使用簡化模型，只考慮簇建立階段和數(shù)據(jù)傳輸階段即穩(wěn)定階段的能量消耗，忽略節(jié)點(diǎn)數(shù)據(jù)具體內(nèi)容和數(shù)據(jù)的融合方式.

將n個節(jié)點(diǎn)隨機(jī)散布在傳感區(qū)域內(nèi)，sink節(jié)點(diǎn)分布在傳感區(qū)域的中心，仿真用到的其他基礎(chǔ)數(shù)據(jù)來自于文獻(xiàn)[12].由于針對LEACH算法進(jìn)行了兩點(diǎn)改進(jìn)，分析單獨(dú)改進(jìn)每一點(diǎn)后的仿真結(jié)果，最后再將兩點(diǎn)綜合起來分析仿真結(jié)果.

首先考慮根據(jù)節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)遠(yuǎn)近選取不同的當(dāng)選概率時的仿真結(jié)果，如表1所示.R是節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的距離，M為傳感區(qū)域邊長.在Firstdead一列中代表網(wǎng)絡(luò)中第一個節(jié)點(diǎn)死亡的輪數(shù)，該數(shù)據(jù)越大代表網(wǎng)絡(luò)壽命越長，負(fù)載越均衡.如表中仿真結(jié)果所示，節(jié)點(diǎn)當(dāng)選簇首概率選取數(shù)據(jù)⑥時，其第一個節(jié)點(diǎn)死亡輪數(shù)最長，性能最優(yōu)，數(shù)據(jù)（①代表的是經(jīng)典LEACH算法中簇首選擇概率.由仿真結(jié)果可以算出，采用該改進(jìn)方法，第一個節(jié)點(diǎn)死亡的輪數(shù)比經(jīng)典算法優(yōu)化：

由于節(jié)點(diǎn)是隨機(jī)均勻分布，每次仿真時所得到的第一個節(jié)點(diǎn)死亡的輪數(shù)不盡相同，從圖像和相關(guān)數(shù)據(jù)分析，改進(jìn)后的算法在有節(jié)點(diǎn)死亡后的優(yōu)勢更加凸顯，其能量下降得更慢一點(diǎn)，表明全網(wǎng)絡(luò)的負(fù)載更加均衡一些.

下面分析使用簇首間多跳傳輸算法的仿真結(jié)果.

表2 給出的是在數(shù)據(jù)采集區(qū)域大小取不同值時，對經(jīng)典LEACH算法和改進(jìn)簇首多跳傳輸算法（以LEACHMH標(biāo)示）第一個節(jié)點(diǎn)死亡輪數(shù)的比較，考慮到節(jié)點(diǎn)死亡數(shù)目達(dá)到一定比例后整個網(wǎng)絡(luò)已不具備正常收集數(shù)據(jù)的能力，因此該對比過程僅以首個節(jié)點(diǎn)死亡時間作為參考.

4小結(jié)

本文通過對經(jīng)典LEACH算法及其改進(jìn)算法進(jìn)行研究，在綜合節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離、節(jié)點(diǎn)初始能量大小和傳感區(qū)域面積這三點(diǎn)的基礎(chǔ)上提出改進(jìn)措施，延長第一個節(jié)點(diǎn)死亡時間即均衡網(wǎng)絡(luò)負(fù)載延長網(wǎng)絡(luò)壽命.通過Matlab對改進(jìn)算法進(jìn)行仿真后發(fā)現(xiàn)，改進(jìn)程度的大小和傳感區(qū)域面積大小有密切關(guān)系：面積越大多跳改進(jìn)方案的優(yōu)勢越明顯.雖然節(jié)點(diǎn)是隨機(jī)分布的，簇頭為隨機(jī)選舉，每次仿真時第一個節(jié)點(diǎn)死亡輪數(shù)不盡相同，但是從仿真結(jié)果看，對網(wǎng)絡(luò)壽命還是有明顯的延長.當(dāng)然這其中還存在一些其他的問題，例如在距離越大當(dāng)選簇頭概率相對越小這部分改進(jìn)措施適應(yīng)性尚待加強(qiáng)，因?yàn)楫?dāng)區(qū)域面積改變或者節(jié)點(diǎn)數(shù)目改變時相應(yīng)的概率大小也要隨之調(diào)整；一些論文也提出多跳算法所用到的數(shù)據(jù)融合即將多級數(shù)據(jù)融合后壓縮到原來的長度其實(shí)很難實(shí)現(xiàn).下一步工作將會在以上不足之處再繼續(xù)開展深入研究，進(jìn)一步改善無線網(wǎng)絡(luò)性能.

參考文獻(xiàn)

[1]OZEL Omur， TUTUNCUOGLU Kaya， YANG Jing，et al. Transmission with energy harvesting nodes in fading wireless channels： optimal policies[J]. IEEE Journal on Selected Areas in Communications， 2011，29（8）：1732-1743.

[2]LIU A， ZHENG Z， ZHANG C， et al. Secure and energyefficient disjoint multipath routing for WSNs[J]. Vehicular Technology， IEEE Transactions on， 2012， 61（7）： 3255-3265.

[3]LONG H， QU Z H， FAN X， et al. Dynamic nearest neighborhood collaboration target tracking for WSN[J]. Energy Procedia， 2011， 11： 707-714.

[4]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（4）：660-670.

[5]RAZZAQUE M A， AHMED M H U， HONG C S， et al.QoSaware distributed adaptive cooperative routing in wireless sensor networks[J]. Ad Hoc Netw，2014，19：28-42.

[6]LI Changle，WANG Liran， SUN Tingting，et al. Topology analysis of sireless sensor networks based on nodes spatial distribution[J]. IEEE Transactions on Wireless Communications， 2014，13（5）： 2454-2467.

[7]YOUNIS O， FAHMY S. Distributed clustering in adhoc sensor networks： A hybrid， energyefficient approach[C] // INFOCOM 2004， Twentythird Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE， 2004，1-5.

[8]金鑫. 無線傳感器網(wǎng)絡(luò)層次型拓?fù)淇刂扑惴╗D]. 合肥： 中國科學(xué)技術(shù)大學(xué)計算機(jī)科學(xué)與技術(shù)系，2008.

JIN Xin. A research on hierarchical topology control algorithms and the related problems of wireless sensor networks[D]. Hefei：Department of Computer Science& Technology， University of Science and Technology of China， 2008.（In Chinese）

[9]唐甲東. 無線傳感器網(wǎng)絡(luò)路由協(xié)議研究-LEACH路由協(xié)議的改進(jìn)[D]. 無錫： 江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院， 2013.

TANG Jiadong. Research on routing protocol for wireless sensor networksImproment of LEACH routing protocol[D]. Wuxi：College of Internet of Things Engineering， Jiangnan University， 2013. （In Chinese）

[10]LI Changle， WANG Liran， SUN Tingting ，et al. Topology analysis of wireless sensor networks based on nodes spatial distribution[J]. IEEE Transactions on Wireless Communications， 2014，13（5）： 2454-2467.

[11]李嘉， 劉春華， 胡賽陽， 等. 基于交通數(shù)據(jù)融合技術(shù)的行程時間預(yù)測模型[J].湖南大學(xué)學(xué)報：自然科學(xué)版，2014，41（1）：33-38.

LI Jia， LIU Chunhua， HU Saiyang，et al. A travel time prediction model based on traffic data fusion technology[J]. Journal of Hunan University： Natural Sciences， 2014，41（1）：33-38. （In Chinese）

[12]SMARAGDAKIS Georgios， MATTA Ibrahim， BESTAVROS Azer. SEP： A stable election protocol for clustered heterogeneous wireless sensor networks[C]//Second International Workshop on Sensor and Actor Network Protocols and Applications （SANPA 2004）.Boston MA，2004： 165-190.