# Modélisation et Optimisation des réseaux sans fil: De l'usage des drones aux réseaux LoRaWAN

Christelle Caillouet

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

To cite this version:

Christelle Caillouet. Modélisation et Optimisation des réseaux sans fil: De l'usage des drones aux réseaux LoRaWAN. Informatique [cs]. Université Côte D'Azur, 2024. tel-04602211

HAL Id: tel-04602211

https://inria.hal.science/tel-04602211

Submitted on 6 Jun 2024

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.

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

Distributed under a Creative Commons Attribution 4.0 International License
UNIVERSITÉ
CÔTE D'AZUR

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

ÉCOLE DOCTORALE
SCIENCES ET
TECHNOLOGIES DE
L'INFORMATION ET DE
LA COMMUNICATION

# HABILITATION À DIRIGER LES RECHERCHES

## Modélisation et Optimisation des réseaux sans fil: De l'usage des drones aux réseaux LoRaWAN

### Christelle CAILLOUET

Laboratoire d'Informatique, de Signaux et Systèmes de Sophia Antipolis (I3S)
UMR7271 UniCA CNRS

**Présentée en vue de l'obtention de**
l'habilitation à diriger les recherche
en Informatique

**Soutenue le :** 27 mars 2024

**Devant le jury, composé de :**

Walid DABBOUS, Directeur de Recherche,
Inria d'Université Côte d'Azur
André-Luc BEYLOT, Professeur, Toulouse
INP

Isabelle GUÉRIN LASSOUS, Professeure,
Université Lyon 1

Samer LAHOUD, Associate Professor, Dal-
housie University, Canada

Andrzej DUDA, Professeur, Grenoble INP

Hervé RIVANO, Professeur, INSA Lyon

Catherine ROSENBERG, Professor, Univer-
sity of Waterloo, Canada
<figure><img src="image_4.png" /></figure>
# MODÉLISATION ET OPTIMISATION DES RÉSEAUX SANS FIL: DE L'USAGE DES DRONES AUX RÉSEAUX LORAWAN

## Modelling and Optimizing wireless networks: FANET and LoRaWAN

### Christelle CAILLOUET

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

### Jury :

#### Président du jury

Walid DABBOUS, Directeur de Recherche, Inria d'Université Côte d'Azur

#### Rapporteurs

André-Luc BEYLOT, Professeur, Toulouse INP

Isabelle GUÉRIN LASSOUS, Professeure, Université Lyon 1

Samer LAHOUD, Associate Professor, Dalhousie University, Canada

#### Examinateurs

Andrzej DUDA, Professeur, Grenoble INP

Hervé RIVANO, Professeur, INSA Lyon

Catherine ROSENBERG, Professor, University of Waterloo, Canada
Christelle CAILLOUET

Modélisation et Optimisation des réseaux sans fil: De l'usage des drones aux réseaux LoRaWAN

viii+113 p.
Remerciements

Merci tout d'abord à André-Luc, Isabelle et Samer d'avoir évalué ce manuscrit et d'avoir été
membre du jury avec Andrzej, Walid, Hervé et Catherine. Votre regard et vos remarques sur mes
travaux sont précieux.

Évidemment un grand merci à toute l'équipe Coati dans laquelle j'ai plaisir à venir travailler tous les jours. Nous sommes une grande équipe mais nous avons tous nos complémentarités. Merci à David pour son management et sa collaboration, Majus pour ses dessins et ses encouragements sans faille pour que je rédige ce manuscrit, Minus pour les discussions sportives (à défaut d'en faire), Michel pour les soirées au pub et les anecdotes (sur des nouvelles personnes maintenant qu'il n'est plus à l'IUT), Nico pour sa participation active aux soirées Koh Lanta, Joanna pour nos discussions et son courage à surmonter tous les évènements de l'IUT (et les incursions de Majus dans son bureau), Stéphane pour les discussions scientifiques, Emanuele, André et Chuan avec qui j'espère pouvoir collaborer, et nos vétérans toujours présents (en période hivernale). Jean-Claude, j'espère un jour co-signer un papier avec toi !

Merci également à tous mes collaborateurs. Pour cela merci au GDR RSD, André-Luc, Thomas, vous avez dirigé une structure qui m'a permis de rencontrer plein de gens avec qui j'ai le plaisir de travailler. C'est un plaisir d'œuvrer à son maintien et son évolution. Dans l'ordre chronologique, merci à Tahiry, grâce à toi j'ai réussi à retrouver une thématique de recherche qui m'a sortie de la spirale des responsabilités pédagogiques et administratives afin de me reconcentrer sur des problématiques de recherche motivantes. Merci à Martin, Franck et Andrzej, découvrir les réseaux LoRaWAN avec vous a été un plaisir. Nous avons encore tant à faire. Merci à Géraldine, Nicolas avec qui j'ai travaillé sur les réseaux SDN. Que le PEPR nous apporte de futures collaborations fructueuses ! Merci à Yann pour ses idées innovantes qui permettent d'avancer et à sa collaboration avec Igor. Merci à Oana, Fabrice et Alexandre pour toutes les discussions enrichissantes qui ont permis d'améliorer mon modèle semaine après semaine, année après année... Nous allons arriver à finaliser un joli travail. Toutes ces personnes sont maintenant des amis, et c'est ce qui rend ce métier si attachant et passionnant.

Merci à Igor qui m'a permis de découvrir les joies de l'encadrement doctoral. La période n'était pas la plus propice avec la crise du Covid mais nous avons réussi à mener ton projet à terme. Encore félicitations à toi pour ta thèse et je te souhaite plein de bonnes choses pour ta future carrière.

Merci à Franck (youpi, j'ai réussi à soutenir avant toi !), malgré la distance nous réussissons à avancer, j'espère encore pour longtemps.

Merci à mes enfants, Gaspard et Joris, et à mes parents qui sont toujours là pour nous.
<figure><img src="image_6.png" /></figure>
# Table des matières

<table><tr><td>1</td><td>Introduction générale</td><td>1</td></tr><tr><td>1.1</td><td>Mes activités d'enseignement</td><td>1</td></tr><tr><td>1.2</td><td>Mes activités de recherche</td><td>2</td></tr><tr><td>1.2.1</td><td>Optimiser les réseaux sans fil : ma philosophie de recherche</td><td>2</td></tr><tr><td>1.2.2</td><td>Synthèse de mes recherches</td><td>3</td></tr><tr><td>1.3</td><td>Structure du document</td><td>4</td></tr><tr><td>1.4</td><td>Mes publications depuis 2013</td><td>5</td></tr></table>

## Réseaux de Drones (Flying Ad-Hoc Networks FANETs)

<table><tr><td>2</td><td>Supervision par drone et connectivité</td><td>11</td></tr><tr><td>2.1</td><td>Les réseaux aériens</td><td>14</td></tr><tr><td>2.1.1</td><td>Domaines d'applications</td><td>15</td></tr><tr><td>2.2</td><td>Défis et opportunités</td><td>16</td></tr><tr><td>2.3</td><td>Déploiement de drones connectés pour la couverture de cibles fixes</td><td>18</td></tr><tr><td>2.3.1</td><td>Modélisation de la flotte de drones</td><td>19</td></tr><tr><td>2.3.2</td><td>Compromis coût de déploiement-altitude</td><td>20</td></tr><tr><td>2.3.3</td><td>Coût de la connectivité</td><td>22</td></tr><tr><td>2.3.4</td><td>Déploiement auto-organisé</td><td>24</td></tr></table>

<table><tr><td>3</td><td>Optimisation du suivi de capteurs mobiles</td><td>29</td></tr><tr><td>3.1</td><td>Un modèle dynamique discret</td><td>32</td></tr><tr><td>3.2</td><td>Compromis énergie-distance</td><td>33</td></tr><tr><td>3.3</td><td>Vers un modèle plus efficace</td><td>37</td></tr><tr><td>3.3.1</td><td>Programme Maître : Assurer la couverture des nœuds mobiles</td><td>37</td></tr><tr><td>3.3.2</td><td>Programme Auxiliaire : Calculer efficacement de nouvelles trajectoires</td><td>38</td></tr><tr><td>3.3.3</td><td>Efficacité de la génération de colonnes</td><td>40</td></tr></table>

<table><tr><td>4</td><td>Recharge énergétique de capteurs par des drones</td><td>43</td></tr><tr><td>4.1</td><td>Utiliser les drones comme source de signaux radio-fréquence</td><td>45</td></tr><tr><td>4.2</td><td>Un modèle énergétique réaliste</td><td>46</td></tr><tr><td>4.3</td><td>Une approche en deux étapes</td><td>48</td></tr><tr><td>4.3.1</td><td>Déterminer l'ensemble optimal des positions</td><td>48</td></tr><tr><td>4.3.2</td><td>Optimiser les trajectoires sans conflits</td><td>50</td></tr></table>

## Réseaux Longue Portée LoRa (LoRaWAN)

<table><tr><td>5</td><td>Capacité des réseaux LoRaWAN</td><td>59</td></tr><tr><td>5.1</td><td>Principes de base des réseaux LoRa</td><td>62</td></tr></table>
<table><tbody><tr><td>5.2</td><td>Enjeux scientifiques</td><td>64</td></tr><tr><td>5.3</td><td>Capacité d'une cellule LoRaWAN</td><td>65</td></tr><tr><td>5.3.1</td><td>Modèle de propagation</td><td>65</td></tr><tr><td>5.3.2</td><td>Hypothèse d'un trafic saturé</td><td>66</td></tr><tr><td>5.3.3</td><td>Indicateur de performance de la capacité</td><td>67</td></tr><tr><td>5.3.4</td><td>Améliorations pour une meilleure mesure de la capacité</td><td>69</td></tr><tr><td><b>6</b></td><td><b>Optimisation de l'allocation des facteurs d'étalement (SF)</b></td><td><b>71</b></td></tr><tr><td>6.1</td><td>Application directe des modèles analytiques</td><td>74</td></tr><tr><td>6.2</td><td>Déterminer les limites des SF de manière équitable</td><td>74</td></tr><tr><td>6.2.1</td><td>Efficacité par rapport à la sensibilité</td><td>75</td></tr><tr><td>6.2.2</td><td>Précision du modèle</td><td>76</td></tr><tr><td>6.2.3</td><td>Passage à l'échelle</td><td>77</td></tr><tr><td>6.3</td><td>Allocation optimale avec effet de capture, orthogonalité imparfaite, et macro-diversité</td><td>77</td></tr><tr><td>6.3.1</td><td>Modélisation du point de vue des nœuds.</td><td>78</td></tr><tr><td>6.3.2</td><td>Programme linéaire en nombres entiers pour l'allocation optimale</td><td>79</td></tr><tr><td>6.3.3</td><td>Analyse des résultats</td><td>80</td></tr><tr><td><b>7</b></td><td><b>Ordonnancement des communications dans LoRaWAN</b></td><td><b>83</b></td></tr><tr><td>7.1</td><td>Vers un ordonnancement des communications LoRa</td><td>85</td></tr><tr><td>7.2</td><td>Le problème d'ordonnancement optimal</td><td>87</td></tr><tr><td>7.3</td><td>Intérêt du modèle optimal</td><td>88</td></tr><tr><td><b>8</b></td><td><b>Conclusion et Perspectives</b></td><td><b>91</b></td></tr><tr><td>8.1</td><td>Les limites de nos modèles</td><td>93</td></tr><tr><td>8.2</td><td>Prendre en compte la dynamique</td><td>95</td></tr><tr><td>8.3</td><td>De nouvelles techniques d'optimisation</td><td>96</td></tr><tr><td>8.4</td><td>Perspectives dans les réseaux</td><td>96</td></tr><tr><td>8.4.1</td><td>Travaux en cours</td><td>97</td></tr><tr><td>8.4.2</td><td>Perspectives pour les réseaux aériens</td><td>98</td></tr><tr><td>8.4.3</td><td>Perspectives pour les réseaux LPWAN</td><td>100</td></tr><tr><td>8.4.4</td><td>Les réseaux du futur</td><td>101</td></tr><tr><td><b>Références</b></td><td></td><td><b>103</b></td></tr><tr><td><b>Liste des figures</b></td><td></td><td><b>111</b></td></tr><tr><td><b>Liste des définitions</b></td><td></td><td><b>113</b></td></tr></tbody></table>
CHAPITRE 1

# Introduction générale

Ce manuscrit retrace mon parcours, et se concentre ensuite sur mes travaux de recherche réalisés depuis 2017 sur les réseaux de drones ainsi que les réseaux longue portée LoRaWAN. Depuis mon recrutement en tant que Maître de Conférences en Septembre 2011 au sein d'Université Côte d'Azur, dans l'équipe COATI commune à l'Inria et au laboratoire Informatique, Signaux et Systèmes de Sophia Antipolis (I3S, UMR7271), j'ai eu la chance de travailler avec de nombreuses personnes sur différents sujets, principalement les réseaux radio, mais également les réseaux micro-ondes, la virtualisation des réseaux, et même les réseaux de protéines en biologie. J'ai fait le choix de synthétiser les deux thématiques qui m'ont principalement occupée ces dernières années. Je retrace d'abord mes activités d'enseignement et de recherche (chapitre 1). Je détaille ensuite mes travaux de recherche réalisés depuis 2017 sur les réseaux de drones (chapitres 2-4) puis sur les réseaux LoRaWAN (chapitres 5-7). Finalement, dans la conclusion (chapitre 8), je discute des limites des modèles utilisés et donne diverses perspectives de recherche pour le futur.

## 1.1 Mes activités d'enseignement

Lors de mon recrutement en 2011, j'ai été affectée au département QLIO (Qualité, Logistique Industrielle et Organisation) de l'IUT Nice Côte d'Azur, où l'informatique est surtout un outil, dont les modules d'enseignement sont définis dans un programme pédagogique national (PPN). Durant 5 ans, j'ai enseigné la discipline Informatique en DUT 1ère et 2ème année, ainsi qu'en Licence Professionnelle "Management de la Logistique d'Entreprise". J'ai eu l'occasion de participer aux modules Outils bureautiques, Réseaux locaux, Création et fonctionnement d'un site web. J'ai également été responsable ou co-responsable des modules Conception des systèmes d'information, Bases de données et systèmes d'information logistiques, Recherche opérationnelle, Planification et ordonnancement des livraisons, pour lesquels je me suis investie dans l'élaboration des supports du cours, TD, TP, examens. J'ai assuré le suivi des stages de DUT, ainsi que des étudiants de licence professionnelle en contrat de professionnalisation. Parallèlement aux enseignements, j'ai pris activement part à la vie du département QLIO notamment en participant au processus de recrutement des étudiants (Studyrama, journées portes ouvertes, entretiens individuels), ainsi qu'au recrutement de personnel (responsable d'un comité de recrutement PRAG de Mathématiques, membre d'un autre), et au conseil de département. Dès 2013, j'étais directrice des études de 1ère année de DUT. En 2015, suite à l'élection d'un nouveau chef de département ayant le statut de PAST, j'ai été pendant 1 semestre chef de département adjointe.

En 2016, et à la suite de mon deuxième congé maternité, j'ai eu l'opportunité de changer volontairement de département d'enseignement pour intégrer le département Informatique de l'IUT Nice Côte d'Azur. Depuis la rentrée 2016, je fais partie de l'équipe pédagogique de ce département (participation aux salons d'orientation et aux journées portes ouvertes) et j'ai pris en charge
un module d'enseignement des Bases de Programmation Orientée Objet en 1ère année de DUT, ainsi que de nouvelles ressources avec l'apparition du diplôme du BUT (Automates et Langages BUT2, Méthodes d'optimisation pour l'aide à la décision BUT3). Je me suis donc de nouveau investie dans l'élaboration des supports d'enseignement, des examens, gestion des intervenants, et corrections des copies et projets. Je suis également intervenue dans des enseignements d'Introduc- tion à l'algorithmique et à la programmation (DUT1), Structures de données et algorithmes fonda- mentaux (DUT1), Introduction aux réseaux (DUT1), Compléments d'algorithmique (DUT2). Je participe au suivi des stages de BUT, et des étudiants en alternance. Ce département est bi-localisé entre Nice et Sophia Antipolis : la formation traditionnelle se trouve sur Nice, avec une soixan- taine d'étudiants en première année de BUT répartis en 5 groupes de TD/TP, et la formation en alternance est sur Sophia Antipolis avec un seul groupe d'une vingtaine d'étudiants par année. Je dois ainsi jongler entre ces deux localisations pour enseigner.

Ces dernières années j'ai également enseigné en M2 Recherche (commun Polytech et Master d'Informatique) Ubiquitous Networking (Ubinet (M2 Ubinet, s. d.)) un cours sur l'apprentissage par renforcement, en anglais, à des étudiants venant principalement de l'étranger. Je suis aussi co- responsable avec Dino Lopez Pacheco du module d'introduction à l'algorithmique et Programma- tion (IPA) à Polytech Nice Sophia, en première année du cycle ingénieur parcours Mathématiques Appliquées et Modélisation (MAM). Pour tous mes enseignements, j'ai participé au montage des sujets de cours, TD, et d'examen et à la surveillance et correction de ceux-ci. Je trouve et coord- donne les intervenants des groupes de TD/TP des enseignements dont je suis responsable. J'évalue le travail des étudiants en séance de TD sur des notions spécifiques. Nous devons donner au mini- mum deux notes par étudiant.

En plus de ces enseignements, j'ai encadré chaque année des étudiants de BUT Informatique 2ème année qui partent en stage entre avril et juin. Je supervise en moyenne 3-4 étudiants par an et je participe au jury de soutenance en fin d'année pour une dizaine d'étudiants. J'ai également suivi des étudiants en BUT en alternance (1 étudiant par an en moyenne).

1.2 Mes activités de recherche

1.2.1 Optimiser les réseaux sans fil : ma philosophie de recherche

Mes thématiques de recherche portent sur les techniques d'optimisation combinatoire appli-
quées aux réseaux de télécommunications, et plus principalement aux réseaux sans fil. J'ai débuté
mes recherches dans ce domaine lors de ma thèse, qui portait sur l'optimisation de la capacité
des réseaux radio maillés (Wireless Mesh Networks WMNs) (activités non détaillées dans ce do-
cument). J'ai souhaité poursuivre mes recherches sur ce type de réseaux car la spécificité des
communications radio apporte de nombreuses problématiques d'optimisation. Il faut d'abord as-
surer l'accès des nœuds au canal radio pour pouvoir transmettre, garantir la bonne réception des
transmissions radio et éviter les collisions. Mais on doit aussi optimiser un certain nombre de cri-
tères de qualité de service (durée, latence, consommation énergétique, ...), ainsi que les paramètres
physiques des nœuds (puissance de transmission, facteur d'étalement, ...).

Les recherches dans ce domaine sont multiples et nombreuses et se rangent systématiquement
dans deux catégories : théorique ou pratique, souvent mises en opposition, mais j'aime à penser
qu'elles sont complémentaires. J'aime m'entourer de personnes travaillant dans les domaines plus
appliqués afin de valider mes modèles et m'approcher toujours plus près du fonctionnement en
pratique. Néanmoins mes travaux sont de nature principalement théorique car je trouve important
de connaître les limites de fonctionnement des réseaux étudiés et de pouvoir évaluer l'efficacité de solutions approchées. Mes travaux sont complémentaires avec des études par simulation ou expérimentation. De plus en plus de travaux de recherche s'attellent à proposer une modélisation utilisant la programmation linéaire pour répondre à des problèmes d'optimisation concernant la planification ou le partage des ressources dans les réseaux de télécommunications. Cette modélisation est souvent sous-exploitée de part sa complexité trop élevée. De plus, les modèles ne sont même pas résolus et laissent plutôt la place à des propositions de solutions heuristiques dont on ne peut quantifier l'écart à l'optimal. Mon travail fait lui une grande part à la modélisation des systèmes et scénarios étudiés, et l'intérêt de nos modèles linéaires est toujours évalué, même sur de petites instances.

Proposer des modèles d'optimisation précis, évaluables sur des scénarios réalistes, et comparables avec ce qui se fait en pratique représente un défi important. Il est néanmoins nécessaire de faire des hypothèses de fonctionnement, et des choix de modélisation, qui peuvent parfois représenter des limites par rapport aux scénarios réels. En particulier, les réseaux radio peuvent être décentralisés, sont toujours dynamiques, et proposer une modélisation en programmation linéaire pour une optimisation centralisée peut s'avérer assez éloigné des préoccupations des opérateurs et des utilisateurs. Dans nos études, détaillées dans la suite de ce document, nous identifierons les hypothèses qui ont été les nôtres et leurs implications sur l'interprétation des résultats en pratique. Nous montrerons comment nos études de planification et d'allocation des ressources dans les réseaux aériens et LoRaWAN permettent d'identifier les limites de ces systèmes, et quantifier les équipements nécessaires à un fonctionnement optimal.

## 1.2.2 Synthèse de mes recherches

Les années qui ont suivi mon recrutement ont principalement été occupées avec la naissance de mes deux enfants, en janvier 2013 et mars 2016, et les nombreuses missions relatives à un enseignant-chercheur en début de carrière. Néanmoins j'ai eu des activités de recherche sur les réseaux de protéines avec des membres de l'équipe COATI (David Coudert et Stéphane Perennes), et en collaboration avec l'équipe ABS d'Inria (Frédéric Cazals) (Agarwal et al., 2013; Agarwal, Caillouet, Coudert, & Cazals, 2015). J'ai aussi obtenu des résultats sur les réseaux SDN avec Frédéric Giroire et Joanna Moulierac (COATI), et en collaboration avec l'équipe SIS d'I3S (Guillaume Urvoy-Keller et Dino Lopez Pacheco) (Rifai et al., 2015, 2016, 2017). J'ai aussi participé avec David Coudert à l'encadrement de la thèse d'Alvinice Kodjo, ce qui a donné lieu à deux publications sur les réseaux micro-ondes (Caillouet, Coudert, & Kodjo, 2013; Kodjo, Coudert, & Caillouet, 2014).

Grâce au GdR RSD du CNRS, j'ai obtenu une bourse de mobilité jeune chercheuse/jeune chercheur d'un mois afin de collaborer avec Tahiry Razafindralambo à l'Université de La Réunion. Ce n'était pas notre première collaboration puisqu'en 2011 nous avions publié un papier sur l'optimisation de la collecte de données multi-sauts dans des réseaux de capteurs sans fil. Nous avions commencé à travailler à distance sur le déploiement optimal de drones afin de couvrir des capteurs au sol. Ce séjour fut plus que fructueux puisqu'il a initié une de mes principales thématiques de recherche. Sur ce sujet, j'ai encadré la thèse d'Igor Dias Da Silva qui s'est déroulée d'octobre 2020 à septembre 2023 (co-encadrement à 80% avec David Coudert 20%). Sa thèse regroupe l'essentiel des derniers travaux réalisés ensemble et en collaboration avec Yann Busnel (IMT Atlan-tique à l'époque) sur l'optimisation des trajectoires de drones et de déploiement de réseau aérien
connecté mêlant programmation linéaire, génération de colonnes, algorithmique d'approximation (Dias Da Silva, 2023).

Dans toutes mes activités, j’ai eu à cœur de collaborer avec des chercheuses/chercheurs d’autres laboratoires. C’est un plaisir pour moi de mêler nos connaissances et développer des idées sur un sujet commun. Je peux ainsi principalement citer mes collaborations qui ont mené à la publication d’articles dans des conférences nationales ou internationales, ou des journaux internationaux à comité de lecture :

— Tahiry Razafindralambo (Univ. La Réunion) et Dimitrios Zorbas (Nazarbayev Univ., Kazakhstan) sur le déploiement de drones pour la couverture et la recharge de capteurs sans fil, fixes ou mobiles (Caillouet & Razafindralambo, 2017, 2018; Caillouet, Razafindralambo, & Zorbas, 2018; Caillouet, Giroire, & Razafindralambo, 2019; Caillouet, Razafindralambo, & Zorbas, 2019a, 2019b),

— Dimitrios Zorbas sur l'ordonnancement des communications LoRaWAN (Zorbas, Caillouet, Abdelfadeel, & Pesch, 2021);

— Yann Busnel (IMT Nord Europe) sur le déploiement distribué de drones connectés (Busnel, Caillouet, & Coudert, 2019a, 2019b, 2020) et l'optimisation du plan de vol de drones autonomes pour la recharge des capteurs (Dias da Silva, Busnel, & Caillouet, 2022, 2023);

— Andrzej Duda, Martin Heusse et Franck Rousseau (Grenoble INP) sur l'optimisation de la capacité d'une cellule réseau LoRaWAN (Heusse, Attia, Caillouet, Rousseau, & Duda, 2020; Caillouet, Heusse, & Rousseau, 2020b; Heusse, Caillouet, & Duda, 2022a, 2022b; Heusse & Caillouet, 2023; Heusse, Caillouet, & Duda, 2023) et sur l'optimisation de l'effectation des facteurs d'étalement (Caillouet, Heusse, & Rousseau, 2019, 2020a, 2021);

— Géraldine Texier (IMT Atlantique) sur l'optimisation du placement de services réseaux virtualisés (Morin, Texier, Caillouet, Desmangles, & Phan, 2019, 2020c, 2020b, 2020a)

— Nathalie Mitton sur un volume spécial portant sur l'optimisation et les communications dans les réseaux de drones (Caillouet & Mitton, 2020)

Pour toutes ces collaborations, j'ai pu apporter mon expertise en optimisation (principalement programmation linéaire), et bénéficier du savoir enrichissant de mes collaborateurs pour mener à bien des travaux de planification et de management des réseaux, principalement les réseaux de drones et les réseaux LoRaWAN. J'ai par ailleurs utilisé d'autres approches que l'optimisation, comme le développement d'algorithmes heuristiques, ainsi que l'algorithmique distribuée.

1.3 Structure du document

Ce manuscrit se découpe en deux parties. La première partie porte sur les réseaux sans fil aériens, dans lesquels un ensemble de drones est déployé autour d'une ou plusieurs passerelles fixes reliées au réseau de cœur. Les drones forment un réseau radio ad-hoc multi-sauts, assurant la connectivité entre la station de base et les objets connectés au sol.

Nous nous intéressons à la planification optimale d'un réseau de drones sur une zone à couvrir dans laquelle se trouvent des nœuds au sol. Le Chapitre 2 présente les drones et les problématiques qui ont émergé avec l'utilisation des réseaux aériens multi-sauts. Je me concentre ensuite sur le problème de couverture de cibles fixes par des drones positionnés à différentes altitudes, connectés entre eux et avec une station de base pour échanger continuellement de l'information, que nous avons abordé d'un point de vue de la programmation linéaire et de l'algorithmique distribuée. Le Chapitre 3 ajoute une dimension temporelle aux modèles en considérant des nœuds mobiles au
sol que le réseau aérien doit couvrir et connecter à la station de base en tout temps de surveillance. Pour cela nous avons utilisé la technique de génération de colonnes afin de résoudre efficacement ce problème de couverture connectée et générer rapidement les trajectoires des drones au cours du temps. Le Chapitre 4 présente une autre manière d'utiliser les drones, afin de recharger les batteries de nœuds au sol en envoyant des signaux radio-fréquence. Une approche en deux étapes nous a permis d'obtenir des résultats satisfaisants pour les trajectoires des drones assurant la recharge de tous les nœuds tout en évitant les conflits de positionnement et de recharge multiple qui en dégradent sa qualité.

Le seconde partie du manuscrit présente mes études des réseaux LoRaWAN (Long Range Wide Area Networks) faisant partie de la nouvelle génération des réseaux LPWAN (Low Power Wide Area Networks) apparus ces dernières années. Dans le Chapitre 5, je commence par présenter les caractéristiques des réseaux LoRaWAN, ainsi que les paramètres physiques des nœuds qui entrent en jeu pour l'évaluation du taux de livraison des paquets et de la capacité d'une cellule LoRa. Je présente les modèles analytiques que nous avons dérivés afin de modéliser au mieux le fonctionnement du réseau et estimer au plus près sa capacité. Le Chapitre 6 se concentre ensuite sur l'optimisation des facteurs d'étalement (Spreading Factors SF) des nœuds afin de maximiser la capacité du réseau. Nous abordons tout d'abord ce problème en nous limitant à l'optimisation des bornes des SF dans une cellule avec une seule passerelle, puis étendons le modèle en programmation linéaire afin de se placer du point de vue de chaque nœud, dans un réseau avec une ou plusieurs passerelles, et en prenant en compte les spécificités des collisions en LoRaWAN, à savoir l'effet de capture entre deux transmissions utilisant le même SF, et l'orthogonalité imparfaite des SF permettant la réception des trames simultanées utilisant des SF différents sous certaines conditions. Ces modèles permettent de montrer les avantages de ces réseaux à la fois en terme de portée de communication et dans la gestion des collisions. Le Chapitre 7 présente une proposition d'évolution du fonctionnement des réseaux LoRaWAN, en proposant un ordonnancement des communications avec des nœuds partageant une horloge commune contrôlée par la passerelle. Le programme linéaire optimal que j'ai proposé a permis de valider des algorithmes heuristiques testées ensuite par simulation et expérimentation.

Enfin, le Chapitre 8 présente une conclusion de mes études, en analysant les hypothèses que l'on a choisi et les limites de nos modèles que l'on doit dépasser. Mes travaux en cours et mes perspectives de recherche concluent enfin ce manuscrit.

## 1.4 Mes publications depuis 2013

Agarwal, D., Araujo, J., Caillouet, C., Cazals, F., Coudert, D., & Perennes, S. (2013, septembre). Connectivity Inference in Mass Spectrometry based Structure Determination. In H. Bodlaender & G. Italiano (Eds.), *European Symposium on Algorithms (ESA)* (Vol. 8125, p. 289-300). Sophia-Antipolis, France, France: Springer. doi: 10.1007/978-3-642-40450-4\_25

Agarwal, D., Caillouet, C., Coudert, D., & Cazals, F. (2015, avril). Unveiling Contacts within Macro-molecular assemblies by solving Minimum Weight Connectivity Inference Problems. *Molecular and Cellular Proteomics*, *14*, 2274-2284. doi: 10.1074/mcp.M114.047779

Busnel, Y., Caillouet, C., & Coudert, D. (2019a, décembre). Self-organized Disaster Management System by Distributed Deployment of Connected UAVs. In *6th International Conference*
on Information and Communication Technologies for Disaster Management (ICT-DM). Paris,
France.

Busnel, Y., Caillouet, C., & Coudert, D. (2019b, septembre). Self-organized UAV-based Super-
vision and Connectivity : Challenges and Opportunities. In *18th IEEE International Symposium
on Network Computing and Applications (NCA)*. Cambridge, MA, USA.

Busnel, Y., Caillouet, C., & Coudert, D. (2020, septembre). VESPA, ou l'art de coordonner une
flotte de drone sans leader. In *22èmes Rencontres Francophones sur les Aspects Algorithmiques
des Télécommunications (AlgoTel)*.

Caillouet, C., Coudert, D., & Kodjo, A. (2013, octobre). Robust optimization in multi-operators
microwave backhaul networks. In *4th Global Information Infrastructure and Networking Sym-
posium (GIIS)* (p. 1-6). Trento, Italy : IEEE.

Caillouet, C., Giroire, F., & Razafindralambo, T. (2018a, mai). Déploiement efficace de drones
pour la collecte de données de capteurs mobiles. In *Rencontres Francophones sur la Conception
de Protocoles, l'Évaluation de Performance et l'Expérimentation des Réseaux de Communication
(CoRes)*. Roscoff, France.

Caillouet, C., Giroire, F., & Razafindralambo, T. (2018b, avril). Optimization of mobile sen-
sor coverage with UAVs. In *11th International Workshop on Wireless Sensor, Robot and UAV
Networks (WiSARN) in conjunction with IEEE INFOCOM 2018*. Honolulu, Hawaii, USA.

Caillouet, C., Giroire, F., & Razafindralambo, T. (2019). Efficient Data Collection and Tracking
with Flying Drones. *Elsevier Adhoc networks*, 89(C), 35-46. doi: 10.1016/j.adhoc.2019.01.011

Caillouet, C., Heusse, M., & Rousseau, F. (2019, décembre). Optimal SF Allocation in LoRa-
WAN Considering Physical Capture and Imperfect Orthogonality. In *IEEE Global Communica-
tions Conference (GLOBECOM)*. Waikoloa, Hawaii, USA.

Caillouet, C., Heusse, M., & Rousseau, F. (2020a, juillet). Bringing Fairness in LoRaWAN
through SF Allocation Optimization. In *25th IEEE Symposium on Computers and Communica-
tions (ISCC)*. Rennes, France.

Caillouet, C., Heusse, M., & Rousseau, F. (2020b, septembre). Optimisation de la capacité des réseaux LoRa. In *5ème Rencontres Francophones sur la Conception de Protocoles, l'Évaluation de Performance et l'Expérimentation des Réseaux de Communication (CoRes)*.

Caillouet, C., Heusse, M., & Rousseau, F. (2021, mai). Optimiser l'équité dans les réseaux LoRaWAN. In *CORES 2021 - 6ème Rencontres Francophones sur la Conception de Protocoles, l'Évaluation de Performance et l'Expérimentation des Réseaux de Communication*. La Rochelle, France.

Caillouet, C., & Mitton, N. (2020). Optimization and communication in UAV networks. *MDPI
Sensors*, 20(18), 5036. doi: 10.3390/s20185036

Caillouet, C., & Razafindralambo, T. (2017, octobre). Efficient deployment of connected un-
manned aerial vehicles for optimal target coverage. In *8th Global Information Infrastructure and
Networking Symposium (GIIS)*. Saint Pierre, France.

Caillouet, C., & Razafindralambo, T. (2018, mai). Analyse bi-objectif pour la couverture de
cibles par des drones. In *Rencontres Francophones sur la Conception de Protocoles, l'Évaluation
de Performance et l'Expérimentation des Réseaux de Communication (CoRes)*. Roscoff, France.
Caillouet, C., Razafindralambo, T., & Zorbas, D. (2018, septembre). Recharging wireless sensor networks using drones and wireless power transfer. In *IEEE PIMRC, Recent Results track*. Bologne, Italy.

Caillouet, C., Razafindralambo, T., & Zorbas, D. (2019a, avril). Optimal placement of drones for fast sensor energy replenishment using wireless power transfer. In *Wireless Days (WD). Manchester, United Kingdom. (Best Paper Award)*

Caillouet, C., Razafindralambo, T., & Zorbas, D. (2019b, juin). Utiliser des drones pour recharger efficacement des capteurs. In *21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)*. Saint Laurent de la Cabrerisse, France.

Dias da Silva, I., Busnel, Y., & Caillouet, C. (2022, décembre). Trajectory Optimization for Fast Sensor Energy Replenishment using UAVs as RF sources. In *GLOBECOM 2022 - IEEE Global Communications Conference (p. 1-6)*. Rio de Janeiro / Hybrid, Brazil : IEEE. doi: 10.1109/GLOBECOM48099.2022.10001604

Dias da Silva, I., Busnel, Y., & Caillouet, C. (2023, mai). Optimisation de plan de vol de drones autonomes pour une recharge rapide de capteurs. In *AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications*. Cargese, France.

Dias Da Silva, I., & Caillouet, C. (2020, juin). Optimizing the trajectory of drones : trade-off between distance and energy. In *2nd International Workshop on Internet of Autonomous Unmanned Vehicles (IAUV) in conjunction with IEEE SECON 2020*. Cuomo, Italy.

Dias da Silva, I., & Caillouet, C. (2022, mai). Quand l'immobilisme coûte plus cher que l'échange. In *AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications*. Saint-Rémy-Lès-Chevreuse, France.

Dias da Silva, I., Caillouet, C., & Coudert, D. (2021, décembre). Optimizing FANET deployment for mobile sensor tracking in disaster management scenario. In *ICT-DM 2021 - 7th International Conference on Information and Communication Technologies for Disaster Management* (p. 134-141). Hangzhou, China : IEEE. doi: 10.1109/ICT-DM52643.2021.9664204

Heusse, M., Attia, T., Caillouet, C., Rousseau, F., & Duda, A. (2020, novembre). Capacity of a LoRaWAN Cell. In *23rd ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)*. Alicante, Spain.

Heusse, M., & Caillouet, C. (2023, mai). Ajustement du niveau de redondance des transmissions LoRaWAN. In *CoRes 2023 - 8èmes Rencontres Francophones sur la Conception de proto-coles, l'évaluation de performances et l'expérimentation de Réseaux de communication*. Cargese, France.

Heusse, M., Caillouet, C., & Duda, A. (2022a, septembre). Frame Arrival Timing in LoRaWAN : Capacity Increase With Repeated Transmissions and More Channel Attenuation. In *PIMRC 2022 - IEEE 33rd Annual International Symposium on Personal, Indoor and Mobile Radio Communications. Virtual Conference, Japan*.

Heusse, M., Caillouet, C., & Duda, A. (2022b, mai). Taux de réception en LoRaWAN et temporalité des arrivées : pouvez-vous parler moins fort et répéter ? In *CORES 2022 - 7ème Rencontres Francophones sur la Conception de Protocoles, l'Évaluation de Performance et l'Expérimentation des Réseaux de Communication*. Saint-Rémy-Lès-Chevreuse, France.

Heusse, M., Caillouet, C., & Duda, A. (2023). Performance of Unslotted ALOHA with Capture and Multiple Collisions in LoRaWAN. *IEEE Internet of Things Journal*. doi: 10.1109/JIOT.2023.3280393
Kodjo, A., Coudert, D., & Caillouet, C. (2014, février). Optimisation robuste pour le partage de réseaux d'accès micro-ondes entre opérateurs. In *ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision*. Bordeaux, France.

Morin, C., Texier, G., Caillouet, C., Desmangles, G., & Phan, C.-T. (2019, novembre). VNF placement algorithms to address the mono- and multi-tenant issues in edge and core networks. In *8th IEEE International Conference on Cloud Networking (Cloud-Net)*. Coimbra, Portugal.

Morin, C., Texier, G., Caillouet, C., Desmangles, G., & Phan, C.-T. (2020a, septembre). Algorithmes de placement de VNFs dans des contextes mono-et multi-propriétaire. In *22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)*.

Morin, C., Texier, G., Caillouet, C., Desmangles, G., & Phan, C.-T. (2020b, septembre). Optimisation du coût de déploiement de services réseau virtualisés dans le cloud. In *Rencontres Francophones sur la Conception de Protocoles, l'Évaluation de Performance et l'Expérimentation des Réseaux de Communication (CoRes)*.

Morin, C., Texier, G., Caillouet, C., Desmangles, G., & Phan, C.-T. (2020c, janvier). Optimisation of Network Services Embedding Costs over Public and Private Clouds. In *34th International Conference on Information Networking (ICOIN)*. Barcelona, Spain.

Rifai, M., Huin, N., Caillouet, C., Giroire, F., Moulierac, J., Lopez Pacheco, D., & Urvoy-Keller, G. (2015, décembre). Too many SDN rules? Compress them with MINNIE. In *IEEE GLOBECOM*. San diego, United States.

Rifai, M., Huin, N., Caillouet, C., Giroire, F., Moulierac, J., Lopez Pacheco, D., & Urvoy-Keller, G. (2016, mai). MINNIE : enfin un monde SDN sans (trop de) règles. In *18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)*. Bayonne, France.

Rifai, M., Huin, N., Caillouet, C., Giroire, F., Moulierac, J., Lopez Pacheco, D., & Urvoy-Keller, G. (2017). MINNIE : an SDN World with Few Compressed Forwarding Rules. *Computer Networks*, 121, 185 - 207. doi: https://doi.org/10.1016/j.comnet.2017.04.026

Zorbas, D., Caillouet, C., Abdelfadeel, K. Q., & Pesch, D. (2021). Optimal data collection time in lora networks : a time-slotted approach. *MDPI Sensors*, 21(1193). doi: 10.3390/s21041193
# Réseaux de Drones (Flying Ad-Hoc Networks FANETs)
<figure><img src="image_7.png" /></figure>
## CHAPITRE 2

# Supervision par drone et connectivité

<table><tr><td>2.1 Les réseaux aériens</td><td>14</td></tr><tr><td>2.1.1 Domaines d'applications</td><td>15</td></tr><tr><td>2.1.1.1 Surveillance</td><td>15</td></tr><tr><td>2.1.1.2 Sûreté</td><td>15</td></tr><tr><td>2.1.1.3 Santé</td><td>16</td></tr><tr><td>2.2 Défis et opportunités</td><td>16</td></tr><tr><td>2.3 Déploiement de drones connectés pour la couverture de cibles fixes</td><td>18</td></tr><tr><td>2.3.1 Modélisation de la flotte de drones</td><td>19</td></tr><tr><td>2.3.2 Compromis coût de déploiement-altitude</td><td>20</td></tr><tr><td>2.3.3 Coût de la connectivité</td><td>22</td></tr><tr><td>2.3.4 Déploiement auto-organisé</td><td>24</td></tr></table>
<figure><img src="image_8.png" /></figure>
Cette première partie retrace mes travaux effectués depuis 2017 sur les réseaux aériens auto-
nomes composés de drones auto-organisés en flotte (Flying Ad-hoc Network (FANET)). L'origine
de cette direction de recherche provient d'un projet évoqué avec l'Ifremer de La Réunion qui
souhaitait changer leur étude des déplacements et la détection des requins autour de l'île. Ils
avaient des balises localisées au large des côtes qui envoyaient des communications satellites pour
remonter les données collectées. L'étude envisagée alors est de pouvoir substituer les communica-
tions satellites en envoyant un ou plusieurs drones autour des balises afin de rapporter les données
qui ont été collectées jusqu'à un centre de traitement. Cette collaboration ne s'est pas concrétisée
directement, mais elle m'a permis d'entamer avec Tahiry Razafindralambo, maître de conférences
à l'Université de La Réunion, une collaboration sur cette thématique de recherche.

Différentes directions s'offrent alors à nous car beaucoup de questions se posent dans l'utili-
sation des drones comme solution de communication. Combien de drones avons-nous besoin de
déployer sur une zone donnée, afin de détecter, couvrir, suivre, recharger les batteries des nœuds
au sol ? Quelles caractéristiques prendre en compte pour une bonne modélisation du système aé-
rien multi-sauts ? Quels compromis adopter dans la modélisation afin d'obtenir efficacement des
solutions et qui ont du sens ?

Je vais m'intéresser à ces questions tout au long de cette partie, en m'appuyant sur les travaux réalisés en collaboration avec Yann Busnel, Tahiry Razafindralambo, Dimitrios Zorbas, ou des membres de mon équipe COATI : Frédéric Giroire, David Coudert et évidemment Igor Dias Da Silva, dont j'ai eu le plaisir d'encadrer la thèse de 2020 à 2023 sur ces sujets. Nous avons utilisé les techniques d'optimisation en programmation linéaire mono ou multi-objectif afin de dériver des formulations optimales aux problèmes abordés. J'ai également appliqué des techniques de décomposition telle que la génération de colonnes afin d'améliorer la résolution des modèles. Enfin, nous nous sommes penchés sur le développement d'un algorithme distribué d'auto-organisation de drones pour la découverte de nœuds au sol.

Ce chapitre commence sur une introduction aux réseaux aériens et ma démarche tournée vers les verrous scientifiques liés au déploiement de drones, à leur coordination, et à leur utilité pour la recharge énergétique des capteurs. Cette introduction est commune à toute la première partie du manuscrit comprenant les chapitres 2 à 4. Ce chapitre 2 présente également mes contributions concernant la couverture d'un ensemble de nœuds fixes au sol (capteurs, téléphones, ou autres objets connectés), qui ne peuvent communiquer directement entre eux. Un certain nombre d'hy- pothèses sont ainsi faites dans un premier temps sur l'utilisation d'un réseau de drones permettant d'assurer une couverture connexe des nœuds, appelés cibles, avec une station de base en marge du réseau aérien. Avec Tahiry Razafindralambo, nous avons modélisé le problème et construit un modèle compact en programmation linéaire bi-objectif afin d'analyser la complexité de ce type de problème et étudier les compromis d'optimisation à faire pour obtenir une solution équitable en fonction de divers paramètres (Caillouet & Razafindralambo, 2017, 2018). Puis avec David Cou- dert et Yann Busnel, nous avons cherché à améliorer un algorithme décentralisé afin de déployer un réseau aérien multi-sauts pour la découverte de cibles au sol dont les positions sont incon- nues (Busnel et al., 2019a, 2020). Le chapitre 3 est dédié à une extension de ces travaux pour le problème de suivi de nœuds mobiles par les drones. Et le chapitre 4 aborde la problématique de la recharge énergétique de capteurs au sol par des drones.
<figure><img src="image_9.png" /><figcaption>Figure 2.1 – Modèles de drones.</figcaption></figure>

## 2.1 Les réseaux aériens

Les systèmes aériens autonomes étendent la portée des réseaux sans fil classiques en fournissant des solutions de supervision et de couverture pour la surveillance à grande échelle, la gestion de la santé ou la gestion après une catastrophe (Ackerman & Strickland, 2018; Gupta, Jain, & Vaszkun, 2016; Luo et al., 2019). La densité et la mobilité des nœuds ne sont plus contraintes car le système aérien permet de fournir une connectivité réseau et des services, et d'étendre les déploiements à la demande pour la récupération de données, pour le suivi des utilisateurs mobiles ou pour recharger les batteries des nœuds à l'aide de technologies telles que la radio-fréquence.

Il existe deux principaux types de drones : les drones à ailes fixes et les drones à multirotors (figure 2.1). Les drones à multirotors sont généralement plus petits et moins chers, et leur principale caractéristique est qu'ils offrent une maniabilité plus élevée, peuvent stationner au-dessus d'un emplacement spécifique et adapter leur vitesse. En revanche, un drone à ailes fixes sera plus rapide mais moins maniable. En raison de ces caractéristiques, dans la plupart des cas, les opérations de secours en cas de catastrophe font appel à des drones à multirotors pouvant fournir une connectivité cellulaire à des sites éloignés (Fabra Collado et al., 2019; Lyu, Zeng, Zhang, & Lim, 2017; Mozaffari, Saad, Bennis, & Debbah, 2016). Les drones à multirotors seront privilégiés pour être utilisés comme stations aériennes afin d'augmenter temporairement la capacité, la couverture et la fiabilité du réseau. Les drones à ailes fixes sont généralement plus efficaces dans les opérations qui nécessitent un déploiement rapide sur des zones vastes ou pour la couverture du réseau lorsque celle-ci est censée être dynamique.

Une application particulière peut nécessiter un seul drone ou un essaim de drones. Dans ce deuxième cas, le choix du type de drones sera également influencé par la zone où les drones doivent être déployés, mais la plupart du temps, ces applications nécessitent une coordination entre les drones et souvent un déploiement en régime stationnaire (pour maintenir la connectivité des communications ou surveiller la couverture). Ainsi les drones à multirotors sont en général privilégiés.

En général, les technologies de communication utilisées dans les applications basées sur les drones sont les technologies traditionnelles, c'est-à-dire les technologies cellulaires (LTE/3G/4G/5G), WiFi, WiMAX ou les technologies de l'Internet des Objets (IoT) (Zigbee, 802.15.4, SigFox, LoRa), etc. Le choix dépendra de l'objectif de l'application. De toute évidence, lorsqu'un drone est utilisé pour alléger un réseau en place ou pour déployer un nouveau point d'accès, il sera équipé de la technologie du réseau à prendre en charge. Un drone peut embarquer
différentes technologies, certaines pour le cas d'utilisation spécifique pour lequel il est déployé, mais aussi pour communiquer avec d'autres drones.

### 2.1.1 Domaines d'applications

A partir de 2015, la littérature s'est enrichie d'un certain nombre d'articles portant sur l'utilisation d'un système aérien autonome. Les contextes d'utilisation sont multiples, allant du déploiement d'un réseau de drones dans le cas d'applications militaires (Orfanus, de Freitas, & Eliassen, 2016), à l'utilisation de drones pour étendre la portée des réseaux cellulaires (Becvar, Vondra, Mach, Plachy, & Gesbert, 2017), ou encore pour aider les services de secours en cas de sinistres (Cambra, Sendra, Lloret, & Parra, 2015).

#### 2.1.1.1 Surveillance

L'agriculture et la surveillance de la santé animale attirent récemment de plus en plus d'attention. Des capteurs sont placés dans les champs pour capturer des informations liées à la qualité des cultures et au bien-être des animaux (Zorbas & O'Flynn, 2019), ou pour suivre les animaux sauvages en Afrique (Seddik, Toldov, Clavier, & Mitton, 2018) ou l'application à l'origine de mes collaborations qui concerne les requins près de l'île de la Réunion dans l'océan Indien. Dans de tels environnements, les capteurs ne se réveillent pas très souvent et stockent les données régulièrement mesurées dans leur mémoire. Une flotte de drones est particulièrement intéressante pour fournir un réseau opérationnel permettant de collecter périodiquement des données de grand volume à partir des capteurs et de les regrouper à la station de base. Zorbas et O'Flynn considèrent que la surveillance des animaux peut générer un volume élevé de données (plusieurs méga-octets en une semaine) en raison des déplacements continus des animaux (Zorbas & O'Flynn, 2019). Pour résoudre le problème du transfert de volumes de données élevés, ils proposent une architecture de réseau combinant différentes technologies de communication, comme LoRa et WiFi.

#### 2.1.1.2 Sûreté

Un domaine d'application important pour les drones concerne les catastrophes naturelles telles que les tremblements de terre, les tsunamis, les tempêtes tropicales, les incendies, etc. Les effets de ces catastrophes naturelles à grande échelle pourraient être significativement atténués grâce à un système de gestion des catastrophes complet et hautement efficace. Dans de telles situations, le temps est un facteur critique pour trouver des survivants, et il est important de fournir une connectivité grâce à une solution rapide et efficace pour les équipes de secours. Les systèmes d'urgence terrestres traditionnels sont généralement peu efficaces pour la collecte d'informations avec une latence élevée et une faible largeur de bande des communications par satellite. Au contraire, l'utilisation de drones est devenue une solution clé pour renforcer la capacité des interventions en cas de catastrophe, faire face aux conditions environnementales extrêmes sans connectivité réseau et effectuer des opérations de secours en temps opportun. Par exemple, des drones ont été conçus pour exploiter les appareils intelligents détenus par les survivants dans les zones dévastées et fournir une infrastructure de communication à la demande pour les opérations de secours. Une planification des trajectoires de la flotte de drones de manière décentralisée permet d'obtenir des solution auto-organisées qui sont particulièrement recherchées pour fournir un système de gestion des catastrophes efficace. La gestion militaire sur le champ de bataille est d'un intérêt particulier,
et leurs exigences sont similaires à celles présentées pour les scénarios de gestion de catastrophe civile.

### 2.1.1.3 Santé

De nouvelles applications liées à la médecine et aux soins de santé ont également vu le jour. Les drones ont été utilisés pour livrer des médicaments, des fournitures médicales telles que des défibrillateurs, des échantillons de sang et des vaccins en Afrique de l'Est (Ackerman & Strickland, 2018). Ces nouveaux systèmes de livraison de soins de santé impliquent des exigences logistiques ainsi que des garanties quant à l'exactitude des informations. Déterminer et maintenir un itinéraire sûr en fonction du terrain, de la météo, de l'espace aérien et de la densité de population est un défi majeur. L'itinéraire doit également être calculé de manière efficace pour éviter les zones sensibles telles que les aéroports et les écoles.

Une nouvelle contrainte apparaît dans de tels systèmes en fonction des exigences de livraison, correspondant au poids des fournitures transportées par les drones. La miniaturisation et le coût très bas de ces machines imposent de limiter la quantité et le poids des objets transportés. Dans ce contexte, la trajectoire des drones doit être optimisée pour garantir un temps de vol total, une altitude spécifique et un poids total maximal.

## 2.2 Défis et opportunités

Tous ces contextes impliquent l'analyse de problèmes d'optimisation relatifs à l'utilisation du système aérien autonome.

L'utilisation d'un seul drone dans un système aérien autonome ne permet pas de répondre de manière générique à toutes les contraintes temporelles et spatiales des réseaux de capteurs ou cel- lulaires. En revanche, l'utilisation d'une flotte de drones permettrait de surmonter ces contraintes. Cependant, l'utilisation d'une flotte dans un système aérien autonome présente plusieurs défis en termes de coordination entre les drones, de transfert de données air-sol et air-air, et de couverture dynamique pour la recharge d'énergie ou la connectivité. Les drones doivent être positionnés de manière optimale au-dessus des nœuds au sol afin de pouvoir couvrir une grande superficie tout en minimisant les coûts de déploiement et énergétique de chaque drone. L'espace tridimensionnel dans lequel évoluent les drones complique les modèles d'optimisation, car ils doivent prendre en compte les contraintes de qualité des communications air-sol et air-air (figure 2.2).

Mon travail s'est donc focalisé sur les champs d'action suivants :

1. **Coordination.** Les drones doivent être positionnés de manière optimale au-dessus des capteurs pour pouvoir couvrir un nombre maximum de capteurs en minimisant le coût de déploiement des drones et le coût énergétique dépensé par chaque drone. L'espace à 3 dimensions dans lequel sont déployés les drones complexifie les modèles d'optimisation qui doivent prendre en compte des contraintes de qualité de communications air-sol et air-air (Chapitre 2). Les modèles classiques en programmation linéaire montrent rapidement leurs limites en termes de résolution ou de prise en compte des contraintes physiques des réseaux, notamment lorsque les cibles au sol sont mobiles. Il est donc nécessaire de dé- velopper des modèles sophistiqués pouvant être résolus par des techniques avancées de recherche opérationnelle comme la génération de colonnes (Chapitre 3).
<figure><img src="image_10.png" /><figcaption>Figure 2.2 – Défis des réseaux aériens.</figcaption></figure>

2. **Communication.** Le système aérien autonome doit permettre de récupérer les données des capteurs au sol pour les transférer vers une station de base en marge du réseau. La connexité du réseau pour les communications air-sol et air-air doit être assurée par le déploiement tout en gardant les contraintes sur les coûts dépensés par le système aérien autonome (Chapitres 2 et 3).

3. **Recharge.** Les drones peuvent, grâce à un système de radiofréquence, recharger les batteries des capteurs au sol. Cette technologie a été récemment étudiée dans le cadre même des réseaux de capteurs (Lu, Wang, Niyato, Kim, & Han, 2015). Le but de ce travail est d'étendre cette technologie dans le système aérien autonome, permettant d'allonger efficacement la durée de vie des capteurs au sol en même temps que la surveillance et la collecte. La recharge ajoute la dimension temporelle comme une contrainte forte dans notre déploiement. Les capteurs nécessitent la présence de drones à une localisation donnée (proximité) pendant un temps donné (temps de recharge). Les drones doivent aussi prendre en compte le niveau de batterie de chaque capteur pour optimiser les recharges des capteurs tout en minimisant le nombre de drones déployés et les coûts énergétiques associés (Chapitre 4).

Cette thématique de recherche m'a tout de suite attirée car elle se rapproche des réseaux radio maillés (Wireless Mesh Networks (WMN)) que j'ai étudiés pendant ma thèse. En effet ces réseaux se décomposaient en plusieurs niveaux : les nœuds au sol, puis un *backbone* de point d'accès faisant eux-mêmes l'interface avec le réseau de cœur. J'avais ainsi pendant ma thèse, étudié le déploiement et l'optimisation de la capacité de ce type de réseau, avec une approche orientée sur l'optimisation du nombre de points d'accès nécessaires pour assurer une qualité de service attendue aux nœuds du réseau. De plus, dans un réseau WMN, le backbone est connecté, permettant d'acheminer efficacement les données collectées depuis les nœuds jusqu'au réseau de cœur à travers des chemins multi-sauts dans le backbone.

Les avantages de ces réseaux sont nombreux en comparaison aux WMNs. En effet, le coût de déploiement de tels réseaux est fortement réduit car les drones sont peu chers et facilement
déployables. Ils offrent ainsi une solution efficace et peu coûteuse pour se substituer à une infra-
structure fixe et lourde dans des endroits où il est difficile de la développer, ou pour mettre en
place une infrastructure temporaire lorsque l'infrastructure fixe ne fonctionne plus. Néanmoins les
réseaux aériens sans fil offrent des défis inédits par rapport aux WMNs. Les drones évoluent dans
un environnement en trois dimensions en comparaison des points d'accès du WMN. Cela donne
lieu à des modélisations plus poussées car l'espace des solutions est augmenté ce qui complique
la résolution des modèles. Il y a également davantage de mobilité dans ce type de réseau où tous
les éléments peuvent se déplacer au cours du temps. Les drones sont évidemment mobiles, ce
qui permet d'ajuster leur positionnement pour améliorer les transmissions, éviter les collisions,
ou assurer le suivi des nœuds qui peuvent donc eux aussi se déplacer, mais cela donne lieu à des
problématiques inédites de planification des trajectoires.

Le large éventail des applications possibles avec ce type de réseau le rend donc très attractif d'un point de vue recherche. Je me suis donc concentrée sur l'étude de ces réseaux, tout d'abord dans leur application principale de couverture d'un ensemble de nœuds fixes au sol, afin de comprendre les difficultés résidant dans la modélisation de ces problèmes d'optimisation.

Ainsi, les questions que j'ai abordé dans ces premiers travaux sont :

— Étant donné un ensemble connu de nœuds à couvrir au sol, combien de drones sont nécessaires pour assurer la couverture de tous les nœuds ?

— Où placer les drones dans un environnement en 3 dimensions pour assurer une bonne qualité des liens radio ?

— Quel est le coût de la connectivité entre les drones ? (en termes de nombre de drones additionnels)

— Comment assurer un compromis acceptable entre les différents critères d'optimisation antagonistes ?

## 2.3 Déploiement de drones connectés pour la couverture de cibles fixes

Dans la littérature, la couverture complète de cibles par une flotte de drones a été étudiée sous différents angles, principalement par deux communautés de recherche. Du point de vue de la robotique, l'objectif principal est la collaboration entre les dispositifs mobiles pour une tâche spécifique. La communauté robotique se concentre sur le déploiement lui-même ou sur la manière de conduire chaque dispositif à son emplacement spécifique. Du point de vue des réseaux ad-hoc et des capteurs, une fois qu'un emplacement est défini pour chaque dispositif, l'objectif est de mettre en œuvre des protocoles au-dessus du réseau déployé. Une autre façon d'aborder le problème, qui est celui que j'ai choisi, se place du point de vue de l'optimisation. Beaucoup de travaux se sont concentrés sur le choix optimal de l'emplacement des drones, comme par exemple dans (Navarro-Serment, Dolan, & Khosla, 2004; Martínez & Bullo, 2006; Dasgupta, Kukreja, & Kalpakis, 2003; Wang, Xu, Takahara, & Hassanein, 2006). Dans ces travaux, les auteurs supposent que les dispositifs évoluent dans un espace 2D. Par conséquent, leur problème est simplifié car le rayon de couverture est fixe pour chaque drone.

Dans (Kar, Banerjee, et al., 2003), les auteurs proposent une étude sur le placement des nœuds incluant des contraintes de connectivité. Cependant, la solution fournie n'est pas optimale et est basée sur une approximation. De plus, les algorithmes sont conçus pour un espace 2D dans lequel
<figure><img src="image_11.png" /><figcaption>Figure 2.3 – Modèle de couverture.</figcaption></figure>

le rayon de couverture est fixe. Dans (Alduraibi, Lasla, & Younis, 2016), la connectivité du réseau est également considérée, mais toujours dans un environnement en 2 dimensions. Un point intéressant soulevé par les auteurs de (Alduraibi et al., 2016) concerne l’aspect de la couverture. Ils supposent que la couverture est un disque atténué. Dans notre cas, nous supposons une couverture complète et totale de chaque cible spécifique.

Dans (Pugliese, Guerriero, Zorbas, & Razafindralambo, 2016), les auteurs proposent un programme linéaire mixte pour le problème de couverture des cibles en utilisant des drones. La solution proposée est ensuite utilisée dans (Zorbas, Di Puglia Pugliese, Razafindralambo, & Guerriero, 2016) comme modèle de référence pour leur solution distribuée. Ils cherchent à minimiser le nombre de drones et la consommation d'énergie totale du réseau. Il est supposé que chaque drone a une altitude minimale et maximale et que la consommation d'énergie est liée à son altitude. Ces deux travaux constituent la base de nos premières études sur le sujet présentées dans la suite, pour lesquels nous avons modifié et étendu les modèles afin de prendre en compte la connectivité du réseau aérien.

### 2.3.1 Modélisation de la flotte de drones

Soit U l'ensemble des drones disponibles et N l'ensemble des cibles (objets connectés) à surveiller. Chaque cible $n \in N$ est supposée fixe, située à la position $(x_n, y_n)$ dans le plan 2D.

Chaque drone $u \in U$ peut être situé dans l'espace tridimensionnel. Soit $p = (x_u, y_u, h_u)$ respectivement la position $(x_u, y_u)$ du drone $u$ dans le plan 2D et $h_u$ son altitude. Nous dérivons le rayon d'observation $r_u^h$ du drone $u$ en fonction de son altitude $h_u$ et de la demi-largeur du faisceau de son antenne directionnelle $\theta$ (figure 2.3). La zone de couverture du drone $u$ dans le plan 2D, compte tenu de l'angle de visibilité $\theta$ et de l'altitude $h_u$, est représentée par un disque de rayon borné par :

$$r_u^h \leq h_u \cdot \tan\left(\frac{\theta}{2}\right).$$

Plus l'altitude est élevée, plus le rayon est grand et donc plus la zone couverte est importante. Cependant, le déploiement de drones à haute altitude dégrade la qualité du lien sans fil à cause de l'atténuation du lien radio. Nous cherchons donc à minimiser l'altitude des drones déployés afin de maximiser la qualité de la couverture. Une autre manière d'optimiser l'altitude des drones est de l'obliger à se situer dans l'intervalle $[h_{min}, h_{max}]$ afin d'assurer une bonne couverture sans fil.
Notre hypothèse principale de couverture est la suivante. On dit qu’un drone $u \in U$ couvre une cible $n \in N$ si la distance entre sa projection dans le plan 2D et la cible $d_{un} = \sqrt{(x_u - x_n)^2 + (y_u - y_n)^2}$ est inférieure au rayon d’observation $r_u^h$ du drone. De même, pour les communications air-air, un drone $u$ peut communiquer avec un autre drone $v$ si leur distance dans l’espace en 3D

$$D_{uv} = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2 + (h_u - h_v)^2} \le R_u,$$

où $R_u$ est la portée de communication air-air du drone $u$.

Pour une collecte efficace des données, nous imposons que les drones déployés soient connectés entre eux et avec une station de base fixe $b$ située au sol aux coordonnées $(X_b, Y_b, 0)$.

### 2.3.2 Compromis coût de déploiement-altitude

Placer un drone pour surveiller les cibles implique des considérations de coût. Nous fixons un coût donné $c_u$ associé au déploiement du drone $u$ à une position donnée. Ce coût $c_u$ peut être lié à des considérations énergétiques, des coûts de surveillance, des coûts de déploiement, etc. Cette généralisation du modèle me tient à cœur car il est ensuite facile de modifier les valeurs et donc la signification des paramètres sans changer le modèle d'optimisation. Ce qui permet de résoudre facilement le modèle afin de comparer les résultats des différents critères. Nous restons donc ici le plus générique possible en définissant un coût $c_u$ associé au drone $u$. Dans les résultats numériques, nous fixons $c_u$ égal à 1 pour tous les drones, ainsi notre problème vise à minimiser le nombre de drones déployés.

Étant donné un ensemble de cibles déployées au sol, l'objectif est de couvrir toutes les cibles de manière à minimiser les coût de déploiement, avec des drones volant aussi bas que possible. De plus, nous nous assurons que le réseau aérien de drones forme un graphe connexe avec une station de base fixe afin de fournir une connectivité aux cibles pour transmettre ou récolter efficacement de l'information. Nous montrons qu'il est possible de développer un modèle efficace qui calcule les positions optimales des drones minimisant à la fois le coût de déploiement et l'altitude des drones en utilisant le concept d'optimalité de Pareto. A l'aide de ce modèle et par rapport aux travaux existants dans la littérature qui ne construisent pas de réseau aérien connexe, nous montrons que la contrainte de connectivité a un effet non négligeable sur le nombre de drones nécessaires. Ce travail est détaillé dans l'article (Caillouet & Razafindralambo, 2017).

Soit $z_p^u$ une variable binaire indiquant si le drone $u$ est déployé à la position $p$. De plus, $\chi_n^u$ est une autre variable binaire déclarant si le drone $u$ couvre la cible $n$. Ces variables vont nous servir à dériver un modèle optimal bi-objectif permettant de déployer un nombre minimum de drones à une altitude minimum, de manière à couvrir toutes les cibles au sol et à former un réseau aérien connecté avec une station de base. Les contraintes de couverture des cibles au sol en fonction du modèle de couverture précédent sont ainsi :

$$\sum_{u \in U} \chi_n^u \ge 1, \forall n \in N \qquad (2.1)$$

$$\chi_n^u \le \sum_{p \in P} z_p^u \cdot \frac{r_u^h}{d_{un}}, \forall u \in U, n \in N \qquad (2.2)$$

La connectivité est quant à elle assurée par des contraintes de conservation de flot avec des variables continues $f_{uv}$. Un flot est envoyé depuis la station de base et ne pourra passer que par des
positions occupées par les drones.

$$ \sum_{v \in U, v \neq u} f_{uv} - \sum_{v \in U, v \neq u} f_{vu} = \begin{cases} \sum_{v \in U} \sum_{p} z_p^v & \text{if } u = b \\ -\sum_{p} z_p^u & \text{if } u \neq b \end{cases}, \forall u \in U \quad (2.3) $$

$$ f_{uv} \leq \sum_{p} z_{p}^{u} \cdot \frac{R_{u}}{D_{uv}} \cdot |U|, \quad \forall u, v \in U \quad (2.4) $$

$$ f_{uv} \leq \sum_{p} z_{p}^{v} \cdot \frac{R_{u}}{D_{uv}} \cdot |U|, \quad \forall u, v \in U \quad (2.5) $$

L'objectif du problème est de minimiser le coût total des drones utilisés pour couvrir toutes les cibles tout en assurant une bonne qualité des liens air-sol. Considérant la définition du rayon de couverture des drones présentée dans la section précédente, nous pouvons constater que modifier l'altitude des drones impacte la couverture et les liaisons en ligne de vue avec les utilisateurs au sol. D'une part, la zone de couverture augmente avec l'altitude, permettant ainsi une meilleure couverture des cibles au sol avec un seul drone. D'autre part, les communications sans fil avec les cibles se dégradent avec l'altitude, ce qui peut rendre la couverture insatisfaisante. Notre problème se traduit donc en un modèle bi-objectif où nous souhaitons conjointement optimiser :

$$ \min \sum_{p \in P} \sum_{u \in U} c_u \cdot z_p^u \quad (2.6) $$

$$ \min \max_{u \in U, p \in P} h_u(p) \cdot z_p^u \quad (2.7) $$

Ces deux objectifs étant en conflit, il n'est pas pertinent de les combiner dans un problème d'optimisation efficace. En effet, chercher à optimiser l'altitude des drones augmente inévitablement le nombre de drones nécessaires pour couvrir toutes les cibles. Limiter le coût du déploiement implique quant à lui d'utiliser le moins de drones possible, ce qui augmente leur altitude pour obtenir des zones de couverture plus étendues.

Par conséquent, pour un tel problème d'optimisation multi-objectif où les objectifs ne peuvent pas être optimisés simultanément, le concept d'optimalité de Pareto a été introduit dans le système d'évaluation. L'idée principale pour étudier les compromis entre les deux métriques 2.6 et 2.7 est de découvrir toutes les solutions non-dominées possibles du problème d'optimisation. Si une solution est non-dominée dans tout l'espace des solutions, il n'est pas possible d'améliorer l'une des métriques sans détériorer au moins l'une des autres métriques. L'ensemble de toutes les solutions non-dominées est le front de Pareto. Le front de Pareto fournit un ensemble de solutions qui peuvent être choisies en fonction des exigences de l'application.

Plus précisément, chaque solution non-dominée représente un compromis optimal différent entre les objectifs. Afin de générer des solutions Pareto-optimales pour notre problème de couverture de cibles avec connectivité, nous utilisons la méthode $\epsilon$-constraint qui transforme le problème bi-objectif en une séquence de problèmes mono-objectif paramétrés de telle sorte que l'optimum de chaque problème mono-objectif corresponde à une solution de Pareto-optimale (Laumanns, Thiele, & Zitzler, 2005; Bérubé, Gendreau, & Potvin, 2009).

Les fronts de Pareto obtenus à partir de notre modèle (figure 2.4) nous permettent alors de proposer une solution optimale équitable :
<figure><img src="image_12.png" /><figcaption>Figure 2.4 – Front de Pareto pour différentes tailles de N et P.</figcaption></figure>

**Définition 2.3.1 (Solution optimale équitable).** La solution optimale équitable du problème de couverture de cible avec des contraintes de connectivité entre les drones correspond à la solution $(c^*, h_{max}^*)$ telle que :

— $h_{max}^* = f^2$ est la solution optimale de la fonction objectif 2.7;

— $c^*$ est le coût de déploiement minimal obtenu en atteignant $f^2$.

### 2.3.3 Coût de la connectivité

Nous comparons la couverture optimale des cibles avec et sans les contraintes de connectivité entre les drones déployés. Cet ensemble de contraintes supplémentaires oblige à utiliser au moins autant de drones que dans la couverture optimale sans connectivité. En effet, soit la solution optimale pour la couverture des cibles est un ensemble connecté de drones avec la station de base, ce qui en fait une solution optimale pour notre problème. Soit la solution optimale de la couverture des cibles n’est pas connectée et nous avons alors besoin de drones supplémentaires pour induire la connectivité. Nous définissons ainsi le « coût de la connectivité » par la quantité supplémentaire (en termes de coût de déploiement) à payer pour obtenir un ensemble connecté de drones, également connecté à la station de base.
<figure><img src="image_13.png" /><figcaption>Figure 2.5 – Coût de la connectivité.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 2.6 – Solutions optimales obtenues pour 5 cibles (étoiles) et 48 positions possibles (carrés) (16 coordonnées 2D différentes et 3 altitudes possibles).</figcaption></figure>

Les résultats du cas non connecté montrent d'abord que garantir la connectivité entre les drones n'augmente pas l'altitude maximale de ceux-ci. Il est toujours possible de trouver un ensemble connecté de drones de couverture avec la même altitude maximale que pour la version non connectée. Nous partons de la solution optimale du problème de couverture sans connectivité, et nous ajoutons uniquement des drones intermédiaire à la même altitude pour connecter le réseau. Un résultat plus fort est de réduire l'altitude maximale dans le cas connecté. Par exemple, si une solution optimale possède un drone à haute altitude couvrant toutes les cibles sans être connecté à la station de base, alors déployer plusieurs drones à une altitude inférieure assurant une couverture complète des cibles et l'existence d'un chemin jusqu'à la station de base est parfois possible. Si ce cas où l'altitude maximale diminue dans le cas connecté ne se produit pas dans nos tests, c'est parce qu'il nécessite un nombre important de drones et d'autres altitudes possibles. En effet le nombre de drones nécessaires pour couvrir toutes les cibles à basse altitude peut être important et pas pratiquement réalisable.
La figure 2.6 illustre bien que lorsque le nombre de cibles est faible, alors le nombre de drones supplémentaires nécessaires dans le cas connecté est important (3 fois plus pour $|N| = 5$ et $|P| = 243$). En effet, selon la position des cibles, il est nécessaire de se connecter au moins à la station de base située dans le coin inférieur gauche de la région considérée. En revanche, lorsque le nombre de cibles augmente, le coût de la connectivité diminue, car les contraintes de couverture obligent à déployer plus de drones, de sorte qu’ils ne sont plus là uniquement pour faire relais. Cette observation est également mise en évidence sur la figure 2.5. Lorsque le nombre de cibles ou de positions possibles pour les drones est important, le coût de la connectivité diminue à 1, ce qui est un avantage pour des zones de surveillance denses.

### 2.3.4 Déploiement auto-organisé

Ce coût de la connectivité a également été étudié lors du développement d'un algorithme distribué afin de déployer un réseau aérien en situation d'urgences où le but est de localiser un ensemble de cibles au sol qui ont perdu la connexion au réseau.

Dans des situations d'urgences provoquées notamment par des catastrophes naturelles, le temps est un facteur critique pour trouver des survivants, et il est important de fournir une connectivité par le biais d'une solution rapide et efficace aux équipes de secours. L'utilisation de drones est devenue une solution clé pour améliorer la capacité de réaction aux catastrophes, faire face aux conditions environnementales extrêmes sans aucune connectivité réseau et effectuer des opérations de sauvetage. Dans ce cas une solution centralisée optimale comme envisagée jusque là ne répond pas aux contraintes temporelles et de scenario spécifique. Je me suis donc penchée, en collaboration avec Yann Busnel et David Coudert, sur une solution décentralisée dans laquelle les drones sont déployés sans connaître a priori la position des noeuds au sol (Busnel et al., 2019a, 2020).

**Définition 2.3.2** (VESPA (Vehicle Spreading using Self-organized Parallel Algorithm)). Étant donné un ensemble de cibles dont on ne connaît pas l'emplacement, le but est d'explorer la zone avec des drones pour découvrir autant de cibles que possible tout en assurant la connectivité avec une station de base (ou puits) pour permettre les échanges d'informations entre le puits, les drones et les cibles.

Tous les drones $u \in U$ commencent à la position de la station de base $b$ centralisant les opérations de recherche et de sauvetage. Les positions géographiques absolues sont inconnues (pas de GPS), mais les drones peuvent déduire leurs positions relatives entre eux. Une cible est couverte par un drone si elle est dans la zone d'intersection de la boule de communication du drone avec le sol. Pour éviter les trous de détection et assurer une couverture optimale, nous utilisons une tessellation triangulaire. Chaque drone est situé au centre d'un hexagone, et la portée de communication $R_u$ lui permet de communiquer avec les drones situés au centre des hexagones voisins dans cette tessellation (figure 2.7). Nous supposons aussi que la zone de couverture du drone circonscrit l'hexagone pour assurer une couverture complète de la zone.

Chaque drone exécute indépendamment l'algorithme en suivant une alternance de 3 phases : (i) expansion, (ii) recouvrement, et (iii) équilibrage. Au cours du processus, chaque drone peut prendre 3 états possibles :

- **inamovible** : ces drones resteront toujours dans leur position actuelle. Ils sont essentiels pour assurer la connectivité des cibles découvertes et la trajectoire aérienne vers le puits ;
<figure><img src="image_15.png" /><figcaption>Figure 2.7 – Tessellation triangulaire.</figcaption></figure>

— **frontalier** : ces drones entourent la zone couverte, représentant le bord de la zone d'expansion;

— **libre** : ces drones peuvent se déplacer librement, i.e., ils ne sont ni inamovibles ni frontaliers.

Pour assurer la connectivité pendant les phases d'expansion successives, nous permettons aux drones d'être simultanément inamovibles et frontaliers.

**Phase d'expansion** Dans la phase d'expansion, les drones s'éloignent du puits pour détecter les cibles. Initialement, tous les drones sont à l'état **libre** à la position $p_S$. A chaque étape de cette phase, chaque drone libre situé au centre $s_0$ d'un hexagone décide indépendamment s'il se déplace vers l'un des centres $s_1, ..., s_6$ des hexagones voisins (figure 2.7) ou s'il reste en $s_0$. Si plusieurs drones se trouvent à $s_0$, l'algorithme garantit qu'au moins un drone restera à cette position pour maintenir la couverture et la connectivité.

Nous proposons une procédure de terminaison, permettant de passer à la phase suivante de l'algorithme. En fin d'expansion, tout drone n'étant pas entouré de 6 autres drones, basculera en état **frontalier**.

**Phase de recouvrement.** À la fin de la phase d'expansion, chaque zone est soit vide, soit peuplée par un seul drone. Chaque drone situé sur un spot comprenant une cible, devient **inamovible** et cherchera à la fois à créer un chemin de communication multi-hop le plus court vers le puits, et à se connecter au drone frontalier le plus proche pour assurer la connexité de l'ensemble du réseau. Les drones situés sur ces chemins passent alors en état **inamovibles**, créant un arbre recouvrant connexe ayant le puits pour racine. Comme précédemment, une procédure de terminaison est proposée pour passer à la phase suivante.

Ainsi, à la fin de la phase de recouvrement, au moins un chemin de drones inamovibles existe entre le puits et la frontière de la zone explorée.

**Phase d'équilibrage.** Seuls les drones libres sont autorisés à se déplacer dans cette phase. Chaque drone libre choisit au hasard une zone voisine qui l'éloigne du puits. Ce processus est répété jusqu'à ce que tous les drones atteignent un endroit occupé par un drone frontalier. Nous équilibrons alors le nombre de drones par point de la frontière de sorte que le nombre de drones sur deux points voisins de la frontière diffère de un au maximum. Lorsqu'un drone libre atteint un
<figure><img src="image_16.png" /><figcaption>Figure 2.8 – Exemple d’exécution de l’algorithme VESPA, avec 10 cibles et 217 drones.</figcaption></figure>

drone frontalier, il suit le même processus que lors de la phase d’expansion, permettant de détecter
la terminaison de cette phase.

Enfin, nous répétons les 3 phases (expansion, recouvrement et équilibrage), jusqu’à ce que
tous les drones soient inamovibles ou frontaliers.

Nous illustrons dans la figure 2.8 le déroulement de VESPA, phase par phase, sur un exemple
avec 217 drones et 10 cibles à couvrir (représentées par des étoiles noires). Initialement, tous les
drones sont à l'état libre et se trouvent sur le puits (figure (a)). Le processus commence par
une première phase d'expansion, permettant de couvrir la zone la plus large possible centrée sur
le puits. A la fin de la phase, tous les drones situés en bordure de la zone d'expansion changent
d'état pour devenir frontalier (cellules vertes sur la figure (b)). Puis, les drones couvrant une
zone comprenant une cible passent à l'état inamovable et lancent la phase de recouvrement,
afin de garantir la connectivité entre le puits, les cibles détectées et la frontière (cellules rouges sur
la figure (c)). La 3ème phase de VESPA permet ensuite à tous les drones encore en état libre
d'atteindre la frontière, afin de préparer la prochaine phase d'expansion (cellules bleues sur la
figure (d)). Les figure (e) à (i) illustrent la poursuite de l'exécution de VESPA, nécessitant 11
étapes supplémentaires pour atteindre l'expansion maximale. Une fois la dernière étape atteinte
(plus aucun drone n'est en état libre), tous les drones non nécessaires à la connectivité des
cibles avec le puits retournent à leur point de départ.

L'article (Busnel et al., 2019a) contient l'ensemble des preuves formelles attestant du bon
fonctionnement de l'algorithme VESPA. Nous y démontrons que chaque phase respecte les ga-
<figure><img src="image_17.png" /><figcaption>(a) Nombre de cibles découvertes, avec les valeurs min, max, moyenne et écart type.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(b) Nombre moyen de drones nécessaires pour découvrir toutes les cibles positionnées au hasard.</figcaption></figure>

<caption>Figure 2.9 – Comparaison entre VESPA et l’algorithme SaS.</caption>

ranties de connexité, de couverture et de terminaison.

Nous avons validé notre algorithme par des simulations et avons comparé ses performances avec l’algorithme de propagation et de rétraction (SaS) (Razafindralambo, Erdelj, Zorbas, & Nata-lizio, 2017) en termes de nombre de cibles découvertes, et de nombre de drones nécessaires pour couvrir et assurer la connectivité avec les cibles. Une station de base est située au centre de la zone à surveiller d’environ 6,3 km². Nous déployons au hasard autour du puits des cibles dont les coordonnées sont inconnues des drones et du puits. Nous exécutons l’algorithme sur des milliers de topologies aléatoires, faisant varier le nombre de cibles de 1 à 30, et le nombre de drones de 10 à 250. Comme pour SaS (Razafindralambo et al., 2017), nous fixons la portée de communication $R_u$ de tous les drones à 20m.

Nous exécutons VESPA avec un nombre variable de drones et représentons le nombre de cibles découvertes dans la figure 2.9(a). La découverte de toutes les cibles dépend du nombre de drones. En effet, plus il y a de drones, plus la zone explorée est grande, et donc plus le nombre de cibles découvertes est important. Comme VESPA garantit la connectivité et la couverture à chaque étape du processus, le nombre de drones libres permettant de se déplacer et d’élargir la zone surveillée diminue avec le temps.

Cependant, même avec très peu de drones (20), il est possible de découvrir au moins une cible. La figure 2.9(a) montre également qu’il est possible de découvrir toutes les cibles avec 70 drones. Avec 160 drones, les cibles sont toujours découvertes, et seulement dans 99% des scénarii avec 120 drones. Ce comportement montre que le caractère aléatoire des décisions de mouvement est géré et contrôlé par VESPA. De plus, avec un même nombre de drones, VESPA découvre en moyenne deux à trois fois plus de cibles que SaS (par exemple, 3 fois plus avec 50 drones et 2,5 fois plus avec 100).

La figure 2.9(b) représente le nombre de drones nécessaires pour couvrir toutes les cibles. Le nombre de drones requis augmente avec le nombre de cibles pour les petites valeurs : 45 drones doivent se déployer sur la zone pour couvrir une cible, tandis que 90 drones sont nécessaires pour découvrir 10 cibles en moyenne. Ce phénomène se retrouve également avec SaS, alors que le nombre de drones nécessaires est plus important (deux fois plus de drones pour 5 cibles). Lorsque le nombre de cibles est important, le nombre de drones est toujours inférieur à 140. En effet, les chemins calculés par VESPA regroupent plusieurs cibles sur un même chemin, limitant ainsi le nombre de drones supplémentaires requis dans la solution. VESPA réduit de 40 % le nombre de drones nécessaires pour découvrir autant de cibles que SaS, tout en optimisant la taille des trajectoires se connectant au puits.
<figure><img src="image_19.png" /></figure>
# CHAPITRE 3

## Optimisation du suivi de capteurs mobiles

<table><tr><td>3.1</td><td>Un modèle dynamique discret</td><td>32</td></tr><tr><td>3.2</td><td>Compromis énergie-distance</td><td>33</td></tr><tr><td>3.3</td><td>Vers un modèle plus efficace</td><td>37</td></tr><tr><td>3.3.1</td><td>Programme Maître : Assurer la couverture des nœuds mobiles</td><td>37</td></tr><tr><td>3.3.2</td><td>Programme Auxiliaire : Calculer efficacement de nouvelles trajectoires</td><td>38</td></tr><tr><td>3.3.3</td><td>Efficacité de la génération de colonnes</td><td>40</td></tr></table>
<figure><img src="image_20.png" /></figure>
Les travaux du chapitre précédent se limitent à la couverture de nœuds fixes au sol par des drones. Or, de nombreuses applications telles que la surveillance de la faune sauvage (Dyo et al., 2012), l'observation et le suivi de véhicules dans les villes intelligentes (Guido, Gallelli, Rogano, & Vitale, 2016), l'enregistrement d'événements sportifs (Hayat, Yanmaz, & Muzaffar, 2016; Cambra et al., 2015), ou encore l'aide pour des interventions de secours après des catastrophes naturelles (Odonkor, Ball, & Chowdhury, 2019; Pham, La, Feil-Seifer, & Deans, 2020) impliquent de considérer la mobilité des utilisateurs au sol afin de leur fournir une solution de connexion et collecter leurs données (Enright, Frazzoli, Pavone, & Savla, 2014).

C'est ainsi que dans ce chapitre, j'ai cherché à étendre les premiers travaux sur la couverture de cibles par les drones, dans le cas où les nœuds au sol sont mobiles. Les applications impliquent dans ce cas une collecte ou une diffusion de données régulières entre les nœuds mobiles et une station de base. L'hypothèse de mobilité des nœuds ajoute une dimension temporelle aux problèmes d'optimisation. En effet, dans les problèmes précédents les drones étaient déployés une fois pour toute aux positions 3D pour assurer la couverture et la connectivité du réseau aérien. Maintenant les drones doivent assurer le suivi des cibles et donc se déplacer avec elles, ce qui peut induire un changement de topologie du réseau aérien au cours du temps. Par exemple, si les nœuds au sol se rassemblent dans une même zone à un moment donné, un seul drone peut suffire à les couvrir et d'autres drones peuvent ne plus être utiles dans le réseau aérien. Au contraire, si des nœuds qui étaient proches les uns des autres à un moment donné prennent des directions différentes, de nouveaux drones seront alors nécessaires au cours de la surveillance pour maintenir la couverture et la connectivité. La dynamique des nœuds et de la topologie du réseau aérien ajoute ainsi des difficul-tés dans nos études pour lesquelles nous devons développer de nouvelles méthodes de résolution des problèmes d'optimisation.

Ce chapitre synthétise mes travaux sur le problème de collecte aérienne de données par une flotte de drones (Aerial Data Collection Problem (ADCP)). Les capteurs sont mobiles avec une trajectoire connue, mais isolés les uns des autres les empêchant de communiquer directement, nécessitant ainsi une infrastructure supplémentaire de collecte des données. Les drones constituent ainsi un réseau backbone couvrant les cibles au sol et collectant l'information jusqu'à une station de base à travers des liens radio multi-sauts. Ces travaux ont été réalisés en collaboration avec Tahiry Razafindralambo et Frédéric Giroire (Caillouet, Giroire, & Razafindralambo, 2018b, 2018a, 2019), Igor Dias Da Silva (Dias Da Silva & Caillouet, 2020; Dias da Silva & Caillouet, 2022) et David Coudert (Dias da Silva, Caillouet, & Coudert, 2021).

Les modèles que nous décrivons ici comprennent différentes hypothèses et contraintes qui ont été abordées individuellement dans la littérature, mais notre modèle les réunit dans un cadre complet : le positionnement 3D des drones pour couvrir les nœuds et qui affecte la portée de couverture, la mobilité aléatoire des nœuds au sol qui affecte le positionnement des drones au cours du temps pour une couverture continue, la connectivité du réseau aérien pour une transmission des données récoltées dans le réseau jusqu'à la station de base. Comme la distance entre les drones et la station de base peut dépasser la portée de communication d'un drone, le réseau de drones doit être connecté à la station de base par des chemins multi-sauts à tout moment. Enfin les objectifs considérés sont également multiples. Nous voulons minimiser le coût global du réseau aérien, ce qui facilite la gestion et la coordination des drones. Nous considérons également la minimisation de leurs altitudes et de l'énergie dépensée pendant leur temps de vol.
## 3.1 Un modèle dynamique discret

Mes thématiques de recherche étant orientées optimisation discrète, j'ai naturellement choisi de discrétiser l'espace temporel en intervalles et d'optimiser le problème de couverture et connectivité en chacun de ces intervalles. D'autres directions comme l'optimisation continue ou stochastique peuvent également être envisagées, mais sortent de mon domaine d'expertise. Mes contributions ont donc été d'étudier le problème pour assurer la couverture des nœuds mobiles par des drones tout en assurant la connectivité avec une station de base à tout moment pour la remontée des données. Du point de vue de l'optimisation discrète, la collecte des données d'un ensemble de points vers une entité centrale peut se modéliser principalement de deux manières. Premièrement, le problème peut être vu comme une tournée de véhicules où la station de base constitue le point de collecte, et chaque drone doit déterminer sa trajectoire afin de visiter toutes les cibles au sol une seule fois (Bullo, Frazzoli, Pavone, Savla, & Smith, 2011). Deuxièmement, cela peut se modéliser comme un problème d'ensemble couvrant correspondant à la sélection d'un sous-ensemble de nœuds reliés à tous les nœuds d'un graphe (Popescu, Rivano, & Simonin, 2016). Les nœuds du graphe correspondent aux positions choisies pour placer les drones, et sont donc inconnus en entrée du problème. Ainsi, il est difficile d'appliquer directement un problème de tournée de véhicules. Au contraire, le problème de couverture est directement relié au problème du choix des positions des drones, et nous permet de considérer les différentes altitudes. Plus spécifiquement, puisque les cibles sont mobiles, nous considérons la version dynamique du problème de couverture (Chrissis, Davis, & Miller, 1982), minimisant le coût de déploiement et le délai de collecte, et ajoutons à cela la connectivité du FANET.

Comme dans le chapitre précédent, nous considérons un ensemble $U$ de drones disponibles, $P$ de positions discrètes en 3 dimensions sur lesquelles positionner les drones. Pour une collecte efficace, les drones sont connectés entre eux et avec une station de base $b$ située au sol. Le modèle de couverture est celui présenté dans la Section 2.3 : une cible est dite couverte par un drone si la distance entre la projection de la position du drone au sol et la cible est inférieure au rayon d'observation du drone. Les cibles au sol, encore appelées nœuds ou capteurs, sont maintenant mobiles, suivant un modèle discret dans lequel leurs positions sont estimées à différents intervalles de temps $t \in [0, T]$. Nous considérons 10 intervalles de temps pour la mobilité. Les coordonnées initiales, finales, et la vitesse de déplacement des cibles sont choisies aléatoirement dans la zone. À chaque étape, la position des cibles évolue en fonction de leur position précédente et de leur vitesse jusqu'à la destination. Étant donnés l'ensemble des cibles $N_t$ avec leurs positions connues au temps $t$, le rayon de couverture, et le rayon de communication des drones, nous introduisons une représentation de notre topologie par un graphe dynamique. À chaque intervalle de temps $t \in [0, T]$ est associé le graphe $G^t = (V^t, E^t)$ défini de la manière suivante :

**Définition 3.1.1** (Graphe dynamique pour ADCP). Au temps $t \in [0, T]$ de la période d'observation, la topologie est modélisée par le graphe orienté $G^t = (V^t, E^t)$ où :

- $V^t = \{b\} \cup P \cup N_t$, et

- $E^t = \{(b, p), p \in P \text{ and } (x_p, y_p) = \min_{q \in P} d(b, q)\} \cup \{(p, q), p, q \in P \text{ and } R_p \ge D_{pq}\} \cup \{(p, n), p \in P, n \in N_t \text{ and } r_p^h \ge d(p, n)\}$.

Un modèle compact en programmation linéaire dérivé du modèle fixe du Chaptire 2 est étendu. Chaque variable $z_p^u$ qui indiquait si le drone $u$ était positionné à la position $p$ est maintenant fonction du temps $t$ considéré : $z_{up}^t$. Et dans chaque graphe $G^t$ nous calculons un flot entre la station de
base et les positions courantes des nœuds au sol afin d'assurer la couverture et la connectivité du réseau aérien. J'ai choisi de ne pas détailler ici ce modèle qui ressemble fortement à celui du chapitre précédent, et qui peut être consulté dans (Caillouet, Giroire, & Razafindralambo, 2019) (sans affectation des drones) et (Dias da Silva et al., 2021) (avec affectation des drones). Néanmoins, la section suivante présente un phénomène observé grâce à ce modèle.

## 3.2 Compromis énergie-distance

Afin de garantir la couverture et la connectivité constantes tout en limitant les coûts d'utilisation du réseau aérien, plusieurs paramètres doivent être pris en compte. Étant donné un ensemble fixé de drones disponibles, nous nous sommes concentrés sur la minimisation du coût de déploiement d'un tel réseau. Pour cela, le temps de vol est un facteur critique, car comme nous l'avons vu dans le chapitre précédent, il est nécessaire d'étudier le compromis entre le nombre de drones déployés, l'altitude à laquelle ils sont placés, mais également le temps total de vol du drone. Ce dernier critère n'était pas considéré précédemment car nous nous concentrions sur le calcul des positions et la connectivité. Il est donc important de le considérer ici, maintenant que le déploiement des drones est amené à évoluer au cours du temps. Le temps de vol des drones est affecté par deux critères principaux : la distance totale à parcourir, et la consommation énergétique qui influe sur le niveau de batterie du drone (Thibbotuwawa, Nielsen, Zbigniew, & Bocewicz, 2018).

Différents modèles pour la consommation énergétique des drones ont été étudiés. Dans (Zorbas, Di Puglia Pugliese, et al., 2016) et (Pugliese et al., 2016), la consommation d'énergie est modélisée par $E = (\beta + \alpha k)t + P_{max}(k/s)$ où $\beta$ est la puissance nécessaire en régime stationnaire, $\alpha$ est le multiplicateur de la vitesse du moteur et $P_{max}(s/k)$ est la puissance consommée pour s'élever à l'altitude $k$ à la vitesse $s$. Les auteurs supposent d'après leurs mesures et les spécifications des fabricants de drones que ce modèle n'est pas loin de la réalité. Dans (Thibbotuwawa et al., 2018), la consommation d'énergie est directement liée à la vitesse de vol du drone, à son poids et à sa charge utile, ainsi qu'à la densité de l'air. La puissance nécessaire au vol est donnée par :

$$P_T = \frac{1}{2} C_D A D v^3 + \frac{W^2}{D b^2 v}$$

où $C_D$ est le coefficient de traînée aérodynamique du drone, $A$ est la surface frontale en $m^2$, $W$ est le poids total en kg, $D$ est la densité de l'air en $kg/m^3$, $b$ est la largeur en mètres et $v$ est la vitesse relative en $m/s$ compte tenu de la vitesse et de la direction du vent. On obtient ainsi la vitesse à laquelle le drone consomme le moins d'énergie :

$$v_{min} = \left( \frac{2W^2}{3C_D A b^2 D^2} \right)^{0.25}$$

(Zeng, Xu, & Zhang, 2019) considère que la puissance liée à la communication est une constante et que la consommation de puissance de propulsion se compose de trois éléments : la puissance du profil des pales, la puissance induite et la puissance parasite. La puissance du profil des pales et la puissance parasite sont nécessaires pour surmonter la traînée du profil des pales et la traînée du fuselage, respectivement. D'autre part, la puissance induite est nécessaire pour surmonter la
<figure><img src="image_21.png" /><figcaption>Figure 3.1 – Énergie consommée par le drone en fonction de sa vitesse.</figcaption></figure>

traînée induite par les pales. Le modèle est donné par la formule suivante :

$$
P(V) = P_0 \left(1 + \frac{3V^2}{U_{tip}^2}\right) + P_i \left(\sqrt{1 + \frac{V^4}{4v_0^4} - \frac{V^2}{2v_0^2}}\right)^{1/2} + \underbrace{\frac{1}{2} d_0 \rho s A V^3}_{\text{Parasite}}
$$

où P₀ et Pᵢ sont des constantes définies par :

$$
P_0 = \frac{\delta}{8} \rho s A \Omega^3 R^3 \quad P_i = (1 + k) \frac{W^{3/2}}{\sqrt{2\rho A}}
$$

Dans ce modèle, la consommation d'énergie supplémentaire due à l'accélération et à la décélération n'est pas prise en compte. Ici, $U_{tip}$ représente la vitesse en bout de pale du rotor, $v_0$ est la vitesse moyenne induite par le rotor en vol stationnaire, $d_0$ et $s$ sont respectivement le coefficient de traînée du fuselage et la solidité du rotor, et $\rho$ et $A$ représentent respectivement la densité de l'air et la surface du disque du rotor. $\delta$ est le coefficient de traînée du profil, $\Omega$ est la vitesse angulaire de la pale en radians/seconde, $R$ est le rayon du rotor en mètres et $k$ est un facteur de correction incrémentiel de la puissance induite. Ce modèle montre que la consommation d'énergie du drone n'est pas linéaire en fonction de la vitesse ou de la distance parcourue (figure 3.1). Pour certaines vitesses, la consommation d'énergie est en fait plus faible que si le drone restait simplement en vol stationnaire. Cela signifie que la réduction de la distance parcourue ne réduit pas nécessairement l'énergie consommée. C'est ce modèle que nous avons choisi de prendre en compte car il est plus précis et plus réaliste.

Pour utiliser ce modèle, nous devons d'abord choisir la vitesse de déplacement appropriée du drone avant de calculer la quantité d'énergie qu'il va consommer. Pour décider de la vitesse à laquelle le drone se déplace entre les positions *p* et *q*, nous calculons d'abord la vitesse minimale, $V_{min} = D_{pq}/tts$, où *tts* est le temps nécessaire aux drones pour changer de position entre deux pas de temps. Un drone consomme le moins d'énergie possible à $V_{opt} = 10,2 \text{ m/s}$, donc si $V_{min} \in [V_{opt}, \infty[$, alors $V_{min}$ est la meilleure vitesse à laquelle le drone peut se déplacer car toute vitesse supérieure implique une consommation plus importante. Mais si $V_{min}$ est inférieur à $10,2 \text{ m/s}$, alors nous calculons $V_{opt}$ en fonction du *tts* de manière à optimiser sa consommation impliquant le temps de vol et le temps d'attente en régime stationnaire dans la nouvelle position. La vitesse de vol choisie pour les drones vaut donc $v = \max(V_{min}, V_{opt} = \min_v(E_{p,q}))$.

Nous pouvons ainsi calculer l'énergie consommée par un drone lorsqu'il se déplace entre deux positions à une vitesse *v*, c'est-à-dire l'énergie consommée par le déplacement plus l'énergie
<table><caption>Table 3.1 – Résultats et performances du modèle pour les cas extrêmes ($\alpha$ = 0 ou 1). Indique les valeurs optimales pour chacun des critères que nous cherchons à optimiser, sans aucune contrainte sur l'autre critère.</caption><thead><tr><th>|P|</th><th>α</th><th>Distance totale (m)</th><th>Distance partielle (m)</th><th>Énergie (J)</th><th>Temps de résolution</th></tr></thead><tbody><tr><td>9</td><td>0</td><td><b>642.62 m</b></td><td>41.78 m</td><td>36389.42 J</td><td>3.5 sec</td></tr><tr><td>16</td><td>0</td><td><b>645.24 m</b></td><td>21.85 m</td><td>47050.98 J</td><td>5.46 min</td></tr><tr><td>25</td><td>0</td><td><b>568.20 m</b></td><td>20.03 m</td><td>48514.66 J</td><td>2.82 h</td></tr><tr><td>9</td><td>1</td><td>956.03 m</td><td>443.19 m</td><td><b>16558.69 J</b></td><td>12.6 min</td></tr></tbody></table>

consommée dans le cas où le drone arrive tôt et qu'il doit rester en vol stationnaire jusqu'au prochain pas de temps :

$$E_{p,q} = P(v) \frac{D_{pq}}{v} + E_{hovering} \quad \text{et} \quad E_{hovering} = \begin{cases} P(0)(tts - \frac{D_{pq}}{v}) & \text{si } p \in P \text{ et } q \in P \\ 0 & \text{sinon} \end{cases}$$

Le programme linéaire mixte présenté dans (Dias Da Silva & Caillouet, 2020) combine les contraintes de placement, de couverture, et de connectivité du réseau aérien déjà vues, dans l'objectif de minimiser le poids total des trajectoires des drones pour suivre les cibles mobiles. Ce poids peut être calculé soit en terme de distance parcourue ou d'énergie dépensée. Une trajectoire pour un drone commence au temps 0 à la station de base, et se termine également à la station de base (au temps $T$ au plus tard). Pour tous les temps entre 0 et $T$ nous ajoutons le poids des déplacements effectués. Les fonctions sont similaires et correspondent à

$$D_{total} = \sum_{p \in P} \sum_{u \in U} D_{pb} z_{up}^{0} + \sum_{t=1}^{T} \sum_{p,q \in P \cup \{b\}} \sum_{u \in U} D_{pq} Z_{up,q}^{t-1,t} + \sum_{p \in P} \sum_{u \in U} D_{pb} z_{up}^{T}$$

pour optimiser la distance parcourue, et

$$E_{total} = \sum_{p \in P} \sum_{u \in U} E_{p,b} z_{up}^{0} + \sum_{t=1}^{T} \sum_{p,q \in P \cup \{b\}} \sum_{u \in U} E_{p,q} Z_{up,q}^{t-1,t} + \sum_{p \in P} \sum_{u \in U} E_{p,b} z_{up}^{T}$$

dans le cas de l'énergie totale dépensée. $Z_{up,q}^{t-1,t}$ vaut 1 si le drone $u$ passe de la position $p$ à la position $q$ entre les temps $t-1$ et $t$. Ainsi, nous dérivons la fonction objectif de notre programme linéaire combinant $D_{total}$ et $E_{total}$ dans un ordre de grandeur similaire (à l'aide de la constante $\beta = V_{opt}/P_{min}$) :

$$\min (1 - \alpha) D_{total} + \alpha \beta E_{total} \quad (3.1)$$

où $\alpha \in [0, 1]$ est un paramètre d'entrée permettant d'étudier le compromis entre les deux objectifs : distance parcourue en vol et énergie consommée.

Le tableau 3.1 présente les résultats avec une seule considération : soit optimiser la distance ($\alpha = 0$), soit l'énergie ($\alpha = 1$). Plus il y a de positions disponibles, plus les déplacements des drones sont précis (cela se voit en particulier en colonne 4 avec les distances partielles calculées pendant la couverture, sans tenir compte des trajets de départ et d'arrivée avec la station de base), mais plus important est l'impact sur le temps de résolution car le nombre de variables et de contraintes augmente. La dernière colonne du tableau montre la croissance exponentielle du temps de résolution avec le nombre de positions. La dernière ligne du tableau 3.1 montre qu'en
<figure><img src="image_22.png" /><figcaption>Figure 3.2 – Échange de positions pour limiter la consommation énergétique.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 3.3 – Compromis énergie dépensée/distance parcourue ($\alpha$ varie entre 0 et 1).</figcaption></figure>

optimisant l'énergie avec 9 positions ($\alpha = 1$), la distance moyenne parcourue par les drones est 10 fois plus élevée, mais l'énergie moyenne consommée est réduite de 55%. En effet, le modèle énergétique adopté nous donne une consommation plus faible lorsque les drones se déplacent à faible vitesse que lorsqu'il sont en position stationnaire. Ainsi, minimiser la consommation d'énergie augmente la mobilité des drones, et conduit à des échanges de positions plutôt que de rester en vol stationnaire. La figure 3.2 montre un exemple avec 4 drones (numérotés 2, 3, 4 et 5) d'échange de positions entre les drones 2 et 4 (et aussi 3 et 5), ce qui leur permet de voyager à 12,5 m/s en consommant moins d'énergie que s'ils étaient restés en vol stationnaire. Par conséquent, un déplacement à une vitesse optimale sur de plus longues distances permet d'augmenter la mobilité des drones tout en minimisant leur consommation d'énergie.

Mais cela ne signifie pas que nous devons choisir entre réduire la distance totale parcourue ou la consommation d'énergie. Des compromis équitables existent comme par exemple sur la figure 3.3, lorsque $\alpha = 0.5$, où les solutions ont en moyenne une distance totale de 683.34 m et une énergie consommée de 17432.84 J.
## 3.3 Vers un modèle plus efficace

Les modèles compacts développés jusque là souffrent d'une croissance exponentielle du temps de résolution avec le nombre de positions. Afin de résoudre efficacement ADCP, nous dérivons une nouvelle formulation du problème, appelée ADCP_CG, qui utilise la technique de génération de colonnes (Desaulniers, Desrosiers, & Solomon, 2005). Cette technique a été utilisée une première fois dans (Caillouet, Giroire, & Razafindralambo, 2019) dans lequel les variables représentent les ensembles de positions choisies pour les drones, qui assurent un réseau aérien connecté. Le but est d'éviter l'énumération de tous les ensembles possibles et ne sélectionner qu'un ensemble pour chaque temps $t$ avec d'assurer la couverture des nœuds mobiles. Néanmoins ce modèle, qui donne de bonnes performances, ne calcule qu'un ensemble de positions à chaque temps mais nous ne savons pas quel drone ira en quelle position. C'est ce qui a motivé le sujet de thèse d'Igor Dias Da Silva qui se concentre sur le calcul des trajectoire des drones.

Dans la suite de cette section, je choisis de présenter plus particulièrement le modèle développé avec Igor Dis Da Silva et David Coudert (Dias da Silva et al., 2021) dans lequel les colonnes représentent les trajectoires des drones au cours du temps. Cette formulation nous permet de séparer le problème en deux parties : (i) un programme maître qui gère la mobilité et assure la couverture des cibles au cours du temps, et (ii) un programme auxiliaire qui génère de nouvelles trajectoires permettant d'améliorer la solution courante de notre problème.

**Définition 3.3.1** (Trajectoire discrète d'un drone). Une trajectoire $c \in C$ est une séquence de positions $p \in P \cup \{b\}$ (où $b$ correspond à la position de la station de base) par lesquelles un drone doit passer au cours du temps de surveillance.

Un drone sera associé à une position dans $P \cup \{b\}$ à chaque temps $t \in [0, T]$, $\{b\}$ correspondant au cas où le drone n'est pas utilisé. Un drone pourra ainsi être déployé, puis rapatrié vers la station de base s'il n'est plus utile. Ou au contraire il peut patienter un certain temps en la station de base avant d'aller enrichir la couverture si nécessaire. Évidemment l'ensemble $C$ de toutes les trajectoires possibles est de taille exponentielle. La génération de colonnes nous permet ainsi d'éviter son énumération complète dans un modèle d'optimisation efficace.

Le procédé de génération de colonnes utilise la dualité afin de déterminer l'ensemble des variables du programme maître (appelées *colonnes*) qui sont actives dans la solution optimale. Ces colonnes sont ainsi générées par un programme auxiliaire qui permet de calculer uniquement celles qui violent une contrainte du programme maître. Dans la suite, nos colonnes sont définies sur les trajectoires des drones.

### 3.3.1 Programme Maître : Assurer la couverture des nœuds mobiles

Le problème maître est le programme linéaire qui permet de répondre à notre problème principal de couverture et suivi des nœuds mobiles. Il contient un ensemble de variables définies sur les trajectoires $C$ des drones. La variable binaire $y_c$ permet ainsi d'indiquer si la trajectoire $c \in C$ est sélectionnée ou non. Cependant, nous ne résolvons pas le programme maître avec l'ensemble de toutes les variables possibles. Nous commençons par ne considérer qu'un petit nombre de variables et nous utilisons le problème auxiliaire, ou *pricing problem*, pour ajouter de nouvelles variables au problème maître afin de nous conduire à la solution optimale. De plus, nous relâchons les conditions d'intégralité des variables dans le processus de génération de colonnes afin de vérifier le théorème de séparation/optimisation assurant la solution optimale du problème relâché à
la fin du processus. Ainsi nous pouvons sélectionner seulement une fraction d'une trajectoire, i.e. $0 < y_c < 1$. Afin de garantir une solution entière de notre problème ADCP, nous résolvons une fois le problème maître entier à la fin avec l'ensemble des trajectoires obtenus par la génération de colonnes. Nous verrons que les solutions entières obtenues sont proches de l'optimal entier.

Le programme maître du problème ADCP_CG optimise la distance parcourue par les drones, à savoir :

$$ \min \sum_{c \in C'} D_c y_c \qquad (3.2) $$

où $D_c = \sum_{p,q \in c} D_{pq}$ correspond à $D_{total}$ de la section précédente pour les positions connues et contenues dans la trajectoire $c$, et $C' \subseteq C$ est l'ensemble courant des trajectoires considérées par le programme maître. Les contraintes du problème vérifient quant à elles que les trajectoires sélectionnées permettent d'assurer un flot à chaque temps $t \in [0, T]$ depuis la station de base $b$ jusqu'aux nœuds $N_t$ dans le graphe $G^t$ passant par des positions contenues dans les trajectoires sélectionnées. Nous nous assurons également qu'une même position n'est pas choisie par plusieurs trajectoires au cours du même intervalle de temps afin d'éviter les collisions des drones.

### 3.3.2 Programme Auxiliaire : Calculer efficacement de nouvelles trajectoires

Comme nous résolvons la relaxation continue du programme maître où les variables $y_c$ sont comprises entre 0 et 1, la complexité du processus de génération de colonnes se retrouve dans le problème auxiliaire permettant de générer de nouvelles variables. En effet, le problème auxiliaire doit identifier une contrainte violée par les variables duales et construire une nouvelle variable pour le programme maître. L'identification d'une contrainte violée, qui brise ainsi la garantie d'optimalité de la solution courante, correspond à identifier une variable de coût réduit négatif. Dans notre cas, pour toute solution réalisable $y_1, ..., y_n$ du programme maître relâché (ou primal ici), nous avons une solution équivalente $\beta^{(1)}, ..., \beta^{(m)}$ pour son problème dual. Si cette solution équivalente est une solution réalisable du problème dual, cela signifie que $y_1, ..., y_n$ est une solution optimale du programme primal. C'est ce qu'on appelle la garantie d'optimalité. En créant une variable qui rend la solution correspondante du problème dual infaisable, nous prouvons que la nouvelle variable nous permet de trouver une meilleure solution parce que nous brisons la garantie d'optimalité de la solution actuelle.

Pour dériver notre problème auxiliaire, nous examinons le problème dual. Une variable du programme dual correspond à un ensemble de contraintes du programme primal, et réciproquement les contraintes du dual sont associées aux variables du primal. Les variables duales $\beta_{tp}^1$ et $\beta_{tp}^2$ associées aux contraintes du programme maître contenant les variables $y_c$ nous permettent d'obtenir la contrainte duale associée aux variables $y_c$ :

$$ - \sum_{t=0}^{T} \sum_{p \in P} \delta_{p}^{t} \beta_{tp}^{1} + |N_t| \sum_{t=0}^{T} \sum_{p \in P} \delta_{p}^{t} \beta_{tp}^{2} \leq D_{total} \qquad (3.3) $$

où $\delta_p^t$ est une constante indiquant si la position $p$ est choisie au temps $t$.

Une fois le problème maître résolu, nous obtenons les valeurs correspondantes pour toutes les $\beta_{tp}^1$ et $\beta_{tp}^2$ et la contrainte 3.3 est satisfaite pour toutes les trajectoires dans $C'$ car nous avons la solution optimale du problème maître actuel. Dans ce qui suit, nous cherchons à déterminer s'il existe de nouvelles trajectoires dans le FANET qui violent la contrainte 3.3. C'est l'objectif du problème auxiliaire. Si au moins une telle trajectoire existe, nous l'ajoutons à l'ensemble
<figure><img src="image_24.png" /><figcaption>Figure 3.4 – Graph associated to the problem of the best path in the program auxiliary.</figcaption></figure>

$C'$ de variables du problème maître. Si aucune nouvelle trajectoire ne viole 3.3, le théorème de séparation-optimisation garantit que nous avons atteint la solution optimale du programme maître relâché.

Une manière classique est de dériver un programme auxiliaire en programmation linéaire en
nombres entiers ou mixtes permettant de générer la trajectoire qui minimise :

$$
\sum_{t=0}^{T} \sum_{p \in P} \delta_{p}^{t} \beta_{tp}^{1} - |N_{t}| \sum_{t=0}^{T} \sum_{p \in P} \delta_{p}^{t} \beta_{tp}^{2} + D_{total} \quad (3.4)
$$

Ainsi, si la solution optimale de ce programme auxiliaire nous donne une valeur négative pour
cette fonction objective, alors la contrainte 3.3 est violée et la trajectoire constitue une nouvelle
variable de notre programme maître. Ce programme n'est pas présenté ici mais peut être consulté
dans (Dias da Silva et al., 2021).

Nous nous concentrons ici sur un problème auxiliaire basé sur les plus courts chemins. Étant donné un graphe $G = (V, E)$ tel qu’illustré dans la figure 3.4 où les sommets sont les positions et la station de base à chaque pas de temps et les arêtes relient les positions passées aux positions futures, nous pouvons interpréter notre problème auxiliaire comme étant la recherche d’un chemin de $b_i$ à $b_f$ de coût minimum, dans le but de sélectionner une séquence de positions dans le temps qui nous permette de briser la contrainte d’optimalité. Chaque arête du graphe est pondérée par le coût négatif égal à l’opposé de la distance entre les positions connectées par l’arête, et chaque sommet a comme coût $\beta_{tp}^1 - |N_t|\beta_{tp}^2$. L’objectif ici est donc équivalent à minimiser l’équation (3.4), ce qui nous permet d’associer le programme auxiliaire à un calcul de plus court chemin se résolvant en temps polynomial :

**Lemme 3.3.1.** Le problème auxiliaire peut être résolu en $O(|P|^2|T|)$.

Cela vient du fait que le graphe *G* (figure 3.4) est acyclique, ainsi le calcul du plus court chemin de *b*<sub>*i*</sub> à *b*<sub>*f*</sub> peut se faire en *O*(*|V*| + *|E**) (Cormen, Leiserson, Rivest, & Stein, 2009). Comme le nombre de sommets est en *O*(*|P*|*|T*|) et que le nombre d'arcs est en *O*(*|P*<sup>2</sup>|*T*|), la complexité en temps polynomial est validée.
<figure><img src="image_25.png" /><figcaption>Figure 3.5 – Comparaison des formulations : compacte sans génération de colonnes (MILP), génération de colonnes avec programme auxiliaire exact (CGLP), génération de colonnes avec programme auxiliaire de plus court chemin (CGSP)</figcaption></figure>

### 3.3.3 Efficacité de la génération de colonnes

Un premier aperçu de l'efficacité d'utiliser la technique de génération de colonnes se situe dans l'évaluation du temps de résolution. La figure 3.5(a) montre déjà l'augmentation exponentielle du temps de résolution du programme linéaire compact sans génération de colonnes (MILP : courbe verte). L'utilisation de la génération de colonnes, avec un programme linéaire auxiliaire à variables entières pour la génération de nouvelles trajectoires (CGLP : courbe bleue), est plus efficace que le MILP mais souffre également du nombre de possibilités important dans le choix des positions pour les trajectoires. Le gain du développement de notre algorithme de plus courts chemins sur le graphe présenté en figure 3.4 pour le programme auxiliaire de notre génération de colonnes (CGSP : courbe rouge) apparaît ainsi clairement sur la figure 3.5(a).

Observons que la solution obtenue en résolvant le programme maître entier (MP) avec $C'$ n'est pas toujours une solution optimale pour le problème. Cependant, il s'agit d'une solution valide dont le coût $\tilde{z}_{MP}$ est une borne supérieure de la solution optimale de ADCP. De plus, la valeur ob- jective $z_{RMP}^*$ obtenue lors de la résolution du programme maître relâché par génération de colonnes (RMP) est une borne inférieure de la valeur de la solution optimale de ADCP. Par conséquent, nous pouvons évaluer l'écart d'optimalité d'une solution par la formule $(\tilde{z}_{MP} - z_{RMP}^*)/z_{RMP}^*$. Pour toujours obtenir une solution optimale, il faut combiner le CG avec un processus de branch-and-bound, une approche beaucoup plus complexe que nous n'avons pas abordée. Bien que la généra- tion de colonnes n'atteigne pas toujours la solution optimale, la distance par rapport à la solution optimale est faible et nous pouvons considérer plus de positions qu'avec le MILP. ADCP_CG at- teint la même solution que le MILP dans 54% de nos expériences. Lorsque l'optimal n'est pas atteint, l'écart moyen à l'optimal de la génération de colonnes est de 5%. Il est de 9% lorsque l'on considère 9 positions possibles pour les drones, il diminue à 2% et 3.1% lorsque l'on augmente le nombre de positions possibles respectivement à 16 et 25. L'augmentation du nombre de positions améliore les solutions grâce au positionnement plus précis des drones. Avec peu de positions, lors- qu'un capteur quitte la couverture d'un drone, ce dernier doit parcourir une distance plus grande que nécessaire pour continuer à couvrir le capteur, car les positions sont très éloignées les unes des autres. Lorsque nous augmentons le nombre de positions, les drones peuvent être déployés
avec plus de précision, de sorte qu'ils ont moins besoin de se déplacer, et s'ils doivent se déplacer, ils peuvent ajuster leur positionnement en se déplaçant sur de plus petites distances en raison de la plus grande densité de positions. C'est ce qui est illustré dans la figure 3.5(b) où plus il y a de positions, moins les drones se déplacent en moyenne. Par conséquent, avec CGSP, non seulement les solutions sont de meilleure qualité, mais nous les trouvons également plus rapidement.
<figure><img src="image_26.png" /></figure>
## CHAPITRE 4

# Recharge énergétique de capteurs par des drones

<table><tr><td>4.1</td><td>Utiliser les drones comme source de signaux radio-fréquence</td><td>45</td></tr><tr><td>4.2</td><td>Un modèle énergétique réaliste</td><td>46</td></tr><tr><td>4.3</td><td>Une approche en deux étapes</td><td>48</td></tr><tr><td>4.3.1</td><td>Déterminer l'ensemble optimal des positions</td><td>48</td></tr><tr><td>4.3.2</td><td>Optimiser les trajectoires sans conflits</td><td>50</td></tr><tr><td>4.3.2.1</td><td>Les algorithmes gloutons</td><td>51</td></tr><tr><td>4.3.2.2</td><td>Une solution proche de l'optimal</td><td>53</td></tr></table>
<figure><img src="image_27.png" /></figure>
Ce chapitre retrace mes travaux concernant l'utilisation de drones afin de recharger les batteries de capteurs fixes au sol à l'aide de transmission de signaux radio-fréquence (RF).

Cette problématique ajoute une dimension temporelle aux modèles d'optimisation vus précédemment dans ce manuscrit, car l'efficacité de la recharge énergétique dépend non seulement de la distance entre le drone et le capteur à recharger, mais également de la durée pendant laquelle le drone reste en régime stationnaire dans une position permettant d'atteindre un certain nombre de nœuds à recharger. Ce temps de recharge doit maintenant se combiner avec le déplacement des drones d'une position à une autre que nous considérions en discrétisant le temps en intervalles. En d'autres termes, le temps de recharge s'insère ici à l'intérieur de chaque intervalle de temps afin de quantifier la durée de chaque intervalle pour chaque drone considéré. Nous verrons que cela rend plus difficile le calcul des trajectoires complètes des drones car cela désynchronise les drones entre eux par rapport aux intervalles de temps décidant de leurs positions. Une autre différence avec les travaux précédents est la disparition de la contrainte de connectivité entre les drones, car dans ce cas, les drones n'ont pas besoin d'échanger des messages entre eux, la coordination de leurs déplacements au cours du temps se fait en pré-calcul de manière centralisée afin d'éviter les collisions et les placements engendrant une perte d'efficacité de la recharge, comme nous le verrons dans l'explication des hypothèses de ce chapitre.

Dans la suite, l'approche est découpée en deux étapes. La première étape se concentre sur l'obtention d'un ensemble optimal des positions dans lesquelles un drone doit être placé afin d'assurer la recharge demandée par tous les nœuds du réseau. Pour chaque position, le temps de charge nécessaire est calculé conjointement par le modèle, de manière à minimiser le temps total de charge du réseau. Cette première étape a donné lieu à des publications dans des conférences internationales en collaboration avec Tahiry Razafindralambo et Dimitrios Zorbas. En particulier, le travail décrivant notre approche avec le premier modèle d'optimisation présenté dans ce chapitre a reçu le prix du meilleur article de la conférence Wireless Days 2019 (Caillouet, Razafindralambo, & Zorbas, 2019a, 2019b).

Ce premier travail a permis à Igor Dias Da Silva de poursuivre les objectifs de sa thèse, en améliorant le modèle d'optimisation et en développant une deuxième étape nous permettant d'obtenir les trajectoires complètes des drones tout en évitant les conflits. Cette deuxième étape récupère l'ensemble optimal des positions et calcule les trajectoires à l'aide d'algorithmes à heuristiques gloutonnes comparant différents critères de sélection successive des positions. Le travail sur les trajectoires d'Igor Dias Da Silva a été fait en collaboration avec Yann Busnel, et est disponible en détail dans (Dias da Silva et al., 2022, 2023).

## 4.1 Utiliser les drones comme source de signaux radio-fréquence

L'optimisation de la consommation énergétique des capteurs sans fil a été le point central de nombreuses études dans la littérature. Les capteurs sans fil étant des objets autonomes alimentés par des batteries, les performances de l'application sous-jacente dépendent fortement de leur durée de vie. En particulier, la fréquence de génération et de transmission des données par les capteurs consomment la majeure partie de l'énergie du réseau. Optimiser la consommation de la batterie est important, mais cela ne doit pas se faire au détriment de l'application.

Par ailleurs, même si les applications sont déjà optimisées, prolonger la durée de vie d'un réseau de capteurs sans fil demeure un problème fondamental. Le déploiement des capteurs sans fil peut avoir lieu dans des environnements difficilement accessibles, où il n'est pas toujours possible
de remplacer les batteries à faible coût. Pour faire face à ce problème ou le soulager, des solutions de recharge énergétique ont été proposées. D'une part, il est possible de récupérer de l'énergie en utilisant, par exemple, des panneaux solaires ou d'autres types de dispositifs équivalents. Cependant, même si ce dispositif est très efficace et peut considérablement prolonger la durée de vie des capteurs, la quantité d'énergie n'est pas constante et nécessite la plupart du temps un équipement supplémentaire de grande taille. D'autre part, en utilisant une technologie telle que la recharge par émission de signaux radio-fréquence RF (Lu et al., 2015), une quantité constante d'énergie (à la demande) peut alors être proposée aux nœuds et même recharger plusieurs nœuds en même temps.

Des travaux récents ont étudié l'utilisation des signaux radio-fréquence (RF) pour les systèmes de récupération d'énergie (Sangoleye, Irtija, & Tsiropoulou, 2021). L'utilisation de drones comme chargeurs pour améliorer la durée de vie des réseaux de capteurs sans fil a également attiré l'attention. Cependant, de nombreuses études se limitent à déployer un seul drone (Yang, Xu, & Shikh-Bahaei, 2020; Arabi, Sabir, Elbiaze, & Sadik, 2018; Saif et al., 2021; Xu, Liu, Huang, & Yuen, 2021; Feng et al., 2020), ce qui ne passe pas à l'échelle pour les grands réseaux de capteurs et les vastes zones de couverture. Dans un tel cas, le drone, qui est également limité en énergie, doit décomposer sa trajectoire en plusieurs cycles de courte durée pour fournir suffisamment d'énergie à tous les capteurs. Les études existantes se limitent également à un espace bi-dimensionnel (S. Zhang, Qian, Kong, Wu, & Lu, 2015), ce qui réduit l'accessibilité et les opportunités de recharge. De plus, certains travaux se concentrent sur un modèle de recharge un à un, dans lequel un drone est dédié à un capteur (Park, Kang, & Choi, 2021), ou à un nœud élu d'un groupe de capteurs (Do, Le, Liu, & Jamalipour, 2021; Zorbas, Raveneau, & Ghamri-Doudane, 2016b). Ces scénarios nécessitent donc autant de drones que de capteurs et n'exploitent pas la mobilité des drones et l'émission d'énergie omnidirectionnelle pouvant atteindre plusieurs nœuds simultanément.

Contrairement aux travaux existants de la littérature qui ne considèrent pas toujours des modèles d'énergie réalistes ni la mobilité des drones, nous nous sommes attachés à considérer les hypothèses suivantes :

- nous prenons en compte des estimations de recharge énergétique réalistes (à la fois pour les émetteurs et les récepteurs) obtenues auprès d'un fabricant de modules de recharge d'énergie RF,

- nous positionnons les drones dans l'espace 3D en prenant en compte l'effet de l'ajustement de l'altitude sur la puissance de recharge,

- et nous considérons que les drones peuvent changer de position dans l'espace 3D pour améliorer la couverture et, par conséquent, minimiser le temps total de recharge.

## 4.2 Un modèle énergétique réaliste

Étant donné un ensemble de nœuds N avec des positions 2D connues et fixes, l'objectif est de déployer et de planifier de manière optimale les positions d'un ensemble de drones U dans l'espace en 3D afin de fournir une quantité d'énergie au moins égale à E à tous les nœuds du réseau dans le plus court laps de temps possible borné par le temps de vol maximum τ d'un drone. Cette quantité d'énergie est une valeur empirique qui doit être suffisante pour alimenter un nœud, lui permettre de réaliser une mesure et de transmettre les données au drone (ou à une station de base). Nous faisons ici l'hypothèse que le temps de transmission est négligeable par rapport au temps de recharge des nœuds.
<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /><figcaption>Figure 4.1 – Modèle de recharge.</figcaption></figure>

Chaque nœud $n \in N$ est équipé d'un module de récolte d'énergie RF capable de convertir la puissance RF des signaux émis en puissance continue (DC). Un chargeur doté d'une antenne directionnelle orientée vers le sol est utilisé par les drones pour émettre en continu de l'énergie dans le réseau et recharger les nœuds. Un drone peut ajuster son altitude pour recharger plusieurs nœuds en même temps.

La quantité d'énergie reçue par chaque nœud est influencée par sa distance par rapport à la source de transmission (chargeur sur le drone) et les conditions environnementales (figure 4.1). La formule (4.1) décrit la puissance récoltée par un nœud $n$ lorsqu'il se trouve dans le champ de vision en ligne directe du drone $u \in U$ (Zorbas, Raveneau, & Ghamri-Doudane, 2016a) :

$$P_{hu} = P_{rx}^{d_{un}} f^{d_{un}}, \qquad (4.1)$$

où $P_{rx}^{d_{un}}$ est la puissance reçue et $f^{d_{un}}$ est l'efficacité de l'antenne de récolte d'énergie à la distance $d_{un}$. La puissance reçue à une distance $d$ est donnée par le modèle de propagation suivant (Win, Pinto, & Shepp, 2009) :

$$P_{rx}^{d} = P_{0} \frac{e^{2\sigma G}}{d^{2b}}, \qquad (4.2)$$

où $\frac{e^{2\sigma G}}{d^{2b}}$ suit une distribution log-normale avec un coefficient d'atténuation $\sigma$ ($G \sim N(0, 1)$) et $b$ est l'exposant de perte d'amplitude. $P_0$ est la puissance reçue à la distance de référence.

La puissance minimale récoltée nécessaire pour qu'un nœud recharge sa batterie dépend de l'efficacité du convertisseur pour la puissance reçue correspondante à cette distance particulière. Nous désignons par $\Gamma$ ce seuil de récolte minimale, qui est une constante dépendant du matériel.

La formule (4.3) définit l'énergie récoltée par un nœud $n$ envoyée par $u$ pour une période de temps donnée $t$ :

$$H_{n}^{t} = \int_{0}^{t} P_{hu} t dt. \qquad (4.3)$$

Cette énergie est stockée directement dans un super-condensateur avec une certaine proportion de perte exprimée de la manière suivante $\eta H_n^t$, où $\eta \in (0, 1)$.

Dans les tests de validation, nous souhaitons modéliser au mieux le fonctionnement réel de la recharge énergétique par envoi de signaux RF, c'est pourquoi nous prenons des données du modèle d'énergie que l'on obtient avec du matériel disponible. Ainsi, les drones peuvent transmettre une puissance EIRP de 3W (915 MHz) (Kraft, 1999), ce qui, selon notre modèle d'atténuation, une
décomposition en fonction linéaire par morceaux et les données du fabricant, se traduit par environ
Γ = 6.3 × 10⁻⁵ à 0.01 W d'énergie récoltée en fonction de la distance. Les valeurs de récupération
d'énergie sont calculées en fonction de l'efficacité des modules Powercast P2110B (*Powercast
P2110B*, s. d.) fonctionnant à 915 MHz.

4.3 Une approche en deux étapes

À partir de ce modèle d'énergie, nous pouvons modéliser au mieux le problème de recharge énergétique des capteurs par les drones. En effet, la formule (4.3) nous permet de savoir si un drone est capable de charger un capteur suivant sa position 3D. Nous pouvons ainsi déterminer l'ensemble des positions que les drones doivent visiter, et calculer la durée nécessaire en chaque position pour assurer la recharge demandée par les nœuds. Cette première approche a donné lieu a un modèle en programmation linéaire et une heuristique décrits dans (Caillouet, Razafindralambo, & Zorbas, 2019a). Le problème général qui en découle est d'être capable de calculer les trajectoires des drones permettant de recharger tous les capteurs du réseau.

Trouver une solution optimale de ce problème général est très difficile. (S. Zhang et al., 2015) ont montré que le calcul du positionnement optimal des chargeurs est NP-difficile. (Zorbas & Douligeris, 2018) ont lié ce problème à celui de l'ensemble couvrant. Notre problème ici est une version dynamique de celui de (S. Zhang et al., 2015), où les drones se déplacent, et nous voulons trouver les trajectoires optimales tout en évitant les conflits de positionnement et de recharge entre les drones. L'optimisation globale de la trajectoire 3D des drones pour le transfert d'énergie sans fil a été étudiée dans (Feng et al., 2020). Les auteurs montrent que pour maximiser l'énergie récoltée en tenant compte du placement 3D des drones et du temps de charge, le problème doit être décomposé en sous-problèmes résolus séparément. Cependant, ils limitent leur étude au cas d'un seul drone et d'une position en 2D, puis ajustent l'altitude dans une deuxième étape.

Compte tenu de ces résultats, nous proposons un processus en deux étapes pour minimiser le temps de recharge d'un ensemble de capteurs. Nous cherchons également à minimiser le nombre de drones requis et le temps de vol global. Ce processus, développé au cours de la thèse d'Igor Dias Da Silva, est entièrement détaillé dans (Dias da Silva et al., 2022) et (Dias Da Silva, 2023).

4.3.1 Déterminer l'ensemble optimal des positions

Soient *P* l'ensemble des positions 3D possibles pour les drones et *E*<sub>*n*</sub> les besoins énergétiques de chaque nœud *n* ∈ *N*. Dans le programme linéaire mixte en nombres entiers (MILP), α<sub>*u*</sub> et β<sub>*p*</sub><sup>*u*</sup> sont des variables binaires indiquant respectivement si le drone *u* ∈ *U* est utilisé et s'il est déployé à la position 3D *p* ∈ *P*, et t<sub>*p*</sub><sup>*u*</sup> sont des variables continues représentant le temps associé à la localisation du drone *u* à la position *p*. L'objectif est de minimiser le temps nécessaire aux drones pour fournir la quantité d'énergie requise par les capteurs sans dépasser le budget (en termes de nombre de drones) (contrainte 4.7). Cela revient à minimiser le temps de vol du drone le plus long, décomposé ici en un objectif 4.4 minimisant une variable continue λ égale à la limite supérieure du temps de vol de chaque drone (contrainte 4.5).
<figure><img src="image_30.png" /><figcaption>Figure 4.2 – Temps de résolution du MILP.</figcaption></figure>

$$ \min \lambda \qquad (4.4) $$

$$ \sum_{p \in P} t_p^u \leq \lambda, \forall u \in U \qquad (4.5) $$

$$ \sum_{u \in U} \sum_{p \in P} (1 - \eta) H_n^{t_p^u} \geq E, \forall n \in N \qquad (4.6) $$

$$ \sum_{u \in U} \alpha_u \leq B \qquad (4.7) $$

$$ \sum_{p \in P} t_p^u \leq \tau \alpha_u, \forall u \in U \qquad (4.8) $$

$$ \sum_{u \in U} \beta_p^u \leq 1, \forall p \in P \qquad (4.9) $$

$$ t_p^u \leq \tau \beta_p^u, \forall u \in U, p \in P \qquad (4.10) $$

$$ \sum_{u \in U} t_p^u + \sum_{p' \in P, (x_p, y_p) = (x_{p'}, y_{p'})} (\sum_{u' \in U} t_{p'}^{u'}) \leq \lambda, \forall p \in P \qquad (4.11) $$

$$ \alpha_u \in \{0, 1\}, \beta_p^u \in \{0, 1\}, t_p^u \in \mathbb{R}, \lambda \in \mathbb{R} \qquad (4.12) $$

La contrainte 4.6 garantissent la fourniture des besoins en énergie de chaque nœud au sol. Nous vérifions que la somme des positions collectant une puissance supérieure à Γ est suffisante pour répondre à l'exigence du nœud. Chaque drone peut être placé à différents endroits au cours de l'opération (contrainte 4.8) tant que son temps de vol ne dépasse pas la limite τ. Un seul drone peut être placé à une position donnée (contrainte 4.9) afin de limiter le mouvement des drones, et si un emplacement 2D avec une altitude correspondante est choisi pour un drone, aucun autre drone ne peut être placé au-dessus ou au-dessous de celui-ci (contrainte 4.11). De cette façon, nous évitons d'aligner plusieurs drones à différentes altitudes et limitons ainsi les collisions physiques entre eux ainsi que les interférences.

Ce modèle a été résolu optimalement sur des scénarios dans lesquels nous faisons varier le nombre de drones disponibles, le nombre de nœuds à recharger, et le nombre de positions pos-
<figure><img src="image_31.png" /><figcaption>(a) Nombre moyen de positions/drone.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>(b) Altitude maximum et moyenne.</figcaption></figure>

<caption>Figure 4.3 – Analyse des positions et altitudes des drones.</caption>

sibles pour placer les drones en régime stationnaire. Comme tous les problèmes que nous avons étudiés dans cette partie, le temps de résolution augmente exponentiellement avec le nombre de positions considérées, comme nous pouvons le voir dans la figure 4.2. Néanmoins les résultats sont obtenus pour des topologies jusqu’à 500 positions possibles pour les drones (régulières en grille 10 × 10 * 5 altitudes de 1 à 5m) ce qui permet d’obtenir des résultats satisfaisants sur les scénarios envisagés. De plus, le modèle se résout en quelques secondes pour des scénarios jusqu’à 20 nœuds et 245 positions. Un algorithme glouton a été proposé est peut être consulté dans (Caillouet, Razafindralambo, & Zorbas, 2019a).

Le compromis entre le nombre de drones utilisés et l'altitude à laquelle les placer (déjà cuté dans le chapitre 2) se pose également ici. En effet, en plaçant les drones à basse altitude, le temps total de recharge peut être amélioré car la puissance reçue des signaux RF est plus importante. Lorsque nous disposons de suffisamment de drones disponibles pour recharger les capteurs (c'est-à-dire que la contrainte 4.7 n'est pas contraignante), le modèle les utilisera pour réduire l'altitude moyenne des positions sélectionnées. En revanche, en raison des limitations de durée de vie des drones, le nombre de positions visitées peut également être limité. Ce compromis est pris en compte par le modèle lors du calcul du temps associé à la position (c'est-à-dire la valeur de la variable $t_p^u$). Plus on utilise de drones, plus le modèle trouvera le meilleur compromis entre le nombre de positions visitées par un drone (minimiser la somme de $t_p^u$ pour toutes les positions visitées $p$), et l'efficacité de récolte de chaque position sélectionnée (maximiser la somme de $H_n^{t_p^u}$ pour toutes les positions $p$ en choisissant l'altitude appropriée).

Dans la figure 4.3(a), nous pouvons voir que pour un nombre suffisant de drones, chacun va se déplacer en moyenne sur 2 ou 3 positions afin de répondre aux besoins en énergie des nœuds. Et même s'il existe des positions sélectionnées à 3m (pour $|P| = 125$ ou 250), ou 5m (pour un plus grand $|P|$), l'altitude moyenne de toutes les positions sélectionnées dépasse à peine 1m (figure 4.3(b)). Cela illustre que les positions de basse altitude sont favorisées par notre modèle.

## 4.3.2 Optimiser les trajectoires sans conflits

La sortie du modèle linéaire précédent nous donne, pour chaque drone, l'ensemble des positions et le temps de vol stationnaire associé à chaque position pour envoyer de l'énergie de manière optimale vers les capteurs. L'objectif ici est de construire les trajectoires des drones
passant par les positions sélectionnées, en intégrant des contraintes spatio-temporelles et des
conflits de positionnement induites par les propriétés de recharge par signaux RF. Ce travail
améliore l'état de l'art sur le sujet car le calcul des trajectoires de plusieurs drones permettant la
recharge de la batterie de capteurs n'a pas été étudiée avec toutes les contraintes que nous avons
pris en compte : différentes altitudes possibles pour chaque position pour les drones, recharge
simultanée de plusieurs capteurs par un seul drone, et pris en compte des conflits pouvant résulter
du déplacement d'une flotte de drones au cours du temps au dessus des capteurs et de l'inefficacité
de la recharge d'un même capteur par plusieurs drones simultanément. En effet, cette dernière
contrainte a été mise en évidence dans (Altinel & Karabulut Kurt, 2016). Les auteurs montrent
qu'il n'est pas correct de considérer que la puissance reçue par un nœud pouvant être convertie en
énergie est égale à la somme des puissances émises par les drones. Nous avons donc intégré cette
contrainte dans nos modèles de manière forte en interdisant à plusieurs drones d'être capables de
charger le même capteur simultanément.

Plus précisément, la sortie du modèle linéaire précédent est un ensemble de tâches, où une
tâche *k* est définie par un drone *u*<sub>*k*</sub>, une position *p*<sub>*k*</sub>, une durée *t*<sub>*k*</sub> en secondes et un ensemble
de capteurs *N*<sub>*k*</sub> qui sont chargés pendant l'exécution de la tâche. Chaque drone peut avoir plu-
sieurs tâches à accomplir, et notre objectif ici est de déterminer l'ordre dans lequel les drones
accomplissent leurs tâches respectives sans conflit.

**Définition 4.3.1 (Conflits de tâches).** Il existe un *conflit* entre deux tâches *k* et *k*\* si :

— elles utilisent le même drone ($u_k = u_{k*}$),

— ou elles utilisent la même position ($p_k = p_{k*}$),

— ou elles chargent au moins un même capteur en même temps ($N_k \cap N_{k*} \neq \emptyset$) (pour éviter les contraintes de charge multiple (Altinel & Karabulut Kurt, 2016)).

Une tâche est dite sans conflit à un moment donné si elle n'a aucun conflit avec aucune des
tâches en cours d'exécution.

Même si nous ignorions les conflits potentiels entre les tâches, déterminer l'ordre le plus ra-
pide des tâches pour chaque drone équivaut à résoudre le Problème du Voyageur de Commerce
(TSP) qui est connu pour être NP-difficile. Nous avons donc choisi de développer des algorithmes
gloutons qui attribuent les tâches tout en évitant les conflits. Nous avons néanmoins calculé une
solution optimale pour les petits scénarios afin d'évaluer au mieux les performances de nos heu-
ristiques.

4.3.2.1 Les algorithmes gloutons

Le but était ici de trouver un compromis entre qualité de la solution et rapidité d'exécution afin de proposer des solutions approchées pouvant se calculer rapidement. Différents critères d'ordre entre les tâches ont donc été comparés :

1. Sélectionner de préférence les tâches les plus courtes (*Shortest-Task-First*), donc avec un temps de vol stationnaire faible,

2. Sélectionner de préférence les tâches les plus longues (*Longest-Task-First*),

3. Sélectionner de préférence les tâches qui minimisent le temps de vol des drones pour re-
joindre ces positions (*Time-of-Flight*);
<figure><img src="image_33.png" /><figcaption>Figure 4.4 – Exemple dans une grille 5x5 avec 40 capteurs et 4 drones.</figcaption></figure>

4. Sélectionner de préférence les tâches qui minimisent le temps d'attente des drones dans leur position précédente (*Wait-Time*).

Dans la suite, nous présentons en détail l’algorithme *Wait-Time* qui minimise le temps total d’attente des drones en vol, qui a permis d’obtenir les meilleurs résultats sur les cas testés. Le détail de chaque algorithme peut être trouvé dans le manuscrit de thèse d’Igor Dias Da Silva (Dias Da Silva, 2023).

Nous présentons donc un algorithme glouton qui attribue les tâches afin de minimiser le temps total d'attente des drones en vol stationnaire tout en évitant les conflits entre les tâches des différents drones au cours du temps. Plus précisément, l'algorithme se déroule comme suit :

1. Nous ordonnons les tâches dans l'ordre croissant du temps d'attente, c'est-à-dire la durée pendant laquelle les drones doivent attendre avant de pouvoir exécuter la tâche (y compris le temps de vol pour atteindre $p_k$).

Si la tâche *k* ne présente aucun conflit, alors le temps d'attente correspond au temps de vol (ToF), c'est-à-dire le temps nécessaire au drone $u_k$ pour atteindre $p_k$ depuis sa position précédente.

Cependant, si la tâche *k* entre en conflit avec une tâche $k^*$ actuellement en cours d'exécution, son temps d'attente est $max(ToF, f_{k^*})$, où $f_{k^*}$ équivaut à la durée restante avant la fin de $k^*$. Dans certains cas, lorsque $k^*$ utilise le même drone que *k*, le temps d'attente est $f_{k^*} + ToF$, car le drone $u_k$ ne pourra bouger que lorsque $k^*$ sera terminée.

2. Une fois les tâches ordonnées, si une tâche ne présente aucun conflit, nous l'attribuons immédiatement. Cela modifie le temps d'attente des tâches restantes, qui doivent être réordonnées. Si une tâche *k* n'est pas sans conflit et que $u_k$ n'exécute aucune tâche, alors $u_k$ se déplace vers $p_k$ à l'avance afin de pouvoir exécuter *k* dès qu'il devient sans conflit.

Une illustration de l’algorithme minimisant le temps d’attente est présentée dans la figure 4.4 pour deux de nos algorithmes. Le programme linéaire a calculé 12 tâches attribuées à 4 drones pour couvrir 40 capteurs. Les lignes représentent le temps pendant lequel un drone vole, et les rectangles représentent la période d’exécution des tâches lorsque les drones envoient des signaux RF pour recharger les batteries des capteurs. Tous les drones commencent au même endroit correspondant à une station de base située à la position (0, 0). Les tâches sont ordonnées suivant le point 1 ci-dessus. La tâche 4 a le plus court temps d'attente (au début, le temps d'attente est simplement le temps de vol), donc c'est la première à être attribuée. Maintenant, nous devons réordonner les
tâches restantes car leur temps d'attente peut avoir changé s'il y a un conflit avec la tâche 4. Par exemple, le temps d'attente pour la tâche 7 n'est plus son temps de vol, mais $f_4$, le temps restant pour terminer la tâche 4. Les tâches 0 et 11 ont à nouveau le même temps d'attente car elles sont toutes deux sans conflit et ont le même temps de vol. Une fois que la tâche 0 est attribuée, nous réordonnons les tâches et, comme le temps d'attente pour la tâche 11 reste le même et le plus petit, elle est alors attribuée au drone 3. Les tâches sont réordonnées une fois de plus, et la tâche 8 est celle avec le plus petit temps d'attente car elle doit seulement attendre que la tâche 0 se termine. La tâche 2 doit également attendre que la tâche 0 se termine, mais comme elles utilisent le même drone, il ne peut voyager qu'après la fin de la tâche 0, donc son temps d'attente est plus long que celui pour la tâche 8. L'exécution de l'algorithme se poursuit consécutivement, jusqu'à ce que toutes les tâches soient placées, comme illustré dans la figure 4.4(a).

La figure 4.4(b) présente le résultat de l'algorithme *Time-of-Flight (ToF)* sur le même scénario que la figure 4.4(a). Cette approche gloutonne est similaire à l'algorithme *Wait-Time*, sauf que les tâches sont ordonnées uniquement selon leur temps de vol pour rejoindre leur position $p_k$, dans un ordre croissant. Ensuite, nous attribuons la première tâche qui n'a aucun conflit avec les tâches en cours : le drone quitte immédiatement sa position actuelle et commence à exécuter la tâche dès qu'il atteint la position suivante. En cas de conflit, nous cherchons la prochaine tâche avec le temps de vol le plus court et répétons le processus. Si toutes les tâches pour un drone donné sont en conflit, nous choisissons la tâche la plus proche et programmons le déplacement à l'avance, de sorte que, une fois cette tâche sans conflit, le drone puisse commencer immédiatement à l'exécuter.

On peut observer que le *Wait-Time* donne une meilleure solution, car la tâche 7 a une priorité plus élevée que la tâche 8 avec le temps d'attente, et peut donc être programmée avant. Par conséquent, comme les tâches 3 et 8 entrent en conflit, la programmation de la tâche 8 basée sur le ToF doit être retardée, ce qui donne une solution plus longue pour la trajectoire du drone 2.

### 4.3.2.2 Une solution proche de l'optimal

Afin de valider notre approche en deux étapes pour le calcul des trajectoires des drones, nous avons résolu 2800 scénarios en faisant varier tous les paramètres. La figure 4.5 compare les résultats obtenus par les différents algorithmes gloutons ainsi que les méthodes suivantes :

- **TSP** : Étant donné l'ensemble des positions à visiter pour chaque drone fourni par le MILP, nous calculons la solution TSP optimale par force brute. Cette solution nous donne une borne inférieure pour le temps global minimum nécessaire pour recharger les capteurs. Cependant, cette solution n'est pas sans conflit, ce qui signifie que les trajectoires calculées peuvent permettre à plusieurs chargeurs de charger un capteur simultanément, limitant ainsi l'efficacité de la recharge.

- **Optimal** : Nous considérons toutes les permutations possibles de tâches et, pour chaque permutation, nous attribuons les tâches dans l'ordre. Ensuite, nous sélectionnons la permutation qui donne le meilleur résultat. Pour chaque tâche *k* dans une permutation donnée, *k* est attribuée pour démarrer dès que possible, comme dans l'algorithme *Wait-Time*. Si la tâche *k* entre en conflit avec une tâche en cours, le drone retarde son départ de manière à arriver à $p_k$ dès que *k* est sans conflit. Si le drone $u_k$ est en train d'exécuter une tâche, nous attendons que $u_k$ soit libre pour attribuer *k*. Finalement, nous sélectionnons l'ordonnancement avec le temps de recharge minimum. Lorsqu'une tâche est attribuée, nous ne réordonnons pas les tâches restantes, comme dans l'algorithme du temps d'attente, car à la fin toutes les séquences possibles sont vérifiées.
<figure><img src="image_34.png" /><figcaption>(a) Temps de recharge : 870 scenarios avec moins de 10 tâches et $5 \le N \le 15$.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(b) Temps de recharge pour les 2800 scenarios testés. L'optimal ne peut pas être présenté.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(a) Temps de résolution amélioré du nouveau MILP (appelé SMILP).</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>(b) Temps de recharge pour les 2800 scenarios testés avec le nouveau MILP appelé DATA (l'ancien est appelé DOTA).</figcaption></figure>

<caption>Figure 4.6 – Résultats des améliorations de l’approche.</caption>

L'algorithme *Wait-Time* surpasse toutes les autres approches gloutonnes naïves (figure 4.5(b)). L'exemple précédent (figure 4.4) est confirmé ici sur les 2800 scénarios testés pour différents nombres de drones, de capteurs et de positions. L'algorithme Optimal se résout uniquement sur 870 instances avec moins de 10 tâches correspondant à 3628800 permutations possibles (figure 4.5(a)), ce qui peut prendre déjà 28 minutes de temps de résolution. L'algorithme *Wait-Time* met en moyenne seulement 3,28% de plus pour charger les capteurs que la planification optimale. L'algorithme ToF prend en moyenne 7,87 % de plus, tandis que les approches *Longest-Task-First* et *Shortest-Task-First* prennent respectivement 4,80 % et 5,39 % de plus. Par ailleurs, tous les algorithmes peuvent atteindre la solution optimale dans certains cas : *Wait-Time* l'atteint dans 63,9 % des cas, *Time-of-Flight* dans 59,54 % des cas, tandis que les approches *Longest-Task-First* et *Shortest-Task-First* l'atteignent dans 51,14 % et 47,01 % des cas. Ainsi, l'algorithme *Wait-Time* offre les meilleures performances.

Dans l'ensemble, augmenter le nombre de drones permet de recharger les capteurs plus rapidement, mais cela augmente également le nombre de conflits entre les tâches car nous avons plus de drones chargeant les mêmes capteurs. Réduire le nombre de conflits entre les tâches est important pour permettre l'utilisation simultanée de plusieurs drones et donc profiter encore plus des avantages d'une flotte de drones. Avec Igor Dias Da Silva, nous avons récemment cherché à améliorer le processus. Nous avons ainsi modifié le MILP en enlevant les drones de manière à s'affranchir de l'allocation des positions aux drones dans la première étape. Ce nouveau programme linéaire calcule donc uniquement l'ensemble des positions nécessaires à la recharge demandée des batteries
de tous les capteurs, tout en minimisant la somme des temps de vols stationnaires associés à ces
positions, ce qui le rend beaucoup plus rapide à résoudre (figure 4.6(a)). L'allocation des positions
à chacun des drones est ainsi reportée dans la deuxième étape avec le calcul des trajectoires, ce
qui permet d'allouer plus librement les positions pour éviter les conflits. Nous voyons également
dans la figure 4.6(b) que l'algorithme *Wait-Time* donne de meilleurs résultats à partir des résultats
de ce nouveau modèle linéaire. Néanmoins, ce n'est pas le cas de tous les algorithmes développés
car la répartition des tâches aux drones peut être fortement déséquilibrée. Ces améliorations sont
présentées dans le manuscrit de thèse (Dias Da Silva, 2023).
<figure><img src="image_38.png" /></figure>
# Réseaux Longue Portée LoRa
(LoRaWAN)
<figure><img src="image_39.png" /></figure>
## CHAPITRE 5

# Capacité des réseaux LoRaWAN

<table><tr><td>5.1</td><td>Principes de base des réseaux LoRa</td><td>62</td></tr><tr><td>5.2</td><td>Enjeux scientifiques</td><td>64</td></tr><tr><td>5.3</td><td>Capacité d'une cellule LoRaWAN</td><td>65</td></tr><tr><td>5.3.1</td><td>Modèle de propagation</td><td>65</td></tr><tr><td>5.3.2</td><td>Hypothèse d'un trafic saturé</td><td>66</td></tr><tr><td>5.3.3</td><td>Indicateur de performance de la capacité</td><td>67</td></tr><tr><td>5.3.3.1</td><td>Évènements indépendants</td><td>67</td></tr><tr><td>5.3.3.2</td><td>Évènements dépendants</td><td>68</td></tr><tr><td>5.3.4</td><td>Améliorations pour une meilleure mesure de la capacité</td><td>69</td></tr></table>
<figure><img src="image_40.png" /></figure>
Cette seconde partie de mon manuscrit présente mes travaux sur les réseaux longue portée LoRaWAN qui font partie de la nouvelle génération des réseaux basse consommation LPWAN (Low Power Wide Area Networks). Ces travaux ont principalement été réalisés en collaboration avec les membres de l'équipe Drakkar du Laboratoire d'Informatique de Grenoble (LIG) avec lesquels j'ai pu échanger sur le sujet depuis notre rencontre à la conférence PIMRC en 2018 où je présentais un poster sur mon travail de recharge énergétique à l'aide de drones (chapitre 4), et où nous avons assisté à des présentations concernant ce nouveau type de réseaux. Depuis ce jour, nous avons collaboré sur des études permettant d'évaluer au mieux et d'optimiser la capacité des réseaux à longue portée et à faible débit basés sur LoRa (Long Range).

La croissance de l'Internet des objets (Internet of Things, IoT) a ouvert de nouveaux défis ces dernières années dans le développement de réseaux efficaces, afin d'assurer la fiabilité de communications tout en minimisant la consommation d'énergie, avec le support d'un nombre toujours croissant d'objets connectés. Récemment, les réseaux étendus à faible consommation d'énergie, ou LPWAN (Low Power Wide Area Networks), ont suscité beaucoup d'attention et ont connu une croissance significative. Ces radios sont bon marché et capables d'envoyer et de recevoir de courts messages sur de très longues distances, jusqu'à plusieurs kilomètres, avec une très faible consommation d'énergie, assurant une autonomie des capteurs de plus de 10 ans avec une portée analogue aux réseaux cellulaires (Georgiou & Raza, 2017). La technologie LoRaWAN s'est récemment imposée sur le marché des LPWAN. Elle utilise une couche physique LoRa basée sur la modulation CSS (Chirp Spread Spectrum), ainsi qu'une méthode d'accès simple basée sur Aloha (Kleinrock & Tobagi, 1975). Les réseaux LoRa se présentent comme une solution prometteuse pour l'IoT, dans laquelle plusieurs stations de base sont déployées sur une grande zone pour fournir une couverture et une connectivité aux capteurs (de Carvalho Silva, Rodrigues, Alberti, Solic, & Aquino, 2017). Les nœuds finaux communiquent directement, en un seul saut, vers une ou plusieurs passerelles. L'intérêt croissant pour ce type d'architecture soulève plusieurs défis. En effet, les performances d'un réseau LoRaWAN en termes de couverture, de robustesse et de latence dépendent du nombre de passerelles déployées et du choix des paramètres utilisés pour les transmissions radio (largeur de bande, facteur d'étalement, taux de codage, puissance de transmission).

Cette partie du manuscrit décrit ma démarche qui est celle d'apporter mes compétences en modélisation mathématique et optimisation du fonctionnement de ces réseaux, en terme de nombre de nœuds supportés par le réseau au travers d'une ou plusieurs passerelles LoRa, ou en terme de performances au niveau des nœuds du réseau. Diverses directions existent dans la littérature, dont les buts sont différents mais complémentaires à mes yeux. Tout d'abord des études théoriques visent à développer des modèles analytiques ou d'optimisation. C'est là le cœur de mon travail. Ces études permettent ensuite d'obtenir des bases solides pour la validation et la comparaison de méthodes par simulation. Enfin, l'étape finale d'une étude complète est le développement de protocoles validés par expérimentations, qui suivent généralement les simulations. La complémentation affichée de mes thématiques de recherche, avec celles de Martin Heusse, Andrzej Duda, et Franck Rousseau de l'équipe Drakkar me permet de développer des modèles correspondant au mieux au fonctionnement du réseau en pratique. Ce chapitre, comme pour la première partie de ce manuscrit, commence par décrire le fonctionnement d'un réseau LoRaWAN et les enjeux scientifiques qui en découlent, qui servent de base aux travaux réalisés que je présente dans la suite du chapitre 5, ainsi que dans les chapitres 6 et 7. À la suite de cette introduction, je vais commencer par présenter le modèle analytique que nous avons développés pour estimer au mieux la capacité
d'une cellule LoRa (Heusse et al., 2020, 2023). Des orientations pour améliorer la capacité en optimisant le code correcteur inter-trame d'erreur et en répétant les messages envoyés à la passerelle viennent compléter ce chapitre (Heusse et al., 2022a, 2022b; Heusse & Caillouet, 2023). Le moindre de capacité nous permet ensuite d'optimiser l'allocation des facteurs d'étalement (Spreading Factors (SF)), et nous sert d'indicateur de performances pour évaluer les différentes politiques d'allocation que je présente dans le chapitre 6. Enfin, le chapitre 7 est dédié à ma collaboration avec Dimitrios Zorbas, Khaled Abdelfadeel Hassan, et Dirk Pesch sur l'ordonnancement des communications, qui se place au cœur de la démarche décrite précédemment mêlant étude théorique, développement d'algorithmes validés par simulation et expérimentation (Zorbas et al., 2021).

## 5.1 Principes de base des réseaux LoRa

LoRa® (*Long Range*) est une technologie LPWAN (*Low Power Wide Area Networks*) récente qui prend en charge les communications à faible puissance et à longue portée orientées vers l'Internet des objets (IoT) (*LoRaTM Alliance*, 2015). Elle utilise une couche radio spécifique basée sur la modulation CHIRP (*Compressed High Intensity Radar Pulse*) Spread Spectrum (CSS) pour une communication robuste dans la bande ISM sub-GHz qui donne accès à un certain nombre de débits de données offrant différents niveaux de robustesse de transmission. La couche physique du réseau LoRa présente les caractéristiques suivantes (*Semtech*, 2017) :

**Largeur de bande (BW)** La largeur de bande correspond à la plage de balayage de la fréquence CSS, entre 7,8 kHz et 500 kHz. Elle est réglée typiquement sur 125 kHz ou 250 kHz en Europe. Les largeurs de bande plus importantes permettent des débits de données plus élevés, mais réduisent la sensibilité.

**Facteur d'étalement (SF)** Le facteur d'étalement caractérise le nombre de bits transportés dans un CHIRP : le bloc de $x$ bits à SF$x$ correspond à l'un des $2^x$ décalages de fréquence possibles, sachant que la durée du CHIRP est elle-même de $2^x$ échantillons temporels (à la fréquence d'échantillonnage BW). Le SF varie entre 6 (7 en pratique) et 12. SF12 correspond à la meilleure sensibilité et à la meilleure portée, au prix du débit de données le plus faible et d'une consommation énergétique plus importante. En abaissant le SF d'une unité, on double à peu près le débit de transmission, et on réduit d'environ 3dB la sensibilité et de moitié le temps de transmission et la consommation d'énergie.

**Taux de codage (CR)** Le taux de codage détermine le taux de correction d'erreurs (FEC), qui améliore le taux d'erreurs dans les paquets en présence de bruit et d'interférences. Un taux de codage plus faible offre une plus grande robustesse, mais augmente le temps de transmission et la consommation d'énergie. Les valeurs possibles sont les suivantes : 4/5, 4/6, 4/7 et 4/8.

**Puissance de transmission (TP)** La puissance de transmission en LoRaWAN peut prendre les valeurs suivantes pour la bande EU 863-870 MHz : 2, 5, 8, 11 et 14 dBm. Une puissance plus importante conduit à une qualité de réception plus élevée, mais augmente également la consommation énergétique.
<table><caption>Table 5.1 – Paramètres LoRa pour une BW de 125 kHz.</caption><thead><tr><th>SF<sub>j</sub></th><th>Limite SNR (q<sub>j</sub>)</th><th>Airtime (τ<sub>j</sub>)</th><th>Bit rate DR<sub>j</sub></th><th>s<sub>max</sub></th></tr></thead><tbody><tr><td>7</td><td>-7.5 dB</td><td>102.7 ms</td><td>DR5 : 5469 b/s</td><td>230 B</td></tr><tr><td>8</td><td>-10 dB</td><td>184.8 ms</td><td>DR4 : 3125 b/s</td><td>230 B</td></tr><tr><td>9</td><td>-12.5 dB</td><td>328.7 ms</td><td>DR3 : 1758 b/s</td><td>123 B</td></tr><tr><td>10</td><td>-15 dB</td><td>616.5 ms</td><td>DR2 : 977 b/s</td><td>59 B</td></tr><tr><td>11</td><td>-17.5 dB</td><td>1315 ms</td><td>DR1 : 537 b/s</td><td>59 B</td></tr><tr><td>12</td><td>-20 dB</td><td>2466 ms</td><td>DR0 : 293 b/s</td><td>59 B</td></tr></tbody></table>

<figure><img src="image_41.png" /><figcaption>Figure 5.1 – Architecture d'un réseau LoRa.</figcaption></figure>

Le facteur d'étalement choisi permet un compromis entre le débit de données et la portée : une petite valeur de SF (par exemple, 7) se traduit par un débit de données plus élevé, des transmissions courtes et une faible portée, tandis que SF12 donne la meilleure sensibilité et la plus grande portée, au prix de longues durées de transmission et d'une importante consommation d'énergie. Pour chaque SF(12-j), on associe un débit de données DRj, la limite du rapport signal sur bruit (Signal-to-Noise Ratio) (SNR) pour la réception qj, la taille maximum des données transportées smax. τj correspond ainsi au temps de transmission d'un paquet de taille maximum au débit DRj. Dans nos travaux, nous considérons la modulation LoRa CSS classique avec une largeur de bande de 125 kHz et des valeurs de SF de 12, 11,... 7, ce qui correspond aux débits DRj, avec j = 0, 1, ... 5, and SF = 12 - j présentés dans le tableau 5.1.

LoRaWAN® (Sornin, Editor, 2017) spécifie un protocole de communication au niveau de la couche MAC, au dessus de la couche physique. Nous nous concentrons sur les communications montantes entre des nœuds de classe A et les passerelles LoRa. Les nœuds de classe A accèdent au canal radio en utilisant exclusivement le protocole non synchronisé Aloha pur (Kleinrock & Tobagi, 1975) : un appareil se réveille et peut envoyer des paquets à tout moment sur un canal radio choisi, à condition que son cycle de fonctionnement (duty cycle) soit conforme à la règlementation (typiquement 1 % dans chacune des bandes 868 MHz selon les réglementations de l'UE). Une ou plusieurs passerelles peuvent recevoir le paquet et le transmettre aux serveurs réseau et application (figure 5.1).
Deux conditions décident de la réception d'une trame : d'une part, il faut que la puissance reçue soit suffisante pour dominer le bruit ambiant (rapport signal sur bruit) et d'autre part, en cas de collision, il faut avoir assez de marge de puissance vis à vis des trames concurrentes.

Les performances en termes de taux de livraison de paquets (PDR) et de passage à l'échelle dépendent fortement du nombre de collisions survenant lorsqu'au moins deux nœuds transmettent des paquets qui se chevauchent dans le temps. Les transmissions utilisant différents facteurs d'étalement sont quasi-orthogonales : en cas de collision, les deux trames sont correctement reçues si l'une n'est pas plus forte que l'autre de plusieurs ordres de grandeur (Goursaud & Gorce, 2015; Croce, Gucciardo, Mangione, Santaromita, & Tinnirello, 2018), comme nous le verrons plus tard. Les transmissions se produisant avec le même SF peuvent souffrir d'une collision si elles se produisent simultanément, sauf si un signal est nettement plus fort que l'autre. Dans ce cas, la passerelle peut toujours décoder la transmission la plus forte. Ce phénomène s'appelle l'effet de capture (Bankov, Khorov, & Lyakhov, 2017).

Tous ces paramètres doivent donc être considérés afin de proposer un modèle d'évaluation de la capacité se rapprochant au mieux de la réalité.

## 5.2 Enjeux scientifiques

Il est important pour les opérateurs de parvenir à une utilisation optimale du réseau, car il existe un compromis entre la portée de la couverture d'une cellule LoRaWAN et la charge générée par les nœuds finaux : il est moins coûteux de déployer les passerelles loin les unes des autres, mais les nœuds doivent alors utiliser une modulation plus robuste, ce qui entraîne des temps de transmission plus longs, qui à leur tour augmentent la charge du canal et les collisions, réduisant ainsi le taux de livraison des paquets (Packet Delivery Ratio PDR). Comme dans la plupart des systèmes cellulaires, il doit y avoir plus de passerelles dans les zones à forte densité de nœuds, alors qu'une cellule sous-chargée est un gaspillage de ressources (sauf pour assurer la couverture dans les zones à faible densité). Nous avons donc besoin d'un modèle précis de la capacité pour obtenir le meilleur compromis et optimiser l'utilisation des réseaux LoRaWAN.

Lorsque sa distance à la passerelle augmente, un nœud doit changer de SF pour maintenir le niveau souhaité de PDR : plus loin de la passerelle, les nœuds doivent utiliser des SF plus importants pour augmenter la probabilité de réception des trames. Les limites de SF autour de la passerelle sont donc définies sous la forme d'anneaux concentriques dans lesquels les nœuds partagent la même valeur de SF. Dans la pratique, un mécanisme adaptatif, nommé *Adaptive Data Rate* (ADR), est utilisé par le serveur du réseau LoRaWAN afin d'allouer aux nœuds leur débit de données, et donc leur SF, à utiliser en fonction du rapport signal/bruit (SNR), de la puissance reçue, du PDR mesurés au niveau de la passerelle... Des SF plus importants permettent des transmissions plus robustes en utilisant un débit de données plus faible avec une puissance de transmission similaire. Cependant, les transmissions avec des SF plus importants prennent plus de temps, ce qui augmente la congestion et la probabilité de collision.

Le facteur d'étalement est donc un paramètre clé dans l'optimisation de l'utilisation des réseaux LoRaWAN. Dans mes travaux, je me suis donc concentrée sur l'optimisation du facteur d'étalement des nœuds d'un réseau LoRaWAN de manière à maximiser le PDR des nœuds ou la capacité des cellules. Pour cela, nous avons besoin de bien modéliser la capacité. Nous avons donc cherché à répondre aux questions suivantes :
— Quelles hypothèses réalistes considérer afin de bien modéliser la capacité d'un réseau LoRaWAN ?

— Quels sont les leviers disponibles pour améliorer les performances de ces réseaux ?

— Comment améliorer le mécanisme d'allocation des débits de données ADR à partir de nos observations ?

— Pouvons-nous considérer un protocole synchronisé d'accès au canal dans un réseau LoRaWAN et comment l'optimiser ?

La section suivante présente mes travaux permettant de répondre aux deux premières questions. Le chapitre suivant se concentrera sur les modèles d'optimisation pour une meilleure allocation des facteurs d'étalement dans un réseau LoRaWAN composé d'une ou plusieurs passerelles. Enfin, le chapitre 7 présentera mon apport dans l'étude pour le déploiement d'un réseau LoRaWAN dans lequel l'envoi des paquets est synchronisé.

## 5.3 Capacité d'une cellule LoRaWAN

Nous considérons une cellule LoRa avec un mécanisme classique qui configure les SF en fonction des conditions de transmission des nœuds, ce qui correspond à la vue en anneaux concentriques autour de la passerelle comme présentée dans la figure 5.2. $l_j$ représente la distance jusqu'au nœud le plus éloigné qui utilise SF{12 – j} et donc le débit de données DRj.

La capacité d'une cellule correspond au nombre de nœuds qu'une seule passerelle peut gérer avant que les pertes dues aux collisions ou à l'affaiblissement n'atteignent des niveaux inacceptables. Ces deux facteurs sont antagonistes, car des transmissions plus robustes occupent le canal plus longtemps et augmentent ainsi la probabilité de collision. De nombreux articles abordent cette question (Georgiou & Raza, 2017; Varsier & Schwoerer, 2017; Bor, Roedig, Voigt, & Alonso, 2016; A. Yousuf & Ghaderi, 2018; Mikhaylov, Petäjäjärvi, & Hänninen, 2016; Waret, Kaneko, Guitton, & El Rachkidy, 2018; Mahmood et al., 2018) afin de déterminer analytiquement la capacité d'une cellule LoRa. Différents modèles ont été proposés et tentent d'estimer les effets des collisions entre les transmissions se produisant dans le même SF et le même canal, ayant un fort impact négatif pour les performances du réseau.

Dans la suite sont présentés les choix et hypothèses que nous avons fait pour notre modèle de capacité.

### 5.3.1 Modèle de propagation

Nous considérons un modèle de propagation avec 2 composantes : une atténuation moyenne fonction de la distance à couvrir et un gain aléatoire qui varie d'une transmission à l'autre. Nous utilisons le modèle Okumura-Hata pour l'affaiblissement sur le trajet (également utilisé dans d'autres travaux (Bankov et al., 2017; Magrin, Centenaro, & Vangelista, 2017; Demetri et al., 2019)), plus précisément la variante de l'environnement suburbain avec une hauteur d'antenne de 15m. Ce modèle empirique est légèrement moins favorable mais plus réaliste que l'adoption d'un exposant arbitraire d'affaiblissement sur le trajet comme dans la plupart des travaux cités ci-dessus. Nous considérons un gain d'antenne de la passerelle de 6 dB, qui compense un facteur de bruit du récepteur de 6 dB. Nous négligeons l'effet d'ombrage (shadowing), car son effet net serait faible dans notre cas : il modifierait le gain du canal de chaque nœud sans changer les caractéristiques générales du réseau (Mahmood et al., 2018). Enfin, nous considérons un canal multi-trajet
<figure><img src="image_42.png" /><figcaption>Figure 5.2 – Anneaux des SF autour de la passerelle.</figcaption></figure>

de Rayleigh : une variable aléatoire multiplicative avec une distribution exponentielle de moyenne unitaire affecte la puissance du signal reçu.

Nous supposons que tous les nœuds émettent à une puissance $P_{tx} = 14$ dBm. La puissance du signal reçu à la passerelle dépend de la distance et de l'affaiblissement de Rayleigh. La puissance de transmission est atténuée en fonction de la distance entre l'émetteur et la passerelle, ce qui donne la puissance moyenne suivante :

$$ \overline{P_{rx}} = P_{tx} * g(d_i) \qquad (5.1) $$

où $g(d_i)$ est la fonction d'affaiblissement basée sur le modèle Okumura-Hata.

### 5.3.2 Hypothèse d'un trafic saturé

La superposition du trafic provenant d'un grand nombre d'appareils tend vers un processus de Poisson homogène et nous désignons son intensité par $\lambda_t$ qui dépend du modèle de génération de données des applications IoT. De nombreux articles portant sur la capacité des réseaux LoRaWAN supposent que tous les nœuds utilisent complètement leur *duty cycle* autorisé, indépendamment de leur SF (Georgiou & Raza, 2017; Georgiou, Psomas, & Krikidis, 2020; Hoeller et al., 2018; Mahmood et al., 2018; Li, Zozor, Brossier, Varsier, & Lampin, 2017). Cette hypothèse implique d'envoyer beaucoup plus de paquets lorsqu'un nœud est plus proche de la passerelle, ce qui n'est pas réaliste : supposons qu'une application IoT doive envoyer un paquet toutes les heures et que le nœud se trouve à une distance correspondant au SF8. Si les conditions de transmission changent et qu'il peut passer à SF7, il ne commencera pas à envoyer des paquets toutes les demi-heures simplement parce qu'il a la possibilité de le faire. Dans cette hypothèse, si la mesure de la capacité est le débit global, les modèles donnent des résultats optimistes (c'est-à-dire un débit élevé) parce que peu de nœuds sont capables de remplir tous les sous-canaux quasi-orthogonaux disponibles (Li et al., 2017). Au contraire, si la métrique utilisée pour exprimer la capacité est le nombre de nœuds comme dans les autres travaux cités, les modèles donnent une capacité très faible parce que tous les nœuds saturent leur *duty cycle* et qu'il est donc peu avantageux de déplacer un nœud vers un SF plus petit, puisqu'il transmet immédiatement beaucoup plus de trafic et crée donc des niveaux de collisions similaires. Je pense que dans un réseau LoRaWAN, le trafic est fonction de l'application et ne devrait pas dépendre de la position du nœud dans le réseau ou de la qualité du canal.
Ainsi, nous proposons donc un modèle de trafic dans lequel tous les nœuds génèrent des paquets avec les mêmes temps d'inter-transmission correspondant à la limitation du *duty cycle* au SF le plus élevé, quelle que soit la distance par rapport à la passerelle. Comme les nœuds fonctionnent avec un *duty cycle* donné et se réveillent pour envoyer des données à intervalles constants, la superposition du trafic provenant d'un grand nombre de nœuds tend vers un processus de Poisson homogène et nous désignons son intensité par $\lambda_t$ qui dépend du modèle de génération de données des applications IoT. Le cas limite est celui où $\lambda_t$ est l'intensité du trafic des nœuds fonctionnant à DR0 et SF12 avec *duty cycle* maximal et envoyant des paquets de 59B, la taille maximale des données transportées à ce taux. Notre analyse est également valable pour une intensité de trafic plus faible provenant d'applications moins exigeantes.

Nous supposons que les nœuds sont dispersés de manière homogène avec une densité spatiale $\rho$. Le nombre de nœuds utilisant DRj est fonction des rayons définissant l'anneau entre $l_{j+1}$ et $l_j$ autour de la passerelle (voir figure 5.2). La limitation du *duty cycle* s'applique à chaque bande de fréquence : les nœuds LoRa doivent limiter leur occupation de chaque bande de fréquence à 1% du temps avec 3 à 5 canaux de fréquence dans chaque bande. En Europe, par exemple, il y a 3 canaux dans la bande h1.4 et 5 dans la bande h1.3. Si nous supposons qu'il y a 3 canaux, les appareils peuvent utiliser chacun d'entre eux à 0,33% de *duty cycle*. Le temps de transmission des paquets de taille maximale à DR0 correspond à $\tau_0 = 2,466$s, ils peuvent donc être envoyés toutes les 739,8s sur le même canal (ou toutes les 246,6s sur des canaux différents) pour atteindre un *duty cycle* de 0,33% ($\frac{1}{300}$) par canal. L'intensité est donc :

$$ \lambda_t = \frac{1}{739.8 \text{ s}} \qquad (5.2) $$

Pour SF = 12 - j, et $n_j$ le nombre de nœuds concurrents dans l'anneau j, l'intensité du trafic offert est :

$$ v_j = n_j \tau_j \lambda_t \qquad (5.3) $$

en Erlang, où $\tau_j$ est le temps de transmission au débit DRj, et

$$ n_j = \pi \rho (l_j^2 - l_{j+1}^2) \qquad (5.4) $$

est le nombre de nœuds dans l'anneau de SF 12 - j.

### 5.3.3 Indicateur de performance de la capacité

Rappelons que dans une cellule LoRaWAN, une trame n'est pas correctement reçue pour deux raisons : i) le SNR est inférieur au seuil de réception de la passerelle et/ou ii) une collision se produit et le signal n'est pas assez fort par rapport à l'interférence.

#### 5.3.3.1 Évènements indépendants

Notre métrique de performances est donc le taux de livraison des paquets (PDR) qui est généralement vu comme le produit de $H$, la probabilité qu'un message soit reçu avec une puissance suffisante par rapport à la sensibilité de la passerelle, avec $Q$, la probabilité que la trame ne soit pas perdue du fait d'une collision avec une autre trame, supposant ainsi ces deux probabilités indépendantes.
Comme nous considérons un canal multitrajet de Rayleigh dont la distribution des puissances suit une loi exponentielle de moyenne 1,

$$H = e^{(-\frac{Nq_j}{P_{rx}})} \qquad (5.5)$$

où N est la puissance du bruit dans la bande de 125 kHz considérée (-123 dBm), $q_j$ est la sensibilité de la passerelle pour le SF 12 - j, et $P_{rx}$ est la puissance moyenne reçue d'après l'équation 5.1.

Pour le calcul de Q nous distinguons 3 cas pour une trame donnée :

1. elle ne subit la concurrence d'aucune autre trame, elle est donc reçue avec la probabilité $HQ_1$;

2. une seule autre trame est présente et la trame considérée domine cette interférence (probabilité $Q_2$);

3. plus d'une autre trame est présente et la trame est perdue, la probabilité de prévaloir étant très faible.

$Q_1$ correspond à la probabilité bien connue de succès sur un canal Aloha avec traffic de Poisson :

$$Q_1 = e^{(-2v_j)} \qquad (5.6)$$

Aucune autre trame ne doit arriver pendant une durée $\tau_j$ de part et d'autre du début de la réception de la trame considérée.

$Q_2$ est le produit des probabilités d'avoir une unique autre trame en présence, soit $2v_j \exp(-2v_j)$, avec celle qu'une trame donnée domine une autre trame de 6 dB quand leurs puissances suivent une distribution exponentielle. Cette dernière probabilité est $\frac{1}{\gamma+1}$ pour un facteur $\gamma$ (car 6 dB de plus correspond au fait d'être 4 fois plus puissant, soit $\gamma = 4$), et donc $Q_2 = \frac{2}{\gamma+1} v_j \exp(-2v_j) = \frac{2}{5} v_j \exp(-2v_j)$.

Nous avons donc :

$$Q = Q_1 + Q_2 = \left(1 + \frac{2}{5}v_j\right) \exp(-2v_j). \qquad (5.7)$$

Finalement, en combinant les équations 5.5 et 5.7, nous obtenons la formule du PDR dans le cas indépendant :

$$PDR_I = H \times Q \qquad (5.8)$$

### 5.3.3.2 Évènements dépendants

Dans le modèle précédent ainsi que dans tous les articles de la littérature, la probabilité de capture en cas de collision et la probabilité de réception par rapport au bruit ambiant sont supposées indépendantes. Ce n'est cependant pas le cas dans la réalité car un signal fort à la passerelle est susceptible de surpasser à la fois le bruit ambiant et les interférences des transmissions concurrentes.

Dans le cas d'une collision, la probabilité de réception d'une trame à $DR_j$ est :

$$PDR_I = Pr \left( g_r > \frac{Nq_j}{Pg(d)} \cap g_r > \gamma g_c \right) = Pr \left( g_r > \max \left( \frac{Nq_j}{Pg(d)}, \gamma g_c \right) \right), \qquad (5.9)$$

où $g_r$ et $g_c$ sont les gains du canal de Rayleigh distribués de manière exponentielle pour la trame considérée et la trame en collision respectivement, $g(d)$ est le gain moyen de l'atténuation pour
<figure><img src="image_43.png" /><figcaption>Figure 5.3 – Utilisation du canal en fonction de la charge pour les différents modèles de PDR, comparé avec des résultats de simulation (×,o), dans une cellule de 7.5 km.</figcaption></figure>

les deux trames (en supposant que les deux nœuds sont à distance *d* de la passerelle), et $\gamma$ est le facteur des puissance pour la capture ($\gamma = 4$ dans la section précédente).

Soit $g_t = \frac{Nq_j}{Pg(d)}$ le seuil de réception réussie contre le bruit ambiant, par l'intégrale de la fonction de densité de probabilité sur l'intervalle de réception réussie, le PDR devient :

$$PDR_1 = \int_{0}^{+\infty} e^{-y} \int_{\max(g_t, \gamma y)}^{+\infty} e^{-x} dxdy = \frac{e^{-g_t}}{\gamma + 1} \left(1 + \gamma \left(1 - e^{-\frac{g_t}{\gamma}}\right)\right). \quad (5.10)$$

Finalement, le PDR dans le cas de dépendance des probabilités est :

$$PDR_D = HQ_1 + 2v_j \exp(-2v_j) PDR_1. \quad (5.11)$$

Ces modèles ont été validés par simulation et comparés avec le modèle classique d'Aloha (Kleinrock & Tobagi, 1975), et avec le modèle de (Georgiou & Raza, 2017) (avec et sans correction de la probabilité *Q* qui considérait plutôt un modèle Aloha synchronisé). L'utilisation du canal $U = PDR \times v_0$ présenté dans la figure 5.3 montre l'adéquation de nos modèles et l'apport signification de l'effet de capture comparé à des réseaux Aloha classiques.

### 5.3.4 Améliorations pour une meilleure mesure de la capacité

Dans ce premier modèle du PDR décrit dans (Heusse et al., 2020), nous avons supposé que les trames étaient perdues au-delà de 2 collisions. Nous avons ensuite étendu la formule du PDR dans le cas général de *n* collisions, ainsi qu'en considérant de la diversité d'antenne dans (Heusse et al., 2022a, 2023). Dans le cas de deux collisions, il est important de distinguer les cas où les 2 autres trames intersectent la trame considérée, ou si seulement 1 intersecte la trame courante à la fois (figure 5.4). Cela complexifie nos modèles mais permet néanmoins de dériver une formule du PDR générale pour 0,1, 2, ..., *n* collisions validée par simulation.

La présence de deux antennes sur la passerelle complexifie légèrement le calcul de la probabilité de réception. En effet, les évanouissements multi-trajets sont différents sur chaque antenne et donc plusieurs cas de figure sont à considérer. La figure 5.5 montre néanmoins le gain significatif de l'ordre de 47% obtenu en considérant la diversité obtenue en ajoutant une antenne sur
<figure><img src="image_44.png" /><figcaption>Figure 5.4 – Collision avec 2 autres trames.</figcaption></figure>

<figure><img src="image_45.png" /><figcaption>Figure 5.5 – Utilisation du canal en fonction de la charge pour les différents modèles de PDR avec ou sans diversité, comparé avec des résultats de simulation ($\nabla$), dans une cellule de 7.5 km..</figcaption></figure>

la passerelle, proche de la première mais suffisamment loin pour redistribuer le gain aléatoire des évanouissements multi-trajets.

Le modèle permet de faire ressortir le fait que, si un code correcteur inter-trame d'erreur est disponible, alors un taux de codage, qui définit le niveau de redondance, de l'ordre de $\frac{1}{3}$ (qui correspond aussi au schéma de répétition utilisé par SigFox) conduit à pouvoir approcher l'utilisation maximale du canal sur une large plage de distances. Ce résultat complète les observations faites dans le cas de mécanismes de correction empiriques, pour lesquelles l'imperfection de la correction d'erreur n'était pas détachée de la structure fondamentale du problème (de Souza Sant'Ana, Hoeller, Souza, Alves, & Montejo-Sánchez, 2020).

Dans nos modèles, nous faisons tout de même deux hypothèses importantes : i) nous ne considérons pas les interférences entre les trames utilisant des SF différents, et ii) nous supposons que tous les nœuds utilisant un même SF se situent à la même distance de la passerelle. Nous avons donc produit des simulations pour évaluer l'impact de ces phénomènes et concluons, d'une part, qu'ils sont notables et, d'autre part, que l'utilisation du contrôle de puissance dans la seule zone SF7 suffit à atténuer leurs effets.
## CHAPITRE 6

# Optimisation de l'allocation des facteurs d'étalement (SF)

<table><tr><td>6.1</td><td>Application directe des modèles analytiques</td><td>74</td></tr><tr><td>6.2</td><td>Déterminer les limites des SF de manière équitable</td><td>74</td></tr><tr><td>6.2.1</td><td>Efficacité par rapport à la sensibilité</td><td>75</td></tr><tr><td>6.2.2</td><td>Précision du modèle</td><td>76</td></tr><tr><td>6.2.3</td><td>Passage à l'échelle</td><td>77</td></tr><tr><td>6.3</td><td>Allocation optimale avec effet de capture, orthogonalité imparfaite, et macro-diversité</td><td>77</td></tr><tr><td>6.3.1</td><td>Modélisation du point de vue des nœuds.</td><td>78</td></tr><tr><td>6.3.2</td><td>Programme linéaire en nombres entiers pour l'allocation optimale</td><td>79</td></tr><tr><td>6.3.3</td><td>Analyse des résultats</td><td>80</td></tr></table>
<figure><img src="image_46.png" /></figure>
Les modèles de PDR décrits dans le chapitre précédent servent de base à l’évaluation de la capacité des réseaux LoRaWAN dans une cellule homogène. Nous les avons validés par simulation afin de vérifier qu’ils représentent au mieux le fonctionnement du réseau. Cela nous permet maintenant de les utiliser dans des modèles d’optimisation efficaces. Notre objectif est maintenant d’ajuster l’allocation des facteurs d’étalement (SF) afin de maximiser la capacité du réseau. Nous regardons les optimisations suivantes : i) en terme de nombre de nœuds maximum que peut supporter le réseau, ii) en maximisant la portée d’une cellule de manière à assurer un PDR donné, iii) en maximisant le PDR pour un nombre de nœuds fixés. Les transmissions utilisant le même SF peuvent entrer en collision si elles se produisent simultanément, sauf si un signal est significativement plus fort que l’autre. Dans ce cas, appelé l’effet de capture, la passerelle peut toujours décoder la transmission la plus forte. Les SF sont supposés être quasi-orthogonaux. L’orthogonalité imparfaite des SF a été étudiée et le seuil de SINR pour les transmissions simul-tanées dans différents SF a été quantifié (Goursaud & Gorce, 2015; Croce et al., 2018). Si deux trames avec des SF différents entrent en collision, elles réussissent toutes les deux si elles ne sont pas très significativement plus fortes l’une que l’autre (de 8 à 25dB suivant les SF). Il est donc nécessaire de prendre en compte ces caractéristiques afin d’obtenir des modèles d’optimisation proches de l’utilisation en pratique. Notre but est ainsi de proposer une meilleure allocation que celles généralement proposées pour l’ADR (Adaptive Data Rate) utilisées dans LoRaWAN où les SF sont alloués en se basant principalement sur la portée de communications des nœuds.

La planification et la gestion optimales du réseau LoRaWAN ont retenu peu d'attention, et les travaux existants reposent sur des hypothèses différentes des nôtres. (Cesana, Redondi, & Ortin, 2018) alloue de manière optimale les facteurs d'étalement et estime le taux d'extraction des données pour chaque facteur d'étalement au niveau de la passerelle. Ils considèrent un modèle d'atténuation en log-distance sans canal de Rayleigh et sans effet de capture. (Zorbas, Papadopoulos, Maillé, Montavont, & Douligeris, 2018) fournit un modèle analytique pour quantifier la densité des nœuds qu'une passerelle LoRaWAN peut servir pour chaque facteur d'étalement. Cependant, leur modèle calcule une probabilité moyenne de telle sorte que seuls les facteurs d'étalement 7 et 8 sont utilisés, ce qui n'est pas réaliste dans la pratique puisque les nœuds situés loin de la passerelle ne peuvent pas utiliser ces SF et donc ne seront pas servis. Ils ont récemment étendu ce travail pour augmenter la capacité du réseau en utilisant une allocation optimale des SF (Zorbas, Maillé, O'flynn, & Douligeris, 2019). Ils utilisent la même probabilité moyenne de succès de transmission entre chaque SF pour dériver les limites des SF dans une cellule LoRaWAN. Ils limitent également leurs tests à une cellule de 500m.

Ce chapitre présente dans un premier temps l'évaluation de la capacité d'une cellule en optimisant les bornes des SF à l'aide des modèles analytiques du PDR du chapitre précédent. Nous avons ensuite proposé un programme linéaire en nombres entiers pour garantir l'équité du PDR entre tous les SF. Enfin, un modèle plus fin permet d'allouer optimalement le SF à chacun des nœuds tout en considérant l'effet de capture et l'orthogonalité imparfaite entre les différents SF dans des réseaux LoRaWAN pouvant contenir plusieurs passerelles. Ces travaux ont donné lieu à des publications dans des conférences internationales (Caillouet, Heusse, & Rousseau, 2019; Caillouet et al., 2020a, 2020b, 2021).
<figure><img src="image_47.png" /><figcaption>Figure 6.1 – Limites des SF déterminées par dichotomie pour une densité de 5 nœuds au km².</figcaption></figure>

## 6.1 Application directe des modèles analytiques

Une application directe des modèles analytiques du chapitre précédent afin de calculer la capacité d'une cellule LoRa est d'utiliser la méthode de dichotomie pour délimiter les frontières $l_j$ de chaque SF (Heusse et al., 2020). La frontière de SF7 est fixée à la distance où le $PDR_D$ (équation 5.11) correspond à une valeur cible fixée en entrée. De cette manière, l'anneau comprend le nombre maximal de nœuds qui obtiennent au moins le $PDR_D$ cible. Ensuite, nous passons à SF8 et augmentons sa frontière pour atteindre le $PDR_D$ cible, et ainsi de suite pour les autres frontières de SF. Nous comparons avec la même méthode basée cette fois sur le seuil SNR par rapport à une valeur cible de la probabilité $H$ (équation 5.5) : le SF est incrémenté à chaque fois que la valeur de $H$ passe sous la valeur cible.

Cette méthode simple permet de rapidement mettre en évidence l'avantage d'utiliser le modèle plus fin du PDR car le nombre de nœuds bénéficiant d'un PDR supérieur à 60% (notre PDR cible dans la figure 6.1(b)) est beaucoup plus important qu'en calculant le PDR avec des limites calculées en considérant le SNR. Cette observation nous amène alors à considérer un modèle d'optimisation afin de maximiser le PDR minimum atteignable en chaque limite de SF, i.e. le PDR cible optimal, dans la section suivante.

## 6.2 Déterminer les limites des SF de manière équitable

Le but ici est donc d'équilibrer le PDR dans le réseau pour assurer l'équité entre les nœuds en répartissant correctement les SF, sur la base du modèle tenant compte à la fois de l'atténuation et collisions présenté dans le chapitre précédent. Une première difficulté rencontrée est la non linéarité de la formule du $PDR_D$, car la densité des nœuds $n_j$ (Équation 5.4) et donc la charge de trafic $v_j$ (Équation 5.3) dépendent des deux distances limites $l_j$ et $l_{j+1}$ qui se retrouvent dans tous les éléments de l'équation 5.11 de $PDR_D$. Dans cette étude, nous avons donc choisi d'utiliser le modèle indépendant du PDR (Équation 5.8 de $PDR_I$) qui permet de se linéariser comme nous le verrons dans la suite.

Nous cherchons ici à adapter les bornes $l_j$, $j = 1, ..., 5$, des SFs de manière à maximiser le PDR minimum au niveau de ces bornes, et donc dans le réseau. Nous discrétisons le rayon de la cellule $[0, l_0]$ en $D$ éléments correspondant aux valeurs possibles pour les $l_j$. Le nombre d'échantillons $|D|$ est fixé en entrée du problème. Soit $x_d^j$ la variable binaire indiquant si $l_j$ est fixé à la distance $d \in D$ ou non. Le programme linéaire en nombres entiers pour allouer équitablement
<figure><img src="image_48.png" /><figcaption>Figure 6.2 – PDR des nœuds en fonction de la distance dans une cellule.</figcaption></figure>

les SF est le suivant :

$$ \max \min_{j=0,...,5} \sum_{d \in D} e^{\left(-\frac{Nq_j}{P_{tx} \times g(d)}\right)} x_d^j \times \sum_{d' < d} \left(1 + \frac{2}{5} v_j\right) e^{(-2v_j)} x_{d'}^{j+1} \quad (6.1) $$

$$ \sum_{d \in D} x_d^j = 1, \forall j = 1, ..., 5 \quad (6.2) $$

$$ x_{l_0}^0 = 1 \quad (6.3) $$

$$ x_d^j \in \{0, 1\}, \forall d \in D, j = 0, ..., 5 \quad (6.4) $$

Les contraintes (6.2) assurent qu'une seule distance est allouée à chaque borne $l_j$, et nous fixons la limite de SF12 au rayon de communication maximum $l_0$ fixé en entrée (Contrainte (6.3)). La fonction objectif (6.1) reprend la formule 5.8 du PDR du chapitre précédent afin de maximiser le PDR minimum parmi toutes les distances choisies pour les $l_j$, $j = 1, ..., 5$. La fonction objectif est ensuite linéarisée en ajoutant de nouvelles variables binaires.

### 6.2.1 Efficacité par rapport à la sensibilité

Notre modèle s'applique pour toute taille de cellule. Nous avons regardé 3 scenarios : des cellules de 2.5, 5, et 7 km. Pour chaque scénario, nous prenons les échantillons $d_i = l_0 \times \sqrt{i/|D|}$, pour $i = 1, ..., |D|$ afin de proposer des limites de même aire pour les SFs, telles que les limites pour les grands SFs loin de la passerelle seront plus rapprochées les unes des autres.

Notre optimisation permet d'équilibrer l'impact de l'atténuation et des collisions afin d'obtenir un taux de perte équivalent pour tous les nœuds, contrairement au modèle basé sur le SNR. Pour les petites et moyennes cellules où les collisions ont un fort impact, nous améliorons grandement le PDR minimum en passant de 0.21 à 63.6% pour la petite cellule, et de 8.63 à 60.73% dans la
<figure><img src="image_49.png" /><figcaption>Figure 6.3 – Temps de résolution.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>Figure 6.4 – PDR minimum dans la cellule.</figcaption></figure>

moyenne (figures 6.2(a) et 6.2(b)). Cela permet à des centaines de nœuds d'atteindre un taux de perte convenable. Dans les grandes cellules, le gain est moins important mais représente un gain de 13% pour les nœuds les plus lointains (de 42 à 55.64%) (figure 6.2(c)). Après optimisation, très peu de nœuds utilisent SF12, alors que la zone de SF7 a augmenté, en comparaison aux bornes basées sur le SNR. L'effet négatif des collisions dans la zone proche de la passerelle est ainsi contre-balancé par le gain des nœuds distants. Globalement plus de 50% des nœuds voient leur PDR augmenter par rapport à celui obtenu avec des bornes basées sur SNR.

### 6.2.2 Précision du modèle

Le nombre d'échantillons $|D|$ est un paramètre clé dans notre modèle. Augmenter cette valeur de 1 augmente notre modèle de ($|SF|(1 + |D|)$) nouvelles variables. Le temps de résolution est ainsi fortement dépendant de cette valeur comme l'on peut le voir sur la figure 6.3. Néanmoins, notre modèle nécessite uniquement un faible nombre d'échantillons pour converger vers une valeur précise de PDR en moins de 100 secondes. Sur la figure 6.4(a) nous pouvons voir que la différence du PDR minimum garanti pour tous les nœuds est inférieure à 1% entre le modèle avec 50 et celui avec 300 échantillons de distance. Ainsi nous garantissons une solution efficace obtenue rapidement.
<figure><img src="image_51.png" /><figcaption>Figure 6.5 – Évolution des limites équitables des SF en fonction de la distance à la passerelle.</figcaption></figure>

### 6.2.3 Passage à l'échelle

Plus la densité de nœuds est élevée, plus la zone devient couverte par des petits SF (figure 6.5). Cela révèle que le SF12 n'est pas très utile lorsque la densité de nœuds est élevée, car le nombre de collisions augmente fortement avec le trafic à ce débit de données. Notre allocation des limites des SF préserve un taux acceptable lorsque la densité de nœuds augmente par rapport à l'allocation des SF basée sur le SNR (figure 6.4(b)). Dans ce dernier cas, le PDR chute rapidement à 0%, car l'allocation des SF ne tient pas compte des collisions qui augmentent avec la densité de nœuds. Notre politique équilibre donc bien l'effet des collisions et garantit un PDR minimum de 60% jusqu'à 4500 nœuds dans la petite cellule, 1600 nœuds dans la cellule moyenne et 260 nœuds dans la grande cellule.

Les résultats montrent l'efficacité de notre approche qui permet d'équilibrer efficacement l'effet de l'atténuation et des collisions. Des pistes d'améliorations sont néanmoins possibles, en particulier lorsque le PDR calculé pour un SF est plus haut que pour les SFs qui l'entourent (par exemple sur la figure 6.2(a) pour SF11). Un ajustement précis de ces bornes permettrait d'améliorer la répartition des nœuds avec le même PDR garanti.

## 6.3 Allocation optimale avec effet de capture, orthogonalité imparfaite, et macro-diversité

Une autre direction est de regarder plus précisément quel facteur d'étalement peut être alloué à chaque nœud individuellement, dans un réseau LoRaWAN composé d'une ou plusieurs stations de base. Je vais donc détailler ici le programme linéaire que nous avons développé pour allouer de manière optimale les facteurs d'étalement des nœuds LoRaWAN de manière à garantir la probabilité de réussite de la réception des trames à la passerelle, en tenant compte des collisions intra-SF et inter-SF dans les contraintes. Étant donné un réseau LoRaWAN avec 1 ou plusieurs passerelles et un ensemble de nœuds *I* déployés sur la zone couverte dont nous connaissons les positions, et en particulier leur distance aux passerelles, nous cherchons à allouer de manière optimale les SF et à maximiser le nombre de nœuds pris en charge par le réseau de manière à ce que la probabilité de succès de transmission de chaque nœud servi soit supérieure à un seuil $\gamma$.
### 6.3.1 Modélisation du point de vue des nœuds.

Au lieu de déterminer de manière déterministe les SF possibles pouvant être alloués aux nœuds en utilisant la puissance reçue et la sensibilité de la passerelle comme dans les travaux précédents (Cesana et al., 2018; Zorbas et al., 2018), nous prenons en compte la propriété du canal Rayleigh pour estimer la probabilité de succès de réception de trame H défini par l'équation 5.5. Si cette probabilité est supérieure à un seuil donné $H \ge \beta$ pour le SF $f$, alors nous considérons que le nœud situé à une distance $d_i$ peut utiliser le facteur d'étalement correspondant. Dans le cas avec plusieurs passerelles, le nœud $i$ peut se voir allouer le SF $f$ si cette condition est satisfaite pour au moins une passerelle. Nous allons donc réutiliser le modèle de PDR du chapitre précédent en regardant plus précisément l'ensemble des nœuds répartis dans notre réseau afin d'estimer les collisions suivant la répartition des nœuds considérés.

**Effet de capture.** Dans le cas de deux trames LoRa simultanées sur la même fréquence et utilisant le même SF, la trame ayant la puissance la plus élevée peut être décodée si la puissance reçue à la passerelle est au moins 6 dB supérieure à l'autre trame. Soit $C_{ij}$ un paramètre indiquant si les trames LoRa des nœuds $i$ et $j$ utilisant le même SF $f$ peuvent entrer en collision. Par définition :

$$C_{ij}^{f} = \begin{cases} 1 & \text{si } P_{rx}^{i} - P_{rx}^{j} \le 6\text{dB}, \\ 0 & \text{sinon} \end{cases}$$

Dans un déploiement réel de LoRaWAN, chaque message transmis devrait être reçu correctement par au moins une passerelle. Dans le cas de plusieurs passerelles, deux transmissions de nœuds en collision $i$ et $j$ sur le même SF sont perdues si la différence de puissance est inférieure à 6dB pour toutes les passerelles. Sinon, il existe au moins une passerelle capable de décodeur la trame de $i$ pendant que $j$ émet également.

En considérant un nœud $i \in I$ utilisant le SF $f$, le nombre de nœuds interférant potentiellement sur le SF $f$ avec $i$ est donc $\sum_{j \in I, j \neq i} C_{ij}^f$. Par définition, ce nombre est toujours inférieur ou égal au nombre total de nœuds utilisant le SF $f$.

**Orthogonalité imparfaite des SF.** Si les nœuds émetteurs utilisent des SF différents, alors chaque trame peut être démodulée si la différence entre les puissances reçues est supérieure au seuil SINR (rapport signal sur interférence plus bruit) de chaque SF disponible dans (Goursaud & Gorce, 2015). Nous définissons le paramètre $I_{ij}^{ff'}$ pour les collisions potentielles inter-SF entre les SF $f$ et $f'$ par :

$$I_{ij}^{ff'} = \begin{cases} 1 & \text{si } P_{rx}^{i} - P_{rx}^{j} \le \text{SINR}_{ff'} \\ 0 & \text{sinon} \end{cases}$$

où $\text{SINR}_{ff'}$ est la valeur du SINR requis lorsque le nœud émetteur $i$ utilise le SF $f$ et que l'autre transmission simultanée est effectuée en utilisant le SF $f' \neq f$. Dans le cas de plusieurs passerelles, $I_{ij}^{ff'} = 1$ si toutes les passerelles reçoivent $P_{rx}^{i} - P_{rx}^{j} \le \text{SINR}_{ff'}$. Pour un nœud $i \in I$ utilisant le SF $f$, le nombre de nœuds générant des collisions potentielles inter-SF avec $i$ est $\sum_{f' \neq f} \sum_{j \in I, j \neq i} I_{ij}^{ff'}$.
**Probabilité de succès (DER).** Le schéma de contrôle d'accès LoRaWAN correspond à un modèle Aloha non synchronisé. La probabilité de succès dans ce type de modèle est ainsi donnée par la formule 5.6 de $Q_1$ vue dans le chapitre précédent. Au lieu de considérer la densité des nœuds et une probabilité $Q$ de réception malgré les collisions dans chaque anneau de SF, nous adaptons cette probabilité du point de vue de chaque nœud indépendamment, sans prendre en compte le gain de canal aléatoire. Cela simplifie le modèle, mais permet tout de même d'évaluer l'efficacité de l'allocation proposée en intégrant les différentes caractéristiques de réception au niveau des passerelles. Étant donné le nombre total d'interférents potentiels $N_i = \sum_{j \neq i} C_{ij}^f + \sum_{f' \neq f} \sum_{j \neq i} I^{ff'}_{ij}$ du nœud $i \in I$ utilisant le SF $f$, nous devons nous assurer qu'aucun de ces interférents ne commence une transmission dans la période $2\tau_{(12-f)}$ pour éviter la superposition des trames. La probabilité de transmission réussie pour le nœud $i$, également appelée Data Extraction Rate (DER) est donc donnée par

$$ \mathrm{Pr}(i) = e^{(-2\tau_{(12-f)}\lambda_t N_i)} \quad (6.5) $$

où $\lambda_t$ est l'intensité du trafic (Equation 5.2) et $\tau_{(12-f)}$ est le temps de transmission pour le SF $f$ utilisé par le nœud $i$ (cf. Tableau 5.1). Cette formule est ainsi une adaptation de l'équation 5.7 du chapitre précédent.

### 6.3.2 Programme linéaire en nombres entiers pour l'allocation optimale

Soit $y_i^f$ une variable binaire indiquant si le facteur d'étalement $f$ a été attribué au nœud $i \in I$, avec $f \in \{7, ..., 12\}$.

**Définition 6.3.1 (Nœud servi).** Un nœud $i \in I$ est dit *servi* si le modèle a réussi à lui allouer un SF $f \in \{7, ..., 12\}$, i.e. si $\sum_{f \in \{7, ..., 12\}} y_i^f = 1$, tout en respectant les contraintes.

Notre programme linéaire maximise le nombre de nœuds servis dans le réseau en maximisant $\sum_i \sum_f y_i^f$ (Équation (6.6)). Nous associons un paramètre de poids $\omega_i$ à la sélection de chaque nœud $i$ afin de donner une priorité dans l'allocation des SF. Si un nœud peut être servi, nous souhaitons lui attribuer le plus petit SF possible tout en respectant les exigences globales en termes de probabilité de transmission. Nous choisissons un poids qui diminue avec le facteur d'étalement afin d'encourager les petits SF pour les nœuds sélectionnés et d'éviter les grands SF près de la passerelle. En effet, sans $\omega_i$, le modèle n'a aucune indication dans le choix le SF et peut attribuer un SF arbitrairement grand peu importe la distance par rapport aux passerelles. Nous choisissons par exemple $\omega_i = (1 - H)$ car la probabilité $H$ augmente avec le SF.

$$ \max \sum_{i \in I} \sum_{f \in \{7, \dots, 12\}} \omega_i y_i^f \quad (6.6) $$

$$ \sum_{f \in \{7, \dots, 12\}} y_i^f \le 1 \quad \forall i \in I \quad (6.7) $$

$$ H \ge \beta y_i^f \quad \forall i \in I, f \in \{7, \dots, 12\} \quad (6.8) $$

Les contraintes (6.7)) attribuent au plus un SF aux nœuds et (6.8) vérifient si le SF choisi satisfait la condition de réception pour au moins une passerelle LoRa (avec une probabilité $H$).

Ensuite, nous voulons que $\mathrm{Pr}(i)$ soit supérieure à $\gamma$ pour tous les nœuds. Comme nous ne savons pas quel facteur d'étalement les nœuds utiliseront, nous définissons l'ensemble de contraintes suivant :

$$ e^{\frac{-2\lambda_t}{\sum_{f \in \{7, \dots, 12\}} \tau_{(12-f)} y_i^f \left(1 + \sum_{j \neq i} C_{ij}^f y_j^f + \sum_{f' \neq f} \sum_{j \neq i} I_{ij}^{ff'} y_j^{f'}\right)}} \ge \gamma, \forall i \in I \quad (6.9) $$