Modeling and analysis of networked finite state machine subject to random communication losses

1.   Introduction

Finite state machine (FSM) has found successful applications in many complex artificial systems, including network intrusion detection and cyber-physical ones. In a classical finite state machine, it is assumed that the controller is close to the actuator, the event command can be transmitted to the controlled plant instantaneously through the control channel. After decades of development, many problems for such these systems have been well studied, such as monitor theory ^[1], state estimate and detectability ^[2], controllability ^[3,4] and so on. It is important to note that ^[5,6,7] converting the cyber-physical systems in the logical networks and obtained a series of meaningful and innovative results about the cyber-physical system. On the one hand, the need for the interconnection of all things makes it is easier for information to be transferred by means of communication networks; and on the other hand, the introduction of communication networks renders the system with many excellent performances, such as cost reduction, convenient maintenance friendly, easy tests and so on. Hence, the control problems of NFSM have attracted increasing attention and has become a very active field.

Generally, due to the relatively far transmission distance, it is inevitable to introduce delays or packet losses between supervisory controller and actuator. Specifically, an event occurring spontaneously or a control command generated by the monitor could be transferred at random in the model of NFSM. If the monitor is designed without considering the delays or packet losses in the control channel (from supervisory controller and actuator), the command issued by a supervisor may not be effectively or successfully accepted by the plant. Hence, in consideration of the complex evolutionary behavior, the modeling and analyzing of communication delays and packet losses has given rise to new challenges. Meanwhile, the utilization of communication networks in the control loops have also considerable theoretical and practical significance for NFSM.

From the analysis of the current literature, many researches on NFSM almost always concentrate on the channel delays, such as centralized control ^[8] and decentralized control ^[9], robust control ^[10] and distributed failure prognosis ^[11] and so on. In recent years, Lin ^[12] investigated the bounded communication losses in the control and observation channel from the perspective of supervisory control, and obtained the existence conditions for networked supervisor, $i.e.$, network observability and controllability need to be met simultaneously. Up to now, There are fewer works to address the issues on the controllability problem with communication losses in the control channel, except our previous work ^[13], which has solved the reachability problem with communication losses from a switched perspective. However, in ^[13], we assumed that the communication losses occur determinately, $i.e.$, the probability of random channel packet losses from the controller to the actuator is not considered, which lacks the strict quantitative analysis for random packet losses.

Inspired by the methods in ^[13], $i.e.$, matrix STP method, this paper continues to study the influence of random packet losses on controllability in the control channel of NFSM. We refer to the work in ^[8], and assume that all the events are disabled by default, and then, construct another finite state machine affected by packet losses, where the set of transitions with communication losses are disabled and the predecessor of such transitions will remain unchanged with respect to the lost events. To characterize the dynamics with random channel packet losses, the state estimator is introduced by utilizing a stochastic variable, which is assumed to obey the Bernoulli random binary distribution. Some key contributions include the following points:

● The matrix expression of NFSM with random channel packet losses in control is proposed by an algebraic state space method.

● The validation criteria for the reachability and controllability $w.p.$ 1 are given for NFSM on the basis of the transition probability matrix.

The remaining sections are structured as follows: Section 2 brings in some basic notations and knowledge about the NFSM and matrix STP. Section 3 focuses on the key results of this paper, including the algebraic representation for NFSM with random channel packet losses, and the validation criteria for the existence of controllability. In section 4, one typical simulation example is illustrated to validate the proposed results. Finally, in Section 5, we summarize the whole paper and give a brief prospect of the future study.

2.   Basic notations and preliminaries

● $\mathcal{N^+}$ is said to be the set of all positive integers.

● $\mathcal{M}_{m \times l}$ is expressed as the set of $m\times l$-dimensional real matrices.

● $A_{(i, j)} \in \mathcal{M}_{m \times l}$ represents the element with the $i$-th row and $j$-th column of matrix $M$.

● The $j$-th column of $A \in \mathcal{M}_{m \times l}$ can be expressed as $Col_j(M)$, and furthermore, the set of all columns is $Col(M)$.

● $\bigvee$ is termed as the logical 'OR' operation.

● $\mathbf{1}_n = [\underbrace{1, 1, \cdots, 1}_n]$.

● $\delta_n^k$ is the $k$-th column of identity matrix $I_n$, $k\in \{1, 2, \cdots, n\}$.

● $\Delta_n: = \{\delta_n^1, \delta_n^2, \cdots, \delta_n^n\}$.

● $\nu = [\nu_1, \nu_2, \ldots, \nu_n]^T\in \mathbb{R}^{n}$ is said to be sub-stochastic logical vector if every element is satisfied that $\nu_i \geq 0$ and $\sum _{i = 1}^n \nu_i \leqslant 1$; Especially, it is defined as stochastic logical vector if $\sum _{i = 1}^n \nu_i = 1$.

● The set of $n$-dimensional sub-stochastic logical vector is denoted by $\tilde{\mathcal{L}}_{ n}^s$, making $\mathcal{L}_{n}^s$ as the set of $n$-dimensional stochastic logical vector.

● $E[y]$ is called the expected value of sub-stochastic or stochastic logical vector $y$.

● $\Sigma^{\ast}$ denotes the set, which is composed of all finite-length and non-empty strings on the finite set $\Sigma$.

In the classical FSM, the distance from controller to actuator is assumed to be close, and the supervisory command can be transmitted to the plant instantaneously through the control channel. In general, the finite state machine can be briefly written as $G = \left(Q, \Sigma, f, q^0\right)$, and it consists of four-tuple, including the set of events $\Sigma$ and states $Q$ from the initial state $q^0$, the (partial) state transition function $f$: $Q \times \Sigma \to Q$, generating all possible transitions $f = \{(q, \sigma, q^{\prime}) : f(q, \sigma) = q^{\prime}\}$. Additionally, the transition function $f$ can be generalized over $\Sigma^{\ast}$ by an iterative way.

Due to the relatively far transmission distance, it is noted that packet losses between the supervisory controller and actuator will be introduced inevitably. According to the actual situation of engineering system modeling and the information transmission network, those transitions affected by the actuators that are far away from the supervisor may be lost at random. We define such transitions as the set $f_l \subseteq f$, and the remaining transitions are supposed to not be absolutely lost, which is written as $f_{ul} = f - f_l$. That is, the set of all transitions can be divided into two parts, $i.e.$, $f = f_l\cup f_{ul}$. In view of the above condition, a NFSM can be characterized as $\mathcal{A} = \{A, f_l\}$.

At the beginning of the 21-st century, a novel algebraic framework is proposed on the basis of the matrix semi-tensor product, which transforms the logic dynamic system into algebraic representation and extends the application scope of the classical linear state space approach. Since then, the STP-based algebraic state space method has inspired and generated an abound of excellent works in related areas, such as logic control networks ^{[14,15,16,17,18,19,20]}, multi-agent systems ^[21], networked evolution games ^{[22,23,24,25]} and discrete event systems ^[26,27,28] and so on ^[29]. First of all, for the convenience of understanding, we give some related definitions and properties of matrix STP.

Definition 2.1 (^[30]). Given two matrices of arbitrary dimensions $H \in {\mathcal{M}_{m \times n}}$, $D \in {\mathcal{M}_{p \times q}}$, the corresponding STP ('$\ltimes$') of $H$ and $D$ is defined as:

where $r$ is called the least common multiple of $n$ and $p$.

(1) For $\chi \in \mathcal{M}_{m\times 1}, \varphi \in \mathcal{M}_{n\times 1}$, the pseudo-commutativity of $\chi$ and $\varphi$ is satisfied that $\varphi \ltimes \chi = {\Psi_{[m, n]}}\ltimes \chi\ltimes \varphi$, where $\Psi_{[m, n]}$ is a constructed swap matrix, defined as:

where $\delta_{mn}^j$ is termed as the $j$-th column of identity matrix $I_{mn}$

(2) Given a matrix of arbitrary dimension $X\in\mathcal{M}_{m\times n}$, if it is supposed that $X^{(0)}: = I_n$, then for $k\in\mathcal{N^+}$, the STP power is denoted by

The STP-based algebraic state space method can be described as the following two procedures:

● Firstly, by using the matrix STP, the logical variables involved in the system are represented by a vector of finite dimensions $(x_i\sim\delta_n^i)$;

● Secondly, the logical dynamic system is transferred into a bilinear system on the finite state set. The bilinear representation is used to study the process of the logical dynamic system.

In accordance with the modeling process of algebraic state space method, a NFSM $\mathcal{A}$ can be redefined as $Q = \{ q_1, q_2, \cdots, q_n\}$ and $\Sigma = \{ \sigma_1, \sigma_2, \cdots, \sigma_m\}$, and these variables are further set as $q_i = \delta _n^i$ ($i \in \{1, 2\ldots, n\}$) and $\sigma_k = \delta _m^k$ ($k \in \{1, 2\ldots, m\}$). Meanwhile, for the convenience, we list some variable symbols used later. $q^{ul}(\varsigma) = [q^{ul}_1(\varsigma), q^{ul}_2(\varsigma), \cdots, q^{ul}_n(\varsigma)]^T$ ($q^{l}(\varsigma) = [q^{l}_1(\varsigma), q^{l}_2(\varsigma), \cdots, q^{l}_n(\varsigma)]^T$) is expressed as the vector form of state reached at $t$ steps with (no) control packet loss, and $q^{ul}_i(\varsigma) = 1$ ($q^{l}_i(\varsigma) = 1$) is defined if, and only, if there is a transition that $q_i$ is reachable from $q^0$ with (no) control packet loss; $u(\varsigma) = [u_1(\varsigma), u_2(\varsigma), \cdots, u_m(\varsigma)]^T$ is termed as the event vector on $\Sigma$, and $u_k(\varsigma) = 1$ if $\sigma_k$ is enabled at $\varsigma$ steps. In the next section, we present the model dynamics and controllability analysis of NFSM with packet losses based on the representations.

3.   Controllability under random channel packet losses

3.1.   Models for random channel packet losses

In networked control systems, channel packet loss is inevitable due to the restricted bandwidth, especially in control (from supervisory controller to some remote actuators), which will lead to the occurrence of failure control. Firstly, given a NFSM $\mathcal{A} = \left(A, f_l\right)$,

Assumption 3.1. Before we present the main results, some assumptions are made in the following:

1. Each event in $\Sigma$ is disabled by default, and is only allowed to occur if it is enabled by a control command.

2. The communication losses are random, $i.e.$, the transitions in $f_l$ may or may not be communicated in control.

On the one hand, if the transitions in set $f_l$ are assumed to be communicated successfully in the control channel, the algebraic representation can be constructed in a manner similar to that described in the reference ^[13], and the dynamics of NFSM is shown as a discrete-time bi-linear form in the following form:

where $F^{ul}$ is called the state transition structure matrix with no control packet loss, and it is specifically defined as

where $F_k^{ul} \in \mathcal{M}_{n \times n}$ is defined as:

On the other hand, if the transitions in $f_l$ fails to be communicated to the plant, such transitions are disabled and will be permitted to occur until the transitions are not lost in a later step. In particular, for $(q, \sigma, q^{\prime})\in f_l$, not any transition labeled by $\sigma$ is enabled from state $q$ to $q^{\prime}$. In this situation, state $q$ will remain unchanged in itself with respect to event $\sigma$ under communication losses, which will alter the transition structure of NFSM. In order to characterize such changed transitions, we construct a new finite state machine, in which the transitions will be replaced with a self-loop if $(q, \sigma, q^{\prime}) \in f_l$ is not transmitted to the performer. Let's illustrate the above process with a simple example.

Example 3.1. Consider a NFSM $\mathcal{A} = \left(A, f_l\right)$, where $f_l = \{(q_1, \sigma_2, q_3), (q_3, \sigma_1, q_2)\}$, and if the transitions in $f_l$ are hypothesized to be transmitted through the control channel, and Figure 1 shows the state transition relationship among various states. Otherwise, the newly constructed finite state machine is represented as Figure 2. Note that the added self-loops in Figure 2 are represented by the dashed arrows on account of the communication losses, which can be obtained by substituting $(q_1, \sigma_2, q_3)$, $(q_3, \sigma_1, q_2)$ with $(q_1, \sigma_2, q_1)$, $(q_3, \sigma_1, q_3)$, respectively.

According to (3.2) and (3.3), we define a new structure matrix $F^{l}: = [F_1^{l}, F_2^{l}, \cdots, F_m^{l}] \in {\mathcal{M}_{n \times mn}}$ for the constructed NFSM, and the dynamics with control packet losses will be iterated according to the following equation:

However, the dynamics expressed by (3.1) and (3.4) can characterize both cases with complete communication losses, and the case with no packet loss. In practice, the losses in the control channel are random, $i.e.$, the transitions in $f_l$ may or may not be communicated in the control channel. So as to cope with the random packet losses, we introduce a state estimation with random channel packet losses, which can be depicted as follows:

where $\gamma$ is a random variable on behalf of the packet loss rate, which is independent of system state. Note that $q(\varsigma)$ is also stochastic because it merely refers to the source of randomness from $\gamma$, which is indeed a random variable, then the expectation of $q(\varsigma)$ will be implemented. In this work, it is assumed that the communication losses may happen according to the following Bernoulli random binary distribution:

where $\lambda \in [0, 1)$ is a constant and represents the probability that any transition in $f_l$ will be lost.

In the following theorem, the dynamics of NFSM with random channel packet losses can be established.

Theorem 3.1. Given a NFSM $\mathcal{A} = \left(A, f_l\right)$ with channel packet loss rate $\lambda$, the evolutionary dynamics can be described by the following stochastic logical equation:

where $\mathcal{F} = (1-\lambda) F^{ul}+\lambda F^l$ is termed as the probabilistic transition structure matrix (PTSM), and $E[q(\varsigma)]\in \mathcal{L}_{n}^s$ denotes the expected value of the reachable state $q(\varsigma)$ and $E[q(0)] = q^0$.

Proof. : For any state $q$ in the transition $(q, \sigma, q^{\prime}) \in f_{ul}$, $q(\varsigma) = q^{ul}(\varsigma) = q^l(\varsigma)$ is satisfied. According to (3.5), (3.6) and (3.7), we can obtain that

For state $q$ in the transition $(q, \sigma, q^{\prime}) \in f_l$, $q(\varsigma) = q^{ul}(\varsigma) = q^l(\varsigma)$ may be not satisfied. Generally, it is not hard to get that $E[q(\varsigma+1)]$ equals to $E[(1-\gamma) q^{ul}(\varsigma+1)+\gamma 0]$ or equals to $E[(1-\gamma)0 +\gamma q^l(\varsigma+1)]$. To sum up, $E[q(\varsigma+1)] = ((1-\lambda)F^{ul}+\lambda F^l) u(\varsigma) E[q(\varsigma)]$ represents the state transitions of NFSM with random packet loss rate.

In fact, the aforementioned theorem tells us that the NFSM with random channel packet losses can be captured by a special probabilistic finite state machine ^[31]. Next, by means of the matrix expression in Theorem 3.1, controllability of NFSM with random channel packet losses will be investigated.

Remark 3.1. In the previous work ^[13], we discussed the influence of arbitrary packet loss on the reachability, and a novel theoretical framework is proposed to analyze the robustness of reachable state from a switched perspective. Here, the controllability is studied by the matrix STP, but we concentrates on its analysis from a stochastic view. We firmly believe that the models proposed in this paper and ^[13] provide a very important basis for studying the control problem with network packet loss.

3.2.   Controllability analysis

In this subsection, we continue to investigate the controllability of NFSM (network controllability), where random packet losses are considered. Here, the definition of controllability with random channel packet losses are given as follows:

Definition 3.1. Given a NFSM $\mathcal{A} = \left(A, f_l\right)$ with channel packet loss rate $\lambda$,

(1) from the initial state $q^0 = \delta _n^i$, the target state $q_j = \delta _n^j$ is reachable at the $k$-th step $w.p.$ 1 ($k$-th reachable) if there is an event string $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \in \Sigma^{\ast}$ so that $\operatorname{Prob}\{q(k) = q_j\mid q(0) = q^0\} = 1$.

(2) the set of all $k$-th reachable states from $q^0$ is denoted by $\mathcal{R}_k(q^0)$. Furthermore, $\mathcal{R}(q^0)$ is said to be the set of all states reachable $w.p.$ 1 from $q^0$, and $\mathcal{R}(q^0) = \cup_{i \in \mathcal{N}^+} \mathcal{R}_{i}\left(q^0\right)$.

(3) system is said to be controllable $w.p.$ 1 from $q^0$ if $\mathcal{R}(q^0) = \Delta_n$.

Let us first introduce the notion of $k$-th transition probability matrix (TPM) with some sequence of events. Consider a NFSM with random channel packet losses. Suppose a specified input $u(\varsigma) = \delta _m^k$, Theorem 3.1 means $E[q(\varsigma + 1)] = \mathcal{F}\delta _m^k E[q(\varsigma)] = \mathcal{F}_k E[q(\varsigma)]$; in this case, $\mathcal{F}_k \in \mathcal{M}_{m\times n}$ is called the first step TPM from the current state $q(\varsigma)$ to the next $q(\varsigma+1)$ with the input $u(\varsigma)$, and rewritten as $\mathbb{P}^{1}$. Denote $k$-th TPM by $\mathbb{P}^{k} \in {\mathcal{M}_{n \times n}}$, whose $(i, j)$ entry is $\operatorname{Prob}\{q(t+k) = q_j\mid q(\varsigma) = q_i\}$, $i.e.$, the probability from the state vector $q(\varsigma) = \delta _n^i$ to $q(\varsigma+k) = \delta _n^j$ under a sequence of events $\ltimes _{c = 0}^{k-1}u(\varsigma+c)$ that is executed. By using the matrix STP and Theorem 3.1, $\mathbb{P}^{k}$ can be equivalently calculated through the iterative computation, and established in the following proposition.

Theorem 3.2. Given a NFSM $\mathcal{A} = \left(A, f_l\right)$ with a sequence of events $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \in \Sigma^{\ast}$, then the $k$-th TPM satisfies.

where $\mathbb{D}^{(k)} = (\mathcal{F}\Psi_{[n, m]})^{(k)}\Psi_{[m^k, n]} \in {\mathcal{M}_{n \times nm^k}}$, and $\Psi_{[n, m]}$ can be referred to the pseudo-commutativity.

Proof. Based on the matrix expression (3.8), we have the following result:

If $(\mathcal{F}\Psi_{[n, m]})^{(k)}\Psi_{[m^k, n]}$ is abbreviated as $\mathbb{D}^{(k)}$, then, $k$-th TPM $\mathbb{P}^{k}$ with a sequence of events $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \\\in \Sigma^{\ast}$ can be calculated as $\mathbb{D}^{(k)}\ltimes _{c = 0}^{k-1}\delta _m^{l_c}$.

Theorem 3.2 reveals that the matrix $\mathbb{D}^{(k)} \in {\mathcal{M}_{n \times nm^k}}^s$ consists of the current state transition probability and the event strings with respect to the reachable paths of $\mathcal{A}$, which provides an important basis for system control analysis and design. Here, let us go further to split $\mathbb{D}^{(k)}$ into $m^k$ blocks, and $\mathbb{D}_i^{(k)} \in {\mathcal{M}_{n \times n}}$, $i.e.$, $\mathbb{D}^{(k)} = [\mathbb{D}_1^{(k)}, \mathbb{D}_2^{(k)}, \ldots, \mathbb{D}_{m^k}^{(k)}]$. To characterize the controllability of NFSM with random channel packet losses, an operator $\langle \bullet \rangle$ is introduced and defined by

Finally, the main results to validate the criterion are derived based on the above preliminaries.

Theorem 3.3. Given a NFSM $\mathcal{A} = \left(A, f_l\right)$ with channel packet loss rate $\lambda$,

(1) the target state $q_j = \delta _n^j$ is $k$-th reachable from $q^0 = \delta _n^i$ iff

(2) the target state $q_j = \delta _n^j$ is reachable $w.p.$ 1 from $q^0 = \delta _n^i$ iff there is a positive integer $\alpha$, such that

(3) the NFSM is controllable $w.p.$ 1 from $q^0 = \delta _n^i$ iff the positive integer $\alpha$ satisfies the following condition

Proof. (1) 'if' part: According to the definition of operator $\langle \bullet \rangle$ in Eq. (3.12), $\mathbf{L}^k_{(j, i)} = 1$, $i.e.$, $\langle \mathbb{D}^{(k)} \rangle_{(j, i)} = 1$ iff there is a positive integer $\beta \in \{1, 2, \ldots, m^k\}$, such that $(\mathbb{D}_\beta^{(k)})_{(j, i)} = 1$. According to (3.11), it means that a sequence of events $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \in \Sigma^{\ast}$ exists that $(\mathbb{D}^{(k)} \ltimes _{c = 0}^{k-1}\delta _m^{l_c})_{(j, i)} = 1$, $i.e.$, $\mathbb{P}^{k}_{(j, i)} = 1$ is satisfied. Then, an input string $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \in \Sigma^{\ast}$ can satisfy the condition $\operatorname{Prob}\{q(k) = q_j\mid q(0) = q^0\} = 1$.

'only if' part: If state $q_j = \delta _n^j$ is $k$-th reachable from $q^0 = \delta _n^i$, we prove that $\mathbf{L}^k_{(j, i)} = 1$ is satisfied. Based on the matrix expression (3.8) and Theorem 3.2, the condition shows that there is a sequence of events $s = \sigma_{l_0} \sigma_{l_1} \ldots, \sigma_{l_{k-1}} \in \Sigma^{\ast}$, such that $\delta _n^j = E[x(k)] = \mathbb{P}^{k}\delta _n^i$, $i.e.$, $\mathbb{P}^{k}_{(j, i)} = 1$, which implies that $\beta \in \{1, 2, \ldots, m^k\}$ exists, such that $(\mathbb{D}_\beta^{(k)})_{(j, i)} = 1$. Then clearly, $\mathbf{L}^k_{(j, i)} = (\langle \mathbb{D}^{(k)} \rangle)_{(j, i)} = 1$ is tenable.

(2) 'if' part: we suppose that there is a positive integer $\alpha$ such that

and the existence of $k \in \{1, 2, \ldots, \alpha\}$ makes the formula $\mathbf{L}^k_{(j, i)} = 1$ true. Based on Eq. (3.13), the target state $q_j = \delta _n^j$ is $k$-th reachable $w.p.$ 1 from $q^0 = \delta _n^i$. $i.e.$, state $q_j = \delta _n^j$ is reachable $w.p.$ 1 from $q^0 = \delta _n^i$.

'only if' part: If state $q_j = \delta _n^j$ is reachable $w.p.$ 1 from $q^0 = \delta _n^i$, based on the result mentioned above, we can obtain that $\mathbf{L}^{k_1}_{(j, i)} = 1$, $\mathbf{L}^{k_2}_{(j, i)} = 1$, $\cdots$, or $\mathbf{L}^{k_\tau}_{(j, i)} = 1$. Thus, $\bigvee_{k = 1}^{\alpha} \mathbf{L}^k_{(j, i)} = 1$ can be arrived at, where $\alpha = max\{k_1, k_2, \ldots, k_\tau\}$.

(3) 'if' part: If there is a positive integer $\alpha$ such that

it is satisfied that $\mathbf{L}^{k_1}_{(1, i)} = 1$, $\mathbf{L}^{k_2}_{(2, i)} = 1$, $\cdots$, $\mathbf{L}^{k_\tau}_{(n, i)} = 1$, where $k_i \in \{1, 2, \ldots, \alpha\}$. Based on the aforementioned result, state $q_j = \delta _n^j$ is $k_j$-th reachable $w.p.$ 1 from $q^0 = \delta _n^i$, $i.e.$, the $k_j$-step reachable set $w.p.$ 1 $\mathcal{R}_{k_j}(q^0) = q_j$, and $\mathcal{R}(q_{0}) = \cup_{j \leq \alpha} \mathcal{R}_{k_j}\left(q^0\right) = \Delta_n$. Henceforth, the NFSM system with random packet loss is thought to be controllable $w.p.$ 1 from $q^0$.

'only if' part: If the system is controllable $w.p.$ 1 from $q^0 = \delta _n^i$, it is obvious that the reachable states $w.p.$ 1 from $q^0$ satisfy $\mathcal{R}(q_{0}) = \Delta_n$. According to Eq. (3.13), we can derive that $\mathbf{L}^{k_1}_{(1, i)} = 1$, $\mathbf{L}^{k_2}_{(2, i)} = 1$, $\cdots$, $\mathbf{L}^{k_\tau}_{(n, i)} = 1$. In brief, $\bigvee_{k = 1}^{\alpha} Col_i(\mathbf{L}^k) = \mathbf{1}_n$, where $\alpha = max\{k_1, k_2, \ldots, k_\tau\}$.

Remark 3.2. In this paper, the impact of random channel packet losses on the controllability of NFSM is systematically studied. We discover that the dynamics of NFSM with random channel packet losses can be expressed as a probabilistic finite state machine by utilizing the state estimation, and such dynamics take into account the probability $\lambda$ of random channel packet losses from the controller to actuator, which provides us an important model for quantitative analysis.

Remark 3.3. On a broader note, the underlying evolution of the states seems analogous to that of a discrete-time finite Markov chain, where the transition probabilities depend on the packet loss. The results in this paper are equivalent to the irreducibility of the Markov chain. However, we put more emphasis on the controllable paths from the initial state. With the assistance of matrix STP, the algebraic representation of NFSM with channel packet loss rate $\lambda$ is established, and the verification criteria for the controllability $w.p.$ 1 are derived by the $k$-th transition probability matrix $\mathbb{P}^{k}$.

4.   Numerical example

In this section, we utilize a typical example to validate the theoretical results in Section 3.

Example 4.1. Considering a networked flexible manufacturing system, it is characterized as a FSM $A = \left(Q, \Sigma, f, q^0\right)$, and its corresponding evolution graph is depicted in Figure 3, where $Q = \{q_1, \cdots, q_9\}$ and $\Sigma = \{\sigma_1, \cdots, \sigma_4\}$ denote the different states and signal indicators. Due to the relatively far transmission distance, it is assumed that the occurrences in $f_l = \{(q_1, \sigma_2, q_7), (q_7, \sigma_3, q_1), (q_2, \sigma_3, q_8), (q_8, \sigma_4, q_2), (q_3, \sigma_1, q_9), \\ (q_9, \sigma_3, q_3)\}$ is communicated with channel packet loss rate $\lambda = 0.25$. The following graph (see Figure 4) represents the state transition diagram with packet losses.

When taking the packet loss rate into account, the evolution dynamics on NFSM can be termed as $E[q(\varsigma + 1)] = \mathcal{F}u(\varsigma)E[q(\varsigma)]$, and its corresponding PTSM can be written as $\mathcal{F} = \{\mathcal{F}_1, \mathcal{F}_2, \mathcal{F}_3, \mathcal{F}_4\}$, which is calculated based on Theorem 3.1. The resulting constructed state diagram is shown as Figure 5 by adding the channel packet loss rate $\lambda = 0.25$. In this manufacturing system, some transactions are always assigned to accomplish important tasks, for example, from interface states $q_2, q_5$ to $q_1$. Next, we will show how to verify the controllability $w.p.$ 1.

According to Theorem 3.3, when $k = 3$, the reachability matrix with random packet loss rate $\bigvee_{\mu = 1}^{k}\mathbf{L}^{(\mu)}$ can be obtained in the following:

Notice that $\bigvee_{\mu = 1}^{3}\mathbf{L}^{(\mu)}_{(1, 5)} = \bigvee_{\mu = 1}^{3}\mathbf{L}^{(\mu)}_{(1, 2)} = 1$, state $q_1 = \delta _9^1$ is reachable $w.p.$ 1 from $q_2 = \delta _9^2$ and $q_5 = \delta _9^5$, respectively.

When considering system information security issues, some states are supposed to be safe, such as $q_1 = \delta _9^1$ and the state will be labeled as a target state, which is required to be arrived from all states. Through some iterative calculations, if $k = 4$, the reachability matrix with random packet loss rate $\bigvee_{\mu = 1}^{4}\mathbf{L}^{(\mu)}$ is computed as:

Clearly, $\bigvee_{\mu = 1}^{4}\mathbb{L}^{(\mu)}_{(1, :)} = \textbf{1}_9^T$, $i.e.$, state $q_1 = \delta _9^1$ is reachable $w.p.$ 1, which implies that state $q_1 = \delta _9^1$ is reachable with random packet loss.

5.   Conclusions

In conclusion, the controllability of NFSM with random channel packet losses is explored, in terms of an algebraic state space approach. With the help of matrix STP, the probabilistic logic representation of NFSM with packet loss rate is proposed, which converts the NFSM with random channel packet losses to a special probabilistic automaton. Then, starting from the strict algebraic derivation, some concise validation conditions for the controllability $w.p.$ 1 are obtained for NFSM. Finally, the numerical example demonstrates that the proposed model is succinct and effective.

In future studies, we are planning to address some more complicated problems. For example, opacity ^[32,33] is a very important concept of security information flow, and stochastic opacity with random channel packet losses can be investigated, based on the reachability concept proposed in this paper.

Acknowledgments

We acknowledge the funding support of the National Natural Science Foundation of China under Grant 62203328 and 62173247, Tianjin Natural Science Foundation of China Grant No. 21JCQNJC00840 and Tianjin Research Innovation Project for Postgraduate Students under Grant No. 2021YJSB251.

Conflict of interest

The authors declare that there are no potential conflicts of interests.