Distributed sensing coverage maintenance in sensor networks

Sensing coverage is one of the key performance indicators of a large-scale sensor network. Sensing coverage holes may appear anywhere in the network field at any time due to random deployment, depletion of sensor battery power, or natural events in the deployment environment such as strong wind blowing some sensors away. Discovering the exact boundaries of coverage holes is important because it enables fast and efficient patching of coverage holes. In this thesis, we propose a framework of sensing coverage maintenance in sensor networks. In our framework, a sensor network consists of stationary and mobile sensors, where mobile sensors are used as patching hosts. We divide the coverage maintenance into two components: coverage hole discovery and coverage hole patching, and propose new solutions to both components. (1) We present two efficient distributed algorithms that periodically discover the precise boundaries of coverage holes. Our algorithms can handle the case that the transmission range of a sensor is smaller than twice the sensing range of the sensor. This case is largely ignored by previous work. (2) We present an efficient hole patching algorithm, which runs in linear time, based on the knowledge of the precise boundary of each coverage hole. We further propose new solutions for looking up available patching hosts, and movement planning. We present rigorous mathematical proofs of the correctness of the proposed hole discovery algorithms. We also show the running time and the performance bound in terms of mobile sensors needed of our hole patching algorithm through solid mathematical analysis. Our simulation results show that our distributed discovery algorithms are much more efficient than their centralized counterparts in terms of network overhead and total discovery time while still achieving the same correctness in discovering the boundaries of coverage holes. Furthermore, our patching algorithm performs well in terms of number of mobile sensors needed with a linear running time, and our hole patching scheme can achieve fast hole patching time when moving mobile sensors in a parallel manner