Risk-aware beacon scheduling for tree-based ZigBee/IEEE 802.15.4 wireless networks

ABSTRACT

In a tree-based ZigBee network, ZigBee routers (ZRs) must schedule their beacon transmission times to avoid beacon collisions. The beacon schedule determines packet delivery latency from the end devices to the ZigBee coordinator at the root of the tree. Traditionally, beacon schedules are chosen such that a ZR does not reuse the beacon slots already claimed by its neighbors, or the neighbors of its neighbors. We observe however that beacon slots can be reused judiciously, especially when the risk of beacon collision caused by such reuse is low. The advantage of such reuse is that packet delivery latency can be reduced. We formalize our observation by proposing a node pair classification scheme, that classifies pairs of nodes that are at most two hops apart. Based on this scheme, we can easily assess the risk of slot reuse by a node pair. If the risk is high, slot reuse is disallowed; otherwise, slot reuse is allowed. This forms the essence of our ZigBee-compliant, distributed, risk-aware, probabilistic beacon scheduling algorithm. Simulation results confirm that our algorithm produces a lower latency compared to if a more conventional slot reuse rule is used.

REFERENCES

• 1: P. Hall. Introduction to the Theory of Coverage Processes. John Wiley and Sons, 1988.
• 2: IEEE. 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), Oct. 2003.
• 3: A. Koubâa, M. Alves, M. Attia, and A. Nieuwenhuyse. Collision-free beacon scheduling mechanisms for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks. In 7th Int'l Workshop on Applications and Services in Wireless Networks, Santander, Spain, May 2007.
• 4: Yu-Chee Tseng , Meng-Shiuan Pan, Quick convergecast in ZigBee/IEEE 802.15.4 tree-based wireless sensor networks, Proceedings of the 4th ACM international workshop on Mobility management and wireless access, October 02-02, 2006, Terromolinos, Spain [doi>10.1145/1164783.1164794]
• 5: L.-H. Yen and Y.-M. Cheng. Clustering coefficient of wireless ad hoc networks and the quantity of hidden terminals. IEEE Commun. Lett., 9(3):234--236, Mar. 2005.
• 6: ZigBee Standards Organization. ZigBee Specification, Dec. 2006.

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Reliability

Keywords:
ZigBee/IEEE 802.15.4 beacon scheduling