Approche adaptative et hiérarchique pour la dissémination des connaissances

Approche adaptative et hiérarchique pour la dissémination des connaissances

Un super noeud agit comme un serveur central pour un ensemble de noeuds normaux qui lui sont rattachés. Ainsi, la connaissance est gérée uniquement au niveau des super noeuds et les noeuds normaux y accèdent à travers les super noeuds auxquels ils sont rattachés. Ces super noeuds sont ensuite reliés entre eux au travers d’un réseau virtuel qu’il faudra définir. Le plan global de connaissance sera représenté dans ce cas par l’ensemble des bases de connais- sance distribuées au niveau des super noeuds et sera donc accessible par tout noeud du réseau. et cela, de la manière la plus optimisée possible. La solution la plus simple est, bien évidemment, de diffuser cette connaissance simultanément à l’en- semble des éléments du réseau, or, cette idée est difficilement réalisable dans la réalité. En effet, cette façon de faire engendre une surcharge importante sur les liens étant donné que le coût de diffusion dans le réseau augmente d’une façon exponentielle en fonction de la distance de diffusion [Nguengang et al., 2008]. Le challenge est donc de proposer une méthode de dissémination des connaissances qui répond, à la fois, aux caractéristiques énoncées dans [Clark et al., 2003] (cf. section 1.7.2) et avec un coût (au sens surcharge du réseau) contenu.

Bien que l’architecture à base de super noeuds ait été étudiée dans le cadre de la gestion des connaissances dans les réseaux autonomiques [Diaz and Chen, 2008 ; Abdeljaouad and Karmouch, 2012], le problème de sélection de ces super noeuds demeure un problème ouvert. Ce problème a été défini par Lo et al. [2005] comme étant la sélection d’un ensemble de pairs dans un très grand réseau recouvrant (overlay network). Dans cette architecture, chaque noeud sera connecté à un super noeud comme le montre la figure 2.1. Les pairs sélectionnés fournissent un service particulier pour l’ensemble des pairs du réseau. La difficulté, ici, est qu’un grand nombre de noeuds peuvent être désignés comme super noeuds. Ce processus peut évoluer au cours de temps compte tenu de la forte dynamicité du réseau. Les super noeuds doivent être distribués sur l’ensemble du réseau afin de couvrir, au mieux, l’ensemble des noeuds qui le constitue. Lo et al. [2005] ont proposé un ensemble de contraintes que cette distribution doit respecter totalement ou partiellement. Nous les détaillons ci-dessous : — La surcharge de messages de contrôle (ou Overhead) : afin de maintenir l’architecture hiérarchique, un échange de messages explicites est sou- vent nécessaire. Les échanges fréquents d’informations peuvent donc consommer considérablement la bande passante et nuire ainsi aux per- formances intrinsèques du réseau.— Le cycle de calcul : Il s’agit du nombre de cycles nécessaires à l’accom- plissement d’une procédure de sélection des super noeuds. En effet, tant que la sélection n’est pas effective, le réseau et les applications qui l’utilisent ne peuvent pas fonctionner correctement.

Le problème de sélection d’un super noeud peut être vu comme un pro- blème de “leader election”. Un représentant (ou leader) est un élément élu ou désigné capable de prendre une initiative au nom d’un groupe. Il joue le rôle d’interface pour les éléments ordinaires qui en dépendent. Dans le calcul dis- tribué, l’élection du leader est le processus de désignation d’un seul et même processus organisateur de certaines tâches réparties entre plusieurs noeuds. À l’initialisation, aucun noeud du réseau ne connaît de leader. Un algorithme d’élection du leader est alors exécuté et à chaque noeud normal du réseau sera donc associé un leader. Les noeuds du réseau communiquent donc entre eux afin de décider lequel d’entre eux est le “leader”. Pour cela, ils ont besoin d’un critère de sélection. Par exemple, si chaque noeud a une identité unique, les noeuds peuvent décider simplement que le noeud disposant de la plus grande identité soit le leader.La définition de ce problème a été souvent attribuée à Lelann [Lann, 1977], reprise ensuite en tant que méthode pour créer un nouveau jeton dans un réseau en anneau dont le jeton a été perdu. Ce problème devient encore plus ardu s’il est nécessaire d’élire n Leaders dans un groupe en respectant certaines contraintes liées à l’application. Un tel problème peut être défini comme un problème d’ensemble dominant.Dans la théorie des graphes, un ensemble dominant d’un graphe G = (S; A) est un sous-ensemble S′ tel que tout sommet de l’ensemble S possède au moins une arrête commune avec un sommet de S′. Ce problème a été décrit par Haynes et al. [1998] comme un problème NP-complet.