A Stochastic Game Analysis of the Binary Exponential Backoff Algorithm with Multi-Power Diversity and Transmission Cost

In this paper, we present a game analysis of the Binary Exponential Backoff (BEB), a popular bandwidth allocation mechanism used by a large number of distributed wireless technologies. A Markov chain analysis is used to obtain equilibrium retransmission probabilities and throughput. Numerical results show that when the arrival probability increases, the behavior of mobile stations MSs become more and more aggressive resulting in a global deterioration of the system throughput. We then consider a non-cooperative game framework to study the operation and evaluate the performance of the BEB algorithm when a group of MSs competing with each other to gain access to the wireless channel. We focus our attention to the case when an MS acts selfishly by attempting to gain access to the channel using a higher retransmission probability as a means to increase its own throughput. As a means to improve the system performance, we further explore the use of two transmission mechanisms and policies. First, we introduce the use of multiple power levels (MPLs) for the data transmission. The use of multiple power levels results on a capture effect allowing the receiver to properly decode the message even in the presence of a collision. Under the proposed scheme, named MPL-BEB, the effect of the aggressive behavior, higher transmission probabilities, is diminished since the power level is chosen randomly and independently by each and every station. Second, we introduce a disutility policy for power consumption. The resulting mechanism, named MPL-BEB with costs, is of prime interest in wireless networks composed of battery-powered nodes. Under this scheme aggressive behavior is discouraged since each retransmission translates into the depletion of the energy stored in the battery. Via price of anarchy, our results identify a behavior similar to the well-know prisoner’s dilemma. A non-efficiency of Nash equilibrium is observed for all schemes (BEB, MPL-BEB, MPL-BEB with costs) under heavy traffic with a notable outperformance of MPL-BEB with costs over both MPL-BEB and BEB.