Recent interest in integrated electronic devices (sensors) that operate wirelessly creates a wide range of applications related to national security, surveillance, military, healthcare, and environmental monitoring. Many visions of the future include people immersed in an environment surrounded by sensors and intelligent devices, which use smart infrastructures to improve the quality of life. However, a fundamental feature of sensor networks is coverage: how these tiny devices can cover a certain terrain. These devices should be organized in an optimal manner, consuming the minimum energy and covering the whole area of interest. The coverage concept is subject to a wide range of interpretations due to the variety of sensors and applications. Different coverage formulations have been proposed based on the subject to be covered (area in relation to specific items and obstacles), sensor development mechanisms (random versus deterministic), and other properties of wireless sensor networks (e.g. network connectivity and minimum energy consumption). In this chapter, the authors study the coverage problem in wireless sensor networks using the most recent algorithms. The aim of this chapter is to present these algorithms and a comparison between them based on various criteria. The Node Self-Scheduling algorithm, the Centralized Voronoi Tessellation (CVT), the Particle Swarm Optimization Algorithm (PSO), the Virtual Forces Algorithm (VFA), etc. are analyzed. Through the algorithms’ analysis, the interested reader can have a complete view of the proposed solutions related to the coverage problem.
TopIntroduction
A Wireless Sensor Network (WSN) is a network of portable devices (sensors) that can monitor, compute, and store information depending on their environment. Sensor nodes, also called wireless transceivers, are tiny devices equipped with one or more sensors, one or more transceivers, processors, storage resources and, possibly, actuators, like depicted by Figure 1. Sensors have specific and, usually, small size, weight and cost. Their limited lifetime sets out restrictions on actions that they can perform (e.g. processing and communication). Due to the fact that battery replacement is not feasible in many cases; low power consumption is a critical factor, which affects the entire life of the WSN. Each of these nodes should be able to collect and send data back to a base station via a multi-hop wireless network.
Figure 1. The typical architecture of a sensor node
A WSN is composed of a large number of nodes with sensing capabilities, in which each node can communicate with each other. After the development of the network, sensor nodes begin a process of creating groups (clusters), installing of communication channels, creating hierarchy between them etc. Sensor nodes can be organized in smaller networks and collaborate to accomplish a larger sensing task. The network is expected to operate for long periods without human intervention or supervision. It should be characterized by speediness, agility and adaptability in the environment. These features are useful in emergency situations such as natural disasters and military wars. It is important to be supported by the topology and distribution of the nodes, which should occupy the entire area of interest (ROI). The major components of a typical sensor network shown in Figure 2 are: the sensor nodes, the sensor field, the sink and the task manager or base station. The sensor field can be considered as a field in which the nodes are placed, i.e. the area where we expect a particular phenomenon to occur. The sensor nodes are the heart of the network. They are responsible for data collection and routing this information back to the sink.
Figure 2. Sensor nodes in a sensor field
The sink node is a sensor with the specific aim of taking, processing and storing data from other sensor nodes. The sink is used to reduce the total number of messages to be sent between nodes, thus resulting in low energy needs of the network. Such points are usually defined dynamically by the network. Regular nodes can also be considered as sink if they have gathered enough information. For this reason, the sink is also known as data collection point. The task manager or base station is a central control point in the network, which sends the required information back to the control network. It also provides a gateway to other networks, a powerful data processor, a data storage center and an access point for users. The base station is either a laptop or a terminal. The data is routed from sink to these terminals via the Internet, wireless channels, satellites etc. So, in some cases, hundreds of thousands of nodes extending across the ROI to create a multi-hop wireless network. The nodes can be placed very densely together as 20 nodes per m3. The sensor nodes use the wireless media such as infrared, radio, optical devices or Bluetooth for communications. The transmission range of nodes varies depending on the communication protocol used.
Section 2 contains a reference to the study the problem related with the sensors’ spatial partition, which is called coverage problem. The sensor’s coverage, the sensor’s energy consumption and the most usual characteristics included in the assumption of the proposed algorithms are defined. Section 3 analyzes the most recent algorithms that have been elaborated in the literature, while Section 4 contains a comparative evaluation of basic algorithms with their extensions. In chapter 5, there are proposals for future work and, finally, section 6 presents the conclusions.