A Mobility-aware Tree Construction Algorithm For Zigbee Networks

Zigbee是架構於IEEE 802.15.4標準之上的無線個人通訊網路，而其特色為低耗功、低成本、低資料傳輸量。Zigbee支援三種網路拓樸：星狀、網狀和樹狀拓樸，其中樹狀拓樸被廣泛運用於無限感測網路。當一個網路中的裝置從原先的位置移開時，可能導致其他裝置無法成功遞送資料給它，而必須消耗大量網路資源來做廣播。本論文提出一套有效率的傳輸方法，來解決移動節點的議題。藉由將原本的問題轉化成為一個圖形問題，我們即能夠建構出一個能夠提高成功遞送率的樹狀拓樸。對於這個問題我們也證明了其難度為NP-Hard。同時我們也證明了對於此問題，除非NP = P，否則無介於 0 – 1倍最佳解的多項式時間近似演算法存在。因此本論文提出了一個啟發式演算法，並且評估此演算法與最佳解的效能比較。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.Chinese Abstract p.viibstract p.ixcknowledgement p.xiontents p.xiiiist of Figures p.xv Introduction p.1 System Model and Problem Definition page p.5.1 System Model p.5.2 Problem Formulation p.7 Algorithm and Hardness p.11.1 Problem Hardness p.11.2 Algorithm Description p.15.2.1 ZTG p.17.2.2 FIX p.18 Simulations and Analysis p.23.1 Simulation Setup p.23.2 Simulation Results p.25.2.1 Small scale environment with comparison to optimum p.25.2.2 Large scale environment p.26 Conclusion p.29ibliography p.3