陶建林,苗春雨,吳鳴旦

(1.浙江工業(yè)職業(yè)技術學院,浙江 紹興 312000;2.浙江師范大學數(shù)理與信息工程學院,浙江 金華 321004;3.杭州安恒信息技術有限公司網(wǎng)絡空間安全學院,杭州 310051)

無線傳感器網(wǎng)絡柵欄覆蓋在入侵監(jiān)測方面發(fā)揮著重要的作用,如將柵欄部署在湖面,可有效監(jiān)測污水的擴散;將柵欄部署在軍事陣地前沿,可有效監(jiān)測敵人入侵等[1-2]。一般將傳感器節(jié)點隨機的部署在狹窄的帶狀區(qū)域中,將區(qū)域一分為二,其作用是有效的監(jiān)測目標是否由一個區(qū)域穿越到另一區(qū)域中,這種技術稱為無線傳感器網(wǎng)絡柵欄覆蓋[3-4]。

在無線傳感器網(wǎng)絡柵欄覆蓋領域的研究已取得豐厚的成果。柵欄覆蓋分為強柵欄覆蓋和弱柵欄覆蓋[5]。在強柵欄覆蓋方面,Wang Z等人基于異構傳感器節(jié)點,提出一種基于簇的方向柵欄圖構建柵欄,并派遣可移動節(jié)點完成柵欄間隙修復,實現(xiàn)代價最小化[6]。Silvestri S等人提出一種強k-柵欄自主覆蓋方法(MobiBar),該方法能利用設備的協(xié)調性和自我部署能力達到覆蓋要求,從而使柵欄能夠自主應對外界因素的影響[7]。由于在構建柵欄時一般通過定位系統(tǒng)或定位方法獲得傳感器節(jié)點位置信息,但位置信息存在誤差,針對該問題Wang Z等人提出一種節(jié)點位置容錯的柵欄覆蓋方法,通過分析位置誤差對柵欄覆蓋的影響,利用容錯加權柵欄圖完成柵欄構建,該柵欄構建方法更符合實際應用場景[8]。在弱柵欄覆蓋方面的研究相對較少,如Li L等人研究了一種弱K-柵欄覆蓋方法,準確的判定帶狀區(qū)域是否為弱K-柵欄覆蓋,并討論了考慮邊界情況和不考慮邊界情況的覆蓋率問題[9]。Sadeghi H等人將柵欄覆蓋問題轉為一維離散問題進行分析,提出一種基于順序的貪婪算法(OGA),實現(xiàn)最優(yōu)弱柵欄覆蓋[10]。Dobrev S等人通過研究最小化可移動節(jié)點數(shù)量、最小化平均移動距離和最小化移動的最大距離3個指標優(yōu)化傳感器網(wǎng)絡弱柵欄覆蓋,完成弱柵欄覆蓋[11]。

在水面部署柵欄具有重要的意義,目前大量的研究都是針對陸地場景構建柵欄而很少考慮水面柵欄覆蓋,水面與陸地場景不同的是在水面部署的傳感器節(jié)點會受外界因素(風、浪)干擾產生漂移情況,因此水面柵欄構建和維護的難度較高。本文提出一種水面WSN弱柵欄覆蓋方法,能有效克服節(jié)點漂移對柵欄產生的影響,實現(xiàn)水面上穩(wěn)定的弱柵欄覆蓋。

1 相關模型與假設

1.1 相關模型

①傳感器節(jié)點采用二元感知模型,以節(jié)點為圓心,感知半徑為r,當監(jiān)測目標進入感知范圍內,傳感器節(jié)點能夠監(jiān)測到目標的概率為1,否則為0,如式(1)所示,靜態(tài)傳感器節(jié)點和可移動傳感器節(jié)點的感知半徑相同。

(1)

式中:o表示傳感器節(jié)點,t表示監(jiān)測目標,d(o,t)表示傳感器節(jié)點與監(jiān)測目標的歐氏距離,Po,t表示節(jié)點監(jiān)測到目標的概率。

②在陸地上可移動節(jié)點移動1 m消耗的能量為3.6(J)[12-13],在水中可移動節(jié)點移動1m消耗的能量為3.6-C(J),C為常數(shù)。

③弱柵欄覆蓋模型如圖1(a)所示,當監(jiān)測目標沿任意與部署區(qū)域正交的穿越路徑穿越時,至少能被一個傳感器節(jié)點所感知。而在水面區(qū)域,傳感器節(jié)點可能被水波沖擊而產生漂移,導致柵欄出現(xiàn)間隙,監(jiān)測目標從該間隙穿越而不被柵欄感知,如圖1(b)所示,節(jié)點Ni、Nj發(fā)生漂移,監(jiān)測目標可通過Pa和Pb之間的區(qū)域而不被柵欄所監(jiān)測。

1.2 相關假設

①傳感器節(jié)點上搭載運動感知傳感器(加速度計),能準確感知節(jié)點是否發(fā)生位移。

②傳感器節(jié)點能利用GPS或定位算法獲得自身位置[14-15]。

③傳感器節(jié)點可直接與Sink節(jié)點進行通訊,如目前比較先進的LoRaWAN、NB-iot等傳感器網(wǎng)絡。

④假設水中沒有障礙物,可移動節(jié)點在能量充足的情況下不限制移動距離。

⑤算法選擇在水面比較平靜的情況下構建柵欄,因此在柵欄構建過程中,節(jié)點不會發(fā)生位置漂移。

圖1 弱柵欄水面覆蓋圖

2 弱柵欄構建方法

水面弱柵欄構建主要分為兩個步驟:①搜索覆蓋區(qū)域,構建分段柵欄;②利用可移動節(jié)點將相鄰子柵欄連接,完成整條柵欄的構建。

2.1 分段構建柵欄

在水面隨機均勻部署一定數(shù)量的傳感器節(jié)點,包括靜態(tài)和可移動傳感器節(jié)點,由于節(jié)點分布存在隨機性,因此在節(jié)點部署后,區(qū)域中某些位置已經形成了較短的弱柵欄。該小節(jié)介紹如何構建已經存在的子柵欄,具體算法如表1所示。

表1 子柵欄構建過程表

子柵欄構建過程:首先建立部署區(qū)域坐標系,橫坐標為X,縱坐標為Y,然后按節(jié)點橫坐標x由小到大進行排序,分別編號為n1,n2,n3,…,nnum,傳感器節(jié)點ni的坐標可表示為(xi,yi),節(jié)點ni和nj之間的橫坐標距離di,j如式(2)所示。從節(jié)點n1開始構建柵欄,判斷與節(jié)點n2之間的橫坐標距離d1,2是否小于等于2r,如果是,則將節(jié)點n1和n2加入Set數(shù)據(jù)結構B1中(Set數(shù)據(jù)結構會自動丟棄重復值)。接著沿X軸增大方向判斷與節(jié)點n2橫坐標距離最近的傳感器節(jié)點n3,如果d2,3≤2r,則將節(jié)點n2、n3存入B1中。算法繼續(xù)迭代直到發(fā)現(xiàn)節(jié)點n6和n7之間的橫坐標距離d6,7>2r,則完成一條子柵欄的構建,B1={n1,n2,n3,n4,n5,n6}表示一條子柵欄,如圖2(a)、2(b)所示。

di,j=|xi-xj|

(2)

完成柵欄B1構建后,以節(jié)點n7為起始節(jié)點,繼續(xù)構建子柵欄B2,如圖2(b)所示,直到完成部署區(qū)域內所有的子柵欄構建,如圖2(c)所示。

圖2 弱柵欄分段構建圖

圖3 子柵欄拼接圖

2.2 子柵欄拼接

2.1小節(jié)完成了部署區(qū)域中子柵欄的構建,而子柵欄之間存在間隙,如果利用可移動節(jié)點移動到子柵欄之間,將子柵欄進行拼接即可完成弱柵欄的構建。在子柵欄構建過程中首先要尋找到柵欄間隙處的待修復位置,傳感器節(jié)點移動到這些待修復位即可完成子柵欄的拼接,如圖3所示。圖中子柵欄B1和B2之間存在間隙Gap(B1,B2),可移動節(jié)點1和2移動到間隙中的待修復位即可完成兩條子柵欄的拼接。

由于部署區(qū)域中可移動節(jié)點數(shù)量有限,為保證弱柵欄構建的成功率,應可能少的使用可移動節(jié)點完成子柵欄的拼接。拼接子柵欄所需要的最少可移動節(jié)點數(shù)量如式(3)所示。

numm=「(|xj-xi|-2r)/(2r)?

(3)

式中:numm為拼接子柵欄所需的最少可移動節(jié)點數(shù)量,xi為子柵欄B1最右端節(jié)點的橫坐標,xj為子柵欄B2最左端節(jié)點橫坐標,r為傳感器節(jié)點感知半徑。

根據(jù)式(3)得到拼接兩條子柵欄最少需要的可移動節(jié)點數(shù)量,然后將間隙Gap(B1,B2)均勻劃分為numm+1,總共有numm條均勻分割線,這些分割線又稱為待修復位劃分線,因此待修復位置可以在待修復位劃分線的任何位置,只需要將可移動節(jié)點移動到所有的待修復位劃分線上,即可完成弱柵欄的構建,如圖3所示。

確定了子柵欄的待修復位置后,需要在部署區(qū)域中選擇冗余的可移動傳感器節(jié)點完成柵欄構建工作。由于可移動節(jié)點已經參與到子柵欄的構建過程中,因此在子柵欄拼接階段選擇冗余的可移動傳感器節(jié)點。冗余節(jié)點即去掉該節(jié)點不影響原本子柵欄的完整性,如圖4中可移動節(jié)點mn的感知范圍在橫坐標上的投影能被子柵欄B1中其他傳感器節(jié)點在橫坐標上的投影完全覆蓋,因此去除節(jié)點mn并不會使子柵欄B1被破壞,在算法執(zhí)行時,從兩條子柵欄間隙Gap(B1,B2)的兩側開始查找冗余可移動節(jié)點,從而確保查找到的冗余節(jié)點距離間隙更近。

圖4 冗余節(jié)點選擇圖

為降低可移動節(jié)點移動過程中的能量消耗,采用匈牙利算法派遣冗余的可移動傳感器節(jié)點到待修復位置,使得拼接子柵欄過程中可移動節(jié)點移動的距離之和最短。匈牙利算法用于任務指派問題,如指派a個工人完成a個任務,每位工人對每種收費情況不同,匈牙利算法派遣工人可以使完成所有任務的代價最小。假設可移動傳感器節(jié)點在水面不限移動距離,利用匈牙利算法派遣可移動節(jié)點到待修復位置,如果可移動節(jié)點的數(shù)量M小于待修復位置數(shù)量G,則不能完成弱柵欄的構建。如果M大于等于G,則需要虛擬處M-G個待修復位置,所有可移動節(jié)點到虛擬待修復位置的距離都為0。根據(jù)上述規(guī)則改進匈牙利算法,使之適用于WSN節(jié)點派遣問題。使用匈牙利算法最重要的是構建代價矩陣,假設拼接子柵欄B1和B2,從間隙左側開始尋找子柵欄B1中的冗余可移動節(jié)點m1和m2,從間隙右側搜尋到子柵欄B2中的冗余節(jié)點為m3,且每個冗余節(jié)點到待修復位劃分線的橫坐標距離可根據(jù)節(jié)點位置計算得到,則匈牙利算法的代價矩陣如式(4)所示,根據(jù)代價矩陣即可計算出最佳的節(jié)點派遣方式,使得連接子柵欄B1和B2的可移動節(jié)點移動距離之和最小。當所有的子柵欄都被拼接后,則完成了該區(qū)域的弱柵欄構建。

(4)

式中:矩陣第三列都為0,因為待修復位置只有2個,而有3個可移動節(jié)點能夠移動到待修復位置,因此需要虛擬一個待修復位置,所有冗余可移動節(jié)點到待修復位置的距離都為0。

圖5 可移動節(jié)點移動距離圖

3 柵欄維護

在水面部署柵欄與陸地上有較大的不同,水面部署柵欄,在受外風、波浪等外界因素的影響,即使是靜態(tài)傳感器節(jié)點也可能發(fā)生漂移,因此水面部署的柵欄需要進行難度更高的維護工作,主要包括監(jiān)測柵欄中某些節(jié)點是否產生了位置漂移而使得柵欄出現(xiàn)間隙,以及間隙出現(xiàn)后的修復工作。

圖6 柵欄沖擊圖

4 仿真實驗

實驗采用i5處理器、8G內存的PC,在MATLAB環(huán)境中進行仿真。將靜態(tài)傳感器節(jié)點和可移動傳感器節(jié)點混合后隨機均勻地部署在一個長為100 m,寬為1 000 m的水面帶狀區(qū)域中,傳感器節(jié)點的感知半徑r=30 m。

4.1 子柵欄構建

傳感器節(jié)點隨機部署在區(qū)域中已經形成了一些子柵欄,而在節(jié)點沒有覆蓋到的位置存在間隙。理論上部署的傳感器節(jié)點數(shù)量越多,則區(qū)域中存在的間隙越少,則所有間隙的長度總和越短。實驗驗證傳感器節(jié)點數(shù)量與柵欄間隙總長度之間的關系,實驗中靜態(tài)傳感器節(jié)點占60%,可移動節(jié)點占40%,結果如圖7所示,橫坐標為傳感器節(jié)點數(shù)量,縱坐標為柵欄間隙總長度(m)。

圖7 柵欄間隙長度圖

實驗結果表明隨著部署區(qū)域中傳感器節(jié)點數(shù)量則增加,柵欄間隙的長度逐漸降低。因為傳感器節(jié)點增加,部署后形成子柵欄的數(shù)量越多,則對應的間隙長度會逐漸減少。當部署的傳感器節(jié)點數(shù)量大于60個時,柵欄間隙的長度隨著節(jié)點數(shù)量增加減小的非常緩慢,因此隨著節(jié)點數(shù)量增加,冗余節(jié)點的數(shù)量增加的越來越快,實驗結果表明在部署區(qū)域中部署60個節(jié)點時最合適。當部署100個傳感器節(jié)點后,柵欄間隙的長度之和接近0。

4.2 柵欄構建成功率

柵欄的構建概率與部署的傳感器節(jié)點數(shù)量有關,還與可移動節(jié)點的比例相關。理論上部署的傳感器節(jié)點數(shù)量越多,柵欄構建的成功率越高;可移動節(jié)點比例越高,柵欄構建的成功率越高。實驗結果如圖8所示,橫坐標為部署的傳感器節(jié)點總數(shù)量,縱坐標為柵欄的構建概率,實驗分別驗證不同數(shù)量傳感器節(jié)點以及靜態(tài)、動態(tài)傳感器節(jié)點不同比例對柵欄構建率的影響。由于最近在無線傳感器網(wǎng)絡弱柵欄覆蓋方面的研究較少,因此選擇參考文獻[16]提出的方法進行對比,該方法具有較高的性能。

實驗結果表明隨著部署傳感器節(jié)點數(shù)量增加,柵欄構建概率先快速增加,當部署數(shù)量達到一定值時,柵欄構建的成功率緩慢增加,因為在初始階段,部署傳感器節(jié)點后,已經能構成弱柵欄,而當節(jié)點數(shù)量到達一定值后,大量的節(jié)點為冗余節(jié)點,不能大幅度提高柵欄構建概率。在部署傳感器節(jié)點數(shù)量相同時,隨著靜態(tài)節(jié)點占比增加,則柵欄成功構建的概率逐漸減低,因為靜態(tài)節(jié)點比例增加,可移動節(jié)點的比例降低,可移動節(jié)點比例越低,則柵欄間隙不能被完全的修復拼接,從而導致柵欄成功構建的概率降低。且本文提出的弱柵欄覆蓋方法的柵欄構建成功概率遠高于參考文獻[16]提出的弱柵欄覆蓋方法,因為參考文獻[16]提出的柵欄構建方法并沒有采用可移動傳感器節(jié)點。

當靜態(tài)節(jié)點比例為20%、40%,部署節(jié)點數(shù)量為60個時,柵欄的修復率較高,且隨著節(jié)點數(shù)量增加,柵欄修復率升高幅度逐漸平緩,因此部署60個節(jié)點時最合適。

4.3 柵欄構建能耗

能耗是柵欄構建過程中最重要的問題之一,低能耗的柵欄構建方法能夠節(jié)約大量的能量,有利于延長后期柵欄的生存時間。在柵欄構建階段主要的能量消耗是可移動節(jié)點的移動所產生的,根據(jù)第一小節(jié),移動節(jié)點移動1 m消耗的能量為3.6-C(J),C為常數(shù),實驗中C=1(J)。實驗結果如圖9所示,橫坐標為區(qū)域中部署傳感器節(jié)點的數(shù)量,縱坐標為完成柵欄構建的能量消耗。

圖9 柵欄構建能耗圖

實驗結果表明隨著部署區(qū)域中傳感器節(jié)點數(shù)量增加,構建柵欄消耗的能量逐漸降低,因為部署的傳感器節(jié)點數(shù)量越多,則柵欄間隙的長度越短,因此需要的可移動節(jié)點數(shù)量越少,而且節(jié)點和數(shù)量越多,對應的可移動傳感器節(jié)點密度越高,需要移動的平均距離越短,因此能量消耗越少。隨著靜態(tài)節(jié)點的比例增加,構建柵欄消耗的能量逐漸增加,因為可移動節(jié)點的比例降低,修復柵欄間隙時節(jié)點的平均移動距離增加,因此消耗的能量逐漸增加。

4.4 柵欄維護

在水面區(qū)域部署柵欄與陸地上存在較大的差異,水面干擾因素較多,需要柵欄能夠自主檢測是否被破壞,檢測到柵欄被破壞后需要及時與服務器段進行通訊,啟動柵欄修復方法修復被破壞的柵欄。實驗驗證柵欄維護方法的性能,在帶狀區(qū)域中總共部署100個傳感器節(jié)點,實驗結果如圖10所示。

圖10 柵欄修復成功概率圖

圖10(a)結果表明隨著柵欄損壞長度的增加,柵欄修復成功的概率逐漸降低。當靜態(tài)傳感器節(jié)點的占比增加時,柵欄成功修復的概率降低,因為靜態(tài)節(jié)點比例增加,可移動節(jié)點比例降低,能夠被派遣修復柵欄間隙的可移動節(jié)點數(shù)量降低,因此柵欄修復率降低。

圖10(b)為修復固定長度200 m的損壞柵欄實驗結果,結果表明當修復固定長度的柵欄時,隨著部署的節(jié)點數(shù)量增加,柵欄修復成功率也逐漸增加。當靜態(tài)傳感器節(jié)點的占比增加,則柵欄的修復率會降低。

5 總結

提出了一種水面弱柵欄覆蓋方法,首先在水面部署區(qū)域內搜尋已經存在的子柵欄,然后提出子柵欄拼接方法,使柵欄拼接過程中可移動節(jié)點移動距離之和最短,從而降低了柵欄構建過程中的能量消耗,最后研究了水面弱柵欄維護方法,在傳感器節(jié)點上搭載加速度傳感器,主動監(jiān)測節(jié)點位置是否發(fā)生漂移,并修復柵欄中出現(xiàn)的間隙。后續(xù)工作將進一步研究水面強柵欄覆蓋方法。