WSN 中基于非均勻梯度的分簇拓撲算法

閻新芳，張永坤，李 騰，王曉曉

(1．鄭州大學 信息工程學院，河南 鄭州450001;2．北京郵電大學 信息與通信工程學院，北京100876)

0 引言

路由技術(shù)是無線傳感網(wǎng)(Wireless Sensor Network，WSN)的一個關(guān)鍵技術(shù)，而目前WSN 發(fā)展最大的瓶頸就是節(jié)點能量有限且不易補充．因此，避免不必要的通信、均衡整個網(wǎng)絡(luò)的能耗成為路由協(xié)議設(shè)計的關(guān)鍵因素［1-2］． 基于分簇的層次路由算法由于其能量高效且易于擴展而被廣泛研究和應(yīng)用［3-6］．其中，文獻［6］提出一種基于能量的分級簇算法ETBG(Energy-Aware Topology Protocol Based on Gradient)算法，該算法參考定向擴散協(xié)議中梯度的思想，根據(jù)節(jié)點的通信半徑把網(wǎng)絡(luò)建成一個梯度場，以減少分級簇等級和數(shù)據(jù)分組轉(zhuǎn)發(fā)跳數(shù)，降低延遲時間，同時延長網(wǎng)絡(luò)生存周期．ETBG［7-8］是分布式、異步并行算法，但存在如下問題:靠近基站的簇首由于轉(zhuǎn)發(fā)大量數(shù)據(jù)而負載過重，可能過早耗盡能量而失效．

為解決這個問題，筆者提出了一種基于梯度的分簇拓撲算法CTAUG(a Clustering Topology Algorithm Based on Uneven Gradient in WSN)，即將網(wǎng)絡(luò)劃分為依次遞增的非均勻梯度，并對簇成員入簇的策略進行改進，使得靠近基站的簇的規(guī)模小于遠離基站的簇的規(guī)模，從而使靠近基站的簇頭可以為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留更多能量，延長網(wǎng)絡(luò)的生存周期．

1 基于非均勻梯度的分簇算法

無線傳感器節(jié)點被隨機部署到目標區(qū)域以后，基站按照等差數(shù)列的方法將整個網(wǎng)絡(luò)以基站為圓心從近到遠，劃分為大小不等、依次遞增的非均勻梯度，并將梯度信息以一個初始化消息向全網(wǎng)廣播．網(wǎng)內(nèi)節(jié)點收到該消息后，開始執(zhí)行CTAUG 算法．

如圖1 所示，算法將時間劃分為輪，總體分為簇樹建立和數(shù)據(jù)傳輸兩個階段． 簇樹建立包括以下幾個過程:判斷梯度、構(gòu)建鄰居集、簇頭競爭、節(jié)點入簇、簇樹形成等．數(shù)據(jù)傳輸階段包括簇內(nèi)數(shù)據(jù)傳輸和簇間數(shù)據(jù)傳輸．

圖1 CTAUG 協(xié)議的生存時間劃分Fig．1 The divided of CTAUG agreement survival time

1．1 非均勻梯度的劃分

基站感知它到網(wǎng)絡(luò)的最遠距離和最近距離，分別記為dmax、dmin，然后以自己為圓心把網(wǎng)絡(luò)劃分為多個半徑不同的同心圓環(huán)梯度，最大半徑為Rmax(Rmax=dmax)，最小半徑為Rmin(Rmin=dmin)．基站規(guī)定圓環(huán)梯度層數(shù)L 及每個梯度的上界值UG 和下界值LG，把以基站為圓心，Rmin為半徑的圓定義為第0 梯度L0，然后把以半徑Rmin到Rmax的這個圓環(huán)劃分為大小不等、依次遞增的圓環(huán)梯度，劃分方法如下:

Rmax-Rmin=La1+L(L-1)r/2． (1)

其中，層數(shù)值L 和第1 層梯度的跨度a1均由基站決定，等差數(shù)列的差值r 在L、a1的值確定后，由式(2)可得．

r=2(Rmax-Rmin-La1)/(L-1)L． (2)

由此可得第i(i=2，…，L)層梯度的跨度:

ai=a1+(i-1)r=a1+

2(i-1)(Rmax-La1)/(L-1)L． (3)

假設(shè)LG1=Rmin，基站可采用以下公式計算每層梯度的上界值和下界值:

UGi=LGi+ai(i=1，…，L); (4)

LGi=UGi-1(i=2，…，L)． (5)

劃分成三層的非均勻梯度如圖2 所示．

圖2 非均勻梯度劃分示意圖Fig．2 Schematic division of uneven gradient

算法開始時，基站向全網(wǎng)廣播初始化消息INITMessage，消息格式如下．

各層上邊界:UGL，…，UG2，UG1(L≥2);各層下邊界:LGL，…，LG2，LG1(L≥2)．

1．2 簇樹建立階段

1．2．1 判斷梯度

收到基站發(fā)出的初始化消息后，各節(jié)點根據(jù)自己到基站的近似距離和初始化消息中各個梯度的上下邊界，計算得到自己的梯度等級和到自己所在梯度中心線的距離Dm．

1．2．2 構(gòu)建鄰居集

(1)第一次信息交互． 首先各個節(jié)點啟動定時器T1，開始以R 為功率半徑向其鄰居節(jié)點廣播當前狀態(tài)信息STATUSMessage，其中包括節(jié)點ID、當前剩余能量Er、梯度L、狀態(tài)status、到梯度中心線的距離Dm．然后將交互得到的鄰居信息保存在自己的鄰居集中，并對鄰居節(jié)點個數(shù)進行計數(shù)．

(2)綜合權(quán)值的計算． 在T1 計時結(jié)束之后，節(jié)點根據(jù)自己鄰居集中的信息開始計算自己的綜合權(quán)值W，其定義為

W=w1Er+w2/Nd+w3/Da+w4/Dm． (6)

式中:w1+w2+w3+w4=1;Er為節(jié)點剩余能量;Nd為節(jié)點鄰居節(jié)點數(shù)目;Da為到鄰居節(jié)點的平均距離;Dm為到節(jié)點所在梯度中心線的距離．

用層次分析法［9-10］來確定各自的權(quán)系數(shù)．此方法通過兩兩比較的方式確定諸因素的相對重要性，然后綜合人的判斷，決定諸因素總的順序．

(3)第二次信息交互． 節(jié)點計算好自己的綜合權(quán)值后，啟動定時器T2，進行第二次信息交互，將自己的綜合權(quán)值發(fā)送給所有的鄰居． 節(jié)點將所有鄰居第二次交互時發(fā)送來的綜合權(quán)值保存在自己的鄰居集中．

1．2．3 簇頭競爭

等鄰居集構(gòu)建完成后，節(jié)點將自己的綜合權(quán)值與鄰居節(jié)點的綜合權(quán)值進行比較，如果自己的權(quán)值是鄰居集中最大的，就宣布自己是簇頭，并向周圍鄰居節(jié)點廣播簇頭消息HEADMessage，這樣就選出了部分在鄰居節(jié)點中綜合權(quán)值最大的節(jié)點為簇頭節(jié)點．

1．2．4 節(jié)點入簇

此階段節(jié)點啟動定時器T3，開始接收鄰居簇頭發(fā)來的簇頭消息HEADMessage，并將其保存在自己的簇頭列表中．

在T3 計時結(jié)束后，節(jié)點如果只收到一個簇頭消息，就直接加入該簇頭所在的簇中，并向其發(fā)送JOINMessage;如果收到兩個或兩個以上的簇頭消息，則優(yōu)先選擇加入到梯度較大的簇頭中，并向其發(fā)送JOINMessage;如果這幾個簇頭在同一梯度中，則優(yōu)先加入到剩余能量較大的簇頭中，并向該簇頭發(fā)送JOINMessage;如果沒有收到簇頭消息，且鄰居中綜合權(quán)值比自己大的節(jié)點狀態(tài)都已經(jīng)確定，則宣布自己成為簇頭，并向鄰居節(jié)點中比自己權(quán)值小的節(jié)點廣播簇頭消息HEADMessage． 否則，繼續(xù)等待并接收來自鄰近節(jié)點發(fā)來的消息，直到分簇完成．

考慮到WSN 中節(jié)點與基站直接通信的能耗和其先將數(shù)據(jù)發(fā)送到簇頭再轉(zhuǎn)發(fā)到基站的能耗相近，則讓這些節(jié)點與基站直接通信不僅可以減少在數(shù)據(jù)轉(zhuǎn)發(fā)中產(chǎn)生的額外負載，也減少了靠近基站的簇頭的簇成員數(shù)量，從而可以為數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留更多的能量．因此該算法擬讓能與基站通信的節(jié)點直接與基站進行通信，其他節(jié)點則按照以上方法入簇，分簇完成后，按照ETBG 算法形成簇樹．

1．3 特例說明

特例:假設(shè)在一個100 m×100 m 的區(qū)域內(nèi)隨機拋灑50 個傳感器節(jié)點，采用參考文獻［3］所示能量模型，最大通信半徑R =30 m，梯度層數(shù)L =3，第一層梯度的跨度a1=20 m．

圖3 為算法改進前后的分簇對比圖． 由圖3(b)和圖3(a)可以看出:圖3(b)中產(chǎn)生的簇頭兼顧剩余能量的同時，更接近所在梯度的中心，且更靠近簇的質(zhì)心位置．

由圖3(c)和圖3(b)可以看出:圖3(c)中的灰色節(jié)點14，23，30，27，8，35，47，49，3，40，6，42，29，21 按照優(yōu)化的規(guī)則選擇了加入梯度較大、剩余能量更多的簇頭節(jié)點，而白色節(jié)點依然保留在原來的簇中．例如:節(jié)點39 只收到簇頭9 發(fā)來的簇頭消息，則依然保留在原來的簇中;節(jié)點35 收到兩個簇頭46，48 發(fā)來的簇頭消息，選擇梯度更高的48 作為自己的簇頭;節(jié)點8 收到3 個簇頭9，13，36 發(fā)來的簇頭消息，其中13 的梯度比自己低，而9，36 和自己同一梯度，因此選擇剩余能量更多的36 作為自己的簇頭．

圖3 算法改進前后的分簇對比圖Fig．3 Comparison chart of before and after algorithm optimization

圖3(d)和圖3(c)還可以看出:圖3(d)中的三角形節(jié)點44，43，2，5，40，6，38 按照優(yōu)化的規(guī)則直接與基站進行通信．

2 性能分析

2．1 梯度層數(shù)對生存期的影響

設(shè)定簇頭輪換頻率為1 500 輪/次，通信半徑為30 m，所有仿真結(jié)果都是模擬10 次的均值，圖4 為梯度層數(shù)L 的變化對網(wǎng)絡(luò)生存期的影響．

從圖4 可以看出:兩種算法的生存期都在L=2 時最短及L =3 時最長;隨著L 值繼續(xù)增大，生存期慢慢變短，曲線成山峰型．這是因為當L 值較小即梯度層數(shù)較少時，最外層的簇首的成員過多，簇內(nèi)通信能耗增大，節(jié)點過早死亡;而當L 值較大即梯度層數(shù)較多時，各層跨度變窄，非均勻程度降低，簇間路由增多，導致靠近基站的簇頭容易過早死亡．

圖4 不同梯度的生存期對比圖Fig．4 Lifetime versus layers of gradient

2．2 簇首消耗的能量之和

簇頭輪換頻率設(shè)定為1 500 輪/次，梯度層數(shù)L=3，節(jié)點個數(shù)分別為20，40，…，180，200，從實驗中隨機選取10 輪，統(tǒng)計各輪中所有簇頭消耗的能量，結(jié)果如圖5 所示．

圖5 不同節(jié)點個數(shù)時每輪所有簇首消耗能量對比圖Fig．5 Average energy dissipation versus nodes’number

從圖5 可以看出，隨著區(qū)域內(nèi)節(jié)點個數(shù)的增加，節(jié)點也越來越密集，相應(yīng)的簇頭的任務(wù)也更加繁重，簇首所消耗的總能量隨之快速增加． 但在CTAUG 算法中由于靠近基站的節(jié)點直接與基站通信，其余節(jié)點優(yōu)先加入梯度等級較高、剩余能量較大的簇頭所在的簇中，因此CTAUG 算法中每輪所有簇頭的能耗仍大大低于ETBG 算法中每輪所有簇頭的能耗．

3 結(jié)論

通過研究ETBG 算法中存在的“熱區(qū)”問題，提出了一種基于非均勻梯度的分簇拓撲結(jié)構(gòu)算法CTAUG．該算法綜合考慮節(jié)點剩余能量、鄰居節(jié)點個數(shù)、到鄰居節(jié)點之間距離的平均值和到梯度中心線的距離等因素構(gòu)造綜合權(quán)值，且用層次分析法來確定各個因素的權(quán)系數(shù)，使生成的簇頭分布更加合理．另外，該算法劃分了非均勻梯度，使靠近基站的節(jié)點直接與基站通信，其余節(jié)點則優(yōu)先加入梯度較大、剩余能量較多的簇頭所在的簇中，有效解決“能量空洞”問題，延長了網(wǎng)絡(luò)的生存期，適用于大規(guī)模的網(wǎng)絡(luò)．

［1］ AKKAYA K，YOUNIS M．A survey on routing protocols for wireless sensor network［J］． Ad Hoc Networks，2005，3(3):325 -349．

［2］ JAMAL N A，AHNED E K． Routing techniques in wireless sensor networks:a survey［J］．IEEE Wireless Communication，2004，11(6):6 -28．

［3］ HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H． An application-specific protocol architecture for wireless microsensor network［J］． Wireless Communication，2002，1(4):660 -670．

［4］ MANJESHWAR A，AGRAWAL D P．TEEN:A routing protocol for enhanced efficiency in wireless sensor networks［C］//IEEE Conference Proceedings on Parallel and Distributed Processing． San Francisco CA，USA:IEEE Press，2001:2009 -2015．

［5］ LINDSEY S，RAGHAVENDRA C S．PEGASIS:Powerefficient gathering in sensor information systems［C］//IEEE Conference Proceedings on Aerospace． Los Angeles，CA，USA:IEEE Press，2002:1125-1130．

［6］ AN Na，YAN Xin-fang，ZHU Yu-fang，et al． A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks［C］//The IET International Communication Conference on Wireless Mobile and Sensor Networks． Shanghai，China:IET Press，2007:462 -465．

［7］ 閻新芳，段磊，李騰．無線傳感網(wǎng)中基于梯度的拓撲控制算法［J］． 計算機工程與應(yīng)用，2011，47(2):95 -98．

［8］ 閻新芳，王志龍，閆新生，等．WSN 中基于梯度場拓撲控制算法的維護更新［J］． 傳感器與微系統(tǒng)，2011，30(8):56 -58．

［9］ SAATY T L．The analytic hierarchy process［M］． New York:McGraw-Hill，1980:180 -230．

［10］KWANG E Y，YOUN C C． Analytic hierarchy process approach for identifying relative importance of factors to improve passenger security checks at airports［J］． Air Transport Management，2006，12(3):135 -142．