Article

The Minimum Range Assignment Problem on Linear Radio Networks

Authors:

Andrea E. F. Clementi,

Afonso Ferreira,

Paolo Penna,

Stephane Perennes,

Riccardo SilvestriAuthors Info & Claims

ESA '00: Proceedings of the 8th Annual European Symposium on Algorithms

Pages 143 - 154

Published: 05 September 2000 Publication History

Abstract

Given a set S of radio stations located on a line and an integer h (1 ≤ h ≤ |S| - 1), the Min Assignment problem is to find a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem were known only when h = |S| - 1 (i.e. the unbounded case) or when the stations are equally spaced (i.e. the uniform chain). In particular, Kirousis, Kranakis, Krizanc and Pelc (1997) provided an efficient exact solution for the unbounded case and efficient approximated solutions for the uniform chain, respectively.

This paper presents the first polynomial time, approximation algorithm for the Min Assignment problem. The algorithm guarantees an approximation ratio of 2 and runs in time O(hn³).

We also prove that, for constant h and for "well spread" instances (a broad generalization of the uniform chain case), we can find a solution in time O(hn³) whose cost is at most an (1 + Ɛ(n)) factor from the optimum, where Ɛ(n) = o(1) and n is the number of stations. This result significantly improves the approximability result by Kirousis et al on uniform chains.

Both of our approximation results are obtained by new algorithms that exactly solves two natural variants of the Min Assignment problem that might have independent interest: the All-To-One problem (in which every station must reach a fixed one in at most h hops) and the Base Location problem (in which the goal is to select a set of Basis among the stations and all the other stations must reach one of them in at most h -1 hops).

Finally, we show that for h = 2 the Min Assignment problem can be solved in O(n³)-time.

References

[1]

S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the euclidean k-medians and related problem. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pages 106-113, 1998.

Crossref

Google Scholar

[2]

M.A. Bassiouni and C. Fang. Dynamic channel allocation for linear macrocellular topology. Proc. of ACM Symp. on Applied Computing (SAC), pages 382-388, 1998.

Crossref

Google Scholar

[3]

A. Clementi, P. Penna, and R. Silvestri. Hardness results for the power range assignment problem in packet radio networks. Proc. of RANDOM-APPROX'99, Randomization, Approximation and Combinatorial Optimization, LNCS(1671):197 -208, 1999.

Crossref

Google Scholar

[4]

A. Clementi, P. Penna, and R. Silvestri. The power range assignment problem in radio networks on the plane. 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS(1770):651-660, 2000.

Crossref

Google Scholar

[5]

K. Diks, E. Kranakis, D. Krizanc, and A. Pelc. The impact of knowledge on broadcasting time in radio networks. Proc. 7th European Symp. on Algorithms (ESA), LNCS(1643):41-52, 1999.

Crossref

Google Scholar

[6]

D. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148-162, 1982.

Google Scholar

[7]

L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet radio networks. 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS(1200):363-374, 1997.

Crossref

Google Scholar

[8]

E. Kranakis, D. Krizanc, and A. Pelc. Fault-tolerant broadcasting in radio networks. 6th European Symp. on Algorithms (ESA), LNCS(1461):283-294, 1998.

Google Scholar

[9]

R. Mathar and J. Mattfeldt. Optimal transmission ranges for mobile communication in linear multihop packet radio netwoks. Wireless Networks, 2:329-342, 1996.

Crossref

Google Scholar

[10]

K. Pahlavan and A. Levesque. Wireless Information Networks. Wiley-Interscince, New York, 1995.

Crossref

Google Scholar

[11]

P. Piret. On the connectivity of radio networks. IEEE Trans. on Infor. Theory, 37:1490-1492, 1991.

Google Scholar

[12]

S. Ulukus and R.D. Yates. Stochastic power control for cellular radio systems. IEEE Trans. Commun., 46(6):784-798, 1998.

Google Scholar

Cited By

View all

Shpungin HSegal M(2009)Low-energy fault-tolerant bounded-hop broadcast in wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2009.201465317:2(582-590)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014653
Kantor EPeleg D(2009)Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problemsJournal of Discrete Algorithms10.1016/j.jda.2008.11.0067:3(341-362)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.jda.2008.11.006
Calinescu GKapoor SSarwat M(2006)Bounded-hops power assignment in ad hoc wireless networksDiscrete Applied Mathematics10.5555/1144327.1705288154:9(1358-1371)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.5555/1144327.1705288
Show More Cited By

The Minimum Range Assignment Problem on Linear Radio Networks
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the power assignment problem in radio networks
Discrete algorithms and methods for mobile computing and communications

Given a finite set S of points (i.e. the stations of a radio network) on a d-dimensional Euclidean space and a positive integer 1 ≤ h ≤ |S| - 1, the MIN d D h-RANGE ASSIGNMENT problem consists of assigning transmission ranges to the stations so as to ...
High-Priority Minimum-Interference Channel Assignment in Multi-Radio Multi-Channel Wireless Networks
ICTCE '18: Proceedings of the 2nd International Conference on Telecommunications and Communication Engineering

Wireless network nodes equipping multi-radio interfaces on each node and using multi-channel for transmission can greatly enhance the network performance. In this paper, we study the channel assignment problem in the multi-radio multi-channel wireless ...
On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms

The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the $\mbi d$ -dimensional Euclidean space $\mbi {\BBR^d}$ ($\mbi d$ -RSP), for a given set $\mbi S$ of $\mbi n$ points in $\mbi {\BBR^d}$ and a positive integer $\mbi k$ , ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ESA '00: Proceedings of the 8th Annual European Symposium on Algorithms

September 2000

448 pages

ISBN:354041004X

Editor:
Mike Paterson

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shpungin HSegal M(2009)Low-energy fault-tolerant bounded-hop broadcast in wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2009.201465317:2(582-590)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014653
Kantor EPeleg D(2009)Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problemsJournal of Discrete Algorithms10.1016/j.jda.2008.11.0067:3(341-362)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.jda.2008.11.006
Calinescu GKapoor SSarwat M(2006)Bounded-hops power assignment in ad hoc wireless networksDiscrete Applied Mathematics10.5555/1144327.1705288154:9(1358-1371)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.5555/1144327.1705288
Ingelrest FSimplot-Ryl DStojmenovic I(2006)Optimal Transmission Radius for Energy Efficient Broadcasting Protocols in Ad Hoc and Sensor NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2006.7417:6(536-547)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1109/TPDS.2006.74
Peleg D(2006)Recent advances on approximation algorithms for minimum energy range assignment problems in ad-hoc wireless networksProceedings of the Third international conference on Combinatorial and Algorithmic Aspects of Networking10.1007/11922377_1(1-4)Online publication date: 2-Jul-2006
https://dl.acm.org/doi/10.1007/11922377_1
Shpungin HSegal MBanerjee SGanguly S(2005)k-fault resistance in wireless ad-hoc networksProceedings of the 2005 joint workshop on Foundations of mobile computing10.1145/1080810.1080826(89-96)Online publication date: 2-Sep-2005
https://dl.acm.org/doi/10.1145/1080810.1080826
Hajiaghayi MImmorlica NMirrokni VJohnson DJoseph AVaidya N(2003)Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networksProceedings of the 9th annual international conference on Mobile computing and networking10.1145/938985.939016(300-312)Online publication date: 14-Sep-2003
https://dl.acm.org/doi/10.1145/938985.939016
Santi PBlough D(2003)The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2003.11951492:1(25-39)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/TMC.2003.1195149

Abstract

References

Cited By

Recommendations

On the power assignment problem in radio networks

High-Priority Minimum-Interference Channel Assignment in Multi-Radio Multi-Channel Wireless Networks

On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations