考虑链路重传的工业无线网络确定性调度算法

王 恒 刘清华 李 敏 谭 帅

工业无线网络是工业物联网的重要支撑性网络,具有部署方便、组网灵活、易于维护等优点,对网络数据的传输有严格的可靠性和实时性要求[1−2].现有工业无线网络采用了跳频、重传、多路径等机制,以保证数据能够可靠的到达目标设备,避免工业环境中各种干扰的影响;同时支持时钟同步、确定性调度等技术,使网络能够满足数据收发的实时需求,确保数据在规定时间内传输完成[3−5].此外,工业无线网络通常还使用多信道机制和时分多址接入(Time division multiple access,TDMA)技术为网络中的数据传输提供必需的时槽和信道等通信资源[6].

工业无线网络中的确定性调度技术通过高效配置时槽与频点资源,满足网络中每条通信流的截止时间约束,以保证网络数据的实时传输.由于该问题属于NP 完全问题[7],通常针对不同的网络情况,采用不同的求解策略和目标对其进行研究.现有的工业无线网络主要包括WirelessHART、WIA-PA、ISA100.11a 等网络[8],在上述网络中对确定性调度的研究已取得了一定的成果.围绕WirelessHART标准,在分析调度所需基本前提的基础上,文献[9]基于干扰感知松弛度,提出了C-LLF (Conflictaware least laxity first)调度算法,通过在当前时槽计算网络中所有就绪链路的干扰感知松弛度,使松弛度小的链路优先获得网络资源,取得了较高的调度成功率.文献[10]对混合优先级情况下的实时通信进行了研究,提出了一种基于固定优先级调度的端到端时延分析方法.文献[11]提出了一种分布式WirelessHART 实时调度方案,通过时间区间分配机制,设备只需执行本地调度策略,无需在网络中传递全局调度信息,从而降低了网络资源开销.文献[12] 给出了一种基于迭代的多跳Wireless-HART 调度算法,在截止时间限制下能够最小化端到端传输时延.文献[13]对多个WirelessHART 网络共存场景下的调度问题进行了专门研究,利用有效的频点管理和流调度策略,实现了网络的相互隔离与数据的可靠传输.针对WIA-PA网络的调度问题,文献[14]提出了适用于WIA-PA 网络的基于回溯法的最优调度算法和基于最小时间松弛度优先的调度算法,并针对WIA-PA 网络分为簇内通信和簇间通信不同阶段的特点进行了优化设计.文献[15] 基于跳链路的思想,提出了一种频点分配方案,能够有效利用网络中的频率资源,减少干扰反应时间.针对ISA100.11a 网络的调度问题,文献[16]为满足实时性要求,设计了容纳实时消息、报警消息和非实时消息的超帧,并以此提出了基于ISA100.11a 专用时槽的消息调度方案.除了围绕典型工业无线网络标准进行研究外,还有一些工作针对特定的工业无线网络场景进行了调度算法优化设计.文献[17]针对扰动存在下的工业无线网络提出了一种分布式调度架构,通过非中心化的本地决策,实现了对扰动的快速调度响应.文献[18]针对时间触发通信流与事件触发通信流并存的网络场景,在分析虚拟周期、时槽复用等基础调度方法的基础上,提出了一种混合型中心式调度算法,获得了接近于最优方法的调度性能.文献[19]考虑不同网络位置拥有不同可用频点集的场景,提出了面向树型工业无线网络的启发式汇聚调度算法,实现了对差异化链路可用频点集的优化支持.对于拥有多个射频收发单元的工业无线现场设备,文献[20]提出了一种综合考虑时槽、频点和射频接口分配的调度算法,提高了调度成功率.文献[21]针对截止时间随机可变的场景,通过分析待调度系统的状态、动作空间、条件转移概率和成本函数,将该场景下的调度问题转换为不可观测的马尔科夫决策问题,并提出了基于平均截止时间优先的低复杂度求解方法.文献[22]设计了一种考虑数据到达率的调度方法,加快了网络响应时间.文献[23]考虑了网络中链路选取过程与时槽调度过程之间的前后关联性,提出了一种链路与时槽的联合优化分配方案,改善了网络调度性能.

此外,考虑到工业无线网络是无线传感器网络的行业应用,一些面向通用无线传感器网络所提出的调度算法,对于工业无线网络确定性调度问题的研究,仍具有一定的参考价值.文献[24−26]针对无线传感器网络中的调度问题,探索采用粒子群算法、模拟退火算法、遗传算法等方法进行解决.文献[27]利用机器学习技术,提出了一种基于优先级感知的数据交换调度算法,改善了无线传感器网络的平均时延性能.

工业现场环境复杂、干扰众多,使得工业无线网络中的数据传输经常发生丢包现象.丢包会导致数据传输失败,影响网络正常的调度运行.对抗丢包问题的典型方法包括自动重传请求(Automatic repeat-request,ARQ)、冗余多路径等.重传是一种简单有效的机制,在三种主要的工业无线网络标准中都得到了支持,它通过为传输链路分配额外的时槽、频点资源,在传输失败时利用这些通信资源重新发送数据,避免网络丢包的影响,提升数据通信的可靠性.

围绕工业无线网络调度中的丢包与重传问题,文献[6]、[9]在仿真实验中考虑了网络丢包,发现丢包的存在显著降低了调度成功率.文献[28−29]在工业场景中将ARQ 与节点间的中继协作联合使用,进一步降低了系统丢包率;文献[30−31]在工业网络路由策略中引入了重传操作,提高了路由方法的可靠性,但文献[28−31]均未将重传机制与确定性调度深入结合.文献[32]考虑了ARQ 机制对调度的影响,但只局限在单跳网络内,没有解决更重要的多跳网络重传调度问题.针对以上问题,本文面向使用多信道和TDMA 机制的多跳工业无线网络,结合通信流的截止时间条件,建立了支持链路重传机制的调度网络模型;在分析可调度条件和优先处理条件的基础上,分别针对数据包传输失败后立即进行持续重传的场景和在一定时间区间内完成重传的场景,提出了相应的时槽、频点调度算法,在满足传输确定性的前提下,有效提升了网络可靠性.

1 模型建立

考虑一个基于时槽方式运行的多信道工业无线网络G=(V,ξ) ,V表示网络中所有设备,ξ表示设备之间的通信链接,可用信道频点数为K.网络中存在J条通信流F1,F2,···,FJ,每条通信流通过由多条通信链接构成的传输路径,将数据包从起始设备发往最终设备,如图1 所示.对于任意一条通信流Fm,其数据包产生周期为Pm,传输路径包含的通信链接数为φm,数据包产生后需要在给定的截止时间Dm内到达最终设备.设网络中每条通信链接的重传次数为λ,则需满足:φm(λ+1)≤Dm ≤Pm.

图1 网络模型图Fig.1 Network model

本文确定性调度的任务是在考虑重传条件下,通过安排每个时槽各个频点上的通信链接,使每条数据流所产生的数据包均能在指定时限内确定到达最终设备.设所有通信流周期的最小公倍数为T,称之为宏周期.若在当前宏周期T内,采用某种调度策略,能够使每条通信流的各个数据包均能按时到达,则在下一个宏周期T内,重复执行该调度策略,就能够继续保证数据流的确定性传输.因此,调度任务可转化为研究和设计一个宏周期T内的调度策略.显然,在宏周期T内,数据流Fm将 发送T/Pm个数据包,其中第n个数据包在Am,n=(n −1)Pm+1时刻从起始设备产生,需在截止时刻Bm,n=(n −1)Pm+Dm之前到达最终设备.

在对工业无线网络中每个时槽的通信链接进行调度配置时,主要面临两个方面的制约.一是频点数制约,在同一时槽同一频点只能放置一个通信链接,不同频点可放置不同通信链接,但在同一时槽能够同时工作的通信链接数不能超过系统所提供的频点数;二是通信链接收发制约,在ISA100.11a、WirelessHART、WIA-PA 等主流工业无线网络中,设备通常使用单根天线,采用半双工方式工作,无法同时完成射频的发送和接收,这使得若在当前时槽的某个频点安排了一个通信链接,则以该通信链接发送方进行发送或接收,以及该链接接收方进行发送或接收的所有通信链接,与该通信链接均构成干扰链接,都不能再在当前时槽进行安排.下面将在考虑上述两种制约条件的基础上,对重传场景下的调度问题进行描述.令 Γg(p,q)∈{0,1}表示在时槽g,设备p与设备q之间所建立的通信链接的状态.当p与q之间的通信链接被安排在时槽g进行数据收发,即该通信链接处于活跃状态时,Γg(p,q)=1 ;反之,Γg(p,q)=0 .此外,定义 Hg(p) 表示在时槽g所有以设备p作为发送方的通信链接集合,Θg(p)表示在时槽g所有以设备p作为接收方的通信链接集合.以Lm,n表示通信流Fm的第n个数据包在不考虑重传时槽配置情况下所经历的传输时延,则本文所研究的调度问题具体描述如下:

式(1)采用不等式的形式进行描述,表明在考虑重传时槽及其配置的场景下,所有通信流的数据包传输时间均应小于或等于其各自的截止时间;式(1a)对应频点数制约条件,式(1b)和式(1c)则对应通信链接收发制约条件.

2 调度优先级分析

确定性调度策略所操作的基本单元是通信链接.下面将在干扰感知松弛度理论的基础上[9],进一步考虑重传因素影响,对重传场景下通信链接的属性及其调度优先级进行扩展分析.

在宏周期T内,对于数据流Fm,其第n个数据包从产生时刻开始,将沿着对应路径经过一步步的转发传输至最终设备.这条传输路径由一系列相邻的通信链接组成,设µi=(p,q) 是其中一个通信链接,该通信链接的发送方是设备p,接收方是设备q.假设设备q与最终设备之间相隔的跳数为χi,在时槽g处数据包还需要传递oi个通信链接后才能到达设备p,则通信链接µi的有效调度区间为:

其中,si是通信链接µi的就绪时间,

wi是通信链接µi的截止时间,

通信链接µi需要在上述时间范围内完成传输,如图2 所示,否则将导致调度失败.

图2 通信链接 µi 的有效调度区间Fig.2 Effective scheduling interval of communication link µi

在时槽g处,若某个通信链接的所有前序通信链接都已执行,同时用于重传的通信链接也配置完成,则称该链接为就绪通信链接.所有就绪通信链接构成的集合称为就绪链接集.在重传场景下,对于某个就绪通信链接,除了需在其有效调度区间内安排传输外,还需在其传输之后安排λ次重传,这些重传动作所对应的通信链接称为重传通信链接.

本文在调度安排就绪通信链接和重传通信链接时,采用干扰感知松弛度作为链接排序的基本依据,在此基础上,进一步考虑不同重传类型及其特点,形成包括重传通信链路在内的各种链路的优先级.干扰感知松弛度由文献[9]提出,反映了通信链接调度的紧急程度.它既考虑了通信链接有效调度区间的长度影响,又考虑了潜在干扰通信链接数量的影响.该指标值越小,表征通信链接调度的急迫性越高.设在时槽g处,µi=(p,q) 是一个就绪通信链接,则其干扰感知松弛度表示为:

其中,Cp是由时槽g就绪通信链接集中,以设备p作为发送方,且有效调度区间与µi存在重合的通信链接的截止时间所构成的集合.εp是在时间区间[g,θ] 内设备p所参与的通信链接数量.

对于重传链接,干扰感知松弛度的计算方法需要进行扩展,尤其是区间重传方式.由于该方式下重传链接需在指定的时间区间内完成,故在计算松弛度时,所使用的有效调度区间上限还不得超过重传区间上限.两种重传方式的具体分类说明,将在下一节中进行描述.

3 确定性调度算法设计

面向工厂自动化应用所设计的无线网络,为了防止丢包,在点到点传输时普遍采用了确认帧(ACK)机制.发送方发送数据包后,将启动一个定时器.接收方正确接收到数据包后,将立即返回一个确认帧.若发送方在预定的定时间隔内收到确认帧,则视为数据包传输成功.当网络发生丢包,接收方没有收到数据包,或由于无线信道质量变差,接收方无法正确解码数据包时,接收方将不会反馈确认帧.发送方在定时器超时后若仍未收到确认帧,则认为传输失败,进而启动重传工作.在ISA100.11a 等工业无线网络中,还设计了否决帧(NACK)机制.当接收方发现接收的数据包错误时将反馈否决帧,此时发送方无需等待定时器超时即可进行重传.

在基于时槽机制运行的无线网络中,根据重传时机的不同,存在两类重传方式.第一类是持续重传.若当前时槽通信链接传输不成功,则在接下来的时槽中持续进行重新传输,直至传输成功或达到最大重传次数.第二类是区间重传.若当前时槽传输不成功,则在接下来的一段时槽区间内根据情况可以间断性的完成重传.持续重传具有实现简便的优点,而区间重传则具备更好的扩展性.无论采用何种重传方式,系统都需要为重传的实施调度安排相应的时槽、频点资源.下面将围绕不同的重传方式,提出对应的网络调度方案.

3.1 支持持续重传的调度方法

从持续重传的特点出发,系统在调度完一个就绪通信链接后,将在接下来的相邻时槽,立即且持续安排该就绪链接所对应的重传通信链接.结合干扰感知松弛度,本文设计了支持持续重传的确定性调度(Definiteness schedule with consequent retries,DS-CR)方法.

该算法以时槽为单位逐时槽进行调度.在每个时槽,待调度对象包括该时槽的就绪通信链接和重传通信链接.由于在持续重传方式下,对重传通信链接安排的紧急程度很高,故采用先调度重传通信链接,再调度就绪通信链接的方法,即重传通信链接的优先级总是高于就绪通信链接.在对重传链接进行调度时,需记录并处理数据包的重传轮数.重传链接调度完成后,以干扰感知松弛度指标值为依据,由小到大依次安排就绪链接的频点.该指标值相等时,则比较截止时间,进一步则继续比较通信流编号,数值小者优先安排.当一个通信链接被调度后,与该链接构成干扰的通信链接均不再在当前时槽进行配置.每个时槽采用同样的方式执行以上调度过程,直到每个通信链接及重传链接均调度完成或任一链接无法满足截止时间要求.算法1 描述了该方法的主要运行过程.

从无线传输的角度看,重传是一种时间分集机制.在系统拥有多个频点的条件下,还可在重新传输时进一步联合使用频率分集机制,能够获得更高的可靠性.DS-CR 算法在安排频点时,还可对同一通信链接的就绪链接和多个重传链接尽可能分配不同的频点.这样,当数据包在当前时槽某个频点传输失败后,下一个时槽将在不同的频点重新被传输,避免在受到干扰或质量变差的单一信道上重发数据包.

就绪通信链接的频点确定规则可根据调度次序,按频点编号从小到大依次设定.重传通信链接的频点则可在前序就绪链接或重传链接频点编号的基础上,采用循环增加的方式设定.当重传轮数超过系统可用频点数量时,至少确保相邻两次重传链接采用相异的工作频点.

算法1.支持持续重传的调度方法

3.2 支持区间重传的调度方法

根据区间重传的特征,系统在配置完一个就绪通信链接后,将在之后的一段时槽区间内,对该就绪链接所对应的重传通信链接进行配置.重传通信链接的分布可以是间断性的,但需在给定区间内全部安排完成.结合就绪链接和重传链接的干扰感知松弛度,本文设计了支持区间重传的确定性调度(Definiteness schedule with interval-working retries,DS-IWR)方法.

该方法仍采用逐时槽计算的方式进行调度.与DS-CR 方法不同的是,在每个时槽的调度过程中,系统既计算就绪通信链接的干扰感知松弛度,也计算重传通信链接的干扰感知松弛度,然后将计算结果一并由小到大进行排序,按次序进行调度.就绪通信链接的松弛度采用式(5)进行计算,重传通信链接的松弛度在此基础上,还需额外引入重传区间对有效调度区间的限制.算法2 描述了该方法的主要运行过程.

算法2.支持区间重传的调度方法

DS-IWR 算法同样可进一步结合频率分集机制,使数据包的每一次重传尽可能分布在不同的频点上.其中,就绪通信链接的频点确定规则与DS-CR方法相同,重传通信链接可采用同链接循环增加的方式,资源不足时至少确保相邻两次链接的工作频点不同.当不同通信链接所对应的重传链接频点值冲突时,则先匹配干扰感知松弛度高的链路的频点设定需求,松弛度低的重传链路越过冲突值进行循环相加,必要时采用相邻链接频点值相异的方法重新确定频点.

3.3 算法时间复杂度分析

本文提出的调度算法在运行过程中,需要在每个时槽对就绪通信链接的干扰感知松弛度进行计算.设系统中就绪通信链接数量的最大值为X,通信流跳数最大值为Y,根据干扰感知松弛度计算方法,DS-CR 方法的时间复杂度是 O (T ·Y ·X2) .与DS-CR 方法不同,DS-IWR 方法除了计算就绪通信链接的松弛度外,还同等计算重传通信链接的干扰感知松弛度,故其时间复杂度为 O (T ·Y ·X2·(λ+1)) .在接下来的第4 节中,将对所提两种算法的运行时间进行仿真验证,并与其他算法进行对比分析.

4 仿真实验与分析

本节对所提出的DS-CR 和DS-IWR 两种调度算法进行仿真验证与对比分析.对比算法为四种经典实时调度方法和C-LLF 调度方法[9,33].表1 中列出了用于仿真比较的各种方法的基本原理.同时,为了更好地评价调度算法在测试过程中的性能,本节选择调度成功率和算法平均计算时间作为评价指标.调度成功率的计算方法如下:假设生成W个测试网络,依次执行某调度算法,若能够成功完成该网络中所有数据流调度的测试网络个数为C,则该算法在本次测试中的调度成功率为C/W.

表1 用于仿真比较的各个方法的原理Table 1 Principle of each method in simulation comparison

在Intel G4650 处理器、Win10 系统上对上述调度算法进行仿真实现.仿真区域长度和宽度均为一百米.在该区域内采用类似文献[9]的方式以随机形式构建网络.每种测试场景随机构建一万个网络,通过所提方法和对比方法对网络进行调度,获得相应的评价指标结果.在仿真中,d是设备数量,β ∈(0,1]是起始设备与最终设备所构成的通信对比重,ϑ∈(0,1] 是边密度,K是可用频点数量,λ是重传轮数,η是重传区间,α是丢包率,通信流数量采用β×d/2设定,边数量采用 (d×(d −1)×ϑ)/2 设定.每条通信流的起始设备按设定的时间间隔周期性的产生数据包.不同通信流的数据包产生周期在P′=2x～y范围内以均匀分布(四舍五入取整)的方式随机构造,通过υ∈(0,1] 设置通信流截止时间取值上限所占比重.

4.1 调度算法基本性能与计算时间测试

对调度算法在不同设备数量下的基本性能进行测试.在丢包率为百分之三的情况下,设备数量从10 开始,依次递增10,直至60.频点数量为8,重新传输轮数为3,重新传输时间区间为6 个时槽,其余参数设定为:ϑ=0.8 ,P′=27～9,υ=0.75,β=0.6 .

调度成功率与设备数量之间的关系如图3 所示.该图表明,设备数量增加,会引起各个算法成功率的降低,但DS-CR 算法和DS-IWR 算法通过在调度过程中对重传进行优化,缓解了数据丢包对调度的影响,在不同的设备数量下调度成功率都显著优于对比算法;同时,DS-IWR 算法比DS-CR 算法具有更好的调度效果,这是由于相比于持续重传,区间重传能够在一个区间范围内灵活处理调度资源,从而进一步提高了调度成功率.

图3 调度成功率与设备数量关系图Fig.3 Relationship between schedulable ratio and device number

表2 列出了各个算法在不同设备数量和通信流个数下的平均计算时间.表中数据表明,当设备数量达到20、通信流条数达到6 及其以上时,参与对比的五种算法的平均计算时间低于所提算法.由于所提算法在运行过程中,增加了对重新传输链路的调度,故花费了更多的计算时间.对于本文所提出的两种调度算法,表2 表明DS-CR 算法的平均计算时间小于DS-IWR 算法,从而验证了第3 节中对两种算法时间复杂度的理论分析,因为DS-CR 算法的时间复杂度 O (T ·Y ·X2) 低于DS-IWR 算法的时间复杂度 O (T ·Y ·X2·(λ+1)) .需要说明的是,虽然为了提升可靠性,所提算法以花费相对较多的时间开销作为代价,但在设备数量和通信流条数都比较大的情况下,所提两种算法的计算时间仍未超过300 ms,所需计算时间保持在一个相对较小的水平.

表2 各个调度方法的平均计算时间 (ms)Table 2 Average execution time of each scheduling method (ms)

综上所述,本文提出的调度算法相比对比算法能够取得更高的调度成功率,在满足网络数据传输确定性的同时,保证了丢包情况下的数据传输可靠性,但需要更多的时间开销.因此,在进行网络设计时,可根据不同场景的特点,综合权衡调度成功率和花费时间的重要性来进行算法选择.当网络设备数较少、频点质量较好时,若网络拓扑变化剧烈导致调度算法需频繁执行,且对获取调度结果的时间要求限制在百毫秒以下,可考虑采用经典的调度算法.此时,较小的设备数和良好的频点质量能够适当减缓经典算法调度成功率低的影响.若网络能够接受百毫秒级的调度运行时间,本文所提出的算法则是优选,尤其在网络设备数较多或受丢包影响较明显的场景下,所提算法能够发挥更大的调度成功率优势.

4.2 调度算法在不同网络参数下的性能测试

本节进一步对调度算法在不同的重传区间、丢包率、信道质量、通信对所占比例、截止时间上限比例、周期取值范围、频点数下的性能进行仿真对比.由于DS-IWR 算法采用了区间内重传的方式,区间的取值会影响其性能,故仿真观察了该算法在不同重传区间下的调度结果,如图4 所示.仿真中设置η从3 个时槽开始,依次递增1 个单位时槽长度,直至12 个时槽,其余参数情况为:d=40,K=8,P′=27～9,α=3 %,β=0.6,λ=3,ϑ=0.8 ,υ=0.75 .

从图4 可以看出,当重传区间小于6 个单位长度时,DS-IWR 算法的调度成功率随着重传区间长度增加而提高;当重传区间大于6 个单位长度时,算法的调度成功率反而出现下降的趋势,且长度增加的越大,下降的幅度越明显.这种现象出现的原因在于,当区间在一定范围内增大时,传输失败的数据报文有机会在更宽的时间段内进行重传选择,避免了部分报文因重传时间段窄、优先级低导致的无法及时重传问题,提高了调度成功率.但当区间增加到一定程度后,若再继续增加则会产生两个方面的问题:一是对于需要重传的报文本身,有可能选择大时间段的靠后时槽实施重传,这样虽然当前链路能够传输成功,但由于花费时间过多,会导致剩余跳数的链路可调度时间余量变小,增加报文调度失败的概率;二是当多个数据报文的重传区间设置过大时,会导致正常报文与重传报文的冲突加剧,反而降低成功率.因此,重传区间的设置并非越大越好.根据图4 中成功率最高点所对应的区间取值,在本节后续仿真实验中,采用λ=3,η=6 的网络参数设置.

图4 调度成功率与重传区间关系图Fig.4 Relationship between schedulable ratio and retransmission interval

图5 是所提算法与对比算法在不同链路丢包率下的测试结果.仿真中设置α从 0 开始,依次递增5 %,直至50 %.其余参数情况为:d=30,K=8,P′=27～9,η=6,β=0.6,λ=3,ϑ=0.8,υ=0.75 .图5 表明,各种算法的调度成功率随着丢包程度的加剧呈现下降趋势,但所提出的两种调度算法在链路丢包率增加时的性能明显优于对比算法,原因在于当数据传输失败时,所提算法可以通过重传链路进行数据的重新发送,从而在一定范围内能够较好地缓解数据的丢包问题.

图5 调度成功率与丢包率关系图Fig.5 Relationship between schedulable ratio and packet loss rate

在工厂中部署的工业无线网络,往往所处环境恶劣,电磁情况复杂,从而对无线频点的传输特性产生重要影响.根据文献[34]对工业无线网络频率特性实验测试与建模的调研,Nakagami-m 分布是其中一种主要的信道衰落类型.因此,本文采用Nakagami-m 信道模型,对调度算法在不同信道质量下的性能进行仿真.Nakagami-m 模型的概率密度函数为:,其中pm为形状参数,ps为尺度参数,Γ (·) 表示Gamma函数.仿真主要关注由信道质量改变所引起的通信中断对调度性能的影响.在仿真中设定网络的频谱效率为1 b/s/Hz,各设备的平均信噪比为5 dB,其余参数设置为:d=10,K=8,P′=27～9,η=6,β=0.6,λ=3,ϑ=0.8,υ=0.75.由于 N a kagami-m 信道的平均质量由pm和ps决定,故对(pm,ps) 分别取值 ( 3,1) ,( 3,0.5) 和 ( 1,0.5),在信道平均质量逐渐变差的条件下对所提算法和对比算法进行性能测试,结果如图6 所示.从图中可以看出,所提出的两种算法在不同信道质量下的调度性能均优于对比算法,且在信道质量恶化的情况下,性能下降程度小于对比算法,表明所提算法对工业通信环境具有良好的适应性.

图6 调度成功率与信道质量关系图Fig.6 Relationship between schedulable ratio and channel quality

针对起始设备与最终设备所构成的通信对,其所占比重对调度成功率的影响如图7 所示.通信对比重从20 %开始,依次递增10 %,直至100 %,其余参数情况为:d=30,K=8,P′=27～9,η=6,α= 3 %,λ=3,ϑ=0.8,υ=0.75.从图7 中可以看出,所提方法在同等条件下的性能超过了其他方法.随着通信对所占比重增加,会导致通信冲突加大,从而引起调度成功率降低.

图7 调度成功率与起始设备和最终设备所构成的通信对所占比重关系图Fig.7 Relationship between schedulable ratio and proportion of communication pairs from source devices to final destination devices

截止时间取值上限比重与成功率之间的关系如图8 所示.上限比重从5 %开始,依次递增10 %,直至100 %.其余参数情况为:d=30,k=8,P′=27～9,η=6,α= 3 %,β=0.6,λ=3,ϑ=0.8.该图表明,在截止时间取值上限比重增加的情况下,由于其他算法缺乏丢包应对机制,受制于网络丢包影响,无法有效地改善调度效果,调度成功率维持在一个相对变化较小的范围;而与之相对比的是,所提两种算法的调度成功率均得到了显著改善.

图8 调度成功率与截止时间取值上限比重关系图Fig.8 Relationship between schedulable ratio and proportion of maximal deadline

图9 是两种调度算法与对比算法在不同周期取值范围下的调度成功率.其中,P′取三组值,分别为 28～9,27～10,和 26～11,其余参数情况为:d=30,K=8,η=6,α= 3 %,β=0.6,λ=3,ϑ=0.8,υ=0.75.从图9 中可以观察到,所提算法的调度性能优于对比算法,且周期范围为 28～9时调度成功率最高.该项仿真表明,确定合理的周期取值区间,有利于改进所提算法的调度性能.

图9 调度成功率与周期范围关系图Fig.9 Relationship between schedulable ratio and period range

调度成功率与可用频点数量之前的关系如图10所示.频点数从2 开始,连续增加到8,其余参数情况为:d=40,P′=27～9,η=6,α= 3 %,β=0.6,λ=3,ϑ=0.8,υ=0.75.图10 表明所提调度算法的调度成功率在频点数量变化的情况下高于对比算法.从该图中还可以看出,由于对比算法未考虑调度重传,在固定的周期范围内,每次调度过程都受到丢包的影响,频点的增加并未达到有效提高调度成功率的效果.而所提算法的成功率在可用频点数量从2 增长到4 时变大,后续再增加频点数则基本保持不变.这种现象出现的原因在于,增加频点数量,能够提高调度容量;但当频点资源供应充足时,链路传输冲突则成为制约调度能力的主要因素,从而影响调度成功率的进一步提高.

图10 调度成功率与频点个数关系图Fig.10 Relationship between schedulable ratio and channel number

根据以上在不同网络参数下的调度算法性能测试结果可知,随着网络参数的改变,调度算法的性能也会随之发生变化.因此,在使用调度算法时需要根据具体情况尽可能合理地选择网络参数,提高调度算法成功率.具体到实际的工业无线网络设计,本文所提出的两种调度算法适合应用在对数据传输可靠性要求高的监视类应用或过程控制应用场景中.其中,DS-CR 方法执行简单,易于实现在低复杂度的工业网络中;而DS-IWR 算法调度效果更好,适合应用在资源相对富裕、操作更加灵活的工业网络中.值得说明的是,在调度算法中引入重传机制后,会产生两方面的影响.一方面,借助于建立重传链路,失败的包可以再次被调度传输,缓解了因为丢包导致的调度失败问题;另一方面,重传链路的引入会占用一定的时槽、频点资源,在一些网络资源比较紧张的场景中,有可能会引起部分通信流的资源延迟安排,影响这些数据传输的实时性.因此,在确定性调度算法中考虑重传问题,可视为在数据传输实时与可靠之间进行均衡.

5 结束语

本文在建立工业无线网络调度模型的基础上,分析了通信流调度的必要条件和动态优先级确定方法,针对持续重传和区间重传两种重传策略,分别提出了DS-CR 算法和DS-IWR 算法.仿真结果表明,所提出的两种调度算法相比经典的实时调度算法和C-LLF 算法,在网络数据丢包的情况下,可以取得更高的调度成功率,保证了传输可靠性,实现了数据传输实时与可靠之间的有效均衡.下一步将考虑对调度算法与路由协议进行联合设计,通过双重优化进一步提升网络整体调度性能.