22
ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – [email protected] PFE

ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – [email protected] PFE

Embed Size (px)

Citation preview

Page 1: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP Another Nice Clustering Protocol

27 Juin 2012Benoit Clair – [email protected]

PFE

Page 2: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Plan de la présentation

oHypothèses de travail et cadre de l’étude

oANCP, heuristiques de fonctionnement

oRésultats

2

Page 3: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Cadre de l’étudeoDesign d’un réseau Ad Hoc communicant

oDes nœuds se déploient en opération et doivent rapidement être opérationnelsoCas d’application: déploiement d’équipes de secours

• Situations complexes (pas d’architecture existante, apport en électricité hasardeux)

• Des nœuds formant des équipes aux intérêts variés (e.g. déblaiement et secouristes)

• Des nœuds aux capacités hétérogènes (e.g. véhicules et piétons)

oUne organisation en clusters est une manière d’augmenter les performances

3

Page 4: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Hypothèses de travail - Topologie

oRéseau Ad Hoc totalement autonomeo2 types de nœuds

• Les nœuds privilégiés (PN)• Les nœuds réguliers (RN)

oUn PN et un ensemble de RN forment un groupe opérationnel (GO)

oLes nœuds communiquent entre eux, majoritairement entre membres d’un GO

4

Page 5: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Hypothèses de travail - Ressources disponibles

oChaque nœud dispose d’une interface radio utilisant un système combinant TDMA & FDMA

oOn dispose d’un pool de fréquences Nb_Freq• Nb_Freq << Nb_Nodes• Nb_Freq < Nb_GO

oLe débit des nœuds est d’environ 1Mbits/s

oLes liaisons radio sont bilatérales et fiables, i.e. les nœuds à portée peuvent communiquer

5

Page 6: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Hypothèses de travail - Hypothèses génériques

oLes nœuds arrivent de manière sporadique et aléatoire

oIls se déplacent par groupe opérationnel (le PN dirige le mouvement)

oLa phase de synchronisation (requise entre autres par l’utilisation du TDMA)

• Est utilisée pour la découverte de voisinage • Peut être utilisée pour échanger de l’information

oUne phase d’initialisation, e.g. où les nœuds sont immobiles, est envisageable

6

Page 7: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Problématique

oOrganiser la mise en clusters et la répartition des ressources (i.e. fréquences)

oProduire un protocole fiable, i.e. supportant des scenarii différents.

oLes critères de performances sont: • La cohérence spatiale, les membres d’un GO doivent

appartenir au même cluster et les PNs sont censés être CH• Le coût de signalisation (5% de la BP max)• La réactivité

7

Page 8: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Principe général

oLes fréquences sont distribuées en même temps que la mise en clusters

oOn crée une trame virtuelle dédiée au protocole

oCette trame comporte deux sous-trames

• Une dédiée aux PNs qui envoient un beacon• Une dédiée aux connexions

oUne fréquence est dédiée à la signalisation. Les autres allouées aux clusters

8

Page 9: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Structure de la trame

9

Beaconing stage Connection stage

Chaque PN a un slot qu’il utilise pour envoyer un PN-INFO

PN 1

PN 2

PN 3

PN 4 […] […]

La sous-trame de connexion est subdivisée en sous-ensembles de 3 slots, les fenêtres des connexions

Page 10: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Rejoindre un cluster

10

CH

RN

RN

RN

RN

RN

Page 11: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Comportement d’un RN

11

Page 12: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Comportement d’un PN

12

Page 13: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Sélection d’un clusterhead

oUn nœud obtient des informations sur les clusters avoisinant à travers les beacons transitant sur le réseau

oPour sélectionner un cluster il applique les critères suivants1. Il cherche à rejoindre son PN2. Il cherche à rejoindre le cluster contenant le plus grand nombre de nœuds

de son GO3. Il sélectionne le cluster qui possède la plus grande capacité

oEn cas d’égalité, la fonction de coût permet de départager deux clusters

13

Page 14: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Messages

oPN-INFO

oJOIN-REQ

14

[…]

Page 15: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Ordonnancement

15

Beaconing stage Connection stage

Chaque PN a un slot qu’il utilise pour envoyer un PN-INFO

PN 1

PN 2

PN 3

PN 4 […] […]

La sous-trame de connexion est subdivisée en sous-ensembles de 3 slots, les fenêtres des connexions

L’algorithme d’ordonnancement doit donc, pour une fenêtre de connexion donnée, déterminer le nœud autorisé

Page 16: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

ANCP – Ordonnancement

16

oLes nœuds sont discriminés selon leurs GO et leurs ID

oAu sein d’un GO les nœuds disposent d’ID virtuels linéaires

Page 17: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Implémentation et expérimentations

oSinalgo• Outil de théorie des graphes• Pensé pour prototyper rapidement des

protocoles• Simule simplement les couches basses

(messages par pile)

oMesures • Distribution géographique des groupes opérationnels• Temps de convergence• Nombres de messages utilisés

o Des scenarii différents (e.g. pas de mobilité, vitesses différentes)

17

Page 18: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Distribution des noeuds

18

Page 19: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Temps de convergence (10 fenêtres de connexion)

19

Page 20: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Messages requis pour la convergence

20

Page 21: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

Conclusion et future work

oNous disposons d’une solution efficace qui répond aux contraintes de réactivité et d’économie de bande passante

oPour aller plus loin (entres autres)1. Utiliser une « vraie » couche MAC2. Prendre en compte les interférences à deux sauts3. Dégrader les liens radios4. Réutiliser certains slots inutilisés pour optimiser la réactivité

21

Page 22: ANCP Another Nice Clustering Protocol 27 Juin 2012 Benoit Clair – benoit.clair@insa-lyon.fr PFE

QUESTIONS, DISCUSSIONS …

22