# Dynamic Average Consensus and Consensusability of General Linear Multiagent Systems with Random Packet Dropout

Authors: Wen-Min Zhou; Jiang-Wen Xiao
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

This paper is concerned with the consensus problem of general linear discrete-time multiagent systems (MASs) with random packet dropout that happens during information exchange between agents. The packet dropout phenomenon is characterized as being a Bernoulli random process. A distributed consensus protocol with weighted graph is proposed to address the packet dropout phenomenon. Through introducing a new disagreement vector, a new framework is established to solve the consensus problem. Based on the control theory, the perturbation argument, and the matrix theory, the necessary and sufficient condition for MASs to reach mean-square consensus is derived in terms of stability of an array of low-dimensional matrices. Moreover, mean-square consensusable conditions with regard to network topology and agent dynamic structure are also provided. Finally, the effectiveness of the theoretical results is demonstrated through an illustrative example.


---

## Body

## 1. Introduction

Multiagent systems (MASs) are kinds of networked systems in which each agent updates its states based on the information exchanges over communication networks. Due to their broad applications in many areas such as sensor networks [1], distributed computation [2], swarms and flocks [3], and formation control [4], the consensus problem of MASs has attracted increasing attention in recent years, and considerable interesting results have been obtained on this problem.At the beginning, the consensus problem is investigated mainly for first-order and second-order MASs. Olfati-Saber and Murray [5] studied the consensus problem for a network of first-order integrators under various topology conditions, including directed or undirected, fixed or switching, and with or without communication time-delays; Hatano and Mesbahi [6] studied the asymptotic agreement of first-order continuous MASs over random information network based on stochastic stability analysis; Zhang and Tian [7] investigated the MASs consisting of discrete-time second-order agents under stochastic switching topology and proved that MASs can achieve mean-square consensus if and only if the union graphs in the topology set are connected. Sun et al. [8] investigated the finite-time consensus for first- and second-order leader-following Multiagent systems. In [9], Lin et al. further studied the consensus problems of a class of high-order Multiagent systems with dynamically changing topologies and time-delays and proved that the communication time-delays do not affect the stability of the Multiagent systems.Recently, some researches on MASs with general linear dynamics have been conducted. Li et al. [10] proved that MASs with a communication topology having a spanning tree can reach consensus under an observe-type protocol if and only if each agent is stabilizable and detectable. Xu et al. [11] investigated the information structure for the consensusability of MASs under both fixed and switching topologies with dynamic output feedback control. In [12], Xu et al. further studied the leader-following consensus problem of discrete-time Multiagent systems with switching and undirected topology by applying two kinds of distributed observer-based consensus protocols to each agent. Su and Huang [13] proved that if the system matrix is marginally stable and the dynamic graph is jointly connected, both the leaderless and the leader-following consensus problems for linear discrete-time Multiagent systems under switching network topology can be solved.Note that most of the existing results on the consensus problem of MASs are derived from the assumption that the network communication environment is perfect. However, communication constraints which may deteriorate the performance of MASs are inevitable in practice. There are numerous studies focusing on the consensus problem for MASs with either communication time delay or presence of perturbation or both of them, such as [14–18], but as one of the main reasons for performance deterioration, packet dropout, which takes place frequently during the information exchange between agents, is not fully investigated. Therefore, it is of great significance to study the effect of packet dropout in MASs. Ren and Beard [19] studied the consensus problem for first-order continuous-time agents communicating via unreliable network through dynamically changing interaction topology method and proved that asymptotic consensus can be achieved if the union of the directed graph had a spanning tree frequently enough. Sun et al. [20] investigated the convergence and convergence speed for the second-order and the high-order discrete-time Multiagent systems with random networks and arbitrary weights. Zhang and Tian [21] investigated the mean-square consensus problem for continuous time second-order MASs disturbed by noise, variable delays, and occasional packet dropout and discussed the necessary and sufficient condition for mean-square robust consensusability. And in [22], Zhang and Tian further studied the consensus seeking problem for linear MASs, where each agent communicates via a weighted random lossy network and derived the maximum allowable loss probability.Motivated by the above analysis, this paper is concerned with consensus problem of general linear discrete-time MASs with random packet dropout that happens during the information exchange between agents, which, to the best of our knowledge, has not been fully investigated until now. The contribution of this paper lies in the following: first, a distributed consensus protocol with weighted graph is proposed to address the packet dropout phenomenon; second, through introducing a new disagreement vector, the dynamic average consensus problem is studied based on the established new framework; third, the necessary and sufficient condition for MASs to reach mean-square consensus is derived in terms of stability of an array of low-dimensional matrices, which is easier to be used in reality; moreover, mean-square consensusable conditions with regard to network topology and agent dynamic structure are also provided.The rest of this paper is organized as follows. In Section2, modeling construction of Multiagent systems with packet dropout is proposed, and some useful lemmas are introduced. In Section 3, a new framework is derived to address the consensus problem of MASs. The consensusable conditions with regard to network topology and agent dynamic structure are presented in Section 4. In Section 5, an illustrative example is provided to demonstrate the effectiveness of our results. Concluding remarks are drawn in Section 6.Notation.  ℝn and ℝm×n denote the n-dimensional Euclidean space and the set of m×n real matrix, respectively, and IN represents an  N-dimensional identity matrix. diag{·} refers to a diagonal matrix, or a block diagonal matrix. For matrices A and B, A>B implies that A and B are symmetric matrices and that A-B is positive definite. The superscript T and -1 mean transpose and inverse of a real matrix separately, and symbol * in a symmetric matrix implies a block that can be induced by symmetry. λmin(·), λmax(·) and ρ(·), denote, respectively, the smallest eigenvalue, the largest eigenvalue and the spectral radius of a matrix. Prob{·} stands for the occurrence probability of a stochastic event and Prob{·∣·} the conditional probability. E(·) is the mathematical expectation operator. ∥·∥ and ∥·∥1 stand the 2-norm and 1-norm respectively.


## 2. Problem Formulation and Preliminaries

Consider a system ofN agents with identical general linear dynamics. The dynamic equation of agent i is described by
(1)xi(k+1)=Axi(k)+Bui(k),i=1,2,…,N,
where xi=[xi1,xi2,…,xin]T∈Rn is the state variable, ui∈ℝm is the control input, and A∈ℝn×n and B∈ℝn×m are known constant matrices.Suppose that there is a predesigned undirected fixed topologyG which guarantees the effective communication between distinct nodes. This assumption is quite reasonable, since it is impossible to reach consensus under an unconnected topology. Denote Ni as the neighbor set of the node i and AG=[aij]∈RN×N as the weighted adjacency matrix of undirected graph G with aii=0, and for any i belongs to set Ni, aij=aji>0, otherwise, aij=aji=0.Under ideal communication environment, the commonly used linear distributed consensus protocol in MASs is as follows:(2)ui(k)=K∑j∈Ni‍aij(xj(k)-xi(k)),i=1,2,…,N,
where K∈ℝm×n is the gain matrix.As mentioned in Section1, packet dropout is inevitable in practical environment. In this paper, Bernoulli distributed white sequence {θij(k)} is introduced to model the unreliability of the link between agent i and agent j. At any given time instant k, for any j∈Ni, θij(k) takes value in the set {0,1}. Suppose that for any i,j∈{1,…,N}, θij(k) is mutually independent; that is, the packet dropout probability between each pair of agents is independent. When the packet is transmitted successfully between agent i and agent j, θij(k)=1; when packet dropout takes place between agent i and agent j, θij(k)=0, which can be described as
(3)θij(k)={0,withprobabilitypij,1,withprobability1-pij,
where pij is the occurrence probability of packet dropout between i and j, and for any j∉Ni, θij(k)≡0, pij≡1.Besides, due to the occurrence of packet dropout, the topology of MAS (1) is no longer fixed. Denote |Ni| as the number of agents in set Ni, S as the total number of the possible topologies. It is easy to see that S=2∑i=1N‍|Ni|/2; then the topology of the MAS is changing among the set {G1,…,GS}. Suppose that at certain time instant k, θij(k)=θijm and the network topology is Gm, then the occurrence probability of graph Gm, m=1,…,S, is
(4)πm=∏i=1,i<j(θijm(1-pij)+(1-θijm)pij).Based upon the above analysis, the following distributed consensus protocol is employed in this paper:(5)ui(k)=K∑j∈Ni‍θij(k)aij(xj(k)-xi(k)),i=1,…,N,
where K is the state feedback gain matrix to be designed.Substituting (5) into (1), the dynamic equation of agent i can be rewritten as
(6)xi(k+1)=Axi(k)+BK∑j∈Ni‍θij(k)aij(xj(k)-xi(k)).
Then, the states of MAS (1) evolve according to the following linear system:
(7)x(k+1)=(IN⊗A-Lσ(k)⊗(BK))x(k),
where x=[x1T,…,xNT]T, σ(·):Z+→{1,2,…,S} is a stochastic process driven by an i.i.d. process and Lσ(k)∈{Lm}, where Lm=[lijm]N×N, m=1,…,S, is the Laplacian matrix associated with Gm, with
(8)lijm={∑j=1Nθijmaij,i=j,-θijmaij,i≠j.
Obviously, the Laplacian matrix Lm is a symmetric matrix with zero row sum that is, ∀i≠j, lij=lji, and ∑j=1N‍lijm=0.Before presenting our main results, the concepts of mean-square stability and mean-square consensus are introduced first, and along with them are some useful lemmas which play significant roles in the derivation of our results.Definition 1 (see [23]).
A closed-loop system is said to be mean-square stable, if for anyɛ>0, there exists δ(ɛ)>0 such that for any k>0, E(∥x(k)∥2)<ɛ holds when E(∥x(0)∥2)<δ(ɛ). In addition, if limk→∞E(∥x(k)∥2)=0 for any initial condition, then the closed-loop system is said to be globally mean-square asymptotically stable.Definition 2.
Multiagent system (1) with protocol (5) is said to reach consensus in mean-square sense, if for any initial distribution and initial states, limk→∞E(∥xi(k)-xj(k)∥2)=0 holds for all i,j∈{1,…,N}. Furthermore, if there exists a proper state feedback gain matrix K such that the Multiagent system can achieve mean-square consensus, then we say that system (1) is mean-square consensusable under protocol (5).Lemma 3 (see [21]).
For any vectorz(k)∈ℝn, denote z¯(k):=E(z(k)⊗z(k)), then there is
(9)E(∥z(k)∥2)≤∥z¯(k)∥1≤nE(∥z(k)∥2).Lemma 4 (see [6]).
For an undirected graph withn vertices, the Laplacian is a positive-semidefinite symmetric matrix, and the spectrum of a graph Laplacian is on the form
(10)0=λ1(L)≤λ2(L)≤⋯≤λn-1(L)≤λn(L),
with λ2(L)>0 if and only if the graph that corresponds to L is connected.Lemma 5.
∑
m
=
1
S
‍
π
m
L
m has only one zero eigenvalue, if and only if the union graph of the topology set {G1,…,GS} is connected.Proof.
Since∑m=1S‍πmLm can be treated as a Laplacian matrix of a graph which has the same edges with the union graph of the topology set {G1,…,GS}, then together with Lemma 4, it can be obtained that Lemma 5 holds.Lemma 6 (see [24]).
For anyA∈ℝn×n, there exist orthogonal matrix U and an upper triangular matrix V, such that
(11)UTAU=V=[μ1v12⋯v1nμ2⋯v2n⋱⋮μn],
where μi, i=1,…,n, are the eigenvalues of matrix A.


## 3. Necessary and Sufficient Conditions for Mean-Square Consensus

Introduce the following variable:(12)δi(k)=xi(k)-1N∑j=1Nxj(k).Rewrite (12) in a compact form, which is
(13)δ(k)=(C⊗In)x(k),
where C=IN-(1/N)1→1→T and δ=[δ1T,…,δNT]T∈RNn is the so-called disagreement vector.It is easy to verify thatδ evolves according to the following disagreement dynamics:
(14)δ(k+1)=(IN⊗A-Lσ(k)⊗(BK))δ(k),
where δ(k) is defined in (7).SinceE(∥δ(k)∥2)=E(xT(k)(Q⊗In)x(k)), where Q=CTC=IN-(1/N)1→1→T, it is easy to verify that
(15)E(∥δ(k)∥2)=12N∑i≠jE(∥xj(k)-xi(k)∥2).Equation (15) implies that the mean-square consensus problem can be solved if and only if limk→∞E(∥δ(k)∥2)=0. From Definitions 1 and 2, it is easy to see that the consensus problem of MAS (1) is converted to the mean square stability analysis of system (14).Remark 7.
If the system matrixA is Schur stable, which means all eigenvalues of A are located in the unit circle, MAS (1) would definitely reach consensus without the design of consensus protocol, since under this condition, for any i∈{1,…,N}, xi will converge to zero, and limk→∞E(∥xi(k)-xj(k)∥2)=0 holds for sure. In view of this, we assume that not all eigenvalues of A are located in the unit circle.Theorem 8.
For any initial distribution and initial states, Multiagent system (1) with the Bernoulli packet dropout between agents can achieve mean-square consensus under protocol (1), if and only if
(16)ρ(A-λ^iBK)<1,
where λ^i, i=2,…,N, are the eigenvalues of matrix ∑m=1S‍πmLm except one zero eigenvalue.Proof.
Since for eachσ(k)=m, m=1,…,S, Lσ(k) is a symmetric matrix with zero row sum, and wT=(1/N)1→T and 1→ are, respectively, the left and right eigenvectors of Lσ(k) associated with zero eigenvalue, we can construct an invertible matrix T=[1→T1] with T-1=[wT2T]T, such that
(17)T-1Lσ(k)T=L¯σ(k)=[000L~σ(k)],
where T∈ℝN×N, T1∈ℝN×(N-1), T2∈ℝ(N-1)×N, and L~σ(k)=T2Lσ(k)T1∈R(N-1)×(N-1).
Introduce the following variable:φ(k)=(T-1⊗In)δ(k), where φ=[φ1T,…,φNT]T∈RNn; then (14) can be denoted in terms of φ as
(18)φ(k+1)=(IN⊗A-L¯σ(k)⊗(BK))φ(k).
Note thatφ1=(wT⊗In)δ≡0, which implies that state φ1 is always stable; thus, divide φ(k) into two parts; that is, φ(k)=[φ1T(k),φ^T(k)]T, with φ^=[φ2T,…,φNT]T, it can be derived from (17) and (18) that
(19)φ^(k+1)=A~σ(k)φ^(k),
where A~σ(k)=IN-1⊗A-L~σ(k)⊗(BK).
Similar to [21], let ξ(k)=E(φ~(k)⊗φ~(k)); then ξ(k) evolves according to
(20)ξ(k+1)=∑m=1Sπm(A~m⊗A~m)ξ(k).
From Lemma3, system (14) is mean-square stable if and only if system (20) is stable. Then, from the discrete-time system stability theory, it can be concluded that the necessary and sufficient condition for mean-square stability of (14) is ρ(∑m=1S‍πm(A~m⊗A~m))<1.
DenoteA~m=Φ-ΨmK with Φ=IN-1⊗A, Ψm=L~m⊗B, K=IN-1⊗K, and K=ɛK′; then there is ∑m=1S‍πm(A~m⊗A~m)=Φ⊗Φ-ɛ(∑m=1S‍πmΦ⊗(ΨmK′)+∑m=1S‍πm(ΨmK′)⊗Φ) + ɛ2∑m=1S‍πm(ΨmK′)⊗(ΨmK′). The above equation can be treated as a perturbation of Φ⊗Φ by two terms depending on ɛ. For small enough ɛ, the above formula is equal to ∑m=1S‍πm(A~m⊗A~m)=Φ⊗Φ-ɛ(∑m=1S‍πmΦ⊗(ΨmK′)+∑m=1S‍πm(ΨmK′)⊗Φ). Meanwhile, (∑m=1S‍πmA~m)⊗(∑m=1S‍πmA~m)=Φ⊗Φ-ɛ(∑m=1S‍πmΦ⊗(ΨmK′)+∑m=1S‍πm(ΨmK′)⊗Φ)+ɛ2∑m=1S‍(πmΨmK′)⊗(πmΨmK′). Likewise, by applying perturbation argument, for a small enough ɛ, ρ(∑m=1S‍πm(A~m⊗A~m))<1 is equivalent to
(21)ρ((∑m=1SπmA~m)⊗(∑m=1SπmA~m))<1.
Next, it will be proved that (21) holds if and only if (16) is satisfied.
It can be seen from (18) that ∑m=1S‍πmL~m has the same eigenvalue with ∑m=1S‍πmL¯m and ∑m=1S‍πmLm except one zero eigenvalue. Besides, based on Lemma 6, there exists an orthogonal matrix U∈R(N-1)×(N-1) such that
(22)UT(∑m=1S‍πmL~m)U=[λ^2*⋯*λ^3⋯*⋮λ^N],
where λ^i, i=2,…,N, are the eigenvalues of matrix ∑m=1S‍πmLm except one zero eigenvalue. It is easy to verify that ∑m=1S‍πmA~m=IN-1⊗A-∑m=1S‍πmL~m⊗(BK) is similar to
(23)[A-λ^2BK*⋯*A-λ^3BK⋯*⋱⋮A-λ^NBK].
Based on the matrix theory, matrix∑m=1S‍πmA~m has the same eigenvalue with matrix (23), obviously ρ(∑m=1S‍πmA~m)<1, if and only if (16) is satisfied. Then, together with the properties of the Kronecker product, it is safe to say that (21) holds if and only if (16) is satisfied, which completes the proof.Remark 9.
The contribution of Theorem8 lies in the fact that it converts the consensus problem of MAS (1) into a set of matrices with the same dimensions as a single agent, which reduces the computational complexity greatly. Besides, while in most of the existing results each agent is guaranteed to achieve consensus with agent 1, see [7, 11, 21] for example, or to achieve average consensus, see [5], for example, in this paper a new disagreement vector is introduced to solve the consensus problem so that each agent will reach consensus on the average states of all agents, that is, dynamic average consensus.


## 4. Consensusability Analysis

Theorem8 presents the numerical solution to consensus problem, which also implies the design method of consensus protocol. However, in practice, we are equally interested in that under what conditions MAS (1) has the ability to reach consensus and inequality (16) has a solution at the same time, that is, what are the consensusable conditions? In this section, we focus on addressing this problem.Theorem 10.
Multiagent system (1) with the Bernoulli packet dropout between agents can achieve mean-square consensus under protocol (5), if and only if the union graph of the topology set {G1,…,GS} is connected, and (A,B) is stabilizable.Proof.
Necessity: defineE(Lσ(k))=∑m=1S‍πmLm as the expected Laplacian matrix and its corresponding graph as the expected graph. Since E(Lσ(k)) is a symmetric matrix, there exists an invertible matrix T^=[1→F^] with T^-1=[wE^T]T, such that
(24)T^-1E(Lσ(k))T^=Λ=[000Δ^],
where T^∈ℝN×N, F^∈ℝN×(N-1), E^∈ℝ(N-1)×N, wT, which is defined in (18), is also the left eigenvalue of E(Lσ(k)) associated with zero eigenvalue, and Δ^∈R(N-1)×(N-1) is a diagonal matrix with its diagonal elements being λ^i, i=2,…,N.
Denoteϕ(k)=E(δ(k)); then ϕ(k) evolves according to
(25)ϕ(k+1)=(IN⊗A-E(Lσ(k))⊗(BK))ϕ(k),
where ϕ=[ϕ1T,…,ϕNT]T∈RNn.
Similar to the proof in Theorem8, introduce the following variable transformation: ζ(k)=(T~-1⊗In)ϕ(k); then the dynamic equation of ζ(k) can be written as
(26)ζ(k+1)=(IN⊗A-Λ⊗(BK))ζ(k),
where ζ=[ζ1T,…,ζNT]T∈RNn.
Notice thatζ1(k)=(w~T⊗IN)E(δ(k))≡0, divide ζ(k)=(w~T⊗IN)E(δ(k))≡0 into two parts, that is, ζ(k)=[ζ1T(k),ζ~T(k)]T, from (19) and (21), it can be derived that
(27)ζ~(k+1)=[A-λ^2BK0⋯0A-λ^3BK⋯0⋱⋮A-λ^NBK]ζ~(k).
If the union graph of the topology set{G1,…,GS} is not connected, the expected graph is definitely not connected. It can be obtained from Lemma 3 that 0=λ^2≤λ^3≤⋯≤λ^N. Due to the fact that not all eigenvalues of A are located in the unit circle, there exists an initial state such that limk→∞ζ(k)≠0 and limk→∞E(δ(k))≠0 thus; system (14) is not mean-square stable since E(∥δ(k)∥2)≥∥E(δ(k))∥2, and consequently, Multiagent system (1) cannot achieve mean-square consensus.
Besides, if(A,B) is unstabilizable, it is impossible to guarantee that ρ(A-λ^iBK)<1, i=2,…,N, even if the topology condition is satisfied, and system (27) is still not guaranteed to be stable.
Sufficiency: It can be derived from Lemma5 that when the union of the graphs in the topology set is connected, all eigenvalues of ∑m=1S‍πmL~m are positive; that is, λ^i>0, i=2,…,N. Therefore, when the union graph of the topology set {G1,…,GS} is connected and (A,B) is stablizable, there exists a proper gain matrix K such that ρ(A-λ^iBK)<1, i=2,…,N. The proof is completed.Remark 11.
In [21], for two-order continuous-time MASs with A=[0100], B=[01], which implies that (A,B) is stablizable, Zhang and Tian prove that the MAS can reach mean-square consensus if and only if the union graph is connected, while in this paper, it is verified theoretically that the stabilizability of (A,B) is essential for achieving consensus.


## 5. Numerical Simulation

Consider an MAS consisted of four agents, with its prior fixed weighted communication topology beingN1={2}, N2={1,3}, N3={2,4}, N4={3}, a12=2, a23=2, a34=3; then there are eight graphs in the topology set {G1,…,G8}. Assume that the packet dropout probability between each pair of agents is 0.1.Each agent is described by a three-order difference equation, with(28)A=[0.600.20.30.30.4001.2],B=[001].
Obviously, each agent is unstable since the eigenvalues of A are 0.6, 0.3, and 1.2, and (A,B) is stablizable. By applying Theorem 8, it can be obtained that K=[0.1111-0.00000.1944], such that ρ(A-λ^iBK)=0.8910<1. Suppose the initial conditions are x10=[232]T, x20=[21-1]T, x30=[1-2-3]T, and x40=[-12-2]T; the simulation results are shown in Figure 1.Figure 1
The disagreement values between agents under consensus protocol (5).


## 6. Conclusion

We have studied the consensus problem of general linear discrete-time Multiagent systems (MASs) with random packet dropout that happens during information exchange between agents. The packet dropout phenomenon is characterized as being a Bernoulli random process. A distributed consensus protocol with weighted graph is proposed to address the packet dropout phenomenon. By constructing a new disagreement vector, a new framework is established to solve the consensus problem. Then, through introducing a common linear transformation for the switching system, together with the control theory, the perturbation argument, and the matrix theory, the necessary and sufficient condition for MASs to reach mean-square consensus is derived in terms of stability of an array of low-dimensional matrices. Moreover, mean-square consensusable conditions with regard to network topology and agent dynamic structure are also provided.It is worth pointing out that this paper is only a first step; the consensus problem of linear discrete time MASs, which may be affected by many other factors including time-delay, and noise, is not fully investigated, and this is of our research interest in the future.



---

*Source: 412189-2013-09-30.xml*