IEEE802.16网络动态自适应区分服务算法

蒋文贤，许晓璐

（华侨大学计算机科学与技术学院，福建厦门361021）

IEEE802.16网络动态自适应区分服务算法

蒋文贤，许晓璐

（华侨大学计算机科学与技术学院，福建厦门361021）

针对IEEE802.16MAC协议中的调度机制不能提供流媒体业务区分服务的问题，提出了一种基于服务类别优先级的链路带宽自适应分配调度PDA⁃DFPQ算法。该算法分为两级调度架构，第一级是不同业务间的调度，采用服务质量优先级策略，高优先级服务类分配合适的带宽，以保障实时业务对最大时延限定的要求；第二级是同种业务内的调度，采用自适应调整机制，根据队列长度和分组数动态设置权值系数，以保障不同用户对公平性和非实时业务对吞吐量的要求。仿真结果表明：与DRR和RED⁃DFPQ算法相比较，改进的一级调度算法能降低时延，解决实时性问题；改进的二级调度算法能均衡用户速率，提高网络吞吐量和公平性，解决突发性问题。

无线网络；IEEE802.16；带宽调度；自适应；区分服务

IEEE802.16［1］MAC（media access control，MAC）协议提供了主动授予服务（unsolicited grant service，UGS）、实时轮询服务（real⁃time polling service，rtPS）、拓展实时轮询服务（extended real⁃time polling service，ertPS）、非实时轮询服务（non⁃real⁃time polling Service，nrtPS）和尽力而为服务（best effort，BE）等5种不同服务类型的服务质量（quality of service，QoS），但没有提出保障QoS的具体实现方案和区分服务算法，而有效的上行链路和下行链路带宽调度算法对QoS的保证具有重要意义。

文献［2］提出了一种二级调度机制，第一级调度使用亏空公平优先级队列（deficit fair priority queue，DFPQ）算法。该算法定义了亏空计数器（deficit counter，DC），一旦某队列的首个分组长度大于DC值就终止对该队列的服务；而不同的业务在第二级调度中使用各自的调度算法；文献［3］提出了基于随机早期检测（random early detection，RED）的DPFQ算法，针对高优先级业务负载较高时无法保证低优先级业务的QoS问题对DFPQ算法进行改进，设计了动态变化的DC值；文献［4］为保证各种多媒体QoS，提出了一种基于正交频分多址接入技术和自适应调制编码机制的二级调度方案；文献［5］提出了一种移动IEEE802.16的跨层主动队列管理方案，利用传输层的窗口变化信息，改善上行终端的丢弃率等特性，提高了上行链路的性能；文献［6］提出一种基于传输速率自适应的动态分配算法，并采用一个动态优化的迭代算法自适应调节用户的传输速率来得到最优的带宽重分配矩阵，以此最大化无线网络的效用函数；文献［7］提出一个基于学习自动机的IEEE802.16上行链路的实时多媒体业务调度算法；文献［8］提出了一种用于移动IEEE802.16上行链路流量的高效带宽分配算法，使用智能系统方法，设计了自适应的基于期限的方案，为实时应用保证特定的最大时延要求；文献［9］从数据调度竞争的角度出发，提出了一种节能的实时业务数据调度算法；文献［10］提出了效用最大化的IEEE802.16带宽分配算法和快速解法，可灵活地改变效用函数参数，在不同服务质量要求下高效地做出分配。以上算法虽然在某些方面提高了性能，但没有较好解决时延、吞吐量和公平性之间的平衡。

根据现有文献对IEEE802.16调度机制的研究，针对其不能提供流媒体业务区分服务的问题，将分层设计和自适应控制的思想引入到QoS调度机制中，提出了一种基于服务类别优先级的链路带宽自适应分配调度算法PDA⁃DFPQ。

1 调度服务算法

该算法分为两级调度架构，第一级是不同业务间的调度，采用服务质量优先级策略，高优先级服务类分配合适的带宽，以保障实时业务对最大时延限定的要求，解决实时性问题；第二级是同种业务内的调度，采用自适应调整机制，根据队列长度和分组数动态设置权值系数，以保障不同用户对公平性和非实时业务对吞吐量的要求，解决突发性问题。总体调度框架图如图1所示。

图1 IEEE802.16总体调度框架设计图Fig.1 IEEE802.16 overall scheduling framework design

1.1 基于优先级策略的第一级调度设计

第一级调度也称为类间调度，是指各种不同类型的业务流所在队列的调度服务。用户站（subscribe sta⁃tion，SS）到基站（base station，BS）的连接将分配一种服务类型，BS针对每 个服务类别都建立与之相应的调度队列，每个队列有一组与之相关联的各自不同的QoS需求参数。

由于UGS服务类型的分组是以恒定速率和固定大小进行传输的，在IEEE802.16系统中，BS以主动授权方式为其分配带宽，因而UGS业务无需进入第一级调度。余下rtPS、ertPS、nrtPS和BE4种类型业务进入第一级调度，采用服务类型优先级算法。同类分组具备相同的QoS要求，队头分组的QoS优先级函数值大小决定分组的顺序，取值最大的分组将获得优先调度的权利。如图2所示。

图2 链路带宽分配过程Fig.2 The link bandwidth allocation process

1.2 基于动态自适应的第二级调度设计

第二级调度也称为类内调度，指各个相同类型的业务流间的调度。在IEEE802.16中提供QoS的基本思想：将带有某个特定连接标识符（connection identifi⁃er，CID）标识的服务流，与来自MAC层接口的分组数据相关联。如图3所示。

1）UGS业务。

为有效保障UGS各业务流间的公平性，采用先进先出（first in first out，FIFO）方式，同时满足了业务流对时延、速率等方面的要求，而不受到其他条件的制约。

2）rtPS和ertPS业务。

rtPS及ertPS业务流均属于可变大小且大小不固定的分组，若分组时延超过一定要求会被丢弃，进而影响到用户的感知，因此必须保证这2类业务的时延要求，这里选用基于改进的PDA⁃DFPQ算法。

3）nrtPS业务。

nrtPS业务支持非实时且不定期的大小可变的分组，时延上是没有明确限制，但对最大持续传输速率、最小预留业务速率有要求，采用加权轮询（weighted round robin，WRR）算法进行调度，通过权重系数设定业务队列服务时间，高优先级队列具有优先权。加权值表示获取资源的比重，权重采用的公式：Wi＝其中pi为优先级参数折算后的系数，ri为带宽速率的差值。

4）BE业务。

对于BE业务，由于没有对QoS严格的要求，考虑到多用户间BE业务流的公平性，因此采用轮询（round robin，RR）调度算法，为每个BE流提供相同的机会传输分组，即每次调度执行i＝（i+1）mod n，并选出第i用户进行调度。

2 仿真与分析

2.1 实验参数设置

系统是基于单个BS，在TDMA访问模式下使用点对多点（point to multipoint，PMP）方式执行，多个SS终端随机分布在3 km半径范围内，部署3台服务器，其中流媒体服务器主要是处理rtPS和ertPS业务、FTP服务器主要是处理nrtPS业务、Web服务器主要是处理BE业务，仿真的网络拓扑结构如图4所示。

算法仿真在OPNET环境中实现，参数设置主要包括Config模块、Application模块和Profiles模块，由于IEEE802.16网络业务流具有自相似特性，利用Pareto ON／OFF仿真业务源，到达率为λ，ON期间服从Pareto分布，OFF期间服从泊松分布。

2.2 第一级调度仿真

对提出的PDA⁃DFPQ算法和传统的亏空轮询（defi⁃cit round robin，DRR）算法和RED⁃DFPQ算法在平均时延的性能进行对比；对5种业务进行仿真，SS数量从5个逐步增加到50个，仿真结果如图5和图6所示。图5显示了3种调度算法在不同SS数量下的平均队列时延。其中PDA⁃DFPQ算法的时延最小，主要是其服务类别优先级最高，减少了数据包队列时延，因此，实时流量可在规定的时延约束下完成。而且随着SS数目的增加，PDA⁃DFPQ中队列时延的曲线变得平缓，这表明可满足不同时延的要求，算法趋于平稳。每个服务类别队列获取了合适的带宽，使每个请求在其时限约束内都可达到所需的数据，可以认为实现了调度算法中的公平性。而DRR和RED⁃DFPQ在SS数量较多时，平均队列时延急剧增长，原因是简单对各种业务的轮循或加权轮循，未考虑每个队列的实际带宽请求。

图3 调度算法流程图Fig.3 Scheduling algorithm flow chart

图4 网络拓扑结构Fig.4 Typical network topology

图5 队列平均时延对比Fig.5 Comparion of queue average delay

图6 显示了PDA⁃DFPQ实现的各种服务类别的平均时延。

图6 服务类别平均时延Fig.6 The average delay in service classes

可以看出UGS服务类别的时延最小，这是因为调度算法除了给UGS固定带宽，还授予更高的权限。相比之下，当SS的数量增加时，BE和nrtPS数据包经历的时延增加了，这是因为较多帧时隙去满足rtPS等实时流量需要。但BE业务时延也有一定的期限保障，这是因为调度算法也为非实时应用保证了最小的预留速率。另一方面，ertPS和rtPS数据包时延相对较小，主要是PDA⁃DFPQ可以维持最大时延，为其相应的服务请求区分保证公平性。

2.3 第二级调度仿真

第二级调度方案主要对rtPS业务和BE业务进行仿真，其中rtPS代表了实时流量，BE优先级最低。

图7和图8分别对比了3种调度算法在rtPS和BE业务这2种服务类别吞吐量。很显然，用于rtPS业务的吞吐量比BE高，因为调度算法的优先级是给实时业务的，分配更多的带宽给rtPS流。相应地，rtPS业务的时延也较小。

图7 服务类别平均时延Fig.7 The average delay in service classes

图8 服务类别平均时延Fig.8 The average delay in service classes

虽然BE业务的时延受到一定的影响，但仍在可以接受的范围内。PDA⁃DFPQ算法下的rtPS业务吞吐量总体高于DRR和RED⁃DFPQ算法下的吞吐量，这是因为PDA⁃DFPQ算法采用自适应调整机制，动态分配不同的权值系数，允许长度更大的分组得到更高的服务机会，网络中传输的分组数量较多，更好地保障了分组调度情况；而对比DRR、RED⁃DFPQ算法，PDA⁃DF⁃PQ算法中BE的吞吐量保持在特定最小预留速率下，这是因为PDA⁃DFPQ赋予了rtPS队列足够的带宽，使得当rtPS在其时限到期前，有足够的时间让调度算法能够优先服务BE业务。

图9显示了PDA⁃DFPQ、RED⁃DFPQ和DRR公平性的对比。可以看出，DRR公平性随着流量负载的增加而恶化，因为它为实时业务赋予了高优先级，当实时业务SS连接时，非实时业务则趋向于饿死。另一方面，当系统负载低于30个SS时，DRR显示出公平性方面的稳定，这是因为它为实时业务采用了额外的队列。但当系统负载超过40个SS时，这些额外的队列为非实时业务而得不到带宽。这是因为非实时业务进行很长时间，而DC没有服务完实时服务类别的队列。相比之下，即使当SS为50个时，PDA⁃DFPQ的公平性也比RED⁃DFPQ和DRR要好。

图9 服务类别平均时延Fig.9 The average delay in service classes

因此，可以得出，在可接受范围内牺牲非实时业务的吞吐量性能以换取实时业务的吞吐量优化，更好地保证了实时业务的QoS要求。

3 结束语

针对IEEE802.16中MAC协议的调度机制不能提供流媒体业务区分服务的问题，引入分层设计和自适应控制的思想，提出了一种基于服务类别优先级链路带宽自适应分配调度算法，仿真结果表明该算法不仅能降低时延，保障实时业务的要求，而且能均衡各类型业务性能，提高网络吞吐量和公平性，具有较强的网络自适应能力。在后续的工作中，将考虑不同路由策略下的无线网络QoS性能，从而增强算法的普适性。

［1］PITIC R，SERRELLI F，REDANA S，et al.Performance e⁃valuation of utility⁃based scheduling schemes with QoS guar⁃antees in IEEE 802.16／WiMAX systems［J］.Wireless Com⁃munications and Mobile Computing，2010，10（7）：912⁃931.

［2］SAFA H，ARTAIL H，KARAM M，et al.New scheduling architecture for IEEE802.16 wireless metropolitan area net⁃work［C］／／Computer Systems and Applications，（AICCSA' 07.IEEE／ACS International Conference）.［S.l.］，2007：203⁃210.

［3］TING P C，YU C Y，CHILAMKURTI N，et al.A proposed RED⁃based scheduling scheme for QoS in WiMAX networks［C］／／Wireless Pervasive Computing，（ISWPC 2009.4th International Symposium）.［S.l.］，2009：1⁃5.

［4］陈婷，李建东，钟绍波等.一种面向公平保证QoS的WiMAX二级调度方案［J］.计算机研究与发展，2009，46（7）：1094⁃1101.

CHEN Ting，LI Jiandong，ZHONG Shaobo，et al.A fair⁃ori⁃ented two⁃level scheduling scheme for QoS guarantee in WiMAX［J］.Journal of Computer Research and Develop⁃ment，2009，46（7）：1094⁃1101.

［5］SADRI Y，KHANMOHAMMADI S.A QoS aware dynamic scheduling scheme using fuzzy inference system for IEEE 802.16 networks［J］.Wireless Personal Communications，2013，72（4）：2107⁃2125.

［6］陈赓，夏玮玮，沈连丰.基于传输速率自适应的动态带宽分配算法［J］.通信学报，2014，35（5）：25⁃32.

CHEN Geng，XIA Weiwei，SHEN Lianfeng.Dynamic band⁃width allocation algorithm based on transmission rate adapta⁃tion［J］.Journal on Communications，2014，35（5）：25⁃32.

［7］MISRA S，BANERJEE B，WOLFINGER B E.A learning automata⁃based uplink scheduler for supporting real⁃time multimedia interactive traffic in IEEE802.16 WiMAX net⁃works［J］.Computer Communications，2012，35（15）：1871⁃1881.

［8］ALSAHAG A M，ALI B M，NOORDIN N K，et al.Fair up⁃link bandwidth allocation and latency guarantee for mobile WiMAX using fuzzy adaptive deficit round robin［J］.Journal of Network and Computer Applications，2014，39（3）：17⁃25.

［9］IYENGAR R，SIKDAR B.A queueing model for polled serv⁃ice in WiMAX／IEEE802.16 networks［J］.IEEE Transac⁃tions on Communications，2012，60（7）：1777⁃1781.

［10］聂伟.WiMAX无线网络QoS测量及优化研究［D］.成都：电子科技大学，2011：101⁃112.

NIE Wei.Research on QoS measurement and optimization in WiMAX wireless communication networks［D］.Cheng⁃du：University of Electronic Science and Technology of Chi⁃na，2011：101⁃112.

Algorithm for IEEE802.16 network dynamic adaptive differentiated services

JIANG Wenxian，XU Xiaolu
（College of Computer Science and Technology，Huaqiao University，Xiamen 361021，China）

Considering that IEEE802.16 MAC protocol scheduling mechanism cannot provide streaming media traffic of differentiated services，a link bandwidth adaptive allocation scheduling algorithm based on service class priority and PDA⁃DFPQ is proposed.The first level is scheduling between different services，using the priority strategy for quality of service，which allocates proper bandwidth for high service class，so as to ensure real⁃time services to the maximum delay limit requirements.The second level is scheduling of the same kind of services，using an adaptive adjustment mechanism，it dynamically sets the weight coefficients according to the queue length and the number of packets to ensure the requirements of different users for fairness and non⁃real time services for throughput.The sim⁃ulation results indicated that compared with the DRR and RED⁃DFPQ algorithm，the improved first level scheduling algorithm can reduce the delay and solve the real⁃time scheduling problem.The improved second level scheduling algorithm can balance the user rate，increase the network throughput and fairness，and thus solve sudden problems.Keywords：wireless networks；IEEE802.16；bandwidth scheduling；adaption；differentiated services

10.3969／j.issn.1006⁃7043.201309060

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006⁃7043.201309060.html

TP393.01

A

1006⁃7043（2015）02⁃0186⁃05

2013⁃09⁃17.网络出版时间：2014⁃11⁃27.

国家自然科学基金资助项目（61302094）；福建省科技计划重点资助项目（2014H0030）；泉州市科技计划重点资助项目（2014Z102）.

蒋文贤（1974⁃），男，副教授.

蒋文贤，E⁃mail：jwx＠hqu.edu.cn.