II.3.3 Problèmes de connectivité et les
solutions dans les RCSF
A cause de déploiement aléatoire des noeuds, il
existe des noeuds critiques influents sur la connectivité du
réseau lorsqu'elles tombent en panne, par conséquent
impossibilité de trouver une route entre une source et une
destination.
Figure2.8 Topologie avec le point d'articulation
[27]
Le graphe suivant simplifie deux algorithmes :
47
II.3.3.1 Algorithme de Détection d'un point
d'articulation dans un graphe unidirectionnel [27]
Données : G (V, E).
Résultat : Ensemble de
points d'articulation
n parcourir le graphe G afin de générer arbre
T, (les arcs de retour sont représentés par lignes
pointées).
n un noeud x n'est pas un point d'articulation si ce
dernier n'admet un successeur, ou si chaque successeur admet un descendant qui
admet arc de retour vers un prdcesseur de x dans l'arbre.
n cas particulier la racine est un point d'articulation si
ce dernier admet plus d'un successeur dans l'arbre.
II.3.3.2 $ 0I41%1CP 1109u%I-organisation [27]
Données : G(V,E), avec
l'ensemble des points d'articulations prcdemment dtectes
Résultat : G(V, E), avec un
ensembles des points d'articulations r~duits, G devient au moins
biconnectée
Pour tout point d'articulation
(AP) faire
n si le point d'articulation AP
admet un voisin redondant Alors le tourner et aller vers AP
(pas 1).
n sinon rechercher des voisins de AP à un
saut.
o si les voisins ont des noeuds redondants, sPlectionner au
moins un noeud avec
la plus grande capacité d'énergie et le
déplacer vers les coordonnés (x, y) de
AP ou augmenter sa porté de radio (communication)
Aller à (pas 1). o sinon
«pas de solution pour AP»; aller pas 1.
Fin pour
49
Get algorithme est appliquée afin d'auto-organise le
réseau et augmente la connectivité autour du point
d'articulation.
Figure2.11 Auto-organisation autour du point
d'articulation
| 
