Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2016) | last year (2015) | two years ago (2014) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Bonifaci, Vincenzo Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen dblp dblp dblp dblp Not MPG Author(s): Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen
 BibTeX cite key*: Bonifaci:2011:a

 Title
 Title*: The Distributed Wireless Gathering Problem Attachment(s): gathering-tcs.pdf (299.98 KB)

 Journal
 Journal Title*: Theoretical Computer Science Journal's URL: http://www.journals.elsevier.com/theoretical-computer-science/ Download URL for the article: http://dx.doi.org/10.1016/j.tcs.2010.10.018 Language: English

 Publisher
 Publisher's Name: Elsevier Publisher's URL: http://www.elsevier.com Publisher's Address: Amsterdam ISSN: 0304-3975

 Vol, No, pp, Date
 Volume*: 412 Number: 8-10 Publishing Date: March 2011 Pages*: 633-641 Number of VG Pages: Page Start: 633 Page End: 641 Sequence Number: DOI: 10.1016/j.tcs.2010.10.018

 Note: (LaTeX) 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 $\Omega(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) 104–126] we prove that the algorithm is $(1+\epsilon)$-competitive, when the algorithm sends packets a factor $O(\log(\delta/\epsilon) \log \Delta)$ faster than the optimal off-line solution; here $\delta$ is the radius of the network and $\Delta$ the maximum degree. We finally extend this result to a more complex interference model. URL for the Abstract: Categories, Keywords: Wireless networks, Data gathering, Approximation algorithm, Distributed algorithm, On-line algorithm, Resource augmentation HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Bonifaci:2011:a,
AUTHOR = {Bonifaci, Vincenzo and Korteweg, Peter and Marchetti-Spaccamela, Alberto and Stougie, Leen},
TITLE = {The Distributed Wireless Gathering Problem},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2011},
NUMBER = {8-10},
VOLUME = {412},
PAGES = {633--641},