Efficient distributed low-cost backbone formation for wireless networks
Authors:
- Yu WangYWYu Wang
- Weizhao WangWWWeizhao Wang
- Xiang-Yang LiXLXiang-Yang Li
- 19 June 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 17 (7) , 681-693
Abstract
Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless ad hoc or sensor networks recently. Previous methods are mostly designed to minimize the size of the backbone. 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 large cost. Then, an efficient distributed method to construct a weighted backbone with low cost is proposed. 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 (i.e., the maximum ratio of costs of adjacent nodes is bounded) or the network maximum node degree is bounded. We also show that, with a small modification, the 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 three (or four) times the least cost (or hop) path in the original communication graph. Our theoretical. results are corroborated by our simulation studies. Finally, we discuss several possible ad hoc network applications of our proposed backbone formation algorithmsKeywords
This publication has 34 references indexed in Scilit:
- Applications of k-local MST for topology control and broadcasting in wireless ad hoc networksIEEE Transactions on Parallel and Distributed Systems, 2004
- An extended localized algorithm for connected dominating set formation in ad hoc wireless networksIEEE Transactions on Parallel and Distributed Systems, 2004
- Geometric spanners for wireless ad hoc networksIEEE Transactions on Parallel and Distributed Systems, 2003
- Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating SetsInformation and Computation, 1999
- 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
- Simple heuristics for unit disk graphsNetworks, 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