Equivalence on Quadratic Lyapunov Function Based Algorithms in Stochastic Networks

Hu, Li; Lu, Gao; Jiaqi, Liu; Shangyue, Wang

doi:10.21307/ijanmc-2017-056

Abstract

Quadratic Lyapunov function based Algorithms (QLAs) for stochastic network optimization problems, which are cross-layer scheduling algorithms designed by Lyapunov optimization technique, have been widely used and studied. In this paper, we investigate the performance of using Lyapunov drift and perturbation in QLAs. By analyzing attraction points and utility performance of four variants of OQLA (Original QLA), we examine the rationality of OQLA for using the first- order part of an upper bound of Lyapunov drift of a function L_1. It is proved that either using the real Lyapunov function (L_2) of networks under QLA or using the entire expression of Lyapunov drift does not improve backlog-utility performance. The linear relationship between the attraction point of backlog and perturbation in the queue is found. Simulations verify the results above.

References

[1] L. Georgiadis, M. J. Neely, and L. Tassiulas, Resource allocation and cross-layer control in wireless networks. Now Publishers Inc, 2006.
Search in Google Scholar Back to article
[2] M. J. Neely, Stochastic network optimization with application to communication and queueing systems. Morgan &Claypool Publishers, 2010, vol. 3, no. 1.
Search in Google Scholar Back to article
[3] M. J. Neely, “Energy optimal control for time-varying wireless networks,” IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915– 2934, 2006.
Search in Google Scholar Back to article
[4] R. Urgaonkar and M. J. Neely, “Optimal routing with mutual information accumulation in wireless networks,” in ConferenceRecord of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASlLoMAR),. IEEE, 2011, pp. 1602–1609.
Search in Google Scholar Back to article
[5] L. Huang and M. J. Neely, “Utility optimal scheduling in energy harvesting networks,” in Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2011, p. 21.
Search in Google Scholar Back to article
[6] L. Huang and M. J. Neely, “Utility optimal scheduling in processing networks,” Performance Evaluation, vol. 68, no. 11, pp. 1002–1021, 2011.
Search in Google Scholar Back to article
[7] M. J. Neely, “Stock market trading via stochastic network optimization,” in 49th IEEE Conference on Decision and Control (CDC). IEEE, 2010, pp. 2777–2784.
Search in Google Scholar Back to article
[8] L. Huang and M. J. Neely, “Delay reduction via lagrange multipliers in stochastic network optimization,” IEEE Transactions on Automatic Control, vol. 56, no. 4, pp. 842–857, 2011.
Search in Google Scholar Back to article
[9] L. Huang, “Deterministic mathematical optimization in stochastic network control,” Ph.D. dissertation, UNIVERSITY OF SOUTHERN CALIFORNIA, 2011.
Search in Google Scholar Back to article
[10] M. J. Neely and R. Urgaonkar, “Opportunism, backpressure, and stochastic optimization with the wireless broadcast advantage,” in 42nd Asilomar Conference on Signals, Systems and Computers. IEEE, 2008, pp. 2152–2158.
Search in Google Scholar Back to article
[11] LI Hu and etc.. “The detailed version of ‘Equivalence on Quadratic Lyapunov Function Based Algorithms in Stochastic Networks’”, https://figshare.com/s/4d4d27f38d5d07166c05, available since March 2017.
Search in Google Scholar Back to article

Equivalence on Quadratic Lyapunov Function Based Algorithms in Stochastic Networks

Abstract

Paradigm

My account