A combinatorial algorithm for message scheduling on controller area networks

Carlos A.S. Oliveira, Panos M. Pardalos and Tania M. Querido

International Journal of Operational Research, 2005, vol. 1, issue 1/2, 160-171

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. (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=7439 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:1:y:2005:i:1/2:p:160-171

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().