基于垂直采樣的水下三維傳感網覆蓋算法①

張 彤,馬欣媛,趙太飛

1(西安理工大學 計算機科學與工程學院,西安 710048)

2(西安理工大學 自動化與信息工程學院,西安 710048)

引言

水環境對于人類來說較為惡劣,很難通過傳統的人工部署方式在水域中進行大規模的資源勘測和開發等活動,依靠技術手段來對水環境進行探索這一方式已達成普遍共識[1,2].因此,水下無線傳感網的研究成為目前的研究熱點之一[3].水下傳感器網絡在水質監測、地理信息采集、災難預防、軍事領域應用等方面均具有廣泛的應用前景[4-9].

覆蓋問題是研究無線傳感器網絡的基本問題.近年來,國內外有很多比較成熟的覆蓋算法.Zou Y等人[10]最先提出了一種集群分布式的虛擬力覆蓋算法和一種新的概率目標定位算法,用于提高傳感器節點初始部署后的覆蓋率.黃俊杰等人[11]提出三維水下傳感網絡覆蓋優化算法,利用虛擬力覆蓋算法消除網絡中的覆蓋重疊區和覆蓋盲區,進而提高整個區域的覆蓋率.杜曉玉等人[12]提出了一種基于虛擬勢場的定向移動的覆蓋優化算法,該算法對網絡中節點位置進行微調,多次迭代后節點位置達到穩定,實現網絡的優化覆蓋.王興民等人[13]提出一種基于連通樹的水下傳感網覆蓋算法,由匯聚節點開始構建多個連通子樹將網絡組織成森林保證網絡連通,通過減小每棵子樹內父子節點間覆蓋冗余以達到提升整個網絡覆蓋率的目的.王雪等人[14]提出一種無線傳感網布局的虛擬力導向微粒群算法,結合虛擬力與微粒群算法的優點,在提高網絡覆蓋率的同時減少算法耗時.

現有的文獻中對水環境二維傳感網覆蓋問題研究較多,對水下三維傳感網問題研究較少[15].本文設計一種基于垂直采樣的水下三維傳感網覆蓋算法(Underwater 3D sensor network coverage algorithm based on Vertical Sampling,UVS),先對三維監測區域進行平面采樣,將三維傳感網覆蓋問題轉化為二維異構傳感網覆蓋問題,再對二維平面進行直線采樣,將二維的覆蓋問題轉化為一維直線的覆蓋問題,目的是在傳感器節點耗能最少的情況下將采樣直線更多覆蓋,最終達到提升三維區域傳感網的覆蓋率.

1 垂直采樣算法網絡模型

網絡由3部分構成,包括水下感知節點、錨和水面通信節點構成,如圖1所示.網絡初始時,由飛機或船舶將感知節點、錨和通信節點拋灑到監測區域.拋灑后錨位置固定,防止傳感器因為海水流動和風力因素偏離目標區域,從而降低目標區域的覆蓋率.由于初始時節點被錨定,所以假設傳感器節點只能在豎直方向上運動,不能在水平方向上運動.然后根據部署算法計算出浮標距離傳感器節點纜繩的長度,利用控制電機調節繩索長度,達到調節傳感器節點位置的目的[16].

由于在水環境中無線電波衰減嚴重,采用無線電波通信需要加裝很長的接收天線,并且通信時的能耗非常大,不適用于水下傳感網這種稀疏環境.如果采用激光通信的方式,不僅對節點間對準程度要求非常高,而且水環境的濁度對激光通信的影響也很大.而聲波通信雖然傳播速度不及以上兩種通信方式,但是在水中傳播的衰減小、傳播距離長[17].綜上,考慮到水環境傳感網的這種稀疏環境采用聲學通信的方式.

圖1 三維水下傳感網模型

該網絡具有如下特點:

(1)網絡分為水面通信節點和水下感知節點兩部分.水下感知節點包括濁度傳感器、余氯傳感器、PH值傳感器等,負責對水質參數進行監測;水面通信節點負責與基站進行通信;水下感知節點通過電纜與水面通信節點相連,并可以進行通信.

(2)節點拋灑在監測區域后,感知節點只能在豎直方向上運動,不能在水平方向上運動.

(3)傳感器節點加速度為零,即節點運動時做勻速直線運動,節點到達穩定狀態時速度瞬間為零.

(4)傳感器節點同構,采用布爾感知模型,節點的通信半徑Rc為感知半徑Rs的2倍,每個節點與基站間至少存在一條通信鏈路.

2 基于采樣的三維水下傳感網部署算法

三維監測區域傳感器節點分布如圖2所示,圖中球體為傳感器節點的感知范圍.

由于對三維空間水平平面采樣求解困難,采用對垂直平面采樣的方式進行網絡的覆蓋優化.首先對三維監測區域在垂直方向進行平面采樣,如圖3所示,圖中圓形為采樣平面與感知球體相交得到的截面.圖3(a)中,矩形EFGH為三維監測區域中與xz軸平行的一個垂直采樣平面,平面方程為y=y0.圖3(b)中,矩形EFGH為三維監測區域中與yz軸平行的一個垂直采樣平面,平面方程為x=x0.雖然感知球體同構,但由于球心距采樣平面的距離不同,所以感知球體與采樣平面相交的圓的大小不同,采樣截面可以看作平面異構傳感網.

圖2 三維空間傳感器節點分布示意圖

圖3 三維空間垂直采樣示意圖

圖4 垂直平面覆蓋示意圖

圖5 感知圓球與采樣平面相交示意圖

如圖4所示,矩形EFGH為三維監測區域中的一個垂直截面.MN為截面中一條平行于z軸的直線.圖中,(s1,s2,s3,…,sn)是與直線MN相交的n個異構感知圓,代表n個水下傳感器節點.對應三維空間中感知圓球的圓心坐標為(xi,yi,zi),如圖5所示,感知圓球與采樣平面相交的感知圓的半徑為:如圖6所示,感知圓與采樣直線MN相交的上交點縱坐標為zih=zi+ri,下交點的縱坐標為zil=zi-ri.則感知圓si與直線MN的兩個交點分別為(x0,zil)、(x0,zih),其中,zil＜zih.n個感知圓與采樣直線相交所得的交點為(x0,z1l),(x0,z1h),(x0,z2l),(x0,z2h),(x0,z3l),(x0,z3h),…,(x0,znl),(x0,znh).感知圓與采樣直線相交所得的線段可以表示為:Z1={z/z1l≤z≤z1h},z2={z|z2l≤z≤z2h},z3={z|z3l≤z≤z3h}…={z|znl≤z≤znh}.

圖6 感知圓與采樣直線相交示意圖

優化后感知圓與長度為l的采樣直線MN相交的線段總長度L可表示為:

感知圓對直線的覆蓋需分兩種情況討論: 第一種情況是感知節點移動后,感知圓可將采樣直線完全覆蓋,即L≥l.第二種情況是感知節點移動后,感知圓不能將采樣直線完全覆蓋,即L≤l.

(1)優化后感知圓可將采樣直線完全覆蓋.如果優化后n個感知圓可將直線MN覆蓋完全,即感知圓與采樣直線相交所得的線段集合的并集包含采樣直線的線段集合X={0≤x≤l},l是矩形監測區域的長度.如果優化后直線l可被感知圓完全覆蓋,則每個感知圓si與直線l的下交點至少在另一個感知圓上交點的下邊,上交點至少在另一個感知圓下交點的上邊.式(3)為約束條件:

其中,△di表示第i個傳感器移動的距離,l為矩形區域的長度.由于式(3)為非線性二次規劃,求解困難,為方便求解,依據感知圓位置順序不變時,對采樣直線l完全覆蓋所需移動距離之和小于改變順序時移動的距離之和,將非線性約束條件轉化為線性約束條件進行求解.

根據部署算法優化之后,感知圓可以完全覆蓋采樣直線,約束條件轉化為任意一個感知圓與采樣直線l相交的下交點在上一個感知圓上交點的下邊,任意一個感知圓的上交點在下一個感知圓下交點的上邊,約束條件為:

(2)優化后感知圓不能將采樣直線完全覆蓋.如果優化后n個感知圓不能將直線l覆蓋完全,式(4)無解.在這種情況下,當感知圓互不相交時,感知圓對采樣直線的覆蓋程度最大,即任意一個感知圓與采樣直線相交的下交點在上一個感知圓上交點的上邊,任意一個感知圓與采樣直線相交的上交點在下一個感知圓下交點的下邊,約束條件為:

3 算法描述

三維水下傳感器網絡覆蓋算法具體描述如下:

步驟1.設置監測區域范圍L×W×H、傳感器節點個數N、感知半徑Rs、通信半徑Rc、采樣次數、最大迭代次數;

步驟2.初始化網絡,隨機部署傳感器節;

步驟3.對垂直平面進行平面采樣,依此判斷每個感知圓球與采樣平面是否相交,如果相交,則根據式(1)計算感知圓球與采樣平面相交形成圓的圓心位置和圓的半徑,并保存;

步驟4.判斷感知圓與采樣直線相交的線段總和和L與采樣直線長度l的大小關系,若L≥l,則根據式(4)計算新的節點移動位置,若L＜l,則根據式(5)計算新的節點移動位置;

步驟5.循環迭代,當達到最大迭代次數時跳到步驟6,否則跳到步驟3;

步驟6.算法結束.

4 算法仿真與性能分析

為了驗證基于采樣的水下三維傳感網覆蓋算法的有效性,在MATLAB環境下對垂直采樣算法進行仿真.在1 00m×100m×100m的三維監測區域隨即部署若干傳感器節點,取節點感知半徑Rs為30 m,應用基于垂直采樣的水下三維傳感網覆蓋算法對傳感器網絡進行優化部署.

圖7為節點數不同時覆蓋率與采樣步長的關系.當采樣步長選取較小時,相鄰兩個采樣平面、采樣直線之間的距離較小,優化結果會互相影響,這樣不僅會增加算法的運算量,而且對覆蓋率還會造成負影響.當采樣步長選取過大時,無法對整個監測區域的覆蓋情況進行優化,同樣覆蓋率不能得到有效的提高.綜合這兩方面的因素考慮,選取采樣步長為10米.

圖7 覆蓋率與采樣步長的關系

圖8為感知節點數不同時,隨機部署與迭代兩次的UVS算法的網絡覆蓋率的比較.從圖中可以看出在節點數相同時,UVS算法可以顯著地提高網絡覆蓋率.

圖8 覆蓋率與節點個數的關系

圖9為UVS算法與基于連通樹的深度調節(Conected Tree Depth Adjust,CTDA)算法[13]進行比較.UVS算法與CTDA算法模型相同,均為在水下三維空間中,傳感器節點僅在垂直方向運動.其中,節點數均為50個,感知半徑為30 m.在迭代次數為3時,UVS算法的網絡覆蓋率為91%,CTDA算法的網絡覆蓋率為83%.從圖中可以看出,UVS算法的收斂速度比CTDA算法更快,并且覆蓋程度比CTDA算法更好.

圖9 UVS算法與CTDA算法對比

圖10為節點感知半徑不同時網絡覆蓋率隨迭代次數的變化.其中,四條曲線的傳感器節點數均為40個,采樣步長為10 m.考慮到節點的感知半徑不定,如果采樣步長也不定將無法對不同半徑時的網絡覆蓋率進行比較,因此只考慮采樣步長為10 m的情況.在迭代次數為5時,Rs=30的覆蓋率為76%,Rs=40的覆蓋率為86%,Rs=50的覆蓋率為91%,Rs=60的覆蓋率為94%.從圖中可以看出,在迭代次數相同時,感知半徑越大覆蓋率越大.在迭代次數為0到2時,UVS算法對網絡覆蓋率的提升效果最好,經過3次迭代之后,覆蓋率只在小幅度范圍內變化,說明算法的收斂速度很快.

圖10 感知半徑不同時覆蓋率與迭代次數的關系

圖11為節點數不同時時網絡覆蓋率隨迭代次數的變化.其中,傳感器節點的感知半徑為30 m,采樣步長為10 m.在迭代次數為5時,N=30的覆蓋率為77%,N=40的覆蓋率為86%,N=50的覆蓋率為92%,N=60的覆蓋率為96%.從圖中可以看出,在迭代次數相同時,節點數量越多網絡覆蓋率越大.迭代次數從0增加到2時,網絡覆蓋率增長得最快,隨著迭代次數的增加網絡覆蓋率先快速增長然后趨于平穩,經過3次迭代網絡就已經能到達較好的覆蓋率.當迭代次數大于3時,覆蓋率只在小范圍內變化.圖12為節點平均移動距離隨迭代次數增長的變化,算法每迭代一次會更新傳感器節點的位置信息,傳感器節點移動到算法每次迭代后優化的位置.從圖中可以看出,算法前兩次迭代節點移動距離較大,從第三次迭代開始隨著迭代次數增加節點移動距離減少,并且變化不大.可以看出算法前兩次迭代的效果最明顯,說明算法收斂速度很快.

圖11 節點數不同時覆蓋率與迭代次數的關系

圖12 節點平均移動距離與迭代次數的關系

5 結束語

針對水環境傳感器節點隨機部署時產生覆蓋空洞和覆蓋冗余并且覆蓋率較低的問題,本文采用一種基于采樣的水下三維傳感網覆蓋算法.通過對基于垂直采樣的水下三維傳感網覆蓋算法進行仿真,對節點個數、節點半徑與覆蓋率的關系進行分析,得出以下結論:

(1)與隨機部署策略相比,基于采樣的水下三維傳感 網覆蓋算法可以顯著提高網絡覆蓋率.與CTDA算法相比,UVS算法的收斂速度更快,并且覆蓋程度比CTDA算法更好.

(2)在傳感器節點數一定而節點感知半徑不同時,隨著迭代次數增加,網絡覆蓋率先快速增加然后趨于平穩.在感知半徑不同而節點數相同時,感知半徑越大覆蓋率越大.在迭代次數為0到2時,UVS算法對網絡覆蓋率的提升效果最好,經過3次迭代之后,覆蓋率只在小幅度范圍內變化,說明算法的收斂速度很快.

(3)算法前兩次迭代節點移動距離較大,從第三次迭代開始隨著迭代次數增加節點移動距離減少,并且變化不大.

針對水下三維傳感網覆蓋問題,設計了基于垂直采樣的水下三維傳感網覆蓋算法,下一步將考慮降低網絡的能耗.