Wireless sensor networks (WSNs) consist of a large number of low-cost and low-power sensor nodes. Some of the applications of sensor networks are environmental observation, monitoring disaster areas and so on. Distributed evolutionary computing is a poweful tool that can be applied to WSNs, because these networks require algorithms that are capable of learning independent of the operation of other nodes and also capable of using local information (Johnson, Teredesai & Saltarelli, 2005). Evolutionary algorithms must be designed for the resource constraints present in WSNs. This article describes how genetic algorithms can be used in WSNs design in order to satisfy energy conservation and connectivity constraints.
The recent advances in wireless communications and digital electronics led to the implementation of low power and low cost wireless sensors. A sensor node must have components for sensing, data processing and communication. These devices can be grouped to form a sensor network (Akyildiz, Sankarasubramaniam & Cayirci, 2002) (Callaway 2003). The network protocols, such as formation algorithms, routing and management, must have self-organizing capabilities. In general, sensor networks have some features that differ from traditional wireless networks in some aspects: the number of sensor nodes can be very high; sensor nodes are prone to failures; sensor nodes are densely deployed; the topology of the network can change frequently; sensor nodes are limited in computational capacities, memory and energy.
The major challenge in the design of WSNs is the fact that energy resources are significantly more limited than in wired networks and other types of wireless networks. The battery of the sensors in the network may be difficult to recharge or replace, causing severe limitations in the communication and processing time between all sensors in the network. Thus, the main parameter to optimize for is the network lifetime, or the time until a group of sensors runs out of energy. Another issue in WSN design is the connectivity of the network according to the selected communication protocol. Usually, the protocol follows the cluster-based architecture, where single hop communication occurs between sensors of a cluster and a selected cluster head sensor that collects all information obtained by the other sensors in its cluster. This architecture is shown in Figure 1. Since the purpose of the sensor network is the collection and management of measured data for some particular application, this collection must meet specific requirements depending on the type of data. These requirements are turned into application specific parameters of the network.
Figure 1. Top
Cluster-based sensor network
Genetic Algorithms For Wireless Sensor Networks
A WSN designer who takes into account all the design issues deals with more than one non-linear objective functions or design criteria which should be optimized simultaneously. Therefore, the focus of the problem is how to find many near-optimal non-dominated solutions in a practically acceptable computational time (Jourdan & de Weck, 2004) (Weise, 2006) (Ferentinos & Tsiligiridis, 2007). There are several interesting approaches to tackling such problems, but one of the most powerful heuristics, which is also appropriate to apply in the multi-objective optimization problem, is based on genetic algorithms (GA) (Ferentinos & Tsiligiridis, 2007).
Key Terms in this Chapter
Wireless Sensor Networks: A network of spatially distributed devices using sensors to monitor conditions at different locations, such as temperature, sound, pressure, etc.
Network Lifetime: Time until the first sensor node or group of sensor nodes in the network runs out of energy.
Cluster-Based Architecture: Sensor networks architecture where communication occurs between sensors of a cluster and a selected cluster head that collects the information obtained by the sensors in its cluster.
Fitness Function: A particular type of objective function that quantifies the optimality of a solution in a genetic algorithm.
Sensor Node: Network node with components for sensing, data processing and communication.
Energy Parameters: Parameters that affect the battery consumption of the sensors, including the energy consumed due to sensing, communication and computational tasks.
Mutation: The occasional (low probability) alteration of a bit position.
Crossover: Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next.
Genetic Algorithms: Search technique used in computing to find true or approximate solutions to optimization and search problems.
Cluster Head: Sensor node responsible for gathering data of a sensor cluster and transmitting them to the sink node.