一種WSN柵欄間隙修復優化方法*

趙小敏,方 丁,毛科技

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

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

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

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

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

1 柵欄間隙修復

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

1.1 柵欄間隙查找

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

圖1 柵欄間隙圖

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

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

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

(1)

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

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

1.2 構建可移動節點數量需求拓撲圖

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

圖2 靜態節點全連接拓撲圖

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

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

(2)

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

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

圖3 可移動節點數量需求拓撲圖

1.3 KSP尋找最佳修復路徑

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

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

1.4 匈牙利算法派遣可移動節點

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

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

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

圖5 匈牙利算法指派可移動節點圖

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

(3)

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

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

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

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

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

(4)

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

圖7 柵欄實驗圖

2 修復路徑優化

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

圖6 修復路徑優化圖

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

3 仿真實驗

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

3.1 可移動節點需求數量

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

圖8 可移動節點需求數量圖

3.2 平均移動距離

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

圖9 平均移動距離圖

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

3.3 柵欄修復過程能耗分析

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

圖10 能量消耗分析圖

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

3.4 柵欄間隙修復率

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

圖11 柵欄間隙修復率圖

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

3.5 算法復雜度

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

圖12 算法運行時間圖

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

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

4 總結

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