Algorithme K-CDS
Soit G = (V, E) le graphe qui représente notre réseau de capteurs sans fil ; où V est l'ensemble des nSuds capteurs, E est l'ensemble des liens sans fil.
-
Définition 1 : un réseau G est k-connexe s'il n'aura aucune partition quand l'on omet i nSuds du graphe (i = 1, 2, ..., k-1). Une définition équivalente est donnée par le théorème de Menger ; telle que G est k-connexe si chaque deux nSuds sont connectés par k chemins disjoints.
-
Définition 2 : un sous ensemble V' V est un k-DS (k-dominating Set) de G si chaque nSud de V qui n'appartient pas à V' a au moins k voisins dans V'. Le k-DS V' devient k-CDS si le sous graphe G[V'] est k-connexe.
L'algorithme K-CDS utilise une approche préventive basée sur le clustering. Il propose une construction d'un ensemble k-connexe dominant k-CDS (k-Conncted k-Dominating Set) comme un backbone virtuel pour offrir une efficacité de routage aussi bien qu'une bonne tolérance aux pannes. Pour cela, quatre approches ont été introduites ; dont deux sont des algorithmes probabilistes, une est déterministe et la dernière est une hybridation des approches déterministes et probabilistes. Ces quatre approches permettent de considérer différents critères pour la construction des clusters.
C'est un protocole probabiliste où ; chaque nSud a une probabilité Pk pour devenir un nSud du backbone. Pk est déterminé selon la valeur de k, la surface de déploiement du réseau A, le nombre total des nSuds du réseau N, et le rayon de transmission R. La sélection des nSuds backbone est purement aléatoire ; et ne demande aucune information sur les nSuds voisins. Cependant, elle requiert des informations globales sur le réseau (les paramètres k, A, N et R) pour déterminer la valeur de probabilité Pk. le nombre des nSuds backbone prévus est donc N* Pk.
C'est une approche probabiliste adaptée pour les distributions des nSuds non uniformes, où chaque nSud a au moins Bk voisins backbone. Le paramètre Bk est calculé selon les informations globales du réseau aussi bien que les informations des voisins de chaque nSud. L'algorithme de k-Grid est donné comme suit :
Cette approche définit une condition de couverture telle que chaque nSud v est omis du backbone si pour chaque couple (u, w) de ses voisins il existe k chemins disjoints qui connectent u et w via plusieurs nSuds intermédiaires et avec une priorité supérieure à celle de v. La figure suivante montre un exemple où les nSuds u et w voisins du nSud v sont connectés par des chemins disjoints P1, P2, ..., Pk constitués de nSuds de forte priorité (représentés en gris).
Si cette condition de k-couverture est appliquée sur un réseau G k-connexe, le backbone virtuel résultant forme un k-CDS pour G. cette approche permet donc, d'une manière déterministe, de construire un backbone virtuel formant un k-CDS pour le réseau G en supposant initialement que tous les nSuds appartiennent au backbone puis en appliquant la condition de k-couverture sur cet ensemble de nSuds.
Color-Based k-CDS Construction est une approche hybride basée sur la technique de coloration de graphe et permet de construire un k-CDS avec une forte probabilité dans des réseaux relativement dense. Contrairement aux schémas purement probabilistes, l'algorithme CBKC ne dépend pas des paramètres du réseau. Par ailleurs, il est plus facile à implémenter que l'algorithme déterministe discuté ci-dessus. L'idée de base de cette approche hybride est de partitionner aléatoirement le réseau en sous réseaux de différentes couleurs, puis appliquer l'algorithme CDS traditionnel pour chaque sous réseau. La première étape est probabiliste ; quand le réseau est suffisamment dense, les nSuds colorés de chaque partition forme un CDS pour le réseau original. La deuxième étape est déterministe ; chaque backbone coloré construit à l'intérieur d'un sous réseau par l'algorithme CDS est aussi bien un CDS pour le réseau entier. Tous ensemble, les backbones k-colorés forment un k-CDS pour le réseau. La construction CBKC est détaillée ci-dessous :
