Dual-mode real-time MAC protocol for wireless sensor networks: a validation/simulation approach

ABSTRACT

Several wireless sensor network applications are currently appearing in various domains. Their goal is often to monitor a geographical area. When a sensor detects a monitored event, it informs a sink node using alarm messages. The area surveillance application needs to react to such an event with a finite, bounded and known delay: these are real-time constraints. This work proposes a real-time MAC protocol with realistic assumptions for a random linear network, where sensors are deployed randomly along a line. We present a formal validation of this protocol both for initialization and run-time, and present simulation results on a realistic scenario.

REFERENCES

• 1: R. Lin, Z. Wang, and Y. Sun, "Wireless sensor networks solutions for real time monitoring of nuclear power plant," in World Congress on Intelligent Control and Automation, June 2004.
• 2: I. F. Akyildiz and I. Kasimoglu, "Wireless sensor and actor networks: research challenges," in International Conference on Mobile Ad Hoc and Sensor Systems (MASS). Fort Lauderdale, Florida, USA: IEEE, December 2004.
• 3: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 4: "Crossbow, inc., berkeley mote," last visited on16/01/2006. {Online}. Available: http://www.xbow.com/Products/Wireless_Sensor_Networks.htm
• 5: "Smart dust research project homepage," last visited on16/01/2006. {Online}. Available: http://robotics.eecs.berkeley.edu/~pister/SmartDust/
• 6: V. Rajavavivarme, Y. Yang, and T. Yang, "An overview of wireless sensor network and applications," in Southeastern Symposium on System Theory. Auburn, AL, USA: IEEE, March 2003.
• 7: John A. Stankovic, Research challenges for wireless sensor networks, ACM SIGBED Review, v.1 n.2, p.9-12, July 2004 [doi>10.1145/1121776.1121780]
• 8: T. Facchinetti and G. Buttazzo, "Integrated wireless communication protocol for ad-hoc mobile networks," in International Workshop on Real-Time Networks (RTN), Catania, Italy, June 2004, pp. 43--46.
• 9: P. Boone, "Real-time communication and coordination in wireless embedded sensor networks," April 2004, unpublished. {Online}. Available: http://www.scs.carleton.ca/~pboone/projects/sensor2004- 1.pdf
• 10: Tarek F. Abdelzaher , Shashi Prabh , Raghu Kiran, On Real-Time Capacity Limits of Multihop Wireless Sensor Networks, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.359-370, December 05-08, 2004 [doi>10.1109/REAL.2004.37]
• 11: J. A. Stankovic, T. F. Abdelzaher, C. Lu, L. Sha, and J. C. Hou, "Real-time communication and coordination in embedded sensor network," in Proceedings of the IEEE, vol. 91, no. 7, July 2003, pp. 1002--1022.
• 12: K. Akkaya and M. Younis, "Relocation of gateway for enhanced timeliness in wireless sensor networks," in Workshop on Energy-Efficient Wireless Communications and Networks (EWCN). IEEE, April 2004.
• 13: Andrew Tanenbaum, Computer Networks, Prentice Hall Professional Technical Reference, 2002
• 14: T. Abdelzaher , J. Stankovic , S. Son , B. Blum , T. He , A. Wood , Chenyang Lu, A Communication Architecture and Programming Abstractions for Real-Time Embedded Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.220, May 19-22, 2003
• 15: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 16: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 17: 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 (RTSS'04), p.382-391, December 05-08, 2004 [doi>10.1109/REAL.2004.46]
• 18: T. Facchinetti, G. Buttazo, M. Caccamo, and L. Almeida, "Wireless real-time communication protocol for cooperating mobile units," in Euromicro Conference on Real-Time Systems, Belek near Antalya, Turkey, July 2003.
• 19: Scheduling Communication in Real-Time Sensor Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), p.10, May 25-28, 2004
• 20: "Sebastian thrun's homepage," last visited on16/01/2006. {Online}. Available: http://robots.stanford.edu/
• 21: 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
• 22: M. Caccamo and L. Y. Zhang, "The capacity of implicit edf in wireless sensor networks," in Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 2003.
• 23: Thomas Watteyne , Isabelle Auge-Blum, Proposition of a Hard Real-Time MAC Protocol for Wireless Sensor Networks, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.533-532, September 27-29, 2005 [doi>10.1109/MASCOT.2005.55]
• 24: Georgios Orfanos , Jorg Habetha , Ling Liu, MC-CDMA Based IEEE 802.11 Wireless LAN, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), p.400-405, October 04-08, 2004
• 25: Amre El-Hoiydi, Spatial TDMA and CSMA with Preamble Sampling for Low Power Ad Hoc Wireless Sensor Networks, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.685, July 01-04, 2002
• 26: Simon R. Saunders , Saunders R Simon, Antennas and Propagation for Wireless Communication Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 27: Rajeev Alur , Costas Courcoubetis , David Dill, Model-checking in dense real-time, Information and Computation, v.104 n.1, p.2-34, May 1993 [doi>10.1006/inco.1993.1024]
• 28: K. Godary, I. Augé-Blum, and A. Mignotte, "Temporal bounds for tta: Validation," in Design Methods and Applications for Distributed Embedded Systems, IFIP 18th World Computer Congress, TC 10 Working Conference on Distributed and Parallel Embedded Systems (DIPES), Toulouse, France, August 2004, pp. 73--82.
• 29: K. Godary, I. Augé-Blum, and A. Mignotte, "Sdl and timed petri nets versus uppaal for the validation of embedded architecture in automotive," in Forum on Specification and Design Languages (FDL), Lille, France, September 2004.
• 30: "Uppaal home page," last visited on16/01/2006. {Online}. Available: http://www.uppaal.com/
• 31: J. Bergson and W. Yi, "Timed automata: Semantics, algorithms and tools," Lectures on Concurrency and Petri Nets, vol. 3098, pp. 87--124, 2004.
• 32: Rajeev Alur , D. L. Dill, Automata for modeling real-time systems, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.322-335, July 1990, Warwick University, England
• 33: T. Watteyne, I. Augé-Blum, and S. Ubéda, "Formal qos validation approach on a real-time mac protocol for wireless sensor networks," INRIA, Research Report RR-5782, December 2005. {Online}. Available: http://www.inria.fr/rrrt/rr-5782.html
• 34: "Opnet technologies, inc." last visited on 16/01/2006. {Online}. Available: http://www.opnet.com/

INDEX TERMS

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

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
          Subjects: Protocol verification
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Algorithms, Design