Embed Size (px)
Citation preview
06-07
Localisation dans un réseau de capteurs. TER Master Informatique Première Année
Vivien RAOUL Nicolas SIBUT Laurent SOULIS Pierre-Emmanuel VIVER
Nous tenons à remercier nos tuteurs MM. Clément SAAD, Jean‐Claude KÖNIG pour leur soutien sans faille et leur bonne humeur. Nous remercions M. Alain FOUCARAN pour la confiance qu’il nous a accordée et la mise à notre disposition d’une salle de travail. Nous le remercions aussi, ainsi que les personnes travaillant à la manade du TERNEN pour nous avoir prêté un terrain et du matériel. Nous remercions enfin l’entreprise CORONIS pour le prêt de matériel.
Sommaire 1 Introduction.......................................................................................................... 4 2 Méthode AT-Dist ................................................................................................. 5
2.1 Avant-propos.................................................................................................. 5 2.2 Méthode AT-Dist ............................................................................................ 7
2.2.1 Estimation de distance entre une ancre et un capteur........................... 7 2.2.2 Principe général..................................................................................... 7 2.2.3 Représentation ...................................................................................... 8
2.3 Les règles .................................................................................................... 10 2.3.1 Règle une ............................................................................................ 10 2.3.2 Règle deux .......................................................................................... 11 2.3.3 Règle trois ........................................................................................... 12 2.3.4 Processus de vote ............................................................................... 13
3 Expérimentations............................................................................................... 14 3.1 Présentation................................................................................................. 14 3.2 Prise en main du matériel ............................................................................ 16 3.3 Correspondance RSSI-Mètres ..................................................................... 18 3.4 Divers réseaux expérimentaux..................................................................... 20
3.4.1 Conditions à respecter......................................................................... 20 3.4.2 Protocole ............................................................................................. 21 3.4.3 Problèmes rencontrés ......................................................................... 22 3.4.4 Analyse................................................................................................ 23
3.5 Exploitation des données............................................................................. 23 4 Programmation de la méthode AT-Dist ............................................................. 24
4.1 Fonctionnement général .............................................................................. 24 4.2 Les besoins du programme.......................................................................... 25 4.3 L'utilisation d'une matrice ............................................................................. 26
4.3.1 Stockage de la matrice ........................................................................ 26 4.4 Barycentre, Epsilon, Zone de positionnement ............................................. 28 4.5 Les règles .................................................................................................... 29
4.5.1 Appels des règles ................................................................................ 29 4.5.2 Calcul des points possibles ................................................................. 30 4.5.3 Cas d'utilisation des règles .................................................................. 31
5 Intérêts et ouvertures......................................................................................... 32 5.1 Enjeux économiques.................................................................................... 32 5.2 Les versions futures et besoins.................................................................... 32
6 Conclusion......................................................................................................... 33 7 Annexes ............................................................................................................ 34
7.1 Diagramme UML.......................................................................................... 35 7.2 Caractéristique du cahier des charges......................................................... 36 7.3 Bibliographie ................................................................................................ 36 7.4 Webographie................................................................................................ 36 7.5 Atdist ............................................................................................................ 37
7.5.2 Capteur................................................................................................ 48 7.5.3 Carte.................................................................................................... 55 7.5.4 Cartographie........................................................................................ 61
3
1 Introduction
De nouvelles technologies comme le GPS (Global Positioning System) permettent de se localiser dans l’espace avec une précision accrue. Le besoin de se repérer dans de nombreux domaines (médical, militaire, humanitaire…) se fait de plus en plus ressentir, cependant l’utilisation de cette dernière technologie représente un coût d’investissement relativement important et une consommation d’énergie non négligeable. C’est pourquoi il apparaît indispensable de développer de nouveaux moyens permettant de se localiser tout en limitant les besoins humains et l’accès à ce type de technologie.
Pour répondre à cette attente, les travaux de M. Clément SAAD, doctorant au LIRMM (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier), ont abouti à la réalisation de deux méthodes (AT-Dist, AT-Free) permettant de se localiser précisément, grâce à un nombre réduit d’équipements connaissant leur position géographique.
En collaboration avec ce doctorant et M. Jean-Claude KÖNIG, nos tuteurs de projet de première année de Master Informatique du second semestre, nous tenterons de prouver par des expérimentations l’efficacité d’une de ces méthodes, AT-Dist, sur des réseaux de capteurs.
Avec le concours de nos encadrants du LIRMM et de M. Alain FOUCARAN, responsable à l’IES (Institut d’Electronique du Sud), nous avons pu travailler en partenariat avec l’entreprise CORONIS, spécialistes dans les communications par ondes hertziennes, qui nous a fourni du matériel.
Cette localisation est réalisée dans un réseau de capteurs, à l’aide des équipements prêtés par l’entreprise CORONIS, pouvant communiquer entre eux et capables d’estimer les distances séparant les uns des autres.
A partir des données expérimentales, nous devrons vérifier que notre application implémentant cette méthode retourne des résultats proches de la réalité.
Le positionnement dans une zone définie connaît un réel engouement dans le domaine de la recherche et constitue donc un véritable enjeu économique.
4
2 Méthode AT-Dist
2.1 Avant-propos
De nombreux domaines (application médicale, contrôle du climat, surveillance...) nécessitent une localisation précise d’équipements dans un réseau, ces derniers sont des capteurs. Ils ont les moyens de communiquer entre eux, et de connaître la distance qui les séparent les uns des autres.
L’entreprise CORONIS nous a prêté des modules de communications sur lesquels peuvent être connecté divers type de capteurs, leurs fonctionnement est décris dans la partie 3. Les solutions proposées doivent prendre en compte leurs caractéristiques. Ce sont de petits appareils dotés d’une batterie, capables de communiquer entre eux et de détecter des évènements s’ils se trouvent à l’intérieur de leur rayon de perception.
Il existe diverses méthodes permettant de résoudre le problème de localisation
de capteurs. En effet, en fonction de leur possibilité de calcul et du matériel utilisé, nous avons plusieurs possibilités, selon les informations mises à notre disposition :
Les rayons d’émission des capteurs. L’estimation de la distance entre chaque capteur. Les angles.
Nous avons travaillé dans le cas où chaque capteur est capable d’estimer la distance qui le sépare de ses voisins (les nœuds se trouvant dans son rayon d’émission/réception). Cette méthode est appelée AT-Dist
Dans cette partie nous détaillerons les diverses informations nécessaires à son fonctionnement.
Pour formaliser le problème, un réseau est représenté par un graphe dont les
nœuds symbolisent les capteurs. Ces capteurs ont un certain rayon d’émission et ne peuvent joindre
directement que les points situés dans ce rayon. Par commodité, sur tous les schémas, nous représenterons le voisinage par une arête. Chaque capteur communique donc avec ses voisins mais doit aussi être capable de calculer la distance qui le sépare d’eux. Il existe pour cela plusieurs méthodes :
RSSI (Received Signal Strength Indicator) est la méthode la plus connue. Le récepteur mesure la force du signal radio reçu et la convertit en distance.
ToA/TDoA (Time of arrival / Time difference of arrival) traduit directement le temps de propagation en distance si la vitesse de propagation du signal est connue. Le GPS par exemple emploie cette technique. Elle est donc utilisée pour des distances très grandes.
Il existe d’autres méthodes basées sur les angles permettant de calculer les
positions. Malheureusement, ces méthodes peuvent subir des perturbations dues à
l’environnement du réseau (e.g. présence d’obstacles).
5
Nous avons également besoin de connaître la position exacte de certains capteurs. Il existe pour cela diverses solutions : l’intervention humaine ou l’adjonction d’un GPS à ceux-ci leur permettent d’obtenir leur position exacte. Nous distinguons donc deux types de capteurs : ceux connaissant leur position exacte, appelés « ancres ». Ils seront représentés sur tous les schémas par des nœuds noirs, les autres par des nœuds blancs.
Ci-dessous, un exemple de réseau contenant douze capteurs, dont trois
ancres :
Figure 1
Nous pouvons distinguer deux grandes parties indépendantes :
la partie routage et communication entre les capteurs. la partie algorithmique et programmation de la méthode.
Nous verrons par la suite que nous avons dû nous focaliser sur la deuxième partie, la première faisant l’objet d’un autre projet pour un étudiant de Master Recherche deuxième année.
6
2.2 Méthode AT-Dist
2.2.1 Estimation de distance entre une ancre et un capteur
Une solution pour effectuer cette estimation est de faire la somme des distances pour aller d’un capteur à une ancre. Chacune d’elles envoie son identifiant à ses voisins. Ils estiment alors leur distance avec l'ancre et font circuler cette information à leurs proches, qui répéteront à leur tour ce procédé. Ainsi chaque nœud obtient des évaluations de distance avec les ancres ; seule la distance la plus courte avec chaque ancre est conservée.
Par exemple, (figure 2), la distance estimée entre S et D est dSY + dYD, et nous avons dSD ≤ dSY + dYD due à l'inégalité triangulaire.
Figure 2
Cette méthode, exigeant peu de calculs, est facilement utilisable et
compréhensible. L’inconvénient principal est que les erreurs dues à l’estimation des distances sont propagées et réutilisées par la suite.
Nous représenterons par la suite une distance estimée entre deux points par le
symbole d̂ . Cette dernière est la mesure évaluée entre deux nœuds.
2.2.2 Principe général
Quand un nœud X reçoit la position d’une ancre A, il estime sa distance avec cette dernière et dessine alors un ou deux cercles. En effet, si X et A sont voisins, alors X connaît la distance dAX (i.e. la distance réelle entre A et X). X en déduit qu’il est sur le cercle de centre A et de rayon dAX. Si A et X ne sont pas voisins, alors X sait qu’il n’est pas à l’intérieur du cercle de centre A et de rayon r (r étant le rayon d’émission des capteurs). De plus, X connaît sa distance estimée avec A ( AXd̂ ) déduite par la méthode d’estimation des distances. Par inégalité triangulaire on peut alors dire que dAX ≤ AXd̂ . Donc le point X est dans la zone entre les cercles de centre A et de rayon r et le cercle de centre A et de rayon AXd̂ . Après avoir pu tracer plusieurs cercles à partir de diverses ancres suivant le modèle décrit précédemment, X estime alors sa position comme étant le centre de gravité de la zone définie par
7
l’intersection de ces cercles. X calcule ensuite la distance, que nous noterons ε, entre ce point et celui de la zone qui en est le plus éloigné. Cette valeur correspond donc à l’erreur maximale pouvant être commise.
Voici un exemple pour illustrer cela :
Figure 3
Ici, X reçoit les positions des ancres A, B, C et D. Il estime les distances AXd̂ ,
EXd̂ , CXd̂ , et DXd̂ . La mise en relation des ces informations permet de définir la zone en gras sur le schéma. X calcule alors son centre de gravité et estime sa position en X’.
Enfin, X calcule ensuite la distance, que nous noterons ε, entre X' et le point de
la zone qui en est le plus éloigné. Cette valeur correspond donc à l’erreur maximale de positionnement pouvant être commise.
2.2.3 Représentation
Chaque nœud représente le réseau par une grille. La taille des carreaux qui la compose est fixée à 0.1r afin d’assurer la précision des calculs. Quand un nœud reçoit une position d'ancre, il incrémente les cases incluses dans la zone représentant l’ensemble des positions sur lesquelles il peut se situer. Si l’ancre et le capteur sont voisins, la zone représente un cercle dont le rayon correspond à la distance entre elle et lui, son centre a pour coordonnées celles de l’ancre. Dans le cas contraire, la zone est une surface, délimitée par deux cercles avec un centre commun, la position de l’ancre. Son rayon d’émission définit le premier, le second a pour rayon la distance estimée entre elle et le capteur.
8
La figure 4 représente un exemple de grille. Quand le nœud X reçoit la position
de B (respectivement C, D), il incrémente alors les zones que définissent les ancres B (respectivement C, D). La zone contenant X est définie par le secteur composé par les cases qui ont la plus grande valeur. Sur le schéma, cette zone est caractérisée par les cases étant égales à trois. X calcule alors le centre de gravité de cette zone et obtient sa position estimée.
Figure 4
La méthode AT-Dist a deux règles importantes :
Une fois la position d’un nœud estimée, celui-ci calcule l’erreur maximale ε qu’il peut commettre, comme vu précédemment. Lorsque cette valeur est inférieure à un certain seuil, on considère que le nœud est placé avec une précision suffisante pour diffuser sa position, ainsi que son ε, aux autres nœuds. Un capteur qui reçoit ces informations, citées dans le cas précédent, tient compte de l’erreur pouvant être commise.
Un nœud est capable de détecter certaines erreurs. Ce cas est illustré dans la figure 4 quand le nœud X reçoit la distance estimée avec l’ancre A. Il n’est pas entre les deux cercles centrés en A, ce qui est impossible de par l’inégalité triangulaire. X détecte alors que l’information est erronée. Cette erreur peut-être due à une mesure erronée et donc propagée à chaque estimation de distance la prenant en compte. AT-Dist permet donc de corriger certaines erreurs.
Au début, un capteur considère sa grille (définie en début de partie 2.2.3) dans
sa totalité mais lorsqu’il a acquis suffisamment de données l’informant qu’il est dans une zone, elle devient sa surface de travail.
Il doit donc connaître un nombre fixe d’ancres avant de pouvoir obtenir cette
zone réduite. Ce nombre est appelé nombre de confiance, il représente un seuil minimum à atteindre. L’importance de ce nombre est relative au niveau de
9
perturbation. En effet, les possibilités d'erreurs sont plus importantes dans un milieu perturbé et on devra donc augmenter ce seuil avant de pouvoir définir la zone.
2.3 Les règles
Cette partie présente trois règles permettant de lever l’ambiguïté quand un capteur peut être situé à deux positions.
Par exemple, dans la figure ci-dessous, X reçoit les informations des ancres voisines B et C. Il peut donc être positionné en A ou en A’.
Figure 5
Les règles permettent de déterminer laquelle des deux positions est celle d’un capteur. Les capteurs devenant des ancres grâce aux règles auront un ε égal à zéro.
2.3.1 Règle une
La première règle permet de déterminer une borne dans laquelle est susceptible de se trouver le capteur grâce à une troisième ancre non voisine de celui-ci.
Figure 6
X est le capteur cherchant à déterminer sa position et D une ancre non voisine
de X. Nous estimons dans un premier temps que D n’est pas une ancre estimée. X reçoit alors la position de D et calcule sa distance estimée ( DXd̂ ).
10
Premièrement, nous supposons que X est réellement en A. Nous devons donc avoir :
dAD > r, sinon cela voudrait dire que A et D sont voisins dAD < ADd̂ , par inégalité triangulaire.
Si ces deux conditions sont respectées, alors on peut assurer que X est en A. Nous estimons maintenant que X est en A’. Si une des deux conditions n’est pas
respectée, X interprète qu’il ne peut donc pas se situer en A’ et conclu qu’il est en A. Si toutes les conditions sont respectées pour A et A’, on ne peut pas conclure.
X est donc en A si r < dAD ≤ XDd̂ et que dA’D ≤ r ou dA’D > XDd̂ . Prenons le cas où D est une ancre estimée. D étant estimé, le cercle réel de
centre D et de rayon r (en noir sur la figure) est inclus entre les deux cercles de même centre et de rayon r ± ε (surface représentée en gris). Il en est de même pour le cercle centré en D avec un rayon de dXD. X est donc assurément en A si : r + ε < dAD ≤ XDd̂ - ε et que dA’D ≤ r - ε ou dA’D > XDd̂ + ε.
Cela signifie que A doit être entre les deux zones grises et que A’ doit être en dehors.
2.3.2 Règle deux
Ici, l'ancre n'appartient pas au voisinage du nœud désirant connaître sa position.
Figure 7
Soit X le nœud cherchant sa position et D une ancre qui n’appartient pas à son
voisinage. Pour commencer, nous supposons que D n’est pas une ancre estimée. Quand X
reçoit la position de D, il regarde si dA’D < r. Si tel est le cas, cela signifie que A’ et D sont voisins. Sinon, X conclut qu’il n’est pas en A’ et vérifie alors la condition dAD > r qui lui permet de se positionner en A. Néanmoins, si dAD > r et dA’D > r alors il ne peut pas conclure.
Maintenant, nous supposons que D est une ancre estimée. Comme pour le cas précédent, la position réelle du cercle de centre D et de rayon r est dans la zone grisée. X est assuré d’être en A si r + ε < dAD et dA’D ≤ r – ε. En d’autres termes, A doit être en dehors du cercle de centre D et de rayon r + ε et A’ doit être à l’intérieur du cercle de centre D et de rayon r – ε.
11
2.3.3 Règle trois
Cette règle est utilisée dès lors qu’un capteur compte au moins trois ancres dans son voisinage.
Figure 8
Soit X le capteur cherchant à se positionner et D une ancre voisine de X. Nous supposons que D n’est pas une ancre estimée. Quand X reçoit la position
de D, il regarde si dA’D > r. Si tel est le cas, D et A’ ne sont pas voisins donc X peut conclure qu’il n’est pas en A’ et si dAD ≤ r, X se positionne en A. En revanche, si dA’D > r et si dAD > r alors on ne peut pas lever l’ambiguïté.
Supposons maintenant que D est une ancre estimée. X est assurément en A si dAD ≤ r - ε et dA’D > r + ε. En autrement dit, A doit être à l’intérieur du cercle de centre D et de rayon r – ε et A’ doit être à l’extérieur du cercle de centre D et de rayon r + ε.
Même si le nœud possède au moins trois ancres dans son voisinage, il n’est pas
recommandé d’estimer sa position comme étant l’intersection des trois cercles car cette méthode est très sensible aux erreurs. En effet, si une des distances avec les voisins est erronée ou si un des voisins n'est pas exactement localisé, alors le nœud ne pourra pas calculer sa position. Le deuxième cas est décrit sur le schéma 9 : la localisation du nœud D est légèrement erronée et D est placé sur le point D'. De ce fait, les trois cercles ne se croisent pas en un point. La règle trois est utilisée pour répondre à ce problème.
Figure 9
12
2.3.4 Processus de vote
Dans le cas idéal (sans erreur de mesure), quand un capteur reçoit la position d’une ancre et qu’il peut appliquer une des règles, l’ambiguïté est levée et il trouve alors sa position. Si une règle peut être appliquée avec seulement une ancre (D sur la figure 10) alors la position du capteur peut être trouvée. Mais que ce passerait-il si une ou plusieurs informations (position, distance estimée,…) concernant l’ancre en question était fausse ?
La figure 10 représente le cas où il y a une erreur sur la distance estimée de A à
D d
Figure 10
ue à une ou plusieurs erreurs de mesure. Prenons d̂ = d1 + d2 + d3 + d4 la distance estimée entre A et D sans erreur, et d~ = d~ 1 + d~ 2 + d~ 3 + d~ 4 la longueur du chemin entre A et D ( d~ 1, d~ 2, d~ 3 et d~ 4 étant des distances erronées) tels que d~ < d̂ . Comme nous pouvons le voir sur le schéma ci-dessus, sans les erreurs, X ne peut pas lever l’ambiguïté car aucune règle ne peut être appliquée. En revanche, si nous utilisons d~ , alors grâce à la règle une, X ce positionne en A’ ce qui est faux. X ne peut donc pas faire confiance à une seule ancre.
Le processus de vote a pour but de compter le nombre d’ancres qui positionnent X en A et celles qui le positionnent en A’ afin de déduire sa position. Quand un capteur peut être localisé en deux positions p1 ou p2, on vérifie les règles avec toutes les ancres connues. Quand l’une d’entre elles permet de déterminer la position du capteur en p1 (respectivement p2) alors la valeur de cp1 (respectivement cp2) est incrémentée. Si cp1 – cp2 ≥ confiance (respectivement cp2 – cp1 ≥ confiance) alors le capteur est localisé en p1 (respectivement p2). Si nous sommes dans un cas où il n’y a pas d’erreur, il suffit de mettre la confiance à 1. En réalité, elle est définie en fonction de l’environnement et doit être évaluée expérimentalement.
13
3 Expérimentations Notre projet consiste à utiliser des données réelles pour valider la méthode AT-
Dist décrite dans la partie précédente. Pour cela nous avons dû comprendre le fonctionnement du matériel fourni par l’entreprise CORONIS. Une fois cette première étape accomplie, la partie pratique commence avec la création de différents réseaux, l’objectif final étant d’obtenir des distances (en mètres) entre les différents équipements.
3.1 Présentation
Pour nous permettre de réaliser des expériences réelles dix modules de communication nous ont été fournis. Nous les appellerons par la suite WaveTalk (visible sur la figure 11) ou par abus de langage « capteurs » car il est possible de connecter sur ceux-ci de véritables capteurs (de chute, de mouvements…).
Figure 11 : Un module de communication WaveTalk.
Ces WaveTalk peuvent communiquer entre eux, cependant ce dialogue est
réalisé sur commande. Ils répondent à des requêtes formulées par un WavePort dont deux nous ont été fourni par l’entreprise CORONIS. Ils possèdent une interface USB pour être connectés sur des PC fonctionnant avec le système d’exploitation (OS) Microsoft Windows. Ils sont détectés par défaut comme des modems, c’est pourquoi des drivers doivent être préalablement installés pour qu’ils puissent être correctement reconnus et utilisés.
Nous utilisons un logiciel conçu par l’entreprise CORONIS pour envoyer des requêtes aux WaveTalk, par l'intermédiaire du WavePort (visible sur la figure 12). Elles sont écrites en hexadécimal, leur format pour celles que nous avons utilisé est le suivant : le type du message suivi de l’adresse du WaveTalk que l’on désire interroger.
Figure 12 : Un module de communication WavePort.
14
Tous les modules de communication possèdent une adresse réseau, ainsi qu’un code barre étiqueté sur leur boîtier. Ce dernier permet de connaître l’adresse du module, il se compose ainsi : le numéro de la série de production - l’année de production - numéro du produit. Pour le décomposer on prend les quinze premiers chiffres en décimal pour les passer en hexadécimal. Exemple : Code barre : 00534-06-03167625118 Code hexadécimal : 0216 06 305589
Les WaveTalk peuvent « router » des messages, mais seulement sur trois niveaux (la figure 12 en est une représentation), c’est-à-dire que nous pouvons en interroger un distant de deux modules maximums. Cette contrainte est liée au matériel. Ceci sera intéressant lors de la mise en place d’un réseau afin de limiter les déplacements, cependant il sera impossible pour un capteur de connaître l’ensemble du réseau. De plus, ils ne sont pas créés pour utiliser des programmes informatiques, ils doivent être simplement commandés. Tout ceci implique une centralisation des données et un calcul de positionnement pour chaque capteur depuis un poste unique.
Figure 13
Les modules communiquent entre eux par ondes radio. Le rayon d’action des
WavePort est estimé à 500 mètres et à 1 km pour les WaveTalk. Plus la distance est importante entre deux émetteurs/récepteurs plus la puissance de signal reçu est faible. Celle-ci est évaluée, en dBA, en utilisant une technologie appelée RSSI. Nous verrons dans les parties 3.3 et 3.4 comment nous avons essayé de trouver une correspondance entre un niveau RSSI et une distance en mètres, ce qui est l’élément essentiel pour faire la relation entre les mesures obtenues expérimentalement et notre programme.
15
3.2 Prise en main du matériel
Avant de chercher à relever des mesures entre capteurs, nous devions comprendre le fonctionnement des WavePort et WaveTalk, les requêtes à utiliser, et surtout le moyen de les contacter.
Tous nos relevés d’informations ont été effectués en utilisant le logiciel de l’entreprise, dont l’interface graphique est présentée figure 14.
Figure 14
Après avoir installé les drivers permettant la reconnaissance des WavePort par l’OS Microsoft Windows nous avons récupéré les adresses physiques de ceux-ci codées en hexadécimal. Cette étape nous a permis de comprendre le fonctionnement du programme, à savoir de sélectionner le port de communication avant de charger automatiquement les bibliothèques (DLL) qui servent aux dialogues. Ce port n’est pas choisi aléatoirement, il faut au préalable regarder dans les « informations du système » afin de connaître quel « port com » a été attribué au WavePort connecté à l’ordinateur. Dans la partie précédente nous expliquions comment trouver l’adresse réseau à partir du code barre, mais avant d’avoir eu connaissance de cette information, nous avons dû trouver une solution pour pouvoir commencer les expériences. Après avoir trouvé dans la documentation fournie une requête permettant de faire un « broadcast », la réponse à celle-ci était l’adresse physique de WaveTalk. Les communications portent à 500 mètres (en conditions idéales). Nous n’avons pas lancé cette requête au sein de la faculté des Sciences de Montpellier pour ne pas recevoir de réponses de la part des capteurs déjà installés par l’entreprise CORONIS pour leurs propres expériences.
Les modules de communication peuvent faire du routage, mais du fait d’être limité à trois niveaux nous n’avons pas cherché à apprendre ce mode de fonctionnement. Nous communiquerons manuellement avec chaque capteur à portée d’émission.
16
Les émetteurs communiquent par ondes hertziennes avec un niveau de
puissance variable qui s’exprimera en hexadécimal dans notre cas, comme défini par l’entreprise CORONIS. La valeur maximale, ou seuil de saturation, s’exprime par les nombres 2c, 2d ou 2e. Chaque valeur hexadécimale correspond à une plage de puissance RSSI. Seules les valeurs comprises entre 0a et 2e sont atteignables, ceci constitue une trentaine de paliers.
La partie suivante montrera l’expérience réalisée pour faire correspondre un niveau de puissance en dBA avec une distance en mètres. Pour obtenir un niveau RSSI entre deux modules nous lançons deux requêtes (cf. figure 15). La première renseigne sur la puissance nécessaire pour communiquer avec un WaveTalk donné, et la seconde sur la puissance du signal reçu. Ces deux commandes sont réciproquement 0x68 et 0x6A suivi de l’adresse réseau du capteur à contacter. Les réponses à ces demandes sont respectivement 0x69 et 0x6B suivi du RSSI en hexadécimal.
0x68 : donne la puissance nécessaire pour émettre.
0x6A : donne la puissance reçu par le WaveTalk pour émettre.
Figure 15
Les premiers essais montrent une option intégrée par défaut dans les
WavePort, l’auto adaptation. Elle permet d’adapter la puissance d’émission en fonction de la distance qui sépare un capteur désirant communiquer avec un autre. Si cette option n’est pas désactivée cela fausse entièrement les résultats des relevés de niveau RSSI car l’on obtiendra pratiquement toujours les mêmes valeurs. Pour ce faire nous utilisons avant chaque expérience la commande 0x4600, pour être certain qu’elle soit désactivée.
17
3.3 Correspondance RSSI-Mètres
Les ondes ne se propagent pas uniformément dans l’espace, elles peuvent être perturbées par divers éléments comme un mur de béton armé qui atténuera significativement la puissance du signal, voir l’annuler ou il rebondira et perturbera le reste des ondes (cf. figure 16). D’autres matériaux, très utilisés par les armées dans l’aéronautique, les absorbent, ainsi dans la réalité au lieu d’avoir un cercle de propagation, nous aurons une ellipse ou le plus souvent un « nuage ».
Figure 16 De plus, les composants de ces modules ne sont jamais complètement
identiques. Par conséquent, d’un capteur à un autre, nous ne pouvons pas avoir les mêmes rayons d’émissions, ce qui implique une formule mathématique pour passer d’un niveau RSSI à une distance en mètres, spécifique à chaque WavePort et WaveTalk.
Tout ceci apparaît comme une évidence, et pourtant plusieurs tests ont été
nécessaires pour arriver à ce constat. En ce qui concerne le phénomène de perturbation, nous n’avons pas eu à faire d’expérience pour en prendre conscience. En effet, nos cours de réseaux, nos propres connaissances, l’avis de nos tuteurs et intervenants ainsi que la première réunion avec l’entreprise CORONIS ont suffit à prendre la décision de trouver un terrain offrant un champ libre.
Les expériences ont été effectuées dans un champ appartenant à une manade, connue par M. FOUCARAN qui nous a mis en relation avec les propriétaires des lieux. Le terrain présentait des conditions idéales du fait de n’avoir aucun bâtiment ou élément pouvant perturber les ondes émises par les capteurs. Voici une carte du terrain où les bords sont délimités en rouge.
Figure 17 : Carte du champ de la manade utilisé pour les expériences
18
Les WaveTalk permettent d’obtenir des relevés de distances réelles dans un réseau de capteurs. Cependant lorsque deux modules peuvent communiquer, ils sont dit « voisins » l’un de l’autre, ils ne connaissent pas la distance en mètres qui les sépare mais uniquement le niveau RSSI. Pour obtenir une relation mathématique qui convertit une puissance en dBA en mètres. Pour cela, nous avons réalisé plusieurs relevés suivant un protocole défini avec nos tuteurs, partie 3.4.2.
Le but est d’obtenir une courbe monotone et décroissante. Pour ce faire, nous
traçons une ligne droite avec un repère tous les dix mètres. A l’une des extrémités nous plaçons un WavePort qui restera fixe tout au long de l’expérience. Nous utilisons un unique WaveTalk afin de garantir les mêmes conditions. A chaque position, nous prenons un seul relevé dans les deux sens (0x68 et 0x6A). Nous ne fixons pas de distance maximale, si après plusieurs tentatives les deux modules ne communiquent plus on considère la distance maximum atteinte. Nous répétons plusieurs fois ce processus pour obtenir un plus grand échantillon de données. Nous obtenons les courbes suivantes :
Le WaveTalk utilisé pour ces expériences est le numéro 5 ce qui sera import
Figure 18 : Niveau de signal RSSI après utilisation de la commande 0x6A
Figure 19 : Niveau de signal RSSI après utilisation de la commande 0x68
Nous pouvons observer une légère différence de coefficients sur les deux fonctions obtenues. Si nous intégrons les relevés effectués à une distance inférieure à 15 mètres, cela perturbe la courbe et entraîne un nouveau constat : lorsqu’un émetteur et un récepteur sont trop proches ils se perturbent mutuellement.
ant pour les rubriques suivantes.
19
Le résultat de l’expérience est concluant mais nous verrons dans la partie 3.4.3 pourquoi la fonction obtenue n’est pas utilisable. Nous pouvons ajouter quelques réflexions après cette expérience, les capteurs sont sensibles au vent, il n’était pas rare de perdre des trames lors de rafales de vent. Notre tuteur M. KÖNIG nous a informés qu’ils pouvaient être aussi sensibles à l’humidité et ceci expliquerait certaines pertes de requêtes à des distances relativement faibles compte-tenu de la portée théorique des WavePort et WaveTalk. Il existe une formule permettant d’obtenir une distance en mètres à partir d’un niveau RSSI, mais celle-ci prend beaucoup de paramètres en compte, comme l’épaisseur des dalles si l’on se trouve dans un bâtiment, la hauteur de la plus haute tour qui puisse faire obstacle, la densité de certains matériaux… Il nous était donc impossible de l’utiliser.
3.4 Divers réseaux expérimentaux
Nous pensions pouvoir nous servir des résultats obtenus dans la partie 3.3, et ainsi pouvoir créer diverses topologies de réseaux de capteurs afin de les donner en paramètres à notre programme et ainsi montrer l’utilité et le bon fonctionnement de celui-ci. C’est pourquoi nous présentons ici les divers réseaux que nous avons expérimentés et l’analyse faite dessus.
3.4.1 Conditions à respecter
Dans la partie 3.3 nous observions l’influence d’éléments extérieurs sur les émissions de trames par ondes hertziennes. Le champ libre est respecté cependant le corps humain peut parfois faire antenne c’est pourquoi lors des tests nous nous tenions le plus possible éloignés des capteurs et des WavePort pour limiter cet effet.
De plus à la demande de nos encadrants, les modules de communication étaient placés à des hauteurs équivalentes. De notre propre chef, nous avons fixé les capteurs sur des poteaux en bois, avec l’antenne des WaveTalk dépassant de quelques centimètres ce support pour éviter toutes réflexions et perturbations possibles.
Pour chaque réseau, il est intéressant de posséder un large éventail de
distances différentes afin de vérifier la validité du programme et de ne pas se trouver dans un cas particulier avec des distances équivalentes ou très proches.
20
3.4.2 Protocole
Au fur et à mesures des essais et des différents réseaux les protocoles de relève de mesures ont évolué en fonction des problèmes rencontrés que nous évoquerons dans la partie 3.4.3.
Lors de la création du premier réseau nous avons placé nos 10 capteurs
suivant le graphe réalisé sur papier, figure 20. Pour les relevés nous n’avons pas pris en compte la notion de voisin, même la plus grande distance entre deux capteurs est inférieure à la portée donnée par le constructeur. Pour chaque lien nous avons noté cinq fois les mesures pour obtenir une moyenne et être plus rigoureux.
Figure 20 : Premier réseau de capteur
Pour le dernier réseau, nous avons utilisé un seul capteur, le numéro 5 et le
même WavePort que dans la partie 3.3. Ainsi nous n’avons pas eu de différence de matériel, chaque module de communication était ainsi totalement identique. Il est vrai que cela nuit à la véracité des expériences que l’on pourrait effectuer sur des réseaux déjà existant comme à la faculté des sciences de Montpellier. Cependant les problèmes énoncés dans la partie suivante expliqueront la nécessité de respecter ce protocole.
Les conditions d’utilisations des WaveTalk restent identiques à la partie 3.3. Ces modules de communications peuvent router des messages sur trois
niveaux, mais du fait de ne pas posséder la capacité d’exécuter de programme informatique nous n’utiliserons pas cette option. Les WaveTalk communiquent entre eux uniquement sur commande des WavePort. C’est pourquoi, pour effectuer nos relevés de puissance d’émission et de réception entre chaque capteur nous avons mis en place le protocole suivant.
21
Chaque WaveTalk s’est vu attribuer un numéro, cela permet de les faire correspondre aux indices des nœuds du graphe établi sur papier, ainsi et de connaître le module avec qui l’on désire communiquer.
Nous avons simulé une communication entre un capteur donné et les WaveTalk à portée d’émission. Pour ce faire, nous plaçons un WavePort à la même position géographique que le capteur. Ensuite, nous lançons les requêtes appropriées (0x68, 0x6A) pour connaître les niveaux RSSI.
3.4.3 Problèmes rencontrés
Les niveaux RSSI varient en fonction de la distance entre deux capteurs, notamment lors de la désactivation de l’auto-adaptation.
Nous avons remarqué une impossibilité de communiquer correctement au-delà de 110 mètres de distance entre un WavePort et le WaveTalk numéro 5. Cependant sur notre dernier réseau cette valeur a été réduite à 90 mètres, cette différence peut s’expliquer par des phénomènes divers comme ceux cités dans la partie 3.3. Le véritable problème rencontré tout au long de nos expériences, et qui concerne le but de celles-ci, réside dans les valeurs RSSI retournées par les commandes 0x68 et 0x6A (expliquées dans la partie 3.2). En théorie, plus l’écart entre deux WaveTalk ou WavePort est grand, plus le niveau de puissance est faible. Pour une distance donnée entre deux points fixes cette valeur reste identique et ne varie pas significativement. Cette affirmation s’est vue contredite lors de nos expériences, d’où l’application des consignes d’utilisation afin de limiter tout risque de mauvaise manipulation. Prenons trois positions sur un réseau de capteurs, A, B et C, dont les distances entre tous ces points permettent une communication sans pertes. Nous plaçons un WavePort en C. Le premier relevé se fait entre C et A, sur ce dernier se trouve un WaveTalk, le résultat est a priori correct. Nous éloignons le capteur pour le positionner au point B, situé à quelques mètres d’écart, de sorte que la distance entre B et C soit plus grande que la précédente. Une fois le niveau RSSI noté, nous repositionnons le module de communication en A, et nous observons un net changement de la valeur RSSI par rapport à celle effectuée la première fois. La majorité du temps, cette dernière était égale au seuil de saturation. Dans de nombreux cas, nous n’avons pas eu besoin de changer de position du capteur pour observer cette variation, d’où l’utilité de relever plusieurs fois la puissance d’émission afin de prendre une moyenne. Ce constat nous a amené à un établir un nouveau protocole, utiliser le même WavePort et le même WaveTalk (le numéro 5) qui avait servi pour établir une correspondance entre une mesure RSSI et une distance en mètres. Cependant, le même phénomène est apparu, parfois même plus significativement encore.
22
3.4.4 Analyse
Le problème rencontré implique que nous ne pouvons pas nous fier aux courbes obtenues sur les divers réseaux construits, à cause d’une trop grande marge d’erreur. Les équations mathématiques obtenues restent similaires, mais inexploitables puisqu’elles ont été obtenues sur une moyenne et que celle-ci a pu être faussée par des apparitions, nombreuses, du seuil de saturation.
Nous pensions établir une relation mathématique pour chaque capteur comme
dans la partie 3.3 avec le WaveTalk numéro 5, mais après le constat fait en fin de partie 3.4.3 cela nous parait inutile.
Ces modules de communication sont en théorie utilisés pour des dialogues à
plus grande échelle (1 km pour les WaveTalk), il se peut que cela puisse influer sur les niveaux RSSI, cependant si tel était le cas nous aurions dû avoir constamment des seuils de saturation, notamment sur les puissances d’émission des capteurs vers les WavePort. C’est pourquoi, M. Alain FOUCARAN nous a conseillé de considérer seulement les mesures relevées par la commande 0x68 à savoir les communications d’un WavePort vers un WaveTalk.
Nous avons fait part, lors des réunions avec l’entreprise CORONIS, de nos
résultats et de notre problème. Elle a décidé d’effectuer des tests similaires afin de mieux comprendre ce phénomène.
3.5 Exploitation des données
Le but de ces expériences était d’obtenir des topologies réelles sur lesquelles notre programme pourrait s’exécuter. Pour cela, nous avions besoin de matériels permettant d’évaluer leur distance en mètres avec leurs voisins.
Les WavePort et WaveTalk utilisent la technologie RSSI, qui donne un niveau de
puissance utilisé en fonction de la distance qui sépare les deux communicants. Ceci impliquait un second objectif, obtenir une fonction mathématique permettant de passer de l’unité dBA à celle des mètres.
Effectivement ces objectifs n’ont pas pu être atteints, cependant, ces
expériences n’auront pas étaient vaines. En effet, elles nous ont permis d’apprendre à utiliser du matériel existant et commercialisé, et d’établir une collaboration entre diverses équipes (LIRMM, IES et l’entreprise CORONIS). Ces capteurs n’étaient pas adaptés à ce type d’expérience, le but principal se limitant à communiquer des informations sur de longues distances, sans avoir besoin d’un RSSI précis.
Par rapport à notre programme qui attend des données réelles, partie 4.2, nous
travaillerons sur des graphes réalisés sur papier où nous calculerons mathématiquement les distances entre les capteurs. Par la suite lorsque le problème aura été résolu, il suffira de passer en paramètre les mesures expérimentales. Ainsi le programme peut fonctionner avec des données théoriques comme pratiques.
23
4 Programmation de la méthode AT-Dist
Par convention avec l’entreprise et ce dans un souci de pouvoir adapter notre programme à des applications ActiveX, nous avons réalisé notre projet dans le langage C++ pour pouvoir respecter cette contrainte dans les évolutions futures.
4.1 Fonctionnement général
Pour fonctionner, le programme a besoin d’informations décrivant le graphe à étudier, comme la position des ancres et les distances entre les capteurs voisins. Tout ceci est placé dans un fichier texte et organisé dans un ordre précis, cela est décrit dans la partie 4.2.
Avant d’exécuter le projet AT-Dist, il est important de s’assurer de la présence
du chemin vers le fichier, cité ci-dessus, nécessaires au programme. Une fois cette vérification effectuée, le projet peut être compilé. Le lancement de l’application AT-Dist se fait simplement par l’exécution du fichier « AT-Dist.exe ».
Dès le lancement du programme, l’utilisateur a la possibilité d'activer ou de
désactiver les règles définies par la méthode AT-Dist pour lever des ambiguïtés et placer une nouvelle ancre avec certitude. Cette information est nécessaire car les règles ne sont pas toujours efficaces ; en effet il est préférable de ne pas les utiliser si on travaille en milieu fortement perturbé, la précision du positionnement est amoindrie, et les règles pourraient donner des résultats erronés. Cela ne constitue pas un problème majeur, car dans ce type de milieu, on pourra tolérer une marge d’erreur plus importante.
Grâce aux informations contenues dans le fichier, dont sa composition et sa structure sont précisées dans la partie 4.2, le programme détermine les ancres connues, et les capteurs à positionner. Si l’utilisation des règles a été choisie, chaque capteur ajoutera les ancres se trouvant dans sa zone d’émission à un tableau de voisins. Grâce à deux d’entre elles, deux points possibles pour sa localisation seront calculés : les points d’intersection des deux cercles ayant pour centres les positions des ancres sélectionnées et pour rayons les distances les séparant du capteur.
Les trois règles définies dans la méthode AT-Dist, que nous détaillerons dans une partie ultérieure, permettent dans différents cas de localiser avec certitude un capteur ; celui-ci deviendra alors une ancre fixe.
Ces opérations sont répétées tant que des capteurs deviennent ancres. Ensuite, les capteurs tentent de se positionner en utilisant les informations
fournies successivement par chacune des ancres. Si après traitement, un capteur considère sa position comme suffisamment précise (c’est-à-dire avec un taux d’erreur inférieur à un taux donné), il deviendra une ancre à son tour.
Si les règles sont utilisées, on répète les opérations définies ci-dessus avec cette nouvelle ancre, en prenant en compte sa marge d’erreur.
A la fin des opérations, la position et la marge d’erreur de chaque capteur sont affichées à l’écran.
24
4.2 Les besoins du programme
Pour fonctionner, le programme doit connaître le nombre de capteurs, les coordonnées des ancres, et un nombre de distances lui permettant de représenter un graphe connexe dans sa matrice de distances. Ces informations doivent être contenues dans un fichier dont le nom doit être passé en paramètre dans le programme. Sa réalisation est relativement simple et peut se faire rapidement grâce à un tableur. Il faudra simplement enregistrer ce travail sous forme de fichier texte afin qu’il soit analysable par une fonction de notre application.
La forme du fichier est la suivante :
longueur <longueur du terrain>
largeur <largeur du terrain>
rayon <portée des capteurs>
origine destination distance réelle <numéro de capteur> <numéro de capteur> <distance entre les deux capteurs>
…
…
…
Ancre coord_x coord_y <numéro de capteur ancre> <abscisse du capteur> <ordonnée du capteur>
…
…
…
Les dimensions du terrain sont utiles pour déterminer l’échelle, c’est-à-dire la
distance représentée par une case de la matrice. Le rayon permet de déterminer si deux capteurs sont voisins. En effet, le voisinage est effectif si la distance entre deux capteurs est inférieure ou égale au rayon. En pratique, cela signifie que les deux capteurs sont à même de communiquer directement. La partie suivante concerne les distances entre les capteurs. Ces informations doivent être les plus complètes possible, afin de pouvoir calculer le plus court chemin existant entre chaque capteur.
Enfin, la dernière partie sert à préciser les capteurs dont les coordonnées sont connues (les ancres).
Nous avons implémenté une méthode permettant de créer un fichier de ce type
contenant les informations relatives à un graphe généré aléatoirement. L’utilisateur est invité à renseigner le programme sur le nombre de capteurs, d’ancres, et le rayon d’émission des appareils. L’application instanciera à partir de ces données un graphe connexe. Les coordonnées de chaque capteur sont stockées dans un fichier permettant de comparer les résultats finaux avec les données générées.
25
4.3 L'utilisation d'une matrice
Bien que l’application soit centralisée et que le traitement soit effectué par une seule machine, son fonctionnement a été réfléchi afin de se rapprocher le plus possible d’une application distribuée, dans le but de pouvoir embarquer notre programme dans des capteurs possédants des capacités de calculs. Nous avons de ce fait créé une classe « capteur » afin d’instancier des objets de ce type ; chacun de ceux-ci contient un attribut « cartographie » possédant les différentes méthodes à même de déterminer une ou plusieurs positions possibles pour un capteur, d’effectuer des calculs relatifs aux règles ou d’affiner la zone de localisation de celui-ci.
Pour le calcul indépendant des règles, la méthode stipule l’emploi d’une matrice. Chacune de ses cases représente une certaine distance, définie par l’utilisateur ou le programme. Les cases, correspondant à une zone dans laquelle on estime la position du capteur, sont incrémentées ; après chaque modification, on réduit la surface de travail sur la matrice au « rectangle » incorporant les valeurs maximales. A la fin des opérations, la position du capteur est estimée au centre de gravité de cette surface, et sa marge d’erreur ε est définie comme étant la distance entre ce point et celui qui s’en éloigne le plus sur la zone.
4.3.1 Stockage de la matrice
Lors de la réalisation du projet, le stockage de la matrice a été soumis à de nombreuses interrogations, plusieurs solutions s’offraient à nous et nous devions choisir celle apportant le meilleur rapport consommation de mémoire/temps d’accès.
4.3.1.1 Vector
La première solution que nous avons adoptée a été l’utilisation de la classe « Vector » contenue dans la librairie STL C++. Les vecteurs sont des tableaux dynamiques que l’on peut manipuler facilement à l’aide de méthodes permettant d’insérer ou supprimer un objet contenu dans celui-ci, d’y accéder comme pour l’utilisation des tableaux, mais aussi de définir le nombre de cases réservées. C’est pour ces différents aspects que nous avons décidé d’utiliser la classe « Vector ».
En effet, ayant au départ fixé la distance représentée par une case de la matrice à 10% du rayon, cette dernière devait avoir une taille relative à la surface du réseau. Au lancement du programme, pour un vecteur donné, la matrice ne comptait qu’une seule case. Au fur et à mesure de l’agrandissement de la zone, la matrice s’agrandissait par la réservation de cases mémoires supplémentaires, ainsi que nous l’avions programmé dans une méthode.
La matrice étant un tableau à deux dimensions, elle était représentée sous forme d’un vecteur de vecteurs.
Nous avons rapidement constaté les limites de l’utilisation de ce tableau : le temps de l’allocation mémoire était fort conséquent, et les demandes d’allocation très fréquentes : en effet au traitement de chaque ancre, la zone et donc la matrice étaient modifiées. Une modification en longueur impliquait un ajout de cases sur
26
chacun des vecteurs contenus dans le vecteur principal, une modification en largeur une création de nouveaux vecteurs dans le premier.
Mais le problème majeur de l’utilisation d’une carte dynamique était dû à l’espace mémoire nécessaire ; désirant représenter le réseau précisément, la matrice comptait un nombre important de cases ; et la consommation de mémoire est rapidement devenue exponentielle.
4.3.1.2 Map
L’inconvénient de l’utilisation de notre première méthode venait de la consommation excessive de mémoire. Chacune des cases de la matrice devait être réservée en mémoire ; or le calcul des zones s’effectue par des intersections ou unions de surfaces circulaires ; un nombre important de cases n’est donc jamais concerné par une incrémentation, c’est-à-dire qu’à aucun moment une ancre ne suppose la position du capteur possible à cet endroit.
Dans le but d’éviter la réservation en mémoire de cases inutiles au programme, nous avons décidé d’utiliser des « map » : seules les cases incrémentées seraient réservées. Une « map » est une structure de données qui permet d’associer une clé à un élément ; chaque élément est accessible via sa clé.
Nous avons donc créé une structure de ce type ayant pour clés les abscisses des cases et pour éléments une autre « map ». Chacune d’entre elles reliées à la première avaient pour clé les ordonnées des cases, et pour éléments les valeurs de celles-ci.
A première vue, cet essai était concluant ; la quantité de mémoire utilisée était devenue plus raisonnable ; cependant les temps d’accès étaient accrus, puisqu’une recherche devait s’effectuer dans la première table puis dans la seconde, et l’utilisation de cette structure était très lourde ; l’accès à la valeur d’une case n’était possible qu’après l’appel successif à plusieurs méthodes dont la complexité est logarithmique.
Cette structure est considérée comme une table de hachage dans de nombreuses documentations, mais les temps d’accès nous ont montré qu’elle n’en est pas une.
Cette solution a donc finalement été abandonnée à son tour.
4.3.1.3 Tableau de taille fixe
Après avoir expérimenté plusieurs utilisations de matrices de taille variable, nous avons finalement décidé d’en implémenter une de taille fixe, en accord avec notre tuteur. Le temps de l’allocation mémoire est donc fixe, lui aussi, et n’intervient qu’à l’initialisation du programme. Nous avons introduit la contrainte supplémentaire pour l’utilisateur de préciser les dimensions du terrain ou de la surface où le réseau de capteurs a été installé. Grâce à cette information supplémentaire, le programme calcule une échelle qui définit la surface réelle représentée par une case de la matrice.
27
Nous avons fixé la taille de la matrice à 1000 x 1000 cases ; c’est le compromis entre consommation mémoire, temps d’allocation, d’accès et précision des résultats qui nous a semblé le plus intéressant.
4.4 Barycentre, Epsilon, Zone de positionnement
L’application, lorsqu’elle ne prend pas les règles en compte ou que celles-ci n’ont pas permis de localiser précisément chacun des capteurs, effectue des traitements sur la matrice représentant le réseau connu par chacun des capteurs afin d’en estimer la position.
L’application prend en compte les ancres les unes après les autres alors qu’elles sont stockées dans un vecteur. Lorsqu’une ancre est traitée, elle envoie ses coordonnées à chacun des capteurs non encore localisés avec suffisamment de précision. Le programme principal applique l’algorithme de Dijkstra sur la matrice à partir du capteur en cours. Cela permet de connaître les distances entre ce capteur et chacun des autres dans le réseau ; on connaît donc la distance estimée entre l’ancre et le capteur en cours de traitement.
Il est alors possible d’invoquer la méthode « calculPosition » dans la classe capteur, qui permet d’estimer une position à partir des coordonnées de l’ancre, de sa marge d’erreur, et de la distance la séparant du capteur.
La première opération réalisée dans cette méthode consiste à incrémenter les cases de la matrice correspondant à un emplacement possible du capteur. Ces cases représentent une zone circulaire ; en effet le capteur se trouve à une distance « d » autour d’un centre ayant pour coordonnées celles de l’ancre, ou entre deux cercles de rayon d ± ε. Chacune des cases se trouvant sur le périmètre du premier cercle ou entre les deux autres voit sa valeur incrémentée de 1.
Une fois cette opération effectuée, une méthode calcule la « zone » dans
laquelle on estime la position du capteur ; c’est le rectangle qui englobe toutes les cases ayant la valeur maximale (les cases pour lesquelles un maximum d’ancres a défini la localisation du capteur possible). Cette manipulation permet de limiter les traitements ultérieurs à une surface réduite de la matrice, dans le but d’optimiser les temps de traitement.
On détermine le centre de gravité de la zone composée des cases de valeur maximale, c’est-à-dire l’isobarycentre (car toutes les cases ont le même poids). Ceci s’effectue, comme pour le calcul d’un barycentre ordinaire, par le procédé suivant :
Les coordonnées d’un barycentre partiel (temporaire) et son poids sont initialisés à 0. Pour chaque case appartenant à la zone, on calcule le barycentre partiel en prenant en compte la dite case, puis on augmente le poids de ce nouveau barycentre de 1 (poids d’une case).
Ce traitement implique un parcours en O(n.m) de la zone délimitée, n et m correspondant aux côtés de la zone ; il pourrait être plus rapide de déterminer le barycentre comme étant le point d’abscisse ((abscisse minimale + abscisse maximale des cases de valeur maximum) / 2), et d’ordonnée ((ordonnée minimale + ordonnée maximale des cases de valeur maximum) / 2). Ce calcul s’effectuerait en
28
O(1) puisque les coordonnées nécessaires au calcul sont celles de la « zone ». Cependant, il ne s’agirait que d’une estimation du barycentre, ayant une influence sur le résultat final puisque le calcul de la marge d’erreur ε serait également faussé ; notre calcul donne les coordonnées matricielles exactes du barycentre de la zone.
L’opération suivante consiste à déterminer la marge d’erreur ε du positionnement. Il s’agit de la distance existant entre le barycentre de la « zone », calculé précédemment, et le point de valeur maximale qui en est le plus éloigné. On calcule pour chaque case de valeur maximale la distance la séparant du barycentre ; c’est la distance euclidienne entre ces deux points. On retiendra pour valeur de ε la distance la plus grande.
Une fois ces calculs effectués, on vérifie si le capteur est devenu une ancre ou non. Pour cela, on compare son ε au taux défini ; s’il lui est inférieur, alors le capteur devient une ancre. Il est ajouté au tableau des ancres et supprimé du tableau des capteurs non ancres. On pourra l’utiliser pour localiser d’autres capteurs dans les calculs suivants, en utilisant son ε. En effet, au lieu de localiser le capteur sur le cercle ayant pour centre les coordonnées de l’ancre et pour rayon sa distance au capteur, on le localise entre les cercles de rayon (distance + ε) et (distance – ε).
Remarque : si les règles sont utilisées, on les appelle dès l’ajout de la nouvelle ancre : en effet elles pourront peut-être permettre de localiser plus précisément (et plus rapidement) les capteurs restants.
Ces opérations sont répétées pour chaque capteur, puis l’ancre en cours est effacée du tableau d’ancres ; elle a diffusé ses informations à tous les capteurs, elle n’est plus utile à cette partie du programme.
On recommence cette séquence tant qu’il reste des ancres dans le tableau ; on affiche les résultats dès que ce tableau est vide.
4.5 Les règles
Les règles sont définies par la méthode AT-Dist comme des situations particulières dans lesquelles un capteur peut se localiser précisément. La condition de base est que deux ancres appartiennent au voisinage d’un capteur (c’est-à-dire que la distance entre les ancres et le capteur est inférieure au rayon d’émission des capteurs).
4.5.1 Appels des règles
Les règles (dans le cas où l’utilisateur a choisi de les mettre en application) sont appelées au lancement du programme, après le traitement du fichier. Elles sont également rappelées à chaque découverte d’une nouvelle ancre dans le calcul de position par barycentre. La première étape de la méthode consiste pour chaque capteur non ancre à ajouter à un tableau de voisins, les ancres se trouvant dans son rayon d’émission. Une vérification permet d’éviter qu’une ancre soit ajoutée deux fois à ce tableau.
29
Si un capteur a plus de deux voisins ancres, on calcule les deux points possibles où il peut se trouver. Ce calcul se fait aléatoirement sur deux de ses voisins.
Ensuite, s’il existe un troisième voisin, la règle trois est appelée. Cette règle permet, dans la plupart des cas, de localiser précisément un capteur s’il a trois ancres dans son voisinage.
Si le capteur compte moins de trois ancres dans son voisinage ou si la règle trois n’a pas réussi à lever l’ambiguïté entre les deux positions possibles, on appelle successivement la règle une, puis si elle échoue, la règle deux.
Lorsqu’une des règles a pu découvrir une nouvelle ancre, on ajoute celle-ci au tableau d’ancres, et on la supprime du tableau des capteurs non-ancres.
Cette séquence d’opération est répétée tant que des nouvelles ancres sont découvertes.
4.5.2 Calcul des points possibles
Lorsqu’un capteur non ancre possède au moins deux ancres dans son voisinage, il est possible de calculer les deux points où il est susceptible de se trouver à partir des coordonnées de deux des ancres voisines et de leur distance au capteur. Le calcul des coordonnées des deux points se fait par l’équation des deux cercles ; en effet les deux points sont les points d’intersection des deux cercles ayant pour centre les coordonnées des ancres et pour rayon la distance les séparant du capteur.
Les équations des deux cercles sont les suivantes : Premier cercle :
20
20
20 )()( yyxxR −+−=
Deuxième cercle : 2
12
12
1 )()( yyxxR −+−=
avec ( ; ) et ( ; ) comme coordonnées des centres des cercles, et comme rayons.
0x 0y 1x 1y 0R
1R
Après développement, nous posons une constante :
)(2 10
20
21
20
21
20
21
yyyyxxRR
N−
+−+−−=
De même, nous avons :
( ) 022221 020
220
200
10
10
10
100
2
10
102 =+−+++⎥⎦
⎤⎢⎣
⎡−⎟⎟
⎠
⎞⎜⎜⎝
⎛−−
−⎟⎟⎠
⎞⎜⎜⎝
⎛−−
+⎥⎥⎦
⎤
⎢⎢⎣
⎡+⎟⎟
⎠
⎞⎜⎜⎝
⎛−−
NyRNyxxyyxx
Nyyxx
yxyyxx
x
C B A
Cette équation du second degré est facilement résoluble grâce à Δ.
ACB 42 −=Δ
30
Les deux abscisses des points d’intersections seront alors :
ABx
2Δ±−
=
On peut alors calculer les ordonnées en fonction des abscisses grâce à l’équation suivante :
⎟⎟⎠
⎞⎜⎜⎝
⎛−−
−=10
10
yyxx
xNy
Nous avons défini une structure « point », constituée de deux variables,
respectivement l’abscisse et l’ordonnée du point considéré. Un vecteur de points, « positionsPossibles », stocke les deux positions où le capteur peut se trouver.
Cette structure comporte également une variable « élection ». Cette variable permet de pallier d’éventuelles erreurs dues aux règles, en stipulant qu’un certain nombre d’ancres doivent définir que la position du capteur est effectivement à ce point. Dans un environnement perturbé où l’on décide malgré tout d’utiliser les règles, il est envisageable qu’un capteur soit localisé au mauvais endroit ; cette variable permet de ne fixer la position du capteur qu’après qu’elle ait été confirmée par plusieurs ancres. Par défaut, la première validation suffit ; dans un environnement sans perturbation il est en effet invraisemblable que la mauvaise des deux positions soit retenue. Ce paramètre est néanmoins modifiable dans le code. Dès lors qu’une règle est capable de trancher entre les deux positions, elle incrémentera la variable élection de ce point. Le capteur ne sera alors pas considéré comme ancre fixe après le succès d’une règle, mais après que le nombre de votes pour ce point ait atteint le seuil désiré.
4.5.3 Cas d'utilisation des règles
Les règles sont fort utiles pour trouver précisément et rapidement la position d’un capteur. Or, il existe des situations où ces règles sont inefficaces. En effet, les règles s’appuient sur les distances estimées entre deux nœuds du réseau. Si ces distances sont erronées, la localisation peut être fortement altérée.
Un écart sensible de distance entre deux nœuds peut paraître insignifiant, mais il sera important sur une somme de distances. Une erreur importante sur la distance estimée entre une ancre et un capteur peut permettre à l’ancre de déterminer la position du capteur à un des deux points, là où la règle utilisée aurait dû être inefficace. Le capteur sera donc considéré comme une ancre fixe à une mauvaise position ; il diffusera ensuite cette position erronée aux autres capteurs et les erreurs vont s’accumuler, produisant un résultat final fortement éloigné de la réalité.
C’est pourquoi il faut s’assurer d’avoir des résultats cohérents sur les mesures
de distances avec les capteurs ; le calcul de distances par RSSI est en effet très sensible aux perturbations : présence de bâtiments entre les capteurs, proximité de matériel émettant des radiations électromagnétiques pouvant perturber les ondes radio, ou à moindre échelle, le taux d’humidité ou la pression atmosphérique. Les règles sont donc à utiliser en priorité sur une topologie réalisée dans un environnement soumis au moins de perturbations possibles.
31
5 Intérêts et ouvertures
Ce projet met en collaboration une entreprise et des chercheurs. Cela montre l’attrait de ce sujet, la localisation dans une zone délimitée afin de limiter de nombreux coûts. Mais aussi cela permet d’ouvrir de nouvelles portes dans le monde de la recherche et sur un plan commercial.
5.1 Enjeux économiques
Nous citerons deux exemples d’applications de la méthode de localisation de capteur dans un réseau interconnectant ces équipements.
Le premier domaine peut être par exemple la surveillance des forêts afin de
prévenir d’une détection de départ de feu. Ainsi, l’alerte peut être donnée avec une grande précision, et permettrait de gagner un temps considérable. Car un des systèmes actuels consiste à placer des miradors où un garde forestier surveille, et prévient les pompiers lorsque de la fumée est visible. Mais dans un premier temps un hélicoptère est envoyé pour repérer exactement où se situent les flammes et pour guider les combattants du feu. Un second domaine, émergeant, consiste à aider les personnes âgées. Il existe actuellement des détecteurs de chute qui lorsqu’ils sont activés déclenchent une alarme. Cependant cela ne donne pas le lieu où la personne est tombée. Dans une maison de retraite par exemple, des capteurs fixes pourraient être placés stratégiquement dans l’enceinte du bâtiment et d’autres, portés par les résidents des lieux, sous forme de bracelet ou collier, reliés aux détecteurs de chute. Ainsi, à tout instant, ces modules de communications peuvent se localiser rapidement, et lorsqu’une personne tombe, une unité centrale pourrait avertir le personnel compétent de l’étage, du numéro de chambre où l’accident s’est produit. Ce système pourrait être couplé à la télésurveillance, actuellement proposée aux personnes âgées, pour qu’elles puissent en bénéficier à leur domicile.
L’utilisation de cette méthode n’est pas limitée aux situations d’urgence, elle peut être appliquée pour un suivi médical
5.2 Les versions futures et besoins
L’implémentation de la méthode AT-Dist est actuellement faite sur un plan en deux dimensions, or pour les applications citées ci-dessus la troisième est nécessaire. Pour cela la matrice deviendrait un cube, les équations ne se limiteraient plus à des cercles mais à des sphères, cependant les principes de la méthode restent inchangés.
Pour appliquer le programme sur des topologies réelles, il est impératif de pouvoir évaluer précisément la distance entre deux capteurs, pour la méthode AT-Dist, ou le nombre de sauts à effectuer pour joindre deux modules de communications. Cela signifie réciproquement, de connaître la formule mathématique permettant le passage d’un niveau de puissance RSSI à des mètres, ou la possibilité de router des messages sans limitation sur le nombre de capteurs à traverser.
32
6 Conclusion
Les TER (Travaux Encadrés de Recherche) universitaires sont généralement réalisés en équipe sous la tutelle d’un ou plusieurs encadrants. Cela permet aux étudiants d’acquérir une expérience dans l’accomplissement d’un objectif en groupe. La mise en commun de compétences, l’interaction de différentes méthodes de travail et la gestion d’une équipe sont en effet des valeurs primordiales dans le monde des entreprises et de la recherche.
La participation de l’entreprise CORONIS dans ce projet lui a donné une dimension supplémentaire. En effet cela ne limite plus le travail à une seule équipe, mais permet une collaboration entre plusieurs groupes aux compétences diverses ; effectivement les ingénieurs de cette société ont pu nous apporter des informations sur des caractéristiques et propriétés électroniques du matériel mis à notre disposition et nous, des connaissances en informatique. Cette relation entre l’entreprise et nous a pu se faire par le biais de M. Alain FOUCARAN qui est aussi un intervenant dans la réalisation de ce projet, au même titre que nos tuteurs, MM. Jean-Claude KÖNIG et Clément SAAD.
En plus d’une collaboration de diverses équipes, nous avons pu réaliser un projet conciliant expériences réelles et programmation. Cela nous a appris à nous adapter à du matériel déjà existant et commercialisé mais également à gérer le délai imparti, fixé par le calendrier de l’UFR, pour la réalisation d’un travail avec toutes les contraintes qui lui sont liées.
Pour que chacun de nous puissent maîtriser toutes les parties que comporte ce sujet, nous nous sommes relayés sur toutes les tâches. Nous n’avons pas voulu créer de groupe fixe, ainsi chaque personne à travaillé avec l’ensemble des autres participants au projet.
Les résultats obtenus à partir de données théoriques se sont révélés concluants, ce qui prouve l’efficacité de la méthode AT-Dist. Pour utiliser l’application à partir de données pratiques, il est nécessaire d’utiliser du matériel permettant de fournir des distances précises entre capteurs.
Malgré l’infructuosité des tests effectués avec le matériel fourni, nous avons
implémenté la méthode AT-Dist qui produit des résultats satisfaisants à partir de données théoriques obtenues sur des topologies fictives. L’évolution de l’application dans un repère tridimensionnel permettrait une commercialisation de la méthode.
33
34
7 ANNEXES
7 Annexes
7.1 Diagramme UML
Main -vector<capteur*> capteurNonAncre -vector<capteur*> ancres -float **matriceAdjacence -int nbSommets -float * distanceDepuisS -int rayon -float echelle -bool utilisationRegles
+atdist(char*) +virtual ~atdist() +virtual void dijkstra(int) +virtual void afficheDistanceS() +virtual void afficherResultats() +virtual void initialisation() +virtual void traiterFichier(char*) +virtual void regles()
Cartographie
-float echelle; -float capteur_x; -float capteur_y; -float capteur_epsilon; -float capteur_rayon; -float capteur_taux; -carte map;
+cartographie(float x, float y, float epsilon, float rayon); +virtual ~cartographie(); +virtual void barycentre(); +virtual void afficheValues(); +virtual void calculEpsilon(); +virtual float getX(); +virtual float getY(); +virtual float getEpsilon(); +virtual float getEchelle(); +virtual float getRayon(); +virtual float getMaxValue(); +virtual void afficheCarte(); +virtual void calculPosition(float, float, float, float); +virtual void setRayon(float r); +virtual void setEchelle(float e); +virtual void affiche_zone(int); +virtual void incr(int, int);
Carte
-TYPE_CASES ** map; -int taille_matrice; -int x0; -int y0; -int x_deb_zone; -int y_deb_zone; -int max_value; -int x_fin_zone; -int y_fin_zone; -int y_taille_zone; -int x_taille_zone; +virtual void incrCourone(int x1,int y1,int r1,int r2); +virtual TYPE_CASES incr(int x,int y); +carte(); +virtual ~carte(); +virtual void affiche_carte(); +virtual TYPE_CASES getValeurCase(int x, int y); +virtual void incrCircle(int x1,int y1,int rayon); +virtual int getXor(); +virtual int getYor(); +virtual void calculDebutZone(int x, int y); +virtual int getXFZ(); +virtual int getYFZ(); +virtual int getXDZ(); +virtual int getYDZ(); +virtual int getXTZ(); +virtual int getYTZ(); +virtual int getMaxValue(); +virtual void affiche_zone(int);
Capteur
-float x; -float y; -float epsilon; -float rayon; -float taux; -int numero; -float echelle; -vector<int> ancresUsed; -vector<voisin> mesVoisins; -vector<point> positionsPossibles; -bool deuxPosCalculees;
+capteur(int=0); +capteur(int,float,float); +virtual ~capteur(); +float getX(); +float getY(); +float getEpsilon(); +float getRayon(); +void setX(float); +void setY(float); +void setEpsilon(float); +void setRayon(float); +void setEchelle(float); +void setRayonDansCartographie(float r); +int getNumero(); +bool isAncre(); +calculPosition(float, float, float, float); +bool nouvelleAncre(float,float,float); +virtual void afficheMap(); +virtual void affiche_zone(); +virtual void ajoutVoisin(float, float, float, float); +virtual bool estVoisin(float, float, float); +virtual bool ancreConnue(int); +virtual void ajoutAncreConnue(int); +virtual void calculDeuxPointsPossibles(); +virtual void regleUne(float, float, float, float); +virtual void regleDeux(float, float, float, float); +virtual void regleTrois(); +virtual void incrementeDeuxPositionsPossibles();
*1..n
35
7.2 Caractéristique du cahier des charges
7.3 Bibliographie
Modes d’emploi des WavePort et WaveTalk fournis par l’entreprise CORONIS.
AT-Dist : A Distributed Method for Localization with High Accuracy in Sensor Networks de M. Clément SAAD.
7.4 Webographie
www.cplusplus.com donne le fonctionnement de grand nombre de classes C++ utilisées fréquemment.
www.developpez.com pour obtenir des exemples sur l’utilisation des
Hashtable et des vecteurs.
http://perso.orange.fr/math.15873/IntCercl.html ce site nous a permis d’implémenter les règles. Code source des programmes
36
7.5 Atdist
7.5.1.1 Atdist.h
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
// main.h: interface for the main class. #ifndef MAIN__H #define MAIN__H #include <string> #include <fstream> #include <iostream> #include <stdio.h> #include <time.h> #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #define INT_MAX_VALUES 65000 /* typedef struct InfoAncre { int num; float x; float y; InfoAncre(float _x, float _y, int n){ x = _x; y = _y; num = n; } }InfoAncre; */ class atdist { private: capteur* tab_capteur; vector<capteur*> capteurNonAncre; vector<capteur*> ancres; float **matriceAdjacence; int nbSommets; float * distanceDepuisS; int rayon; float echelle; bool utilisationRegles; public: //atdist(vector<vector<float > > , vector<InfoAncre>); atdist(char*); virtual ~atdist(); virtual void dijkstra(int); virtual void afficheDistanceS(); virtual void afficherResultats(); virtual void initialisation(); virtual void traiterFichier(char*); virtual void regles(); }; #endif // !defined(AFX_MAIN_H__D4C77B54_240A_4EDC_83B0_AFC81BD03251__INCLUDED_)
37
7.5.1.2 Atdist.cpp
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
#include "capteur.h" #include "main.h" #include <vector> using namespace std; atdist::atdist(char* c){ remove("zone.txt"); rayon = 0; char * reponse = (char*)malloc(sizeof(char)*20); cout << "Desires vous utiliser les regles ? oui (Y/O) ou non (N)" << endl; cin.getline(reponse, sizeof(char)*20); cout << "Programme lance..."<< endl; traiterFichier(c); int stop, start; char * s = new char[50]; int j; for(j=0;j<nbSommets;j++){ tab_capteur[j].setEchelle(echelle); } for(j=0;j<capteurNonAncre.size();j++){ capteurNonAncre[j]->setEpsilon(65000.0); } start = GetTickCount(); utilisationRegles = false; if(reponse[0] == 'Y' || reponse[0] == 'y'|| reponse[0] == 'O' || reponse[0] == 'o') utilisationRegles = true; if(utilisationRegles) { regles(); } stop = GetTickCount(); sprintf(s, "Executed in %d ms", stop - start); cout << "temps execution d'utilisation des regles" << s << endl; /* afficherResultats(); exit(0); //*/ int nb=0; float distance = 0.0; int i=0; start = GetTickCount(); while(!ancres.empty()){ dijkstra(ancres[i]->getNumero()-1); vector<capteur*>::iterator it1=capteurNonAncre.begin(); while(it1!=capteurNonAncre.end()) { distance = distanceDepuisS[(**it1).getNumero()-1];
38
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
//cout<<"distance entre ancre numero : "<<ancres[i]->getNumero()<< " et capteur numero "<< (**it1).getNumero() << " = " << distance<<endl; if(rayon != 0) { ancres[i]->setRayon(rayon); (*it1)->setRayonDansCartographie(rayon); } (*it1)->calculPosition( ancres[i]->getX(), ancres[i]->getY(), distance, ancres[i]->getEpsilon()); (*it1)->afficheMap(); if((**it1).isAncre()) { //(*it1)->affiche_zone();y //cout<<"nouvelle ancre numero = "<<(*it1)->getNumero()<<endl; ancres.push_back(*it1); it1=capteurNonAncre.erase(it1); /*if(utilisationRegles) regles(); */ } else it1++; nb++; } ancres.erase(ancres.begin()); } afficherResultats(); stop = GetTickCount(); sprintf(s, "Executed in %d ms", stop - start); cout << "\ntemps execution calcul position : " << s << endl; } atdist::~atdist(){ } void atdist::dijkstra(int s){ initialisation(); //tableau qui contient tous les sommets au depart et que l'on vide ?chaque tour de boucle vector<int> Sbarre; //on place tous les sommets dans ce tableau for(int z = 0; z < nbSommets; z++) Sbarre.push_back(z); int u, minArcs; //initialisation this->distanceDepuisS[s] = 0; int tmpi; int tmpj; float poidtmp;
39
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
int index, nb; //tant que le tableau contenant les sommets n'est pas vide while(Sbarre.size() != 0) { minArcs = INT_MAX_VALUES; u = INT_MAX_VALUES; vector<int>::iterator iti; nb = 0; //on recherche le sommet ayant la distance entre la source et un sommet minimale for(iti = Sbarre.begin(); iti < Sbarre.end(); iti++) { tmpi = *iti; if(this->distanceDepuisS[tmpi] < minArcs) { index = nb; u = tmpi; minArcs = this->distanceDepuisS[u]; }//fin if nb++; }//Fin for //on supprime ce sommet du tableau Sbarre.erase(Sbarre.begin()+index); vector<int>::iterator itj; //on va mettre a jour, si besoin est, tous les sommets contenu dans le tableau et ayant //un arcs avec le sommet u trouv?precedement. for(itj = Sbarre.begin(); itj < Sbarre.end(); itj++) { tmpj = *itj; //test de l'?istance d'un arc(u,v) if(this->matriceAdjacence[u][tmpj] != 0) { poidtmp = this->distanceDepuisS[u]+this->matriceAdjacence[u][tmpj]; //si le poids de l'arc(u,v) + la distance de la source ?u est inferieur ?la distance //de la source au sommet v if(this->distanceDepuisS[tmpj] > poidtmp) { this->distanceDepuisS[tmpj] = poidtmp; }//fin if }//fin du if }//Fin for du parcour de Sbarre }//fin while }//fin de la methode Dijkstra void atdist::afficheDistanceS(){ for(int i = 0; i < nbSommets; i++) { cout << "le sommet(index) numero : " << i <<" est a distance : " << distanceDepuisS[i] << endl; } } void atdist::initialisation(){ //i les lignes et j les colonnes for (int i=0;i<nbSommets;i++) {
40
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
this->distanceDepuisS[i] = INT_MAX_VALUES; //les distance entre i et la source est ?l'infini }//fin for }//fin de la methode init void atdist::afficherResultats(){ for(int i =0; i < nbSommets; i++) { cout << "capteur : " << tab_capteur[i].getNumero() << " x : " << tab_capteur[i].getX() << " y : " << tab_capteur[i].getY() << " e : " << tab_capteur[i].getEpsilon() << endl; } }//fin de la methode afficherResultats void atdist::traiterFichier(char * nameFile){ // le constructeur de ifstream permet d'ouvrir un fichier en lecture ifstream fichier(nameFile); bool lectureancre = true; int pos,pos2,longu,larg; string ligne; // variable contenant chaque ligne lue int count = 0; if ( fichier ) // ce test échoue si le fichier n'est pas ouvert { string num; //longueur getline( fichier, ligne ); getline( fichier, ligne ); longu=atoi(ligne.c_str()); //largeur getline( fichier, ligne ); getline( fichier, ligne ); larg=atoi(ligne.c_str()); if(longu>larg) echelle = 1000.0/(float)longu; else echelle = 1000.0/(float)larg; //rayon getline( fichier, ligne ); getline( fichier, ligne ); rayon = atoi(ligne.c_str()); // cette boucle s'arrête dès qu'une erreur de lecture survient while ( getline( fichier, ligne ) && lectureancre) { if(isdigit(ligne[0])) { pos = ligne.find("\t"); num.assign(ligne, 0, pos); if(atoi(num.c_str()) > nbSommets) nbSommets = atoi(num.c_str()); pos2 = ligne.find("\t",pos+1); num.assign(ligne, pos+1, pos2); if(atoi(num.c_str()) > nbSommets) nbSommets = atoi(num.c_str()); } else if(ligne.find("Ancre") != string::npos) lectureancre = false;
41
237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
}//fin while }//fin if fichier.close(); ifstream fic(nameFile); if ( fic ) // ce test échoue si le fichier n'est pas ouvert { //allocation mémoire matriceAdjacence = new float*[nbSommets]; for (int i=0;i<nbSommets;i++) matriceAdjacence[i] = new float[nbSommets]; for(int z = 0; z < nbSommets; z++) for(int j = 0; j < nbSommets; j++) matriceAdjacence[z][j] = 0; distanceDepuisS = new float[nbSommets]; initialisation(); tab_capteur = new capteur[nbSommets]; //fin allocation mémoire //longueur getline( fic, ligne ); getline( fic, ligne ); //largeur getline( fic, ligne ); getline( fic, ligne ); //rayon getline( fic, ligne ); getline( fic, ligne ); lectureancre = false; //ceration de la matrice de distance while ( getline( fic, ligne )) { // afficher la ligne à l'écran int i = 0; if(isdigit(ligne[0]) && !lectureancre) { pos = ligne.find("\t"); string src; string dest; string dist; src.assign(ligne, 0, pos); ligne.erase(0, pos+1); pos = ligne.find("\t"); dest.assign(ligne, 0, pos); ligne.erase(0, pos+1); dist = ligne; matriceAdjacence[atoi(src.c_str())-1][atoi(dest.c_str())-1] = atof(dist.c_str()); matriceAdjacence[atoi(dest.c_str())-1][atoi(src.c_str())-1] = atof(dist.c_str()); } else if(ligne.find("Ancre") != string::npos) { lectureancre = true; for(int y = 1; y <= nbSommets; y++) tab_capteur[y-1] = capteur(y); }
42
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
else if(lectureancre) { int i = 0; if(isdigit(ligne[0])) { pos = ligne.find("\t"); string ancre; string x; string y; ancre.assign(ligne, 0, pos); ligne.erase(0, pos+1); pos = ligne.find("\t"); x.assign(ligne, 0, pos); ligne.erase(0, pos+1); y = ligne; tab_capteur[atoi(ancre.c_str()) - 1].setX(atof(x.c_str())); tab_capteur[atoi(ancre.c_str()) - 1].setY(atof(y.c_str())); tab_capteur[atoi(ancre.c_str()) - 1].setEpsilon(0); ancres.push_back(&tab_capteur[atoi(ancre.c_str()) - 1]); }//fin if }//fin else }//fin while }//fin if fic.close(); bool trouve = false; for(int a = 0; a < nbSommets; a++) { trouve = false; vector<capteur*>::iterator iti; for(iti = ancres.begin(); iti < ancres.end(); iti++) { if((**iti).getNumero() == (a+1)) trouve = true; }//Fin for if(!trouve) capteurNonAncre.push_back(&tab_capteur[a]); } }//fin de la methode traitementFichier void atdist::regles() { bool modification = true; //On ajoute à chaque capteur ses voisins ancres while(modification) { modification = false; vector<capteur*>::iterator it=capteurNonAncre.begin(); while(it!=capteurNonAncre.end()) { dijkstra((*it)->getNumero()-1); if(rayon != 0) { (*it)->setRayonDansCartographie(rayon); } int nb_voisins = 0; int g = (*it)->getNumero()-1;
43
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416
int iif=0; for(int j=0;j<ancres.size();j++) { if( matriceAdjacence[g][ancres[j]->getNumero()-1]>0 && !tab_capteur[g].ancreConnue(ancres[j]->getNumero()) ) { tab_capteur[g].ajoutVoisin(tab_capteur[ancres[j]->getNumero()-1].getX(), tab_capteur[ancres[j]->getNumero()-1].getY(), matriceAdjacence[g][ancres[j]->getNumero()-1],tab_capteur[ancres[j]->getNumero()-1].getEpsilon()); tab_capteur[g].ajoutAncreConnue(ancres[j]->getNumero()); nb_voisins++; } } //Si on a au moins deux voisins, on calcule les positions possibles if(nb_voisins>=2) { tab_capteur[g].calculDeuxPointsPossibles(); //Si on en a un troisième on peut directement déterminer la position if(nb_voisins>=3 && tab_capteur[g].getEpsilon()!=0) { tab_capteur[g].regleTrois(); if(tab_capteur[g].getEpsilon()==0) { //cout<<"nouvelle ancre numero = "<<tab_capteur[g].getNumero()<<endl; ancres.push_back(&tab_capteur[g]); it = capteurNonAncre.erase(it); modification = true; } }//fin if for(int a=0;a<ancres.size() && (tab_capteur[g].getEpsilon()!=0);a++) { if(!tab_capteur[g].ancreConnue(ancres[a]->getNumero())&& tab_capteur[g].getEpsilon()!=0) { tab_capteur[g].ajoutAncreConnue(a); tab_capteur[g].regleUne(ancres[a]->getX(),ancres[a]->getY(), distanceDepuisS[ancres[a]->getNumero()-1], ancres[a]->getEpsilon()); if(tab_capteur[g].getEpsilon()==0) { ancres.push_back(&tab_capteur[g]); it = capteurNonAncre.erase(it); modification = true; } else { tab_capteur[g].regleDeux(ancres[a]->getX(),ancres[a]->getY(), distanceDepuisS[ancres[a]->getNumero()-1], ancres[a]->getEpsilon()); if(tab_capteur[g].getEpsilon()==0) { ancres.push_back(&tab_capteur[g]); it = capteurNonAncre.erase(it); modification = true; }//fin if
44
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
}//fin else }//fin if }//fin for if(tab_capteur[g].getEpsilon()!=0) it++; }//fin if else { it++; } }//fin while }//fin while } void genererGraphe(int nb_sommets, int nb_ancres, int r) { point *positions_capteurs = new point[nb_sommets]; FILE *coord, *reseau; coord = fopen("coord.txt","w"); reseau = fopen("reseau.txt","w"); srand(time(NULL)); int encours = 0; int x =0,y=0; int num_capteur; float distance; bool position_correcte; fprintf(reseau,"Longueur\n1000\nLargeur\n1000\nRayon\n%d\nOrigine\tDestination\tDistance réelle\n",r); //coordonnées du premier point x = positions_capteurs[encours].x = rand()%1000; y = positions_capteurs[encours].y = rand()%1000; fprintf(coord,"Capteur\tX\tY\n"); fprintf(coord,"%d\t%d\t%d\n",encours+1,x,y); encours++; while(encours<nb_sommets) { position_correcte = false; while(!position_correcte) { //le capteur ajouté doit être dans le rayon d'action d'un capteur existant if(encours-1 == 0) num_capteur = 0; else num_capteur = rand()%(encours-1); x = (rand()%(r*2))-r+positions_capteurs[num_capteur].x; y = (rand()%(r*2))-r+positions_capteurs[num_capteur].y; distance = sqrt(pow(positions_capteurs[num_capteur].x-x,2)+pow(positions_capteurs[num_capteur].y-y,2)); if(distance<=r && x>0 && y>0 && x<1000 && y<1000) position_correcte = true; } positions_capteurs[encours].x = x; positions_capteurs[encours].y = y; fprintf(coord,"%d\t%d\t%d\n",encours+1,x,y); for(int i=0;i<encours;i++) { distance = sqrt(pow(positions_capteurs[encours].x-positions_capteurs[i].x,2)+ pow(positions_capteurs[encours].y-positions_capteurs[i].y,2)); if(distance<=r) { fprintf(reseau,"%d\t%d\t%f\n",encours+1,i+1,distance); } }
45
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
encours++; } fclose(coord); fprintf(reseau,"Ancres\tCoord_x\tCoord_y\n"); int ancres_creees = 0; int num; bool trouve; int *ancres = new int[nb_ancres]; while(ancres_creees<=nb_ancres) { num = rand()%nb_sommets; trouve = false; for(int i=0;i<ancres_creees && !trouve;i++) { if(num==ancres[i]) trouve = true; } if(!trouve) { ancres[ancres_creees] = num; ancres_creees++; fprintf(reseau,"%d\t%f\t%f\n",num+1,positions_capteurs[num].x,positions_capteurs[num].y); } } fclose(reseau); } int main(){ cout<<"Voulez-vous generer un graphe aleatoire ?(o/n)"<<endl; char * reponse = (char*)malloc(sizeof(char)*50); cin.getline(reponse, sizeof(char)*50); if(reponse[0] == 'Y' || reponse[0] == 'y'|| reponse[0] == 'O' || reponse[0] == 'o') { int nbS = 0; while(nbS == 0) { cout<<"Combien de sommets voulez-vous generer ?"<<endl; cin.getline(reponse, sizeof(char)*50); nbS = atoi(reponse); if(nbS == 0) cout<<"Veuillez entrer un nombre de sommets superieur à 0 !"<<endl; } int nbA = 0; while(nbA == 0) { cout<<"Combien d'ancres voulez-vous dans le graphe ?"<<endl; cin.getline(reponse, sizeof(char)*50); nbA = atoi(reponse); if(nbA == 0 && nbA<=nbS) cout<<"Veuillez entrer un nombre d'ancres superieur à 0 et inferieur au nombre de sommets !"<<endl; } int rayon = 0; while(rayon == 0) { cout<<"Quel est le rayon d'emission des capteurs ?"<<endl; cin.getline(reponse, sizeof(char)*50); rayon = atoi(reponse); if(nbA == 0) cout<<"Veuillez entrer un rayon superieur à 0 !"<<endl; } genererGraphe(nbS,nbA,rayon); new atdist("reseau.txt"); } else {
46
537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
bool erreur = true; while(erreur) { erreur = false; cout<<"Veuillez entrer le nom du fichier a traiter : "<<endl; cin.getline(reponse, sizeof(char)*50); FILE *f; if((f = fopen(reponse,"r"))==NULL) { cout<<"Nom de fichier incorrect !"<<endl; erreur = true; } else { fclose(f); new atdist(reponse); } } } return 0; }//fin main
47
7.5.2 Capteur
7.5.2.1 Capteur.h
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
// capteur.h: interface for the capteur class. // ////////////////////////////////////////////////////////////////////// #ifndef CAPTEUR__H #define CAPTEUR__H #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #define INT_MAX_VALUES 65000 #define ELECTION 5 #include "cartographie.h" #include <math.h> #include <time.h> typedef struct point{ float x; float y; int election; }point; typedef struct voisin{ float x; float y; float distance; float epsilon; }voisin; class capteur { private: float x; float y; float epsilon; float rayon; float taux; cartographie *carto; int numero; float echelle; //vecteur contenant les ancres à partir desquelles les règles ont été appliquées vector<int> ancresUsed; //tableau contenant les deux points possibles vector<voisin> mesVoisins; vector<point> positionsPossibles; bool deuxPosCalculees; public: capteur(int=0); capteur(int,float,float);
48
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
virtual ~capteur(); float getX(); float getY(); float getEpsilon(); float getRayon(); void setX(float); void setY(float); void setEpsilon(float); void setRayon(float); void setEchelle(float); void setRayonDansCartographie(float r); int getNumero(); /*reçoit les coordonnées d'une nouvelle ancre, *affine sa position et retourne true si *il devient une ancre à son tour */ bool isAncre(); calculPosition(float, float, float, float); bool nouvelleAncre(float,float,float); virtual void afficheMap(); virtual void affiche_zone(); /*méthodes relatives aux règles*/ virtual void ajoutVoisin(float, float, float, float); virtual bool estVoisin(float, float, float); virtual bool ancreConnue(int); virtual void ajoutAncreConnue(int); virtual void calculDeuxPointsPossibles(); virtual void regleUne(float, float, float, float); virtual void regleDeux(float, float, float, float); virtual void regleTrois(); }; #endif // !defined(AFX_CAPTEUR_H__A959A1B2_C51A_4A7E_9B71_11977D5718BD__INCLUDED_)
49
7.5.2.2 Capteur.cpp
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
// capteur.cpp: implementation of the capteur class. // ////////////////////////////////////////////////////////////////////// #include "capteur.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// //ne sait pas où il se trouve capteur::capteur(int num) { x = 0; y = 0; numero = num; rayon = 10.0; taux = (float)0.10; epsilon = 65000; carto = new cartographie(0, 0, epsilon, rayon); deuxPosCalculees = false; } //cas ancres juste capteur::capteur(int num, float _x,float _y) { numero = num; rayon = (float)10.0; epsilon = 0; x = _x; y = _y; taux = (float)0.10; } capteur::~capteur() { } float capteur :: getX() {return x;} float capteur::getY() {return y;} float capteur::getEpsilon() {return epsilon;} float capteur::getRayon() {return rayon;} int capteur::getNumero() {return numero;} void capteur::setX(float _x) {x = _x;} void capteur::setY(float _y) {y = _y;} void capteur::setEpsilon(float e) {epsilon = e;} void capteur::setRayon(float r) {rayon = r;}
50
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
void capteur::setRayonDansCartographie(float r) {rayon = r; carto->setRayon(r);} void capteur::setEchelle(float e) { echelle = e; carto->setEchelle(e); } void capteur::afficheMap(){ carto->afficheCarte(); }//fin de la methode afficheMap capteur::calculPosition(float _x, float _y, float _r,float _epsilon){ carto->calculPosition(_x,_y,_r,_epsilon); x = carto->getX(); y = carto->getY(); epsilon = carto->getEpsilon(); if(numero==6) carto->afficheValues(); } bool capteur::isAncre() { if(carto->getEpsilon() <= taux /*&& carto->getMaxValue() >= 3*/) //???????????????? return true; else return false; }//fin de la methode nouvelleAncre void capteur::affiche_zone() { carto->affiche_zone(numero); } /**Méthodes relatives aux règles**/ void capteur::ajoutVoisin(float _x, float _y, float d, float _e) { voisin tmp; tmp.x = _x; tmp.y = _y; tmp.distance = d; tmp.epsilon = _e; mesVoisins.push_back(tmp); } bool capteur::estVoisin(float _x, float _y, float dist) { bool trouve = false; for(int i=0;i<mesVoisins.size() && !trouve;i++) { if(mesVoisins[i].x == _x && mesVoisins[i].y == _y && mesVoisins[i].distance == dist) trouve = true; } return trouve; }
51
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
void capteur::ajoutAncreConnue(int num) { ancresUsed.push_back(num); } bool capteur::ancreConnue(int num) { bool trouve = false; for(int i=0;i<ancresUsed.size() && !trouve;i++) { if(ancresUsed[i] == num) trouve = true; } return trouve; } void capteur::calculDeuxPointsPossibles() { if(!deuxPosCalculees) { srand(time(NULL)); int v1 = rand()%mesVoisins.size(); int v2 = rand()%mesVoisins.size(); while(v2==v1) v2 = rand()%mesVoisins.size(); float tmp1 = mesVoisins[v1].y; float tmp2 = mesVoisins[v2].y; if(((int)(mesVoisins[v1].y - mesVoisins[v2].y)) != 0) { float A,B,C,N; N = (pow(mesVoisins[v2].distance,2) - pow(mesVoisins[v1].distance,2) - pow(mesVoisins[v2].x,2) + pow(mesVoisins[v1].x,2) - pow(mesVoisins[v2].y,2) + pow(mesVoisins[v1].y,2))/ (2 * (mesVoisins[v1].y - mesVoisins[v2].y)); A = pow((mesVoisins[v1].x-mesVoisins[v2].x)/ (mesVoisins[v1].y-mesVoisins[v2].y),2)+1; B = (2*(mesVoisins[v1].y-N))*(mesVoisins[v1].x- mesVoisins[v2].x)/ (mesVoisins[v1].y-mesVoisins[v2].y) - 2*mesVoisins[v1].x; C = pow(mesVoisins[v1].x,2) + pow(mesVoisins[v1].y,2) + pow(N,2) - pow(mesVoisins[v1].distance,2) - 2*N*mesVoisins[v1].y; float racine_delta; racine_delta = sqrt((pow(B,2)) - 4*A*C); point PA; PA.x = (-B + racine_delta) / (2*A); PA.y = N - (PA.x * ((mesVoisins[v1].x-mesVoisins[v2].x)/ (mesVoisins[v1].y-mesVoisins[v2].y))); PA.election = 0; point PAprime; PAprime.x = (-B - racine_delta) / (2*A); PAprime.y = N - (PAprime.x * ((mesVoisins[v1].x-mesVoisins[v2].x)/ (mesVoisins[v1].y-mesVoisins[v2].y))); PAprime.election = 0; positionsPossibles.push_back(PA);
52
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
positionsPossibles.push_back(PAprime); deuxPosCalculees = true; } else if(((int)(mesVoisins[v1].y - mesVoisins[v2].y)) == 0) { point PA; PA.x = (pow(mesVoisins[v2].distance, 2) - pow(mesVoisins[v1].distance, 2) - pow(mesVoisins[v2].x, 2) + pow(mesVoisins[v1].x, 2) - pow(mesVoisins[v2].y, 2) + pow(mesVoisins[v1].y, 2))/ (2 * (mesVoisins[v1].x - mesVoisins[v2].x)); PA.y = - sqrt( pow(mesVoisins[v2].distance, 2) - pow((mesVoisins[v2].x - PA.x),2)) + mesVoisins[v2].y; PA.election = 0; point PAprime; PAprime.x = PA.x; PAprime.y = sqrt( pow(mesVoisins[v1].distance, 2) - pow((mesVoisins[v1].x - PAprime.x),2)) + mesVoisins[v1].y; PAprime.election = 0; positionsPossibles.push_back(PA); positionsPossibles.push_back(PAprime); deuxPosCalculees = true; } }//fin if } void capteur::regleUne(float _x, float _y, float dist, float _epsilon) { float distanceA = sqrt(pow(_x - positionsPossibles[0].x,2)+pow(_y - positionsPossibles[0].y,2)); float distanceAprime = sqrt(pow(_x - positionsPossibles[1].x,2)+pow(_y - positionsPossibles[1].y,2)); if(distanceA > rayon + _epsilon && distanceA <= (dist - _epsilon) && (distanceAprime > (dist + _epsilon) || distanceAprime <= rayon - _epsilon)) { positionsPossibles[0].election++; if(positionsPossibles[0].election-positionsPossibles[1].election == ELECTION) { epsilon = 0; x = positionsPossibles[0].x; y = positionsPossibles[0].y; } } else if(distanceAprime > rayon + _epsilon && distanceAprime <= (dist - _epsilon) && (distanceA > (dist + _epsilon) || distanceA <= rayon - _epsilon)) { positionsPossibles[1].election++; if(positionsPossibles[1].election-positionsPossibles[0].election == ELECTION) { epsilon = 0; x = positionsPossibles[1].x; y = positionsPossibles[1].y; } } } void capteur::regleDeux(float _x, float _y, float dist, float _epsilon) { float distanceA = sqrt(pow(_x - positionsPossibles[0].x,2)+pow(_y - positionsPossibles[0].y,2));
53
238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289
float distanceAprime = sqrt(pow(_x - positionsPossibles[1].x,2)+pow(_y - positionsPossibles[1].y,2)); if((distanceA <= rayon - mesVoisins[2].epsilon) && (distanceAprime > rayon + mesVoisins[2].epsilon)){ positionsPossibles[1].election++; if(positionsPossibles[1].election-positionsPossibles[0].election == ELECTION) { x = positionsPossibles[1].x; y = positionsPossibles[1].y; epsilon = 0; } } else if((distanceAprime <= rayon - mesVoisins[2].epsilon) && (distanceA > rayon + mesVoisins[2].epsilon)){ positionsPossibles[0].election++; if(positionsPossibles[0].election-positionsPossibles[1].election == ELECTION) { x = positionsPossibles[0].x; y = positionsPossibles[0].y; epsilon = 0; } } } void capteur::regleTrois() { float precision = 0.3f; float distanceA = sqrt(pow(mesVoisins[2].x - positionsPossibles[0].x,2)+ pow(mesVoisins[2].y - positionsPossibles[0].y,2)); float distanceAprime = sqrt(pow(mesVoisins[2].x - positionsPossibles[1].x,2)+ pow(mesVoisins[2].y - positionsPossibles[1].y,2)); if((distanceA <= rayon - mesVoisins[2].epsilon) && (distanceAprime > rayon + mesVoisins[2].epsilon)){ positionsPossibles[0].election++; if(positionsPossibles[0].election-positionsPossibles[1].election == ELECTION) { x = positionsPossibles[0].x; y = positionsPossibles[0].y; epsilon = 0; } } else if((distanceAprime <= rayon - mesVoisins[2].epsilon) && (distanceA > rayon + mesVoisins[2].epsilon)){ positionsPossibles[1].election++; if(positionsPossibles[1].election-positionsPossibles[0].election == ELECTION) { x = positionsPossibles[1].x; y = positionsPossibles[1].y; epsilon = 0; } } }
54
7.5.3 Carte
7.5.3.1 Carte.h
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
// carte.h: interface for the carte class. // ////////////////////////////////////////////////////////////////////// #ifndef AFX_CARTE_H #define AFX_CARTE_H #include <vector> #include <iostream> #include<math.h> #include<stdio.h> #include <windows.h> using namespace std; #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #define INT_MAX_VALUES 65000 #define TYPE_CASES short class carte { public: int count; private: TYPE_CASES ** map; int taille_matrice; int x0; int y0; int x_deb_zone; int y_deb_zone; int max_value; int x_fin_zone; int y_fin_zone; int y_taille_zone; int x_taille_zone; public: virtual void incrCourone(int x1,int y1,int r1,int r2); //virtual TYPE_CASES& allocationMemoire(int x,int y); virtual TYPE_CASES incr(int x,int y); carte(); virtual ~carte(); virtual void affiche_carte(); virtual TYPE_CASES getValeurCase(int x, int y); virtual void incrCircle(int x1,int y1,int rayon); virtual int getXor(); virtual int getYor(); virtual void calculDebutZone(int x, int y); virtual int getXFZ(); virtual int getYFZ(); virtual int getXDZ();
55
55 56 57 58 59 60 61 62
virtual int getYDZ(); virtual int getXTZ(); virtual int getYTZ(); virtual int getMaxValue(); virtual void affiche_zone(int); };//fin de la classe carte #endif // !defined(AFX_CARTE_H)
56
7.5.3.2 Carte.cpp
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
// carte.cpp: implementation of the carte class. // ////////////////////////////////////////////////////////////////////// #include "carte.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// carte::carte(){ count=0; x_deb_zone = 0; y_deb_zone = 0; max_value = 0; x_fin_zone = 0; y_fin_zone = 0; x_taille_zone = 0; y_taille_zone = 0; taille_matrice = 1000; map = new TYPE_CASES *[taille_matrice]; for(int i = 0; i < taille_matrice; i++){ map[i] = new TYPE_CASES [taille_matrice]; for(int j = 0; j < taille_matrice; j++) map[i][j] = 0; } }//fin constructeur carte::~carte(){ }//fin destructeur void carte::affiche_carte(){ /* //cout<<endl; FILE * fic = fopen("carte.txt", "w"); int x, y; for (x = 0; x < taille_matrice; x++){ fprintf(fic, "["); //cout<<"[ "; for(y = 0; y < taille_matrice; y++){ fprintf(fic, "%u ", map[x][y]); //cout<<map[x][y]<<" "; }//fin for fprintf(fic, "]\n"); //cout<<"] "<<endl; }//fin for fclose(fic); //cout<<endl; //*/ }//fin de la methode affiche_carte void carte::affiche_zone(int n) { char nom[50];
57
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
sprintf(nom,"zone capteur %d.txt",n); FILE * fic = fopen(nom, "w"); int x, y; for (x = x_deb_zone; x < x_fin_zone; x++){ fprintf(fic, "["); for(y = y_deb_zone; y < y_fin_zone; y++){ fprintf(fic, "%u ", map[x][y]); }//fin for fprintf(fic, "]\n"); }//fin for fclose(fic); } TYPE_CASES carte::incr(int x, int y){ map[x][y] = map[x][y] + 1; TYPE_CASES toReturn = map[x][y]; calculDebutZone(x, y); return toReturn; }//fin de la methode incr TYPE_CASES carte::getValeurCase(int x, int y){ TYPE_CASES toReturn = map[x][y]; return toReturn; }//fin de la methode getValeurCase void carte::incrCircle(int x1,int y1, int rayon){ for(int x=x1;x<=x1+rayon;x++){ for( int y=y1; (int)pow(x-x1,2)+(int)pow(y-y1,2)<=(int)pow(rayon,2) ; y++){ incr(x ,y); if (x1!=(2*x1)-x-1){ incr( (2*x1)-x-1,y); if (y1!=2*y1-y-1) incr(2*x1-x -1 ,2*y1-y-1); } if (y1!=2*y1-y-1) incr(x ,(2*y1)-y-1); } } }//fin de la méthode incrCercle void carte::incrCourone(int x1, int y1, int r1, int r2){ int rayon_petit=(r1<r2)?r1:r2; int rayon_grand=(r1>r2)?r1:r2; for(int x=x1+rayon_grand;x>=x1;x--){ double tmp=(sqrt((double)(pow(rayon_petit,2)-pow(x-x1,2))) + sqrt((double)(pow(rayon_petit,2)-pow(x+1-x1,2))))/2; if(x == x1) tmp++; for( int y=((x)>=(x1+rayon_petit))?y1:(y1+tmp) ; (int)pow(x-x1,2)+(int)pow(y-y1,2)<=(int)pow(rayon_grand,2) ; y++){ if(y>=0 && y<taille_matrice){ if (x>=0 && x<taille_matrice){ incr(x ,y); }
58
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
if ((2*x1)-x-1>=0 && (2*x1)-x-1<taille_matrice){ incr( (2*x1)-x-1,y); } } if (2*y1-y-1>=0 && 2*y1-y-1<taille_matrice){ if (2*x1-x -1>=0 && 2*x1-x -1<taille_matrice){ incr(2*x1-x -1 ,2*y1-y-1); } if (x>=0 && x<taille_matrice){ incr(x ,(2*y1)-y-1); } } } }//fin for }//fin de la méthode incrCourone int carte::getXor(){return x0;} int carte::getYor(){return y0;} void carte::calculDebutZone(int x, int y){ if(getValeurCase(x, y) == max_value) { if(x < x_deb_zone) x_deb_zone = x; if(x > x_fin_zone) x_fin_zone = x; if(y < y_deb_zone) y_deb_zone = y; if(y > y_fin_zone) y_fin_zone = y; }//fin du if qui regarde si la valeur de la case demandee est egale à max_value else if(getValeurCase(x, y) > max_value) { max_value = getValeurCase(x, y); x_deb_zone = x; y_deb_zone = y; x_fin_zone = x; y_fin_zone = y; }//fin du if qui regarde si la valeur de la case demandee est superieur à max_value x_taille_zone = x_fin_zone - x_deb_zone + 1; y_taille_zone = y_fin_zone - y_deb_zone + 1; }//fin de la methode calculDebutZone int carte::getXFZ(){ return x_fin_zone;} int carte::getYFZ(){ return y_fin_zone;} int carte::getXDZ(){ return x_deb_zone;}
59
178 179 180 181 182 183 184
int carte::getYDZ(){ return y_deb_zone;} int carte::getXTZ(){ return x_taille_zone;} int carte::getYTZ(){ return y_taille_zone;} int carte::getMaxValue(){ return max_value;}
60
7.5.4 Cartographie
7.5.4.1 Cartographie.h
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
// cartographie.h: interface for the cartographie class. // ////////////////////////////////////////////////////////////////////// #ifndef CARTOGRAPHIE__H #define CARTOGRAPHIE__H #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 //#include "capteur.h" #include "carte.h" #include "iostream" #define INT_MAX_VALUES 65000 class cartographie { private: float echelle; float capteur_x; float capteur_y; float capteur_epsilon; float capteur_rayon; float capteur_taux; carte map; public: cartographie(float x, float y, float epsilon, float rayon); virtual ~cartographie(); virtual void barycentre(); virtual void afficheValues(); virtual void calculEpsilon(); virtual float getX(); virtual float getY(); virtual float getEpsilon(); virtual float getEchelle(); virtual float getRayon(); virtual float getMaxValue(); virtual void afficheCarte(); virtual void calculPosition(float, float, float, float); virtual void setRayon(float r); virtual void setEchelle(float e); virtual void affiche_zone(int); virtual void incr(int, int); };//fin de la classe cartographie #endif
61
7.5.4.2 Cartographie.cpp
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
// cartographie.cpp: implementation of the cartographie class. // ////////////////////////////////////////////////////////////////////// #include "cartographie.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// cartographie::cartographie(float x, float y, float epsilon, float rayon){ capteur_x = x; capteur_y = y; capteur_epsilon = epsilon; capteur_rayon = rayon; }//fin constructeur void cartographie::barycentre(){ float x_bary=0,y_bary=0; int poids_bary =0; for(int i=map.getXDZ();i<=map.getXDZ()+map.getXTZ();i++) { if (i>=0 && i<1000){ for(int j=map.getYDZ();j<=map.getYDZ()+map.getYTZ();j++) { if (j>=0 && j<1000){ if(map.getValeurCase(i,j)==map.getMaxValue()) { capteur_x = (capteur_x*poids_bary+i+0.5)/(poids_bary+1); capteur_y = (capteur_y*poids_bary+j+0.5)/(poids_bary+1); poids_bary++; } } } } } capteur_x = capteur_x / echelle; capteur_y = capteur_y / echelle; }//fin de la methode barycentre cartographie::~cartographie(){ }//fin destructeur void cartographie::afficheValues(){ /* cout << "max values : " << map.getMaxValue() << endl; cout<<"--------------------------------"<<endl; cout << "x debut zone : " << map.getXDZ()/echelle << endl; cout << "y debut zone : " << map.getYDZ()/echelle << endl; cout << "x fin zone : " << map.getXFZ()/echelle << endl; cout << "y fin zone : " << map.getYFZ()/echelle << endl; cout << "largeur zone (x) : " << map.getXTZ()/echelle << endl; cout << "hauteur zone (y): " << map.getYTZ()/echelle << endl; cout<<"--------------------------------"<<endl; cout << "epsilon : " << capteur_epsilon << endl; cout<<"--------------------------------"<<endl;
62
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
cout << "barycentre x : " << capteur_x <<endl; cout << "barycentre y : " << capteur_y <<endl; //*/ /* FILE * fic = fopen("zone.txt", "a"); fprintf(fic, "max values : %d\n" , map.getMaxValue()); fprintf(fic, "--------------------------------\n"); fprintf(fic, "x debut zone : %d\n", map.getXDZ()); fprintf(fic, "y debut zone : %d\n", map.getYDZ()); fprintf(fic, "x fin zone : %d\n", map.getXFZ()); fprintf(fic, "y fin zone : %d\n", map.getYFZ()); fprintf(fic, "largeur zone (x) : %d\n", map.getXTZ()); fprintf(fic, "hauteur zone (y): %d\n", map.getYTZ()); fprintf(fic, "--------------------------------\n"); fprintf(fic, "X0 : %d\n", map.getXor()); fprintf(fic, "Y0 : %d\n", map.getYor()); fprintf(fic, "--------------------------------\n"); fprintf(fic, "epsilon : %d\n", capteur_epsilon); fprintf(fic, "--------------------------------\n"); fprintf(fic, "barycentre x : %d\n", capteur_x); fprintf(fic, "barycentre y : %d\n", capteur_y); fprintf(fic, "--------------------------------\n"); fprintf(fic, "\n\n"); fclose(fic); //*/ }//fin de la methode afficheValues //*/ void cartographie::calculEpsilon(){ int distancetmp; int epsilon = 0; int compteur_x =0, compteur_y=0; for(int x = map.getXDZ(); x <= map.getXFZ(); x++) { compteur_x++; compteur_y=0; for(int y = map.getYDZ(); y <= map.getYFZ(); y++) { if(map.getValeurCase(x,y)==map.getMaxValue()){ distancetmp = sqrt((double)(pow(x-capteur_x,2)+pow(y-capteur_y,2))); if(distancetmp > epsilon){ epsilon = distancetmp; } } compteur_y++; }//fin for qui parcours les y }//fin du for qui parcours les x*/ capteur_epsilon = epsilon/(echelle*echelle*capteur_rayon);//echelle*(echelle*rayon) pour avoir le rayon a l'echelle }//fin de la methode calculEpsilon float cartographie::getX(){return capteur_x;} float cartographie::getY(){return capteur_y;}
63
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
float cartographie::getEpsilon(){return capteur_epsilon;} float cartographie::getRayon(){return capteur_rayon;} float cartographie::getMaxValue(){ return map.getMaxValue();} void cartographie::setEchelle(float e){ echelle=e; } float cartographie::getEchelle(){ return echelle; } void cartographie::afficheCarte(){ map.affiche_carte(); }//fin de la methode afficheCarte void cartographie::calculPosition(float x,float y,float r, float e){ if(r > capteur_rayon) { map.incrCourone( (int)(x*echelle), (int)(y*echelle), (int)(capteur_rayon*echelle) - 1, (int)(r*echelle) + 1 +e*echelle*echelle*capteur_rayon); } else { map.incrCourone( (int)(x*echelle), (int)(y*echelle), (int)(r - 1) * echelle, (int)(r + 1) * echelle +e*echelle*echelle*capteur_rayon); }//fin else barycentre(); calculEpsilon(); //afficheValues(); }//Fin de la methode calcaulPosition void cartographie::setRayon(float r){capteur_rayon = r;} void cartographie::affiche_zone(int n) { map.affiche_zone(n); } void cartographie::incr(int _x, int _y) { map.incr(_x,_y); }
64
