TY - GEN
T1 - The cover time of neighbor-avoiding gossiping on geometric random networks
AU - Gianini, Gabriele
AU - Damiani, Ernesto
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84885737176&partnerID=8YFLogxK
U2 - 10.1109/DEST.2013.6611321
DO - 10.1109/DEST.2013.6611321
M3 - Conference contribution
AN - SCOPUS:84885737176
SN - 9781479907861
T3 - IEEE International Conference on Digital Ecosystems and Technologies
SP - 7
EP - 12
BT - 2013 7th IEEE International Conference on Digital Ecosystems and Technologies
T2 - 2013 7th IEEE International Conference on Digital Ecosystems and Technologies: Smart Planet and Cyber Physical Systems as Embodiment of Digital Ecosystems, DEST 2013
Y2 - 24 July 2013 through 26 July 2013
ER -