范興剛,蒿 翔,程斯顥,嚴天一

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

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

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

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

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

圖1 三維柵欄面

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

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

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

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

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

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

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

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

定義3覆蓋空洞修補線段,如果一個節(jié)點移動到穿過覆蓋空洞質(zhì)心的垂直線段上,這個空洞就可以得到最大程度的修補,這樣的垂直線段稱為空洞修補線段。

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

2 三維柵欄的理論分析

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

圖2 覆蓋區(qū)域

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

(1)

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

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

我們進一步分析三維區(qū)域中的平面覆蓋。隨機部署的節(jié)點在垂直切面ABCD上的覆蓋區(qū)域不再是大小相等的感知圓。如果某個節(jié)點正好在這個切面上,其覆蓋區(qū)域為半徑R的感知圓。如果節(jié)點到這個切面的距離小于R,其覆蓋區(qū)域為半徑小于R的感知圓。如果節(jié)點到這個切面的距離大于R,其覆蓋區(qū)域為0。

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

圖3 距離對節(jié)點感知能力的影響

定理3一個節(jié)點對一個垂直切面上的覆蓋空洞的最小修補區(qū)域為0,最大為πR2。

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

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

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

3.1 BinP算法

3.2 Bmon算法

BinP算法雖然可以形成柵欄面,但需要很多節(jié)點移動到目標位置,導致較大能耗。為了減少能耗,提高效率,我們先找到覆蓋空洞,再選擇節(jié)點修補覆蓋空洞,完成柵欄面構(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é)點Nbm構(gòu)成柵欄面的移動節(jié)點Nc覆蓋柵欄面的節(jié)點集合Nr覆蓋柵欄面的冗余節(jié)點集合Nrr修補空洞的節(jié)點集合Nrr/min修補空洞的當前節(jié)點lr修補線段Jm移動單位能耗

3.2.2 算法基本過程

Bmon算法的具體步驟如下:

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

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

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

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

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

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

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

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

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

圖6 覆蓋空洞

Step 5 找到這個垂直切面的覆蓋空洞

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

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

(2)

Step 6 找到每個覆蓋空洞的修補線段

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

Step 7 用最少能耗修補每個覆蓋空洞

Step 8 回到Step 5

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

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

當所有的空洞都修補完成,且再也沒有覆蓋空洞,柵欄面就建立起來。計算總移動能耗Et,平均移動能耗Em,輸出結(jié)果。

3.2.3 算法時間復雜度

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

3.3 Rmon算法

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

4 仿真結(jié)果分析

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

表2 實驗參數(shù)

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

本文采用的是全向感知模型,基于有向感知模型的三維柵欄覆蓋增強是下一步的研究內(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ǎng)絡(luò)的研究進展[J]. 計算機研究與發(fā)展,2010,47(3):377-389.

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

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

[8] 黃俊杰,孫力娟,王汝傳,等. 三維水下傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J]. 南京郵電大學學報(自然科學版),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] 夏娜,鄭語晨,杜華爭,等. 剛性驅(qū)動水下傳感器節(jié)點自組織布置[J]. 計算機學報,2013,36(3):494-505.

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

[12] 何明,陳秋麗,陳希亮,等. 魚群啟發(fā)的三維Ad hoc網(wǎng)絡(luò)節(jié)點隨機移動優(yōu)化模型[J]. 儀器儀表學報,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] 班冬松,溫俊,蔣杰,等. 移動無線傳感器網(wǎng)絡(luò)K-柵欄覆蓋的構(gòu)建算法[J]. 軟件學報,2011,22(9):2089-2103.

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

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

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