Exploring Coverage within Wireless Sensor Networks through Evolutionary Computations

Introduction

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.