在IEEE 802.16j的標準中，增訂了Relay Station(RS)中繼網路元件於網路中，以提高網路效能。然而，其並未針對RS 佈建的位置及其個數進行討論。在一給定BS通訊範圍可及的廣大區域中，佈建RS將可提昇各行動主機的通訊速率，並滿足各鄉鎮區域的頻寬需求。然而，過多RS的佈建將額外增加硬體成本。本論文在一給定的BS服務區域中，針對各子區域的頻寬需求量，嘗試以最少的RS佈建在最適當的地方，使各子區域的頻寬需求。實驗結果顯示，我們所提出的演算法，能有效地提昇網路傳輸效能，並且找出最適合RS的佈建位置，進而降低RS佈建成本。

IEEE 802.16j standard defines Relay Station (RS) to enhance network throughput. However, the number and deployment location of RSs are not discussed. Deploying RSs within the serving area of BS could increase network throughput but raise the hardware cost problem. This paper presents a deployment scheme for IEEE 802.16j network. The proposed scheme deploys the minimal number of RSs at suitable locations according to the requirement of each subarea such that   all requirements can be satisfied. Experimental results show that our proposed algorithm can efficiently enhance network throughput and deploys the Relays at the most appropriate locations.

目錄
目錄	III
圖目錄	IV
表目錄	VI
第一章、 簡介	1
第二章、 相關研究	4
第三章、 網路環境與問題描述	7
第四章、 Low-Cost Relay Deployment Mechanism	12
4.1 Promising Zone Construction Phase	12
4.2 Promising Zone Mergence Phase	20
4.3 Maximal Number of RS Estimation Phase	25
4.4 RS Allocation Phase	29
4.5 RS Sharing Phase	31
4.6 RS Removing Phase	35
4.7 The Algorithm	38
第五章、 模擬實驗	40
5.1  Simulation Model	40
5.2  Simulation result	43
第六章、 結論	47
第七章、 參考文獻	48
附錄-英文論文	49

圖目錄
圖(一) : IEEE 802.16j Transparent Mode的Frame架構圖。	2
圖(二) : 在此網路環境中，將BS覆蓋範圍內每個子區域之中心點CP來代表此區。	7
圖(三) : 鄉鎮子區域的Promising Zone。	16
圖(四) : 此圖為下一個合適的RS有效佈建區域。	17
圖(五) : 執行Promising Zone Construction Phase後的結果。	18
圖(六) : Algorithm of Promising Zone Construction Phase	19
圖(七) : 此圖為兩個CP的例子。	20
圖(八) : 此圖為四個CP的例子。	21
圖(九) (a)  : 未合併前的交集情況 。	22
圖(九) (b)  : 合併後的交集情況。	22
圖(十) : Algorithm of Promising Zone Mergence Phase	24
圖(十一)(a) : 此圖為三個CP的例子。	26
圖(十一) (b) : 佈建一個RS於 。	26
圖(十一) (c) : 佈建一個RS於 。	26
圖(十二) : Algorithm of Maximal Number of RS Estimation Phase	28
圖(十三) : RS佈建於減少時間較大的佈建區域。	29
圖(十四) : Algorithm of RS Allocation Phase	30
圖(十五)(a) : 兩個佈建區域皆佈建RS。	32
圖(十五) (b): 合併為一個RS。	32
圖(十六) (a) : 三個佈建區域都有佈建RS的例子。	33
圖(十六) (b) : 將RS佈建於其中一個交集區中。	33
圖(十七) : Algorithm of RS Sharing Phase	34
圖(十八) : 此場景為執行完Phase 3~6的佈建結果。	36
圖(十九) : Algorithm of RS Removing Phase	37
圖(二十) : Algorithm of Low-Cost Relay Deployment Mechanism	39
圖(二十一) : RS佈建結果圖。	41
圖(二十二) : RS佈建結果的τ值評估。	42
圖(二十三) : Number of RSs的評估。	44
圖(二十四) : Transmission delay time的評估。	45
圖(二十五) : 計算時間複雜度的評估。	46

表目錄
表(一)  :  調變與編碼表格	4
表(二)  :  符號定義	9
表(三)  :  調變與編碼表格	13
表(四)  :  實驗參數	40

[1]IEEE 802.16j-2007 (2007), Draft IEEE Standard for Local and Metropolitan area networks – Part 16： Air Interface for Fix and Mobile Broadband Wireless Access Systems, December 2007.
[2]A. So, and B. Liang (2005), “Optimal Placement of Relay infrastructure in Heterogeneous Wireless Mesh Networks by Bender's Decomposition,” In QShine’06, Aug 2006. 
[3]Y. Yu, S. Murphy and L. Murphy (2008), “Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-hop Relay Networks,” In CCNC, Jan 2008
[4]L. C. Wang, W. S. Su, J. H. Huang, A. Chen, and C. J. Chang(2008),“Optimal Relay Location in Multi-Hop Cellular Systems,” In WCNC 2008, April 2008.
[5]H. C. Lu, Wanjiun Liao, “Joint Base Station and Relay Station Placement for IEEE 802.16j Networks,” In GLOBECOMM 2009, November 2009.
[6]IEEE 802.16-2004, IEEE Standard for Local and Metropolitan area networks – Part 16： Air Interface for Fix and Mobile Broadband Wireless Access Systems, Table-215, October 2004.