TT-RMS:时间触发网络通信表生成算法

针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n2),空间复杂度为O(n).目前广泛研究和应用的可满足性理论(SMT)通信表生成方法,其计算时间复杂度通常是多项式级,有时计算时间不收敛.实验结果显示,TT-RMS调度的网络单个链路负载最大可接近100%,计算时间在1 ms左右,平均可调度网络负载是SMT方法可调度网络负载的两倍.TT-RMS通信表生成算法具有计算时间短,可调度消息负载多等优点,可以更好地满足航空航天复杂系统中上千条实时消息流的调度需要.      

航空电子WDM网络的实时性能分析

对航空电子波分复用(WDM,Wavelength Division Multiplexing)网络实时性评估问题,采用网络演算理论,提出了一种周期消息在WDM复杂虚拓扑上多跳端对端最大延迟的计算方法.建立了波长路由器WDM网络模型,分析了消息流端对端延迟的组成部分.针对网络演算理论下的WDM网络通信模型,推导了消息经单节点和多节点波长路由器的最大延迟的计算公式.并结合实际航空电子系统对公式进行了修正,解决了突发度过大的问题.最终得到最大延迟的紧密上限.最后在OPNET仿真环境下验证了计算分析方法的有效性.     

令牌传递网络消息优先级的控制

对令牌传递网络按优先级传输消息的机制进行了分析,提出了一种新的令牌旋转定时器初值的计算方法,该方法使网络消息依最大允许的延迟时间从小到大排序,并在一定网络负载下保证所有消息传输的实时性.本算法得出的结果与国外较成熟的工程实例相比有相当的精度,证明本文的分析和算法是合理有效的.      

基于AFDX的航空电子系统可调度性分析

航空电子全双工交换式以太网(AFDX,Avionics Full Duplex Switched Ethernet)是新一代大型飞机机载网络的首选方案,构建其上的航空电子系统应保证强实时应用在时限内完成.针对现有AFDX实时性研究仅给出网络延迟上界的不足,综合考虑了任务的响应时间以及实时消息在AFDX网络中的传输延迟.建立了使用AFDX网络的航空电子系统模型,分析了分布式任务序列的整体时间需求.应用全局分析思想,给出任务序列的最坏情况响应时间,为系统实时性的评价和优化提供了理论依据.仿真结果表明该分析给出了紧凑的任务序列响应时间上界.     

网络分区中混合消息集传输模式的精确配置

针对分布式综合模块化航空电子网络分区方法,指出其对消息传输模式配置存在不确定性;通过形式化描述将问题转化为包括实时性约束、带宽约束、缓存约束的最优化问题;提出了基于遗传模拟退火的传输模式配置算法,以系统的消息端到端延迟均衡为优化目标.通过给出两个具体算例对算法有效性进行了验证,同时比较了本算法与传统遗传算法的性能.对比结果表明,本算法能够解决传输模式的配置问题,尽管计算时间较传统遗传算法高出18.1%,但所得到的适应度值高出28.7%.本算法为网络分区在实际航电系统中的应用提供了参考.     

上面级快速星图匹配算法研究

现有星图匹配算法存在搜索时间慢、算法实时性差的问题。为了满足上面级实时性的要求,文章采用K矢量查找算法来提高查找快速性,选择星对角矩作为星图匹配的特征量,构造星对角矩矢量,采用星棱锥星图匹配算法进行星图识别。最后采用上下位机的形式进行仿真分析,结果表明采用该星棱锥快速星图匹配算法成功率在99%以上,识别时间最长约为100ms,平均时间在15ms以内。该算法能够满足上面级对匹配算法快速性和高精度的要求。     

航空电子AFDX与AVB传输实时性抗干扰对比

为满足未来航电系统音视频信息传输的需求,考虑车载嵌入式系统的候选实时多媒体网络AVB在航电环境中的应用,并对AVB与AFDX的传输进行了对比研究。首先构建AVB与AFDX标准对比;其次提出基于网络演算的AVB和AFDX端到端延迟计算方法;然后通过定义不同的消息传输场景,采用理论方法分析消息传输实时性的干扰要素;最后利用仿真方法予以验证。在典型1 000条虚拟链路的组网规模下,结果显示:AFDX高优先级流量的端到端延迟优于AVB,对于低优先级流量端到端延迟,则AVB和AFDX各有优劣;但受突发的流量影响,在增加50条各0.22 Mbit/s带宽的低优先级流量干扰情况下,高优先级流量平均端到端延迟的变化率在AVB中为0.25%,在AFDX中为0.38%;在增加50条各0.22 Mbit/s带宽的高优先级流量干扰情况下,低优先级流量平均端到端延迟的变化率在AVB中为5.17%,在AFDX中为10.25%。结果表明:时间敏感消息在AVB网络中传输实时性的抗干扰能力优于AFDX。     

光纤通道网络实时性能分析

针对航空电子光纤通道网络的实时性问题,建立了光纤通道的网络演算模型,分析了在交换机不同服务策略下系统各类数据流的延迟上界情况,给出了计算在交换机不同服务策略下各类数据流延迟上限的数学方法.分析结果表明与先到先服务(FCFS,First Come First Service)服务策略相比,非抢占式静态优先级(NPP,Non-Preemptive Priority)服务策略可以降低高优先级数据的延迟上界,能更好地满足高优先级数据的强实时性要求.通过与仿真结果比较可知,仿真结果与此数学方法的分析结果一致,此方法适于分析系统中各类消息的延迟上界情况,可用于光纤通道网络设计和性能评价.      

保证速率的AFDX交换机实时调度算法

针对AFDX(Avionics Full Duplex Switched Ethernet)网络关键技术——交换机实时调度算法,提出一种保证速率的优先级实时调度算法(PRTRG,Priority Real Time sched-uling algorithm based on Rate-Guaranteed),并运用网络演算理论分析了此调度算法的实时性.在AFDX网络典型配置下,与(FIFO,First In First Out)结果进行分析对比,证明PRTRG算法有效地减少了高优先级数据的端到端延迟上界,同时保证了低优先级数据端到端延迟的确定性,并且阻止了数据流拥塞的扩散,在交换机内部实现了流量隔离.     

应用于MIMO-OFDMA下行链路的分组调度算法

提出了一种基于效用函数的应用于多输入多输出正交频分复用接入 (MIMO-OFDMA, Multiple Input Multiple Output-Orthogonal Frequency Division Multiplexing Access )系统下行链路的分组调度算法.该算法在调度时不仅考虑物理层的信道状况,还利用基站发送缓冲区的状态信息和用户反馈回来的ARQ(Automatic Repeat-request)信息来帮助基站做出调度决策.针对系统中多种业务的不同服务质量(QoS,Quality of Service)要求,分别设计了其效用函数,并将调度决策问题转化成一个系统总效用函数值最大化问题.同时考虑到实际的长期演进计划(LTE,Long Term Evolution) 系统中对子载波共享的限制条件,提出了一种可以降低实际复杂度的启发式算法用于求解该最优化问题.仿真结果表明,该算法不但在保证实时业务用户QoS要求方面要好于传统的调度算法,还能获得较好的系统总容量和丢包率性能.     

蜂群无人机自组网多优先级自适应退避算法

针对现有媒质接入控制（MAC）协议退避算法无法为蜂群无人机自组网（FANETs）提供区分服务,且在重负载时性能严重恶化等问题,提出一种多优先级自适应退避算法。采用忙闲因子自适应机制和最优竞争窗自适应机制,根据信道忙闲程度和网络状态参数自适应实时更新各优先级竞争窗口（CW）长度,从而使每次退避的竞争窗口可快速收敛到最佳状态,并实现了多业务区分服务,得到了最优的系统性能。通过建立不同优先级退避过程的三维Markov链模型求解得到了饱和吞吐量下的最优竞争窗自适应因子,并且理论推导了系统吞吐量和平均MAC时延的数学表达式。仿真结果表明,所提算法在重负载时能够实现多优先级区分服务并有效提高系统的吞吐量性能,相比区分业务优先级的自适应退避（PAB）算法和支持QoS的自适应竞争窗口退避算法（Q-ABACW）,性能均有较大提升。      

CICQ结构中逼近work-conserving的分组调度算法

联合输入交叉点排队（CICQ）结构的分组调度算法是一个得到了充分研究的领域,但已有算法在吞吐率和分组平均时延方面与输出排队（OQ）的结果相比,依然不够令人满意,其关键在于OQ交换机可以工作于work-conserving状态。不同于已有的研究,本文提出了以使得交换机最大程度工作于work-conserving状态为目标的新的研究思路,给出并证明了CICQ交换机实现work-conserving状态的充分且必要条件。以此为基础,提出了一种新的CICQ输入调度的算法即交叉缓存队列均衡（CQB）算法,并将经典的最大队长优先（LQF）算法用于输出调度,结合得到CQB-LQF算法。仿真结果显示,与经典的及最新的CICQ分组调度算法相比,CQB-LQF算法显著提高了吞吐率及分组平均时延性能。      

Groebner基方法在LEO卫星网络路由优化中的应用

卫星网络中的服务质量(QoS,Quality of Service)多目标约束路由问题已被证明是一个非确定性多项式完全(NPC,Non-deterministic Polynomial Complete)问题.根据低轨(LEO,Low Earth Orbit)卫星网络拓扑变化有规律、可预知的特点,将Groebner基方法引入满足QoS多目标约束的路由算法中,应用算法前将QoS多目标约束问题转化为单目标约束问题,使它能够被多项式的最短路径优先(SPF,Shortest Path First)路由算法求解,从而通过Groebner基方法解决QoS多目标约束路由问题,保证了QoS参数的有效性.最后,将所提出的算法与启发式算法和最短路径优先算法进行了仿真比较.仿真实验结果表明,Groebner基方法有效降低了星上计算的难度,比传统方法能提供更好的QoS保证.     

基于Work-Conserving的CICQ结构中单组播分组调度算法

基于联合输入交叉队列(CICQ)结构提出了一种新的均衡交叉节点缓存单组播混合调度算法,即单组播交叉缓存均衡(MUCB)算法,该算法不同于现有的基于业务状态如队长和/或等待时间的调度算法,而是尽力使交换机最大程度地工作于工作保持(Work-Conserving)状态,其方法是尽量均衡CICQ交叉节点的缓存占用。同时,算法充分考虑单组播业务差异性及CICQ结构下输入输出调度间的影响关系。仿真结果显示,在不同组播业务比例条件下,与现有CICQ结构中主流的单组播混合调度算法相比,MUCB算法显著提高了单组播业务总体的通过率及分组平均时延性能。     

移动Ad Hoc网络中一种支持QoS的多址接入协议

基于随机竞争和冲突解决的思想,为多跳移动Ad Hoc网络提出了一种支持服务质量(QoS)的多址接入(QMA)协议.将业务负载划分为时延敏感的实时业务和非时延敏感的数据业务.按照该协议,节点在发送业务分组前利用预报突发进行竞争接入,节点按照业务分组时延情况确定预报突发的长度,所发预报突发能持续到最后的节点优先获得接入.同时,具有实时业务的节点可以按照其优先级在更早的竞争微时隙中开始发送预报突发,因而可以比发送数据业务的节点更优先接入信道.最后利用OPNET仿真评估了QMA协议的多址性能,通过与带冲突避免的载波侦听(CSMA/CA)协议比较表明,QMA协议可以提供较高的吞吐量和较低的消息丢失率,并能为实时业务提供较低的时延,从而实现了对多媒体业务的QoS支持.      

面向航空电子云的混合式时间同步算法

针对航空电子云对时间同步的需求,建立了相应的网络模型、时钟模型和延时模型.给出了节点在不同网络状态下的同步操作流程,基于贝叶斯估计对同步消息的接收处理时间进行补偿,结合集中式同步和分布式一致同步机制,提出了混合式时间同步算法.通过仿真实例比较了该算法与传统同步算法的性能.对比结果表明,该算法在具有更高同步精度和最高收敛速度的同时,仍然能够在链路失效率低于50%的情况下维持与传统分布式算法相当的鲁棒性.该算法为解决航空电子云的时间同步问题提供了参考.     

基于累积效应的光交换机分组调度算法

光交换机中的光路重置需要较长的时间,分组调度必须是基于帧的.为提高传输效率帧长通常较大,从而导致了光交换机中特有的分组累积效应.针对该效应,提出一种新的分组调度算法p-LQF(Longest Queue First)+Hold.通过对业务需求矩阵分解得到置换矩阵, 选择匹配占用最大的置换矩阵建立端口匹配.在4×4端口的VOQ(Virtual Output Queue)结构的光交换机中,分别对均匀、非均匀以及对角线的Bernoulli和ON/OFF业务进行了仿真.仿真结果显示该算法对于符合强大数定理的可接入业务能获得100%的通过率,其平均分组时延接近甚至低于主流的LQF+Hold算法,但复杂度更低.该算法能够提供带宽保证以及短期公平性,同时能适应分组的动态到达.      

基于行程累加的目标标记硬件加速算法

针对目标标记算法的长耗时、大延迟严重影响目标跟踪的效果和实时性问题,提出了快速的基于行程累加的目标标记硬件加速算法.通过对像素进行行程编码,按照定义的累加规则对相邻行的行程进行累加运算,避免了标号冲突的发生,无需建立等价表,实现了一遍扫描完成连通域标记和连通域特征的计算.实验结果表明提出的算法资源占用较少,输出延迟小,与软件算法相比具有很高的加速比,有利于后续目标跟踪的高速实时处理.     

低树代价的低轨卫星网络组播算法

为了解决低轨卫星网络中现有典型源组播算法的信道资源浪费问题,提出了一套单核共享树组播算法,即核心群合并共享树(CCST)和加权核心群合并共享树(w-CCST)算法.CCST算法包括动态近似中心(DAC)选核方法和核心群合并组播路径构建方法.在核心群合并方法中,以核节点作为初始核心群,通过核心群和剩余组成员的最短路径方法逐步扩展直至整棵组播树构建完成,从而大大提高了网络带宽利用率.在w-CCST算法中,通过调整加权因子可以适度增大树代价、降低端到端传播时延,以支持某些时延性能要求严格的实时业务.仿真结果说明,CCST算法的树代价性能比其它算法有显著改善,w-CCST算法的端到端传播时延性能好于CCST算法.