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

research-article

Throughput characterization of node-based scheduling in multihop wireless networks: a novel application of the Gallai-Edmonds structure theorem

Authors:

Yu SangAuthors Info & Claims

MobiHoc '16: Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing

Pages 41 - 50

https://doi.org/10.1145/2942358.2942388

Published: 05 July 2016 Publication History

Abstract

Maximum Vertex-weighted Matching (MVM) is an important link scheduling algorithm for multihop wireless networks. Under certain assumptions, it has been shown that if the underlying network graph is bipartite, MVM not only maximizes the throughput in settings with continuous packet arrivals, but also minimizes the evacuation time (i.e., time to drain all the initial packets) in settings without future packet arrivals. Further, even if the network graph is arbitrary, MVM achieves the best known performance guarantee for the evacuation time among existing online link scheduling algorithms. Also, it empirically exhibits close-to-optimal throughput performance and good delay performance. However, in an arbitrary network graph the throughput performance of MVM has not been well understood. To that end, in this paper we aim to carry out a systematic study of the throughput performance of MVM, assuming single-hop flows and the node-exclusive interference model. Inspired by the celebrated Gallai-Edmonds structure theorem, we introduce a novel topological notion, called the Gallai-Edmonds decomposition factor, and rigorously prove that the efficiency ratio of MVM is no smaller than the Gallai-Edmonds decomposition factor of the network graph. Further, we show that if the smallest size of an odd cycle in a graph is 2m + 1 for a positive integer m, then the Gallai-Edmonds decomposition factor is equal to 2m/(2m + 1). This implies that the Gallai-Edmonds decomposition factor is at least 2/3 for an arbitrary graph and is equal to 1 for bipartite graphs. Having these results, the throughput performance of MVM can be well characterized.

References

[1]

J. Akiyama and M. Kano. Factors and factorizations of graphs: Proof techniques in factor theory, volume 2031 of Lecture Notes in Mathematics. Springer, 2011.

Digital Library

[2]

M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. Scheduling in a queuing system with asynchronously varying service rates. Probability in the Engineering and Informational Sciences, 18(02):191--217, 2004.

Digital Library

[3]

M. Bramson. Stability of queueing networks. Springer, 2008.

[4]

J. G. Dai. On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability, pages 49--77, 1995.

[5]

J. G. Dai and B. Prabhakar. The throughput of data switches with and without speedup. In Proceedings of IEEE INFOCOM, 2000.

[6]

J. Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449--467, 1965.

[7]

L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource allocation and cross-layer control in wireless networks. Foundations and Trends in Networking, 1(1):1--144, 2006.

Digital Library

[8]

G. R. Gupta. Delay efficient control policies for wireless networks. Ph.D. thesis, Purdue University, 2009.

[9]

G. R. Gupta, S. Sanghavi, and N. B. Shroff. Node weighted scheduling. In Proceedings of ACM SIGMETRICS, pages 97--108, 2009.

Digital Library

[10]

B. Hajek and G. Sasaki. Link scheduling in polynomial time. IEEE Transactions on Information Theory, 34(5):910--917, 1988.

Digital Library

[11]

B. Ji, G. R. Gupta, and Y. Sang. Node-based Service-Balanced Scheduling for Provably Guaranteed Throughput and Evacuation Time Performance. In Proceedings of IEEE INFOCOM, 2016.

[12]

B. Ji and J. Wu. Node-based scheduling with provable evacuation time. In Proceedings of IEEE CISS, March 2015.

[13]

L. Jiang and J. Walrand. A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Transactions on Networking, 18(3):960--972, 2010.

Digital Library

[14]

C. Joo, X. Lin, and N. 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.

[15]

C. Joo and N. B. Shroff. Performance of random access scheduling schemes in multi-hop wireless networks. IEEE/ACM Transactions on Networking, 17(5):1481--1493, 2009.

Digital Library

[16]

X. Lin and S. B. Rasool. Constant-time distributed scheduling policies for ad hoc wireless networks. IEEE Transactions on Automatic Control, 54(2):231--242, 2009.

[17]

X. Lin and N. Shroff. The impact of imperfect scheduling on cross-Layer congestion control in wireless networks. IEEE/ACM Transactions on Networking, 14(2):302--315, 2006.

Digital Library

[18]

X. Lin, N. Shroff, and R. Srikant. A tutorial on cross-layer optimization in wireless networks. IEEE Journal on Selected Areas in Communications, 24(8):1452--1463, Aug. 2006.

Digital Library

[19]

A. Mekkittikul and N. McKeown. A practical scheduling algorithm to achieve 100% throughput in input-queued switches. In Proceedings of IEEE INFOCOM, pages 792--799, 1998.

[20]

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 Transactions on Networking, 20(3):825--836, 2012.

Digital Library

[21]

S. Rajagopalan, D. Shah, and J. Shin. Network adiabatic theorem: an efficient randomized protocol for contention resolution. In Proceedings of ACM SIGMETRICS, pages 133--144, 2009.

Digital Library

[22]

G. Sharma, R. Mazumdar, and N. Shroff. On the complexity of scheduling in wireless networks. In Proceedings of ACM Mobicom, pages 227--238, 2006.

Digital Library

[23]

T. H. Spencer and E. W. Mayr. Node weighted matching. In Automata, Languages and Programming, pages 454--464. Springer, 1984.

Digital Library

[24]

V. Tabatabaee and L. Tassiulas. MNCM: a critical node matching approach to scheduling for input buffered switches with no speedup. IEEE/ACM Transactions on Networking, 17(1):294--304, 2009.

Digital Library

[25]

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

[26]

X. Wu, R. Srikant, and J. Perkins. Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. IEEE Transactions on Mobile Computing, pages 595--605, 2007.

Digital Library

[27]

Q. R. Yu and G. Liu. Graph factors and matching extensions. Springer, 2010.

Cited By

Liu YLiu ZYang Y(2019)Non-stationary Stochastic Network Optimization with Imperfect Estimations2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00050(431-441)Online publication date: Jul-2019
https://doi.org/10.1109/ICDCS.2019.00050
Huang LChen MLiu Y(2018)Learning-Aided Stochastic Network Optimization With State PredictionIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2018.285459326:4(1810-1820)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2854593
Huang LChen MLiu Y(2017)Learning-aided Stochastic Network Optimization with Imperfect State PredictionProceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3084041.3084054(1-10)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3084041.3084054

Index Terms

Throughput characterization of node-based scheduling in multihop wireless networks: a novel application of the Gallai-Edmonds structure theorem
1. Networks

Recommendations

Performance of multichannel wireless ad hoc networks

This paper addresses the design of Medium Access Control (MAC) protocols for wireless ad hoc networks that derive benefits from using multiple orthogonal channels for data transmission. Each node is assumed to have a single half-duplex transceiver that ...
Goodput and throughput comparison of single-hop and multi-hop routing for IEEE 802.11 DCF-based wireless networks under hidden terminal existence

We investigate how multi-hop routing affects the goodput and throughput performances of IEEE 802.11 distributed coordination function-based wireless networks compared with direct transmission single hopping, when medium access control dynamics such as ...
Induced Graph Packing Problems

Let $${\mathcal{H}}$$be a set of undirected graphs. The induced $${\mathcal{H}}$$-packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '16: Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing

July 2016

421 pages

ISBN:9781450341844

DOI:10.1145/2942358

General Chairs:
Falko Dressler
Paderborn University
,
Friedhelm Meyer auf der Heide
Paderborn University

Copyright © 2016 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: 05 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc'16

Sponsor:

MobiHoc'16: The Seventeenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

July 5 - 8, 2016

Paderborn, Germany

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
212
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YLiu ZYang Y(2019)Non-stationary Stochastic Network Optimization with Imperfect Estimations2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00050(431-441)Online publication date: Jul-2019
https://doi.org/10.1109/ICDCS.2019.00050
Huang LChen MLiu Y(2018)Learning-Aided Stochastic Network Optimization With State PredictionIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2018.285459326:4(1810-1820)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2854593
Huang LChen MLiu Y(2017)Learning-aided Stochastic Network Optimization with Imperfect State PredictionProceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3084041.3084054(1-10)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3084041.3084054

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