劉志雄,鄧旭東

(長沙學院 計算機工程與應用數學學院,長沙410022)(中國科學院 低溫工程重點實驗室,北京 100190)

1 引 言

隨著傳感技術、分布式信息處理和嵌入式計算技術的日益成熟,無線傳感器網絡(Wireless Sensor Networks,WSNs)在軍事和民用領域獲得了越來越廣泛的應用[1].受限于體積和成本,傳感器節(jié)點攜帶的電池能量極其有限且難以補充.因此,最大化監(jiān)測壽命是WSN的核心目標之一[2].

在入侵檢測等重要應用中,需要由傳感器對目標物的移動路徑進行覆蓋,該類問題稱為路徑覆蓋(path coverage)[3].國內外學者分析了節(jié)點部署密度與路徑覆蓋概率之間的關系[11-14],并針對一類特定場景提出了路徑覆蓋算法[15].這些工作假設目標物的移動軌跡為直線路徑,且在特定場景中對傳感器的精度、帶寬等有特殊要求,在實際應用中受到很大限制.此外,已有算法沒有對資源有限的傳感器網絡進行能量優(yōu)化.針對以上問題,本文提出了一種基于最大加權二分匹配的路徑覆蓋算法,將路徑離散成一些點,并將傳感器節(jié)點分成多個可以獨立覆蓋路徑的組,最后利用最大加權二分匹配對組內節(jié)點進行調度.

2 相關工作

為了對目標區(qū)域實施有效監(jiān)控,需要根據監(jiān)測任務完成覆蓋部署.覆蓋問題通常分為點覆蓋、區(qū)域覆蓋、柵欄覆蓋和路徑覆蓋[3].以下分別對這四類覆蓋問題的研究工作進行介紹.Abrams等[4]證明了最大化生命周期的傳感器網絡k覆蓋是NP完全問題,并提出了隨機算法和分布式貪婪算法.隨機算法的思想是各節(jié)點隨機選擇一個覆蓋集加入,該方法易于實施且魯棒性強,但覆蓋概率較低.在分布式算法中,各節(jié)點依據最大化自身收益的原則,按照編號順序逐個選擇覆蓋集.由于節(jié)點在決策前需獲取之前節(jié)點的決策信息,故該算法不屬于嚴謹的分布式算法.此外,每個節(jié)點僅做一次決策,無法保證獲得最優(yōu)解.

Cardei等[5]提出了一種傳感器網絡目標覆蓋的集中式算法DSC(disjoint set covers).DSC先將目標覆蓋抽象成最大流圖問題,然后給n個節(jié)點分配任務集.每個節(jié)點僅屬于一個任務集,且每個任務集可以獨立覆蓋所有目標.接下來依次調度每個任務集輪流監(jiān)控目標并傳送數據,從而提高網絡工作壽命.然而,一旦網絡拓撲發(fā)生變化,這種靜態(tài)分組策略將帶來較大的維護開銷.

Lu等[6]證明了即便所有傳感器和目標點處于同一歐式平面,目標覆蓋和數據收集的生命周期最大化是NP難問題,并提出了一種多項式時間的近似算法.其思想是通過構建虛擬骨干網絡保證網絡連通性,還通過調整節(jié)點感知半徑實現能量有效覆蓋,由路徑中的葉子節(jié)點對網絡進行監(jiān)控并收集數據,其他節(jié)點只收集數據,然后構建最小權值的覆蓋、數據收集樹對節(jié)點進行調度.

Kumar等[7]提出了一種傳感器網絡柵欄覆蓋生命周期最大化算法.算法通過尋找最大數量的不相交路徑,分時間片輪流調度這些路徑來監(jiān)測柵欄,以最大化網絡生命周期.無需在局部交換信息,各節(jié)點在時間片中以預定概率p進入活動狀態(tài),但無法保證覆蓋概率.算法還推導了弱柵欄存在的臨界條件,為后續(xù)柵欄覆蓋的研究[8-10]提供了理論依據.

Ram等[11]和Manohar等[12]分別在同構和異構節(jié)點模型下,對二維區(qū)域中節(jié)點部署密度和路徑k覆蓋平均比例之間的關系進行了分析,并給出了數學表達式.Harada等[13]和Lei等[14]分別針對路徑1覆蓋和k覆蓋的情形,研究了節(jié)點部署密度與覆蓋概率之間的關系.上述工作僅研究了直線路徑覆蓋,在實際應用中具有很大的局限性.

Zhang等[15]提出了一種適用于無線多媒體傳感器網絡的路徑覆蓋算法MTPCA(Moving Target based Path Coverage-enhancing Algorithm),將一種新的概率模型應用到基于虛擬勢場的有向傳感器網絡中,并利用覆蓋影響因子來校正扇區(qū)的中心位置,以達到更好的覆蓋效果.MTPCA還通過路徑曲線離散技術來獲取目標點的實時位置,并利用節(jié)點間相互作用力和協(xié)作通信來調整傳感器的移動方向,從而實現少量傳感器對目標移動軌跡的覆蓋.然而,由于對節(jié)點配備的能量及帶寬要求較高,MTPCA無法順利用于常規(guī)的傳感器網絡應用中.

綜上可知,點覆蓋、區(qū)域覆蓋和柵欄覆蓋的研究已經較為成熟,但路徑覆蓋及能量優(yōu)化的研究還存在著不足.因此,本文基于曲線離散技術和最大加權二分匹配技術,提出了一種最大化生命周期的傳感器網絡路徑覆蓋算法.

3 問題及定義

3.1 問題描述

問題1.最大生命周期的路徑覆蓋.在傳感器網絡中存在路徑￡,n個傳感器節(jié)點S1,S2,…,Sn,調度傳感器節(jié)點覆蓋路徑￡,并最大化網絡生命周期L.

圖1 傳感器覆蓋路徑Fig.1 Sensors covering path

其中,路徑覆蓋的生命周期是指,從路徑￡能被傳感器節(jié)點完整覆蓋的時間t0,到￡中任意一個點無法被覆蓋的時間t1之間的時間段,即L=t1-t0.

本文通過分組調度傳感器來實現最大生命周期的路徑覆蓋,例如在圖1中,先將節(jié)點分為兩組:W1={S3,S5,S7,S9,S12},W2={S1,S2,S4,S6,S8,S10,S11},然后輪流調度W1和W2來覆蓋路徑.這種分組可能并非最優(yōu),但通過一些啟發(fā)式規(guī)則來接近最優(yōu).

3.2 相關定義

傳感器Si的能量記為ASi,其所覆蓋的路徑￡中的點集合記為C(Si).路徑￡中的點Pi簡稱路徑點,N(Pi)表示覆蓋點Pi的傳感器集合.

定義1.覆蓋加權二分圖.WSNs中覆蓋加權二分圖定義為:B=(V1,V2,E).其中V1、V2和E分別表示傳感器的集合、路徑點的集合和邊的集合.其中,邊是指:若路徑點Pk∈C(Sj),則ei=(Sj,Pk)是B中的一條邊.邊ei的權值w(ei)等于傳感器Sj的能量,即w(ei)=ASj.

圖2 最大加權二分匹配Fig.2 Maximum weighted bipartite matching

定義2.最大加權二分匹配.在二分圖B=(V1,V2,E)中,匹配是指由一組無公共頂點的邊構成的集合,其邊的權值之和最大的匹配稱為最大加權二分匹配.

如圖2中,最大加權匹配是{(S1,P3),(S2,P2),(S3,P1)},權值之和為7.

4 啟發(fā)式算法

最大生命周期的路徑覆蓋算法包括三個步驟:

1)首先,將路徑離散成一些點;

2)其次,將傳感器節(jié)點隨機分為h組,再對組進行合并,使得每個組都能獨立覆蓋所有路徑點;

3)然后,調度各組輪流覆蓋路徑,并對組內的傳感器進行調度.各個傳感器組的生命周期之和就是傳感器網絡路徑覆蓋的最大生命周期.以下分別介紹三個步驟.

4.1 路徑離散

路徑離散的目標為:對給定路徑￡進行曲線離散,產生離散點的集合Q.

路徑離散的過程為:假設路徑￡上所有點的x坐標值的范圍為(x1,xk),設定步長值d,先取路徑￡中x坐標值為x1的點加入到集合Q,然后依次在x軸上移動距離d并相應從路徑￡中取點,再將所取的點添加到集合Q,當取到x坐標值為xh的點結束.由于取點次數為(xk-x1)/d,故算法的時間復雜度為O((xk-x1)/d),算法具體描述如下:

輸入:路徑￡,步長值d1,最小和最大x坐標x1,xk

輸出:一組離散點

1.Note the minimum and maximum x-coordinates in ￡ asx1,xk;

2.Set step-valued;

3.IfQis empty,xi=x1;

4.Else wherexi<=xk

5. get pointP=(xi,f(xi)),

6.Q=Q+{P},xi=xi+d;

7.ReturnQ.

4.2 傳感器分組

傳感器分組包括兩個階段,首先隨機將傳感器分成h組,其次,由于部分組無法覆蓋所有路徑點,故采取策略將一些組進行合并,使得合并后的每個傳感器組都能覆蓋所有路徑點.第一階段為隨機分組,其目標為:給定路徑￡上的m個點P1,P2,…,Pm,以及n個部署的傳感器節(jié)點S1,S2,…,Sn,尋找h個傳感器分組T1,T2,…,Th,且每個分組能覆蓋￡中的部分點.

隨機分組的過程為:對每個路徑點Pi,將覆蓋Pi的傳感器集合N(Pi)隨機分成h組,最終將產生h組傳感器,且每組傳感器能覆蓋路徑￡中的部分點.算法需循環(huán)h*m次,每次從各個N(Pi)中隨機移除部分傳感器,共n個傳感器,故算法的時間復雜度為O(mnh).算法具體描述如下:

輸入:離散點集合Q,傳感器S1,S2,…,Sn

輸出:傳感器組T1,T2,…,Th

1.N(P1)=?;

2. Fori=1 tohdo

3. Forj=1 tomdo

4. select random subsetN′ of N(Pj);

5.Ti=Ti+(N′-N(P1));

6.N(Pj)=N(Pj)-(N′-N(P1));

7.N(P1)=N(P1)+(N′-N(P1));

8.ReturnT1,T2,…,Th.

第二階段為隨機合并分組,其目標為:給定h組傳感器T1,T2,…,Th,以及一組路徑點Q={P1,P2,…,Pm},產生一組集合W1,W2,…,Wr(r≤h),使Wi能覆蓋所有路徑點.

隨機合并分組的過程為:首先,將所有組以覆蓋路徑點數量的多少按照升序排序,其次,選取排序后的第一個組Ti,若其能覆蓋所有路徑點,則將Ti放入Wi并從分組中移除;反之,將Ti放入Wi后并選取下一個組Ti+1,若Ti+1能覆蓋Wi無法覆蓋的路徑點,則將Ti+1加入Wi.重復上述步驟,直到Wi能覆蓋所有路徑點,或所有分組都被考慮到但仍無法覆蓋全部路徑點.如果還有路徑點無法被Wi覆蓋,則需考慮是否存在其他Wj能覆蓋所有路徑點.如果不存在,則返回null,反之剩余組及Wi都將被放置于Wj中.

由于計算每個傳感器覆蓋的路徑點的時間復雜度為O(mnh),將h組傳感器進行排序的時間復雜度為O(hlogh),合并分組的時間復雜度為O(h2),且logh

輸入:傳感器組T1,T2,…,Th,離散點集合Q

輸出:新的傳感器組W1,W2,…,Wr

1.T={T1,T2,…,Th},Q={P1,P2,…,Pm};

2.SortTby the number of covered points;

3.a=1;T′=T;Z=Q;

4.Whilea<=hdoWa=?;b=1;

5. WhileT′ &Z&(b<=h)do

6. If |C(Tb)-(Q-Z)|<=0

7.b++; continue;

8.Wa=Wa+{Tb};T′=T′-Tb;

9.Z=Z-C(Tb);b++;

10. IfZis emptya++

11. Else Ifa<=1 return NULL;

12. else addT′ intoWa-1;

13. addWrintoWa-1;a--;

14.ReturnW1,W2,…,Wa.

4.3 組調度及傳感器調度

傳感器分組之后,調度這些組進行監(jiān)控,并使得路徑覆蓋生命周期最大化.由于組之間不相關,故調度順序對網絡生命周期沒有影響.易知對每個組運行一次調度,即可實現網絡生命周期最大化,該過程耗時O(a),其中a為傳感器組的數量.

接下來對組內的傳感器進行調度,其目標為:給定一組傳感器W1,W2,…,Wa,以及一組路徑點Q={P1,P2,…,Pm},調度傳感器覆蓋所有路徑點,并使生命周期最大化.

傳感器調度的過程為:先構建一個覆蓋加權二分圖B;再從圖中找出一個最大加權二分匹配;接下來,由于要調度能量最多的傳感器工作,因此,若選出的傳感器無法覆蓋所有路徑點,則針對沒有被覆蓋的路徑點繼續(xù)構建覆蓋加權二分圖B′,直到所有路徑點被覆蓋或者直到剩余傳感器都無法覆蓋所有路徑點.

為描述方便,將最大加權二分匹配簡記為MWM(maximum weighted matching),傳感器節(jié)點和邊的數量均為n,路徑點數量為m,最大加權匹配需要遍歷所有傳感器、邊和路徑點,故其耗時O(n2m),接下來還需遍歷路徑點求解B′,故總時間耗費為O(n2m2w),其中w是指所有邊的最大權值.算法具體描述如下:

輸入:傳感器組W1,W2,…,Wr,離散點集合Q

輸出:Wi中的節(jié)點調度

1.ConstructB=(V1,V2,E);

2.Find a MWM inB,denoted byM;

3.While there is unmatched vertex inV2do

4.Denote unmatched vertices set byV2′;

5.ConstructB′ fromV1,V2′;

6.Find a MWM inB′;

7.For each vertexvinV2,letM(v)be the matched vertex inV1,and minimum energy in allM(v)is noted asmin_er;

8.ScheduleM(v)to covervandM(v),so each vertex inV1matched by vertex inV2spendmin_erenergy;

9.Delete the vertices inWiout of energy.

4.4 仿真實驗

為了進一步驗證算法性能,本文利用phython語言和C++語言建立了模擬仿真平臺.仿真環(huán)境如下:在100×100m2監(jiān)控區(qū)域中,取中心點為坐標原點(0,0),路徑￡采用曲線函數y=0.1(x-10)(x-20)(0≤x≤100)產生,且路徑￡被離散成10個點,傳感器節(jié)點隨機分布在路徑點周圍,節(jié)點初始能量為5和10之間的隨機數.

實驗1和實驗2中,傳感器感知半徑為6m;實驗三中,傳感器節(jié)點的感知半徑范圍為1m～22m.實驗1中,傳感器節(jié)點的數量范圍為0～200;實驗2和實驗3中,傳感器節(jié)點的數量為150.假定傳感器覆蓋的點都是連續(xù)的,即若傳感器Si覆蓋離散的路徑點Pj和Pk,則路徑上Pj和Pk之間的點也能被Si覆蓋.限于篇幅,僅給出了當傳感器節(jié)點數量n、節(jié)點初始能量ASi以及傳感器感知半徑rs分別發(fā)生變化時,網絡生命周期L變化情況方面的實驗數據.取15次仿真實驗的平均值作為試驗結果.

實驗1考察了網絡生命周期隨傳感器數量變化的情況,如圖3所示.從圖中可以看出:

1)當網絡中部署的傳感器非常少時,傳感器覆蓋路徑的生命周期為0,例如當n≤16時,L=0.其原因是此時沒有足夠的傳感器來覆蓋這些路徑點.

2)隨著傳感器數量的增加,傳感器覆蓋路徑的生命周期呈上升趨勢,例如當n由25增大到100時,L則從6增到42.因為有越來越多的傳感器覆蓋網絡中的路徑點,故覆蓋路徑生命周期逐漸增大.

圖3 生命周期L隨傳感器數量n變化Fig.3 Change of lifetime L with size of sensors n

圖4 生命周期L隨節(jié)點初始能量ASi變化Fig.4 Change of lifetime L with initial energy of sensors ASi

圖5 生命周期L隨節(jié)點感知半徑rs變化Fig.5 Change of lifetime L with sensing radius of sensors rs

實驗2給出了當n=150,且每個傳感器具有相同的初始能量時,網絡生命周期隨傳感器節(jié)點初始能量的變化情況,如圖4所示.從圖中可以看出,隨著傳感器的初始能量增大,傳感器蓋路徑的壽命迅速增加,例如當ASi=5時,L=60,而當ASi增大到20時,L達到了410.這是因為節(jié)點初始能量是影響路徑覆蓋生命周期的關鍵因素之一,當傳感器具有更多能量可供消耗時,生命周期也相應更大.

實驗3觀察了生命周期隨傳感器節(jié)點感知半徑rs的變化情況,其中每個傳感器隨機具有5～10的初始能量,如圖5所示.從圖中可以看出,網絡生命周期隨傳感器的感知半徑增大而增多,例如當rs=2時L為40,而當rs=5時L為95.但是當感知半徑增加到某個閾值時,網絡的壽命不再增加,例如當rs≥7.5時L保持110不變,因為感知半徑達到該閾值時傳感器已經覆蓋整個網絡區(qū)域.

5 結 論

本文針對已有傳感器網絡路徑覆蓋算法存在的不足,提出了一種最大生命周期的路徑覆蓋算法.利用曲線離散將路徑分割成點,并將部署的傳感器分成多個能獨立覆蓋路徑的組,再采用最大加權二分匹配技術對傳感器組內節(jié)點進行調度,從而在覆蓋路徑的同時最大化網絡生命.仿真實驗考察了節(jié)點數量、節(jié)點初始能量及節(jié)點感知半徑等因素對網絡生命周期的影響.對算法性能進一步優(yōu)化將是接下來的工作.