Mobile backbone networks --: construction and maintenance

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 approac 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 problem.We show that it can be decomposed into the Geometric Disk Cover (GDC)problem and the Steiner Tree Problem wit Minimum Number of Steiner Points (STP-MSP). We prove that if these sub-problems are solved separately by γ- and δ- approximation algorithms, the approximation ratio of t e joint solution is γ + δ. 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 Connected Disk Cover 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 approac for the joint solution can significantly reduce the number of required Mobile Backbone Nodes.

REFERENCES

• 1: D. J. Baker and A. Ephremides. The architectural organization of a mobile radio network via a istributed algorithm. IEEE Trans. Commun., 29(11):1694--1701, 1981.
• 2: Donghui Chen , Ding-Zhu Du , Xiao-Dong Hu , Guo-Hui Lin , Lusheng Wang , Guoliang Xue, Approximations for Steiner Trees with Minimum Number of Steiner Points, Journal of Global Optimization, v.18 n.1, p.17-33, September 2000 [doi>10.1023/A:1008384012064]
• 3: X. Cheng, D.-Z. Du, L. Wang, and B. Xu. Relaysensor placement in wireless sensor networks. To appear in ACM/Springer WINET 2006.
• 4: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 5: M. Franceschetti, M. Cook, and J. Bruck. A geometric theorem for approximate disk covering algorithms. Technical Report ETR035 Caltech, 2001.
• 6: J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete mobile centers. Disc. Comput. Geom., 30(1):45--63, 2003.
• 7: M. R. Garey an D. S. Johnson. Computers and Intractibility Freeman, 1979.
• 8: T. Gonzalez. Covering a set of points in multidimensional space. Inf. Proc. Letters 40(4):181--188, 1991.
• 9: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
• 10: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 11: John Hershberger, Smooth kinetic maintenance of clusters, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777800]
• 12: John Hershberger , Subhash Suri, Finding tailored partitions, Journal of Algorithms, v.12 n.3, p.431-463, Sept. 1991 [doi>10.1016/0196-6774(91)90013-O]
• 13: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 14: Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004 [doi>10.1023/B:MONE.0000013626.53247.1c]
• 15: A. Kansal, M. Rahimi, D. Estrin, W. J. Kaiser, G. J. Pottie, and M. B. Srivastava. Controlled mobility for sustainable wireless sensor networks. In Proc. IEEE SECON'04 October 2004.
• 16: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 17: Guo-Hui Lin , Guoliang Xue, Steiner tree problem with minimum number of Steiner points and bounded edge-length, Information Processing Letters, v.69 n.2, p.53-57, Jan. 29, 1999 [doi>10.1016/S0020-0190(98)00201-4]
• 18: M. Lu, J. Wu, M. Cardei, and M. Li. Energy-efficient connected coverage of discrete targets in wireless sensor networks. In Proc. ICCNMC'05 August 2005.
• 19: J. S. Provan, Convexity and the Steiner tree problem, Networks, v.18 n.1, p.55-72, Spring 1988 [doi>10.1002/net.3230180108]
• 20: I. Rubin, A. Behza, R. Zhang, H. Luo, and E. Caballero. TBONE:a mobile-backbone protocol for a hoc wireless networks. In Proc. IEEE Aerospace Conf., March 2002.
• 21: A. Segev, The node-weighted Steiner tree problem, Networks, v.17 n.1, p.1-17, Spring 1987 [doi>10.1002/net.3230170102]
• 22: A. Srinivas, G. Zussman, and E. Modiano. Construction and maintenance of a mobile backbone for wireless networks. MIT/LIDS Technical Report #2676 October 2005.
• 23: Chaitanya Swamy , Amit Kumar, Primal–Dual Algorithms for Connected Facility Location Problems, Algorithmica, v.40 n.4, p.245-269, September 2004 [doi>10.1007/s00453-004-1112-3]
• 24: J. Tang, B. Hao, and A. Sen. Relay node placement in large scale wireless sensor networks, Computer Commun., 29(4):490--501, 2006.
• 25: Kaixin Xu , Xiaoyan Hong , Mario Gerla, Landmark routing in ad hoc networks with mobile backbones, Journal of Parallel and Distributed Computing, v.63 n.2, p.110-122, February 2003 [doi>10.1016/S0743-7315(02)00058-8]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
approximation algorithms, controlled mobility, disk cover, distributed algorithms, wireless networks