Multi-objective genetic algorithm for the automated planning of a wireless
sensor network to monitor a critical facility
Damien B. Jourdan
Dept. of
Aeronautics and Astronautics, Massachusetts Institute of Technology
77
Massachusetts Ave., Cambridge, MA, USA 02139
ABSTRACT
This paper examines the optimal
placement of nodes for a Wireless Sensor Network (WSN) designed to monitor a
critical facility in a hostile region. The sensors are dropped from an
aircraft, and they must be connected (directly or via hops) to a High Energy
Communication Node (HECN), which serves as a relay from the ground to a
satellite or a high-altitude aircraft. The sensors are assumed to have fixed
communication and sensing ranges. The facility is modeled as circular and
served by two roads. This simple model is used to benchmark the performance of
the optimizer (a Multi-Objective Genetic Algorithm, or MOGA) in creating WSN
designs that provide clear assessments of movements in and out of the facility,
while minimizing both the likelihood of sensors being discovered and the number
of sensors to be dropped. The algorithm is also tested on two other scenarios;
in the first one the WSN must detect movements in and out of a circular area,
and in the second one it must cover uniformly a square region. The MOGA is
shown again to perform well on those
scenarios, which shows its flexibility and possible application to more complex
mission scenarios with multiple and diverse targets of observation.
Keywords: Multi-objective genetic
algorithm, wireless sensor network, network planning, node placement, facility
monitoring, coverage.
1. INTRODUCTION
Recent military operations
demonstrated the limitations of surveillance missions performed by
high-altitude platforms (UAV, U2, satellite) even when equipped with state of
the art sensors. Most of these limitations are inherent to this type of
long-distance surveillance and cannot be resolved with any improvement in the
onboard-sensor technology. Indeed these
techniques are useful to detect features on the ground (such as facilities or
vehicles), but they are often insufficient for identifying them with
certainty and monitoring their activity. In order to gain a clear understanding
of the situation on the ground, it is vital to observe from close range using
remote sensing devices placed around the feature of interest, e.g. Wireless
Sensor Networks (WSN). Since these missions will be performed in hostile areas,
the placement of such sensors needs to be done without human personnel involved,
e.g. via aerial deployment from an aircraft. Once the sensors are deployed on
the ground, their data is transmitted back to the home base to provide the
necessary situational awareness.
The
deployed units (the wireless sensors, called sensors in the following) fulfill
two fundamental functions: sensing and communicating. The sensing can be of different
types depending on the feature to observe (seismic, acoustic, chemical,
optical, etc.), and the communication is performed wirelessly. However, the
small size and energy storage capacity of the sensors prevent them from
relaying their gathered information directly to the base. It is therefore
necessary that they transmit their data to a high-energy communication node
(HECN) able to provide the transmission relay to an aircraft or a satellite.
All sensors must be able to transmit their data to this node, either directly
or via hops, using nearby sensors as communication relays. In this paper an idealized
model for the two characteristics of the sensors is used; they can communicate with one another if they are within a
fixed distance RCOMM, and they can sense anything within
their sensing radius RSensing. All sensors in the WSN are
assumed to be identical. They also must be connected to
the HECN in order to transmit their
data to the base. This is illustrated in Fig. 1, where the area covered by each
sensor is shown as a circle (sensing disk) and arrows represent the
communication links present between sensors. The HECN is placed on top of a
building.
Three case studies are conducted.
In the first one (Case 1), the feature to monitor is a facility served by two
roads. The WSN must provide a good coverage of the facility, i.e. it must be able to detect movement along the
roads (where it is most likely to occur), but also around the facility as a
whole. Moreover, since the area is hostile, the survivability of the WSN
depends on whether the sensors will be
detected or not. The closer to the facility sensors are placed, the greater the
probability that they will be discovered. Finally the network is
deployed from an aircraft that can only carry a limited
2. LITERATURE REVIEW
From the early 1990’s to a few
years ago, a large body of research was devoted to the Base Station (BS)
location problem for cellular phone networks. At that time the problem was to
find the optimal location of BS (transmitters) in order to satisfactorily cover
subscribers. Although this problem differs in many aspects from the sensor
network planning problem (notably because in WSN the sensors (“BS”) also need
to communicate with each other (connectivity)), it is insightful to review the
methods used. These range from Dynamic Programming1, to Genetic
Algorithms2,3 and Tabu Search4. Virtually every type of
optimization technique was tested on this problem, many of which dealt with
multiple objectives (though often blended into a single objective function,
except Meunier3 who uses Pareto optimality) while using non-trivial
communication models taking the terrain into account.
The BS location problem is part of
the larger topic of Facility Location in Operations Research5. Here
a set of demand points must be covered by a set of facilities (which corresponds
in WSN to covering an area with a set of sensors). The goal is to locate these
facilities so as to optimize a certain objective (e.g. minimize the total
distance of demand points to their closest
facility). A classic example close to the WSN problem is the Maximal Covering
Location Problem6,7 (MCLP), where as many demand points as possible
must be covered with p sensors of fixed radius. It is also referred to
as a location-allocation problem, since each demand point must be assigned to a
certain sensor. Again in all these
discussions, the main difference with WSN is that the nodes are not required to
be connected. Another problem of interest is the Facility
Location-Network Design problem, where facilities positions need to be
determined (just as in
MCLP) and the network connecting
these facilities must also be optimized. Unfortunately, in WSN design it is
impossible to decouple sensor placement and network design, since the location
of the sensors determines the network topology.
The past three years
have seen a rising interest in sensor network planning, focusing mostly on
optimizing the location of the sensors in order to maximize their collective
coverage (a problem almost identical to the BS location problem). Several techniques were used, but the research on BS location
is never mentioned. Chakrabarty8 used Integer Programming, while Bulusu9, Dhillon10
and Howard11,12 devised different greedy heuristic rules to
incrementally deploy the sensors. Zou13
adapted Virtual Force Methods (often used for the deployment of robots12)
for the sensor deployment. Only one objective is optimized in these
methods, although in the greedy algorithms referenced above it is possible to obtain the trade-off between number of sensors
and coverage (e.g. by continuing to add sensors and noticing how much coverage
is gained each time). Particular to WSN is the relationship between optimal WSN
layout and the ratio between the sensors sensing and communication
radius. This interaction is studied in Jourdan14.
Current work on WSN
gives little or no attention to the communication requirement between sensors.
Also, only a single objective is considered
(almost always coverage), whereas it seems other considerations are also of
vital practical importance in the choice of the network layout
(survivability, robustness to node failure, etc.). This paper presents a method
that starts addressing these gaps, while testing it on realistic (although
simplified) scenarios.
3. MODELING
3.1 WSN Modeling
The area considered is a flat
square of side 10 (in arbitrary units), centered on the origin. The sensors are
identical and are characterized as follows.
They can monitor anything within RSemmg and they can
communicate with any other sensor located within RComm. The HECN, with
which each sensor must communicate (either directly or through hops using nearby sensors) is assumed to have been placed
beforehand (presumably in a location with good line of sight to the relay aircraft
or satellite). In this paper it is placed at the upper right corner of the
area. This assumption is for convenience and does not prevent generalizability.
The
design variables correspond to the horizontal and vertical coordinates of the
sensors, and the maximum number of sensors MAXJJUM is a parameter fixed by the
operator (it may correspond to the total number of available sensors). The
vector DV containing the design variables is of size 2 x MAXJJUM:
DV=[x1 y1 ... õøõ_ìì óøõ_øì] (1)
Although DV is of constant
size, the number of sensors actually present in each design vector is allowed
to vary (this is important for the optimization described below). For a WSN
containing less than MAXJJUM sensors, the remaining entries are set to
0. So if x, and y, are both equal to 0, it
signifies that there is no ith sensor. Therefore, for a WSN
containing n sensors (with n less than MAXNUM), MAXJIUM-n pairs of
entries of DFwill be equal to 0. Equation 2 is an example of a design
for a network with at most 4 sensors, where only 2 sensors are present (the
first and third sensors).
DV=[x1 y1 0 0 x3 y3 0
0] (2)
3.2 Objectives Calculation
The operator designating the
features of interest has the choice to select what type of surveillance action (s)he
wishes to take. For example, the movements
in and out of a facility may be of interest in order to identify the use of the
compound (Case 1). It may also be the case that a “suspect” area has
been selected, and the operator wishes to discover what kind of activity is taking place there. He may wish to
monitor the movements in and out of it without placing sensors directly inside
it, corresponding to perimeter monitoring (Case 2), or he may decide to cover
it uniformly in order to have complete coverage (Case 3). These three cases
illustrate possible mission scenarios for the WSN, and the following sections
detail how the objectives are calculated in each case. In all cases, only the
sensors connected to the HECN are taken into account in the calculation of the
objectives.
4.1 Case 1
The objectives graph is shown in
Fig. 6a, where the objectives of the individuals from all 300 generations are
plotted. The approximate Pareto Front can be observed, from which the user can view
the trade-off between the three objectives and choose a design based on his or
her preference. The utopia point is where coverage and survivability are 1, and
the number of sensors is 0. The remaining plots of Fig. 6 are examples of
Pareto-optimal designs, to illustrate the trade-off between coverage,
survivability and number of sensors. This optimization took 24 minutes to
complete.
These results confirm the intuition
about this problem. Higher survivability is achieved by placing the sensors far
away from the facility and the roads (Fig. 6b), and to maintain full coverage
of the movements more sensors are needed (compare (b) and (d)). The cost for
using less sensors (and requiring the same full coverage) is a lower
survivability: it drops of 39% from that with 9 sensors (0.73) to that with 5
sensors (0.44). The layouts selected in Fig. 6 all have a coverage value close
to 1. However it may be the case that the survivability is the greatest concern
for a particular mission (e.g. if we want the WSN to stay on site for a long
time), so that we are ready to sacrifice some coverage in order to gain some
survivability. Given a certain number of sensors (from 9 to only 1),
Pareto-optimal layouts with the largest survivability are found to have the
same structure as in Fig. 6b, with the coverage decreasing as more and more
sensors are removed from the original layout shown in Fig 6b.
4.2 Case 2
The objectives graph is shown in
Fig. 7a, this time with only two objectives, coverage and number of sensors.
The approximate Pareto Front is plotted as
a black line. It shows the trade-off between coverage of the area versus number
of sensors. This optimization took 20 minutes to complete.
Results of the MOGA are shown in Fig. 8. These results agree again with
the intuition, showing that the MOGA finds optimal layouts (notice the
symmetrical structures that appear). Although in this case study the coverage
is calculated in a different way, the very same MOGA used in Cases 1 and 2
works well. This illustrates the flexibility of this algorithm to the modeling
and the choice of objectives. This optimization took 25 minutes to complete.
5. CONCLUSIONS AND FUTURE WORK
The automated planning of WSN will
become crucial in the near future. However, little research has gone into
devising a planner that accounts for the specificities of WSN (e.g. the
communication connectivity requirement between sensors and the multi-objective
aspect). Also, the variety of missions that WSN will be asked to perform calls for
a flexible optimization technique.
In this paper we first described
the modeling used for the terrain and the sensors, and then three mission
scenarios were proposed: the monitoring of the movements in and out of a facility
served by two roads (with hostile threats to the WSN), the monitoring of the
movements in and out of a perimeter, and the uniform monitoring of an area.
These three examples are not comprehensive of all scenarios that will come up
in reality, but they provide important basic building blocks of more complex
missions.
The Multi-Objective
Genetic Algorithm (MOGA) used to perform the optimization was then described,
and the results on the three above scenarios were presented. It was shown that
the MOGA successfully generated the Pareto Front of non-dominated network
designs, providing the decision-maker with useful trade-off information between
the objectives. Also, the very same algorithm was used in all three instances,
where the only change is in the objective functions. This shows the flexibility
of the algorithm chosen, and it is promising for more complex scenarios.
More work is required on the MOGA itself in order to increase its
efficiency, especially by tailoring it more to the specificities of WSN. Also, a case study involving several of the basic
mission scenarios described in this paper, as well
as multiple HECN, should be performed. Other
objectives such as the robustness of the WSN to node failure should also be explored. The fact
that the network will be dropped by an aircraft is also of major importance,
since it will incur some uncertainty in the final positions of the sensors.
Integrating the airdrop uncertainty in the WSN planner will provide more
robustness to the deployment process and increase the chances that the WSN
actually placed on the ground will perform as planned. Finally a more realistic
model for the terrain should be implemented, where an uneven terrain produces
non-circular sensing and communicating ranges.
REFERENCES
1. R. Rose, “A smart
technique for determining base-station locations in an urban environment,” Proc.
IEEE Vehicular Technology Conference, vol. 50, pp. 43-47, Jan. 2001.
2. J. K. Han, B. S. Park, Y.
S. Choi and H. K. Park, “Genetic approach with a new representation for base
station placement in mobile communications,” Proc. IEEE Vehicular Technology
Conference, vol. 4, pp. 2703-2707, Oct. 2001.
3. H. Meunier, E. Talbi, P.
Reininger, “A multiobjective genetic algorithm for radio network optimization,”
Proc. Congress on Evolutionary Computation, vol. 1, pp. 317-324, July
2000.
4. E. Amaldi, A. Capone, F.
Malucelli, F. Signori, “UMTS radio planning: optimizing base station configuration,”
Proc. IEEE Vehicular Technology Conference , vol. 2, pp. 768-772, Sept.
2002.
5.
Z. Drezner, H. W. Hamacher (editors), Facility location: applications
and theory, Springer-Verlag, Berlin, 2002.
6. R. Church, C. ReVelle,
“The maximal covering location problem,” Papers of The Regional Science
Association, 32: 101-118, 1974.
7. A. Mehzer, A. Stulman,
“The maximal covering location problem with facility placement on the entire
plane,” Journal of Regional Science, vol. 22, no. 3, 1982.
8. K. Chakrabarty, S. S.
Iyengar, H. Qi and E. Cho, “Grid coverage for surveillance and target location
in distributed sensor networks,” IEEE Transactions on Computers, vol.
51, pp. 1448-1453, Dec. 2002.
9. N.
Bulusu, J. Heidemann and D. Estrin, “Adaptative beacon placement,” Proc.
Int. Conf. on Distributed Computing Systems, pp. 489-498, Apr. 2001.
10. S. S. Dhillon, K.
Chakrabarty and S. S. Iyengar, “Sensor placement for grid coverage under
imprecise detections,” Proc. Int. Conf. on Information Fusion, vol. 2, pp. 1581-1587, Jul.
2002.
11. A. Howard, M. J. Mataric
and G. S. Sukhatme, “An incremental self-deployment algorithm for mobile sensor
networks,” Autonomous Robots Special Issue on Intelligent Embedded Systems,
vol. 13, no. 2, pp. 113-126, 2002.
12. A. Howard, M. J. Mataric
and G. S. Sukhatme, “Mobile sensor network deployment using potential fields: a
distributed, scalable solution to the area coverage problem,” Proc. Int.
Conf. on Distributed Autonomous Robotic Systems, pp. 299-308, 2002.
13. Y. Zou and K.
Chakrabarty, “Sensor deployment and target localization based on virtual
forces,” Proc. IEEE Infocom Conference, vol. 2, pp. 1293-1303, Apr.
2003.
14. D. B. Jourdan and O. L.
de Weck, “Layout optimization for a wireless sensor network using a
multi-objective genetic algorithm,” to appear in Proc. IEEE Vehicular
Technology Conference, Milan, May 2004.
15. C. M. Fonseca and P. J.
Fleming, “Genetic algorithms for Multiobjective optimization: formulation,
discussion and generalization”, Genetic Algorithms: Proc. Fifth
International Conference, pp 416-423, Morgan Kaufmann, 1993.