Laboratorio de Redes: Actividad 9

Artículo: "ENERGY EFFICIENT ROUTING IN WIRELESS SENSOR NETWORKS "
Autores: Curt Schurgers, Many B. Srivastava

I. INTRODUCCIÓN
Los circuitos integrados han madurado al grado que permiten la integración de comunicaciones, sensores y procesamiento de señal en conjunto. Ahora es factible dispersar nodos sensores ultra pequeños en un campo de batalla para recolectar información estratégica. Debido a que los nodos deben ser discretos, solo pueden cargar baterías muy pequeñas. Como resultado, tienen un suministro de energía limitado. Protocolos de ruteo para redes conformadas por estos nodos necesitan ser desarrollados con un enfoque en eficiencia de energía.

En el artículo se proponen dos opciones para incrementar el tiempo de vida de la red de sensores: (1) minimizar el consumo de energía de transmisiones y (2) explotar el aspecto multi-hop de las comunicaciones en red.

Antes de discutir dichas opciones se trata el problema: como incrementar el tiempo de vida de una red de dispositivos de energía limitada.

II. ENUNCIADO DEL PROBLEMA
1. Ruteo Óptimo de Energía
Algoritmos de ruteo ad-hoc tradicionales se enfocan en evitar la congestión o mantener la conectividad cuando se enfrentan con mobilidad. No consideran el suministro limitado de energía de los dispositivos de red. La siguiente figura ilustra cómo el suministro limitado altera el asunto del ruteo.

Carga vs. ruteo orientado a energía

Los nodos A y E mandan 50 paquetes a B. Después, F manda 100 paquetes a B. Desde una perspectiva de balanceo de carga, las rutas preferidas son ADB, ECB y FDB, respectivamente. Sin embargo, cuanto los nodos están limitados en energía de manera que solo pueden enviar 100 paquetes, estas rutas ya no son óptimas.

Este caso de estudio simple resalta la siguiente observación: la calendarización de tráfico óptimo en redes de energía limitada requiere conocimiento futuro. En el ejemplo, un número máximo de paquetes puede alcanzar B solo si justo al inicio sabemos exactamente cuándo los nodos generarán tráfico en el futuro.

2. Ruteo Eficiente de Energía  
Por lo discutido, el ruteo óptimo en redes de energía limitada no es prácticamente factible. Sin embargo, se pueden ablandar los requerimientos hacia un esquema estadísticamente óptimo. Un esquema es eficiente de energía (en comparación con el ópimo de energía) cuando es estadísticamente óptimo y casual (solo toma el pasado y el presente en cuenta). Tomar en cuenta todos los posibles escenarios futuros en las aplicaciones de redes es demasiado intensivo computacionalmente, aun para simulaciones. Así, esto es inoperable como una guía para basar esquemas prácticos.

3. Razonamiento de la Difusión de Tráfico
Para lograr una guía práctica, se comienza por la siguiente observación: las rutas de salto mínimo para un usuario para diferentes streams tienden a tener un número mayor de saltos en común. Los nodos en esas rutas mueren más pronto y así limitan el tiempo de vida de la red. La siguiente figura presenta un histograma típico de consumo de energía en cierto punto en el tiempo. Algunos nodos apenas han sido usados y otros casi han terminado su energía.

Si asumimos que todos los nodos son igualmente importantes ningún nodo debería ser más critico que otro. En cada momento cada nodo debería entonces ser usado la misma cantidad de energía, la cual también debería estar minimizada. La siguiente figura muestra un histograma más deseable, aunque el total de consumo de energía es el mismo.

Los esfuerzos para un histograma de energía compacto se traducen en la guía con la que el tráfico debería ser dispersado a través de la red tan uniformemente como sea posible.

III. RUTEO BÁSICO
Como un esquema de ruteo subyaciente, se toma una base en el paradigma de difusión dirigida. Cuando un usuario se une a la red de sensores, anuncia el tipo de información en el que está interesado. Se ha optado por una instancia simple de este paradigma, al cual han llamado Ruteo Basado en Gradiente (Gradient-Based Routing (GBR). Mientras es inundado, el mensaje de interés graba el número de saltos del usuario, llamado el peso del nodo. La diferencia entre el peso del nodo y el del usuario es considerado el gradiente de ese enlace. Un paquete es remitido en el enlace con el gradiente mayor. Aunque las técnicas para incrementar el tiempo de vida de una red están construidas sobre GBR, los principios principales son lo suficientemente generales para también ser aplicables a otros protocolos de ruteo ad-hoc.

IV. COMBINACIÓN DE DATOS.
1.Entidades de Combinación de datos (Data Combining Entities)

Nodos sensores individuales procesan su información antes de transmitirla al usuario. Es ventajoso combinar observaciones de diferentes nodos para incrementar la eficiencia de los recursos. Este proceso reduce no solo la sobrecarga de la cabecera, pero también la información en si misma puede ser compactada ya que contiene en parte la misma información.

Aunque esta combinación puede ser implementada al seleccionar explícitamente una cabecera de cluster, se presenta un esquema que es más robusto a fallas de nodos aleatorios. Primero hay que notar que los nodos sensores que son activados por el mismo evento, son típicamente ubicados en la misma vecindad. La nube resultante de nodos activados también está en una proximidad de comunicación cercana. Simulaciones han mostrado que las DCE´s están ubicadas dentro o muy cerca de esta nube de nodos activados. Este esquema es altamente robusto. Cuando un nodo con una DCE muere, el paquete automáticamente toma una ruta alternativa y pasa a través de otro nodo que puede crear un nuevo DCE.

V. DISPERSIÓN DE TRÁFICO DE RED
1. Técnicas de Dispersión

Esquema Estocástico: cada nodo puede seleccionar el siguiente salto en una manera estocástica. Más específicamente, cuando hay dos o más saltos adyacentes con el mismo gradiente bajo, uno aleatorio es elegido. Esto no incrementa la longitud de la ruta seguida, sin embargo contribuye a la dispersión del tráfico de red.

Esquema basado en energía: Cuando un nodo detecta que su reserva de energía ha disminuido por debajo de cierto umbral, este "desanima" a otros de mandar información a el al incrementar su peso. Esto puede cambiar el peso de un vecino. Este a su vez informa a otros nodos y estas actualizaciones son propagadas tan lejos como sea necesario para mantener consistentes todas las gradientes.

Esquema basado en stream: La idea es desviar nuevos streams de los nodos que son actualmente parte de la ruta de otros streams. Un nodo que recibe paquetes informa a sus vecinos excepto a aquel de donde se origina el stream, al que su peso a incrementado. De nuevo, otros nodos deben asegurarse de que las gradientes permanezcan consistentes. Como resultado de este esquema, el stream original no es afectado, debido a que estos nodos no han actualizado el peso de su siguiente salto. Nuevos streams de paquetes, sin embargo, tomarán otras rutas mientras el peso de los nodos en la primer ruta ha incrementado aparentemente.


Referencia
http://www.shihada.com/F12-344/papers/EnEff_routing_wsn.pdf