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

16

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

Podría ser útil buscar un caso de uso más concreto en lugar del siguiente ejemplo de patio trasero. 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 las zonas escolares. Esto presenta un problema para los padres que recogen a sus hijos después de una función en la escuela secundaria. 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 amplio, con cobertura wifi. Parece que debería ser posible escribir una aplicación móvil que permitiría a un usuario de teléfono celular enviar un mensaje de texto que contenga una lista de potencias de señal wifi a un servicio web. El servicio web crearía entonces un arreglo de ubicación y enviaría el mensaje al dispositivo de navegación integrado de los padres. Los padres luego conducirían a la ubicación correcta en el campus.

Estuche de uso en el patio trasero (original) Cuando llevo mi computadora portátil a mi patio trasero y elijo "ver redes disponibles", veo una lista de mis 4 vecinos. A medida que me muevo, los puntos fuertes de la señal relativa de mis vecinos cambian.

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 potencias de señal diferentes.

Después de recopilar una gran cantidad (pero no demasiada) 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 error en una elipse. Las señales pueden medirse utilizando un dispositivo diferente al utilizado para recolectar los puntos de calibración originales.

¿Qué algoritmo debo usar?

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

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

    
pregunta Kirk Kuykendall 22.10.2010 - 23:22

6 respuestas

6

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

Si desea cierta 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 reticulado 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 al postular una fórmula para la atenuación de la señal y permitir el error. No llegará muy lejos con una fórmula completamente general (con una función de atenuación que depende 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 entonces la fuerza esperada en otra ubicación y viene dada por

z (y; x) = a f (| y - x |).

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

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

La probabilidad de que se maximice el registro es la suma doble de L (y, x) en 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 a cero y resolver), pero para las funciones de atenuación realista f tiene un problema no lineal para encontrar las ubicaciones . Sin embargo, en su ejemplo involucra solo 13 parámetros, por lo que debería ser capaz de volcarlo en, por ejemplo, un optimizador multivariado Newton-Raphson y obtener rápidamente una buena respuesta. (La literatura de estadísticas 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, tendrá poca diferencia en el modelo que he propuesto (porque las intensidades de la señal entran multiplicativamente). De hecho, si deja que los errores se amplíen con intensidad (para que tengan una desviación estándar a * s * en lugar de s ), la diferencia entre 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 multivariable, no un problema de intervalo de confianza. Si la cantidad de error no es grande (es decir, s es pequeña), la diferencia no tendrá mucha importancia.

    
respondido por el whuber 25.10.2010 - 19:08
1

Acabo de encontrar un tutorial para mapear redes WiFi con Kismet, gpsmap, gdal y GRASS. Busque "Mapeo de redes Wifi con Kismet, GDAL y GRASS" en enlace

    
respondido por el jvangeld 21.12.2010 - 23:10
0

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

    
respondido por el Brad Nesom 25.10.2010 - 16:22
0

¿No puede aprovechar uno de los sistemas de posicionamiento WiFi existentes como Skyhook Wireless o ¿Ubicación del núcleo en el iOS de Apple? Skyhook le permite agregar direcciones MAC Wi-Fi a su base de datos manualmente, iOS recopila las direcciones MAC Wi-Fi automáticamente usando IPhone equipado con GPS.

    
respondido por el Ortwin Gentz 08.12.2010 - 16:24
0

Kirk,

Aunque puedo estar equivocado, creo que estás complicando las cosas. Aunque para ser justos, al no ser de tu parte del mundo, no sé con qué limitaciones trabajas 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 para las siguientes razones: 1. Su base de datos de ubicaciones 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 la posición. Así que cuanto más se usa en un área, más preciso se vuelve. Supongo que en una ubicación de alta densidad como un campus, si no hay una buena cobertura, tendrá en cuestión de días de uso regular. 3. Algunos teléfonos usan SkyHook como parte de las API de su ubicación, lo que significa que las API de teléfonos más y más las tendrán ya integradas.

Para ser honesto, a menos que desee que este servicio esté disponible en computadoras portátiles (la mayoría de los navegadores nuevos 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 BlackBerry. 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.

    
respondido por el BlinkyBill 22.12.2010 - 03:52

Lea otras preguntas en las etiquetas