Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy

Prasanna Chaporkar, Alexandre Proutiere, and Bozidar Radunovic

Abstract

In Wireless LANs, users may adapt their transmission rates depending on the observed radio conditions on their links to maximize their throughput. Recently, there has been a significant research effort in developing distributed rate adaptation schemes offering better performance than that of the current ARF (Automatic Rate Fallback). Unlike previous works, this paper characterizes the optimal reaction of a rate adaptation protocol to the contention information received from the MAC. We formulate this problem analytically. We study both competitive and cooperative user behaviors: In the case of competition, users selfishly adapt their rates so as to maximize their own throughput, whereas in the case of cooperation they aim at adapting their rates to maximize the overall system throughput. We show that the Nash Equilibrium realized in the case of competition can be inefficient (i.e., the price of anarchy is high, up to 50% of the social optimum), and provide insightful properties of the socially optimal rate adaptation schemes. We also show that RTS/CTS does not make the competitive scenario more efficient. We then apply the same analysis to recently proposed collision-aware rate adaptation algorithms and observe similar conclusions. Finally, we propose a novel collision-aware rate adaptation algorithm that significantly reduces the price of anarchy in many scenarios of interest. %Collision-aware algorithms have been recently proposed to handle the %interaction of the distributed scheduling (DCF) and rate adaptation %schemes, and require that users are able to differentiate packet %collisions from transmission failures caused by channel errors.

Details

Publication typeTechReport
NumberMSR-TR-2008-137
Pages22
InstitutionMicrosoft Research
> Publications > Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy