A combinatorial algorithm for message scheduling on controller area networks

摘要

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.