带宽约束下舰艇编队网络的跨平台任务调度算法

武树斌，温玉屏，夏洋，汪慧君，李含辉

武汉船舶通信研究所，湖北 武汉 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 网络测试环境中，开展了多任务跨平台调度模拟测试，验证了最短时限优先扩展算法设计的合理性以及应用可行性。