Source coding

We know that the purpose of source coding is to convert the original information source into information bits. The main challenge of source coding in a CPS is how to adapt the source coding scheme to the physical dynamics. In Section 8.3 we consider the point-to-point case, in which there is a single sensor and a single controller. Then the source coding is extended to the distributed case in Section 8.4, where we consider multiple sensors.

Channel coding

Channel coding is used to protect the communication from noise and interference. The challenge of channel coding in a CPS is how to embed the channel coding procedure into the control procedure. In Section 8.5 we consider existing channel codes but integrate the decoding procedure into the system state estimation. In Section 8.6 the channel codes are specially designed for the purpose of control in a CPS. Since control can be considered as a special case of computing, the channel codes are designed in the context of distributed computing in Section 8.7.

8.2.1 System Model

Physical dynamics

Continuous-time physical dynamics are considered, whose evolution is described by the following differential equation:

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

where x(t) is the N-dimensional system state, u(t) is the M-dimensional control action, and A and B are both system parameters which are assumed to be perfectly known. Here the physical dynamics are deterministic. The analysis of stochastic systems is much more complicated, and is beyond the scope of our discussion. A sensor is used to measure the system state x. It is assumed that there is no measurement noise. Then the sensor sends the measurements in a digital communication channel to the controller. We assume that linear feedback control is used by the controller in the ideal case; i.e.,

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

where K is the feedback gain matrix, which is predetermined before system operation. For example, it can be obtained from the linear quadratic regulator (LQR) controller.

Communication channel

The number of bits used to quantize the measurement at the sensor is denoted by B. For simplicity of analysis, we ignore the quantization error. This is reasonable if B is sufficiently large, which is true in practical systems (otherwise the control will be unreliable and that analysis is also complex). The symbol rate is R symbols per second, which is fixed. Hence for different modulation schemes, the communication delays are different since different numbers of symbols are needed to convey the B bits. We assume that there are S available modulation schemes, among which the sensor can switch. This is reasonable in modern software-defined radio systems. In the sth modulation scheme, each symbol contains b_s bits (e.g., a 8PSK contains 3 bits). Hence the time needed to convey the B bits is given by

$\begin{array}{l}\hfill T_{\text{s}}=\frac{B}{b_{\text{s}}R},\end{array}$

for the sth modulation scheme.

It is possible that the sensor cannot switch the modulation scheme freely, since usually the switching time is nonnegligible. Therefore we assume that the modulation scheme can be changed every T_m seconds. The time period of sampling for measurement is denoted by $\mathcal{T}$. The following assumptions are used for simplicity of analysis:

• We assume $\mathcal{T}>T_{\text{s}}$, for all possible s; i.e., any measurement can always be sent out (but not necessarily reach the controller) before the next sample arrives.

• We assume that $t_{\text{m}}=T_{\text{m}}/\mathcal{T}$ is an integer; i.e., each modulation scheme can be used for t_m samples after being activated.

Since noise exists in the communication channel, it is possible that packet loss occurs. The packet loss rate of the sth modulation scheme is denoted by P_e, s. For simplicity, we assume that all the transmission errors can be detected (but not corrected). Since the communication is highly real-time, we assume that there is no retransmission in the communications even if a packet is dropped.

Suppose that the sth scheme starts from time 0. The control action u at time t is determined by linear feedback control:

$\begin{array}{l}\hfill \mathbf{u}(t)=-\mathbf{K}\mathbf{x}({\tau }_{\text{s}}(t)),\end{array}$

where τ_s(t) is the time of the nearest sample of the system state:

$\begin{array}{l}\hfill {\tau }_{\text{s}}(t)=max\{(n-1)T_{\text{s}}|n{T}_{\text{s}}\le t\}.\end{array}$

Compared with Eq. (8.2), we replace the instantaneous feedback x(t) with the closest observation x(τ_s(t)), by assuming that the error between x(t) and x(τ_s(t)) is small, which is reasonable if the system dynamics do not change very rapidly.

When transmission error occurs, the following two possible approaches are considered to synthesize u:

• Zero observation upon transmission failure (ZOTF): When x(t) is not successfully received, we set x(t) = 0 and then obtain u(t) = 0; i.e., the controller takes zero control action.

• Most recent observation upon transmission failure (MROTF): When x(t) is not successfully received, the controller uses the most recent sample of x as a reasonable estimation of x(t).

Impact of communication delay

In Ref. [16], the impact of communication delays on the system dynamics has been analyzed by assuming that the delay is shorter than the sampling period. Essentially, the analysis converts the controlled system with communication delay into an equivalent discrete-time system, whose state is defined as

$\begin{array}{l}\hfill \mathbf{z}(k)=(\mathbf{x}(k\mathcal{T}),\mathbf{u}((k-1)\mathcal{T})),\end{array}$

and the evolution law of dynamics is given by

$\begin{array}{l}\hfill \mathbf{z}(k+1)={\mathbf{\Phi }}_s\mathbf{z}(k),\end{array}$

where, when the sth modulation scheme is used, the matrix Φ_s is given by

$\begin{array}{l}\hfill {\mathbf{\Phi }}_{\text{s}}=\left(\begin{array}{ll}\mathbf{\Psi }-{\mathbf{\Gamma }}_0(T_{\text{s}})\mathbf{K}& {\mathbf{\Gamma }}_1(T_{\text{s}})\\ -\mathbf{K}& 0\end{array}\right),\end{array}$

where

$\begin{array}{l}\hfill \left\{\begin{array}{l}\mathbf{\Psi }={\mathrm{e}}^{\mathbf{A}\mathcal{T}},\\ {\mathbf{\Gamma }}_0(T_{\text{s}})={\int }_0^{\mathcal{T}-T_{\text{s}}}{\mathrm{e}}^{\mathbf{A}s}ds\mathbf{B},\\ {\mathbf{\Gamma }}_1(T_{\text{s}})={\int }_{\mathcal{T}-T_{\text{s}}}^{\mathcal{T}}{\mathrm{e}}^{\mathbf{A}s}ds\mathbf{B}.\end{array}\right.\end{array}$

Impact of delay and packet loss

We add the impact of packet losses to that of the communication delay. Since we assume two possible control actions upon a packet loss, we discuss the impact of packet loss in the following two situations:

• ZOTF criterion: In this case, the controller carries out zero control action if a packet of measurement is lost. Then there are two possible modes for the control feedback gain matrix, namely

$\begin{array}{l}\hfill {\mathbf{K}}_r=k\mathbf{K},r=0,1,\end{array}$

where k = 0 (or 1) means transmission failure (or transmission success). Thus the matrix Φ_s in Eq. (8.7) should be replaced with Φ_s^r(k) where K is replaced with K_r(k). Therefore when the sth modulation scheme is used, the system dynamics is governed by

$\begin{array}{l}\hfill \mathbf{z}(k+1)={\mathbf{\Phi }}_{\text{s}}^{r(k)}\mathbf{z}(k).\end{array}$

• MROTF criterion: In this case, if a packet is lost, the controller uses the most recently received packet for system state estimation. For the analysis a new variable x_c(t) is defined, which is given by

$\begin{array}{l}\hfill {\mathbf{x}}_c(k)=r(k)\mathbf{x}(k)+(1-r(k)){\mathbf{x}}_c(k).\end{array}$

We can verify that x_c(k) is the most recent received observation no later than time k.
Then the equivalent system state z is defined as

$\begin{array}{l}\hfill \mathbf{z}(k)={({\mathbf{x}}^T(k),{\mathbf{x}}_c(k),\mathbf{u}(k-1))}^T,\end{array}$

in which the timing of the variables is illustrated in Fig. 8.2.

The equivalent system state satisfies the same expression as in Eq. (8.11), in which the expression of Φ_s^r(k) is given by

$\begin{array}{l}\hfill {\mathbf{\Phi }}_{\text{s}}^{r(k)}=\left(\begin{array}{lll}\mathbf{\Psi }& -{\mathbf{\Gamma }}_0(T_{\text{s}})\mathbf{K}& {\mathbf{\Gamma }}_1(T_{\text{s}})\\ r(k)\mathbf{I}& (1-r(k))\mathbf{I}& 0\\ 0& -\mathbf{K}& 0\end{array}\right).\end{array}$

Markovian jump process

The system described in Eq. (8.11) is essentially a Markovian jump process [147], in which the state r(k) forms a Markov chain. On the other hand, the state s (namely the selected modulation scheme) is a discrete state while it can be controlled by the sensor. Given a fixed s, the system stability is judged by the following theorem, as a straightforward conclusion from the theorem in Ref. [148]:

Beyond the system stability, we can also consider the cost of the dynamics. We define the cost as

$\begin{array}{ll}\hfill J_N& =\sum _{k=0}^{N-1}{\mathbf{x}}^T(k)\mathbf{Q}\mathbf{x}(k)\hfill \\ \hfill & =\sum _{k=0}^{N-1}{\mathbf{z}}^T(k)\tilde{\mathbf{Q}}\mathbf{z}(k),\hfill \end{array}$

where $\tilde{\mathbf{Q}}=\mathrm{diag}(\mathbf{Q},0,0)$. As a straightforward conclusion of Theorem 1 in Ref. [149], the expected cost is given by

$\begin{array}{l}\hfill J_N(\mathbf{z}(0),r(0),s)={\mathbf{x}}^T(0){\mathbf{P}}_{0,r(0),s}\mathbf{x}(0),\end{array}$

where

$\begin{array}{ll}\hfill {\mathbf{P}}_{t,j,s}& =P_{e,s}{({\mathbf{\Phi }}_{\text{s}}^0)}^T{\mathbf{P}}_{t,0,s}{\mathbf{\Phi }}_{\text{s}}^0\hfill \\ \hfill & +(1-P_{e,s}){({\mathbf{\Phi }}_{\text{s}}^1)}^T{\mathbf{P}}_{t,1,s}{\mathbf{\Phi }}_{\text{s}}^1+\tilde{\mathbf{Q}},\hfill \end{array}$

with P_N, j, s = Q. Note that z(0) and r(0) are known initial conditions.

SPAAM

As indicated by the name, in SPAAM the modulation scheme is adaptive only to the system parameters and is fixed regardless of the current system state of physical dynamics. We assume that the objective of SPAAM is the stability of system dynamics. Then by applying the conclusion in Theorem 49, we obtain the following optimization problem:

$\begin{array}{ll}\hfill & \underset{s,\gamma ,\mathbf{G}}{max}\gamma \hfill \\ \hfill & \text{s.t.}\mathbf{G}-P_{e,s}{({\mathbf{\Phi }}_{\text{s}}^0)}^T\mathbf{G}{\mathbf{\Phi }}_{\text{s}}^0\hfill \\ \hfill & -(1-P_{e,s}){({\mathbf{\Phi }}_{\text{s}}^1)}^T\mathbf{G}{\mathbf{\Phi }}_{\text{s}}^1-\gamma \mathbf{I}>0\hfill \\ \hfill & \mathbf{G}>0,\hfill \end{array}$

where γ represents the eigenvalue of the corresponding matrix.

Below is an intuitive explanation for the above optimization: the goal is to maximize the minimal eigenvalue on the left-hand side of Eq. (8.15). If the maximum γ is positive, then the corresponding modulation can stabilize the system dynamics. A simple algorithm for the optimization is to carry out an exhaustive search for all modulation schemes. For each s, we apply the theory of linear matrix inequalities (LMI) [133] to find the optimal γ and G. Finally, we choose the optimal s that maximizes the objective function γ. Since the number of possible modulation schemes is usually quite limited, an exhaustive search is computationally efficient.

SSAAM

As indicated by the name SSAAM, the modulation scheme is selected adaptively to the current system state of physical dynamics. We have assumed that the modulation scheme can be changed every T_m seconds (or equivalently t_m samples). The set of modulation schemes that the sensor can choose from is denoted by Ω. The strategy of adaptive modulation is denoted by π; essentially it is a mapping from the system state x to the modulation scheme within Ω. In terms of hybrid systems, the modulation scheme selection is equivalent to the control of the discrete system state in the corresponding hybrid system.

The basic elements of SSAAM, as an optimization problem, are as follows:

• Cost function: A quadratic cost is considered over T_f scheduling periods (equivalently T_ft_m samples), which is given by

$\begin{array}{l}\hfill J=\sum _{t=1}^{T_f{t}_{\text{m}}}{\mathbf{x}}^T(t)\mathbf{Q}\mathbf{x}(t).\end{array}$

Thus the optimal adaptive modulation strategy is to minimize the cost given the current system state; i.e.,

$\begin{array}{l}\hfill {\pi }^{*}=arg\underset{\pi }{min}J(\pi ).\end{array}$

• Dynamic programming (DP): This is a powerful approach to optimize the above cost function. As a standard procedure of DP, we define the following cost-to-go function at the tth decision as the minimal cost in the future:

$\begin{array}{l}\hfill J_t(\mathbf{x})=\sum _{r=(t-1)t_{\text{m}}+1}^{T_f{t}_{\text{m}}}{\left.{\mathbf{x}}^T(r)\mathbf{Q}\mathbf{x}(r)\right|}_{\mathbf{x}((t-1)t_{\text{m}})=\mathbf{x}}.\end{array}$

By solving the following Bell equation, we can obtain the cost-to-go function in a recursive manner:

$\begin{array}{ll}\hfill J_t(\mathbf{x})& =\underset{s}{min}\sum _{r=(t-1)t_{\text{m}}+1}^{t{t}_{\text{m}}}{\left.{\mathbf{x}}^T(r)\mathbf{Q}\mathbf{x}(r)\right|}_{\mathbf{x}((t-1)t_{\text{m}})=\mathbf{x}}\hfill \\ \hfill & +{\left.J_{t+1}({\mathbf{x}}^{\prime })\right|}_{\mathbf{x}((t-1)t_{\text{m}})=\mathbf{x},s},\hfill \end{array}$

where x′ is the initial system state in the next decision period, which is determined by the current system state x and the action s (the selection of modulation). The cost-to-go function can be calculated from the last time slot T_ft_m, which is trivial.

• Approximate dynamic programming (ADP): The main challenge of DP is that it is difficult to represent the continuous function J_t(x), as many DP problems do. An effective approach to handle this challenge is to apply ADP. In Ref. [146], we approximate the cost-to-go function by using quadratic functions given by

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

where Σ_t is a positive-definite function. Then the computation of the cost-to-go function is equivalent to estimating Σ_t. Due to limitations of space, we are unable to discuss how to estimate Σ_t. The detailed algorithm can be found in Ref. [146]. Numerical results have shown that the proposed ADP approach can effectively handle the challenge and results in good performance for controlling the physical dynamics.

Both SPAAM and SSAAM have been demonstrated to achieve good performances in the context of smart grids [146].

Sliding block causal coders

In this case the output of a decoder at time t is given by

$\begin{array}{l}\hfill {\widehat{X}}_t=f_t({\{X_k\}}_{k=-\infty }^t).\end{array}$

If the coder has finite memory, then we have

$\begin{array}{l}\hfill {\widehat{X}}_t=f_t({\{X_k\}}_{k=t-M}^t),\end{array}$

where M is the memory length.

Block causal coders

In such coders, the information is encoded and decoded in a block manner, namely

$\begin{array}{l}\hfill {\widehat{X}}_{kN+1}^{kN+N}=f(X_{kN+1}^{kN+N}),\end{array}$

where k is the index of the block (or codeword). Obviously, such a coding scheme will cause an average delay N/2.

Block stationary coders

Block stationary coders can be considered as a combination of sliding block causal coders and block causal coders. The output is given by

$\begin{array}{l}\hfill {\widehat{X}}_{kN+1}^{kN+N}=f(X_{-\infty }^{kN+N}),\end{array}$

where the decoder output is in blocks and the decoding procedure uses all the previous received bits.

Finite-state causal coders

A challenge of sliding block causal coders and block stationary coders is that infinite memory is needed to store all the previously received bits. To alleviate this problem while not discarding the history, a state S can be defined for the coders, such that the decoder output is a function of the state and the newest information symbol, namely

$\begin{array}{l}\hfill {\widehat{X}}_k=f_x(S_k,X_k),\end{array}$

and the system state S evolves in the following law:

$\begin{array}{l}\hfill S_k=f_{\text{s}}(S_{k-1},X_k).\end{array}$

Rate distortion

In the context of causal coding, the rate-distortion function r_c(D) is defined to be the minimum average transmission rate such that the average distortion is no larger than D. It is shown in Ref. [150] that r_c(D) is determined as follows:

$\begin{array}{l}\hfill r_c(D)=\underset{f\text{causal,}d(f)\le D}{inf}lim\underset{K\to \infty }{sup}\frac{1}{K}H({\widehat{X}}_1^K),\end{array}$

where d(f) denotes the average distortion caused by the coder f. An interesting conclusion in Theorem 3 of Ref. [150] is that the causal rate-distortion functions in the above coder schemes are all the same when the information source is memoryless. However, it is still an open problem to compare the rate-distortion functions when the information source has memory.

Transceiver structure

We assume that the encoder and decoder have states T and R, respectively. Upon receiving a source information symbol X_t, the transmitter sends out a coded symbol D_t (with possibly N_D values) and updates its state:

$\begin{array}{l}\hfill \left\{\begin{array}{l}{T}_{t+1}=\tau (X_t,T_t),\\ D_t=\delta (X_t,T_t).\end{array}\right.\end{array}$

Upon receiving the coded symbol D_t, the receiver updates its own state and outputs a symbol Y_t:

$\begin{array}{l}\hfill \left\{\begin{array}{l}{R}_{t+1}=\rho (D_t,R_t),\\ Y_t=\eta (D_t,R_t).\end{array}\right.\end{array}$

It is assumed that the information source {X_t}_t is a stationary ergodic stochastic process, and the encoding/decoding mappings are deterministic. The distortion function is denoted by ψ(x, y). We assume that the following limit exists:

$\begin{array}{l}\hfill {ϵ}_k^2=\underset{n\to \infty }{lim}E\psi (X_{n-k},Y_n).\end{array}$

Major problem and conclusions

Ref. [151] mainly focused on how to find the encoding and decoding mechanisms τ, δ, ρ, and η in order to minimize the expected distortion ${ϵ}_k^2$. Although there is no determining conclusion for generic cases, many conclusions on the transceiver structure have been obtained.

First it has been shown that, given sufficiently long delay k, the finite-state transceiver can achieve the traditional rate-distortion function with unlimited codeword length.

Then it is of major interest to study how to choose the encoding and decoding mechanisms τ, δ, ρ, and η such that the average distortion ${ϵ}_k^2$ is minimized, given the delay k. For notational simplicity, we define

$\begin{array}{l}\hfill p_{X_{n-k},T_n,D_n,R_n}(x,t,d,r)=Pr(X_{n-k}=x,T_n=t,D_n=d,R_n=r).\end{array}$

We assume that the initial states T₁ and R₁ are known, or the distributions are given. If τ, δ, and ρ are properly chosen, the distribution $p_{X_{n-k},T_n,D_n,R_n}$ will converge to a stationary one:

$\begin{array}{l}\hfill \underset{n\to \infty }{lim}{p}_{X_{n-k},T_n,D_n,R_n}(x,t,d,r)=p_{X,T,D,R}^k(x,t,d,r).\end{array}$

Or the distribution will converge to a periodic structure with period L:

$\begin{array}{l}\hfill \underset{n\to \infty }{lim}{p}_{X_{m-k},T_{\text{m}},D_{\text{m}},R_{\text{m}}}(x,t,d,r)=p_{j,X,T,D,R}^k(x,t,d,r),\end{array}$

where m = nL + j. In this case, we can define the average distribution over one period:

$\begin{array}{l}\hfill p_{X,T,D,R}^k(x,t,d,r)=\frac{1}{L}\sum _{j=1}^L{p}_{j,X,T,D,R}^k(x,t,d,r).\end{array}$

The definitions of $p_{X,T,D,R}^k(x,t,d,r)$ in both Eqs. (8.41) and (8.43) are called the steady-state distribution. Hence the average distortion is given by

$\begin{array}{l}\hfill {ϵ}_k^2=\sum _{x,d,r}{p}_{X,D,R}^k(x,d,r)\psi (x,\eta (d,r)),\end{array}$

where

$\begin{array}{l}\hfill p_{X,D,R}^k(x,d,r)=\sum _t{p}_{X,T,D,R}^k(x,t,d,r).\end{array}$

Using the Bayesian rule, we have

$\begin{array}{ll}\hfill {ϵ}_k^2& =\sum _{d,r}{p}_{D,R}^k(d,r)\sum _x{p}_{X|D,R}^k(x|d,r)\psi (x,\eta (d,r))\hfill \\ \hfill & =\sum _{d,r}{p}_{D,R}^k(d,r)F_{d,r}(\eta (d,r)),\hfill \end{array}$

where

$\begin{array}{l}\hfill F_{d,r}(y)=\sum _x{p}_{X|D,R}^k(x|d,r)\psi (x,y).\end{array}$

Let $y_0=arg{max}_y{F}_{d,r}(y)$. Then the following theorem shows that the optimal decoder should adopt y₀.

Given the optimal decoder η, the next task is to design the optimal functions of τ, δ, and ρ. However, the search space of these functions is enormously large. Hence the optimal design is still an open problem, even for special cases such as Markov information sources. However, for some special cases, such as the one discussed subsequently, we can obtain more information.

System model

We consider a discrete-time information source {X_n}, which is ergodic and Markovian. The information source {X_n} cannot be observed directly. An associated observation process {Y_n} can be measured. The conditional distribution of Y given X is denoted by ψ(Y |X). We assume that X_n and Y_n are n-dimensional and d-dimensional real vectors, respectively. The evolution law of X_n and Y_n is given by

$\begin{array}{ll}\hfill P(X_{n+1}\in A,Y_{n+1}\in B|X^n,Y^n)& ={\int }_{A\times B}p(X_n,dx,dy)\hfill \\ \hfill & ={\int }_A{\int }_B\varphi (y,z|X_n)dydz,\hfill \end{array}$

for any $A\subset R^n$ and $B\subset R^d$. Since given X_n the distribution of X_n+1 and Y_n+1 is independent of Xⁿ⁻¹ and Yⁿ, such an information source is called a Markov source. An explicit description of the source and observation processes is given by

$\begin{array}{l}\hfill \left\{\begin{array}{l}{X}_{n+1}=g(X_n,{\xi }_n),\\ Y_{n+1}=h(X_n,{\xi }_n^{\prime }),\end{array}\right.\end{array}$

where g and h are the mechanisms of both processes, and ξ_n and ξ_n′ are random perturbations that are mutually independent and are independent of X_n. We further assume that the evolution of the system state X_n is continuous with respect to the initial value. In more detail, if two realizations X_n and X_n′, with initial values X₀ = x and X₀′ = y, have the same driving random noises {ξ_n}, we have

$\begin{array}{l}\hfill E[\parallel X_n-X_n^{\prime }\parallel ]\le K{\beta }^n\parallel x-y\parallel ,n\ge 0,\end{array}$

for some constants K and β.

Vector quantizer

A vector quantizer is assumed. The set of alphabets is denoted by Σ = {α₁, …, α_N}. The quantized version of the observation process {Y_n} is given by {q_n}, which takes values in Σ.

We denote the set of all possible finite subsets of R^d by D, which satisfies the following condition: there exists an M > 0 and a Δ > 0 such that

• x ∈ A ∈ D implies ∥x∥≤ M;

• if x = (x₁, …, x_d) and y = (y₁, …, y_d) are both within A ∈ D and x≠y, then we have |x_i − y_i| > Δ for all i.

Intuitively, A denotes the set of representative vectors for the quantizer. The first requirement means that all the representative vectors have bounded norms. The second requirement means that all the dimensions of any pair of representative vectors should be well separated.

Then the quantizer is given by

$\begin{array}{l}\hfill \left\{\begin{array}{l}{q}_{n+1}=i_{Q_n}(l_{Q_n}(Y_{n+1})),\\ Q_n={\eta }_n(q^n),\end{array}\right.\end{array}$

where Q_n is the set of representative vectors which change with time, η_n maps from all the quantization outputs to the set of representative vectors, $l_{Q_n}$ maps from the observation to the nearest representative vector, and $i_{Q_n}$ maps from the representative vector to the index in Σ.

The goal of the quantizer is to optimize the choice of η_n such that the average entropy rate of {q_n} and the average distortion are jointly optimized. The cost function can be formulated as

$\begin{array}{l}\hfill lim\underset{n\to \infty }{sup}\frac{1}{n}\sum _{m=0}^{n-1}E[H(q_{m+1}|q^{\text{m}})+\lambda \parallel Y_{\text{m}}-{\stackrel{-}{q}}_{\text{m}}{\parallel }^2],\end{array}$

where λ is the weighting factor and ${\stackrel{-}{q}}_{\text{m}}=i_{Q_{m-1}}^{-1}(q_{\text{m}})$.

Equivalent control problem

We now rewrite the cost function in Eq. (8.59) into an alternative form, which is reduced to a control problem. First we define

$\begin{array}{l}\hfill {\pi }_n(A)=P(X_n\in A|q^n),\end{array}$

which is the probability distribution of X_n given the previous quantizer outputs, and can be computed recursively. We further define

$\begin{array}{l}\hfill h_a(\pi ,A)=\int \pi (dx)f_n(x,A),\end{array}$

where

$\begin{array}{l}\hfill f_n(x,A)=\int \psi (y|x)I[i_A(l_A(y))=a]dy.\end{array}$

The intuitive meaning of f_n(x, A) is the probability of generating the quantization output a when the true system state is x and the set of representative vectors is A. h_a(π, A) is the probability of outputting a when the distribution of x is π and the representative vector set is A.

We also define

$\begin{array}{l}\hfill \widehat{f}(x,A)=\int \psi (y|x)\parallel y-l_A(y){\parallel }^{2}dy,\end{array}$

which is the expected cost when the true system state is x and the set of representative vectors is A, and

$\begin{array}{l}\hfill k(\pi ,A)=-\sum _a{h}_a(\pi ,A)log{h}_a(\pi ,A),\end{array}$

which means entropy of the quantizer output when the distribution of x is π and the set of representative vectors is A, and

$\begin{array}{l}\hfill r(\pi ,A)=\int \pi (dx)\widehat{f}(x,A),\end{array}$

which is the expected cost when the distribution of x is π and the set of representative vectors is A.

Then the cost in Eq. (8.59) can be written as

$\begin{array}{l}\hfill lim\underset{n\to \infty }{sup}\frac{1}{n}\sum _{m=0}^{n-1}E[k({\pi }_{\text{m}},Q_{\text{m}})+\lambda r({\pi }_{\text{m}},Q_{\text{m}})].\end{array}$

In Ref. [153], a technical mechanism is proposed to make the corresponding probabilities bounded from below by a small number. Here we skip this step and simply assume that all the probabilities have been bounded by a small constant.

Now the problem becomes to find the control policy mapping from the a posteriori probability π_n to the quantization policy (i.e., the representative vectors) Q_n, which is denoted by Q_n = v(π_n). Thus the source coding problem is transformed to a Markov decision problem.

Dynamic programming

The cost function in Eq. (8.66) is the long-term average of costs, whose solution is involved. Hence we first convert the cost function to a discounted one, which is given by

$\begin{array}{l}\hfill J_{\alpha }({\pi }_0,\{Q_n\})=\sum _{m=0}^{\infty }{\alpha }^{m}E[k({\pi }_{\text{m}},Q_{\text{m}})+\lambda r({\pi }_{\text{m}},Q_{\text{m}})].\end{array}$

The standard procedure of DP can then be applied. First we define the value function as

$\begin{array}{l}\hfill V_{\alpha }({\pi }_0)=\underset{v}{inf}{J}_{\alpha }({\pi }_0,\{Q_n\}).\end{array}$

Using Bellman’s equation, the value function satisfies

$\begin{array}{l}\hfill V_{\alpha }(\pi )=\underset{A}{min}[k({\pi }_{\text{m}},Q_{\text{m}})+\lambda r({\pi }_{\text{m}},Q_{\text{m}})+\alpha \int V_{\alpha }({\pi }^{\prime })P(d{\pi }^{\prime }|A,\pi )],\end{array}$

where P(dπ′|A, π) is the conditional probability of the a posteriori probability given the quantization scheme represented by A and the current a posteriori probability π. The corresponding optimal strategy can be obtained via

$\begin{array}{l}\hfill v(\pi )=arg\underset{A}{min}[k({\pi }_{\text{m}},Q_{\text{m}})+\lambda r({\pi }_{\text{m}},Q_{\text{m}})+\alpha \int V_{\alpha }({\pi }^{\prime })P(d{\pi }^{\prime }|A,\pi )].\end{array}$

To remove the discounting in Eq. (8.67), it was shown in Ref. [153] that we can let $\alpha \to 1$ and obtain the optimal policy for Eq. (8.66). The details are omitted here. One challenge for the DP here is that both π_n and Q_n are continuous and thus the strategy v is infinitely dimensional. It still remains an open problem to efficiently solve the Bellman equation in Eq. (8.69). One possible approach is to use ADP and obtain suboptimal solutions.

Once the optimal strategy of sequential quantization is found, the estimations of X and Y are given by the maximum a posteriori (MAP) ones, i.e.,

$\begin{array}{l}\hfill {\widehat{X}}_n=argmax{\pi }_n(\cdot )\end{array}$

and

$\begin{array}{l}\hfill {Ŷ}_n=argmax\int I\{i_{Q_{n}l}=q_{n}P(\cdot ,z|x)dz{\pi }_{n-1}(dx)\}.\end{array}$

Distortion

In traditional source coding, a typical distortion criterion is the mean square error (MSE), which can also be applied in a CPS. However, the eventual goal of a CPS is not to convey the measurements; instead, it is to stabilize the system and minimize the cost of physical dynamics operation. Therefore we propose a new criterion for the distortion in a CPS.

First we notice that the system state estimation error may have different effects on system stability. In stable subspace, the error of system state estimation will be automatically damped and then vanish; in unstable subspace, the error may be amplified and make the whole system unstable. Therefore we first decompose the system state space by decomposing the matrix A to

$\begin{array}{l}\hfill \mathbf{A}={\mathbf{U}}^T\mathbf{\Lambda }\mathbf{U},\end{array}$

where U is unitary and Λ = diag(λ₁, …, λ_N), where λ_n is the nth eigenvalue. For simplicity, we assume that λ_i≠λ_j, if i≠j. Also for simplicity, we assume that the matrix A is of full rank. We consider the following dichotomy for the eigenvalues:

• |λ_n| > 1: in this subspace, the physical dynamics is not stable; the error of system state estimation may be amplified;

• |λ_n| < 1: in this subspace, the system state of physical dynamics inherently converges to zero (if no random perturbation is considered); any system state estimation error will be naturally suppressed; hence even if there is no control in this subspace, the system state is still stable.

The decomposition is illustrated in Fig. 8.4. We denote by Ω the set of unstable subspaces. For simplicity, we assume that the first N₀ subspaces are unstable.

Using the above decomposition, the system can be decomposed into N uncorrelated subsystems:

$\begin{array}{l}\hfill z_n(t+1)={\lambda }_n{z}_n(t)+v_n(t)+ñ(t),\end{array}$

where z = (z₁, …, z_N) = Ux, $\tilde{\mathbf{n}}=({ñ}_1,\dots ,{ñ}_N)=\mathbf{U}\mathbf{n}$, and v = (v₁, …, v_N) = UBu.

We assume that a “blow-up” control policy is used by the controller, which intuitively means that the controller simply removes the deviation from the desired operational point and does not consider the cost of the control action (not like the strategy in linear quadratic Gaussian (LQG) control, where the cost of control action is also considered in the cost function). The corresponding control action in the nth subspace is given by

$\begin{array}{l}\hfill v_n(t)=-{\lambda }_n{\widehat{z}}_n(t),\end{array}$

where ${\widehat{z}}_n$ is the estimation of z_n. We assume that the matrix UB has a full row rank, which assures the existence of v. When there is no random noise (namely $ñ(t)=0$) and the state estimation ${\widehat{z}}_n$ is perfect, the blow-up control action drives the system state back to zero, which is assumed to be desired. Then the variance of system state in the nth subspace is given by

$\begin{array}{l}\hfill V[z_n]=E[{ñ}_n^2]+|{\lambda }_n{|}^{2}E[{ϵ}_n^2],\end{array}$

where ϵ is the estimation error of z_n.

Based on the above discussion, we define the distortion as

$\begin{array}{l}\hfill \mathcal{D}=\sum _{n\in \Omega }V[z_n],\end{array}$

namely the sum variance of the system state in the unstable subspaces. The fluctuations in the stable subspaces are not taken into consideration. Note that Eq. (8.85) is a heuristic definition for the distortion. It emphasizes the unstable subspaces and totally omits the stable ones, since the latter can be automatically stabilized and do not affect the system stability. Below are some other possibilities as regards distortion:

• The stable subspaces can also be taken into account. This helps to better suppress the total variance. However, the definition of distortion in this book increases the dimension of the system state space and incurs more computational cost.

• Typical criteria in controls such as quadratic cost functions (e.g., the cost function in the framework of an LQG system) can be considered. However, we are still not clear about the connection between these cost functions and the source coding problem.

Lattice-based quantization

An effective approach for quantization is to apply the concept of a lattice. A lattice is defined as the following infinite set [162, 164]:

$\begin{array}{l}\hfill \Sigma =\{\mathbf{G}\mathbf{i},\mathbf{i}\in {\mathbf{Z}}^n\},\end{array}$

where Z = (…, −2, −1, 0, 1, 2, …), n is the dimension, and G is an n × n matrix, which is called the generation matrix.

We then study how to form lattices for the observations y₁ and y₂. We consider a higher dimension lattice generated by G₁ and G₂ (i.e., the generating matrices for y₁ and y₂); i.e.,

$\begin{array}{l}\hfill {\mathbf{G}}_{12}={({\mathbf{G}}_1^T,{\mathbf{G}}_2^T)}^T\end{array}$

and

$\begin{array}{ll}\hfill {\Sigma }_{12}& =\{{\mathbf{G}}_{12}\mathbf{i},\mathbf{i}\in {\mathbf{Z}}^{N_1+N_2}\}\hfill \\ \hfill & =\{{({({\mathbf{G}}_1{\mathbf{i}}_1)}^T,{({\mathbf{G}}_2{\mathbf{i}}_2)}^T)}^T,{\mathbf{i}}_1\in {\mathbf{Z}}^{N_1},{\mathbf{i}}_2\in {\mathbf{Z}}^{N_2}\}.\hfill \end{array}$

The next task is to design the generating matrices G₁ and G₂. We apply the distortion function defined in Eq. (8.85). It is assumed that the system state estimation based on y₁ and y₂ is obtained from

$\begin{array}{l}\hfill \widehat{\mathbf{x}}={({\mathbf{C}}_1^T{\mathbf{C}}_1+{\mathbf{C}}_2^T{\mathbf{C}}_2)}^{-1}({\mathbf{C}}_1^T,{C_2}^T){({\mathbf{y}}_1^T,{\mathbf{y}}_2^T)}^T.\end{array}$

We map the space to the unstable subspaces of the system state. Then the lattice generated by matrix G_x is given by

$\begin{array}{l}\hfill {\mathbf{G}}_x=\tilde{\mathbf{U}}\tilde{\mathbf{C}}{\mathbf{G}}_{12},\end{array}$

where $\tilde{\mathbf{U}}$ consists of the eigenvectors in U associated with the unstable subspaces, and $\tilde{\mathbf{C}}={({\mathbf{C}}_1^T{\mathbf{C}}_1+{\mathbf{C}}_2^T{\mathbf{C}}_2)}^{-1}({\mathbf{C}}_1^T,{C_2}^T)$.

We want to equalize the mean square quantization errors in each unstable subspace. To that end, the lattice is designed to be parallel to the axes, and the distances between two neighboring lattice points are designed to be proportional to ${\left\{{\frac{1}{\lambda }}_n\right\}}_{n\in \Omega }$. This means that, in a particular unstable subspace, the quantization error variance is inversely proportional to the corresponding eigenvalue, since the eigenvalue scales the impact of the quantization error on the system state. Hence the generating matrix G_x is designed to be

$\begin{array}{l}\hfill {\mathbf{G}}_x=\Delta \left(\begin{array}{llll}\frac{1}{{\lambda }_1}& 0& \cdots & 0\\ 0& \frac{1}{{\lambda }_2}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \frac{1}{{\lambda }_{N_0}}\end{array}\right),\end{array}$

where Δ is a constant to control the tradeoff between coding rate and quantization errors. This procedure is illustrated in Fig. 8.5 when y₂ (i.e., C₂ = 0) is ignored.

For lattices Σ₁ and Σ₂, we require

$\begin{array}{l}\hfill E[{\mathbf{y}}_1|y_2]\in {\mathbf{\Sigma }}_1,\forall y_2\in {\mathbf{\Sigma }}_2.\end{array}$

If y₁ and y₂ are separable, we have

$\begin{array}{l}\hfill h_{21}({\mathbf{y}}_2)+E[{\mathbf{w}}_{12}]\in {\mathbf{\Sigma }}_1,\forall y_2\in {\mathbf{\Sigma }}_2.\end{array}$

Slepian-Wolf coding

We first revisit the well-known scheme of Slepian-Wolf coding proposed in 1973. Consider two information sources whose symbols are denoted by X₁(t) and X₂(t). There is no communication between the two information sources. The surprising conclusion of Slepian-Wolf coding is that it can achieve asymptotically lossless coding when the sum of the transmission rates of the two sources equals the entropy of the information sources [155]; i.e.,

$\begin{array}{l}\hfill R_1+R_2=H(X_1,X_2),\end{array}$

as if the two information sources can perfectly collaborate as a single information source, although there is no explicit communication and coordination between the two information sources.

Coloring-based coding

We now apply the principle of Slepian-Wolf coding in the context of distributed source coding for a CPS. The main challenge is that the coding delay in a CPS cannot be tolerated while the Slepian-Wolf coding needs an infinite delay. Moreover, the random codebook in Slepian-Wolf coding is infeasible in practice, while the encoding/decoding complexities must be addressed in our proposed coding scheme.

In this book, we adopt the approach of coloring-based coding. It is well known that the source coding for computing functions with side information is equivalent to the problem of coloring a graph. We apply the same idea to distributed source coding in a CPS.

For simplicity of analysis, it is assumed that sensor 2 sends its full quantized version of y₂. This provides side information for the transmission and decoding of y₁ from sensor 1 and thus can decrease the communication requirement of sensor 1. For each y₂, the set of related values of y₁ is defined as

$\begin{array}{l}\hfill \mathbf{\Gamma }({\mathbf{y}}_2,{\gamma }_1)=\{{\mathbf{y}}_1|{\mathbf{y}}_1\in {\mathbf{\Sigma }}_1,P({\mathbf{y}}_1|{\mathbf{y}}_2)>{\gamma }_1\},\end{array}$

where γ₁ is a predetermined threshold and the set Γ(y₁, γ₁) consists of the lattice points in Σ₁ that are of significantly large conditional probability given y₂.

An $n_1\times n_2\times \cdots \times n_{N_1}$ super-rectangle in Σ₁ is defined as

$\begin{array}{l}\hfill \mathbf{R}={\mathbf{G}}_1\prod _{p=1}^{N_1}[y_p,y_p+1,\dots ,y_p+n_p],\end{array}$

for a particular ${\{y_p\}}_{p=1,\dots ,N_1}$.

The compatible super-rectangle in Σ₁ given y₂ and γ₁ is defined as

$\begin{array}{l}\hfill {\mathbf{R}}_1({\mathbf{y}}_2,{\gamma }_1)=\text{the minimum}\mathbf{R}\text{containing}\mathbf{\Gamma }({\mathbf{y}}_1,{\gamma }_1).\end{array}$

The reason why we choose a rectangle for the shape of the set is that it results in an efficient coloring scheme and the corresponding source coding, which will be detailed later. Once γ₁ is properly selected, we assume that the probability of y₁ falling out of R₁(y₂, γ₁) is negligible. For the generic case, the compatible super-rectangles of different y₂ values may have different sizes. However, for the case of separable y₁ and y₂, the super-rectangles of different y₂ values have the same sizes (with different centers); i.e.,

$\begin{array}{l}\hfill {\mathbf{R}}_1({\mathbf{y}}_2,\gamma )=h_{21}({\mathbf{y}}_2)+\stackrel{-}{\mathbf{R}}({\gamma }_1),\end{array}$

where $\stackrel{-}{\mathbf{R}}({\gamma }_1)$ is the basic rectangle defined as

$\begin{array}{l}\hfill {\stackrel{-}{\mathbf{R}}}_1(\gamma )=\text{the minimum}\mathbf{R}\text{containing}\mathbf{\Gamma }(h_{12}^{-1}(0),{\gamma }_1).\end{array}$

The definition of super-rectangles is illustrated in Fig. 8.6, in which ${\mathbf{y}}_2^0$ in Σ₂ corresponds to ${\mathbf{y}}_1^0$ in Σ₁ (i.e., ${\mathbf{y}}_1^0$ is the value of y₁ when there is no noise in the observation). A super-rectangle is given by the dotted lines. Hence with a large probability, y₁ lies in the area specified by the dotted lines.

We have assumed that the precise information of quantized y₂ has been transmitted to the fusion center, as the side information for sensor 1. Since with a large probability y₁ falls in the compatible super-rectangle R₁(y₂, γ₁),¹ sensor 1 only needs to specify the point within R₁(y₂, γ₁). If the labeling of each point in Σ₁ is considered as coloring a set of elements, two different points in R₁(y₂, γ₁) should have different colors; otherwise, the same color causes decoding confusion.

Hence the following requirements are needed for the coloring problem:

• There are no different points having the same color in the same compatible super-rectangle.

• The mappings to and from the color should be computationally efficient.

Although algorithms in graph theory can be applied to minimize the number of colors used in the coding of y₁ with the guarantee of different colors, the mapping between lattice points and colors can be irregular and needs look-up tables, which substantially increases the computational complexity. Hence we propose a simple but efficient approach of coloring:

• First we determine the maximal sizes in different dimensions of a compatible super-rectangle; i.e.,

$\begin{array}{ll}\hfill & n_k^{*}=max\{n_k|n_k\text{is the length of the}k\text{th}\hfill \\ \hfill & \text{dimension of a compatible super-rectangle}\}.\hfill \end{array}$

• Then for a lattice point in Σ₁ which can be written as

$\begin{array}{l}\hfill {\mathbf{y}}_1={\mathbf{G}}_1{(n_1,\dots ,n_{N_1})}^T,n_k\in Z,\end{array}$