Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks
The Minimum Energy Broadcast problem consists in finding
the minimum-energy range assignment for a given set S of n
stations of an ad hoc wireless network that allows a source
station to perform broadcast operations over S.
\noindent We prove an almost tight asymptotical bound on the
optimal cost for the Minimum Energy Broadcast problem on square
grids. We emphasize finding tight bounds for this problem
restriction is far to be easy: it involves the Gauss's
Circle problem and the Apollonian Circle Packing. We also
derive near-tight bounds for the Bounded-Hop version of the
this problem. The obtained results show that the best-known
heuristic, the MST-based one, for the Minimum Energy Broadcast
problem is far to achieve optimal solutions (even) on very
regular, well-spread instances: its approximation ratio is about
\pi and it yields Omega(\sqrt{n}) hops.
As a by product, we get almost tight bounds for the
Minimum Disk Cover problem and for its restriction
in which allowed disks must have non-constant
radius.
Finally, we emphasize that our upper bounds are
polynomial-time constructible.
Conference Version
JournalVersion