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

曲家慶，張曙

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

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

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

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

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

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

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

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

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

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

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

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

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

2 CCLO算法

2.1 判別冗余節(jié)點(diǎn)

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

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

圖1 判別覆蓋冗余節(jié)點(diǎn)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ū)域外任意一點(diǎn)，(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é)點(diǎn):如果節(jié)點(diǎn)的等效感知區(qū)域與場(chǎng)景邊界存在交點(diǎn)，那么這樣的節(jié)點(diǎn)就是邊界節(jié)點(diǎn).

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

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

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

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

4)n－yi≤Rs':第Ⅱ象限的感知鄰居 vj，如果n－yj≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限;對(duì)第Ⅰ象限的感知鄰居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é)點(diǎn);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é)點(diǎn);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é)點(diǎn);m－xj≤Rs'且n－yi＞Rs'，vj完全覆蓋vi的Ⅰ、Ⅱ象限;m－xj＞Rs'且y－yi≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.③第Ⅲ象限的感知鄰居如果m－xj≤Rs'，vj完全覆蓋vi的Ⅱ、Ⅲ象限.

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

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

2.2 線性規(guī)劃過程

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

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

2.3 CCLO算法描述

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

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

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

2)while(Temp≠?)

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

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

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

③temp=temp－{v}.

End while.

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

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

if(圖G連通)

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

else End.

算法說明:

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證CCLO算法的有效性，在OPNET中對(duì)不同的拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真實(shí)驗(yàn).以下實(shí)驗(yàn)都是在Z= 100 m×100 m的區(qū)域內(nèi)隨機(jī)拋灑N=100，150，200個(gè)節(jié)點(diǎn).基站位于場(chǎng)景的中心位置，節(jié)點(diǎn)具有相同的初始能量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］方法對(duì)20個(gè)不同拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真得到的網(wǎng)絡(luò)壽命對(duì)比情況.可以看出CCLO通過采用的節(jié)點(diǎn)休眠調(diào)度機(jī)制能夠有效地拓展網(wǎng)絡(luò)壽命.并且隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加CCLO算法的網(wǎng)絡(luò)壽命線性增加，而文獻(xiàn)［6］中的網(wǎng)絡(luò)壽命則保持不變.因?yàn)閷?duì)大量傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)，隨著N的增加，一跳節(jié)點(diǎn)數(shù)量將隨之增加，同時(shí)增加的還有一跳節(jié)點(diǎn)的負(fù)載eNR，而一跳節(jié)點(diǎn)的能耗不變，所以文獻(xiàn)［6］的網(wǎng)絡(luò)壽命不會(huì)隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加而增加.

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

圖3 能量損耗Fig.3 Energy consumption

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

圖5 覆蓋率Fig.5 Coverage rate

4 結(jié)束語(yǔ)

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