SHORT: self-healing and optimizing routing techniques for mobile ad hoc networks

ABSTRACT

On demand routing protocols provide scalable and cost-effective solutions for packet routing in mobile wireless ad hoc networks. The paths generated by these protocols may deviate far from the optimal because of the lack of knowledge about the global topology and the mobility of nodes. Routing optimality affects network performance and energy consumption, especially when the load is high. In this paper, we define routing optimality using different metrics such as path length, energy consumption along the path, and energy aware load balancing among the nodes. We then propose a framework of Self-Healing and Optimizing Routing Techniques (SHORT) for mobile ad hoc networks. While using SHORT, all the neighboring nodes monitor the route and try to optimize it if and when a better local sub-path is available. Thus SHORT enhances performance in terms of bandwidth and latency without incurring any significant additional cost. In addition, SHORT can be also used to determine paths that result in low energy consumption or optimize the residual battery power. Thus, we have detailed two broad classes of SHORT algorithms: Path-Aware SHORT and Energy-Aware SHORT. Finally, we evaluate SHORT using the ns-2 simulator. The results demonstrate that the performance of existing routing schemes can be significantly improved using the proposed SHORT algorithms.

REFERENCES

• 1: Suman Banerjee , Archan Misra, Minimum energy paths for reliable communication in multi-hop wireless networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513818]
• 2: Timthoy X. Brown , Harold N. Gabow , Qi Zhang, Maximum flow-life curve for a wireless ad hoc network, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501434]
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: J. Broch, D. B. Johnson and D. A. Maltz, "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks," IETF Internet draft, draft-ietf-manet-dsr-01.txt, Dec. 1998 (work in progress.)
• 5: T. Camp, J. Boleng, and V. Davies, "A Survey of Mobility Models for Ad Hoc Network Research," Wireless Communication & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol. 2, no. 5, pp. 483--502, 2002.
• 6: J. Gomez and A. Campbell, "Power-aware routing optimization for wireless ad hoc networks," In proceedings of High Speed Networks Workshop(HSN), June, 2001.
• 7: J. Gomez, A. T. Campbell, M. Naghshineh, and C. Bisdikian, "PARO: A Power-Aware Routing Optimization Scheme for Mobile Ad hoc Networks," draft-gomez-paro-manet-00.txt, work in progress, IETF, Mar. 2001.
• 8: C. Gui, and P. Mohapatra, "A Self-Healing and Optimizing Routing Technique for Ad Hoc Networks," Computer Science Department, UC Davis, Technical Report CSE-2002-23.
• 9: 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]
• 10: A. Iwata, C. C. Chiang, G. Pei, M. Gerla and T. Chen, "Scalable Routing Strategies for Ad Hoc Wireless Networks," IEEE Journal of Selected Areas on Communications, vol. 17, No. 8, Aug 1999.
• 11: D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad-Hoc Wireless Networks," Mobile Computing, T. Imielinski and H. Korth, Eds., Kluwer, 1996, pp.153--81.
• 12: Sung-Ju Lee , Mario Gerla, Routing and multicasting strategies in wireless mobile ad hoc networks, 2000
• 13: S. J. Lee and M. Gerla, "AODV-BR: Backup Routing in Ad Hoc Networks," Proc. IEEE WCNC 2000, Chicago, IL, Sep. 2000.
• 14: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 15: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 16: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 17: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 18: C.E. Perkins, E.M. Royer, and S.R. Das, "Ad-Hoc On Demand Distance Vector (AODV) Routing," Internet Draft, draft-ietf-manet-aodv-05.txt, Mar 2000, work in progress.
• 19: E. M. Royer and C-K. Toh, "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks," IEEE Personal Communications, April 1999.
• 20: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 21: Marcelo Spohn , J. J. Garcia-Luna-Aceves, Neighborhood aware source routing, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501417.501419]
• 22: Ivan Stojmenovic , Xu Lin, Power-Aware Localized Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1122-1133, November 2001 [doi>10.1109/71.969123]
• 23: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting, IEEE Transactions on Mobile Computing, v.1 n.3, p.176-191, July 2002 [doi>10.1109/TMC.2002.1081754]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, energy-aware SHORT, path-aware SHORT, routing protocol, self-healing and optimizing routing techniques