Algorithms for Barrier Coverage with Wireless Sensors


Student thesis: Doctoral Thesis

View graph of relations


  • Xiao ZHANG

Related Research Unit(s)


Awarding Institution
Award date8 Sep 2016


Wireless Sensor Networks (WSNs) consist of a number of wireless sensor nodes, which are characterized by having limited battery power. Their low cost, non-intrusiveness, flexibility and easy installation are advantages of using WSNs. Recent years have witnessed an increasing development in the field of WSNs, in which the coverage problem has been a research hot spot. A major application of coverage in WSNs is intrusion detection, such as detecting intruders that attempt to penetrate country borders or boundaries of battlefields, which is referred to as barrier coverage. In the area, we study the barrier coverage problem from two perspectives, i.e., static sensors with adjustable sensing ranges and mobile sensors with fixed sensing ranges.

Specifically, in the first topic, we consider the barrier coverage problem for a line interval, in which we are given a set of sensors and the goal is to determine a range assignment with the lowest possible cost. We study two variants of this problem. The first variant is the case when the sensors are deployed exactly on a line interval, for which we propose a solution based on integer linear programming (ILP) for the k-coverage problem. Due to the environmental factors in the real world, we observe that the sensors would be distributed along the line interval with random offsets. This motivates us to consider the variant with offsets. More precisely, we consider the barrier coverage problem with the line-based offsets deployment and present an approximation algorithm with a ratio of 4/3 in O(n2) time. Furthermore, based on the line interval division, we give an FPTAS runs in O(n3/ϵ2 ) time for 0 <ϵ< 1. We also evaluate the performance by experiments and show that our approximation algorithms run correctly and efficiently.

In addition, in previous works, the barrier coverage problem is solved by considering only one objective with various constraints. To address a number of practical issues in this problem, we introduce three relevant objectives: (1) minimizing total power consumption while satisfying full coverage, (2) minimizing the number of active sensors to improve the reliability, and (3) minimizing the active sensor nodes’ maximum sensing range to maintain fairness. With the aim of obtaining a better tradeoff among the three objectives, we present an evolutionary multiobjective algorithm, which is evaluated experimentally.

In the second topic, we consider the problem of covering a line interval by mobile sensors, in which the mobile sensors may have different energy dissipation ratios that are characterized by a weight. In this problem, we are given a set of sensors and are required to move each sensor from the initial position to the final position such that (i) every point of the barrier is covered and (ii) the maximum moving cost (weight times moving distance) is minimized. We present a first-known algorithm when all sensors have the same sensing range and our algorithm runs in O(n2 log n log log n) time. When the sensors have different sensing ranges, we prove the NP-hardness by reduction from the Partition problem.