Les mesures de centralit dans les rseaux de capteurs sans fils : Origines et Applications.

EL HAJJI Fouad
Laboratoire L@M
Facult des Sciences et Techniques (FST) BP 146 Mohammadia 20650 Maroc
Email: elhajji.fouad88@gmail.com

LEGHRIS Charekaoui
Laboratoire L@M
Facult des Sciences et Techniques (FST) BP 146 Mohammadia 20650 Maroc
Email: cleghris@yahoo.fr

DOUZI Khadija
Laboratoire L@M
Facult des Sciences et Techniques (FST) BP 146 Mohammadia 20650 Maroc
Email: kdouzi@yahoo.fr

Rsum Depuis la naissance des rseaux de capteurs sans fil, les chercheurs ont centr leurs efforts sur lexploitation des possibilits infinies que cette nouvelle technologie peut offrir. Ces micro nuds- capteurs, dont les capacits ont mont en flche au cours des dernires annes surtout avec les progrs technologiques, ont permis de dvelopper une large gamme d'applications, que pas si longtemps semblaient impossibles, impraticable et ncessitaient beaucoup de ressources. Ceci revient notamment la contribution de diffrents domaines de recherches, micro-lectronique, informatique, tlcommunication, etc. Cette avance technologique des rseaux de capteurs a donn un nouveau souffle de recherche dans le domaine et a permis d'largir son champ dapplication. En effet, et titre dexemple, les rseaux sociaux sont considrs comme lun des domaines pouvant influencer la faon dont nous percevons les nuds-capteurs et leur organisation eu sein du rseau.

suivi des courants sous-marins, la dtection des phnomnes souterrains pour la prvention en cas de susceptibles tremblements de terre, etc. Pour notre vie quotidienne, les deux domaines, o les rseaux de capteurs sans fils jouent un rle crucial et montrent leur efficacit, restent la surveillance du trafic et la sant. Pour la surveillance du trafic, les informations recueillies par les WSNs peuvent tre utilises pour soulager les problmes de circulation que de nombreuses villes semblent tre confrontes dans nos jours. Ceci passe par la prvention des embouteillages et la mise disposition, en conjonction avec les appareils GPS, d'autres routes alternatives. Dans le domaine de sant, les rseaux de capteurs peuvent tre utiliss pour surveiller les patients et aider les personnes handicapes, soit dans les hpitaux ou mme dans leurs propres maisons. Les caractristiques des rseaux de capteurs sans fils englobent beaucoup de paramtres qui incluent la puissance limite, la sensibilit aux dfaillances de nuds, la mobilit des nuds, le dploiement grande chelle et la topologie dynamique du rseau [7]. En fonction de la demande relle et les besoins pour lesquels un rseau de capteurs est mis en uvre, l'administrateur du rseau doit valuer limpact que chacune des caractristiques aura sur les autres. Le domaine des WSNs prsentent normment de dfis pour la recherche scientifiques. Ainsi, les travaux actuels abordent, mais ne sy limitent pas, les domaines suivants : Le contrle de la topologie qui se rfre au concept d'essayer de maintenir la connectivit du rseau dans certaines circonstances. Un exemple serait d'ajuster la puissance d'mission des nuds afin de prserver leur nergie. La mise en cache cooprative, en tant que domaine de recherche, a t souleve comme un moyen de faire face aux exigences de QoS au niveau applications. Comme le cot de la communication est presque trois fois plus que le cot de traitement, le dfi est de rduire la communication autant que possible par le partage de donnes entre les capteurs, la coordination et l'exploitation de l'espace de mmoire cache globale des capteurs cooprants ;

Dans cet article, nous prsentons un aperu de la contribution de l'analyse des rseaux sociaux dans le dveloppement des rseaux de capteurs en termes de thories, algorithmes et applications. Cette analyse se base sur la notion de la mesure de centralit dun nud et son impact sur le reste des nuds dun rseau de capteurs sans fils.
Mots-cls Rseau de capteurs sans fil; Rseaux sociaux; Centralit; Topologie; Graphe; Protocoles

I.

INTRODUCTION

Dans le monde des rseaux informatiques et les tlcommunications, les rseaux de capteurs sans fil ou WSN (Wireless Sensors Networks) prsentent un domaine actif de recherche. Ces rseaux sont constitus essentiellement dautonomes micro-dispositifs distribues spatialement, savoir les nuds-capteurs, qui peuvent tre programms pour surveiller une large gamme de phnomnes physiques, chimiques et environnementales, comme la temprature, les vibrations, les sons et la localisation des objets [7]. En effet, dans plusieurs domaines, industriels en particulier, les rseaux de capteurs semblent avoir eu un grand impact. On peut citer titre dexemple la surveillance des habitats, la prvention contre les incendies, l'observation de groupes d'animaux, le

Dans les rseaux vhiculaires, les WSN sont utiliss pour combiner entre les vhicules, utiliss comme des nuds-capteurs, et les technologies de rseau local sans fil afin d'viter ou prvenir les accidents possibles, alerter sur les embouteillages ou informer sur les places disponibles de stationnement dans un parking auto par exemple ;

Rcemment, le domaine des rseaux sociaux commence concentrer le plus dintrt au sein de la communaut scientifique grce ses similitudes avec les rseaux de capteur sans fils. Dans ce domaine, les structures sociales se composent des nuds, qui sont gnralement reprsentes par des individus ou organisations quant aux liens entre ces nuds, ils sont reprsents par les relations qui existent entre ces entits [1]. Cest grce cette analogie, les rseaux de capteurs et les rseaux sociaux peuvent collaborer ensemble. Par exemple, les rseaux de capteurs peuvent tre utiliss pour dtecter et fournir des informations qui servent personnaliser les services et les applications sociales. De leur cot, l'analyse des rseaux sociaux peut fournir des algorithmes et des techniques qui peuvent conduire des conomies d'nergie et un stockage efficace dans les rseaux de capteurs en fonction des exigences de l'application en cours d'excution. Dans cet article, nous examinons la contribution de l'analyse des rseaux sociaux dans les rseaux de capteurs, en termes d'algorithmes et applications, plus particulirement lapport de la notion de centralit dans ce domaine. Cet article est organis comme suit : Nous abordons, dans la section 2, les similitudes et lanalogie entre les rseaux sociaux et les rseaux de capteurs sans fils ainsi que lintroduction du concept danalyse base des graphes et la centralit. Dans la section 3, nous allons prsenter quelques aspects de calcul de centralit les plus utiliss dans lanalyse des rseaux, tels que ceux provenant du domaine de rseaux sociaux et ceux dvelopps dans le cadre des tudes des rseaux de capteurs. La section 4 sera consacre la prsentation de quelques exemples dutilisation de la centralit ainsi que les critiques qui influent le choix dune centralit en fonction des besoins de la conception de protocoles dans les rseaux de capteurs. Ensuite nous proposons, dans la section 5, une tude comparative entre quelques mthodes de calcul de centralit avec des rsultats numriques pour montrer les diffrences entre ces mthodes et justifier le choix en fonction des besoins. On termine par une conclusion qui dresse un bilan des volutions futures dans ce domaine ainsi que nos perspectives. II. LANALYSE DES RESEAUX ET LES MESURES DE
CENTRALITE

Le concept de degr de centralit provient de rseaux sociaux. Cest dans le cadre des travaux de recherche dans ce domaine quon a constat que certaines entits (personnes, livres, sites .) jouent un rle plus important que dautres et peuvent influer sur lensemble des lments constituants un rseau. Afin dvaluer cette notion dimportance, les chercheurs ont propos une suite de mesures, bases sur la modlisation en graphe, nomme mesures de centralit. La diversit des mesures de centralit revient au fait que limportance dun nud dpend dautres paramtres tels que la connectivit et lorientation dans le graphe ainsi que la nature de mesure (locale ou globale) de tout le rseau. Les travaux de Linton Freeman [10] reprsentent sans doute lune des plus importantes contributions dans lanalyse des rseaux sociaux et les rseaux en gnral. Freeman propose trois mesures de centralit : La centralit de degr, qui repose sur le principe que limportance dun nud dpendra du nombre des nuds auxquels il est connect (en interaction, prsence dune liaison) ; La centralit de proximit, qui est base sur lhypothse quun nud est plus important tant quil est plus proche aux autres nuds dans le rseau ; La centralit dintermdiarit, qui est fonde sur lide que limportance dun nud dpendra de la quantit des changes, entre les autres nuds de rseau, et qui transitent par ce nud ; Dautres mesures de centralit, telles que la centralit spectrale et la centralit de Bridging, qui sinspirent des travaux de Freeman, ont t dveloppes par dautres chercheurs. Si on revient sur lanalogie des rseaux capteurs sans fil et les rseaux sociaux, les chercheurs ont constat des similitudes et points communs, du point de vue modlisation en graphes [1], tels que : Distribution des degrs en loi de puissance : dans les graphes des rseaux sociaux (e.g graphes des documents) et les graphes des WSNs, la distribution des degrs des nuds suit une loi de puissance. Ceci est traduit par le fait quun ensemble de nuds (limits en nombre) ont un fort degr et jouent un rle plus important que le reste des nuds, qui possdent ainsi un degr faible. Il savre judicieux de reprer donc ces nuds qui occupe une place stratgique et ont une grande importance ; Fort coefficient de regroupement : le coefficient de regroupement exprime la probabilit que les voisins dun nud soient eux-mmes lis par un lien (relation, interaction) et ainsi, le coefficient de regroupement global du graphe est gal la moyenne des coefficients de tous les nuds. Les graphes des rseaux sociaux et WSNs sont caractriss par un fort coefficient. Ceci est traduit par le fait que malgr que ces graphes aient une faible densit, on peut dtecter la prsence dun regroupement des nuds dans des sous-groupes (commuts, cluster) ; Ces similitudes ont pouss les chercheurs des WSNs sinspirer des travaux de leurs collgues dans les rseaux sociaux, chose qui a rvolutionn la faon avec laquelle les

WSNs sont traits et a ouvert de nouveaux horizons dans les domaines de routage, prvision de pannes, contrle de topologies, les problmes daccs au support, la scurit des changes, etc [5]. Nanmoins, il a fallu noter que lapplication de ces mesures, inspires des rseaux sociaux, nchappe pas quelques limites dues au fait que ces mesures ne prennent pas en considration les questions dnergie, la robustesse du rseau, la qualit des services, lvolution et le changement de topologie, etc. Ceci a permis la recherche et le dveloppement de nouvelles mesures qui prennent en considration ces points telles que la centralit QoB (Quality of Backup), la centralit APC (Alternative Path Centrality), la centralit de clustiring, etc. III. LES CENTRALITES DANS LES RESEAUX DE CAPTEURS
SANS FILS

B. Centralit de proximit La centralit de proximit selon Freeman [1][10] est une mesure de centralit base sur lide quun nud occupe une position plus stratgique tant quil est proche des autres sommets (nuds) de ce graphe. En pratique, la centralit de proximit dun nud est obtenue en calculant sa distance moyenne vis--vis des autres nuds du graphe. Soit G = (V, E) un graphe dordre N reprsent par sa matrice dadjacence A. La centralit de proximit dun nud vi V est dfinie par :

Cpro(vi) =

1
( , ) =1

o dist(vi,vj) est la distance entre les deux sommets vi et vj. C. Centralit dintermdiarit (betweenness centrality) La centralit dintermdiarit est une autre mesure qui prend en considration la topologie globale du rseau. Lide derrire cette mesure est quun nud est dautant plus important quil soit ncessaire, pour acheminer les informations entre les dfrents nuds, de le traverser. Plus prcisment, un nud ayant une forte centralit dintermdiarit est un nud par lequel passe un grand nombre de chemins godsiques (i.e. chemins les plus courts). Soit G = (V, E) un graphe (orient ou non) dordre N. La centralit dintermdiarit dun nud vi V est dfinie par :

Il sagit l de survoler les mesures de centralit les plus importantes dans le domaine des rseaux de capteurs. Ces mesures peuvent tre divises en catgories selon plusieurs critres. Par rapport au critre de la nature par exemple, les mesures peuvent tre divises en deux catgories : locales et globales. Les premires sont caractrises, de point de vue topologique, par le fait quelles se basent sur des mthodes, qui prennent en considration la relation du nud avec ses voisins et comment il est proche par rapport au reste des nuds. On peut citer, dans ce cadre, la centralit de degr et la centralit de proximit. La deuxime catgorie se focalise sur ltude du rle du nud, par rapport la globalit du rseau et dans lchange de donnes ainsi que la circulation des flux. Les centralits de bridging et dintermdiarit font partie e cette deuxime catgorie. Cest ainsi quon peut catgorise les mesures de centralit, que a soient celles dont lorigine est lanalyse des rseaux sociaux (centralits de Freeman), avec leurs limitations, ou celles inspires et qui ont t dveloppes pour rpondre aux exigences des rseaux de capteurs sans fils, telles que la centralit de clustering, QOB, APC et L-CRC (LengthConstrained connectivity and Rerouting centrality). A. Centralit de degr Selon Freeman [1][10] cette mesure dtermine limportance dun nud dans un graphe en calculant le nombre de ses sommets voisins. En thorie des graphes, ce nombre est appel degr du nud, do lappellation de centralit de degr. Soit G = (V, E) un graphe dordre N reprsent par sa matrice dadjacence A. La centralit de degr dun nud vi V est dfinie par :

Cint(vi) =

=1

( ) =1

o gjk(vi) est le nombre total de chemins godsiques entre les nuds vj et vk qui passent par le nud vi, et gjk est le nombre total de chemins godsiques entre les nuds vj et vk. D. Centralit spectrale Lapproche propose par Bonacich [1] pour le calcul de centralit dans un graphe est trs diffrente desautres approches annonces par Freeman. Il a propos lide que la centralit dun nud soit calcule par la centralit des nuds auxquels il est connect. Pour la mise en uvre de ce principe, Bonacich propose de considrer la centralit dun nud comme tant dpendante de la combinaison linaire des centralits de ses nuds voisins. Soit G = (V, E) un graphe dordre N reprsent par sa matrice dadjacence A. La centralit spectrale Cspe(vi) dun nud vi V est donne par lquation :

Cspe(vi) = a1iCspe(v1) + a2iCspe(v2) ++ aniCspe(vn)

o est un rel strictement positif. Le calcul de la centralit spectrale dun noeud dans un graphe ncessite donc de rsoudre un systme dquations qui peut tre reprsent en termes de matrices de la manire suivante : Cspe = MCspe o est un rel strictement positif, Cspe est le vecteur de centralit spectrale ; M correspond la matrice dadjacence.

Cdeg(vi) =

1 1

=1

La centralit de degr est aussi appele mesure de centralit locale car elle ne prend pas en compte la hirarchie et la structure globale du graphe et nest calcule qu partir du voisinage immdiat dun sommet.

E. Centralit de Bridging (de transition) La centralit de transition (Bridging) [9] identifie les nuds qui jouent le rle de liaison entre les rgions fortement lies. Par exemple, un nud de liaison entre des zones de densit importante. La centralit de bridging d'un nud est le produit de la centralit dintermdiarit (betweenness centrality) BC et le bridging coefficient (CB), qui mesure respectivement les caractristiques globales et locales d'un nud. Exactement, la centralit de transition CR (v) pour le nud v est dfini par: CR(v) = BC(v) x CB(v) Le coefficient de bridging d'un nud v est dfini par:
1
1 i N v

de connexion et reroutage sous contrainte de la longueur de chemin (L-CRC). La centralit L-CRC mesure l'importance d'un nud v en fonction de l'impact de sa suppression, ce qui affecte la connectivit du rseau et la longueur des plus courts chemins, qui passent par v, entre les autres nuds et le Sink (nud passerelle). L-CRC est un indice qui se compose d'une paire de valeurs de centralit: La centralit de connectivit sous contraint de la longueur de chemin (l-CC) et La centralit de reroutage sous contraint de la longueur de chemin (l-RC). Nous dfinissons l-CRC d'un nud v comme : l-CRC (v) = <l-CC(v), l-RC(v)> i. La centralit de connectivit sous contrainte de la longueur de chemin (l-CC)

BC (v) =

o d (v) est le degr du noeud v, et

N(v) est l'ensemble des voisins du nud v.

F. Quality of Backup (QoB) and Alternative Path Centrality (APC) L'utilisation de la centralit dans lanalyse de la robustesse du rseau a t dj propose dans la littrature. Shavitt et Singer [11] prsentent deux nouveaux mesures de centralit fondes sur l'existence d'un chemin secondaire (alternatif ou de sauvegarde) si un nud tombe en panne, savoir la qualit de Sauvegarde (QOB) et la centralit de chemin alternatif (APC). L'ide derrire ces deux centralits est tel que la dfaillance de nuds avec des parfaites chemins secondaires n'affecte pas ni la connectivit ni augmenter la longueur des chemins dans le rseau. QOB est une mesure du chemin de redirection entre les parents directs du nud et ses fils directs. La QOB d'un nud v est : (v) =
1 max { , 1, 1}

La centralit de la connectivit sous contrainte de la longueur de chemin d'un nud v [6] est le nombre des descendants de v qui seraient repouss au del de la limite lmax des pas entre chaque nud et le SINK lorsque v est retir du rseau. Nous dfinissons l-CC (v), la centralit de la connectivit sous contrainte de la longueur de chemin d'un nud v comme
l-CC (v) = |{w D(v) d(w, SINK) lmax , dv(w, SINK)> Imax}|

o D(v) est l'ensemble des descendants de v dans l'arbre de routage, d(w, SINK) est la longueur du chemin entre w et le Sink qui ne passe pas par v et dv(w, SINK) est la longueur du chemin entre w et le Sink passant par v. ii. La centralit de reroutage sous contraint de la longueur de chemin (l-RC)

| |.| |

o V est lensemble des parents directs de v et CV est lensemble d'enfants directs de v. (v) = 1 si v a d es parfaites chemins de redirection et (v) = 0 sil ne la pas. APC est la diffrence entre la centralit topologique des nuds, avant et aprs la dfaillance dun nud. La centralit topologique d'un nud u V, not (u), dpend du nombre de nuds connects u et de leurs distances de u.

La centralit de reroutage sous contraint de la longueur de chemin d'un nud v [6] est le nombre des routes (trajets) entre les descendants de v et le nud-passerelle (SINK) que leurs longueurs dpasseront la longueur limite lmax, aprs l'enlvement de v. Notez que nous ne prenons en considration que les descendants de v qui seront encore reli l'arbre de routage aprs la suppression de v. Nous dfinissons l-RC (v), La centralit de reroutage sous contraint de la longueur de chemin d'un nud v comme :

(u) =

\{ } , . Par consquent,

l-RC(v) = wD(v)(

Max {d v (w,SINK ),l max } max {d(w,SINK ),l max }

-1); dv(w,Sink)

0 (u) | V | -1; u V. La valeur de l'APC d'un noeud v est dfinie par :

IV.
\{ }

APPLICATIONS DE LA CENTRALITE DANS LES WSNS

(v)=

\{ }

u -

v u

o v indique que les valeurs de la centralit sont calcule en utilisant des chemins de redirection qui passe par v. G. L-CRC (Length-Constrained Connectivity and Rerouting Centrality) L. Sitanayah [6] a propos une nouvelle variante de la centralit de bridging pour WSN, quil la nomm la centralit

Grace la souplesse et la facilit du dploiement des algorithmes de calcul de centralits, ces derniers ont pris plus de places dans les travaux de recherches dans les rseaux de capteurs sans fil. La nature des rseaux de capteurs et la manire de leur dploiement imposent, dans la plupart des cas, lutilisation de la communication multi-sauts pour atteindre le Sink. Nanmoins, lemploi de ce genre de communication implique

des risques aussi, comme par exemple la charge plus leve, des nuds les plus proches du sink, dans la transmission des paquets par rapport aux autres nuds. D'autre part, lorsque les nuds utilisent la communication simple saut (unique) pour atteindre le Sink, les nuds situs plus loin ont une consommation plus leve de l'nergie cause de la longue distance entre ces nuds et le Sink. Pour surmonter ces problmes les nuds-capteurs peuvent tre organiss en clusters o, dans chaque cluster, un maitre de cluster (cluster head) est responsable de la communication avec le Sink ainsi qu'avec les nuds membres [7]. Cependant, dans la plupart des rseaux de capteurs, les nuds sont statiques. Par consquent, les nuds proches du cluster-head subirent une surcharge en permanence. Un autre problme de clustering consiste choisir le cluster-head et implmenter un mcanisme qui permet llection chacun des nuds membres comme cluster-head tour de rle afin dviter lpuisement des batteries de quelques nuds aussitt que les autres. Pour rpondre ces problmes de clustering, plusieurs mtriques ont t employes telles que la centralit de degr, proximit, spectrale et dintermdiarit [2][7]. Dans les rseaux de capteurs sans fil, les Sink doivent tre placs judicieusement. Dans le cas des Sink mobiles, le dploiement, la direction et la dlocalisation devraient tre choisis de faon optimale afin qu'ils puissent amliorer la QoS. L aussi, il est propos que les mesures de centralit telles que la centralit dintermdiarit peuvent tre utilise pour dterminer lemplacement optimal, la direction et la dlocalisation [3]. Les rseaux de capteurs sans fil sont employs dans diverses applications. Parfois, les nuds sont tenus transmettre priodiquement ou sur la dtection dun vnement (changement de mesures), des informations de dbit faible comme la temprature, lhumidit, la pression, etc. Cette transmission peut tre retarde avec un dlai qui peut tre accept ou non. D'autre part, certaines applications ncessitent un dbut de transmission des donnes plus lev mais avec un dlai de retard intolrant comme la vido en direct de la zone surveille par les capteurs en cas de dtection de cibles, des prises instantans par le capteur-camra ou bien la transmission des informations audio. Un routage multi-sauts avec un dbit optimis est gnralement prfr dans de tels cas. Par consquent, des mesures de centralit, qui pourraient aider quilibrer la charge et accrotre l'efficacit nergtique, comme la centralit dintermdiarit de flux dans le rseau pourraient tre un bon choix [7]. Dans certains cas, la couverture prsente un enjeu primordial pour rpondre aux exigences de l'application, peu importe combien de capteurs sont dploys. En outre, dans de nombreux cas, des capteurs doivent tre placs l'intrieur d'un btiment ou une zone sans courir de risques (par exemple dans le cas dun accident de voiture). Dans un tels cas, il est ncessaire de faire usage de capteurs mobiles, qui peuvent se dplacer vers les bons endroits pour fournir une bonne couverture de la zone surveille. L encore, les mesures de centralit comme la centralit de degr, proximit, spectrale ou toute mesure de centralit combinatoire pourraient tre utilises pour amliorer la couverture dans les rseaux de capteurs sans fil [7].

En plus des domaines dapplication dj cits, dautres recherches ont abord lutilisation de la centralit dans lamlioration de lefficacit nergtique et la dure de vie du rseau. Parmi ces travaux, on peut mentionner le modle propos par Parth H.Pathak et Rudra Dutta [8], qui visent rsoudre le problme de surcharge dans les rseaux qui affecte certain nuds et implique une surconsommation dnergie, chose qui peut engendre la dconnexion de tout le rseau cause la dconnexion de ces nuds puiss. Pour rsoudre ce problme, Pathak and Dutta ont dvelopp un modle bas sur la dtection des nuds qui subirent une surcharge grce la centralit dintermdiarit. Dautres travaux mettent le point sur les caractristiques et les risques topologiques, telles que ceux de Shavitt et Singer [11], qui sont bass sur les mesures de centralit QOB et APC. De sa part, L.Sitanayah [6] a bti ses travaux de recherche sur la centralit L-CRC. Le but de ces travaux est lanalyse de la robustesse du rseau et limpact de la suppression dun nud (risque de panne ou dconnexion) sur la connectivit au sein du rseau. Junqi Duan et ses collgues [4] ont concentr leurs efforts sur le dveloppement dun nouveau mcanisme de contrle daccs bas sur lide d'utiliser la centralit de degr pour valuer les risques tenir en compte lors de l'adoption des systmes distribus, chose qui a permet aussi de rendre les politiques de scurit raisonnables, rduire les risques et rpondre un certain niveau de protection. V. COMPARAISON ET RESULTATS NUMERIQUES

Pour concrtiser ce que nous venons de dire, on abordera dans cette section une tude de cas dun rseau de capteurs sans fil o on va calculer quelques mesures de centralit et on termine par une discussion des rsultats obtenus. La Figure 1 illustre lexemple d'un petit rseau qui se compose de 12 nuds-capteurs et un Sink (nud-passerelle) avec lmax = 5 (nombre de pas maximum). On note que dans cette topologie, d (L, Sink)> lmax (distance entre le nud L et le Sink). Les lignes continues sont les chemins de routage depuis les nuds jusquau Sink tandis que les lignes pointilles indiquent les liaisons de communication directes entre les nuds. Dans cet exemple, le nud B a la plupart des descendants et le nud D a le plus de voisins.

Fig. 1. Un rseau qui se compose de 12 nuds-capteurs et un Sink

Dans le but dexpliquer la diffrence entre la varit des mesures de centralit, on va prendre lexemple de quatre de ces mesures : la centralit de proximit, la centralit

dintermdiarit, le coefficient de clustiring et la L-CRC. Ce choix nest pas arbitraire mais il va nous permettre dexaminer des exemples des diffrents types de mesure de centralit tels que les mesures locales (centralit de proximit et coefficient de clustiring), les mesures globales (centralit dintermdiarit) et les mesures dveloppes pour les WSNs (L-CRC). Le tableau 1 prsente les valeurs des quatre mesures pour chaque nud du rseau. Le calcul de la centralit de proximit et du coefficient de clustering a t ralis par des mthodes bases sur lalgorithme de Dijkstra, tandis que la centralit dintermdiarit a t calcule avec un autre algorithme, appel algorithme de Brandes, jug plus rapide que celui de Dijkstra, mme dans le cas de grands rseaux et dimportante densit. Les valeurs de la centralit L-CRC ont t issues des travaux de L.Sitanayah afin dexaminer lutilit des variantes de la centralit dveloppes exclusivement pour les WSNs [6].
TABLE I. nuds Sink A B C D E F G H I J K L
a. b. c. d.

long que lmax entre au moins lun de leurs descendants et le Sink. Ces rsultats montrent clairement que chaque centralit a ces propres caractristiques et son propre domaine dapplication, ce qui ncessite un choix judicieux de la dfinition de la centralit utiliser, base sur la nature du rseau et les buts souhaits de lutilisation de cette notion. VI. CONCLUSION

Les applications de rseaux de capteurs sont pratiquement illimites. Par consquent, le besoin en matire de nouveaux protocoles et algorithmes a connu une importante affluence. Ces algorithmes permettent un stockage de donnes plus efficace, une conomie de lnergie, une rduction du taux des messages changs et une livraison garantie des messages. Les diverses mesures de centralit abords dans ce document peuvent rpondre ces besoins. Plusieurs recherches ont dj t menes sur lapplication des mesures de centralit dans les rseaux de capteurs, mais il reste encore normment daxes parcourir dans ce domaine en futur. L'utilisation d'autres variantes de centralits doit tre explore afin que des solutions globale et plus rentables soient dveloppes et rpondent aux exigences des applications du monde rel. Parmi ces domaines de recherche, on trouve la couverture sous contraintes, le routage sous contrainte dnergie et le routage dans les rseaux htrognes REFERENCES
N. F. CHIKHI, Calcul de centralit et identification de structures de communauts dans les graphes de documents, Thse, Institut de Recherche en Informatique de Toulouse (IRIT), 2012. [2] C. Chaudet, N. Costagliola, I. Demeure, S. Ktari, S. Tardieu, Slection des brokers dans un reseau de capteurs en mode publication / souscription, "14mes Rencontres Francophones sur les Aspects Algorithmiques des Tlcommunications (AlgoTel), La Grande Motte, France 2012. [3] Li, Xiao-Hui, and Zhi-Hong Guan. "Energy-Aware Routing in Wireless Sensor Networks Using Local Betweenness Centrality." International Journal of Distributed Sensor Networks 2013 (2013). [4] J. Duan et al., TC-BAC: A trust and centrality degree based access control model in wireless sensor networks, Ad Hoc Networks (2013). [5] Aarti Jain and B.V.R. Reddy, Node Centrality in Wireless Sensor Networks: Importance, Applications and Advances, 3rd IEEE International Advance Computing Conference (IACC), Ghaziabad, India 2013. [6] L. Sitanayah, K. N. Brown, and C. J. Sreenan, Fault -Tolerant RelayDeployment Based on Length-Constrained Connectivity and Rerouting Centrality in Wireless Sensor Networks, Wireless Sensor Networks. Springer Berlin Heidelberg, pp. 115130, 2012. [7] Ian F. Akyildiz and Mehmet Can Vuran, Wireless Sensor Networks, Edition WILEY, 2010. [8] Parth H. Pathak and Rudra Dutta, Centrality-based power control for hot-spot mitigation in multi-hop wireless networks, Computer Communications 35, pp. 10741085, 2012. [9] W. Hwang et al., Bridging Centrality: Identifying Bridging Nodes In Scale free Networks, KDD06, pp 20 23, Philadelphia, USA, 2006. [10] Freeman, L.C. Freeman, Centrality in social networks: conceptual Clarification, Social Networks, 215239, 1978. [11] Yuval Shavitt and Yaron Singer, Beyond Centrality - Classifying Topological Significance using Backup Efficiency and Alternative Paths, IFIP NETWORKING 2007, Atlanta, Georgia, USA, 2007. [1]

RESULTATS DE QUELQUES MESURES DE CENTRALITE APPLIQUEES SUR LE RESEAU DE LA FIGURE1 C.P b 0.0278 0.0333 0.0345 0.0333 0.0417 0.0385 0.0313 0.0385 0.0333 0.0333 0.0303 0.0303 0.0227 C.C c 0.1250 0.3750 0.2500 0.2308 0.1250 0.1667 0 0 0 0 0 0 0 L-CRC d 0 0 0 0 0 (0.181 , 0.25) 0 (0.0909 , 0.0556) (0.0909 , 0.1667) 0 0 0 0

C.I a 0.043 0.0583 0.093 0.11 0.483 0.3116 0.0516 0.396 0.201 0.278 0.141 0.3 0

C.I : Centralit dintermdiarit C.P : Centralit de proximit C.C: Coefficient de clustiring L-CRC : Length-Constrained Connectivity and Rerouting Centrality

Daprs les rsultats, on remarque que lutilisation de la centralit dintermdiarit montre que les nuds les plus centraux sont respectivement B, D et E. Ceci revient au fait que la plupart des plus courts chemins, entre les nuds et le Sink, passent par ces nuds. Par contre, la centralit de proximit montre que le nud central dans le rseau est D car il a le plus grand nombre des voisins. Dautre part, le coefficient de clust ring indique que les nuds A et B ont une forte probabilit de crer des clusters autour deux. Ceci sexplique par le fait que la plupart des voisins de A et B sont lies entre eux par des liaisons directes. Les nuds E, H et G ont une centralit LCRC gale < 0,1818 ; 0,25>, <0,0909 ; 0,1667> et <0,0909 ; 0,0556> respectivement. Ceci traduit le risque davoir au moins un chemin alternatif, en cas de leur dfaillance, plus