Given a finite set S of points (i.e. the stations of a radio network) on the plane and a positive integer 1 ≤ h ≤ |S| − 1, the 2d Min h R. Assign. problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption provided that the transmission ranges of the stations ensure the communication between any pair of stations in at most h hops. We provide a lower bound on the total power consumption opth(S) yielded by an optimal range assignment for any instance (S, h) of 2d Min h R. Assign., for any positive constant h > 0. The lower bound is a function of |S|, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound for the same problem as a function of |S|, h and the maximum distance over all the pairs of stations in S (i.e. the diameter of S). Finally, by combining the above bounds, we obtain a polynomial-time approximation algorithm for 2d Min h R. Assign. restricted to well-spread instances, for any positive constant h. Previous results for this problem were known only in special 1-dimensional configurations (i.e. when points are arranged on a line).

Clementi, A., Penna, P., Silvestri, R. (2000). The Power Range Assignment Problem in Radio Networks on the Plane. In {STACS} 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings. Springer.

The Power Range Assignment Problem in Radio Networks on the Plane

CLEMENTI, ANDREA
Membro del Collaboration Group
;
2000-02-01

Abstract

Given a finite set S of points (i.e. the stations of a radio network) on the plane and a positive integer 1 ≤ h ≤ |S| − 1, the 2d Min h R. Assign. problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption provided that the transmission ranges of the stations ensure the communication between any pair of stations in at most h hops. We provide a lower bound on the total power consumption opth(S) yielded by an optimal range assignment for any instance (S, h) of 2d Min h R. Assign., for any positive constant h > 0. The lower bound is a function of |S|, h and the minimum distance over all the pairs of stations in S. Then, we derive a constructive upper bound for the same problem as a function of |S|, h and the maximum distance over all the pairs of stations in S (i.e. the diameter of S). Finally, by combining the above bounds, we obtain a polynomial-time approximation algorithm for 2d Min h R. Assign. restricted to well-spread instances, for any positive constant h. Previous results for this problem were known only in special 1-dimensional configurations (i.e. when points are arranged on a line).
STACS 2000
2000
Rilevanza internazionale
contributo
feb-2000
Settore INF/01 - INFORMATICA
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Approximation Algorithms; Lower Bounds; Multi-Hop Packet Radio Networks; Power Consumption
Intervento a convegno
Clementi, A., Penna, P., Silvestri, R. (2000). The Power Range Assignment Problem in Radio Networks on the Plane. In {STACS} 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings. Springer.
Clementi, A; Penna, P; 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/13234
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 70
  • ???jsp.display-item.citation.isi??? 50
social impact