常用調度算法

本詞條以LTE為例介紹LTE技術中的常用調度算法。

調度器的主要功能是在不同時間點上為不同的用戶調度各種系統資源,它是基站中最重要的組成部分之一,調度器的設計好壞直接決定了基站的工作效率和實際性能。調度器相關的內容絕大多數不在標準化工作範圍內,主要是設備內部實現的問題。調度器在工作時需要考慮多種因素,如終端所處位置的信道質量、終端快取狀態、基站系統資源狀態、業務優先權、用戶優先權等,同時利用合理的調度算法使系統資源利用效率最高,儘量保證用戶有最好的使用體驗。

通信系統中使用的調度算法主要是3種:輪詢算法(Round Robin,RR)、最大載乾比算法(Maximum C/I)和比例公平算法(Proportional Fair)。下面對這3種基本算法進行簡要介紹。

基本介紹

  • 中文名:常用調度算法
  • 外文名:Commonlyusedschedulingalgorithm
  • 所屬學科:通信
輪詢算法,最大載乾算法,比例公平算法,

輪詢算法

輪詢算法的基本思想就是認為小區內所有用戶的調度優先權都是相等的,所有用戶周期性地被調度,保證每個用戶被調度機率相同。例如小區中有3個用戶,採用輪詢算法的調度器不會考慮每個用戶所處的位置以及之前被調度的情況,只是簡單地按照某個固定的調度順序,如終端1、終端2、終端3、終端1、終端2、終端3……周期性地調度每個用戶。因此輪詢算法是一種典型的追求公平最大化的調度算法,實現起來比較簡單。但是,輪詢算法沒有考慮不同用戶的信道狀況,信道質量差的用戶和信道質量好的用戶會被分配到相同多的調度時間,因此會導致系統的平均吞吐量受到較大影響。同時該算法也沒有考慮業務特性、用戶優先權、業務優先權等QoS方面的因素,所以在系統用戶數較多、業務複雜的情況下,輪詢算法難以發揮理想的調度效果。

最大載乾算法

最大載乾比算法的基本思想是在每一個調度時刻,調度器會對所有待調度用戶進行載乾比(也就是意味著可以達到的最大瞬時傳輸速率)的排序,然後調度器會選擇信道質量最好的用戶進行調度,這樣保證系統總是能夠調度到最好的用戶,保證系統性能的最大化,資源利用率最高。最大載乾比算法的數學表達可以參考式(1),其中k是被調度的用戶,Ri(t)是第i個用戶的瞬時傳輸速率。
k=argmaxRi(t)(1)
可見,最大載乾比算法是一種追求系統性能最大化的調度算法,在調度周期內把所有資源分配給信號質量最好的終端,保證系統吞吐量可以達到最大值。但是,該方法完全沒有考慮公平性的因素,對於處於小區邊緣或深衰落處的終端因為信號質量不好將會長時間得不到調度,出現終端被“餓死”的情況。

比例公平算法

比例公平算法
輪詢算法保證了用戶間的公平性,但損失系統吞吐量;最大載乾比算法獲得了最大的系統吞吐量,但喪失了公平性。因此,為了在這兩種算法間取得一定的折衷,提出了比例公平算法。該方法在儘量滿足信道質量較好的終端的高速數據業務需求的同時,也兼顧信道質量狀況不好的終端的使用體驗。該算法的基本思想是在選擇用戶時考慮瞬時速率和長期平均速率的比值,同時利用權重值對不同用戶進行調整,達到同時兼顧系統性能和用戶體驗的目的。
此算法為小區內每個用戶都分配了一個優先權,在任意時刻系統調度優先權最大的用戶,比例公平算法的數學表達式可以參考式(2),其中k是被調度用戶,Ri(t)為用戶i在t時刻請求的速率,Ti(t)為用戶i在t時刻的累積平均速率。在調度完成後,需要對用戶的優先權因子進行更新。若小區中有多個用戶,當系統對某個信道質量較好的用戶連續進行了調度時,Ti(t)將會逐漸增大,使得優先權逐漸變小,從而系統會調度其他優先權較高的用戶。若某個用戶的信道質量較差,長期得不到系統的調度,那么它的平均吞吐量Ti(t)會降低,這樣的話優先權將會增大,使用戶獲得被調度的機會。比例公平算法綜合考慮了公平性和系統性能兩方面的因素,是一種性能較優的算法。
k= arg max
(2)

相關詞條

熱門詞條

聯絡我們