IEEE 802.16j標準分別定義了穿透式中繼與非穿透式中繼傳輸模式來達到增加網路吞吐量與延伸網路傳輸範圍。本論文針對非穿透式中繼傳輸模式多節點跳躍網路的資源排程問題進行公式化，並且證明此資源排程問題為NP-Complete。有鑑於劃分訊框範圍的邊界在IEEE 802.16j標準中並無規定如何決定，又此訊框範圍的界定對系統吞吐量有相當大的影響，我們在提出的演算法中一併提出如何界定的方法。為了使演算法能夠實作在即時性的WiMAX中繼網路，我們提出一個低時間複雜度的啟發式演算法名為多節點跳躍中繼資源排程(Multi-hop Relay Resource Scheduling，MRRS)演算法。MRRS能夠根據不同的使用者分佈與通道狀態資訊回報來決定子訊框的範圍界定以提升資源排程最小單位槽(slot)的使用率，並且在網路吞吐量與使用者公平性上取得平衡。經由模擬的結果，我們發現MRRS在系統吞吐量的效能評比上優於其他研究所提出來的演算法，並且在跳躍節點增加的情況下，和其他研究相比受到很小的影響。若是使用中繼節點的使用者占大多數，MRRS的公平性評比和其他研究相比幾乎沒有差距，在其它的網路情況下也能夠維持不錯的使用者公平性。

IEEE 802.16j standard defines transparent relay and non-transparent relay transmission mode to increase system capacity and coverage extension respectively. In this paper, we focus on non-transparent relay network scenario, and formulating the relay resource scheduling problem. We also prove the resource scheduling problem to be NP-Complete. The zone boundary placement has greatly effect to system throughputs, we propose the determination method in our algorithm. To ensure the algorithm can easily implements on WiMAX network, we propose a low time complexity heuristic algorithm MRRS (Multi-hop Relay Resource Scheduling). According to different user distribution and variety channel state information, MRRS can adaptively adjust zone boundary placement to improve the available slots utilization, and we strike a balance between network throughput and fairness index. From the simulation results, we find out that the performance evaluation of MRRS is better than other algorithms we studied. In the situation of hop increased, the throughput performance of MRRS suffers vary little effect compared with other algorithms. From the fairness point of view, MRRS and other algorithms behave about the same performance when R-MSs are majority. In other network scenario, MRRS maintains good fairness index performance.

[1] Hsiao-Chen Lu, Wanjiun Liao, and Frank Yeong-Sung Lin, “Relay Station Placement Strategy in IEEE 802.16j WiMAX Networks”, IEEE Transactions on Communications, Vol. 59, No. 1, pp. 151-158, Jan. 2011.
[2] Dong Jun Son, and Ju Wook Jang, “A Path Selection Scheme Considering Traffic Load for IEEE 802.16j Mobile Multi-hop Relay Networks”, 2010 6th International Conference on Wireless Communications Networking and Mobile Computing, pp. 1-5, Sep. 2010.
[3] Hongtao Zhang, Xiaoxiang Wang, and Yihua Huang, “A Novel Path Selection Mechanism for IEEE 802.16j Network”, 2010 IEEE 71st Vehicular Technology Conference, pp. 1-5, May. 2010.
[4] Supratim Deb, Vivek Mhatre, and Venkatesh Ramaiyan, “WiMAX Relay Networks: Opportunistic Scheduling to Exploit Multiuser Diversity and Frequency Selectivity”, Proceedings of the 14th ACM international conference on Mobile Computing and networking, pp. 163-174, 2008.
[5] Megumi Kaneko, Petar Popovski, and Kazunori Hayashi, “Throughput-Guaranteed Resource-Allocation Algorithms for Relay-Aided Cellular OFDMA System”, IEEE Transactions on Vehicular Technology, Vol. 58, No. 4, pp. 1951-1964, May. 2009.
[6] Yongchul Kim, and Mihail L. Sichitiu, “Fairness Schemes in 802.16j Mobile Multihop
Relay Networks”, IEEE Global Telecommunications Conference, pp. 1-5, Dec. 2010.
[7] Alessandro Biagioni, Romano Fantacci, Dania Marabissi, and Daniele Tarchi, “Adaptive Subcarrier Allocation Schemes for Wireless OFDMA Systems in WiMAX Networks”, IEEE Journal on Selected Areas in Communications, Vol. 27, No.2, pp. 217-225, Feb. 2009.
[8] Kyungjoo Lee, Hyukjoon Lee, Yong-Hoon Choi, Younguk Chung, and Young-il Kim, “A Joint Bandwidth Allocation and Routing Scheme for the IEEE 802.16j Multi-hop Relay Networks”, International Conference on Information Networking , pp. 1-5, Jan. 2009.
[9] Dusit Niyato, and Ekram Hossain, “A Radio Resource Management Framework for IEEE
802.16-Based OFDM/TDD Wireless Mesh Networks”, IEEE International Conference on Communications, pp. 3911-3916, Jun. 2006.
[10] Steven W. Peters, and Robert W. Heath, Jr.,” The future of WiMAX: Multihop relaying with IEEE 802.16j”, IEEE Communications Magazine, Vol. 47, No. 1, pp.104-111, Jan. 2009.
[11] 林輝堂, 林英佑, 孫仲銳, "針對IEEE 802.16j穿透式中繼網路中有效資源排程", The Sixth Workshop on Wireless Ad Hoc and Sensor Networks, 台灣大學, 台北市, 台灣, 2010年9月.
[12] Youhei OHNO, Tatsuya SHIMIZU, Takefumi HIRAGURI, and Masashi NAKATSUGAWA, “Novel Frame Structures to Improve System Capacity and Latency Performance of a Time-Division Duplex Multihop Relay Wireless Access System”, IEEE Wireless Communications and Networking Conference, pp. 1-6, 2009.
[13] IEEE 802.16-2004 standard, “Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” Oct. 2004.
[14] IEEE 802.16e-2005 standard, “Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed Broadband Wireless Access Systems: Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands,” Feb. 2006.
[15] IEEE 802.16j-2009 standard, “Local and Metropolitan Area Networks, Part16: Air Interface for Broadband Wireless Access Systems: Amendment for Multiple Relay Specification,” Jul. 2009.
[16] Vasken Genc, Sean Murphy, Yang Yu, and John Murphy, “IEEE 802.16J RELAY-BASED WIRELESS ACCESS NETWORKS: AN OVERVIEW”, IEEE Wireless Communications, Vol. 15, No. 5, pp. 56-63, Oct. 2008.
[17] Zhifeng Tao, Anfei Li, Koon Hoo Teo, and Jinyun Zhang, “Frame Structure Design for IEEE 802.16j Mobile Multihop Relay (MMR) Networks”, IEEE Global Telecommunications Conference, pp. 4301-4306, Nov. 2007.
[18] Hoon Baek , and Ju Wook Jang “Dynamic frame scheduling with load balancing for IEEE 802.16j”, International Conference on Wireless Communications and Signal Processing , pp. 1-5, 2009.
[19] Srinath Narasimha, and Krishna Moorthy Sivalingam, "Improved opportunistic scheduling algorithms for WiMAX Mobile Multihop Relay networks", International Conference on High Performance Computing, pp. 20-29, 2009.
[20] Ashutosh Deepak Gore, and Abhay Karandikar, "Link Scheduling Algorithms for Wireless Mesh Networks", in IEEE Communications Surveys & Tutorials, Vol. 13, No. 2, pp. 258-273, May. 2011.
[21] Karthikeyan Sundaresan, and Sampath Rangarajan, “Efficient Algorithms for Leveraging Spatial Reuse in OFDMA Relay Networks”, IEEE INFOCOM, pp. 1539-1547, Apr. 2009.
[22] Subramanian Ramanathan and Errol L. Lloyd, “Scheduling algorithms for multihop radio networks,” IEEE/ACM Transactions on Networking, Vol. 1, No. 2, pp. 166-177, Apr. 1993.
[23] Gurashish Brar, Douglas M. Blough, and Paolo Santi, “Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks,” ACM MobiCom in Proc., pp. 2-13, Sep. 2006.
[24] Ashutosh Deepak Gore, “On wireless link scheduling and flow control,” Ph.D. dissertation, Indian Institute of Technology, Mumbai, India, Dec. 2008,[Online]. Available: http://arxiv.org/abs/0812.4744.
[25] David Pisinger, “A Minimal Algorithm for the Bounded Knapsack Problem”, Informs Journal on Computing, Vol. 12, No. 1, pp. 75-82, 2000.
[26] Rajendra K. Jain, Dah-Ming W. Chiu, and William R. Hawe, “A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems”, DEC Research Report TR-301, September 1984.
[27] Karthikeyan Sundaresan, and Sampath Rangarajan, “On Coexistence of Unicast and Multicast Traffic in Relay-enabled Wireless Networks”, 5th International Conference on Broadband Communications Networks and Systems, pp. 479-486, Sep. 2008.