Advertisement
Published in:
2009 | OriginalPaper | Chapter
A Branch-and-Cut Algorithm for the Minimum Energy Symmetric Connectivity Problem in Wireless Networks
Authors : Xiangyong Li, Y. P. Aneja
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.