标题

Size: px

Start display at page:

Download "标题"

更束
5 years ago
Views:

1 第 36 卷第 2 期哈尔滨工程大学学报 Vol 年 2 月 Journal of Harbin Engineering University Feb.2015 摘 IEEE 网络动态自适应区分服务算法蒋文贤, 许晓璐 ( 华侨大学计算机科学与技术学院, 福建厦门 ) 要 : 针对 IEEE802.16MAC 协议中的调度机制不能提供流媒体业务区分服务的问题, 提出了一种基于服务类别优先级的链路带宽自适应分配调度 PDA DFPQ 算法该算法分为两级调度架构, 第一级是不同业务间的调度, 采用服务质量优先级策略, 高优先级服务类分配合适的带宽, 以保障实时业务对最大时延限定的要求 ; 第二级是同种业务内的调度, 采用自适应调整机制, 根据队列长度和分组数动态设置权值系数, 以保障不同用户对公平性和非实时业务对吞吐量的要求仿真结果表明 : 与 DRR 和 RED DFPQ 算法相比较, 改进的一级调度算法能降低时延, 解决实时性问题 ; 改进的二级调度算法能均衡用户速率, 提高网络吞吐量和公平性, 解决突发性问题关键词 : 无线网络 ;IEEE802.16; 带宽调度 ; 自适应 ; 区分服务 doi: / j.issn 网络出版地址 :http: / / / kcms / doi / / j.issn html 中图分类号 :TP 文献标志码 :A 文章编号 : (2015) Algorithm for IEEE network dynamic adaptive differentiated services JIANG Wenxian,XU Xiaolu ( College of Computer Science and Technology, Huaqiao University, Xiamen , China) Abstract:Considering that IEEE 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 IEEE [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) 算法该算法定义了亏空计数器收稿日期 : 网络出版时间 : 基金项目 : 国家自然科学基金资助项目 ( ); 福建省科技计划重点资助项目 (2014H0030); 泉州市科技计划重点资助项目 (2014Z102). 作者简介 : 蒋文贤 (1974 ), 男, 副教授. 通信作者 : 蒋文贤,E mail:jwx@ hqu.edu.cn. (deficit counter,dc), 一旦某队列的首个分组长度大于 DC 值就终止对该队列的服务 ; 而不同的业务在第二级调度中使用各自的调度算法 ; 文献 [3] 提出了基于随机早期检测 ( random early detection, RED) 的 DPFQ 算法, 针对高优先级业务负载较高时无法保证低优先级业务的 QoS 问题对 DFPQ 算法进行改进, 设计了动态变化的 DC 值 ; 文献 [4] 为保证各种多媒体 QoS, 提出了一种基于正交频分多址接入技术和自适应调制编码机制的二级调度方案 ; 文献 [5] 提出了一种移动 IEEE 的跨层主动队列管理方案, 利用传输层的窗口变化信息, 改善上行终端的丢弃率等特性, 提高了上行链路的性能 ; 文献 [6] 提出一种基于传输速率自适应的动态分配算法, 并采用一个动态优化的迭代算法自适应调节用户的传输速率来得到最优的带宽重分配矩阵, 以此最大化无线网络的效用函数 ; 文献 [7] 提出一个基于学习自动机的 IEEE 上行链路的实时多媒

2 第 2 期蒋文贤, 等 :IEEE 网络动态自适应区分服务算法 187 体业务调度算法 ; 文献 [ 8] 提出了一种用于移动 IEEE 上行链路流量的高效带宽分配算法, 使用智能系统方法, 设计了自适应的基于期限的方案, 为实时应用保证特定的最大时延要求 ; 文献 [9] 从数据调度竞争的角度出发, 提出了一种节能的实时业务数据调度算法 ; 文献 [10] 提出了效用最大化的 IEEE 带宽分配算法和快速解法, 可灵活地改变效用函数参数, 在不同服务质量要求下高效地做出分配以上算法虽然在某些方面提高了性能, 但没有较好解决时延吞吐量和公平性之间的平衡根据现有文献对 IEEE 调度机制的研究, 针对其不能提供流媒体业务区分服务的问题, 将分层设计和自适应控制的思想引入到 QoS 调度机制中, 提出了一种基于服务类别优先级的链路带宽自适应分配调度算法 PDA DFPQ 1 调度服务算法该算法分为两级调度架构, 第一级是不同业务间的调度, 采用服务质量优先级策略, 高优先级服务类分配合适的带宽, 以保障实时业务对最大时延限定的要求, 解决实时性问题 ; 第二级是同种业务内的调度, 采用自适应调整机制, 根据队列长度和分组数动态设置权值系数, 以保障不同用户对公平性和非实时业务对吞吐量的要求, 解决突发性问题总体调度框架图如图 1 所示 Fig.1 图 1 IEEE 总体调度框架设计图 IEEE overall scheduling framework design 1.1 基于优先级策略的第一级调度设计第一级调度也称为类间调度, 是指各种不同类型的业务流所在队列的调度服务用户站 ( subscribe sta tion,ss) 到基站 (base station,bs) 的连接将分配一种服务类型,BS 针对每个服务类别都建立与之相应的调度队列, 每个队列有一组与之相关联的各自不同的 QoS 需求参数由于 UGS 服务类型的分组是以恒定速率和固定大小进行传输的, 在 IEEE 系统中,BS 以主动授权方式为其分配带宽, 因而 UGS 业务无需进入第一级调度余下 rtps ertps nrtps 和 BE4 种类型业务进入第一级调度, 采用服务类型优先级算法同类分组具备相同的 QoS 要求, 队头分组的 QoS 优先级函数值大小决定分组的顺序, 取值最大的分组将获得优先调度的权利如图 2 所示 Fig.2 图 2 链路带宽分配过程 The link bandwidth allocation process 1.2 基于动态自适应的第二级调度设计第二级调度也称为类内调度, 指各个相同类型的业务流间的调度在 IEEE 中提供 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) 算法进行调度, 通过权重系数设定业务队列服务时间, 高优先级队列具有优先权加权值表示获取资源的比重, 权重采用的公式 : W i = p i r i / p i r i, 其中 p i 为优先级参数折算后的系数, r i 为 i 带宽速率的差值 4)BE 业务对于 BE 业务, 由于没有对 QoS 严格的要求, 考虑到多用户间 BE 业务流的公平性, 因此采用轮询 ( round robin,rr) 调度算法, 为每个 BE 流提供相同的机会传输分组, 即每次调度执行 i = (i + 1)mod n, 并选出第 i 用户进行调度 2 仿真与分析 2.1 实验参数设置系统是基于单个 BS, 在 TDMA 访问模式下使用点

3 188 哈尔滨工程大学学报第 36 卷对多点 (point to multipoint,pmp) 方式执行, 多个 SS 终端随机分布在 3 km 半径范围内, 部署 3 台服务器, 其中流媒体服务器主要是处理 rtps 和 ertps 业务 FTP 服务器主要是处理 nrtps 业务 Web 服务器主要是处理 BE 业务, 仿真的网络拓扑结构如图 4 所示算法仿真在 OPNET 环境中实现, 参数设置主要包括 Config 模块 Application 模块和 Profiles 模块, 由于 IEEE 网络业务流具有自相似特性, 利用 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 数量较多时, 平均队列时延急剧增长, 原因是简单对各种业务的轮循或加权轮循, 未考虑每个队列的实际带宽请求 Fig.3 图 3 调度算法流程图 Scheduling algorithm flow chart

4 第 2 期蒋文贤, 等 :IEEE 网络动态自适应区分服务算法 189 可以看出 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 业务的时延也较小图 4 网络拓扑结构 Fig.4 Typical network topology Fig.7 图 7 Fig.5 图 5 队列平均时延对比 Comparion of queue average delay 的平均时延图 6 显示了 PDA DFPQ 实现的各种服务类别 Fig.8 图 8 Fig.6 图 6 虽然 BE 业务的时延受到一定的影响, 但仍在可以接受的范围内 PDA DFPQ 算法下的 rtps 业务吞吐量总体高于 DRR 和 RED DFPQ 算法下的吞吐量, 这是因为 PDA DFPQ 算法采用自适应调整机制, 动态分配不同的权值系数, 允许长度更大的分组得到更高的服

5 190 哈尔滨工程大学学报第 36 卷务机会, 网络中传输的分组数量较多, 更好地保障了分组调度情况 ; 而对比 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 因此, 可以得出, 在可接受范围内牺牲非实时业务的吞吐量性能以换取实时业务的吞吐量优化, 更好地保证了实时业务的 QoS 要求 3 结束语针对 IEEE 中 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 / WiMAX systems[j]. Wireless Com munications and Mobile Computing, 2010, 10 ( 7): [2]SAFA H, ARTAIL H, KARAM M, et al. New scheduling architecture for IEEE wireless metropolitan area net work[ C] / / Computer Systems and Applications, ( AICCSA 07. IEEE / ACS International Conference). [ S. l.], 2007: [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 th International Symposium).[ S.l.], 2009:1 5. [4] 陈婷, 李建东, 钟绍波等. 一种面向公平保证 QoS 的 WiMAX 二级调度方案 [J]. 计算机研究与发展, 2009, 46 (7): 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): [5] SADRI Y, KHANMOHAMMADI S. A QoS aware dynamic scheduling scheme using fuzzy inference system for IEEE networks [ J]. Wireless Personal Communications, 2013, 72(4): [6] 陈赓, 夏玮玮, 沈连丰. 基于传输速率自适应的动态带宽分配算法 [J]. 通信学报, 2014, 35(5): CHEN Geng, XIA Weiwei, SHEN Lianfeng. Dynamic band width allocation algorithm based on transmission rate adapta tion[ J]. Journal on Communications, 2014, 35(5): [7] MISRA S, BANERJEE B, WOLFINGER B E. A learning automata based uplink scheduler for supporting real time multimedia interactive traffic in IEEE WiMAX net works [ J ]. Computer Communications, 2012, 35 ( 15 ): [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): [9]IYENGAR R, SIKDAR B. A queueing model for polled serv ice in WiMAX / IEEE networks [ J]. IEEE Transac tions on Communications, 2012, 60(7): [10] 聂伟. WiMAX 无线网络 QoS 测量及优化研究 [ D]. 成都 : 电子科技大学, 2011: 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:

Mechanical Science and Technology for Aerospace Engineering October Vol No. 10 Web SaaS B /S Web2. 0 Web2. 0 TP315 A

2012 10 31 10 Mechanical Science and Technology for Aerospace Engineering October Vol. 31 2012 No. 10 Web2. 0 400030 SaaS B /S Web2. 0 Web2. 0 TP315 A 1003-8728 2012 10-1638-06 Design and Implementation