A real-time medium access control protocol for ad hoc wireless local area networks

ABSTRACT

We develop and analyze a simple, elegant medium access control (MAC) protocol for use in transmitting real-time data in point to point ad hoc wireless local area networks (WLANs). Our enhancement of IEEE 802.11, real-time MAC (RT-MAC), achieves dramatic reductions in mean delay, missed deadlines, and packet collisions by selectively discarding packets and sharing station state information. For example, in a 50 station network with a normalized offered load of 0.7, mean delay is reduced from more than 14 seconds to less than 45 ms, late packets are reduced from 76% to less than 1%, and packet collisions are reduced from 36% to less than 1%. Regression models are developed from simulation data to describe network behavior in terms of throughput, mean delay, ratio of late packets, and ratio of collisions. Stations using RT-MAC are interoperable with stations using IEEE 802.11.

REFERENCES

• 1: N. Abramson. The ALOHA system-another alternative for computer communications. In AFIPS Conference Proceedings 1970 Fall Joint Computer Conference, volume 37, pages 281--285, 1970.
• 2: N. Abramson. The throughput of packet broadcasting channels. IEEE Transactions on Communications, COM-25(1):117--128, January 1977.
• 3: ASC/ENA Wright-Patterson AFB, OH, Wright-Patterson AFB, OH. Digital Time Division Command/Response Multiplex Data Bus, MIL-STD-1553B edition, September 1978.
• 4: R. O. Baldwin, N. J. Davis IV, and S. F. Midkiff. Implementation of an IEEE 802.11 wireless LAN model using OPNET. In Proceedings of OPNETWORK'98. MIL3, Inc., June 1998.
• 5: P. Bhagwat, P. Bhattacharya, A. Krishna, and S. Tripathi. Enhancing throughput over wireless LANs using channel state dependent packet scheduling. In Proceedings IEEE INFOCOM '96, pages 1133--1140. Institute of Electrical and Electronics Engineers, 1996.
• 6: Pravin Bhagwat , Partha Bhattacharya , Arvind Krishma , Satish K. Tripathi, Using channel state dependent packet scheduling to improve TCP throughput over wireless LANs, Wireless Networks, v.3 n.1, p.91-102, March 1997 [doi>10.1023/A:1019132612232]
• 7: V. Bharghavan. Performance evaluation of algorithms for wireless medium access. In IEEE International Computer Performance and Dependability Symposium. IPDS'98, pages 86--95. Institute of Electrical and Electronics Engineers, 1998.
• 8: G. Bianchi, L. Fratta, and M. Oliveri. Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 wireless LANs. The Seventh IEEE International Symposium on Personal, Indoor and Mobile Radio Communications PIMRC '96, pages 392--396, October 1996.
• 9: C. R. Braun. Wireless LAN standard proposal highlights the need for speed. Wireless Systems Design, 3(9):13--16, September 1998.
• 10: F. Calì, M. Conti, and E. Gregori. IEEE 802.11 wireless LAN: Capacity analysis and protocol enhancement. In INFOCOM '98, Conference on Computer Communications, pages 142--149. Institute of Electrical and Electronics Engineers, 1998.
• 11: T. Carpenter, K. Driscoll, K. Hoyme, and J. Carciofini. ARINC 659 scheduling: Problem definition. In 1994 Real-Time Systems Symposium, pages 165--169. Institute of Electrical and Electronics Engineers, 1994.
• 12: B. Crow, I. Widjaja, J. G. Kim, and P. Sakai. Performance of IEEE 802.11 wireless local area networks. In Proceedings of the SPIE, volume 2917, pages 480--491. The International Society of Optical Engineers, 1996.
• 13: Rohit Dube , Cynthia D. Rais , Satish K. Tripathi, Improving NFS Performance Over Wireless Links, IEEE Transactions on Computers, v.46 n.3, p.290-298, March 1997 [doi>10.1109/12.580425]
• 14: Editors of IEEE 802.11. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Draft Standard 802.11, P802.11/D6.1. Institute of Electrical and Electronics Engineers, Inc., New York, May 1997.
• 15: J. Ellsberger, D. Hogrefe, and A. Sarma. SDL, Formal Object-Oriented Language for Communicating Systems. Prentice Hall Europe, Hertfordshire, UK, 1997.
• 16: L. Kleinrock F. S. Tobagi. Packet switching in radio channels: Part III-polling and (dynamic) split-channel reservation multiple access. IEEE Transactions on Communications, COM-24(8):832--845, August 1976.
• 17: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley and Sons, Inc., New York, 1991.
• 18: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 19: L. Kleinrock. Queueing Systems Volume 2: Computer Applications. John Wiley and Sons, Inc., New York, 1976.
• 20: L. Kleinrock. Principles and lessons in packet communications. Proceedings of the IEEE, 66(11):1320--1329, November 1978.
• 21: L. Kleinrock and M. O. Scholl. Packet switching in radio channels: New conflict-free multiple access schemes. IEEE Transactions on Communications, COM-28(7):1015--1029, July 1980.
• 22: L. Kleinrock and F. A. Tobagi. Packet switching in radio channels: Part I: CSMA modes and their throughput-delay characteristics. IEEE Transactions on Communications, COM-23(12):1400--1416, December 1975.
• 23: James F. Kurose , Mischa Schwartz , Yechiam Yemini, Multiple-access protocols and time-constrained communication, ACM Computing Surveys (CSUR), v.16 n.1, p.43-70, March 1984 [doi>10.1145/861.870]
• 24: T. Liu, J. A. Silvester, and A. Polydoros. Performance evaluation of R-ALOHA in distributed packet radio networks with hard real-time communications. In 1995 IEEE 45th Vehicular Technology Conference, volume 25, pages 554--558. Institute of Electrical and Electronics Engineers, Inc., July 1995.
• 25: M. H. MacDougall, Simulating computer systems: techniques and tools, MIT Press, Cambridge, MA, 1987
• 26: Nicholas James Malcolm, Hard real-time communication in high speed networks, Texas A & M University, College Station, TX, 1995
• 27: Nicholas Malcolm , Wei Zhao, Hard real-time communication in multiple-access networks, Real-Time Systems, v.8 n.1, p.35-77, Jan. 1995 [doi>10.1007/BF01893145]
• 28: MIL 3, Inc., 3400 International Drive, NW Washington D.C., 20008. OPNET Modeler, 1997.
• 29: J. L. Sobrinho and A. S. Krishnakumar. Real-time traffic over the IEEE 802.11 medium access control layer. Bell Labs Technical Journal, pages 172--187, 1996.
• 30: The SAS System. SAS Institute, Inc. Cary, NC.
• 31: F. S. Tobagi and L. Kleinrock. Packet switching in radio channels: Part II-the hidden terminal problem in carrier sense multiple-access and the busy-tone solution. IEEE Transactions on Communications, COM-23(12):1417--1433, December 1975.
• 32: F. S. Tobagi and L. Kleinrock. Packet switching in radio channels: Part IV-stability considerations and dynamic control in carrier sense multiple access. IEEE Transactions on Communications, COM-25(10):1103--1119, October 1977.
• 33: F. S. Tobagi and L. Kleinrock. The effect of acknowledgment traffic on the capacity of packet-switched radio channels. IEEE Transactions on Communications, COM-26(6):815--826, June 1978.
• 34: M. A. Visser and M. El Zarki. Voice and data transmission over an 802.11 wireless network. In 6th IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications, volume 2, pages 648--652. Institute of Electrical and Electronics Engineers, 1995.
• 35: Jost Weinmiller , Hagen Woesner , Adam Wolisz, Analyzing and Improving the IEEE 802.11-MAC Protocol for Wireless LANs, Proceedings of the 4th International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.200, February 01-04, 1996
• 36: W. Zhao , K. Ramamritham, Virtual time CSMA protocols for hard real-time communication, IEEE Transactions on Software Engineering, v.13 n.8, p.938-952, Aug. 1987 [doi>10.1109/TSE.1987.233512]