On target monitoring in directional sensor networks by jointly considering network lifetime and fault tolerance
Suman Saha, Abdullah Al Zishan, Ashikur Rahman · 2019
The target coverage in directional sensor networks (DSNs) faces two major challenges: prolonging network lifetime, and providing fault tolerance. To address the first challenge, sensors are divided into multiple set covers each of which is capable of monitoring all the targets and schedule them in a round-robin fashion. Therefore, maximizing the number of set covers can lead to a longer network lifetime. Interestingly, the number of set covers is increased when the sensors are allowed to overlap within the set covers. Thus in one extreme, one can attain maximum lifetime by allowing the sensors to overlap boundlessly. Besides lifetime, fault tolerance is another important aspect which has been overlooked by most of the research works. Practically, sensor nodes are very much prone to failure and difficult to be replaced. If a particular sensor dies out, then all set covers containing the faulty sensor get affected. This indicates another extreme: increasing the sensor overlap within set covers decrease fault tolerance of the network. In this paper, we address these two antithetical approaches and provide a solution to resolve this problem. At first, we formulate the problem as an Integer Linear Programming (ILP) problem which gives the optimal solution. As ILP formulation is computationally expensive, we develop two approximation greedy algorithms which are solvable in polynomial time. We also investigate the performance of our proposed heuristics through rigorous simulation experiments.