适用于矿山物联网多业务传输的动态差额加权轮询调度方法

摘要

本发明提出一种适用于矿山物联网多业务传输的动态差额加权轮询调度方法，包括：井下传感器采集的数据汇聚到网关；将传感器采集的数据按照优先级分类，并排到对应等级的调度队列中；调度服务器按时延优先级高低依次服务各个队列；服务某队列时，根据队列的差额计数器值来判断是否发送数据包；更新队列的差额计数器时不仅考虑队列的时延优先级，还考虑了网络突发流量及历史排队时延。本发明通过增加了对队列瞬时到达率及历史排队时延两个因素，使得该方法在网络出现突发流量时可以自适应地调整差额分配，并且可以有效防止低优先级队列由于分配资源较少导致的队列拥塞现象。

说明书

技术领域

本发明属于矿山物联网多类型业务调度传输领域，具体涉及根据矿山网络中不同类型业务的QoS(Quality of Service，服务质量)需求，提出了一种动态调整的差额加权轮询传输调度方法。

背景技术

煤炭是我国重要的能源，煤矿产业作为基础产业和资源生产产业，在我国有着举足轻重的地位，为国家的稳定发展贡献了巨大力量。但是，煤矿产业也是一个安全性极不稳定的行业，煤矿开采安全事故时有发生，严重制约着煤炭行业的发展，同时也威胁着矿井职工的人身安全。一方面，由于全国各地区矿井地质构造结构比较复杂，负责生产的设备种类不一；另一方面，生产作业人员专业知识不够扎实，安全意识匮乏；多方面因素导致煤矿生产存在巨大的安全隐患。因此，有必要对煤矿井下复杂的环境开展研究，探求新的信息处理理论和方法对矿井系统进行实时控制、精确管理和科学决策。

矿山物联网是互联网技术和通信网技术的延伸和应用，通过灵活布局的无线传感器网络对矿山的环境状态、设备状态及人员位置等信息进行全方位的动态控制，将矿山基础设施整合为一个有机整体，无线传感器网络的分布式感知能力可以实现对煤矿全面、透彻的感知，为煤矿安全生产、决策管理和灾害预警提供保障。随着矿山物联网中传感设备种类的增多，井下网络网关处汇聚了各种类型的业务信息，如环境监测信息、人员状态信息、语音视频通话信息等。不同的业务类型具有不同的QoS需求，由于井下网络网关带宽有限，为了满足各业务类型的QoS需求，必须使用高效合理的调度方案。因此，基于QoS需求的多类型业务调度研究对提高矿山网络传输效率、保证矿山安全生产具有重要的意义。

同时随着煤矿开采规模的扩大以及对煤矿安全生产要求的不断提高，对煤矿井下人员、设备、环境监控、视频监控、自动化、信息化等各类子系统的要求也在不断增加。因此，传输中井下接入业务也越来越多，对矿井网络传输需求呈现出多样性发展趋势，既有设备状态监测信息的高实时性、低时延的传输需求，也有人员位置、矿压环境等低时延、全覆盖的传输需求；既有环境监测的小数据传输，也有高清视频的高带宽的传输需求。网关需要对具有不同传输需求的各类型业务进行统一调度处理，因此需要设计合适的队列调度算法，是提高井下网络传输效率，增强网关数据传输性能的关键。

传统的队列调度算法主要分为基于时间戳的调度算法和基于轮询的调度算法两大类。典型的有WFQ(Weighted Fair Queuing，加权公平排队算法)[参考文件1]和WRR(Weighted Round Robin，加权循环调度算法)[参考文件2]。差额加权轮询算法(DWRR)[参考文件3]在WRR的基础上作了改进，克服了WRR在分组长度变化的情况下无法精确分配带宽的问题，同时降低了计算复杂度，更适应于硬件实现，克服了WFQ的不足。尽管以上的算法提高了面对多类型业务流时的表现，然而这些算法都主要关注调度时刻的队列时延，并没有对队列的数据到达速率以及队列历史排队时延进行考量，因此无法在网络遇到突发流量或队列历史排队时延过大时保证良好的公平性。

参考文献1：Lu,Feng,Geoffrey M.Voelker,and Alex C.Snoeren."Weightedfair queuing with differential dropping."INFOCOM,2012Proceedings IEEE.IEEE,2012.

参考文献2：Zhou,Aibing,et al."Hybrid weighted round robin(WRR)trafficscheduling."U.S.Patent No.8,462,802.11Jun.2013.

参考文献3：Richard,Frederic,and David W.Mendel."Multi-level deficitweighted round robin scheduler acting as a flat single scheduler."U.S.PatentNo.9,424,088.23Aug.2016.

发明内容

本发明的目的是在DWRR算法的基础上，根据矿山物联网多类型业务不同传输需求的特点，对DWRR算法中差额计数器(Deficit counter)的更新方法进行改进，提出一种适用于矿山网络的动态队列调度方法，在满足时延优先级要求的同时考虑网络突发流量及队列长期公平性，为矿山网络多业务调度传输提供了一种有效解决方法。

本发明提供了一种适用于矿山物联网多业务传输的动态差额加权轮询调度方法，在井下传感器采集的数据经由网关汇聚传输至井上网络的过程中，在网关处将传感器采集的数据按照优先级分类，并排到对应等级的调度队列中，各队列的时延优先级是固定设置的。本发明方法在网关处对传感器采集的数据，基于动态差额加权轮询算法进行调度处理，包括如下步骤：

调度服务器按时延优先级高低依次服务各个队列；

在服务非空队列时，根据队列的差额计数器来决定是否发送数据包，当发送数据包时，在差额计数器中减去当前发送的数据包长度，当不发送数据包时，更新队列的差额计数器；

更新队列的差额计数器的方法如下：

设队列i在第k+1次轮询时的差额计数器值为Dc(i,k+1)，根据下面公式更新：

Dc(i,k+1)＝Dc_res(i,k)+Dc_cal(i,k)

其中，Dc_res(i,k)表示队列i在第k次轮询时差额计数器的剩余值，Dc_cal(i,k)表示队列i在第k次轮询时计算的差额计数器值，Dc_cal(i,k)的根据下式计算得到：

Dc_cal(i,k)＝α_i×P(i)+β_i×A(i,k)+γ_i×D(i,k)

其中，P(i)表示队列i的时延优先级权重因素，A(i,k)表示队列i在第k次轮询时的瞬时到达率权重因素，D(i,k)表示队列i在第k次轮询时的历史排队时延权重因素；α_i,β_i,γ_i为队列i的权重影响因子。

本发明与现有技术相比，具有以下明显优势：

(1)当矿山网络中出现突发流量时，本发明方法可以根据队列的数据到达速率自适应地调整队列分配的带宽，及时处理突发数据，降低因为突发流量而造成网络拥塞的可能性。

(2)本发明方法可以有效避免矿山网络中具有较低时延优先级和较大数据传输量的业务队列因为长期分配带宽较小而导致的队列拥塞问题。

附图说明

图1是本发明应用的矿山物联网无线传感器网络传输示意图；

图2是动态差额加权轮询算法的流程示意图；

图3是动态差额加权轮询算法中差额计数器Dc的更新示意图；

图4是本发明基于动态差额加权轮询对矿山物联网多业务进行数据传输调度的示意图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图对本发明作进一步的详细描述。

如图1为矿山物联网无线传感器网络传输示意图，本发明方法以矿山物联网为应用场景，在井下部署了各类传感器用于监测矿井环境、设备状态、人员位置等信息，传感器网络的信息将经由网关汇聚传输至井上网络，利用工业以太网与井上设备相连接，实现对矿井系统的监测和控制。

由于矿山物联网中信息种类繁多，各种业务类型对传输延迟、时延抖动等对QoS参数都有不同的要求。因此，在进行调度发送之前有必要将接收到的信息进行分类，包含报警类信息的业务属于关键业务，要求立刻得到转发，其余信息类型属于非关键业务，将进一步处理后调度发送。本发明方法首先在网关处将传感器采集的数据按照优先级分类，并排到对应等级的调度队列中，本发明的调度方法将在网关处对传感器采集的信息进行调度处理。

在本发明的队列调度方法中，根据不同业务类型的QoS要求，提出了一种在动态差额加权轮询算法的基础上增加了对队列瞬时到达率及历史排队时延两个因素，使得该算法在网络出现突发流量时可以自适应地调整差额分配，并且可以有效防止低优先级队列由于分配资源较少导致的队列拥塞现象。

动态差额加权轮询算法流程示意图如图2所示，调度服务器按时延优先级高低依次服务各个队列，首先判断队列i是否为空，若为空则直接服务下一个队列；若队列i非空，检查队列i头部的数据包长度Pac_size(i,n)是否小于等于队列i被分配的差额计数器Dc(i,k)，k表示当前轮询次数，n表示数据包的编号，若是，则发送该数据包n，更新n自增1，并在差额计数器值中减去相应的数据包长度；若大于差额计数器Dc(i,k)，则不发送数据，更新该队列i的差额计数器，D_C(i,k)＝D_C_res(i,k)+D_C_cal(i,k)，更新方法为上次轮询剩余的差额D_C_res(i,k)加上根据队列当前状态计算的新的差额D_C_cal(i,k)。在对每个队列处理时，当队列的差额计数器值小于队列最小的数据包长度min(Pac_size)时，停止对该队列处理，继续服务下一个队列。利用差额计数器进行队列轮询的示意图，如图3所示。

本发明的适用于矿山物联网多业务传输的动态差额加权轮询调度方法，如图4所示，在网关处的调度服务器按时延优先级高低依次服务各个队列。在服务非空队列时，如图2所示方法，根据队列的差额计数器来决定是否发送数据包，当发送数据包时，在差额计数器中减去当前发送的数据包长度，当不发送数据包时，更新队列的差额计数器。队列的差额计数器的初始值是根据队列的时延优先级设置的。

在本发明的适用于矿山物联网多业务传输的动态差额加权轮询调度方法中，最关键的是对差额计数器Deficitcouter(Dc)进行了动态调整。差额计数器是差额加权轮询算法(DWRR)中核心的部分，每个队列在轮询开始时会被分配一个差额值，差额值决定了该队列在这次轮询中允许发送的最大数据量。在DWRR算法中，每个队列的差额是固定的，仅由队列的时延优先级决定。本发明对差额的计算进行了改进，考虑了网络突发流量及历史排队时延，对差额进行了动态调整，具体调整方法如下。

当差额计数器等待更新时，将根据每次轮询时队列的时延优先级、瞬时到达率及历史排队时延三个状态信息计算新的Dc值，用计算得到的值加上上次轮询Dc的剩余值得到下一次轮询时的Dc值，计算方法如公式(1)所示：

Dc(i,k+1)＝Dc_res(i,k)+Dc_cal(i,k)(1)

其中，Dc(i,k+1)表示队列i在第k+1次轮询时的Dc值，Dc_res(i,k)表示队列i在第k次轮询时Dc的剩余值，Dc_cal(i,k)表示队列i在第k次轮询时计算的Dc值。Dc_cal(i,k)的计算方法如公式(2)所示：

Dc_cal(i,k)＝α_i×P(i)+β_i×A(i,k)+γ_i×D(i,k)(2)

其中，P(i)表示队列i的时延优先级权重因素，A(i,k)表示队列i在第k次轮询时的瞬时到达率权重因素，D(i,k)表示队列i在第k次轮询时的历史排队时延权重因素。α_i,β_i,γ_i为队列i的权重影响因子，影响因子的取值将根据当前网络状况分情况决定。

下面详细分析P(i)，A(i,k)，D(i,k)的计算方法。

(1)时延优先级权重因素P(i)。每个队列的时延优先级是固定的。假设共有N个队列，队列i的时延优先级为Pri(i)，则时延优先级权重因素P(i)的计算方法如公式(3)所示：

(2)瞬时到达率权重因素A(i,k)。数据包的瞬时到达率Ari(i,k)表示队列i在第k次轮询和第k-1次轮询之间数据包到达的速度。引入瞬时到达率权重因素是为了在网络出现突发流量时可以及时调整各队列带宽分配，防止出现网络拥塞现象。Ari(i,k)的计算方法如公式(4)所示：

其中，t_k表示第k次轮询时的时刻，t_k-1表示第k-1次轮询时的时刻，Ari_sum(i,t)表示队列i在时刻t到达的数据包数目，此处，t取值为t_k或t_k-1。瞬时到达率权重因素A(i,k)的计算方法如公式(5)所示：

(3)历史排队时延权重因素D(i,k)。由于低优先级队列分配的带宽较少，长期发送会导致队列出现拥塞，后到的数据排队时间过长得不到发送，从而出现队列拥塞现象。为了防止此现象的发生，引入对历史排队时延因素的考虑，队列i在第k次轮询时的历史排队时延Del(i,k)的计算方法如公式(6)所示：

其中，Num(i,t_k)表示队列i在第k次轮询时到达的数据包数目；Num(i,t_k-1)表示队列i在第k-1次轮询时到达的数据包数目；Pac_sen(i,n)表示队列i第n个数据包发送的时刻，Pac_ari(i,n)表示队列i第n个数据包到达的时刻。即用每个队列已经发送的数据包的等待时间的平均值来表示该队列的历史排队时延。历史排队时延权重因素D(i,k)的计算方法如公式(7)所示：

本发明的动态差额加权轮询调度方法在基础的差额加权轮询算法上增加了对瞬时到达率和历史排队时延因素的考虑，各队列将根据自身状态自适应调整差额分配，在保证高优先级队列优先发送的同时，也可以有效防止低优先级队列因分配带宽过小导致数据包长时间得不到发送而造成的拥塞现象。同时使得调度算法在网络出现突发流量时有较好的应对能力，相对其他队列调度算法对矿山物联网有很好的适用性。