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