Article

The Power Range Assignment Problem in Radio Networks on the Plane

Authors:

Andrea E. F. Clementi,

Paolo Penna,

Riccardo SilvestriAuthors Info & Claims

STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science

Pages 651 - 660

Published: 01 February 2000 Publication History

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 opt_h(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).

References

[1]

E. Arikan, "Some Complexity Results about Packet Radio Networks", IEEE Transactions on Information Theory, 456-461, IT-30, 1984.

Google Scholar

[2]

A.E.F. Clementi, P. Penna, and R. Silvestri, "Hardness Results for the Power Range Assignment Problem in Packet Radio Networks", II InternationalWorkshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'99), LNCS, 1671, 1999.

Crossref

Google Scholar

[3]

A. Ephemides and T. Truong, "Scheduling Broadcast in Multihop Radio Networks", IEEE Transactions on Communications, 456-461, 30, 1990.

Google Scholar

[4]

L. M. Kirousis and E. Kranakis and D. Krizanc and A. Pelc, "Power Consumption in Packet Radio Networks", 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS 97), LNCS 1200, 363-374, 1997 (to appear also in TCS).

Crossref

Google Scholar

[5]

C.H. Papadimitriou, "Computational Complexity", Addison-Wesley Publishing Company, Inc., 1995.

Google Scholar

[6]

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

Crossref

Google Scholar

[7]

S. Ramanathan and E. Lloyd, "Scheduling Broadcasts in Multi-hop Radio Networks" IEEE/ACM Transactions on Networking, 166-172, 1, 1993.

Crossref

Google Scholar

[8]

R. Ramaswami and K. Parhi, "Distributed Scheduling of Broadcasts in Radio Network", INFOCOM'89, 497-504, 1989.

Google Scholar

Cited By

View all

Ruiz PBouvry P(2015)Survey on Broadcast Algorithms for Mobile Ad Hoc NetworksACM Computing Surveys10.1145/278600548:1(1-35)Online publication date: 22-Jul-2015
https://dl.acm.org/doi/10.1145/2786005
Panigrahi DRandall D(2011)Survivable network design problems in wireless networksProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133114(1014-1027)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133114
Luo WWang JFeng QGuo J(2011)The min-power multicast problems in wireless ad hoc networksProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021932(156-167)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021932
Show More Cited By

Index Terms

The Power Range Assignment Problem in Radio Networks on the Plane
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Networks
  1. Network types
    1. Mobile networks

Index terms have been assigned to the content through auto-classification.

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 ...
The Minimum Range Assignment Problem on Linear Radio Networks
ESA '00: Proceedings of the 8th Annual European Symposium on Algorithms

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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science

February 2000

661 pages

ISBN:3540671412

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ruiz PBouvry P(2015)Survey on Broadcast Algorithms for Mobile Ad Hoc NetworksACM Computing Surveys10.1145/278600548:1(1-35)Online publication date: 22-Jul-2015
https://dl.acm.org/doi/10.1145/2786005
Panigrahi DRandall D(2011)Survivable network design problems in wireless networksProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133114(1014-1027)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133114
Luo WWang JFeng QGuo J(2011)The min-power multicast problems in wireless ad hoc networksProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021932(156-167)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021932
Zhao LLloyd ERavi S(2010)Topology control in constant rate mobile ad hoc networksWireless Networks10.1007/s11276-008-0147-916:2(467-480)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1007/s11276-008-0147-9
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
Chiganmi ABaysan MSarac KPrakash R(2008)Variable power broadcast using local information in ad hoc networksAd Hoc Networks10.1016/j.adhoc.2007.06.0026:5(675-695)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1016/j.adhoc.2007.06.002
Lloyd ELiu RRavi S(2006)Approximating the minimum number of maximum power users in ad hoc networksMobile Networks and Applications10.1007/s11036-006-4467-711:2(129-142)Online publication date: 1-Apr-2006
https://dl.acm.org/doi/10.1007/s11036-006-4467-7
Calinescu GWan P(2006)Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networksMobile Networks and Applications10.1007/s11036-006-4466-811:2(121-128)Online publication date: 1-Apr-2006
https://dl.acm.org/doi/10.1007/s11036-006-4466-8
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
Lloyd ELiu RMarathe MRamanathan RRavi S(2005)Algorithmic aspects of topology control problems for ad hoc networksMobile Networks and Applications10.5555/1046430.104643310:1-2(19-34)Online publication date: 1-Feb-2005
https://dl.acm.org/doi/10.5555/1046430.1046433
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

On the power assignment problem in radio networks

The Minimum Range Assignment Problem on Linear Radio Networks

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

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations