7. Les méthodes libres de mesure
Dans cette famille de méthodes, les capteurs cherchant
à déterminer leurs positions s'appuient uniquement sur les
positions des ancres. Aucune mesure de distance ou d'angle n'est
utilisée. Par conséquent, ces méthodes ne peuvent fournir
que
Chapitre 2 la localisation dans les Réseaux de
Capteurs sans Fil
des positions estimées aux capteurs. Les
méthodes (He et al. 2005; Bulusu et al., 2000; Nagpal et al., 2003; Chan
et al., 2005; Datta et al., 2006; Liu et al., 2007, 2005c), pour ne citer
qu'elles, sont des exemples de méthodes libres de mesure.
Il existe deux techniques courantes dans ce type de
méthodes. La première consiste à définir des zones
contenant les capteurs dont les centres de gravité correspondent
à leurs positions estimées. Par exemple, dans (He et al. 2005)
les auteurs proposent le raisonnement suivant : soit n étant le nombre
d'ancres dans le réseau, chaque ancre diffuse sa position. Lorsqu'un
capteur obtient les positions des n ancres, il calcule tous les triangles
possibles qu'il peut former avec ces positions et obtient alors un ensemble de
triangles. Ensuite, pour chaque triangle, le capteur détermine s'il se
situe à l'intérieur ou à l'extérieur. Après
avoir déterminé son appartenance ou non à chacun des
triangles, il en déduit une zone le contenant et calcule sa position
estimée comme étant le centre de gravité de cette zone. En
présence d'un pourcentage faible d'ancres dans le réseau, cette
solution est intéressante. En revanche, si l'augmentation de ce
pourcentage améliore la précision des positions, elle engendre
dans le même temps des calculs importants pour les capteurs.
Dans (Datta et al. 2006), les auteurs définissent des
zones en utilisant non pas des triangles mais des polygones.
Dans la seconde technique, chaque capteur estime les distances
qui le séparent des ancres et applique la multilatération pour
calculer sa position estimée. La méthode HTRefine (Savarese et
Rabaey, 2002) utilise ce procédé. Ce schéma est
également adopté par des méthodes basées
mesures.
HTRefine
75m,--' B At.
Figure II. 2 : DV-hop
Au commencement de la méthode HTRefine, toutes les ancres
diffusent leurs positions.
Chapitre 2 la localisation dans les Réseaux de
Capteurs sans Fil
Lorsqu'un capteur reçoit la position d'une ancre, il
estime la distance qui le sépare d'elle. Pour ce faire, HTRefine utilise
la technique d'estimation des distances DV-Hop.
Dans cette technique, lors de l'inondation des positions des
ancres, chaque capteur calcule le nombre de sauts minimum qui le sépare
de chacune des ancres. Une deuxième vague d'inondation fournit
suffisamment d'informations au capteur pour qu'il puisse convertir ces nombres
de sauts en estimations de distances. La conversion consiste à
multiplier le nombre de sauts séparant le capteur d'une ancre par une
distance moyenne entre deux capteurs voisins. Lors de la première vague,
lorsqu'une ancre A reçoit la position d'une ancre B, elle calcule la
distance euclidienne qui les sépare et la divise par le nombre de sauts.
Elle obtient ainsi une moyenne des distances des sauts entre elle et B et la
communique aux capteurs. Lorsque A reçoit d'autres positions d'ancres,
elle calibre à nouveau sa distance moyenne et diffuse cette mise
à jour aux capteurs afin qu'ils puissent affiner leurs estimations de
distances.
DV-Hop
La figure 2.2 est une illustration de DV-Hop où l'ancre
A estime la distance moyenne d'un saut. Les noeuds noirs représentent
les ancres et les noeuds blancs les capteurs non localisés. Trois sauts
séparent A et B alors que quatre séparent A de C. L'ancre A
calcule les distances euclidiennes d AB = 75m et d AC = 125m. La distance
moyenne d'un saut est donnée par la fraction (125+75)/ (3+4)= 28.75
m.
Le capteur X estimera les distances avec B et C comme suit : d
XB = 2* 28.57 et d XC = 3 * 28.57.
Pour obtenir leurs positions, les capteurs utilisent ensuite
la multilatération. En reprenant l'exemple de la figure 2.2, X obtiendra
sa position en résolvant le système suivant :
Finalement, un processus de raffinement des positions est
effectué. En effet, après avoir estimé leurs positions,
les capteurs les diffusent à leurs voisins. En fonction de ces
données et grâce aux relations de voisinage, les capteurs
calculent à nouveau leurs positions qui se rapprochent de leurs
positions réelles. Après un nombre d'itérations
défini, les capteurs fixent leurs positions estimées. [12]
Chapitre 2 la localisation dans les Réseaux de
Capteurs sans Fil
| 
