Relay deployment and scheduling approaches for improving network throughputs in WiMAX broadband networks

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Thesis > Item 987654321/94393

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/94393

Title:	Relay deployment and scheduling approaches for improving network throughputs in WiMAX broadband networks
Other Titles:	WiMAX寬頻無線網路中具提升網路效能之中繼站佈建與排程技術
Authors:	李明憲;Li, Ming-Hsien
Contributors:	淡江大學資訊工程學系博士班張志勇;Chang, Chih-Yung
Keywords:	全球互通微波存取;佈建;排程;中繼站;寬頻無線網路;WiMAX;Deployment;scheduling;Relay;Broadband Wireless Network
Date:	2013
Issue Date:	2014-01-23 14:33:02 (UTC+8)
Abstract:	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)和Cost-Aware 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 Cost-Aware 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.
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	249	View/Open

Loading...