Energy efficiency and balancing are very important issues from the perspective of increasing the lifetime of a wireless sensor network (WSN). In this study, we concentrate on energy balancing. Given a WSN, we consider the problem to minimize its total power consumption over consecutive time slots with respect to communication activities. Disjoint subsets of nodes are required to be active and connected under a tree topology configuration in each time slot. Moreover, each network node must be active in a unique time slot, and the power consumption to establish a direct communication channel between the same pair of network nodes may vary in the different time slots. The problem has been recently introduced in the literature under the name Sub-Tree Scheduling for Wireless Sensor Networks with Partial Coverage. We focus on the exact solution of the problem. We present a branch-and-cut (BC) algorithm based on a novel Integer Linear Programming formulation which allows avoiding the introduction of symmetries in the solution space. In particular, the algorithm relies on an easy-to-implement primal bound heuristic to restrict the search space. The effectiveness of the BC algorithm is empirically proven through an extensive experimental analysis involving 300 newly generated benchmark instances with up to 200 network nodes and 8 time slots. Moreover, the experimental results show that the BC algorithm represents a valid computational tool to benchmark the performance of heuristics addressing the problem, and can be used in practice, as an heuristic solver, to address problem instances that are not too large.
Citation
Bianchessi, N. (2022). On optimally solving sub-tree scheduling for wireless sensor networks with partial coverage. Università degli Studi di Milano, http://hdl.handle.net/2434/934107.