Sensor coverage and actors relocation in wireless sensor and actor networks (WSAN) : optimization models and approximation algorithms

Abstract

Wireless Sensors and Actor Networks (WSAN) have a wide variety of applications such as military surveillance, object tracking and habitat monitoring. Sensors are data gathering devices. Selecting the minimum number of sensors for network coverage is crucial to reduce the cost of installation and data processing time. Actors in a WSAN are decision-making units. They need to be communicating with their fellow actors in order to respond to events. Therefore, the need to maintain a connected inter-actor network at all times is critical. In the Actor Relocation Problem (Chapter 2) of this thesis we considered the problem of finding optimal strategies to restore connectivity when inter-actor network fails. We used a mixed integer programming formulation to find the optimal relocation strategies for actors in which the total travel distance is minimized. In our formulation we used powers of the adjacency matrix to generate constraints that ensure connectivity. In the Sensor Coverage Problem (Chapter 3) we developed a mixed integer programming model to find the minimum number of sensors and their locations to cover a given area. We also developed a bi-level algorithm that runs two separate optimization algorithms iteratively to find the location of sensors such that every point in a continuous area is covered.