A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment

Rui ZHAO; Gui-he QIN; Jia-qiao LIU

doi:10.1631/FITEE.1500232

Your Location：

Home >

Browse articles >

A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment

Special Issue on Distributed Computing and Artificial Intelligence | Updated：2022-05-19

- A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment
- 一种解决FlexRay总线静态段信号调度问题的矩形装箱优化方法
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 4, Pages: 375-388(2016)
- Affiliations：
  
  1Department of Computer Science and Technology, Jilin University, Changchun 130000, China
  2Technology Development Department, FAW-Volkswagen Automotive Company Ltd., Changchun 130000, China
- Author bio：
  
  E-mail: zhaor1022@163.com
  E-mail: qingh@jlu.edu.cn
  E-mail: jiaqiao.liu@faw-vw.com
- Funds：
- DOI：10.1631/FITEE.1500232
  CLC： TP393
- Received：21 June 2015，
  
  Accepted：14 December 2015，
  
  Published：2016-04
- Accepted：
Scan QR Code
Rui ZHAO, Gui-he QIN, Jia-qiao LIU. A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(4): 375-388.
DOI：

Rui ZHAO, Gui-he QIN, Jia-qiao LIU. A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(4): 375-388. DOI： 10.1631/FITEE.1500232.

摘要

目的

为解决大量汽车分布式实时应用的数据信号在FlexRay总线静态段的有效调度问题，提出了一种矩形装箱优化方法。该方法在满足每个通信信号时间限制的前提下，可以实现最小化FlexRay总线静态段带宽消耗。

创新点

提出了一种矩形装箱优化方法将强实时车载通信信号以最小的带宽消耗调度在FlexRay总线静态段。提出的方法具备以下三个显著优势：（1）该方法同时支持最新版FlexRay通信协议中两个时隙分配机制，包括单发送时隙复用机制及多发送时隙复用机制（截至目前该方法是第一个使用多发送时隙复用机制进行FlexRay静态段信号优化调度的研究）；（2）该方法创造性地将更小粒度的信号实例作为优化调度的基本单元，允许将不同周期的信号实例调度到相同的时隙上，提高了调度的灵活性，从而大幅度增加了FlexRay静态段带宽的利用率；(3)通过应用特定领域的知识减少了方法的搜索空间，显著提高了该方法的运行效率。

方法

首先，通过举例分析了FlexRay总线单发送时隙复用机制及多发送时隙复用机制对静态段信号优化调度的重要作用（图2和3）。然后，基于整数线性规划方法，将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.

关键词

Keywords

references

M Bertoluzzo , , , G Buja , , , A Zuccollo . . Design of drive-by-wire communication network for an industrial vehicle . . 2004 . . IEEE Int. Conf. on Industrial Informatics . . 155 - - 160 . . DOI: 10.1109/INDIN.2004.1417320 http://doi.org/10.1109/INDIN.2004.1417320 . .

M Grenier , , , L Havet , , , N Navet . . Configuring the communication on FlexRay: the case of the static segment . . 2008 . . 4th European Congress on Embedded Real Time Software . . 1 - - 18 . . . .

M.L Hu , , , J Luo , , , Y Wang , , , 等 . . Holistic scheduling of real-time applications in time-triggered in-vehicle networks . . IEEE Trans. Ind. Inf. , , 2014 . . 10 ( ( 3 ): ): 1817 - - 1828 . . DOI: 10.1109/TII.2014.2327389 http://doi.org/10.1109/TII.2014.2327389 . .

Y Hua , , , X Liu , , , W.B He , , , 等 . . Design and implementation of holistic scheduling and efficient storage for FlexRay . . IEEE Trans. Parall. Distrib. Syst. , , 2014 . . 25 ( ( 10 ): ): 2529 - - 2539 . . DOI: 10.1109/TPDS.2013.205 http://doi.org/10.1109/TPDS.2013.205 . .

International Organization for Standardization . . Road Vehicles-FlexRay Communications System-Part 2: Data Link Layer Specification, ISO 17458-2:2013. . . International Organization for Standardization, Geneva . . . .

M Kang , , , K Park , , , M.K Jeong . . Frame packing for minimizing the bandwidth consumption of the FlexRay static segment . . IEEE Trans. Ind. Electron. , , 2013 . . 60 ( ( 9 ): ): 4001 - - 4008 . . DOI: 10.1109/TIE.2012.2208433 http://doi.org/10.1109/TIE.2012.2208433 . .

K.C Lee , , , M.H Kim , , , S Lee , , , 等 . . IEEE-1451-based smart module for in-vehicle networking systems of intelligent vehicles . . IEEE Trans. Ind. Electron. , , 2003 . . 51 ( ( 6 ): ): 1150 - - 1158 . . DOI: 10.1109/TIE.2004.837879 http://doi.org/10.1109/TIE.2004.837879 . .

A Lodi , , , S Martello , , , D Vigo . . Models and bounds for two-dimensional level packing problems . . J. Combin. Optim. , , 2004 . . 8 ( ( 3 ): ): 363 - - 379 . . DOI: 10.1023/B:JOCO.0000038915.62826.79 http://doi.org/10.1023/B:JOCO.0000038915.62826.79 . .

M Lukasiewycz , , , M Glaß , , , J Teich , , , 等 . . FlexRay schedule optimization of the static segment . . 2009 . . Proc. 7th IEEE/ACM Int. Conf. on Hardware/Software Codesign and System Synthesis . . 363 - - 372 . . DOI: 10.1145/1629435.1629485 http://doi.org/10.1145/1629435.1629485 . .

N Navet , , , Y Song , , , F Simonot-Lion , , , 等 . . Trends in automotive communication systems . . Proc. IEEE , , 2005 . . 93 ( ( 6 ): ): 1204 - - 1223 . . DOI: 10.1109/JPROC.2005.849725 http://doi.org/10.1109/JPROC.2005.849725 . .

I Park , , , M Sunwoo . . FlexRay network parameter optimization method for automotive applications . . IEEE Trans. Ind. Electron. , , 2011 . . 58 ( ( 4 ): ): 1449 - - 1459 . . DOI: 10.1109/TIE.2010.2049713 http://doi.org/10.1109/TIE.2010.2049713 . .

T Pop , , , P Pop , , , P Eles , , , 等 . . Timing analysis of the FlexRay communication protocol . . Real-Time Syst. , , 2008 . . 39 ( ( 1-3 ): ): 205 - - 235 . . DOI: 10.1007/s11241-007-9040-3 http://doi.org/10.1007/s11241-007-9040-3 . .

J Puchinger , , , G.R Raidl . . Models and algorithms for three-stage two-dimensional bin packing . . Eur. J. Oper. Res. , , 2007 . . 127 ( ( 3 ): ): 1304 - - 1327 . . DOI: 10.1016/j.ejor.2005.11.064 http://doi.org/10.1016/j.ejor.2005.11.064 . .

Bosch GmbH Robert . . Controller Area Network 1991 . . 2015 Available http://www.can.bosch.com/ http://www.can.bosch.com/ [Accessed on Mar.22, 2015] . .

K Schmidt , , , E.G Schmidt . . Message scheduling for the FlexRay protocol: the static segment . . IEEE Trans. Veh. Techn. , , 2008 . . 58 ( ( 5 ): ): 2170 - - 2179 . . DOI: 10.1109/TVT.2008.2008654 http://doi.org/10.1109/TVT.2008.2008654 . .

R Schneider , , , D Goswami , , , S Chakraborty , , , 等 . . On the quantification of sustainability and extensibility of FlexRay schedules . . 2011 . . Proc. 48th Design Automation Conf. . . 375 - - 380 . . DOI: 10.1145/2024724.2024814 http://doi.org/10.1145/2024724.2024814 . .

B Tanasa , , , U.D Bordoloi , , , P Eles , , , 等 . . Reliabilityaware frame packing for the static segment of FlexRay . . 2011 . . 9th ACM Int. Conf. on Embedded Software . . 175 - - 184 . . DOI: 10.1145/2038642.2038670 http://doi.org/10.1145/2038642.2038670 . .

B Tanasa , , , U.D Bordoloi , , , S Kosuch , , , 等 . . Schedulability analysis for the dynamic segment of FlexRay: a generalization to slot multiplexing . . 2012 . . IEEE 18th Real-Time and Embedded Technology and Applications Symp. . . 185 - - 194 . . DOI: 10.1109/RTAS.2012.10 http://doi.org/10.1109/RTAS.2012.10 . .

H.B Zeng , , , M.D Natale , , , A Ghosal , , , 等 . . Schedule optimization of time-triggered systems communicating over the FlexRay static segment . . IEEE Trans. Ind. Inform. , , 2011 . . 7 ( ( 1 ): ): 1 - - 17 . . DOI: 10.1109/TII.2010.2089465 http://doi.org/10.1109/TII.2010.2089465 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰