The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n × √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. By using information-theoretic arguments, we prove a lower bound (1-ε) n/π on the energy cost of any feasible solution for this problem. Then, we provide an efficient solution of energy cost not larger than 1.1204 n/π Finally, we present a fully-distributed protocol that constructs a broadcast range assignment of energy cost not larger than 8n, thus still yielding constant approximation. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is asymptotically optimal. The completion time of the protocol is only a 0(log n)factor slower than the optimum. The approximation quality of our distributed solution is also experimentally evaluated. All bounds hold with probability at least 1-1/n⊖ (1). Copyright 2008 ACM.

Minimum-energy broadcast in random-grid Ad-Hoc Networks: Approximation and distributed algorithms / Calamoneri, Tiziana; Andrea E. F., Clementi; Monti, Angelo; Gianluca, Rossi; Silvestri, Riccardo. - STAMPA. - (2008), pp. 354-361. (Intervento presentato al convegno 11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, MSWiM'08 tenutosi a Vancouver, BC nel 27 October 2008 through 31 October 2008) [10.1145/1454503.1454563].

Minimum-energy broadcast in random-grid Ad-Hoc Networks: Approximation and distributed algorithms

CALAMONERI, Tiziana;MONTI, Angelo;SILVESTRI, RICCARDO
2008

Abstract

The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n × √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. By using information-theoretic arguments, we prove a lower bound (1-ε) n/π on the energy cost of any feasible solution for this problem. Then, we provide an efficient solution of energy cost not larger than 1.1204 n/π Finally, we present a fully-distributed protocol that constructs a broadcast range assignment of energy cost not larger than 8n, thus still yielding constant approximation. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is asymptotically optimal. The completion time of the protocol is only a 0(log n)factor slower than the optimum. The approximation quality of our distributed solution is also experimentally evaluated. All bounds hold with probability at least 1-1/n⊖ (1). Copyright 2008 ACM.
2008
11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, MSWiM'08
approximation algorithms; distributed algorithms; probabilistic analysis; range assignment problems
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Minimum-energy broadcast in random-grid Ad-Hoc Networks: Approximation and distributed algorithms / Calamoneri, Tiziana; Andrea E. F., Clementi; Monti, Angelo; Gianluca, Rossi; Silvestri, Riccardo. - STAMPA. - (2008), pp. 354-361. (Intervento presentato al convegno 11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, MSWiM'08 tenutosi a Vancouver, BC nel 27 October 2008 through 31 October 2008) [10.1145/1454503.1454563].
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/227823
 Attenzione

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

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