The orphan problem in zigbee-based wireless sensor networks

ABSTRACT

ZigBee is a standard which is considered to be suitable for wireless sensor networks. In ZigBee, a device is said to join a network if it can obtain a network address from a parent device. Devices calculate addresses for their child devices by a distributed address assignment scheme. This assignment is easy to implement, but it restricts the number of children of a device and the depth of the network. We observe that if one uses the random formation policy specified in ZigBee, the utilization of the address pool will be very low. Those devices that can not receive network addresses will be isolated from the network and become orphan nodes. In this paper, we model the orphan problem by two subproblems: the bounded-degree-and-depth tree formation (BDDTF) problem and the end-device maximum matching (EDMM) problem. We then present solutions to these problems. The results can be applied to network formation in ZigBee networks.

REFERENCES

• 1: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 3: 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.
• 4: ZigBee-2006 specification, ZigBee document 064112, 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: Distributed networks

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

General Terms:
Algorithms, Design, Theory

Keywords:
graph theory, ieee 802.15.4, orphan problem, wireless sensor network, zigbee