A Game-Theoretic Approach to Distributed Opportunistic Scheduling Articles uri icon

publication date

  • October 2013

start page

  • 1553

end page

  • 1566

issue

  • 5

volume

  • 21

International Standard Serial Number (ISSN)

  • 1063-6692

Electronic International Standard Serial Number (EISSN)

  • 1558-2566

abstract

  • Distributed opportunistic scheduling (DOS) is inherently more difficult than conventional opportunistic scheduling due to the absence of a central entity that knows the channel state of all stations. With DOS, stations use random access to contend for the channel and, upon winning a contention, they measure the channel conditions. After measuring the channel conditions, a station only transmits if the channel quality is good; otherwise, it gives up the transmission opportunity. The distributed nature of DOS makes it vulnerable to selfish users: By deviating from the protocol and using more transmission opportunities, a selfish user can gain a greater share of wireless resources at the expense of "well-behaved" users. In this paper, we address the problem of selfishness in DOS from a game-theoretic standpoint. We propose an algorithm that satisfies the following properties: 1) When all stations implement the algorithm, the wireless network is driven to the optimal point of operation; and 2) one or more selfish stations cannot obtain any gain by deviating from the algorithm. The key idea of the algorithm is to react to a selfish station by using a more aggressive configuration that (indirectly) punishes this station. We build on multivariable control theory to design a mechanism for punishment that is sufficiently severe to prevent selfish behavior, yet not so severe as to render the system unstable. We conduct a game-theoretic analysis based on repeated games to show the algorithm's effectiveness against selfish stations. These results are confirmed by extensive simulations.

keywords

  • contention-based channel access; distributed opportunistic scheduling (dos); game theory; multivariable control theory; repeated games; selfish stations; wireless networks; random-access; networks; service; csma/ca