TY - CONF T1 - Capacity of Asynchronous Random-Access Scheduling in Wireless Networks T2 - IEEE INFOCOM 2008. The 27th Conference on Computer Communications Y1 - 2008 A1 - Chafekar,D. A1 - Levin,D. A1 - Kumar,V. S.A A1 - Marathe,M. V A1 - Parthasarathy,S. A1 - Srinivasan, Aravind KW - asynchronous random-access scheduling KW - channel access probability KW - Computer networks KW - Computer science KW - Educational institutions KW - Interference KW - Optimal scheduling KW - Peer to peer computing KW - probability KW - Processor scheduling KW - radio link KW - radio links KW - radio networks KW - Routing KW - scheduling KW - Throughput KW - throughput capacity KW - wireless channels KW - Wireless networks AB - We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models. JA - IEEE INFOCOM 2008. The 27th Conference on Computer Communications PB - IEEE SN - 978-1-4244-2025-4 M3 - 10.1109/INFOCOM.2008.170 ER -