WSANs中基于可靠性最大化的报文实时投递方案

崔立尉++杨申浩

摘 要 无线传感反应器网络（WSANs）中现有的报文投递方案可靠性不足，不适用于数据率互不相同的网络场景.为此，提出一种基于可靠性最大化的报文实时投递方案.报文投递问题被分解为两个子问题：基于子周期的时隙分配问题和基于时隙的传输调度问题.第1个子问题被转化为一个线性整数规划问题，并给出一种具有多项式时间复杂度的求解方法.对于第2个子问题，文中证明是否存在最优可行调度取决于求解前一子问题时获得的时隙分配向量中的元素次序，然后给出一种可行时隙分配方案求解算法.仿真结果表明，本文算法可保证每个设备即使在不同的报告周期内也可实现基本相同的报文投递率，这一特性对于维持控制系统的稳定性具有重要作用.

关键词 无线传感反应器网络；流量；非线性整数规划；可靠性；时隙；报文投递率；稳定性

中图分类号 TP393 文献标识码 A 文章编号 10002537（2016）010085010

A RealTime Delivery Scheme of Packet Based on Reliability

Maximization in Wireless SensorActuator Networks

CUI Liwei1，2， YANG Shenhao3*

（1. School of Information Management and Computer Technology， Inner Mongolia Agricultural University， Baotou 014109， China；

2. School of Information Engineering， Inner Mongolia University of Science and Technology， Baotou 014010， China；

3. School of Computer Science and Technology， Tsinghua University， Beijing 100083， China）

Abstract The existing packet delivery schemes have a low reliability in wireless sensoractuator networks （WSANs）. Hence， these schemes are not suitable for networks with heterogeneous traffic rates. To solve this problem， a realtime delivery scheme of packet based on reliability maximization is proposed. The packet delivery problem is decomposed into two subproblems： subperiodbased slot allocation and slotbased transmission scheduling. The former subproblem is formulated as a linear integer programming problem， and we present a solution with polynomialtime complexity. For the latter subproblem， we demonstrate that the existence of a feasible optimal schedule depends on the order of the elements in the slot allocation vector produced by solving the former subproblem， and then an algorithm is designed to compute a feasible slot allocation that sustains a realizable schedule. Simulation results demonstrate that our scheme ensures each device has almost the same packet delivery rate in different report periods， which is important for maintaining the stability of control systems.

Key words wireless sensoractuator networks； traffic； nonlinear integer programming； reliability； slot； packet delivery rate； stability

基于无线传感反应器网络[1]（WSANs）的工业自动化技术在降低部署成本和提高系统灵活性方面具有巨大优势，因此在近些年引起了研究和工业领域的大量关注.为了促进WSANs在工业领域的应用，人们已经提出了3套国际标准[23]：WirelessHART，ISA 100.11a和IEEE 802.15.4e.这些标准均采用基于IEEE 802.15.42006标准且支持2.4 GHz ISM频段16个信道的低功率无线电技术.然而，采用这些低功率无线电技术的设备非常不可靠，且链路质量往往具有时变特性，尤其是恶劣环境下更是如此，比如存在大量噪声且对象移动导致频繁信号反射现象的工厂车间等.因此，设计无线工业控制网络的关键难点在于，存在信道损耗条件下实现高可靠性实时数据通信.

在工业控制领域的WSANs中，传感器生成的报文往往带有严格的时间约束，如果没有在截止时间前成功发送报文将会降低控制性能，导致控制系统性能不够稳定.为了满足无线通信严格的可靠性和实时性要求，所有近期工业无线标准均采用时分多址（TDMA）技术并将其与时限约束通信调度策略结合起来.为了提高有损无线信道的传输可靠性，被丢失的报文必须进行重传，基于TDMA的方案往往通过预留额外时隙实现报文重传.一个关键问题是如何进行额外时隙的分配和重传调度，以便使控制器在时限范围内接收到所有报文的概率最大.国外学者已经针对无线传感器网络的最小延时数据采集问题提出了多种基于TDMA的链路调度算法[45]，但是这些算法假设每轮数据采集期间生成的所有报文具有相同的时限要求，而且只能处理同一数据采集周期内生成的所有报文具有相同时限约束的同质流量，所以不适用于数据率互不相同的工业应用网络场景.另外，当前针对蜂窝网络和无线LAN网络的调度算法[69]要么只考虑软约束，要么假设流量比特率恒定，因此不适用于对可靠性和时限要求非常高的无线工业控制网络.文献[10]研究了不同任务具有不同可靠性要求的周期性实时任务调度问题，建立了调度可行性的充分必要条件，并提出称为Greedy Maximizer的贪婪式在线调度策略.然而，只有当所有任务的周期相同时贪婪策略才能实现可行性最优.

为了弥补以上方案的不足，本文假设不同传感器设备具有不同的报文生成率，不同的无线链路具有不同的报文丢失率，研究单跳无线工业控制网络下带有时限约束的报文调度可靠性问题.具体来说，本文贡献如下：（1）提出一种单跳无线网络的时限约束异质流量理论调度模型，并给出一种双阶段调度算法：基于子周期的时隙分配方案和基于时隙的传输方案.（2）将基于子周期的时隙分配问题表述为线性整数规划问题.给出一种多项式时间算法，可求出基于子周期的时隙分配问题的最优解.（3）基于子周期的时隙分配问题的解将会生成一个时隙分配向量，该向量可明确有多少个时隙被分配给哪个设备的哪个汇报周期.因为最优性能增益取决于分配向量中的元素数值，所以我们证明是否存在可行的最优调度方案取决于分配向量中的元素次序.设计了一种可行次序求解算法，可求解出能够表示可行调度的次序.

1 系统模型和问题表述

1.1 系统模型

假设有一个无线工业网络由一个控制器c和N个无线传感器设备d1，d2，…，dN构成.每个设备配备一个半双工射频收发器，表明控制器无法同时从多个传感器设备接收报文.所有传感器设备可与控制器直接通信（即单跳通信）.时间经过同步且划分为多个长度相同的时隙，每个时隙可以传输一个数据报文及对应的确认报文.假设不同无线链路的报文丢失率互相独立，且服从Bernoulli模型[11].对于从di到c的每个报文传输过程，报文丢失概率为pi.在本文模型中当且仅当发射器已经接收到报文的确认时才认为报文传输成功.因此，每条链路的报文丢失概率同时考虑了数据报文及确认报文的丢失情况.

每个传感器设备di以Ti个时隙的固定汇报间隔，定期向控制器汇报数据.每个周期性流量只包括一个在相应汇报周期快要开始时生成的时间报文.di生成的报文的时限要求与其周期Ti相吻合.如果报文没有在其时限要求内成功传输到控制器，则在下个汇报周期开始时将其丢弃.

1.2 问题表述

下面首先定义了子周期和超级周期.di的子周期只表示Ti个时隙构成的固定长度的汇报周期，使用Si，m来表示设备di的第m个子周期.超级周期定义为长度固定为H个时隙的周期，其中H表示所有T的最小公倍数，即H=lcm{T1，…，TN}.因此，对于设备di，一个超级周期包括HTi个子周期，每个子周期需要向控制器传输一个报文.图1给出了子周期和超级周期的示例.可以看到，引入子周期和超级周期后，只需研究一个超级周期内的报文传输调度问题即可，因为其余超级周期重复相同的调度方案.

4 性能评估

本节利用MATLAB仿真对本文算法进行全面的性能评估.从可靠性最大化和每个设备不同子周期的均衡效果方面对本文算法（表示为OPTSLOT）与文献[10]中的Greedy Maximizer算法加以比较.还证明了通过调整每个设备的权重可以保证可靠性.

4.1 与Greedy Maximizer算法的比较

在本文算法中，每个设备在每个超级周期内重复相同的调度方案.因此，每个设备在不同超级周期同一子周期内的可靠性是相同的.然而，Greedy Maximizer算法从长期均值角度使系统可靠性最大化，每个设备在不同超级周期同一子周期内的可靠性可以不同.为了兼顾公平，确定仿真实验内容如下：选择具有不同N和Ti的7种网络配置，如表2所示.对每种网络配置，我们设置不同的报文丢失率进行1 000次仿真实验.每次仿真时，每条链路的报文丢失率从[0.2， 0.8]中均匀选择，且在仿真期间保持不变.每次仿真持续200个超级周期.在该组仿真中，式（1）中所有传感器设备的权重设置为1，Greedy Maximizer算法每个设备的最小可靠性要求设置为0.

表2 网络配置

Tab.2 The network configuration

群组序列号NTi群组序列号NTi

G13[3，4，6]G54[12，5，9，6]

G23[5，7，8]G65[6，9，12，10，8]

G34[3，4，10，7]G75[20，15，5，6，9]

G43[20，10，7]

因为所有传感器设备的权重设置为1，所以式（1）中的R等价于一个超级周期内接收到的报文数量期望值，最小可靠性等于一个超级周期内生成的报文总量.我们将平均可靠性定义为一个超级周期的平均可靠性与最大可靠性之比.图3比较了两种算法在一个超级周期内的平均可靠性及标准差.可以看出，本文算法在最差情况下可以成功投递48%的报文，在最好情况下可成功投递95%的报文.Greedy Maximizer算法在大多数情况下可投递30%左右的报文，且不同网络配置下的性能相差不大.这是因为Greedy Maximizer在提升性能时的思路是满足每个设备的最小可靠性要求，而不是使可靠性最大.在每个时隙期间，可靠性要求较高的任务在调度期间被赋予较高的优先级，而本文方法的目标是使一个超级周期的总可靠性最大.

图4给出了同一设备不同子周期被分配的时隙数量平均差值及标准差.可以看出，本文算法的平均差值小于0.2.这是因为最多只有一个设备其不同子周期可被分配不同数量的时隙，且互相之间最多相差1个时隙（参考引理3），表明每个设备在不同子周期内基本具有相同的可靠性.这种设备内可靠性可提升控制系统的稳定性.Greedy Maximizer算法生成的传输调度方案，其波动性更强.从图4可见，平均差值为2.5，最大差值在8以上.这是因为Greedy Maximizer算法将系统性能定义为长期平均可靠性，在每个时隙期间该算法贪婪地选择可靠性要求最高的任务加以执行，导致不同子周期的可靠性发生波动.这些波动现象可能会影响工业系统的性能.

图3 不同网络配置下可靠性期望值的比较情况

Fig.3 The comparison of expectations of reliability under different network configuration

图4 不同子周期的可靠性差值比较

Fig.4 The comparison of poor reliability value in the different subperiod

4.2 wi对性能的影响

本文算法可保证同一设备不同子周期性能的公平性，但是不保证不同设备间的公平性.在本文算法中，报文丢失率较低的设备被调度的概率较高.在许多工业控制应用中，每个传感器设备对于从自己到达控制器的报文投递率有最低要求.用ri来表示di在一个子周期内应该实现的最低可靠性.假设xi表示为了满足最小可靠性，每个子周期内应该分配给di的时隙最小数量.于是有：

xi=|log（1-ri）log pi|. （20）

对每个设备di，一个超级周期内生成HTi个报文.于是，下式成立：

图5 不同权重配置条件下每个设备每个子周期接收到的报文数量期望值比较

Fig.5 The comparison of packet expectations received period of each device under different weights

x1·HT1+…+xN·HTN≤H. （21）

将式（20）代入式（21），有：

∑Ni=11Ti·|log（1-ri）log pi|≤1. （22）

利用上式可以检查在某种网络配置下满足最低要求的可行性.一旦上述不等式成立，则可以按照如下两种方式进行调度以满足最低要求：（1）分配给报文的时隙由两部分构成，强制型部分（即xi）和可选部分，首先分配强制型部分，以满足最低要求，然后利用本文算法分配可选部分；（2）调整分配给每个设备的权重，以满足最低要求.由于第1种方法比较简单，所以在下文将利用一个示例来阐述第2种方法.

图5给出了每个设备在一个子周期内接收到的报文数量期望值，其中N=3，[T1，T2，T3]=[3，4，5]，[p1，p2，p3]=[0.6，0.8，0.7].当所有3种设备具有相同权重时（wi=[0.33，0.33，0.33]），d1在每个子周期内接收到的报文数量最大.然而，d2没有被分配任何时隙，因为其丢失率太高.如果将权重调整为wi=[025，0.5，0.25]，则d2被分配的时隙增多，因此一个子周期内接收到的报文预期数量增加到5.4个，控制器接收到的报文总量期望值为16.4.即使最大可靠性略有下降，但是所有3种设备均有机会将其报文传输到控制器.通过合理调整权重，可以确定一种调度方案满足每个设备的最小要求.

5 总结

本文研究了WSANs中的报文投递可靠性问题，提出一种双阶段调度算法，首先采取优化策略将时隙分配给每个设备的不同子周期，以便实现可靠性最大化，然后利用基于时隙的调度策略构建传输调度方案.即使目标函数为关于分配给每个子周期的时隙数量的非线性函数且该函数往往是NP难题，提出一种多项式时间复杂度求解算法，可计算出上述问题的最优解.仿真结果证明本文算法的报文投递率远高于当前算法.此外，本文算法还保证同一设备不同子周期的性能的公平性，这一特性对于控制系统的稳定性具有重要作用.证明通过调整分配给每个设备的权重可以控制不同设备的可靠性，进而满足每个设备的最小可靠性要求.下步工作主要是对权重和最小可靠性要求之间的关系进行分析.

参考文献：

[1] MAZO M， TABUADA P. Decentralized eventtriggered control over wireless sensor/actuator networks[J]. IEEE Trans Aut Contr， 2011，56（10）：24562461.

[2] GUGLIELMO D D， SEGHETTI A. A performance analysis of the network formation process in IEEE 802.15. 4e TSCH wireless sensor/actuator networks[C]// 2014 IEEE Symposium on Computers and Communication， Madeira， Portugal： IEEE Press， 2014：16.

[3] CECILIO J， FURTADO P. Architecture for uniform configuration and processing over embedded sensor and actuator networks [J]. IEEE Trans Industr Info， 2014，10（1）：5360.

[4] ERGEN S， VARAIYA P. TDMA scheduling algorithms for wireless sensor networks [J]. Wirel Netw， 2010，16（4）：985997.

[5] SOLDATI P， ZHANG H， ZOU Z， et al. Optimal routing and scheduling of deadlineconstrained traffic over lossy networks[C]// IEEE Global Telecommunications Conference （GLOBECOM）， Miami， Florida， USA： IEEE Press，2010：16.

[6] FRANCESCO C， GIUSEPPE P， CAMARDA P. Downlink packet scheduling in lte cellular networks： Key design issues and a survey [J]. IEEE Commun Surv Tut， 2013， 15（2）： 678700.

[7] DJUKIC P， VALAEE S. Distributed link scheduling for TDMA mesh networks[C]// In Proceedings of IEEE International Conference on Communications （ICC）， Glasgow， Scotland： IEEE Press， 2007：38233828.

[8] WANG Y， WANG W， LI X Y， et al. Interferenceaware joint routing and tdma link scheduling for static wireless networks [J]. IEEE Trans Parall Distr Syst，2008，19（12）：17091726.

[9] SAIFULLASH A， XU Y， CHEN Y. Realtime scheduling for wireless hart networks[C]// In IEEE 31st RealTime Systems Symposium （RTSS）， San Diego， California， USA： IEEE Press， 2010：150159.

[10] HOU I， KUMAR P. Scheduling periodic realtime tasks with heterogeneous reward requirements[C]// In IEEE 32nd RealTime Systems Symposium （RTSS）， Vienna， Austria： IEEE Press， 2011：282291.

[11] 周霞， 钟守铭. 一类概率依赖的随机网络系统的随机容错设计[J]. 计算机工程与应用， 2014， （9）：1720.

[12] SCHNEIDER E R F A， KROHLING R A. A hybrid approach using TOPSIS， Differential Evolution， and Tabu Search to find multiple solutions of constrained nonlinear integer optimization problems [J]. Knowlbased Syst， 2014， 62（3）： 4756.

[13] BESIRIS D， ZIGOURIS E. Dictionarybased color image retrieval using multiset theory [J]. J Vis Commun Imager， 2013，24（7）：11551167.

[14] 薛 明， 高德民. 无线传感器网络最大生命期与最大流路由算法[J]. 计算机工程与应用， 2013，49（12）：6569.

[15] 马 宁， 李开宇， 吴 寅，等. 基于最大流的能量采集型无线传感器网络路由算法[J]. 传感器与微系统， 2013，32（1）：131134.

（编辑 HWJ）