¿Qué algoritmo debo usar para la geolocalización wifi?

16

Caso de uso de recogida en la escuela (actualización)

Puede ser útil entrar en un caso de uso más concreto en lugar del ejemplo de patio trasero original a continuación. La policía local ha comenzado a tomar medidas enérgicas contra el uso de mensajes de texto y el uso de teléfonos celulares en zonas escolares. Esto presenta un problema para los padres que recogen niños después de una función de la escuela intermedia. Incluso para aquellos que hacen alarde de la ley, la torre celular se sobrecarga rápidamente cuando cientos de niños llaman a sus padres a la vez. El campus es grande, con cobertura wifi. Parece que debería ser posible escribir una aplicación móvil que permita a un usuario de teléfono celular enviar un mensaje de texto que contiene una lista de intensidades de señal wifi a un servicio web. El servicio web luego crearía una corrección de ubicación y enviaría el mensaje al dispositivo de navegación a bordo de los padres. El padre luego conduciría a la ubicación correcta en el campus.

Caso de uso del patio trasero (original) Cuando llevo mi computadora portátil al patio trasero y elijo "ver redes disponibles", veo una lista de mis 4 vecinos. Mientras camino, la intensidad relativa de la señal de mis vecinos cambia.

Me gustaría estar con mi computadora portátil en lugares conocidos en mi patio trasero, hacer clic en el mapa y acumular puntos con 4 intensidades de señal diferentes.

Después de recopilar muchos (pero no demasiados) de estos puntos de calibración, me gustaría escribir un programa que tome 4 niveles de intensidad de señal wifi y calcule una ubicación en forma de una elipse de error. Las señales pueden medirse usando un dispositivo diferente al que se usó para recolectar los puntos de calibración originales.

¿Qué algoritmo debo usar?

No quiero molestar a mis vecinos preguntándoles si puedo entrar y examinar la ubicación exacta de su enrutador.

Sin embargo, puedo suponer que la ubicación de los enrutadores de mis vecinos no cambia.

Kirk Kuykendall
fuente
44
Creo que solo quiere hacer triangulaciones, no a cuestas ...
Marinheiro
Sin piggybacking, solo señal de fuerza, que es legal medir, ¿verdad? No voy a "buscar en Google" el wifi ... blogs.discovermagazine.com/80beats/2010/10/25/…
Kirk Kuykendall

Respuestas:

6

Parece que no conoce muy bien las ubicaciones de las señales, por lo que primero debe estimarlas y luego, dadas esas estimaciones, triangular su posición.

Si desea algo de precisión y realismo, considere adoptar un modelo de probabilidad para las intensidades de la señal, encontrar la probabilidad máxima y hacer un mapa cuadriculado de la probabilidad de ubicación calculada a partir de las estimaciones de probabilidad máxima. El máximo global en la cuadrícula identifica la mejor estimación de la ubicación y los contornos (en relación con el máximo) dan conjuntos de confianza para esa ubicación.

Se obtiene un modelo de probabilidad general postulando una fórmula para la atenuación de la señal y permitiendo el error. No llegará muy lejos con una fórmula completamente general (con una función de atenuación dependiente del ángulo y la ubicación), por lo que tendrá que simplificar. Por ejemplo, podría considerar una función de atenuación "universal", llámela f , de modo que si la potencia de la fuente en una ubicación WiFi x es igual a a , la fuerza esperada en otra ubicación y viene dada por

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

Por ejemplo, podría considerar la atenuación de la inversa del cuadrado para la cual f (t) = 1 / t ^ 2 siempre que la distancia t sea ​​mayor que un umbral pequeño. Como otra simplificación, puede tomar la lectura de fuerza z (y; x) en la ubicación y para que la fuente en x difiera del valor esperado por un error normalmente distribuido; suponga que todos los errores son independientes; y supongamos que todos tienen la misma desviación estándar ( s ). La contribución a la probabilidad logarítmica de una lectura de fuerza z se convierte en

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

La probabilidad logarítmica de maximizarse es la suma doble de L (y, x) sobre todas las ubicaciones y y todas las fuentes x . Es una función de las ubicaciones desconocidas, las intensidades de fuente desconocidas y la desviación estándar desconocida de los errores. Es sencillo encontrar la desviación estándar óptima y las intensidades de fuente óptimas (tomar derivadas parciales, establecerlas en cero y resolver), pero para funciones de atenuación realistas f tiene un problema no lineal para encontrar las ubicaciones. Sin embargo, en su ejemplo, solo involucra 13 parámetros, por lo que debería poder volcarlo, por ejemplo, en un optimizador multivariante Newton-Raphson y obtener rápidamente una buena respuesta. (La literatura estadística está llena de métodos para resolver este tipo de ecuaciones).

Si además asume que el segundo dispositivo tiene una sensibilidad proporcionalmente mayor que el dispositivo de recopilación de datos, hará poca diferencia en el modelo que he propuesto (porque las intensidades de la señal entran multiplicativamente). De hecho, si deja que los errores escalen con intensidad (por lo que tienen una desviación estándar a * s * en lugar de s ), la diferencia entre los dispositivos debería ser intrascendente.

Para mantener esto simple, me he saltado algunas sutilezas estadísticas, como el hecho de que este es un problema de intervalo de predicción multivariante, no un problema de intervalo de confianza. Si la cantidad de error no es grande (es decir, s es pequeña), la diferencia no será de mucha consecuencia.

whuber
fuente
Gracias Bill, esto parece factible. Con las computadoras portátiles me acabo de dar cuenta de que la señal es sensible a la orientación de las antenas. No estoy seguro si esto es cierto con los teléfonos celulares. ¿El arreglo de ubicación sería lo suficientemente bueno para el caso de uso de la escuela intermedia?
Kirk Kuykendall
Puede manejar la orientación, pero se vuelve más complicado y necesitaría más lecturas. Considere en su lugar utilizar la señal máxima entre todas las orientaciones posibles en cada punto. El caso de uso de la escuela secundaria es una variante interesante, ya que sugiere hacer todo lo posible para identificar las ubicaciones y las fortalezas del remitente WiFi de una vez por todas. Después de eso es un ejercicio de triangulación. Una preocupación que tengo es que las fortalezas de la fuente pueden variar, a menudo de manera impredecible. Eso realmente puede arruinar la triangulación. Considere agregar una pantalla inicial para las señales periféricas (bajas) para que no arruinen la solución.
whuber
0

Si está recopilando la ubicación con gps, creo que está viendo dos factores de error diferentes. uno para los gps y el otro para la intensidad de la señal.

Brad Nesom
fuente
En este contexto, Kirk podría verificar las ubicaciones en su patio trasero de forma independiente (es decir, simplemente tomar múltiples lecturas de GPS de cada ubicación).
Andy W
0

¿No puede aprovechar uno de los sistemas de posicionamiento WiFi existentes, como Skyhook Wireless o Core Location en iOS de Apple? Skyhook le permite agregar direcciones MAC de Wi-Fi a su base de datos de forma manual, iOS recopila las direcciones MAC de Wi-Fi automáticamente usando los iPhone equipados con GPS.

Ortwin Gentz
fuente
Esto podría no ser una mala idea si quisiera averiguar dónde está. Pero él está tratando de encontrar una manera de recopilar las ubicaciones de las redes él mismo. Además, está tratando de triangular su posición en función de la fuerza de las señales WiFi. No estoy seguro si las soluciones comerciales hacen eso.
jvangeld
@jvangeld: Según tengo entendido, Core Location en iOS usa la intensidad de la señal de Wi-Fi para triangular la posición. Para el caso de recogida de la escuela mencionado, sería el camino a seguir.
Ortwin Gentz
0

Iglesia,

Si bien puedo estar equivocado, creo que estás superando las cosas complicadas. Aunque para ser justos, al no ser de tu parte del mundo, no sé con qué limitaciones estás trabajando en el entorno de un campus escolar.

Si bien la mayoría de los dispositivos móviles ya admiten GPS y / o triangulación de torre celular, para WiFi, SkyHook es la respuesta por las siguientes razones: 1. Su base de datos de ubicaciones de WiFi es ENORME. 2. Cada vez que se usa una aplicación que usa SkyHook, agrega redes WiFi recién encontradas a la base de datos, con posición. Entonces, cuanto más se usa en un área, más precisa se vuelve. Supongo que en una ubicación de alta densidad como un campus, si aún no hay una buena cobertura, tendrá en cuestión de días de uso regular. 3. Algunos teléfonos usan SkyHook como parte de sus API de ubicación, lo que significa que cada vez más API de teléfonos normales ya lo tendrán incorporado.

Para ser honesto, a menos que desee que este servicio esté disponible en computadoras portátiles (la mayoría de los nuevos navegadores tienen SkyHook incorporado), la mayoría de los teléfonos ahora tienen GPS, al que se puede acceder a través de las API nativas del teléfono, ya sea iOS, Android, WP7 o Mora. La otra opción sería convertirla en una aplicación web móvil, que solo usaría la API de ubicación del navegador, con acceso a todas las herramientas de ubicación en el teléfono de todos modos.

BlinkyBill
fuente
Pensé que Skyhook recopiló datos a través de la protección. No puedo imaginarlos conduciendo por las carreteras de la escuela, aunque supongo que son públicos.
Kirk Kuykendall
Tienes razón, pero debido a que los clientes 'expanden' su base de datos además de su conducción de guerra, probablemente descubras que tienen cobertura de todos modos. Siempre puedes probar cargando Opera en tu computadora portátil, ir al campus con maps.google.com y WiFi habilitados, y ver dónde te ubica.
BlinkyBill