一种用于无人机集群发射控制系统调度机制的应用研究

李博, 张盛兵, 张小林, 席博闻, 田云鹏

1.西北工业大学 计算机学院, 陕西 西安 710072;2.西北工业大学 第365研究所, 陕西 西安 710065; 3.空军驻西安地区军事代表室, 陕西 西安 710065

当前，集群无人机作战的理念越来越受到各国军方的重视。集群无人机作战不仅能够增加无人机的打击力度，也能够使各个无人机协同配合达到最佳的战斗性能[1]。集群发射阶段是无人机集群作战的第一阶段。快速、有效地将无人机在短时间内发射升空，直接关系无人机系统在战场上的作战能力和生存能力，其相关技术是无人机集群作战装备研究的重要领域。

本文所研究的无人机集群发射控制系统是一种基于CAN总线的网络控制系统，下文将其简称为发射控制系统。其中指挥控制节点和无人机号位控制节点构成了控制系统的主网络，各个号位控制节点与系统传感器、测量传感器以及执行机构成了子系统。

由于CAN总线数据传输是依据仲裁机制进行的[2]，因此在发射控制系统中，各个节点会对网络带宽等系统资源进行竞争，从而造成网络中数据传输延时或拥塞，甚至可能将低优先级的数据丢弃，从而影响了系统的正常工作。为此，本文中提出了一种基于SnPWFQ机制的调度方法来解决此问题。

1 发射控制系统工作原理分析

在发射无人机集群过程中，发射控制系统的传感器会实时测量系统中各个环节当前状态下的动态数据，并回传给指挥控制节点。发射控制系统网络构架如图1所示。

图1 发射控制系统网络构架

在发射控制系统中指挥控制节点用于控制管理各个号位，即向各个号位控制节点发送指令数据、任务数据、采集数据等。每个子系统由本号位控制节点与传感器、执行机构构成闭环的控制系统。因此，在网络带宽给定的情况下，当集群发射的无人机越多，发射控制系统网络的负担越重，故在网络通信中，普遍采用了网络调度技术。

在发射控制系统中，用于各个子系统自动控制的数据是实时性的，而用于更改系统工作状态、处理意外状态时数据是非实时性的。发射控制系统中设置网络调度机制时，应分别为各种数据分配合适带宽，以实现调度的公平性。同时，在发射控制系统的实时数据时某些数据是有严格的顺序性，即发送端应将数据有序发送，否则接收端会认为数据无效而丢弃。

目前常用的队列调度算法或者动态调度算法[3]，例如WFQ算法[4]、EDF算法[5]及其相关的改进算法等，是以独立性数据为的假设条件，即前一时刻数据和下一时刻数据相关性为零，发送顺序可以颠倒。所以无法直接应用到发射控制系统中。根据发射控制系统中数据的特点，本文提出了一种新的调度机制——SnPWFQ调度机制，以期解决发射控制系统中数据的顺序性、实时性和公平性等调度问题。

2 发射控制网络SnPWFQ调度机制

2.1 调度机制设计

发射控制系统网络调度机制可分为3部分：状态监控模块、动态调度模块、输出调度模块。调度机制的原理如图2所示：

图2 发射控制网络调度机制原理框图

状态监控模块用于接收网络节点拟发送数据的请求，其参数包括网络数据的优先级P，数据的截止期DL，数据的顺序号Sn，发送节点的ID。在状态监控模块中，设置了1个输入缓存FIFO队列，用于存储所接收到的请求发送数据，以避免在调度过程中丢失数据。

数据分类模块用于将发射控制系统中的数据进行分类，并保存在各自的数据队列中。在此模块中设置了4个FIFO队列，分别存储4类发射控制网络数据。4类数据按表1进行分类:

表1 发设控制系统网络数据分类表

队列Q1～Q4分别存储4类优先级的数据,4个队列长度为l,优先级P1>P2>P3>P4。在保存数据时,为了保证数据的实时性,每个队列按照截止期DL从小到大的顺序保存数据。

输出调度模块中设置了输出缓存FIFO队列。模块中FIFO队列通过SnPWFQ调度算法,将请求数据的ID放入输出缓存FIFO队列中,并通过CAN总线发送给所属的节点。在此模块中,输入的参数是各个请求的D和ID,输出为调度的结果。

2.2 SnPWFQ算法设计

2.2.1 WFQ算法实现方法

WFQ是一个基于虚拟完成时间的调度算法,是对GPS(通用处理器共享)调度算法的模拟实现[6]。虽然GPS 算法的服务原则是绝对公平的[7],但由于它是依据理想流模型把数据包分成无穷小的数据元。在发射控制网络中,数据传输的最小单元是完整的数据帧,因此GPS算法是不可能实现的。WFQ算法是通过对GPS算法的改进,在算法中引入了虚拟时间函数和虚拟时钟,并按照 GPS处理过程对每一个分组进行处理,是一个基于虚拟完成时间的调度算法。虚拟时间越小,则优先级越高[8-9]。

WFQ算法带宽分配方法是:假设有事件j,ti表示到达时间,Bj表示通路,事件的权值为φi。V(t)表示虚拟时间,在服务器处于空闲状态的所有时间均置为0。在任意忙碌周期,虚时间都从V(0)开始。V(t)可定义为:

V(0)=0

V(tj-1+τ)=V(tj-1)+τ∑i∈Bjφi

τ≤tj-tj-1,j=2,3…

(1)

设第i个队列中的第k个数据在tk时刻到达,数据长度为Li,k。Si,k表示这个数据开始调度的时间,Fi,k表示这个数据结束调度的时间,ωi为调度器服务事件的速率。对所有的i,定义Fi,0=0,则有下面公式

Fi,0=0

Si,k=max{Fi,k-1,V(tk)}

Fi,k=Si,k+Li,kωi

(2)

在WFQ算法情况下对每帧数据所分配的带宽为

gi=ωi∑Nj=1ωjC

C≥∑Ni=1ωi

(3)

式中,C表示数据调度平均速率。从(2)式、(3)式中可以看出,WFQ算法对数据的调度仅与数据长度和到达时间相关,可以满足数据发送调度的要求,且能保证公平性。但是,WFQ算法并不考虑当前时刻数据的顺序性,因此在实际调度中会将到达的所有数据打乱顺序发送,从而无法满足发射控制网络中,某些顺序性数据发送的需要。并且WFQ是按照各个数据的权值分配带宽,会增大实时数据的排队延时。

2.2.2 SnPWFQ算法

SnPWFQ算法是在WFQ算法的基础上进行改进的产物。在带宽分配时,将数据的队列 优先级Pi和顺序号Sn作为数据速率ω计算的因子。从而将带宽分配计算方法从(3)式变为下式。

gi=ωi∑Nj=1ωjC

C≥∑Ni=1ωi

i∈R

(4)

式中，a为Pi的底数,b为Sn的底数。当数据为无序时,Sn=0;当为有序数据时,Sn则表示数据的顺序号。

由于在控制系统中,队列的优先级与数据的实时性级别相对应,所以,从(4)式中可以看出:在改进后的算法中,ωi与数据优先级指数成正比,与顺序号指数成反比。如果数据无顺序性,则Sn=0时,ωi与顺序号无关。因此在队列Qi中优先级高的数据权值较大,优先级的数据权值较小;在发射控制系统网络中,实时性高的数据权值较大,实时性低的数据权值较小。同理对有序数据而言,顺序号靠后的数据权值较小。于是SnPWFQ机制中,会将实时性较高、顺序号靠前的数据分配更多的带宽。

3 性能分析

3.1 队列数据的公平性

公平性是发射控制系统调度机制性能的重要指标,本文采用队列公平性指数来分析[9],即在发射控制系统中,任意2个队列Qm,Qn在时间段[tk,tk+1]内持续产生等待发送数据,则有:

fi=LiLmin

Si(tk,tk+1)fi-Sj(tk,tk+1)fj≤M

(5)

表明此调度机制具有公平性。其中:Li表示队列中可被成功发送的数据长度,Lmin表示队列中可被成功发送数据的最小长度,M表示公平性指数,Si(tk,tk+1)表示在时间[tk,tk+1]内队列Q发送的数据量。公式(5)的正确性可论证如下。

证明:假设在时间段[tk,tk+1]内队列Qi发送的数据量为Si(tk,tk+1),令tq为队列Qi调度一次的时间,由(4)式可知,在调度机制下,数据发送量小于存储队列Qi, 则有:

Si(tk,tk+1)≤li+(vout-vin)(tk+1-tk)

(6)

(tk+1-tk)=tk+1-tktqtq≤tk+1-tktq+1tq

(7)

将上式代入(6)式得到

Si(tk,tk+1)≤li+(vout-vin)tk+1-tktq+1tq

(8)

因为tq(vout-vin)=Li,所以

Si(tk,tk+1)≤li+tk+1-tktq+1Li

(9)

因为fi=LiLmin,fi>0所以

tk+1-tktq+1Lmin-Lmaxfj≤Sj(tk,tk+1)fj

(10)

代入(9)式得到

Si(tk,tk+1)fi-Sj(tk,tk+1)fj≤lifi+Lmaxfj+Lmin=M

(11)

3.2 队列数据的实时性

在本文的调度机制中,根据公平性论证过程可得到一次调度周期的最长时间为:

Tmax=Lmaxvin-vout+lvin-vout+∑2i=1Livout

(12)

式中:Lmaxvin-vout表示队列Q1中强实时数据的最长调度时间;lvin-vout表示队列Q2周期性数据中的最长调度时间;Livout表示Q3和Q4中非实时的调度时间。由于在发射控制系统中Lmax≤l,vin-vout≤vout,因此在调度过程中,实时数据的调度时间远远小于非实时数据。即

Lmaxvin-vout≤lvin-vout≤∑2i=1Livout

(13)

设D为发射控制系统数据网络调度延时上限,根据(13)式分析结论可知DQ1

4 仿真实验

本文中使用的仿真实验平台是基于MATLAB/Simulink建立瞬态分析环境,同时加载自定义的目标配置模块及CAN模块。通过Simulink 模型生成硬件下可运行的代码,实现对各个网络节点的模拟。指挥控制节点计算机操作系统采用Windows+RTX的架构,各个号位控制节点的微处理器采用Freescale公司的MPC82XX系列处理器,操作系统为VxWorks5.5.1。

4.1 实时性仿真

硬件平台设置如下:共设置10个CAN总线节点,分别模拟了指挥控制节点和9个发射号位节点。CAN总线速率设置为500 kb/s,4类数据长度均为16byte。分别采用本文的调度机制、WFQ算法以及动态EDF算法进行了网络通信实验。

实验方法如下:设置网络中各个节点时钟处于同步状态;在实时性数据报文内容填入节点发送时间tout,最小单位为0.1 ms,接收端接收到数据后在数据报文中填入接收时间tin,仿真软件根据公式d=tout-tin计算延时。本论文分别取指挥控制节点和第3号位节点的延时数据,对比3种调度算法,结果如下:

图3 指挥指控节点数据延时对比

图4 3号位节点数据发送延时对比

图3、图4表明在实时数据传输时,采用本文方法数据传输延时与EDF算法的延时比较接近。而采用WFQ算法,系统延时较大。

4.2 公平性仿真实验

硬件平台设置如下:在仿真系统中设置CAN节点共10个,分别模拟了指挥控制节点和9个发射号位节点,设置CAN总线速率为256 kb/s～1Mb/s的变化范围,网络中4类数据长度均为8 byte,发送周期为20 ms,分别采用本文方法、WFQ算法以及动态EDF算法进行了网络通信实验。通过统计系统数据丢包的情况分析每种算法对公平性的影响。

实验方法如下:系统工作后,所有节点将发送节点号、接收节点号、顺序号和计数周期填入要发送的数据包中;系统工作3分钟,每个接收节点将接收到数据包的顺序号上传给仿真软件进行分析。其中发送端的顺序号位连续计数,从0计数到255,满255后从0重新开始计数,计数周期+1。如果数据包未发送成果则仿真软件无法收到对应的顺序号。

丢包率计算公式为r=∑n/∑m×100%,其中r表示丢包率,m表示所有节点发送报文的数量,n表示系统中报文丢失的数量。本实验中顺序性数据的Snmax=20。以指挥控制节点和3号位节点进行统计和分析,结果如下:

图5 指挥控制节点数据丢失统计分析

从图中可以看出，当网络带宽越高，3种方法法的丢包率越来越小。在带宽较低的情况下，本文方法与WFQ算法的丢包率相差不大，说明本算法在公平性上与WFQ算法相一致。

图6 3号位节点数据丢失统计分析

同时在仿真实验中发现，经WFQ算法和EDF算法调度后的有序数据已无法保持原有的顺序性。在实际应用中，这类数据即使成功传输给接收端，接收端无法正常执行相关动作，从而导致系统无法正常工作。

5 结 论

本文提出了基于优先级和顺序性的SnPWFQ算法，通过理论分析和仿真实验结果表明，此算法能够满足无人机集群发射控制系统中，网络数据的顺序性、公平性和实时性要求，在无人机集群发射应用中有重要意义。但由于本算法是对WFQ算法进行改进而得，因此，仍需要实时更新虚拟时间集合。所以如何简化虚拟时间计算，仍是作者以后的主要研究方向。

参考文献：

[1] 牛轶峰,肖湘江,柯冠岩. 无人机集群作战概念及关键技术分析[J]. 国防科技，2013，35(5)：37-43

Niu Yifeng, Xiao Xiangjiang, Ke Guanyan. Operation Concept and Key Techniques of Unmanned Aerial Vehicle Swarms[J]. National Defense Science & Technology, 2013, 35(5)：37-43 (in Chinese)

[2] 徐超,李正平,汪长勤. 基于CSMA/CD的CAN总线访问的建模与仿真的研究[J]. 仪器仪表学报,2008,29(4):866-869

Xu Chao, Li Zhengping, Wang Changqin. Research on Modeling and Simulation of CAN Bus Access Based on CSMA/CD[J]. Chinese Journal of Scientific Instrument, 2008,29(4): 866-869 (in Chinese)

[3] Hasnaoui S, Bouallegue A. A Proposal Modification of CAN Protocol to Support a Dynamic Priority Policy Being Able to Be Implemented on CAN Fieldbus Controller Components[C]∥Industry Applications Conference, 2000

[4] He Dongzhi , Wang Feiyue, Li Wei. Dynamic Preemption Threshold Scheduling for Specific Real-Time Control Systems[C]∥Proceedings of the 2005 IEEE Networking, Sensing and Control. Tucson Arizona, 2005 :395-400

[5] Magana E, Morato D, Varaiya P. Tuning the Weights in WFQ Schedulers for the Maximization of Carried Best Effort Traffic[C]∥10th International Conference on Telecommunications, 2003: 917-922

[6] 晋晓辉，李建东，刘乃安．WFQ的两种简化实现方法及性能分析[J]．西安电子科技大学学报：自然科学版:2002,29(2):178-195

Jin Xiaohui, Li Jiandong, Liu Naian. Two Simple Implementation Algorithms of WFQ and Their Performance Analysis[J]. Journal of Xidian University, 2002,29(2):178-195 (in Chinese)

[7] 王重钢，隆克平，龚向阳． 分组交换网络中队列调度算法的研究及其展望[J]． 电子学报，2001，29(4) : 553-559

Wang Chonggang, Long Keping, Gong Xiangyang. The Study and Perspective of Queue Scheduling Algorithms in Packet Switching Networks[J]. Acta Elecoronica Sinica, 2001，29(4): 553-559 (in Chinese)

[8] 李秉权，张松，王兆伟,等. WFQ与WRR 调度算法的性能分析与改进[J]. 北京理工大学学报,2015，35(3)：316-320

Li Bingquan, Zhang Song, Wang Zhaowei, et al.,Performance Analysis and Improvement about WFQ and WRR Schedule Algorithm[J]. Transactions of Beijing Institute of Technology, 2015，35(3):316-320 (in Chinese)

[9] Shreedhar M, Varghese G. Efficient Fair Queueing Using Deficit Round Robin[C]∥IEEE/ACM Trans on Networksing,1996