CLC number: TP393
On-line Access: 2016-04-05
Received: 2015-07-21
Revision Accepted: 2015-12-14
Crosschecked: 2016-02-26
Cited: 0
Clicked: 6874
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.
@article{title="A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment",
author="Rui Zhao, Gui-he Qin, Jia-qiao Liu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="17",
number="4",
pages="375-388",
year="2016",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1500232"
}
%0 Journal Article
%T A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment
%A Rui Zhao
%A Gui-he Qin
%A Jia-qiao Liu
%J Frontiers of Information Technology & Electronic Engineering
%V 17
%N 4
%P 375-388
%@ 2095-9184
%D 2016
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500232
TY - JOUR
T1 - A rectangle bin packing optimization approach to the signal scheduling problem in the FlexRay static segment
A1 - Rui Zhao
A1 - Gui-he Qin
A1 - Jia-qiao Liu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 17
IS - 4
SP - 375
EP - 388
%@ 2095-9184
Y1 - 2016
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500232
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.
The paper addresses the scheduling of FlexRay Static Segment, and it presents an ILP based scheduling approach that considers multiple sender slot multiplexing in that segment. I have seen several proposals regarding FlexRay Static Segment, and many of them are based on some optimization technique, since ST scheduling is a combinatorial problem. But I believe that this proposal is an interesting one, since most of recent publications consider only single sender slot multiplexing.
[1]Bertoluzzo, M., Buja, G., Zuccollo, A., 2004. Design of drive-by-wire communication network for an industrial vehicle. IEEE Int. Conf. on Industrial Informatics, p.155-160.
[2]Grenier, M., Havet, L., Navet, N., 2008. Configuring the communication on FlexRay: the case of the static segment. 4th European Congress on Embedded Real Time Software, p.1-18.
[3]Hu, M.L., Luo, J., Wang, Y., et al., 2014. Holistic scheduling of real-time applications in time-triggered in-vehicle networks. IEEE Trans. Ind. Inf., 10(3):1817-1828.
[4]Hua, Y., Liu, X., He, W.B., et al., 2014. Design and implementation of holistic scheduling and efficient storage for FlexRay. IEEE Trans. Parall. Distrib. Syst., 25(10):2529-2539.
[5]International Organization for Standardization, 2013. Road Vehicles—FlexRay Communications System—Part 2: Data Link Layer Specification, ISO 17458-2:2013. International Organization for Standardization, Geneva.
[6]Kang, M., Park, K., Jeong, M.K., 2013. Frame packing for minimizing the bandwidth consumption of the FlexRay static segment. IEEE Trans. Ind. Electron., 60(9):4001-4008.
[7]Lee, K.C., Kim, M.H., Lee, S., et al., 2003. IEEE-1451-based smart module for in-vehicle networking systems of intelligent vehicles. IEEE Trans. Ind. Electron., 51(6):1150-1158.
[8]Lodi, A., Martello, S., Vigo, D., 2004. Models and bounds for two-dimensional level packing problems. J. Combin. Optim., 8(3):363-379.
[9]Lukasiewycz, M., Glaß, M., Teich, J., et al., 2009. FlexRay schedule optimization of the static segment. Proc. 7th IEEE/ACM Int. Conf. on Hardware/Software Codesign and System Synthesis, p.363-372.
[10]Navet, N., Song, Y., Simonot-Lion, F., et al., 2005. Trends in automotive communication systems. Proc. IEEE, 93(6): 1204-1223.
[11]Park, I., Sunwoo, M., 2011. FlexRay network parameter optimization method for automotive applications. IEEE Trans. Ind. Electron., 58(4):1449-1459.
[12]Pop, T., Pop, P., Eles, P., et al., 2008. Timing analysis of the FlexRay communication protocol. Real-Time Syst., 39(1-3):205-235.
[13]Puchinger, J., Raidl, G.R., 2007. Models and algorithms for three-stage two-dimensional bin packing. Eur. J. Oper. Res., 127(3):1304-1327.
[14]Robert Bosch GmbH, 1991. Controller Area Network. Available from http://www.can.bosch.com/ [Accessed on Mar. 22, 2015]
[15]Schmidt, K., Schmidt, E.G., 2008. Message scheduling for the FlexRay protocol: the static segment. IEEE Trans. Veh. Techn., 58(5):2170-2179.
[16]Schneider, R., Goswami, D., Chakraborty, S., et al., 2011. On the quantification of sustainability and extensibility of FlexRay schedules. Proc. 48th Design Automation Conf., p.375-380.
[17]Tanasa, B., Bordoloi, U.D., Eles, P., et al., 2011. Reliability-aware frame packing for the static segment of FlexRay. 9th ACM Int. Conf. on Embedded Software, p.175-184.
[18]Tanasa, B., Bordoloi, U.D., Kosuch, S., et al., 2012. Schedulability analysis for the dynamic segment of FlexRay: a generalization to slot multiplexing. IEEE 18th Real-Time and Embedded Technology and Applications Symp., p.185-194.
[19]Zeng, H.B., Natale, M.D., Ghosal, A., et al., 2011. Schedule optimization of time-triggered systems communicating over the FlexRay static segment. IEEE Trans. Ind. Inform., 7(1):1-17.
Open peer comments: Debate/Discuss/Question/Opinion
<1>