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

16

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.

Kirk Kuykendall
la source
4
je pense qu'il veut juste faire des triangulations, pas de ferroutage ...
Marinheiro
Pas de ferroutage - juste la force du signal, ce qui est légal à mesurer, non? Je ne vais pas "googler" le wifi ... blogs.discovermagazine.com/80beats/2010/10/25/…
Kirk Kuykendall

Réponses:

6

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.

whuber
la source
Merci Bill, cela semble faisable. Avec les ordinateurs portables, je viens de réaliser que le signal est sensible à l'orientation des antennes. Je ne sais pas si cela est vrai avec les téléphones portables. Le correctif d'emplacement serait-il assez bon pour le cas d'utilisation du collège?
Kirk Kuykendall du
Vous pouvez gérer l'orientation mais cela devient plus compliqué et nécessiterait plus de lectures. Envisagez plutôt d'utiliser le signal maximal parmi toutes les orientations possibles à chaque point. Le cas d'utilisation du collège est une variante intéressante en ce qu'il suggère de faire de votre mieux pour identifier les emplacements et les points forts de l'expéditeur WiFi une fois pour toutes. Après c'est un exercice de triangulation. Une de mes préoccupations est que les forces des sources peuvent varier, souvent de façon imprévisible. Cela peut vraiment gâcher la triangulation. Pensez à ajouter un écran initial pour les signaux (bas) périphériques afin qu'ils ne ruinent pas le correctif.
whuber
0

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.

Brad Nesom
la source
Dans ce contexte, Kirk pourrait en fait vérifier indépendamment les emplacements dans sa cour arrière (c'est-à-dire simplement prendre plusieurs lectures GPS de chaque emplacement).
Andy W
0

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.

Ortwin Gentz
la source
Ce ne serait peut-être pas une mauvaise idée s'il voulait savoir où il est. Mais il essaie de trouver lui-même un moyen de collecter les emplacements des réseaux. De plus, il essaie de trianguler sa position en fonction de la force des signaux WiFi. Je ne sais pas si les solutions commerciales font cela.
jvangeld
@jvangeld: Autant que je sache, Core Location dans iOS utilise la force du signal Wi-Fi pour trianguler la position. Pour le cas de ramassage scolaire mentionné, ce serait la voie à suivre.
Ortwin Gentz
0

É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.

BlinkyBill
la source
Je pensais que Skyhook collectait des données via Wardriving. Je ne peux pas imaginer qu'ils conduisent sur les routes de l'école, même si je suppose que ces routes sont publiques.
Kirk Kuykendall
Vous avez raison, mais parce que les clients élargissent leur base de données en plus de leur conduite de guerre, vous constaterez probablement qu'ils ont une couverture de toute façon. Vous pouvez toujours tester en chargeant Opera sur votre ordinateur portable, aller sur le campus avec maps.google.com et WiFi activé, et voir où cela vous mène.
BlinkyBill