Appendix 1. RSSI and FER measures of in our experimental tests (Scenario 1)

<table><tbody><tr><td rowspan="3">P11</td><td>FER detected by 'C'</td><td>0,875</td><td>0,718</td><td>0,732</td><td>0,067</td><td>0,017</td><td></td><td></td><td>0,213</td><td>0,099</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER generated by 'C'</td><td></td><td>0,733</td><td></td><td></td><td>0,912</td><td></td><td></td><td></td><td></td><td>0,8</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,75</td><td>0,52</td><td>0,861</td><td>0,627</td><td>0,014</td><td>0,769</td><td>0</td><td>0,065</td><td>0,028</td><td>0</td><td></td><td>0,3218</td><td>0,2895214</td><td>0,232</td><td>0,198</td><td></td></tr><tr><td rowspan="2">P12</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,082</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,625</td><td>0,298</td><td>0,465</td><td>0,219</td><td>0,080</td><td>0,64</td><td>0,72</td><td>0,017</td><td>0</td><td>0,055</td><td>0,769</td><td></td><td>0,2191</td><td>0,186125</td><td>0,18956</td><td>0,136</td></tr><tr><td rowspan="3">P13</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,708</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,551</td><td>0,574</td><td>0,677</td><td>0,017</td><td>0,554</td><td>0</td><td>0,363</td><td>0,038</td><td></td><td>0,338</td><td>0,87</td><td></td><td>0,3545</td><td>0,234</td><td>0,249</td><td>0,202</td></tr><tr><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,129</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">P14</td><td>FER detected by 'C'</td><td>0,826</td><td>0,918</td><td>0,421</td><td>0,011</td><td>0,441</td><td></td><td></td><td>0,27</td><td>0,263</td><td>0,819</td><td>0,139</td><td>0,28</td><td></td><td>0,2067</td><td>0,18885</td><td>0,211</td><td>0,074</td></tr><tr><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,013</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,058</td><td>0,937</td><td>0,054</td><td>0,004</td><td>0</td><td></td><td></td><td>0,021</td><td></td><td>0,056</td><td></td><td>0,017</td><td></td><td>0,1354</td><td>0,109075</td><td>0,0798</td><td>0,037</td></tr><tr><td rowspan="3">P15</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,245</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,4</td><td>0,311</td><td>0,648</td><td>0,092</td><td>0,25</td><td></td><td></td><td>0,05</td><td>0,66</td><td>0,028</td><td>0,615</td><td>0,03</td><td></td><td>0,1685</td><td>0,11675</td><td>0,089</td><td>0,053</td></tr><tr><td rowspan="3">P16</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,135</td><td>0,685</td><td>0,072</td><td>0,326</td><td></td><td></td><td></td><td>0,030</td><td>0,666</td><td></td><td>0,280</td><td>0,917</td><td></td><td>0,21079</td><td>0,17616</td><td>0,16772</td><td>0,12904</td></tr><tr><td colspan="21">Average values</td></tr></tbody></table>

* VMF (A): Let Vi be the average value between the FER value of detecting 'C' by the node 'Ni' and the FER value of detecting 'Ni' by 'C' in a given position Pi considering the new nomad node's positions given by the algorithm A. VMF(A) is the average value of the FER. It is defined by dividing the sum of the Vi values by the total number of nodes detecting or detected by 'C'.

* The positions of nomad nodes and their corresponding values of FER in each location Pi are not mentioned in Tables A3 and A4.

<table><caption>Table A4 Averages of FER values by neighbours of 'C' in different positions overnight</caption><thead><tr><th>\</th><th></th><th>N1</th><th>N2</th><th>N3</th><th>N4</th><th>N5</th><th>N6</th><th>N7</th><th>N8</th><th>N9</th><th>N10 (A)</th><th>N11 (B)</th><th>VMF (Initial deployment)</th><th>VMR(ε-NSGA-II-AxN-AmN)</th><th>VMR(U-NSGA-III-AxN-AmN)</th><th>VMR(mMOEA/DD-AxN-AmN)</th></tr></thead><tbody><tr><td rowspan="2">P1</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,048</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,439</td><td>0,268</td><td>0,156</td><td>0,008</td><td>0,218</td><td>0</td><td>0,156</td><td>0,159</td><td>0,091</td><td>0,294</td><td>0,08</td><td>0,1675</td><td>0,1469</td><td>0,133</td><td>0,128</td></tr><tr><td rowspan="2">P2</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,036</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,185</td><td>0,182</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">P3</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,542</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,265</td><td>0,25</td><td>0,154</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">P4</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,258</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">P5</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,853</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,029</td><td>0,446</td><td>0,022</td><td>0,006</td><td>0,734</td><td>0,781</td><td>0,615</td><td>0,058</td><td>0,246</td><td>0,416</td><td>0,775</td><td>0,0573</td><td>0,0522</td><td>0,044</td><td>0,033</td></tr><tr><td rowspan="2">P6</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,821</td><td>0,333</td><td>0,083</td><td>0,205</td><td>0,066</td><td>0,101</td><td></td><td>0,003</td><td></td><td>0,693</td><td>0</td><td>0,104</td><td>0,074</td><td>0,0114</td><td>0,0028</td></tr><tr><td rowspan="2">P7</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,498</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,166</td><td>0,165</td><td>0,68</td><td>0,009</td><td>0,023</td><td>0,040</td><td>0</td><td>0,005</td><td>0</td><td>0,220</td><td></td><td>0,1319</td><td>0,1174</td><td>0,129</td><td>0,098</td></tr><tr><td rowspan="2">P8</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,617</td><td>0,644</td><td>0,79</td><td>0,211</td><td>0,010</td><td>0,705</td><td>0,936</td><td>0,010</td><td>0,901</td><td>0,021</td><td></td><td>0,1105</td><td>0,0768</td><td>0,088</td><td>0,076</td></tr><tr><td rowspan="2">P9</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FER detected by 'C'</td><td>0,736</td><td>0,607</td><td>0,846</td><td>0,020</td><td>0,022</td><td>0,5</td><td></td><td>0,039</td><td>0,930</td><td>0,031</td><td></td><td>0,0295</td><td>0,0122</td><td>0,0326</td><td>0,008</td></tr><tr><td>P10</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,046</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
Appendix 1. RSSI and FER measures of in our experimental tests (Scenario 1)

<table><thead><tr><th></th><th>by 'C'</th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>FER detected by 'C'</td><td>0,710</td><td>0,111</td><td>0,200</td><td>0,037</td><td>0,023</td><td>0,923</td><td></td><td>0,120</td><td>0</td><td>0,040</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P11</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td>0,276</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,2954</td><td>0,2383</td><td>0,266</td><td>0,241</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,95</td><td>0,118</td><td>0,954</td><td>0,030</td><td>0,074</td><td></td><td></td><td>0,690</td><td></td><td>0,681</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P12</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,5315</td><td>0,3024</td><td>0,4036</td><td>0,29</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,863</td><td>0,627</td><td>0,902</td><td>0,643</td><td>0,7</td><td>0,636</td><td>0,631</td><td>0,39</td><td>0,828</td><td>0,307</td><td>0,425</td><td></td><td></td><td></td><td></td></tr><tr><td>P13</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,775</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,1706</td><td>0,1512</td><td>0,166</td><td>0,147</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,795</td><td>0</td><td>0,007</td><td>0,079</td><td>0,714</td><td>0</td><td>0,12</td><td>0,826</td><td>0,092</td><td>0,166</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P14</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,082</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,1293</td><td>0,1163</td><td>0,128</td><td>0,115</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,075</td><td>0,765</td><td>0,089</td><td>0,005</td><td>0,125</td><td></td><td>0,012</td><td>0,018</td><td>0,065</td><td>0,653</td><td>0,538</td><td></td><td></td><td></td><td></td></tr><tr><td>P15</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td>0,121</td><td></td><td></td><td>0</td><td></td><td></td><td></td><td></td><td></td><td>0,0287</td><td>0,0249</td><td>0,0251</td><td>0,0242</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,155</td><td>0,757</td><td>0,031</td><td>0,004</td><td>0,183</td><td></td><td>0,013</td><td>0,121</td><td>0,024</td><td>0,898</td><td>0,015</td><td></td><td></td><td></td><td></td></tr><tr><td>P16</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,29</td><td>0,196</td><td>0,188</td><td>0,167</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0,869</td><td>0,615</td><td>0,827</td><td>0,29</td><td>0,284</td><td></td><td>0,294</td><td>0,555</td><td>0,732</td><td>0,86</td><td>0,232</td><td></td><td></td><td></td><td></td></tr><tr><td>P17</td><td>FER generated by 'C'</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,0534</td><td>0,0279</td><td>0,0252</td><td>0,018</td></tr><tr><td></td><td>FER detected by 'C'</td><td>0</td><td>0,688</td><td>0,901</td><td>0,053</td><td>0,315</td><td></td><td>0,194</td><td>0,74</td><td>0,975</td><td>0,393</td><td>0,294</td><td></td><td></td><td></td><td></td></tr><tr><td colspan="2">Average values</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,15125</td><td>0,11827</td><td>0,12317</td><td>0,10288</td></tr></tbody></table>
**Mots-clefs** : Réseau de collecte de l'IoT, optimisation, redéploiement 3D d'intérieur, validation expérimentale, méta-heuristique, hybridation, algorithme de colonies de fourmis, algorithmes génétiques, optimisation par essaim particulaire, réduction de dimensionnalité, incorporation de préférences.

# 1 Motivations et problématique

Pour différents contextes d'application, le domaine des réseaux de capteurs sans fil (RCSF) est un axe de recherche en évolution continue, surtout avec l'émergence de l'internet des objets (IoT). Par la suite, l'IoT est un concept qui se relie étroitement aux problématiques traitées dans notre étude. L'IoT offre un scénario dans lequel différents entités hétérogènes et communiquant appelées objets/choses (personnes, robots ou appareils) sont connectées et distinguées par des identifiants uniques. Ces entités peuvent transférer des données sur le réseau automatiquement sans intervention humaine. Le RCSF est le pont reliant le monde numérique au monde réel. Il permet d'assurer la communication matérielle pour transmettre et récupérer les valeurs réelles détectées par les objets connectées sans fil (nœuds de capteurs). Le rôle de l'IoT est celui de traiter ces données, de les manipuler et de prendre les décisions. Dans nos travaux de recherche, nous nous intéressons aux réseaux DL-IoT (Device Layer-IoT) qui représentent le réseau de collecte utilisé pour obtenir des données à partir des nœuds de capteurs réparties dans l'environnement réseau. De ce fait, notre approche peut etre appliquée pour les contextes WSN et IoT. A cet égard, face à la capacité limitée en énergie, en traitement et en mémoire des capteurs/objets, le DL-IoT soulève de nombreux problèmes d'optimisation. Notre contribution globale s'oriente vers la proposition des heuristiques, des méta-heuristiques hybrides (centralisées et distribuées), de modèles multi-objectif, de formulations mathématiques et d'évaluations de récents approches d'optimisation sur le DL-IoT. Compte tenu de la croissance continue dans les thématiques du DL-IoT, différents contextes peuvent être investiguées tel que l'optimisation du déploiement des nœuds.

Le déploiement des nœuds représente la première phase dans l'installation d'un WSN. En termes d'optimisation de consommation d'énergie, ceci influe considérablement sur la performance, la fiabilité et le fonctionnement du réseau. On peut décrire le problème de déploiement des nœuds comme étant le positionnement de l'ensemble des capteurs constituant le réseau et se trouvant disséminés de manière aléatoire. Pour compenser le caractère erratique de leur placement, on déploie souvent un grand nombre de capteurs intelligemment. Ceci peut contribuer également à l'augmentation de la tolérance aux fautes du réseau. Pour le déploiement 2D de réseaux de capteurs sans fil, une littérature très abondante existe allant de l'organisation topologique du réseau aux spécificités techniques des capteurs et leur manière de communiquer. Pourtant, le déploiement 3D à moindre coût pose de très nombreux problèmes d'optimisation avec une littérature peu abondante. Donc, notre objectif est de trouver l'architecture la plus optimisée et de fournir des solutions d'organisation 3D des capteurs, tout en améliorant la performance du réseau. A cet égard, plusieurs issues et objectifs sont reliées au problème de déploiement des réseaux de capteurs tels que la consommation d'énergie, la durée de vie et la localisation. De ce fait, différents approches heuristiques pour l'optimisation dans les WSN peuvent être envisagées.
La nature distribuée et dynamique du problème de déploiement exige l'utilisation de méthodologies avancées d'optimisation et de modélisation : les méta-heuristiques hybrides. Ces dernières permettent d'exploiter la complémentarité de ces méthodes entre elles, et de tirer les avantages des autres approches classiques hybrides avec eux. Face à nos objectifs qui concernent principalement l'assurance d'un système évolutif, flexible et robuste contre les perturbations du réseau, cette nouvelle classe de méta-heuristiques hybrides a montré sa performance dans la résolution des problèmes d'optimisation difficiles. Notre contribution consiste à proposer un ensemble de modifications et hybridations bien justifiées sur les méta-heuristiques, tout en les appliquant et évaluant leurs performances sur notre problème de déploiement issu du monde réel. A cet égard, les problèmes d'optimisation les plus difficiles à résoudre sont généralement dérivés de problématiques réelles qui sont souvent non mesurables, complexes et antagonistes. Ils sont, majoritairement, des problèmes comprenant plusieurs critères. Ceci est dû au fait qu'ils possèdent plusieurs objectifs d'évaluations, souvent contradictoires et à considérer simultanément. Ceci a donné naissance à la théorie de l'optimisation multi-objectif. Dans la littérature, plusieurs méthodes de résolution des problèmes multi-objectifs ont été développées. On peut classifier ces méthodes en deux grandes classes : les méthodes exactes et les méthodes approchées qui sont subdivisées en des heuristiques spécifiques et des méta-heuristiques. Les méta-heuristiques forment un ensemble d'algorithmes d'optimisation visant à résoudre les problèmes d'optimisation difficiles. Ces algorithmes permettent d'améliorer la qualité des solutions sans garantir l'optimalité de la solution obtenue mais dans un temps de calcul très raisonnable par rapport à la complexité du problème souvent insolvable dans un temps polynomial. Les problèmes d'optimisation du monde réel ont souvent plusieurs objectifs et contraintes conflictuels et contradictoires (nommés problèmes d'optimisation multi-objectif (MOP)). Ceci implique qu'il n'existe pas une solution unique qui est optimale par rapport à tous ces objectifs simultanément. La solution est en général plusieurs solutions non comparables, et l'ensemble des compromis de ces solutions est appelé « front de Pareto » (PF). Le but du MOP est de trouver une approximation bien répartie et bien convergente du PF. Par la suite, le décideur (DM) peut sélectionner la solution préférée. Pour déterminer le PF, différents méthodes, appelés algorithmes évolutionnaires (EA) ont été proposées dans la littérature en se basant sur l'imitation des principes de l'évolution biologique. Les EA sont devenus populaires et largement utilisés dans la résolution des MOP à cause de leurs insensibilité aux aspects et formes des fonctions objectives (Deb 2001) telles que la multi-modalité, la discontinuité, la convexité et l'uniformité de l'espace de recherche, etc.. En effet, l'optimisation multi-objectif évolutionnaire (EMO) est une récente branche de l'optimisation qui est apparue suite à ce succès des algorithmes d'optimisation multi-objective évolutionnaires (MOEA) dans la résolution MOP.

## 2 Organisation du document

Ce rapport comporte quatres chapitres répartis sur deux parties. Une première partie qui concerne l'état d'art et comporte deux premiers chapitres ; et une deuxième partie qui concerne les contributions proposées et qui se compose des chapitres 3 et 4. Nous commençons dans le premier chapitre par présenter l'état de l'art du problème de déploiement 3D indoor. Nous introduisons les défis de déploiement tridimensionnel et ses différents types, objectives, modèles et applications. Ensuite, des travaux de recherche récents portant sur le problème du déploiement ont été identifiés et critiqués. Le deuxième chapitre permet d'introduire les méthodes utilisées pour résoudre le déploiement en 3D à l'intérieur, en particulier les algorithmes d'optimisation évolutif, les systèmes multi-agents et les concepts d'incorporation de la réduction et des préférences de l'utilisateur. Nous détaillons, également, les concepts fondamentaux d'optimisation multi-objectifs tels que la domination, la frontière de Pareto. Nous décrivons aussi les approches principales et méta-heuristiques classiques de la résolution pour ces problèmes multi-objectifs. Dans le troisième chapitre, nous présentons
une modélisation mathématique du problème de déploiement, basée sur une formulation de programmation linéaire entière. Nous présentons alors l'architecture des nœuds, les hypothèses, la notation et la fonction objective. Ensuite, nous proposons les objectifs et leurs spécificités. Ce troisième chapitre est aussi consacré à expliquer et justifier les hybridations et modifications introduites aux méta-heuristiques, dans l'optique d'améliorer leurs performances et capabilités à résoudre les problèmes d'optimisation. En particulier, nous détaillons les problèmes complexes et à plusieurs objectifs du monde réel tel que le nôtre. Ces modifications concernent essentiellement l'utilisation du voisinage et d'un concept adaptatif pour les opérateurs de mutation et de recombinaison, l'utilisation de fonctions de scalarisation multiples dans l'approche basée sur l'agrégation. Nous détaillons l'incorporation de la réduction de dimensionnalité, l'incorporation des préférences des utilisateurs, un cadre hybride pour NSGA-III et colonies de fourmis, enfin la proposition d'un concept d'accents d'oiseaux dans PSO et son hybridation avec les systèmes multi-agents. Le dernier (quatrième) chapitre est consacré à l'illustration des résultats des différents tests expérimentaux. Nous commençons par introduire les différents paramètres de test et les métriques d'évaluation que nous avons utilisée pour valider nos propositions. Nous passons par la suite à l'illustration des résultats numériques du problème de déploiement 3D après avoir incorporé notre schéma proposé de réduction de dimensionnalité et de préférences. Ensuite, nous détaillons les résultats sur les fonctions de test sans contrainte DTLZ. Une étude qui présente la modélisation des protocoles utilisés puis des simulations avec des instances petites et grandes. Ensuite, nous proposons des expériences sur des bancs d'essai réels et les résultats obtenus lors de l'hybridation d'ACO et de NSGA-III, puis les résultats de l'algorithme PSO basé sur le concept d'accents d'oiseaux et l'algorithme d'hybridation PSO et SMA. Enfin, nous présentons nos conclusions ainsi que nos perspectives et pistes de recherches futures.

# 3 Etude bibliographique et principales contributions

Le but de cette thèse est de proposer des hybridations et modifications des algorithmes d'optimisation évolutionnaire dans le but de réaliser le positionnement adéquat des nœuds dans les réseaux de capteurs sans fil avec satisfaction d'un ensemble de contraintes et objectifs.

## 3.1 Étude bibliographique

En première étape on a réalisé une étude bibliographique approfondie portant sur les méthodes d'optimisation du déploiement dans les réseaux de capteurs sans fil, particulièrement le déploiement 3D à l'intérieur.

### 3.1.1 Travaux en relation avec la problématique de déploiement 2D-3D

Plusieurs travaux récents ont proposé des algorithmes d'optimisation évolutifs pour un déploiement efficace des nœuds WSN. (Banimelhem et al., 2013) proposent un algorithme génétique (AG) pour résoudre le problème des trous de couverture et du déploiement 2D déterministe dans les WSN. L'objectif est de minimiser le nombre de nœuds mobiles. Cependant, aucune modélisation mathématique n'est donnée au problème. (Danping et al., 2013) proposent un algorithme évolutif multi-objectif combiné à une heuristique à bas coût pour résoudre le problème du signal et de la propagation radio en intérieur avec un scénario de déploiement en 3D. L'objectif est d'optimiser la couverture, la qualité de la liaison, la durée de vie et le coût du matériel. Cependant, l'évolutivité de l'approche proposée n'est pas prouvée. Ko and Gagnon (2015) suggèrent un AG reposant sur un schéma d'analyse du croisement pour résoudre le déploiement dans des terrains 3D irréguliers. L'objectif est de maximiser la couverture probabiliste des points et la couverture globale. En revanche, ils n'ont pas prouvé que la stratégie de croisement proposée est meilleure que l'approche génétique originale. Alia and Al-Ajouri (2017) proposent un algorithme basé sur une recherche d'harmonie
pour optimiser le nombre de capteurs déployés et la couverture. L'inconvénient de ce travail est que le modèle de réseau proposé est simpliste. De plus, seuls deux objectifs sont considérés et la validation de l'approche est basée uniquement sur des tests Matlab, sans scénario de simulation ou d'expérimentation du monde réel.

### 3.1.2 Travaux en relation avec l'hybridation par les procédures de préférence des utilisateurs et la réduction de dimensionnalité

De nombreuses recherches récentes ont suggéré des approches évolutives, telles que les algorithmes génétiques (AG) pour garantir un déploiement efficace dans les RCSF. Cependant, cette étude est basée sur une simple comparaison entre les deux algorithmes mentionnés et les évaluations ne s'appuient que sur des simulations sans validations expérimentales. (Unaldi et al., 2017) ont proposé un algorithme basé sur une mutation aléatoire et une transformée d'ondelette guidée pour résoudre le problème du déploiement probabiliste de nœuds dans des terrains 3D. L'objectif est de maximiser la qualité de la couverture et de minimiser le nombre de capteurs. Cependant, la méthode proposée est évaluée à l'aide de capteurs stationnaires et aucun environnement dynamique n'est utilisé. De plus, cette étude n'est pas validée par des scénarios empiriques sur un problème du monde réel. En outre, des simulations sont réalisées sans utiliser des mesures d'évaluation connues telles que l'IGD (Coello et al 2002) ou l'Hypervolume (Zitzler al., 1999) pour évaluer la performance de l'approche. Concernant les algorithmes évolutifs, Zhang et al. (2018) ont proposé d'injecter le hasard dans la population pour mieux contrôler la diversité. Ils ont proposé un algorithme génétique appelé (BEGA) basé sur une matrice de similarité (SGM). Bien que BEGA soit comparé à différents autres variantes génétiques pour douze benchmarks, aucun test sur des problèmes industriels réels n'est proposé et aucune preuve d'efficacité de son application dans les problèmes à grande échelle n'est donnée. En ce qui concerne l'incorporation des préférences de l'utilisateur dans des algorithmes d'optimisation à objectifs multiples, un algorithme appelé *Prio-ε-Preferred* basé sur une relation *ε-preferred* est proposé par (Drechsler et al., 2015). Cependant, pour prouver l'efficacité de l'algorithme suggéré, il est comparé uniquement à l'algorithme standard NSGA-II et il n'y a aucune comparaison avec d'autres approches de préférences de l'utilisateur.

### 3.1.3 Travaux en relation avec l'hybridation des PSO et SMA

Différentes études suggèrent divers schémas pour hybrider l'OEP (Optimisation par Essaim Particulaires) et les SMA (Systèmes multi-agents). Kolomvatsos and Hadjieftymiades (2014) proposent dans un algorithme OEP reposant sur des négociations intelligentes et simultanées entre un agent acheteur et un agent vendeur pour réaliser une transaction d'achat. L'algorithme OEP a été exécuté sur chaque thread avec une stratégie d'intelligence de l'essaim pour obtenir l'accord optimal. Cependant, seulement deux objectifs sont considérés dans cette étude. Dans (Wu et al., 2015), un système multi-agent basé sur une approche d'optimisation par l'essaim de particules (MAPSO) est utilisé pour résoudre le problème de la distribution de la charge économique des systèmes d'alimentation. En effet, chaque agent coopère avec ses voisins pour ajuster sa capacité de recherche globale et sa capacité d'exploration locale. Bien que les résultats indiquent que cet algorithme a une grande précision et vitesse de convergence par rapport aux autres algorithmes évolutionnaires, cet algorithme doit être testé sur un problème du monde réel avec un plus grand nombre d'objectifs et une dimension du problème plus élevée. De plus, la modélisation du problème n'est pas présentée. Dans (Ahmad et al., 2007), les auteurs proposent un autre algorithme OEP basé sur un SMA. Avec un degré d'apprentissage plus élevé et une exécution asynchrone, les particules de cet algorithme ont plus d'autonomie que les particules dans l'OEP standard. L'environnement de ces particules d'agent est modélisé comme un groupe de points non-optimaux. Les auteurs ont également mis en œuvre une variante parallèle de l'algorithme proposé, qui est plus efficace mais ayant
une complexité algorithmique plus élevée. Une autre étude qui combine l'OEP, les SMA et les AG a été proposée dans (Peng et al., 2008). Les auteurs suggèrent l'intégration des approches mentionnées pour résoudre le problème de la génération automatique de papier de test dans un environnement informatique parallèle. L'architecture multi-agent proposée est basée sur un nœud distant, un nœud central et un ensemble d'agents appelés *TPAgents* qui contrôlent les opérations d'évolution de chaque génération de population dans l'AG. Pour minimiser le coût de la communication entre les nœuds, une évaluation de la condition physique est effectuée par *TPAgents* au niveau des nœuds locaux. Seule la meilleure particule locale et sa fonction d'adaptation (*fitness*, en anglais) locale correspondante sont envoyées au nœud central pour calculer la meilleure particule globale. Pour échapper aux optimum locaux, la meilleure particule globale est transmise aléatoirement au nœud distant. Bien que l'approche proposée soit efficace, son évolutivité n'est pas prouvée et le nombre d'agents utilisés est assez faible. De même, aucun déploiement d'application réelle basée sur un système prototype n'est proposé. Dans (Kumar et al., 2011), un algorithme d'optimisation d'essaim de particules multi-agent hybridé avec un processus de prise de décision d'abeilles est proposé pour résoudre le problème de répartition de puissance. L'avantage de cette étude est que l'algorithme proposé est performant avec différentes fonctions objectives et sur des problèmes d'optimisation non contraints. Cependant, le temps de convergence de cet algorithme augmente considérablement si le nombre d'agents augmente.

Tous les travaux mentionnés ci-dessus utilisent des schémas d'hybridation simplistes basés sur l'idée de modéliser la particule en tant qu'agent. La modélisation environnementale, la capacité des particules et les mécanismes d'interaction entre les agents sont souvent non spécifiés. Dans notre approche, nous visons à proposer un schéma d'hybridation plus sophistiqué des deux approches (OEP et SMA) en utilisant le nouveau concept d'accent.

## 3.2 Formulation mathématique

Dans la deuxième étape, une formulation mathématique vise la modélisation de la problématique. Il s'agit de fixer la fonction objective à optimiser, les variables de décision et les différentes contraintes à prendre en considération. Notre objectif est de minimiser le nombre de nœuds capteurs à utiliser et la consommation de l'énergie. Simultanément, on vise ainsi la maximisation de la durée de vie du réseau, mais aussi la couverture, la localisation et la connectivité. Une modélisation détaillée peut être consultée dans le troisième chapitre de ce rapport de thèse. Dans ce qui suit on explique nos propositions de différents schémas d'hybridation justifiés et de modifications entre les algorithmes d'optimisation pour mieux résoudre notre problématique.

## 3.3 Inclusion de la diversité

Dans une première approche, une mutation adaptative et des opérateurs de recombinaison avec des contraintes de croisement avec le voisinage sont proposées. L'utilisation d'un concept de fonctions de scalarisation multiples est introduit pour faire face : (i) à l'inefficacité des Algorithmes évolutionnaires multi-objectives à base de Pareto, (ii) à l'inefficacité de l'opération de recombinaison, et (iii) à l'augmentation exponentielle des coûts (temps et espace) lors de la résolution de problèmes à plusieurs objectifs dans le contexte du monde réel. Pour cela on propose des mécanismes d'inclusion de diversité qui se basent essentiellement sur les concepts suivants (pour plus de détails, consultez la section 3.3.2 du rapport):

**Concept de recombinaison avec le voisinage** : Dans le cas des problèmes MaOP (ayant un nombre d'objectives supérieur à trois), la dimension de l'espace objectif devient trop élevée, ce qui augmente la diversité de la population. Ainsi, les opérateurs de mutation et de
recombinaison deviennent inefficaces. D'où la possibilité qu'ils créent des individus qui ne sont pas sélectionnés comme parents. Par la suite, les algorithmes MaOA résolvant ce genre de problèmes deviennent plus efficaces si la recombinaison est effectuée avec un chromosome voisin et si les objectifs sont corrélés. En effet, le concept de voisinage utilisé repose sur les étapes suivantes:

- le calcul de la distance séparant les individus dans l'espace objectif,

- l'identification du sous-ensemble de $|P| \cdot N_s$ voisins les plus proches pour chaque individu, où $N_s$ est la taille du voisinage et P est la population. D'après QU (2013), $N_s$ entre 1/20 et 1/5 est préféré. Dans nos tests, on a fixé $N_s$ à 1/10.

**Concept de multi-opérateurs adaptatifs** : lors de la résolution des problèmes MaOP, les MaOA sont souvent incapables de trouver les opérateurs de mutation et de recombinaison appropriés en fonction des spécificités du problème à résoudre. Pour surmonter cette faiblesse, nous suggérons de faire varier l'opérateur utilisé de manière adaptative. En effet, la contribution d'un opérateur à l'itération précédente est prise en compte pour l'ajustement de sa probabilité d'être sélectionné lors des itérations suivantes. Par ailleurs, les informations de retour d'expérience des générations passées permettent de sélectionner les opérateurs dans les générations futures sans affecter l'aspect probabiliste des opérateurs.

## Résultats de l'utilisation des restrictions d'association de voisinage et d'opérateurs de recombinaison adaptative

Nous examinons l'effet de la stratégie proposée de recombinaison avec le voisinage et de multi-opérateurs adaptatifs. La performance de chaque algorithme est évaluée en utilisant la métrique Hypervolume (HV) (une valeur moyenne du HV sur 15 exécutions. La taille de la population dans MOEA/D est fixée à 1000. La probabilité de mutation est de 1/500 et la probabilité de recombinaison est de 0,8. La recombinaison est basée sur l'appariement avec les voisins et les objectifs sont corrélés. Le nombre de points de référence est fixé à 100. Le tableau B1 illustre les résultats obtenus.

<table><caption>Tableau B1 Valeurs HV optimales, moyennes et pires; en utilisant des opérateurs adaptatifs</caption><thead><tr><th></th><th>Nbr d'Obj</th><th>MOEA/D(PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="6">Bit-flip (mutation) / SBX (recombinaison)</td><td rowspan="3">4</td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td></tr><tr><td>0.976416</td><td>0.981426</td><td>0.978574</td><td>0.976422</td></tr><tr><td>0.976328</td><td>0.976124</td><td>0.976231</td><td>0.976346</td></tr><tr><td rowspan="3">8</td><td>0.969886</td><td>0.971841</td><td>0.966876</td><td>0.952886</td></tr><tr><td>0.969815</td><td>0.969822</td><td>0.966525</td><td>0.952835</td></tr><tr><td>0.969702</td><td>0.969723</td><td>0.966234</td><td>0.952803</td></tr><tr><td rowspan="6">Avec restrictions de voisinage et opérateurs adaptives</td><td rowspan="3">4</td><td>0.978678</td><td>0.983129</td><td>0.979697</td><td>0.977234</td></tr><tr><td>0.978133</td><td>0.981952</td><td>0.979342</td><td>0.976986</td></tr><tr><td>0.976253</td><td>0.980237</td><td>0.979032</td><td>0.976343</td></tr><tr><td rowspan="3">8</td><td>0.970489</td><td>0.971002</td><td>0.971234</td><td>0.953864</td></tr><tr><td>0.969932</td><td>0.970254</td><td>0.967751</td><td>0.953366</td></tr><tr><td>0.963231</td><td>0.968968</td><td>0.963268</td><td>0.953032</td></tr></tbody></table>

Les résultats obtenus avec différents nombres d'objectifs indiquent que le croisement avec le voisinage et l'utilisation des opérateurs adaptatifs améliorent considérablement la performance de recherche des solutions. En effet, des meilleurs résultats ont été obtenus pour différents nombres d'objectifs sur l'algorithme MOEA/DD. Lorsque le nombre d'objectifs augmente, l'avantage du MOEA/DD par rapport au MOEA/D devient plus clair. Néanmoins, comparée à d'autres algorithmes, MOEA/D améliore plus significativement la valeur moyenne du HV (avec et sans recombinaison avec des parents similaires). De plus, les résultats expérimentaux montrent que le croisement des parents similaires améliore la diversité sans détériorer la convergence.

## 3.4 L'incorporation de la réduction de dimensionnalité et de préférences

Dans une deuxième approche, l'incorporation des préférences est établie : en effet, dans le cas des problèmes du monde réel, connus comme ayant un grand nombre d'objectifs, la taille de la population et le nombre de solutions nécessaires dépendent exponentiellement du nombre
d'objectifs. Ainsi, les performances des algorithmes d'optimisation se détériorent lors de la
résolution de ce genre de problèmes. Pour résoudre ce défi, l'algorithme NSGA-III est hybridé
avec une stratégie interactive d'incorporation des préférences de l'utilisateur (PI-EMO-VF) qui
suit l'évolution des nouvelles solutions pour incorporer progressivement les préférences de
l'utilisateur. Dans ce travail, l'efficacité du NSGA-III est testée dans le cas de problèmes du
monde réel, et comparée à un autre algorithme récent à plusieurs objectifs (MOEA/DD). Dans
une troisième approche, un schéma d'hybridation justifié combine trois classes d'algorithmes à
objectifs multiples. Ces algorithmes sont basés sur les points de référence (NSGA-III,
MOEA/DD), l'agrégation (Two_Arch2) et la décomposition (MOEA/D) avec deux
procédures basées sur la réduction de dimensionnalité (MVU-PCA) et les préférences (PI-
EMO-PC). Le but de cette hybridation est de bénéficier des avantages de chaque méthode
pour résoudre notre problème complexe.

Intégration de PI-EMO-PC, de points Knee et de NL-MVU-PCA sur les EMO testées

Afin de surmonter les difficultés déjà mentionnées des MOA dans la résolution des MaOP,
nous proposons un schéma hybride justifié intégrant différentes approches (figure B1).

<figure><img src="image_85.png" /><figcaption>Figure B1 Les quatre étapes du schéma d'hybridation proposé</figcaption></figure>

Dans ce schéma, quatre classes de MaOEA sont combinées : à base d'agrégation, à base de
point de référence, à base de réduction et à base de préférence.

Au début, le MaOA est exécuté (MOEA/DD, NSGA-III ou Two-Arch2) tout en préservant la diversité en utilisant un mécanisme de voisinage adaptatif. Ainsi, un ensemble de solutions correspondant à l'optimisation de l'ensemble initial d'objectifs est obtenu. Sur cet ensemble, la réduction de dimensionnalité est effectuée et un ensemble de solutions correspondant à un plus petit ensemble d'objectifs est fourni. Ensuite, la procédure de préférence est établie.

En effet, les approches de préférence supposent qu'il n'existe pas d'objectifs redondants dans
le problème donné (Saxena et al., 2013). Ainsi, dans notre approche, la procédure de
réduction de la dimensionnalité est toujours effectuée avant d'appliquer les préférences du
décideur (DM).

Étant donné que la procédure PI-EMO-PC (Sinha et al., 2014) nécessite une « fenêtre » de
recherche suffisante, sa population d'entrée doit être choisie de manière à ce que la recherche
converge vers une solution conforme aux préférences du DM. Pour choisir la population
d'entrée pour notre procédure de préférence en garantissant un équilibre entre l'efficacité de
calcul et la convergence vers une solution unique, nous suivons les mêmes étapes que celles
indiquées dans (Sinha et al., 2013) : La population d'entrée est une population intermédiaire prise après l'exécution de Ng générations (50% de progrès) après l'application de la réduction. Après avoir identifié cette population d'entrée pour la procédure de préférence, un ensemble plus petit représentant ses membres est considéré, en utilisant le clustering k-means. Ces membres sont les premiers membres de la population du PI-EMO-PC.

## Notre algorithme de préférence hybride proposé PI-EMO-PC-INK: (PI-EMO-PC-Point idéal- point Nadir - points Knee)

Les préférences interactives sont les plus intéressantes puisqu'elles sont dynamiquement injectées dans le processus de sélection afin de guider en permanence la recherche. La figure B2 illustre la méthode hybride proposée basée sur la combinaison de préférences interactives implicites et explicites. Tout d'abord, le point idéal et le point Nadir sont respectivement obtenus en utilisant l'algorithme EC-NSGA-II (Deb et al., 2006) et en minimisant chaque objectif individuellement dans l'espace de recherche. Ensuite, un algorithme explicite basé sur PI-EMO-PC est exécuté si le DM a des préférences. Dans le cas contraire, un processus de préférence implicite visant à trouver des régions du genou basées sur le TKR-NSGA-II (Bechikh et al., 2011) est mis en œuvre. Lors de l'utilisation d'un algorithme explicite basé sur PI-EMO-PC, si le DM n'est pas satisfait mais qu'il est fatigué, la procédure exécute le processus pour trouver les régions knee précédemment indiquées. Par la suite, si le DM n'est pas encore fatigué, il modifie les niveaux d'aspiration du PI-EMO-PC afin d'intégrer de nouvelles informations sur ses préférences. Ces processus (PI-EMO-PC et TKR-NSGA-II) seront répétés si le DM n'est pas satisfait ou si le nombre maximal autorisé d'interventions autorisées n'est pas atteint. Dans les deux cas, lorsque le DM devient satisfait ou que le nombre maximal autorisé d'interventions autorisées est atteint, le processus global sera arrêté.

<figure><img src="image_86.png" /><figcaption>Figure B2 L'algorithme hybride proposé de préférences (PI-EMO-PC-INK)</figcaption></figure>

## PI-NSGA-III-VF (NSGA-III avec préférences interactives)

PI-EMO-VF (EMO progressivement interactive en utilisant la fonction de valeur) utilise une procédure générique qui peut être incorporée à tout algorithme d'optimisation multi-objectif évolutif (EMO). PI-EMO-VF utilise une fonction de valeur approximative qui est générée progressivement. Ainsi, après chaque nombre d'itérations (donc de générations) de l'algorithme EMO utilisé, un ensemble de solutions non dominées équitablement réparties est identifié, et on demande au DM de donner ses informations de préférences sur la relation entre les solutions. Dans un scénario idéal, le
DM fournit un classement complet des solutions (du meilleur au pire). Néanmoins, le DM peut donner une information partielle de préférence. Cette information aide à établir une fonction de valeur polynomiale croissante. Ensuite, suivant cette fonction de valeur, la condition d'arrêt est configurée.

## Résultats de l'effet d'hybridation des EMOs avec une approche de réduction de dimensionnalité

A partir des résultats présentés dans le tableau B2, pour quatre et huit objectifs, les valeurs HV trouvées en utilisant l'approche de réduction de dimension sont plus élevées que celles obtenues sans utiliser cette méthode en raison de la réduction du nombre d'objectifs de huit à cinq dans notre problème du monde réel. De plus, le taux d'amélioration du MOEA/D dépasse clairement ceux des autres algorithmes.

<table><caption>Tableau B2 Meilleures, moyennes et pires valeurs du HV avant et après l'application de réduction de dimensionnalité</caption><thead><tr><th></th><th>Nbr d'Obj Initial</th><th>Nbr d'Obj après réduction</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="3">Sans réduction</td><td rowspan="3">4 / 5</td><td rowspan="3">4 / 5</td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td></tr><tr><td>0.976416</td><td>0.981426</td><td>0.978574</td><td>0.976422</td></tr><tr><td>0.976328</td><td>0.976124</td><td>0.976231</td><td>0.976346</td></tr><tr><td rowspan="3">Avec L- PCA /NL-MVU-PCA</td><td rowspan="3"></td><td rowspan="3">3</td><td>0.994975</td><td>0.982897</td><td>0.982896</td><td>0.989352</td></tr><tr><td>0.991264</td><td>0.982542</td><td>0.982251</td><td>0.987144</td></tr><tr><td>0.980023</td><td>0.982231</td><td>0.982033</td><td>0.986021</td></tr><tr><td rowspan="3">Sans réduction</td><td rowspan="3">8</td><td rowspan="3">8</td><td>0.969886</td><td>0.971841</td><td>0.966876</td><td>0.952886</td></tr><tr><td>0.969815</td><td>0.969822</td><td>0.966525</td><td>0.952835</td></tr><tr><td>0.969702</td><td>0.969723</td><td>0.966234</td><td>0.952803</td></tr><tr><td rowspan="3">Avec L- PCA /NL-MVU-PCA</td><td rowspan="3"></td><td rowspan="3">4</td><td>0.971978</td><td>0.984986</td><td>0.969897</td><td>0.954237</td></tr><tr><td>0.970951</td><td>0.984158</td><td>0.961152</td><td>0.953654</td></tr><tr><td>0.970236</td><td>0.983943</td><td>0.960364</td><td>0.953028</td></tr></tbody></table>

## Résultats de l'hybridation des EMO avec la réduction de dimensionnalité et les préférences

Dans cette section, nous examinons l'effet de l'application de notre approche proposée pour intégrer à la fois la réduction de la dimensionnalité et les préférences du DM. Dans nos tests, le HV est calculé avec une population égale à 1000. La fonction de scalarisation utilisée pour MOEA/D et MOEA/DD est PBI (0.5). La probabilité de mutation est de 1/400 avec un indice de 50, et la probabilité de recombinaison est de 0,9 avec un indice de 5. Les opérateurs adaptatifs de mutation et de recombinaison sont employés avec des parents voisins. 8 objectifs corrélés sont utilisés (et pour chaque expérience de N objectifs, au moins N/2 objectifs sont corrélés). Nous utilisons 250 points de référence pour NSGA-III. Après l'application de l'approche de réduction, la préférence est appliquée à l'ensemble réduit d'objectifs. Les Tableaux B3 et B4 montrent les spécifications des solutions finales. Chaque exécution a une population initiale différente, qui est le résultat de l'application de notre procédure de réduction sur l'EMO concernée. $d_s$ est un paramètre défini par l'utilisateur représentant l'amélioration attendue des solutions obtenues à partir de la meilleure solution actuelle basée sur la fonction de valeur. TDMax est le nombre maximum d'appels de l'information de préférence introduite par le DM. Dans nos tests, $d_s = 0,01$ et TDMax = 30.

<table><caption>Tableau B3 Solutions moyenne obtenues (des valeurs objectives)</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th rowspan="2">Le point le plus préféré utilisé pour construire la valeur de la fonction objective</th><th colspan="4">Valeurs moyenne des fonctions objectives f<sub>i</sub></th></tr><tr><th>MOEA/D</th><th>NSGA-III</th><th>Two_Arch2</th><th>MOEA/DD</th></tr></thead><tbody><tr><td>f1</td><td>Nombre de noeuds nomades ajoutés</td><td>128.452</td><td>134.161</td><td>142.54</td><td>152.339</td><td>133.581</td></tr><tr><td>f2</td><td>Consommation d'énergie</td><td>3.857</td><td>3.998</td><td>4.021</td><td>4.056</td><td>3.962</td></tr><tr><td>f3 (redondant)</td><td>Coût de déploiement du matériel</td><td>85</td><td>88.468</td><td>96.184</td><td>93.923</td><td>88.646</td></tr><tr><td>f4 (redondant)</td><td>L'utilisation du réseau</td><td>1.00</td><td>0.946</td><td>0.796</td><td>0.849</td><td>0.962</td></tr><tr><td>f5</td><td>Taux de localisation</td><td>3.991</td><td>3.605</td><td>3.882</td><td>3.863</td><td>3.812</td></tr><tr><td>f6 (redondant)</td><td>Taux de couverture</td><td>5.865</td><td>4.189</td><td>4.984</td><td>4.235</td><td>5.572</td></tr><tr><td>f7</td><td>Durée de vie du réseau</td><td>4280</td><td>3885</td><td>3687</td><td>3956</td><td>4065</td></tr><tr><td>f8</td><td>Taux de connectivité</td><td>189.89</td><td>168.524</td><td>166.515</td><td>168.542</td><td>174.266</td></tr></tbody></table>

<table><caption>Tableau B4 Distance moyenne des solutions obtenues à partir des solutions les plus préférées</caption><thead><tr><th></th><th>MOEA/D</th><th>NSGA-III</th><th>Two_Arch2</th><th>MOEA/DD</th></tr></thead><tbody><tr><td>Précision</td><td>0.234</td><td>0.419</td><td>0.468</td><td>0.023</td></tr><tr><td>Nombre d'évaluations de fonctions</td><td>6321</td><td>7945</td><td>8231</td><td>5895</td></tr><tr><td>Nombre d'appels requis du DM</td><td>TD<sub>Max</sub></td><td>26</td><td>25</td><td>16</td></tr></tbody></table>
## Résultats des expérimentations sur PI-NSGA-III

Pour évaluer la connectivité (f8 dans notre modélisation, voir la section 3.2.2 du rapport), la qualité des liens (f10) et la localisation (f5), la métrique RSSI est utilisée puisque le modèle de localisation utilisé repose sur le protocole RSSI et Distance-Vector Hop. Ainsi, plus la puissance RSSI reçue est élevée, meilleure est la localisation. La figure B3 illustre la moyenne valeur de RSSI (une valeur en [0, 256] convertible en dBm) entre les nœuds (RSSI entre chaque nœud $i \in [1, 36]$ et les autres nœuds).

<figure><img src="image_87.png" /><figcaption>Figure B3 Taux moyens de RSSI</figcaption></figure>

## 3.5 Hybridation entre l'algorithmes de colonies de fourmis et l'algorithmes génétiques

Dans une quatrième approche, un nouvel algorithme hybride issu du comportement de recherche de fourmis et de la génétique est proposé. Il est basé sur la variante récente des algorithmes génétiques (NSGA-III) et l'algorithmes de colonies de fourmis (ACO). C'est la première fois que le NSGA-III et l'ACO sont intégrés dans une plateforme hybride. Aussi, au contraire des hybridations classiques, ces deux algorithmes fonctionnent en même temps et interagissent en utilisant la même population (la population initiale du NSGA-III est la population construite par les fourmis dans la phase initiale de l'ACO). Ensuite, les étapes de l'algorithmes des fourmis sont injectées dans le NSGA-III avec incorporation de plusieurs modifications du NSGA-III originale.

Malgré son efficacité, le NSGA-III a des difficultés à résoudre des problèmes d'optimisation mono-objectif et à deux objectifs. Ces difficultés concernent la faible pression de sélection que NSGA-III introduit dans les solutions non dominées d'une population lors de la résolution de problèmes à deux objectifs. De plus, les difficultés concernent la petite taille de la population et le processus de sélection aléatoire lors de la résolution de problèmes mono-objectifs (Ibrahim et al., 2016). De son côté, l'algorithmes ACO présente un inconvénient principal qui concerne la convergence vers les optimum locaux (Sim et al., 2003).

L'idée est donc de proposer un schéma d'hybridation utilisant ces deux algorithmes (NSGA-III et ACO) pour tirer parti de leurs forces et remédier à leurs inconvénients. Lors de l'hybridation de ces deux algorithmes, la plupart des études (Huang and Chne, 2013), (Shen 2016) utilisent la version standard et basique de l'algorithmes génétique. De plus, la plupart de ces études exécutent séquentiellement les deux algorithmes (le GA standard puis l'ACO, ou le contraire). Ainsi, la solution finale de l'un des deux algorithmes est la solution initiale de l'autre. Bien que ce schéma basique d'intégration améliore le taux de convergence ACO, celui-ci reste convergent de façon excessive, ce qui rend le problème de l'optimum local insoluble. Dans notre étude, nous proposons une plateforme où NSGA-III et ACO s'exécutent en même temps et interagissent avec la même population. Ainsi, les étapes de l'algorithmes de la fourmi sont injectées dans le NSGA-III avec incorporation de plusieurs modifications de ce dernier. Parmi ces modifications, la population initiale du NSGA III devient la population construite par les fourmis dans la phase initiale de l'ACO. Il convient de mentionner que c'est la première fois que NSGA-III et ACO sont intégrés dans une plate-forme hybride. De plus, il s'agit de la
première plate-forme utilisant un algorithme génétique et ACO hybride pour résoudre le problème du déploiement 3D en intérieur des nœuds. L'algorithme proposé, appelé AcNSGA-III, est illustré dans Algorithme 3.6 de la section 3.3.5 du rapport. Il s'agit d'un algorithme fourmi-génétique hybride qui effectue une sélection ACO optimale des nœuds, une mise à jour dynamique des phéromones et une stratégie de mutation. Il accélère la convergence globale afin d'accélérer la recherche locale ce qui permet de trouver plus rapidement les solutions adaptées au problème de déploiement 3D. La capacité de recherche globale et le caractère aléatoire des opérateurs génétiques sont garantis, ce qui garantit la conduite de l'opération de l'opérateur génétique dans la génération de routes par les fourmis si l'ACO converge rapidement. Ceci permet à ce dernier de trouver les conditions de convergence. Enfin, puisqu'il y a une faible probabilité que les fourmis et le processus NSGA-III produisent le même individu dans la même itération, l'individu est ajouté à la population à moins qu'il n'y existe pas.

**Résultats** : afin de mesurer la localisation, la métrique RSSI est utilisée puisque notre modèle de localisation est basé sur l'hybridation entre le RSSI et le protocole de localisation DVHop. Ainsi, plus le RSSI est élevé, meilleure est la localisation. Un voisin peut être ajouté à la table de voisinage d'un nœud uniquement si la valeur RSSI du nœud détecté est supérieure à un seuil prédéfini. Selon nos expérimentations réelles, on a fixé cette valeur à 90 (valeur RSSI entre 0 et 256 convertible en dBm). Initialement, les niveaux RSSI sont basés sur nos expériences empiriques. Ensuite, afin de garantir le dynamisme au sein du réseau, une perturbation de la valeur de RSSI est introduite via une fonction aléatoire. La figure B4 montre, pour différents nombres d'objectifs pris en compte par les algorithmes testés, la moyenne des valeurs RSSI mesurées pour tous les nœuds en relation avec le nœud mobile.

<figure><img src="image_88.png" /><figcaption>Figure B4 Comparaison des taux moyens de RSSI</figcaption></figure>

## 3.6 Nouveau concept d'accent d'oiseaux et hybridation entre l'essaim de particules à base d'accent d'oiseaux et les SMA

Dans une cinquième approche, l'algorithme d'optimisation de l'essaim de particules basé sur un nouveau concept d'accent d'oiseaux (appelé acMaPSO) est proposé. Le nouveau concept d'accent d'oiseaux est basé sur un ensemble d'oiseaux qui sont séparés en différents groupes d'accentuation par leur habitation régionale et qui sont classés en groupes selon leurs manières de chanter. Pour conserver la diversité de la population pendant la recherche, ce nouveau concept d'accent d'oiseau est introduit pour évaluer la capacité de recherche des particules dans leurs zones locales. Pour assurer que la recherche s'échappe des optimums locaux, les particules les plus expertes (les parents) "meurent" et sont régulièrement remplacées par des nouvelles particules qui sont aléatoirement générées.

On propose également de tester cette hybridation dans un milieu distribué. Pour cela, on propose d'hybrider l'algorithme acMaPSO avec un système multi-agent (SMA). La nouvelle variante (nommée acMaMaPSO) tire parti de la distribution et de l'interactivité des agents. L'architecture multi-agents est décentralisée puisqu'il s'agit d'un réseau ad-hoc. Cette architecture renferme trois types d'agents : un agent environnement, des agents d'essaim et des
agents oiseaux (ou agents particules). Ces agents possèdent des connaissances, des buts, des capacités et des plans d'actions différentes.

**L'algorithme acMaPSO proposée:** incluant le concept d'accent d'oiseaux sur le MaOPSO.
Les modifications proposées de l'OEP multi-objectif standard visent principalement à
surmonter les difficultés rencontrées lors de la résolution de problèmes complexes du monde
réel ayant généralement plusieurs optimums locaux. Dans notre approche, des changements
sont faits dans la topologie de l'essaim : afin d'éviter le caractère prématuré de l'algorithme
OEP standard (Kennedy and Eberhart, 1995), en plus de l'utilisation de la meilleure position
globale (gbest) et de la meilleure position personnelle de la particule (pbest), nous utilisons la
meilleure position de la zone locale autour de la particule, appelée le meilleur cluster (cbest).
En effet, selon des recherches récentes en biologie (Oesel et al., 2017), les oiseaux chanteurs
ont des accents régionaux exactement comme les êtres humains. En effet, la capacité de
chanter et de créer une chanson complète que les oiseaux possèdent est héritée en grande
partie de leurs parents. Des expériences ont montré que si ces oiseaux sont élevés en silence,
ils ne peuvent que crier. De plus, les oiseaux de différentes régions développent des accents
distincts. En imitant ce concept biologique, nous proposons une OEP basée sur une topologie
des catégories d'accent d'oiseaux chanteurs (acMaPSO). L'idée est que chaque groupe d'accent
possède des paramètres différents pour accélérer la convergence, ce qui améliore la
prévention des optimums locaux. Pour évaluer les capacités de recherche des particules dans
leurs zones locales, cet algorithme est basé sur ce nouveau concept d'accent où les particules
appartiennent à différentes communautés ou groupes. Pendant la recherche, les particules sont
séparées en groupes en fonction de leurs accents, comme le montre la figure B5. Pour
conserver la diversité de la population, les particules de chaque catégorie d'accent peuvent
sélectionner comme voisins seulement les particules les moins expérimentées (de leur propre
groupe ou des autres groupes).

<figure><img src="image_89.png" /><figcaption>Figure B5 Le choix du voisinage d'une particule Pa</figcaption></figure>

**acMaMaPSO : Un algorithme OEP hybride, multi-objectif, multi-agent, basé sur l'accent d'oiseaux**

acMaMaPSO est un nouvel algorithme qui combine les principales caractéristiques du acMaPSO et SMA. En effet, l'hybridation du PSO avec les SMA allie l'autonomie et les capacités d'apprentissage du SMA à la simplicité de l'OEP. En conséquence, les particules deviennent plus autonomes, plus intelligentes et plus capables de tirer profit de leur environnement. En collaborant entre eux, les agents développent une société pour atteindre un but commun ainsi que leurs propres objectifs individuels. Le processus de prise de décision du groupe dans le SMA correspond à la nature fondamentale d'une particule dans l'OEP. Par conséquent, l'hybridation proposée offre la possibilité de calculer et d'optimiser des problèmes complexes

**L'architecture SMA proposée** : l'architecture SMA proposée repose sur trois types d'agents :
l'agent d'environnement (agEnv), l'agent d'oiseau (agBird ou agParticle) et l'agent swarm (agSwarm ou agCommunity). En effet, après l'initialisation des paramètres, agEnv affecte
pour chaque *agBird* une position de départ dans l'espace problème et un ensemble de voisins. Ensuite, les agents d'oiseaux commencent à rechercher une solution optimale jusqu'à ce qu'un nombre maximum d'itérations soit atteint ou qu'une bonne fonction *fitness* soit trouvée. Chaque *agBird* vérifie si sa position actuelle est déjà visitée. Si oui, il n'évalue pas sa fonction de fitness et interroge ses voisins sur leurs *pBest* et leurs emplacements, puis interroge l'*agEnv* sur les emplacements des clusters voisins afin de calculer son *pBest* actuel et de mettre à jour sa position et sa vitesse. Si la position actuelle n'est pas visitée, l'oiseau (*agBird*) évalue la fonction *fitness*, marque le point actuel comme visité et met à jour sa position et sa vitesse. La procédure globale est illustrée à la figure B6.

<figure><img src="image_90.png" /><figcaption>Figure B6 L'architecture SMA proposée</figcaption></figure>

Pour évaluer le coût de déploiement (f1 dans notre modélisation, voir section 3.2.2) et la localisation (f5), la métrique RSSI est utilisée. La figure B7 illustre, pour différents nombres d'objectifs (à satisfaire par les algorithmes testés), les valeurs moyennes du RSSI mesurés pour tous les nœuds en connexion avec le nœud mobile. Ce RSSI moyen est une valeur dans [0, 256] convertible en dBm.

<figure><img src="image_91.png" /><figcaption>Figure B7 Taux moyens de RSSI des nœuds en connexion avec le nœud mobile</figcaption></figure>

Pour mesurer la couverture (f6), le FER (Frame Error Rate) est utilisé comme une métrique pour évaluer la qualité des liens entre les nœuds. Ainsi, plus le FER est bas, meilleure est la couverture. La figure B8 illustre, pour un nombre différent d'objectifs à satisfaire par les algorithmes testés, la moyenne des taux FER mesurés pour tous les nœuds en connexion avec (détectant / détecté par) le nœud mobile.
<figure><img src="image_92.png" /><figcaption>Figure B8 Taux moyens de FER des nœuds en connexion avec le nœud mobile</figcaption></figure>

## 4 Conclusions et interprétations

Les principales contributions de nos travaux de recherche et leurs résultats peuvent être résumées comme suit :

- Une étude bibliographique approfondie portant sur les méthodes d'optimisation du déploiement dans les réseaux de capteurs sans fil, particulièrement les algorithmes qui prennent en considération le déploiement 3D à l'intérieur. Cette étude couvre les méta-heuristiques à base d'essaim (optimisation par Essaim Particulaire, optimisation par colonies de fourmis), les algorithmes génétiques, la recherche tabou, le recuit simulé. L'étude traite aussi le cas mono-objectif et multi-objectif ; le cas statique et dynamique du déploiement.

- Une formulation mathématique qui vise la modélisation de la problématique. Il s'agit de fixer la fonction objective à optimiser, les variables de décision et les différentes contraintes à prendre en considération. Notre objectif est de minimiser le nombre de nœuds capteurs à utiliser et la consommation de l'énergie. Simultanément, on vise ainsi la maximisation de la durée de vie du réseau, mais aussi la couverture, la localisation et la connectivité.

- On propose aussi une mutation adaptative et des opérateurs de recombinaison qui favorisent le croisement avec le voisinage, et l'intégration d'un concept de fonctions scalarisation multiples dans les EMO à base de Pareto pour lutter contre l'inefficacité de la recombinaison et à l'augmentation des coûts en temps et en espace dans le cas des problèmes réelles à plusieurs objectifs. Les résultats obtenus montrent que pour la plupart des cas, l'algorithme d'agrégation (MOEA/DD) est plus efficace que les autres algorithmes testés (NSGA-II and NSGA-III) pour résoudre du déploiement 3D à l'intérieur. De plus, les résultats prouvent que la méthode adaptative de sélection des opérateurs de recombinaison et de mutation avec des restrictions de voisinage améliore la performance des algorithmes.

- Une première hybridation justifiée qui combine deux procédures basées sur les préférences des utilisateurs (PI-EMO-PC) et la réduction de dimensionnalité (MVU-PCA) avec des algorithmes d'optimisation appartenant à trois classes : algorithmes à base d'agrégation (Two_Arch2), à base de points de référence (MOEA/DD, NSGA-III) et à base de décomposition (MOEA/D). Pour évaluer les nouveaux algorithmes hybrides proposés, on a utilisé la métrique HV sur notre problème de déploiement ; et la métrique IGD sur des problèmes de tests théoriques tels que DTLZ. Ensuite, pour valider les observations théoriques, un ensemble de prototypages a été réalisés. Les résultats montrent la performance supérieure des algorithmes hybrides modifiés par rapport aux algorithmes originaux. On a constaté aussi d'autres découvertes intéressantes telles que la performance supérieure du MOEA/D par rapport à NSGA-III dans le cas d'objectifs corrélés.

- Une deuxième hybridation est proposée, qui combine une approche interactive d'incorporation des préférences de l'utilisateur (PI-EMO-VF) avec l'algorithme NSGA-III. Les résultats ont montré que l'algorithme hybride proposé dépasse pour certaines métriques d'évaluation (comme le nombre de voisins), la performance d'un autre algorithme récent d'optimisation avec plusieurs objectifs (MOEA/DD) sachant que la littérature (voir (Li et al. 2015) et (Yuan et al., 2016)) affirme que MOEA/DD donne de meilleurs résultats que le NSGA-III standards sur les problèmes théoriques.
- Une troisième hybridation est proposée, qui combine, pour la première fois, l’algorithme d’optimisation de colonies des fourmis (ACO) avec une variante récente des algorithmes génétiques (NSGA-III). L’avantage de ce schéma d’hybridation est que, au contraire des hybridations classiques, les deux algorithmes hybridés s’exécutent en même temps et peuvent interagir avec la même population. A partir des résultats, on peut déduire que l’algorithme proposé (acNSGA-III) surpasse les algorithmes NSGA-III et le ACO standards.

- Une autre modification proposée, consiste à introduire un nouveau concept d'accent d'oiseau dans l'algorithme d'optimisation de l'essaim de particules. Le nouvel algorithme est nommé acMaPSO. Ce nouveau concept se base sur l'idée de séparer l'essaim (la communauté des oiseaux) en différents groupes selon leurs accents. En effet, pour conserver la diversité de la population durant le processus de recherche de l'algorithme, ce concept d'accent évalue la capacité de recherche locale des particules et classifie les particules en différents groupes d'accent selon leur manière commune de chanter. La sélection des voisins de chaque particule peut s'effectuer parmi les particules du même groupe ou parmi d'autres groupes. Pour s'échapper aux optima locaux, les particules âgées "meurent" et sont remplacées périodiquement par des nouveau particules générées aléatoirement.

- Une quatrième hybridation proposée, consiste à distribuer l'algorithme acMaPSO en l'hybridant avec un multi-agent system (SMA). Le nouveau algorithme (acMaMaPSO) bénéficie de l'interactivité des particules (devenues des agents) et de la distribution. L'architecture multi-agents proposée se base sur trois types d'agents qui possèdent des connaissances et des plans d'actions différents : un agent environnement, des agents oiseaux (ou agents particules) et des agents d'essaim. Les deux algorithmes acMaPSO et acMaMaPSO sont très compétitifs par rapport à l'algorithme MOPSO. Les résultats obtenues montrent que les deux algorithmes proposés (acMaPSO et acMaMaPSO) atteignent (et dépassent pour des métriques d'évaluation spécifiques telles que le nombre de voisins), la performance de l'algorithme PSO standard et l'algorithme NSGA-III.

Les schémas d'hybridation précédemment mentionnés sont tous validés par des résultats numériques qui ont permis l'évaluation des algorithmes avec des métriques telles que l'hypervolume. Ensuite, des simulations complétées par des expérimentations réelles sur des *testbeds* ont été proposées. Enfin, les simulations sont confrontées aux expérimentations pour évaluer le comportement des algorithmes et prouver leur stabilité et leur efficacité.

Pour résumer, les indicateurs de performances utilisés pour justifier notre travail, les simulations et les prototypages réels mettent en évidence le très bon comportement de nos approches proposées et montrent l'efficacité de l'hybridation.

# 5 Perspectives et directions de recherche futures

Les perspectives de nos travaux sont multiples et plusieurs questions ouvertes restent à explorer. Nos perspectives concernent principalement deux classes : La première s'intéresse au développement de nouveaux schémas d'hybridation entre EMO et autres approches de résolution de déploiement. La seconde concerne les défis en relation avec le réseau, les expérimentations réelles et le prototypage.

## Perspectives d'hybridation :

- Selon ces auteurs (Deb et al., 2010), la procédure PI-EMO-VF renferme un nombre assez élevé de paramètres à initialiser auparavant par l'utilisateur, ce qui le rend sensible au paramétrage initial. D'où l'importance de proposer une version du PI-EMO-VF avec moins de paramètres.

- On peut aussi intégrer d'autres MOEA récents et d'autres procédures de réduction (autre que celle de MVU-PCA utilisé déjà) dans notre plate-forme pour évaluer leurs performances. A
cet égard, on peut incorporer l’algorithme KnEA (Zhang et al., 2015) et la procédure de réduction FS (Feature Selection) (Mitra et al., 2002).

- Bien que notre plateforme d'incorporation de réduction et préférences puisse réduire le nombre d'objectifs et par la suite la complexité du problème, elle semble elle-même complexe à implémenter et à mettre en œuvre. Par conséquent, pour montrer l'apport de son utilisation, une étude de la complexité algorithmique de notre approche hybride peut être menée.

- L'intégration des préférences dans des méta-heuristiques autre que les EA s'avère une piste prometteuse car différentes méta-heuristiques basées sur la population ont prouvé leurs performances dans la résolution de MOPs. On peut citer à ce propos le PSO et l'AIS.

- Afin d'aider le DM à naviguer dans des espaces multidimensionnels des problèmes à plusieurs objectives, des recherches peuvent être menées en ce qui concerne le développement de meilleurs outils de visualisation.

- Dans la suite du travail présenté dans cette thèse, on poursuit actuellement nos travaux en proposant un nouvel algorithme d'optimisation basé sur l'imitation des comportements des animaux sauvages dans leurs territoires, et son application sur notre problématique.

## Perspectives applicatives de réseau et de prototypage :

- Un des avantages du banc d'essai Ophelia que nous avons utilisé est qu'il est plus réaliste en termes de contraintes et conditions d'utilisation réelles, qu'une plate-forme ayant un grand nombre de nœuds uniformes tels que SmartSantander (Sanchez et al., 2014), IoTLab (Fleury et al., 2015) ou INDRIYA (Doddavenkatappa et al., 2011). Ces plateformes nous permettent de tester nos algorithmes en utilisant un nombre de nœuds plus grand (jusqu'à 1024 nœuds). Dans de futures études, afin de comparer nos résultats d'Ophelia avec d'autres plateformes de prototypages et afin de prouver l'évolutivité de notre approche, des tests sur la plateforme IoTLab sont envisageables puisque cette dernière permet de tester les mêmes métriques de nos expériences (Qualité de lien, RSSI,... etc)

- D'autres pistes de recherche peuvent être investiguées comme la résolution du redéploiement dynamique des nœuds avec prise en considération d'autres objectifs. Nous visons aussi à intensifier le réseau déployé en ajoutant de nouveaux nœuds pour mieux satisfaire la contrainte de localisation qui exige quatre voisins pour chaque cible. On pourrait refaire par la suite nos expériences pour avoir une idée sur l'influence de la densité du réseau sur les résultats. Néanmoins, l'implémentation de la localisation par DV-Hop RSSI est aussi intéressante à évaluée réellement.

- Une autre contribution future concerne l'implémentation d'un modèle énergétique plus réaliste avec OMNeT++, en se basant sur la gestion des valeurs BO et SO (Farhad et al., 2016) du protocole CSMA/CA 802.15.4 par exemple.

- Malgré son efficacité, OpenWiNo a le défaut de manque de bibliothèques qui implémentent les protocoles standards, d'où l'intérêt d'inclure et implémenter d'autres protocoles de transmission et technologies dans OpenWiNo.

Finalement, vu le succès de l'utilisation de l'optimisation multi-objectif dans la résolution de plusieurs problèmes du monde réel ayant des objectifs souvent nombreux et conflictuels, le moment est venu pour pousser son utilisation dans des domaines d'applications différents, dynamiques et complexes.
## Contributions to the optimized deployment of connected sensors on the Internet of Things collection networks

IoT collection networks raise many optimization problems; in particular because the sensors have limited capacity in energy, processing and memory. In order to improve the performance of the network, we are interested in a contribution related to the optimization of the 3D indoor deployment of nodes using multi-objective mathematics models relying on hybrid meta-heuristics. Therefore, our main objective is to propose hybridizations and modifications of the optimization algorithms to achieve the appropriate 3D positioning of the nodes in the wireless sensor networks with satisfaction of a set of constraints and objectives that are often antagonistic. We propose to focus our contribution on meta-heuristics hybridized and combined with procedures to reduce dimensionality and to incorporate user preferences. These hybridization schemes are all validated by numerical tests. Then, we proposed simulations that are completed by, and confronted with experiments on real testbeds.

**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.

## Contributions au déploiement optimisé des capteurs connectés dans les réseaux de collecte de l'Internet des Objets

Les Réseaux de collecte de l'IoT soulèvent de nombreux problèmes d'optimisation, à cause des capacités limitées des capteurs en énergie, en traitement et en mémoire. Dans l'optique d'améliorer la performance du réseau, nous nous intéressons à une contribution liée à l'optimisation du déploiement 3D d'intérieur des nœuds sur les réseaux de capteurs sans fil en utilisant des méta-heuristiques hybrides se basant sur des modèles mathématiques multi-objectif. L'objectif principal est donc de proposer des hybridations et modifications des algorithmes d'optimisation dans le but de réaliser le positionnement 3D adéquat des nœuds dans les réseaux de capteurs sans fil avec satisfaction d'un ensemble de contraintes et objectifs qui sont souvent antagonistes. Nous proposons d'axer notre contribution sur les méta-heuristiques hybrides et combinés avec des procédures de réduction de dimensionnalité et d'incorporation de préférences des utilisateurs. Ces schémas d'hybridation sont tous validés par des résultats numériques de test. Ensuite, des simulations complétées par; et confrontées à des expérimentations sur des testbeds réelles.

**Mots-clés:** algorithmes génétiques, algorithme de colonie de fourmis, déploiement 3D à l'intérieur, hybridation, méta-heuristique, optimisation par essaim de particules, préférences d'utilisateur, réduction de la dimensionnalité, réseaux de collecte IoT, validation expérimentale.