林海峰 韋素云 劉云飛

(南京林業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，南京 210037)

隨著3G移動通信成為全球性的通信標(biāo)準(zhǔn)，新的服務(wù)質(zhì)量(QoS)的模型和算法的開發(fā)，使得3G發(fā)展成為真正的集成服務(wù)網(wǎng)絡(luò).時延、公平性和吞吐量是QoS的關(guān)鍵因素［1-5］.如果一個用戶經(jīng)常無法獲得任何服務(wù)，它的很多分組將會因為超時而被丟棄，進(jìn)而導(dǎo)致其QoS明顯下降.另一方面，有效的調(diào)度策略能夠增加信道利用率，從而使用戶的時延性能獲得提高［6-9］.因此為了提高時延性能、公平性和吞吐量，好的調(diào)度策略應(yīng)該在為用戶提供有保證的服務(wù)的同時有效地利用無線信道的容量［10-14］.本文提出了一種有效的無線分組調(diào)度算法，該算法在基于傳統(tǒng)的分組公平排隊(PFQ)策略基礎(chǔ)上，設(shè)計一個新的傳輸速率選擇方案.該方案考慮用戶落后(lagging)服務(wù)的同時，還考慮用戶活躍(leading)服務(wù)，從而使系統(tǒng)中所有用戶獲得較好的時延性能、公平性和信道吞吐量.

1 系統(tǒng)建模

本文研究無線網(wǎng)絡(luò)多用戶多服務(wù)下分組調(diào)度機制.假設(shè)某一個小區(qū)內(nèi)存在M個具有時延敏感業(yè)務(wù)的用戶，共提出N種服務(wù).該系統(tǒng)僅支持一個信道，信道容量為E，在任意時刻僅有一個用戶能夠接受服務(wù).由于調(diào)度器需要利用信道條件以及用戶數(shù)量進(jìn)行調(diào)度判決，使用隨機過程來模擬信道條件和用戶數(shù)量.

系統(tǒng)模型如圖1所示，當(dāng)一個用戶提出一個具有時延敏感的服務(wù)時，根據(jù)此刻的信道條件，判斷服務(wù)的活躍情況，從而調(diào)度器決定將其放入活躍序列或落后序列.根據(jù)信道的實際傳輸速率更新序列，確保系統(tǒng)中所有用戶獲得較好的時延性能、公平性和信道吞吐量.

圖1 系統(tǒng)模型

2 算法

首先對算法中的變量進(jìn)行說明.令Φji(S0)表示在t=0時刻用戶i提出服務(wù)j的會話S的時延門限;表示在t時刻為用戶i提供服務(wù)j的信道條件;Wji(St)表示在t時刻為用戶i提供服務(wù)j的控制參數(shù);Xji(St)表示在t時刻用戶i提出服務(wù)j的會話S的信道帶寬實際使用率.算法中使用了2個隊列:活躍隊列和落后隊列.(Lji(St)，Dji(St))，這里，L為隊列長度;D為時延常量，與隊列長度以及服務(wù)類型有關(guān);d為突發(fā)情況變量，在每個單位時間內(nèi)都將會發(fā)生變化，當(dāng)t=0時，D=d.S0為會話提交給信道的時刻.

假設(shè)在時刻t，活躍會話和落后會話的信道條件狀態(tài)良好.當(dāng)d∈［0，∞］時，lagging(St)=leading(St)，即在任意時刻，活躍隊列的總帶寬總是等于落后隊列的總帶寬.

模擬用戶 在每一個單位時間產(chǎn)生一個隨機整數(shù)U(t)，其中U(t)∈［0，Umax］，Umax=E/mindj(j=1，2，…，N).

時延保證 本文只考慮具有良好信道質(zhì)量的數(shù)據(jù)流，并不考慮信道質(zhì)量不好的數(shù)據(jù)流.例如，某一個服務(wù)的時延是3package/s，如果它的隊列長度是12個分組，那么這些分組將在12/3=4 s內(nèi)發(fā)送完畢.在本文的算法中，Φji(S0)=Wji(S0)=12/4=3package/s，如果受帶寬等因素的影響，在第1 s只能分配給此次會話1個分組的帶寬，那么當(dāng)信道質(zhì)量恢復(fù)良好時，需要對此次會話做一些相應(yīng)的補償措施，因此在這種情況下，Wji(St)=3+2/3=11/3package/s，即為了保證此次會話的時延，需要分配更多的帶寬給它.

公平性包括長期公平性和短期公平性.

長期公平性 假設(shè)信道繁忙時，某一個會話暫時沒有機會獲得調(diào)度，但是一旦信道質(zhì)量良好，并且此次會話無差錯，那么它將獲取原先在信道質(zhì)量差的錯誤狀態(tài)下“丟失”的所有服務(wù).系統(tǒng)中任意一個活躍的無錯用戶均可以在一定的時間門限內(nèi)獲得有保證的服務(wù)時間，提供長期公平保證.

短期公平性 對每個數(shù)據(jù)流都有一個隨時間變化的共享服務(wù).當(dāng)信道狀態(tài)變差時，該會話的共享服務(wù)隨之增加.這種變化是有范圍界定的，算法采用傳統(tǒng)分組公平排隊調(diào)度PFQ法來提供嚴(yán)格的延遲邊界，用賦予每個數(shù)據(jù)流的動態(tài)的時變公平共享因子來適應(yīng)不同數(shù)據(jù)流的QoS需要，在系統(tǒng)輸出和公平性方面得到了良好的折中.短期公平依據(jù)傳統(tǒng)分組公平排隊調(diào)度PFQ算法中公平性.相同狀態(tài)下收到相同數(shù)量歸一化服務(wù)的會話需求包括:①活躍會話在獎勵期間需要得到相同歸一化數(shù)量的懲罰;②獎勵服務(wù)需要依據(jù)落后會話的速率按比例分配;③當(dāng)錯誤會話的服務(wù)可用，落后會話以相同歸一化速率獲得這些服務(wù)，落后會話同樣如此.

最大化信道吞吐量 本文的模型將信道帶寬分配給具有良好信道質(zhì)量的會話，即帶寬使用率為100%，沒有數(shù)據(jù)包丟失，因此信道吞吐量將一直能夠達(dá)到最大.

3 證明

引理1 無差錯會話的落后序列長度小于Lmax，其中Lmax表示信息的最大長度.

證明 歸納法.從算法可見，無差錯的落后會話i在以下幾種情況下會發(fā)生變化:①會話i狀態(tài)變活躍;②會話i被選中的同時，另一個超前會話j也被選中，并接受服務(wù);③會話i從另一個會話j上得到服務(wù).

1)基本步驟 當(dāng)一個無差錯會話i狀態(tài)變活躍時，它的落后序列被設(shè)置成0，引理正確.

2)歸納步驟 假設(shè)lagi≤Lmax，考慮2種情況:①lagi＜0;②0≤lagi≤Lmax.在情況①中，由于會話i處于活躍狀態(tài)，只有當(dāng)另一個會話j獲得服務(wù)時，它的落后序列長度增加，這時有

式中，Lkj代表會話j隊列頭部的分組長度.在情況②中，會話i不是活躍的，因此落后序列長度只能減少.

證畢.

定理1 規(guī)范化服務(wù)之間的差異收到任何兩會話i和j的時間間隔［t1，t2)，其中2次會話不斷累積，無差錯，而且他們的狀態(tài)沒有變化是有界定的.

假設(shè)考慮2種情況:在任意時間間隔［t1，t2)內(nèi)，2個會話同時都是落后狀態(tài)，或者同時都是活躍狀態(tài).

證明 假設(shè)在任意時間間隔［t1，t2)內(nèi)，2個會話同時都是落后狀態(tài).這種情況下，2個會話有可能都被選中接受服務(wù)，或者從另一個活躍會話接受獎勵.無錯的落后會話在任意時間間隔［t1，t2)內(nèi)接受的服務(wù)總數(shù)遵循以下不等式:

當(dāng)在任意時間間隔［t1，t2)內(nèi)，2個會話同時都是活躍狀態(tài)，可得αi－βj≤(E－di－dj)((di－dj)/(di+dj))，其中α，β表示2個活躍會話的比例，E表示信道容量，假設(shè)di＞dj.

證明 假設(shè)在時刻t，2個會話都處于活躍狀態(tài).并且假設(shè)在時刻t，只有這2個會話請求，為了按比例分配帶寬，分配給會話i的實際帶寬是αi=(E－di－dj)(di/(di+dj))，分配給會話j的實際帶寬是βj=(E－di－dj)(dj/(di+dj))，可得:

1)在時刻t，αi－βj≤(E－di－dj)((di－dj)/(di+dj))成立;

2)在時間間隔［t1，t2)內(nèi)，αi－βj≤(E－di－dj)((di－dj)/(di+dj))(t2－t1)成立.

定理1說明了在任何時間間隔內(nèi)2個活動的無差錯的歸一化會話在同一狀態(tài)上是有嚴(yán)格界定的(例如活躍或滯后是有界定的，從而保證短期的公平性.

定理2 如果在時刻t之后，落后會話i在處于無錯狀態(tài)，當(dāng)會話i不斷請求服務(wù)時，那么必須保證它在最多Δ個單位時間后接受服務(wù)，其中

式中，L0是t=0時刻的分組長度;d0是t=0時刻的時延門限.

定理2證明了算法的長期公平性.

證明 通過算法的偽代碼，可得:

4 仿真實驗

4.1 服務(wù)定義

本文定義n(n=4)種能被信道接收的服務(wù)，以及每個服務(wù)的時延門限，如表1所示.

表1 服務(wù)定義

4.2 會話產(chǎn)生器

使用C++代碼生成隨機會話，以及會話ID和會話的長度.

/*生成會話*/

#include＜iostream＞

#include＜ctime＞

using namespace std;

int main()

{

srand(time(0));

int S［4］;

int L［4］;

for(int i=0;i＜4;i++){

}

for(int j=0;j＜4;j++){

cout?"L［"?j?"］="?L［j］?"";

cout?endl;

}

return 0;

}

其中，數(shù)組S表示會話ID(0～3)，數(shù)組L表示每一個服務(wù)(1～100)的會話長度，結(jié)果如表2所示.

表2 數(shù)組定義

從表2中可以看出系統(tǒng)在同一時刻產(chǎn)生4組會話，例如，會話［0］的ID為3，代表它是HTTP服務(wù)，會話長度為84個分組，由于HTTP服務(wù)的時延門限是5package/s，因此為了保證服務(wù)質(zhì)量，必須保證此次會話在［84/5］=17 s中被接收.

4.3 白噪聲產(chǎn)生器

本文只關(guān)注調(diào)度算法本身，而不是物理信道.使用高斯隨機變量生成器生成信道噪聲.稍后將介紹更復(fù)雜的信道模型.以下用C++代碼模擬信道條件(C++高斯噪聲產(chǎn)生器).

/*每秒鐘產(chǎn)生符合高斯分布的白噪聲*/

#include＜cstdlib＞

#include＜iostream＞

#include＜ctime＞

using namespace std;

const int numSamples=3;

int main()

{

srand(time(0));

const static int q=15;

const static float c1=(1?q)－1;

const static float c2=((int)(c1/3))+1;

const static float c3=1.f/c1;

float random=0.f;

float noise=0.f;

for(int j=0;j＜10;j++){

cout?"time:"?j?endl;

for(int i=0;i＜=numSamples;i++){

random=((float)rand()/(float)(RAND_MAX+1));

noise=(2.f*((random*c2)+(random*c2)+(random*c2))－3.f*(c2－1.f))*c3;

cout?noise?endl;

}

sleep(1);

}

return 0;

}

該算法生成符合高斯分布的隨機數(shù)，其中均值為0，方差為1(標(biāo)準(zhǔn)高斯分布)，隨機數(shù)映射范圍在－1～1之間，并且在0點上取得最大值.變量q代表精度，通常效果最好的參數(shù)設(shè)置是q=15，則2個隨機數(shù)間的最短距離是1/(2qdiv 3)=1/10922.代碼中的“sleep(1)”是用來模擬每秒鐘每一次會話的信道條件，如果值大于0，說明本次會話的信道條件良好，反之，如果值不大于0，則說明本次會話的信道條較差.表3列出連續(xù)10 s模擬信道情況.

表3 連續(xù)10 s模擬信道情況

4.4 仿真結(jié)果

在經(jīng)過第2步會話產(chǎn)生器、第3步白噪聲產(chǎn)生器的基礎(chǔ)上，得到仿真結(jié)果，如表4所示.下一節(jié)將分析如何得到這些結(jié)果，以及如何滿足時延、公平性、吞吐量3方面的性能.

表4 連續(xù)10 s的仿真結(jié)果

在表4中，α表示在時刻t分配給會話的帶寬，β表示在在時刻t還剩下多少數(shù)據(jù)包，τ表示維持本次會話的剩余時間，σ表示在時刻t有多少超前(+)或滯后(－)的數(shù)據(jù)包.

信道容量:E=27 package，假設(shè)4個會話長度分別為3，1，2，2，那么5+20+1+1=27 package，如果信道質(zhì)量良好，27 package是信道容量的下界，可以滿足4個會話的時延門限.

4.5 結(jié)果分析

時延 從表4中可以看出，本文的算法能夠很好地處理每一個會話的時延門限，例如，會話1在時刻1結(jié)束，會話2在時刻8結(jié)束，會話3在時刻4結(jié)束.雖然會話0在以上連續(xù)10 s內(nèi)并未結(jié)束(還剩余35 package)，但在剩下的時間內(nèi)，如果會話0的信道條件良好，那么會話0可以占用整個帶寬來順利通信.

長期公平性 由于每個會話最終都可以在時刻i結(jié)束，這意味著經(jīng)過足夠長網(wǎng)絡(luò)繁忙時間，如果此次會話無差錯，那么一旦有足夠的服務(wù)需求，它將獲取原先在錯誤狀態(tài)下“丟失”的所有服務(wù).

短期公平性 由表4可知，在時刻0上只有會話0和會話2擁有良好的信道條件，為了處理時延，首先給會話0分配5個數(shù)據(jù)包，給會話2分配1個數(shù)據(jù)包，由于整個信道容量是27個數(shù)據(jù)包，因此還可以分配容量27－5－1=21 package，根據(jù)時延處理規(guī)則，將給會話0分配5+［21×5/6］=22 package，給會話2分配1+［21×1/6］=5 package，此結(jié)果與第3節(jié)的證明:在時刻t上，αi－βj≤(E－di－dj)((di－dj)/(di+dj))的結(jié)論相一致.

吞吐量 在單位時間內(nèi)，對于信道狀態(tài)良好的會話，將分配盡可能多的帶寬，這樣不僅能夠處理時延，而且可以獲得單位時間內(nèi)的最大吞吐量，例如表4中的時刻0(24+3=27)，但最壞的情況是所有會話的信道狀態(tài)都很差，如表4中的時刻2所示.

5 結(jié)語

本文提出了一種用于無線網(wǎng)絡(luò)中的分組調(diào)度算法，該算法不僅能夠滿足用戶公平性的要求，而且能夠處理多種服務(wù)中的突發(fā)情況.算法綜合考慮信道條件，確保在單位時間內(nèi)單個信道獲取最大吞吐量，同時考慮長期公平性以及短期公平性，使得整體吞吐量達(dá)到最大.在后續(xù)工作中將進(jìn)一步細(xì)化信道情況，基于復(fù)雜信道情況的分組調(diào)度算法有待進(jìn)一步研究.

References)

［1］Cao Jianglian，Pei Tingrui.One novel multi-services scheduling algorithm in WCDMA system［C］//Proceedings of the 27th Chinese Control Conference.Kunming，China，2008:365-369.

［2］Elshaikh M A，Othman M，Subramaniam S，et al.Enhanced TSWTCM to improve fairness in DiffServ networks［C］//13th IEEE International Conference on Networks.Kuala Lumpur，Malaysia，2005:302-307.

［3］Elshaikh M A，Othman M，Shamala S，et al.A new fair weighted fair queuing scheduling algorithm in differentiated services network［J］.International Journal of Computer Science and Network Security，2006，6(11):267-271.

［4］Cao Yaxin，Li V O K，Cao Zhigang.Scheduling delay-sensitive and best-effort traffics in wireless networks［C］//IEEEInternational Conference on Communications.Alaska，USA，2003:2208-2212.

［5］Lee B G.QoS support by using CDF-based wireless packet scheduling in fading channels［J］.IEEE Transactions on Communications，2006，54(5):955.

［6］Liu Xin，Chong E K P，Shroff N B.Optimal opportunistic scheduling in wireless networks［C］//Vehicular Technology Conference.Los Angeles，CA，USA，2003:1417-1421.

［7］Abawajy J H.Job scheduling policy for high throughput computing environments［C］//Proceedings of the Ninth International Conference on Parallel and Distributed Systems.2002:605-610.

［8］Farrokh A，Krishnamurthy V.Opportunistic scheduling for streaming users in high-speed downlink packet access［C］//Global Telecommunications Conference.2004:4043-4047.

［9］Liu Xin，Chong E K P，Shroff N B.Transmission scheduling for efficient wireless resource utilization with minimum-performance guarantees［C］//Vehicular Technology Conference.San Antonio，2001:824-828.

［10］Liu Yonghe，Gruhl S，Knightly E W.WCFQ:an opportunistic wireless scheduler with statistical fairness bounds［J］.Wireless Communications，2003，2(5):1017-1028.

［11］Elshaikh M A，Othman M，Subramaniam S，et al.An enhancement of TSWTCM algorithm to improve fairness in Diff-Serv networks:design and implementation［C］//Brunei International Conference of Engineering and Technology.Bandar Sri Begawan，2005:89-96.

［12］Avidor D，Ling J，Papadias C.Jointly opportunistic beamforming and scheduling(JOBS)for downlink packet access［C］//2004 IEEE International Conference on Communications.Paris，2004:2959-2964.

［13］Choi Yonghoon，Han Youngnam.A channel-based scheduling algorithm for cdma2000 1xEV-DO system［C］//The 5th International Symposium of Wireless Personal Multimedia Communications.Lisboa，Portugal，2002:621-625.

［14］Choi Eun Ho，Choi Wan，Andrews J.Throughput of the 1x EV-DO system with various scheduling algorithms［C］//IEEE Eighth International Symposium of Spread Spectrum Techniques and Applications.2004:359-363.