張 彤,馬欣媛,趙太飛

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

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

引言

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

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

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

1 垂直采樣算法網(wǎng)絡(luò)模型

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

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

圖1 三維水下傳感網(wǎng)模型

該網(wǎng)絡(luò)具有如下特點:

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

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

(3)傳感器節(jié)點加速度為零,即節(jié)點運動時做勻速直線運動,節(jié)點到達穩(wěn)定狀態(tài)時速度瞬間為零.

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

2 基于采樣的三維水下傳感網(wǎng)部署算法

三維監(jiān)測區(qū)域傳感器節(jié)點分布如圖2所示,圖中球體為傳感器節(jié)點的感知范圍.

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

圖2 三維空間傳感器節(jié)點分布示意圖

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

圖4 垂直平面覆蓋示意圖

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

如圖4所示,矩形EFGH為三維監(jiān)測區(qū)域中的一個垂直截面.MN為截面中一條平行于z軸的直線.圖中,(s1,s2,s3,…,sn)是與直線MN相交的n個異構(gòu)感知圓,代表n個水下傳感器節(jié)點.對應(yīng)三維空間中感知圓球的圓心坐標為(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 感知圓與采樣直線相交示意圖

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

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

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

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

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

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

3 算法描述

三維水下傳感器網(wǎng)絡(luò)覆蓋算法具體描述如下:

步驟1.設(shè)置監(jiān)測區(qū)域范圍L×W×H、傳感器節(jié)點個數(shù)N、感知半徑Rs、通信半徑Rc、采樣次數(shù)、最大迭代次數(shù);

步驟2.初始化網(wǎng)絡(luò),隨機部署傳感器節(jié);

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

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

步驟5.循環(huán)迭代,當達到最大迭代次數(shù)時跳到步驟6,否則跳到步驟3;

步驟6.算法結(jié)束.

4 算法仿真與性能分析

為了驗證基于采樣的水下三維傳感網(wǎng)覆蓋算法的有效性,在MATLAB環(huán)境下對垂直采樣算法進行仿真.在1 00m×100m×100m的三維監(jiān)測區(qū)域隨即部署若干傳感器節(jié)點,取節(jié)點感知半徑Rs為30 m,應(yīng)用基于垂直采樣的水下三維傳感網(wǎng)覆蓋算法對傳感器網(wǎng)絡(luò)進行優(yōu)化部署.

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

圖7 覆蓋率與采樣步長的關(guān)系

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

圖8 覆蓋率與節(jié)點個數(shù)的關(guān)系

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

圖9 UVS算法與CTDA算法對比

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

圖10 感知半徑不同時覆蓋率與迭代次數(shù)的關(guān)系

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

圖11 節(jié)點數(shù)不同時覆蓋率與迭代次數(shù)的關(guān)系

圖12 節(jié)點平均移動距離與迭代次數(shù)的關(guān)系

5 結(jié)束語

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

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

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

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

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