Coverage maximization under resource constraints using proliferating random walks

Pramana

Niloy Ganguly1¹  Abhijit Guria¹  Sudipta Saha¹ 

[1] Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur 721 302, India$$

关键词: Coverage;    resource constraints;    random walk;    proliferation;    sparsity.;   

DOI  :  

学科分类：物理（综合）

来源: Indian Academy of Sciences

【 摘 要 】

Dissemination of information has been one of the prime needs in almost every kind of communication network. The existing algorithms for this service, try to maximize the coverage, i.e., the number of distinct nodes to which a given piece of information could be conveyed under the constraints of time and energy. However, the problem becomes challenging for unstructured and decentralized environments. Due to its simplicity and adaptability, random walk (RW) has been a very useful tool for such environments. Different variants of this technique have been studied. In this paper, we study a history-based non-uniform proliferating random strategy where new walkers are dynamically introduced in the sparse regions of the network. Apart from this, we also study the breadth-first characteristics of the random walk-based algorithms through an appropriately designed metrics.

【 授权许可】

Unknown