WANG Gang, LIN Zun, WANG Fuxiang, “Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 386-391, 2019, doi: 10.1049/cje.2019.01.012
Citation:
WANG Gang, LIN Zun, WANG Fuxiang, “Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 386-391, 2019, doi: 10.1049/cje.2019.01.012
WANG Gang, LIN Zun, WANG Fuxiang, “Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 386-391, 2019, doi: 10.1049/cje.2019.01.012
Citation:
WANG Gang, LIN Zun, WANG Fuxiang, “Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 386-391, 2019, doi: 10.1049/cje.2019.01.012
Corresponding author:
WANG Fuxiang (corresponding author) is currently a lecturer at Beihang University, Beijing, P.R. China. He received his Ph.D. degree from Beihang University. His current research interests include Blind signal processing and application of air traffic flow management.(Email:wangfx@buaa.edu.cn)
An Index geographic gossip (IGG) algorithm is proposed. Relay nodes participate in information exchange and updating. The cumulative number of times these nodes participate is characterized by an index number, which can be used to accelerate information updating. The convergence property of the IGG algorithm is theoretically analyzed in ring and grid network topologies. The IGG algorithm improves the standard gossip algorithm by a gain of O(n) in both convergence time and communication cost. Compared to the geographic gossip algorithm, the IGG algorithm has a gain on the order of O(n) and O(n1/2) in the average hop count for information exchange and communication cost, respectively. Finally, the proposed IGG algorithm is compared with various baselines through simulations, and it is shown that significant performance gain can be achieved.
H. A. Milner and E.C. Szemeredi, “A cure for the telephone disease”, Canadian Mathematical Bulletin, Vol.15, No.3, pp.447-450, 1972.
S. Hedetniemi and A. Liestman, ”A Survey of Gossiping and Broadcasting in Communication Networks,” Networks, Vol.18, No.4, pp. 319-349, Dec. 1988.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, ”Randomized gossip algorithms”, IEEE Transaction Information Theory, Vol. 52, No.6, pp. 2508-2530, 2006.
Ze D, Dan F, Ke Z, et al. ”A gossip-based approach for resource discovery in structured peer-to-peer networks”. Acta Electronica Sinica, Vol.38, No.11, pp.2510-2517, 2010. (in Chinese)
X.N. Zhao, “A signal mechanism based energy-aware geographic routing algorithm” Acta Electronica Sinica, Vol.43, No.5, pp.965-973, 2015. (in Chinese)
J.X Wang, X.N. Zhao and H.Y. Liu, “A greedy geographic routing algorithm based on 2-hop neighbors,” Acta Electronica Sinica, Vol.36, No.10, pp.1903-1909, 2008. (in Chinese)
A.G. Dimakis, A.D. Sarwate, and M.J. Wainwright, “Geographic Gossip Efficient Averaging for Sensor Networks,” IEEE Transactions on Signal Processing, Vol.56, No.3, pp. 1205-1216, Mar. 2008.
N. Biggs, E. Lloyd and R. Wilson, “Graph Theory,” Oxford University Press, pp.1736-1936, 1986.