Cluster based routing using a k-tree core backbone for mobile ad hoc networks

ABSTRACT

The problem of routing in Mobile Ad hoc Networks is non-trivial because of the dynamic nature of the network topology. In addition to computing shortest paths, as in wire-line networks, any routing scheme must consider that the topology of the network can vary while the packet is being routed.Cluster based schemes have been proposed which segregate the network into manageable sets for maintaining routing information. In this paper we propose a novel method of constructing the clusters and a backbone based on the concept of a k-tree core. We also propose an hierarchical routing scheme using this cluster information and evaluate its performance through extensive simulations.

REFERENCES

• 1: B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
• 2: T.-W. Chen and M. Gerla. Global state routing: A new routing scheme for ad-hoc wireless networks. In Proc of IEEE ICC '98, 1998.
• 3: F. Chin and H. Ting. An almost linear time and o(vlog v + e) messages distributed algorithm for minimum weight spanning trees. In Proc. of the Foundations of Computer Science (FOCS) Conf., Portland, Oregon, Oct 1985.
• 4: Michalis Faloutsos , Mart Molle, Optimal distributed algorithm for minimum spanning trees revisited, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.231-237, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.225474]
• 5: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 6: K. Krizman, T. Bieda, and T. Rappaport. Wireless position location: fundamentals, implementation strategies, and source of error. In Proc. of the 47th Veh. Tech. Conf., pages 919--923, 1997.
• 7: Shan-Chyun Ku , Wei Kuan Shih , Biing-Feng Wang, Efficient Parallel Algorithms for Optimally Locating a k-Leaf Tree in a Tree Network, Proceedings of the international Conference on Parallel Processing, p.16-19, August 11-15, 1997
• 8: C. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265--1275, Sep 1997.
• 9: S. Peng and W.-T. Lo. A simple optimal parallel algorithm for a core of a tree. Journal of Parallel and Distributed Computing, 20:388--392, 1994.
• 10: Shietung Peng , A. B. Stephens , Yelena Yesha, Algorithms for a core and k-tree core of a tree, Journal of Algorithms, v.15 n.1, p.143-159, July 1993 [doi>10.1006/jagm.1993.1034]
• 11: C. E. Perkins. Ad Hoc Networking. Addison Wesley, 2000.
• 12: C. E. Perkins. Ad hoc on demand distance vector (AODV) routing. Technical report, Internet draft, draft-ietf-manet-aodv-00.txt., 2000.
• 13: E. M. Royer and C.-K. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Magazine on Personal Communication, 17(8):46--55, 1999.
• 14: Biing-Feng Wang, Finding a k-Tree Core and a k-Tree Center of a Tree Network in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.186-191, February 1998 [doi>10.1109/71.663884]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Performance, Theory

Keywords:
cluster based routing, distributed algorithms, multihop packet, radio networks, wireless ad hoc networks