We address the problem of data gathering in a wireless network using multi-hop communication; our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of ω(n) on the expected competitive ratio of any acknowledgment-based distributed algorithm minimizing the maximum flow time, where n is the number of nodes of the network. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and Systems Sciences 45 (1) (1992) 104126] we prove that the algorithm is (1+)-competitive, when the algorithm sends packets a factor O(log(δ)logΔ) faster than the optimal off-line solution; here δ is the radius of the network and Δ the maximum degree. We finally extend this result to a more complex interference model. © 2010 Elsevier B.V. All rights reserved.

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2011). The distributed wireless gathering problem. THEORETICAL COMPUTER SCIENCE, 412(8-10), 633-641 [10.1016/j.tcs.2010.10.018].

The distributed wireless gathering problem

Bonifaci V.;
2011

Abstract

We address the problem of data gathering in a wireless network using multi-hop communication; our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of ω(n) on the expected competitive ratio of any acknowledgment-based distributed algorithm minimizing the maximum flow time, where n is the number of nodes of the network. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and Systems Sciences 45 (1) (1992) 104126] we prove that the algorithm is (1+)-competitive, when the algorithm sends packets a factor O(log(δ)logΔ) faster than the optimal off-line solution; here δ is the radius of the network and Δ the maximum degree. We finally extend this result to a more complex interference model. © 2010 Elsevier B.V. All rights reserved.
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2011). The distributed wireless gathering problem. THEORETICAL COMPUTER SCIENCE, 412(8-10), 633-641 [10.1016/j.tcs.2010.10.018].
File in questo prodotto:
File Dimensione Formato  
Bonifaci2010c.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: DRM non definito
Dimensione 245.71 kB
Formato Adobe PDF
245.71 kB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/11590/381241
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact