REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
1
Ahorro de Energ´ıa en Sensores de Red ´ Inalambrica Utilizando Algoritmo de ´ Agrupamiento Jerarquico ´ Estudiante, U. de Cuenca Jorge Merchan, ´ Resumen—En este documento se hace un breve resumen de analisis de datos por agrupamiento, ya que hoy en ´ de diversos fenomenos, ´ d´ıa juega un papel importante para la compresion ya que dispone de una amplia cantidad ´ que se puede utilizar para un bien determinado, en este caso se examinara la agrupacion ´ jerarquica ´ de informacion, ´ (Hierarchical Clustering), para el ahorro de energ´ıa en sensores de red inalambrica que consiste en un gran numero ´ ˜ sensores con transceptores de baja potencia, siendo una herramienta eficaz para la recopilacion ´ de datos de pequenos ´ o de paso de mensajes debe estar disenado ˜ en una variedad de entornos. El proceso de comunicacion para conservar ´ ´ los recursos energeticos limitados de los sensores, se utilizara, los resultados de la geometr´ıa estocastica para derivar ´ soluciones para los valores de parametros de nuestro algoritmo para minimizar la energ´ıa total gastada en la red cuando todos los sensores informan. Keywords—Transceptores
F
1
´ I NTRODUCCI ON
E
N la actualidad nos encontramos rodeados de ´ la cual pueuna gran cantidad de informacion, de o no encontrarse almacenado en una base de datos, para su posterior an´alisis, lo que se busca es clasificar o agrupar estos datos en un conjunto de categor´ıas o grupos. B´asicamente, los sistemas ´ son o bien supervisado o no sude clasificacion pervisado, dependiendo de si se asignan nuevas ´ entradas a un numero finito de clases supervisadas ´ respectivadiscretos o categor´ıas sin supervision, ´ supervisada, se mente [1], [2]. En la clasificacion tiene un conjunto de vectores de datos de entrada, ´ maeste se modela en t´erminos de alguna funcion tem´atica, donde se tiene un vector de par´ametros ajustables (pesos). Los valores de estos par´ametros se determinan (optimizado) mediante un algoritmo de aprendizaje. Cuyo objetivo es reducir al m´ınimo ´ no el error de tolerancia [1], [2]. En la clasificacion supervisada, tambi´en llamada an´alisis exploratorio de datos, est´an disponibles datos no etiquetados [3], ´ es separar un conjunto El objetivo de la agrupacion en un conjunto finito y discreto de ”naturales”,
•
J. Merch´an es Estudiante de la Universidad de Cuenca, Facultad de Ingenier´ıa, Escuela de Electr´onica y Telecomunicaciones E-mail:
[email protected]
Manuscript received Juilio 08, 2015; revised Julio 09, 2015.
estructuras de datos ocultos finitos sin etiqueta, en ´ precisa lugar de proporcionar una caracterizacion de las muestras observadas generados a partir de ´ de probabilidad [4], [2]. Los la misma distribucion ´ algoritmos de agrupamiento de datos de particion ´ en un cierto numero de grupos (grupos, subconjuntos o categor´ıas). No tiene universalmente una ´ [3]. En este documento se analiza, La definicion ´ jer´arquica, la cual intenta construir una agrupacion estructura de particiones de a´ rbol-anidadas. En la siguiente figura se analiza brevemente en 4 pasos ´ el an´alisis de agrupacion.
´ ´ con una Figura 1.Pasos del analisis de agrupacion ´ Estos pasos estan ´ estrev´ıa de retroalimentacion. chamente relacionados entre s´ı. ´ de caracter´ısticas: la extraccion ´ 1) Extraccion de caracter´ısticas utiliza algunas transformaciones ´ para generar caracter´ısticas utiles y novedosas de ´ sobre la seleccion ´ las originales. M´as informacion de caracter´ısticas se puede encontrar en [1].
REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
´ ´ 2) Seleccion de algoritmos de clusteres: En ´ este paso normalmente se combina con la seleccion de una medida de proximidad correspondiente ´ de una funcion ´ de criterio. y la construccion Los patrones se agrupan de acuerdo a si se parecen entre s´ı. Sin embargo, no hay algoritmo de agrupamiento que se puede utilizar universalmente para resolver todos los problemas [5. ´ 3) Validacion de grupos: Dado un conjunto de datos, cada algoritmo de agrupamiento siempre ´ no importa si existe puede generar una division, la estructura o no. En general, hay tres categor´ıas de criterios de prueba: los ´ındices externos, ´ındices internos, y los ´ındices relativos. Estos se definen en ´ conocida tres tipos de estructuras de agrupacion, ´ particional, agrupacion ´ jer´arquica como agrupacion y grupos individuales [6]. ´ de Resultados: El objetivo final de 4) Interpretacion ´ es proporcionar a los usuarios una la agrupacion perspectiva interesante de los datos originales, por lo que pueden resolver con eficacia los problemas encontrados. Actualmente existen sensores extremadamente ˜ ´ pequenos y de bajo costo que poseen deteccion, ˜ procesamiento de senales y capacidad de ´ comunicacion inal´ambrica. Estos sensores se pueden implementar a un costo mucho m´as bajo que los sistemas de sensores cableados ˜ tradicionales. Para mantener el costo y el tamano ˜ de estos sensores pequenos, que est´an equipados ˜ con pequenas bater´ıas que pueden almacenar como m´aximo 1 Joule [7]. Esto pone limitaciones significativas en la potencia disponible para las comunicaciones, lo que limita tanto el rango de ´ y la velocidad de datos. El costo de transmision ´ de un bit es mayor que un c´alculo, la transmision y por lo tanto puede ser ventajoso para organizar los sensores en grupos, los datos recogidos por los sensores se comunican al centro de procesamiento de datos a trav´es de una jerarqu´ıa de gruposprincipales. El centro de procesamiento determina las estimaciones finales de los par´ametros en ´ utilizando la informacion ´ comunicada por cuestion los grupos-principales. El centro de procesamiento de datos puede ser un dispositivo. Dado que los sensores est´an comunicando datos a trav´es de ˜ en el entorno de grupo, la distancias m´as pequenas energ´ıa gastada en la red ser´a mucho menor que,
2
la energ´ıa gastada cuando cada sensor se comunica directamente con el centro de procesamiento de la ´ informacion. Para las redes de sensores inal´ambricos con ´ un gran numero de sensores, con limitaciones de ˜ un algoritmo energ´ıa, es muy importante disenar r´apido para organizar sensores en grupos, para reducir al m´ınimo la energ´ıa utilizada para ´ desde todos los nodos comunicar informacion al centro de procesamiento. En este trabajo, se propone un algoritmo distribuido aleatoriamente ´ de los sensores, en r´apido, para la organizacion una red de sensores inal´ambricos con jerarqu´ıa de grupos, con el objetivo de minimizar el gasto ´ de la informacion ´ de energ´ıa en la comunicacion ´ al centro de procesamiento de la informacion. Hemos utilizado los resultados en la geometr´ıa estoc´astica para derivar valores de par´ametros para el algoritmo, que minimice la energ´ıa gastada en la red de sensores [8, 9] jml Julio 10, 2015
2 2.1.
C ONTENIDO ´ Red inalambrica de sensores
Una red inal´ambrica de sensores es un ´ sistema autonomo compuesto de diminutos nodos equipados con sensores y capacidades ˜ y de procesamiento [10]. Su reducido tamano capacidad de transmitir sin cables, permiten un despliegue r´apido y flexible de centenares a miles de dispositivos. Estos nodos se han desarrollado gracias al progreso en los sistemas micro electro mec´anicos (MEMS) y radio frecuencia RF. Cada dispositivo o nodo de la red est´a t´ıpicamente conformado por cuatro componentes [10]: 1. Una o varias unidades de sensores: temperatura, humedad, etc. ´ 2. Una unidad de procesamiento o computo: un microcontrolador con memoria. ´ un transceiver 3. Una unidad de comunicacion: de radio frecuencia. 4. Una unidad de energ´ıa: bater´ıas comunes, tambi´en paneles solares u otras formas de ´ de energ´ıa. recoleccion Estas redes se caracterizan principalmente por [10,11]: ´ Capacidad de auto organizacion. ´ de datos bajas. Tasas de transmision
REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
3
en la pr´actica. Nos centramos en el agrupamiento aglomerativo [3]. Primero definiremos la matriz de proximidad, para luego ver el algortimo: Hace referencia a una ´ de un conjunto de datos para distancia en funcion satisfacer las siguientes condiciones: 1) Simetr´ıa. D(xi , xj ) = D(xj , xi ) 2) Positividad. D(xi , xj ) ≥ 0 para todo xi , xj condiciones if
Figura 2.Arquitectura de hardware de un nodo sensor [10]. Cantidad de energ´ıa disponible para cada nodo limitada. Capacidad computacional y memoria de los nodos limitada. ´ Baja potencia de transmision. Capacidad de operar en ambientes hostiles. Ahora analizaremos el agrupamiento jer´arquico, el ahorro de energ´ıa utilizando este algoritmo, los ´ par´ametros optimos para este algoritmo. 2.2.
´ Agrupamiento Jerarquico
´ jer´arquica (Hierarchical Clustering La agrupacion (HC)), es un algoritmo que organiza los datos en una estructura jer´arquica de acuerdo con la matriz de proximidades. Los resultados de HC se representan generalmente por un a´ rbol binario o dendrograma. El nodo ra´ız del dendrograma representa todo el conjunto de datos y cada nodo hoja es considerado como un objeto de datos. Los nodos intermedios, por lo tanto, describen ´ la medida en que los objetos son proximos entre s´ı, y la altura del dendrograma generalmente expresa la distancia entre cada par de objetos o grupos, o de un objeto y un grupo. Los algoritmos HC se clasifican principalmente como m´etodos aglomerativos y m´etodos divisivos. El m´etodo de ´ aglomerativo comienza con grupos agrupacion y cada uno de ellos incluye exactamente un objeto. En un principio, todo el conjunto de datos pertenece a un grupo y un procedimiento lo divide sucesivamente hasta que todos los grupos son grupos aislados. Para un grupo con varios objetos, existen posibles divisiones de dos subconjuntos, que demanda mucho en el c´alculo. Por lo tanto, ´ de division ´ no se usa comunmente ´ la agrupacion
3) Desigualdad triangular. D(xi , xj ) ≤ D(xi , xk ) + D(xk , xj ) para todo xi , xj , xk 4) Reflexividad. D(xi , xj ) = 0 si y solo si xi = xj tambien llamada metrica. En general el agrupamiento aglomerativo puede resumirse mediante el siguiente procedimiento. ´ 1) Comenzar con N grupos unicos, luego calculamos la matriz de proximidad para los N grupos. 2) Buscar la distancia m´ınima D(Ci , Cj ) = minD(Cm , Cl ), para 1 ≤ m, l ≥ N ´ de con m 6= l donde D(∗, ∗), es la funcion distancia mencionada anteriormente en la matriz de proximidad, y combina el grupo Ci y Cj , para formar un nuevo grupo. 3) Actualizar la matriz de proximidades calculando las distancias entre el nuevo grupo y los dem´as grupos. 4) Repetir los pasos (2,3), hasta que todos los objetos est´en en el mismo grupo. 2.3. Ahorro de energ´ıa utilizando algoritmo de ´ agrupamiento Jerarquico El algoritmo de estudio en este trabajo es similar al algoritmo de agrupamiento en [12]. En [12], los autores han supuesto que los sensores est´an equipados con la capacidad de ajuste de la potencia a la que se transmiten y se comunican con po´ aceptable tencia suficiente para lograr una relacion ˜ con ruido en el receptor. Aqu´ı, por otro de senal lado, se supone una red en la que los sensores son muy simples y todos los sensores transmiten a un nivel de potencia fijo; los datos entre dos sensores
REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
4
que se comunican fuera del radio de alcance de cada uno, se transmitir´a por otros sensores en la red. Los autores, en [12], han observado en sus ´ que en una red con experimentos de simulacion ´ ´ un nivel de agrupamiento, hay un numero optimo de grupos-principales que minimiza la energ´ıa utilizada en la red. En este trabajo, se utiliza los resultados proporcionados en [13] para obtener el ´ ´ numero optimo de grupos-principales en cada nivel ´ de agrupacion, analizando anal´ıticamente la red agrupada, se utiliza este algoritmo para generar un ´ nivel de agrupacion.
que encontrar los valores de los par´ametros p y k ´ de este algoritmo que garantice la minimizacion del consumo de energ´ıa. Se deriva expresiones ´ para los valores optimos de p y k en la siguiente ´ subseccion.
2.3.1 Algoritmo Cada sensor en la red (CH) se inicia como un grupo-principal con probabilidad p y se comunica como un grupo-principal a los sensores dentro de su radio. Llamamos a estos grupos-principales los grupos-principales voluntarios. Este comunicado se env´ıa a todos los sensores que est´an a k saltos de distancia del grupo-principal. Cualquier sensor que recibe este tipo de aviso y no es en s´ı mismo un grupo-principal, se une al grupo del grupo-principal m´as cercano. Cualquier sensor que no es ni un grupo-principal ni se ha unido ´ grupo en s´ı se convierte en un grupoa ningun principal forzado; Debido a que hemos limitado el comunicado de reenv´ıo a k saltos, si un sensor no recibe un aviso del CH dentro del tiempo de ´ t (donde t es el tiempo requerido para que duracion los datos lleguen al grupo-principal de cualquier sensor a k saltos de distancia) se puede inferir que este no est´a dentro de k saltos de cualquier grupoprincipal voluntario y por lo tanto se convertirse en un grupo-principal forzado. Por otra parte, ya que todos los sensores dentro de un grupo est´an dentro de los k saltos de distancia de un grupoprincipal, el grupo-principal puede transmitir la ´ agregada al centro de procesamiento informacion despu´es de cada t unidades de tiempo. Este l´ımite ´ en el numero de saltos permite que los gruposprincipales programen sus transmisiones. Tenga en cuenta que este es un algoritmo distribuido ´ de reloj entre los sensores. y no exige sincronizacion
´ Para determinar los par´ametros optimos para el algoritmo descrito anteriormente, hacemos los siguientes supuestos:
La energ´ıa utilizada en la red para trasmitir ´ recogida por los sensores al centro la informacion de procesamiento depender´a de los par´ametros p y k de este algoritmo. Dado que el objetivo de este trabajo es organizar los sensores en grupos para minimizar este consumo de energ´ıa, tenemos
2.3.2 ´ ´ Parametros optimos para el algoritmo
a) Los sensores en la red de sensores inal´ambricos ´ se distribuyen segun un proceso de Poisson espacial homog´enea 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 radio r. c) Los datos intercambiados entre dos sensores que se comunican fuera del alcance de otros radios, se transmitir´a por otros sensores. d) Una distancia d entre cualquier sensor y su grupo-principal es equivalente a [d/r] saltos. e) Cada sensor utiliza 1 unidad de energ´ıa para transmitir o recibir 1 unidad de datos. f) Una infraestructura de enrutamiento es est´atico, por lo tanto, cuando un sensor comunica los datos ´ a otro sensor, solo los sensores en la ruta de enrutamiento env´ıan los datos. ´ g) El entorno de comunicacion es libre de ´ y sin errores, por lo tanto, los sensores contencion no tienen que retransmitir los datos. ´ de los valores La idea b´asica de la derivacion ´ ´ de los par´ametros optimos es definir una funcion para la energ´ıa utilizada en la red, para comunicar ´ informacion al centro de procesamiento de ´ y luego encontrar los valores de los informacion par´ametros que se reduzcan al m´ınimo.
REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
5
2.3.3 ´ ´ Calculo de la probabilidad optima para convertirse en un grupo-principal
por los sensores en una celda de Voronoi para comunicar una unidad de datos al grupo-principal. Entonces,
Suponiendo, que los sensores se distribuyen ´ segun un proceso de homog´eneo espacial de ´ Poisson y, por tanto, el numero de sensores en una zona cuadrado de lado 2a es una variable aleatoria de Poisson, N con media λA, donde ´ A = 4a2 . Se supone, que para una realizacion particular del procedimiento hay n sensores en esta zona. Adem´as que el centro de procesamiento est´a en el centro de la plaza. La probabilidad de convertirse en un grupo-principal es p, por lo tanto, en promedio, los sensores np se convertir´an en grupos-principales. Di es una variable aleatoria que indica la longitud del segmento de un sensor situado en (xi , yi ), i = 1, 2, ..., n al centro de procesamiento. Sin p´erdida de generalidad, el centro de procesamiento se encuentra en el centro de la qzona de la plaza. Entonces, R E[Di |N = n] = A x2i + yi2 4a12 dA = 0,765a.
E[C1 |N = n] =
Dado que hay un promedio np en un CHs y ´ de cualquier CH es independiente la ubicacion de las ubicaciones de otros CHs, la longitud total de los segmentos de todas estas CHs al centro de procesamiento es 0,765npa. Ahora, ya que un sensor se convierte en un grupoprincipal con probabilidad p, los grupos-principales y los grupos-no-principales se distribuyen como procesos de Poisson homog´eneos espaciales independientes P P 1 y P P 0 de intensidad λ1 = pλ y λ0 = (1 − p)λ respectivamente. Por ahora, se supone que no esta limitando el ´ numero m´aximo de saltos en en los grupos. Cada grupo-no-principal se une al grupo del grupo´ de principal m´as cerca para formar una teselacion Voronoi [10]. Si N v es la variable aleatoria que ´ denota el numero de puntos del proceso P P 0 en cada celda de Voronoi y Lv es la longitud total de todos los segmentos que conectan los puntos del ´ proceso P P 0 al nucleo en una celda de Voronoi, de acuerdo con los resultados en [11], entonces, E[Nv |N = n] = E[Nv ] = E[Lv |N = n] = E[Lv ] =
λ0 λ1 λ0 3/2 2λ1
Se define C1 como la energ´ıa total utilizada
E[Lv |N =n] r
Se define C2 como la energ´ıa total gastada por todos los sensores que comunican 1 unidad de datos a sus respectivos grupos-principales, ya que hay np c´elulas, el valor esperado de C2 condicionado por N, est´a dado por E[C2 |N = n] = npE[C1 |N = n]
Si la energ´ıa total gastada por los grupos´ principales para comunicar la informacion agregada al centro de procesamiento esta dada por C3, entonces, E[C3 |N = n] =
0,765npa r
Se define C como la energ´ıa total gastada en el sistema. Entonces, E[C|N = n] = E[C2 |N = n] + E[C3 |N = n] = 0,765npa np (1−p) √ r 2p3/2 λ + r
en N = n
E[C] = λA
1−p √ 2r pλ
+
0,765npa r
E[C] se reduce al m´ınimo con un valor de p, ´ de, que es una solucion cp3/2 − p − 1 = 0
´ ´ anterior, esta La unica ra´ız real de la ecuacion dada por
p=
1 3c
+
√ 3 2 √ √ 1/3 3c(2+27c2 +3 3c 27c2 +4)
+
√ √ 1/3 3c 27c2 +4) 1 √ 3 3c
(2+27c2 +3
√ donde, c = 3,06a λ
´ Para conocer el numero m´aximo de saltos permitidos entre un sensor y un grupo-principal se puede ver en [14]. Los c´alculos para el ahorro de energ´ıa se encuentran en[14].
REPORTE FINAL SURVEY PAPER, EN LATEX , REDES NEURONALES, JULIO 2015
3
C ONCLUSION
El sistema desarrollado se puede adaptar a varias aplicaciones, por ejemplo medir variables de temperatura, humedad, luz, en data centers, ´ museos, h´abitat de animales y vegetacion, invernaderos, edificios, etc.; facilitando de este modo al usuario final, ˜ Se presento´ una forma general de disenos de agrupamiento, en la que se tiene una ´ para optimizacion ´ del proceso. retroalimentacion, Se ha analizado el algoritmo distribuido por ´ de los sensores en una jerarqu´ıa la organizacion de grupos con el objetivo de minimizar la energ´ıa total gastada en el sistema para comunicar la ´ recogida por estos sensores al centro informacon ´ de procesamiento de informacion.
4
L INK V IDEO .........
R EFERENCIAS [1] [2] [3] [4]
[5]
[6] [7]
[8]
[9]
[10]
[11]
C. Bishop,Neural Networks for Pattern Recognition, New York: Oxford Univ. Press, 1995. V. Cherkassky and F. Mulier,Learning From Data: Concepts, Theory, and Methods, New York: Wiley, 1998. B. Everitt, S. Landau, and M. Leese,Cluster Analysis, London: Arnold, 2001. A. Baraldi and E. Alpaydin,“Constructive feedforward ART clustering networks—Part I and II,” IEEE Trans. Neural Netw., vol. 13, no. 3, pp. 645–677, May 2002. J. Kleinberg,“An impossibility theorem for clustering,” in Proc. 2002 Conf. Advances in Neural Information Processing Systems, vol. 15, 2002, pp. 463–470. A. Jain and R. Dubes,Algorithms for Clustering Data, Englewood Cliffs, NJ: Prentice-Hall, 1988. J. M. Kahn, R. H. Katz and K. S. J. Pister,“Next Century Challenges: Mobile Networking for Smart Dust”, in the Proceedings of 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 99), Aug. 1999, pp. 271-278. A. B. McDonald, and T. Znati,“A Mobility Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks”, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, pp. 1466-1487, Aug. 1999. A. D. Amis, and R. Prakash,“Load-Balancing Clusters in Wireless Ad Hoc Networks”, in Proceedings of ASSET 2000, Richardson, Texas, March 2000. W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan,“Energy-Efficient Communication Protocol for Wireless Microsensor Networks”, in Proceedings of IEEE HICSS, January 2000. S. G. Foss and S. A. Zuyev,“On a Voronoi Aggregative Process Related to a Bivariate Poisson Process”, Advances in Applied Probability, Vol. 28, no. 4, pp. 965-981,1996.
6
M. Ilyas, I. Mahgoub,Handbook of Sensor Networks: Compact Wireless and Wired Sensing Systems, CRC Press LLC, 2005. [13] K. Sohraby, D. Minoli, T. Znati,Wireless Sensor Networks Technology - Protocols And Applications, WILEY, 2007. [14] S. Bandyopadhyay and E. J. Coyle,An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks, School of Electrical and Computer Engineering, Purdue University West Lafayette, IN, USA [12]
