# Contributions to the optimized deployment of connected sensors on the Internet of Things collection networks

Sami Mnasri

► To cite this version:

Sami Mnasri. Contributions to the optimized deployment of connected sensors on the Internet of Things collection networks. Networking and Internet Architecture [cs.NI]. Université Toulouse Jean Jaurès, 2018. English. NNT: tel-03124110

HAL Id: tel-03124110

https://hal.science/tel-03124110

Submitted on 28 Jan 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Université Fédérale

<figure><img src="image_1.png" /></figure>

Toulouse Midi-Pyrénées

THÈSE

En vue de l'obtention du

DOCTORAT DE L'UNIVERSITÉ DE
TOULOUSE

Délivré par :

Université Toulouse - Jean Jaurès

Présentée et soutenue par :

Sami MNASRI

le mercredi 27 Juin 2018

Titre :

Contributions to the optimized deployment of connected sensors
on the Internet of Things collection networks

École doctorale et discipline ou spécialité :

ED MITT : Domaine STIC : Réseaux, Télécoms, Systèmes et Architecture

Unité de recherche :

Institut de Recherche en Informatique de Toulouse (IRIT), équipe RMESS

Directeur de Thèse :

Thierry VAL, Professeur à l'Université de Toulouse

Jury :

Pr. Belhassen ZOUARI, Université de Carthage, Rapporteur

HDR Dr. Hanen IDOUDI, Ecole Nationale des Sciences de l'informatique de Tunis, Rapporteur

Dr. Najeh NASRI, Ecole Nationale d'Ingénieur de Sfax, Co-Directeur de thèse

Dr. Adrien VAN DEN BOSSCHE, l'Université de Toulouse, Co-Encadrant de thèse
*Nothing is stronger than a good education system that can be the basis of building human
being in order to reform morals towards modern civilizations and nations*
*Sami Mnasri*
To my mother and my father,
To my sisters and my brother,
To Ameni,
To my friends,

*In testimony of my great love*
*and my strong gratitude*
*Sami*
Acknowledgements

I would first like to thank Pr. Thierry VAL, my thesis director for his support and contribution in this research as well as for his availability. In particular, I thank him for giving me a great freedom in my research, for being attentive to all my comments or ideas and for answering my many questions. His encouragement and advices were invaluable, without which this work would probably not have been possible.

I thank Dr Nejah NASRI for his interest in my work as well as for his comments and advices which allowed me to improve the substance and form. I would like to thank Dr. Adrien VAN DEN BOSSCHE for his advice and guidelines, especially at the level of experiments and prototyping that have enhanced my work.

I also thank Pr. Belhassen ZOUARI and Dr. Hanen IDOUDI for agreeing to be part of my evaluation committee.

My thanks also go to all the teachers, staff and my students on the IUT of Blagnac for the good atmosphere they created in the premises of the IUT.

Finally, I thank all the teachers who contributed to my training and to all those who helped me during this work.
# About this dissertation

IoT collection networks raise many optimization problems, in particular because the sensors have limited capacity in energy, processing and memory. We are interested in a global contribution related to the optimization on wireless sensor networks using heuristics, meta-heuristics, hybrid methods, mathematical models, assessments of new optimization approaches on wireless sensor networks, multi-objective models, etc.

The continuous evolution of the IoT collection network research domain and technology allows optimizing the use of these networks in different number of contexts. The general problem of deployment of nodes can be described as follows: often, the sensors constituting the network cannot be precisely positioned and are scattered erratically. In order to compensate the randomness of sensor placement and increase the fault tolerance of the network, these sensors can be deployed intelligently. Unlike 3D deployment, there is a very abundant literature on this problem for 2D deployment ranging from the technical specificities of the sensors and their way of communicating, to the topological organization of the network itself. The 3D deployment of wireless sensors poses many optimization problems. Therefore, the goal is to provide 3D sensor organization solutions and find the most optimized architecture in order to improve the network performance.

In this context, heuristic approaches for optimization in wireless sensor networks can be envisaged. In addition, optimization problems are generally derived from real problems that are often antagonistic, unmeasurable and include several criteria. The dynamic, distributed and open aspect of the deployment problem led us to adopt advanced modeling and optimization technologies: hybridizing recent meta-heuristics. Indeed, in order to ensure a continuous evolution, a pragmatic flexibility and an infallible robustness against possible disturbances that could affect all or part of the network, the main goal was to propose hybridizations and modifications of the evolutionary optimization algorithms in order to achieve the positioning of nodes in wireless sensor networks with satisfaction of a set of constraints and objectives. In fact, hybrid meta-heuristics exploit the complementarity of these methods with each other, as well as with other "classical" approaches. This new class of hybrid algorithms has proven its robustness and efficiency in solving difficult optimization problems. We propose to focus our contribution composed of several complementary and progressive approaches, on the hybrid meta-heuristics. Especially on the evaluation of their performances and their applications on our real-world problem. These hybridization schemes are all validated by numerical results by the evaluation of algorithms with metrics such as the Hypervolume. Then, simulations supplemented by real experiments on testbeds were proposed. Finally, simulations are confronted with experiments to evaluate the behavior of algorithms and prove their stability and efficiency.

**Keywords:** 3D indoor deployment, ant colony algorithm, dimensionality reduction, experimental validation, genetic algorithms, hybridization, IoT collection networks, meta-heuristics, optimization, particle swarm optimization, user preferences.
## 2 Optimization methods and multi-agent systems for many-objective problems 30

<table><tr><td>2.1 Introduction</td><td>31</td></tr><tr><td>2.2 Combinatorial optimization</td><td>31</td></tr><tr><td>2.2.1 Complexity of a problem</td><td>31</td></tr><tr><td>2.2.2 Classification of optimization problems</td><td>31</td></tr><tr><td>2.3 Multi-objective optimization</td><td>32</td></tr><tr><td>2.3.1 Pareto Optimality Concepts</td><td>33</td></tr><tr><td>2.3.2 Approaches to solve multi-objective optimization problems</td><td>34</td></tr><tr><td>2.3.2.1 Transformation of a multi-objective problem into a single objective problem</td><td>34</td></tr><tr><td>2.3.2.2 Non-Pareto approaches (non-aggregated)</td><td>36</td></tr><tr><td>2.3.2.3 Pareto approach</td><td>37</td></tr><tr><td>2.4 Methods for solving multi-objective optimization problems</td><td>37</td></tr><tr><td>2.4.1 Exact methods</td><td>37</td></tr><tr><td>2.4.2 Meta-heuristics</td><td>38</td></tr><tr><td>2.4.2.1 Taboo Search (TS) / Simulated Annealing (SA)</td><td>38</td></tr><tr><td>2.4.2.2 Swarm Intelligence (ACO, PSO, BSO)</td><td>39</td></tr><tr><td>2.4.2.3 Genetic algorithms (NSGA-II as an exemple)</td><td>43</td></tr><tr><td>2.4.3 Many-objective optimization</td><td>46</td></tr><tr><td>2.4.3.1 Many-objective PSO algorithm</td><td>47</td></tr><tr><td>2.4.3.2 NSGA-III algorithm</td><td>47</td></tr><tr><td>2.4.3.3 MOEA/DD</td><td>48</td></tr><tr><td>2.4.3.4 Two_Arch2 algorithm</td><td>48</td></tr><tr><td>2.4.3.5 Similitudes and differences between many-objective algorithms</td><td>49</td></tr><tr><td>2.4.3.6 Difficulties in MaOAs</td><td>50</td></tr><tr><td>2.4.4 Hybridization of Meta-heuristics</td><td>51</td></tr><tr><td>2.4.4.1 Hybridization between metaheuristics</td><td>51</td></tr><tr><td>2.4.4.2 Hybridization of Meta-heuristics and Exact Methods</td><td>52</td></tr><tr><td>2.4.5 Relationship between the deployment problem and the multi-objective optimization</td><td>52</td></tr><tr><td>2.5 Multi-agent Systems</td><td>53</td></tr><tr><td>2.6 Preferences incorporation</td><td>56</td></tr><tr><td>2.6.1 Generalities</td><td>56</td></tr><tr><td>2.6.2 Interactive preferences (PI-EMO-PC)</td><td>57</td></tr><tr><td>2.7 Dimensionality reduction</td><td>58</td></tr><tr><td>2.7.1 Generalities</td><td>58</td></tr><tr><td>2.7.2 Offline correlation reduction methods based on machine learning for the 3D deployment problem</td><td>59</td></tr><tr><td>2.8 Conclusion</td><td>59</td></tr></table>

## II Contributions 60

### 3 Theoretical contributions 61

<table><tr><td>3.1 Introduction</td><td>62</td></tr><tr><td>3.2 Mathematical model of the 3D indoor deployment in DL-IoT collection networks</td><td>62</td></tr><tr><td>3.2.1 Architecture of nodes, assumptions, notation and objective function</td><td>62</td></tr><tr><td>3.2.1.1 Architecture of nodes</td><td>62</td></tr><tr><td>3.2.1.2 Assumptions</td><td>62</td></tr><tr><td>3.2.1.3 Notation</td><td>63</td></tr><tr><td>3.2.1.4 The objective function</td><td>65</td></tr><tr><td>3.2.2 The details of the objectives</td><td>65</td></tr><tr><td>3.3 Hybridizations and modifications on the optimization approaches for the 3D deployment</td><td>71</td></tr><tr><td>3.3.1 Chromosome coding for the proposed MaOEAs</td><td>71</td></tr><tr><td>3.3.2 Inclusion of diversity</td><td>72</td></tr><tr><td>3.3.2.1 Neighbourhood restriction and adaptive multi-operators</td><td>72</td></tr><tr><td>* Principles of the mutation and recombination with the neighbourhood (AxN and AmN)</td><td>72</td></tr><tr><td>* Implementation of the AxN and AmN strategies on the proposed algorithms</td><td>74</td></tr><tr><td>3.3.2.2 Including single-grid and mutiple scalarizing functions in the aggregation based approach</td><td>76</td></tr><tr><td>3.3.3 Incorporation of Dimensionality Reduction (the NL-MVU-PCA algorithm)</td><td>77</td></tr><tr><td>3.3.3.1 Incorporating L-PCA and NL-MVU-PCA on the tested EMOs</td><td>77</td></tr><tr><td>3.3.3.2 Integrating PI-EMO-PC, Knee points and NL-MVU-PCA on the proposed EMOs</td><td>77</td></tr><tr><td>3.3.4 Incorporation of preferences</td><td>78</td></tr><tr><td>3.3.4.1 PI-NSGA-III-VF (NSGA-III with interactive preferences)</td><td>79</td></tr><tr><td>3.3.4.2 The proposed hybrid PI-EMO-PC-INK algorithm: (PI-EMO-PC-Ideal-Nadir-Knee points)</td><td>81</td></tr></table>
List of figures

<table><tr><td>Figure 1.1 An example of area coverage using randomly deployed sensors</td><td>8</td></tr><tr><td>Figure 1.2 2D deployment vs. 3D deployment</td><td>8</td></tr><tr><td>Figure 1.3 Phases of deployment</td><td>10</td></tr><tr><td>Figure 1.4 Different geometric 3D coverage layouts</td><td>11</td></tr><tr><td>Figure 1.5 3D surface coverage</td><td>11</td></tr><tr><td>Figure 1.6 Mobility taxonomy</td><td>12</td></tr><tr><td>Figure 1.7 Coverage types</td><td>15</td></tr><tr><td>Figure 1.8 Binary sensing model</td><td>18</td></tr><tr><td>Figure 1.9 Probability sensing model</td><td>19</td></tr><tr><td>Figure 1.10 Guaranteed-connectivity scheme (a) and guaranteed-coverage scheme (b)</td><td>20</td></tr><tr><td>Figure 1.11 Deployment of an underwater WSN</td><td>21</td></tr><tr><td>Figure 1.12 Smart homes</td><td>25</td></tr><tr><td>Figure 2.1 Example of dominance</td><td>33</td></tr><tr><td>Figure 2.2 Pareto front for a bi-objective problem</td><td>33</td></tr><tr><td>Figure 2.3 Pareto Solutions</td><td>34</td></tr><tr><td>Figure 2.4 ε-contraint method</td><td>35</td></tr><tr><td>Figure 2.5 Classification of multi-objective optimization methods</td><td>36</td></tr><tr><td>Figure 2.6 Displacement of a particle</td><td>40</td></tr><tr><td>Figure 2.7 General architecture of a genetic algorithm</td><td>44</td></tr><tr><td>Figure 2.8 NSGA-II Steps</td><td>46</td></tr><tr><td>Figure 2.9 Flow-chart of the Two_Arch2 Algorithm</td><td>49</td></tr><tr><td>Figure 2.10 Classes of Hybridization</td><td>51</td></tr><tr><td>Figure 2.11 Schematization of an agent</td><td>54</td></tr><tr><td>Figure 2.12 Multi-agent System</td><td>54</td></tr><tr><td>Figure 3.1 The 3D DV-HOP and RSSI protocol</td><td>63</td></tr><tr><td>Figure 3.2 Different orientation positions of antennas</td><td>70</td></tr><tr><td>Figure 3.3 The chromosome representing the sensor in the 3D position (46, 53, 34)</td><td>72</td></tr><tr><td>Figure 3.4 The four steps of the proposed hybridization scheme</td><td>78</td></tr><tr><td>Figure 3.5 Flowchart of the PI-NSGA-III-VF</td><td>80</td></tr><tr><td>Figure 3.6 The proposed hybrid preference algorithm (PI-EMO-PC-INK)</td><td>81</td></tr><tr><td>Figure 3.7 Nadir and ideal objective points</td><td>82</td></tr><tr><td>Figure 3.8 The choice of the neighborhood of a particle Pa</td><td>85</td></tr><tr><td>Figure 3.9 The proposed MAS architecture</td><td>88</td></tr><tr><td>Figure 4.1: Localization algorithm with 3D DV-HOP + RSSI</td><td>109</td></tr><tr><td>Figure 4.2 Small-scale simulation scenario</td><td>112</td></tr><tr><td>Figure 4.3 Average RSSI rates during small-scale simulations</td><td>112</td></tr><tr><td>Figure 4.4 Average FER rates in small-scale simulations</td><td>113</td></tr><tr><td>Figure 4.5 Average number of neighbors in small-scale simulations</td><td>113</td></tr><tr><td>Figure 4.6 Variation of energy in relation to the number of fixed nodes, for 2 objectives</td><td>113</td></tr><tr><td>Figure 4.7 Variation of energy in relation to the number of fixed nodes, for 4 objectives</td><td>114</td></tr><tr><td>Figure 4.8 Change in lifetime in relation to the time</td><td>114</td></tr><tr><td>Figure 4.9 Experiments vs. simulations for small scale instances</td><td>114</td></tr><tr><td>Figure 4.10 Large-scale simulation scenario (85 fixed nodes and 36 nomad nodes)</td><td>115</td></tr><tr><td>Figure 4.11 Variations in the number of nomad nodes added for two objectives</td><td>115</td></tr><tr><td>Figure 4.12 Variations in the number of nomad nodes added for four objectives</td><td>115</td></tr><tr><td>Figure 4.13 Average RSSI rates for different number of objectives</td><td>116</td></tr><tr><td>Figure 4.14 Average RSSI rates according to the number of initial nodes</td><td>116</td></tr><tr><td>Figure 4.15 Average FER rates for different number of objectives</td><td>116</td></tr><tr><td>Figure 4.16 Average FER rates according to the number of initial node</td><td>116</td></tr><tr><td>Figure 4.17 Average numbers of neighbors for three objectives</td><td>117</td></tr><tr><td>Figure 4.18 Average numbers of neighbors for nine objectives</td><td>117</td></tr><tr><td>Figure 4.19 Variation of energy in relation to the number of fixed nodes, for two objectives</td><td>117</td></tr><tr><td>Figure 4.20 Variation of energy in relation to the number of fixed nodes, for four objectives</td><td>118</td></tr></table>
<table><tr><td>Figure 4.21 Change in lifetime in relation to the number of targets</td><td>118</td></tr><tr><td>Figure 4.22 The Teensy WiNo used nodes</td><td>120</td></tr><tr><td>Figure 4.23 The logical network architecture</td><td>121</td></tr><tr><td>Figure 4.24 The 2D and 3D architecture of the real deployed indoor network</td><td>122</td></tr><tr><td>Figure 4.25 Variations on the localization (RSSI), by day, for different positions</td><td>124</td></tr><tr><td>Figure 4.26 Variations on the localization (RSSI), by night, for different positions</td><td>124</td></tr><tr><td>Figure 4.27 Variations of the coverage (FER), by day, in different positions</td><td>125</td></tr><tr><td>Figure 4.28 Variations of the coverage (FER), overnight, in different positions</td><td>125</td></tr><tr><td>Figure 4.29 Variation of the number of neighbors, by day</td><td>125</td></tr><tr><td>Figure 4.30 Variation of the number of neighbors, by night</td><td>125</td></tr><tr><td>Figure 4.31 The average RSSI values, for different number of objectives</td><td>127</td></tr><tr><td>Figure 4.32 The average FER values, for different number of objectives</td><td>128</td></tr><tr><td>Figure 4.33 Average number of neighbors, for different number of objectives</td><td>128</td></tr><tr><td>Figure 4.34 Average lifetime of the network, for different number of objectives</td><td>128</td></tr><tr><td>Figure 4.35 Average energy consumption levels, as a function of time</td><td>128</td></tr><tr><td>Figure 4.36 Average rates of RSSI</td><td>129</td></tr><tr><td>Figure 4.37 Average rates of FER</td><td>130</td></tr><tr><td>Figure 4.38 Average number of neighbors</td><td>130</td></tr><tr><td>Figure 4.39 Comparing the average RSSI rates</td><td>132</td></tr><tr><td>Figure 4.40 Comparing the average FER rates</td><td>133</td></tr><tr><td>Figure 4.41 Comparing the average number of neighbors</td><td>133</td></tr><tr><td>Figure 4.42 Comparing the average energy consumption levels</td><td>133</td></tr><tr><td>Figure 4.43 Comparing the average lifetime</td><td>133</td></tr><tr><td>Figure 4.44 RSSI average rates of nodes in connection with the mobile node</td><td>137</td></tr><tr><td>Figure 4.45 FER average rates of nodes in connection with the mobile node</td><td>137</td></tr><tr><td>Figure 4.46 Average number of neighbors of nodes in connection with the mobile node</td><td>137</td></tr><tr><td>Figure 4.47 Comparing the average energy consumption levels</td><td>138</td></tr></table>
# List of algorithms

<table><tr><td>Algorithm 2.1 Simulated Annealing algorithm</td><td>38</td></tr><tr><td>Algorithm 2.2 Tabu Search algorithm</td><td>39</td></tr><tr><td>Algorithm 2.3 Ant Colony Optimization algorithm</td><td>40</td></tr><tr><td>Algorithm 2.4 PSO algorithm</td><td>42</td></tr><tr><td>Algorithm 2.5 Bee colony optimization algorithm</td><td>43</td></tr><tr><td>Algorithm 2.6 The NSGA-III algorithm</td><td>48</td></tr><tr><td>Algorithm 2.7 The MOEA/DD algorithm</td><td>48</td></tr><tr><td>Algorithm 3.1 The Neighbourhood crossover algorithm</td><td>73</td></tr><tr><td>Algorithm 3.2 The Neighbourhood mutation algorithm</td><td>74</td></tr><tr><td>Algorithm 3.3 The proposed ∈-NSGA-II-AxN-AmN algorithm</td><td>75</td></tr><tr><td>Algorithm 3.4 choosing_operator() procedure</td><td>75</td></tr><tr><td>Algorithm 3.5 The generation t of the proposed U-NSGA-III-AxN-AmN algorithm</td><td>76</td></tr><tr><td>Algorithm 3.6 The proposed AcNSGA-III algorithm</td><td>83</td></tr><tr><td>Algorithm 3.7 Operation of Each ant builds a solution() and Update_pheromone()</td><td>84</td></tr><tr><td>Algorithm 3.8 The acMaPSO algorithm</td><td>86</td></tr></table>
List of tables

<table><tr><td>Table 1.1 Recent deployment applications</td><td>25</td></tr><tr><td>Table 1.2 Comparisons between recent works resolving the deployment problem in WSN</td><td>27</td></tr><tr><td>Table 4.1 Comparative table of the most appropriate/recommended metrics for MaOAs</td><td>92</td></tr><tr><td>Table 4.2 Used objectives and their significance</td><td>94</td></tr><tr><td>Table 4.3 Best, average and worst values of HV with non-correlated objectives, using 15 independent runs</td><td>95</td></tr><tr><td>Table 4.4 Best, average and worst values of HV with correlated objectives using 15 independent runs</td><td>95</td></tr><tr><td>Table 4.5 Best, average and worst HV with different population sizes and various objectives numbers</td><td>95</td></tr><tr><td>Table 4.6 Average HV values with various scalarizing functions and correlation objectives relations</td><td>96</td></tr><tr><td>Table 4.7 Best, average and worst HV values using adaptive operators</td><td>97</td></tr><tr><td>Table 4.8 Best, average and worst HV values before and after applying the dimensionality reduction</td><td>98</td></tr><tr><td>Table 4.9 The correlation Matrix R on the first iteration</td><td>98</td></tr><tr><td>Table 4.10 The kernel Matrix K</td><td>98</td></tr><tr><td>Table 4.11 Eigenvectors and eigenvalues of the matrix R</td><td>99</td></tr><tr><td>Table 4.12 Eigenvectors and eigenvalues of the matrix K</td><td>99</td></tr><tr><td>Table 4.13 Eigenvalue Analysis for L-PCA</td><td>99</td></tr><tr><td>Table 4.14 Eigenvalue Analysis for NL-MVU-PCA</td><td>99</td></tr><tr><td>Table 4.15 RCM analysis for L-PCA</td><td>99</td></tr><tr><td>Table 4.16 RCM analysis for NL-MVU-PCA</td><td>99</td></tr><tr><td>Table 4.17 Selection scheme for L-PCA</td><td>100</td></tr><tr><td>Table 4.18 Selection scheme for NL-MVU-PCA</td><td>100</td></tr><tr><td>Table 4.19 Median obtained solutions (objective values)</td><td>100</td></tr><tr><td>Table 4.20 Median distance of the solutions obtained from the most preferred solutions</td><td>100</td></tr><tr><td>Table 4.21 Parameters setting of the algorithms</td><td>101</td></tr><tr><td>Table 4.22 Hypervolume values (Best, average and worst)</td><td>101</td></tr><tr><td>Table 4.23 Average retained objective values</td><td>101</td></tr><tr><td>Table 4.24 Average distance between the most preferred solutions and the obtained ones</td><td>102</td></tr><tr><td>Table 4.25 Features of the used DTLZ test problems</td><td>102</td></tr><tr><td>Table 4.26 Best, average and worst IGD values on DTLZ1-4 problems</td><td>103</td></tr><tr><td>Table 4.27 Best, average and worst IGD values on DTLZ5(2,15) and DTLZ5(3,5) problems</td><td>104</td></tr><tr><td>Table 4.28 Best, average and worst IGD values on DTLZ1 and DTLZ2 for different population sizes</td><td>104</td></tr><tr><td>Table 4.29 Best, average and worst IGD on DTLZ(2,15) et DTLZ(3,5) for different population sizes</td><td>105</td></tr><tr><td>Table 4.30 IGD median values on DTLZ1 and DTLZ2 for different population sizes</td><td>106</td></tr><tr><td>Table 4.31 Median IGD on DTLZ1 and DTLZ2 using neighborhood mating and adaptive recombination</td><td>106</td></tr><tr><td>Table 4.32 Median IGD on DTLZ(2,15), DTLZ(3,15) with neighborhood mating, adaptive recombination</td><td>106</td></tr><tr><td>Table 4.33 Smallest non-redundant objectives number on DTLZ5(2,15), DTLZ5(3,5)</td><td>107</td></tr><tr><td>Table 4.34 median IGD values before and after applying the dimensionality reduction</td><td>108</td></tr><tr><td>Table 4.35 Median distance between the obtained solutions and the most preferred solutions for ds =0.01</td><td>108</td></tr><tr><td>Table 4.36 Parameters of the experiments</td><td>119</td></tr><tr><td>Table 4.37 Technical characteristics of the used TeensyWiNo nodes</td><td>120</td></tr><tr><td>Table 4.38 Technical and localization characteristics of the installed node</td><td>122</td></tr><tr><td>Table 4.39 Locations of selected positions taken by the mobile node 'C'</td><td>123</td></tr><tr><td>Table 4.40 The improvement of RSSI and FER rates compared to the initial deployment, by day</td><td>126</td></tr><tr><td>Table 4.41 The improvement of RSSI and FER rates compared to the initial deployment, by night</td><td>126</td></tr><tr><td>Table 4.42 HV (Best, average and worst values)</td><td>131</td></tr><tr><td>Table 4.43 Setting parameters of the algorithm</td><td>134</td></tr><tr><td>Table 4.44. Hypervolume values (Best, average and worst)</td><td>135</td></tr><tr><td>Table 4.45 Best, average and worst IGD values on DTLZ1-4 test suite</td><td>136</td></tr><tr><td>Table 4.46 Comparing the average lifetime</td><td>138</td></tr></table>
List of acronyms

<table><tr><td>acMaPSO</td><td>accent-based Many-objective Particle Swarm Optimization</td></tr><tr><td>acMaMaPSO</td><td>accent-based many-objective multi-agent Particle Swarm Optimization</td></tr><tr><td>AcNSGA-III</td><td>Ant colony NSGA-III</td></tr><tr><td>ACO</td><td>Ant colony optimization</td></tr><tr><td>AGP</td><td>Art Gallery Problem</td></tr><tr><td>AHCH</td><td>Adaptive Hole Connected Healing</td></tr><tr><td>AI</td><td>Artificial Intelligence</td></tr><tr><td>AIS</td><td>Artificial Immune System</td></tr><tr><td>AmN</td><td>Adaptive multi-Mutation strategy with Neighbourhood restrictions</td></tr><tr><td>AODV</td><td>Ad-hoc On-demand Distance Vector</td></tr><tr><td>AxN</td><td>Adaptive multi-Recombination with Neighbourhood restrictions</td></tr><tr><td>BCO</td><td>Bees Colonies Optimization</td></tr><tr><td>BDA</td><td>Bernoulli Deployment Algorithm</td></tr><tr><td>BDI</td><td>Belief-Desire-Intention (model)</td></tr><tr><td>BS</td><td>Base Station</td></tr><tr><td>CA</td><td>Convergence Archive</td></tr><tr><td>cNSGA-III</td><td>constrained NSGA-III</td></tr><tr><td>CSMA/CA</td><td>Carrier-sense multiple access with collision avoidance</td></tr><tr><td>DA</td><td>Diversity Archive</td></tr><tr><td>DAI</td><td>Distributed Artificial Intelligence</td></tr><tr><td>dBm</td><td>Decibel-milliwatt (unit)</td></tr><tr><td>DDA</td><td>Differentiated Deployment Algorithm</td></tr><tr><td>DL-IoT</td><td>Device Layer -Internet of Things</td></tr><tr><td>DM</td><td>Decision Maker</td></tr><tr><td>DRP</td><td>Dominance Relation Preservation-based</td></tr><tr><td>DSN</td><td>Directional Sensor Networks</td></tr><tr><td>DTLZ</td><td>Deb-Thiele-Laumanns-Zitzler (test problems)</td></tr><tr><td>DV-Hop</td><td>Distance Vector Hop</td></tr><tr><td>EA</td><td>Evolutionary Algorithm</td></tr><tr><td>EC-NSGA-II</td><td>Extremized-Crowded NSGA-II</td></tr><tr><td>EMaO</td><td>Evolutionary Many-objective Optimization</td></tr><tr><td>EMO</td><td>Evolutionary Multi-objective Optimization</td></tr><tr><td>EMOA</td><td>Evolutionary Multi-objective Optimization Algorithm</td></tr><tr><td>FER</td><td>Frame Error Rate</td></tr><tr><td>FS</td><td>Feature Selection</td></tr><tr><td>GD</td><td>Generational Distance</td></tr><tr><td>GNVG</td><td>Generational Non-dominated Vector Generation</td></tr><tr><td>GNVGR</td><td>Generational Non-dominated Vector Generation Ratio</td></tr><tr><td>GPS</td><td>Global Positioning System</td></tr><tr><td>GSM</td><td>Global System for Mobile Communications</td></tr><tr><td>HV</td><td>HyperVolume</td></tr><tr><td>IGD</td><td>Inverted Generational Distance</td></tr><tr><td>IoT</td><td>Internet of Things</td></tr><tr><td>JADE</td><td>Java Agent Development framework</td></tr><tr><td>LoS</td><td>Line of sight</td></tr><tr><td>LQI</td><td>link quality indication</td></tr><tr><td>LoRa</td><td>Long Range</td></tr><tr><td>LS</td><td>Local Search</td></tr><tr><td>L-PCA</td><td>Linear Principal Component Analysis</td></tr><tr><td>MaOA</td><td>Many-objective optimization Algorithm</td></tr><tr><td>MaOEA</td><td>Many-objective Optimization Evolutionary Algorithm</td></tr><tr><td>MaOP</td><td>Many-objective Optimization Problem</td></tr><tr><td>MaOPSO</td><td>Many-objective Particle Swarm Optimization</td></tr><tr><td>MAS</td><td>multi-agent systems</td></tr></table>
<table>
  <tr>
    <td>MCDM</td>
    <td>Multi-Criteria Decision Making</td>
  </tr>
  <tr>
    <td>MOEA</td>
    <td>Multi-objective Optimization Evolutionary Algorithm</td>
  </tr>
  <tr>
    <td>MOEA/D</td>
    <td>Multi-objective Evolutionary Algorithm based on Decomposition</td>
  </tr>
  <tr>
    <td>MOEA/DD</td>
    <td>Multi-objective Evolutionary Algorithm based on Decomposition and Dominance</td>
  </tr>
  <tr>
    <td>MOGA</td>
    <td>Multi-Objective Genetic Algorithm</td>
  </tr>
  <tr>
    <td>MOP</td>
    <td>Multi-objective Optimization Problem</td>
  </tr>
  <tr>
    <td>MOPSO</td>
    <td>Multi-Objective Particle Swarm Optimization</td>
  </tr>
  <tr>
    <td>MVU</td>
    <td>Maximum Variance Unfolding</td>
  </tr>
  <tr>
    <td>NL-MVU-PCA</td>
    <td>Non-Linear-Maximum Variance Unfolding-Principal Component Analysis</td>
  </tr>
  <tr>
    <td>NPGA</td>
    <td>Niched Pareto Genetic Algorithm</td>
  </tr>
  <tr>
    <td>NSGA</td>
    <td>Non-dominated Sorting Genetic Algorithm</td>
  </tr>
  <tr>
    <td>NU</td>
    <td>Network Utilization</td>
  </tr>
  <tr>
    <td>NVA</td>
    <td>Non-dominated Vector Additional</td>
  </tr>
  <tr>
    <td>OMNeT++</td>
    <td>Objective Modular Network++</td>
  </tr>
  <tr>
    <td>ONVG</td>
    <td>Overall Non-dominated Vector Generation</td>
  </tr>
  <tr>
    <td>ONVGR</td>
    <td>Overall Non-dominated Vector Generation Ratio</td>
  </tr>
  <tr>
    <td>PAES</td>
    <td>Pareto Archived Evolutionary Strategy</td>
  </tr>
  <tr>
    <td>PBI</td>
    <td>Penality-based Boundary Intersection</td>
  </tr>
  <tr>
    <td>PCA</td>
    <td>Principal Component Analysis</td>
  </tr>
  <tr>
    <td>PCS</td>
    <td>Pareto Corner Search based</td>
  </tr>
  <tr>
    <td>PCSEA</td>
    <td>Pareto corner search evolutionary algorithm</td>
  </tr>
  <tr>
    <td>PESA</td>
    <td>Pareto Envelope-based Selection Algorithm</td>
  </tr>
  <tr>
    <td>PF</td>
    <td>Pareto front</td>
  </tr>
  <tr>
    <td>PFDA</td>
    <td>Potential Field Deployment Algorithm</td>
  </tr>
  <tr>
    <td>PI-EMOA</td>
    <td>Progressively Interactive EMO algorithm</td>
  </tr>
  <tr>
    <td>PI-EMO-PC</td>
    <td>Progressive-Interactive-Evolutionary Multi-objective Optimization-Polyhedral Cone</td>
  </tr>
  <tr>
    <td>PI-EMO-PC-INK</td>
    <td>Progressive-Interactive-EMO- Polyhedral Cone-Ideal point-Nadir point-Knee points</td>
  </tr>
  <tr>
    <td>PI-EMO-VF</td>
    <td>Progressive-Interactive-Evolutionary Multi-objective Optimization-Value-Function</td>
  </tr>
  <tr>
    <td>PL</td>
    <td>Path loss</td>
  </tr>
  <tr>
    <td>PP</td>
    <td>Positioning Problem</td>
  </tr>
  <tr>
    <td>PSO</td>
    <td>Particle Swarm Optimization</td>
  </tr>
  <tr>
    <td>RCM</td>
    <td>Reduced Correlation Matrix</td>
  </tr>
  <tr>
    <td>RERR</td>
    <td>Route Error</td>
  </tr>
  <tr>
    <td>RoI</td>
    <td>Region Of Interest</td>
  </tr>
  <tr>
    <td>RREP</td>
    <td>Route Reply</td>
  </tr>
  <tr>
    <td>RREQ</td>
    <td>Route Request</td>
  </tr>
  <tr>
    <td>RSSI</td>
    <td>Received Signal Strength Indication</td>
  </tr>
  <tr>
    <td>SA</td>
    <td>Simulated Annealing</td>
  </tr>
  <tr>
    <td>SBX</td>
    <td>Simulated Binary Crossover</td>
  </tr>
  <tr>
    <td>SMCP</td>
    <td>Set MultiCover Problem</td>
  </tr>
  <tr>
    <td>SOP</td>
    <td>Single-objective Optimization Problem</td>
  </tr>
  <tr>
    <td>SPEA</td>
    <td>Strength Pareto Evolutionary Approach</td>
  </tr>
  <tr>
    <td>TCB</td>
    <td>Weighted Tchebycheff Distance</td>
  </tr>
  <tr>
    <td>TKR-NSGA-II</td>
    <td>Trade-off-based KR-NSGA-II</td>
  </tr>
  <tr>
    <td>TS</td>
    <td>Taboo Search</td>
  </tr>
  <tr>
    <td>Two_Arch2</td>
    <td>Two_Arch2 Two-Archive2 (algorithm)</td>
  </tr>
  <tr>
    <td>UASN</td>
    <td>Underwater Acoustic Sensor Network</td>
  </tr>
  <tr>
    <td>UFS</td>
    <td>Unsupervised Feature Selection-based</td>
  </tr>
  <tr>
    <td>USN</td>
    <td>Underwater Sensor Network</td>
  </tr>
  <tr>
    <td>UWB</td>
    <td>Ultra Wide Band</td>
  </tr>
  <tr>
    <td>U-NSGA-III</td>
    <td>Unified NSGA-III</td>
  </tr>
  <tr>
    <td>VEGA</td>
    <td>Vector Evaluated Genetic Algorithm</td>
  </tr>
  <tr>
    <td>VFA</td>
    <td>Virtual Force Algorithm</td>
  </tr>
  <tr>
    <td>VP</td>
    <td>Voronoi Partition</td>
  </tr>
  <tr>
    <td>WFG</td>
    <td>Walking Fish Group (test problems)</td>
  </tr>
  <tr>
    <td>WiFi</td>
    <td>Wireless Fidelity</td>
  </tr>
  <tr>
    <td>WiNo</td>
    <td>Wireless Node</td>
  </tr>
  <tr>
    <td>WS</td>
    <td>Weighted Sum</td>
  </tr>
  <tr>
    <td>WSN</td>
    <td>Wireless Sensor Network</td>
  </tr>
  <tr>
    <td>ZDT</td>
    <td>Zitzler-Deb-Thiele (test problems)</td>
  </tr>
</table>
# Introduction and overview

## Motivations and problematic

With different contexts of application, wireless sensor networks (WSN) are a research field that is in continuous evolution, especially with the emergence of the Internet of Things (IoT). Indeed, IoT is a concept that is closely related to the issues discussed in our study. IoT is a scenario in which different heterogeneous and communicating entities called objects or things (people, robots or devices) are connected and distinguished by unique identifiers. These entities can automatically transfer data to the network without any human intervention. WSN is the bridge connecting the real world to the digital one. It provides hardware communication to transmit and retrieve real values detected by wireless connected objects (sensor nodes). While the role of IoT is to process this data, manipulate it and make the decisions. In this thesis, we are interested in DL-IoT (DeviceLayer-IoT) networks which are collection networks used to collect data from distributed sensor nodes in the environment of the network. Hence, our approach can be applied for both WSN and IoT contexts. In this respect, given the limited energy, processing and memory capacity of sensors/objects, DL-IoT collection networks raise many optimization problems. Our global contribution is the proposal of heuristics, hybrid meta-heuristics (centralized and distributed), multi-objective models, mathematical formulations and evaluations of recent optimization approaches on DL-IoT collection networks. Given the continuous growth in the themes of DL-IoT collection networks, different contexts can be reversed such as optimizing the deployment of nodes.

Deploying the nodes is the first step in installing a WSN. In terms of energy consumption optimization, this first step greatly affects the performance, reliability and operation of the network. The problem of deploying the nodes can be described as the positioning of all the sensors (that can be randomly scattered initially) constituting the network. To compensate their erratic nature of placement, a large number of sensors are often deployed intelligently. This can also contribute in increasing the fault tolerance of the network. For the 2D deployment of WSN, a very abundant literature exists ranging from the topological organization of the network to the technical specificities of the sensors and their way of communicating. However, the low-cost 3D deployment poses many optimization problems with a limited literature. Hence, our goal is to find the most optimized architecture and provide 3D sensor solutions, while improving the network performance. In this respect, several issues and objectives are related to the problem of deployment of sensor networks such as energy consumption, lifetime and localization. As a result, different heuristic approaches can be considered for optimizing WSNs.

The distributed and dynamic nature of the deployment problem requires the use of advanced and recent optimization and modeling methodologies: hybrid meta-heuristics. These latters allow exploiting the complementarity of these methods with each other and taking advantage from the benefits of other conventional approaches hybridized with them. This new class of hybrid meta-heuristics has shown its performance in solving difficult optimization problems especially when faced by objectives (like ours) that mainly concern the assurance of an evolutionary, flexible and robust system against network disturbances. Our contribution consists in putting a set of well justified modifications and hybridizations on the meta-heuristics, then applying them and evaluating their performances on our real world problem of deployment. In this respect, the most difficult optimization problems to be solved are generally derived from real problems that are often unmeasurable, complex and antagonistic.
In general, these problems include several criteria. This is due to the fact that they have
several evaluation objectives; often contradictory; to be considered simultaneously. This gave
birth to the theory of multi-objective optimization. In the literature, several methods of
solving multi-objective problems have been developed. These methods can be classified into
two main classes: exact methods and approximate ones that are subdivided into meta-
heuristics and specific heuristics. Meta-heuristics form a set of optimization algorithms that
aim to solve difficult optimization problems. These algorithms allows improving the quality
of the solutions without guaranteeing the optimality of the obtained solution but in a very
reasonable calculation time with respect to the complexity of the problem, often unsolvable in
a polynomial time. Real-world optimization problems often have several conflicting and
contradictory objectives and constraints (called multi-objective optimization problems
(MOP)). This implies that there is not a single solution that is optimal in relation to all these
objectives in the same time. The output of such multi-objective optimization algorithms is
generally composed of a set of incomparable non-dominated solutions. These solutions are
called "Pareto front" (PF). The goal of multi-objective optimization is to find a well-
distributed and well-converged approximation of the PF. Subsequently, the decision maker
(DM) can select the preferred solution. To determine the PF of a problem, various methods
that are based on the imitation of the principles of biological evolution, have been proposed in
the literature. These methods, named evolutionary algorithms (EA), have become popular and
widely used in the resolution of MOPs because of their insensitivity to the objective function
aspects and forms such as multimodality, discontinuity, convexity and its search space
uniformity (Deb 2001). Indeed, evolutionary multi-objective optimization (EMO) is a new
branch of optimization that has emerged following this success of the Multi-Objective
Optimization EA (MOEA) on MOP resolving.

**Research aims and principal contributions**

The aim of this thesis is to propose hybridizations and modifications of evolutionary
optimization algorithms in order to realize the adequate positioning of nodes in WSN while
satisfying of a set of constraints and objectives.

* As a first stage, an in-depth literature review was conducted on the methods of optimizing the deployment in WSN, especially the methods resolving the 3D indoor deployment. This study covers swarm-based meta-heuristics (particle swarm optimization, ant colony optimization and bee hives algorithm), genetic algorithms, taboo research and simulated annealing. The study also deals with the single-objective and multi-objective case; the static and dynamic case; the distributed and parallel case of deployment.

* In the second stage, a mathematical formulation based on an Integer Linear Programming model and aims at modeling the problematic is proposed. This formulation identifies and explains the objective function to optimize, the decision variables and the different constraints to be taken into consideration. Our goal is to minimize the number of sensor nodes to use and the energy consumption. At the same time, maximizing the network lifetime, the coverage, the localization and connectivity.

* In the third stage, the focus is on the proposition of different justified hybridization and modifications schemes introduced on the optimization algorithms in order to better solve the deployment problem:

- In a first approach, an adaptive mutation and recombination operators with neighborhood mating constraints is proposed. The use of a concept of multiple scalarization functions is introduced to deal with: (i) the inefficiency of Pareto-based multi-objective evolutionary algorithms, (ii) the inefficiency of the
recombination operation, and (iii) the exponential increase in costs (time and space) when solving multi-objective problems in the real world context.

- In a second approach, the incorporation of preferences is established: In the case of real world problems having a large number of objectives, the size of the population and the number of necessary solutions depend exponentially on number of objectives. Thus, the performance of the optimization algorithms deteriorates when solving such problems. To solve this challenge, the NSGA-III algorithm is hybridized with an interactive user preference strategy (PI-EMO-VF) that follows the evolution of new solutions to gradually incorporate the preferences of the user. In this work, the effectiveness of the NSGA-III is tested in real-world problems, and compared to another recent multi-objective algorithm (MOEA/DD).

- In a third approach, a justified hybridization scheme that combines three classes of multi-objective algorithms. These algorithms rely on reference points (NSGA-III, MOEA/DD), aggregation (Two_Arch2) and decomposition (MOEA/D) with two procedures based on dimensionality reduction (MVU-PCA) and preferences (PI-EMO-PC). The purpose of this hybridization is to benefit from the advantages of each method to solve our complex problem.

- In a fourth approach, a new hybrid algorithm derived from biological observations (ant search behavior and genetics) is proposed. It is based on the recent variant of the genetic algorithms (NSGA-III) and the ant colony algorithm (ACO). This is the first time NSGA-III and ACO are integrated into a hybrid platform. Moreover, unlike traditional hybridizations, these two algorithms iterate at the same time and interact using the same population (the initial population of the NSGA-III is the population built by the ants in the initial phase of the ACO in the same iteration). Then, the steps of the ant algorithm are injected into the NSGA-III with incorporation of several modifications on the original NSGA-III.

- In a fifth approach, a particle swarm optimization algorithm (called acMaPSO) based on a new bird accent concept is proposed. The new bird accent concept is which relies on a set of birds that are separated into different accent groups by their regional dwelling and are classified into groups according to their ways of singing. This new concept of bird accent is introduced to preserve the diversity of the population during research and to assess the particle search capability in their local areas. To ensure that the search escapes local optima, the most expert particles (the parents) "die" and are regularly replaced by new particles that are randomly generated.

It is also proposed to test this hybridization in a distributed environment. For this purpose, it is proposed to hybridize the acMaPSO algorithm with a multi-agent system (MAS). The new variant (named acMaMaPSO) takes advantage of agent distribution and particle interactivity. We propose a decentralized multi-agent architecture that contains three types of agents: an environment agent, swarm agents and bird agents (or particle agents). These agents have different knowledge, goals, abilities and action plans.

All these proposed hybridizations are tested and approved by numerical results that use evaluation metrics such as the Hypervolume. Afterwards, simulations and prototypes on real testbeds have been proposed. Then, in order to prove the stability and efficiency of these hybridizations in different contexts, the simulations are confronted with real experiments.
Structuring of the document

This document is structured into four chapters divided in two parts. The first part illustrates the state of the art in the first two chapters; and the second part details the proposed contributions in chapters 3 and 4.

The first chapter starts by presenting the state of the art of the 3D indoor deployment problem. We introduce the issues of the three-dimensional deployment and its different types, objectives, models and applications. Then we identified and criticized the recent research works dealing with the problem of deployment.

The second chapter introduces the methods used to solve the 3D indoor deployment, especially the evolutionary optimization algorithms, the multi-agent systems and the incorporation of dimensionality reduction and user preferences. We also detail the fundamental concepts of multi-objective optimization such as the dominance and the Pareto front. Then we describe the main classical approaches and meta-heuristic of resolution of multi-objective problems.

In the third chapter is dedicated to illustrate our mathematical modeling of the deployment problem based on an integer linear programming formulation. We present the architecture of nodes, the assumptions, the notation and the objective function. Then we detail the considered objectives and their specificities. Moreover, this chapter is devoted to explain and justify the proposed hybridizations and modifications that are introduced to meta-heuristics to improve their performances and capabilities to solve optimization problems. Especially complex and many-objective real world problems like ours. These changes relies essentially on the following contributions: the use of the neighborhood and adaptive recombination operators; the use of multiple scalarizing functions in the aggregation based approach; the incorporation of dimensionality reduction and users preferences; a hybrid framework for NSGA-III and Ant system; and finally the proposition of a concept of bird accents in PSO and its hybridization with MAS.

The last fourth chapter is devoted to illustrate the results of various evaluations. We initially introduced the different test parameters and evaluation metrics that we used to validate our proposals. We turn next to illustrate the numerical results of the 3D deployment problem after incorporating our proposed hybrid scheme of dimensionality reduction and preferences. Then we present the results on the DTLZ unconstrained test functions. Afterward, we propose a study that investigates the modeling of the used protocols and presents the simulations with small and large instances. Next, we propose ACO and NSGA-III experiments, then the results of the based-on bird's accent PSO algorithm and the PSO-MAS one.

Finally, we present our conclusions as well as our perspectives and futures directions of research.
# Part I
## State of the Art
# Chapter 1
## The 3D indoor deployment problem in WSN and DL-IoT collection networks

<table><tr><td>1.1 Introduction</td><td>7</td></tr><tr><td>1.2 Presentation, migration from WSN to DL-IoT and complexity of the deployment problem</td><td>7</td></tr><tr><td>1.3 The 3D deployment strategies in WSN</td><td>10</td></tr><tr><td>1.3.1 Full coverage</td><td>10</td></tr><tr><td>1.3.2 K-coverage</td><td>11</td></tr><tr><td>1.3.3 Surface coverage</td><td>11</td></tr><tr><td>1.4 Conflicting types of deployments</td><td>11</td></tr><tr><td>1.4.1 Single Objective deployment vs. multi-objective deployment</td><td>11</td></tr><tr><td>1.4.2 Deterministic deployment vs. stochastic deployment</td><td>12</td></tr><tr><td>1.4.3 Stationary deployment vs. mobile deployment</td><td>12</td></tr><tr><td>1.4.4 Homogenous deployment vs. heterogeneous deployment</td><td>12</td></tr><tr><td>1.4.5 Static deployment vs. dynamic deployment</td><td>13</td></tr><tr><td>1.5 Initial objectives to be satisfied during deployment</td><td>13</td></tr><tr><td>1.5.1 The number of deployed nodes, cost and scalability</td><td>13</td></tr><tr><td>1.5.2 Coverage problem</td><td>14</td></tr><tr><td>1.5.3 Connectivity problem</td><td>15</td></tr><tr><td>1.5.4 Coverage with Connectivity</td><td>16</td></tr><tr><td>1.5.5 Energy efficiency</td><td>16</td></tr><tr><td>1.5.6 Network lifetime</td><td>17</td></tr><tr><td>1.5.7 Network traffic</td><td>17</td></tr><tr><td>1.5.8 Data fidelity</td><td>17</td></tr><tr><td>1.5.9 Fault tolerance and load balancing</td><td>18</td></tr><tr><td>1.5.10 Latency</td><td>18</td></tr><tr><td>1.6 Sensing models</td><td>18</td></tr><tr><td>1.6.1 Binary model</td><td>18</td></tr><tr><td>1.6.2 Probability model</td><td>19</td></tr><tr><td>1.6.3 Tracking detection model</td><td>19</td></tr><tr><td>1.6.4 Coverage and connectivity model</td><td>20</td></tr><tr><td>1.7 Open deployment issues</td><td>20</td></tr><tr><td>1.8 Applications of the deployment</td><td>23</td></tr><tr><td>1.9 Methodologies for solving the problem of deployment</td><td>25</td></tr><tr><td>1.9.1 Virtual Force algorithms</td><td>26</td></tr><tr><td>1.9.2 BDA, PFDA and DDA Algorithms</td><td>26</td></tr><tr><td>1.9.3 Heuristic optimization</td><td>26</td></tr><tr><td>1.10 Other problems similar to the node positioning problem</td><td>26</td></tr><tr><td>1.10.1 Set MultiCover Problem</td><td>26</td></tr><tr><td>1.10.2 Art Gallery Problem</td><td>27</td></tr><tr><td>1.10.3 Other similar problems</td><td>27</td></tr><tr><td>1.11 Comparison and review of recent studies on WSN deployment</td><td>27</td></tr><tr><td>1.12 Conclusion</td><td>29</td></tr></table>
## 1.1 Introduction

Deployment represents a fundamental role in setting up efficient wireless sensor networks (WSN). In general, WSN are widely used in a variety of applications ranging from monitoring a smart house (planned deployment) to monitoring forest fires with parachuted sensors (random deployment). In this first chapter, we focus on the planned deployment, in which the sensor nodes must be accurately positioned at predetermined locations to optimize one or more design objectives of the WSN, under some given constraints. The purpose of planned deployment is to determine the type, number, and locations of nodes to optimize coverage, connectivity and network lifetime. There have been a large number of studies, which proposed algorithms for solving the premeditated deployment problem. The main purposes of this chapter are two-fold. The first one is to present the complexity of 3D deployment and then detail the types of sensors, objectives, applications and recent research that concerns the strategy used to solve this problem. The second one is to present a comparative survey between recent optimization approaches used to resolve the deployment problem in WSN. Based on our extensive review, we discuss the strengths and limitations of each proposed solutions and compare them in terms of the different WSN design factors.

## 1.2 Presentation, migration from WSN to DL-IoT and complexity of the deployment problem

Another concept is closely related to our problem, it is the IoT (Internet of Things). The IoT is a scenario in which entities (devices, people or robots) are connected and have a unique identifier for each. They are able to transfer data over the network without human or automatic intervention. These objects communicate using protocols such as the Bluetooth or the 802.15.4 as it is the case in our experiments (section 4.5). WSN is the bridge which links the real world to the digital one. It is responsible for the hardware communication to convey the real world values detected by the wireless connected things (sensor nodes) to the Internet. While the IoT is responsible for data processing, manipulation and decision making. In our study we are interested in the DL-IoT (DeviceLayer-IoT) (Van den Bossche et al, 2016) which is a network of collection used to collect data from the sensors nodes disseminated in the network environment. Thus, our approach and contributions are valid for both WSN and IoT contexts.

Indeed, a fundamental problem in the WSN is how to deploy sensor nodes. The deployment problem can be described as follows: Having *N* wireless sensors and an area *A* to cover, how to deploy these sensors to form a WSN that meets system requirements, such as the connectivity of the network, its ability to detect relevant events happening in *A*, and its ability to provide a required period of operation. This problem is related to coverage, connectivity, and lifetime issues. Indeed, the problem of deployment in WSN refers to the determination of the positions of nodes (and/or the base stations) so that the coverage, the connectivity and the energy efficiency can be obtained with a minimum number of nodes.

Events happening in an area lacking a sufficient number of nodes may be unnoticed. Moreover, areas with dense sensor populations suffer from congestion, redundancy detection, and delays. Optimal deployment ensures adequate quality of service, long network life and cost saving. The problem of deployment can also be defined as follows: having a surface *A* in 2D or 3D with a set of obstacles (if these obstacles exist, they should not partition the area) and a set of sensors with different types (according to their radii of detection and communication), the overall goal is to minimize the number of nodes to be deployed on *A* while ensuring one or more objectives such as network coverage and connectivity. It is said that the target region is covered if each point in *A* is covered by an active sensor having a probability of coverage *Pc* and a sensing range *R<sub>s</sub>* if there is direct communication (Line of Sight). Besides, it is said
that the network monitoring a target region is fully connected if all sensors can route data in multi-hop to the base station or to another destination node.

Most deployment approaches consider a WSN with randomly deployed sensors (Ammari, 2014) which are generally modeled by a Poisson point process with a density $\gamma$. This Poisson process is defined as follows: for any zone $A$ in the region $R$, the distribution of the number of nodes in $A$ is the mean distribution of Poisson $\gamma \|A\|$, $\|A\|$ is the surface of $A$ (Ammari, 2014). Given the number of nodes, their locations are mutually independent random variables and uniformly distributed over $A$. It is known that $n$ nodes whose locations are mutually independent random variables, with a uniform distribution within $A$, are mainly associated to a Poisson process with a density $\gamma$, provided that $A$ is large (Hall, 1988).

An example of randomly deployed sensor networks is shown in Figure 1.1. There are twelve sensors deployed in a rectangular detection field. The density of sensors on the left side of the field is higher than that on the right one. Therefore, the detection field is not fully covered by the sensors.

<figure><img src="image_2.png" /><figcaption>Figure 1.1 An example of area coverage using randomly deployed sensors</figcaption></figure>

Finding the optimal node distribution is a difficult problem to solve and is considered NP-hard for most formulations. This problem is proven to be optimally solved in 2D environments while it has been proven to be NP-difficult if it is generalized to 3D environments (Cheng et al., 2008). Figure 1.2 shows an example of 2D deployment and another for 3D deployment.

<figure><img src="image_3.png" /><figcaption>Figure 1.2 The 2D deployment vs. the 3D deployment</figcaption></figure>

When sensors are deployed randomly, the initial coverage area provided by the network cannot be optimal as in the case of deterministic deployment. In order to increase the covered area, redundant sensors are deployed. Redundancy makes sensor networks denser than normal ad hoc networks. However, increasing sensor density cannot provide a 100% coverage probability. In addition, it is expensive to maintain high-density WSN on a large scale. Therefore, other approaches should be used to avoid these problems and improve the
coverage after the initial random deployment. Another problem that complicates the redeployment is that of the robustness of WSN. Indeed, once deployed, it is expensive and impractical, even impossible, to replace unusable sensors in most types of applications. Hence, if a particular node is no longer running, there will be an impact on the overall performance of the network. The loss of a node may be due to different causes, such as battery depletion, physical damage caused by environmental forces, or destruction by the enemy. If a sensor that covers a sensitive area dies and no other sensor can cover that area, the WSN fails its mission of efficiently distributing the sensors.

Indeed, one way to optimize the distribution strategy in WSN is to have redundant sensors that improve the performance of the network. In addition, if the detection field is vast or has limited access, the sensors may not be able to be deployed one by one in specific locations. Instead, they can be disseminated from an airplane. When the sensors are randomly deployed, the initial coverage area provided by the network cannot be optimal as in the case of deterministic deployment. In order to increase the coverage area, redundant sensors can be deployed. Redundancy makes sensor networks denser than ad hoc networks. However, increasing sensor density can not provide a 100% coverage probability. Even more, it is expensive to maintain high-density sensor arrays on a large scale. Therefore, other approaches should be used in order to avoid these problems and improve the coverage after the initial random deployment. Another problem that complicates the redeployment is the robustness of WSN. Once deployed, it is expensive and impractical, if not impossible, to replace unusable sensors in most types of applications. Therefore, if a particular node is no longer running, there will be an impact on the overall performance of the network. The loss of a node may be due to various causes such as battery depletion, physical damage from environmental forces, or destruction by the enemy. If a sensor that covers a sensitive area dies and no other sensor can cover that area, the sensor array fails in its mission of efficiently distributing the sensors.

The process of deploying sensor nodes greatly influences the performance of a WSN. The problem of deployment or positioning nodes in a WSN is a strategy that defines the topology of the network, and therefore the number and position of nodes. The quality of monitoring, connectivity, and power consumption are also directly affected by the network topology.

The different deployment tasks can be grouped into three main phases: A pre-deployment and deployment phase (Figure 1.3 (a)) which is achieved by the manual placement of nodes or the spreading of nodes from a helicopter, for example. A phase of post-deployment (figure 1.3 (b)) is necessary if the topology of the network has evolved, for example following a displacement of nodes, or a change of the radio propagation conditions. The third phase concerns the redeployment (Figure 1.3 (c)) which is based on adding new nodes to the network in order to replace some failed nodes. The system can iterate on phases 2 and 3.

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /><figcaption>Figure 1.3 Phases of deployment</figcaption></figure>

Different issues are encountered at the level of the deployment of sensor nodes in WSN. These studies mainly concern stationary and mobile cases; single and multi-objective cases; deterministic and stochastic aspects; and finally static and dynamic deployments.

The coverage is affected by the sensitivity of the sensors represented by the detection range (noted Rs), while the connectivity is guaranteed by the communication range (noted Rc). According to (Frye et al., 2006), the degradation of the coverage probability in some WSN applications is tolerable, whereas the degradation of the probability of connectivity could be fatal for the network. In the context of dynamic deployment, we investigate in (Mnasri et al., 2014a) the research works proposing solutions for the sensor nodes repositioning and its related issues. Connectivity and coverage are the most used factors in determining the communication and the detection efficiency, respectively. Moreover, we propose in (Mnasri et al., 2014a) and (Mnasri et al., 2014b) a detailed study of deployment in the static case. They distinguish two deployment methodologies according to the distribution of the nodes (either random or controlled). The treated primary objectives can be as follows:

- The coverage which is one of the most preponderant problems in WSN. Several types of coverage are presented: point coverage, area coverage, barrier coverage and coverage of an event or a moving target.

- The consumed energy and ensuring the energy efficiency.

- The network connectivity.

- The lifetime of the network.

- The network traffic.

- The reliability of data.

- The cost of deployment (depending on the number of deployed nodes).

- The fault tolerance and load balancing between nodes.

## 1.3 The 3D deployment strategies in WSN

When designing deployment strategies, several factors must be considered such as the monitoring area, the sensor capabilities (detection range and transmission range), the area coverage, and the lifetime. The following questions should also be considered when establishing a deployment strategy: how many sensors should be deployed? How to place sensors in the monitoring area? Where to put the sink if we can choose its position? The number of sensors can be deduced from the lower limit of the monitoring area, sensor capacity and design requirements. Three types of coverage exist:

### 1.3.1 Full coverage

Full coverage is achieved if every point in the 3D RoI is at least covered by a sensor. Full area coverage requires the deployment of a large number of sensors, which increases cost and complexity. However, partial coverage only guarantees a certain percentage of coverage (Wang et al., 2007). Figure 1.4 illustrates different geometric layouts used in the 3D coverage.
<figure><img src="image_6.png" /><figcaption>**Figure 1.4 Different geometric 3D coverage layouts** (Younis and akkaya, 2008)</figcaption></figure>

### 1.3.2 K-coverage

With regard to the k-coverage, a 3D RoI is assumed to be k-covered if there are at least k sensors that cover and monitor each point of the 3D RoI. Indeed, k-coverage represents the logical extension of the case of 1-coverage. In the case of k-coverage, the distance between the detection nodes is minimized with the appearance of overlaps between the detection spheres. In general, when achieving the k-coverage optimally (K>1), the complexity of the coverage algorithm will increase (Xu et al., 2010).

### 1.3.3 Surface coverage

In the case of surface coverage (shown in Figure 1.5), the sensors can only be deployed on the surface of the RoI. Many real applications require this kind of surface coverage where the RoI is a complex surface that is neither a complete 3D space nor a 2D plane. Mathematically, the detection field can be modeled as several small simplified rectangles as a single-valued function $z=f(x, y)$ with two node distribution models: a planar surface Poisson point model and a space surface Poisson point one (Ammari, 2014). (Jin et al., 2012) addresses the problem of surface coverage in terms of reliability of the monitored data and quality of detection.

<figure><img src="image_7.png" /><figcaption>**Figure 1.5 3D surface coverage** (Ammari, 2014)</figcaption></figure>

## 1.4 Conflicting types of deployments

### 1.4.1 Single Objective deployment vs. multi-objective deployment

The criteria and objectives, on which the deployment is optimized, are often contradictory. This is the case of coverage and energy consumption because the best the coverage is, the most the energy consumption is. It is also the case of the survivability and fault tolerance. Therefore, we cannot find a deployment that optimizes all objectives simultaneously. Hence the need for an optimal trade-off between the different objectives. According to the used approach, we can either optimize each objective alone or use an aggregation function that combines all objectives in a single function with weights that represent the importance of each objective.
### 1.4.2 Deterministic deployment vs. stochastic deployment

When the selection of sensor positions is possible and determined beforehand, this is referred to as the deterministic deployment. When sensors can be dropped from an aircraft, for example, this is referred to as the non-deterministic or stochastic deployment. This last type of deployment cannot be optimal as long as it can result in very dense areas and others less dense or even disconnected. Deterministic deployment provides an optimal network configuration. However, because of the size and density required to provide adequate network coverage across large geographic areas, careful node positioning is not practical. In addition, many WSN applications should operate in hostile environments which make the deterministic deployment impossible in some cases. As a result, stochastic deployment becomes the only possible alternative. As an example, the work of (Clouqueur et al., 2002) aims to determine the number of needed randomly deployed nodes for target detection by optimizing the deployment cost and the area coverage.

### 1.4.3 Stationnary deployment vs. mobile deployment

Considering the mobility of nodes as a criterion, two deployment strategies can be distinguished: static deployment in which nodes have unchanged positions and mobile deployment where the nodes have a mobile capacity and can move and reposition themselves after the initial deployment. Then, some regions of the network may become uncovered due to occurred events in the RoI or depletion of sensor batteries. A solution to remedy this is to move some mobile nodes to these regions. Various examples of mobile node applications can be cited such as target tracking, rescue or underwater and military surveillance. (Romer and Mattern, 2004) classify nodes according to their mobility into three classes: static nodes, mobile ones and mobile sinks. Figure 1.6 describes other characteristics of mobility: passive nodes are often attached to or carried by moving entities while active nodes have automotive capabilities. Besides, the degree of mobility varies from a continuous movement to an occasional movement with long periods of immobility.

<figure><img src="image_8.png" /><figcaption>Figure 1.6 Mobility taxonomy</figcaption></figure>

However, different studies (Idoudi et al. 2012), Idoudi (2017) highlights the necessity to optimize the movement of nodes. According to (Guvensan and Yavuz, 2011), moving a node one meter can consume more than 30 times of energy than transmitting 1 ko of data. Despite this, mobility provides better coverage and connectivity and increases the network adaptability.

### 1.4.4 Homogenous deployment vs. heterogeneous deployment

The type of application for which the WSN is installed determines the types of sensors to deploy: are they homogeneous or having different roles thus characterizing a heterogeneous architecture. A wireless network is qualified as heterogeneous if the distribution of the nodes in the RoI is heterogeneous. Indeed, the first visions of the WSN consider homogeneous devices, generally identical from software and hardware point of view. However, different recent applications require a variety of devices that differ in number, type and role played in
the network (some nodes may function as cluster heads or gateways to other communication networks such as GSM networks, satellite ones, LoRa, SigFox, 5G, NB-IoT or WiFi).

### 1.4.5 Static deployment vs. dynamic deployment

Static deployment assumes that there is no mobility after the first positioning of nodes in the network. In the case of static deployment, the best node locations are chosen based on the optimization strategy, then no changes will occur during the lifetime of the network. Static deployment can be either random or deterministic. As we mentioned before, the positions of nodes have a considerable influence on the performance of the WSN and its operation. On the other hand, metrics which are independent of the state of the network and assuming a fixed operation scheme are often used to choose the locations of nodes. Among these static metrics, the distance between nodes. Moreover, the initial configuration of the network does not take into account the dynamic changes during the operation of the latter such as the mobility of targets. Hence the interest of dynamically repositioning nodes during the network operation. For example, to substitute some nodes having exhausted batteries, other sensors can be moved. Dynamic deployment is a solution for the problem of no guarantee of optimality during the initial deployment. It assumes that nodes can move in a coordinated way in the RoI. However, the relocation of nodes during the network operation is often expensive and requires the continuous monitoring of the state of the network and the events occurring in the neighborhood of the node. In addition, solutions must be found to the problem of data manipulation and delivery during the relocation process.

## 1.5 Initial objectives to be satisfied during deployment

### 1.5.1 The number of deployed nodes, cost and scalability

- **Number of nodes:** More than half of the papers dedicated to resolve the optimal deployment of nodes aim to reach the defined goals with a minimum cost. These studies are based on the assumption that low-cost detection devices embedded inside the sensors are used to monitor phenomena such as temperature, pressure, humidity, light, sound or magnetism. However, if we consider the deployment of hundreds or thousands of sensors, the overall cost of deploying the network must be taken into consideration. Thus, the number of sensors deployed is one of the essential measures that must be taken into account in the WSN deployment process. Indeed, in some specific applications, it is not realistic to consider low cost sensors because the more sensors used, the higher the cost becomes. Hence, the cost of a sensor strongly depends on the target application and the monitoring environment. For example, in the case of oceanographic applications such as offshore exploration, the cost of the sensor will be much higher because the detection device is much more sophisticated in order to detect specific phenomena and withstand the influences of the environment.

- **Cost:** The cost of a WSN starts from the construction phase of nodes. This cost may be variable depending on the application and the included detection devices. Nodes can be equipped with other equipment such as GPS that can increase the final cost of the node. Some applications do not take into account the cost of the node because of the low price of the used nodes. In this case, random deployment is an excellent way to deploy nodes in the RoI. A forest, an ocean or a battlefield are some examples of these applications. In other applications, the node costs are quite high and must be included in the node deployment strategies. Besides the node construction cost, deployment and maintenance costs are also applied to the total cost of a network. When the deployment is not random and is done by hand or with the help of particular automated robots, the cost of placing nodes must be taken into account. Indeed, the more the network needs nodes, the more its construction, deployment and maintenance will be high.
**- Scalability and density of nodes:** To monitor and detect events, some WSNs require hundreds or thousands of deployed nodes. In some specific applications (see section 1.8), this number can even reach an extreme value of millions. Scalability is another essential metric to consider when the deployment scheme is designed because it will affect the network coverage, cost and performance. High-density areas increase the cost of networking and computing. While low-density areas can cause the problem of coverage holes or network partitions. The distribution of the nodes may be uniform or non-uniform. Indeed, sensors that are near the base station are more likely to be used in data transmission. Thus, the density of nodes near the base station must be higher than other areas. In this case, the density of the nodes is said to be non-uniform. Uniform density of nodes decreases the likelihood of nodes clustering and the appearance of cover holes. The number of nodes must be minimized while ensuring maximum coverage.

**1.5.2 Coverage problem**

Coverage and deployment issues are fundamentally related. In order to achieve deterministic coverage, a static network must be deployed in a predefined form. Thus, optimal deployment of sensors will also provide good coverage of the monitored area. The coverage can be defined as follows: if each point in the region is at a maximum distance of R$_{s}$ (detection range) from at least one sensor, then the network guarantees full coverage. Depending on the application for which the network is deployed, different levels of coverage may be implemented. Some applications (see section 1.8) accept a deterioration of coverage. While some other critical applications require full coverage over the lifetime of the network and failure to meet this requirement can lead to network failure. The ratio of the area covered by the detection nodes to the global application area is defined as the coverage. The ideal value of this parameter is 100%, which means that the entire surface is covered by nodes. In addition, the degree of coverage of a point in the RoI is defined as the number of nodes covering that point. Based on this definition, the degree of coverage of a WSN is defined as the minimum of the degrees of coverage in all the RoI. Theoretically, each node has a communication range (R$_{c}$) that defines the field in which another node can be placed to receive data. R$_{c}$ is different from the detection range (R$_{s}$) that defines the area that a node can observe. R$_{c}$ and R$_{s}$ may be equal but are often different.

The coverage in WSN is widely discussed in the literature, especially in the 2D case. Generally, the considered coverage issues are area coverage, point/target coverage, energy optimization coverage, and k-coverage. The percentage of the deployment area in which an event can be monitored by at least one sensor is expressed as 1-coverage (Ammari M. Habib, 2014). In an ideal deployment, the coverage must be 100%. Unfortunately, sensors are subject to failure, measurement errors, damages and energy depletion. Therefore, a more general case has been defined: the k-coverage (k ≥ 1), where each point of the monitored area must be monitored by at least k sensors.

The most studied coverage problem is that of area coverage. The primary objective of the sensor network is to cover and monitor an area (also called region). Figure 1.7 shows an example of several types of sensor deployments to cover a square-shaped area.

<figure><img src="image_9.png" /><figcaption>Figure 1.7 Coverage types</figcaption></figure>
In the area coverage problem, each sensor covers a particular sub-area, and the total area of the sensor network is constituted by all the covered sub-areas. Maximizing the total coverage area of the WSN is the primary objective of the coverage area problem. Area coverage problem is closely related to the targeted application, such as target detection and tracking, battlefield monitoring, personal protection, and animal behavior tracking.

The most commonly used model for coverage is the disk detection model. It is based on the idea that all the points located in a centered-on-sensor disk, are supposed to be covered by the sensor. However, in the literature, many research works assume a fixed detection range and an isotropic sensor detection capability. The detection capability of a sensor can be classified as a binary or probabilistic. Some published articles, use the ratio of the covered area and the overall deployment area as a metric to measure the quality of coverage. However, other works focused on the worst-case coverage. In addition, another less used method is based on measuring the probability of movement of targets or the probability of an event that is happening without being detected.

Most coverage problems in WSN are related to the quality of area monitoring or event tracking. When the nodes are randomly deployed, the position of the nodes is no longer controlled. Therefore, some places in the target region remain uncovered. These areas are known as coverage holes. In some applications, nodes are equipped with mobile units to be able to move and cover these holes. To measure the coverage, we can just divide the RoI following a grid of small squares where each one represents a sensitive zone. Each square containing a node is considered as covered while each square that does not contain a node is considered as uncovered. Using this measurement method, the percentage of covered squares of all squares is known as the coverage rate. (Aitsaadi et al., 2011) considered this model to measure the coverage rate found by their proposed algorithms. The circular detection model can be also adopted. It is also known as a binary disk model where each point inside the cover disc centered on the node is covered, and every point that is outside that disc is uncovered. Due to the characteristics of the real world, this model was unrealistic and the researchers proposed a more realistic model based on probability. According to these models used to represent the detection capabilities of each node, the detection coverage for the entire network can be determined. The probabilistic circular model is more realistic (but more complicated) than other models.

### 1.5.3 Connectivity problem

In addition to the coverage, it is crucial for a WSN to maintain connectivity. Connectivity can be defined as the ability of nodes to reach the base station. If there is no available path from any node to the sink, then the data collected by that node cannot be processed. Regardless of the used communication model, network connectivity is often measured by a connectivity graph. If this graph is full connected, the network is assumed to be connected; otherwise it is considered as partitioned. That is, a network is said to be connected if active nodes can communicate together and a path can be established between each sending node and a presumed receiver one. Otherwise, we may not be informed of the events occurring in the RoI. This communication can be indirect using other nodes as relays. If a sensor detecting a fire cannot send this information to the base station, it will be more challenging to extinguish this fire. Therefore, the network topology must be connected and able to give information about any evolution of the monitored events.

Network connectivity is a problem to consider when designing the WSN. Indeed, in different research works; contrary to the coverage that is often considered a constraint or an objective when positioning nodes; the network connectivity has been neglected assuming that a good coverage will always give a connected network (when the communication field
exceeds the detection one). Despite this, a limited communication field results in a reduced connectivity unless there is a substantial redundancy of coverage.

The connectivity also makes possible the adjustment of the communication between the nodes of the network if a part of the network becomes disconnected due to breakdowns or energy exhaustion of a set of nodes. Connectivity is also needed to ensure the message propagation to the base station. The loss of connectivity often involves the end of the network lifetime. Assuming that there are several distinct paths between every two nodes, the degree of connectivity can be defined as the minimum number of paths between every two nodes in the network. If we should be connected with more than one sensor, this is referred to as the k-connectivity (Guang et al., 2009). As well as the coverage, various research works describe based-on k-connectivity algorithms that construct k distinct paths between each node and sink. K-connectivity introduces more reliability than 1-connectivity in data transmission by guaranteeing k-1 other paths if a path fails. Moreover, using different paths facilitates the design of distributed mechanisms such as the traffic load balancing which helps to reduce power consumption and extend the network life.

### 1.5.4 Coverage with Connectivity

Coverage and connectivity are related to the locations of nodes that affect them both. Any optimal deployment strategy must simultaneously ensure a globally connected network and an optimal coverage. (Bai et al., 2006) formulate sufficient conditions to ensure coverage and connectivity in WSN. These conditions are influenced by the node locations, the detection range ($R_s$), and the communication range ($R_c$). They prove that if $R_s \ge \sqrt{3}R_c$ and the RoI is fully covered, then the communication graph is connected. Thus, it is necessary to combine the achievement of coverage and connectivity in a single deployment planning.

- **Relation between 1-coverage and connectivity:** (Zhang, 2003) and (Wang et al., 2003) were the first to integrate the scheduling of activities in detection and communication. Both studies state that if a convex region is totally covered entirely by sensors, the corresponding communication graph will be connected when $R_c \ge 2R_s$. That is, if $R_c \ge 2R_s$, the network can guarantee both coverage and connectivity.

- **Relation between k-coverage and connectivity:** Based on the condition $R_c \ge 2R_s$ for coverage to imply connectivity, (Tian and Georganas, 2004) study the relationship between the degree of coverage and the connectivity. They prove the following findings for a convex region A covered by K nodes if $R_c \ge 2R_s$: i) These nodes form a connected communication graph K. ii) Interior connectivity is 2K. iii) It is possible to disconnect a boundary node from the rest of the communication graph by removing K sensors.

### 1.5.5 Energy efficiency

Generally, nodes in WSN have limited energy. The initial deployment scenario is usually based on a set of nodes and a smaller number of base stations. Indeed, a mobile node has different components such as memory, battery, processor, detection devices and mobility ones. These components use the battery power. After deployment, it is not always possible to recharge and maintain the node battery. Therefore, it is beneficial to know the energy consumed by each of these components to optimize their energy consumption. In this respect, (Pei et al., 2008) investigate the energy consumption of different types of node's hardware for different applications with different microprocessor platforms and communication protocols. (Mei et al., 2004) have also proposed a mobile device for moving nodes and calculated the energy consumed by nodes when moving straight or turning.

The energy consumed by nodes is not uniform. In general, the nodes near the BS consume more power than nodes far from BS or at the border of the RoI, because they are used as relays to transmit the packets to other nodes. In many practical scenarios, the placement of sensors can be controlled so that the density of nodes can be changed by the
variation of the energy consumption. In this way, the lifetime of the network can be increased. In a small WSN, nodes can be arbitrarily placed. As for a large WSN, it is possible to deploy several sensors in areas where the energy consumption is much higher. For example, in the case of aerial deployment, by merely dropping sensors on a set of selected areas. Thus, it is necessary to establish a correlation between the density of nodes and the energy consumption. This density must correspond to the distance between the sensors and the BS.

Indeed, the waste of energy can be caused by several reasons: i) The phenomenon of collision: if more than one packet is received by a node at the same time, these packets must be discarded and a process of retransmissions must be initiated. ii) The over-listening where the node receives packets that are destined to other nodes. iii) The control packet overhead.

The energy consumption is often considered interchangeable with the lifetime. Indeed, due to the limited energy resources in the node batteries, it is necessary to effectively deploy and use the nodes in order to increase the lifetime of the network.

### 1.5.6 Network lifetime

As mentioned above, the limitation of the energy resources affects the overall operation of the WSN. Therefore, it is important to optimize the energy consumption to maximize the network lifetime. This latter can be defined as the time after which the network is partitioned in a way that makes data collection impossible from a part of the network (Ferentinos et al., 2007). Another definition of the network lifetime uses the time after which the first node becomes non-operational. Indeed, according to the application of the WSN, the lifetime varies from a few hours to several years. It considerably influences the energy efficiency and the robustness of the nodes. In order to increase the lifetime of the network, different ways exist such as the relocation of nodes, the incremental deployment (adding new nodes after identifying defective ones), the balancing of loads and energy consumption between nodes to minimize the risk of node failure.

### 1.5.7 Network traffic

Another factor that directly affects the lifetime is the message traffic. Indeed, the consumed energy is proportionally dependent on the number of delivered messages. Hence, the message traffic must be minimized in WSN. Two types of messages exist. i) *Network messages* that contain information such as viewing angle, status, residual energy, detection range, and node position. ii) *Application-related messages* that contain data detected from the environment. To optimize the lifetime in WSN, the distribution of redundant messages must be avoided or minimized. To achieve this, we often use the in-network processing in the case of *application messages* (Ammari M. Habib, 2014). Regarding *network messages*, they are exchanged during the initial configuration where each node determines its position and those of its neighbors by using specific network messages. Repositioning strategies aim at calculating the final position of nodes. These strategies are iterative, which implies excessive message traffic. Two repositioning approaches exist: repositioning with physical movement and with virtual movement. Inversely with the virtual movement strategy, in the physical movement strategy, the sensor nodes physically change its position after each step. In terms of network lifetime, the physical movement strategy is less efficient than the virtual one.

### 1.5.8 Data fidelity

Data fidelity is another important factor to be considered when deploying and designing WSN. This factor aims to ensure the credibility of the collected data. WSN determine an evaluation of the detected phenomena by collecting readings from different independent nodes often heterogeneous. The merging of these data decreases the likelihood of false alarms and increases the reliability of the reported incidents. From the point of view of signal processing, the merging of these data aims to minimize the effect of distortion by including
the ratios of different nodes in the evaluation of the detected phenomena. Redundancy of nodes in the RoI increases the accuracy of the merged data, but it has the disadvantage of requiring an increased density of nodes which causes additional costs.

### 1.5.9 Fault tolerance and load balancing

As noted above, excessive power consumption causes the malfunction of nodes that lose their energies and becomes useless. Hence, the WSN must be fault tolerant. In this regard, fault-tolerant deployment strategies are used to prevent individual failures that minimize the overall network lifetime. Different deployment strategies can be used to make the network more fault-tolerant. Among others, the distribution of loads between nodes, the deployment of new nodes and the relocation of them. More details on the problem of fault tolerance are discussed in (Wang et al (2005).

### 1.5.10 Latency

Latency mainly concerns the delay in the aggregation, transmission or routing data. It is measured by the time elapsed between the departure of data packets from the source node and the arrival of these packets to the destination. Indeed, one of the causes of the emergence of latency is the use of alternative paths which are often longer than the main path. This leads to a higher consumption of energy. Moreover, some applications merge data to reduce the network traffic, which causes latency in the network.

## 1.6 Sensing models

In this section, we present the most important used detection models, their differences and their cases of use.

### 1.6.1 Binary model

In the binary model, the detection field of each node is considered as a circular area and a target can be either detected or undetected. In this model, there is no transition period and a slight displacement of the target may lead it to be outside the detection field. This model aims to simplify the analysis of detection. Unfortunately, it does not realistically reflect the detection capabilities of nodes. It only takes into consideration the distance between the sensor and the target. This model is illustrated in Figure 1.8.

<figure><img src="image_10.png" /><figcaption>Figure 1.8 Binary sensing model</figcaption></figure>

Mathematically, if the node S is at the location $(x_s, y_s)$, the detection field of S is a circular area of radius $R_s$ centered in $(x_s, y_s)$. In the binary model, S detects the target in its detection field with a probability of 1 because the distance between the target area and the node is less than $R_s$. It cannot detect this target outside its range detection (a probability of 0). Hence, the probability $P_{sb}$ of detecting a target T at the position $(x_t, y_t)$ by S in the binary model is as follows:

$$P_{sb} = \begin{cases} 1 & D_{TS} \le R_s \\ 0 & \text{Otherwise} \end{cases} \quad (1)$$

The distance between T and S, denoted $D_{TS}$, is calculated as follows:
$$D_{TS} = \sqrt{(x_s - x_t)^2 + (y_s - y_t)^2} \quad (2)$$

### 1.6.2 Probability model

In the probabilistic model, there is a transition period between the ability of a node to detect a target and its non-ability. Hence, the target is detectable with a probability that varies between 0 and 1. By deploying a WSN, the distance that separates the target to be monitored from the node and the characteristics of the node itself influence the perception of the node and its ability to detect the target. Indeed, the probability of detection of an event is inversely proportional to the distance separating the node from this event. However, in this model, the geometric distance is not the only factor used to determine the coverage. Other factors come into play such as noise, environment, interference, and signal attenuation (Wu et al., 2007). The probabilistic detection model, shown in Figure 1.9, reflects a concept of fuzzy coverage that represents a changing regularity of sensor detection capability.

<figure><img src="image_11.png" /><figcaption>Figure 1.9 Probability sensing model</figcaption></figure>

According to figure 1.9, we assume the existence of two critical distances for each node. A detection distance $R_s$ (same parameter as the binary model) where the target is detected with a probability of 1 if the distance between the target and the node is less than $R_s$. The second distance is $R_u$ which represents an uncertain detection range. The probability of detection of the target by the node depends on the distance that separates them if the distance between them is between $R_s$ and $R_s+R_u$. The target is not detectable by the node if the distance between the target and the node exceeds $R_s+R_u$. Mathematically, this probability can be defined as follows:

$$P_{sb} = \begin{cases} 1 & D_{TS} \le R_s \\ e^{-\lambda\alpha\beta} R_s < D_{TS} \le R_s + R_u & (3) \\ 0 & R_s + R_u < D_{TS} \end{cases}$$

Knowing that $a = D_{TS}-R_s$. $\lambda$ and $\beta$ are constants that depend on the sensors' hardware properties.

### 1.6.3 Tracking detection model

As an extension of the probabilistic model of event detection described in the previous section, Aitsaadi et al. (2011) proposed a new model that highlights the duration of the event. They assume that the probability of detection of an event is increased when this event occurs for a long time at the same point. This model is ideal in the case of a target tracking application. They propose a variable $t$ that quantifies the duration of an event at a specific point. Let $T$ be a period at the end of which the detection algorithm is executed and a decision is made if an event occurs. Hence, the probability of detection of this event will be calculated as follows:
$$P_p^s(t) = \begin{cases} P_p^s & \text{if } 0 < t \le T \\ 1 - [1 - P_p^s]^{l/T} & \text{if } t > T \end{cases} \quad (4)$$

### 1.6.4 Coverage and connectivity model

Coverage diagrams describe the topology of the sensor network to ensure perfect and optimal detection while connectivity schemes are related to the transmission and reception of messages in the network. According to (VAL, 1994), coverage and connectivity schemes include:

- "Connectivity-first" or "Guaranteed-connectivity" scheme (figure 1.10 (a)): it aims to guarantee connectivity. Thus, sensors are at a distance equal to $r_c$. According to (Wang et al, 2008), the efficiency of this deployment mode is guaranteed when $R_c \le \sqrt{3R_s}$, $R_c$ is the communication range and $R_s$ is the detection one.

- "Coverage-first" or "Guaranteed-Coverage" scheme (Figure 1.10 (b)): This deployment scheme tries to reduce the number of sensors by minimizing the intersections and overlaps of the coverage. In this scheme, nodes are at a distance of $\sqrt{3R_s}$. According to (Wang et al., 2008), the efficiency of this deployment mode is guaranteed when $R_c \ge \sqrt{3R_s}$.

- Hybrid coverage scheme: it is a combination of the two previous schemes. Coverage is guaranteed to a certain distance until it becomes probabilistic (Wu et al, 2007).

<figure><img src="image_12.png" /><figcaption>Figure 1.10 Guaranteed-connectivity scheme (a) and guaranteed-coverage scheme (b) (VAL, 1994)</figcaption></figure>

Other models exist such as the model that aims to ensure better energy consumption during detection or that which aims to extend the lifetime of the network.

## 1.7 Open deployment issues

Although many studies have been provided in the field of optimization of nodes positioning, various research challenges remain to be solved. In what follows, we identify open research problems in the 3D sensor deployment.

- **Underwater WSN**: is a network of sensors deployed under water. Underwater WSN are investigated by different studies BOUZOUALEGH et al. (2003), BOUZOUALEGH et al. (2005). Given the cost of installing these nodes, we must minimize their number. In order to communicate under water, these networks use acoustic waves that meet different issues such as fading signal, high latency, long propagation delay and limited bandwidth. The submarine nodes must be adapted to the extreme conditions of the environment and be self-configured. Batteries installed in these nodes must be energy efficient as they are non-replaceable and non-rechargeable. Different underwater applications can be considered, including earthquake and pollution monitoring, underwater exploration and disaster prevention. Indeed, deployment problems in underwater environments are quite different from those of the WSN. In this regard, the work of (Zhang et al, 2004) provides an overview of the latest developments in
submarine deployment algorithms. The authors categorize deployment algorithms into three
categories, based on the mobility of sensor nodes: static deployment, self-adjustment
deployment and assisted motion deployment. Future research problems with submarine
deployment algorithms may focus on the following ideas:

- How to design a mobility model that solves the problem of displacement of underwater sensors with water flow? This can make submarine deployment algorithms more efficient.

- Current deployment algorithms often deal with small scale networks while many monitored underwater areas are large scale. How to design failed node recovery mechanisms and deployment algorithms with a minimal number of redundant nodes that can be used to avoid network partitioning.

- To our knowledge, in order to extend the overall lifetime of a UASN network, little research has focused on the deployment of cyclical nodes dynamically working.

- Given the dynamism and complexity of underwater environments and the high cost of deploying submarine nodes, it is interesting to design efficient deployment algorithms for heterogeneous UASNs taking into account nodes with different ranges of communication and detection.

Figure 1.11 illustrates a deployment of an underwater WSN.

<figure><img src="image_13.png" /><figcaption>Figure 1.11 deployment of an underwater WSN (Jiang et al, 2016)</figcaption></figure>

- **Underground WSN**: is a network of sensors deployed in mines or caves to monitor underground events. To communicate data collected from underground nodes to the base station, additional sink nodes can be deployed above the ground. Because of the attenuation and signal loss, underground wireless networks are often more expensive than terrestrial ones because of the specific equipment used to ensure reliable communication across rocks and ground. Even more, as well as underwater networks, buried node batteries are often difficult to replace and recharge which require the design of deployment algorithms and communication protocols that are energy efficient. Different applications of underground networks can be cited such as military border surveillance, agriculture and minerals.

- **Multimedia WSN**: is a network of sensors deployed at low cost and equipped with microphones and cameras used to detect, store and process multimedia data such as audio, images or videos. When deploying such a network, different issues need to be considered, such as high power consumption, the need for different compression and data processing techniques and the demand for high bandwidth. Moreover, it is essential to guarantee a minimum quality of service to ensure the supply of reliable content. In general, multimedia networks are used to enhance existing WSN applications, such as monitoring and tracking.

- **Coordinated multi-node relocation**: Different contexts require that nodes coordinate between them to efficiently manage the application requirements while having the ability to synchronize inter-relocation (Younis and Akkaya, 2008) which is the case of the exploration of inaccessible fields or the detection of landmines.
**- Heterogeneity:** The majority of WSN studies assume that nodes are homogeneous. In this respect, and knowing the simplicity of collection networks in IoT, it is necessary to design and further study networks with heterogeneous nodes that can be simultaneously shared by several applications with conflicting objectives.

**- Simulation vs. real experimental deployment:** often, studies on node deployment are validated by performance analyzes that are based on simulations. The contribution of the simulation is that it is simpler and more controllable. However, it does not reflect the modeling of real application scenarios and may be less accurate than tests based on real prototypes. It is therefore attractive to design and implement real prototypes for the analysis of network performances under realistic experimental conditions and the real validation of the proposed models for deployment and coverage. Our contributions in this thesis are validated by real experiments. The results of these real experiments are then compared to simulations to draw more consistent and applicable findings in different contexts.

**- Mechanisms for detection and repair of coverage holes:** Despite the fact that different works have addressed the problems of connectivity and coverage, the issue of coverage holes has not been well highlighted. In this context, the problem of the coverage holes in the detection field is related to the deployment. Indeed, coverage holes are usually caused by failures of sensor nodes, by hostile environments (battle areas or volcanic regions) or by random deployment of stationary nodes in hybrid WSN composed of static and mobile nodes. Mobile sensor nodes are often added after the initial deployment to overcome the problem of coverage holes. However, because of the low power of mobile nodes, an effective management of their movements to maintain the network coverage and connectivity while minimizing the power consumption becomes a challenge. In this context, (Guvensan and Yavuz, 2011) solved the coverage problem in directional WSN. Indeed, directional nodes are often equipped with ultrasonic sensors, video sensors or infrared sensors. They differ from traditional omnidirectional nodes in different parameters such as viewing angle, direction of operation and field of view. (Guvensan and Yavuz, 2011) classify existing approaches solving the problem of coverage holes and determine their complexities, specificities and performances. They classify coverage optimization methods into four main classes: targeting-based, coverage-based, coverage guaranteeing connectivity-based and extending lifetime-based. They define the detection models, the challenges envisaged for DNS (Directional Sensor Networks) and their (dis)similarities to WSN. (Shen et al., 2013) develop an adaptive algorithm named AHCH (Adaptive Hole Connected Healing), to solve holes problems with the guarantee of network connectivity without the need to find new deployment schemes. Indeed, this algorithm adapts the existing deployment scheme to avoid coverage holes. To prove the effectiveness of this algorithm, authors compare, for different time intervals, the optimal solution with the estimation of the adaptive approximation ratio of this algorithm, with a complexity in $O(\log|M|)$, M is the number of mobile sensors. Then, they extend this algorithm in the general case by establishing two other versions to solve the same problem. The first version is InAHCH (Insufficient AHCH) which is used to solve the problem of holes if the number of mobile sensors is insufficient to guarantee the k-coverage for all the holes. The second version is GenAHCH (General AHCH) which is a generalization of the specific cases treated by the AHCH algorithm.

**- Three-dimensional node positioning:** The two-dimensional coverage problem has been solved in (Zhang et al., 2010) using an algorithm with a polynomial time in terms of the number of sensors. On the other hand, concerning the tridimensional problematic, it is much
more complicated to solve; and the use of random deployment is often inefficient in the case
of real 3D networks. Moreover, compared to 2D coverage, the complexity of 3D coverage
algorithms exponentially increases compared to the number of sensors (Zhang et al., 2010).
So far, most studies on node positioning strategies are limited to the two-dimensional
networks. Similarly for networks with multimedia applications, the focus has been on
coverage by managing the angular orientation of the nodes in a 2D plan. Indeed, most
deployment and coverage algorithms used in 2D spaces become NP-Hard in a three-
dimensional space (Akyildiz et al., 2007). Yet, with the emergence of WSN applications in
underwater and aerial surveillance, solving issues related to connectivity and 3D coverage has
become a necessity. Hence, sensor deployment optimization strategies in large-scale 3D WSN
applications is one of the most emerging research topics currently. In this thesis, we propose
to solve this problem using evolutionary optimization algorithms. In this regard, different
related works are detailed in section 1.11.

**1.8 Applications of the deployment**

Technological advances on the construction and manufacture of sensors have made them smaller, more affordable and more reliable which allowed broadening the range of targeted application areas. The integration of WSN technology in industry has improved the business performance. Still more experimental work is needed to increase the reliability and efficiency of real-world WSN use. Given the variety of sensors, the WSN fields of application are very varied. Generally, WSN applications concern the detection of an event or a phenomenon, taking periodic measurements (physical quantities), the detection of contours or the tracking of a moving target.

- **Ecological Applications:** Another use of WSN is optimizing the use and consumption of energy resources, such as a sensor incorporated into an air conditioning system in a building. Indeed, this network manages the air-conditioning according to the location of the individuals. The air conditioning trips only if it is necessary (when the sensor detects the existence of people in the RoI). This is the case for a heating, lighting or ventilation systems.

- **Traceability and localization applications:** WSN can be a major fault correction of Global Positioning System (GPS) systems which are high energy consumption. Indeed, people who ski can be equipped with sensors. These sensors will be handy to locate victims under snow in case of an avalanche. Several other traceability and localization applications with significant economic interests can be considered. Again, unlike location solutions that are based on GPS systems, WSN allow their deployment in enclosed areas such as mines or underwater areas (Baouche et al, 2009). Further investigations can be found in Fofana et al. (2016) and Van den Bossche et al. (2016).

- **Industrial applications:** The use of WSN in recent contexts is very beneficial since the use of a wireless network will significantly reduce the deployment and maintenance constraints. WSN can enhance manufacturing activities and it is ideal for any activity that requires fixed location and limited resources. Several other constraints and restrictions can be solved using WSN. Among others, weight restrictions (in an airplane for example) and mobility ones (tracking a moving target or detecting a robot movement). Among industrial WSN applications, we can mention the following ones:

- Surveillance and monitoring activities on hazardous conditions (radioactivity exposure, etc.).

- Monitoring polluted geographical areas or real-time monitoring of a contaminated area to draw a dynamic geographical map. As an example, we cite the OCARI (Open Communication protocol for Ad hoc Reliable industrial Instrumentation) project which is a
low-power wireless communication protocol based on the IEEE 802.15.4 standard. It was
initially developed by the ANR OCARI project funded by the French National Research
Agency.

- Monitoring the operation of machines.

- Logistics and inventory control.

- Process monitoring and Traffic monitoring.

- Preventive maintenance of equipment and structures.

- Supervision of foundations and buildings in civil engineering

- **Security applications:** WSNs have a beneficial use in the security field. Indeed, they can limit the financial expenses of securing structures. Among the WSN security applications:

* The deployment of sensors for detecting cracks and alterations in structures and buildings, following an earthquake or just to control its aging. This can anticipate the destruction of the structure.

* Monitoring of movements in a geographical area to set up a distributed system of intrusion detection. The distributed aspect of different systems makes it possible to cross it or put it in a state of dysfunction.

- **Environmental Applications:** To ensure broad coverage over a large geographic area, WSN can be used. We can cite several typical WSN environmental applications:

* Dissemination of temperature-sensitive sensors on a forest (deployment from an airplane) to detect the outbreak of fire.

* Controlling and managing the irrigation of green surfaces by detecting dry areas.

* The deployment of sensors on industrial sites, nuclear structures or oil refineries to capture and report the existence of leaks of toxic products (gases, chemicals, etc.) for rapid and effective intervention.

* The control of natural parks: sensors can be deployed to monitor animal movements and activities or to report and provide information on seasonal migrations of birds.

- **Medical and veterinary applications:** In medicine, WSN are generally used to monitor patients permanently. They are deployed to collect physiological data on vital functions such as heart rate, glucose level, respiration or blood pressure which facilitates the diagnosis of diseases and the monitoring of patients' health status. These sensors can be implanted under the skin or worn by the patient. As applications for this field we can mention:

* Micro-cameras are providing images of the interior of the body without performing a surgery operation.

* Biomedical micro-sensors forming an artificial retina to correct vision.

* Micro-sensor for the study of phonation.

* Early detector of cutaneous infection in peritoneal dialysis.

* Non-invasive micro-sensor for the study of the autonomic nervous system.

* Micro-sensors for the early detection of certain diseases such as cancer.

- **Military applications:** They were the first engine for the development of WSN. These applications take advantage of specific features of WSN such as easy deployment, fault tolerance and auto configuration. In military field, these networks are often deployed to monitor or analyze strategic areas, unattainable ones or those of the enemy to predict its activities and movements. Several other contexts of use can be found such as: Providing information regarding the loss or damage after a battle, monitoring the enemy equipment and ammunition, detecting chemical or nuclear attacks, etc.
For military applications, submarine deployment is one of the most interesting applications. Due to the complexity of the deployment environment in 3D spaces and the specific characteristics of underwater acoustic channel, many factors must be taken into consideration.

- **Commercial applications:** WSN can also be used in a commercial context. Indeed, sensors can control the operations of storage and delivery and provide (in real time) information about conditions, directions or positions of the goods. In addition, we can cite the WSN used to follow the production chains in factories and to control the entire production process.

- **Smart homes:** Another very practical WSN use is that of smart homes (Figure 1.12 (a)). Figure 1.12 (b) illustrates the intelligent home of the IUT of Blagnac in Toulouse in which our experiments are carried out. This application mostly targets people with disabilities or elderly to ensure their safety. Among the services offered in this context, the automatic control of doors and curtains (closing and opening), the control of household appliances (activation or shutdown), the triggering of the watering of plants in the garden or the management of air-conditioning and heating systems.

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /><figcaption>Figure 1.12 Smart homes</figcaption></figure>

Table 1 illustrates different recent deployment applications.

<table><caption>Table 1.1 Recent deployment applications</caption><thead><tr><td>Paper</td><td>Application(s)</td></tr></thead><tbody><tr><td>Qu (2013)</td><td>Mobile WSN, indoor surveillance applications</td></tr><tr><td>BOUSSAÏD (2013)</td><td>Signal detection<br>Segmentation of grayscale images by multi-level thresholding</td></tr><tr><td>Aitsaadi et al. (2011)</td><td>Image processing : 3D modeling</td></tr><tr><td>Guvensan et Yavuz (2011)</td><td>Directional WSN</td></tr><tr><td>(Han et al. 2013)</td><td>Acoustics WSN; submarines WSN</td></tr><tr><td>Ben Hadj et al. (2006)</td><td>Surveillance of the elderly persons and smart homes</td></tr><tr><td>Brinis and Saidane (2013)</td><td>Precision agriculture</td></tr></tbody></table>

# 1.9 Methodologies for solving the problem of deployment

## 1.9.1 Virtual Force algorithms

VFA (virtual force algorithms) are used to solve the problem of coverage and deployment of nodes. Different studies aim to resolve the deployment problem using VFA such as (Boufares et al., 2015). VFA consider nodes as a set of points that exert forces of attraction and repulsion between them. This calculated force permet to produce an acceleration allowing the nodes to
move. The authors in (Yu el al., 2013) solve the deployment problem in mobile sensor
networks using the *Van Der Waals* force. It relies on a friction force that is introduced into the
force equation using an adjacency based-on Delaunay-triangulation relationship between
nodes. To evaluate the uniformity of the node distribution, VFA use an evaluation metric
called the pairwise correlation function.

1.9.2 BDA, PFDA and DDA Algorithms

The study in (Ait Saadi 2010) aims to resolve the static deployment in WSN by optimizing
the quality of monitoring, the cost of deployment in terms of the number of nodes, the lifetime
and the connectivity of the network. They propose three approaches of approximate
resolution. The first approach is based on a Differentiated Deployment Algorithm (DDA).
The second approach is based on a Bernoulli deployment algorithm (BDA) that uses a
Bernoulli distribution which decides, in a probabilistic way, the addition or removal of a node
in the RoI. The third approach is based on a Potential Field Deployment Algorithm (PFDA)
which is a deterministic method based on virtual forces.

1.9.3 Heuristic optimization

A heuristic is an approximate method for solving an optimization problem. It is an algorithm
that aims to find a feasible solution while respecting a set of constraints and criteria without
guaranteeing optimality, but in a reasonable resolution time. In general, the heuristic methods
consist in exploring a search space to maximize or minimize a given objective function.
Different heuristic resolution methods are used depending on the complexity (in size and
structure) of the targeted search space. A small search space requires a deterministic method,
whereas a larger and complex search space requires an approximate research method (genetic
algorithm, simulated annealing ...). The heuristic solution is considered by a set of variables
(decision variables describing a system for example). These variables are defined on
continuous or discrete domains. If it is a discrete domain, then we speak of combinatorial
optimization and the set of solutions is enumerable. If some variables are related to each
other, we talk about continuous optimization. Scheduling problems are part of constrained
combinatorial optimization problems. In terms of complexity, the majority of scheduling
problems are NP-hard. Indeed, one of the solutions to solve them is to develop heuristics that
provide feasible scheduling in a reasonable time with a duration close to that of an optimal
scheduling. The study in (Zhang et al., 2014) proposes a deployment based on swarm
intelligence algorithms such as the particle swarm optimization algorithm, the bee algorithm
and the ant colony algorithm. They discuss the issues of self-organized networks at the
physical, MAC and network layers.

1.10 Other problems similar to the node positioning problem

Having similar constraints and issues, several problems can be compared to the 3D indoor
deployment. Among others, the following problems can be envisaged:

1.10.1 Set MultiCover Problem

The Set MultiCover Problem (SMCP) is a generalization of the Set Cover Problem in which
each element *i* must be covered by a minimum number of sets *ri*. This constatation involves
covering all elements while minimizing costs (Fujito and Kurahashi, 2006). The SMCP
problem can be reduced to a PP (Positioning Problem) as follows: Given an instance of the
SMCP problem, we can build an instance of the PP such that an optimal solution of the PP is
also an optimal solution of the SMCP.
### 1.10.2 Art Gallery Problem

There is also a great resemblance between the problem of sensor positioning and the problem of the Art Gallery Problem (AGP). The AGP has been defined and treated by (O'Rourke et al, 1987) which involves placing agents or surveillance cameras in an art gallery represented by a non-convex polygon of $n$ vertices in such a way that each point of the gallery is visible to at least one agent or camera. The AGP problem has been solved for a 2D surface and has been demonstrated to be NP-hard for a 3D surface. Different variants of the AGP problem have been studied. An interesting version of the AGP problem is that after a random initial deployment, how agents move so that each point is visible to at least one agent, this is the Distributed Art Gallery Deployment Problem. However, in some positioning problems, the sensors can be heterogeneous unlike the AGP problem where cameras have the same characteristics. Cardei and Wu (2006) study the problem of energy optimization for the coverage problem in WSN. They detail the WSN design factors and present coverage issues similar to those of coverage in WSN. They are particularly interested in AGP, Ocean Coverage and Robotic Systems Coverage. The addressed energy optimization issues are either based on energy efficient area coverage or on energy efficient point coverage.

### 1.10.3 Other similar problems

A set of academic problems has a close relationship with the problem of sensor deployment. For example, the problem of warehouse location which consists of setting up a set of warehouses to serve a certain number of demand points while minimizing costs. The k-center problem is one of the problems of warehouse localization and more specifically of the minimax location-allocation type (Hale and Moberg, 2003). Many works have concentrated on studying different versions and their complexity. The k-center problem defines an objective function of minimizing the maximum distance between a demand point and the nearest warehouse. The decision version of this problem is that of determining whether a set of request points can be covered by k centers at a distance equal to r. Another similar problem is that of k-median. Formulated by Hakimi in 1964, the k-median problem is one of the minimum localization-allocation problems (Hale and Moberg, 2003). It is a question of determining k centers among a set of n centers such that the sum of the distances between each point of the request and the nearest center is minimum.

## 1.11 Comparison and review of recent studies on WSN deployment

In literature, different works aim at resolving the problem of deploying sensors in WSN exist. Table 2 illustrates a comparison between the recent optimization approaches used to resolve the deployment problem in WSN.

<table><caption>Table 1.2 Comparisons between recent works resolving the deployment problem in WSN</caption><thead><tr><td>Paper</td><td>Application</td><td>Space</td><td>Sensing model</td><td>Contribution / Approach</td><td>Objective(s)</td><td>Disadvantage(s)</td></tr></thead><tbody><tr><td>Konstantinidis et al. (2010)</td><td>Power assignment and deployment problem</td><td>2D</td><td>Deterministic</td><td>A modified MOEA/D algorithm</td><td>Maximize the coverage and the lifetime</td><td>The performance of the MOEA/D is compared with only one algorithm (the standard NSGA-II) which does not give a sufficient idea about the effectiveness of the proposed approach compared with other ones.</td></tr><tr><td>Banimelhem et al. (2013)</td><td>The problem of coverage holes</td><td>2D</td><td>Deterministic</td><td>Genetic Algorithm</td><td>Minimum number and best locations of mobile nodes</td><td>No mathematical modeling is given</td></tr><tr><td>Aval et al. (2012)</td><td>A survey</td><td>2D</td><td>Deterministic</td><td>Multi-objective methodologies: genetic algorithms and particle swarms</td><td>Coverage, connectivity, cost and lifetime</td><td>No simulations (or experimental studies) are given to compare the proposed approaches</td></tr><tr><td>Qu (2013)</td><td>Redeployment</td><td>2D</td><td>Deterministic</td><td>Centralized optimization algorithms: GA and PSO</td><td>Maximize the detection range and minimize the energy consumption.</td><td>The standard versions of the proposed algorithms are tested, with enhancements only on the problem assumptions. Moreover, it would be</td></tr></tbody></table>
Chapter 1. 3D indoor deployment problem in WSN and DL-IoT collection networks

<table><tr><td>Kang and Chen (2009)</td><td>3D Differentiated WSN deployment problem</td><td>3D</td><td>Deterministic</td><td>A force-driven strategy based on a multi-objective genetic algorithm</td><td>Coverage, energy conservation, detection levels</td><td>A local optimum can be given by the proposed algorithm as a final solution because of the simple proposed mutation operator</td></tr><tr><td>Topcuoglu et al. (2011)</td><td>Deploy multiple sensors on synthetically generated 3D terrains</td><td>3D</td><td>Deterministic</td><td>Hybrid evolutionary algorithm (three crossover operators+ a local-search phase)</td><td>Maximize visibility<br>Maximize stealth<br>Minimize cost</td><td>Authors do not treat in this work, the 3D WSN deployment issues with unusual detection levels that require a number of nodes that exceeds the usual detection level</td></tr><tr><td>Unaldi et al. (2012)</td><td>3D terrains</td><td>3D</td><td>Probabilistic</td><td>Random walk mutation + guided wavelet transform (WT)</td><td>Maximize the quality of the coverage, minimize the number of sensors</td><td>The proposed method is not evaluated in dynamic environments and using mobile sensors. Moreover, it is not proved by empirical real-world scenarios</td></tr><tr><td>Danping et al. (2013)</td><td>Signal and radio propagation modeling indoor and outdoor 3D scenarios</td><td>3D</td><td>Deterministic</td><td>3D multi-objective evolutionary algorithm+ a low cost heuristic</td><td>link quality, coverage, lifetime and cost of hardware</td><td>The scalability of the used algorithm is not proved</td></tr><tr><td>Matsuo et al. (2013)</td><td>Radio propagation model in the disaster area</td><td>3D</td><td>Deterministic</td><td>Genetic algorithm + Local search</td><td>Maximize k-coverage, Minimize the number of deployed nodes</td><td>The proposed algorithm is not evaluated by the known metrics (Hypervolume, Inverted Generational Distance).</td></tr><tr><td>Xu et al. (2014)</td><td>Deploy indoor wireless antenna with obstacles</td><td>3D</td><td>Deterministic</td><td>Mathematical morphology strategy</td><td>Optimize the number of and locations of indoor antennas, maximize the coverage.</td><td>Directed antennas are not taken into consideration</td></tr><tr><td>Ko and Gagnon (2015)</td><td>3D irregular terrains</td><td>3D</td><td>Deterministic</td><td>A parsing crossover strategy for the genetic algorithm</td><td>Maximize the probabilistic coverage on a point and the global coverage</td><td>Authors do not prove that the proposed parsing crossover scheme can be a full remedy when GA approach fails</td></tr><tr><td>Jiang et al. (2016)</td><td>Thermal Sensor Placement in Smart Grid</td><td>2D</td><td>Stochastic</td><td>A genetic approach based on a Gappy proper orthogonal decomposition (GPOD-GA)</td><td>Minimize the thermal sensor number</td><td>A single objective is considered. No evaluation of the proposed approach using known metrics.</td></tr><tr><td>Alia and Al-Ajouri (2017)</td><td>No application is given</td><td>2D</td><td>Deterministic</td><td>harmony search-based algorithm</td><td>Maximizing the coverage, maximizing the deployed sensor number</td><td>A simple model of the network. A bi-objective model: only two objectives are considered. No simulator is used: only Matlab results are presented</td></tr><tr><td>Sweidan and Havens (2016)</td><td>Terrain-Aware Wireless Sensor Networks</td><td>2D</td><td>Deterministic</td><td>Normalized Genetic approach (NGA), Artificial Immune System (AIS) approach and Particle Swarm Optimization (PSO) based approach</td><td>Minimize the cost of mobility and maximize the coverage</td><td>The high execution time of the proposed AIS and NGA.</td></tr><tr><td>Enayatifar et al. (2014)</td><td>A simulation scenario for the deployment of sensors</td><td>2D</td><td>Deterministic</td><td>A new algorithm: objective Imperialist Competitive Algorithm (MOICA).</td><td>Minimizing the number of deployed nodes<br>Maximizing the coverage.</td><td>No real experimentations<br>The comparison with other approaches is not based on known metrics (such as hypervolume and IGD).</td></tr><tr><td>Zainol Abidin et al. (2014)</td><td>A simulation scenario for the deployment of sensors</td><td>2D</td><td>Deterministic</td><td>A new algorithm: multi-objective territorial predator scent marking algorithm (MOTPSMA).</td><td>Maximizing the coverage and the connectivity.<br>Minimizing the consumed energy.</td><td>No real experimentations (using testbeds), even the simulations are performed using Matlab, not a dedicated simulator for wireless networks.<br>No comparison of the new approach with other known metaheuristics.</td></tr><tr><td>Cao et al. (2018)</td><td>monitoring maritime environments</td><td>3D</td><td>3D uncertain coverage model</td><td>distributed parallel cooperative co-evolutionary multi-objective largescale evolutionary algorithm</td><td>Maximizing coverage, lifetime and reliability</td><td>the parallelism of the proposed algorithm can be further improved through implementation on GPUs or MICs.</td></tr><tr><td>Liu and Ouyang (2018)</td><td>Heterogeneous Camera Sensor</td><td>3D</td><td>probabilistic sector-disk</td><td>A mathematical k-coverage estimation</td><td>Maximizing k-coverage</td><td>A solid modeling but no real experiments</td></tr></table>
Chapter 1. 3D indoor deployment problem in WSN and DL-IoT collection networks

<table><thead><tr><th></th><th>Networks</th><th>region</th><th>expression</th><th></th><th></th></tr></thead><tbody><tr><td>Khalfallah et al. (2017)</td><td>3D Underwater WSN Deployment in Rivers</td><td>3D</td><td>probabilistic<br>a novel deployment heuristic (3D-UWSN-Deploy) based on subcube tessellation and a mixed ILP optimization</td><td>Maximizing Full-Coverage Connectivity, and Quality of Monitoring</td><td>The choice of the values of simulation parameters is not justified. Performance metrics are not the standards known ones. Comparison with exact methods.</td></tr><tr><td>Brown et al. (2016)</td><td>Wireless Video Sensor Network</td><td>3D</td><td>Deterministic<br>a greedy heuristic and an enhanced Depth First Search (DFS) algorithm</td><td>Maximizing the 3D indoor space coverage</td><td>No comparison with other methods<br>Only one objective is considered (the coverage)<br>Video security is not considered</td></tr><tr><td>Wu and Wang (2017)</td><td></td><td>3D</td><td>probabilistic sensing<br>An approximation greedy discretization approach</td><td>Maximizing the k-coverage and connectivity</td><td>Simplistic Problem Formulation<br>Small-scale problem<br>Instances<br>Comparison with the standard GA</td></tr></tbody></table>

Among the main drawbacks of these studies, the non-consideration of the many-objective case of the problem. Even more, the majority of these studies did not test the proposed approaches on real-world problems which are more complicated. Hence the proposed contributions in this thesis.

1.12 Conclusion

In this chapter, we presented the issues of three-dimensional deployment and its different types, objectives, models and applications. A set of problems which are similar to ours was detailed. Then recent research works dealing with the problem of deployment were identified and criticized. The next chapter will describe the different approaches used to solve the three-dimensional deployment, especially the evolutionary optimization algorithms, the multi-agent systems and the concepts of incorporation of dimensionality reduction and user preferences.
Chapter 2

Optimization methods and multi-agent systems for solving many-objective problems

<table><tr><td>2.1 Introduction</td><td>31</td></tr><tr><td>2.2 Combinatorial optimization</td><td>31</td></tr><tr><td>2.2.1 Complexity of a problem</td><td>31</td></tr><tr><td>2.2.2 Classification of optimization problems</td><td>31</td></tr><tr><td>2.3 Multi-objective optimization</td><td>32</td></tr><tr><td>2.3.1 Pareto Optimality Concepts</td><td>33</td></tr><tr><td>* Notion of dominance</td><td>33</td></tr><tr><td>* Concept of optimality</td><td>33</td></tr><tr><td>* Pareto Front</td><td>33</td></tr><tr><td>* Concept of dominance with constraints</td><td>33</td></tr><tr><td>* Optimum in the sense of Pareto</td><td>34</td></tr><tr><td>2.3.2 Approaches to solve multi-objective optimization problems</td><td>34</td></tr><tr><td>2.3.2.1 Transformation of a multi-objective problem into a single objective problem</td><td>34</td></tr><tr><td>2.3.2.2 Non-Pareto approaches (non-aggregated)</td><td>36</td></tr><tr><td>2.3.2.3 Pareto approach</td><td>37</td></tr><tr><td>2.4 Methods for solving a multi-objective optimization problem</td><td>37</td></tr><tr><td>2.4.1 Exact methods</td><td>37</td></tr><tr><td>* Branch and Bound</td><td>37</td></tr><tr><td>* Dynamic programming</td><td>37</td></tr><tr><td>2.4.2 Meta-heuristics</td><td>38</td></tr><tr><td>2.4.2.1 Taboo Search (TS) / Simulated Annealing (SA)</td><td>38</td></tr><tr><td>2.4.2.2 Swarm Intelligence (ACO, PSO, BSO)</td><td>39</td></tr><tr><td>2.4.2.3 Genetic algorithms (NSGA-II as an example)</td><td>43</td></tr><tr><td>2.4.3 Many-objective optimization</td><td>46</td></tr><tr><td>2.4.3.2 NSGA-III algorithm</td><td>47</td></tr><tr><td>2.4.3.3 MOEA/DD</td><td>48</td></tr><tr><td>2.4.3.4 Two_Arch2 algorithm</td><td>48</td></tr><tr><td>2.4.3.5 Similitudes and differences between many-objective algorithms</td><td>49</td></tr><tr><td>2.4.3.6 Difficulties in MaOAs</td><td>50</td></tr><tr><td>2.4.4 Hybridization of Meta-heuristics</td><td>51</td></tr><tr><td>2.4.4.1 Hybridization between metaheuristics</td><td>51</td></tr><tr><td>2.4.4.2 Hybridization of Meta-heuristics and Exact Methods</td><td>52</td></tr><tr><td>2.5 Multi-agent Systems</td><td>53</td></tr><tr><td>2.5.1 Notion of Distributed Artificial Intelligence</td><td>53</td></tr><tr><td>2.5.2 Concept of agent</td><td>53</td></tr><tr><td>2.5.3 Multi-agents systems</td><td>54</td></tr><tr><td>2.5.4 Agents types</td><td>55</td></tr><tr><td>2.5.5 Software platforms for MAS</td><td>55</td></tr><tr><td>2.5.6 Applications of MAS in WSN</td><td>56</td></tr><tr><td>2.6 Preferences incorporation</td><td>56</td></tr><tr><td>2.6.1 Generalities</td><td>56</td></tr><tr><td>2.6.2 Interactive preferences (PI-EMO-PC)</td><td>57</td></tr><tr><td>2.7 Dimensionality reduction</td><td>58</td></tr><tr><td>2.7.1 Generalities</td><td>58</td></tr><tr><td>2.7.2 Offline correlation reduction methods based on machine learning for the 3D deployment problem</td><td>59</td></tr><tr><td>2.8 Conclusion</td><td>59</td></tr></table>
## 2.1 Introduction

In the real world, especially in industrial fields such as telecommunication, chemistry, transportation, and mechanics, the problems are complex and have a large scale. This makes them difficult to solve, although they are often easy to define. Optimization, which represents a crucial part of operational research deals with this type of problems. Indeed, most of these problems belong to the class of NP-hard problems and so do not have any efficient and valid algorithmic solutions for all data. In the literature, several studies were interested in solving optimization problems, especially in industrial fields (Khemiri et al., 2017), (Kadri et al., 2014). Optimization problems are divided into two groups: single-objective problems and multi-objective ones. Single objective problems rarely exist in real-world applications. However, multi-objective problems; generally characterized by different conflictual criteria to be simultaneously satisfied; represent a majority of real situations. Whether it is mono-objective or multi-objective, an optimization problem can be classified into one of two categories: a problem having a real-time variable solution also called continuous optimization problem or a problem with a discrete variable solution. Combinatorial optimization is an intermediate type between continuous and discrete optimization. When the problem is multi-objective, it is named multi-objective combinatorial optimization. In what follows in this chapter, we present the different types of combinatorial optimization, multi-objective optimization and its resolution methods. Then, we detail MAS and other processes such as user preferences and dimensionality reduction.

## 2.2 Combinatorial optimization

A combinatorial optimization problem is defined by a set of instances where each instance associates a discrete set of solutions $S$ composed by a subset of admissible (feasible) solutions $X$ and a cost function $f$ (objective function) that associates with each solution $s \in X$ a real number $f(s)$ representing its cost. Solving a combinatorial optimization problem involves finding a solution $s^*$ belonging to $X$ to optimize the cost function $f$. $s^*$ is called an optimal solution or global optimum. (Papadimitriou and Steiglitz, 1982) proposed the following definition for a combinatorial optimization problem: An instance $I$ of a minimization problem is a pair $(X, f)$ where $X \subset S$ is a finite set of solutions eligible and $f$ a cost (or objective) function to be minimized. The problem is to find $s^* \in X$ such that $f(s^*) \le f(s) \ \forall s \in X$. Similarly, the problem of maximization can be defined by changing $\le$ by $\ge$.

### 2.2.1 Complexity of a problem

The complexity of an algorithm is the necessary time and memory space for its execution. It is computed according to the number $N$. $N$ is the number of data also called the size of the problem (Carlier and Pinson, 1989). In the worst case, the complexity theory increases the number of operations required by a function having the size $N$ of the problem. The complexity of an algorithm is $f(N)$ denoted $O(f(N))$, if it $\exists$ a constant $C$ and an integer $A$, such that the number of elementary instructions $I(N)$ satisfy $I(N) \le Cf(N)$ for all $N \ge A$. If $f(N)$ is polynomial then the algorithm is polynomial (Farreny and Ghallab, 1987).

### 2.2.2 Classification of optimization problems

Independently from the degree of difficulty of the optimization problem, its resolution requires, first of all, its classification with respect to existing problems in the literature. This classification is not just a way to show the importance of the problem but also to facilitate its resolution by making analogies compared to another existing problem for example. The industrial domain is full of different types of problems which can be grouped into two main classes: The decision problems characterized by a solution reduced to a simple "yes" or "no" answer, and the optimization problems with a permissible solution that must be constructed by minimizing or maximizing the objective function. Another particular type of problem,
called undecidable problems, exists. It is the most difficult to resolve and generally with no method of resolution. Although this classification shows independence between these two types of problems, the literature shows an active link between decision problems and optimization problems. Solving a problem which aims to minimize or maximize the value of the objective function, requires indirectly the resolution of a decision problem which consists in studying the existence or not of an optimal admissible solution. Inversely, the study of the complexity of a decision problem allows giving indications of the associated optimization problems (Charon et al., 1996). Generally, any decision or optimization problem must belong to one of the following three classes:

* **P-Class problems:** Any problem belonging to this class must be a decision problem and should have at least one polynomial algorithm as a method of resolution. This class is named easy or P-class. The verification of the existence of such an algorithm is mandatory to show the belonging of the problem to this class.

* **NP-class problem:** The problems belonging to this type of class, called NP difficult problems, cannot be solved in a polynomial time. The resolution methods used are the heuristics that allow to find an optimal solution but not demonstrable. P-class problems can be solved by conventional or exact algorithms that are included in the family of heuristics. Subsequently, the P class is included in the NP class.

* **NP-Complete Class Problem:** A decision problem P is said NP-complete if it belongs to the class NP and if we have the following properties for any problem P' of NP:

- There is a polynomial application that transforms any instance I' of P' into an instance I of P.

- P' admits a 'yes' answer for the instance I', if and only if P admits a 'yes' answer for the instance I.

A general property of complete NP problems is as follows: If only one NP-complete problem is polynomial, then all NP-complete problems are polynomial. If the problem is NP-hard, there is no polynomial algorithm solving it (Esquirol and Lopez, 2001).

## 2.3 Multi-objective optimization

The origin of multi-objective optimization dates back to the 19th century. Firstly, it has been applied in the fields of management and economy by Edgeworth and Pareto in the 1980s; then it was extended to engineering sciences in the 1990s. The researchers were initially interested in bi-objective issues. To solve this type of problem, they used methods such as Branch and Bound (Sen et al., 1988), A* algorithm (Stewart and White, 1991) and linear programming (White D., 1982). Different studies have shown the effectiveness of these methods for small size problems, but also their inefficiencies for large size or multicriteria problems. The complexity of the latter type of problems becomes greater. Given the lack of adequate and efficient methods to resolve these problems, different meta-heuristics have been proposed as approaches. Unlike single-objective optimization, which consists of finding a unique solution, multi-objective optimization allows finding a set of solutions that represents all the Pareto optimal solutions.

**Définition:** An optimization problem consists of searching for the maximum or minimum value, called global optimum, of a function $F: S \to R$ called the *objective function*. For a multi-objective problem, we minimize or maximize a vector of functions where each component represents an objective function. A multi-objective problem can be defined as follows:

$$ \text{PMO} \quad \begin{cases} \min F(x) = (f_1(x), f_2(x), \dots, f_n(x), n \ge 2) \text{ is the number of objective functions} \\ \text{s.c } x \in C \end{cases} $$

$x = \{x_1, x_2, \dots, x_k\}$ is the vector representing the decision variables, C represents the set of feasible solutions associated with constraints of equality, inequality and explicit bounds
(decision space). $F(x) = (f_1(x), f_2(x), ..., f_n(x))$ is the vector of criteria to be optimized (in minimization or in maximization). The solution of a multi-objective optimization problem is a set of non-dominated solutions known as the set of optimal Pareto solutions (PO).

### 2.3.1 Pareto Optimality Concepts

**\* Notion of dominance**

Let $x$ be a potential solution to the multi-objective problem, $x \in A$ dominates $x' \in A$ if, and only if, $\forall i f_i(x) \le f_i(x')$ with at least $i$ such that $f_i(x) \le f_i(x')$. A solution $x$ is said weakly not dominated, if there is no solution $x' \in A$ such that $f_i(x') \le f_i(x)$ with at least $i$ such that $f_i(x) < f_i(x)$ where $i = 1, ..., n$ is the number of objectives. Figure 2.1 illustrates examples of dominance.

<figure><img src="image_16.png" /><figcaption>Figure 2.1 Example of dominance</figcaption></figure>

The functions $f_1$ and $f_2$ are two functions to be minimized; solutions 1, 4 and 5 are not dominated by any other solution while solutions 2 and 3 are dominated by solution 4.

**\* Concept of optimality**

A solution $x^* \in C$ is Pareto optimal (or effective, or not dominated) if and only if, there is no solution $x \in C$ such that $x$ dominates $x^*$. A solution $y = (y_1, y_2, ..., y_k)$ is said to dominate a solution $z = (z_1, z_2, ..., z_k)$ in the case of a minimization of objectives if, and only if $\forall i \in [1..n]$, $f_i(y) \le f_i(z)$ et $\exists i \in [1..n]$ such that $f_i(y) \le f_i(z)$. Thus, any solution of the Pareto set can be considered optimal since no improvement cannot be made on one objective without degrading the relative value of another objective. These solutions compose the Pareto front.

**\* Pareto Front**

The Pareto front is the set of optimal Pareto points. For the previous example in Figure 2.1, the Pareto front is composed of the points 1, 4 and 5. Figure 2.2 illustrates an example of a Pareto front for a bi-objective problem. A is the feasible domain.

<figure><img src="image_17.png" /><figcaption>Figure 2.2 Pareto front for a bi-objective problem</figcaption></figure>

**\* Concept of dominance with constraints**

A solution $i$ dominate a solution $j$ when one of the following situations occurs:

- The solution $i$ is feasible while the solution $j$ is not.

- Both solutions are possible and the solution $i$ dominates the solution $j$.
- The two solutions are not feasible, but the solution *i* has a number of violations of the constraints lower than that of *j*.

**\* Optimum in the sense of Pareto**

In a multi-objective problem, there is a balance which consists in saying that we cannot improve a criterion without damaging at least one of the others. This balance is called the Pareto optimum. A solution *x* is called Pareto optimal if it is not dominated by any other solution belonging to the search space. Optimal Pareto solutions are called non-dominated solutions or non-inferior solutions.

**2.3.2 Approaches to solve multi-objective optimization problems**

In order to solve a multi-objective optimization problem, a set of Pareto solutions must be determined. However, the resolution requires, as a first step, the choice of the right method. A first classification consists in grouping the resolution methods in three families according to the preferences of the DM and the degree and time of his intervention: a priori, progressive and a posteriori optimization method. Another more interesting classification of the multi-objective optimization problem is based on three classes as follows: the first class concerns approaches that are based on the transformation of a multi-objective problem into a single-objective problem, the second class is based on non-Pareto approaches and the third-class concerns Pareto approaches. Figure 2.5, shown below, presents a classification of the different methods and approaches solving multi-objective problems (Talbi, 1999).

**2.3.2.1 Transformation of a multi-objective problem into a single objective problem**

This approach is based on the transformation of a multi-objective problem into a single-objective problem. Among these methods of resolution: the aggregation method, the ε-constraints method and the goal programming method (global programming) (Hwang and Masud, 1979).

**a. Aggregation method:** This is one of the first methods used to solve multi-objective problems. It consists in lineary combining several criteria *fi* of the problem into a single criterion *F*. $F(x) = \sum_{i=1}^{n} a_i f_i(x)$ knowing that $a_i \ge 0$ are the weights assigned to the criteria, *x* is the parameter vector of the objective function $\sum_{i=1}^{n} a_i = 1$ and *n* is the number of criteria. The values of $\alpha_i$ will be the components of the vector weight which will be represented by the hyperplane in the space objective (a straight line for a bi-objective problem) with a fixed orientation. The optimal Pareto solution is the point where the hyperplane has a common tangent with the realizable space (the point *x* in Figure 2.3).

<figure><img src="image_18.png" /><figcaption>Figure 2.3 Pareto Solutions</figcaption></figure>

The choice of $\alpha_i$ values is crucial because it strongly influences the problem resolution results. This step is sensible because these values depend on the decision maker's (DM) preferences. One of the approaches to have good values of $\alpha_i$ is to solve the problem with several $\alpha_i$ values.
Several "Blind" strategies can be used to generate the weights. In (Veldhuizen et al. 1997), weights are randomly generated: $w_i = (random_i / random_i + random_i + ... + random_n)$, $i=1, 2, ... n$ where random_i variables are positive integers. The different objectives are generally evaluated in different scales. Standardization of the objectives values is necessary to have an equation with variables in the same scale. Thus, F becomes as follows: $F(x) = \sum_{i=1}^{n} c_i a_i f_i(x)$ where $c_i$ are constants that put the different objectives on the same scale. $c_i$ are usually initialized to $1/f_i(x^*)$, where $f_i(x^*)$ is the optimal solution associated with the objective function $f_i$. In this case, the vector is normalized with respect to the ideal vector.

Although the found solutions may not be acceptable especially if the space of research is prematurely reduced, this approach has some advantages such as determining a single solution and the no need to interact with the DM (except for weight values requiring the knowledge of the addressed problem by the DM).

**b. ε-constraint method:** The ε-constraint method is based on the optimization of an objective function $f_k$ whose constraints are in function of the constraints of the other functions i # j.

$$ \begin{cases} \min f_k(x) \\ x \in C \quad \text{où } \varepsilon = (\varepsilon_1, \dots, \varepsilon_{k-1}, \varepsilon_{k+1}, \dots, \varepsilon_n) \\ \text{s.c } f_j(x) \le \varepsilon_j, \quad j=1, \dots, n, \quad j \ne k \end{cases} $$

Several optimal Pareto solutions can be generated by modifying the values of the variable $\varepsilon_i$. This requires a priori knowledge of the appropriate intervals for the $\varepsilon_i$ values for all objectives. The ideal vector must be calculated to determine the lower bounds. Hence we have: $\varepsilon_i \ge f_i(x^*$), $i = 1, 2, k-1, k+1, n$.

The example in Figure 2.4 shows a comparison between the original objective space $F(C)$ of a bi-maximization problem and the restricted space $F(C')$ by the ε-constraint transformation. The objective functions $f_i$ can be classified in order of priority following the lexicographic order of the indices of these functions. Therefore, the function $f_1$ is more priority than $f_2$. This approach has been applied to several meta-heuristics such as genetic algorithm (Ritzel et al., 1994), (Hertz et al., 1994) and taboo research (Wienke et al., 1992). In general, this method generates weak Pareto optimal solutions. However, if the optimal solution is unique, then the found solution becomes strongly Pareto optimal. Generating multiple solutions requires running the algorithm multiple times (with different constraints), which is high-cost computing time.

<figure><img src="image_19.png" /><figcaption>Figure 2.4 ε-constraint method</figcaption></figure>

**c. Goal Programming Method:** It consists in defining the goals presented by a priori values for the objectives to be achieved. These values will be used to transform the multi-objective problem into a single-objective one.
$$ \begin{cases} \min & \left( \sum_{j=1}^{n} \lambda_j |f_j(x) - z_j|^p \right)^{1/p} \\ \text{s.c} & x \in C \end{cases} $$

Where z is the reference vector (goal) or the ideal vector and $1 \le p \le \infty$. The used norm is the metric of Chebysheff (Lp-metric). Generally, if p is equal to 2, we have a Euclidean metric. If p = ∞, the equation comes back to a Min-Max function. An arbitrary selection of the reference vector may be a wrong choice of the reference vector because it can lead to a solution that is not Pareto optimal. This approach has been applied to several meta-heuristics such as genetic algorithms (Coello, 1998) (Serafini, 1992). Simulated Annealing (Gandibleux et al., 1996) and taboo search (Collette and Siarry, 2002).

Figure 2.5 shows a classification of multi-objective optimization methods.

<figure><img src="image_20.png" /><figcaption>Figure 2.5 Classification of multi-objective optimization methods (Talbi, 1999)</figcaption></figure>

### 2.3.2.2 Non-Pareto approaches (non-aggregated)

Methods based on this approach treat the objectives separately. We can distinguish three groups of processes:

**a. Lexicographic selection:** The selection is carried out using an order which is defined a priori by the DM according to the importance of the objectives. This order allows determining the weight of the objectives. Many heuristics are based on this approach such as the genetic algorithm. A lexicographical approach was proposed in (Kursawe, 1991). This approach compares the individuals according to a randomly chosen objective based on a predetermined probability.

**b. Parallel selection:** The VEGA method proposed in (Schaffer, 1985) consists in selecting the Pareto Front solutions following each objective independently from other objectives. The principle of the algorithm consists of dividing the population into n subpopulations knowing that n is the number of objectives. Each subpopulation i is selected according to the objective i. The analysis of this algorithm showed that its behavior is the same as an algorithm performing a linear aggregation (Richardson et al., 1989).

**c. Multi-Sexual Reproduction:** As proposed in (Allenson, 1992), the principle of this method is to associate with each class of individuals an objective using a bijective function. Each class of individuals is identified by a different gender. An individual of a given gender is evaluated according to the associated objective function of its gender. At the creation of an
individual, its gender is randomly choosen and assigned. An individual can be of male or
female. Reproduction can only be between a male individual and a female individual. At the
initialization of the population, the number of male and female individuals is equal. For
the next generations, Evolutionary algorithms can be used to implement a form of sexual
attractors. This method allows defining subpopulations separated by objectives. Parallel
selection and lexicographic selection differ in the multi-sexual reproduction by the
neighborhood restriction. This latter is used in the *lexicographic selection* to avoid the random
reproduction of individuals.

### 2.3.2.3 Pareto approach

Unlike other approaches combining criteria and treating them separately, the Pareto approach uses the concept of dominance to select solutions that allow the population to converge towards a set of efficient solutions. These methods allow having a set of possible Pareto solutions of the problem, but do not allow comparing solutions. The choice of the final solution is decided by the user (DM).

## 2.4 Methods for solving multi-objective optimization problems

The choice of a resolution method for a multi-objective problem necessarily depends on the complexity of the problem as well as its size. A simple small-size optimization problem can be solved using an exact method having a reasonable execution time. However, for difficult large-size problems, the exact methods are not efficient. Then, meta-heuristics become the most appropriate. Although the meta-heuristic is approximate (and not optimum), its execution time is reasonable and favors its choice for difficult and complex problems.

### 2.4.1 Exact methods

For large size problems, the calculation time becomes unreasonable. Exact methods provide optimal solutions only for small size problems. Among these methods, the Branch and Bound which is the most used.

* Branch and Bound

This method provides solutions by exploring a search tree describing all the possible solutions. It consists of finding the best configuration to avoid (to prune) the branches of the tree that lead to inadequate solutions. To find the best solution, the Branch and Bound algorithm performs a full search in a given problem space. The steps of the Branch and Bound algorithm are as follows:

1. Divide the search space into a set of subspaces.

2. Find a minimum bound for each objective function associated with each sub-search space.

3. Eliminate bad spaces.

4. Reproduce the previous steps until reaching the global optimum.

(Lin, 2015) suggests a branch and bound algorithm to resolve the problem of deployment of smart gateway in smart home environments. This study investigates the connections between the different devices in the network and its applications in the systems of home automation. The aim is to minimize the cost of deployment while achieving the coverage of all service areas. However, the size of the problem is small and is not suitable for real contexts.

* Dynamic programming

It is based on the principle of Bellman (Bellman, 1986): "if a point C belongs to the optimal path between A and B, then the portion of this same path from A to C is the optimal path between A and C". Therefore, this method consists in constructing the optimal subpaths then recursively constructing the optimal path for the entire problem.
(Li et al, 2015) introduce a strategy, named EDSNDA for deploying nodes in WSN. This strategy relies on a dynamic programming model to optimize the coverage, the connectivity and the number of needed nodes. Although its efficiency compared to other methods (Max_cov and Min_cov), the given results are based only on simulations.

### 2.4.2 Meta-heuristics

Meta-heuristics are NP-complete methods used to solve combinatorial optimization problems. Several definitions have been proposed. (Osman and Laporte, 1996) introduced the following description: "It is an iterative process that subordinates and guides a heuristic by cleverly combining several concepts to explore and exploit the entire research space. Learning strategies are used to structure information in order to find optimal solutions or almost optimal ones" (Osman and Laporte, 1996). The fundamental properties of meta-heuristics are as follows:

* They are strategies to guide the research and effectively explore the space in order to achieve a solution close to optimal.

* They are non-deterministic since the optimal solution is not guaranteed.

* They can range from a simple local search procedure to a complex learning process (Widmer et al., 2001).

#### 2.4.2.1 Taboo Search (TS) / Simulated Annealing (SA)

*Simulated annealing* is proposed by (Kirkpatrick et al., 1983), it is a method inspired by a physical procedure which is used by metallurgists. To have a flawless alloy, we heat the metal and let it cool very slowly (annealing technique) until reaching its thermodynamic equilibrium. This method exploits the algorithm in Algorithm 2.1 which consists in introducing an elementary modification to the objective function F. If this modification decreases the value of this function, the solution will be accepted. Otherwise, it will be recognized with a probability of exp (ΔF/T). Note that the choice of the temperature function is decisive.

01: Variable : s (current solution)

02: Begin

03: T ← T0

04: Choose an initial solution s₀;

05: Current solution s ← s₀;

06: Repeat

07: Randomly choose s'∈N(s)

08: Generate a real random number r in [0,1]

09: if r < e<sup>f(s)-f(s')</sup> / T then s ← s'

10: Update T

11: Until the termination criterion is met

12: End

**Algorithm 2.1 Simulated Annealing algorithm**

The authors in (Ateş et al, 2017) introduce a priority-estimation approach for WSN deployment based on area-priority. A K-means-clustered satellite image of the environment is used to identify the coverage-areas priorities of the sensor coverage areas on the image positions. After a priority-queue-based initial deployment, a simulated annealing method is achieved to minimise gaps between sensors and maximise the covered area priority. Although different experiments prove the efficiency of the suggested approach compared to the random deployment, there is no comparison with other optimisation algorithms.

* **Taboo search:** Proposed by Fred Glover in the 80s (Glover, 1989), it is a classical combinatorial optimization method. Its main feature is a history of visited solutions allowing a minimum blind search. Using this history, the Taboo search is able to avoid periodically falling in the same local optima. The Tabou method examines a solution sampling of N (s)
and retains the best solution s' even if $f(s') > f(s)$. Thus, the taboo search does not stop at the first found optimum. To avoid the risk of immediately return to s, since s is better than s', the last visited solutions will be stored in a Taboo list and forbid any move to any item on this list. The Taboo search algorithm is illustrated in Algorithm 2.7, knowing that $N_T(s) = \{s'\}$ $s' \in N(s)$.

01: Begin

02: Choose an initial solution s

03: Let $T \leftarrow \Phi$ and $s' \leftarrow s$;

04: Repeat

05: Choose $s'$ that minimize $f(s')$ in $N_T(s)$

06: if $f(s') < f(s)$ then $s^* \leftarrow s'$;

07: Let $s \leftarrow s'$ and update $T$

08: Until the termination criterion is met

09: End

<caption>**Algorithm 2.2 Tabu Search algorithm**</caption>

One of the most interesting studies using a Tabu Search method to solve the deployment of sensors in WSN, was proposed in (Aitsaadi et al., 2008). Authors formulate the problem as a multi-objective one, aiming to guarantee a minimum detection probability and number of used nodes. Compared to random, grid, MIN MISS, MAX MIN COV, and MAX AVG COV algorithms, the results of the Tabu Search algorithm are encouraging.

### 2.4.2.2 Swarm Intelligence (ACO, PSO, BSO)

#### *Ant colony optimization (ACO)*

ACO algorithms are inspired by the behavior of ants proposed by Marco Dorigo et al in the 90s Dorigo and Di Caro (1999). In nature, an ant colony having the choice between two paths of unequal length leading to a food source, tend to use the shortest route. The model explaining this behavior is as follows:

1. An ant called "scout" walks randomly around the colony.

2. If this ant discovers a food source, it returns to the nest, leaving a trail of pheromones on its path.

3. These pheromones are attractive, ants pass nearby will tend to follow this track.

4. Returning to the nest, these same ants will strengthen the trail.

5. To reach the same food source, if two trails are possible, the shortest one will be traveled by the most ants.

6. The short path will be stronger and therefore more attractive

7. Since the pheromones are volatile, the most extended path will eventually disappear.

The ACO algorithm was introduced by (Dorigo et al., 1996) in order to resolve the problems of hard CO (Combinatorial Optimization). It is a bio-inspired approximate algorithm which aims to obtain good solutions with reasonable computational cost (time) when resolving CO problems. Moreover, it is a meta-heuristic which is considered as probabilistic and population-based. The ACO stems from the foraging behavior of the real ants. Indeed, the ants aim at finding the shortest path between its nest and the source of food. Instead of using visual informations, ants use a chemical substance named 'pheromone' which is left behind their trails. So, in the ACO, the artificial ants (called agents) imitate their natural counterparts to resolve the problems by finding the optimal solutions. The ACO algorithm is illustrated in Algorithm 2.3. Indeed, firstly, when the collection begins, the shortest route leading to food is not known. Thus, each ant pursues a route randomly and place pheromone. As the collection progress, ants continue putting the pheromone. As a consequence, all traveled routes contain this substance. Then, because the pheromone evaporates overtime, if an ant wants to travel, it chooses the route with the highest rate of pheromone, which corresponds to the shortest among all routes. Therefore, overtime, only one route will remain (the shortest one).
01: Initialize the ACO parameters (pheromone, ..)

02: Each_ant_builds_aSolution()

03: Evaluate_the_solutions

04: Initialize the number of travels per ant, t = 1

05: While t < Itmax do

06: Update_the_pheromone()

07: Each_ant_builds_a_newSolution()

08: Evaluate_the_solutions

09: t = t + 1

10: End while

<caption>**Algorithm 2.3 Ant Colony Optimization algorithm**</caption>

In (Deif and Gadallah, 2017), authors address the minimum cost reliability constrained deployment problem (MCRC-SDP) using a hybrid approach based on ant colony and local search. The experimental results relying on a comparison with the greedy heuristic show the efficiency of the suggested method.

*Particle swarm optimization algorithm (PSO)*

**General Principle:** PSO is an evolutionary algorithm that uses a population of candidate solutions to develop an optimal solution to the problem. This algorithm was proposed by Russell Eberhart (an electrical engineer) and James Kennedy (a socio-psychologist) in 1995 (Kennedy and Eberhart, 1995). It is inspired by the origins of the world of living beings, specifically the social behavior of swarming animals, such as fishes and birds. We can observe the complex and dynamic displacement of these animals where each, if does not interact with others, has a limited "intelligence" and local knowledge of his situation in the swarm. The local information and the memory of each are used to decide its movements. Simple rules, such as "staying close to other people", "going in the same direction" or "going to same speed", are sufficient to maintain the cohesion of the swarm, and allow the implementation of complex and adaptive collective behaviors. The swarm of particles corresponds to a population of simple agents, called particles. Each particle is considered as a solution to the problem containing a position (the solution vector) and a velocity. In addition, each particle has a memory allowing it to remember its best performance (in position and value) and the best performance achieved by the "neighboring" (informative) particles: each particle has a group of informants, historically called his neighborhood. A swarm of particles composed of the potential solutions of the problem, "flies" over the search space in search of the global optimum. The displacement of a particle is influenced by the following three components:

1. A component of inertia: the particle tends to support its current direction of movement.

2. A cognitive component: the particle tends to move towards the best site by which it has already passed.

3. A social component: the particle tends to rely on the experience of its congeners and move towards the best site already reached by its neighbors.

The strategy for moving a particle is illustrated in Figure 2.6.

<figure><img src="image_21.png" /><figcaption>**Figure 2.6 Displacement of a particle [inspired from (Eldor, 2012)]**</figcaption></figure>
**Formalization:** In a research space of dimension D, the particle i of the swarm is modeled by its position vector $\vec{x}_i = (x_{i1}, x_{i2}, ..., x_{iD})$ and velocity vector $\vec{v}_i = (v_{i1}, v_{i2}, ..., v_{iD})$. The quality of its position is determined by the value of the objective function at this point. This particle keeps in memory the best position by which it has already passed, noted $\vec{P}_{best_i} = (p_{best_i1}, p_{best_i2}, ..., p_{best_iD})$. The best position reached by the particles of the swarm is noted by $\vec{G}_{best} = (g_{best_1}, g_{best_2}, ..., g_{best_D})$. We refer to the global version of PSO, where all the particles of the swarm are considered as close to the particle i, hence the notation $\vec{G}_{best}$ (global best).

The term "speed" is abusive here because $\vec{v}_i$ vectors are not homogeneous at one speed. It would be more appropriate to use the term of "direction of displacement". However, to respect the analogy with the animal world, the authors preferred to use the term "speed". At the beginning of the algorithm, the particles of the swarm are randomly and regularly initialized in the search space of the problem. Then, at each iteration, each particle moves and linearly combines the three components mentioned above. Indeed, at the iteration t+1, the velocity and position vectors are calculated using equation (2.1) and equation (2.2), respectively.

$$v_{i,j}^{t+1} = w v_{i,j}^t + c_1 r_{1,i,j}^t [pbest_{i,j}^t - x_{i,j}^t] + c_2 r_{2,i,j}^t [gbest_j^t - x_{i,j}^t], j \in \{1, 2, ..., D\} \quad (2.1)$$

$$x_{i,j}^{t+1} = x_{i,j}^{t} + v_{i,j}^{t+1}, j \in \{1, 2, ..., D\} \quad (2.2)$$

where w is a constant, named the coefficient of inertia; c1 and c2 are two constants, named acceleration coefficients; r1 and r2 are two random numbers uniformly taken in [0, 1] at each iteration t for each dimension j.

The three components mentioned above (i.e. of inertia, cognitive and social) are represented in equation (2.1) by the following terms:

1. $w v_{i,j}^t$ corresponds to the component of inertia of the displacement, where the parameter w controls the influence of the direction of the displacement on the future displacement;

2. $c_1 r_{1,i,j}^t [pbest_{i,j}^t - x_{i,j}^t]$ corresponds to the cognitive component of displacement, where the parameter c1 controls the cognitive behavior of the particle;

3. $c_2 r_{2,i,j}^t [gbest_j^t - x_{i,j}^t]$ corresponds to the social component of displacement, where the parameter c2 controls the social aptitude of the particle.

Once the displacement of the particles has been carried out, the new positions are evaluated and the two vectors $\vec{P}_{best_i}$ and $\vec{G}_{best}$ are updated, at the iteration t+1, according to the two equations (2.3) (in the case of a minimization) and (2.4) (in the global version of the PSO), respectively.

This procedure is presented in Algorithm 2.4, where N is the number of particles in the swarm.

$$\vec{P}_{best_i}(t+1) = \begin{cases} \vec{P}_{best_i}(t), & \text{if } f(\vec{x}_i(t+1)) \ge \vec{P}_{best_i}(t) \\ \vec{x}_i(t+1), & \text{otherwise} \end{cases} \quad (2.3)$$

$$\vec{G}_{best}(t+1) = \arg \min_{\vec{P}_{best_i}} f(\vec{P}_{best_i}(t+1)), \quad 1 \le i \le N \quad (2.4)$$

01: Randomly initializes the position and speed of N particles.

02: Evaluate the particle positions

03: For each particle i, $\vec{P}_{best_i} = \vec{x}_i$

04: Calculate $\vec{G}_{best}$ according to (2.4)
05: While the stopping criterion is not satisfied do

06: Move the particles according to (2.1) and (2.2)

07: Evaluate particle positions

08: Update $\vec{P}_{best}_i$ and $\vec{G}_{best}$ according to (2.3) and (2.4)

09: End

<caption>**Algorithm 2.4 PSO algorithm**</caption>

In (Chen and Jiang 2016), authors propose a Particle Swarm method, named PSCD, to resolve the charger deployment problem in Wireless Rechargeable Sensor Networks (WRSNs). PSCD uses the angle and distance between nodes and chargers to estimate the charging efficiency. Afterwards, to sustain WRSNs lifetime, PSCD uses the local and global optimal result to adjust charger's antenna orientations and positions. PSCD is tested using simulation than compared with two other heuristic greedy algorithms prouve its efficiency.

* **Bees Colonies Optimization (BCO)**

In this algorithm, the location of the food source represents the possible solution of the problem and the quantity of the food of this source corresponds to an objective value called fitness. Foragers are assigned to different food sources to maximize the total food intake. The colony must optimize the overall efficiency of the collection. Therefore, the distribution of bees is achieved according to many factors such as the amount of food and the distance between the food source and the hive. This problem is similar to the distribution of web hosting servers, which was actually one of the first problems solved using bee algorithms by (Nakrani and Tovey, 2004). The number of active or inactive foragers represents the number of solutions in this population.

In the first step, the algorithm generates an initial population of solutions randomly distributed. Each solution $x_i (i = 1, 2, ..., SN)$ represents a vector of solutions to the optimization problem. The variables that each vector contains must be optimized. After initialization, the population of solutions is subject to repeated cycles $C = 1, 2, ..., C_{max}$. These cycles represent research processes performed by active, inactive foragers and scouts. Active foragers search in the vicinity of the previous source $x_i$ for new sources $v_i$ having more food and then they calculate their fitness. In order to produce a new food source from the former, we use the following expression:

$$v_{ij} = x_{ij} + \phi_{ij} \times (x_{ij} - x_{kj})$$

Where $k \in \{1, 2, ..., BN\}$ (BN is the number of active foragers) and $j \in \{1, 2, ..., SN\}$ are randomly chosen indices. Although k is randomly determined, it must be different from i. $\phi_{ij}$ is a random number belonging to the interval [-1, 1], it controls the production of a food source in the neighborhood of $x_{ij}$.

After the discovery of each new food source $v_{ij}$, a greedy selection mechanism is adopted and this source is evaluated by the artificial bees, its performance is compared to that of $x_{ij}$. If the food in this source is equal to or better than that of the previous source, this one is replaced by the new one. Otherwise the old one is kept.

For a minimization problem, the fitness is calculated according to this formula:

$$fit_i(\vec{x}_i) = \begin{cases} \frac{1}{1 + f_i(\vec{x}_i)} & si f_i(\vec{x}_i) \ge 0 \\ 1 + abs(f_i(\vec{x}_i)) & si f_i(\vec{x}_i) > 0 \end{cases}$$

$f_i(\vec{x}_i)$ is the value of the objective function of the solution $\vec{x}_i$. At this stage, inactive foragers and scouts are waiting in the hive. At the end of the research process, active foragers share food information from food sources and their locations with other bees via waggling dancing. The latter evaluate this information from all active foragers, and choose the food sources
according to the probability value $P_i$ associated with this source and calculated by the following formula: $P_i = \frac{fit_i}{\sum_{n=1}^{SN} fit_n}$. $fit_i$ is the fitness of the solution $i$ which is proportional to the amount of food in the position $i$. The scouts replace the source of food which is abandoned by bees with a new source. If a position cannot be improved during a predetermined cycle number called "limit", the food source is assumed to be abandoned. All these steps are summarized in the algorithm in Algorithm 2.5.

**Input:** S (number of foragers), W (number of active foragers), O (number of inactive foragers)

**Output:** the best solution

01: Initialize the population with S+W random solutions

02: Evaluate the fitness of the population

03: **While** the stopping criterion is not satisfied **do**

04: Recruit O inactive foragers and assign each to a member of the population

05: **For** each inactive forager assigned to a limb n of the population **do**

06: Iterate the algorithm of the search for a new source

07: **End for**

08: Evaluate the fitness of the population

09: **If** the members of the population have not improved during the iterations **then**

10: Save the solution and replace it with a random solution

11: Find S random solutions and replace the S members of the population having bad fitness

12: **End while**

13: **Return** the best solution

<caption>**Algorithm 2.5** Bee colony optimization algorithm</caption>

In (Udgata et al., 2009), the problem of node deployment in WSN is formulated as a data-clustering problem and resolved using an Artificial Bee Colony (ABC) method. Although the quality of ABC solutions should be compared to other algorithms to prove its performance.

### 2.4.2.3 Genetic algorithms (NSGA-II as an example)

Since the 20th century, the studies of the scientist Charles Darwin affirm that the evolution of species and organisms uses several mechanisms leading to the emergence of new species always better adapted to their respective environments. Among these mechanisms, the selection and the reproduction. Selection is a mechanism which is used to select the most « robust » individuals (chromosomes) in order to reproduce. The reproduction is the mechanism producing descendants that are not identical, it is the evolution phase of the species. As a result, the idea of algorithms named evolutionary algorithms is developed by J.Holland (Holland, 1975). It is based on the principles of natural evolution (coding, selection, crossing and mutation). By analogy with these evolution principles, Holland studies aim to allow the computer to mimic the natural evolutionary mechanisms in order to solve the problems encountered in reality. These studies proposed a first canonical genetic algorithm to solve optimization problems (Bourazza, 2006). Genetic algorithms (GA) are stochastic algorithms belonging to the family of evolutionary algorithms based on the mechanisms of natural evolution and genetics. The operation of a genetic algorithm begins by the selection of a population of potential 'initial solutions' (chromosomes), generally randomly chosen. The relative performance of each individual is evaluated by a fitness function that determines its quality. The generation of a new population of potential solutions is based on the evolutionary operators: selection, crossing and mutation. This evolutionary cycle is repeated until a stopping condition is met. This condition can be a maximum number of generations or a stability degree of the characteristics of the solution. Actually, GA is in wide use in different domains such as economics, finance, optimal control theory, the theory of games, scheduling or engineering real-world problems.

#### a. Principle of the Genetic Algorithm

Genetic algorithms are the combination of two domains: biology and computer science. To define the functioning of a genetic algorithm, we start by setting the technical used words:
* **Genesis:** is the first phase of the algorithm, it is an initial population of size N.

* **Chromosome:** is a chain representing the characteristics of the individual.

* **Phenotype:** is a set of parameters or a decoded structure.

* **Evaluation:** is the calculation phase of the fitness function.

* **Selection:** is the choice of the individuals who will reproduce.

* **Crossing:** is the phase of production of the descendants

* **Mutation:** is the modification of a chromosome in order to improve the characteristics of the individual.

As shown in Figure 2.7, the GA is composed of five steps:

1. Initialization of the situation.

2. Selection for reproduction.

3. Crossing of the selected individuals.

4. Mutation of the selected individuals.

5. Selection for replacement.

6. If the stop condition is satisfied then STOP, S = {the best individuals}
Otherwise go back to step (2).

<figure><img src="image_22.png" /><figcaption>Figure 2.7 General architecture of a genetic algorithm</figcaption></figure>

## Types of chromosome coding

The use of GA for resolving a given problem requires the coding of its data. This coding is related to the nature of the problem. It is based on establishing a connection between the values of the variable and the individuals of the population in order to imitate the link which exists in biology between the genotype and the phenotype. Three types of coding exist:

- Digital: binary or real, this type is used if the alphabet of the problem consists of digits.

- Symbolic: if the alphabet is a set of alphabetic letters or symbols.

- Alpha-numeric: if the alphabet of the problem is a combination of letters and numbers (Bourazza, 2006).

The correct choice of coding strongly conditions the effectiveness of the genetic algorithm.

## b. Individual selection methods

Selection is the choice of individuals for reproduction and mutation. Several selection methods exist in the literature:

* **Sélection by rank:** This method consists in attributing to each individual a classification according to the value of its objective function. For a maximization problem, individuals are ranked in descending order of the values of the objective function. Thus, the worst individual
that is the one with the lowest value of the objective function will take rank 1. For a minimization problem, the ranking will be the opposite of the previous case. The new population is then taken from sets of ordered individuals using probabilities that are indexed according to the ranks of individuals. The probability of selection of Parent$_i$ is equal to $\frac{\text{Rang}(\text{Parent}_i)}{\sum_{j \in \text{population}} \text{Rang}(\text{Parent}_j)}$

* **Roulette selection:** This method consists in associating with each individual *i* a probability of selection denoted Prob$_i$ proportional to its objective function value F$_i$. Prob$_i$ = F$_i$ / $\sum_{j \in \text{population}}$ F$_j$. Each individual is then reproduced with a Prob$_i$ probability. Some individuals (the good ones) will be reproduced more and others (the bad ones) eliminated. For a minimization problem, the selection probability used for an individual *i* is equal to (1-prob$_i$)/(N-1).

* **Selection by Tournament:** The principle of this method is to randomly choose a subpopulation of size M fixed a priori by the user. Better individuals with respect to the sub-population will be selected for the application of the crossover operator. Indeed, it is a competition between individuals of a subpopulation of size M (M≤N), N is the size of the population. This method gives more chance to poor quality individuals to participate in improving the quality of the population. The M parameter plays an essential role in the tournament method. If M=N, the tournament selection gives each time a single individual that is the best individual according to the value of the objective function, which reduces the genetic algorithm to a local search algorithm. If M = 1, the selection corresponds to the random selection.

**c. Crossing operators:** Crossing consists of generating two children from two parents with a probability of crossing P$_x$ in order to enrich the diversity of the population. In the following, two crossing operators are detailed.

**- One-point operator:** It consists in dividing every two parents (P1 and P2) into two parts at the same position, chosen at random. The first child (D1) is composed of two parts of both parents. The first part is that of the first parent and the second one is that of the second parent. The second child (D2) is composed of two parts, the first part of the second parent and the second part of the first parent.

<table><tr><td>P1</td><td>0 1 1 1 0 1 0 1</td></tr><tr><td>P2</td><td>1 1 0 0 1 0 1 0</td></tr></table>

<table><tr><td>D1</td><td>0 1 1 0 1 0 1 0</td></tr><tr><td>D2</td><td>1 1 0 1 0 1 0 1</td></tr></table>

**- Two-point operator:** This method consists in setting two positions. The first child will be the copy of the first parent by replacing its part between the two positions by that of the second parent. The same operation will be applied to determine the second child by reversing the roles of the first and the second parent.

<table><tr><td>P1</td><td>0 1 1 1 0 1 0 1</td></tr><tr><td>P2</td><td>1 1 0 0 1 0 1 0</td></tr></table>

<table><tr><td>D1</td><td>0 1 1 0 1 1 0 1</td></tr><tr><td>D2</td><td>1 1 0 1 0 0 1 0</td></tr></table>

**d. Mutation operator:** In accordance with the natural mutation, this operator changes the value of a chromosome in order to improve the characteristics of the individual. It allows
the GA to efficiently explore the search space. Moreover, it guarantees a susceptibility to reach the majority of points in the realizable domain.

<figure><img src="image_23.png" /></figure>

### e. Advantages of GA

- The use of an objective function (fitness) regardless of its nature (convex, continuous or differentiable) which gives it more flexibility and a large field of application.

- The solution is a population of size N, which allows the generation of a form of parallelism.

- The probability of crossing and mutation avoid falling into a local optimum and moving towards the global optimum.

### f. Non dominated Sorting Genetic Algorithm II (NSGA-II)

NSGA-II was introduced by Deb and Agawal (Deb et al., 2002) to correct the criticisms of NSGA-I. This algorithm estimates the density of solutions that surround a particular solution in the population by calculating the distance between two points and their sides for all the objectives of the problem. This value is called "crowding distance" during the selection. The algorithm NSGA-II uses the operator "crowded comparison" which takes into account the ranking of non-dominance of the individual in the population and its "crowding distance" (i. e. non-dominated solutions are preferred over dominated solutions). If two solutions have the same rank of non-dominance, the one that resides in the least public region is preferred. The NSGA-II steps are shown in Figure 2.8.

<figure><img src="image_24.png" /><figcaption>Figure 2.8 NSGA-II Steps</figcaption></figure>

The NSGA-II algorithm is considered in the literature as one of the most efficient algorithms for solving a multi-objective optimization problem using the Pareto approach. However, many-objective optimization problems are more complex and even the NSGA-II becomes inefficient.

#### 2.4.3 Many-objective optimization

##### 2.4.3.1 Many-objective PSO algorithm

Proposed by (Kennedy and Eberhart, 1995), the PSO is a stochastic evolutionary algorithm which is inspired by the social behavior of animals such as fishes and birds. In this algorithm, the particles are initially scattered in the search space in a random manner and they cooperate to achieve an optimal global objective in the Pareto sense. Each particle is characterized by a current position noted $\vec{X}_i(t) = \vec{X}_i(t-1) + V_i(t)$ (14) and a speed of movement noted

$$ \vec{V}_i(t) = \omega \vec{V}_i(t-1) + c_1 r_1(\vec{X}_{pbest} - \vec{X}_i(t)) + c_2 r_2(\vec{X}_{gbest} - \vec{X}_i(t)) \quad (15) $$ where $\omega$
represents the weight of inertia that controls the speed of change as a function of the current speed. $c_1$ and $c_2$ are two knowledge factors. $r_1$ and $r_2$ are two random values in [0..1].

A particle can maintain its best-visited position, noted pbest. Moreover, it can access the best position visited by its neighbors, named gbest. The particle changes its position by following these tendencies: A conservative tendency in which the particle tends to return to its best-visited point, an adventurous tendency in which the particle tends to find a better position in the search space and a panurgical tendency in which the particle tends to follow the best position found by its neighbors.

In many-objective optimization problems where the number of objectives (often conflicting) exceeds three, the most important challenging issue is how to obtain a well distributed non-dominated set of solutions which are close to the Pareto Front (PF) in the objective space. Different MaOPSO were proposed in several studies to resolve the lack of diversity and convergence in many-objective problems: In (Figueiredo et al. 2016), the authors proposed a MaOPSO algorithm relying on a set of reference points to recognize the best solutions and guide the search process according to these reference points. The study in (Díaz-Manríquez et al., 2016) proposed an algorithm that empowers the multi-objective structure of the PSO to deal with many-objective problems and suggest a R2 indicator to guide the search. In (Britto and Pozo, 2012), the authors proposed a based-on archiving PSO algorithm named I-MOPSO which explores specific aspects of the MOPSO to hundle many-objective problems while introducing more convergence and diversity on the search.

In (Hu et al., 2017), a MaOPSO based on a two-stage strategy and a parallel cell coordinate system is introduced to separately emphasize the diversity and convergence at different stages using a many-objective optimizer and a single-objective one, respectively.

### 2.4.3.2 NSGA-III algorithm

NSGA-III (Deb and Jain 2014) is a recent algorithm, proposed as an extension of NSGA-II (Deb et al., 2002). It uses a reference point-based approach to solve many objective problems (MaOPs). NSGA-III use the same concept of weight vector generation in MOEA/D (Zhang and Li, 2007) to determine a set of reference points scattered over the objective space. At every generation of each solution, the values of the objective function are normalized to [0, 1]. Then, a reference point is associated with each solution based on its perpendicular distance to the reference line. Assigning a reference point to each solution ensures the uniform repartition of the reference points across the normalized hyper-plane. The generated offspring is combined with the parent to create a hybrid population. Afterward, the hybrid population is divided into a set of non-domination levels according to a non-dominated sorting procedure. The next parents as composed of the solutions in the first level so on and so forth. A niche-preservation operator is used to select solutions in the last acceptable level where the solutions associated with a less crowded reference line are more likely to be selected. For the majority of test problems, NSGA-III which is proposed especially for many-objective optimization shows superior performance compared to other methods such as MOEA/D and NSGA-II. Algorithm 2.6 illustrates the NSGA-III algorithm.

**Input:** $P_0(Initial Population)$, $N_{pop}$ size of the population, $t$ (iteration) = 0, $It_{max}$ (Maximum iteration)

**Output:** $P_t$

01: **While** $t<It_{max}$ **do**

02: Create Offspring $Q_t$

03: Mutation and recombination on $Q_t$

04: Set $R_t=P_t \cup Q_t$

05: Apply non-dominated sorting on $R_t$ and find $F1, F2, ...$

06: $S_t=\{\}, i=1$

07: **While** $|S_t| \le N_{pop}$ **do**

08: $S_t=S_t \cup F_i$

09: $i=i+1$

10: **End While**

11: If $|S_t|<N_{pop}$ **do**

12: $P_{t+1}=\{i=1,...,F_i\}$
13: Normalize $S_t$ using min and intercept points of each objective

14: Associate each member of $S_t$ to a reference point

15: Choose $N_{pop}-|P_t+1|$ members from $F_t$ by the niche-preserving operator

16: Else $P_{t+1}=S_t$

17: End if

18: $t=t+1$

19: End While

<caption>Algorithm 2.6 The NSGA-III algorithm</caption>

### 2.4.3.3 MOEA/DD

This algorithm (Li et al. 2015) aims to achieve the balance between diversity and convergence which is a key issue in resolving scalable multi-objective optimization. Most of the existing methodologies, demonstrating efficiency in solving real-world problems with two and three objectives, face significant challenges in optimizing problems with more than four objectives. MOEA/DD suggests a unified paradigm, which combines approaches based on decomposition and dominance for multi-objective optimization. The primary goal is to balance the convergence and diversity of the evolutionary process using the decomposition and dominance metrics. Compared to other recent constrained optimizers, the MOEA/DD is very competitive on constrained optimization problems with up to 15 objectives. On the other hand, as the performance of an optimization algorithm may degenerate with the increase in the number of decision variables, it is useful to study the scalability of MOEA/DD for large scale problems. Algorithm 2.7 illustrates the MOEA/DD algorithm.

**Output:** population $P$

01: $[P, W, E] \leftarrow INITIALIZATION();$
// $P$ is the parent population, $W$ is the weight vector set and $E$ is the neighborhood index set
02: **while** termination criterion is not fulfilled **do**

03: **for** $i \leftarrow 1$ **to** $N$ **do**

04: $P \leftarrow MATING SELECTION(E(i), P)$;

05: $S \leftarrow VARIATION(P)$;

06: **foreach** $x^c \in S$ **do** // $x^c$ is an offspring

07: $P \leftarrow UPDATE_POPULATION(P, x^c)$

08: **end**

09: **end**

10: **end**

11: **return** $P$

<caption>Algorithm 2.7 The MOEA/DD algorithm (Li et al. 2015)</caption>

### 2.4.3.4 Two_Arch2 algorithm

Two_Arch2 (Wang et al. 2015) is a low-complexity algorithm that represents an enhancement of the Two_Arch algorithm that offers two significantly improved archives (CA and DA) focused on diversity and convergence and separately designed to provide a more balanced optimization algorithm for ManyOPs. In Two_Arch2, different selection principles based on Pareto based indicators are attached to both archives. Moreover, a new diversity maintenance scheme based on the Lp ($p<1$) standard for ManyOPs is proposed. Illustrated in Figure 2.9, the Two_Arch2 is based on indicator and Pareto dominance, which combines the benefits of the indicator and Pareto-based MOEA. Indeed, the $I_{\epsilon+}$ indicator is used as a selection principle in the CA archive to improve the convergence of MaOPs while the Pareto dominance is used as a selection principle in DA to promote diversity. This means that Two_Arch2 has a good convergence capability by CA (that is indicator-based), and it can maintain a satisfactory diversity by DA (that is Pareto-based). In Two_Arch2, an $L_{1/m}$-norm maintenance scheme is used to remove additional DA solutions since most Euclidean distance-based diversity maintenance methods encounter problems in solving ManyOPs. Hence, the Lp-norm based distances ($p \ge 1$) are inefficient in a high-dimensional space whereas the distances based on the norm Lp ($p<1$) are more efficient in such high-dimensional space.
<figure><img src="image_25.png" /><figcaption>Figure 2.9 Flow-chart of the Two_Arch2 Algorithm</figcaption></figure>

According to the authors of Two_Arch2, its experimental results show an efficiency for ManyOP up to 20 objectives with diversity, convergence and satisfactory complexity. Despite this, unsatisfactory performance of Two_Arch2 on several issues such as the WFG. Moreover, unlike other recent optimizers such as NSGA-III, the Two_Arch2 could not keep the extreme points. In this respect, the extreme point maintenance principle in NSGA-III can be used to enhance the Two_Arch2.

### 2.4.3.5 Similitudes and differences between many-objective algorithms

Different similarities and differences between MOEA/DD, MOEA/D and NSGA-III can be detailed as follows (Li et al. 2015):

With regard to MOEA/DD and MOEA/D, the main similarities concern the use of a set of weight vectors to guide the selection procedure, the use of the concept of neighborhood and the application of a scalarization function to measure the aptitude value of a solution. The main differences between MOEA/DD and MOEA/D are as follows:

- MOEA/DD use weight vectors which, in addition to defining a sub-problem that evaluates the aptitude value of a solution, specifies a subregion for estimating the local density of a population.

- The MOEA/D uses an update/selection procedure with a ‘one-sided’ selection in which only the sub-problems have the right to choose their preferred solutions. On the other hand, each MOEA/DD solution is associated with a subregion (subproblem) and has the right to select its preferred subregion.

- The speed of convergence of the MOEA/D is often faster than that of the MOEA/DD. However, MOEA/D does not enhance the preservation of diversity, which is very important for many-objective problems.

- In MOEA/D, the concept of neighborhood is used for mating and updating while it is used only for mating restriction in MOEA/DD.

With regard to MOEA/DD and NSGA-III, the main similarities concern the selection procedure where the two algorithms use the same concept (named weight vectors in MOEA/DD and reference points in NSGA-III) with solutions that are associated with weight vectors (or reference point). Moreover, the two algorithms use the Pareto dominance relation to divide the population into several levels of non-denomination. The main differences between MOEA/DD and NSGA-III are as follows:

- The selection in NSGA-III is based on a generational scheme while the selection in MOEA/DD is based on a permanent scheme.

- In MOEA/DD, the population is divided into several levels of non-denomination with a selection procedure that does not fully obey the decision taken by the Pareto dominance relationship and a solution associated with an isolated subregion may survive the next iteration even if it does not belong to the last level of non-denomination. On the other hand,
such a solution in NSGA-III cannot survive the next generation and can result in a significant
loss of population diversity.

### 2.4.3.6 Difficulties in MaOAs

Recently, with an increasing number of objectives, the realism and complexity of optimization problems, the interest of the EMO (evolutionary multi-objective optimization) community are focused on the evolutionary many objective optimization (EMaO). This focus is explained by the fact that the performance of most evolutionary optimization algorithms deteriorates if the number of objectives exceeds three.

In what follows, we enumerate the most critical challenges faced by EMO and EMaO (evolutionary many-objective optimization) when solving MaOPs:

* **Exponential complexity in space and time:** A major failing of most EMOs is the time exponential increase with the rise in the number of objectives. Same goes for the exact calculation of certain performance indicators such as the Hypervolume (HV) (Zitzler et al. 1999). This exponential complexity can deteriorate the performance of EMOs in the resolution of MaOPs. As it is the case in our study, this problem can be solved by using dimensionality reduction mechanisms to eliminate redundant objectives. An approximate method is also used to calculate the performance indicators.

* **Pareto-based EMOs:** The final solutions given by Pareto-based EMOs for many-objective problems can be distributed uniformly in the search space and away from the desired PF (Pareto Front). Studies like (Purshouse et al. 2007) show that random search can yield better results than Pareto-based EMOs for problems having nine objectives or more. Hence, the criterion of dominance by Pareto cannot be applied to compare individuals. In this respect, several solutions can be used to solve this problem. We can cite, for instance, replacing the principle of Pareto dominance by that of the $\in$-dominance (Laumanns et al. 2002). Moreover, modifying the dominance region by the control of the dominance angle to increase the selection pressure in the PF. Another solution used to guide the population towards the PF is the maintenance of diversity. As in the case of our work, this can be achieved by incorporating some mechanisms to ensure that the parents are chosen in the neighborhood when performing the mutation and recombination operators or by adaptively selecting these operators.

* **The problem of representing the trade-off surface:** A problem with n objectives has a PF with (n-1) hypersurface dimensions, which considerably increases the number of points used in the representation of this surface and creates problems related to the visualization of these points. Hence, new visualization methods of the PF are needed.

* **The recombination and mutation operators are inefficient:** By increasing the number of dimensions in the search space, the distances between individuals become large, causing the inefficiency of the operators (Purshouse et al. 2007). For this reason, having distant parents implies that the created offspring may also be distant from its parents, which slows down the search process. To solve this problem, we adaptively choose the operators at each iteration according to their contributions.

* **The density estimation is inaccurate:** If the space is highly dimensional, the degree of crowding of the population will become unspecifiable by the majority of the density estimation methods. For example, the density estimation using the crowding distance loses its relevance for a number of objectives greater than three which can be explained by the exponential increase in the number of hyperboxes in the grid that causes the dispersion of individuals in several hyperboxes. Indeed, several MoAs suffer from the inaccuracy of the density estimators using the euclidean distance to measure the resemblance between individuals. Thus, it is necessary to substitute the dominance relation by other concepts such