# Consensus of Multiagent Systems with Sampled Information and Noisy Measurements

Authors: Zhao-Jun Tang; Ting-Zhu Huang; Jin-Liang Shao
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

We consider consensus problems of first-order multiagent systems with sampled information and noisy measurements. A distributed stochastic approximation type algorithm is employed to attenuate the measurement noises. We provide conditions under which almost sure strong consensus is guaranteed for fixed and switching directed network topologies. Simulation results are provided to illustrate the theoretical results.


---

## Body

## 1. Introduction

In recent years, distributed coordination control of multiagent systems has received compelling attention from the control community. As a critical issue for coordination control, consensus means that the group of agents reach an agreement on a common value via local communication. Consensus problems are closely related to many different problems that involve interconnection of dynamic systems in various fields of science and engineering, such as synchronization of coupled oscillators, flocking theory, fast consensus in small worlds, rendezvous in space, distributed sensor fusion in sensor networks, and distributed formation control (see [1]).Vicsek et al. [2] provided a variety of simulation results which demonstrate that simple distributed algorithms allow all nodes to eventually reach an agreement. The work in [3] provided a theoretical explanation for the observed behavior of the Vicsek model. Up to now, a variety of consensus protocols have been developed to deal with dynamic topologies [4–6], time delays [7–9], finite-time convergence [10–12], and random network topologies [13, 14], just to name a few.In many applications envisioned, due to the application of digital sensors and controllers, the information exchange among the group of agents may only occur at sampling instants. Thus, it is more practical to consider the consensus problems with sampled-data information. Moreover, with sampled-data control, many benefits can be achieved such as flexibility, robustness, and low cost. Some results about consensus problems for multi-agent systems via sampled-data control have been reported [15–18]. On the other hand, it was assumed that in most existing works each agent can obtain the accurate information from its neighbors. Obviously, this assumption is impractical for real communication channels since the information exchange is often corrupted by various noises. Consensus seeking with noisy measurements has attracted the attention of some researchers. Huang and Manton [19] studied the consensus problem of discrete-time multi-agent systems with fixed and undirected topology under noisy measurements and proposed stochastic approximation-type protocols with a decreasing step size. Subsequently, they extended the results of [19] to the directed topology case. Li and Zhang [20] investigated the average-consensus problem of discrete-time multi-agent systems with time-varying topologies and noisy measurements. Different from discrete-time systems in which the sampling period is often assumed to be 1, the impact of the sampling period has to be considered for sampled-data control systems. In most existing results concerning consensus problems based on sampled-data control, it is shown that the sampling period must satisfy a certain condition to guarantee convergence. To the best of our knowledge, there are a few works considering the consensus problems with sampled information and noisy measurements. Li and Zhang [21] considered mean square average-consensus problems of multi-agent systems based on sampled-data control with noisy measurements and time-invariant topology. Under the assumption that the interaction topology is undirected and connected, it was shown that the agents reach mean square average consensus if the sampling period is sufficiently small.In this paper, we are interested in the consensus problems with sampled information and noisy measurements. That is, we assume that each agent can only obtain the noisy measurements of its neighbors' states at sampling instants. This paper is partly motivated by [21]. This paper makes the following contributions. First, for the case of fixed topology, only the existence of a spanning tree is required in this paper, which is much weaker than connected. Second, the case of time-varying topology is investigated, and we prove that the agents reach almost sure strong consensus provided each interaction topology is balanced and contains a spanning tree. Third, we prove that the convergence condition is independent of the sampling period due to the introduction of the step size. Nevertheless, it should be pointed out that both the step size and the sampling period have an impact on the convergence speed. Comparing with [20, 22], we study continuous-time multi-agent systems with sampled information instead of discrete-time systems. In addition, the method used in the convergence analysis in this paper is different from it in the aforementioned references.The following notations will be used throughout this paper. LetI be an identity matrix with appropriate dimension, and 1 be a column vector of all ones with appropriate dimension. For a given matrix A, AT denotes its transpose; ∥A∥ denotes its 2-norm; let λmax(A) and λmin(A) denote its maximum and minimum eigenvalues, respectively. A matrix A is said to be positive stable if all of its eigenvalues have positive real parts. For a given random variable ξ, E[ξ] denotes its mathematical expectation.


## 2. Problem Formulation

### 2.1. Graph Theory

Consider a multi-agent system consisting ofn agents labeled 1 through n. The interaction topology among the n agents can be described by a digraph 𝒢=(𝒱,ℰ), where 𝒱={1,…,n} is the set of nodes and ℰ⊆𝒱×𝒱 is the set of edges of the graph. An edge of 𝒢 is denoted by (i,j), representing that agent j can directly receive information from agent i. The set of neighbors of node i is denoted by 𝒩i={j∈𝒱∣(j,i)∈ℰ}. A path in 𝒢 is a sequence i0,i1,…,im of distinct nodes such that (ij-1,ij)∈ℰ for j=1,…,m. A directed graph 𝒢 is strongly connected if there is a path between any two distinct nodes. A graph contains a spanning tree if there exists at least one node having a directed path to all other nodes.The weighted adjacency matrix of the digraph𝒢 is denoted by A=[aij]∈ℝn×n, where aij>0 if (j,i)∈ℰ and aij=0 otherwise. The in-degree of node i is defined as degin(i)=∑j=1n‍aij and the out-degree is defined as degout(i)=∑j=1n‍aji. Its degree matrix D=diag{d1,…,dn} is a diagonal matrix, whose diagonal elements di=degin(i). 𝒢 is called a balanced digraph, if degin(i)=degout(i),i=1,2,…,n. The Laplacian matrix associated with the digraph 𝒢 is defined as
(1)L𝒢=D-A.Below is an important property of LaplacianL𝒢.Lemma 1 (see [6]).
Zero is an eigenvalue ofL𝒢, and 1 is the associated right eigenvector. In addition, zero is a simple eigenvalue of L𝒢 and all the other eigenvalues have positive real parts if and only if the digraph 𝒢 contains a spanning tree.


### 2.2. Consensus Protocols

Consider the following first-order integrator system ofn agents:
(2)x˙i(t)=ui(t),i=1,…,n,
where xi∈ℝ and ui∈ℝ are the state and control input of agent i, respectively.In this paper, we assume that each agent can only obtain noisy measurements of the states of its neighbors at sampling instants. Denote the resulting measurement by agenti of xj(kh) by
(3)yij(kh)=xj(kh)+wij(kh),j∈𝒩i,k∈ℤ+={0,1,2,…},
where h is the sampling period and wij(kh) is the additive noise. The underlying probability space is denoted by (Ω,ℱ,P).Definition 2 (see [19]).
The agents are said to reach almost sure strong consensus if there exists a random variablex* such that limt→∞xi(t)=x* almost surely (a.s.), for all i∈𝒱.Remark 3.
When there is no noisy measurements, Definition2 is equivalent to the definition of consensus for deterministic systems. That is, the agents are said to reach consensus if limt→∞(xi(t)-xj(t))=0 for any i≠j.
Our objective is to design a distributed protocol so that then agents can reach almost sure strong consensus. For this end, we study the following distributed protocol [21]:
(4)ui(t)=a(k)∑j∈𝒩i(kh)‍aij(yij(kh)-xi(kh)),∀t∈[kh,(k+1)h),k∈ℤ+,i=1,…,n,
where a(k)>0 is the step size. Here, the introduction of the step size is to attenuate the noises, which is often used in classical stochastic approximation theory [23]. We introduce the following assumptions on the step size sequence:(A1)
∑k=0∞a(k)=∞, ∑k=0∞a2(k)<∞,(A1′)
∑k=0∞a(k)=∞, limk→∞a(k)=0.Remark 4.
Assumption (A1′) is weaker than assumption (A1). The above assumptions imply that the impact of the noise can be attenuated as time goes on sincea(k)→0 as k→∞. ∑k=0∞‍a(k)=∞ implies that a(k) cannot decrease too fast since, otherwise, the agents may prematurely converge to different individual limits.
Writex=(x1,…,xn)T. The discrete-time model with zero-order hold of (2) is
(5)xi((k+1)h)=xi(kh)+hui(kh),k∈ℤ+.
With the protocol (4), (5) can be written in matrix form as
(6)x((k+1)h)=(I-a(k)hL𝒢(kh))x(kh)+a(k)hw(kh),
where w(kh)=(w1(kh),…,wn(kh))T with wi(kh)=∑j=1n‍aijwij(kh). Denote w(kh)=(w1T(kh),…,wnT(kh))T∈ℝn2 with wi(kh)=(wi1(kh),…,win(kh))T∈ℝn. We introduce the following assumptions on the measurement noises.
(A2){w(kh)∈ℝn2,ℱw(kh)} is a martingale difference sequence, supk≥0E∥w(kh)∥2<∞, where and whereafter ℱw(kh) denotes the σ-algebras σ{w(0),…,w(kh)} for k≥0.
Note that (A2) contains that{wij(kh),k∈ℤ+,i,j=1,2,…,n,(j,i)∈ℰ} are independent sequences with zero mean and uniformly bounded second-order moments as a special case.


## 2.1. Graph Theory

Consider a multi-agent system consisting ofn agents labeled 1 through n. The interaction topology among the n agents can be described by a digraph 𝒢=(𝒱,ℰ), where 𝒱={1,…,n} is the set of nodes and ℰ⊆𝒱×𝒱 is the set of edges of the graph. An edge of 𝒢 is denoted by (i,j), representing that agent j can directly receive information from agent i. The set of neighbors of node i is denoted by 𝒩i={j∈𝒱∣(j,i)∈ℰ}. A path in 𝒢 is a sequence i0,i1,…,im of distinct nodes such that (ij-1,ij)∈ℰ for j=1,…,m. A directed graph 𝒢 is strongly connected if there is a path between any two distinct nodes. A graph contains a spanning tree if there exists at least one node having a directed path to all other nodes.The weighted adjacency matrix of the digraph𝒢 is denoted by A=[aij]∈ℝn×n, where aij>0 if (j,i)∈ℰ and aij=0 otherwise. The in-degree of node i is defined as degin(i)=∑j=1n‍aij and the out-degree is defined as degout(i)=∑j=1n‍aji. Its degree matrix D=diag{d1,…,dn} is a diagonal matrix, whose diagonal elements di=degin(i). 𝒢 is called a balanced digraph, if degin(i)=degout(i),i=1,2,…,n. The Laplacian matrix associated with the digraph 𝒢 is defined as
(1)L𝒢=D-A.Below is an important property of LaplacianL𝒢.Lemma 1 (see [6]).
Zero is an eigenvalue ofL𝒢, and 1 is the associated right eigenvector. In addition, zero is a simple eigenvalue of L𝒢 and all the other eigenvalues have positive real parts if and only if the digraph 𝒢 contains a spanning tree.


## 2.2. Consensus Protocols

Consider the following first-order integrator system ofn agents:
(2)x˙i(t)=ui(t),i=1,…,n,
where xi∈ℝ and ui∈ℝ are the state and control input of agent i, respectively.In this paper, we assume that each agent can only obtain noisy measurements of the states of its neighbors at sampling instants. Denote the resulting measurement by agenti of xj(kh) by
(3)yij(kh)=xj(kh)+wij(kh),j∈𝒩i,k∈ℤ+={0,1,2,…},
where h is the sampling period and wij(kh) is the additive noise. The underlying probability space is denoted by (Ω,ℱ,P).Definition 2 (see [19]).
The agents are said to reach almost sure strong consensus if there exists a random variablex* such that limt→∞xi(t)=x* almost surely (a.s.), for all i∈𝒱.Remark 3.
When there is no noisy measurements, Definition2 is equivalent to the definition of consensus for deterministic systems. That is, the agents are said to reach consensus if limt→∞(xi(t)-xj(t))=0 for any i≠j.
Our objective is to design a distributed protocol so that then agents can reach almost sure strong consensus. For this end, we study the following distributed protocol [21]:
(4)ui(t)=a(k)∑j∈𝒩i(kh)‍aij(yij(kh)-xi(kh)),∀t∈[kh,(k+1)h),k∈ℤ+,i=1,…,n,
where a(k)>0 is the step size. Here, the introduction of the step size is to attenuate the noises, which is often used in classical stochastic approximation theory [23]. We introduce the following assumptions on the step size sequence:(A1)
∑k=0∞a(k)=∞, ∑k=0∞a2(k)<∞,(A1′)
∑k=0∞a(k)=∞, limk→∞a(k)=0.Remark 4.
Assumption (A1′) is weaker than assumption (A1). The above assumptions imply that the impact of the noise can be attenuated as time goes on sincea(k)→0 as k→∞. ∑k=0∞‍a(k)=∞ implies that a(k) cannot decrease too fast since, otherwise, the agents may prematurely converge to different individual limits.
Writex=(x1,…,xn)T. The discrete-time model with zero-order hold of (2) is
(5)xi((k+1)h)=xi(kh)+hui(kh),k∈ℤ+.
With the protocol (4), (5) can be written in matrix form as
(6)x((k+1)h)=(I-a(k)hL𝒢(kh))x(kh)+a(k)hw(kh),
where w(kh)=(w1(kh),…,wn(kh))T with wi(kh)=∑j=1n‍aijwij(kh). Denote w(kh)=(w1T(kh),…,wnT(kh))T∈ℝn2 with wi(kh)=(wi1(kh),…,win(kh))T∈ℝn. We introduce the following assumptions on the measurement noises.
(A2){w(kh)∈ℝn2,ℱw(kh)} is a martingale difference sequence, supk≥0E∥w(kh)∥2<∞, where and whereafter ℱw(kh) denotes the σ-algebras σ{w(0),…,w(kh)} for k≥0.
Note that (A2) contains that{wij(kh),k∈ℤ+,i,j=1,2,…,n,(j,i)∈ℰ} are independent sequences with zero mean and uniformly bounded second-order moments as a special case.


## 3. Main Results

### 3.1. Fixed Topology

In this subsection, we consider the case of fixed topology. We begin by studying the noise-free case; that is,wij=0,i,j=1,…,n. Then protocol (4) becomes
(7)ui(t)=a(k)∑j=1n‍aij(xj(kh)-xi(kh)),∀t∈[kh,(k+1)h),i=1,…,n,
and system (6) becomes
(8)x((k+1)h)=(I-a(k)hL)x(kh).We make the following assumption on the network topology.(A3)
𝒢 has a spanning tree.It is not easy to analyze the convergence of system (8) directly since L is not positive stable. To deal with this problem, we need the following lemma.Lemma 5 (see [22]).
Assuming (A3), denote𝒞(L)={ϕ∈Rn×(n-1)∣span{ϕ}=span{L}}. For any given Q1∈𝒞(L), the matrix Q=(1,Q1) is nonsingular and
(9)Q-1LQ=(0H),
where H∈ℝ(n-1)×(n-1) is positive stable. In addition, let Q-1=(qTQ2), where q∈ℝn; then qTL=0 and qT1=1.Following the notation in Lemma5, let δ(kh)=(δ1(kh),…,δn(kh))T=Q-1x(kh). Then we can obtain the following system associated with system (8):
(10)δ^((k+1)h)=(I-a(k)hH)δ^(kh),
where δ^(kh)=(δ2(kh),…,δn(kh))T. Furthermore, we have the following relationship:
(11)x(kh)=δ1(kh)1+Q1δ^(kh),(12)δ1((k+1)h)=δ1(kh)+a(k)hqTw(kh).
Noticing that H is positive stable, by Lyapunov theorem [24], there exists a positive definite matrix P such that
(13)PH+HTP=I.
Before moving on, we need the following lemma.Lemma 6 (see [25]).
Let{u(k),k=0,1,…},  {α(k),k=0,1,…}, and {q(k),k=0,1,…} be real sequence, satisfying 0<q(k)≤1, α(k)≥0, k=0,1,…,∑k=0∞‍q(k)=∞, α(k)/q(k)→0, k→∞, and
(14)u(k+1)≤(1-q(k))u(k)+α(k).
Then limsupk→∞u(k)≤0. In particular, if u(k)≥0,k=0,1,…, then u(k)→0 as k→∞.Theorem 7.
Apply protocol (7) to system (2). Assume that (A1′) and (A2) hold; then the n agents reach consensus.Proof.
Take a Lyapunov function(15)V(k)=δ^T(kh)Pδ^(kh),
where P is defined in (13). Then,
(16)V(k+1)=V(k)-a(k)hδ^T(kh)δ^(kh)+a2(k)h2δ^T(kh)HTHδ^(kh).
Using the fact that
(17)λmin(P)δ^T(kh)δ^(kh)≤δ^T(kh)Pδ^(kh)≤λmax(P)δ^T(kh)δ^(kh),
it follows that
(18)V(k+1)≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k).
By (A1′), there exists a k0>0 such that a(k)≤λmin(P)/2hλmax(HTH)λmax(P) and a(k)≤λmin(P)/h for all k≥k0. Thus,
(19)V(k+1)≤[1-12a(k)h1λmax(P)]V(k),k≥k0.
In light of Lemma 6, we have limk→∞V(k)=0 by noting that ∑k=0∞‍a(k)=∞. This implies limk→∞δ^(kh)=0. Therefore, the conclusion readily follows from (11).Now we investigate the case of having noisy measurements. We can obtain the following system associated with system (6):
(20)δ^((k+1)h)=(I-a(k)hH)δ^(kh)+a(k)hQ2w(kh),whereH and Q2 are defined in Lemma 5.Theorem 8.
Consider system (20). Assume that (A1)–(A3) hold; then
(21)limk→∞∥δ^(kh)∥2=0a.s.Proof.
Choose a Lyapunov function(22)V(k)=δ^T(kh)Pδ^(kh),
where P is defined in (13). By a similar argument to that in the proof of (18), we can obtain
(23)V(k+1)≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k)+2a(k)hδ^T(kh)×(I-a(k)hHT)PQ2w(kh)+a2(k)h2wT(kh)Q2TQ2w(kh).
Taking the expectation of the above, given {V(s):s≤k}, yields
(24)E{V(k+1)∣V(s):s≤k}≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k)+C1a2(k),
for some constant C1>0, where we have used the fact that E[δ^T(kh)(I-a(k)hHT)PQ2w(kh)]=0 by noting that δ^(kh)∈ℱw((k-1)h).
By a similar argument to that in the proof of (19), there exists a k0>0 such that
(25)E{V(k+1)∣V(s):s≤k}≤[1-12a(k)h1λmax(P)]×V(k)+C1a2(k),∀k≥k0.
We will make use of the following lemma to finish up our proof.
Lemma 9 (see [25]). Consider a sequence of nonnegative random variables{V(k)}k≥0withE{V(0)}<∞. Let(26)E{V(k+1)∣V(k),…,V(1),V(0)}≤(1-c1(k))V(k)+c2(k),where(27)0≤c1(k)≤1,c2(k)≥0,∀k,∑k=0∞‍c2(k)<∞,∑k=0∞‍c1(k)=∞,limk→∞c1(k)c2(k)=0.
Then,
V
(
k
)
a.s. converges to zero; that is,
(28)
lim
k
→
∞
V
(
k
)
=
0
a
.
s
.
It is not hard to show that conditions (26) and (27) are satisfied. Therefore,
lim
k
→
∞
V
(
k
)
=
0
, a.s., which implies the conclusion.LetJ=(1/n)11T. The following lemma will be used to obtain the main result of this subsection.Lemma 10 (see [26]).
LetV(k)=∥x(kh)-Jx(kh)∥2. Then
(29)limk→∞V(k)=0a.s.
if and only if
(30)limk→∞x(kh)=c1a.s.,
for some c∈ℝ.Theorem 11.
Apply protocol (4) to system (2). Assume that (A1)–(A3) hold; then the n agents reach almost sure strong consensus.Proof.
From (11), we have
(31)∥(I-J)x(kh)∥2=∥(I-J)Q1δ^(kh)∥2≤∥Q1T(I-J)Q1∥∥δ^(kh)∥2,
by noting that (I-J)1=0 and (I-J)2=I-J. By Theorem 8, we have
(32)limk→∞∥x(kh)-Jx(kh)∥2=0a.s.
Invoking Lemma 10, we have
(33)limk→∞x(kh)=c1a.s.,
for some constant c.
At the same time, since∑k=0∞‍a2(k)E∥w(kh)∥2<∞ by (A2), it follows that
(34)∑k=0∞‍a2(k)E∥w(kh)∥2<∞.
By the martingale convergence theorem [27], it follows that ∑k=0∞‍a(k)w(kh) converge a.s., as k→∞. Then, we have
(35)limk→∞a(k)w(kh)=0a.s.
Notice that
(36)x(t)=[I-a(k)(t-kh)L]x(kh)+a(k)hw(kh),∀t∈[kh,(k+1)h).
This together with (33) and (35) leads to
(37)limt→∞x(t)=c1a.s.,
for some constant c, which completes the proof.Remark 12.
In most existing works concerning consensus problems based on sampled-data control, there is a requirement on the sampling periodh to guarantee convergence since there is no step size or step size a(k)≡1. For instance, when a(k)≡1 we can easily show that the sampling period must satisfy h≤1/λmax(L) to guarantee the convergence of system (8). However, by Theorems 7 and 11, we find that the convergence condition is independent of the sampling period h for both noise-free and noisy measurements cases. This is due to the introduction of the step size. In other words, the introduction of the step size is necessary for enhancing the robustness of the sampled-data consensus protocol against sampling period.


### 3.2. Time-Varying Topology

In this subsection, we consider the case when the network topology changes dynamically. In order to describe the time-varying topology, we define a switching signalσ(k):ℤ+→𝒫={1,2,…,N}, where N is the total number of all possible graphs describing the interaction topologies. At each sampling time kh, the underlying graph is denoted by 𝒢σ(k). Then, we rewrite system (6) as
(38)x((k+1)h)=(I-a(k)hLσ(k))x(kh)+a(k)hw(kh),
where Lσ(k) denotes the Laplacian matrix associated with the diagraph 𝒢σ(k).We introduce the following assumption on the network topology.(A4)
𝒢σ(k) is balanced for any k∈ℤ+.Under (A4), there exists an orthogonal matrixU=((1/n)1,U1)∈ℝn×n such that
(39)UTLσ(k)U=(0Hσ(k)),∀k∈ℤ+,
where Hσ(k)∈ℝ(n-1)×(n-1).Letδ(kh)=(δ1(kh),…,δn(kh))T=UTx(kh). We can obtain the following system associated with system (38):
(40)δ^((k+1)h)=(I-a(k)hHσ(k))δ^(kh)+a(k)hU1Tw(kh),
where δ^(kh)=(δ2(kh),…,δn(kh))T. In addition, we have
(41)x(kh)=1nδ1(kh)1+U1δ^(kh).Theorem 13.
Consider system (40). Suppose that (A1)–(A4) hold; then
(42)limk→∞∥δ^(kh)∥2=0a.s.Proof.
Choose a Lyapunov function(43)V(k)=δ^T(kh)δ^(kh).
It is not hard to show that both Hσ(k)+Hσ(k)T and Hσ(k)THσ(k) are positive definite for any k∈ℤ+ since 𝒢σ(k) is balanced and contains a spanning tree. It follows from (40) that
(44)V(k+1)≤[1-a(k)hλmin(Hσ(k)T+Hσ(k))+a2(k)h2λmax(Hσ(k)THσ(k))]V(k)+2a(k)hδ^T(kh)(I-a(k)hHσ(k)T)U1Tw(kh)+a2(k)h2wT(kh)U1U1Tw(kh).
Denote λ*=mink≥0{λmin(Hσ(k)T+Hσ(k))} and λ**=maxk≥0{λmax(Hσ(k)THσ(k))}, which are well defined since 𝒫 is a finite set. Thus,
(45)V(k+1)≤[1-a(k)hλ*+a2(k)h2λ**]V(k)+2a(k)hδ^T(kh)(I-a(k)hHσ(k)T)×U1Tw(kh)+a2(k)h2wT(kh)U1U1Tw(kh).
The rest of the proof is similar to that in Theorem 8 and hence omitted.Theorem 14.
Apply protocol (4) to system (2). Assume that (A1)–(A4) hold; then the n agents reach almost sure consensus.Proof.
Note that(46)∥x(kh)-Jx(kh)∥2=∥(I-J)U1δ^(kh)∥2≤∥U1T(I-J)U1∥∥δ^(kh)∥2,
by (41).
The remaining of the proof is similar to that of Theorem11 and hence omitted here.Remark 15.
Note that the condition in Theorem14 that 𝒢σ(k) is balanced is a sufficient condition. To weaken the condition on the network topology, it may require a new method. We leave this for further investigation.


## 3.1. Fixed Topology

In this subsection, we consider the case of fixed topology. We begin by studying the noise-free case; that is,wij=0,i,j=1,…,n. Then protocol (4) becomes
(7)ui(t)=a(k)∑j=1n‍aij(xj(kh)-xi(kh)),∀t∈[kh,(k+1)h),i=1,…,n,
and system (6) becomes
(8)x((k+1)h)=(I-a(k)hL)x(kh).We make the following assumption on the network topology.(A3)
𝒢 has a spanning tree.It is not easy to analyze the convergence of system (8) directly since L is not positive stable. To deal with this problem, we need the following lemma.Lemma 5 (see [22]).
Assuming (A3), denote𝒞(L)={ϕ∈Rn×(n-1)∣span{ϕ}=span{L}}. For any given Q1∈𝒞(L), the matrix Q=(1,Q1) is nonsingular and
(9)Q-1LQ=(0H),
where H∈ℝ(n-1)×(n-1) is positive stable. In addition, let Q-1=(qTQ2), where q∈ℝn; then qTL=0 and qT1=1.Following the notation in Lemma5, let δ(kh)=(δ1(kh),…,δn(kh))T=Q-1x(kh). Then we can obtain the following system associated with system (8):
(10)δ^((k+1)h)=(I-a(k)hH)δ^(kh),
where δ^(kh)=(δ2(kh),…,δn(kh))T. Furthermore, we have the following relationship:
(11)x(kh)=δ1(kh)1+Q1δ^(kh),(12)δ1((k+1)h)=δ1(kh)+a(k)hqTw(kh).
Noticing that H is positive stable, by Lyapunov theorem [24], there exists a positive definite matrix P such that
(13)PH+HTP=I.
Before moving on, we need the following lemma.Lemma 6 (see [25]).
Let{u(k),k=0,1,…},  {α(k),k=0,1,…}, and {q(k),k=0,1,…} be real sequence, satisfying 0<q(k)≤1, α(k)≥0, k=0,1,…,∑k=0∞‍q(k)=∞, α(k)/q(k)→0, k→∞, and
(14)u(k+1)≤(1-q(k))u(k)+α(k).
Then limsupk→∞u(k)≤0. In particular, if u(k)≥0,k=0,1,…, then u(k)→0 as k→∞.Theorem 7.
Apply protocol (7) to system (2). Assume that (A1′) and (A2) hold; then the n agents reach consensus.Proof.
Take a Lyapunov function(15)V(k)=δ^T(kh)Pδ^(kh),
where P is defined in (13). Then,
(16)V(k+1)=V(k)-a(k)hδ^T(kh)δ^(kh)+a2(k)h2δ^T(kh)HTHδ^(kh).
Using the fact that
(17)λmin(P)δ^T(kh)δ^(kh)≤δ^T(kh)Pδ^(kh)≤λmax(P)δ^T(kh)δ^(kh),
it follows that
(18)V(k+1)≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k).
By (A1′), there exists a k0>0 such that a(k)≤λmin(P)/2hλmax(HTH)λmax(P) and a(k)≤λmin(P)/h for all k≥k0. Thus,
(19)V(k+1)≤[1-12a(k)h1λmax(P)]V(k),k≥k0.
In light of Lemma 6, we have limk→∞V(k)=0 by noting that ∑k=0∞‍a(k)=∞. This implies limk→∞δ^(kh)=0. Therefore, the conclusion readily follows from (11).Now we investigate the case of having noisy measurements. We can obtain the following system associated with system (6):
(20)δ^((k+1)h)=(I-a(k)hH)δ^(kh)+a(k)hQ2w(kh),whereH and Q2 are defined in Lemma 5.Theorem 8.
Consider system (20). Assume that (A1)–(A3) hold; then
(21)limk→∞∥δ^(kh)∥2=0a.s.Proof.
Choose a Lyapunov function(22)V(k)=δ^T(kh)Pδ^(kh),
where P is defined in (13). By a similar argument to that in the proof of (18), we can obtain
(23)V(k+1)≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k)+2a(k)hδ^T(kh)×(I-a(k)hHT)PQ2w(kh)+a2(k)h2wT(kh)Q2TQ2w(kh).
Taking the expectation of the above, given {V(s):s≤k}, yields
(24)E{V(k+1)∣V(s):s≤k}≤[1-a(k)h1λmax(P)+a2(k)h2λmax(HTH)λmin(P)]V(k)+C1a2(k),
for some constant C1>0, where we have used the fact that E[δ^T(kh)(I-a(k)hHT)PQ2w(kh)]=0 by noting that δ^(kh)∈ℱw((k-1)h).
By a similar argument to that in the proof of (19), there exists a k0>0 such that
(25)E{V(k+1)∣V(s):s≤k}≤[1-12a(k)h1λmax(P)]×V(k)+C1a2(k),∀k≥k0.
We will make use of the following lemma to finish up our proof.
Lemma 9 (see [25]). Consider a sequence of nonnegative random variables{V(k)}k≥0withE{V(0)}<∞. Let(26)E{V(k+1)∣V(k),…,V(1),V(0)}≤(1-c1(k))V(k)+c2(k),where(27)0≤c1(k)≤1,c2(k)≥0,∀k,∑k=0∞‍c2(k)<∞,∑k=0∞‍c1(k)=∞,limk→∞c1(k)c2(k)=0.
Then,
V
(
k
)
a.s. converges to zero; that is,
(28)
lim
k
→
∞
V
(
k
)
=
0
a
.
s
.
It is not hard to show that conditions (26) and (27) are satisfied. Therefore,
lim
k
→
∞
V
(
k
)
=
0
, a.s., which implies the conclusion.LetJ=(1/n)11T. The following lemma will be used to obtain the main result of this subsection.Lemma 10 (see [26]).
LetV(k)=∥x(kh)-Jx(kh)∥2. Then
(29)limk→∞V(k)=0a.s.
if and only if
(30)limk→∞x(kh)=c1a.s.,
for some c∈ℝ.Theorem 11.
Apply protocol (4) to system (2). Assume that (A1)–(A3) hold; then the n agents reach almost sure strong consensus.Proof.
From (11), we have
(31)∥(I-J)x(kh)∥2=∥(I-J)Q1δ^(kh)∥2≤∥Q1T(I-J)Q1∥∥δ^(kh)∥2,
by noting that (I-J)1=0 and (I-J)2=I-J. By Theorem 8, we have
(32)limk→∞∥x(kh)-Jx(kh)∥2=0a.s.
Invoking Lemma 10, we have
(33)limk→∞x(kh)=c1a.s.,
for some constant c.
At the same time, since∑k=0∞‍a2(k)E∥w(kh)∥2<∞ by (A2), it follows that
(34)∑k=0∞‍a2(k)E∥w(kh)∥2<∞.
By the martingale convergence theorem [27], it follows that ∑k=0∞‍a(k)w(kh) converge a.s., as k→∞. Then, we have
(35)limk→∞a(k)w(kh)=0a.s.
Notice that
(36)x(t)=[I-a(k)(t-kh)L]x(kh)+a(k)hw(kh),∀t∈[kh,(k+1)h).
This together with (33) and (35) leads to
(37)limt→∞x(t)=c1a.s.,
for some constant c, which completes the proof.Remark 12.
In most existing works concerning consensus problems based on sampled-data control, there is a requirement on the sampling periodh to guarantee convergence since there is no step size or step size a(k)≡1. For instance, when a(k)≡1 we can easily show that the sampling period must satisfy h≤1/λmax(L) to guarantee the convergence of system (8). However, by Theorems 7 and 11, we find that the convergence condition is independent of the sampling period h for both noise-free and noisy measurements cases. This is due to the introduction of the step size. In other words, the introduction of the step size is necessary for enhancing the robustness of the sampled-data consensus protocol against sampling period.


## 3.2. Time-Varying Topology

In this subsection, we consider the case when the network topology changes dynamically. In order to describe the time-varying topology, we define a switching signalσ(k):ℤ+→𝒫={1,2,…,N}, where N is the total number of all possible graphs describing the interaction topologies. At each sampling time kh, the underlying graph is denoted by 𝒢σ(k). Then, we rewrite system (6) as
(38)x((k+1)h)=(I-a(k)hLσ(k))x(kh)+a(k)hw(kh),
where Lσ(k) denotes the Laplacian matrix associated with the diagraph 𝒢σ(k).We introduce the following assumption on the network topology.(A4)
𝒢σ(k) is balanced for any k∈ℤ+.Under (A4), there exists an orthogonal matrixU=((1/n)1,U1)∈ℝn×n such that
(39)UTLσ(k)U=(0Hσ(k)),∀k∈ℤ+,
where Hσ(k)∈ℝ(n-1)×(n-1).Letδ(kh)=(δ1(kh),…,δn(kh))T=UTx(kh). We can obtain the following system associated with system (38):
(40)δ^((k+1)h)=(I-a(k)hHσ(k))δ^(kh)+a(k)hU1Tw(kh),
where δ^(kh)=(δ2(kh),…,δn(kh))T. In addition, we have
(41)x(kh)=1nδ1(kh)1+U1δ^(kh).Theorem 13.
Consider system (40). Suppose that (A1)–(A4) hold; then
(42)limk→∞∥δ^(kh)∥2=0a.s.Proof.
Choose a Lyapunov function(43)V(k)=δ^T(kh)δ^(kh).
It is not hard to show that both Hσ(k)+Hσ(k)T and Hσ(k)THσ(k) are positive definite for any k∈ℤ+ since 𝒢σ(k) is balanced and contains a spanning tree. It follows from (40) that
(44)V(k+1)≤[1-a(k)hλmin(Hσ(k)T+Hσ(k))+a2(k)h2λmax(Hσ(k)THσ(k))]V(k)+2a(k)hδ^T(kh)(I-a(k)hHσ(k)T)U1Tw(kh)+a2(k)h2wT(kh)U1U1Tw(kh).
Denote λ*=mink≥0{λmin(Hσ(k)T+Hσ(k))} and λ**=maxk≥0{λmax(Hσ(k)THσ(k))}, which are well defined since 𝒫 is a finite set. Thus,
(45)V(k+1)≤[1-a(k)hλ*+a2(k)h2λ**]V(k)+2a(k)hδ^T(kh)(I-a(k)hHσ(k)T)×U1Tw(kh)+a2(k)h2wT(kh)U1U1Tw(kh).
The rest of the proof is similar to that in Theorem 8 and hence omitted.Theorem 14.
Apply protocol (4) to system (2). Assume that (A1)–(A4) hold; then the n agents reach almost sure consensus.Proof.
Note that(46)∥x(kh)-Jx(kh)∥2=∥(I-J)U1δ^(kh)∥2≤∥U1T(I-J)U1∥∥δ^(kh)∥2,
by (41).
The remaining of the proof is similar to that of Theorem11 and hence omitted here.Remark 15.
Note that the condition in Theorem14 that 𝒢σ(k) is balanced is a sufficient condition. To weaken the condition on the network topology, it may require a new method. We leave this for further investigation.


## 4. Simulations

In this section, two examples are provided to illustrate the theoretical results. In the following two examples, the variance of the i.i.d zero mean Gaussian measurement noises isσ2=0.01, and the step size a(k)=1/(k+1),k≥0. It is clear that Assumptions (A1) and (A2) hold.Example 16.
Consider a multi-agent system consisting of five agents with the interaction topology shown in Figure1. Note that 𝒢1 has a spanning tree. For simplicity, we assume that 𝒢1 has 0-1 weights. Let the initial value of x(0) be taken randomly as [5,2,-3,-1,4]T. Figures 2(a)–2(c) show that the five agents reach consensus under different sampling periods in the case of noise-free. Figures 3(a)–3(c) show that the states of the five agents converge to the same constant under different sampling periods with measurement noises.Figure 1
Interaction topology𝒢1.State trajectories under different sampling periods in the case of noise-free and fixed topologies.
(a)
h= 1
(b)
h= 2
(c)
h= 5State trajectories under different sampling periods with fixed topology and noisy measurements.
(a)
h
=
1
(b)
h
=
2
(c)
h
=
5Example 17.
Consider a multi-agent system consisting of five agents. The interaction topology is time varying of switching periodh between two graphs 𝒢i(i=2,3) described as in Figure 4. For simplicity, we assume that a34=a45=2 in 𝒢3 and the weights of all the other edges in 𝒢2 and 𝒢3 are 1. Note that both 𝒢2 and 𝒢3 are balanced and have a spanning tree. So, (A3) and (A4) are satisfied. It can be seen from Figures 5(a)–5(c) that the states of the five agents converge to the same constant under different sampling periods with measurement noises.Interaction topologies𝒢2 and 𝒢3.
(a)
𝒢
2
(b)
𝒢
3State trajectories under different sampling periods with noisy measurements and time-varying topology.
(a)
h
=
1
(b)
h
=
2
(c)
h
=
5


## 5. Conclusion

In this paper, a consensus problem for a multi-agent system with sampled information and noisy measurements is investigated. Both the case of fixed topology and time-varying topologies are taken into consideration. For the case of fixed topology, we prove that the agents reach almost sure strong consensus as long as the network topology contains a spanning tree. For the case of time-varying topologies, under the assumption that each interaction topology is balanced and contains a spanning tree, we show that the agents reach almost sure strong consensus. Different from the most existing results concerning sampled-data control of multi-agent systems, it is shown that the convergence conditions are independent of the sampling period, which is due to the introduction of the step size.



---

*Source: 206408-2013-02-12.xml*