%0 Journal Article
%T The Performance of Multimessage Algebraic Gossip in a Random Geometric Graph
%A Gang Wang
%A Zun Lin
%A Wenyang Guan
%A Feng Wang
%J International Journal of Distributed Sensor Networks
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/545362
%X 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. The n nodes 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 is with 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. 1. Introduction With the increased demand for network resources and the expansion of the variety of information resources, information dissemination based on gossip becomes an effective way to improve quality of service (QoS) in large-scale network environment. Gossip algorithm is a simple and efficient algorithm which has good extensibility and robustness to adapt to the large-scale network environment well; it also reduces the redundancy of the retransmission to disseminate information in a wide range of distributed applications. Recently, gossip algorithms have been proposed for many distributed applications, including peer-to-peer (P2P) network, broadcast and multicast [1, 2], adhoc network routing [3], and distributed computation and parameter estimation [4, 5]. Network coding [6] is first proposed by Ahlswede et al. in 2000 to change the traditional store-and-forward routing. Network coding brought many potential advantages like improving network throughput, balancing network load and high bandwidth utilization, and increasing the network robustness and adaptability for multicast network. Chen and Tseng [7] proposed a distributed algorithm with random linear network coding [8], which is developed to effectively detect, locate, and isolate the Byzantine attackers in a wireless ad-hoc network. In 2006, Boyd et al. boldly proposed a randomized gossip algorithm [9]. They showed that the convergence time in the random geometric graph (RGG) was , where is the transmission radius threshold and is the number of nodes. Based on the advantage of random linear network coding, Deb et al. [10] suggested an algebraic gossip algorithm that innovatively integrated network coding with a gossip algorithm and proved that the convergence time of the information dissemination improved more quickly than in a
%U http://www.hindawi.com/journals/ijdsn/2013/545362/