Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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


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, Abstract, ©

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},
ADDRESS = {Amsterdam},
MONTH = {March},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2010.10.018},
}


Entry last modified by Anja Becker, 02/01/2012
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
gathering-tcs.pdf