在無線網路下具適應性補償之公平排程演算法

Abstract

在有線網路下，公平排程演算法可以對多媒體資料流提供有限延遲及公平性。由於位置相關及爆發性兩種錯誤，在無線網路直接應用這些演算法可能造成它們失去公平性。CIF-Q藉補償機制以解決這個問題。然而，它的補償方式可能會降低提供補償之資料流的服務品質。在本論文中，我們提出一個在無線網路下具適應性補償的公平排程演算法(AC-FQ) 。此演算法不但實現公平性，也不驟降服務品質。AC-FQ根據一條資料流的佇列長度改變其權值。一個佇列長度大(小)的資料流表示它的資料負載重(輕)。藉由這種方式，AC-FQ不但可以根據資料流的負載，適應地補償自錯誤中復原的資料流，也不降低其他無錯誤資料流的服務品質。模擬結果顯示，在不犧牲傳輸量(佇列延遲)之下，AC-FQ比CIF-Q對及時性應用(非及時性應用)有較低的佇列延遲(較高的傳輸量)。AC-FQ的理論分析證明我們的演算法能夠維持一定的公平性與傳輸量。

Fair scheduling algorithms can provide both bounded delay and fairness for multimedia traffic flows in wired networks. Applying these algorithms to wireless networks directly may cause the algorithms fall out of fairness due to location- dependent and bursty errors. CIF-Q were proposed to solve this problem through a compensation mechanism. However, its compensation may degrade the quality of service (QoS) for the flows which provide compensation. In this thesis, we propose a fair scheduling algorithm with adaptive compensation (AC-FQ) for wireless networks, which can achieve fairness as well as graceful QoS degradation. AC-FQ changes a flow's weight according to its queue length. A flow with large (small) queue length means its traffic load is heavy (light). In this way, AC-FQ can not only adaptively compensate recovered error-prone flows based on its traffic load, but also does not degrade the QoS of other error-free flows. Simulation results show that, without sacrificing throughput (queuing delay), AC-FQ has less queuing delay (higher throughput) than CIF-Q for real-time (non-real-time) Theoretical analysis of AC-FQ supports that our algorithm has bounds on fairness and throughput.