趙小敏,方 丁,毛科技

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

柵欄覆蓋是無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)領(lǐng)域中廣泛使用的覆蓋模型之一,其目的是研究移動目標(biāo)試圖穿越無線傳感器網(wǎng)絡(luò)保護(hù)的區(qū)域時被檢測到的問題[1-3]。無線傳感器網(wǎng)絡(luò)柵欄覆蓋應(yīng)用廣泛,如在國土安全方面,將柵欄部署在邊界線可以檢測非法越境者;在生態(tài)檢測方面,將柵欄部署在自然保護(hù)區(qū)邊界用于對入侵物種的檢測;在環(huán)境保護(hù)方面,將柵欄部署在污染隔離區(qū)外圍檢測污染物質(zhì)的擴(kuò)散[4]。

目前國內(nèi)對無線傳感器的柵欄覆蓋研究已經(jīng)取得了很大的成果。在柵欄構(gòu)建和柵欄調(diào)度方面,班冬松等人[5]提出了一種1-網(wǎng)格柵欄覆蓋優(yōu)化算法(CBGB),以較低能量構(gòu)建1-網(wǎng)格柵欄,并提出了一種分治策略的K-柵欄覆蓋構(gòu)建算法,該算法極大地降低了計算以及通信的開銷。王超等人[6]提出了一種分區(qū)強(qiáng)K-柵欄覆蓋構(gòu)建算法PMNSB,該算法利用最少的節(jié)點(diǎn)進(jìn)行強(qiáng)柵欄的構(gòu)建,提升了WSN的性能。程建夫等人[7]提出了一種利用移動傳感器節(jié)點(diǎn)巡邏式的查找柵欄潛在穿越點(diǎn)的柵欄調(diào)度方法,該方法通過調(diào)度休眠的可移動節(jié)點(diǎn)來強(qiáng)化柵欄薄弱點(diǎn),從而提高了柵欄的覆蓋率。在柵欄修復(fù)方面,陳業(yè)綱等人[8]針對柵欄覆蓋優(yōu)化問題提出一種通過派遣最少移動節(jié)點(diǎn)修復(fù)柵欄的方法,將帶狀的目標(biāo)區(qū)域分解成規(guī)則域,在每個規(guī)則域中實(shí)現(xiàn)CBMS算法,降低了柵欄修復(fù)時的能耗,但該方法沒有考慮可移動節(jié)點(diǎn)的移動距離。鄧先軍等人[9]提出一種混合式的柵欄間隙修復(fù)方法,融合了最小最大方案(min-max scheme)和最大生存時間方案(max-lifetime scheme),雖然降低了可移動節(jié)點(diǎn)的最大移動距離,但是沒有使可移動節(jié)點(diǎn)的平均移動距離達(dá)到最小,因此修復(fù)柵欄時具有較高的能耗代價。戴光麟等人[10]提出了一種利用網(wǎng)絡(luò)中移動節(jié)點(diǎn)修復(fù)柵欄間隙的方法,采用基于集合最大流算法計算修復(fù)間隙所需的移動節(jié)點(diǎn)數(shù)量,并利用二分搜索法得到可移動節(jié)點(diǎn)距離對應(yīng)的鄰居待修復(fù)節(jié)點(diǎn)的最短距離,從而使移動節(jié)點(diǎn)的移動距離盡可能的減少,該方法雖優(yōu)化了移動節(jié)點(diǎn)的派遣問題,但利用二分搜索法計算移動距離時存在誤差,因此移動距離不能達(dá)到最短。陳姣燕等人[11]研究了有向傳感器節(jié)點(diǎn)組成的柵欄出現(xiàn)間隙的問題,通過基于線路的部署策略對傳感器節(jié)點(diǎn)進(jìn)行部署從而形成柵欄覆蓋,提出一種查找子?xùn)艡谝约皷艡陂g隙的高效方法,并設(shè)計了兩種柵欄間隙修復(fù)算法(SRA算法和CRA算法),有效地提高了柵欄間隙的修復(fù)率。

國外無線傳感器網(wǎng)絡(luò)的柵欄部署技術(shù)也已經(jīng)非常成熟。在柵欄構(gòu)建方面,Santosh Kumar等人[12]首次提出了弱K-柵欄覆蓋和強(qiáng)K-柵欄覆蓋的概念,通過使用集中式算法快速判斷監(jiān)測區(qū)域能否形成K-柵欄覆蓋,推導(dǎo)出形成弱K-柵欄覆蓋的臨界條件。CF Cheng 等人[13]提出一種新型柵欄覆蓋方法—目標(biāo)柵欄覆蓋,該覆蓋方法對外部入侵和內(nèi)部目標(biāo)的突破進(jìn)行監(jiān)測,適用于監(jiān)獄場景中,部署時降低了傳感器節(jié)點(diǎn)的部署數(shù)量,減少了節(jié)點(diǎn)之間的信息交換量,從而降低了部署的成本。Kim等人[14]提出了一種優(yōu)化的強(qiáng)柵欄部署方法,該方法可以檢測到任何入侵者進(jìn)入檢測區(qū)域,提高了傳感器節(jié)點(diǎn)檢測的準(zhǔn)確度。Ashutosh Baheti等人[15]提出了一種集中式算法,通過隨機(jī)初始化部署傳感器節(jié)點(diǎn)形成非線性柵欄,減少了所需可移動節(jié)點(diǎn)的移動距離,從而降低了整個網(wǎng)絡(luò)的能耗。柵欄調(diào)度方面,Jonathan DeWitt等人[16]提出一種分時調(diào)度柵欄的方法,將能量收集納入到柵欄覆蓋問題中,通過節(jié)點(diǎn)剩余能量調(diào)整柵欄睡眠時間表,由于該方法充分考慮了節(jié)點(diǎn)的能耗均衡,因此大大提高了柵欄覆蓋的生存時間。柵欄修復(fù)方面,Larbi-Mezeghrane等人[17]利用隨機(jī)部署節(jié)點(diǎn)引起的信息冗余,提出一種生成調(diào)度集的方法,使用最少的可移動節(jié)點(diǎn)修復(fù)柵欄實(shí)現(xiàn)了K-柵欄覆蓋,減少了能耗,增加了網(wǎng)絡(luò)的生存時間。Nikitha等人[18]提出了一種覆蓋間隙修復(fù)算法(CGR),該方法通過檢測網(wǎng)絡(luò)中低能量的節(jié)點(diǎn),派遣分布在低能量節(jié)點(diǎn)周圍最近的可移動節(jié)點(diǎn)進(jìn)行替換,由于替換的過程中采用就近策略,會陷入局部移動距離最短,難以實(shí)現(xiàn)修復(fù)柵欄的移動距離總和最小,因此修復(fù)柵欄的能耗代價并不是最低的。

鑒于上述柵欄間隙修復(fù)方法存在修復(fù)代價高的問題,本文提出一種WSN柵欄間隙修復(fù)優(yōu)化方法OMBR(An Optimization Method for WSN Barrier Gap Repair),利用KSP(Top-k-Shortest Paths)算法[19]尋找所需可移動節(jié)點(diǎn)數(shù)量最少的可修復(fù)路徑,采用匈牙利算法[20]派遣可移動節(jié)點(diǎn)去修復(fù)柵欄,使可移動節(jié)點(diǎn)修復(fù)柵欄間隙的移動距離總和最小。該方法能夠在花費(fèi)較小代價(即修復(fù)柵欄時所需可移動節(jié)點(diǎn)最少,且修復(fù)過程中移動距離總和最短)的前提下完成柵欄的修復(fù)工作。

1 柵欄間隙修復(fù)

柵欄間隙修復(fù)方法OMBR的具體思路是首先利用柵欄間隙查找方法獲得柵欄中所有間隙的位置和間隙的長度,然后利用靜態(tài)節(jié)點(diǎn)構(gòu)建可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D,接著采用KSP算法尋找可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D中的最佳修復(fù)路徑,最后利用匈牙利算法派遣可移動節(jié)點(diǎn),完成柵欄的修復(fù)工作。

1.1 柵欄間隙查找

假設(shè)已經(jīng)通過參考文獻(xiàn)[21-23]等提出的柵欄構(gòu)建方法完成了柵欄的初始化構(gòu)建工作,但是由于諸多因素的影響,如泥石流對柵欄的沖擊、節(jié)點(diǎn)自身電量消耗殆盡,此時柵欄會產(chǎn)生間隙,從而導(dǎo)致柵欄有入侵檢測的漏洞,如圖1所示,左側(cè)柵欄節(jié)點(diǎn)ni與右側(cè)柵欄節(jié)點(diǎn)ni+1之間出現(xiàn)了間隙,入侵者可穿越柵欄間隙而不被柵欄監(jiān)測到。

圖1 柵欄間隙圖

當(dāng)柵欄出現(xiàn)間隙時,需要定位到柵欄間隙所處位置并對其進(jìn)行修復(fù)。傳感器節(jié)點(diǎn)部署到監(jiān)測區(qū)域時,一般采用靜態(tài)節(jié)點(diǎn)和可移動節(jié)點(diǎn)按一定比例混合的方式部署,且部署的節(jié)點(diǎn)能夠通過GPS或WSN定位方法獲得自身位置,因此為柵欄的修復(fù)提供了可能。

由于節(jié)點(diǎn)的位置已知,假設(shè)傳感器節(jié)點(diǎn)(靜態(tài)節(jié)點(diǎn)和可移動節(jié)點(diǎn))的感知半徑為r,則可根據(jù)節(jié)點(diǎn)之間的距離判斷柵欄之間是否出現(xiàn)了間隙。間隙距離Dgap如式(1)所示。

Dgap=dist(ni,ni+1)-2r

(1)

式中,dist(ni,ni+1)表示節(jié)點(diǎn)ni,ni+1之間的歐式距離,r為傳感器感知半徑。

當(dāng)Dgap>0時表示柵欄出現(xiàn)了間隙,應(yīng)該及時查找并進(jìn)行修復(fù),其中查找方法可根據(jù)參考文獻(xiàn)[24]中提出的柵欄間隙查找法得到柵欄中所有間隙發(fā)生的位置以及間隙的長度。

1.2 構(gòu)建可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D

利用分布在柵欄間隙周圍的靜態(tài)傳感器節(jié)點(diǎn)構(gòu)建全連接拓?fù)鋱DG(V,E),其中V代表分布在柵欄間隙周圍的靜態(tài)傳感器節(jié)點(diǎn),E表示兩個靜態(tài)傳感器節(jié)點(diǎn)之間的邊。假設(shè)柵欄在節(jié)點(diǎn)s,t之間出現(xiàn)了間隙,且間隙周圍存在3個靜態(tài)節(jié)點(diǎn),如圖2所示,其中di,j表示節(jié)點(diǎn)si與節(jié)點(diǎn)sj之間的距離(如d1,2表示節(jié)點(diǎn)s1和s2之間的距離),則拓?fù)鋱DG(V,E)中的V和E可以表示為V={s,s1,s2,s3,t},E={ds,1,ds,2,ds,3,…,d3,t}。

圖2 靜態(tài)節(jié)點(diǎn)全連接拓?fù)鋱D

基于構(gòu)建的靜態(tài)節(jié)點(diǎn)全連接拓?fù)鋱D,可計算出覆蓋兩節(jié)點(diǎn)之間的邊所需的可移動節(jié)點(diǎn)數(shù)量。以圖2中的節(jié)點(diǎn)s1和s2為例,覆蓋節(jié)點(diǎn)s1和s2之間的邊所需的最少可移動節(jié)點(diǎn)數(shù)量nm1,2可由式(2)計算得到。

nm1,2=「(d1,2-2r)/(2r)?

(2)

式中,d1,2表示節(jié)點(diǎn)s1與節(jié)點(diǎn)s2之間邊的長度,r表示傳感器感知半徑。

根據(jù)式(2)得到的覆蓋兩節(jié)點(diǎn)之間的邊所需的可移動節(jié)點(diǎn)數(shù)量,就可以將全連接拓?fù)鋱DG(V,E),轉(zhuǎn)化為所需的可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱DG′(V′,E′),其中V′代表分布在柵欄間隙周圍的靜態(tài)傳感器節(jié)點(diǎn),E′表示覆蓋兩節(jié)點(diǎn)之間的邊所需的可移動節(jié)點(diǎn)數(shù)量。如圖3所示,拓?fù)鋱D中的元素可表示為V′={s,s1,s2,s3,t},E′={nms,1,nms,2,nms,3,…,nm3,t}。

圖3 可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D

1.3 KSP尋找最佳修復(fù)路徑

在柵欄間隙修復(fù)時,可移動節(jié)點(diǎn)數(shù)量有限,因此應(yīng)盡可能多的利用靜態(tài)傳感器節(jié)點(diǎn),移動少量的可移動傳感器節(jié)點(diǎn)完成柵欄的修復(fù)。當(dāng)構(gòu)建了從柵欄間隙起始節(jié)點(diǎn)s到終點(diǎn)t之間的可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D之后,利用KSP算法尋找可移動節(jié)點(diǎn)數(shù)量需求拓?fù)鋱D中的最佳路徑,KSP算法可計算得到前K條最佳路徑(前K條最短路徑),這里的路徑長度是指所需可移動節(jié)點(diǎn)的數(shù)量,最佳路徑是指后續(xù)可能被修復(fù)的路徑。如圖4中,利用KSP算法尋找到2條最佳修復(fù)路徑,其中修復(fù)路徑P1最少需要3個可移動節(jié)點(diǎn)能夠完成柵欄的修復(fù)(路徑長度為3),修復(fù)路徑P2需要4個可移動節(jié)點(diǎn)能夠完成柵欄的修復(fù)(路徑長度為4)。假設(shè)柵欄間隙處有3個可移動節(jié)點(diǎn)移動到修復(fù)路徑P1的待修復(fù)位置V1、V2、V3即可完成柵欄的間隙修復(fù),而如果存在4個或以上節(jié)點(diǎn)則能夠完成P1和P2任意一條路徑的修復(fù)。在K條最佳修復(fù)路徑中,首先選擇所需可移動節(jié)點(diǎn)數(shù)量最少的修復(fù)路徑進(jìn)行修復(fù),因為多移動一個節(jié)點(diǎn)需要消耗大量的能量,不利于柵欄的長期生存。如果對最短路徑進(jìn)行修復(fù)時,可移動節(jié)點(diǎn)的移動距離總和大于次最短路徑,則算法會選擇次最短路徑進(jìn)行修復(fù)。

圖4 KSP算法尋找G′的最佳修復(fù)路徑圖

1.4 匈牙利算法派遣可移動節(jié)點(diǎn)

找出拓?fù)鋱DG′中的K條最佳修復(fù)路徑之后,就可調(diào)度分布在柵欄周圍的可移動節(jié)點(diǎn)進(jìn)行柵欄修復(fù)。假設(shè)可移動節(jié)點(diǎn)的移動距離沒有限制,可以通過派遣可移動節(jié)點(diǎn)對尋找到的最佳路徑中的待修復(fù)位置進(jìn)行柵欄修復(fù)。

首先判斷可移動節(jié)點(diǎn)數(shù)量是否能夠滿足柵欄間隙的修復(fù),如果可移動節(jié)點(diǎn)數(shù)量大于或等于待修復(fù)位置數(shù)量,則能夠完成柵欄的修復(fù),否則不能完成柵欄間隙修復(fù)。假如修復(fù)柵欄間隙需要m個可移動傳感器節(jié)點(diǎn),而有n個可移動節(jié)點(diǎn)可以被調(diào)度,且n>m,如何從n個可移動節(jié)點(diǎn)中選擇m個節(jié)點(diǎn)對柵欄進(jìn)行修復(fù)使得所有節(jié)點(diǎn)完成柵欄修復(fù)的移動距離總和最短是需要著重解決的問題。

如果修復(fù)路徑中待修復(fù)位置的數(shù)量和可移動節(jié)點(diǎn)數(shù)量相同,則可以直接使用匈牙利算法完成節(jié)點(diǎn)的派遣工作,通過a個可移動節(jié)點(diǎn)去修復(fù)柵欄中a個待修復(fù)位置使移動節(jié)點(diǎn)的移動距離總和最小。當(dāng)用于修復(fù)柵欄的可移動節(jié)點(diǎn)數(shù)量為n,而最短修復(fù)路徑存在m個待修復(fù)位置,其中n>m,為了使匈牙利算法適用于可移動節(jié)點(diǎn)的派遣問題,需要虛擬出n-m個待修復(fù)位置,并且約定可移動節(jié)點(diǎn)到這些虛擬待修復(fù)位置的移動距離為0,如圖5所示,可移動節(jié)點(diǎn)mi與待修復(fù)位置v4之間的移動距離為0。

圖5 匈牙利算法指派可移動節(jié)點(diǎn)圖

現(xiàn)假設(shè)待修復(fù)位置數(shù)為3,而可用于修復(fù)柵欄的可移動節(jié)點(diǎn)數(shù)為4,因此需要虛擬出1個待修復(fù)位置(圖中v4為虛擬待修復(fù)位置),為尋找到的最短修復(fù)路徑P1構(gòu)造出匈牙利算法中的代價矩陣Mcost,如式(3)所示。

(3)

式中,di,j表示可移動節(jié)點(diǎn)mi與待修復(fù)位置vj之間的距離,以此類推,其中可移動節(jié)點(diǎn)到虛擬出的待修復(fù)位置的距離為0。

使用匈牙利算法對代價矩陣Mcost進(jìn)行優(yōu)化,得到一種代價最小的派遣方式,該派遣方式使修復(fù)柵欄間隙時可移動節(jié)點(diǎn)的移動距離總和最小,如圖5所示,其中代價最小的派遣方式可表示為

Wmin={m1→v1,m2→v4,m3→v2,m4→v3}

即用移動節(jié)點(diǎn)m1去修復(fù)v1,m2修復(fù)v4,m3修復(fù)v2,m4修復(fù)v3,此時的移動距離總和dWmin可由式(4)計算得到。

dWi=da,1+db,2+dc,3+…+dn,n

(4)

式中,da,1表示移動節(jié)點(diǎn)ma到待修復(fù)位置v1的距離,同理db,2表示移動節(jié)點(diǎn)mb到待修復(fù)位置v2的距離,dn,n表示移動節(jié)點(diǎn)mn到待修復(fù)位置vn的距離。

圖7 柵欄實(shí)驗圖

2 修復(fù)路徑優(yōu)化

由于柵欄間隙中的靜態(tài)節(jié)點(diǎn)數(shù)量很多,在構(gòu)建所需可移動節(jié)點(diǎn)數(shù)量拓?fù)鋱DG′時,利用KSP算法尋找可移動節(jié)點(diǎn)需求拓?fù)鋱DG′的最佳修復(fù)路徑過程中很大概率上會出現(xiàn)多條最短修復(fù)路徑和多條次短修復(fù)路徑,如圖6所示,存在3條修復(fù)路徑,其中修復(fù)路徑P1和P2為最短修復(fù)路徑,需要3個可移動節(jié)點(diǎn)即可完成柵欄間隙修復(fù),路徑P3為次短修復(fù)路徑,需要4個可移動節(jié)點(diǎn)才能完成柵欄的修復(fù)。由于可移動節(jié)點(diǎn)的分布不同,造成可移動節(jié)點(diǎn)移動到這2條最短修復(fù)路徑P1和P2上的待修復(fù)位置的移動距離并不相同,因此當(dāng)多條最短修復(fù)路徑存在時,利用匈牙利算法分別計算可移動節(jié)點(diǎn)修復(fù)每條最短路徑的移動距離總和,然后選擇距離總和最短的修復(fù)路徑完成柵欄的修復(fù)。

圖6 修復(fù)路徑優(yōu)化圖

然而并不一定修復(fù)最短路徑是可移動節(jié)點(diǎn)的移動距離總和最短的,也可能是修復(fù)次最短路徑時移動距離總和最短。因此利用KSP算法求得K條最佳修復(fù)路徑,K條最佳修復(fù)路徑中包含了最短修復(fù)路徑和次最短修復(fù)路徑。假如部署區(qū)域內(nèi)可移動節(jié)點(diǎn)的數(shù)量足夠(能夠滿足最短路徑和次最短路徑的修復(fù)),修復(fù)次最短路徑P3需要4個可移動傳感器節(jié)點(diǎn),可移動節(jié)點(diǎn)的移動距離總和為D1,修復(fù)最短路徑P1需要3個傳感器節(jié)點(diǎn),可移動節(jié)點(diǎn)移動距離為D2,而D1

3 仿真實(shí)驗

實(shí)驗的硬件環(huán)境為i7處理器、8G內(nèi)存的PC機(jī),采用MATLAB R2013a仿真軟件進(jìn)行編程。將傳感器節(jié)點(diǎn)部署在一個長為3 000 m,寬為200 m的矩形區(qū)域中,在該區(qū)域中隨機(jī)部署100個傳感器節(jié)點(diǎn)(包括靜態(tài)傳感器節(jié)點(diǎn)和可移動傳感器節(jié)點(diǎn)),傳感器節(jié)點(diǎn)的感知半徑r為45 m。在監(jiān)測區(qū)域內(nèi)已經(jīng)通過參考文獻(xiàn)[21]提出的柵欄構(gòu)建方法構(gòu)建了一條柵欄,由于某些因素導(dǎo)致柵欄出現(xiàn)間隙,需要進(jìn)行修復(fù),如圖7所示,圖中柵欄中間出現(xiàn)了間隙,采用本文提出的修復(fù)方法進(jìn)行柵欄修復(fù)。

3.1 可移動節(jié)點(diǎn)需求數(shù)量

修復(fù)不同長度的柵欄間隙所需要的可移動節(jié)點(diǎn)數(shù)量是不同的,理論上間隙越長,則需要可移動節(jié)點(diǎn)數(shù)量越多。仿真實(shí)驗驗證柵欄間隙長度與可移動節(jié)點(diǎn)數(shù)量之間的關(guān)系,圖8驗證了可移動節(jié)點(diǎn)比例分別為75%、50%、25%情況下修復(fù)不同長度的柵欄間隙所需要的可移動節(jié)點(diǎn)數(shù)量,實(shí)驗數(shù)據(jù)為100次獨(dú)立重復(fù)實(shí)驗的平均結(jié)果。從圖8可知,隨著柵欄間隙長度的增加,修復(fù)柵欄需要的可移動節(jié)點(diǎn)數(shù)量逐漸增加,且呈線性增長?？梢苿庸?jié)點(diǎn)比例越高,則修復(fù)柵欄間隙需要的可移動節(jié)點(diǎn)數(shù)量越多。因為可移動節(jié)點(diǎn)在總部署節(jié)點(diǎn)中的占比越高,則靜態(tài)節(jié)點(diǎn)的比例越低。OMBR柵欄修復(fù)方法是盡可能地使用靜態(tài)節(jié)點(diǎn)構(gòu)建修復(fù)路徑,因此當(dāng)柵欄間隙長度不變的情況下,靜態(tài)節(jié)點(diǎn)的數(shù)量越少,則需要可移動節(jié)點(diǎn)數(shù)量就越多。

圖8 可移動節(jié)點(diǎn)需求數(shù)量圖

3.2 平均移動距離

柵欄修復(fù)過程中可移動節(jié)點(diǎn)的平均移動距離是評價柵欄修復(fù)方法的重要指標(biāo),平均移動距離越短,則修復(fù)柵欄花費(fèi)的代價越少,即消耗的能量越少,越有利于柵欄的長期生存。為驗證柵欄間隙長度對可移動節(jié)點(diǎn)的平均移動距離的影響,實(shí)驗中可移動節(jié)點(diǎn)占總部署節(jié)點(diǎn)的比例為50%,結(jié)果如圖9所示。實(shí)驗對比了參考文獻(xiàn)[23]提出的最佳修復(fù)方法和廣泛用于柵欄間隙修復(fù)的貪婪算法,分別記為Optimal和Greedy,其中最佳修復(fù)方法性能卓越,是目前比較優(yōu)秀的一種柵欄間隙修復(fù)方法。

圖9 平均移動距離圖

從圖9可以看出,隨著柵欄間隙長度的增加,可移動節(jié)點(diǎn)的平均移動距離逐漸增加,但增加速度緩慢。在利用貪婪算法修復(fù)柵欄間隙時,可移動節(jié)點(diǎn)的平均移動距離最長,OMBR柵欄修復(fù)方法修復(fù)間隙時可移動節(jié)點(diǎn)的平均移動距離最短,最佳修復(fù)方法修復(fù)柵欄間隙時可移動節(jié)點(diǎn)的平均移動距離略高于OMBR。OMBR算法從間隙修復(fù)的全局考慮,使得所有可移動節(jié)點(diǎn)的移動距離最短,貪婪算法選擇最接近待修復(fù)位置的移動節(jié)點(diǎn)修復(fù)柵欄,會陷入局部最優(yōu)問題,最佳修復(fù)方法采用二分查找法計算節(jié)點(diǎn)的移動距離,雖然效率較高,但是不能完全達(dá)到最優(yōu),存在誤差。

3.3 柵欄修復(fù)過程能耗分析

在利用可移動節(jié)點(diǎn)修復(fù)柵欄間隙的過程中,節(jié)點(diǎn)的能量消耗與節(jié)點(diǎn)移動的距離呈正相關(guān),由于節(jié)點(diǎn)移動所消耗的能量遠(yuǎn)遠(yuǎn)高于其他行為消耗的能量,因此在柵欄修復(fù)過程中忽略其他能量消耗。假設(shè)節(jié)點(diǎn)移動10 m,消耗一個單位的能量,實(shí)驗中可移動節(jié)點(diǎn)占總部署節(jié)點(diǎn)數(shù)量的50%,實(shí)驗對比了貪婪算法和最佳修復(fù)方法,可移動節(jié)點(diǎn)修復(fù)柵欄間隙所消耗的能量,如圖10所示。

圖10 能量消耗分析圖

實(shí)驗結(jié)果表明在修復(fù)相同的柵欄間隙時,OMBR算法消耗的能量最少,其次是最佳修復(fù)方法,能量消耗最多的是貪婪算法。根據(jù)圖9的實(shí)驗結(jié)果,OMBR算法修復(fù)柵欄間隙的平均移動距離最短,其次是最佳修復(fù)方法,貪婪算法的平均移動距離最長,而可移動節(jié)點(diǎn)修復(fù)間隙的能量消耗與移動距離呈正相關(guān)。因此,實(shí)驗驗證了OMBR算法在柵欄修復(fù)方面的總體性能比其他兩種算法更好。

3.4 柵欄間隙修復(fù)率

為驗證部署區(qū)域內(nèi)可移動節(jié)點(diǎn)的比例與柵欄間隙修復(fù)率的關(guān)系,實(shí)驗對比了最佳修復(fù)方法和貪婪算法,實(shí)驗中柵欄間隙的長度為1 000 m,結(jié)果如圖11 所示。

圖11 柵欄間隙修復(fù)率圖

從圖11可以看出,當(dāng)沒有可移動節(jié)點(diǎn)時,OMBR的修復(fù)率達(dá)到了9%,而最佳修復(fù)方法和貪婪算法修復(fù)率為0%,主要是因為OMBR算法充分利用了分布在柵欄間隙處的靜態(tài)節(jié)點(diǎn)進(jìn)行柵欄的初期修復(fù),在只有靜態(tài)節(jié)點(diǎn)的情況下柵欄能被部分修復(fù),而最佳修復(fù)方法和貪婪算法僅利用可移動節(jié)點(diǎn)進(jìn)行間隙修復(fù),所以當(dāng)沒有可移動節(jié)點(diǎn)時修復(fù)率為0%?？傮w上,OMBR柵欄間隙修復(fù)率比最佳修復(fù)方法、貪婪算法的修復(fù)率都高,其中最佳修復(fù)方法與貪婪算法的修復(fù)率相當(dāng),因為在可移動節(jié)點(diǎn)的移動距離不限的情況下,部署區(qū)域內(nèi)的移動節(jié)點(diǎn)可以移動到柵欄間隙的任意待修復(fù)位置,所以最佳修復(fù)方法與貪婪算法的修復(fù)率基本接近。

3.5 算法復(fù)雜度

算法復(fù)雜度也是衡量柵欄間隙修復(fù)方法好壞的重要指標(biāo)之一。圖12分別驗證了OMBR算法和最佳修復(fù)方法在不同比例的可移動節(jié)點(diǎn)情況下完成柵欄修復(fù)所運(yùn)行的時間。

圖12 算法運(yùn)行時間圖

由圖12可知,OMBR算法隨著可移動節(jié)點(diǎn)比例的增加,修復(fù)柵欄消耗的時間逐漸降低。由于OMBR算法采用靜態(tài)節(jié)點(diǎn)構(gòu)建拓?fù)鋱D,因此構(gòu)建的拓?fù)鋱D規(guī)模比較小,算法所消耗的時間較短。最佳修復(fù)方法隨著可移動節(jié)點(diǎn)的比例增加,修復(fù)柵欄消耗的時間逐漸增加,因為該方法采用可移動節(jié)點(diǎn)構(gòu)建拓?fù)鋱D,然后計算拓?fù)鋱D的最大流完成柵欄的修復(fù),因此隨著可移動節(jié)點(diǎn)數(shù)量的增加,算法修復(fù)柵欄間隙所花的時間也會增加。隨著柵欄間隙長度的增加,這兩種算法消耗的時間都呈指數(shù)增長,因為柵欄間隙長度增加,這兩種算法在修復(fù)柵欄間隙時構(gòu)建的拓?fù)鋱D規(guī)模也呈指數(shù)增長。

將OMBR修復(fù)法與最佳修復(fù)方法進(jìn)行對比,當(dāng)移動節(jié)點(diǎn)所占比例為25%、50%時OMBR算法比最佳修復(fù)方法的時間復(fù)雜度高。但在可移動節(jié)點(diǎn)比例為75%,柵欄間隙小于800 m的情況下,OMBR算法的時間復(fù)雜度比最佳修復(fù)方法低。因為OMBR算法采用靜態(tài)節(jié)點(diǎn)建立拓?fù)鋱D,當(dāng)柵欄間隙短,可移動節(jié)點(diǎn)的所占比例比較高時,OMBR算法構(gòu)建的靜態(tài)節(jié)點(diǎn)拓?fù)鋱D規(guī)模較小,最佳修復(fù)方法構(gòu)建的拓?fù)鋱D規(guī)模較大,因此OMBR算法的運(yùn)算時間比最佳修復(fù)方法小。綜上所述,雖然OMBR算法時間復(fù)雜度在一定程度上比最佳修復(fù)方法略高,但在柵欄間隙小,移動節(jié)點(diǎn)比例高的情況下,OMBR的時間復(fù)雜度比最佳修復(fù)方法低。

4 總結(jié)

針對可移動節(jié)點(diǎn)進(jìn)行WSN柵欄間隙修復(fù)問題,提出一種WSN柵欄間隙修復(fù)優(yōu)化方法,利用分布在柵欄間隙周圍的靜態(tài)節(jié)點(diǎn),使可移動節(jié)點(diǎn)的移動距離總和最小。仿真實(shí)驗表明該方法在降低網(wǎng)絡(luò)能耗、提高柵欄間隙修復(fù)率方面具有較好的性能,但仍然存在不足之處,如傳感器節(jié)點(diǎn)數(shù)量較大時,算法的復(fù)雜度略高。在后續(xù)的工作中,降低OMBR算法復(fù)雜度,并將無線傳感器節(jié)點(diǎn)部署于實(shí)際場景的帶狀區(qū)域以對穿越區(qū)域的移動物體進(jìn)行監(jiān)測,當(dāng)部署的柵欄出現(xiàn)間隙時,利用本文提出的柵欄間隙修復(fù)方法進(jìn)行修復(fù),對方法在實(shí)際場景下的應(yīng)用中進(jìn)一步驗證。