An information theoretic point of view to contention resolution

We consider a slotted wireless network in an infrastructure setup with a base station (or an access point) and N users. The wireless channel gain between the base station and the users is assumed to be i.i.d. over users and slots, and the base station seeks to schedule the user with the highest channel gain in every slot (opportunistic scheduling). We assume that contention for opportunistic scheduling is resolved using a series of minislots and with feedback from the base station. In this setup, we formulate the contention resolution problem for opportunistic scheduling as identifying a random threshold (channel gain) that separates the best channel from the other samples. The average delay minimization for contention resolution is then related to entropy (of the random threshold) minimization, which is a concave minimization problem. We illustrate our formulation by studying a popular contention resolution strategy called the opportunistic splitting algorithm (OSA, [9]). OSA is a greedy algorithm that maximizes the probability of success in every minislot. We study the delay and entropy optimality of OSA for i.i.d. wireless channel. Finally, we discuss the applicability of the entropy minimization framework to identify optimal contention resolution strategies for general network scenarios.