On the Role of Mobility and Network Coding on Multi-message Gossip in Random Geometric Graph

摘要

In this paper, the performance of network codingbased gossip algorithms -- i.e. algebraic gossip algorithms -- is analyzed on random geometric graphs under static and mobile environments. The lower bounds for the convergence time of algebraic gossip algorithms are derived based on the conductance, and these bounds are O(n log n log ε -- 1 -- log n log ε -- 1) with node mobility and O((n3/2 -- n1/2) log ε -- 1/log1/2 n) without node mobility. Theoretical results show that algebraic gossip algorithms with node mobility converge O(n1/2/log3/2n) more quickly than without node mobility, and O(log n) more quickly than a gossip algorithm with node mobility but without network coding. Finally, we assess and compare the convergence time of various gossip algorithms, with both mobility and network coding. As corroborated by extensive numerical experimentation, integrated network coding with mobility can significantly improve the convergence time of information dissemination in dynamic environments.