考慮鏈路重傳的工業(yè)無線網(wǎng)絡(luò)確定性調(diào)度算法

王 恒 劉清華 李 敏 譚 帥

工業(yè)無線網(wǎng)絡(luò)是工業(yè)物聯(lián)網(wǎng)的重要支撐性網(wǎng)絡(luò),具有部署方便、組網(wǎng)靈活、易于維護(hù)等優(yōu)點(diǎn),對網(wǎng)絡(luò)數(shù)據(jù)的傳輸有嚴(yán)格的可靠性和實(shí)時性要求[1?2].現(xiàn)有工業(yè)無線網(wǎng)絡(luò)采用了跳頻、重傳、多路徑等機(jī)制,以保證數(shù)據(jù)能夠可靠的到達(dá)目標(biāo)設(shè)備,避免工業(yè)環(huán)境中各種干擾的影響;同時支持時鐘同步、確定性調(diào)度等技術(shù),使網(wǎng)絡(luò)能夠滿足數(shù)據(jù)收發(fā)的實(shí)時需求,確保數(shù)據(jù)在規(guī)定時間內(nèi)傳輸完成[3?5].此外,工業(yè)無線網(wǎng)絡(luò)通常還使用多信道機(jī)制和時分多址接入(Time division multiple access,TDMA)技術(shù)為網(wǎng)絡(luò)中的數(shù)據(jù)傳輸提供必需的時槽和信道等通信資源[6].

工業(yè)無線網(wǎng)絡(luò)中的確定性調(diào)度技術(shù)通過高效配置時槽與頻點(diǎn)資源,滿足網(wǎng)絡(luò)中每條通信流的截止時間約束,以保證網(wǎng)絡(luò)數(shù)據(jù)的實(shí)時傳輸.由于該問題屬于NP 完全問題[7],通常針對不同的網(wǎng)絡(luò)情況,采用不同的求解策略和目標(biāo)對其進(jìn)行研究.現(xiàn)有的工業(yè)無線網(wǎng)絡(luò)主要包括WirelessHART、WIA-PA、ISA100.11a 等網(wǎng)絡(luò)[8],在上述網(wǎng)絡(luò)中對確定性調(diào)度的研究已取得了一定的成果.圍繞WirelessHART標(biāo)準(zhǔn),在分析調(diào)度所需基本前提的基礎(chǔ)上,文獻(xiàn)[9]基于干擾感知松弛度,提出了C-LLF (Conflictaware least laxity first)調(diào)度算法,通過在當(dāng)前時槽計(jì)算網(wǎng)絡(luò)中所有就緒鏈路的干擾感知松弛度,使松弛度小的鏈路優(yōu)先獲得網(wǎng)絡(luò)資源,取得了較高的調(diào)度成功率.文獻(xiàn)[10]對混合優(yōu)先級情況下的實(shí)時通信進(jìn)行了研究,提出了一種基于固定優(yōu)先級調(diào)度的端到端時延分析方法.文獻(xiàn)[11]提出了一種分布式WirelessHART 實(shí)時調(diào)度方案,通過時間區(qū)間分配機(jī)制,設(shè)備只需執(zhí)行本地調(diào)度策略,無需在網(wǎng)絡(luò)中傳遞全局調(diào)度信息,從而降低了網(wǎng)絡(luò)資源開銷.文獻(xiàn)[12] 給出了一種基于迭代的多跳Wireless-HART 調(diào)度算法,在截止時間限制下能夠最小化端到端傳輸時延.文獻(xiàn)[13]對多個WirelessHART 網(wǎng)絡(luò)共存場景下的調(diào)度問題進(jìn)行了專門研究,利用有效的頻點(diǎn)管理和流調(diào)度策略,實(shí)現(xiàn)了網(wǎng)絡(luò)的相互隔離與數(shù)據(jù)的可靠傳輸.針對WIA-PA網(wǎng)絡(luò)的調(diào)度問題,文獻(xiàn)[14]提出了適用于WIA-PA 網(wǎng)絡(luò)的基于回溯法的最優(yōu)調(diào)度算法和基于最小時間松弛度優(yōu)先的調(diào)度算法,并針對WIA-PA 網(wǎng)絡(luò)分為簇內(nèi)通信和簇間通信不同階段的特點(diǎn)進(jìn)行了優(yōu)化設(shè)計(jì).文獻(xiàn)[15] 基于跳鏈路的思想,提出了一種頻點(diǎn)分配方案,能夠有效利用網(wǎng)絡(luò)中的頻率資源,減少干擾反應(yīng)時間.針對ISA100.11a 網(wǎng)絡(luò)的調(diào)度問題,文獻(xiàn)[16]為滿足實(shí)時性要求,設(shè)計(jì)了容納實(shí)時消息、報警消息和非實(shí)時消息的超幀,并以此提出了基于ISA100.11a 專用時槽的消息調(diào)度方案.除了圍繞典型工業(yè)無線網(wǎng)絡(luò)標(biāo)準(zhǔn)進(jìn)行研究外,還有一些工作針對特定的工業(yè)無線網(wǎng)絡(luò)場景進(jìn)行了調(diào)度算法優(yōu)化設(shè)計(jì).文獻(xiàn)[17]針對擾動存在下的工業(yè)無線網(wǎng)絡(luò)提出了一種分布式調(diào)度架構(gòu),通過非中心化的本地決策,實(shí)現(xiàn)了對擾動的快速調(diào)度響應(yīng).文獻(xiàn)[18]針對時間觸發(fā)通信流與事件觸發(fā)通信流并存的網(wǎng)絡(luò)場景,在分析虛擬周期、時槽復(fù)用等基礎(chǔ)調(diào)度方法的基礎(chǔ)上,提出了一種混合型中心式調(diào)度算法,獲得了接近于最優(yōu)方法的調(diào)度性能.文獻(xiàn)[19]考慮不同網(wǎng)絡(luò)位置擁有不同可用頻點(diǎn)集的場景,提出了面向樹型工業(yè)無線網(wǎng)絡(luò)的啟發(fā)式匯聚調(diào)度算法,實(shí)現(xiàn)了對差異化鏈路可用頻點(diǎn)集的優(yōu)化支持.對于擁有多個射頻收發(fā)單元的工業(yè)無線現(xiàn)場設(shè)備,文獻(xiàn)[20]提出了一種綜合考慮時槽、頻點(diǎn)和射頻接口分配的調(diào)度算法,提高了調(diào)度成功率.文獻(xiàn)[21]針對截止時間隨機(jī)可變的場景,通過分析待調(diào)度系統(tǒng)的狀態(tài)、動作空間、條件轉(zhuǎn)移概率和成本函數(shù),將該場景下的調(diào)度問題轉(zhuǎn)換為不可觀測的馬爾科夫決策問題,并提出了基于平均截止時間優(yōu)先的低復(fù)雜度求解方法.文獻(xiàn)[22]設(shè)計(jì)了一種考慮數(shù)據(jù)到達(dá)率的調(diào)度方法,加快了網(wǎng)絡(luò)響應(yīng)時間.文獻(xiàn)[23]考慮了網(wǎng)絡(luò)中鏈路選取過程與時槽調(diào)度過程之間的前后關(guān)聯(lián)性,提出了一種鏈路與時槽的聯(lián)合優(yōu)化分配方案,改善了網(wǎng)絡(luò)調(diào)度性能.

此外,考慮到工業(yè)無線網(wǎng)絡(luò)是無線傳感器網(wǎng)絡(luò)的行業(yè)應(yīng)用,一些面向通用無線傳感器網(wǎng)絡(luò)所提出的調(diào)度算法,對于工業(yè)無線網(wǎng)絡(luò)確定性調(diào)度問題的研究,仍具有一定的參考價值.文獻(xiàn)[24?26]針對無線傳感器網(wǎng)絡(luò)中的調(diào)度問題,探索采用粒子群算法、模擬退火算法、遺傳算法等方法進(jìn)行解決.文獻(xiàn)[27]利用機(jī)器學(xué)習(xí)技術(shù),提出了一種基于優(yōu)先級感知的數(shù)據(jù)交換調(diào)度算法,改善了無線傳感器網(wǎng)絡(luò)的平均時延性能.

工業(yè)現(xiàn)場環(huán)境復(fù)雜、干擾眾多,使得工業(yè)無線網(wǎng)絡(luò)中的數(shù)據(jù)傳輸經(jīng)常發(fā)生丟包現(xiàn)象.丟包會導(dǎo)致數(shù)據(jù)傳輸失敗,影響網(wǎng)絡(luò)正常的調(diào)度運(yùn)行.對抗丟包問題的典型方法包括自動重傳請求(Automatic repeat-request,ARQ)、冗余多路徑等.重傳是一種簡單有效的機(jī)制,在三種主要的工業(yè)無線網(wǎng)絡(luò)標(biāo)準(zhǔn)中都得到了支持,它通過為傳輸鏈路分配額外的時槽、頻點(diǎn)資源,在傳輸失敗時利用這些通信資源重新發(fā)送數(shù)據(jù),避免網(wǎng)絡(luò)丟包的影響,提升數(shù)據(jù)通信的可靠性.

圍繞工業(yè)無線網(wǎng)絡(luò)調(diào)度中的丟包與重傳問題,文獻(xiàn)[6]、[9]在仿真實(shí)驗(yàn)中考慮了網(wǎng)絡(luò)丟包,發(fā)現(xiàn)丟包的存在顯著降低了調(diào)度成功率.文獻(xiàn)[28?29]在工業(yè)場景中將ARQ 與節(jié)點(diǎn)間的中繼協(xié)作聯(lián)合使用,進(jìn)一步降低了系統(tǒng)丟包率;文獻(xiàn)[30?31]在工業(yè)網(wǎng)絡(luò)路由策略中引入了重傳操作,提高了路由方法的可靠性,但文獻(xiàn)[28?31]均未將重傳機(jī)制與確定性調(diào)度深入結(jié)合.文獻(xiàn)[32]考慮了ARQ 機(jī)制對調(diào)度的影響,但只局限在單跳網(wǎng)絡(luò)內(nèi),沒有解決更重要的多跳網(wǎng)絡(luò)重傳調(diào)度問題.針對以上問題,本文面向使用多信道和TDMA 機(jī)制的多跳工業(yè)無線網(wǎng)絡(luò),結(jié)合通信流的截止時間條件,建立了支持鏈路重傳機(jī)制的調(diào)度網(wǎng)絡(luò)模型;在分析可調(diào)度條件和優(yōu)先處理?xiàng)l件的基礎(chǔ)上,分別針對數(shù)據(jù)包傳輸失敗后立即進(jìn)行持續(xù)重傳的場景和在一定時間區(qū)間內(nèi)完成重傳的場景,提出了相應(yīng)的時槽、頻點(diǎn)調(diào)度算法,在滿足傳輸確定性的前提下,有效提升了網(wǎng)絡(luò)可靠性.

1 模型建立

考慮一個基于時槽方式運(yùn)行的多信道工業(yè)無線網(wǎng)絡(luò)G=(V,ξ) ,V表示網(wǎng)絡(luò)中所有設(shè)備,ξ表示設(shè)備之間的通信鏈接,可用信道頻點(diǎn)數(shù)為K.網(wǎng)絡(luò)中存在J條通信流F1,F2,···,FJ,每條通信流通過由多條通信鏈接構(gòu)成的傳輸路徑,將數(shù)據(jù)包從起始設(shè)備發(fā)往最終設(shè)備,如圖1 所示.對于任意一條通信流Fm,其數(shù)據(jù)包產(chǎn)生周期為Pm,傳輸路徑包含的通信鏈接數(shù)為φm,數(shù)據(jù)包產(chǎn)生后需要在給定的截止時間Dm內(nèi)到達(dá)最終設(shè)備.設(shè)網(wǎng)絡(luò)中每條通信鏈接的重傳次數(shù)為λ,則需滿足:φm(λ+1)≤Dm ≤Pm.

圖1 網(wǎng)絡(luò)模型圖Fig.1 Network model

本文確定性調(diào)度的任務(wù)是在考慮重傳條件下,通過安排每個時槽各個頻點(diǎn)上的通信鏈接,使每條數(shù)據(jù)流所產(chǎn)生的數(shù)據(jù)包均能在指定時限內(nèi)確定到達(dá)最終設(shè)備.設(shè)所有通信流周期的最小公倍數(shù)為T,稱之為宏周期.若在當(dāng)前宏周期T內(nèi),采用某種調(diào)度策略,能夠使每條通信流的各個數(shù)據(jù)包均能按時到達(dá),則在下一個宏周期T內(nèi),重復(fù)執(zhí)行該調(diào)度策略,就能夠繼續(xù)保證數(shù)據(jù)流的確定性傳輸.因此,調(diào)度任務(wù)可轉(zhuǎn)化為研究和設(shè)計(jì)一個宏周期T內(nèi)的調(diào)度策略.顯然,在宏周期T內(nèi),數(shù)據(jù)流Fm將 發(fā)送T/Pm個數(shù)據(jù)包,其中第n個數(shù)據(jù)包在Am,n=(n ?1)Pm+1時刻從起始設(shè)備產(chǎn)生,需在截止時刻Bm,n=(n ?1)Pm+Dm之前到達(dá)最終設(shè)備.

在對工業(yè)無線網(wǎng)絡(luò)中每個時槽的通信鏈接進(jìn)行調(diào)度配置時,主要面臨兩個方面的制約.一是頻點(diǎn)數(shù)制約,在同一時槽同一頻點(diǎn)只能放置一個通信鏈接,不同頻點(diǎn)可放置不同通信鏈接,但在同一時槽能夠同時工作的通信鏈接數(shù)不能超過系統(tǒng)所提供的頻點(diǎn)數(shù);二是通信鏈接收發(fā)制約,在ISA100.11a、WirelessHART、WIA-PA 等主流工業(yè)無線網(wǎng)絡(luò)中,設(shè)備通常使用單根天線,采用半雙工方式工作,無法同時完成射頻的發(fā)送和接收,這使得若在當(dāng)前時槽的某個頻點(diǎn)安排了一個通信鏈接,則以該通信鏈接發(fā)送方進(jìn)行發(fā)送或接收,以及該鏈接接收方進(jìn)行發(fā)送或接收的所有通信鏈接,與該通信鏈接均構(gòu)成干擾鏈接,都不能再在當(dāng)前時槽進(jìn)行安排.下面將在考慮上述兩種制約條件的基礎(chǔ)上,對重傳場景下的調(diào)度問題進(jìn)行描述.令 Γg(p,q)∈{0,1}表示在時槽g,設(shè)備p與設(shè)備q之間所建立的通信鏈接的狀態(tài).當(dāng)p與q之間的通信鏈接被安排在時槽g進(jìn)行數(shù)據(jù)收發(fā),即該通信鏈接處于活躍狀態(tài)時,Γg(p,q)=1 ;反之,Γg(p,q)=0 .此外,定義 Hg(p) 表示在時槽g所有以設(shè)備p作為發(fā)送方的通信鏈接集合,Θg(p)表示在時槽g所有以設(shè)備p作為接收方的通信鏈接集合.以Lm,n表示通信流Fm的第n個數(shù)據(jù)包在不考慮重傳時槽配置情況下所經(jīng)歷的傳輸時延,則本文所研究的調(diào)度問題具體描述如下:

式(1)采用不等式的形式進(jìn)行描述,表明在考慮重傳時槽及其配置的場景下,所有通信流的數(shù)據(jù)包傳輸時間均應(yīng)小于或等于其各自的截止時間;式(1a)對應(yīng)頻點(diǎn)數(shù)制約條件,式(1b)和式(1c)則對應(yīng)通信鏈接收發(fā)制約條件.

2 調(diào)度優(yōu)先級分析

確定性調(diào)度策略所操作的基本單元是通信鏈接.下面將在干擾感知松弛度理論的基礎(chǔ)上[9],進(jìn)一步考慮重傳因素影響,對重傳場景下通信鏈接的屬性及其調(diào)度優(yōu)先級進(jìn)行擴(kuò)展分析.

在宏周期T內(nèi),對于數(shù)據(jù)流Fm,其第n個數(shù)據(jù)包從產(chǎn)生時刻開始,將沿著對應(yīng)路徑經(jīng)過一步步的轉(zhuǎn)發(fā)傳輸至最終設(shè)備.這條傳輸路徑由一系列相鄰的通信鏈接組成,設(shè)μi=(p,q) 是其中一個通信鏈接,該通信鏈接的發(fā)送方是設(shè)備p,接收方是設(shè)備q.假設(shè)設(shè)備q與最終設(shè)備之間相隔的跳數(shù)為χi,在時槽g處數(shù)據(jù)包還需要傳遞oi個通信鏈接后才能到達(dá)設(shè)備p,則通信鏈接μi的有效調(diào)度區(qū)間為:

其中,si是通信鏈接μi的就緒時間,

wi是通信鏈接μi的截止時間,

通信鏈接μi需要在上述時間范圍內(nèi)完成傳輸,如圖2 所示,否則將導(dǎo)致調(diào)度失敗.

圖2 通信鏈接 μi 的有效調(diào)度區(qū)間Fig.2 Effective scheduling interval of communication link μi

在時槽g處,若某個通信鏈接的所有前序通信鏈接都已執(zhí)行,同時用于重傳的通信鏈接也配置完成,則稱該鏈接為就緒通信鏈接.所有就緒通信鏈接構(gòu)成的集合稱為就緒鏈接集.在重傳場景下,對于某個就緒通信鏈接,除了需在其有效調(diào)度區(qū)間內(nèi)安排傳輸外,還需在其傳輸之后安排λ次重傳,這些重傳動作所對應(yīng)的通信鏈接稱為重傳通信鏈接.

本文在調(diào)度安排就緒通信鏈接和重傳通信鏈接時,采用干擾感知松弛度作為鏈接排序的基本依據(jù),在此基礎(chǔ)上,進(jìn)一步考慮不同重傳類型及其特點(diǎn),形成包括重傳通信鏈路在內(nèi)的各種鏈路的優(yōu)先級.干擾感知松弛度由文獻(xiàn)[9]提出,反映了通信鏈接調(diào)度的緊急程度.它既考慮了通信鏈接有效調(diào)度區(qū)間的長度影響,又考慮了潛在干擾通信鏈接數(shù)量的影響.該指標(biāo)值越小,表征通信鏈接調(diào)度的急迫性越高.設(shè)在時槽g處,μi=(p,q) 是一個就緒通信鏈接,則其干擾感知松弛度表示為:

其中,Cp是由時槽g就緒通信鏈接集中,以設(shè)備p作為發(fā)送方,且有效調(diào)度區(qū)間與μi存在重合的通信鏈接的截止時間所構(gòu)成的集合.εp是在時間區(qū)間[g,θ] 內(nèi)設(shè)備p所參與的通信鏈接數(shù)量.

對于重傳鏈接,干擾感知松弛度的計(jì)算方法需要進(jìn)行擴(kuò)展,尤其是區(qū)間重傳方式.由于該方式下重傳鏈接需在指定的時間區(qū)間內(nèi)完成,故在計(jì)算松弛度時,所使用的有效調(diào)度區(qū)間上限還不得超過重傳區(qū)間上限.兩種重傳方式的具體分類說明,將在下一節(jié)中進(jìn)行描述.

3 確定性調(diào)度算法設(shè)計(jì)

面向工廠自動化應(yīng)用所設(shè)計(jì)的無線網(wǎng)絡(luò),為了防止丟包,在點(diǎn)到點(diǎn)傳輸時普遍采用了確認(rèn)幀(ACK)機(jī)制.發(fā)送方發(fā)送數(shù)據(jù)包后,將啟動一個定時器.接收方正確接收到數(shù)據(jù)包后,將立即返回一個確認(rèn)幀.若發(fā)送方在預(yù)定的定時間隔內(nèi)收到確認(rèn)幀,則視為數(shù)據(jù)包傳輸成功.當(dāng)網(wǎng)絡(luò)發(fā)生丟包,接收方?jīng)]有收到數(shù)據(jù)包,或由于無線信道質(zhì)量變差,接收方無法正確解碼數(shù)據(jù)包時,接收方將不會反饋確認(rèn)幀.發(fā)送方在定時器超時后若仍未收到確認(rèn)幀,則認(rèn)為傳輸失敗,進(jìn)而啟動重傳工作.在ISA100.11a 等工業(yè)無線網(wǎng)絡(luò)中,還設(shè)計(jì)了否決幀(NACK)機(jī)制.當(dāng)接收方發(fā)現(xiàn)接收的數(shù)據(jù)包錯誤時將反饋否決幀,此時發(fā)送方無需等待定時器超時即可進(jìn)行重傳.

在基于時槽機(jī)制運(yùn)行的無線網(wǎng)絡(luò)中,根據(jù)重傳時機(jī)的不同,存在兩類重傳方式.第一類是持續(xù)重傳.若當(dāng)前時槽通信鏈接傳輸不成功,則在接下來的時槽中持續(xù)進(jìn)行重新傳輸,直至傳輸成功或達(dá)到最大重傳次數(shù).第二類是區(qū)間重傳.若當(dāng)前時槽傳輸不成功,則在接下來的一段時槽區(qū)間內(nèi)根據(jù)情況可以間斷性的完成重傳.持續(xù)重傳具有實(shí)現(xiàn)簡便的優(yōu)點(diǎn),而區(qū)間重傳則具備更好的擴(kuò)展性.無論采用何種重傳方式,系統(tǒng)都需要為重傳的實(shí)施調(diào)度安排相應(yīng)的時槽、頻點(diǎn)資源.下面將圍繞不同的重傳方式,提出對應(yīng)的網(wǎng)絡(luò)調(diào)度方案.

3.1 支持持續(xù)重傳的調(diào)度方法

從持續(xù)重傳的特點(diǎn)出發(fā),系統(tǒng)在調(diào)度完一個就緒通信鏈接后,將在接下來的相鄰時槽,立即且持續(xù)安排該就緒鏈接所對應(yīng)的重傳通信鏈接.結(jié)合干擾感知松弛度,本文設(shè)計(jì)了支持持續(xù)重傳的確定性調(diào)度(Definiteness schedule with consequent retries,DS-CR)方法.

該算法以時槽為單位逐時槽進(jìn)行調(diào)度.在每個時槽,待調(diào)度對象包括該時槽的就緒通信鏈接和重傳通信鏈接.由于在持續(xù)重傳方式下,對重傳通信鏈接安排的緊急程度很高,故采用先調(diào)度重傳通信鏈接,再調(diào)度就緒通信鏈接的方法,即重傳通信鏈接的優(yōu)先級總是高于就緒通信鏈接.在對重傳鏈接進(jìn)行調(diào)度時,需記錄并處理數(shù)據(jù)包的重傳輪數(shù).重傳鏈接調(diào)度完成后,以干擾感知松弛度指標(biāo)值為依據(jù),由小到大依次安排就緒鏈接的頻點(diǎn).該指標(biāo)值相等時,則比較截止時間,進(jìn)一步則繼續(xù)比較通信流編號,數(shù)值小者優(yōu)先安排.當(dāng)一個通信鏈接被調(diào)度后,與該鏈接構(gòu)成干擾的通信鏈接均不再在當(dāng)前時槽進(jìn)行配置.每個時槽采用同樣的方式執(zhí)行以上調(diào)度過程,直到每個通信鏈接及重傳鏈接均調(diào)度完成或任一鏈接無法滿足截止時間要求.算法1 描述了該方法的主要運(yùn)行過程.

從無線傳輸?shù)慕嵌瓤?重傳是一種時間分集機(jī)制.在系統(tǒng)擁有多個頻點(diǎn)的條件下,還可在重新傳輸時進(jìn)一步聯(lián)合使用頻率分集機(jī)制,能夠獲得更高的可靠性.DS-CR 算法在安排頻點(diǎn)時,還可對同一通信鏈接的就緒鏈接和多個重傳鏈接盡可能分配不同的頻點(diǎn).這樣,當(dāng)數(shù)據(jù)包在當(dāng)前時槽某個頻點(diǎn)傳輸失敗后,下一個時槽將在不同的頻點(diǎn)重新被傳輸,避免在受到干擾或質(zhì)量變差的單一信道上重發(fā)數(shù)據(jù)包.

就緒通信鏈接的頻點(diǎn)確定規(guī)則可根據(jù)調(diào)度次序,按頻點(diǎn)編號從小到大依次設(shè)定.重傳通信鏈接的頻點(diǎn)則可在前序就緒鏈接或重傳鏈接頻點(diǎn)編號的基礎(chǔ)上,采用循環(huán)增加的方式設(shè)定.當(dāng)重傳輪數(shù)超過系統(tǒng)可用頻點(diǎn)數(shù)量時,至少確保相鄰兩次重傳鏈接采用相異的工作頻點(diǎn).

算法1.支持持續(xù)重傳的調(diào)度方法

3.2 支持區(qū)間重傳的調(diào)度方法

根據(jù)區(qū)間重傳的特征,系統(tǒng)在配置完一個就緒通信鏈接后,將在之后的一段時槽區(qū)間內(nèi),對該就緒鏈接所對應(yīng)的重傳通信鏈接進(jìn)行配置.重傳通信鏈接的分布可以是間斷性的,但需在給定區(qū)間內(nèi)全部安排完成.結(jié)合就緒鏈接和重傳鏈接的干擾感知松弛度,本文設(shè)計(jì)了支持區(qū)間重傳的確定性調(diào)度(Definiteness schedule with interval-working retries,DS-IWR)方法.

該方法仍采用逐時槽計(jì)算的方式進(jìn)行調(diào)度.與DS-CR 方法不同的是,在每個時槽的調(diào)度過程中,系統(tǒng)既計(jì)算就緒通信鏈接的干擾感知松弛度,也計(jì)算重傳通信鏈接的干擾感知松弛度,然后將計(jì)算結(jié)果一并由小到大進(jìn)行排序,按次序進(jìn)行調(diào)度.就緒通信鏈接的松弛度采用式(5)進(jìn)行計(jì)算,重傳通信鏈接的松弛度在此基礎(chǔ)上,還需額外引入重傳區(qū)間對有效調(diào)度區(qū)間的限制.算法2 描述了該方法的主要運(yùn)行過程.

算法2.支持區(qū)間重傳的調(diào)度方法

DS-IWR 算法同樣可進(jìn)一步結(jié)合頻率分集機(jī)制,使數(shù)據(jù)包的每一次重傳盡可能分布在不同的頻點(diǎn)上.其中,就緒通信鏈接的頻點(diǎn)確定規(guī)則與DS-CR方法相同,重傳通信鏈接可采用同鏈接循環(huán)增加的方式,資源不足時至少確保相鄰兩次鏈接的工作頻點(diǎn)不同.當(dāng)不同通信鏈接所對應(yīng)的重傳鏈接頻點(diǎn)值沖突時,則先匹配干擾感知松弛度高的鏈路的頻點(diǎn)設(shè)定需求,松弛度低的重傳鏈路越過沖突值進(jìn)行循環(huán)相加,必要時采用相鄰鏈接頻點(diǎn)值相異的方法重新確定頻點(diǎn).

3.3 算法時間復(fù)雜度分析

本文提出的調(diào)度算法在運(yùn)行過程中,需要在每個時槽對就緒通信鏈接的干擾感知松弛度進(jìn)行計(jì)算.設(shè)系統(tǒng)中就緒通信鏈接數(shù)量的最大值為X,通信流跳數(shù)最大值為Y,根據(jù)干擾感知松弛度計(jì)算方法,DS-CR 方法的時間復(fù)雜度是 O (T ·Y ·X2) .與DS-CR 方法不同,DS-IWR 方法除了計(jì)算就緒通信鏈接的松弛度外,還同等計(jì)算重傳通信鏈接的干擾感知松弛度,故其時間復(fù)雜度為 O (T ·Y ·X2·(λ+1)) .在接下來的第4 節(jié)中,將對所提兩種算法的運(yùn)行時間進(jìn)行仿真驗(yàn)證,并與其他算法進(jìn)行對比分析.

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

本節(jié)對所提出的DS-CR 和DS-IWR 兩種調(diào)度算法進(jìn)行仿真驗(yàn)證與對比分析.對比算法為四種經(jīng)典實(shí)時調(diào)度方法和C-LLF 調(diào)度方法[9,33].表1 中列出了用于仿真比較的各種方法的基本原理.同時,為了更好地評價調(diào)度算法在測試過程中的性能,本節(jié)選擇調(diào)度成功率和算法平均計(jì)算時間作為評價指標(biāo).調(diào)度成功率的計(jì)算方法如下:假設(shè)生成W個測試網(wǎng)絡(luò),依次執(zhí)行某調(diào)度算法,若能夠成功完成該網(wǎng)絡(luò)中所有數(shù)據(jù)流調(diào)度的測試網(wǎng)絡(luò)個數(shù)為C,則該算法在本次測試中的調(diào)度成功率為C/W.

表1 用于仿真比較的各個方法的原理Table 1 Principle of each method in simulation comparison

在Intel G4650 處理器、Win10 系統(tǒng)上對上述調(diào)度算法進(jìn)行仿真實(shí)現(xiàn).仿真區(qū)域長度和寬度均為一百米.在該區(qū)域內(nèi)采用類似文獻(xiàn)[9]的方式以隨機(jī)形式構(gòu)建網(wǎng)絡(luò).每種測試場景隨機(jī)構(gòu)建一萬個網(wǎng)絡(luò),通過所提方法和對比方法對網(wǎng)絡(luò)進(jìn)行調(diào)度,獲得相應(yīng)的評價指標(biāo)結(jié)果.在仿真中,d是設(shè)備數(shù)量,β ∈(0,1]是起始設(shè)備與最終設(shè)備所構(gòu)成的通信對比重,?∈(0,1] 是邊密度,K是可用頻點(diǎn)數(shù)量,λ是重傳輪數(shù),η是重傳區(qū)間,α是丟包率,通信流數(shù)量采用β×d/2設(shè)定,邊數(shù)量采用 (d×(d ?1)×?)/2 設(shè)定.每條通信流的起始設(shè)備按設(shè)定的時間間隔周期性的產(chǎn)生數(shù)據(jù)包.不同通信流的數(shù)據(jù)包產(chǎn)生周期在P′=2x～y范圍內(nèi)以均勻分布(四舍五入取整)的方式隨機(jī)構(gòu)造,通過υ∈(0,1] 設(shè)置通信流截止時間取值上限所占比重.

4.1 調(diào)度算法基本性能與計(jì)算時間測試

對調(diào)度算法在不同設(shè)備數(shù)量下的基本性能進(jìn)行測試.在丟包率為百分之三的情況下,設(shè)備數(shù)量從10 開始,依次遞增10,直至60.頻點(diǎn)數(shù)量為8,重新傳輸輪數(shù)為3,重新傳輸時間區(qū)間為6 個時槽,其余參數(shù)設(shè)定為:?=0.8 ,P′=27～9,υ=0.75,β=0.6 .

調(diào)度成功率與設(shè)備數(shù)量之間的關(guān)系如圖3 所示.該圖表明,設(shè)備數(shù)量增加,會引起各個算法成功率的降低,但DS-CR 算法和DS-IWR 算法通過在調(diào)度過程中對重傳進(jìn)行優(yōu)化,緩解了數(shù)據(jù)丟包對調(diào)度的影響,在不同的設(shè)備數(shù)量下調(diào)度成功率都顯著優(yōu)于對比算法;同時,DS-IWR 算法比DS-CR 算法具有更好的調(diào)度效果,這是由于相比于持續(xù)重傳,區(qū)間重傳能夠在一個區(qū)間范圍內(nèi)靈活處理調(diào)度資源,從而進(jìn)一步提高了調(diào)度成功率.

圖3 調(diào)度成功率與設(shè)備數(shù)量關(guān)系圖Fig.3 Relationship between schedulable ratio and device number

表2 列出了各個算法在不同設(shè)備數(shù)量和通信流個數(shù)下的平均計(jì)算時間.表中數(shù)據(jù)表明,當(dāng)設(shè)備數(shù)量達(dá)到20、通信流條數(shù)達(dá)到6 及其以上時,參與對比的五種算法的平均計(jì)算時間低于所提算法.由于所提算法在運(yùn)行過程中,增加了對重新傳輸鏈路的調(diào)度,故花費(fèi)了更多的計(jì)算時間.對于本文所提出的兩種調(diào)度算法,表2 表明DS-CR 算法的平均計(jì)算時間小于DS-IWR 算法,從而驗(yàn)證了第3 節(jié)中對兩種算法時間復(fù)雜度的理論分析,因?yàn)镈S-CR 算法的時間復(fù)雜度 O (T ·Y ·X2) 低于DS-IWR 算法的時間復(fù)雜度 O (T ·Y ·X2·(λ+1)) .需要說明的是,雖然為了提升可靠性,所提算法以花費(fèi)相對較多的時間開銷作為代價,但在設(shè)備數(shù)量和通信流條數(shù)都比較大的情況下,所提兩種算法的計(jì)算時間仍未超過300 ms,所需計(jì)算時間保持在一個相對較小的水平.

表2 各個調(diào)度方法的平均計(jì)算時間 (ms)Table 2 Average execution time of each scheduling method (ms)

綜上所述,本文提出的調(diào)度算法相比對比算法能夠取得更高的調(diào)度成功率,在滿足網(wǎng)絡(luò)數(shù)據(jù)傳輸確定性的同時,保證了丟包情況下的數(shù)據(jù)傳輸可靠性,但需要更多的時間開銷.因此,在進(jìn)行網(wǎng)絡(luò)設(shè)計(jì)時,可根據(jù)不同場景的特點(diǎn),綜合權(quán)衡調(diào)度成功率和花費(fèi)時間的重要性來進(jìn)行算法選擇.當(dāng)網(wǎng)絡(luò)設(shè)備數(shù)較少、頻點(diǎn)質(zhì)量較好時,若網(wǎng)絡(luò)拓?fù)渥兓瘎×覍?dǎo)致調(diào)度算法需頻繁執(zhí)行,且對獲取調(diào)度結(jié)果的時間要求限制在百毫秒以下,可考慮采用經(jīng)典的調(diào)度算法.此時,較小的設(shè)備數(shù)和良好的頻點(diǎn)質(zhì)量能夠適當(dāng)減緩經(jīng)典算法調(diào)度成功率低的影響.若網(wǎng)絡(luò)能夠接受百毫秒級的調(diào)度運(yùn)行時間,本文所提出的算法則是優(yōu)選,尤其在網(wǎng)絡(luò)設(shè)備數(shù)較多或受丟包影響較明顯的場景下,所提算法能夠發(fā)揮更大的調(diào)度成功率優(yōu)勢.

4.2 調(diào)度算法在不同網(wǎng)絡(luò)參數(shù)下的性能測試

本節(jié)進(jìn)一步對調(diào)度算法在不同的重傳區(qū)間、丟包率、信道質(zhì)量、通信對所占比例、截止時間上限比例、周期取值范圍、頻點(diǎn)數(shù)下的性能進(jìn)行仿真對比.由于DS-IWR 算法采用了區(qū)間內(nèi)重傳的方式,區(qū)間的取值會影響其性能,故仿真觀察了該算法在不同重傳區(qū)間下的調(diào)度結(jié)果,如圖4 所示.仿真中設(shè)置η從3 個時槽開始,依次遞增1 個單位時槽長度,直至12 個時槽,其余參數(shù)情況為:d=40,K=8,P′=27～9,α=3 %,β=0.6,λ=3,?=0.8 ,υ=0.75 .

從圖4 可以看出,當(dāng)重傳區(qū)間小于6 個單位長度時,DS-IWR 算法的調(diào)度成功率隨著重傳區(qū)間長度增加而提高;當(dāng)重傳區(qū)間大于6 個單位長度時,算法的調(diào)度成功率反而出現(xiàn)下降的趨勢,且長度增加的越大,下降的幅度越明顯.這種現(xiàn)象出現(xiàn)的原因在于,當(dāng)區(qū)間在一定范圍內(nèi)增大時,傳輸失敗的數(shù)據(jù)報文有機(jī)會在更寬的時間段內(nèi)進(jìn)行重傳選擇,避免了部分報文因重傳時間段窄、優(yōu)先級低導(dǎo)致的無法及時重傳問題,提高了調(diào)度成功率.但當(dāng)區(qū)間增加到一定程度后,若再繼續(xù)增加則會產(chǎn)生兩個方面的問題:一是對于需要重傳的報文本身,有可能選擇大時間段的靠后時槽實(shí)施重傳,這樣雖然當(dāng)前鏈路能夠傳輸成功,但由于花費(fèi)時間過多,會導(dǎo)致剩余跳數(shù)的鏈路可調(diào)度時間余量變小,增加報文調(diào)度失敗的概率;二是當(dāng)多個數(shù)據(jù)報文的重傳區(qū)間設(shè)置過大時,會導(dǎo)致正常報文與重傳報文的沖突加劇,反而降低成功率.因此,重傳區(qū)間的設(shè)置并非越大越好.根據(jù)圖4 中成功率最高點(diǎn)所對應(yīng)的區(qū)間取值,在本節(jié)后續(xù)仿真實(shí)驗(yàn)中,采用λ=3,η=6 的網(wǎng)絡(luò)參數(shù)設(shè)置.

圖4 調(diào)度成功率與重傳區(qū)間關(guān)系圖Fig.4 Relationship between schedulable ratio and retransmission interval

圖5 是所提算法與對比算法在不同鏈路丟包率下的測試結(jié)果.仿真中設(shè)置α從 0 開始,依次遞增5 %,直至50 %.其余參數(shù)情況為:d=30,K=8,P′=27～9,η=6,β=0.6,λ=3,?=0.8,υ=0.75 .圖5 表明,各種算法的調(diào)度成功率隨著丟包程度的加劇呈現(xiàn)下降趨勢,但所提出的兩種調(diào)度算法在鏈路丟包率增加時的性能明顯優(yōu)于對比算法,原因在于當(dāng)數(shù)據(jù)傳輸失敗時,所提算法可以通過重傳鏈路進(jìn)行數(shù)據(jù)的重新發(fā)送,從而在一定范圍內(nèi)能夠較好地緩解數(shù)據(jù)的丟包問題.

圖5 調(diào)度成功率與丟包率關(guān)系圖Fig.5 Relationship between schedulable ratio and packet loss rate

在工廠中部署的工業(yè)無線網(wǎng)絡(luò),往往所處環(huán)境惡劣,電磁情況復(fù)雜,從而對無線頻點(diǎn)的傳輸特性產(chǎn)生重要影響.根據(jù)文獻(xiàn)[34]對工業(yè)無線網(wǎng)絡(luò)頻率特性實(shí)驗(yàn)測試與建模的調(diào)研,Nakagami-m 分布是其中一種主要的信道衰落類型.因此,本文采用Nakagami-m 信道模型,對調(diào)度算法在不同信道質(zhì)量下的性能進(jìn)行仿真.Nakagami-m 模型的概率密度函數(shù)為:,其中pm為形狀參數(shù),ps為尺度參數(shù),Γ (·) 表示Gamma函數(shù).仿真主要關(guān)注由信道質(zhì)量改變所引起的通信中斷對調(diào)度性能的影響.在仿真中設(shè)定網(wǎng)絡(luò)的頻譜效率為1 b/s/Hz,各設(shè)備的平均信噪比為5 dB,其余參數(shù)設(shè)置為:d=10,K=8,P′=27～9,η=6,β=0.6,λ=3,?=0.8,υ=0.75.由于 N a kagami-m 信道的平均質(zhì)量由pm和ps決定,故對(pm,ps) 分別取值 ( 3,1) ,( 3,0.5) 和 ( 1,0.5),在信道平均質(zhì)量逐漸變差的條件下對所提算法和對比算法進(jìn)行性能測試,結(jié)果如圖6 所示.從圖中可以看出,所提出的兩種算法在不同信道質(zhì)量下的調(diào)度性能均優(yōu)于對比算法,且在信道質(zhì)量惡化的情況下,性能下降程度小于對比算法,表明所提算法對工業(yè)通信環(huán)境具有良好的適應(yīng)性.

圖6 調(diào)度成功率與信道質(zhì)量關(guān)系圖Fig.6 Relationship between schedulable ratio and channel quality

針對起始設(shè)備與最終設(shè)備所構(gòu)成的通信對,其所占比重對調(diào)度成功率的影響如圖7 所示.通信對比重從20 %開始,依次遞增10 %,直至100 %,其余參數(shù)情況為:d=30,K=8,P′=27～9,η=6,α= 3 %,λ=3,?=0.8,υ=0.75.從圖7 中可以看出,所提方法在同等條件下的性能超過了其他方法.隨著通信對所占比重增加,會導(dǎo)致通信沖突加大,從而引起調(diào)度成功率降低.

圖7 調(diào)度成功率與起始設(shè)備和最終設(shè)備所構(gòu)成的通信對所占比重關(guān)系圖Fig.7 Relationship between schedulable ratio and proportion of communication pairs from source devices to final destination devices

截止時間取值上限比重與成功率之間的關(guān)系如圖8 所示.上限比重從5 %開始,依次遞增10 %,直至100 %.其余參數(shù)情況為:d=30,k=8,P′=27～9,η=6,α= 3 %,β=0.6,λ=3,?=0.8.該圖表明,在截止時間取值上限比重增加的情況下,由于其他算法缺乏丟包應(yīng)對機(jī)制,受制于網(wǎng)絡(luò)丟包影響,無法有效地改善調(diào)度效果,調(diào)度成功率維持在一個相對變化較小的范圍;而與之相對比的是,所提兩種算法的調(diào)度成功率均得到了顯著改善.

圖8 調(diào)度成功率與截止時間取值上限比重關(guān)系圖Fig.8 Relationship between schedulable ratio and proportion of maximal deadline

圖9 是兩種調(diào)度算法與對比算法在不同周期取值范圍下的調(diào)度成功率.其中,P′取三組值,分別為 28～9,27～10,和 26～11,其余參數(shù)情況為:d=30,K=8,η=6,α= 3 %,β=0.6,λ=3,?=0.8,υ=0.75.從圖9 中可以觀察到,所提算法的調(diào)度性能優(yōu)于對比算法,且周期范圍為 28～9時調(diào)度成功率最高.該項(xiàng)仿真表明,確定合理的周期取值區(qū)間,有利于改進(jìn)所提算法的調(diào)度性能.

圖9 調(diào)度成功率與周期范圍關(guān)系圖Fig.9 Relationship between schedulable ratio and period range

調(diào)度成功率與可用頻點(diǎn)數(shù)量之前的關(guān)系如圖10所示.頻點(diǎn)數(shù)從2 開始,連續(xù)增加到8,其余參數(shù)情況為:d=40,P′=27～9,η=6,α= 3 %,β=0.6,λ=3,?=0.8,υ=0.75.圖10 表明所提調(diào)度算法的調(diào)度成功率在頻點(diǎn)數(shù)量變化的情況下高于對比算法.從該圖中還可以看出,由于對比算法未考慮調(diào)度重傳,在固定的周期范圍內(nèi),每次調(diào)度過程都受到丟包的影響,頻點(diǎn)的增加并未達(dá)到有效提高調(diào)度成功率的效果.而所提算法的成功率在可用頻點(diǎn)數(shù)量從2 增長到4 時變大,后續(xù)再增加頻點(diǎn)數(shù)則基本保持不變.這種現(xiàn)象出現(xiàn)的原因在于,增加頻點(diǎn)數(shù)量,能夠提高調(diào)度容量;但當(dāng)頻點(diǎn)資源供應(yīng)充足時,鏈路傳輸沖突則成為制約調(diào)度能力的主要因素,從而影響調(diào)度成功率的進(jìn)一步提高.

圖10 調(diào)度成功率與頻點(diǎn)個數(shù)關(guān)系圖Fig.10 Relationship between schedulable ratio and channel number

根據(jù)以上在不同網(wǎng)絡(luò)參數(shù)下的調(diào)度算法性能測試結(jié)果可知,隨著網(wǎng)絡(luò)參數(shù)的改變,調(diào)度算法的性能也會隨之發(fā)生變化.因此,在使用調(diào)度算法時需要根據(jù)具體情況盡可能合理地選擇網(wǎng)絡(luò)參數(shù),提高調(diào)度算法成功率.具體到實(shí)際的工業(yè)無線網(wǎng)絡(luò)設(shè)計(jì),本文所提出的兩種調(diào)度算法適合應(yīng)用在對數(shù)據(jù)傳輸可靠性要求高的監(jiān)視類應(yīng)用或過程控制應(yīng)用場景中.其中,DS-CR 方法執(zhí)行簡單,易于實(shí)現(xiàn)在低復(fù)雜度的工業(yè)網(wǎng)絡(luò)中;而DS-IWR 算法調(diào)度效果更好,適合應(yīng)用在資源相對富裕、操作更加靈活的工業(yè)網(wǎng)絡(luò)中.值得說明的是,在調(diào)度算法中引入重傳機(jī)制后,會產(chǎn)生兩方面的影響.一方面,借助于建立重傳鏈路,失敗的包可以再次被調(diào)度傳輸,緩解了因?yàn)閬G包導(dǎo)致的調(diào)度失敗問題;另一方面,重傳鏈路的引入會占用一定的時槽、頻點(diǎn)資源,在一些網(wǎng)絡(luò)資源比較緊張的場景中,有可能會引起部分通信流的資源延遲安排,影響這些數(shù)據(jù)傳輸?shù)膶?shí)時性.因此,在確定性調(diào)度算法中考慮重傳問題,可視為在數(shù)據(jù)傳輸實(shí)時與可靠之間進(jìn)行均衡.

5 結(jié)束語

本文在建立工業(yè)無線網(wǎng)絡(luò)調(diào)度模型的基礎(chǔ)上,分析了通信流調(diào)度的必要條件和動態(tài)優(yōu)先級確定方法,針對持續(xù)重傳和區(qū)間重傳兩種重傳策略,分別提出了DS-CR 算法和DS-IWR 算法.仿真結(jié)果表明,所提出的兩種調(diào)度算法相比經(jīng)典的實(shí)時調(diào)度算法和C-LLF 算法,在網(wǎng)絡(luò)數(shù)據(jù)丟包的情況下,可以取得更高的調(diào)度成功率,保證了傳輸可靠性,實(shí)現(xiàn)了數(shù)據(jù)傳輸實(shí)時與可靠之間的有效均衡.下一步將考慮對調(diào)度算法與路由協(xié)議進(jìn)行聯(lián)合設(shè)計(jì),通過雙重優(yōu)化進(jìn)一步提升網(wǎng)絡(luò)整體調(diào)度性能.