Algorithms for Barrier Coverage with Wireless Sensors
Student thesis: Doctoral Thesis
Related Research Unit(s)
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, ﬂexibility and easy installation are advantages of using WSNs. Recent years have witnessed an increasing development in the ﬁeld 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 battleﬁelds, 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 ﬁxed sensing ranges.
Speciﬁcally, in the ﬁrst 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 ﬁrst 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 oﬀsets. This motivates us to consider the variant with oﬀsets. More precisely, we consider the barrier coverage problem with the line-based oﬀsets 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 eﬃciently.
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 tradeoﬀ 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 diﬀerent 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 ﬁnal 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 ﬁrst-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 diﬀerent sensing ranges, we prove the NP-hardness by reduction from the Partition problem.