方 凯，吴武豪，陈 琼

（中电海康集团有限公司，浙江 杭州 310012）

0 引言

无线传感器网络栅栏覆盖的主要作用是监测是否有监测目标发生入侵，如在军事方面，将栅栏部署在阵地前沿能有效监测敌人是否发动突袭；在环保方面，将栅栏部署在工厂周围能监测污染物扩散情况；在林业方面，将栅栏部署在保护区边界可有效监测火灾的蔓延等[1]。

目前在 WSN（Wireless Sensor Network）栅栏覆盖领域已取得丰厚的研究成果，如在栅栏构建方面Saipulla（2013）等人提出一种基于线性部署的栅栏构建方法，沿目标路径部署传感器节点，从而提高了栅栏覆盖的数量[2]。毛科技（2015）等人对传统的蚁群算法进行改进使之适用于WSN栅栏构建问题，在部署区域内搜索存在的栅栏[3]。Wang Z（2017）等人考虑到利用WSN定位方法或GPS模块获得的节点位置信息存在误差，提出一种位置容忍的栅栏构建方法，从而有效的解决节点位置不准确而导致栅栏构建不完整的问题[4]。Nguyen T G（2018）等人提出一种分布式的栅栏构建算法，利用网络区域聚类技术减少节点间信息交换，通过移动少量可移动节点完成栅栏构建[5]。为延长栅栏的生存时间，栅栏调度算法被学者研究，如Kumar S（2017）等人提出了一种K-栅栏最佳调度算法，充分利用了传感器节点的能耗，大幅延长了栅栏的生存时间[6]。Xu B（2016）等人通过构建入侵轨迹模型，预测栅栏中被频繁攻击的位置，并调度可移动节点强化这些位置，从而延长了栅栏的生存时间[7]。在栅栏修复方面的研究，如Deng（2013）等人提出了一种混合传感器网络栅栏间隙修复方法，通过调整传感器节点的感知半径，使可移动节点修复间隙的移动距离最短[8]。Chen J（2017）等人提出一种利用栅栏段旋转方法修复栅栏间隙[9]。Xu H（2016）等人提出最小费用方案和自适应贪婪移动方案修复栅栏间隙[10]。

上述栅栏构建和栅栏修复方面的研究都取得了较好的成果，但这些方法对静态节点的利用率不高，而对可移动节点的需求较大。考虑到成本以及栅栏构建、修复的代价问题，本文提出一种能耗优先的WSN栅栏覆盖方法，该方法充分利用静态传感器节点构建和修复栅栏，如静态传感器节点不能完成栅栏构建或修复工作，再派遣少量的可移动节点，并且使可移动节点的移动距离最短，从而实现代价最小化。

1 相关模型

假设栅栏覆盖的应用场景为理想场景，在节点部署区域中没有障碍物的干扰，可移动节点都是沿直线移动，且传感器节点采用电池供电，能耗有限。

在研究中传感器节点采用二元感知模型，以传感器节点为圆心，感知半径为r，当监测目标在节点感知范围内，则被节点感知的概率为1，否则为0，如公式1所示。

公式1中o表述传感器节点位置，t表示监测目标位置，d（o，t）表示监测目标距离传感器节点的欧氏距离，Po，t表示监测目标在位置t处被节点o感知的概率。

栅栏覆盖可分为强栅栏覆盖和弱栅栏覆盖，本文研究强栅栏覆盖，传感器节点部署在带状区域中，监测目标沿任意路径从带状区域的一侧穿越到另一侧至少能被一个传感器节点感知，强栅栏覆盖模型如图1所示。

图1 强栅栏覆盖图

在栅栏构建阶段，主要能量消耗发生在可移动节点移动过程中，而在感知方面的能量消耗较少。参考文献[11～12]研究了可移动节点移动能耗模型，由于节点在移动过程中消耗的能量远远高于感知所消耗的能量，且本文的衡量指标是节点移动所消耗的能量，因此节点感知的能耗忽略不计，移动1m消耗能量为3.6J。

2 栅栏构建方法

2.1 拓扑图建立

静态传感器节点和可移动传感器节点按一定比例随机部署在带状区域中，且节点位置可通过WSN定位方法或GPS模块得到，在构建栅栏过程中为充分利用静态传感器节点，尽可能降低可移动节点的需求量，采用静态传感器节点构建全连接拓扑图，如图2a）所示，图中S为部署区域最左端节点，E 为部署区域最右端节点，di，j为节点 ni和 nj之间的欧氏距离。

在拓扑图中从节点S开始到节点E结束，存在一条路径，当该路径被静态节点和可移动节点完全覆盖时，则完成了栅栏的构建。为了得到栅栏构建过程中不同路径所需要的可移动节点数量，需要将全连接拓扑图转化为可移动节点需求图，如图2b）所示。

图2 拓扑图转换过程图

图 2b）中 Mni，j表示节点 ni和节点 nj之间的边被节点感知区域完全覆盖所需要的最少可移动节点数量，如公式2所示。

式中：di,j——节点ni和nj之间的欧氏距离；

r——感知半径。

2.2 最优栅栏构建路径

图2b）构建了部署区域内可移动节点需求图，倘若存在一条路径从节点S开始，到节点E结束，移动少量的可移动节点到该路径上某些位置即可完成路径的全覆盖，则该路径被称为栅栏构建路径。若构建栅栏过程中移动节点的移动距离总和最短，则该路径为最佳栅栏构建路径。

如果能够在拓扑图中寻找到最佳栅栏构建路径，则构建栅栏的能耗会最低。影响栅栏构建能耗的因素有2个：①栅栏构建过程中需要移动的传感器节点数量；②可移动节点的平均移动距离。由于传感器节点随机部署在区域中，因此并不能计算出哪条栅栏构建路径构建栅栏的移动节点移动距离之和最短，但可以首先从因素①考虑，利用KSP[13～14]算法选择需要可移动节点数量最少的前K条路径，当K取值合适时，最佳栅栏构建路径被包含在其中。如图3所示，图中利用KSP算法计算得到需要可移动节点数量最少的前3条栅栏构建路径Path1、Path2、Path3，将可移动节点移动到待修复位置即可完成栅栏构建，其中Path1需要4个可移动节点、Path2需要5个可移动节点，Path3需要4个可移动节点。

图3 栅栏构建路径图

当确定K条栅栏构建路径后，采用匈牙利算法虚拟派遣可移动节点到待修复位，并计算沿每条构建路径完成构建栅栏可移动节点移动距离之和。匈牙利算法是一种最优指派方法[15][16]，假设指派a个工人完成a个任务，每个工人可以做多种工作，但是对每种工作的收费不同，利用匈牙利算法分配工作能使完成所有工作花费的代价最小。同样的利用匈牙利算法派遣可移动节点完成栅栏构建能够实现最优派遣，保证可移动节点的移动距离总和最短。本文对匈牙利算法进行改进使之适用于栅栏覆盖问题。传统的匈牙利算法需要a个人去完成a个任务，而在栅栏覆盖问题上，派遣m个可移动节点去修复n个待修复位置，而m与n可能并不相同，如果m＞n，则虚拟出m-n个待修复位，可移动节点到虚拟待修复位的距离都为0；如果m＜n，则不能完成栅栏构建。如图4所示，图中总共有m1、m2、m3二个可移动节点，两个修复位置1和2，因此需要虚拟出一个修复位置o，根据上述规则建立匈牙利算法的代价矩阵，如公式3所示。

图4 匈牙利派遣图

公式3中di，j表示传感器节点距离待修复位的欧氏距离 （di，j≤R，R为可移动节点的最大移动距离），其中 di，o=0，表示节点距离虚拟修复位 o的距离都为0。

建立匈牙利算法的代价矩阵后即可计算出沿K条栅栏构建路径构建栅栏可移动节点的移动距离之和，假设分别完成图3中3条栅栏构建路径可移动节点移动的距离总和为D1、D2和D3，且D1＜D2，D1＜D3，则 Path1是最佳栅栏构建路径，沿该路径构建栅栏消耗的能量最低。

2.3 栅栏构建过程

2.2小节从图2b）可移动节点需求拓扑图中选择了最佳栅栏构建路径，并采用匈牙利算法得到可移动节点最优派遣方式，因此本节根据派遣方案将可移动节点移动到最佳栅栏构建路径的修复位置完成栅栏构建，如图5所示。图中可移动传感器节点 m1、m2、m3、m4被派遣到最佳栅栏构建路径上，完成栅栏的构建，且能够保证构建栅栏时可移动节点的移动距离之和最短。

图5 栅栏构建图

3 栅栏间隙修复

栅栏运行一段时间后，由于传感器节点能量耗尽或故障等原因导致栅栏出现间隙，监测目标可通过间隙穿越栅栏而不被检测到，因此需要对栅栏间隙进行修复。修复方法与上述栅栏构建方法类似，首先定位到栅栏间隙的左右端，判断栅栏中相邻传感器节点的感知区域是否相互重叠。如果不重叠，则判断该处出现间隙，然后继续寻找栅栏间隙的另一侧，如图6中栅栏出现了间隙，间隙最左侧为L传感器节点，最右侧为R节点。定位到栅栏间隙后，以L节点为起始节点，R节点为结束点构建静态节点全连接拓扑图，然后将全连接拓扑图转化为可移动节点需求拓扑图，最后利用匈牙利算法派遣可移动节点完成栅栏的修复工作。

图6 栅栏间隙图

4 仿真实验

采用i5处理器、8G内存的PC机，利用Matlab平台进行仿真实验。将静态传感器节点和可移动传感器节点按照一定比例混合，随机均匀部署在一个长为1000m，宽为200m的带状区域中，静态节点和可移动节点的感知半径r=50m，根据提出的方法构建栅栏如图7所示。实验分析了本文提出的方法的相关性能，并在栅栏构建方面与任勇默（2017）[17]等提出的FCOIS方法进行对比，在栅栏修复方面与 Saipulla A（2013）[18]等提出的 Optimal方法、贪婪算法（Greedy）进行对比。

图7 栅栏构建结果图

4.1 栅栏构建

部署区域确定的情况下，影响栅栏构建的因素主要包括传感器节点数量、可移动节点与静态节点的比例、传感器节点的感知半径r。评价栅栏构建方法的指标为可移动节点的能耗、栅栏构建率。实验结果如图8和图9所示，实验中可移动节点和静态节点各占50%，可移动节点最大移动距离R=200m。

实验结果表明，随着带状区域内传感器节点数量增加，构建栅栏时消耗的能量逐渐降低。因为部署传感器节点数量增加，节点密度提高，构建栅栏时可移动节点需要移动的距离更短，因此能耗逐渐减低，且本文提出的方法在构建栅栏时的能耗远低于FCOIS方法。因为本文的方法首先利用静态传感器节点构建栅栏，当静态传感器节点不能完成栅栏构建时，才移动少量的可移动节点完成栅栏构建；而FCOIS方法完全采用可移动节点构建栅栏，因此需要移动的节点数量远多于本文方法。在传感器节点数量为50个时，节约了971.6J能量，在传感器节点为150个时，节约了426.5J能量。

图8 栅栏构建能耗图

在栅栏构建成功率方面，部署传感器节点数量相同时，FCOIS算法的成功率高于本文方法。因为FCOIS完全采用可移动节点构建栅栏，因此节点具有较高的灵活性，能够自由移动到任何指定位置完成栅栏的构建；而本文方法构建栅栏大部分采用静态传感器节点，倘若静态传感器节点部署位置比较集中，则可移动节点即使能够移动较远距离也不能完成栅栏构建。当传感器节点数量为90个时，FCOIS方法的栅栏构建成功率达到100%，当传感器节点数量为130个时（在部署区域内部署130个传感器节点密度合适），本文方法的栅栏构建成功率达到100%。

图9 栅栏覆盖率图

综上实验结果，本文提出的方法在栅栏构建方面，能够节约大量的能耗，且当带状区域内部署的传感器节点达到一定数量时，具有100%的栅栏构建成功率。

4.2 栅栏修复

Saipulla A （2013）[18]提出的 Optimal栅栏间隙修复方法首先定位到间隙所在位置，然后计算需要的可移动节点数量，最后采用二分法派遣可移动节点完成栅栏修复使得可移动节点移动距离之和最短。贪婪算法派遣最近的可移动传感器节点修复栅栏。而本文提出的栅栏间隙修复方法首先寻找可以使用的静态传感器节点，当静态传感器节点不能完成栅栏修复时，派遣可移动节点修复栅栏。在带状区域中部署100个传感器节点，可移动节点占30%，静态节点各占70%，可移动节点最大移动距离R=200m，实验结果如图10和图11所示。

由图10可以看出，在栅栏间隙修复方面，随着栅栏间隙长度的增加，二种栅栏修复方法修复栅栏的能耗呈梯度升高。因为栅栏间隙为50m和100m时需要的可移动节点数量相同，250m和300m需要的移动节点数量相同，因此消耗的能耗呈梯度提高。且本文的方法的能耗低于Optimal方法和Greedy方法，因为首先考虑使用静态节点修复栅栏间隙，当静态节点不能完成修复时，再派遣可移动节点，因此需要调度的可移动节点数量相对其他两种方法较少，因此节点移动的总距离更短，消耗的能量更低。Optimal方法的能耗低于Greedy方法，因为Optimal方法使用二分搜索方法，能够使派遣的可移动节点最优 （总移动距离最短），而Greedy方法每次都派遣距离待修复位置最近的可移动节点完成栅栏修复，会陷入局部最优问题，因此Greedy方法修复栅栏间隙的能耗高于Optimal方法。

图10 栅栏修复能耗图

在栅栏修复率方面的实验如图11所示。实验结果表明随着栅栏间隙长度的增加，栅栏修复成功率会逐渐降低。因为栅栏间隙长度增加，需要的可移动节点数量增加，但可移动节点存在最大可移动距离R，故修复率逐渐降低。本文方法的栅栏修复成功率最高，在栅栏间隙长度为350m时，比Optimal方法提高了8%左右，比Greedy方法提高了12.6%左右，Optimal方法的修复成功率高于Greedy方法。

图11 栅栏修复率图

5 结语

本文研究了一种低能耗的WSN栅栏覆盖方法，通过构建静态节点拓扑图，利用KSP算法和匈牙利算法构建栅栏使得可移动节点移动距离之和最小，即栅栏构建的能耗最小。然后提出了栅栏间隙修复方法，同样利用前述算法支配可移动节点修复间隙，实验结果表明该方法在栅栏覆盖方面具有较好的性能。后续工作将进一步研究能耗最低的K-栅栏覆盖方法。