Etat De L\'art Algo RéSeaux De Capteurs sans-fil

$Page 1: Etat De L\'art Algo RéSeaux De Capteurs sans-fil$
LOC‟In Recherche bibliographique – Algorithmes de localisations 1

Etat de l‟art sur les algorithmes de Localisation

basés sur les

Réseaux de Capteurs sans-fil

(Version beta)

Kaïs MABROUK

ESIGETEL 2011


Sommaire

Introduction générale .................................................................................................................. 4

I-Positionnement du problème de localisation ........................................................................... 5

II- Classification de la localisation dans les réseaux de capteurs sans-fil .................................. 8

III. Localisation centralisée ...................................................................................................... 10

III.1 MDS-MAP ................................................................................................................... 10

III.2. Localisation des nœuds basée sur le « recuit simulé » ................................................ 11

III.3. Une technique de localisation centralisée basée sur le RSSI ...................................... 13

IV. Localisation Distribuée ...................................................................................................... 14

IV.1. Localisation distribués basée sur les Balises ............................................................... 14

IV.2. Algorithme distribué basé sur la relaxation ................................................................ 21

IV.3. Pointage d‟un système de coordonnées ...................................................................... 25

IV.4. Localisation hybride .................................................................................................... 29

IV.5. Localisation basée sur l‟interférométrie ...................................................................... 33

IV.6. Propagation des erreurs au cours de la localisation .................................................... 33

Conclusion générale ................................................................................................................. 35

Les axes de recherche porteurs dans la localisation basée sur les WSN .................................. 36


Liste des figures

Figure 1 Techniques de localisation ........................................................................................... 8

Figure 2 Classification des différentes techniques de location dans les réseaux de capteurs .. 10

Figure 3 Illustration de l‟ambigüité .......................................................................................... 13

Figure 4 (a) Multilatération à un saut (b) Multilatération à deux sauts .................................... 16

Figure 5 Limitation des coordonnés x de C à partir des estimations initiales. ......................... 17

Figure 6 Estimation à travers les multiples sauts ..................................................................... 18

Figure 7 Erreur de saut due à la présence d‟obstacles .............................................................. 21

Figure 8 (a) ambigüité de symétrie (b) ambigüité de discontinuité ......................................... 25

Figure 9 Topologie réseau avec des distances inter-nodes ...................................................... 27

Figure 10 (a) matrice des distances entre nœuds (b) Chevauchement locale des cartes ......... 28

Figure 11 Carte initiale ............................................................................................................. 29


Introduction générale

Les progrès massives des systèmes micro-électromécaniques (MEMS), et des

technologies de calcul et de la communication ont provoqué une émergence des réseaux de

capteurs sans fil, qui peuvent constituer des centaines de milliers de nœuds. Chaque noeud est

capable d‟écouter l'environnement, d‟exécuter des calculs simples et de communiquer avec

ses capteurs voisins ou à un serveur. Une manière pour déployer les réseaux de capteurs est de

disperser les nœuds à travers certaines régions d'intérêt. Cela rend la topologie du réseau

aléatoire. Ces réseaux sont très utilisés pour effectuer un certain nombre de tâches, allant de

la simple surveillance de l'environnement et de l'habitat sous forme de réseaux domestiques,

à des applications médicales et des applications militaires sur les champs de bataille. Un

réseau de capteurs peut signaler un dysfonctionnement d‟un appareil au centre de contrôle et

maintenance dans une usine ou avertir à distance d‟une fumée sur une colline boisée indiquant

qu'un incendie de forêt vient de commencer. D'autre part, un groupe de nœuds de capteurs

sans fil peuvent être conçus pour détecter les vibrations du sol générées par les pas silencieux

d'un cambrioleur afin de déclencher une alarme.

Comme la majorité des applications nécessitent une localisation fine, c'est à dire de calculer

leurs positions dans un système de coordonnées fixe, il est d'une grande importance de

disposer d‟algorithmes de localisation efficaces. Les articles [1], [2], [3], montrent que dans

les réseaux ad hoc à grande échelle, la localisation peut aider dans le routage. A la maternelle

[4], la localisation peut être utilisée pour surveiller les progrès des enfants par le suivi de leurs

interactions avec des jouets et aussi les uns avec les autres. Elle peut être également employée

en milieu hospitalier pour maintenir le suivi des équipements, les patients, les médecins et les

infirmières [1].

Les possibilités cités ci-dessus, notamment une localisation précise des nœuds fixes

ou mobiles dans les réseaux de capteurs, sont la source de recherche très active dans le

domaine des réseaux sans fil. A cet effet, une solution simple peut être envisagée. C‟est par

l‟ajout des GPS à tous les nœuds dans le réseau. Malheureusement, cette solution n'est pas

possible à cause des contraintes suivantes :


• Le GPS ne peut pas être mis en œuvre en présence de forêts denses, des montagnes ou

d'autres obstacles qui bloquent le champ de vision des satellites GPS.

• La consommation électrique du GPS réduit la durée de vie des batteries des capteurs ce qui

contribue également à diminuer la durée de vie effective de l'ensemble du réseau.

• Dans un réseau qui comprend un nombre important de nœuds, le coût de production du GPS

est élevé.

• Les capteurs doivent être de petite taille. La taille du GPS ainsi que de son antenne font

augmenter la taille du capteur.

Pour mieux répondre à ces problèmes, une solution alternative est nécessaire. Cette

solution doit être rentable, avoir un déploiement rapide ainsi que la possibilité de fonctionner

dans des environnements divers.

Toutes les techniques sans-fils (RFID, UWB, ZigBee, Bluetooth, WiFi…) utilisées

pour la localisation fait appel à une communication de données entre un point et un autre ou

entre un point et plusieurs autres ou autre mode de communication entre des nœuds. Ce qui

peut se généraliser par des réseaux de capteurs.

I-Positionnement du problème de localisation

Prenons le cas où nous avons déployé un réseau de capteurs comprenant N capteurs qui ont

l‟ensemble des emplacements S , avec SSSS N,....,,

21 . Soit S

i

x, S

i

y, S

i

z les

coordonnées zyx ,, respectivement. Dans le cas où Si

z est à 0, c‟est la version 2D du

problème. La détermination de ces emplacements constitue le problème de localisation.

Certains nœuds de capteurs connaissent leurs propres positions, ces noeuds sont connus

comme ancres. Tous les autres nœuds se localisent à l'aide des références de localisation

reçues à partir de ces ancres. Donc, mathématiquement le problème de localisation peut être

formulé comme suit: étant donné un réseau multi-sauts, représenté par un graphe EVG , ,

et un ensemble de nœuds balises B , dont leurs positions yx bb, pour tous les b ε B, nous

voulons trouver la position yx uu, pour tous les nœuds inconnues u ε U.


Différentes approches de détermination de position

Les approches existantes pour la détermination des positions se composent fondamentalement

de deux phases principales :

(1) estimation des distances et (2) combinaison de distance.

Les méthodes les plus connues pour estimer la distance entre deux noeuds sont décrites ci-

dessous :

Indicateur reçu sur le niveau de puissance du signal (RSSI) :

RSSI mesure la puissance du signal au niveau du récepteur et est fondée sur l‟estimation de la

puissance de transmission (communication). Les pertes dues à la propagation peuvent en être

déduites.

Ensuite et en se basant sur des modèles théoriques et empiriques nous pouvons traduire cette

perte en une estimation de la distance. Cette méthode a été utilisée essentiellement dans le cas

des signaux RF. RSSI est une solution relativement peu coûteuse sans aucun périphérique

supplémentaire, sachant que tous les nœuds de capteurs sont susceptibles d'avoir l‟équipement

radio. Cependant, en terme de performance, cette solution n'est pas aussi bonne que d'autres

techniques. Cela est dû aux trajets multiples des signaux radio. Dans [26], les auteurs

caractérisent les limites d'une série de solutions de localisation en intérieur en utilisant la

puissance du signal issue des routeurs de la norme 802,11. Ils suggèrent également que l'ajout

de matériel supplémentaire ou la modification de modèle de propagation est la seule

alternative pour améliorer les performances de localisation.

Méthodes temporelles :

Techniques de localisation par différence de temps (ToA, TDOA): mesures des instants

d‟arrivées ou les instants de différence des arrivées (TDoA). Ces temps de propagation


peuvent être directement traduits en distance, tout en se basant sur la vitesse de propagation

connue des signaux. Ces méthodes peuvent être appliquées à de nombreux signaux différents,

tels que les signaux RF, acoustique, infrarouge et ultrasons. Ces méthodes ont une précision

impressionnante à conditions qu‟il y est une visibilité directe. En outre, la vitesse du son varie

avec la température de l'air et l'humidité, ce qui introduisent des inexactitudes dans

l'estimation des distances. Les signaux acoustiques subissent aussi les effets engendrés par les

trajets multiples qui peuvent provoquer des incertitudes importantes.

Techniques de localisation par Angle d'arrivée (AsA):

Estimation de l'angle sous lequel les signaux sont reçus et l'utilisation des relations

géométriques simples pour calculer les positions des noeud. Généralement, les techniques

AoA fournissent des résultats de localisation plus précis que les techniques basées sur le

RSSI, mais le coût du matériel dans ce cas est plus important.

Techniques par combinaison:

Trilatération hyperbolique: est la méthode la plus simple et intuitive. Son principe de

localisation des nœuds se base sur le calcul de l'intersection de 3 cercles comme il était

montré dans la Fig. 1 (a).

Triangulation: Cette méthode est utilisée lorsque la direction du nœud est estimée au lieu de

sa distance, comme dans les systèmes AoA. Les positions des nœuds sont calculées dans ce

cas en utilisant les lois de trigonométrie des sinus et cosinus (représenté sur la Fig. 1 (b)).

Estimation du Maximum de vraisemblance : estime la position d'un nœud en minimisant les

différences entre les distances mesurées et les distances estimées (représenté sur la figure 1

(c).).


Figure 1 Techniques de localisation

II- Classification de la localisation dans les réseaux de capteurs sans-fil

Cette partie présente les différentes contributions formulées par la communauté

scientifique spécialisée dans le domaine de la localisation dans les réseaux de capteurs sans fil.

Différentes critiques qui correspondent à ces propositions sont aussi présentées. La recherche

sur la localisation dans les réseaux de capteurs sans fil peut être classée en deux grandes

catégories.

II-1La Localisation centralisée

Localisation centralisée est essentiellement basée sur le déplacement des inter-nœuds ayant

une connectivité de données à une station de base centrale suffisamment puissante, puis le

déplacement des sites résultant de nouveau vers les noeuds respectifs. L'avantage des

algorithmes centralisés est d‟alléger la charge du calcul dans chaque nœud, Cependant, cette

méthode est limitée par le coût de la communication de déplacement des données vers la

station de base. Une présentation détaillée de cette catégorie est disponible dans [5], [6] et [7].

La Localisation Distribuée:

Dans ce cas, les capteurs eux-mêmes sont chargés de faire les calculs pertinents sur différents

nœuds qui constituent le réseau. Ces nœuds communiquent les uns avec les autres afin

d‟obtenir leurs emplacements dans un réseau. La localisation distribuée peut être classées en

trois catégories :

• Algorithmes distribués basé sur des balises : Cet algorithme commence par faire des

mesures de distance à quelques balises en exploitant un certain groupe de balises et de


nœuds dans le réseau, puis utilise ces mesures pour déterminer leur propre position. Certaines

des propositions de cette catégorie [8], [9], [10], [11], sont décrites plus loin.

• Algorithmes distribués basés sur la relaxation: Cette méthode utilise des

algorithmes distribués bruts pour localiser à peu près les noeuds du réseau. Ces algorithmes

sont suivis par une étape de raffinement, qui implique typiquement chaque nœud afin

d‟ajuster leurs position pour approcher la solution optimale. Certaines de ces propositions [12],

[13] sont examinées en détail.

• Algorithmes distribués basés sur un système de coordonnées de points : Dans cette

méthode, le réseau est divisé en petits sous régions de recouvrement. Chacune de ces régions

crée une carte optimale locale. Ensuite, une fusion de ces cartes locales en une seule carte

globale est établie. Certaines approches de cette catégorie [14], [15] sont examinées plus loin.

• Les algorithmes hybrides de localisation: Les schémas de localisation hybrides utilisent

deux techniques différentes de localisation : la graduation multidimensionnelle (MDS) et la

carte basée sur la proximité (PDM) ou MDS et le système de positionnement Ad-hoc (APS)

pour réduire le coût de communication et de calcul. Ce genre d'approche est décrit en détail

dans [16], [17].

• Localisation basée sur l’interférométrie : Cette méthode exploite les ondes radio émises à

partir de deux endroits et à des fréquences légèrement différentes pour obtenir les

informations nécessaires concernant la portée et la localisation. Ce type de technique de

localisation est proposé dans [18], [19] and [20].

• Localisation par prise en compte de la propagation des erreurs: Lorsque les capteurs

communiquent les uns avec les autres, cela peut provoquer une des erreurs de propagation

dues à l'environnement radio, tels que l‟évanouissement du canal et du bruit. Pour supprimer

les erreurs de propagation, il a été proposé dans [21] une méthode appelée algorithme

d‟évitement d‟erreur de propagation.


La figure. 2. montre une classification des différentes méthodes.

Figure 2 Classification des différentes techniques de location dans les réseaux de capteurs

III. Localisation centralisée

III.1 MDS-MAP

Dans [5], les auteurs présentent un algorithme de localisation centralisée appelée MDS-MAP

qui consiste essentiellement en trois étapes :

1. D'abord le système calcule les plus courts chemins entre toutes les paires des nœuds

dans la région considérée en utilisant tous les algorithmes qui calculent les paires des

plus courts chemins tels que l‟algorithme de Dijkstra ou l‟algorithme de Floyd. Les

distances des plus courts chemins sont utilisées pour construire une matrice de

distance de la partie MDS.

2. Ensuite la MDS classique est appliquée à cette matrice de distance, en conservant les 2

(ou 3) premières des plus grandes valeurs et vecteurs propres pour construire une carte

2-D (ou 3-D) relative qui donne une position pour chaque noeud. Bien que ces lieux


peuvent être précis relativement les uns aux autres, la carte sera arbitrairement tournée

et déplacée par rapport aux vraies positions des noeuds.

3. En se basant sur la position d‟un nombre suffisant d‟ancres (3 ou plus pour le 2-D, 4

ou plus pour le 3-D), la carte relative est transformée en une carte absolue en se basant

sur des positions absolues des ancres qui comprennent le dimensionnement, la rotation

et l‟effet miroir. L'objectif est de minimiser la somme des carrés des erreurs entre les

positions réelles des ancres et de leurs positions transformées dans la carte MDS.

L'avantage de ce système est qu'il ne nécessite pas de nœuds ancres dans la phase

d‟initialisation. Il s'appuie sur une carte relative des nœuds, même sans nœuds ancres et sur

trois ou plusieurs nœuds ancres, pour la carte relative suivante lors de la transformation en

coordonnées absolues. Cette méthode fonctionne bien dans les situations où les nœuds ancres

sont de faibles proportions. Un inconvénient de MDS-MAP est qu'elle nécessite une

information globale sur le réseau et un calcul centralisé.

III.2. Localisation des nœuds basée sur le « recuit simulé »

Dans [6] les auteurs proposent une approche innovatrice basée sur le « recuit simulé » afin de

localiser les nœuds de capteurs d‟une manière centralisée. Sachant que l'algorithme est

centralisé, cette méthode bénéficie à un accès à des informations estimées sur les positions et

les voisins de tous les nœuds localisables dans le système. Considérons un réseau de capteurs

de m ancres de postions connus et mn capteurs avec de positions inconnus. Comme

l'algorithme proposé est implémenté dans une architecture centralisée, il a accès à des

informations estimées des positions et des voisins de tous les nœuds localisables dans le

système. Le système proposé est basé sur deux étapes. Dans la première étape, le recuit

simulé est utilisé pour obtenir une estimation des positions des capteurs localisables en

exploitant des contraintes de distance. Nous allons définir l'ensemble iN comme un ensemble

qui contient tous les sauts des voisins des nœuds i . Le problème de la localisation peut être

formulé comme :


2

1

^

n

mi jijij

N

Min

i

dd (1)

Dans l‟équation 1 , d ijest la distance mesurée entre le nœud i et son voisin j , avec :

2^^2^^^

yyxxd jijiijest la distance estimée,

yx ii

^^, et

yx jj

^^, sont les

coordonnées estimées du nœud i et son seul voisin de saut j , respectivement, et la fonction de

coût : 2

1

^

n

mi jijij

N

CF

i

dd . Ensuite, selon les coordonnées estimées par recuit simulé

yx ii

^^, de n‟importe quel nœud i choisi est donné un petit déplacement dans une direction

aléatoire et la nouvelle valeur de la fonction de coût est calculée pour une nouvelle position

estimée. Si ,0 CF oldnew CFCFCF , puis la perturbation est acceptée et

l'estimation de la nouvelle position est utilisée comme point d‟initialisation de l'étape suivante.

Sinon, la probabilité pour laquelle le déplacement est accepté

est : TCFCFP /exp . IciT est un paramètre de contrôle et de P est une fonction

monotone croissante deT .

Dans la prochaine étape de l'algorithme, les auteurs éliminent l'erreur provoquée par une

l‟ambigüité. Cette ambiguïté se produit lorsque les voisins d'un nœud sont placés dans des

positions approximativement sur la même ligne.

Dans la figure. 3, les voisins du noeud A sont les nœuds B, C, D et E qui sont situés sur la

même droite et le nœud A peut être renversé à travers la ligne de meilleur ajustement de

nœuds B, C, D et E à la position A‟ avec presque aucun changement de la fonction de coût.

Mais nous devrions noter de la Fig. 3 que la position renversée A‟ est entrée dans le voisinage

faux des noeuds H et I. En se basant sur cette observation, les auteurs définissent un ensemble

de compléments comp( iN ) de l'ensemble iN comme un ensemble qui contient tous les

nœuds qui ne sont pas des voisins du nœud i . Si R est la portée de transmission du capteur et

le coordonné estimé du nœud j comp( iN ) est telle que Rd ij

^, alors le nœud j a été placé

dans le voisinage faux de nœud i . Ainsi l'erreur minimale due à l‟ambiguïté, est Rd ij

^et le

nouveau problème de localisation peut être formulé par l'équation (2).


n

miij

jijij

R

N

Min dddi

1

2^2^ (2)

Par des simulations, les auteurs montrent que l'algorithme proposé donne une meilleure

précision qu‟une localisation issue à partir de programmation semi-définie.

Figure 3 Illustration de l’ambigüité

Ils montrent que l'algorithme proposé ne propage pas les erreurs dans la localisation. La

méthode proposée qui consiste à atténuer l‟ambiguïté est basée sur des informations des

nœuds de voisinage et elle fonctionne bien dans un réseau de capteurs de densité moyenne de

nombre de nœuds élevée. Cependant, lorsque la densité des noeuds est faible, il est possible

qu'un nœud soit renversé et maintient toujours le voisinage correct. Dans cette situation,

l'algorithme proposé ne parvient pas à identifier le nœud retourné.

III.3. Une technique de localisation centralisée basée sur le RSSI

Dans [7] les auteurs proposent une technique qui localise les nœuds à partir des

atténuations RF. Cette méthode se compose essentiellement de trois étapes :

1) la cartographie RF du réseau: est obtenue en transportant des paquets courts à différents


niveaux de puissance à travers le réseau et en stockant la valeur moyenne du RSSI reçus dans

les tables de mémoire.

2) Création du modèle de la portée : Tous les n-uples (lignes de la table mémoire) enregistrées

entre les deux ancres sont traitées par l'unité centrale afin de compenser la non linéarité et de

calibrer le modèle. Soit un n-uple générique PP rxtxji ,,, provient de la cartographie RF

caractérisant la scène, où i est le nœud de transmission et j est le noeud de réception.

Maintenant, le premier algorithme corrige la puissance reçue en ,,'

ppP txrxrxf ()f est

une fonction qui prend en compte les effets de modularité. Ainsi, la distance estimée entre les

nœuds sera donnée par :

pmr rxij

'10.

3) modèle de localisation centralisé: Un problème d'optimisation est résolu et fournit la

position des nœuds. Le résultat final peut être obtenu en minimisant la fonction :

n n

ijijjiji rrakE1 1

20

,,, ),( jidrij

où i et j sont des ancres.

Lorsque N est le nombre des nœuds, a ji,est égal à 1 lorsque le lien est présent et 0 sinon.

Une fois la distance entre les nœuds r ijpeut être exprimée en termes de leurs

coordonnées i

yx, et j

yx, , les auteurs résolvent le problème de minimisation par la méthode

de programmation séquentielle quadratique (SQP).

L'avantage de ce système est qu'il s'agit d'une méthode pratique, et qui a un modèle

d'organisation autonome permettant d‟adresser tous type d‟environnements et également

l‟extérieur. La limitation de ce système est qu‟il est gourmant en termes de consommation car

il nécessite une production extensive de données et un besoin de transmettre une quantité

importante d'informations à l'unité centrale.

IV. Localisation Distribuée

IV.1. Localisation distribués basée sur les balises.


Les approches basées sur les balises peuvent être classées en terme de : diffusion, zone de

délimitation et gradient qui sont décrites ci-dessous:

IV.1.1. Diffusion

Dans la diffusion, la position la plus susceptible du nœud est celle du barycentre de ses

noeuds voisins connus.

APIT: Dans [8] les auteurs décrivent une nouvelle technique de localisation basée sur un

secteur de portée libre, appelé APIT qui nécessite un réseau hétérogène de dispositifs de

détection où certains appareils sont équipés d'émetteurs à haute puissance et des informations

de positionnement. Ces dispositifs sont connus comme des ancres.

Dans cette approche, l'information de positionnement résulte en effectuant un isolement de

l'environnement en régions triangulaires entre les nœuds de balisage. Un nœud inconnu

choisit de tous les ancres audibles et vérifie s'il est à l'intérieur du triangle construit en reliant

ces trois ancres. APIT répète ces tests avec différentes combinaisons d'ancres détectables

jusqu'à la fin de toutes les combinaisons ou la précision requise est obtenue. À ce stade, APIT

calcule le centre de gravité de l'intersection de tous les triangles dans lesquelles le noeud

inconnu réside pour déterminer la position estimée.

L'avantage de APIT réside dans sa simplicité et sa facilité de mise en œuvre. Mais APIT exige

un rapport élevé de balises/nœuds et des balises qui ont une longue portée qui permet

d‟obtenir une bonne estimation de la position. Pour une faible densité de balises cette méthode

ne donne pas des résultats précis.

IV.1.2. Zone de délimitation

Le zone de délimitation constitue une région pour chaque nœud et essaye de raffiner leurs

positions en convergeant la zone à la cible.

IV.1.2.1. Multilatération Collaborative

Dans [9], les auteurs présentent une approche de multilatération collaborative qui se compose


d'un ensemble de mécanismes permettant aux nœuds de trouver à travers plusieurs sauts les

positions des nœuds balises qui collaborent les uns avec les autres pour estimer leurs

emplacements avec une grande précision.

Cette technique se compose de trois phases:

• Formation des arbres secondaires colloboratives: Un arbre secondaire de calcul

constitue une configuration des balises inconnues et des balises pour lesquelles la solution qui

donne une estimation des positions inconnues peut être déterminée d‟une façon unique. La

contrainte d'une multilatération pour un nœud inconnu est qu'il doit appartenir à un intervalle

d'au moins trois balises (voir figure 4 (a)).

Une multilatération à deux sauts représente le cas où les balises ne sont pas toujours

directement reliées aux nœuds, mais ils appartiennent à un rayon de deux sauts à partir du

noeud inconnu (voir Fig. 4 (b)).

Figure 4 (a) Multilatération à un saut (b) Multilatération à deux sauts

• Obtention des estimations initiales: Cette phase est expliquée à l'aide de la figure. 5. Dans

cette figure, A et B sont des balises (ancre), quand à C est le nœud inconnu. Si la distance

entre C et A est a , alors la coordonné x deC est délimitée par a à gauche et à droite de la

coordonnée x de A , axA et axA . De même la balise B qui se situe à deux sauts à partir de

C , délimite les coordonnées deC à l'intérieur de )( cbxB et )( cbxB . Connaissant

cette information, C peut déterminer que sa coordonnée sur x en prenant considération des


balises A et B sont : )( cbxB et axA . La même opération est appliquée sur les

coordonnées y . C combine alors ses limites sur les coordonnées x et y , pour obtenir une

zone de délimitation de la région où il se trouve.

Figure 5 Limitation des coordonnés x de C à partir des estimations initiales.

• Amélioration de la position: Dans la troisième phase, les positions initiales des nœuds sont

affinées à l'aide de mise en œuvre d‟un Filtre de Kalman. Maintenant, étant donné que la

plupart des nœuds inconnus ne sont pas directement reliés aux balises, ils utilisent les

estimations initiales de leurs voisins comme points de référence pour estimer leurs

emplacements. Dès qu'un nœud inconnu calcule une nouvelle estimation, il diffuse cette

estimation à ses voisins, et le voisin va l'utiliser pour mettre à jour leurs propres positions

estimées. Comme le montre la Fig. 6 le premier nœud 4 calcule son emplacement estimé à

l'aide des balises 1 et 5 et comme référence le noeud 3. Une fois le noeud 4 diffuse sa mise à

jour, le nœud 3 recalcule sa propre estimation reçue à partir du nœud 4. Ensuite le nœud 3

diffuse la nouvelle position estimée et le nœud 4 l‟utilise pour calculer une nouvelle estimée

qui est plus précise que son estimée précédente.

La multilatération collaborative permet d'estimer les positions des nœuds de capteurs avec

précision en utilisant des emplacements connus des balises qui sont à plusieurs sauts et la

mesures de distance des noeuds voisins. En même temps, elle augmente le coût de calcul

également.


Figure 6 Estimation à travers les multiples sauts

IV.1.2.2. Localisation des noeuds en supposant des zones carrées :

Dans [10], les auteurs posent le problème de localisation comme suit. Ils ont supposé qu‟il y a

N nœuds dans une région carrée ],0[],0[ ssQ , appelée région des opérations. Ces N

nœuds SS N,...,

1ont été dispersés et dont chacun est équipé d'un émetteur-récepteur RF avec

une portée de communication 0r . En d'autres termes un nœud S ipeut communiquer avec

n‟importe quel nœud qui se trouve dans sa région de communication. Cette région est

représentée par un disque de rayon r centré à S i. Les nœuds forment un réseau ad hoc Ŋ dans

lequel il y a une bordure entre S iet S j

si leur distance est inférieure à r . Ces méthodes

supposent qu'il y a certains nombres positifs des nœuds balises dans Q et les autres sont des

nœuds inconnus. Maintenant, pour tout entier 0n , divisantQ enn2

carrés conformes appelés

cellules de zone ns /2

et pour chaque nœud connu S , nous connaissons la cellule qui

contient S . Pour rendre le problème soluble, les auteurs supposent que la portée de

communication est 2snr , où x désigne la partie entière de x , ce qui signifie que

chaque nœud S peut communiquer avec chaque nœud qui se trouve dans le carré centré en S

et contenant 122

cellules.

Très souvent n est grand et r est beaucoup plus petit que n , en particulier n12 . Ensuite,

pour un nœud inconnue S quelconque dans Ŋ, l'algorithme de localisation de S peut être écrit

comme:


Etape 1: Initialiser l'estimation: QLs .

Etape 2: Envoyez des paquets « Bonjour » pour les voisins. Chaque voisin connu

renvoie ba,,1 , où ba, est sa position sur la grille, alors que chaque voisin inconnu

envoie 0,0,0 .

Étape 3: Pour chaque réponse ba,,1 mettre à jour l‟estimation comme indiqué dans

l'équation (3).

bbaaLL ss ,, (3)

Étape 4: Arrêtez lorsque toutes les réponses sont reçues. La position estimée est alors sL .

Dans cette approche, un nœud inconnu pourra interroger certains de ses voisins ce qui réduit

le coût de la communication, mais avec un taux important de calcul.

IV.1.3. Gradient

Dans [11] les auteurs décrivent un algorithme pour organiser un système de coordonnées

global à partir d‟une information locale. Dans cette approche, des nœuds de capteurs ad-hoc

sont distribués aléatoirement sur un plan bidimensionnel et chaque capteur communique avec

des capteurs de proximité sur une distance fixe r , où r est beaucoup plus petit que la

dimension du plan. Dans leur algorithme, ils assument un certain ensemble de capteurs

"graines" qui sont identiques à d'autres capteurs en terme de capacité, sauf qu'ils sont déjà

programmés avec leurs positions globales.

L'algorithme se compose de deux parties:

• Algorithme du Gradient: - Chaque capteur graine produit un gradient de propagation local

qui permet à d'autres capteurs d‟estimer la distance entre les capteurs graines. Un capteur

graine lance un gradient en envoyant à ses voisins un message avec son emplacement et une

incrémentation d‟un compteur à un. Chaque destinataire se souvient de la valeur du compteur

et transfère le message à ses voisins en incrémentant le compteur de un. Par conséquent une

vague de messages se propage de la graine vers l'extérieur. Chaque capteur maintient la valeur


minimale du compteur reçu et ignore les messages contenant les plus grandes valeurs, ce qui

empêche à la vague de reculer vers l'arrière. Si deux capteurs peuvent communiquer

directement entre eux alors ils sont considérés être dans un unique saut de communication les

uns des autres.

La valeur minimale du compteur des sauts hi, qu‟un capteur i maintient représente finalement

la longueur du chemin le plus court vers la graine dans une communication à saut. Dans le

réseau de capteurs ad hoc proposé, un saut de communication a une distance physique

maximale r qui lui est associée. Cela implique qu'un capteur i est tout au plus de

distance rhide la graine.

Cependant, comme la densité moyenne des capteurs augmentent avec le même nombre de

sauts, cela va former des anneaux circulaires concentriques, de largeur environ r , autour du

capteur graine.

• Algorithme de multilatération: - Chaque capteur utilise une procédure multilatérale pour

combiner les estimations de distance de tous les capteurs afin de déterminer leurs propres

positions. Après avoir reçu au moins trois valeurs de gradient, les capteurs combinent les

distances à partir des graines afin d'estimer leur position relatives par rapport aux positions

des capteurs de graines. En particulier, chaque capteur estime ses coordonnées en minimisant

l'erreur carrée totale entre les distances calculées et les distances estimées. La distance

calculée du capteur j à la graine i est:

yyxxd jijiij

22

(4)

Et l‟erreur totale du capteur j est :

ddE jijij

^2

(5)

Dans l'équation (4) et l'équation (5), n est le nombre de capteurs de graines et d ji

^est la

distance estimée et calculée par la propagation du gradient. Les coordonnées sont ensuite

mises à jour progressivement et proportionnellement au gradient de l'erreur totale.


L'avantage de cet algorithme est qu'il peut être facilement adapté au cas d‟un ajout de capteurs,

des graines et aussi à la mort des capteurs ou des graines. Mais il faut avoir une densité

substantielle de nœuds avant que sa précision puisse atteindre un niveau acceptable. En plus,

ce nombre de sauts n‟est pas fiable dans les mesures parce que les obstacles de

l'environnement peuvent empêcher les bordures d'apparaître dans le graphe de connectivité,

comme le montre la figure 7. Dans la figure 7, le nombre de sauts de distance entre A et E est

de quatre sauts dus aux obstacles, mais la distance réelle est bien moins que quatre valeurs.

Figure 7 Erreur de saut due à la présence d’obstacles

IV.2. Algorithme distribué basé sur la relaxation

IV.2.1. Modèle de ressort

Dans [12] les auteurs proposent un algorithme de localisation sans ancre (AFL :

Anchor Free Localization) où les nœuds s‟initialisent à partir d'une affectation aléatoire des

coordonnées et convergent vers une solution cohérente en utilisant seulement des interactions

du nœud local. L'algorithme dans son principe se compose de deux phases et suppose que les

nœuds sont comme des masses ponctuelles liées à des chaînes et utilisent des méthodes de

relaxation fortement dirigée à converger à une configuration d'énergie minimale.

La première phase est une heuristique qui produit un assemblage graphique qui ressemble à

l'assemblage d'origine. Les auteurs supposent que chaque nœud possède un identifiant unique

et l'identifiant du nœud i est notée par iID et le nombre de sauts entre les nœuds i et j est le


nombre de nœuds jih , le long du plus court chemin entre i et j .L'algorithme choisit d'abord les

cinq nœuds de référence dans lesquels quatre noeuds n1, n2

, n3et n4

sont choisis de sorte

qu'ils soient à la périphérie du graphe et la paire nn 21, est sensiblement perpendiculaire à la

paire nn 43, . Le noeud n5

est sélectionné de sorte qu'il soit au milieu du graphique. Au

début, le nœud avec le plus petit ID est sélectionné. Ensuite, le nœud de référence n1est

choisi pour maximiser 2,1h . Après avoir sélectionnén3 afin de minimiser hh 3,23,1

et la règle

bris d'égalité permettant de choisir le nœud qui minimise hh 3,23,1 . Dans la prochaine étape,

le nœudn4est choisi pour minimiser hh 4,24,1

et les liens sont rompus en cherchant le nœud

qui maximise 4,3h . Le nœud suivantn5est sélectionné et on minimise hh 5,25,1

et à partir des

nœuds concurrents on cherche le nœud qui minimise hh 5,45,3 . Ainsi le noeud n5

est le

centre du graphe et les nœudsn1,n2

,n3,n4

deviennent la périphérie du graphe.

Maintenant, pour tous les nœuds ni, les heuristiques utilisent le comptage de saut h1,i, h2,i, h3,i,

h4,i, et h5,i à partir des nœuds de référence choisi pour rapprocher les coordonnées polaires

ii, où :

Rh ii

,5 (7)

hhhh iiiii ,4,3,2,1

1 /tan

(8)

et R est la portée radio maximale.

Dans la première étape, lorsqu‟on calculek, l'utilisation de la portée R pour représenter un

saut résulte dans un graphe qui est physiquement plus grand que le graphe original et cette

erreur peut être éliminée par l'étape suivante.

Dans la deuxième phase, chaque nœud nicalcule la distance estiméed ji

^

,à chaque voisinn j

et il connaît également la distance mesurée r ji,, au voisinn j

. Maintenant, si le vecteur v ji

^

,


représente le vecteur unité dans la direction de pi

^

à pj

^

( pi

^

et pj

^

sont les valeurs courantes

estimées de i et j respectivement). La force F ji,dans la direction v ji

^

, est donnée par :

rdvF jijijiji ,

^

,

^

,, (9)

et la force résultante sur le nœud i est donnée par :

ji jii FF , , (10)

L'énergie E ji,des nœuds ni

etn jdue à la différence entre les distances mesurées et estimées

est l‟effet de l'amplitude de F ji,, dans la directionv ji

^

,qui est égale à :

jj jii rdEE jiji ,

^,

2

, (11)

Et l'énergie totale du système E est donnée par :

j iEE (12)

Maintenant, l'énergie E ide chaque noeud ni

est réduite lorsqu‟il se déplace par une quantité

infinitésimale dans la direction de la force F i. Dans l'optimisation, l'amplitude des F i

pour

chaque nœudniest nulle et l'énergie globale du système E est également zéro et l'algorithme

converge.

Des simulations approfondies montrent que l'algorithme proposé peut être en mesure de

converger vers des positions correctes et est nettement plus robuste aux erreurs d'estimation

de distance locale [13]. La limitation de cette approche est que l'algorithme est sensible aux

minima locaux.

IV.2.2. Approche coopératives des portées

Dans [13], les auteurs décrivent une approche coopérative des portées basée sur les

suppositions de la base des coordonnées (ABC : Assumption Based Coordinate) comme

primitive pour résoudre le problème de localisation. L‟algorithme ABC détermine

l'emplacement des nœuds inconnus en faisant des hypothèses quand c‟est nécessaire et

compense les erreurs par des corrections et des calculs redondants une fois que d'autres


renseignements sont disponibles. L'algorithme commence avec l'hypothèse suivante : le

noeud n0est situé à 0,0,0 . On suppose que n1

est le premier nœud pour établir une

communication avec n0et est supposé être situé à 0,0,

01r où r01est la distance RSSI

entre n0et n1

. L'emplacement du prochain nœud n2 zyx 222

,, peuvent être obtenus en se

basant sur deux hypothèses: y2

est positive et 02z , donc :

rrrrx 01

2

12

2

02

2

0122/ (13)

xry2

2

2

022 (14)

La prochaine position den3peut être déterminée en supposant que 0

3z , alors :

rrrrx 01

2

13

2

03

2

0132/ (15)

yxxyxrry232

2

2

2

2

2

23

2

0332/2

(16)

yxrz2

3

2

3

2

033 (17)

À partir de ce moment là, le système d‟équations utilisé pour résoudre n'est plus sous-

déterminé et ainsi l'algorithme standard peut être appliqué pour chaque noeud et ses voisins.

Après, les auteurs proposent une approche de portée coopérative qui exploite la haute

connectivité du réseau pour traduire le défi de positionnement global en un certain nombre de

problèmes de positionnement localement distribués qui convergent itérativement vers une

solution globale en interagissant les uns avec les autres. Dans l'approche proposée, chaque

noeud seul joue le même rôle répétitivement et exécute concurremment les fonctions

suivantes :

• Recevoir l'information de la portée et de la position des nœuds voisins.

• Résoudre le problème de localisation locale par l'algorithme ABC.

• Transmettre les résultats obtenus aux noeuds voisins.

Après quelques itérations répétitives, le système converge vers une solution globale.

L'avantage de cette approche est qu‟aucunes ressources globales ou communications ne sont


nécessaires. L'inconvénient est que la convergence peut prendre un peu de temps et que la

couverture des nœuds qui ont une mobilité élevée peut être difficile.

IV.3. Pointage d’un système de coordonnées

Figure 8 (a) ambigüité de symétrie (b) ambigüité de discontinuité

IV.3.1. Approche basée sur le cluster

Dans [14], les auteurs proposent un algorithme distribué pour la localisation des nœuds dans

un réseau de capteurs dans lequel les nœuds ont la capacité d'estimer la distance aux noeuds

voisins. Avant de décrire l'algorithme, nous devons savoir la distinction entre les graphes

souples et rigides.

Les graphes souples peuvent être déformés en permanence pour produire un nombre infini de

réalisations différentes, tandis que les graphiques rigides ne peuvent pas. Cependant, dans les

graphes rigides, il existe deux types de déformations discontinues qui peuvent empêcher une

réalisation d'être unique.

• Les ambiguïtés de symétrie se produisent pour un graphique dans un espace à d-dimensions

lorsque les positions de tous les voisins d‟un certain sommet couvrent un sous-espace de

dimension (d-1). Dans ce cas, les voisins créent un miroir à travers lequel le sommet peut être

reflété. Comme la montre la Fig. 8 (a), le sommet A peut être reflété à travers la ligne reliant

B et C, sans changement dans les contraintes de distance.


• Les ambiguïtés de discontinuités se produisent lorsqu‟on supprime un bord et ceci permet à

une partie du graphe d'être fléchie pour une configuration différente. Comme dans la figure

Fig.8 (b) la première AD est retiré, puis remis en place, le graphe peut fléchir dans la direction

de la flèche, en prenant une configuration différente, mais conserve toutes les contraintes de

distance.

L'algorithme est essentiellement constitué de deux phases. La phase 1 est la localisation de

cluster où chaque nœud devient le centre du faisceau et estime les positions relatives de ses

voisins pouvant être localisés sans ambiguïté. Pour chaque cluster, tous les quadrilatères

robustes ainsi que le plus grand graphe secondaire sont identifiés. Les auteurs définissent des

triangles robustes qui vérifient :

dBmin

2sin (18)

Dans l'équation (18), b est la longueur du côté le plus court et est le plus petit angle et d min

est le seuil basé sur le bruit mesuré. Si un quadrilatère a quatre triangles robustes secondaires,

alors ce quadrilatère est un quadrilatère robuste. L'algorithme commence avec un quadrilatère

solide et lorsque deux quadruples ont trois nœuds en commun et le premier quadruples est

entièrement localisé, le deuxième quadruples peut être localisé par trilatération des trois

positions connues.


Figure 9 Topologie réseau avec des distances inter-nodes

Dans la deuxième phase c.-à-d. la transformation de cluster, la position de chaque noeud dans

chaque système de coordonnées locales sont partagées. Tant qu'il y a au moins trois nœuds

non-alignés en commun entre les deux localisations, la transformation peut être calculée par

rotation, translation, la réflexion.

L'avantage de ce système est que la localisation basée sur les clusters supporte l'insertion et la

mobilité dynamique de nœuds. La limitation est que sous la condition de faible connectivité

des nœuds ou d‟un bruit de mesure élevé, l'algorithme peut être incapable de localiser un

nombre utile de noeuds.

IV.3.2. Construction du système de coordonnées global dans un réseau de nœuds de

calcul statique à partir d’une Distance Inter Nœud :

Dans [15], les auteurs proposent un algorithme qui est basé sur un système de coordonnés de

points qui construit une carte spatiale et une matrice de distance, puis tente de minimiser les

contradictions entre elles par translation, rotation et la réflexion. La matrice de distance est

expliquée à l'aide de la figure. 9. et la figure. 10. Dans la figure. 9 une collection des nœuds et

des distances estimées entre certaines paires de ces nœuds a été démontrée. Une matrice de

distance d'un nœud individuel peut acquérir un sous-ensemble de distances estimées. Ainsi, la

matrice de distance pour le nœud 2 est représentée sur la figure. 10 (a). La matrice de distance


de deux nœuds différents peut se chevaucher comme sur la Fig. 10 (b). Maintenant, pour

construire la carte spatiale à partir d'une matrice de distance, nous avons besoin de construire

une première carte contenant un triangle de trois noeuds voisins deux à deux non-alignés. Puis

plusieurs nœuds sont insérés dans la carte, une à la fois, basée sur les distances aux noeuds

déjà dans la carte, dans un processus itératif de sorte que le nœud doit avoir au moins trois

nœuds voisins non-alignés. Le processus se termine quand tous les noeuds sont insérés dans la

carte ou quand aucun nœud non inséré ne peut l‟être.

Figure 10 (a) matrice des distances entre nœuds (b) Chevauchement locale des cartes

Maintenant, pour calculer la carte initiale, nous devons trouver le côté le plus long et désigner

son nœud final comme p et r , puis aligner ce côté avec l'axe des abscisses x par réglage de la

position p à 0,0 et la position r à 0,Dpr. Ensuite, on choisit n'importe quel troisième

noeud q dont la position est yx, où DDDD prqrprpqx

22222 et xDpr

y22

(comme

le montre la figure 11). Ensuite à chaque itération, un noeud avec le plus grand nombre de

voisins déjà dans la carte est choisi pour l'insertion et le processus s'arrête lorsqu‟aucun autre

nœud non cartographié ne peut être trouvé avec au moins trois voisins mappé qui sont non-

colinéaires.


Figure 11 Carte initiale

Toujours dans [15], les auteurs discutent le processus pour réconcilier deux cartes qui ont au

moins certains nœuds en commun, mais qui diffèrent sur la position de ces nœuds communs

par rotation, translation et de réflexion. Quand un noeud a une distance estimée suffisante, il

diffuse localement une carte de son voisinage. Quand un nœud reçoit une carte à partir d'un

voisin, il réconcilie sa propre carte avec son voisin et diffuse sa propre carte. De cette façon,

chaque nœud doit acquérir rapidement une carte de son voisinage. Finalement, cet accord

devrait s'étendre à travers le réseau de sorte qu'un système de coordonnées commun soit

formé.

L'avantage de ce système est qu'il ne nécessite pas de nœuds ancres ou balises pour la

localisation. Mais dans le modèle de communication traditionnel, où les noeuds peuvent

communiquer uniquement avec les voisins, cet algorithme peut converger très lentement à

partir d‟un seul système de coordonnées qui doit se propager à partir de sa source jusqu‟à

l'ensemble du réseau.

IV.4. Localisation hybride

IV.4.1. Schéma de localisation composé MDS et PDS

D‟autres auteurs [16] présentent un schéma de localisation composé de deux

techniques de localisation : graduation multidimensionnelle (MDS) et carte basée sur la

proximité (PDM). Au début, certaines ancres sont déployées et enregistrées comme des ancres

primaires. Dans la première phase, certains capteurs sont choisis comme des ancres

secondaires qui sont localisées à travers la graduation multidimensionnelle. Les nœuds qui ne


sont ni ancres primaires, ni secondaires sont appelés capteurs normaux. Dans la deuxième

phase, les capteurs normaux sont localisés grâce à la cartographie de distance de proximité.

Dans la première étape, chaque ancre primaire envoie un paquet d‟invitation contenant son

numéro d'identification unique, un compteur est initialisé à zéro et une valeur k scontrôle le

nombre d'ancres secondaires, à l'un de ses voisins. Le capteur normal qui reçoit ce paquet

effectuera une épreuve de Bernoulli avec un taux de réussite de P . Si le résultat est vrai, le

capteur normal incrémente le compteur par un et devient une ancre secondaire. Le paquet sera

expédié à un autre voisin jusqu'à ce que le compteur soit égal à k s. Après l'envoi du paquet

d‟invitation, chaque ancre primaire envoie des paquets contenant son ID unique et ses

coordonnées à tout l'ensemble de ses voisins. Le paquet porte également un champ marquant

la proximité, c-à-d. le décompte de la distance ou le saut que le paquet a parcouru. La valeur

est initialisée à zéro. Les ancres secondaires feront également ce que les ancres primaires font,

en envoyant des paquets avec leurs identificateurs uniques mais en laissant vide les champs

des coordonnées.

Chaque noeud (y compris les ancres) recevant un paquet de proximité d'une ancre (primaire

ou secondaire) va stocker son ID et la valeur de proximité. Si un paquet à partir d‟une ancre

particulière a été reçu avant, le nœud examine la proximité et vérifie si sa valeur est plus

grande que la valeur de proximité stockée.

Si cette valeur est supérieure à la valeur stockée, le paquet sera jeté. Sinon, la valeur stockée

et le champ de proximité du paquet seront mis à jour et le paquet sera transmis à d'autres

voisins. Ainsi, la proximité stockée reflète toujours la distance du plus court chemin ou le

nombre des sauts à partir d'une ancre particulière. Ensuite, une ancre découvre ses proximités

par rapport à toutes les ancres, elle enverra les proximités qu'elle a recueillies à d'autres ancres

et attend que d'autres ancres réalisent la même chose. Lorsque toutes les ancres distribuent les

proximités à leurs homologues, chaque ancre connaît l'information de proximité entre chaque

paire d‟ancres. Chaque ancre secondaire peut maintenant déterminer sa position par MDS

classique.

Après la première phase, chaque ancre secondaire connaît aussi les positions estimées des

autres ancres secondaires comme le MDS offre une configuration sur les ancres primaires et


secondaires et calcule la cartographie distance de proximité. La cartographie et les positions

estimées des ancres secondaires obtenues à partir de la première phase sont distribuées aux

nœuds normaux avoisinant. Le capteur normal utilise la cartographie normale pour traiter le

vecteur de proximité qu'il a stocké. Enfin, la position du nœud est calculée par multilatération

avec le vecteur de proximité traité et les informations de position des ancres primaires et

secondaires.

L'avantage principal de ce système est de minimiser le coût de calcul. Pour MDS classique, la

complexité est nO3

, où n est le nombre de nœuds. La complexité de la PDM

est mO3

où m est le nombre d'ancres. Mais ce système composé de MDS et PDM a une

complexité de mxO

3oùmx

est le nombre total des ancres primaires et secondaires. Donc, en

gardant mxcomme un nombre raisonnable, la complexité peut être similaire à la complexité

de PDM. La limitation de cette méthode est qu'elle ne fonctionne pas bien quand il n'y a que

quelques ancres.

IV.4.2. Positionnement absolu-relatif hybride simple (SHARP)

Le positionnement absolu relatif hybride simple (SHARP) est un technique de

localisation présentée dans [17]. Il utilise la graduation multidimensionnelle (MDS) et le

System de positionnement Ad-hoc (APS) pour la localisation.

Le schéma de localisation se compose de trois phases. Dans la première phase, un ensemble

de nœuds de référence sont choisis aléatoirement sur le long du périmètre extérieur du réseau.

Dans la deuxième phase, une méthode relative de localisation MDS est utilisée pour localiser

relativement les noeuds de référence choisis dans la première phase.

A la première distance du plus court chemin entre chaque paire, des noeuds de

référence sont calculées puis MDS est appliqué à la construction de la carte relative. Le

résultat de la première et la deuxième phase est un ensemble des nœuds ayant les coordonnées

connues à partir de certaines coordonnées du système. En troisième phase, une méthode de

localisation absolue APS est utilisée pour localiser le reste des nœuds dans le réseau en


utilisant les nœuds de référence comme des ancres. Chaque noeud utilise les informations de

distance du plus court chemin pour estimer ces distances aux ancres. Puis, il exécute la

multilatération pour estimer sa position.

SHARP exécute MDS dans deux cas : l'erreur de localisation et le coût sont pris en

considération. La limitation de ce système est que pour les réseaux anisotropes, SHARP

donne un mauvais rendement.

IV.4.3. Schéma de localisation composé des deux approches inductive et déductive

Dans [27], les auteurs présentent un schéma de localisation pour l'environnement indoor. Il

existe deux méthodes principales pour estimer la position dans les environnements indoor.

D'une part, il y a les méthodes dites déductives. Celles-ci prennent en compte les propriétés

physiques de la propagation du signal. Elle exige un modèle de propagation, des informations

topologiques sur l'environnement, et la position exacte des stations de base. D'autre part, il y a

les méthodes dites inductives. Celle-ci exige une phase de formation antérieure

d‟apprentissage, où le système apprend la puissance du signal à chaque endroit.

L‟inconvénient principal de cette approche est que la phase d‟apprentissage peut être très

coûteuse. La complexité de l'environnement indoor rend le fait d‟avoir un bon modèle de

propagation une tâche très difficile. Il est difficile d'améliorer les méthodes déductives quand

il y a de nombreux murs et d‟obstacles parce que les méthodes déductives fonctionnent en

estimant mathématiquement la position à partir des vraies mesures prises directement de

l'environnement dans la phase d‟apprentissage.

Dans [27], les auteurs présentent un système de localisation hybride utilisant une nouvelle

approche stochastique basée sur une combinaison de méthodes déductives et inductives.

L'avantage de cette méthode est qu‟elle couvre un environnement indoor dur sans avoir

beaucoup de stations de base. Par ailleurs, cette technique permet de réduire la phase

d„apprentissage sans perte de précision.


IV.5. Localisation basée sur l’interférométrie

L'idée derrière le système de positionnement radio interférométrique (RIPS) proposé dans

[18], [19], [20] est d'utiliser deux émetteurs pour créer directement le signal d'interférence. Si

les fréquences des deux émetteurs sont presque les mêmes, le signal composite aura une

enveloppe de basse fréquence qui peut être mesurée facilement par un matériel simple et pas

cher disponibles sur un nœud WSN. Mais en raison du manque de synchronisation des noeuds,

il y aura une phase relative qui cherche à décaler le signal et la fréquence porteuse des deux

récepteurs en fonction des positions relatives des quatre nœuds impliqués.

En effectuant des mesures multiples, il est possible de reconstituer la position relative des

nœuds en 3D. Mais la localisation à l'aide de la portée interférométrique est un problème NP-

complet [20]. Afin d'optimiser la solution au niveau globale, les auteurs de [18] utilisent une

approche basée sur un algorithme génétique, tandis que [19] réduit l'espace de recherche avec

des lectures supplémentaires du RSSI.

Par rapport aux techniques les plus communes telles que la puissance du signal reçu, le temps

d‟arrivée, et l'angle d'arrivée, la portée interférométrique a l'avantage de donner des mesures

très précises. Mais la localisation en utilisant l'interférométrie exige un ensemble important de

mesures ce qui limite leurs solutions pour les petits réseaux (16 nœuds [18] et 25 nœuds [19]).

Pour résoudre ce problème un algorithme itératif a été proposé dans [20], qui calcule la

position des nœuds d'un ensemble d'ancres et construit graduellement une solution de

localisation globale. Par rapport à [18] et [19], qui traitent la localisation comme un problème

d'optimisation globale, l'algorithme itératif est un algorithme distribué qui est simple à mettre

en œuvre dans les grands réseaux.

IV.6. Propagation des erreurs au cours de la localisation

Un algorithme de propagation de l'erreur courante (EPA) a été proposé dans [21], qui intègre

la perte due au multi-trajets et le modèle d'erreur de la distance mesurée. Au début de

l'algorithme, les nœuds ancres diffusent leurs informations, qui comprend leur ID unique,

leurs coordonnées globales, et la variance de l'erreur de position2

p. Chaque nœud écoute le


canal et enregistre les informations TOA au niveau de chaque ancre. La puissance de la

trajectoire directe détectée est traduite en une variance de portée2

r. Après avoir

2

ret

2

p le

nœud capteur construit la matrice de pondération donnée par l'équation (19).

WW prW (19)

22

1,.....,

rnrrdiagW et

22

1,.....,

pnppdiagW de n mesures de puissance jusqu‟aux

ancres. Dans la phase suivante, le nœud calcule sa position en intégrant sa matrice de

pondération dans l‟algorithme des moindres carrés pondérés (WLS). Après avoir obtenu sa

propre position, le nœud capteur devient une ancre et commence à diffuser son identité, ses

coordonnées globale et2

p. Ce processus est répété jusqu'à ce que tous les nœuds obtiennent

leurs positions et se transforment en ancres.

L'algorithme trouve son avantage dans l‟obtention des informations de portée et de

position à partir de chaque ancre impliquée et donc il résulte une estimation plus précise que

d'autres méthodes de localisation.


Conclusion générale

La performance de n'importe quel algorithme de localisation dépend d'un certain

nombre de facteurs [28], tels que la densité des nœuds ancres, la densité des noeuds, les coûts

de calcul et de la communication, la précision du système. Toutes les approches ont leurs

propres avantages et inconvénients, les rendant ainsi adaptés à différentes applications.

Certains algorithmes nécessitent des balises (Diffusion, zone de délimitation, Gradient, APIT)

et d'autres pas (MDS-MAP). Les algorithmes sans balises produisent un système de

coordonnées relatif qui peut éventuellement être inscrit à un système de coordonnées global.

Parfois, les réseaux de capteurs ne nécessitent pas de système de coordonnées global. Dans

ces situations, les algorithmes sans balises suffisent.

Certains algorithmes sont centralisés alors que d'autres sont distribués. Les algorithmes

centralisés calculent généralement des positions plus précises et peuvent être appliqués à des

situations où la précision est importante. D'autre part, les algorithmes distribués ne dépendent

pas de grand système centralisé et ont potentiellement une meilleure évolutivité. La durée de

vie de la batterie et le coût de la communication sont également importants pour les réseaux

de capteurs. Généralement les coûts de communication des algorithmes centralisés sont élevés

afin de déplacer les données vers la station de base. Cependant, la précision est également

élevée dans les systèmes centralisés par rapport aux approches distribuées. En outre, certaines

méthodes se comportent bien dans la densité élevée d'ancres alors que certains ont besoin

seulement de peu d'ancres. Comme il a était démontré dans [25], la multilatération a un coût

faible de calcul et de communication et en plus elle se comporte bien quand il y a beaucoup

d'ancres. D'autre part MDS-MAP a un coût plus élevé de calcul et de communication et

fonctionne bien quand il y a peu de nœuds ancrages.


Les axes de recherche porteurs dans la localisation basée sur les WSN

Il y a beaucoup d'activités de recherche visant à améliorer la précision de localisation dans les

réseaux de capteurs sans fil. Mais il ya aussi des problèmes intéressants ouvertes qui ont

besoin d'attention.

1- La Technique Interférométrique de localisation prenant en compte la propagation

d'erreur

La technique interférométrique a été récemment proposée comme un moyen possible de

localiser les réseaux de capteurs, car il donne des mesures précises que les autres techniques

courantes. Mais les résultats de simulation [20] indiquent que la propagation d'erreur peut

être un problème potentiellement important en interférométrie. Afin de localiser les grands

réseaux en utilisant l'interférométrie allant d'un petit ensemble d'ancres, les algorithmes de

localisation future nécessitent de trouver un moyen de limiter efficacement la propagation des

erreurs.

2- Algorithme robuste pour réseaux de capteurs mobiles:

Récemment il y a eu beaucoup de recherche sur l'utilisation de la mobilité dans les

réseaux de capteurs pour aider dans le déploiement initial de nœuds. Les capteurs mobiles

sont utiles dans cet environnement, car ils peuvent se déplacer à des endroits qui répondent

aux exigences de couverture de détection.

Des nouveaux algorithmes de localisation devront être développés pour répondre à ces nœuds

mobiles. Ainsi, l'élaboration d'un algorithme de localisation robuste pour les réseaux de

prochaine génération de capteurs mobiles est un problème ouvert à l'avenir.

3- Sécurité des réseaux de capteurs:

Les réseaux de capteurs sont souvent utilisés pour des applications militaires comme la

détection des mines terrestres, la surveillance du champ de bataille, ou de poursuite de cibles.

Dans ces environnements opérationnels uniques, un adversaire peut capturer et de

compromettre un ou plusieurs capteurs. L'adversaire peut maintenant jouer avec le nœud en

injectant du code malveillant, forçant le nœud à un mauvais fonctionnement, ou en extrayant


de l'information cryptographique détenue par le nœud afin de contourner les obstacles de

sécurité comme l'authentification et la vérification. Dans un modèle de localisation par balise,

puisque les capteurs ne sont pas capables de déterminer leur emplacement, ils n'ont aucun

moyen de déterminer quels nœuds de balise fournissent des informations de localisation

précises, qui sont vraies. Il pourrait y avoir des nœuds balise malveillants qui donnent des

informations de localisation fausses, des nœuds de capteurs qui les obligent à calculer la

localisation incorrecte. Cette situation, dans laquelle l'entité a plus d'informations que l'autre,

est appelée asymétrie de l'information. Pour résoudre ce problème, dans [22] les auteurs

proposent une technique Distribution Reputation Beacon Trust System (DRBTS), qui vise à

fournir un procédé par lequel les nœuds balise peuvent se surveiller mutuellement et fournir

des informations afin de connaître les nœuds inconnus enqui faire confiance. Des travaux de

recherche futurs sont nécessaire dans ce domaine.

4- Trouver le nombre minimal d'emplacements d‟ancre:

L‟approche localisation basée sur des ancres exige un ensemble de nœuds balise, avec des

emplacements connus. Ainsi, un système optimal et robuste serait d'avoir un nombre

minimum de balises dans une région. Des travaux supplémentaires sont nécessaires pour

trouver le nombre minimal d'emplacements où les balises doivent être placées de sorte que le

réseau entier peut être localisé avec un certain niveau de précision.

5- Trouver des algorithmes de localisation dans un espace tridimensionnel:

Il est techniquement impossible de déployer dans une zone plan absolue les réseaux de

capteurs dans un contexte d‟applications réel. Pour toutes sortes d'applications dans les

réseaux de capteurs une localisation précise est essentielle et passe par une mesure

géométrique réelle prenant compte de l‟aspect 3D des empalements des ancres. Ainsi, une

bonne localisation 3D peut être un axe de travaux futurs.


References

[1] J.Li, J. Jannotti, D. S. J. DeCouto, D. R. Karger and R. Morris, “A Scalable Location Service for Geographic

Ad-Hoc Routing”, in Proceedings of Sixth Annual International Conference on Mobile Computing and

Networking, August 2000, Boston, Massachusetts, USA, pp. 120-130.

[2] K. Amouris, S. Papavassiliou, M. Li, “A Position-Based Multi-Zone Routing Protocol for Wide Area Mobile

Ad-Hoc Networks”, in Proceedings of IEEE Vehicular Technology Conference (VTC ‟99), May 1999, Houston,

Texas, USA, Vol. 2, pp.1365-1369.

[3] M. Mauve, J. Widmer and H. Hartenstein, “A Survey on Position Based Routing in Mobile Ad-hoc

Networks”, IEEE Network Magazine, vol. 15, no. 6, pp. 30–39, November 2001.

[4] M. B. Srivastava , R. Muntz and M. Potkonjak, “Smart Kindergarten: Sensor-based Wireless Networks for

Smart Developmental Problem-solving Environments”, In Proceedings of Seventh Annual Inernationatl

Conference on Mobile Computing and Networking, July 2001, Rome, Italy, pp. 132-138.

[5] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, “Localization from mere connectivity”, In Proceedings of

ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc‟03), June 2003, Annapolis,

Maryland, USA, pp. 201-212.

[6] Anushiya A Kannan, Guoqiang Mao and Branka Vucetic, “Simulated Annealing based Wireless Sensor

Network Localization”, Journal of Computers, Vol. 1, No. 2, pp 15-22, May 2006.

[7] Cesare Alippi, Giovanni Vanini, “A RSSI-based and calibrated centralized localization technique for

Wireless Sensor Networks”, in Proceedings of Fourth IEEE International Conference on Pervasive Computing

and Communications Workshops (PERCOMW‟06), Pisa, Italy, March 2006,pp. 301-305.

[8] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, “Range-free localization schemes in large scale

sensor networks”, In Proceedings of the Ninth Annual International Conference on Mobile Computing and

Networking (MobiCom'03), September 2003, San Diego, CA, USA, pp.81-95.

[9] A. Savvides, H. Park, and M. Srivastava, “The bits and flops of the n-hop multilateration primitive for node

localization problems”, In Proceedings of the 1st ACM international Workshop on Wireless Sensor Networks

and Applications (WSNA'02), September 2002, Atlanta, Georgia, USA, pp. 112-121.

[10] S. Simic and S. Sastry, “Distributed localization in wireless ad hoc networks”, Technical Report UCB/ERL

M02/26, UC Berkeley, 2002, Available HTTP:

http://citeseer.ist.psu.edu/simic01distributed.html.


[11] J. Bachrach, R. Nagpal, M. Salib and H. Shrobe, “Experimental Results for and Theoritical Analysis of a

Self-Organizing a Global Coordinate System from Ad Hoc Sensor Networks”, Telecommunications System

Journal, Vol. 26, No. 2-4, pp. 213-233, June 2004.

[12] N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, “Anchor-free distributed localization in sensor

networks”, MIT Laboratory for Computer Science, Technical Report TR-892, April 2003, Available HTTP:

http://citeseer.ist.psu.edu/681068.html.

[13] C. Savarese, J. Rabaey, and J. Beutel, “Locationing in distributed ad-hoc wireless sensor

networks”, in Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing

(ICASSP'01), May 2001, Salt Lake City, Utah, USA, vol. 4, pp. 2037-2040.

[14] David Moore, John Leonard, Daniela Rus, and Seth Teller, “Robust distributed network localization with

noisy range measurements”, in Proceedings of the Second ACM Conference on Embedded Networked Sensor

Systems (SenSys'04), November 2004, Baltimore, MD, pp. 50-61. [15] Lambert Meertens and Stephen

Fitzpatrick, “The Distributed Construction of a Global Coordinate System in a Network of Static Computational

Nodes from Inter-Node Distances”, Kestrel Institute Technical Report KES.U.04.04, Kestrel Institute, Palo Alto,

2004, Available FTP:ftp://ftp.kestrel.edu/pub/papers/fitzpatrick/LocalizationReport.pdf.

[16] King-Yip Cheng, King-Shan Lui and Vincent Tam, “Localization in Sensor Networks with Limited Number

of Anchors and Clustered Placement”, in Proceedings of Wireless Communications and Networking Conference,

2007 (IEEE WCNC 2007), March 2007, pp. 4425 – 4429.

[17] A. A. Ahmed, H. Shi, and Y. Shang, “Sharp: A new approach to relative localization in wireless sensor

networks,” in Proceedings of IEEE ICDCS, 2005.

[18] M. Maroti, B. Kusy, G. Balogh, P. V olgyesi, A. Nadas, K. Molnar, S. Dora, and A. Ledeczi, “Radio

Interferometric Geolocation,” in Proceedings of 3rd International Conference on Embedded Networked Sensor

Systems (SenSys), pp. 1-12, San Diego, California, USA, Nov. 2005.

[19] N. Patwari and A. O. Hero, “Indirect Radio Interferometric Localization via Pairwise Distances,” in

Proceedings of 3rd IEEE Workshop on Embedded Networked Sensors (EmNets 2006), pp. 26-30, Boston, MA,

May 30-31, 2006.

[20] Rui Huang, Gergely V. Zaruba, and Manfred Huber, “Complexity and Error Propagation of Localization

Using Interferometric Ranging”, in Proceedings of IEEE International Conference on Communications ICC

2007, pp. 3063-3069, Glasgow, Scotland, June 2007.

http://citeseer.ist.psu.edu/681068.html


[21] N. A. Alsindi, K. Pahlavan, and B. Alavi, “An Error Propagation Aware Algorithm for Precise Cooperative

Indoor Localization”, in Proceedings of IEEE Military Communications Conference MILCOM 2006, pp. 1-7,

Washington, DC, USA, October 2006.

[22] A. Srinivasan, J. Teitelbaum, J. Wu. DRBTS, “Distributed Reputation-based Beacon Trust System”, 2nd

IEEE International Symposium on Dependable, Autonomic and Secure Computing (DASC ‟06), September

2006, Indianapolis, USA, pp. 277-283.

[23]J. Bachrach and C. Taylor, "Localization in Sensor Networks," in Handbook of Sensor Networks:

Algorithms and Architectures, I. Stojmenovic, Ed., 2005.

[24] Available HTTP : http://www.cse.ust.hk/~yangzh/yang_pqe.pdf.

[25] Yi Shang, Hongchi Shi and A. Ahmed, “Performance study of localization methods for ad-hoc sensor

networks”, in proceedings of IEEE International Conference of Mobile Ad-hoc and Sensor Systems, Fort

Lauderdale, FL, October 2004.

[26] Eiman Elnahrawy, Xiaoyan Li and Richard P. Martin, “ The Limits of Localization Using Signal Strength:

A Comparative Study, in Proceedings of IEEE SECON, pp. 406-414, Santa Clara, California, USA, October

2004.

[27] Jaime Lloret, Jesus Tomas, Miguel Garcia, Alejandro Canovas, “A Hybrid Stochastic Approach for Self-

Location of Wireless Sensors in Indoor Environments” Sensors 9, no. 5: 3695-3712.

[28] A.Pal, “Localisation Algorithms in Wireless Sensor Networks”, Network Protocols and Algorithms, Vol. 2,

No. 1- 2010.

Documents

Etat De L\'art Algo RéSeaux De Capteurs sans-fil