Bandwidth utilization improvement scheduling algorithms for IEEE 802.16 wireless broadband networks

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 學位論文 > Item 987654321/94447

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

Title:	Bandwidth utilization improvement scheduling algorithms for IEEE 802.16 wireless broadband networks
Other Titles:	IEEE 802.16無線寬頻網路中，提升頻寬資源利用率之排程演算法設計
Authors:	蔣季陶;Chiang, Chi-Tao
Contributors:	淡江大學資訊工程學系博士班石貴平;Shih, Kuei-Ping
Keywords:	頻寬分配演算法;IEEE 802.16;網狀網路;點對多點網路;無線寬頻網路;全球互通微波存取;Bandwidth Allocation Algorithms;Mesh Networks;Point-to-multipoint Networks;Wireless Broadband Networks;Worldwide Interoperability for Microwave Access (WiMAX)
Date:	2013
Issue Date:	2014-01-23 14:39:25 (UTC+8)
Abstract:	在無線網路的環境中，增加頻寬利用率一直以來是一個很重要的議題之一，尤其是在 802.16 寬頻網路環境。其原因在於 802.16 使用的頻寬大小是有限的，同時，802.16 運作的頻譜必須透過付費授權才能夠使用。因此，對於一個電信業者而言，如何有效率的來使用這些有限的頻寬以最大化系統效能，是各大電信業者共同努力的目標。有鑑於此，本研究將分別就 802.16 支援的兩種網路環境：點對多點(Point-to-multipoint, PMP)與網狀網路(Mesh)，來針對問題來進行深入的探討與研究。在IEEE 802.16 點對多點網路，頻寬資源的分配基本單位是Burst，而每個Burst是由許多的Slot所構成的二維空間。本研究探討問題是Burst Allocation Problem (簡稱BAP)，在BAP中，將決定每個Burst的形狀與位置，以最大化Downlink頻寬利用率。為了解決BAP，我們提出Burst Fragmentation, Packing and Scheduling Algorithm (簡稱 BFPA) 與 Burst Shifting Scheme (簡稱BSS)。BFPA主要可以分成3個Schemes，首先，在Burst Allocation Scheme中，BS會透過決定每個Burst在Downlink Subframe中的位置與排入的先後順序來解決外部碎裂的問題發生，然而，在Allocation的過程中，可能會有內部碎裂的問題發生，因此，在第二個Scheme中，將針對發生內部碎裂的Burst進行切割，釋放內部碎裂的空間給其他Burst使用，同時，所切割出來的Burst將填補部分外部碎裂的空間，最後，再透過Burst Packing的方式，將支援相同調變的Burst進行合併，降低DL-MAP Control Overhead。BSS的運作是在給定一組的Burst Allocation的情況， BSS 主要是利用Burst Overlapping概念，Burst Overlapping概念是讓相鄰兩有內度碎裂的Burst能夠透過調整內部碎裂在Burst中的位置，利用Burst平移，使相鄰兩Burst可以共用內部碎裂的Slots來減少Slot的浪費，進而增加頻寬利用率。在IEEE 802.16 網狀網路的環境中，頻寬資源分配的基本單位是Minislots，本論文考量在IEEE 802.16 無線網狀網路傳輸環境中，針對規格書所定義的集中式排程 (Centralized Scheduling) 機制下提出一個分散式時槽排程機制。此機制的目標在於有效地分配Minislots資源使其能充分的利用，期望能夠使用最少的Minislots 來滿足網路中節點的需求。基於此目的，本論文先使用整數線性規劃 (Integer Linear Problem, ILP) 的方式來建構此排程問題的模型。此數學模型考慮傳輸對在不會互相影響的前提下，Minislot 的最佳使用數量及排程方式。然而ILP屬於NP-complete 之問題，因此本論文因而進一步探討分散式時槽分散式機制以符合IEEE 802.16 無線網狀網路之真實情況。本論文首先探討不當的選擇Minislot 將會衍生出的三大造成整體網路執行效能下降問題：資料傳輸碰撞 (Data Collision Problem) 、Flow內部Minislot不足問題 (Intra-flow Minislot Insufficient Problem, Intra-flow MIP) 及Flow間Minislot不足問題 (Inter-flow Minislot Insufficient Problem, Inter-flow MIP) 。有鑑於此，本論文對於網路中節點使用Minislots傳輸方式提出Minislots使用限制（Minislots Usage Constraints, MUCs）與Minislots決定政策（Minislots Decision Strategies, MDSs），並且同時考慮資料傳輸路徑上Minslots 的衝突問題及Minislot 的重覆使用，提出一分散式Minislot 時槽排程之機制。本論文預期透過此分散式MInislot排程機制之設計，致使多對傳輸對可在同時間內進行傳輸，並降低碰撞的機率，藉以提高頻寬利用率。除了上述方法提出外，本論文亦透過模擬的方式來驗證方法的效能，同時並與相關研究進行比較，透過多項的效能評估，可以發現本研究提出的做法不管在網狀網路與點對多點網路，對於頻寬使用之提升均有很大的助益。 Improving bandwidth utilization is one of the important research issues, especially in the IEEE 802.16 wireless broadband networks. The IEEE 820.16 standard supports two network topologies, the point-to-multipoint networks and mesh networks. In this dissertation, bandwidth utilization improving scheduling algorithms are proposed for these two supported networks, respectively. For the point-to-multipoint networks, burst is an atomic bandwidth allocation unit for downlink and uplink transmissions in IEEE 802.16 orthogonal frequency division multiple access (OFDMA) systems. This dissertation investigates downlink burst scheduling problem in IEEE 802.16 OFDMA systems. Solving this problem with the objective of maximizing downlink bandwidth utilization, a burst fragmentation, packing and allocation algorithm is proposed to decide the position and shape of each burst in the downlink subframe. For further improving the downlink bandwidth utilization in an given burst allocation scenario, a burst shifting scheme is proposed to make neighboring bursts share and utilize wasted slots caused by the rectangular mapping constraint of bursts by means of arranging the position of the wasted slots in bursts. For the mesh networks, minislot is an atomic bandwidth allocation unit for data transmissions among subscriber stations and base station. This dissertation overcomes minislot scheduling problem for IEEE 802.16 mesh networks and formulates this problem as an integer linear programming model. Due to the high computational complexity for solving integer linear programming model at subscriber stations and the degrade of bandwidth utilization resulted from data collision problems and minislot insufﬁcient problems, this dissertation proposes a decentralized minislot scheduling protocol to make subscriber stations, rather than the base station, schedule minislot usage for throughput gains in the IEEE 802.16 mesh networks. The decentralized minislot scheduling protocol includes minislot usage constraints and minislot decision strategies to alleviate data collisions and minislot insufﬁcient problems as well as to increase bandwidth utilization. The proposed protocol not only can accommodate to the IEEE 802.16 standard, but also make subscriber stations schedule minislots with the latest minislot usage information. Based on the above mentions, this dissertation conducts a series of simulations to evaluate the performance of proposed bandwidth utilization improving scheduling algorithms for the two supported networks, respectively. The simulation results show that the proposed algorithms and protocol outperform related work in the bandwidth utilization.
Appears in Collections:	[資訊工程學系暨研究所] 學位論文

Files in This Item:

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

Loading...