Sending messages to mobile users in disconnected ad-hoc wireless networks

ABSTRACT

An ad-hoc network is formed by a group of mobile hosts upon a wireless network interface. Previous research in this area has concentrated on routing algorithms which are designed for fully connected networks. The usual way to deal with a disconnected ad-hoc network is to let the mobile computer wait for network reconnection passively, which may lead to unacceptable transmission delays. In this paper, we propose an approach that guarantees message transmission in minimal time. In this approach, mobile hosts actively modify their trajectories to transmit messages. We develop algorithms that minimize the trajectory modifications under two different assumptions: (a) the movements of all the nodes in the system are known and (b) the movements of the hosts in the system are not known.

REFERENCES

• 1: Jyh-Jong Fu , R. C. T. Lee, Minimum Spanning Trees of Moving Points in the Plane, IEEE Transactions on Computers, v.40 n.1, p.113-118, January 1991 [doi>10.1109/12.67328]
• 2: Z. J. Haas. A new routing protocol for the reconfigurable wireless network. In Proceedings of the 1997 IEEE 6th International Conference on Universal Personal Communications, ICUPC'97, pages 562 -566, San Diego, CA, October 1997.
• 3: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad-hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153 -181. Kluwer Academic Publishers, 1996.
• 4: Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
• 5: S. Kaxlin and H. M. Taylor. A First Course in Stochastic Processes. Academic Press, New York, 2nd edition, 1975.
• 6: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 7: David Kotz , Robert Gray , Saurab Nog , Daniela Rus , Sumit Chawla , George Cybenko, Agent Tcl: Targeting the Needs of Mobile Computers, IEEE Internet Computing, v.1 n.4, p.58-67, July 1997 [doi>10.1109/4236.612217]
• 8: Zhuyu Lei and Christopher Rose. Wireless subscriber mobility management using adaptive individual location areas for pcs systems. In IEEE International Conference on Communications (ICC), Atlanta, GA, USA, June 1998.
• 9: 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]
• 10: C. Okino and G. Cybenko. Modeling and analysis of active messages in volatile networks. In Proceedings of the 37th Allerton Conference on Communication, Control, Computing, Monticello, IL, September 1999.
• 11: 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
• 12: 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
• 13: Elizabeth Royer and C-K. Toh. A review of current routing protocols for ad hoc mobile wireless networks. In IEEE Personal Communication, volume 6, pages 46 - 55, April 1999.
• 14: T.Imielinski and H. Korth. Location management for networks with mobile users. In Mobile Computing, pages 129-152. KIuwer Publishers, 1996.

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: Applications (SMTP, FTP, etc.)
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Portable devices (e.g., laptops, personal digital assistants)

General Terms:
Algorithms, Design, Human Factors, Measurement, Performance, Theory, Verification