A Branch-and-Cut Algorithm for the Minimum Energy Symmetric Connectivity Problem in Wireless Networks

摘要

In this paper, we study the minimum energy symmetric connectivity problem in wireless sensor networks. This problem is to assign transmission power to each sensor node in a wireless sensor network such that all the sensor nodes are connected by bidirectional links and the overall power consumption is minimized. The determined transmission powers must support the communication session between each pair of nodes along a single-hop path or a multi-hop path. We view this feature as strong symmetric connectivity defined on a digraph. We present two mixed integer programming formulations involving an exponential number of constraints. By introducing some logical constraints, we give the first formulation. Based on this formulation, we further produce some strong cuts which result in the second stronger formulation. Using these formulations, we then devise a branch-and-cut algorithm. Computational results demonstrate that our algorithm is an efficient algorithm for the instances with up to 100 nodes.