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

崔立尉，楊申浩

(1.內(nèi)蒙古農(nóng)業(yè)大學(xué)計(jì)算機(jī)技術(shù)與信息管理系，中國(guó) 包頭　014109；2.內(nèi)蒙古科技大學(xué)信息科學(xué)技術(shù)學(xué)院；中國(guó) 包頭　014010;3.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，中國(guó) 北京　100083)

?

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

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

(1.內(nèi)蒙古農(nóng)業(yè)大學(xué)計(jì)算機(jī)技術(shù)與信息管理系，中國(guó) 包頭014109；2.內(nèi)蒙古科技大學(xué)信息科學(xué)技術(shù)學(xué)院；中國(guó) 包頭014010;3.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，中國(guó) 北京100083)

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

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

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

基于無(wú)線傳感反應(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套國(guó)際標(biāo)準(zhǔn)[2-3]：WirelessHART，ISA 100.11a和IEEE 802.15.4e．這些標(biāo)準(zhǔn)均采用基于IEEE 802.15.4-2006標(biāo)準(zhǔn)且支持2.4 GHz ISM頻段16個(gè)信道的低功率無(wú)線電技術(shù)．然而，采用這些低功率無(wú)線電技術(shù)的設(shè)備非常不可靠，且鏈路質(zhì)量往往具有時(shí)變特性，尤其是惡劣環(huán)境下更是如此，比如存在大量噪聲且對(duì)象移動(dòng)導(dǎo)致頻繁信號(hào)反射現(xiàn)象的工廠車間等．因此，設(shè)計(jì)無(wú)線工業(yè)控制網(wǎng)絡(luò)的關(guān)鍵難點(diǎn)在于，存在信道損耗條件下實(shí)現(xiàn)高可靠性實(shí)時(shí)數(shù)據(jù)通信．

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

為了彌補(bǔ)以上方案的不足，本文假設(shè)不同傳感器設(shè)備具有不同的報(bào)文生成率，不同的無(wú)線鏈路具有不同的報(bào)文丟失率，研究單跳無(wú)線工業(yè)控制網(wǎng)絡(luò)下帶有時(shí)限約束的報(bào)文調(diào)度可靠性問(wèn)題．具體來(lái)說(shuō)，本文貢獻(xiàn)如下：(1)提出一種單跳無(wú)線網(wǎng)絡(luò)的時(shí)限約束異質(zhì)流量理論調(diào)度模型，并給出一種雙階段調(diào)度算法：基于子周期的時(shí)隙分配方案和基于時(shí)隙的傳輸方案．(2)將基于子周期的時(shí)隙分配問(wèn)題表述為線性整數(shù)規(guī)劃問(wèn)題．給出一種多項(xiàng)式時(shí)間算法，可求出基于子周期的時(shí)隙分配問(wèn)題的最優(yōu)解．(3)基于子周期的時(shí)隙分配問(wèn)題的解將會(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)模型和問(wèn)題表述

1.1系統(tǒng)模型

假設(shè)有一個(gè)無(wú)線工業(yè)網(wǎng)絡(luò)由一個(gè)控制器c和N個(gè)無(wú)線傳感器設(shè)備d1,d2,…,dN構(gòu)成．每個(gè)設(shè)備配備一個(gè)半雙工射頻收發(fā)器，表明控制器無(wú)法同時(shí)從多個(gè)傳感器設(shè)備接收?qǐng)?bào)文．所有傳感器設(shè)備可與控制器直接通信(即單跳通信)．時(shí)間經(jīng)過(guò)同步且劃分為多個(gè)長(zhǎng)度相同的時(shí)隙，每個(gè)時(shí)隙可以傳輸一個(gè)數(shù)據(jù)報(bào)文及對(duì)應(yīng)的確認(rèn)報(bào)文．假設(shè)不同無(wú)線鏈路的報(bào)文丟失率互相獨(dú)立，且服從Bernoulli模型[11]．對(duì)于從di到c的每個(gè)報(bào)文傳輸過(guò)程，報(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)周期快要開(kāi)始時(shí)生成的時(shí)間報(bào)文．di生成的報(bào)文的時(shí)限要求與其周期Ti相吻合．如果報(bào)文沒(méi)有在其時(shí)限要求內(nèi)成功傳輸?shù)娇刂破?，則在下個(gè)匯報(bào)周期開(kāi)始時(shí)將其丟棄．

1.2問(wèn)題表述

圖1　子周期和超級(jí)周期示例Fig.1　The sample of subperiod and superperiod

為了確定重傳調(diào)度方案，需要確定為超級(jí)周期內(nèi)每個(gè)新到達(dá)的報(bào)文分配多少個(gè)時(shí)隙．然而，不同報(bào)文的時(shí)隙分配具有強(qiáng)烈的相關(guān)性．分配給一個(gè)報(bào)文的時(shí)隙越多，報(bào)文的成功傳輸概率越高，但是能夠用于分配給其余報(bào)文的時(shí)隙越少．為此，本文使如下目標(biāo)函數(shù)最小化來(lái)對(duì)時(shí)隙分配進(jìn)行優(yōu)化：

(1)

其中wi表示為di生成的報(bào)文所分配的權(quán)重．在部分應(yīng)用中，部分設(shè)備生成的報(bào)文比其他設(shè)備生成的報(bào)文更為重要，因此對(duì)傳輸可靠性要求更高．通過(guò)合理配置每個(gè)設(shè)備的權(quán)重即可實(shí)現(xiàn)這一點(diǎn)．對(duì)于所有報(bào)文具有相同權(quán)重的情況，R對(duì)應(yīng)于控制器在一個(gè)超級(jí)周期內(nèi)接收到的報(bào)文平均數(shù)量．

因?yàn)樗袌?bào)文的傳輸必須在超級(jí)周期內(nèi)進(jìn)行調(diào)度，所以本文問(wèn)題中的第1個(gè)約束為：被分配的時(shí)隙總量不得超過(guò)超級(jí)周期的長(zhǎng)度．

(2)

對(duì)di生成的每個(gè)報(bào)文，其時(shí)限要求與其周期Ti吻合，這要求為di每個(gè)報(bào)文分配的時(shí)隙數(shù)量不得超過(guò)Ti，于是有：

(3)

本文將最優(yōu)時(shí)隙分配問(wèn)題表述為如下優(yōu)化問(wèn)題：

(4)

表1　相關(guān)符號(hào)及其含義

2基于子周期的分配問(wèn)題

基于子周期的時(shí)隙分配問(wèn)題一種非線性整數(shù)規(guī)劃問(wèn)題，該問(wèn)題是NP難題[12]．為此．文中首先將該問(wèn)題轉(zhuǎn)化為一種整數(shù)線性規(guī)劃問(wèn)題，然后給出一種多項(xiàng)式時(shí)間算法，計(jì)算該問(wèn)題的最優(yōu)解．

2.1非線性問(wèn)題到線性問(wèn)題的轉(zhuǎn)化

(5)

假設(shè)C為一個(gè)多重集合[13]，且定義如下：

顯然，R可表示為C中所有元素之和．根據(jù)約束(2)，C的基數(shù)為H．再定義一個(gè)多重集合B：

實(shí)際上，B表示xi,m=Ti時(shí)多重集合C的特例．鑒于式(2)和式(3)中的約束，子周期調(diào)度問(wèn)題任意可行解的多重集C必須是B的一個(gè)子集．例如，圖1(c)中解的多重集C為{4·(1-p1),3·(1-p2),2·(1-p3),3·(1-p1)p1}．下文將證明基于子周期的調(diào)度問(wèn)題可以轉(zhuǎn)化為一個(gè)線性整數(shù)規(guī)劃問(wèn)題．

(6)

2.2最優(yōu)解

假設(shè)O表示包括B中H個(gè)最大元素的多重集．有如下引理1．

(10)

算法1：OPT-SP

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

3：構(gòu)建B的支撐集Bu；

4：選擇Bu中H個(gè)最大元素并按照非升次序形成隊(duì)列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最多只有一個(gè)設(shè)備，其子周期被分配不同數(shù)量的時(shí)隙，且這些分配之間最多相差一個(gè)時(shí)隙．

證算法1中的for循環(huán)(第7~11行)可證明確定bi,k后，只要有可用時(shí)隙用于分配，則di的每個(gè)子周期將獲得一個(gè)時(shí)隙．因此，只有一個(gè)設(shè)備，其子周期可獲得不同數(shù)量的時(shí)隙，當(dāng)最后一輪子周期分配為不充分分配時(shí)才會(huì)出現(xiàn)這一情況．因此，子周期的最大分配差異為1個(gè)時(shí)隙．得證．

上述引理證明本文提供的解可使每個(gè)設(shè)備在不同子周期內(nèi)具有基本相同的報(bào)文投遞率．然而，這無(wú)法保證不同設(shè)備間的公平性．將在第5節(jié)證明通過(guò)調(diào)整分配給每個(gè)設(shè)備的權(quán)重可保證設(shè)備間的公平性．

3基于時(shí)隙的調(diào)度問(wèn)題

前一節(jié)給出的最優(yōu)解只明確了為每個(gè)子周期分配的時(shí)隙最優(yōu)數(shù)量，但是沒(méi)有明確如何分配時(shí)隙(即在哪個(gè)子周期內(nèi)向哪個(gè)設(shè)備分配哪些時(shí)隙)．本節(jié)首先分析已知時(shí)隙分配解后調(diào)度的可行性問(wèn)題，然后給出一種最優(yōu)調(diào)度方案求解方法．

3.1調(diào)度的可行性

引理3約束(2)和(3)是存在可行調(diào)度方案的必要非充分條件．

證定義一個(gè)決策變量zi,j：

使用Z={zi,j,?i∈[1,N],?j∈[1,H]}表示一個(gè)超級(jí)周期的傳輸調(diào)度．很顯然，當(dāng)且僅當(dāng)如下約束滿足時(shí)，Z為可行性調(diào)度．

(11)

該式可保證每個(gè)時(shí)隙只能被分配給一個(gè)傳感器．式(11)還可間接保證分配給所有傳感器的時(shí)隙總數(shù)不得超過(guò)H，即

(12)

在第m個(gè)超級(jí)周期分配給di的時(shí)隙數(shù)量為xi,m，即

(13)

因?yàn)閦i,j非0即1，所以xi,m≤Ti．因此，約束(3)必被滿足．根據(jù)式(12)和式(13)，有

(14)

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

因此，約束(2)和(3)是存在可行性調(diào)度方案的必要條件．然而，約束(2)和(3)不是存在可行性調(diào)度方案的充分條件，因?yàn)槭?11)無(wú)法得到保證．圖2給出的例子中，上述兩個(gè)約束均被滿足但不存在可行性解．網(wǎng)絡(luò)包括兩個(gè)設(shè)備d1和d2且T1=3，T2=5．分配給d15個(gè)子周期的時(shí)隙數(shù)量分別為2、2、2、3、3．設(shè)備d2在其每個(gè)子周期內(nèi)均被分配一個(gè)時(shí)隙．因?yàn)閤1,3=x1,4=3，所以必須在第10個(gè)至第15個(gè)時(shí)隙內(nèi)對(duì)d1進(jìn)行調(diào)度，導(dǎo)致d2無(wú)法在該周期內(nèi)獲得時(shí)隙．因此，基于子周期的時(shí)隙分配不可行．得證．

(15)

根據(jù)引理4，計(jì)算最大流可以獲得一種調(diào)度方案，通過(guò)利用Ford-Fulkerson算法[15]便可有效實(shí)現(xiàn)這一點(diǎn)．然而，F(xiàn)ord-Fulkerson算法的時(shí)間復(fù)雜度高達(dá)O(Ef)，其中E表示邊的數(shù)量，f表示網(wǎng)絡(luò)最大流．下文給出了一種基于容量調(diào)度的求解方法．

(16)

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

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

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

2：根據(jù)式(15)計(jì)算Ns；

3：根據(jù)式(16)計(jì)算Δ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性能評(píng)估

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

4.1與Greedy Maximizer算法的比較

在本文算法中，每個(gè)設(shè)備在每個(gè)超級(jí)周期內(nèi)重復(fù)相同的調(diào)度方案．因此，每個(gè)設(shè)備在不同超級(jí)周期同一子周期內(nèi)的可靠性是相同的．然而，GreedyMaximizer算法從長(zhǎng)期均值角度使系統(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，GreedyMaximizer算法每個(gè)設(shè)備的最小可靠性要求設(shè)置為0．

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

因?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可見(jiàn)，平均差值為2.5，最大差值在8以上．這是因?yàn)镚reedy Maximizer算法將系統(tǒng)性能定義為長(zhǎ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.2wi對(duì)性能的影響

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

(20)

圖5　不同權(quán)重配置條件下每個(gè)設(shè)備每個(gè)子周期接收到的報(bào)文數(shù)量期望值比較　Fig.5　The comparison of packet expectations received period of each device under different weights

(21)

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

(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種方法比較簡(jiǎn)單，所以在下文將利用一個(gè)示例來(lái)闡述第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沒(méi)有被分配任何時(shí)隙，因?yàn)槠鋪G失率太高．如果將權(quán)重調(diào)整為wi=[0.25,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ù)娇刂破鳎ㄟ^(guò)合理調(diào)整權(quán)重，可以確定一種調(diào)度方案滿足每個(gè)設(shè)備的最小要求．

5總結(jié)

本文研究了WSANs中的報(bào)文投遞可靠性問(wèn)題，提出一種雙階段調(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ì)算出上述問(wèn)題的最優(yōu)解．仿真結(jié)果證明本文算法的報(bào)文投遞率遠(yuǎn)高于當(dāng)前算法．此外，本文算法還保證同一設(shè)備不同子周期的性能的公平性，這一特性對(duì)于控制系統(tǒng)的穩(wěn)定性具有重要作用．證明通過(guò)調(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 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ī)網(wǎng)絡(luò)系統(tǒng)的隨機(jī)容錯(cuò)設(shè)計(jì)[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]薛明, 高德民. 無(wú)線傳感器網(wǎng)絡(luò)最大生命期與最大流路由算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013,49(12):65-69.

[15]馬寧, 李開(kāi)宇, 吳寅,等. 基于最大流的能量采集型無(wú)線傳感器網(wǎng)絡(luò)路由算法[J]. 傳感器與微系統(tǒng), 2013,32(1):131-134.

(編輯HWJ)

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

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

A：對(duì)照組明場(chǎng)圖；B：對(duì)照組熒光圖；C：貼壁轉(zhuǎn)染組明場(chǎng)圖；D：貼壁轉(zhuǎn)染組熒光圖；E：懸浮轉(zhuǎn)染組明場(chǎng)圖；F：懸浮轉(zhuǎn)染組熒光圖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　瞬時(shí)轉(zhuǎn)染48 h后的細(xì)胞熒光成像(P.21)Fig.3　Fluorescence image after 48 h of transient transfection(P.21)

A：對(duì)照組熒光圖；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后的細(xì)胞熒光成像(P.22)Fig.4　Fluorescence image after 48 h of virus infection(P.22)

中圖分類號(hào)TP393

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1000-2537(2016)01-0085-010

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目(61471215);國(guó)家自然科學(xué)基金資助項(xiàng)目(61163025)

收稿日期：2015-06-10

DOI:10.7612/j.issn.1000-2537.2016.01.015