The ``Real" Approximation Factor of the MST heuristic for the Minimum Energy Broadcasting

This paper deals with one of the most studied problems in the last few years in the field of wireless communication in ad-hoc networks. The problem consists of reducing the total energy consumption of wireless radio stations distributed over a given area of interest in order to perform the basic pattern of communication by a broadcast. Recently, a tight 6-approximation of the minimum spanning tree heuristic has been proven. While such a bound is theoretically optimal if compared to the known lower bound of 6, there is an obvious gap with practical experimental results. By extensive experiments, proposing a new technique to generate input instances and supported by theoretical results, we show how the approximation ratio can be actually considered close to 4 for a “real-world” set of instances. We consider, in fact, instances more representative of common practices. Those are usually composed by considerable number of nodes uniformly and randomly distributed inside the area of interest.