Access Restriction

Author Flammini, Michele ♦ Navarra, Alfredo ♦ Perennes, Stephane
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Ad-hoc networks ♦ Broadcast ♦ Energy saving ♦ Spanning tree
Abstract 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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-02-09
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 11

Open content in new tab

   Open content in new tab
Source: ACM Digital Library