Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs

WANG Gang; LIN Zun; WANG Fuxiang

doi:10.1049/cje.2019.01.012

Volume 28 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2019 > 28(2): 386-391

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

Citation:

PDF( 473 KB)

Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs

doi: 10.1049/cje.2019.01.012

1.
School of Electrical and Information Engineering, Beihang University, Beijing 100191, China;
2.
China Mobile Communications Group Co. Ltd, Beijing 100053, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61271194).

More Information

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)
Received Date: 2018-04-28
Rev Recd Date: 2018-11-22
Publish Date: 2019-03-10

Abstract

Abstract

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(n^1/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.
- Information dissemination,
- Gossip algorithm,
- Node mobility,
- Geography

FullText(HTML)

References(8)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views