1. Introduction
Wireless sensor networks (WSN) have been the subject of numerous research studies since the first known deployment of the
SOund SUrveillance System (SOSUS) 1950s [
1,
2]. Until the 1990s, except for a few radio beacons to route data from a sensor to the central controller expensive and cumbersome cabling was required. New sensor networks appeared in the 1990s, thanks to advances in the field of wireless techniques. As new wireless technologies progress, their range of applications increases. Among these innovative technologies, wireless sensor networks (WSN) have become very flexible and dynamic facets deployed in almost all types of environments whether rural, suburban, or urban [
1].
A WSN is a collection of sensor nodes that communicate using wireless technologies. WSNs are made up of small nodes that differ from traditional networks in their communication and detection ranges. Sensor nodes detect the physical phenomena located in the area and transmit the data in collaboration with the receiver node [
3]. The data captured by the nodes are routed through a multi-hop routing to a node, considered to be a “collection point”, called sink-node (or sink). The latter can be connected to the network user (via the Internet, a satellite, or another system). A sensor node can be a detection node, a transmission node, a relay node, or a combination of theses nodes.
Initially used in the army, this kind of network is now found in several fields, varying from industrial surveillance to the measurement of environmental data, agriculture, home automation, fire detection, medical sector, etc. [
1,
4,
5,
6,
7,
8,
9,
10]. These applications are responsible for monitoring a target point or area by recording a reaction and communicating it. Consequently, WSN applications play critical roles whether deployed in industry or in everyday life and must be effective. However, the weak capacities of the sensors both at the level of the detection and communication range constitute one of the first weaknesses of this type of network. The consequences are areas or targets with little or no coverage in the detection region reducing the effectiveness of the network.
Due to the constraining characteristics of the WSNs, one of the first challenges they face is figuring out how to perfectly cover a surveillance area. Coverage and connectivity are the two most fundamental problems of the WSN [
6]. One of the solutions that have long been considered to increase the global network coverage has been to increase the number of sensors. However, this solution is not efficient in terms of deployment, coverage, connectivity, and network lifetime. In fact, deployment and collaboration of sensors are some of the major features that directly influence the performance of the WSN. WSN deployment schemes can be classified into two main groups; deterministic and non-deterministic [
8,
11]. The main performance measures that come into play during the deployment of a WSN include coverage, connectivity, and network lifetime. Among these measures, we focus on coverage and connectivity.
For practical design and use of sensor networks in various application scenarios, coverage depends on several parameters. The coverage reflects how well a sensor monitors a point or an area. In most cases, to obtain maximum coverage a massive number of sensor nodes is required. In [
12], coverage is defined as how an area is covered by the sensor or to what extent each point is under of a sensor node. Depending on the kind of application, the coverage can take several forms [
11,
12,
13], including barrier coverage, point coverage and area coverage, which is divided into two types including full area coverage and partial area coverage [
3].
In addition to coverage, connectivity is an equally vital element of wireless sensor networks. The network in a defined area is connected if each deployed sensor node has at least one neighboring node with which it is connected. Khoufi, I. et al. [
6] explained that two sensor nodes are connected if and only if they can communicate directly (one-hop connectivity) or indirectly (multi-hop connectivity). In [
14], network connectivity is defined as the communication capacity between the different nodes of the network where data are transmitted to the base station by a single hop or by several hops. In this transmission process, if a sensor node communicates directly with the base station, it is a single-hop communication. On the other hand, the sensed data are transmitted to the base station via other intermediate sensor nodes, which is called multi-hop communication. When a WSN has single connectivity between sensor nodes, it is called single connectivity or 1-connectivity. The breakdown of a single node in such a scenario can lead to a failure of communication in the network. In the case of k-connectivity (
1), despite the failure of one node, the network remains connected. Connectivity is therefore vital for the transmission of sensed data to the base station [
6,
15]. It has a significant impact on the WSN, as the failure of a link between sensor nodes can result in communication failure in the network.
In real-life situations, usually for cost reasons, the number of sensors is generally restricted but there is a need to cover a large area and provide connectivity. It is also important to cover an area regardless of its shape and the way it is presented geometrically. The issue of coverage and connectivity can be described in various ways. Still, in our case, we are concerned with how to cover more of the area regardless of its geometric shape, with a given number of sensors of the same type while ensuring connectivity. This paper attempts to cover our area of interest (regular and irregular shape) using a genetic algorithm (GA) rather than circular wrapping algorithms [
16,
17]. Moreover, due to the random deployment of the sensors, causing an overlap, we propose a new fitness function, to know the exact area covered by the sensors.
The rest of the paper is organized as follows: in
Section 2, we provide related work on maximum coverage and connectivity. Then, in
Section 3, we present the network model by defining the problem and proposing a mathematical model with a detailed objective function. In
Section 4, the proposed GA approach is described in detail, and in
Section 5, we present and discuss the results. In
Section 6, we concludes this paper and gives an overview of some future works.
2. Related Works
Optimal positioning of the sensors for accurate measurement and data transmission is vital in wireless sensor networks. For this purpose, node deployment techniques are usually referred to as one of the most important approaches. Although several studies have been carried out to solve this problem, known as the Maximum Coverage Sensor Deployment Problem (MCSDP), there is a continuing requirement to refine the proposed solutions or to propose new ones. To do so, optimization techniques can be used to identify the best node placements that satisfy the desired objectives. In this section, we present some of the recent solutions proposed and based on genetic algorithms.
The coverage issue in WSN was firstly tackled by Yourim Yoon and Yong-Hyuk Kim, who showed that it is NP-hard [
18]. They focused on the problem of maximizing the area covered by the sensor with a specified number of sensors. They build their study on
n static sensors of
k types, and every type of sensor cover a part of the area with an arbitrary set radius
. They assumed that there is at least one sensor for each sensor type. The goal is to find locations
for all
n sensors that generate a maximum coverage for the area covered. They proposed a new approach to normalizing the problem that could improve the genetic algorithms’ performance. This approach was adapted to MCSDP to combine the GA search with the original solution space. After presenting some GAs (RANDOM, PGA, and MGA) without normalization, they propose OPTGA, which, similar to MGA, uses the Monte Carlo technique with an increased number of random samples to estimate the solutions and reorders the genes of the second parent to minimize the sum of the distances before recombination is applied. To further improve the performance of OPTGA, they merged OPTGA with a local search method called Virtual Force Algorithm (VFA) with some modifications. The VFA defined two concepts: “repulsive force” and “attractive force”. A repulsive force exists between two sensors if their coverage areas overlap; otherwise, an attractive force exists. Based on these two forces, the placement of the sensor is adjusted. In OPTGA, they apply the VFA to each offspring after the mutation step. They call it OPTHGA and show that OPTHGA performs significantly better than OPTGA, even if the OPTHGA algorithms have high computational complexity.
To overcome this pitfall, Ly et al. [
19] proposed an algorithm called IGA, which used the individual representation and replaced the Monte Carlo technique [
18] with a new technique and introduced a new mutation operator heuristic and dynamic. This has led to a considerable reduction in computational complexity and an increase in the quality of the IGA solution compared to OPTHGA. They introduced a new concept— the overlapping—for designing a new evaluation function, a heuristic technique for initializing population, and a dynamic mutation instead of the static one. The newly-proposed fitness function has shown its tremendous effectiveness in assessing the physical condition of individuals and reducing the complexity of calculations. The heuristic initialization method and the dynamic mutation operator have also improved the quality of their algorithm. They conclude from the experimental results that IGA is better than OPTHGA on all the instances in terms of computation time, quality, and solution stability.
Nguyen Thihanh et al. [
3] proposed a solution by reusing the same procedure for the mentioned problem as [
18]. They proposed a genetic algorithm called MIGA, based on IGA of [
19], to solve the problem of maximizing area coverage in a WSN with heterogeneous nodes. This genetic algorithm is built around the expression of a new chromosome, a custom heuristic initialization, a fusion of the Laplace crossover method (LX) and the arithmetic crossover method (AMXO), and a local search (VFA). They explain this choice of combining the two crossover methods by the fact that in IGA, the crossover operator used makes the offspring generated from the parents strictly follow the genetic information of its parents without the possibility of customizing the parameters. The combining of LX and AMXO guarantees them better results in terms of the quality of the solutions resulting from the crossover. Then, the authors perform the placement by using heterogeneous sensors, and completely excluding overlaps between sensors. By this way, they not only found an optimal positioning for all sensor nodes, but also ensured the maximum of the area coverage as much as possible. To increase the accuracy of the results, they use an exact integral area calculation for the fitness function to compute the area coverage for a set of sensors. The efficiency of their algorithm was then compared to that of IGA, PSO, DPSO, ICS, and CFPA and the results presented show that MIGA offers the best performance in terms of solution quality and stability on a majority of the tested instances.
However, the previous works cited above focus only on coverage and did not respond to the connectivity.
SK. Gupta et al. [
20] proposed a genetic algorithm based approach to find potential positions for sensor node placement such that all target points are k-covered and all sensor nodes are m-connected. They presented their linear programming formulation of the problem and then presented their approach based on the genetic algorithm they propose, with an appropriate representation of the chromosomes, the derivation of the fitness function, the selection, crossover, and mutation operators. The authors present a design for chromosome representation and derive a fitness function with three objectives: the use of minimum number of sensor nodes, the coverage, and the connectivity. They represent the chromosome as a string of 0 and 1 and set the length of each chromosome equal to the number of potential positions. Thus for a chromosome, if the value of gene
ith is 1, it means that a sensor node is placed on the potential position
ith, and the value of gene 0 indicates that no sensor is placed on the potential position
ith. Using several WSN scenarios for the experimental results, the authors showed that the proposed algorithm has much better time complexity than other GA-based approaches.
Two evolutionary algorithms are presented and evaluated for the indoor WSN deployment problem in [
14]. In the study, authors proposed a multi-objective deployment strategy (MODS) for WSNs based on evolutionary algorithms. The proposed strategy enables the deployment of a wireless sensor network for a smart building application. In the deployment approach, they considered the building constraints (such as walls and doors) that may affect the network communication by using an appropriate propagation model. The proposed WSN deployment method is then formulated as a combinatorial optimization problem by regarding a variety of objectives (energy, connectivity, and network implementation) that compose an exhaustive list of WSN design objectives. That is, unlike other methods, this approach to indoor WSN deployment considers coverage, cost, and connectivity objectives at the same time. The authors have considered constraints such as the multi-wall propagation model that takes into account all the obstacles in the building (i.e., walls, doors, windows, etc.) in order to obtain efficient results. An innovative coding solution, integrating both the cost of the network and the position of the nodes, was proposed. Indeed, in this study, the authors have coded the chromosome in such a way that it can integrate several pieces of information in a single bit (node coordinates and network cost). Finally, a comparative study between two evolutionary algorithms (classical GA and NSGA-II) was also presented to identify the use case of each.
Subash Harizan and Pratyay Kuila in [
21], proposed an improved genetic algorithm-based approach for energy-efficient scheduling of sensor nodes. A collection of N sensor nodes,
, is randomly spread within a region of interest to continuously or periodically monitor a set of
K targets,
. Therefore, the proposed algorithm will select a set of minimum number of active sensor nodes from
S to provide complete coverage of the target points and also maintain connectivity between the activated sensor nodes and the base station. During scheduling, sensor nodes of higher energy levels are preferred so that they can provide the service for maximum number of rounds. Thus, this is on of the aspect on which they are evaluated by the fitness function. Indeed, the authors derived an efficient fitness function to deal with four conflicting objectives with are to activate a minimum number of sensor nodes among the densely deployed sensor nodes, provide full coverage at all target points, maintain connectivity between the activated active sensor nodes and the base station, and ensure the selection of the active sensor nodes with a higher level of residual energy. Additionally, unlike the traditional GA, the authors have introduced another way of conducting the mutation operation to gain performance improvement and speed up the convergence of the proposed algorithm. In this mutation operation, instead of randomly returning the gene value, redundant or unused activated sensor nodes are found and turned off without affecting the network coverage and connectivity. Finally, the authors present several simulation cases of the approach and compare its performance to NSGA-II, traditional GA, and the GreedyCSC algorithm in terms of the number of sensor nodes selected in a schedule, the energy consumption of the network, and the number of turns required for the first sensor node to be completely without energy.
ZainEldin Hanaa et al. in [
22] proposed a GA-based deployment technique to maximize the coverage of randomly spread nodes in an area of interest, which is an
grid with a collection of homogeneous wireless sensor nodes
. They introduced an improved dynamic deployment technique based on genetic algorithm, called IDDT-GA, to maximize the area coverage by reducing the number of sensor nodes in the random deployment. Indeed, by reducing the number of sensor nodes in this way, the authors decrease the area of overlapping between sensor nodes and consequently increase the area covered by the sensors. The approach introduced in their paper uses the variable length coding notation by a two-point crossover and allows them to guarantee 1-connectivity between sensor nodes. In fact, the two-point crossover allows the chromosome length to be adaptive and the algorithm to search for the minimum number of sensor nodes that can cover the area. Thus, IDDT-GA uses a sufficient number of nodes to cover the entire region. The authors will then use random deployment to produce regions of varying intensity and regions with high density, while others, of lower intensity but interesting data, may be lost due to lack of optimal coverage. To compensate this, they add a mobility function to eliminate coverage gaps and increase the coverage of the area. The authors present several simulation results and comparisons with other algorithms which attest to the effectiveness of their proposal.
Njoya, A.N. et al. [
23] addressed the target coverage as in [
20]. They proposed a hybrid approach that ensured sensor deployment on a grid for coverage targets while considering connectivity. The authors proposed a sequential hybrid approach based on three algorithms. Based on the location of targets, the location of the sink, and the number of targets, the first placed the sensors to all targets were covered. The second removed redundancies from the placement algorithm to reduce the number of sensors deployed. Finally, to establish the connectivity between sensors, the third one, based on the Traveling Salesman Problem (TSP) with the genetic algorithm, generates a tree that gives a minimal path that links deployed sensors and sink. An essential aspect of their placement algorithm is the deterministic initialization at the start of the deployment algorithm that differs from those that do it randomly.
Later, authors in [
24] tackle fault tolerance and connectivity problems in WSNs. They focused their work on the restoration of connectivity and proposed a simple and efficient algorithm to accomplish movement-based
k-connectivity restoration that divides the nodes into the critical, which are the nodes whose failure reduces
k, and non-critical groups. The algorithm picks up and moves the non-critical nodes when a critical node stops working. This algorithm (PINC) moves a non-critical node with minimum movement cost to the position of the failed mote. The use of ultrasonic waves, or the use of a unique strength indicator received, allows them to identify obstacles, so that nodes can detect and ignore links passing through obstacles. This simplifies the communication and movement model. This way, nodes with communication links can move directly to each other’s position. The authors have proven the accuracy and complexity of their algorithm by stating four theorems that they prove. They also show, from their complexity analysis, that the time complexity of the proposed PINC algorithm is better than its counterparts. They then implemented the PINC algorithm on a small scale on a testbed of Kobuki robots and IRIS sensor motes.
More recently, the authors in [
25] have discussed connectivity estimation approaches for internet of things enabled wireless sensor networks. In this study, the authors review connectivity estimation approaches, describe their main ideas, and explain how they work by illustrating example networks. As, in WSN, connectivity is generally obtained in two cases (
k = 1 and
k > 1), the authors divided the connectivity estimation problem into two categories. For each case, they presented the algorithms for detecting cut vertices and bridges and explain in detail how these algorithms work. For the case
k = 1, several algorithms such as BFS, I-PRITCHARD, ENDBRIDGE, MILIC and E-MILIC, ABIDE, and DENCUT have been presented with each their specificities. For the case
k > 1, algorithms such as SECO, NIKE, BFSK, PACK, DECK, and KEIP have been discussed.
To the best of our knowledge, with the exception of [
19], for overlaps, the studies cited above and encountered in the literature perform the deployment based on non-overlapping cases and use
regular shape zones. In this paper, we introduce a deployment study for the maximum coverage considering overlaps while providing connectivity. Consequently, we have focused on the coverage of the most possible area with a set of sensor nodes, regardless of the geometric shape of the area concerned. The maximum coverage problem addressed in this paper is related to the calculation of the area covered by the deployed sensor nodes. Our work is based on GA and concentrates on:
the choice of optimal sensor positions;
finding the actual area covered by the sensors taking into account the overlap;
covering all types of area (regular shape or not);
deriving an efficient objective function with two main objectives: maximizing coverage in the observed area and minimizing coverage outside of the observed area with constraints to ensure connectivity.