在IEEE 802.16協議中，對於無線都會網路(WireleSS Metropolitian Area Networks, WMANs)制定了網狀模式的架構，可增加網路的覆蓋區以及提昇傳輸的效能。由於整體網路的架構較PMP架構複雜，基地台(BS)如何依使用者之頻寬要求，透過Mesh Network的拓樸結構予以排班將是影響傳輸效能及頻寬利用率的重要關鍵。近年來，雖有許多論文針對IEEE 802.16 Mesh Network以Greedy或Heuristic技術提出排班演算法，但其效能仍無法達到最佳化。本論文提出一運作於Base Station(BS)的排班最佳演算法，根據各個SuBScriber Station(SS)所提出的上傳頻寬要求，同時考量傳輸的平行性與Link的傳輸速率，發展一個網路傳輸效能最佳化的排班演算法，以達到增加空間再利用(Spatial Reuse)及增加在網狀(mesh)網路上傳流量傳輸等目的。實驗結果顯示，相較於現有的排班演算機制，我們所提出的排班演算法對於頻寬分配，能夠達到整個網路具有單位時間最大傳輸流量及傳輸總時間最佳化之效益。

WiMAX Mesh Network architecture is defined in IEEE 802.16 for increasing the network coverage and improving the communication performance. In the past few years, many greedy or heuristic approaches have been proposed to cope with the scheduling problem in WiMAX mesh networks. However, their performances highly depend on the network topology and the bandwidth requests and none of them achieves optimal for all cases. This paper proposes an optimal scheduling algorithm that exploits the opportunities of spatial reuse and maximize the network throughput based on the network topology and the uplink transmission requests of each Subscriber Station(SS). Simulation study reveals that the proposed optimal scheduling algorithm provides the WiMAX mesh network with maximal throughput and shortest transmission time.

Table of Contents
Table of Contents	I
List of Figures	II
List of Tables	IV
I. Introduction	1
II. Related Work	6
III. Optimal Scheduling Algorithm	12
3.1. Network Environment and Problem Definition	12
3.2. Basic Concepts and Scheduling Rules	14
3.3. Optimal Scheduling Algorithm	18
IV. Performance Study	26
V. Conclusion	32
References	33
附錄-英文論文	35
List of Figures
Figure 1: An example of IEEE 802.16 Mesh Network.	6
Figure 2: The optimal scheduling of the example shown in Fig.1(a).	7
Figure 3: The transmission scheduling by applying the scheduling algorithm proposed in [5].	8
Figure 4: The scheduling by applying algorithm proposed in [6].	9
Figure 5: The schedule by applying algorithm proposed in [8].	11
Figure 6: A valid scheduling which considers the flow from v5 to BS in Fig.1(a).	16
Figure 7: The scheduling considers interfered relation for the example given in Fig.1(a).	17
Figure 8: A Parallel scheduling for the example given in Fig.1(a).	18
Figure 9: A tree topology example.	19
Figure 10: The proposed optimal algorithm.	25
Figure 11: The performance comparison of average transmission delay.	27
Figure 12: The performance comparison of average throughput.	27
Figure 13: The relation between link utilization and the number of SS in the network.	30
Figure 14: The comparison of four algorithms in terms of peak throughput.	30
Figure 15: The impact of tree height on transmission delay.	31 
List of Tables 
Table 1:  The comparison of related works.	11
Table 2:  The parameter of burst profile.	26

[1]	802.16d-2004, “Draft IEEE Standard for Local and Metropolitan area networks – Part 16: Air Interface for Fixed Broadband Wireless Access Systems”, May 2004.
[2]	H-Y. Wei, S. Ganguly, R. Izmailov, and Z.J. Haas, “Interference-Aware IEEE 802.16 WiMax Mesh Networks”, in 61st IEEE Vehicular Technology Conference (VTC), 2005, pp. 3102- 3106. 
[3]	L. W. Chen, Y. C. Tseng, D. W. Wang, and J. J. Wu, “Exploiting Spectral Reuse in Resource Allocation, Scheduling ,and Routing for IEEE 802.16 Mesh Networks”, in 66st IEEE Vehicular Technology Conference (VTC), 2007, pp. 1608-1612.
[4]	Y. Cao, Z. Liu, Y. Yang, “Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Network”, in IEEE International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), 2006, pp. 1-4. 
[5]	H. Shetiya and V Sharma, ” Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Network”, in IEEE Wireless Communications and Networking Conference(WCNC), 2006, pp. 174-152. 
[6]	S. M. Cheng, P. Lin, D. W. Huang, S. R. Yang, “A study on distributed-centralized scheduling for wireless mesh network”, in Proceedings of international conference on Wireless communications and mobile computing (IWCMC), 2006, pp. 599-604. 
[7]	Bo Han, Fung Po Tso, Lidong Lin and Weijia Jia, “Performance Evaluation of Scheduling in IEEE 802.16 Based Wireless Mesh Networks”, in IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), 2006, pp. 789-794. 
[8]	D. Ghosh, A. Gupta, P. Mohapatra, “Admission Control and Interference-Aware Scheduling in Multi-hop WiMAX Networks”, in IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), 2007, pp. 1-9. 
[9]	S. Ramanathan, E.L. Lloyd, “Scheduling algorithms for multihop radio networks”, IEEE/ACM Transactions on Networking, vol. 1, pp. 166 -177 ,1993.