基于集合最大流算法的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