一種基于無線傳感器網(wǎng)絡(luò)分簇路由的改進算法

郭文強， 周 強， 侯勇嚴， 王阿娟

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安 710021)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，簡稱WSN)是由一組傳感器以自組織方式構(gòu)成的無線網(wǎng)絡(luò),它由一定數(shù)目的傳感器節(jié)點構(gòu)成[1].WSN綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)，能協(xié)作地實時監(jiān)測、感知和采集節(jié)點部署區(qū)域的各種環(huán)境或監(jiān)測對象的信息(如光強、溫度、濕度、噪音和有害氣體濃度等物理現(xiàn)象)，并對這些數(shù)據(jù)進行處理，獲得詳盡而準確的信息，通過無線網(wǎng)絡(luò)最終發(fā)送給觀察者[2-4].因而WSN具有十分廣闊的應(yīng)用前景，在軍事國防、工農(nóng)業(yè)、城市管理、生物醫(yī)療、環(huán)境監(jiān)測、搶險救災(zāi)、危險區(qū)域遠程控制等許多領(lǐng)域都具有重要的科研價值和巨大的實用價值，并成為近年來公認的熱點研究領(lǐng)域[5-8].

無線傳感器網(wǎng)絡(luò)中，節(jié)點的電源能量是有限的,所以基于能量角度設(shè)計有效的路由協(xié)議,是確保WSN網(wǎng)絡(luò)性能的關(guān)鍵技術(shù)之一.本文對當(dāng)前傳感器網(wǎng)絡(luò)路由算法進行了分析，針對具有不同初始能量節(jié)點的異構(gòu)WSN，提出了改進型SEP(Stable Election Protocol，穩(wěn)定選舉協(xié)議)路由算法，通過合理加權(quán)選擇簇頭，使剩余能量高的成為簇頭的概率加大、推遲了網(wǎng)絡(luò)第一個節(jié)點的死亡時間，延長了網(wǎng)絡(luò)運行的穩(wěn)定期.

1 LEACH路由算法

無線傳感器網(wǎng)絡(luò)是一種由大量小型傳感器所組成的網(wǎng)絡(luò).這些小型傳感器一般稱作傳感器節(jié)點.網(wǎng)絡(luò)中一般也有一個或幾個基站(Sink)用來集中從小型傳感器收集的數(shù)據(jù).在WSN中，節(jié)點需要完全以自組織的形式構(gòu)成自治型網(wǎng)絡(luò)，并且能夠工作在無人值守的惡劣環(huán)境當(dāng)中.

LEACH(Low-energy Adaptive Clustering Hierarchy，低功耗自適應(yīng)聚類分層)是一個提出較早的基于分簇思想的WSN層次路由算法[9].與傳統(tǒng)網(wǎng)絡(luò)中網(wǎng)關(guān)節(jié)點的能量較充足相比，WSN中的節(jié)點能量有限，故不能用固定簇頭節(jié)點作為網(wǎng)關(guān).LEACH從WSN中隨機選擇少數(shù)節(jié)點作簇頭，考慮到網(wǎng)絡(luò)中各節(jié)點能耗的平衡性，節(jié)點輪流作為簇頭，使網(wǎng)絡(luò)不會因少數(shù)節(jié)點先耗盡能量而造成網(wǎng)絡(luò)癱瘓.

1.1 能耗模型

假設(shè)發(fā)送的能量包括信號處理與功率放大兩部分,接收的能量僅用于信號處理, 使用接近中心的距離d0作為參考, 并且假設(shè)兩節(jié)點之間的距離d小于d0時采用自由空間模型,大于等于d0時采用多徑衰減模型[10].LEACH 算法的無線信道能量模型如圖1所示.

圖1 WSN信道能量模型

圖1中當(dāng)兩個距離為d的節(jié)點之間發(fā)送l比特數(shù)據(jù)時, 發(fā)送和接收所消耗的能量分別為:

ETx(l,d)=ETx-ele(l)+ETx-amp(l,d)

(1)

ERx(l)=lEelec

(2)

其中，Eelec是信號處理所需能量, 由數(shù)字編碼、調(diào)制、濾波和擴展信號等因素決定；εfs是自由空間信道模型下功率放大器的能量消耗常數(shù)；εmp是多徑衰減信道模型下功率放大器的能量消耗常數(shù),它們由放大器功耗、發(fā)射距離和接收誤碼率等決定.

1.2 路由協(xié)議的分析

LEACH定義了“輪”(round)的概念，每一輪由簇頭建立和穩(wěn)定工作兩個階段組成.前者是LEACH算法實現(xiàn)的關(guān)鍵，后者是數(shù)據(jù)傳輸?shù)谋ＷC.LEACH主要通過隨機選擇聚類首領(lǐng),平均分擔(dān)中繼通信業(yè)務(wù)來實現(xiàn)網(wǎng)絡(luò)服務(wù).為了避免額外的處理開銷,穩(wěn)定工作階段一般持續(xù)相對較長的時間.

在簇頭建立階段，傳感器節(jié)點生成0與1之間的隨機數(shù)rand.如果隨機數(shù)小于閾值T(n)，則該節(jié)點成為這一輪的一個簇頭.用G表示最后的1/p輪中沒有被選為簇頭的節(jié)點集合，p表示簇頭節(jié)點濃度(如5%)，則T(n)為：

(3)

其中，r是當(dāng)前的輪數(shù)；G是在前1/p輪中未充當(dāng)過簇頭節(jié)點的集合.

當(dāng)簇頭選定之后，簇頭節(jié)點主動向網(wǎng)絡(luò)中節(jié)點廣播自己成為簇頭的消息(ADV_CH).接收到此消息的節(jié)點，依據(jù)接收信號的強度，選擇它所要加入的簇，并發(fā)消息通知相應(yīng)的簇頭(JOIN_REQ).基于時分多址(Time Division Multiple Address，簡稱TDMA)的方式，簇頭節(jié)點為其中的每個成員分配通信時隙，并以廣播的形式通知所有的簇內(nèi)節(jié)點.這樣保證了簇內(nèi)每個節(jié)點在指定的傳輸時隙進行數(shù)據(jù)傳輸，而在其他時間進入休眠狀態(tài)，減少了能量消耗.在穩(wěn)定工作階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，在自身傳輸時隙到來時把監(jiān)測數(shù)據(jù)傳給簇頭節(jié)點.簇頭節(jié)點對接收到的數(shù)據(jù)進行融合處理之后，發(fā)送到Sink節(jié)點，這是一種減小通信業(yè)務(wù)量的合理工作模式.持續(xù)一段時間以后，整個網(wǎng)絡(luò)進入下一輪工作周期，重新選擇簇頭節(jié)點.

LEACH協(xié)議采用動態(tài)轉(zhuǎn)換簇頭的方法來平均網(wǎng)絡(luò)節(jié)點的能量消耗，使因能量耗盡而失效的節(jié)點呈隨機分布狀態(tài).因而與一般的多跳路由協(xié)議和靜態(tài)簇算法相比，LEACH可以將網(wǎng)絡(luò)生命周期延長15%.LEACH的分簇機制可降低網(wǎng)絡(luò)的整體能耗，延長網(wǎng)絡(luò)生存時間；在簇內(nèi)節(jié)點間通常采用TDMA編碼[11]，在簇頭與基站間采用CDMA編碼，保證信息有效傳輸；數(shù)據(jù)采集和簇頭節(jié)點都是周期性的，網(wǎng)絡(luò)適合監(jiān)測連續(xù)變化事件.

2 SEP路由算法

LEACH路由算法假定所有的節(jié)點都配備了相同數(shù)量的能量，因此，它們不能充分利用節(jié)點異質(zhì)性的存在.為了延長網(wǎng)絡(luò)穩(wěn)定期，SEP協(xié)議中路由算法對能源消耗進行約束，試圖均衡能源消耗.SEP協(xié)議中高級節(jié)點(初始能量高的節(jié)點)成為簇頭的概率大于普通的節(jié)點(初始能量低的節(jié)點).

SEP協(xié)議假定每個節(jié)點通過通信知道網(wǎng)絡(luò)的總能量，然后根據(jù)節(jié)點的剩余能量計算出其成為簇頭的最佳概率.運行之初根據(jù)經(jīng)驗值設(shè)定了最優(yōu)概率Popt，并引入Pnrm為普通節(jié)點加權(quán)選舉的概率，Padv為高級節(jié)點加權(quán)選舉的概率[6].其中：

(4)

(5)

其中，a為高級節(jié)點的初始能量多于普通節(jié)點初始能量的倍數(shù)，m為高級節(jié)點在總節(jié)點數(shù)中所占比例.普通節(jié)點與高級節(jié)點成為簇頭的閾值分別為T(snrm) 和T(sadv)，計算公式如下：

(6)

(7)

其中，r是當(dāng)前輪數(shù)；G1和G2是相應(yīng)的在前1/p輪中未充當(dāng)過簇頭節(jié)點的集合.

3 改進型SEP路由算法

在SEP路由算法中的第r輪簇頭選舉時，若存在關(guān)系隨機數(shù)randr

(8)

其中，Er,left為第r輪時節(jié)點的剩余能量;Eini為節(jié)點的初始化能量.則第r輪簇頭選舉時，隨機數(shù)按下式確定：

randr=rand*Cr

(9)

分析可知: 參數(shù)Cr為一個考慮節(jié)點剩余能量因素的動態(tài)變量.當(dāng)節(jié)點剩余能量較大，對應(yīng)的隨機數(shù)randr會相應(yīng)地減小，從而提高了其當(dāng)選為簇頭的概率，減少了普通節(jié)點當(dāng)選為簇頭引起的因能量過早耗盡而造成的數(shù)據(jù)丟失.

改進型SEP協(xié)議能夠適用于節(jié)點能量不同的網(wǎng)絡(luò)，可以有效避免能量過低的節(jié)點當(dāng)選為簇頭，協(xié)議可以延長第一個節(jié)點的死亡時間，即網(wǎng)絡(luò)穩(wěn)定期，而這對于許多網(wǎng)絡(luò)應(yīng)用來講至關(guān)重要.

4 仿真實驗與性能分析

4.1 實驗環(huán)境

為了驗證本文提出的改進型SEP協(xié)議的有效性，在相同無線傳感器網(wǎng)絡(luò)條件下分別采用LEACH協(xié)議、SEP協(xié)議和改進型的SEP協(xié)議進行了大量的仿真對比實驗.在PC 機(奔騰 2.5GHz CPU, 2G 內(nèi)存)上采用Matlab 7.1完成如下仿真實驗.

具體仿真環(huán)境參數(shù)如下: 區(qū)域大小為100 m×100 m 正方形區(qū)域，節(jié)點數(shù)量為100，基站在網(wǎng)絡(luò)區(qū)域中心.普通節(jié)點能量Eo為0.5 J；高級節(jié)點所占比例m為0.1，其所含能量為普通節(jié)點的(1+a)倍.實驗中a取1.

數(shù)據(jù)包和控制包長度為4 000 byte，Eelec為50 nJ /bit，εfs為10 pJ/( bit /m2) 、εmp為0.001 3 pJ/( bit /m4)，節(jié)點數(shù)據(jù)處理能耗為5 nJ /bit /singal.

4.2 性能分析

圖2所示為WSN運行LEACH協(xié)議初始節(jié)點狀態(tài).圖中“x”代表基站，“+”代表高級節(jié)點，“o”代表普通節(jié)點，“*”代表節(jié)點為簇頭，“·”代表已經(jīng)死亡節(jié)點.

圖2 LEACH協(xié)議運行初始網(wǎng)絡(luò)節(jié)點狀態(tài)

WSN分別運行LEACH協(xié)議、SEP協(xié)議和改進型SEP協(xié)議至第1 050輪時節(jié)點狀態(tài)如圖3至5所示.

圖3 LEACH協(xié)議運行1 050輪時網(wǎng)絡(luò)節(jié)點狀態(tài)

圖4 SEP協(xié)議運行1 050輪時網(wǎng)絡(luò)節(jié)點狀態(tài)

圖5 改進型SEP協(xié)議運行1 050輪時網(wǎng)絡(luò)節(jié)點狀態(tài)

對比可知：協(xié)議至第1 050輪時，SEP協(xié)議存活節(jié)點的數(shù)量明顯多于LEACH協(xié)議(“·”節(jié)點相對較少).這是由于在LEACH協(xié)議中每個節(jié)點成為簇頭的概率是完全一樣的，而普通節(jié)點由于初始能量較少所以死亡的可能性也更大；改進型SEP協(xié)議存活節(jié)點明顯多于SEP協(xié)議，是因為改進型SEP算法能夠在能量異構(gòu)的網(wǎng)絡(luò)模式下，使剩余能量較高的節(jié)點當(dāng)選為簇頭的概率得以增加，有效地均衡了網(wǎng)絡(luò)中的節(jié)點能耗.

圖6 不同協(xié)議下網(wǎng)絡(luò)節(jié)點存活數(shù)量對比

WSN分別運行LEACH協(xié)議、SEP協(xié)議和改進型SEP協(xié)議10次，網(wǎng)絡(luò)中平均存活節(jié)點數(shù)對比情況如圖6所示.分別采用LEACH算法、SEP算法和改進型SEP算法后，網(wǎng)絡(luò)中出現(xiàn)第1 個死亡節(jié)點的代數(shù)分別為902、1026和1078.實驗表明，改進型算法明顯地延長了網(wǎng)絡(luò)中出現(xiàn)第1 個死亡節(jié)點的時間，延長了網(wǎng)絡(luò)的生命周期，從而提高了網(wǎng)絡(luò)的性能.

5 結(jié)束語

通過對無線傳感器網(wǎng)絡(luò)路由協(xié)議中的LEACH算法和SEP算法的機理分析，提出了改進型SEP算法.大量實驗結(jié)果表明，改進型SEP算法在能量異構(gòu)的網(wǎng)絡(luò)模式下，通過改進選舉簇頭機制，提高了剩余能量較高的節(jié)點當(dāng)選為簇頭的概率，增加了選舉簇頭節(jié)點的合理性，有效地均衡了網(wǎng)絡(luò)中的節(jié)點能耗，提高了網(wǎng)絡(luò)中能量的利用效率，從而更好地延長了網(wǎng)絡(luò)的生命周期.

[1] K.W.Chin.Pairwise:A time hopping medium access control protocol for wireless sensor networks[J].IEEE Transactions on Consumer Electronics,2009,55(4):1 898-1 906.

[2] P.Baldi,L.D.Nardis,M.D.Benedetto.Modeling and optimization of UWB communication networks through a flexible cost function[J].IEEE Journal on Selected Areas in Communications,2006,20(9):1 733-1 744.

[3] N.Saputro,K.Akkaya,S.Uludag.A survey of routing protocols for smart grid communications[J].Computer Networks,2012,56(11):2 742-2 771.

[4] A.A.Cardenas,T.Roosta,S.Sastry.Rethinking security properties, threat models, and the design space in sensor networks:A case study in SCADA systems[J].Ad Hoc Networks,2009,7(8):434-1447.

[5] 陶志勇，胡 明，方寧.無線傳感器網(wǎng)絡(luò)的分簇時間同步算法研究[J].計算機測量與控制,2012,20(7):2 010-2 013.

[6] 郭文強,張玉杰,侯勇嚴,等.無線傳感器網(wǎng)絡(luò)在環(huán)境監(jiān)測系統(tǒng)中的設(shè)計與應(yīng)用[J].陜西科技大學(xué)學(xué)報，2012,30(4):81-84,89.

[7] 蹇 強，龔正虎，朱培棟，等.無線傳感器網(wǎng)絡(luò)MAC 協(xié)議研究進展[J].軟件學(xué)報,2008,19(2):389- 403.

[8] T. Westeyn,G.Abowd,T.Starner,et al.Monitoring children′s developmental progress using augmented toys and activity recognition[J].Personal and Ubiquitous Computing,2012,16(2):169-191.

[9] 呂 濤，朱清新，張路橋.一種基于LEACH協(xié)議的改進算法[J].電子學(xué)報, 2011,39(6)：1 405-1 409.

[10] W.B.Heinzelman，A.P.Chandrakasan，H．Balakrishnan. An application-specific protocol architecture for wireless micro-sensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660- 670．

[11] S.Coleri-Ergen,P.Varaiya.Pedamcs:Power efficient and delay aware medium access protocol for sensor networks[J].IEEE Trans.on Mobile Computing,2006,5(7):920-930.