Construction and Maintenance of Wireless Mobile Backbone Networks
- 2 May 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 17 (1), 239-252
- https://doi.org/10.1109/tnet.2009.2012474
Abstract
We study a novel hierarchical wireless networking approach in which some of the nodes are more capable than others. In such networks, the more capable nodes can serve as mobile backbone nodes and provide a backbone over which end-to-end communication can take place. Our approach consists of controlling the mobility of the backbone nodes in order to maintain connectivity. We formulate the problem of minimizing the number of backbone nodes and refer to it as the Connected Disk Cover (CDC) problem. We show that it can be decomposed into the Geometric Disk Cover (GDC) problem and the Steiner Tree Problem with Minimum Number of Steiner Points (STP-MSP). We prove that if these subproblems are solved separately by gamma- and delta-approximation algorithms, the approximation ratio of the joint solution is gamma+delta. Then, we focus on the two subproblems and present a number of distributed approximation algorithms that maintain a solution to the GDC problem under mobility. A new approach to the solution of the STP-MSP is also described. We show that this approach can be extended in order to obtain a joint approximate solution to the CDC problem. Finally, we evaluate the performance of the algorithms via simulation and show that the proposed GDC algorithms perform very well under mobility and that the new approach for the joint solution can significantly reduce the number of mobile backbone nodes.Keywords
This publication has 23 references indexed in Scilit:
- Relay node placement in large scale wireless sensor networksComputer Communications, 2006
- Steiner tree problem with minimum number of Steiner points and bounded edge-lengthInformation Processing Letters, 1999
- Multicluster, mobile, multimedia radio networkWireless Networks, 1995
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner TreesJournal of Algorithms, 1995
- Covering a set of points in multidimensional spaceInformation Processing Letters, 1991
- Finding tailored partitionsJournal of Algorithms, 1991
- Convexity and the Steiner tree problemNetworks, 1988
- The node‐weighted steiner tree problemNetworks, 1987
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985
- The Architectural Organization of a Mobile Radio Network via a Distributed AlgorithmIEEE Transactions on Communications, 1981