王 涌,黃留信,紀(jì)專凱,沈鵬飛,朱濤濤

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

1 引 言

無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋在入侵檢測(cè)等諸多領(lǐng)域都有著廣泛的用途,如可將傳感器網(wǎng)絡(luò)部署在工廠周?chē)?利用柵欄感知環(huán)境從而發(fā)現(xiàn)污染物的擴(kuò)散;在現(xiàn)代化軍事領(lǐng)域,將柵欄部署在敵我陣地前沿,檢測(cè)敵人入侵從而避免造成重大損失[1,2].將無(wú)線傳感器節(jié)點(diǎn)隨機(jī)或有規(guī)律的部署到帶狀區(qū)域內(nèi),利用相關(guān)算法形成一條感知范圍重疊的柵欄,該柵欄將區(qū)域一分為二,從而能夠有效發(fā)現(xiàn)是否有入侵目標(biāo)從區(qū)域的一側(cè)穿越到另外一側(cè),該技術(shù)被稱為WSN柵欄覆蓋[3,4].目前大部分普通傳感器節(jié)點(diǎn)僅能在干燥的環(huán)境下工作,而在水中則會(huì)失效,從而導(dǎo)致柵欄失去功能,因此研究一種晴雨天都適用的柵欄覆蓋方法具有重要意義[5].

目前國(guó)內(nèi)外學(xué)者在WSN柵欄覆蓋領(lǐng)域做了大量的研究工作,其中在柵欄構(gòu)建算法方面的研究如參考文獻(xiàn)[6]采用異構(gòu)傳感器節(jié)點(diǎn)并利用基于簇的方向柵欄圖理論實(shí)現(xiàn)柵欄構(gòu)建,針對(duì)柵欄構(gòu)建過(guò)程中存在間隙問(wèn)題,通過(guò)派遣可移動(dòng)節(jié)點(diǎn)修復(fù),使得修復(fù)能耗最低.參考文獻(xiàn)[7]針對(duì)柵欄不能自適應(yīng)各種部署環(huán)境問(wèn)題,提出了一種強(qiáng)k-柵欄自主覆蓋方法,利用協(xié)同感知方法讓傳感器節(jié)點(diǎn)間能夠協(xié)同起來(lái),實(shí)現(xiàn)柵欄自我部署的目的.在構(gòu)建柵欄過(guò)程中大量的算法首先需要獲得傳感器節(jié)點(diǎn)自身的位置,常見(jiàn)的技術(shù)包括GPS定位、WSN定位算法等,但柵欄一般部署在遮擋物較多的環(huán)境中,定位信號(hào)受到遮擋導(dǎo)致定位結(jié)果不準(zhǔn)確,最終會(huì)導(dǎo)致柵欄構(gòu)建存在間隙.針對(duì)該問(wèn)題參考文獻(xiàn)[8]研究了一種傳感器節(jié)點(diǎn)位置容錯(cuò)的柵欄構(gòu)建方法,利用容錯(cuò)加權(quán)柵欄圖方法解決節(jié)點(diǎn)位置飄移從而導(dǎo)致柵欄構(gòu)建不完善問(wèn)題.在柵欄間隙修復(fù)方面的研究如參考文獻(xiàn)[9]提出柵欄間隙的尋找方法,并利用最大流算法和二分法對(duì)柵欄間隙進(jìn)行修復(fù),使修復(fù)代價(jià)最小.參考文獻(xiàn)[10]針對(duì)間隙修復(fù)復(fù)雜度高等問(wèn)題,利用鄰居可移動(dòng)節(jié)點(diǎn)集合降低了 修復(fù)算法的復(fù)雜度.參考文獻(xiàn)[11]通過(guò)建立入侵軌跡模型預(yù)測(cè)入侵者穿越柵欄時(shí)的位置,并將可移動(dòng)節(jié)點(diǎn)移動(dòng)到頻繁穿越位置強(qiáng)化柵欄,防止出現(xiàn)柵欄間隙.參考文獻(xiàn)[12]研究了一種混合傳感器網(wǎng)絡(luò)柵欄間隙修復(fù)方法,假設(shè)傳感器節(jié)點(diǎn)的感知范圍可調(diào),利用移動(dòng)節(jié)點(diǎn)修復(fù)柵欄使得移動(dòng)距離最短.參考文獻(xiàn)[13]根據(jù)節(jié)點(diǎn)間距離查找柵欄間隙,并通過(guò)旋轉(zhuǎn)柵欄中關(guān)鍵傳感器節(jié)點(diǎn)或一段柵欄修復(fù)柵欄間隙.

雖然傳統(tǒng)的柵欄覆蓋方法能夠滿足多種條件下的應(yīng)用要求,但未充分考慮晴天和雨天場(chǎng)景下柵欄適用問(wèn)題.本文根據(jù)節(jié)點(diǎn)在不同天氣下的特性,研究了一種適用于晴天和雨天兩種場(chǎng)景自由切換的柵欄覆蓋方法,且在構(gòu)建柵欄過(guò)程中基于能耗優(yōu)先原則從而使得構(gòu)建的柵欄具有較好的魯棒性.

2 相關(guān)模型

a)普通傳感器節(jié)點(diǎn)為靜態(tài)節(jié)點(diǎn),且僅能在晴天狀況下正常工作,當(dāng)節(jié)點(diǎn)被打濕后功能失效,節(jié)點(diǎn)干燥后恢復(fù)正常功能.增強(qiáng)傳感器節(jié)點(diǎn)可同時(shí)在雨天和晴天狀態(tài)下工作且可移動(dòng),具有較強(qiáng)的移動(dòng)能力.兩種傳感器節(jié)點(diǎn)都能根據(jù)Gps技術(shù)或定位算法獲得自身位置.

b)本文節(jié)點(diǎn)采用二元感知模型,該模型以傳感器節(jié)點(diǎn)位置為圓心,以半徑r的圓形區(qū)域?yàn)楦兄秶?感知概率如公式(1)所示.

(1)

公式(1)中o為傳感器節(jié)點(diǎn)位置,s為入侵目標(biāo)位置,d(o,s)為傳感器節(jié)點(diǎn)和入侵目標(biāo)的歐氏距離,Po,s表示節(jié)點(diǎn)感知到入侵目標(biāo)的概率.

c)增強(qiáng)傳感器節(jié)點(diǎn)在移動(dòng)時(shí)消耗的能量遠(yuǎn)遠(yuǎn)高于感知消耗的能量,因此其感知過(guò)程消耗的能量忽略不計(jì),且移動(dòng)過(guò)程消耗的能量與移動(dòng)距離呈正比,移動(dòng)1m消耗的能量為3.6J[14,15].

3 柵欄構(gòu)建

本章主要介紹一種k-柵欄構(gòu)建方法,通過(guò)該方法構(gòu)建的柵欄能夠在晴天和雨天狀況下正常工作.首先根據(jù)需要構(gòu)建柵欄的數(shù)量將監(jiān)測(cè)區(qū)域均勻劃分為k個(gè)子區(qū)域,然后在每個(gè)子區(qū)域內(nèi)構(gòu)建1條晴雨天都適用的復(fù)合型柵欄.

3.1 區(qū)域劃分

在初始時(shí)刻,將普通傳感器節(jié)點(diǎn)和增強(qiáng)傳感器節(jié)點(diǎn)按一定比例混合后隨機(jī)均勻的部署到監(jiān)測(cè)區(qū)域中,并對(duì)監(jiān)測(cè)區(qū)域進(jìn)行劃分,理論上每個(gè)子區(qū)域內(nèi)包含的傳感器節(jié)點(diǎn)數(shù)量接近,然后在子區(qū)域內(nèi)構(gòu)建柵欄,且子區(qū)域內(nèi)的節(jié)點(diǎn)僅供該區(qū)域柵欄構(gòu)建使用,如圖1所示.

圖1 區(qū)域分割圖Fig.1 Area segmentation diagram

在子區(qū)域內(nèi)如何構(gòu)建柵欄使得代價(jià)最小是重點(diǎn)研究問(wèn)題.在構(gòu)建柵欄過(guò)程中應(yīng)盡可能降低柵欄間隙的數(shù)量和長(zhǎng)度,從而提高柵欄構(gòu)建的成功率.本文研究的柵欄構(gòu)建方法主要分為三個(gè)步驟:1)傳感器節(jié)點(diǎn)簇查找;2)最優(yōu)柵欄構(gòu)建路徑選擇;3)增強(qiáng)節(jié)點(diǎn)派遣;具體方法如下所示.

3.2 節(jié)點(diǎn)簇查找

在監(jiān)測(cè)區(qū)域中,隨機(jī)部署一定數(shù)量的傳感器節(jié)點(diǎn),如果兩個(gè)傳感器節(jié)點(diǎn)的感知范圍存在重疊的情況,則認(rèn)為這兩個(gè)傳感器節(jié)點(diǎn)組成一個(gè)簇.在該階段利用深度優(yōu)先搜索算法查找每個(gè)子區(qū)域中所有的傳感器節(jié)點(diǎn)簇.搜索過(guò)程如圖2所示.

圖2 子區(qū)域成簇過(guò)程圖Fig.2 Sub-region clustering process diagram

從子區(qū)域的最左側(cè)開(kāi)始搜索,首先被查找到的是節(jié)點(diǎn)a,將a壓入棧中,然后判斷是否存在傳感器節(jié)點(diǎn)與a的感知范圍存在重疊,經(jīng)遍歷發(fā)現(xiàn)與a感知重疊的節(jié)點(diǎn)為b,依次用同樣的方法直到搜索到d后發(fā)現(xiàn)沒(méi)有其他節(jié)點(diǎn)與其存在感知重疊,則第一個(gè)簇查找結(jié)束,由{a、b、c、d}組成,簇頭為a節(jié)點(diǎn),簇尾為d節(jié)點(diǎn).接著從節(jié)點(diǎn)d開(kāi)始查找,搜索距離子區(qū)域左邊界最近的節(jié)點(diǎn),搜索結(jié)果為k,且沒(méi)有任何節(jié)點(diǎn)與它存在感知重疊,因此第二個(gè)簇由一個(gè)節(jié)點(diǎn){k}組成,則該簇的簇頭和簇尾都為節(jié)點(diǎn)k.第三個(gè)簇從節(jié)點(diǎn)e開(kāi)始,按深度搜索方法,遍歷的步驟為e→f→g→h,其中h作為其中一個(gè)簇尾,然后算法返回到f節(jié)點(diǎn),繼續(xù)遍歷到節(jié)點(diǎn)i和節(jié)點(diǎn)j,節(jié)點(diǎn)j作為另一個(gè)簇尾.

3.3 最優(yōu)構(gòu)建路徑

在子區(qū)域內(nèi)完成簇的遍歷后,應(yīng)盡可能利用已經(jīng)形成的簇來(lái)構(gòu)建柵欄,通過(guò)在簇之間填充增強(qiáng)型節(jié)點(diǎn),實(shí)現(xiàn)子區(qū)域內(nèi)的柵欄構(gòu)建,如圖3所示,將增強(qiáng)節(jié)點(diǎn)1、2、3、4派遣到簇1、2、3之間,將簇連接起來(lái)完成整個(gè)柵欄的構(gòu)建.

圖3 簇構(gòu)建柵欄過(guò)程圖Fig.3 Cluster construction barrier process diagram

但在子區(qū)域內(nèi)簇的數(shù)量較大,如何選擇最合適的簇來(lái)構(gòu)建柵欄使得需要增強(qiáng)節(jié)點(diǎn)(可移動(dòng))的數(shù)量最少是難點(diǎn).需要增強(qiáng)節(jié)點(diǎn)的數(shù)量越少,理論上完成柵欄構(gòu)建的概率越高.本文提出一種基于增強(qiáng)節(jié)點(diǎn)需求拓?fù)浣Y(jié)構(gòu)圖和最短路徑方法實(shí)現(xiàn)最優(yōu)柵欄構(gòu)建路徑的選擇.根據(jù)簇構(gòu)建拓?fù)浣Y(jié)構(gòu)的過(guò)程如下:首先添加2個(gè)虛擬節(jié)點(diǎn),start和end,分別位于監(jiān)測(cè)區(qū)域的左右邊界中心位置,然后將子區(qū)域內(nèi)不同簇的簇頭和簇尾相互之間兩兩連接,完成拓?fù)鋱D的構(gòu)建.拓?fù)鋱D中邊的權(quán)重為連接兩個(gè)簇所需要的增強(qiáng)節(jié)點(diǎn)數(shù)量numi,j,如公式(2)所示.

numi,j=0,d(i,j)-2r≤0d(i,j)-2r2r,d(i,j)-2r>0 (2)

公式(2)中d(i,j)表示兩個(gè)簇之間的歐氏距離,r為節(jié)點(diǎn)感知半徑.

假設(shè)子區(qū)域內(nèi)建立的增強(qiáng)節(jié)點(diǎn)需求拓?fù)鋱D如圖4所示,完成拓?fù)浣Y(jié)構(gòu)建立后即可進(jìn)行最優(yōu)柵欄構(gòu)建路徑的選擇.利用最短路徑算法(如Dijkstra算法)選擇圖4中從start節(jié)點(diǎn)到end節(jié)點(diǎn)的最短路徑即為最優(yōu)柵欄構(gòu)建路徑,且路徑長(zhǎng)度為構(gòu)建柵欄需要的增強(qiáng)節(jié)點(diǎn)數(shù)量.選擇該拓?fù)鋱D中最短路徑上的簇構(gòu)建柵欄需要的增強(qiáng)節(jié)點(diǎn)數(shù)量最少.

圖4 增強(qiáng)節(jié)點(diǎn)需求拓?fù)鋱DFig.4 Enhanced node requirements topology

3.4 復(fù)合型柵欄構(gòu)建

本文3.3小節(jié)介紹了最優(yōu)柵欄構(gòu)建路徑的選擇,本文介紹構(gòu)建復(fù)合型的柵欄,能夠同時(shí)滿足晴天和雨天狀況下的正常工作要求.在晴天狀況下,構(gòu)建柵欄比較簡(jiǎn)單,僅需要派遣增強(qiáng)節(jié)點(diǎn)到3.3小節(jié)選擇出的最優(yōu)柵欄構(gòu)建路徑間隙處即可完成柵欄的構(gòu)建.但雨天柵欄的構(gòu)建涉及到增強(qiáng)節(jié)點(diǎn)的派遣.本文提出一種柵欄分割的方法,如圖5所示,假設(shè)晴天柵欄已構(gòu)建完成, 如果將晴天柵欄中的普通傳感器節(jié)點(diǎn)替換為增強(qiáng)節(jié)點(diǎn),則該柵欄即可在雨天正常工作.首先從左到右掃描柵欄,如果是增強(qiáng)節(jié)點(diǎn),則作為一個(gè)分界線,按上述方法將柵欄進(jìn)行劃分,劃分后每個(gè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)都為普通傳感器節(jié)點(diǎn),然后計(jì)算每個(gè)區(qū)域內(nèi)普通傳感器節(jié)點(diǎn)的數(shù)量.如區(qū)域a中的柵欄有1個(gè)普通傳感器節(jié)點(diǎn)和1個(gè)空閑的增強(qiáng)傳感器節(jié)點(diǎn),則該增強(qiáng)節(jié)點(diǎn)可移動(dòng)到普通傳感器節(jié)點(diǎn)位置完成該段柵欄的復(fù)合化.區(qū)域b中的柵欄共有2個(gè)普通節(jié)點(diǎn),但只有一個(gè)空閑的增強(qiáng)節(jié)點(diǎn),無(wú)法完全柵欄復(fù)合化,因此將區(qū)域b和區(qū)域c進(jìn)行合并,合并后變成區(qū)域e,如圖5(b)所示,區(qū)域e中的柵欄共有5個(gè)普通節(jié)點(diǎn),且區(qū)域中剛好有5個(gè)增強(qiáng)節(jié)點(diǎn),因此能夠完成區(qū)域e中的柵欄普通節(jié)點(diǎn)的復(fù)合化.按上述方法對(duì)柵欄進(jìn)行切分,然后派遣增強(qiáng)節(jié)點(diǎn)到普通節(jié)點(diǎn)位置,即可構(gòu)建一條雨天狀況下適用的柵欄.

圖5 區(qū)域合并圖Fig.5 Area merge diagram

4 最優(yōu)派遣

匈牙利算法是一種最優(yōu)指派算法,假設(shè)派遣n個(gè)工人去做n個(gè)工作,每個(gè)工人可同時(shí)能做若干種任務(wù),但每個(gè)任務(wù)只能派遣1個(gè)工人,而每個(gè)工人對(duì)不同任務(wù)的熟練程度不同,即完成時(shí)間不同.匈牙利算法能夠最優(yōu)的指派人員去做相應(yīng)的工作,使完成所有工作花費(fèi)的時(shí)間總和最短.將增強(qiáng)節(jié)點(diǎn)的派遣問(wèn)題類比到人員指派問(wèn)題,上文中晴天和雨天柵欄的構(gòu)建過(guò)程中都涉及到增強(qiáng)節(jié)點(diǎn)的派遣,為盡可能降低柵欄構(gòu)建過(guò)程中的能量消耗,因盡可能降低增強(qiáng)節(jié)點(diǎn)的移動(dòng)距離.假設(shè)派遣x個(gè)增強(qiáng)節(jié)點(diǎn)到y(tǒng)個(gè)指定位置,但x與y的值不一定相等,因此利用“加邊補(bǔ)零法”對(duì)傳統(tǒng)的匈牙利算法進(jìn)行改進(jìn),使之適用于不完全指派問(wèn)題[16,17],如圖6所示.假設(shè)實(shí)際有2個(gè)位置需要分配增強(qiáng)節(jié)點(diǎn),但增強(qiáng)節(jié)點(diǎn)的數(shù)量為3,分別為v1、v2、v3,由于位置數(shù)量少于增強(qiáng)節(jié)點(diǎn)的數(shù)量,因此虛擬出一個(gè)位置o,所有增強(qiáng)節(jié)點(diǎn)到虛擬位置o的歐式距離都為0,增強(qiáng)節(jié)點(diǎn)與實(shí)際位置的距離可用di,j表示,i表示增強(qiáng)節(jié)點(diǎn)的編號(hào),j表示位置編號(hào).根據(jù)“加邊補(bǔ)零法”構(gòu)建匈牙利算法代價(jià)矩陣,如公式(3)所示.

圖6 匈牙利最優(yōu)派遣圖Fig.6 Hungary′s best dispatch map

(3)

構(gòu)建相應(yīng)的代價(jià)矩陣后,根據(jù)傳統(tǒng)的匈牙利算法步驟即可最優(yōu)的派遣增強(qiáng)節(jié)點(diǎn)到指定的位置,使得整個(gè)派遣過(guò)程中增強(qiáng)節(jié)點(diǎn)的移動(dòng)距離總和最短,從而實(shí)現(xiàn)總能耗最低的目的.

在構(gòu)建晴天柵欄時(shí),主要派遣增強(qiáng)節(jié)點(diǎn)到簇的間隙處,將不同簇連接起來(lái),實(shí)現(xiàn)柵欄的構(gòu)建,如圖7所示.首先將簇1和簇2的間隙用直線連接, 然后根據(jù)公式(2)計(jì)算連接2個(gè)簇需要的增強(qiáng)節(jié)點(diǎn)數(shù)量num,接著在間隙處均勻確定num個(gè)位置,最后基于匈牙利派遣方法將增強(qiáng)節(jié)點(diǎn)派遣到相應(yīng)位置.利用該方法可完成晴天柵欄的構(gòu)建.

圖7 簇連接圖Fig.7 Cluster connection diagram

晴天柵欄構(gòu)建完成后,只需利用3.4小節(jié)的柵欄劃分方法分段派遣增強(qiáng)節(jié)點(diǎn)到普通節(jié)點(diǎn)位置即可完成雨天柵欄的構(gòu)建.

5 實(shí)驗(yàn)分析

本文采用MATLAB軟件進(jìn)行仿真實(shí)驗(yàn),并采用i7的處理器和8G內(nèi)存的電腦作為硬件支撐.在一個(gè)長(zhǎng)、寬分別為300m和1000m的矩形帶狀區(qū)域內(nèi)隨機(jī)均勻地部署普通傳感器節(jié)點(diǎn)和增強(qiáng)傳感器節(jié)點(diǎn),傳感器節(jié)點(diǎn)的感知半徑r=30m.在監(jiān)測(cè)區(qū)域中構(gòu)建3條復(fù)合型柵欄(能滿足晴雨天工作的柵欄),通過(guò)對(duì)比參考文獻(xiàn)[18]和文獻(xiàn)[19]結(jié)合的柵欄構(gòu)建方法Flow和貪婪算法Greedy,驗(yàn)證本文算法(HCBC)的性能.Flow方法和Greedy方法利用普通傳感器節(jié)點(diǎn)完成基礎(chǔ)柵欄的構(gòu)建,并派遣增強(qiáng)節(jié)點(diǎn)修復(fù)柵欄間隙,實(shí)現(xiàn)柵欄構(gòu)建.

5.1 柵欄覆蓋率

柵欄構(gòu)建算法的主要目的是盡可能完整的構(gòu)建柵欄,因此柵欄覆蓋率是柵欄構(gòu)建算法的重要指標(biāo)之一.柵欄覆蓋率是指完成構(gòu)建的柵欄在矩形監(jiān)測(cè)區(qū)域水平方向上的投影與監(jiān)測(cè)區(qū)域水平方向長(zhǎng)度的比值.如果構(gòu)建的柵欄沒(méi)有間隙,能夠完全覆蓋監(jiān)測(cè)區(qū)域,則柵欄覆蓋率為100%.實(shí)驗(yàn)中在監(jiān)測(cè)區(qū)域中部署250個(gè)傳感器節(jié)點(diǎn),其中普通節(jié)點(diǎn)和增強(qiáng)節(jié)點(diǎn)按一定比例混合,實(shí)驗(yàn)驗(yàn)證不同混合比例情況對(duì)柵欄覆蓋率的影響.針對(duì)Flow柵欄覆蓋算法和貪婪算法Greedy,增強(qiáng)節(jié)點(diǎn)視為可移動(dòng)節(jié)點(diǎn),普通節(jié)點(diǎn)視為靜態(tài)節(jié)點(diǎn),實(shí)驗(yàn)結(jié)果如圖8、圖9所示,圖8為構(gòu)建晴天柵欄的覆蓋率,圖9為構(gòu)建雨天柵欄的覆蓋率,橫坐標(biāo)為普通節(jié)點(diǎn)與增強(qiáng)節(jié)點(diǎn)的混合比例,縱坐標(biāo)為柵欄總體覆蓋率.

圖8 晴天柵欄構(gòu)建覆蓋率Fig.8 Sunny barrier construction coverage

實(shí)驗(yàn)結(jié)果表明構(gòu)建晴天柵欄時(shí),隨著增強(qiáng)節(jié)點(diǎn)比例的提高,柵欄平均覆蓋率也隨之提高.且本文提出的HCBC方法覆蓋率高于Flow方法,Greedy的覆蓋率最低,且當(dāng)節(jié)點(diǎn)比例為1∶1時(shí),HCBC方法的柵欄覆蓋率比Greedy方法提高了59.1%,因?yàn)殡S著增強(qiáng)節(jié)點(diǎn)比例提高,可被派遣的增強(qiáng)節(jié)點(diǎn)數(shù)量增加,能修復(fù)柵欄間隙的概率也會(huì)提高,所以覆蓋率逐漸增加.HCBC方法在構(gòu)建柵欄過(guò)程中能夠利用增強(qiáng)節(jié)點(diǎn),且利用匈牙利算法能夠?qū)崿F(xiàn)最優(yōu)派遣,而Flow和Greedy方法在構(gòu)建柵欄時(shí)僅用到靜態(tài)節(jié)點(diǎn)(普通節(jié)點(diǎn)),只有在間隙修復(fù)是用到了移動(dòng)節(jié)點(diǎn)(增強(qiáng)節(jié)點(diǎn)),因此構(gòu)建的柵欄覆蓋率低于HCBC方法.在構(gòu)建雨天柵欄時(shí),HCBC方法構(gòu)建的柵欄覆蓋率高于Flow和Greedy,且當(dāng)節(jié)點(diǎn)比例為1∶1時(shí),HCBC方法的柵欄覆蓋率比Greedy方法提高了51.6%.因?yàn)镕low方法采用二分法派遣移動(dòng)節(jié)點(diǎn)(增強(qiáng)節(jié)點(diǎn)),只能算是逼近最優(yōu)派遣,Greedy方法僅派遣最近節(jié)點(diǎn),容易陷入局部最優(yōu)問(wèn)題,而本文提出的HCBC方法能夠?qū)崿F(xiàn)最優(yōu)派遣.綜上所述,本文方法在構(gòu)建晴雨天柵欄時(shí),平均覆蓋率比Greedy提高了55.35%.

圖9 雨天柵欄構(gòu)建覆蓋率Fig.9 Rainy day barrier construction coverage

5.2 平均移動(dòng)距離

在構(gòu)建柵欄過(guò)程中往往需要利用增強(qiáng)節(jié)點(diǎn)對(duì)間隙進(jìn)行修復(fù)才能夠構(gòu)建強(qiáng)k-柵欄.理論上構(gòu)建柵欄的平均移動(dòng)距離越短,則消耗的能量越少,越有利于柵欄后期的長(zhǎng)期生存.本實(shí)驗(yàn)在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)均勻部署300個(gè)傳感器節(jié)點(diǎn),通過(guò)調(diào)整普通節(jié)點(diǎn)和增強(qiáng)節(jié)點(diǎn)的混合比例驗(yàn)證柵欄構(gòu)建時(shí)增強(qiáng)節(jié)點(diǎn)的平均移動(dòng)距離.實(shí)驗(yàn)結(jié)果如圖10、圖11所示,圖10為構(gòu)建晴天柵欄的實(shí)驗(yàn)結(jié)果,圖11為構(gòu)建雨天柵欄的實(shí)驗(yàn)結(jié)果,橫坐標(biāo)為普通節(jié)點(diǎn)和增強(qiáng)節(jié)點(diǎn)的比例,縱坐標(biāo)為增強(qiáng)節(jié)點(diǎn)的平均移動(dòng)距離.

圖10 晴天柵欄平均移動(dòng)距離Fig.10 Average moving distance of sunny barrier

實(shí)驗(yàn)結(jié)果表明隨著增強(qiáng)節(jié)點(diǎn)比例的逐漸提高,晴天和雨天柵欄構(gòu)建時(shí)增強(qiáng)節(jié)點(diǎn)的平均移動(dòng)距離逐漸降低,因?yàn)樵鰪?qiáng)節(jié)點(diǎn)數(shù)量增加,則柵欄間隙位置附近有更大概率存在增強(qiáng)節(jié)點(diǎn),而無(wú)需去更遠(yuǎn)的地方派遣.在晴天柵欄構(gòu)建時(shí),當(dāng)增強(qiáng)節(jié)點(diǎn)比例低于1∶3時(shí),Flow的平均移動(dòng)距離低于HCBC方法,而HCBC方法的平均移動(dòng)距離高于Greedy方法,因?yàn)樵谠鰪?qiáng)節(jié)點(diǎn)比例不高時(shí),HCBC方法構(gòu)建柵欄是使用了部分增強(qiáng)節(jié)點(diǎn),導(dǎo)致空閑的增強(qiáng)節(jié)點(diǎn)密度低于Flow方法,因此平均移動(dòng)距離會(huì)略高于Flow方法,而Greedy每次都派遣最近的節(jié)點(diǎn)構(gòu)建柵欄,在增強(qiáng)節(jié)點(diǎn)密度不高時(shí),容易陷入局部最優(yōu)問(wèn)題.當(dāng)增強(qiáng)節(jié)點(diǎn)的比例提高時(shí),HCBC方法的平均移動(dòng)距離低于Flow和Greedy方法,因?yàn)楫?dāng)增強(qiáng)節(jié)點(diǎn)密度提高,柵欄間隙附近有足夠的增強(qiáng)節(jié)點(diǎn)可用于構(gòu)建柵欄,而HCBC方法實(shí)現(xiàn)了最優(yōu)派遣.在構(gòu)建雨天柵欄時(shí),隨著增強(qiáng)節(jié)點(diǎn)比例的提高,三種方法的平均移動(dòng)距離都降低.其中Flow方法的平均移動(dòng)距離最低,其次是HCBC方法,平均移動(dòng)距離最高的是Greedy方法,因?yàn)镕low在構(gòu)建柵欄過(guò)程中僅用了靜態(tài)節(jié)點(diǎn)(普通節(jié)點(diǎn)),而HCBC方法使用了部分增強(qiáng)節(jié)點(diǎn),因此Flow方法構(gòu)建柵欄后空閑的增強(qiáng)節(jié)點(diǎn)密度要略高于HCBC,因此平均移動(dòng)距離低于HCBC方法.

圖11 雨天柵欄平均移動(dòng)距離Fig.11 Average distance of rain barrier

5.3 柵欄構(gòu)建總能耗

柵欄構(gòu)建消耗的能量不僅與節(jié)點(diǎn)的平均移動(dòng)距離有關(guān),還與節(jié)點(diǎn)的移動(dòng)數(shù)量有關(guān).本文設(shè)計(jì)HCBC方法的主要目的是盡可能低的降低柵欄構(gòu)建能耗.本實(shí)驗(yàn)在監(jiān)測(cè)區(qū)域內(nèi)部署300個(gè)傳感器節(jié)點(diǎn),其中普通節(jié)點(diǎn)和增強(qiáng)節(jié)點(diǎn)按一定比例混合,驗(yàn)證在柵欄構(gòu)建過(guò)程中的總能耗.實(shí)驗(yàn)結(jié)果如圖12、圖13所示,其中圖12為晴天柵欄構(gòu)建過(guò)程中的總能耗,圖13為雨天柵欄構(gòu)建過(guò)程中的總能耗.橫坐標(biāo)為普通節(jié)點(diǎn)與增強(qiáng)節(jié)點(diǎn)的比例,縱坐標(biāo)為總能耗.節(jié)點(diǎn)移動(dòng)過(guò)程消耗的能量可參考本文第2章節(jié)的移動(dòng)能耗模型.

圖12 晴天柵欄構(gòu)建總能耗Fig.12 Energy consumption of the sunny barrier construction

實(shí)驗(yàn)結(jié)果表明隨著增強(qiáng)節(jié)點(diǎn)比例的提高,本文提出的HCBC方法消耗的總能量逐漸減低,而Flow和Greedy方法消耗的能量逐漸提高.因?yàn)镠CBC方法在初始構(gòu)建晴天柵欄時(shí)能夠利用增強(qiáng)節(jié)點(diǎn),因此增強(qiáng)節(jié)點(diǎn)混合比例的提高不影響柵欄構(gòu)建,但隨著增強(qiáng)節(jié)點(diǎn)比例增加,平均移動(dòng)距離會(huì)逐漸減低,因?yàn)榭偰芎闹饾u降低,而Flow和Greedy方法構(gòu)建柵欄時(shí)僅利用靜態(tài)節(jié)點(diǎn)(普通節(jié)點(diǎn)),當(dāng)增強(qiáng)節(jié)點(diǎn)的比例提高時(shí),普通節(jié)點(diǎn)比例會(huì)降低,初步構(gòu)建柵欄后有大量的間隙需要派遣可移動(dòng)節(jié)點(diǎn)去修復(fù),因此部署區(qū)域中增強(qiáng)節(jié)點(diǎn)的比例提高,消耗的能量越大.雨天柵欄構(gòu)建過(guò)程中隨著增強(qiáng)節(jié)點(diǎn)比例的提升,三種方法的柵欄構(gòu)建總能耗逐漸降低,因?yàn)樵鰪?qiáng)節(jié)點(diǎn)比例提高,增強(qiáng)節(jié)點(diǎn)派遣到柵欄中普通節(jié)點(diǎn)位置的距離會(huì)逐漸減小,因此總能耗逐漸降低,且能耗最低的是Flow方法,其次是HCBC方法,能耗最高的是Greedy方法.

圖13 雨天柵欄構(gòu)建總能耗Fig.13 Energy consumption of rainy day barrier construction

5.4 實(shí)物實(shí)驗(yàn)

柵欄覆蓋可應(yīng)用于軍事領(lǐng)域,能有效監(jiān)測(cè)敵人入侵.在陣地前沿部署無(wú)線傳感器網(wǎng)絡(luò)柵欄,當(dāng)敵人試圖穿越柵欄時(shí)能被發(fā)現(xiàn)并發(fā)出警報(bào).本實(shí)驗(yàn)以竹林為實(shí)際場(chǎng)景部署300m長(zhǎng)的柵欄,用于監(jiān)測(cè)入侵者,采用的傳感器節(jié)點(diǎn)如圖14(a)所示,該節(jié)點(diǎn)為CrossBow公司的Telosb節(jié)點(diǎn),可通過(guò)設(shè)置節(jié)點(diǎn)功率來(lái)控制節(jié)點(diǎn)的通訊半徑.實(shí)驗(yàn)中節(jié)點(diǎn)的通訊半徑為15m,利用10個(gè)傳感器節(jié)點(diǎn)組建長(zhǎng)為300m的強(qiáng)柵欄,從柵欄左端開(kāi)始分別編號(hào)為1～10,并隨機(jī)的從10個(gè)節(jié)點(diǎn)中選擇5個(gè)節(jié)點(diǎn)進(jìn)行休眠,模擬節(jié)點(diǎn)死亡,形成柵欄間隙.在距離柵欄左右2側(cè)垂直距離1.5m的帶狀區(qū)域內(nèi)隨機(jī)均勻部署10個(gè)節(jié)點(diǎn)作為可移動(dòng)節(jié)點(diǎn),其移動(dòng)過(guò)程通過(guò)人工搬運(yùn)實(shí)現(xiàn),柵欄部署如圖14(b)所示.實(shí)驗(yàn)中入侵者(人)攜帶一個(gè)傳感器節(jié)點(diǎn)(目標(biāo)節(jié)點(diǎn))從任意位置穿越柵欄,且目標(biāo)節(jié)點(diǎn)一直在向外發(fā)出Beacon幀,而柵欄中的傳感器節(jié)點(diǎn)一直處于監(jiān)聽(tīng)狀態(tài),當(dāng)目標(biāo)節(jié)點(diǎn)距離柵欄中某個(gè)傳感器節(jié)點(diǎn)的距離小于等于15m時(shí),柵欄中的監(jiān)聽(tīng)節(jié)點(diǎn)收到Beacon幀,則認(rèn)為柵欄監(jiān)測(cè)到了入侵者(目標(biāo)節(jié)點(diǎn)).實(shí)驗(yàn)對(duì)比貪婪算法(Greedy)和最大流算法(Flow),10次實(shí)驗(yàn)的平均結(jié)果如表1所示.

圖14 柵欄實(shí)物部署圖Fig.14 Barrier physical deployment map

表1 實(shí)物實(shí)驗(yàn)結(jié)果表
Table 1 Physical experiment results table

HCBCGreedyFlow修復(fù)節(jié)點(diǎn)數(shù)量(個(gè))平均移動(dòng)距離(米)50次穿越監(jiān)測(cè)率(%)4.423.1699.33.433.0790.44.133.2498.6

實(shí)驗(yàn)結(jié)果表明基于本文提出的HCBC方法成功修復(fù)柵欄中間隙(死亡節(jié)點(diǎn)處)的平均數(shù)量最多,為4.42個(gè),其次是Flow方法,修復(fù)柵欄間隙平均數(shù)量最低的是Greedy.因此HCBC方法構(gòu)建柵欄的成功率是最高的.Greedy方法的平均移動(dòng)距離最短,因?yàn)樵摲椒偸桥汕沧罱?jié)點(diǎn)替換死亡節(jié)點(diǎn)(到柵欄間隙處),因此平均移動(dòng)距離最短,而HCBC和Flow方法首先會(huì)盡最大可能修復(fù)間隙,其次再考慮修復(fù)代價(jià),即平均移動(dòng)距離,平均移動(dòng)距離略高于Greedy方法,但HCBC考慮最優(yōu)派遣,因此平均移動(dòng)距離略低于Flow方法.構(gòu)建柵欄夠,進(jìn)行50次獨(dú)立重復(fù)的隨機(jī)穿越柵欄實(shí)驗(yàn),其中HCBC方法成功檢測(cè)到入侵目標(biāo)的概率最高,其次是Flow方法,最后是Greedy方法,因?yàn)镠CBC方法構(gòu)建的柵欄最完善,間隙長(zhǎng)度最短.

6 總 結(jié)

本文研究了一種異構(gòu)WSN復(fù)合型柵欄覆蓋方法,能夠適用于晴天和雨水天氣.該方法首先根據(jù)構(gòu)建柵欄的需求,將監(jiān)測(cè)區(qū)域劃分為k個(gè)子區(qū)域,然后在每個(gè)子區(qū)域內(nèi)構(gòu)建一條復(fù)合型柵欄,在構(gòu)建過(guò)程中充分考慮了節(jié)點(diǎn)移動(dòng)能耗,以及增強(qiáng)節(jié)點(diǎn)的數(shù)量.實(shí)驗(yàn)結(jié)果表明該方法能夠有效解決柵欄在晴天和雨天場(chǎng)景下的適用性問(wèn)題.后續(xù)工作希望進(jìn)一步研究多場(chǎng)景下柵欄的調(diào)度問(wèn)題,延長(zhǎng)傳感器網(wǎng)絡(luò)的生存時(shí)間.