We address the problem of data gathering in a wireless network using multihop 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 Ω(logm) on the competitive ratio of any distributed algorithm minimizing the maximum flow time, where m is the number of packets. 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. (J. of Computer and Systems Science, 1992) we prove that the algorithm is (1∈+∈ε)-competitive, when the algorithm sends packets a factor O(log(δ/ε) logΔ) faster than the optimal offline solution; here δ is the diameter of the network and Δ the maximum degree. We finally extend this result to a more complex interference model. © 2008 Springer-Verlag Berlin Heidelberg.

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). The distributed wireless gathering problem. In Proc. 4th Conf. on Algorithmic Aspects of Information Management (pp.72-83). Berlin : Springer [10.1007/978-3-540-68880-8_9].

The distributed wireless gathering problem

Bonifaci V.;
2008-01-01

Abstract

We address the problem of data gathering in a wireless network using multihop 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 Ω(logm) on the competitive ratio of any distributed algorithm minimizing the maximum flow time, where m is the number of packets. 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. (J. of Computer and Systems Science, 1992) we prove that the algorithm is (1∈+∈ε)-competitive, when the algorithm sends packets a factor O(log(δ/ε) logΔ) faster than the optimal offline solution; here δ is the diameter of the network and Δ the maximum degree. We finally extend this result to a more complex interference model. © 2008 Springer-Verlag Berlin Heidelberg.
2008
978-3-540-68865-5
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). The distributed wireless gathering problem. In Proc. 4th Conf. on Algorithmic Aspects of Information Management (pp.72-83). Berlin : Springer [10.1007/978-3-540-68880-8_9].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11590/379880
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
social impact