SETIT 2007

4th International Conference: Sciences of Electronic,

Technologies of Information and Telecommunications
March 25-29, 2007 – TUNISIA

Topologie Dynamique Virtuelle pour le Routage dans

les Réseaux Mobiles Ad Hoc
Kaouther Drira *, Hamamache Kheddouci* et Nabil Tabbane**
*
Laboratoire PRISMA, Université Claude Bernard Lyon 1, Bâtiment Nautibus,
843, Bd. du 11 novembre 1918, 69622 Villeurbanne Cedex France
{kdrira, hkheddou}@bat710.univ-lyon1.fr
**
Unité de recherche MEDIATRON, Ecole Supérieure des Communications de Tunis
Route de Raoued Km 3.5, 2083Cité El Ghazala Ariana, Tunisie
[email protected]

Résumé: Dans les réseaux mobiles ad hoc, la conception et la mise en oeuvre de protocoles de routage représentent un
problème complexe. Cela est du essentiellement à l’absence de toute infrastructure et de toute administration
centralisée. Une des solutions à ce problème, passe par la mise en place de topologies bien adaptées au routage dans les
réseaux ad hoc. C’est dans ce cadre que s’inscrit notre travail. En effet, nous proposons une topologie orientée routage
sur laquelle va s’appuyer ce dernier. Cette topologie intègre deux notions fondamentales: noeuds dominants et clusters.
Elle forme une structure capable de s’adapter dynamiquement aux changements de l’environnement mobile. Nous
fournissons en outre des résultats expérimentaux qui mettent en évidence l’efficacité de la topologie et du protocole de
routage, notamment pour les réseaux à forte densité de nœuds. L’algorithme a également l’avantage de supporter le
passage à l’échelle, d’être asynchrone et de minimiser le nombre de messages échangés.

Mots-clés: Graphes, Protocole de Routage, Réseaux Mobiles Ad hoc, Topologie Dynamique.

Les réseaux ad hoc et plus particulièrement la

définition d’une stratégie de routage au sein de ces
INTRODUCTION réseaux ouvrent une nouvelle piste de recherche.
Les environnements mobiles offrent aujourd'hui L’objectif consiste à résoudre le problème
une bonne alternative de communication à moindre d’acheminent de l’information entre les différents
coût et à grande flexibilité d'emploi. En effet, les nœuds du réseau d’une manière efficace. Quelques
mobiles permettent à un ensemble de machines hôtes paramètres doivent être pris en compte afin
d’être interconnectées facilement et rapidement entre d’économiser la bande passante, les ressource radio
elles avec un minimum d’infrastructure préalable, rares, etc. Le protocole conçu doit s’adapter à
voire sans infrastructure. Les réseaux mobiles ad hoc l’augmentation du nombre de participants et à leurs
sont définis comme une collection relativement dense mobilités pour qu’il puisse fonctionner correctement.
d’entités mobiles interconnectées par une liaison sans
fil, sans aucune administration ou support fixe. Une Notre point de vue sur ce problème est fondé sur
des spécificités fondamentales de ces réseaux c’est l'idée de structurer et d'organiser le réseau avant de
qu’ils doivent assurer automatiquement leur propre diffuser efficacement une information. L’idée consiste
organisation interne sachant qu’aucune administration à agir sur des paramètres pour obtenir la topologie
du réseau n’est fournie : ils doivent donc s’auto- adéquate du réseau. La présence d'une telle structure
organiser pour acheminer le trafic entre deux pourrait: diminuer l'impact de la mobilité, optimiser le
différents nœuds du réseau ad hoc. passage à l'échelle, faciliter le routage…

Un réseau mobile ad hoc peut être modélisé par un En effet, un réseau ad hoc est un réseau
graphe orienté connexe G = (V, E). V représente complètement autonome qui ne se base sur aucune
l'ensemble des nœuds (i.e. les unités ou les hôtes infrastructure existante. Afin de faciliter la
mobiles) du réseau et E modélise l'ensemble des communication et optimiser les taches qui impliquent
connections qui existent entre ces nœuds. Si e = (u,v) plusieurs nœuds à la fois, une organisation du réseau
Є E, cela veut dire que les nœuds u et v sont en s’impose. Cette organisation est garantie par la mise
mesure de communiquer directement à l'instant t. en place d’une topologie logique dans le réseau. Cette

-1-
SETIT2007

topologie permet d’imposer des règles et des leurs protocoles. Suite aux capacités limitées des
contraintes qui régissent le fonctionnement du réseau, équipements mobiles en termes de batterie, les
ainsi que la collaboration qui existe entre les premiers travaux pour le contrôle de la topologie dans
différends nœuds. les réseaux ad hoc utilisent la consommation d’énergie
comme métrique. Ces travaux sont basés
Nous allons dans une première partie présenter un
principalement sur l’ajustement de la puissance de
état de l’art des solutions existantes pour la
transmission des nœuds [RAM 00]. Une autre
construction d’arbres, de clusters, d’un sous-ensemble
approche pour contrôler la topologie du réseau ad hoc
de nœuds dominants dans un réseau ainsi que les
est basée sur l’utilisation d’un sous-ensemble de
solutions des protocoles de routage. Ensuite, la partie
noeuds pour couvrir la totalité du réseau. Ce sous-
suivante traite notre topologie orientée routage. Son
ensemble peut servir de cluster-head (super noeud)
principe est basé sur la sélection d’un sous-ensemble
dotés de fonctionnalités additionnelles. Ce type
de nœuds afin de contrôler et de maintenir la topologie
d’approche, souvent appelée ’Cluster Based Protocol’,
désirée du réseau puis un nouvel algorithme de
consiste à élire un ensemble de cluster-heads, où
groupement en cluster est appliqué. Dans la troisième
chaque noeud mobile est associé à un cluster-head.
partie, nous décrivons notre solution de routage.
D'autres approches proposent la construction d'un
Quelques résultats expérimentaux vont suivre pour
ensemble dominant connecté (connected dominating
démontrer l’efficacité de la topologie et du protocole
set: CDS) comme un backbone virtuel pour acheminer
de routage proposés. Une conclusion et des
les informations dans un réseau mobile. Cet ensemble
perspectives achèveront cet article.
dominant est une notion de la théorie de graphes. Un
sous-ensemble D de V est dit dominant si et seulement
1. Etat de l'art si tout nœud de V est soit dans D soit voisin d’un
Le routage est un des problèmes le plus difficile. nœud de D. Plus précisément, l’ensemble D est
Cependant, les solutions actuelles ne peuvent être dominant si et seulement si:
utilisées sur des réseaux à grande échelle car le trafic ∀i ∈ V i ∈ D ∧ (∃j ∈ D i ∈ N ( j )) (1)
de contrôle généré, ainsi que les tables de routage Dans un réseau ad hoc, l’ensemble dominant doit
augmentent avec la taille du réseau. De nombreux être connexe pour assurer une diffusion complète. Par
protocoles de routage ont été proposés. Ces protocoles définition, un graphe est dit connexe si tous les nœuds
peuvent être classés en trois catégories [ROY 99]: sont joignables, c’est-à-dire qu’il existe toujours un
réactif, proactif et hybride. Le réactif crée des routes à chemin constitué d’arcs reliant deux nœuds du graphe.
la demande. Un nœud initie une découverte de route Cette propriété est très importante dans le cas des
lorsqu’il doit envoyer un paquet et qu’il ne connaît ensembles dominants. En effet, elle garantit que
aucune route vers la destination. Dans l’approche chaque nœud de l’ensemble dominant peut joindre
proactive, chaque nœud connaît une route vers chaque n’importe quel autre nœud de ce même ensemble.
nœud du réseau. Quand un nœud décide de diffuser un message et si
tous les nœuds appartenant au CDS réémettent, tout le
Parmi les protocoles réactifs développés, nous
réseau est couvert. L'intérêt ici est de minimiser la
pouvons trouver : Dynamic Source Routing (DSR), Ad
taille du CDS de manière à limiter le nombre de
hoc On Demand Distance Vector (AODV), Temporally
nœuds qui retransmettent le message. De même pour
Ordered Routing Algorithm (TORA) et Associativity
le routage, diminuer la taille du CDS réduit la
Based Routing (ABR). Ces derniers protocoles
complexité de la recherche de route. Wu et Li [WU
maintiennent des architectures plates. Des protocoles
01] proposent un algorithme de marquage fournissant
proactifs ont été proposés tels que Destination
un CDS. Les nœuds sont supposés disposer d'une
Sequenced Distance Vector (DSDV), Wireless Routing
priorité qui peut être fonction de l'identifiant du nœud,
Protocol (WRP), Global State Routing (GSR),
du niveau de batterie, du nombre de voisins ou encore
Clusterhead Gateway Switch Routing (CGSR) et
aléatoire. La première étape de l'algorithme consiste à
Fisheye State Routing (FSR). Le routage dans DSDV,
marquer les nœuds possédant au moins deux voisins
FSH, GSR et WRP est basé sur une architecture plate
qui ne sont pas directement connectés. Ensuite, deux
tandis que dans CGSR, il est basé sur une architecture
règles sont successivement appliquées pour réduire la
hiérarchique. Les protocoles hybrides combinent les
taille du CDS précédemment obtenu.
dispositifs proactifs et réactifs. Comme exemple, nous
pouvons citer le protocole Zone Routing Protocol Plusieurs méthodes ont été déployées pour
(ZRP) [ZOU 02]. construire une topologie d’arbre. Dans l’article [JAV
05], les auteurs propose de construire l’arbre couvrant
Le contrôle de la topologie [WAT 01] dans les
minimal MST à partir de l’arbre couvrant minimal
réseaux ad hoc est un domaine de recherche récent. Il
localisé LMST (local minimum spanning-tree) [LI 03].
vise à maintenir une topologie adéquate en maîtrisant
Chaque nœud construit indépendamment son arbre
les liens à inclure dans le réseau. Parmi les objectifs
d'enjambement minimum local et ne maintient que les
visés, on peut citer : la réduction des interférences, la
nœuds qui sont à un houblon loin de ses voisins dans
réduction de la consommation d’énergie,
la topologie finale. En cas de l’ajout d’un nœud dans
l’augmentation de la capacité efficace de réseau…
le réseau, l’algorithme proposé achève une mise à jour
Certains travaux se basent sur ses critères pour
de MST simple à mettre en oeuvre.
proposer une construction de topologies adaptée à

-2-
SETIT2007

Un K-tree est un arbre à k feuilles, minimisant la n’apparaît pas dans sa table de voisinage (ses voisins
distance entre un nœud du réseau et un nœud de ainsi que leurs voisins), la requête est par conséquent
l’arbre. Les articles [SRI 02] et [SRI 03] traitent dans diffusée vers les CHSs qui s’occupent à la faire
un premier temps la création d’un spanning-tree dont circuler aux nœuds passerelles. Une passerelle permet
les feuilles se trouvent à la périphérie du réseau. La de diffuser l’information aux clusters voisins. Un
deuxième étape consiste à interconnecter tous les cluster maintient une structure d’arborescence utile
arbres. Chaque racine envoie un identifiant d’arbre. pour éliminer les boucles au sein du cluster. Ainsi, le
Une fois le nœud reçoit les identifiants de tous ses réseau tout en entier peut être considéré comme un
voisins, il sélectionne l’identifiant le plus fort, et en ensemble de zones reliées.
cas d’égalité, il choisi comme père l’émetteur de cet
Le principe de l’algorithme se résume comme
identifiant. Une telle solution est intéressante car elle
suit : Au début, chaque noeud dans le réseau choisi
élit des cluster-heads permettant de minimiser la
son nœud préféré (appelé aussi nœud de diffusion) : le
distance entre les cluster-heads et les membres.
nœud qui lui assure une meilleure diffusion à deux
Cependant, le nombre de cluster-heads est fixe, ce qui
sauts. Ensuite, le nœud de diffusion ayant une
défavorise l’adaptabilité de tous les nœuds du réseau.
moyenne de choix supérieure à celle de ses voisins se
De plus, des antennes directionnelles sont obligatoires
déclare comme CH. La moyenne de choix est le
pour pouvoir départager un cône de réception d’angle
rapport du nombre de nœuds dominants qui sont
α. La structure du k-tree n’est pas construite selon des
voisins à un nœud u et ont choisi ce même nœud u
principes de stabilité, elle entraîne de nombreuses
comme nœud de diffusion divisé par le nombre de
mises à jour, et des répercussions globales de
voisins. Pour les NOs, ils sont toujours rattachés à leur
changements locaux. Le trafic de contrôle est donc
nœud de diffusion. Ces nœuds ont une moyenne de
important. L’approche du k-tree core a été utilisée
choix nulle. Une forêt est alors construite en reliant les
pour un routage dense entre clusters par
CHs, les CHSs et les NOs. Après, l'algorithme
l’intermédiaire de « dense cluster gateways » (DCG)
construit la table de routage intra cluster afin de
[GHO 06]. Ce dernier est caractérisé par un nombre
donner une structure appropriée à chaque arbre. Cette
important d’arrêtes assurant la connectivité entre deux
dernière est située uniquement au niveau du CH. Pour
clusters. Ce protocole est une amélioration du routage
les CHSs et les NOs, ils maintiennent un vecteur
basé sur le clustering et utilisant le backbone k-tree
(prochain nœud qui recevra l’information) vers leur
core, Il assure en outre des meilleures performances
noeud de diffusion. L'algorithme construit ainsi la
du trafic dans le cluster et réduit le goulot
table inter cluster au niveau des nœuds de frontière :
d’étranglement dans le cluster-head. Il se base sur une
les passerelles. Il est à noter que chaque cluster a un
nouvelle méthode appelée random wheel. Son principe
identifiant unique qui est l’identité du CH. Décrivons
consiste à choisir une passerelle pour router
maintenant les différentes étapes de l'algorithme. Il se
l'information. Cette méthode présente l'avantage de
décompose en trois phases:
diminuer la probabilité de choisir une passerelle ayant
une surcharge de routage. Cependant, cette approche (1) Election du nœud de diffusion,
copie tous les inconvénients de l’approche décrite (2) Partitionnement du réseau,
dans [SRI 02] et [SRI 03]. (3) Nomination des clusters.
Ces différentes phases sont établies à base de
2. Topologie orientée routage l'information fournie par les messages HELLO.
HELLO est un message périodique échangé seulement
2.1. Description de la construction de la topologie entre un noeud et ses voisins. Ce message ne contient
L'idée principale consiste à construire un ensemble au début que l’information reliée à son identité. Le
de nœuds dominants dans le réseau. Le caractère contenu de ce message sera enrichi au fur et à mesure
dominant caractérise les nœuds dont le nombre de de son évolution dans les différentes phases de
chemin de diffusion, pour atteindre les nœuds à deux l'algorithme. Après réception des messages HELLO de
sauts, est supérieur à celui de leurs voisins. La fixation ses voisins directs, le nœud u connaît l’identité et le
des nœuds dominants représente une étape primordiale degré de ses voisins. Il enregistre ces informations
pour la construction de l’ensemble des clusters dont le dans une matrice appelée matrice de la topologie. Le
diamètre est égal au plus à quatre. En outre, chaque message HELLO forme une structure de vecteur
cluster est identifié par trois catégories de noeuds : HELLO={ZID, VID, N, DEG, BP, BN, AVRG, GTWY}:

(1) Le cluster-head (CH) est un nœud dominant et il − Zone ID number (ZID) : identité du cluster,
est chef du cluster − Vertex ID number (VID) : l’identifiant du nœud,
(2) Les cluster-heads secondaires (CHS) est un sous- − Neighbors (N) : liste des noeuds voisins,
ensemble de nœuds dominants voisins au CH. Ces − Degree (DEG) : le nombre de voisins,
nœuds se mettent d’accord sur le même CH. − Broadcast Parameter (BP) : paramètre de
(3) Les nœuds ordinaires (NO) ne sont pas des nœuds diffusion, le nombre des chemins possibles pour
dominants. atteindre ses voisins à deux sauts,
− Broadcast Neighbour (BN) : noeud de diffusion,
Le CH acquiert une connaissance totale des nœuds
le nœud préféré (ayant la valeur maximale de BP)
de son cluster. Etant donné une requête à diffuser,
pour la diffusion à deux sauts,
cette dernière doit passer par le CH. Si la destination

-3-
SETIT2007

− Average (AVRG) : rapport du nombre de nœuds 2.1.2. Partitionnement du réseau

dominants qui sont voisins à un nœud u et ont La formation du noyau du cluster est limitée
choisi ce même nœud u comme nœud de diffusion uniquement aux nœuds dominants. Dès qu‘un noeud u
divisé par le nombre de voisins, détermine son nœud préféré, il doit informer ses
− Gateway (GTWY): le champ mis à 1 si un nœud voisins de sa décision. Après avoir reçu tous les
est une passerelle sinon il est mis à zéro. messages HELLO voisins, le nœud u calcule sa
moyenne de choix (AVRG). Dans cette partie le choix
2.1.1. Calcul du BP et choix du BN du CH dépend parfois du choix des autres nœuds :
Une fois toutes les mises à jour de la matrice sont
effectuées, le nœud u calcule son BP. Trois cas − Un nœud u avec une moyenne de choix
peuvent se présenter : supérieure à celles de ses voisins se déclare
comme CH. Ses (BNs)-1 (sous-ensemble de nœuds
− Si le nœud u ne possède aucun voisin alors son dominants qui se mettent d’accord sur le même
paramètre de diffusion sera mis à zéro et il CH) vont être inclus dans le noyau du cluster. Ces
s’identifie en tant que nœud de diffusion. Dans la nœuds sont appelés CHSs. La figure 2 illustre que
figure 1, le nœud 14 n’a pas de voisin ; ce qui le nœud 15 a une variable AVRG égale à 1
implique l’absence de nœud de diffusion. Son (marquée en bleu) et supérieure à la moyenne des
champ BP contient donc son identité. nœuds {1, 3, 6, 9}. Le noyau du cluster est formée
− Si le nœud u possède un seul voisin alors son par le CH (VID=15) et les CHSs: VID = {1,3,6,9}.
unique voisin est son BN. A titre d’exemple, le
− Un nœud u peut ne pas vérifier la première
nœud 5 de la figure 1 choisit le nœud 13 comme
condition, il a au moins un nœud voisin avec une
nœud de diffusion.
− Si DEGu >1 alors le nœud u applique la formule moyenne supérieure à la sienne. Si ce nœud
suivante : voisin est un CHS, alors le nœud u se déclare
comme CH. Sinon le nœud ne fait rien, il attend
BPu = ∑ (DEG
i∈ N
i − 1) (2) un changement des messages HELLO.

Il cherche l’ensemble de ses voisins ayant la Par exemple dans la figure 2, le nœud 4 a comme
valeur maximale du paramètre BP : voisins dominants {1, 9, 24}, sa moyenne est :
BN u= { VIDi avec i/
[AVRG4 = 1 ] > [AVRG1 = 1 ] et [AVRG24 = 1 ]
∃i ∈ N , ∀j ∈ N BPi=max(BP(Nj))} (3) 2 4 4
Mais [AVRG4 = ] < [AVRG9 = 3 ]
1
2 5
Si le nœud 9 a été choisi par le nœud 15 comme un
CHS, le nœud 4 limite sa comparaison aux nœuds 1
et 24. Sa moyenne est supérieure, il se déclare donc
comme CH et ses (BNs)-1 sont définies comme CHSs.
Dans ce cas, le seul nœud qui appartient à la table de
routage intra cluster est le nœud 24. Le nœud 20
n’appartient pas au noyau du cluster puisqu’il n’est
pas un nœud dominant.

Figure 1: Election du nœud de diffusion

Dans la figure 1, le nœud 1 choisit le nœud 15

comme nœuds de diffusion, ce nœud a la valeur
maximale du paramètre BP (marquée avec la couleur
rouge et BP=18) des nœuds voisins. Si l’ensemble BN
contient plusieurs nœuds, le nœud dont le VID =1
choisit celui qui a le plus grand nombre de voisins. En
cas d’égalité, le nœud caractérisé par l’identité
maximale est privilégié. Donc, le nœud 1 choisi le
nœud 15.
Les nœuds s'échangent périodiquement les
informations des messages HELLO, et chacun Figure 2: Formation du noyau du cluster
construit une partie de l’arbre de la topologie offrant
des routes vers les autres nœuds. En effet, un nœud Dans l’étape suivante, nous avons comme entrée
choisit son meilleur chemin, ainsi que le nœud voisin les noyaux des clusters sous forme d’un ensemble
qui va être élu comme nœud de diffusion. Dans cette d’étoiles éparpillées dans le réseau. En sortie, les NOs
partie, le choix du BN se fait en une seule étape. Le vont se rattacher à leurs nœuds de diffusions (Fig. 3).
choix d’un nœud ne dépend pas du choix des autres.

-4-
SETIT2007

2.3. Construction de la table de routage inter cluster

La recherche de la destination est effectuée au
niveau du cluster. En son absence, la recherche doit se
faire dans les autres clusters. Ce sont les passerelles
qui permettent la communication entre eux. Pour
router l’information aux clusters voisins, une
passerelle consulte sa table de routage inter cluster.
Cette table contient un sous-ensemble de nœuds
voisins qui vont prendre la relève pour le routage.
Ceci présente l’avantage de minimiser le nombre
d’entrée de la table de routage, uniquement les nœuds
de frontière auront une table de routage inter cluster.
Une passerelle regroupe dans sa table de routage tous
les voisins appartenant à d’autres clusters ayant
Figure 3: Partitionnement du réseau
comme champ GTWY=1. Il peut exister plus qu’un
2.1.3. Nomination des clusters nœud avec une même identité de zone. Pour minimiser
Le but de cette partie est de correctement répartir d’avantage la taille de la table, une passerelle
les différents noeuds afin de définir les clusters. Ceci maintient un seul nœud menant à un cluster voisin.
doit être mis en oeuvre de telle sorte que chaque nœud Cette sélection privilégie les nœuds situés en haut de
dans le réseau n'appartient qu'à un seul cluster. Pour la hiérarchie. Si deux nœuds ou plus appartiennent à la
tout nœud du réseau qui se déclare comme CH, son même hiérarchie, le choix se base sur le nœud ayant
champ ZID prend la valeur de son VID. Pour les autres un degré maximal. En cas d’égalité du degré, c’est le
nœuds (les CHSs et les NOs), leurs champs ZID nœud dont sa VID est maximale qui sera inclut dans la
prennent une valeur égale à celle de leurs nœuds de table de routage inter cluster.
diffusions. En effet, l’attribution d’un numéro à un
cluster se fait d’une façon hiérarchique : tout d’abord, 3. Conception du protocole de routage
les CHs définissent les valeurs de leurs champs ZID
Cette section décrit notre algorithme de routage se
qui seront copiées à la suite par leurs voisins. Cette
base sur la topologie construite dans la section
procédure sera itérée sur les voisins des voisins afin
précédente. Lorsqu’un paquet arrive à l’agent de
d’aboutir à un ensemble de zone formant une forêt.
routage, ce dernier vérifie si la destination existe ou
non dans la table de voisinage à un et à deux sauts -
2.2. Maintenance des clusters
chaque nœud dans le réseau à une connaissance à deux
Les changements topologiques d’un réseau mobile sauts :
ad hoc peuvent se résumer en trois différents types :
allumage, arrêt et mouvement de l’hôte mobile. − Si la route menant au destinataire est trouvée,
l’agent envoie une réponse (route_reply) qui
En ce qui concerne les nœuds de diffusion, une suivra le chemin inverse pour informer le nœud
mise à jour automatique de leurs valeurs est réalisée source du chemin complet menant au destinataire.
chaque fois qu’un nœud de diffusion modifie son − Si la destination n’apparaît pas, l’agent essaye
champ BN suivant les messages HELLO de ses alors de trouver une route. Par conséquent, il
voisins. Par conséquent, nous n’avons pas besoin dans envoie sa requête (route_request) en appliquant
ces conditions d’un algorithme de maintenance pour soit la première phase correspondant au routage
ces nœuds de diffusion. Le défi ici consiste à définir intra cluster soit la deuxième phase correspondant
l’instant de la mise à jour du CH et à recalculer ses au routage inter cluster. Ceci ne peut avoir lieu
informations au niveau du cluster. qu’après avoir ajouté ce nœud intermédiaire à la
− s’il y a ajout d’un nouveau nœud dans le réseau, requête et enregistré cette requête dans sa
le CH compare la valeur de sa moyenne mémoire tampon. Chaque nœud ayant reçu la
(AVRGCH) à celle du nouveau nœud (AVRG’). requête (route_request), maintient un vecteur
− Si AVRGCH > AVRG’, le CH ajoute cette inverse qui indique le chemin de la réponse. Un
nouvelle entrée dans sa table de routage intra tel vecteur n’est activé que s’il reçoit un
cluster. route_reply associé à cette même requête. Si après
un certain temps, le vecteur n’est pas activé, il est
− Sinon il initialise son état, son identité de
automatiquement supprimé de sa mémoire
zone est vide.
tampon ainsi que la requête associée.
− Une entrée de sa table de routage intra cluster est
supprimée tant qu’elle n’apparaît pas dans son Le route_request forme une struture de vecteur ;
voisinage. route_request={ SRC, DEST, IN, phase}avec :
− Si AVRGCHS devient supérieure à AVRGCH, alors
− le champ SRC : l’identité du nœud source,
le CH initialise son état.
− le champ DEST : l’identité du nœud destinataire,
Les CHSs et les NOs seront automatiquement mis − le champ IN : les identités des nœuds
à jour dés qu’il y a une mise à jour du CH. intermédiaires. Chaque nœud enregistre son
identité avant de la diffuser,

-5-
SETIT2007

− le champ phase : indique la phase du routage.

Phase=1 pour le routage intra cluster et phase=2
pour le routage inter cluster.
Les entrées enregistrées peuvent être changées
durant la propagation de la requête. Cette procédure
permet de trouver le chemin le pus court (shortest path
routing SPR). Si un nœud voisin (respectivement un
nœud à deux sauts) apparaît dans le champ IN, mais il
n’est pas le dernier (respectivement l’avant dernier) Figure 4 : Exemple de routage (phase 1)
nœud qui a envoyé la requête, une modification visant
l’amélioration du chemin peut être appliquée dans ce 3.1.2. Phase du routage inter cluster
cas. Par conséquent, l’agent supprime tous les Cette phase permet à un nœud source (ou
successeurs de ce voisin (respectivement ce voisin à intermédiaire) d’atteindre les nœuds des clusters
deux sauts). Le route_reply a presque la même voisins.
structure que le route_request, sauf qu’il n’utilise pas − Le CH consulte sa table de routage intra cluster et
le dernier champ, route_reply={ SRC, DEST, IN}. il envoie sa requête (SRC, DEST, IN, 2). Si son
Cette réponse suit le vecteur inverse enregistré au champ GTWY =1, il consulte sa table inter cluster
niveau du nœud. pour envoyer sa requête aux différentes entrées.
Cette requête est enregistrée dans le tampon.
3.1. Route_request − Les CHSs dans cette phase qui reçoivent le
message envoyé par le CH enregistrent cette
3.1.1. Phase du routage intra cluster requête. Puis ils envoient la nouvelle requête
Cette phase permet à un nœud source de trouver la (SRC, DEST, IN, 1), aux nœuds passerelle en
destination à l’intérieur du cluster tant que le nœud consultant leur table de routage inter cluster. La
destinataire ne se trouve pas à deux sauts de lui. C’est requête (SRC, DEST, IN, 2) est envoyée aux NOs
le CH qui a une connaissance totale du cluster, toute dont leurs champs GTWY=1 et appartenant au
requête doit obligatoirement passer par lui, il vérifie si même cluster.
le nœud destinataire se trouve dans le cluster. − Si un NO est une passerelle, il consulte sa table de
Plusieurs cas peuvent se présenter : routage inter cluster pour envoyer sa requête aux
− Si le nœud émetteur (ou un nœud intermédiaire) clusters voisins.
est un NO (respectivement un CHS), nous n’avons L’exemple fourni dans la figure 5 (a) traite un
pas encore une connaissance totale du cluster, une exemple de routage. En effet, le CH enregistre la
requête est envoyée donc à son nœud de diffusion requête dans sa mémoire tampon, crée un vecteur de
sous la forme de (SRC, DEST, IN, 1), tant que la réponse qui mène au dernier nœud situé dans la liste
destination n’apparaît pas. L’enregistrement de des nœuds intermédiaires de la requête, puis envoie (3,
cette requête dans la mémoire tampon du nœud 12, 3-15, 2) aux CHSs qui sont {1, 3, 6, 9}. Ces CHSs
est relié au type du nœud : créent à leur tour un vecteur de réponse, enregistrent
− Pour les nœuds passerelle, la requête est cette requête puis l’envoient aux autres nœuds
envoyée à son nœud de diffusion sans passerelles appartenant aux autres clusters (Fig. 5 (b)).
l’enregistrer dans sa mémoire tampon. Pour
éviter les boucles infinies dans le réseau, un − Le nœud 1 envoie (3, 12, 3-15-1, 1) aux nœuds 4
nœud recevant la même requête (c'est-à-dire et 21,
provenant d’une même source et envoyée − le nœud 9 envoie (3, 12, 3-9, 1) aux nœuds 4 et 11
vers une même destination) ne la transmet (dans ce cas une modification au niveau de la
pas. Dans la deuxième phase, ce nœud requête a été initié par le nœud 9) et
passerelle va servir pour envoyer la requête − le nœud 3 envoie (3, 12, 3, 1) au nœud 11.
aux clusters voisins.
Une fois la requête arrive aux nœuds (4, 21, 11),
− Si le nœud n’est pas une passerelle, la
ces derniers finissent par se comporter comme des
requête sera enregistrée dans le tampon.
nœuds émetteurs et les deux phases du routage se ré-
− Si le nœud émetteur (ou un nœud intermédiaire) exécutent.
est un CH et la destination n’apparaît pas dans le
cluster, la recherche de la destination dans ce cas
va se faire dans les autres clusters.
Par exemple, dans la figure 4, si on suppose que le
nœud 3, qui est un CHS veut atteindre le nœud 12. Il
doit envoyer alors une requête (3, 12, 3,1) vers son
nœud de diffusion (VID=15), sans l’enregistrer dans sa
mémoire tampon. (C’est un nœud passerelle). Le
nœud 15 est un CH et la destination n’apparaît pas
dans sa table de voisinage, une phase de routage inter Figure 5 (a) : Exemple de routage (phase 2)
cluster est nécessaire.

-6-
SETIT2007

Le taux de mobilité est un facteur très important

dans le processus de simulation dans les réseaux ad
hoc, il nous permet de bien évaluer et interpréter les
résultats de la simulation. Le calcul du taux de
mobilité est basé sur la vitesse et le mouvement des
noeuds mobiles. « Si plusieurs noeuds se déplacent
pendant un laps de temps, alors la mobilité est la
moyenne du changement de la distance entre tous les
noeuds pendant cette période » [LAR 98]. Il existe
trois types majeurs de mobilité (Mob): mobilité faible
Figure 5 (b) : Exemple de routage (phase 2) 0 < Mob ≤ 3, mobilité moyenne : 3 < Mob < 8,
mobilité élevée : Mob ≥ 8
3.2. Route_reply
Le nœud destinataire doit recevoir la requête afin 4.2. Résultats préliminaires
de pouvoir y répondre. C’est lui l’initiateur de la Nous présentons les simulations qui illustrent les
première réponse route_reply. Si un nœud reçoit un résultats préliminaires des tests du protocole. Les
route_reply alors il insère son identité au niveau du simulations montrent une allure décroissante des
champ NI de la réponse. Cette requête sera à la suite courbes pour différents scénarios de mobilité. Nous
envoyée au prochain nœud, qui représente l’entrée avons évalué le comportement de la topologie face à
enregistrée au niveau de son vecteur. l'augmentation de la connectivité ou de la densité.
Le premier aspect que nous notons est la
4. Simulation diminution du nombre de nœuds dominants et des
La simulation permet de tester à moindre coût les clusters en fonction de l’augmentation de la densité du
nouveaux protocoles et d'anticiper les problèmes qui réseau. Dans la figure 6, nous remarquons une baisse
pourront se poser dans le futur afin d’implémenter la du nombre de nœuds dominants pour les trois courbes
topologie la mieux adaptée aux besoins. Network de la mobilité. Ce nombre diminue de 10 à 4 si nous
simulator NS [FAL 03] est un simulateur qui permet à augmentons la connectivité de 20% à 80%. Cette
l'utilisateur de définir un réseau et de simuler des diminution est ainsi linéaire avec l'augmentation de la
communications entre les noeuds de ce réseau. NS v2 densité, ceci peut s’expliquer par nos meilleurs choix
utilise le langage OTCL (Object Tools Command des métriques utilisées. Les mêmes remarques
Language), dérivé objet de TCL. À travers ce langage, s’appliquent sur la figure 7 qui montre la diminution
l'utilisateur décrit les conditions de la simulation : du nombre de clusters. En conséquence, cette
topologie du réseau, caractéristiques des liens topologie s'adapte bien avec les réseaux ayant une
physiques, protocoles utilisés, communications... La forte densité de noeuds. Le nombre de noeuds
simulation doit d'abord être saisie sous forme de dominants et de clusters est plus réduit permettant
fichier texte que NS utilise pour produire un fichier d’optimiser la diffusion dans le réseau.
trace contenant les résultats. NS est fourni avec
différents utilitaires dont des générateurs aléatoires et 12
un programme de visualisation : Nam. 10
Nombre de BN

8
Mob faible
4.1. Étude de la simulation 6 Mob moyenne
Nous avons mené certaines simulations pour 4 Mob élevée
déterminer l'efficacité de notre topologie. Ces 2
simulations ont été effectuées en utilisant NS2 Le but
0
principal de ces simulations est d'analyser le
0 50 100
comportement de notre protocole dans divers
Connectivité (% )
scénarios de simulation. Les noeuds se déplacent selon
le modèle de mobilité RWP (Random Waypoint
Model) [BET 04]. Généralement, c'est le modèle de Figure 6: Nombre moyen de noeuds dominants
mobilité le plus utilisé dans ces types de simulation. La figure 6 et 7 montre que le nombre de nœuds
Dans ce modèle, le mouvement des nœuds est dominants et de clusters est légèrement affecté par le
typiquement aléatoire. En effet, la destination et la facteur de la mobilité, pour une valeur fixe de la
vitesse de chaque nœud mobile, désirant se déplacer, connectivité. Normalement, l’accroissement de la
est aléatoire, et est limité à un intervalle bien mobilité signifie plus de changements topologiques,
déterminé. Après son déplacement le nœud mobile d’où augmentation du nombre de messages de mise à
s’immobilise pour un temps fini, puis se déplace à jour. Nous pouvons conclure que notre topologie
nouveau de la même manière que la première fois, et réduit nettement l'impact de mobilité. Notre protocole
cela jusqu'à la fin de la simulation. Notons que le fonctionne très bien, il a fait preuve, dans l’ensemble,
modèle RWM reflète bien les caractéristiques des de bonnes performances pour des mobilités élevées,
réseaux ad hoc, il offre une mobilité aléatoire aux dans un temps raisonnable. Notre topologie s'adapte
nœuds mobiles appartenant au réseau ad hoc. aux différents scénarios de mobilité sans augmentation

-7-
SETIT2007

du trafic de contrôle, nous utilisons seulement les REFERENCES

messages HELLO. Ainsi, la mise à jour de la topologie
[BET 04] Bettstetter, C. et col., 2004. Stochastic properties
est généralement exécutée automatiquement. Dans of the random waypoint mobility model. Dans
notre protocole le nombre de message de contrôle est ACM/Kluwer Wireless Networks: Special Issue on
constant, même lorsque la mobilité est extrêmement Modeling and Analysis of Mobile Networks
élevée.
[FAL 03] Fall, K. et Varadhan, K., 2003. The ns Manual
7 (formerly ns Notes and Documentation). The VINT
6 Project, disponible dans
Nomber de cluster

5
http://www.isi.edu/nsnam/ns/doc/
Mob faible
4 [GHO 06] Ghosh, R.K. et col., 2006. Dense cluster gateway
Mob moyenne
3
Mob élevée
based routing protocol for multi-hop mobile ad Hoc
2 networks. Ad hoc Networks.
1
[JAV 05] Javier, F. et col., 2005. Finding minimum
0 transmission radii for preserving connectivity and
0 50 100
constructing minimal spanning trees in ad hoc and
Connectivité (% )
sensor networks. Journal of Parallel and Distributed
Computing.
Figure 7: Nombre moyen de clusters
[LAR 98] Larsson, T. et Hedman, N., 1998. Routing
protocols in wireless ad-hoc networks-a simulation
5. Conclusion study. Master's thesis, Luleå University of Technology,
Dans cet article, nous avons proposé un nouvel Stockholm.
algorithme distribué pour le routage dans les réseaux [LI 03] Li, N. et col., 2003. Design and Analysis of an MST-
mobiles ad hoc. Il calcule un ensemble de noeuds Based Topology Control Algorithmin. Dans Infocom'03,
dominants qui fournissent la topologie adaptée pour le proceedings of the IEEE Infocom.
routage. Notre principale contribution a été de
[ROY 99] Royer, E.M., et Toh, C.K., 1999. A review of
proposer une métrique et un algorithme qui permette
current routing protocols for ad hoc mobile wireless
d’auto-organiser un très grand nombre de nœuds ad networks. Dans IEEE Personal Communications
hoc. La métrique est calculée à la base du nombre de magazine.
chemins, à deux sauts, possible pour la diffusion à
partir de ce nœud. En outre, dans l'algorithme proposé [RAM 00] Ramanathan, R. et Rosales-Hain, R., 2000.
une nouvelle construction de clusters est développée. Topology Control of Multihop Wireless Networks Using
Une telle structure s'adapte dynamiquement aux Transmit Power Adjustment. Dans Infocom’00,
changements de l'environnement. Elle fournit les plus proceedings of the IEEE Infocom.
courts chemins et une mise à jour rapide. [SRI 02] Srivastava, S. et Ghosh, R.K., 2002. Cluster based
Pour démontrer l’efficacité de notre proposition, routing using a k-tree core backbone for mobile ad hoc
networks. Dans DIAL M’02, proceedings of the 6th
des simulations ont été effectuées. Les premiers
international workshop on Discrete algorithms and
résultats prouvent que la topologie est bien adaptée
methods for mobile computing and communications.
même pour des réseaux à forte densité de noeuds ce
qui optimise la diffusion dans le réseau. L’algorithme [SRI 03] Srivastava, S. et Ghosh, R.K., 2003. Distributed
a également l’avantage de supporter le passage à algorithms for finding and maintaining a k-tree core in a
l’échelle et de minimiser le nombre de messages dynamic network. Information processing letters.
échangés. [WAT 01] Wattenhofer, R. et col., 2001. Distributed
Cette première partie de l’étude a permis de poser Topology Control for Power Efficient Operation in
les bases de notre protocole de routage, mais des Multihop Wireless ad hoc Networks. Dans Infocom’01,
améliorations et des évolutions sont envisageables. proceedings of the IEEE Infocom.
Les résultats obtenus montrent que notre système [WU 01] Wu, J. et Li, H., 2001. A dominating-set-based
actuel impose le passage de la requête par tous les routing scheme in ad hoc wireless networks. Special
clusters du réseau, surtout pour le traitement de deux Issue on Wireless Networks Telecommunication
nœuds (source/destination) localement différents. Systems Journal.
Nous envisageons introduire un routage probabiliste
[ZOU 02] Zou, X. et col., 2002. Routing Techniques in
afin de privilégier certains clusters dans la réception
Wireless Ad hoc Networks - Classification and
de la requête ce qui permet de mieux optimiser la
Comparison. Dans SCI’02, Proceedings of the Sixth
diffusion dans le réseau. Une simulation plus World Multiconference on Systemics, Cybernetics, and
approfondie du protocole est envisageable, car elle Informatics.
permettrait d’évaluer le protocole dans des
environnements dynamiques de plus grande échelle.
Ainsi, une comparaison avec les autres protocoles de
routage existants permettrait de mieux évaluer le
protocole.

-8-