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. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum Energy Broadcast problem on square grids. We emphasize that 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 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 Ω(√n) hops. 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. © Springer-Verlag Berlin Heidelberg 2006.

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. - STAMPA. - 4056 LNCS:(2006), pp. 227-239. (Intervento presentato al convegno 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006 tenutosi a Chester nel 2 July 2006 through 5 July 2006) [10.1007/11780823_18].

Minimum energy broadcast and disk cover in grid wireless networks

CALAMONERI, Tiziana;LAURIA, MASSIMO;MONTI, Angelo;SILVESTRI, RICCARDO
2006

Abstract

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. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum Energy Broadcast problem on square grids. We emphasize that 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 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 Ω(√n) hops. 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. © Springer-Verlag Berlin Heidelberg 2006.
2006
13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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. - STAMPA. - 4056 LNCS:(2006), pp. 227-239. (Intervento presentato al convegno 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006 tenutosi a Chester nel 2 July 2006 through 5 July 2006) [10.1007/11780823_18].
File allegati a 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/11573/366304
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact