Overview of wireless sensors networks
As previously mentioned, WSN are composed by a large numbers of sensors deployed to monitor an interesting phenomenon. Sensors are typically small electronic devices composed by the combination of sensor circuits used to collect information from the environment that might be application-dependent. A sensor node integrates sensing, processing, and communication sub-systems. The sensing subsystem links the sensor to the world and signals that it has to monitor. The processing subsystem provides the sensor with the capabilities to perform medium to high complexity computations and to make low complexity decisions. The communication module consists typically in a radio unit that allows the sensor to communicate with other nodes around it by using short range radio signals. Finally, all of these parts are coupled with a power subsystem in charge of providing the energy required for the sensor nodes to perform its operations.
Sensors are either Passive or Active . Passive sensors are those used to monitor signals as humidity, temperature, vibrations, etc. by using passive measurement sensing units. Active sensors include elements as radars or sonars that might require as much energy as the communication technologies in order to detect the interesting signal from the environment. As expected, this characteristic complicates the network design, as the WSN might require to answer to diﬀerent energy draining conditions that may heavily aﬀect its performance. Current technology combines diﬀerent characteristics into a single device that may be used to accomplish diﬀerent and/or simultaneous tasks before exhausting all of its energy.
Types of networks
The application for which a WSN is developed may certainly aﬀect the challenges and constraints faced when planning its operation. Depending on the environment in which sensors will operate, the characteristics of the sensors, their technical specifications, and the strategies adopted to use eﬃciently their resources may require to be adapted.
WSN may operate unattended in certain applications, e.g., when it is deployed in re-mote of hostile environments. These unstructured networks may be randomly deployed from a remote location where neither the location of the sensors nor the topology of the network are known in advance, before sensors deployment. As a consequence, eﬃcient algorithms, protocols and strategies need to be designed to answer to these uncertain conditions in order to use the resources eﬃciently. By contrast, in structured networks the location of the sensors can be pre-planned in such a way that the operational con-straints of the network and the waste of sensors resources can be avoided a priori, before sensors actual deployment. In other words, the WSN is designed to operate eﬃciently rather than to respond to random conditions.
Yick et al.  classifiy the WSN into five types: terrestrial, underground, under-water, multi-media, and mobile WSN. However, the limits between this categories might be unclear and diﬀuse considering that current sensor technology may embed a lot of diﬀerent technologies and capabilities into a single node. An overview of the specifica-tions of these categories regarding the structure of the network and energy consumption is outlined in Table 2.1.
One of the most important questions in WSN design is the coverage . Sensors are deployed to retrieve periodically information either from the environment or from some targets to keep record of the values of some interesting variables. As expected, the coverage strongly depends of the characteristics and technology embedded in the sensors. Sensor nodes may have diﬀerent types of sensing devices that are selected based on the requirements of the application . Furthermore, each application may specify diﬀerent conditions that impose the terms in which coverage is provided.
The coverage that sensors provide strongly depends on the technologies they have embedded and the application for which they are used. Consider for example a video network used for surveillance, in this case the monitored area for each sensor might correspond only to a region that lies within a certain angle and distance. By contrast, a sound sensor may be able to monitor the phenomena occurring within a spheric 3D region around it defined by the maximum sensing distance.
Maybe the simplest coverage model that can be considered is the binary disc model in 2D regions . According to it, each sensor is capable of sensing only from points located within the circular disk around it and located within a defined sensing range Rs. This is probably the most studied model regarding to the coverage in WSN and is the basis for a lot of theoretical advances in WSN theory. As the name indicates, every point in the binary disc model only have two states, covered or uncovered according to its distance to the nearest active sensor. Nonetheless, this model can be extended to consider probabilistic coverage in which the probability of coverage may decrease as the distance to the active sensors increase . Figure 2.1 depicts the coverage and communication disk model in a WSN. The external and internal discs represent respectively the communication Rc and sensing Rs ranges for sensor s1. Sensor s1 is able to establish communication with sensor s2 and is able to survey the point κ1. The sensor s3 is disconnected as it is located out of the communication range. In the same way, the points out of the disk are not covered, e.g., the point κ2. Similar considerations may apply for a binary disc connectivity model.
Sensors may be deployed to monitor a continuous area around it, that is probably a representative sample of the space around it, as in the case of temperature or humidity sensors. In this case it is possible to say that sensors are deployed for area coverage (see Figure 6.1a), and the interesting area can be seen as a collection of areas, derived from the region covered by each sensor, to be covered. Point or target coverage consists in the monitoring of certain points located at discrete positions in the space that may correspond to positions on a grid or randomly distributed in the interesting space (Figure 6.1b) [25, 26, 73, 105]. In Barrier coverage the idea is to guarantee that any intrusion to an interesting area is detected, which indicates that emphasis must be addressed to cover any point in the frontier of that region . Finally, in WSN deployed for tracking applications, sensors are at charge of tracing the position of a given target at every moment. Target tracking is a typical and challenging application that in addition to identify the set of sensors able to monitor the intrusion, may require the prediction of the movements in order to optimize the use of the energy.
In addition to the previous categories, the applications may impose additional con-straints in order to guarantee that the collected information is reliable and/or the quality of the coverage is appropriated. In Q-coverage, for example, it is mandatory to cover every target (area) up to Q times, i.e., with at least Q active sensors [2, 118]. Diﬀerent reasons may imply that the coverage is not geometric, for example the covered area might not be a perfect disk around the sensor, but a region with a diﬀerent shape (see Figure 6.1c). In the case of directional sensor networks, the region covered by the sen-sors may be a conic region or a semicircle in the 2D space (see Figure 6.1d). All of these considerations may aﬀect the performance of the sensors and the operations planning in WSN; however, in practice, the modeling can be simplified if it is possible to assume that every sensor is aware of the regions (targets) that it covers. A complete review of coverage problems in WSN is presented by Li and Liu .
Relations between area coverage and discrete target coverage are well known . For example, area coverage may be represented by using discrete points representing either the regions covered by the same set of sensors or the intersection between the frontiers limiting the covered area. This kind of relationships can be exploited when area coverage problems are considered in such a way that approaches used for discrete coverage can also be used to approximate the coverage of continuous areas.
Energy consumption in wireless sensors
Energy consumption in WSN strongly depends on the characteristics of the sensor node . Indeed, recent research demonstrates that there exist huge diﬀerences in the energy consumed by diﬀerent commercial nodes . It has been claimed that certain remarks remain present almost in every current sensor node, however, no agreement on this subject has been reached yet. In general, it is assumed that the communication subsystems account for the largest portion of the energy consumed by sensor nodes [10, 53]. However, in certain applications the sensing, the signal processing and the hardware operation consume an important amount of power as well .
The function of the sensor nodes in a WSN consists in detecting the interesting phenomena, process the collected information, and (re)transmit the collected data. Thus, consumption of energy at the sensors is consistently related with these activities . Power consumption in WSN mainly comes from three factors: communication, sensing and computing.
• Communication: It consists on the energy consumed by the transmission and reception modules embedded in the sensor. In general, sensors employ low energy consumption devices; nonetheless, it generally accounts for the bigger portion of the energy consumed. Moreover, the intensity of the use can be an important source of consumption and networks with higher sampling rates necessarily drain the energy faster than networks that sample occasionally.
• Sensing: Diﬀerent applications may imply a lot of diﬀerences in the energy con-sumption rates associated with the sensing activities. Sensors may be used to monitor easy variables as the temperature, which only require the use of a pas-sive device with a low energy consumption rate. However, some applications (for example the ultrasonic sensors) may require the sensors to generate signals and capture the answer, which can lead to a higher energy consumption.
• Computing and information processing: This is the energy consumed by the sensors to perform data processing and decision making tasks. Current technolo-gies allows sensors to perform even complex computation tasks; nonetheless, it means that energy expenses may increase. Each sensor receiving data either raw from the environment or processed originated in other sensors might be required to encode and create packets with the information at expenses of higher energy consumption rates.
In multi-hop WSN, the communication task certainly implies harvesting, processing and re-transmit the information collected by other sensors, consequently the power consumption could increase depending on the traﬃc of the network.
The energy consumption rate associated to a sensor node is also related with the activity that it performs within the network. The rate at which power is drained from the sensors might not be constant; consumption rates may depend on the diﬀerent roles assumed by the sensors, and that can be used to save energy. Some operating modes (roles) that they can adopt can be classified into the four following categories :
• On-duty: All the components of the sensors are operative in order to collect information about the interesting variables, process the information, perform any type of computation and (re)transmit the information to other sensors or the final user.
• Used for transmission: In this case the sensor is only used to re-transmit the information collected by other sensors. It is not retrieving any information from the environment but still have to perform any type of computation to transmit the information it receives. The sensor is only used to help keeping connectivity within the diﬀerent parts of the and provide a path to send the information to the final user.
• Used for coverage: Sensors can turn oﬀ the communications technologies in order to save energy and avoid redundant information interfering in the networks. Sensors can activate their communication modules as a response to a phenomenon detected or may store the information in a storage unit, if sensors are provided with it, to transmit it just in the right moment when it is required.
• Oﬀ-Duty: The sensor is in an idle state in which it is neither used for commu-nication nor for sensing purposes and it consumes energy at a negligible energy consumption rate (typically some self-discharge is observed). The sensor may have some mechanism that will reactivate the sensor once it is required.
As expected, each of the modes above consumes power at diﬀerent rates depend-ing on the sensor modules involved in the operations. Moreover, additional variables may influence the power consumption of the sensors. The power consumed might in-crease as a consequence of the traﬃc that passes through a sensor node due to the amount of transmissions established and the processing, packing and retransmission of the information. Similarly, the energy consumed by transmission may depends on the distance to the receptor node (sensor of base station). A classical example of sensors draining energy at diﬀerent rates is observed in sensors that can adjust their sensing or communication ranges.
Lifetime and coverage optimization on WSN
Several studies has been devoted to represent all of the aspects of the energy consump-tion, the network operations, and the lifetime of WSN. Diﬀerent characteristics and specifications of the network operation have been provided, some of them designed with the specific purpose of network optimization in one of the large number of aspects in-volved in WSN design. WSN are resource constrained devices that impose big challenges to overcome the operational constraints and successfully deploy these devices without neither aﬀecting their reliability nor waste their energy. The use of energy and the knowledge of its consumption is a major concern to be considered when dealing with WSN design.
Lifetime is probably one of the most studied metrics in WSN; however, its definition might be flexible and application specific . A lot of definitions have been proposed according to diﬀerent specifications and requirements for the network operations. It was classically defined as the time until which the first node fails . Nonetheless, this definition does not take into account that WSN can be still fully operative and able to survey the required phenomenon after some sensors fails, e.g., densely deployed WSN for temperature monitoring. Consequently, several definitions based on the availability of nodes, the sensor coverage, and the connectivity have been also explored. For a complete review of definitions of network lifetime in WSN, the reader may be referred to the manuscript of Dietrich et al. .
In the context of this work, network lifetime is defined in terms of sensor coverage and network connectivity. It is is defined as the time interval during which sensor network can perform the sensing functions and is able to transmit the collected information to the sink used to compute or retransmit the information . In other words, the lifetime of a sensor network is the total time that the WSN have sensors with the necessary energy to provide the required level of coverage of the interesting phenomena and transmit the information to the sink. This definition does not make any assumption about the characteristics of the coverage that has to be delivered. Consequently, it is possible to extend this definition to diﬀerent scenarios, e.g., when sensors are required to provide multiple target coverage, sensors are heterogeneous, or when sensors are used to survey a 3D region.
WSN technology is still on a development phase and requires to be optimized for a successful adoption. Some works are devoted to improve the performance of WSN not only in the technical aspects, the technology embedded, their sensing capabilities, and their power sources, but also to take the maximum advantage of the possibilities they oﬀer and the limited resources they have. Several metrics have been defined to evaluate the lifetime and the eﬃciency of the energy usage in WSN . Lifetime and coverage are typically related objectives that are commonly used to define network operation in WSN. Whereas it is interesting to provide reliable and timely coverage, it might be also important to guarantee the operation of the network as long as possible. As could be expected, network lifetime strongly depends on the battery lifetime of each individual node. Coverage depends on the availability of sensors; moreover, reliable coverage might require the use of extra sensors that can reduce network lifetime.
According to the capabilities of the sensors, the purpose of the network, or the inner structure of the device, it is possible to create a wide classification of WSN and its en-ergy usage. Anastasi et al.  present a comprehensive review of energy conservation schemes on WSN. The authors consider approaches for energy conservation based on power management on sensor nodes as well as approaches based on data acquisition and energy-eﬃcient protocols. From the viewpoint of coverage and connectivity, the applications of WSN can be classified as: (i) Area coverage, (ii) Target coverage, and (iii)Target tracking. Zorbas et al.  present a survey considering the main charac-teristics studied by researchers regarding the energy eﬃciency of WSN used for target coverage. If a continuous region requires to be monitored, it has been demonstrated that area coverage can be accurately represented by discrete points corresponding to the intersections of the circles delimiting the covered area for each sensor .
Table of contents :
Table of contents
1.2 Contributions of this thesis
1.4 How to read this document
2 Energy efficient coverage in wireless sensor networks
2.2 Overview of wireless sensors networks
2.2.1 Types of networks
2.2.2 Sensing Models
2.2.4 Energy consumption in wireless sensors
2.3 Lifetime and coverage optimization on WSN
2.3.1 Related works
2.3.2 Duty scheduling on densely deployed WSN
2.3.3 Battery life and network lifetime
2.4 Column generation based approaches for wireless sensor networks optimization
2.4.1 General model and basic ideas
2.4.2 Related problems and directions of research
220.127.116.11 Maximum network lifetime
18.104.22.168 Partial coverage and lifetime
22.214.171.124 Strategies to solve the pricing subproblem
3 A numerical evaluation of acceleration strategies for column generation applied to wireless sensor networks optimization
3.2 Problem description and related work
3.2.1 Mathematical approach
126.96.36.199 Master problem
188.8.131.52 Pricing subproblem
184.108.40.206 Convergence of the Column Generation algorithm .
3.3 Acceleration strategies for the column generation algorithm
3.3.1 Dual variables stabilization
220.127.116.11 BoxStep stabilization method
18.104.22.168 Generalized BoxStep method
22.214.171.124 Neame’s stabilization method
126.96.36.199 Dual variable values initialization
188.8.131.52 Computational experiments
3.3.2 Intensification strategies
184.108.40.206 Intensification and diversification through a Genetic Algorithm
220.127.116.11 Computational experiments
3.3.3 Hybridizing stabilization and intensification strategies in column generation
18.104.22.168 Computational experiments
3.4 Conclusions and future work
4 A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints
4.2 The maximum network lifetime problem under coverage and connectivity constraints
4.2.1 Decomposition approach
22.214.171.124 Pricing subproblem
4.3 Solving the pricing subproblem
4.3.1 A GRASP approach to solve the pricing subproblem
126.96.36.199 Greedy randomized construction
188.8.131.52 Solution improvement
4.3.2 A VNS approach to solve the pricing subproblem
184.108.40.206 Initial Solution
220.127.116.11 Local search
4.4 Computational Experiments
4.5 Conclusions and future work
5 Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks
5.2 Problem description
5.3 Solution approach
5.3.1 Pricing subproblem
5.4 Solution approaches to address pricing subproblem
5.4.1 A decomposition approach to address pricing subproblem
5.4.2 A constraint programming approach to address the pricing subproblem
5.5 Computational experiments
6 Partial coverage to extend the lifetime in wireless multi-role sensor networks
6.2 Problem description and model
6.3 Solution approach
6.3.1 A constraint programming model for PS
18.104.22.168 Constraint programming definitions
22.214.171.124 Constraint model
126.96.36.199 Search strategy
6.3.2 An evolutionary algorithm to boost up CG
6.3.3 Hybrid CG+EA+CP approach to maximize network lifetime
6.4 Computational experiments
6.5 Conclusions and future work
7 General conclusions and future works
7.1 General remarks
7.1.1 Thesis summary
7.1.2 Methodology and findings summary
7.2 Limitations of this study
7.3 Perspectives of research