面向工业无线系统的实时聚合调度方法

王忠锋，张 楠，4，夏长清，尚志军，田 宇，4，金 曦，许 驰

1(中国科学院 网络化控制系统重点实验室，沈阳 110016) 2(中国科学院 沈阳自动化研究所工业控制网络与系统研究室，沈阳110016) 3(中国科学院 机器人与智能创造创新研究院，沈阳 110169) 4(中国科学院大学，北京 100049)

1 引 言

近年来，工业无线网络的研究引起了越来越多的关注，并逐渐成为发展的热点[1].随着工业互联网与智能工厂的兴起，无线网络的规模正在不断扩大，工业无线网络已成为工业控制系统的重要组成部分.对于工业系统，实时性保障至关重要.目前，主流工业无线协议大多采用TDMA(Time Division Multiple Access，时分多址)技术确保网络系统的实时性.然而，有限的网络资源难以满足工业控制系统中大量指令、数据的实时需求.

数据聚合传输[2]是提高网络资源利用率的有效手段.通过对多个数据包中有效数据进行解析、聚合，实现一组包头校验位下的多组有效数据传输.聚合传输可以减少数据包在重叠链路上的传输次数，缓解传输冲突，减少网络资源需求.然而，聚合传输主要用于实时性较低的大数据量传输以及树状拓扑网络，难以满足工业控制实际需求[3].针对此问题，本文研究了网状拓扑下的工业无线网络实时聚合传输问题，主要贡献如下：

1.提出网状拓扑下的实时聚合调度新方法EDF-PA，该算法通过在路径重叠区域采用基于优先级排序被动聚合等待的方式对数据包进行聚合，低优先级数据包在聚合点被动等待高优先级数据包到来后进行聚合，在不改变高优先级数据包传输规则的情况下提高系统整体传输效率.仿真结果表明，EDF-PA方法比传统聚合方法调度成功率提升20%；在考虑网络丢包时，性能仍可提升5%.

2.为进一步提高重叠区域数据包的聚合度，提出一种改进的聚合调度算法EDF-OPA，EDF-OPA首先对EDF-PA调度表进行检测，当检测到聚合后数据包到达目标节点后产生延迟等待时，EDF-OPA将以数据流可调度性为约束，令满足约束的数据流主动聚合等待，通过延迟等待时间最大化特定重叠区域的数据包聚合度，提高信道资源利用率.改进算法能有效提高工业无线系统性能，将调度成功率提升35%；在网络丢包严重时，性能仍可提升20%.

2 相关研究

工业无线网络资源有限，聚合传输是在受限的资源条件下提高传输性能的有效方法.工业无线网络中的数据聚合调度方法目前已有广泛研究.文献[4]提出了基于簇的无线传感器网络中的数据聚合经典算法LEACH.通过随机选取的簇头节点从簇中成员收集数据进行聚合，并将聚合后的数据通过其他簇头以单跳或多跳的方式与基站通信[5].此后，研究人员通过使用路由协议[6]和优化簇头的选择[7]来提高LEACH算法的性能；另一方面，也引入了多输入多输出[8]、网络编码[9]、机会路由[10]和空中接入点[11]等方法做进一步优化.然而，这些技术主要关注减少节点能耗以延长生命周期，没有考虑数据传输的实时性能.

为了降低数据聚合带来的时延影响，文献[12]使用了经典的聚合调度算法(Earliest Deadline First Scheduling Method with a First Fit bin-packing algorithm，EDF-FF)，通过FF算法分配资源与EDF调度算法的结合来提高网络的实时性.为了进一步提高聚合调度的性能，可通过建立最优的聚合树来得到聚合方案，构建最优聚合树得到最小延迟的聚合方案已被证明是NP-hard问题[13，14].文献[15]提出了基于自适应的分布式马尔可夫近似算法构造最小延迟数据聚合树来降低聚合延迟.文献[16]通过蜻蜓算法(DA)查找网络延迟和数据包传输速率表现好的最佳聚合树.文献[17]提出每个簇头先将数据进行压缩聚合，再使用最小生成树(MST)构造聚合树，并综合考虑丢包率和时延等指标分配通信资源.上述方法均通过构建聚合树实现聚合[18]，虽然可以提高网络通信的实时性能，但仅适用于树状拓扑结构的无线网络.

网状拓扑结构具有高度鲁棒性，是工业无线网络中最为常见的拓扑结构，也是下一代工业无线系统中的关键组成部分[19].因此，迫切需要面向网状拓扑网络的实时聚合传输方法研究.

3 系统模型及问题描述

3.1 系统模型

工业无线网络中数据流的传输路径，由源设备到目的设备之间的一系列有序链路组成，其传输路径由网络层的路由算法计算得出，数据包采用多跳的形式沿着传输路径在分配的时隙和信道上进行传输.在工业无线网络中，数据的传输主要存在两种冲突，分别是传输冲突与信道冲突.传输冲突指工业现场设备采用单天线的通信方式，设备不能在同一时隙下既发送数据又接收数据.信道冲突要求在同一时隙下，若当前待调度链路的总数超过可用信道数，则不能在当前时隙下调度所有链路.当前时隙未调度的通信链路只能安排到下一时隙.当数据流传输至相同节点附近时，由于传输冲突的限制，相互冲突的链路必须安排在不同的时隙，因此会减少可用时隙，导致数据流不能在截止时间内分配到充足的通信资源，影响数据传输的实时性.

WirelessHART是典型工业无线网络通信协议，其应用较为广泛.可以将基于WirelessHART组建的网络系统抽象为G=(V，E)，V表示网络中所有设备，E表示设备之间的通信链路.令所有工业设备的总数为|V|，则网络中所有设备可表示为V={V1，V2，…，VI，…}.一条有向边e=(Vu，Vv)表示设备Vu向设备Vv发送数据.工业无线网络数据流沿着通信链路传输，数据流通过多跳的形式在分配好的时隙和信道上进行传输.网络中数据流数量为|F|，可表示为F={f1，f2，…fj，…}，将数据流定义为fi=.对于任意数据流fi，数据包的生成周期为pi，数据包原始有效负载为si.本文设定数据包原始负载长度相同，即si=s.将聚合的数据包解聚时需要识别出聚合包中不同的数据报文，聚合时在数据包有效负载前加入一个长度标识h，定义聚合有效负载的上界为Smax.数据包长度定义为L，表示有效负载长度、数据包头长度和校验部分的长度之和.

图1 数据帧结构Fig.1 Data frame structure

数据包的数据帧结构如图1所示.网络中数据流的路径可表示为R={R1，R2，…Rm}.数据流沿通信路径传输的跳数为ci.对于网络中的数据流fi，令di表示其相对截止时隙，为保证数据流产生后在给定的截止时间内传送至目的节点，应满足ci≤di≤pi.定义整个网络中所有数据流周期的最小公倍数为网络的超帧周期P.网络可用信道数目为M，丢包率为l.

无线网络数据流模型的示例如图2所示.在网状拓扑结构中，根据EDF调度方法为3条数据流分配时隙与信道资源.这里3条数据流优先级相同，则依照优先传输较小编号数据流的规则，可得基于EDF调度方法的调度表，此时数据流f3的8-9链路因错失截止期而不可调度.选用常见于树状网络中的经典聚合调度方法[12]得到新调度表.在第3时隙，根据聚合调度方法的原理，数据流f1在节点4处等待与即将到达的数据流f2聚合传输；同样的，数据流f3从第4时隙开始在节点8处等待与路径重合的f1聚合并在第6时隙传输8-9链路.其中数据流f1与f3的等待时间均满足可调度性约束，但导致数据流f2的5-9链路的传输因存在传输冲突无法在截止时间前分到信道资源最终不可调度.由于网状拓扑结构复杂，聚合包在重叠链路流出节点处需要占用更多的通信资源将各解聚的包传到各自的目的节点，而树状拓扑聚合后则不需要解聚传输，所以传统的用于树状拓扑的聚合调度方法并不适用于网状拓扑.因此，设计出在网状拓扑下有效的实时聚合调度方法尤为重要.

3.2 问题描述

对于支持数据包聚合解聚功能的工业无线网络，应通过设计算法保证数据包等待聚合的延时消耗满足截止时间约束，且聚合有效数据负载小于聚合上限.通过数据包的聚合减少节点转发路径重叠的数据包的传输次数，提高网络资源利用率，保证每条数据流都可调度.聚合执行时间与传输时间相比可忽略不计，因此问题可以被描述为：

(1)

其中，F*={f1,f2,…fi},F*为网络中可调度的数据流集合.在上述数学描述中，公式(1)表示聚合问题的目标是保证尽量多的数据流在截止时间内成功传输到达目的节点，提高数据流的可调度性.聚合问题的目标，即公式(1)需满足以下约束条件：

1)截止时间约束：端到端数据流需要在其截止时间内传输成功.

(2)

(3)

minci(wait)

(4)

2)信道约束：在同一时隙下，网络调度的链路总数不能超过可用信道数，以免造成信道冲突，则：

∑(u,v)∈Eζt(u,v)≤M

(5)

3)传输冲突约束：工业现场设备采用单天线的通信方式，设备不能在同一时隙下既发送数据又接收来自其他设备的数据.

∑(u,v)∈Eg(u)ζt(u,v)+∑(v，u)∈Hg(v)ζt(v,u)≤1

(6)

ζt(u,v)∈{0,1}，ζt(v,u)∈{0,1}

(7)

ζt(v,u)表示时隙设备u和v之间的链路传输状态.若通信链路(u,v)在t时隙可以传输数据流，则ζt(u,v)=1；反之，ζt(u,v)=0.Eg(u)表示当前时隙以设备u为发送方的链路集合，Hg(v)为当前时隙以设备v为接收方的链路集合.

4)聚合有效负载长度约束：聚合传输时，聚合数据包的有效负载长度需满足聚合长度上限.

h=「log2x⎤

(8)

Su=n×(s+h)

(9)

Su≤Smax

(10)

公式(8)表示数据包聚合标识长度的计算方式，其中，x为流经各网络设备数据流数量的最大值，在当前网络中聚合标识长度在各设备处均为固定值.例如，当前网络中流经网络设备数据流数目中最大值为7，在各节点处聚合标识长度取值为3.将各网络设备的聚合解聚标识位设置为开启状态，通过识别数据包头与有效数据部分之间的聚合标识来确定是否需要解聚该数据包.公式(9)表示设备u处的n个数据包聚合后的有效负载长度.公式(10)为聚合长度约束.

5)聚合度约束：模型希望聚合尽量多的数据包以提高网络资源利用率.

max∑u∈VSu

(11)

4 聚合调度方法

4.1 考虑数据包聚合的最短截止时间调度方法

考虑数据包聚合的最短截止时间调度方法(Earliest Deadline First Scheduling Method considered on Packet Aggregation，EDF-PA)的主要思想是：首先将当前时隙下传输至重叠链路流入节点的多个数据包进行聚合，然后在传输至重叠链路末端节点处进行解聚，解聚后的数据包沿着后续各自不同的路径传输.该方法能够有效缓解数据流路径重叠导致的传输冲突，显著降低数据流在通信链路传输时对网络资源的需求；并在不改变数据包按优先级传输规则的情况下，提高系统的整体传输效率与实时性.EDF-PA调度方法比经典调度方法的复杂度大，延长了算法的执行时间，但由于调度算法离线进行，可以满足工业无线网络的实时性需求.

EDF-PA算法执行过程如下：

1)首先根据网络输入参数初始化网络状态与调度表(第1行).

2)在当前时隙下，若有数据流超出截止时间则返回不可调度；否则可进入下一步.(3～5行)

3)当前时隙下数据包在重叠链路的流入节点处等待分配信道资源，若有其他路径重叠的包传输至该节点，且满足数据包聚合后的有效负载长度上限，将节点处的多个数据包聚合成一个包(6～8行)，选择聚合的多个数据包中截止时间最小值作为整个数据包的优先级判断依据(9～11行).

4)将聚合的包与其他数据包一起根据EDF方法计算的优先级依次分配通信资源，若优先级较高，可直接将数据包传输至下一节点，若优先级较低，则根据调度规则令其在当前节点处等待下一时隙重新计算优先级排序(12～13行)，并更新数据流的传输状态与调度表(14～16行).

5)将整个超帧的资源都分配完后可得到数据流调度表(17～20行).

EDF-PA算法的伪代码如算法1所示.

算法1.考虑数据包聚合的最短截止时间调度算法

输入：网络拓扑G=(U，V)，数据流F={f1,f2,…fj,…)，信道数目M，网络超帧P，聚合有效负载长度上限Smax

输出：sche[1…M][1…P]

1.初始化调度表sche[1…M][1…P]

2.whilep!=0do

3.ifP-p

4.return不可调度信息

5.else

6.fori=1to{R}

7.if节点i存在多条数据流有相同下一跳节点andsumsi

8.在当前节点聚合数据流

9.newd=mind(f1,f2,…fm)

10.endif

11.endfor

12.用EDF调度方法为数据流分配M条信道

13.更新各数据流的传输状态

14.foriinM

15.sche[i][p]=i→next[i]

16.endfor

17.p- -

18.endif

19.endwhile

20.returnsche[1…M][1…P]

基于EDF-PA方法，图2的无线网络数据流模型示例中数据流f1仅与数据流f3在第5时隙的8-9链路聚合传输，此时3条数据流均可调度.

4.2 优化数据包聚合的最短截止时间调度算法

上节提出的EDF-PA方法虽然能有效提高网络资源利用率，但并不能保证得到聚合数据包最多的调度结果.为进一步提高重叠区域数据包聚合度，本节提出了优化的数据包聚合的最短截止时间调度方法(Earliest Deadline First Scheduling Method considered on Optimized Packet Aggregation，EDF-OPA).

EDF-OPA算法检测到EDF-PA调度表中聚合后数据包到达目标节点后产生延迟等待时，以数据流可调度性为约束，令满足约束的数据流主动聚合等待，等待下一个数据包进行聚合.因此，主动聚合等待的方式在满足高优先级数据流可调度性的约束下，通过牺牲少量时隙资源作为额外的等待时间消耗，等待下一个到达的数据包进行聚合.有效提高重叠区域数据包聚合度，充分利用原本调度表中因传输冲突而不可占用的信道资源.同时，节省出来信道资源可以分配给其它无传输冲突的数据流或原本不可调度的数据流，提高信道资源利用率.EDF-OPA算法通过牺牲部分时隙资源换取更高的聚合度及信道资源利用率，实现系统性能的二次提升.虽然算法的时间复杂度变大，但由于算法离线完成，仍能满足实际工业应用的实时性要求.

EDF-OPA算法的初始化与聚合调度过程与EDF-PA算法相同(1～13行).在聚合调度的同时，EDF-OPA动态检测调度表，若在某个时隙检测到聚合数据包到达目标节点后产生延迟等待，可在满足可调度性约束下，令这个包主动等待一个不会产生冲突的时隙(14～17行).返回上一时隙重新根据EDF调度分配通信资源，更新数据流的传输状态和调度表(18～23行).将整个超帧的资源都分配完后可得到优化的调度表(23～27行).

EDF-OPA算法的伪代码如算法2所示.

算法2.优化数据包聚合的最短截止时间调度算法

输入：网络拓扑G=(U，V)，数据流F={f1,f2,…，fj，…)，信道数目M，网络超帧P，聚合有效负载长度上限Smax

输出：sche[1…M][1…P]

1.初始化调度表sche[1…M][1…P]

2.whilep!=0do

3.ifP-p

4.return不可调度信息

5.else

6.fori=1to{R}

7.if节点i存在多条数据流有相同下一跳节点andsumsi

8.在当前节点聚合数据流

9.newd=mind(f1,f2,…fm)

10.endif

11.endfor

12.用EDF调度方法为数据流分配M条信道

13.ifM>count(p时隙可传输数据流)

14.finde((e=(Vu,Vv)in

sche[M][p+1]&

(Vu,Vv∃/sche[M][p]))

15.令链路e等待至p时隙再传输

16.p=p+1

17.重新根据EDF调度方法分配信道

18.更新各数据流的传输状态

19.foriinM

20.sche[i][p]=i→next[i]

21.endfor

22.endif

23.p- -

24.endif

25.endwhile

26.returnsche[1…M][1…P]

4.3 复杂度分析

EDF-PA算法需遍历条数据流中的最长路径范围，并在每个时隙计算数据流的优先级并排序，令网络中数据流路径的最大长度为C，则EDF-PA算法的时间复杂度为O(P×|F|2×log|F|×C).EDF-FF算法[12]判断聚合时，同样需要查找重叠链路，复杂度与EDF-PA相同.EDF-OPA算法需重新查找数据包主动聚合等待所在时隙中其它|F|-1条数据流.令可以主动等待的数据包数目为Y，其时间复杂度为O(P×|F|2×log|F|×C+(|F|-1)×Y).在调度方法的实际执行过程中，本文提出的算法提高了数据的聚合度，因此会减少网络传输的链路数，所以实际调度执行时间要比理论计算值更小.

5 仿真实验与分析

5.1 实验配置

实验测试平台采用的工作站相关配置为：Intel(R)Xeon(R)W-10855M @2.80GHz 12核处理器，128GB内存，基于64位的Win 10系统.采用Python软件的版本为3.7.

网络参数设置如下：网络边密度取值为σ=0.7.边密度的设置参考文献[20]，δ取值较大保证网络中任意两个设备节点可通过一系列其他节点相互连通，构成各数据流的路径.源节点和目的节点数与网络设备总数比值为ε，ε值越大意味着网络中源节点—目的节点对的数目越多.数据流数量越多，网络负载越大，这里网络节点可重复被选为源节点或目的节点.本节仿真设置比真实情况更大的网络负载来充分展现算法性能.丢包率l表示数据流路径上的每两个相邻节点间的通信链路都有l%的概率传输失败.此外，网络设备数目为|V|与网络中数据流数目存在如下关系[20]：

(12)

对同一网络配置将随机生成200个数据流测试集，计算每组测试集中满足截止期数据流K占数据流N总数的比例计算得到当前测试集的调度成功率，故，实验结果中每点值可通过计算200组测试集调度成功率的平均值得到.通过上述参数设定方式，有效保证本文对算法性能的分析可以合理真实的反映工业无线网络聚合调度方法的实际性能.

5.2 性能评价指标

选取调度成功率(Scheduling Success Rate，SSR)与平均执行时间两种性能指标对本文提出的聚合调度方法进行评估.调度成功率指根据网络参数生成一定数量的随机测试网络，所有数据流可成功调度的测试用例数目K与总测试用例数目N的比值，比值越大表示算法的调度能力越强.

(13)

平均执行时间(Average Execution Time，AET)通过统计全部的测试网络中调度成功花费的时间与调度成功的测试集数目的比值，比值越小表示算法的时间开销越少，执行调度的速度越快.

5.3 实验结果分析

本节仿真实验从实际的工业应用出发，搭建基于工业无线标准WirelessHART协议的网络模型，并根据真实的工业无线系统采集的数据特征设计仿真数据.为清晰反映算法性能，本节仿真实验中的网络负载比真实工业情况的网络负载更大；并通过观测符合真实工况的多个关键参数动态变化对调度成功率的影响多方面评估算法性能，验证其合理性与通用性.

图3 不同网络规模下调度成功率对比Fig.3 Comparison of SSR under different network scales

图4为各算法在不同网络规模下的平均执行时间对比结果.参数配置为ε=0.8，则|F|=|V|×0.4，可用信道数目m=6，丢包率l=3%.如图4所示，所有算法的平均执行时间都随着网络规模的扩大而不断增加，3种聚合调度算法的平均执行时间均高于经典的EDF调度方法与LLF调度方法.因为EDF-PA与EDF-FF调度算法需要耗费一定的时间查找路径重叠可能聚合的数据流，而EDF-OPA在此基础上需找到可以主动聚合等待的数据流，所以复杂度均大于两种经典的动态调度方法，验证了4.3节中各算法的时间复杂度.由于本文提出的算法离线实现，可以满足工业无线网络的实时性需求.

图4 不同网络规模下的平均执行时间对比Fig.4 Comparison of AET under different network scales

图5 不同数据流数目下的调度成功率对比Fig.5 Comparison of SSR under different numbers of flows

图5表现了丢包率分别为l=0%与l=1.5%时不同数据流数下的调度成功率对比结果，其中设备数目分别为|V|=50，可用信道数M=5.如图5所示，所有算法的调度成功率都随着数据流数量的不断增加而降低，但本文提出算法性能始终最优.原因是数据流数量增加导致网络负载持续增大，数据流传输冲突的情况加重，将传输冲突的数据流安排在不同时隙需要耗费更多资源，部分数据流无法在截止时间前传输至目的节点，所有算法的调度成功率都呈下降趋势.但EDF-PA算法可以有效缓解传输冲突，提高网络调度成功率；EDF-OPA算法比起EDF-PA算法可以更加充分利用空余信道资源，进一步提高网络的调度成功率.图5(a)和图5(b)对比可知，当网络丢包时，所有算法的调度成功率会下降，但EDF-OPA算法为不可调度数据流安排信道资源，尽量降低丢包对调度成功率的影响.

图6表现了丢包率分别为l=0%与l=2%时，不同信道数目下的调度成功率对比结果.参数配置为ε=1.6，设备数目为|V|=70，|F|=|V|×0.8.如图6所示，在网络设备数目与数据流数量不变时，所有算法的调度成功率都随着信道数目的增加而不断提高，且本文提出的算法性能十分优越.这是因为信道资源增加意味着网络中可利用的通信资源更加充足，同时传输的数据流数目随之增加，调度成功率获得提升.EDF-PA算法的调度成功率在开始时增加趋势较为明显，但当信道数目增加至一定值时，其增幅逐渐平缓，原因是虽然可用的信道资源增多，但存在着传输冲突无法保证数据流能够使用全部的信道资源；EDF-OPA算法比起EDF-PA算法可以更有效的缓解传输冲突，因此即使网络中数据流数目较多，在信道资源较为充足时，调度成功率几乎达100%.由图6(a)和图6(b)对比可知，丢包率增加时，所有算法的调度成功率下降.

图6 不同信道数目下的调度成功率对比Fig.6 Comparison of SSR under different channel numbers

图7 不同资源利用率下的调度成功率对比Fig.7 Comparison of SSR under different resource utilization rates

图8 不同丢包率下的调度成功率对比Fig.8 Comparison of SSR under different packet loss rates

6 总 结

本文研究了网状拓扑下的工业无线系统实时调度问题.为减少数据流传输对网络资源的需求，首先提出了EDF-PA算法.在路径重叠区域采用基于优先级排序被动聚合等待的方式聚合数据包，降低数据流间的传输冲突，提高系统整体传输效率.在此基础上，为进一步提高重叠区域数据包聚合度，提出改进算法EDF-OPA采用主动聚合等待的方式，以数据流可调度性为约束，最大化特定重叠区域的数据包聚合度，提高信道资源利用率.本文选取调度成功率与平均执行时间作为评价指标与传统的调度方法和聚合调度方法对比分析.仿真结果表明，本文提出的两种算法可以有效提高调度成功率，在网络负载较高但资源有限的情况下，对比传统聚合调度方法调度成功率可提升35%；在网络丢包严重时，调度成功率可提升20%.后续将搭建工业无线网络的硬件测试平台，在平台中测试算法的性能；并考虑真实场景中的高温、电磁干扰等恶劣环境因素对网络通信状况的影响，进一步优化与改进本文提出算法的性能.