Distributed low-cost backbone formation for wireless ad hoc networks
Authors:
Open Access
- 25 May 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2-13
Abstract
Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless networks. Previous methods are mostly designed to minimize the backbone size. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with a large cost. We then propose an efficient distributed method to construct a weighted sparse backbone with low cost. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded. We also show that with a small modification the constructed backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than 3 (or 4) times of the least cost (or hop) path in the original communication graph. As a side product, we give an efficient overlay based multicast structure whose total cost is no more than 10 times of the minimum when the network is modeled by UDG. Our theoretical results are corroborated by our simulation studies.Keywords
This publication has 26 references indexed in Scilit:
- Geometric spanners for wireless ad hoc networksIEEE Transactions on Parallel and Distributed Systems, 2003
- Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networksIEEE Transactions on Parallel and Distributed Systems, 2002
- Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating SetsInformation and Computation, 1999
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- Adaptive clustering for mobile wireless networksIEEE Journal on Selected Areas in Communications, 1997
- Multicluster, mobile, multimedia radio networkWireless Networks, 1995
- The Design and Simulation of a Mobile Radio Network with Distributed ControlIEEE Journal on Selected Areas in Communications, 1984
- The Architectural Organization of a Mobile Radio Network via a Distributed AlgorithmIEEE Transactions on Communications, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979