Efficient wireless packet scheduling in a non-cooperative environment: Game theoretic analysis and algorithms

Abstract

In many practical scenarios, wireless devices are autonomous and thus, may exhibit non-cooperative behaviors due to self-interests. For instance, a wireless cellular device may be programmed to report bogus channel information to gain resource allocation advantages. Such non-cooperative behaviors are highly probable as the device's software can be modified by the user. In this paper, we first analyze the impact of these rationally selfish behaviors on the performance of packet scheduling algorithms in time-slotted wireless networks. Using a mixed strategy game model, we show that the traditional maximum rate packet scheduling algorithm can cause non-cooperative devices to converge to highly inefficient Nash equilibria, in which the wireless channel resources are significantly wasted. By using a repeated game to enforce cooperation, we further propose a novel game theoretic algorithm that can lead to an efficient equilibrium. © 2010 Elsevier Inc. All rights reserved.