{'fraction_non_alphanumeric': 0.028278688524590163, 'fraction_numerical': 0.003961748633879781, 'mean_word_length': 4.9808006535947715, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Wireless Sensor Network Deployment Optimization Using Reference-Point-Based Non-dominated Sorting Approach (NSGA-III)

Wireless sensor networks (WSN) nowadays have gained more interest, pushed by the growing necessity for data collection and transmission from both civilian and military domains. WSN is constructed from interconnected sensors and limited resource (battery), which requests great importance on the deployment strategy to increase the performance metrics for WSN (lifetime, coverage, QoS connectivity). Also, the deployment is considered as a fundamental issue in (WSNs) design, and it was taken from the perspective of the multi-objective optimization problem. Many of the existing deployment strategies are based on metaheuristics algorithms such as Genetic Algorithms (GAs) to resolve the deployment problem. In this article, we use and adopt one of the most attractive approaches for wireless sensor networks deployment (WSND) optimization based on metaheuristic searching which is named Non-dominated Sorting Genetic Algorithm-III (NSGA-III) In order to reach maximum coverage and minimize the consumption of energy to maximize the network lifetime under the connectivity constraint. The comparison results have proved the NSGA-III algorithm outperformed the Constrained Pareto-based Multi-objective Evolutionary Approach (CPMEA) that taken as a benchmark for this study. Those results encourage the application of NSGA-III to real-world deployment problems, and the importance of this approach is that it can be handled many objectives.


Introduction
WSNs are an increasing area of technology that has applications across many domains to keep pace with the developing technology of the Internet of Things (IoT). In general, the applications of WSNs can be classified into two types: monitoring and tracking. Monitoring is applied and used for analyzing; some of the examples are military, agriculture, health care, smart house, etc. Tracking is generally used for following the variation of an event; some of the examples are industry, public health, and military [1]. However, the WSN is not perfect. Indeed, given their low cost, and deployment in the often hostile or inaccessible area, which have some weaknesses including limited energy, thus a limited network lifetime, reduced bandwidth, low capture, processing, and communication. These limitations cause topology instabilities, degraded zone coverage, and network connectivity, and so on [2]. Therefore, to overcome all these critical limitations of the WSN, several research interests recently was issued in recent decades to enhance the performance of WSN, and the main ones concern the optimization of WSN deployment with the aim of improving the life-time of the network and coverage [3]. The deployment of the nodes in the interest zone is not necessarily predetermined. Thus, they can be a random or deterministic deployment in the interest zone. In situations where there is prior information of the interest zone, the deterministic deployment is preferably. While in other cases, because of the large size of the network or the inaccessibility of the interest zone, the use of random deployment is the only alternative [4]. As a result, the choice depends strongly on the sensor characteristics and the information of the terrain. Also, the deployment strategies may differ depending on the applications and objectives to be optimized, such as maximizing the coverage of the interest zone, ensuring good connectivity and maximizing the network lifetime. WSND is considered a multi-objective optimization (MOO) problem [3]. In order to reach maximum coverage and minimize the consumption of energy under the connectivity constraint in the same resolution model, many approaches were applied which formulated the problem as the form of a multi-objective function with constraints, have also been proposed in the literature. Such a problem modeled as a multi-objective function with constraints is generally proved to be an NP-complete problem.

Related Work
There are numerous problems related with several optimization aspects or criteria in the real world [5]. Numerous techniques based on optimization methods such as GA [6], heuristics and meta-heuristics [7], have been introduced for the resolution of NP-complete optimization problems in the WSND. In the following, we will present some of these solutions.
Deployment is sometimes considered a decision-making element is applied in some status where the user can place the sensors at specific positions. We find this approach in the study of Konstantinidis et al. [8]. where the authors present the problem DPAP (Deployment and Power Assignment Problem). Either a set of sensors of defined size, the objectives are to maximize the coverage (binary model) as well as to maximize the network lifetime. Lifetime depends to the moment when one of the sensors die (the batteries runs out). The decision variables are the sensor positions and the power allocated to the communication devices. To solve this problem, the author proposes a decomposition algorithm MOEA / D that he compares to NSGA-II. The authors redefine this problem in [9], where they integrate a more realistic energy model and are interested in dense deployments. MOEA / D previously used is modified and hybridized with heuristics specific to the problem; it proved to be more efficient than the previous methods. More accurate modeling of the area was discussed in [10], where the authors considered the obstacles, the variation of the detection radius and the inaccessible positions for the deployment. The authors have also developed a MOASA (Multi-objective Optimization Approach for Sensor Arrangement) algorithm, inspired by the SPEA2 algorithm to resolve these multi-objective problems: (i) maximizing the binary coverage; (ii) minimizing the redundancy of coverage; and (iii) minimize the deployed sensors number. Wei et al. [11]. developed a Multi-Objective GA (FD-MOGA) to resolve a three-dimensional deployment problem where the objectives are maximizing probabilistic coverage and maximizing detection levels, and minimizing energy consumption. The FD-MOGA algorithm proved to be more efficient than the MOGA algorithm. In the article of Oh et al. [12]. the authors used NSGA-II approach to optimize the following four objectives: (i) maximizing the binary coverage (taking into account several geometric coverage schemes) (ii) minimize the deployed sensors number, (iii) maximizing the user's preference, taking into account a classification of the types of sensors to be used and (iv) minimizing the distance between the nodes and the target. Chen et al. [13] suggested a hybrid GA based on the basic processes of genetic algorithms, merged with local search strategies. These hybrid methods divide the network nodes into a maximum disjoint coverings number that can cover every one of the targets. The purpose of their algorithm is to be able to resolve the problem, which is NP-complete by a detection technique comprehensive coverage and periodic switching of these disjoint covers. Thus, with such an approach, the network lifetime can be significantly improved. Chamam and Pierre proposed in [14] a centralized heuristic that allows dynamically calculating an almost-optimal set of sensors that can guarantee a predefined coverage rate while ensuring network connectivity in the situation where the communication radius (Rc) of each sensor is bigger than or equal to double its detection radius. However, it can be remarked that 100% coverage of the surveillance zone is not always guaranteed by  [15]. proposed a heuristic technique for life maximization in WSN via sensors with adjustable communication radius Rc. They implemented an approach based on a column generation technique and a heuristic incorporated into a local search pattern. This approach is tested in two different scenarios: the situation where the Rc of the sensors can be adjusted according to several levels of different powers, and the situation where the Rc of the sensors are fixed. They have shown that in the scenario where the sensors have adjustable Rc, the performance regarding lifetime is higher than the scenario where they have fixed Rc (the classic case). Also, Panag et al. [16]. proposed a new heuristic search scheme to find a maximum disjoint sensors number that absolutely cover a given surveillance area. To do this, they have implemented a method that enables applying a set of heuristics to search the solution space. The best-explored solution is used to update the next population. They have also shown, through tests done on applications requiring several coverage points, that the performance of their proposals in terms of optimality of the solution exceeds other existing proposals. Abdusy et al. [17]. used approach based on NSGA-II to get an optimal deployment that maintains full coverage and connectivity with a minimum sensor number. Authors defined a fitness function to maintain that each sensor is placed within the communication range of the other sensor and to restrict the sensors being near to each other in order to reach the optimal deployment. In addition, the authors apply this approach with the existence of the obstacles in [18].
The major aspect of this work aims to adapt the optimization algorithm NSGA-III introduced by Deb et al. [19]. for wireless sensor deployment problem the purpose is to maximize the coverage and the network lifetime and to compare our result with the state of the art approach CPMEA [3]. To the best of the author`s' knowledge, this strategy hasn't nevermore been suggested for WSND.
The remaining of the article is ordered as follows. In section III we provide the methodology for implementing the objective of the article. The simulation results are displayed in section IV while section V supplies a summary conclusion.

Proposed Deployment Methodology
This section provides the methodology used for WSND by adapting NSGA-III and the computation of the objective functions: coverage and the network lifetime.

Problem Formulation
We assume a 2-D static node in a rectangular sensing zone S, some similar sensors M with energy E and a static sink node K with infinite energy in the center of S. The sensors monitoring the zone of interest and reporting all issues to K. Each sensor i = 1...M has functional characteristics represented in sensing range (Rs) and communication range (Rc). However, these sensors make the communication with each other directly or via multiple hops through the adjacent sensors with K. The WSND problem is regarded from the aspect of the MOO problem due to its objectives. Therefore, for the formulation of the problem, we defined two contrasting objectives: the coverage zone and the network lifetime.

NSGA-III General Framework
The NSGA-III algorithm has been introduced in [19]. It is the last version of NSGA-II [20] one of the most used multi-objective algorithms, especially for its excellent performance, and its facility of adaptation to most continuous and combinatorial problems. The NSGA-III follows the pattern of a classic genetic algorithm, namely a reproduction cycle and a selection cycle; NSGA-III based on reference points instead of the crowd distance in NSGA-II to choose the individuals that will form the next generation in future, the main process is presented in Table 1. Order the population into Pareto fronts. The first front includes all the non-dominated individuals of the current population, and the second includes the individuals dominated by individuals of the first front. This distribution will intervene in the selection of the solutions until reached to the required size to form the next generation. If the last front to be inserted contain more individuals than is necessary, a selection must be made within this front based on reference points. Where the solutions that have the minimum perpendicular distance to the reference line has priority to be selected, the reference line is the line that starts from the center and passes on the reference point. Table 1. Pseudo code of NSGA-III algorithm. Finally, after we get the deployment solution that represents the positions of the sensors the computation of the objectives: coverage and lifetime, is provided in the following equations.

Coverage
Coverage: is a significant performance measure in the WSND. Let S be a region (zone) and let G {( 1 , 1 ), ( 2 , 2 ) … ( , )} be grids point of S. The coverage of region S by a set of sensors M mathematically defined in [3] by:

Lifetime
Lifetime: is given by determining the necessity cycles for forwarding the messages until the first nodes die, and we divide the need cycles over the maximum number of cycles, which is computed according to the minimum distance among the distances between every two nodes. It calculated as following:

Results and Discussion
For evaluating our adapting algorithm, a set of configurations has been adopted. As represented in Table  2 for taking more information concerning the metaheuristic searching optimization performance by modifying some parameters settings. The experimental researches were taken out in a MATLAB environment on a PC with 64-bit Windows 8.1 operating system, 8 GB RAM, and i5 CPU. We use each one of the configurations to produce results of our adaption (NSGA-III) and the benchmark (CPMEA). The Pareto front results presented in the following figures and compared between the two algorithms.
The results of our adaption (NSGA-III) have been compared with CPMEA results based on the configurations C1-C4. The Pareto front was plotted for each of the set of configurations, as presented in figure 1. The two axes represent the two main objectives of the deployment optimization: lifetime and coverage. From this figure, we can observe NSGA-III is superior to CPMEA in the most of the configurations.

Conclusion
In this article, we have proposed a formulation of the deployment problem taking into account the two objectives: coverage and network lifetime, a problem of multi-objective optimization is thus posed. NSGA-III was adapted for the goal of WSND. For evaluation, the approach was compared with the benchmark CPMEA. Four configurations of the parameters were employed for the evaluation, which allowed us to construct the optimal Pareto fronts. In the experiments, the NSGA-III found the optimal solutions for all configuration sets and stood out in the figure. Therefore, we can confirm the superiority of the NSGA-III compared to the benchmark (CPMEA) tested in the context of the wireless sensor network deployment problem.