Design and analysis of distributed utility maximization algorithm for multihop wireless network with inaccurate feedback

• Published in: International journal of communication systems 2014-12, Vol.27 (12), p.4280-4299
• Main Authors: Liao, Shengbin, He, Jianhua
• Format: Article
• Language: English
• Subjects: Algorithms; Control systems; Control theory; dual decomposition; Feedback; gradient estimation; infinitesimal perturbation analysis; Maximization; multihop wireless networks; network utility maximization; noise; Routers; Traffic flow; Wireless networks
• ISSN: 1074-5351; 1099-1131
• DOI: 10.1002/dac.2611

SUMMARYDistributed network utility maximization (NUM) is receiving increasing interests for cross‐layer optimization problems in multihop wireless networks. Traditional distributed NUM algorithms rely heavily on feedback information between different network elements, such as traffic sources and routers. Because of the distinct features of multihop wireless networks such as time‐varying channels and dynamic network topology, the feedback information is usually inaccurate, which represents as a major obstacle for distributed NUM application to wireless networks. The questions to be answered include if distributed NUM algorithm can converge with inaccurate feedback and how to design effective distributed NUM algorithm for wireless networks. In this paper, we first use the infinitesimal perturbation analysis technique to provide an unbiased gradient estimation on the aggregate rate of traffic sources at the routers based on locally available information. On the basis of that, we propose a stochastic approximation algorithm to solve the distributed NUM problem with inaccurate feedback. We then prove that the proposed algorithm can converge to the optimum solution of distributed NUM with perfect feedback under certain conditions. The proposed algorithm is applied to the joint rate and media access control problem for wireless networks. Numerical results demonstrate the convergence of the proposed algorithm. Copyright © 2013 John Wiley & Sons, Ltd. Distributed network utility maximization (NUM) is receiving increasing interests for cross‐layer optimization problems in multihop wireless networks. In this paper, we use infinitesimal perturbation analysis technique to provide an unbiased gradient estimation on the aggregate rate of traffic sources at the routers. A stochastic approximation algorithm is then proposed to solve the distributed NUM problem with inaccurate feedback and its convergence is proved. The proposed algorithm is applied to the joint rate and media access control problem for wireless networks.