帶寬約束下艦艇編隊網絡的跨平臺任務調度算法

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

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

0 引 言

艦艇編隊網絡與美海軍數字網絡系統（automatic digital network system，ADNS）和海上戰術廣域網（maritime tactical wide area network，MTWAN ）[1]類似，其集成了HF 子網、VHF 子網、衛星子網，運行無線異構網絡互連協議（wireless heterogenous routing protocol，WHRP），旨在建立適應于艦艇編隊戰術無線通信環境的無線IP 網絡[2]，使艦艇編隊能夠執行跨平臺網絡任務。然而，受路由切換、復雜環境、電子干擾等因素的影響，艦艇編隊無線IP 網絡的網絡帶寬具有時變性，從而給跨平臺任務規劃和任務調度帶來了困難。

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

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

1 構建跨平臺任務調度模型

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

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

1.1 網絡帶寬影響分析

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

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

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

1.2 跨平臺任務調度模型

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

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

2 跨平臺任務調度算法

以艦艇編隊無線IP 網絡任務調度模型為指導，研究跨平臺任務調度算法。首先，分析比較現有各類單處理機任務調度算法，然后，選擇最適合的算法進行適應性擴展改進。典型的單處理機實時任務調度算法包括2 大類：靜態優先級調度算法和動態優先級調度算法。

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

艦艇編隊無線IP 網絡任務調度模型，在傳統單平臺單處理機實時調度算法EDF 的基礎上，計算任務執行時間由處理機占用時間轉換為網絡占用時間，從而適用于艦艇編隊的任務調度，實現“單平臺任務調度”到“網絡化任務調度”，推導出任務可調度性的判定條件。

2.1 擴展EDF 算法的任務運行時間

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

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

2.2 擴展EDF 算法的可調度性分析

根據圖1 描述的艦艇編隊無線IP 網絡任務調度模型，艦艇編隊跨平臺調度的假設條件如下：

1） 艦艇編隊中所有跨平臺任務之間不存在相關性；

2） 單平臺處理器依據任務優先級采用搶占式調度方式；

3） 任務執行周期等于任務截止時限。

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

3 試驗測試

3.1 試驗測試網絡環境

構建如圖2 所示包括3 個平臺節點的艦艇編隊無線IP 網絡典型應用場景。其中，平臺節點1含10 個傳感器，平臺節點2 含10 個執行器，控制器（處理機）位于平臺節點3。處理機運行10 個跨平臺任務，從平臺節點1 的傳感器節點采集數據，向平臺節點2 的執行器下發指令，形成以{處理器，傳感器1，執行器1}、{處理器，傳感器2，執行器2}等為基本組態的10 個跨平臺閉環控制任務。

圖 2 艦艇編隊網絡跨平臺任務執行典型應用場景Fig. 2 Typical application scenarios of cross-platform task execution in warship formation network

根據圖2 給出的典型應用場景，建立如圖3所示的測試網絡拓撲。通過3 臺服務器模擬艦艇編隊無線IP 網絡中的3 個平臺節點，分別通過無線路由器接入艦艇編隊無線IP 網絡，服務器1 和服務器2 中分別用傳感器模擬軟件和執行器模擬軟件初始化10 個傳感器實例和10 個執行器實例，用以模擬10 個傳感器和10 個執行器；服務器3中用控制器模擬軟件初始化10 個控制器實例，用以模擬10 個控制器，并運行主控調度軟件，共模擬10 個跨平臺閉環控制任務。通過網絡抓包分析軟件（network sniffer）統計收發包。服務器 1～服務器3 通過無線路由器1～無線路由器3 組網，無線路由器通過無線信道設備與無線信道模擬器相連，配置信道設備的數據傳輸速率和無線信道模擬器的環境參數，調整信息傳輸帶寬參數。

圖 3 測試網絡拓撲Fig. 3 Test network topology

3.2 帶寬約束下的可調度性分析

在不影響結論的前提下，為便于分析，調整網絡等效帶寬為定值 16 kbit/s，依據式（2）計算任務1～10 的執行時間 ec，結果如表 1 所示。

表 1 艦艇編隊網絡跨平臺任務執行時間Table 1 Cross-platform task execution time of warship formation network

設任務1～任務10 為周期性任務且調度時間和截止時間均為300 s，在計算出任務執行時間后，依據式（3）進行可調度性分析：

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

4 結 語

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