Guiding hyperplane evolutionary algorithm for optimal layout of Wireless Sensors Networks.
Rotar, Corina ; Risteiu, Mircea ; Muntean, Maria 等
1. INTRODUCTION
In many WSN applications the critical issue is the coverage of the
monitoring area. Other applications demand an increased network
lifetime. Generally, both criteria are fundamental and should be taken
into consideration when the WSN is deployed. As the complexity of the
problem is high, a metaheuristic option would be appropriate.
Evolutionary algorithms are an interesting alternative for solving
Optimal WSN layout problem. In (Molina et al., 2008) the problem is
formulated as a bi-objective problem which involves the maximization of
the network's lifetime, and the minimization of the number of
sensor nodes, in order to reduce the network cost. Another work
presented in (Jourdan et al., 2004) considered the coverage and lifetime
of the network as the objectives of the optimization problem and the
solutions are obtained by a popular evolutionary technique for
multiobjective optimization: MOGA. Other interesting problems related to
the wireless sensor network's issues have been successfully
approached by evolutionary techniques: (Yildirim et al., 2008), (Sajid
et al, 2008), (Wang et al, 2007).
Recently, our work focuses on solving the optimal layout of the
sensors using an original evolutionary technique called Guiding
Hyperplane Evolutionary Algorithm. The approach proves itself suitable
for the considered problem. Next, we extend our work in a more general
case, where the sensing and communication radius of the sensors differs.
2. OPTIMAL WSN LAYOUT PROBLEM
Optimal sensors network layout can be reformulated as a
multiobjective optimization problem. The involved criteria are several
to be considered: lifetime of the network, communication's
efficiency, degree of the connectivity, coverage of the network, and so
on. In this paper, we formulate the problem of optimal placement of
sensors as a bi-criteria optimization problem, emphasizing the two major
objectives which derive from the main functions of the sensors:
communication and sensing. Sensor networks represent dense wireless
networks of small, low-cost sensors, which collect and disseminate
environmental data. Each unit of the network is attached by a battery
that provides a limited amount of energy. The purpose of a sensor is to
sense or react smartly at a possible event in its neighborhood and to
transmit the proper information to the High Energy Communication Node
(HECN) of the network. Given the sensing radius, a sensor is able to
gather the right information from its vicinity and further transmit it
to the HECN. Data transmission to the special node is done directly or
via hops, using nearby sensors. Therefore, each sensor also behaves as a
communication relay. The communication between two sensors is possible
if they are within a fixed distance. Given the communication radius, two
sensors are allowed to communicate if the distance between them is less
than communication radius.
The lifetime of the entire network is measured by the elapsed time until the first sensor spends the initial allocated energy (Time to
First Failure). Beyond other tasks, each data transmission accomplished
by a sensor decreases its energy, and consequently, the lifetime of
entire network. Therefore, the lifetime of the network depends by the
maximum number of communication tasks of its nodes. In optimal sensors
placement problem, we focus on finding a configuration which does not
comprise nodes engaged in too many transmission activities.
The coverage of the network represents the other major criteria in
optimal placement of the sensors. The coverage of a specific network is
given by the ratio between the area of the union of the disks centered
at the sensors' positions, of sensing radius and the total area of
the region in which the sensors are placed. Better coverage affects in a
positive way the quality of the network. Therefore, this objective is
maximized.
Another criterion in finding the optimal position of the sensors
arises from the connectivity degree of the network. This objective of
our problem can be simply reformulated as a penalization of the other
two major criteria.
According to the two main functions of a sensor: sensing and
communication, two major objectives arise: the first refers to the
lifetime of the network and the second one measures the coverage of the
net.
3. GHEA FOR OPTIMAL SENSOR NETWORK LAYOUT PROBLEM
In a previous article (Rotar et al, 2009) GHEA technique was
successfully applied on the optimal layout of the WSN problem. Then, the
sensing and communication radius was set to be equal. Further, we
reconsider the problem, taking into account different alues for those
two parameters of the sensors.
In optimal sensor network placement, a solution is given by any
configuration of sensors' locations on the given map. For
simplification we consider that the region where the sensors are placed
is a 2-dimensional area, and each sensor's location is given by the
pair of coordinates ([x.sub.i], [y.sub.i]).A possible network of n
sensors located on the map is represented by the vector: of n pairs of
coordinates. In our approach, we consider a homogenous network; each
sensor has the same initial energy. One sensor will consume exactly one
unit of energy per each transmission it makes. Therefore, if one sensor
behaves as a communication relay, and the number of transmission tasks
is higher, its lifetime decreases accordingly and further the lifetime
of the network decreases. At one time, a particular network should send
data from all sensors to the HECN in an optimal manner. Optimality in
this context refers to the problem of finding the minimum paths from the
HECN to each sensor. For completing this job, Dijkstra's algorithm is applied. After the minimum paths are found, the number of
transmission tasks per sensor is computed. The number of transmission
tasks per sensor is measured by the total number of inputs and outputs a
sensor has to assure. The standard deviance of these values offers an
appropriate measure of the tasks distribution among the network. A
smaller value of this metric is preferred, as it denotes the fact that
transmissions tasks are uniformly distributed among the network and,
therefore, very few sensors are extra loaded and suppressed by too many
communications. The connectivity degree of the network is an important
issue for the formulation of the criteria. The connectivity can be
measured by the number of sensors that are able to communicate to at
least another sensor. If the connectivity is less than the total number
of sensors, the overall quality of the network decreases.
The second criterion refers to the degree of coverage of the
network. As finding the exact value of the area of union of the disks of
sensing radius, centered in sensors' locations (x,y) needs high
computational costs, an approximation approach of the coverage is
chosen. In our approach, we consider a grid which covers the entire map.
Each center of the grid's cell could be included or not into at
least one disk corresponding to a sensor. If the center of a cell is
covered by at least one sensor, we consider that the area corresponding
to that cell is covered by the net. The ratio between the number of
covered cells and the total number of cells give us a useful measure of
the network's coverage ratio. As the GHEA algorithms performs a
minimization of the considered objectives of the problem, and the aim is
to maximize the coverage and the lifetime of the network, the following
functions are considered as objectives for GHEA implementation.
First objective: Considering n--the number of sensors, [xi]--the
number of connected sensors (connectivity degree) and [sigma]--standard
deviation of the numbers of transmission tasks [t.sub.t] of the ith
sensor: the first objective is formulated as follows:
[F.sub.1] = [sigma]/[square root of n] + n - [chi] (1)
Second objective: Considering the grid with m rows and p columns
and g--the number of covered cells of the grid, the second objective
function is formulated as follows:
[F.sub.2] = (m x p - g/(m x p) + n - [chi] (2)
4. EXPERIMENTS
In our experiments, we tried several scenarios which involve
different number of sensors of communication radius [R.sub.C] and
sensing radius [R.sub.S]. We considered that sensing and communication
radiuses are not equal. In our experiment sensing radius is less than
communication radius. Regarding the two parameters lifetime and coverage
are computed. Therefore, coverage measure takes into account the sensing
radius and lifetime is computed accordingly to the communication radius.
The area of 500x500 units has to be covered with the given number of
sensors in an optimal manner. The High Energy Communication Node (HECN)
represents the gateway for external access to the network and it is
located in the center of the area. Several scenarios have beed taken
into consideration. The GHEA algorithm runs for variable number of
sensors, with different sensing radius and communication radius. The
size of the population is set to 50 individuals and the maximum number
of generations is 100.
[FIGURE 1 OMITTED]
[FIGURE 2 OMITTED]
5. CONCLUSION
Using an ideal hyperplane to guide the population of solutions
toward the Pareto front of the considered optimization problem, GHEA
offers in many situations better results than the state-of-the-art
evolutionary algorithms. The WSN layout problem is formulated as a
multiobjective optimization problem, emphasizing two criteria: attaining
the maximum area coverage and a maximum lifetime of the network. For the
simplified model of 2-dimensional map, having a pre-estimated fixed
number of homogenous sensors, GHEA provides the Pareto optimal solutions
of the bi-objective problem. The results show that GHEA technique is
suitable for optimal WSN layout problem; in all experiments, GHEA offers
a good approximation of the Pareto front. As further research, we
investigate GHEA's performance for a heterogenous wireless sensors
network in a more realistic monitored map.
6. REFERENCES
Jourdan, D.B. de Weck, O.L., Layout optimization for a wireless
sensor network using a multi-objective genetic algorithm, Vehicular
Technology Conference, 2004. VTC 2004-Spring. 2004 IEEE 59th, Vol.5,
2005, pp. 2466- 2470
Molina G. and E. Alba and E.-G. Talbi, Optimal Sensor Setwork
Layout Using Multi-Objective Metaheuristics, Journal of Universal
Computer Science 2008, Vol. 14, No. 15, 2008, pp. 2549-2565
Rotar C., Ileana I., Risteiu M., Hutanu C., Optimal sensors network
layout using evolutionary algorithms, Proceedings of WSEAS '09,
Prague, Czech republic, 2009
Sajid Hussain, Obidul Islam, Genetic Algorithm for Energy Efficient
Trees in Wireless Sensor Networks, Advanced Intelligent Environments,
Springer, 4(1), pages 36, 2008
Wang, X.; Ma, J.; Wang, S.; Bi, D. Distributed Particle Swarm
Optimization and Simulated Annealing for Energy-efficient Coverage in
Wireless Sensor Networks. Sensors 2007, 7, pp. 628-648
Yildirim, K. S., Kalayci, T. E., U ur, A., Optimizing coverage in a
K-covered and connected sensor network using genetic algorithms. Proc.
of the 9th WSEAS Conference on Evolutionary Computing, Wisconsin, 2008
