应用于物联网边缘网关的队列调度算法研究
时间：2023-06-06 10:45:18 来源：雅意学习网 本文已影响 人 
袁 瑞, 蒋 伟, 胡 静, 宋铁成
(东南大学 信息科学与工程学院，江苏 南京 211102)
网关为非直连设备连接物联网平台的桥梁。物联网网关整合了物联网的多种接入手段[1]，接入大量设备节点，会产生大量需要转发的数据。在网络带宽受限制的情况下，网关数据会产生积压，子设备与物联网平台之间的通信链路被堵塞。
分组调度技术是实现网络QoS(Quality of Service)的核心技术，是实现网络DiffServ模型的主要手段，是用于解决网络延迟和阻塞等问题的技术支撑。队列调度的原理为将待转发数据按照一定的标准分类为若干个队列，并且按照规则选取合适的分组提供转发服务。
为了优化物联网网关的数据传输模型，考虑在网关上植入调度机制。分组调度策略适用于不同网络环境[2-3]，调度算法轻量化可以被应用在边缘环境[4-5]。由于物联网网关具有一定的边缘计算能力，在网关实现优化的调度传输模型具有可行性。常见的可以应用于边缘网关的队列调度算法[6]包括：基于优先级的调度算法(Priority Queue,PQ)、基于轮询的算法(Round Robin,RR)、基于GPS(General Processor Sharing)流模型的算法等。
PQ算法按照优先级为各个队列提供服务，只有当优先级高的队列为空时才会为低优先级队列提供转发服务，该算法是静态的调度算法，低优先级数据包会出现“饿死”现象；
基于轮询[7]的算法对所有队列进行轮询调度，在某个队列业务量较大时，会降低系统的性能；
GPS模型则假设数据是理想化模型，按照每个队列的权重比例分配带宽，GPS算法假设数据包无限可分，但在实际应用中无法实现。在GPS模型基础上，前人提出了WFQ[8]、WF2Q[9]、WF2Q+(Worst-Case Fair Weighted Fair Queueing+)[10]等公平队列调度算法，此类队列调度技术按优先级分配带宽，适用于物联网网关环境，可以在边缘网关建立队列管理机制，降低实时数据的时延。
为了优化物联网边缘网关上行数据传输模型，考虑利用网关边缘计算能力，在物联网网关引入WF2Q+ 调度算法进行队列管理。在WF2Q+算法中优先级队列的基础上引入实时队列和低时延队列[11](Low Latency Queue)的概念，可以在网络拥堵的情况下保证对延时敏感的数据及时获得转发服务。在队列调度模型后级联令牌桶进行流量整形，并且建立多网关协同传输模型。仿真结果表明，在传输方案中将队列分为实时队列、低时延队列和优先级队列，可以降低数据传输时延，保障网络通信稳定可靠。
为了降低物联网网关传输时延，在网关搭建队列调度机制、比较传统调度算法后，选择基于WF2Q+算法进行改进。
1.1 WF2Q+算法原理
WF2Q+算法的基本思想[10]是维护一个系统虚拟时间V(t)。包裹经过分类器后，形成多个具有不同优先级的队列，每个队列计算一个虚拟服务开始时间Si(等于队列i头部的数据包虚拟服务开始时间)和队列虚拟服务结束时间Fi(等于队列i头部的数据包虚拟服务介绍时间)。队列i第k个包裹到达时，虚拟服务开始时间Si和虚拟服务结束时间Fi需要根据公式进行更新：
(1)
(2)
WF2Q+算法将系统虚拟时间函数更新公式的定义为
VWF2Q+(tj-1+τ)=max(VWF2Q+(t)+W(t,t+τ),mini∈B(Si))
(3)
式中：W(t,t+τ)为在(t,t+τ)时间内数据包得到的服务量；
B为非空队列集合。
WF2Q+算法采用SEFF(Smallest Eligible Virtual Finish-Time First)分组策略，首先对于等待调度的队列进行测试，只有虚拟服务开始时间Si小于系统虚拟时间V(t)的分组才具有出队资格；
其次在具有通过测试的队列中选择具有最小的虚拟服务结束时间Fi的队列，为其提供转发服务。
WF2Q+算法在众多公平队列调度算法中提供了最为严格的时延控制，并且可以提供最小的WFI(Time Worst-Case Fair Index)指数。
1.2 算法缺陷
WF2Q+算法的缺陷在于对于所有业务流都按比例分配带宽，并不能区分实时业务流和非实时业务流。当实际网络波动、带宽不足时，实时性业务会得不到即时的转发服务。并且当存在突发性数据流进入网关时，网络会出现拥塞现象。
针对WF2Q+算法的不足，本文提出了一种改进的WF2Q+调度策略，搭建了多网关协同传输的模型。该算法可以区分实时数据队列、低时延队列和普通优先级队列，并且加入令牌桶作为流量监管机制，很好地提升了网络时延性能，可以应对突发数据流造成网络拥堵崩溃的情况。
2.1 单网关改进的WF2Q+策略
考虑在WF2Q+算法的基础上，将数据包分为实时数据、低时延数据和普通优先级数据。数据包经过分类器，分为实时队列、低时延队列和优先级队列。调度器根据3种不同队列的调度机制从队列中挑选数据包进行转发，最后利用令牌桶算法进行流量整形。单网关改进的WF2Q+算法模型如图1所示。
图1 单网关改进的WF2Q+算法模型
2.1.1 实时队列调度机制
实时队列具有最高的数据优先级，并不经过队列调度器。当实时队列非空时，直接占用带宽，获取转发服务。实时队列内部采用先入先出(First In First Out,FIFO)规则。当实时队列为空时，启用调度器为其他队列提供服务。
2.1.2 低时延队列调度机制
为了保证带宽有限条件下数据的时效性，引入低时延队列。低时延队列不产生数据积压时，可以看作普通优先级队列，根据队列权重分配带宽，根据调度规则选择数据包出列。当低时延队列产生数据积压时，则对队列权值进行调整。
WF2Q+算法根据队列权重分配带宽，因此队列i末尾数据包传输时延为
(4)
式中：B为非空队列集合；
φi为队列i设定的权值；
QLcrt为当前队列长度；
bandwidth为队列分配带宽。根据希望获得的队列最大时延，设定队列最大长度QLmax和队列长度阈值Qth。根据队列长度反馈，在数据包进入队列时，为低时延队列动态分配时延为
(5)
此时随着数据包积压，低时延队列会被分配获取更大的权值。同时，为了保障网络极端拥挤环境下队列延迟情况，在数据包k出队时，修改虚拟服务结束时间更新函数为
(6)
当队列长度超过最大长度QLmax时，包裹出队只为队列虚拟服务完成时间带去很小的增益，队列可以更好地抢占出队服务，从而控制队列时延。
2.1.3 优先级队列调度机制
优先级队列根据WF2Q+算法计算队列虚拟服务完成时间，通过调度器选择，出队获取转发服务。
2.1.4 令牌桶算法
令牌桶(Token-Bucket，TB)为一种流量监管机制[12]，能供控制调度器以固定的速率发送数据，可以应对突发性大量数据造成网络拥堵的情况，并对数据的发送速率进行限制。
令牌桶自身有一定的容量可以存储一些令牌，令牌以恒定的速率存放到令牌桶中[13]。如果令牌桶已经处于满桶状态，应停止向令牌桶中添加令牌。当有数据包到达时，判断令牌桶中是否有足够的令牌数量发送该数据包，如果数量足够，则可以直接发送，数据包发送后，令牌桶需要移除相应数量的令牌。如果令牌桶中令牌数量不够，等待令牌数量足够的时候再发送该数据包。令牌桶算法原理如图2所示。
图2 令牌桶算法原理
令牌桶可以对流量进行整形，令牌桶具有一定深度的容量，可以允许突发性的数据流，总体数据发送速率虽然受到了限制，但是网络具有更好的稳定性。
2.2 多网关协同传输模型
当物联网子设备可以根据不同协议接入多个网关时，建立多网关协同传输模型，子设备自主选择网关进行数据传送，从而在单网关网络拥挤时降低系统整体传送时延。多网关协同传输模型如图3所示。
图3 多网关协同传输模型
网关l的队列i计算参数ηli与当前队列长度QLcrt、队列分配带宽有关，定义为
(7)
多网关协同传输模型可以避免各个网关之间传输负载不均衡的现象。根据网关传输能力，均衡地分配网关的传输任务，从而降低整体传输时延。
在Linux环境下，搭建网络仿真环境。仿真6条数据流，实时数据流发送速率为64 kbit/s，在改进的WF2Q+算法下不设定权重，在WF2Q+算法下设定权重为10，队列号为1，低时延数据包发送速率均为 128 kbit/s，设定最大队列长度QLmax为1024，队列长队阈值Qth为512，权重分别设定为5和4，队列号分别对应为2和3；
优先级数据包发送速率为256 kbit/s具有3种权重：3、2和1，分别对应队列4、5和6。数据流从0.0 s开始发送，对于每个队列，取前50个数据包进行时延分析。
3.1 单网关改进WF2Q+策略仿真结果分析
单网关仿真拓扑结构如图4所示。
图4 单网关仿真拓扑结构
首先验证改进的WF2Q+算法对实时数据、低时延数据的时延控制，分别模拟链路带宽不足(0.3 Mbit/s)和带宽严重不足(0.1 Mbit/s)的情况，仿真对比WF2Q+算法和改进的WF2Q+算法对不同业务流时延的影响，两种算法均使用令牌桶算法进行流量整形，时延统计结果如图5和图6所示。
由图5、图6可以看出，当带宽不足时，改进的WF2Q+算法可以将低时延队列的传输延迟控制在一定时间之内；
当带宽严重不足时，改进的WF2Q+算法仍然可以保证实时业务流的传输，并且降低了低时延数据流的传输时延增长速度。
图5 带宽为0.1 Mbit/s时不同业务流时延
图6 带宽为0.3 Mbit/s时不同业务流时延
其次验证令牌桶算法对数据传输稳定性的影响。分别仿真链路带宽充足(1 Mbit/s)和带宽较为不充足(0.5 Mbit/s)情况下，突发速率为768 kbit/s高优先级(权重为5)低时延数据流，数据流从0.1 s持续至0.15 s。对比使用改进的WF2Q+算法级联或不级联令牌桶算法产生的传输时延。仿真结果如图7和图8所示。
图7 带宽为0.5 Mbit/s时不同业务流时延
图8 带宽为1 Mbit/s时不同业务流时延
统计带宽分别为0.5 Mbit/s、1.0 Mbit/s时，级联或不级联令牌桶情况下，各个队列产生的最大传输时延，WF2Q+/TB表示在改进的WF2Q+算法后级联令牌桶算法，WF2Q+则表示单独使用改进的WF2Q+算法，队列产生的最大传输时延结果如表1所示。
表1 令牌桶算法对时延影响
比较仿真结果，令牌桶算法使链路更加稳定，存在突发数据流时，令牌桶算法可以更快速降低传输时延，并且控制队列时延最大值。
级联令牌桶的改进的WF2Q+算法可以区分实时队列、低时延队列和普通优先级队列，为实时数据提供更低的传输时延，并且算法具有应对突发数据流的能力，可以保证网关传输的稳定性。
3.2 多网关协同传输模型仿真结果与分析
多网关协同传输仿真拓扑结构如图9所示。
图9 多网关协同传输仿真拓扑结构
仿真结构中，假设子设备可以选择传送数据给3个不同的网关。假设网关1链路带宽为0.1 Mbit/s，网关2、网关3的链路带宽为0.2 Mbit/s。发送端产生的数据包根据规则自主挑选网关，经过网关到达接收端。对照组假定发送端产生的数据均匀分配给各个网关，网关对数据包进行转发，网关内部均采用改进的WF2Q+算法进行队列调度。取每个队列前50个获取转发服务的数据包，各个队列的平均时延如图10所示。
由图10可以看出，多网关协同传输模型可以降低子设备数据传输整体时延。数据包自主选择路径传送，优化了传输路径选择策略。
图10 队列平均传输时延
基于WF2Q+算法提出了一种应用于物联网网关传输模型中的改进的WF2Q+队列调度策略。该策略对优先队列算法无法区分会话优先级的情况进行了优化，引入了实时队列、低时延队列、优先级队列的分类，保障了网络堵塞情况下实时队列和低时延队列的及时传输，级联令牌桶算法保证调度模型在遇到突发数据流时具有稳定性。在改进队列调度算法的基础上提出了多网关协同传输模型，数据包依据规则自主选择传输路径，保证了单网关传输带宽有限情况下数据包可以正常传输至物联网平台。该传输模型具有很好的应用前景和实用意义。
猜你喜欢 令牌数据流队列 称金块小猕猴学习画刊·下半月(2022年2期)2022-04-16数据流计算研究进展与概述数据与计算发展前沿(2021年5期)2021-11-30汽车维修数据流基础(上)汽车维修与保养(2020年10期)2021-01-22队列队形体育教案科学导报·学术(2020年26期)2020-10-21汽车维修数据流基础(下)汽车维修与保养(2020年11期)2020-06-09队列里的小秘密小学生学习指导(低年级)(2020年4期)2020-06-02基于多队列切换的SDN拥塞控制*软件(2020年3期)2020-04-20基于路由和QoS令牌桶的集中式限速网关网络安全技术与应用(2019年7期)2019-12-24在队列里军营文化天地(2018年2期)2018-12-15AADL端对端数据流一致性验证方法计算机技术与发展(2018年1期)2018-01-23
