skip to main content
10.1145/1288107.1288122acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
Article

Complexity in geometric SINR

Published: 09 September 2007 Publication History

Abstract

In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem.

References

[1]
A. Behzad and I. Rubin. On the Performance of Graph-based Scheduling Algorithms for Packet Radio Networks. In Proc. of the IEEE Global Telecommunications Conference (GLOBECOM), 2003.
[2]
A. Behzad and I. Rubin. Impact of Power Control on the Performance of Ad Hoc Wireless Networks. In Proc. of the 24th INFOCOM, 2005.
[3]
P. Björklund, P. Värbrand, and D. Yuan. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Networks, 2(4):405--418, 2004.
[4]
A. Borbash, S. A. ;Ephremides. Wireless link scheduling with power control and sinr constraints. Information Theory, IEEE Transactions on, 52(5):5106--5111, 2006.
[5]
G. Brar, D. Blough, and P. Santi. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In Proc. of the 12th International Conference on Mobile Computing and Networking (MOBICOM), 2006.
[6]
R. Cruz and A. Santhanam. Optimal routing, link scheduling and power control in multi-hop wireless networks, 2003.
[7]
A. Ephremides and T. V. Truong. Scheduling broadcasts in multihop radio networks. IEEE Trans. Communications, 38(4):456--460, Apr. 1990.
[8]
M. Fussen, R. Wattenhofer, and A. Zollinger. Interference Arises at the Receiver. In International Conference on Wireless Networks, Communications, and Mobile Computing (WIRELESSCOM), Maui, Hawaii, USA, June 2005.
[9]
A. Giridhar and P. R. Kumar. Computing and communicating functions over sensor networks. IEEE Journal on Selected Areas in Communication, 23(4), 2005.
[10]
J. Grönkvist. Interference-Based Scheduling in Spatial Reuse TDMA--PhD thesis, Royal Institute of Technology, Stockholm, Sweden, 2005.
[11]
J. Grönkvist and A. Hansson. Comparison Between Graph-Based and Interference-Based STDMA Scheduling. In Proc. of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC), pages 255--258, 2001.
[12]
P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming (March 1998), pages 547--566, 1998.
[13]
P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Information Theory, 46(2):388--404, 2000.
[14]
B. Hajek and G. Sasaki. Link scheduling in polynomial time. Information Theory, IEEE Transactions on, 34(5):910--917.
[15]
H. Hunt, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, and R. Stearns. NC-Approximation Schemes for NP-and PSPACE-Hard Problems for Geometric Graphs. ALGORITHMS:Journal of Algorithms, 26, 1998.
[16]
K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interference on multi-hop wireless network performance. In MobiCom'03:Proc. of the 9th Annual International Conference on Mobile Computing and Networking, pages 66--80, New York, NY, USA, 2003. ACM Press.
[17]
R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. 1972.
[18]
I. T. L. Kozat, U. C. ;Koutsopoulos. Cross-layer design for power efficiency and qos provisioning in multi-hop wireless networks. Wireless Communications, IEEE Transactions on, 5, 2006.
[19]
S. O. Krumke, M. Marathe, and S. Ravi. Models and approximation algorithms for channel assignment in radio networks. Wireless Networks, 6:575--584.
[20]
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. End-to-end packet-scheduling in wireless ad-hoc networks. In Proc. of the 15th annual ACM-SIAM symposium on Discrete Algorithms (SODA'04), pages 1021--1030, 2004.
[21]
K. Leung and L. Wang. Integrated link adaptation and power control for wireless ip networks, 2000.
[22]
H. L. Mainak Chatterjee and S. K. Das. Rate allocation and admission control for differentiated services in cdma data networks. IEEE Transactions on Mobile Computing, 6(2):179--191, 2007.
[23]
T. Moscibroda. The worst-case capacity of wireless sensor networks. In IPSN, pages 1--10, 2007.
[24]
T. Moscibroda and R. Wattenhofer. Coloring Unstructured Radio Networks. In Proc. of the17th Symposium on Parallel Algorithms and Architectures (SPAA), pages 39--48, 2005.
[25]
T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proc. of the 25th IEEE INFOCOM, 2006.
[26]
T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-based Models. In Proc. of the 5th ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets), 2006.
[27]
T. Moscibroda, R. Wattenhofer, and A. Zollinger. Topology Control meets SINR:The Scheduling Complexity of Arbitrary Topologies. In Proc. of the 7th ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2006.
[28]
S. Papavassiliou and L. Tassiulas. Joint optimal channel base station and power assignment for wireless access. IEEE/ACM Trans. Netw, 4(6):857--872, 1996.
[29]
B. Radunovic and J.-Y. Le Boudec. Optimal Power Control, Scheduling, and Routing in UWB Networks. Journal on Selected Areas in Communications, 2(7), 2004.
[30]
B. Radunovic and J.-Y. Le Boudec. Rate Performance Objectives of Multi-hop Wireless Networks. In Proc. 23th IEEE INFOCOM, 2004.
[31]
S. Ramanathan and E. L. Lloyd. Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Netw., 1(2):166--177, 1993.
[32]
G. Sharma, R. R. Mazumdar, and N. B. Shroff. On the complexity of scheduling in wireless networks. In MobiCom '06:Proc. of the 12th annual international conference on Mobile computing and networking, pages 227--238, New York, NY, USA, 2006. ACM Press.
[33]
S. Singh and C. S. Raghavendra. PAMAS -Power Aware Multi-Access Protocol with Signalling for Ad Hoc Networks. SIGCOMM Comput. Commun. Rev., 28(3):5--26, 1998.

Cited By

View all
  • (2024)WNV-RA: Wireless Network Virtualization Empowered Resource Allocation in Delay-Sensitivity Airborne Tactical NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2024.347759523:12(18855-18869)Online publication date: Dec-2024
  • (2024)A Reassessment on Applying Protocol Interference Model Under Rayleigh Fading: From Perspective of Link SchedulingIEEE/ACM Transactions on Networking10.1109/TNET.2023.328443332:1(238-252)Online publication date: Feb-2024
  • (2024)A Diamond-based approximation algorithm for the shortest link scheduling in wireless networks under SINR model2024 8th International Conference on Smart Cities, Internet of Things and Applications (SCIoT)10.1109/SCIoT62588.2024.10570114(114-118)Online publication date: 14-May-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '07: Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing
September 2007
276 pages
ISBN:9781595936844
DOI:10.1145/1288107
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 September 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. NP-complete
  2. SINR
  3. ad-Hoc networks
  4. approximation algorithms
  5. geometric SINR
  6. scheduling
  7. weighted scheduling
  8. wireless

Qualifiers

  • Article

Conference

MobiCom/MobiHoc '07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)WNV-RA: Wireless Network Virtualization Empowered Resource Allocation in Delay-Sensitivity Airborne Tactical NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2024.347759523:12(18855-18869)Online publication date: Dec-2024
  • (2024)A Reassessment on Applying Protocol Interference Model Under Rayleigh Fading: From Perspective of Link SchedulingIEEE/ACM Transactions on Networking10.1109/TNET.2023.328443332:1(238-252)Online publication date: Feb-2024
  • (2024)A Diamond-based approximation algorithm for the shortest link scheduling in wireless networks under SINR model2024 8th International Conference on Smart Cities, Internet of Things and Applications (SCIoT)10.1109/SCIoT62588.2024.10570114(114-118)Online publication date: 14-May-2024
  • (2024)Intelligent Dual Time Scale Network Slicing for Sensory Information Synchronization in Industrial IoT NetworksIEEE Internet of Things Journal10.1109/JIOT.2024.344846611:23(38615-38630)Online publication date: 1-Dec-2024
  • (2023)Wireless Link Scheduling Over Recurrent Riemannian ManifoldsIEEE Transactions on Vehicular Technology10.1109/TVT.2022.322821272:4(4959-4968)Online publication date: Apr-2023
  • (2023)Minimizing Age of Information for Underwater Optical Wireless Sensor NetworksIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228991(1-10)Online publication date: 17-May-2023
  • (2023)Multi-agent reinforcement learning enabled link scheduling for next generation Internet of ThingsComputer Communications10.1016/j.comcom.2023.04.006205(35-44)Online publication date: May-2023
  • (2023)A Bioinspired Scheduling Strategy for Dense Wireless Networks Under the SINR ModelIntelligent Systems Design and Applications10.1007/978-3-031-35507-3_23(228-238)Online publication date: 3-Jun-2023
  • (2022)Delay Efficient D2D Communications Over 5G Edge-Computing Mobile Networks with Power Control2022 IEEE 19th International Conference on Mobile Ad Hoc and Smart Systems (MASS)10.1109/MASS56207.2022.00082(546-554)Online publication date: Oct-2022
  • (2022)TDMA Frame Length Minimization by Deep Learning for Swarm Communication2022 International Wireless Communications and Mobile Computing (IWCMC)10.1109/IWCMC55113.2022.9825428(617-622)Online publication date: 30-May-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media