Effect of Network Geometry and Interference on Consensus in Wireless Networks

Summary We study the convergence of the average consensus algorithm in wireless networks in the presence of interference. It is well known that convergence of the consensus algorithm improves with network connectivity. However, from a networking standpoint, highly connected wireless networks may have lower throughput because of increased interference. This raises an interesting question: what is the effect of increased network connectivity on the convergence of the consensus algorithm, given that this connectivity comes at the cost of lower network throughput? We address this issue for two types of networks: regular lattices with periodic boundary conditions, and a hierarchical network where a backbone of nodes arranged as a regular lattice supports a collection of randomly placed nodes. We characterize the properties of an optimal Time Division Multiple Access (TDMA) protocol that maximizes the speed of convergence on these networks, and provide analytical upper and lower bounds for the achievable convergence rate. Our results show that in an interference-limited scenario the fastest converging interconnection topology for the consensus algorithm crucially depends on the geometry of node placement. In particular, we prove that asymptotically in the number of nodes, forming long-range interconnections improves the convergence rate in one-dimensional tori, while it has the opposite effect in higher dimensions.