Quick convergecast in ZigBee/IEEE 802.15.4 tree-based wireless sensor networks

ABSTRACT

Convergecast is a fundamental operation in wireless sensor networks. Existing convergecast solutions have focused on reducing latency and energy consumption. However, a good design should be compliant to standards, in addition to considering these factors. Based on this observation, this paper defines a minimum delay beacon scheduling problem for quick convergecast in ZigBee/IEEE 802.15.4 tree-based wireless sensor networks and proves that this problem is NP-complete. Our formulation is also compliant with the low-power design of IEEE 802.15.4. We then propose optimal solutions for special cases and heuristic algorithms for general cases. Simulation results show that the proposed algorithms can indeed achieve quick convergecast.

REFERENCES

• 1: Design and construction of a wildfire instrumentation system using networked sensors. http://firebug.sourceforge.net/.
• 2: Dust network Inc. http://dust-inc.com/flash-index.shtml.
• 3: Habitat monitoring on great duck island. http://www.greatduckisland.net/technology.php.
• 4: Motes, smart dust sensors, wireless sensor networks. http://www.xbow.com/Products/productsdetails.aspx?sid=3.
• 5: Zigbee alliance. http://www.zigbee.org/.
• 6: Barbara Hohlt , Lance Doherty , Eric Brewer, Flexible power scheduling for sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984653]
• 7: IEEE standard for information technology - telecommunications and information exchange between systems - local and metropolitan area networks specific requirements part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs), 2003.
• 8: Qun Li , Michael De Rosa , Daniela Rus, Distributed algorithms for guiding navigation across a sensor network, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939017]
• 9: Chih-Yu Lin , Yu-Chee Tseng, Structures for In-Network Moving Object Tracking in Wireless Sensor Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.718-727, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.78]
• 10: G. Lu, B. Krishnamachari, and C. S. Raghavendra. An adaptive energy-efficient and low-latency mac for data gathering in wireless sensor networks. In Proceedings of Int'l Parallel and Distributed Processing Symp., 2004.
• 11: Y.-C. Tseng, S.-P. Kuo, H.-W. Lee, and C.-F. Huang. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies. In Proc. of Int'l Symp. on Information Processing in Sensor Networks (IPSN), 2003.
• 12: Yu-Chee Tseng , Meng-Shiuan Pan , Yuen-Yung Tsai, Wireless Sensor Networks for Emergency Navigation, Computer, v.39 n.7, p.55-62, July 2006 [doi>10.1109/MC.2006.248]
• 13: S. Upadhyayula, V. Annamalai, and S. K. S. Gupta. A low-latency and energy-efficient algorithm for convergecast in wireless sensor networks. In Proc. of IEEE Global Telecommunications Conference (Globecom), 2003.
• 14: D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
• 15: M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y. Liu, and S. Singh. Exploiting heterogeneity in sensor networks. In Proc. of IEEE INFOCOM, 2005.
• 16: Y. Yu, B. Krishnamachari, and V. K. Prasanna. Energy-latency tradeoffs for data gathering in wireless sensor networks. In Proc. of IEEE INFOCOM, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Theory

Keywords:
IEEE 802.15.4, ZigBee, convergecast, graph theory, scheduling, wireless sensor network