We consider the problem of computing an optimal range assignment in a wireless network which allows a specified source station to perform a broad- cast operation. In particular, we consider this problem as a special case of the following more general combinatorial optimization problem, called Minimum Energy Consumption Broadcast Subgraph (in short, MECBS): Given a weighted directed graph and a specified source node, find a minimum cost range assignment to the nodes, whose corresponding transmission graph contains a spanning tree rooted at the source node. We first prove that MECBS is not approximable within a sub-logarithmic factor (unless P=NP).We then consider the restriction of MECBS to wireless networks and we prove several positive and negative results, depending on the geometric space dimension and on the distance-power gradient. The main result is a polynomial-time approximation algorithm for the NP-hard case in which both the dimension and the gradient are equal to 2: This algorithm can be generalized to the case in which the gradient is greater than or equal to the dimension.
ON THE COMPLEXITY OF COMPUTING MINIMUM ENERGY CONSUMPTION BROADCAST SUBGRAPHS / P. CRESCENZI; P. PENNA; G. ROSSI; A. CLEMENTI; P. VOCCA. - STAMPA. - (2001), pp. 121-131. (Intervento presentato al convegno 18TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (LECTURE NOTES IN COMPUTER SCIENCE)) [10.1007/3-540-44693-1_11].
ON THE COMPLEXITY OF COMPUTING MINIMUM ENERGY CONSUMPTION BROADCAST SUBGRAPHS
CRESCENZI, PIERLUIGI;
2001
Abstract
We consider the problem of computing an optimal range assignment in a wireless network which allows a specified source station to perform a broad- cast operation. In particular, we consider this problem as a special case of the following more general combinatorial optimization problem, called Minimum Energy Consumption Broadcast Subgraph (in short, MECBS): Given a weighted directed graph and a specified source node, find a minimum cost range assignment to the nodes, whose corresponding transmission graph contains a spanning tree rooted at the source node. We first prove that MECBS is not approximable within a sub-logarithmic factor (unless P=NP).We then consider the restriction of MECBS to wireless networks and we prove several positive and negative results, depending on the geometric space dimension and on the distance-power gradient. The main result is a polynomial-time approximation algorithm for the NP-hard case in which both the dimension and the gradient are equal to 2: This algorithm can be generalized to the case in which the gradient is greater than or equal to the dimension.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
