skip to main content
10.1145/2491288.2491297acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
research-article

Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels

Published: 29 July 2013 Publication History

Abstract

Developing scheduling mechanisms that can simultaneously achieve throughput optimality and good delay performance often require solving the Maximum Independent Weighted Set (MWIS) problem. However, under most realistic network settings, the MWIS problem can be shown to be NP-hard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of the opportunistic gain, and may no longer guarantee good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size, and achieves provable performance guarantees (which is arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). Through simulations we verify that both the throughput and the delay under our proposed distributed scheduling scheme are close to that of the optimal solution to MWIS. Further, we implement a preliminary version of our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The preliminary experiment results show that our implementation successfully accounts for wireless fading, and attains the opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.

References

[1]
ALIX system boards. http://pcengines.ch/alix.htm.
[2]
Atheros Linux Wireless Drivers. http://wireless.kernel.org/en/users/Drivers/ath5k.
[3]
Voyage Linux. http://linux.voyage.hk.
[4]
S. Basagni. Finding a Maximal Weighted Independent Set in Wireless Networks. Telecommunication Systems, 18:155--168, 2001.
[5]
B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, and Y. Zwols. Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory. IEEE/ACM Trans. Netw., 20(1), Feburary 2012.
[6]
L. Bui, S. Sanghavi, and R. Srikant. Distributed Link Scheduling with Constant Overhead. IEEE/ACM Trans. Netw., 17(5):1467--1480, October 2009.
[7]
P. Chaporkar, K. Kar, X. Luo, and S. Sarkar. Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks. IEEE Trans. Inf. Theory, 54(2):572--594, February 2008.
[8]
J. Ghaderi and R. Srikant. Effect of Access Probabilities on the Delay Performance of Q-CSMA Algorithms. In IEEE INFOCOM, April 2012.
[9]
P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inf. Theory, 46(2):388--404, March 2000.
[10]
J.-H. Hoepman. Simple Distributed Weighted Matchings. eprint, October 2004.
[11]
L. Jiang and J. Walrand. A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks. IEEE/ACM Trans. Netw., 18(13):960--972, June 2010.
[12]
C. Joo. On Random Access Scheduling for Multimedia Traffic in Multi-hop Wireless Networks, 2012. to appear in IEEE Trans. Mobile Computing.
[13]
C. Joo, G. Sharma, N. B. Shroff, and R. R. Mazumdar. On the Complexity of Scheduling in Wireless Networks. EURASIP Journal of Wireless Communications and Networking, October 2010.
[14]
C. Joo and N. B. Shroff. Local Greedy Approximation for Scheduling in Multi-hop Wireless Networks. IEEE Trans. Mobile Computing, 11(3):414--426, March 2012.
[15]
E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan. On the Stability of Input-Queued Switches with Speed-Up. IEEE/ACM Trans. Netw., 9(1), Feburary 2001.
[16]
B. Li and A. Eryilmaz. A Fast-CSMA Algorithm for Deadline Constraint Scheduling over Wireless Fading Channels. In Workshop on Research Allocation and Cooperation in Wireless Networks (RAWNET), May 2011.
[17]
X. Lin and S. Rasool. Constant-Time Distributed Scheduling Policies for Ad Hoc Wireless Networks. IEEE Trans. Autom. Control, 54(2):231--242, Feburary 2009.
[18]
X. Lin and N. B. Shroff. The Impact of Imperfect Scheduling on Cross-Layer Congestion Control in Wireless Networks. IEEE/ACM Trans. Netw., 14(2):302--315, April 2006.
[19]
X. Liu, E. K. P. Chong, and N. B. Shroff. A Framework for Opportunistic Scheduling in Wireless Networks. Computer Networks, 41(4):451--474, March 2003.
[20]
M. Lotfinezhad and P. Marbach. Delay Performance of CSMA Policies in Multihop Wireless Networks: A New Perspective. In Information Theory and Application Workshop, Feburary 2010.
[21]
E. Modiano, D. Shah, and G. Zussman. Maximizing Throughput in Wireless Networks via Gossiping. Sigmetrics Performance Evaluation Review, 34(1):27--38, 2006.
[22]
M. J. Neely, E. Modiano, and C. E. Rohrs. Dynamic Power Allocation and Routing for Time-varying Wireless Networks. IEEE J. Sel. Areas Commun., 23(1), 2005.
[23]
J. Ni, B. Tan, and R. Srikant. Q-CSMA: Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks. IEEE/ACM Trans. Netw., 20(3), June 2012.
[24]
S. Sakai, M. Togasaki, and K. Yamazaki. A Note on Greedy Algorithms for the Maximum Weighted Independent Set Problem. Discrete Appl. Math., 126(2--3):313--322, March 2003.
[25]
S. Sarkar and L. Tassiulas. End-to-end Bandwidth Guarantees Through Fair Local Spectrum Share in Wireless Ad-hoc Networks. In IEEE CDC, pages 564--569, December 2003.
[26]
G. Sharma, C. Joo, N. B. Shroff, and R. R. Mazumdar. Joint Congestion Control and Distributed Scheduling for Throughput Guarantees in Wireless Networks. ACM Trans. Model. and Comput. Simul., 21(1):5:1--5:25, December 2010.
[27]
L. Tassiulas and A. Ephremides. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximal Throughput in Multihop Radio Networks. IEEE Trans. Autom. Control, 37(12):1936--1948, December 1992.
[28]
P.-J. Wan, O. Frieder, X. Jia, F. Yao, X. Xu, and S. Tang. Wireless Link Scheduling under Physical Interference Model. In IEEE INFOCOM, April 2011.
[29]
X. Wu and R. Srikant. Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks. In IEEE INFOCOM, April 2006.
[30]
S. Yun, J. Shin, and Y. Yi. Medium Access over Time-varying Channels with Limited Sensing Cost. CoRR, abs/1206.5054, 2012.

Cited By

View all
  • (2023)Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00195(2538-2550)Online publication date: Apr-2023
  • (2020)Jamsa: A Utility Optimal Contextual Online Learning Framework for Anti-Jamming Wireless Scheduling Under Reactive Jamming AttackIEEE Transactions on Network Science and Engineering10.1109/TNSE.2019.29554647:3(1862-1878)Online publication date: 1-Jul-2020
  • (2020)Minimizing Wireless Delay with a High-Throughput Side ChannelIEEE Transactions on Mobile Computing10.1109/TMC.2019.291404819:7(1634-1648)Online publication date: 1-Jul-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '13: Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing
July 2013
322 pages
ISBN:9781450321938
DOI:10.1145/2491288
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 the author(s) 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: 29 July 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. distributed algorithm
  2. maximum weighted independent set
  3. wireless scheduling

Qualifiers

  • Research-article

Conference

MobiHoc '13
Sponsor:

Acceptance Rates

MobiHoc '13 Paper Acceptance Rate 42 of 234 submissions, 18%;
Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00195(2538-2550)Online publication date: Apr-2023
  • (2020)Jamsa: A Utility Optimal Contextual Online Learning Framework for Anti-Jamming Wireless Scheduling Under Reactive Jamming AttackIEEE Transactions on Network Science and Engineering10.1109/TNSE.2019.29554647:3(1862-1878)Online publication date: 1-Jul-2020
  • (2020)Minimizing Wireless Delay with a High-Throughput Side ChannelIEEE Transactions on Mobile Computing10.1109/TMC.2019.291404819:7(1634-1648)Online publication date: 1-Jul-2020
  • (2020)The maximum weighted k distance-d independent set problem on interval graph2020 9th International Congress on Advanced Applied Informatics (IIAI-AAI)10.1109/IIAI-AAI50415.2020.00177(840-841)Online publication date: Sep-2020
  • (2019)EasyPassProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365421(186-199)Online publication date: 3-Dec-2019
  • (2018)A Distributed Transmission Scheduling Algorithm for Wireless Networks Based on the Ising Model2018 IEEE Statistical Signal Processing Workshop (SSP)10.1109/SSP.2018.8450715(6-10)Online publication date: Jun-2018
  • (2017)A Study on Application-Aware Scheduling in Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2016.261352916:7(1787-1801)Online publication date: 1-Jul-2017
  • (2017)Scheduling Flows With Multiple Service Frequency ConstraintsIEEE Internet of Things Journal10.1109/JIOT.2016.25776304:2(496-504)Online publication date: Apr-2017
  • (2017)iType: Using eye gaze to enhance typing privacyIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057233(1-9)Online publication date: May-2017
  • (2017)Conflict graph embedding for wireless network optimizationIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057226(1-9)Online publication date: May-2017
  • 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

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media