Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2016, Vol. 17 Issue (4): 375-388    DOI: 10.1631/FITEE.1500232
    
一种解决FlexRay总线静态段信号调度问题的矩形装箱优化方法
Rui Zhao, Gui-he Qin, Jia-qiao Liu
Department of Computer Science and Technology, Jilin University, Changchun 130000, China; Technology Development Department, FAW-Volkswagen Automotive Company Ltd., Changchun 130000, China  
A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment
Rui Zhao, Gui-he Qin, Jia-qiao Liu
Department of Computer Science and Technology, Jilin University, Changchun 130000, China; Technology Development Department, FAW-Volkswagen Automotive Company Ltd., Changchun 130000, China
 全文: PDF 
摘要： 目的：为解决大量汽车分布式实时应用的数据信号在FlexRay总线静态段的有效调度问题，提出了一种矩形装箱优化方法。该方法在满足每个通信信号时间限制的前提下，可以实现最小化FlexRay总线静态段带宽消耗。
创新点：提出了一种矩形装箱优化方法将强实时车载通信信号以最小的带宽消耗调度在FlexRay总线静态段。提出的方法具备以下三个显著优势：（1）该方法同时支持最新版FlexRay通信协议中两个时隙分配机制，包括单发送时隙复用机制及多发送时隙复用机制（截至目前该方法是第一个使用多发送时隙复用机制进行FlexRay静态段信号优化调度的研究）；（2）该方法创造性地将更小粒度的信号实例作为优化调度的基本单元，允许将不同周期的信号实例调度到相同的时隙上，提高了调度的灵活性，从而大幅度增加了FlexRay静态段带宽的利用率；(3)通过应用特定领域的知识减少了方法的搜索空间，显著提高了该方法的运行效率。
方法：首先，通过举例分析了FlexRay总线单发送时隙复用机制及多发送时隙复用机制对静态段信号优化调度的重要作用（图2和3）。然后，基于整数线性规划方法，将FlexRay总线静态段的信号优化调度问题转换成一个具有诸多特殊限制的矩形装箱问题。提出的方法以最小化静态段使用的时隙的目标，以信号的时间限制、FlexRay协议中相关限制，包括信号打包的限制、单发送时隙复用机制、多发送时隙复用机制等，为约束条件。此外，应用特定领域的知识减少了整数线性规划的搜索空间，大幅度提高了该方法的运行效率。最后，通过大量基于合成信号集及一个真实线控系统信号集的试验，证明了提出的矩形装箱优化方法具有良好的性能。
结论：提出了一种解决FlexRay总线静态段信号调度问题的矩形装箱优化方法。该方法基于整数线性规划，在满足每个信号时间限制的前提下，实现了静态段带宽消耗的最小化。
关键词： FlexRay;  实时应用;  矩形装箱;  优化调度;  时隙复用    
Abstract: As FlexRay communication protocol is extensively used in distributed real-time applications on vehicles, signal scheduling in FlexRay network becomes a critical issue to ensure the safe and efficient operation of time-critical applications. In this study, we propose a rectangle bin packing optimization approach to schedule communication signals with timing constraints into the FlexRay static segment at minimum bandwidth cost. The proposed approach, which is based on integer linear programming (ILP), supports both the slot assignment mechanisms provided by the latest version of the FlexRay specification, namely, the single sender slot multiplexing, and multiple sender slot multiplexing mechanisms. Extensive experiments on a synthetic and an automotive X-by-wire system case study demonstrate that the proposed approach has a well optimized performance.
Key words: FlexRay    Real-time applications    Rectangle bin packing    Schedule optimization    Slot multiplexing
收稿日期: 2015-07-21 出版日期: 2016-04-05
CLC:  TP393  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Rui Zhao
Gui-he Qin
Jia-qiao Liu

引用本文:

Rui Zhao, Gui-he Qin, Jia-qiao Liu. A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment. Front. Inform. Technol. Electron. Eng., 2016, 17(4): 375-388.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1500232    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2016/V17/I4/375

[1] Mei-juan Jia, Hui-qiang Wang, Jun-yu Lin, Guang-sheng Feng, Hai-tao Yu. DGTM：基于动态分组的移动P2P网络信任模型[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 559-569.
[2] Dong-wei Xu, Yong-dong Wang, Li-min Jia, Yong Qin, Hong-hui Dong. 基于ARIMA和Kalman滤波的道路交通状态实时预测[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 287-302.
[3] Shuo Wang, Jiao Zhang, Tao Huang, Jiang Liu, Yun-jie Liu, F. Richard Yu. 流追踪：一种软件定义网络中低开销的时延测量和路径追踪方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 206-219.
[4] Reza Sookhtsaraei, Javad Artin, Ali Ghorbani, Ahmad Faraahi, Hadi Adineh. 基于位置的数据云复制管理器[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1275-1286.
[5] Jun-feng Xie, Ren-chao Xie, Tao Huang, Jiang Liu, F. Richard Yu, Yun-jie Liu. 一种基于博弈论的无线接入网中缓存资源共享方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1253-1265.
[6] Da-fang Zhang, Dan Chen, Yan-biao Li, Kun Xie, Tong Shen. 虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1266-1274.
[7] Gui-lin CAI, Bao-sheng WANG, Wei HU, Tian-zuo WANG. 移动目标防御：现状及特征[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(11): 1122-1153.
[8] Guang-jia Song, Zhen-zhou Ji. 匿名地址解析模型[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(10): 1044-1055.
[9] Adel Khosravi, Yousef Seifi Kavian. 一种用于判断分布式网络中故障节点的自主故障诊断及决策算法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 885-896.
[10] Vignesh Renganathan Raja, Chung-Horng Lung, Abhishek Pandey, Guo-ming Wei, Anand Srinivasan. 软件定义网络组播中一种基于Subtree来进行失败检测和保护的方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 682-700.
[11] Huan-zhao Wang, Peng Zhang, Lei Xiong, Xin Liu, Cheng-chen Hu. 一种安全、高性能的软件定义网络多控制器体系结构[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 634-646.
[12] Peng Xiao, Zhi-yang Li, Song Guo, Heng Qi, Wen-yu Qu, Hai-sheng Yu. 一种K自适应的广域网SDN控制器部署方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 620-633.
[13] Mingjie Feng, Shiwen Mao, Tao Jiang. 利用软件定义网络结构提升未来无线通信网络性能的方法研究与展望[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 606-619.
[14] Gang Xiong, Yu-xiang Hu, Le Tian, Ju-long Lan, Jun-fei Li, Qiao Zhou. 一种基于改进量子遗传算法的虚拟服务部署方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 661-671.
[15] En-zhong Yang, Lin-kai Zhang, Zhen Yao, Jian Yang. 软件定义网络中采用可伸缩视频组播的视频会议系统[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(7): 672-681.