Ad Hoc Networks. First International Conference, ADHOCNETS 2009, Niagara Falls, Ontario, Canada, September 22-25, 2009. Revised Selected Papers

Research Article

Exact Models for the -Connected Minimum Energy Problem

Download272 downloads
  • @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
Christina Burt1,*, Yao-ban Chan1,*, Nikki Sonenberg1,*
  • 1: University of Melbourne
*Contact email: c.burt@ms.unimelb.edu.au, y.chan@ms.unimelb.edu.au, n.sonenberg@ms.unimelb.edu.au

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.