TY - JOUR
T1 - Utility-optimal random access
T2 - Reduced complexity, fast convergence, and robust performance
AU - Mohsenian-Rad, A. Hamed
AU - Huang, Jianwei
AU - Chiang, Mung
AU - Wong, Vincent W.S.
N1 - Funding Information:
This work was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada, the Competitive Earmarked Research Grants (Project Number 412308) under the University Grant Committee of the Hong Kong Special Administrative Region, China, the Direct Grant (Project Number C001-2050398) of The Chinese University of Hong Kong, the National Key Technology R&D Program (Project Number 2007BAH17B04) established by the Ministry of Science and Technology of the People’s Republic of China, as well as NSF CNS-0720570, AFOSR FA9550-06-1-0297, and U.S. ONR Grant N00014-07-1-0864. Part of this paper was presented at the MILCOM’08 Conference, San Diego, CA, November 2008. Digital Object Identifier 10.1109/TWC.2009.071359
PY - 2009/2
Y1 - 2009/2
N2 - In this paper, we propose two distributed contention-based medium access control (MAC) algorithms for solving a network utility maximization (NUM) problem in wireless ad hoc networks. Most of the previous NUM-based random access algorithms have one or more of the following performance bottlenecks: (1) extensive signaling among the nodes to achieve semi-distributed implementations, (2) synchronous updates of contention probabilities, (3) small update stepsizes to ensure convergence but with typically slow speed, and (4) supporting a limited range of utility functions under which the NUM is shown to be convex. Our proposed algorithms overcome the bottlenecks in all four aspects. First, only limited amount of message passing among nodes is required. Second, fully asynchronous updates of contention probabilities are allowed. Furthermore, our algorithms are robust to arbitrary large message passing delay and message loss. Third, we do not utilize any stepsize during updates, thus our algorithms can achieve faster convergence. Finally, our proposed algorithms have provable convergence, optimality, and robustness properties under a wider range of utility functions, even if the NUM problem is non-convex. Simulation results show the optimality and fast convergence of our algorithms, performance improvements compared with the subgradient-based MAC, and better efficiency-fairness tradeoff compared with the IEEE 802.11 distributed coordination function.
AB - In this paper, we propose two distributed contention-based medium access control (MAC) algorithms for solving a network utility maximization (NUM) problem in wireless ad hoc networks. Most of the previous NUM-based random access algorithms have one or more of the following performance bottlenecks: (1) extensive signaling among the nodes to achieve semi-distributed implementations, (2) synchronous updates of contention probabilities, (3) small update stepsizes to ensure convergence but with typically slow speed, and (4) supporting a limited range of utility functions under which the NUM is shown to be convex. Our proposed algorithms overcome the bottlenecks in all four aspects. First, only limited amount of message passing among nodes is required. Second, fully asynchronous updates of contention probabilities are allowed. Furthermore, our algorithms are robust to arbitrary large message passing delay and message loss. Third, we do not utilize any stepsize during updates, thus our algorithms can achieve faster convergence. Finally, our proposed algorithms have provable convergence, optimality, and robustness properties under a wider range of utility functions, even if the NUM problem is non-convex. Simulation results show the optimality and fast convergence of our algorithms, performance improvements compared with the subgradient-based MAC, and better efficiency-fairness tradeoff compared with the IEEE 802.11 distributed coordination function.
KW - Complexity reduction
KW - Contention-based medium access control
KW - Network utility maximization
KW - Non-convex optimization
KW - Robust design
KW - α-fair utility functions
UR - http://www.scopus.com/inward/record.url?scp=61349179600&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=61349179600&partnerID=8YFLogxK
U2 - 10.1109/TWC.2009.071359
DO - 10.1109/TWC.2009.071359
M3 - Article
AN - SCOPUS:61349179600
SN - 1536-1276
VL - 8
SP - 898
EP - 911
JO - IEEE Transactions on Wireless Communications
JF - IEEE Transactions on Wireless Communications
IS - 2
M1 - 4786452
ER -