王忠鋒，張 楠，4，夏長清，尚志軍，田 宇，4，金 曦，許 馳

1(中國科學(xué)院 網(wǎng)絡(luò)化控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，沈陽 110016) 2(中國科學(xué)院 沈陽自動(dòng)化研究所工業(yè)控制網(wǎng)絡(luò)與系統(tǒng)研究室，沈陽110016) 3(中國科學(xué)院 機(jī)器人與智能創(chuàng)造創(chuàng)新研究院，沈陽 110169) 4(中國科學(xué)院大學(xué)，北京 100049)

1 引 言

近年來，工業(yè)無線網(wǎng)絡(luò)的研究引起了越來越多的關(guān)注，并逐漸成為發(fā)展的熱點(diǎn)[1].隨著工業(yè)互聯(lián)網(wǎng)與智能工廠的興起，無線網(wǎng)絡(luò)的規(guī)模正在不斷擴(kuò)大，工業(yè)無線網(wǎng)絡(luò)已成為工業(yè)控制系統(tǒng)的重要組成部分.對(duì)于工業(yè)系統(tǒng)，實(shí)時(shí)性保障至關(guān)重要.目前，主流工業(yè)無線協(xié)議大多采用TDMA(Time Division Multiple Access，時(shí)分多址)技術(shù)確保網(wǎng)絡(luò)系統(tǒng)的實(shí)時(shí)性.然而，有限的網(wǎng)絡(luò)資源難以滿足工業(yè)控制系統(tǒng)中大量指令、數(shù)據(jù)的實(shí)時(shí)需求.

數(shù)據(jù)聚合傳輸[2]是提高網(wǎng)絡(luò)資源利用率的有效手段.通過對(duì)多個(gè)數(shù)據(jù)包中有效數(shù)據(jù)進(jìn)行解析、聚合，實(shí)現(xiàn)一組包頭校驗(yàn)位下的多組有效數(shù)據(jù)傳輸.聚合傳輸可以減少數(shù)據(jù)包在重疊鏈路上的傳輸次數(shù)，緩解傳輸沖突，減少網(wǎng)絡(luò)資源需求.然而，聚合傳輸主要用于實(shí)時(shí)性較低的大數(shù)據(jù)量傳輸以及樹狀拓?fù)渚W(wǎng)絡(luò)，難以滿足工業(yè)控制實(shí)際需求[3].針對(duì)此問題，本文研究了網(wǎng)狀拓?fù)湎碌墓I(yè)無線網(wǎng)絡(luò)實(shí)時(shí)聚合傳輸問題，主要貢獻(xiàn)如下：

1.提出網(wǎng)狀拓?fù)湎碌膶?shí)時(shí)聚合調(diào)度新方法EDF-PA，該算法通過在路徑重疊區(qū)域采用基于優(yōu)先級(jí)排序被動(dòng)聚合等待的方式對(duì)數(shù)據(jù)包進(jìn)行聚合，低優(yōu)先級(jí)數(shù)據(jù)包在聚合點(diǎn)被動(dòng)等待高優(yōu)先級(jí)數(shù)據(jù)包到來后進(jìn)行聚合，在不改變高優(yōu)先級(jí)數(shù)據(jù)包傳輸規(guī)則的情況下提高系統(tǒng)整體傳輸效率.仿真結(jié)果表明，EDF-PA方法比傳統(tǒng)聚合方法調(diào)度成功率提升20%；在考慮網(wǎng)絡(luò)丟包時(shí)，性能仍可提升5%.

2.為進(jìn)一步提高重疊區(qū)域數(shù)據(jù)包的聚合度，提出一種改進(jìn)的聚合調(diào)度算法EDF-OPA，EDF-OPA首先對(duì)EDF-PA調(diào)度表進(jìn)行檢測，當(dāng)檢測到聚合后數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點(diǎn)后產(chǎn)生延遲等待時(shí)，EDF-OPA將以數(shù)據(jù)流可調(diào)度性為約束，令滿足約束的數(shù)據(jù)流主動(dòng)聚合等待，通過延遲等待時(shí)間最大化特定重疊區(qū)域的數(shù)據(jù)包聚合度，提高信道資源利用率.改進(jìn)算法能有效提高工業(yè)無線系統(tǒng)性能，將調(diào)度成功率提升35%；在網(wǎng)絡(luò)丟包嚴(yán)重時(shí)，性能仍可提升20%.

2 相關(guān)研究

工業(yè)無線網(wǎng)絡(luò)資源有限，聚合傳輸是在受限的資源條件下提高傳輸性能的有效方法.工業(yè)無線網(wǎng)絡(luò)中的數(shù)據(jù)聚合調(diào)度方法目前已有廣泛研究.文獻(xiàn)[4]提出了基于簇的無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合經(jīng)典算法LEACH.通過隨機(jī)選取的簇頭節(jié)點(diǎn)從簇中成員收集數(shù)據(jù)進(jìn)行聚合，并將聚合后的數(shù)據(jù)通過其他簇頭以單跳或多跳的方式與基站通信[5].此后，研究人員通過使用路由協(xié)議[6]和優(yōu)化簇頭的選擇[7]來提高LEACH算法的性能；另一方面，也引入了多輸入多輸出[8]、網(wǎng)絡(luò)編碼[9]、機(jī)會(huì)路由[10]和空中接入點(diǎn)[11]等方法做進(jìn)一步優(yōu)化.然而，這些技術(shù)主要關(guān)注減少節(jié)點(diǎn)能耗以延長生命周期，沒有考慮數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性能.

為了降低數(shù)據(jù)聚合帶來的時(shí)延影響，文獻(xiàn)[12]使用了經(jīng)典的聚合調(diào)度算法(Earliest Deadline First Scheduling Method with a First Fit bin-packing algorithm，EDF-FF)，通過FF算法分配資源與EDF調(diào)度算法的結(jié)合來提高網(wǎng)絡(luò)的實(shí)時(shí)性.為了進(jìn)一步提高聚合調(diào)度的性能，可通過建立最優(yōu)的聚合樹來得到聚合方案，構(gòu)建最優(yōu)聚合樹得到最小延遲的聚合方案已被證明是NP-hard問題[13，14].文獻(xiàn)[15]提出了基于自適應(yīng)的分布式馬爾可夫近似算法構(gòu)造最小延遲數(shù)據(jù)聚合樹來降低聚合延遲.文獻(xiàn)[16]通過蜻蜓算法(DA)查找網(wǎng)絡(luò)延遲和數(shù)據(jù)包傳輸速率表現(xiàn)好的最佳聚合樹.文獻(xiàn)[17]提出每個(gè)簇頭先將數(shù)據(jù)進(jìn)行壓縮聚合，再使用最小生成樹(MST)構(gòu)造聚合樹，并綜合考慮丟包率和時(shí)延等指標(biāo)分配通信資源.上述方法均通過構(gòu)建聚合樹實(shí)現(xiàn)聚合[18]，雖然可以提高網(wǎng)絡(luò)通信的實(shí)時(shí)性能，但僅適用于樹狀拓?fù)浣Y(jié)構(gòu)的無線網(wǎng)絡(luò).

網(wǎng)狀拓?fù)浣Y(jié)構(gòu)具有高度魯棒性，是工業(yè)無線網(wǎng)絡(luò)中最為常見的拓?fù)浣Y(jié)構(gòu)，也是下一代工業(yè)無線系統(tǒng)中的關(guān)鍵組成部分[19].因此，迫切需要面向網(wǎng)狀拓?fù)渚W(wǎng)絡(luò)的實(shí)時(shí)聚合傳輸方法研究.

3 系統(tǒng)模型及問題描述

3.1 系統(tǒng)模型

工業(yè)無線網(wǎng)絡(luò)中數(shù)據(jù)流的傳輸路徑，由源設(shè)備到目的設(shè)備之間的一系列有序鏈路組成，其傳輸路徑由網(wǎng)絡(luò)層的路由算法計(jì)算得出，數(shù)據(jù)包采用多跳的形式沿著傳輸路徑在分配的時(shí)隙和信道上進(jìn)行傳輸.在工業(yè)無線網(wǎng)絡(luò)中，數(shù)據(jù)的傳輸主要存在兩種沖突，分別是傳輸沖突與信道沖突.傳輸沖突指工業(yè)現(xiàn)場設(shè)備采用單天線的通信方式，設(shè)備不能在同一時(shí)隙下既發(fā)送數(shù)據(jù)又接收數(shù)據(jù).信道沖突要求在同一時(shí)隙下，若當(dāng)前待調(diào)度鏈路的總數(shù)超過可用信道數(shù)，則不能在當(dāng)前時(shí)隙下調(diào)度所有鏈路.當(dāng)前時(shí)隙未調(diào)度的通信鏈路只能安排到下一時(shí)隙.當(dāng)數(shù)據(jù)流傳輸至相同節(jié)點(diǎn)附近時(shí)，由于傳輸沖突的限制，相互沖突的鏈路必須安排在不同的時(shí)隙，因此會(huì)減少可用時(shí)隙，導(dǎo)致數(shù)據(jù)流不能在截止時(shí)間內(nèi)分配到充足的通信資源，影響數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性.

WirelessHART是典型工業(yè)無線網(wǎng)絡(luò)通信協(xié)議，其應(yīng)用較為廣泛.可以將基于WirelessHART組建的網(wǎng)絡(luò)系統(tǒng)抽象為G=(V，E)，V表示網(wǎng)絡(luò)中所有設(shè)備，E表示設(shè)備之間的通信鏈路.令所有工業(yè)設(shè)備的總數(shù)為|V|，則網(wǎng)絡(luò)中所有設(shè)備可表示為V={V1，V2，…，VI，…}.一條有向邊e=(Vu，Vv)表示設(shè)備Vu向設(shè)備Vv發(fā)送數(shù)據(jù).工業(yè)無線網(wǎng)絡(luò)數(shù)據(jù)流沿著通信鏈路傳輸，數(shù)據(jù)流通過多跳的形式在分配好的時(shí)隙和信道上進(jìn)行傳輸.網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)量為|F|，可表示為F={f1，f2，…fj，…}，將數(shù)據(jù)流定義為fi=.對(duì)于任意數(shù)據(jù)流fi，數(shù)據(jù)包的生成周期為pi，數(shù)據(jù)包原始有效負(fù)載為si.本文設(shè)定數(shù)據(jù)包原始負(fù)載長度相同，即si=s.將聚合的數(shù)據(jù)包解聚時(shí)需要識(shí)別出聚合包中不同的數(shù)據(jù)報(bào)文，聚合時(shí)在數(shù)據(jù)包有效負(fù)載前加入一個(gè)長度標(biāo)識(shí)h，定義聚合有效負(fù)載的上界為Smax.數(shù)據(jù)包長度定義為L，表示有效負(fù)載長度、數(shù)據(jù)包頭長度和校驗(yàn)部分的長度之和.

圖1 數(shù)據(jù)幀結(jié)構(gòu)Fig.1 Data frame structure

數(shù)據(jù)包的數(shù)據(jù)幀結(jié)構(gòu)如圖1所示.網(wǎng)絡(luò)中數(shù)據(jù)流的路徑可表示為R={R1，R2，…Rm}.數(shù)據(jù)流沿通信路徑傳輸?shù)奶鴶?shù)為ci.對(duì)于網(wǎng)絡(luò)中的數(shù)據(jù)流fi，令di表示其相對(duì)截止時(shí)隙，為保證數(shù)據(jù)流產(chǎn)生后在給定的截止時(shí)間內(nèi)傳送至目的節(jié)點(diǎn)，應(yīng)滿足ci≤di≤pi.定義整個(gè)網(wǎng)絡(luò)中所有數(shù)據(jù)流周期的最小公倍數(shù)為網(wǎng)絡(luò)的超幀周期P.網(wǎng)絡(luò)可用信道數(shù)目為M，丟包率為l.

無線網(wǎng)絡(luò)數(shù)據(jù)流模型的示例如圖2所示.在網(wǎng)狀拓?fù)浣Y(jié)構(gòu)中，根據(jù)EDF調(diào)度方法為3條數(shù)據(jù)流分配時(shí)隙與信道資源.這里3條數(shù)據(jù)流優(yōu)先級(jí)相同，則依照優(yōu)先傳輸較小編號(hào)數(shù)據(jù)流的規(guī)則，可得基于EDF調(diào)度方法的調(diào)度表，此時(shí)數(shù)據(jù)流f3的8-9鏈路因錯(cuò)失截止期而不可調(diào)度.選用常見于樹狀網(wǎng)絡(luò)中的經(jīng)典聚合調(diào)度方法[12]得到新調(diào)度表.在第3時(shí)隙，根據(jù)聚合調(diào)度方法的原理，數(shù)據(jù)流f1在節(jié)點(diǎn)4處等待與即將到達(dá)的數(shù)據(jù)流f2聚合傳輸；同樣的，數(shù)據(jù)流f3從第4時(shí)隙開始在節(jié)點(diǎn)8處等待與路徑重合的f1聚合并在第6時(shí)隙傳輸8-9鏈路.其中數(shù)據(jù)流f1與f3的等待時(shí)間均滿足可調(diào)度性約束，但導(dǎo)致數(shù)據(jù)流f2的5-9鏈路的傳輸因存在傳輸沖突無法在截止時(shí)間前分到信道資源最終不可調(diào)度.由于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)復(fù)雜，聚合包在重疊鏈路流出節(jié)點(diǎn)處需要占用更多的通信資源將各解聚的包傳到各自的目的節(jié)點(diǎn)，而樹狀拓?fù)渚酆虾髣t不需要解聚傳輸，所以傳統(tǒng)的用于樹狀拓?fù)涞木酆险{(diào)度方法并不適用于網(wǎng)狀拓?fù)?因此，設(shè)計(jì)出在網(wǎng)狀拓?fù)湎掠行У膶?shí)時(shí)聚合調(diào)度方法尤為重要.

3.2 問題描述

對(duì)于支持?jǐn)?shù)據(jù)包聚合解聚功能的工業(yè)無線網(wǎng)絡(luò)，應(yīng)通過設(shè)計(jì)算法保證數(shù)據(jù)包等待聚合的延時(shí)消耗滿足截止時(shí)間約束，且聚合有效數(shù)據(jù)負(fù)載小于聚合上限.通過數(shù)據(jù)包的聚合減少節(jié)點(diǎn)轉(zhuǎn)發(fā)路徑重疊的數(shù)據(jù)包的傳輸次數(shù)，提高網(wǎng)絡(luò)資源利用率，保證每條數(shù)據(jù)流都可調(diào)度.聚合執(zhí)行時(shí)間與傳輸時(shí)間相比可忽略不計(jì)，因此問題可以被描述為：

(1)

其中，F(xiàn)*={f1,f2,…fi},F*為網(wǎng)絡(luò)中可調(diào)度的數(shù)據(jù)流集合.在上述數(shù)學(xué)描述中，公式(1)表示聚合問題的目標(biāo)是保證盡量多的數(shù)據(jù)流在截止時(shí)間內(nèi)成功傳輸?shù)竭_(dá)目的節(jié)點(diǎn)，提高數(shù)據(jù)流的可調(diào)度性.聚合問題的目標(biāo)，即公式(1)需滿足以下約束條件：

1)截止時(shí)間約束：端到端數(shù)據(jù)流需要在其截止時(shí)間內(nèi)傳輸成功.

(2)

(3)

minci(wait)

(4)

2)信道約束：在同一時(shí)隙下，網(wǎng)絡(luò)調(diào)度的鏈路總數(shù)不能超過可用信道數(shù)，以免造成信道沖突，則：

∑(u,v)∈Eζt(u,v)≤M

(5)

3)傳輸沖突約束：工業(yè)現(xiàn)場設(shè)備采用單天線的通信方式，設(shè)備不能在同一時(shí)隙下既發(fā)送數(shù)據(jù)又接收來自其他設(shè)備的數(shù)據(jù).

∑(u,v)∈Eg(u)ζt(u,v)+∑(v，u)∈Hg(v)ζt(v,u)≤1

(6)

ζt(u,v)∈{0,1}，ζt(v,u)∈{0,1}

(7)

ζt(v,u)表示時(shí)隙設(shè)備u和v之間的鏈路傳輸狀態(tài).若通信鏈路(u,v)在t時(shí)隙可以傳輸數(shù)據(jù)流，則ζt(u,v)=1；反之，ζt(u,v)=0.Eg(u)表示當(dāng)前時(shí)隙以設(shè)備u為發(fā)送方的鏈路集合，Hg(v)為當(dāng)前時(shí)隙以設(shè)備v為接收方的鏈路集合.

4)聚合有效負(fù)載長度約束：聚合傳輸時(shí)，聚合數(shù)據(jù)包的有效負(fù)載長度需滿足聚合長度上限.

h=「log2x?

(8)

Su=n×(s+h)

(9)

Su≤Smax

(10)

公式(8)表示數(shù)據(jù)包聚合標(biāo)識(shí)長度的計(jì)算方式，其中，x為流經(jīng)各網(wǎng)絡(luò)設(shè)備數(shù)據(jù)流數(shù)量的最大值，在當(dāng)前網(wǎng)絡(luò)中聚合標(biāo)識(shí)長度在各設(shè)備處均為固定值.例如，當(dāng)前網(wǎng)絡(luò)中流經(jīng)網(wǎng)絡(luò)設(shè)備數(shù)據(jù)流數(shù)目中最大值為7，在各節(jié)點(diǎn)處聚合標(biāo)識(shí)長度取值為3.將各網(wǎng)絡(luò)設(shè)備的聚合解聚標(biāo)識(shí)位設(shè)置為開啟狀態(tài)，通過識(shí)別數(shù)據(jù)包頭與有效數(shù)據(jù)部分之間的聚合標(biāo)識(shí)來確定是否需要解聚該數(shù)據(jù)包.公式(9)表示設(shè)備u處的n個(gè)數(shù)據(jù)包聚合后的有效負(fù)載長度.公式(10)為聚合長度約束.

5)聚合度約束：模型希望聚合盡量多的數(shù)據(jù)包以提高網(wǎng)絡(luò)資源利用率.

max∑u∈VSu

(11)

4 聚合調(diào)度方法

4.1 考慮數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度方法

考慮數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度方法(Earliest Deadline First Scheduling Method considered on Packet Aggregation，EDF-PA)的主要思想是：首先將當(dāng)前時(shí)隙下傳輸至重疊鏈路流入節(jié)點(diǎn)的多個(gè)數(shù)據(jù)包進(jìn)行聚合，然后在傳輸至重疊鏈路末端節(jié)點(diǎn)處進(jìn)行解聚，解聚后的數(shù)據(jù)包沿著后續(xù)各自不同的路徑傳輸.該方法能夠有效緩解數(shù)據(jù)流路徑重疊導(dǎo)致的傳輸沖突，顯著降低數(shù)據(jù)流在通信鏈路傳輸時(shí)對(duì)網(wǎng)絡(luò)資源的需求；并在不改變數(shù)據(jù)包按優(yōu)先級(jí)傳輸規(guī)則的情況下，提高系統(tǒng)的整體傳輸效率與實(shí)時(shí)性.EDF-PA調(diào)度方法比經(jīng)典調(diào)度方法的復(fù)雜度大，延長了算法的執(zhí)行時(shí)間，但由于調(diào)度算法離線進(jìn)行，可以滿足工業(yè)無線網(wǎng)絡(luò)的實(shí)時(shí)性需求.

EDF-PA算法執(zhí)行過程如下：

1)首先根據(jù)網(wǎng)絡(luò)輸入?yún)?shù)初始化網(wǎng)絡(luò)狀態(tài)與調(diào)度表(第1行).

2)在當(dāng)前時(shí)隙下，若有數(shù)據(jù)流超出截止時(shí)間則返回不可調(diào)度；否則可進(jìn)入下一步.(3～5行)

3)當(dāng)前時(shí)隙下數(shù)據(jù)包在重疊鏈路的流入節(jié)點(diǎn)處等待分配信道資源，若有其他路徑重疊的包傳輸至該節(jié)點(diǎn)，且滿足數(shù)據(jù)包聚合后的有效負(fù)載長度上限，將節(jié)點(diǎn)處的多個(gè)數(shù)據(jù)包聚合成一個(gè)包(6～8行)，選擇聚合的多個(gè)數(shù)據(jù)包中截止時(shí)間最小值作為整個(gè)數(shù)據(jù)包的優(yōu)先級(jí)判斷依據(jù)(9～11行).

4)將聚合的包與其他數(shù)據(jù)包一起根據(jù)EDF方法計(jì)算的優(yōu)先級(jí)依次分配通信資源，若優(yōu)先級(jí)較高，可直接將數(shù)據(jù)包傳輸至下一節(jié)點(diǎn)，若優(yōu)先級(jí)較低，則根據(jù)調(diào)度規(guī)則令其在當(dāng)前節(jié)點(diǎn)處等待下一時(shí)隙重新計(jì)算優(yōu)先級(jí)排序(12～13行)，并更新數(shù)據(jù)流的傳輸狀態(tài)與調(diào)度表(14～16行).

5)將整個(gè)超幀的資源都分配完后可得到數(shù)據(jù)流調(diào)度表(17～20行).

EDF-PA算法的偽代碼如算法1所示.

算法1.考慮數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度算法

輸入：網(wǎng)絡(luò)拓?fù)銰=(U，V)，數(shù)據(jù)流F={f1,f2,…fj,…)，信道數(shù)目M，網(wǎng)絡(luò)超幀P，聚合有效負(fù)載長度上限Smax

輸出：sche[1…M][1…P]

1.初始化調(diào)度表sche[1…M][1…P]

2.whilep!=0do

3.ifP-p

4.return不可調(diào)度信息

5.else

6.fori=1to{R}

7.if節(jié)點(diǎn)i存在多條數(shù)據(jù)流有相同下一跳節(jié)點(diǎn)andsumsi

8.在當(dāng)前節(jié)點(diǎn)聚合數(shù)據(jù)流

9.newd=mind(f1,f2,…fm)

10.endif

11.endfor

12.用EDF調(diào)度方法為數(shù)據(jù)流分配M條信道

13.更新各數(shù)據(jù)流的傳輸狀態(tài)

14.foriinM

15.sche[i][p]=i→next[i]

16.endfor

17.p- -

18.endif

19.endwhile

20.returnsche[1…M][1…P]

基于EDF-PA方法，圖2的無線網(wǎng)絡(luò)數(shù)據(jù)流模型示例中數(shù)據(jù)流f1僅與數(shù)據(jù)流f3在第5時(shí)隙的8-9鏈路聚合傳輸，此時(shí)3條數(shù)據(jù)流均可調(diào)度.

4.2 優(yōu)化數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度算法

上節(jié)提出的EDF-PA方法雖然能有效提高網(wǎng)絡(luò)資源利用率，但并不能保證得到聚合數(shù)據(jù)包最多的調(diào)度結(jié)果.為進(jìn)一步提高重疊區(qū)域數(shù)據(jù)包聚合度，本節(jié)提出了優(yōu)化的數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度方法(Earliest Deadline First Scheduling Method considered on Optimized Packet Aggregation，EDF-OPA).

EDF-OPA算法檢測到EDF-PA調(diào)度表中聚合后數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點(diǎn)后產(chǎn)生延遲等待時(shí)，以數(shù)據(jù)流可調(diào)度性為約束，令滿足約束的數(shù)據(jù)流主動(dòng)聚合等待，等待下一個(gè)數(shù)據(jù)包進(jìn)行聚合.因此，主動(dòng)聚合等待的方式在滿足高優(yōu)先級(jí)數(shù)據(jù)流可調(diào)度性的約束下，通過犧牲少量時(shí)隙資源作為額外的等待時(shí)間消耗，等待下一個(gè)到達(dá)的數(shù)據(jù)包進(jìn)行聚合.有效提高重疊區(qū)域數(shù)據(jù)包聚合度，充分利用原本調(diào)度表中因傳輸沖突而不可占用的信道資源.同時(shí)，節(jié)省出來信道資源可以分配給其它無傳輸沖突的數(shù)據(jù)流或原本不可調(diào)度的數(shù)據(jù)流，提高信道資源利用率.EDF-OPA算法通過犧牲部分時(shí)隙資源換取更高的聚合度及信道資源利用率，實(shí)現(xiàn)系統(tǒng)性能的二次提升.雖然算法的時(shí)間復(fù)雜度變大，但由于算法離線完成，仍能滿足實(shí)際工業(yè)應(yīng)用的實(shí)時(shí)性要求.

EDF-OPA算法的初始化與聚合調(diào)度過程與EDF-PA算法相同(1～13行).在聚合調(diào)度的同時(shí)，EDF-OPA動(dòng)態(tài)檢測調(diào)度表，若在某個(gè)時(shí)隙檢測到聚合數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點(diǎn)后產(chǎn)生延遲等待，可在滿足可調(diào)度性約束下，令這個(gè)包主動(dòng)等待一個(gè)不會(huì)產(chǎn)生沖突的時(shí)隙(14～17行).返回上一時(shí)隙重新根據(jù)EDF調(diào)度分配通信資源，更新數(shù)據(jù)流的傳輸狀態(tài)和調(diào)度表(18～23行).將整個(gè)超幀的資源都分配完后可得到優(yōu)化的調(diào)度表(23～27行).

EDF-OPA算法的偽代碼如算法2所示.

算法2.優(yōu)化數(shù)據(jù)包聚合的最短截止時(shí)間調(diào)度算法

輸入：網(wǎng)絡(luò)拓?fù)銰=(U，V)，數(shù)據(jù)流F={f1,f2,…，fj，…)，信道數(shù)目M，網(wǎng)絡(luò)超幀P，聚合有效負(fù)載長度上限Smax

輸出：sche[1…M][1…P]

1.初始化調(diào)度表sche[1…M][1…P]

2.whilep!=0do

3.ifP-p

4.return不可調(diào)度信息

5.else

6.fori=1to{R}

7.if節(jié)點(diǎn)i存在多條數(shù)據(jù)流有相同下一跳節(jié)點(diǎn)andsumsi

8.在當(dāng)前節(jié)點(diǎn)聚合數(shù)據(jù)流

9.newd=mind(f1,f2,…fm)

10.endif

11.endfor

12.用EDF調(diào)度方法為數(shù)據(jù)流分配M條信道

13.ifM>count(p時(shí)隙可傳輸數(shù)據(jù)流)

14.finde((e=(Vu,Vv)in

sche[M][p+1]&

(Vu,Vv?/sche[M][p]))

15.令鏈路e等待至p時(shí)隙再傳輸

16.p=p+1

17.重新根據(jù)EDF調(diào)度方法分配信道

18.更新各數(shù)據(jù)流的傳輸狀態(tài)

19.foriinM

20.sche[i][p]=i→next[i]

21.endfor

22.endif

23.p- -

24.endif

25.endwhile

26.returnsche[1…M][1…P]

4.3 復(fù)雜度分析

EDF-PA算法需遍歷條數(shù)據(jù)流中的最長路徑范圍，并在每個(gè)時(shí)隙計(jì)算數(shù)據(jù)流的優(yōu)先級(jí)并排序，令網(wǎng)絡(luò)中數(shù)據(jù)流路徑的最大長度為C，則EDF-PA算法的時(shí)間復(fù)雜度為O(P×|F|2×log|F|×C).EDF-FF算法[12]判斷聚合時(shí)，同樣需要查找重疊鏈路，復(fù)雜度與EDF-PA相同.EDF-OPA算法需重新查找數(shù)據(jù)包主動(dòng)聚合等待所在時(shí)隙中其它|F|-1條數(shù)據(jù)流.令可以主動(dòng)等待的數(shù)據(jù)包數(shù)目為Y，其時(shí)間復(fù)雜度為O(P×|F|2×log|F|×C+(|F|-1)×Y).在調(diào)度方法的實(shí)際執(zhí)行過程中，本文提出的算法提高了數(shù)據(jù)的聚合度，因此會(huì)減少網(wǎng)絡(luò)傳輸?shù)逆溌窋?shù)，所以實(shí)際調(diào)度執(zhí)行時(shí)間要比理論計(jì)算值更小.

5 仿真實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)測試平臺(tái)采用的工作站相關(guān)配置為：Intel(R)Xeon(R)W-10855M @2.80GHz 12核處理器，128GB內(nèi)存，基于64位的Win 10系統(tǒng).采用Python軟件的版本為3.7.

網(wǎng)絡(luò)參數(shù)設(shè)置如下：網(wǎng)絡(luò)邊密度取值為σ=0.7.邊密度的設(shè)置參考文獻(xiàn)[20]，δ取值較大保證網(wǎng)絡(luò)中任意兩個(gè)設(shè)備節(jié)點(diǎn)可通過一系列其他節(jié)點(diǎn)相互連通，構(gòu)成各數(shù)據(jù)流的路徑.源節(jié)點(diǎn)和目的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)設(shè)備總數(shù)比值為ε，ε值越大意味著網(wǎng)絡(luò)中源節(jié)點(diǎn)—目的節(jié)點(diǎn)對(duì)的數(shù)目越多.數(shù)據(jù)流數(shù)量越多，網(wǎng)絡(luò)負(fù)載越大，這里網(wǎng)絡(luò)節(jié)點(diǎn)可重復(fù)被選為源節(jié)點(diǎn)或目的節(jié)點(diǎn).本節(jié)仿真設(shè)置比真實(shí)情況更大的網(wǎng)絡(luò)負(fù)載來充分展現(xiàn)算法性能.丟包率l表示數(shù)據(jù)流路徑上的每兩個(gè)相鄰節(jié)點(diǎn)間的通信鏈路都有l(wèi)%的概率傳輸失敗.此外，網(wǎng)絡(luò)設(shè)備數(shù)目為|V|與網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)目存在如下關(guān)系[20]：

(12)

對(duì)同一網(wǎng)絡(luò)配置將隨機(jī)生成200個(gè)數(shù)據(jù)流測試集，計(jì)算每組測試集中滿足截止期數(shù)據(jù)流K占數(shù)據(jù)流N總數(shù)的比例計(jì)算得到當(dāng)前測試集的調(diào)度成功率，故，實(shí)驗(yàn)結(jié)果中每點(diǎn)值可通過計(jì)算200組測試集調(diào)度成功率的平均值得到.通過上述參數(shù)設(shè)定方式，有效保證本文對(duì)算法性能的分析可以合理真實(shí)的反映工業(yè)無線網(wǎng)絡(luò)聚合調(diào)度方法的實(shí)際性能.

5.2 性能評(píng)價(jià)指標(biāo)

選取調(diào)度成功率(Scheduling Success Rate，SSR)與平均執(zhí)行時(shí)間兩種性能指標(biāo)對(duì)本文提出的聚合調(diào)度方法進(jìn)行評(píng)估.調(diào)度成功率指根據(jù)網(wǎng)絡(luò)參數(shù)生成一定數(shù)量的隨機(jī)測試網(wǎng)絡(luò)，所有數(shù)據(jù)流可成功調(diào)度的測試用例數(shù)目K與總測試用例數(shù)目N的比值，比值越大表示算法的調(diào)度能力越強(qiáng).

(13)

平均執(zhí)行時(shí)間(Average Execution Time，AET)通過統(tǒng)計(jì)全部的測試網(wǎng)絡(luò)中調(diào)度成功花費(fèi)的時(shí)間與調(diào)度成功的測試集數(shù)目的比值，比值越小表示算法的時(shí)間開銷越少，執(zhí)行調(diào)度的速度越快.

5.3 實(shí)驗(yàn)結(jié)果分析

本節(jié)仿真實(shí)驗(yàn)從實(shí)際的工業(yè)應(yīng)用出發(fā)，搭建基于工業(yè)無線標(biāo)準(zhǔn)WirelessHART協(xié)議的網(wǎng)絡(luò)模型，并根據(jù)真實(shí)的工業(yè)無線系統(tǒng)采集的數(shù)據(jù)特征設(shè)計(jì)仿真數(shù)據(jù).為清晰反映算法性能，本節(jié)仿真實(shí)驗(yàn)中的網(wǎng)絡(luò)負(fù)載比真實(shí)工業(yè)情況的網(wǎng)絡(luò)負(fù)載更大；并通過觀測符合真實(shí)工況的多個(gè)關(guān)鍵參數(shù)動(dòng)態(tài)變化對(duì)調(diào)度成功率的影響多方面評(píng)估算法性能，驗(yàn)證其合理性與通用性.

圖3 不同網(wǎng)絡(luò)規(guī)模下調(diào)度成功率對(duì)比Fig.3 Comparison of SSR under different network scales

圖4為各算法在不同網(wǎng)絡(luò)規(guī)模下的平均執(zhí)行時(shí)間對(duì)比結(jié)果.參數(shù)配置為ε=0.8，則|F|=|V|×0.4，可用信道數(shù)目m=6，丟包率l=3%.如圖4所示，所有算法的平均執(zhí)行時(shí)間都隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而不斷增加，3種聚合調(diào)度算法的平均執(zhí)行時(shí)間均高于經(jīng)典的EDF調(diào)度方法與LLF調(diào)度方法.因?yàn)镋DF-PA與EDF-FF調(diào)度算法需要耗費(fèi)一定的時(shí)間查找路徑重疊可能聚合的數(shù)據(jù)流，而EDF-OPA在此基礎(chǔ)上需找到可以主動(dòng)聚合等待的數(shù)據(jù)流，所以復(fù)雜度均大于兩種經(jīng)典的動(dòng)態(tài)調(diào)度方法，驗(yàn)證了4.3節(jié)中各算法的時(shí)間復(fù)雜度.由于本文提出的算法離線實(shí)現(xiàn)，可以滿足工業(yè)無線網(wǎng)絡(luò)的實(shí)時(shí)性需求.

圖4 不同網(wǎng)絡(luò)規(guī)模下的平均執(zhí)行時(shí)間對(duì)比Fig.4 Comparison of AET under different network scales

圖5 不同數(shù)據(jù)流數(shù)目下的調(diào)度成功率對(duì)比Fig.5 Comparison of SSR under different numbers of flows

圖5表現(xiàn)了丟包率分別為l=0%與l=1.5%時(shí)不同數(shù)據(jù)流數(shù)下的調(diào)度成功率對(duì)比結(jié)果，其中設(shè)備數(shù)目分別為|V|=50，可用信道數(shù)M=5.如圖5所示，所有算法的調(diào)度成功率都隨著數(shù)據(jù)流數(shù)量的不斷增加而降低，但本文提出算法性能始終最優(yōu).原因是數(shù)據(jù)流數(shù)量增加導(dǎo)致網(wǎng)絡(luò)負(fù)載持續(xù)增大，數(shù)據(jù)流傳輸沖突的情況加重，將傳輸沖突的數(shù)據(jù)流安排在不同時(shí)隙需要耗費(fèi)更多資源，部分?jǐn)?shù)據(jù)流無法在截止時(shí)間前傳輸至目的節(jié)點(diǎn)，所有算法的調(diào)度成功率都呈下降趨勢.但EDF-PA算法可以有效緩解傳輸沖突，提高網(wǎng)絡(luò)調(diào)度成功率；EDF-OPA算法比起EDF-PA算法可以更加充分利用空余信道資源，進(jìn)一步提高網(wǎng)絡(luò)的調(diào)度成功率.圖5(a)和圖5(b)對(duì)比可知，當(dāng)網(wǎng)絡(luò)丟包時(shí)，所有算法的調(diào)度成功率會(huì)下降，但EDF-OPA算法為不可調(diào)度數(shù)據(jù)流安排信道資源，盡量降低丟包對(duì)調(diào)度成功率的影響.

圖6表現(xiàn)了丟包率分別為l=0%與l=2%時(shí)，不同信道數(shù)目下的調(diào)度成功率對(duì)比結(jié)果.參數(shù)配置為ε=1.6，設(shè)備數(shù)目為|V|=70，|F|=|V|×0.8.如圖6所示，在網(wǎng)絡(luò)設(shè)備數(shù)目與數(shù)據(jù)流數(shù)量不變時(shí)，所有算法的調(diào)度成功率都隨著信道數(shù)目的增加而不斷提高，且本文提出的算法性能十分優(yōu)越.這是因?yàn)樾诺蕾Y源增加意味著網(wǎng)絡(luò)中可利用的通信資源更加充足，同時(shí)傳輸?shù)臄?shù)據(jù)流數(shù)目隨之增加，調(diào)度成功率獲得提升.EDF-PA算法的調(diào)度成功率在開始時(shí)增加趨勢較為明顯，但當(dāng)信道數(shù)目增加至一定值時(shí)，其增幅逐漸平緩，原因是雖然可用的信道資源增多，但存在著傳輸沖突無法保證數(shù)據(jù)流能夠使用全部的信道資源；EDF-OPA算法比起EDF-PA算法可以更有效的緩解傳輸沖突，因此即使網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)目較多，在信道資源較為充足時(shí)，調(diào)度成功率幾乎達(dá)100%.由圖6(a)和圖6(b)對(duì)比可知，丟包率增加時(shí)，所有算法的調(diào)度成功率下降.

圖6 不同信道數(shù)目下的調(diào)度成功率對(duì)比Fig.6 Comparison of SSR under different channel numbers

圖7 不同資源利用率下的調(diào)度成功率對(duì)比Fig.7 Comparison of SSR under different resource utilization rates

圖8 不同丟包率下的調(diào)度成功率對(duì)比Fig.8 Comparison of SSR under different packet loss rates

6 總 結(jié)

本文研究了網(wǎng)狀拓?fù)湎碌墓I(yè)無線系統(tǒng)實(shí)時(shí)調(diào)度問題.為減少數(shù)據(jù)流傳輸對(duì)網(wǎng)絡(luò)資源的需求，首先提出了EDF-PA算法.在路徑重疊區(qū)域采用基于優(yōu)先級(jí)排序被動(dòng)聚合等待的方式聚合數(shù)據(jù)包，降低數(shù)據(jù)流間的傳輸沖突，提高系統(tǒng)整體傳輸效率.在此基礎(chǔ)上，為進(jìn)一步提高重疊區(qū)域數(shù)據(jù)包聚合度，提出改進(jìn)算法EDF-OPA采用主動(dòng)聚合等待的方式，以數(shù)據(jù)流可調(diào)度性為約束，最大化特定重疊區(qū)域的數(shù)據(jù)包聚合度，提高信道資源利用率.本文選取調(diào)度成功率與平均執(zhí)行時(shí)間作為評(píng)價(jià)指標(biāo)與傳統(tǒng)的調(diào)度方法和聚合調(diào)度方法對(duì)比分析.仿真結(jié)果表明，本文提出的兩種算法可以有效提高調(diào)度成功率，在網(wǎng)絡(luò)負(fù)載較高但資源有限的情況下，對(duì)比傳統(tǒng)聚合調(diào)度方法調(diào)度成功率可提升35%；在網(wǎng)絡(luò)丟包嚴(yán)重時(shí)，調(diào)度成功率可提升20%.后續(xù)將搭建工業(yè)無線網(wǎng)絡(luò)的硬件測試平臺(tái)，在平臺(tái)中測試算法的性能；并考慮真實(shí)場景中的高溫、電磁干擾等惡劣環(huán)境因素對(duì)網(wǎng)絡(luò)通信狀況的影響，進(jìn)一步優(yōu)化與改進(jìn)本文提出算法的性能.