Joint Optimization of Sensor Selection and Routing for Distributed Estimation in Wireless Sensor Networks

Resumen

Avances recientes en redes inalámbricos de sensores (WSNs, Wireless Sensor Networks) han posibilitado que pequeños sensores, baratos y con recursos limitados tanto en sensado, comunicación, como en computación, sean desplegados a gran escala. En consecuencia, las WSNs pueden ofrecer diversos servicios en importantes aplicaciones para la sociedad. Entre las varias restricciones que aparecen en el diseño de WSNs, tales como la limitación en energía disponible, procesamiento y memoria, la limitación en energía es muy importante ya que en muchas aplicaciones (ej., monitorización remota de diferentes entornos, edificios administrativos, monitoreo del hábitat, los incendios forestales, la atención sanitaria, la vigilancia del tráfico, vigilancia del campo de batalla, las reservas de vida silvestre, etc.) los sensores están alimentados por baterías, pudiendo hacer uso también de captación de energía renovables. Dado que las comunicaciones son causantes del mayor consumo energético en un nodo, la transmisión y recepción de información deben optimizarse lo máximo posible. Estas limitaciones y el diseño específico de los sensores, hacen necesario el estudio de métodos eficientes energéticamente y que reduzcan la cantidad de información a transmitir. Motivación y Objetivos: Aunque las WSNs necesitan cubrir en muchas ocasiones una importante área geográfica, muchos eventos necesitan ser detectados y tratados localmente. Algunos de estos ejemplos son la energía capturada por sensores de energía acústica donde existe una cierta fuente acústica localizada en el espacio, detección y verificación de un foco de fuego en un bosque, sensores de dirección de llegada para localización, u otra fuente difusiva localmente generada (ej. radiación nuclear). Intuitivamente, en estos escenarios, los nodos que están localizados lejos de la fuente observarán medidas significativamente menos informativas que los nodos cercanos a la fuente. Por lo tanto, la vida útil de la red puede ser incrementada al considerar la activación de solo un subconjunto de sensores (los más informativos) cuya información es útil y por tanto debe ser recolectada. Además, la eficiencia energética puede ser mejorada aún más al elegir la mejor estructura de enrutamiento. Es importante resaltar que la técnica utilizada más tradicional es la transmisión directa inalámbrica de las medidas desde todos los nodos seleccionados al centro de fusión de datos (nodo solicitante de la estimación global), lo cual resultas en un ineficiente uso de los recursos energéticos. Una solución factible puede ser el uso de la naturaleza multisalto de la transmisión de datos, el cual puede significativamente reducir la potencia total de transmisión, y por tanto aumentar la vida de la red. La cuantificación de la información (fusión) puede también utilizarse en un procesado intra-red para ahorrar energía, ya que reduce la cantidad de información a ser reenviada en dirección al nodo centro de fusión. La asignación dinámica de bit-rate (bits por muestra) en cada nodo puede también ser empleada para reducir también el consumo total de la red. De esta manera, se puede obtener un importante ahorro energético al realizar de manera distribuida una cierta tarea de estimación optimizando el conjunto de sensores activo; la estructura de enrutamiento, y los bits por muestra para cada sensor seleccionado. En la literatura reciente, se ha demostrado claramente que la transmisión multisalto en WSNs es más eficiente energéticamente que la transmisión directa, donde cada medida es directamente transmitida al centro de fusión de datos (MT, Measure-and-Transmit). Además, transmisión mutlisalto, en general, permite el envío de las medidas al nodo fusión de dos formas: a) cada nodo reenviar directamente la información recibida, b) cada nodo reenviar la información agregada. Puede observarse que, el fusionar las medidas en sensores intermedios ofrece una mejora en la calidad global de la estimación con coste computacional limitado. Esto nos lleva a considerar los dos esquemas siguientes: Medir-y-reenviar (MF, Measure-and-Forward): En este esquema, los nodos sensores simplemente reenvían las medidas que reciben de sus nodos sensores hijos en dirección al nodo solicitante a lo largo de la estructura de enrutamiento elegida. El nodo solicitante obtendrá por tanto la estimación final, por lo tanto, no hay estimación agregadas incrementales en los sensores intermedios. Estimar-y-reenviar (EF, Estimate-and-Forward): En este esquema, se considera un enfoque con estimación agregada secuencial en los nodos intermedios de la ruta de encaminamiento. Dada una estructura de enrutamiento, cada sensor fusiona todas las otras medidas que son recibidas de sus nodos hijos junto con la suya propia, con el objetivo de obtener una estimación agregada, y luego enviar un único flujo de la información fusionada a su nodo sensor padre en la estructura de enrutamiento elegida. El esquema EF tiene varias ventajas interesantes respecto al esquema MF. En primer lugar, el esquema EF es más eficiente energéticamente ya que un nodo sensor activo en una ruta solo tiene que reenviar la estimación fusionada (una único paquete de información transmitir), en vez de reenviar su propia medida además de las medidas de sus nodos hijos. Además, utilizando un esquema EF, los nodos intermedios en la ruta tienen una estimación del parámetro que es mejor conforme el nodo está más cercano al nodo solicitante. La otra principal desventaja del esquema MF es que los nodos cerca del nodo solicitante pueden sobrecargarse, lo crea un efecto de cuello de botella. Por lo tanto, dada una WSN con una cierto grafo subyacente de conectividad de red, un cierto nodo solicitante, y una fuente localizada, esta tesis considera el problema de la estimación distribuida de un parámetro, donde la potencia total disponible esta limitada, por lo tanto, y donde utilizamos el esquema EF, optimizando conjuntamente el subconjunto de sensores activos, la asignación de bit-rate en cada sensor y la estructura de enrutamiento multisalto asociada hasta el nodo solicitante. Por lo tanto, la distorsión total en la estimación es minimizada para una cierta potencia total de transmisión. Un resultado importante de este trabajo el consiste en que el algoritmo Shortes Path Tree (SPT) basado solo en coste de comunicación (SPT-CC) no es la estructura óptima de enrutamiento en general cuando se busca alcanzar un compromiso óptimo entre la distorsión de la estimación y el coste total de comunicaciones, sin importar si uno usa el esquema MF o el EF. En nuestra estimación distribuida multisalto, mientras nos dirigimos hacia el nodo solicitante, necesitamos asignar tasas mayores de bits ya que la precisión de la estimación mejora a medida que más información se fusiona en los nodos de sensores intermedios. Por lo tanto, la asignación de tasa de bits en un sensor depende del número de saltos que existe entre dicho nodo y el nodo solicitante, de tal manera que hay una necesidad de proporcionar mayores tasas de bits al ir acercándose al nodo solicitante en la ruta de multisalto escogido. Por otro parte, la localización de la fuente que determine fenómeno estimar también influencia la asignación de bit-rate para sensor. Por ejemplo, si un sensor está cerca de la fuente (relación Señal-Ruido alto), incluso aunque existe un gran número de saltos necesarios para llegar al nodo solicitante, necesitamos asignar un bit-rate razonablemente alto. En consecuencia, hay una clara necesidad de diseñar un cuantificador adaptativo en cada sensor con el objetivo de proporcionar un apropiado bit-rate, el cual depende del compromiso entre el número de saltos y la localización de la fuente. Además, el bit-rate también depende del coste de comunicación entre cada dos sensores. Metodología: En esta tesis, combinamos métodos de análisis teórico, diseño algoritmos iterativos inspirados en herramientas de optimización así como simulaciones por ordenador. En el caso del análisis teórico del problema mencionado anteriormente, hemos seguido la metodología estándar de estimación óptima lineal no sesgada; en otras palabras, Best Linear Unbiased Estimator (BLUE). En particular, este trabajo de tesis se centra en el problema de optimizar conjuntamente la selección de sensores, la estructura de enrutamiento y la asignación de bit-rate para cada sensor seleccionado. En primer lugar, consideramos solamente la optimización conjunta de la selección de sensores y la estructura de enrutamiento, donde se asume una cuantificación fina, y por tanto se ignora la asignación óptima de bit-rate. En este caso, la función objetivo es lineal y las restricciones en el problema de optimización son no convexas, lo cual lleva a un problema a resolver que tiene una complejidad y alto. En segundo lugar, tenemos en cuenta la asignación del bit-rate como una variable adicional en el primer problema, convirtiéndose en un problema de optimización no lineal no convexo. Por lo tanto, el problema de optimización conjunta se hace aún más difícil de resolver que el primera problema de optimización. La solución de este problema no convexo se aborda utilizando varios pasos de relajación convexa y resolviendo estos problemas relajados para las diferentes variables en tándem. El objetivo en ambos problemas anteriormente mencionadas es reducir al mínimo la distorsión total en la estimación bajo una cierta limitación de potencia total dada. También demostramos que nuestros problemas pertenecen a la clase de problemas NP-hard, realizando una reducción (de complejidad polinomial) de nuestro problema el problema Hamiltoniano no dirigido (UHP, Undirected Hamiltonian Path). Nuestros problemas de optimización relajados se pueden resolver a través de métodos de optimización convexa, tales como los métodos de punto interior. Después de los análisis teóricos, los algoritmos propuestos considerados para ambos casos (cuantificación fina y cuantificación adaptativa), son simulados usando programación Matlab y el toolbox de CVX. Los algoritmos propuestos son comparados, en cada caso, con los mejores algoritmos propuestos en la literatura para la asignación de recursos en WSN para estimación. %Aunque las simulaciones fueron realizadas con el lenguaje de programación de Matlab, es posible usar otras plataformas de simulación y lenguajes de programación. Conclusiones: En esta tesis, dada una WSN con un grafo subyacente de conectividad de red, un cierto nodo solicitante (sumidero) y una fuente localizada, hemos considerado el problema de la estimación distribuida de parámetros con donde la potencia total disponible esta limitada. Por lo tanto, para llevar a cabo un cierta tarea de estimación distribuida (por ejemplo, detección de fuego en un bosque, localización basada en dirección de llegada, estimación de cualquier otro fenómeno localizado, etc.), hemos considerado el problema, usando el esquema EF, de optimizar conjuntamente el subconjunto de sensores activas, la asignación de bit-rate y la asociada estructura de enrutamiento multisalto para enviar la información agregada hasta el nodo solicitante. De esta manera, la distorsión en la estimación total es minimizada una cierta potencia total. La mayoría de las soluciones recientemente propuestas, intentan simplificar el problema considerando solamente la selección de un subconjunto de sensores, ignorando la optimización conjunta de la estructura de enrutamiento así como de la codificación. Sin embargo, optimizar la estructura de enrutamiento es una importante variable en el problema ya que, en general, transmitir información que está lejos del nodo solicitante es más costoso que desde un nodo cercano. La cuantificación de fuente también juega un papel importante ya que los sensores lejos de la fuente requieren menos niveles de cuantificación ya que reciben un SNR menor. A continuación resumimos nuestras principales contribuciones: 1. El problema de optimización conjunta de la selección de sensores, la estructura de enrutamiento multisalto y la asignación adaptativa de la tasa de bit (mediciones del sensor) para la estimación distribuida con un restricción en el coste total de comunicaciones, es formulado y analizado, tanto en términos de diseño de algoritmos como de análisis de complejidad, demostrando que es un problema NP-hard cuando se utiliza el esquema EF. También proporcionamos una cota inferior para la solución óptima del problema de optimización NP-hard original. 2. En primer lugar, consideramos el problema de optimización conjunta de la selección de los sensores y de la estructura de enrutamiento multisalto asumiendo que se dispone de una cuantificación fina para cada medición de los sensores. A continuación, presentamos un Algoritmo que llamamos FTRA (Fixed-Tree Relaxation-based Algorithm) que consiste en una relajación de nuestro problema de optimización original, y que desacopla la elección de la estructura de enrutamiento de la selección de sensores activos. 3. A continuación, también diseñamos un nuevo y eficiente algoritmo iterativo distribuido que llamamos IDA (Iterative Distributed Algorithm), que optimiza de forma conjunta a nivel local y distribuida la selección de sensores y la estructura de enrutamiento de saltos múltiples. También demostramos experimentalmente que nuestro IDA genera una solución que está cerca de la solución óptima al problema NP-hard original, haciéndose uso de la cota anteriormente obtenida. 4. En segundo lugar, hemos considerado la asignación de tasa de bit como una variable adicional al anterior problema la optimización, en un problema de optimización no lineal y no convexo resultando en un problema todavía mas complejo de resolver, y por tanto NP-Hard también. 5. Para este segundo problema de optimización, hemos desarrollado dos algoritmos: a) Algoritmo de Cuantificación Adaptativa basado en árbol Fijo (FTR-AQ, Fixed-Tree Relaxation-based Adaptive Quantization), y b) Algoritmo de Cuantificación Adaptativa basado en Optimización Local (LO-AQ, Local Optimization-based Adaptive Quantization). LO-AQ proporciona una estimación más precisa para la misma potencia total dada, aunque esto implica una complejidad computacional adicional en cada nodo. 6. Por último, comparamos nuestros algoritmos con los otros mejores trabajos relacionados presentados previamente en la literatura, mostrando claramente un rendimiento superior en términos de distorsión en la estimación para la misma potencia total dada.