Target monitoring algorithm in directional sensor networks considering lifetime and fault tolerance

Abstract

Target coverage by directional sensor networks (DSNs) is a fundamental problem where targets should be covered by at least one sensor. During coverage, prolonging network lifetime and providing fault tolerance are the major challenges. To tackle 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 thesis, we address these two antithetical approaches and provide a solution to resolve this problem. We find the maximum possible number of set covers by activating a subset of sensors within a given upper bound on sensor overlap. A sensor can not participate within the set covers more than this bound value. To solve this problem, at first we formulate the problem as a Linear Programming (LP) problem which gives the optimal solution. As LP 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 with respect to different performance metrices through extensive simulations.