Information Technology Reference
In-Depth Information
and communication activities are considered. Liu et al propose a method based on
elastic neural network to reduce energy consumption under the background of tracking
aerial flying targets with the aim of the task allocation of collaborative technique in
wireless sensor network
[3]. In order to prolong the lifetime, reduce the energy con-
sumption and balance the network load effectively, CHEN et al propose a dynamic
Coalition model and its corresponding algorithm of task assignment in wireless sensor
network (WSN)
[4]. This method describes a cost function according to the execution
time, energy consumption and load balance. Particle swarm optimization (PSO) is used
to optimize task allocation. And on this basis propose a multi-agent-based architecture
for WSNs and construct a mathematical model of dynamic Coalition for the task allo-
cation problem
[5].
Since Maynard Smith and Price introduced the ideas of evolutionary into game
theory, learning from the analysis method of biological theory of evolution became a
new way to calculate Nash equilibrium points and had been obtained abundant out-
comes[6~8]. As in [9], the solution of the Nash equilibrium been shown to belong
PPAD problem completely. Thomas et al solves the Nash equilibrium by using the
genetic algorithms
[10]. YI et al built a Grid model of m*n type grid using M/ M/ 1
queue system, and promoted the concept of task scheduling Nash equilibrium among
multi-schedulers. The optimal objective of each scheduler is mean complete time per
task
[11].
This paper also based on the mechanism of dynamic coalition, and PSO was
adopted to design a WSNs task allocation algorithm based on game theory. PSO is
simple and easy to implement, and with no gradient information and with other ad-
vantages, which can be used to solve many complex problems. Our algorithm is able
to adapt to the dynamic change of network load and adjust the network running status
in time. This paper defines the utility function with the goal of reducing the execution
time, reducing transport energy consumption and balancing network energy distribu-
tion, and using PSO to obtain the Nash equilibrium of tasks allocation. The results of
experiment show its dependability and feasibility. The following will detail descrip-
tion of the problem as well as the specific algorithm implementation.
2
Model of Dynamic Task Allocation
2.1
Parallel Coalition
Coalition formation is a key problem in multi-agent systems. Parallel Coalition
[12] is
a concurrent generation problem of multiple dynamic coalitions. Parallel Coalition
consists of two cases: Crossed Coalition and multi-task Coalition. Crossed Coalition
means that an agent to join multiple coalition s or a task can be performed by multiple
Coalitions.
Due to the limitations of WSNs such as resource availability and shared
communication medium, parallel processing among sensor nodes is a promising
solution to provide the demanded computation capacity in WSNs. Considering many
points of similarity between WSNs and multi-agent systems, this paper introduces the
complicated coalition into WSNs. As shown in Figure 1, a coalition consists of a
