تجزیه و تحلیل نظری از چند هاپ الگوریتم اجماع برای شبکه های بی سیم: تجارت کردن در میان قابلیت اطمینان، پاسخگویی و تاخیر تحمل

Recently great attention has been posed on the consensus protocols in networks of agents. A widely studied consensus algorithm allows every agent automatically converge to a common consensus state using only local information received from its one hop neighboring agents. We study the problem of reaching a consensus in network of mesh nodes under m-hop protocols where each node-agent can access to the state of its m-steps neighboring agents. Moreover we consider also the presence of heterogeneous time delays affecting the communication through the different hops. The first aim of the paper in the WMNs research theoretical foundations is to give a sufficient condition for the multi hop network consensus protocol stability in the presence of heterogeneous time delays that explicitly relates the network and algorithm features (e.g. time delay tolerance, topology, the number of hop). The second aim is to point out by the previous analytical condition the interplay between the network performance/features (i.e. reliability, the delay tolerance, the communication topology) and the effectiveness of the distributed consensus algorithms/communication protocols (i.e. in terms of complexity, amount of the information to be managed, responsiveness and steady state error performance). This trade off must be taken into account in the performance evaluation and algorithm design for WMNs. Finally, the theoretical result has been validated by simulation experiments using a realistic evaluation environment.

The Wireless Mesh Network (WMN) is an emerging communication architecture with many practical applications in such areas as selforganizing community networks, industrial plant automation, wireless sensor networks, community networks and municipal networks [1]. A WMN can be considered as a two-tier architecture. The first tier is a wireless backbone composed of mesh routers with gateway functionality and capable of packet routing. The second tier is composed of mobile and/or portable wireless devices (e.g. smart phones, mobile devices, etc.) acting as clients. The first tier allows the integration of WMNs with other networks such as the Internet, cellular, IEEE 802.15, IEEE 802.16, sensor networks. WMN is a communication paradigm to enable resilient, cost-efficient and reliable services for improving the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs). Due to the large scales of WMNs in terms of the number of devices/users and their geographical dimensions, communication is efficiently carried out through the cooperation of wireless devices in a multi-hop manner. This has recently called a wide and deep research about the analysis, the performance evaluation and the protocol design of these networks [1], [2], [3], [4], [5], [6], [7], [8], [9] and [10] focusing on the multi hop scenarios [11], [12], [13], [14], [15], [16] and [17]. The multi hop and self-organizing nature of WMNs and their degree of variability in terms of clients and topology arise challenging objectives as the analysis and design of distributed flooding algorithms for a reliable and efficient communication through the network. Moreover, the recently emerging network paradigms such as sensor networks, peer-to-peer networks, surveillance networks, formation flight, clusters of satellites, automated highway systems have led to the requirement of designing distributed consensus, iterative and efficient algorithms for estimation, detection, optimization and control (i.e. [18], [19], [23], [24], [25], [26], [27], [28] and [29]). Those algorithms provide the necessary scalability and robustness to efficiently operate in highly distributed and dynamic networks as it is the case of WMNs [38], [40] and [41]. One common feature of this research is the sharing of information between agents in order to address a common objective. The most studied distributed algorithm allows every agent automatically converge to a common average value (average consensus) using only local information received from its one step neighboring agents. They use a limited amount of local information to allow distributed knowledge of global network properties/measures. By and large flooding and gossip algorithms are based on the idea that the nodes talk together by a deterministic or probabilistic interaction law in a way similar to human ”gossip”. For example, when, in a crowd, somebody has a “news”, he shares it with his neighbors. In this way all the people connected with him learn the “news” and repeat it to their neighbors, so that the new information is spread like an epidemic illness. A similar process is implemented in WMNs where new message or measure initially given to each node could be disseminated through the mesh network in order to achieve a specific objective. Specifically, starting with each mesh node having a message or a measure, two kinds of objectives can be desired: (i) each mesh node distributes its message to all other mesh nodes in a reliable way and in the shortest possible time; (ii) the mesh nodes average their values (average consensus) with a bounded steady state error and in the shortest possible time. Several papers deal with the objective (i) as [30], [31], [32], [33], [34] and [35] and references therein. Other papers investigate average consensus problem trying to achieve objective (ii). In this paper we dwell at great length on the performance evaluation of the flooding algorithm aimed to address the objective (ii). Specifically, protocol design problems for achieving faster average consensus have attracted considerable attention from a number of researchers. It has been pointed out that the convergence rate is related to the algebraic connectivity (the second smallest eigenvalue of a stochastic matrix characterizing the averaging algorithm). So, the fastest averaging algorithm is obtained by optimizing the eigenvalue over the set of allowed gossip algorithms. In [36], the design of the weights of a network is considered in order to increase the algebraic connectivity of a network graph that is a measure of speed of convergence of consensus algorithms. An alternative approach [46] keeps the weights fixed and designs the topology of the network to assess high algebraic connectivity based on Watts’ rewiring procedure [47] that led to creation of small-world model. This increases of a multiple orders of magnitude the algebraic connectivity of the network with respect to regular graph. Moreover, a lower and an upper bound for the averaging time, in terms of algebraic connectivity, were derived in [37]. Recently in [48] it has been proposed a multi-hop relay protocol based on the idea that each agent can get more information by passing its neighbors states to others with the aim of improving the convergence speed. Although the authors highlight the trade off between number of hop and convergence speed, they analyzed only the “two-hop” relay protocol case and in the presence of identical delays, carrying out the analysis validation by a Matlab simulations without using a more realistic network simulator. On the other side, the analysis of multi-hop consensus protocol is particularly useful for those network scenarios intrinsically based on multi path communication mechanisms (e.g. for WMNs services, sensor/actuator network applications) and when the rate of convergence of the algorithm strongly affects the final performance (e.g. in the cases of tracking problem and presence of mobile agents). For example, the rate of convergence of the algorithm determines the agility of a distributed estimator to track the desired value [38] or the error in the distributed optimization algorithm [39], [42] and [43]. Specifically, the consensus algorithms find actual applicability to geographical wireless mesh scenarios such as formation control, cooperative classification and surveillance, intelligent highways, cooperative tasking, spatio-temporal planning, vehicular networks as shown preliminary implementations (e.g. see [44] and references therein). For these reasons, the analysis and the performance evaluation of protocols in multi-hop scenario are of a great recent interest [38], [24] and [45] and they are the question that we consider in this paper. Differently from the previous works, we study the problem of reaching a consensus in networked mesh nodes under m-hop protocols where each node-agent can access to the state of its m-steps neighboring agents. In addition, we consider the presence of heterogeneous time delays affecting the communication through the different hops. The first aim of the paper in the WMNs research theoretical foundations is to give a sufficient condition for the multi hop network consensus protocol stability in the presence of heterogeneous time delays that explicitly relates the network and algorithm features (e.g. time delay tolerance, topology, the number of hop). The second aim is to point out by the previous analytical condition the interplay between the network performance/features (i.e. reliability, the delay tolerance, the communication topology) and the effectiveness of the distributed consensus algorithms/communication protocols (i.e. in terms of complexity, amount of the information to be managed, responsiveness and steady state error performance). This trade off must be taken into account in the performance evaluation and algorithm design for WMNs. Finally, most of papers in the literature, however, are focused only on the theoretical issues and system modelling (e.g. [38], [39], [42] and [43]) without using a realistic performance evaluation environment. Herein the theoretical result has been validated by simulation experiments using a more realistic evaluation environment. This is of main interest when one aim is to investigate the interplay between the flooding algorithm features and the communication network performance. The rest of the paper is outlined as follows. In Section 2, a multi hop consensus protocol models are described. Then in Section 3, the presence of inhomogeneous time delays is considered and a sufficient condition for protocol stability is presented. Simulation experiments are shown in Section 4. Finally, conclusions are outlined in Section 5.

We have analyzed the problem of reaching the average consensus in WMNs under multi-hop protocols where each agent can access to the state of its m-steps neighboring agents. The presence of heterogeneous time delays is considered and a sufficient stability condition to reach a consensus is explicitly given as function of network and algorithm features. The latter analytical condition has been used for pointing out the interplay between the network performance (i.e. reliability, the delay tolerance, the communication topology) and the effectiveness of the distributed consensus protocol (i.e. in terms of responsiveness and steady state error). This interplay highlights different trade off, summarized in the follows: • the algorithm responsiveness improves for increasing number of hop m. This is particularly desired in the case of high dynamic scenario (i.e. average value tracking application) where the average value computation need to be done in a short time; • the maximum admissible time-delay for the network is inversely proportional to m resulting in a trade off between delay margin robustness, number of hop and algorithm responsiveness; • the algorithm steady state error between the average value computation and the actual average value increases with the increasing of m. Indeed increasing m, increases the number of packets in the network and their probability to be lost for collision effect with a consequently reduction of network reliability; • the mesh node computational capacity and the communication bandwidth might limit the maximum number of hops of the consensus algorithm and in turn they might affect the algorithm responsiveness; • an increasing of m yields an increase of energy consumption due to higher number of packets to be managed by the node and higher number of retransmissions for packet losses; • collision effect and node buffer size affect the network reliability and therefore the algorithm steady state error performance; • when the target is to have both high responsiveness and reduced steady state error, the node buffer size and computation capacity have to be designed in order to make up the drawbacks of the high value of m. The simulation experiments have validated the sufficient stability condition and shown up the above trade off that must taken into account in the analysis and design of cooperative strategies for WMNs. Finally, the algorithm presents a good scalability property with respect the number of nodes.