IEEE 802.16集中式排程之網狀網路中，基地台依據用戶端需傳送封包的需求建構路由樹。路由樹的建構對是影響網路效能的主要因素之一，因此許多路由樹建構方法提出的目的皆在改良現有的路由樹建構法。在本文首先評比了目前所提出的路由樹建構法的效能，其結果顯示尚無一種方法在不同的拓撲環境下皆較其他方法能得到較短的排程長度。隨後我們以摸擬方式分析這些方法在不同拓撲類型所建構的路由樹及排程長度，摸擬結果顯示Hemyari的第二種路由樹建構法在低節點密度下有最佳的排程結果；Hung的方法在高節點密度的大型拓撲下有最佳排程結果；Sheu的方法則在中節點密度，以及高節點密度的小型拓撲排程結果最佳。

In IEEE 802.16 centralized scheduling mesh network, Base Station (BS) constructs routing tree for Subscriber Stations (SS) which have packets to send. The routing tree construction algorithm is the key factor of mesh network performance, and many improved algorithms have been proposed. This paper first compares the performance of each of the routing tree construction algorithms. The results show that none of each algorithm is able to apply to every topology to have the shortest scheduling length among others. We then perform a simulation scheme to verify which algorithm is most suitable for what topology type. The simulation results show that Hemyari’s 2ndalgorithm is best suitable on low node density topologies, while Hung’s is best on large scale and high node density, and Sheu’s algorithm outperforms others on medium node density and high node density on small scale topologies.

中文摘要………………………………………………………………I
Abstract……………………………………………………………II
目次……………………………………………………………………III
圖目次…………………………………………………………………IV
表目錄…………………………………………………………………VI
1 緒論……………………………………………………………………1
1.1研究背景……………………………………………………………1
1.2研究動機與目的……………………………………………………3
1.3論文組織與架構……………………………………………………4
2相關研究…………………………………………………………………5
2.1 路由樹的建立………………………………………………5
2.2路由樹建構演算法……………………………………………9
2.2.1 IEEE 802.16 Routing Tree Algorithm…………11
2.2.2 Hemyari’s 1st Routing Tree Algorithm……13
2.2.3 Hemyari’s 2nd Routing Tree Algorithm……14
2.2.4 Sheu’s Routing Tree Algorithm…………………17
2.2.5 Hung’s Routing Tree Algorithm…………………19
3路由樹建構演算法優劣探討……………………………………………21
3.1路由樹建構法之特例情形……………………………………22
3.2路由樹建構法相對於不同拓撲排程結果之不穩定性………29
3.3路由樹建構法優劣探討………………………………………32
4摸擬與分析建議…………………………………………………………33
4.1 實驗設計……………………………………………………………33
4.2 模擬結果……………………………………………………………35
4.3 分析與建議…………………………………………………………50
5 結論……………………………………………………………………55
參考文獻…………………………………………………………………56

[1] IEEE Std. 802.16TM-2004, “IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” Oct. 1,2004.
[2] R. Prasad, OFDM for Wireless Communications Systems, Artech House, Boston, 2004.
[3] A. A. Hemyari,K. Ng Chee , K. N. Nor, A. Ismail and S. Khatun, “Constructing Routing Tree for Centralized Scheduling using Multi-Channel Single Transceiver System in 802.16 Mesh Mode” RF and Microwave Conference, 2-4 Dec. 2008, pp. 192-196.
[4] A. Ghiamatyoun, M. Nekoui,N. E. Said, M. Soltan, “Efficient Routing Tree Construction Algorithms for Multi-Channel WiMax Networks,” Computer Communications and Networks, 13-16 Aug. 2007, pp. 957-960.
[5] Y. Lu , G. Zhang ,"Maintaining Routing Tree in IEEE 802.16 Centralized Scheduling Mesh Networks ",Computer Communications and Networks, 13-16 Aug. 2007, pp. 240-245.
[6] A. A. Hemyari, N. K. Noordin, A. Ismail, S. Khatun, Y.H. Tahir, and Y. A. Qassem, “Centralized Scheduling, Routing Tree in WiMAX Mesh Networks,” Proceedings of the International Conference on Innovations in Information Technology (IIT 2008), December 2008, pp. 539-543.
[7] Pi-RongSheu, Chuan-Fu Hu, Chi-ChiuanLiou, Fang-Chen Chuang, and Yi-Cyun Chen, “An Efficient and Interference-Aware Centralized Routing Tree Algorithm for the Routing and Packet Scheduling Problem in IEEE 802.16 Mesh Networks ,”2010 International Conference on Communications and Mobile Computing, 2010, vol. 3, pp.496-503.
[8]洪敏捷, “Construction of Routing Tree for Centralized Scheduling in IEEE 802.16 Mesh Networks”, July, 2011.
[9] B. Han, W. Jia, and L. Lin, “Performance Evaluation of Scheduling in IEEE 802.16 Based Wireless Mesh Networks ,” Computer Communications, vol. 30, no. 4, February 2007, pp. 782-792.