崔立尉++楊申浩

摘 要 無線傳感反應器網(wǎng)絡（WSANs）中現(xiàn)有的報文投遞方案可靠性不足，不適用于數(shù)據(jù)率互不相同的網(wǎng)絡場景.為此，提出一種基于可靠性最大化的報文實時投遞方案.報文投遞問題被分解為兩個子問題：基于子周期的時隙分配問題和基于時隙的傳輸調(diào)度問題.第1個子問題被轉化為一個線性整數(shù)規(guī)劃問題，并給出一種具有多項式時間復雜度的求解方法.對于第2個子問題，文中證明是否存在最優(yōu)可行調(diào)度取決于求解前一子問題時獲得的時隙分配向量中的元素次序，然后給出一種可行時隙分配方案求解算法.仿真結果表明，本文算法可保證每個設備即使在不同的報告周期內(nèi)也可實現(xiàn)基本相同的報文投遞率，這一特性對于維持控制系統(tǒng)的穩(wěn)定性具有重要作用.

關鍵詞 無線傳感反應器網(wǎng)絡；流量；非線性整數(shù)規(guī)劃；可靠性；時隙；報文投遞率；穩(wěn)定性

中圖分類號 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

基于無線傳感反應器網(wǎng)絡[1]（WSANs）的工業(yè)自動化技術在降低部署成本和提高系統(tǒng)靈活性方面具有巨大優(yōu)勢，因此在近些年引起了研究和工業(yè)領域的大量關注.為了促進WSANs在工業(yè)領域的應用，人們已經(jīng)提出了3套國際標準[23]：WirelessHART，ISA 100.11a和IEEE 802.15.4e.這些標準均采用基于IEEE 802.15.42006標準且支持2.4 GHz ISM頻段16個信道的低功率無線電技術.然而，采用這些低功率無線電技術的設備非常不可靠，且鏈路質量往往具有時變特性，尤其是惡劣環(huán)境下更是如此，比如存在大量噪聲且對象移動導致頻繁信號反射現(xiàn)象的工廠車間等.因此，設計無線工業(yè)控制網(wǎng)絡的關鍵難點在于，存在信道損耗條件下實現(xiàn)高可靠性實時數(shù)據(jù)通信.

在工業(yè)控制領域的WSANs中，傳感器生成的報文往往帶有嚴格的時間約束，如果沒有在截止時間前成功發(fā)送報文將會降低控制性能，導致控制系統(tǒng)性能不夠穩(wěn)定.為了滿足無線通信嚴格的可靠性和實時性要求，所有近期工業(yè)無線標準均采用時分多址（TDMA）技術并將其與時限約束通信調(diào)度策略結合起來.為了提高有損無線信道的傳輸可靠性，被丟失的報文必須進行重傳，基于TDMA的方案往往通過預留額外時隙實現(xiàn)報文重傳.一個關鍵問題是如何進行額外時隙的分配和重傳調(diào)度，以便使控制器在時限范圍內(nèi)接收到所有報文的概率最大.國外學者已經(jīng)針對無線傳感器網(wǎng)絡的最小延時數(shù)據(jù)采集問題提出了多種基于TDMA的鏈路調(diào)度算法[45]，但是這些算法假設每輪數(shù)據(jù)采集期間生成的所有報文具有相同的時限要求，而且只能處理同一數(shù)據(jù)采集周期內(nèi)生成的所有報文具有相同時限約束的同質流量，所以不適用于數(shù)據(jù)率互不相同的工業(yè)應用網(wǎng)絡場景.另外，當前針對蜂窩網(wǎng)絡和無線LAN網(wǎng)絡的調(diào)度算法[69]要么只考慮軟約束，要么假設流量比特率恒定，因此不適用于對可靠性和時限要求非常高的無線工業(yè)控制網(wǎng)絡.文獻[10]研究了不同任務具有不同可靠性要求的周期性實時任務調(diào)度問題，建立了調(diào)度可行性的充分必要條件，并提出稱為Greedy Maximizer的貪婪式在線調(diào)度策略.然而，只有當所有任務的周期相同時貪婪策略才能實現(xiàn)可行性最優(yōu).

為了彌補以上方案的不足，本文假設不同傳感器設備具有不同的報文生成率，不同的無線鏈路具有不同的報文丟失率，研究單跳無線工業(yè)控制網(wǎng)絡下帶有時限約束的報文調(diào)度可靠性問題.具體來說，本文貢獻如下：（1）提出一種單跳無線網(wǎng)絡的時限約束異質流量理論調(diào)度模型，并給出一種雙階段調(diào)度算法：基于子周期的時隙分配方案和基于時隙的傳輸方案.（2）將基于子周期的時隙分配問題表述為線性整數(shù)規(guī)劃問題.給出一種多項式時間算法，可求出基于子周期的時隙分配問題的最優(yōu)解.（3）基于子周期的時隙分配問題的解將會生成一個時隙分配向量，該向量可明確有多少個時隙被分配給哪個設備的哪個匯報周期.因為最優(yōu)性能增益取決于分配向量中的元素數(shù)值，所以我們證明是否存在可行的最優(yōu)調(diào)度方案取決于分配向量中的元素次序.設計了一種可行次序求解算法，可求解出能夠表示可行調(diào)度的次序.

1 系統(tǒng)模型和問題表述

1.1 系統(tǒng)模型

假設有一個無線工業(yè)網(wǎng)絡由一個控制器c和N個無線傳感器設備d1，d2，…，dN構成.每個設備配備一個半雙工射頻收發(fā)器，表明控制器無法同時從多個傳感器設備接收報文.所有傳感器設備可與控制器直接通信（即單跳通信）.時間經(jīng)過同步且劃分為多個長度相同的時隙，每個時隙可以傳輸一個數(shù)據(jù)報文及對應的確認報文.假設不同無線鏈路的報文丟失率互相獨立，且服從Bernoulli模型[11].對于從di到c的每個報文傳輸過程，報文丟失概率為pi.在本文模型中當且僅當發(fā)射器已經(jīng)接收到報文的確認時才認為報文傳輸成功.因此，每條鏈路的報文丟失概率同時考慮了數(shù)據(jù)報文及確認報文的丟失情況.

每個傳感器設備di以Ti個時隙的固定匯報間隔，定期向控制器匯報數(shù)據(jù).每個周期性流量只包括一個在相應匯報周期快要開始時生成的時間報文.di生成的報文的時限要求與其周期Ti相吻合.如果報文沒有在其時限要求內(nèi)成功傳輸?shù)娇刂破?，則在下個匯報周期開始時將其丟棄.

1.2 問題表述

下面首先定義了子周期和超級周期.di的子周期只表示Ti個時隙構成的固定長度的匯報周期，使用Si，m來表示設備di的第m個子周期.超級周期定義為長度固定為H個時隙的周期，其中H表示所有T的最小公倍數(shù)，即H=lcm{T1，…，TN}.因此，對于設備di，一個超級周期包括HTi個子周期，每個子周期需要向控制器傳輸一個報文.圖1給出了子周期和超級周期的示例.可以看到，引入子周期和超級周期后，只需研究一個超級周期內(nèi)的報文傳輸調(diào)度問題即可，因為其余超級周期重復相同的調(diào)度方案.

4 性能評估

本節(jié)利用MATLAB仿真對本文算法進行全面的性能評估.從可靠性最大化和每個設備不同子周期的均衡效果方面對本文算法（表示為OPTSLOT）與文獻[10]中的Greedy Maximizer算法加以比較.還證明了通過調(diào)整每個設備的權重可以保證可靠性.

4.1 與Greedy Maximizer算法的比較

在本文算法中，每個設備在每個超級周期內(nèi)重復相同的調(diào)度方案.因此，每個設備在不同超級周期同一子周期內(nèi)的可靠性是相同的.然而，Greedy Maximizer算法從長期均值角度使系統(tǒng)可靠性最大化，每個設備在不同超級周期同一子周期內(nèi)的可靠性可以不同.為了兼顧公平，確定仿真實驗內(nèi)容如下：選擇具有不同N和Ti的7種網(wǎng)絡配置，如表2所示.對每種網(wǎng)絡配置，我們設置不同的報文丟失率進行1 000次仿真實驗.每次仿真時，每條鏈路的報文丟失率從[0.2， 0.8]中均勻選擇，且在仿真期間保持不變.每次仿真持續(xù)200個超級周期.在該組仿真中，式（1）中所有傳感器設備的權重設置為1，Greedy Maximizer算法每個設備的最小可靠性要求設置為0.

表2 網(wǎng)絡配置

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等價于一個超級周期內(nèi)接收到的報文數(shù)量期望值，最小可靠性等于一個超級周期內(nèi)生成的報文總量.我們將平均可靠性定義為一個超級周期的平均可靠性與最大可靠性之比.圖3比較了兩種算法在一個超級周期內(nèi)的平均可靠性及標準差.可以看出，本文算法在最差情況下可以成功投遞48%的報文，在最好情況下可成功投遞95%的報文.Greedy Maximizer算法在大多數(shù)情況下可投遞30%左右的報文，且不同網(wǎng)絡配置下的性能相差不大.這是因為Greedy Maximizer在提升性能時的思路是滿足每個設備的最小可靠性要求，而不是使可靠性最大.在每個時隙期間，可靠性要求較高的任務在調(diào)度期間被賦予較高的優(yōu)先級，而本文方法的目標是使一個超級周期的總可靠性最大.

圖4給出了同一設備不同子周期被分配的時隙數(shù)量平均差值及標準差.可以看出，本文算法的平均差值小于0.2.這是因為最多只有一個設備其不同子周期可被分配不同數(shù)量的時隙，且互相之間最多相差1個時隙（參考引理3），表明每個設備在不同子周期內(nèi)基本具有相同的可靠性.這種設備內(nèi)可靠性可提升控制系統(tǒng)的穩(wěn)定性.Greedy Maximizer算法生成的傳輸調(diào)度方案，其波動性更強.從圖4可見，平均差值為2.5，最大差值在8以上.這是因為Greedy Maximizer算法將系統(tǒng)性能定義為長期平均可靠性，在每個時隙期間該算法貪婪地選擇可靠性要求最高的任務加以執(zhí)行，導致不同子周期的可靠性發(fā)生波動.這些波動現(xiàn)象可能會影響工業(yè)系統(tǒng)的性能.

圖3 不同網(wǎng)絡配置下可靠性期望值的比較情況

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對性能的影響

本文算法可保證同一設備不同子周期性能的公平性，但是不保證不同設備間的公平性.在本文算法中，報文丟失率較低的設備被調(diào)度的概率較高.在許多工業(yè)控制應用中，每個傳感器設備對于從自己到達控制器的報文投遞率有最低要求.用ri來表示di在一個子周期內(nèi)應該實現(xiàn)的最低可靠性.假設xi表示為了滿足最小可靠性，每個子周期內(nèi)應該分配給di的時隙最小數(shù)量.于是有：

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

對每個設備di，一個超級周期內(nèi)生成HTi個報文.于是，下式成立：

圖5 不同權重配置條件下每個設備每個子周期接收到的報文數(shù)量期望值比較

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）

利用上式可以檢查在某種網(wǎng)絡配置下滿足最低要求的可行性.一旦上述不等式成立，則可以按照如下兩種方式進行調(diào)度以滿足最低要求：（1）分配給報文的時隙由兩部分構成，強制型部分（即xi）和可選部分，首先分配強制型部分，以滿足最低要求，然后利用本文算法分配可選部分；（2）調(diào)整分配給每個設備的權重，以滿足最低要求.由于第1種方法比較簡單，所以在下文將利用一個示例來闡述第2種方法.

圖5給出了每個設備在一個子周期內(nèi)接收到的報文數(shù)量期望值，其中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在每個子周期內(nèi)接收到的報文數(shù)量最大.然而，d2沒有被分配任何時隙，因為其丟失率太高.如果將權重調(diào)整為wi=[025，0.5，0.25]，則d2被分配的時隙增多，因此一個子周期內(nèi)接收到的報文預期數(shù)量增加到5.4個，控制器接收到的報文總量期望值為16.4.即使最大可靠性略有下降，但是所有3種設備均有機會將其報文傳輸?shù)娇刂破?通過合理調(diào)整權重，可以確定一種調(diào)度方案滿足每個設備的最小要求.

5 總結

本文研究了WSANs中的報文投遞可靠性問題，提出一種雙階段調(diào)度算法，首先采取優(yōu)化策略將時隙分配給每個設備的不同子周期，以便實現(xiàn)可靠性最大化，然后利用基于時隙的調(diào)度策略構建傳輸調(diào)度方案.即使目標函數(shù)為關于分配給每個子周期的時隙數(shù)量的非線性函數(shù)且該函數(shù)往往是NP難題，提出一種多項式時間復雜度求解算法，可計算出上述問題的最優(yōu)解.仿真結果證明本文算法的報文投遞率遠高于當前算法.此外，本文算法還保證同一設備不同子周期的性能的公平性，這一特性對于控制系統(tǒng)的穩(wěn)定性具有重要作用.證明通過調(diào)整分配給每個設備的權重可以控制不同設備的可靠性，進而滿足每個設備的最小可靠性要求.下步工作主要是對權重和最小可靠性要求之間的關系進行分析.

參考文獻：

[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] 周霞， 鐘守銘. 一類概率依賴的隨機網(wǎng)絡系統(tǒng)的隨機容錯設計[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] 薛 明， 高德民. 無線傳感器網(wǎng)絡最大生命期與最大流路由算法[J]. 計算機工程與應用， 2013，49（12）：6569.

[15] 馬 寧， 李開宇， 吳 寅，等. 基于最大流的能量采集型無線傳感器網(wǎng)絡路由算法[J]. 傳感器與微系統(tǒng)， 2013，32（1）：131134.

（編輯 HWJ）