基于分層的多跳分簇路由算法

基于分層的多跳分簇路由算法

無線傳感器網(wǎng)絡（wsd）通常由各種隨機分布的傳感器節(jié)點組成，以承擔電池電源的任務。在無人監(jiān)控下。因為節(jié)點一般不太可能更換電池,所以能量受限是傳感器網(wǎng)絡最顯著的特點之一,因此設計高效的路由算法是WSN設計的一個重點。隨著研究的深入,各種路由算法如LEACH、SEP、HEED等被提出來用以有效利用節(jié)點能量。LEACH是最早提出的一種基于簇結構的層次型WSN路由算法。該算法的基本思想是通過隨機循環(huán)地選擇簇首,將整個網(wǎng)絡的能量負載平均分配到每個傳感器節(jié)點中,從而達到降低網(wǎng)絡能源消耗、提高網(wǎng)絡整體生存時間的目的。SEP是對LEACH的改進,對不同剩余能量的節(jié)點采用不同的選舉概率。HEED采用能量和通信代價(AMRP)主次兩個參數(shù)分布式選擇簇首,從而使簇首的分布更加均勻,進一步減少能耗。但這些算法都要求傳感器節(jié)點與Sink節(jié)點可以直接通信,因此網(wǎng)絡的擴展性不強,不適用于大型網(wǎng)絡。為了彌補單跳通信的缺陷,發(fā)展出了多跳路由算法如PEGASIS、UCS、EEUC等。PEGASIS算法中距離簇首越近的節(jié)點能耗越大,會使整個網(wǎng)絡的能耗不均衡。UCS算法將節(jié)點按距離Sink的遠近分成大小不同的簇,較好地克服了“熱點”問題,但該算法假定里層的簇首在圓形區(qū)域中的分布是事先設計好的,這個假設不適合于隨機部署的WSN網(wǎng)絡。EEUC算法是和UCS類似的異構網(wǎng)絡算法,該算法的基本思想是使每個節(jié)點先根據(jù)一個預先確定的門限,隨機確定自己是否成為偽簇首,成為偽簇首的節(jié)點根據(jù)接收到的Sink信號能量,計算自己與Sink的距離,形成不同半徑的競爭區(qū)域,競爭區(qū)域內的偽簇首通過競爭,能量最大的成為簇首;簇首再根據(jù)周圍簇首的剩余能量與轉發(fā)代價,從轉發(fā)代價最小的2個簇首中選擇剩余能量最大的簇首作為自己的下一跳節(jié)點。同樣,該算法中需要得出節(jié)點的位置信息,這是一個難點,而且若有節(jié)點接收不到Sink節(jié)點的信號,則該節(jié)點將無法加入網(wǎng)絡,這使整個網(wǎng)絡的連通性存在一定的問題。針對LEACH等路由算法擴展性不強,而UCS等路由算法應對網(wǎng)絡隨機性不足等缺點,本文融合了傳感網(wǎng)絡的分簇思想和鏈式多跳機制,根據(jù)通信代價對網(wǎng)絡進行分層,提出了分層多跳分簇路由算法LBMC(LayerBasedMultihopClusteringroutingalgorithm,LBMC)。與SEP、LEACH等算法相比,獲得了更好的能量效率和更高的網(wǎng)絡生存時間。1區(qū)域多排設器假設有N個節(jié)點隨機分布于一片區(qū)域,節(jié)點能量異構,但分布基本均勻,節(jié)點位置未知,Sink節(jié)點位于區(qū)域邊緣或者區(qū)域中間。首先將監(jiān)控區(qū)域根據(jù)通信代價分成多個層,層的寬度可以通過參數(shù)控制;然后采用類似于LEACH的簇首選舉算法,根據(jù)事先計算出的最優(yōu)閾值選舉簇首,每一層的最優(yōu)閾值可以不同,此后根據(jù)剩余能量最大原則指定下一輪簇首;簇首間形成簇首鏈進行通信;簇內節(jié)點與簇首間一般通過單跳通信,但對于一些邊緣節(jié)點可以通過虛擬簇首進行多跳通信;最后形成一個能耗均勻、簇大小異構的多跳無線傳感器網(wǎng)絡,克服網(wǎng)絡中的“熱點”問題。1.1最大的所在層參數(shù)分層網(wǎng)絡模型如圖1所示,Sink節(jié)點位于監(jiān)控區(qū)域邊緣,網(wǎng)絡中節(jié)點分為多個層,最靠近Sink節(jié)點為第1層,向外分別為第2、3…層,各層中節(jié)點數(shù)量在分層之前并不知道。網(wǎng)絡建立路由的第一步便是執(zhí)行分層算法。分層算法的實質是根據(jù)通信代價的高低對區(qū)域中的傳感器進行分類,到Sink節(jié)點的通信代價相同或相近的節(jié)點歸為一類。分層算法成功結束時,會使每個節(jié)點得到唯一的所在層參數(shù),這個參數(shù)會逐層遞增,表示了通信代價的逐層遞增,這個特性在數(shù)據(jù)路由時提供了一個強有力的路由方向選擇依據(jù)。層參數(shù)越小,通信代價越小,越靠近Sink節(jié)點。數(shù)據(jù)在路由時,便可以據(jù)此選出能量代價最小的路由路徑。Sink節(jié)點向網(wǎng)絡發(fā)送一個分層指令,并包含一個層寬調節(jié)參數(shù)Rp、發(fā)射功率PT和當前所在層L。其中Rp是功率比閾值,節(jié)點用Rp與進行比較來確定自己所處的層,其中PR是接收功率(即RS-SI,ReceivedSignalStrengthIndication)。對于Sink節(jié)點來說,L=0。在網(wǎng)絡分層之前,每一個節(jié)點都將自己所在層標識為L=0。分層指令以類似泛洪傳播的方式在網(wǎng)絡傳播。假設節(jié)點i已經(jīng)確定了自己所在的層(如Sink節(jié)點),節(jié)點j接收到了來自節(jié)點i的分層指令(Rp,PTi,Li),則進行判斷,若則忽略這個消息,若則進行如下操作:如果Lj=0或者Lj>Li+1,則設置Lj=Li+1,記錄Rp,修正分層指令中的參數(shù),即用PTj和Lj替換PTi和Li,而后轉發(fā)分層指令。這樣處理可以減少不必要的指令轉發(fā),有效防止泛洪風暴帶來的能量損耗。經(jīng)過一段時間以后,網(wǎng)絡中所有的節(jié)點都能確定自己所在的層。分層算法到此結束。1.2無線傳感器網(wǎng)絡的融合每一層的簇首節(jié)點個數(shù)及其分布將顯著地影響網(wǎng)絡的能耗、健壯性、連通性等性能指標,因此我們需要計算出每一層的最優(yōu)簇首個數(shù)。我們將以能耗為考慮重點,推導出每一層最優(yōu)簇首個數(shù)的計算公式。根據(jù)文獻的無線信道能量消耗自由空間模型,發(fā)送一個l比特的數(shù)據(jù)包到距離發(fā)送端為d的節(jié)點需要消耗的能量為:而接收這個數(shù)據(jù)包需要消耗的能量為:根據(jù)文獻中實驗所測數(shù)據(jù),通常情況下,發(fā)射能量Eelec=50nJ/bit,自由空間傳播系數(shù)εfs=10pJ/bit/m2,εmp=0.0013pJ/bit/m2,數(shù)據(jù)融合能量消耗系數(shù)EDA=5nJ/bit/signa,在本文的網(wǎng)絡模型中,無線傳感器網(wǎng)絡共分為s層,各層的寬度為δ,每層節(jié)點數(shù)為Nk,k=1,2…s,每層簇首節(jié)點數(shù)為mk,k=1,2…s,每個數(shù)據(jù)包長度為l比特。我們假設簇內節(jié)點的數(shù)據(jù)可以百分百的融合,而簇間的數(shù)據(jù)則不作融合處理。首先來考慮僅有一層的情況,且假設所有節(jié)點距離Sink節(jié)點的距離都不超過d0。根據(jù)文獻、文獻和文獻的推導,我們可以得到此時的最優(yōu)簇首節(jié)點數(shù)為:由式(3)可見,對于僅有一層的情況,最優(yōu)簇首節(jié)點數(shù)只跟這一層的節(jié)點總數(shù)相關。根據(jù)我們的假設,我們的網(wǎng)絡是分層的,通過對層寬的調節(jié),可以保證,相鄰兩層的距離小于d0,外層的簇首節(jié)點可以選擇相鄰內層的簇首節(jié)點作為下一跳。如果把內層簇首節(jié)點看作是Sink節(jié)點,則最外層的最優(yōu)簇首節(jié)點數(shù)可以按照式(3)來進行計算。內層簇首除了要負擔本層簇內節(jié)點的數(shù)據(jù)通信外,還要擔任外層簇首的中繼節(jié)點,這時外層簇首節(jié)點可以看成是內層簇首節(jié)點的普通節(jié)點,但是在簇間數(shù)據(jù)不作融合處理的情況下,外層簇首節(jié)點應該相當于兩個普通節(jié)點。因為在d不是很大的情況下:設最外層最優(yōu)簇首節(jié)點個數(shù)占總本層節(jié)點總數(shù)的比例為kopt,如果網(wǎng)絡的最大層寬為s,那么對于第s-1層來說,其最優(yōu)簇首節(jié)點數(shù)滿足下式要求:如果我們忽略掉kopt的三次及以上的項,則可以推導出第i層的近似最優(yōu)簇首節(jié)點數(shù):式中這個結論非常符合我們的直覺,因為多跳通信意味著越靠近Sink節(jié)點的簇首負擔越重,因而需要更多的簇首節(jié)點。一旦知道了每一層的最優(yōu)簇首節(jié)點所占的比例,就可以以此作為選舉門限,分布式的選舉簇首。1.3節(jié)點間節(jié)點連接的特點LBMC的成簇算法包括簇首選舉、簇內節(jié)點連接、簇首鏈的形成、簇首輪換等幾個步驟。具體規(guī)則如下:(1)簇首選舉我們采用類似LEACH算法的方式進行,但又有些不同。各層中節(jié)點以各自的隨機概率單獨進行簇首選舉,選舉的門限值為根據(jù)上一節(jié)的分析,每層的最優(yōu)簇首節(jié)點所占的比例為因此我們選擇選舉門限:這里要求知道網(wǎng)絡的最大層數(shù)s,這個參數(shù),可以根據(jù)事先的信息估算出來,在分層指令中發(fā)布到網(wǎng)絡中。每一層節(jié)點分別計算自己所在層的選舉門限,并隨機選舉。節(jié)點成為簇首之后,就以固定的功率廣播自己,等待簇內節(jié)點的加入。(2)簇內節(jié)點根據(jù)通信能耗最小原則選擇對應的簇首簇內節(jié)點根據(jù)接收的簇首節(jié)點的信號強弱來選擇信號最強的一個,因為簇首是以固定的功率廣播,通常情況下,接收信號越強,距離就越短,通信能耗就越低。在這里,我們并沒有要求某一層的節(jié)點只能連接到本層簇首。如圖2所示,節(jié)點n距離簇首chA更近,則選擇加入chA,而不是距離更遠的chB,盡管chA不在同一層,而chB則位于同一層。這樣可以最大限度的節(jié)約節(jié)點通信能耗。(3)簇首鏈的形成同樣的,外層簇首根據(jù)能耗最優(yōu)原則選擇下一跳。簇首選擇或者輪換完成后,就會從最內層,即接近Sink節(jié)點的簇首開始計算自己到Sink的距離。當然,這個根據(jù)接收信號強度計算出來的距離只是大致距離,但是用來選擇下一跳已經(jīng)足夠了。根據(jù)文獻的無線信道能量衰減模型結合文獻的實際測量結果,在假設信號傳播距離1m后能量與初始能量相同并忽略其他一些因素后,接收功率PR、發(fā)射功率pT和節(jié)點間距離d的關系可用下式近似:式中η為路徑衰減系數(shù),取值在2~5之間。由式(9)可得:要使所有的簇首都能選擇最合理的一個路徑,距離估算需要從最內層開始,最內層簇首節(jié)點到Sink的距離可以根據(jù)式(10)直接計算出來。從第二層開始,如果不是直接與Sink節(jié)點通信,則距離可以如下計算:式中di,j為節(jié)點i到節(jié)點j之間的距離,可以根據(jù)式(10)計算出來,dj表示節(jié)點j到Sink節(jié)點的距離,表示轉發(fā)代價。節(jié)點i比較所有的內層節(jié)點包括Sink的通信距離(這個距離即代表了通信能耗代價),選擇最小的節(jié)點,作為它的下一跳。這樣由內而外,由近及遠,很快就能建立起最優(yōu)的簇首鏈。之后就可以進行數(shù)據(jù)傳輸。(4)簇首的輪換規(guī)則LEACH、SEP等協(xié)議,需要每一輪都重新選舉簇首,會消耗比較多的能量。針對這一點,LBMC算法并不是每一輪都重新選舉簇首,而是在一定的輪數(shù)之內,由本輪簇首來指定下一輪的簇首。本輪簇首根據(jù)剩余能量最大原則來選擇下一輪簇首。這樣剩余能量大的節(jié)點可以更多的擔任簇首節(jié)點,從而從整體上平衡能量消耗。但有時會發(fā)生剩余能量多的節(jié)點集中到某一塊區(qū)域的情況,這樣就會造成簇首分布不均勻的問題,因此每隔一定的輪數(shù),需要重新進行簇首選舉。(5)邊緣節(jié)點的連接對于某些邊緣節(jié)點,所有簇首節(jié)點都不在它的通信范圍之內,如果不采取措施,必然會使網(wǎng)絡的連通性降低。這里引入虛擬簇首節(jié)點的概念,虛擬簇首節(jié)點并不是真正的簇首節(jié)點,它只作為某些邊緣節(jié)點與簇首節(jié)點之間通信的中間節(jié)點。節(jié)點在找不到簇首節(jié)點的情況下,會試著尋找已存在的虛擬簇首節(jié)點,如果都找不到,則選擇某一通信范圍內的簇內節(jié)點相連,該簇內節(jié)點同時成為虛擬簇首。邊緣節(jié)點選擇某簇內節(jié)點與其相連的概率為即選擇通信能耗最低的節(jié)點為虛擬簇首。1.4網(wǎng)絡分層控制LBMC算法的執(zhí)行步驟如下:(1)節(jié)點初始化,Sink節(jié)點向網(wǎng)絡發(fā)送網(wǎng)絡配置參數(shù):層寬調節(jié)參數(shù)Rp、最外層簇首選舉門限Ts、最大層數(shù)s、循環(huán)輪數(shù)C,并發(fā)起網(wǎng)絡分層指令。(2)節(jié)點分層。(3)各層根據(jù)本層的簇首選舉門限,隨機選舉簇首。(4)網(wǎng)絡中非簇首節(jié)點選擇相應的簇首節(jié)點并與其連接,當有邊緣節(jié)點存在時,需選擇虛擬簇首節(jié)點。簇首節(jié)點形成簇首鏈。(5)當一個簇的生命周期完成時,且小于預設的循環(huán)輪數(shù)C,則由簇首選擇某個簇內節(jié)點成為簇首,同時解散原簇并重新成簇。(6)當?shù)竭_循環(huán)輪數(shù)C時,重復進行步驟(3)到(6)的過程。2仿真結果與分析仿真實驗對LEACH、SEP、HEED和本文提出的LBMC算法進行了分析和比較。仿真環(huán)境為Matlab,仿真重點為不同算法的網(wǎng)絡存活時間和節(jié)點的能耗。前三種算法專注于簇首節(jié)點的選舉問題,因此不適用于大范圍的網(wǎng)絡,為此,我們將LBMC的分層算法和簇間路由算法分別加入進去,使之都成為多跳路由算法,擴展其網(wǎng)絡范圍。其中LEACH、SEP采用文獻中使用的參數(shù),HEED采用文獻中使用的參數(shù)。本文對總節(jié)點數(shù)為100,事件區(qū)域范圍為100m×100m到400m×400m的場景進行了仿真。節(jié)點參數(shù)如下表1所示。圖3是100m×100m時,每一輪簇首節(jié)點的平均剩余能量,從中可以看出,LBMC的簇首具有更高的剩余能量,且越大后邊差距越大,說明LBMC具有比其他三個協(xié)議更好的能量效率。圖4和圖5是100m×100m和400m×400m時,網(wǎng)絡生存時間的比較,橫軸的代表網(wǎng)絡生存時間的周期數(shù),縱軸則是存活的節(jié)點數(shù)。從中可以看出,SEP相比LEACH的提高很少,HEED則有很大的提高,而LBMC則提高更多。因為LBMC和HEED使網(wǎng)絡的能耗更加均勻,網(wǎng)絡的中節(jié)點的死亡相當集中,從第一個節(jié)點死亡到最后一個節(jié)點死亡的時間非常接近。圖4和圖5是LBMC、SEP、LEACH、HEED4個協(xié)議的穩(wěn)定生存周期(即第一個節(jié)點死亡之前的運行周期)的比較。從圖中可以看出,當場地大小從100m×100m到400m×400m變化時,所有的協(xié)議的穩(wěn)定周期都下降了,但是LBMC的穩(wěn)定周期明顯比其他三個協(xié)議要長,且場地越大差距越大,同樣說明了LBMC有著更好的能量效率。圖6是隨著場地范圍的擴大,4種協(xié)議的網(wǎng)絡穩(wěn)定生存周期的變化,從圖中可以看出,LBMC比其他三種協(xié)議有更長的穩(wěn)定生存周期,即網(wǎng)絡完整工作的時間比其他三種協(xié)議要長。圖7是基站接收到的的數(shù)據(jù)包的總量,結合圖4和圖5可以看出,雖然SEP和LEACH的最后的生存周期比HEED和LB-MC的要長,但其傳輸?shù)目偟臄?shù)據(jù)包量并沒有比HEED和LBMC的多,這是因為由于SEP和LEACH本身協(xié)議存在一些缺陷,即當節(jié)點數(shù)很少時,會出現(xiàn)沒有簇首的情況,這時候數(shù)