留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

武树斌, 温玉屏, 夏洋, 等. 带宽约束下舰艇编队网络的跨平台任务调度算法[J]. 中国舰船研究, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
引用本文: 武树斌, 温玉屏, 夏洋, 等. 带宽约束下舰艇编队网络的跨平台任务调度算法[J]. 中国舰船研究, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
WU S B, WEN Y P, XIA Y, et al. Cross-platform task scheduling algorithm of warship formation network under bandwidth constraints[J]. Chinese Journal of Ship Research, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
Citation: WU S B, WEN Y P, XIA Y, et al. Cross-platform task scheduling algorithm of warship formation network under bandwidth constraints[J]. Chinese Journal of Ship Research, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899

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

doi: 10.19693/j.issn.1673-3185.01899
详细信息
    作者简介:

    武树斌,男,1975年生,博士,高级工程师。研究方向:信息系统通信网络,舰船通信系统。E-mail:34041381@qq.com

    温玉屏,女,1978年生,硕士,高级工程师。研究方向:数据通信,信息安全

    夏洋,男,1983年生,博士,高级工程师。研究方向:舰船通信系统

    通讯作者:

    武树斌

  • 中图分类号: U674.7; TN929.5

Cross-platform task scheduling algorithm of warship formation network under bandwidth constraints

图(3) / 表 (1)
计量
  • 文章访问数:  15
  • HTML全文浏览量:  6
  • PDF下载量:  1
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-12
  • 修回日期:  2020-07-05
  • 网络出版日期:  2020-11-09
  • 刊出日期:  2020-12-30

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

doi: 10.19693/j.issn.1673-3185.01899
    作者简介:

    武树斌,男,1975年生,博士,高级工程师。研究方向:信息系统通信网络,舰船通信系统。E-mail:34041381@qq.com

    温玉屏,女,1978年生,硕士,高级工程师。研究方向:数据通信,信息安全

    夏洋,男,1983年生,博士,高级工程师。研究方向:舰船通信系统

    通讯作者: 武树斌
  • 中图分类号: U674.7; TN929.5

摘要:   目的  舰艇编队无线IP网络的带宽有限且具有时变性,故为满足编队作战应用对跨平台任务运行的时限要求,需研究网络带宽约束下的跨平台任务调度算法。  方法  提出舰艇编队无线IP网络任务调度模型,运用“任务发起方”和“任务响应方”的通信模式,实现“最早时限优先+先来先服务”两级任务调度。采用所提的最早时限优先(EDF)扩展算法,在传统的单平台单处理机实时调度算法基础上,将任务执行时间的计算由处理机占用时间转换为网络占用时间,以适用于舰艇编队需要,进而推导出任务可调度性的判定条件,并对此进行试验验证。  结果  试验结果表明,在所构建的测试网络环境下,可计算得到舰艇编队跨平台任务集合的可调度性。  结论  所提理论模型及算法具有较强的可实施性,对于指导舰艇编队无线IP网络的任务规划和任务调度具有重要价值。

English Abstract

武树斌, 温玉屏, 夏洋, 等. 带宽约束下舰艇编队网络的跨平台任务调度算法[J]. 中国舰船研究, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
引用本文: 武树斌, 温玉屏, 夏洋, 等. 带宽约束下舰艇编队网络的跨平台任务调度算法[J]. 中国舰船研究, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
WU S B, WEN Y P, XIA Y, et al. Cross-platform task scheduling algorithm of warship formation network under bandwidth constraints[J]. Chinese Journal of Ship Research, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
Citation: WU S B, WEN Y P, XIA Y, et al. Cross-platform task scheduling algorithm of warship formation network under bandwidth constraints[J]. Chinese Journal of Ship Research, 2020, 15(6): 170–175 doi:  10.19693/j.issn.1673-3185.01899
    • 舰艇编队网络与美海军数字网络系统(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占用时间”改进为“无线网络占用时间”,来确定执行(运行)任务的时间,进而给出任务可调度性的判定条件,并对此进行试验验证。

    • 抽象的舰艇编队中,各平台传感器、指控系统及武器分别为传感器、控制器和执行器,而编队跨平台任务调度涉及网络中多平台节点搭载的控制器、传感器和执行器。目前,研究任务调度模型的技术路线有2个方向:一是研究分布式多处理机调度模型,其涉及网络中硬件服务器或者云平台多个处理机间的信息交互、资源协调等,研究的重点是任务在处理机中的执行效率[8-9];二是研究无线IP网络任务调度模型,用于分析无线IP网络环境下跨平台任务调度的处理时间与网络带宽的相互关系,建立处理机任务执行时间与网络带宽的对应关系,以及采用单处理机“网络化”任务调度的技术路线开展研究分析。

      分布式多处理机调度模型是将任务映射到网络中多个处理机并发运行,以达到缩短任务运行总体时间的目的,但由此会造成多处理机间通信开销变大[10],会消耗宝贵的无线通信资源。本文将重点研究如何以尽量少的通信开销来调度任务,但其不适用于分布式多处理机调度模型,故在实时系统的单处理器调度算法[11]的基础上进行“网络化”改进,以研究处理机任务执行时间与网络带宽的量化对应关系,构建无线IP网络任务调度模型。

    • 舰艇编队网络的跨平台任务调度涉及的资源包括:舰艇编队无线IP网络传输带宽、本平台处理机的处理时间、本平台路由器的处理时间等。任务$T$的运行时间E用函数F表示为

      $$E(T) = F(C,W)$$ (1)

      式中:$C$为任务T的本平台处理时间(包括本平台内网交换时间、本平台处理机处理时间、本平台路由器处理时间等);$W$为任务$T$所占用的舰艇编队无线IP网络传输带宽。

      舰艇编队网络的跨平台任务主要受无线IP网络传输时延的影响,该网络基于IP的战术无线通信网络,覆盖范围大、通信对象多,带宽受到的影响因素较多(包括网络层面和链路层面)。在网络层面,带宽主要受IP网络路由算法的影响,算法动态选择无线链路,路由切换会造成端到端的网络带宽变化。另外,IP网络路由算法的邻居节点发现与维护、路由表维护等的运行开销也会占用并影响宝贵的无线网络带宽。在链路层面,带宽主要受无线信道传播特性环境的影响(包括信号衰落、路径延迟、多普勒效应、干扰和噪声等),致使通信链路的传输速率处于动态变化中。另外,处于强对抗环境中的舰艇编队网络还会受到敌方的干扰与破坏,使通信链路的传输速率降级或不可用。

    • 选取典型的舰艇编队跨平台任务分析和建模。设控制器、传感器和执行器分别位于舰艇编队不同的平台节点上,一个舰艇编队跨平台任务包括“单播请求–单播响应”、“组播请求–单播响应”、“组播请求–组播响应”等多种信息交互形式,其涉及了请求报文和网络响应报文的多次网络交互。

      舰艇编队跨平台任务通过编队无线IP网络交互通信,此时,称初始跨平台任务的控制器、执行器和传感器为“任务发起方”,而响应跨平台任务的控制器、执行器和传感器则为“任务响应方”。设任务发起方采用基于时限优先级的周期调度,每个周期内的跨平台任务组成调度队列,处理机采用基于截止时限优先级从高到低的方式调度各跨平台任务。设任务响应方采用先来先服务(first come first serve,FCFS)的调度方式,对跨平台任务响应作业进行排队调度,处理接收到的请求和响应报文。该任务模型可以将研究重点聚焦于任务发起方的处理机,从而将复杂的网络全局调度问题简化为任务发起方中的单处理机任务调度问题。图1所示为基于舰艇编队无线IP网络的跨平台任务调度模型。

      图  1  舰艇编队无线IP网络任务调度模型

      Figure 1.  Task scheduling model of wireless IP network for warship formation

    • 以舰艇编队无线IP网络任务调度模型为指导,研究跨平台任务调度算法。首先,分析比较现有各类单处理机任务调度算法,然后,选择最适合的算法进行适应性扩展改进。典型的单处理机实时任务调度算法包括2大类:静态优先级调度算法和动态优先级调度算法。

      时间片轮转调度[12]是典型的静态优先级调度算法,即每个时间片执行一个任务,当时间片到期后,如果该任务未执行完成则保存其上、下文,并挂起以等待下一个时间片继续执行。EDF算法是典型的动态优先级调度算法,其按照任务截止时限调度任务,被广泛应用于实时系统任务调度。其中,抢占式EDF算法的调度灵活、CPU利用率高,已被证明是最优的单处理机动态调度算法[13]。与非抢占式EDF算法相比,虽然抢占式EDF算法存在内容转换开销大、内存需求相对较高的缺点,但该缺点可通过增加处理机内存容量的方式予以克服。

      舰艇编队无线IP网络任务调度模型,在传统单平台单处理机实时调度算法EDF的基础上,计算任务执行时间由处理机占用时间转换为网络占用时间,从而适用于舰艇编队的任务调度,实现“单平台任务调度”到“网络化任务调度”,推导出任务可调度性的判定条件。

    • 根据式(1),舰艇编队跨平台任务运行时间受限于本平台处理时间和任务占用舰艇编队的无线IP网络传输带宽。在本平台处理时间较短且可控的前提下,跨平台任务的运行时间主要由无线IP网络带宽决定。

      扩展EDF算法[14]是以实时系统任务调度算法EDF为基础,将每个任务的网络带宽需求映射为等效网络带宽。等效网络带宽为估计值,代表未来某通信时段的网络带宽预测值,采取的估计方式包括:一是通信设备主动上报,时变信道引发通信设备的自适应调制编码(adaptive coding and modulation,ACM)机制,主动选择与信道质量相适应的调制参数,经由此通信链路的网络路由将产生带宽变化;二是通信系统采用“网络探针”进行网络带宽探测,并结合历史数据和信道质量预测未来通信时间段的等效网络带宽。

      扩展EDF算法任务运行时间的计算是以“网络等效带宽”替代传统EDF算法中的“CPU占用时间”,映射方法是通过统计任务运行过程中交换的网络请求报文及网络响应报文的长度与数量,并与等效网络带宽相比较得出。应用扩展EDF算法的舰艇编队跨平台任务运行(执行)时间${e_{\rm{c}}}$遵循以下公式:

      $${e_{\rm{c}}} = \sum\limits_{\rm{1}}^n {\frac{{{L_i}}}{{{{\hat w}_i}}}} \;,\;\;{1 \leqslant i \leqslant n} $$ (2)

      式中:$n$为在任务发起方与任务响应方间交换的网络请求报文及网络响应报文数量;${L_i}$为舰艇编队网络相关处理机、传感器、执行器间交换的第$i$个网络报文的长度(完成一项跨平台任务,需要$n$个报文交换);${\hat w_i}$为第$i$个报文所经过的舰艇编队网络路由中的等效网络带宽。

      扩展EDF算法将根据每个任务的运行时间${e_{\rm{c}}}$距离任务截止时限的长短,按照由小到大的优先级顺序调度任务,其顺序可根据${e_{\rm{c}}}$的变化动态调整,高优先级任务可抢占低优先级任务。扩展EDF算法的算法复杂度不高,工程可实施性强。

    • 根据图1描述的舰艇编队无线IP网络任务调度模型,舰艇编队跨平台调度的假设条件如下:

      1) 舰艇编队中所有跨平台任务之间不存在相关性;

      2) 单平台处理器依据任务优先级采用抢占式调度方式;

      3) 任务执行周期等于任务截止时限。

      由上述假设,舰艇编队中单平台处理机可基于EDF算法跨平台调度任务的充要条件如下:

      $$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$$ (3)

      式中:${e_i}$为任务$i$的运行时间;${P_i}$为任务$i$的任务执行周期及任务截止时限。

      证明:

      首先,通过反证法证明必要性。令$\sum\limits_{i = 1}^n {({e_i}/{P_i})} > 1$$P$为从任务${P_1}$${P_n}$的最小公倍数,比值${l_i} = P/{P_i}$。在$\left[ {kP,(k + 1)P} \right],(k = 0,1, \cdots ,n)$区间内,处理机接收的调度任务请求数量为

      $$\sum\limits_{i = 1}^n {{l_i}{e_i} = P\left\{ {\sum\limits_{i = 1}^n {\frac{{{e_i}}}{{{P_i}}}} } \right\}} > P$$ (4)

      由上式可知,处理机接收的任务调度请求数量高于处理速度,没有得到调度的任务将随时间堆积。因此,若在$\sum\limits_{i = 1}^n {({e_i}/{P_i})} {\rm{ > }}1$的情况下处理机不能调度从${P_1}$${P_n}$的全部任务,则$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$成立,从而完成必要性证明。

      然后,通过反证法证明充分性。若$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$不成立,将存在满足$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$的有限任务集合$S$,EDF算法不能全部调度任务集合$S$。假设${t_{\rm{f}}}$为任务调度时限被超过的最早时间,最早时间${t_{\rm{f}}}$存在且满足${t_{\rm{f}}} > 0$,假设${S_{\rm{f}}}$为有限任务集合$S$中绝对时间等于${t_{\rm{f}}}$的任务集合,则处理机在$[0,\;{t_{\rm{f}}}]$区间内保持被占用的状态,具体分析包括:

      1)$[{\rm{0}},\;{t_{\rm{f}}}]$区间内运行的任务截止时限低于${t_{\rm{f}}}$。因为${t_{\rm{f}}}$时间后的其他任务重复运行时限均已到达,所以在此区间内任务${T_i}$完成的重复次数为$[{{{t_{\rm{f}}}} / {{P_i}}}]$。由于处理机在$[{\rm{0}},\;{t_{\rm{f}}}]$时间内一直保持被占用的状态,所以将出现时限未到${t_{\rm{f}}}$的任务向处理机请求的运行时间超过${t_{\rm{f}}}$。推导过程如式(5)所示。

      $$\begin{split} &\quad\quad {\left\lfloor {\frac{{{t_{\rm{f}}}}}{{{P_1}}}} \right\rfloor {e_1} + \left\lfloor {\frac{{{t_{\rm{f}}}}}{{{P_2}}}} \right\rfloor {e_2} + \cdots + \left\lfloor {\frac{{{t_{\rm{f}}}}}{{{P_n}}}} \right\rfloor {e_n} > {t_{\rm{f}}}} \Rightarrow\\ & { \left( {\frac{{{t_{\rm{f}}}}}{{{P_1}}}} \right){e_1} + \left( {\frac{{{t_{\rm{f}}}}}{{{P_2}}}} \right){e_2} + \cdots + \left( {\frac{{{t_{\rm{f}}}}}{{{P_n}}}} \right){e_n} > {t_{\rm{f}}}} { \Rightarrow \sum\limits_{i = 1}^n {\frac{{{e_i}}}{{{P_i}}} > 1} } \end{split} $$ (5)

      该推论与假设条件$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$矛盾。

      2)在$[\tau ,\;{t_{\rm{f}}}]$区间内运行的任务截止时限高于${t_{\rm{f}}}$。设处理机在某时间τ(接近tf)正在运行时限超过${t_{\rm{f}}}$的一个任务,根据假设条件2)可知,EDF算法是基于抢占式的任务调度,故此时没有正在等待被调用且其为任务截止时限早于$n$的任务,在$i$区间处理机将释放所有任务。若某任务截止时限高于$L$,则在$[\tau ,\;{t_{\rm{f}}}]$区间内处理机总的占用时间将超过区间长度。推导过程如式(6)所示。

      $$\begin{split} &\quad\;\; {\left\lfloor {\frac{{{t_{\rm{f}}} - \tau }}{{{P_1}}}} \right\rfloor {e_1} + \left\lfloor {\frac{{{t_{\rm{f}}} - \tau }}{{{P_2}}}} \right\rfloor {e_2} + \cdots + \left\lfloor {\frac{{{t_{\rm{f}}} - \tau }}{{{P_n}}}} \right\rfloor {e_n} > {t_{\rm{f}}}} \Rightarrow \\ & {\left( {\frac{{{t_{\rm{f}}} \!-\! \tau }}{{{P_1}}}} \right){e_1} \!+ \!\left( {\frac{{{t_{\rm{f}}}\! -\! \tau }}{{{P_2}}}} \right){e_2} \!+\! \cdots \!+\! \left( {\frac{{{t_{\rm{f}}} \!- \!\tau }}{{{P_n}}}} \right){e_n} > {t_{\rm{f}}}} { \Rightarrow \sum\limits_{i = 1}^n {\frac{{{e_i}}}{{{P_i}}} > 1} } \end{split} $$ (6)

      该推论与假设条件$\sum\limits_{i = 1}^n {({e_i}/{P_i})} \leqslant 1$相矛盾,完成了充分性证明。

    • 构建如图2所示包括3个平台节点的舰艇编队无线IP网络典型应用场景。其中,平台节点1含10个传感器,平台节点2含10个执行器,控制器(处理机)位于平台节点3。处理机运行10个跨平台任务,从平台节点1的传感器节点采集数据,向平台节点2的执行器下发指令,形成以{处理器,传感器1,执行器1}、{处理器,传感器2,执行器2}等为基本组态的10个跨平台闭环控制任务。

      图  2  舰艇编队网络跨平台任务执行典型应用场景

      Figure 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  测试网络拓扑

      Figure 3.  Test network topology

    • 在不影响结论的前提下,为便于分析,调整网络等效带宽为定值16 kbit/s,依据式(2)计算任务1~10的执行时间${e_{\rm{c}}}$,结果如表1所示。

      表 1  舰艇编队网络跨平台任务执行时间

      Table 1.  Cross-platform task execution time of warship formation network

      任务$n$报文数量
      $i$/个
      报文字节数
      /Byte
      报文长度
      /bit
      任务执行时间
      ec /s
      任务141284 0960.25
      任务281288 1920.5
      任务31612816 3841
      任务43212832 7682
      任务56412865 5364
      任务6128128131 0728
      任务7256128262 14416
      任务8512128524 28832
      任务91 0241281 048 57664
      任务102 0481282 097 152128

      设任务1~任务10为周期性任务且调度时间和截止时间均为300 s,在计算出任务执行时间后,依据式(3)进行可调度性分析:

      $$ \begin{split} & \frac{{{\rm{0}}{\rm{.25}}}}{{{\rm{300}}}} + \frac{{{\rm{0}}.5}}{{{\rm{300}}}} + \frac{{\rm{1}}}{{{\rm{300}}}} + \frac{{\rm{2}}}{{{\rm{300}}}} + \frac{{\rm{4}}}{{{\rm{300}}}} + \frac{{\rm{8}}}{{{\rm{300}}}} + \\&\quad \frac{{{\rm{16}}}}{{{\rm{300}}}} + \frac{{{\rm{32}}}}{{{\rm{300}}}} + \frac{{{\rm{65}}}}{{{\rm{300}}}} + \frac{{{\rm{130}}}}{{{\rm{300}}}} = {\rm{0}}.853 < 1 \end{split} $$ (7)

      结果小于1符合可调度性判定条件,因此位于服务器3的主控调度软件可以进行跨平台任务1~任务10的实时调度,而且任务10距离截止时间最近,应安排的调度优先级高于其他任务,最先得到调度运行。

    • 舰艇编队跨平台任务执行时间具有实时性或时限性的要求,而无线IP网络在网络层、链路层存在时变性,使多任务并发执行受到网络带宽瓶颈约束,给多任务调度带来困难。本文分析了网络带宽对任务调度的影响,提出了网络等效带宽的概念及其计算方法。在比较分布式多处理机网络调度算法和单处理机调度算法的基础上,建立了舰艇编队跨平台任务调度模型,提出了最短时限优先扩展算法,该算法能够在考虑网络等效带宽的基础上,较好地计算任务执行时间并分析多任务的可调度性。本文在设计的典型舰艇编队无线IP网络测试环境中,开展了多任务跨平台调度模拟测试,验证了最短时限优先扩展算法设计的合理性以及应用可行性。

参考文献 (14)

目录

    /

    返回文章
    返回