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

VL - 8

SP - 1073

EP - 1079

JO - IEEE Transactions on Wireless Communications

JF - IEEE Transactions on Wireless Communications

SN - 1536-1276

IS - 3

M1 - 4801448

ER -