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

research-article

Stability analyses of longest-queue-first link scheduling in MC-MR wireless networks

Authors:

Zhiguo WanAuthors Info & Claims

MobiHoc '12: Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing

Pages 45 - 54

https://doi.org/10.1145/2248371.2248381

Published: 11 June 2012 Publication History

Abstract

Longest-queue-first (LQF) link scheduling is a greedy link scheduling in multihop wireless networks. Its stability performance in single-channel single-radio (SC-SR) wireless networks has been well studied recently. However, its stability performance in multi-channel multi-radio (MC-MR)wireless networks is largely under-explored. In this paper, we present a stability subregion with closed form of the LQF scheduling in MC-MR wireless networks, which is within a constant factor of the network stability region. We also obtain constant lower bounds on the efficiency ratio of the LQF scheduling in MC-MR wireless networks under the 802.11 interference model or the protocol interference model.

References

[1]

Brzezinski, G. Zussman, and E. Modiano, Distributedthroughput maximization in wireless mesh networks via pre-partitioning, IEEE/ACM Transactions on Networking 16(6): 1406--1419, 2008.

Digital Library

[2]

Chaporkar, K. Kar, X. Luo, and S. Sarkar, Throughput andfairness guarantees through maximal scheduling in wirelessnetworks, IEEE Transactions on Information Theory 54(2):572--594, 2008.

Digital Library

[3]

G. Dai, On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach via Fluid Limit Models, Annals of Applied Probability 5(1):49--77, 1995.

[4]

Dimakis and J. Walrand, Sufficient conditions for stability of longest queue first scheduling: second order properties using fluid limits, phAdvances in Applied Probability 38(2):505--521, 2006.

[5]

Joo, X. Lin, and N. B. Shroff, Greedy Maximal Matching: Performance Limits for Arbitrary Network Graphs Under the Node-exclusive Interference Model, IEEE Transactions on Automatic Control 54(12):2734--2744, 2009.

[6]

Joo, X. Lin, and N. B. Shroff, Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multi-hop Wireless Networks, IEEE/ACM Transactions on Networking 17(4):1132--1145, 2009.

Digital Library

[7]

Leconte, J. Ni, and R. Srikant, Improved bounds on the through put efficiency of greedy maximal scheduling in wireless networks, Proc. ACM MOBIHOC 2009.

Digital Library

[8]

Li, C. Boyaci, and Y. Xia, A refined performance characterization of longest-queue-first policy in wireless networks, Proc. ACM MOBIHOC 2009.

Digital Library

[9]

Lin and S. Rasool, A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad-hoc Wireless Networks, Proc. IEEE INFOCOM 2009, pp. 1118--1126.

[10]

Lin and N. B. Shroff, The impact of imperfect scheduling on cross-layer rate control in wireless networks, IEEE/ACM Transactions onNetworking 14(2):302--315, 2006.

Digital Library

[11]

A. Malyshev and M.V. Menshikov, Ergodicity, continuity and analyticity of countable Markov chains, Trans. Moscow Math. Soc. 391--48, 1981.

[12]

V. Skorokhod, Basic principles and applications of probability theory, edited by Yu.V. Prokhorov, and translated from the 1989 Russian original by B.D. Seckler. Springer-Verlag, Berlin, 2005.

[13]

Tassiulas and A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Transactions on Automatic Control 37(12):1936--1948, 1992.

[14]

-J. Wan, Multiflows in Multihop Wireless Networks, Proc. ACM MOBIHOC 2009.

Digital Library

[15]

-J. Wan, Y. Cheng, Z. Wang, and F. Yao, Multiflows in Multi-Channel Multi-Radio Multihop Wireless Networks, in phProc. IEEE INFOCOM 2011.

[16]

J. Wan, M. Li, L. Wang, and O. Frieder, Local Pooling Factor of Multihop Wireless Networks, in Proc. IEEE INFOCOM 2011.

[17]

J. Wan, C. Ma, Z. Wang, B. Xu, M. Li, and X. Jia, Weighted Wireless Link Scheduling without Information of Positions And Interference/Communication Radii, in Proc. IEEE INFOCOM 2011.

[18]

Wu and R. Srikant, Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks, in Proc. of IEEE INFOCOM 2006.

[19]

Wu, R. Srikant and J. R. Perkins, Queue-Length Stability of Maximal Greedy Schedules in Wireless Networks, IEEE Transactions on Mobile Computing 6(6): 595--605, 2007.

Digital Library

[20]

-J. Wan et al., Concise Conflict Graph of MC-MR Wireless Networks and Its Algorithmic Applications, manuscript, available at http://www.cs.iit.edu/\symbol126wan/ccg.pdf.

Cited By

Atar RKeslassy IMendelson G(2019)Subdiffusive Load Balancing in Time-Varying Queueing SystemsOperations Research10.1287/opre.2019.1851Online publication date: 29-Oct-2019
https://doi.org/10.1287/opre.2019.1851
Li JGuo XGuo LJi SHan MCai Z(2018)Optimal routing with scheduling and channel assignment in multi-power multi-radio wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2015.03.00631:C(45-62)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.adhoc.2015.03.006
Ulucinar AKorpeoglu I(2016)Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networksWireless Networks10.1007/s11276-015-0954-822:1(83-104)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11276-015-0954-8
Show More Cited By

Index Terms

Stability analyses of longest-queue-first link scheduling in MC-MR wireless networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference

We consider the stability of the longest-queue-first (LQF) scheduling policy in wireless networks with multihop traffic under the one-hop interference model. Although it is well known that the back-pressure algorithm achieves the maximal stability, its ...
Efficient interference-aware TDMA link scheduling for static wireless networks
MobiCom '06: Proceedings of the 12th annual international conference on Mobile computing and networking

We study efficient link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk ...
Degree-based link scheduling for collision avoidance in distributed wireless sensor networks
ICUIMC '14: Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication

Wireless sensor networks consist of multiple sensor nodes, which communicate with each other under the constrained energy. Retransmissions caused by collision and interference during the communication among sensor nodes increase the transmission delay ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '12: Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing

June 2012

280 pages

ISBN:9781450312813

DOI:10.1145/2248371

General Chair:
Asis Nasipuri
University of North Carolina at Charlotte, USA
,
Program Chairs:
Yih-Chun Hu
University of Illinois at Urbana-Champaign, USA
,
Sanjay Shakkottai
University of Texas at Austin, USA

Copyright © 2012 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

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc '12

Sponsor:

SIGMOBILE

MobiHoc '12: The Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

June 11 - 14, 2012

South Carolina, Hilton Head, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
312
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

Atar RKeslassy IMendelson G(2019)Subdiffusive Load Balancing in Time-Varying Queueing SystemsOperations Research10.1287/opre.2019.1851Online publication date: 29-Oct-2019
https://doi.org/10.1287/opre.2019.1851
Li JGuo XGuo LJi SHan MCai Z(2018)Optimal routing with scheduling and channel assignment in multi-power multi-radio wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2015.03.00631:C(45-62)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.adhoc.2015.03.006
Ulucinar AKorpeoglu I(2016)Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networksWireless Networks10.1007/s11276-015-0954-822:1(83-104)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11276-015-0954-8
Wan PWan Z(2014)Maximizing Networking Capacity in Multi-Channel Multi-Radio Wireless NetworksJournal of Computer Science and Technology10.1007/s11390-014-1477-y29:5(901-909)Online publication date: 12-Sep-2014
https://doi.org/10.1007/s11390-014-1477-y
Wan PWan ZWang ZXu XTang SJia X(2013)Stability analyses of static greedy link schedulings in MC-MR wireless networks2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6567097(2868-2876)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOM.2013.6567097

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