A combinatorial algorithm for message scheduling on controller area networks
by Carlos A.S. Oliveira, Panos M. Pardalos, Tania M. Querido
International Journal of Operational Research (IJOR), Vol. 1, No. 1/2, 2005

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.

Online publication date: Wed, 20-Jul-2005

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com