On optimally solving sub‐tree scheduling for wireless sensor networks with partial coverage: A branch‐and‐cut algorithm

Given a wireless sensor network, we consider the problem to minimize its total energy consumption over consecutive time slots with respect to communication activities. Nonempty and disjoint subsets of nodes are required to be active and connected under a tree topology configuration in the different...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2023-06, Vol.81 (4), p.499-513
Main Author: Bianchessi, Nicola
Format: Article
Language:English
Subjects:
Algorithms
Benchmarks
branch‐and‐cut algorithm
consecutive time slots
Energy consumption
energy consumption minimization
Exact solutions
Heuristic
Integer programming
Linear programming
Nodes
partial coverage
Scheduling
Sensors
Software
Solution space
sub‐tree scheduling
Topology
wireless sensor network
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a wireless sensor network, we consider the problem to minimize its total energy consumption over consecutive time slots with respect to communication activities. Nonempty and disjoint subsets of nodes are required to be active and connected under a tree topology configuration in the different time slots, and each network node must be active in a unique time slot. Moreover, the power required by the same pair of network nodes to communicate on the associated direct channel 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 efficient and nontypical separation algorithm for known valid inequalities, and on an easy‐to‐implement primal bound heuristic. The effectiveness of the BC algorithm is empirically shown through an extensive experimental analysis involving 300 newly generated benchmark instances with up to 200 network nodes and 8 time slots. Additionally, 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 tackle problem instances that are not too large.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.22145