針對移動節點的Zigbee拓樸生成演算法

A Mobility-aware Tree Construction Algorithm For Zigbee Networks

陳冠昌(Kuan-Chang Chen)

指導教授 ： 逄愛君

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.01862

摘要

Zigbee是架構於IEEE 802.15.4標準之上的無線個人通訊網路，而其特色為低耗功、低成本、低資料傳輸量。Zigbee支援三種網路拓樸：星狀、網狀和樹狀拓樸，其中樹狀拓樸被廣泛運用於無限感測網路。當一個網路中的裝置從原先的位置移開時，可能導致其他裝置無法成功遞送資料給它，而必須消耗大量網路資源來做廣播。本論文提出一套有效率的傳輸方法，來解決移動節點的議題。藉由將原本的問題轉化成為一個圖形問題，我們即能夠建構出一個能夠提高成功遞送率的樹狀拓樸。對於這個問題我們也證明了其難度為NP-Hard。同時我們也證明了對於此問題，除非NP = P，否則無介於 0 – 1倍最佳解的多項式時間近似演算法存在。因此本論文提出了一個啟發式演算法，並且評估此演算法與最佳解的效能比較。

關鍵字

Zigbee ； 無線網路 ； 樹狀拓樸 ； 行動網路

並列摘要

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.

並列關鍵字

Zigbee ； wireless network ； tree topology ； mobility

參考文獻

[3] I.F. Akyildiz, Jiang Xie, and S. Mohanty. A survey of mobility management in next-generation all-ip-based wireless systems. Wireless Communications,IEEE, 11(4):16{28, Aug. 2004.

[4] Beongku An and Symeon Papavassiliou. A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks. International Journal of Network Management, 11(6), 2001.

[5] B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 230{240, New York, NY, USA, 1987. ACM.

[8] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cli®ord Stein. Introduction to algorithms, second edition, 2001.

[9] Yanfei Fan, Jingqiu Zhang, and Xuemin Shen. Mobility-aware multi-path forwarding scheme for wireless mesh networks. In Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE, pages 2337{2342, 31 2008-