An Improved Backoff Algorithm for Wireless Sensor Network
Based on Game Theory
Yanliang Jin
1
, HuiJun miao
1
,Haitao Liu
2
1.Key Laboratory of Special Fiber Optics and Optical Access Networks of Ministry of Education, Shanghai University,
Shanghai China, 200072
2. SIMIT, Shanghai, China, 200050
Phone: (86)21-56331423, Fax: (86)21-56332292
E-mail: jinyanliang@staff.shu.edu.cn; kalwen@163.com
Keywords: backoff ; wireless sensor network; game theory.
Abstract
The Binary Exponential Backoff (BEB) is used by IEEE
802.15.4 Medium Access Control (MAC). BEB regulates CW
abruptly which causes problem of more packet collision and
delay alternating. This paper introduces the game theory into
the backoff algorithm of wireless communication. Results
from simulation experiments reveal that the new algorithm
achieves higher throughput and less packet collision rate
when in a wireless sensor network environment.
1 Introduction
IEEE 802.15.4 standard is to achieve the characteristics of
low power and low rate for wireless personal area networks to
meet the demands of sensor networks.
V.Bharghavan proposed a Multiplicative Increase Linear
Decrease backoff algorithm which is called MILD.
Chengliang Na proposed an AASC backoff algorithm that can
adapt to flow and avoid second-collision. [1]
In literature [3], Liqiang Zhao and Hailin Zhang use the
incompletely cooperative game theory to improve the
traditional contention-based MAC protocols.
Saher S. Manaseer and Mohamed Ould-Khaoua proposed
Logarithmic Based Backoff Algorithm for MAC Protocol in
MANETs. [5]
Game theory is a discipline aimed at modelling situations in
which decision makers have to make specifications that have
mutual, possibly confliction, consequences. Recently, game
theory has been applied to wireless communications where
the decision makers in the game are devices willing to
transmit or receive data.
The rest of this paper is organized as follows. Section 2
introduces the game theory into wireless communication, and
point out the Nash equilibrium point of the model. Section 3
introduces the traditional algorithm of 802.15.4(BEB) and
describes the backoff algorithm suggested by this technical
paper. Section 4 describes simulation environment and
discusses the results compared to IEEE 802.15.4 BEB
algorithm. Section 5 concludes this technical paper, suggests
that the new algorithm achieves higher performance in the
environment of wireless sensor network.
2 Game Theory Model for Wireless
Communication
There’s a simple communication model of game theory as
follow.
Fig.1 The simple model
Both of the two transmitters want to send packets to the
receiver between them with a certain probability. This
probability represent for the new data rate of the sensor nodes.
Since radio communication channel is usually shared in
wireless networks, a simultaneous transmission of both
players leads to a collision. If they access the channel in the
same time neither of the packets will be received by the
receiver successfully. Once a transmitter accessed into the
channel, it would cost him a fixed cost 0 < C < 1. Accordingly,
he receives a payoff of 1 if his packet didn’t jam by another
transmitter. Then his totally payoffs would be 1-C. It can
immediately be seen that if transmitter1 accesses the channel,
then the best response of transmitter2 is to wait, and vice
versa.
It is a mixed strategy game in the game theory. For each
player in a mixed strategy game his payoffs can be defined by:
||
ii
sS
ususS
Î
=Î
(1)
The mixed strategy,
s
of player i in a game is a
probability distribution over his pure strategies
.[4]
Here, the payoff of transmitter1 is
112121
=´---´=--
(2)
Likewise, the payoff of transmitter2 is
22
=--
(3)
Transmitter1 Transmitter2
Receiver