Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(12)
Approximate Algorithm
Competitive Ratio
Data Gathering
Distributed Algorithm
Maximum Degree
Maximum Flow
Online Algorithm
Radio Networks
Time Complexity
Wireless Network
Lower Bound
Shortest Path
Subscribe
Academic
Publications
The distributed wireless gathering problem
The distributed wireless gathering problem,10.1016/j.tcs.2010.10.018,Theoretical Computer Science,Vincenzo Bonifaci,Peter Korteweg,Alberto MarchettiS
Edit
The distributed wireless gathering problem
BibTex

RIS

RefWorks
Download
Vincenzo Bonifaci
,
Peter Korteweg
,
Alberto MarchettiSpaccamela
,
Leen Stougie
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 Ω(n) on the expected
competitive ratio
of any acknowledgmentbased
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 BarYehuda et al. [R. BarYehuda, O. Goldreich, A. Itai, On the
time complexity
of broadcast in multihop 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+ϵ)competitive, when the algorithm sends packets a factor O(log(δ/ϵ)logΔ) faster than the optimal offline solution; here δ is the radius of the network and Δ the maximum degree. We finally extend this result to a more complex interference model.
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 810, pp. 633641, 2011
DOI:
10.1016/j.tcs.2010.10.018
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
References
(16)
Wireless sensor networks: a survey
(
Citations: 4085
)
Ian F. Akyildiz
,
Weilian Su
,
Yogesh Sankarasubramaniam
,
Erdal Cayirci
Journal:
Computer Networks  COMPUT NETW
, vol. 38, no. 4, pp. 393422, 2002
On the TimeComplexity of Broadcast in Multihop Radio Networks: An Exponential Gap Between Determinism and Randomization
(
Citations: 206
)
Reuven Baryehuda
,
Oded Goldreich
,
Alon Itai
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 45, no. 1, pp. 104126, 1992
Multiple Communication in Multihop Radio Networks
(
Citations: 65
)
Reuven Baryehuda
,
Amos Israeli
,
Alon Itai
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 22, no. 4, pp. 875887, 1993
Optimal gathering protocols on paths under interference constraints
(
Citations: 4
)
JeanClaude Bermond
,
Ricardo C. Corrêa
,
MinLi Yu
Journal:
Discrete Mathematics  DM
, vol. 309, no. 18, pp. 55745587, 2009
Hardness and approximation of Gathering in static radio networks
(
Citations: 35
)
Jeanclaude Bermond
,
Nelson Morales
,
Stéphane Pérennes
,
Jérôme Galtier
,
Ralf Klasing
Conference:
IEEE International Conference on Pervasive Computing and Communications
, vol. 16, no. 2, pp. 7579, 2006