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]为网络节点Vk和Vl之间的通信链路,M为所有运行的消息,Mi和Mj分别为第i条和第j条消息,则:
E为所有消息的集群周期,则:
其中:a和b分别为消息Mi和Mj当前所在的消息周期,如0,1,2,…,n,n为一个集群周期内消息周期的个数;Mi.T和Mj.T分别为消息Mi和Mj的消息周期;Mi.o和Mj.o分别为消息Mi和Mj消息传输的周期偏移.通信表生成算法的目的是根据输入消息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
| 网络规模 | 可调度消息数 | |
| SMT2 | TT-RMS | |
| 4 | 80 | 152 |
| 6 | 120 | 227 |
| 8 | 170 | 310 |
表选项
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 | ||
| SMT1 | SMT2 | TT-RMS | |
| 80 | 6 | 4 | <10-3 |
| 120 | 8 | 6 | <10-3 |
| 170 | 12 | 11 | <10-3 |
| 600 | 60 | None | 10-3 |
| 1000 | 180 | None | 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 |
