Quel algorithme dois-je utiliser pour la géolocalisation wifi?

Cas d'utilisation du ramassage scolaire (mise à jour)

Il pourrait être utile d'aller dans un cas d'utilisation plus concret au lieu de l'exemple de cour arrière ci-dessous. Les forces de l'ordre locales ont commencé à sévir contre l'utilisation de la messagerie texte et l'utilisation du téléphone portable dans les zones scolaires. Cela présente un problème pour les parents qui ramassent des enfants après une fonction de collège. Même pour ceux qui font étalage de la loi, la tour cellulaire devient rapidement surchargée lorsque des centaines d'enfants appellent leurs parents à la fois. Le campus est grand, avec une couverture wifi. Il semble qu'il devrait être possible d'écrire une application mobile qui permettrait à un utilisateur de téléphone portable d'envoyer un message texte contenant une liste des forces du signal wifi à un service Web. Le service Web créerait alors un correctif de position et enverrait le message au dispositif de navigation embarqué des parents. Le parent conduirait alors au bon endroit sur le campus.

Cas d'utilisation d'arrière-cour (original) Lorsque je prends mon ordinateur portable dans mon arrière-cour et que je choisis «voir les réseaux disponibles», je vois une liste de mes 4 voisins. Alors que je me promène, la force relative du signal de mes voisins change.

Je voudrais me tenir avec mon ordinateur portable à des endroits connus dans ma cour arrière, cliquer sur la carte et collecter des points avec 4 puissances de signal différentes.

Après avoir collecté beaucoup (mais pas trop) de ces points d'étalonnage, je voudrais ensuite écrire un programme qui prend 4 niveaux de force du signal wifi et estime un emplacement sous la forme d'une ellipse d'erreur. Les signaux peuvent être mesurés à l'aide d'un appareil différent de celui utilisé pour collecter les points d'étalonnage d'origine.

Quel algorithme dois-je utiliser?

Je ne veux pas déranger mes voisins en leur demandant si je peux entrer et surveiller l'emplacement exact de leur routeur.

Je peux cependant supposer que l'emplacement de mes routeurs voisins ne change pas.

Il semble que vous ne connaissiez pas très bien les emplacements des signaux, vous devez donc d'abord les estimer, puis, compte tenu de ces estimations, trianguler votre position.

Si vous voulez un peu de précision et de réalisme, envisagez d'adopter un modèle de vraisemblance pour les forces du signal, de trouver la vraisemblance maximale et de faire une carte quadrillée de la probabilité d'emplacement calculée à partir des estimations de vraisemblance maximale. Le maximum global sur la grille identifie la meilleure estimation de l'emplacement et les contours (par rapport au maximum) donnent des ensembles de confiance pour cet emplacement.

Un modèle général de vraisemblance est obtenu en posant une formule pour l'atténuation du signal et en tenant compte de l'erreur. Vous n'irez pas très loin avec une formule complètement générale (avec une fonction d'atténuation dépendante de l'angle et de l'emplacement), vous devrez donc simplifier. Par exemple, vous pourriez envisager une fonction d'atténuation "universelle", appelez-la f , de sorte que si la force de la source à un emplacement WiFi x est égale à a, alors la force attendue à un autre emplacement y est donnée par

z (y; x) = af (| y - x |).

Par exemple, vous pourriez envisager une atténuation carrée inverse pour laquelle f (t) = 1 / t ^ 2 à condition que la distance t soit supérieure à un petit seuil. Comme autre simplification, vous pourriez prendre la lecture de la force z (y; x) à l'emplacement y pour que la source à x diffère de la valeur attendue par une erreur normalement distribuée; supposons que toutes les erreurs sont indépendantes; et supposer qu'ils ont tous le même écart - type ( s ). La contribution à la probabilité logarithmique d'une lecture de force z devient alors

L (y, x) = - [(z (y; x) - af (| yx |) ^ 2 / s ^ 2 + ln (s)] / 2.

La probabilité logarithmique à maximiser est la double somme de L (y, x) sur tous les emplacements y et toutes les sources x . Elle est fonction des emplacements inconnus, des intensités de source inconnues et de l'écart type inconnu des erreurs. Il est simple de trouver l'écart type optimal et les intensités de source optimales (prendre des dérivées partielles, les mettre à zéro et les résoudre), mais pour les fonctions d'atténuation réalistes f, vous avez un problème non linéaire pour trouver les emplacements. Cependant, dans votre exemple, il n'implique que 13 paramètres, vous devriez donc être en mesure de le vider, par exemple, dans un optimiseur Newton-Raphson multivarié et d'obtenir rapidement une bonne réponse. (La littérature statistique regorge de méthodes pour résoudre ces types d'équations.)

Si vous supposez en outre que le deuxième appareil a une sensibilité proportionnellement plus élevée que l'appareil de collecte de données, cela fera peu de différence dans le modèle que j'ai proposé (car les intensités du signal entrent en multiplication). En fait, si vous laissez les erreurs évoluer avec l'intensité (afin qu'elles aient l'écart type a * s * plutôt que s ), la différence entre les appareils devrait être sans conséquence.

Afin de garder cette simplicité, j'ai ignoré certaines subtilités statistiques, telles que le fait qu'il s'agit d'un problème d'intervalle de prédiction multivarié, pas d'un problème d'intervalle de confiance. Si la quantité d'erreur n'est pas grande (c'est-à-dire que s est petit), la différence n'aura pas beaucoup de conséquence.

Vérifiez peut-être ces papiers:

• RADAR: un système de localisation et de suivi des utilisateurs basé sur la RF
• Détermination de l'emplacement WLAN via le clustering et les distributions de probabilité

Je viens de trouver un tutoriel pour cartographier les réseaux WiFi avec Kismet, gpsmap, gdal et GRASS. Recherchez «Cartographie des réseaux Wifi avec Kismet, GDAL et GRASS» sur http://casoilresource.lawr.ucdavis.edu/drupal/book/export/html/96

Si vous collectez l'emplacement avec le GPS, je pense que vous regardez deux facteurs d'erreur différents. un pour le gps et l'autre pour la force du signal.

Ne pouvez-vous pas exploiter l'un des systèmes de positionnement WiFi existants tels que Skyhook Wireless ou Core Location dans iOS d'Apple? Skyhook vous permet d' ajouter manuellement des adresses MAC Wi-Fi à leur base de données, iOS collecte automatiquement les adresses MAC Wi-Fi à l'aide d'iPhone équipé d'un GPS.

Église,

Bien que je puisse me tromper, je pense que vous êtes loin de compliquer les choses. Bien que pour être juste, n'étant pas de votre partie du monde, je ne sais pas avec quelles limitations vous travaillez dans un campus scolaire.

Alors que la plupart des appareils mobiles prennent déjà en charge la triangulation GPS et / ou tour cellulaire, pour le WiFi, SkyHook est la réponse pour les raisons suivantes: 1. Leur base de données des emplacements WiFi est ÉNORME. 2. Chaque fois qu'une application utilisant SkyHook est utilisée, elle ajoute des réseaux WiFi nouvellement trouvés à la base de données, avec position. Donc, plus il est utilisé dans une zone, plus il devient précis. Je suppose que dans un endroit à haute densité comme un campus, s'il n'y a pas déjà une bonne couverture, il en aura en quelques jours d'utilisation régulière. 3. Certains téléphones utilisent SkyHook dans le cadre de leurs API de localisation, ce qui signifie que de plus en plus d'API téléphoniques normales auront déjà cela intégré.

Pour être honnête, à moins que vous ne vouliez que ce service soit disponible sur les ordinateurs portables (la plupart des nouveaux navigateurs ont SkyHook intégré), la plupart des téléphones ont maintenant un GPS, qui est accessible via les API de téléphone natives, que ce soit iOS, Android, WP7 ou La mûre. L'autre option serait d'en faire une application Web mobile, qui utiliserait simplement l'API de localisation du navigateur, avec un accès à tous les outils de localisation sur le téléphone de toute façon.