A Mobility-aware Tree Construction Algorithm For Zigbee Networks
Date Issued
2009
Date
2009
Author(s)
Chen, Kuan-Chang
Abstract
Zigbee, based on the IEEE 802.15.4 standard, is a specification for wireless personal area network with the properties of low‐power, low‐cost, low‐data rate. Zigbee supports 3 kinds of network topologies, i.e., star, tree and mesh, and the tree topology is widely adopted for wireless sensor applications. When a device in the tree network moves away from its previous position, the data delivery to the device might fail, and the data broadcasting which cause extremely large resource consumption would be activated. We present a method to deal with the mobility issue and efficiently send data to mobile devices in a Zigbee tree network. The problem is formulated as a graph, and a suitable tree topology is constructed to increase the data delivery ratio for mobile devices. We show NP‐hardness of this problem and prove that the approximation with any ratio 0≦ρ≦1 does not exist unless NP = P. A heuristic algorithm for this problem is developed and experimental results demonstrate the performance of the heuristic algorithm compared to the optimal solution.
Subjects
wireless network
tree topology
mobility
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922099-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):af6b061406e11d59548ee610979938ad