The cover time of neighbor-avoiding gossiping on geometric random networks

Gabriele Gianini, Ernesto Damiani

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

The standard gossiping used in many overlay networks consists in a Self-Avoiding Random Walk (SAW): a message, once received by a node, is forwarded to a node chosen uniformly at random among the neighbors, excluding the node it comes from. We focus on a generalization of the above walks, defined by the Neighbor-Avoiding Walks (NAWs), i.e. walks that not only avoid themselves, but preferably also the neighbors of the path they traveled. We studied the performance of NAW policies over geometric random networks (a common model used for unstructured networks for instance for Wireless Sensor Networks) in terms of cover time and as a function of several structural network graph metrics: nodes' cardinality, nodes' clustering coefficient, node distance distribution, link centrality distribution. We find that neighbor avoiding policies perform better that the usual SAW policy and that this improvement is especially apparent in networks whose topology is characterized by high values of link centrality.

Original languageBritish English
Title of host publication2013 7th IEEE International Conference on Digital Ecosystems and Technologies
Subtitle of host publicationSmart Planet and Cyber Physical Systems as Embodiment of Digital Ecosystems, DEST 2013
Pages7-12
Number of pages6
DOIs
StatePublished - 2013
Event2013 7th IEEE International Conference on Digital Ecosystems and Technologies: Smart Planet and Cyber Physical Systems as Embodiment of Digital Ecosystems, DEST 2013 - Menlo Park, CA, United States
Duration: 24 Jul 201326 Jul 2013

Publication series

NameIEEE International Conference on Digital Ecosystems and Technologies
ISSN (Print)2150-4938
ISSN (Electronic)2150-4946

Conference

Conference2013 7th IEEE International Conference on Digital Ecosystems and Technologies: Smart Planet and Cyber Physical Systems as Embodiment of Digital Ecosystems, DEST 2013
Country/TerritoryUnited States
CityMenlo Park, CA
Period24/07/1326/07/13

Fingerprint

Dive into the research topics of 'The cover time of neighbor-avoiding gossiping on geometric random networks'. Together they form a unique fingerprint.

Cite this