Coverage in wireless sensor networks: models and algorithms

Due to technological advances which enabled their deployment in relevant and diversescenarios, Wireless Sensor Networks (WSNs) have been object of intense study in the lastfew 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 ormeasure physical quantities for a subregion of the space around it (its sensing area), andmore in particular for speci c points of interest (target points or simply targets) within thisarea. The targets located in the sensing area of a given sensor s are covered by s. Individualsensors are usually powered by batteries which make it possible to keep them functional fora limited time interval, with obvious constraints related to cost and weight factors. Using anetwork of such devices in a dynamic and coordinated fashion makes it possible to overcomethe limitations in terms of range extension and battery duration which characterize eachindividual sensor, enabling elaborate monitoring of large regions of interest. Extendingthe amount of time over which such monitoring activity can be carried out representsa 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 andii) the activation time of these subsets so that the battery constraints are satis ed. Itshould be noted that while sensors could be considered as belonging to di erent statesduring their usage in the intended application (such as receiving, transmitting, or idle) inthis context two essential states can be identi ed. That is, each sensor may currently beactive (i.e. used in the current cover, and consuming its battery) or not. Activating acover refers therefore to switching all its sensors to the active state, while switching o allthe other ones. This research thesis shows a detailed overview about the wireless sensornetworks, about their applications but mainly about typical coverage issues in this eld. Inparticular, this work focuses on the issue of maximizing the amount of time over which aset of points of interest (target points), located in a given area, can be monitored by meansof such wireless sensor networks. More in detail, in this research work we addressed themaximum lifetime problem on wireless sensor networks considering the classical problemin which all targets have to be covered (classical MLP) and a problem variant in whicha portion of them can be neglected at all times ( -MLP) in order to increase the overallnetwork lifetime. We propose an Column Generation approach embedding an e cientgenetic algorithm aimed at producing new covers. The obtained algorithm is shown to bevery e ective and e cient outperforming the previous algorithms proposed in the literaturefor the same problems. In this research work we also introduce two variants of MLP problemwith heterogeneous sensors. Indeed, wireless sensor networks can be composed of severaldi erent types of sensor devices, which are able to monitor di erent aspects of the regionof interest including temperature, light, chemical contaminants, among others. Givensuch sensor heterogeneity, di erent sensor types can be organized to work in a coordinatedfashion in many relevant application contexts. Therefore in this work, we faced the problemof maximizing the amount of time during which such a network can remain operationalwhile assuring globally a minimum coverage for all the di erent sensor types. We consideredalso some global regularity conditions in order to assure that each type of sensor providesan adequate coverage to each target. For both these problem variants we developed anotherhybrid approach, which is again based on a column generation algorithm whose subproblemis either solved heuristically by means of an appropriate genetic algorithm or optimally bymeans of ILP formulation. In our computational tests the proposed genetic algorithm isshown to be able to meaningfully speed up the global procedure, enabling the resolution oflarge-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]