{'fraction_non_alphanumeric': 0.055866391821967946, 'fraction_numerical': 0.017836860039543982, 'mean_word_length': 4.141003460207613, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Consensus over Markovian Packet Loss Channels

This paper studies the consensusability problem of multi-agent systems (MASs), where agents communicate with each other through Markovian packet loss channels. We try to determine conditions under which there exists a linear distributed consensus controller such that the MAS can achieve mean square consensus. We first provide a necessary and sufficient consensus condition for MASs with single input and i.i.d.\ channel losses, which complements existing results. Then we proceed to study the case with identical Markovian packet losses. A necessary and sufficient consensus condition is firstly derived based on the stability of Markov jump linear systems. Then a numerically verifiable consensus criterion in terms of the feasibility of linear matrix inequalities (LMIs) is proposed. Furthermore, analytic sufficient conditions and necessary conditions for mean square consensusability are provided for general MASs. The case with nonidentical packet loss is studied subsequently. The necessary and sufficient consensus condition and a sufficient consensus condition in terms of LMIs are proposed. In the end, numerical simulations are conducted to verify the derived results.


I. INTRODUCTION
The rapid development of technology has enabled wide applications of multi-agent systems (MASs). The consensus problem, which requires all agents to agree on certain quantity of common interests, builds the foundation of other cooperative tasks. One question arises before control synthesis: whether there exist distributed controllers such that the MAS can achieve consensus. This problem is referred to as consensusability of MASs. Previously, the consensusability problem with perfect communication channels has been well studied under an undirected/directed communication topology [1], [2], [3], [4], [5]. In [1], it is shown that to ensure the consensus of a continuous-time linear MAS, the linear agent dynamics should be stabilizable and detectable, and the undirected communication topology should be connected. Furthermore, references [2], [3] show that for a discretetime linear MAS, the product of the unstable eigenvalues of the agent system matrix should additionally be upper bounded by a function of the eigen-ratio of the undirected graph. Extensions to directed graphs and robust consensus can be found in [4], [5].
Most of the consensusability results discussed above are derived under perfect communications assumptions. However, this is not the case in practical applications, where communication channels naturally suffer from limited data rate constraints, signal-to-noise ratio constraints, time-delay and so on. Therefore, the consensusability problem of MASs under communication channel constraints has been widely studied in [6], [7], [8], [9], [10], [11] under different channel models. In this paper, we are interested in the lossy channel [12], [13], [14], which models the packet drop phenomenon in wireless communications due to the communication noise, interference or congestion. Previously, the case with independent and identically distributed (i.i.d.) channel fading has been studied in [9]. However, the i.i.d. assumption fails to capture the correlation of channel conditions over time. Since Markov models are simple and effective in capturing temporal correlations of channel conditions [15], [16], we are interested in the consensusability problem of MASs over Markovian packet loss channels. Due to the existence of correlations of packet losses over time, the methods used to deal with the i.i.d. Liang Xu, Yilin Mo and Lihua Xie are with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798, Singapore. Email:lxu006@e.ntu.edu.sg, {ylmo, elhxie}@ntu.edu.sg channel state in [9] cannot be applied directly to the Markovian channel loss case.
This paper studies the consensusability problem of MASs over packet loss channels. The contributions are listed as follows. A necessary and sufficient consensus condition for MASs with single input and identical i.i.d. channel losses is firstly derived, which complements existing results and explicitly demonstrates how the network topology, the agent dynamics and the packet loss interplay with each other in the consensus problem. For the consensus with identical Markovian packet loss: 1, a necessary and sufficient consensusability condition is provided; 2, a numerically testable criterion and analytical sufficient and necessary consensusability conditions are derived; 3, a critical consensusability condition is obtained for the special case of scalar agent dynamics. For the consensus with nonidentical Markovian packet loss, sufficient and necessary consensus conditions are also derived by introducing the edge Laplacian.
Some preliminaries results on distributed consensus over identical Markovian packet loss channels are contained in [17]. This paper contains new results for the case of MASs with single input and identical i.i.d. packet losses, and for distributed consensus with nonidentical Markovian packet loss. This paper is organized as follows: The problem formulation is stated in Section II. The consensusability results for MASs with single input and identical i.i.d. channel losses are presented in Section III. The consensusability results for the cases with identical Markovian and nonidentical Markovian packet losses are discussed in Section IV and Section V, respectively. Numerical simulations are provided in Section VI. This paper ends with some concluding remarks in Section VII.
Notation: All matrices and vectors are assumed to be of appropriate dimensions that are clear from the context. R, R n , R m×n represent the sets of real scalars, n-dimensional real column vectors and m×ndimensional real matrices, respectively. 1 denotes a column vector of ones. I represents the identity matrix. A , A −1 , ρ(A) and det(A) are the transpose, the inverse, the spectral radius and the determinant of matrix A, respectively. ⊗ represents the Kronecker product. For a symmetric matrix A, A ≥ 0 (A > 0) means that matrix A is positive semi-definite (definite). For a symmetric matrix A, λmin(A) denotes the smallest eigenvalue of A. diag(A, B) denotes a diagonal matrix with diagonal entries A and B. E{·} denotes the expectation operator. The symmetric

II. PROBLEM FORMULATION
Let V = {1, 2, . . . , N } be the set of N agents with i ∈ V representing the i-th agent. A graph G = (V, E) is used to describe the interaction among agents, where E ⊆ V × V denotes the edge set with paired agents. We assume G is undirected throughout this paper. An edge (j, i) ∈ E means that the i-th agent and the j-th agent can communicate each other. The neighborhood set Ni of agent i is defined as Ni = {j |(j, i) ∈ E}. The graph Laplacian matrix L = [Lij] N ×N is defined as Lii = j∈N i aij, Lij = −aij for i = j, where aii = 0, aij = 1 if (j, i) ∈ E and aij = 0, otherwise. A path on G from agent i1 to agent i l is a sequence of ordered edges in the form of (i k , i k+1 ) ∈ E, k = 1, 2, . . . , l − 1. A graph is connected if there is a path between every pair of distinct nodes. arXiv:1810.03314v1 [math.OC] 8 Oct 2018 In this paper, we assume that each agent has the homogeneous dynamics where xi ∈ R n is the system state; ui ∈ R m is the control input; (A, B) is controllable and B has full-column rank. The interaction among agents is characterized by an undirected connected graph G = {V, E}. The consensus protocol is given by where γij(t) ∈ {0, 1} models the lossy effect of the communication channel from agent j to agent i, which satisfies that γij(t) = 1 when the transmission is successful at time t, and 0 otherwise. Throughout the paper, we say that the MAS (1) is mean square consensusable by the protocol (2) if there exists K such that the MAS (1) can achieve mean square consensus under the protocol (2), i.e., limt→∞ E xi(t) − xj(t) 2 = 0 for all i, j ∈ V. The following assumption is made as in [2]. In this section, we consider the special case that the agent is with single input, i.e., ui ∈ R and the packet loss processes for all channels are identical and i.i.d., which has been studied in [9]. We provide a necessary and sufficient condition to guarantee the mean square consensus, which complements existing results in [9], where only the sufficiency is proved. Specifically, we make the following assumption about the packet loss process. Assumption 2. γij(t) = γ(t) for all (i, j) ∈ E and t ≥ 0. Moreover, the sequence {γ(t)} t≥0 is i.i.d. and γ(t) has a Bernoulli distribution with lossy rate p.
Define the consensus error as δ(t) = (I − 1 N 11 )x(t), where x(t) = [x1(t) , . . . , xN (t) ] . Following similar derivations as in [9], the consensus error dynamics is given by where L is the graph Laplacian of G. If there exists K such that system (3) is mean square stable, i.e., limt→∞ E {δ(t)δ(t) } = 0, the MAS can achieve mean square consensus. It has been proved in [9] that the mean square stability of (3) is equivalent to the simultaneous mean square stability of where λi is the nonzero positive eigenvalues of L with λ2 ≤ · · · ≤ λN . The following lemmas are needed in the proof of the main result and stated first.
Lemma 3. Let P > 0. Suppose there exists a vector v, such that v P v > φ 2 and φ > 0, then there exists a vector x, such that the following inequalities hold Proof. Let us choose x = αP v, then Since v P v > φ 2 , we can choose α, such that The proof is completed.
Lemma 4. Suppose that det(A) = 0, then any P > 0 that satisfies must also satisfy Proof. We prove this lemma by contradiction. Let Suppose that there exists a P > 0 to (5), such that Therefore, by Lemma 3, there exists a K, such that and where By Schur complement lemma and the fact that B P B > 0, (7) is equivalent to or P > (A + BK) P (A + BK). Therefore, K is stabilizing, i.e., A+BK is strictly stable. By matrix determinant lemma, if A+BK is stable, then | det(A+BK)| = | det A||1+KA −1 B| < 1. Therefore, On the other hand, by the definition of K * , we have Then, we have from (8) that which contradicts with (9). Therefore, any P > 0 that satisfies (5), must also satisfy (6). The proof is completed.
The main result is stated as follows.
Proof. The sufficiency follows from Theorem 1 in [9]. Only the necessity is proved here, which follows from the simultaneous mean square stability of (4). Let µ and σ 2 be the mean and variance of γ(t), respectively, then we have µ = 1 − p and σ 2 = p(1 − p).
In view of Lemma 1 in [18], (4) is mean square stable for i.i.d. {γ(t)} t≥0 if and only if there exist Pi > 0, i = 2, . . . , N and K, such that for all i = 2, . . . , N . With some manipulations, we can show that Left and right multiply the above inequality with B (A ) −1 and A −1 B, we can obtain that Since Pi satisfies (5), we have from Lemma 4 that Therefore we have from (11) that with Since there exists a common KA −1 B , such that (12) holds for all i = 2, . . . , N . ∩i β i , β i must be non-empty, which implies β 2 < β N . Further calculation shows that Substituting the definitions of µ, σ 2 and a0, we can obtain (10). The proof is completed.
Furthermore, in view of the above derivations, we have the following consensusability condition for the general fading case studied in [9].

IV. IDENTICAL MARKOVIAN PACKET LOSS
In the section, we consider a more general case that ui is a R m vector with m ≥ 1 and γ(t) is a Markov process and make the following assumption.
Remark 8. Markov models are widely used to capturing temporal correlations of channel conditions [15], [16]. However, due to the correlations of packet losses over time, the methods used to deal with the i.i.d. channel fading in [9] cannot be applied to the Markovian packet loss case.
Since {γ(t)} t≥0 is a Markov process, the consensusability is equivalent to the simultaneous mean square stabilizability of the N −1 Markov jump linear systems (4). In view of Theorem 3.9 in [19] describing the stability of Markov jump linear systems, we can obtain the following consensusability condition.
2) There exists K such that ρ (Hi) < 1, With similar transformations as in the proof of Theorem 10, the consensus criterion in Theorem 9.1) can be shown to be equivalent to a feasibility problem with bilinear matrix inequality (BMI) constraints. It is well known that checking the solvability of a BMI, is generally NP-hard [20]. Therefore, in the sequel, we propose a sufficient consensus condition in terms of the feasibility of linear matrix inequalities (LMIs) by a fixed Pi,1 and Pi,2.
In view of the above result and (19) (20), we have, Since −c = min k maxi(λ 2 i k 2 + 2λik) and the optimal k to the minmax problem isǩ = − 2 λ 2 +λ N , we know that hold for all i = 2, . . . , N . Therefore Theorem 9.1) is satisfied with The proof is completed.

A. Analytic Consensus Conditions
The criterion stated in Theorem 10 is easy to verify. However, it fails to provide insights into the consensusability problem. In the following, we provide analytical consensusability conditions, which show directly how the channel properties, the network topology and the agent dynamics interplay with each other to allow the existence of a distributed consensus controller. The following lemma is needed in proving the main result and is stated first.

Lemma 11 ([21]). Under Assumption 1, if (A, B) is controllable, then
admits a solution P > 0, if and only if γ is greater than a critical value γc > 0.

Remark 12.
The value γc is of great importance in determining the critical lossy probability in Kalman filtering over intermittent channels [12], [21], [22]. It has been shown that the critical value γc is only determined by the pair (A, B) [22]. However, an explicit expression of γc is only available for some specific situations. For example, when rank(B) = 1, γc = 1 − where γc is given in Lemma 11. Moreover, if (24) holds, an admissible control gain is given by where P is the solution to (23) with γ = γ1.
Remark 14. Theorem 10 is obtained by letting Pi,1 = P1, Pi,2 = P2. Theorem 13 is obtained by letting Pi,1 = Pi,2 = P . Since the latter is more restrictive than the former. We can expect that Theorem 13 is more restrictive than Theorem 10, which will be illustrated by a simulation example in the next subsection.
In conjunction with the analytic sufficient consensusability condition in Theorem 13, we also provide an explicit necessary consensusability condition as stated below.
Theorem 15. Under Assumption 1 and 7, the MAS (1) is mean square consensusable by the protocol (2) only if there exists K such that for all i = 2, . . . , N . Moreover, when the agent is with single input, i.e., m = 1, the MAS (1) is mean square consensusable by the protocol (2) only if Proof. If the MAS can achieve mean square consensus, in view of Theorem 9.1), we have that there exist Pi,1 > 0, Pi,2 > 0 and K such that for all i = 2, . . . , N . Further from Lyapunov stability theory, we can obtain the necessary conditions (25), (26). When the agent is with single input, following similar line of argument as in the necessity proof of Lemma 3.1 in [2], we can obtain the necessary condition (28) from (26). The proof is completed.

B. Critical Consensus Condition for Scalar Agent Dynamics
When all the agents are with scalar dynamics, we can obtain a closed-form consensusability condition. The following lemma is needed in the proof of the main result and is stated first. (14); D = [ 1 0 0 δ ] with 0 < q, p, δ < 1; λ ∈ R, |λ| ≥ 1. The following conditions are equivalent:

1)
Without loss of generality, for scalar agent dynamics, i.e., n = m = 1, we let A = a ∈ R, B = 1, K = k ∈ R. The main result is stated as follows.
Proof. In view of Theorem 9.2), for scalar agent dynamics, the MAS (1) is mean square consensusable by the protocol (2) if and only if there exists k such that for all i = 2, . . . , N . Further from Lemma 16, a necessary and sufficient consensus condition is that if there exists k such that for all i = 2, . . . , N .
Since (34) holds for all i, we have that Moreover, since we can obtain the necessary and sufficient consensusability condition (31), (32) from (33), (34). The proof is completed.
Interestingly, we can show that when the agent dynamics is scalar, the sufficient condition indicated in Theorem 10 is also necessary. Theorem 10 is equivalent to check the solvability of (21) and (22). For scalar systems with A = a ∈ R, B = 1, (21) and (22) change to We can show that the necessary and sufficient condition to guarantee the solvability of the above inequality is given by (31)  . We can obtain a lower bound of P1 from (35) and substitute this bound into (36) to obtain .
Since P2 > 0, we further have that which implies Dividing both sides by 1 − a 2 (1 − q), we can obtain (32). In contrast to the tightness of Theorem 10 for scalar systems, Theorem 13 is generally not necessary. Consider the case that A = 2, B = 1, λ2 = 2 and λN = 3, then the tolerable (p, q) from Theorem 17 are given by While the sufficiency indicated by Theorem 13, is given by The tolerable failure rate and recovery rate are plotted in Fig. 1. It is clear that the result in Theorem 13 is conservative in the case of scalar agent dynamics.
The assumption of identical channel loss distributions is somewhat restrictive and less practical. However, it is the simplest case in studying the consensus problem over Markovian packet loss channels and is expected to shed light on solutions to more general nonidentical cases, which is studied in the subsequent section.

V. NONIDENTICAL MARKOVIAN PACKET LOSS
In the presence of nonidentical packet losses, the consensus error dynamics of δ is given by δ(t + 1) = (I ⊗ A + L(t) ⊗ BK) δ(t) with L(t) modeling both the communication topology and the packet losses. Since the packet loss is coupled with the communication topology in L(t), the analysis of the mean square consensus is difficult. Therefore, the edge Laplaican [24] is used to model the consensus error dynamics as in [9], which allows to separate the lossy effect from the network topology to facilitate the consensusability analysis by building dynamics on edges rather than on vertexes.
The following graph definitions are needed in introducing the edge Laplacian. A virtual orientation of the edge in an undirected graph is an assignment of directions to the edge (i, j) such that one vertex is chosen to be the initial node and the other to be the terminal node. The incidence matrix E for an oriented graph G is a {0, 1, −1}matrix with rows and columns indexed by vertices and edges of G, respectively, such that The graph Laplacian L and edge Laplacian Le can be constructed from the incidence matrix respectively as L = EE , Le = E E [24].
Define the state on the i-th edge as zi = xj − x k , with j, k representing the initial node and the terminal node of the ith edge, respectively. Assume that the packet losses on the same edge are equal, i.e., γ jk = γ kj , which make sense in practical applications [25]. Following the definition of incidence matrix, the controller (2) can be alternatively represented as where l is the total number of edges in G, e jk is the jk-th element of E and ζ k denotes the packet loss effect on the k-th edge, i.e., ζ k = γij where i, j are the initial node and terminal node of the k-the edge. If we define z = [z 1 , z 2 , . . . , z l ] , then following similar steps as in [9], the closed-loop dynamics on edges can be calculated as with ζ(t) = diag(ζ1(t), ζ2(t), . . . , ζ l (t)).
With appropriate indexing of edges, we can write the incidence matrix E as E = [Eτ , Ec], where edges in Eτ are on a spanning tree and edges in Ec complete cycles in G. We further have that when G is connected, there exists a matrix T , such that Ec = Eτ T [24]. Moreover, with such indexing of edges, we can decompose the edge state z as z = [z τ , z c ] , where zτ is the edge state on the spanning tree and zc is the remaining edge state. Besides, it is straightforward to verify that zc = (T ⊗ I)zτ , since z = [z τ , z c ] = (E ⊗ I)x = ([Eτ , Ec] ⊗ I)x and Ec = Eτ T . Let M = E τ E and R = [I, T ], we have that Remark 19. It is possible that certain outcomes in Φ are unlikely to happen. For example, if two agents are close to each other, the communication between them can be reliable. It is unlikely that the communication link would undergo packet losses. In such cases, the sample space of ζ(t) would be a subset of Φ. Therefore, in Assumption 18, we use o to denote the carnality of the actual sample space of ζ(t), which might be smaller than 2 l . Therefore (38) is a Markov jump linear system. In view of Theorem 3.9 in [19], we have the following consensus result. We can show that the consensus criterion in Theorem 20.1) is equivalent to a feasibility problem with BMI constraints. Therefore, checking the conditions in Theorem 20 are generally not easy. In the following a numerically easy testable condition in terms of the feasibility of LMIs are proposed. Proof. If (39) holds, there exists κ such that κNi + κ 2 Mi < −γcI for all i = 1, . . . , o. Since κNi + κ 2 Mi is real and symmetric, it is diagonalizable by an orthogonal matrix Ψ, i.e., Ψ (κNi +κ 2 Mi)Ψ = Υ and Υ is diagonal. Then we have that Υ < −γcI. In view of Lemma 11, we can find P > 0 such that Left and right multiply the above inequality with Ψ ⊗ I and Ψ ⊗ I, we have that I ⊗ P > I ⊗ A P A + (κNi + κ 2 Mi) ⊗ A P B(B P B) −1 B P A. Remark 22. This paper only discusses the consensusability problem over undirected graphs. For the consensusability problem with directed graphs, the compressed edge Laplacian proposed in [26] can be used to model the consensus error dynamics. Then following similar derivations as in this section, consensus conditions over directed graphs in the presence Markovian packet losses can be obtained.

VI. NUMERICAL SIMULATIONS
In this section, simulations are conducted to verify the derived results. In simulations, agents are assumed to have system parameters The initial state of each agent is uniformly and randomly generated from the interval (0, 0.5). We assume that there are four agents and the undirected communication topology among agents is given in The simulation results are presented by averaging over 1000 runs. Mean square consensus errors for agent 1 are plotted in Fig. 3, which shows that the mean square consensus is achieved. Secondly, we consider the consensus over nonidentical Markovian packet loss networks. We index the edges and apply a virtual orientation to each edge as in Fig. 2.(ii). Denote the packet loss processes in these edges as ζ1(t), ζ2(t), ζ3(t), ζ4(t). Suppose the timehomogeneous Markov packet loss process {ζ(t)} t≥0 with ζ(t) = diag(ζ1(t), ζ2(t), ζ3(t), ζ4(t)) has three states Γ1 = diag(1, 0, 1, 0), Γ2 = diag(0, 1, 0, 1), Γ3 = diag(1, 1, 1, 1) and is with the probability transition matrix With such settings, we can show that (39) is feasible, and an admissible control gain is given by The simulation results are presented by averaging over 1000 runs. The consensus error for agent 1 is given below, which shows that the mean square consensus is achieved.

VII. CONCLUSIONS
This paper studies the mean square consensusability problem of MASs over Markovian packet loss channels. Necessary and sufficient consensus conditions are derived under various situations. The derived results show how the agent dynamics, the network topology and the channel loss interplay with each other to allow the existence of a linear distributed consensus controller. Analytic consensus conditions are only provided for consensus with identical Markovian packet losses. The case with nonidentical Markovian packet losses deserves more effort.