一種水面WSN弱柵欄覆蓋方法研究*

陶建林,苗春雨,吳鳴旦

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

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

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

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

1 相關(guān)模型與假設(shè)

1.1 相關(guān)模型

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

(1)

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

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

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

1.2 相關(guān)假設(shè)

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

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

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

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

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

圖1 弱柵欄水面覆蓋圖

2 弱柵欄構(gòu)建方法

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

2.1 分段構(gòu)建柵欄

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

表1 子?xùn)艡跇?gòu)建過程表

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

di,j=|xi-xj|

(2)

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

圖2 弱柵欄分段構(gòu)建圖

圖3 子?xùn)艡谄唇訄D

2.2 子?xùn)艡谄唇?/h3>

2.1小節(jié)完成了部署區(qū)域中子?xùn)艡诘臉?gòu)建,而子?xùn)艡谥g存在間隙,如果利用可移動節(jié)點移動到子?xùn)艡谥g,將子?xùn)艡谶M(jìn)行拼接即可完成弱柵欄的構(gòu)建。在子?xùn)艡跇?gòu)建過程中首先要尋找到柵欄間隙處的待修復(fù)位置,傳感器節(jié)點移動到這些待修復(fù)位即可完成子?xùn)艡诘钠唇?如圖3所示。圖中子?xùn)艡贐1和B2之間存在間隙Gap(B1,B2),可移動節(jié)點1和2移動到間隙中的待修復(fù)位即可完成兩條子?xùn)艡诘钠唇印?/p>

由于部署區(qū)域中可移動節(jié)點數(shù)量有限,為保證弱柵欄構(gòu)建的成功率,應(yīng)可能少的使用可移動節(jié)點完成子?xùn)艡诘钠唇?。拼接子?xùn)艡谒枰淖钌倏梢苿庸?jié)點數(shù)量如式(3)所示。

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

(3)

式中:numm為拼接子?xùn)艡谒璧淖钌倏梢苿庸?jié)點數(shù)量,xi為子?xùn)艡贐1最右端節(jié)點的橫坐標(biāo),xj為子?xùn)艡贐2最左端節(jié)點橫坐標(biāo),r為傳感器節(jié)點感知半徑。

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

確定了子?xùn)艡诘拇迯?fù)位置后,需要在部署區(qū)域中選擇冗余的可移動傳感器節(jié)點完成柵欄構(gòu)建工作。由于可移動節(jié)點已經(jīng)參與到子?xùn)艡诘臉?gòu)建過程中,因此在子?xùn)艡谄唇与A段選擇冗余的可移動傳感器節(jié)點。冗余節(jié)點即去掉該節(jié)點不影響原本子?xùn)艡诘耐暾?如圖4中可移動節(jié)點mn的感知范圍在橫坐標(biāo)上的投影能被子?xùn)艡贐1中其他傳感器節(jié)點在橫坐標(biāo)上的投影完全覆蓋,因此去除節(jié)點mn并不會使子?xùn)艡贐1被破壞,在算法執(zhí)行時,從兩條子?xùn)艡陂g隙Gap(B1,B2)的兩側(cè)開始查找冗余可移動節(jié)點,從而確保查找到的冗余節(jié)點距離間隙更近。

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

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

(4)

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

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

3 柵欄維護(hù)

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

圖6 柵欄沖擊圖

4 仿真實驗

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

4.1 子?xùn)艡跇?gòu)建

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

圖7 柵欄間隙長度圖

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

4.2 柵欄構(gòu)建成功率

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

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

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

4.3 柵欄構(gòu)建能耗

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

圖9 柵欄構(gòu)建能耗圖

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

4.4 柵欄維護(hù)

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

圖10 柵欄修復(fù)成功概率圖

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

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

5 總結(jié)

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