Linear switching system

Here, we use linear switching systems to model the CPS, for simplicity, as illustrated in Fig.7.1. The dynamics is described by the following difference equations¹ :

$\begin{array}{l}\hfill \left\{\begin{array}{c}\mathbf{x}(t+1)={\mathbf{A}}_{k(t)}\mathbf{x}(t)+{\mathbf{B}}_{k(t)}\mathbf{u}(t)+\mathbf{n}(t),\\ \mathbf{y}(t)={\mathbf{C}}_{k(t)}\mathbf{x}(t)+\mathbf{w}(t),\end{array}\right.\end{array}$

where x is the continuous system state, k is the discrete system state, u is the control action, y is the observation vector, n and w are both random noise, and A_k, B_k and C_k are system parameters, which are dependent on the discrete system state. The set of the discrete system state is denoted by $\mathcal{K}$. Obviously, when the discrete system state k changes, the mode of the dynamics of the continuous system state x also changes. Hence the continuous system dynamics seems to be switched among multiple modes determined by the discrete system state. The observability, controllability, stability, and control strategies (for both x and k) have been intensively studied, which can be found in the survey book [123].

Control of linear switching systems

In this section we provide an introduction to an effective approach for controlling linear switching systems using linear quadratic regulator (LQR) theory. For simplicity, we consider the following dynamical system with the continuous system state x and discrete system state k:

$\begin{array}{l}\hfill \mathbf{x}(t+1)={\mathbf{A}}_{k(t)}\mathbf{x}(t)+{\mathbf{B}}_{k(t)}\mathbf{u}(t),\end{array}$

which is a special case of the generic linear switching system in Eq. (7.1) with n = w = 0 and C = I (i.e., there is no noise and the system state is observed directly).

In the framework of the LQR, we define the cost function as

$\begin{array}{l}\hfill L(\mathbf{x},\mathbf{u},k)={\mathbf{x}}^T{\mathbf{Q}}_k\mathbf{x}+{\mathbf{u}}^T{\mathbf{R}}_k\mathbf{u},\end{array}$

where {Q_k}_k and {R_k}_k are positive definite matrices. Then for a time period T, the cost of system operation is defined as

$\begin{array}{l}\hfill J(\mathbf{x}(0),{\pi }_T)=\psi (\mathbf{x}(T))+\sum _{t=0}^{T-1}L(\mathbf{x}(t),\mathbf{u}(\mathbf{x}(t)),k(\mathbf{x}(t))),\end{array}$

where ψ is the cost of the final time slot, x(0) is the initial system state, and π_T is the feedback control law. We can also let $T\to \infty$ such that

$\begin{array}{l}\hfill J(\mathbf{x}(0),{\pi }_{\infty })=\sum _{t=0}^{\infty }L(\mathbf{x}(t),\mathbf{u}(\mathbf{x}(t)),k(\mathbf{x}(t))).\end{array}$

The goal of switched LQR control is to obtain the following value functions:

$\begin{array}{l}\hfill \left\{\begin{array}{c}{V}_T(\mathbf{z})=\underset{{\pi }_T}{inf}J(\mathbf{z},{\pi }_T),\\ V_{\infty }(\mathbf{z})=\underset{{\pi }_{\infty }}{inf}J(\mathbf{z},{\pi }_{i}nfty),\end{array}\right.\end{array}$

A standard approach for solving multistage optimization problems is dynamic programming (DP). We consider a control law ξ = (u, k) which maps from the system state x to the continuous action u and the discrete state selection k. We define an operator T_ξ as follows:

$\begin{array}{l}\hfill T_{\xi }[g](\mathbf{z})=L(\mathbf{z},\mathbf{u}(\mathbf{z}),k(\mathbf{z}))+g({\mathbf{A}}_{k(\mathbf{z})}\mathbf{z}+{\mathbf{B}}_{k(\mathbf{z})}\mathbf{u}),\end{array}$

for any function g mapping from Rⁿ to positive numbers. Then, the one-stage value iteration operation T, which is now independent of the control law, is given by

$\begin{array}{l}\hfill T[g](\mathbf{z})=\underset{\mathbf{u},k}{inf}\{L(\mathbf{z},\mathbf{u},k)+g({\mathbf{A}}_{k(\mathbf{z})}\mathbf{z}+{\mathbf{B}}_k)\mathbf{u})\}.\end{array}$

The tth repetition of the value iteration is denoted by T^t. For the finite duration case, the optimal action taken at time slot t is given by

$\begin{array}{l}\hfill {(\mathbf{u},k)}_{\mathrm{opt}}=arg\underset{\mathbf{u},k}{min}\{L(\mathbf{z},\mathbf{u},k)+T^{T-t}[\psi ]({\mathbf{A}}_{k(\mathbf{z})}\mathbf{z}+{\mathbf{B}}_k)\mathbf{u})\}.\end{array}$

Although the DP framework is theoretically simple, it is difficult in practice since the argument z (namely the initial value) in the function T[g] is continuous. For the generic case, it takes infinitely many bits to perfectly describe the function T[g]. An approach to handle the continuous argument is to discretize it by dividing the real space into many bins. However, such an approach is impractical when the dimension of z is high, due to the curse of dimensions.

Fortunately, the special structure in the switched LQR problem can be used to simplify the DP. This is accomplished in Ref. [129]. To that goal, we define the Riccati mapping for each dynamics mode k:

$\begin{array}{l}\hfill {\rho }_k(\mathbf{P})={\mathbf{Q}}_k+{\mathbf{A}}_k^T\mathbf{P}{\mathbf{A}}_k-{\mathbf{A}}_k\mathbf{P}{\mathbf{B}}_k{({\mathbf{R}}_k+{\mathbf{B}}_k^T\mathbf{P}{\mathbf{B}}_k)}^{-1}{\mathbf{B}}_k^T\mathbf{P}{\mathbf{A}}_l.\end{array}$

Then, we define the switched Riccati mapping as

$\begin{array}{l}\hfill {\rho }_{\mathcal{K}}(\mathcal{H})=\{{\rho }_k(\mathbf{P})|k\in \mathcal{K},\mathbf{P}\in \mathcal{H}\},\mathcal{H}\in \mathcal{F},\end{array}$

where $\mathcal{F}$ is the set of all subsets of semidefinite matrices with finitely many elements. The switched Riccati sets are defined as the sequence of sets ${\{{\mathcal{H}}_t\}}_{t=0}^{\infty }$ generated iteratively by

$\begin{array}{l}\hfill {\mathcal{H}}_{t+1}={\rho }_{\mathcal{K}}({\mathcal{H}}_t),\end{array}$

with the initial condition ${\mathcal{H}}_0=\{{\mathbf{Q}}_f\}$. The analogy between the function value iteration and the Raccati sets value iteration is illustrated in Fig.7.2.

The following theorem shows the relationship between the value functions and the switched Raccati sets, which provides an approach to calculate the value functions:

As pointed out in the above remark, the key challenge here is the large number of matrices in each ${\mathcal{H}}_t$ when t becomes large. It was found in Ref. [129] that many matrices in ${\mathcal{H}}_t$ can actually be removed without affecting the optimal value functions. For a matrix P in $\mathcal{H}$, we say that P is algebraic redundant if we can find another ${\mathbf{P}}^{\prime }\in \mathcal{H}$ such that

$\begin{array}{l}\hfill {\mathbf{z}}^T\mathbf{P}\mathbf{z}\ge {\mathbf{z}}^T{\mathbf{P}}^{\prime }\mathbf{z},\end{array}$

for any z with appropriate dimension. Intuitively speaking, P is algebraically redundant if it represents the value of a strategy that is suboptimal in all cases. Then it does not affect the optimality if we omit these algebraically redundant matrices. The following theorem provides a sufficient condition for the redundant matrices [129]:

Based on the above theorem, the procedure for removing algebraically redundant matrices and computing the sets $\{{\mathcal{H}}_t\}$ is given in Procedure 3.

Although Procedure 3 can substantially reduce the complexity of the DP procedure, its complexity is still too high for the case of large time durations. Hence, for practical systems, it is desirable to propose suboptimal but computationally efficient algorithms. One possible approach is to relax the condition of the redundancy in Eq. (7.14) to the following ϵ-redundancy:

$\begin{array}{l}\hfill {\mathbf{z}}^T(\mathbf{P}+ϵ\mathbf{I})\mathbf{z}\ge {\mathbf{z}}^T{\mathbf{P}}^{\prime }\mathbf{z},\end{array}$

where ϵ is a predetermined positive number. The larger ϵ is, the more relaxed the concept of redundancy is and the more matrices can be removed from the sets $\mathcal{H}(t)$. Theorem 43 can be correspondingly changed to the following version:

Then, the algorithm in Procedure 3 can be modified accordingly, and the constant ϵ can be set according to the tradeoff between the complexity and the optimization performance.

The modified algorithm using ϵ-redundancy can work for finite time horizons. However, the complexity increases at least linearly with respect to the time duration T, since the sets $\mathcal{H}(t)$ need to be stored for each t. Hence, the above approaches cannot work in the infinite horizon case, i.e., $T\to \infty$. A practical approach is to fix a sufficiently large T, obtain the optimal (or near-optimal) strategy π_T, and repeat π_T for each time slot in order to approximate the optimal strategy in the infinite time horizon. A key challenge for this approximate approach is whether the resulting strategy can yield stable system dynamics (in the finite time horizon, we do not have this concern). The following theorem provides a sufficient condition for stability (Lemma 7, [129]):

Based on this lemma, Ref. [129] provides an efficient algorithm for designing the control algorithm with the assurance of system stability.

Communication mode

We first define a communication mode as a configuration of the communication network in a CPS, which is discrete. For example, if we consider only the physical layer, a communication mode may correspond to a combination of modulation and coding, e.g., QPSK + convolutional code with transmission rate 1/2; if we consider only the MAC layer, a communication mode may correspond to a set of active communication links scheduled for communications; in the network layer, a communication mode may correspond to a set of routes for different data traffic. A communication mode may be across different layers, e.g., it may specify the configurations of both physical and MAC layers. The communication mode may change with time due to the change of either the information source characteristics or the communication channel qualities. For example, in the physical layer, the mode may be changed if adaptive modulation/coding is employed; in the MAC layer, the active communication links may change with time, which can be determined by a scheduler.

Relationship between communication and dynamics modes

We have defined the communication mode. Now we map each communication mode to a mode of the physical dynamics, which means the law of system state evolution. When different communication modes are used, the controller in a CPS may receive different packets with different delays or different packet drop rates, thus resulting in different dynamics modes. Below we use examples in the physical layer and MAC layer to illustrate the mapping.

Example 2

(Physical Layer)

Here we consider the physical layer communication from a sensor to a controller. Two possible modulations, QPSK and 8-PSK, can be used. Fig.7.3 shows a comparison between QPSK and 8-PSK used by the sensor. We suppose that the same number of bits are used for quanizing each measurement at the sensor and the channel coding is fixed. Obviously, the delay when using QPSK is longer because each QPSK symbol carries fewer bits than the 8-PSK; meanwhile, since the constellation of QPSK is sparser, the demodulation error rate of QPSK is lower. The different communication delays and different error rates result in different actions of the controller and thus different dynamics modes. Then, the evolution of the system state can be written as (consider the discrete-time case)

$\begin{array}{ll}\hfill \mathbf{x}(t+1)& =f(\mathbf{x}(t),g_{e,d}(\mathbf{x}),\mathbf{n}(t))\hfill \\ \hfill & ={\tilde{f}}_{e,d}(\mathbf{x}(-\infty :t),\mathbf{n}(t)),\hfill \end{array}$

  (7.20)

where g is the control action law as a function of the observations, e and d represent the packet error probability level and delay, $\tilde{f}$ is the evolution law taking e, d, and g into account. Obviously, e and d denote the discrete state of a hybrid system, which is determined by the selection of modulation.

Example 3

(MAC Layer)

Fig.7.4 shows a system with two sensors, each monitoring one dimension of the continuous system state x, and one controller. We assume that only one sensor can transmit its measurement at a time, due to co-channel interference. If all other aspects of the communication infrastructure, e.g., modulation and code, are fixed, there are two communication modes in the CPS: one is sensor 1 being scheduled while the other is sensor 2 being scheduled. The equations describing the different dynamics corresponding to different communication modes are also given in Fig.7.4. We observe that the system matrix A and control matrix B do not change, while the observation matrix C changes with the communication mode.

From the examples, we observe that each communication mode corresponds to a unique dynamics mode. Hence a communication mode is equivalent to a dynamics mode, if there are no other external factors affecting the dynamics mode. To fit a CPS into the hybrid system model, we can use the discrete state, i.e., k(t) in (8.19), to indicate the current communication/dynamics mode, and use the continuous system state, i.e., x(t) in (8.19), to model the physical dynamics. For example, in Example 3, k equals either 1 or 2, indicating whether sensor 1 or 2 is scheduled; in each case, either matrix C₁ = (1, 0;0, 0) or C₂ = (0, 0;0, 1) is used in the dynamics equation. Then we can fully exploit the existing conclusions on the observability, controllability, or stability of hybrid systems to analyze or design the communication network in a CPS. Note that a rapid change of the MAC layer links is possible. For example, when the voltages in a microgrid are experiencing an oscillation, it is important to check the measurements of different sensors quickly, thus requiring a fast change of active links.

Generic procedure

The generic procedure of mode provisioning is illustrated in Fig.7.6. It consists of the following steps:

1. Formulate the hybrid system for the given CPS configurations.

2. Add a basic set of communication modes (such as modulation, coding, or scheduling schemes) to the pool.

3. Check the system stability using certain criteria in controls and systems, which will be provided later, and the system complexity.

4. If the system is still unstable and still within the requirement of complexity, add proper unused communication modes to the pool.

5. Finally, the procedure either claims failure or outputs a pool of communication modes that can stabilize the physical dynamics.

Illustration by examples

Centralized mode scheduling

For the generic case, mode scheduling is carried out in the following steps:

1. Define a cost function for the scheduling.

2. For each scheduling period, the scheduler receives certain observations on the current system state.

3. Based on the current system state, the scheduler chooses the communication mode that minimizes the expectation of the cost function using DP (or approximate dynamic programming (ADP) if needed).

4. If the scheduling is in a distributed manner, quantities characterizing the expected cost will be broadcast.

Note that the scheduler can be centralized or decentralized. The procedure will be discussed in the subsequent discussions.

There have been many studies on mode scheduling in generic hybrid systems. For example, Ref. [135] studied the optimization of both states by decomposing the optimization into master and slave problems. A special case of mode scheduling is to schedule the observations of sensors, which is called sensor selection (or sensor switching) in the field of control theory [136]. In the seminal work of Ref. [137], it has been shown that, for linear quadratic Gaussian (LQG) control, which is a very popular framework of controller synthesis due to the explicit and efficient computation of the control actions, the optimal sequence of selected sensors (it is assumed that only one sensor can be selected at a time) can be determined in advance and is independent of the observations. In Ref. [122], the communication delay is taken into account based on delayed Kalman filtering. The sensor selection problems have also been studied in many other publications [138].

We define the scheduling law as a mapping from the system state to the selection of communication mode. We want the scheduling law to minimize the expectation of the system cost, i.e.,

$\begin{array}{l}\hfill k_1^{*}(\mathbf{x}(0))=arg\underset{k_1}{min}E[J|k_1,\mathbf{x}(0)],\end{array}$

where x(0) is the feedback of the system state, k₁ is the first mode selection when seeing the system state x(0), and J is a cost function. Intuitively, the scheduler determines the selection of communication mode to minimize the expected future cost J given the current system observation.

For simplicity, we assume that the cost function is the sum of quadratic functions, i.e.,

$\begin{array}{l}\hfill J=\sum _{t=1}^{T_f}{\mathbf{x}}^T(t)\mathbf{P}\mathbf{x}(t),\end{array}$

where P is a positive definite matrix and T_f is the total number of time slots under consideration. This cost function is reasonable if we desire a small norm of x(t) and different dimensions of x have different priorities. This is reasonable if x denotes the deviation of a system from a desired operation state. We assume that the communication mode can be changed every T_s time slots (which is called a scheduling period) and t_f = T_f/T_s is an integer; i.e., within the window of optimization the scheduler can change the communication mode t_f times. For example, in practical cellular systems, T_s can be the period of each data frame (10 ms in 4G LTE systems).

Theoretically, the optimal scheduling law can be obtained from DP [139]. Carrying out the standard DP, we define the cost-to-go function $J_t^{*}(\mathbf{x}(t))$, t = 1, …, t_f, as

$\begin{array}{ll}\hfill & J_t^{*}(\mathbf{x}((t-1)T_{\text{s}}))\hfill \\ \hfill & =\underset{k_t}{min}E\left[\sum _{\tau =(t-1)T_{\text{s}}+1}^{T_f}\left.{\mathbf{x}}^T(\tau )\mathbf{P}\mathbf{x}(\tau )\right|\mathbf{x}((t-1)T_{\text{s}})\right],\hfill \end{array}$

which is the minimum expected cost in the future given the observation at the beginning of the scheduling period, i.e., x((t − 1)T_s). Applying Bellman’s equation in DP [139], we have

$\begin{array}{ll}\hfill & J_t^{*}(\mathbf{x}((t-1)T_{\text{s}})\hfill \\ \hfill & =\underset{k_t}{min}\left\{E\left[\sum _{\tau =(t-1)T_{\text{s}}+1}^{t{T}_{\text{s}}}\left.{\mathbf{x}}^T(\tau )\mathbf{P}\mathbf{x}(\tau )\right|\mathbf{x}((t-1)T_{\text{s}}),k_t\right]\right.\hfill \\ \hfill & \left.+E\left[J_{t+1}^{*}(\mathbf{x}(t{T}_{\text{s}})|\mathbf{x}((t-1)T_{\text{s}}),k_t)\right]\right\},\hfill \end{array}$

for t = 1, …, t_f − 1, and the final condition is

$\begin{array}{l}\hfill J_{t_f}^{*}(\mathbf{x}((t_f-1)T_{\text{s}})=\underset{k_{t_f}}{min}E\left[\sum _{\tau =(t_f-1)T_{\text{s}}+1}^{T_f{T}_{\text{s}}}\left.{\mathbf{x}}^T(\tau )\mathbf{P}\mathbf{x}(\tau )\right|\mathbf{x}((t_f-1)T_{\text{s}}),k_t\right].\end{array}$

Intuitively, $J_t^{*}(\mathbf{x}((t-1)T_{\text{s}})$ is the minimal expected cost from the tth scheduling to the final time slot, given the final system state at the previous scheduling period. To obtain the cost-to-go functions, we can begin from the last scheduling period in Eq. (7.27) and compute the cost-to-go functions in a time-reversed order. The computation of $J_{t_f}^{*}(\mathbf{x}((t_f-1)T_{\text{s}})$ can be an exhaustive search for every possible communication mode; for each communication mode, the cost within the T_s time slots can either be obtained from Monte-Carlo simulations or explicit expressions (if the noise is Gaussian). Once the cost-to-go functions are obtained, it is straightforward to obtain the optimal decision (i.e., the scheduling law):

$\begin{array}{l}\hfill k_1^{*}(\mathbf{x}(0))=arg\underset{k_t}{min}\left\{E\left[\sum _{\tau =1}^{T_{\text{s}}}\left.{\mathbf{x}}^T(\tau )\mathbf{P}\mathbf{x}(\tau )\right|\mathbf{x}(0),k_t\right]+E\left[J_{t+1}^{*}(\mathbf{x}(T_{\text{s}})|\mathbf{x}(0),k_1)\right]\right\},\end{array}$

which can be computed using an exhaustive search among all possible selections of communication modes.

Although DP can theoretically solve the mode scheduling problem, the corresponding computation is infeasible in practice. The reason is that x is a continuous vector. To obtain the cost-to-go functions for every x, we have to compute uncountably many functions, which is impossible in practical systems.

To alleviate the computational challenge, we can apply ADP [140]. We can assume an explicit expression for the cost-to-go function, which is usually chosen as a mathematically tractable form. For example, in Ref. [141], the cost-to-go function for communication mode scheduling is assumed to be a quadratic function, i.e.,

$\begin{array}{l}\hfill J_t(\mathbf{x})={\mathbf{x}}^T{\mathbf{\Sigma }}_t\mathbf{x},\end{array}$

where Σ_t is a positive definite matrix. Then the problem of estimating the cost-to-go functions is converted to the estimation of the matrices ${\mathbf{\Sigma }}_1,\dots ,{\mathbf{\Sigma }}_{t_f}$. An algorithm for estimating the matrices {Σ_t}_t is proposed in Ref. [130], which is based on Monte-Carlo simulation and matrix equations. We also define the conditional cost

$\begin{array}{l}\hfill J_t(\mathbf{x}|\mathbf{z})={\mathbf{x}}^T{\mathbf{\Sigma }}_{t,\mathbf{z}}\mathbf{x},\end{array}$

where Σ_t, z is a symmetric matrix dependent on z and t, and z = (z₁, …, z_N) is the transmission status of the sensors (z_i = 1 or 0 means that sensor i is active or not).

Distributed scheduling

In the previous discussion of the scheduling algorithm, an implicit assumption is the centralized scheduling; i.e., a centralized scheduler observes the system state x and then maps it to the decision of the communication mode selection. However, such centralized scheduling needs to convey the sensor observations to the scheduler, which may incur much communication overhead and is difficult in many practical applications. Hence it is necessary to study the decentralized scheduling of the communication mode; i.e., the sensors determine their communication modes based on their local observations. Below, we use MAC layer scheduling as an example to illustrate decentralized scheduling.

We can take MAC layer scheduling as an example of distributed scheduling. We assume that the scheduling follows the above optimization framework and the quadratic approximation of the cost-to-go functions in Eq. (7.29) has been obtained in offline computations. Then we assume that the positive definite matrix Σ₁ has dominant diagonal elements; i.e., the diagonal elements have much larger magnitude than the off-diagonal elements. This assumption has been demonstrated to be valid in numerical simulations of voltage control in microgrids [130].

Then the cost can be approximately decomposed to the sum of local costs, which is given by

$\begin{array}{l}\hfill J_1(\mathbf{x},\mathbf{z})\approx \sum _{n=1}^N{\sigma }_{n,z_n}{x}_n^2,\end{array}$

where

$\begin{array}{l}\hfill {\sigma }_{n,z_n}{|}_{z_n=z}=\frac{1}{\#(z_n=z)}\sum _{z_n=z}{\left({\mathbf{\Sigma }}_{1,\mathbf{z}}\right)}_{nn},\end{array}$

where #(z_n = z) is the number of matrices having z_n = z. Recall that Σ_1, z is the symmetric matrix for approximating the conditional cost in Eq. (7.30). The cost can be further written as

$\begin{array}{ll}\hfill J_1(\mathbf{x},\mathbf{z})& =\sum _{n=1}^N\left({\sigma }_{n,1}-{\sigma }_{n,0}\right)x_n^{2}I(z_n=0)\hfill \\ \hfill & =\sum _{n=1}^N{c}_{n}I(z_n=0),\hfill \end{array}$

where I(z_n = 0) is the characteristic function of the event z_n = 0 (i.e., node n is not scheduled) and

$\begin{array}{l}\hfill c_n=({\sigma }_{n,1}-{\sigma }_{n,0})x_n^2,\end{array}$

which is the cost contributed by node n if it is not scheduled. Then, the problem is converted to the following one: every node (say node n) is associated with a potential cost c_n; if node n is scheduled, the cost is zero; otherwise, the cost is c_n; then, we study how to arrange the transmission within the constraint of communication interference such that the sum cost is minimized. If we define the total reward as the negative of the total cost, then the problem is essentially the same as the problem of maximizing the total throughput of the network, or more abstractly the problem of maximizing the total weight of matching in a graph. Many distributed algorithms for the maximization of weighted matching [142], such as a greedy algorithm, can be applied to the distributed scheduling in CPS communications. Procedure 4 shows simple distributed scheduling by broadcasting a number of bits for scheduling before data transmission, in which it is assumed that a mechanism of broadcasting has been implemented (e.g., each transmitter is assigned a very short time slot).

System model

The CPS system considered in Ref. [22] consists of a linear time-invariant (LTI) dynamical system and a communication network, which is illustrated in Fig.7.7.

The system dynamics is given by

$\begin{array}{l}\hfill \left\{\begin{array}{c}\mathbf{z}={\mathbf{G}}_{11}(\psi )\mathbf{w}+{\mathbf{G}}_{12}(\psi ){\mathbf{y}}_r,\\ \mathbf{y}={\mathbf{G}}_{21}(\psi )\mathbf{w}+{\mathbf{G}}_{22}(\psi ){\mathbf{y}}_r,\end{array}\right.\end{array}$

where {G_ij} are the LTI operations that are dependent on the design parameter ψ. It is assumed that y(t) and y_r(t) are both M-dimensional real vectors. y consists of M scalar signals, y₁, …, y_M, sent through the communication network at each time slot, while y_r is the received signals y_r1, …, y_rM. y and y_r are related by a memoryless scalar quantizer.

A uniform quantizer is used, which partitions the interval [−1, 1] into 2^b segments. It is assumed that each scalar signal y_i has an amplitude bound s_i. Hence the signal y_i is put into the quantizer after being normalized by s_i, namely

$\begin{array}{l}\hfill y_{ri}(t)=s_i{Q}_{b_i}\left(\frac{y_i(t)}{s_i}\right),\end{array}$

where $Q_{b_i}$ denotes the uniform quantization function with b_i bits. The quantization error is given by

$\begin{array}{l}\hfill q_i(t)=y_{ri}(t)-y_i(t),\end{array}$

which is assumed to be uniformly distributed in the interval $s_i[-2^{-b_i},2^{-b_i}]$.

Then the system dynamics can be rewritten as

$\begin{array}{l}\hfill \left\{\begin{array}{c}\mathbf{z}={\mathbf{G}}_{zw}(\psi )\mathbf{w}+{\mathbf{G}}_{zq}(\psi )\mathbf{q},\\ \mathbf{y}={\mathbf{G}}_{yw}(\psi )\mathbf{w}+{\mathbf{G}}_{yq}(\psi )\mathbf{q},\end{array}\right.\end{array}$

where G_zw, G_zq, G_yw, and G_yq are closed-loop transfer matrices. Since w is independent of q, the variance of z is then given by

$\begin{array}{ll}\hfill V& =E[\parallel \mathbf{z}{\parallel }^2]\hfill \\ \hfill & =V_q+E[\parallel {\mathbf{G}}_{zw}\mathbf{w}{\parallel }^2],\hfill \end{array}$

where V_q is the variance of z due to the quantization error, which is given by

$\begin{array}{ll}\hfill V_q& =E[\parallel {\mathbf{G}}_{zq}\mathbf{q}{\parallel }^2]\hfill \\ \hfill & =\sum _{i=1}^M{a}_i{2}^{-2b_i},\hfill \end{array}$

with

$\begin{array}{l}\hfill a_i=\frac{1}{3}\parallel {\mathbf{G}}_{zqi}{\parallel }^2{s}_i^2.\end{array}$

Communication constraints

The vector of bits allocated to every quantized signal is denoted by b while the corresponding communication rates are denoted by r (bits per second). It is easy to verify that

$\begin{array}{l}\hfill b_i=\frac{c_{\text{s}}{r}_i}{f_{\text{s}}},\end{array}$

where f_s is the sampling frequency and c_s is the channel coding rate (information bits per coded bit). The following constraints are used for the bit allocations:

$\begin{array}{l}\hfill \left\{\begin{array}{c}{f}_i(\mathbf{b},\theta )\le 0,i=1,\dots ,m_f,\\ {\mathbf{h}}_i^T\theta \le d_i,i=1,\dots ,m_h,\\ {\theta }_i\ge 0,i=1,\dots ,m_{\theta },\\ b_{il}\le b_i\le b_{iu},i=1,\dots ,M.\end{array}\right.\end{array}$

These constraints are explained as follows:

• We assume that functions {f_i} are convex; they are monotonically increasing in b and monotonically decreasing in θ. They represent the constraints on the communication capacities. For example, in the Gaussian noise channel, we have

$\begin{array}{l}\hfill f(b,W,P)=b-\alpha W{log}_2\left(1+\frac{P}{NW}\right)\le 0,\end{array}$

where W is the bandwidth, P is the transmission power, N is the noise power spectrum density, and α is the discount on the Shannon capacity due to the performance loss in practical coding schemes.

• The constraints ${\mathbf{h}}_i^T\theta \le d_i$ represent the limitations on the communication resources. Take the broadcast channel as an example. Suppose that the total available power is P and the total bandwidth is W. Then the constraints become

$\begin{array}{l}\hfill W_1+W_2+\cdots +W_n=W\end{array}$

and

$\begin{array}{l}\hfill P_1+P_2+\cdots +P_n=P.\end{array}$

• The constraints θ_i ≥ 0 mean that the allocated communication resource must be nonnegative. For example, the transmission power and bandwidth must be nonnegative.

• The constraints b_il ≤ b_i ≤ b_iu put limitations on the communication resource that can be allocated to one agent.

Then the resource allocation/scheduling is formulated as an optimization problem, which is given by

$\begin{array}{l}\hfill \begin{array}{cc}& \underset{\{b_i\}}{min}\sum _{i=1}^M{a}_i{2}^{-2b_i}\\ s.t.& f_i(\mathbf{b},\theta )\le 0,& i=1,\dots ,m_f\\ & {\mathbf{h}}_i^T\theta \le d_i,& i=1,\dots ,m_h\\ & {\theta }_i\ge 0,& i=1,\dots ,m_{\theta }\\ & b_{il}\le b_i\le b_{iu},& i=1,\dots ,M.\end{array}\end{array}$

Delay-tolerant Kalman filtering

Here, we provide a brief introduction to delay-tolerant Kalman filtering, which was originally proposed in Ref. [122]. It is well known that, in traditional Kalman filtering, the expectation and covariance of x are given by

$\begin{array}{ll}\hfill \stackrel{-}{\mathbf{x}}(t|t-1)& =\mathbf{A}\stackrel{-}{\mathbf{x}}(t|t)+\mathbf{B}\mathbf{u}(t),\hfill \end{array}$

$\begin{array}{ll}\hfill \mathbf{\Sigma }(t|t-1)& =\mathbf{A}\mathbf{\Sigma }(t-1|t-1){\mathbf{A}}^T+\mathbf{W},\hfill \end{array}$

$\begin{array}{ll}\hfill \mathbf{\Sigma }(t|t)& ={[{\mathbf{\Sigma }}^{-1}(t|t-1)+{\mathbf{C}}^T{\mathbf{N}}^{-1}\mathbf{C}]}^{-1},\hfill \end{array}$

and

$\begin{array}{ll}\hfill \stackrel{-}{\mathbf{x}}(t|t)& =\stackrel{-}{\mathbf{x}}(t|t-1)\hfill \\ \hfill & +\mathbf{\Sigma }(t|t){\mathbf{C}}^T{\mathbf{N}}^{-1}(\mathbf{y}(t)-\mathbf{C}\stackrel{-}{\mathbf{x}}(t|t-1)),\hfill \end{array}$

where the subscripts m|n (m ≥ n) denote the quantities for time m given observations until time n.

According to Ref. [144], Eqs. (7.50) and (7.51) can be rewritten as

$\begin{array}{l}\hfill {\mathbf{\Sigma }}^{-1}(t|t)={\mathbf{\Sigma }}^{-1}(t|t-1)+\sum _{m=1}^M{\mathbf{c}}_{\text{m}}^T{\mathbf{N}}_{mm}^{-1}{\mathbf{c}}_{\text{m}},\end{array}$

where c_m is the mth row of matrix C and

$\begin{array}{ll}\hfill {\mathbf{\Sigma }}^{-1}(t|t)\stackrel{-}{\mathbf{x}}(t|t)& ={\mathbf{\Sigma }}^{-1}(t|t)\stackrel{-}{\mathbf{x}}(t|t-1)\hfill \\ \hfill & +\sum _{m=1}^M{\mathbf{c}}_{\text{m}}^T{\mathbf{N}}_{mm}^{-1}{y}_{\text{m}},\hfill \end{array}$

which is called the information form of Kalman filtering [144].

Based on the information form of Kalman filtering, the delay-tolerant Kalman filtering maintains a window lasting for L time slots and a set of buffers. Whenever observations, which could have been delayed, are received, these buffers are updated and then are used to update the estimations and error matrices.

Definition of virtual queues

In delay-tolerant Kalman filtering, different messages have different levels of importance and provide different amounts of information to the controller. We first evaluate the amount of information in each message and then define the virtual queue.

Information bits

Given a measurement y that has not been received and a set of measurements received at the controller $\mathcal{Y}$ ($y\notin \mathcal{Y}$), its amount of information is evaluated by computing the mutual information between y and $\widehat{\mathbf{x}}$ [122],² i.e.,

$\begin{array}{l}\hfill I(y;\widehat{\mathbf{x}}|\mathcal{Y})=E\left[log\left(\frac{p(\widehat{\mathbf{x}}|\mathcal{Y},y)}{p(\widehat{\mathbf{x}}|y)}\right)\right],\end{array}$

where $\widehat{\mathbf{x}}$ is the system state estimation and the expectation is with respect to the randomness in the observation. Obviously, if the mutual information $I(y;\widehat{\mathbf{x}})$ is large, the common information between the observation y and the estimation based on other observations is large, which implies that y can provide much information for system state estimation, once being delivered at the controller, and thus is very important. On the other hand, if the mutual information is small, the measurement y cannot provide significant new information for the purpose of system state estimation. Hence it is reasonable to use $I(y;\widehat{\mathbf{x}})$ to measure the information bits (although not rigorously) that the measurement y carries for the purpose of system state estimation.

In Ref. [122], it was shown that the mutual information in Eq. (7.54) is given by

$\begin{array}{l}\hfill I(y;\widehat{\mathbf{x}})=\frac{1}{2}E\left[log\left|\mathbf{\Sigma }{\mathbf{\Sigma }}_{\mathcal{Y},y}^{-1}\right|\right],\end{array}$

where Σ and ${\mathbf{\Sigma }}_{\mathcal{Y},y}$ are the error covariance matrices without and with the observation y, and the expectation is with respect to the randomness of y.

When the value of y is known, e.g., y₀, we claim that the following quantity specifies the number of bits the observation y can bring to the estimation:

$\begin{array}{l}\hfill i(y_0;\widehat{\mathbf{x}})=\frac{1}{2}log\left|\mathbf{\Sigma }{\mathbf{\Sigma }}_{\mathcal{Y},y_0}^{-1}\right|.\end{array}$

The expression in Eq. (7.56) is intuitive. When x is scalar, Eq. (7.56) becomes

$\begin{array}{l}\hfill i(y_0;\widehat{\mathbf{x}})=\frac{1}{2}log\frac{\sigma }{{\sigma }_{\mathcal{Y},y_0}},\end{array}$

where σ is the mean square error (MSE) of x. When i is large, the MSE given $\mathcal{Y}$ and y₀ is much smaller than that given only $\mathcal{Y}$, which implies that the reception of y₀ can significantly reduce the MSE of x.

Based on the discussion of the information bits brought by each measurement, we can define the virtual queue. We assume that a transmitter has R measurements denoted by y¹, y², …, y^R in its buffer, all waiting to be transmitted. The set of measurements that the destination controller has received in the history (including the R measurements) is denoted by $\mathcal{Y}$. Then, we assume that the number of bits in its virtual queue is given by

$\begin{array}{l}\hfill Q=\sum _{k=1}^{R}i(y^k;\widehat{\mathbf{x}}).\end{array}$

Distributed scheduling

Based on the concept of virtual queues, we propose a distributed scheduling algorithm for the purpose of stabilizing the physical dynamics in a CPS. We first describe the procedure of evaluating the queue length at each transmitter. Then we modify and apply the back-pressure scheduling algorithm.

In the distributed scheduling, each transmitter (either a source node or an intermediate node) evaluates the length of its virtual queue. To that purpose, it needs to estimate Σ and ${\mathbf{\Sigma }}_{\mathcal{Y},y}$ for a measurement y. Here $\mathcal{Y}$ is the set of measurements the controllers have received. The following two actions will be taken by the node:

• Estimation of $\mathcal{Y}$: The node may not be able to know whether a measurement that it has transmitted has been received by the destination node since the acknowledgment (ACK) could be lost or could be on the way. It can either use the ACKs it has received to estimate $\mathcal{Y}$, which is more conservative, or simple assume that all the measurements it has transmitted have been received, which is more risky. We will use the latter approach in this chapter.

• Computation of Σ and ${\mathbf{\Sigma }}_{\mathcal{Y},y}$: The node carries out delay-tolerant Kalman filtering in order to compute the above two matrices.

Once the virtual queue length is evaluated at each node, they can use the queue length for the scheduling. In this chapter, we use a heuristic algorithm. As we have assumed, before the transmission of a packet, there is a scheduling period. We assume that each node can broadcast its current virtual and real queue lengths to its neighbors during the scheduling period. The detailed design of the queue length broadcast is omitted here. Once receiving the queue lengths, each node can compute the back pressures of itself and its neighbors. Then a node transmits only when there is no neighbor having a higher back pressure. However, it is not straightforward to apply the traditional concept of back pressure.

In traditional queuing networks with multiple flows, the back pressure of node i is given by

$\begin{array}{l}\hfill b_i=\underset{f\in F_i,j=n(f,i)}{max}{\mu }_{ij}(q_i(f)-q_j(f)),\end{array}$

where μ_ij is the service rate of the link from node i to node j, F_i is the set of flows flowing through node i, q_i(f) is the queue length of flow f at node i, and n(f, i) is the next hop neighbor of node i for flow f. In the context of a CPS with physical dynamics, we have the following concerns:

• Virtual queue and actual queue: In Eq. (7.59), q_i(f) represents the motivation to transmit the packet while q_j(f) is the impedance to prevent packet transmission. In this chapter, we propose to use the virtual queue length for q_i, which measures the desire to transmit, and use the actual queue length for q_j, which means the congestion of the downstream node.

• Multicasting: In the scenario of this chapter, one transmission can possibly send the packet to multiple next-hop neighbors. Then, it is not intuitive what should be used for q_j in Eq. (7.59). We will test three possible options, namely the average, the maximum, or the minimum of the actual queue lengths of the next-hop neighbors.

• Estimation of $\mathcal{Y}$: When evaluating the virtual queue length, the node needs to know the set of received packets at the controllers, namely $\mathcal{Y}$, such that it can evaluate the importance of each packet in the queue. In this chapter, we assume that $\mathcal{Y}$ is the set of packets the node has sent out, with the implicit assumption that all packets have been received by the controllers.

Summarizing the above discussions, we define the back pressure at node i as

$\begin{array}{l}\hfill b_i=\underset{f}{max}h\left({\{{\mu }_{ij}\}}_{j\in n(i,f)}\right)\left(Q_i(f)-h\left({\{q_{ij}(f)\}}_{j\in n(i,f)}\right)\right),\end{array}$

where the function h is average, max or min, Q is the virtual queue length, and q is the real queue length. Note that it is difficult to derive this definition of back pressure from first principles. However, numerical simulations will demonstrate the validity of this framework. The scheduling algorithm is summarized in Procedure 5.

The proposed scheduling algorithm has been tested in the context of smart grids and has achieved good performance [143].

System model

We assume that the system state evolution law is given by the following linear and discrete-time equation:

$\begin{array}{l}\hfill \mathbf{x}(t+1)=\mathbf{A}\mathbf{x}(t)+\mathbf{w}(t),\end{array}$

where w(t) is white Gaussian noise with covariance matrix Σ_w. The observation measured by a sensor is given by

$\begin{array}{l}\hfill \mathbf{y}(t)=\mathbf{C}\mathbf{x}(t)+\mathbf{v}(t),\end{array}$

where v is also white Gaussian noise with covariance matrix Σ_v. The sensor sends the observations to an estimator, which estimates the system state based on the received observation, via a communication network. It is assumed that the sensor encodes the observation into an n_d-dimensional real vector s at each time slot. The message sent out by the sensor, s(t), is a function of all the previous observations at the sensor.

Note that, in digital networks, it is impossible to transmit a real number without any distortion. However, the analysis on quantized real numbers is challenging. Hence we assume that the real vectors can be sent directly, which is reasonable if the number of bits used to encode the vector is large and the quantization error is negligible.

The communication network incurs communication delay (denoted by d(t)) of the message s(t). We assume that the communication delay is dependent on the previous τ delays (hence the memory has a length τ); i.e.,

$\begin{array}{l}\hfill P(d(t)|d(t-1),\dots ,d(0))=P(d(t)|d(t-1),\dots ,d(t-\tau )).\end{array}$

It is not assumed that the encoder has knowledge about the previous delays. The estimator uses all the previously received signals to estimate the system state, and the corresponding error covariance is given by

$\begin{array}{l}\hfill \mathbf{P}(t)=E[(\mathbf{x}(t)-{\widehat{\mathbf{x}}}_{\mathrm{dec}}(t)){(\mathbf{x}(t)-{\widehat{\mathbf{x}}}_{\mathrm{dec}}(t))}^T],\end{array}$

where ${\widehat{\mathbf{x}}}_{\mathrm{dec}}(t)$ is the estimation of x(t). Because of the time-varying channel qualities, the error covariance P(t) can be considered as a random variable, whose moments should be characterized. In Ref. [24], the expectation of P is studied.

If the packets go through a network to reach the destination, it is assumed that different communication links incur independent delays to the packet. Then the goal of routing is to find a path from the sensor to the controller for minimizing the error covariance in the steady state.

Encoder and decoder

The following encoder and decoder are assumed in Ref. [24]:

• Encoder: At time t the sensor estimates the system state from the observations {y(s)}_s≤t by using Kalman filtering, and sends out the estimate $\widehat{\mathbf{x}}(t)$.

• Decoder: At time t, the estimator obtains the estimation of the system state by using different approaches in the following different situations:

• If no packet arrives, the estimator updates the estimate using

$\begin{array}{l}\hfill {\widehat{\mathbf{x}}}_{\mathrm{dec}}(t)=\mathbf{A}{\widehat{\mathbf{x}}}_{\mathrm{dec}}(t-1).\end{array}$

• If a packet with the newest time stamp (newer than all the other previously received packets) is sent out at time m, the estimator updates the system state estimate by using

$\begin{array}{l}\hfill {\widehat{\mathbf{x}}}_{\mathrm{dec}}(t)={\mathbf{A}}^{t-m}\widehat{\mathbf{x}}(m).\end{array}$

Note that there may be other packets with older time stamps arriving. They will be discarded.

– If one or more packets arrives with time stamps older than a previously received one, the estimator discards these packets and uses Eq. (7.65) to update the system state estimation.

The following theorem guarantees the optimality of the above encoder and decoder scheme:

Evolution of covariance

The error covariance of system state estimation is denoted by Σ(t), which is given by

$\begin{array}{l}\hfill \mathbf{\Sigma }(t)=E[(\widehat{\mathbf{x}}(t|{\{\mathbf{y}(s)\}}_{s\le t})-\mathbf{x}(t)){(\widehat{\mathbf{x}}(t|{\{\mathbf{y}(s)\}}_{s\le t})-\mathbf{x}(t))}^T].\end{array}$

It is easy to verify that the evolution of the error covariance is described by

$\begin{array}{l}\hfill \mathbf{\Sigma }(t+1)=f(\mathbf{\Sigma }(t)),\end{array}$

where f is the Lyapunov recursion, which is given by

$\begin{array}{l}\hfill f(\mathbf{X})=\mathbf{A}\mathbf{X}{\mathbf{A}}^T+{\mathbf{R}}_w.\end{array}$

We denote by t_s(k) the latest time stamp among all the packets received by time k. Then, it was shown in Ref. [24] that the expected error covariance matrix for x(t + 1) at the estimator is given by

$\begin{array}{l}\hfill E[\mathbf{P}(t+1)]=\sum _{m=-1}^{k}P(t_{\text{s}}(k)=m)f_{k-m}(M(m+1)).\end{array}$

The following theorem shows a necessary condition for the stability of the encoder-decoder design:

A straightforward conclusion from the theorem is given as follows:

An interesting observation is that the system stability is only affected by the packet loss probability and is independent of the delay profile, which is counterintuitive.

An example in Ref. [24] is provided to show that it is not necessarily optimal to minimize the expected delay during the routing procedure. Consider the following system having scalar dynamics:

$\begin{array}{l}\hfill x(t+1)=1.2x(t)+w(t),\end{array}$

where w(t) has variance 1. The initial state has variance P(0) = 1. The observation of a sensor is given by

$\begin{array}{l}\hfill y(t)=x(t)+v(t),\end{array}$

where the noise v(t) has power 1. Consider the following two delay profiles:

$\begin{array}{l}\hfill P_1:P(d=5)=1\end{array}$

and

$\begin{array}{l}\hfill P_2:P(d=m)=\left\{\begin{array}{c}1/6,m=1,\\ 5/6,m=6.\end{array}\right.\end{array}$

Obviously, both delay distributions have the same expectation. However, a simple calculation shows that the error covariances of P₁ and P₂ are 23.88 and 17.34, respectively. If the expectation of P₂ is slightly increased by increasing P(d = 6) (simultaneously decreasing P(d = 0)), the error covariance of P₂ is still smaller than that of P₁, although P₂ actually results in a larger expected delay.

To study the relationship between expected delay and error covariance more systematically, we define the modified delay r as a random variable having the following distribution:

$\begin{array}{l}\hfill P(r=-1)=\prod _{j=0}^{k}P(d(t)>j)\end{array}$

and

$\begin{array}{l}\hfill P(r=m)=P(d(t)\le t-m)\prod _{j=0}^{t-m-1}P(d(t)>j).\end{array}$

Then it is easy to verify that

$\begin{array}{l}\hfill E(\mathbf{P}(t+1))=\sum _{m=-1}^{t}P(r=m)f_{t-m}(\mathbf{M}(m+1)).\end{array}$

Before proceeding to the next conclusion, we need to define the stochastic dominance:

Since the delay distribution is the key consideration in the selection of paths in the routing procedure, the following theorem provides a principle for designing routing algorithms for the purpose of system state estimation:

The following theorem was presented in Ref. [24], and is illustrated in Fig.7.8

:

Based on this theorem, the following routing algorithm was proposed in Ref. [24]. Essentially the algorithm is very similar to the shortest path ones such as the celebrated Dijkstra algorithm. The key difference is that the cost in this procedure is related to the cost of system state estimation.

System model

We assume that there are N_c controllers and N_s sensors in the CPS, all being decentralized. For simplicity, we assume that the control action at each controller is scalar, as is the observation at each sensor. This simplifies the mathematical notation and can be straightforwardly extended to the generic case of vector control actions or vector observations.

For simplicity, we assume that the dynamics of the physical subsystem is linear and free of perturbations, and given by

$\begin{array}{l}\hfill \left\{\begin{array}{c}\stackrel{.}{\mathbf{x}}(t)=\mathbf{A}\mathbf{x}(t)+\mathbf{B}\mathbf{u}(t),\\ \mathbf{y}(t)=\mathbf{C}\mathbf{x}(t),\end{array}\right.\end{array}$

where x is an M-vector representing the system state; u is the N_c-dimensional vector of control actions where $u_{n_c}$ stands for the control action of controller n_c; y is the N_s-dimensional vector of observations at the sensors where $y_{n_{\text{s}}}$ is the observation at sensor n_s. The dimensions of matrices A, B, and C are M × M, M × N_c, and N_s × M, respectively. Note that the assumption of linear dynamics is valid for linear systems and is also effective for nonlinear systems when the system state deviates only slightly from an equilibrium point. It is much more challenging to study the general nonlinear case, which is a topic for future work. We also note that we do not consider random perturbations, such as noise in the observations, in the system. The only uncertainty is the initial condition in the system dynamics (otherwise, if the initial state is also known, there is no need for communications). The study of this deterministic system will be extended to stochastic systems in future.

We assume that the N_c controllers and N_s sensors are all equipped with communication interfaces, either wired or wireless. There are also N_r relay nodes in the communication network, which can help with the delivery of observations from the sensors to the controllers. We denote the three types of nodes by ${\{n_c\}}_{n_c=1,\dots ,N_c}$, ${\{n_{\text{s}}\}}_{n_{\text{s}}=1,\dots ,N_{\text{s}}}$, and ${\{n_r\}}_{n_r=1,\dots ,N_r}$, where the subscripts represent the types of nodes. We call the data flow from a sensor to a controller a connection. The topology of the communication network composed of the three types of nodes is known in advance. For a wired network, the topology is determined by the existence of a wired link; for a wireless network, the topology is determined by the distances among the nodes. We use the notation a ∼ b to signify that nodes a and b are directly connected in the communication network.

We make the following assumptions on the communication network throughout in order to simplify the analysis:

• Fluid traffic: We consider the data flows from sensors to controllers to be continuous; i.e., we ignore the details of sampling, quantization, and possible packet dropout. Although the effects of sampling interval, quantization error, and packet drop probability on the system dynamics have been intensively studied in the area of networked control [19], it renders the analysis prohibitively complicated to consider all these details. This fluid traffic assumption can simplify the analysis and is valid when the sampling rate is high, the quantization error is very small, and the communication channels are of very good quality.

• Bandwidth constraint: We assume that transmitting the data flow of one sensor requires one unit of bandwidth. The bandwidth of the communication link between nodes a and b is assumed to be an integer and is denoted by w_ab (in units of bandwidth). Hence the link can support data flows from at most w_ab sensors:

$\begin{array}{l}\hfill \sum _{n_{\text{s}}=1}^{N_{\text{s}}}I(n_{\text{s}},a,b)\le w_{ab},\end{array}$

where I(n_s, a, b) equals 1 if the data flow of sensor n_s passes through link ab; otherwise, I(n_s, a, b) = 0.

• Routing mode switching: We assume that there are a total of Q different routing modes, and that the routing mode can be switched every τ seconds. For simplicity, we consider a simple round-robin switching policy; i.e., the routing mode is selected in the order 1, 2, …, Q. The performance can be improved by adaptively selecting the routing mode. However, the mode decision needs to be carried out in a decentralized manner.

Single mode routing

We first consider the case in which there is only one routing mode (or path design). We assume that linear feedback control is employed for the CPS, which is given by

$\begin{array}{l}\hfill \mathbf{u}(t)=\mathbf{K}\mathbf{y}(t),\end{array}$

where K is a constant feedback gain matrix. Note that K is dependent on the routing mode. Since we consider decentralized control, the matrix K has a special structure, i.e.,

$\begin{array}{l}\hfill {\mathbf{K}}_{ij}=0,\end{array}$

if there is no connection between sensor j and controller i, such that the control action u_i is independent of the observation y_j. Equivalently, the nonzero elements of the ith row of K correspond to the sensors having connections to controller i. For instance, in the example in Fig.7.9, the matrix K is given by

$\begin{array}{l}\hfill \mathbf{K}=\left(\begin{array}{ccc}{K}_{11}& K_{12}& K_{13}\\ K21& K_{22}& 0\\ 0& 0& K_{33}\\ \end{array}\right).\end{array}$

Substituting Eq. (7.83) into Eq. (7.81), we obtain the system dynamics, which is given by

$\begin{array}{ll}\hfill \stackrel{.}{\mathbf{x}}(t)& =\mathbf{A}\mathbf{x}(t)+\mathbf{B}\mathbf{K}\mathbf{C}\mathbf{x}(t)\hfill \\ \hfill & =\tilde{\mathbf{A}}\mathbf{x}(t),\hfill \end{array}$

where $\tilde{\mathbf{A}}\triangleq \mathbf{A}+\mathbf{B}\mathbf{K}\mathbf{C}$.

Then we consider how to optimize the single routing mode. The key challenge is how to determine the set of destinations. Given an arbitrary routing mode, if the feedback gain matrix K is determined in advance,³ we can simply check the eigenvalues of $\tilde{\mathbf{A}}$: if the real parts of all eigenvalues are in the left half of the complex plane, the system is stable (here the stability means that all trajectories of the dynamics converge to a unique equilibrium point [133]); otherwise, it is unstable. In this chapter, we consider the nontrivial design of K given the routing mode. First we obtain the following proposition stating a sufficient condition for system stability. The proof is very simple and a very similar one can be found on page 30 of Ref. [145].

Proposition 4 provides a sufficient condition for judging whether a given routing mode can stabilize the system. The difficulty is how to find suitable matrices P and K. We take an approach similar to that in Ref. [145] via the following two steps:

1. Computation of P: Assume that A is unstable.⁵ Suppose that there exists a β > 0 such that A − βI is unstable and there exists a positive definite matrix P such that

$\begin{array}{l}\hfill (\mathbf{A}-\beta \mathbf{I})\mathbf{P}+\mathbf{P}{(\mathbf{A}-\beta \mathbf{I})}^T=-\mathbf{I}.\end{array}$

Note that the rationale of Eq. (7.88) is to make the feasible set of the optimization problem Eq. (7.89), which will be discussed forthwith, nonempty.

2. Computation of K: Given P, we obtain K by considering the following optimization problem:

$\begin{array}{ll}\hfill & \underset{\mathbf{K}}{max}\gamma \hfill \\ \hfill \text{s.t.}& {\mathbf{A}}^T\mathbf{P}+{(\mathbf{B}\mathbf{K}\mathbf{C})}^T\mathbf{P}+\mathbf{P}\mathbf{A}+\mathbf{P}\mathbf{B}\mathbf{K}\mathbf{C}+\gamma \mathbf{I}<0\hfill \\ \hfill & K_{ij}=0,\text{if sensor}j\text{is not connected to controller}i\hfill \\ \hfill & \parallel \mathbf{K}{\parallel }_2\le c_K,\hfill \end{array}$

where the last constraint is to prevent the feedback matrix K from being prohibitively large (c_K is the upper bound of the 2-norm of K). Using the Schur complement formula [133], it is easy to verify that the constraint ∥K∥₂ ≤ c_K is equivalent to the following linear matrix inequality [145, p. 33], which is easier to manipulate mathematically:

$\begin{array}{l}\hfill \left(\begin{array}{cc}-c_K\mathbf{I}& {\mathbf{K}}^T\\ \mathbf{K}& -\mathbf{I}\\ \end{array}\right)<0.\end{array}$

It is easy to verify that, if the optimal value of Eq. (7.89) is positive, then the condition Eq. (7.87) holds. Note that the optimization problem in Eq. (7.89) can be readily solved using the theory of LMI.

Based on the above discussion, we are able to check the stability of the system given the routing mode; meanwhile, we can also construct the stabilizing feedback gain matrix K (if possible), as a byproduct. Now the challenge is how to find a routing mode such that the optimal γ is positive (thus stabilizing the system). Formulated as an optimization problem, the search for a routing mode stabilizing the system dynamics is to maximize γ; i.e.,

$\begin{array}{ll}\hfill & \underset{\mathcal{R}}{max}\gamma (\mathcal{R})\hfill \\ \hfill \text{s.t.}& \mathcal{R}\text{satisfies the bandwidth constraint},\hfill \end{array}$

where $\mathcal{R}$ stands for a routing mode and γ is a function of $\mathcal{R}$ which can be obtained in Eq. (7.89). The difficulty is that it is too complicated to analytically describe the relationship between the routing mode and the objective function γ. Currently, we still do not have an analytic approach to find the stabilizing routing mode. Moreover, it is prohibitively complicated to carry out an exhaustive search. In the next subsection, we will propose a heuristic algorithm to search for such a routing mode in a greedy manner.

Multiple routing modes

Now we consider the case in which the system can switch among multiple routing modes. Recall that there is a total of Q routing modes. We denote by K_q the feedback gain matrix corresponding to the qth routing mode. Then the system dynamics can be written as

$\begin{array}{l}\hfill \dot{\mathbf{x}}(t)={\tilde{\mathbf{A}}}_{q(t)}\mathbf{x}(t),\end{array}$