In this study, the problem of designing a multi-sink clustered Wireless Sensor Network (WSN) is considered. WSNs are central to the Internet of Things (IoT), and an extensive range of applications has emerged. WSN applications demand prolonged unattended operation. As sensor nodes have limited battery capacity, maximizing network lifespan is challenging. In this article, we investigate the hierarchical clustering to save energy, assigning distinct roles (master, bridge, or slave nodes) to sensors. We propose a mixed integer programming flow-based formulation with arc-sink assignment variables. In addition, a set of valid inequalities is proposed, either derived from existing literature or adapted versions. Computational experiments are conducted to evaluate the proposed approach, involving up to forty nodes and eight sinks.

International audience

In this article, we investigate the stochastic maximum weight forest problem. We present two mathematical formulations for the problem: a polynomial sized one based on the characterization of forests in graphs and a formulation with an exponential number of constraints. We give a proof of the correctness of the new formulation and present a polynomial reduction from the set cover problem to give some insight about the complexity of this problem. We introduce an L‐shaped decomposition approach for the polynomial formulation, thus allowing the optimal solution of large scale instances with up to 90 nodes. Finally, we propose a Kruskal based variable neighborhood search (VNS) metaheuristic to compute near optimal solutions with significantly less computational effort. Our numerical results show that the VNS approach provides tight near optimal solutions with a gap less than 1% for most of the instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 289–305 2015