The evolutionary search approach has demonstrated its effectiveness in many real world applications, such as the coverage problem in wireless sensor networks. It is to place sensor devices in a service area so that the entire service area is covered. We have modeled the coverage problem as two sub-problems: floorplan and placement. The floorplan problem is to partition the service area into well-defined geometric cells, where the placement problem is to assign the sensor devices into a set of cells. Even though the search space has been transformed from continuous into discrete, the complexity of the coverage problem is computationally intensive. The objective function is to maximize the coverage of the service area while not exceeding a given budget. The merged optimization problem has been coded into the genetic algorithm (GA) and the experimental results reveal the versatility of GA to adapt and find a good solution in a short time.
The wireless sensor network (WSN) has emerged as a promising platform to monitor an area with minimal human interventions. Advancements in low-power micro-electronic circuits, wireless communications, and operating systems have made WSN into feasible platforms that are used in many applications. Initially, WSN applications were dominated and funded by military applications, such as monitoring the activity in a battlefield. Now, many civilian applications, such as environmental and habitat monitoring, have emerged to benefit from the usage of WSN.
The initial deployment of WSN involves two fundamental problems, which are known as the coverage and communication problems. The coverage problem has a number of interpretations depending on the type of sensors and applications. However, many researchers have considered the coverage as the measure of quality of service of a sensor network (Dasgupta, Kukreja, & Kalpakis, 2003). For example, in battlefield monitoring, one may ask how well WSN can observe the activity of a tank’s movements in the battlefield (service area), and what are the likelihoods that a tank’s movements in a specific location will be detected in a given time frame. The communication problem is to determine a small set of sensors, which are also known as base stations, to collect data from all sensors.
Here the authors‘ main focus is on the coverage problem; moreover, an analogous of placing and integrating modules of integrated circuit (IC) into a circuit board as placing sensor devices in a service area is the technique used. Since both problems are known to be NP-complete and there is no known polynomial time algorithm to solve either problem; to simplify the placement and integration modules of integrated circuits (IC) into a circuit board, we have divided the problem into two sub-problems: floorplan and placement. The floorplan problem is to divide the circuit board into well-defined geometric cells, and then it determines the best cells to place the IC modules into them with minimal total wire connections. Such an approach has been adapted for more than 25 years in many computer-aided design (CAD) tools for the placement and integration of IC modules. Its success comes from converting the continuous design space into a discrete design space that can be searched with heuristic algorithms in finding good solutions.
In order to apply a genetic algorithm (GA) to search for the maximal coverage with minimal sensors the authors have customized GA to work well with the problem. The overall framework of GA is well understood; however, an improper implementation can easily nullify its advantages. The primary difficulty comes from the representation of WSN, which involves information regarding the service area and placed sensors. If a linear binary string (chromosome) were selected, then the string’s length would be very long. This would occupy a lot of space during the execution of GA, and also this might lead to compromise between the population size and its diversity. If the population size were limited to a small number, then the small and less diverse population would affect the outcome of the optimization process negatively. Using a binary representation forces the GA program to include both encoding and decoding operations to perform the translation not only during the initial coverage step, but at all steps of the coverage validation. This would utilize the processor time inefficiently instead of executing more of the optimization procedure. Therefore, a hybrid object-oriented link list is selected rather than the classical linear string to encode explicitly all problem’s inputs, floorplan decisions, and sensors placement decisions. A hybrid link list consists of a primary link list and sets of secondary link lists. A node (chromosome) in the primary link list represents a candidate solution in the population. Also, every node in the primary list contains a secondary link list (genes) that represents all placed sensors within a chromosome. From experiments, it is observed the effectiveness of WAN chromosome during the crossover and mutation operations by eliminating the repair operation.
Key Terms in this Chapter
Floorplan: Planning the location of each sensor to be placed.
Evolutionary Approach: A suite of search techniques that are based on the evolution and improved over time.
Coverage Problem: How well sensors monitor each location in the physical space of interest within the sensing range of at least one sensor.
Sensor: An electronic device that detects the value or the change of value of a physical quantity or parameter and converts the observed value into a signal for an indicating or recording instrument.
Genetic Algorithm: A search technique used in computing to find exact or approximate solutions to optimization and search problems.
Optimization: The problem of finding the best solution from all feasible solutions.
Wireless Sensor Network: A wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions at different locations.
Discrete Space: A topological space or similar structure, one in which the points are isolated from each other in a certain sense.