Deterministic Scheduling Algorithm With Priority Classification for Industrial Wireless Networks
-
摘要: 确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况, 基于多信道时分多址接入(TDMA)技术, 在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上, 对网络进行调度预处理, 进而排除参数不合理的网络, 并向网络管理者反馈.对于通过预处理的网络, 调度算法优先为高优先级数据流的链路分配时隙和信道资源, 而对属于同一类优先级的数据流, 提出一种基于比例冲突空余时间的调度方案, 在满足可调度性条件的前提下, 根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明, 所提出的调度算法可以取得较高的网络调度成功率.Abstract: Deterministic scheduling technology has a significant impact on the real-time and deterministic data transmission in industrial wireless networks. This paper considers the case that end-to-end flows in industrial wireless networks have a property of priority classification, and adopt multi-channel time division multiple access (TDMA) technology. On the basis of analyzing the delays of lower priority flows due to both link conflict and channel contention caused by higher priority flows, there is a pre-processing scheduling for testing networks firstly. Therefore, some networks with unreasonable parameters can be excluded, and this will inform network administrator for further processing. For networks passing the test of pre-processing scheduling, the scheduling algorithm gives preference to allocate time slots and channels to link with higher priority flows. For the flows with the same priority, a scheduling scheme based on proportional deadline and conflict is also presented, which allocates the time slots and channels according to the values of proportional deadline and conflict in ascending order for flows that meet the schedulability condition. Results show that the proposed scheduling method can achieve a higher schedulable ratio.
-
Key words:
- Industrial wireless networks /
- deterministic scheduling /
- priority classification /
- pre-processing scheduling
-
工业无线网络是对现有工业通信技术的一种强有力的补充, 具有快速部署、高可靠性以及节约成本等特性.随着工业物联网的不断发展, 工业无线网络将会被更大范围的应用[1-2].当前国际上出现了三项主流的工业无线网络技术, 分别是WirelessHART标准、ISA100.11a标准以及我国自主制定的WIA-PA (Wireless networks for industrial automation-process automation)标准[3].其中确定性调度问题作为工业无线网络的一个重要研究方向, 在三项标准中通过多信道时分多址接入(Time division multiple access, TDMA)机制来提供调度所需要的时隙和信道资源[4].目前, 工业无线网络的确定性调度问题已经被证明是一个NP-hard问题[5].
在与工业无线网络密切相关的无线传感器网络领域, 网络调度问题被广泛研究, 其研究成果对于解决工业无线网络的调度问题, 具有一定的参考价值.在无线传感器网络中, 已有的网络调度算法包括元启发式算法(例如粒子群算法)、图着色法等调度方法[6-7], 以及考虑数据聚合、能量消耗、优先级策略等目标的调度算法[8-10].其中, 确定性调度问题的研究目标是考虑如何合理的分配时隙、信道等通信资源, 使网络中的数据流满足规定的端到端时延约束[11-15]. Kim等采用模拟退火法和粒子群算法对无线传感器网络中的调度问题进行了优化研究, 并对两种算法进行了分析比较[6]. Kang等探索了分簇无线传感器网络下基于TDMA机制的分布式图着色调度算法, 该算法包含着色和调度两个阶段, 增加簇内吞吐量的同时也降低了簇内传输延时, 但此算法没有考虑网络存在多信道资源的情况[7].贾杰等提出一种基于最大干扰度优先的链路调度算法, 令尽可能多的链路并行传输, 在调度周期以及能量消耗双重优化目标下获得不错的性能[9].李金宝等面向多信道无线传感器网络, 提出了最小化数据聚集延迟的调度算法[14].牛建军等对无线传感器网络中的分布式调度方法进行了系统讨论和分析[15].
具体到各种工业无线网络, 针对确定性调度问题的研究, 也取得了一定进展.针对WIA-PA网络, 文献[16]提出了面向中小规模网络和大规模网络的两种确定性调度方法, 结合WIA-PA网络的分层分簇特征进行了优化设计.针对ISA100.11a网络, 文献[17]研究了基于确定性调度的路径选择方法, 保障了传输路径的端到端时延.针对WirelessHART网络, Saifullah等提出了C-LLF (Conflict-aware least laxity first)调度算法[5], 该算法计算网络中当前时隙下所有处于释放态链路的冲突觉知松散度值, 越小的冲突觉知松散度就会优先在当前时隙的剩余可用信道上安排此链路.算法在网络可调度率上取得了良好的性能, 该算法考虑了多信道的情况, 但没有考虑数据流存在固有优先级属性的情况.文献[18]同样围绕WirelessHART网络, 对固定优先级下网络中端到端数据流的时延进行了分析, 为当前网络在基于时隙信道分配技术下是否可调度提供了一种指导思路, 但没有给出数据流存在固定优先级下具体的调度方法.综上所述, 以上针对工业无线网络和无线传感器网络调度问题的研究文献, 要么基于TDMA机制对优化目标进行启发式或元启发式调度, 但没有考虑工业无线网络中存在多信道时的情况; 要么研究了多信道TDMA机制下链路调度, 但没有考虑网络中数据流存在固有优先级属性的情况.此外, 对于同一优先级下存在多条数据流的情况很少有文献进行研究.
在工业无线网络中, 网络中的数据流本身是具有优先级属性的, 数据的优先级根据其业务应用的特点决定.例如WIA-PA标准规定了数据的四种优先级[19], 优先级从高到低排列分别为:处理网络管理控制与紧急告警的命令帧、用于工业自动化生产监控的过程数据、一般数据和非紧急的报警数据.在给定优先级个数限制下, 网络中会存在多条数据流具有同一个优先级的情况.此时对于确定性调度问题, 不仅要考虑时隙和信道资源的分配能满足网络所有数据流的时延约束要求, 还应该在全部数据流满足时延约束的前提下, 尽量保障高优先级的数据流优先分配时隙和信道.
因此, 本文针对多信道TDMA机制下数据流存在优先级分类属性的情况, 通过分析网络中高优先级数据流对低优先级数据流在最坏情况下造成的时延, 利用时延分析的结果对网络进行调度预处理, 达到排除一些参数不合理的网络的效果, 并反馈给网络管理者处理.对于通过预处理的网络, 在进行时隙和信道的分配时, 优先分配给高优先级数据流的链路; 对于优先级相同的链路, 则提出了一种基于比例冲突空余时间值的调度方案, 根据该值从小到大按序对各条链路进行调度.最终的仿真结果验证了提出的调度方案的正确性, 以及相比经典的优先级调度方法具有更高的调度成功率.
1. 确定性调度问题描述
1.1 网络模型
工业无线网络可以抽象为一个图$ G = (V, E) $, 其中$ V $是由网络节点$ \left\{ {v_0 , v_1 , v_2 , v_3 , \cdots , v_n } \right\} $构成的集合, 构成图的顶点, 其中$ v_0 $代表网关. $ E $代表网络中节点间的通信链路, 构成图的边.如果$ e(u, v)\in E $, 其中$ (u, v)\in V $, 则表示网络节点$ u $和$ v $在网络中建立了可靠的双向通信链路, 可以直接进行通信传输.如果节点$ u $作为数据发送设备, 节点$ v $作为数据接收设备能够与节点$ u $进行数据传输, 则两个节点间的链路可以表示为链路$ \overrightarrow {uv} $.同时本文仅考虑网络节点为单天线设备的情况, 节点不能同时进行收发动作, 对于同一时隙待调度的链路$ \overrightarrow {uv} $和$ \overrightarrow {xy} $, 如果存在$ (u = x)\vee (u = y)\vee (v = x)\vee (v = y) $为真的情况, 则两条链路发生传输冲突, 不能在同一时隙调度.
1.2 数据流模型与假设
图 1为工业无线网络中一条数据流示意图, 源节点$ S $周期性产生数据, 经过图中粗虚线连接的路由和网关的转发, 进入目的节点$ D, $形成一条具有周期性的端到端数据流.端到端数据流的目的节点也可以只到网关, 且网络中存在着多条端到端数据流.
假设网络$ G = (V, E) $中存在$ N $条端到端数据流, 表示为$ F = \{F_1, F_2, F_3 , \cdots , F_N \} $, 且存在$ K $类不同的优先级$ P = \{P_1 , P_2 , \cdots , P_k \} $, 每类优先级可以包含不止一条的端到端数据流.数据流$ F_i \in F $周期性地产生数据, 周期为$ T_i $, 但一条数据流有且只能有一个优先级别.假设数据流$ F_i $所属优先级大小为$ P_n \in P $, 且满足优先级分类条件$ 1\le P_n \le K $, $ P_n $越小表示优先级越大, 里面包含的数据流相对越重要.但是优先级$ P_n $可能同时包含其他的数据流$ F_j \in F $, 即$ F_j $的优先级类别也为$ P_n $, 所以多个不同的数据流可能具有同一个优先级.在本文中令$ hp(F_i ) $表示优先级类别高于$ F_i $的所有数据流集合.
基于优先级的调度过程中, 不同优先级的数据流发生调度冲突时, 将优先为优先级较高的数据流分配通信资源, 优先级较低的数据流将受到延时影响.在基于时隙的确定性调度中, 令$ C_i $表示数据流$ F_i $完成一次端到端传输的相对截止时隙大小, $ H_i $表示数据流$ F_i $端到端路径上的路由跳数, 即其端到端传输路径中所含的链路个数, 是$ F_i $完成数据从源节点到目的节点的传输所需最小时隙个数, $ L_i $为数据流$ F_i $的实际完成端到端传输的时隙个数.如图 2所示, 数据流$ F_i $的源节点若在时隙$ m $产生数据, 并在时隙$ n $到达目的节点, 则数据流$ F_i $的端到端传输延时为:
$$ \begin{align} L_i = n-m+1 \end{align} $$ (1) 令$ D_i $表示数据流$ F_i $受到的所有高优先级数据流造成的以时隙个数表示的总延时, 即$ hp(F_i ) $条高优先级数据流造成的延时, 数据流$ F_i $在调度时必须满足在截止时隙$ C_i $内完成传输, 所以需要满足条件
$$ \begin{align} L_i = D_i +H_i \le C_i \end{align} $$ (2) 为便于研究, 本文对端到端数据流模型做出以下假设: 1)运行确定性调度方法的网络管理者已知整个网络的拓扑信息; 2)网络管理者根据相应路由算法已完成对网络路由的计算, 数据流从源节点到目的节点的传输路径固定且已知; 3)已知网络中当前可使用的信道个数; 4)端到端数据流周期性地产生数据, 且传输的数据具有截止时间的要求.
根据上述假设, 本文所考虑的工业无线网络采用基于网络管理者的集中式管理策略.在ISA100.11a、WirelessHART和WIA-PA这三个工业无线网络标准中, 都定义了网络管理者或系统管理者的角色, 网络由该管理者进行监测和管理.需要指出的是, 在集中式管理机制下, 信息采集和相应控制都会产生额外数据流和能耗.因此, 在对确定性调度算法进行实际部署时, 网络设计者需对这些额外开销进行必要的考虑.
1.3 确定性调度的数学描述
为将网络中的确定性调度问题转换为公式化的数学描述, 令$ I(v_i ) $表示网络中所有数据流进入节点$ v_i $的链路集合, $ O(v_i ) $表示网络中所有数据流离开节点$ v_i $的链路集合.设处于时隙$ t $时, 节点$ v_i $和节点$ v_j $间的有向通信链路$ \overrightarrow {v_i v_j } $表示为$ s_t (v_i , v_j ) $, 如果在时隙$ t $, 节点$ v_i $向节点$ v_j $发送一次数据, 则$ s_t (v_i , v_j ) = 1 $, 若没有进行发送数据, 则$ s_t (v_i , v_j ) = 0 $.令节点$ v_i $在时隙$ t $结束时所缓存的数据包数表示为$ p_t (v_i ) $, 并且初始化$ p_0 (v_i ) = 1 $, $ rH_t $表示数据流$ F_i $在时隙$ t $下剩余未传输的链路个数.因此, 可以将满足网络中数据流端到端时延要求的确定性调度表示如下所示.
目标:
$$ \begin{align} L_i \le C_i , \mbox{ }\forall i\in [1, N] \end{align} $$ (3) 约束条件:
$$ \begin{align} s_t (v_i , v_j )\in &\{0, 1\}, \mbox{ }s_t (v_j , v_i )\in \{0, 1\}, \\ &\forall v_i \in V, \forall v_j \in V \\ \end{align} $$ (4) $$ \begin{align} \sum\limits_{(v_i , v_j )\in I(v_i )} {s_t (v_i , v_j )} &+\sum\limits_{(v_i , v_j )\in O(v_i )} {s_t (v_j , v_i )} \le 1, \\&\forall v_i \in V, \forall v_j \in V \end{align} $$ (5) $$ \begin{align} p_t (v_i ) = &p_{t-1} (v_i )+\sum\limits_{(v_i , v_j )\in I(v_i )} {s_t (v_j , v_i )} - \\ &\sum\limits_{(v_i , v_j )\in O(v_i )} {s_t (v_i , v_j )} , \mbox{ }\forall v_i \in V, \forall v_j \in V \end{align} $$ (6) $$ \begin{align} rH_t \le C_i - t \end{align} $$ (7) 式(3)表示了确定性调度的最终目标, 即网络中端到端数据流均能在其截止时间内完成数据的传输; 式(4)表示了数据流的通信链路在当前时隙的工作状态, 数据流某一通信链路在当前时隙包含未激活无任何操作、$ v_i $向$ v_j $发送数据和$ v_i $接收$ v_j $数据三种状态; 式(5)是对节点作为半双工设备不能在同一个时隙同时进行收发数据的限制, 从而避免网络调度中的链路冲突; 式(6)表示的是数据包缓存的更新情况; 式(7)限制网络中数据流传输路径上的剩余传输跳数必须小于等于其截止时时隙$ C_i $减去当前时隙$ t $的差值, 否则周期性数据无法在截止时隙$ C_i $的限制内到达.端到端的数据流模型中各参数符号代表意义总结如表 1所示.
表 1 模型中参数符号代表的意义Table 1 Notations used in the considered model符号 意义 Fi 第i条数据流 Ti 第i条数据流的周期 hp(Fi) 优先级高于Fi的所有数据流集合 Di 数据流Fi受到hp(Fi)影响造成的总延时 Ci 数据流Fi完成传输的截止时隙 Hi 数据流Fi端到端传输路径上的路由跳数 Li 数据流Fi的端到端传输延时 rHt 某条数据流在时隙t下剩余未传输的链路个数 2. 数据流调度预处理
对网络进行确定性调度的时候, 所需调度的网络可能会存在一些参数不合理的数据流, 通过对网络中的数据流进行时延分析, 进一步结合数据流各自的截止时间要求, 对所需调度网络进行调度预处理, 能够排除一些参数不合理的网络, 进而达到降低整个调度过程算法复杂度的效果.本文采用一种适用于工业无线网络的时延分析方法来分析不同优先级下端到端数据流的延时[18].
2.1 数据流时延分析
受网络中半双工天线限制和通信资源有限的影响, 数据流的每一跳链路在传输时会受到两种时延:链路冲突时延和信道竞争时延.链路冲突指的是不同数据流的链路因为节点半双工通信不能同时收发的特性, 在同一时隙调度时包含了相同的节点.信道冲突指的是网络信道资源有限, 当前时隙所有的信道均已被优先排列的数据流链路占用, 因此待传输的低优先级链路需要等待至下一个时隙时, 重新为其分配信道资源.
2.1.1 链路冲突时延
链路冲突时延在工业无线网络端到端数据流的时延中占据着主要部分, 主要受到数据流之间路径走向和重叠程度的影响[18].在同一时隙, 当链路冲突发生在不同优先级数据流的链路之间时, 多条链路传输包含了相同的节点, 此时无论网络资源中包含多少可利用信道, 较低优先级数据流的链路均会受到延时影响.如图 3所示, 数据流$ F_1 $的优先级比数据流$ F_2 $的优先级高, 数据流$ F_1 $的传输链路中和数据流$ F_2 $的传输路径包含相同节点的链路一共有6条, 在最坏情况下, 数据流$ F_1 $最多会对数据流$ F_2 $造成6个时隙的延时.
图 3 不同优先级数据流发生链路冲突情况一Fig. 3 The first case of link conflict caused by data flows with different priorities图 3只是不同优先级数据流间发生链路冲突时的一种情况, 当不同优先级数据流间存在连续相同的重复链路时, 采用以上的计算方法会过多地估计低优先级数据流的时延.在图 4中, $ F_1 $和$ F_2 $两条数据流在节点$ v_i $和$ v_j $之间的路径完全重合, 该完全重合路径包含6条链路, 令不同优先级数据流间出现的完全重合路径且重合的链路数大于3的重合路径表示为最大重叠路径(Maximal overlap path, MOP).按照图 3的计算方法, $ F_1 $最多能够对$ F_2 $造成8个时隙的延时, 但是实际上高优先级数据流$ F_1 $最多只能对$ F_2 $造成5个时隙的延时, 因为在MOP路径上最多会对低优先级数据流造成3个时隙的延时.可以观察到当链路1在某一时隙需要调度时, 较高优先级数据流$ F_1 $的链路2同时也需要调度, 于是链路1不得不等待链路2、链路3、链路4均完成传输, 该种情况是在MOP路径上能发生延时的最坏情况.所以在MOP路径上, 较高优先级数据流最多只能对较低优先级数据流造成3个时隙的延时.
图 4 不同优先级数据流发生链路冲突情况二Fig. 4 The second case of link conflict caused by data flows with different priorities令数据流$ F_j \in hp(F_i ) $对较低优先级数据流$ F_i $的链路冲突时延表示为$ l(i, j) $, 则有
$$ \begin{align} l(i, j) = O(i, j)-\sum\limits_{k = 1}^\sigma {(M_k (i, j)-3)} \end{align} $$ (8) 其中, $ O(i, j) $表示数据流$ F_j $中与数据流$ F_i $包含相同节点的链路数, $ \sigma $表示数据流$ F_j $和$ F_i $间包含的MOP路径的条数, $ M_k (i, j) $表示每条MOP路径中完全重合的链路数.在$ t $个时隙内, 令数据流$ F_i $受到所有高优先级数据流因链路冲突造成的总时延表示为$ link\_conf(i, t) $, $ T_i $为$ F_i $的周期, 则有
$$ \begin{align} link\_conf(i, t) = \sum\limits_{F_j \in hp(F_i )} {\left\lceil {\frac{t}{T_i }} \right\rceil \times } l(i, j) \end{align} $$ (9) 2.1.2 信道竞争时延
在本文中, 不考虑信道的空间复用, 在同一时隙, 只有一条链路唯一地占有某个信道.数据流的任意一条链路只允许在某一时隙专享某一信道完成一次通信传输动作, 该过程可类比为多处理器中一个任务在一个时间单位上只允许在一个处理器上运行.数据流的周期性数据通过多条链路完成通信传输, 和一个任务在多个处理器间切换完成执行类似.所以, 网络通信资源中的信道可以类比为多处理器系统中的处理器, $ m $个信道相当于$ m $个处理器:网络中的数据流可以类比为多处理器系统中需要执行的一个任务, 数据流定义的周期、截止时间、优先级、传输时间和多处理器中的周期、截止时间、优先级、执行时间具有同等意义.进而数据流信道竞争时延可以类比为多处理器调度时延, 可以利用已有的多处理器调度成果来分析信道竞争时延[18].
当调度数据流$ F_k $时, 如果当前时隙所有信道均被$ F_i \in hp(F_k) $占据, 令数据流$ F_k $完成端到端传输前所有信道均被占据的持续时间称为$ k- $忙碌期.对于数据流$ F_i \in hp(F_k ) $, 如果存在数据包的生成时间早于$ k- $忙碌期, 而且截止时间在$ k- $忙碌期内, 则数据流$ F_i $在$ k- $忙碌期具有插入负载.在$ t $时间内, 数据流$ F_i $若不存在插入负载, 数据流$ F_i $对数据流$ F_k $造成的信道冲突时延$ I_k^{NC} (F_i , t) $为
$$ \begin{align} I_k^{NC} (F_i , t)\! = \! &\min (\left\lfloor {\frac{t}{T_i }} \right\rfloor \!\times\! H_i \!+\!\min (t\mbox{ }\bmod \mbox{ }T_i , H_i ), \\ &t-H_k +1) \end{align} $$ (10) 其中, $ H_i $为数据流$ F_i $的传输跳数, 也是理想情况下完成传输所需的最小时间.在一段时隙$ t $内, 若数据流$ F_i $存在插入负载, 则数据流$ F_i $对数据流$ F_k $造成的信道冲突时延$ I_k^{CI} (F_i , t) $为
$$ \begin{align} I_k^{CI} (F_i , t)\! = \! &\min (\left\lfloor {\frac{\max (t-H_i , 0)}{T_i }\!\times\! H_i \!+\! H_i \!+\! u_i } \right\rfloor , \\ &t-H_k +1) \end{align} $$ (11) 其中, $ u_i = \min (\max (\max (t-H_i , 0)-(T_i -R_i ), 0), H_i -1) $, $ R_i $表示数据流$ F_i $的最大端到端时延.由于网络有$ m $个信道, 所以网络中最多存在$ m-1 $条更高优先级数据流具有插入负载.因此, 数据流$ F_k $受到的信道冲突总时延为
$$ \begin{align} \Omega _k (t) = X_k (t)+\sum\limits_{F_i \in hp(F_k )} {I_k^{NC} } (F_i , t) \end{align} $$ (12) 式中, $ X_k (t) $表示对网络中所有的$ F_i \in hp(F_k ) $取$ \min ({\left| hp(F_k )\right|, m-1}) $个$ I_k^{CI} (F_i , t)-I_k^{NC} (F_i , t) $的最大值之和.当网络包含$ m $个信道时, 由于信道冲突造成的时延为
$$ \begin{align} t = \left\lfloor {\frac{\Omega _k (t)}{m}} \right\rfloor +H_k \end{align} $$ (13) $ t $可以通过初始化$ t = H_k $, 然后通过定点迭代算法, 使等式两边相等的$ t $值即为信道冲突时延的值.最后结合信道冲突时延和链路冲突时延, 再次通过定点迭代算法, 可以求出数据流$ F_i $在最坏情况下受到$ hp(H_i) $数据流造成的的总的延时.
2.2 调度预处理
调度预处理在数据流时延分析的基础上, 结合数据流自身的截止时间限制, 对所需调度网络进行判定, 过滤掉一些调度成功率已经非常低的网络, 进而达到排除参数不合理的网络的效果, 或者向网络管理者提供参数不合理信息.根据之前的定义, 网络中存在$ K $类不同优先级, 数据流所属优先级值$ P_n $越小, 数据流优先级越大.因此从最低优先级第$ P_n = K $类优先级开始, 遍历当前优先级的所有数据流, 利用数据流时延分析方法计算所有较高优先级数据流对当前优先级数据流$ F_i $造成的总时延$ D_i $, 再结合数据流本身完成传输所需的最小传输时隙, 可以得到当前类中数据流$ F_i $受到较高优先级数据流时延影响后的端到端传输时$ L_i = D_i +H_i $.通过计算每类优先级的每条数据流的$ L_i $值, 得到每条数据流受较高优先级数据流影响后的最大端到端传输时延, 和自身截止时间$ C_i $对比, 如果$ L_i $大于$ C_i $, 该条数据流在最坏情况下不可调度, 不再对该网络进行通信资源的调度.通过遍历网络中所有的数据流, 如果所有数据流的最大端到端传输时延均满足小于等于各自的截止时间, 则视当前网络在最坏情况下可调度.
上述数据流时延分析方法, 计算得到的是数据流的最坏端到端时延, 但是文献[18]已经证明虽然计算得到的是最坏时延, 但是该时延和优先级下真实调度产生的时延是非常接近的, 虽然利用该种数据流时延分析方法进行的调度预处理可能会漏掉一些网络, 但是这个几率是比较低的, 为了过滤掉某些调度成功率已经非常低的网络, 降低整个网络调度的复杂度, 采用上述数据流时延分析方法对待调度的网络进行调度预处理是可行的, 预处理的流程图如图 5所示.
3. 确定性调度算法设计
3.1 基于优先级分类的EPD-C调度方法
整个网络采用基于优先级调度的方法, 网络中的数据流自带固定优先级, 对于不同固定优先级下的数据流调度, 根据优先级从大到小的顺序依次在每个时隙对待释放的链路进行调度.但是同一个优先级类别下的不同数据流具有相同的优先级, 对于这些相同优先级的数据流调度时如若发生链路传输冲突, 缺少一个参数指标判断安排调度的先后顺序.因此, 需要设计一种方法为相同优先级下的数据流调度提供另一种优先指标.
基于优先级的调度在实时任务调度领域已经有丰富的研究成果, 实时任务调度和工业无线网络的数据流调度非常相似, 实时调度需要满足任务在限定的时间内做出响应, 而工业无线网络数据流的调度也需要在截止时间内完成数据流的传输, 对于基于动态优先级的比例截止时间单调(Proportional deadline monotonic, PDM)实时调度方法, 文献[20]证明了在任务的截止时间小于等于任务周期的情况下, PDM调度算法是最优的优先级分配算法, 工业无线网络中的数据流的截止时间往往小于等于周期时间, 所以可将PDM调度算法的思想应用于工业无线网络中相同优先级下不同数据流的调度.
工业无线网络中的确定性调度存在链路冲突的情况, 而实时任务调度则没有考虑此因素.链路冲突在数据流延时中扮演着很重要的角色, 对网络的确定性调度影响很大, 而且网络中的不同节点, 根据经过数据流的多少, 会经历不同程度的链路冲突, 比如网络中的网关和网关的邻居节点遭受的冲突就比一般的节点多, 因为网络中所有的数据最终都要汇聚到网关, 不同数据流在网关附近遭受的潜在冲突越多, 数据流被延迟的时间越大.因此在PDM调度方法的基础上, 考虑到工业无线网络数据流在传输过程中会遭受潜在链路冲突的影响, 本文提出一种基于最小比例冲突空余时间优先(Earliest proportional deadline and conflict first, EPD-C)的调度方法.
数据流$ F_i $在当前时隙$ t $下的比例冲突空余时间为$ \Delta _t $, $ \Delta _t $定义为
$$ \begin{align} \Delta _t = \frac{C_i -t-c_t }{rH_t } \end{align} $$ (14) 式中, $ C_i $表示数据流的截止时隙, $ C_i $减去当前时隙$ t $表示数据流在截止时间内完成传输的剩余时隙数, $ rH_t $表示数据流$ F_i $在当前时隙$ t $下完成剩余传输所需的最小时隙, $ c_t $表示当前时隙下数据流的潜在冲突时隙数, 计算方法为
$$ \begin{align} c_t = \sum\limits_{q = hop}^{H_i } {nf_{hop} } \end{align} $$ (15) 式中, $ hop $表示数据流当前时隙$ t $所在路由位置, $ nf_{hop} $表示第$ hop $跳的邻居数据流个数.
3.2 可调度性判定
网络中的数据流在调度过程中需要满足以下条件, 1)在当前时隙待安排的链路, 不能和其他在当前时隙已安排的链路发生传输冲突; 2)对数据流链路进行调度的时隙不应该超过该数据流完成传输的截止时隙; 3)数据流的截止时隙减去当前时隙的时隙数, 不应该小于该数据流未完成传输的链路个数.
3.3 算法流程
已知网络数据流集合$ F = \{F_1, F_2, F_3, \cdots, F_N\} $, 可用信道数$ M $, 网络中总共有$ K $类优先级, 且每条数据流有固定的优先级, 在同类优先级内, 待调度的链路根据$ \Delta _t $值从小到大的顺序依次安排信道和时隙资源, 且必须满足可调度性判断中的3个条件.对于信道的选取, 采用以下规则: 1)如果当前时隙下前$ x $个信道均被占用, 则链路安排在第$ x+1 $信道; 2)如果当前时隙下没有可用信道, 则在下一个时隙重新计算$ \Delta _t $值, 重新调度; 3)如果当前调度链路和当前时隙中的已安排的链路发生冲突, 则只能在下个时隙重新根据$ \Delta _t $值大小安排调度. EPD-C调度方法具体过程如算法1所示.
算法1.基于优先级分类的EPD-C确定性调度方法
输入: $ T \gets $调度周期时隙个数; $ M \gets $可用信道数目; $ F \gets $数据流集; $ n \gets $数据流编号. /*其中$ F_i = (T_i, P_i, C_i, L_i) \in F $, 输入参数包含周期、优先级和截止时间*/
输出: $ S[0 \cdots T-1] [0 \cdots M-1 $] /*二维数组$ S $为调度结果, 包含时隙和信道, 数组值为数据流编号*/
$ t \gets 0 $; $ c \gets 0 $; /*初始化时隙$ t $, 信道$ c $ */
if $ F \neq 0 $ then
根据数据流自带固定优先级从小到大排序并归类,
$ K $[]$ \leftarrow $每类数据流的条数;
if网络通过调度预处理then
while $ t < T $ do
for $ i\leftarrow $0; $ i < K; $ $ i $++ do
/*不同优先级下的调度*/
for $ j\leftarrow $0; $ j \leq K $[$ i $]; $ j $++ do
/*相同优先级下的EPD-C调度*/
if当前优先级下数据流需调度链路可调度 then
计算当前所有需调度链路$ \Delta _t $值, 并从小到大排序;
while $ c < M $ do
$ S $[$ t $][$ c $]$ \leftarrow $$ \Delta _t $值最小的数据流$ F_n $编号;
/*优先调度$ \Delta _t $最小的数据流*/
$ c\leftarrow c+1; $
/*在剩余可用信道继续调度$ \Delta _t $次小的数据流*/
end while
else
return当前链路不可调度;
end if
end for
$ t\leftarrow t $+1; /*当前时隙$ t $加1*/
end for
end while
else
return网络不可调度;
end if
else
return error;
end if
基于优先级分类的EPD-C调度方法分为两个阶段:调度预处理阶段和通信资源分配阶段.令集合$ K[n_1 , n_2 , \cdots , n_K ] $分别代表每类优先级下数据流的个数, 调度预处理的阶段时间复杂度为$ {\rm O}((K-1)n_1 +(K-2)n_2 +\cdots +n_{K-1} ) $.通信资源分配阶段根据$ \Delta _t $值大小为数据流链路分配时隙和信道, 时间复杂度为$ {\rm O}(N\times M\times T) $, 其中$ N $为数据流总数, $ M $为信道总数, $ T $为调度周期.
4. 实验与分析
4.1 仿真与验证
本节对所提出的EPD-C调度算法进行仿真, 并与经典的调度算法进行对比分析.仿真包括调度结果正确性和调度成功率, 采用MATLAB进行算法编程设计, 网络可用信道数为8, 仿真节点的坐标在$ 100 \times 100 $的区域内均匀随机生成, 网关节点坐标为(50, 50), 所有节点具有相同的通信半径, 使用Dijkstra算法计算源节点到目的节点的路径.在仿真时, 每一个节点都会被选作一条数据流的源节点或者目的节点, 因此可以保证所有的节点都至少会被使用一次.尽管在不同测试网络下可能存在一些主要链路被不同数据流重复使用, 但由于数据流的源目节点对是随机组合的, 而且节点只能和处于通信半径内的节点相互传输数据, 加之采用固定区域内均匀随机生成测试网络拓扑的方法, 节点的度比较相近, 数据流的链路选择总的呈现分散态势, 因此均匀随机生成测试网络的方式能够较好地验证EPD-C算法的性能.其他一些网络拓扑结构生成方法, 如幂律网络等, 同样可以用来验证EPD-C算法的性能, 但在实际应用中, 为了保证工业无线网络的可靠性以及减少单个节点的能量消耗, 通常会对节点的邻居个数进行控制, 避免大量节点连接到同一个路由节点下, 从而使大部分节点的邻居个数相近, 因此均匀随机网络拓扑生成方法与真实的工业无线网络拓扑较为符合.仿真平台运行于64位Windows7操作系统, 计算机配置为酷睿i5处理器、3.6 GHz主频、4 GB内存, 仿真平台通过随机地生成网络和数据流, 为调度方法提供测试网络.同时本文提出的EPD-C调度方法将与经典的优先级调度算法:基于静态优先级的速率单调(Rate monotonic, RM)调度方法[21]和基于动态优先级的LLF (Least laxity first, 最小空余时间优先)调度方法[22], 进行对比分析.
针对调度结果正确性的测试, 利用仿真平台分别产生20个节点, 10条数据流和30个节点, 15条数据流的随机网络进行多次测试, 节点被设置成只能唯一地作为某条数据流的源节点或者目的节点, 因此节点数和数据流条数保持2 : 1的关系可以保证网络的每一个节点都至少一次被用作数据流的源节点或者目的节点, 防止测试网络中的一些节点始终被闲置, 然后对每个随机网络首先进行调度预处理, 如果调度预处理通过, 再运行EPD-C调度算法为所有数据流进行时隙和信道的分配, 若未通过, 则针对此网络下的调度失败.在对以上两种规模的网络进行仿真时, 分别固定数据流的源目节点对和截止时间不变, 只改变源目节点对之间的路径, 然后生成大量测试网络进行仿真.在两种网络规模下, 三种调度算法的截止时间和实际调度平均传输时延的数据对比如图 6所示.仿真结果表明本文提出的EPD-C调度算法在上述两种网络参数的网络下, 均能保证端到端数据流在截止时间内完成传输, 且在网络规模较小时数据流平均传输时延也较小, 证明了调度方法的正确性.
图 6 三种调度方法关于截止时间和实际调度平均时延数据对比图Fig. 6 Comparisons between the deadlines and the actual scheduled average delays for three scheduling methods为验证提出的调度方法在不同网络规模下的性能表现, 利用仿真平台分别随机生成: 10个节点5条数据流、20个节点10条数据流、30个节点15条数据流、40个节点20条数据流、50个节点25条数据流、60个节点30条数据流和70个节点35条数据流等七种不同规模的网络, 并且针对该七种规模的网络进行调度成功率的测试.调度成功率是针对一定数量的随机测试网络, 调度方法能够成功调度的测试网络所占百分比.在不同网络规模下三种调度方法的调度成功率测试结果如图 7所示.
图 7 不同网络规模下三种调度方法的调度成功率Fig. 7 Success probabilities of scheduling for the three scheduling schemes in different network sizes通过观察图 7可以发现, 在网络规模较小时, EPD-C调度方法的成功率比较高, 几乎接近百分之百, 但是随着网络规模增大, 调度成功率开始呈下降趋势.通过分析可以知道, 随着网络规模和数据流数量增大, 数据流之间路径的交错重叠也增多, 发生冲突的机率也变大, 不同优先级数据流间造成的时延也增多, 因此造成调度成功率的下降.基于RM的调度方法调度成功率最低, 并且随着网络规模增大, 调度成功率迅速下降, 因为该种调度方法仅仅根据数据流周期大小进行静态优先级调度, 没有考虑传输延迟对调度的影响.基于LLF的调度方法通过计算调度剩余时间, 动态地分配优先级, 但是由于LLF调度方法并没有考虑潜在冲突的情况, 调度成功率低于EPD-C调度方法, 但是高于RM调度方法.在网络规模较大时, 由于给定的信道等调度资源有限, 三种调度算法的调度成功率均下降严重, 此时可以通过提供更多的调度资源, 如增加可用信道的个数、增大数据流的截止时间等方式, 以此来维持算法调度成功率在一个较高水平.尽管EPD-C调度算法对于大规模网络的调度成功率较低, 但相比于RM算法和LLF算法的调度成功率仍具有一定优势.该算法为基于优先级分类的工业无线网络数据流调度问题提供了一种解决方法, 具有一定的参考价值.
为了观察调度算法在网络存在丢包时的性能, 对三种算法在不同丢包情况下的调度效果进行仿真对比, 结果如图 8所示.仿真参数设置为20个节点和10条数据流, 按照一定比例从网络的所有链路中随机生成丢包链路, 丢包链路比例从0到20 %依次递增.注意到在丢包场景下, 一条数据流调度失败分为两种情况:一是调度算法无法给出满足所有数据流要求的调度解, 此时所有数据流均属于调度失败; 二是调度算法获得了有效调度解, 但该数据流由于链路发生丢包导致调度失败.在第二种情况中, 会出现一部分数据流调度失败, 而另外一部分数据流调度成功的状态.因此, 为了全面反映调度效果, 在丢包情况下以数据流为统计单位, 将调度算法有解, 且数据流正确传输的情况称为该数据流被调度成功, 通过多次生成测试网络, 以调度成功数据流占总仿真数据流的比例作为调度衡量指标.需要说明的是, 丢包比例为0对应网络不考虑丢包的情况, 采用图 7中的仿真结果并转换为基于数据流的衡量指标, 以此作为对比基准.从图 8可以看出, 在网络存在一定丢包的情况下, EPD-C调度算法仍然能够运行, 且调度性能优于另外两种算法.随着丢包比例不断增加, 三种算法的数据流成功调度比例均逐步减小, 表明网络中丢包现象的加重将引起调度算法性能的下降.
图 8 不同丢包情况下三种调度方法的调度结果Fig. 8 Successful scheduling ratios of data flows for the three scheduling methods in different packet loss cases此外, 本文进一步对EPD-C调度算法的执行时间进行测试, 测试时维持与调度解成功率测试下相同的网络参数和计算机硬件环境, 且仅对可以调度的网络进行了执行时间的测试.同时为了更好地比较三种调度方法的时间性能, 在以上七种网络规模下, 统一使用Matlab计算三种调度算法的平均执行时间.七种网络规模下三种调度算法的平均执行时间变化如表 2所示.
表 2 三种调度方法的平均执行时间(ms)Table 2 Average execution time of three scheduling methods (ms)网络规模 10个节点,
5条数据流20个节点,
10条数据流30个节点,
15条数据流40个节点,
20条数据流50个节点,
25条数据流60个节点,
30条数据流70个节点,
35条数据流EPD-C 21.4 89.9 195.6 311.6 491.4 737.9 973.9 LLF 24.7 100.5 215.6 391.6 625.5 943.9 1 215.5 RM 26.5 113.3 269.4 483.6 859.3 1 340 2 084 实验结果表明, 在网络规模较小时, 三种调度算法的平均执行时间均较快, 但是随着网络规模的增大, 三种调度算法的平均执行时间增长较为迅速.这是因为随着网络规模的增大, 网络的数据流个数会变多, 调度算法在计算数据流的优先级, 以及判断链路冲突、安排调度的过程中均会消耗更多的时间.虽然三种调度算法的平均执行时间均随着网络规模增大而变长, 但在70个节点下, EPD-C算法的平均执行时间保持在1秒以内, 仍处于可接受的范围.在每种网络规模下, EPD-C算法的执行时间均要优于RM算法和LLF算法.而且EPD-C算法可以排除参数不合理的网络, 并且进行了保证数据基于优先级分类的确定性调度.综上所述, 相比于RM算法和LLF算法, EPD-C算法在执行时间和调度成功率上均具有一定的优势, 能够较好地满足工业无线网络数据流的确定性传输需求.
4.2 讨论与分析
EPD-C调度算法能够为同类优先级下的多条数据流提供一种新的优先级指标, 以此为所有数据流按照优先级顺序分配时隙和信道资源, 保证满足数据流的截止时间约束, 从而能够满足工业无线网络数据流的实时性和确定性传输需求.本文从调度成功率和平均执行时间两项指标上对EPD-C调度算法进行了对比验证, 但是考虑到工业环境的恶劣性, 下面对影响调度算法性能的一些因素进行讨论和分析.
1) 干扰:工业无线标准采用跳信道技术来提升网络的抗干扰能力, 跳信道技术的主要思想是在时隙上进行信道的不断切换, 以此降低同频信道的干扰概率. EPD-C算法虽然没有直接考虑抗干扰的问题, 但是在整个调度过程中, 同类优先级的不同数据流的调度顺序是动态改变的, 分配的信道也是动态的, 因此网络节点的不同通信链路所采用的信道不是固定不变的, 从而EPD-C算法具有一定的抗干扰能力.但是后续可以从抗干扰问题出发对EPD-C算法进行优化, 从而进一步提升网络抗干扰能力.
2) 能耗:本文提出的EPD-C算法是一种基于TDMA机制的确定性调度算法, 能够避免因信道竞争导致的链路传输失败, 从而节省设备的能量开销.调度完成后, 网络节点按照调度结果有序进行数据传输动作, 在没有数据传输时, 节点可以切换到休眠状态, 从而减少额外的能量开销.因此EPD-C算法在一定程度上可以降低网络的能耗.
3) 丢包与重传:本文所提方法未显式考虑数据丢包和重传问题, 但无线网络因其特性本质上难以保证不丢包, 尤其是在通信环境较为恶劣的工厂网络中. 图 8中的仿真结果表明, 当网络发生丢包时, 所提出的确定性调度算法仍然能够运行, 但调度成功率会因数据包丢失而降低.由于工业网络对于可靠性有着更为严格的要求, 在ISA100.11a、WirelessHART、WIA-PA等标准中采用了多种方式来克服丢包的影响.例如, 利用ISA100.11a和WirelessHART标准所提供的图路由机制, 或WIA-PA标准所提供的路由配置策略, 在源节点和目的节点之间可以设置多条冗余路径同时进行数据的传输.当一条路径由于发生丢包问题而传输失败时, 源节点发出的数据包仍然可以沿着其他路径到达目的节点, 从而提高了传输可靠性.对于上述多路径传输机制, 在进行调度时可以将源节点与目的节点之间各条路径上的数据流视为拥有相同截止时间的独立数据流, 然后代入所提出的调度算法便可进行时隙、信道资源的计算与分配.因此, 配合多路径传输等路由机制, 所提调度算法能够在一定程度上缓解丢包问题对网络的影响.此外, 重传也是克服丢包问题的重要方式.在调度问题中, 重传可视为单条路径上的每跳传输以规定的重传次数为倍数在不同的时隙进行重复, 仍然可以基于所提出的优先级分类调度算法, 在进行资源分配时引入上述因素以适应重传场景.考虑到处理丢包和重传问题的效果与具体的网络协议密切相关, 后续工作可在调度算法中针对丢包和重传问题进行专门优化, 以进一步提高调度算法的适用性.
4) 信道带宽:信道是数据流调度的基本资源之一, 本文所提算法主要针对信道带宽相等的情况进行讨论.在某些工业无线网络中, 不同信道的带宽大小存在差异, 拥有更高带宽的信道往往能够提供更多的调度资源.如何充分利用这些带宽资源来改善调度效果, 是本文算法下一步的改进方向之一.
5) 网络拓扑: EPD-C算法以数据流为处理对象, 在将网络分解为若干条源节点到目标节点的数据流后, 算法的执行本身不依赖于特定的网络拓扑结构.但需要指出的是, 算法的调度结果会受到拓扑结构的影响.例如在某种网络拓扑下, 若出现一些主要的链路被大量重复使用, 而另一些链路被始终闲置的情况, 则会严重降低调度成功率.实际上, 工业无线网络中的拓扑主要由拓扑控制协议和路由协议负责, 若能将EPD-C算法与上述两类协议进行联合设计和优化, 在链路冲突时进行灵活调节, 引入更多的节点和链路资源, 将起到避免拥塞、提高调度成功率的良好效果.
5. 总结
本文研究了工业无线网络下基于优先级分类的数据流确定性调度问题, 在对数据流模型数学化描述的基础上, 分析了造成低优先级数据流传输延迟的两个因素:链路冲突和信道竞争.根据数据流时延分析结果对网络的数据流进行调度预处理, 从而达到排除一些参数不合理的网络的效果, 并可以反馈给网络管理者.针对同一优先级下可能包含多条数据流, 提出一种基于最小比例冲突时间的动态EPD-C调度算法, 仿真结果表明相比经典的RM算法和LLF算法, EPD-C算法可以取得更高的调度解成功率, 而且具有较低的算法时间执行.不足之处是当网络规模较大时, 计算效率和调度成功率下降明显, 未来将对EPD-C算法在大规模网络下的性能进行进一步的优化研究.此外, 本文仿真采用了随机生成网络的方式, 将来可进一步结合有代表性的过程控制应用场景进行仿真分析, 并可搭建实物网络, 在真实的工业环境下进行测试验证, 以进一步提高调度算法的实用性.
-
图 3 不同优先级数据流发生链路冲突情况一
Fig. 3 The first case of link conflict caused by data flows with different priorities
图 4 不同优先级数据流发生链路冲突情况二
Fig. 4 The second case of link conflict caused by data flows with different priorities
图 6 三种调度方法关于截止时间和实际调度平均时延数据对比图
Fig. 6 Comparisons between the deadlines and the actual scheduled average delays for three scheduling methods
图 7 不同网络规模下三种调度方法的调度成功率
Fig. 7 Success probabilities of scheduling for the three scheduling schemes in different network sizes
图 8 不同丢包情况下三种调度方法的调度结果
Fig. 8 Successful scheduling ratios of data flows for the three scheduling methods in different packet loss cases
表 1 模型中参数符号代表的意义
Table 1 Notations used in the considered model
符号 意义 Fi 第i条数据流 Ti 第i条数据流的周期 hp(Fi) 优先级高于Fi的所有数据流集合 Di 数据流Fi受到hp(Fi)影响造成的总延时 Ci 数据流Fi完成传输的截止时隙 Hi 数据流Fi端到端传输路径上的路由跳数 Li 数据流Fi的端到端传输延时 rHt 某条数据流在时隙t下剩余未传输的链路个数 
下载: 导出CSV
表 2 三种调度方法的平均执行时间(ms)
Table 2 Average execution time of three scheduling methods (ms)
网络规模 10个节点,
5条数据流20个节点,
10条数据流30个节点,
15条数据流40个节点,
20条数据流50个节点,
25条数据流60个节点,
30条数据流70个节点,
35条数据流EPD-C 21.4 89.9 195.6 311.6 491.4 737.9 973.9 LLF 24.7 100.5 215.6 391.6 625.5 943.9 1 215.5 RM 26.5 113.3 269.4 483.6 859.3 1 340 2 084
下载: 导出CSV
-
[1] Sha M, Gunailaka D, Wu C J, Lu C Y. Empirical study and enhancements of industrial wireless sensor-actuator network protocols. IEEE Internet of Things Journal, 2017, 4(3): 696-704 doi: 10.1109/JIOT.2017.2653362 [2] Begum K, Dixit S. Industrial WSN using IoT: a survey. In: Proceedings of the 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT). Palnchur, Chen Nai, India: IEEE, 2016. 499-504 [3] Wang Q, Jiang J. Comparative examination on architecture and protocol of industrial wireless sensor network standards. IEEE Communications Surveys & Tutorials, 2016, 18(3): 2197-2219 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7b14c25bc9010a525f25c11d6c1db59d [4] Toscano E, Lo Bello L. Multichannel superframe scheduling for IEEE 802.15.4 industrial wireless sensor networks. IEEE Transactions on Industrial Informatics, 2012, 8(2): 337-350 doi: 10.1109/TII.2011.2166773 [5] Saifullah A, Xu Y, Lu C Y, Chen Y X. Real-time scheduling for wirelessHART networks. In: Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS). San Diego, CA, USA: IEEE, 2010. 150-159 [6] Kim Y G, Lee M J. Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization. IEEE Communications Magazine, 2014, 52(1): 122-129 doi: 10.1109/MCOM.2014.6710073 [7] Kang H, Zhao Y N, Mei F. A graph coloring based TDMA scheduling algorithm for wireless sensor networks. Wireless Personal Communications, 2013, 72(2): 1005-1022 doi: 10.1007/s11277-013-1052-9 [8] Kang B, Nguyen P K H, Zalyubovskiy V, Choo H. A distributed delay-efficient data aggregation scheduling for duty-cycled WSNs. IEEE Sensors Journal, 2017, 17(11): 3422-3437 doi: 10.1109/JSEN.2017.2692246 [9] 贾杰, 代恩亮, 陈剑, 王兴伟, 赵林亮.无线传感器网络中联合路由优化的高能效链路调度.电子学报, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013Jia Jie, Dai En-Liang, Chen Jian, Wang Xing-Wei, Zhao Lin-Liang. Energy-efficient link scheduling combined with routing optimization in wireless sensor network. Acta Electronica Sinica, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013 [10] 牛建军, 邓志东.基于马尔可夫链的无线传感器网络分布式调度方法.自动化学报, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685Niu Jian-Jun, Deng Zhi-Dong. Markov chain-based distributed scheduling approach for wireless sensor network. Acta Automatica Sinica, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685 [11] Sgora A, Vergados D J, Vergados D D. A survey of TDMA scheduling schemes in wireless multihop networks. ACM Computing Surveys, 2015, 47(3): 1-39 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=84249ad24dcfe9401e41c7781eade0a7 [12] 张晓玲, 梁炜, 于海斌, 封锡盛.无线传感器网络传输调度方法综述.通信学报, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019Zhang Xiao-Ling, Liang Wei, Yu Hai-Bin, Feng Xi-Sheng. Survey of transmission scheduling methods in wireless sensor networks. Journal on Communications, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019 [13] Rao S, Keshri S, Gangwar D, Sundar P, Geetha V. A survey and comparison of GTS allocation and scheduling algorithms in IEEE 802.15.4 wireless sensor networks. In: Proceedings of the 2013 IEEE Conference on Information and Communication Technologies (ICT). Thuckalay, Tamil Nadu, India: IEEE, 2013. 98-103 [14] 李金宝, 王蒙, 郭龙江. MR-MC无线传感器网络最小延迟数据聚集调度研究.通信学报, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022Li Jin-Bao, Wang Meng, Guo Long-Jiang. Minimum latency data aggregation scheduling in MR-MC wireless sensor networks. Journal on Communications, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022 [15] 牛建军, 邓志东, 李超.无线传感器网络分布式调度方法研究.自动化学报, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517Niu Jian-Jun, Deng Zhi-Dong, Li Chao. Distributed scheduling approaches in wireless sensor network. Acta Automatica Sinica, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517 [16] 王恒, 陈鹏飞, 王平.面向WIA-PA工业无线传感器网络的确定性调度算法.电子学报, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010Wang Heng, Chen Peng-Fei, Wang Ping. Deterministic scheduling algorithms for WIA-PA industrial wireless sensor networks. Acta Electronica Sinica, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010 [17] 王恒, 李敏, 刘其琛, 王平.一种基于确定性调度的工业无线网络路由算法.仪器仪表学报, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001Wang Heng, Li Min, Liu Qi-Chen, Wang Ping. Routing algorithm for industrial wireless network based on deterministic scheduling. Chinese Journal of Scientific Instrument, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001 [18] Saifullah A, Xu Y, Lu C Y, Chen Y X. End-to-end communication delay analysis in industrial wireless networks. IEEE Transactions on Computers, 2015, 64(5): 1361-1374 doi: 10.1109/TC.2014.2322609 [19] Industrial networks - Wireless communication network and communication profiles - WIA-PA, IEC 62601, 2015 [20] Leung J Y, Whitehead J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 1982, 2(4): 237-250 doi: 10.1016/0166-5316(82)90024-4 [21] 王永吉, 陈秋萍.单调速率及其扩展算法的可调度性判定.软件学报, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002Wang Yong-Ji, Chen Qiu-Ping. On schedulability test of rate monotonic and its extendible algorithms. Journal of Software, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002 [22] Ayele A A, Rao V S, Dileep K G, Bokka R K. Combining EDF and LST to enhance the performance of real-time task scheduling. In: Proceedings of the 2016 International Conference on ICT in Business, Industry, and Government (ICTBIG). Indore, India: IEEE, 2016. 期刊类型引用(10)
1. 裘莹，张敬宣，柯杰，方梦园，徐伟强. 工业无线网络实时传输调度算法研究综述. 自动化学报. 2024(11): 2102-2127 . 
本站查看2. 王忠锋，张楠，夏长清，尚志军，田宇，金曦，许驰. 面向工业无线系统的实时聚合调度方法. 小型微型计算机系统. 2023(01): 204-210 . 百度学术3. 王恒，余蕾，谢鑫. 基于信息年龄的工业无线传感器网络混合数据调度方法. 电子与信息学报. 2023(03): 1065-1073 . 百度学术4. 郑静雅，安军社. SpaceFibre星载数据网络低延时确定性调度算法. 国防科技大学学报. 2023(02): 179-187 . 百度学术5. 程楠，朱国超. 考虑阴影衰落的无线网络拓扑离散优化算法. 计算机仿真. 2023(06): 435-438+503 . 百度学术6. 徐会彬. 一种基于链路信任的无线网络安全路由. 湖州师范学院学报. 2023(08): 62-68 . 百度学术7. 王恒，彭政岑，马文巧，李敏. 免时间戳交互的无线传感网隐含节点同步参数估计算法. 自动化学报. 2022(11): 2788-2796 . 本站查看8. 李兰英，蒋维成，周玲，黄静. 传感器网中基于角度的移动目标跟测方法. 计算机工程与设计. 2021(12): 3310-3315 . 百度学术9. 王恒，刘清华，李敏，谭帅. 考虑链路重传的工业无线网络确定性调度算法. 自动化学报. 2021(11): 2664-2674 . 本站查看10. 罗伟华. 面向5G的车载无线通信低时延信道节点调度方法. 贵阳学院学报(自然科学版). 2021(04): 12-15 . 百度学术其他类型引用(6)
-
下载:
计量
- 文章访问数: 1905
- HTML全文浏览量: 424
- PDF下载量: 224
- 被引次数: 16
