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

HAL
open science

# Quand l'immobilisme coûte plus cher que l'échange

Igor Dias da Silva, Christelle Caillouet

► To cite this version:

Igor Dias da Silva, Christelle Caillouet. Quand l'immobilisme coûte plus cher que l'échange. AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France. hal-03665199

HAL Id: hal-03665199

https://inria.hal.science/hal-03665199

Submitted on 11 May 2022

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.
# Quand l'immobilisme coûte plus cher que l'échange†

Igor Dias da Silva et Christelle Caillouet

Université Côte d'Azur, Inria, CNRS, I3S, Sophia Antipolis

Dans cet article nous présentons un modèle en programmation linéaire permettant de déployer un réseau aérien à moindre coût pour la collecte de données de capteurs mobiles. Nous utilisons un modèle énergétique réaliste afin d'étudier le compromis entre distance parcourue et énergie dépensée. Ce modèle montre que l'état stationnaire d'un drone est plus coûteux en énergie que le déplacement à une vitesse modérée, ce qui se répercute dans nos résultats par des échanges de positions entre les drones au cours du temps afin de limiter leur consommation énergétique.

**Mots-clefs** : UAVs, optimisation, compromis énergie distance

## 1 Introduction

Ce travail présente une étude sur le compromis entre la consommation énergétique et le temps de vol de drones afin de couvrir des capteurs mobiles au sol et assurer un réseau aérien connecté avec une station de base pendant toute une période de temps donnée [BCC19]. Dans un scenario où la collecte de données est critique et essentielle, il est nécessaire d'assurer un suivi constant par les drones ou d'ajouter/enlever de nouveaux drones dans le réseau aérien à chaque instant. Afin de garantir cette couverture et cette connectivité constantes tout en limitant les coûts d'utilisation du réseau aérien, plusieurs paramètres doivent être pris en compte. Etant donné un ensemble fixé de drones disponibles, notre but est de minimiser le coût de déploiement d'un tel réseau. Pour cela, le temps de vol est un facteur critique. Ce temps peut être affecté par deux critères principaux : la distance totale à parcourir, et la consommation énergétique qui influe sur le niveau de batterie du drone [TNZB18]. Dans la suite, nous présentons notre modèle pour déployer un réseau aérien à moindre coût pour la collecte de données de capteurs mobiles, basé sur un modèle énergétique réaliste. Nous dérivons ensuite le programme linéaire permettant d'étudier le compromis entre distance parcourue et énergie dépensée. Une analyse des résultats obtenus montre qu'étant donné que l'état stationnaire d'un drone est plus coûteux en énergie que le déplacement à une vitesse modérée, les drones ont ainsi intérêt à échanger leurs positions au cours du temps afin de limiter leur consommation énergétique et ainsi augmenter la durée de vie du réseau.

## 2 Modèle

Nous considérons un modèle discret dans lequel les positions des cibles sont estimées à différents intervalles de temps $t \in [0,T]$. Soit $P$ l'ensemble des positions 3D possibles pour les drones. 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 $r_p^h \le h_p \tan(60^\circ/2)$ (h est l'altitude de la position p du drone). Pour une collecte efficace, les drones sont connectés entre eux et avec une station de base b située au sol. Etant donnés $N^t$, $r_p^h$ et $R_p$, nous introduisons une représentation de notre topologie par un graphe dynamique. A 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 en fonction des distances euclidiennes en 2D ($d(p,q)$) et 3D ($D_{pq}$) :

**Definition 1** 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, \text{ et}$$

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

<footnote>†Ce travail a été accepté et publié au workshop UAV 2020 de IEEE SECON.</footnote>
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Energie consommée par le drone en fonction de sa vitesse.</figcaption></figure>

<table><caption>TABLE 1 – Résultats et performances du modèle pour les cas extrêmes ($α = 0$ ou $1$). Donne une indication sur 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>Tot. Dist.</th><th>Part. Dist.</th><th>Energie</th><th>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>

Le but est de trouver un ensemble de chemins dans $G^t$ entre la station de base et les capteurs de $N^t$, de telle sorte qu'il y ait un drone déployé sur chaque sommet des ces chemins pour assurer la couverture et la connectivité. Ensuite, l'objectif global est d'associer une position à chaque pas de temps $t$ avec un drone, de sorte que nous minimisons la distance totale parcourue et l'énergie consommée par chaque drone.

**Distance** : Comme pour le graphe $G^t$, les distances mesurées sont les distances euclidiennes en 3D entre 2 positions $p$ et $q$ appartenant à $\{b\} \cup P : D_{p,q} = \sqrt{(x_p - x_q)^2 + (y_p - y_q)^2 + (h_p - h_q)^2}$. Cet objectif vise à minimiser les longueurs des trajectoires des drones depuis et jusqu'à la station de base $b$.

**Energie** : Nous souhaitons ici minimiser l'énergie consommée par les drones au cours de leurs trajets. Nous utilisons le modèle présenté dans [ZXZ19] car il est plus précis et réaliste que ceux utilisés dans [ZDPPRG16] et [CGR19]. Il permet de connaître la consommation énergétique $P(v)$ d'un drone en fonction de sa vitesse $v$ pour des translations horizontales (Figure 1). 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_{p,q}/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 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_{p,q}}{v} + E_{hovering} \quad \text{et} \quad E_{hovering} = \begin{cases} P(0)(tts - \frac{D_{p,q}}{v}) & \text{si } p \in P \text{ et } q \in P \\ 0 & \text{sinon} \end{cases}$$

### 3 Programme linéaire

Nous définissons plusieurs ensembles de variables binaires afin de décider les positions pour chaque drone au cours du temps. $y_{p,m}^t$ indique si le drone $m \in [1, M]$ est placé en position $p \in P$ au temps $t \in [0, T]$. $z_{p,q,m}^{t-1,t}$ vaut 1 si le drone $m$ était en position $p$ à $t-1$ puis se déplace en position $q$ à $t$. Enfin, nous définissons les variables entières $x_p^t$ indiquant combien de drones sont positionnés en $p$ au temps $t$. Cette variable vaudra 0 ou 1 pour une position $p \in P$, et une valeur entre 0 et $M$ pour la station de base $b$ où peuvent se regrouper tous les drones (non utilisés ou qui sont rentrés à un moment donné) (Equation (1)).

**Contraintes de placement** : A chaque temps $t$, nous devons placer chaque drone $m$ en une position $p \in P$, ou sur la station de base $b$ (s'il n'est pas utilisé à ce moment là). Nous utilisons donc les variables $x$, $y$, et $z$.
Nous assurons la définition des variables $x'_p$ ainsi que le fait qu'au plus un drone puisse se trouver en une position $p$ à chaque intervalle de temps par l'équation (1).

$$x'_{p} = \sum_{m=1}^{M} y'_{p,m} \quad , \forall t \in [0, T] \text{ and } \forall p \in P \cup \{b\}, \qquad x'_{p} \in [0, M] \quad \text{if } p = b, \quad x'_{p} \in [0, 1] \quad \text{if } p \neq b \quad (1)$$

Puis nous vérifions la concordance des valeurs entre y et z dans l'équation (2) (car $z_{p,q,m}^{t-1,t} = y_{p,m}^{t-1} * y_{q,m}^t$).

$$z_{p,q,m}^{t-1,t} \le y_{p,m}^{t-1}, \quad z_{p,q,m}^{t-1,t} \le y_{q,m}, \quad z_{p,q,m}^{t-1,t} \ge y_{p,m}^{t-1} + y_{q,m} - 1 \quad (2)$$

Les contraintes (3) assurent qu'un drone ne puisse pas se trouver sur plusieurs positions simultanément.

$$\sum_{p \in P \cup \{b\}} y'_{p,m} = 1 \quad , \forall t \in [0, T] \text{ and } \forall m \in [0, M] \quad (3)$$

**Contraintes de connectivité et couverture :** La couverture des capteurs mobiles est assurée par l'existence d'un flot entre b et $N^t$ dans $G^t$. Les variables sont notées $f_{pl}^t$ et correspondent à la quantité de flot transmise de $p$ à $l$ au temps $t$.

$$\sum_{l \in V^t, l \neq p} f_{pl}^t - \sum_{l \in V^t, l \neq p} f_{lp}^t = \begin{cases} |N^t| & \text{if } p = b \\ 0 & \text{if } p \in P \quad \forall t \in [0, T], p \in V^t, f_{pl}^t \in \mathbb{R} \\ -1 & \text{if } p \in N^t \end{cases} \quad (4)$$

Chaque sommet utilisé par le flot doit correspondre à une position choisie pour un drone afin d'assurer la couverture des capteurs et la connectivité du réseau aérien.

$$f_{pl}^t \le x'_p |N^t|, \forall t \in [0, T], (p, l) \in E^t \text{ with } p \in P \quad (5)$$

**Objectif :** Nous souhaitons minimiser le poids total des trajectoires des drones du réseau aérien. 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_{m=1}^{M} D_{p,b} y_{p,m}^0 + \sum_{t=1}^{T} \sum_{p,q \in P \cup \{b\}} \sum_{m=1}^{M} D_{p,q} z_{p,q,m}^{t-1,t} + \sum_{p \in P} \sum_{m=1}^{M} D_{p,b} y_{p,m}^T$ pour optimiser la distance parcourue, et $E_{total} = \sum_{p \in P} \sum_{m=1}^{M} E_{p,b} y_{p,m}^0 + \sum_{t=1}^{T} \sum_{p,q \in P \cup \{b\}} \sum_{m=1}^{M} E_{p,q} z_{p,q,m}^{t-1,t} + \sum_{p \in P} \sum_{m=1}^{M} E_{p,b} y_{p,m}^T$ dans le cas de l'énergie totale dépensée. 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 (6)$$

où $\alpha \in [0, 1]$ est un paramètre d'entrée permettant d'étudier le compromis entre distance et énergie.

## 4 Résultats

Le modèle a été implémenté en Java et résolu en utilisant le solveur IBM Cplex 12.10. Le nombre de positions varie entre 9, 16 et 25 positions qui sont distribuées sur une grille dans le carré de 10 000 m² à une hauteur de 45 m. Nous utilisons au maximum $M = 5$ drones avec une portée de communication de 60 m pour couvrir 5 capteurs mobiles. La période d'observation est de 7 pas de temps, la durée entre les pas de temps est fixée à 2 secondes. Les capteurs se déplacent de manière aléatoire à une vitesse entre 5 et 20 m/s dans la zone de couverture des positions. La station de base se trouve dans le coin inférieur gauche.

**Efficacité du modèle :** Ce modèle permet de calculer des trajectoires optimales pour les drones assurant la connectivité du réseau aérien et la couverture de tous les capteurs au cours du temps. Le tableau 1 présente les résultats avec une seule considération : soit optimiser la distance ($\alpha = 0$), ou l'énergie ($\alpha = 1$). La distance totale moyenne parcourue avec 9 positions sur différents scenarios de déplacement est de 642m et baisse à 568m avec 25 positions. 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.
<figure><img src="image_3.png" /><figcaption>FIGURE 2 – Compromis énergie dépen-
sée/distance parcourue ($\alpha$ varie entre 0 et 1).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 3 – Echange de positions pour limiter la consom-
mation énergétique.</figcaption></figure>

**Compromis énergie/distance** : La dernière ligne du tableau 1 montre qu'en 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%, de 36389.42 à 16558.69 Joules. En effet, le modèle énergétique adopté nous donne une consommation d'énergie 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 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 consom-
mation d'énergie. Des compromis équitables existent comme par exemple sur la figure 2, 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.

5 Conclusion

Nous avons présenté un modèle en programmation linéaire pour le déploiement optimal d'un réseau aérien connecté et couvrant des capteurs mobiles. Les trajectoires optimales des drones sont calculées en combinant l'optimisation de la distance parcourue et l'énergie consommée basée sur un modèle réaliste. Les résultats théoriques obtenus permettent de mettre en évidence la nécessité pour un drone de se déplacer à une vitesse modérée plutôt que de rester en régime stationnaire afin de dépenser le minimum d'énergie et augmenter la durée de vie du réseau aérien.

Une évolution du modèle est à considérer afin de pouvoir tester nos hypothèses sur des réseaux plus im-
portants et des possibilités de placement plus grandes. Des techniques avancées de recherche opérationnelle
comme la génération de colonnes sont actuellement mises en oeuvre pour le passage à l'échelle du modèle.

Références

[BCC19] Y. Busnel, C. Caillouet, and D. Coudert. Self-organized UAV-based Supervision and Connectivity : Challenges and Opportunities. In *IEEE NCA*, Cambridge, United States, September 2019.

[CGR19] C. Caillouet, F. Giroire, and T. Razafindralambo. Efficient data collection and tracking with flying drones. *Ad Hoc Networks*, 89:35–46, 2019.

[TNZB18] A. Thibbotuwawa, P. Nielsen, B. Zbigniew, and G. Bocewicz. Energy consumption in unmanned aerial vehicles : a review of energy consumption models and their relation to the uav routing. In *ISAT*, pages 173–184. Springer, 2018.

[ZDPPRG16] D. Zorbas, L. Di Puglia Pugliese, T. Razafindralambo, and F. Guerriero. Optimal drone placement and cost-efficient target coverage. *Journal of Network and Computer Applications*, 75:16–31, 2016.

[ZXZ19] Y. Zeng, J. Xu, and R. Zhang. Energy minimization for wireless communication with rotary-wing uav. *IEEE Transactions on Wireless Communications*, 18(4):2329–2345, 2019.