# Partially Measured State Estimation of Complex Dynamical Networks with Random Data Loss

Authors: Ke Zhang; Nan Wang; Xingdong Hua; Xinwei Wang; Xu Wu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The state estimation problem is a very important and interesting issue in the field of complex dynamical networks. Yet, the constructions of the state estimators in most existing literature studies all need to measure the output information of all nodes. However, the practical situation is that not all nodes could be measured to obtain the output information. Thus, in this paper, the state estimation is realized while only measuring the output data of partial nodes for a complex dynamical network with random data loss existing on its external communication links to the observers, where the lost data are compensated by the corresponding observer data. Depending on whether the network possesses the root strongly connected components that have a perfect matching, the choice problem of measured nodes and the construction problem of specific output matrices are discussed. By applying the Lyapunov stability theory and stochastic analysis method, a sufficient condition for state estimation is given. Through simulation experiments, the effectiveness of the proposed state estimation scheme is demonstrated.


---

## Body

## 1. Introduction

In the last few decades, complex networks have been paid much attention due to their ability to describe many networks in the real world, such as social networks, biological networks, communication networks, transportation networks, and power grids. The small-world and scale-free characteristics of complex networks have been studied [1, 2], and many research studies for complex networks have been conducted increasingly in different fields [3–10].Due to the large-scale characteristic of complex networks, it is realistic that partial states of networks cannot be measured in general. So, it is necessary to estimate the states and construct the state estimator, which is an enduring research topic [11–14]. Simultaneously, the phenomenon of the information loss often exists in real networks [15–21]. Hence, the data loss should be considered in the state estimation of complex networks.When constructing the state estimators of complex networks, most previous studies require the output information of all nodes. However, the reality is that the output information of all nodes cannot be measured, so it is interesting to achieve state estimation while measuring the output data of partial nodes. The idea of the partial measurement is similar to the pinning control. It is theoretically possible to set controllers for each node of the network, but there are a large number of nodes in complex networks, which requires setting controllers of large size and simultaneously needs to measure and transmit the output information of all nodes. It is neither economical nor practical; thus, the pinning control strategy was introduced. The basic idea of the pinning control is to control the behaviour of the entire network by exerting control on only a portion of the nodes. Wang and Chen [22], firstly, proposed the pinning synchronization control of the scale-free complex networks, and considering the pinning strategy with the large degree nodes and the stochastic nodes, it is found that the number of pinning nodes of the former is significantly less than the latter. Li et al. [23] studied the pinning control problem of stochastic networks and scale-free networks, where the virtual control was used on pinned nodes to control other nodes through the connections between nodes. Yu et al. [24] investigated the synchronization problem of general complex dynamic networks by the pinning control; a pinning algorithm was proposed by, respectively, exploring the relationships between the pinned nodes and the structures of the strongly connected networks, the weakly connected networks, the directed spanning tree networks, and the directed forest networks. Besides the pinning control idea, some works directly focused on the state estimation problem based on the partial nodes by constructing specific Lyapunov–Krasovskii functionals [25–27] or developing a recursive estimator based on the framework of the extended Kalman filter (EKF) [28]. While these existing studies have not addressed the problem of determining the exact number and the locations of these partial nodes, in this paper, this problem is addressed from the perspective of the network controllability and observability.A remarkable work on the structural controllability of complex networks by Liu et al. [29] has drawn wide and strong attention in a complex network control area. Based on the study of the system structural controllability by Lin [30], they transformed the structural controllability problem into a maximum matching problem on a bipartite graph and proposed the minimum inputs theorem to obtain the minimum driver nodes which could guarantee the network is fully controllable. Later, Liu et al. [31] addressed the structural observability problem of complex systems, and based on the concept of strongly connected components in the graph theory, a graphical approach was proposed to obtain the minimum number of sensors needed. Thereafter, a large number of research studies focused on the effects of network topology, internal interactions, and node dynamics on network controllability and observability [32–38]. Most of these results identify the driver nodes; however, the controller configuration needs to determine all the controlled nodes. When the network structure exhibits the root strongly connected components which have the perfect matching, there are more controlled nodes than driver nodes. Hence in this paper, the problem of determining the controlled or measured nodes is addressed.Motivated by the discussions above, in this paper, based on the idea of the structural observability, the state estimation problem is investigated for the case that the external communication links between the complex network and the observer have the random data loss, while only measuring the output data of partial nodes. And the selection of the measured nodes and the specific construction of output matrices are discussed according to whether the network structure exhibits the root strongly connected components which have the perfect matching. Then, the Lyapunov stability theory and stochastic analysis method are applied to derive a sufficient condition to realize the state estimation and determine the appropriate observer gains.The rest of the paper is organized as follows: In Section2, the problem to be studied is formulated. In Section 3, the identification of the measured nodes and the specific construction of output matrices are discussed, and then, a sufficient condition for state estimation is derived. Section 4 verifies the effectiveness of the proposed state estimation scheme for two cases of synchronous and independent data loss on multichannels. Section 5 concludes this work.Notations: the vectors and matrices are in bold type.I and O denote an identity matrix and a zero matrix of suitable dimensions, respectively. XN×N is a N×N block matrix whose every block is X. ⊗ denotes the Kronecker product. diag⋯ denotes a block-diagonal matrix. ∗ denotes the transpose of symmetric term. E⋅ denotes the operator of the mathematical expectation.


## 2. Problem Formulation

We consider the communication links between the complex network and the corresponding observer network exhibiting the random data loss, and we use the observer output data to compensate for the lost output data of the original network. The state estimation scheme is as follows:(1)xi,k+1=Axi,k+d∑j=1NcijΓxj,k,yi,k=Hixi,k,(2)y¯i,k=ϕi,kyi,k+1−ϕi,ky^i,k,(3)x^i,k+1=Ax^i,k+d∑j=1NcijΓx^j,k+Kiy^i,k−y¯i,k,y^i,k=Hix^i,k,where equation (1) is the estimated complex network, equation (2) denotes the actual output data received by the observer, and equation (3) is the constructed state observer. i=1,2,…,N, xi,k=xi1,k,xi2,k,...,xin,kT∈Rn is the n-dimensional state vector of the ith node at time k, yi,k∈Rmm≤n represents the output vector of the ith node at time k, y¯i,k∈Rm is the actual output data received by the observer from the original network, x∧i,k=x^i1,k,x^i2,k,...,x^in,kT∈Rn is the observed value of xi,k, and y^i,k∈Rm is the output vector of the observer, namely, the observed value of yi,k. A∈Rn×n is the coefficient matrix of the node system, d indicates the coupling strength of the network, and C=cijN×N is the coupling matrix of the network which represents the topology of the network. If there is a link between the ith node and the jth node, then cij≠0 and cji≠0; otherwise, cij=cji=0. Γ∈Rn×n is the internal connecting matrix between the connected nodes which is assumed to be an identity matrix in this paper, and Ki∈Rn×m are the observer gains. ϕi,k∈R are Bernoulli random variables satisfying the independent identically distribution which describe the data loss over the communication links between the network and the observer; each of them takes the value 0 or 1 with the following probability:(4)Prϕi,k=1=Eϕi,k=ϕi¯,Prϕi,k=0=1−ϕi¯=ϕi˜,and ϕ˜i is the data loss rate of each channel; ϕ¯i≠0 for i∈Smeasured (Smeasured is the set of indices of the measured nodes); otherwise, ϕ¯i=0. ϕi,k=1 indicates that the output data of the ith node of the network at time k are successfully transmitted to the observer; otherwise, ϕi,k=0 indicates that the output data are lost and not transmitted to the observer. Hi∈Rm×n is the output matrix of the ith node; here, it only needs to measure the output data of partial nodes, that is as follows:(5)Hi≠O,i∈Smeasured,=O,i∈1,…,N−Smeasured.TheSmeasured will be determined in Section 3.The estimation errors are as follows:(6)ei,k=x^i,k−xi,ki=1,2,…,N,and then, the following error system is obtained from equations (1)–(3):(7)ei,k+1=x^i,k+1−xi,k+1=Ax^i,k+d∑j=1NcijΓx^j,k+Kiy^i,k−y¯i,k−Axi,k−d∑j=1NcijΓxj,k=Ax^i,k−Axi,k+d∑j=1NcijΓx^j,k−d∑j=1NcijΓxj,k+Kiy^i,k−ϕi,kyi,k−1−ϕi,ky^i,k=Aei,k+d∑j=1NcijΓej,k+Kiϕi,ky^i,k−ϕi,kyi,k=Aei,k+d∑j=1NcijΓej,k+ϕi,kKiHiei,k.Here, the aim is to determine the output matricesHi and the observer gains Ki so that the estimation errors could asymptotically converge to zero.


## 3. Main Results

First, the selection of the measured nodes and the specific construction of output matrices will be discussed. Then, the observer gains will be determined.


### 3.1. Determining the Output Matrices

Some concepts of the graph theory are recalled as follows.Definition 1 (see [29]).
For a digraph, the maximum matching includes the largest subset of edges which do not share common starting nodes or ending nodes.
A node is matched if it is an ending node of an edge in the matching, and the others are unmatched nodes. The maximum matching is perfect if every node is matched.Definition 2 (see [31]).
For a digraph, a strongly connected component (SCC) is a subgraph where there is a directed path from each node to every other node.
A SCC is a root SCC (rSCC) if it has no incoming edges to its nodes from other nodes; that is, the rSCC is overall inaccessible. A rSCC whose maximum matching is a perfect matching is called a pm-rSCC in this paper. Because its matching is perfect, the pm-rSCC does not have unmatched nodes, but due to its inaccessibility, we need to measure it and it is enough to measure a random node of it. Therefore, if we try to determine which nodes should be measured, we need to discuss it according to whether the pm-rSCC exists.Case 1.
The network structure does not exhibit any pm-rSCC.
If the network structure does not exhibit the pm-rSCC, determining the nodes to be measured is equal to determining the unmatched nodes. Then, aiming at the complex network with multidimensional node dynamics considered in this paper, according to the results in [39], the measured nodes could be obtained by applying the maximum matching principle to the network topology. For these measured nodes, it only needs to measure some partial states to observe the whole network. If the network topology is perfect matching, the states to be measured could be obtained by applying the graphical approach to the node structure; otherwise, the measured states could be obtained by applying the maximum matching principle to the node structure. Then, Hi could be determined according to the measured states.Remark 1.
The partial measurement in this paper refers to the measurement of both the partial nodes and the calculation of partial states of these measured nodes.Remark 2.
In this paper, the whole network structure is composed of the network topology, node dynamics, and internal interactions. It is assumed that the connections between the nodes are bidirectional, so the network topology does not exhibit any pm-rSCC. If the nodes are considered to have multidimensional dynamics, then the node has its own structure, called the node structure, which could exhibit the pm-rSCCs. So, the statement that network structure exhibits the pm-rSCCs means the node structure exhibits the pm-rSCCs.Case 2.
The network structure exhibits the pm-rSCCs.
As mentioned before, the measured nodes could be obtained by applying the maximum matching principle to the network topology, and if the node structure exhibits the pm-rSCCs, then besides the unmatched states in these measured nodes chosen as the measured states, it also needs to choose a random state from each pm-rSCC as a measured state. In order to minimize the number of measured states, here the strategy that maximizing the number of pm-rSCCs that contain unmatched states is adopted.
The whole network is introduced on a digraph which is composed of the network topology, node structure, and internal interactions, where the network topology is expressed asGD by drawing a directed edge xi⟶xj if dij≠0, the node structure is expressed as GA=V,E with V=x1,…,xn being the vertex set and E=xp,xqapq≠0 being the edge set, and because Γ is assumed to be an identity matrix here, the internal interactions are represented by drawing n directed edges xip⟶xjpp=1,…,n if dij≠0. To apply the maximum matching principle to the digraph, the corresponding bipartite graph should be obtained. For the node structure GA, its bipartite graph is denoted as BGV+,V−,E′ with V+=x1+,⋯,xn+ and V−=x1−,…,xn− being the sets of starting and ending vertices and E′=xp+,xq−apq≠0. The ending vertex of a matching edge is matched. Otherwise, it is unmatched. A simple example is shown in Figure 1.
According to the strategy mentioned before, Algorithm is proposed to find a minimum measured state set of the whole network and an illustrative example is shown in Figure2 to explain the process of obtaining the set of measured states of one measured node. The output matrices Hi could be determined according to the measured states obtained by this algorithm.
Algorithm 1: Find a minimum measured state set of the network.
Input: network topology GD, node structure GA, bipartite graph of GABGV+,V−,E′Output: Set of unmatched states Viunmatched and measured states Vimeasured of the measured node xi, i∈Smeasured, set of the minimum measured states of the network Vmeasured(1)
InitializeViunmatched=, Vimeasured=, Vmeasured=;(2)
Applying the maximum matching toGD, obtain the unmatched nodes, namely the measured nodes xi, i∈Smeasured;(3)
Applying the depth-first search onGA and testing the maximum matching of each rSCC, obtain the pm-rSCCs, denoted by δl, l∈I=1,…,α;(4)
Compute an initial maximum matchingMini associated with BGV+,V−,E′;(5)
Vp=;(6)
for all μ∈δ1∪⋯∪δα−Vp(7)
Compute a maximum matchingMμ associated with BGV+,V−,E′−ν,μ:ν∈V, getting the unmatched state set Vμ;(8)
ifMμ==Miniμ∈δl(9)
E′=E′−ν,μ:ν∈V;(10)
Viunmatched=Vμ;(11)
I=I−l;(12)
Vp=Vp∪ωl;(13)
end if(14)
end for(15)
Vimeasured=Viunmatched;(16)
for all l∈I(17)
Randomly select a stateμ from δl and Vimeasured=Vimeasured∪μ;(18)
end(19)
for all i∈Smeasured(20)
Vmeasured=Vmeasured∪Vimeasured(21)
endFigure 1
A simple network. (a) Network topology and its maximum matching: the node is marked in grey, the connections are marked by arrows, the matching edges are marked in red, matched nodes are marked in green, andx1, x2, x3, and x5 are matched. (b) Node structure and its maximum matching: the states are marked in white, the interactive relations are marked by grey dashed arrows, and xi1 and xi2 are matched. (c) Network structure: there are five nodes. (d) Observing the node system: besides the unmatched state xi3, it also needs to choose the state xi1 as a measured state because xi1 composes a pm-rSCC.
(a)(b)(c)(d)Figure 2
Illustration of obtaining the set of measured states of one measured node. (a) The node consists of 7 states. (b) There exist 3 pm-rSCCs, denoted byδ1, δ2, and δ3 and marked by a blue dashed rectangle. The initial matching edges are marked in red, where Mini=5. (c) Set the state xi1 as an unmatched state by leaving out the edge xi2,xi1, where Mxi1=4≠Mini. (d) Set the state xi2 as an unmatched state by leaving out the edge xi1,xi2, where Mxi2=5=Mini. (e) Set the state xi3 as an unmatched state by leaving out the edge xi3,xi3, where Mxi3=4≠Mini. (f) Set the state xi6 as an unmatched state by leaving out the edge xi6,xi6, where Mxi6=5=Mini. (g) Finally, the unmatched states are xi2 and xi6 and the measured states are xi2, xi3 and xi6, which are marked in yellow.
(a)(b)(c)(d)(e)(f)(g)Remark 3.
In Algorithm 1, the time complexity of computing the maximum matching ofGD is ONED, where ED is the set of edges. To obtain the pm-rSCCs, we need to use two depth-first searches on GA with OV+E and test the maximum matching of each rSCC. Computing the initial maximum matching Mini has the complexity OVE. Finally, the time complexity of getting the minimum measured states of the network Vmeasured is ∑l=1αδlOVE.


### 3.2. Determining the Observer Gains

After the output matricesHi have been determined, a sufficient condition for the state estimation will be derived; thereupon, the observer gains Ki will be determined.Theorem 1.
If there exist positive definite symmetric matricesPii=1,...,N and matrices Si satisfying the inequality(8)ΞΦGΦGT−Π<0,where(9)Ξ=A¯TΠA¯+Φ2GA¯+Φ2A¯TGT+dA¯TΠQ+Φ2dGQ+dQTΠA¯+Φ2dQTGT+d2Θ−Π,Si=PiKi,Φ=diagϕ¯1In,⋯,ϕ¯NIn,A¯=IN⊗A,Π=diagP1,⋯,PN,G=diagH1TS1T,⋯,HNTSNT,Q=C⊗InΓN×N,Θ=∑i=1Nci12ΓTPiΓ∑i=1Nci1ΓTPici2Γ⋯∑i=1Nci1ΓTPiciNΓ∗∑i=1Nci22ΓTPiΓ⋯∑i=1Nci2ΓTPiciNΓ⋮⋮⋱⋮∗∗⋯∑i=1NciN2ΓTPiΓ,then error system (7) is asymptotically stable, and the errors will eventually converge to zero. The observer gains Ki=Pi−1Si.Remark 4.
The existing studies which focused on the state estimation problem based on the partial nodes [25–28] have not addressed the problem of determining the exact number and the locations of these partial nodes, i.e., the exact the output matrices Hi, while in this paper, this problem is studied from the perspective of the network controllability and observability, and this is the main contribution of this work.Proof.
The following Lyapunov function is chosen:(10)Vk=∑i=1Nei,kTPiei,k.
Deriving the difference ofVk, the following is obtained:(11)ΔVk=Vk+1−Vk=∑i=1Nei,k+1TPiei,k+1−ei,kTPiei,k=∑i=1NAei,k+d∑j=1NcijΓej,k+ϕi,kKiHiei,kTPiAei,k+d∑j=1NcijΓej,k+ϕi,kKiHiei,k−ei,kTPiei,k=∑i=1Nei,kTATPiAei,k+∑i=1Nei,kTATPid∑j=1NcijΓej,k+∑i=1Nei,kTATPiϕi,kKiHiei,k+∑i=1Nd∑j=1NcijΓej,kTPiAei,k+∑i=1Nd∑j=1NcijΓej,kTPid∑j=1NcijΓej,k+∑i=1Nd∑j=1NcijΓej,kTPiϕi,kKiHiei,k+∑i=1Nei,kTϕi,kHiTKiTPiAei,k+∑i=1Nei,kTϕi,kHiTKiTPid∑j=1NcijΓej,k+∑i=1Nei,kTϕi,kHiTKiTPiϕi,kKiHiei,k−∑i=1Nei,kTPiei,k.
LetΛ=diagH1TS1TP1−1S1H1,⋯,HNTSNTPN−1SNHNek=e1,kT⋯eN,kTT, and taking the mathematical expectation of ΔVk, we could obtain the following:(12)EΔVk=ekTA¯TΠA¯ek+ekTdA¯TΠQek+ekTΦ2A¯TGTek+ekTdQTΠA¯ek+ekTd2Θek+ekTΦ2dQTGTek+ekTΦ2GA¯ek+ekTΦ2dGQek+ekTΦ2Λek−ekTΠek=ekTΦ2Λ+A¯TΠA¯+Φ2GA¯+Φ2A¯TGT+dA¯TΠQ+Φ2dGQ+dQTΠA¯+Φ2dQTGT+d2Θ−Πek=ekTΞek.
Then, applying the Schur complement lemma, inequality (8) can be obtained from Ξ<0.
If inequality (8) holds, then according to the Lyapunov stability theory and stochastic analysis method, it is known that error system (7) is asymptotically stable and the error will eventually converge to zero. Then, the corresponding observer gains could be obtained by Ki=Pi−1Si. The proof is completed.


## 3.1. Determining the Output Matrices

Some concepts of the graph theory are recalled as follows.Definition 1 (see [29]).
For a digraph, the maximum matching includes the largest subset of edges which do not share common starting nodes or ending nodes.
A node is matched if it is an ending node of an edge in the matching, and the others are unmatched nodes. The maximum matching is perfect if every node is matched.Definition 2 (see [31]).
For a digraph, a strongly connected component (SCC) is a subgraph where there is a directed path from each node to every other node.
A SCC is a root SCC (rSCC) if it has no incoming edges to its nodes from other nodes; that is, the rSCC is overall inaccessible. A rSCC whose maximum matching is a perfect matching is called a pm-rSCC in this paper. Because its matching is perfect, the pm-rSCC does not have unmatched nodes, but due to its inaccessibility, we need to measure it and it is enough to measure a random node of it. Therefore, if we try to determine which nodes should be measured, we need to discuss it according to whether the pm-rSCC exists.Case 1.
The network structure does not exhibit any pm-rSCC.
If the network structure does not exhibit the pm-rSCC, determining the nodes to be measured is equal to determining the unmatched nodes. Then, aiming at the complex network with multidimensional node dynamics considered in this paper, according to the results in [39], the measured nodes could be obtained by applying the maximum matching principle to the network topology. For these measured nodes, it only needs to measure some partial states to observe the whole network. If the network topology is perfect matching, the states to be measured could be obtained by applying the graphical approach to the node structure; otherwise, the measured states could be obtained by applying the maximum matching principle to the node structure. Then, Hi could be determined according to the measured states.Remark 1.
The partial measurement in this paper refers to the measurement of both the partial nodes and the calculation of partial states of these measured nodes.Remark 2.
In this paper, the whole network structure is composed of the network topology, node dynamics, and internal interactions. It is assumed that the connections between the nodes are bidirectional, so the network topology does not exhibit any pm-rSCC. If the nodes are considered to have multidimensional dynamics, then the node has its own structure, called the node structure, which could exhibit the pm-rSCCs. So, the statement that network structure exhibits the pm-rSCCs means the node structure exhibits the pm-rSCCs.Case 2.
The network structure exhibits the pm-rSCCs.
As mentioned before, the measured nodes could be obtained by applying the maximum matching principle to the network topology, and if the node structure exhibits the pm-rSCCs, then besides the unmatched states in these measured nodes chosen as the measured states, it also needs to choose a random state from each pm-rSCC as a measured state. In order to minimize the number of measured states, here the strategy that maximizing the number of pm-rSCCs that contain unmatched states is adopted.
The whole network is introduced on a digraph which is composed of the network topology, node structure, and internal interactions, where the network topology is expressed asGD by drawing a directed edge xi⟶xj if dij≠0, the node structure is expressed as GA=V,E with V=x1,…,xn being the vertex set and E=xp,xqapq≠0 being the edge set, and because Γ is assumed to be an identity matrix here, the internal interactions are represented by drawing n directed edges xip⟶xjpp=1,…,n if dij≠0. To apply the maximum matching principle to the digraph, the corresponding bipartite graph should be obtained. For the node structure GA, its bipartite graph is denoted as BGV+,V−,E′ with V+=x1+,⋯,xn+ and V−=x1−,…,xn− being the sets of starting and ending vertices and E′=xp+,xq−apq≠0. The ending vertex of a matching edge is matched. Otherwise, it is unmatched. A simple example is shown in Figure 1.
According to the strategy mentioned before, Algorithm is proposed to find a minimum measured state set of the whole network and an illustrative example is shown in Figure2 to explain the process of obtaining the set of measured states of one measured node. The output matrices Hi could be determined according to the measured states obtained by this algorithm.
Algorithm 1: Find a minimum measured state set of the network.
Input: network topology GD, node structure GA, bipartite graph of GABGV+,V−,E′Output: Set of unmatched states Viunmatched and measured states Vimeasured of the measured node xi, i∈Smeasured, set of the minimum measured states of the network Vmeasured(1)
InitializeViunmatched=, Vimeasured=, Vmeasured=;(2)
Applying the maximum matching toGD, obtain the unmatched nodes, namely the measured nodes xi, i∈Smeasured;(3)
Applying the depth-first search onGA and testing the maximum matching of each rSCC, obtain the pm-rSCCs, denoted by δl, l∈I=1,…,α;(4)
Compute an initial maximum matchingMini associated with BGV+,V−,E′;(5)
Vp=;(6)
for all μ∈δ1∪⋯∪δα−Vp(7)
Compute a maximum matchingMμ associated with BGV+,V−,E′−ν,μ:ν∈V, getting the unmatched state set Vμ;(8)
ifMμ==Miniμ∈δl(9)
E′=E′−ν,μ:ν∈V;(10)
Viunmatched=Vμ;(11)
I=I−l;(12)
Vp=Vp∪ωl;(13)
end if(14)
end for(15)
Vimeasured=Viunmatched;(16)
for all l∈I(17)
Randomly select a stateμ from δl and Vimeasured=Vimeasured∪μ;(18)
end(19)
for all i∈Smeasured(20)
Vmeasured=Vmeasured∪Vimeasured(21)
endFigure 1
A simple network. (a) Network topology and its maximum matching: the node is marked in grey, the connections are marked by arrows, the matching edges are marked in red, matched nodes are marked in green, andx1, x2, x3, and x5 are matched. (b) Node structure and its maximum matching: the states are marked in white, the interactive relations are marked by grey dashed arrows, and xi1 and xi2 are matched. (c) Network structure: there are five nodes. (d) Observing the node system: besides the unmatched state xi3, it also needs to choose the state xi1 as a measured state because xi1 composes a pm-rSCC.
(a)(b)(c)(d)Figure 2
Illustration of obtaining the set of measured states of one measured node. (a) The node consists of 7 states. (b) There exist 3 pm-rSCCs, denoted byδ1, δ2, and δ3 and marked by a blue dashed rectangle. The initial matching edges are marked in red, where Mini=5. (c) Set the state xi1 as an unmatched state by leaving out the edge xi2,xi1, where Mxi1=4≠Mini. (d) Set the state xi2 as an unmatched state by leaving out the edge xi1,xi2, where Mxi2=5=Mini. (e) Set the state xi3 as an unmatched state by leaving out the edge xi3,xi3, where Mxi3=4≠Mini. (f) Set the state xi6 as an unmatched state by leaving out the edge xi6,xi6, where Mxi6=5=Mini. (g) Finally, the unmatched states are xi2 and xi6 and the measured states are xi2, xi3 and xi6, which are marked in yellow.
(a)(b)(c)(d)(e)(f)(g)Remark 3.
In Algorithm 1, the time complexity of computing the maximum matching ofGD is ONED, where ED is the set of edges. To obtain the pm-rSCCs, we need to use two depth-first searches on GA with OV+E and test the maximum matching of each rSCC. Computing the initial maximum matching Mini has the complexity OVE. Finally, the time complexity of getting the minimum measured states of the network Vmeasured is ∑l=1αδlOVE.


## 3.2. Determining the Observer Gains

After the output matricesHi have been determined, a sufficient condition for the state estimation will be derived; thereupon, the observer gains Ki will be determined.Theorem 1.
If there exist positive definite symmetric matricesPii=1,...,N and matrices Si satisfying the inequality(8)ΞΦGΦGT−Π<0,where(9)Ξ=A¯TΠA¯+Φ2GA¯+Φ2A¯TGT+dA¯TΠQ+Φ2dGQ+dQTΠA¯+Φ2dQTGT+d2Θ−Π,Si=PiKi,Φ=diagϕ¯1In,⋯,ϕ¯NIn,A¯=IN⊗A,Π=diagP1,⋯,PN,G=diagH1TS1T,⋯,HNTSNT,Q=C⊗InΓN×N,Θ=∑i=1Nci12ΓTPiΓ∑i=1Nci1ΓTPici2Γ⋯∑i=1Nci1ΓTPiciNΓ∗∑i=1Nci22ΓTPiΓ⋯∑i=1Nci2ΓTPiciNΓ⋮⋮⋱⋮∗∗⋯∑i=1NciN2ΓTPiΓ,then error system (7) is asymptotically stable, and the errors will eventually converge to zero. The observer gains Ki=Pi−1Si.Remark 4.
The existing studies which focused on the state estimation problem based on the partial nodes [25–28] have not addressed the problem of determining the exact number and the locations of these partial nodes, i.e., the exact the output matrices Hi, while in this paper, this problem is studied from the perspective of the network controllability and observability, and this is the main contribution of this work.Proof.
The following Lyapunov function is chosen:(10)Vk=∑i=1Nei,kTPiei,k.
Deriving the difference ofVk, the following is obtained:(11)ΔVk=Vk+1−Vk=∑i=1Nei,k+1TPiei,k+1−ei,kTPiei,k=∑i=1NAei,k+d∑j=1NcijΓej,k+ϕi,kKiHiei,kTPiAei,k+d∑j=1NcijΓej,k+ϕi,kKiHiei,k−ei,kTPiei,k=∑i=1Nei,kTATPiAei,k+∑i=1Nei,kTATPid∑j=1NcijΓej,k+∑i=1Nei,kTATPiϕi,kKiHiei,k+∑i=1Nd∑j=1NcijΓej,kTPiAei,k+∑i=1Nd∑j=1NcijΓej,kTPid∑j=1NcijΓej,k+∑i=1Nd∑j=1NcijΓej,kTPiϕi,kKiHiei,k+∑i=1Nei,kTϕi,kHiTKiTPiAei,k+∑i=1Nei,kTϕi,kHiTKiTPid∑j=1NcijΓej,k+∑i=1Nei,kTϕi,kHiTKiTPiϕi,kKiHiei,k−∑i=1Nei,kTPiei,k.
LetΛ=diagH1TS1TP1−1S1H1,⋯,HNTSNTPN−1SNHNek=e1,kT⋯eN,kTT, and taking the mathematical expectation of ΔVk, we could obtain the following:(12)EΔVk=ekTA¯TΠA¯ek+ekTdA¯TΠQek+ekTΦ2A¯TGTek+ekTdQTΠA¯ek+ekTd2Θek+ekTΦ2dQTGTek+ekTΦ2GA¯ek+ekTΦ2dGQek+ekTΦ2Λek−ekTΠek=ekTΦ2Λ+A¯TΠA¯+Φ2GA¯+Φ2A¯TGT+dA¯TΠQ+Φ2dGQ+dQTΠA¯+Φ2dQTGT+d2Θ−Πek=ekTΞek.
Then, applying the Schur complement lemma, inequality (8) can be obtained from Ξ<0.
If inequality (8) holds, then according to the Lyapunov stability theory and stochastic analysis method, it is known that error system (7) is asymptotically stable and the error will eventually converge to zero. Then, the corresponding observer gains could be obtained by Ki=Pi−1Si. The proof is completed.


## 4. Simulations

In this section, the results proposed previously are verified by a numerical example for both cases of synchronous and independent data loss on multichannels.Remark 5.
The synchronous data loss on multichannels refers that the data on each transmission channel from the complex network to its observerare lost or not synchronously. However, the independent data loss on multichannels means that the data on each transmission channel are lost independently, which is a more general case.
Consider a complex network of 12 nodes where the network topology is as shown in Figure3(a) and the node structure is identical to the one in Figure 1(b), where d = 0.01 and A=0.5−0.400000−0.30.
Applying the maximum matching principle to the network topology, the unmatched nodes arex1, x9, x10, and x12. We apply Algorithm 1 to these unmatched nodes, and it is obtained that the measured states are xi1 and xi3 as shown in Figure 3(b), so the output matrices are as follows:(13)Hi=101,i∈1,9,10,12,=O,i∈2,3,4,5,6,7,8,11.Figure 3
The network topology and the measured states in the simulation. (a) There exist 12 nodes. (b)xi1 and xi3, i∈1,9,10,12, are measured.
(a)(b)Case 3.
Synchronous data loss on multichannels.
The data loss rate of each channel is set asϕi˜=0.15i=1,9,10,12, and according to the Theorem 1, the following observer gains are obtained:(14)K1=−0.0692−0.0012−0.0178,K9=−0.0651−0.0022−0.0172,K10=−0.0651−0.0022−0.0172,K12=−0.0651−0.0022−0.0172.
The estimation errorseip,ki=1,…,12;p=1,2,3 are shown in Figures 4(a)–4(c), all of which converge to zero, implying the state estimation is successful. The data loss process is shown in Figure 4(d), indicating the data loss is synchronous.Figure 4
The estimation errors and the data loss process in Case3. (a) ei1,ki=1,…,12. (b) ei2,ki=1,…,12. (c) ei3,ki=1,…,12. (d) The data loss process.
(a)(b)(c)(d)Case 4.
Independent data loss on multichannels.
In this case, the data loss rate of each channel is set asϕi˜=0.12+0.005ii=1,9,10,12, and according to Theorem 1, the following observer gains are obtained:(15)K1=−0.0686−0.0012−0.0177,K9=−0.0654−0.0022−0.0173,K10=−0.0655−0.0022−0.0173,K12=−0.0657−0.0022−0.0174.
Figure5(a)–5(c) show the estimation errors, all of which converge to zero, implying the network is successfully observed. The data loss process is shown in Figure 5(d), indicating the data loss is independent.
From the simulations given above, the state estimation scheme proposed in this work is demonstrated to be effective to observe the complex network with partial measurement.Figure 5
The estimation errors and the data loss process in Case4. (a) ei1,ki=1,…,12. (b) ei2,ki=1,…,12. (c) ei3,ki=1,…,12. (d) The data loss process.
(a)(b)(c)(d)


## 5. Conclusions

In this work, considering that the external transmission channels between the complex network and the observer show random data loss, based on the idea of structural observability, the state estimation problem has been studied on the premise that only the output data of partial nodes is measured. According to whether the network structure exhibits the pm-rSCCs, the set of the measured nodes and the output matrices have been obtained by Algorithm 1 proposed. Then, a sufficient condition has been derived to realize the state estimation and the observer gains have been determined. From the simulation results of synchronous and independent data loss on multichannels, the proposed state estimation scheme has been verified to be effective.Here, the connections between the nodes are bidirectional, that is, the coupling matrix is symmetric; therefore, the case of general coupling modes will be studied in the future. Simultaneously, the impact on estimation performance from the minimum measured state set is a very interesting problem which deserves further investigation. The approach addressed here could potentially be utilized to solve other engineering issues [40, 41], which is also worthy of further study.



---

*Source: 8311014-2022-12-19.xml*