Experimental analysis of practically efficient algorithms for bounded-hop accumulation in ad-hoc wireless networks

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.