WANG Gang, LIN Zun, WANG Fuxiang. Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs[J]. Chinese Journal of Electronics, 2019, 28(2): 386-391. doi: 10.1049/cje.2019.01.012
Citation: WANG Gang, LIN Zun, WANG Fuxiang. Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs[J]. Chinese Journal of Electronics, 2019, 28(2): 386-391. doi: 10.1049/cje.2019.01.012

Index Geographic Gossip Algorithm for Information Dissemination over Regular Graphs

doi: 10.1049/cje.2019.01.012
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (118) PDF downloads(144) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return