# Asynchronous Communication under Reliable and Unreliable Network Topologies in Distributed Multiagent Systems: A Robust Technique for Computing Average Consensus

Authors: Ali Mustafa; Muhammad Najam ul Islam; Salman Ahmed; Muhammad Ahsan Tufail
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Nearly all applications in multiagent systems demand precision, robustness, consistency, and rapid convergence in designing of distributed consensus algorithms. Keeping this thing in our sight, this research suggests a robust consensus protocol for distributed multiagent networks, continuing asynchronous communications, where agent’s states values are updated at diverse interval of time. This paper presents an asynchronous communication for both reliable and unreliable network topologies. The primary goal is to delineate local control inputs to attain time synchronization by processing the update information received by the agents associated in a communication topology. Additionally in order to accomplish the robust convergence, modelling of convergence analysis is conceded by commissioning the basic principles of graph and matrix theory alongside the suitable lemmas. Moreover, statistical examples presenting four diverse scenarios are provided in the end; produced results are the recognisable indicator to authenticate the robust effectiveness of the proposed algorithm. Likewise, a simulation comparison of the projected algorithm with the other existing approaches is conducted, considering different performance parameters are being carried out to support our claim.


---

## Body

## 1. Introduction

Multiagent systems can be defined as a system that is distributed in nature; multiple agents in a network communicate with each other with their limited resources to achieve their local and global goal in a cooperative manner. It is important to mention here that agents are intelligent nodes and have some degree of independence to take their decisions to achieve their desired goals. Such coordination in multiagent system is referred to as a consensus, and it is considered as one the fundamental research activities in distributed control strategy. Study of multiagent systems attracted scientists and researchers from diverse fields of control theory, applied mathematical modelling, computer sciences, engineering, and so on to study the significance of distributed control of agents in a network, as distributed multiagents systems gain a lot of significance in various real time applications such as flocking [1–4], wireless sensor networks (WSN) [5, 6], coordination control of robots [7, 8], underwater vehicles, unmanned aerial vehicles [9, 10], intelligent transportation systems [11], robotics [12], formation control [13, 14], balancing of load in parallel computers [15], and intelligent decentralized mechanism for smart grids [16, 17].Consensus problem was first investigated in late 1960s in the modelling of statistical theory and management science [18]. Moreover in the fields of control system theory, consensus problem was initially discussed by [19]. Computer sciences problem focusing on animal aggregation through consensus control is studied by the author in [20]. In latest research horizons of consensus control is pioneered by Olfati-Saber and Murray; they utilize the concepts of graph and matrix theories along with the different network topologies with directed and undirected graph connectivity [21, 22]. Later on authors in [23] implement the consensus control for dynamically changing topologies. Moreover, consensus in switching network topologies is addressed by [24, 25], filter designing for consensus is addressed by [26], optimized solution for large scale industry using distributed consensus algorithm is proposed by the authors in [27], and Kalman filtering design for distributed consensus approach is initially addressed in [28]. Impulsive control as an important mechanism is highlighted in [29]. Time synchronized algorithms for various application are discussed by authors in [30–32]. Likewise, concept of asynchronous consensus under different network environments is presented by authors in [33, 34].After concisely discussing various theories and the existing approaches, we are suggesting a new control mechanism for attaining robust average consensus for asynchronous communication in distributed multiagent network centred on discrete time information sharing among the neighbours within the communication network. Practically such networks may suffer communication delays, information loss, broken communication links, unreliable switching network topology, and limitation in channel capacity. So in our proposed solution, we are considering resource constrained intelligent agents with limited communication abilities and also simulated the proposed network control mechanism under both reliable and unreliable random network topologies. Most importantly as mentioned above it is asynchronous in nature, which means that each agent communicating in a network is adjusting its dynamics independently with respect to other neighbouring agents. In proposed scheme starting time of each agent is common but the update time of each agent in a network is assigned randomly; in other words we can say update time of each agent is asynchronous and depending on upper and lower bound of the time. For designing of the proposed control algorithm we used the key concepts from the theory of graph and nonnegative matrix along with state space model to prove the convergence conditions. Proposed algorithm is compared with other existing protocols with a synchronous communication in four different scenarios under reliable and unreliable network topologies and results are compared it a tabular form consisting of various performance parameters. Structure of the paper is organised as follows. Key concepts from the matrix theory and algebraic graph theory are presented in Section2, convergence analysis is proved in Section 3, and Section 4 is enriched with the proposed control algorithm. Numerical simulation and comparison analysis of performance parameters are presented in Section 5. Section 6 is devoted for concluding remarks.


## 2. Preliminaries from Algebraic Graph and Matrix Theory

Algebraic graph theory and nonnegative matrix theory are considered as a preliminary tool for designing and convergence analysis in distributed algorithms in multiagent systems. In this segment significant fundamental concepts are concisely deliberated to enhance the understanding of the projected investigation.In algebraic graph theory, graph is fundamentally a group of linked agents communicating with each other through communication links. Mathematically it can be represented asG=(V,E). Agents set in a graph are called vertex set and they can be written as V=v1,v2,…,vn, where 1,2,n are the number of agents in a graph. Moreover, connection links between vertices are referred to as an edge set E = (i,j). Graph can be classified into two types, directed graph and undirected graph. In directed communication between the agents is one way (i,j) demonstrating data flowing from jth vertex to ith and vice versa. Similarly in undirected graph the communication between vertices is bidirectional. Furthermore, edge set consists of order pairs of vertices representing the information flow. Directly connected vertices which are directly communicating with each other through edges are known as neighbour and algebraically notated as Ni for agent i. In graph theory connectivity of the agents in a network is represented by n∗n matrix, known as adjacency matrix A=[aij]. Degree matrix D=dij delivers the information about the total neighbours connected with any agent in a communication network. Additionally if one vertex in a network has the direct path to all the vertices in a network, then the connectivity graph is supposed to procedure a spanning tree. Spanning tree is considered as one vital convergence condition for consensus in reliable communication but not considerably enough for the systems with time varying delays [35]. If edges in a graph have weights then the matrix is called weighted matrix and summation of the weights coming towards the vertex is called in-degree and alike sum of outward weight is said to be out-degree [36, 37]. Few other matrices which are considered to be of prime importance in convergence analysis for the distributed consensus algorithms are named Laplacian matrix L=D-A, rank 1 matrix, stochastic matrix P, and SIA matrix [38].Furthermore, when designing the weighting matrixβ to validate the convergence condition towards a targeted value, then there are multiple approaches available to design such matrices. Local degree weight matrix is one of the popular methodologies, which states that the highest out-degree of any two incident agents is assigned as weight on each edge [39]. It is significant to mention here that it is compulsory that each agent in a network must possesses the knowledge of out-degrees of all of its neighbors. Mathematically we can express (1)βijtki=1max⁡ditki,djtkii≠j0otherwise.Similarly one of the popular techniques is for designing weigh matrix as metropolis hasting weights. It can be defined as the fact that all agents must know the out-degree of all of its neighbors but it is essential to mention here that the graph topology is changing at all instants of time. It can be algebraically expressed as [40, 41](2)βijtki=1max⁡ditki,djtki+1i≠j0otherwise.Moreover, while in designing process of distributed consensus algorithm, some useful lemmas and facts from the theory of controls play a very significant role to produce desire results to achieve convergence.Lemma 1.
Assume a collection of stochastic matricesZ1,Z2,…,Zn. The final graph which is produced after performing the union operation of all the graphs in matrices set GZ1,GZ2,…,G(Zn) must possess the spanning tree; afterwards the produced matrix outcome ZnZn-1⋯Z1 is called a SIA matrix [23].Lemma 2.
Stochastic matrixZ is supposed to be a SIA, if and only if a spanning tree in G(Z) is present [42].


## 3. Convergence Condition

This section will deal with the convergence analysis of the proposed algorithm based on the given below distributed iteration:(3)zitki+1=βiitkizitki+∑jϵNiβijtkizjtki;where i ranges between i=1,2,3,…,n, and similarly tki=0,1,2,….β i j is the weight on zj at agent i, where βii=(1-∑jϵNiβij). By assigning βij=0 for jϵNi, we can write (3) in a vector form as(4)Ztki+1=βtkiZtkiby utilizing the concept of a t-step transition matrix, we can state that(5)βtki=βt-1⋯β1β0,where in (4)(6)Ztki+1=Z1tk1+1Z2tk2+1⋯⋯Zntkn+1Ztki=Z1tk1Z2tk2⋯⋯Zntknβϵψ represents the sparsity design of the matrix β with restraint, where(7)ψ=βϵRn×n∣βij=0ifi,j∉E,i≠jAfter defining the sparsity pattern of the matrix, we can now transform (4) as(8)Ztki=∏i=0tki-1βtkiZ0.Here it is important to highlight that (8) is valid for all tki:(9)Ztki=βtkiZ0.Now the primary goal is to achieve a consensus and to select a weighting matrix in such a way that the convergence condition is satisfied and Z(tki) converge to the average vector, with any initial value Z(0):(10)limtki→∞⁡Ztki=1n11TZ0,where n represents the number of participating agents in communication network and a 1 is a vector of ones:(11)limtki→∞⁡Ztki=limtki→∞⁡βtkiZ0.If we now compare (10) with (11), we will attain(12)limtki→∞⁡βtkiZ0=1n11TZ0.Here we compare the terms in (12), and we will come up with(13)limtki→∞⁡βtki=1n11T.From (13) we can compute the equations for different performance parameters for convergence analysis; the asymptotic convergence factor [26] is calculated as(14)rasymβtki=supz0≠z•ztki-z•2z0-z•21/tki,where z•=limt→∞z(tki).Generally convergence is mentioned as a degree of error reduction with refinement towards zero for finite elements with grid spacing. Similarly asymptotic convergence is defined as a convergence behaviour of the system when grid arrangement is considered very trivial in a matrix and error between two states ranges towards zero.From (14), the convergence time can be computed as (15)τasym=1log⁡1/rasymβtki.Convergence time of any system is defined as a computation time, exactly how speedily different agents in a network touch a state of consistent convergence. It is considered to be one of the foremost goals and vital performance indicators in designing of distributed algorithms.One of the other important performance indicators used for network convergence is matrix spectral radius and it is denoted byρ(·). It is a biggest absolute value of its eigenvalues in the matrix spectrum. Mathematically it can be expressed as(16)rasymβ=ρβ-11Tn.


## 4. Proposed Algorithm

In the field of distributed multiagent systems, its primary impression that consensus algorithms enforce the network agents communicating in a network towards a common value by information exchange by their neighbourhood if the communication is reliable; network topology is considered fixed. But achieving consensus for the cases in which network connectivity is unreliable, communication is asynchronous and update time for the network agents varying time to time is really challenging.In this section we are proposing a consensus algorithm for distributed network consisting ofn autonomous agents (i.e., 1,2,…,n), whose directed graph topology is considered as a fixed (reliable) and for switching topology (unreliable). Agents are sharing a common state space R with asynchronous communication in terms of different update time for each agent. Initial start time for all agent is considered the same but later on each agent adjusts its current state value, depending on the information received from other set of defined neighbors N(t,i) at a particular instance of time. Let zi(tki)ϵR represents the initial state of an agent i and let Z=[z1,z2,…,zn]T. We can represent designed discrete time multiagent system as z(tki+1)=ftki,utki, where u(tki) is a state feedback controller which needs to be designed as well with the help of weighting matrix. If we suppose z(tki) as an initial value and it converges to a stable value z˙, in such away that zi˙=zj˙ for all i,j as t→∞, then it is said to achieve consensus. If agent i receives the state information of its neighbors at tki, then agent i is assumed to take the following dynamics in time interval (tki,tk+1i):(17)z˙it=zit+∑jϵNtki,iβijtkizjtki-zitifNtki,i≠ϕ,where tε[tki,tk+1i).We assume that agenti receives its neighbors states at update times t0i,t1i,…,tki,… which can be denoted as tki. In proposed model we are considering the following condition, which presumed to be essentially contented by {tki}.Condition.For any kϵZ+˙,0<Tuˇ≤tk+˙1i≤Tu^, where Tuˇ, Tu^.The core intention behind the update times is to acquire an information of neighbours state value by an agenti to apprise its dynamic consequently. Two time bounds are presented in the proposed algorithm, upper bound Tu^ and lower bound Tuˇ. Both have their own importance and significance in convergence analysis under asynchronous time update communication. Lower bound Tuˇ of time interval among any two consecutive update time offers assurance to the authentication of the consensus algorithm, while on the other hand upper bound Tu^; of tk+1i-tki supports the dissimilar states of an agents to assemble themselves on a common value.While designing a proposed algorithm, primary goals are to achieve quick convergence, reduce the iterations for bounded convergence, and also meet the best of performance indicators as mentioned in the previous section.Proposed algorithm can be mathematically expressed as(18)zitk+1i=zitki+∑jϵNtki,iβijtkizjtki-zitkiwe can write(19)βijtki=ditki+djtki2ditki∗djtkii≠j0otherwise.In the above equationdi is the degree of agent i or we can say the total neighbors of an agent i.Proof of an Algorithm.
Suppose(20)Ztki=Z1tk1Z2tk2⋯⋯Zntkn,Utki=u1tk1u2tk2⋯⋯untkn.Similarly(21)Ztki+1=z1tk1+1z2tk2+1⋯⋯zntkn+1. At this point it is significant to articulate a global state equation for a system, which is intended for average convergence in the given form as (22)Ztki+1=Ztki+Utki.Global input vector can be formulated as(23)Utki=βijtkiA-DZtki.For unreliable network topology the weighting matrix β is not fixed, so for the particular case we used the following symbolization βij(tki) in (23). After deputizing (23) in (22), we will get(24)Ztki+1=Ztki+βijtkiA-DZtki.We can additionally write the following after applying the concept of Laplacian matrix:(25)Ztki+1=Ztki-LβijtkiZtki,(26)Ztki+1=I-LβijtkiZtki.Distributed linear iteration in (26) designates for tki=0,1,2,…:(27)Ztki=I-LβijtkiZ0,(28)limtki→∞⁡Ztki=limtki→∞⁡I-βijtkiLZ0.Now equating (11) and (28),(29)limtki→∞⁡βtki=limtki→∞⁡I-βijtkiL. Now referring to (13)(30)limtki→∞⁡βtki=1n11T.Therefore,(31)limtki→∞⁡I-βijtkiL=1n11T.If we consider a system, with infinite number of agents, that is, n→∞, then we can write(32)limtki→∞⁡I-βijtkiL=0.
The concluding outcome of (32) will develop as(33)βijtki=ditki+djtki2ditki∗djtkii≠j0otherwise.


## 5. Numerical Examples and Simulation Results

In this section stimulation results are presented for various numerical examples. All examples are simulated in Matlab environment for generating results. This section also validate the efficiency of projected algorithm in four different scenarios for asynchronous time update communication under reliable and unreliable communication. To compare the benchmarks of proposed algorithm, a detailed simulation comparison with other existing approaches is performed. For that particular purpose four different performance parameters, that is, total number of iterations, CPU time, asymptotic convergence factor, and convergence time, have been considered to compute the results for each scenario. Total number of iterations is basically the iteration count in which the consensus is achieved using Matlab software and similarly CPU time is the processing time of the machine on which all the simulation are carried out with same computational resources. Error graphs of proposed method and other existing approaches are also produced in this section for better understanding. Initial values are assigned to agents asxn(0)=1 and xi(0)=0,∀i=1,2,3,…,n-1 in all four numerical examples. For any iεIn,tk+1i-tki is evenly distributed between 0.2 and 0.6, lower time bound is Tuˇ=0.2, and upper time bound is Tu^=0.6. Additionally error tolerance considered is e=10-15, in which the total number of iterations is represented by NI, where(34)eik=∑jϵNixik-xjk,i=1,2,…,n.Example 1 (fixed network topology with asynchronous time update).
In this example, a case of reliable communication among multiagents with asynchronous time update is considered (Figure1). Communication topology remains fixed throughout the simulation but the update times of agents are diverse and independent of each others. Each agent can get all of its neighbour states only at its update times. For any iεIn,tk+1i-tki is evenly distributed between 0.2 and 0.6. A network of 30 agents is considered which are communicating with each other under reliable conditions. All agents have to develop an average consensus on the value of 0.0333. To evaluate the performance of proposed algorithm, the comparison results of Example 1, simulated by proposed and existing methods are shown in Table 1. An error graph is generated in Figure 2, which evaluates how fast a method converges to its consensus value. It also helps us to graphically evaluate the performance of different methods. The consensus graphs of proposed method, Metropolis method, and local degree method are shown in Figures 3, 4, and 5 respectively.Table 1
Comparison results of Example1 for different performance parameters.
Methods NI C P U M i n ρ(W-11T/n) τasym Proposed method 127 0.342 0.7518 3.505 Metropolis method 215 0.3972 0.8461 6.003 Local degree method 189 0.3617 0.8284 5.3131Figure 1
Network topology considered in Example1.Figure 2
Plot of error graph generated for Example1.Figure 3
Agents approaching to a consensus value using proposed algorithm in Example1.Figure 4
Agents approaching to a consensus value using Metropolis method in Example1.Figure 5
Agents approaching to a consensus value using local degree method in Example1.Example 2 (unreliable switching network topology with asynchronous time update).
The second case is on unreliable switching topologies with asynchronous update time. In this example two major challenges in cooperative control are highlighted, that is, unreliable communication among agents and asynchronous behavior in update times. When the communication topology is changing dynamically and additionally the update times are also varying and independent of each other, it becomes more challenging for agents to make consensus on a single value. These kinds of problems are really helpful to compare the performance of consensus methods. The numerical results of case 2 are shown in Table2. The graphical comparison of consensus methods and the network topology are shown in Figures 7 and 6, respectively. The consensus graphs of proposed method, Metropolis method, and local degree method are shown in Figures 8, 9, and 10, respectively, which are the evidence of perfectness of proposed method.Table 2
Comparison results of Example2 for different parameters.
Methods NI C P U M i n ρ ( W - 1 1 T / n ) τasym Proposed method 163 0.2092 0.7998 4.778 Metropolis method 245 0.2868 0.8635 6.8173 Local degree method 215 0.2540 0.8456 5.9660Figure 6
Network topology considered in Example2.Figure 7
Pot of an error graph for Example2.Figure 8
Agents approaching to a consensus value using proposed algorithm in Example2.Figure 9
Agents approaching to a consensus value using Metropolis method in Example2.Figure 10
Agents approaching to a consensus value using local degree method in Example2.Example 3 (addition of agents in reliable network topology at any time instant).
This example is the continuity case of Example1 and is called forced consensus problem. As in Example 1, some agents are selected randomly with fixed topology with asynchronous time updates, and finally they develop a consensus on a single value. Similarly in this example, some agents are randomly added in the network at any time instant and now they have to develop consensus on some new unique value. This means that at any time instant, the agents are forced from one value to another consensus value. In this example, 10 agents are added at some time interval; that is, t=50ms; the total number of agents becomes 40 and they have to develop consensus on value 0.025 with utilizing the asynchronous time updates; that is, it is fixed between 0.2 and 0.6. The numerical results of Example 3 are produced in Table 3. The network topology considered for this example is shown in Figure 11. In Figure 12, error is plotted for the proposed method, metropolis, and local degree method, respectively. Consensus graphs for this case are presented in Figures 13, 14, and 15.Table 3
Comparison results of Example3 for different parameters.
Methods NI C P U M i n ρ ( W - 1 1 T / n ) τasym Proposed method 147 0.3515 0.7743 3.909 Metropolis method 193 0.4013 0.8216 5.089 Local degree method 180 0.3961 0.8070 4.663Figure 11
Communication topology considered in Example3.Figure 12
Plot of error graph generated for Example3.Figure 13
Agents approaching to a consensus value using proposed algorithm in Example3.Figure 14
Agents approaching to a consensus value using Metropolis method in Example3.Figure 15
Agents approaching to a consensus value using local degree method in Example3.Example 4 (addition of agents in unreliable network topology with asynchronous time update at any instant of time).
This example is the second problem of forced consensus and is the continuity of case in Example2. As in Example 2, some agents are selected randomly with dynamically changing interaction topology and asynchronous time updates; they developed consensus on a single value. In this example some agents are randomly added in the system at any time instant. Addition of agents disturbs the performance of consensus methods as the communication strategy is unreliable and changing randomly and also the time updates are asynchronous, so it becomes difficult for the agents to develop agreement on a single value but with proposed method it reaches to the consensus value in a less convergence time as compared to other techniques. The numerical results of Example 4 are shown in Table 4. The network topology considered for this example is given in Figure 16. In Figure 17 error is plotted for the proposed method, metropolis, and local degree method, respectively. Consensus graphs for this case are shown in Figures 18, 19, and 20. From the numerical and graphical analysis of different consensus techniques, it is observed that the proposed method converges faster to consensus value than other well-known consensus methods.Table 4
Comparison results of Example4 for different parameters.
Methods NI C P U M i n ρ ( W - 1 1 T / n ) τ a s y m Proposed method 159 0.4571 0.7950 4.359 Metropolis method 217 0.4767 0.8494 6.1297 Local degree method 199 0.4654 0.8370 5.6231Figure 16
Network topology considered in Example4.Figure 17
Plot of an error graph for Example4.Figure 18
Agents approaching to a consensus value using proposed algorithm in Example4.Figure 19
Agents approaching to a consensus value using Metropolis method in Example4.Figure 20
Agents approaching to a consensus value using local degree method in Example4.


## 6. Conclusion

This paper proposed a new convergence algorithm for distributed multiagent systems. A unique approach of asynchronous time updates under reliable and unreliable network topology is implemented to produce better results in terms of different performance indicators, such as number of iterations and computational cost, and, capable of operability in large dynamic networks with unreliable communication, CPU processing time, asymptotic convergence factor, and convergence time have been considered. A detailed comparison is produced with each example with different operational scenario, as an effective evidence to prove the efficiency of the proposed algorithm. In future we will extend our research for systems experiencing time varying delays under asynchronous communication to study their performance.



---

*Source: 4635701-2018-03-11.xml*