Scheduling the FlexRay bus using optimization techniques

ABSTRACT

FlexRay is a new communication protocol for automotive systems, providing support for transmission of periodic messages in static segments and priority-based scheduling of event-triggered messages in dynamic segments. The design of a FlexRay schedule is not an easy task because of protocol constraints and demands for extensibility and flexibility. We study the problem of FlexRay bus scheduling from the perspective of the application designer, interested in optimizing the performance of application related timing metrics or extensibility. We provide solutions for different task scheduling policies on existing industry standards based on a mixed integer linear programming (MILP) framework.

REFERENCES

• 1: Road vehicles-controller area network (can) part 4: Time-triggered communication. ISO Standard-11898-4, International Standards Organisation (ISO), 2004.
• 2: J. Berwanger, M. Peller, and R. Griessbach. Byteflight - a new high-performance data bus system for safety related applications. http://www.byteflight.com, 2004.
• 3: P. Caspi, A. Curic, A. Maignan, C. Sofronis, S. Tripakis, and P. Niebert. From simulink to scade/lustre to tta: a layered approach for distributed embedded applications. SigPlan Not., 38(7):153--162, 2003.
• 4: S. Ding, N. Murakami, H. Tomiyama, and H. Takada. A ga-based scheduling method for flexray systems. In EMSOFT '05: Proceedings of the 5th ACM international conference on Embedded software, pages 110--113, 2005.
• 5: A. Hagiescu, U. D. Bordoloi, S. Chakraborty, P. Sampath, P. V. V. Ganesan, and S. Ramesh. Performance analysis of flexray-based ecu networks. In DAC '07: Proceedings of the 44th annual conference on Design automation, pages 284--289, 2007.
• 6: A. Hamann and R. Ernst. Tdma time slot and turn optimization with evolutionary search techniques. In DATE '05: Proceedings of the conference on Design, Automation and Test in Europe, pages 312--317, 2005.
• 7: H. Kopetz and I. G. Bauer. The time-triggered architecture. In Proceedings of the IEEE, pages 112--126, 2003.
• 8: P. Pop, P. Eles, and Z. Peng. Schedulability-driven communication synthesis for time-triggered embedded systems. Real-Time Systems, 24:297--325, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design

Keywords:
FlexRay, MILP, automotive, real-time systems, scheduling