MCRT: Multichannel Real-Time Communications in Wireless Sensor Networks

Abstract

As many radio chips used in today’s sensor mote hardware can work at different frequencies, several multichannel communication protocols have recently been proposed to improve network throughput and reduce packet loss for wireless sensor networks. However, existing work cannot utilize multiple channels to provide explicit guarantees for application-specified end-to-end communication delays, which are critical to many real-time applications such as surveillance and disaster response. In this article, we propose MCRT, a multichannel real-time communication protocol that features a flow-based channel allocation strategy. Because of the small number of orthogonal channels available in current mote hardware, MCRT allocates channels to network partitions formed based on many-to-one data flows. To achieve bounded end-to-end communication delay for every data flow, the channel allocation problem has been formulated as a constrained optimization problem and proven to be NP-complete. We then present the design of MCRT, which includes a channel allocation algorithm and a real-time packet forwarding strategy. Extensive simulation results based on a realistic radio model and empirical results on a real hardware testbed of Tmote nodes both demonstrate that MCRT can effectively utilize multiple channels to reduce the number of deadlines missed in end-to-end communications. Our results also show that MCRT outperforms a state-of-the-art real-time protocol and two baseline multichannel communication schemes.

References

1. Ahn, G.-S., Campbell, A., Veres, A., and Sun, L.-H. 2002. Swan: Service differentiation in stateless wireless ad hoc networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 2. 457--466.
2. Caccamo, M., Zhang, L., Sha, L., and Buttazzo, G. 2002. An implicit prioritized access protocol for wireless sensor networks. In Proceedings of the 23rd IEEE International Real-Time Systems Symposium. 39--48.
3. Chang, J.-H. and Tassiulas, L. 2000. Energy conserving routing in wireless ad-hoc networks. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 1. 22--31.
4. Cheng, C., Kumar, S. P. R., and Garcia-Luna-Aceves, J. J. 1990. A distributed algorithm for finding k disjoint paths of minimum total length. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing.
5. Chipara, O., He, Z., Xing, G., Chen, Q., Wang, X., Lu, C., Stankovic, J., and Abdelzaher, T. 2006a. Real-time power-aware routing in sensor networks. In Proceedings of the 14th IEEE International Workshop on Quality of Service. 83--92.
6. Chipara, O., Lu, C., and Stankovic, J. 2006b. Dynamic conflict-free query scheduling for wireless sensor networks. In Proceedings of the 14th IEEE International Conference on Network Protocols. 321--331.
7. Doshi, S., Bhandare, S., and Brown, T. X. 2002. An on-demand minimum energy routing protocol for a wireless ad hoc network. SIGMOBILE Mob. Comput. Comm. Rev. 6, 3.
8. Felemban, E., Lee, C.-G., and Ekici, E. 2006. MMSPEED: Multipath multi-speed protocol for QoS guarantee of reliability and. timeliness in wireless sensor networks. IEEE Trans. Mob. Comp. 5, 6, 738--754.
9. Garey, M. R. and Johnson, D. S. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY.
10. Gupta, P. and Kumar, P. R. 2000. The capacity of wireless networks. IEEE Trans. Inform. Theor. 46, 2.
11. He, T., Stankovic, J., Lu, C., and Abdelzaher, T. 2003. Speed: A stateless protocol for real-time communication in sensor networks. In Proceedings of the 23rd International Conference on Distributed Computing Systems. 46--55.
12. Jeong, J., Culler, D. E., and Oh, J.-H. 2005. Empirical analysis of transmission power control algorithms for wireless sensor networks. Tech. rep. UCB/EECS-2005-16. EECS Department, University of California, Berkeley.
13. Jurcik, P., Severino, R., Koubaa, A., Alves, M., and Tovar, E. 2010. Real-time communications over cluster-tree sensor networks with mobile sink behaviour. In Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.
14. Karenos, K. and Kalogeraki, V. 2006. Real-time traffic management in sensor networks. In Proceedings of the 27th IEEE International Real-Time Systems Symposium. 422--434.
15. Kim, Y., Shin, H., and Cha, H. 2008. Y-MAC: An energy-efficient multi-channel mac protocol for dense wireless sensor networks. In Proceedings of the 7th International Conference on Information Processing in Sensor Networks.
16. Kyasanur, P. and Vaidya, N. H. 2005. Capacity of multi-channel wireless networks: Impact of number of channels and interfaces. In Proceedings of the 11th Annual International Conference on Mobile Computing and Networking. ACM, New York, NY, 43--57.
17. Le, H. K., Henriksson, D., and Abdelzaher, T. 2007. A control theory approach to throughput optimization in multi-channel collection sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks.
18. Le, H. K., Henriksson, D., and Abdelzaher, T. 2008. A practical multi-channel media access control protocol for wireless sensor networks. In Proceedings of the 7th International Conference on Information Processing in Sensor Networks.
19. Li, Q., Aslam, J., and Rus, D. 2001. Online power-aware routing in wireless ad-hoc networks. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. ACM, New York, NY, 97--107.
20. Li, L., Halpern, J. Y., Bahl, P., Wang, Y.-M., and Wattenhofer, R. 2001. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, NY, 264--273.
21. Li, N., Hou, J., and Sha, L. 2003. Design and analysis of an MST-based topology control algorithm. In Procceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 3. 1702--1712.
22. Lin, S., Zhang, J., Zhou, G., Gu, L., Stankovic, J. A., and He, T. 2006. ATPC: Adaptive transmission power control for wireless sensor networks. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems. ACM, New York, NY, 223--236.
23. Lu, C., Blum, B., Abdelzaher, T., Stankovic, J., and He, T. 2002. Rap: A real-time communication architecture for large-scale wireless sensor networks. In Procceedings of the 18th IEEE Real-Time and Embedded Technology and Applications Symposium. 55--66.
24. Polastre, J., Hill, J., and Culler, D. 2004. Versatile low power media access for wireless sensor networks. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. ACM, New York, NY, 95--107.
25. Ramanathan, R. and Rosales-Hain, R. 2000. Topology control of multihop wireless networks using transmit power adjustment. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 2. 404--413.
26. Ronen, D. and Perl, Y. 1984. Heuristics for finding a maximum number of disjoint bounded paths. Networks 14, 531--544.
27. Sankar, A. and Liu, Z. 2004. Maximum lifetime routing in wireless ad-hoc networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 2. 1089--1097.
28. Santi, P. 2003. Topology control in wireless ad hoc and sensor networks. Tech. rep. IIT-TR-04. Istituto di Informatica e Telematica, Pisa, Italy.
29. Selavo, L., Wood, A. D., Cao, Q., Sookoor, T., Liu, H., Srinivasan, A., Wu, Y., Kang, W., Stankovic, J. A., Young, D., and Porter, J. 2007. Luster: Wireless sensor network for environmental research. In Proceedings of the ACM SIGOPS International Conference on Embedded Networked Sensor Systems.
30. Sidhu, D., Nair, R., and Abdallah, S. 1991. Finding disjoint paths in networks. SIGCOMM Comput. Comm. Rev. 21, 4, 43--51.
31. Singh, S., Woo, M., and Raghavendra, C. S. 1998. Power-aware routing in mobile ad hoc networks. In Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking. ACM, New York, NY, 181--190.
32. Son, D., Krishnamachari, B., and Heidemann, J. 2004. Experimental study of the effects of transmission power control and blacklisting in wireless sensor networks. In Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. 289--298.
33. Stankovic, J., Abdelzaher, T., Lu, C., Sha, L., and Hou, J. 2003. Real-time communication and coordination in embedded sensor networks. Proc. IEEE 91, 7, 1002--1022.
34. Vedantham, R., Kakumanu, S., Lakshmanan, S., and Sivakumar, R. 2006. Component based channel assignment in single radio, multi-channel ad hoc networks. In Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. ACM, New York, NY, 378--389.
35. Wang, X., Wang, X., Fu, X., Xing, G., and Jha, N. 2009. Flow-based real-time communication in multi-channel wireless sensor networks. In Proceedings of the 6th European Conference on Wireless Sensor Networks.
36. Wang, X., Wang, X., Xing, G., and Yao, Y. 2010a. Dynamic duty cycle control for end-to-end delay guarantees in wireless sensor networks. In Proceedings of the 18th IEEE International Workshop on Quality of Service.
37. Wang, X., Wang, X., Xing, G., and Yao, Y. 2010b. Exploiting overlapping channels for minimum power configuration in real-time sensor networks. In Proceedings of the 7th European Conference on Wireless Sensor Networks.
38. Woo, A., Tong, T., and Culler, D. 2003. Taming the underlying challenges of reliable multihop routing in sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM, New York, NY, 14--27.
39. Wu, Y., Stankovic, J., He, T., and Lin, S. 2008. Realistic and efficient multi-channel communications in wireless sensor networks. In Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies. 1193--1201.
40. Zhang, J., Zhou, G., Huang, C., Son, S., and Stankovic, J. 2007. TMMAC: An energy efficient multi-channel mac protocol for ad hoc networks. In Proceedings of the IEEE International Conference on Communications. 3554--3561.
41. Zhao, J. and Govindan, R. 2003. Understanding packet delivery performance in dense wireless sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM, New York, NY, 1--13.
42. Zhou, G., Huang, C., Yan, T., He, T., Stankovic, J. A., and Abdelzaher, T. F. 2006. MMSN: Multi-frequency media access control for wireless sensor networks. In Proceedings of the 25th Annual Joint Conference of the IEEE Computer and Communications Societies.
43. Zuniga, M. and Krishnamachari, B. 2004. Analyzing the transitional region in low power wireless links. In Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Networks

  • Network protocols

  • Network types

    • Mobile networks

    • Wireless access networks