一种用于无线网络中多服务的分组调度算法

林海峰 韦素云 刘云飞

(南京林业大学信息科学技术学院，南京 210037)

随着3G移动通信成为全球性的通信标准，新的服务质量(QoS)的模型和算法的开发，使得3G发展成为真正的集成服务网络.时延、公平性和吞吐量是QoS的关键因素［1-5］.如果一个用户经常无法获得任何服务，它的很多分组将会因为超时而被丢弃，进而导致其QoS明显下降.另一方面，有效的调度策略能够增加信道利用率，从而使用户的时延性能获得提高［6-9］.因此为了提高时延性能、公平性和吞吐量，好的调度策略应该在为用户提供有保证的服务的同时有效地利用无线信道的容量［10-14］.本文提出了一种有效的无线分组调度算法，该算法在基于传统的分组公平排队(PFQ)策略基础上，设计一个新的传输速率选择方案.该方案考虑用户落后(lagging)服务的同时，还考虑用户活跃(leading)服务，从而使系统中所有用户获得较好的时延性能、公平性和信道吞吐量.

1 系统建模

本文研究无线网络多用户多服务下分组调度机制.假设某一个小区内存在M个具有时延敏感业务的用户，共提出N种服务.该系统仅支持一个信道，信道容量为E，在任意时刻仅有一个用户能够接受服务.由于调度器需要利用信道条件以及用户数量进行调度判决，使用随机过程来模拟信道条件和用户数量.

系统模型如图1所示，当一个用户提出一个具有时延敏感的服务时，根据此刻的信道条件，判断服务的活跃情况，从而调度器决定将其放入活跃序列或落后序列.根据信道的实际传输速率更新序列，确保系统中所有用户获得较好的时延性能、公平性和信道吞吐量.

图1 系统模型

2 算法

首先对算法中的变量进行说明.令Φji(S0)表示在t=0时刻用户i提出服务j的会话S的时延门限;表示在t时刻为用户i提供服务j的信道条件;Wji(St)表示在t时刻为用户i提供服务j的控制参数;Xji(St)表示在t时刻用户i提出服务j的会话S的信道带宽实际使用率.算法中使用了2个队列:活跃队列和落后队列.(Lji(St)，Dji(St))，这里，L为队列长度;D为时延常量，与队列长度以及服务类型有关;d为突发情况变量，在每个单位时间内都将会发生变化，当t=0时，D=d.S0为会话提交给信道的时刻.

假设在时刻t，活跃会话和落后会话的信道条件状态良好.当d∈［0，∞］时，lagging(St)=leading(St)，即在任意时刻，活跃队列的总带宽总是等于落后队列的总带宽.

模拟用户 在每一个单位时间产生一个随机整数U(t)，其中U(t)∈［0，Umax］，Umax=E/mindj(j=1，2，…，N).

时延保证 本文只考虑具有良好信道质量的数据流，并不考虑信道质量不好的数据流.例如，某一个服务的时延是3package/s，如果它的队列长度是12个分组，那么这些分组将在12/3=4 s内发送完毕.在本文的算法中，Φji(S0)=Wji(S0)=12/4=3package/s，如果受带宽等因素的影响，在第1 s只能分配给此次会话1个分组的带宽，那么当信道质量恢复良好时，需要对此次会话做一些相应的补偿措施，因此在这种情况下，Wji(St)=3+2/3=11/3package/s，即为了保证此次会话的时延，需要分配更多的带宽给它.

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

长期公平性 假设信道繁忙时，某一个会话暂时没有机会获得调度，但是一旦信道质量良好，并且此次会话无差错，那么它将获取原先在信道质量差的错误状态下“丢失”的所有服务.系统中任意一个活跃的无错用户均可以在一定的时间门限内获得有保证的服务时间，提供长期公平保证.

短期公平性 对每个数据流都有一个随时间变化的共享服务.当信道状态变差时，该会话的共享服务随之增加.这种变化是有范围界定的，算法采用传统分组公平排队调度PFQ法来提供严格的延迟边界，用赋予每个数据流的动态的时变公平共享因子来适应不同数据流的QoS需要，在系统输出和公平性方面得到了良好的折中.短期公平依据传统分组公平排队调度PFQ算法中公平性.相同状态下收到相同数量归一化服务的会话需求包括:①活跃会话在奖励期间需要得到相同归一化数量的惩罚;②奖励服务需要依据落后会话的速率按比例分配;③当错误会话的服务可用，落后会话以相同归一化速率获得这些服务，落后会话同样如此.

最大化信道吞吐量 本文的模型将信道带宽分配给具有良好信道质量的会话，即带宽使用率为100%，没有数据包丢失，因此信道吞吐量将一直能够达到最大.

3 证明

引理1 无差错会话的落后序列长度小于Lmax，其中Lmax表示信息的最大长度.

证明 归纳法.从算法可见，无差错的落后会话i在以下几种情况下会发生变化:①会话i状态变活跃;②会话i被选中的同时，另一个超前会话j也被选中，并接受服务;③会话i从另一个会话j上得到服务.

1)基本步骤 当一个无差错会话i状态变活跃时，它的落后序列被设置成0，引理正确.

2)归纳步骤 假设lagi≤Lmax，考虑2种情况:①lagi＜0;②0≤lagi≤Lmax.在情况①中，由于会话i处于活跃状态，只有当另一个会话j获得服务时，它的落后序列长度增加，这时有

式中，Lkj代表会话j队列头部的分组长度.在情况②中，会话i不是活跃的，因此落后序列长度只能减少.

证毕.

定理1 规范化服务之间的差异收到任何两会话i和j的时间间隔［t1，t2)，其中2次会话不断累积，无差错，而且他们的状态没有变化是有界定的.

假设考虑2种情况:在任意时间间隔［t1，t2)内，2个会话同时都是落后状态，或者同时都是活跃状态.

证明 假设在任意时间间隔［t1，t2)内，2个会话同时都是落后状态.这种情况下，2个会话有可能都被选中接受服务，或者从另一个活跃会话接受奖励.无错的落后会话在任意时间间隔［t1，t2)内接受的服务总数遵循以下不等式:

当在任意时间间隔［t1，t2)内，2个会话同时都是活跃状态，可得αi－βj≤(E－di－dj)((di－dj)/(di+dj))，其中α，β表示2个活跃会话的比例，E表示信道容量，假设di＞dj.

证明 假设在时刻t，2个会话都处于活跃状态.并且假设在时刻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)内，αi－βj≤(E－di－dj)((di－dj)/(di+dj))(t2－t1)成立.

定理1说明了在任何时间间隔内2个活动的无差错的归一化会话在同一状态上是有严格界定的(例如活跃或滞后是有界定的，从而保证短期的公平性.

定理2 如果在时刻t之后，落后会话i在处于无错状态，当会话i不断请求服务时，那么必须保证它在最多Δ个单位时间后接受服务，其中

式中，L0是t=0时刻的分组长度;d0是t=0时刻的时延门限.

定理2证明了算法的长期公平性.

证明 通过算法的伪代码，可得:

4 仿真实验

4.1 服务定义

本文定义n(n=4)种能被信道接收的服务，以及每个服务的时延门限，如表1所示.

表1 服务定义

4.2 会话产生器

使用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;

}

其中，数组S表示会话ID(0～3)，数组L表示每一个服务(1～100)的会话长度，结果如表2所示.

表2 数组定义

从表2中可以看出系统在同一时刻产生4组会话，例如，会话［0］的ID为3，代表它是HTTP服务，会话长度为84个分组，由于HTTP服务的时延门限是5package/s，因此为了保证服务质量，必须保证此次会话在［84/5］=17 s中被接收.

4.3 白噪声产生器

本文只关注调度算法本身，而不是物理信道.使用高斯随机变量生成器生成信道噪声.稍后将介绍更复杂的信道模型.以下用C++代码模拟信道条件(C++高斯噪声产生器).

/*每秒钟产生符合高斯分布的白噪声*/

#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;

}

该算法生成符合高斯分布的随机数，其中均值为0，方差为1(标准高斯分布)，随机数映射范围在－1～1之间，并且在0点上取得最大值.变量q代表精度，通常效果最好的参数设置是q=15，则2个随机数间的最短距离是1/(2qdiv 3)=1/10922.代码中的“sleep(1)”是用来模拟每秒钟每一次会话的信道条件，如果值大于0，说明本次会话的信道条件良好，反之，如果值不大于0，则说明本次会话的信道条较差.表3列出连续10 s模拟信道情况.

表3 连续10 s模拟信道情况

4.4 仿真结果

在经过第2步会话产生器、第3步白噪声产生器的基础上，得到仿真结果，如表4所示.下一节将分析如何得到这些结果，以及如何满足时延、公平性、吞吐量3方面的性能.

表4 连续10 s的仿真结果

在表4中，α表示在时刻t分配给会话的带宽，β表示在在时刻t还剩下多少数据包，τ表示维持本次会话的剩余时间，σ表示在时刻t有多少超前(+)或滞后(－)的数据包.

信道容量:E=27 package，假设4个会话长度分别为3，1，2，2，那么5+20+1+1=27 package，如果信道质量良好，27 package是信道容量的下界，可以满足4个会话的时延门限.

4.5 结果分析

时延 从表4中可以看出，本文的算法能够很好地处理每一个会话的时延门限，例如，会话1在时刻1结束，会话2在时刻8结束，会话3在时刻4结束.虽然会话0在以上连续10 s内并未结束(还剩余35 package)，但在剩下的时间内，如果会话0的信道条件良好，那么会话0可以占用整个带宽来顺利通信.

长期公平性 由于每个会话最终都可以在时刻i结束，这意味着经过足够长网络繁忙时间，如果此次会话无差错，那么一旦有足够的服务需求，它将获取原先在错误状态下“丢失”的所有服务.

短期公平性 由表4可知，在时刻0上只有会话0和会话2拥有良好的信道条件，为了处理时延，首先给会话0分配5个数据包，给会话2分配1个数据包，由于整个信道容量是27个数据包，因此还可以分配容量27－5－1=21 package，根据时延处理规则，将给会话0分配5+［21×5/6］=22 package，给会话2分配1+［21×1/6］=5 package，此结果与第3节的证明:在时刻t上，αi－βj≤(E－di－dj)((di－dj)/(di+dj))的结论相一致.

吞吐量 在单位时间内，对于信道状态良好的会话，将分配尽可能多的带宽，这样不仅能够处理时延，而且可以获得单位时间内的最大吞吐量，例如表4中的时刻0(24+3=27)，但最坏的情况是所有会话的信道状态都很差，如表4中的时刻2所示.

5 结语

本文提出了一种用于无线网络中的分组调度算法，该算法不仅能够满足用户公平性的要求，而且能够处理多种服务中的突发情况.算法综合考虑信道条件，确保在单位时间内单个信道获取最大吞吐量，同时考虑长期公平性以及短期公平性，使得整体吞吐量达到最大.在后续工作中将进一步细化信道情况，基于复杂信道情况的分组调度算法有待进一步研究.

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.