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

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

0 引 言

艦艇編隊網(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)，運行無線異構(gòu)網(wǎng)絡(luò)互連協(xié)議（wireless heterogenous routing protocol，WHRP），旨在建立適應(yīng)于艦艇編隊?wèi)?zhàn)術(shù)無線通信環(huán)境的無線IP 網(wǎng)絡(luò)[2]，使艦艇編隊能夠執(zhí)行跨平臺網(wǎng)絡(luò)任務(wù)。然而，受路由切換、復(fù)雜環(huán)境、電子干擾等因素的影響，艦艇編隊無線IP 網(wǎng)絡(luò)的網(wǎng)絡(luò)帶寬具有時變性，從而給跨平臺任務(wù)規(guī)劃和任務(wù)調(diào)度帶來了困難。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 擴展EDF 算法的任務(wù)運行時間

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

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

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

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

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

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

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

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

3 試驗測試

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

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

圖 2 艦艇編隊網(wǎng)絡(luò)跨平臺任務(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ò)拓撲。通過3 臺服務(wù)器模擬艦艇編隊無線IP 網(wǎng)絡(luò)中的3 個平臺節(jié)點，分別通過無線路由器接入艦艇編隊無線IP 網(wǎng)絡(luò)，服務(wù)器1 和服務(wù)器2 中分別用傳感器模擬軟件和執(zhí)行器模擬軟件初始化10 個傳感器實例和10 個執(zhí)行器實例，用以模擬10 個傳感器和10 個執(zhí)行器；服務(wù)器3中用控制器模擬軟件初始化10 個控制器實例，用以模擬10 個控制器，并運行主控調(diào)度軟件，共模擬10 個跨平臺閉環(huán)控制任務(wù)。通過網(wǎng)絡(luò)抓包分析軟件（network sniffer）統(tǒng)計收發(fā)包。服務(wù)器 1～服務(wù)器3 通過無線路由器1～無線路由器3 組網(wǎng)，無線路由器通過無線信道設(shè)備與無線信道模擬器相連，配置信道設(shè)備的數(shù)據(jù)傳輸速率和無線信道模擬器的環(huán)境參數(shù)，調(diào)整信息傳輸帶寬參數(shù)。

圖 3 測試網(wǎng)絡(luò)拓撲Fig. 3 Test network topology

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

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

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

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

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

4 結(jié) 語

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