Information Technology Reference
In-Depth Information
3
Our Algorithm
This paper assumes that a coalition is constituted by a number of sensor nodes, and
these nodes are mutually closer in distance. Tasks are scheduled on the coalitions,
rather than directly on the sensor nodes. Algorithm assigns tasks according to the
current situation of networks. With development of energy consumption, the algo-
rithm adaptively adjusts the allocation plan. The condition that the Nash equilibrium
scheduling algorithm directly work on coalitions can be established is: a coalition is
constituted by several nodes, therefore, a coalition can be considered to be a virtual
node which has stronger ability and higher energy. Meanwhile, as mentioned above,
both of multi-tasks allocation and solution of Nash equilibrium belong to NP-hard
problem, take such an approach can reduce the scale of problem to obtain the solution
of the problem quickly and reduce the difficult of experimental simulation. Specific
implementation approach of our algorithm is given below.
Definition 2.
Three components of game theory in our algorithm:
(1)
players of game is s set of non-cooperative tasks,
T= (t
1
, t2, ..., t
m
)
;
(2)
The pure strategy set of players consist of n coalition, coalitions are heterogene-
ous, and coalitions have own corresponding task ability, transmission consump-
tion and residual energy; The corresponding mixed strategy set of players is
X=(x
1
, x
2
,… , x
n
)
, where
x
i
is called mixed strategy of
i
-th player;
(3)
In game theory, the utility function is an important indicator to measure the gain
of players, it defined herein is:
uw t
i
j
=× +×
w
cos
t
+×
we
(6)
1
j
2
ij
3
j
u
represents utility function which is used to transform multi-target to
single target, and denotes the gain that
i
-th task obtain from
j
-th coalition. The smaller
the value of utility function, the better;
nt
j
is the sum of
busy
j
and
Time
ji
,
busy
j
denotes
the busy time of
j
-th coalition;
cost
ij
denotes transmission energy consumption of the
i
-
th player in the
j
-th coalition;
e
j
denotes the residual energy of
j
-th coalition;
w
1
,
w
2
and
w
3
denote weight value.
i
Where
3.1
Nash Equilibrium PSO
In this paper, according to Definition 2, we use PSO to find the point of Nash Equili-
brium. And our algorithm is called NEPSO.
We use the floating number matrix to represent the task allocation plan. The utility
function is defined to optimize task execution time, energy consumption and energy
entropy of network. Then we use utility function to further define the fitness function
of PSO.
We use a matrix
X
m
×
to code the position of a particle:
1
x
1
1
x
l
12
mT
Xxx
=
(, , , )
x
=
(7)
m
m
x
x
1
l
