Robust implicit EDF: A wireless MAC protocol for collaborative real-time systems

ABSTRACT

Advances in wireless technology have brought us closer to extensive deployment of distributed real-time embedded systems connected through a wireless channel. The medium-access control (MAC) layer protocol is critical in providing a real-time guarantee. We have devised a real-time wireless MAC protocol, robust implicit earliest deadline first, or RI-EDF. Packets are transmitted according to EDF scheduling rules, offering a protocol that implicitly avoids contention. In the event of a packet loss or a node failure, every node has the opportunity to recover the schedule based on a static recovery priority, offering a protocol that is robust with no central point of failure. We demonstrate in simulations that RI-EDF provides better goodput and lower packet loss than existing protocols like 802.11 PCF and EDCF. In our implementation and distributed control test-bed, we show that RI-EDF provides better throughput than the TinyOS MAC-layer protocol. Overall, RI-EDF provides predictable temporal behavior with minimal impact on node failures, packet losses, and noise in the channel.

REFERENCES

• 1: T. P. Baker, Stack-based scheduling for realtime processes, Real-Time Systems, v.3 n.1, p.67-99, March 1991 [doi>10.1007/BF00365393]
• 2: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 3: Benveniste, M., Chesson, G., Hoeben, M., Singla, A., Teunissen, H., and Wentink, M. 2001. EDCF Proposed Draft Text. IEEE Working Document 802.11-01/131r1.
• 4: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 5: Giorgio C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 6: Marco Caccamo , Lynn Y. Zhang , Lui Sha , Giorgio Buttazzo, An Implicit Prioritized Access Protocol for Wireless Sensor Networks, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.39, December 03-05, 2002
• 7: Tanya L. Crenshaw , Ajay Tirumala , Spencer Hoke , Marco Caccamo, A Robust Implicit Access Protocol for Real-Time Wireless Collaboration, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.177-186, July 06-08, 2005 [doi>10.1109/ECRTS.2005.3]
• 8: Raymond Cunningham , Vinny Cahill, Time bounded medium access control for ad hoc networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584492]
• 9: Tullio Facchinetti , Luis Almeida , Giorgio C. Buttazzo , Carlo Marchini, Real-Time Resource Reservation Protocol for Wireless Mobile Ad Hoc Networks, Proceedings of the 25th IEEE International Real-Time Systems Symposium, p.382-391, December 05-08, 2004 [doi>10.1109/REAL.2004.46]
• 10: Hoke, S. 2004. Wireless distributed control based on RI-EDF MAC protocol. http://pertsserver.cs. uiuc.edu/~mcaccamo/IPC/.
• 11: Lee, D., Puri, A., Varaiya, P., Sengupta, R., Attias, R., and Tripakis, S. 2002. A wireless token ring protocol for ad-hoc networks. In Proceedings of the IEEE Aerospace Conference. Vol. 3. Big Sky, Montana.
• 12: Anders Lindgre , Olov Schelén , Andreas Almquist, Evaluation of Quality of Service Schemes for IEEE 802.11 Wireless LANs, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.348, November 14-16, 2001
• 13: Anders Lindgren , Andreas Almquist , Olov Schelén, Quality of service schemes for IEEE 802.11 wireless LANs: an evaluation, Mobile Networks and Applications, v.8 n.3, p.223-235, June 2003 [doi>10.1023/A:1023389530496]
• 14: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 15: Liu, J. W. S. 2000. Real-Time Systems. Prentice Hall, Inc., Upper Saddle River, New Jersey.
• 16: Monks, J. P., Bharghavan, V., and Hwu, W. 2001. A power controlled multiple access protocol for wireless packet networks. In Proceedings of 20th IEEE Conference on Computer Communications (INFOCOM 2001). Anchorage, Alaska.
• 17: Navneet Malpani , Jennifer L. Welch , Nitin Vaidya, Leader election algorithms for mobile ad hoc networks, Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.96-103, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345871]
• 18: Sobrinho, J. and Krishnakumar, A. 1999. Quality-of-service in ad hoc carrier sense multiple access networks. IEEE Journal on Selected Areas in Communications 17, 8 (August), 1353--1368.
• 19: Tomasz Jurdziński , Mirosław Kutyłowski , Jan Zatopiański, Efficient algorithms for leader election in radio networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571833]
• 20: Tobagi, F. A. and Kleinrock, L. 1975. 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 23, 12 (Dec.), 1417--1433.
• 21: Xue Yang , Nitin H. Vaidya, Priority scheduling in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513809]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.2 Network Protocols
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Keywords:
Earliest deadline first, medium-access control, real time, wireless