Frame packing algorithms for automotive applications

Article type: Research Article

Authors: Saket, Rishi | Navet, Nicolas

Affiliations: Georgia Institute of Technology, College of Computing, Atlanta GA 30332, USA. E-mail: Rishi.Saket@cc.gatech.edu | Loria – Inria, Campus Scientifique – BP 236, 54506 Vandoeuvre-lès-Nancy, France

Note: [] Corresponding author. N. Navet, Tel.: +33 3 54958463; Fax: +33 3 54958401; E-mail: nnavet@loria.fr

Abstract: The set of frames exchanged in automotive applications must meet two constraints: it has to be feasible from a schedulability point of view and it should minimize the network bandwidth consumption. This latter point is important since it allows the use of low cost electronic components and it facilitates an incremental design process. The purpose of this study is to propose efficient algorithms for solving the NP-hard problem of generating a set of schedulable frames that minimize the bandwidth usage. This study presents novel algorithms for building bandwidth-minimizing sets of frames that meet the schedulability requirement. In our experiments, these proposals have proved to be more effective than the existing approaches.

Keywords: Embedded systems, scheduling algorithms, controller area network, heuristics, bandwidth-minimization problems

Journal: Journal of Embedded Computing, vol. 2, no. 1, pp. 93-102, 2006