連通和覆蓋性優(yōu)化無線傳感器網(wǎng)絡(luò)壽命的方法

曲家慶，張曙

(1.哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001;2.上海航天技術(shù)研究院802所，上海 200090)

無線傳感器網(wǎng)絡(luò)是由微小的傳感器節(jié)點借助無線通信以自組織方式構(gòu)成的數(shù)據(jù)采集網(wǎng)絡(luò)［1］.基站通過散布在監(jiān)控區(qū)域的若干傳感器節(jié)點間的聯(lián)絡(luò)，回收場景中的信息.由于傳感器節(jié)點的能量、資源、通信能力都十分有限，因此如何充分利用節(jié)點能量提高網(wǎng)絡(luò)壽命成為當(dāng)前無線傳感器網(wǎng)絡(luò)研究的重要課題之一［2］.

Chang等［3］建立了線性規(guī)劃模型優(yōu)化無線傳感器網(wǎng)絡(luò)壽命.文獻(xiàn)［4］應(yīng)用上述模型基于帕蕾托最優(yōu)理論提出一種優(yōu)化網(wǎng)絡(luò)壽命的方法.但文獻(xiàn)［3－4］都沒考慮節(jié)點的覆蓋冗余，全部節(jié)點同時工作將增加感知信息的冗余度，增加網(wǎng)絡(luò)能量的損耗，降低節(jié)點能量的有效性.更重要的是隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加，線性規(guī)劃過程計算復(fù)雜度將不可接受.為此，采用節(jié)點休眠調(diào)度機制來優(yōu)化網(wǎng)絡(luò)壽命，在不降低系統(tǒng)性能的前提下，僅保留部分節(jié)點采集信息，將大部分節(jié)點轉(zhuǎn)入低功耗的休眠狀態(tài).Xing等［5］提出覆蓋配置協(xié)議(coverage configuration protocol，CCP)，通過求解感知圓與場景邊界和感知圓之間交點給出了凸區(qū)域被工作節(jié)點集合k度覆蓋的充分條件，算法復(fù)雜度為O(N3).Carbunar等［6］提出基于Voronoi圖的冗余節(jié)點休眠算法(redundant sensor elimination，RSE)，傳感器節(jié)點通過判斷它的全部2－Voronoi頂點和2－Voronoi交點是否被其鄰居節(jié)點覆蓋來判斷冗余性，復(fù)雜度為O(NlnN).但文獻(xiàn)［5－6］沒有考慮節(jié)點的連通冗余，把通信半徑設(shè)置為感知半徑的2倍.通過節(jié)點對場景的完全覆蓋來保證節(jié)點間的連通性，這必然增加不必要的網(wǎng)絡(luò)能量損耗.

基于以上分析，本文提出一種將節(jié)點的休眠調(diào)度機制與高效的路由策略相結(jié)合的優(yōu)化無線傳感器網(wǎng)絡(luò)壽命的新方法CCLO(connectivity and coverage for network lifetime optimization).

1 網(wǎng)絡(luò)模型及問題描述

無線傳感器網(wǎng)絡(luò)G=(V，E)，V是節(jié)點集，E是邊集.對vi，vj∈V，eij∈E當(dāng)且僅當(dāng)vi，vj能進(jìn)行信息交換.N個節(jié)點被隨機均勻地拋灑到Z=m×n的區(qū)域中，節(jié)點具有相同的通信半徑Rc和感知半徑Rs，Ni和ni表示節(jié)點vi的通信鄰居和感知鄰居.節(jié)點vi每回合采集Ri數(shù)量的信息，以固定的發(fā)射功率通過多跳的方式發(fā)送給基站.基站是網(wǎng)絡(luò)中唯一的信宿，用v0表示，基站的能耗不予討論.基站通過GPS或者其他的定位算法［7］獲得節(jié)點的位置信息.

根據(jù)上述分析得到節(jié)點vi的能耗其中xij是vi向vj發(fā)送的信息數(shù)量，eij是節(jié)點收發(fā)單位信息時的能量損失系數(shù)［8］.節(jié)點的生存時間ti= Ei/ξi，Ei為vi的剩余能量.

定義1 連通圖:圖G=(V，E)中a，b∈V，若存在交替的頂點和邊序列Γ=(a=v0－e01－v1－e12－…－ek－vkk+1=y)，則a、b連通.如果?vi，vj∈V都是連通的，則G是連通圖.

定義2 完全覆蓋:工作節(jié)點集(work set，WS)完全覆蓋區(qū)域Z的充要條件:?P∈Z，?vi∈WS使vi覆蓋點P.

定義3 連通冗余節(jié)點:節(jié)點vi∈V休眠后，圖G仍然連通，則vi是連通冗余節(jié)點.

定義4 覆蓋冗余節(jié)點:節(jié)點vi∈V的感知區(qū)域Si?∪j∈WSSj能夠被工作節(jié)點集完全覆蓋，則Vi就是覆蓋冗余節(jié)點.

定義5 冗余節(jié)點:滿足連通冗余條件又滿足覆蓋冗余條件的節(jié)點.

定義6 網(wǎng)絡(luò)壽命:當(dāng)G不再連通時，網(wǎng)絡(luò)壽命終止.Tnetwork=Σ Tk，其中k是各階段的拓?fù)浣Y(jié)構(gòu)，Tk表示某一拓?fù)浣Y(jié)構(gòu)的工作時間.

2 CCLO算法

2.1 判別冗余節(jié)點

為降低覆蓋冗余節(jié)點判別過程中的復(fù)雜度，把節(jié)點感知圓盤的內(nèi)接正四邊形作為等效感知區(qū)域，得到等效感知半徑.如果|xi－xj|≤Rs'，|yi－yj|≤Rs'，則vj∈ni.

定理1:以節(jié)點vi為原點建立平面直角坐標(biāo)系，將其感知圓盤劃分成為Ⅰ、Ⅱ、Ⅲ、Ⅳ個象限.如果每個象限的等效感知區(qū)域中都至少存在一個感知鄰居，那么vi就是覆蓋冗余節(jié)點.

圖1 判別覆蓋冗余節(jié)點Fig.1 Identify the coverage redundant node

證明 如圖1所示，vj是vi的第Ⅰ象限內(nèi)的感知鄰居，0＜xj－xi≤Rs'，0＜yj－yi≤Rs'.顯然0＜xj－xi≤Rs'，0＜yj－yi≤Rs'，即vj能夠?qū)i第Ⅰ象限的等效感知區(qū)域完全覆蓋.K是等效感知區(qū)域外任意一點，(xk－xi)2+(yk－yi)2≤R2s.不妨設(shè)xk－xi＞Rs'，0＜yk－yi≤Rs'，得到djk=(xk－xj)2+(yk－yj)2=(xk－xi+xi－xj)2+(yk－xi+xi－yj)2＜R+R2'2－2(xk－xi)(xi－xj)－2(yk－yi)(yi－yj)＜R說明vj能將區(qū)域{(x，y)|x－xj＞Rs'，0＜y－yi≤Rs'完全覆蓋.同理vj也能將區(qū)域{(x，y)|0＜x－xi≤Rs'，y－yi＞Rs'}完全覆蓋.說明vj能夠?qū)i第Ⅰ象限的感知圓盤完全覆蓋.同理位于Ⅱ、Ⅲ、Ⅳ象限的感知鄰居也能將其Ⅱ、Ⅲ、Ⅳ象限的感知圓盤完全覆蓋.證畢.

定義7 邊界節(jié)點:如果節(jié)點的等效感知區(qū)域與場景邊界存在交點，那么這樣的節(jié)點就是邊界節(jié)點.

邊界節(jié)點冗余情況分析:

1)xi≤Rs':第Ⅰ象限的感知鄰居xj≤Rs'，如果xj≤Rs'，那么xi－Rs'≤xj－Rs'≤0，說明vj將vi的Ⅰ、Ⅱ完全象限;對第Ⅳ象限的感知鄰居如果xj－Rs'≤0，vj完全覆蓋vi的Ⅲ、Ⅳ象限.

2)m－xi≤Rs':第Ⅱ象限的感知鄰居vj，如果m－xj≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅱ象限;對第Ⅲ象限的感知鄰居，如果m－xj≤Rs'，vj完全覆蓋vi的Ⅲ、Ⅳ象限.

3)yi≤Rs':第Ⅲ象限的感知鄰居，如果yj≤Rs'，vj覆蓋vi的Ⅱ、Ⅲ象限;對第Ⅳ象限的感知鄰居如果yj≤Rs'時，vj覆蓋vi的Ⅰ、Ⅳ象限.

4)n－yi≤Rs':第Ⅱ象限的感知鄰居 vj，如果n－yj≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限;對第Ⅰ象限的感知鄰居vj如果n－yj≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅳ象限.

5)xi≤Rs'且yi≤Rs':①第Ⅰ象限的感知鄰居如果xj≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅱ象限.②第Ⅲ象限的感知鄰居如果yj≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.③第Ⅳ象限感知鄰居:xj≤Rs'且yj≤Rs'，vi成為冗余節(jié)點;xj≤Rs'且yj＞Rs'，vj完全覆蓋vi的Ⅲ、Ⅳ象限;xj＞Rs'且 yj≤Rs'，vj完全覆蓋 vi的Ⅰ、Ⅳ象限.

6)xi≤Rs'且n－yi≤Rs':①第Ⅰ象限感知鄰居: xj≤Rs'且n－yi≤Rs'，vi成為冗余節(jié)點;xj≤Rs'且n－yi＞Rs'，vj完全覆蓋vi的Ⅰ、Ⅱ象限;xj＞Rs'且n－yi≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅳ象限.②第Ⅱ象限的感知鄰居如果n－y＞Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.③第Ⅳ象限的感知鄰居如果xi≤Rs'，vj完全覆蓋vi的Ⅲ、Ⅳ象限.

7)m－xi≤Rs'且n－yi≤Rs':①第Ⅰ象限感知鄰居如果n－yj≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅳ象限.②第Ⅱ象限的感知鄰居:m－xj≤Rs'且n－yj≤Rs'，vi成為冗余節(jié)點;m－xj≤Rs'且n－yi＞Rs'，vj完全覆蓋vi的Ⅰ、Ⅱ象限;m－xj＞Rs'且y－yi≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.③第Ⅲ象限的感知鄰居如果m－xj≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.

低空旅游通常稱作航空旅游是指在低空空域范圍內(nèi)利用民用航空器從事商業(yè)航空運輸之外的商務(wù)、觀光、休閑、娛樂等形式的旅游活動。低空旅游作為一種高端旅游消費方式，將飛行體驗和旅游體驗結(jié)合起來，方便快捷，新奇刺激，體驗深刻，給游客帶來高強度的視覺刺激和心靈感受。目前西沙群島三島之間的交通方式是從郵輪依次乘坐快艇前往目的島嶼，交通方式較為單一。利用低空旅游這一旅行方式，可以從整體上觀賞島嶼全貌，甚至島礁全貌，將島嶼景觀盡收眼底，觀賞七連嶼、永樂大環(huán)礁等全貌。其次低空旅游的引進(jìn)將增加島嶼往返之間的交通方式，增加島嶼交通方式的多樣性。

8)m－xi≤Rs'且yi≤Rs':①第Ⅱ象限感知鄰居如果m－xj≤Rs'，vj將完全覆蓋vi的Ⅰ、Ⅱ象限.②第Ⅲ象限的感知鄰居:m－xi≤Rs'且yi≤Rs'，vi成為冗余節(jié)點;m－xi≤Rs'且yi＞Rs'，vj完全覆蓋vi的Ⅲ、Ⅳ象限;m－xi＞Rs'且yi≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.③第Ⅳ象限感知鄰居如果m－xj≤Rs'，vj完全覆蓋vi的Ⅰ、Ⅳ象限.

2.2 線性規(guī)劃過程

為降低工作節(jié)點間能耗差異，優(yōu)化網(wǎng)絡(luò)壽命應(yīng)用線性規(guī)劃最大最小WS中節(jié)點的生存時間:

約束等式是節(jié)點的負(fù)載均衡條件，保證節(jié)點將采集的信息都發(fā)送給基站

2.3 CCLO算法描述

輸入:傳感器節(jié)點集V={v1，v2，…，vN}，節(jié)點的通信半徑Rc，感知半徑Rs，目標(biāo)區(qū)域Z.

輸出:工作節(jié)點集WS，工作節(jié)點的路由策略.

1)WS=RS=?，Temp=V.

2)while(Temp≠?)

①依次選取{Temp}中剩余能量最少的節(jié)點v根據(jù)定理1和邊界節(jié)點冗余條件判別其覆蓋冗余性.

按照定義4判斷v的連通冗余性.

if(v是連通冗余節(jié)點)

③temp=temp－{v}.

End while.

3)WS=V－RS，應(yīng)用式(1)的線性規(guī)劃確定的WS中節(jié)點的路由策略.

4)根據(jù)節(jié)點路由策略向基站傳輸信息，當(dāng)有節(jié)點因能量耗盡而失效時，

if(圖G連通)

更新節(jié)點剩余能量Temp=V，去第2)步.

else End.

算法說明:

1)算法中僅執(zhí)行線性運算即可判別覆蓋冗余節(jié)點，復(fù)雜度為O(ni).

2)根據(jù)節(jié)點剩余能量的大小依次判別冗余性，允許剩余能量少的節(jié)點優(yōu)先進(jìn)入休眠狀態(tài)，提高了算法的穩(wěn)定性和減少節(jié)點丟包數(shù)量.

3)基站根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計算節(jié)點的路由策略，向網(wǎng)絡(luò)中的節(jié)點廣播路由信息.當(dāng)有節(jié)點失效時，基站重將新指派工作節(jié)點和分配路由信息.

3 實驗結(jié)果及分析

為驗證CCLO算法的有效性，在OPNET中對不同的拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真實驗.以下實驗都是在Z= 100 m×100 m的區(qū)域內(nèi)隨機拋灑N=100，150，200個節(jié)點.基站位于場景的中心位置，節(jié)點具有相同的初始能量Ei=0.01 J和信息采集速率Ri=128 bit，Rc=Rs=20 m，eij=140 nJ/bit［9］.

圖2 網(wǎng)絡(luò)壽命Fig.2 Network lifetime

圖2是CCLO算法和文獻(xiàn)［6］方法對20個不同拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真得到的網(wǎng)絡(luò)壽命對比情況.可以看出CCLO通過采用的節(jié)點休眠調(diào)度機制能夠有效地拓展網(wǎng)絡(luò)壽命.并且隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加CCLO算法的網(wǎng)絡(luò)壽命線性增加，而文獻(xiàn)［6］中的網(wǎng)絡(luò)壽命則保持不變.因為對大量傳感器節(jié)點組成的網(wǎng)絡(luò)，隨著N的增加，一跳節(jié)點數(shù)量將隨之增加，同時增加的還有一跳節(jié)點的負(fù)載eNR，而一跳節(jié)點的能耗不變，所以文獻(xiàn)［6］的網(wǎng)絡(luò)壽命不會隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加而增加.

圖3給出了傳感器網(wǎng)絡(luò)的能量消耗，可見由于引入了冗余節(jié)點休眠機制CCLO算法降低了網(wǎng)絡(luò)中工作節(jié)點的數(shù)量，所以CCLO算法的網(wǎng)絡(luò)能耗明顯小于文獻(xiàn)［6］中的方法，這也是提高了網(wǎng)絡(luò)壽命的原因.需要說明的是隨著場景中節(jié)點的失效兩種方法的網(wǎng)絡(luò)能耗都會有所增加，但CCLO算法的能耗始終較小.圖4給出了信息采集過程中工作節(jié)點數(shù)量的平均值，隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加工作節(jié)點的數(shù)量略有增加，但算法中工作節(jié)點數(shù)量趨于穩(wěn)定，并沿Nth=(ceil(m/Rs')+1)×(ceil(n/Rs')+1)方向收斂，其中ceil()是向上取整函數(shù).圖5給出了算法執(zhí)行過程中節(jié)點的覆蓋率，除個別情況由于一跳節(jié)點的失效而導(dǎo)致網(wǎng)絡(luò)的覆蓋率為99.96%外，大多數(shù)情況下對場景實現(xiàn)了完全覆蓋.需要說明的是線性規(guī)劃的計算量是O(n3)［10－12］，n是線性規(guī)劃中變量的個數(shù).所以N個節(jié)點無線傳感器網(wǎng)絡(luò)的變量個數(shù)為線性規(guī)劃過程的復(fù)雜度CCLO算法去除冗余后的計算量僅為，且此時的計算量與網(wǎng)絡(luò)中節(jié)點的數(shù)量無關(guān).

圖3 能量損耗Fig.3 Energy consumption

圖4 工作節(jié)點數(shù)量的平均值Fig.4 Average size of work set

圖5 覆蓋率Fig.5 Coverage rate

4 結(jié)束語

本文提出了基于網(wǎng)絡(luò)的連通和覆蓋性優(yōu)化無線傳感器網(wǎng)絡(luò)壽命的方法，該算法的基本思想是:利用節(jié)點感知圓盤的內(nèi)接正四邊形作為節(jié)點的等效感知區(qū)域，將本來求感知圓盤間交點的復(fù)雜問題簡化為節(jié)點位置關(guān)系的線性判別，降低了判別冗余節(jié)點的復(fù)雜過程.然后應(yīng)用線性規(guī)劃降低工作節(jié)點間能耗差異，當(dāng)某個節(jié)點因能量耗盡而失效時，根據(jù)剩余能量動態(tài)激活其周圍的休眠節(jié)點繼續(xù)執(zhí)行信息的采集和轉(zhuǎn)發(fā)過程.理論分析和仿真研究表明，CCLO方法能夠快速有效地識別網(wǎng)絡(luò)中的冗余節(jié)點，不但降低了線性規(guī)劃過程中的計算復(fù)雜度，而且有效的減少了網(wǎng)絡(luò)的能量損耗，達(dá)到了優(yōu)化網(wǎng)絡(luò)壽命的目的.

［1］AKYILDIZ I，SU W，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks［J］.IEEE Communication Magazine，2002，40(8):102－114.

［2］CHAMAM A，PIERRE S.On the planning of wireless sensor networks:energy－efficient clustering under the joint routing and coverage constraint［J］.IEEE Transactions on Mobile Computing，2009，8(8):1077－1086.

［3］CHANG J H，TASSIULAS L.Maximum lifetime routing in wireless sensor networks［J］.IEEE/ACM Transactions on Networking，2004，12(4):609－619.

［4］DAGHER J C，MARCELLIN M W，NEIFELD M A.A theory for maximizing the lifetime of sensor networks［J］.IEEE Transactions on Communications，2007，55(2):323－332.

［5］XING G L，WANG X R，ZHANG Y F，et al.Integrated coverage and connectivity configuration for energy conservation in sensor networks［J］.ACM Transactions on Sensor Networks，2005，1(1):36－72.

［6］CARBUNAR B，GRAMA A，VITEK J，et al.Redundancy and coverage detection in sensor networks［J］.ACM Transactions on Sensor Networks，2006，2(1):94－128.

［7］RADU S，STANKOVIC J.Probability grid:a location estimation scheme for wireless sensor networks［C］//Proc of IEEE SECON 2004.Santa Clara，CA，2004:430－438.

［8］LUO J，HUBAUX J.Joint mobility and routing for lifetime elongation in wireless sensor networks［C］//Proc IEEE INFOCOM 2005.24th Annual Joint Conference.Miami，2005:1735－1746.

［9］HEIZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－efficient communication protocol for wireless micro sensor networks［C］//Proc IEEE Hawaii Int＇l Conf.Hawaii，2000:1－10.

［10］SAJID H，OBIDUL I.An energy efficient spanning tree based multi－h(huán)op routing in wireless sensor networks［C］// Proc of IEEEE WCNC 2007.Hong Kong，2007:4383－4388.

［11］VAHID S，VINCENT W.Lifetime－resource tradeoff for multicast traffic in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2010，9(6): 1924－1934.

［12］RITESH M，SANJAY L.Distributed algorithms for maximum lifetime routing in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2006，5(8): 2185－2193.