0 引言
随着航空装备系统的功能日益强大,系统承受的负荷持续日渐加重,对系统的可靠性需求不断增加。目前大量的实时系统作为核心关键系统运行着,实时系统的可靠性成为影响整个航空装备系统可靠性的决定性因素。针对实时系统而言,提高实时系统的可靠性的关键是要解决实时系统中的任务调度问题[1]。
能否解决好实时系统中的任务调度问题,使每个任务得以在规定的时限内运行,是实时系统能否得以可靠运行的首要因素[2]。实时系统中的任务根据是否具有周期性可分为周期性任务和非周期性任务,对于周期性任务,目前大量的任务调度算法不断地被提出[3-4],被用于实时系统在峰值负载条件下,保证重要和基本任务满足时限要求。而对于非周期性任务来说,由于其释放时间事先并不知道,这就给任务调度带来了大量的困难。目前国内外专家学者对非周期任务的调度进行了卓有成效的探索。
李延祺等[5]针对星载实时嵌入式系统非周期性任务的调度问题,提出了一种基于计算概率的建模方法和非周期任务调度算法,以解决传统调度算法易陷入局部最优解的问题。柳子来等[6]针对信息物理融合系统中的实时任务存在的调度效率低下和无法满足用户需求的问题,提出了一种基于自适应t分布的改进粒子群实时任务调度算法,达到提高算法收敛速度的目的。王沁等[7]根据任务执行时间估计系统实时性能,应用排队理论,提出了一种基于固定优先级抢占调度算法的非周期实时任务调度模型。Hu等[8]提出了一种用于基于关键性的机器感知的实时任务调度框架,将实时系统调度问题公式化为任务对象的整合合并最优化问题,并为其设计了详细解决方案。
上述方法在系统建模、算法效率、任务完成时间、减少任务失败率等方面做了改进,同时考虑保证系统实时性问题,使得实时系统能够更好地利用系统资源,这些都显著增强了系统的实时调度能力。但是这些方法可以发挥作用的前提是系统上的非周期实时任务已知或者优先级已知,但航空装备实时系统中还存在着大量的突发的、偶发的任务,而针对实时任务量无法预计的偶发型非周期任务,这些方法的效果并不显著。因此提高非周期实时任务执行成功率的关键在于能够对其任务量进行预测,在知悉任务量的情况下,其任务调度模式就和周期性任务有很大的相似之处,用于周期性任务的调度算法就能发挥出其效果。
对于航空装备实时系统来说,由于其飞行控制和火力控制存在一定的程序性,规定动作占了较大部分,相当于一定的时间内的非周期实时任务在一定程度上是类似的,通过统计方法处理可知他们的任务到达时间都遵从某个概率分布A(x)。类似地,一些非周期实时任务的执行时间也是遵从某个概率分布B(x)。从而意味着非周期实时任务从长时间尺度上看其统计行为并不随时间而改变,因此系统中的非周期任务在一定程度上是可以预测的。如果解决了非周期任务的预测问题,非周期任务在未来的执行计划就是可知的,就能像周期任务那样采用现有大量的、成熟的任务调度算法进行任务调度,从而在根本上解决了非周期任务的调度问题[9]。
在非规律数据预测方法的研究上,模糊网络由于其具有良好的自适应性,近年来被广泛用于复杂对象的预测。喻圣等[10]针对传统BP神经网络的不足,提出了一种基于引入惯性量的BP学习算法的模糊神经网络模型用于电力负荷的预测,取得了较为理想的效果。苑文鑫等[11]将T-S模糊神经网络用于对火电厂未来时间脱硝效率的变化的预测,其检测集99%点的相对误差在±0.5%之间,最大误差小于2.5%,预测模型能够较好地反映SCR烟气脱硝效率。但是模糊神经网络需要前期大量的数据进行训练且擅长预测周期性规律较强的数据,对于突发数据较多的实时系统非周期任务,适用效果不佳,而小波神经网络具有自学习能力强、自适应能力强和容错性高的特点,可用于训练数据量较少、突发性程度高的数据预测。
1 基于小波神经网络的预测方法
1.1 小波神经网络
由于航空装备实时系统非周期任务的统计规律不明显,因此需要任务预测算法具有较强的学习能力,且由于实时系统运行速度的要求,需要预测算法具有较快的收敛速度。而小波神经网络的结构和基元是由小波理论确定,其信号前向传播的同时其误差通过神经网络反向传播[12]。相比较传统BP神经网络和其他前向型神经网络而言,小波神经网络具有更强的学习能力,收敛速度更快,精度更高,具有更灵敏的逼近能力和更强势的容错能力,适用于航空装备实时系统对运算速度要求高、灵敏度要求高的要求。小波神经网络的拓扑结构如图1所示。
图1 小波神经网络的拓扑结构
Fig.1 Diagram of stress and strength distributions
图1中X1、X2、…、Xk是小波神经网络的输入参数,Y1、Y2、…、Ym是小波神经网络的预测输出值,ωij为输入层与隐含层的连接权值,ωjk为隐含层与输出层的连接权值。
在输入信号序列为xi(i=1,2,…,k)时,其隐含层输出公式为
(1)
式(1)中: h(j)为隐含层第j个节点的输出值;hj为小波基函数;aj为小波基函数hj的伸缩因子;bj为小波基函数hj的平移因子。
输出层的计算公式为
(2)
式(2)中: h(i)为第i个隐含层的输出值;l为隐含层节点数;m为输出层节点数。
小波神经网络通常采用梯度修正法修正网络权值和小波基函数参数,其修正过程如下:
1) 计算小波神经网络的预测误差
(3)
式(3)中: yn(k)为期望输出;y(k)为小波神经网络预测输出。
2) 根据预测误差e来修正小波神经网络权值
(4)
根据预测误差e来修正小波基函数的系数:
(5)
(6)
式(4)—式(6)中,
是通过网络预测误差计算得到,其计算方法如下:
(7)
(8)
(9)
式(7)—式(9)中, η为网络学习速率。
1.2 人工鱼群算法的改进策略
人工鱼群算法是一种利用生物体视觉能够快速感知大量空间事物的特点而提出的一种基于生物群体智能寻优算法。该算法是通过模拟鱼类在水中一系列追随食物的行为,以达到在搜索域内进行寻优的目的,对于优化小波预测模型参数发挥很好的作用[13-15]。
本文中的小波预测模型中需要优化的参数有3个,分别为输入层与隐含层的连接权值ωij、小波基函数hj的平移因子bj以及小波基函数hj的伸缩因子aj,这3个参数对模型的整体准确性影响较大[16],在传统的小波神经网络中是依据梯度修正法,使预测输出不断逼近期望输出从而达到修正参数的目的。但梯度修正法类似于BP神经网络中的权值修正算法,极易陷入局部最优值,这会给模型的准确性带来不稳定性因素,无法保证模型是最优的。而通过人工鱼群算法来确定参数值,可以避免陷入局部最优值的情况,其根据预测对象数值的特点得出相应最适合的参数值,保证了模型的准确性。
人工鱼群算法的运算行为包括鱼群的初始化、鱼群的觅食行为、鱼群的聚群行为、追尾行为和随机行为[17-18]。
1) 人工鱼群的初始化
首先要为人工鱼群建立运算模型。设人工鱼群中的每条鱼均为一组在给定范围内的随机一维数组。设人工鱼群中鱼的数量为N,将小波神经网络模型中3个待优化的参数设为x、y、z,其范围分别为[x1,x2]、[y1,y2]和[z1,z2],因此要产生一个3行N列的初始人工鱼群,每列中的数值为一条人工鱼的3个待优化的参数。
2) 人工鱼群的觅食行为
该行为类似于实际鱼类倾向于前往食物众多的水域中寻找食物的行为。设一条人工鱼当前的位置状态为Xi,在其感知范围内随机选择一个状态Xj,若在计算极大值过程中有Yi>Yj,则该人工鱼向Xj方向前进一步;若Yi≤Yj,则重新随机选择状态Xj,重新判断是否满足前进条件。计算极小值时方法同理,这样随机选择状态计算的尝试超过一定的次数后,若该人工鱼仍然未找到满足条件的前进方向,则该人工鱼朝任意方向移动一步。
3) 人工鱼群的聚群行为
聚群行为类似于实际鱼类往往向已找到食物的鱼群中心前进,但同时又不希望在食物附近聚集过多鱼类同伴从而造成食物争抢行为。设一条人工鱼当前的位置状态为Xi,搜索该人工鱼一定范围内的人工鱼同伴数量nf及人工鱼群的中心位置Xc,设δ为鱼群的拥挤度,如果Yc/nf>δYi,表明同伴鱼群的中心有充足的食物并且同伴的数量不多因而不会造成过多的食物争抢,则该人工鱼朝同伴的中心位置方向前进一步;否则执行觅食行为。
4) 人工鱼群的追尾行为
追尾行为类似于实际鱼类往往向已找到食物的伙伴位置前进,同时又不希望伙伴附近聚集过多的争抢食物的鱼的行为。设人工鱼当前的状态为Xi,搜索查询该人工鱼一定范围内的伙伴数量nf和伙伴中Yi最大的人工鱼Xj,如果Yj/nf>δYi,表明伙伴Xj的附近食物充足并且食物周围的鱼不多,所以竞争者不多,因此该人工鱼朝伙伴Xj的方向前进一步,否则执行觅食行为。
5) 人工鱼群的随机行为
随机行为类似于实际鱼类当前在没有明确的觅食目标时在水中的随机游动。随机行为指的是人工鱼随机选择一个目标方向并向该方向移动的一种行为,是人工鱼群算法中较为常见的一种行为,可以认为是觅食行为的一个补充,即Xi的下一个位置Xi′为
Xi′ = Xi + r · Visual
(10)
式(10)中: r为[-1,1]区间的随机数,Visual为感知距离范围。
人工鱼群算法改进的小波神经网络任务流量预测模型流程框图如图2所示。
图2 预测模型流程图
Fig.2 The flow chart of forecast model
2 实验案例与分析
2.1 模型建立
实时系统任务流量预测类似于交通流量预测[19],具有高度非线性和不确定性等特点,但在长时间尺度宏观上看,存在一定的时间相关性,因此为实时任务流量预测提供可能。
本案例采用Morlet母小波基函数作为实时任务流量预测的小波基函数,该函数具有较好的时域和频域局部化特征,可以在时间轴和频域轴上精确地定位信号的瞬时特征和频域特征,因此适用于实时系统非周期任务随机性较大、规律难以捕捉的特性。Morlet母小波基函数公式为
y=cos(1.75x)e-x2/2
(11)
研究表明,航空装备实时系统的线程中的某段时刻的非周期任务流量与前几个时段的任务流量密切相关,并且在每个飞行航程内具有准周期的特性。根据航空装备实时系统的任务流量特性设计小波神经网络,该网络由输入层、隐含层和输出层构成。其中输入层的输入为当前时间点的前n个时间点的任务流量;隐含层节点由小波函数构成;输出层输出当前时间点的任务流量。
2.2 实验仿真
在VxWorks航空装备实时系统中的CPCI总线测控系统中采集了连续3天系统忙时负载量较大的连续120分钟的任务流量数据,该时间段存在较高比例的非周期任务,同时在长时间尺度上看也存在一定的规律性。系统每隔15 s记录1次该段时间内的任务流量,3 d共计360 min内一共记录1 440个时间点的任务流量数据。随机抽取其中24 min共计96个点作为待预测验证的数据,其余336 min共1 344个任务流量的数据用于训练小波神经网络,最后用训练好的小波神经网络来预测选定的待预测的96个点的任务流量,将预测到的数据与真实数据作对比,以考核预测模型的准确性。
根据预测对象特点来构建确定小波神经网络结构。本案例采用的小波神经网络结构为4-6-1型:输入层有4个节点,表示预测时间节点前4个时间点的任务流量;隐含层有6个节点;输出层有1个节点即为神经网络预测系统预测出的任务流量。系统初始化数值为:交叉概率为80%,变异概率为0.01,迭代次数为100,染色体和种群数量均为100,权值学习速度为0.001,训练次数为100次。建立2种小波预测模型,一个小波预测模型中的链接权值ωij、小波基函数hj的平移因子bj及伸缩因子aj利用人工鱼群算法优化处理后得到,另一个的相关参数采用常规的梯度修正法修正后得到。
利用Matlab搭建实时任务流量预测系统,对本文中设计的原始小波神经网络的实时系统任务流量预测模型和利用人工鱼群算法进行参数优化改进的实时系统任务流量预测模型进行编程和仿真实验,同时对比目前在非周期数据预测算法中应用效果较好的T-S模糊神经网络模型,建立了基于T-S模糊神经网络的实时系统任务流量预测系统,比较3种模型对同一组样本的预测效果。
为了量化评价模型的预测效果,通过对模型预测结果的平均绝对误差(MAE)、平均绝对百分误差(MAPE)和均方根误差(RMSE)的计算来量化比较3种模型的上述指标。
设实际流量值为xa,神经网络的预测流量值为xf,神经网络预测样本数为n。
平均绝对误差MAE计算公式为
(12)
平均绝对百分误差MAPE计算公式为
(13)
均方根误差RMSE计算公式为
(14)
2.3 结果分析
分别利用训练好的T-S模糊神经网络任务流量预测系统、原始小波神经网络任务流量预测系统和改进的小波神经网络任务流量预测系统按照3.2节的设置进行任务流量预测。3个系统输出的预测结果与实际任务流量的比较结果分别如图3、图4和图5所示。
图3 T-S模糊神经网络模型预测结果
Fig.3 Prediction results of the T-S FNN model
图4 原始小波神经网络模型预测结果
Fig.4 Prediction results of the original WNN model
图5 改进的小波神经网络预测结果
Fig.5 Predicting results of the improved WNN model
从图3预测结果可以看出,基于T-S模糊神经网络的预测模型在实际任务流量值较低时,特别是在0至50左右波动时,误差较大,几乎处于预测失效状态,预测出的值均为60左右,且几乎没有反映出数值的波动。当数值在100以上时,体现出有效的预测,在中等流量数值(即200左右),预测跟随度较好,但在波动时存在一定的预测延时。这是因为T-S模糊模型能够通过学习大量输入数据来选择匹配最适合的隶属函数,因此具有较强的自适应性,但由于前期训练数据中的低流量数据较少,模型无法进行足够的训练,而模糊模型的预测准确度对相关训练数据量的依赖程度较高,达不到一定的数量会导致模型无法有效预测。从图4的预测结果可以看出,原始小波神经网络的预测模型预测的任务流量结果在数值小于100时,预测效果和T-S模糊神经网络类似,处于预测失效状态,在数值超过100时基本上可以预测出流量的起伏,但存在较大的延时误差。这是因为小波模型在某一数值范围宜陷入局部最优解,且对某些范围特别是前期训练数据较少的数值段不敏感,造成预测结果和实际数值的巨大偏差,因此需动态地对小波模型参数进行优化,避免陷入局部最优解而造成精度下降的情况。
图5为经过人工鱼群算法进行小波预测模型参数优化后的预测结果,可以看出无论在实际任务数据量较高还是较低时间点,预测模型均能较好地预测到任务流量的变化,只是在极少数数值突升或者突降的尖峰时间点,预测的跟随性较弱,这是由于前期训练时提供尖峰的任务不够多且存在一些突发的、不可预测的任务所导致。改进的预测模型总体预测数值误差低于10%,由此可见采用基于人工鱼群算法改进的小波神经网络实时系统任务流量预测模型能够比较精确地预测实时任务流量,其准确度要高于未用人工鱼群算法改进的小波神经网络预测模型,且算法相对简单,具有较强的实用性。
利用式(12)—式(14)分别计算3种模型预测系统预测结果的平均绝对误差、平均绝对百分误差和均方根误差,得到的结果如表1所示。
表1 预测模型的评价指标结果
Table 1 Evaluation indexes of forecast model
模型MAPEMAERMSET-S模糊网络0.089 918.22820.970小波模型0.098 119.87123.098改进的小波模型0.045 58.37711.977
通过预测模型的评价指标结果可以看出,改进的小波模型的平均绝对误差、平均绝对百分误差和均方根误差均远小于T-S模糊神经网络模型和原始小波模型,表明了经过人工鱼群算法进行小波预测模型参数优化可以有效地提高模型的预测精度,各项误差均较小,算法精度高。
3 结论
针对航空装备实时系统非周期任务调度的困难,从解决非周期实时任务流量的预测问题为技术突破口,提出一种改进的基于小波神经网络的航空装备实时系统任务流量预测方法,并进行实际实时任务的预测验证实验,得出以下结论:
1) 航空装备实时系统非周期任务从较长的时间尺度上看,大多数任务的到达时间和执行时间均服从一定的概率分布,因此实时系统的非周期任务流量在一定程度上是可以利用神经网络模型进行预测的。
2) 利用人工鱼群算法对小波神经网络模型参数进行优化,可以避免相关参数陷入相应局部最优解,建立的模型的预测效果优于原始的小波神经网络模型及T-S模糊神经网络模型。
[1]宋小庆,王海生,赵梓旭,等.时间敏感网络流量调度机制研究综述[J].兵器装备工程学报,2023,44(1):11-19.SONG Xiaoqing,WANG Haisheng,ZHAO Zixu,et al.Survey on scheduling mechanisms of time-sensitive networking traffic[J].Journal of Ordnance Equipment Engineering,2023,44(1):11-19.
[2]BENVENISTE A,BERRY G.The synchronous approach to reactive and real-time systems[J].IEEE Sensors Journal,2022,22(15):15410-15418.
[3]LI DAN,HU XIAOGUANG.Redundancy and fault-tolerant algorithms for real-time measurement and control systems for weapons equipment[J].ISA Transactions,2017,67(2):398-406.
[4]赵秀嘉,李雷,刘先华.一种保障实时系统时间约束的处理器指令扩展[J].北京大学学报(自然科学版),2023,59(2):179-188.ZHAO Xiujia,LI Lei,LIU Xianhua.Instruction extension ensuring time constraints in real time processor[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2023,59(2):179-188.
[5]李延祺,任海,白亮,等.一种面向节能的星载实时任务动态调度算法研究[J].上海航天,2019,36(3):81-88.LI Yanqi,REN Hai,BAI Liang,et al.An energy-saving oriented dynamic scheduling algorithm forspace-borne real-time tasks[J].AerospaceShanghai,2019,36(3):81-88.
[6]柳子来,王健敏.基于自适应t分布的改进粒子群实时任务调度算法[J].化工自动化及仪表,2020,47(5):393-397,424.LIU Zilai,WANG Jianmin.Real-time task scheduling algorithm of the improved particle swarm based on the self-adaptive t-distribution[J].Control and Instruments in Chemical Industry,2020,47(5):393-397,424.
[7]王沁,袁玲玲,张燕.固定优先级抢占调度算法下非周期任务实时性能研究[J].小型微型计算机系统,2011,32(6):1025-1029.WANG Qin,YUAN Lingling,ZHANG Yan.Research on real-time performance of aperiodic task for fixed priority preemptive scheduling algorithm[J].Journal of Chinese Computer Systems,2011,32(6):1025-1029.
[8]HU Y,LIU S,ABDELZAHER T,et al.Real-time task scheduling with image resizing for criticality-based machine perception[J].Real-Time Systems,2022,58(4):430-455.
[9]李冬予,田小川,刘念,等.基于有限资源并行测试任务调度研究[J].兵器装备工程学报,2021,42(6):219-222,229.LI Dongyu,TIAN Xiaochuan,LIU Nian,et al.Research on parallel test task scheduling based on limited resources[J].Journal of Ordnance Equipment Engineering,2021,42(6):219-222,229.
[10]喻圣,邹红波,余凡,等.模糊神经网络在电力系统短期负荷预测中的应用[J].智慧电力,2018,46(11):88-91,97.YU Sheng,ZOU Hongbo,YU Fan,et al.Application of fuzzy neural network in power short-term load forecasting[J].Smart Power,2018,46(11):88-91,97.
[11]苑文鑫,苑文磊.基于模糊神经网络的SCR脱硝效率预测模型研究[J].自动化仪表,2023,44(4):35-38,42.YUAN Wenxin,YUAN Wenlei.Study of SCR denitrification efficiency prediction model based on fuzzy neural network[J].Process Automation Instrumentation,2023,44(4):35-38,42.
[12]JAN A,HIU C.A wavelet neural network conjunction model for groundwater level forecasting[J].Journal of Hydrology,2011,407(1/4):28-40.
[13]何星,丁有军,宋丽君,等.基于加速鱼群算法的锂离子电池剩余寿命预测[J].兵器装备工程学报,2022,43(2):163-169.HE Xing,DING Youjun,SONG Lijun,et al.Residual life prediction for lithium-ion battery based on accelerating AFSA[J].Journal of Ordnance Equipment Engineering,2022,43(2):163-169.
[14]YUAN M,KAN X,CHI C,et al.An adaptive simulated annealing and artificial fish swarm algorithm for the optimization of multi-depot express delivery vehicle routing[J].Intelligent Data Analysis,2022,26(1):239-256.
[15]马梓元,龚华军,王新华.基于改进人工鱼群算法的无人直升机编队航迹规划[J].北京航空航天大学学报,2021,47(2):406-413.MA Ziyuan,GONG Huajun,WANG Xinhua.Trajectory planning of unmanned helicopter formation based on improved artificial fish swarm algorithm[J].Journal of Beijing University of Aeronautics and Astronautics,2021,47(2):406-413.
[16]周玉萌.基于改进的小波神经网络短时交通流预测模型研究[D].青岛:青岛科技大学,2022.ZHOU Yumeng.Research on short-term traffic flow prediction model optimized by improved wavelet neural network[D].Qingdao:Qingdao University of Science &Technology,2022.
[17]蒋华伟,郭陶,杨震,等.基于离散鲸鱼群算法的物资应急调度研究[J].电子与信息学报,2022,44(4):1484-1494.JIANG Huawei,GUO Tao,YANG Zhen,et al.Research on material emergency scheduling based on discrete whale swarm algorithm[J].Journal of Electronics &Information Technology,2022,44(4):1484-1494.
[18]SABIR Z,BALEANU D,RAJA Z,et al.Computational performances of morlet wavelet neural network for solving a nonlinear dynamic based on the mathematical model of the affection of layla and majnun[J].Fractals,2023,31(2):234001.
[19]ZHANG W,ZHU K,ZHANG S,et al.Dynamic graph convolutional networks based on spatiotemporal data embedding for traffic flow forecasting[J].Knowledge-based Systems,2022,250(17):1-14.