1. Introducción
Los sistemas de localización de personas, tanto en interiores como en exteriores, han tomado un gran valor en la actualidad. Para la localización en exteriores, existe un sistema fiable y preciso cuyo uso se ha extendido, debido a una reducción de coste de los dispositivos necesarios para su funcionamiento. Este sistema se denomina GPS (Global Positioning System).
Para la localización en interiores existen diversas ramas de desarrollo. La principal se denomina WPS (Wireless Positioning System) que basa la localización en las señales emitidas por diferentes puntos de acceso.
Durante el desarrollo de este proyecto, se ha realizado un estudio sobre la efectividad de las redes bayesianas en un sistema de localización para interiores encuadrado dentro de WPS. El algoritmo de localización desarrollado se ha implementado en dispositivos PDA. |
2. Conceptos Teóricos
Una WLAN 802.11 está basada en una arquitectura celular. Cada celda, llamada BSS (Basic Service Set), está controlada por una estación base, denominada AP (Access Point). Toda la WLAN interconectada, incluyendo las diferentes celdas con sus respectivos APs, es tomada por los niveles superiores del modelo OSI como una única red 802, y se denomina ESS (Extended Service Set).
Los dispositivos que acceden a una WLAN (ordenadores, PDAs,etc.) lo pueden hacer mediante escaneo pasivo (el dispositivo se queda a la espera de tramas Beacon, enviadas desde los puntos de acceso) y escaneo activo (el dispositivo envía una trama Probe Request a un punto de acceso y recibe una trama Probe Response). |
Se basan en el teorema de Bayes, que define:
donde H es la hipótesis, E es la evidencia y c el contexto.
P(H|E,c) se denomina probabilidad a posteriori. Es la probabilidad de que se cumpla la hipótesis H después de considerar el efecto de la evidencia E sobre el entorno (o contexto) c. |
El concepto de probabilidad condicional es útil. Hay muchos casos en el mundo real donde la probabilidad de un suceso depende de la probabilidad de otros sucesos previos. Las reglas de suma y multiplicación de la teoría de la probabilidad pueden anticipar este factor de dependencia entre sucesos de forma exacta. Sin embargo, en muchos casos se convierte en un problema irresoluble. Por ejemplo, un escenario de diagnóstico de enfermedades con 5 variables discretas ( parámetros) sería programable. Sin embargo, un sistema experto con 37 variables ( parámetros) no sería una problema programable. Para el tratamiento de este tipo de problemas surgen las redes bayesianas.
|
3. Técnicas y herramientas
La elección de unas u otras técnicas y herramientas condicionan enormemente el desarrollo y la efectividad de un proyecto informático. Por ello debe llevar un tiempo el estudiar qué metodologías, lenguajes de programación, sistemas de gestión de datos, etc. Se deben utilizar para la realización del sistema. Con una buena elección se minimizará el tiempo necesario y el coste para la realización del proyecto y además se ayudará a proporcionar una mayor calidad al sistema. |
Se han utilizado los siguientes lenguajes de programación:
- C++ (eMbedded)
- C# (.NET Framework)
- C# (.NET Compact Framework)
Las aplicaciones se ejecutan en los siguientes entornos:
- PocketPC basado en Windows® CE
- Windows® Mobile 2003
- Windows® Mobile 5.0
|
La forma de acceso al driver de los dispositivos de red inalámbrica no fue trivial, convirtiéndose en una complicación significativa en el desarrollo del proyecto.
Se utilizó:
- NDIS (Network Driver Interface Specification): Biblioteca de funciones que oculta la complejidad de funcionamiento del dispositivo de red a nivel hardware.
- SDF OpenNETCF.NET 1.4 (Smart Device Framework): Framework de ampliación al .NET Compact Framework desarrollado por un partner de Microsoft® llamado OpenNETCF.NET.
|
4. Aspectos relevantes del proyecto
El flujo de trabajo que se siguió durante el desarrollo del proyecto se expone en la siguiente figura:
Se realizaron diez mediciones completas en cada celda del espacio de muestreo. Cada medición en una celda contiene diez muestras, distribuidas en las configuraciones representadas en las siguientes figuras
|
Este proceso genera la matriz heurística que será utilizada en el algoritmo de localización. Esta matriz indica la posibilidad que existe de pasar de una celda A a una celda B. Si la celda B está alejada de la celda A, la probabilidad de pasar de una celda a otra será menor que si la celda B es adyacente a la celda A. Será una matriz cuadrada de 90 × 90 (tantas como celdas se tienen en el espacio de muestreo).
La función de dispersión es P = e^-0.3d (que se observa en la figura), donde es la distancia que separa dos celdas. Esta distancia se calcula teniendo en cuenta el número de celdas de separación y el número de cambios de orientación. Así, entre la celda (3,0,0) y la celda (0,0,6) la distancia sería de 4 (3 celdas de separación + 1 cambio de orientación). Cuando la distancia entre dos celdas supera el valor de 6, la probabilidad de pasar de una celda a la otra es 0, ya que es la distancia máxima entre dos mediciones consecutivas.
|
- Mediciones Alineadas: Entrada del proceso de entrenamiento. Se almacenan en ficheros diferentes las mediciones centrales y las alejadas (en forma de X ó +)
- Mezclar mediciones: Agrupar todos los ficheros de mediciones en un único fichero. Genera las Mediciones sin Alinear.
- Agrupar mediciones: Agrupar los ficheros de mediciones sin alinear (tantos como mediciones completas realizadas) en un único fichero. Genera las Mediciones Totales.
- Calcular Probabilidades: Se generan las Probabilidades Condicionadas. Las probabilidades condicionadas de una celda serán las diferentes probabilidades de que un AP haya sido detectado con una potencia de señal concreta.
Las probabilidades se calculan con una discretización de tres, esto es, las probabilidades condicionadas de que un AP sea detectado con una pérdida de potencia de señal -100 dBm, -99 dBm y -98 dBm quedarán agrupadas.
|
|
- Medición: Se toma una muestra por cada uno de los puntos de acceso observables. Es la única entrada que precisa el algoritmo.
- Vector de probabilidades condicionadas (VPC): Representa las probabilidades de localización en cada una de las celdas, partiendo de la medición realizada. Tiene tantas componentes como celdas del espacio de muestreo y se calcula de la siguiente forma:
donde APi se refiere al AP i-ésimo; Ri es la potencia actual recibida de ese AP;Pi(APi, Ri) es la probabilidad que, estando en la celda i-ésima, se tiene de recibir la potencia de señal Ri, por el APi. Esta probabilidad se encuentra en los ficheros de probabilidades condicionadas que se obtuvieron en el proceso de entrenamiento de la red bayesiana.
- Vector de probabilidades vecinas (VPV): Se trata de seleccionar la celda candidata, utilizando un criterio distinto al de máxima probabilidad. El nuevo criterio tiene en cuenta que las celdas candidatas se encontrarán en aquellas zonas que presentan una mayor probabilidad acumulada. Cada una de las componentes del vector de probabilidades vecinas se calcula de la siguiente forma:
- Vector de probabilidades a posteriori (VPP): Es el vector sobre el que se determinará la celda candidata y los resultados. Cada componente se calcula de la siguiente forma:
- Vector de probabilidades a priori (VPPI): Está formado por tantas componentes como celdas se tienen en el espacio de muestreo. Cada componente representa la probabilidad de que el resultado final sea esa celda. En definitiva, el vector de probabilidades a priori proporciona una predicción del resultado. Este vector se actualiza en cada localización.
- Actualización de VPPI: La celda actual proporciona mucha información. Si se asume un itinerario no caótico y brusco, se puede estimar que la próxima celda a recorrer se encuentre dentro de unos límites de distancia acotados mediante una función de dispersión. Esta función viene representada en nuestro caso por la matriz heurística (H). El nuevo VPPI se calcula de la siguiente forma:
- Celda estimada: El resultado de este algoritmo es una celda candidata a actual posición.
|
Para el acceso a los drivers de las tarjetas de red inalámbricas de los dispositivos PDA utilizados nos basamos en:
- Programación de una DLL para acceso a tarjeta COMPAQ WL110 11Mbps
- Utilización de Smart Device Framework de OpenNETCF.NET
|
- Medidor:
Aplicación de soporte utilizada en el proceso de muestreo.
- Entrenador:
Aplicación de soporte utilizada en el proceso de entrenamiento de la red bayesiana y generación de la matriz heurística.
- Localizador:
Aplicación final de usuario que a partir de una medición, localiza en tiempo real
- Analizador:
Aplicación final de usuario que a partir de un conjunto de mediciones tomadas con anterioridad (itinerario) realiza un análisis de resultados del proceso de localización.
|
Se realizaron estudios sobre la dependencia de la atenuación de la señal respecto a determinados factores como:
- Distancia
- Altura respecto del suelo
- Dispositivo de red receptor
|
5. Conclusiones
Se ha desarrollado un algoritmo de localización con una eficiencia adecuada, basándose en una optimización del método de muestreo, entrenamiento y del propio algoritmo. Se han realizado aplicaciones para dispositivos PDA que funcionan bajo diferentes sistemas operativos móviles y para diferentes dispositivos de red inalámbrica. |