TY - JOUR
T1 - Utility-optimal random access without message passing
AU - Rad, A. Hamed Mohsenian
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; and NSF CNS-0720570, ONR N00014-07-1-0864, and AFOSR FA9550-06-1-0297.
PY - 2009/3
Y1 - 2009/3
N2 - Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.
AB - Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.
KW - Message passing
KW - Network utility maximization
KW - Non-convex optimization
KW - Random access
KW - Wireless scheduling
UR - http://www.scopus.com/inward/record.url?scp=62949207182&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=62949207182&partnerID=8YFLogxK
U2 - 10.1109/TWC.2009.071446
DO - 10.1109/TWC.2009.071446
M3 - Article
AN - SCOPUS:62949207182
SN - 1536-1276
VL - 8
SP - 1073
EP - 1079
JO - IEEE Transactions on Wireless Communications
JF - IEEE Transactions on Wireless Communications
IS - 3
M1 - 4801448
ER -