Information Technology Reference
In-Depth Information
number of nodes, and tasks are assigned to the selected coalition structure. Using this
method we can take full advantage of the core capacity of member nodes, which can
lead to finishing the tasks more efficiently and is more suitable for the application
environment of WSNs.
2.2
The Concept of Mixed Nash Equilibrium
Game theory is a mathematical decisive approach aiming to solve the problem between
competition and cooperation. If there is a competing or collaborative behavior among
bodies in the environment, they will tend to adopt some effective strategies to maxim-
ize the utility of the individual of group. Generally, game body, strategy and utility
are three main elements of game theory. The game body also acts as the player for the
game. In general, a game requires at least two players. Besides, the game strategy is
the actions of each body which is defined in advance, and each body has their own
strategy set. In additional, each player of the game has a utility function to estimate
the utility obtained from a certain strategy of the body. Assuming an
n
-person non-
cooperative game, the pure strategy of player
p
i
is defined as
S
i
=
(
s
i
1
, s
i
2
, ···, s
i
mi
),
where
m
i
denotes the number of the pure strategy of
p
i
. The corresponding mixed
strategy of the pure strategy
S
i
is defined as
x
i
= (x
i
1
, x
i
2
, ···, x
i
mi
)
, where
x
i
meets
x
i
j
≥0
and
x
i
1
+x
i
2
+···+x
i
mi
=
1. i.e., the player selects the pure strategy
s
i
j
(1
≤j≤m
j
) with
probability
x
i
j
. Then the mixed situation of the game theory can be defined as
X=
(x
1
, x
2
, ···, x
n
)
.
In this mixed situation, the expected payoff of
p
i
is defined as follows:
1
m
m
m
2
n
1
2
n
12
n
(1)
uX
(
)
=
...
Ps s
(
,
,...,
s
)
•
x
•
x
•
...
•
x
i
i
j
j
j
j
j
j
12
n
1
2
n
j
=
1
j
=
1
j
n
=
1
1
2
Where
P
i
(s
1
j1
, s
2
j2
, ···, s
n
jn
)
denotes the gain of player
p
i
when
p
1
select strategy
s
1
j1
,
player
p
2
select strategy
s
2
j2
,
···
, and player
p
n
select strategy
s
n
jn
.
Definition 1.
If the mixed situation
X
*
meets
u
i
(X
*
||x
i
)≤u
i
(X
*
)
, the mixed situation
X
*
is the mixed Nash Equilibrium of an
n
-person non-cooperative game where
X
*
||x
i
denotes that only
p
i
change its strategy.
Property 1.
The mixed situation
X
*
is the mixed Nash equilibrium of an
n
-person
non-cooperative game if and only if the pure strategy
s
i
j
meets
u
i
(X
*
|| s
i
j
)≤u
i
(X
*
)
.
Proof:
Suppose that
X
*
is the mixed Nash equilibrium. If
u
i
(X
*
|| s
i
j
) ≥u
i
(X
*
)
, the
player
p
i
will obtain a better gain when it select strategy
s
i
j
. According to the idea of
game theory, Nash equilibrium is the best select of each player, so
X
*
will not be
mixed Nash equilibrium.
2.3
Task Allocation
A wireless sensor network consisting of n heterogeneous wireless sensor nodes distri-
buted in a certain range, and 10% of the node elected as the leader node. The number
of Coalition is l, and we define the set of coalitions as
C= (c
1
, c
2, ···,
cl)
, where
l=n*10%
. A set of independent tasks
T= (t
1
, t2, ···, t
m
)
arrive at sink node at the
same time.
