無線寬頻網路中，單憑佈建基地台(Base Station, BS)以滿足使用者的傳輸要求，將耗費大量的建置成本。因此，若能以佈建成本較低的中繼站(Relay Station, RS)取代上述之基地台佈建作業，除了可大幅降低網路整體的佈建成本外，亦能提昇網路整體的傳輸吞吐量。近年來，雖有眾多WiMAX 802.16j中繼站佈建之相關研究，然而，這些研究僅單純考慮傳輸效能的高低，卻忽略必須遵循IEEE 802.16j訊框架構之規範，以致中繼站佈建後的使用者需求無法確實滿足。本論文主要針對 WiMAX 802.16j 網路，提出一多躍中繼站佈建演算法，不但考慮中繼站佈建位置影響網路傳輸效益的程度，更遵循IEEE 802.16j訊框架構之傳輸規範，評估單一訊框中可安排傳輸的中繼站與使用者數量，以期使用最少數量的中繼站，確實滿足使用者的資料傳輸需求。透過實驗模擬，本論文所提出的多躍中繼站佈建演算法與現有的研究相比，在中繼站佈建數量、使用者需求滿意度、傳輸延遲及網路吞吐量各方面，皆有較優越的效能展現。

In wireless broadband networks, only deployment a base station (BS) in order to satisfy all users’ transmission requirements, will spend a lot of build costs.
To reduce the cost of deploying BSs, the relay station (RS) interconnected between the BS and MSs (or SSs) is proposed in the new version of IEEE 802.16j standard.
In recent years, there has many relay station deployment related studies in IEEE 802.16j, however, these studies simply consider the efficiency of transmission ,not consider the frame structure of IEEE 802.16j, lead to users requirement can not really satisfied after relay station was deployment. 
This paper aims WiMAX 802.16j networks, propose a multi-hop relay station placement algorithm, not only consider the location of relay but also follow IEEE 802.16j frame structure of transmission specification, evaluate the number of relay stations and users can transmission in a frame, using the minimum number of relay stations, in order to satisfying all users’ data requirement.
Our performance study compared with existing research, proposed a multi-hop relay station placement algorithm, the number of relay stations , satisfaction of users, transmission delay and throughput has relatively superior performance.

目錄
圖目錄		IV
表目錄		VI
第一章、Introduction	1
第二章、Related Works	5
第三章、Network Environment and Problem Formulation	8
第四章、Cost-Effective Multi-hop Relay Placement (CEMRP) Mechanism	15
4.1 Promising Zone Construction (PZC) Phase	16
4.2 Promising Zone Reduction (PZR) Phase	25
4.3 Minimal Number of RS Allocation (MRA)Phase	27
第五章、Performance Study	31
第六章、Conclusions	40
References	41
附錄—英文論文	44

圖目錄
圖一、基地台(BS)的服務區域分割成子區域A={A1, A2,…,An}，每個子區域Ai 的資訊中心點由CPi表示。	10
圖二、BS,RS,MS 經由兩步傳輸及三步傳輸，依照彼此間距離對應表2所採用的傳輸速率。	17
圖三、BS 的服務區依照MCSs不同的距離所劃分出的同心圓。	19
圖四、BS 與 CPi 之間的 promising zone。	20
圖五、Promising Zone Construction Phase 第二個步驟所建立出的第二個交集區。	21
圖六、服務CP3的 promising zone Zi1。	21
圖七、CP3的兩個 promising zone Z31 與Z32。	23
圖八、建立出所有CPS 的promising zone之例子。	23
圖九、Algorithm of Promising Zone Construction Phase。	24
圖十、RS中繼站佈建於Z21與Z31的交集區O2,3內，可降低佈建RS中繼站之硬體成本。	26
圖十一、合併Z21、Z31為Z1M能有效減少promising zone之數量。	26
圖十二、經Promising Zone Reduction Phase 後的802.16j寬頻網路。	27
圖十三、CP1直接由BS服務與RS服務所需傳輸時間之差別。	28
圖十四、CP1、CP5、CP9、CP10的relay benefit分別為80、65、35、40， Tover的值為215個時槽。	30
圖十五、假設之網路環境。	32
圖十六、PZR階段模擬之結果。	33
圖十七、CEMRP演算法之執行結果，實際上佈建4個RS來服務CPs。	34
圖十八、網路中RS的數量與平均資料需求量之關係。	35
圖十九、所提出之CEMRP與其他四種方法的平均傳輸延遲隨著RS數量變動。	36
圖二十、所提出之CEMRP與其他四種方法的Qos需求滿意指數與RS數量之關係。	37
圖二十一、CEMRP與OPT方法在PZC階段計算時間之比較。	38
圖二十二、每個階段所需的RS數量之比較。	39

表目錄
表一、符號定義	11
表二、調變與編碼表格	16
表三、實驗參數	31

[1]H.Wang,W.Jia and G.Min,“Effective Channel Exploitation in IEEE 802.16j Networks for Maritime Communications,”IEEE International Conference on Distributed Computing Systems (IEEE ICDCS),Jun.2011.
[2]H.C.Lu and W.Liao,“On Cooperative Strategies in Wireless Relay Networks,”IEEE International Conference on Computer Communications (IEEE INFOCOM),Apr.2011.
[3]C.Y.Hong and A.C.Pang,“3-Approximation algorithm for joint routing and link scheduling in wireless relay networks,”IEEE Transactions on Wireless Communications (IEEE TWC),vol.8,no.2,Feb.2009.
[4]IEEE 802.16 Working Group,Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems–multihop Relay Specification,IEEE Standard,2009.
[5]K.Sundaresan and S.Rangarajan,“Efficient Algorithms for Leveraging Spatial Reuse in OFDMA Relay Networks,”IEEE International Conference on Computer Communications(IEEE INFOCOM),Apr.2009.
[6]Y.Kim and M.L.Sichitiu,“Optimal Max–Min Fair Resource Allocation in Multihop Relay-Enhanced WiMAX Networks,” IEEE Transactions on Vehicular Technology (IEEE TVT),vol.60,no.8,Oct.2011.
[7]Liu,Q.,Zhou,S.,& Giannakis,G.B.,“Queuing withadaptive modulation and coding over wireless links: Cross-layer analysis and design,”IEEE Transactions on Wireless Communications,4(3),1142–1153.May 2005.
[8]A. So,and B.Liang,“Optimal placement of relay infrastructure in heterogeneous wireless mesh networks by bender's decomposition,”International conference on Quality of service in heterogeneous wired/wireless networks (QShine),Aug.2006.
[9]Y.Yu, S.Murphy and L.Murphy,“Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-hop Relay Networks,”IEEE Consumer Communications and Networking Conference(IEEE CCNC),Jan.2008.
[10]J.H.Huang,L.C.Wang,C.J.Chang and W.S.Su,“Design of Optimal Relay Location in Two-hop Cellular Systems,” Wireless Networks,vol.16,no.8,Nov.2010.
[11]Y.Yu,S.Murphy and L.Murphy,“A Clustering Approach to Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-hop Relay Networks,”IEEE Internet Conference on Communications(IEEE ICC),Jan.2008.
[12]D. Yang, X. Fang, G. Xue, J. Tang,“Relay Station Placement for Cooperative Communications in WiMAX Networks,”IEEE Global Telecommunications Conference(IEEE GLOBECOM),Dec.2010.
[13]Lu,H.C.,Liao,W.,“Joint Base Station and Relay Station Placement for IEEE 802.16j Networks,”IEEE GlobalCommunications Conference(IEEE GLOBECOM),Nov.2009.
[14]H. C. Lu, W. Liao, F. Y. S. Lin,“Relay Station Placement Strategy in IEEE 802.16j WiMAX Networks,”IEEE Transactions on Communications,vol.59,no.1,Jan.2011,pp. 151-158.
[15]C.Y.Chang,C.T.Chang,M.H.Li,and C.H.Chang,“A Novel Relay Placement Mechanism for Capacity Enhancement in IEEE 802.16j WiMAX Networks,”IEEE International Conference on Communication(IEEE ICC),Jun.2009.
[16]J.M.Chang,C.F.Lai,H.C.Chao,and J.L.Chen,“Optimized Path Selection Mechanism for IEEE 802.16j Multi-Hop Relay Networks,”IEEE International Conference on Communication (IEEE ICC),Jun.2012