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

Research Article

Improved Topology Control Algorithms for Simple Mobile Networks

Download314 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-11723-7_30,
        author={Fei Che and Errol Lloyd and Liang Zhao},
        title={Improved Topology Control Algorithms for Simple Mobile Networks},
        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={topology control mobile ad hoc networks Delaunay triangulations Voronoi diagrams 1-Connected power optimization},
        doi={10.1007/978-3-642-11723-7_30}
    }
    
  • Fei Che
    Errol Lloyd
    Liang Zhao
    Year: 2012
    Improved Topology Control Algorithms for Simple Mobile Networks
    ADHOCNETS
    Springer
    DOI: 10.1007/978-3-642-11723-7_30
Fei Che1,*, Errol Lloyd1,*, Liang Zhao2,*
  • 1: University of Delaware
  • 2: QUALCOMM Inc.
*Contact email: fei@cis.udel.edu, elloyd@cis.udel.edu, zhaol@qualcomm.com

Abstract

Topology control is the problem of assigning powers to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. Topology control in wireless ad hoc networks under the (SMN) Model was introduced in [6]. In that model, there is only one moving node. That node moves on a straight line segment throughout a unit time interval and no assumptions are made about the moving speed. In this paper we study the problem of minimizing the maximum power consumed by any network node to maintain a (i.e. connected) topology under the SMN model. For that problem, in [6], a decision algorithm that runs in time ( ) and an optimization algorithm that runs in time ( log) are described. In this paper we improve upon those results by taking advantage of Voronoi diagrams and Delaunay triangulations. We provide three main results: a decision algorithm that runs in time (log); an optimization algorithm with an expected running time of ( log); and a constant factor approximation algorithm that runs in time (log). Simulation results evaluating the approximation algorithm are also provided.