A column generation heuristic for optimal wireless sensor network design with mobile sinks

Wireless Sensor Networks (WSNs) consist of a high number of tiny, multi-functional, electronic devices called sensors. They collectively provide a distributed environment that is capable of monitoring remote areas. Collected information is transmitted in a direct or multi-hop fashion to the gateway nodes called sinks. An even distribution of energy loads among the sensors is critical for elongating network lifetime. There are four main WSN design issues that substantially affect the distribution of the energy: locations of the sensors, schedule of the active and standby periods of the sensors, trajectory of the mobile sink(s) and routes for data flows. As a result, many studies try to make energy usage more efficient by optimal determination of these design issues. However, only a few of them provide a unified frame in which all four design issues are integrated. In this work, we follow this line of research and propose a column generation heuristic for a Mixed Integer Linear Programing (MILP) model that integrates all design issues. Based on the extensive numerical experiments, we can say that the heuristic outperforms its competitors in the literature.