一种改进的M-LWDF 动态业务调度方法

刘海客，李集林，张华健

（北京卫星信息工程研究所 北京 100086）

一种改进的M-LWDF 动态业务调度方法

刘海客，李集林，张华健

（北京卫星信息工程研究所 北京 100086）

随着地面无线通信技术的高速发展，无线通信网络将承载越来越多的高速多媒体业务，为使用户获得良好的业务体验，需要为其提供灵活可靠的服务质量保障。高速业务流的调度方法作为系统QoS保障的重要一环。传统业务调度方法有的仅考虑业务流的绝对优先级、有的依据业务包等待时延的长短进行调度，这些方法缺乏随信道质量及吞吐量变化情况的动态调控能力。针对上述问题，提出一种改进型的M-LWDF动态调度方法，通过引入公平性参数与优先级参数，提升业务调度器的性能。通过仿真验证，改进后的动态调度方法可以使业务流获得更好的时延及抖动指标。

无线通信网络；M-LWDF；业务调度算法；实时性业务；公平性

目前地面宽带无线通信系统发展迅猛，多媒体应用已全面接入无线网络中，无线通信网络承载高速业务流的种类将更为繁多。随着系统中新增业务提供不断增加，用户对业务体验的要求也子不断提升。因此需要在宽带无线通信网络中，为用户提供良好的服务质量保障功能，针对不同的业务特性，提供不同的QoS保障策略，在用户无感知的情况下，提升用户的业务体验。

在无线通信系统中，业务由有线传输到无线发射间的业务调度功能对业务流的延迟、吞吐量、抖动等QoS指标具有较大的影响，因此好的业务流调度器及调度算法将更好的保障业务流的QoS要求[1-2]。传统调度算法一般采用严格优先级调度或加权公平调度等方法，但是该方法在调度的过程中缺乏一种动态调控的功能，不能根据信道质量的变化情况及吞吐量的最低保障要求，在每次调度周期对调度优先级进行有效的调整[3-4]。这种缺乏动态变化的业务调度策略并不能较好的满足当前网络中多媒体业务爆炸式增长的现状。

因此在宽带无线通信系统的业务调度算法中需引入业务流之间的公平性与差异性调控指标，进而更好的完成高速多媒体业务的调度发送功能。

1　无线高速业务动态调度算法

在当前星状网络拓扑结构的宽带无线通信系统中，系统承载越来越多的高速多媒体业务流，因此中心站到终端站下行业务以及终端站到中心站上行业务的调度算法性能是保障系统业务服务质量的重要环节[5-6]。

由于宽带无线通信系统主要承载语音、视频、游戏、上网等多媒体业务，在中心站与终端站中需各实现一个多业务流的调度器结构，并在此调度器结构的基础上依据设计的调度算法完成业务流调度发送。处于MAC层与IP层之间的业务调度器，其功能是以一定的算法将不同队列中的业务数据包调度至MAC层中的调度缓冲区中等待发送。业务调度器依照调度算法与系统预设的QoS参数为业务提供调度服务。

1.1业务调度器

在中心站与终端站之间传输的数据包括：信令、实时性业务流与非实时性业务流。信令数据应在系统中接受可靠保障，实时性业务流应接受优先保障，而非实时性业务则应接受尽力而为的服务质量保障[7]。为在系统中针对不同类型的数据流提供不同的服务质量保障级别，在业务调度器中建立两种属性的QoS队列：专用队列和默认队列。专用队列主要用来承载系统中的实时性业务流，如语音、视频等实时流或缓冲流。默认队列主要分为两种，一种为专门承载系统信令数据的队列，可称之为信令默认队列，一种为承载非实时性业务流的队列，可称为业务默认队列。

根据系统所承载业务的QoS保障要求，在中心站与终端站中建立多个专用队列和业务默认队列，完成系统对实时性业务及非实时性业务的QoS保障及调度发送功能。同时建立一个承载系统信令数据的信令默认队列，以完成信令数据的周期性发送功能。由专用队列与默认队列组成的业务调度器采用多级调度的策略。中心站与终端站业务调度器结构如图1和图2所示。

图1　中心站业务调度器结构

图2　终端站业务调度器结构

对于承载实时性业务的各种专用队列，采用实时性调度算法将其中的数据包调度至调度缓冲区中的缓冲队列中，等待发送。而对于承载系统信令的信令默认承载，采取周期性插入到调度缓冲队列的调度策略。对业务默认队列采用优先级调度策略，由于其承载非实时性业务，所以将业务默认队列的优先级置为最低，即当实时性业务专用队列为空时，若有空闲的资源则对其进行调度。

中心站的业务调度器与终端站有所不同，由于中心站采用广播式的方式向所有终端站发送业务数据，因此在调度器中针对非实时性业务引入终端优先级的概念，即发往不同终端的非实时性业务应按优先级接收调度。

具体调度过程如下：首先，通过实时性调度算法计算所有专用队列的调度优先级，按照优先级次序将各个专用队列中的分组调度至缓冲区队列中，同时周期性向缓冲区队列中插入信令默认队列中的信令数据。一次调度周期T中，在无线资源未被所有专用队列占满的情况下，调度业务默认队列中的非实时性业务。

1.2改进的M-LWDF算法

在宽带无线通信系统中，对于实时性业务的调度算法性能将直接关系到系统QoS保障的效果，尤其是当前无线通信系统承载种类繁多的高速多媒体业务流。根据上节所述的业务调度器结构，本节提出一种改进的M-LWDF算法，该算法在调度实时性业务时，将综合考虑业务流本身的QoS属性要求与当前信道质量情况。

M-LWDF算法是针对无线高速业务流提出的，其主要思想是将分组包的时延和如何有效利用信道信息平衡考虑，其用户优先级的计算不仅和用户当前的信道质量有关，还和数据包的队列时延有关[8-9]。

对于M-LWDF分组调度算法，分组队列调度优先级函数表示为：

其中，i和j分别表示用户和业务类型；Pi，j（t）表示用户i 的j类业务分组队列在调度时刻t得到的调度优先级；Rj表示业务j所支持的最大比特速率，其值越高，那么用户的优先级就越高；r~i，j（t）为用户i的j类业务在调度周期内所获得的平均数据率；wi，j（t）为t时刻用户i的j类业务分组队列列首的等待时间；Tj和δj分别表示j类业务分组的传输时延和丢包率界限。当分组在队列中的等待时延超过Tj，分组就被丢掉，因此时延限制越大，分组包丢弃的概率就越小。在每个调度周期中将会调度优先级最高的用户i的j类业务。

M-LWDF算法是一种非公平算法，对于那些由于信道质量下降引起的吞吐量下降的业务流，该算法会造成这类业务的数据包在中心站或终端站侧有较大的时延，当时延超过用户的最大容忍时间时就会被抛弃，进而使得该业务流不能满足系统预设的QoS保障要求，影响用户的业务体验[10-11]。为了降低数据业务流包被丢弃的概率，在中心站侧需要对信道条件差的用户进行补偿。基于用户公平性，在保证用户分组最小吞吐量的条件下最大化实时业务的用户数。

同时，宽带无线通信系统承载多种多样的多媒体业务流，为了在业务调度的过程中体现不同业务流QoS保障要求的差异性，需要在调度算法中引入QoS标识参数，使具有较高QoS标识优先级的业务获得更高的调度优先级。假如系统中承载语音、实时视频、缓冲视频等业务流，设定语音业务流优先级大于实时视频流大于缓冲视频流，则可规定3种业务流的QoS标识分别为1、2、3，因此可以看出，标识数值越大，业务流优先级越低。

针对上述分析，宽带无线通信系统的业务调度算法需综合考虑系统的公平性与特定业务流的QoS保障要求。

在M-LWDF算法中引入Q参数与W参数。Q参数用来表示QoS标识，W参数表示吞吐量参数。调度规则为：

其中，Q=qi，j，

qi，j为QoS标识，D为预先定义的用户最小吞吐量，ci为用户平均吞吐量的估计，考虑到用户的公平性，对信道条件好的用户限制其优先级，使信道条件差的用户可以得到服务。

算法不仅考虑到信道条件和用户时延的影响，还考虑到了用户最小吞吐量保证。对于平均吞吐量开始低于最小吞吐量的用户，通过一个W权值参数来提高低吞吐量用户的优先级，增加了系统中用户之间的公平性。

同时通过引入Q参数，使算法在保证实时性业务分组时延的同时，兼顾QoS标识优先级，并在一定程度上控制了QoS标识对调度判决的影响。

Q参数与W参数可被分别称为优先级参数与公平性参数，两者组成的函数采用指数形式，该函数具有非负性，并保持单调递增趋势，这种设计方式可以保障被调度业务流吞吐量的平稳性。这种调度算法在调度判决中为高QoS标识的业务数据包提供更多的调度机会，从而适应端到端QoS保障的需求，满足不同业务数据流对QoS标识优先等级的差异化需求。

可证明采用下列判决表达式的一类调度算法的稳定性：

其中fi，j（·）为非负、无界递增函数。只要所有的业务分组到达速率之和不超过系统的容量范围[12-13]。依据该判决表达式设计出的调度算法可保障系统业务流吞吐量最优，因此文中所提的改进型M-LWDF算法具有算法稳定性。

2　算法仿真

为验证改进型的M-LWDF算法的优越性，在matlab中对改进型M-LWDF算法进行仿真，对比改进前后两种算法对高速实时性业务数据包的调度延时，并比较两种算法的优劣性。

在业务建模中建立3种实时性业务流队列，其中一种用于模拟聚合话音业务，另两种为普通视频流业务，在3种业务中将聚合话音业务的QoS标识设置为1，则该业务被映射成为最高优先级。在通信系统中，通常认为话音业务是固定比特速率业务，当通话处在已连接状态时，可以认为其占用的带宽是近似不变的。为模拟3种业务信道质量的不同，将聚合话音业务的传输速率设置为最低，由此可以模拟承载此业务的无线信道在资源不足情况下，改进型M-LWDF算法对此业务的补偿能力。

当大量用户进行话音业务的连接和挂断的操作时，此类聚合的话音业务流按统计信息来描述可表示为：用户业务到达服从泊松分布，通话服务时间间隔服从负指数分布[14-15]。

假设话音业务到达率为λp，均值为μv，则话音业务的到达时间和服务时间可由公式（4）和公式（5）得到。

话音业务可采用马尔科夫On/Off模型，如图3所示，从On状态向Off状态转换的速率为μ，从Off状态向On状态的转换速率为λ，用户处于On状态和Off状态的时间分别服从均值为μon和μoff的指数分布，那么话音业务的激活因子为：av=μon/（μon＋μoff）。因此话音业务的平均传输速率为avRv，Rv表示语音业务在网络中传输速率[16-18]。

图3　聚合流话音业务模型

图4和图5为M-LWDF算法与改进型M-LWDF算法在业务数据包时延方面的比较图。其中横坐标为流入话音队列中的数据分组个数，纵坐标为第n个数据分组进入队列的时间与调出队列时间的差值，也就是聚合话音业务等待调度的时延参数。图4为使用M-LWDF算法时每个聚合话音分组的调度时延，图5为使用改进型M-LWDF算法时的调度时延。在系统中模拟较大的链路延迟以及丢包情况，用来构造较低信道质量的场景。从图中可以看出改进型的M-LWDF平均时延小于原算法的平均延时，即使在聚合语音业务所在信道质量较低的情况下，也可以较好地保障其服务质量，在降低平均延时的同时其延时抖动也有较大改善。

图4　M-LWDF算法业务分组调度时延

图6为聚合话音业务队列分组的平均延时，图中纵坐标为每个分组的延时累加/业务分组个数。从图中可以看出改进型的M-LWDF算法可使聚合话音业务的分组平均延时降低，故性能好于M-LWDF算法。

图5　改进型M-LWDF算法业务分组调度时延

图6　两种算法业务平均时延对比图

3　结束语

文中根据无线通信系统业务承载发展情况，提出了一种基于专用队列和默认队列的上下行业务调度器结构，针对不同队列采用不同的调度策略。同时为更好的保障实时性业务的服务质量，提出了一种改进型的实时队列调度算法，在MLWDF算法中引入优先级参数与公平性参数，使得业务发送调度既可满足业务流的QoS保障要求，又可对信道质量的变化情况进行响应，提升系统中用户的业务体验，并通过matlab仿真验证其合理性与优越性。

[1]仉娟娟，杨丰瑞.HSDPA中M-LWDF实时业务分组调度算法的改进[J].无线电工程，2009，39:11-13.

[2]XIAN Yong-ju，TIAN Feng-chun.Analysis of M-LWDF fairness and an enhanced M-LWDF packet scheduling mechanism[J].Journal of China Universities of Posts&Telecommunications，2011，18（4）:82-88.

[3]胡永东，吴国新，徐逸卿.M-WiMAX中马尔可夫预测的MLWDF调度算法研究[J].计算机科学，2014，4（4）:31-35.

[4]Hu L，Ning C，Mao M.Research and simulation on wireless packet scheduling scheme based on High-Speed packet access network[J].Open Mechanical Engineering Journal， 2014，8（1）:92-95.

[5]解冰.未来无线通信系统面向QoS保障的资源分配研究[D].北京邮电大学，2011.

[6]Foronda A，Ohta C，Tamaki H.Scheduling algorithm to provide QoS over a shared wireless link[J].Ieice Trans Commun，2009，92（6）:2160-2167.

[7]Xu C，Xian Y.An enhanced M-LWDF packet scheduling algorithm[M].Recent Advances in Computer Science and Information Engineering.Springer Berlin Heidelberg，2012: 333-338.

[8]Lee J Y，Sorour S，Valaee S，et al.Dynamic parameter adaptation for M-LWDF/M-LWWF scheduling[J].IEEE Transactions on Wireless Communications，2012，11（3）:927-937.

[9]杨鹏，闫俊杰，王汝言.LTE中队列状态感知的优化MLWDF调度算法[J].重庆邮电大学学报；自然科学版，2015.

[10]Khan N，Martini M G，Staehle D.QoS-aware composite scheduling using fuzzy proactive and reactive controllers[J]. Eurasip Journal on Wireless Communications&Networking，2014，2014（12）:1189-1200.

[11]Afroz F，Barua S，Sandrasegaran K.Performance Analysis of FLS，EXP，LOG and M-LWDF packet scheduling algorithms in downlink 3GPP LTE System[J].International Journal of Wireless&Mobile Networks，2014，6（5）:77-91.

[12]Alghamdi M，Alghamdi M.Performance comparison of downlink packet scheduling algorithms in LET Network[J]. International Conference on Electrical Engineering Computer Science&Informatics，2014.

[13]姚丹，崔维嘉，季仲梅.基于QCI优先级的分组调度算法[J].计算机工程，2011（9）:141-143.

[14]冯星华，李艳慧.典型话务模型的呼叫中心系统资源计算算法[J].邮电设计技术，2014（6）:76-79.

[15]Sung D H，Park H H，Chung J H，et al.Method for transmitting VoIP packet:WO，US8391311 B2[P].2013.

[16]Ivan R J D S V，Kleinschmidt J H.Capture and analysis of malicious traffic in VoIP environments using a low interaction honeypot[J].Latin America Transactions IEEE，2015，13.

[17]代家强，孙智卿.基于无线网络技术的智能家居能量管理系统开发及需求侧管理应用研究[J].陕西电力，2013 （10）：39-43.

[18]牛博，姚林，曹小行，等.基于3G物联网的高压输电线路多状态信息监测系统[J].陕西电力，2013（12）：56-60，70.

An improved M-LWDF dynamic traffic scheduling method

LIU Hai-ke，LI Ji-lin，ZHANG Hua-jian
（Beijing Institute of Satellite Information Engineering，Beijing 100086，China）

With the rapid development of wireless communication technology，wireless communication network will carry more and more high-speed multimedia services.It requires a flexible and reliable QoS function to provide users with a good service experience.The scheduling method of high speed traffic flow is an important part of QoS system.The traditional traffic schedule algorithms only consider the absolute priority of the traffic flows，or the waiting time before the packets scheduled. These methods lack the ability of dynamic regulation with the change of channel quality and traffic throughput.In view of the above problems，an improved M-LWDF dynamic scheduling method is proposed.By introducing the fairness parameter and priority parameter，improve the performance of the traffic scheduler.The simulation results show that the improved dynamic scheduling method can make the traffic flows get better delay and jitter index.

wireless communication network；M-LWDF；traffic scheduling algorithm；real-time traffic；fairness

TN915.41

A

1674－6236（2016）22-0026-04

2015-11-18稿件编号：201511166

刘海客（1986—），男，河北秦皇岛人，博士研究生。研究方向：计算机网络、SDN网络。