Heuristics for designing multi-sink clustered WSN topologies

In this study, the problem of building cluster-based topologies for Wireless Sensor Networks with several sinks is considered. The optimization relies on different levels of decision: choosing which sensors are masters and balancing the load among sinks. The topology associated with each sink is modeled as an Independent Dominating Set with Connecting requirements (IDSC). Thus, the solution is a partition of a given graph into as many IDSC as there are sinks. In addition, several optimization criteria are proposed to implicitly or explicitly balance the topology. The network lifetime is improved since it benefits from a clustered structure and the number of hops control. The former reduces the average amount of messages to be sent and the latter improves the average energy consumption for messages to be sent. Different combinations of criteria are proposed in lexicographical order. They are compared in terms of maximum number of clusters per topology, of deviation between the smallest and the biggest number of clusters considering all topologies, and of total number of clusters in the final topology. Two local searches, a two-step local search and a Variable Neighborhood Descent, are developed. Each one is embedded into a multi-start framework. Results are provided for instances with up to 10 000 sensors and up to five sinks.