Coverage maximization

Overview -

Information dissemination and search in networks are the most frequently performed operations in any large scale distributed system. In most of the instances of such systems there is a limitation of the available energy in the nodes (e.g., sensor networks, mobile ad hoc networks, internet of things etc). On the other hand the initiated operation also has to be completed within a limited time. Hence, maximization of coverage, i.e., the number of distinctly visited nodes under constraints of time and energy is the prime target of any proposed algorithm for these operations. In order to quickly achieve high coverage, the existing algorithms tend to proliferate message packets (modeled as walkers) at higher rate. Due to the nondeterministic nature of the algorithms and the unknown network topology (unstructured), these blind proliferations create many redundant visits of the nodes in the network which reduces the utilization of the available energy. Thus, there is a trade off between the optimization of the time and energy consumption in the algorithms : if we want to minimize the time requirement then there is a high probability of huge wastage of energy - on the other hand - if we want to minimize the energy consumption, then the time requirement will be high. Many algorithms have been proposed in the past to solve this issue. In one extreme of these algorithms, there is basic flooding which takes the minimum time but wastes the maximum amount energy to achieve a certain coverage. In the other extreme there is the single random walk algorithm, which wastes the minimum energy but spends the maximum time to achieve a certain coverage. The following figure pictorially describes this scenario.

We capture this tradeoff through a formal understanding of the problem space and using the results from analytical studies done in the past on K-random-walk-based algorithms we derive a notion of optimal coverage under a given constraint of time and energy. Specifically, we identify that wastage of energy quickly increases with an increase in the spatial density of the walkers. Based on this postulate, we design a very simple distributed algorithm which dynamically estimates the density of the walkers and thereby carefully proliferates the walkers in sparse regions. We use extensive computer simulations to test our algorithm in various kinds of network topologies whereby we find it to be performing particularly well in networks that are highly clustered as well as sparse. This work has been published in Physical Review E [1].

Publication out of this work -

[1] Coverage maximization under resource constraints using a non-uniform proliferating random walk. Sudipta Saha and Niloy Ganguly, Physical Review E., vol. 87, p. 022807, 2013. [Online]