1

Nathalie Mitton – Anthony Busson - Éric Fleury

Laboratoire CITI – INSA de Lyon – INRIA

Auto-organisation dans les réseaux ad hoc

Algotel 2004 - Batz/mer – 28 mai 2004

2

La problématique

Un réseau ad hoc est un réseau mobile sans infrastructure.

Les protocoles de routage « à plat » ne permettent pas le passage à l’échelle.

Une solution le routage hiérarchique avec formations de clusters.

3

Le routage hiérarchique

•Principe:

• partitionne le réseau en regroupant des nœuds proches géographiquement en « clusters » .

• Les clusters sont identifiés par leur tête de cluster dite « clusterhead »

4

Le routage hiérarchique

•But:

• permettre le passage à l’échelle en limitant les données à stocker: les nœuds ont des informations complètes sur leur groupe et partielles pour les autres groupes.

• peut éventuellement servir pour l’application de différents services par groupe

•L’organisation en clusters doit être :

• distribuée et générer le moins de trafic possible

• stable face à la mobilité des nœuds afin de limiter le trafic de maintenance et de reconstruction

6

État de l’art du routage hiérarchique

• Dans les solutions existantes:

- élection des chefs de clusters sur différents critères : plus fort degré, plus faible mobilité, plus faible identifiant, une somme pondérée de plusieurs paramètres.

- clusters homogènes limités par des critères « absolus »: nombre de nœuds dans un cluster, diamètre ou rayon de cluster.

- tous les nœuds sont pris en compte

• Mais :

- pas toujours adapté à un grand nombre de nœuds

- un nœud peu mobile peut être isolé

• Dans tous les cas, chaque nœud calcule localement sa métrique et la diffuse à ses voisins afin de savoir lequel parmi eux sera le chef de cluster.

7

Nos objectifs

• Proposer une méthode de formation de clusters :– non basée sur des critères « fixes »– distribuée et asynchrone

afin de générer le moins de trafic possible lors de la formation

– qui favorise le trafic local– qui s’adapte aux changements de topologie– qui propose une organisation des nœuds stable face à la mobilité des nœuds (afin de limiter le trafic de

reconstruction)

favoriser la stabilité des nœuds lors de l’élection des chefs de clusters

permettre de lisser les petits changements de topologie

ne pas prendre en compte les nœuds trop mobiles lors de la phase d’élection

8

Notre métrique de découpage hiérarchique

– la métrique de densité– analyse– la formation des clusters– exemple

9

Notre métrique: la densité

)()(

),()(

uu

kvudVvu

kk

k

= ( 6 = ( 6 + 4 )= ( 6 + 4 )/6 = 10/6

10

Pour chaque nœud:

- Découverte de son voisinage (paquets Hello)

- Vérification de la constance de son voisinage

si trop mobile, le nœud ne participe pas à la formation et quitte l’algorithme

- Calcul de sa densité

- Élection du clusterhead : rattachement à son voisin de plus forte densité voire à soi-même

-En cas de conflit, on prend comme autre critère:

- priorité à l’ancien père dans l’arbre de rattachement si concerné

- puis la mobilité (voisin le plus stable)

- puis l’ID

Notre algorithme: formation des clusters

densité = 4/3

11

Notre contribution: exemple

Trop mobile

12

Notre contribution: exemple

Trop mobileCusterhead

13

Analyse: densité moyenneSi on suppose les nœuds de rayon de voisinage R et répartis avec un

processus de Poisson d’intensité :

• On ramène le calcul au calcul de la proba qu’un point donné soit chef de cluster à l’aide du théorème de Campbell.

• Si v est un voisin de u à distance r: le nombre moyen de liens entre v et un autre voisin de u revient au calcul du nombre d nœuds dans A(r) :

Idée de la preuve:

42

22 2

arccos2)( rRr RrRrA

rUV

14

Analyse: nombre moyen de clusters

15

Simulation

16

Exemples d’organisations obtenues

1000 nœuds – rayon 0.1 3000 nœuds – rayon 0.1

17

Théorie – Simulations

18

Ce que l’on constate:

Notre métrique se trouve être satisfaisante vis à vis des critères suivants:

• Formation de clusters distribuée et sans générer trop de trafic

• Nombre de clusters formés qui n’explose pas avec le nombre de nœuds

• Formation stable face à la mobilité des nœuds (pourcentage de réélection des chefs après mouvements plus important que pour d’autres métriques)

• Formation stable face à l’ajout ou la suppression de nœuds (pourcentage de réélection des chefs après ajouts plus important que pour d’autres métriques)

19

Conclusion et perspectives

20

Conclusion et perspectives

Ce que nous avons proposé:

une nouvelle métrique distribuée pour organiser un réseau ad hoc ou de senseurs sur de grandes échelles.

avec des résultats analytiques et de simulation satisfaisants

Nos perspectives :

retrouver analytiquement les résultats de stabilité obtenus par simulation

appliquer un processus de localisation sur cette organisation

proposer des protocoles de routage inter et intra clusters

21

Merci de votre attention .Des questions ?