Paper Info
Title
A distributed protocol for the bounded-hops converge-cast in ad-hoc networks
Abstract
Given a set S of points (stations) located in the d-dim. Euclidean space and a rootb ∈S, the h-hops Convergecast problem asks to find for a minimal energy-cost range assignment which allows to perform the converge-cast primitive (i.e. node accumulation) towards b in at most h hops. For this problem no polynomial time algorithm is known even for h = 2. The main goal of this work is the design of an efficient distributed heuristic (i.e. protocol) and the analysis (both theoretical and experimental) of its expected solution cost. In particular, we introduce an efficient parameterized randomized protocol for h-hops Convergecast and we analyze it on random instances created by placing n points uniformly at random in a d-cube of side length L. We prove that for h = 2, its expected approximation ratio is bounded by some constant factor. Finally, for h = 3,..., 8, we provide a wide experimental study showing that our protocol has very good performances when compared with previously introduced (centralized) heuristics.
Year
DOI
Venue
2006
10.1007/11814764_7
ADHOC-NOW
Keywords
Field
DocType
constant factor,random instance,h-hops convergecast problem,good performance,h-hops convergecast,expected approximation ratio,wide experimental study,ad-hoc network,efficient parameterized randomized protocol,bounded-hops converge-cast,expected solution cost,euclidean space,ad hoc network
Discrete mathematics,Randomized algorithm,Parameterized complexity,Heuristic,Computer science,Euclidean space,Heuristics,Wireless ad hoc network,Time complexity,Bounded function
Conference
Volume
ISSN
ISBN
4104
0302-9743
3-540-37246-6
Citations 
PageRank 
References 
2
0.40
21
Authors
6
Name
Order
Citations
PageRank
Andrea E. F. Clementi1116885.30
Miriam di Ianni214417.27
Massimo Lauria312214.73
Angelo Monti467146.93
Gianluca Rossi523521.60
Riccardo Silvestri6132490.84