The Minimum-Energy Broadcast problem is to assign a transmission range to every station of an ad hoc wireless networks so that (i) a given source station is allowed to perform broadcast operations and (ii) the overall energy consumption of the range assignment is minimized. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum-Energy Broadcast problem on square grids. We also derive near-tight bounds for the Bounded-Hop version of this problem. Our results imply 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 worst-case approximation ratio is about pi and it yields Omega(root n) hops, where n is the number of stations. As a by product, we get nearly tight bounds for the Minimum-Disk Cover problem and for its restriction in which the allowed disks must have non-constant radius. Finally, we emphasize that our upper bounds are obtained via polynomial time constructions. (C) 2008 Published by Elsevier B.V.
Minimum-Energy Broadcast and disk cover in grid wireless networks / Calamoneri, Tiziana; Andrea E. F., Clementi; Miriam Di, Ianni; Lauria, Massimo; Monti, Angelo; Silvestri, Riccardo. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 399:1-2(2008), pp. 38-53. (Intervento presentato al convegno 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2006) tenutosi a Chester, ENGLAND nel JUL 02, 2006-JUL 05, 3006) [10.1016/j.tcs.2008.02.005].
Minimum-Energy Broadcast and disk cover in grid wireless networks
CALAMONERI, Tiziana;LAURIA, MASSIMO;MONTI, Angelo;SILVESTRI, RICCARDO
2008
Abstract
The Minimum-Energy Broadcast problem is to assign a transmission range to every station of an ad hoc wireless networks so that (i) a given source station is allowed to perform broadcast operations and (ii) the overall energy consumption of the range assignment is minimized. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum-Energy Broadcast problem on square grids. We also derive near-tight bounds for the Bounded-Hop version of this problem. Our results imply 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 worst-case approximation ratio is about pi and it yields Omega(root n) hops, where n is the number of stations. As a by product, we get nearly tight bounds for the Minimum-Disk Cover problem and for its restriction in which the allowed disks must have non-constant radius. Finally, we emphasize that our upper bounds are obtained via polynomial time constructions. (C) 2008 Published by Elsevier B.V.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
