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

HAL
open science

# MPR alternant : un algorithme de diffusion MANET équilibré

Aymeric Agon-Rambosson, Jonathan Lejeune, Julien Sopena, Pierre Sens

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

## To cite this version:

Aymeric Agon-Rambosson, Jonathan Lejeune, Julien Sopena, Pierre Sens. MPR alternant : un algorithme de diffusion MANET équilibré. COMPAS 2022 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Jul 2022, Amiens, France. hal-04007347

HAL Id: hal-04007347

https://hal.science/hal-04007347

Submitted on 28 Feb 2023

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

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

Public Domain
# MPR alternant : un algorithme de diffusion MANET équilibré

Aymeric Agon-Rambosson, Jonathan Lejeune, Julien Sopena et Pierre Sens *

Équipe DELYS, LIP6,
Sorbonne Université - CNRS - INRIA
4, place Jussieu
75005 Paris - France
prénom.nom@lip6.fr

## Résumé

Les réseaux mobiles adhoc (MANET) sont des réseaux de noeuds mobiles hétérogènes communicants par radio dans lesquels on ne fait aucune hypothèse quant à une infrastructure réseau préexistante. Ce genre de réseaux nécessite une opération de diffusion globale (*broadcast*) performante. Si les noeuds sont réputés ne connaître aucune caractéristique globale du système, il est néanmoins parfois possible de construire sur la seule base d'informations locales une topologie virtuelle couvrante de son voisinage à partir de messages de contrôle. MPR est un algorithme qui s'appuie sur une telle topologie pour améliorer la couverture de la diffusion et diminuer son coût en messages, en limitant la charge de la retransmission à un ensemble de voisins relais bien choisis. Malheureusement, ces topologies virtuelles couvrantes ont tendance à trop s'appuyer sur les noeuds les mieux connectés, causant une surconsommation de leur batterie. Nous proposons un nouvel algorithme, MPR alternant, qui s'efforce de constituer plusieurs ensembles disjoints de relais pour chaque noeud, permettant aux messages de diffusion de les utiliser de manière alternante. Notre simulation de la pile réseau complète de systèmes de densité variable montre que notre algorithme distribue de manière plus égalitaire les coûts énergétiques, sans dommages pour la couverture ni pour le coût en messages, permettant aux noeuds fonctionnant sur batterie de survivre plus longtemps.

**Mots-clés** : MANET, diffusion globale, MPR, répartition énergétique

## 1. Introduction

Un réseau mobile adhoc (MANET) consiste en un ensemble de noeuds mobiles potentiellement hétérogènes communicant via radio directement les uns avec les autres. Ce paradigme développé à la fin des années 90 représente fidèlement des environnements de calcul informatique en brouillard, les réseaux maillés, les réseaux de capteurs sans fil, ainsi que diverses situations de réseaux correspondant à des applications de type « Internet des objets ».

Puisque ce paradigme ne permet aucune hypothèse quant à l'existence d'une infrastructure réseau préalable, les noeuds sont amenés à relayer des messages qui ne leur sont pas destinés. Les communications sans fil sont soumises à des erreurs, en particulier des collisions : un noeud situé dans l'intersection des zones de couverture de deux autres noeuds qui transmettent en même temps ne recevra aucun des deux messages. Dans le cas des communications sans fil, ces collisions sont impossibles à détecter [8, 14], difficiles à éviter [8, 14] et coûteuses à traiter. Ce problème est particulièrement grave pour les opérations de diffusion globale, qui sont à la fois primordiales dans les réseaux mobiles adhoc (les algorithmes de routage efficaces comme [9] s'appuient sur une primitive de diffusion globale) et ont de grandes chances d'occasionner des collisions [15], puisque les retransmissions sont synchronisées.

<footnote>∗. Ce travail est financé par le projet ANR SeMaFoR</footnote>
Restreindre la charge des retransmissions à un ensemble de noeuds du système comme proposé par [12] permet d'économiser des messages, éviter des collisions et de préserver la couverture de la diffusion. Cela signifie en revanche que la charge des retransmissions est inégalement répartie, et que les noeuds les mieux connectés consomment leur batterie beaucoup plus vite que les autres.

**Contributions.** Nous cherchons à pallier ce problème en proposant une primitive de diffusion globale qui soit à la fois :

— Efficace, c'est-à-dire qu'elle couvre le plus grand nombre possible de noeuds du système.

— Efficiente, c'est-à-dire qu'elle cause aussi peu de retransmissions que possible.

— Égalitaire, c'est-à-dire qu'elle répartisse aussi également que possible la charge des retransmissions sur tous les noeuds sans dégrader l'efficience ou la couverture.

Pour ce faire, nous proposons le nouvel algorithme de *MPR alternant*, dans lequel plusieurs ensembles de relais sont construits, et chacun d'entre eux est utilisé à son tour quand un message doit être envoyé ou retransmis. Nous ciblons les MANETs *denses* et *statiques*, et nous verrons pourquoi cette restriction ne signifie pas de perte de généralité pour notre algorithme.

Nous commençons par présenter un rapide état de l'art de la diffusion MANET. Nous rappellerons ensuite les hypothèses de ce paradigme quant au système et au modèle de communications, et nous rappelons dans les grandes lignes le fonctionnement du protocole MAC 802.11. Ensuite, nous rappelons plus spécifiquement le principe de l'algorithme MPR, et en particulier la procédure de sélection des relais. Nous présentons notre amélioration, *MPR alternant* en proposant une nouvelle manière de sélectionner les relais. Le gain amené par notre amélioration est évalué en utilisant une simulation de la pile réseau complète à l'aide de OMNeT++/INET [16]. Nous montrons que sans augmenter sensiblement les retransmissions ni sans dégrader la couverture, nous pouvons répartir la charge de la retransmission de manière plus égalitaire. Nous terminons par une discussion des perspectives de travaux futurs, puis nous concluons.

## 2. État de l'art

L'algorithme le plus simple de la littérature, le *flooding*, dans lequel chaque noeud relaie un message applicatif à chaque première réception de ce dernier, a de grandes chances, dans des environnements denses, de causer le problème de la « tempête de diffusion » [15] (*broadcast storm*) à cause d'un trop grand nombre de retransmissions simultanées, augmentant le coût en messages et diminuant la couverture.

Les algorithmes de diffusion proposés lors de ces vingt dernières années se sont efforcés d'améliorer *flooding* en trouvant diverses manières de réduire le nombre de relais [6, 13]. [13] a proposé deux catégories d'algorithmes, les algorithmes à *flooding* conditionnel et les algorithmes à topologie virtuelle couvrante. La première catégorie rassemble tous les algorithmes qui ajoutent des conditions de diverse sorte à la retransmission lors de la réception du message (probabiliste [7], selon un compteur [10] ou selon la distance à l'envoyeur [2]). La seconde rassemble ceux qui construisent et maintiennent à l'avance une topologie virtuelle couvrante, soit un ensemble fixe de relais, en utilisant des messages de contrôle périodiques (cette topologie peut être une forêt d'arbre couvrants [5] ou un ensemble dominant connexe [1]). Les algorithmes à *flooding* conditionnel sont plus performants dans des MANETs peu denses ou trop dynamiques, tandis que les algorithmes à topologie dominent dans les MANETs denses et stables [4]. L'impossibilité de proposer un algorithme qui soit performant dans les deux environnements à la fois a amené [3] à proposer un protocole d'interopérabilité permettant d'exécuter un algorithme ou un autre selon l'environnement local, et de passer de manière coordonnée de l'un à l'autre. Il devient donc possible de proposer un algorithme qu'on sait n'être performant que dans un des deux environnements sans perte de généralité : il pourra au besoin être associé à un algorithme « complémentaire » en situation réelle.

Dans un environnement favorable, un algorithme comme celui des Relais MultiPoint (MPR) proposé par [12] sera très performant tout en ne s'appuyant que sur la connaissance du 2-voisinage de chaque noeud, information facile à obtenir par l'envoi régulier de la liste de ses voisins. MPR utilise un algo-
rithme glouton pour construire à partir de l'ensemble des 1-voisins d'un noeud un ensemble de relais suffisant pour garantir une couverture complète des 2-voisins de ce même noeud. Quand un noeud décide de transmettre un message applicatif, ou doit retransmettre un message qu'il a reçu d'un de ses voisins, il indique dans l'en-tête du message les identifiants des relais, qui doivent eux-mêmes re-transmettre et spécifier leurs propres relais, et ainsi de suite... L'ensemble des relais choisi n'est pas nécessairement minimal, mais est généralement composé d'une fraction des 1-voisins.

Cependant, cet ensemble est déterministe, et un 2-voisinage bien précis produira toujours le même ensemble de relais, ce qui signifie qu'une suite de messages envoyés par un noeud source vont toujours être retransmis par les mêmes 1-voisins. La charge énergétique des retransmissions est donc inéquitablement répartie, ce qui va avoir tendance à engendrer une surconsommation énergétique chez les noeuds les mieux connectés (puisqu'ils vont avoir tendance à être choisis souvent). Nous voulons proposer un algorithme qui atténue ce problème.

### 3. Hypothèses et concepts généraux

Nous commençons par préciser le système et le modèle de communication. Ensuite, nous décrirons le protocole MAC 802.11 et la spécification de la diffusion globale dans les MANETs.

#### 3.1. Système et modèle de communications

Un ensemble N de noeuds $n_i, n_j, ...$ sont statiques dans un carré de dimension 2. On suppose qu'aucune information de localisation GPS n'est disponible. Les noeuds communiquent via un émetteur-récepteur sans fil omnidirectionnel qui dispose d'une portée fixe d'émission T et de réception R identiques et choisis de manière à assurer la connexité du réseau. La zone de couverture d'un noeud est donc donnée par un cercle centré en le noeud de rayon T. Quand un noeud émet une trame, tous les autres noeuds dans ce cercle reçoivent le signal avec une probabilité 1, tandis que tous les noeuds à l'extérieur de ce cercle le reçoivent avec une probabilité 0. On voit immédiatement que le coût de transmettre un message à son voisinage immédiat (l'ensemble des noeuds à portée de transmission) est indépendant de la taille de ce voisinage. En raison de limitations physiques des radiotransmetteurs, les noeuds ne peuvent pas envoyer et recevoir en même temps.

Comme il a été brièvement mentionné plus haut, un noeud situé à l'intersection de deux noeuds distincts qui transmettent une trame simultanément ne recevra aucun des deux signaux correctement : ce phénomène s'appelle *collision*. Les collisions sont impossibles à détecter par l'émetteur [8], et doivent donc être esquivées par quelque protocole de contrôle d'accès au medium (MAC).

#### 3.2. Le protocole MAC IEEE 802.11

Le rôle de la couche MAC du protocole IEEE 802.11 est d'ordonnancer l'utilisation du medium de communication (dans notre cas, l'onde radio porteuse du signal, ci-après nommée *porteuse*) de manière à éviter les collisions. Selon ce protocole, les noeuds qui désirent transmettre une trame doivent d'abord écouter la porteuse afin de vérifier qu'aucun autre noeud n'est en train de transmettre. Plus spécifiquement, le noeud créé un compteur aléatoire, et le décrémente à chaque fois qu'il n'a entendu aucun signal sur la porteuse pendant une période de temps spécifique appelée DIFS (*DCF InterFrame Spacing*). La trame est envoyée quand le compteur atteint 0. Le protocole autorise de manière optionnelle les noeuds qui reçoivent une trame correcte à envoyer immédiatement une courte trame d'acquittement. Cette partie optionnelle est bien évidemment désactivée lorsque la trame est diffusée globalement, puisque tous les voisins enverraient leur trame d'acquittement en même temps, empêchant le noeud source de recevoir aucune de ces trames correctement.

#### 3.3. La diffusion globale dans les MANETs

Le but d'un protocole de diffusion global pour MANET est d'envoyer un message au plus grand nombre possible de noeuds dans le réseau, malgré la mobilité et les collisions. N'importe quel noeud du système peut envoyer un message, et un message peut avoir à être divisé en de multiples trames MAC. Les noeuds sont susceptibles de retransmettre des messages lors de leur première réception (et donc d'agir comme des *relais*). Les réceptions suivantes du même message (*duplicats*) sont simplement ignorées (ce
qui suppose le maintien dans la mémoire de chaque noeud d'une mémoire glissante des messages re-
transmis). Le but est d'atteindre une bonne couverture (la proportion des noeuds qui ont vu le message
délivré à leur couche applicative) tout en diminuant le nombre de relais dans le réseau, de manière à
diminuer les coûts énergétiques et éviter les collisions.

4. Algorithme

Nous allons commencer par rappeler le fonctionnement de la sélection des relais dans MPR statique.
MPR statique comme alternant partent du même principe que chaque noeud connaît son 2-voisinage
soit la liste de ses 1-voisins, de ses 2-voisins, et la totalité des connexions entre tout membre de son
2-voisinage. Le but est de garantir une couverture totale du 2-voisinage, soit s'assurer que chacun des
2-voisins est couvert par au moins un relais.

4.1. MPR statique

L'ensemble des relais est construit ainsi (Algorithme 1) : premièrement, l'ensemble des relais nécessaires est inclus dans l'ensemble (lignes 3 à 6). Un relais est dit nécessaire quand il est le seul à fournir une couverture sur un ensemble non vide de 2-voisins : si il n'était pas inclus, la couverture ne saurait être complète. Bien entendu, tous les 2-voisins couverts par ces relais nécessaires sont enlevés de l'ensemble des 2-voisins restant à couvrir (ligne 6).

Par la suite, un ensemble de relais *suffisants* est calculé ainsi (lignes 7 à 10) : le 1-voisin qui couvre le plus de 2-voisins restants à couvrir (ligne 8) est ajouté à la liste des relais (ligne 9), et les 2-voisins ainsi couverts sont expurgés (ligne 10). L'algorithme s'arrête quand il ne reste plus de 2-voisins à couvrir. Nous savons que l'algorithme se termine, puisque chaque 2-voisin est couvert par au moins un 1-voisin : au pire cas, tous les 1-voisins sont inclus dans l'ensemble des relais.

L'ensemble des relais rendu par cet algorithme est déterministe : étant donné un noeud et son 2-voisinage,
le même ensemble de relais sera choisi. Une conséquence de ça est que pour une suite de messages en-
voyés ou retransmis par le noeud, tous les messages seront retransmis par les mêmes relais (si on admet
que le voisinage ne change pas pendant ce temps), qui épuiseront leur batterie, pendant que le reste des
1-voisins sera oisif.

4.2. MPR alternant

De manière à remédier au moins partiellement à ce problème, nous proposons dans MPR alternant (Al-
gorithme 2) de construire plusieurs ensembles de relais (lignes 2 et 5) qui devront être disjoints deux à
deux, à l'exception des relais nécessaires, qui devront être dans tous les ensembles. Pour ce faire, nous
introduisons uniquement des variables locales supplémentaires, comme un ensemble de noeuds « in-
terdits » (ligne 3), et un temporaire pour stocker l'ensemble de relais en cours de construction (ligne 4).
L'algorithme prend la forme d'une boucle infinie (lignes 6 à 22) de construction de relais, qui se termine
dès qu'on échoue (ligne 14). La construction de l'ensemble courant passe d'abord par l'ajout de tous les
relais nécessaires (lignes 7 à 10), puis par l'ajout d'un ensemble suffisant (lignes 11 à 17). Cette fois-ci, les
relais ainsi ajoutés le sont aussi dans l'ensemble des relais « interdits » (ligne 16), ce qui garantit qu'ils
ne seront pas réutilisés dans un ensemble futur. Une fois que l'ensemble des relais est suffisant, il est
ajouté à l'ensemble des ensembles (ligne 18), l'ensemble des relais courants est réinitialisé (ligne 19) et
celui des 2-voisins à couvrir (ligne 20) avant de recommencer. On est assuré de retourner un ensemble
d'ensemble non-vide (au moins celui que nous aurait proposé MPR statique), et on est aussi assuré de
la terminaison de l'algorithme (la quantité d'ensembles de relais qu'il est possible de construire ainsi est
nécessairement finie). On est aussi assuré qu'on ne trouvera pas le même relais non strictement néces-
saire dans plusieurs ensembles de relais.

Le nombre d'ensembles qu'on sera capable de construire, ainsi que la taille de chacun de ces ensembles,
dépendront des propriétés structurelles du 2-voisinage du noeud considéré. Néanmoins, puisque les
« meilleurs » relais seront choisis dans les premiers ensembles, on peut s'attendre à ce que la taille des
ensembles augmente. Un algorithme qui utiliserait ces ensembles de manière alternante (notre proposi-
tion) selon un tourniquet occasionnerait donc plus de messages qu'un algorithme qui ne se servirait que
du premier (la version originale, ou statique, de MPR). En revanche, on peut légitimement s'attendre
à ce que la répartition des retransmissions soit plus égalitaire avec la version alternante de l'algorithme.
Pour mesurer l'importance de ces deux effets, et donc l'intérêt de notre variante, nous nous proposons
de simuler les deux algorithmes à l'aide d'un simulateur à événements discrets.

5. Évaluation

5.1. Protocole expérimental

La performance d'un algorithme de diffusion globale dans un MANET s'évalue traditionnellement dans la littérature selon les métriques suivantes :

— le taux de couverture, soit le rapport du nombre de noeuds atteint par un message sur le nombre total de noeuds du graphe.

— le nombre de retransmissions imputables à l’algorithme.

En plus, dans notre cas, puisqu'on cherche à atteindre une répartition plus égalitaire des retransmis-
sions, on mesurera aussi la variance du nombre des retransmissions sur le graphe. Plus une variance est
élevée, plus la répartition est inégalitaire.

Puisque le gain attendu de notre variante dépend des propriétés structurelles du graphe, la manière
dont ces derniers seront générés est importante. Nous proposons d'utiliser la procédure du graphe géo-
métrique aléatoire, qui fonctionne ainsi : on place N points dans le carré unité de manière uniforme, et
on considère qu'une arête relie deux points si et seulement si leur distance euclidienne est inférieure à
un paramètre R, qui représentera dans notre cas la portée des antennes des radiotransmetteurs. Bien évi-
demment, un graphe ainsi créé n'est pas nécessairement connexe, ce qui implique de filtrer les graphes
non connexes après génération. La valeur de N aura une influence directe sur l'arité moyenne du graphe
[11], et donc sur la performance des algorithmes MPR, nous allons donc faire varier ce paramètre, en
créant donc 5 échantillons de graphes avec N valant respectivement 50, 100, 150, 200 et 250.

Pour que la simulation d'un réseau MANET soit réaliste, on doit disposer d'une modélisation réaliste des antennes WiFi et de la couche MAC IEEE 802.11, de manière à correctement représenter le phénomène des collisions. Le simulateur à événements discrets OMNeT++, ou plus exactement le socle INET associé, dispose d'une telle modélisation déjà implémentée, dont nous nous servirons. Il nous reste à implémenter l'algorithme MPR statique, notre variante alternante, ainsi que l'algorithme de flooding pour fournir une ligne de base quant aux retransmissions. Un sous-ensemble de noeuds du graphe seront choisis au hasard pour initier des messages de diffusion, qui seront de taille fixe, et qui seront envoyés séquentiellement, de manière à ce qu'un message ait fini d'être propagé avant que l'envoi du suivant commence.

5.2. Résultats

<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Évaluation des métriques selon l’algorithme (couleur) et l’arité moyenne du graphe (abscisses).</figcaption></figure>
On remarque en premier lieu sur le graphique 1a que notre algorithme ne dégrade pas le taux de couverture : dans les conditions de notre expérience, et malgré les collisions, les trois algorithmes présentent une couverture parfaite, et ce pour toutes les tailles de graphe (identifiées par l'arité moyenne).

En ce qui concerne les retransmissions occasionnées, nous voyons sur le graphique 1b que MPR statique et MPR alternant permettent d'économiser un grand nombre de messages (près de la moitié) par rapport au flooding. Ensuite, comme prévu, MPR alternant occasionne légèrement plus de messages que MPR statique (de l'ordre de 5% en plus), parce que les ensembles de relais après le premier sont probablement moins bons en ce qu'ils contiennent plus de relais pour assurer la même couverture.

En revanche, comme on peut le voir sur le graphique 1c, ce léger coût en messages supplémentaires permet d'atteindre une bien meilleure répartition des retransmissions sur le graphe. Si le flooding propose la répartition la plus égalitaire des retransmissions (tout le monde retransmet une fois par message applicatif, ce qui explique la variance nulle), on pouvait s'attendre à ce que l'utilisation alternante d'ensembles de relais « presque disjoints » (hormis les relais nécessaires) débouche sur une répartition plus égalitaire que l'utilisation d'un seul ensemble. Nous voyons que l'effet est plus marqué pour les graphes à arité forte (de l'ordre de 35% de variance en moins) que sur les graphes à arité faible (10-15% de variance en moins), parce qu'il est possible d'y construire plus d'ensembles.

La répartition des retransmissions dans MPR alternant reste partiellement inégalitaire pour plusieurs raisons :

- Les relais nécessaires doivent être utilisés à chaque retransmission, ils auront donc une proportion de messages retransmis plus élevée que la moyenne.

- Les noeuds du 1-voisinage les moins bien connectés ne se retrouvent dans aucun ensemble de relais et ne sont donc jamais utilisés.

- Les noeuds en bordure de réseau n'ont pas à retransmettre en raison de leur position : tous leurs voisins sont déjà couverts quand ils reçoivent le message.

Ces causes de la répartition inégalitaire des retransmissions ne peuvent être atténuées sans augmenter davantage le nombre des retransmissions redondantes. D'une certaine manière, notre algorithme est un compromis entre un algorithme très égalitaire, mais très peu efficient (flooding) et un algorithme très efficient, mais très inégalitaire (MPR statique).

## 6. Conclusion

Nous avons proposé une amélioration de l'algorithme MPR qui permet d'atténuer la mauvaise répartition des retransmissions typiques de cet algorithme, au prix d'une augmentation légère du total des retransmissions occasionnée par la diffusion globale d'un message applicatif. Nous construisons plusieurs ensembles de relais presque disjoints, chacun d'entre eux étant utilisé à son tour. Nos expérimentations montrent que notre mécanisme diminue sensiblement la variance en augmentant très peu la proportion des messages retransmis, et sans dégrader la couverture.

Selon les préférences de l'application utilisant la primitive de diffusion globale, il est possible d'arbitrer entre l'efficience et la répartition égalitaire en limitant la quantité d'ensembles de relais sur lesquels alerner.

Il est possible d'améliorer ce mécanisme de répartition de charge en incluant dans les messages de contrôle des informations sur sa propension à retransmettre en fonction de son alimentation en énergie. De cette manière, des noeuds qui disposeraient d'une source d'énergie pérenne seraient utilisés à la place de noeuds fonctionnant sur batterie.
Bibliographie

1. Adjih (C.), Jacquet (P.) et Viennot (L.). – Computing Connected Dominated Sets with Multipoint Relays. *Ad Hoc & Sensor Wireless Networks*, vol. 1.1-2, 2005, p. 27-39.

2. Cartigny (J.) et Simplot (D.). – Border Node Retransmission Based Probabilistic Broadcast Protocols in Ad-Hoc Networks. *IEEE annual Hawaii Intl. Conference on System Sciences*, 2003.

3. Carvajal-Gómez (R.), Bromberg (Y.-D.), Elkhatib (Y.), Réveillère (L.) et Rivière (E.). – Emergent Overlays for Adaptive MANET Broadcast. *Symposium on Reliable Distributed Systems*, 2019.

4. Carvajal-Gómez (R.), Gonzalez-Herrera (I. Y.), Bromberg (Y.-D.), Réveillère (L.) et Rivière (E.). – Density and Mobility-Driven Evaluation of Broadcast Algorithms for MANETs. *IEEE International Conference on Distributed Computing Systems*, 2017.

5. Casteigts (A.), Chaumette (S.), Guinand (F.) et Pigné (Y.). – Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks. *Ad-hoc, Mobile, and Wireless Network Conference*, 2013.

6. Gutiérrez-Reina (D.), Toral-Marín (S. L.), Johnson (P.) et Barrero-García (F. J.). – A survey on probabilistic broadcast schemes for wireless ad hoc networks. *Ad Hoc Networks*, vol. 25, 2015.

7. Haas (Z. J.), Halpern (J. Y.) et Li (E. L.). – Gossip-based ad hoc routing. *IEEE Conference on Computer Communications*, 2002.

8. IEEE 802.11 Working Group. – Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. *IEEE Std 802.11-2016*, 2016.

9. Jacquet (P.), Mühlethaler (P.), Clausen (T.), Laouiti (A.), Qayyum (A.) et Viennot (L.). – Optimized Link State Routing Protocol for Ad Hoc Networks. *IEEE Intern. Multitopic Conference*, 2001.

10. Mohammed (A.), Ould-Khaoua (M.), Mackenzie (L. M.), Perkins (C.) et Abdulai (J.). – Probabilistic counter-based route discovery for mobile ad hoc networks. *International Conference on Wireless Communications and Mobile Computing*, 2009.

11. Penrose (M. D.). – *Random Geometric Graphs*. – Oxford University Press, 2003.

12. Qayyum (A.), Viennot (L.) et Laouiti (A.). – Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks. *IEEE annual Hawaii Intl. Conference on System Sciences*, 2002.

13. Ruiz (P.) et Bouvry (P.). – Survey on Broadcast Algorithms for Mobile Ad Hoc Networks. *ACM Computing Surveys*, vol. 48.1, 2015.

14. Tanenbaum (A. S.) et Wetherall (D.). – *Computer networks*, 5th Edition. – Pearson, 2011.

15. Tseng (Y.-C.), Ni (S.-Y.), Chen (Y.-S.) et Sheu (J.-P.). – The Broadcast Storm Problem in a Mobile Ad Hoc Network. *Wireless Networks*, vol. 8.2-3, 2002.

16. Varga (A.) et Hornig (R.). – An overview of the OMNeT++ simulation environment. *International Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops*, 2008.
# Annexes

## A. Description formalisée des algorithmes

### Algorithme 1 : Sélection des relais, MPR statique

**Entrées :**

N<sub>1</sub> : ensemble (1-voisinage)

N<sub>2</sub>[] : dictionnaire noeud → ensemble, (n<sub>j</sub> ∈ N<sub>1</sub>) ↦→ {n<sub>k</sub>, ...} (2-voisinage)

1. local U ← ⋃<sub>n<sub>j</sub>∈N<sub>1</sub></sub> N<sub>2</sub>[n<sub>j</sub>] : ensemble (noeuds à couvrir);

2. local R ← ∅ : ensemble (relais);

3. **pour tous** n<sub>j</sub> ∈ N<sub>1</sub> **faire**

4. si ∃n<sub>iso</sub> ∈ N<sub>2</sub>[n<sub>j</sub>] | ∀n<sub>k≠j</sub>, n<sub>iso</sub> ∉ N<sub>2</sub>[n<sub>k</sub>] **alors**

5. R ← R ∪ {n<sub>j</sub>};

6. U ← U \ N<sub>2</sub>[n<sub>j</sub>];

7. **tant que** U ≠ ∅ **faire**

8. sélectionner n<sub>j</sub> ∈ N<sub>1</sub> maximisant |N<sub>2</sub>[n<sub>j</sub>] ∩ U|;

9. R ← R ∪ {n<sub>j</sub>};

10. U ← U \ N<sub>2</sub>[n<sub>j</sub>];

11. **retourner** R;

### Algorithme 2 : Sélection des relais, MPR alternant

**Entrées :**

N<sub>1</sub> : ensemble (1-voisinage)

N<sub>2</sub>[] : dictionnaire noeud → ensemble, (n<sub>j</sub> ∈ N<sub>1</sub>) ↦→ {n<sub>k</sub>, ...} (2-voisinage)

1. local U ← ⋃<sub>n<sub>j</sub>∈N<sub>1</sub></sub> N<sub>2</sub>[n<sub>j</sub>] : ensemble (noeuds à couvrir);

2. local R[] ← ∅ : dictionnaire indice → ensemble (relais);

3. local F ← ∅ : ensemble (relais interdits);

4. local C ← ∅ : ensemble (relais en cours);

5. local i ← 0 : scalaire (indice ensemble relais);

6. **répéter**

7. **pour tous** n<sub>j</sub> ∈ N<sub>1</sub> **faire**

8. si ∃n<sub>iso</sub> ∈ N<sub>2</sub>[n<sub>j</sub>] | ∀n<sub>k≠j</sub>, n<sub>iso</sub> ∉ N<sub>2</sub>[n<sub>k</sub>] **alors**

9. C ← C ∪ {n<sub>j</sub>};

10. U ← U \ N<sub>2</sub>[n<sub>j</sub>];

11. **tant que** U ≠ ∅ **faire**

12. sélectionner n<sub>j</sub> ∈ N<sub>1</sub> ∩ F maximisant |N<sub>2</sub>[n<sub>j</sub>] ∩ U|;

13. si N<sub>1</sub> ∩ F = ∅ **alors**

14. **retourner** R

15. C ← C ∪ {n<sub>j</sub>};

16. F ← F ∪ {n<sub>j</sub>};

17. U ← U \ N<sub>2</sub>[n<sub>j</sub>];

18. R[i] ← C;

19. C ← ∅;

20. U ← U \ ⋃<sub>n<sub>j</sub>∈N<sub>1</sub></sub> N<sub>2</sub>[n<sub>j</sub>];

21. i ← i + 1;

22. jusqu'à vrai;