基于節(jié)點(diǎn)重部署的水下傳感器網(wǎng)絡(luò)三維柵欄覆蓋*

范興剛,蒿 翔,程斯顥,嚴(yán)天一

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

由具有聲學(xué)通信與計(jì)算能力的傳感器節(jié)點(diǎn)構(gòu)成的水下傳感器網(wǎng)絡(luò)UWSNs(Underwater Sensor Networks)可應(yīng)用于水環(huán)境監(jiān)測(cè)、資源勘測(cè)、輔助導(dǎo)航和戰(zhàn)術(shù)監(jiān)視等領(lǐng)域[1-5],特別是將傳感器節(jié)點(diǎn)部署于感興趣水域,對(duì)進(jìn)入該水域的移動(dòng)目標(biāo)進(jìn)行入侵檢測(cè)。

為了增強(qiáng)水下傳感器網(wǎng)絡(luò)目標(biāo)檢測(cè)能力,很多學(xué)者研究如何增強(qiáng)整個(gè)三維區(qū)域覆蓋。蔣鵬等人[6]提出了一種水下傳感器網(wǎng)絡(luò)單跳覆蓋保持路由算法(SCPR),對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行分簇,選舉覆蓋冗余度大的節(jié)點(diǎn)為簇首來(lái)保持區(qū)域覆蓋。還提出一種分布式的網(wǎng)絡(luò)不均勻分層的覆蓋保持路由算法(NULCPR)[7],由SINK節(jié)點(diǎn)開(kāi)始逐層向下建立通信半徑逐漸增大網(wǎng)絡(luò),保證網(wǎng)絡(luò)連通的情況下保持區(qū)域覆蓋。以上都是調(diào)度靜態(tài)節(jié)點(diǎn),保持網(wǎng)絡(luò)覆蓋,這需要較多的節(jié)點(diǎn)?？梢圆捎靡晕⒄{(diào)方式的重部署,提高網(wǎng)絡(luò)覆蓋。黃俊杰等人[8]提出一種基于虛擬力調(diào)節(jié)運(yùn)動(dòng)受限(節(jié)點(diǎn)只能豎直方向運(yùn)動(dòng))節(jié)點(diǎn),減少覆蓋冗余,提高網(wǎng)絡(luò)覆蓋率。Li等人[9]提出一種基于虛擬力利用局部信息分布式實(shí)現(xiàn)均勻覆蓋。夏娜等人[10]提出一種基于剛性理論的節(jié)點(diǎn)移動(dòng)策略提高三維網(wǎng)絡(luò)覆蓋率。劉惠等人[11]提出一種基于虛擬力的三維節(jié)點(diǎn)重部署算法來(lái)提高網(wǎng)絡(luò)覆蓋。何明等人[12]通過(guò)三維節(jié)點(diǎn)半隨機(jī)移動(dòng)模型(3D_NMM)提高三維網(wǎng)絡(luò)的覆蓋率。Samil等人[13]將小波變換和貓群優(yōu)化算法用于三維傳感器部署,最大化無(wú)線傳感器網(wǎng)絡(luò)的覆蓋質(zhì)量。

對(duì)整個(gè)區(qū)域進(jìn)行全覆蓋,雖然可以實(shí)現(xiàn)目標(biāo)檢測(cè),但這會(huì)浪費(fèi)大量節(jié)點(diǎn)。二維網(wǎng)絡(luò)情況下,可以只對(duì)某一狹長(zhǎng)區(qū)域進(jìn)行覆蓋,來(lái)實(shí)現(xiàn)目標(biāo)檢測(cè),這種技術(shù)被稱(chēng)為柵欄覆蓋。Tian等人[14]研究了二維柵欄覆蓋,從橫向和豎向兩方面分布式構(gòu)建柵欄。Ma等人[15]通過(guò)線性規(guī)劃方法運(yùn)用受限移動(dòng)特性構(gòu)建最多的柵欄覆蓋。為了能量高效地構(gòu)建K-柵欄覆蓋,班冬松等人[16]設(shè)計(jì)CBIGB算法。預(yù)先確定實(shí)現(xiàn)柵欄覆蓋的目標(biāo)位置,再通過(guò)匈牙利算法選擇能耗最小的節(jié)點(diǎn)移動(dòng)實(shí)現(xiàn)柵欄覆蓋。但是在相鄰的子?xùn)艡谥g通過(guò)貫穿整個(gè)區(qū)域的豎直柵欄鏈接,需要較多節(jié)點(diǎn),消耗移動(dòng)能量也較多。王超等人[17]的PMNSB算法只在相鄰子?xùn)艡谥g構(gòu)建豎直鏈接?xùn)艡?來(lái)克服這個(gè)問(wèn)題。任勇默等人[18]的NSDBC算法則選擇能耗最小的相鄰節(jié)點(diǎn)構(gòu)造有向柵欄。

三維水域中,我們也可以只對(duì)部分水域進(jìn)行覆蓋,用更少的節(jié)點(diǎn)實(shí)現(xiàn)目標(biāo)入侵檢測(cè),我們稱(chēng)之為三維柵欄覆蓋。如圖1所示,如果平面ABCD完全被覆蓋,沿著路徑1、2、3、4的入侵者都可以被檢測(cè)。但到目前為止,還鮮有三維柵欄覆蓋的研究。本文致力于三維水下網(wǎng)絡(luò)的柵欄覆蓋研究,主要工作如下:采用柵欄面模型把三維柵欄覆蓋轉(zhuǎn)化為二維平面的覆蓋空洞修補(bǔ)問(wèn)題,采用微調(diào)方式對(duì)部分節(jié)點(diǎn)進(jìn)行重部署,節(jié)能高效的實(shí)現(xiàn)三維柵欄覆蓋。

圖1 三維柵欄面

剩余章節(jié)安排如下;第1節(jié)是問(wèn)題描述和相關(guān)模型;第2節(jié)詳細(xì)描述基于節(jié)點(diǎn)移動(dòng)的柵欄面算法;第3節(jié)詳細(xì)描述基于節(jié)點(diǎn)部分移動(dòng)的柵欄面算法;第4節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)提出的算法進(jìn)行性能評(píng)估;第5節(jié)總結(jié)全文并介紹下一步工作。

1 問(wèn)題描述和相關(guān)定義

在一個(gè)水下三維區(qū)域內(nèi),隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)集合。節(jié)點(diǎn)之間使用聲學(xué)方式通信。網(wǎng)絡(luò)還存在以下假設(shè):①同文獻(xiàn)[2],采用布爾感知模型,傳感器的感知區(qū)域?yàn)榘霃絉的球體。②所有傳感器都能不受限移動(dòng),移動(dòng)單位能耗Jm=1 J/m。③入侵者水平運(yùn)動(dòng),從長(zhǎng)方體最左邊進(jìn)入,從最右邊出去,或者相反的運(yùn)動(dòng)方向。

定義1切面覆蓋率,在一個(gè)穿過(guò)整個(gè)三維區(qū)域的切面內(nèi),被節(jié)點(diǎn)覆蓋的子區(qū)域與整個(gè)切面面積之比,就是這個(gè)平面的覆蓋率。

本文采用放置探測(cè)點(diǎn)的方法計(jì)算切面覆蓋率,在整個(gè)切面平均放置探測(cè)點(diǎn)。如果一個(gè)探測(cè)點(diǎn)在任意一個(gè)傳感器的感知區(qū)域內(nèi),這個(gè)探測(cè)點(diǎn)就標(biāo)記為1。否則,這個(gè)探測(cè)點(diǎn)就標(biāo)記為0。在一個(gè)切面中,覆蓋率就是被覆蓋的探測(cè)點(diǎn)數(shù)與這個(gè)切面總探測(cè)點(diǎn)數(shù)之比。

定義2柵欄面,在三維區(qū)域內(nèi),如果一個(gè)切面的覆蓋率達(dá)到100%,這個(gè)切面就是這個(gè)三維區(qū)域的柵欄面。

如圖1所示,在一個(gè)長(zhǎng)方體水下三維區(qū)域內(nèi),豎直面ABCD是它的一個(gè)切面。如果這個(gè)切面被完全覆蓋,任何一個(gè)沿x軸方向進(jìn)出的入侵者,無(wú)論是沿著左邊進(jìn),右邊出的路徑1和2,還是沿著右邊進(jìn),左邊出的路徑3和4穿過(guò)這個(gè)區(qū)域,都能被這個(gè)切面監(jiān)測(cè)到,豎直面ABCD就是這個(gè)水下三維區(qū)域一個(gè)柵欄面。如果切面ADHI也是完全覆蓋,它也是水下三維區(qū)域一個(gè)柵欄面。

如果在給定的三維區(qū)域內(nèi),存在至少一個(gè)完全覆蓋的切面,我們就說(shuō)這個(gè)三維區(qū)域?qū)崿F(xiàn)了柵欄覆蓋。如果柵欄面存在覆蓋空洞,我們可以選擇一些節(jié)點(diǎn)進(jìn)行重部署,修補(bǔ)這個(gè)覆蓋空洞。

定義3覆蓋空洞修補(bǔ)線段,如果一個(gè)節(jié)點(diǎn)移動(dòng)到穿過(guò)覆蓋空洞質(zhì)心的垂直線段上,這個(gè)空洞就可以得到最大程度的修補(bǔ),這樣的垂直線段稱(chēng)為空洞修補(bǔ)線段。

我們研究的問(wèn)題是:在一個(gè)隨機(jī)部署了N個(gè)傳感器水下三維區(qū)域內(nèi),如何用最少的移動(dòng)能耗實(shí)現(xiàn)三維柵欄覆蓋。

2 三維柵欄的理論分析

垂直切面ABCD的面積為L(zhǎng)2,根據(jù)幾何知識(shí)可知某個(gè)節(jié)點(diǎn)在這個(gè)切面上的最大覆蓋區(qū)域?yàn)棣蠷2。根據(jù)幾何特性,感知圓內(nèi)有一個(gè)內(nèi)切多邊形,如圖2(a)所示。在二維覆蓋中,如果僅僅是節(jié)點(diǎn)感知圓相切,4個(gè)相鄰的節(jié)點(diǎn)感知圓內(nèi)部就有可能形成如圖2(a)的覆蓋空洞,如果感知圓的內(nèi)切多邊形正好相連,盡管感知圓有重疊區(qū)域,但內(nèi)切正方形沒(méi)有重疊,恰好相鄰,就可以消除覆蓋空洞,如圖2(b)所示。

圖2 覆蓋區(qū)域

定理1如果一個(gè)豎直切面的面積為L(zhǎng)2,節(jié)點(diǎn)感知圓內(nèi)的內(nèi)切q多邊形相連,則形成一個(gè)柵欄面需要的最少節(jié)點(diǎn)數(shù)可用式(1)表示。

(1)

q越大,內(nèi)切多面形的面積越大,柵欄覆蓋需要的節(jié)點(diǎn)數(shù)量越少,為了計(jì)算簡(jiǎn)單,這里選用內(nèi)切四邊形相連,如圖2(b)所示,盡管感知圓有重疊區(qū)域,但內(nèi)切四邊形沒(méi)有重疊,恰好相鄰,就可以消除圖2(a)覆蓋空洞。

根據(jù)幾何知識(shí),顯然Nb?Narea,柵欄覆蓋遠(yuǎn)小于區(qū)域覆蓋需要的節(jié)點(diǎn)數(shù)量。要使ABCD切面成為柵欄面,就要選擇節(jié)點(diǎn)移動(dòng)到相應(yīng)位置,使這個(gè)切面的覆蓋率為100%。這雖然可以形成三維柵欄覆蓋,但會(huì)消耗很多能量。

我們進(jìn)一步分析三維區(qū)域中的平面覆蓋。隨機(jī)部署的節(jié)點(diǎn)在垂直切面ABCD上的覆蓋區(qū)域不再是大小相等的感知圓。如果某個(gè)節(jié)點(diǎn)正好在這個(gè)切面上,其覆蓋區(qū)域?yàn)榘霃絉的感知圓。如果節(jié)點(diǎn)到這個(gè)切面的距離小于R,其覆蓋區(qū)域?yàn)榘霃叫∮赗的感知圓。如果節(jié)點(diǎn)到這個(gè)切面的距離大于R,其覆蓋區(qū)域?yàn)?。

文獻(xiàn)[19],二維平面中,可以找到覆蓋空洞,然后對(duì)其進(jìn)行修補(bǔ)來(lái)提高覆蓋率。在三維水下區(qū)域中,為了能量高效的形成三維柵欄,對(duì)于最大覆蓋率的豎直切面,確定覆蓋這個(gè)切面的節(jié)點(diǎn)集合和覆蓋空洞,然后選擇移動(dòng)節(jié)點(diǎn)移動(dòng),修補(bǔ)這個(gè)空洞。

圖3 距離對(duì)節(jié)點(diǎn)感知能力的影響

定理3一個(gè)節(jié)點(diǎn)對(duì)一個(gè)垂直切面上的覆蓋空洞的最小修補(bǔ)區(qū)域?yàn)?,最大為πR2。

很顯然,如果一個(gè)節(jié)點(diǎn)移動(dòng)到空洞質(zhì)心上,對(duì)空洞的修補(bǔ)效果最好,但對(duì)于較小的空洞,只要以微調(diào)方式移動(dòng)到空洞修補(bǔ)線段上,就完全可以修補(bǔ)空洞,能量高效的形成柵欄。

定理4豎直切面上如果存在一個(gè)面積小于πR2的覆蓋空洞,只要移動(dòng)一個(gè)節(jié)點(diǎn)到其修補(bǔ)線段,就可以對(duì)其完成修補(bǔ)。

3 基于節(jié)點(diǎn)重部署的三維柵欄構(gòu)建

3.1 BinP算法

3.2 Bmon算法

BinP算法雖然可以形成柵欄面,但需要很多節(jié)點(diǎn)移動(dòng)到目標(biāo)位置,導(dǎo)致較大能耗。為了減少能耗,提高效率,我們先找到覆蓋空洞,再選擇節(jié)點(diǎn)修補(bǔ)覆蓋空洞,完成柵欄面構(gòu)建。這就是基于重部署的三維柵欄構(gòu)建算法Bmon(3D barrier coverage construction based on node movement)算法。

3.2.1 偽代碼

此算法的偽代碼如圖4所示,其中的變量如表1所示。

圖4 Bmon算法偽代碼

ROI三維監(jiān)控區(qū)域Pb柵欄面Et總能耗Em平均能耗Nb柵欄面的構(gòu)成節(jié)點(diǎn)Nbm構(gòu)成柵欄面的移動(dòng)節(jié)點(diǎn)Nc覆蓋柵欄面的節(jié)點(diǎn)集合Nr覆蓋柵欄面的冗余節(jié)點(diǎn)集合Nrr修補(bǔ)空洞的節(jié)點(diǎn)集合Nrr/min修補(bǔ)空洞的當(dāng)前節(jié)點(diǎn)lr修補(bǔ)線段Jm移動(dòng)單位能耗

3.2.2 算法基本過(guò)程

Bmon算法的具體步驟如下:

Step 1 尋找覆蓋率最大的YOZ切面

采用和文獻(xiàn)[19]類(lèi)似的方法計(jì)算每個(gè)垂直切面的覆蓋率,其中的網(wǎng)格就是探測(cè)點(diǎn),由于這里采用0-1確定感知模型,只要探測(cè)點(diǎn)距離一個(gè)節(jié)點(diǎn)的歐式距離

Step 2 找到覆蓋這個(gè)垂直切面的初始節(jié)點(diǎn)集合Nc

根據(jù)定理2,任何一個(gè)節(jié)點(diǎn)在一個(gè)垂直切面上的感知區(qū)域最小為0,最大感知區(qū)域離πR2。只要一個(gè)節(jié)點(diǎn)在這個(gè)切面上的感知區(qū)域大于0,這個(gè)節(jié)點(diǎn)就屬于集合Nc。

Step 3 找到覆蓋這個(gè)垂直切面的冗余節(jié)點(diǎn)集合Nr

先從覆蓋這個(gè)切面的節(jié)點(diǎn)集合中,選出可能的修補(bǔ)節(jié)點(diǎn)組建修補(bǔ)集合。節(jié)點(diǎn)移動(dòng)后可以修補(bǔ)空洞,且切面上原來(lái)的覆蓋區(qū)域仍然是覆蓋區(qū)域,這樣的節(jié)點(diǎn)組成冗余修補(bǔ)節(jié)點(diǎn)集合Nr。例如,圖5中的節(jié)點(diǎn)E,F在切面ABCD上的覆蓋區(qū)域都已經(jīng)被其他節(jié)點(diǎn)覆蓋,這兩個(gè)節(jié)點(diǎn)的移動(dòng)不會(huì)導(dǎo)致原來(lái)覆蓋區(qū)域的改變,這兩個(gè)節(jié)點(diǎn)就是冗余節(jié)點(diǎn)。所有這樣的冗余節(jié)點(diǎn)組成冗余節(jié)點(diǎn)集合Nr。

圖5 柵欄面的冗余節(jié)點(diǎn)

Step 4 構(gòu)造候選移動(dòng)節(jié)點(diǎn)集合Nrr

從所有節(jié)點(diǎn)中減去覆蓋節(jié)點(diǎn)集合Nc,再加上冗余節(jié)點(diǎn)集合Nr,構(gòu)成候選移動(dòng)節(jié)點(diǎn)集合Nrr。

圖6 覆蓋空洞

Step 5 找到這個(gè)垂直切面的覆蓋空洞

同樣采用文獻(xiàn)[19]的方法統(tǒng)計(jì)覆蓋空洞,計(jì)算每個(gè)空洞的面積和質(zhì)心位置。從橫坐標(biāo)最小的探測(cè)點(diǎn)開(kāi)始,采用寬度搜索和深度搜索相結(jié)合的方法。從(1,1)開(kāi)始,考察每一行,如果探測(cè)點(diǎn)(1,j)為0,標(biāo)記為空洞1,如果探測(cè)點(diǎn)(1,j+1)為0,也把這個(gè)探測(cè)點(diǎn)標(biāo)記為空洞1。依次類(lèi)推。如果空洞1的探測(cè)點(diǎn)上面的探測(cè)點(diǎn),(2,j)也為0,則此探測(cè)點(diǎn)也標(biāo)記為空洞1。這樣依次考查每一行,所有連續(xù)的未被覆蓋的探測(cè)點(diǎn)綜合起來(lái)為一個(gè)空洞,計(jì)算出空洞數(shù)量和每一個(gè)空洞面積。如圖6所示,有3個(gè)覆蓋空洞。

進(jìn)一步確定每個(gè)空洞的位置,設(shè)空洞h包含g個(gè)探測(cè)點(diǎn),第i個(gè)探測(cè)點(diǎn)的坐標(biāo)為(xi,yi),質(zhì)量為i,則空洞h的質(zhì)心坐標(biāo)可以根據(jù)式(2)來(lái)求出。

(2)

Step 6 找到每個(gè)覆蓋空洞的修補(bǔ)線段

針對(duì)每個(gè)覆蓋空洞,根據(jù)其面積和定義3進(jìn)一步確定空洞的修補(bǔ)線段。

Step 7 用最少能耗修補(bǔ)每個(gè)覆蓋空洞

Step 8 回到Step 5

重新計(jì)算柵欄面的覆蓋率,找到新的覆蓋空洞,并選擇最優(yōu)節(jié)點(diǎn)進(jìn)行修補(bǔ)。如圖6所示,藍(lán)色圓為πR2,盡管對(duì)空洞進(jìn)行了修補(bǔ),但由于空洞面積>πR2,或者不規(guī)則,覆蓋空洞仍然有部分區(qū)域不能覆蓋,這就需要重新計(jì)算覆蓋空洞,重新對(duì)其進(jìn)行修補(bǔ)。

Step 9 完成柵欄面構(gòu)建

當(dāng)所有的空洞都修補(bǔ)完成,且再也沒(méi)有覆蓋空洞,柵欄面就建立起來(lái)。計(jì)算總移動(dòng)能耗Et,平均移動(dòng)能耗Em,輸出結(jié)果。

3.2.3 算法時(shí)間復(fù)雜度

柵欄面形成過(guò)程中,需要從候選移動(dòng)節(jié)點(diǎn)集合Nrr個(gè)節(jié)點(diǎn)中選中第1個(gè)修補(bǔ)節(jié)點(diǎn),然后從(Nrr-1)個(gè)節(jié)點(diǎn)中選出第2個(gè)修補(bǔ)節(jié)點(diǎn)…以此類(lèi)推,直至柵欄形成完畢。因此在整體上,時(shí)間復(fù)雜度會(huì)隨著候選移動(dòng)集合的增加而增加。最壞情況:在形成柵欄面的過(guò)程中,感興趣三維區(qū)域內(nèi)全部N個(gè)節(jié)點(diǎn)都為候選移動(dòng)節(jié)點(diǎn)。此時(shí),時(shí)間復(fù)雜度為:O(N2)。

3.3 Rmon算法

如果去掉Step 3,僅從沒(méi)有覆蓋柵欄面的冗余節(jié)點(diǎn)中選擇移動(dòng)節(jié)點(diǎn)修補(bǔ)覆蓋空洞,雖然增加了形成柵欄的節(jié)點(diǎn)數(shù),但可以使算法簡(jiǎn)單,易于實(shí)現(xiàn),這個(gè)算法稱(chēng)為Rmon(barrier plane construction scheme based on redundant moving node)算法。

4 仿真結(jié)果分析

采用MATLAB進(jìn)行仿真。實(shí)驗(yàn)參數(shù)如表2,在邊長(zhǎng)為30 m的立方體區(qū)域內(nèi),初始投撒結(jié)60個(gè)覆蓋半徑8.7 m的節(jié)點(diǎn),柵欄面為1,節(jié)點(diǎn)的移動(dòng)能耗為1 J/m。

表2 實(shí)驗(yàn)參數(shù)

主要研究節(jié)點(diǎn)數(shù)量,節(jié)點(diǎn)半徑對(duì)算法性能的影響,考察指標(biāo)為:三維柵欄形成的總能耗,平均能耗,最大能耗,形成柵欄總節(jié)點(diǎn)個(gè)數(shù),形成柵欄的移動(dòng)節(jié)點(diǎn)個(gè)數(shù)。并比較Rmon、BinP、Bmon 3種算法的性能。

圖7 節(jié)點(diǎn)數(shù)量的影響

4.1 節(jié)點(diǎn)數(shù)量的影響

節(jié)點(diǎn)數(shù)量對(duì)三維柵欄形成的影響如圖7所示,從圖7(a),7(b)和7(e)中可以看出,隨著節(jié)點(diǎn)密度的增加,3種算法所對(duì)應(yīng)的總能耗,平均能耗和最大能耗均呈顯著性下降趨勢(shì),這是節(jié)點(diǎn)數(shù)量隨之增加,可選節(jié)點(diǎn)數(shù)量隨之增多,導(dǎo)致了節(jié)點(diǎn)移動(dòng)的距離和需要移動(dòng)的節(jié)點(diǎn)數(shù)量都下降。因?yàn)锽mon算法是先在形成柵欄面的節(jié)點(diǎn)集合內(nèi)部選擇冗余節(jié)點(diǎn)移動(dòng),再在形成柵欄面的節(jié)點(diǎn)集合外選擇節(jié)點(diǎn),修補(bǔ)所需節(jié)點(diǎn)中部分節(jié)點(diǎn)移動(dòng)距離小,所需移動(dòng)節(jié)點(diǎn)數(shù)也少,所以在各種情況下Bmon算法的總能耗和平均能耗都明顯低于BinP算法和Rmon算法。根據(jù)定理1和2,對(duì)整個(gè)柵欄面全覆蓋的節(jié)點(diǎn)數(shù)是固定的,所以BinP算法所需節(jié)點(diǎn)數(shù)量一直不變,而另外兩種算法所需節(jié)點(diǎn)數(shù)量較多。在節(jié)點(diǎn)數(shù)量較少時(shí),需要從較遠(yuǎn)處移動(dòng)節(jié)點(diǎn)來(lái)覆蓋,所以BinP算法的最大能耗低于Bmon算法和Rmon算法。從圖7(c)和7(d)中可以看出,隨著節(jié)點(diǎn)數(shù)量的增加,Bmon算法和Rmon算法形成柵欄的總節(jié)點(diǎn)數(shù)量在增加,移動(dòng)節(jié)點(diǎn)數(shù)量在降低,這是因?yàn)楣?jié)點(diǎn)數(shù)量上升時(shí),柵欄面的覆蓋率增加,需要移動(dòng)節(jié)點(diǎn)數(shù)減小。

4.2 節(jié)點(diǎn)半徑的影響

節(jié)點(diǎn)感知半徑R的影響如圖8所示。

圖8 節(jié)點(diǎn)半徑的影響

而B(niǎo)inP算法在節(jié)點(diǎn)感知半徑增加的過(guò)程中,節(jié)點(diǎn)能耗總體是下降的,但節(jié)點(diǎn)平均能耗和最大能耗在感知半徑較高時(shí)會(huì)有一個(gè)起伏。這是因?yàn)?雖然形成柵欄面所需要的節(jié)點(diǎn)數(shù)量沒(méi)有變化,但在用匈牙利算法以總能耗最小為目標(biāo)選擇最優(yōu)節(jié)點(diǎn)匹配到相應(yīng)的目標(biāo)位置時(shí),因節(jié)點(diǎn)半徑的變化,匹配關(guān)系會(huì)發(fā)生變化,從而導(dǎo)致移動(dòng)能耗發(fā)生變化,因此在BinP算法中,節(jié)點(diǎn)的平均能耗和單個(gè)節(jié)點(diǎn)的最大能耗會(huì)有一個(gè)起伏。

總之,節(jié)點(diǎn)重部署可以有效形成三維柵欄覆蓋,先從柵欄面覆蓋集合內(nèi)部選擇節(jié)點(diǎn)修補(bǔ)覆蓋空洞,再?gòu)倪@個(gè)集合外部選擇節(jié)點(diǎn)以最少能耗修補(bǔ)覆蓋空洞的Bmon算法,可以能量高效的實(shí)現(xiàn)三維柵欄。

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

本文研究了水下傳感器網(wǎng)絡(luò)的三維柵欄覆蓋增強(qiáng)策略,在覆蓋率最大的柵欄平面上找到二維覆蓋空洞,構(gòu)造此空洞的垂直修補(bǔ)線段,以能耗最小的方式重部署部分節(jié)點(diǎn)到此修補(bǔ)線段,修補(bǔ)覆蓋空洞,能量高效的實(shí)現(xiàn)三維柵欄覆蓋。

本文采用的是全向感知模型,基于有向感知模型的三維柵欄覆蓋增強(qiáng)是下一步的研究?jī)?nèi)容。

[1] Babar Shah,Kill Kim. A Survey on Three-Dimensional Wireless Ad Hoc and Sensor Networks[J]. International Journal of Distributed Sensor Networks,2014:1-20.

[2] Jiang J,Han G,Zhu C,et al. A Trust Cloud Model for Underwater Wireless Sensor Networks[J]. IEEE Communications Magazine,2017,55(3):110-116.

[3] Tomic S,Beko M,Rui D. 3-D Target Localization in Wireless Sensor Networks Using RSS and AoA Measurements[J]. IEEE Transactions on Vehicular Technology,2017,66(4):3197-3210.

[4] Luo H,Wu K,Ruby R,et al. Simulation and Experimentation Platforms for Underwater Acoustic Sensor Networks:Advancements and Challenges[J]. Acm Computing Surveys,2017,50(2):28.

[5] 郭忠文,羅漢江,洪鋒,等. 水下無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展,2010,47(3):377-389.

[6] 蔣鵬,阮斌鋒. 基于分簇的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法[J]. 電子學(xué)報(bào),2013,41(10):2067-2073.

[7] 蔣鵬,王興民. 網(wǎng)絡(luò)分層的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法[J]. 電子學(xué)報(bào),2016,44(5):1240-1246D.

[8] 黃俊杰,孫力娟,王汝傳,等. 三維水下傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,33(5):69-74.

[9] Li X,Ci L,Yang M,et al. Deploying Three-Dimensional Mobile Sensor Networks Based on Virtual Forces Algorithm[M]. Advances in Wireless Sensor Networks. Springer Berlin Heidelberg,2013:204-216.

[10] 夏娜,鄭語(yǔ)晨,杜華爭(zhēng),等. 剛性驅(qū)動(dòng)水下傳感器節(jié)點(diǎn)自組織布置[J]. 計(jì)算機(jī)學(xué)報(bào),2013,36(3):494-505.

[11] 劉惠,柴志杰,杜軍朝,等. 基于組合虛擬力的傳感器網(wǎng)絡(luò)三維空間重部署算法研究[J]. 自動(dòng)化學(xué)報(bào),2011,37(6):713-723.

[12] 何明,陳秋麗,陳希亮,等. 魚(yú)群?jiǎn)l(fā)的三維Ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)移動(dòng)優(yōu)化模型[J]. 儀器儀表學(xué)報(bào),2014,35(12):2826-2834.

[13] Samil T,Numan U,Okyay K. On Deployment of Wireless Sensors on 3-D Terrains to Maximize Sensing Coverage by Utilizing Cat Swarm Optimization With Wavelet Transform[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2014,44(1):111-120.

[14] Tian J,Zhang W,Wang G,et al. 2D K-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J]. Computer Communications,2014,4(3):31-42.

[15] Ma H,Li D Y,Chen W P,et al. Energy Efficient K-Barrier Coverage in Limited Mobile Wireless Sensor Networks[J]. Computer Communications,2012,35(14):1749-1758.

[16] 班冬松,溫俊,蔣杰,等. 移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)K-柵欄覆蓋的構(gòu)建算法[J]. 軟件學(xué)報(bào),2011,22(9):2089-2103.

[17] 王超,范興剛. 一種高效強(qiáng)K-柵欄覆蓋構(gòu)建算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(2):228-233.

[18] 任默勇,范興剛. 一種有向傳感器網(wǎng)絡(luò)柵欄覆蓋增強(qiáng)算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(7):1051-1057.

[19] 范興剛,楊靜靜,王恒. 一種無(wú)線傳感器網(wǎng)絡(luò)的概率覆蓋增強(qiáng)算法[J]. 軟件學(xué)報(bào),2016,27(2):418-431.