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

崔立尉，杨申浩

(1.内蒙古农业大学计算机技术与信息管理系，中国 包头　014109；2.内蒙古科技大学信息科学技术学院；中国 包头　014010;3.清华大学计算机科学与技术系，中国 北京　100083)



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

崔立尉1,2，杨申浩3*

(1.内蒙古农业大学计算机技术与信息管理系，中国 包头014109；2.内蒙古科技大学信息科学技术学院；中国 包头014010;3.清华大学计算机科学与技术系，中国 北京100083)

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

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

A Real-Time Delivery Scheme of Packet Based on Reliability Maximization in Wireless Sensor-Actuator Networks

CUILi-wei1,2,YANGShen-hao3*

(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)

AbstractThe existing packet delivery schemes have a low reliability in wireless sensor-actuator networks (WSANs). Hence, these schemes are not suitable for networks with heterogeneous traffic rates. To solve this problem, a real-time delivery scheme of packet based on reliability maximization is proposed. The packet delivery problem is decomposed into two sub-problems: subperiod-based slot allocation and slot-based transmission scheduling. The former sub-problem is formulated as a linear integer programming problem, and we present a solution with polynomial-time complexity. For the latter sub-problem, 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 wordswireless sensor-actuator networks; traffic; nonlinear integer programming; reliability; slot; packet delivery rate; stability

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

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

图1　子周期和超级周期示例Fig.1　The sample of subperiod and superperiod

为了确定重传调度方案，需要确定为超级周期内每个新到达的报文分配多少个时隙．然而，不同报文的时隙分配具有强烈的相关性．分配给一个报文的时隙越多，报文的成功传输概率越高，但是能够用于分配给其余报文的时隙越少．为此，本文使如下目标函数最小化来对时隙分配进行优化：

(1)

其中wi表示为di生成的报文所分配的权重．在部分应用中，部分设备生成的报文比其他设备生成的报文更为重要，因此对传输可靠性要求更高．通过合理配置每个设备的权重即可实现这一点．对于所有报文具有相同权重的情况，R对应于控制器在一个超级周期内接收到的报文平均数量．

因为所有报文的传输必须在超级周期内进行调度，所以本文问题中的第1个约束为：被分配的时隙总量不得超过超级周期的长度．

(2)

对di生成的每个报文，其时限要求与其周期Ti吻合，这要求为di每个报文分配的时隙数量不得超过Ti，于是有：

(3)

本文将最优时隙分配问题表述为如下优化问题：

(4)

表1　相关符号及其含义

2基于子周期的分配问题

基于子周期的时隙分配问题一种非线性整数规划问题，该问题是NP难题[12]．为此．文中首先将该问题转化为一种整数线性规划问题，然后给出一种多项式时间算法，计算该问题的最优解．

2.1非线性问题到线性问题的转化

(5)

假设C为一个多重集合[13]，且定义如下：

显然，R可表示为C中所有元素之和．根据约束(2)，C的基数为H．再定义一个多重集合B：

实际上，B表示xi,m=Ti时多重集合C的特例．鉴于式(2)和式(3)中的约束，子周期调度问题任意可行解的多重集C必须是B的一个子集．例如，图1(c)中解的多重集C为{4·(1-p1),3·(1-p2),2·(1-p3),3·(1-p1)p1}．下文将证明基于子周期的调度问题可以转化为一个线性整数规划问题．

(6)

2.2最优解

假设O表示包括B中H个最大元素的多重集．有如下引理1．

(10)

算法1：OPT-SP

1：H=lcm{T1,T2,…,TN};

3：构建B的支撑集Bu；

4：选择Bu中H个最大元素并按照非升次序形成队列Q；

5：bi,k=Q→next;

6：whileH>0do

8：更新xi,m=xi,m+1;

9：H=H-1;

10：ifH=0 then

11：break;

12：bi,k=Q→next;

引理2最多只有一个设备，其子周期被分配不同数量的时隙，且这些分配之间最多相差一个时隙．

证算法1中的for循环(第7~11行)可证明确定bi,k后，只要有可用时隙用于分配，则di的每个子周期将获得一个时隙．因此，只有一个设备，其子周期可获得不同数量的时隙，当最后一轮子周期分配为不充分分配时才会出现这一情况．因此，子周期的最大分配差异为1个时隙．得证．

上述引理证明本文提供的解可使每个设备在不同子周期内具有基本相同的报文投递率．然而，这无法保证不同设备间的公平性．将在第5节证明通过调整分配给每个设备的权重可保证设备间的公平性．

3基于时隙的调度问题

前一节给出的最优解只明确了为每个子周期分配的时隙最优数量，但是没有明确如何分配时隙(即在哪个子周期内向哪个设备分配哪些时隙)．本节首先分析已知时隙分配解后调度的可行性问题，然后给出一种最优调度方案求解方法．

3.1调度的可行性

引理3约束(2)和(3)是存在可行调度方案的必要非充分条件．

证定义一个决策变量zi,j：

使用Z={zi,j,∀i∈[1,N],∀j∈[1,H]}表示一个超级周期的传输调度．很显然，当且仅当如下约束满足时，Z为可行性调度．

(11)

该式可保证每个时隙只能被分配给一个传感器．式(11)还可间接保证分配给所有传感器的时隙总数不得超过H，即

(12)

在第m个超级周期分配给di的时隙数量为xi,m，即

(13)

因为zi,j非0即1，所以xi,m≤Ti．因此，约束(3)必被满足．根据式(12)和式(13)，有

(14)

图2　xi,m次序影响示例Fig.2　The sample of xi,m order effect

因此，约束(2)和(3)是存在可行性调度方案的必要条件．然而，约束(2)和(3)不是存在可行性调度方案的充分条件，因为式(11)无法得到保证．图2给出的例子中，上述两个约束均被满足但不存在可行性解．网络包括两个设备d1和d2且T1=3，T2=5．分配给d15个子周期的时隙数量分别为2、2、2、3、3．设备d2在其每个子周期内均被分配一个时隙．因为x1,3=x1,4=3，所以必须在第10个至第15个时隙内对d1进行调度，导致d2无法在该周期内获得时隙．因此，基于子周期的时隙分配不可行．得证．

(15)

根据引理4，计算最大流可以获得一种调度方案，通过利用Ford-Fulkerson算法[15]便可有效实现这一点．然而，Ford-Fulkerson算法的时间复杂度高达O(Ef)，其中E表示边的数量，f表示网络最大流．下文给出了一种基于容量调度的求解方法．

(16)

输入：H,x[i][m],Ti

输出：x[i][m]的可行次序

1：if 对任意di存在max(x[i][m])≠min(x[i][m]) then

2：根据式(15)计算Ns；

3：根据式(16)计算Δl；

6：if Δl<Δminthen

7：Δmin=Δl；

8：Ng++；

11： forj=1 toNgdo

12：t=ΔPs[j];

13：fork=1 totdo

14：x[i*][Ps[j]]++;

15：Ps[j]--;

16：ΔPs[j+1]-=ΔPs[j];

4性能评估

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

4.1与Greedy Maximizer算法的比较

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

表2　网络配置

因为所有传感器设备的权重设置为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.2wi对性能的影响

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

(20)

图5　不同权重配置条件下每个设备每个子周期接收到的报文数量期望值比较　Fig.5　The comparison of packet expectations received period of each device under different weights

(21)

将式(20)代入式(21)，有：

(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=[0.25,0.5,0.25]，则d2被分配的时隙增多，因此一个子周期内接收到的报文预期数量增加到5.4个，控制器接收到的报文总量期望值为16.4．即使最大可靠性略有下降，但是所有3种设备均有机会将其报文传输到控制器．通过合理调整权重，可以确定一种调度方案满足每个设备的最小要求．

5总结

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

参考文献：

[1]MAZO M, TABUADA P. Decentralized event-triggered control over wireless sensor/actuator networks[J]. IEEE Trans Aut Contr, 2011,56(10):2456-2461.

[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:1-6.

[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):53-60.

[4]ERGEN S, VARAIYA P. TDMA scheduling algorithms for wireless sensor networks [J]. Wirel Netw, 2010,16(4):985-997.

[5]SOLDATI P, ZHANG H, ZOU Z,etal. Optimal routing and scheduling of deadline-constrained traffic over lossy networks[C]// IEEE Global Telecommunications Conference (GLOBECOM), Miami, Florida, USA: IEEE Press,2010:1-6.

[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): 678-700.

[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:3823-3828.

[8]WANG Y, WANG W, LI X Y,etal. Interference-aware joint routing and tdma link scheduling for static wireless networks [J]. IEEE Trans Parall Distr Syst,2008,19(12):1709-1726.

[9]SAIFULLASH A, XU Y, CHEN Y. Real-time scheduling for wireless hart networks[C]// In IEEE 31st Real-Time Systems Symposium (RTSS), San Diego, California, USA: IEEE Press, 2010:150-159.

[10]HOU I, KUMAR P. Scheduling periodic real-time tasks with heterogeneous reward requirements[C]// In IEEE 32nd Real-Time Systems Symposium (RTSS), Vienna, Austria: IEEE Press, 2011:282-291.

[11]周霞, 钟守铭. 一类概率依赖的随机网络系统的随机容错设计[J]. 计算机工程与应用, 2014, (9):17-20.

[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 non-linear integer optimization problems [J]. Knowl-based Syst, 2014, 62(3): 47-56.

[13]BESIRIS D, ZIGOURIS E. Dictionary-based color image retrieval using multiset theory [J]. J Vis Commun Imager, 2013,24(7):1155-1167.

[14]薛明, 高德民. 无线传感器网络最大生命期与最大流路由算法[J]. 计算机工程与应用, 2013,49(12):65-69.

[15]马宁, 李开宇, 吴寅,等. 基于最大流的能量采集型无线传感器网络路由算法[J]. 传感器与微系统, 2013,32(1):131-134.

(编辑HWJ)

图1　橙胸姬鹟生境(P.16)Fig.1　Habitat of Rufous-gorgeted Flycatcher(P.16)

图2　橙胸姬鹟(a: 侧面，b: 腹面)(P.17)Fig.2　Rufous-gorgeted Flycatcher (a: side view, b: ventral view)(P.17)

A：对照组明场图；B：对照组荧光图；C：贴壁转染组明场图；D：贴壁转染组荧光图；E：悬浮转染组明场图；F：悬浮转染组荧光图A: Bright filed image of the control group; B: Fluorescence image of the control group; C: Bright filed image of the adherent transfection group; D: Fluorescence image of the adherent transfection group; E: Bright filed image of the suspended transfection group; F: Fluorescence image of the suspended transfection group图3　瞬时转染48 h后的细胞荧光成像(P.21)Fig.3　Fluorescence image after 48 h of transient transfection(P.21)

A：对照组荧光图；B：贴壁包装病毒感染荧光图；C：悬浮包装病毒感染荧光图A: Fluorescence image of the control group; B: Fluorescence image of the infection of virus packaged in adherent status; C: Fluorescence image of the infection of virus packaged in suspended status图4　病毒感染48 h后的细胞荧光成像(P.22)Fig.4　Fluorescence image after 48 h of virus infection(P.22)

中图分类号TP393

文献标识码A

文章编号1000-2537(2016)01-0085-010

*通讯作者,E-mail：3235208763@qq.com

基金项目：国家自然科学基金重点资助项目(61471215);国家自然科学基金资助项目(61163025)

收稿日期：2015-06-10

DOI:10.7612/j.issn.1000-2537.2016.01.015