Research Article
Improved Topology Control Algorithms for Simple Mobile Networks
@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
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.