
系統識別號 
U00021208201314555000 
中文論文名稱

WiMAX寬頻無線網路中具提升網路效能之中繼站佈建與排程技術

英文論文名稱

Relay Deployment and Scheduling Approaches for Improving Network Throughputs in WiMAX Broadband Networks

校院名稱 
淡江大學 
系所名稱(中) 
資訊工程學系博士班 
系所名稱(英) 
Department of Computer Science and Information Engineering 
學年度 
101 
學期 
2 
出版年 
102 
研究生中文姓名 
李明憲 
研究生英文姓名 
MingHsien Li 
學號 
897410139 
學位類別 
博士 
語文別 
英文 
口試日期 
20130624 
論文頁數 
122頁 
口試委員 
指導教授張志勇 委員張志勇 委員石貴平 委員游國忠 委員陳裕賢 委員張兆村 委員洪麗玲 委員蘇民揚

中文關鍵字 
全球互通微波存取
佈建
排程
中繼站
寬頻無線網路

英文關鍵字 
WiMAX
Deployment
Scheduling
Relay
Broadband Wireless Network

學科別分類 
學科別＞應用科學＞資訊工程

中文摘要 
WiMAX(全球互通微波存取)是一種新興的無線寬頻通訊技術，可提供高速率與遠距離的傳輸，這項技術的標準規格為 IEEE 802.16。目前IEEE 802.16標準已發展了許多規格，包含了802.16d、802.16e和802.16j等。其中，802.16d的標準中提出了WiMAX 網狀網路架構，用以提升網路的傳輸可靠性與網路效能。而802.16e則改良了PMP的傳輸，以支援移動用戶的傳輸。由於基地台(BS)的建置成本較高，在進行佈建工作時，往往須耗費較多的建置成本才能滿足使用者的傳輸速率要求，因此在IEEE 802.16j的標準中，增訂了Relay Station (RS)中繼網路元件及運作規範，以提高網路效能以及降低網路建置成本。近年來，已有部分論文針對IEEE 802.16j Networks提出Relay Station的佈建方法，但大都未遵循現有IEEE 802.16j之Frame架構。此外，有些論文假設候選佈建地點為隨機決定，這些隨機選擇的地點將可能無法使RS之佈建符合實際的需求並達到較佳的網路效能。此外，過多RS的佈建將會額外增加硬體成本，因此該如何佈建最少數量的中繼站，並使得所有使用者的頻寬需求都能被滿足將是一個重要的問題。有鑑於此，本論文針對IEEE 802.16j Networks，提出兩種不同的中繼站佈建技術，分別為Placement Mechanism (RPM)和CostAware Relay Deployment Mechanism (CARD)，這兩種技術使得中繼站可以被佈建在最適當的位置，以最大化網路效能。首先，本論文所提出的RPM佈建技術，在給予一個BS及k個Relay的條件下，決定Relay Station (RS)佈建的位置，使網路的Capacity 得以提昇。而CARD佈建技術則嘗試提出低成本且滿足頻寬需求的解決方案，以最少的RS佈建在最適當的地方，使各子區域的頻寬需求得以滿足。
在另一方面，針對多躍網路而言，其架構較PMP架構複雜，因此基地台(BS)如何依使用者之頻寬要求，透過樹狀拓樸結構予以排班將是影響傳輸效能及頻寬利用率的重要關鍵。近年來，雖有許多論文針對IEEE 802.16 Mesh Network以Greedy或Heuristic技術提出排班演算法，但其效能仍無法達到最佳化。為了能夠進一步的提升網路效能，本論文亦提出兩個傳輸排程演算法以提升網路傳輸的平行性，分別為Scheduling Algorithm with Dynamic Programming Approach (SADP) and Heuristic Scheduling Algorithm (HSA)。本論文所提出的SADP，根據各個SuBScriber Station (SS)所提出的上傳頻寬要求，同時考量傳輸的平行性與Link的傳輸速率，以達到增加空間再利用(Spatial Reuse)及增加網路上傳流量傳輸的目的。最後，為了降低SADP演算法的計算成本，本論文所提出的HSA演算法將能夠在降低計算成本的情況下，提供接近SADP的傳輸效能。實驗結果顯示，我們所提出的演算法，能有效地提升網路傳輸效能，並且找出最適合RS的佈建位置。而我們所提出的排班演算法對於頻寬分配，能夠達到整個網路具有單位時間最大傳輸流量及傳輸總時間最佳化之效益。

英文摘要 
WiMAX, as supported by standard IEEEE 802.16, is an emerging broadband wireless access technology which can provide good features including high transmission rate and large transmission range. The family of IEEE 802.16 standard contains 802.16d, 802.16e, 802.16j, etc. The IEEE 802.16d defines the mesh architecture for improving the responsibility and network throughput while IEEE 802.16e further supports Mobile stations. Since the deployment for base station (BS) to fully cover the whole region might lead to high deployment cost, IEEE 802.16j standard defines Relay Station (RS) to reduce the deployment cost and increase network throughput. In literature, some deployment strategies have been proposed. However, none of them follows the frame structure designed in IEEE 802.16j standard. Furthermore, some existing studies assume having some predefined candidate locations which are randomly determined. However, those candidate locations might not be the best deployment locations, leading to the degradation of network throughput. In addition, the excess of RSs might result in the increase of hardware cost. It is a critical problem to deploy as few as possible RSs at proper locations such that the traffic requirement of each subarea can be satisfied while the hardware cost can be minimized. To cope with the deployment issue, this thesis proposes two RS deployment mechanisms, including Relay Placement Mechanism (RPM) and CostAware Relay Deployment Mechanism (CARD). The RPM is developed for deploying k RSs at the most suitable locations for maximizing the network throughput while the CARD aims to deploy as few as possible RSs such that the traffic requirement of each subarea can be satisfied. Simulation results show that our proposed algorithms can deploy the RSs at the most appropriate locations and thus efficiently reduce transmission delay and save the hardware cost.
In addition to the WiMAX 802.16j broadband network, this thesis futher consider the WiMAX mesh networks and proposes an optimal transmssion scheduling algorithm and a heuristic algorithm for BS to schedule the transmission of MSs. As compared with the PMP network, the transmission scheduling for a mesh network is much more complicated. Developing a scheduling algorithm for WiMAX mesh networks faces a big challenge. In the past few years, several greedy or heuristic algorithms have been proposed to cope with the scheduling issue in WiMAX mesh networks. However, their performances highly depend on the network topology and bandwidth requests and thus they do not achieve optimal performance in all cases. To further improve the network throughput, this thesis proposes two scheduling algorithms for exploiting the opportunities of spatial reuse in WiMAX mesh networks, including Scheduling Algorithm with Dynamic Programming Approach (SADP) and Heuristic Scheduling Algorithm (HSA). Based on the network topology and the uplink bandwidth requests of each Subscriber Station (SS), the proposed SADP algorithm aims to maximize the network throughput by applying the dynamic programming approach. Although the SADP can obtain the optimal results, it might need high computational cost. To cope with the problem, the HSA is proposed for further reducing the computing complexity while its results are approximate to the optimal results. It is notable that the proposed scheduling algorithms can be easily applied to the IEEE 802.16j networks by treating RSs as SSs with no traffic requirement. Consequently, the work for developing scheduling approach for mesh network also enrich the studies of deployment approaches as developed for IEEE 802.16j broadband networks. Simulation results show that the proposed SADP algorithm provides maximal throughput and shortest transmission time while the proposed HSA likely obtains optimal results.

論文目次 
Contents
List of Figures VII
List of Tables XI
Chapter 1 Introduction 1
Chapter 2 Related Work 6
2.1 Relay Deployment Approaches 6
2.2 Scheduling Algorithms 7
Chapter 3 The Relay Placement Mechanism (RPM) 13
3.1 Network Environment and Problem Statement 13
3.2 The RPM Scheme 20
3.2.1 Overview of RPM 20
3.2.2 The Proposed RPM 23
3.2.2.1 Partitioning Phase 23
3.2.2.2 BrightRegion Identification Phase 24
3.2.2.3 CandidateRegion Identification Phase 35
3.2.2.4 CandidateLocation Identification Phase 36
3.2.3 The Algorithm of RPM 36
3.3 Performance study 41
3.4 Summary 49
Chapter 4 The CostAware Relay Deployment (CARD) Mechanism 50
4.1 Network Environment and Problem Statement 50
4.2 The CostAware Relay Deployment (CARD) Mechanism 55
4.2.1 Promising Zone Construction (PZC) Phase 55
4.2.2 Promising Zone Reduction (PZR) Phase 61
4.2.3 Minimal Number of RSs Allocation Phase 65
4.2.4 The algorithm of CARD 70
4.3 Performance Study 72
4.4 Summary 82
Chapter 5 The Scheduling Algorithm with Dynamic Programming (SADP) Approach 83
5.1 Network Environment and Problem Statement 83
5.2 Basic Concepts and Scheduling Rules 86
5.3 The Scheduling Algorithm with Dynamic Programming (SADP) Approach 89
5.4 Heuristic Scheduling Algorithm (HSA) 98
5.5 Performance Study 104
5.6 Summary 116
Chapter 6 Conclusions 117
References 120
List of Figures
Figure 1.1: Frame structure of IEEE 802.16j transparent mode and the transmission from BS to SS through RS. 2
Figure 1.2: The data rate between the BS and MS is highly depending on distance. 2
Figure 2.1: A typical example of scheduling problem in IEEE 802.16 Mesh Network. 8
Figure 2.2: The optimal scheduling of the example shown in Figure 2.1(a). 9
Figure 2.3: The transmission schedule by applying the scheduling algorithm proposed in [18]. 9
Figure 2.4: The scheduling by applying algorithm proposed in [19]. 10
Figure 2.5: The schedule by applying algorithm proposed in [22]. 11
Figure 3.1: The frame structure defined in IEEE 802.16j standard. 18
Figure 3.2: An example of executing the partitioning phase for k=3. (a) The initial partitions. (b) The adjusted partitions. 21
Figure 3.3: The bright region of Pi is a promising region for RS deployment. 22
Figure 3.4: The bright region that is obtained by the union of bright regions of n subregions Ai. 22
Figure 3.5: An example of the candidateregion which is marked by the red ink. 22
Figure 3.6: The candidateregion is partitioned into several grids and a location will be selected from the grids for deploying the RS. 22
Figure 3.7: An example of data transmission from Pi to the BS. 27
Figure 3.8: The calculation of transmission latency of the example given in Fig. 7. 27
Figure 3.9: An example of data transmissions from Pi to RSj and then the data is forwarded from RSj to BS. 28
Figure 3.10: The link capacity of l(RSj, BS) is the bottleneck of the path from Pi to the BS through RSj. 30
Figure 3.11: The serving area of BS is partitioned into M concentric circles. 34
Figure 3.12: An example of the intersection area I4,6 of ABS and Ap. 34
Figure 3.13: An example of considered environment which contains 25 representative points. 42
Figure 3.14: The comparison of network throughput by varying the numbers of RSs. 43
Figure 3.15: The comparisons of each phase designed in the proposed RPM and the other mechanisms in terms of throughput by varying the number of MSs. 45
Figure 3.16: The comparison of each phase of the proposed RPM and the other mechanisms in terms of average transmission delay by varying the number of MSs. 46
Figure 3.17: The comparison of the proposed RPM and the other two schemes in terms of QoS Satisfactory Index λ versus the number of given RSs. 47
Figure 3.18: The comparison of the proposed RPM and the other mechanisms in terms of the relay traffic by varying the number of RSs. 48
Figure 3.19: The impact of grid size on the network throughput and transmission delay of the proposed RPM. 49
Figure 4.1: The serving area of BS is partitioned into a set of subareas A={A1, A2, ..., An} and the central point of subarea Ai is denoted by Pi. 50
Figure 4.2: The CARD can verify whether or not a given location is suitable for deploying RSj. 56
Figure 4.3: The serving area of the BS partitions into M coronas. 58
Figure 4.4: The promising zone of Pi. 58
Figure 4.5: The step 2 of Promising Zone Construction Phase constructs second intersection area. 59
Figure 4.6: An example of Promising Zone Construction for P1. 59
Figure 4.7: An example of the promising zones which are successfully constructed for some Ps. 60
Figure 4.8: Algorithm of Promising Zone Construction Phase. 61
Figure 4.9: The RS deployed in the overlapped region O{1,2} of Z1 and Z2 can reduce the hardware cost of relay deployment. 62
Figure 4.10: An example of the execution of promising zone reduction phase. 64
Figure 4.11: Algorithm of Promising Zone Reduction Phase. 65
Figure 4.12: An example of 802.16j networks by applying Promising Zones Reduction Phase. 66
Figure 4.13: The required transmission time of three case of RS deployment. 67
Figure 4.14: An example of six Promising Zones and their corresponding reduced time. 69
Figure 4.15: The proposed CARD deploys four RSs by applying Minimal Number of RSs Allocation Phase. 69
Figure 4.16: Algorithm of Minimal Number of RSs Allocation Phase. 70
Figure 4.17: CostAware Relay Deployment mechanism (CARD). 71
Figure 4.18: Screenshot of network environment. 73
Figure 4.19: The results by applying the operations of PZR phase of the proposed CARD algorithm. 74
Figure 4.20: The final decision by applying the proposed CARD algorithm. There are four relays actually deployed in the serving region of the BS for supporting the required traffics of 10 Ps. 75
Figure 4.21: The relation between the average traffic requirement and the number of RSs in the networks. 76
Figure 4.22: The comparison of the proposed CARD and the other four schemes in terms of average transmission delay by varying the number of deployed RS. 77
Figure 4.23: The comparison of the proposed CARD and the other four schemes in terms of QoS Satisfactory Index λ versus the number of RSs. 79
Figure 4.24: The comparison of Promising Zone construction phase and OPT in terms of calculation time. 80
Figure 4.25: The investigation of the impact of each phase on the number of relays. 81
Figure 5.1: A valid scheduling which considers the flow from v5 to BS in Figure 2.1(a). 88
Figure 5.2: A Parallel scheduling for the example given in Figure 2.1(a). 88
Figure 5.3: The scheduling cases consider nonparallel relation for the example given in Figure 2.1(a). 89
Figure 5.4: A tree topology example. 91
Figure 5.5: An example of the merged schedule {{v110}8{v550}3}8. 96
Figure 5.6: An example of the merged schedule {{v110}8{{v550}3→{v450}3}6}8. 96
Figure 5.7: The two null slots can be allocated to the subschedule {{v350}3 because node v3 has parallel relation with v1. 97
Figure 5.8: An example of optimal schedule U({v1, v5}) which can be obtained by merging U({v1}) and U({v5}). 97
Figure 5.9: The proposed Scheduling Algorithm with Dynamic Programming Approach (SADP). 98
Figure 5.10: A schedule by applying HSA on the tree given in Figure 2.1. 101
Figure 5.11: The pseudo code of the proposed HSA. 102
Figure 5.12: The two distributions applied in the considered environment. 106
Figure 5.13: The comparison of the network throughput of the five compared algorithms with uniform distribution of SSs. 107
Figure 5.14: The comparison of the proposed SADP and HAS algorithms, and the other three existing algorithms in terms of the network throughput under congregating distribution. 108
Figure 5.15: The comparison of five compared algorithms in terms of the peak traffic by applying uniform distribution to place SSs. 109
Figure 5.16: The comparison of five compared algorithms in terms of the peak traffic by applying congregating distribution as deployment policy. 109
Figure 5.17: The comparison of the proposed SADP and HSA and the other three schemes in terms of the normalized throughput by varying 1hop traffic ratio under uniform distribution. 110
Figure 5.18: The normalized throughput versus 1hop traffic ratio by applying the congregating distribution as deployment policy. 111
Figure 5.19: The comparison of five algorithms in terms of the average throughput achieved on each level and the average buffering time by applying uniform distribution as the deployment policy. 114
Figure 5.20: The packet dropping ratio by varying MTT delay. 114
Figure 5.21: The comparison of four algorithms in terms of the network throughput. The transmission rate of each link is varied because the signal is corrupted by adding Gaussian noise for 10 minutes at the 30, 60 and 90 minutes. 115
List of Tables
Table 1.1: Modulation and coding schemes 3
Table 3.1: Notation list 16
Table 3.2: Simulation parameters 41
Table 4.1: Notation List 51
Table 4.2: Simulation parameters 72
Table 5.1: The comparison of related studies 103
Table 5.2: The parameters of burst profile 104 
參考文獻 
[1] S. M. Oh and J. H. Kim, “ApplicationAware Design to Enhance System Efficiency for VoIP Services in BWA Networks,” IEEE Transactions on Multimedia, vol. 13, no. 1, pp. 143154, Feb. 2011.
[2] N. AbuAli, M. Hayajneh and H. Hassanein, “CongestionBased Pricing Resource Management in Broadband Wireless Networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 8, pp. 26002610, Aug. 2010.
[3] A. K. A. Tamimi, C. S.In and R. Jain, “Modeling and Resource Allocation for Mobile Video over WiMAX Broadband Wireless Networks,” IEEE Journal on Selected Areas in Communications, vol. 28, no. 3, pp. 354365, Apr. 2010.
[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] 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 (ICDCS), June 2011.
[6] H. C. Lu and W. Liao, “On Cooperative Strategies in Wireless Relay Networks,” IEEE International Conference on Computer Communications (INFOCOM), Apr. 2011.
[7] C. Y. Hong and A. C. Pang, “3Approximation algorithm for joint routing and link scheduling in wireless relay networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 2, pp. 856861, Feb. 2009.
[8] K. Sundaresan and S. Rangarajan, “Efficient Algorithms for Leveraging Spatial Reuse in OFDMA Relay Networks,” IEEE International Conference on Computer Communications (INFOCOM), Apr. 2009.
[9] Y. Kim and M. L. Sichitiu, “Optimal Max–Min Fair Resource Allocation in Multihop RelayEnhanced WiMAX Networks,” IEEE Transactions on Vehicular Technology, vol. 60, no. 8, pp. 39073918, Oct. 2011.
[10] Q. Liu, S. Zhou and G. B. Giannakis, “Queuing With Adaptive Modulation and Coding Over Wireless Links: CrossLayer Analysis and Design,” IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 11421153, May 2005.
[11] Y. Yu, S. Murphy and L. Murphy, “Planning Base Station and Relay Station Locations in IEEE 802.16j Multihop Relay Networks,” IEEE Consumer Communications and Networking Conference (CCNC), Jan. 2008.
[12] L. C. Wang, W. S. Su, J. H. Huang, A. Chen, and C. J. Chang,“Optimal Relay Location in MultiHop Cellular Systems,” IEEE Wireless Communications and Networking Conference (WCNC), Apr. 2008.
[13] IEEE 802.16 Working Group, Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Standard, 2004.
[14] IEEE 802.16 Working Group, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, IEEE Standard, 2005.
[15] H. Y. Wei, S. Ganguly, R. Izmailov, and Z.J. Haas, “InterferenceAware IEEE 802.16 WiMax Mesh Networks,” IEEE Vehicular Technology Conference (VTC), pp. 3102 3106, 2005.
[16] 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,” IEEE Vehicular Technology Conference (VTC), pp. 16081612, 2007.
[17] Y. Cao, Z. Liu, Y. Yang, “A Centralized Scheduling Algorithm based on Multipath Routing in WiMax Mesh Network,” IEEE International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), pp. 14, 2006.
[18] H. Shetiya and V Sharma, “Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Network,” IEEE Wireless Communications and Networking Conference (WCNC), pp. 174152, 2006.
[19] S. M. Cheng, P. Lin, D. W. Huang, S. R. Yang, “A Study on DistributedCentralized Scheduling for Wireless Mesh Network,” IEEE International Wireless Communications and Mobile Computing conference (IWCMC), pp. 599604, 2006.
[20] B. Han, FP Tso, L. Lin and W. Jia, “Performance Evaluation of Scheduling in IEEE 802.16 Based Wireless Mesh Networks,” IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), pp. 789794, 2006.
[21] B. Han, L. Lin and W. Jia, “Performance Evaluation of Scheduling in IEEE 802.16 Based Wireless Mesh Networks,” Computer Communications, vol. 30, no. 4, pp. 782792, Feb. 2007.
[22] D. Ghosh, A. Gupta, P. Mohapatra, “Admission Control and InterferenceAware Scheduling in Multihop WiMAX Networks,” IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), pp. 19, 2007.
[23] S. Ramanathan, E. L. Lloyd, “Scheduling Algorithms for Multihop Radio Networks,” IEEE/ACM Transactions on Networking, vol. 1, pp. 166 177, 1993.
[24] A. Esmailpour and N. Nasser, “A Novel Scheme for Packet Scheduling and Bandwidth Allocation in WiMAX Networks,” IEEE International Conference on Communication (ICC), pp. 16, 2011.
[25] J. M. Liang, J. J. Chen,Y. C. Wang and Y. C. Tseng, “A CrossLayer Framework for Overhead Reduction, Traffic Scheduling, and Burst Allocation in IEEE 802.16 OFDMA Networks,” IEEE Transactions on Vehicular Technology, vol. 60, no. 4, pp. 17401755, May 2011.
[26] P. H. Wu and J. N. Hwang, “CrossLayer ChannelQualityFair Scheduling for Video Uplink of Camera Networks over WiMAX,” IEEE International Conference on Communication (ICC), pp. 15, 2011.
[27] A. Esmailpour and N. Nasser, “Dynamic QoSBased Bandwidth Allocation Framework for Broadband Wireless Networks,” IEEE Transactions on Vehicular Technology, vol. 60, no. 6, pp. 26902700, July 2011.
[28] H. C. Lu, W. Liao, “Joint Base Station and Relay Station Placement for IEEE 802.16j Networks,” IEEE Global Communications Conference (GLOBECOM), Nov. 2009.
[29] 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, pp. 151158, Jan. 2011.
[30] 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 (ICC), June 2009.
[31] P. S. Mogre, M. Hollick, S. Dimitrov and R. Steinmetz, “Incorporating Spatial Reuse into Algorithms for Bandwidth Management and Scheduling in IEEE 802.16j Relay Networks,” IEEE 34th Conference on Local Computer Networks (IEEE LCN), Oct. 2009. 
論文使用權限 
同意紙本無償授權給館內讀者為學術之目的重製使用，於20180814公開。同意授權瀏覽/列印電子全文服務，於20180814起公開。 


