基于集合最大流算法的WSN柵欄修復方法研究*

戴光麟，方 凱，方 飛，戴國勇，夏 明，宦若虹，毛科技

（浙江工業大學計算機科學與技術學院，杭州310023）

基于集合最大流算法的WSN柵欄修復方法研究*

戴光麟，方 凱，方 飛，戴國勇，夏 明，宦若虹，毛科技*

（浙江工業大學計算機科學與技術學院，杭州310023）

無線傳感器網絡柵欄覆蓋在入侵檢測方面發揮著重要作用，如何修復柵欄間隙是該領域重點研究問題之一。柵欄將監測區域劃分為二部分，任何入侵目標從一個區域穿越到另外一個區域都會被柵欄中至少一個傳感器節點監測到。柵欄中的節點由于某些原因過早死亡導致柵欄出現間隙，監測目標可以通過間隙而不被柵欄監測到。提出一種利用移動節點修復柵欄間隙的方法，該方法采用基于集合的最大流算法計算出能修復間隙的數量并且具有較高的效率，然后利用移動節點修復柵欄，修復過程中，移動節點的總移動距離最短。最后仿真實驗驗證了該方法的有效性。

無線傳感器網絡；柵欄修復；集合最大流算法；效率

柵欄覆蓋是無線傳感器網絡領域主要的覆蓋模型之一，是覆蓋控制研究的熱點，主要考察監測目標穿越傳感器網絡時被檢測的情況［1］。無線傳感器網絡柵欄覆蓋有著廣泛的用途，如在國防應用中，將柵欄部署在邊境線可以探測非法越境者。在環保方面，將柵欄部署在污染源周圍可檢測污染物的擴散情況。在林業保護方面，將柵欄部署在森林火災現場可檢測火災蔓延情況等［2-4］。

目前國內外對無線傳感器網絡柵欄覆蓋的相關研究已經取得了很大的成果，柵欄覆蓋的概念最早出現在機器人傳感器中［5］。舒堅等人在柵欄覆蓋中合理的引入了移動模型，能夠保證以較高的概率發現入侵者以及提早發現入侵者［6］。Anwar Saipulla等人提出了line-based部署方法，該方法形成柵欄的概率比均勻部署等方式更高，然后提出2階段算法修補柵欄間隙，第一階段，FIND-GAPS算法發現柵欄間隙，第二階段MEND-GAPS算法修補柵欄間隙［7］。羅卿等人采用概率感知模型結合數據融合技術構建虛擬節點來提高柵欄覆蓋率，并借助分治法構建柵欄提出一種柵欄控制算法，延長了網絡生存壽命［8］。Xu B等人研究了通過研究入侵者的歷史數據，分析柵欄中某些傳感器節點最容易監測到入侵者，然后將移動傳感器節點移動到這些易受攻擊的位置加強柵欄［9］。Liu等人提出了一種分布式算法構建多條不相交的強柵欄，傳感器節點按泊松分布部署［10］。

在延長柵欄生存時間方面的研究如Kumar等人提出了Optimal Sleep-Wakeup柵欄調度算法，該方法通過交替激活柵欄，最后使得柵欄的能量恰好全部消耗，從而延長了網絡的生存時間［11］。Habib等人研究了研究了一種分布式自學習算法該方法一方面能構建柵欄，另一方面延長了網絡的生存時間［12］，并且與文獻［11］的調度方法進行了比較。Li等人提出一種延長網絡生存時間的方法，該方法在滿足一定入侵檢測率的情況下調度柵欄使得柵欄生存時間得到延長［13］。

柵欄間隙的修復是個值得研究的問題，在柵欄構建初很可能出現間隙或者隨著節點能量的消耗，節點感知半徑減小也極易出現間隙。因此本文利用移動節點修復柵欄間隙，在保證最大可能修復間隙數量的情況下，使得移動節點的總移動距離最小。

1 柵欄間隙

本文將一定比例的可移動節點和靜態節點混合部署在監測區域中，假設本文中的傳感器節點可以通過定位技術獲得坐標并且柵欄已經通過文獻［14-15］等柵欄構建方法構建完成。柵欄在工作過程中由于某些原因（故障）導致柵欄出現間隙，可利用移動節點修復柵欄，當移動節點與間隙的距離小于移動節點的可移動距離D時，此時移動節點可用于修復該間隙，如圖1所示，柵欄中節點ni和ni+1之間出現了間隙。

圖1 柵欄間隙圖

查找出柵欄間隙的位置，才能對其進行修復。假設節點的感知半徑為R，由于柵欄中節點的位置已知，所以可以根據柵欄中相鄰節點的距離判斷是否存在間隙。間隙查找方法如表1所示。最后得到柵欄間隙集合Gap。Gap（i，1）表示間隙出現在節點ni之后，Gap（i，2）表示柵欄間隙的長度L。

表1 柵欄間隙查找方法

2 柵欄修復

本小節主要是通過基于集合的最大流算法計算可修復的柵欄間隙數量，然后將可移動節點移動到柵欄中的間隙處修復柵欄并且使得移動節點的總移動距離最小。

2.1 可修復間隙的數量

目前很多研究都將間隙修復問題轉化為基于權重有向圖的最大流問題，如文獻［8-9］所示。利用最大流算法計算出移動節點可修復的柵欄間隙，但是這些方法并不是從柵欄整體考慮修復所有間隙，而是分別對單個間隙進行修復，使得移動節點修復該間隙的移動距離總和最小，但是這并不能保證移動節點修復所有柵欄間隙的移動距離總和最小，柵欄所有間隙的修復過程涉及到的移動節點數量龐大，普通的最大流算法（如EdmondsKarp）計算復雜度會非常高。針對上述問題，本文提出了基于集合的最大流算法，利用集合的數量代替移動節點的數量，可以大大降低算法的復雜度。

第一小節已經找到了柵欄的間隙并存放在集合Gap中，修補柵欄的過程如圖2所示。

圖2 修復過程圖

修補長度為L的間隙至少需要移動節點的數量為mnum，如式（1）所示。將間隙長度L均勻的分為mnum段，每段的中點為待修補點，如圖中g所示，將移動節點移動到這些位置即可完成修復。

假設整條柵欄所有待修補點的集合為GD={g1, g2,…,gn}，移動節點集合為M={m1,m2,m3,…,ms}，當移動節點和待修補點的距離小于D時，移動節點稱為待修補點的鄰居移動節點。建立各個待修補節點的鄰居移動節點集合 NG={ng1,ng2,…, ngnum|ng1≤i≤num?M}，ngi表示待修補點gi的鄰居移動節點集合。相鄰的鄰居移動節點集合存在重疊元素，以相鄰結合ngi、ngi+1、ngi+2為例，介紹本文提出的基于集合的最大流算法解決間隙修復問題。具體步驟如下：

步驟1 分別計算出專屬于待修補點gi和gi+1的集合a、c，然后計算屬于集合gi和gi+1的公共集合b，假設集合d專屬于待修補點gi+2。如式（2）～式（5）和圖3（a）所示。

步驟2 以集合a、b、c、d和待修補點gi、gi+1、gi+2作為點，以集合的元素數量Na、Nb、Nc、Nd為權重值，建立有向圖G（V，E），如圖3（b）所示，圖中添加開始節點u和結束節點v，與u連接的權重值為集合元素的數量，與v連接的權重值都為1。V表示有向圖的點集合，E表示有向圖的邊集合，待修復點和其鄰居移動節點集合存在一條邊，對應的權重值為集合元素的數量，公共的鄰居移動節點集合與它對應的多個待修復點分別存在一條邊，對應的權重值為集合元素的數量，如集合b與待修復點gi、gi+1都存在一條邊，對應的權重值為Nb。

步驟3 采用最大流算法計算圖G的最大流，當最大流等于待修復點的數量，此時柵欄間隙能被全部修復，否則存在不能被修復的間隙。

2.2 算法復雜度

文獻［8-9］利用最大流算法計算移動節點可修復間隙的數量，然而他們都是以鄰居移動節點和待修復點建立權重有向圖，鄰居移動節點和待修復點間的權重都為1。按照傳統的方法，根據圖3（a）構建的有向圖G（V，E）如圖4所示。該算法的時間復雜度為O(MN2)，M表示有向圖G邊的數量E，N表示有向圖G點的數量V。該算法的時間復雜度隨有向圖G中點的數量V呈指數上升，因此當移動節點數量比較多時，算法時間復雜度變得非常高。如果采用本文提出的基于集合的最大流算法，利用集合代替移動節點，構建有向圖G′(V′,E′)，如圖3（b）所示，V′遠遠小于V，且E′也小于E。因此本文提出的基于集合的最大流算法解決該問題時在保證結果準確的條件下能大幅度降低算法的復雜度。

圖3 集合最大流算法圖

圖4 傳統的有向圖

2.3 間隙修復方法

本小節利用可移動節點修復柵欄的間隙，并且使得移動節點的移動距離最小。在2.1小節的步驟一得到了待修補點集合GD的所有鄰居移動節點集合NG，集合NG中的所有移動節點表示可用于修復柵欄間隙的節點，集合NG有num個元素。集合NG中的可移動節點距離它對應的鄰居待修復點的距離集合為MD={md1,md2,md3,…,mdnum|mdi≤md}，對集合非降序排序，得到集合MD′，找出集合MD′中的最小元素mdoptimum和最大元素mdmax。假設現在存在一個距離mdoptimum，mdmin＜mdoptimum＜mdmax，使得集合MD中的元素不大于mdoptimum時，柵欄間隙能被完全修復，則此時移動節點的總移動距離最短，因此尋找合適的mdoptimum是關鍵。

本文采用二分搜索法查找mdoptimum，ε為一個值很小的閾值，用于結束算法，算法具體操作如下步驟所示：

①

②更新待修復點的鄰居集合NG，將距離待修復點大于mdoptimum的節點從鄰居集合NG中移除，并更新有向圖G的權重和拓撲。

③計算有向圖G的最大流，如果最大流小于n（待修補點集合GD元素數量），則，最大流不會大于待修復點的數量。如果最大流等于n，且，輸出mdoptimum，算法結束，否則執行步驟2。

3 三維場景中的應用

本文提出的柵欄修復方法主要是利用移動節點與柵欄間隙的距離作為修補依據。因此該算法同樣適用于三維空間中的柵欄修復問題。

如在水中部署柵欄以監測水下入侵者，如圖5所示。當柵欄中某些傳感器節點電量耗盡或者外部原因導致節點過早死亡，此時柵欄出現間隙，利用移動節點使用本文提出的柵欄修復算法可最優化的修復柵欄。修復過程中移動節點被充分利用且修復多個間隙的移動距離總和最小。

圖5 柵欄水下部署圖

4 仿真實驗

實驗中已經構建的柵欄長度為5 000 m，部署區域是矩形區域，長5 000 m，寬100 m。移動節點均勻分布在部署區域中。節點的感知半徑為R，移動節點的可移動距離為D。已經構建的柵欄存在很多間隙，總共有165個待修復的點。實驗結果都是重復50次的平均結果。

4.1 柵欄間隙修復

本文提出利用基于集合的最大流算法計算能修復的待修復點數量。該方法以傳感器鄰居移動節點和待修補點為單位構建有向圖，大大簡化了有向圖的拓撲結構，因此提高了算法的效率且不會影響算法的結果。實驗中移動節點的可移動距離D=50 m，實驗采用文獻［8-9］的最大流算法（Maxixmum flow）和貪婪算法（Greedy）與本文的基于集合的最大流算法（A-Maxixmum flow）算法進行對比，貪婪算法每次都選取距離待修補點最近的移動節點來修補，實驗結果如圖6所示，橫坐標表示移動節點的數量，縱坐標表示修復的待修復點數量。

實驗結果表明隨著移動節點數量的增加，柵欄中能被修復的間隙數量在增加，當移動節點達到一定數量后，柵欄的間隙能完全被修復。而且本文提出的方法和文獻［8-9］的方法得到了相同的結果，而貪婪算法在移動節點數量相同的情況下，能修復柵欄間隙的數量相對來說比較少。

圖6 柵欄間隙修復圖

4.2 平均移動距離

利用二分搜索算法（BS）選取移動節點修補柵欄間隙使得移動節點的總移動距離最小。實驗對比了本文的方法和較貪婪算法（Greedy）在修補柵欄間隙時的節點移動距離。移動節點的可移動距離D=30 m和40 m。實驗結果如圖7所示，橫坐標表示移動節點的數量，縱坐標表示移動節點的平均移動距離。

圖7 平均移動距離圖

實驗結果表明當移動節點的可移動距離相同時，本文的方法（BS）移動節點移動的平均距離比貪婪算法（Greedy）大，結合4.1小節我們發現貪婪算法都是選取距離待修補點最近的移動節點修補柵欄的，但是能修補柵欄間隙的數量比較少，因此它是通過犧牲柵欄的修補率使得移動節點的移動距離減小的，但是本文的方法是在保證最大化修補率的情況下修補柵欄間隙，所以節點的移動距離比貪婪算法的大。同樣的當節點的可移動距離D越大，能修補柵欄的間隙數量也在增加，所以節點的平均移動距離也相應增加。

4.3 算法復雜度分析

本文提出的基于集合的最大流算法（A-Maxix?mum flow）比傳統的最大流（Maxixmum flow）算法具有更好的性能。實驗在移動節點的可移動距離為D=40 m、50 m兩種情況下對比了這兩種方法的運算效率，實驗結果如圖8所示，橫坐標表示移動節點的數量，縱坐標表示運算時間（s），實驗采用Matlab編程環境，硬件平臺為i7處理器。

圖8 復雜度分析圖

實驗結果表明基于集合的最大流算法具有更高的效率，并且隨著移動節點的可移動距離增加，算法運算的時間也相應增加，這是因為可移動距離越大，有向圖G中的點和線都在增加，圖G的拓撲結構更大，所以運算時間更長。

4.4 三維場景中算法性能實驗

本次實驗驗證本文提出的算法適合用于三維場景中的柵欄間隙修復問題。仿真實驗在水中部署了一條無線傳感器網絡柵欄，柵欄長度為5 000 m，柵欄中存在50處間隙，間隙的長度大于節點感知半徑R且小于2R，其中R=30 m。沿著柵欄部署均勻500個可移動傳感器節點，部署寬度為60 m，可移動傳感器節點的感知半徑為R，可移動距離D=40 m。實驗采用文獻［9］的最大流算法（Maxixmum flow）和貪婪算法（Greedy）與本文的基于集合的最大流算法（A-Maxixmum flow）算法進行對比。實驗結果如圖9、圖10所示。

圖9中縱坐標表示被修復的間隙數量，實驗結果表明在三維場景中，本文提出的基于集合的最大流算法與傳統的最大流算法相比能修復間隙數量相同且多于貪婪算法。因為貪婪算法僅僅將距離柵欄間隙最近的移動節點移動到間隙處進行修復，沒有從整體考慮柵欄間隙修復。圖10中縱坐標表示修復柵欄過程中算法迭代所需的時間，單位為s，圖10的實驗結果基于圖9的實驗結果，實驗結果表明本文提出的算法修復柵欄比傳統的最大流算法修復柵欄具有更高的效率，由于貪婪算法能修復的間隙數量最少，因此最快完成修復。

圖9 間隙修復數量圖

圖10 算法效率圖

5 總結

本文研究了利用移動節點修復柵欄間隙問題，提出基于集合的最大流算法，大大降低了算法復雜度，并且使得移動節點修復柵欄的移動距離總和最小。仿真結果表明我們的算法不管在柵欄修復和算法性能方面都達到很好的效果。但是還存在不足之處比如移動節點的部署方式比較普通，采用均勻部署，沒有研究比較好的部署方式來提高節點的利用率。在后續工作中，將研究如何部署移動節點使得節點的利用率更高，柵欄修復的效果更好。

［1］Lewis F L.Wireless Sensor Networks［J］.Smart Environments：Technologies，Protocols，and Applications，2004：11-46.

［2］Chen A，Kumar S，Lai T H.Designing Localized Algorithms for Barrier Coverage［C］//Proceedings of the 13th Annual ACM Inter?national Conference on Mobile Computing and Networking ACM，2007：63-74.

［3］班冬松，溫俊，蔣杰，等.移動無線傳感器網絡k-柵欄覆蓋構建算法［J］.軟件學報，2011，22（9）：2089-2103

［4］郭新明.高效無線傳感器網絡強k-柵欄覆蓋節能算法［J］.計算機應用，2013，33（8）：2104-2107.

［5］Gage D W.Command Control for Many-Robot Systems［R］.Naval Command Control and Ocean Surveillance Center Rdt And E Div San Diego CA，1992.

［6］舒堅，余坤，劉琳嵐，等.無線傳感器網絡中基于移動模型的柵欄覆蓋研究［J］.計算機研究與發展，2011，48（S2）：141-144.

［7］Saipulla A，Westphal C，Liu B，et al.Barrier Coverage with Line-Based Deployed Mobile Sensors［J］.Ad Hoc Networks，2013，11（4）：1381-1391.

［8］羅卿，林亞平，王雷，等.傳感器網絡中基于數據融合的柵欄覆蓋控制研究［J］.電子與信息學報，2012（4）：825-831.

［9］Xu B，Zhu Y，Kim D，et al.Strengthening Barrier-Coverage of Stat?ic Sensor Network with Mobile Sensor Nodes［J］.Wireless Net?works，2015，8491：368-377.

［10］Liu B，Dousse O，Wang J，et al.Strong Barrier Coverage of Wire?less Sensor Networks［C］//Proc of the ACM International Sympo?sium on Mobile Ad Hoc Networking and Computing（MobiHoc），2010：411-419.

［11］Kumar S，Lai T H，Posner M E，et al.Optimal Sleep-Wakeup Algo?rithms for Barriers of Wireless Sensors［C］//Broadband Communi?cations，Networks and Systems，2007.Broadnets 2007.FourthIn?ternational Conference on.IEEE，2007：327-336.

［12］Mostafaei H，Meybodi M R.An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2014.

［13］Li J，Chen J，Lai T H.Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors.In Proceedings of the 31th Annu?al Joint Conference of the IEEE Computer and Communications Societies（INFOCOM），2012.

［14］毛科技，方凱，戴國勇，等.基于改進蟻群算法的無線傳感器網絡柵欄覆蓋優化研究［J］.傳感技術學報，2015，28（7）：1058-1065.

［15］王超，范興剛，王恒，等.一種高效強K-柵欄覆蓋構建算法［J］.傳感技術學報，2015，28（2）：227-23.

戴光麟（1979-），男，漢族，浙江工業大學計算機學院講師，博士研究生，主要研究方向為無線傳感器網絡；

方 凱（1992-），男，漢族，浙江工業大學計算機學院碩士研究生，主要研究方向為無線傳感器網絡；

毛科技（1979-），男，漢族，浙江工業大學計算機學院副教授，博士，主要研究方向為無線傳感器網絡、數據挖掘，maokeji@zjut.edu.cn。

Repairing Barrier Gaps in WSN Using Set-Based Max-Flow Algorithm*

DAI Guanglin，FANG Kai，FANG Fei，DAI Guoyong，XIA Ming，HUAN Ruohong，MAO Keji*
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

In wireless sensor networks（WSNs），barrier coverage is a typical coverage model and is of paramount im?portance for intrusion detection.A barrier divides the area of interest into two regions such that any intruder pene?trates from one region to another is guaranteed to be detected by one or more sensor nodes in the barrier.The emer?gence of a gap in the barrier，which is caused by running out of energy or other reasons，may leads to the penetration without being detected.Therefore，the functions of WSNs will be seriously influenced.A mobile nodes based gap healing method is proposed in this paper.The set-based max-flow algorithm is introduced to efficiently carry out the number of existed gaps and then the mobile nodes are scheduled to the right position to heal the gap under the con?dition of minimizing the total moving distance.Some experiments are conducted and shows the effectiveness of the proposed method.

WSN；barrier repairing；set-based Max-flow algorithm；efficiency

TP393

A

1004-1699（2016）11-1742-06

EEACC：6150P；6210；7230 10.3969/j.issn.1004-1699.2016.11.019

項目來源：國家自然科學基金項目（61379023，61401397，61302129）；浙江省公益性技術應用研究計劃項目（2015C31066）；浙江省安全生產科技計劃項目（2013A1001，2013A1002）

2016-03-26 修改日期：2016-07-10