Consensus de moyenne dans les réseaux de capteurstheses.insa-lyon.fr/publication/2009ISAL0078/these.pdf · 2016-01-11 · THÈSE présentée pour obtenir le grade de docteur de l’Institut

THÈSE

présentée pour obtenir le grade de docteur

de l’Institut National des Sciences Appliquées de Lyon

Spécialité : Informatique

par

Nicolas MARÉCHAL

Consensus de moyennedans les réseaux de capteurs :Applications et optimisation

A soutenir devant le jury composé de :

Rapporteurs David Simplot-RylCédric Richard

Examinateurs Eric FleurySergio Barbarossa

Directeur de thèse Jean-Marie GorceCo-encadrant CEA Jean-Benoît Pierrot

Institut National des Sciences Appliquées de Lyon

2

3

Remerciements

4 REMERCIEMENTS

5

Sommaire

Remerciements 3

Glossaire et abréviations 9

Conventions 11

Introduction 13

1 Algorithmes de consensus de moyenne 171.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2 Hasardisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.1 Hasardisation temporelle . . . . . . . . . . . . . . . . . . . . . . . . . 191.2.2 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.2.3 Condition et critères de convergence . . . . . . . . . . . . . . . . . . . 21

1.3 Solutions P2P en temps fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.3.1 Cas des pondérations standard . . . . . . . . . . . . . . . . . . . . . . 231.3.2 Faisabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.3.3 Hasardisation et universalité . . . . . . . . . . . . . . . . . . . . . . . 251.3.4 Sous-optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.4 Caractérisation et accélération des performances . . . . . . . . . . . . . . . . . 271.4.1 Méthodes idéales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.4.2 Heuristiques topologiques directes . . . . . . . . . . . . . . . . . . . . 281.4.3 Caractérisation à haute densité . . . . . . . . . . . . . . . . . . . . . . 321.4.4 Écoute passive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1.5 Interaction asymétriques & convolutions de Bernoulli . . . . . . . . . . . . . . 351.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2 JEGA 412.1 Estimation et consensus de moyenne conjoints . . . . . . . . . . . . . . . . . . 41

2.1.1 Processus d’estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 422.1.2 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 432.1.3 Convergence au premier ordre . . . . . . . . . . . . . . . . . . . . . . 442.1.4 Convergence au second ordre . . . . . . . . . . . . . . . . . . . . . . 44

2.2 Simulation et analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.2.1 Conditions de simulations . . . . . . . . . . . . . . . . . . . . . . . . 472.2.2 Résultats et heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . 47

6 SOMMAIRE

2.2.3 Comparaison avec un algorithme en deux phases . . . . . . . . . . . . 492.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3 Une application à la synchronisation fine 513.1 Algorithme bavard de synchronisation . . . . . . . . . . . . . . . . . . . . . . 52

3.1.1 Arbres recouvrants et notations de la théorie des graphes . . . . . . . . 523.1.2 Mesure de dérive d’horloge et estimation . . . . . . . . . . . . . . . . 523.1.3 DV-Hop et liens arborescents . . . . . . . . . . . . . . . . . . . . . . . 533.1.4 Correction de dérive de la référence . . . . . . . . . . . . . . . . . . . 543.1.5 Algorithme complet . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2 Résultats et performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.2.1 Hypothèses de simulation . . . . . . . . . . . . . . . . . . . . . . . . 563.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.2.3 Optimisation et robustesse . . . . . . . . . . . . . . . . . . . . . . . . 57

3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4 Asynchronie et régularisation 614.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.2 Minimisation distribuée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.3 Spécificité du cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . 684.4 Type de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.5.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724.5.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5 Une application à la cartographie 775.1 Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.2 Régression au sens des moindres carrés . . . . . . . . . . . . . . . . . . . . . 785.3 Régularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.3.1 Fonction de coût/potentiel . . . . . . . . . . . . . . . . . . . . . . . . 795.3.2 Minimisation par la méthode de Jacobi . . . . . . . . . . . . . . . . . 805.3.3 Bornes de précision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.3.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Conclusion et perspectives 87

A Rappels : Graphes & Probabilités modernes 89A.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89A.2 Axiomatique de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

B JEGA : compléments de preuves 93

SOMMAIRE 7

C Convergence d’un opérateur convolutif 97C.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97C.2 Limite convolutive nulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Références personnelles 101

Bibliographie 103

8 SOMMAIRE

9

Glossaire et abréviations

ACM Algorithme de Consensus de Moyenne.CS Compressed Sensing/Sampling. Echantillonnage parcimonieux.DV-Hop Distance-Vector Hop. Protocole de positionnement basé sur des propriétés de routage.EQM Erreur Quadratique Moyenne.IMT Infinite Monkey Theorem.JEGA Joint Estimation and Gossip Averaging.LMS Least Mean Squares. Moindres CarrésMET Multiplicative Ergodic Theorem.OFDM Orthogonal Frequency Division Multiplexing.PLL Phase Lock Loop. Boucle à verrouillage de phaseRDC Réseau de capteur.RDH Rapport de dérives d’horloges.RF RadiofréquenceSDP Semipositive Definite Programming. Problèmes/méthodes d’optimisation sur l’espace

des matrices définies semi-positives.TDMA Time Division Multiple Access.UWB Ultra Wide Band.WSN Wireless Sensor Network. Réseau de capteur

10

11

Conventions

∆= Définition d’un nouvel objet (membre de gauche) par égalité.N Ensemble des entiers naturels positifs ou nuls.Z Ensemble des entiers relatifs.Card (·) Cardinal de l’ensemble ·.1· Fonction caractéristique de l’évènement ·. Ex : x ∈ A, x ≤ π

Vaut 1 si l’évènement est vérifié, 0 sinon.

(xi)k∈I Suite d’éléments xi avec i parcourant I (ensemble ordonné).EF Espace des fonctions de F dans E.

Lorsque F = N, EN est l’espaces des suites à valeur dans E. Opérateur de composition de fonctions.∇ Opérateur gradient / Jacobien (suivant le contexte).∇2 Opérateur Hessien.O(·) Notation de Landau pour la domination asymptotique.

Ex : f(x) = O(g(x))⇔ ∃x0,∃C > 0,∀x > x0, |f(x)| ≤ C|g(x)|.

1 Vecteur dont toutes les composantes valent 1.·T Transposée vectorielle ou matricielle (sans conjugaison, non-hermitienne)I, In Matrice identité, matrice identité de taille n× n.Tr · Trace d’un endomorphisme d’espace vectoriel, d’une matriceρ(·) Rayon spectral d’une matrice.4 Ordre partiel de définition positive matricielle.

0 4M ⇔M définie semi-positive, et M 4 N ⇔ 0 4 N −M .

Pr [·] Probabilité d’un évènement.d= Egalité en distribution de deux variables aléatoires.E [·] Espérance probabiliste.V [·] Variance probabiliste.Cov(·, ·) Covariance· Estimateur de la variable “·”.

12

13

Introduction

Réseaux de capteurs

Définition et applications

Un réseau de capteurs sans-fil est composé de dispositifs communicants et autonomes ap-pelés nœuds-capteurs. Ces nœuds ont pour objectif de mesurer et surveiller les paramètresphysiques de leur environnement (température, humidité, vibrations, acoustique, mouvements,radioactivité, pollution,...), par le biais de techniques coopératives de traitement de l’informa-tion. Les applications de ce type de réseaux sont nombreuses tant dans le domaine civil (mon-itoring environnemental, étude de mouvements migratoires, mesures physiologiques pour lasanté, agriculture, domotique, ...) que militaire (reconnaissance et surveillance de zone, détec-tion d’essais nucléaires, ...). Les demandes publiques et industrielles pour de tels systèmes sontdes réalités qui laissent envisager la perspective d’un marché dans les années à venir ([ZA],[BAN], [EDF06], [DOE09]).

Historique

Comme dans de nombreux domaines technologiques, les premières applications des réseauxde capteurs sont de nature militaire. On peut fixer le point de départ des recherches avec ledéveloppement du projet SOund Surveillance System (SOSUS, [Whi05]) au début des années50, qui cherchait à détecter et suivre tout activité sous-marine soviétique dans le contexte dela Guerre Froide. Des milliers de kilomètres carrés étaient ainsi surveillés à l’aide de capteursacoustiques (hydrophones) et de magnétomètres. Par la suite, pendant les années 80, le “De-partment Of Defense“ (DoD - Ministère de la Défense américain) lança le program DistributedSensor Networks (DSN) afin de donner une suite au projet SOSUS et d’étendre les capacitésd’ARPAnet, l’ancêtre de notre Internet moderne, lui-même développé à des fins de communi-cations militaires longue-distance. Il faut attendre la fin des années 90 pour voir apparaître lathématique des réseaux de capteurs dans la recherche civile, avec le développement du projetSmartDust [WLLP01], visant à concevoir des systèmes communicants et autonomes de mesuredont la taille serait de l’ordre du millimètre-cube. Ce fut le point de départ de nombreusesrecherches tant sur des aspects technologiques (conception, communication, ...) que théoriques(protocoles, algorithmes de traitement de l’information, ...)

14 INTRODUCTION

Contexte techniqueEn règle générale, un nœud-capteur est équipé d’une ou plusieurs interfaces de communi-

cation (transceiver radio, infrarouge, ultrasons), d’une unité de calcul (microcontrôleur, FPGA,DSP), d’un système de stockage et/ou de récupération d’énergie (batterie, cellule photovoltaïque)et d’un ensemble de capteurs embarqués (température, pression, ...). De plus, ces entités peuventêtre rendues actives par l’adjonction d’actuateurs (système moteur, vibrateurs, ...).

Nous donnons ci-dessous une liste de caractéristiques techniques de quelques nœuds-capteursconnus :

Model Microcontrôleur MHz Memoire TransceiverSensinode N711R1 TI 8051 32 128 kB + 8kB TI CC2431

WorldSens WSN430 TI MSP430 8 10 kB + 1 MB TI CC1100Intel IMote 1.0 ARM 7TDMI 48 512 kB + 64 kB 30m BluetoothIntel IMote 2.0 Marvel PXA271 400 32 MB + 32 MB TI CC2420Berkeley DOTS ATMEGA 163 4 16 kB + 256 kB T1000

(source : Wikipedia)

Par ailleurs, un certain nombre de Stations de Base (ou Point d’Accès) peuvent être intro-duites pour faciliter le déploiement et le management d’un tel réseau. Ces équipements ont pourobjectifs :

– d’interfacer l’utilisateur final avec le réseau– d’effectuer les calculs/algorithmes complexes ou impossibles à l’échelle du réseau– de veiller à son bon fonctionnement– de servir de point de stockage de masse dans le cas d’un réseau isolé

Contraintes et modélisationLes réseaux de capteurs se modélisent par des nœuds distribués spatialement. Cette distri-

bution dépend fortement des objectifs et du scénario environnemental. La capacité d’un nœudà communiquer avec un sous-ensemble du réseau varie suivant le type d’interface de communi-cation utilisé, de l’environnement et des algorithmes incriminés (MAC, routage, ...).

Afin d’augmenter la capacité de surveillance de tels systèmes à coût constant, on préfèreaugmenter le nombre de capteurs tout en réduisant leur taille et coût unitaire, ce qui, suivantl’application, introduit des contraintes importantes plus ou moins interdépendantes :

– utilisation de technologies/matériels de faible complexité– faible capacité de stockage (quelques Mo)– impossibilité d’embarquer des batteries de grande capacité– consommation énergétique faible– capacités de communication limitées (portée, quantité de messages)– par corollaire sur tout un ensemble d’autres paramètres (complexités protocolaires, ...).

Pour s’en convaincre, il suffit de se rapporter au tableau de la section précédente. De plus, lecoût de l’utilisation d’une station est généralement prohibitif, sa mise à place est délicate, et lerecours à des techniques centralisées semble inefficace.

INTRODUCTION 15

En conséquence, ces caractéristiques et contraintes se traduisent par le besoin d’une utilisa-tion de méthodes décentralisées d’auto-organisation et de traitement des données, c’est à dire àdes algorithmes distribués simples et robustes.

Algorithmes de consensus

Le point de départ de cette thèse est donné par un article de Pierrot et al. proposant l’utilisa-tion d’algorithmes de consensus de moyenne pour la synchronisation fine de dérives d’horlogesdans les réseaux de capteurs [Pie05]. Hors de tout cadre algorithmique, le PETIT LAROUSSE

donne la définition suivante :

Consensus : Accord entre plusieurs personnes. En politique, accord et consentement du plusgrand nombre, de l’opinion.

Dans la communauté informatique, l’étude des problèmes de consensus se focalise prin-cipalement sur l’obtention d’un commun accord en présence d’entités malintentionnées oudéloyales (ex : problème des généraux Byzantins).

Par opposition, la communauté du contrôle automatique ne s’intéresse pas aux problèmesde sécurité, mais plutôt à l’aspect convergence (possibilité, vitesse). Les algorithmes de consen-sus prennent alors la forme d’un système dynamique d’équations récursives (temps discret) oudifférentielles (temps continu), et modélisent l’évolution d’une population (essaim, groupe derobots), d’un groupe d’oscillateurs couplés (modèle de Kuramoto [ABPV+05]) ou des opinionsau sein d’une communauté.

La classe des algorithmes de consensus de moyenne (ACM) fut initialement conçue pourle calcul de la valeur moyenne d’un jeu de paramètres distribués (de plsu amples détails serontfournis au chapitre 1). Comme le point de convergence est alors déterministe et donne la mêmeimportance à chaque donnée initiale, ce type d’algorithme constitue une brique de base amenéeà jouer un rôle important pour des protocoles/algorithmes applicatifs complexes (cf chapitres 3et 5).

Sur le plan historique, on peut considérer que les premiers travaux théoriques et pratiquessur les applications numériques des algorithmes aléatoires de consensus sont fournis en 2003par Kempe et Dobra dans [KDG03]. Entre 2003 et 2006, à la suite d’une série d’articles derecherche opérationnelle de type SDP (cf. glossaire), Boyd et ses associés publient une séried’articles sur les algorithmes aléatoires de consensus de moyenne et leurs applications (ajuste-ment au sens des moindres carrés) entre 2003 et 2006 ([BGPS06], [XBL06a], [BGPS05],[XBL05], [BGPS04], [XB03],...). Pendant ce temps, la communauté de la théorie du con-trôle s’intéresse à des problèmes d’oscillateurs couplés ([BS07], [BSP06], ...) et de mouve-ments/prise de décision au sein de groupes : les équipes respectives de Jadbabaie et Olfati-Saberproposent alors de nombreux résultats complémentaires entre 2004 et 2007 sur les algorithmesde consensus synchrones généraux ou de moyenne ([JLM02], [OSFM07]). Plus récemment, cer-tains chercheurs se sont focalisés sur les ACM en présence d’information quantifiée ([ACR08],[FCFZ08], [KM08], ...).

16 INTRODUCTION

Contenu de la thèseL’objectif de cette thèse est de fournir des éléments d’amélioration et d’application de la

catégorie des ACM. Elle se focalise dans un premier temps sur des méthodes de caractérisationet d’optimisation des algorithmes de l’état de l’art. Dans un second temps, deux nouveauxalgorithmes sont proposés afin de réduire le coût énergétique de manière empirique.

Cette thèse s’organise de la manière suivante. Le chapitre 1 décrit les principes fonda-mentaux des algorithmes de consensus de moyenne, et pose des éléments de compréhensionet d’amélioration de leur performance. Ensuite, une version modifiée de ces algorithmes estprésentée dans le chapitre 2 : ce nouvel algorithme se place dans un cadre d’estimation et vise àprendre en compte de nouvelles informations plus rapidement. Une application à la synchroni-sation fine est proposée dans le chapitre 3. Un second algorithme est introduit au chapitre 4 : ilpermet d’utiliser la nature diffusante du canal radio et présente l’avantage de ne pas nécessiterde mécanismes de contrôle (acquittements). Une application à la cartographie paramétrique(couche application) est décrite au chapitre 5.

17

Chapitre 1

Algorithmes de consensus de moyenne

Les algorithmes/protocoles de consensus distribués visent à obtenir un commun accord surune valeur ou une décision entre entités constituant un réseau d’information. Un algorithme estqualifié de bavard (gossip-based) lorsque les échanges sont de simples interactions asynchronesentre nœuds voisins. Les algorithmes bavards de consensus peuvent être utilisés pour cal-culer de manière distribuée toute sorte de quantités statistiques telles que moyennes/variances,valeur maximum/minimum, ou encore quantiles ([JMB05] et [KDG03]). En particulier, la sous-classe des algorithmes de consensus de moyenne joue un rôle particulier car, comme son noml’indique, cette classe à pour objectif le calcul de la valeur moyenne de quantités distribuées spa-tialement. Ce principe permet alors de calculer toute sorte de moments statistiques empiriques.Des applications plus indirectes telles que l’ajustement au sens des moindres carrés de modèlesparamétriques ont aussi été proposées ([XBL05],[XBL06a]).

1.1 PrincipesEn pratique, les algorithmes de consensus sont utilisés pour l’homogénéisation de paramètres

(choix d’une direction d’exploration, fréquence porteuse de communication, ...). Cependant, lavaleur du consensus à obtenir peut être critique. Par exemple, trouver un commun accord sur unpoint de rendez-vous n’est pas aussi critique que de déterminer la position d’un tireur d’élite.En particulier, obtenir un consensus sur une valeur moyenne est un processus plus lent qued’utiliser des méthodes d’inondation/propagation (flooding/broadcasting), mais assure en con-trepartie une bonne qualité de consensus.

Le consensus de moyenne a largement été étudiés dans la littérature ([OSFM07], [BGPS05],[JMB05], ...) notamment par la communauté du domaine du contrôle automatique, pour laquelleil s’agit en général, d’étudier la convergence d’un système dynamique pouvant être :

– en temps discret ou continu– linéaire ou non– synchrone ou asynchrone– déterministe ou aléatoire.Comme le cadre de travail de cette thèse est celui des réseaux de capteurs, nous retiendrons

uniquement les versions discrètes, linéaires et asynchrones des ACM. Dans notre contexte ap-

18 ALGORITHMES DE CONSENSUS DE MOYENNE

plicatif, les échanges d’information des ACM se composent d’interaction entre nœuds voisins(gossiping en anglais). Dans un souci de coût de coordination, ces interactions ne feront inter-venir que deux nœuds à chaque instant.

Le principe des ACM est alors intuitif : il faut systématiquement réduire les écarts d’étatsentre nœuds voisins sans jamais introduire ou perdre de l’information. Autrement dit, les nœudsdoivent tendre à avoir la même valeur d’état, et la masse totale d’information dans le réseau doitêtre conservée. Ce dernier point est important, car si l’on note xi(0) la valeur initiale possédéepar le nœud i, et xi(t) la valeur sa variable d’état au temps t, et x∞ le consensus obtenu, alorsle principe de conservation de masse nous donne :

∀t,n∑i=1

xi(0) =n∑i=1

xi(t) −−−→t→∞

nx∞ ⇒ x∞ =1

n

n∑i=1

xi(0) (1.1)

Autrement dit, un algorithme de consensus avec conservation de masse est nécessairement unalgorithme de consensus de moyenne. La méthode la plus triviale rencontrée dans la littéra-ture, et certainement la plus efficace, consiste alors à choisir une paire de nœuds (i, j) pouvantcommuniquer entre eux, et à effectuer une interaction du type :[

xi(t+ 1)xj(t+ 1)

]=

[α (1− α)

(1− α) α

]×[xi(t)xj(t)

]α ∈ [0, 1] (1.2)

Cette interaction vérifie bien le principe de conservation de masse. En général, le poids α estfixé de manière radicale à 1/2, ce qui entraîne l’égalité de xi(t + 1) et xj(t + 1). Pour α = 0,l’interaction est simplement l’identité, alors que pour α = 1 l’interaction permute1 les états desnœuds i et j. L’algorithme peut alors se formuler sous forme d’un système linéaire récursif :

Xt+1 = WtXt (1.3)

où Xt est le vecteur des états des nœuds au temps t (X0 contient alors les valeurs à moyenner)et Wt est une matrice d’ordre n qui décrit l’interaction pair-à-pair. Les composantes de Xt sontdes estimations locales de la moyenne globale des paramètres initiaux, et si la convergence estassurée, ces estimations doivent tendre vers la vraie moyenne globale. En utilisant la notationde Boyd et Xiao [XBL05], Wt est de la forme :

Wt = I − α(ei − ej)(ei − ej)T ∆= W

(α)ij (1.4)

où ei = [0 . . . 0 1 0 . . . 0]T est un vecteur de dimension n dont seule la i-ème entrée vaut 1(ici, le double indice matriciel ij signifie que le nœud i initie une interaction avec le nœudj). La notation Wij fera systématiquement référence à W (1/2)

ij . Nous appellerons politique lafonction qui à t associe le triplet (i, j, α). L’ensemble des valeurs que peut prendre ce triplet estprincipalement restreint par la topologie du réseau. Par extension, cette politique associe unematrice Wt à toute valeur de t, de manière déterministe ou aléatoire. Dans ce document, lespolitiques consistent à choisir les nœuds initiateurs de manière aléatoire et uniforme. Ce choixarbitraire permet de s’absoudre de tout problème d’ordonnancement et de synchronisation desnœuds. Nous détaillerons à la section suivante comment rendre cette modélisation réaliste etenvisageable.

1Ce fait est utile pour construire des ACM aléatoires à convergence presque sûrement en temps fini

HASARDISATION 19

Exemple 1.1 (Quelques exemples de politiques [XBL05]) Si le nœud i est choisi comme ini-tiateur, il choisit dans son voisinage le nœud j comme destinataire avec la probabilité pij définiepar :

1. politique naturelle :

pij =1

δi, pii = 0

2. politique Metropolis-Hasting :

pij =1

max(δi, δj), pii = 1−

∑j∼i

pij

3. politique constante :

pij =1

δmax, pii = 1− δi

δmaxoù δi représente le degré du nœud i, i.e. son nombre de voisins, et δmax le degré maximum surl’ensemble des nœuds. Une probabilité pii non nulle signifie que le nœud i sélectionné seraautorisé à ne rien faire, et sert en général à “compléter” les probabilités des liens pour obtenirun total de 1.

En pratique, la politique naturelle est la plus simple à mettre en œuvre et donne de loinles meilleurs résultats parmi ces trois standards : elle sera systématiquement choisie. L’intérêtd’avoir une politique aléatoire est multiple :

1. ne pas avoir à déployer de méthode d’ordonnancement/synchronisation qui peut être coû-teuse et instable.

2. éviter certaines inefficacités dues à un mauvais ordonnancement déterministe.3. limiter le risque d’interblocage.4. sur le plan théorique, ne pas avoir à utiliser de méthode d’optimisation combinatoire qui

longue, difficile à distribuer et qui nécessite une nouvelle exécution au moindre change-ment de topologie.

1.2 Hasardisation

1.2.1 Hasardisation temporelleChaque itération est initiée par un unique nœud choisi aléatoirement suivant une loi uni-

forme, de manière indépendante à chaque itération. Autrement dit, dans un réseau de n nœuds,chaque nœud a une probabilité 1/n d’initier une interaction. Ce modèle présente l’avantage desimplifier l’étude comportementale des algorithmes de consensus de moyenne, mais il peut êtremodifié à souhait au prix d’une complexité d’étude accrue. Boyd et Xiao justifient la pertinencede cette hypothèse en supposant que chaque nœud embarque une horloge générant un processusponctuel de Poisson, c’est à dire dont les déclenchements sont espacés par des durées aléatoiresi.i.d. de loi exponentielle de paramètre λ (densité du processus) identique pour chaque nœud. Ilsdémontrent alors que le processus des déclenchements à l’échelle du réseau équivaut2 à prendre

2en toute rigueur, ceci est vrai à partir de l’instant où toutes les horloges sont démarrées


0.01

0.1

1

10

0 200 400 600 800 1000 1200 1400

EQ

M

Iteration

politique naturellepolitique Metropolis-Hasting

politique degrˆ' max

Figure 1.1 – EQM en fonction de la politique choisie (100 nœuds distribués uniformément dansun carré de largeur 1, modèle booléen de communication, rayon 0.25)

un processus de Poisson marqué de densité nλ dont les marques sont i.i.d suivant la loi uni-forme discrète de support 1, 2, . . . , n. Cette approche se généralise aisément à des horlogeshétérogènes : si on associe au nœud i une horloge générant un processus ponctuel de Poissonde densité λi, alors le processus global est un processus ponctuel de Poisson marqué, de densité∑

i λi, dont les marques sont i.i.d. et telles que la probabilité de constater la i-ème marque soitλi/∑

j λj .Notons qu’une variable aléatoire exponentielle E de paramètre λ se génère aisément à partir

d’une variable aléatoire U uniforme sur l’intervalle [0, 1] par le biais de la transformation :

E =− ln(U)

λ(1.5)

et que l’on peut toujours se ramener au cas d’horloges homogènes par le biais d’un algorithmede consensus distribué quelconque visant à homogénéiser les densités λi.

1.2.2 FormalisationPar la suite, les matrices aléatoires Wk sont considérées indépendantes et identiquement

distribuées (i.i.d.) : chaque matrice Wij est choisie avec une probabilité pij , qui correspond àl’évènement “le nœud i a choisi d’interagir avec le nœud j “.

W = E [Wk] = E [W0] =1

n

∑i,j

pijWij (1.6)

où n représente le nombre de nœuds du réseau.

HASARDISATION 21

En utilisant l’axiomatique de Kolmogorov (cf annexe A), on peut décrire rigoureusementces modélisations. On peut associer un espace probabilisé identique (Ω,A, µ) à chaque instantt, tel que :

1. Ω est l’ensemble des matrices d’interaction envisageables (généralement fini ou dénom-brable)

2. A est la σ-algèbre engendrée par les singletons de Ω (équivalente à la topologie discrètesur Ω).

3. µ est une mesure de probabilité discrète sur (Ω,A)

A partir de ces espaces, on peut bâtir un espace probabilisé produit (Ω∞,A∞, µ∞) cor-respondant aux suites infinies de matrices d’interaction. Ce formalisme sert principalement àdériver des résultats d’existence et à définir une notion de propriété ”presque-sûre“ (cf annexeA).

1.2.3 Condition et critères de convergence

Dans [BGPS05], la proposition suivante est démontrée :

Proposition 1.1 Si W est doublement stochastique et ergodique, alors limt→∞

E [Xt] = θ1 et

limt→∞

E[∥∥Xt − θ1

∥∥] = 0 avec θ = 1n

∑ni=1 xi(0) et 1 = [1, . . . 1]T ∈ Rn.

Autrement dit, la convergence vers le consensus de moyenne est assurée si et seulementsi l’ensemble des modules des valeurs propres de W contient 1 avec une multiplicité unitaire.On peut aussi traduire ceci dans un contexte markovien : W est la matrice de transition d’unechaîne de Markov dont le graphe de transition est fortement connecté, c’est à dire que pourchaque paire d’états (i, j), il existe un chemin de i à j et de j à i.

Remarque 1.1 Il faut noter que l’assertion limt→∞

E [Xt] = θ1 ne suffit pas à garantir que leconsensus obtenu est le consensus de moyenne : il pourrait s’agir d’une variable aléatoirecentrée sur la moyenne, gaussienne ou uniforme par exemple. Cependant, la convergence dusecond ordre exprimée par lim

t→∞E[∥∥Xt − θ1

∥∥] = 0 assure asymptotiquement l’absence dedéviation par rapport à la moyenne.

La même équipe démontra aussi un résultat qui fait abstraction de la dimension probabiliste

Proposition 1.2 ([XBL05]) Soit G = (V , E) l’ensemble de ses arêtes, et Et l’ensemble desarêtes actives au temps t (paires de nœuds en interaction). Alors si le graphe G = (V ′, E ′)défini par :

V ′ = V E ′ =⋂k≥0

⋃t≥k

Et (1.7)

est connexe, alors limt→∞

Xt = θ1.


Cette proposition peut être reformulée comme suit : si l’ensemble des liens de communicationbidirectionnels activés une infinité de fois forment un graphe connexe, alors l’ACM converge.En conséquence, si dans un schéma probabiliste, cette propriété des liens de communication estvérifiée presque-sûrement, i.e. avec une probabilité de 1, alors l’algorithme converge lui aussipresque-sûrement vers le consensus de moyenne.

Tahbaz-Salehi a posé le problème probabiliste dans le cadre de l’axiomatique de Kolmogorovdans [TSJ07] puis a démontré le résultat suivant :

Proposition 1.3 Soient :– (Ω,A, µ) un espace probabilisé pour lequel Ω est l’ensemble des matrices stochastiques

à coefficients diagonaux strictement positifs.– (Ω∞,A∞, µ∞) l’espace probabilisé produit des suites de telles matrices.– (W1,W2,W3, . . . ) la variable aléatoire canonique sur Ω∞

Alors, si |λ2(E [Wt])| < 1 (ne dépendant pas de t), alors presque-sûrement :

limt→∞

Wt . . .W3W2W1 = 1cT

où c est un vecteur aléatoire Rn. De plus, si E [Wt] est doublement stochastique, alors c = 1n1

(consensus de moyenne).

Du point de vue du temps de convergence, l’équipe de Boyd posa la définition suivante :

Définition 1.1 Le temps d’ε-moyennage se défini comme :

Tave(ε)∆= sup

X0

inf

Pr

[‖X0 − z1‖‖X0‖

≥ ε

]≤ ε

(1.8)

L’indicateur Tave(ε) quantifie le temps nécessaire pour avoir une probabilité arbitrairementfaible d’avoir une déviation arbitrairement grande. Boyd et al. ont démontré l’existence d’uneminoration et d’une majoration de Tave(ε) basées sur la seconde plus grande valeur propre deW .

Proposition 1.4 Le temps d’ε-moyennage peut être encadré de la manière suivante :

0.5 log ε−1

log λ2(W )−1≤ Tave(ε) ≤

3 log ε−1

log λ2(W )−1(1.9)

La valeur propre λ2 est fonction des probabilités d’interaction.

Définition 1.2 On appelle facteur temps le terme −1/ log λ2(W ).

Le terme λ2(W ) doit être minimisé pour accélérer l’algorithme : nous présenterons plusieursapproches dans la suite de ce document.

SOLUTIONS P2P EN TEMPS FINI 23

1.3 Solutions P2P en temps finiDans cette section nous allons démontrer les résultats suivants :

1. il est impossible d’atteindre le consensus de moyenne en temps fini avec la pondérationstandard 1/2 dans le cas général.

2. des solutions en temps fini peuvent être construites sur tout réseau connexe.3. il existe un algorithme aléatoire universel qui converge en temps fini de manière presque

sûre.4. ces solutions aléatoires sont largement sous-optimales du point de vue de la vitesse de

convergence.Les motivations de cette étude proviennent de l’exemple suivant :

Exemple 1.2 Considérons un 4-cycle, i.e. un réseau en forme d’anneau composé de 4 nœuds,chacun ayant exactement deux voisins. La procédure suivante permet d’obtenir un consensusde moyenne en 4 itérations :

1. Le nœud 1 initie avec le nœud 2 une itération de poids 1/2.2. Le nœud 3 initie avec le nœud 4 une itération de poids 1/2.3. Le nœud 1 initie avec le nœud 4 une itération de poids 1/2.4. Le nœud 2 initie avec le nœud 4 une itération de poids 1/2.

En partant des états initiaux x1(0), x2(0), x3(0) et x4(0), il est facile de vérifié qu’à la fin de laquatrième itération, le consensus de moyenne est obtenu sur tous les nœuds :

∀i ∈ 1, 2, 3, 4, xi(t = 4) =1

4

4∑i=1

xi(0) (1.10)

1.3.1 Cas des pondérations standardProposition 1.5 Dans le schéma standard, si le nombre de nœuds n’est pas une puissance de 2,il existe un vecteur pour lequel le consensus de moyenne ne peut pas être atteint en temps fini.

Preuve : L’idée de la preuve est de trouver une structure algébrique contenant, pour uncertain vecteur initial, les entrées des vecteurs d’états obtenus au cours des itérations, mais necontenant pas le consensus de moyenne correspondant.

L’algorithme standard (éq. 1.2 avec α = 1/2) se modélise comme un produit de matricedont les entrées proviennent de l’ensemble 0, 1, 1/2. Si une solution en temps fini existe, ceproduit est fini et on obtient alors une certaine matrice W . Notons (A,+,×) l’anneau3 abélienengendré par l’ensemble 0, 1, 1/2, stable par addition/soustraction et multiplication. Commele produit matriciel est obtenu par multiplication et addition des entrées des matrices, et que cesentrées sont des éléments de A, il en résulte alors que les éléments deW sont aussi des élémentsde A. On montre facilement que A est l’ensemble des combinaisons linéaires de puissances(éventuellement négatives) de 2 :

A = Z[1/2] = r

2s| r ∈ Z, s ∈ N

(1.11)

3on pourrait en fait se contenter d’une structure de semi-anneau


Maintenant, si le vecteur initialX0 sur lequel on doit appliquer l’algorithme possède des entréesdans A, alors à tout moment, les entrées du vecteur d’état Xt sont aussi dans A = Z[1/2]. Choi-sissons par exemple le vecteur X0 = [1, 0, . . . , 0]T. Le consensus de moyenne vaut clairement1/n, ce qui veut dire que si une solution en temps fini existe, alors en particulier il existe unt pour lequel Xt = [1/n, . . . , 1/n]T. Or on peut montrer facilement que 1/n ∈ Z[1/2] si etseulement si n est une puissance de 2.

1.3.2 FaisabilitéDans cette partie, nous allons construire une solution universelle qui converge en temps fini.

La question de la coordination sera abordée dans la partie suivante. Cette construction s’inspiredes filtres récursifs à moyenne mobile.

Proposition 1.6 Pour tout réseau connexe, il existe un algorithme de consensus de moyennepair à pair en temps fini.

Preuve : Tout d’abord remarquons que pour tout couple de nœuds voisins, W (1)ij est une

matrice de permutation qui correspond à la transposition i j. Si on considère l’ensemblede ces matrices, on constate qu’il est possible d’échanger les états de n’importe quelle pairede nœuds voisins sur un graphe connexe. On peut alors montrer que, sous réserve de connexitédu graphe, le semigroupe engendré par les matrices W (1)

ij avec (i, j) ∈ E est exactement legroupe M(Sn) des matrices de permutation d’ordre n. Il devient alors possible d’apporter desinformations lointaines dans un voisinage par échanges successifs, de les traiter localement puisde renvoyer le résultat à sa place initiale. Cette méthode permet alors d’étendre l’ensemble desmatrices d’interaction à tous les nœuds du réseau en utilisant les W (1)

ij , comme le montre laconstruction suivante : Il est facile de vérifier qu’à la fin de la boucle secondaire pour le i-ème

pour i ∈ [1, n] faireActiver le nœud i;Choisir un voisin v de i;k ← 2;pour j ∈ [i+ 1, n] faire

Echanger les états de j et v ;Appliquer l’interaction de poids 1/k : W (1/k)

iv ;Echanger les états de j et v;k ← k + 1;

finfin

Algorithme 1 : Exemple d’ACM pair-à-pair en temps fini

passage de la boucle principale, l’état du nœud i est précisément le consensus de moyenne z. Ilne reste plus qu’à formuler cet algorithme de manière matricielle. Pour chaque nœud i, fixonsun voisins vi, puis pour tout j > i notons W tr

jvila matrice de permutation correspondant à la

transposition vi j, et Wmaij la matrice définie par :

Wmaij

∆= W tr

jviW

(1/(j−i+1))ij W tr

jvi(1.12)

SOLUTIONS P2P EN TEMPS FINI 25

puis Wmai la matrice définie par :

Wmai

∆= Wma

in . . .Wmai(i+1) (1.13)

L’algorithme cité ci-dessus se met alors sous la forme suivante :

Wman−1W

man−1 . . .W

ma1 =

11T

n(1.14)

Il s’agit donc bien d’une formulation conforme aux algorithmes de consensus de moyennebavards.

1.3.3 Hasardisation et universalitéNous supposerons dans cette partie que le réseau comporte n nœuds mais qu’eux même

ignorent leur nombre. On notera Fi l’ensemble des matrices d’interactions pouvant être initiéespar le nœud i, i.e. :

Fi =W

(1/k)ij : k ∈ N∗, j ∈ Ni

(1.15)

et de manière générale F dénotera l’ensemble dénombrable des interactions possibles sur leréseau :

F =n⋃i=1

Fi (1.16)

Si chaque matrice de Fi se voit affecter une probabilité strictement positive d’être choisie par lenœud i, chaque élément de F a donc une probabilité strictement positive d’être choisi à chaqueinstant. Sans perte de généralité, on supposera qu’à chaque instant une interaction est choisie.Toute allocation de probabilités sur les éléments de F satisfaisant ces hypothèses correspond àun algorithme aléatoire de consensus de moyenne.

Proposition 1.7 Soit un choix de probabilité sur F tel que :

∀t, ∀W ∈ F, Pr [W (t) = W ] = pW > 0 et∑W∈F

pW = 1

Alors l’algorithme aléatoire correspondant converge en temps fini vers le consensus de moyennede manière presque sûre (i.e. la probabilité que cet évènement n’ait pas lieu est nulle).

Preuve : Soit Wtf = W tf1 . . .W tf

K une solution de consensus de moyenne en temps fini.On a montré à la section 1.3.3 qu’une telle solution existe et n’est généralement pas unique. Soit(W (t))t∈N∗ une suite d’élément de F correspondant à une réalisation de l’algorithme aléatoire.Cette chaine peut alors être découpée en blocs de longueur K.

Pr[W (NK)W (NK − 1) . . .W ((N − 1)K + 1) = W tf

](1.17)

≥K∏k=1

Pr[W ((N − 1)K + k) = W tf

k

]=

K∏k=1

pW tfk

∆= ptf > 0 (1.18)


où le signe ≥ provient du fait que la factorisation de W tf en un produit de K matrices d’in-teraction peut ne pas être unique. La probabilité pNK qu’une sous chaine de longueur NK (Nblocs) ne contiennent pas W tf vérifie donc :

PNK ≤ (1− ptf )N (1.19)

En faisant tendreN vers +∞, on obtient que la probabilité pour que la suite aléatoire (W (t))t∈N∗

ne contienne pas W tf est nulle. Une preuve plus rigoureuse peut être dérivée par le biais dulemme de Borel-Cantelli [Gar03].

Si les nœuds connaissent le paramètre n, alors on peut réduire les Fi et F aux matrices dutype W (1/k)

ij avec k entier dans [1, n]. La conclusion est alors la même.

1.3.4 Sous-optimalitéDans cette partie nous allons montrer que toute solution en temps fini est nécessairement

sous-optimale en vitesse de convergence, i.e. au sens du critère λ2(W ) (cf déf. 1.2).

Proposition 1.8 Soit un algorithme aléatoire de consensus de moyenne en temps presque sûre-ment fini, F l’ensemble de ses matrices d’interactions, et pour W ∈ F , pW la probabilité dedéclencher l’interaction de matrice W . Alors :

λ2

∑W

(α)ij ∈F

pW

(α)ijW

(α)ij

TW

(α)ij

> λ2

∑W

(α)ij ∈F

pW

(α)ijW

(1/2)ij

TW

(1/2)ij

Autrement dit, la solution en temps fini converge moins vite au sens du second-ordre proba-

biliste qu’une solution standard utilisant les mêmes probabilités mais des interactions de poids1/2. Preuve :

W(α)ij = In − αEij ⇒ W

(α)ij

TW

(α)ij = In − 2α(1− α)Eij (1.20)

Fixons un matrice d’interaction quelconque dans F , disons W0, de poids α0 6= 1/2, etnotons F0 = F \W0.

S∆=

∑W

(α)ij ∈F

pW

(α)ijW

(α)ij

TW

(α)ij (1.21)

S0∆=

∑W

(α)ij ∈F0

pW

(α)ijW

(α)ij

TW

(α)ij (1.22)

Dans W0 on s’autorise alors à faire varier le poids :

W(α)0

∆= In − αEi0j0 (1.23)

λ2 (S) = λ2

(pW0W0

TW0 + S0

)(1.24)

= maxX⊥1‖X‖=1

XT [pW0(In − 2α0(1− α0)Ei0j0) + S0]X (1.25)

CARACTÉRISATION ET ACCÉLÉRATION DES PERFORMANCES 27

Par compacité de la sphère unité fermée, et par continuité des formes quadratiques sur Rn,pour chaque α, il existe un Xα ∈ Rn réalisant ce maximum (cf Th. de Heine-Borel [Arm97]).En particulier, une simple étude variationnelle montre que pour α ∈ [0, 1], le terme −2α(1 −α)XT

1/2Ei0j0X1/2 est minimal pour α = 1/2, ce qui implique alors :

λ2

(pW0W

(1/2)0

TW

(1/2)0 + S0

)= XT

1/2

[pW0(In −

1

2Ei0j0) + S0

]X1/2 (1.26)

≤ XT1/2 [pW0(In − 2α(1− α)Ei0j0) + S0]X1/2 (1.27)

≤ maxX⊥1‖X‖=1

XT[pW0W

(α)0

TW

(α)0 + S0

]X = λ2

(pW0W

(α)0

TW

(α)0 + S0

)(1.28)

avec égalité si et seulement si α = 1/2. En opérant le même raisonnement à tous les élémentsde F , chaque matrice d’interaction se voit remplacée par son homologue de poids 1/2. Laproposition est démontrée.

Bien que ce résultat s’oppose à l’intuition, il reste facile à comprendre. En effet, on con-naît l’existence d’au moins une solution en temps fini pour tout réseau connexe. Or, dans unschéma d’interactions aléatoires, cette solution apparaîtra sûrement, mais à partir d’un tempslui aussi aléatoire, et pouvant être arbitrairement grand. Donc l’espérance de l’erreur quadra-tique moyenne à un instant donné, prise sur les réalisations de l’algorithme, ne peut être nulle.Or on sait que la vitesse de décroissance est maximale pour des interactions de poids 1/2 (con-sensus local optimal).

1.4 Caractérisation et accélération des performancesDans cette section, nous allons présenter quelques résultats autour des performances en

termes de temps de convergence.

1.4.1 Méthodes idéalesDans [BGPS05], deux méthodes d’optimisation du facteur de convergence λ2(W ) (cf eq.

1.6) sont proposées. La première consiste à reformuler la minimisation de λ2(W ) en un prob-lème de programmation semi-définie (SDP) sous contraintes :

minimiser savec a)W − 11T/n 4 sI

b)W = 1n

∑ni,j=1 pijWij

c)∀i, j, pij ≥ 0d)∀(i, j) /∈ E , pij = 0e)∀i,

∑nj=1 pij = 1

(1.29)

1. W − 11T/n est une matrice définie positive dont le rayon spectral vaut λ2(W )

2. la matrice W est définie comme l’espérance par rapport aux Wij et pij3. les probabilités doivent être positives


4. une probabilité de communication est positive ssi les nœuds impliqués sont en mesure decommuniquer

5. un nœud initiateur doit choisir une destination

L’avantage de cette technique est de pouvoir prendre en compte des critères énergétiques,en rajoutant par exemple une contrainte de dépense énergétique moyenne par nœud.

f)∀i,∑j

pijε(s)ij + pjiε

(d)ij ≤ ε

(0)i (1.30)

où :– ε

(s)ij représente la dépense énergétique moyenne du nœud i comme initiateur (s : source)

d’une interaction avec le nœud j– ε

(d)ij représente la dépense énergétique moyenne du nœud i comme destinataire (d) d’une

interaction avec le nœud j– ε

(0)i représente la dépense énergétique moyenne acceptable par le nœud i

Cependant, à l’heure actuelle, aucun algorithme de SDP pouvant être distribué sur un réseaude capteurs n’existe. Les méthodes existantes sont principalement synchrones (donc idéalespour des clusters de calcul), et la taille des données incriminées est très importante. En essayantde proposer une technique d’optimisation pseudo-distribuée, les auteurs de [XBL05] ont aussisuggéré l’utilisation d’une méthode de sous-gradient, mais cette méthode souffre d’une syn-chronie sévère et sa condition d’arrêt reste empirique. Il est donc nécessaire de trouver d’autresheuristiques d’optimisation.

1.4.2 Heuristiques topologiques directesIl est possible de formuler des méthodes heuristiques d’optimisation et/ou de caractérisa-

tion des performances. Par exemple, des simulations tendent à nous indiquer que les perfor-mances s’améliorent en rajoutant des liens de voisinage à la connectivité actuelle d’un réseau.En général, les meilleures performances sont obtenues pour des liens longs, mais ces liens sontpénalisants sur le plan énergétique. L’intuition appuie ces constatations : en augmentant la con-nectivité du réseau, on améliore aussi sa capacité à brasser l’information. Celle-ci se diffused’autant plus rapidement, à l’image d’un virus lors d’une pandémie4. Cependant, il ne s’agitpas d’un résultat exact : en effet, en rajoutant petit à petit des liens à un graphe donné, les in-dicateurs de performances peuvent avoir tendance à augmenter avant de subir des sauts plus oumoins brutaux.

De manière équivalente, on peut se concentrer sur des heuristiques topologiques générales,basées sur les propriétés du graphe de connectivité du réseau. Par exemple, les figures 1.2 et 1.4illustrent l’évolution des performances pour un réseau modélise comme un graphe géométriquedistribué sur une surface carrée, en fonction du rayon de communication ou de la connectivitéalgébrique du réseau (cf annexe A).

Tout d’abord, par le biais de calculs directs, on obtient la valeur exacte de λ2(W ) pourquelques topologies particulières (cf tableau 1.1). Ce type de calcul devient rapidement difficile,voire impossible à effectuer pour des topologies triviales d’intérêt (chemins, grilles,...). Par

4ce qui explique que les algorithmes bavards (gossip-based) sont aussi appelés algorithmespandémiques/épidémiques


G λ2(W )Clique Kn 1− 1

n−1

Cycle Cn 1− 1n

[1− 1 cos 2π

n

]Étoile Sn 1− 1

2(n−1)

Tableau 1.1 – Valeurs exactes de λ2(W )

0.975

0.98

0.985

0.99

0.995

1

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6

λ 2(W

)

Rayon de communication

50 noeuds100 noeuds150 noeuds200 noeuds

Figure 1.2 – λ2(W ) en fonction du rayon de communication

contre, il est possible de trouver de bonnes approximations en reliant λ2(W ) à la connectivitéalgébrique du graphe de connectivité.

Par exemple, la proposition suivante permet de borner les performances de l’ACM naturel enfonction de quantités simples de la connectivité :

Proposition 1.9

1− 1

nδminα(G) ≤ λ2(W ) ≤ 1− 1

nδmaxα(G) (1.31)

Preuve : Nous avons besoin des deux lemmes suivants :


10

100

1000

10000

100000

1e+06

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6

Fac

teur

tem

ps -

1/lo

g(λ 2

(W))

Rayon de communication

50 noeuds100 noeuds150 noeuds200 noeuds

Figure 1.3 – Facteur temps en fonction du rayon de communication

Lemme 1.1W = I − 1

2nLW (1.32)

où LW est un laplacien de graphe pondéré, avec [LW ]ij = pij + pji si (i, j) ∈ E

Lemme 1.2 (minu∼vpuv + pvu

)α(G) ≤ λ2 (LW ) ≤

(maxu∼vpuv + pvu

)α(G) (1.33)

Graphe Cardinalité Spectre du laplacien λ2 (LG)Clique Kn n 0, n(n−1) n

Clique Km,n m+ n 0,m(n−1), n(m−1),m+ n min m,nEtoile Sn n 0, 1(n−2), n 1

Chemin Pn n 2(1− cos kπ

n

), k ∈ Zn 2

(1− cos π

n

)Cycle Cn n 2

(1− cos 2kπ

n

), k ∈ Zn 2

(1− cos 2π

n

)n-cube Qn 2n (2k)(

nk) , k ∈ Zn 2

2-arbre Tn n = 2h − 1 ? ≥ 1(n−1) log2 n

Grille Gn,m nm λi(Pn) + λj(Pm), (i, j) ∈ Z2n ?

Tableau 1.2 – Valeur de la connectivité algébrique pour des topologies classiques (λ(k) signifieque λ est valeur propre de multiplicité k). Voir [Spi09]


0.988

0.99

0.992

0.994

0.996

0.998

1

0 50 100 150 200 250 300 350 400

λ 2(W

)

Connectivite algebrique α(G)

100 noeuds200 noeuds400 noeuds

Figure 1.4 – λ2(W ) en fonction de α(G)

La valeur exacte du paramètre α(G) est connue pour certaines topologies particulières in-diquées (cf tableau 1.2). Cette méthode permet d’obtenir des résultats extrêmement intéressantsà partir de bornes disponibles dans la littérature (cf [Moh91],[Fie73]), comme :

Théorème 1.1 Pour tout graphe G à n sommets, λ2 (LG) ≤ nn−1

δmin

Cette borne est atteinte pour le graphe complet Kn, et les performances sont alors maximalespour ce graphe :

Corollaire 1.1 Pour tout graphe G à n sommets, λ2 (WG) ≥ λ2 (WKn)

Preuve :

λ2(W ) ≥ 1− 1

nδminλ2 (LG) ≥ 1− 1

nδmin

n

n− 1δmin ≥ 1− 1

n− 1(1.34)

Et lorsque le graphe G est d-régulier5, c’est à dire que les sommets sont tous de degré d :

Corollaire 1.2 Si G est d-régulier :

λ2(W ) < 1− d− 2√d− 1

nd(1.35)

Preuve :λ2 (LG) > d− 2

√d− 1 (1.36)

5correspond à un réseau où chaque nœud a exactement d voisins


λ2(W ) = 1− 1

ndλ2 (LG) (1.37)

λ2(W ) < 1− d− 2√d− 1

nd(1.38)

De manière générale, cette méthode indique des voies d’accélération mais ne permet pas dequantifier le coût énergétique nécessaire. Certains constats doivent s’ajouter à l’inventaire qui aété fait :

– Le retrait d’une arête diminue α(G) mais pas nécessairement λ2(W ).– Sur des cliques reliées par des arêtes, on trouve en pratique quelques heuristiques per-

mettant de comparer les performances, mais cela reste à l’état empirique et il y a des casparticuliers.

– Cependant, on peut essayer de garantir un encadrement de la performance (bornes) enfonction de certains paramètres (diamètre, degré min/max, ...)

1.4.3 Caractérisation à haute densité

Dans certaines conditions, on peut trouver d’excellentes approximations des facteurs λ2(W )et−1/λ2(W ). Dans cette section, nous présentons une méthode d’approximation basée sur uneétude ”à haute-densité”. Pour cela, nous allons commencer par poser quelques hypothèses detravail :

1. Le monde est un espace compact Ω fixé.

2. Les nœuds sont distribués aléatoirement, uniformément et indépendamment sur Ω

3. Ils ont tous la même fonction de connectivité.

Lorsque ces hypothèses sont réunies et que l’on augment le nombre de nœuds, les simulationsdévoilent deux phénomènes intéressants concernant la relation (1.9) : on peut y remplacer

1. δmin et δmax par le degré moyen empirique ou théorique, δ

2. α(G)/n par limn→∞

E [α(G)/n]

pour obtenir les approximations recherchées. En particulier, on peut être tenté d’écrire :

−1

log λ2(W )≈

n→∞

δ

α∞(1.39)

où l’équivalence est à prendre au sens large.A l’aide de la méthode que nous allons détailler par la suite, cette formule permet d’opti-

miser les performances en jouant sur la fonction de connectivité. Commençons par définir unefonction de connectivité :

Définition 1.3 (fonction de connectivité) Une fonction de connectivité est une fonction de Ω×Ω dans 0, 1. En particulier, on dira qu’une fonction de connectivité ψ est radiale s’il existeune distance d sur Ω pour laquelle ψ(x, y) n’est fonction que de d(x, y).


Exemple 1.3 Soit Ω = [0, 1]m un cube en dimension m et la fonction de connectivité radiale ψdéfinie par :

∀x, y ∈ Ω, ψ(x, y) =

1 si d(x, y) ≤ r0

0 sinon (1.40)

où r0 est une constante que nous appellerons rayon de connectivité

Rappelons que le paramètre α(G) est la connectivité algébrique du graphe de connectivité,i.e. la seconde plus petite valeur propre de sa matrice laplacienne LG . Celle-ci, s’écrit :

[LG]ij =

δi si i = j−1 si i 6= j et ψ(xi, xj) = 1

0 sinon(1.41)

Fixons un nœud i et augmentons le nombre de nœuds. D’après la loi des grands nombres,on a le passage à la limite suivante :

∀i, [ 1

nLGv]i =

n∑j=1

Lijvj −−−→n→∞

∫Ω

ψ(xi, y)[v(xi)− v(y)]dy∆= Lψ[v](xi) (1.42)

Autrement dit, la matrice laplacienne se transforme en un opérateur auto-adjoint. Le but est alorsde trouver le spectre de celui-ci. De même, les travaux de Bordenave et Mézard ont permis dedéterminer le spectre limite de matrices similaires :

– de manière exacte dans le cas de la matrice de connectivité [Bor06]– de manière approximative dans un cas global [MPZ99] en utilisant des outils mathéma-

tiques complexes de la mécanique statistique et de la théorie quantique des champs.Nous donnerons une démarche rapide mais non-rigoureuse pour retrouver ces résultats exactset/ou empiriques.

Considérons, par exemple un monde torique, Rd/Zd. Il est facile de voir que la famillee2πikT·x, k ∈ Zd constitue une base orthogonale de fonctions propres de Lψ[·](·) et les valeurspropres associées sont ψ(0)− ψ(k), où ψ(k) représente le k-ième coefficient de la transforméede Fourier de la fonction ψ(0, x).

Ainsi on obtient le résultat attendu :

−1

log λ2(W )≈

n→∞

(n− 1)ψ(0)

mink∈Zd∗ [ψ(0)− ψ(k)](1.43)

A titre d’illustration, les courbes des figures 1.5 et 1.6 permettent de comparer le facteurtemps à ses approximations pour 400 nœuds distribués uniformément sur un tore bidimension-nel et pour des fonctions de connectivité circulaire : en particulier, on voit que l’approxima-tion n’est pas très précise. De manière générale, l’expérience montre que cette approximationgrossière permet de prédire les points de fonctionnement optimaux.


1000

10000

100000

0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Fac

teur

tem

ps m

oyen

Rayon de connectivite

valeur reelleapproximation laplacienne

approximation haute-densite

Figure 1.5 – Facteur temps moyen en fonction du rayon de connectivité - valeurs réelles etapproximations à haute densité

Le problème reste de trouver la fonction de connectivité ψ qui minimise cet indicateur, etdes contraintes énergétiques peuvent être imposées. Mais, ce type de problème de rechercheopérationnelle en dimension infinie est impossible à résoudre numériquement. Pour y parvenir,il faut restreindre l’espace de recherche (par exemple, considérer les fonctions de connectivitéen forme de disque ou d’anneau simple).

Cette approche peut se transposer aisément à tout monde Ω vérifiant les hypothèses suiv-antes :

1. Ω est un espace métrique compact

2. il existe un groupe d’isométries Iso(Ω) opérant transitivement sur Ω, un groupe de trans-formations préservant les distances et tel que pour tout couple de point (x, y) il existe unetransformation portant x en y.

Par exemple, un monde sphérique vérifie pleinement ces conditions. Sous ces hypothèses, onpeut utiliser une base de représentation (voir par ex. [DE08]) de Iso(Ω) en guise d’analogue àla transformée de Fourier et retrouver des résultats similaires.

Remarque 1.2 Si un des points suivant est vérifié, les solutions exactes sont difficiles à trouveret l’aide d’un logiciel de calcul numérique est un recours quasi-systématique :

– la fonction de connectivité n’est pas isotrope pour une certaine distance sur Ω.– il n’existe pas de groupe d’isométries transitif sur Ω.– les nœuds ne sont pas distribués uniformément.

Par exemple, un simple cube en dimension d ne vérifie jamais le second point.

INTERACTION ASYMÉTRIQUES & CONVOLUTIONS DE BERNOULLI 35

0.1

1

10

100

0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Err

eur

moy

enne

(%

)

Rayon de connectivite

Reel-Approx. Lap.Reel-Approx. HD

Figure 1.6 – Pourcentage d’erreur d’approximation en fonction du rayon de connectivité

1.4.4 Écoute passiveAu printemps 2008, alors que nous avions stoppé les recherches sur les ACM classiques,

Rabbat et al ont proposé une méthode efficace d’accélération des ACM basée sur l’écoute pas-sive du canal [UCR08]. Lorsqu’un nœud entend une interaction en cours dans son voisinage, ilest en mesure de connaître l’état du voisin incriminé, et peut alors déterminer quel destinatairechoisir pour sa prochaine interaction en choisissant celui qui possède l’état le plus différent dusien. Autrement dit, cette méthode cherche à minimiser l’écart maximal a priori.

Cette méthode présente cependant des inconvénients :– elle force le chipset RF à remonter tous les paquets protocolaires pour analyse par l’algo-

rithme, y compris les paquets non nécessaires (contrôles, acquittements).– si des paquets sont perdus, un nœud tend à acquérir une vision passée et faussée des états

de ses voisins qui peut entraîner une inefficacité de l’algorithme.

1.5 Interaction asymétriques & convolutions de BernoulliLes solutions algorithmes présentées jusqu’ici nécessitent l’acquittement systématique des

interactions. Sans cela, il est impossible de garantir que la convergence du consensus vers lavaleur moyenne des valeurs initiales des nœuds. Une question se pose alors : que se passe-t-ilsi on autorise des interactions non acquittées ? Le but de cette section est d’étudier certainespropriétés statistiques du point de consensus aléatoire obtenu. En particulier, nous verrons quela mesure de probabilité sous-jacente possède des caractéristiques fractales.

Dans cette partie, nous allons traiter un cas très simple qui reflète la complexité proba-biliste du point de consensus lorsque l’on abandonne les mécanismes de contrôle de réception.


Nous supposons que le réseau ne contient que deux nœuds avec des états initiaux x0 et y0. Lesvariables xn et yn représenterons respectivement l’état du premier et du second nœud, et nousposerons pour chaque itération n :

µn =xn + yn

2δn =

xn − yn2

Ces deux variables permettent de retrouver aisément xn et yn, mais possèdent surtout descomportements probabilistes beaucoup plus simples à étudier. Nous supposons que les nœudssouhaitent déclencher des itérations de poids 1−α préalablement fixé. En faisant abstraction desinteractions inutiles, nous considérons qu’avec une probabilité p0 le nœud 2 reçoit l’informationdu nœud 1 et procède à la barycentration, et inversement avec une probabilité 1− p0.

∀t ∈ N, Pr

[W (t) =

[1 0

1− α α

]]= p0 (1.44)

∀t ∈ N, Pr

[W (t) =

[α 1− α0 1

]]= 1− p0 (1.45)

Proposition 1.10 La variable aléatoire µn évolue suivant le système dynamique stochastique :

µn+1 = µ0 + (1− α)δ0

n∑k=0

εkαk (1.46)

où les εn sont des variables aléatoires i.i.d telles que :Pr [εn = 1] = p0

Pr [εn = −1] = 1− p0(1.47)

Preuve : µn+1 = µn + εn(1− α)δn

δn+1 = αδn(1.48)

D’où l’on tire δn = αnδ0 et :

µn+1 = µn + εn(1− α)αnδ0 (1.49)

= µ0 + (1− α)δ0

n∑k=0

εkαk (1.50)

Proposition 1.11 Soit la variable aléatoire de consensus asymptotique renormalisée Y∞ définiepar :

Y∞ = limn→∞

µn − µ0

(1− α)δ0

=∞∑k=0

εkαk (1.51)

alors la fonction caractéristique de Y∞ est donnée par :

E[eiωY

]=∞∏n=0

[p0e

iωαn + (1− p0)e−iωαn]

(1.52)

INTERACTION ASYMÉTRIQUES & CONVOLUTIONS DE BERNOULLI 37

Le cas particulier p0 = 1 − p0 = 1/2, µ0 = δ0 = 1/2 est connu dans la littérature sous lenom de convolution de Bernoulli. La question de la nature de la distribution de Y∞ dans ce cass’est posée pendant plus de 60 ans. Il a été démontré que cette distribution à des comportementspathologiques extrêmement différents suivant les valeurs de α. Dans la suite, on note Fα lafonction de répartition de Y∞ et να sa densité de probabilité. La fonction caractéristique de Y∞qui prend alors la forme :

E[eiωY

]=∞∏n=0

cos(ωαn) (1.53)

et Fα vérifie l’équation d’autosimilarité suivante [BK05] :

F (t) =1

2

[F

(t− 1

α

)+ F

(t+ 1

α

)](1.54)

Cette dernière équation suggère que να et Fα possèdent des propriétés (multi)fractales. Pourillustrer ce phénomène, la fonction de répartition du consensus obtenu pour deux nœuds, avecpour vecteur initial X0 = [01]T, et pour divers paramètres α et p0, ont été tracés sur les figures1.7 à 1.14. On constate plusieurs phénomènes intéressants, à savoir :

– une invariance d’échelle qui se traduit par des structures similaires après/avant zoom etcaractéristique des figures/fonctions fractales.

– une impossibilité à garantir un consensus localisé vers la moyenne : soit il y a une grandedéviation dès la première itération et la stabilisation est immédiate, soit de petits déplace-ments se cumulent et se stabilisent lentement sur un domaine large.

Nous avons volontairement tracé la fonction de répartition et non la fonction de densitécar celle-ci peut ne pas exister. C’est le cas, par exemple, si la mesure de probabilité est sin-gulière [BK05]. Or, les théorèmes suivants sur les convolutions de Bernoulli montrent que cettesingularité est un phénomène envisageable.

Proposition 1.12 (Jessen et Wintner, 1935)1. La fonction Fα est continue.2. La mesure να est absolument continue ou bien continue singulière.3. Pour α < 1/2, να est continue singulière. Plus précisément, le support de να est un

Cantor de mesure de Lebesgue nulle.

Proposition 1.13 (Erdös, 1939) Soit 1 < g < 2 un nombre de Pisot, i.e. un nombre algébriquedont les conjugués sont de module < 1, et α = 1/g. Alors να est singulière.

Proposition 1.14 (Solomnyak, 1995) Soit S ⊂]1/2, 1[ l’ensemble des valeurs α pour lesquellesνα est singulière. Alors S est de mesure de Lebesgue nulle.

La conclusion de cette section est claire : le contrôle de la convergence du consensus versla moyenne en présence de perte de paquet est un sujet sensible et complexe. Nous verrons auchapitre 4 une méthode qui autorise tout de même cette liberté : à la différence des résultatsde cette section, la qualité du consensus obtenu par rapport à la moyenne sera contrôlable àsouhait.


0

0.2

0.4

0.6

0.8

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.25p=0.25, α=0.4p=0.25, α=0.5p=0.25, α=0.6

p=0.25, α=0.75

Figure 1.7 – Consensus en présenced’asymétries, 2 nœuds (1)

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.5, α=0.25p=0.5, α=0.4p=0.5, α=0.5p=0.5, α=0.6

p=0.5, α=0.75


0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.75, α=0.25p=0.75, α=0.4p=0.75, α=0.5p=0.75, α=0.6

p=0.75, α=0.75


0

0.2

0.4

0.6

0.8

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.25p=0.5, α=0.25

p=0.75, α=0.25


0

0.2

0.4

0.6

0.8

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.4p=0.5, α=0.4

p=0.75, α=0.4


0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.5p=0.5, α=0.5

p=0.75, α=0.5


CONCLUSION 39

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.6p=0.5, α=0.6

p=0.75, α=0.6


0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fon

ctio

n de

den

site

cum

ulee

Point de consensus

p=0.25, α=0.75p=0.5, α=0.75

p=0.75, α=0.75


1.6 ConclusionDans ce chapitre, nous avons présenté les principes des ACM et certaines caractéristiques

de leurs performances. L’optimisation de leur vitesse de convergence est une tâche hautementnon-triviale., et l’existence et la proposition d’une méthode d’optimisation réellement distribuéesans coordination restent des questions ouvertes. Nous avons donc abordé ce problème par desapproches topologiques (propriétés du graphe de connectivité) et asymptotiques (comportementà haute densité).

En réponse au temps de convergence infini, nous avons proposé une construction pour dessolutions aléatoires en temps presque-sûrement fini, puis nous avons démontré que, contraire-ment à toute intuition, ces solutions sont nécessairement sous-optimales en termes de vitesse deconvergence.

Du point de vue de la robustesse, les ACM sont sensibles aux pertes de paquets, et né-cessitent donc l’utilisation systématique de mécanismes de contrôle de réception. Nous avonsdémontré que l’abandon de ces mécanismes de contrôle donne au point de consensus obtenuune distribution probabiliste de nature extrêment complexe.

Dans les prochains chapitres, nous nous attacherons en particulier à améliorer le fonction-nement de ces algorithmes et leur consommation énergétique en agissant sur des points pé-riphériques tels que :

– la prise en compte rapide d’informations nouvelles (chapitre 2)– l’exploitation de la nature diffusante du canal radio (chapitre 4)– l’abandon des mécanismes de contrôle de réception (chapitre 4)


41

Chapitre 2

Estimation et consensus de moyenneconjoints

Jusqu’ici, les algorithmes de consensus de moyenne rencontrés travaillaient sur des condi-tions initiales statiques. Cependant dans la réalité, ces conditions initiales peuvent être sujettesà des fluctuations, comme par exemple, lorsque ces données sont des quantités statistiques es-timées à partir de flots temporels d’échantillons bruitées. Le processus d’estimation agit commeun schéma de régularisation temporelle et l’amplitude des fluctuations diminue avec l’afflux dedonnées : il serait alors intéressant d’ajuster les états en cours dans l’algorithme de consensusde moyenne de manière à prendre en compte ces informations de meilleure qualité et précision.Dans le cas d’un bruit de mesure centré stationnaire, la qualité de l’estimation augmente avec lenombre de mesure, et par corollaire, avec le temps. Cependant, il peut sembler sous-optimal ouimpossible d’attendre que la mesure ait convergé avant de procéder à la régularisation spatiale.Pour répondre aux contraintes énergétiques sur les ressources des réseaux de capteurs, il devientalors nécessaire d’exécuter en parallèle l’algorithme de consensus et le processus d’estimationen utilisant des mécanismes de correction. Ce double processus doit être interprété comme unschéma de régularisation spatio-temporel : chaque nœud effectue localement l’extraction d’unequantité à partir des échantillons dont il dispose (estimation), pendant qu’une régularisationspatiale (consensus de moyenne) extrait une quantité globale. Cette approche est adoptée dans[XBL06b] mais les hypothèses sont trop restrictives : échanges et mises à jour synchrones,suites d’estimateurs de `2(N) (suites de carrés sommables ).

L’originalité de notre approche réside dans :– l’asynchronisme des échanges– l’asynchronisme des mises à jour des estimateurs à l’échelle du réseau et par rapport aux

échanges– la large gamme d’estimateurs pouvant être utilisés

et nous présenterons une application à la synchronisation fine au chapitre 3

2.1 Estimation et consensus de moyenne conjoints

Pour certaines applications, les paramètres à moyenner sont estimés à partir de flots demesures bruitées (échantillons). Une solution de consensus de moyenne et estimation conjoints

42 JEGA

est proposée pour la première fois en [XBL06b], mais ce travail repose sur des hypothèsesextrêmement restrictives en termes de synchronisation des communications et de type d’esti-mateurs (estimation LMS). Le problème reste ouvert concernant la recherche d’une solutiontotalement asynchrone tout en assurant la convergence pour une très large gamme d’estima-teurs locaux : par exemple, dans [XBL06b], la preuve de convergence n’est donnée que pourdes estimateurs dont les variances sont des séquences de l1(N). En général, ce n’est pas le cas(ex : estimation de variance). De manière similaire à [XBL06b], nous proposons d’exécuter unprocessus de régularisation spatial asynchrone (ACM), conjointement avec une régularisationtemporelle locale (estimation). La différence principale réside dans l’asynchronisme total entreéchanges de messages et/ou estimateurs locaux, les pondérations plus générales et le processusde rétroaction. Par ailleurs, nous donnons une preuve de convergence généraliste qui repose surl’hypothèse que les estimateurs ont des covariances tendant vers 0, sans aucune contrainte surla fréquence d’échantillonnage par exemple.

2.1.1 Processus d’estimation

Pendant une phase d’estimation, un nœud tente de retrouver un paramètre statistique in-connu, disons θ, à partir de données aléatoires (échantillons bruités). Un estimateur θ de θ estalors dit non-biaisé, si à chaque instant, E

[θ]

= θ. Dans ce chapitre, nous rencontrerons desprocessus d’estimation que nous qualifierons de propres, pour lesquels la variance tend vers0 lorsque le nombre d’échantillons disponibles augmente : il s’agit donc d’une régularisationtemporelle. C’est le cas, par exemple, de l’estimation de la moyenne d’une distribution à partird’échantillons i.i.d..

Exemple 2.1 Soit (vk)k∈N∗ une séquence de variables aléatoires i.i.d. suivant D(µ, σ). L’esti-mateur µn défini par

µn =1

n

n∑k=1

vk (2.1)

vérifie les relations suivantes :E [µn] = µ (2.2)

V [µn] =σ2

n−−−→n→∞

0 (2.3)

Cov (µm, µn) =σ2

max(m,n)−−−−−−−−→max(m,n)→∞

0 (2.4)

Autrement dit, l’estimateur µn de µ est non-biaisé et converge vers l’espérance µ de D.

Pour répondre au problème, un algorithme en deux phases aurait pu être proposé :

1. une phase d’estimation pendant une durée T0 correspondant à N0 échantillons.

2. une phase de consensus de moyenne de durée infinie.

Or cette solution est sous-optimale du point de vue de la qualité du consensus obtenu. En effet,supposons que l’on ait sur chaque noeud un estimateur non-biaisé θi d’une quantité θi au temps

ESTIMATION ET CONSENSUS DE MOYENNE CONJOINTS 43

T0. Le consensus de moyenne xavg obtenu en temps infini à partir de ces estimations est dès lorsaléatoire et vérifie les relations suivantes :

E [xavg] = E

[1

n

n∑i=1

θi

]=

1

n

n∑i=1

θi∆= xavg (2.5)

E[(xavg − xavg)2

]=

1

n2

∑i,j

Cov(θi, θj) ≥ 0 (2.6)

En général, ces covariances tendront vers 0 lorsque le nombre d’échantillons tendra vers +∞.En particulier, dans les conditions de l’estimation locale de l’espérance d’un ensemble de N0

échantillons indépendants (décorrélés spatialement) sur chaque capteur, on obtient :

E[(xavg − xavg)2

]=

1

nN0

∑i

σ2i (2.7)

Dans ce schéma, il est alors impossible d’obtenir une précision arbitraire sans arrêter la phased’acquisition. L’algorithme que nous allons présenter dans la section suivante résout ce prob-lème de manière purement locale, sans altérer la complexité du consensus de moyenne en termesde communication (contenu et nombre des messages échangés, modifications protocolaires).

2.1.2 Description de l’algorithmeL’algorithme JEGA se base sur le schéma standard (1.3), sur lequel se greffe une rétroaction

permettant d’introduire au plus vite les nouvelles informations qui proviennent des estimateurslocaux :

Xk+1 = WkXk + Zk+1 − Zk avec Z0 = X0 = [0 . . . 0]T (2.8)

Dans cette équation, Zk est un vecteur de Rn défini par Zk = [θ(k)1 , . . . , θ

(k)n ]

T, où θ(k)

i représentel’estimation courante du paramètre θi sur la base des échantillons disponibles au nœud i et autemps k. Comme ces estimateurs sont non-biaisé par hypothèse, alors E [Zk] est constant dansle temps :

Z∆= E [Zk] = [θ1, . . . , θn]T (∀k ≥ 1) (2.9)

Par la suite nous aurons besoin de définir le vecteur de déviation Bk par :

Bk∆= Zk − Z =

[b

(k)1 , . . . , b(k)

n

]T(∀k ≥ 1) (2.10)

ainsi que la covariance Cklij entre θi

(k)et θj

(l):

Cklij

∆= E

[(θi

(k)− θi

)(θj

(l)− θj

)]= E

[b

(k)i b

(l)j

](2.11)

Hypothèse 2.1 Les estimateurs sont asymptotiquement décorrélés :

∀(i, j) ∈ [1, n]2, Cklij −−−−−→

(k+l)→∞0 (2.12)

44 JEGA

Dans la majorité des applications orientées réseaux de capteurs, cette hypothèse n’est pas re-strictive. Cependant, elle est nécessaire pour mener à bien la preuve de convergence de l’algo-rithme, i.e. pour montrer que Xk converge bien vers (θi)i=1..n en termes de moments du premieret second ordre, tandis que Zk tend vers Z :

Xk −−−→k→∞

(1

n

n∑i=1

θi

)1 et Zk −−−→

k→∞Z = [θ1, . . . , θn]T (2.13)

Dans le système (2.8), la matrice aléatoire Wk est la même que pour le consensus de moyennestandard. Qualitativement, l’évolution de ce système est aisée. Les matrices Wk homogénéisentles valeurs du vecteur Xk tandis que celles de Zk se stabilisent : Zk+1 − Zk doit alors tendrevers 0 tandis que Xk tend vers un vecteur colinéaire à [1, . . . , 1].

Le terme Zk+1 − Zk entraîne une correction permanente du poids total du vecteur Xk. Onpeut en conclure qu’après un temps infini, la somme de ses composantes serait égale à celle descomposantes de Z. Dans les deux prochaines sections, nous donnerons une preuve formelle dece phénomène.

2.1.3 Convergence au premier ordreLe premier résultat stipule que la limite de Xk est naturellement le vecteur de consensus de

moyenne pour les paramètres à estimer, i.e. θ = 1n

∑ni=1 θi :

Proposition 2.1limk→∞

E [Xk] = θ1 (2.14)

Preuve : Dans cette preuve, nous tirons profit de la forme récursive du système (2.8) :

E [Xk+1] = E [WkXk + Zk+1 − Zk] = E [Wk] E [Xk] = WE [Xk] ∀k > 0 (2.15)

Pour k = 0, on a E [X1] = E [Z1] = Z, et donc s’en suit :

E [Xk+1] = W kE [Z1] = W kZ (2.16)

L’ergodicité de W implique alors que W k converge vers 1n11T lorsque k tend vers +∞. En

invoquant la relation (2.16), on obtient le résultat attendu : limk→∞

E [Xk] = 1n11TZ = θ1

2.1.4 Convergence au second ordreNous savons désormais que l’algorithme tend en moyenne vers le vecteur constant θ1, mais

la qualité de cette convergence doit être analysée : la distance entre le consensus de moyenneet le point de convergence devient-elle arbitrairement petite lorsque le nombre d’itération aug-mente ? Une réponse positive à cette question est démontrée par la suite. L’aspect techniquede cette preuve réside dans la nature aléatoire des matrices et vecteurs qui apparaissent dansl’algorithme, mais aussi du fait que les termes de covariances ne sont pas nécessairement dansun espace de type `p.

Les lemmes ci-dessous permettent de réduire temporairement la longueur de la démonstra-tion de la proposition 2.2. Le lecteur trouvera le détail de leurs preuves à l’annexe B.

ESTIMATION ET CONSENSUS DE MOYENNE CONJOINTS 45

Lemmes 2.1

a) limk→∞

E

[ZT

k−1∑i=1

Φ(k, i)Z

]= nθ2 −

∥∥Z∥∥2b) lim

k→∞E

[BTk

k−1∑i=1

Φ(k, i)Bi

]= 0

c) limk→∞

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Z

∥∥∥∥∥2 =

∥∥Z∥∥2 − nθ2 d) limk→+∞

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Bi

∥∥∥∥∥2 = 0

Proposition 2.2

limk→∞

E[∥∥Xk − θ1

∥∥2]

= 0 (2.17)

Preuve :

E[∥∥Xk − θ1

∥∥2]

= E[(Xk − θ1

)T (Xk − θ1

)](2.18)

Le terme de droite dans (2.18) peut se développer sous la forme :

E[XTkXk

]− 2θE

[1TXk

]+ E

[∥∥θ1∥∥2]

(2.19)

ce qui donne alors :

E[∥∥Xk − θ1

∥∥2]

= E[‖Xk‖2]− nθ2 (2.20)

L’objectif est maintenant de démontrer que E[‖Xk‖2] converge vers nθ2. Pour cela, on écrit le

système récursif (2.8) sous une forme plus efficace, en définissant les matrices Ψ(k, i) et Φ(k, i)par :

Ψ(k, i)∆=

I pour i ≥ k

Wk−1Wk−2 . . .Wi+1Wi sinon (2.21)

Φ(k, i)∆= Ψ(k, i)−Ψ(k, i+ 1) = Ψ(k, i+ 1)(Wi − I) (2.22)

En remplaçant Φ(k, i) et Ψ(k, i) dans l’équation (2.8), on obtient une formulation directe pourXk :

Xk = Zk +k−1∑i=1

Φ(k, i)Zi with Z0 = X0 = [0 . . . 0]T (2.23)

Cette formulation sera plus pratique à manipuler pour prouver la convergence du momentdu second ordre de Xk, où des majorations classiques comme développées dans [BGPS05]échoueraient.

Comme on l’attend de l’expression (2.23), E[‖Xk‖2] s’écrit en fonction des moments du

second ordre des mesures :

E[‖Xk‖2] = E

[‖Zk‖2]+ 2E

[ZTk

k−1∑i=1

Φ(k, i)Zi

]+ E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Zi

∥∥∥∥∥2 (2.24)

46 JEGA

La limite du premier terme s’obtient facilement :

limk→∞

E[‖Zk‖2] = lim

k→∞

n∑p=1

E[(θ(k)p

)2]

= limk→∞

n∑p=1

(Ckkpp + E

[θ(k)p

]2)(2.25)

=n∑p=1

(limk→∞

Ckkpp + θ2

p

)=

n∑p=1

θ2p =

∥∥Z∥∥2 (2.26)

Afin de rendre la preuve plus claire, les deux derniers termes de l’équation (2.24) peuvent êtredécomposés en séparant les composantes aléatoires et déterministes :

E

[ZTk

k−1∑i=1

Φ(k, i)Zi

]= E

[ZT

k−1∑i=1

Φ(k, i)Z

]+ E

[BTk

k−1∑i=1

Φ(k, i)Bi

]

+ E

[BTk

k−1∑i=1

Φ(k, i)Z

]+ E

[ZT

k−1∑i=1

Φ(k, i)Bi

](2.27)

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Zi

∥∥∥∥∥2 = E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Z

∥∥∥∥∥2+ E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Bi

∥∥∥∥∥2

+ 2E

(k−1∑i=1

Φ(k, i)Z

)T(k−1∑i=1

Φ(k, i)Bi

) (2.28)

Comme les vecteurs de bruitBi sont centrés, les termes croisés de (2.27) et (2.28) disparaissent :

E

[ZTk

k−1∑i=1

Φ(k, i)Zi

]= E

[ZT

k−1∑i=1

Φ(k, i)Z

]+ E

[BTk

k−1∑i=1

Φ(k, i)Bi

](2.29)

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Zi

∥∥∥∥∥2 = E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Z

∥∥∥∥∥2+ E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Bi

∥∥∥∥∥2 (2.30)

Grâce aux lemmes 2.1.a) à 2.1.d), on obtient la limite du terme E[‖Xk‖2] quand k tend vers

+∞ :E[XTkXk

]−−−→k→∞

∥∥Z∥∥+ 2(nθ2 −∥∥Z∥∥) + (

∥∥Z∥∥− nθ2) = nθ2 (2.31)

L’équation (2.20) et la relation (2.31) permettent de conclure la preuve de la proposition 2.2.

2.2 Simulation et analyseLa vitesse de convergence de JEGA est encore inconnue à l’heure actuelle. Cependant,

comme nous allons le voir, des heuristiques intuitives peuvent se déduire à partir de simulations.

SIMULATION ET ANALYSE 47

n 50d 1r 0.25

σ 0, 0.01, 0.1, 1, 10Niter 10000Navg 500

Tableau 2.1 – Paramètres de simulation

2.2.1 Conditions de simulationsDans cette partie, un réseau de capteurs est modélisé comme suit : n nœuds sont distribués

aléatoirement et uniformément dans un carré de largeur d, et deux nœuds sont voisins si leurdistance euclidienne est au plus unitaire. Par soucis de simplicité, chaque nœud obtient unéchantillon par itération et met à jour directement son estimateur local. Par contre, une seulepaire de nœuds interagit durant une itération. Un initiateur i est choisi de manière uniformé-ment aléatoire, tandis que la destination j est aussi prise uniformément dans le voisinage dunœud i. Les bruits de mesures sont des variables aléatoires additives, i.i.d., distribuées suiv-ant une loi Gaussienne centrée et d’écart-type σi au nœud i. Les composantes du vecteur Zsont prises de manière aléatoires, arbitrairement dans l’intervalle [0, 1], et fixées pour toutesles simulations. Nous enregistrons alors l’évolution de l’erreur quadratique moyenne (EQM),i.e. E

[∥∥Xk − θ1∥∥2], pendant Navg simulations de Niter itérations, et pour des valeurs de σ

identiques pour tous les nœuds1 à préciser.

2.2.2 Résultats et heuristiquesLes résultats de trois types de simulations comparatives vont être décrits dans cette partie.

Impact de la variance des échantillons

Dans cet ensemble de simulations, l’écart type du bruit de mesure (= écart type des échan-tillons) est choisie dans l’ensemble 0, 0.01, 0.1, 1, 10. Le cas σ = 0 correspond clairementà un consensus de moyenne classique car la rétroaction de JEGA s’annule. Cependant, ce casn’est pas dénué d’intérêt car il servira de point de référence pour la vitesse de convergence. Lesrésultats de ces simulations peuvent être visualisés sur la figure 2.1.

Dans le cas parfait (aucun bruit de mesure), on reconnait la convergence de type pluri-géométrique de l’ACM standard, dominée pour k grand de la manière suivante :

E[∥∥Xk − θ1

∥∥2]≤ [λ2(W )]kE

[∥∥X0 − θ1∥∥2]

(2.32)

Une preuve de cette inégalité est donnée dans [BGPS05]. Dans le cas général, on observe deuxtypes de vitesse de convergence : dans un premier temps, les composantes du vecteur Xk s’ho-mogénéisent comme si les rétroactions étaient déconnectées (entrées constantes des ACM clas-siques [XBL05]). Dans un second temps, la régularisation spatiale semble instantanée tandisque l’erreur d’estimation décroît lentement vers 0.

1le cas σ = 0 correspond à l’ACM classique

48 JEGA

1e-10

1e-08

1e-06

0.0001

0.01

1

100

10000

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

EQ

M

Iteration

σ=0 (ACM classique)σ=0.01

σ=0.1σ=1

σ=10

Figure 2.1 – JEGA - EQM E[∥∥Xk − θ1

∥∥2]

pour différentes variances

Impact de la connectivité

Dans cette sous-section, nous faisons varier deux paramètres :– le rayon de connectivité : choisi dans l’ensemble 0.20, 0.350.5.– l’écart type du bruit de mesure 0, 0.1, 1.

Les résultats de ces simulations peuvent être visualisés sur la figure 2.2.

Dans le cas σ = 0, les résultats sont ceux d’un ACM classique avec des conditions initiales sta-tiques. On retrouve le résultat empirique stipulant qu’augmenter le rayon de connectivité permetd’accélérer l’algorithme : l’erreur quadratique moyenne a une pente plus forte en échelle loga-rithmique. Par ailleurs, on observe qu’après la transition de phase la convergence n’est quasi-ment plus dictée par l’algorithme de consensus mais par le processus d’estimation. Lorsquele rayon de connectivité est faible, la figure 2.2 laisse penser que JEGA converge à la mêmevitesse que l’ACM. En réalité, le résultat précédent reste valable asymptotiquement : il faudraitvisualiser l’EQM sur une échelle temporelle beaucoup plus grande pour visualiser à nouveauque la vitesse de convergence asymptotique est du même type que l’estimation.

Il faut cependant noter que ceci reste valable tant que la vitesse de convergence du processusd’estimation est négligeable par rapport à celle d’un ACM (géométrique). Par exemple, dans lecas d’un estimateur de moyenne, nous avons vu que la convergence ce faisait en O( 1

N) où N est

le nombre d’échantillons, tandis qu’un ACM converge en O(λt), avec 0 < λ < 1.

SIMULATION ET ANALYSE 49

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

10

100

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

EQ

M

Iteration

r=0.2, σ=0 (ACM classique)r=0.2, σ=0.1

r=0.2, σ=1r=0.35, σ=0

r=0.35, σ=0.1r=0.35, σ=1r=0.5, σ=0

r=0.5, σ=0.1r=0.5, σ=1

Figure 2.2 – EQM E[∥∥Xk − θ1

∥∥2]

2.2.3 Comparaison avec un algorithme en deux phasesLe but de ce jeu de simulations est d’illustrer la sous-optimalité d’un algorithme en deux

phases par rapport à JEGA. Pour rappels, il s’agit d’une phase d’estimation pendant une duréeT0 suivie d’une phase de consensus de moyenne dont les conditions initiales sont les estimationsobtenues à T0. Pour des raisons de simplicité, nous supposerons que les conditions suivantes :

– la variance du bruit de mesure est fixée à 1.– le temps est divisé en T0 unités temporelles.– chaque capteur obtient un nouvel échantillons à chaque unité temporelle.– les nœuds démarrent les différentes phases en même temps.

En parallèle, l’algorithme JEGA sera exécuté dans les mêmes conditions pour comparaison, etles résultats sont visibles sur la figure 2.2.

Deux phénomènes attendus sont remarquables sur cette figure. Tout d’abord, la version en deuxphase tend vers un consensus dont la variance n’est pas nulle contrairement à l’algorithmeJEGA : quelque soit le nombre d’échantillons à partir desquels on lance l’ACM, il reste uneincertitude sur le consensus de moyenne. Cette incertitude diminue lorsque le nombre d’échan-tillons augmente vers +∞, mais le temps de latence avant d’obtenir une estimation correcte duconsensus augmente par la même occasion. Ceci est d’autant plus pénalisant que l’informationdisponible localement avant T0 est de très faible qualité (plateaux en fin de phase d’estimation)en comparaison à celle que l’on peut obtenir pendant la phase de consensus.

Ensuite, on pourrait sélectionner, à un instant donné, l’algorithme en deux phases donnantla variance de consensus la plus faible (autrement dire sélectionner le meilleur T0). Or à la vue

50 JEGA

0.001

0.01

0.1

1

10

100

1000

10000

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

EQ

M

Iteration

T0=1T0=25T0=50

T0=100T0=250T0=500

T0=1000T0=2500T0=5000

JEGA

Figure 2.3 – Comparaison de JEGA avec un algorithme en deux phases - EQM E[∥∥Xk − θ1

∥∥2]

de la figure 2.2, l’algorithme JEGA donne pour chaque instant un résultat équivalent à celui dela meilleur solution en deux phases. Comme sa complexité en termes de communications estidentique à celle d’un ACM standard, la rétroaction introduite dans JEGA prend tout son intérêt.

2.3 ConclusionDans ce chapitre, nous avons proposé un nouvel algorithme asynchrone d’estimation et con-

sensus de moyenne conjoints, pouvant s’appliquer à des problème d’estimation distribuée, decartographie, ou de synchronisation (cf chapitre 3). Il généralise le schéma spatio-temporel in-troduit dans [XBL06b] et sa convergence a été prouvée en termes de moments du premier etsecond ordre. Cet algorithme se base sur des interactions locales qui en font une solution adaptéeau contexte des réseaux de capteurs. Sa vitesse de convergence exacte reste une question ou-verte. Cependant, des résultats empiriques issus de simulations ont été fournis. De nombreusesapplications peuvent être envisagées, comme par exemple l’extraction de paramètres en radiocognitive ou l’extraction/fusion d’information dans les réseaux de capteurs. Dans le chapitesuivant, nous présentons une application à la synchronisation fine d’horloges.

51

Chapitre 3

Une application à la synchronisation fine

Dans les réseaux de capteurs, de nombreux problèmes apparaissent à cause de l’hétérogénéitéet du comportement dynamique des nœuds. Un exemple d’obstacle est le déploiement d’uneméthode de partage temporel des ressources canal (TDMA, Slotted-ALOHA, ...). Ce challengerepose essentiellement sur la capacité du réseau à se synchroniser à plusieurs échelles. Par syn-chronisation fine, nous entendons l’homogénéisation des dérives d’horloges, en opposition à ladéfinition donnée dans [Els03] et [ER02]. L’impact de ce type de synchronisation est important :elle permet de réduire la taille des préambules, et donc, d’augmenter la proportion de données.Dans cet article, nous utilisons un algorithme de consensus de moyenne simple pour calculerles corrections d’horloges nécessaires à la synchronisation fine. Cette solution peut se grefferde manière symbiotique sur d’autres protocoles comme par exemple DV-Hop [NN01] ou unalgorithme de routage de données.

La précision temporelle partagée est cruciale pour certaines fonctionnalités qui s’appuientsur la qualité statistique des mesures effectuées par rapport à des références datées. Celle-ci estassurée par la stabilité et l’homogénéité des horloges et de leurs paramètres (biais, dérive) ausein d’un groupe de nœuds-capteurs. L’ensemble de ces paramètres sont en réalité indexés parune variable : la dérive, c’est à dire l’évolution du biais de l’horloge par rapport à une base detemps universelle. Par exemple, le lien entre le temps local d’une horloge et le temps universelt est généralement décrit par la formule intégrale suivante ([R01]) :

T (t) = T0 +

∫ t

t0

ε(t)dt (3.1)

où ε(t) est la dérive instantanée, et T0 le biais par rapport au temps universel t0 (voir[Pie05]). Dans le même article, il a été rappelé que les performances de radiolocalisation dansles systèmes ultra large bande (UWB) sont dégradées par des imprécisions dues aux écarts dedérives d’horloges. De manière plus importante, cela concerne un large éventail de systèmesutilisés en radiocommunications dont quelques exemples sont les protocoles de synchronisa-tion grossière (ECMA 368), les méthodes d’accès au médium (TDMA, Slotted-ALOHA), oubien encore les techniques de modulation (OFDM).

La section suivante débute par une rapide introduction aux algorithmes bavards (gossip)et rappelle quelques définitions de théorie des graphes. Après une description du procédé demesure des rapports de dérives d’horloges (RDH) et de sa modélisation, on propose une combi-naison des mesures à des fins de moyennage en prenant l’opportunité de réutiliser les principes

52 UNE APPLICATION À LA SYNCHRONISATION FINE

de diffusion de l’information déployée en particulier dans les protocoles de routage et/ou du typeDV-Hop. Notre solution repose sur l’utilisation simultanée de deux mécanismes asynchrones.Les calculs de moyennes :

– temporelle du RDH entre chaque nœud et une référence choisie– spatiale de ces RDH avec possibilité de rétro-correction

L’algorithme JEGA (cf chapitre 2) apparaît naturellement comme une brique de base de laméthode que nous présentons dans ce chapitre.

3.1 Algorithme bavard de synchronisationNous allons poser dans cette section les bases pour l’application de JEGA au problème

de la synchronisation fine de dérives d’horloges. La solution présentée fournit une méthodepour atteindre un consensus de moyenne sur les dérives d’horloges. Pour arriver à cet objectif,deux processus sont exécutés parallèlement : un mécanisme de propagation et un algorithmede moyennage distribué. La convergence vers le consensus repose sur l’estimation des RDHentre chaque nœud et la référence préalablement choisie (balise). Comme nous le verrons par lasuite, ces valeurs suffisent pour calculer la correction nécessaire à apporter à chaque horloge. Letype de référence (GPS, station de base, capteur, ...) et sa couverture réseau impacte de manièresignificative la qualité de l’estimation et la vitesse de convergence.

3.1.1 Arbres recouvrants et notations de la théorie des graphesSoit G = (V , E) un graphe non orienté, un arbre recouvrant T sur G est un sous-graphe

connexe acyclique de G ayant le même ensemble de sommets. Dans la suite, dG(i, j) dénote ladistance naturelle entre deux sommets i et j, i.e. la longueur en nombre d’arêtes du plus courtchemin reliant i et j. Un sommet de T reçoit le statut de racine (ou balise). Cette particularitéinduit un ordre partiel entre nœuds voisins de T conformément à la distance qui les sépare dela racine : p est l’unique parent de q, et on note p = π(q) et q ∈ π−1(p), lorsque (p, q) ∈ ET

et dT(p,R) < dT(q,R). Sur un arbre, le plus court chemin entre deux sommets est trivialementunique : on représente sans ambigüité par Γ(i, j) l’ensemble des sommets rencontrés sur le pluscourt chemin reliant i et j et incluant ces deux extrémités.

3.1.2 Mesure de dérive d’horloge et estimationNous supposons être dans la capacité de mesurer le rapport de dérive entre deux nœuds i

et j, i.e. γij = εi/εj , du côté du récepteur (i). Une manière d’obtenir ce rapport est présentéedans [Pie05], où l’auteur propose de mesurer la durée d’un paquet de longueur connue, rela-tivement au temps local du récepteur. Une autre solution classique est d’estimer le décalage defréquence à la sortie du système de détection/synchronisation de préambule (PLL par exem-ple) utilisé pour la réception des paquets. Indépendamment de la manière selon laquelle nousobtenons cette mesure, nous supposons que les RDH sont connus à un bruit bij(τ) près, centré(pas nécessairement gaussien) d’écart-type σij :

γij(τ) = γij + bij(τ) avec σ2ij

∆= V [bij] (3.2)

ALGORITHME BAVARD DE SYNCHRONISATION 53

La puissance des bruits extérieurs (bruit thermique et interférences) affecte σij mais, pourune raison de simplicité, bij est pris stationnaire temporellement. Dans [Pie05], σij est unefonction linéaire du rapport εi/∆, où ∆ représente la longueur supposée d’un paquet. Par Tij ,nous désignons l’ensemble des temps de mesure de γij . On définit par la même occasion Tij(t)et µij(t) comme étant :

Tij(t)∆= Tij ∩ [0, t] µij(t)

∆= Card (Tij(t))

Dans notre protocole, on suppose que les dérives d’horloges restent constantes ou varient demanière extrêmement lente en comparaison avec le temps de convergence de notre algorithme.De plus les mesures de γij , i.e. γij(.), sont modélisées par des variables aléatoires indépendantesmais identiquement distribuées. Si en particulier ces mesures suivent une loi normale, l’estima-teur de moyenne classique de l’équation (3.3) sera optimal au sens de Cramér-Rao [Poo98] :

γij(t) =1

µij(t)

∑t′∈Tij(t)

γij(t′) (3.3)

3.1.3 DV-Hop et liens arborescentsDV-Hop est un protocole de localisation grossière de nœuds pour les réseaux sans-fil ad-

hoc développé par Niculescu et Nath [NN01]. Dans ce système, les nœuds qui connaissent leurposition réelle (à l’aide d’un GPS, ...) sont appelés balises. Chaque balise transmet sa positionpar diffusion à l’ensemble des entités du réseau. Chaque nœud met à jour une estimation localede sa position en ayant recours à un procédé de trilatération qui utilise la position réelle desbalises ainsi que la distance liée au nombre de sauts depuis celle-ci. L’idée développée dans cetarticle est d’utiliser le mode de propagation des procédures de diffusion du type DV-Hop pourcréer la structure d’arbre qui est nécessaire. Ce contexte offre un cadre simple pour calculer lesRDH entre n’importe quel nœud et une référence (balise DV-Hop par exemple). Par soucis declarté, on réduit le nombre des indices en désignant par p le couple (p, π(p)), i.e. le nœud p etson parent dans l’arbre recouvrant :

γp∆= γp,π(p), γp(t)

∆= γp,π(p)(t) (3.4)

Avec ces notations il est plus aisé de décrire la phase de propagation de notre algorithme.Le principe proposé estime récursivement le RDH entre un nœud et la balise, en chaînant lesestimations de RDH par le biais de variables z.(.) propagées numériquement :

zR(t) = 1, zi(t) = zπ(i)(τπ(i)i(t))γi(t) =∏

p∈Γ(R,i)p6=R

γp(τqi(t)) (3.5)

où τqi(t) représente la date de l’information γq contenue dans le dernier paquet reçu par ijusqu’au temps t. Dans l’équation (3.5), chaque terme du produit est une estimation de la formeεp/επ(p) indépendante des autres. Il en résulte, comme le montre l’équation (3.7), que zi· est unestimateur non biaisé de εi/εR.

E [zi(t)] =∏

q∈Γ(R,p)q 6=R

E [γq(τqi(t))] =∏

q∈Γ(R,p)q 6=R

γq = γiR =εiεR

(3.6)


De plus, lorsque les chemins qui joignent respectivement les nœuds i et j, éventuellementidentiques, àR bifurquent au nœud p, i.e. p est le nœud de Γ(i, R)∩Γ(j, R) à distance maximalede R, nous pouvons écrire les comoments des estimations :

E [zi(s)zj(t)] = γipγjp∏

q∈Γ(R,p)q 6=R

(γ2q +

σ2q

µq(τqi(s)⊗ τqj(t))

)(3.7)

où t1⊗t2 signifie maxt1, t2. L’équation (3.7) nous permet d’accéder aux termes de covarianceCstij pour chaque paire de nœuds (i, j) :

Cstij = Cov (zi(s), zj(t)) = E [zi(s)zj(t)]− γiRγjR (3.8)

Il est réaliste de supposer que les flux de paquets sont suffisamment soutenus pour fairetendre µp(t) vers +∞ avec le temps, pour chaque p 6= R du réseau. En utilisant les notations deLandau par rapport à la variable temporelle s+ t, nous déduisons de (3.7) que :

E [zi(s)zj(t)] = γipγjpγ2pR + o(1) (3.9)

En la combinant avec (3.8) cette équation permet de vérifier l’hypothèse cruciale de l’algorithmeJEGA :

lim(s+t)→∞

Cstij = 0 (3.10)

3.1.4 Correction de dérive de la référenceRappelons que la particularité de JEGA réside dans le fait qu’il est initialement conçu pour

les situations où les paramètres sont estimés dans un premier temps puis la moyenne est cal-culée. JEGA permet la parallélisation de ces tâches de moyennage et d’acquisition des observa-tions. Il réduit le temps de latence pour l’obtention d’une estimée de la valeur moyenne recher-chée. Les estimées des paramètres à moyenner sont stockées dans le vecteur n-dimensionnelZt :

Zt = [zR(t), z1(t), . . . , zn−1(t)]T (3.11)

Dans notre cas, chaque composante de Zt dénotera en réalité l’estimation de γpR au tempst. Par le biais de l’équation (3.10), les pré-requis de JEGA sur la covariance d’estimation sontrespectés, et sa convergence est statistiquement assurée. Dans la suite, Xt représente le vecteurd’état n-dimensionnel des estimées de la valeur moyenne (spatiales) recherchée :

Xt∆= [xR(t), x1(t), . . . , xn−1(t)] (3.12)

Avec ces notations, les itérations de JEGA peuvent être mise sous la forme d’une simple équa-tion aux différences :

Xt+1 = WtXt + Zt+1 − Zt , X0 = Z0 = 0n (3.13)

où 0n est le vecteur nul, etZt représente le vecteur des estimations de RDH obtenues à l’itérationprécédente : il faudra éventuellement redimensionner le numéro d’itération t pour donner tout

ALGORITHME BAVARD DE SYNCHRONISATION 55

son sens à µp(t). En pratique, cela ne présente aucune difficulté car les occurrences du tempsdisparaissent dans l’aspect protocolaire. L’espace mémoire requis est minime puisque chaquenœud p n’accumule que ses propres composantes : xp(t), zp(t) et zp(t− 1).

Contrairement à la phase de propagation, les interactions de moyennage ne se limitent pasau seul arbre recouvrant, mais mettent en jeu toutes les relations de voisinage du graphe deconnectivité initial. Nous avons vu précédemment que les hypothèses faites sur le réseau et lesquantités stochastiques satisfont les conditions d’utilisation de JEGA. Par ailleurs, un asynchro-nisme entre la phase de propagation et les itérations de JEGA peut être considéré sans aucunproblème.

Comme zi(t) est une estimation de γiR, alors X(t) converge vers le vecteur X∞ défini par :

X∞ =1

n

∑i∈V

εiεR

=ε

εR1 (3.14)

où ε est la valeur moyenne des RDH. L’équation (3.14) implique directement que chaque nœudi est capable de calculer la correction de fréquence d’horloge dont il a besoin via :

∀i ∈ V , limt→+∞

xi(t)

zi(t)=

ε

εi(3.15)

Nous n’avons fait aucune hypothèse quant à la fréquence des interactions et à la stratégiede choix des voisins. Ces deux points sont fortement liés aux performances de l’algorithme entermes de vitesse de convergence.

3.1.5 Algorithme completNotre solution repose essentiellement sur la construction d’un arbre recouvrant. Cette tâche

peut être exécutée de manière simple en tirant profit de n’importe quel processus de diffusion. Ilfaut noter qu’un nœud n’a besoin d’avoir connaissance que de l’identité de son père et non de lastructure complète de l’arbre. Une fois les relations père-fils définies, chaque nœud peut trans-mettre sa valeur xi(t) à un de ses voisins, et s’ils ont un lien de parenté, le père enverra aussiz•(•). Ainsi l’algorithme dans une de ses versions les plus simples prend la forme suivante :

Construire un arbre recouvrant;tant que Critère d’arrêt non satisfait faire

si Réception d’un paquet de propagation alorsmesurer γp et rafraîchir γp;calculer zp(t) = γpzπ(p);stocker et propager zp aux nœuds de π−1(p);

finsi Réception ou émission d’un paquet JEGA alors

Procéder à l’itération de JEGA;si Voisin = π(p) alors

mesurer γp et rafraîchir γp;fin

finfin

Algorithme 2 : Synchronisation fine


Afin de réduire le temps de latence dû à la faible vitesse de convergence de l’algorithme demoyennage, il est possible d’appliquer ces corrections à tout moment sur les horloges. Cepen-dant, il est nécessaire d’identifier les paquets corrigés et de garder un flot sans correction.

3.2 Résultats et performances

3.2.1 Hypothèses de simulationSans perte de généricité, on choisi de distribuer les nœuds de manière uniforme sur un rect-

angle S de dimensions D × d, et on connecte les paires séparées par une distance inférieure àRmax (modèle booléen). Seules sont retenues les configurations telles que le graphe de connec-tivité G est connexe. L’arbre recouvrant T est construit de manière aléatoire sur G et la racine estchoisie de manière uniforme parmi les nœuds. Les dérives d’horloges sont distribuées suivantune loi normaleN (µ0, σ0). Les bruits de mesure (aussi gaussiens) ont une variance σ2

ij = σ2Bεi.

Un nœud est choisi de manière uniforme à chaque itération et initie une interaction avec un deses voisins choisi lui aussi uniformément. Cela correspond au schéma d’itération du moyennagegossip classique de [BGPS06].

λ 0.006D × d 100× 500 mn 33

Rmax 20 mtmax 105

Nsim 1000

µ0 1σ0 33 ppm

min εi − 1 −5.7× 10−5

max εj − 1 7.9× 10−5

σB 10−4

Tableau 3.1 – Conditions de simulation - graphe de connectivité du réseau et valeurs desparamètres

3.2.2 AnalyseComme nous l’avions prédit, chaque terme xi(t) converge vers ε/εR (fig. 3.2) avec des es-

timations locales de γiR qui ne sont pas altérées. Ainsi, lorsqu’un nœud calcule son propre ε/εi(fig. 3.1), il bénéficie du moyennage des xi(t) mais pas des γiR. Ce phénomène est perceptiblesur les figures 3.3 et 3.4. La vitesse de convergence des RDH ralentit drastiquement et suit celledes estimées γiR. Notons qu’aucune hypothèse n’a été faite au sujet de la couche MAC et deséchanges simultanés sont possibles.

Comme précisé au chapitre 2, la vitesse de convergence exacte de JEGA est inconnue, maisde simples considérations intuitives peuvent être formulées pour expliquer le comportementglobal de l’erreur quadratique moyenne (EQM) en fonction du temps (fig. 3.3 et 3.4). Plusspécifiquement, lorsque la variance du bruit de mesure est faible par rapport à la dispersiondes termes γiR on observe une transition dans la pente de l’EQM. On conjecture que JEGA setrouve alors dans deux états différents. Le premier traduirait une homogénéisation grossière des

CONCLUSION 57

composantes du vecteur d’état Xt comme si les estimations étaient constantes. Le second cor-respond à la lente disparition du bruit d’estimation. L’erreur engendrée disparaît à une vitessebeaucoup plus lente que l’erreur de moyennage. Pour argumenter ce fait, la variance d’estima-tion décroît de manière inversement proportionnelle au nombre d’échantillons (i.e. αt−1) alorsque l’erreur de moyennage décroît exponentiellement avec le nombre d’itérations (au moins enαλt2 où λ2 < 1 est la seconde plus grande valeur propre de E [Wt], [BGPS06]). Ainsi, les courbessur les figures 3.3 et 3.4 décroissent vers 0 lorsque t augmente. Lorsque la transition a eu lieu,nous pouvons considérer que les corrections des estimations sont immédiatement propagées parJEGA. De plus, nous avons utilisé l’estimateur de moyenne classique qui est connu pour êtreoptimal au sens de Cramér-Rao [Poo98] dans le cas d’un bruit gaussien. Cette optimalité a desconséquences importantes sur la vitesse de convergence de l’algorithme qui est bornée par lavariance des estimateurs sans amélioration des performances.

3.2.3 Optimisation et robustesseIl existe de nombreuses manières d’améliorer conjointement les performances et la ro-

bustesse de notre algorithme. Par exemple il est envisageable d’utiliser plusieurs points deréférence et arbres de recouvrement imbriqués. Plus tard, nous souhaiterions nous affranchirtotalement de la notion d’arbre de recouvrement et prendre appui sur des méthodes de diffusiondéployées dans des protocoles de routage. Il faut noter que le point de convergence de notrealgorithme ne dépend pas du recouvrement utilisé et rien ne s’oppose à la construction d’unarbre optimal en utilisant la variance des dérives comme métrique. D’autre part, si le nombrede nœuds est suffisamment grand, il est alors possible de synchroniser des grappes de nœuds enconsidérant que les dérives finales seront statistiquement proches.

3.3 ConclusionNous avons présenté un algorithme distribué pour homogénéiser les dérives d’horloges dans

un réseau de nœuds-capteurs. La solution proposée est robuste au bruit de mesure, légère etfacile à implémenter. En accord avec la philosophie d’économie dans ce domaine, on utiliseles informations déjà apportées par des protocoles de fonctionnalités préexistantes pour ali-menter l’algorithme distribué de synchronisation. Certaines d’entre elles pourront rétroactive-ment bénéficier d’une meilleure précision temporelle. Cette qualité est d’une grande importancepour les applications telles que les algorithmes de radiolocalisation ou les protocoles d’alloca-tion de ressources canal datés (TDMA...). Des études sont poursuivies sur ce type d’algorithmeafin d’améliorer l’insensibilité aux changements de topologie, la robustesse et les performancestout en restant symbiotique avec les algorithmes proposés pour réaliser d’autres objectifs duréseau de capteurs.


Figure 3.1 – Estimations de la dérive beacon/moyenne zi(t) en fonction du temps

Figure 3.2 – Dérives corrigées xi(t)zi(t)

εi(t) en fonction du temps

CONCLUSION 59

Figure 3.3 – E[max

∣∣ εi−εε

∣∣] en fonction du temps

Figure 3.4 – E[‖~ε(t)/ε− 1‖2] en fonction du temps


61

Chapitre 4

Asynchronie et régularisation

Notons zavg la moyenne empirique des quantités zi à moyenner (mesures par exemple).Lorsque ces valeurs sont sujettes à un a priori d’ordre probabiliste, des techniques d’estimationtelles que celles présentées dans [Now03] ou [DZ06] peuvent être adoptées pour calculer zavg.Mais lorsque ce n’est pas le cas, la solution de l’état de l’art la plus simple et la moins couteuseen coordination est donnée dans [BGPS04] : cette méthode consiste à calculer des barycentresdes états entre paires de voisins de manière aléatoire et en prenant comme conditions initialesles données à moyenner. Cependant, cette solution nécessite un acquittement systématique deséchanges d’informations. Sans cette précaution, l’algorithme converge effectivement mais versun consensus imprévisible. De plus, les mécanismes d’acquittement deviennent pénalisants enmilieu interférent comme c’est le cas sur un canal de communication radio. Le but de ce chapitreest de proposer une nouvelle solution asynchrone qui ne souffre pas de ces inconviénients et quitire profit de la nature diffusante du canal radio.

4.1 PrincipeLa méthode que nous proposons s’inspire de techniques utilisées en traitement d’images a

des fins de débruitage/lissage ou de segmentation automatique (voir par exemple [GFD+02],[Nik05], [CBFAB97]). Parmi d’autres, deux méthodes méritent d’être citées. La première con-siste en un simple filtrage convolutif à moyenne mobile bidimensionnel appliqué directementaux pixels de l’image. La deuxième technique repose sur l’utilisation d’une fonction d’én-ergie/potentiel. Celle-ci traduit à l’aide de fonctions de couplage les prérequis suivants :

– l’image obtenue x doit être fidèle à l’image originale z.– les pixels voisins dans z doivent se ressembler.

Ceci justifie alors la minimisation de fonctions d’énergie U du type suivant :

U =∑i

(xi − zi)2 + βn∑i=1

∑j∼i

(xi − xj)2 (4.1)

que l’on reduira à l’écriture :

U =∑i

(xi − zi)2 + β∑i∼j

(xi − xj)2 (4.2)

62 ASYNCHRONIE ET RÉGULARISATION

Figure 4.1 – Caméraman avant lissage

β = 0 β = 1 β = 10 β = 100 β = 1000

Figure 4.2 – Caméraman après lissage

Ici l’index i parcourt l’ensemble des pixels de l’image et les relations de voisinages entre pixelssont notées par ∼. Lorsque β tend vers +∞, on s’attend à ce que les intensités des pixels devi-ennent similaires. A des fins d’illustrations, appliquons cette méthode à la tête du caméramande l’image de la figure 4.1, et observons alors l’image optimale obtenue pour différentes valeursde β sur les images de la figure 4.2.

Le cas β = 0 correspond à l’image originale car minimiser U =∑

i(xi− zi)2 revient à fixerxi = zi, ∀i. On constate bien le phénomène attendu : lorsque β augmente, l’histogramme desniveaux de gris de l’image se concentre autour d’un pseudo-consensus. L’idée est alors d’ap-pliquer ce concept aux réseaux de capteurs en remplacer les pixels par les nœuds-capteurs, leurintensité par la valeur d’une mesure locale, et les relations de voisinages entre pixels par les rela-tions de voisinages dans le réseau (communication à 1 saut par exemple). Il est de plus possible

PRINCIPE 63

de généraliser la fonction de potentiel obtenue en autorisant un nombre arbitraire (éventuelle-ment nul) de mesures locales, des fonctions de couplages non-quadratiques, et des coefficientsde couplages β• propres à chaque paire communicante.

U(X) =∑i,l

αilψa(xi − zl) +∑i,j

βijψn(xi − xj) (4.3)

Ce type de formalisation est utilisé pour le débruitage dans le domaine du traitement d’im-ages [CBFAB97] et des méthodes d’estimation [Now03], mais l’objectif est ici de répondre àune problématique de consensus de moyenne totalement distribué en l’absence d’a priori prob-abiliste sur les mesures. Dans l’équation (4.3), les variables d’attachement (z•) doivent êtreconsidérées comme des constantes locales, et les variables d’états (x•) comme des paramètresà régulariser. Pour des raisons de stricte convexité du potentiel U , les fonctions de couplageψe et ψn doivent être paires, à dérivées secondes continues et positives, et coercives (de tellesfonctions peuvent alors être obtenues en intégrant deux fois une fonction g continue, positive etsymétrique). De plus, les constantes de couplage βij doivent refléter la topologie du réseau : onne peut coupler que les variables d’états entre nœuds voisins ( i ∼ j ⇔ i voisin de j).

U(X) =∑Gk

∑i∈Gkl

αilψe(xi − zl) +∑i,j∈Gk

βijψn(xi − xj)

(4.4)

Dans la suite, nous imposerons αil = δil, i.e. un attachement par nœud. Afin d’assurerde bonnes conditions de minimisation et algorithmiques, nous devons restreindre l’espace desfonctions de potentiel à certaines fonctions dites admissibles :

Définition 4.1 Une fonction ψ est une fonction de potentiel admissible si et seulement si ellevérifie les conditions suivantes :

1. ψ ∈ C2(R→ R).

2. ψ est paire, i.e ψ(x) = ψ(−x).

3. ψ′′ > 0, donc strictement convexe.

4. ψ est coercive, i.e. : limx→±∞

ψ(x) = +∞.

5. Sans manque de généricité, on impose ψ(0) = 0.

Bien que les hypothèses semblent contraignantes, ces fonctions sont nombreuses commel’indique le résultat de construction suivant :

Proposition 4.1 ψ est admissible si et seulement si il existe une fonction g : R → R continue,positive et paire telle que :

ψ(x) =

∫ x

0

∫ y

0

g(z)dzdy

En réalité, lorsque les forces de couplages augmentent et tendent vers +∞, on n’obtient pasforcément un consensus de moyenne mais un simple consensus. La proposition suivante permetde prédire le point de convergence asymptotique :


Proposition 4.2 (Point de consensus asymptotique)

arg minX∈Rn

U(X) −−−−−−→minβ→+∞

x∞1 avec x∞ = arg minx∈R

Ua(x1)

Avant d’en donner la preuve, notons que lorsque les forces de couplages augmentent, le pointde convergence est indépendant des fonctions de potentiel ψn et ne dépend donc que du choixde ψa et des données d’attachement z•.

Preuve : Pour un choix de couplages ~β, nous noterons X ~β le vecteur défini par :

X~β = arg min

X∈RnU(X; ~β)

De même, nous noterons respectivement Ua et Un les fonctions d’énergie d’attachement et derégularisation, définies par :

Ua =∑i,l

ψa(xi − zl) Un =∑i,j

βijψn(xi − xj) (4.5)

Ce vecteur possède une composante moyenne X ~β et une composante perturbatrice ∆X~β . Com-

mençons par montrer que ∆X~β → 0 lorsque mini,j βij → ∞. En remarquant que pour toutefonction, on a l’identité suivante :

ψ·(xi − xj) = ψcdot(∆xi −∆xj) si

xi = α + ∆xixj = α + ∆xjα quelconque

(4.6)

on obtient les relations suivantes pour la fonction d’énergie U :

U(X~β) = Ua(X

~β) + Un(X~β) (4.7)

= Ua(X~β) + Un(X

~β +X~β) (4.8)

= Ua(X~β) + Un(∆X

~β) (4.9)

car X ~β est un vecteur ayant toutes les composantes identiques par construction.

maxi∼j

ψn(X~βi −X

~βj ) ≤ Un(X

~β)

min βij≤ U(X

~β)

min βij≤ U(Z)

min βij=

Ua(Z)

min βij(4.10)

Cependantmaxi∼j

ψn(X~βi −X

~βj ) = max

i∼jψn(∆X

~βi −∆X

~βj ) (4.11)

donc :maxi∼j|∆X ~β

i −∆X~βj | −−−−→

β→+∞0 (4.12)

Comme X ~β ⊥ ∆X~β , mini ∆X

~βi ≤ 0 et maxi ∆X

~βi ≥ 0, d’où :

0 ≤

maxi ∆X

~βi

−mini ∆X~βi

≤ max

i∼j|∆X ~β

i −∆X~βj | (4.13)

PRINCIPE 65

donc par encadrement les composantes de ∆X~β tendent vers 0.

limβ→∞

h(β) = 0 (4.14)

Soit βn telle que βn →∞ et ∀n, ||h(βn)||∞ < ε.

x(βn) ∈ [(min zi)− ε, (max zi) + ε]∆= Ωε (4.15)

de plus :Ua(x

(βn) + h(βn)) ≤ Ua(x∗ + h(βn)) (4.16)

Comme Ωε est compact, il existe une sous suite β′n telle que x(β′n) converge et notons xe cettelimite. On obtient alors :

Ua(xe) ≤ Ua(x

∗) (4.17)

mais comme x∗ est l’unique minimiseur de Ua(x1), on a xe = x∗. En résumé, toute sous-suiteconvergente extraite de x(βn) converge vers x∗, donc x∗ est l’unique valeur d’adhérence de x(βn)

et donc x(βn) converge vers x∗. Donc, en éliminant les termes initiaux si nécessaire, pour toutesuite βn telle que lim βn = +∞,

∀(βn)n∈N, limn→∞

βn = +∞ ⇒ limn→∞

x(βn) = x∗ (4.18)

c’est précisément la définition de la limite d’une fonction en +∞, et donc :

limβ→+∞

x(β) = x∗ (4.19)

Maintenant, nous allons caractériser les fonctions de potentiel ψa susceptibles d’induireun consensus de moyenne asymptotiquement par rapport aux couplages. Ces fonctions, ditesmoyennantes, sont définies de manière rigoureuse comme suit :

Définition 4.2 On appellera une fonction de potentiel d’attachement ψa admissible moyen-nante si et seulement si

∀Z ∈ Rn, arg minX∈Rn

Ua(X)Z

Le résultat suivant est extrêmement étonnant de part la simplicité apportée au problèmed’existence et de caractérisation des fonctions moyennantes :

Proposition 4.3 (Caractérisation des fonctions moyennantes)– Si n = 2 tout fonction admissible est moyennante.– Si n ≥ 2, les seules fonctions moyennantes sont de la forme αx2, avec α > 0.

Preuve : Soit X∞ = x∞1 le point de consensus asymptotique. On a clairement

∇Ua(X∞) =n∑i=1

ψ′a(x∞ − zi) = 0 (4.20)


On cherche des fonctions admissibles ψa telles que ∀Z, x∞ = z, ce qui implique que pour toutn-uplet de réels (v1, . . . , vn), on a :

n∑i=1

vi = 0 ⇒n∑i=1

ψ′a(vi) = 0 (4.21)

On montre aisément par récurrence que pour tout réel x et tout entier k, ψ′a(kx) = kψ′a(x). Cettepropriété se généralise alors directement aux rationnels : ∀q ∈ Q et x ∈ R, ψ′a(qx) = qψ′a(x).Comme ψa doit être continue pour être admissible, un simple argument de densité de Q dans Rpermet de conclure que ∀x, y ∈ R, ψ′a(xy) = xψ′a(y). En particulier, ψ′a(x) = xψ′a(1) = αx.Les seules primitives admissibles de αx sont clairement de la forme αx2 avec α > 0.

Le choix de ψn peut donc être arbitraire parmi les fonctions admissibles. Un choix relative-ment simple consiste à choisir ψa(x) = ψn(x) = x2, mais des fonctions ψn non-quadratiquesouvre la perspective de convergence plus rapide pour de faibles couplages1.

4.2 Minimisation distribuéeDans cette section, nous donnons quelques rappels sur la méthode de minimisation de Jacobi

et les itérations asynchrones. Nous prouvons par la même occasion qu’il est possible d’utilisercette technique pour résoudre le problème de la minimisation du potentiel U de manière totale-ment distribuée et asynchrone.

Définition 4.3 Soit U : Rn → R une fonction à minimiser, et Ji : Rn → R l’opérateur :

Ji(x1, . . . , xn) = arg minyi∈R

U(x1, . . . , xi−1, yi, xi+1, . . . , xn)

Pour un vecteur initial X(0) ∈ Rn, l’algorithme de Jacobi synchrone consiste à itérer l’appli-cation simultanée des opérateurs Ji :

X(t+ 1) = [J1(X(t)), . . . , Jn(X(t))]

Autrement dit, l’opérateur de Jacobi consiste en une minimisation coordonnée par coordonnée,contrairement aux méthodes de gradients qui agissent simultanément sur toutes les coordon-nées. Cette dernière méthode est nécessairement synchrone et ne peut donc être utilisée ici.

Soit J un opérateur de E = E1 × · · · × En dans E, et Hi sa projection sur Ei, i.e :

[y1, . . . , yn] = J(X)⇒ Hi(X) = [J(X)]i = yi

En combinant la définition d’une itération asynchrone de [FS99] avec le cadre théorique de[BT97], chapitre 6, on obtient la formulation suivante :

Définition 4.4 ([BT97]) Soient, pour tout t ∈ N, les objets suivants :– I(t) ⊆ 1, . . . , n

1pour des couplages forts, et à partir d’un temps suffisant, des fonctions admissibles non-quadratiques tendentà s’approximer au second ordre, induisant alors le même résultat que pour le cas totalement quadratique

MINIMISATION DISTRIBUÉE 67

– τ ij(t) ∈ N, ∀i, j ∈ [1, n]– T i = t ∈ N : i ∈ I(t)

tels que :

1. τ ij(t) ≤ t pour i ∈ 1, . . . , n, t ∈ N2. limt→∞ τ

ij(t) =∞ pour i, j ∈ 1, . . . , n

3. Card (T i) =∞ pour i ∈ 1, . . . , nPour un vecteur initial x0 ∈ E = E1 × · · · × En, on appelle itération asynchrone le principerécursif suivant :

xi(t+ 1) =

Ji(x1(τ i1(t)), . . . , xn(τ in(t))) si i ∈ I(t)

xi(t) si i /∈ I(t)(4.22)

(I(t) indique les composantes mises à jour au temps t).

Dans cette définition, la variable τ ji (t) s’interprète comme la dernière date antérieure à t àlaquelle le nœud j a pu avoir accès à la variable d’état du nœud i. Cette formulation permet deprendre en compte les pertes de paquets et les délais de transmission : la situation où le paquetdu nœud i est perdu en réception au nœud j tombe bien dans ce contexte car cela ne fait quedécroitre la valeur de τ ij(t). Par ailleurs, on voit que l’interprétation en terme de connectivitéest beaucoup plus stricte que celle rencontrée dans la condition de convergence des algorithmesde consensus de moyenne : ici, chaque lien de voisinage doit être activé une infinité de foisau cours du temps, alors que dans le second cas il suffisait que les liens qui vérifient cettepropriété forment un sous-graphe connexe (avec bien sûr la condition que tous les nœuds soientreprésentés dans ce sous graphe).

Proposition 4.4 Sous les hypothèses des définitions 4.1 et 4.4, la minimisation asynchrone deU(X) par le biais de la méthode de Jacobi converge vers l’unique minimiseur Xopt de U pourtout vecteur initial X(0) si ∀i, ∃l, αil > 0.

Preuve : Cette preuve repose principalement sur des résultats et concepts issus de [BT97].A la section 6.3/p.434 de cet ouvrage, les auteurs démontrent qu’un schéma d’itération asyn-chrone appliqué à une fonction F converge vers un point fixe x∗ de F si cette fonction estcontractante par rapport à une norme maximum pondérée. Dans le cas présent, F est l’opéra-teur de Jacobi appliqué au potentiel U . En particulier, les auteurs de [BT97] prouvent dans laproposition 3.10, p.221, que la propriété de contraction de F repose sur l’opérateur R(X)

∆=

X − ∇U(X) qui doit être lui-même une contraction par rapport à la même norme maximumpondérée. La propriété de contraction deR(X) peut être démontrée par le biais de la proposition1.11 (p.194). Un calcul direct assure que les hypothèses nécessaires à l’utilisation de ce résultatsont bien réunies sous les conditions de la définition 4.1 lorsque chaque variable de régulari-sation possède au moins un attachement aux données. La matrice hessienne de U est définiepositive car ∇2U(X)) est la somme d’une matrice diagonale à éléments positifs et d’une ma-trice de type laplacien pondéré (donc semidéfinie positive). U est donc strictement convexe etcoercive (cf conditions 4.1) : un théorème classique de recherche opérationnelle stipule que Uadmet alors un unique minimum [Bon06], noté Xopt. La finalisation de cette preuve se finalisesi, les hypothèses b) et c) de la proposition 1.11 (p.194) sont vérifiées. En particulier,∇2U doit


avoir des termes diagonaux bornés par une constante K > 0 (point b)) et être strictement diag-onalement dominante avec un gap positivement minoré (point c)). La condition de dominancediagonale stricte est facilement vérifiable :

∂2U

∂x2i

=∑l

αilψ′′a(xi − zl) +

∑j∼i

(βij + βji)ψ′′n(xi − xj) (4.23)

∂2U

∂xi∂xj= −(βij + βji)ψ

′′n(xi − xj) (4.24)

comme ∀x ∈ R, ψ′′a(x) > 0, et ψn(x) > 0

∂2U

∂x2i

>∑j 6=i

∣∣∣∣ ∂2U

∂xi∂xj

∣∣∣∣ (4.25)

Le Hessien∇2U peut être considéré comme une fonction continue que nous pouvons restreindreau cube compact Ωn obtenu par produit cartésien de dimension n de l’enveloppe convexe desétats initiaux et des variables d’attachement : le théorème d’Heine-Borel [Arm97] permet deconclure sur l’existence de K et β.

4.3 Spécificité du cas quadratiqueDans cette partie nous fixerons les paramètres de régularisation de la manière suivante :– αij = δij/2, i.e. xi est uniquement attaché à la mesure du nœud i.– βij = β/4 si i et j sont voisins (i ∼ j), 0 sinon.– ψe(x) = ψn(x) = x2

Remarque 4.1 Une formulation similaire est proposée dans [PBS08], mais l’algorithme deminimisation utilisé est supposé synchrone et les hypothèses de communication sont différentesex : les couches physiques sont capables de remonter le signal du paquet. En particulier, lebruit de communication est pris en compte mais pas la perte de paquet. Si on oublie le bruit decommunication, l’approche présentée dans ce chapitre peut être considérée comme une exten-sion du principe présenté en [PBS08] dans le sens où une asynchronie totale dans le traitementdes données algorithmiques et leur transmission devient possible. Ce gain est considérable carla dépense énergétique nécessaire pour assurer la synchronisation d’un grand RdC peut de-venir non-négligeable. Cependant, il y a une différence supplémentaire : alors que l’objectif de[PBS08] est de fournir une solution robuste au bruit de communication, notre algorithme vise àutiliser au maximum la nature diffusante du mode de communication radio (contrairement auxACM classiques). On pourrait facilement imaginer un algorithme hybride.

Comme toute les fonctions de couplages sont quadratiques, un calcul direct montre quel’opérateur de Jacobi associé au nœud i, i.e. Ji, se met sous la forme :

Ji(x1, . . . , xn) =zi + β

∑j∼i xj

1 + βNi

(4.26)

SPÉCIFICITÉ DU CAS QUADRATIQUE 69

où Ni représente la taille du voisinage du nœud i. Le point de consensus Xopt vérifie alorsl’équation :

Xopt = M−1Z, avec M = I + βLG (4.27)

où LG est le laplacien standard de G (voir [Moh91] et annexe A). Xopt dépend clairement de latopologie du réseau. Cependant le résultat suivant prouve que l’erreur de consensus et l’impactde la topologie peuvent être rendus arbitrairement faibles :

Proposition 4.5 ∥∥Xopt − Z∥∥

2≤ 1

1 + α(G)β

∥∥Z − Z∥∥2

(4.28)

où α(G) dénote la connectivité algébrique de G.

Preuve : Comme G est connexe, les valeurs propres de LG vérifient (voir [Moh91]) :

0 = λ1 < λ2 = α(G) < · · · < λn

De plus, la matrice inverse M−1 est symétrique semidéfinie positive, et possède les mêmesvecteurs propres que L. Les valeurs propres correspondantes λ′i sont données par :

λ′i =1

1 + βλi(4.29)

Le vecteur 1∆= [1, . . . , 1]T est alors le seul vecteur propre (à renormalisation près) associé :

– à la valeur propre λ1 = 0 pour LG– à la valeur propre λ′1 = 1 pour M−1

Ainsi le vecteur Z = zavg1 est invariant sous l’action de M−1, alors que le vecteur d’erreurinitial Z − Z est transformé car orthogonal 1 :

Xopt − Z = M−1(Z − Z) (4.30)

De cette dernière équation, on obtient la borne cherchée :∥∥Xopt − Z∥∥

2≤ (max

i>1λ′i)∥∥Z − Z∥∥

2=

1

1 + βα(G)

∥∥Z − Z∥∥2

(4.31)

En conséquence, l’erreur entre la régularisation et le consensus de moyenne dépend seule-ment du paramètre β, et de la connectivité algébrique du réseau α(G) (voir [Fie73], [Moh91]...).En particulier, α(G) peut être minorée de la manière suivante [Moh91] :

α(G) ≥ 2(1− cos(π/n)) (4.32)

Cette borne est cependant peu précise.

Remarque 4.2 Les résultats précédents indiquent qu’on pourrait obtenir le consensus de moyenneexact en forçant β =∞. Cependant, dans ce cas, l’impact des variables d’attachement est nulet l’algorithme devient instable : la convergence n’est plus assurée, et il existe alors un hyper-plan de points d’équilibre. Autrement dit, si l’algorithme converge vers un équilibre, celui-cipeut être loin du consensus recherché.


4.4 Type de convergenceSous les hypothèses générales de ce chapitre, la convergence est assurée mais la question de

sa vitesse exacte reste encore ouverte. Dans le cas d’interactions linéaires (potentiels quadra-tiques), des résultats sont disponibles dans la littérature pour deux cas particuliers :

– lorsque l’algorithme est synchrone, i.e. les nœuds appliquent simultanément l’opérateurde Jacobi et échangent leurs états correctement avec leurs voisins [BCC07].

– lorsque les délais t− τ ji (t) sont bornés [BT97].Par exemple, la version synchrone converge géométriquement [BCC07] avec une vitesse donnéepar :

ρ([I + β∆]−1A

)(4.33)

où ∆ est la matrice diagonale des degrés des nœuds de G, A sa matrice d’adjacence, et ρ(·)la fonction “rayon spectral”. Lorsque β tend vers +∞, cet indicateur de vitesse tend vers 1(algorithme stoppé).

Certaines pistes suggèrent une convergence aussi de type géométrique dans le cas d’inter-actions linéaires avec délais probabilistes [BP93].

Dans la suite, nous donnons une preuve de ce type de convergence sous l’hypothèse d’unprocessus de communication stationnaire :

Théorème 4.1 Soit S(t) l’ensemble des liens de communication actifs au temps t, i.e. l’ensem-ble des échanges unidirectionnels réussis de paquets. Si S(t) est un processus aléatoire vérifiantles conditions suivantes :

1. les variables aléatoires S(·) sont i.i.d

2. ∀t, chaque liens du graphe de connectivité2 appartient au moins à une valeur possible deS(t), dont la probabilité est non-nulle

alors l’algorithme de régularisation converge géométriquement, i.e. il existe une constante 0 <ρ < 1 telle que :

‖X(t)−Xopt‖ = O(ρt) presque sûrement

i.e. avec une probabilité 1.

Preuve : Dans cette preuve, notons ‖ ‖ la norme euclidienne pour les vecteurs et la normeinduite pour les matrices, i.e. la norme spectrale [HJ86]. Remarquons que l’algorithme peut sereformuler comme un système dynamique vectoriel :

X(t+ 1) = S(t)J1X(t) + J2Z (4.34)

Dans cette équation de mise-à-jour, X est un vecteur contenant pour chaque nœud :– son propre état– le dernier état qu’il a reçu de chacun de ses voisins

On obtient donc ce vecteur en empilant les buffers de chaque nœud. J1 and J2 sont des opéra-teurs matriciels correspondant à la méthode de minimisation de Jacobi, et S(t) est une matricede transmission qui décrit les transmissions de paquets réussies. Il est possible de construire un

2on peut se contenter d’un sous-graphe de connectivité dont le motif est compatible avec celui des poids algo-rithmiques et du graphe de connectivité originel

TYPE DE CONVERGENCE 71

vecteur Xopt à partir de Xopt de la manière suivante : si la k-ième composante de X correspondà l’état du nœud j perçu par le nœud i, alors la k-ième entrée de Xopt vaut xoptj , i.e. la j-èmecomposante de Xopt. Un calcul direct montre alors que Xopt est un point fixe de l’équation(4.34). On obtient alors :

X(t+ 1)− Xopt (4.35)

= S(t)J1X(t) + J2Z − (S(t)J1Xopt + J2Z) (4.36)

= S(t)J1(X(t)− Xopt) (4.37)

Si les états locaux des nœuds convergent vers leur valeur optimale, il est clair que X(t) convergevers Xopt. Il y a donc une équivalence entre la convergence des états de l’itération asynchroneet celle de l’équation (4.34). Avec l’introduction d’une base orthonormée de vecteurs initiaux,l’utilisation de la proposition 4.4 et des hypothèses de la définition 4.4, on démontre que :

∀ε > 0,∃T ∈ N,∀X(0) > 0 t.q.∥∥∥X(0)

∥∥∥ = 1,

t ≥ T ⇒∥∥∥Xopt − X(t)

∥∥∥ < ε (4.38)

En d’autres termes, on peut trouver une date T qui ne dépend pas de X(0), et telle que l’er-reur résiduelle

∥∥∥Xopt − X(t)∥∥∥ soit rendue arbitrairement faible. Cette universalité joue un rôle

important dans la suite de ce développement. Soit Φ(t) la matrice définie par :

Φ(t)∆= S(t)J1S(t− 1)J1 . . . S(1)J1S(0)J1 (4.39)

Cette matrice s’obtient comme le produit des éléments d’une suite S(·)J1 de matrices aléa-toires i.i.d. obtenues à partir du processus S(t). On construit alors l’espace probabilisé produit(Ω,F ,P) de ces suites (cf annexe A). Les résultats basiques de probabilités modernes montrentque l’ensemble des séquences de matrices de transmission qui ne vérifient pas les hypothèsesde la définition 4.4 est de mesure nulle par rapport à la mesure de probabilité P. Maintenant,nous pouvons invoquer le théorème ergodique multiplicatif suivant :

Théorème 4.2 ([FK60],[Kin73],[HGG06]) Soit (Bk : k ≥ 0) une suite ergodique station-naire de matrices aléatoires telle que E [ln max(‖B0‖ , 1)] < ∞. Alors, il existe une constantedéterministe γ, appelée exposant de Lyapunov, telle que :

limk→∞

1

klog ‖Bk . . . B1‖ = γ presque sûrement (4.40)

De plus

γ = limk→∞

1

kE [log ‖Bk . . . B1‖] (4.41)

= infk≥1

1

kE [log ‖Bk . . . B1‖] (4.42)

Il est important de remarquer les points suivants :


1. La limite γ ne dépend, presque sûrement, pas de la réalisation de la suite aléatoire.

2. Presque sûrement signifie que l’ensemble des suites qui ne vérifient pas cette propriétéest de probabilité nulle.

3. Comme les normes matricielles sont topologiquement équivalentes, la définition et lavaleur de γ ne dépendent pas de la norme choisie.

4. Suivant les auteurs, le produit matriciel est pris de gauche à droite ou inversement : lerésultat reste valide tant que l’orientation est gardée constante.

Comme l’ensemble des suites de matrices de transmission qui vérifient les hypothèses de laproposition 4.4, et celui des suites qui satisfont le théorème 4.2 ont tous deux de mesure 1,leur intersection est aussi de mesure 1. Soit un Φ(t) obtenu à partir d’une suite dans cetteintersection. Par le théorème 4.2, γ ≥ 0 impliquerait que ∀t, ‖Φ(t)‖ ≥ 1. Alors, ∀t, il existeraitun vecteur unitaire Vt tel que

∥∥∥Φ(t)Vt

∥∥∥ ≥ ∥∥∥Vt∥∥∥ = 1, ce qui contredit la convergence supposée,et donc γ < 0. A l’aide de l’équation (4.40), on obtient :

1

tlog ‖Φ(t)‖ = γ + o(1) (4.43)

et donc :‖Φ(t)‖ =

(eγ+o(1)

)t(4.44)

Si t est suffisamment grand, le terme γ + o(1) est nécessairement négatif, et le terme eγ+o(1)

peut être majoré par une constante 0 < ρ < 1 de telle manière que :∥∥∥Xopt − X(t)∥∥∥ =

∥∥∥Φ(t)(Xopt − X(0))∥∥∥ = O

(ρt)

(4.45)

Cependant en pratique, l’ordre t tel que γt < 0 est très grand.

4.5 SimulationsDans cette section, nous allons présenter quelques résultats de simulation obtenus à l’aide

de MatLab.

4.5.1 ConditionsNous considérons un réseau de 400 nœuds qui ont été distribués de manière uniforme et

aléatoire sur un carré S de 200 mètres de largeur. Pour comparer les performances dans desconditions réalistes, nous supposerons que les paquets transmis sont reçus avec une probabilitépsuc dépendant de la distance entre l’émetteur et le récepteur potentiel suivant le modèle utilisédans [KNS05], i.e. :

psuc(d) =

1− (d/R)2α/2 si 0 ≤ d ≤ R(2− d/R)2α/2 si R < d ≤ 2R

0 sinon(4.46)

SIMULATIONS 73

où R est une distance de référence pour laquelle psuc = 0.5, α est un paramètre relié auphénomènes de fading, et d est la distance émetteur/récepteur. Sans manque de généricité, nouschoisissons α = 2, R = 20 m, et deux nœuds seront voisins si et seulement si leur distanceest inférieure à R. Les capteurs observent un phénomène spatial illustré sur la figure 4.3 : ils’agit d’une combinaison d’ondes sinusoïdales, d’une surface gaussienne est d’un champ debruit additif aléatoire. Ces mesures sont notées h(si) où si représente la position du nœud isur S. Maintenant que la topologie et les observations sont définies, les seuls degrés de libertérestants sont les paramètres de régularisation : nous utiliserons ceux du modèle (4.3) :

– ψe(x) = ψn(x) = x2

– βij = β/4 si i ∼ j, 0 sinon– αil = 1/2 si i = l, 0 sinon

Autrement dit, chaque nœud possède une seule variable d’attachement correspondant à sonobservation (mesure). La valeur de β est successivement prise dans l’ensemble [0.1, 1, 10, 100]pour illustrer l’impact de sa magnitude sur la vitesse et la qualité de convergence. Par ailleurs,l’algorithme de régularisation sera comparé à un ACM classique à double acquittement :

1. la communication doit être initiée2. acquittée par le destinataire3. puis finalisée par l’initiateur

Sans cette procédure, il est impossible de garantir la convergence de l’ACM vers le bon consen-sus. De manière standard, un nœud est tiré aléatoirement et uniformément à chaque itération :dans le cas de la régularisation, il ne transmet que son état actuel, alors que dans le cas del’ACM, il initie une interaction complète avec un voisin choisi suivant la politique naturelle (cfchapitre 1)

4.5.2 RésultatsOn commence par donner les résultats sur la qualité du vecteur optimal Xopt par rapport

au consensus de moyenne Z. Deux normes d’erreur∥∥Xopt − Z

∥∥2

et∥∥Xopt − Z

∥∥∞ ainsi que la

borne fournie par l’équation (4.31), sont tracées sur la figure 4.4 pour des valeurs de β allant de0.1 à 104. Comme le prédisait la section 4.3, la qualité de l’approximation Xopt augmente avecβ et l’erreur résiduelle peut être rendue arbitrairement faible en faisant tendre β vers l’infini.

Après ces détails sur la précision asymptotique, on donne quelques résultats sur le comporte-ment dynamique de l’algorithme de régularisation vis-à-vis de celui de l’ACM. L’erreur résidu-elle état-consensus moyenne E

[∥∥X(t)− Z∥∥

2

]et état-optimum moyenne E

[‖X(t)−Xopt‖2

]sont tracées sur les figures 4.6 et 4.5 en fonction du nombre de messages échangés afin decomparer la consommation énergétique des deux algorithmes3. Comme prévu par la théorie,les états régularisés convergent vers les optimaux dans le voisinage du consensus de moyennecomme le montre la figure 4.4. Les figures 4.6 et 4.5 illustrent aussi le fait que l’algorithme derégularisation peut opérer plus vite que l’ACM classique lorsque le facteur β est faible et atteintrapidement son approximation du consensus. Le recours systématique aux acquittements dansle cas des ACM (voir [MSP+07]) réduit significativement les performances lorsque les infor-mations peuvent être perdues. De plus, il semble envisageable d’améliorer encore cet écart devitesse en augmentant lentement le facteur β.

3les moyennes sont calculées à l’aide de 1000 réalisations


Remarques 4.1 1. L’effet du rayon de connectivité sur la vitesse de convergence n’est pasclair dans le cas de la régularisation :

2. Il semblerait que la vitesse de convergence augmente en pondérant les couplages entrevariables régularisées de manière inversement proportionnelle à la probabilité d’erreurde transmission, au lieu d’utiliser la même pondération pour chaque voisin.

3. Pour améliorer la convergence de l’algorithme après une erreur ou un changement im-portant (topologie, mesure, ...), les simulations montrent qu’il est judicieux de réduiretemporairement le facteur β afin de stabiliser à nouveau les états puis d’augmenter pro-gressivement ce facteur pour obtenir une meilleure qualité d’approximation.

SIMULATIONS 75

0

50

100

150

200

0

50

100

150

200−0.05

0

0.05

0.1

0.15

0.2

0.25

0.3

xy

z

Figure 4.3 – Observations brutes

0.0001

0.001

0.01

0.1

1

10

1 10 100 1000 10000

Nor

me

d’er

reur

Facteur de regularisation β

Norme euclidienneNorm MaxBorne sup

Figure 4.4 – Erreur d’approximation asymptotique∥∥Xopt − Z

∥∥


1e-09

1e-08

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

10

1 10 100 1000 10000 100000

Nor

me

d’er

reur

Eta

ts-O

ptim

um

Nombre de messages

gossip averagingβ=1

β=10β=100

β=1000

Figure 4.5 – Erreur résiduelle états-optimum moyenne E[‖Xopt −X(t)‖2

]

0.1

1

10

1 10 100 1000 10000 100000

Nor

me

d’er

reur

Eta

ts-M

oyen

ne

Nombre de messages

gossip averagingβ=1

β=10β=100

β=1000

Figure 4.6 – Erreur résiduelle états-consensus E[∥∥Z −X(t)

∥∥2

]

77

Chapitre 5

Une application à la cartographie

Dans ce chapitre, l’attention est portée sur un mécanisme de fusion de données particulier :la cartographie. Il s’agit de fournir une représentation compacte des phénomènes observés.Ce type de représentation est utile pour plusieurs raisons. D’un coté, l’utilisateur final peutdésirer un aperçu global (à l’échelle du réseau) des mesures effectuées. D’autre part, un nœud-capteur peut avoir besoin d’une information provenant d’une source lointaine ou inaccessible(phénomène environnemental ...). La question de la cartographie dans les réseaux de capteurspeut être abordée sous trois angles principaux. Tout d’abord, il peut s’agir de collecter les don-nées individuelles des capteurs et de les transporter vers les nœuds intéressés : le coût énergé-tique/organisationnel de cette approche peut être prohibitif. Une deuxième approche consisteà utiliser des techniques classiques d’estimation distribuée ([Now03], [DNB06], [DZ06]) afinde retrouver les données d’intérêt sur la base d’une connaissance partielle des informations etdes dépendances probabilistes qui les relient. Cependant, ces dépendances doivent exister etêtre identifiées, ce qui est irréaliste dans un cadre général. Enfin, une troisième approche estde fournir une représentation concise des données en leur ajustant un modèle paramétrique.Un bon nombre de travaux ont été publiés afin de fournir des cadres théoriques et algorith-miques à cette méthode mais les solutions proposées souffrent d’inconvénients assez communstels que des coûts de stockage/communication/coordination prohibitifs ([GBT+04], [BCA05b],[BCA05a], [BK08]), haute complexité algorithmique, échanges fiables et/ou synchrones dedonnées ([SRB07], [GBT+04]), ... Néanmoins, la contrainte de synchronie peut toujours êtreassurée par le biais d’un mécanisme de synchronisation ou d’acquittement, ce qui entraîne unsurcoût de complexité et d’énergie.

Dans ce chapitre, nous proposons un nouvel algorithme pour ajuster linéairement un modèleparamétrique sur la base d’observations. Tout comme le schéma de régularisation scalaire, il sebase sur la minimisation d’une fonction de potentiel, et fournit une approximation du jeu deparamètres, optimal au sens des moindres carrés, dont la qualité peut être réglée. Encore unefois, la nouveauté de cette approche par rapport à l’état de l’art réside dans son support intrin-sèque des pertes de paquets et de l’exploitation la nature diffusante du mode de communicationradio. Cet algorithme possède de nombreuses applications directes telles que par exemple :

– fournir des cartographies d’occupation de ressources spectrales pour des systèmes deradio cognitive

– construire de l’information de fond pour des techniques d’agrégation/récupération dedonnées adaptative dans les WSN.

78 UNE APPLICATION À LA CARTOGRAPHIE

5.1 ReprésentationL’intérêt principal de la méthode paramétrique est de rendre aisée l’extrapolation de données

de régions inaccessibles ou lointaines. Parmi d’autres références, [XBL05] propose une solutionau problème d’estimation au sens du maximum de vraisemblance d’un vecteur de paramètres θintervenant dans un modèle paramétrique linéaire y = Aθ + v, où v est un vecteur de bruit etA la matrice de réponse du modèle. Dégagée de son contexte statistique, cette méthode permetd’obtenir un vecteur θ qui minimise l’erreur quadratique de la représentation par rapport auxobservations initiales.

Dans ce chapitre, l’utilisation d’une base de représentation ([GBT+04], [WCWG07]) donneune signification particulière à la matriceA. Cependant, contrairement à [XBL05] qui développeune méthode à base de gossip averaging, nous proposons ici d’utiliser la technique de régulari-sation distribuée.

On considère un réseau connexe de n nœuds, et nous supposons que chacun connaît, aumoins approximativement, sa propre position dans un système de coordonnées quelconque.Cette information peut être obtenue par le biais d’un algorithme de positionnement (DV-HOPpar exemple) exécuté préalablement ou conjointement. Ces nœuds observent un phénomènesuffisamment régulier supposé stationnaire1, et partagent une famille de fonction de bases ϕj(·),j ∈ [1,m], appelée base de représentation2.

Avec ces hypothèses, un nœud i est en mesure de calculer la valeur de la base de représen-tation évaluée à sa position si, noté à l’aide du vecteur-ligne φ(si) :

φ(si) = [ϕ1(si), . . . , ϕm(si)] (5.1)

Nous aurons besoin pour des raisons calculatoires de définir la matrice Φ contenant l’empile-ment des vecteurs φ(si) pour i balayant l’ensemble des nœuds du réseau :

Φ =[φ(s1)T, . . . , φ(sn)T

]T(5.2)

5.2 Régression au sens des moindres carrésComme expliqué précédemment, le but de cette partie est d’ajuster une combinaison linéaire

de fonction de bases aux données observées. Ceci se formalise de manière matricielle commesuit :

y = Φp + e (5.3)

où y est le vecteur des observations, p celui des paramètres des modèles, et e un vecteur d’erreurde représentation. Comme critère d’ajustement, nous choisissons de trouver le vecteur p quiminimise l’erreur quadratique par rapport aux mesures :

p = argminp∈Rm

‖y − Φp‖2 (5.4)

1au moins par rapport à la durée d’exécution de notre algorithme2temporairement en conflit avec la définition mathématique classique d’une base de représentation en analyse

harmonique [DE08]

RÉGULARISATION 79

Il s’agit d’un problème classique dont la solution est données par l’équation suivante ([XBL05]) :

p = (ΦTΦ)−1ΦTy (5.5)

Pour obtenir une forme distribuée du problème, il est utile de reformuler les termes de la solution(5.5) d’un point de vue local comme dans [XBL05] :

ΦTΦ =∑i

φ(si)Tφ(si) ΦTy =

∑i

yiφ(si)T (5.6)

où yi est l’observation du nœud i et φ(si) est le vecteur des valeurs prises par les fonctions dela base de représentation à la position si. On obtient alors l’expression suivante pour p :

p =

(1

n

∑i

φ(si)Tφ(si)

)−1(1

n

∑i

yiφ(si)T

)(5.7)

La formule (5.7) montre qu’il est possible de trouver le vecteur optimal p par le biais d’unesérie d’algorithmes de consensus de moyenne.

5.3 RégularisationDans cette section, l’algorithme de régularisation présenté au chapitre 4 est utilisé dans une

version matricielle pour répondre au problème de consensus de moyenne de l’équation 5.7.

5.3.1 Fonction de coût/potentielOn considère la fonction de potentiel suivante :

U(X) =1

2

∑i

‖Xi − Zi‖2 +β

2

∑i∼j

‖Xi −Xj‖2 (5.8)

oùXi est la variable de régularisation du nœud i, Zi sa variable d’attachement, et β le paramètrede force de la régularisation. Par le biais de la minimisation du potentiel U , nous visons àaccroître la similarité des variables de régularisation entre nœuds voisins tout en gardant unecertaine proximité avec les variables d’attachement. Dans notre cas, les variables d’attachementZi sont définies par

Zi = [φ(si)Tφ(si) yiφ(si)

T] ∈Mm(R)× Rm ∆= Ω (5.9)

les variables de régularisation Xi sont aussi des objets matriciels de taille m-par-m + 1, et lesfonctions de couplages sont des normes matricielles de Frobenius. Quant à lui, le problème deminimisation se formule alors ainsi :

Trouver Xopt = argminX∈Ωn

U(X) (5.10)

Chaque nœud se voit alors affecté d’une variable Xi = [Mi Vi], dans laquelle Mi et Vi sontrespectivement des approximations de 1

nΦTΦ et 1

nΦy. Donc par le biais de l’équation (5.7) et

sous réserve de pouvoir inverser Mi, le nœud i peut calculer une approximation locale pi de pvia :

pi = M−1i Vi (5.11)


5.3.2 Minimisation par la méthode de JacobiDu point de vue algorithmique, nous nous intéressons à la minimisation de U de manière

purement locale. La méthode de Jacobi vue au chapitre 4 est un candidat adéquat. Pour rap-pel, cette méthode consiste à opérer des minimisations séparées et indépendantes sur chaquevariable :

Xi = argminXi∈Ω

U(X1, . . . , Xi−1, Xi, Xi+1, . . . , Xn) (5.12)

Cette technique diffère de la descente de gradient classique par le fait que la structure sous-jacente qui relie les variables n’est pas prise en compte. Nous allons voir que cet analoguevectoriel de la méthode scalaire du chapitre 4 peut aussi être menée de manière distribuée etasynchrone. Pour cela, notons τ kij(t) la date du dernier instant antérieur à t où le nœud i a reçula k-ème composante3 de la variable de régularisation du nœud j, i.e. la dernière date où i areçu Xk

i . La version asynchrone de la méthode de Jacobi se formule alors comme suit :

Xki (t) = argmin

x∈RU(Xk

1 (τ ki1(t)), . . . , x, . . . , Xkn(τ kin(t))) (5.13)

où la variable x se trouve à l’indice i. Un calcul direct donne alors :

Xki (t) =

Zki + β

∑j∼i

Xkj (τ kij(t))

1 + βNi

(5.14)

avec Ni la taille du voisinage du nœud i. Cette équation scalaire a été proposée au chapitre 4et fournit une alternative asynchrone à l’approche présentée dans [PBS08]. Pour des raisons desimplicité, l’opérateur de Jacobi sera noté :

Xki (t) = Jki (ωki (t)) (5.15)

où ωki (t) doit être interprété comme la vision que le nœud i a au temps t du k-ème état de sesvoisins4. En appliquant la théorie du chapitre 4, on prouve la convergence de l’algorithme decartographie :

Théorème 5.1 Si les opérateurs Jki et les τ kij vérifie les hypothèses du chapitre 4 pour tout k, laminimisation asynchrone de U converge vers Xopt :

limt→∞

X(t) = Xopt ∈ Ωn (5.16)

Preuve : Les variables de régularisation sont des matrices de taille m-par-(m + 1). Lesfonctions de couplage utilisées sont des normes de Frobenius et U peut donc se réécrire commeune somme de m(m + 1) fonctions d’énergie scalaires indépendantes, une par composante.En conséquence, la proposition 1 du chapitre 4 assure la convergence de chaque composante,qui assure par la même occasion la convergence des variables de régularisation m(m + 1)-dimensionnelles.

3pour faire simple dans les notations, nous avons préféré éviter l’indexation ligne-colonne4on peut y intégrer les nœuds manquants car ils n’interviennent pas dans Jk

i

RÉGULARISATION 81

5.3.3 Bornes de précisionSur chaque nœud i, le k-ième état converge vers un optimalXk,opt

i vérifiant la borne suivante[MPG] :

||Xk,opt• − Zk|| ≤ [1 + βα(G)]−1||Zk

• − Zk|| −−−→β→∞

0 (5.17)

où Zk représente la moyenne spatiale de la k-ième composante des variables d’attachement(correspondant à la solution au sens des moindres carrés), et α(G) la connectivité algébrique deG. Alors,

Xi −−−→β→∞

Z =

[1

n

∑i

φ(si)Tφ(si) ,

1

n

∑i

yiφ(si)T

](5.18)

Fixons les notations p et pi comme précédemment, y pour le vecteur des observationsreconstruites sur la base du modèle optimal au sens des moindres carrés, et yi les observationsreconstruites à l’aide du vecteur de paramètres pi. La proposition suivante assure que l’erreurd’approximation peut être rendue arbitrairement faible en augmentant β :

Proposition 5.1 Pour t =∞ :

‖pi − p‖ −−−→β→∞

0 et maxi‖y − yi‖∞ −−−→

β→∞0

Preuve : On note ‖ ‖ la norme Euclidienne pour les vecteurs et sa norme induite pourles matrices. Par continuité de l’inversion matricielle pour de petites perturbations des entrées,le développement suivant est valide lorsque β est suffisamment grand :

‖y − yi‖ = ‖Φp− Φpi‖ (5.19)

≤∥∥Φ(ΦTΦ)−1V − Φ(ΦTΦ + ∆Mi)

−1(V + ∆Vi)∥∥ (5.20)

≤∥∥∥ΦΦ

∥∥∥× ∥∥∥∥V − [I + ∆MiΦ]−1

(V + ∆Vi)

∥∥∥∥ (5.21)

≤∥∥∥ΦΦ

∥∥∥‖∆Mi‖

∥∥∥Φ∥∥∥ (∥∥ΦTy

∥∥+ ‖∆Vi‖)

1− ‖∆Mi‖∥∥∥Φ∥∥∥ + ‖∆Vi‖

(5.22)

où on a noté Φ∆= (ΦTΦ)−1. Comme pour toute matrice carrée M , ‖M‖ ∆

= ‖M‖2 ≤ ‖M‖F ,la convergence vers 0 de chaque composante matricielle implique la convergence vers 0 de‖yi − y‖.

5.3.4 CommentairesFragmentation

La méthode proposée précédemment repose sur une topologie de réseau et une base dereprésentation supposées fixes. Dans la réalité, on peut souhaiter exécuter l’algorithme dans unpremier temps sur des groupes réduits de nœuds (clusters), puis étendre par la suite le calculau réseau entier. Cependant, lorsque les clusters sont de petite taille, les nœuds sont en général


proches les uns des autres, et les observations peuvent être ressemblantes (corrélées) : la taille dela base de représentation peut alors être réduite à ses composantes les plus pertinentes. D’autrepart, le réseau peut décider de réduire la taille de la base si elle est jugée trop complexe parrapport aux phénomènes observés. En fait, ces procédures sont des cas spéciaux de schémasd’itérations asynchrones tel qu’ils ont été préalablement définis : la taille de la base peut êtreadaptée localement (fragmentation représentative) et les calculs internes à chaque clusters peu-vent être fusionnés à la volée (fragmentation spatiale).

Robustesse topologique

Lors d’un changement topologique, le point optimal Xopt et sa qualité sont altérés maistoujours majorables via la connectivité algébrique α(G) dans l’équation (5.17). En utilisant lamajoration α(G) ≥ 2(1 − cos(π/n)) (voir [Moh91]), et en augmentant β en conséquence, onpeut garantir un degré de qualité arbitraire.

Complexité

Du point de vue de la complexité temporelle, la convergence géométrique du cas scalairereste valide pour la convergence de chaque composante des variables de régularisation.

Par ailleurs, on aurait pu travailler directement sur les paramètres du modèle plutôt que surles paramètres de la pseudo-inversion. Ceci peut se faire par le biais de la fonction de potentielsuivante :

U =n∑i=1

(yi − φ(si)Tpi)

2 − β∑i∼j

‖pi − pj‖22 (5.23)

où pi représente le vecteur, estimé au nœud i, des paramètres du modèle. L’intérêt de cetteapproche serait une réduction de la taille des données a échanger (m au lieu de m× (m + 1)).Cependant, plusieurs arguments de nature mathématiques et algorithmiques s’opposent à cettesolution. Tout d’abord, dans certains cas, ce potentiel peut être simplement convexe (et non passtrictement convexe). C’est en particulier le cas si une fonction de base vaut 0 dans la régionoù les capteurs sont déployés. Sans l’hypothèse de stricte convexité, il devient difficile voireimpossible d’assurer la convergence la minimisation locale par la méthode de Jacobi.

Supposons maintenant la stricte convexité du potentiel 5.23. Il reste encore à vérifier queles hypothèses assurant la convergence de la méthode de Jacobi sont elles aussi vérifiée (voirchapitre 4). Or, on ne peut utiliser l’argumentation de la preuve de la proposition 4.4 le hessiende U dans l’équation 5.23 n’est en général pas à diagonale strictement dominante. Quant àla condition spectrale proposée dans [BCC07] et [BT97], elle devient extrêmement difficile àmanipuler et à prouver.

En conclusion, ce principe est intelligent mais les conditions précises de son bon fonction-nement dans un cadre concret restent à trouver et à démontrer.

5.4 SimulationsLes simulations se font dans les mêmes conditions que pour la régularisation scalaire du

chapitre 4 : modèle d’erreur de [KNS05], n = 400 nœuds, etc. Les capteurs observent un

SIMULATIONS 83

Figure 5.1 – Observations

phénomène spatial en forme de selle de cheval y = f(s) défini par :

y = f(s) = 2 cos(πsx/L)− 4 cos(πsy/L) + 1 +N (0, σ) (5.24)

où les N (0, σ) sont des perturbations additives gaussiennes centrées i.i.d. de variance σ2 =0.025. La réalisation du champ gaussien est fixée une fois pour toutes les simulations. Cesmesures sont naturellement représentées sur la base φ(s) = [1 cos(πsx/L) cos(πsy/L)]5.Ainsi, l’objet d’attache Zi au nœud i prendra la forme suivante :

Zi =

1 cos(πsi,xL

) cos(πsi,yL

) yicos(

πsi,xL

) cos(πsi,xL

)2 cos(πsi,xL

) cos(πsi,yL

) yi cos(πsi,xL

)cos(

πsi,yL

) cos(πsi,xL

) cos(πsi,yL

) cos(πsi,yL

)2 yi cos(πsi,yL

)

(5.25)

Les figures 5.1 et 5.2 illustrent respectivement l’observation initiale et le modèle optimalrécupéré par régression au sens des moindres carrés. Par le biais de l’algorithme de régu-larisation, chaque nœud acquiert un jeu de paramètres estimés qui doit être comparé à celuiobtenu par la méthode des moindres carrés. La figure 5.3 illustre le comportement de l’erreurparamétrique asymptotique max

i|[p]k − [pi]k| et de l’erreur maximale de représentation lorsque

la force de régularisation β augmente. Comme prévu analytiquement, ces deux erreurs dis-paraissent lorsque β tend vers +∞6, mais la vitesse de convergence de l’algorithme diminue.

5on aurait pu aussi choisir par exemple une base de polynômes de Legendre6Rappelons qu’il est impossible de prendre β =∞ dans la méthode de Jacobi


Figure 5.2 – Modèle optimal au sens des moindres carrés

D’un point de vue dynamique, les performances de notre algorithme sont comparées à laméthode de [XBL05] utilisant les ACM classiques sur les figures 5.4 and 5.5. On voit que larégularisation nécessite moins d’envois de messages7, et donc par corollaire, moins d’énergie,pour fournir une bonne représentation du phénomène spatial observé. C’est une conséquence dela nécessité d’acquitter systématiquement les interactions dans le cas d’un ACM8. Par ailleurs,les perturbations transitoires observables durant les premières itérations proviennent du mauvaisconditionnement, voire même de la singularité, des matrices Mi dans l’équation (5.11), i.e.lorsque peu de messages ont été échangés localement. Tant queMi n’est pas devenue inversible,le nœud i doit trouver une autre approximation des paramètres : en première approximation, ilpeut considérer yj = yi, ∀j 6= i.

5.5 Conclusion

Dans cette partie, nous avons appliqué la méthode de régularisation du chapitre 4 à l’ajuste-ment linéaire d’un modèle paramétrique par rapport à des mesures distribuées spatialement.Cet algorithme présente l’avantage d’être distribué, asynchrone et robuste aux pertes d’infor-mations : ces caractéristiques en font une solution de choix pour une utilisation dans les réseauxde capteurs et/ou ad-hoc généraux. En termes d’applications concrète, on pourrait imaginer

7il ne faut pas oublier de diviser le nombre de messages par le nombre de capteurs pour avoir une idée de laconsommation énergétique locale

8voir le chapitre 4 pour plus de détails

CONCLUSION 85

0.0001

0.001

0.01

0.1

1

10

100

0.1 1 10 100 1000 10000

Err

eur

asym

ptot

ique

Facteur de regularisation β

Erreur sur p1Erreur sur p2Erreur sur p3

Erreur de representation Reg/LMS

Figure 5.3 – Erreur paramétrique maximale maxi|[p]k − [pi]k| et erreur de modélisation maxi-

male maxi‖Φp− Φpi‖

0.0001

0.01

1

100

10000

0 10000 20000 30000 40000 50000

Err

eur

de r

epre

sent

atio

n pa

r ra

ppor

t a l’

etat

opt

imal

Messages

β=0.1β=1

β=10β=100

Gossip Averaging

Figure 5.4 – Erreur de représentation maximale maxi‖Φpi(t)− Φpi‖2 par rapport aux

paramètres régularisés optimaux


0.1

1

10

100

1000

10000

100000

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Err

eur

de r

epre

sent

atio

n er

ror

par

rapp

ort a

ux m

oind

res

carr

es

Messages

β=0.1β=1

β=10β=100

Gossip Averaging

Figure 5.5 – Erreur de représentation maximale maxi‖Φpi(t)− Φp‖2 par rapport aux

paramètres LMS optimaux

construire des cartes représentatives des variations spatiales de phénomènes environnementaux(température, pression) ou liés au réseau (débit local, occupation spectrale, puissance de bruit,...).

87

Conclusion et perspectives

Dans cette thèse, nous avons abordé les algorithmes de consensus de moyenne en tempsdiscret dans le contexte des réseaux de capteurs sous trois aspects principaux.

Tout d’abord, nous avons contribué à la caractérisation de leurs performances et de leurfonctionnement en se basant sur principalement les travaux de [XBL05], [BK05], [Bor06] et[MPZ99]. En particulier, l’optimisation de la vitesse de convergence est apparue comme unproblème hautement non-trivial, et le recours à des mécanismes de contrôle de réception commestrictement nécessaire.

Puis, nous avons proposé diverses améliorations de l’état de l’art. Notamment, l’accent aété mis sur la prise en compte rapide d’informations nouvelles (dans un contexte d’estimationpar exemple), sur la résistance aux pertes de paquets, ainsi que sur l’exploitation de la naturediffusante du canal radio. Ces travaux ont abouti sur de nouvelles généralisations distribuées,asynchrones et robustes des solutions algorithmiques introduites par [XBL06b] et [PBS08].

Afin de concrétiser la démarche, deux applications primaires de ces algorithmes ont étéproposées, avec la synchronisation fine d’horloges et l’ajustement d’un modèle paramétrique.En particulier, la première application permet d’améliorer les performances de radiolocalisation,et la seconde trouve certainement un intérêt majeur dans les systèmes à base de radio cognitive etdans l’accélération de protocoles d’interrogation des capteurs (querying, data gathering, fusion& agrégation).

Par ailleurs, les techniques d’échantillonnage parcimonieux9 et les outils dérivés des al-gorithmes de consensus de moyenne pourraient devenir complémentaires : il serait par exem-ple envisageable de fournir de l’information utile à l’échantillonnage, ou encore de réduire ladépense énergétique des ACM.

Cependant, de nombreuses questions restent ouvertes sur les aspects pratiques de la familledes ACM. Nous pouvons citer par les points suivant :

– aucune implémentation générique capable d’opérer sur un réseau quelconque et indépen-damment des spécificités de la couche MAC, n’a été proposée dans la littérature.

– existe-t-il un moyen de résoudre de manière légère, réaliste, distribuée et non-coordonnéele problème d’optimisation SDP rencontré à la section 1.4.1 ?

– dans un cadre général, est-il possible d’exploiter la nature corrélée des informationsmesurées par les capteurs pour accélérer la vitesse de convergence des ACM ?

Il semblerait que les deux derniers ne recevront aucune réponse simple et exploitable à courtterme.

9compressed sensing en anglais

88 CONCLUSION ET PERSPECTIVES

89

Annexe A

Rappels : Graphes & Probabilitésmodernes

A.1 GraphesDéfinition A.1 Un graphe G = (V,E) est la donnée :

– d’un ensemble V dont les éléments sont appelés sommets ou noeuds.– d’un ensemble E dont les éléments sont des couples non-ordonnés de sommets, appelés

arcs.

Définition A.2 Un graphe est connexe si et seulement si pour toute paire de sommets u et v, ilexiste une suite d’arcs consécutifs (chemin) reliant u et v.

Définition A.3 Soit G = (V,E) un graphe. On appelle degré du sommet v ∈ V , noté deg(v) lenombre d’arcs de E contenant v.

Définition A.4 La matrice d’adjacence d’un graphe G = (V,E) est la matrice A d’ordreCard (V ) telle que Aij = 1 si et seulement (i, j) ∈ E.

Définition A.5 Le laplacien standard d’un graphe G = (V,E) est la matriceL d’ordre Card (V )telle que :

Lij =

deg(i) si i = j−1 si i 6= j et (i, j) ∈ E0 sinon

Théorème A.1 SoitL le laplacien standard du graphe G = (V,E).L est une matrice symétrique,semidéfinie positive.

Définition A.6 On appelle connectivité algébrique de G, notée α(G), la seconde plus petitevaleur propre de L(G).

Théorème A.2 α(G) > 0 si et seulement si G est connexe.

Définition A.7 Un chemin entre deux sommets i et j est une succession d’arêtes adjacente(i, s1) . . . (sp, j).

90 RAPPELS : GRAPHES & PROBABILITÉS MODERNES

Définition A.8 Un arbre recouvrant sur G est un sous-graphe connexe acyclique de G

Définition A.9 Un arbre recouvrant enraciné sur un graphe G = (V,E) est un couple (T , r)où :

– T est un arbre recouvrant de G.– r ∈ V est un sommet distingué, appelé racine de l’arbre.

A.2 Axiomatique de KolmogorovL’axiomatique de Kolmogorov pose les bases rigoureuses, bien qu’abstraites, de la théorie

moderne des probabilités. Nous en donnons quelques éléments inspirés de [Kal97] nécessairesà la compréhension de cette thèse.

Définition A.10 Une σ-algèbre1, ou tribu, sur un espace Ω est une collection non-vide A desous-ensembles de Ω stable par unions et intersections dénombrables et par passage au com-plémentaire, i.e. :

– A ∈ A ⇒ Ω \ A ∈ A– Pour toute famille dénombrable (Ai)i∈I d’éléments de A,

⋃i∈I Ai ∈ A et

⋂i∈I Ai ∈ A

Une sous-tribu de A1 est une tribu contenue dans A1

Définition A.11 Soit C une collection d’ensembles d’un espace Ω. On appelle σ-algèbre en-gendrée par C, notée σ(C), la plus petite σ-algèbre sur Ω contenant C.

Définition A.12 Un espace mesurable est un couple (Ω,A) où A est une σ-algèbre sur Ω.

Définition A.13 Soient deux espaces mesurables (Ω1,A1) et (Ω2,A2), une fonction f : Ω1 →Ω2 est dite A1/A2-mesurable, ou mesurable, si et seulement si f−1(A2) est une sous-tribu deA1.

Définition A.14 Une mesure sur un espace mesurable (Ω,A) est une application mesurableµ : Ω→ R+, en prenant comme tribu sur R+ sa tribu borélienne, telle que :

– µ(∅) = 0– si (Ai)i∈I est une famille dénombrable d’éléments deA1 deux à deux disjoints, µ(

⋃i∈I Ai) =∑

i∈I µ(Ai) (propriété de σ-additivité)On appelle mesure de probabilité toute mesure µ telle que µ(Ω) = 1. Une mesure est dite finiesi µ(Ω) <∞

Définition A.15 Une variable aléatoire (v.a.) est une fonction mesurable sur un espace prob-abilisé. En particulier, on appellera variable aléatoire canonique de (Ω,A, µ) l’applicationidentité de Ω.

Définition A.16 Soit (Ω,A, µ) un espace probabilisé. Un élément E de A est dit négligeablesi et seulement si µ(E) = 0.

1en anglais : σ-field ou σ-algebra suivant les auteurs

AXIOMATIQUE DE KOLMOGOROV 91

Définition A.17 Un espace probabilisé est un triplet (Ω,A,P) où A est une σ-algèbre sur Ωet P est une mesure de probabilité sur (Ω,A).

Définition A.18 Soient I un ensemble dénombrable et (Ω,A,P) un espace probabilisé, on ap-pelle espace probabilisé produit, le triplet (Ω′,A′,P′) tel que :

– Ω′ = Ω× Ω× · · · = ΩI

– A′ = σ(⋃i∈I Ci), où Ci = (Cij)j∈I ∈ AI tel que Cii = A, et Cij = Ω pour i 6= j (on dit

que A′ est engendrée par les cylindres monodimensionnels).– P′ est une mesure de probabilité sur (Ω′,A′) qui coïncide avec µ × · · · × µ sur tout

cylindre, i.e. pour tout élément C = (Ci)i∈I deA′ tel que Ci = Ω pour i /∈ I ′ ⊂ I , I ′ fini,P′(C) =

∏i∈I′ µ(Ci).

On montre alors que (Ω′,A′,P′) définit correctement un espace probabilisé.

Définition A.19 Une propriété est dite presque-sûre si l’ensemble Pc des éléments qui ne lavérifient pas est mesurable et négligeable, i.e. :

Pc ∈ A et µ(Pc) = 0 (A.1)

92 RAPPELS : GRAPHES & PROBABILITÉS MODERNES

93

Annexe B

JEGA : compléments de preuves

Dans cette section, nous fournissons les preuves des lemmes intermédiaires nécessaires pourdémontrer la convergence de l’algorithme JEGA.

Preuve du lemme 2.1.a)

E

[ZT

k−1∑i=1

Φ(k, i)Z

]= ZTE

[k−1∑i=1

Φ(k, i)

]Z (B.1)

où la somme dans le terme de droite peut se simplifier :

E

[k−1∑i=1

Φ(k, i)

]= E

[k−1∑i=1

(Ψ(k, i)−Ψ(k, i+ 1))

]= E [Ψ(k, 1)−Ψ(k, k)] (B.2)

= E [Wk−1Wk−2 . . .W1]− I (B.3)

Comme les matrices Wk sont i.i.d., on peut passer à l’espérance séparément :

E

[k−1∑i=1

Φ(k, i)

]= W k−1 − I (B.4)

En réinjectant cette expression dans l’équation (B.1), on obtient :

E

[ZT

k−1∑i=1

Φ(k, i)Z

]= ZT

(W k−1 − I

)Z (B.5)

Puis, par ergodicité de W :

ZT(W k−1 − I

)Z −−−→

k→∞ZT

(11T

n− I)Z = nθ2 −

∥∥Z∥∥2 (B.6)

94 JEGA : COMPLÉMENTS DE PREUVES

Preuve du lemme 2.1.b)

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Z

∥∥∥∥∥2 = E

∥∥∥∥∥(k−1∑i=1

Φ(k, i)

)Z

∥∥∥∥∥2 = E

[∥∥(Ψ(k, 1)− I) Z∥∥2]

(B.7)

= E[ZTΨ(k, 1)TΨ(k, 1)Z

]− 2E

[ZTΨ(k, 1)Z

]+∥∥Z∥∥2 (B.8)

Le premier terme de (B.8) n’est autre que le carré de la norme du vecteur d’état de l’ACM stan-dard [BGPS06], qui tend alors vers le carré de la norme du vecteur de consensus de moyenne :

E[ZTΨ(k, 1)TΨ(k, 1)Z

]−−−→k→∞

∥∥θ1∥∥2= nθ2 (B.9)

Comme (B.8) et (B.6) sont équivalentes, la limite de (B.7) est donnée par :

limk→∞

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Z

∥∥∥∥∥2 =

∥∥Z∥∥2 − nθ2 (B.10)

Preuve du lemme 2.1.c)Cette preuve repose sur la proposition suivante, dont une démonstration est fournie à l’an-

nexe C :

Proposition B.1 (cf annexe C) Soient E = R ou C, (un)n∈N une suite d’éléments de E telleque lim

n→∞‖un‖ = 0, et z ∈ E avec |z| < 1. Alors, lim

n→+∞

∑1≤k≤n

ukzn−k = 0

Comme la matriceW est symétrique et définie positive, elle peut se diagonaliser par une matriceorthogonale : notons Pj le vecteur propre de W associé à la valeur propre λj :

E

[BTk

k−1∑i=1

Φ(k, i)Bi

]=

k−1∑i=1

E[BTk E [Φ(k, i)]Bi

](B.11)

=k−1∑i=1

E[BTk

(W k−i −W k−i−1

)Bi

](B.12)

=n∑j=1

k−1∑i=1

(λk−ij − λk−i−1

j

)E[(BTk Pj) (PTj Bi

)](B.13)

où (B.12) provient de l’indépendance du bruit d’estimation par rapport aux matrices d’échanges.Pour λj = 1, λk−ij − λk−i−1

j disparaît. D’un autre côté, les termes de covariance peuvent êtrebornés par une suite convergeant vers 0 :

∣∣E [(BTk Pj) (PTj Bi

)]∣∣ =

∣∣∣∣∣∑u,v

[PjP

Tj

]uvCkiuv

∣∣∣∣∣ ≤ n2 maxu,v

maxk∈Nk>i

|Ckiuv|

∆= n2Ci (B.14)

95

Les hypothèses Ckiuv assurent la convergence de Ci vers 0, et par conséquent, E[(BT

k Pj)(PTj Bi)]

tend aussi vers 0 quelque soit le vecteur normalisé Pj . D’un autre côté, |λj| < 1 dèq queλj 6= 1. En séparant la somme sur les valeurs propres puis en développant la multiplicationpar λk−ij − λk−i−1

j , l’équation (B.13) s’exprime comme une combinaison linéaire de 2(n − 1)sommes, dont chacune vérifie les conditions de la proposition B.1 : (B.13) tend donc vers 0lorsque k →∞, indépendamment de la vitesse de décroissance des covariances.

Preuve du lemme 2.1.d)Commençons par réécrire le côte gauche de l’expression :

E

∥∥∥∥∥k−1∑i=1

Φ(k, i)Bi

∥∥∥∥∥2 =

k−1∑i=1

k−1∑j=1

E[BTj Φ(k, j)TΦ(k, i)Bi

](B.15)

En développant le terme Φ(k, j)TΦ(k, i), on observe une fois de plus que les composantes desBi et Bj qui sont colinéaires à 1 (associé à la valeur propre 1) ne sont transmises qu’au traversde Φ(k, i) :

Φ(k, j)TΦ(k, i) = Ψ(k, j)TΨ(k, i)−Ψ(k, j + 1)TΨ(k, i)

−Ψ(k, j)TΨ(k, i+ 1) + Ψ(k, j + 1)TΨ(k, i+ 1) (B.16)

Par soucis de simplicité, on pose Ξk(i, j) = E[Ψ(k, j)TΨ(k, i)

]. Notons que Ξk(i, j) se fac-

torise en externalisant les termes en i :

Ξk(i, j) = E[Ψ(k, j)TΨ(k, i)

]= E

[Ψ(k, j)TΨ(k, j)Ψ(j, i)

](B.17)

= E[Ψ(k, j)TΨ(k, j)W j−i

]= Ξk(j, j)W

j−i (B.18)

En suivant l’approche de [BGPS05] on peut majorer le rayon spectral de Ξk(j, j). Pour toutvecteur X ⊥ 1 de Rn, on a l’inégalité suivante :

XTΞk(j, j)X = XTE[Ψ(k, j)TΨ(k, j)

]X (B.19)

= XTE[Ψ(k − 1, j)TWΨ(k − 1, j)

]X (B.20)

≤ λ2XTE[Ψ(k − 1, j)TΨ(k − 1, j)

]X ≤ λk−j2 ‖X‖2 (B.21)

Cette inégalité en conjonction avec le théorème variationnel de Rayleigh-Ritz donne :

ρΨ(k, j)∆= ρ

(Ξk(j, j)−

11T

n

)(B.22)

= maxX⊥1‖X‖=1

XTE

[Ψ(k, j)TΨ(k, j)

]X≤ λk−j2 (B.23)

96 JEGA : COMPLÉMENTS DE PREUVES

où ρ(·) dénote le rayon spectral de son argument. Comme la composante de Bi colinéaire à 1n’est pas transmise, l’amplitude de ses projections sur une base de vecteurs propres de W sontredimensionnées par un facteur majoré par λj−i2 lorsqu’on lui applique W j−i. Ceci impliquel’inégalité suivante :∣∣E [BT

j VkVTk W

j−iBi

]∣∣ =∣∣∣∑λj−ip E

[BTj VkV

Tk V pV

TpBi

]∣∣∣ (B.24)

≤ (n− 1)n2λj−i2 maxu,v|Cij

uv| (B.25)

où Vk est un vecteur unitaire arbitraire de Rn et V p est le vecteur propre deW (et donc deW j−i)associé à la valeur propre λp. Soit S ijk le spectre Ξk(i, j), constitué des valeurs propres λψ devecteur propre VλΨ

. Sous ces notations, et à des fins de majoration, E[BTj Ξk(i, j)Bi

]se met

sous la forme : ∣∣E [BTj Ξk(i, j)Bi

]∣∣ =∣∣E [BT

j Ξk(j, j)Wj−iBi

]∣∣ (B.26)

≤∑

λΨ∈Sijk \1

∣∣λΨE[(BTj VλΨ

V TλΨW j−iBi

)]∣∣ (B.27)

≤ (n− 1)2ρΨ(k, j)n2λj−i2 maxu,v|Cij

uv| (B.28)

En couplant (B.23) et (B.25), on obtient la majoration suivante :∣∣E [BTj Ξk(i, j)Bi

]∣∣ ≤ (n− 1)2n2λk−i2 maxu,v|Cij

uv| (B.29)

On pose alors ξ ∆=√λ2, et comme i < j, 0 ≤ λk−i2 = ξ2k−2i ≤ ξ2k−i−j . Ceci implique alors :∣∣∣∣∣∑i<j

E[BTj Ξk(i, j)Bi

]∣∣∣∣∣ ≤ (n− 1)2n2∑i<j

λk−i2 maxu,v|Cij

uv| (B.30)

≤ n4∑i<j

ξ2k−i−j maxu,v|Cij

uv| (B.31)

La convergence vers 0 du terme de droite est alors assurée par la proposition B.2 :

Proposition B.2 (cf annexe C) Soient E = R ou C, et une suite 2D (uij)(i,j)∈N2 ∈ EN2telle

que lim(i+j)→∞

‖uij‖ = 0, et z ∈ E avec |z| < 1. Alors limn→+∞

∑1≤i,j≤n

uijz2n−i−j = 0

Lorsque i = j, un résultat classique de [BGPS05] stipule que : E[BTi Ξk(i, i)Bi

]≤ λk−i2 E

[‖Bi‖2].

Sommer sur i donne la limite diagonale :

0 ≤k−1∑i=1

E[BTi Ξk(i, i)Bi

]≤

k−1∑i=1

λk−i2 E[‖Bi‖2] −−−→

k→∞0 (B.32)

De la même manière, les termes en Ξk(i+ 1, j), Ξk(i, j + 1) et Ξk(i+ 1, j + 1) de l’équation(B.15) se majorent facilement. On obtient 4 sommes ayant une forme équivalente à (B.30) et(B.32), et qui tendent vers 0 quand k → +∞.

97

Annexe C

Convergence d’un opérateur convolutif

Dans cette partie, nous allons démontrer une généralisation d’un cas particulier du théorèmede Stolz-Cesaro.

C.1 PréliminairesSoit (E, ‖ ‖E) un espace de Banach de dimension finie sur K = R ou C. La boule unité

ouverte pour la norme euclidienne sera notée B(0, 1), i.e. :

B(0, 1)∆= z ∈ K : |z| < 1 (C.1)

et pour tout k-uplet λ d’entiers naturels, on définit |λ| par :

∀λ = (λ1, . . . , λk) ∈ Nk, |λ| ∆=

k∑i=1

λi (C.2)

Quelque soit ν ∈ E, on note Ωk[ν] l’espace des suites k-dimensionnelles ayant ν pour limiteisotrope, i.e. :

Ωk[ν]∆=

(uλ)λ∈Nk ∈ ENk : limλ→∞

uλ = ν

(C.3)

On note Ωk l’union indénombrable des Ωk[ν] :

Ωk∆=u ∈ ENk : ∃ν ∈ E, u ∈ Ωk[ν]

(C.4)

On peut équiper ces espaces de la norme “sup“ ‖u‖k∆= supλ∈Nk ‖uλ‖E , et voir chaque

espace Ωk et Ωk[0] comme des espaces vectoriels normés de dimension infinie, notés respec-tivement Ω∞k et Ω∞k [0]. Si ν 6= 0, Ωk[ν] n’est pas un espace vectoriel mais un polytope convexe.Maintenant, définissons l’opérateur convolutif Tz deH étant soit Ωk[ν] soit Ωk dans EN par :

Tz : Ωk[ν] −→ EN, u −→

∑λ∈Nkλn

uλzkn−|λ|

n∈N

(C.5)

98 CONVERGENCE D’UN OPÉRATEUR CONVOLUTIF

C.2 Limite convolutive nulleLe but de ce chapitre est de démontrer que pour tout z ∈ B(0, 1), Tz est bien défini et que

Ωk[ν] est stable sous l’action de (1− z)kTz. La motivation initiale est le cas particulier ν = 0.

Proposition C.1 ∀k ∈ N∗,∀z ∈ B(0, 1), Tz est bien défini et appartient à l’espaceL(Ω∞k , E∞).

Preuve : Nous devons prouver que :

∀z ∈ B(0, 1), ∃Mz ∈ R+∗, ∀u ∈ Ωk ⇒ ‖Tzu‖1 ≤M ‖u‖k (C.6)

‖(Tzu)n‖E ≤∑λ∈Nkλn

‖uλ‖E |z|kn−|λ| ≤ ‖u‖k

∑λ∈Nkλn

|z|kn−|λ| (C.7)

≤ ‖u‖k

(n∑i=1

|z|n−i)k

≤ ‖u‖k(1− |z|)k

(C.8)

L’équation (C.8) est valide ∀n ∈ N∗, d’où :

‖Tzu‖1 ≤‖u‖k

(1− |z|)k(C.9)

En prenant Mz = (1− |z|)−k, Tzu est un opérateur linéaire borné de Ω∞k dans E∞.L’étape suivante est de montrer que la proposition C.1 peut être renforcée par le résultat

suivant, qui prouve la stabilité par Tz des suites multidimensionnelles de limite nulle.

Proposition C.2Tz ∈ L(Ω∞k [0],Ω∞1 [0]) (C.10)

Preuve : Comme Ω∞k [0] ⊂ E∞, et par la proposition C.1, il suffit de prouver que Tz est enfait une application linéaire de Ω∞k [0] dans Ω∞1 [0]. Il ne reste qu’à montrer que :

∀z ∈ B(0, 1), ∀u ∈ Ωk[0]⇒ limn→∞

(Tzu)n = 0 (C.11)

Γnp∆= λ ∈ Nk : ∃i ∈ [1, k], n < λi ≤ (n+ p) (C.12)

fn+p =∑λ∈Nkλn+p

uλzk(n+p)−|λ| = zkpfn +

∑λ∈Γnp

uλzk(n+p)−|λ| (C.13)

Mu = Mz ‖u‖k (C.14)

∀ε1 > 0,∃n1 ∈ N,∀λ ∈ Nk, |λ| > n1 ⇒ ‖uλ‖E < ε1 (C.15)

LIMITE CONVOLUTIVE NULLE 99

∀ε2 > 0,∃n2 ∈ N,∀n ∈ N, n > n2 ⇒ |zknMu| < ε2 (C.16)

Prenons ε > 0 et ε1 = ε2(1− |z|)k ε2 = ε

2, et posons n0

∆= max(n1, n2). Alors ∀n > n0, on

a :

‖f2n‖E ≤ |z|kn ‖fn‖E + ‖u‖k

∑λ∈Γnn

|z|2kn−|λ| (C.17)

≤ |z|knMf + ε1|z|2kn∑λ∈Γnn

|z|−|λ| (C.18)

∑λ∈Γnn

|z|−|λ| =

(2n∑i=1

|z|−i)k

−

(n∑i=1

|z|−i)k

≤

(2n∑i=1

|z|−i)k

(C.19)

‖f2n‖E ≤ ε2 + ε11

(1− |z|)k= ε (C.20)

limn→∞

‖f(2n)‖E = 0 (C.21)

Soit λ ∈ Nk−1

Sjk(λ) = µ ∈ Nk : µ = (λ1, . . . , λj−1, p, λj, . . . , λk), p ∈ N (C.22)

ξ(j)λ

∆= max

µ∈Sjk(λ)‖uµ‖E (C.23)

∀λ ∈ Nk−1, ξ(j)λ −−−→i→∞

0 (C.24)

‖f2n+1‖E =

∥∥∥∥∥∥zkf2n +∑λ∈Γ2n

1

uλzk(2n+1)−|λ|

∥∥∥∥∥∥E

(C.25)

≤ |z|k ‖f(2n)‖E +∑λ∈Γ2n

1

|z|k(2n+1)−|λ| ‖uλ‖E (C.26)

En particulier, pour k = 1,

‖f2n+1‖E = ‖zf2n + un+1‖E ≤ |z| ‖f(2n)‖E + ‖u2n+1‖E −−−→n→∞0 (C.27)

Pour k ≥ 2, supposons que la proposition est vraie jusqu’au rang k − 1.

‖f2n+1‖E ≤ |z|k ‖f2n‖E +

∑λ∈Γ2n

1

|z|k(2n+1)−|λ| ‖uλ‖E (C.28)

100 CONVERGENCE D’UN OPÉRATEUR CONVOLUTIF

‖f2n+1‖E ≤ |z|k ‖f2n‖E +

∑λ∈Γ2n

1

|z|k(2n+1)−|λ| ‖uλ‖E (C.29)

≤ |z|k ‖f2n‖E +k∑j=1

∑λ∈Nk−1

λ2n+1

|z|(k−1)(2n+1)−|λ|ξ(j)λ (C.30)

≤ |z|k ‖f2n‖E +k∑j=1

(T|z|ξ(j)• )2n+1 (C.31)

Dans le dernier terme, T|z| opère clairement sur Ω∞k−1[0]. Par récurrence, ‖f(2n+ 1)‖E con-verge vers 0.

101

Références personnelles

Revues internationales– JEGA : A JOINT ESTIMATION AND GOSSIP AVERAGING ALGORITHM FOR SEN-

SOR NETWORK APPLICATIONS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-MarieGorce, rapport de recherche INRIA RR-6597, en révision par IEEE Journal on AutomaticControl

Conférences et ateliers internationaux– FINE SYNCHRONIZATION FOR WIRELESS SENSOR NETWORKS USING GOSSIP AV-

ERAGING ALGORITHMS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce,(IEEE) ICC 2008, Beijing, Chine.

– ASYNCHRONOUS AND DISTRIBUTED NONLINEAR REGULARIZATION FOR WIRE-LESS SENSOR NETWORKS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce,LOCALGOS 2009 (workshop rattaché à DCOSS 2009), Marina Del Rey, USA.

– A NEW DISTRIBUTED ALGORITHM FOR PARAMETRIC DATA MODELING IN WIRE-LESS SENSOR NETWORKS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce,SPAWC 2009, Perguia, Italie.

Conférences et ateliers nationaux– CONSENSUS DE MOYENNE POUR LA SYNCHRONISATION FINE D’HORLOGES DANS

LES RÉSEAUX DE CAPTEURS SANS-FIL, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce, JDIR 2008, Villeneuve d’Ascq.

– ESTIMATION ET MOYENNAGE CONJOINTS : PRINCIPES & APPLICATIONS, réunionde projet ARES, 24/01/2007, CITI INSA-Lyon.

– REGULARISATION DISTRIBUÉE ASYNCHRONE POUR LA CARTOGRAPHIE DANSLES RÉSEAUX DE CAPTEURS, groupe de travail PAN 2008, 24/06/2008, CEA Saclay

102 RÉFÉRENCES PERSONNELLES

– REGULARISATION DISTRIBUÉE ASYNCHRONE POUR LA CARTOGRAPHIE DANSLES RÉSEAUX DE CAPTEURS, journée GDR-ISIS, 12/06/2008, ENST Paris

– RÉGULARISATION ASYNCHRONE POUR LES RÉSEAUX DE CAPTEURS : PRINCIPESET APPLICATIONS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce, ALGO-TEL 2008, Carry-Le-Rouet

– RÉGULARISATION ASYNCHRONE POUR LES RÉSEAUX DE CAPTEURS : PRINCIPESET APPLICATIONS, Nicolas Maréchal, Jean-Benoît Pierrot et Jean-Marie Gorce, GRETSI2009, Dijon.

Projets– DISTRIBUTED ALGORITHMS FOR AVERAGE CONSENSUS : A STATE OF THE ART,

projet WinSOC, contribution au délivrable D3.1 du WP3 (System Design), 16/02/2007.

– JOINT ESTIMATION AND GOSSIP AVERAGING : PRINCIPLES & APPLICATIONS,projet WinSOC, contribution au délivrable D3.2 du WP3 (System Design), 20/11/2007.

– DISTRIBUTED CARTOGRAPHY FOR WSN, projets Sensei & eUWB 2009

– Contributions diverses aux projets SVP et ARES

Autres– ESTIMATION ET MOYENNAGE CONJOINTS : PRINCIPES & APPLICATIONS, Sémi-

naire LCNA, 24/10/2007, CEA Grenoble.

– STRATÉGIES D’OPTIMISATION DISTRIBUÉE DE LA GESTION DE LA CONNECTIV-ITÉ DANS LES RÉSEAUX ADHOC DE CAPTEURS EN FONCTION DES CONTRAINTESET OBJECTIFS APPLICATIFS, Journées des Thèses du CEA, 22/09/2007.

– ON THE ACTION OF A CONVOLUTION-LIKE OPERATOR ON SPACES OF MULTI-DIMENSIONAL SEQUENCES HAVING ISOTROPIC LIMITS, Nicolas Maréchal, note in-terne CEA.

103

Bibliographie

[ABPV+05] J.A. Acebrón, L. L. Bonilla, Conrad J. Pérez V., F. Ritort, and R. Spigler. Thekuramoto model : A simple paradigm for synchronization phenomena. Rev. Mod.Phys., 77(1) :137–185, Apr 2005.

[ACR08] T.C. Aysal, M.J. Coates, and M.G. Rabbat. Distributed average consensus withdithered quantization. IEEE Trans. Signal Processing, 56(10) :4905–4918, Oct.2008.

[Arm97] M.A. Armstrong. Basic Topology. Springer, May 1997. ISBN 0387908390.

[BAN] Projet banet : Body area networks and technologies.http ://www.banet.fr.

[BCA05a] T. Banerjee, K. Chowdhury, and D.P. Agrawal. Distributed data aggregation insensor networks by regression based compression. Proc. of IEEE MobiHoc’05,pages 8 pp.–290, Novembre 2005.

[BCA05b] T. Banerjee, K. Chowdhury, and D.P. Agrawal. Tree based data aggregation insensor networks using polynomial regression. Proc. of ICIF’05, 2 :8 pp.–, Juillet2005.

[BCC07] J. M. Bahi, S. Contassot-Vivier, and R. Couturier. Parallel Iterative Algorithms :From Sequential to Grid Computing. Chapman & Hall/CRC, 1 edition, Novembre2007. ISBN 1584888083.

[BGPS04] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Analysis and optimization ofrandomized gossip algorithms. In Proc. of IEEE CDC’04, pages 5310 – 5315,Décembre 2004.

[BGPS05] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms : Design,analysis and applications, 2005.

[BGPS06] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms.IEEE/ACM Trans. on Networking, 14 :2508–2530, 2006.

[BK05] M. Benaïm and N. El Karoui. Promenade aléatoire : Chaînes de Markov et sim-ulations ; martingales et stratégies. Ecole Polytechnique, Février 2005. ISBN2730211683.

[BK08] K. Bhaduri and H. Kargupta. A scalable local algorithm for distributed multivari-ate regression. Stat. Anal. Data Min., 1(3) :177–194, 2008.

[Bon06] F. Bonnans. Optimisation continue : Cours et problèmes corrigés. Dunod, Août2006. ISBN 2100500899.

104 BIBLIOGRAPHIE

[Bor06] C. Bordenave. Eigenvalues of euclidean random matrices, 2006.

[BP93] B. F. Beidas and G. P. Papavassilopoulos. Convergence analysis of asynchronouslinear iterations with stochastic delays. Parallel Computing, 19(3) :281 – 302,1993.

[BS07] S. Barbarossa and G. Scutari. Decentralized maximum-likelihood estimation forsensor networks composed of nonlinearly coupled dynamical systems. IEEETrans. on Signal Processing, 55(7) :3456–3470, July 2007.

[BSP06] S. Barbarossa, G. Scutari, and L. Pescosolido. Global stability of a population ofmutually coupled oscillators reaching global ml estimate through a decentralizedapproach. In Proc. of IEEE ICASSP’06, volume 4, pages IV–IV, May 2006.

[BT97] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation : Nu-merical Methods. Athena Scientific, 1997. ISBN 1886529019.

[CBFAB97] P. Charbonnier, L. Blanc-Feraud, G. Aubert, and M. Barlaud. Deterministic edge-preserving regularization in computed imaging. IEEE Transactions on Image Pro-cessing, 6(2) :298–311, February 1997.

[DE08] A. Deitmar and S. Echterhoff. Principles of Harmonic Analysis. Springer, 1edition, November 2008. ISBN 0387854681.

[DNB06] V. Delouille, R. Neelamani, and R.G. Baraniuk. Robust distributed estimationusing the embedded subgraphs algorithm. IEEE Trans. on Signal Processing,54(8) :2998–3010, Août 2006.

[DOE09] The smart grid : an introduction, 2009. US Department of Energy.

[DZ06] A. Dogandzic and B. Zhang. Distributed estimation and detection for sensor net-works using hidden markov random field models. IEEE Trans. on Signal Process-ing, 54(8) :3200–3215, Août 2006.

[EDF06] Le nivomètre à rayonnement cosmique, 2006. EDF R&D.

[Els03] J. E. Elson. Time synchronization in wireless sensor networks. PhD thesis, UCLA,2003.

[ER02] J. E. Elson and K. Römer. Wireless sensor networks : A new regime for timesynchronization. Technical report, UCLA, Juillet 2002.

[FCFZ08] P. Frasca, R. Carli, F. Fagnani, and S. Zampieri. Average consensus by gossip al-gorithms with quantized communication. In Proci of IEEE CDC’08, pages 4831–4836, 2008.

[Fie73] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Jour-nal, 23(98) :298–305, 1973.

[FK60] H. Furstenberg and H. Kesten. Products of random matrices. Ann. Math. Stat.,31 :457–469, 1960.

[FS99] A. Frommer and D. B. Szyld. On asynchronous iterations, Juin 1999.

[Gar03] O. Garet. Cours MA 6.06 : Mesure et Probabilités. Université d’Orléans, Annéeuniversitaire 2002-2003.

BIBLIOGRAPHIE 105

[GBT+04] C. Guestrin, P. Bodik, R. Thibaux, M. Paskin, and S. Madden. Distributed re-gression : an efficient framework for modeling sensor network data. In Proc. ofIPSN’04, pages 1–10, 2004.

[GFD+02] J.-M. Gorce, D. Friboulet, I. Dydenko, J. D’hooge, B. Bijnens, and I.E. Magnin.Processing radiofrequency ultrasound images : A robust approach for local spec-tral estimation by a spatially constrained parametric approach. IEEE Trans. OnUltrasonics Ferroeletricity and Frequency Control, 49(12) :1704–1719, 2002.

[HGG06] T. Holliday, A. Goldsmith, and P. Glynn. Capacity of finite state channels basedon lyapunov exponents of random matrices. IEEE Trans. on Information Theory,52(8) :3509–3532, Août 2006.

[HJ86] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, NewYork, NY, USA, 1986. ISBN 0-521-30586-1.

[JLM02] A. Jadbabaie, J. Lin, and A. Morse. Coordination of groups of mobile autonomousagents using nearest neighbor rules. IEEE Transactions on Automatic Control,48(6) :988 – 1001, 2002.

[JMB05] M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in largedynamic networks. ACM Trans. Comput. Syst., 23(3) :219–252, 2005.

[Kal97] O. Kallenberg. Foundations of modern probability. Springer, New York, 1997.ISBN 9780387227047.

[KDG03] D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregateinformation. FOCS, 00 :482, 2003.

[Kin73] J.F.C. Kingman. Subadditive ergodic theory. Ann. Probab., 1 :883–909, 1973.

[KM08] S. Kar and J.M.F. Moura. Distributed average consensus in sensor networks withquantized inter-sensor communication. In Acoustics, Speech and Signal Process-ing, 2008. ICASSP 2008. IEEE International Conference on, pages 2281–2284,31 2008-April 4 2008.

[KNS05] J. Kuruvila, A. Nayak, and I. Stojmenovic. Hop count optimal position-basedpacket routing algorithms for ad hoc wireless networks with a realistic physicallayer. IEEE JSAC, 23(6) :1267–1275, Juin 2005.

[Moh91] B. Mohar. The laplacian spectrum of graphs. In Proc. of ICTAG, volume 2, pages871–898. Wiley, 1991.

[MPG] N. Maréchal, J.B. Pierrot, and J.M. Gorce. Asynchronous and distributednonlinear regularization for wireless sensor networks. In Proc. of IEEEDCOSS/LOCALGOS 2009, special workshop adjunct.

[MPZ99] M. Mezard, G. Parisi, and A. Zee. Spectra of euclidean random matrices, 1999.

[MSP+07] M. Mehyar, D. Spanos, J. Pongsajapan, S.H. Low, and R.M. Murray. Asyn-chronous distributed averaging on communication networks. IEEE/ACM Trans-actions on Networking, 15(3) :512–520, 2007.

[Nik05] M. Nikolova. Restoration of edges by minimizing non-convex cost-functions. InImage Processing, 2005. ICIP 2005. IEEE International Conference on, volume 2,pages 786–9, September 2005.

106 BIBLIOGRAPHIE

[NN01] D. Niculescu and B. Nath. Ad hoc positioning system (APS). In Proc. of IEEEGLOBECOM’01, 2001.

[Now03] R.D. Nowak. Distributed em algorithms for density estimation and clusteringin sensor networks. IEEE Trans. on Signal Processing, 51(8) :2245–2253, Août2003.

[OSFM07] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation innetworked multi-agent systems. In Proc. of the IEEE, Janvier 2007.

[PBS08] L. Pescosolido, S. Barbarossa, and G. Scutari. Average consensus algorithmsrobust against channel noise. Proc. of IEEE SPAWC’08, pages 261–265, Juillet2008.

[Pie05] J.B. Pierrot. Time synchronization in uwb ad hoc networks using TOA estimation.In Proc. of IEEE ICU’05, Septembre 2005.

[Poo98] H. Vincent Poor. An Introduction to Signal Detection and Estimation. Springer,2nd edition, March 1998. ISBN 0387941738.

[R01] K. Römer. Time synchronization in ad hoc networks. In Proc. of MobiHoc ’01,2001.

[Spi09] D. Spielman. Spectral graph theory and its applications (Applied Mathematics500A). MIT, Spring 2009.

[SRB07] I.D. Schizas, A. Ribeiro, and G.B. Biannakis. Consensus-based distributed pa-rameter estimation in ad hoc wireless sensor networks with noisy links. Proc. ofIEEE ICASSP’07, 2 :II–849–II–852, Avril 2007.

[TSJ07] A. Tahbaz-Salehi and A. Jadbabaie. Necessary and sufficient conditions for con-sensus over random independent and identically distributed switching graphs.Proc. of IEEE CDC’07, 2007.

[UCR08] D. Ustebay, M. Coates, and M. Rabbat. Greedy gossip with eavesdropping. InProc. of ISWPC 2008, pages 759–763, May 2008.

[WCWG07] G. Wang, J. Cao, H. Wang, and M. Guo. Polynomial regression for data gatheringin environmental monitoring applications. Proc. of IEEE GLOBECOM’07, pages1307–1311, Novembre 2007.

[Whi05] E.C. Whithman. SOSUS : The "secret weapon" of undersea surveillance. Under-sea Warfare, 7(2), Winter 2005.

[WLLP01] B. Warneke, M. Last, B. Liebowitz, and K.S.J. Pister. Smart dust : communicatingwith a cubic-millimeter computer. Computer, 34(1) :44–51, Jan 2001.

[XB03] L. Xiao and S. Boyd. Fast linear iterations for distributed averaging, 2003.

[XBL05] L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion basedon average consensus. In Proc. of IPSN’05, page 9, Piscataway, NJ, USA, 2005.IEEE Press.

[XBL06a] L. Xiao, S. Boyd, and S. Lall. A space-time diffusion scheme for peer-to-peerleast-squares estimation. In Proc. of ISPN ’06, pages 168–176. ACM Press, 2006.

BIBLIOGRAPHIE 107

[XBL06b] L. Xiao, S. Boyd, and S. Lall. A space-time diffusion scheme for peer-to-peerleast-squares estimation. In Proc. of IPSN ’06, pages 168–176, New York, NY,USA, 2006. ACM Press.

[ZA] Zigbee alliance. http ://www.zigbee.org.

108 BIBLIOGRAPHIE

RÉSUMÉ - ABSTRACT 109

CONSENSUS DE MOYENNE DANS LES RÉSEAUX DE CAPTEURS :APPLICATIONS ET OPTIMISATION DE PERFORMANCES

En fonction de leur application, les réseaux ad hoc de capteurs peuvent être composés d’unnombre plus ou moins important de nœuds avec des contraintes sur leur taille, coûts, consom-mation énergétique et par corollaire sur tout un ensemble d’autres paramètres. Ces contraintescaractéristiques se traduisent par le besoin d’une utilisation de méthodes distribuées d’auto-organisation et de traitement des données. En particulier, la classe des algorithmes de consen-sus de moyenne (ACM) initialement conçue pour le calcul de la valeur moyenne d’un jeu deparamètres distribués, est une brique de base amenée à jouer un rôle important pour des proto-coles/algorithmes applicatifs complexes.

L’objectif de cette thèse est de fournir des éléments d’amélioration et d’application de cettecatégorie d’algorithme. La thèse s’est focalisée dans un premier temps sur des méthodes decaractérisation et d’optimisation des ACM de l’état de l’art. Dans un second temps, deux nou-veaux algorithmes sont proposés afin de réduire le coût énergétique. Le premier se place dansun cadre d’estimation et vise à prendre en compte de nouvelles informations plus rapidement.Le second permet d’utiliser la nature diffusante du canal radio et présente l’avantage de ne pasnécessiter de mécanismes contrôle (acquittements). Enfin, des applications à la synchronisationfine d’horloge (couche physique) et à la cartographie paramétrique (couche application) sontdécrites et apportent une concrétisation du besoin.

AVERAGE CONSENSUS FOR SENSOR NETWORKS :APPLICATIONS & PERFORMANCE OPTIMISATION

Depending on their applications, sensor networks may be composed of a varying numberof nodes having severe constraints on their size, cost, energetic consumption, and as a conse-quence on a large set of related parameters. These characteristics involve the need of distributedmethods for organization and data processing. In particular, the class of average consensusalgorithms (ACA), initially designed for computing the empirical mean of a set of input pa-rameters, is a building block which is about to play an important role for complex applicativealgorithms/protocols.

The goal of this thesis is to provide elements for improving this category of algorithms, andvalidating them on some applications. In a first time, it focuses on characterization and optimiza-tion methods applied to ACA from the state of the art. Then, two new algorithms are proposedin order to reduce the energetic cost. The first one takes place in an estimation framework andaims at taking quickly account of fresh information. The second algorithm focuses on reduc-ing the communication cost by exploiting the diffusive nature of wireless communications andrequiring no transmission control mechanism (such as acknowledgements or synchronization).To finish with, applications to fine synchronization of clocks (physical layer) and to parametriccartography (application layer) are given.

Documents

Consensus de moyenne dans les réseaux de capteurstheses.insa-lyon.fr/publication/2009ISAL0078/these.pdf · 2016-01-11 · THÈSE présentée pour obtenir le grade de docteur de l’Institut