Title: A combinatorial algorithm for message scheduling on controller area networks

Authors: Carlos A.S. Oliveira, Panos M. Pardalos, Tania M. Querido

Addresses: School of Industrial Engineering and Management, Oklahoma State University, 322 Engienering North, Stillwater, OK 74078, USA. ' Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA. ' Centro Federal de Educacao Tecnologica, Avenida Maracana 229, Rio de Janeiro, RJ, Brazil

Abstract: A controller area network (CAN) is a special-purpose communications system, used for real time control of embedded components in vehicles and other general purpose automation systems. A combinatorial algorithm based on network optimisation concepts is presented for scheduling messages on a CAN. The message scheduling (CANMS) problem in CAN requires that messages be allocated according to their priorities, to prevent excessive delays on important messages. The CANMS is an NP-hard problem. The objective of the proposed algorithm is to minimise the total time allocated for message occurrences, in order to avoid message loss. A graph construction is employed, transforming the original problem into the problem of finding cliques with restricted size. According to computer experiments conducted on representative instances, low latency schedules can be obtained through the use of the proposed algorithm. The low computational complexity of the procedure presents the possibility of efficiently solving larger instances of this NP-hard problem.

Keywords: controller area networks; CANs; heuristics; graph algorithms; real time control; embedded systems; combinatorial algorithms; network optimisation; message scheduling; communications networks.

DOI: 10.1504/IJOR.2005.007439

International Journal of Operational Research, 2005 Vol.1 No.1/2, pp.160 - 171

Published online: 20 Jul 2005 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article