一種WSN柵欄間隙修復優(yōu)化方法*

趙小敏,方 丁,毛科技

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

柵欄覆蓋是無線傳感器網(wǎng)絡WSN(Wireless Sensor Networks)領域中廣泛使用的覆蓋模型之一,其目的是研究移動目標試圖穿越無線傳感器網(wǎng)絡保護的區(qū)域時被檢測到的問題[1-3]。無線傳感器網(wǎng)絡柵欄覆蓋應用廣泛,如在國土安全方面,將柵欄部署在邊界線可以檢測非法越境者;在生態(tài)檢測方面,將柵欄部署在自然保護區(qū)邊界用于對入侵物種的檢測;在環(huán)境保護方面,將柵欄部署在污染隔離區(qū)外圍檢測污染物質(zhì)的擴散[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ū)強K-柵欄覆蓋構(gòu)建算法PMNSB,該算法利用最少的節(jié)點進行強柵欄的構(gòu)建,提升了WSN的性能。程建夫等人[7]提出了一種利用移動傳感器節(jié)點巡邏式的查找柵欄潛在穿越點的柵欄調(diào)度方法,該方法通過調(diào)度休眠的可移動節(jié)點來強化柵欄薄弱點,從而提高了柵欄的覆蓋率。在柵欄修復方面,陳業(yè)綱等人[8]針對柵欄覆蓋優(yōu)化問題提出一種通過派遣最少移動節(jié)點修復柵欄的方法,將帶狀的目標區(qū)域分解成規(guī)則域,在每個規(guī)則域中實現(xiàn)CBMS算法,降低了柵欄修復時的能耗,但該方法沒有考慮可移動節(jié)點的移動距離。鄧先軍等人[9]提出一種混合式的柵欄間隙修復方法,融合了最小最大方案(min-max scheme)和最大生存時間方案(max-lifetime scheme),雖然降低了可移動節(jié)點的最大移動距離,但是沒有使可移動節(jié)點的平均移動距離達到最小,因此修復柵欄時具有較高的能耗代價。戴光麟等人[10]提出了一種利用網(wǎng)絡中移動節(jié)點修復柵欄間隙的方法,采用基于集合最大流算法計算修復間隙所需的移動節(jié)點數(shù)量,并利用二分搜索法得到可移動節(jié)點距離對應的鄰居待修復節(jié)點的最短距離,從而使移動節(jié)點的移動距離盡可能的減少,該方法雖優(yōu)化了移動節(jié)點的派遣問題,但利用二分搜索法計算移動距離時存在誤差,因此移動距離不能達到最短。陳姣燕等人[11]研究了有向傳感器節(jié)點組成的柵欄出現(xiàn)間隙的問題,通過基于線路的部署策略對傳感器節(jié)點進行部署從而形成柵欄覆蓋,提出一種查找子柵欄以及柵欄間隙的高效方法,并設計了兩種柵欄間隙修復算法(SRA算法和CRA算法),有效地提高了柵欄間隙的修復率。

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

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

1 柵欄間隙修復

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

1.1 柵欄間隙查找

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

圖1 柵欄間隙圖

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

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

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

(1)

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

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

1.2 構(gòu)建可移動節(jié)點數(shù)量需求拓撲圖

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

圖2 靜態(tài)節(jié)點全連接拓撲圖

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

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

(2)

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

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

圖3 可移動節(jié)點數(shù)量需求拓撲圖

1.3 KSP尋找最佳修復路徑

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

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

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

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

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

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

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

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

(3)

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

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

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

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

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

(4)

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

圖7 柵欄實驗圖

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

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

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

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

3 仿真實驗

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

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

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

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

3.2 平均移動距離

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

圖9 平均移動距離圖

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

3.3 柵欄修復過程能耗分析

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

圖10 能量消耗分析圖

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

3.4 柵欄間隙修復率

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

圖11 柵欄間隙修復率圖

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

3.5 算法復雜度

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

圖12 算法運行時間圖

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

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

4 總結(jié)

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