Han Ruisong, Yang Wei, Zhang Li
School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China.
School of Electronic and Electrical Engineering, University of Leeds, Leeds LS2 9DX, UK.
Sensors (Basel). 2018 Feb 10;18(2):534. doi: 10.3390/s18020534.
Barrier coverage has been widely used to detect intrusions in wireless sensor networks (WSNs). It can fulfill the monitoring task while extending the lifetime of the network. Though barrier coverage in WSNs has been intensively studied in recent years, previous research failed to consider the problem of intrusion in transversal directions. If an intruder knows the deployment configuration of sensor nodes, then there is a high probability that it may traverse the whole target region from particular directions, without being detected. In this paper, we introduce the concept of crossed barrier coverage that can overcome this defect. We prove that the problem of finding the maximum number of crossed barriers is NP-hard and integer linear programming (ILP) is used to formulate the optimization problem. The branch-and-bound algorithm is adopted to determine the maximum number of crossed barriers. In addition, we also propose a multi-round shortest path algorithm (MSPA) to solve the optimization problem, which works heuristically to guarantee efficiency while maintaining near-optimal solutions. Several conventional algorithms for finding the maximum number of disjoint strong barriers are also modified to solve the crossed barrier problem and for the purpose of comparison. Extensive simulation studies demonstrate the effectiveness of MSPA.
屏障覆盖已被广泛用于检测无线传感器网络（WSN）中的入侵行为。它可以在延长网络寿命的同时完成监测任务。尽管近年来对WSN中的屏障覆盖进行了深入研究，但以往的研究未能考虑横向入侵问题。如果入侵者了解传感器节点的部署配置，那么它很有可能从特定方向穿越整个目标区域而不被检测到。在本文中，我们引入了交叉屏障覆盖的概念，以克服这一缺陷。我们证明了寻找最大交叉屏障数量的问题是NP难问题，并使用整数线性规划（ILP）来制定优化问题。采用分支定界算法来确定最大交叉屏障数量。此外，我们还提出了一种多轮最短路径算法（MSPA）来解决优化问题，该算法通过启发式工作来保证效率，同时保持接近最优的解决方案。还对几种用于寻找最大不相交强屏障数量的传统算法进行了修改，以解决交叉屏障问题并用于比较。大量的仿真研究证明了MSPA的有效性。
