即時性與非即時性訊務之無線網路資源分配

Resource Allocation for Real-Time and Non-Real-Time Traffic in Wireless Networks

黃郁文(Yu-Wen Huang)

指導教授 ： 李程輝

國立交通大學/電機學院/電信工程系所/博士(2011年)

https://doi.org/10.6842/NCTU.2011.01171

摘要

在本篇論文中，我們首先討論無線網路(IEEE 802.11e WLANs、以OFDMA技術為基礎的系統)資源分配技術。接著，將相關經驗應用至廣義有線系統即時性訊務多工器。
在IEEE 802.11e WLANs中，我們用高效能TXOP分配演算法、多工機制與相關的允入控制單元推廣IEEE 802.11e HCCA規格標準中的樣本排程器以保證不同變動位元速率訊務的不同服務品質保證需求(延遲限制、封包遺失率)。其中，我們透過定義等效訊務流和集成封包遺失率來得到訊務內與訊務間多工增益。並藉此達到高頻寬使用效率。再者，我們採用加權遺失公平的服務排程演算法將集成TXOP分配給各個訊務流。電腦模擬結果顯示我們提出的方法可以達到訊務流之服務品質需求，並且與先前研究比較起來，可以達到較高的頻寬使用效率。
在以OFDMA技術為基礎的系統中，我們提出同時處理即時性與非即時性訊務的資源分配演算法。其中，對於即時性訊務而言，假設其服務品質需求為延遲限制與資料遺失率。接著，根據訊務流之延遲限制與資料遺失率計算『最小所需頻寬』，然後將資源分配定義為滿足訊務流之『最小所需頻寬』下，最大化系統吞吐量之最佳化問題。資源分配結束後，若用戶端連結多個訊務流，則採用等比例遺失排程演算法決定訊務流間資源分配。萬一現有資源無法提供每個訊務流最小所需頻寬，則將資源分配問題轉為最大化即時性訊務傳送量。其中，每個用戶所得資源不得超過其最小所需頻寬。此外，我們也設計『先行處理器』以最大化滿足服務品質需求之訊務流數。在本論文中，我們證明，在任意訊框中，若任意排程演算法可滿足訊務流之服務品質需求，則我們提出之等比例排程演算法亦可。電腦模擬結果亦顯示我們提出之演算法相較於先前的研究，擁有較佳效能。
論文的最後一個部份，我們研究可處理變動封包長度之多工系統。我們提出等比例遺失佇列管理演算法，使其與近期限優先之排程演算法結合提供即時性訊務之不同服務品質需求(延遲限制與資料遺失率)。我們指出，若以等效頻寬為指標，我們所提出之等比例遺失演算法為最佳佇列管理演算法。等比例遺失演算法假設封包可以無限制切割。為了更貼近實際封包交換網路，我們亦提出二個以封包為基本單位之佇列管理演算法。其中一個演算法為G-QoS演算法之直接推廣，另外一個則根據等比例遺失演算法的結果設計。電腦模擬結果指出，根據等比例遺失演算法設計的佇列管理演算法(以封包為基本單位)比G-QoS演算法之直接推廣，擁有較佳效能。

關鍵字

無線網路 ； 服務品質保證

並列摘要

In this dissertation, we firstly studied resource allocation technique for wireless network such as IEEE 802.11e WLANs and OFDMA-based systems. Then, extend the developed results to a general multiplexer for real-time traffic in wired systems.
In IEEE 802.11e WLANs, we generalize the sample scheduler described in IEEE 802.11e HCCA standard with an efficient TXOP allocation algorithm, a multiplexing mechanism, and the associated admission control unit to guarantee QoS for VBR flows with different delay bound and packet loss probability requirements. We define equivalent flows and aggregate packet loss probability to take advantage of both intra-flow and inter-flow multiplexing gains so that high bandwidth efficiency can be achieved. Moreover, the concept of proportional-loss fair service scheduling is adopted to allocate the aggregate TXOP to individual flows. From numerical results obtained by computer simulations, we found that our proposed scheme meets QoS requirements and results in much higher bandwidth efficiency than previous algorithms.
In OFDMA-based Systems, we present a resource allocation algorithm for OFDMA-based systems which handles both real-time and non-real-time traffic. For real-time traffic, the QoS requirements are specified with delay bound and loss probability. The resource allocation problem is formulated as one which maximizes system throughput subject to the constraint that the bandwidth allocated to a flow is no less than its minimum requested bandwidth, a value computed based on loss probability requirement and running loss probability. A user-level proportional-loss scheduler is adopted to determine the resource share for flows attached to the same subscriber station (SS). In case the available resource is not sufficient to provide every flow its minimum requested bandwidth, we maximize the amount of real-time traffic transmitted subject to the constraint that the bandwidth allocated to an SS is no greater than the sum of minimum requested bandwidths of all flows attached to it. Moreover, a pre-processor is added to maximize the number of real-time flows attached to each SS that meet their QoS requirements. We show that, in any frame, the proposed proportional-loss scheduler guarantees QoS if there is any scheduler which guarantees QoS. Simulation results reveal that our proposed algorithm performs better than previous works.
Finally, we study a multiplexing system which handles variable-length packets. A proportional loss (PL) queue management algorithm is proposed for packet discarding, which combined with the work-conserving EDF service discipline, can provide QoS guarantee for real-time traffic flows with different delay bound and loss probability requirements. We show that the proposed PL queue management algorithm is optimal because it minimizes the effective bandwidth among all stable and generalized space-conserving schemes. The PL queue management algorithm is presented for fluid-flow models. Two packet-based algorithms are investigated for real packet switched networks. One of the two algorithms is a direct extension of the G-QoS scheme and the other is derived from the proposed fluid-flow based PL queue management algorithm. Simulation results show that the scheme derived from our proposed PL queue management algorithm performs better than the one directly extended from the G-QoS scheme.

並列關鍵字

Wireless Networks ； Quality of Service

參考文獻

[3] S. Mangold, S. Choi, and G. R. Hiertz, “Analysis of IEEE 802.11e for QoS support in Wireless LANs,” IEEE Wireless Commun., vol. 10, no. 6, pp. 40-50, Dec. 2003.

[5] E. Dahlman, S. Parkvall, J. Skold, and P. Beming, “3G HSPA and LTE for Mobile Broadband,” New York: Academic, 2007.

[6] C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” J. ACM, vol. 20, no. 1, pp. 46-61, 1973.

[7] A. K. Parekh and R.G. Gallager, “A Generalized Processor Sharing Approach to flow control in Integrated Services Networks - The Single Node Case,” IEEE/ACM Trans. on Networking, vol. 1, no.3, pp. 344-357, Jun. 1993.

[8] A. K. Parekh and R.G. Gallager, “A Generalized Processor Sharing Approach to flow control in Integrated Services Networks - The Multiple Node Case,” IEEE/ACM Trans. on Networking, vol. 2, no.1, pp. 137-150, Apr. 1994.