4.3. Notion de couverture de zone dans les RCSF
La couverture de zone (Figure 4.1) veut dire que nous voulons
déployer un réseau de capteurs pour couvrir tous points de la
zone d'intérêt à couvrir. Cela veut dire que si on prend
n'importe quel point de la zone d'intérêt, ce dernier doit
être couvert par au moins un noeud capteur. Ce type de couverture est
utilisé généralement dans la majorité des
applications, telles que la surveillance de forêts pour détecter
d'éventuels incendies et la surveillance de champs de bataille. Pour
établir une couverture de zone on doit déployer les noeuds soit
de façon aléatoire ou déterministe et, pour cela, il faut
répondre à la question suivante : quel est le nombre minimum de
capteurs faut-il utiliser tout en garantissant un taux de couverture maximum
[37] sans oublier que les noeuds proches des station de bases sont plus
sollicité pour la transmission des donnée que d'autres noeuds
relativement loin donc, il faut déployer plus des noeuds dans des
régions proches des stations de base.
Figure 4.1 Couverture de zone
d'intérêt
28
29
4.4. Définition de la redondance
Chaque méthode de détection de la redondance
emploie une procédure spécifique pour évaluer la
redondance d'un capteur, néanmoins le critère de redondance est
le même pour toutes ces méthodes ; un noeud est redondant si sa
zone de surveillance est couverte par les zones de surveillance de ses voisins.
Ce critère peut être formalisé de la façon suivante
:
Un noeud est complètement redondant si UJN E (
j) S(i) _CS(j) tel que S(i), S(i) est la zone de surveillance
du capteur « i » et « j » respectivement
étant j les voisins de i.
Nous avons remarqué que l'ensemble N(i) est
défini de deux façons dans les travaux portant sur les
problèmes de couverture en tant que la distance séparant le noeud
« i » de ses voisins est inférieure au rayon de
couverture Rs ou bien inférieure à deux fois le rayon
de couverture 2Rs;
Il existe aussi la redondance partielle qui est
utilisée par la classe d'applications qui tolèrent la
présence de quelques régions vides dans la zone
d'intérêt [30].
4.5. Classification des méthodes de
détection de la redondance
Les méthodes que nous allons présenter dans
cette section sont à l'origine intégrées avec des
algorithmes d'ordonnancement d'activités, en tant qu'étape en
début du schéma d'ordonnancement. L'ordonnancement
d'activités dans un réseau de capteurs consiste à alterner
les charges de façon à épuiser les noeuds
équitablement. Pendant qu'une partie participe à l'application,
les capteurs redondants sont dans un mode passif, économisant ainsi leur
énergie.
L'ordonnancement d'activités des capteurs doit
toutefois préserver le but essentiel du réseau, en faisant en
sorte que quel que soit l'état des capteurs la zone
d'intérêt doit être couverte le plus complètement
possible [38, 39]. De plus, l'efficacité d'un algorithme
d'ordonnancement dépend largement de l'efficacité de l'algorithme
de détection de la redondance, c'est pour cette raison que ces derniers
visent à détecter un nombre maximum de capteurs redondants. Etant
donné que nous nous intéressons au problème de
détection de la redondance, nous allons donc étudier les
méthodes utilisées avec les algorithmes d'ordonnancement, et
proposer une classification de ces méthodes selon l'approche
utilisée pour déterminer la redondance des capteurs. Nous
distinguons deux approches, à savoir : l'approche
géométrique et l'approche analytique. Dans chaque approche, nous
avons également catégorisé les travaux proposés
selon la technique employée pour la détection de la redondance
des capteurs, voici dans la figure 4.2 qui suit une classification des
méthodes de détection.
Méthodes de détection de la
redondance dans les réseaux de
capteurs
La couverture de périmètre
Les secteurs sponsorisés
Approche géométrique
La méthode des grilles
Couverture des
points
d'intersection
La méthode
de
sectorisation
Les sommets de Voronoi
La méthode de Wu et al
La méthode de Bulut et al
Approche analytique
La méthode LUC
30
Figure 4.2 Classification des méthodes de détection
de redondance dans les RCSF. 4.5.1. L'approche
géométrique
Les techniques de détection de la redondance qui se
base sur la géométrie prennent comme données les
informations de localisation des noeuds capteurs et se basent sur des calculs
géométriques pour formaliser le problème afin de
détecter la redondance :
a) La technique des secteurs sponsorisés
:
Tian et al. [40] proposent le modèle des secteurs
sponsorisés pour la détection des capteurs redondants. Dans ce
modèle, un capteur «Si » est appelé sponsor du capteur
«Sj » si la distance qui les sépare est inférieure au
rayon de surveillance Rs, autrement
d(Si, Sj) =
Rs, ici l'intersection est représentée
sur forme de secteurs car c'est plus facile de calculer sa surface. La
règle de redondance avec les secteurs sponsorisés est comme suit
: Si l'union des secteurs sponsorisés des sponsors d'un capteur atteint
2ð , alors le capteur est redondant. Les auteurs dans [41] soulignent une
limite de la méthode des secteurs sponsorisés dans le fait
qu'elle considère seulement les voisins se trouvant dans la zone de
couverture du capteur voulant évaluer sa redondance.
31
Figure 4.3 Représentation des secteurs
sponsorisés.
b) La technique de couverture de périmètre
:
La technique de couverture se base sur la valeur de la
couverture de périmètre des voisins du capteur voulant
évaluer sa redondance ou sur la couverture de périmètre
des segments des voisins, parmi les méthodes qui utilisent cette
technique on cite la méthode de périmètre couvert, la
méthode de Jiang et al et la méthode de Huang et al. La
règle de la redondance dans ce cas est que si la valeur de la couverture
de périmètre des voisins ne change pas en supprimant le capteur
Si alors il est redondant.
Figure 4.4 Couverture de périmètre
c) La technique des grilles :
Elle constitue une démarche simple de détection
de la redondance des capteurs, dans laquelle chaque capteur maintient une liste
des points de la grille se trouvant dans sa zone de couverture. Si ces points
sont couverts par ses voisins actifs, donc le capteur est redondant. Comme
indiqué sur la figure 4.5, les points de la grille
représentés par des cercles gras sont couverts par le capteur S1
et ces mêmes points sont également couverts par ses voisins. Le
capteur est redondant si ses voisins sont actifs. Parmi les méthodes qui
utilisent cette technique, nous citons la méthode de Bai et al ou il
s'agit de vérifier que chaque point de la grille appartenant à la
zone de surveillance du noeud est couvert par au moins un voisin en comparant
la distance qui sépare chaque point de la grille des capteurs voisins,
si cette distance est inférieure au rayon de surveillance alors le point
est couvert.
32
Figure 4.5 : Utilisation de l'approche en grilles pour la
détection de la redondance [35].
Nous citons aussi la méthode SCRC (Self Calculated
Redundancy Check) de Sakib qui introduit le concept de la ?-redondance,
qui stipule que si un point qi est couvert par au minimum ?+1 noeuds alors i
est ? redondant.
d) La technique de couverture des points d'intersection
:
Wang et al. se basent sur la couverture des points
d'intersection entre les voisins d'un noeud pour déterminer sa
redondance. L'intersection des zones de couverture de deux capteurs
créent deux points d'intersection sur leurs périmètres de
couverture. Les points d'intersection considérés par cette
méthode sont les points se trouvant à l'intérieur de la
zone de couverture du capteur voulant évaluer sa redondance. Si tous les
points d'intersection se trouvant dans la zone de couverture du capteur sont
couverts, alors il est redondant.
Wueng et al. proposent l'algorithme EKE (Efficient
K-CoverageEligibility) qui permet de réduire la complexité
des calculs en considérant de vérifier la couverture de quelques
points d'intersection candidats au lieu de tous les points se trouvant dans la
zone de couverture du capteur calculant sa redondance, les auteurs proposent
aussi l'algorithme AKCE (Accurate K-CoverageEligibility) basé
sur la découverte d'une petite surface de décision à
l'intérieur de la zone de couverture de chaque capteur.
e) La méthode RSE :
Carbunar et al. [01] utilisent le concept des diagrammes
Voronoi pour détecter la redondance d'un capteur, et formalisent le
problème d'élimination des noeuds redondants (RSE- Redundant
Sensor Elimination) en proposant une solution basée sur le pavage de
Voronoï. Le diagramme de Voronoi, parfois appelé tessellation de
Dirichlet, est une des structures géométriques les plus
importantes en pratique. Il peut être informellement défini comme
étant un partitionnement de l'espace en régions, où
chacune de ces régions est le lieu de points de R2 le plus
proche d'un objet donné P que de tout autre objet Q dans R2.
Le diagramme de Voronoi d'une collection de noeuds partitionne l'espace en
polygones. Les côtés d'un polygone de Voronoi sont définis
par les bissectrices verticales des lignes reliant le noeud enveloppé
par ce polygone aux autres noeuds voisins. La figure 4.7 montre un exemple d'un
polygone de diagramme de Voronoi.
33
Figure 4.6. Diagramme de Voronoi
La règle de redondance de la méthode RSE est
comme suit : Un capteur s est redondant si et seulement si tous ses 2-VV (les
sommets des régions de type 2-Voronoi) et 2-VIP (l'intersection entre
une arête de la région 2-Voronoi de et le périmètre
de la zone de surveillance) sont couverts par ses voisins Voronoi.
f) La technique de sectorisation :
Khedr et al. proposent l'algorithme de découverte de la
redondance (the redundant discovery algorithm), qui détermine la
redondance d'un capteur en effectuant une sectorisation de sa zone de
couverture en six secteurs et en testant la couverture de chaque secteur. La
règle de redondance de cette technique est comme suit : un capteur est
redondant si ses secteurs ( Secti C {1,..,6} (Si) ) sont couverts par la zone
de surveillance de ses voisins.
En divisant la zone de surveillance en six secteurs
égaux d'un angle de 60°, les auteurs ont prouvé qu'un
secteur est couvert s'il contient un capteur à l'intérieur.
Toutefois, il se peut que le secteur soit couvert même s'il ne contient
pas de capteur à l'intérieur, dans ce cas il suffit de
vérifier la couverture de la frontière du secteur (i.e. la
distance entre chaque point de la frontière et le noeud voisin est
inférieure à ). Si les points frontières du secteur sont
couverts par le même noeud, alors le secteur est couvert par ce noeud.
Sinon, le secteur est divisé en deux sous-secteurs égaux et les
mêmes étapes sont répétées jusqu'à
atteindre un secteur avec un angle limite.
Figure 4.8 Méthode de sectorisation
La découverte de la redondance se base sur la
couverture des secteurs. L'algorithme de découverte de la redondance est
exécuté par chaque noeud et passe par trois phases :
? Phase 1 : le noeud envoie un message à ses voisins
contenant sa position ; ? Phase 2 : Le noeud divise sa zone de surveillance en
six secteurs ;
? Phase 3 : Pour chaque secteur, il considère qu'il est
couvert s'il a un capteur à l'intérieur, sinon le noeud
exécute les étapes suivantes :
o
34
Si les points frontières du secteur sont couverts par le
même noeud, alors le secteur est couvert par ce noeud ;
o - Sinon, les étapes suivantes sont
répétées jusqu'à ce que l'angle du secteur atteigne
un seuil :
- Le secteur est divisé en deux sous-secteurs égaux
;
- La couverture des points de la frontières du
sous-secteur est vérifiée ;
- Si tous les points de la frontière sont couverts,
retourner à (i). Sinon le noeud n'est pas redondant.
4.5.2. L'approche analytique
Les méthodes basées sur l'approche analytique
n'utilisent aucune information de localisation pour la détection de la
redondance, et ne requièrent pas non plus la connaissance des
informations directionnelles ni la distance séparant les capteurs. Elles
se basent seulement sur le nombre de voisins à un saut du capteur
voulant évaluer sa redondance, et assument l'existence d'un
mécanisme qui permet aux noeuds de connaitre leur nombre de voisins
à un saut, par exemple en envoyant des messages hello (beacons)
contenant seulement l'identifiant des noeuds.
Ces méthodes se basent sur un modèle de calcul
probabiliste pour décrire la redondance des capteurs. L'utilisation du
calcul probabiliste permet seulement d'estimer la redondance partielle des
capteurs et non pas complète.
a) La méthode de Wu et al. :
Les auteurs dans [30] introduisent une formule simple pour
estimer la redondance des capteurs, en définissant une borne
inférieure et supérieure de la probabilité d'une
redondance complète d'un capteur. Ils estiment également la
probabilité d'une redondance partielle donnent une bonne heuristique
pour l'estimation du nombre de voisins nécessaires pour obtenir une
certaine redondance.
b) La méthode de Bulut et al. :
Cette méthode estime la redondance des capteurs en
calculant le ratio du capteur couvert par ses voisins [33]. Les auteurs
estiment qu'en connaissant seulement le nombre de ses voisins, un capteur est
en mesure de calculer Pn (i).
35
Figure 4.9 Méthode de Bulut et al [33]
c) La méthode LUC :
Younis et al. [44] proposent la méthode LUC (Location
Unware Coverage) qui se base sur quatre tests pour vérifier la
redondance d'un capteur. Deux tests (RTest-D1 et RTest-D2) sont
géométriques, tandis que les deux autres tests (RTest-H1 et
RTest-H2) sont destinés à un déploiement dense. Pour
déterminer la redondance d'un noeud, la méthode exploite les
distances séparant ce noeud de ses voisins. Les auteurs assument qu'un
noeud peut estimer les distances le séparant de ses voisins à un
saut en utilisant quelques approches connues, telle que la force du signal RF
reçu minimale parmi ses voisins.
La procédure de vérification de la redondance se
déroule selon l'ordre cité ci-dessus. Si le résultat d'un
test détermine que le noeud est redondant, la procédure de
vérification est terminée et le noeud passe à
l'état passif. Par contre, si tous le résultat de tous les tests
est négatif le noeud n'est pas redondant (état actif).
| 
