Random consensus protocol in large-scale networks

One of the main performance issues for consensus protocols is the convergence speed. In this paper, we focus on the convergence behavior of discrete-time consensus protocols over large-scale sensor networks with uniformly random deployment, which are modelled as Poisson random graphs. Instead of using the random rewiring procedure, we introduce a deterministic principle to locate certain "chosen nodes" in the network and add "virtual" shortcuts among them so that the number of iterations to achieve average consensus drops dramatically. Simulation results are presented to verify the efficiency of this approach. Moreover, a random consensus protocol is proposed, in which virtual shortcuts are implemented by random routes.