帶寬約束下艦艇編隊(duì)網(wǎng)絡(luò)的跨平臺(tái)任務(wù)調(diào)度算法

武樹斌，溫玉屏，夏洋，汪慧君，李含輝

武漢船舶通信研究所，湖北 武漢 430205

0 引 言

艦艇編隊(duì)網(wǎng)絡(luò)與美海軍數(shù)字網(wǎng)絡(luò)系統(tǒng)（automatic digital network system，ADNS）和海上戰(zhàn)術(shù)廣域網(wǎng)（maritime tactical wide area network，MTWAN ）[1]類似，其集成了HF 子網(wǎng)、VHF 子網(wǎng)、衛(wèi)星子網(wǎng)，運(yùn)行無線異構(gòu)網(wǎng)絡(luò)互連協(xié)議（wireless heterogenous routing protocol，WHRP），旨在建立適應(yīng)于艦艇編隊(duì)?wèi)?zhàn)術(shù)無線通信環(huán)境的無線IP 網(wǎng)絡(luò)[2]，使艦艇編隊(duì)能夠執(zhí)行跨平臺(tái)網(wǎng)絡(luò)任務(wù)。然而，受路由切換、復(fù)雜環(huán)境、電子干擾等因素的影響，艦艇編隊(duì)無線IP 網(wǎng)絡(luò)的網(wǎng)絡(luò)帶寬具有時(shí)變性，從而給跨平臺(tái)任務(wù)規(guī)劃和任務(wù)調(diào)度帶來了困難。

目前，針對艦艇編隊(duì)跨平臺(tái)網(wǎng)絡(luò)任務(wù)的研究主要集中在編隊(duì)作戰(zhàn)中的火力規(guī)劃[3]、火力兼容[4]、武器組織[5]等作戰(zhàn)應(yīng)用層面，在評(píng)價(jià)艦艇編隊(duì)無線網(wǎng)絡(luò)的指標(biāo)方面也有許多研究成果，例如通信覆蓋能力、通信容量、網(wǎng)絡(luò)帶寬、信息傳輸時(shí)延、信息更新率、目標(biāo)傳輸精度[6-7]等。然而，有關(guān)艦艇編隊(duì)無線IP 網(wǎng)絡(luò)支撐保障能力的研究仍相對欠缺，尤其是在如何建立作戰(zhàn)應(yīng)用與無線IP 網(wǎng)絡(luò)指標(biāo)的映射關(guān)系方面，尚需開展深入的研究。

本文將運(yùn)用所開發(fā)的一種無線IP 網(wǎng)絡(luò)帶寬約束條件下的艦艇編隊(duì)跨平臺(tái)任務(wù)調(diào)度模型，以及“最早時(shí)限優(yōu)先+先來先服務(wù)”兩級(jí)任務(wù)調(diào)度模型，分析編隊(duì)作戰(zhàn)應(yīng)用與編隊(duì)網(wǎng)絡(luò)的關(guān)系。通過改 進(jìn) 常 規(guī) 的 最 早 時(shí) 限 優(yōu) 先（earliest deadline first，EDF）算法，將傳統(tǒng)的“CPU占用時(shí)間”改進(jìn)為“無線網(wǎng)絡(luò)占用時(shí)間”，來確定執(zhí)行（運(yùn)行）任務(wù)的時(shí)間，進(jìn)而給出任務(wù)可調(diào)度性的判定條件，并對此進(jìn)行試驗(yàn)驗(yàn)證。

1 構(gòu)建跨平臺(tái)任務(wù)調(diào)度模型

抽象的艦艇編隊(duì)中，各平臺(tái)傳感器、指控系統(tǒng)及武器分別為傳感器、控制器和執(zhí)行器，而編隊(duì)跨平臺(tái)任務(wù)調(diào)度涉及網(wǎng)絡(luò)中多平臺(tái)節(jié)點(diǎn)搭載的控制器、傳感器和執(zhí)行器。目前，研究任務(wù)調(diào)度模型的技術(shù)路線有2 個(gè)方向：一是研究分布式多處理機(jī)調(diào)度模型，其涉及網(wǎng)絡(luò)中硬件服務(wù)器或者云平臺(tái)多個(gè)處理機(jī)間的信息交互、資源協(xié)調(diào)等，研究的重點(diǎn)是任務(wù)在處理機(jī)中的執(zhí)行效率[8-9]；二是研究無線IP 網(wǎng)絡(luò)任務(wù)調(diào)度模型，用于分析無線IP 網(wǎng)絡(luò)環(huán)境下跨平臺(tái)任務(wù)調(diào)度的處理時(shí)間與網(wǎng)絡(luò)帶寬的相互關(guān)系，建立處理機(jī)任務(wù)執(zhí)行時(shí)間與網(wǎng)絡(luò)帶寬的對應(yīng)關(guān)系，以及采用單處理機(jī)“網(wǎng)絡(luò)化”任務(wù)調(diào)度的技術(shù)路線開展研究分析。

分布式多處理機(jī)調(diào)度模型是將任務(wù)映射到網(wǎng)絡(luò)中多個(gè)處理機(jī)并發(fā)運(yùn)行，以達(dá)到縮短任務(wù)運(yùn)行總體時(shí)間的目的，但由此會(huì)造成多處理機(jī)間通信開銷變大[10]，會(huì)消耗寶貴的無線通信資源。本文將重點(diǎn)研究如何以盡量少的通信開銷來調(diào)度任務(wù)，但其不適用于分布式多處理機(jī)調(diào)度模型，故在實(shí)時(shí)系統(tǒng)的單處理器調(diào)度算法[11]的基礎(chǔ)上進(jìn)行“網(wǎng)絡(luò)化”改進(jìn)，以研究處理機(jī)任務(wù)執(zhí)行時(shí)間與網(wǎng)絡(luò)帶寬的量化對應(yīng)關(guān)系，構(gòu)建無線IP 網(wǎng)絡(luò)任務(wù)調(diào)度模型。

1.1 網(wǎng)絡(luò)帶寬影響分析

艦艇編隊(duì)網(wǎng)絡(luò)的跨平臺(tái)任務(wù)調(diào)度涉及的資源包括：艦艇編隊(duì)無線IP 網(wǎng)絡(luò)傳輸帶寬、本平臺(tái)處理機(jī)的處理時(shí)間、本平臺(tái)路由器的處理時(shí)間等。任務(wù) T的運(yùn)行時(shí)間E 用函數(shù)F 表示為

式中： C為任務(wù)T 的本平臺(tái)處理時(shí)間（包括本平臺(tái)內(nèi)網(wǎng)交換時(shí)間、本平臺(tái)處理機(jī)處理時(shí)間、本平臺(tái)路由器處理時(shí)間等）； W 為任務(wù) T所占用的艦艇編隊(duì)無線IP 網(wǎng)絡(luò)傳輸帶寬。

艦艇編隊(duì)網(wǎng)絡(luò)的跨平臺(tái)任務(wù)主要受無線IP 網(wǎng)絡(luò)傳輸時(shí)延的影響，該網(wǎng)絡(luò)基于IP 的戰(zhàn)術(shù)無線通信網(wǎng)絡(luò)，覆蓋范圍大、通信對象多，帶寬受到的影響因素較多（包括網(wǎng)絡(luò)層面和鏈路層面）。在網(wǎng)絡(luò)層面，帶寬主要受IP 網(wǎng)絡(luò)路由算法的影響，算法動(dòng)態(tài)選擇無線鏈路，路由切換會(huì)造成端到端的網(wǎng)絡(luò)帶寬變化。另外，IP 網(wǎng)絡(luò)路由算法的鄰居節(jié)點(diǎn)發(fā)現(xiàn)與維護(hù)、路由表維護(hù)等的運(yùn)行開銷也會(huì)占用并影響寶貴的無線網(wǎng)絡(luò)帶寬。在鏈路層面，帶寬主要受無線信道傳播特性環(huán)境的影響（包括信號(hào)衰落、路徑延遲、多普勒效應(yīng)、干擾和噪聲等），致使通信鏈路的傳輸速率處于動(dòng)態(tài)變化中。另外，處于強(qiáng)對抗環(huán)境中的艦艇編隊(duì)網(wǎng)絡(luò)還會(huì)受到敵方的干擾與破壞，使通信鏈路的傳輸速率降級(jí)或不可用。

1.2 跨平臺(tái)任務(wù)調(diào)度模型

選取典型的艦艇編隊(duì)跨平臺(tái)任務(wù)分析和建模。設(shè)控制器、傳感器和執(zhí)行器分別位于艦艇編隊(duì)不同的平臺(tái)節(jié)點(diǎn)上，一個(gè)艦艇編隊(duì)跨平臺(tái)任務(wù)包括“單播請求–單播響應(yīng)”、“組播請求–單播響應(yīng)”、“組播請求–組播響應(yīng)”等多種信息交互形式，其涉及了請求報(bào)文和網(wǎng)絡(luò)響應(yīng)報(bào)文的多次網(wǎng)絡(luò)交互。

艦艇編隊(duì)跨平臺(tái)任務(wù)通過編隊(duì)無線IP 網(wǎng)絡(luò)交互通信，此時(shí)，稱初始跨平臺(tái)任務(wù)的控制器、執(zhí)行器和傳感器為“任務(wù)發(fā)起方”，而響應(yīng)跨平臺(tái)任務(wù)的控制器、執(zhí)行器和傳感器則為“任務(wù)響應(yīng)方”。設(shè)任務(wù)發(fā)起方采用基于時(shí)限優(yōu)先級(jí)的周期調(diào)度，每個(gè)周期內(nèi)的跨平臺(tái)任務(wù)組成調(diào)度隊(duì)列，處理機(jī)采用基于截止時(shí)限優(yōu)先級(jí)從高到低的方式調(diào)度各跨平臺(tái)任務(wù)。設(shè)任務(wù)響應(yīng)方采用先來先服務(wù)（first come first serve，F(xiàn)CFS）的調(diào)度方式，對跨平臺(tái)任務(wù)響應(yīng)作業(yè)進(jìn)行排隊(duì)調(diào)度，處理接收到的請求和響應(yīng)報(bào)文。該任務(wù)模型可以將研究重點(diǎn)聚焦于任務(wù)發(fā)起方的處理機(jī)，從而將復(fù)雜的網(wǎng)絡(luò)全局調(diào)度問題簡化為任務(wù)發(fā)起方中的單處理機(jī)任務(wù)調(diào)度問題。圖1 所示為基于艦艇編隊(duì)無線IP 網(wǎng)絡(luò)的跨平臺(tái)任務(wù)調(diào)度模型。

2 跨平臺(tái)任務(wù)調(diào)度算法

以艦艇編隊(duì)無線IP 網(wǎng)絡(luò)任務(wù)調(diào)度模型為指導(dǎo)，研究跨平臺(tái)任務(wù)調(diào)度算法。首先，分析比較現(xiàn)有各類單處理機(jī)任務(wù)調(diào)度算法，然后，選擇最適合的算法進(jìn)行適應(yīng)性擴(kuò)展改進(jìn)。典型的單處理機(jī)實(shí)時(shí)任務(wù)調(diào)度算法包括2 大類：靜態(tài)優(yōu)先級(jí)調(diào)度算法和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法。

時(shí)間片輪轉(zhuǎn)調(diào)度[12]是典型的靜態(tài)優(yōu)先級(jí)調(diào)度算法，即每個(gè)時(shí)間片執(zhí)行一個(gè)任務(wù)，當(dāng)時(shí)間片到期后，如果該任務(wù)未執(zhí)行完成則保存其上、下文，并掛起以等待下一個(gè)時(shí)間片繼續(xù)執(zhí)行。EDF 算法是典型的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，其按照任務(wù)截止時(shí)限調(diào)度任務(wù)，被廣泛應(yīng)用于實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度。其中，搶占式EDF 算法的調(diào)度靈活、CPU 利用率高，已被證明是最優(yōu)的單處理機(jī)動(dòng)態(tài)調(diào)度算法[13]。與非搶占式EDF 算法相比，雖然搶占式EDF 算法存在內(nèi)容轉(zhuǎn)換開銷大、內(nèi)存需求相對較高的缺點(diǎn)，但該缺點(diǎn)可通過增加處理機(jī)內(nèi)存容量的方式予以克服。

艦艇編隊(duì)無線IP 網(wǎng)絡(luò)任務(wù)調(diào)度模型，在傳統(tǒng)單平臺(tái)單處理機(jī)實(shí)時(shí)調(diào)度算法EDF 的基礎(chǔ)上，計(jì)算任務(wù)執(zhí)行時(shí)間由處理機(jī)占用時(shí)間轉(zhuǎn)換為網(wǎng)絡(luò)占用時(shí)間，從而適用于艦艇編隊(duì)的任務(wù)調(diào)度，實(shí)現(xiàn)“單平臺(tái)任務(wù)調(diào)度”到“網(wǎng)絡(luò)化任務(wù)調(diào)度”，推導(dǎo)出任務(wù)可調(diào)度性的判定條件。

2.1 擴(kuò)展EDF 算法的任務(wù)運(yùn)行時(shí)間

根據(jù)式（1），艦艇編隊(duì)跨平臺(tái)任務(wù)運(yùn)行時(shí)間受限于本平臺(tái)處理時(shí)間和任務(wù)占用艦艇編隊(duì)的無線IP 網(wǎng)絡(luò)傳輸帶寬。在本平臺(tái)處理時(shí)間較短且可控的前提下，跨平臺(tái)任務(wù)的運(yùn)行時(shí)間主要由無線IP 網(wǎng)絡(luò)帶寬決定。

擴(kuò)展EDF 算法[14]是以實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度算法EDF 為基礎(chǔ)，將每個(gè)任務(wù)的網(wǎng)絡(luò)帶寬需求映射為等效網(wǎng)絡(luò)帶寬。等效網(wǎng)絡(luò)帶寬為估計(jì)值，代表未來某通信時(shí)段的網(wǎng)絡(luò)帶寬預(yù)測值，采取的估計(jì)方式包括：一是通信設(shè)備主動(dòng)上報(bào)，時(shí)變信道引發(fā)通信設(shè)備的自適應(yīng)調(diào)制編碼（adaptive coding and modulation，ACM）機(jī)制，主動(dòng)選擇與信道質(zhì)量相適應(yīng)的調(diào)制參數(shù)，經(jīng)由此通信鏈路的網(wǎng)絡(luò)路由將產(chǎn)生帶寬變化；二是通信系統(tǒng)采用“網(wǎng)絡(luò)探針”進(jìn)行網(wǎng)絡(luò)帶寬探測，并結(jié)合歷史數(shù)據(jù)和信道質(zhì)量預(yù)測未來通信時(shí)間段的等效網(wǎng)絡(luò)帶寬。

2.2 擴(kuò)展EDF 算法的可調(diào)度性分析

根據(jù)圖1 描述的艦艇編隊(duì)無線IP 網(wǎng)絡(luò)任務(wù)調(diào)度模型，艦艇編隊(duì)跨平臺(tái)調(diào)度的假設(shè)條件如下：

1） 艦艇編隊(duì)中所有跨平臺(tái)任務(wù)之間不存在相關(guān)性；

2） 單平臺(tái)處理器依據(jù)任務(wù)優(yōu)先級(jí)采用搶占式調(diào)度方式；

3） 任務(wù)執(zhí)行周期等于任務(wù)截止時(shí)限。

由上述假設(shè)，艦艇編隊(duì)中單平臺(tái)處理機(jī)可基于EDF 算法跨平臺(tái)調(diào)度任務(wù)的充要條件如下：

3 試驗(yàn)測試

3.1 試驗(yàn)測試網(wǎng)絡(luò)環(huán)境

構(gòu)建如圖2 所示包括3 個(gè)平臺(tái)節(jié)點(diǎn)的艦艇編隊(duì)無線IP 網(wǎng)絡(luò)典型應(yīng)用場景。其中，平臺(tái)節(jié)點(diǎn)1含10 個(gè)傳感器，平臺(tái)節(jié)點(diǎn)2 含10 個(gè)執(zhí)行器，控制器（處理機(jī)）位于平臺(tái)節(jié)點(diǎn)3。處理機(jī)運(yùn)行10 個(gè)跨平臺(tái)任務(wù)，從平臺(tái)節(jié)點(diǎn)1 的傳感器節(jié)點(diǎn)采集數(shù)據(jù)，向平臺(tái)節(jié)點(diǎn)2 的執(zhí)行器下發(fā)指令，形成以{處理器，傳感器1，執(zhí)行器1}、{處理器，傳感器2，執(zhí)行器2}等為基本組態(tài)的10 個(gè)跨平臺(tái)閉環(huán)控制任務(wù)。

圖 2 艦艇編隊(duì)網(wǎng)絡(luò)跨平臺(tái)任務(wù)執(zhí)行典型應(yīng)用場景Fig. 2 Typical application scenarios of cross-platform task execution in warship formation network

根據(jù)圖2 給出的典型應(yīng)用場景，建立如圖3所示的測試網(wǎng)絡(luò)拓?fù)?。通過3 臺(tái)服務(wù)器模擬艦艇編隊(duì)無線IP 網(wǎng)絡(luò)中的3 個(gè)平臺(tái)節(jié)點(diǎn)，分別通過無線路由器接入艦艇編隊(duì)無線IP 網(wǎng)絡(luò)，服務(wù)器1 和服務(wù)器2 中分別用傳感器模擬軟件和執(zhí)行器模擬軟件初始化10 個(gè)傳感器實(shí)例和10 個(gè)執(zhí)行器實(shí)例，用以模擬10 個(gè)傳感器和10 個(gè)執(zhí)行器；服務(wù)器3中用控制器模擬軟件初始化10 個(gè)控制器實(shí)例，用以模擬10 個(gè)控制器，并運(yùn)行主控調(diào)度軟件，共模擬10 個(gè)跨平臺(tái)閉環(huán)控制任務(wù)。通過網(wǎng)絡(luò)抓包分析軟件（network sniffer）統(tǒng)計(jì)收發(fā)包。服務(wù)器 1～服務(wù)器3 通過無線路由器1～無線路由器3 組網(wǎng)，無線路由器通過無線信道設(shè)備與無線信道模擬器相連，配置信道設(shè)備的數(shù)據(jù)傳輸速率和無線信道模擬器的環(huán)境參數(shù)，調(diào)整信息傳輸帶寬參數(shù)。

圖 3 測試網(wǎng)絡(luò)拓?fù)銯ig. 3 Test network topology

3.2 帶寬約束下的可調(diào)度性分析

在不影響結(jié)論的前提下，為便于分析，調(diào)整網(wǎng)絡(luò)等效帶寬為定值 16 kbit/s，依據(jù)式（2）計(jì)算任務(wù)1～10 的執(zhí)行時(shí)間 ec，結(jié)果如表 1 所示。

表 1 艦艇編隊(duì)網(wǎng)絡(luò)跨平臺(tái)任務(wù)執(zhí)行時(shí)間Table 1 Cross-platform task execution time of warship formation network

設(shè)任務(wù)1～任務(wù)10 為周期性任務(wù)且調(diào)度時(shí)間和截止時(shí)間均為300 s，在計(jì)算出任務(wù)執(zhí)行時(shí)間后，依據(jù)式（3）進(jìn)行可調(diào)度性分析：

結(jié)果小于1 符合可調(diào)度性判定條件，因此位于服務(wù)器3 的主控調(diào)度軟件可以進(jìn)行跨平臺(tái)任務(wù)1～任務(wù)10 的實(shí)時(shí)調(diào)度，而且任務(wù)10 距離截止時(shí)間最近，應(yīng)安排的調(diào)度優(yōu)先級(jí)高于其他任務(wù)，最先得到調(diào)度運(yùn)行。

4 結(jié) 語

艦艇編隊(duì)跨平臺(tái)任務(wù)執(zhí)行時(shí)間具有實(shí)時(shí)性或時(shí)限性的要求，而無線IP 網(wǎng)絡(luò)在網(wǎng)絡(luò)層、鏈路層存在時(shí)變性，使多任務(wù)并發(fā)執(zhí)行受到網(wǎng)絡(luò)帶寬瓶頸約束，給多任務(wù)調(diào)度帶來困難。本文分析了網(wǎng)絡(luò)帶寬對任務(wù)調(diào)度的影響，提出了網(wǎng)絡(luò)等效帶寬的概念及其計(jì)算方法。在比較分布式多處理機(jī)網(wǎng)絡(luò)調(diào)度算法和單處理機(jī)調(diào)度算法的基礎(chǔ)上，建立了艦艇編隊(duì)跨平臺(tái)任務(wù)調(diào)度模型，提出了最短時(shí)限優(yōu)先擴(kuò)展算法，該算法能夠在考慮網(wǎng)絡(luò)等效帶寬的基礎(chǔ)上，較好地計(jì)算任務(wù)執(zhí)行時(shí)間并分析多任務(wù)的可調(diào)度性。本文在設(shè)計(jì)的典型艦艇編隊(duì)無線IP 網(wǎng)絡(luò)測試環(huán)境中，開展了多任務(wù)跨平臺(tái)調(diào)度模擬測試，驗(yàn)證了最短時(shí)限優(yōu)先擴(kuò)展算法設(shè)計(jì)的合理性以及應(yīng)用可行性。