loading...
Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks
Denver, Colorado April 04-April 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2005.21019th IEEE International Parallel and ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Andrea E. F. Clementi, Universit? degli Studi di Roma "Tor Vergata"
Miriam Di Ianni, Universit? degli Studi di Roma "Tor Vergata"
Angelo Monti, Universit? degli Studi di Roma "La Sapienza"
Gianluca Rossi, Universit? degli Studi di Roma "Tor Vergata"
Riccardo Silvestri, Universit? degli Studi di Roma "La Sapienza"
The paper studies the problem of computing a minimal energy-cost range assignment in an ad-hoc wireless network which allows a set S of stations located in the 2-dimensional Euclidean space to perform accumulation (all-to-one) operations towards some root station b in at most h hops (2-Dim Min h-Accumulation Range Assignment problem).
We experimentally investigate the behavior of fast and easy-to-implement heuristics for the 2-Dim Min h-Accumulation Range Assignment problem on instances obtained by choosing at random n points in a square of side length L. We compare the performance of an easy-to-implement, very fast heuristic with those of three simple heuristics based on classical greedy algorithms (Prim's and Kruskal's ones) defined for the Minimum Spanning Tree problem. The comparison is carried out over thousands of random instances in several different situations depending on: the distribution of the stations in the plane, their density, the energy cost function.
Citation:
Andrea E. F. Clementi, Miriam Di Ianni, Angelo Monti, Gianluca Rossi, Riccardo Silvestri, "Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks," ipdps, vol. 13, pp.247a, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, 2005
Usage of this product signifies your acceptance of the Terms of Use.