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.

Calamoneri, T., Clementi, A., Di Ianni, M., Lauria, M., Monti, A., & Silvestri, R. (2006). Minimum-Energy Broadcast and disk cover in grid wireless networks. In Structural information and communication complexity: 13th International colloquium, SIROCCO 2006: proceedings (pp.227-239). AMSTERDAM : Springer [10.1016/j.tcs.2008.02.005].

Minimum-Energy Broadcast and disk cover in grid wireless networks

CLEMENTI, ANDREA;DI IANNI, MIRIAM;
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.
International colloquium on structural information and communication complexity (SIROCCO 2006)
Chester (Great Britain)
2006
13.
Rilevanza internazionale
contributo
2006
Settore INF/01 - Informatica
English
ad hoc wireless networks; broadcast problem; disk cover problem; overall energy minimization; range assignment
Intervento a convegno
Calamoneri, T., Clementi, A., Di Ianni, M., Lauria, M., Monti, A., & Silvestri, R. (2006). Minimum-Energy Broadcast and disk cover in grid wireless networks. In Structural information and communication complexity: 13th International colloquium, SIROCCO 2006: proceedings (pp.227-239). AMSTERDAM : Springer [10.1016/j.tcs.2008.02.005].
Calamoneri, T; Clementi, A; DI IANNI, M; Lauria, M; Monti, A; Silvestri, R
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: http://hdl.handle.net/2108/57384
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact