Discussion :

[bazoga]

Bonjour,

Je cherche à développer une application de localisation dans les réseaux de capteurs, une partie de cette application est basée sur un algorithme de sélection des nœuds.

Au début plusieurs capteurs sans fils (nœuds) sont dispersés aléatoirement dans une zone géographiques. Parmi ces nœuds il existe quelques uns qui connaissent leurs positions (équipes de GPS) et contribuent à l'estimation de la position des autres.

Ensuite chaque nœud envoie une requête de localisation et reçoit plusieurs réponses provenant des nœuds équipes de GPS et des autres qui ont déjà estimé leurs positions.

Pour une estimation de bonne précision, je choisi en priorité les réponses provenant des nœuds GPS suivi des nœuds qui ont servi directement des nœuds GPS suivi des autres avec un intermédiaire (sans GPS) de plus et ainsi de suite.

l'erreur d'estimation s'accumule à chaque fois qu'on utilise un nœuds non équipe de GPS.

voila un exemple qui illustre la selection :



le nœud n1 a reçu 4 réponse provenant de B1 , B2 , n2 et n4, l'estimation nécessite 3 nœuds donc je choisi B1 , B2 (sans erreurs) et n4 (n4 a un niveau de moins par rapport n3).

Je veux attribuer un poids à chaque nœud, à base duquel je sélectionne les nœuds.

toute remarque sera la bienvenue.

Cordialement
E. Bazoga

[Flodelarab]

Bonjour

Comme d'habitude, ton message ne contient pas de point d'interrogation donc il n'y a pas de question.

J'ai quand même une remarque. Tu as deux choses bien différentes:

• La localisation
• Le taux de confiance de la localisation.

Tu peux affecter des probas à chaque branche pour calculer les niveaux de confiance.

[m_piou]

Bonjour,

Un élément me manque. Est-ce que tu inclus une notion de distance lorsqu'un noeud GPS répond à un autre?
En fait je ne voit pas en quoi cela va aider pour un nœud sans GPS de savoir où sont les noeuds GPS? Seuls les plus proches répondent?

A ++

[bazoga]

Un élément me manque. Est-ce que tu inclus une notion de distance lorsqu'un noeud GPS répond à un autre?

un nœud répond en envoyant ses coordonnées.

En fait je ne voit pas en quoi cela va aider pour un nœud sans GPS de savoir où sont les noeuds GPS?

en utilisant la propagation des ondes radio, le nœud calcule la distance ensuite il estime sa position à travers la triangularisation ou multilatération.

Seuls les plus proches répondent?

Parmi ceux qui répondent, lesquels vais-je choisir ? aléatoirement !!! possible mais je veux trouver ma solution pour soutenir

[Flodelarab]

En reprenant son schéma, et en imaginant que la position soit sure à 100% venant d'un noeud avec GPS et 70% venant d'un noeud sans GPS, le point n4 aura une position sure à 49% (70%x70%). Sans changer la localisation.

Une autre façon de corriger peut être de dessiner un point venant d'un gps et une zone venant d'un non-GPS. Mais là, ça peut vite devenir très compliqué.

[souviron34]

Moi je ferais une triangulation de Delaunay avec les GPS, et à partir de là je saurai dans quelle cellule je me trouve.

Et par conséquent le poids des non-GPS serait affecté de la distance en terme de cellules.. Ceux qui ont déjà calculé leurs positions dans les cellules adjacentes disont 70%, et ainsi de suite avec un facteur dégressif..

Chaque cellule aura une triangulation exacte, basée sur 3 points, et donc permet de faire une interpolation exacte. A partir de là on ne prend en compte que les non-GPS déjà positionnés à l'intérieur de cette cellule, pour raffiner.. Et eventuellement ceux des cellules voisines seulement.

[bazoga]

Moi je ferais une triangulation de Delaunay avec les GPS, et à partir de là je saurai dans quelle cellule je me trouve.

... A partir de là on ne prend en compte que les non-GPS déjà positionnés à l'intérieur de cette cellule, pour raffiner.. Et eventuellement ceux des cellules voisines seulement.

Merci pour l’intérêt que vous avez porté à ma question. en fait le nombre des nœuds équipés d'un GPS est très réduit, donc on est obligé, dans certain cas, de passer pas des nœuds non GPS.

voila à ce que je pense :

1: j'attribue un poids w à chaque nœud référence (position connue)
2: le poids des nœud GPS est égale à 0
3: le poids des autres nœuds références non GPS est égale à la moyenne (plus 1) des poids des nœuds références qui ont contribué à l'estimation de sa position.
4: quand un nœud reçoit plusieurs réponses, il choisi ceux qui ont un poids minimal pour estimer sa position.

Qu'est ce que vous en pensez ?

[Flodelarab]

Poids Valeur
1 12
2 24
3 23
3 23
7 25
10 24

A mon avis, dans l'exemple ci-dessus, le poids le plus faible a buggué. La valeur vraie est plus 24 que 12.

[bazoga]

Poids Valeur
1 12
2 24
3 23
3 23
7 25
10 24

Désolé je n'ai pas compris d'ou vient ces valeurs ??!!
Dans l'exemple ci dessous n1 n'a pas encore choisi ses trois références pour estimer sa position, donc il calcule le poids des noeuds b1 b2 n2 n4 :

w(b1)=w(b2)=0
w(n2)=w(n4)/3+1 =4/9+1 = 13/9 = 1.44
w(n4)=w(n3)/3+1 = 1/3+1=4/3 = 1.33
w(n3)=1

donc les nœuds sélectionnés sont : b1 , b2 et n4. ce qui ne contredit pas avec le principe de l'accumulation des erreurs.



Cordialement
E. Bazoga

[Flodelarab]

Désolé je n'ai pas compris d'ou vient ces valeurs ??!!

Elles viennent de nulle part. C'est pour illustrer que choisir un champion n'est pas la meilleure idée car il peut avoir un bug.

Un exemple en image:


4 points: A, B, C, D
L'information de distance, envoyée par A, est clairement à la ramasse, comparée aux informations de distance indiquées par les autres points, qui désignent tous, à peu près le même endroit.
Maintenant, imagine que A ait le plus gros poids. Auras-tu la meilleure localisation ?

[DonQuiche]

En premier lieu je calcule un rectangle englobant tous les cercles. Peu importe s'il est trop grand, ça ne fera que nous ralentir un peu.

Je divise ce rectangle en quatre et je calcule pour chaque sous-rectangle le nombre de cercles qui y cohabitent (inscrits OU intersectant). Je retiens le plus peuplé et je le redivise en quatre. Et ainsi de suite jusqu'à avoir moins de trois cercles dans le rectangle. La position désirée est quelque part dans le rectangle parent.

[bazoga]

Elles viennent de nulle part. C'est pour illustrer que choisir un champion n'est pas la meilleure idée car il peut avoir un bug.
.... Auras-tu la meilleure localisation ?

Merci pour l'exemple. En fait, la précision de la localisation est influencée à cause de trois facteurs :
1: Le calcul de l'estimation de la position => vient du nœud lui-même.
2: La position d'un nœud référence ==> vient du nœud référence (tend vers 0 pour les GPS).
3: La mesure de la distance entre le nœud et la référence utilisé.

Donc si on sélectionne comme référence les nœuds les plus proches alors on traite seulement le facteur n°3 et on ignore les 2/3 du problème non optimisé.