Topological design of Wireless sensor network: Formulations and exact algorithms

Abstract

The subject of this thesis is the design of Wireless Sensor Networks (WSN). Given a limited set of sensors and a single sinks, we are particularly interested in the topological WSN design problem. This problem consists in clustering the sensors and defining a communication topology to gather the sensed information throughout the network. Natural connectivity and coverage requirements are satisfied assuming an imposition on the number of clusters. Two variants of the problem are studied: p-arborescence star problem (P-ASP) and p-cycle star problem (P-CSP). P-ASP organizes the network into p clusters and defines the communication topology as rooted directed tree, i.e., an arborescence rooted at the sink. In P-CSP, mobile-sink based networks are designed replacing the core arborescence by a directed cycle. We introduce Mixed Integer Programming formulations and exact solution approaches. To validate our approaches, experiments are performed on instance sets extended from the literature.