A combinatorial algorithm for message scheduling on controller area networks (Q2505322)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A combinatorial algorithm for message scheduling on controller area networks |
scientific article |
Statements
A combinatorial algorithm for message scheduling on controller area networks (English)
0 references
4 October 2006
0 references
Summary: 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.
0 references
controller area networks
0 references
CANs
0 references
heuristics
0 references
graph algorithms
0 references
real time control
0 references
embedded systems
0 references
combinatorial algorithms
0 references
network optimisation
0 references
message scheduling
0 references
communications networks
0 references