Article

Shortest Link Scheduling with Power Control under Physical Interference Model

Authors:

Peng-Jun Wan,

Xiaohua Xu,

Ophir FriederAuthors Info & Claims

MSN '10: Proceedings of the 2010 Sixth International Conference on Mobile Ad-hoc and Sensor Networks

Pages 74 - 78

https://doi.org/10.1109/MSN.2010.17

Published: 20 December 2010 Publication History

Publisher Site

Abstract

Shortest link scheduling (SLS) in multihop wireless networks under physical interference model is notoriously hard to resolve and been studied only recently by a few works. Most of the obtained approximation bounds grow linearly with the number of links, and many are only valid with single-hop wireless networks, and some claimed approximation bounds are even false. This paper conducts a rigorous algorithmic study of SLS with power control under the physical interference model. We develop a polynomial $O\left(\beta\ln\alpha\right) $-approximation algorithm for SLS, where $\alpha$ is the independence number and \ $\beta$ is the power diversity.

Cited By

View all

Huang BYu JCheng XChen HLiu H(2017)SINR based shortest link scheduling with oblivious power control in wireless networksJournal of Network and Computer Applications10.1016/j.jnca.2016.10.01277:C(64-72)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.jnca.2016.10.012
Sgora AVergados DVergados D(2015)A Survey of TDMA Scheduling Schemes in Wireless Multihop NetworksACM Computing Surveys10.1145/267795547:3(1-39)Online publication date: 16-Apr-2015
https://dl.acm.org/doi/10.1145/2677955
Wang CYu JYu DHuang B(2014)An Improved Approximation Algorithm for the Shortest Link Scheduling Problem in Wireless Networks under SINR and Hypergraph ModelsProceedings of the 9th International Conference on Wireless Algorithms, Systems, and Applications - Volume 849110.1007/978-3-319-07782-6_14(150-160)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1007/978-3-319-07782-6_14
Show More Cited By

Shortest Link Scheduling with Power Control under Physical Interference Model
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
2. Networks
  1. Network types

Recommendations

Exact and approximate link scheduling algorithms under the physical interference model
DIALM-POMC '08: Proceedings of the fifth international workshop on Foundations of mobile computing

Given n arbitrarily distributed single-hop wireless links, using the physical interference model, the objective is to minimize the scheduling length. This is an open problem (Problem 1) proposed by Locher et al. [21]. In this paper, we solve this open ...
Link scheduling for throughput maximization in multihop wireless networks under physical interference

We consider the problem of link scheduling for throughput maximization in multihop wireless networks. Majority of previous methods are restricted to graph-based interference models. In this paper we study the link scheduling problem using a more ...
A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model
FOWANC '09: Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing

Link scheduling is crucial in improving the throughput in wireless networks and it has been widely studied under various interference models. In this paper, we study the link scheduling problem under physical interference model where all senders of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MSN '10: Proceedings of the 2010 Sixth International Conference on Mobile Ad-hoc and Sensor Networks

December 2010

248 pages

ISBN:9780769543154

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 December 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Huang BYu JCheng XChen HLiu H(2017)SINR based shortest link scheduling with oblivious power control in wireless networksJournal of Network and Computer Applications10.1016/j.jnca.2016.10.01277:C(64-72)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.jnca.2016.10.012
Sgora AVergados DVergados D(2015)A Survey of TDMA Scheduling Schemes in Wireless Multihop NetworksACM Computing Surveys10.1145/267795547:3(1-39)Online publication date: 16-Apr-2015
https://dl.acm.org/doi/10.1145/2677955
Wang CYu JYu DHuang B(2014)An Improved Approximation Algorithm for the Shortest Link Scheduling Problem in Wireless Networks under SINR and Hypergraph ModelsProceedings of the 9th International Conference on Wireless Algorithms, Systems, and Applications - Volume 849110.1007/978-3-319-07782-6_14(150-160)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1007/978-3-319-07782-6_14
Du HZhang ZWu WWu LXing K(2013)Constant-approximation for optimal data aggregation with physical interferenceJournal of Global Optimization10.1007/s10898-012-9939-756:4(1653-1666)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s10898-012-9939-7
Ma CAl-dhelaan FWan P(2013)Maximum independent set of links with power controlProceedings of the 8th international conference on Wireless Algorithms, Systems, and Applications10.1007/978-3-642-39701-1_39(474-485)Online publication date: 7-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-39701-1_39
Wan PMa CTang SXu B(2011)Maximizing capacity with power control under physical interference model in simplex modeProceedings of the 6th international conference on Wireless algorithms, systems, and applications10.5555/2033150.2033158(84-95)Online publication date: 11-Aug-2011
https://dl.acm.org/doi/10.5555/2033150.2033158

Abstract

Cited By

Recommendations

Exact and approximate link scheduling algorithms under the physical interference model

Link scheduling for throughput maximization in multihop wireless networks under physical interference

A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model

Comments

Information

Published In

Publisher

Publication History

Author Tags

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