More Web Proxy on the site http://driver.im/

research-article

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

Authors:

ShaoJie TangAuthors Info & Claims

FOWANC '09: Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing

Pages 13 - 20

https://doi.org/10.1145/1540343.1540347

Published: 18 May 2009 Publication History

Abstract

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 links transmit at a given power P and a link can transmit successfully if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR) at the corresponding receiver is at least a certain threshold. The link scheduling problem is to find a maximum "independent set" (MIS) of links, i.e., the maximum number of links that can transmit successfully in one time-slot, given a set of input links. This problem has been shown to be NP-hard [10]. Here we propose the first link scheduling algorithm with a constant approximation ratio for arbitrary background noise N ≥ 0. When each link l has a weight w(l)>0, we propose a method for weighted MIS with approximation ratio O(min(log max_ι∈L w(ι)/min_ι∈L w||ι||, log max_ι∈L w(ι)/min_ι∈L w||ι||, where ||ι|| is the Euclidean length of a link ι.

References

[1]

Brar, G., Blough, D., and Santi, P. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In Proceedings of the 12th annual international conference on Mobile computing and networking (2006), pp. 2--13.

Digital Library

[2]

Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., and Srinivasan, A. Cross-layer latency minimization in wireless networks with SINR constraints. In Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing (2007), pp. 110--119.

Digital Library

[3]

Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., and Srinivasan, A. Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints. In IEEE INFOCOM (2008), pp. 1166--1174.

[4]

Cruz, R., and Santhanam, A. Optimal routing, link scheduling and power control in multihop wireless networks. In IEEE INFOCOM 2003, vol. 1.

[5]

ElBatt, T., and Ephremides, A. Joint scheduling and power control for wireless ad hoc networks. Wireless Communications, IEEE Transactions on 3, 1 (2004), 74--85.

Digital Library

[6]

Gao, Y., Hou, J., and Nguyen, H. Topology Control for Maintaining Network Connectivity and Maximizing Network Capacity under the Physical Model. In IEEE INFOCOM (2008), pp. 1013--1021.

[7]

Giridhar, A., and Kumar, P. Computing and communicating functions over sensor networks. Selected Areas in Communications, IEEE Journal on 23, 4 (2005), 755--764.

Digital Library

[8]

Goussevskaia, O., Oswald, Y., and Wattenhofer, R. Complexity in geometric SINR. In Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing (2007), pp. 100--109.

Digital Library

[9]

Goussevskaia, O., W.R.H.M., and Welzl, E. Capacity of Arbitrary Wireless Networks. In Proceedings of IEEE INFOCOM 09 (2009).

[10]

Gupta, P., and Kumar, P. The capacity of wireless networks. Information Theory, IEEE Transactions on 46, 2 (2000), 388--404.

Digital Library

[11]

Joo, C., Lin, X., and Shroff, N. Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multi-Hop Wireless Networks. In IEEE INFOCOM (2008), pp. 1103--1111.

[12]

Kumar, V., Marathe, M., Parthasarathy, S., and Srinivasan, A. Algorithmic aspects of capacity in wireless networks. In Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems (2005), pp. 133--144.

Digital Library

[13]

Moscibroda, T. The worst-case capacity of wireless sensor networks. In Proceedings of the 6th international conference on Information processing in sensor networks (2007), pp. 1--10.

Digital Library

[14]

Moscibroda, T., and Wattenhofer, R. The Complexity of Connectivity in Wireless Networks. In Proc. of the 25 thIEEE INFOCOM (2006).

[15]

Moscibroda, T., Wattenhofer, R., and Weber, Y. Protocol Design Beyond Graph-Based Models. In ACM HotNets (2006).

[16]

Moscibroda, T., Wattenhofer, R., and Zollinger, A. Topology control meets SINR: the scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing (2006), pp. 310--321.

Digital Library

[17]

Sharma, G., Mazumdar, R., and Shroff, N. On the complexity of scheduling in wireless networks. In Proceedings of the 12th annual international conference on Mobile computing and networking (2006), pp. 227--238.

Digital Library

[18]

Tassiulas, L. Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In IEEE INFOCOM (1998), pp. 533--539.

[19]

Tassiulas, L., and Ephremides, A. Stability properties of constrained queueing systems and schedulingpolicies for maximum throughput in multihop radio networks. Decision and Control, 1990., Proceedings of the 29th IEEE Conference on (1990), 2130--2132.

Cited By

Tan ZLuo QXu XLi X(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
https://doi.org/10.1109/MASS56207.2022.00082
Brown MMarshall CYang DLi MLin JXue GBrown MMarshall CDejun Yang Ming Li Jian Lin Guoliang Xue (2017)Maximizing Capacity in Cognitive Radio Networks Under Physical Interference ModelIEEE/ACM Transactions on Networking10.1109/TNET.2017.271802225:5(3003-3015)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1109/TNET.2017.2718022
He QYuan DEphremides A(2017)Maximum Link Activation with Cooperative Transmission and Interference Cancellation in Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2016.254690616:2(408-421)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2546906
Show More Cited By

Index Terms

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

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 in wireless networks with successive interference cancellation

Successive interference cancellation (SIC) is an effective way of multipacket reception (MPR) to combat interference at the physical layer. To understand the potential MPR advantages, we study link scheduling in an ad hoc network with SIC at the ...
Shortest Link Scheduling with Power Control under Physical Interference Model
MSN '10: Proceedings of the 2010 Sixth International Conference on Mobile Ad-hoc and Sensor Networks

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOWANC '09: Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing

May 2009

104 pages

ISBN:9781605585239

DOI:10.1145/1540343

General Chairs:
Ivan Stojmenovic
University of Ottawa, Canada
,
Ding-Zhu Du
University of Texas at Dallas, USA
,
Program Chairs:
Yu Wang
University of North Carolina at Charlotte, USA
,
Yingshu Li
Georgia State University, USA

Copyright © 2009 ACM.

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: 18 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc '09

Sponsor:

MobiHoc '09: The Tenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

May 18, 2009

Louisiana, New Orleans, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
309
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan ZLuo QXu XLi X(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
https://doi.org/10.1109/MASS56207.2022.00082
Brown MMarshall CYang DLi MLin JXue GBrown MMarshall CDejun Yang Ming Li Jian Lin Guoliang Xue (2017)Maximizing Capacity in Cognitive Radio Networks Under Physical Interference ModelIEEE/ACM Transactions on Networking10.1109/TNET.2017.271802225:5(3003-3015)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1109/TNET.2017.2718022
He QYuan DEphremides A(2017)Maximum Link Activation with Cooperative Transmission and Interference Cancellation in Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2016.254690616:2(408-421)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2546906
Niu YGao CLi YJin DSu LWu D(2016)Boosting Spatial Reuse via Multiple-Path Multihop Scheduling for Directional mmWave WPANsIEEE Transactions on Vehicular Technology10.1109/TVT.2015.247963365:8(6614-6627)Online publication date: Aug-2016
https://doi.org/10.1109/TVT.2015.2479633
Reddy IMeenakshi R(2016)Congestion control using distributed link scheduling in wireless networks2016 World Conference on Futuristic Trends in Research and Innovation for Social Welfare (Startup Conclave)10.1109/STARTUP.2016.7583928(1-5)Online publication date: Feb-2016
https://doi.org/10.1109/STARTUP.2016.7583928
Bundel BMenaria V(2016)Low Latency Based Efficient Aggregation Scheduling in Multihop Wireless Sensor Network2016 8th International Conference on Computational Intelligence and Communication Networks (CICN)10.1109/CICN.2016.30(124-128)Online publication date: Dec-2016
https://doi.org/10.1109/CICN.2016.30
Niu YLi YJin DSu LWu D(2016)A two stage approach for channel transmission rate aware scheduling in directional mmWave WPANsWireless Communications & Mobile Computing10.1002/wcm.252116:3(313-329)Online publication date: 25-Feb-2016
https://dl.acm.org/doi/10.1002/wcm.2521
Zhou ZLi C(2015)Approximation algorithms for maximum link scheduling under SINR-Based interference modelInternational Journal of Distributed Sensor Networks10.5555/2810710.28364502015(81-81)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2810710.2836450
Deng HYu JYu DLi GHuang B(2015)Heuristic algorithms for one-slot link scheduling in wireless sensor networks under SINRInternational Journal of Distributed Sensor Networks10.1155/2015/8065202015(23-23)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/806520
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
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents