在IEEE 802.16j協議中，對於無線都會網路(Wireless Metropolitan Area Networks, WMANs)增定了中繼站Relay Station(RS)這個新的網路元件，除了能提昇傳輸的效能之外，也能增加基地台Base Station(BS)的覆蓋範圍。由於基地台(BS)的建置成本較高，在進行佈建工作時，往往須耗費較多的建置成本才能滿足使用者的傳輸速率要求，若能藉由中繼站(RS)來取代大量基地台(BS)的建置，不僅能降低網路的佈建成本，也能有效地提昇網路傳輸效能。而中繼站(RS)佈建位置的選擇，即是影響傳輸效能最重要關鍵。近年來，已有部分論文針對IEEE 802.16j Networks提出Relay Station的佈建方法，但大都未遵循現有IEEE 802.16j之Frame架構，亦未考慮BS及RS隨距離變化後之頻寬上限以及各個User或區域不同之頻寬要求，因此無法使RS之佈建達到較佳的網路效能。本論文針對IEEE 802.16j網路規劃之議題提出一Relay Station佈建的演算法，在給予一個BS及k個Relay Station的條件下，決定Relay Station(RS)佈建的位置，以滿足BS所能覆蓋的範圍內各個區域其不同的頻寬要求，並使網路的Capacity 得以提昇。本論文所提出的演算法同時考量了Base Station(BS)及Relay Station(RS)的頻寬限制，在有限的硬體成本下藉由Relay Station(RS)的佈建來提昇網路傳輸效能。實驗結果顯示，我們所提出的演算法，能有效地提升網路傳輸效能，並且找出最適合RS的佈建位置。

The IEEE 802.16j draft proposes a multi-hop relay network architecture that introduces the new network element of relay station aiming at increasing the network throughput or coverage. The deployment of the relay stations is one of the most important issues that determine the network throughput. In literature, some deployment strategies have been proposed. However, none of them follows the frame structure designed in IEEE 802.16j draft. Furthermore, they did not consider that the bandwidth constraint of BS, RS and MS will be changed with the deployed location of relay. Given a base station, k relay stations, and a region that can be full covered by the base station, this paper proposed a relay deployment mechanism that determines the deployed locations of RSs so that the bandwidth requirement of MSs can be satisfied while the network throughput can be significantly improved. Experimental study reveals that the proposed relay deployment mechanism can efficiently determine the locations for relay deployment and improve the network throughput.

Table of contents
Table of contents IV
List of figures V 
List of tables VI

I. Introduction 1
II. Preliminary and Related Works 4
III. System Model and Problem Formulation 9
IV. Relay Placement Mechanism with Maximal Network Capacity(RPM) 16
4.1 OVERVIEW OF RPM 16
4.2 RELAY PLACEMENT MECHANISM (RPM) 19
4.3 THE ALGORITHM OF RPM 25
V. Performance Study 30
VI. Conclusion 38
References 39
Appendix - Conference Version 40

List of Figures
Figure 1. The examples illustrating the basic usages of multi-hop relays in WiMAX networks. 4
Figure 2. Examples that depict the challenges of relay placement problems. 5
Figure 3. The frame structure defined in IEEE 802.16j draft. 9
Figure 4. An example of executing the partitioning phase for k=3. 16
Figure 5. The bright region of Ai constructed by identifying the BS and CPi boundaries.	17
Figure 6. The bright region that is obtained by the union of bright regions of n sub-regions Ai. 18
Figure 7. An example of the candidate-region which is surrounded by the red line. 18
Figure 8. The candidate-region is partitioned into several grids and a location will be selected from the grids for deploying the relay. 19
Figure 9. The comparison of the proposed RPM and the other two mechanisms in terms of network throughput. 31
Figure 10. The comparison of the proposed RPM and the other two mechanisms in terms of the network throughput by varying the traffic demands of sub-regions that are served by the deployed RS. 33
Figure 11. The comparison of network capacity by varying the numbers of RSs. 34
Figure 12. The comparison of average transmission delay of the networks with and without relay deployment. 35
Figure 13. The comparison of the proposed RPM and the other mechanism in terms of the network throughput by varying the number of sub-regions. 36
Figure 14. The comparison of the proposed RPM and the other mechanism in terms of average transmission delay by varying the number of sub-regions. 37

List of Tables 
Table 1 The received SNR and the Net Data Rate of each modulation coding schemes defined in the IEEE 802.16 standard. 30
Table 2 Simulation Parameters 31

[1] IEEE 802.16j-2007,“Draft IEEE Standard for Local and Metropolitan area networks – Part 16： Air Interface for Fix and Mobile Broadband Wireless Access Systems,Dec.2007.

[2] A. So, and B. Liang, “Optimal placement of relay infrastructure in heterogeneous wireless mesh networks by bender's decomposition,” in Proceeding of conference on Quality of service in heterogeneous wired/wireless networks, Aug. 2006.

[3] Y. Yu, S. Murphy and L. Murphy,“Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-hop Relay Networks,” in Proceeding of conference on Consumer Communications and Networking Conference, Jan. 2008.

[4] L. C. Wang, W. S. Su, J. H. Huang, A. Chen, and C. J. Chang,“Optimal Relay Location in Multi-Hop Cellular Systems,”in Proceeding of conference on Wireless Communications and Networking Conference, Mar. 2008.

[5] C. Hoymann,“Analysis and performance evaluation of the OFDM-based metropolitan area network IEEE 802.16,”in Proceeding of Computer Networks, Computer Networks, Oct. 2005.

[6] B. Lin, P. H. Ho, L. L. Xie, and X. Shen,“Relay Station Placement in IEEE 802.16j Dual-Relay MMR Networks,”in Proceeding of International Conference on Communications, May 2008.

[7] B. Lin, M. Mehrjoo, P. H. Ho, L. L. Xie, and X. Shen“Capacity Enhancement with Relay Station Placement in Wireless Cooperative Networks,”in Proceeding of conference on Wireless Communications and Networking Conference, Apr. 2009.