Published in Qin, X., & Berry, R. (2003). Exploiting multiuser diversity for medium access control in wireless networks. INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 1084-1094. ©2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.


Multiuser diversity refers to a type of diversity present across different users in a fading environment. This diversity can be exploited by scheduling transmissions so that users transmit when their channel conditions are favorable. Using such an approach leads to a system capacity that increases with the number of users. However, such scheduling requires centralized control. In this paper, we consider a decentralized medium access control (MAC) protocol, where each user only has knowledge of its own channel gain. We consider a variation of the ALOHA protocol, channel-aware ALOHA; using this protocol we show that users can still exploit multi-user diversity gains. First we consider a backlogged model, where each user always has packets to send. In this case we show that the total system throughput increases at the same rate as in a system with a centralized scheduler. Asymptotically, the fraction of throughput lost due to the random access protocol is shown to be 1/e. We also consider a splitting algorithm, where the splitting sequence depends on the users’ channel gains; this algorithm is shown to approach the throughput of an optimal centralized scheme. Next we consider a system with an infinite user population and random arrivals. In this case, it is proved that a variation of channel-aware ALOHA is stable for any total arrival rate in a memoryless channel, given that users can estimate the backlog. Extensions for channels with memory are also discussed.