Project topics and materials
Get Complete Project Material File(s) Now! »
Overview of wireless sensors networks
As previously mentioned, WSN are composed by a large number 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 their operations.
Sensors are either passive or active [Sohraby et al., 2007]. 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 different energy draining conditions that may heavily affect its performance. Current technology combines differ-ent characteristics into a single device that may be used to accomplish different and/or simultaneous tasks before exhausting all of its energy.
Types of networks
The application for which WSN are developed may certainly affect the challenges and constraints faced when planning their operation. Depending on the environment in which sensors will operate, the characteristics of the sensors, their technical specifica-tions, and the strategies adopted to use efficiently 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, efficient algorithms, protocols and strategies need to be designed to answer to these uncertain conditions in order to use the resources efficiently. 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 are designed to operate efficiently rather than to respond to random conditions.
Yick et al. [Yick et al., 2008] classify the WSN into five types: terrestrial, under-ground, underwater, multimedia, and mobile WSN. However, the limits between these categories might be unclear and diffuse considering that current sensor technology may embed a lot of different technologies and capabilities into a single node. An overview of the specifications of these categories regarding the structure of the network and energy consumption is outlined in Table 2.1.
Energy consumption in wireless sensors
Energy consumption in WSN strongly depends on the characteristics of the sensor node [Anastasi et al., 2009]. Indeed, recent research demonstrates that there exist huge differences in the energy consumed by different commercial nodes [Raghunathan et al., 2002]. 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 [Anastasi et al., 2009, Farahani, 2008]. However, in certain applications the sensing, the signal processing and the hardware operation consume an important amount of power as well [Puccinelli and Haenggi, 2005].
The function of the sensor nodes in the WSN consists in detecting the interest-ing phenomena, processing the collected information, and (re)transmiting the collected data. Thus, consumption of energy at the sensors is consistently related with these activities [Sohraby et al., 2007]. 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: Different applications may imply a lot of differences 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 tech-nologies allow 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-transmiting the information collected by other sensors, consequently the power consumption could increase depending on the traffic 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 different 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 [Zhu et al., 2012].
• 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 has to perform any type of computation to transmit the information it receives. The sensor is only used to help keeping connectivity within the different parts of the network and providing a path to send the information to the final user.
• Used for coverage: Sensors can turn off 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 memory unit, if sensors are provided with it, to transmit it just in the right moment when it is required.
• Off-Duty: The sensor is in an idle state in which it is neither used for com-munication nor for sensing purposes and it consumes energy at a negligible 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 different 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 traffic 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 depend on the distance to the receptor node (sensor of base station). A classical example of sensors draining energy at different rates is observed in sensors that can adjust their sensing or communication ranges.
Lifetime and coverage optimization on WSN
Several studies have been devoted to represent all of the aspects of the energy con-sumption, the network operations, and the lifetime in WSN. Different 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 involved in WSN design. WSN are resource constrained devices that impose big chal-lenges to overcome the operational constraints and successfully deploy these devices without neither affecting their reliability nor wasting 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 [Sha and Shi, 2005]. A lot of definitions have been proposed according to different specifications and requirements for the network operations. It was classically defined as the time until which the first node fails [Shi, 2007]. 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 fail, 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. [Dietrich and Dressler, 2009].
In the context of this work, network lifetime is defined in terms of sensor coverage and network connectivity. It 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 [Cardei and Wu, 2004]. 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 phe-nomena 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. Conse-quently, it is possible to extend this definition to different scenarios, e.g., when sensors are required to overcover targets by using several sensors, sensors are heterogeneous, or when sensors are used to survey a 3D region.
Table of contents :
Table of contents
1 Introduction
1.1 Motivation
1.2 Contributions of this thesis
1.3 Outline
1.4 How to read this document
2 Energy efficient coverage in wireless sensor networks (WSN)
2.1 Introduction
2.2 Overview of wireless sensors networks
2.2.1 Types of networks
2.2.2 Sensing models
2.2.3 Connectivity
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
2.4.2.1 Maximum network lifetime
2.4.2.2 Partial coverage and lifetime
2.4.2.3 Strategies to solve the pricing subproblem
3 A numerical evaluation of acceleration strategies for column generation applied to wireless sensor networks optimization
3.1 Introduction
3.2 Problem description and related work
3.2.1 Mathematical approach
3.2.1.1 Master problem
3.2.1.2 Pricing subproblem
3.2.1.3 Convergence of the Column Generation algorithm
3.3 Acceleration strategies for the column generation algorithm
3.3.1 Dual variables stabilization
3.3.1.1 BoxStep stabilization method
3.3.1.2 Generalized BoxStep method
3.3.1.3 Neame’s stabilization method
3.3.1.4 Dual variable values initialization
3.3.1.5 Computational experiments
3.3.2 Intensification strategies
3.3.2.1 κ-Intensification
3.3.2.2 Diversification
3.3.2.3 Intensification and diversification through a Genetic Algorithm
3.3.2.4 Computational experiments
3.3.3 Hybridizing stabilization and intensification strategies in column generation
3.3.3.1 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.1 Introduction
4.2 The maximum network lifetime problem under coverage and connectivity constraints
4.2.1 Decomposition approach
4.2.1.1 Pricing subproblem
4.3 Solving the pricing subproblem
4.3.1 A GRASP approach to solve the pricing subproblem
4.3.1.1 Greedy randomized construction
4.3.1.2 Solution improvement
4.3.2 A VNS approach to solve the pricing subproblem
4.3.2.1 Initial solution
4.3.2.2 Local search
4.3.2.3 Neighborhoods
4.3.2.4 Shake
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.1 Introduction
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
5.6 Conclusions
6 Partial coverage to extend the lifetime in wireless multi-role sensor networks
6.1 Introduction
6.2 Problem description and model
6.3 Solution approach
6.3.1 A constraint programming model for the pricing subproblem .
6.3.1.1 Constraint programming definitions
6.3.1.2 Constraint model
6.3.1.3 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
References
