Coverage in wireless sensor networks: models and algorithms

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]