Fair Scheduling in Next-Generation Wireless Communication Networks

Channel and link scheduling, also referred to as resource allocation, is a fun- damental yet important issue of wireless communication networks. The design and implementation of scheduling algorithms have great impact on the performance, such as throughput, delay, jitter, and fairness, of wireless communication networks. In this dissertation, we investigate fair scheduling problems in next-generation wireless com- munication networks. First, we investigate the proportional fair scheduling in OFDMA relay networks. Such network consists of one base station and multiple relay stations that serve as MAC-level repeaters. To achieve better system efficiency and throughput, we consider frequency diversity, multi-user diversity, and cooperative diversity in the scheduling, which must be done in each frame of a duration less than 10 ms. We first formulate the problem and prove that it is a NP-hard problem. It is computationally infeasible to obtain the optimal solution in real-time. We then propose three greedy-based heuris- tic algorithms. The performance of the proposed algorithms is evaluated by extensive simulations. We show that although the three algorithms are capable of achieving fairness, they perform differently in system throughput. We explain the reasons be- hind the differences and discuss the usefulness of the algorithms in different scenarios. The computational complexities of the proposed algorithms are low. They can eas- ily meet the requirement of real-time scheduling, which makes them practical for real implementation in OFDMA relay networks. Cognitive radio has received much attention recently for its ability to improve spectrum efficiency by letting secondary users to access spectrum resource that is un- occupied by primary users. However, cognitive radio also brings new challenges in the design of future wireless networks. We investigate the problem of resource allocation in cognitive radio networks. Specifically, we consider the problem of proportional fair scheduling in cognitive radio relay networks. Our problem formulation takes into ac- count the fluctuations of usable spectrum resource, channel quality variations caused by frequency selectivity, and interference caused by different transmit power levels. We prove that the problem is NP-hard and is computationally infeasible to be solved in a timely manner by using brute force algorithms. An easy-to-compute upper bound for the formulated problem is also derived. We propose two heuristic algorithms that are easy-to-implement, yet achieve performance close to the upper bound. The proposed algorithms can be executed and finished within 1 millisecond. Thus, they can meet the requirement of real-time scheduling. Simulation experiments verify that the proposed algorithms can achieve good proportional fairness among users and enhance system throughput by proper power control.

關鍵字

公平排程； OFDMA網路；感知無線電網路

並列摘要

無線通訊頻道以及連結的排程 (又稱資源分配 Resource Allocation) 為無線通訊網路中最基本同時也最重要之課題。排程演算法的設計及實作方式對於系統的效能 (如：吞吐量、延遲、公平性等) 具有相當大的影響。此論文主要探討次世代無線通訊網路中公平排程之問題。首先，我們先就OFDMA 轉傳網路 (OFDMA Relay Networks) 中比例性公平排程 (Proportional Fair Scheduling) 的問題做深入討論。在此種網路架構下，系統由一個基地台 (Base Station)、數個MAC 層級轉傳基地台 (Relay Station) 以及數個使用者 (Mobile Station) 所構成。在執行排程時，我們考量了頻率選擇多樣性 (Frequency Diversity)、使用者多樣性 (Multi-user Diversity) 以及合作式傳輸多樣性 (Cooperative Diversity) 的影響。我們以數學方式抽象描述了此問題，並證明其為NP-Hard。因此，我們無法在有限的時間內取得此問題之最佳解。我們提出了三個貪婪式演算法，並以大量的模擬驗證其效能。模擬結果指出我們所提出之演算法可有效地達成比例性公平，並在不同的環境中具有不同的特性。我們針對各種現象提出解釋，並探討了各演算法適用的環境。我們所提出之演算法具有低複雜度，可符合實際OFDMA 轉傳網路中之使用需求。近年來，感知無線電技術 (Cognitive Radio) 於受到相當的矚目。感知無線電可讓次要使用者 (Secondary User) 利用主要使用者 (Primary User) 未利用之頻帶，以提高頻譜的使用率。但感知無線電同時也對未來無線網路的設計架構帶來了新的挑戰。此論文在接下來的部分探討了感知無線電網路中比例性公平排程資源分配的問題。我們在論文中考慮了剩餘頻寬的變動、頻道品質的差異性以及不同傳輸能量所造成的干擾之影響。我們以數學方式抽象此問題，並證明其為NP-Hard。因此，我們無法在有限的時間內求得此問題之最佳解。另外，我們針對此問題推導出了一個可輕易計算的上限。我們提出了兩個可容易實作且具有接近最佳效能之貪婪式演算法。我們所提出之演算法可在1 毫秒的時間內執行完畢，相當適合於實際系統中使用。我們同時也使用了大量的模擬實驗，驗證了所提出之演算法的效能。實驗結果證實我們的演算法可有效達成比例性公平，並藉由傳輸能量的控制提高系統的整體吞吐量。

並列關鍵字

Fair Scheduling ； OFDMA Networks ； Cognitive Radio Networks

參考文獻

[1] I. Koffman and V. Roman, “Broadband wireless access solutions based on OFDM

MIMO-OFDM broadband wireless system: design, performance, and field trial

[3] “IEEE standard for local and metropolitan area networks; part 16: air interface for

fixed and mobile broadband wireless access systems multihop relay specification.”

IEEE P802.16j/D6, July 2008.

國際替代計量

Fair Scheduling in Next-Generation Wireless Communication Networks

全文下載

主題瀏覽