On the behavior of communication links of a node in a multi-hop mobile environment

ABSTRACT

In this work, we develop an analytical framework to investigate the behavior of the communication links of a node in a random mobility environment. Analytical expressions characterizing various properties related to the formation, lifetime and expiration of links are derived. The derived framework can be used to design efficient algorithms for medium access, routing and transport control, or to analyze and optimize the performance of existing network protocols. A number of applications of the characteristics investigated, such as selection of stable routes, route cache lifetime optimization, providing Quality-of-Service (QoS) data communication and analysis of route lifetime are discussed. In particular, we focus on designing an efficient updating strategy for proactive routing protocols based on the derived statistics. Using simulations, we show that the proposed strategy can lead to significant performance improvements in terms of reduction in routing overhead, while maintaining high data packet delivery ratio and acceptable latency.

REFERENCES

• 1: S. Agarwal, A. Ahuja, J.P. Singh, R. Shorey, "Route-lifetime Assessment Based Routing (RABR) Protocol for Mobile Ad-hoc Networks," it ICC 2000, vol. 3, pp.1697 - 1701, New Orleans.
• 2: B. Bellur, R.G. Ogier, "A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks," it IEEE INFOCOM, March 1999.
• 3: Christian Bettstetter , Hannes Hartenstein , Xavier Pérez-Costa, Stochastic properties of the random waypoint mobility model, Wireless Networks, v.10 n.5, p.555-567, September 2004 [doi>10.1023/B:WINE.0000036458.88990.e5]
• 4: Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, March 2003 [doi>10.1109/TMC.2003.1233531]
• 5: T. Camp, J. Boleng, V. Davies, "A Survey of Mobility Models for Ad Hoc Network Research," it Wireless Communication \& Mobile Computing (WCMC), vol. 2, no. 5, pp. 483-502, 2002.
• 6: R. Dube, C. Rais, K.-Y. Wang, S. Tripathi, "Signal stability based adaptive routing (SSA) for ad hoc networks," it IEEE Personal Communications, Feb. 1997.
• 7: Michael Gerharz , Christian de Waal , Matthias Frank , Peter Martini, Link Stability in Mobile Wireless Ad Hoc Networks, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.30-42, November 06-08, 2002
• 8: A.J. Goldsmith, S.B. Wicker, "Design challenges for energy-constrained ad hoc wireless networks," it IEEE Wireless Communications, vol. 9, no. 4, Aug. 2002.
• 9: Z.J. Haas, M.R. Pearlman, P. Samar, "The Zone Routing Protocol (ZRP) for Ad Hoc Networks," it IETF MANET, Internet Draft, July 2002.
• 10: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.427-438, August 2001 [doi>10.1109/90.944341]
• 11: Z.J. Haas, M.R. Pearlman, P. Samar, "The Intrazone Routing Protocol (IARP) for Ad Hoc Networks," it IETF MANET, Internet Draft, July 2002.
• 12: Gavin Holland , Nitin Vaidya, Analysis of TCP performance over mobile ad hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.219-230, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313540]
• 13: Yih-Chun Hu , David B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.231-242, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345952]
• 14: S. Jiang, D.J. He, J.Q. Rao, "A prediction-based link availability estimation for mobile Ad Hoc networks," it IEEE INFOCOM 2001, Anchorage, April, 2001.
• 15: B. Liang, Z.J. Haas, "Optimizing Route-Cache Lifetime in Ad Hoc Networks," it IEEE INFOCOM 2003, San Francisco, April, 2003.
• 16: A.B. McDonald, T.F. Znati, "A mobility-based framework for adaptive clustering in wireless ad hoc networks," it IEEE JSAC, 17(8), Aug. 1999.
• 17: John P. Mullen, Robust approximations to the distribution of link distances in a wireless network occupying a rectangular region, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.2, p.80-91, April 2003 [doi>10.1145/950391.950393]
• 18: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 19: G. Pei, M. Gerla, T.-W. Chen, "Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks," it ICC 2000, New Orleans, LA, June 2000.
• 20: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 21: Narayanan Sadagopan , Fan Bai , Bhaskar Krishnamachari , Ahmed Helmy, PATHS: analysis of PATH duration statistics and their impact on reactive MANET routing protocols, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778444]
• 22: Prince Samar , Marc R. Pearlman , Zygmunt J. Haas, Independent zone routing: an adaptive hybrid routing framework for ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.595-608, August 2004 [doi>10.1109/TNET.2004.833153]
• 23: P. Samar, M.R. Pearlman, Z.J. Haas, "Hybrid Routing: The Pursuit of an Adaptable and Scalable Routing Frame-work for Ad Hoc Networks," it Ad hoc Wireless Networking, X. Cheng, X. Huang and D.-Z. Du (eds.), Kluwer Academic Publishers, Nov. 2003.
• 24: P. Samar, S.B. Wicker, "Link Dynamics in a Multi-Hop Mobile Environment," under submission.
• 25: William Su , Sung-Ju Lee , Mario Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management, v.11 n.1, p.3-30, January–February 2001 [doi>10.1002/nem.386]
• 26: Chai-Keong Toh, Associativity-Based Routing for Ad Hoc Mobile Networks, Wireless Personal Communications: An International Journal, v.4 n.2, p.103-139, March 1997 [doi>10.1023/A:1008812928561]
• 27: D. Turgut, S.K. Das, M. Chatterjee, "Longevity of Routes in Mobile Ad hoc Networks," it VTC Spring 2001, Rhodes, Greece, May, 2001.
• 28: J. Yoon, M. Liu, B. Noble, "Random Waypoint Considered Harmful," it IEEE INFOCOM 2003, San Francisco, CA, April 2003.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
ad hoc networks, communication link, interarrival time, lifetime, link dynamics, mobility, proactive routing, updating