article

Asynchronous congestion control in multi-hop wireless networks with maximal matching-based scheduling

Authors:

Atilla Eryilmaz,

Xinzhou WuAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 4

Pages 826 - 839

https://doi.org/10.1109/TNET.2007.904007

Published: 01 August 2008 Publication History

Abstract

We consider a multi-hop wireless network shared by many users. For an interference model that constrains a node to either transmit to or receive from only one other node at a time, and not to do both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms.

References

[1]

L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

[2]

L. Tassiulas, "Scheduling and performance limits of networks with constantly changing topology," IEEE Trans. Inf. Theory, vol. 43, no. 3, pp. 1067-1073, May 1997.

[3]

S. Shakkottai and A. Stolyar, "Scheduling for multiple flows sharing a time-varying channel: The exponential rule," Translations AMS, ser. 2, vol. 207, pp. 185-201, 2002, a volume in memory of F. Karpelevich.

[4]

S. Shakkottai, R. Srikant, and A. Stolyar, "Pathwise optimality of the exponential scheduling rule for wireless channels," Adv. Appl. Prob., vol. 36, no. 4, pp. 1021-1045, 2004.

[5]

A. Eryilmaz, R. Srikant, and J. Perkins, "Stable scheduling policies for fading wireless channels," in Proc. IEEE Int. Symp. Information Theory, 2003, p. 454.

[6]

M. Neely, E. Modiano, and C. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," in Proc. IEEE INFOCOM, Apr. 2003, pp. 745-755.

[7]

A. Eryilmaz, R. Srikant, and J. R. Perkins, "Stable scheduling policies for fading wireless channels," IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 411-424, Apr. 2005.

[8]

F. P. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.

[9]

S. H. Low and D. E. Lapsley, "Optimization flow control, I: Basic algorithm and convergence," IEEE/ACM Trans. Netw., vol. 7, no. 6, pp. 861-875, Dec. 1999.

[10]

R. Srikant, The Mathematics of Internet Congestion Control. Boston, MA: Birkhauser, 2004.

[11]

A. Stolyar, "Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm," Queueing Syst., vol. 50, no. 4, pp. 401-457, Aug. 2005.

[12]

A. Eryilmaz and R. Srikant, "Fair resource allocation in wireless networks using queue-length based scheduling and congestion control," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1794-1803.

[13]

M. Neely, E. Modiano, and C. Li, "Fairness and optimal stochastic control for heterogeneous networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1723-1734.

[14]

X. Lin and N. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proc. IEEE Conf. Decision and Control, Dec. 2004, pp. 1484-1489.

[15]

S. Sarkar and L. Tassiulas, "End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks," in Proc. IEEE Conf. Decision and Control, Dec. 2003, pp. 564-569.

[16]

Y. Yi and S. Shakkottai, "Hop-by-hop congestion control over a wireless multi-hop network," in Proc. IEEE INFOCOM, Mar. 2004, pp. 2548-2558.

[17]

L. Chen, S. H. Low, and J. C. Doyle, "Joint congestion control and media access control design for ad hoc wireless networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 2212-2222.

[18]

B. Miller and C. Bisdikian, Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communication. Englewood Cliffs, NJ: Prentice-Hall, 2000.

[19]

D. J. Baker, J. Wieselthier, and A. Ephremides, "A distributed algorithm for scheduling the activation of links in a self-organizing mobile radio network," in Proc. IEEE Int. Conf. Communications, Jun. 1982, pp. 2F.6.1-2F.6.5.

[20]

B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.

[21]

X. Lin and N. Shroff, "The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks," in Proc. IEEE INFOCOM , Mar. 2005, pp. 1804-1814.

[22]

C. Humes, "A regulator stabilization technique: Kumar-Seidman revisited," IEEE Trans. Autom. Control, vol. 39, no. 1, pp. 191-196, Jan. 1994.

[23]

X. Wu and R. Srikant, "Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing," in Proc. IEEE Conf. Decision and Control, Dec. 2005, pp. 5342-5347.

[24]

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Belmont, MA: Athena Scientific, 1997.

[25]

M. B. Pursley, H. B. Russell, and P. E. Staples, "Routing multimedia packets in a frequency-hop packet radio network," in Proc. MILCOM, 1996, pp. 220-224.

[26]

J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556-567, Oct. 2000.

[27]

M. Kodialam and T. Nandagopal, "Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem," in Proc. ACM MOBICOM, Sep. 2003, pp. 42-54.

[28]

C. E. Shannon, "A theorem on coloring the lines of a network," J. Math. Phys., vol. 28, pp. 148-151, 1949.

[29]

L. Ying, R. Srikant, A. Eryilmaz, and G. E. Dullerud, "Distributed fair resource allocation in cellular networks in the presence of heterogeneous delays," in Proc. WiOPT, Apr. 2005, pp. 96-105.

[30]

J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization: Theory and Examples (CMS Books in Mathematics). New York: Springer-Verlag, 2000.

[31]

H. Khalil, Nonlinear Systems, 3rd ed. Englewood Cliffs, NJ: Prentice-Hall, 2002.

[32]

J. R. Norris, Markov Chains. Cambridge, U.K.: Cambridge Univ. Press, 1998.

Cited By

Kim DOh SLim J(2017)Multi-channel-based scheduling for overlay inband device-to-device communicationsWireless Networks10.1007/s11276-016-1306-z23:8(2587-2600)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s11276-016-1306-z
Wu XTavildar SShakkottai SRichardson TLi JLaroia RJovicic A(2013)FlashLinQIEEE/ACM Transactions on Networking10.1109/TNET.2013.226463321:4(1215-1228)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1109/TNET.2013.2264633
Le LModiano EShroff N(2012)Optimal control of wireless networks with finite buffersIEEE/ACM Transactions on Networking10.1109/TNET.2011.217614020:4(1316-1329)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1109/TNET.2011.2176140
Show More Cited By

Index Terms

Asynchronous congestion control in multi-hop wireless networks with maximal matching-based scheduling
1. Networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control

We consider the problem of allocating resources (time slots, frequency, power, etc.) at a base station to many competing flows, where each flow is intended for a different receiver. The channel conditions may be time-varying and different for different ...
Joint congestion control, routing, and MAC for stability and fairness in wireless networks

In this paper, we describe and analyze a joint scheduling, routing and congestion control mechanism for wireless networks, that asymptotically guarantees stability of the buffers and fair allocation of the network resources. The queue-lengths serve as ...
Understanding congestion control in multi-hop wireless mesh networks
MobiCom '08: Proceedings of the 14th ACM international conference on Mobile computing and networking

Complex interference in static multi-hop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 4

August 2008

249 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 August 2008

Revised: 01 April 2007

Received: 14 March 2006

Published in TON Volume 16, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
279
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim DOh SLim J(2017)Multi-channel-based scheduling for overlay inband device-to-device communicationsWireless Networks10.1007/s11276-016-1306-z23:8(2587-2600)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s11276-016-1306-z
Wu XTavildar SShakkottai SRichardson TLi JLaroia RJovicic A(2013)FlashLinQIEEE/ACM Transactions on Networking10.1109/TNET.2013.226463321:4(1215-1228)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1109/TNET.2013.2264633
Le LModiano EShroff N(2012)Optimal control of wireless networks with finite buffersIEEE/ACM Transactions on Networking10.1109/TNET.2011.217614020:4(1316-1329)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1109/TNET.2011.2176140
Le LModiano EShroff N(2010)Optimal control of wireless networks with finite buffersProceedings of the 29th conference on Information communications10.5555/1833515.1833788(2034-2042)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833788
Weeraddana PCodreanu MLatva-aho MEphremides A(2010)On the effect of self-interference cancelation in multihop wireless networksEURASIP Journal on Wireless Communications and Networking10.1155/2010/5139522010(1-10)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1155/2010/513952

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents