viernes, 26 de abril de 2013

Laboratorio : Resumen

Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks

por Deepak Ganesan, Ramesh Govindan, Scott Shenker y Deborah Estrin

Introducción.
Tres criterios impulsan el diseño de redes de sensores a gran escala: la escalabilidad (estas redes podrían involucrar miles de nodos), la eficiencia energética (en particular, la comunicación inalámbrica puede implicar significativamente mayor costo de la energía de computación), y la solidez (a los efectos ambientales y los fallos del nodo y enlace).

Estas redes pueden requerir técnicas de enrutamiento novedosos para la difusión de datos escalables y robustas, como la difusión dirigida. De particular interés es la noción de trayectoria-refuerzo, para que un nodo de la red puede hacer que una decisión local (basada posiblemente en las características del tráfico percibidos) para extraer los datos de uno o más vecinos de preferencia a otros vecinos.

En este trabajo, se propone el uso de múltiples rutas de enrutamiento para aumentar la resistencia de fallo de un nodo. Se exploran algoritmos localizados por dos enfoques diferentes para la construcción de trayectorias múltiples entre dos nodos. Uno de ellos es el clásico múltiples nodos disjuntos. El otro enfoque abandona el requisito de caminos disjuntos y en su lugar se basa en muchos caminos trenzadas.

Se miden dos cosas de estos algoritmos que son la resistencia y la sobrecarga de mantenimiento Hay una compensación entre estas dos cantidades ya que ser más resistente por lo general consumen más energía.

Multitrayecto disjunto.
El primer mecanismo de multitrayecto que se considera, construye un pequeño número de caminos alternativos que son nodos-disjuntos con la ruta principal, y unos con otros. Estos caminos alternativos son por lo tanto afectados por fallos en el camino principal, pero pueden ser potencialmente menos deseable (por ejemplo, tener latencia más larga) que la ruta o camino principal.

Este es un algoritmo localizada para la posible construcción de trayectos disjuntos. Suponemos por un momento que algunas muestras de baja velocidad inicial se han inundado en toda la red. El sumidero tiene alguna información empírica acerca de cuál de sus vecinos puede proporcionarle los datos de mayor calidad (menor pérdida o demora más baja). Para este vecino más preferido, le envía un refuerzo primario de la ruta. Al igual que con el esquema de difusión de dirección básica, entonces ese vecino determina localmente a su vecino más preferido en la dirección de la fuente, y así sucesivamente.

Poco después, a partir de entonces, el sumidero envía una ruta alternativa de refuerzo a su vecino más preferido. Al limitar cada nodo para aceptar sólo un refuerzo, la configuración de rutas alternativas se garantiza que sea mutuamente disjuntos y disjuntos con la ruta principal. Un nodo que recibe más de un reforzamiento, refuerza negativamente todos los refuerzos. Este mecanismo se puede extender trivialmente para construir trayectorias múltiples disjuntos. A esto se le llamara trayectos múltiples disjuntos localizadas.

Multitrayecto trenzado.
Mientras que los trayectos disjuntos tienen algunas propiedades de resistencia atractivas, pueden ser ineficiente para la energía, desde el nodo de caminos-disjuntos podrían ser potencialmente más larga que la ruta o camino principal. El multitrayecto trenzado relaja la exigencia del nodo desarticulado. Vías alternas en una trenza están parcialmente disjunta de la ruta principal, no del todo en el nodo disjunto.

La mejor ruta alternativa no tiene que ser necesariamente completamente un nodo disjunto, con la ruta principal. Al conjunto resultante de caminos (incluyendo la ruta de acceso primario) se le llamó multitrayecto trenzado idealizado. Como su nombre lo indica, los vínculos que constituyen una trenza o bien se encuentran en la ruta de acceso principal, o pueden esperar a estar geográficamente cerca de la ruta principal. En este sentido, los caminos alternativos que forman una trenza serían gastar energía comparable a la ruta o camino principal.

Ahora se describirá como es que trabaja este algoritmo, como en la sección anterior, el sumidero envía un refuerzo por el camino primario a su vecino más preferido. Además, el sumidero envía una ruta de refuerzo alternativo a su vecino preferido. Además, de forma recursiva cada otro nodo en la ruta o camino principal se origina una ruta de refuerzo alternativo a su vecino más preferido. Al hacer esto, cada nodo intenta una ruta alrededor de su vecino inmediato en el camino principal hacia la fuente.

METODOLOGÍAS DE EVALUACIÓN.
Sobrecarga de mantenimiento.
La sobrecarga de mantenimiento de un régimen es una medida de energía necesaria para mantener estos caminos alternativos, usando periódicos mecanismos keep-alive. Se supone que la fuente difunde "r" eventos en algún intervalo de tiempo "T" sobre el camino primario. Entonces, los eventos "εr" se envían por los caminos alternativos de la disjuntos o el multitrayecto trenzado, con cada ruta alternativa que recibe la misma proporción de este tráfico keep-alive. Entonces, la energía necesaria para mantener las rutas alternativas es proporcional a la duración media (en número de saltos) de los caminos alternativos.
Para calibrar significativamente la sobrecarga de mantenimiento, se normaliza con respecto a la longitud del camino más corto. Por lo tanto, la métrica sobrecarga de mantenimiento es:
(La - Lp)/Lp

donde "La" es la longitud media de un camino alternativo, y "Lp" la longitud de la ruta o camino principal.

Fallas.
Se estudia la capacidad de recuperación de los esquemas de enrutamiento multitrayecto a dos modelos muy diferentes de fallo: fallos en los nodos independientes y fracasos geográficamente correlacionados.
  • Las fallas aisladas: El primer modelo de fallo captura fallos en los nodos independientes y representan el cambio de los efectos ambientales locales. Entonces, para cada uno de los esquemas de multitrayecto, se define la resistencia al fracaso aislado en el sentido de la probabilidad de que al menos una ruta alternativa que está disponible dentro del intervalo de, dado que al menos un nodo en el camino principal ha fallado.
  • Las fallas modeladas: El modelo de segundo fracaso captura fracasos geográficamente relacionados. La justificación aproximada para este modelo es que la actividad sostenida o el medio ambiente (como la lluvia) dentro de una región geográfica pueden ocasionar dicho incumplimiento relacionada, ya sea debido a la pérdida de conectividad o debido a la disipación de energía. 
Resultados de la simulación.
Al realizar los experimentos de simulación, el objetivo era entender el equilibrio de energía/capacidad de recuperación entre los distintos esquemas de multitrayectorua, su dependencia a la densidad de la red, y la validación de los modelos idealizados. Un sencillo ejemplo de la compensación de energía/capacidad de recuperación se ilustra en la siguiente figura.


Se puede apreciar que las fallas aisladas, 2 disjuntos multitrayectos idealizadas son mucho menos resistentes, y tienen una mayor sobrecarga de mantenimiento de multitrayecto trenzados idealizado. Para fallas modeladas, los esquemas idealizados tienen la capacidad de recuperación comparable, pero 2 disjuntos tiene una mayor sobrecarga de mantenimiento. Existen diferencias similares a los mecanismos localizados. En las simulaciones se estudia cuidadosamente las repercusiones de cada medida de la variación de los diferentes parámetros.
  • Sobrecarga de mantenimiento: En general, las multrayectos idealizados trenzados requieren menos sobrecarga de mantenimiento que 2-disjuntos multitrayectos idealizados, siendo la diferencia significativa en las densidades más bajas. La heurística trenzada localizada no presenta las mismas propiedades que la versión idealizada a bajas densidades, pero sigue de cerca a densidades más altas. Por último, se cree que los resultados muestran que podría ser más fácil de construir trenzas sobrecargadas que construir caminos disjuntos sobrecargadas utilizando algoritmos localizadas. 
  • La resistencia a fallos aislados: En general, la trenza idealizada es más resistente que el idealizada multitrayecto disjunto, siendo la diferencia significativa en las densidades más altas. Algoritmos localizadas son ligeramente menos resistentes que sus semejantes idealizadas. Las razones de estos es que tanto la trenza localizada y el multitrayecto disjuntos localizada pueden descubrir caminos más largos que sus homólogos idealizadas. 
  • Resistencia a las fallas modeladas: La resistencia al fracaso de la trenza idealizada se compara bien con el idealizado 2-disjuntos y caminos 3-disjuntos. La trenza localizada varía de manera diferente a la densidad que el esquema idealizado con el aumento de la frecuencia de fallo, o el radio de fallo, la resistencia disminuye, aunque el impacto de radio es más dramático. El aumento del nivel de desarticulación (de caminos disjuntos) sólo nos da ganancia modesta capacidad de recuperación, y está sujeto a diferencia de coste grande.

Conclusiones.
Se demuestra que el enrutamiento de trayectos múltiples, se puede utilizar para la recuperación de energía eficiente desde el fracaso en redes de sensores inalámbricos. Se analiza y evalúa un nuevo diseño trenzado que puede ser utilizado a futuro. Para una configuración de múltiples disjuntos en donde el modelado falla de la resistencia se puede comparar a la de trayectos múltiples trenzados, los trayectos múltiples trenzados tienen alrededor del 50% mayor capacidad de resistencia a fallos aislados y un tercio de la parte superior para el mantenimiento de vía de acceso alternativa. 

Se cree que es más difícil de diseñar mecanismos de eficiencia energética para la construcción de caminos disjuntos alternativos, debido a que los algoritmos localizados no tienen información necesaria para encontrar caminos disjuntos de baja latencia. Por último, el aumento del número de caminos disjuntos hace que aumente la resistencia de trayectos múltiples disjuntos, pero con un coste de energía más elevado. No es el caso de que un gasto de energía pequeña mejora la capacidad de recuperación de caminos disjuntos.


Referencias:
Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks
http://dl.acm.org/citation.cfm?id=509514

http://www.it.uc3m.es/~jgr/Doctorado/RSING/Papers/rsing-iseoane.pdf

"Imagenes sacadas de los pdf "

1 comentario:

  1. Falta darle un formato adecuado con datos completos a la referencia bibliográfica. Checa algún tutorial. 6 pts.

    ResponderEliminar