Coverage-maximization in networks under resource constraints

Subrata Nandi, Lutz Brusch, Andreas Deutsch, Niloy GangulyPhysical 2010 · DOI

Abstract

Efficient coverage algorithms are essential for information search or dispersal in all kinds of networks. We define an extended coverage problem which accounts for constrained resources of consumed bandwidth B and time T . Our solution to the network challenge is here studied for regular grids only. Using methods from statistical mechanics, we develop a coverage algorithm with proliferating message packets and temporally modulated proliferation rate. The algorithm performs as efficiently as a single random walker but O(B(d-2)/d) times faster, resulting in significant service speed-up on a regular grid of dimension d . The algorithm is numerically compared to a class of generalized proliferating random walk strategies and on regular grids shown to perform best in terms of the product metric of speed and efficiency.
BibTeX
@inproceedings{nandi2010coverage,
  author = {Subrata Nandi and Lutz Brusch and Andreas Deutsch and Niloy Ganguly},
  title = {{Coverage-maximization in networks under resource constraints}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physreve.81.061124},
}

Loading related content...

Figure