1

Les mesures de centralité dans les réseaux 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

DOUZI Khadija

Laboratoire L@M Faculté des Sciences et Techniques (FST)

BP 146 Mohammadia 20650 Maroc

Email: kdouzi@yahoo.fr

Résumé— Depuis la naissance des réseaux de capteurs

sans fil, les chercheurs ont centré leurs efforts sur

l’exploitation des possibilités infinies que cette nouvelle

technologie peut offrir. Ces micro nœuds- capteurs, dont

les capacités ont monté en flèche au cours des dernières

années surtout avec les progrès technologiques, ont permis

de développer une large gamme d'applications, que pas si

longtemps semblaient impossibles, impraticable et

nécessitaient beaucoup de ressources. Ceci revient

notamment à la contribution de différents domaines de

recherches, micro-électronique, informatique,

télécommunication, etc. Cette avancée technologique des

réseaux de capteurs a donné un nouveau souffle de

recherche dans le domaine et a permis d'élargir son

champ d’application. En effet, et à titre d’exemple, les

réseaux sociaux sont considérés comme l’un des domaines

pouvant influencer la façon dont nous percevons les

nœuds-capteurs et leur organisation eu sein du réseau.

Dans cet article, nous présentons un aperçu de la

contribution de l'analyse des réseaux sociaux dans le

développement des réseaux de capteurs en termes de

théories, algorithmes et applications. Cette analyse se base

sur la notion de la mesure de centralité d’un nœud et son

impact sur le reste des nœuds d’un réseau de capteurs sans

fils.

Mots-clés— Réseau de capteurs sans fil; Réseaux sociaux;

Centralité; Topologie; Graphe; Protocoles

I. INTRODUCTION

Dans le monde des réseaux informatiques et les télécommunications, les réseaux de capteurs sans fil ou WSN (Wireless Sensors Networks) présentent un domaine actif de recherche. Ces réseaux sont constitués essentiellement d’autonomes micro-dispositifs distribuées spatialement, à savoir les nœuds-capteurs, qui peuvent être programmés pour surveiller une large gamme de phénomènes physiques, chimiques et environnementales, comme la température, les vibrations, les sons et la localisation des objets [7]. En effet, dans plusieurs domaines, industriels en particulier, les réseaux de capteurs semblent avoir eu un grand impact. On peut citer à titre d’exemple la surveillance des habitats, la prévention contre les incendies, l'observation de groupes d'animaux, le

suivi des courants sous-marins, la détection des phénomènes souterrains pour la prévention en cas de susceptibles tremblements de terre, etc.

Pour notre vie quotidienne, les deux domaines, où les réseaux de capteurs sans fils jouent un rôle 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 utilisées pour soulager les problèmes de circulation que de nombreuses villes semblent être confrontées dans nos jours. Ceci passe par la prévention des embouteillages et la mise à disposition, en conjonction avec les appareils GPS, d'autres routes alternatives. Dans le domaine de santé, les réseaux de capteurs peuvent être utilisés pour surveiller les patients et aider les personnes handicapées, soit dans les hôpitaux ou même dans leurs propres maisons.

Les caractéristiques des réseaux de capteurs sans fils englobent beaucoup de paramètres qui incluent la puissance limitée, la sensibilité aux défaillances de nœuds, la mobilité des nœuds, le déploiement à grande échelle et la topologie dynamique du réseau [7]. En fonction de la demande réelle et les besoins pour lesquels un réseau de capteurs est mis en œuvre, l'administrateur du réseau doit évaluer l’impact que chacune des caractéristiques aura sur les autres.

Le domaine des WSNs présentent énormément de défis pour la recherche scientifiques. Ainsi, les travaux actuels abordent, mais ne s’y limitent pas, les domaines suivants :

Le contrôle de la topologie qui se réfère au concept d'essayer de maintenir la connectivité du réseau dans certaines circonstances. Un exemple serait d'ajuster la puissance d'émission des nœuds afin de préserver leur énergie.

La mise en cache coopérative, en tant que domaine de recherche, a été soulevée comme un moyen de faire face aux exigences de QoS au niveau applications. Comme le coût de la communication est presque trois fois plus que le coût de traitement, le défi est de réduire la communication autant que possible par le partage de données entre les capteurs, la coordination et l'exploitation de l'espace de mémoire cache globale des capteurs coopérants ;

LEGHRIS Charekaoui

Laboratoire L@M Faculté des Sciences et Techniques (FST)

BP 146 Mohammadia 20650 Maroc Email: cleghris@yahoo.fr

2

Dans les réseaux véhiculaires, les WSN sont utilisés pour combiner entre les véhicules, utilisés comme des nœuds-capteurs, et les technologies de réseau local sans fil afin d'éviter ou prévenir les accidents possibles, alerter sur les embouteillages ou informer sur les places disponibles de stationnement dans un parking auto par exemple ;

Récemment, le domaine des réseaux sociaux commence à concentrer le plus d’intérêt au sein de la communauté scientifique grâce à ses similitudes avec les réseaux de capteur sans fils. Dans ce domaine, les structures sociales se composent des nœuds, qui sont généralement représentées par des individus ou organisations quant aux liens entre ces nœuds, ils sont représentés par les relations qui existent entre ces entités [1]. C’est grâce à cette analogie, les réseaux de capteurs et les réseaux sociaux peuvent collaborer ensemble. Par exemple, les réseaux de capteurs peuvent être utilisés pour détecter et fournir des informations qui servent à personnaliser les services et les applications sociales. De leur coté, l'analyse des réseaux sociaux peut fournir des algorithmes et des techniques qui peuvent conduire à des économies d'énergie et un stockage efficace dans les réseaux de capteurs en fonction des exigences de l'application en cours d'exécution.

Dans cet article, nous examinons la contribution de l'analyse des réseaux sociaux dans les réseaux de capteurs, en termes d'algorithmes et applications, plus particulièrement l’apport de la notion de centralité dans ce domaine.

Cet article est organisé comme suit :

Nous abordons, dans la section 2, les similitudes et l’analogie entre les réseaux sociaux et les réseaux de capteurs sans fils ainsi que l’introduction du concept d’analyse à base des graphes et la centralité.

Dans la section 3, nous allons présenter quelques aspects de calcul de centralité les plus utilisés dans l’analyse des réseaux, tels que ceux provenant du domaine de réseaux sociaux et ceux développés dans le cadre des études des réseaux de capteurs.

La section 4 sera consacrée à la présentation de quelques exemples d’utilisation de la centralité ainsi que les critiques qui influent le choix d’une centralité en fonction des besoins de la conception de protocoles dans les réseaux de capteurs.

Ensuite nous proposons, dans la section 5, une étude comparative entre quelques méthodes de calcul de centralité avec des résultats numériques pour montrer les différences entre ces méthodes 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. L’ANALYSE DES RESEAUX ET LES MESURES DE

CENTRALITE

Le concept de degré de centralité provient de réseaux sociaux. C’est dans le cadre des travaux de recherche dans ce domaine qu’on a constaté que certaines entités (personnes, livres, sites ….) jouent un rôle plus important que d’autres et peuvent influer sur l’ensemble des éléments constituants un réseau. Afin d’évaluer cette notion d’importance, les chercheurs ont proposé une suite de mesures, basées sur la modélisation en graphe, nommée mesures de centralité.

La diversité des mesures de centralité revient au fait que l’importance d’un nœud dépend d’autres paramètres tels que la connectivité et l’orientation dans le graphe ainsi que la nature de mesure (locale ou globale) de tout le réseau. Les travaux de Linton Freeman [10] représentent sans doute l’une des plus importantes contributions dans l’analyse des réseaux sociaux et les réseaux en général. Freeman propose trois mesures de centralité :

• La centralité de degré, qui repose sur le principe que l’importance d’un nœud dépendra du nombre des nœuds auxquels il est connecté (en interaction, présence d’une liaison) ;

• La centralité de proximité, qui est basée sur l’hypothèse qu’un nœud est plus important tant qu’il est plus proche aux autres nœuds dans le réseau ;

• La centralité d’intermédiarité, qui est fondée sur l’idée que l’importance d’un nœud dépendra de la quantité des échanges, entre les autres nœuds de réseau, et qui transitent par ce nœud ;

D’autres mesures de centralité, telles que la centralité spectrale et la centralité de Bridging, qui s’inspirent des travaux de Freeman, ont été développées par d’autres chercheurs.

Si on revient sur l’analogie des réseaux capteurs sans fil et les réseaux sociaux, les chercheurs ont constaté des similitudes et points communs, du point de vue modélisation en graphes [1], tels que :

• Distribution des degrés en loi de puissance : dans les graphes des réseaux sociaux (e.g graphes des documents) et les graphes des WSNs, la distribution des degrés des nœuds suit une loi de puissance. Ceci est traduit par le fait qu’un ensemble de nœuds (limités en nombre) ont un fort degré et jouent un rôle plus important que le reste des nœuds, qui possèdent ainsi un degré faible. Il s’avère judicieux de repérer donc ces nœuds qui occupe une place stratégique et ont une grande importance ;

• Fort coefficient de regroupement : le coefficient de regroupement exprime la probabilité que les voisins d’un nœud soient eux-mêmes liés par un lien (relation, interaction) et ainsi, le coefficient de regroupement global du graphe est égal à la moyenne des coefficients de tous les nœuds. Les graphes des réseaux sociaux et WSNs sont caractérisés par un fort coefficient. Ceci est traduit par le fait que malgré que ces graphes aient une faible densité, on peut détecter la présence d’un regroupement des nœuds dans des sous-groupes (commutés, cluster) ;

Ces similitudes ont poussé les chercheurs des WSNs à s’inspirer des travaux de leurs collègues dans les réseaux sociaux, chose qui a révolutionné la façon avec laquelle les

3

WSNs sont traités et a ouvert de nouveaux horizons dans les domaines de routage, prévision de pannes, contrôle de topologies, les problèmes d’accès au support, la sécurité des échanges, etc [5].

Néanmoins, il a fallu noter que l’application de ces mesures, inspirées des réseaux sociaux, n’échappe pas à quelques limites dues au fait que ces mesures ne prennent pas en considération les questions d’énergie, la robustesse du réseau, la qualité des services, l’évolution et le changement de topologie, etc. Ceci a permis la recherche et le développement de nouvelles mesures qui prennent en considération 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

Il s’agit là de survoler les mesures de centralité les plus

importantes dans le domaine des réseaux de capteurs. Ces mesures peuvent être divisées en catégories selon plusieurs critères.

Par rapport au critère de la nature par exemple, les mesures peuvent être divisées en deux catégories : locales et globales. Les premières sont caractérisées, de point de vue topologique, par le fait qu’elles se basent sur des méthodes, qui prennent en considération la relation du nœud avec ses voisins et comment il est proche par rapport au reste des nœuds. On peut citer, dans ce cadre, la centralité de degré et la centralité de proximité. La deuxième catégorie se focalise sur l’étude du rôle du nœud, par rapport à la globalité du réseau et dans l’échange de données ainsi que la circulation des flux. Les centralités de bridging et d’intermédiarité font partie e cette deuxième catégorie.

C’est ainsi qu’on peut catégorise les mesures de centralité, que ça soient celles dont l’origine est l’analyse des réseaux sociaux (centralités de Freeman), avec leurs limitations, ou celles inspirées et qui ont été développées pour répondre aux exigences des réseaux de capteurs sans fils, telles que la centralité de clustering, QOB, APC et L-CRC (Length-Constrained connectivity and Rerouting centrality).

A. Centralité de degré

Selon Freeman [1][10] cette mesure détermine l’importance d’un nœud dans un graphe en calculant le nombre de ses sommets voisins. En théorie des graphes, ce nombre est appelé degré du nœud, d’où l’appellation de centralité de degré.

Soit G = (V, E) un graphe d’ordre N représenté par sa matrice d’adjacence A. La centralité de degré d’un nœud vi ∈V est définie par :

Cdeg

(vi) = 1

𝑁−1 𝑎𝑖𝑗

𝑁𝑗=1

La centralité de degré est aussi appelée mesure de centralité locale car elle ne prend pas en compte la hiérarchie et la structure globale du graphe et n’est calculée qu’à partir du voisinage immédiat d’un sommet.

B. Centralité de proximité

La centralité de proximité selon Freeman [1][10] est une mesure de centralité basée sur l’idée qu’un nœud occupe une position plus stratégique tant qu’il est proche des autres sommets (nœuds) de ce graphe. En pratique, la centralité de proximité d’un nœud est obtenue en calculant sa distance moyenne vis-à-vis des autres nœuds du graphe.

Soit G = (V, E) un graphe d’ordre N représenté par sa matrice d’adjacence A. La centralité de proximité d’un nœud vi ∈V est définie par :

Cpro(vi) =

𝑁−1

𝑑𝑖𝑠𝑡 (𝑣𝑖 ,𝑣𝑗 )𝑁𝑗=1

où dist(vi,vj) est la distance entre les deux sommets vi et vj.

C. Centralité d’intermédiarité (betweenness centrality)

La centralité d’intermédiarité est une autre mesure qui prend en considération la topologie globale du réseau. L’idée derrière cette mesure est qu’un nœud est d’autant plus important qu’il soit nécessaire, pour acheminer les informations entre les déférents nœuds, de le traverser. Plus précisément, un nœud ayant une forte centralité d’intermédiarité est un nœud par lequel passe un grand nombre de chemins géodésiques (i.e. chemins les plus courts).

Soit G = (V, E) un graphe (orienté ou non) d’ordre N. La centralité d’intermédiarité d’un nœud vi ∈V est définie par :

Cint

(vi) = 𝑔𝑗𝑘 (𝑣𝑖)

𝑔𝑗𝑘

𝑁𝑘=1

𝑁𝑗=1

où gjk(vi) est le nombre total de chemins géodésiques entre les nœuds vj et vk qui passent par le nœud vi, et gjk est le nombre total de chemins géodésiques entre les nœuds vj et vk.

D. Centralité spectrale

L’approche proposée par Bonacich [1] pour le calcul de centralité dans un graphe est très différente desautres approches annoncées par Freeman. Il a proposé l’idée que la centralité d’un nœud soit calculée par la centralité des nœuds auxquels il est connecté. Pour la mise en œuvre de ce principe, Bonacich propose de considérer la centralité d’un nœud comme étant dépendante de la combinaison linéaire des centralités de ses nœuds voisins.

Soit G = (V, E) un graphe d’ordre N représenté par sa matrice d’adjacence A. La centralité spectrale C

spe(vi) d’un

nœud vi ∈V est donnée par l’équation :

μCspe

(vi) = a1iCspe

(v1) + a2iCspe

(v2) +…+ aniCspe

(vn)

où μ est un réel strictement positif.

Le calcul de la centralité spectrale d’un noeud dans un graphe nécessite donc de résoudre un système d’équations qui peut être représenté en termes de matrices de la manière suivante : μC

spe = MC

spe où μ est un réel strictement positif,

Cspe

est le vecteur de centralité spectrale ; M correspond à la matrice d’adjacence.

4

E. Centralité de Bridging (de transition)

La centralité de transition (Bridging) [9] identifie les nœuds qui jouent le rôle de liaison entre les régions fortement liées. Par exemple, un nœud de liaison entre des zones de densité importante. La centralité de bridging d'un nœud est le produit de la centralité d’intermédiarité (betweenness centrality) BC et le bridging coefficient (CB), qui mesure respectivement les caractéristiques globales et locales d'un nœud. Exactement, la centralité de transition CR (v) pour le nœud v est défini par:

CR(v) = BC(v) x CB(v)

Le coefficient de bridging d'un nœud v est défini par:

BC (v) = 𝑑 𝑣 −1

1

𝑑 𝑖 iϵN v

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

N(v) est l'ensemble des voisins du nœud v.

F. Quality of Backup (QoB) and Alternative Path Centrality

(APC)

L'utilisation de la centralité dans l’analyse de la robustesse du réseau a été déjà proposée dans la littérature. Shavitt et Singer [11] présentent deux nouveaux mesures de centralité fondées sur l'existence d'un chemin secondaire (alternatif ou de sauvegarde) si un nœud tombe en panne, à savoir la qualité de Sauvegarde (QOB) et la centralité de chemin alternatif (APC). L'idée derrière ces deux centralités est tel que la défaillance de nœuds avec des parfaites chemins secondaires n'affecte pas ni la connectivité ni augmenter la longueur des chemins dans le réseau. QOB est une mesure du chemin de redirection entre les parents directs du nœud et ses fils directs. La QOB d'un nœud v est :

ρ(v) =

1

max {𝑑𝑣 𝑢 ,𝑤 −1, 1}𝑢∈𝐶𝑣𝑢∈𝜋𝑣

| 𝜋𝑣 |.| 𝐶𝑣 |

où πV est l’ensemble des parents directs de v et CV est l’ensemble d'enfants directs de v. ρ(v) = 1 si v a des parfaites chemins de redirection et ρ(v) = 0 s’il ne l’a pas.

APC est la différence entre la centralité topologique des nœuds, avant et après la défaillance d’un nœud. La centralité topologique d'un nœud u ∈ V, noté χ(u), dépend du nombre de nœuds connectés à u et de leurs distances de u.

χ (u) = 1

𝑑 𝑢 ,𝑤 𝑤∈𝑉\{𝑈} . Par conséquent,

0 ≤ χ (u) ≤ | V | -1; ∀ u ∈ V.

La valeur de l'APC d'un noeud v est définie par :

φ(v)= χ u 𝑢∈𝑉\{𝑣} - χv u 𝑢∈𝑉\{𝑣}

où χv indique que les valeurs de la centralité sont calculée 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, qu’il l’a nommé la centralité

de connexion et reroutage sous contrainte de la longueur de chemin (L-CRC). La centralité L-CRC mesure l'importance d'un nœud v en fonction de l'impact de sa suppression, ce qui affecte la connectivité du réseau et la longueur des plus courts chemins, qui passent par v, entre les autres nœuds et le Sink (nœud 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 définissons l-CRC d'un nœud 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)

La centralité de la connectivité sous contrainte de la longueur de chemin d'un nœud v [6] est le nombre des descendants de v qui seraient repoussé au delà de la limite lmax des pas entre chaque nœud et le SINK lorsque v est retiré du réseau. Nous définissons l-CC (v), la centralité de la connectivité sous contrainte de la longueur de chemin d'un nœud 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)

La centralité de reroutage sous contraint de la longueur de chemin d'un nœud v [6] est le nombre des routes (trajets) entre les descendants de v et le nœud-passerelle (SINK) que leurs longueurs dépasseront la longueur limite lmax, après l'enlèvement de v. Notez que nous ne prenons en considération que les descendants de v qui seront encore relié à l'arbre de routage après la suppression de v.

Nous définissons l-RC (v), La centralité de reroutage sous contraint de la longueur de chemin d'un nœud v comme :

l-RC(v) = ∑wϵD(v)(Max {dv (w,SINK ),lmax }

max {d(w,SINK ),lmax } -1); dv(w,Sink) ≠ ∞

IV. APPLICATIONS DE LA CENTRALITE DANS LES WSNS

Grace à la souplesse et la facilité du déploiement des

algorithmes de calcul de centralités, ces derniers ont pris plus de places dans les travaux de recherches dans les réseaux de capteurs sans fil.

La nature des réseaux de capteurs et la manière de leur déploiement imposent, dans la plupart des cas, l’utilisation de la communication multi-sauts pour atteindre le Sink. Néanmoins, l’emploi de ce genre de communication implique

5

des risques aussi, comme par exemple la charge plus élevée, des nœuds les plus proches du sink, dans la transmission des paquets par rapport aux autres nœuds. D'autre part, lorsque les nœuds utilisent la communication à simple saut (unique) pour atteindre le Sink, les nœuds situés plus loin ont une consommation plus élevée de l'énergie à cause de la longue distance entre ces nœuds et le Sink. Pour surmonter ces problèmes les nœuds-capteurs peuvent être organisés en clusters où, dans chaque cluster, un maitre de cluster (cluster head) est responsable de la communication avec le Sink ainsi qu'avec les nœuds membres [7]. Cependant, dans la plupart des réseaux de capteurs, les nœuds sont statiques. Par conséquent, les nœuds proches du cluster-head subirent une surcharge en permanence. Un autre problème de clustering consiste à choisir le cluster-head et implémenter un mécanisme qui permet l’élection chacun des nœuds membres comme cluster-head à tour de rôle afin d’éviter l’épuisement des batteries de quelques nœuds aussitôt que les autres. Pour répondre à ces problèmes de clustering, plusieurs métriques ont été employées telles que la centralité de degré, proximité, spectrale et d’intermédiarité [2][7].

Dans les réseaux de capteurs sans fil, les Sink doivent être placés judicieusement. Dans le cas des Sink mobiles, le déploiement, la direction et la délocalisation devraient être choisis de façon optimale afin qu'ils puissent améliorer la QoS. Là aussi, il est proposé que les mesures de centralité telles que la centralité d’intermédiarité peuvent être utilisée pour déterminer l’emplacement optimal, la direction et la délocalisation [3].

Les réseaux de capteurs sans fil sont employés dans diverses applications. Parfois, les nœuds sont tenus à transmettre périodiquement ou sur la détection d’un événement (changement de mesures), des informations de débit faible comme la température, l’humidité, la pression, etc. Cette transmission peut être retardée avec un délai qui peut être accepté ou non. D'autre part, certaines applications nécessitent un début de transmission des données plus élevé mais avec un délai de retard intolérant comme la vidéo en direct de la zone surveillée par les capteurs en cas de détection de cibles, des prises instantanés par le capteur-caméra ou bien la transmission des informations audio. Un routage multi-sauts avec un débit optimisé est généralement préféré dans de tels cas. Par conséquent, des mesures de centralité, qui pourraient aider à équilibrer la charge et accroître l'efficacité énergétique, comme la centralité d’intermédiarité de flux dans le réseau pourraient être un bon choix [7].

Dans certains cas, la couverture présente un enjeu primordial pour répondre aux exigences de l'application, peu importe combien de capteurs sont déployés. En outre, dans de nombreux cas, des capteurs doivent être placés à l'intérieur d'un bâtiment ou une zone sans courir de risques (par exemple dans le cas d’un accident de voiture). Dans un tels cas, il est nécessaire de faire usage de capteurs mobiles, qui peuvent se déplacer vers les bons endroits pour fournir une bonne couverture de la zone surveillée. Là encore, les mesures de centralité comme la centralité de degré, proximité, spectrale ou toute mesure de centralité combinatoire pourraient être utilisées pour améliorer la couverture dans les réseaux de capteurs sans fil [7].

En plus des domaines d’application déjà cités, d’autres recherches ont abordé l’utilisation de la centralité dans l’amélioration de l’efficacité énergétique et la durée de vie du réseau. Parmi ces travaux, on peut mentionner le modèle proposé par Parth H.Pathak et Rudra Dutta [8], qui visent à résoudre le problème de surcharge dans les réseaux qui affecte certain nœuds et implique une surconsommation d’énergie, chose qui peut engendre la déconnexion de tout le réseau à cause la déconnexion de ces nœuds épuisés. Pour résoudre ce problème, Pathak and Dutta ont développé un modèle basé sur la détection des nœuds qui subirent une surcharge grâce à la centralité d’intermédiarité. D’autres travaux mettent le point sur les caractéristiques et les risques topologiques, telles que ceux de Shavitt et Singer [11], qui sont basés sur les mesures de centralité QOB et APC. De sa part, L.Sitanayah [6] a bâti ses travaux de recherche sur la centralité L-CRC. Le but de ces travaux est l’analyse de la robustesse du réseau et l’impact de la suppression d’un nœud (risque de panne ou déconnexion) sur la connectivité au sein du réseau. Junqi Duan et ses collègues [4] ont concentré leurs efforts sur le développement d’un nouveau mécanisme de contrôle d’accès basé sur l’idée d'utiliser la centralité de degré pour évaluer les risques à tenir en compte lors de l'adoption des systèmes distribués, chose qui a permet aussi de rendre les politiques de sécurité raisonnables, réduire les risques et répondre à un certain niveau de protection.

V. COMPARAISON ET RESULTATS NUMERIQUES

Pour concrétiser ce que nous venons de dire, on abordera

dans cette section une étude de cas d’un réseau de capteurs sans fil où on va calculer quelques mesures de centralité et on termine par une discussion des résultats obtenus.

La Figure 1 illustre l’exemple d'un petit réseau qui se compose de 12 nœuds-capteurs et un Sink (nœud-passerelle) avec lmax = 5 (nombre de pas maximum). On note que dans cette topologie, d (L, Sink)> lmax (distance entre le nœud L et le Sink). Les lignes continues sont les chemins de routage depuis les nœuds jusqu’au Sink tandis que les lignes pointillées indiquent les liaisons de communication directes entre les nœuds. Dans cet exemple, le nœud B a la plupart des descendants et le nœud D a le plus de voisins.

Fig. 1. Un réseau qui se compose de 12 nœuds-capteurs et un Sink

Dans le but d’expliquer la différence entre la variété des mesures de centralité, on va prendre l’exemple de quatre de ces mesures : la centralité de proximité, la centralité

6

d’intermédiarité, le coefficient de clustiring et la L-CRC. Ce choix n’est pas arbitraire mais il va nous permettre d’examiner des exemples des différents types de mesure de centralité tels que les mesures locales (centralité de proximité et coefficient de clustiring), les mesures globales (centralité d’intermédiarité) et les mesures développées pour les WSNs (L-CRC). Le tableau 1 présente les valeurs des quatre mesures pour chaque nœud du réseau.

Le calcul de la centralité de proximité et du coefficient de clustering a été réalisé par des méthodes basées sur l’algorithme de Dijkstra, tandis que la centralité d’intermédiarité a été calculée avec un autre algorithme, appelé algorithme de Brandes, jugé plus rapide que celui de Dijkstra, même dans le cas de grands réseaux et d’importante densité. Les valeurs de la centralité L-CRC ont été issues des travaux de L.Sitanayah afin d’examiner l’utilité des variantes de la centralité développées exclusivement pour les WSNs [6].

TABLE I. RESULTATS DE QUELQUES MESURES DE CENTRALITE

APPLIQUEES SUR LE RESEAU DE LA FIGURE1

nœuds C.I a C.P b C.C c L-CRC d

Sink 0.043 0.0278 0.1250 0

A 0.0583 0.0333 0.3750 0

B 0.093 0.0345 0.2500 0

C 0.11 0.0333 0.2308 0

D 0.483 0.0417 0.1250 0

E 0.3116 0.0385 0.1667 (0.181 , 0.25)

F 0.0516 0.0313 0 0

G 0.396 0.0385 0 (0.0909 , 0.0556)

H 0.201 0.0333 0 (0.0909 , 0.1667)

I 0.278 0.0333 0 0

J 0.141 0.0303 0 0

K 0.3 0.0303 0 0

L 0 0.0227 0 0

a. C.I : Centralité d’intermédiarité

b. C.P : Centralité de proximité

c. C.C: Coefficient de clustiring

d. L-CRC : Length-Constrained Connectivity and Rerouting Centrality

D’après les résultats, on remarque que l’utilisation de la centralité d’intermédiarité montre que les nœuds les plus centraux sont respectivement B, D et E. Ceci revient au fait que la plupart des plus courts chemins, entre les nœuds et le Sink, passent par ces nœuds. Par contre, la centralité de proximité montre que le nœud central dans le réseau est D car il a le plus grand nombre des voisins. D’autre part, le coefficient de clust ring indique que les nœuds A et B ont une forte probabilité de créer des clusters autour d’eux. Ceci s’explique par le fait que la plupart des voisins de A et B sont liées entre eux par des liaisons directes. Les nœuds E, H et G ont une centralité L-CRC égale à < 0,1818 ; 0,25>, <0,0909 ; 0,1667> et <0,0909 ; 0,0556> respectivement. Ceci traduit le risque d’avoir au moins un chemin alternatif, en cas de leur défaillance, plus

long que lmax entre au moins l’un de leurs descendants et le Sink.

Ces résultats montrent clairement que chaque centralité a ces propres caractéristiques et son propre domaine d’application, ce qui nécessite un choix judicieux de la définition de la centralité à utiliser, basée sur la nature du réseau et les buts souhaités de l’utilisation de cette notion.

VI. CONCLUSION

Les applications de réseaux de capteurs sont pratiquement

illimitées. Par conséquent, le besoin en matière de nouveaux

protocoles et algorithmes a connu une importante affluence.

Ces algorithmes permettent un stockage de données plus

efficace, une économie de l’énergie, une réduction du taux des

messages échangés et une livraison garantie des messages. Les

diverses mesures de centralité abordés dans ce document

peuvent répondre à ces besoins.

Plusieurs recherches ont déjà été menées sur l’application des mesures de centralité dans les réseaux de capteurs, mais il reste encore énormément d’axes à parcourir dans ce domaine en futur. L'utilisation d'autres variantes de centralités doit être explorée afin que des solutions globale et plus rentables soient développées et répondent aux exigences des applications du monde réel. Parmi ces domaines de recherche, on trouve la couverture sous contraintes, le routage sous contrainte d’énergie et le routage dans les réseaux hétérogènes

REFERENCES

[1] N. F. CHIKHI, “Calcul de centralité et identification de structures de communautés dans les graphes de documents”, Thése, Institut de Recherche en Informatique de Toulouse (IRIT), 2012.

[2] C. Chaudet, N. Costagliola, I. Demeure, S. Ktari, S. Tardieu, “Sélection des brokers dans un réeseau de capteurs en mode publication / souscription,” "14èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (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. 115–130, 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. 1074–1085, 2012.

[9] W. Hwang et al., “Bridging Centrality: Identifying Bridging Nodes In Scale free Networks,” KDD’06, pp 20 23, Philadelphia, USA, 2006.

[10] Freeman, L.C. Freeman, “Centrality in social networks: conceptual

Clarification,” Social Networks, 215–239, 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.