Research Article
Exact Models for the -Connected Minimum Energy Problem
@INPROCEEDINGS{10.1007/978-3-642-11723-7_26, author={Christina Burt and Yao-ban Chan and Nikki Sonenberg}, title={Exact Models for the -Connected Minimum Energy Problem}, proceedings={Ad Hoc Networks. First International Conference, ADHOCNETS 2009, Niagara Falls, Ontario, Canada, September 22-25, 2009. Revised Selected Papers}, proceedings_a={ADHOCNETS}, year={2012}, month={7}, keywords={Minimum transmission exact model k-connectivitiy mixed-integer programming}, doi={10.1007/978-3-642-11723-7_26} }- Christina Burt
Yao-ban Chan
Nikki Sonenberg
Year: 2012
Exact Models for the -Connected Minimum Energy Problem
ADHOCNETS
Springer
DOI: 10.1007/978-3-642-11723-7_26
Abstract
We consider the minimum energy problem for a mobile ad hoc network, where any node in the network may communicate with any other via intermediate nodes. To provide quality of service, the network must be connected, even if one or more nodes drop out. This motivates the notion of -connectivity. The minimum energy problem aims to optimise the total energy that all nodes spend for transmission. Previous work in the literature includes exact mixed-integer programming formulations for a 1-connected network. We extend these models for when the network is -connected, and compare the models for various network sizes. As expected, the combinatorial nature of the problem limits the size of the networks that we can solve to optimality in a timely manner. However, these exact models may be used for the future design of mobile ad hoc networks and provide useful benchmarks for heuristics in larger networks.