Noname manuscript No.
(will be inserted by the editor)

Model Predictive Control under Timing Constraints
induced by Controller Area Networks

arXiv:1503.02300v2 [] 20 Sep 2016

Zhenwu Shi · Fumin Zhang

Received: date / Accepted: date

Abstract When multiple model predictive controllers are implemented on a
shared controller area network (CAN), their performance may degrade due
to the variable timing and delays among messages. The priority based realtime scheduling of messages on the CAN introduces complex timing of events,
especially when the types and number of messages change at runtime. This
paper introduces a novel hybrid timing model to make runtime predictions
on the timing of the messages for a finite time window. Controllers can be
designed using the optimization algorithms for model predictive control by
considering the timing as optimization constraints. This timing model allows
multiple controllers to share a CAN without significant degradation in the
controller performance. The timing model also provides a convenient way to
check the schedulability of messages on the CAN at runtime. Simulation results
demonstrate that the timing model is accurate and computationally efficient
to meet the needs of real-time implementation. Simulation results also demonstrate that model predictive controllers designed when considering the timing
constraints have superior performance than the controllers designed without
considering the timing constraints.

1 Introduction
Modern industrial control applications, such as the automotive control, are
characterized by the use of shared networks to replace excessive wiring. Deterministic timing is crucial in time-critical industrial applications, because
The research work is supported by NSF grants ECCS-0841195 (CAREER), CNS-0931576,
and CMMI-1436284. Authors would like to thank Prof. Haibo Zeng for the discussion of
CAN bus.
Zhenwu Shi and Fumin Zhang
Georgia Institute of Technology E-mail: zwshi, fumin@gatech.edu

2

Zhenwu Shi, Fumin Zhang

uncertainty in timing may cause embarrassing, or even life-threatening, sudden decreases in systems performance. Real-time networks have been developed to support networking with deterministic timing, with the control area
network, or CAN, being the most mature and accepted one [Gmbh 1991,
Zeng et al. 2010]. A CAN connects a number of nodes that are able to send
and receive messages. Each message on the CAN is broadcasted to all nodes,
and only one message can be transmitted at any time. To resolve contention
among multiple messages, the CAN utilizes a media access control protocol
called carrier sense multiple access with bitwise arbitration (or CSMA/BA).
Each message is assigned a unique identifier, which is used as an assigned
priority when contention occurs. Since each identifier is unique, each message
has a unique priority. Therefore, when two or more nodes attempt to send
messages at the same time, the node with the highest priority message will be
granted access to the CAN to transmit, and the other nodes will need to defer
their message transmission until the communication link becomes idle, which
can be detected after receiving a bit field indicating the end of the message
being transmitted. The length of each CAN message can be determined up
to certain accuracy and uncertainties so that the value well approximate the
real timing and there is no randomness in the mechanism to resolve conflicts.
Therefore, the timings of message transmission and reception events on CAN
can be well predicted.
Using CAN to support networked control systems increases flexibility. However, most networked control system designs are usually constrained by limited bandwidth of the communication link, which does not allow message
transmission at an arbitrarily high rate. The CAN based control systems
are no exception. When multiple control loops must share access to a common communication link, the bandwidth must be distributed appropriately
so that all control loops are stable and all achieve a desired level of performance. Hence, one must design both the controller and the distribution
of bandwidth to guarantee stability and optimal and robust performance
[Hespanha et al. 2007, Zhang et al. 2013].
Over the last several decades, hardware and software systems supporting
the CAN have improved significantly, resulting in very reliable message transmission and timing accuracy. Therefore, the probability of packet drops, and
the possible randomness in timing caused by clock drift, can be practically
ignored for controller design. However, since the CSMA/BA used by CAN
is a contention based protocol, it alone cannot provide sufficient control over
the distribution of bandwidth among networked controllers. While the timing
is still deterministic, contention may cause large variations in timing, a phenomenon generally known as jitters [Baruah et al. 1997, Cervin et al. 2003]. If
not handled well, jitters may cause controls to be faulty at unexpected (or
even life threatening) times. These timing variations cannot be ignored by any
controller design. But some jitters happen with small probability, and so are
hard to diagnose [Cervin et al. 2006]. Since the contention based media access
protocol is not sufficient to avoid timing variations, a higher level scheduling
algorithm is often designed to allocate the bandwidth among control loops.

Title Suppressed Due to Excessive Length

3

In [Anta and Tabuada 2009], authors discuss the design of self-triggered controllers that can reduce the number of required messages for control systems,
which can save communication bandwidth for other applications. Also, authors
of [Martı́ et al. 2010] propose an optimal strategy to allocate communication
bandwidth to different control loops implemented on a CAN, and the article [Jeon et al. 2001] analyzes the effect of response time on the control performance. However, these methods cannot completely avoid contention. When
unexpected contention occurs, classical real-time scheduling resolves these contentions by priority based scheduling algorithms [Sha et al. 2004], such as the
popular rate monotonic scheduling (or RMS) and earliest deadline first (or
EDF) algorithms [Liu and Layland 1973].
Model predictive controllers, or MPCs, were originally developed for industrial process control [Clarke et al. 1987, Lee et al. 1994, Richalet et al. 1978].
The success led to a new general approach for controller design that has
been used in many other applications, including vehicle and robot control
[Camacho and Bordons Alba 2004, Grune and Jurgen 2011, Wang 2009]. The
basic idea of model predictive control is to use a model of the physical system
to predict future system behavior over a finite time horizon, starting from each
sampling time where new sensor measurements are available. The control effort in the finite time horizon is computed by solving an optimization problem.
At each sampling time, only the first value of the resulting control is applied to
the plant, and then the entire calculation is repeated at subsequent sampling
time instants. Model predictive control offers a natural way to incorporate
state and control constraints [Mayne et al. 2000] to the design. However, it
requires sufficient online computing resources and computing time. Chemical
process control, where model predictive control has seen great success over
many years, allows for both. While other applications, such as the control
of automobiles or robots, are more constrained in terms of timing and computing resources because of their reliance on (networked) embedded computers [Leen and Heffernan 2002], recent advances in embedded processors show
considerable promise for applying model predictive control in automotive and
robotic applications as well.
Effective MPC designs rely on accurate, high fidelity models of the control
loops. However, the jitters associated with messages on the CAN incur timevarying delays into the control loops. Such time-varying delays make it difficult
to derive a reliable model used by MPC. This challenge may be answered by
the approach of control-scheduling co-design where a controller and the timing
of control related events can be jointly determined. Two categories of methods
exist in the literature: the offline methods and the online methods.
Offline methods perform optimization at an offline design stage [Chantem et al. 2006,
Zhang et al. 2008]. Typically, a scheduling algorithm is first determined, and
then computer simulation is used to generate a sequence of timings of all possible events under the scheduling algorithm. Optimization techniques can then
be applied to tune the parameters of the scheduling algorithm and the controller design until a predefined performance criteria is optimized [Arzen et al. 2000].
Offline methods are feasible. However, they lead to overly conservative designs,

4

Zhenwu Shi, Fumin Zhang

and they are not completely compatible with model predictive control that requires control efforts to be computed online for a finite time window using
predictions. Online methods for handling jitters involve co-designing a schedule of events and a model predictive control at each sampling time for a finite
horizon [Henriksson et al. 2002], which reduce the amount of computation required compared to offline methods since a shorter time window is concerned.
Furthermore, the controllers that are designed in such methods are usually
less conservative than the ones designed with offline methods, because they
only need to compensate for the worst case delay in a relatively short time
window. A key requirement for the online approach is a computationally efficient method to predict the timing of events for the finite horizon used by
the model predictive control. While timing can be computed by simulations
for offline methods, such simulations are too expensive for online methods. To
the best of our knowledge, the existing works do not offer a general method
for accurate timing prediction on real-time networks. For example, the works
[Gaid et al. 2006,Liu et al. 2013] obtain a timing prediction from a lookup table that is generated offline by computer simulation. In [Zhao et al. 2008], the
timing is assumed to be periodic, while [Zhang et al. 2005] models the timing as a Markov process, where the transition probabilities are assumed to
be known. These methods all have certain degrees of inaccuracy that must
be tolerated by a model predictive control design. If a message takes longer
than expected to transmit, or is perturbed by other messages that were not
considered at the design stage so that its deadline is missed, then the schedule
would not adjust for this fault. The work [Shi and Zhang 2013] is perhaps the
first to introduce a deterministic timing model that connects real-time priority
based scheduling algorithms with model predictive control designs. This timing model may be leveraged by model predictive control designs to improve
performance, by better compensating for timing variations, which serves as
the starting point of the work of this paper.
This paper develops a novel methodology that focuses on handling the
timing constraints (e.g. jitters and delays) associated with MPC on CAN. The
major contributions are summarized as below:
– Model. We develop a receding horizon timing model for event-triggered
model predictive control on CAN. Existing real-time scheduling analysis
of the CAN focuses on modeling time-varying delays as either constant
values in worst-case scenarios [Tindell and Burns 1994,Tindell et al. 1995,
Davis et al. 2007] or stochastic variables obeying certain distribution [Zeng et al. 2010].
These results do not provide a process model with sufficient accuracy. Moreover, many control systems nowadays are operating in dynamic and uncertain environments. As a result, the system workload will change accordingly. For instance, some messages on the CAN may need to be removed
in some cases, while new messages may be added in other cases. This variability of messages inevitably further increases delay variation in feedback
control loop. Our model is able to capture the variations of timing caused
by the changes of number of messages, message length, and priorities at

Title Suppressed Due to Excessive Length

5

run-time over a finite time window. This is particularly suitable for model
predictive control.
– MPC design. We propose an effective design for an event-triggered MPC
that incorporates both the timing model and the control loop model to find
the optimal controlling effort under the timing constraints on CAN. Networked model predictive control designs exist for contention based protocols over the Ethernet; see, for example, [Goodwin et al. 2004,Imer et al. 2006,
Liu et al. 2007,Loontang and de Silva 2006,Montestruque and Antsaklis 2004].
However, the Ethernet is very different from the CAN bus, since it does not
offer predictable timing. Therefore, these works cannot be applied directly
to the model predictive control design problem for the CAN bus. Our MPC
design is triggered by the deterministic timing events on the CAN. We have
discovered that a state observer is necessary to estimate the states of the
timing model. An observer with proved convergence is thus incorporated
into the MPC design. The observer and the event triggered MPC controller
design have not appeared in previous works.
– Simulations. We perform simulations to demonstrate that our MPC design can lead to improved MPC performance. The design is compared to
MPC designs without the timing model to show the performance improvement.
To the best of our knowledge, these contributions do not exist in the literatures
reviewed and have not been previously published.
The technical content of the paper is organized as follows. Section 2 first
review the CAN protocol and its message properties. Then a structure for
MPC is introduced, which formulates the co-design problem studied in this
paper. This problem motivates the need for an efficient timing model that is
necessary to enable the co-design. Section 3 then derives the timing model
that is needed to solve the co-design problem. The timing model consists state
vectors, selected to represent the status of all messages on the CAN bus, and
transition rules that determine the values of state vectors over time. Using the
timing model, one can check for schedulability of all messages at significant
moments. Not all states in the state vectors are directly observable on a CAN
bus, Section 4 discusses how to estimate the state vectors in the hybrid timing
model from measurements collected in each CAN node. We rigorously prove
that the algorithm used for estimation converges to the true values of the state
vectors. Section 5 presents the solution of MPC design proposed in this paper.
The timing model is used to determine controller delays so that the MPC can
be determined more accurately than using worst case response times. Section
6 presents simulations to show the effectiveness of our approach. We demonstrate that the timing model is at least as accurate as other simulation based
methods, but significantly reduced computational cost. We also demonstrate
that the co-designed MPC with timing model achieves better tolerance to disturbances in timing than using worst-case timing. For ease of reading, we have
summarized all major notations used throughout the paper in Table 1.

6

Zhenwu Shi, Fumin Zhang

Table 1: Major Notations in Paper
CAN Bus Messages
τn

message chain consisting of sensor and control messages

τn1

1st sub-message of τn , i.e. the sensor message

τn2

2nd sub-message of τn , i.e. the control message

1
Cn

transmission duration of τn1

2
Cn

transmission duration of τn2

1
In
2
In

time for preparing τn1
time for preparing τn2

Tn

sampling interval of τn

Pn

priority of τn

αn

sampling instant of τn

βn

time instant when τn1 finishes transmission

γn

time instant when τn2 finishes transmission

δn

time delay between γn and αn
MPC Control Design

x

state variable of a physical plant

y

output of a physical plant

u

MPC control signal applied on the physical plant

J

cost function for MPC design

Tp

length of MPC prediction horizton

λ

reference trajectory that MPC tracks
Timing Model

N

number of total message chains on the CAN bus

dn

deadline state of a message chain τn

rn

residue state of a message chain τn

on

delay state of a message chain τn

D

deadline state of all message chains, i.e. D = [d1 , · · · , dN ]

R

residue state of all message chains, R = [r1 , · · · , rN ]

O

delay state of all message chains, O = [o1 , · · · , oN ]

ID

index of the message chain being transmitted on CAN

Z

state vector of the model, i.e. Z = [D, R, O, ID]

H

the timing model

2 Problem Formulation
Our main goal is to establish an event-triggered model predictive control design
approach for real-time networks. An “event” is defined as a significant moment
that should be accounted for by the controller. For example, each time a sensor
message finishes transmission, a model predictive controller can be initiated
to leverage the new information. Event-triggered model predictive control fits
nicely with the CAN bus, since the CAN hardware can generate hardware

Title Suppressed Due to Excessive Length

7

interrupts when “end of transmission” events happen. We propose a timing
model so that whenever the model predictive control is triggered by an event,
one can predict the timing of future events within a finite time horizon and
compute control effort accordingly. For example, one can predict when a future
sensor message will arrive and when the corresponding control effort will be
applied, and then compute the control effort for that future time.
Without loss of generality, we make the following technical assumptions
about message transmission and reception on the CAN bus:
1. The CAN bus is reliable such that no error occurs in sending and receiving
messages.
2. At each node, among all messages that are ready for transmission, the
message with the highest priority will be sent first.
These two assumptions are valid in real applications, and have been used in
many theoretical works related to CAN [Tindell et al. 1995, Davis et al. 2007,
Anta and Tabuada 2009].

MPC Controller Node

MPC Controller Node

CAN Bus

Sensor
Node

Actuator
Node

Plant

Sensor
Node

Actuator
Node

Plant

Fig. 1: Multiple Feedback Control Loops Sharing a CAN

2.1 CAN-based Control System
Consider a set of feedback control loops designed to share a CAN as illustrated
in Figure 1. Each feedback control loop utilizes the CAN to send sampled data
from sensors to an MPC controller, and to send control commands from the
MPC controller to actuators. The sensors, MPC controllers, and actuators are
connected to the CAN and are named as sensor nodes, MPC controller nodes,
and actuator nodes. We simplify the design so that each feedback control loop
has one sensor node, one MPC controller node, and one actuator node. This
is not to be considered as only allowing single-input-single-output systems
because multiple sensors can be integrated into a sensor node, and multiple
actuators can be integrated into an actuator node. The following rules are
imposed by this system:

8

Zhenwu Shi, Fumin Zhang

– At the sensor node, a user specified software program samples the state of
the plants, and then combines sampled data into a single sensor message
for transmission;
– At the MPC controller node, upon reception of a sensor message, a user
specified software program extracts sampled data from the sensor message.
The node then computes MPC algorithms, and combines the resulting
control commands into a single control message for transmission;
– At the actuator node, upon reception of a control message, a user specified
software program extracts control commands from the control message.
The node then issues the control on the actuator;
– All control loops are mutually independent, which means that the sensor
messages and control messages of one control loop do not rely on messages
from other loops for computation.
Therefore, we consider two types of messages related to the control: sensor messages and actuator messages. The above rules imply a causality constraint
between sensor and control messages as follows: in each feedback control loop,
a sensor message must be transmitted before the MPC controller starts computing the control law. A control message can only be transmitted after the
control law is computed.
2.2 Message Chains
For causality in each feedback control loop, one requires that the transmission
of a sensor message be followed by the computation of the control effort,
which is then followed by the transmission of a control message. This process
iteratively repeats. Each iteration of this process, beginning from the sampling
of sensor and ending at the actuation, is called an instance, and then the
above process for any n-th feedback control loop is called a message chain
and denoted by τn . Thus, each message chain τn is composed of recurring
instances. Let the indices k = 1, 2, ... indicate each of the recurring instances
in τn for the n-th loop i.e. the k-th instance of τn is denoted by τn [k]. Figure
2 illustrates the timing of a message chain when there is no contention.
Tn [k + 1]

Tn [k]

¿n

®n [k]

Cn1 [k]
¯n [k]

In2 [k+1]

In1 [k+1]

In2 [k]

In1 [k]

Cn1 [k+1]

Cn2 [k]
°n [k]

®n [k+1]

¯n [k+1]

Cn2 [k+1]

°n [k+1]

®n [k+2]

Fig. 2: An Example Message Chain τn when No Contention Occurs
The horizontal line in Figure 2 represents the progression of time. Suppose
that τn [k] starts at the k-th sampling instant αn [k]. The instance τn [k] contains two sub-messages, namely, τn1 [k] and τn2 [k], where τn1 [k] represents the

Title Suppressed Due to Excessive Length

9

sensor message, and τn2 [k] represents the control message. Also, In1 [k] is the
amount of time for the user specified software program on the sensor node to
sample plants and prepare τn1 [k]; Cn1 [k] is the transmission duration of τn1 [k];
βn [k] is the time instant when the transmission of τn1 [k] is completed; In2 [k] is
the amount of time for the user specified software program on the controller
node to extract sensor information, compute the model predictive control, and
prepare τn2 [k]. In2 [k] can be viewed as the worst case execution time over the finite time horizon that our timing model applies. We assume that the constant
value In2 [k] approximate its true executing time well; Cn2 [k] is the transmission
duration of τn2 [k]; γn [k] is the time instant when the transmission of τn2 [k] is
completed; and Tn [k] is the sampling interval between αn [k] and αn [k + 1].
Then βn [k] represents the time when the sensor message finishes transmission,
and γn [k] represents the time when the control message finishes transmission.
Note that the potential randomness and variations in Cn1 [k] and Cn2 [k], which
are caused by the possible bit-stuffing, can be significantly reduced by effectively encoding the original payload [Gianluca et al. 2012]. Even when the
transmission time is NOT completely deterministic, the values of Cn1 [k] and
Cn2 [k] will provide a good approximation of the actual transmission time. Here
again we want to emphasize that the timing model applies to a finite time
horizon only and is updated dynamically as part of the MPC scheme. So the
small (unexpected) variations in the values of Cn1 [k] and Cn1 [k] will be tolerated by the control. There may also exist some general-purpose messages that
are not related to the control, but that share the CAN bus with the feedback control loops. These general-purpose messages can also be represented
by message chains. For example, one can let a message chain τj represent a
general purpose message by choosing Ij2 [k] = 0 and Cj2 [k] = 0. The following
equations are satisfied by the parameters of a message chain when there is no
contention:
βn [k] = αn (k) + In1 [k] + Cn1 [k]
γn [k] = βn [k] + In2 [k] + Cn2 [k]
αn [k + 1] = αn [k] + Tn [k]

(1)

The above equations will not hold when there is contention between messages. Since only one message can be transmitted on the CAN bus at a time,
τn1 [k] and τn2 [k] in τn [k] may not be transmitted immediately after they are
generated. Instead, they have to compete with other messages for access to
the CAN bus, under the CSMA/BA arbitration scheme. The priority of τn [k]
can be represented by Pn [k]. Since each sub-message τn1 [k] and τn2 [k] in τn [k]
may have its own priority, we have
(
Pn1 [k] when τn1 [k] is transmitted
Pn [k] =
(2)
Pn2 [k] when τn2 [k] is transmitted
where Pn1 [k] and Pn2 [k] represent the priorities (identifier fields) of τn1 [k] and
τn2 [k], respectively. We will see in Section 3 that equation (1) will be replaced
by a timing model which is able to answer the challenge.

10

Zhenwu Shi, Fumin Zhang

2.3 MPC Design
MPC is an advanced control algorithm with increasing popularity in applications. It iteratively uses a model of the feedback control loop to predict the
future control strategy over a finite time horizon [Rawlings 2000]. However,
only the first step of the predicted control strategy is implemented. At the
next step, the process of predictions are repeated again, yielding a new control
strategy. Such prediction horizon keeps shifting forward as time propagate.
For the n-th feedback control loop in Figure 1 where n = 1, 2, ..., N , we
assume that the plant is an independent, multiple input multiple output, and
linear time-invariant system
ẋn (t) = Axn (t) + Bun (t)
yn (t) = Cxn (t),

(3)

where un (t) is the control command, yn (t) is the plant output, xn (t) is the
plant state, and A, B and C are matrices of proper dimensions.
CAN based MPC relies on the controller nodes to compute the control
effort un (t) over a finite time window into the future. This finite time window
is called the prediction horizon. When a controller node is triggered by the
end of the transmission of a sensor message in the same feedback control loop,
the time when the sensor reading is obtained will be used as the start time
of the prediction horizon. Denoting this start time by t0 , an estimate x̂n (t0 )
of the state is first obtained by a filtering algorithm. Let the finite prediction
horizon be [t0 , t0 + Tp ], where Tp is the length of the prediction horizon. The
goal of the MPC is to find control commands un (t) that brings the predicted
plant output yn (t) as close as possible to a reference trajectory λn (t) for all
t ∈ [t0 , t0 + Tp ].
A controller is triggered by the end of transmission of sensor messages,
and an actuator node can only take actions when receiving a control message.
Hence, each model predictive controller only needs to generate one control
command for each sensor message received. The resulting control command
is applied to the plant, and remains constant until the next sensor message
triggers the controller again. Time delay exists between the moment when the
sensor takes measurements, and the moment when the actuator implements
the control command. Therefore, the control command un (t) in (3) must be a
piecewise constant function


un (t)=µn [k], t ∈ αn [k]+δn [k], αn [k + 1]+δn [k+1] ,
(4)

where αn [k] is the k-th sampling instant of the sensor as shown in Figure 2, and
µn [k] is the optimal control command that is generated by the model predictive
controller in the sampling interval [αn [k], αn [k+1] ). Also, δn [k] = γn [k]−αn [k]
is the time delay between the sampling time instant αn [k], and the end time
γn [k] of the transmission of the control message, as shown in Figure 2. Let
un represents the piecewise constant control policy, defined by un (t), where
t ∈ [t0 , t0 + Tp ]. If one can perform online prediction of δn [k] for all k that fall

Title Suppressed Due to Excessive Length

11

within the prediction horizon, then the piecewise constant control policy un is
a finite dimensional vector [µn [1], µn [2], ..., µn [k], ...] for all k that fall within
the finite prediction horizon [t0 , t0 + Tp ].
A cost function J(xn (t0 ), un ) can be defined for the model predictive controller to optimize. One typical example of the cost function [Liu et al. 2007]
is
J(xn (t0 ), un )
R t +T 
= t00 p (λn (s) − yn (s))T Q1 (λn (s) − yn (s)) + un (s)T Q2 un (s) ds
+xT (t0 + Tp )Q3 x(t0 + Tp ),

(5)

where Q1 , Q2 , and Q3 are positive semidefinite weighting matrices chosen
by design. The first term in the integral penalizes the difference between the
future plant output and the reference trajectory during the prediction horizon,
and the second term is the control penalty. The last term in the cost function
is the terminal cost that ensures the system is stabilized by the controller. In
(5), yn (t) must be predicted as a function of xn (t) and un (t) for t ∈ [t0 , t0 + Tp ]
through the process model in (3)-(4).
If the delays δn [k] for all tasks, indexed by k, that falls within the interval
[t0 , t0 + Tp ] can be predicted, then the model predictive control design problem
can be formulated as a optimization problem that needs to compute at every
k:
Given xn (t0 ) = x̂n (t0 ) and δn [k], solve min J(xn (t0 ), un )

(6)

un

subject to the following constraints:
un (t) ∈ U, xn (t) ∈ X ,

(6.a)

ẋn (t) = Axn (t) + Bun (t), yn (t) = Cxn (t), and


un (t)=µn [k], t ∈ αn [k]+δn [k], αn [k+1]+δn [k+1] ,

(6.b)
(6.c)

where (6.a) represents the constraints on the control command and the plant
states. The sets U and X are assumed to be known. Equations (6.b) and (6.c)
represent the physical plant in the process model. The physical plant and the
CAN timing model are coupled through the delay δn [k] in (6.c). Note that in
the cost function J(xn (t0 ), un ), yn (t + τ ) for τ ∈ [0, Tp ] must be predicted as
a function of xn (t) and un (t + τ ) for τ ∈ [0, Tp ] through the process model in
Equation (6.b) and (6.c).
If there was no contention on the CAN, the prediction of the time delays
δn [k] would be trivial. In fact, using equation (1), the delay δn [k] = γn [k] −
αn [k] = In1 [k] + Cn1 [k] + In2 [k] + Cn2 [k]. In this special case the MPC design
problem would be the classical problem which would be relatively easy to
solve. We emphasize here that even in this special case, a continuous time
MPC may be preferred than the discrete time one since the δn [k] may be
time-varying.

12

Zhenwu Shi, Fumin Zhang

2.4 The Need of a Timing Model
Real-time scheduling of messages under contention introduces time-varying
delays δn [k] in Equation (6.c). Since MPC design relies on the process model
in Equation (6.b) and (6.c), the accurate prediction of δn [k] is important to
MPC performance. Using the worst case delay would result in poor performance. Figure 3 shows an example of MPC performance under either accurate
or inaccurate prediction of δn [k]. The inaccurate prediction of δn [k] is chosen as a constant delay from the worst-case analysis [Tindell and Burns 1994,
Tindell et al. 1995, Davis et al. 2007] and the accurate prediction of δn [k] is
the actual time-varying delay of δn [k]. The solid line represents the plant output yn (t) and the dashed line represents the reference trajectory γn (t). As we
can see, using an inaccurate δn [k] would lead to an unreliable process model,
which severely degrades the performance of MPC.
Plant Output
Reference

1

Plant Output
Reference

0.8
0.6

0.5
0.4

3

0

0.2

−0.5

y

0

3
−0.2

−1

−0.4
−1.5
−0.6
−2
0.8

−0.8
1

1.2

1.4

1.6

Time−Seconds

(a) Inaccurate prediction

1.8

2

0.8

1

1.2

1.4

1.6

1.8

2

Time−Seconds

(b) Accurate prediction

Fig. 3: MPC performance under two different predictions of δn [k]
MPC procedure treats the delay δn [k] as a timing constraint. The accurate
prediction of δn [k] for messages under contention and priority based scheduling is difficult. To our knowledge, such model does not exist in the previous
literature. To answer this challenge, our contribution is to derive a timing
model that is able to predict the timing constraints on the CAN-based control
systems.
3 The Timing Model
Our goal in this section is to derive a timing model for message chains under
contentions that are resolved via the assigned priorities. This timing model
generates predictions for αn [k], βn [k], and γn [k] for all n and k for a finite
length time window into the future, which will replace equation (1) and then
enable the MPC control design in (6). Using the timing model, all transmission
events, including the start and the end of all sensor and control messages can
be inferred. From these timing information we will be able to estimate the
delays δn [k] that are needed when computing the MPC.

Title Suppressed Due to Excessive Length

13

Due to the time varying delays under contention, a continuous-time MPC
design approach is a natural choice over discrete time MPC. To support the
continuous time MPC, we need to model the scheduled behaviors of message
chains as a (piecewise) continuous function of t. Therefore, we redefine the
message chain characteristics in continuous time domain as follows:
Definition 1 For any message chain τn , an instance τn [k] is active at time t
if and only if it starts before t and its next instance starts after t, i.e. αn [k] <
t < αn [k + 1]. At any time t, τn has only one active instance denoted as τn (t),
i.e.
if αn [k] ≤ t < αn [k + 1] then τn (t) = τn [k]
(7)
Definition 2 At any time t, we define τn1 (t) and τn2 (t) as the first and second
sub-messages in τn (t), i.e.
if αn [k] ≤ t < αn [k + 1], then τn1 (t) = τn1 [k] and τn2 (t) = τn2 [k]

(8)

Based on the above definitions, we can convert the message chain characteristics in Figure 2 into a continuous time description for the active task instance
τn (t). In1 (t) and In2 (t) are the time needed for preparing τn1 (t) and τn2 (t). Cn1 (t)
and Cn2 (t) are the transmission duration of τn1 (t) and τn2 (t). Tn (t) is the sampling interval of τn (t), and Pn (t) is the priority of τn (t). These notations are
summarized in Table 2.
Table 2: Characteristics of a message chain τn
τn (t)
τn1 (t), τn2 (t)
Tn (t)
Pn (t)
1 (t), C 2 (t)
Cn
n
1 (t), I 2 (t)
In
n

Active instance of τn at time t
1st and 2nd sub-messages in τn (t)
Sampling interval of τn (t)
Priority of τn (t)
Transmission duration of τn1 (t), τn2 (t)
Time for preparing τn1 (t), τn2 (t)

The parameters listed in Table 2 are not enough to describe the timing
of message chains on the CAN due to contention. The problem of scheduling
message chains on a CAN shares some similarity with the problem of task
scheduling on a processor. Authors of [Zhang et al. 2013,Shi and Zhang 2013,
Shi and Zhang 2012] introduced a dynamic timing model for the task scheduling problem on a processor. However, scheduling message chains on a CAN is a
more complex problem. First, messages on the CAN are not preemptible while
tasks considered in [Zhang et al. 2013, Shi and Zhang 2013] are preemptible.
Moreover, messages on the CAN are subject to causality constraints while
tasks in [Zhang et al. 2013,Shi and Zhang 2013,Shi and Zhang 2012] are independent. Such increased complexity requires significant extensions to the previous results. We show that the timing model will be a mixed set of continuoustime differential equations and logic equations that describe the evolutions of
states that capture the timing. This model can faithfully describe the timing
of events.

14

Zhenwu Shi, Fumin Zhang

3.1 States of the Message Chains
To model the preempted behaviors among multiple message chains, we introduce some extra parameters called the states for each message chain.
Definition 3 The deadline dn (t), for n = 1, 2, · · · , N , denotes how long after
t the next instance of the nth message chain will start.
Definition 4 The residue rn (t), for n = 1, 2, ..., N , denotes the least remaining time required to finish processing and transmitting the active instance
τn (t) after time t.
Definition 5 The delay on (t), for n = 1, 2, ..., N , denotes the time between
the starting time of τn (t) and the current time t if the active instance τn (t) has
not been fully processed. If the active instance τn (t) has been fully processed
at a time instant before the current time t, then the value of the delay at time
t will be the length of the time interval between the starting time of τn (t) and
the time instant when τn (t) has been fully processed.
Definition 6 The index ID(t) ∈ {1, · · · , N } is the index of the message chain
that is being transmitted on the CAN at time t, where ID(t) 6= 0 implies that
the active instance τID(t) is being transmitted and ID(t) = 0 implies that no
message chain is being transmitted.
To help readers understand these concepts, let us consider the case of a
message chain without contention as shown in Figure 2. Suppose the current
time t = βn [k]. Then the deadline dn (t) = αn [k + 1] − t = αn [k] + Tn [k] − βn [k].
The residue rn (t) = γn [k] − t = In2 [k] + Cn2 [k], and on (t) = t − αn [k] = In1 [k] +
Cn1 [k]. These relationships will be much more complicated under contention.
We can assemble the states of all message chains at time t into a large
row vector Z(t) = [D(t), R(t), O(t), ID(t)] where D(t) = [d1 (t), · · · , dN (t)] ,
R(t) = [r1 (t), ..., rN (t)] and O(t) = [o1 (t), ..., oN (t)]. Our timing model will
determine the value of this row vector Z(t) at any time t.
3.2 Stages of a Message Chain
The residue rn (t) is a key state that indicates how much time is still needed
before the active instance τn (t) will be completely processed. Its value always
starts from In1 (t)+Cn1 (t)+In2 (t)+Cn2 (t) and decreases to 0. During this process,
the active instance τn (t) sequentially goes through seven different stages from
the starting time to completion.
– Stage 1: the first sub-message τn1 (t) is being prepared. At this stage,
ID(t) 6= n, the residue of τn (t) satisfies that Cn1 (t) + In2 (t) + Cn2 (t) <
rn (t) ≤ In1 (t) + Cn1 (t) + In2 (t) + Cn2 (t).
– Stage 2: τn1 (t) is waiting for access to the CAN. At this stage, ID(t) 6= n,
the residue stays unchanged: rn (t) = Cn1 (t) + In2 (t) + Cn2 (t).

Title Suppressed Due to Excessive Length

15

– Stage 3: τn1 (t) is being transmitted on the CAN. At this stage, ID(t) = n,
the residue satisfies that In2 (t) + Cn2 (t) < rn (t) < Cn1 (t) + In2 (t) + Cn2 (t).
– Stage 4: the second sub-message τn2 (t) is being prepared. At this stage,
ID(t) 6= n, the residue satisfies that Cn2 (t) < rn (t) ≤ In2 (t) + Cn2 (t).
– Stage 5: τn2 (t) is waiting for access to the CAN bus. At this stage, ID(t) 6=
n, the residue stays unchanged e.g. rn (t) = Cn2 (t).
– Stage 6: τn2 (t) transmitting on the CAN bus. At this stage, ID(t) = n, the
residue satisfies that 0 < rn (t) < Cn2 (t).
– Stage 7: τn2 (t) is finished. At this stage, ID(t) 6= n, the residue stays
unchanged e.g. rn (t) = 0.
Whenever a new instance of τn arrives, it will go from Stage 7 back to Stage
1 and repeat the above process. Note that these stages are for one specific
message chain. Multiple message chains may stay in different stages at any
given time.
Suppose the active instance of message chain τn (t) is marked by the index k.
The dynamic deadline dn (t) starts from the initial value Tn [k] and continuously
decreases as time propagates, regardless of which stage the message chain is
in. Hence we have that
d˙n (t) = −1,
(9)
with initial value dn (αn [k]) = Tn [k]. But after the value of dn (t) decreases to
0, this indicates that a new instance of the message chain arrives. Then the
message chain goes from Stage 7 back to Stage 1, and dn (t) will jump from 0
to a new value Tn [k + 1].
The residue rn (t) starts from the initial value rn (αn [k]) = In1 [k] + Cn1 [k] +
2
In [k] + Cn2 [k]. In Stages 2, 5, and 7, the residue satisfies ṙn (t) = 0. In Stages 1,
3, 4, and 6, the residue decreases homogeneously e.g. ṙn (t) = −1. The value of
rn (t) will jump from 0 to a new value In1 [k +1]+Cn1 [k +1]+In2 [k +1]+Cn2 [k +1]
when a new instance of message arrives e.g. the message chain goes from Stage
7 back to Stage 1.
The delay on (t) starts from initial value 0 at the starting time αn [k] e.g.
on (αn [k]) = 0. Whenever the value of the residue is not 0 e.g. rn (t) > 0, the
delay increases homogeneously as ȯn (t) = 1. In other words, the delay keeps
increasing at Stages 1-6. The delay on (t) stops increasing at Stage 7 since the
active instance of the message chain has been fully processed. When a new
message instance arrives e.g. the message chain goes from Stage 7 back to
Stage 1, the delay on (t) is reset to 0.
The index ID(t) keeps constant until a change of access to the CAN happens. Since the CAN only transmits one message at a time, we have the following claim.
Claim Consider a set of message chains {τ1 , · · · , τN }. At any time t, at most
one message chain from {τ1 , · · · , τN } can stay at Stage 3 or Stage 6, but
multiple message chains can stay at other stages at the same time.

16

Zhenwu Shi, Fumin Zhang

The massage chain that is in Stage 3 or Stage 6 at the time t will be the
message indicated by the value of ID(t). On a real CAN implementation, this
value is known to all message chains due to the broadcasting mechanism used
by the CAN. When one of the message chains is at Stage 3 or Stage 6, all other
message chains will remain at Stages 1, 2, 4, 5, or 7. Since our goal is to derive
a model for the CAN, we need to determine and predict the value of the state
variable ID(t) from the priorities Pn (t). Let us suppose that a change of access
to the CAN happens at a time instant t0 . From the values of the residue, we
know which stage each message chain is at. Then the message that has access
to the CAN will be the message with the highest priority among all messages
that are either at stage 2 or stage 4 at time t0 . Therefore
ID(t0 ) =

argmin

Pi (t0 ).

(10)

{i|τi in Stages 2 or 4, at t0 }

We enforce the convention that if the set {i|τi in Stages 2 or 4, at t0 } is empty,
then ID(t0 ) = 0. Note that this equation does not hold for all t since the messages are non-preemptive. Therefore, to complete the timing model, we need
to pinpoint the time instants when a change of access to the CAN happens.
As we see the evolution of Z(t) is relatively straightforward within each
stage. What remains to do is to discover the length of each stage for each
message chain. The length of Stages 1, 3, 4, and 6 are known due to the
homogeneous decreasing of the residue rn (t). But the length of Stages 2, 5,
and 7 can not be directly determined from the residue because it relies on
knowing which message chain holds the access to the CAN.
3.3 Significant Moments
Let the current time be t, suppose the vector Z(t) is completely known. We
need to predict the value of Z(t+s) at a future time instant t+s. We know that
the values of Z(t+s) will evolve continuously within each stage. However, since
the message chain that has access to the CAN will change, and new instance
of messages will arrive, the values of Z(t + s) will not evolve continuously in
between different stages, but will rather have jumps. The moments when these
jumps happen are of more significant value than other time instants.
Definition 7 At time t, we define the next significant moment as the time
instant t + S(t) where the state vector Z(t) = {D(t), R(t), O(t), ID(t)} evolve
continuously within the time interval [t, t + S(t)), but sees a jump in one of
the components of Z(t) at time instant t + S(t).
The state vector {D(t), R(t), O(t), ID(t)} evolves continuously most of time
except in two situations: (1) a new message accesses the CAN and starts
transmission, i.e. the message chain transits from Stage 2 to Stage 3 or from
Stage 5 to Stage 6; and (2) a new instance of a message chain arrives, i.e.
the message chain transits from Stage 7 to Stage 1. In the first situation,
ID(t) will have a jump; and in the second situation, components of the vector

Title Suppressed Due to Excessive Length

17

{D(t), R(t), O(t)} will have a jump. At the current time t, the value of S(t) is
the time-interval between t and the first time instant when a jump happens.
3.3.1 A new message chain gaining access to CAN
At the current time t, we want to know how long after t a new message will
gain access to the CAN. Depends on whether the CAN is busy or idle at the
current time t, we will have four different cases. To simplify the notation, we
use τID to denote τID(t) in the following part of this paper, unless otherwise
specified.
First, suppose that the CAN bus is busy at time t, i.e. ID(t) 6= 0, which
implies that τID is currently being transmitted on the CAN. As discussed in
Section 3.2, we know that τID at current time t falls into either Stage 3 or Stage
6.
Case 1: τID at Stage 3 when the residue rID (t) satisfies the following condition
II2D (t)+CI2D (t) < rID (t) < CI1D (t) + II2D (t) + CI2D (t)

(11)

1
In this case, τID will stay within Stage 3 before τID
finishing transmission. Hence
the next significant moment will happen no later than the moment when the
2
2
(t)].
(t)+CID
transmission finishes. Therefore, S(t) ≤ rID (t)−[IID

Case 2: τID at Stage 6, i.e. the residue rID (t) satisfies the following condition
0 < rID (t) < CI2D (t)

(12)

2
finishing transmission. No
In this case, τID will stay within Stage 6 before τID
2
other message will gain access to the CAN before τID
finishing transmission.
Then S(t) ≤ rID (t).

Based on the above two cases, let us define S1 (t) as the following
 2

2
S1 (t) = rID (t)− IID
(t)+CID
(t) sgn(max{0, rID (t)−CI2D (t)}).

(13)

Since the CAN can only transmit one message and the transmission is nonpreemptive, it has to wait at least S1 (t) amount of time before a new message
can access to the CAN. Then the next significant moment for τID (t) will be at
t + S(t) where S(t) ≤ S1 (t).
Next, we suppose that the CAN is idle at time t, i.e. ID(t) = 0, which
implies no message is currently being transmitted on the CAN. In other words,
all message chains are preparing sub-messages at current time t. In this case,
any message chain τn from {τ1 , · · · , τN } falls into either Stage 1, 2, 4, or 5.
But if there is a message at stage 2 or stage 5 and there is no other messages
has access to the CAN, then this message will immediately gain access to the
CAN right at the time t and transits to Stage 3 or Stage 6 and ID(t) 6= 0.
In these cases S(t) = 0. Therefore, we only need to consider the cases where
all message chains are either at Stage 1 or Stage 4. Let us consider a message
chain indexed by n.

18

Zhenwu Shi, Fumin Zhang

Case 3: τn is at Stage 1, i.e. the residue rn (t) satisfies the following condition
Cn1 (t) + In2 (t)+Cn2 (t) < rn (t) ≤ In1 (t) + Cn1 (t) + In2 (t) + Cn2 (t)

(14)

τn will stay within Stage 1 before τn1 finishing its preparation. The next significant moment will happen at least before τn1 finishing its preparation. Hence
the value of S(t) will be no bigger than the remaining preparation time of τn1
e.g. S(t) ≤ rn (t) − Cn1 (t) − In2 (t) − Cn2 (t).
Case 4: τn is at Stage 4, i.e. the residue rn (t) satisfies the following condition
Cn2 (t) < rn (t) ≤ In2 (t) + Cn2 (t)

(15)

In this case, τn will stay within Stage 4 before τn2 finishing preparation. The
next significant moment will happen at least before τn2 finishing its preparation.
Hence the value of S(t) will be no bigger than the remaining preparation time
of τn2 e.g. S(t) ≤ rn (t) − Cn2 (t).
Based on the above two cases, we know that the next significant moment
will happen at t + S(t) where S(t) should be at most equal to the remaining
preparation time for any message chain τn


S(t) ≤ rn (t)−Cn2 (t)− Cn1 (t)+In2 (t) sgn(max{0, rn (t)−In2 (t)−Cn2 (t)}) (16)

This argument holds for all tasks in stages 1, 2, 4, or 5. Define S2 (t) as



S2 (t) = min rn (t)−Cn2 (t)− Cn1 (t)+In2 (t) sgn(max{0, rn (t)−In2 (t)−Cn2 (t)})
1≤n≤N

(17)
Therefore, the next significant moment will happen at t + S(t) where S(t) ≤
S2 (t).
At the significant moments t + S(t) in the four cases above, if the either
equation (13) or equation (17) holds e.g. S(t) = S1 (t) for ID(t) 6= 0 or S(t) =
S2 (t) for ID(t) = 0, then the values of ID(t + S(t)) will see a jump as
ID(t + S(t)) =

argmin

Pi (t + S(t))

(18)

{i|τi in Stages 2 or 4, at t+S(t)}

If the set {i|τi at Stages 2 or 4 at t + S(t)} is empty, then ID(t + S(t)) = 0. The
values of {D(t), R(t), O(t)} will remain unchanged.
3.3.2 A new instance of message chain arrives
The states of a message chain will jump discretely whenever a new instance
of a message arrives. For any message chain τn , a new instance of τn will
arrive at t + dn (t). Therefore, the earliest next instance of message chains in
{τ1 , · · · , τN } will not arrive until t + min {dn (t)}. Define S3 (t) as
1≤n≤N

S3 (t) = min {dn (t)}.
1≤n≤N

Then S(t) ≤ S3 (t).

(19)

Title Suppressed Due to Excessive Length

19

Let n∗ be the index of the message chain that has the earliest instance that
is arriving after t. If S(t) = dn∗ (t). Then
dn∗ (t + S(t)) = Tn∗ (t + S(t))
rn∗ (t + S(t)) = In1∗ (t + S(t)) + Cn1∗ (t + S(t)) + In2∗ (t + S(t)) + Cn2∗ (t + S(t))
on∗ (t + S(t)) = 0.

(20)

All the other components in {D(t+S(t)), R(t+S(t)), O(t+S(t))} do not jump.
Since there is no change of access to the CAN,the state variable ID(t + S(t))
does not jump either.

3.4 The Timing Model
Let S(t) = min{S1 (t), S2 (t), S3 (t)}. Our timing model integrates both the
continuous time evolution of the state vector Z(t) within [t, t + S(t)), and
the discrete jumps at t + S(t). Hence the evolution of the state vector within
any large time interval [ta , tb ] can be obtained by concatenating the evolution
within individual continuous time interval that belongs to [ta , tb ].
Theorem 1 At any time instant t, given initial values of the state vector
Z(t) = [D(t), R(t), O(t), ID(t)] and the parameters of the message chains
{Tn (t + s′ ), In1 (t + s′ ), Cn1 (t + s′ ), In2 (t + s′ ), Cn2 (t + s′ ), Pn (t + s′ )}N
n=1 for all
0 ≤ s′ ≤ s, there exists a unique vector [D(t + s), R(t + s), O(t + s), ID(t + s)].
Proof Based on our previous discussion, we will just construct the unique solution Z(t + s) at any s > 0. We first show that a unique trajectory is generated
from the continuous evolution of the state vector {D(t), R(t), O(t), ID(t)} from
t to any time t + s where t + s ∈ [ t, t + S(t) ).
For any message chain indexed n, Since dn (t) will continuously decrease as
time propagate, we have that
dn (t + s) = dn (t) − s

(21)

Next, we consider the residue rn (t). If the message chain n is at Stages 1, 3,
4, or 6 then
rn (t + s) = rn (t) − s.
(22)
If the message chain n is at Stages 2, 5, or 7. Then
rn (t + s) = rn (t).

(23)

Next, we consider the delay on (t). If τn has been processed before t, i.e. rn (t) =
0, the delay on (t) will not increase after t. On the other hand, if τn has not
finished before t, i.e. rn (t) > 0, the delay on (t) will continuously increase
between t and t + s. Thus, we have that
on (t + s) = on (t) + sgn(rn (t)) s.

(24)

20

Zhenwu Shi, Fumin Zhang

Finally, we consider the index ID(t). It will keep at constant between t and
t + s since there is no significant moment, i.e.
ID(t + s) = ID(t).

(25)

We see that all the values in the state vector Z(t + s) are uniquely determined.
We now show that at a significant moment, the states jump to unique
values. The possible values for S(t) have been given in equations (13), (17)
and (19) as S1 (t), S2 (t) and S3 (t). The possible jumps in the states are given
by equations (18) and (20). In all cases the states jump to unique values. ⊓
⊔
Due to the theorem, we can represent the hybrid timing model of the CAN
based system as

′
(26)
Z(t + s) = H Z(t), {Tn , In1 , Cn1 , In2 , Cn2 , Pn }N
n=1 (t + s )

where the symbol H(·) represents the timing model and {Tn , In1 , Cn1 , In2 , Cn2 , Pn }N
n=1 (t+
s′ ) represents the parameters of all tasks at any time t + s′ for all 0 ≤ s′ ≤ s.
One immediate benefit of this timing model is a necessary and sufficient
condition for schedulability of all messages in a finite time window.
Definition 8 A message chain τn is instantaneously schedulable on the CAN
at time t if rn (t) ≤ dn (t).
If τn is instantaneously schedulable for all time t, then all the deadlines of τn
are met, then message τn is schedulable in the usual definition. On the other
hand, if the message chain τn is schedulable, then all the deadlines of τn are
met, which implies that the message chain is instantaneously schedulable for
all t.
Corollary 1 A message chain τn is instantaneously schedulable on the CAN
at time t if rn ((t + S(t))− ) ≤ dn ((t + S(t))− ).
Proof Using the dynamic timing model which contains equations (21), (22)
and (23), we must have
dn ((t + S(t))− ) − rn ((t + S(t))− ) = dn (t) − S(t) − rn ((t + S(t))− )
≤ dn (t) − S(t) − (rn (t) − S(t))
= dn (t) − rn (t).

(27)

Hence if rn ((t + S(t))− ) ≤ dn ((t + S(t))− ), then rn (t) ≤ dn (t).
Corollary 2 A message chain is schedulable if and only if it is instantaneously
schedulable at the significant moments.
Proof Consider the time instants right before the significant moments t +
S(t). If the message is instantaneously schedulable at these moments, then the
message chain is instantaneously schedulable at any time t. The entire message
change is schedulable. If a message chain is not instantaneously schedulable
at the significant moments, then the message chain is not schedulable.
⊓
⊔

Title Suppressed Due to Excessive Length

21

4 State Observer
At each embedded controller node, the hybrid timing model will be used to
predict delays and timing constraints for MPC. The prediction requires the
knowledge of the state vector Z(t) = [D(t), R(t), O(t), ID(t)]. Since the CAN
uses a broadcast scheme, each embedded controller node will know which message is currently being transmitted on the CAN, i.e. the value of ID(t) can
be determined. However, the values of the states [D(t), R(t), O(t)] may not be
measured directly. In this section, we will discuss how to estimate the state
vector [D(t), R(t), O(t)] based on events that can be observed on the CAN.

4.1 Estimation of [D(t), R(t), O(t)]
As discussed in [Di Natale et al. 2012], CAN chips can generate an interrupt
whenever a message is received by a node. These interrupts can be pre-handled
by a dedicated MCU that usually shipped together with CAN chip. Therefore,
we can easily design an interrupt handler on the host processor of a CAN node
to observe the receiving times of τn1 [k] and τn2 [k], which corresponds to βn [k]
and γn [k] as shown in Figure 2. Note that the CAN utilizes a broadcast scheme
for message transmission. The MPC controller node in each feedback loop
can not only receive messages within its own control loop, but also messages
from other feedback control loops. Therefore, each MPC controller node has
complete information of {βn [k], γn [k]} for all message chains {τ1 , · · · , τN } on
the CAN. But there is no direct way to measure αn [k].
Based on the above observations, we propose an algorithm to estimate the
value of αn [k] as follows
α̂n [k] = min{α̂n [k−1]+Tn [k−1], βn [k]−Cn1 [k]−In1 [k]}

(28)

where α̂n [k − 1] is the estimate from the previous observations of βn [k − 1]
and γn [k − 1]. Each controller node can estimate α̂n [k] for all message chains.
The computation of α̂n [k] for 1 ≤ n ≤ N at each node is linear with respect
to the number of control loops.
At the current time t, given {α̂n [k], βn [k], γn [k]}, each embedded controller
node can estimate the state vector {dˆn (t), ôn (t), r̂n (t)}. The deadline dn (t) is
estimated as
dˆn (t) = α̂n [k] + Tn [k] − t,

(29)

where α̂n [k] + Tn [k] is the time instant when τn [k + 1] starts. The delay on (t)
is estimated as
ôn (t) =

(

t − α̂n [k]
γn [k] − α̂n [k]

if τn2 [k] NOT received
,
if τn2 [k] received

(30)

22

Zhenwu Shi, Fumin Zhang

The delay will not increase if τn2 [k] has finished transmission before t. The
residue rn (t) can be estimated as
r̂n (t) =
 1
1
2
2
{I
+C
+I
+C
}[k]−min{
t−α̂
[k],
In1 [k] }, τn1 [k] and τn2 [k] NOT received

n
 n n n n
In2 [k]+Cn2 [k]−min{t−βn [k], In2 [k]},
τn1 [k] received, τn2 [k] NOT received


0,
τn1 [k] and τn2 [k] received
(31)
where {In1+Cn1+In2+Cn2 }[k] is the shorthand notation for In1 [k]+Cn1 [k]+In2 [k]+Cn2 [k].
Whenever a message is received by the controller node, an interrupt function can be triggered to estimate [dˆn (t), r̂n (t), ôn (t)] for n = 1, 2, ..., N at
the moment of reception. Then the state vector [D̂(t), R̂(t), Ô(t)] will be constructed. The timing model H can then be used to predict the state vectors in
future times starting from t.

4.2 Convergence of Estimation
We show that the estimation [D̂(t), R̂(t), Ô(t)] will have bounded error. The
error will not increase as time t propagates.
As we discussed in Equation (29), (30), and (31), the estimates [D̂(t), R̂(t), Ô(t)]
N
are derived from {α̂n [k], βn [k], γn [k]}N
n=1 . Since {βn [k], γn [k]}n=1 can be directly observed from the CAN, the accuracy of estimating [D̂(t), R̂(t), Ô(t)] is
actually determined by the accuracy of estimating α̂n [k]. Define the estimation
error between α̂n [k] and αn [k] as
ǫn [k] = α̂n [k] − αn [k] for any k ≥ 0

(32)

Claim The estimation error ǫn [k] is non-negative and non-increasing as k
grows, i.e.
ǫn [0] ≥ ǫn [1] ≥ · · · ≥ ǫn [k] ≥ ǫn [k + 1] ≥ · · · ≥ 0.
(33)
Proof First, we prove that the estimation error is non-negative, i.e. ǫn [k] ≥ 0
for any k ≥ 0. When multiple message chains {τ1 , · · · , τN } are transmitted on
the CAN, each message may not be transmitted immediately after it is ready.
Instead, it has to compete with other messages for access to the CAN. Thus,
we have that
αn [k] + In1 [k] ≤ βn [k] − Cn1 [k] for any k ≥ 0

(34)

where the left hand side represents the time when a message τn1 [k] is ready for
transmission, i.e. τn at Stage 2, and the right hand side represents the time
when τn1 [k] actually starts to transmit on the CAN bus, i.e. τn at the beginning
of Stage 3. According to Equation (28) and (34), we know that
α̂n [0] = βn [0] − Cn1 [0] − In1 [0] ≥ αn [0]

(35)

Title Suppressed Due to Excessive Length

23

which implies ǫn [0] ≥ 0. Moreover, we have that
α̂n [0] + Tn [0] ≥ αn [0] + Tn [0] = αn [1].

(36)

According to Equation (34), we have that
βn [1] − Cn1 [1] − In1 [1] ≥ αn [1]

(37)

Therefore, based on Equation (28), (36), and (37), we have that
α̂n [1] = min{α̂n [0]+Tn [0], βn [1]−Cn1 [1]−In1 [1]} ≥ αn [1]

(38)

which implies that ǫn [1] ≥ 0. By induction, we have shown that ǫn [k] ≥ 0 for
any k ≥ 0.
Next, we show that the estimation error ǫn [k] is non-increasing as k grows,
i.e. ǫn [k] ≥ ǫ[k + 1]. According to Equation (28), we have that
α̂n [k + 1] ≤ α̂n [k] + Tn [k]

(39)

α̂n [k + 1] − α̂n [k] ≤ Tn [k] = αn [k + 1] − αn [k]

(40)

which implies that
Hence, we have that
α̂n [k] − αn [k] ≥ α̂n [k + 1] − αn [k + 1]

(41)

Therefore, ǫ[k] ≥ ǫ[k + 1] for any k ≥ 0 is proved.

⊓
⊔

The claim implies that the estimation error for the state vector are all
bounded and the error will never increase. In fact, we have observed in our
simulations that this error often decreases to zero. But there are cases where
the error stays as a constant value.
Using the estimated states, we can also test for instantaneous schedulability by checking the condition r̂n (t) ≤ dˆn (t) at the significant moments. The
following theorem holds.
Theorem 2 If a task is instantaneously schedulable e.g. rn (t) ≤ dn (t), then
the estimated states satisfies r̂n (t) ≤ dˆn (t).
Proof According to equation (29), we have
dˆn (t) = α̂n [k] + Tn [k] − t
= αn [k] + ǫn [k] + Tn [k] − t
= dn (t) + ǫn [k]
≥ rn (t) + ǫn [k].

(42)

According to (31), we have
r̂n (t) − rn (t) =
(
min{ t−αn [k], In1 [k] }−min{ t−α̂n [k], In1 [k] } τn1 [k] and τn2 [k] NOT received
0

otherwise

(43)
which implies that r̂n (t) − rn (t) = α̂n (t) − αn (t) = ǫn [k]. Therefore r̂n (t) ≤
dˆn (t).
⊓
⊔

24

Zhenwu Shi, Fumin Zhang

The above theorem implies that if the message chains are schedulable, then
the estimated states will never fail the schedulability test. On the other hand,
suppose we detect that a message chain is not schedulable using the estimated
states, then the task set must not be schedulable.

5 MPC Design
In this section, the MPC design problem proposed in Section 2 will be solved.
We assume that all the message chains are schedulable. Since each control loop
is independent, the MPC design for any of the loops can be solved in the same
way.
Let us consider the MPC design for the nth feedback loop corresponding
to the message chain τn . As discussed in Section 2.4, the value of δn [k] within
the prediction horizon is needed for MPC design. The message chain τn has
K instances that falls within the prediction horizon. Let the indices of these
instances starts from k and ends at k + K − 1 where K ≥ 1 is an integer. Then
we need to determine δn [k + j − 1] for j = 1, 2, ..., K.
Theorem 3 Suppose all messages are schedulable. Consider the time instants
tj = αn [k] +

j
X

Tn [k + l − 1]

(44)

l=1

for j = 1, 2, ..., K. Then the delay δn [k + j − 1] can be obtained from the states
as
δn [k + j − 1] = on (t−
(45)
j ).
Proof By definition of the state variable on (t), it represents the time delay
between the starting time of the active instance of a message chain and the
−
time t. If we let t = t−
j , then on (tj ) is the delay between the starting time
of the active instance τ (tj ) and tj . Since all message chains are schedulable,
the active instance τ (tj ) would have been processed before tj . Then the delay
on (t−
j ) is the delay between the starting time and the finishing time of the
active instance e.g. δn [k + j − 1] = on (t−
⊓
⊔
j ).
Let the current time be t, suppose we have estimated the state vector Ẑ(t)
by the state observer introduced in Section 4. Then, we will be able to predict
the future trajectory of Ẑ(t + s) for all s ∈ [0, Tp ] where Tp is the length of the
prediction horizon:
[D̂(t + s), R̂(t + s), Ô(t + s), ID(t + s)] =
′
H([D̂(t), R̂(t), Ô(t), ID(t)], {Tn , In1 , Cn1 , In2 , Cn2 , Pn }N
n=1 (t + s ))

(46)

where 0 ≤ s′ ≤ s. Using the hybrid timing model H, let t + s = tj for j =
1, 2, ..., K − 1. we can perform online prediction of the delay as δn [k + j − 1] =

Title Suppressed Due to Excessive Length

25

ôn (tj ) according to equation (45). Due to the fact that α̂n [k] ≥ αn [k], the
delay based on the estimate ôn may be smaller than the actual delay.
With the delay δn [k + j − 1] determined for j = 1, 2, ..., K all determined,
the MPC design problem (6) subject to the constraints (6.a)-(6.c) is now well
formulated. The solution of the continuous time MPC problem can be obtained
using well-known optimization techniques as in [Wang 2009]. The resulting
piecewise linear control effort is then applied to the plant until the next time
the controller is triggered. The timing model will be engaged again to predict
the delays, and then a new piecewise control law will be computed by solving
the MPC design problem. This process will be iterated. The prediction of
the delay requires little computing time for the following reasons: (1) the
timing model is very simple with linear complexity; (2) the calculation is only
performed at the significant moment because the transition between any two
consecutive moments is continuous and follows the equations in the timing
model. Hence, the timing model is compatible with the MPC design approach.

6 Numeric Simulation
In this section, we use numeric simulations to demonstrate the MPC design
using the hybrid timing model of the CAN. We show that the timing model is
preferred even when there exist other simulation tools to generate the timing
sequences for the message chains.
The simulation environment for the CAN-based control system is established according to Figure 1. To compare with our approach, the CAN in
Figure 1 is simulated using Truetime (Version 2.0) [Cervin et al. 2003]. Truetime is a Matlab/Simulink-based simulator for real-time control system, which
provides a network block that supports the protocol of the CAN. The Truetime simulation results are used as the ground truth for the timing of message
chains.
Our simulation contains three feedback control loops sharing the CAN.
The plant in each feedback loop is an inverted pendulum model represented
as follows

 

0
0 1
u (t)
x (t) +
ẋn (t) =
cn n
an b n n


yn (t) = 1 0 xn (t)
(47)
The inverted pendulums in the three feedback control loops have different coefficients as [a1 , a2 , a3 ] = [98, 65, 44], [b1 , b2 , b3 ] = [120, 52, 30] and [c1 , c2 , c3 ] =
[20, 13, 10]. The sensor nodes sample the state of the plants at the time interval of 20 ms, 30 ms, and 40 ms. Each sensor node needs 1 ms to process
the sampling information and generate a sensor message. The MPC controller
node in each feedback control loop computes an optimal control signal un (t)
that makes the plant output yn (t) track a given reference trajectory γn (t) as

26

Zhenwu Shi, Fumin Zhang
δn [k]
n=1
n=2
n=3

k=1
10 ms
13 ms
21 ms

k=2
9 ms
9 ms
13 ms

k=3
10 ms
13 ms
13 ms

k=4
10 ms
11 ms
21 ms

Table 3: Delays predicted through the hybrid timing model
close as possible, under the constraint that −4 ≤ un (t) ≤ 4. The computation time of an MPC is 2 ms. The actuator node takes action as soon as the
control message is received from the CAN bus. We assume that sensor and
control messages have the transmission duration of 3 ms and they are assigned
unique identifier fields such that the priorities of the message chains satisfy
P11 [k] < P12 [k] < P21 [k] < P22 [k] < P31 [k] < P32 [k] which implies that the
first feedback loop has the highest priority and the third loop has the lowest
priority. Hence the three message chains transmitted on the CAN have the
following characteristics


T1 (t), I11 (t), C11 (t), I12 (t), C12 (t) = [20, 1, 3, 2, 3] ms


T2 (t), I21 (t), C21 (t), I22 (t), C22 (t) = [30, 1, 3, 2, 3] ms


(48)
T3 (t), I31 (t), C31 (t), I32 (t), C32 (t) = [40, 1, 3, 2, 3] ms
6.1 Verification of Hybrid Timing Model
We first verify the correctness of our proposed timing model by comparing
the delays predicted through the hybrid timing model with the delay observed
from the simulation results generated from Truetime. Suppose the message
chains in Equation (48) are being transmitted on the CAN. Figure 4 shows
the timing of message chains generated by the Truetime simulation. Table 3
shows the delays δn [k] predicted through the hybrid timing model in Equation
(46) and (45). In Figure 4, the value “0.5”. indicates that the message is ready
for transmission but blocked by other messages on the CAN bus, the value
“1” indicates that the message is being transmitted on the CAN bus, and the
value “0” indicates that the message finishes transmission.
For illustration, we examine the delay δ3 [k] in the third feedback control
loop. The delays in other feedback control loops can be studied using the exactly same procedure. We know that δ3 [k] is a time interval between the moment when the sensor take measurements and the moment when the actuator
take actions. The sensor in the third feedback control loops take measurements at 0 ms, 40 ms, 80 ms, and 120 ms. By closely examining Figure 4, we
observe that the control message τ32 in the third feedback control loop finishes
transmission at 21 ms, 53 ms, 92 ms, and 141 ms. Therefore, the observation
of Figure 4 shows that the value of δ3 [k] is 21 ms, 13 ms, 12 ms, and 21 ms,
for 1 ≤ k ≤ 4. This observation exactly matches the value of δ3 [k] listed in
Table 3. Similarly, we can see that the values of δ1 [k] and δ2 [k] observed from
Figure 4 also match that listed in Table 3. Therefore, we can claim that the

Title Suppressed Due to Excessive Length

27

Result from Truetime Simulation
1

τ 11

0
1

τ 12

0
1

τ 21

0
1

τ 22

0
1

τ 31

0
1

τ 32
0

0
20

40

60

80
Time(ms)

100

120

140

160

Fig. 4: Timing of message chains produced by Truetime simulation

hybrid timing model can accurately describe the timing of message chains on
the CAN.

6.2 Analysis of Computational Cost
Even though Truetime and other event-based simulation tools are able to generate the timing sequences of the message chains, running such simulation
takes significant amount of computation resources. Hence these simulations
may be too slow for realtime embedded applications. Our timing model is discontinuous at limit number of time points, but continuous the rest of time. So,
running our model only requires significant computation at a small fraction of
discrete time points, and the system transition between any two consecutive
discrete time points can be directly derived using mathematical equations.
This has caused a significant reduction of computing load when compared to
typical simulation based methods. To verify this computational advantage, we
evaluate the computational time of generating scheduled behavior in Figure
4 using both the hybrid timing model and Truetime. The experiment is performed on a MacBook computer with Processor 2.26 GHz Intel Core 2 Duo,
and Memory 4GB 1067MHz DDR3. Since Truetime is written in C++ Mex,
we also implement the analytical timing model in the same way as Truetime.
Matlab version 2010Rb and the Trutime Version 2.0 are used for the comparison. For each simulation window length that falls within [0, 100]s, we run both
methods 50 times and then calculate the averaged computation time for each
method. Fig 5 shows the comparison. The horizontal axis denotes the window
length used for all simulated scheduled behaviors, and the vertical axis denotes
the time spent to compute the simulation. In both figures, the computational
time linearly increases with window length. More importantly, we can see that
the hybrid timing model is approximately 4000 times faster than Truetime,
which is a significant improvement for embedded system applications.

28

Zhenwu Shi, Fumin Zhang
Computational Complexity of Truetime
30

0.01

25

Computational Time(s)

Computational Time(s)

Computational Complexity of Our Timing Model
0.012

0.008

0.006

0.004

0.002

0

20

15

10

5

0

10

20

30

40

50

60

70

80

Window Length(s)

(a) Hybrid Timing Model

90

100

0

0

10

20

30

40

50

60

70

80

90

100

Window Length(s)

(b) Truetime Simulation

Fig. 5: Comparing the time needed to simulating scheduled behaviors.
6.3 MPC Performance
We demonstrate the performance of the MPC using the hybrid timing model
for a CAN-based control system operating in dynamic, uncertain environment.
Suppose the messages on the CAN are changed at runtime. We consider two
types of messages adjustments on the CAN within the time interval [1, 1.5]s.
One is the adjustment of the message period as
[ T1 (t), T2 (t), T3 (t) ] = [20, 40, 50] ms

(49)

The other type of adjustments is the activation of two sporadic messages on
the CAN, which have the following characteristics


T4 (t), I41 (t), C41 (t), I42 (t), C42 (t) = [40, 0.2, 1, 0, 0] ms


T5 (t), I51 (t), C51 (t), I52 (t), C52 (t) = [60, 0.2, 1, 0, 0] ms
(50)

The sporadic messages are assigned unique identifier field such that P5 [k] <
P4 [k] < P11 [k]. Note that since these adjustments happen at runtime, their
characteristics are not available at the off-line design stage. It is then expected
that the timing of the message chains will be disturbed and the controller
performance will be affected.
We compare two different approaches of designing MPC for the CANbased control system. The two approaches differ in their way of predicting
δn [k]. In the first approach, the delay δn [k] is predicted off-line through the
worst-case analysis discussed in [Tindell and Burns 1994, Tindell et al. 1995,
Davis et al. 2007]. In the second approach, the delay δn [k] is predicted online
through the hybrid timing model. Figure 6 shows the MPC performance of
three feedback control loops under the above two different approaches. The
solid line represents the plant output yn (t) and the dashed line represents the
reference trajectory γn (t). The left plots are results of the first approach that
uses the worst-case response time and the right plots are results of the second
approach that uses the hybrid timing model. It is obvious that the second

Title Suppressed Due to Excessive Length

29

Plant Output
Reference

0.8

Plant Output
Reference

0.8

0.6

0.6

0.4

0.4

0.2

0.2

1
0

0

2
−0.2

−0.2

−0.4

−0.4

−0.6

−0.6

−0.8
0.8

−0.8
1

1.2

1.4

1.6

1.8

2

0.8

1

1.2

1.4

1.6

1.8

2

Time−Seconds

Time−Seconds

(a) The first feedback control loop
Plant Output
Reference

0.8

Plant Output
Reference

0.8

0.6

0.6

0.4

0.4

0.2

0.2

2
0

0

2
−0.2

−0.2

−0.4

−0.4

−0.6

−0.6

−0.8
0.8

−0.8
1

1.2

1.4

1.6

1.8

2

0.8

1

1.2

1.4

1.6

1.8

2

Time−Seconds

Time−Seconds

(b) The second feedback control loop
Plant Output
Reference

1

Plant Output
Reference

0.8
0.6

0.5
0.4

3

0

0.2

−0.5

0

3
−0.2

−1

−0.4
−1.5
−0.6
−2
0.8

−0.8
1

1.2

1.4

1.6

1.8

2

0.8

1

1.2

Time−Seconds

1.4

1.6

1.8

2

Time−Seconds

(c) The third feedback control loop

Fig. 6: MPC performance of three feedback control loops, under two design
approaches

approach (right plots) gives better performance than the first approach (left
plots). This is because in the second approach, delays are predicted online using
the hybrid timing model of the CAN, which can accurately predict delay and
dynamically compensate for the delay.
Also, it is worth mentioning that even in the first approach(left plots),
MPC performance in the first feedback control loop is better than the other
two loops. This is because the messages in the first feedback control loop are
assigned the highest priorities among all messages on the CAN. Therefore, the
difference between the actual delay and the worst-case response time is small
in the first feedback control loop . Using even the worst-case response time for
MPC design can still give out the acceptable performance for the first feedback
control loop. However, such difference in the second and third feedback control
loop will increases, which leads to the degraded MPC performance.

30

Zhenwu Shi, Fumin Zhang

7 Conclusion and Future Work
The main contribution of this paper is a hybrid timing model for messages
scheduled on the CAN. We have shown that such timing model enables a model
predictive control approach on the CAN. It also provides convenient ways to
check for schedulability of messages. This model may be used for co-design of
scheduling and MPC for real-time embedded systems on the CAN. Moreover,
the timing model is a generic mathematical model that can be extended to
many applications [Wang et al 2013,Wang et al 2015,Wang et al 2015,Shi et al 2016].
Our simulations show that using the hybrid timing model for MPC can achieve
improved performance than using worst case timing. Our future work will extend this hybrid timing model to other real-time communication networks
that use message priorities for arbitration, for example, the dynamic segment
of FlexRay [Pop et al. 2008].
References
Almeida et al. 2002. Almeida L, Pedreiras P, Fonseca J (2002) The FTT-CAN protocol:
Why and How. IEEE Transactions on Industrial Electronics 49(6):1189–1201
Anta and Tabuada 2009. Anta A, Tabuada P (2009) On the Benefits of Relaxing the Periodicity Assumption for Networked Control Systems over CAN. In: Proc. of IEEE
International Conference on Real-Time Systems Symposium, pp 3–12
Arzen et al. 2000. Arzen KE, Cervin A, Eker J, Sha L (2000) An introduction to control
and scheduling co-design. In: Proceedings of the 39th IEEE Conference on Decision and
Control, IEEE, Sydney, Australia, vol vol.5, pp 4865–4870
Baruah et al. 1997. Baruah SK, Chen D, Mok AK (1997) Jitter concerns in periodic task
systems. In: Proceedings of the 18th IEEE Real Time Systems Symposium, IEEE,
Piscataway, NJ, USA, pp 68–77
Camacho and Bordons Alba 2004. Camacho EF, Bordons Alba C (2004) Model Predictive
Control, Advanced Textbooks in Control and Signal Processing, vol 57. Springer
Cervin et al. 2003. Cervin A, Henriksson D, Lincoln B, Eker J, Å rzén KE (2003a) How
Does Control Timing Affect Performance. IEEE Control Systems Magazine 23(3):16–30
Cervin et al. 2006. Cervin A, Arzen KE, Henriksson D, Lluesma M, Balbastre P, Ripoll
I, Crespo A (2006) Control loop timing analysis using TrueTime and Jitterbug. In:
Proceedings of the 2006 IEEE International Conference on Computer-Aided Control
Systems Design, IEEE, Munich, Germany, pp 1194–1199
Chantem et al. 2006. Chantem T, Hu XS, Lemmon MD (2006) Generalized elastic scheduling. In: Proc. 27th RTSS
Clarke et al. 1987. Clarke D, Mohtadi C, Tuffs P (1987) Generalized Predictive Control
Algorithm Part I. The Basic Algorithm. Automatica 23(2):137–148
Davis et al. 2007. Davis RI, Burns A, Bril RJ, Lukkien JJ (2007) Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems
35:239–272
Di Natale et al. 2012. Di Natale M, Zeng H, Giusto P, Ghosal A (2012) Understanding and
Using the Controller Area Network Communication Protocol. Springer, New York, NY
Gaid et al. 2006. Gaid M, Cela A, Hamam Y (2006) Optimal integrated control and scheduling of networked control systems with communication constraints: application to a car
suspension system. Control Systems Technology, . . . 14(4):776–787
Gmbh 1991. Gmbh RB (1991) CAN Specification Version 2.0. Tech. rep., Stuttgart, Germany
Goodwin et al. 2004. Goodwin GC, Haimovich H, Quevedo DE, Welsh JS (2004) A Moving Horizon Approach to Networked Control System Design. IEEE Transactions on
Automatic Control 49(9):1427–1445

Title Suppressed Due to Excessive Length

31

Grune and Jurgen 2011. Grune L, Jurgen P (2011) Nonlinear Model Predictive Control
Theory and Algorithms. Communications and Control Engineering Series, Springer,
New York
Henriksson et al. 2002. Henriksson D, Cervin A, Akesson J, Arzen KE (2002) On dynamic
real-time scheduling of model predictive controllers. In: IEEE 2002 Conf. on Decision
and Control, IEEE, Las Vegas, NV, USA, vol vol.2, pp 1325–1330
Hespanha et al. 2007. Hespanha JP, Naghshtabrizi P, Xu Y (2007) A Survey of Recent
Results in Networked Control Systems. IEEE Proceedings 95(1)
Imer et al. 2006. Imer OC, Yüksel S, Baar T (2006) Optimal Control of LTI Systems over
Unreliable Communication Links. Automatica 42(9):1429–1439
Jeon et al. 2001. Jeon JM, Kim DW, Kim HS, Cho YJ, Lee BH (2001) An Analysis of
Network-Based Control System using CAN (Controller Area Network) Protocol. Proc
of IEEE International Conference on Robotics and Automation 4:3577–3581
Lee et al. 1994. Lee J, Morari M, Garcia C (1994) State-space interpretation of model predictive control. Automatica 30(4):707–717
Leen and Heffernan 2002. Leen G, Heffernan D (2002) TTCAN: a new time-triggered controller area network. Microprocessors and Microsystems 26(2):77–94
Liu and Layland 1973. Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a Hard-Real-Time environment. Journal of the ACM 20(1):46–61
Liu et al. 2013. Liu G, Sun J, Zhao Y (2013) Design, Analysis and Real-time Implementation of Networked Predictive Control Systems. Acta Automatica Sinica 39(11)
Liu et al. 2007. Liu GP, Xia Y, Chen J, Rees D, Hu W (2007) Networked Predictive Control
of Systems With Random Network Delays in Both Forward and Feedback Channels.
IEEE Transactions on Industrial Electronics 54(3):1282–1297
Loontang and de Silva 2006. Loontang P, de Silva CW (2006) Compensation for Transmission Delays in an Ethernet-Based Control Network Using Variable-Horizon Predictive
Control. IEEE Transactions on Control Systems Technology 14(4):707–718
Martı́ et al. 2010. Martı́ P, Camacho A, Velasco M, Gaid MEMB (2010) Runtime Allocation
of Optional Control Jobs to a Set of CAN-Based Networked Control Systems. IEEE
Transactions on Industrial Informatics 6(4):503–520
Mayne et al. 2000. Mayne DQ, Rawlings JB, Rao CV, Scokaert POM (2000) Constrained
model predictive control: Stability and optimality. Automatica 36(6):789–814
Montestruque and Antsaklis 2004. Montestruque LA, Antsaklis P (2004) Stability of
Model-Based Networked Control Systems With Time-Varying Transmission Times.
IEEE Transactions on Automatic Control 49(9):1562–1572
Pop et al. 2008. Pop T, Pop P, Eles P, Peng Z, Andrei A (2008) Timing analysis of the
FlexRay communication protocol. Real-Time Systems 39(1-3):205–235
Rawlings 2000. Rawlings JB (2000) Tutorial Overview of Model Predictive Control. IEEE
Control Systems Magazine 20(3):38–52
Richalet et al. 1978. Richalet J, Rault A, Testud J, Papon J (1978) Model Predictive
Heuristic Control : Applications to Industrial Processes. Automatica 14(5):413–428
Sha et al. 2004. Sha L, Abdelzaher T, Arzen KE, Cervin A, Baker T, Burns A, Buttazzo G, Caccamo M, Lehoczky J, Mok AK, Å rzén KE (2004) Real Time
Scheduling Theory: A Historical Perspective. Real-Time Systems 28(2-3):101–155URL
http://dx.doi.org/10.1023/B:TIME.0000045315.61234.1e
Shi and Zhang 2012. Shi Z, Zhang F (2012) An Analytical Model of the CAN Bus for
Online Schedulability Test. In: Proc.of the Third Analytic Virtual Integration of CyberPhysical Systems Workshop (AVICPS), held in conjunction with the 33rd IEEE RealTime Systems Symposium (RTSS2012).
Shi and Zhang 2013. Shi Z, Zhang F (2013) Predicting Time-Delays under Real-Time
Scheduling for Linear Model Predictive Control. In: Proc.of 2013 International Conference on Computing,Networking and Communication, Workshops Cyber Physical System, pp 205–209.
Tindell and Burns 1994. Tindell K, Burns A (1994) Guarantee Message Latency on Control
Area Network(CAN). In: Proc. of International CAN Conference, Figure 1, pp 1–11
Tindell et al. 1995. Tindell K, Burns A, Wellings A (1995) Calculating Controller Area
Network (CAN) message response times. Control Engineering Practice 3(8):1163–1169
Wang 2009. Wang L (2009) Model Predictive Control System Design and Implementation
Using MATLAB, 1st edn. Springer.

32

Zhenwu Shi, Fumin Zhang

Zeng et al. 2010. Zeng H, Natale MD, Giusto P, Sangiovanni-vincentelli A (2010) Using
Statistical Methods to Compute the Probability Distribution of Message Response Time
in Controller Area Network. IEEE Transactions on Industrial Informatics 6(4):678–691
Zhang et al. 2008. Zhang F, Szwaykowska K, Mooney V, Wolf W (2008) Task scheduling
for control oriented requirements for cyber-physical systems. In: Proc. of 29th IEEE
Real-Time Systems Symposium (RTSS 2008), Barcelona, Spain, pp 47–56
Zhang et al. 2013. Zhang F, Shi Z, Mukhopadhyay S (2013) Robustness analysis for batterysupported cyber-physical systems. ACM Transactions on Embedded Computing Systems 12(3): Article No. 69 (1–27)
Zhang et al. 2005. Zhang L, Shi Y, Chen T, Huang B (2005) A New Method for Stabilization of Networked Control with Random Delays. Automatic Control, IEEE
. . . 50(8):1177–1181
Zhao et al. 2008. Zhao Y, Liu G, Rees D (2008) Integrated predictive control and scheduling
co-design for networked control systems. Control Theory & Applications, IET
Gianluca et al. 2012. Gianluca Cena, Ivan Cibrario Bertolotti, Adriano Valenzano An Efficient Fixed-length Encoding Scheme for CAN. In: Proc of 9th IEEE International
Workshop on Factory Communication Systems, pp. 265 - 274, 2012
Wang et al 2015. Wang X, Shi Z, Zhang F, Wang Y (2015) Mutual trust based scheduling
for (semi) autonomous multi-agent systems. In: Proc.of 2015 American Control Conference , pp 459–464.
Wang et al 2013. Wang Y, Shi Z, Wang C, Zhang F (2013) Human-robot mutual trust in
(semi) autonomous underwater robots. Cooperative Robots and Sensor Networks, pp.
115-137, 2013
Wang et al 2015. Wang X, Shi Z, Zhang F, Wang Y (2015) Dynamic real-time scheduling
for human-agent collaboration systems based on mutual trust. Cyber-Physical Systems
1(2-4): 76-90
Shi et al 2016. Shi Z, Yao N, Zhang F (2016) Scheduling Feasibility of Energy Management in Micro-grids Based on Significant Moment Analysis. Cyber-Physical Systems
Foundations, Principls, and Applications, pp. 431-449, 2016

