基于節(jié)點(diǎn)向心性路由協(xié)議簇首的選舉協(xié)議

王 軍， 馬德朋， 徐萬一， 張亞君

(沈陽化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 遼寧 沈陽 110142)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng).它的目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對象的信息，并發(fā)送給觀察者.傳感器、感知對象和觀察者構(gòu)成了無線傳感器的3個(gè)要素[1].由于WSN具有節(jié)點(diǎn)可以大規(guī)模部署、自組織網(wǎng)絡(luò)、動態(tài)性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、數(shù)據(jù)和傳輸?shù)目煽啃砸约皞鞲衅鞴?jié)點(diǎn)高度集成的特點(diǎn)，使其在軍事監(jiān)控、環(huán)境監(jiān)測、地震與氣候預(yù)測、搶險(xiǎn)救災(zāi)、地下、深水以及外層空間探索等許多方面都具有廣泛的應(yīng)用前景[2-3].

當(dāng)今WSN路由協(xié)議的研究已經(jīng)成為國內(nèi)外備受關(guān)注的熱點(diǎn)[4].傳感器節(jié)點(diǎn)的能量消耗問題直接影響著無線傳感器網(wǎng)絡(luò)的生命周期[5-6].本文是在原有LEACH路由協(xié)議的基礎(chǔ)上，提出XX_LEACH路由協(xié)議.改進(jìn)后的路由協(xié)議很大程度地延長了無線傳感器網(wǎng)絡(luò)的生命周期，提高了數(shù)據(jù)傳輸?shù)男?

1 WSN路由協(xié)議的介紹

無線傳感器網(wǎng)絡(luò)網(wǎng)絡(luò)層路由協(xié)議執(zhí)行效率的高低對傳感器節(jié)點(diǎn)收發(fā)信息有直接的影響，進(jìn)而影響到傳感器節(jié)點(diǎn)的能量消耗，最終影響到整個(gè)WSN的性能[7].因此，網(wǎng)絡(luò)層的路由協(xié)議是當(dāng)今WSN研究的重要方向[8].這類協(xié)議主要是使監(jiān)測區(qū)域節(jié)點(diǎn)和目的節(jié)點(diǎn)(sink)之間的數(shù)據(jù)得到最優(yōu)化路徑傳輸[9].

2 LEACH路由協(xié)議概述

LEACH是一種基于聚類的路由協(xié)議，是最早的路由協(xié)議[10-11].LEACH協(xié)議主要分為類準(zhǔn)備和就緒兩個(gè)階段.在類準(zhǔn)備階段，LEACH協(xié)議隨機(jī)地選取一個(gè)傳感器節(jié)點(diǎn)作為簇頭節(jié)點(diǎn).類形成之后進(jìn)入就緒階段，簇頭節(jié)點(diǎn)開始接收簇內(nèi)節(jié)點(diǎn)采集的數(shù)據(jù)，經(jīng)過數(shù)據(jù)融合技術(shù)的處理，將整合之后的數(shù)據(jù)傳輸給目的節(jié)點(diǎn)(sink)[12-13].

2.1 LEACH簇頭的產(chǎn)生算法

首先在每個(gè)節(jié)點(diǎn)中選取0～1之間的隨機(jī)數(shù)，與閾值T(n)比較，小于閾值的作為簇頭.簇頭向節(jié)點(diǎn)廣播自己成為了簇頭的消息，節(jié)點(diǎn)根據(jù)收到信號的強(qiáng)弱選擇簇頭，并回復(fù)簇頭.其中T(n)的計(jì)算公式為：

(1)

其中：p是簇頭占所有節(jié)點(diǎn)百分比；rmod(1/p)代表一輪循環(huán)中當(dāng)選簇頭節(jié)點(diǎn)的個(gè)數(shù)；G是最近1/p輪中還沒有當(dāng)選過簇頭節(jié)點(diǎn)的集合；r是目前循環(huán)的輪數(shù)；n為節(jié)點(diǎn)的總數(shù).

2.2 LEACH協(xié)議算法流程

圖1為LEACH協(xié)議算法的流程，主要分為簇的建立、簇的形成、簇的路由、簇的循環(huán)幾個(gè)步驟[14].

圖1 LEACH協(xié)議算法流程Fig.1 LEACH Protocol algorithm flowchart

3 改進(jìn)的LEACH路由協(xié)議

在LEACH路由協(xié)議中，為了減慢簇內(nèi)節(jié)點(diǎn)的能量損耗，提高數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，使簇內(nèi)節(jié)點(diǎn)的能量消耗更均勻且緩慢，提高節(jié)點(diǎn)的能量利用效率，設(shè)計(jì)了XX_LEACH路由協(xié)議.改進(jìn)的LEACH路由協(xié)議主要是通過評估簇內(nèi)各節(jié)點(diǎn)與簇內(nèi)中心的距離和節(jié)點(diǎn)能量剩余以及節(jié)點(diǎn)溫度的綜合值來作為選取簇頭的參考，進(jìn)而使簇內(nèi)邊緣節(jié)點(diǎn)傳遞的數(shù)據(jù)更加可靠，避免簇內(nèi)少數(shù)節(jié)點(diǎn)出現(xiàn)過早死亡的現(xiàn)象，有效地增強(qiáng)了無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)傳遞的全面性和真實(shí)性.

3.1 基本思想

3.1.1 節(jié)點(diǎn)向心性

節(jié)點(diǎn)的向心性指的是簇建成之后簇內(nèi)各個(gè)節(jié)點(diǎn)距簇中心的距離.通常在簇頭選舉時(shí)用來衡量是否可以作為簇頭的標(biāo)準(zhǔn).

3.1.2 算法的基本思想

XX_LEACH協(xié)議算法的環(huán)境與LEACH協(xié)議的環(huán)境相同：(1)初始化網(wǎng)絡(luò)節(jié)點(diǎn)都屬于同種類型；(2)初始能量相同；(3)各節(jié)點(diǎn)在每一幀(Frame)中都有數(shù)據(jù)傳送；(4)節(jié)點(diǎn)靜止；(5)基站固定并遠(yuǎn)離WSN.假設(shè)初始值都為1，經(jīng)過一次循環(huán)后，簇內(nèi)節(jié)點(diǎn)的能量損耗各不相同，下一輪開始前，計(jì)算出每一個(gè)節(jié)點(diǎn)的位置距離簇內(nèi)中心位置的距離、剩余能量和節(jié)點(diǎn)溫度的綜合值作為下一輪簇頭選舉的條件.

由LEACH路由協(xié)議，在第一輪結(jié)束時(shí)計(jì)算出簇內(nèi)各節(jié)點(diǎn)位置的向心性、能量剩余和節(jié)點(diǎn)溫度的綜合值.將綜合值和其他數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，由簇頭經(jīng)過數(shù)據(jù)融合之后傳送給基站.再由基站計(jì)算出當(dāng)前各簇內(nèi)節(jié)點(diǎn)位置的向心程度、能量剩余和節(jié)點(diǎn)溫度的綜合值，并與第一輪的綜合值比較，如果差值大于閾值T(n)時(shí)，在網(wǎng)絡(luò)模型中刪除該節(jié)點(diǎn)，再把剩余的節(jié)點(diǎn)依據(jù)LEACH路由協(xié)議中規(guī)定T(n)的選舉下一輪的簇頭.實(shí)驗(yàn)結(jié)果表明：該過程可以提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃裕娱L網(wǎng)絡(luò)生命周期.

3.1.3 計(jì)算方法

(1) 計(jì)算節(jié)點(diǎn)的剩余能量

當(dāng)節(jié)點(diǎn)n將k位的數(shù)據(jù)傳送的距離為d時(shí)，剩余的能量公式為：

En(k,d)=Ec-(Efkd+Ejk)

(2)

其中，En(k,d)表示節(jié)點(diǎn)剩余的能量，k表示報(bào)文的長度，d表示傳輸?shù)木嚯x，Ec表示節(jié)點(diǎn)初始能量，Ef表示節(jié)點(diǎn)發(fā)送單位數(shù)據(jù)時(shí)消耗的能量，Ej表示節(jié)點(diǎn)接收單位數(shù)據(jù)時(shí)消耗的能量.通過計(jì)算簇內(nèi)節(jié)點(diǎn)的剩余能量，將其作為評估節(jié)點(diǎn)是否可以作為簇頭的條件之一，從而可以延長網(wǎng)絡(luò)的生命周期.

(2) 計(jì)算節(jié)點(diǎn)的向心性

通過計(jì)算節(jié)點(diǎn)n的位置坐標(biāo)(Si,Se)與簇內(nèi)中心坐標(biāo)(Za,Zb)的距離，解決節(jié)點(diǎn)邊緣化帶來的數(shù)據(jù)傳輸不準(zhǔn)確、不及時(shí)的問題.其計(jì)算公式為：

Dn(S,Z)=(Si-Za)2+(Se-Zb)2

(3)

其中，Dn(S,Z)表示簇內(nèi)節(jié)點(diǎn)到簇內(nèi)中心的距離，Si表示節(jié)點(diǎn)的橫坐標(biāo)，Se表示節(jié)點(diǎn)的縱坐標(biāo)，Za表示簇內(nèi)中心的橫坐標(biāo)，Zb表示簇內(nèi)中心的縱坐標(biāo).在無線傳感器網(wǎng)絡(luò)中，計(jì)算節(jié)點(diǎn)的向心性，將其作為評估節(jié)點(diǎn)是否可以成為簇首的另一個(gè)條件.節(jié)點(diǎn)向心性有效地提高了節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)目煽啃裕苊饬瞬涣嘉恢霉?jié)點(diǎn)傳輸數(shù)據(jù)的片面性和單一性.

(3) 計(jì)算節(jié)點(diǎn)的溫度

無線傳感器網(wǎng)絡(luò)在運(yùn)行的過程中，節(jié)點(diǎn)n隨著能量消耗EX的變化，節(jié)點(diǎn)溫度的計(jì)算公式為：

(4)

其中，Hn(t)表示節(jié)點(diǎn)的溫度值；EX表示節(jié)點(diǎn)的消耗能量；EC表示節(jié)點(diǎn)的初始能量；β表示節(jié)點(diǎn)容熱值的權(quán)值，其值根據(jù)實(shí)際應(yīng)用選取；βEX/EC即表示溫度的變化系數(shù)；HC表示節(jié)點(diǎn)的初始溫度.通過計(jì)算無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的溫度，將其作為簇首選擇時(shí)的一個(gè)條件，可以更好地解決簇內(nèi)節(jié)點(diǎn)負(fù)載過大時(shí)，能耗多的節(jié)點(diǎn)過早死亡的問題，有效地使簇內(nèi)節(jié)點(diǎn)的能量均勻消耗，使網(wǎng)絡(luò)的生命周期得到延長.

(4) 計(jì)算節(jié)點(diǎn)n的剩余能量、節(jié)點(diǎn)向心性以及節(jié)點(diǎn)溫度的綜合值

綜合評估節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的向心性和節(jié)點(diǎn)溫度，作為最終節(jié)點(diǎn)可以選為簇頭的條件.其計(jì)算公式為：

Pn=α1En(k,d)+α2Dn(S,Z)+α3Hn(t)

(5)

其中，α1、α2、α3分別表示節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)的向心性和節(jié)點(diǎn)溫度的權(quán)重值，具體權(quán)重值在應(yīng)用中根據(jù)實(shí)際情況選取.

3.2 算法流程

在真實(shí)環(huán)境里的無線傳感器網(wǎng)絡(luò)中，簇首選舉往往不能保證能量的均勻消耗以及簇內(nèi)節(jié)點(diǎn)過渡邊緣化造成的節(jié)點(diǎn)過早死亡、傳輸?shù)臄?shù)據(jù)不可靠等問題.XX_LEACH路由協(xié)議改進(jìn)簇首選舉的評估機(jī)制，通過計(jì)算簇形成后各節(jié)點(diǎn)到簇內(nèi)中心的距離和節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)溫度的綜合值來作為選擇簇頭的條件.該算法可以很大程度地提升數(shù)據(jù)傳輸?shù)恼鎸?shí)性，延長網(wǎng)絡(luò)的生命周期，可以解決實(shí)際環(huán)境中無線傳感器網(wǎng)絡(luò)存在的問題.其具體的算法流程如圖2所示.

圖2 XX_LEACH協(xié)議算法流程Fig.2 XX_LEACH protocol algorithm flowchart

3.3 算法的偽代碼

由XX_LEACH路由協(xié)議的算法流程，設(shè)計(jì)出算法的偽代碼，可以更直觀地看出該算法的執(zhí)行過程.具體編寫如下：

Begin

輸入P1，Pn-1，Pn

輸入T(n)

IFPn-Pn-1>=T(n)

則刪除該節(jié)點(diǎn)，執(zhí)行LEACH路由協(xié)議

否則執(zhí)行LEACH路由協(xié)議

Print循環(huán)此過程

End

4 仿真

4.1 搭建仿真環(huán)境

在仿真環(huán)境中，為了更清晰地了解改進(jìn)后的LEACH路由協(xié)議，XX_LEACH設(shè)置的仿真參數(shù)如表1所示.

表1 仿真參數(shù)Table 1 Simulation parameters

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

使用OPNET網(wǎng)絡(luò)仿真工具進(jìn)行仿真，同時(shí)使用MATLAB數(shù)據(jù)分析軟件進(jìn)行數(shù)據(jù)結(jié)果比較分析，從無線傳感器網(wǎng)絡(luò)中網(wǎng)絡(luò)的剩余能量和節(jié)點(diǎn)的存活數(shù)對LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議進(jìn)行對比[15].

在LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議中，各自的節(jié)點(diǎn)剩余能量變化如圖3所示.

圖3 3種協(xié)議剩余能量的比較Fig.3 Comparison of residual energy of three protocols

在0～79輪時(shí)，LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議節(jié)點(diǎn)的剩余能量幾乎相同；在79輪之后，隨著時(shí)間的增加，3種協(xié)議下節(jié)點(diǎn)所剩的能量開始出現(xiàn)差距，LEACH協(xié)議和NPT_LEACH協(xié)議中節(jié)點(diǎn)的消耗能量增多，XX_LEACH協(xié)議中節(jié)點(diǎn)的剩余能量明顯多于LEACH協(xié)議和NPT_LEACH協(xié)議中節(jié)點(diǎn)剩余能量.研究結(jié)果表明：改進(jìn)的XX_LEACH能夠減少能量的消耗，延長網(wǎng)絡(luò)的生命周期.

觀察LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議，3種協(xié)議在相同時(shí)間內(nèi)，存活節(jié)點(diǎn)數(shù)的變化如圖4所示.當(dāng)最初都為100個(gè)節(jié)點(diǎn)存活時(shí)，LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議在600輪之后，XX_LEACH協(xié)議存活的節(jié)點(diǎn)個(gè)數(shù)明顯高于LEACH協(xié)議和NPT_LEACH協(xié)議存活的節(jié)點(diǎn)個(gè)數(shù)；LEACH協(xié)議和NPT_LEACH協(xié)議在1 600輪時(shí)，節(jié)點(diǎn)全部死亡，而XX_LEACH協(xié)議直到1 800輪時(shí)才全部死亡.改進(jìn)結(jié)果表明：XX_LEACH協(xié)議比LEACH協(xié)議和NPT_LEACH協(xié)議性能更好；XX_LEACH協(xié)議使節(jié)點(diǎn)存活的個(gè)數(shù)顯著增多，能延長無線傳感器網(wǎng)路的生命周期.

圖4 3種協(xié)議存活節(jié)點(diǎn)的比較Fig.4 Comparison of survival nodes of three protocols

LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議中節(jié)點(diǎn)的分布情況如圖5～圖7所示.

圖5 LEACH協(xié)議節(jié)點(diǎn)的分布Fig.5 LEACH protocols node map

圖6 NPT_LEACH協(xié)議節(jié)點(diǎn)分布Fig.6 NPT_LEACH protocols node map

圖7 XX_LEACH協(xié)議節(jié)點(diǎn)分布Fig.7 XX_LEACH protocols node map

從圖5、圖6中可以清楚地看到：LEACH協(xié)議節(jié)點(diǎn)和NPT_LEACH協(xié)議節(jié)點(diǎn)與簇頭之間的距離比較分散，邊緣節(jié)點(diǎn)時(shí)刻存在，造成簇頭的負(fù)載不均衡，能量消耗不均勻等結(jié)果.而通過改進(jìn)的XX_LEACH協(xié)議與LEACH協(xié)議和NPT_LEACH協(xié)議相比，可以明顯地看出節(jié)點(diǎn)與簇頭之間的距離趨近于均勻分布(見圖7)，能更好地實(shí)現(xiàn)節(jié)點(diǎn)的能耗均勻，數(shù)據(jù)傳輸更有效.

根據(jù)仿真結(jié)果比較LEACH協(xié)議、NPT_LEACH協(xié)議和XX_LEACH協(xié)議的性能.從路由策略、以數(shù)據(jù)為中心、最優(yōu)路徑、穩(wěn)定性和可靠性5個(gè)方面分析[9]，得出的結(jié)論如表2所示.

表2 3種路由協(xié)議性能的比較Table 2 Comparison of three routing protocols

5 算法分析與展望

基于節(jié)點(diǎn)向心性的路由協(xié)議簇首選舉，在LEACH協(xié)議的基礎(chǔ)之上，提出了XX_LEACH路由協(xié)議.以節(jié)點(diǎn)的向心性和節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)溫度綜合值作為簇首選舉的標(biāo)準(zhǔn)，有效解決了無線傳感器網(wǎng)絡(luò)中各節(jié)點(diǎn)，尤其是邊緣節(jié)點(diǎn)數(shù)據(jù)傳輸時(shí)能量消耗不均勻的問題.XX_LEACH路由協(xié)議算法的提出，能夠提高各節(jié)點(diǎn)的能量利用效率，延長網(wǎng)絡(luò)的生命周期，解決LEACH路由協(xié)議簇首選取方法的不足.通過OPNET網(wǎng)絡(luò)仿真工具，使用MATLAB進(jìn)行數(shù)據(jù)分析比較，對新型的無線傳感器路由協(xié)議XX_LEACH進(jìn)行仿真.仿真結(jié)果表明：XX_LEACH協(xié)議與LEACH協(xié)議相比，能更好地減緩無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，延長網(wǎng)絡(luò)的生命周期，該算法比LEACH的簇頭選擇方法更可靠.為了更好地解決無線傳感器網(wǎng)絡(luò)分簇路由的問題，對于 XX_LEACH路由協(xié)議，在以后簇頭選取的研究中不能只局限于節(jié)點(diǎn)的向心性、節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)溫度3個(gè)因素，還需要考慮簇頭到基站的距離，以及節(jié)點(diǎn)的密集程度等因素.XX_LEACH協(xié)議的提出，在無線傳感器網(wǎng)絡(luò)的理論指導(dǎo)和實(shí)際發(fā)展中有著重大的意義.