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.
