On fault tolerant ad hoc network design

ABSTRACT

Minimal configuration and quick deployment of ad hoc networks make it suitable for numerous applications such as emergency situations, border monitoring, and military missions, etc. For such ad hoc networks to fulfill their mission in a timely manner, they should be able to establish a connection between nodes and to maintain this connection until the communication halts. Establishing a connection is achieved by using a routing protocol, and maintaining it is achieved by having a resilient fault tolerant network. In this paper, we propose a network design scheme that incorporates these features. We first propose a special network topology that is unique in terms of how nodes are interconnected. After constructing the initial topology, we propose a distributed routing protocol that allows any two sites to communicate by traversing at most 2 nodes regardless of the network size. We conducted both simulation study and theoretical analysis; the results show that the proposed scheme is resilient to network dynamics and has high quality as well as efficient routing.

REFERENCES

• 1: C. P. Low and Y. J. Lee. Distributed multicast routing with end-to-end delay and delay variation constraints. Computer Communications, 24(9):848--862, 2000.
• 2: Perkins, C. E., Royer, E. M., and Das, S. R. Ad hoc on-demand distance vector routing. IETF Draft, October 1999.
• 3: Johnson, D., and Maltiz, D. Dynamic source routing in ad hoc wireless networks. Mobile Computing, T. Imelinsky and H. Korth, Eds. Kluwer Academic Publishers, pages 153--181, 1996.
• 4: Royer, E. M., AND Toh, C. K. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, pages 46--55, 1999.
• 5: 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
• 6: TOH, C.-K. A novel distributed routing protocol to support ad hoc mobile computing. Proc. 1996 IEEE 15th Annual Int'l. Phoenix Conf. Comp. and Commun., pages 480--486, March 1996.
• 7: TOH, C.-K. Long-lived ad-hoc routing based on the concept of associativity. IETF Internet Draft, March 1999.
• 8: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 9: J. Wu. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 4(1):59--70, March 2002.
• 10: Jamil A. Shaikh , Julio Solano , Ivan Stojmenovic , Jie Wu, New Metrics for Dominating Set Based Energy Efficient Activity Scheduling in Ad Hoc Networks, Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, p.726, October 20-24, 2003
• 11: Jie Wu , Ming Gao , Ivan Stojmenovic, On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.346-356, September 03-07, 2001
• 12: J. Wu and B. Wu. A transmission range reduction scheme for power-aware broadcasting in ad hoc networks using connected dominating sets. Proc. of 2003 IEEE Semiannual Vehicular Technology Conference (VTC2003-fall), October 2003.
• 13: J. Wu, B. Wu, and I. Stojmenovic. Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets. Proc. of IASTED International Conference on Wireless and Optical Communication (WOC 2002), 2002.
• 14: J. Wu, B. Wu, and I. Stojmenovic. Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets. Wireless Communications and Mobile Computing, a special issue on Research in Ad Hoc Networking, Smart Sensing, and Pervasive Computing, 3(4):425--438, June 2003.

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.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Design

Keywords:
ad hoc networks, fault tolerance, network design and planning