Cours Gratuit
Proposition d’approches distribuées pour la restauration de la connectivité dans les RCSFs
multi-canaux
Communication multi-canal dans un contexte distribué
Dans cette partie, nous nous focalisons sur les protocoles distribués conçus pour la communication multi-canal. Ainsi, nous diférencions entre les protocoles d’allocation des canaux qui utilisent seulement les informations de voisinage (solutions natives) de ceux qui utilisent aussi les informations de routage pour mieux attribuer les canaux aux nœuds capteurs (solutions basées sur le routage). 3.2.1 Allocation native des canaux Dans [80], les auteurs ont proposé trois techniques d’allocation des canaux d’une manière distribuée. Deux des trois protocoles proposés visent à minimiser le nombre de canaux nécessaires pour éliminer complètement les interférences dans le réseau. Le premier protocole attribue un canal à chaque récepteur ; tandis que le deuxième attribue un canal pour chaque lien de transmission, c’est à dire un canal est alloué à chaque paire émetteurrécepteur. Par contre, le troisième protocole MinMax, lui aussi distribué et proposé dans le même article, s’applique dans le cas où le nombre de canaux disponibles est limité. L’objectif principal de MinMax est d’attribuer un canal à chaque lien de transmission tout en minimisant le nombre maximal d’interférences se produisant sur n’importe quel lien. Les auteurs de [80] ont également proposé une technique distribuée basée sur TDMA pour l’ordonnancement des liens ain d’éviter les interférences entre les liens utilisant le même canal dans MinMax. L’avantage majeur de MinMax est d’atténuer les goulots d’étranglement dans le RCSF où un nœud ou un lien génère un nombre important d’interférences. Cependant, MinMax traite les voisins appartenant au même parent et ceux appartenant à des parents diférents de la même façon. Ainsi, il peut attribuer le même canal à deux liens de transmission ayant des émetteurs et des récepteurs totalement diférents. Il peut, par contre, donner des canaux diférents à deux liens avec le même récepteur alors que ces deux liens ne peuvent jamais transmettre simultanément. Un autre point faible pour ces protocoles est qu’ils n’ofrent pas un mécanisme pour la réallocation des canaux en cas de pannes.
Allocation des canaux basée sur le routage
Le protocole le plus connu dans cette catégorie est TMCP (Tree-based Multi-Channel protocol)[67], qui est proposé essentiellement pour la collecte de données dans les RCSFs. L’idée principale de TMCP est de considérer les arbres de routage comme étant des groupes disjoints. Ainsi, il assigne un canal diférent aux nœuds de chaque sous-arbre. Ceci permet de router les données des nœuds sources au nœud puits sans commuter les radio le long des routes vers le puits. Cependant, la communication entre les nœuds de deux arbres diférents est impossible ce qui met en question l’eicacité de cet algorithme en cas de panne d’un nœud ou de changement du chemin de transmission. En 2014, le protocole MCC (Multi-Channel Collection) [81] est proposé pour la collecte de données dans les RCSFs. MCC incorpore des mécanismes sophistiqués pour la formation d’arbres de routage équilibrés, l’allocation multifréquence des canaux et la planiication TDMA synchronisée. Pour l’attribution des canaux, MCC utilise un mécanisme de coloration de graphes pour colorer le graphe de conlits. Ce dernier est construit en mettant un lien entre deux nœuds si l’un d’eux interfère avec le ils de l’autre nœud. Ensuite, si un lien existe entre les deux nœuds, le mécanisme de coloration donne deux couleurs diférentes pour ces deux nœuds. Cependant, bien que MCC maximise le débit en utilisant la communication multi-canal et la planiication de la transmission, il suppose que la topologie du réseau et la qualité des canaux ne changent pas au cours du temps. Par conséquent, il ne prend pas en compte la défaillance d’un nœud et n’intègre aucun mécanisme pour résoudre le problème dans ce cas. Le protocole MCRT (Multi-Channel Real-Time communication) [82] est proposé dans le but de minimiser le délai de bout en bout dans les RCSFs temps réel. MCRT utilise une stratégie d’allocation des canaux basée sur les lux pour optimiser le nombre de commutations radios ain de minimiser la consommation énergétique et le délai de transmission. Ainsi, il cherche les routes disjointes pour les lux de données entre chaque nœud source et sa destination. Une fois les routes sélectionnées, MCRT essaye d’allouer un canal différent pour chaque lux de données sur une route disjointe pour éliminer ou réduire les interférences entre les diférents lux. Le point faible de ce protocole est que chaque nœud (sauf la destination) ne peut appartenir qu’à une seule route.
Synthèse
Tous les mécanismes d’allocation des canaux proposés ne prennent pas en considération le rétablissement de la connectivité après l’occurrence d’une panne dans le réseau. Ceci peut afecter les performances du RCSF même avec l’utilisation la communication multi-canal d’où la nécessité d’utiliser un mécanisme qui combine à la fois la communication multi-canal et le recouvrement de pannes. Ainsi, nous proposons deux approches distribuées pour la restauration de la connectivité dans un RCSF multi-canal. Dans la première approche, appelée CR-MC (Connectivity Restoration for Multi-Channel WSNs), nous adoptons un mécanisme d’allocation des canaux où seule l’information de voisinage est utilisée pour minimiser les interférences entre les nœuds voisins. Dans la deuxième approche, appelée CR-RMC (Connectivity Restoration for Routing based Multi-Channel WSNs), nous exploitons les arbres de routage pour améliorer l’eicacité de notre algorithme d’allocation des canaux et ainsi minimiser le taux d’interférences dans le réseau. Néanmoins, nous optons pour une technique d’allocation de canaux qui minimise le nombre de liens conlictuels pour chaque nœud au lieu de minimiser le nombre total de nœuds en conlit dans le réseau. Un lien entre deux nœuds i et j est dit conlictuel si dist(i, j) ≤ Rc et les deux nœuds sont sur le même canal. L’idée est de permettre à chaque nœud du réseau d’avoir un nombre minimal de nœuds voisins avec lesquels il est en conlit plutôt que de minimiser le nombre total de nœuds en conlit dans tout le réseau. En efet, si nous considérons un scénario d’un réseau à six nœuds et deux canaux (chaque couleur représente un canal), une coniguration de canaux qui minimise le nombre de nœuds en conlit dans ce réseau est donnée par la igure 3.1a. Dans cette igure le nœud 2 est en conlit avec trois de ces voisins qui émettent sur le même canal, alors que le nœud 1 et 6 ne sont en conlit avec aucun voisin. Le nombre total de nœuds en conlit dans tout le réseau est égal à quatre. Si maintenant nous optons pour l’afectation des canaux présentée dans la igure 3.1b, nous nous trouvons dans le cas où les nœuds 2 et 6 auront deux liens en conlit et le nœud 1 aura deux liens en conlit, alors que le nombre de nœuds en conlit dans tout le réseau est égal à six. Ainsi, nous avons essayé de minimiser le nombre de conlits pour chaque nœud du réseau plutôt que se trouver dans un cas de igure où certains nœuds ont très peu de liens conlictuels et d’autres nœuds se trouvent en conlit avec un grand nombre de voisins.
Télécharger le document complet
