Low hitting time random walks in wireless networks
Low hitting time random walks in wireless networks
复制标题
DOI：
10.1002/wcm.v9:5
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Beraldi Roberto;Leonardo Querzoni;Baldoni Roberto
中科院分区：
文献类型：
--
作者：
Beraldi Roberto;Leonardo Querzoni;Baldoni Roberto
随机游走可以方便地利用实现概率算法来解决许多搜索问题所产生的分布式应用程序，例如，服务发现，P2P文件共享，在本文中，我们认为随机游走均匀的无线网络上执行，并研究如何减少预期数量的步行步骤需要达到一个目标，即命中时间。后者是基于随机游走的算法的主要搜索性能指标，因为它决定了对搜索的平均响应及其成本;因此，与其他解决方案相比，使用随机游走的实际便利性取决于实现低命中时间。我们展示了如何在均匀的无线网络中，随机游走的自然实现，选择下一个节点随机访问所有邻居之间是不是一个很好的选择，因为它有一个很强的负面影响的命中时间。本文分析了这种负面影响，并提出了两个邻居选择规则，旨在减少命中时间。模拟研究证实了所提出的解决方案的好处。版权所有© 2008约翰威利父子有限公司。
Random walks can be conveniently exploited for implementing probabilistic algorithms to solve many searching problems arised by distributed applications, for example, service discovery, p2p file sharing, etc. In this paper we consider random walks executed on uniform wireless networks and study how to reduce the expected number of walk steps required to reach a target, namely the hitting time. The latter is the main search performance metric of a random walk based algorithm, since it determines the average response to a search as well as its cost; thus, the actual convenience of using random walks compared to other solutions depends on achieving a low hitting time. We show how in uniform wireless networks, the natural implementation of a random walk which selects the next node to visit at random among all neighbors is not a good choice, since it has a strong negative effect on the hitting time. This paper studies such a negative effect analytically and proposes two neighbor selection rules aiming at reducing the hitting time. A simulation study confirms the benefits of the proposed solutions. Copyright © 2008 John Wiley & Sons, Ltd.