key: cord-0045676-r59a5nk4
authors: Tossa, Frantz; Abdou, Wahabou; Ezin, Eugène C.; Gouton, Pierre
title: Improving Coverage Area in Sensor Deployment Using Genetic Algorithm
date: 2020-05-25
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50426-7_30
sha: 5a2e92b00c7ba9d245b88f567802f3b84d881af0
doc_id: 45676
cord_uid: r59a5nk4

Wireless sensor networks (WSN) are a collection of autonomous nodes with a limited battery life. They are used in various fields such as health, industry, home automation. Due to their limited resources and constraints, WSNs face several problems. One of these problems is the optimal coverage of a observed area. Indeed, whatever the domain, ensuring optimal network coverage remains a very important issue in WSNs, especially when the number of sensors is limited. In this paper, we aim to cover a two-dimensional Euclidean area with a given number of sensors by using genetic algorithm in order to find the best placement to ensure a good network coverage. The maximum coverage problem addressed in this paper is based on the calculation of the total area covered by deployed sensor nodes. We first, define the problem of maximum coverage. For a given number of sensors, the proposed algorithm find the best position to maximize the sensor area coverage. Finally, the results show that the proposed method well maximize the sensor area coverage.

The rapid growth of wireless technologies and the decrease in their cost has made it possible to generalize the use of Wireless Sensor Networks (WSN). Originally used in the military field, this type of network is now present in several fields, ranging from industrial monitoring to the measurement of environmental data, home automation, fire detection, medical sector [9, 11] . WSN applications have therefore critical roles in daily life. Most of these applications have the task of monitoring a target point or area, recording a reaction and transmitting it. Broadly, a WSN is a collection of sensors which communicate thanks to some wireless technologies. WSNs consist of small nodes that differ from traditional networks within their communication and sensing ranges. Sensor nodes, sense the physical phenomena located in the area and transmit the data collaboratively to sink node. A sensor node can be either sensing, transmitting node, relay node or both of them together. Therefore, to perform their tasks, wireless sensor networks must be effective.

Deployment is one of the important aspects that have a direct impact on the WSN effectiveness. The deployment mechanisms of WSN can be classified into two main categories: deterministic and non-deterministic [1, 11] . The deployment of a WSN affects almost all of its mains performance metrics, such as coverage, connectivity, and network lifetime. Among these metrics, we focus on coverage. Indeed for an effective design and employment of sensor networks in various application scenarios, the coverage relies on numerous parameters. It reflects the quality of monitoring a point or area by a sensor. In [10] , coverage is defined as how well or to how much extent each point of a deployed network is under the vigilance of a sensor node. The coverage can be classified into three categories [1, 2] : -Barrier coverage: The objective is to achieve an arrangement of sensors with the task of maximizing the detection probability of a specific target penetration through the barrier. -Point coverage: The objective is to cover a set of point (target) with known position that need to be monitored. This coverage scheme focuses on determining sensor nodes exact positions while guarantee efficient coverage application for a limited number of immobile targets. -Area coverage: The main objective is to cover (monitor) a region and to maximize the detection rate of a specific area. In this paper, we focus on this type of coverage.

Most of the previous studies on this problem have focused on how to reduce the number of sensors to cover the area. In our case, we examine the problem of the maximum coverage of the area with a given number of sensors of the same type. In real-life situations, due to cost considerations, the number of sensors is often limited, but the requirement to cover an area as wide as possible is necessary. As indicated in [12] , depending on the objectives, the coverage problem can be formulated in different ways. In this study, we aim to cover a two-dimensional detection area by using a limited number of sensors to have the best network coverage. Instead of using methods such as circle packing algorithms [5, 8] , we use a Genetic Algorithm (GA). In addition, due to the random deployment of the sensors, causing a probable overlap, we propose a new way as the evaluation function of the GA to know the exact surface covered by sensors. To the best of our knowledge, this method is not been used in the literature.

The rest of the paper is organized as follows: in Sect. 2 we briefly present the related work on sensor deployment and maximum coverage. In Sect. 3, the problem definition is provided, a mathematical modeling is proposed. In Sect. 4 the proposed approach is detailed and in Sect. 5, we present and discuss numerical results. Section 6 concludes this paper and gives an overview of some future works.

Optimal sensor placement for good and accurate measurement is essential for data transmission in sensor networks. That's why getting the best network coverage is important. This problem is known as maximum coverage sensor deployment problem (MCSDP) and is known to be NP-hard. Several works have been carried out in various situations to solve sensor placement for best area monitoring and they have presented their solutions with various algorithms.

Ozan Zorlu and Ozgur Koray Sahingoz proposed a genetic algorithm to increase the coverage of an homogeneous wireless sensor networks [14] . The problem of maximum coverage that the authors address in this paper is based on the calculation of the total area covered by the sensors. In the paper, the covered area is tried to calculated by geometric formulas. They first describe the problem, then they formulate it for their genetic algorithm. In their proposal, they seek to deploy a minimum number of sensor nodes which should not overlap and not go beyond the observed area for maximum coverage. Their objective is to maximize the area coverage while minimizing the intersection between sensor nodes. Based on this formulation of the problem, they calculate the area covered by the deployed sensors. They reach the maximum coverage by varying the parameters of the genetic algorithm and finally show the algorithm perform well and is stable.

Based on previous work that applies genetic algorithms to sensor deployment problems, Yourim Yoon and Yong-Hyuk Kim analyze the problem, its representation and its properties and propose a methodology which they consider new and more adapted to the properties of genetic algorithms [12] . An effective evaluation method and a new standardization technique are also proposed. The authors in this paper, adopt the Boolean disk coverage model and deal with the zone coverage problem, which also addresses all points of the sensor field. In this paper, as a new approach, they focus on the problem of maximizing the area covered by the sensor field with a given number of sensors. For the notation of the problem, they use the multidimensional multiple-choice knapsack problem. In contrast to [14] , they base their study on n static sensors of k types and each type of sensor can cover a given area with an arbitrary fixed radius r 1 , r 2 , ..., r k . They assume there is at least one sensor for each type of sensors. Their objective is to find locations (x 1 , y 1 ), (x 2 , y 2 ), ....., (x n , y n ) for all n sensors that produce the maximum coverage for a given domain. So they proposed a novel normalization method for the problem that could improve the performance of genetic algorithms they use. This method tailored to the MCSDP to associate the search by GAs with the original solution space. After presenting some GAs, (RANDOM, PGA and MGA) that are without normalization, they propose the OPTGA which, like MGA, uses the Monte Carlo method with an increasing number of random samples to evaluate solutions, and rearranges the genes of the second parent to minimize the distance sum before applying recombination. They then make a comparison between their proposal and these algorithms and show that their proposal is more stable and faster.

With a different approach, Sami Mnasri and al have worked on target coverage and presented a mathematical model to provide a deployment scheme while optimizing the target coverage of the location in an audio sensors networks [6] . They aim to optimize the placement of nodes with the most possible uniform distribution of nodes (anchors and mobile nodes) around the target to locate. To model the problem of target coverage considering the localization, they define the objective function in two sub-functions (coverage and location), which they then add. The sub-function objective for coverage is the ability of a mobile node to compute coverage based on the targets covered, while that of the location computes the ability for each target to be monitored by at least n nodes (mobile or anchor). In doing so, they aim to optimize target coverage and location. They publish thirteen constraints which constitute the rules of management of the network and evaluate the performance of the proposed genetic algorithm in terms of coverage rate, degree of coverage (k-coverage), number of iterations, and the front Pareto.

Nguyen ThiHanh and in [4] based their work on the same problem formulation as [12] . They proposed a genetic algorithm called MIGA, based on IGA, to solve the problem of maximizing area coverage in a WSN with heterogeneous sensing ranges. Their modified IGA algorithm, approaches the problem with a new individual representation, a different heuristic initialization, a combination of Laplace Crossover (LX) and Arithmetic Crossover Method (AMXO) operators, and a local search (VFA). K different types of sensors were used in the set of sensor nodes, in which one type of sensor i has a detection range r i . The goal of their work is to find an optimal placement scheme for all the sensor nodes without overlapping so that the coverage of the area is maximized. To increase the reliability of results, they provided an exact integral area calculation for the fitness function for computing the area coverage corresponding to a given number of sensor nodes. At the end they compare the performance of their algorithm with the performance of MIGA, IGA, PSO, DPSO, ICS and CFPA.

The problem of deploying sensors for maximum coverage (MCSDP) aims to cover as much as possible an area with a minimum number of sensor nodes. The maximum coverage problem addressed in this paper is based on the calculation of the total area covered by deployed sensor nodes. Our contribution is based on GA and focuses on to choose the optimal positions of sensors for the best coverage.

Let us consider n be the number of homogeneous sensors with identical sensing range r s . We assume that each sensor has omnidirectional antena. We also assume that the sensing range and the communication range are the equal. The detection by each sensor is modeled as a circle on the two-dimensional grid. The center of the circle indicates the sensor and its radius indicates its sensing range. The cover model is Boolean. Boolean disk coverage model might be the most widely used sensor coverage model in the literature [4, 7, 12, 14] . The coverage function used is define by:

where d(s, p), the Euclidean distance between the sensor s and a point p is given by:

The observed area (A) to be covered with sensors is a rectangular region in two-dimensional Euclidean space. Ideally, having a fully covered area is given by:

The parameter of sensing range is generated from the real-world sensor in formations as in literature [12] [13] [14] .

The problem can be described as follows: we seek to have the maximum coverage with a given number n of sensors of the same radius r s . We formulate that the area really covered by the sensors, is the difference between the area of the surface A that we note Area(A) and the sum of the areas of the sensors Area(S i ). We call this difference Coverage(A) and calculate as presented in Eq. (4):

However, due to several overlaps, calculating n i Area(S i ) is not obvious. For two or three sensors, this can be less complex. Figure 1 illustrates the case with three sensors nodes.

We note the area covered by the three sensors in Fig. 1 , Area(S 1 ∪ S 2 ∪ S 3 ). Finding this area, would mean sum up the areas of the sensors and then subtract the sum of the areas of the intersections, being careful not to remove the same intersection area several times. This gives us:

This makes the task more complex when the number of sensors exceeds three. Found the total area covered by four or more sensors is mathematically very complex (Fig. 2) .

Based on the above, we formalize the problem as follows:

4 Genetic Algorithm

Genetic Algorithm (GA) is a widely used optimization algorithm, and it has been used frequently in different applications especially in WSN. It is an optimization method which is based on natural selection, the process that drives biological evolution. Especially, when no deterministic methods exist GA are used and it performs well. This technique is based on basic principles. First, it works on an initially random population of individuals, each representing a solution of the problem being addressed. Each solution is represented by a genotype or chromosome and is expressed as a phenotype. It is then necessary to develop an evaluation function (fitness) that distinguishes the best performing phenotype. The latter have a higher probability of bequeathing their genotype to their offspring. The rules governing this gene transfer are described in the form of genetic operators. Three operators are required:

-The selection operator which describes how the candidates are chosen for recombination; -The crossover operator is the main operator and corresponds to the method used to order mix the parents in order to generate offspring; -The mutation operator, used to add diversity to the population. Algorithm 1. Genetic algorithm's steps 1: Generation of a random population; 2: Evaluation for each individual; 3: Selection of individuals for recombination; 4: Generation of offspring thanks to a crossover operator; 5: Using mutation of offspring; 6: Go back to step 2 until stop criterion is met.

In the proposed genetic algorithm, we represent a chromosome as a set of n sensors with different geographic coordinates. Figure 3 shows the structure of a chromosome. 

As shown in Sect. 3, calculating the total area covered by sensor nodes with mathematical formulas is very hard to apply. Sensors can have one or more overlapping zones and this calculation when the number of sensor nodes is equal or greater than four is complex.

In this paper, we evaluate the area covered by considering each sensor node as an image and proposing another and new way to find the area covered. Indeed, we simulate a two-dimensional surface as a background with a number of 0. The number of 0 depends on the resolution initially selected. For example, a surface of 10 × 20 with a resolution of 0.5 will provide a table of 20 × 40 of 0 in the matrix. The circular stamp is the square of 0 which is entirely filled by a circle formed by 1. The size of the circle is based on a radius defined in the chromosome. Each chromosome provides the x and y axes of the position of the circles within the defined rectangular area as well as the proposed radius r s of the circles. The coordinates x and y change with each generation so that at the end we have the best positions. Finally, the program counts the number of 1 inside the rectangular field. Coverage corresponds to found by the ratio between the number of 1 and the initial number of 0. The following pseudo-code briefly summarizes how we arrive at the final result: 

In this section, we evaluate our proposal. Let N be the size of the population. In our study, a population of N = 100 individuals was used. The population consists of N genotype, and each genotype is a set of n = 15 sensors. The genetic algorithm ends after 350 iterations. As crossover and mutation operators, BLX-α and the Gaussian mutation are respectively used [3, 13] . P c and P m are respectively the crossover and mutation rate and the sensing area A is a rectangular of dimension 100 × 90.

Unlike the other methods listed in the literature review, ours puts itself in a real deployment situation, and takes into account overlapping between one or more sensors to calculate and give the maximum coverage rate. Several tests have been done. Figure 4 show the initial deployment at the beginning of the algorithm of one of these tests. At each iteration the positions of the sensors are displayed and at the end, the best population (Fig. 5 ) and the final position of sensors (Fig. 6 ) are given. For each set of values coverage -crossover, coverage-number of sensor, coverage-permutation and coverage -iteration, we have conduced several experiments which show that we can reach a coverage rate of up to 88%. For the cases shown in Fig. 5 and Fig. 6 we reach 85% of coverage rate. The results showed our algorithm is efficient and the proposed approach produces better coverage than initial deployment. Table 1 and Table 2 shows respectively the variation in the coverage rate as a function of the percentage of crossover and the variation in the coverage rate as a function of the number of sensors. For Table 1 the number of sensors is unchanged and the permutation rate is P m = 0.1 and for Table 2 the permutation rate is P m = 0.1 and crossover rate is P c = 0.7 (Fig. 7) . Keeping the number of sensors and the parameters fixed, we carried out several tests, some of the numerical results of which are listed in Table 3 . These tests show a coverage average of 77.36% and a standard deviation of 2.14. This significant standard deviation shows that on average the coverage rate between two tests varies slightly and hovers around 77%. 

Wireless sensor networks are used in several fields. Thus, covering an area as much as possible, with a limited number of sensor nodes is a major problem. This problem is called the Maximum Coverage Sensor Deployment Problem (MCSDP). Due to the increasing number of sensor nodes, and the likely overlaps of these nodes during deployment, this problem cannot be resolved using discrete mathematical formulas. This paper presents a solution to this problem. We have formally defined the problem of maximum coverage sensor deployment (MCSDP), which occurs frequently in real world applications. Given this definition, we proposed a new method for the evaluation of the areas of sensor nodes by combining this method with a genetic algorithm. Our approach, tested with homogeneous sensor nodes shows the effectiveness and the efficiency of the proposed system. In future work, it is planned to include obstacles and areas that do not require coverage in the deployment space and also use this approach for heterogeneous sensor nodes.

Deployment strategies in the wireless sensor networks: systematic literature review, classification, and current trends

Node deployment coverage in large wireless sensor networks

Real-coded genetic algorithms and intervalschemata

An efficient genetic algorithm for maximizing area coverage in wireless sensor networks

Packing circular-like objects in a rectangular container

A genetic algorithm-based approach to optimize the coverage and the localization in the wireless audio-sensors networks

Evolutionary-based wireless sensor deployment for target coverage

A linearized circle packing algorithm

Applications of wireless sensor networks for urban areas: a survey

Survey on coverage problems in wireless sensor networks

Coverage problems in sensor networks: a survey

An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks

The Roles of Crossover and Mutation in Real-coded Genetic Algorithms

Increasing the coverage of homogeneous wireless sensor network by genetic algorithm based deployment