The paper studies the problem of computing a minimal energy cost range assignment in an ad-hoc wireless network which allows a station s to perform a broadcast operation in at most h hops. The general version of the problem (i.e. when transmission costs are arbitrary) is known to be log-APX hard even for h=2. The current paper considers the well-studied real case in which n stations are located in the plane and the cost to transmit from station i to station j is proporttional to the a-th power of the distance between i and j, where a is any positive constant. A polynomial-time algorithm is presented for finding an optimal range assignment to perform a 2-hop broadcast from a given source station. The algorithm relies on dynamic programming and operates in (worst case) O(n^7) time. Then, a polynomial-time approximation scheme (PTAS) is provided for the above problem for any fixed h>=1.

Ambhl, C., Clementi, A., DI IANNI, M., Lev Tov, N., Monti, A., Peleg, D., et al. (2004). Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. In Lecture Notes in Computer Science (pp.418-427). Springer [10.1007/978-3-540-24749-4_37].

Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks

CLEMENTI, ANDREA;DI IANNI, MIRIAM;ROSSI, GIANLUCA;
2004

Abstract

The paper studies the problem of computing a minimal energy cost range assignment in an ad-hoc wireless network which allows a station s to perform a broadcast operation in at most h hops. The general version of the problem (i.e. when transmission costs are arbitrary) is known to be log-APX hard even for h=2. The current paper considers the well-studied real case in which n stations are located in the plane and the cost to transmit from station i to station j is proporttional to the a-th power of the distance between i and j, where a is any positive constant. A polynomial-time algorithm is presented for finding an optimal range assignment to perform a 2-hop broadcast from a given source station. The algorithm relies on dynamic programming and operates in (worst case) O(n^7) time. Then, a polynomial-time approximation scheme (PTAS) is provided for the above problem for any fixed h>=1.
Annual Symposium on Theoretical Aspects of Computer Science
2004
21th
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
English
Intervento a convegno
Ambhl, C., Clementi, A., DI IANNI, M., Lev Tov, N., Monti, A., Peleg, D., et al. (2004). Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. In Lecture Notes in Computer Science (pp.418-427). Springer [10.1007/978-3-540-24749-4_37].
Ambhl, C; Clementi, A; DI IANNI, M; Lev Tov, N; Monti, A; Peleg, D; Rossi, G; 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: https://hdl.handle.net/2108/58328
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact