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 π and it yields View the MathML source 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.

Calamoneri, T., Clementi, A., DI IANNI, M., Lauria, M., Monti, A., Silvestri, R. (2008). Minimum-energy broadcast and disk cover in grid wireless networks. THEORETICAL COMPUTER SCIENCE, 399(1-2), 38-53 [10.1016/j.tcs.2008.02.005].

Minimum-energy broadcast and disk cover in grid wireless networks

CLEMENTI, ANDREA;DI IANNI, MIRIAM;
2008-06-01

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 π and it yields View the MathML source 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.
1-giu-2008
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Ad hoc wireless networks; Broadcast problem; Disk cover problem; Overall energy minimization; Range assignment
Calamoneri, T., Clementi, A., DI IANNI, M., Lauria, M., Monti, A., Silvestri, R. (2008). Minimum-energy broadcast and disk cover in grid wireless networks. THEORETICAL COMPUTER SCIENCE, 399(1-2), 38-53 [10.1016/j.tcs.2008.02.005].
Calamoneri, T; Clementi, A; DI IANNI, M; Lauria, M; Monti, A; Silvestri, R
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/18928
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact