martes, 30 de abril de 2013

Tarea 9 - (LAB)Redes - Energia eficiente en las redes inalambricas de sensores


An Energy Efficient Hierarchical Clustering 
Algorithm for Wireless Sensor Networks


--------------
Autores: Seema Bandyopadhyay and Edward J. Coyle
School of Electrical and Computer Engineering
Purdue University

-------------


Introducción

Los recientes avances en las comunicaciones inalámbricas y sistemas microelectromecánicos tienen la motivación el desarrollo de sensores muy pequeños y de bajo costo que poseen detección, procesamiento de señales y de comunicación inalámbrica capacidades. 
Estos sensores se pueden implementar a un costo mucho más bajo que los sistemas de sensores cableados tradicionales.

Organizar los sensores tales que abarquen el mejor rango posible, es un ahorro de energia siginificativo.
Muchos algoritmos de agrupamiento en diversos contextos han sido propuesto. Estos algoritmos son en su mayoría de naturalueza heurística y el objetivo de generar el número mínimo de agrupaciones de tal manera que cualquier nodo en cualquier grupo es como máximo de saltos de distancia desde el Clusterhead. 

La mayoría de estos algoritmos tienen un tiempo complejidad de O(n), donde n es el número total de nodos. 
Muchos de ellos también exigen sincronización de tiempo entre los nodos, lo que hace que sean adecuadas sólo para redes con un pequeño número de sensores. 

Para las redes de sensores inalámbricas con un gran número de sensores de energía limitada, es muy importante diseñar un algoritmo rápido para organizar en grupos de sensores para reducir al mínimo la la energía utilizada para comunicar información desde todos los nodos al centro de procesamiento. 

Algoritmo

Cada sensor en la red se convierte en una Clusterhead (CH) con probabilidad p y anuncia como un Clusterhead a los sensores dentro de su radio de alcance. Llamamos a estos clusterheads los clusterheads voluntarios. Este anuncio se reenvía a todos los sensores que no son más que k saltos de distancia del Clusterhead. Cualquier sensor que recibe este tipo de etiqueta y no forma parte de un  Clusterhead se une al clúster del Clusterhead más cercano. Cualquier sensor que no es ni un Clusterhead y no tiene unido a ningún grupo en sí se convierte en un Clusterhead, llamamos a estos clusterheads los clusterheads forzadas .

La energía utilizada en la red para obtener la información recogida por los sensores para llegar al centro de procesamiento se dependerá de los parámetros p y k de nuestro algoritmo. Puesto que el objetivo de nuestro trabajo es organizar los sensores en grupos para minimizar el consumo de energía, tenemos que encontrar los valores de los parámetros p y k de nuestro algoritmo para que garantice minimización del consumo de energía.

Los parámetros óptimos para el algoritmo

Para determinar los parámetros óptimos para el algoritmo descrito anteriormente, hacemos los siguientes supuestos:
a) Los sensores de la red de sensores inalámbricos son distribuido como por una homogénea espacial de Poisson proceso de intensidad λ en el espacio de 2 dimensiones.
b) Todos los sensores transmiten al mismo nivel de potencia y por lo tanto tienen el mismo alcance de radio r.
c) Los datos intercambiados entre dos sensores se comunican no dentro del alcance de radio de los demás se remite por otros sensores
d) Una distancia de d entre cualquier sensor y su Clusterhead es equivalente a [d/r]
e) Cada sensor utiliza 1 unidad de energía para transmitir o recibir 1 unidad de datos.
f) Una infraestructura de enrutamiento esta en su lugar, por lo que, cuando un sensor se comunica datos a los otros sensores, sólo el sensor en la direccionde ruteo puede recibir la información.
g) El medio de comunicación es la conexión y libre de errores, por lo que los sensores no tienen que retransmitir cualquier datos.


La idea básica de la derivación de los valores de los parámetros óptimos es definir una función de la energía utilizada en la red para comunicar la información al centro de procesamiento de información y a continuación, encontrar los valores de los parámetros que se reduzcan al mínimo.

Cálculo de la probabilidad óptima de convertirse en un Clusterhead


De acuerdo con nuestras suposiciones, los sensores se distribuyen según un proceso de Poisson espacial homogénea y, por tanto, el número de sensores en una zona cuadrada de lado 2 es una variable aleatoria de Poisson.

Concluciones

La forma en que estén acomodados los sensores y los receptores es una buena forma de quitar sensores innecesarios, y quitando esos sensores extras nos ahorrariamos energía. 
El algoritmo que ellos nos muestran es heurístico y se actualiza con los nodos(sensores) que tengamos, me recuerda a una tarea de unos compañeros en donde tenia que acomodar los "modems" para que abarcara todo el rango posible con el menor números de aparatos basándose en el rango que cubría cada uno.

Los senosres inalambricos es mucho mas eficaz y en algunos casos mas baratos que tener sensores conectados directamente.

Referencias
Autores:
Seema Bandyopadhyay and Edward J. Coyle.