Scalable location services for hierarchically organized mobile ad hoc networks

ABSTRACT

This paper proposes a location service to assist location-based routing protocols, realized through a novel Associativity-Based clustering protocol. The main goal of our scheme, which employs hierarchical principles, is to minimize the control traffic associated with location-management. In location-based routing protocols, the control traffic is mainly due to location-updates, queries and responses. Our scheme employs a novel geographically-oriented clustering scheme in order to minimize control traffic without impairing performance. In our location management scheme, nodes are assigned home-zones, and are required to send their location-updates to their respective home-zones through a dominating-set. This strategy, unlike similar location-management approaches, minimizes inevitable superfluous flooding by every node, and prevents location updates and queries from traversing the entire network unnecessarily, hence conserving bandwidth and transmission power. The proposed scheme is evaluated through mathematical analysis and simulations, and the results indicate that our protocol scales well with increasing node-count, node-density and node-speed.

REFERENCES

• 1: Sivavakeesar, S.,, and Pavlou, G., Stable Clustering Through Mobility Prediction for Large-Scale Multihop Intelligent Ad Hoc Networks, In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'04), Georgia, USA, Mar. 2004, vol. 3, 1488 -- 1493.
• 2: Hong, X., Gerlo, M., Yi, Y., Xu, K., and Kwon, T.J., Scalable Ad Hoc Routing in Large, Dense Wireless Networks Using Clustering and Landmarks, In Proceedings of the IEEE International Conference on Communications. (ICC'02), Apr. 2002, vol. 25, no. 1, 3179 -- 3185.
• 3: Seung-Chul M. Woo , Suresh Singh, Scalable routing protocol for ad hoc networks, Wireless Networks, v.7 n.5, p.513-529, September 2001 [doi>10.1023/A:1016726711167]
• 4: Philip, S.J., and Qiao, C., ELF: Efficient Location Forwarding in Ad Hoc Networks, In Proceedings of the IEEE Global Telecommunications Conference (Globecom'03), Dec. 2003, vol. 22, no. 1, 913 -- 918.
• 5: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 6: Sucec, J., and Marsic, I., Location Management for Hierarchically Organized Mobile Ad hoc Networks, In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'02), Florida, USA, March 2002, 603--607.
• 7: Mauve, M., Widmer, J., and Hartenstein, H., A Survey on Position-Based Routing in Mobile Ad Hoc Networks, IEEE Network, Nov./Dec. 2001, vol. 15, no. 6, 30 -- 39.
• 8: Hong, X., Xu, K., and Gerla, M., Scalable Routing Protocols for Mobile Ad Hoc Networks, IEEE Network, Jul./Aug. 2002, vol. 16, no. 4, 11 -- 21.
• 9: Toh, C-K., Lin, G., and Delwar, M., Implementation and Evaluation of an Adaptive Routing Protocol for Infrastructureless Mobile Networks, In Proceedings of the IEEE International Conference on Computer Communications & Networks (IC3N'00), Las Vegas, 2000.
• 10: Sivakumar, R., Sinha, P., and Bharghavan, V., CEDAR: A Core-Extraction Distributed Ad hoc Routing Algorithm, IEEE Journal on Selected Areas in Communications, August 1999, vol. 17, no. 8, 1 -- 12.
• 11: Sucec, J., and Marsic, I., Clustering Overhead for Hierarchical Routing in Mobile Ad Hoc Networks, In Proceedings of the IEEE Conference on Computer Communications (INFOCOM'02), New York, NY, USA, June 2002, 1698 -- 1706.
• 12: Xiang Zeng , Rajive Bagrodia , Mario Gerla, GloMoSim: a library for parallel simulation of large-scale wireless networks, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.154-161, May 26-29, 1998, Banff, Alberta, Canada
• 13: Perkins, C.E., Belding-Royer, E.M., and Chakeres, I., Ad Hoc On Demand Distance Vector (AODV) Routing, IETF Internet draft, draft-perkins-manet-aodvbis-00.txt, Oct 2003 (Work in Progress ).
• 14: Johnson, D.B., Maltz, D.A., and Hu, Y-C., The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR), IETF Internet draft, draft-ietf-manet-dsr-10.txt, Jul. 2004.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Performance

Keywords:
hierarchical clustering, location service, location-based routing, location-management