Self-stabilizing minimum connected covers of query regions in sensor networks

摘要

Sensor networks are mainly used to gather strategic information in various monitored areas. Sensors may be deployed in zones where their internal memory, or the sensors themselves, can be corrupted. Since deployed sensors cannot be easily replaced, network persistence and robustness are the two main issues that have to be addressed while efficiently deploying large scale sensor networks. The sensing radius of a sensor is the distance within which a sensor can monitor certain events. The communication radius of a sensor is the distance within which a sensor can transmit and receive data. A sensor is said to cover a particular monitored area if a circular area, with radius equal to that sensor's sensing radius, covers that area. A set of sensors is said to be strongly connected if any two sensors in the set can communicate with each other, either directly or indirectly. The goal of forming a minimum connected cover of a query region in sensor networks is to select a subset of nodes that entirely covers a particular monitored area, which is strongly connected, and which does not contain a subset with the same properties. Selecting a minimal number of connected sensors is an NP hard problem. In our work, we address minimality in terms of inclusion. In this paper, we consider the most general case, wherein every sensor has a different sensing and communication radius. We propose two novel and robust solutions to the minimum connected cover problem that can cope with both transient faults (corruptions of the internal memory of sensors) and sensor crash/join. Also, our proposal includes extended versions which use multi-hop information. We also prove the self-stabilization property of our solutions, both analytically and through extended simulations. A self-stabilizing system is a system that, when started from an arbitrary state, is always guaranteed to recover following the occurrence of (transient) faults and converge to a desired behavior (legitimate state) in a finite number of steps. Via simulations, we also conclude that our solutions provide better performance, in terms of coverage, than preexisting self-stabilizing solutions. Moreover, we observe that multi-hop solutions produce a better approximation to an optimal cover set.