A new approach to channel access scheduling for Ad Hoc networks

ABSTRACT

Three types of collision-free channel access protocols for ad hoc networks are presented. These protocols are derived from a novel approach to contention resolution that allows each node to elect deterministically one or multiple winners for channel access in a given contention context (e.g., a time slot), given the identifiers of its neighbors one and two hops away. The new protocols are shown to be fair and capable of achieving maximum utilization of the channel bandwidth. The delay and throughput characteristics of the contention resolution algorithms are analyzed, and the performance of the three types of channel access protocols is studied by simulations.

REFERENCES

• 1: P.W. Baier. CDMA or TDMA? CDMA for GSM? In 5th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, pages 1280-4, The Hague, Netherlands, 18-23 Sept. 1994. IOS Press.
• 2: Alan A. Bertossi , Maurizio A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.701-709, May 1992, Florence, Italy
• 3: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 4: I. Chlamtac and S. Kutten. A spatial-reuse TDMA/FDMA for mobile multi-hop radio networks. In Proceedings IEEE INFOCOM, pages 389-94, Washington, DC, March 1985.
• 5: I. Chlamtac and A. Lerner. Fair algorithms for maximal link activation in multihop radio networks. IEEE Transactions on Communications, 35(7):739-46, July 1987.
• 6: I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
• 7: B.P. Crow, I. Widjaja, L.G. Kim, and P.T. Sakai. IEEE 802.11 Wireless Local Area Networks. IEEE Communications Magazine, 35(9):116-26, Sept 1997.
• 8: A. Ephremides and T.V. Truong. Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications, 38(4):456-60, April 1990.
• 9: S. Even, O. Goldreich, S. Moran, and P. Tong. On the NP-completeness of certain network testing problems. Networks, 14(1):1-24, Spring 1984.
• 10: W. Feller. An introduction to probability theory and its applications, volume 1. New York: John Wiley, 2nd edition, 1957.
• 11: W. Fuhrmann and A. Eizenhofer. Radio access protocol of the new GSM land mobile communication standard. In 38th IEEE Vehicular Technology Conference: Telecommunications Freedom - Technology on the Move, pages 30-7, Philadelphia, PA, USA, 15-17 June 1988.
• 12: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Solutions to hidden terminal problems in wireless networks, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.39-49, September 14-18, 1997, Cannes, France
• 13: J.J. Garcia-Luna-Aceves and J. Raju. Distributed assignment of codes for multihop packet-radio networks. In MILCOM 97 Proceedings, pages 450-4, Monterey, CA, USA, 2-5 Nov. 1997.
• 14: J. J. Garcia-Luna-Aceves , Asimakis Tzamaloukas, Reversing the collision-avoidance handshake in wireless networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.120-131, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313516]
• 15: Limin Hu, Distributed code assignments for CDMA Packet Radio Network, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.668-677, Dec. 1993 [doi>10.1109/90.266055]
• 16: M. Joa-Ng and I.T. Lu. Spread spectrum medium access protocol with collision avoidance in mobile ad-hoc wireless network. In IEEE INFOCOM '99, pages 776-83, New York, NY, USA, 21-25 March 1999.
• 17: Ji-Her Ju , Victor O. K. Li, An optimal topology-transparent scheduling method in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.298-306, June 1998 [doi>10.1109/90.700893]
• 18: R. J. Larsen and M. L. Marx. An introduction to probability and its applications. Number p.165-167. Englewood Cliffs, N.J. : Prentice-Hall, 1985.
• 19: T. Makansi. Trasmitter-Oriented Code Assignment for Multihop Radio Net-works. IEEE Transactions on Communications, 35(12):1379-82, Dec. 1987.
• 20: L.C. Pond and V.O.K. Li. A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks. In MILCOM 89, volume 1, pages 70-4, Boston, MA, USA, 1989.
• 21: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]
• 22: R. Ramaswami and K.K. Parhi. Distributed scheduling of broadcasts in a radio network. In IEEE INFOCOM'89, volume 2, pages 497-504, Ottawa, Ont., Canada, 23-27 April 1989. IEEE Comput. Soc. Press.
• 23: Timothy J. Shepard, A channel access scheme for large dense packet radio networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.219-230, August 28-30, 1996, Palo Alto, California, United States
• 24: J.A. Silvester. Perfect scheduling in multi-hop broadcast networks. In Proceedings of the Sixth International Conference on Computer Communication, pages 449-54, London, UK, 7-10 Sept. 1982.
• 25: Z. Tang and J.J. Garcia-Luna-Aceves. A Protocol for Topology-Dependent Transmission Scheduling. In Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), New Orleans, Louisiana, September 21-24 1999.
• 26: F. A. Tobagi and L. Kleinrock. Packet switching in radio channels: Part II - the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution. IEEE Transactions on communications, 23(12):1417-33, December 1975.
• 27: C. Zhu and M.S. Corson. A five-phase reservation protocol (FPRP) for mobile ad hoc networks. In IEEE INFOCOM '98, volume 1, pages 322-31, San Francisco, CA, USA, 29 March-2 April 1998.

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 communications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Experimentation, Performance