基于垂直采樣的水下三維傳感網(wǎng)覆蓋算法①

張 彤,馬欣媛,趙太飛

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

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

引言

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

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

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

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

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

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

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

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

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

(2)節(jié)點(diǎn)拋灑在監(jiān)測(cè)區(qū)域后,感知節(jié)點(diǎn)只能在豎直方向上運(yùn)動(dòng),不能在水平方向上運(yùn)動(dòng).

(3)傳感器節(jié)點(diǎn)加速度為零,即節(jié)點(diǎn)運(yùn)動(dòng)時(shí)做勻速直線運(yùn)動(dòng),節(jié)點(diǎn)到達(dá)穩(wěn)定狀態(tài)時(shí)速度瞬間為零.

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

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

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

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

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

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

圖4 垂直平面覆蓋示意圖

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

如圖4所示,矩形EFGH為三維監(jiān)測(cè)區(qū)域中的一個(gè)垂直截面.MN為截面中一條平行于z軸的直線.圖中,(s1,s2,s3,…,sn)是與直線MN相交的n個(gè)異構(gòu)感知圓,代表n個(gè)水下傳感器節(jié)點(diǎn).對(duì)應(yīng)三維空間中感知圓球的圓心坐標(biāo)為(xi,yi,zi),如圖5所示,感知圓球與采樣平面相交的感知圓的半徑為:如圖6所示,感知圓與采樣直線MN相交的上交點(diǎn)縱坐標(biāo)為zih=zi+ri,下交點(diǎn)的縱坐標(biāo)為zil=zi-ri.則感知圓si與直線MN的兩個(gè)交點(diǎn)分別為(x0,zil)、(x0,zih),其中,zil＜zih.n個(gè)感知圓與采樣直線相交所得的交點(diǎ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)化后感知圓與長(zhǎng)度為l的采樣直線MN相交的線段總長(zhǎng)度L可表示為:

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

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

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

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

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

3 算法描述

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

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

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

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

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

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

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

4 算法仿真與性能分析

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

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

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

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

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

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

圖9 UVS算法與CTDA算法對(duì)比

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

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

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

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

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

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

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

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

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

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

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