Consensus de moyenne dans un réseau de capteurs sans

fil sécurisé
Alain Kibangou

To cite this version:

Alain Kibangou. Consensus de moyenne dans un réseau de capteurs sans fil sécurisé. CIFA 2012
- 7ème Conférence Internationale Francophone d’Automatique, Jul 2012, Grenoble, France. Paper
ThAM2T8.5. �hal-00735066�

HAL Id: hal-00735066

[Link]
Submitted on 25 Sep 2012

HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est

archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
 Consensus de moyenne dans un réseau de
capteurs sans fil sécurisé
Alain Y. Kibangou ∗
∗
GIPSA-LAB,
UMR 5216 – Université Joseph Fourier, CNRS
11, rue des mathématiques. Grenoble Campus, BP 46,
F-38402 Saint Martin d’Hères Cedex, France.
[Link]@[Link]

Résumé : Dans cet article, notre étude est relative au problème du consensus de moyenne dans
un réseau de capteurs. Contrairement à différents algorithmes, proposés dans la littérature, qui
ne garantissent qu’une convergence asymptotique, nous proposons deux nouvelles approches
de synthèse des matrices de consensus permettant d’atteindre le consensus de moyenne en un
nombre fini d’itérations. Dans des travaux récents, nous avons montré que ce nombre n’est autre
que celui des valeurs propres distinctes et non nulles de la matrice Laplacienne du graphe. Dans
le présent article, nous montrons comment faire la synthèse des matrices de consensus dans le
cas d’un réseau sécurisé. En particulier, nous montrons que dans le cas d’un graphe de Hamming
ou plus généralement d’un graphe distance-régulier le consensus de moyenne peut être réalisé
en un nombre d’itérations égal au diamètre du graphe associé.

Mots-clés: Consensus ; Réseaux de capteurs ; Algorithmes distribués ; Réseaux sécurisés ;

Théorie des graphes.

1. INTRODUCTION Cependant, les réseaux de capteurs sans fil ont plusieurs

caractéristiques qui ne garantissent ni l’intégrité physique
des capteurs ni la confidentialité des messages échangés.
Tout d’abord, un canal sans fil est ouvert à tous. Avec
Ces dernières années de nombreuses contributions ont été une interface radio configurée sur la même bande de
apportées, tant dans la communauté de l’automatique que fréquences, n’importe qui peut avoir accès aux messages
de celle du traitement du signal, en termes d’algorithmes échangés et même s’inviter à la conversation. Ensuite,
d’estimation distribuée à l’aide de capteurs sans fil aussi les ressources limitées en calcul et en mémoire ne per-
bien statiques que mobiles, Blondel et al. (2005); Olfati- mettent pas d’implémenter des algorithmes de sécurité
Saber et Murray (2004). Un tel effort est motivé par le robustes. Un réseau de capteurs sans fil peut donc être
grand potentiel qu’ont les réseaux de capteurs en termes sujet à différentes attaques extérieures. En conséquence,
d’applications. il est nécessaire de rajouter, via la couche réseau, des
algorithmes de cryptage de complexité calculatoire faible
La plupart des algorithmes d’estimation distribuée sont mais d’efficacité maximale. Ainsi, la couche réseau peut
basés sur le concept du consensus. L’objectif principal induire un graphe différent de celui engendré par la couche
d’un algorithme de consensus étant de faire converger physique. Pour être voisins, il ne suffit plus que deux
tous les nœuds du réseau vers une valeur commune capteurs soient dans un même rayon de communication
après négociations. Par exemple, le consensus de moyenne, mais il faut en plus qu’ils soient à même de partager une
consistant à faire converger tous les nœuds vers la moyenne même clé cryptographique. Dans ce cas, la structure du
de leurs valeurs initiales, peut être obtenu en mettant à graphe est imposée par la technique de cryptage utilisée.
jour de manière itérative les valeurs locales des différents
nœuds comme étant une somme pondérée des valeurs La plupart des travaux dédiés à l’estimation distribuée
issues des voisins. basée sur des algorithmes de consensus de moyenne ne
considèrent que le graphe lié à la couche physique. Dans cet
Une caractéristique importante d’un réseau de capteurs article, nous nous intéressons au problème du consensus
sans fil concerne la topologie du réseau. Les différents dans des réseaux sécurisés utilisant des techniques de pré-
nœuds du réseau sont généralement représentés comme distribution de clés. En particulier, nous montrons qu’en
étant les sommets d’un graphe dont les arêtes représentent absence de bruit, le consensus de moyenne peut être atteint
l’existence d’une communication entre les nœuds associés. en un nombre fini d’itérations.
En raison de ses ressources limitées, un nœud-capteur
ne peut communiquer qu’avec d’autres nœuds se trou- Le problème du consensus de moyenne en un nombre fini
vant dans son rayon de communication. Ainsi, la couche d’itérations a été étudié par un certain nombre d’auteurs.
physique du réseau donne lieu généralement à un graphe Dans Kingston et Beard (2006), la méthode proposée re-
géométrique aléatoire. quiert un graphe complet durant au moins une itération.
Un algorithme d’agrégation de données est proposé par Le- où les valeurs hors diagonales wi,j de la matrice W sont
chevin et al. (2009), approche nécessitant davantage de res- non-nulles si et seulement si j ∈ Ni . Le consensus de
sources en mémoire qu’une approche itérative. Une autre moyenne est atteint si
approche plus compatible aux ressources des capteurs est 1
celle proposée par Sundaram et Hadjicostis (2008). L’idée lim x(t) = 11T x(0),
t→∞ N
principale exploitée par les auteurs est qu’au bout d’un cer-
ce qui signifie que
tain temps, les capteurs ont suffisamment d’observations
leur permettant de reconstruire l’état initial du système 1
lim Wt = 11T .
et d’en déduire toute fonction de celui-ci, la moyenne t→∞ N
par exemple. Dans Sundaram et Hadjicostis (2007), les La condition nécessaire et suffisante permettant d’at-
mêmes auteurs montrent que chaque capteur peut calculer teindre le consensus est : W doit admettre 1 comme valeur
la valeur du consensus comme une combinaison linéaire de propre simple, les autres valeurs propres étant de valeur
ses valeurs antérieurs après D itérations, D étant le degré absolue strictement inférieure à 1. Les vecteurs propres
du polynôme caractéristique de la matrice de consensus à gauche et à droite associés à la valeur propre 1 étant
associée. Cependant, cette approche nécessite le calcul du donnés par N1 1 et 1, Xiao et Boyd (2004). Grâce à cette
rang d’une matrice et de son noyau ; ce qui a un coût condition, la convergence asymptotique est assurée.
de calcul élevé. Dans Ko (2010), le consensus en temps
Plusieurs matrices de pondération W permettent d’assurer
fini est formulé comme un problème de factorisation de
une convergence asymptotique. L’une d’elles, couramment
matrices. Cependant, la méthode requiert une topologie
utilisée, est reliée à la matrice laplacienne du graphe de la
variable dans le temps, les variations étant guidées par
manière suivante : W = I − γL, avec 0 < γ < 1/Nmax ,
un nœud central. Récemment, nous avons reformulé le
Nmax = max {N1 , · · · , NN }, Olfati-Saber et al. (2007).
problème comme étant un problème de diagonalisation
conjointe de matrices permettant de conserver la topologie La vitesse de convergence de l’algorithme du consensus est
du réseau constante. La solution proposée requiert toute- directement liée à la seconde plus grande valeur propre de
fois l’utilisation du spectre de la matrice Laplacienne du la matrice de pondération W. Par conséquent, différents
graphe, Kibangou (2011, 2012). auteurs ont proposé différentes techniques pour accélérer
la convergence en modifiant adéquatement le spectre de la
matrice de pondération, Xiao et Boyd (2004); Kokiopoulou
2. POSITION DU PROBLÈME
et Frossard (2009); Montijano et al. (2011). Bien que les
algorithmes de consensus rapide soient suffisant dans de
Considérons un réseau représenté à l’aide d’un graphe nombreux cas, la détermination de l’arrêt de l’algorithme
non-orienté et connecté G = (N , E) où N = {1, · · · , N } n’est cependant pas claire. Il est donc parfois plus judicieux
désigne l’ensemble des sommets et E ⊆ N × N l’ensemble de recourir à des algorithmes garantissant une valeur
d’arêtes. Nous notons par Ni l’ensemble des nœuds pou- exacte en un nombre fini d’itérations. Par ailleurs de tels
vant communiquer avec le nœud ni (pour l’instant nous ne algorithmes peuvent permettre de mieux évaluer la durée
distinguons pas la couche physique de la couche réseau). de vie du réseau. Dans la suite de cet article, nous allons
Son cardinal est noté Ni . La matrice Laplacienne L du développer de nouvelles techniques de calcul de consensus
graphe G, est définie par ses éléments lij donnés par : en temps fini en considérant des connexions sécurisées via
Ni si i = j un schéma de prédistribution de clés cryptographiques.
(
lij = −1 si j ∈ Ni
0 partout ailleurs 3. SÉCURISATION DES COMMUNICATIONS À
Le graphe étant non-orienté, la matrice Laplacienne est L’AIDE DE CLÉS CRYPTOGRAPHIQUES
symétrique (L = LT ). Ses valeurs propres, λ0 < λ1 ≤
· · · ≤ λN −1 , permettent d’appréhender de nombreuses pro- La plupart des protocoles de sécurité sont basés sur des
priétés associées à la topologie du graphe G. En particulier, opérations cryptographiques nécessitant des clés. Pour as-
λ0 = 0 avec 1, le vecteur ayant tous ses éléments égaux à surer la confidentialité, une opération de cryptage nécessite
1, comme vecteur propre. une clé embarquée dans un algorithme permettant de
A présent, supposons que chaque nœud n dispose initiale- transformer un message en un cryptogramme. Deux types
ment d’une valeur scalaire xn (0) ∈ < et définissons par de clés sont utilisées dans les systèmes cryptographiques.
T
x(0) = ( x1 (0) · · · xN (0) ) le vecteur des valeurs ini- La première est la clé symétrique dont les propriétés
tiales du réseau. Nous nous intéressons à calculer la valeur théoriques ont été établies dans Shannon (1949). Dans
moyenne des valeurs initiales au moyen d’un algorithme ce type d’approche, la source et le destinataire partagent
distribué, chaque nœud ne pouvant communiquer qu’avec une clé secrète inconnue des autres nœuds du réseau. La
ses voisins. Ainsi, à chaque itération, le nœud n met à source code son message M avec la clé K à l’aide d’un
jour sa valeur xn (t) comme une combinaison linéaire des algorithme de cryptage E générant ainsi un cryptogramme
apports de ses voisins et de sa valeur antérieure : C = E(M, K). Après réception du message crypté, le
X destinataire recouvre le message original à l’aide d’un
xn (t + 1) = wnn xn (t) + wnm xm (t) (1) algorithme de décryptage D et de la clé secrète : M =
m∈Nn
D(C, K), Zhou et al. (2008).
De manière équivalente, sous forme matricielle on obtient :
La seconde approche considère une clé asymétrique.
Chaque nœud dispose d’une paire de clés {Ks , Kp }. La
x(t + 1) = Wx(t) (2) clé privée Ks est gardée secrète par son détenteur qui
diffuse sa clé publique Kp . Ainsi chaque source désirant Bose-Mesner (voir Bose et Mesner (1959)). Il en découle
envoyer un message M vers le source de clé publique Kp les propriétés suivantes :
code le message de la manière suivante : C = E(M, Kp ). XD
A la réception le message est décrypté en faisant M = Am = 11T (3)
D(C, Ks ). Il est à noter que la mise en place d’une ap- m=0
proche de sécurisation asymétrique est plus complexe que et
l’approche asymétrique. Par conséquent, la plupart des
protocoles de sécurité dans les réseaux de capteurs sans AAm = bm−1 Am−1 +am Am +cm+1 Am+1 , m = 1, · · · , D
fil utilisent des clés symétriques. (4)
où
La procédure de sécurisation d’un réseau de capteurs am + bm + cm = k,
sans fil inclut deux étapes. Avant d’être déployés, les a0 = 0, b0 = k, bD = 0, c0 = 1, et c1 = 1.
nœuds sont configurés avec un certain nombre de clés.
Une fois déployés, les nœuds choisissent les clés à utiliser 3.2 Graphe de Hamming
après plusieurs échanges de messages. Ce choix peut être
fait via un serveur de clés, Perrig et al. (2002). Bien Le graphe de Hamming H(D, q) de dimension D sur un
évidemment l’existence d’un tel serveur central en fait alphabet S de taille q est le graphe dont les sommets sont
un point névralgique dont toute défaillance ruinerait les l’ensemble des mots de longueur D sur un alphabet S.
efforts de sécurisation entrepris. Par conséquent, la plupart Deux sommets sont adjacents dans H(D, q) s’ils sont à une
des solutions récemment proposées sont distribuées, Zhou distance de Hamming de 1. Ce graphe admet les propriétés
et al. (2008). Dans l’une d’elles, chaque nœud est associé à suivantes Brouwer et al. (1989) :
un identifiant unique (n1 , n2 , · · · , nk ) de sorte que tous les – Chaque sommet est connecté à exactement D(q − 1)
nœuds forment une grille de dimension k. Chaque nœud, voisins ;
lors de sa configuration, est équipé d’un certain nombre – Le diamètre du graphe est égal à D ;
de clés qu’il peut partager avec d’autres nœuds avec qui il – Le graphe est D(q − 1)-régulier ;
partage la même dimension. Ainsi, deux nœuds ne peuvent – Le graphe est distance régulier avec comme paramètres
partager une secrète que si la distance de Hamming de ci = i et bi = (q − 1)(D − i).
leurs identifiants est égale à 1. En d’autres termes, tous les – Sa matrice d’adjacence admet comme
éléments de l’identifiant sont égaux sauf un, Zhou et Fang   valeurs propres
D
(2007). En appliquant un tel protocole, le graphe résultant (q − 1)D − qi de multiplicité (q − 1)i , i =
i
de la couche réseau est donc un graphe de Hamming dont
nous allons exploiter différentes propriétés. 0, 1, · · · , D.

3.1 Algèbre de Bose-Mesner

Rappelons tout d’abord quelques définitions :

– Deux sommets sont adjacents s’il existe une arête entre
eux. On définit alors la matrice d’adjacence A d’entrées
Aij = 1 s’il existe une arête entre les sommets i et j et
Aij = 0 dans le cas contraire.
– Un chemin est une liste de sommets telle qu’il existe une
arête entre chaque paire de sommets. Ce chemin est dit
simple si chaque arête est empruntée une seule fois.
– La longueur du chemin correspond au nombre d’arêtes
parcourues. Fig. 1. Graphe cubique en treillis ou graphe de Hamming
– La distance entre deux sommets est la longueur du plus H(3, q), avec q = 3
court chemin contenant ces deux sommets.
– Le diamètre d’un graphe est la distance maximale 4. CONSENSUS EN TEMPS FINI DANS UN RÉSEAU
quelque soit la paire de sommets. SÉCURISÉ REPRÉSENTÉ À L’AIDE D’UN GRAPHE
– Un graphe est dit régulier de degré (ou valence) k si tous DE HAMMING
les sommets ont exactement le même nombre de voisins.
– Un graphe est dit distance-régulier si pour tous sommets
Nous allons à présent considérer le problème du consensus
ni et nj le nombre de sommets voisins de ni à distance
en un nombre fini d’itérations dans un réseau représenté
d et le nombre de sommets voisins de nj à distance δ ne
à l’aide d’un graphe de Hamming. Il s’agit de faire la
dépendent que de d, δ et de la distance entre ni et nj .
synthèse d’un ensemble de matrices {Wi }i=1,··· ,d , com-
Soit G(N , E) un graphe distance-régulier de valence k. patibles avec le réseau, telles que
Notons Rm ⊂ E le sous-ensemble d’éléments (ni , nj ) tels d
Y 1
que ni et nj sont à une distance m. Soit Am la matrice Wi = 11T . (5)
N
d’adjacence du graphe Xm = (N , Rm ). Evidemment A0 = i=1
I, la matrice identité et A1 = A, la matrice d’adjacence Notons qu’une matrice Wi est dite compatible avec le
du graphe G. Les matrices Am , m = 0, · · · , D, engendrent réseau s’il existe une matrice Qi telle que W = Qi ◦ A
une algèbre de dimension (D + 1) de matrices symétriques où ◦ représente le produit de Hadamard et A la matrice
ayant une diagonale constante. Cette algèbre est celle de d’adjacence du graphe représentant le réseau.
A cet effet, nous allons centrer notre étude sur des matrices un graphe k-régulier, D = kI. Sachant que les valeurs
de consensus dépendant de la matrice Laplacienne du propres distinctes de la matrice d’adjacence d’un graphe
graphe et paramétrées par des constantes αi : de Hamming H(D, q) sont données par (q − 1)D − qi,
Wi = I − αi L. i = 0, 1, · · · , D et sachant que la valence de ce graphe
de Hamming est D(q − 1), nous déduisons que :
On peut aisément vérifier que ces matrices sont compa-
tibles avec le réseau. λi = qi, i = 0, 1, · · · , D.
Par application du théorème 1, nous déduisons les valeurs
4.1 Synthèse basée sur une diagonalisation conjointe de des constantes αi . 
matrices
Nous pouvons noter que dans le cas d’un graphe de
La matrice Laplacienne du graphe étant sysmétrique, sa Hamming et plus généralement dans le cas des graphes
diagonalisation est donnée par : distance-régulier, le nombre d’itérations de l’algorithme
de consensus proposé est exactement égal au diamètre du
L = UΛ ΛUT , UT U = I, UUT = I graphe. Rappelons que celui-ci représente la distance entre
 
1 les deux points les plus distants du réseau.
où Λ = diag(λ0 , λ1 , · · · , λN −1 ) et U = √ 1 Ũ avec
N Exemple 1. Considérons un graphe de Hamming H(3, 2).
ŨT Ũ = IN −1 et ŨT 1 = 0. D’après le corollaire du théorème 1, les matrices de consen-
sus sont données par : W1 = I − 21 L, W2 = I − 14 L et
Par suite, les matrices de pondération Wi peuvent être
exprimées en fonction des valeurs propres et des vecteurs W3 = I − 61 L. Le tableau 1 décrit les trois itérations
propres de la matrice Laplacienne : de l’algorithme de consensus permettant de calculer la
moyenne des valeurs initiales.
Wi = U (I − αiΛ ) UT .
Par conséquent, l’équation (5) peut être récrite comme : Tab. 1. Consensus de moyenne dans un graphe
d
!
Y 1 H(3, 2)
U (I − αiΛ ) UT = 11T (6)
i=1
N x(0) x(1) x(2) x(3)
4.1000 2.6000 2.9100 3.1950
ou de manière équivalente :
! 3.1000 2.4150 3.4800 3.1950
d
Y 2.9100 3.5350 3.4800 3.1950
U (I − αiΛ ) UT = Udiag(1 0 · · · 0)UT . (7) 2.1700 4.2300 2.9100 3.1950
i=1 3.2900 3.0900 3.4800 3.1950
Nous pouvons alors formuler le théorème suivant : 1.6600 4.6750 2.9100 3.1950
3.7100 3.5550 2.9100 3.1950
Théorème 1. Soient λ1 6= λ2 6= · · · 6= λD 6= 0 les D valeurs 4.6200 1.4600 3.4800 3.1950
propres distinctes non-nulles de la matrice Laplacienne
L du graphe représentant le réseau. Les matrices de
pondérations Wi = I − λ1i L, i = 1, · · · , D, permettent Exemple 2. Considérons un graphe de Hamming H(4, 2).
d’atteindre la valeur exacte du consensus de moyenne en D’après le corollaire du théorème 1, les matrices de consen-
D itérations. sus sont données par : W1 = I − 21 L, W2 = I − 14 L,
W3 = I − 61 L, et W4 = I − 81 L. Le tableau 2 décrit les
Preuve : A partir de l’équation (7), nous obtenons : quatre itérations de l’algorithme de consensus permettant
d  de calculer la moyenne des valeurs initiales.
Y 1 si j = 0
(1 − αi λj ) =
0 sinon
i=1
Tab. 2. Consensus de moyenne dans un graphe
Puisque λ0 = 0, nous avons donc à résoudre H(4, 2)
d
Y
(1 − αi λj ) = 0, j = 2, 3, · · · , N. x(0) x(1) x(2) x(3) x(4)
i=1
2.3100 4.4550 2.7375 3.2337 3.1800
3.8600 1.6800 3.9175 3.1262 3.1800
En prenant en compte les multiplicités des valeurs propres, 4.2500 1.1000 4.3550 3.1262 3.1800
il n’y a que D équations distinctes. Une solution de ce 1.5000 6.2350 1.7100 3.2337 3.1800
système d’équation est alors obtenue en prenant αi égal 1.6000 4.7400 2.7800 3.1262 3.1800
à l’inverse d’une des valeurs propres λi de la matrice 3.5700 2.0050 3.2850 3.2337 3.1800
Laplacienne.  2.6000 3.6600 2.8475 3.2337 3.1800
3.6900 1.5650 3.8075 3.1262 3.1800
Nous en déduisons le corollaire qui suit : 3.8200 3.4300 2.8750 3.1262 3.1800
Corollaire 1. Les matrices de pondérations 3.7000 2.9750 3.1900 3.2337 3.1800
1 4.2900 3.0700 2.7525 3.2337 3.1800
Wi = I − L, i = 1, · · · , D 3.6700 2.4950 3.9025 3.1262 3.1800
qi 4.2000 1.0000 4.3275 3.2337 3.1800
permettent d’atteindre la valeur exacte du consensus de 2.0000 5.1550 2.3275 3.1262 3.1800
moyenne dans un graphe de Hamming H(D, q). 2.9800 3.9850 2.7650 3.1262 3.1800
2.8400 3.3300 3.3000 3.2337 3.1800
Preuve : On sait que L = D − A où D est la matrice
diagonale contenant les degrés de chaque sommets. Pour
4.2 Synthèse basée sur l’algèbre de Bose-Mesner comme des combinaisons linéaires de puissances de la
matrice Laplacienne :
m
En utilisant différentes propriétés issues de l’algèbre de X
Bose-Mesner, nous allons à présent montrer comment Am = γi,m Li , (10)
faire la synthèse des matrices de pondération Wi = I − i=0
αi L. Pour ce faire, nous énonçons tout d’abord le lemme les coefficients γi,m étant les éléments de la matrice trian-
suivant : gulaire inférieure Γ = B−1 avec :
1 0 ··· 0
 
Lemme 1. Etant donnée la matrice Laplacienne L = kI −
A d’un graphe distance-régulier de valence k et de pa-  β0,1 β1,1 · · · 0 
ramètres bi et ci , les matrices Lm sont à diagonale princi- B=  ... .. . . ..  (11)
. . . 
pale constante et peuvent être développées sur la base des
β0,m β1,m · · · βm,m
matrices d’adjacence associées à l’algèbre de Bose-Mesner :
m Par suite, tenant compte des équations (3) et (10) nous
pouvons conclure que :
X
Lm = βi,m Ai (8)
D X m
i=0 X γi,m i 1
où les coefficients de développement s’écrivent de manière L = 11T . (12)
m=0 i=0
N N
recursive comme suit, pour i = 1, · · · , m + 1 :
Nous pouvons alors formuler le théorème suivant :
Théorème 2. L’ensemble des matrices de pondération
βi,m = −ci βi−1,m−1 + (bi + ci )βi,m−1 − bi βi+1,m−1 ,
Wi = I − 1i L, i = 1, · · · , D, permet d’atteindre le consen-
i = 1, · · · , m sus de moyenne en D itérations si les pas i sont les racines
D P m
βi,m = 0, i>m du polynôme p(t) =
P
γi,m ti .
β0,0 = 1. (9) m=0 i=0

On peut montrer que les racines du polynôme p(t) cor-

Preuve : Nous pouvons vérifier que cette proposition est respondent aux valeurs propres non nulles de la matrice
vraie pour L0 et pour L. Supposons qu’elle est vraie pour Laplacienne. Ce qui permet de conclure que les deux
Lm−1 et montrons qu’elle l’est aussi au rang supérieur : approches de synthèse des matrices de consensus sont
strictement équivalentes.
m−1
On peut par ailleurs noter que grâce aux symétries
X
Lm = LLm−1 = (kI − A) βi,m−1 Ai
i=0
présentes dans le réseau. Le nombre d’itérations ne dépend
m−1 m−1
pas du nombre de nœuds dans le réseau. Pour un graphe
X X de Hamming H(D, q) contenant q D sommets, le nombre
= kβi,m−1 Ai − βi,m−1 AAi
d’itérations ne dépend que de D. Ainsi, pour un réseau de
i=0 i=0
N nœuds tel que N = q1D1 = q2D2 avec D1 > D2 , il vaut
Tenant compte de la propriété (4), nous obtenons : mieux structurer la sécurisation du réseau en utilisant des
identifiants les plus courts possibles. En d’autres termes, il
m−1
X m−1
X vaut mieux choisir des identifiants de longueur D2 plutôt
Lm = (k − ai )βi,m−1 Ai − bi−1 βi,m−1 Ai−1 que D1 . On peut notamment se restreindre à l’utilisation
i=0 i=0 d’identifiant de longueur D = 3. Dans ce cas, le graphe
m−1
X correspondant est aussi appelé graphe cubique en treillis
− ci+1 βi,m−1 Ai+1 Laskar (1969).
i=0 Exemple 3. Considérons de nouveau un graphe de Ham-
Sachant que c0 = 0, nous pouvons récrire l’expression ming H(3,2). On peut aisément vérifier que la matrice B,
précédente de la manière suivante : définie par (11), est donnée par :
1 0 0 0
 
m−1 m−2  3 −1 0 0 
B= .
12 −6 2 0 
X X
Lm = (k − ai )βi,m−1 Ai − bi βi+1,m−1 Ai
i=0 i=0 54 −34 18 −6
m
X Par suite, on en déduit :
− ci βi−1,m−1 Ai 1 0 0 0
 
i=0  3 −1 0 0 
Γ=
Les termes βi,m−1 étant nuls pour i > m − 1 et sachant 3 −3 1/2 0 
que k − ai = bi + ci nous obtenons : 1 −10/3 3/2 −1/6
m−1 D’après le théorème 2, les pas i , i = 1, 2, 3 sont les racines
du polynôme p(t) = −1 3 2 22
6 t + 2t − 3 t + 8. On obtient
X
Lm = ((bi + ci )βi,m−1 − bi βi+1,m−1 − ci βi−1,m−1 ) Ai
i=0
i ∈ {2, 4, 6}, qui sont les valeurs propres non-nulles de
la matrice Laplacienne du graphe.
d’où l’expression de βi,m donnée en (9). 
Exemple 4. Dans cet exemple, nous considérons un graphe
Une conséquence intéressante de ce Lemme est que de Hamming H(5,3). C’est un graphe de valence 10 conte-
réciproquement nous pouvons écrire les matrices Ai nant 243 nœuds. Ces paramètres sont ci = i et bi = 2(5−i),
i = 0, 1, · · · , D. En utilisant les formules récursives don- Kibangou, A. (2011). Finite-time average consensus based
nant les paramètres βi,m , on obtient la matrice B suivante. protocol for distributed estimation over awgn channels.

1 0 0 0 0 0
 In Proc. of the 50th IEEE Conference on Decision and
 10 −1 0 0 0 0  Control (CDC). Orlando, Fl, USA.
 110

−19 2 0 0 0 
 Kibangou, A. (2012). Graph laplacian based matrix design
B= . for finite-time distributed average consensus. In Proc. of
 1290 −297 54 −6 0 0 
the American Conference on Control(ACC). Montréal,

 15870 −4395 1062 −204 24 0 
202650 −63921 18510 −4710 960 −120 Canada.
Kingston, D. et Beard, R. (2006). Discrete-time average
Après avoir déduit les paramètres γi,m , on peut conclure consensus under switching network topologies. In Proc.
que les pas i , i = 1, 2, 3 sont les racines du polynôme of American Control Conference (ACC). Minneapolis,
p(t) = 243−184.95t+50.625t2 −6.375t3 +0.375t4 −0.0083t5 . Minenesota, USA.
On obtient i ∈ {3, 6, 9, 12, 15}, qui sont les valeurs propres Ko, C.K. (2010). On matrix factorization and scheduling
non-nulles de la matrice Laplacienne du graphe. for finite-time average consensus. Thèse de doctorat,
California Institue of Technology, Pasadena, California,
5. CONCLUSION USA.
Kokiopoulou, E. et Frossard, P. (2009). Polynomial filte-
De nombreuses contributions récentes parues dans la ring for fast convergence in distributed consensus. IEEE
littérature montrent l’intérêt d’utiliser l’algorithme de Trans. on Signal Processing, 57, 342–354.
consensus en vue de distribuer une tâche d’estimation, Laskar, R. (1969). Eigenvalues of the adjacency matrix of
de commande ou plus généralement d’optimisation. La cubic lattice graphs. Pacific Journal of Mathematics,
plupart de ces algorithmes ont des propriétés de conver- 29(3), 623–629.
gence asymptotique dont la rapidité est liée au spectre Lechevin, N., Rabbath, C., et Zhang, Y. (2009). Informa-
des matrices de consensus. Dans cet article, nous avons tion broadcasting algorithm for finite-time reaching-at-
développé un nouveau résultat permettant d’atteindre le risk consensus with application to weapon-target assign-
consensus de moyenne en un nombre fini d’itérations. ment. In Proc. of American Control Conference (ACC),
Cette performance est réalisée en utilisant des matrices 3286–3291. St. Louis, MO, USA.
de consensus variant dans le temps, la loi de variation Montijano, E., Montijano, J., et Sagues, C. (2011). Fast
étant fixée par l’ensemble des valeurs propres non-nulles distributed consensus with Chebyshev polynomials. In
de la matrice Laplacienne du graphe. Bien souvent, l’étude 2011 American Control Conference, 5450–5455. San
du problème du consensus est menée en ne considérant Francisco, CA, USA.
que le graphe induit par la couche physique ; graphe dans Olfati-Saber, R., Fax, A., et Murray, R. (2007). Consen-
lequel l’existence d’une arête est liée à la présence de sus and cooperation in networked multi-agent systems.
capteurs dans le rayon de communication de la source. En Proc. of the IEEE, 95(1), 215–233.
y ajoutant les contraintes de sécurité, le graphe engendré Olfati-Saber, R. et Murray, R. (2004). Consensus problems
par la couche réseau peut avoir des propriétés pouvant in networks of agents with switching topology and time-
être exploitées pour améliorer les algorithmes d’estima- delays. IEEE Trans. on Automatic Control, 49, 1520–
tion. Lorsque le schéma de sécurisation des données d’un 1533.
réseau engendre un graphe distance-régulier, nous avons Perrig, A., Szewczyk, R., Tygar, J., Wen, V., et Culler, D.
développé une nouvelle approche de synthèse des matrices (2002). SPINS : Security protocols for sensor networks.
de consensus permettant d’achever celui-ci en un temps fini Wireless Networks, 8, 521–534.
correspondant au diamètre du graphe. Dans les travaux Shannon, C. (1949). Communication theory of secrecy
futurs nous nous intéresserons à l’impact du bruit et de la systems. Bell Sys. Tech. J., 28, 656–715.
perte des paquets dans les communications entre capteurs. Sundaram, S. et Hadjicostis, C. (2007). Finite-time distri-
Il est à noter que dans le cas d’une communication via un buted consensus in graphs with time-invariant topolo-
canal additif blanc gaussien, nous avons montrer dans Ki- gies. In Proc. of American Control Conference (ACC).
bangou (2011) que l’algorithme du consensus en temps fini New York City, USA.
pouvait être utilisé comme étant le noyau d’une approche Sundaram, S. et Hadjicostis, C. (2008). Distributed func-
de type monte-carlo. tion calculation and consensus using linear iterative
strategies. IEEE Journal on Selected Areas in Com-
munications, 26(4), 650–660.
RÉFÉRENCES Xiao, L. et Boyd, S. (2004). Fast linear iterations for
distributed averaging. Systems Control Lett., 53, 65–78.
Blondel, V., Hendrickx, J., Olshevsky, A., et Tsitsiklis, Zhou, Y. et Fang, Y. (2007). Scalable and deterministic
J. (2005). Convergence in multiagent coordination, key agreement scheme for large scale networks. IEEE
consensus, and flocking. In Proc. of the joint 44th IEEE Trans. Wireless Communications, 6(11).
Conf. on Decision and Control (CDC) and European Zhou, Y., Fang, Y., et Zhang, Y. (2008). Securing wireless
Control Conf (ECC), 2996–3000. Seville, Spain. sensor networks : a survey. IEEE Communications
Bose, R. et Mesner, D. (1959). On linear associative Surveys, 10(3), 6–28.
algebras corresponding to association schemes of par-
tially balanced designs. The Annals of Mathematical
Statistics, 30, 21–38.
Brouwer, A., Cohen, A., et Neumaier, A. (1989). Distance-
regular graphs. Springer.