A Converse Result on Convergence Time for Opportunistic Wireless Scheduling
Pages 40 - 48
Abstract
This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multi-access and broadcast systems. Every time slot an access point observes the current channel states and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of O(log(T)/T), where T is the time the algorithm has been running. An existing Ω(1/T) converse is known. The current paper improves the converse to Ω(log(T)/T), which matches the known achievability result. The proof uses a reduction from the opportunistic scheduling problem to a Bernoulli estimation problem. Along the way, it refines a result on Bernoulli estimation.
References
[1]
M. J. Neely, Convergence and adaptation for utility optimal opportunistic scheduling. IEEE/ACM Transactions on Networking, 27(3):904–917, June 2019.
[2]
M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool, 2010.
[3]
F. Kelly, Charging and rate control for elastic traffic. European Transactions on Telecommunications, vol. 8, no. 1 pp. 33-37, Jan.-Feb. 1997.
[4]
F.P. Kelly, A. Maulloo, and D. Tan, Rate control for communication networks: Shadow prices, proportional fairness, and stability. Journ. of the Operational Res. Society, vol. 49, no. 3, pp. 237-252, March 1998.
[5]
J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, vol. 8, no. 5, Oct. 2000.
[6]
E. Altman, K. Avrachenkov, and A. Garnaev, Generalized α-fair resource allocation in wireless networks. In Proc. Conference on Decision and Control, Dec. 2008.
[7]
T. Lan, D. Kao, M. Chiang, and A. Sabharwal, An axiomatic theory of fairness in network resource allocation. In Proc. IEEE INFOCOM, March 2010.
[8]
H. Kushner and P. Whiting. Asymptotic properties of proportional-fair sharing algorithms. Proc. 40th Annual Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Oct. 2002.
[9]
R. Agrawal and V. Subramanian. Optimality of certain channel aware scheduling policies. Proc. 40th Annual Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Oct. 2002.
[10]
M. J. Neely, E. Modiano, and C. Li, Fairness and optimal stochastic control for heterogeneous networks. IEEE/ACM Transactions on Networking, vol. 16, no. 2, pp. 396-409, April 2008.
[11]
M. J. Neely, Energy optimal control for time varying wireless networks. IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006.
[12]
A. Eryilmaz and R. Srikant. Joint congestion control, routing, and MAC for stability and fairness in wireless networks. IEEE Journal on Selected Areas in Communications, Special Issue on Nonlinear Optimization of Communication Systems, vol. 14, pp. 1514-1524, Aug. 2006.
[13]
A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1333-1344, Dec. 2007.
[14]
A. Stolyar, Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems, vol. 50, no. 4, pp. 401-457, 2005.
[15]
A. Stolyar, Greedy primal-dual algorithm for dynamic resource allocation in complex networks. Queueing Systems, vol. 54, no. 3, pp. 203-220, 2006.
[16]
E. Hazan and S. Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. Journal of Machine Learning Research, vol. 15 (July):pp. 2489–2512, 2014.
[17]
E. Hazan, A. Agarwal, and S. Kale, Logarithmic regret algorithms for online convex optimization. Machine Learning, vol. 69, no. 2, pp. 169-192, Dec. 2007.
[18]
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Proc. 20th International Conference on Machine Learning (ICML), 2003.
[19]
Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Boston, 2004.
[20]
M. J. Neely, A converse result on convergence time for opportunistic wireless scheduling. ArXiv Technical Report, arXiv:2001.01031, Jan. 2020.
[21]
T. M. Cover and J. A. Thomas. Elements of Information Theory. New York: John Wiley & Sons, Inc., 1991.
Index Terms
- A Converse Result on Convergence Time for Opportunistic Wireless Scheduling
Index terms have been assigned to the content through auto-classification.
Recommendations
Opportunistic link scheduling for multihop wireless networks
This paper studies throughput improvement for TCP traffic in IEEE 802.11-based multihop ad hoc wireless networks. Due to the incompatibility between TCP and the IEEE 802.11 distributed coordination function (DCF) protocols, the reaction of TCP in case ...
Opportunistic Fair Scheduling in Wireless Networks: An Approximate Dynamic Programming Approach
We consider the problem of temporal fair scheduling of queued data transmissions in wireless heterogeneous networks. We deal with both the throughput maximization problem and the delay minimization problem. Taking fairness constraints and the data ...
Joint uplink/downlink opportunistic scheduling for Wi-Fi WLANs
Recent advances in the speed of multi-rate wireless local area networks (WLANs) and the proliferation of WLAN devices have made rate adaptive, opportunistic scheduling critical for throughput optimization. As WLAN traffic evolves to be more symmetric ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jul 2020
2647 pages
Copyright © 2020.
Publisher
IEEE Press
Publication History
Published: 06 July 2020
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in