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'sand 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.
Experimental analysis of practically efficient algorithms for bounded-hop accumulation in ad-hoe wireless networks / A. E. F., Clementi; M., Di Ianni; G., Rossi; Monti, Angelo; Silvestri, Riccardo. - 2005:(2005). (Intervento presentato al convegno 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005 tenutosi a Denver, CO nel 4 April 2005 through 8 April 2005) [10.1109/ipdps.2005.210].
Experimental analysis of practically efficient algorithms for bounded-hop accumulation in ad-hoe wireless networks
MONTI, Angelo;SILVESTRI, RICCARDO
2005
Abstract
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'sand 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
