# Distributed Estimation in Periodically Switching Sensor Networks

Authors: Jie Niu; Ya Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper studies the distributed estimation problem of sensor networks, in which each node is periodically sensing and broadcasting in order. A consensus estimation algorithm is applied, and a weight design approach is proposed. The weights are designed based on an adjusting parameter and the nodes’ lengths of their shortest paths to the target node. By introducing a(T+2)-partite graph of the time-varying networks over a time period [0,T] and studying the relationships between the product of the time-sequence estimation error system matrices and the sequences of edges in the (T+2)-partite graph, a sufficient condition in terms of the observer gain and the adjusting parameter for the stability of the estimation error system is proposed. A simulation example is given to illustrate the results.


---

## Body

## 1. Introduction

Distributed estimation is an important problem in applications of sensor networks such as health monitoring of bridges, collaborative tracking and positioning, and intelligent transportation. In many cases, although partial sensors may be unable to get the measurement of the target, cooperation between neighboring sensors in a network makes it possible that all sensors can participate in a distributed estimation process and reach an estimation of the target’s varying state.Consensus, which means the states of all agents achieve agreement, is a simple and feasible protocol for cooperation of sensors [1–3]. Consensus protocol has been commonly applied in developing distributed estimation algorithms. For first-order data processing, consensus algorithm was applied in [4, 5], and topology and weight design were discussed to optimize the estimators. For general dynamical systems, distributed estimation algorithms are composed of both consensus protocols and observers. There have been many works addressing this consensus estimation problem. The literature includes consensus Kalman filtering [6–9], Luenberger-like consensus estimation [10–16], and consensus H∞ estimation [17, 18]. The stability conditions given in the above works are mainly based on multiple linear matrix inequalities (LMIs). Matei and Baras [14] combined Luenberger-like observers with consensus protocol to present distributed estimation techniques for linear time-invariant systems. They showed that the weights in consensus algorithms were important for distributed detectability of networks. However, by the existing literature, it is not clear how to derive useful guidelines for weight design from LMIs-based conditions.The weights play an essential role in the cooperation. In recent years, the works concerning designing the weights for the network are limited. Xiao et al. [5] proposed an optimal weight design for first-order data processing. Jafarizadeh [19] designed weights to optimize the second largest eigenvalue modulus of the weighted stochastic matrix. Park et al. [20] designed two weighted consensus schemes based on the edge betweenness centrality and the eigenvector centrality of the topology. Wei et al. [21] allocated the weights to minimize the H∞ norm of the network by solving a semidefinite program problem. To the best of our knowledge there is no work providing an explicit weight design approach for consensus of time-varying networks.This paper will design a distributed estimator for sensors over periodically sensing and broadcasting networks and propose a weight design approach in the consensus protocol. Firstly, a consensus based estimation algorithm, where the weights are designed based on the length of the shortest path from each sensor to the target and an adjusting parameter, is proposed. Secondly, by introducing the (T+2)-partite graph of the time-varying network over a time period [0,T] to depict the sequences of edges in time-sequence graphs as paths, and by developing the relationships between the product of time-sequence network stochastic matrices and the paths, a lower bound of certain value in the multiplications of the stochastic matrices in one switching period is provided. And then, based on the properties of the stochastic matrices in one switching period, a sufficient condition of the parameter and estimator gain for the stability of the networked estimation error system is further given. The main contributions of this paper lie in that we provide an explicit condition on the weight’s parameter and estimation gain for periodically switching networks, and the condition requires limited topology information.Notation. In this paper, Ip denotes a unit matrix of size p, and 0 denotes a zero matrix with proper dimension. Re(·) and · denote the real part and modulus of one value, respectively. For a finite set V, |V| denotes the number of nodes in this set. ρ(·) represents the spectral radius of a matrix. The norm AP2 is defined as maxx≠0⁡xTATPAx/xTPx. diag{G1,…,Gn} denotes a block diagonal matrix with diagonal blocks G1,…,Gn. ⊗ denotes the Kronecker product of matrices. [A]ij denotes the element in the ith row and jth column of matrix A.


## 2. Problem Formulation

Consider a target with linear discrete-time dynamical system(1)x0k+1=Ax0k,where x0∈Rp denotes the state of the target. A∈Rp×p is the system matrix and not necessarily Schur stable.The target (1) is monitored by a network of n homogeneous sensors. Not all of the sensors could successfully measure the target simultaneously. If sensor i has access to the target at time k, it measures the target with measuring equation(2)yik=Cx0k,where yi∈Rq is the measurement vector at sensor i, 1≤i≤n; C∈Rq×p is the measurement matrix, and (A,C) is assumed to be completely observable.The sensors in the network detect the target and communicate with each other. The communication topology of the sensors at timek is denoted by G(k)=(V,E(k),A(k)), where V={1,…,n} denotes the node set, E(k)={(i,j),1≤i,j≤n} denotes the edge set at time k, and A(k)=[aij(k)]n×n denotes the adjacency matrix at time k. The adjacency elements associated with the edges of the graph are defined as (i,j)∈E(k)⇔aij(k)=1. Since each node can always get its own information, for all i,   aii(k)≡1. Neighbor set of sensor i is denoted as Ni(k)={j:aij(k)=1}. The sensing vector of the sensors is denoted by B(k)={b1(k),…,bn(k)}, where if sensor i gets the measurement at time k, then bi(k)=1; otherwise bi(k)=0.In practical applications, to save sensors’ power and avoid congestions of communication networks, the sensors work intermittently and asynchronously. In this paper, we consider a periodically switching network satisfying the following assumptions.Assumption 1.
The available communication topology of the sensors is directed and prior given asG^=(V,E^,A^), A^=[a^ij]n×n. Due to limited sensing range, some sensors cannot obtain the target’s measurements and the available sensing vector of the sensors is prior given as B^={b^1,…,b^n}. Each sensor is periodically activated in order; i.e., if node i is activated at time k, then it will be activated again at time k+n. At each time instant, just one node is activated and other nodes just receive information from their neighbors. If node i is activated at time k, it measures the target and broadcasts its information to its neighbors, and correspondingly bi(k)=b^i and bj(k)=0 (j≠i); for all j∈{1,…,n}, s≠i,j, there hold aji(k)=a^ji, ajs(k)=0, and ass(k)=1.By treating the target as one node, define a new topologyG¯=(V¯,E¯,A¯) being composed of all sensors and the target node for the given available communication topology and sensing vector. Without loss of generality, let n+1 be the number of the target node, and then the node set is V¯={1,2,…,n,n+1}, the adjacency matrix A¯=[a¯ij](n+1)×(n+1) satisfying, for i,j∈{1,2,…,n}, a¯ij=a^ij, a¯i(n+1)=b^i, and a¯(n+1)i=0. Node i’s neighbor set in G¯ is denoted as N¯i.InG¯, a simple path of length l from i to j is a sequence of nodes i1,i2,…,il with il=j and each subsequent edge (i,i1),(i1,i2),…,(il-1,il)∈E¯. If there exists a path in G¯ from node i to another node j, then j is said to be reachable from i. If a node j is reachable from every other node in V¯, then it is globally reachable.Assumption 2.
For the given available communication topologyG^ and sensing vector B^, the target node n+1 in topology G¯ is globally reachable. Each node knows the length of its shortest path to node n+1 in topology G¯.From Assumption2, denote li(1≤i≤n) as node i’s length of its shortest path from it to n+1 in topology G¯, 1≤li≤m≤n, m=maxi{li}. Define Vs={i∈V∣li=s} as the set of nodes whose shortest path length to node n+1 is s, 1≤li≤m. Then, for s≠j, Vs∩Vj=⌀, and V=∪s=1mVs. Obviously, for each node in Vs,s≥1, it has at least one neighbor in Vs-1 and no neighbors in Vs-j,j≥2.Assumption 3.
During any one period[tn,(t+1)n)(t≥0), all nodes in Vs+1 are activated after the nodes in Vs, 1≤s≤m-1.This paper focuses on designing a distributed estimator for the time-varying network satisfying Assumptions1–3 such that each sensor can asymptotically estimate the state of the target.


## 3. Main Results

In this section, we firstly propose a consensus based estimation algorithm. Then, we analyse the property of the stochastic matrices over the periodically switching network. Finally, we investigate the stability conditions of the estimation error system.


### 3.1. A Consensus Based Estimation Algorithm

In this paper we apply a distributed estimation algorithm based on the consensus strategy.From Assumptions1–3, when sensor j∈{1,…,n} is activated to measure the target and broadcast its information to its neighbor sensors at time k, it computes its estimation by using its own available measurement information:(3)xjk+1=Axjk+b^jFyjk-Cxjk,and for other sensor i, it computes its estimation using the network information based on the weighted average consensus protocol:(4)xik+1=a^ijwijAxjk+b^jFyjk-Cxjk+1-a^ijwijAxik,where xi∈Rp denotes the estimation state made by sensor i, and F∈Rp×q is the estimation gain to be designed.From (4), if sensor i is not sensor j’s out-neighbor, i.e., a^ij=0, it updates its estimation based on its own information(5)xik+1=Axik.It is well known that the weights of the network play an essential role in the stability of the estimation errors [10–18]. In the following, we will propose a weight design approach based on the nodes’ lengths of their shortest paths to node n+1 in G¯, i.e., li,1≤i≤n, and an adjusting parameter μ. If sensor j∈{1,…,n} is activated at time k, for i≠j satisfying a^ij=1,(6)wijk=μlj-lijμli-lij+μlj-lij,(7)wiik=μli-lijμli-lij+μlj-lij.where μ≥0 is an adjusting parameter to be designed, lij=min⁡{li,lj}. If μ=0, μ0=1, and μl=0,l>0. Since for i∈Vs,s≥1, node i has no neighbors in Vs-2; thus lj-li+1≥0 for all j∈N¯i.Fori≠j satisfying a^ij=0,(8)wijk=0,(9)wiik=1.Defineei(k)=xi(k)-x0(k) as the estimation error of sensor i, 1≤i≤n. Then if sensor j∈{1,…,n} is activated at time k,(10)ejk+1=A-b^jFCejk.For other sensors, the estimation errors are given by(11)eik+1=a^ijwijkA-b^jFCejk+1-a^ijwijkAeik,Here we usebi(k) and aij(k)wij(k) to uniformly depict the time-varying sensing topology and communication topology, respectively. They are defined as follows: if sensor j∈{1,…,n} is activated at time k, then (1) bj(k)=b^j and bi(k)=0 (i≠j); (2) ajj(k)wjj(k)=1, ajs(k)wjs(k)=0 (s≠j); (3) for i≠j, aij(k)wij(k)=a^ijwij(k), aii(k)wii(k)=1-a^ijwij(k), and for s≠j,i, ais(k)wis(k)=0. Then, the estimation error system (11) of each sensor i can be formulated as a uniform equation(12)eik+1=∑j=1naijkwijkA-bjkFCejk.Lete(k)=[e1T(k),…,enT(k)]T. Then, from (12), the estimation error system is(13)ek+1=Ξkek,where Ξ(k)=(W(k)⊗Ip)diag{A-bi(k)FC,1≤i≤n}, W(k)=[aij(k)wij(k)]n×n.If the periodically switching system (13) is asymptotically stable, the estimation errors of sensors converge to zero. In the following, we discuss under what conditions system (13) in periodically switching networks satisfying Assumptions 1–3 is asymptotically stable.


### 3.2. Stochastic Matrices for Periodically Switching Networks

To analyse the stability of the estimation error system, in this subsection, we will investigate the properties of the stochastic matrices over the periodically switching networks satisfying Assumptions1–3 and give important lemmas.To begin with, we introduce some important notions.Definition 4.
( V + ∪ V - , E + ) is said to be abipartite graph[22] of a given n-vertex topology (V,E,A), if V+={1+,…,n+} and V-={1-,…,n-} are two disjoint vertex sets, and E+={(i-,j+):(i,j)∈E} is an arc set.Definition 5.
( ⋃ k = 0 T + 1 V k , ⋃ k = 0 T E k ) is said to be (T+2)-partite graph for a time-varying topology G(k)=(V,E(k),W(k)) over a time period [0,T] with T≥0, if Vk(0≤k≤T+1) are T+2 disjoint vertex sets and Ek(0≤k≤T) are T+1 arc sets. For 0≤k≤T+1, the vertex set Vk with n vertex nodes is denoted by {v1k,…,vnk}. For 0≤k≤T, the arc set Ek is defined as Ek={(vi(k+1),vjk)∣1≤i,j≤n,(i,j)∈E(k)}. And for each edge (vi(k+1),vjk)∈Ek, its weight w¯vi(k+1)vjk=wij(k).Obviously, by the above definition, there are(T+2)n nodes in the (T+2)-partite graph. When T=0, the (T+2)-partite graph is equivalent to the bipartite graph of topology G(0); each pair (Vk⋃Vk+1,Ek) can be seen as the bipartite graph of topology G(k).Example 6.
Consider a network with 4 nodes. The available communication topology is prior given by Figure1 and its bipartite graph is given in Figure 2.Figure 1
Given communication topology.Figure 2
Bipartite graph of topology in Figure1.If the topology is varying andE(0)={(2,1),(3,2),(4,3)}, E(1)={(3,1),(4,2),(2,4)}. The 3-partite graph over a time period [0,1] is given in Figure 3.Figure 3
3-Partite graph.For analysis simplicity, renumber the nodes such that for all nodes inVs+1 their numbers are larger than those in Vs, 1≤s≤m-1. By Assumptions 1–3, without loss of generality we can assume that node j(1≤j≤n) is activated in order at times kn+j-1, k≥0. Here we introduce the (n+1)-partite graph of the time-varying networks. The (n+1)-partite graph of the time-varying networks during time 0 to time n-1 is 0≤t≤n-1, when μ=0, Et={(vj(t+1),v(t+1)t)∣(j,t+1)∈E^,lj≥lt+1}∪{(vj(t+1),vjt)∣(j,t+1)⊈E^,j∈V}, and when μ>0, Et={(vj(t+1),v(t+1)t)∣(j,t+1)∈E^,j∈V}∪{(vj(t+1),vjt)∣j∈V}, where E^ is the edge set of the prior given communication topology.Lemma 7.
W ( k ) is a periodically switching stochastic matrix with period n, and for k≥0,1≤j≤n, W(kn+j-1)=Wj, where (1) [Wj]jj=1 and [Wj]js=0, s≠j; (2) for i≠j, [Wj]ij=a^ij(μlj-lij/(μli-lij+μlj-lij)), [Wj]ii=1-[Wj]ij, and [Wj]is=0, s≠j,i.Proof.
Firstly, from the above definition ofaij(k)wij(k), we have that ∑j=1naij(k)wij(k)=1, which means that W(k) is a stochastic matrix.
Since nodej(1≤j≤n) is activated in order at times kn+j-1, k≥0, then the stochastic matrix in system (13) satisfies (1) [W(kn+j-1)]jj=1 and [W(kn+j-1)]js=0, s≠j; (2) for i≠j, [W(kn+j-1)]ij=a^ij(μlj-lij/(μli-lij+μlj-lij)), [W(kn+j-1)]ii=1-[W(kn+j-1)]ij, and [W(kn+j-1)]is=0, s≠j,i. Denote Wj as the weight matrix of the network when node j is activated; then W(kn+j-1)=Wj and it is stochastic. This completes the proof of this lemma.To investigate the properties of the stochastic matrixW(k) in system (13), we introduce following system:(14)θk+1n=W¯θkn,where W¯=[W¯ij]n×n=WnWn-1⋯W1,In the following, we discuss the property of the stochastic matrixW¯. To begin with, we give two important lemmas regarding the property of the network.Lemma 8.
Consider periodically switching networks satisfying Assumptions1–3. In the (n+1)-partite graph of the time-varying networks among one period n, i.e., (⋃t=0nVt,⋃i=0n-1Et), for any node vin, 1≤i≤n, there exists at least one sequence of edges (vinn,vin-1(n-1)), vin-1n-1,vin-2n-2,…,(vi11,vi00) satisfying the following three conditions: (1) vinn=vin; (2) (viss,vis-1(s-1))∈Es-1, 1≤s≤n; (3) in node set {viss,1≤s≤n}, there exists at least one node vis0s0, is0∈V1 and is0=s0+1.Proof.
Denotek1=|V1|, k2=k1+|V2|, ks+1=ks+|Vs+1|, 1≤s≤m-1; then km=n. From Assumption 3, in time interval [kn,kn+k1) just the nodes in V1 are activated in order, and in any time interval [kn+ks,kn+ks+1), just the nodes in Vs+1 are activated in order, k≥0.
Fori∈V1, from the weight design approach we have that, for all μ and for 1≤s≤n, (vis,vi(s-1))∈Es-1, and then there exists a sequence satisfying the conditions in Lemma 8 as long as vis-1(s-1)=vi(s-1) for all s.
Fori∈Vl,2≤l≤m, in G there exists a path of length l-1 from i to one node i¯1∈V1. Here we denote the path as (i,i¯l-1),(i¯l-1,i¯l-2),…,(i¯2,i¯1), i¯s∈Vs,1≤s≤l-1. From the weight design approach we have that, for all μ, (i,i)∈E(t) for t∈[kl,n). Thus in the (n+1)-partite graph (⋃t=0nVt,⋃t=0n-1Et), for kl≤t<n, (vi(t+1),vit)∈Et. In time interval [kl-1,kl), denote ti¯l-1=i¯l-1-1 as the time when i¯l-1∈Vl-1∩Ni is activated, and there is no else node in Vl-1∩Ni being activated in (ti¯l-1,kl). Then for t=ti¯l-1, (i,i¯l-1)∈E(ti¯l-1); for ti¯l-1<t<kl, (i,i)∈E(t); and for kl-1≤t<ti¯l-1, (i¯l-1,i¯l-1)∈E(t). Thus in (⋃t=0nVt,⋃t=0n-1Et), for ti¯l-1<t<kl, (vi(t+1),vit)∈Et; (vi(ti¯l-1+1),vi¯l-1ti¯l-1)∈Eti¯l-1; and for kl-1≤t<ti¯l-1, (vi¯l-1(t+1),vi¯l-1t)∈Et. In the same way, in time interval [0,k1), denote ti¯0=i¯0-1 as the time when i¯0∈V1∩Ni¯1 is activated, and there is no else node in V1∩Ni¯1 being activated in (ti¯0,k1). Then (i¯1,i¯0)∈E(ti¯0); for ti¯0<t<k1, (i¯1,i¯1)∈E(t); and for 0≤t<ti¯0, (i¯0,i¯0)∈E(t). Thus in (⋃t=0nVt,⋃t=0n-1Et), for i¯0-1<t<k1, (vi¯1(t+1),vi¯1t)∈Et; (vi¯1i¯0,vi¯0(i¯0-1))∈Ei¯0-1; and for 0≤t<i¯0-1, (vi¯0(t+1),vi¯0t)∈Et.
Therefore, in the (n+1)-partite graph (⋃t=0nVt,⋃t=0n-1Et), there exists a sequence of edges ⋃t=n-1i¯l-1(vi(t+1),vit), vii¯l-1,vi¯l-1i¯l-1-1,…,(vi¯1i¯0,vi¯0(i¯0-1)), ⋃t=i¯0-20(vi¯0(t+1),vi¯0t), where i¯0∈V1. This lemma has been proved.Remark 9.
Lemma8 implies that, in the network satisfying Assumptions 1–3, during each switching period [tn,(t+1)n)(t≥0), any sensor node can receive the information of some node in V1.Remark 10.
In this paper, we apply Assumption3 to make sure that Lemma 8 holds. If the sensors’ activated order does not satisfy Assumption 3, the conditions in Lemma 8 cannot be guaranteed. For example, if the communication graph is a path, the edge set is denoted by {(4,3),(3,2),(2,1)}, and the activated order is 4,3,2,1, then, in the 5-partite graph of the time-varying topology over any period [4t+s,4(t+1)+s) (0≤s≤3, t≥0), node 1 is not reachable; i.e., the conditions in Lemma 8 cannot be satisfied.In the following, we use a simple example to illustrate the result in Lemma8.Example 11.
Consider a network with 4 nodes. Just node 1 can get the information of the leader, i.e.,b^1=1 and b^i=0,i>1. The available communication topology is prior given by Figure 1 and, for all i, (i,i)∈E. The network is periodically switching and satisfies Assumptions 1–3. We know that V1={1},V2={2,3}, and V3={4}. The order of working sensor in one period is 1,2,3,4.Whenμ in weights is 0, the 5-partite graphs of the network in one period are, respectively, given in Figure 4. Here the solid black nodes denote the activated nodes in the time instants. For the case μ=0, there are 2 sequences of edges from v44 to v10, and from v34 to v10, and there is one sequence of edges from v24 to v10, and from v14 to v10. In these sequences, there exist edges containing working node v10, 1∈V0. For the case μ>0, there is one sequence of edges from v14 to v10, there are 2 sequences of edges from v34 to v10, 3 sequences of edges from v44 to v10, and 4 sequences of edges from v24 to v10. In these sequences, there exist edges containing working node v10, 1∈V0.Figure 4
Time-sequence bipartite graphs of the network in one period.Lemma 12.
Consider a periodically switching network satisfying Assumptions1–3 with weights given by (6)-(8). For i,1≤i≤n, denote Pi as the set of sequences of edges (vinn,vin-1(n-1)), (vin-1(n-1),vin-2(n-2)),…,(vi11,vi00) satisfying the conditions in Lemma 8. Then the weights w¯vissvis-1(s-1) of the edges (viss,vis-1(s-1)), s=1,2,…,n, in (n+1)-partite graph satisfy the following inequality:(15)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1≥11+μli+ri-1,where ri=|Ni⋂{Vli,…,Vm}|.Proof.
For notation simplicity, we letk1=|V1|, k2=k1+|V2|, ks+1=ks+|Vs+1|, 1≤s≤m-1.
Firstly we discuss the case whenμ=0. Under the weight design approach, for any edge (viss,vis-1(s-1))∈Es-1 in a sequence in Pi, there has lis≥lis-1. If lis>lis-1, then w¯vissvis-1(s-1)=1, and if lis=lis-1, then w¯vissvis-1(s-1) equals 1 or 1/2. For i∈Vl, when kl<s≤n, wii(s-1)≡1, and then is-1=i, w¯vissvis-1(s-1)=w¯visvi(s-1)=1. If, in the time-varying network (V,E(k),A(k)), node sl∈Vl is activated to transmit its information to node i at sl-1(kl-1≤sl-1<kl), and there is no else node in Vl∩Ni being activated in time [sl,kl), then wii(s-1)=1 for s∈(sl,kl], and wii(sl-1)=wisl(sl-1)=1/2. Thus in (⋃s=0nVs,⋃s=0n-1Es), for s∈(sl,kl], vis-1(s-1)=vi(s-1) and w¯vissvis-1(s-1)=1. For s=sl, there are two edges in Es-1 satisfying the conditions for Pi. One is with visl-1(sl-1)=vi(sl-1) and w¯vislslvi(sl-1)=1/2. The other is with visl-1(sl-1)=vsl(sl-1) and w¯vislslvsl(sl-1)=1/2. Then, (16)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1=12∑P^i∏s=1sl-1w¯vissvis-1s-1+12∑P^sl∏s=1sl-1w¯vjssvjs-1s-1. where P^i={(vin,vi(n-1)),…,(vi(sl+1),visl),(visl,vi(sl-1)), (vi(sl-1),visl-2(sl-2)),…,(vi11,vi00)}∈Pi, P^sl={(vin,vi(n-1)),…,(vi(sl+1),visl),(visl,vsl(sl-1)), (vsl(sl-1),vjsl-2(sl-2)),…,(vj11,vj00)}∈Pi.
Similarly, we have that(17)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1=1.
Secondly we discuss the case whenμ>0. Under the weight design approach, for any edge (viss,vis-1(s-1))∈Es-1, we have (18)w¯vissvis-1s-1=11+μ,iflis>lis-1;μlis-1μlis+μlis-1≤μ1+μ,iflis<lis-1;12,iflis=lis-1andis≠is-1;1,ifis=is-1=sors∉Nis;12,ifis=is-1≠s,s∈Nis,andlis=ls;μlisμls+μlis≥11+μ,ifis=is-1≠s,s∈Nis,andlis<ls;μlisμls+μlis≤μ1+μ,ifis=is-1≠s,s∈Nis,andlis>ls.
DefineP¯i as the set of sequences in Pi in which each edge (viss,vis-1(s-1)) satisfies lis≥lis-1 and lis≤ls. Then for lis>lis-1, w¯vissvis-1(s-1)=1/(1+μ), and for other cases, w¯vissvis-1(s-1) equals 1/2, 1, or larger than 1/(1+μ).
Fori∈Vl and {(vin,vin-1(n-1)),…,(vi11,vi00)} in P¯i. Consider s, kl<s≤n; then ls>lis and vis-1(s-1) must be vi(s-1), is-1=i. If s∈Nis=Ni, then w¯vissvis-1(s-1)≥1/(1+μ), otherwise w¯vissvis-1(s-1)=1. Thus (19)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=kl+1nw¯vissvis-1s-1≥11+μri,where ri=|Ni⋂{Vl,…,Vm}|.
Considerkl-1<s≤kl. If, in the time-varying network (V,E(k),A(k)), node sl∈Vl/{i} is activated to transmit its information to node i at sl-1(kl-1≤sl-1<kl), and there is no other node in Vl∩Ni being sensing and broadcasting in time [sl,kl), then wii(sl-1)=wisl(sl-1)=1/2, and for t∈[sl,kl), wii(t)=1. Thus for s∈(sl,kl], vis-1(s-1)=vi(s-1), is-1=i, and w¯vissvis-1(s-1)=1. For s=sl, there are two edges in Es-1 satisfying the conditions for P¯i. One is with visl-1(sl-1)=vi(sl-1) and w¯vislslvisl-1(sl-1)=1/2. The other is with visl-1(sl-1)=vsl(sl-1) and w¯vislslvisl-1(sl-1)=1/2. For edges {(viss,vis-1(s-1)),kl-1≤s<sl} with visl-1(sl-1)=vi(sl-1) in sequences in P¯i, w¯vissvis-1(s-1) equals 1/2 or 1. If for some edge (viss,vis-1(s-1)), w¯vissvis-1(s-1) equals 1/2, then there are also two paths from node vis-1(s-1). Then, ∑E^i∏s=kl-1+1sl-1w¯vissvis-1(s-1)=1, where E^i={(visl,vi(sl-1)), (vi(sl-1),visl-2(sl-2)),…, (vikl-1+1(kl-1+1),vikl-1kl-1)}. Similarly, ∑E^sl∏s=kl-1+1sl-1w¯vjssvjs-1(s-1)=1, where E^sl={(visl,vsl(sl-1)),(vsl(sl-1),vjsl-2(sl-2)),…, (vjkl-1+1(kl-1+1),vjkl-1kl-1)}. Thus, (20)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=kl-1+1nw¯vissvis-1s-1≥11+μri.
Considerkl-2<s≤kl-1. For a path (vinn,vin-1(n-1)),…,(vikl-1+1(kl-1+1),vikl-1kl-1) in one of sequence in P¯i, for node ikl-1∈Vl in the time-varying network (V,E(k),A(k)), if node sl-1∈Vl-1 is activated to transmit its information to node ikl-1 at sl-1-1(kl-2≤sl-1-1<kl-1), and there is no other node in Vl-1∩Nikl-1 being activated in [sl-1,kl-1), then wikl-1,sl-1(sl-1-1)=1/(1+μ), and for t∈[sl-1,kl-1), wikl-1ikl-1(t)=1. Thus for s∈(sl-1,kl-1], vis-1(s-1)=vikl-1(s-1) and w¯vissvis-1(s-1)=1; for s=sl-1, vis-1(s-1)=vsl-1(s-1) and w¯vissvis-1(s-1)=1/(1+μ). For edges (visl-1-1(sl-1-1),visl-1-2(sl-1-2)), …,(vikl-2+1(kl-2+1),vikl-2kl-2), applying the similar analysis for edges {(viss,vis-1(s-1)),kl-1≤s<sl}, we have that (21)∑E^kl-1∏s=kl-2+1kl-1w¯vissvis-1s-1=11+μ, where E^kl-1={(vin,vin-1(n-1)),…, (vikl-1+1(kl-1+1),vikl-1kl-1),…,(vj11,vj00)}∈P¯i
In the same way, for2≤g≤l, k0=0, we have that (22)∑E^kg-1∏s=kg-2+1kg-1w¯vissvis-1s-1=11+μ,where E^kg-1={(vin,vin-1(n-1)),…, (vikg-1+1(kg-1+1),vikg-1kg-1),…,(vj11,vj00)}∈P¯i. Therefore, for i∈Vl, (23)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=1nw¯vissvis-1s-1≥11+μl+ri-1.Since P¯i is a subset of Pi, this lemma has been proved.Back to Example11, we have ∑P1∏s=1nw¯v1ssv1s-1(s-1)=1, ∑P2∏s=1nw¯v2ssv2s-1(s-1)=1/(1+μ)2+(1+μ)/(1+μ)3+μ2/(1+μ)4, ∑P3∏s=1nw¯v3ssv3s-1(s-1)=1/(1+μ), ∑P4∏s=1nw¯v4ssv4s-1(s-1)=1/(1+μ)2+(1-μDD)/(1+μ)3. These values satisfy the condition in Lemma 12.Lemma 13.
Consider a periodically switching network satisfying Assumptions1–3, and the weights are given by (6)-(8). For i,1≤i≤n, there exists a nonempty set Pi consisting of time-sequences of edges {(in,in-1),…,(i1,i0)}, where (is,is-1)∈E(s-1), in=i, and there is at least one edge (is0,is0)∈E(is0-1) and is0∈V1. And moreover,(24)∑in,in-1,…,i1,i0∈Pi∏s=1nwisis-1s-1≥11+μli+ri-1,where ri=|Ni⋂{Vli,…,Vm}|.Proof.
If, in the time-varying networks, during time interval[kn,(k+1)n) there exist g>0 time-sequences of edges (in,in-1), in-1,in-2,…,(i1,i0) with in=i, i0=j, each edge (is,is-1)∈E(kn+s-1) with positive weights, s=1,2,…,n, then W¯ij is nonzero and equals the sum of g elements ∏s=1nwisis-1(s-1).
From the definition of the (n+1)-partite graph of the time-varying networks from time 0 to time n-1, we have that the sequence of edges (in,in-1),…,(i1,i0) with (is,is-1)∈E(s-1) in the time-varying networks is equivalent to the sequence of edges vinn,vin-1n-1,…,(vi11,vi00) with (viss,vis-1(s-1))∈Es-1 in the (n+1)-partite graph (⋃s=0nVs,⋃s=0n-1Es), and wisis-1(s-1)=w¯vissvis-1(s-1). Thus ∏s=1nwisis-1(s-1)=∏s=1nw¯vissvis-1(s-1).
For a network satisfying Assumptions1–3, from Lemma 8 we have that, for all i, in the sequence of edges {(in,in-1),…,(i1,i0)} with (is,is-1)∈E(s-1) and in=i, there exists at least one sequence of edges (is0,is0)∈E(is0-1) and is0∈V1. And by applying Lemma 12, this lemma can be proved.


### 3.3. Stability Condition

In this subsection, we discuss how to selectμ and observer gain such that in periodically working sensor networks the estimation error system (13) can asymptotically converge to zero.From system (13), when j is activated at time k we have(25)ek+1=Ξjek,where Ξj is a matrix in which the ith(i≠j) diagonal block matrices are (1-a^ij(μlj-lij/(μli-lij+μlj-lij)))Aei(k) and the jth diagonal block matrix is (A-b^jFC), the jth column block matrices are a^ij(μlj-lij/(μli-lij+μlj-lij))(A-bjFC), and the other column block matrices are0.It is obvious that in almost all cases system (25) is not stable, which means that each subsystem of the switching system is not asymptotically stable. However, through periodic switching, the whole system can still achieve stability. From Assumptions 1–3, the estimation error system has the following equation:(26)ek+1n=Ξekn,where Ξ=ΞnΞn-1⋯Ξ1.Theorem 14.
For periodically switching networks satisfying Assumptions1–3, and the weights are given by (6)-(8). If there exists a symmetric definite matrix P∈Rp×p and a gain matrix F∈Rp×q such that(27)An-1A-FCAk0-1TPAn-1A-FCAk0-1<P,and(28)μ<AnP-An-1A-FCAk0-1PAnP-11/M-1,then the estimation error of the sensor network asymptotically converges to zero, where k0=|V0|, M=maxi⁡{li+ri-1}, ri=|Ni⋂{Vli,…,Vm}|.Proof.
DenoteΞ=[Ξij]n×n as a block matrix with blocks Ξij∈Rp×p. In the time-varying networks if, during each time interval [kn,(k+1)n), there exist g>0 sequences of edges (in,in-1), (in-1,in-2),…,(i1,i0) with in=i, i0=j, each edge (is,is-1)∈E(kn+s-1) with positive weights, s=1,2,…,n, then Ξij is nonzero and is a sum of g matrices. Each addition part is a multiplication of n matrices and weights and has the form ∏s=1nwisis-1(s-1)Ais-1. Define k0=|V0|. Obviously, for is>k0, Ais-1=A, and for 1≤is≤k0, Ais-1 is either A or A-FC.
For a network satisfying Assumptions1–3, from Lemma 12 we have that, for each i (1≤i≤n), there exists at least one nonzero block matrix Ξii0=∑{(is,is-1)∈E(s-1),1≤s≤n∏s=1nwisis-1(s-1)An-k0Aik0-1⋯Ai0 having at least one addition part with at least one multiplied matrix A-FC and the corresponding weight being larger than 1/(1+μ)li+ri-1. That is to say, there exists at least one matrix ∏s=1nwisis-1(s-1)An-k0Aik0-1⋯Ai0 where there is at least one matrix in Aik0-1,…,Ai0 being equal to A-FC, and ∏s=1nwisis-1(s-1)≤1/(1+μ)li+ri-1. Thus, if there exists a matrix P>0 such that (27) holds, then for the matrix An-k0Aik0-1⋯Ai0 containing multiplied matrix A-FC, An-k0Aik0-1⋯Ai0P≤An-1(A-FC)Ak0-1P<1, where AP2=maxx≠0(xTATPAx/xTPx).
Since(29)∑j=1nΞijP≤∑j=1n∑is,is-1∈Es-1,1≤s≤n,i0=j∏s=1nwisis-1s-1An-k0Aik0-1⋯Ai0P≤11+μMAn-1A-FCAk0-1P+1-11+μMAnP,if the condition (28) holds, then ρ(Ξ)≤maxi⁡{∑j=1nΞijP}<1, and then system (26) is asymptotically stable. This theorem has been proved.Remark 15.
IfA is nonsingular, the LMI (27) can be converted to the following LMI: (30)PPAn+k0-1-YCAk0-1TPAn+k0-1-YCAk0-1P>0,where the gain F can be obtained by F=(A-1)n-1P-1Y. Since (A,C) is observable, the LMI must be feasible and thus μ can be computed from inequality (28). If the prior given extended topology G¯ is a tree, then M=m, there is only one sequence in Pi, and ∑{(vin,vin-1(n-1)),…,(vi11,vi00)}∈Pi∏s=1nw¯vissvis-1(s-1)=1/(1+μ)li. Ξ is a lower triangular block matrix with diagonal blocks An-1(A-FC) and (μ/1+μ)An. Thus the estimation error system is asymptotically stable if and only if ρAn-1A-FC<1 and μ<1/(ρn(A)-1).


## 3.1. A Consensus Based Estimation Algorithm

In this paper we apply a distributed estimation algorithm based on the consensus strategy.From Assumptions1–3, when sensor j∈{1,…,n} is activated to measure the target and broadcast its information to its neighbor sensors at time k, it computes its estimation by using its own available measurement information:(3)xjk+1=Axjk+b^jFyjk-Cxjk,and for other sensor i, it computes its estimation using the network information based on the weighted average consensus protocol:(4)xik+1=a^ijwijAxjk+b^jFyjk-Cxjk+1-a^ijwijAxik,where xi∈Rp denotes the estimation state made by sensor i, and F∈Rp×q is the estimation gain to be designed.From (4), if sensor i is not sensor j’s out-neighbor, i.e., a^ij=0, it updates its estimation based on its own information(5)xik+1=Axik.It is well known that the weights of the network play an essential role in the stability of the estimation errors [10–18]. In the following, we will propose a weight design approach based on the nodes’ lengths of their shortest paths to node n+1 in G¯, i.e., li,1≤i≤n, and an adjusting parameter μ. If sensor j∈{1,…,n} is activated at time k, for i≠j satisfying a^ij=1,(6)wijk=μlj-lijμli-lij+μlj-lij,(7)wiik=μli-lijμli-lij+μlj-lij.where μ≥0 is an adjusting parameter to be designed, lij=min⁡{li,lj}. If μ=0, μ0=1, and μl=0,l>0. Since for i∈Vs,s≥1, node i has no neighbors in Vs-2; thus lj-li+1≥0 for all j∈N¯i.Fori≠j satisfying a^ij=0,(8)wijk=0,(9)wiik=1.Defineei(k)=xi(k)-x0(k) as the estimation error of sensor i, 1≤i≤n. Then if sensor j∈{1,…,n} is activated at time k,(10)ejk+1=A-b^jFCejk.For other sensors, the estimation errors are given by(11)eik+1=a^ijwijkA-b^jFCejk+1-a^ijwijkAeik,Here we usebi(k) and aij(k)wij(k) to uniformly depict the time-varying sensing topology and communication topology, respectively. They are defined as follows: if sensor j∈{1,…,n} is activated at time k, then (1) bj(k)=b^j and bi(k)=0 (i≠j); (2) ajj(k)wjj(k)=1, ajs(k)wjs(k)=0 (s≠j); (3) for i≠j, aij(k)wij(k)=a^ijwij(k), aii(k)wii(k)=1-a^ijwij(k), and for s≠j,i, ais(k)wis(k)=0. Then, the estimation error system (11) of each sensor i can be formulated as a uniform equation(12)eik+1=∑j=1naijkwijkA-bjkFCejk.Lete(k)=[e1T(k),…,enT(k)]T. Then, from (12), the estimation error system is(13)ek+1=Ξkek,where Ξ(k)=(W(k)⊗Ip)diag{A-bi(k)FC,1≤i≤n}, W(k)=[aij(k)wij(k)]n×n.If the periodically switching system (13) is asymptotically stable, the estimation errors of sensors converge to zero. In the following, we discuss under what conditions system (13) in periodically switching networks satisfying Assumptions 1–3 is asymptotically stable.


## 3.2. Stochastic Matrices for Periodically Switching Networks

To analyse the stability of the estimation error system, in this subsection, we will investigate the properties of the stochastic matrices over the periodically switching networks satisfying Assumptions1–3 and give important lemmas.To begin with, we introduce some important notions.Definition 4.
( V + ∪ V - , E + ) is said to be abipartite graph[22] of a given n-vertex topology (V,E,A), if V+={1+,…,n+} and V-={1-,…,n-} are two disjoint vertex sets, and E+={(i-,j+):(i,j)∈E} is an arc set.Definition 5.
( ⋃ k = 0 T + 1 V k , ⋃ k = 0 T E k ) is said to be (T+2)-partite graph for a time-varying topology G(k)=(V,E(k),W(k)) over a time period [0,T] with T≥0, if Vk(0≤k≤T+1) are T+2 disjoint vertex sets and Ek(0≤k≤T) are T+1 arc sets. For 0≤k≤T+1, the vertex set Vk with n vertex nodes is denoted by {v1k,…,vnk}. For 0≤k≤T, the arc set Ek is defined as Ek={(vi(k+1),vjk)∣1≤i,j≤n,(i,j)∈E(k)}. And for each edge (vi(k+1),vjk)∈Ek, its weight w¯vi(k+1)vjk=wij(k).Obviously, by the above definition, there are(T+2)n nodes in the (T+2)-partite graph. When T=0, the (T+2)-partite graph is equivalent to the bipartite graph of topology G(0); each pair (Vk⋃Vk+1,Ek) can be seen as the bipartite graph of topology G(k).Example 6.
Consider a network with 4 nodes. The available communication topology is prior given by Figure1 and its bipartite graph is given in Figure 2.Figure 1
Given communication topology.Figure 2
Bipartite graph of topology in Figure1.If the topology is varying andE(0)={(2,1),(3,2),(4,3)}, E(1)={(3,1),(4,2),(2,4)}. The 3-partite graph over a time period [0,1] is given in Figure 3.Figure 3
3-Partite graph.For analysis simplicity, renumber the nodes such that for all nodes inVs+1 their numbers are larger than those in Vs, 1≤s≤m-1. By Assumptions 1–3, without loss of generality we can assume that node j(1≤j≤n) is activated in order at times kn+j-1, k≥0. Here we introduce the (n+1)-partite graph of the time-varying networks. The (n+1)-partite graph of the time-varying networks during time 0 to time n-1 is 0≤t≤n-1, when μ=0, Et={(vj(t+1),v(t+1)t)∣(j,t+1)∈E^,lj≥lt+1}∪{(vj(t+1),vjt)∣(j,t+1)⊈E^,j∈V}, and when μ>0, Et={(vj(t+1),v(t+1)t)∣(j,t+1)∈E^,j∈V}∪{(vj(t+1),vjt)∣j∈V}, where E^ is the edge set of the prior given communication topology.Lemma 7.
W ( k ) is a periodically switching stochastic matrix with period n, and for k≥0,1≤j≤n, W(kn+j-1)=Wj, where (1) [Wj]jj=1 and [Wj]js=0, s≠j; (2) for i≠j, [Wj]ij=a^ij(μlj-lij/(μli-lij+μlj-lij)), [Wj]ii=1-[Wj]ij, and [Wj]is=0, s≠j,i.Proof.
Firstly, from the above definition ofaij(k)wij(k), we have that ∑j=1naij(k)wij(k)=1, which means that W(k) is a stochastic matrix.
Since nodej(1≤j≤n) is activated in order at times kn+j-1, k≥0, then the stochastic matrix in system (13) satisfies (1) [W(kn+j-1)]jj=1 and [W(kn+j-1)]js=0, s≠j; (2) for i≠j, [W(kn+j-1)]ij=a^ij(μlj-lij/(μli-lij+μlj-lij)), [W(kn+j-1)]ii=1-[W(kn+j-1)]ij, and [W(kn+j-1)]is=0, s≠j,i. Denote Wj as the weight matrix of the network when node j is activated; then W(kn+j-1)=Wj and it is stochastic. This completes the proof of this lemma.To investigate the properties of the stochastic matrixW(k) in system (13), we introduce following system:(14)θk+1n=W¯θkn,where W¯=[W¯ij]n×n=WnWn-1⋯W1,In the following, we discuss the property of the stochastic matrixW¯. To begin with, we give two important lemmas regarding the property of the network.Lemma 8.
Consider periodically switching networks satisfying Assumptions1–3. In the (n+1)-partite graph of the time-varying networks among one period n, i.e., (⋃t=0nVt,⋃i=0n-1Et), for any node vin, 1≤i≤n, there exists at least one sequence of edges (vinn,vin-1(n-1)), vin-1n-1,vin-2n-2,…,(vi11,vi00) satisfying the following three conditions: (1) vinn=vin; (2) (viss,vis-1(s-1))∈Es-1, 1≤s≤n; (3) in node set {viss,1≤s≤n}, there exists at least one node vis0s0, is0∈V1 and is0=s0+1.Proof.
Denotek1=|V1|, k2=k1+|V2|, ks+1=ks+|Vs+1|, 1≤s≤m-1; then km=n. From Assumption 3, in time interval [kn,kn+k1) just the nodes in V1 are activated in order, and in any time interval [kn+ks,kn+ks+1), just the nodes in Vs+1 are activated in order, k≥0.
Fori∈V1, from the weight design approach we have that, for all μ and for 1≤s≤n, (vis,vi(s-1))∈Es-1, and then there exists a sequence satisfying the conditions in Lemma 8 as long as vis-1(s-1)=vi(s-1) for all s.
Fori∈Vl,2≤l≤m, in G there exists a path of length l-1 from i to one node i¯1∈V1. Here we denote the path as (i,i¯l-1),(i¯l-1,i¯l-2),…,(i¯2,i¯1), i¯s∈Vs,1≤s≤l-1. From the weight design approach we have that, for all μ, (i,i)∈E(t) for t∈[kl,n). Thus in the (n+1)-partite graph (⋃t=0nVt,⋃t=0n-1Et), for kl≤t<n, (vi(t+1),vit)∈Et. In time interval [kl-1,kl), denote ti¯l-1=i¯l-1-1 as the time when i¯l-1∈Vl-1∩Ni is activated, and there is no else node in Vl-1∩Ni being activated in (ti¯l-1,kl). Then for t=ti¯l-1, (i,i¯l-1)∈E(ti¯l-1); for ti¯l-1<t<kl, (i,i)∈E(t); and for kl-1≤t<ti¯l-1, (i¯l-1,i¯l-1)∈E(t). Thus in (⋃t=0nVt,⋃t=0n-1Et), for ti¯l-1<t<kl, (vi(t+1),vit)∈Et; (vi(ti¯l-1+1),vi¯l-1ti¯l-1)∈Eti¯l-1; and for kl-1≤t<ti¯l-1, (vi¯l-1(t+1),vi¯l-1t)∈Et. In the same way, in time interval [0,k1), denote ti¯0=i¯0-1 as the time when i¯0∈V1∩Ni¯1 is activated, and there is no else node in V1∩Ni¯1 being activated in (ti¯0,k1). Then (i¯1,i¯0)∈E(ti¯0); for ti¯0<t<k1, (i¯1,i¯1)∈E(t); and for 0≤t<ti¯0, (i¯0,i¯0)∈E(t). Thus in (⋃t=0nVt,⋃t=0n-1Et), for i¯0-1<t<k1, (vi¯1(t+1),vi¯1t)∈Et; (vi¯1i¯0,vi¯0(i¯0-1))∈Ei¯0-1; and for 0≤t<i¯0-1, (vi¯0(t+1),vi¯0t)∈Et.
Therefore, in the (n+1)-partite graph (⋃t=0nVt,⋃t=0n-1Et), there exists a sequence of edges ⋃t=n-1i¯l-1(vi(t+1),vit), vii¯l-1,vi¯l-1i¯l-1-1,…,(vi¯1i¯0,vi¯0(i¯0-1)), ⋃t=i¯0-20(vi¯0(t+1),vi¯0t), where i¯0∈V1. This lemma has been proved.Remark 9.
Lemma8 implies that, in the network satisfying Assumptions 1–3, during each switching period [tn,(t+1)n)(t≥0), any sensor node can receive the information of some node in V1.Remark 10.
In this paper, we apply Assumption3 to make sure that Lemma 8 holds. If the sensors’ activated order does not satisfy Assumption 3, the conditions in Lemma 8 cannot be guaranteed. For example, if the communication graph is a path, the edge set is denoted by {(4,3),(3,2),(2,1)}, and the activated order is 4,3,2,1, then, in the 5-partite graph of the time-varying topology over any period [4t+s,4(t+1)+s) (0≤s≤3, t≥0), node 1 is not reachable; i.e., the conditions in Lemma 8 cannot be satisfied.In the following, we use a simple example to illustrate the result in Lemma8.Example 11.
Consider a network with 4 nodes. Just node 1 can get the information of the leader, i.e.,b^1=1 and b^i=0,i>1. The available communication topology is prior given by Figure 1 and, for all i, (i,i)∈E. The network is periodically switching and satisfies Assumptions 1–3. We know that V1={1},V2={2,3}, and V3={4}. The order of working sensor in one period is 1,2,3,4.Whenμ in weights is 0, the 5-partite graphs of the network in one period are, respectively, given in Figure 4. Here the solid black nodes denote the activated nodes in the time instants. For the case μ=0, there are 2 sequences of edges from v44 to v10, and from v34 to v10, and there is one sequence of edges from v24 to v10, and from v14 to v10. In these sequences, there exist edges containing working node v10, 1∈V0. For the case μ>0, there is one sequence of edges from v14 to v10, there are 2 sequences of edges from v34 to v10, 3 sequences of edges from v44 to v10, and 4 sequences of edges from v24 to v10. In these sequences, there exist edges containing working node v10, 1∈V0.Figure 4
Time-sequence bipartite graphs of the network in one period.Lemma 12.
Consider a periodically switching network satisfying Assumptions1–3 with weights given by (6)-(8). For i,1≤i≤n, denote Pi as the set of sequences of edges (vinn,vin-1(n-1)), (vin-1(n-1),vin-2(n-2)),…,(vi11,vi00) satisfying the conditions in Lemma 8. Then the weights w¯vissvis-1(s-1) of the edges (viss,vis-1(s-1)), s=1,2,…,n, in (n+1)-partite graph satisfy the following inequality:(15)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1≥11+μli+ri-1,where ri=|Ni⋂{Vli,…,Vm}|.Proof.
For notation simplicity, we letk1=|V1|, k2=k1+|V2|, ks+1=ks+|Vs+1|, 1≤s≤m-1.
Firstly we discuss the case whenμ=0. Under the weight design approach, for any edge (viss,vis-1(s-1))∈Es-1 in a sequence in Pi, there has lis≥lis-1. If lis>lis-1, then w¯vissvis-1(s-1)=1, and if lis=lis-1, then w¯vissvis-1(s-1) equals 1 or 1/2. For i∈Vl, when kl<s≤n, wii(s-1)≡1, and then is-1=i, w¯vissvis-1(s-1)=w¯visvi(s-1)=1. If, in the time-varying network (V,E(k),A(k)), node sl∈Vl is activated to transmit its information to node i at sl-1(kl-1≤sl-1<kl), and there is no else node in Vl∩Ni being activated in time [sl,kl), then wii(s-1)=1 for s∈(sl,kl], and wii(sl-1)=wisl(sl-1)=1/2. Thus in (⋃s=0nVs,⋃s=0n-1Es), for s∈(sl,kl], vis-1(s-1)=vi(s-1) and w¯vissvis-1(s-1)=1. For s=sl, there are two edges in Es-1 satisfying the conditions for Pi. One is with visl-1(sl-1)=vi(sl-1) and w¯vislslvi(sl-1)=1/2. The other is with visl-1(sl-1)=vsl(sl-1) and w¯vislslvsl(sl-1)=1/2. Then, (16)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1=12∑P^i∏s=1sl-1w¯vissvis-1s-1+12∑P^sl∏s=1sl-1w¯vjssvjs-1s-1. where P^i={(vin,vi(n-1)),…,(vi(sl+1),visl),(visl,vi(sl-1)), (vi(sl-1),visl-2(sl-2)),…,(vi11,vi00)}∈Pi, P^sl={(vin,vi(n-1)),…,(vi(sl+1),visl),(visl,vsl(sl-1)), (vsl(sl-1),vjsl-2(sl-2)),…,(vj11,vj00)}∈Pi.
Similarly, we have that(17)∑vin,vin-1n-1,…,vi11,vi00∈Pi∏s=1nw¯vissvis-1s-1=1.
Secondly we discuss the case whenμ>0. Under the weight design approach, for any edge (viss,vis-1(s-1))∈Es-1, we have (18)w¯vissvis-1s-1=11+μ,iflis>lis-1;μlis-1μlis+μlis-1≤μ1+μ,iflis<lis-1;12,iflis=lis-1andis≠is-1;1,ifis=is-1=sors∉Nis;12,ifis=is-1≠s,s∈Nis,andlis=ls;μlisμls+μlis≥11+μ,ifis=is-1≠s,s∈Nis,andlis<ls;μlisμls+μlis≤μ1+μ,ifis=is-1≠s,s∈Nis,andlis>ls.
DefineP¯i as the set of sequences in Pi in which each edge (viss,vis-1(s-1)) satisfies lis≥lis-1 and lis≤ls. Then for lis>lis-1, w¯vissvis-1(s-1)=1/(1+μ), and for other cases, w¯vissvis-1(s-1) equals 1/2, 1, or larger than 1/(1+μ).
Fori∈Vl and {(vin,vin-1(n-1)),…,(vi11,vi00)} in P¯i. Consider s, kl<s≤n; then ls>lis and vis-1(s-1) must be vi(s-1), is-1=i. If s∈Nis=Ni, then w¯vissvis-1(s-1)≥1/(1+μ), otherwise w¯vissvis-1(s-1)=1. Thus (19)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=kl+1nw¯vissvis-1s-1≥11+μri,where ri=|Ni⋂{Vl,…,Vm}|.
Considerkl-1<s≤kl. If, in the time-varying network (V,E(k),A(k)), node sl∈Vl/{i} is activated to transmit its information to node i at sl-1(kl-1≤sl-1<kl), and there is no other node in Vl∩Ni being sensing and broadcasting in time [sl,kl), then wii(sl-1)=wisl(sl-1)=1/2, and for t∈[sl,kl), wii(t)=1. Thus for s∈(sl,kl], vis-1(s-1)=vi(s-1), is-1=i, and w¯vissvis-1(s-1)=1. For s=sl, there are two edges in Es-1 satisfying the conditions for P¯i. One is with visl-1(sl-1)=vi(sl-1) and w¯vislslvisl-1(sl-1)=1/2. The other is with visl-1(sl-1)=vsl(sl-1) and w¯vislslvisl-1(sl-1)=1/2. For edges {(viss,vis-1(s-1)),kl-1≤s<sl} with visl-1(sl-1)=vi(sl-1) in sequences in P¯i, w¯vissvis-1(s-1) equals 1/2 or 1. If for some edge (viss,vis-1(s-1)), w¯vissvis-1(s-1) equals 1/2, then there are also two paths from node vis-1(s-1). Then, ∑E^i∏s=kl-1+1sl-1w¯vissvis-1(s-1)=1, where E^i={(visl,vi(sl-1)), (vi(sl-1),visl-2(sl-2)),…, (vikl-1+1(kl-1+1),vikl-1kl-1)}. Similarly, ∑E^sl∏s=kl-1+1sl-1w¯vjssvjs-1(s-1)=1, where E^sl={(visl,vsl(sl-1)),(vsl(sl-1),vjsl-2(sl-2)),…, (vjkl-1+1(kl-1+1),vjkl-1kl-1)}. Thus, (20)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=kl-1+1nw¯vissvis-1s-1≥11+μri.
Considerkl-2<s≤kl-1. For a path (vinn,vin-1(n-1)),…,(vikl-1+1(kl-1+1),vikl-1kl-1) in one of sequence in P¯i, for node ikl-1∈Vl in the time-varying network (V,E(k),A(k)), if node sl-1∈Vl-1 is activated to transmit its information to node ikl-1 at sl-1-1(kl-2≤sl-1-1<kl-1), and there is no other node in Vl-1∩Nikl-1 being activated in [sl-1,kl-1), then wikl-1,sl-1(sl-1-1)=1/(1+μ), and for t∈[sl-1,kl-1), wikl-1ikl-1(t)=1. Thus for s∈(sl-1,kl-1], vis-1(s-1)=vikl-1(s-1) and w¯vissvis-1(s-1)=1; for s=sl-1, vis-1(s-1)=vsl-1(s-1) and w¯vissvis-1(s-1)=1/(1+μ). For edges (visl-1-1(sl-1-1),visl-1-2(sl-1-2)), …,(vikl-2+1(kl-2+1),vikl-2kl-2), applying the similar analysis for edges {(viss,vis-1(s-1)),kl-1≤s<sl}, we have that (21)∑E^kl-1∏s=kl-2+1kl-1w¯vissvis-1s-1=11+μ, where E^kl-1={(vin,vin-1(n-1)),…, (vikl-1+1(kl-1+1),vikl-1kl-1),…,(vj11,vj00)}∈P¯i
In the same way, for2≤g≤l, k0=0, we have that (22)∑E^kg-1∏s=kg-2+1kg-1w¯vissvis-1s-1=11+μ,where E^kg-1={(vin,vin-1(n-1)),…, (vikg-1+1(kg-1+1),vikg-1kg-1),…,(vj11,vj00)}∈P¯i. Therefore, for i∈Vl, (23)∑vin,vin-1n-1,…,vi11,vi00∈P¯i∏s=1nw¯vissvis-1s-1≥11+μl+ri-1.Since P¯i is a subset of Pi, this lemma has been proved.Back to Example11, we have ∑P1∏s=1nw¯v1ssv1s-1(s-1)=1, ∑P2∏s=1nw¯v2ssv2s-1(s-1)=1/(1+μ)2+(1+μ)/(1+μ)3+μ2/(1+μ)4, ∑P3∏s=1nw¯v3ssv3s-1(s-1)=1/(1+μ), ∑P4∏s=1nw¯v4ssv4s-1(s-1)=1/(1+μ)2+(1-μDD)/(1+μ)3. These values satisfy the condition in Lemma 12.Lemma 13.
Consider a periodically switching network satisfying Assumptions1–3, and the weights are given by (6)-(8). For i,1≤i≤n, there exists a nonempty set Pi consisting of time-sequences of edges {(in,in-1),…,(i1,i0)}, where (is,is-1)∈E(s-1), in=i, and there is at least one edge (is0,is0)∈E(is0-1) and is0∈V1. And moreover,(24)∑in,in-1,…,i1,i0∈Pi∏s=1nwisis-1s-1≥11+μli+ri-1,where ri=|Ni⋂{Vli,…,Vm}|.Proof.
If, in the time-varying networks, during time interval[kn,(k+1)n) there exist g>0 time-sequences of edges (in,in-1), in-1,in-2,…,(i1,i0) with in=i, i0=j, each edge (is,is-1)∈E(kn+s-1) with positive weights, s=1,2,…,n, then W¯ij is nonzero and equals the sum of g elements ∏s=1nwisis-1(s-1).
From the definition of the (n+1)-partite graph of the time-varying networks from time 0 to time n-1, we have that the sequence of edges (in,in-1),…,(i1,i0) with (is,is-1)∈E(s-1) in the time-varying networks is equivalent to the sequence of edges vinn,vin-1n-1,…,(vi11,vi00) with (viss,vis-1(s-1))∈Es-1 in the (n+1)-partite graph (⋃s=0nVs,⋃s=0n-1Es), and wisis-1(s-1)=w¯vissvis-1(s-1). Thus ∏s=1nwisis-1(s-1)=∏s=1nw¯vissvis-1(s-1).
For a network satisfying Assumptions1–3, from Lemma 8 we have that, for all i, in the sequence of edges {(in,in-1),…,(i1,i0)} with (is,is-1)∈E(s-1) and in=i, there exists at least one sequence of edges (is0,is0)∈E(is0-1) and is0∈V1. And by applying Lemma 12, this lemma can be proved.


## 3.3. Stability Condition

In this subsection, we discuss how to selectμ and observer gain such that in periodically working sensor networks the estimation error system (13) can asymptotically converge to zero.From system (13), when j is activated at time k we have(25)ek+1=Ξjek,where Ξj is a matrix in which the ith(i≠j) diagonal block matrices are (1-a^ij(μlj-lij/(μli-lij+μlj-lij)))Aei(k) and the jth diagonal block matrix is (A-b^jFC), the jth column block matrices are a^ij(μlj-lij/(μli-lij+μlj-lij))(A-bjFC), and the other column block matrices are0.It is obvious that in almost all cases system (25) is not stable, which means that each subsystem of the switching system is not asymptotically stable. However, through periodic switching, the whole system can still achieve stability. From Assumptions 1–3, the estimation error system has the following equation:(26)ek+1n=Ξekn,where Ξ=ΞnΞn-1⋯Ξ1.Theorem 14.
For periodically switching networks satisfying Assumptions1–3, and the weights are given by (6)-(8). If there exists a symmetric definite matrix P∈Rp×p and a gain matrix F∈Rp×q such that(27)An-1A-FCAk0-1TPAn-1A-FCAk0-1<P,and(28)μ<AnP-An-1A-FCAk0-1PAnP-11/M-1,then the estimation error of the sensor network asymptotically converges to zero, where k0=|V0|, M=maxi⁡{li+ri-1}, ri=|Ni⋂{Vli,…,Vm}|.Proof.
DenoteΞ=[Ξij]n×n as a block matrix with blocks Ξij∈Rp×p. In the time-varying networks if, during each time interval [kn,(k+1)n), there exist g>0 sequences of edges (in,in-1), (in-1,in-2),…,(i1,i0) with in=i, i0=j, each edge (is,is-1)∈E(kn+s-1) with positive weights, s=1,2,…,n, then Ξij is nonzero and is a sum of g matrices. Each addition part is a multiplication of n matrices and weights and has the form ∏s=1nwisis-1(s-1)Ais-1. Define k0=|V0|. Obviously, for is>k0, Ais-1=A, and for 1≤is≤k0, Ais-1 is either A or A-FC.
For a network satisfying Assumptions1–3, from Lemma 12 we have that, for each i (1≤i≤n), there exists at least one nonzero block matrix Ξii0=∑{(is,is-1)∈E(s-1),1≤s≤n∏s=1nwisis-1(s-1)An-k0Aik0-1⋯Ai0 having at least one addition part with at least one multiplied matrix A-FC and the corresponding weight being larger than 1/(1+μ)li+ri-1. That is to say, there exists at least one matrix ∏s=1nwisis-1(s-1)An-k0Aik0-1⋯Ai0 where there is at least one matrix in Aik0-1,…,Ai0 being equal to A-FC, and ∏s=1nwisis-1(s-1)≤1/(1+μ)li+ri-1. Thus, if there exists a matrix P>0 such that (27) holds, then for the matrix An-k0Aik0-1⋯Ai0 containing multiplied matrix A-FC, An-k0Aik0-1⋯Ai0P≤An-1(A-FC)Ak0-1P<1, where AP2=maxx≠0(xTATPAx/xTPx).
Since(29)∑j=1nΞijP≤∑j=1n∑is,is-1∈Es-1,1≤s≤n,i0=j∏s=1nwisis-1s-1An-k0Aik0-1⋯Ai0P≤11+μMAn-1A-FCAk0-1P+1-11+μMAnP,if the condition (28) holds, then ρ(Ξ)≤maxi⁡{∑j=1nΞijP}<1, and then system (26) is asymptotically stable. This theorem has been proved.Remark 15.
IfA is nonsingular, the LMI (27) can be converted to the following LMI: (30)PPAn+k0-1-YCAk0-1TPAn+k0-1-YCAk0-1P>0,where the gain F can be obtained by F=(A-1)n-1P-1Y. Since (A,C) is observable, the LMI must be feasible and thus μ can be computed from inequality (28). If the prior given extended topology G¯ is a tree, then M=m, there is only one sequence in Pi, and ∑{(vin,vin-1(n-1)),…,(vi11,vi00)}∈Pi∏s=1nw¯vissvis-1(s-1)=1/(1+μ)li. Ξ is a lower triangular block matrix with diagonal blocks An-1(A-FC) and (μ/1+μ)An. Thus the estimation error system is asymptotically stable if and only if ρAn-1A-FC<1 and μ<1/(ρn(A)-1).


## 4. Numerical Examples

To verify the validity of the proposed consensus based estimation algorithm, a case where there is one mobile target to be monitored by the network is applied and MATLAB is employed for numerical simulation.The target is moving with second-order system(31)p0k+1=p0k+v0k,v0k+1=2v0k.There are 4 sensors in the network trying to measure the target’s position; i.e., the sensing matrix is C=10. Due to limited sensing capacity, just sensor 1 can get the measurement of the target. The available communication topology is given by Figure 1 as illustrated in Example 6.According to the topology we have thatM=2. By applying Theorem 14 we choose F=1.54320.768T, P=2.747-4.8433-4.84338.9409; then as long as μ<0.0131, the condition in Theorem 14 holds. Selecting μ=0.01, the estimation error of the network ∑i=14ei(k)22 is given in Figure 5. It is shown that the estimation error of the network converges to 0, and thus the design approach is feasible.Figure 5
Estimation errors of periodically switching network whenμ=0.01.


## 5. Conclusion

In this paper we propose a distributed estimation algorithm with a path length based weighted consensus protocol for sensor networks with periodically sensing and broadcasting scheme.(T+2)-partite graph of the time-varying networks over a time period [0,T] is introduced and three lemmas specifying the properties of the multiplications of the stochastic matrices under the periodically switching networks are given. Based on the lemmas, a sufficient condition of the stability of the estimation error is provided. The sensing models considered in this paper are all observable. Individually unobservable while collaboratively observable case is of our interest in future.



---

*Source: 7063724-2018-11-22.xml*