Abstract
FlexRay is a reliable and hard real-time in-vehicle communication protocol that is strongly promoted by car manufacturers as the de facto standard in the automotive domain. The protocol offers both a time-triggered and an eventtriggered architecture. This paper focuses on the optimal scheduling of the time-triggered component of FlexRay known as the static (ST) segment using a two-dimensional bin-packing technique. To maximize the bandwidth utilization in the ST segment, a fast heuristic as well as an efficient integer linear programming approach are proposed. Our methods directly schedule signals into slots including frame packing, according to signal-based data scheduling and the slot/ cycle multiplexing mechanisms presented by the latest version of the FlexRay protocol. The benefits of our proposed methods are demonstrated by extensive experiments on synthetic and an automotive X-by-wire system case study. An additional test case is examined to emphasize the superior performance of the proposed approach relative to that of existing optimal scheduling approaches.
Similar content being viewed by others
References
FlexRay Consortium (2010). FlexRay Communications Systems Protocol Specification Version 3.0.1, http://www.flexray.com
Führer, T., Müller, B., Dieterle, W., Hartwich, F., Hugel, R. and Walther, M. (2000). CAN Network with Time Triggered Communication, http://www.can-cia.de/fileadmin/cia/files/icc/7/hartwich.pdf
Han, G., Zeng, H. B., Li, Y. P. and Dou, W. H. (2014). SAFE: Security-aware FlexRay scheduling engine. The 18th Design, Automation and Test in Europe Conf. and Exhibition.
Jang, K., Park, I., Han, J., Lee, K. and Sunwoo, M. (2011). Design framework for FlexRay network parameter optimization. Int. J. Automotive Technology 12, 4, 589–597.
Kang, M., Park, K. and Jeong, M. K. (2013). Frame packing for minimizing the bandwidth consumption of the flexRay static segment. IEEE Trans. Industrial Electronics 60, 9, 4001–4008.
Kim, M. H., Lee, S. and Lee, K. C. (2014). Node-based scheduling method for easy migration from CAN to FlexRay in in-vehicle networking systems. Int. J. Automotive Technology 15, 6, 953–959.
Leu, K. L., Chen, Y. Y., Wey, C. L. and Chen, J. E. (2010). Robustness Analysis of the FlexRay System through Fault Tree Analysis. 2011 IEEE Int. Conf. Vehicular Electronics and Safety, 30–35.
LIN Consortium (2010). Local Interconnection Network Specification Package Version 2.2A, http://www.linsubbus.org
Lodi, A., Martello, S. and Vigo, D. (2004). Models and bounds for two-dimensional level packing problems. J. Combinatorial Optimization 8, 3, 363–379.
Lukasiewycz, M., Glaß, M. and Teich, J. (2009). FlexRay schedule optimization of the static segment. 2011 Proc. Int. Conf. Hardware/Software Codesign and System Synthesis, 363–372.
Navet, N., Song, Y., Simonot-Lion, F. and Wilwert, C. (2005). Trends in automotive communication systems. Proc. IEEE 93, 6, 1204–1223.
Pop, T., Pop, P., Eles, P., Peng, Z. and Andrei, A. (2008). Timing analysis of the FlexRay communication protocol. Real-Time Systems, 39, 205–235.
Puchinger, J. and Raidl, G. R. (2007). Models and algorithms for three-stage two-dimensional bin packing. European J. Operational Research 183, 3, 1304–1327.
Robert Bosch GmbH (1991). CAN Specification Version 2.0, http://www.can.bosch.com
Schmidt, E. G. and Schmidt, K. (2009a). Message scheduling for the FlexRay protocol: The dynamic segment. IEEE Trans. Vehicular Technology 58, 5, 2160–2169.
Schmidt, K. and Schmidt, E. G. (2009b). Message scheduling for the FlexRay protocol: The static segment. IEEE Trans. Vehicular Technology 58, 5, 2170–2179.
Specification of the FlexRay Interface (2014). http://www.autosar.org/fileadmin/files/releases/4–2/softwarearchitecture/communication-stack/standard/AUTOSAR_SWS_FlexRayInterface.pdf
Tanasa, B., Bordoloi, U. D., Eles, P. and Peng, Z. (2013). Probabilistic timing analysis for the dynamic segment of FlexRay. The 25th Euromicro Conf. Real-Time Systems, 135–144.
Tanasa, B., Bordoloi, U., Eles, P. and Peng, Z. (2011). Reliability-aware frame packing for the static segment of FlexRay. 2011 Proc. Int. Conf. Embedded Software, 175–184.
Tanasa, B., Bordoloi, U., Kosuch, S., Eles, P. and Peng, Z. (2012). Schedulability analysis for the dynamic segment of FlexRay: A generalization to slot multiplexing. IEEE 18th Real Time and Embedded Technology and Applications Symp., 185–194.
TTTech (2003). Time-Triggered Protocol TTP/C High-Level Specification Document Version 1.1, http://www.tttech.com
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhao, R., Qin, G.H. & Liu, J.Q. Optimal scheduling of the flexray static segment based on two-dimensional bin-packing algorithm. Int.J Automot. Technol. 17, 703–715 (2016). https://doi.org/10.1007/s12239-016-0070-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12239-016-0070-5