WSANs中基于可靠性最大化的報(bào)文實(shí)時(shí)投遞方案

崔立尉++楊申浩

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

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

中圖分類號(hào) TP393 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 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

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

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

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

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

1.1 系統(tǒng)模型

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

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

1.2 問題表述

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

4 性能評(píng)估

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

4.1 與Greedy Maximizer算法的比較

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

表2 網(wǎng)絡(luò)配置

Tab.2 The network configuration

群組序列號(hào)NTi群組序列號(hào)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]

因?yàn)樗袀鞲衅髟O(shè)備的權(quán)重設(shè)置為1，所以式（1）中的R等價(jià)于一個(gè)超級(jí)周期內(nèi)接收到的報(bào)文數(shù)量期望值，最小可靠性等于一個(gè)超級(jí)周期內(nèi)生成的報(bào)文總量.我們將平均可靠性定義為一個(gè)超級(jí)周期的平均可靠性與最大可靠性之比.圖3比較了兩種算法在一個(gè)超級(jí)周期內(nèi)的平均可靠性及標(biāo)準(zhǔn)差.可以看出，本文算法在最差情況下可以成功投遞48%的報(bào)文，在最好情況下可成功投遞95%的報(bào)文.Greedy Maximizer算法在大多數(shù)情況下可投遞30%左右的報(bào)文，且不同網(wǎng)絡(luò)配置下的性能相差不大.這是因?yàn)镚reedy Maximizer在提升性能時(shí)的思路是滿足每個(gè)設(shè)備的最小可靠性要求，而不是使可靠性最大.在每個(gè)時(shí)隙期間，可靠性要求較高的任務(wù)在調(diào)度期間被賦予較高的優(yōu)先級(jí)，而本文方法的目標(biāo)是使一個(gè)超級(jí)周期的總可靠性最大.

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

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

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對(duì)性能的影響

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

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

對(duì)每個(gè)設(shè)備di，一個(gè)超級(jí)周期內(nèi)生成HTi個(gè)報(bào)文.于是，下式成立：

圖5 不同權(quán)重配置條件下每個(gè)設(shè)備每個(gè)子周期接收到的報(bào)文數(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)絡(luò)配置下滿足最低要求的可行性.一旦上述不等式成立，則可以按照如下兩種方式進(jìn)行調(diào)度以滿足最低要求：（1）分配給報(bào)文的時(shí)隙由兩部分構(gòu)成，強(qiáng)制型部分（即xi）和可選部分，首先分配強(qiáng)制型部分，以滿足最低要求，然后利用本文算法分配可選部分；（2）調(diào)整分配給每個(gè)設(shè)備的權(quán)重，以滿足最低要求.由于第1種方法比較簡單，所以在下文將利用一個(gè)示例來闡述第2種方法.

圖5給出了每個(gè)設(shè)備在一個(gè)子周期內(nèi)接收到的報(bào)文數(shù)量期望值，其中N=3，[T1，T2，T3]=[3，4，5]，[p1，p2，p3]=[0.6，0.8，0.7].當(dāng)所有3種設(shè)備具有相同權(quán)重時(shí)（wi=[0.33，0.33，0.33]），d1在每個(gè)子周期內(nèi)接收到的報(bào)文數(shù)量最大.然而，d2沒有被分配任何時(shí)隙，因?yàn)槠鋪G失率太高.如果將權(quán)重調(diào)整為wi=[025，0.5，0.25]，則d2被分配的時(shí)隙增多，因此一個(gè)子周期內(nèi)接收到的報(bào)文預(yù)期數(shù)量增加到5.4個(gè)，控制器接收到的報(bào)文總量期望值為16.4.即使最大可靠性略有下降，但是所有3種設(shè)備均有機(jī)會(huì)將其報(bào)文傳輸?shù)娇刂破?通過合理調(diào)整權(quán)重，可以確定一種調(diào)度方案滿足每個(gè)設(shè)備的最小要求.

5 總結(jié)

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

參考文獻(xiàn)：

[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ī)網(wǎng)絡(luò)系統(tǒng)的隨機(jī)容錯(cuò)設(shè)計(jì)[J]. 計(jì)算機(jī)工程與應(yīng)用， 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)絡(luò)最大生命期與最大流路由算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2013，49（12）：6569.

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

（編輯 HWJ）