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

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

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

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

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

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

無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋在入侵檢測(cè)方面發(fā)揮著重要作用，如何修復(fù)柵欄間隙是該領(lǐng)域重點(diǎn)研究問題之一。柵欄將監(jiān)測(cè)區(qū)域劃分為二部分，任何入侵目標(biāo)從一個(gè)區(qū)域穿越到另外一個(gè)區(qū)域都會(huì)被柵欄中至少一個(gè)傳感器節(jié)點(diǎn)監(jiān)測(cè)到。柵欄中的節(jié)點(diǎn)由于某些原因過早死亡導(dǎo)致柵欄出現(xiàn)間隙，監(jiān)測(cè)目標(biāo)可以通過間隙而不被柵欄監(jiān)測(cè)到。提出一種利用移動(dòng)節(jié)點(diǎn)修復(fù)柵欄間隙的方法，該方法采用基于集合的最大流算法計(jì)算出能修復(fù)間隙的數(shù)量并且具有較高的效率，然后利用移動(dòng)節(jié)點(diǎn)修復(fù)柵欄，修復(fù)過程中，移動(dòng)節(jié)點(diǎn)的總移動(dòng)距離最短。最后仿真實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

無(wú)線傳感器網(wǎng)絡(luò)；柵欄修復(fù)；集合最大流算法；效率

柵欄覆蓋是無(wú)線傳感器網(wǎng)絡(luò)領(lǐng)域主要的覆蓋模型之一，是覆蓋控制研究的熱點(diǎn)，主要考察監(jiān)測(cè)目標(biāo)穿越傳感器網(wǎng)絡(luò)時(shí)被檢測(cè)的情況［1］。無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋有著廣泛的用途，如在國(guó)防應(yīng)用中，將柵欄部署在邊境線可以探測(cè)非法越境者。在環(huán)保方面，將柵欄部署在污染源周圍可檢測(cè)污染物的擴(kuò)散情況。在林業(yè)保護(hù)方面，將柵欄部署在森林火災(zāi)現(xiàn)場(chǎng)可檢測(cè)火災(zāi)蔓延情況等［2-4］。

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

在延長(zhǎng)柵欄生存時(shí)間方面的研究如Kumar等人提出了Optimal Sleep-Wakeup柵欄調(diào)度算法，該方法通過交替激活柵欄，最后使得柵欄的能量恰好全部消耗，從而延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間［11］。Habib等人研究了研究了一種分布式自學(xué)習(xí)算法該方法一方面能構(gòu)建柵欄，另一方面延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間［12］，并且與文獻(xiàn)［11］的調(diào)度方法進(jìn)行了比較。Li等人提出一種延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的方法，該方法在滿足一定入侵檢測(cè)率的情況下調(diào)度柵欄使得柵欄生存時(shí)間得到延長(zhǎng)［13］。

柵欄間隙的修復(fù)是個(gè)值得研究的問題，在柵欄構(gòu)建初很可能出現(xiàn)間隙或者隨著節(jié)點(diǎn)能量的消耗，節(jié)點(diǎn)感知半徑減小也極易出現(xiàn)間隙。因此本文利用移動(dòng)節(jié)點(diǎn)修復(fù)柵欄間隙，在保證最大可能修復(fù)間隙數(shù)量的情況下，使得移動(dòng)節(jié)點(diǎn)的總移動(dòng)距離最小。

1 柵欄間隙

本文將一定比例的可移動(dòng)節(jié)點(diǎn)和靜態(tài)節(jié)點(diǎn)混合部署在監(jiān)測(cè)區(qū)域中，假設(shè)本文中的傳感器節(jié)點(diǎn)可以通過定位技術(shù)獲得坐標(biāo)并且柵欄已經(jīng)通過文獻(xiàn)［14-15］等柵欄構(gòu)建方法構(gòu)建完成。柵欄在工作過程中由于某些原因（故障）導(dǎo)致柵欄出現(xiàn)間隙，可利用移動(dòng)節(jié)點(diǎn)修復(fù)柵欄，當(dāng)移動(dòng)節(jié)點(diǎn)與間隙的距離小于移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離D時(shí)，此時(shí)移動(dòng)節(jié)點(diǎn)可用于修復(fù)該間隙，如圖1所示，柵欄中節(jié)點(diǎn)ni和ni+1之間出現(xiàn)了間隙。

圖1 柵欄間隙圖

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

表1 柵欄間隙查找方法

2 柵欄修復(fù)

本小節(jié)主要是通過基于集合的最大流算法計(jì)算可修復(fù)的柵欄間隙數(shù)量，然后將可移動(dòng)節(jié)點(diǎn)移動(dòng)到柵欄中的間隙處修復(fù)柵欄并且使得移動(dòng)節(jié)點(diǎn)的總移動(dòng)距離最小。

2.1 可修復(fù)間隙的數(shù)量

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

第一小節(jié)已經(jīng)找到了柵欄的間隙并存放在集合Gap中，修補(bǔ)柵欄的過程如圖2所示。

圖2 修復(fù)過程圖

修補(bǔ)長(zhǎng)度為L(zhǎng)的間隙至少需要移動(dòng)節(jié)點(diǎn)的數(shù)量為mnum，如式（1）所示。將間隙長(zhǎng)度L均勻的分為mnum段，每段的中點(diǎn)為待修補(bǔ)點(diǎn)，如圖中g(shù)所示，將移動(dòng)節(jié)點(diǎn)移動(dòng)到這些位置即可完成修復(fù)。

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

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

步驟2 以集合a、b、c、d和待修補(bǔ)點(diǎn)gi、gi+1、gi+2作為點(diǎn)，以集合的元素?cái)?shù)量Na、Nb、Nc、Nd為權(quán)重值，建立有向圖G（V，E），如圖3（b）所示，圖中添加開始節(jié)點(diǎn)u和結(jié)束節(jié)點(diǎn)v，與u連接的權(quán)重值為集合元素的數(shù)量，與v連接的權(quán)重值都為1。V表示有向圖的點(diǎn)集合，E表示有向圖的邊集合，待修復(fù)點(diǎn)和其鄰居移動(dòng)節(jié)點(diǎn)集合存在一條邊，對(duì)應(yīng)的權(quán)重值為集合元素的數(shù)量，公共的鄰居移動(dòng)節(jié)點(diǎn)集合與它對(duì)應(yīng)的多個(gè)待修復(fù)點(diǎn)分別存在一條邊，對(duì)應(yīng)的權(quán)重值為集合元素的數(shù)量，如集合b與待修復(fù)點(diǎn)gi、gi+1都存在一條邊，對(duì)應(yīng)的權(quán)重值為Nb。

步驟3 采用最大流算法計(jì)算圖G的最大流，當(dāng)最大流等于待修復(fù)點(diǎn)的數(shù)量，此時(shí)柵欄間隙能被全部修復(fù)，否則存在不能被修復(fù)的間隙。

2.2 算法復(fù)雜度

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

圖3 集合最大流算法圖

圖4 傳統(tǒng)的有向圖

2.3 間隙修復(fù)方法

本小節(jié)利用可移動(dòng)節(jié)點(diǎn)修復(fù)柵欄的間隙，并且使得移動(dòng)節(jié)點(diǎn)的移動(dòng)距離最小。在2.1小節(jié)的步驟一得到了待修補(bǔ)點(diǎn)集合GD的所有鄰居移動(dòng)節(jié)點(diǎn)集合NG，集合NG中的所有移動(dòng)節(jié)點(diǎn)表示可用于修復(fù)柵欄間隙的節(jié)點(diǎn)，集合NG有num個(gè)元素。集合NG中的可移動(dòng)節(jié)點(diǎn)距離它對(duì)應(yīng)的鄰居待修復(fù)點(diǎn)的距離集合為MD={md1,md2,md3,…,mdnum|mdi≤md}，對(duì)集合非降序排序，得到集合MD′，找出集合MD′中的最小元素mdoptimum和最大元素mdmax。假設(shè)現(xiàn)在存在一個(gè)距離mdoptimum，mdmin＜mdoptimum＜mdmax，使得集合MD中的元素不大于mdoptimum時(shí)，柵欄間隙能被完全修復(fù)，則此時(shí)移動(dòng)節(jié)點(diǎn)的總移動(dòng)距離最短，因此尋找合適的mdoptimum是關(guān)鍵。

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

①

②更新待修復(fù)點(diǎn)的鄰居集合NG，將距離待修復(fù)點(diǎn)大于mdoptimum的節(jié)點(diǎn)從鄰居集合NG中移除，并更新有向圖G的權(quán)重和拓?fù)洹?/p>

③計(jì)算有向圖G的最大流，如果最大流小于n（待修補(bǔ)點(diǎn)集合GD元素?cái)?shù)量），則，最大流不會(huì)大于待修復(fù)點(diǎn)的數(shù)量。如果最大流等于n，且，輸出mdoptimum，算法結(jié)束，否則執(zhí)行步驟2。

3 三維場(chǎng)景中的應(yīng)用

本文提出的柵欄修復(fù)方法主要是利用移動(dòng)節(jié)點(diǎn)與柵欄間隙的距離作為修補(bǔ)依據(jù)。因此該算法同樣適用于三維空間中的柵欄修復(fù)問題。

如在水中部署柵欄以監(jiān)測(cè)水下入侵者，如圖5所示。當(dāng)柵欄中某些傳感器節(jié)點(diǎn)電量耗盡或者外部原因?qū)е鹿?jié)點(diǎn)過早死亡，此時(shí)柵欄出現(xiàn)間隙，利用移動(dòng)節(jié)點(diǎn)使用本文提出的柵欄修復(fù)算法可最優(yōu)化的修復(fù)柵欄。修復(fù)過程中移動(dòng)節(jié)點(diǎn)被充分利用且修復(fù)多個(gè)間隙的移動(dòng)距離總和最小。

圖5 柵欄水下部署圖

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)中已經(jīng)構(gòu)建的柵欄長(zhǎng)度為5 000 m，部署區(qū)域是矩形區(qū)域，長(zhǎng)5 000 m，寬100 m。移動(dòng)節(jié)點(diǎn)均勻分布在部署區(qū)域中。節(jié)點(diǎn)的感知半徑為R，移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離為D。已經(jīng)構(gòu)建的柵欄存在很多間隙，總共有165個(gè)待修復(fù)的點(diǎn)。實(shí)驗(yàn)結(jié)果都是重復(fù)50次的平均結(jié)果。

4.1 柵欄間隙修復(fù)

本文提出利用基于集合的最大流算法計(jì)算能修復(fù)的待修復(fù)點(diǎn)數(shù)量。該方法以傳感器鄰居移動(dòng)節(jié)點(diǎn)和待修補(bǔ)點(diǎn)為單位構(gòu)建有向圖，大大簡(jiǎn)化了有向圖的拓?fù)浣Y(jié)構(gòu)，因此提高了算法的效率且不會(huì)影響算法的結(jié)果。實(shí)驗(yàn)中移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離D=50 m，實(shí)驗(yàn)采用文獻(xiàn)［8-9］的最大流算法（Maxixmum flow）和貪婪算法（Greedy）與本文的基于集合的最大流算法（A-Maxixmum flow）算法進(jìn)行對(duì)比，貪婪算法每次都選取距離待修補(bǔ)點(diǎn)最近的移動(dòng)節(jié)點(diǎn)來(lái)修補(bǔ)，實(shí)驗(yàn)結(jié)果如圖6所示，橫坐標(biāo)表示移動(dòng)節(jié)點(diǎn)的數(shù)量，縱坐標(biāo)表示修復(fù)的待修復(fù)點(diǎn)數(shù)量。

實(shí)驗(yàn)結(jié)果表明隨著移動(dòng)節(jié)點(diǎn)數(shù)量的增加，柵欄中能被修復(fù)的間隙數(shù)量在增加，當(dāng)移動(dòng)節(jié)點(diǎn)達(dá)到一定數(shù)量后，柵欄的間隙能完全被修復(fù)。而且本文提出的方法和文獻(xiàn)［8-9］的方法得到了相同的結(jié)果，而貪婪算法在移動(dòng)節(jié)點(diǎn)數(shù)量相同的情況下，能修復(fù)柵欄間隙的數(shù)量相對(duì)來(lái)說(shuō)比較少。

圖6 柵欄間隙修復(fù)圖

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

利用二分搜索算法（BS）選取移動(dòng)節(jié)點(diǎn)修補(bǔ)柵欄間隙使得移動(dòng)節(jié)點(diǎn)的總移動(dòng)距離最小。實(shí)驗(yàn)對(duì)比了本文的方法和較貪婪算法（Greedy）在修補(bǔ)柵欄間隙時(shí)的節(jié)點(diǎn)移動(dòng)距離。移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離D=30 m和40 m。實(shí)驗(yàn)結(jié)果如圖7所示，橫坐標(biāo)表示移動(dòng)節(jié)點(diǎn)的數(shù)量，縱坐標(biāo)表示移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離。

圖7 平均移動(dòng)距離圖

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

4.3 算法復(fù)雜度分析

本文提出的基于集合的最大流算法（A-Maxix?mum flow）比傳統(tǒng)的最大流（Maxixmum flow）算法具有更好的性能。實(shí)驗(yàn)在移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離為D=40 m、50 m兩種情況下對(duì)比了這兩種方法的運(yùn)算效率，實(shí)驗(yàn)結(jié)果如圖8所示，橫坐標(biāo)表示移動(dòng)節(jié)點(diǎn)的數(shù)量，縱坐標(biāo)表示運(yùn)算時(shí)間（s），實(shí)驗(yàn)采用Matlab編程環(huán)境，硬件平臺(tái)為i7處理器。

圖8 復(fù)雜度分析圖

實(shí)驗(yàn)結(jié)果表明基于集合的最大流算法具有更高的效率，并且隨著移動(dòng)節(jié)點(diǎn)的可移動(dòng)距離增加，算法運(yùn)算的時(shí)間也相應(yīng)增加，這是因?yàn)榭梢苿?dòng)距離越大，有向圖G中的點(diǎn)和線都在增加，圖G的拓?fù)浣Y(jié)構(gòu)更大，所以運(yùn)算時(shí)間更長(zhǎng)。

4.4 三維場(chǎng)景中算法性能實(shí)驗(yàn)

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

圖9中縱坐標(biāo)表示被修復(fù)的間隙數(shù)量，實(shí)驗(yàn)結(jié)果表明在三維場(chǎng)景中，本文提出的基于集合的最大流算法與傳統(tǒng)的最大流算法相比能修復(fù)間隙數(shù)量相同且多于貪婪算法。因?yàn)樨澙匪惴▋H僅將距離柵欄間隙最近的移動(dòng)節(jié)點(diǎn)移動(dòng)到間隙處進(jìn)行修復(fù)，沒有從整體考慮柵欄間隙修復(fù)。圖10中縱坐標(biāo)表示修復(fù)柵欄過程中算法迭代所需的時(shí)間，單位為s，圖10的實(shí)驗(yàn)結(jié)果基于圖9的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果表明本文提出的算法修復(fù)柵欄比傳統(tǒng)的最大流算法修復(fù)柵欄具有更高的效率，由于貪婪算法能修復(fù)的間隙數(shù)量最少，因此最快完成修復(fù)。

圖9 間隙修復(fù)數(shù)量圖

圖10 算法效率圖

5 總結(jié)

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

［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］班冬松，溫俊，蔣杰，等.移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)k-柵欄覆蓋構(gòu)建算法［J］.軟件學(xué)報(bào)，2011，22（9）：2089-2103

［4］郭新明.高效無(wú)線傳感器網(wǎng)絡(luò)強(qiáng)k-柵欄覆蓋節(jié)能算法［J］.計(jì)算機(jī)應(yīng)用，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］舒堅(jiān)，余坤，劉琳嵐，等.無(wú)線傳感器網(wǎng)絡(luò)中基于移動(dòng)模型的柵欄覆蓋研究［J］.計(jì)算機(jī)研究與發(fā)展，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］羅卿，林亞平，王雷，等.傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的柵欄覆蓋控制研究［J］.電子與信息學(xué)報(bào)，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］毛科技，方凱，戴國(guó)勇，等.基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：1058-1065.

［15］王超，范興剛，王恒，等.一種高效強(qiáng)K-柵欄覆蓋構(gòu)建算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（2）：227-23.

戴光麟（1979-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院講師，博士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；

方 凱（1992-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；

毛科技（1979-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院副教授，博士，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘，maokeji@zjut.edu.cn。

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

DAI Guanglin，F(xiàn)ANG Kai，F(xiàn)ANG 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

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61379023，61401397，61302129）；浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目（2015C31066）；浙江省安全生產(chǎn)科技計(jì)劃項(xiàng)目（2013A1001，2013A1002）

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