On the minimum cost range assignment problem

DOI10.1007/978-3-662-48971-0_9MaRDI QIDQ3459853zbMATH OpenOpenAlexFDO

Authors Paz Carmi, Lilach Chaitman-Yerushalmi

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04533

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Communication networks in operations research (90B18)

Abstract: We study the problem of assigning transmission ranges to radio stations placed arbitrarily in a $d$-dimensional ($d$-D) Euclidean space in order to achieve a strongly connected communication network with minimum total power consumption. The power required for transmitting in range $r$ is proportional to $r^{a}lpha$, where $alpha$ is typically between $1$ and $6$, depending on various environmental factors. While this problem can be solved optimally in $1$D, in higher dimensions it is known to be $NP$-hard for any $alphageq1$. For the $1$D version of the problem, i.e., radio stations located on a line and $alphageq1$, we propose an optimal $O(n^2)$-time algorithm. This improves the running time of the best known algorithm by a factor of $n$. Moreover, we show a polynomial-time algorithm for finding the minimum cost range assignment in $1$D whose induced communication graph is a $t$-spanner, for any $tgeq1$. In higher dimensions, finding the optimal range assignment is $NP$-hard; however, it can be approximated within a constant factor. The best known approximation ratio is for the case $alpha=1$, where the approximation ratio is $1.5$. We show a new approximation algorithm with improved approximation ratio of $1.5-epsilon$, where $epsilon>0$ is a small constant.

Recommendations

• On the bounded-hop range assignment problem
• Distributed Computing - IWDC 2004
• scientific article; zbMATH DE number 1500550
• Power consumption in packet radio networks
• The minimum range assignment problem on linear radio networks

Cited in

(12)

• On the hardness of range assignment problems
• On the Hardness of Range Assignment Problems
• The minimum range assignment problem on linear radio networks
• scientific article; zbMATH DE number 1670654 (Why is no real title available?)
• Approximation algorithm for receiver interference problem in dual power wireless sensor networks
• Structural Information and Communication Complexity
• The range co-minima problem
• IMPROVED ALGORITHM FOR MINIMUM COST RANGE ASSIGNMENT PROBLEM FOR LINEAR RADIO NETWORKS
• On the bounded-hop range assignment problem
• Distributed Computing - IWDC 2004
• scientific article; zbMATH DE number 1787233 (Why is no real title available?)
• Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks

This page was built for publication: On the minimum cost range assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459853)