| dc.description.abstract | Due to technological advances which enabled their deployment in relevant and diverse
scenarios, Wireless Sensor Networks (WSNs) have been object of intense study in the last
few years. Possible application contexts include environmental monitoring, tra c control,
patient monitoring in healthcare and intrusion detection, among others (see, for example,
[1], [2], [3]). The general structure of a WSN is composed of several hardware devices
(sensors) deployed over a given region of interest. Each sensor can collect information or
measure physical quantities for a subregion of the space around it (its sensing area), and
more in particular for speci c points of interest (target points or simply targets) within this
area. The targets located in the sensing area of a given sensor s are covered by s. Individual
sensors are usually powered by batteries which make it possible to keep them functional for
a limited time interval, with obvious constraints related to cost and weight factors. Using a
network of such devices in a dynamic and coordinated fashion makes it possible to overcome
the limitations in terms of range extension and battery duration which characterize each
individual sensor, enabling elaborate monitoring of large regions of interest. Extending
the amount of time over which such monitoring activity can be carried out represents
a very relevant issue. This problem, generally known as Maximum Lifetime Problem
(MLP), has been widely approached in the literature by proposing methods to determine:
i) several subsets of sensors each one able to provide coverage for the target points and
ii) the activation time of these subsets so that the battery constraints are satis ed. It
should be noted that while sensors could be considered as belonging to di erent states
during their usage in the intended application (such as receiving, transmitting, or idle) in
this context two essential states can be identi ed. That is, each sensor may currently be
active (i.e. used in the current cover, and consuming its battery) or not. Activating a
cover refers therefore to switching all its sensors to the active state, while switching o all
the other ones. This research thesis shows a detailed overview about the wireless sensor
networks, about their applications but mainly about typical coverage issues in this eld. In
particular, this work focuses on the issue of maximizing the amount of time over which a
set of points of interest (target points), located in a given area, can be monitored by means
of such wireless sensor networks. More in detail, in this research work we addressed the
maximum lifetime problem on wireless sensor networks considering the classical problem
in which all targets have to be covered (classical MLP) and a problem variant in which
a portion of them can be neglected at all times ( -MLP) in order to increase the overall
network lifetime. We propose an Column Generation approach embedding an e cient
genetic algorithm aimed at producing new covers. The obtained algorithm is shown to be
very e ective and e cient outperforming the previous algorithms proposed in the literature
for the same problems. In this research work we also introduce two variants of MLP problem
with heterogeneous sensors. Indeed, wireless sensor networks can be composed of several
di erent types of sensor devices, which are able to monitor di erent aspects of the region
of interest including temperature, light, chemical contaminants, among others. Given
such sensor heterogeneity, di erent sensor types can be organized to work in a coordinated
fashion in many relevant application contexts. Therefore in this work, we faced the problem
of maximizing the amount of time during which such a network can remain operational
while assuring globally a minimum coverage for all the di erent sensor types. We considered
also some global regularity conditions in order to assure that each type of sensor provides
an adequate coverage to each target. For both these problem variants we developed another
hybrid approach, which is again based on a column generation algorithm whose subproblem
is either solved heuristically by means of an appropriate genetic algorithm or optimally by
means of ILP formulation. In our computational tests the proposed genetic algorithm is
shown to be able to meaningfully speed up the global procedure, enabling the resolution of
large-scale instances within reasonable computational times. To the best of our knowledge,
these two problem variants has not been previously studied in the literature. [edited by author] | en_US |
