46
« DE LA THÉORIE À LA PRATIQUE » THÈSE SOUTENUE PAR YANN BUSNEL SOUS LA DIRECTION DE ANNE-MARIE KERMARREC & MARIN BERTIER MARDI 18 NOVEMBRE 2008 Systèmes d’information collaboratifs et auto-organisants pour réseaux de capteurs large échelle

Systèmes d’information collaboratifs et auto-organisants pour réseaux de capteurs large échelle

  • Upload
    jerica

  • View
    16

  • Download
    0

Embed Size (px)

DESCRIPTION

Systèmes d’information collaboratifs et auto-organisants pour réseaux de capteurs large échelle. « De la théorie à la pratique » Thèse soutenue par Yann Busnel Sous la direction de Anne-Marie Kermarrec & Marin Bertier Mardi 18 Novembre 2008. Réseaux de capteurs sans-fil (RCsF). - PowerPoint PPT Presentation

Citation preview

Page 1: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

« DE LA THÉORIE À LA PRATIQUE »

T H È S E S O U T E N U E PA R

YANN BUSNEL

S O U S L A D I R E C T I O N D EA N N E - M A R I E K E R M A R R E C & M A R I N B E RT I E R

M A R D I 1 8 N O V E M B R E 2 0 0 8

Systèmes d’information collaboratifs et auto-organisants

pour réseaux de capteurs large échelle

Page 2: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

2

Réseaux de capteurs sans-fil (RCsF)

18 novembre 2008

Capteurs: entité de taille minimalisteToujours orientés réseauxDeux grandes familles :

RCsF statiques RCsF mobiles

Adapté à des environnements particuliersConception orientée application

Recherche de généricité Nécessité de modélisation

Page 3: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

3

18 novembre 2008

Thèse soutenue

Page 4: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

4

Positionnement de cette thèse

18 novembre 2008

Intérêt de la décentralisation

Une approche « de la théorie à la pratique »

Moyens de mise en œuvre Auto-organisation Collaboration

Page 5: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

5

Contribution

18 novembre 2008

Tableau des contributions

RCsF statiques

RCsF mobiles

Approche théorique

MAPP

Approche pratique

SOLIST GCP

MOTIPE ≅ PP & PC

Page 6: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

6

SUIVI ET IDENTIFICATION DE TRAJECTOIRES SUR UN RÉSEAU DE

CAPTEURS BINAIRES

18 novembre 2008

RÉSEAUX DE CAPTEURS STATIQUES

MOTI

Page 7: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

7

Contexte

Problématique : Suivi de trajectoires Un réseau de capteurs binaires statiques Un ensemble d’entités mobiles anonymes et

indiscernables

18 novembre 2008

Page 8: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

8

Plan de la partie

Modélisation du système

La problématique MOTI Un résultat d’impossibilité

Rendre MOTI résoluble Caractérisation des situations dangereuses Décentralisation des solutions

18 novembre 2008

Page 9: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

9

Caractéristiques du système

Un ensemble d’entités anonymes {o1, …, ox}Graphe de connectivité des chemins :

GCC(V,E)

18 novembre 2008

A

K

C

D

J

B

E

G

F

H

I

Page 10: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

10

Caractéristiques du système

A chaque temps t, chaque entité o occupe un sommet vi

Deux restrictions du système : Au même moment,

deux entités distinctes ne peuvent être à la même position deux entités distinctes ne peuvent se déplacer sur le même

arc

L’état du système est représenté par le vecteur St :

∀vi V, S∊ t[vi] = 1 si vi héberge une entité 0 sinon

18 novembre 2008

Page 11: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

11

Trajectoire d’une entité

Toute entité se déplace en suivant une trajectoire Décrite dans un intervalle de temps donné t⟦ i, tj ⟧ Définie par la position de l’entité à chaque temps tk

Représentée par la notation suivante (avec vtk, sommet de o à tk)

Pti,tj,o = ⟨vti, …, vtj⟩

18 novembre 2008

A

K

C

D

J

B

E

G

F

H

I Pt,t’,o = ⟨ F, E,G, J ⟩

Page 12: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

12

Problématique MOTI : l’observateur omniscient

Objectifs de MOTI : Identifier les entités Suivre leur trajectoire à travers le temps

Présence d’un observateur de St à tout temps t

Rôle : Extrapolation des trajectoires par observation

Pti,tj,o = ⟨vti, …, vtj⟩ où vtk est le sommet hébergeant l’entité identifiée par o au temps tk

18 novembre 2008

Page 13: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

13

Problématique MOTI : formalisation

MOTI (Suivi d’Entités Multiples et Identification)

Sur un intervalle donné ⟦ti, tj , la condition suivante ⟧peut-elle toujours être vérifiée par l’observateur :

∀o,∃o tels que Pti,tj,o = Pti,tj,o ?

i.e. les trajectoires observées sont identiques aux réelles ?

Difficulté : Possibilité de confusion entre deux trajectoires trop

proches18 novembre 2008

Page 14: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

14

Un résultat d’impossibilité

THEOREME :MOTI est impossible à résoudre en général…

18 novembre 2008

t0

t1

A B

C D

A B

C D

A B

C D

A B

C D

A B

C D

Page 15: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

15

Rendre MOTI résoluble ?

Recherche des caractérisations de MOTIDeux notions nécessaires :

Mouvement : Mt

Déplacements de toutes les entités entre t et t+1 Ensemble des déplacements unitaires des entités Représente l’évolution du système juste après un temps donné

Faillible ou infaillible ? En terme de mouvement, et a fortiori de situation Définition : Deux mouvements sont faillibles s’ils permettent

de passer du même état initial S au même état final S’ Définition : Un état S est faillible s’il existe des mouvements

faillibles possibles à partir de S

18 novembre 2008

Page 16: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

16

Graphe des états

Représentation de l’évolution du système avec un graphe :

18 novembre 2008

A B

C D

Page 17: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

17

Caractérisations de MOTI

18 novembre 2008

THEOREME 1 : P –résolubilitéEtant donné une trajectoire de ces entités entre ti

et tj

MOTI peut être résolu ssi ∀ t ∈ t⟦ i, tj-1 , ⟧ Mt est infaillible

Page 18: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

18

Caractérisations de MOTI

18 novembre 2008

THEOREME 1 : P –résolubilitéEtant donné une trajectoire de ces entités entre ti et tj

MOTI peut être résolu ssi ∀ t ∈ t⟦ i, tj-1 , ⟧ Mt est infaillible

THEOREME 2 : ℙ –résolubilitéPour toutes les trajectoires des entités entre ti et tj

MOTI peut être résolu ssi ∀S état possible, S est infaillible

Page 19: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

19

Une condition suffisante

Objectif : Prévention des éléments faillibles⇒ toute trajectoire est identifiable de façon déterministe

Problème de résolution ≡ Présence d’éléments faillibles

Éléments faillibles ≡ Présence de cycles dans le GCC

Comment rendre MOTI ℙ -résoluble ? Limiter les déplacements possibles Limiter le nombre d’entités pouvant

Être dans le système Se déplacer de façon concurrente à chaque temps t

18 novembre 2008

Page 20: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

20

Résumé des théorèmes caractérisant

18 novembre 2008

Caractérisation générique de mouvement infaillible Le nombre d’entités se déplaçant de façon

concurrente doit être strictement inférieur à la moitié de la longueur du cycle

Page 21: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

21

Résumé des théorèmes caractérisant

18 novembre 2008

Caractérisation générique de mouvement infaillible Le nombre d’entités se déplaçant de façon

concurrente doit être strictement inférieur à la moitié de la longueur du cycle

Caractérisation locale d’état faillible Tout sommet inoccupé d’un cycle est entouré de 2

occupés

Page 22: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

22

Résumé des théorèmes caractérisants

18 novembre 2008

Caractérisation générique de mouvement infaillible Le nombre d’entités se déplaçant de façon

concurrente doit être strictement inférieur à la moitié de la longueur du cycle

Caractérisation locale d’état faillible Tout sommet inoccupé d’un cycle est entouré de 2

occupés

Caractérisation locale de mouvement faillible Expression formelle et locale au cycle faillible du

déplacement des entités induisant une insolubilité de MOTI

Page 23: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

23

Algorithmes répartis

18 novembre 2008

Possibilité d’établir des algorithmes de Détection : identifier les situations faillibles Prévention : éviter les mouvements faillibles

Objectif : Supprimer l’intervention d’un observateur

Deux algorithmes de prévention proposés Sans information topologique

Plus producteur de messages mais sans temps d’initialisation Avec information topologique

Optimisé dans l’émission de messages mais avec détection de cycle

Page 24: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

24

« De la théorie à la pratique »

18 novembre 2008

Identification d’une problématique

Modélisation du système

Impossibilité

Caractérisation de contraintes

Formulation locale des contraintes

Conception d’algorithmes répartis

Page 25: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

25

ÉQUIVALENCE ENTRE LES PROTOCOLES ÉPIDÉMIQUES ETLES PROTOCOLES DE POPULATION

18 novembre 2008

RÉSEAUX DE CAPTEURS MOBILES

PE ≅ PP & PC

Page 26: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

26

Intuition

18 novembre 2008

Protocolesde population

Protocolesépidémiques

Cadre formelRéseaux mobiles

Équivalence ?

Relation ?

Cadre pratiqueRéseaux filaires

Page 27: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

27

Plan de la partie

18 novembre 2008

Présentation des modèles Protocoles de population et de communauté Protocoles épidémiques

Relier les deux mondes Equivalences entre les modèles

Impact mutuel entre théorie et pratique

Page 28: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

28

Protocoles de population

18 novembre 2008

Idée : un ensemble d’agents anonymes interagissent deux par deux pour un calcul global

Puissance du modèle : Arithmétique de Presburger

a2a1

Ordonnanceur

équitablea2a1

Page 29: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

29

10

000 11

1 1

Protocole de population – un exemple

18 novembre 2008

La fonction ou (primitive de diffusion) une unique transition (0,1) (1,1)

0 00 0

0 11 11 1

Page 30: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

30

Protocoles de communauté

18 novembre 2008

Extension du modèle des protocoles de population

Assigner un identifiant unique à chaque agent

Augmentation de l’espace des états Chaque agent peut en mémoriser un ensemble fini Limitation de leur utilisation à l’identification

uniquement(ne peut être utilisé afin d’augmenter la mémoire d’un agent)

Augmentation forte de la puissance du modèle De Presburger à NSPACE(n.log n)

Page 31: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

31

Protocoles épidémiques

18 novembre 2008

Analogie avec la propagation d’un virus ou rumeur

Idée : Échange périodique d’informations avec d’autres

451

2 3SélectionPair

5SélectionIn

fo

Info2Info2

Info5

Info5

SélectionInfo

miseAJour(Info2

)

miseAJour(Info5

)3 - miseAJour2 - SélectionInfo1 - SélectionPair

Page 32: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

32

Similitudes

18 novembre 2008

Anonymat dans les protocoles épidémiques ?

PP : Ordonnanceur équitablePE : Service d’échantillonnage de nœuds

Modèlesdécentralis

és

Interactions deux à deux

Capacitésfinies

Traitementdes

donnéesprédétermi

nées

Échange d’informatio

ns

Page 33: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

33

Deux classes de protocoles épidémiques

18 novembre 2008

Anonymat des nœuds possible ? Utilisation nécessaire d’identifiants dans les 3

fonctions

PENA : Protocoles épidémiques sur nœuds anonymes selectionInfo et miseAJour dépendent uniquement des

états selectionPair renvoie un nœud via une sorte de boîte

noirePENI :

Protocoles épidémiques sur nœuds identifiables Nécessité d’identification (adresse, coordonnées, etc.)

Page 34: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

34

Classification plus fine des PE

18 novembre 2008

Deux types de canaux de communication

Synchrone : Délai de transmission des messages borné Permet de tirer profit de la périodicité des PE

Asynchrone : Délai de transmission fini mais non borné Traitement des échanges par acquittement

Page 35: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

35

PENA : sans identifiant

PENI : avec identifiants

Classification fine des PE

18 novembre 2008

syncPENA asyncPENA

syncPENI asyncPENI

≻Communication

ssynchrones

Communications

asynchrones

Page 36: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

36

Analogie avec les protocoles de population

18 novembre 2008Soutenance de thèse - Yann Busnel

PENA : sans identifiant

PENI : avec identifiants

syncPENAasyncPEN

A

syncPENI asyncPENI

≻Communication

ssynchrones

Communications

asynchrones

Protocoles de

population

Protocoles de

communauté

Interactionsatomiques

Page 37: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

37

« De la théorie à la pratique »

18 novembre 2008

Identification de similitudes

Prot. de Population Prot. Épidémiques

Classifications d’ordre analogue

Équivalence de classes

Utilisation mutuelle

Page 38: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

38

Optimalité du RPS

18 novembre 2008

Théorème : L’ordonnancement uniforme implique une vitesse de convergence moyenne optimale

Existence d’un Random Peer Sampling uniforme

[Bortnikov et al. – Brahms – PODC 2008]

Optimalité dans le cas moyen par l’utilisation de ce service d’échantillonnage

Page 39: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

39

18 novembre 2008

Conclusion & Perspectives

Page 40: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

40

Conclusion

18 novembre 2008

Nécessité de conception de systèmes d’information collaboratifs et auto-organisants

pour permettre le passage à l’échelle des RCsF

Permet d’obtenir des RCsF décentralisés et autonomes, où l’information est disponible partout

Une approche de « la théorie vers la pratique » Optimalité des solutions de développement

Page 41: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

41

Rappel des contributions

18 novembre 2008

Présentation d’une contribution dans chaque classe RCsF statique : MOTI RCsF mobile : équivalence entre PE et PP & PC

Autres contributions non présentées RCsF statique : SOLIST RCsF mobile : MAPP et GCP Protocoles épidémiques : Stockage réparti de données

Page 42: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

42

Perspectives et questions ouvertes

18 novembre 2008

Perspective globale Contexte commun admis : existence de stations de

base Généricité sans perte d’optimalité

MOTI Analyse de solutions probabilistes Utilisation de protocoles épidémiques

PE ≅ PP & PC Affinement de la classification des PE Analyse des PE via MAPP

Page 43: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

43

Sélection de publications

18 novembre 2008

Journaux H. Weatherspoon, H. Miranda, K. Iwanicki, A. Ghodsi, and Y. Busnel.

Gossiping Over Storage Systems Is Practical. ACM Operating System Review, Octobre 2007.

Yann Busnel. Le modèle de pair à pair profite aux réseaux de capteurs très étendus. Interstices : Découvrir la recherche en informatique, May 2007.

Yann Busnel. Système d'information pair-à-pair pour les réseaux de capteurs larges échelles. La lettre de la Fondation Michel Métivier, 5:3–5, Octobre 2006.

Conférences internationales Yann Busnel, Marin Bertier, and Anne-Marie Kermarrec. SOLIST or or How

To Look For a Needle in a Haystack? In the 4th IEEE Internatal Conference on Wireless and Mobile Computing, Networking and Communications (WiMob'2008), Octobre 2008.

Yann Busnel, Leonardo Querzoni, Roberto Baldoni, Marin Bertier, and Anne-Marie Kermarrec. On the deterministic tracking of moving objects with a binary sensor network . In 4th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '08), Juin 2008.

Yann Busnel, Marin Bertier, Eric Fleury, and Anne-Marie Kermarrec. GCP: Gossip-based code propagation for large-scale mobile wireless sensor network. In Autonomics 2007, First International Conference on Autonomic Computing and Communication Systems, Octobre 2007.

Page 44: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

« DE LA THÉORIE À LA PRATIQUE »

T H È S E S O U T E N U E PA R

YANN BUSNEL

S O U S L A D I R E C T I O N D EA N N E - M A R I E K E R M A R R E C & M A R I N B E RT I E R

M A R D I 1 8 N O V E M B R E 2 0 0 8

Systèmes d’information collaboratifs et auto-organisants

pour réseaux de capteurs large échelle

Page 45: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

45

Classification plus fine des PE

18 novembre 2008

Deux types de canaux de communicationSynchrone :

Délai de transmission des messages borné Permet de tirer profit de la périodicité des PE

Asynchrone : Délai de transmission fini mais non borné Traitement des échanges par acquittement

x…

y

Page 46: Systèmes d’information  collaboratifs et  auto-organisants pour réseaux de capteurs large échelle

Soutenance de thèse - Yann Busnel

46

Impact pour chacun des domaines

18 novembre 2008

Network Slicing Découpage du réseau en tranches homogènes Evaluation locale de la position globale dans le

système

Possibilité de modélisation par un protocole de population Intérêt sur la preuve de la convergence de

l’algorithme Amélioration potentielle par l’utilisation d’identifiant Passage de asyncPENA à PENI