文章快速检索  
  高级检索
TT-RMS:时间触发网络通信表生成算法
徐晓飞, 曹晨, 郭骏, 刘忠伟    
中国航空无线电电子研究所, 上海 200233
摘要:针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n2),空间复杂度为O(n).目前广泛研究和应用的可满足性理论(SMT)通信表生成方法,其计算时间复杂度通常是多项式级,有时计算时间不收敛.实验结果显示,TT-RMS调度的网络单个链路负载最大可接近100%,计算时间在1 ms左右,平均可调度网络负载是SMT方法可调度网络负载的两倍.TT-RMS通信表生成算法具有计算时间短,可调度消息负载多等优点,可以更好地满足航空航天复杂系统中上千条实时消息流的调度需要.
关键词RMS调度机制     时间触发网络     通信表生成     可满足性理论     实时通信    
TT-RMS: Communication table generation algorithm of time-triggered network
XU Xiaofei , CAO Chen, GUO Jun, LIU Zhongwei     
China Aeronautical Radio Electronics Research Institute, Shanghai 200233, China
Abstract:According to the characteristic of communications in time-triggered network, which is data communication being triggered by a global clock, a rate monotonic scheduling (RMS) based time-triggered communication table generation algorithm was proposed, which was used to generate configurable communication schedule in the time-triggered network. The scheduling of message timeslots in time-trigger RMS (TT-RMS) algorithm included calculating link load by message period, sorting messages by RMS mechanism according to link load and message period, determining sequences of message transmission, and scheduling messages by timeslots, which optimized scheduling process. The time complexity of the TT-RMS was O(n2). And the space complexity was O(n). The time complexity of the widely used satisfiability modulo theories (SMT) method was polynomial, which did not converge sometimes. The experiment results show that to a single link, maximum bandwidth of the TT-RMS algorithm is approximate to 100% and the computing time is close to 1 millisecond. The average schedulable traffic bandwidth is twice of using SMT. The TT-RMS has better performances on computing time and schedulable traffic bandwidth, which could better satisfy the application of complex aeronautic and aerospace system which has thousands of real-time traffic in network.
Key words: rate monotonic scheduling (RMS) mechanism     time-triggered network     communication table generation     satisfiability modulo theories (SMT)     real-time communication    

时间触发网络(time-trigger network)可避免数据帧争用物理链路,保证了网络实时性[1, 2].时间触发网络强实时特性[3, 4, 5, 6],可以满足工业实时通信的需要,在新一代航空航天通信系统中得到了广泛的应用.时间触发网络中所有消息通信都基于离线生成的通信表来驱动.通信表的质量直接决定了网络可传输消息的负载.通信表的生成结果与配置表生成的计算机运行环境无关,只与通信配置表生成方法有关.由于受到网络拓扑结构和应用消息的约束,交换网络的时间触发通信表生成算法是NP(Non-deterministic Polynomial)完全问题.文献[7, 8]研究的通信调度算法基于广播网络的单资源调度,文献[9, 10, 11, 12]研究的通信调度算法也都基于单资源调度.TTE(Time-Trigger Ethernet)网络是一种基于以太网的交换式时间触发网络,目前得到较广泛的研究. 交换式时间触发网络调度是多资源调度问题,文献[13, 14, 15, 16]提出采用SMT(Satisfiability Modulo Theories)解决器来实现TTE多资源调度,SMT解决器通过时间自动机技术,采用形式化验证方法,在状态空间中穷尽搜索,来生成通信配置表.为提高搜索效率,文献[13, 14, 15]分别对SMT解决器的调度算法采用了不同的方法进行了优化,但采用优化后的调度算法,网络单个链路调度的负载也都小于90%,目前该方法得到了广泛的研究和工业应用.SMT解决器在状态空间中穷尽搜索将导致消息调度需要花费大量运算时间,算法执行效率低.

1 问题描述及要求

研究的网络结构如图 1所示.每个站点仅与一个交换机的端口相连,具有一个发送链路(Ls)和一个接收链路(Lr).图 1中调度服务器运行通信表生成算法来生成网络通信表,通信表在数据通信之前加载到所有终端和交换机中.采用的资源分配模型如图 2所示,调度的时间单位为基本周期,每一个基本周期用于传输一个周期性实时消息.通信任务重复的基本周期,构成集群周期.图 2的示例中有1条消息周期为4的时间触发消息,1个集群周期包括12个基本周期.消息被安排在周期偏移为0的位置.

图 1 网络结构 Fig. 1 Network architecture

图 2 资源分配模型 Fig. 2 Resource allocation model

本文主要讨论的是在时间触发网络中如何合理、有效地把基本周期分配给时间触发消息的资源调度问题,以实现整个网络中传输消息负载的最大化.每一条消息通信时间的安排,需要同时获得图 1中的发送链路Ls和接收链路Lr.

时间触发消息流模型的定义为N′(Vk,Vl,T,O);Vk为消息源节点;Vl为消息目的节点;T为消息周期;O为周期偏移,即消息周期T中消息N′所在的基本周期.消息N′从网络节点Vk发送到网络节点Vl.

L为网络中所有的通信链路,[Vk,Vl]为网络节点VkVl之间的通信链路,M为所有运行的消息,MiMj分别为第i条和第j条消息,则:

E为所有消息的集群周期,则:

其中:ab分别为消息MiMj当前所在的消息周期,如0,1,2,…,n,n为一个集群周期内消息周期的个数;Mi.TMj.T分别为消息MiMj的消息周期;Mi.oMj.o分别为消息MiMj消息传输的周期偏移.通信表生成算法的目的是根据输入消息Mi的消息源节点、消息目的节点和消息周期,来生成消息对应的周期偏移Mi.o,形成消息的通信表.

本文提出的通信表生成算法以RMS调度机制为基础.做出如下假设:①网络中所有消息都为周期性时间触发消息;②网络的所有通信链路资源都可用,交换机采用存储转发方式;③所有消息都可以在一个基本周期中完成,一个基本周期也仅仅有一个时间触发消息可传输.

2 SMT解决器介绍

SMT解决器[13, 14, 15](SMT solver)可以解决的SMT问题是一阶逻辑范畴,可判定的理论域包括等式与未解释函数、线性算术、位向量以及量化公式等.SMT解决器的核心是SAT(satisfiability)可满足性问题(satisfiability problem).可满足性是对一个以合取范式(Conjunctive Normal Form,CNF)的形式给出的命题逻辑公式进行判断,确定该命题逻辑公式是否存在真值.广泛采用的SAT可满足性判断算法是DPLL(Davis-Putnam-Logemann-Loveland)算法,该算法属于完备性算法,其基本思路是首先把SAT问题转换为CNF范式,而后对CNF范式中的文字进行真值赋值,形成搜索二叉树.通过深度优先搜索方法来搜索生成的二叉树,以找到满足问题的解,确定问题是否可解.单纯的DPLL算法的计算时间复杂度是指数级的,通过加入启发式搜索策略,来减少搜索空间,提高计算效率.目前SMT解决器的平均时间复杂度是多项式级的,但最坏情况下的时间复杂度仍然是指数级的.

基于SMT解决器的SMT通信表生成方法实现时间触发消息调度时,首先把需要调度的消息、网络拓扑结构、消息调度时间约束等内容用形式化的方法,进行抽象描述,生成SMT解决器的输入.SMT解决器根据输入,计算出消息是否能在对应的物理网络中完成资源分配,并生成对应的配置安排.

由于SMT通信表生成方法的计算时间长度具有不确定性.通常用户在使用SMT通信表生成方法时,需要根据消息调度的规模采用人工干预的方法,进行增量迭代计算[15].

3 TT-RMS说明与分析 3.1 TT-RMS通信表生成算法说明

TT-RMS(Time-Trigger Rate Monotonic Scheduling)通信表生成算法根据RMS调度机制,把网络通信资源分配给时间触发网络中的时间触发消息.其基本思路为:根据RMS调度机制,把网络资源(发送链路和接收链路)按照消息优先级顺序,逐一分配给网络中运行的通信消息,若所有消息都可以分配到网络资源,则表示通信表生成成功,否则表示生成失败.

TT-RMS主调度程序如下:

其中:N为消息总数.

TT-RMS调度分为消息排序(Sort_message)和消息RMS调度两个步骤.

消息在排序之前存放在Init_M数组中,函数Sort_message()按照消息周期和链路负载,对存入Init_M数组中的所有消息进行排序:消息周期按照由小到大顺序进行排序,相同周期的消息则按照所在链路负载由大到小顺序进行排序.排序后的消息存入SORT_M数组中.根据RMS调度机制,消息周期小的消息具有更高的调度优先级.RMS函数通过RMS调度机制,对SORT_M中的消息进行调度.

Int RMS(SORT_M)

{

init_time_slot();

For(i=0;i<N;i++){

time_slot=

find_resource(SORT_M[i],Ls,Lr)

Cluster_state=

search_cluster(E,time_slot)

If(time_slot<=0 || Cluster_state<=0)

Return fail;

allocate_time_slot(time_slot);

}

Return successful

}
其中:time_slot为分配的时间槽;Cluster_state为是否能搜索到空闲时间槽.

RMS调度的思路为:对每一条消息SORT_M[i],首先通过函数find_resource,在发送链路Ls和接收链路Lr中寻找可用资源.再通过函数search_cluster确定该资源是否在整个集群周期E内都可用.如果资源搜索成功,则通过函数allocate_time_slot进行资源分配.

发送链路Ls和接收链路Lr的通信资源分别用一个资源数组来表示,资源数组中的每一项对应一个基本周期,可用于传输一个消息帧.初始时,发送链路Ls和接收链路Lr中的资源都尚未分配,对应资源数组的每一项都处于未标记状态,表示资源空闲.在调度中已分配出去的链路资源对应的资源数组项将被标记成已分配状态.函数find_resource通过Ls和Lr资源数组中的资源分配状态,来寻找可用资源.函数search_cluster通过确定该资源在整个集群周期内是否都处于未分配状态,来验证资源是否可用.若寻找到可用资源,则完成消息资源分配.

3.2 配置案例分析

假定一个交换机连接4个节点A、B、C、D,系统集成周期为32.消息流的配置为:

M1(A,B,8)

M2(A,B,16)

M3(A,C,32)
M4(A,D,32)

M5(A,C,16) M6(B,A,8)

M7(B,C,8) M8(B,C,16)

M9(B,D,32)
Ma(C,A,32)

Mb(C,B,8) Mc(C,D,16)

Md(D,A,8) Me(D,B,32)

Mf(D,C,16)
M10(D,C,8)
其中:Md为第d条消息.根据TT-RMS调度算法,上述消息生成的时间触发网络通信表如图 3所示.在图 3中,第d条消息安排在节点D的第3个时间槽发送,在节点A的第4个时间槽接收.

图 3 时间触发网络通信表 Fig. 3 Time-trigger network communication table
3.3 算法复杂度分析

TT-RMS算法主要包括消息排序和消息RMS调度两个部分.

函数Sort_message()进行消息排序的过程是:对网络中的每一条通信消息,按照消息周期和链路负载进行排序,时间复杂度为O(n2).RMS调度中,需要按照每一条消息,在对应的通信链路中寻找一个可用的资源,其时间复杂度为O(n2).综合上述分析,TT-RMS算法的时间复杂度为O(n2).TT-RMS计算过程主要为链表排序操作,空间复杂度为O(n).

SMT通信表生成方法的通常时间复杂度为多项式级,在生成配置表过程中,有时候由于算法的发散,导致成指数级的时间复杂度,需要用人工方式或者超时自动停止方式来停止算法的运行.随着调度消息的增加,SMT方法计算时间的不确定性进一步增加.在利用SMT方法进行时间触发消息配置时,通常都需要根据消息的规模主动进行消息划分或者开发增量调度器,进行迭代计算[13, 15].

SMT方法需要在整个变量空间构成的二叉树中进行深度优先搜索,伴随着搜索过程,还需要进行回溯搜索,空间复杂度与回溯搜索的实现方式有关,通常都大于O(n2).

综上所述:TT-RMS运行时间复杂度小,运行空间复杂度低,可以更好地满足航空航天复杂系统中上千条实时数据流的配置需要.

4 实验环境及结果 4.1 实验环境

1) 计算环境.

计算环境为2GHz的PC机,和文献[13, 15]中的SMT通信表生成方法执行环境中CPU速度类似,存储器为512MB.文献[13]中SMT通信表生成方法运算过程中需要存储器10GB,文献[15]中SMT通信表生成方法的执行环境中存储器为4GB.文中把文献[15]的SMT通信表生成方法测试结果称为SMT1,本文测试的SMT通信表生成方法结果称为SMT2.SMT2测试软件包由TTE工具集提供[16],运行环境与本文提出的TT-RMS计算环境相同.

2) 流量模型.

消息调度的时间单位为基本周期.消息周期介于16~512之间,周期为2的幂次方,例如:消息周期为16、32、64等.在下面的2种流量模型中,消息周期在16~512之间随机分布.

本文实验中采用常见的2种流量模型:均匀流量模型和对角流量模型.文献[15]中采用了均匀流量模型.假定交换机端口数为Np,当前端口号为m,则均匀流量的数据平均分布在网络的所有端口.而对角流量则把2/3的流量分布到第m+1端口(若m+1>Np,则需要取余),其余流量分布到第m+2端口.

3) 与其他调通信表生成方法的比较.

目前TTE网络常用的配置表生成工具基于SMT解决器技术.为更有效地说明本文的测试结果,本文将把TT-RMS调度算法从系统吞吐量和计算时间两个方面,与SMT通信表生成方法进行比较.

4.2 系统吞吐量

随着端口数的不同,可调度的消息数量也不同,图 4给出了TT-RMS可调度消息数与网络规模的关系.图 5为TT-RMS消息负载在各种流量下资源利用率曲线,表 1给出了可调度消息数.从图 4图 5表 1可见:①在均匀流量和对角流量下,TT-RMS调度的消息数接近;②TT-RMS链路资源利用率最大可接近100%,平均达到80%以上,超过了文献[13, 15]中链路资源利用率最大90%的负载;③TT-RMS可调度消息数接近SMT2的两倍.

图 4 可调度消息数与网络规模的关系 Fig. 4 Relationship between scheduled messages and network size

图 5 TT-RMS调度消息负载 Fig. 5 Network throughput schedule of TT-RMS

表 1 可调度消息数比较 Table 1 Scheduling message number comparison
网络规模可调度消息数
SMT2TT-RMS
480152
6120227
8170310

TT-RMS算法在安排消息时间槽过程中,根据链路的消息周期和总负载情况,首先通过RMS机制对消息进行了排序,确定出消息调度的先后顺序,再进行消息调度,优化了消息的调度过程.TT-RMS算法对各种不同的消息流都具有良好的调度效果.而SMT通信表生成方法通常采用的DPLL算法,主要用于通用的SAT可满足性问题的验证,没有针对时间触发网络中消息调度的特点专门进行通信调度优化.SMT通信表生成方法最大可调度消息链路负载为90%,小于TT-RMS的100%最大链路负载.

4.3 计算时间

各种流量下,消息调度的计算时间如表 2所示.表中消息数为相应网络规模下最大可支持的消息量.SMT1的计算时间来自于文献[15],1000条消息最好计算时间大于100s,SMT2在170条消息的情况下计算时间为11s,TT-RMS算法的计算时间都在1ms左右.从表 2中可见,各种流量下,TT-RMS的计算时间都很短,随着消息数量的增加,调度计算时间变化不大,都在1ms左右.而SMT通信表生成方法的计算时间则对消息数量很敏感,随着消息数的增加,调度时间达到分钟级,并呈现爆炸式增长.

表 2 计算时间比较 Table 2 Execution time comparison
消息数计算时间/s
SMT1SMT2TT-RMS
8064<10-3
12086<10-3
1701211<10-3
60060None 10-3
1000180None 10-3
注:None—没有开展该项目的计算.

TT-RMS调度算法的计算过程主要是对消息顺序进行排序,时间复杂度为O(n2).SMT通信表生成方法在运算过程中,需要在整个变量空间构成的二叉树中进行深度优先搜索,伴随着搜索过程,还需要进行回溯搜索,导致执行时间是多项式复杂度.

测试结果和本文第3.3节的算法时间复杂度分析的结论一致.

5 结 论

针对TTE时间触发网络的网络通信表生成问题,提出了一种基于RMS调度机制的时间触发网络离线消息调度算法TT-RMS.

1) 基于RMS调度机制的TT-RMS算法主要运行操作为消息排序,时间复杂度为O(n2),消息调度的计算时间可控,没有调度时间不收敛问题.

2) TT-RMS具有可调度消息负载大,可扩展性好等优点,可支持上千条实时消息的调度,相比目前广泛研究和应用的SMT通信表生成方法,具有明显的优势.

3) 实验结果证明了算法的有效性.TT-RMS算法可以很好地满足航空航天复杂系统中实时消息流的调度需要.

参考文献
[1] 邱爱华,张涛, 顾逸东.面向空间应用的时间触发以太网[J].国防科技大学学报,2014,36(5):117-123. Qiu A H,Zhang T,Gu Y D.Time-triggered Ethernet for space utilization[J]. Journal of National University of Defense Technology,2014,36(5):117-123(in Chinese).
Cited By in Cnki
[2] Lauer M, Mullins J,Yeddes M,et al.Cost optimization strategy for iterative integration of multi-critical functions in IMA and TTEthernet architecture[C]//Proceedings of IEEE 37th Annual Computer Software and Applications Conference Workshops (COMPSACW).Piscataway,NJ:IEEE Press,2013:139-144.
Click to display the text
[3] Zhang L C, Goswami D,Schneider R,et al.Task-and network-level schedule co-synthesis of Ethernet-based time-triggered systems[C]//Proceedings of the 19th Asia and South Pacific Design Automation Conference,ASP-DIC.Piscataway,NJ:IEEE Press,2014:119-124
Click to display the text
[4] 罗安心. 基于时间触发以太网的同步算法研究与实现[D].成都:电子科技大学,2013. Luo A X.Research and implementation synchronization algorithm based on time-trigger Ethernet[D].Chengdu:University of Electronic Science and Technology of China,2013(in Chinese).
Cited By in Cnki
[5] Steiner W, Bauer G,Hall B,et al.Time-triggered communication[M].Boca Raron:CRC Press Inc,2011:88-89.
[6] 郝燕艳,潘瑞, 万小磊.基于TTEthernet的综合电子系统通信网络研究[J].航天器工程,2013,22(6):98-99. Hao Y Y,Pang R,Wan X L.Research of integrated avionics communication network based on TTEthernet[J].Space Engineering,2013,22(6):98-99(in Chinese).
Cited By in Cnki ()
[7] 章磊,祝明,武哲. 无人直升机系统CAN总线应用层协议设计[J].北京航空航天大学学报,2011,37(10):1264-1270. Zhang L,Zhu M,Wu Z.CAN bus application layer protocol design for unmanned helicopter system[J].Journal of Beijing University of Aeronautics and Astronautics,2011,37(10):1264-1270(in Chinese).
Cited By in Cnki (3)
[8] Kang M, Park K,Jeong M-K.Frame packing for minimizing the bandwidth consumption of flex ray static segment[J].IEEE Transaction on Vehicular Technology,2013,60(9):4001-4008.
Click to display the text
[9] Sagstetter F, Lukasiewycz M,Chakraborty S,et al.Schedule integration for time-triggered systems[C]//Proceedings of the 18th Asia and South Pacific Design Automation Conference,ASP-DIC.Piscataway,NJ:IEEE Press,2013:53-58.
Click to display the text
[10] 王振宇,李照瑜. 单层树型网格下独立任务的周期性调度[J].软件学报,2013,24(2):378-390. Wang Z Y,Li Z Y.Scheduling periodic independent tasks on single-level tree grid[J].Journal of Software,2013,24(2):378-390(in Chinese).
Cited By in Cnki (2)
[11] 刘虎球,赵鹏. 一种多核间内存公平调度模型[J].计算机学报,2013,36(11):2192-2198. Liu H Q,Zhao P.A Multi-core fair memory scheduling model[J].Chinese Journal of Computers,2013,36(11):2192-2198(in Chinese).
Cited By in Cnki (3)
[12] Noguero A, Calvo I,Almeida L,et al.A model for system resources in flexible time-triggered middleware architectures[C]//Proceedings of 16th International Conference on Information and Communications Technologies,EUNICE.Berlin:Springer,2012,7479 LNCS:215-226.
Click to display the text
[13] Steiner W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of 31st IEEE Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2010:375-384.
Click to display the text
[14] Steiner W, Dutertre B.SMT based formal verification of a TTEthernet synchronization function in formal methods for industrial critical systems[C]//Proceedings of 15th International Workshop on Formal Methods for Industrial Critical Systems,FMICS.Berlin:Springer,2010,6371 LNCS:148-163.
Click to display the text
[15] Huang J, Blech J O,Raabe A,et al.Static scheduling of a time-triggered network-on-chip based on SMT solving[C]//Proceedings of Design,Automation & Test in Europe Conference & Exhibition, DATE.Piscataway,NJ:IEEE Press,2012:509-514.
Click to display the text
[16] Craciunas S S, Oliver R S,et al.SMT-based task-and network-level static schedule generation for time-triggered networked systems[C]//Proceedings of the 22nd International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery,2014:45-54.
Click to display the text
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0618
北京航空航天大学主办。
0

文章信息

徐晓飞, 曹晨, 郭骏, 刘忠伟
XU Xiaofei, CAO Chen, GUO Jun, LIU Zhongwei
TT-RMS:时间触发网络通信表生成算法
TT-RMS: Communication table generation algorithm of time-triggered network
北京航空航天大学学报, 2015, 41(8): 1403-1408
Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(8): 1403-1408.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0618

文章历史

收稿日期:2014-10-10
网络出版日期: 2015-01-19

相关文章

工作空间