The distributed wireless gathering problem

V. Bonifaci, P. Korteweg, A. Marchetti Spaccamela, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)633-641
JournalTheoretical Computer Science
Volume412
Issue number8-10
DOIs
Publication statusPublished - 2011

Fingerprint

Flow Time
Distributed Algorithms
Parallel algorithms
Interference
Resource Augmentation
Wireless multi-hop Networks
Determinism
Radio Networks
Systems science
Maximum Flow
Competitive Ratio
Multi-hop
Randomisation
Maximum Degree
Shortest path
Broadcast
Computer science
Time Complexity
Wireless networks
Radius

Cite this

Bonifaci, V., Korteweg, P., Marchetti Spaccamela, A., & Stougie, L. (2011). The distributed wireless gathering problem. Theoretical Computer Science, 412(8-10), 633-641. https://doi.org/10.1016/j.tcs.2010.10.018
Bonifaci, V. ; Korteweg, P. ; Marchetti Spaccamela, A. ; Stougie, L. / The distributed wireless gathering problem. In: Theoretical Computer Science. 2011 ; Vol. 412, No. 8-10. pp. 633-641.
@article{aeac273ad73e42038a26689020b4fe2a,
title = "The distributed wireless gathering problem",
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. {\circledC} 2010 Elsevier B.V. All rights reserved.",
author = "V. Bonifaci and P. Korteweg and {Marchetti Spaccamela}, A. and L. Stougie",
year = "2011",
doi = "10.1016/j.tcs.2010.10.018",
language = "English",
volume = "412",
pages = "633--641",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "8-10",

}

Bonifaci, V, Korteweg, P, Marchetti Spaccamela, A & Stougie, L 2011, 'The distributed wireless gathering problem' Theoretical Computer Science, vol. 412, no. 8-10, pp. 633-641. https://doi.org/10.1016/j.tcs.2010.10.018

The distributed wireless gathering problem. / Bonifaci, V.; Korteweg, P.; Marchetti Spaccamela, A.; Stougie, L.

In: Theoretical Computer Science, Vol. 412, No. 8-10, 2011, p. 633-641.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - The distributed wireless gathering problem

AU - Bonifaci, V.

AU - Korteweg, P.

AU - Marchetti Spaccamela, A.

AU - Stougie, L.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1016/j.tcs.2010.10.018

DO - 10.1016/j.tcs.2010.10.018

M3 - Article

VL - 412

SP - 633

EP - 641

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 8-10

ER -