This paper considers a random walk-based search algorithm in which the random walk occasionally makes longer jumps. The algorithm is tailored to work over wireless networks with uniform node distribution. In a classical random walk each jump has the same mean length. On the contrary, in the proposed algorithm a node may decide to double the expected jump length by increasing the nominal transmission power and picking a neighbor beyond the nominal range. The aim of these long jumps is reducing the spatial correlation among short term subsequent node selections, thus improving the search performance, namely the hitting time. Two versions of the algorithm are studied, with and without lookahead. A protocol for implementing each version is also proposed. When there is no lookahead the proposed protocol allows for a finer transmission power transmission regulation. The paper studies, for three network topologies, the impact of the long jump probability on the hitting time and on the average total power required before the target is found. (C) 2008 Elsevier B.V. All rights reserved.

Random walk with long jumps for wireless ad hoc networks / Beraldi, Roberto. - In: AD HOC NETWORKS. - ISSN 1570-8705. - 7:2(2009), pp. 294-306. [10.1016/j.adhoc.2008.03.001]

Random walk with long jumps for wireless ad hoc networks

BERALDI, ROBERTO
2009

Abstract

This paper considers a random walk-based search algorithm in which the random walk occasionally makes longer jumps. The algorithm is tailored to work over wireless networks with uniform node distribution. In a classical random walk each jump has the same mean length. On the contrary, in the proposed algorithm a node may decide to double the expected jump length by increasing the nominal transmission power and picking a neighbor beyond the nominal range. The aim of these long jumps is reducing the spatial correlation among short term subsequent node selections, thus improving the search performance, namely the hitting time. Two versions of the algorithm are studied, with and without lookahead. A protocol for implementing each version is also proposed. When there is no lookahead the proposed protocol allows for a finer transmission power transmission regulation. The paper studies, for three network topologies, the impact of the long jump probability on the hitting time and on the average total power required before the target is found. (C) 2008 Elsevier B.V. All rights reserved.
2009
probabilistic search algorithms; random walk; wireless networks
01 Pubblicazione su rivista::01a Articolo in rivista
Random walk with long jumps for wireless ad hoc networks / Beraldi, Roberto. - In: AD HOC NETWORKS. - ISSN 1570-8705. - 7:2(2009), pp. 294-306. [10.1016/j.adhoc.2008.03.001]
File allegati a questo prodotto
File Dimensione Formato  
VE_2009_11573-226683.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 387.23 kB
Formato Adobe PDF
387.23 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/226683
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 21
social impact