Probabilistic flooding in stochastic networks: Analysis of global information outreach

• Type: Article in International Scientific Journal
• Date: 2012

Authors

Sergio Crisostomo (Author) FCUP; Udo Schilcher (Author) Other; Christian Bettstetter (Author) Other; Joao Barros (Author) FEUP

Journal

Title: Computer Networks

Vol. 56

Pages: 142-156

ISSN: 1389-1286

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 14 Citations

ISI Web of Science

Scopus - 13 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-002-DXT

DOI: 10.1016/j.comnet.2011.08.014

Abstract (EN): This article investigates probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a received message to all its neighbors with a common network-wide forwarding probability omega. Question is: what is the minimum omega-value each node should use, such that the flooded message is obtained by all nodes with high probability? We first present a generic approach to derive the global outreach probability in arbitrary networks and then focus on Erdos Renyi graphs (ERGs) and random geometric graphs (RGGs). For ERGs we derive an exact expression. For RGGs we derive an asymptotic expression that represents an approximation for networks with high node density. Both reliable and unreliable links are studied.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15