Coverage-maximization in networks under resource constraints

作     者：Subrata Nandi Lutz Brusch Andreas Deutsch Niloy Ganguly 

作者机构：Department of Computer Science and Engineering Indian Institute of Technology Kharagpur 721302 India Center for Information Services and High Performance Computing Technical University Dresden 01062 Dresden Germany 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2010年第81卷第6期

页      面：061124-061124页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

主　　题：Statistical mechanics 

摘      要：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.