The Performance of Multimessage Algebraic Gossip in a Random Geometric Graph

摘要

Gossip algorithm has been widely regarded as a simple and efficient method to improve quality of service (QoS) in large-scale network which requires rapid information dissemination. In this paper, information dissemination based on algebraic gossip in a random geometric graph (RGG) is considered. Thennodes only have knowledge about their own contents. In every time slot, each node communicates with a neighbor partner chosen randomly. The goal is to disseminate all of the messages rapidly among the nodes. We show that the gain of the convergence time isOn1/2logε-1/log1/2nwith network coding. Simulation results show that these bounds are valid for the random geometric graph and demonstrate that network coding significantly improves the bounds with the number of users increasing.