Análisis del conformado del haz para optimizar el consumo energético en redes de sensores usando metaheurísticas

An´alisis del conformado del haz para optimizar el consumo energ´etico en redes de sensores usando metaheur´ısticas J. Enrique Agudo1, Juan F. Valenzuela-Vald´es2, Francisco Luna3, Rafael M. Luque-Baena1, and Pablo Padilla2 1Dpto. de Ingenier´ıa de Sistemas Inform´aticos y Telem´aticos, Centro Universitario de M´erida, Universidad de Extremadura {jeagudo,rmluque}@unex.es 2Dpto. Teor´ıa de la Se˜nal, Telem´atica y Comunicaciones, Universidad de Granada {juanvalenzuela,pablopadilla}@ugr.es 3Dpto. de Lenguajes y Ciencias de la Computaci´on, Universidad de M´alaga [email protected] Resumen Conformar el haz de forma colaborativa en una red de sensores permite reducir la potencia consumida en la comunicaci´on inal´ambrica, un aspecto cr´ıtico para aumentar el tiempo de vida de este tipo de sistemas donde la energ´ıa proviene de fuentes limitadas como bater´ıas o pilas. Este trabajo analiza el impacto de la dimensionalidad en la dificultad de resoluci´on del problema del conformado del haz atendiendo a dos factores: n´umero de sensores que intervienen y tipo de antena instalado en los sensores. La evaluaci´on preliminar utilizando algoritmos del estado del arte ha mostrado que, fijado el tipo de antena, el n´umero de nodos hace que el problema sea mucho duro por las condiciones que impone el conformado colaborativo del haz. En cualquier caso, los resultados tambi´en muestran que el tiempo de vida de la red de sensores se incrementa considerablemente usando esta t´ecnica. Keywords: Redes de sensores, eficiencia energ´etica, conformado del haz 1. Introducci´on Las redes de sensores (Wireless Sensor Networks, o WSNs por sus siglas en ingl´es) han emergido como una de las tecnolog´ıas m´as prometedoras de los ´ultimos a˜nos. Hay dos indicadores que constatan este hecho: el primero es el n´umero de art´ıculos de revisi´on publicados, e.g., [11] (y las revisiones anteriores que contiene); el segundo son las predicciones en volumen de negocio que han ido desde 450 millones de d´olares en 2012 y se estima que asciendan a 2000 millones en 2022 [10]. Las WSNs ofrecen numerosas ventajas con respecto a las redes tradicionales, como bajo coste, escalabilidad, fiabilidad, precisi´on, flexibilidad y facilidad de despliegue, permitiendo su aplicaci´on en una gran diversidad de aplicaciones. 166 J. Enrique Agudo et al. Una WNS se puede definir como una red de dispositivos, llamados nodos o sensores, que est´an distribuidos espacialmente y trabajan de forma colaborativa para comunicar informaci´on, a trav´es de enlaces inal´ambricos, que se recolecta de un ´area que se desea monitorizar [2]. La informaci´on obtenida se transfiere a un nodo distinguido que, bien utiliza los datos localmente, bien est´a conectado a otras redes (e.g., Internet). Este nodo se denomina HECN (High Energy Communication Node en ingl´es). En una WSN la informaci´on es transmitida entre el HECN y un sensor particular cuando ambos est´an lo suficientemente pr´oximos, o bien se usan los sensores intermedios como routers. T´ıpicamente, los nodos se organizan de forma aut´onoma para establecer las comunicaciones. La caracter´ıstica principal de las WSNs radica en la naturaleza de los propios nodos, que tienen recursos muy limitados (capacidad de c´omputo, memoria, etc.) debido a su tama˜no. En particular, la energ´ıa disponible en cada nodo se considera como el par´ametro m´as cr´ıtico, ya que se emplean bater´ıas de un tama˜no muy peque˜no. Esto obliga a utilizar los recursos de forma eficiente para alargar la vida de la WSN, y es una de las l´ıneas donde se han desarrollado m´as avances, e.g., enrutamiento eficiente [6]. Este es el contexto tambi´en de este trabajo: mejorar la eficiencia energ´etica de las comunicaciones inal´ambricas que se usan en las WSN, empleando para ello t´ecnicas de conformado del haz [8]. La t´ecnica del conformado de haz es ´util para recibir y transmitir se˜nales de una forma selectiva en el espacio, es decir puede recibir y enviar las se˜nales en una determinada direcci´on. Si tenemos en cuenta que el HECN est´a localizado normalmente en un punto fijo del ´area de trabajo, esta t´ecnica resulta especialmente ´util. Al igual que se puede mejorar la transmisi´on en una determinada direcci´on, tambi´en se puede anular la trasmisi´on de potencia a zonas no deseadas y no recibir as´ı se˜nal ´estas (esto puede servir para evitar recibir se˜nales interferentes). En [13], ya se ha mostrado que la conformaci´on de haz se puede utilizar en el contexto de WSNs para llevar a cabo un ahorro de energ´ıa en la transmisi´on de datos, realizando comunicaciones de datos de forma eficiente, y permitiendo as´ı que el tiempo de vida de las redes de sensores aumente. Para ello se formul´o un problema de optimizaci´on en el que se la excitaci´on de la antena de cada sensor, dado por la amplitud y fase, constitu´ıan el espacio de b´usqueda y el objetivo final era maximizar el tiempo de vida de la red (medido como el tiempo en el que el primer sensor se queda sin bater´ıa). El objetivo de este trabajo es analizar en profundidad este nuevo problema de optimizaci´on en base al n´umero de sensores que se utilizan para conformar el haz y el tipo de antena que instalan (isotr´opica, dipolo, o h´elice). El problema se ha abordado con cuatro algoritmos, dos del estado del arte, Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [9] y Differential Evolution (DE) [12], y uno cl´asico como es un algoritmo gen´etico (GA) [3], en sus versiones generacional (gGA) y estado estacionario (ssGA). Los resultados han mostrado que el tipo de antena es cr´ıtico en la definici´on del problema y que, a igualdad de antena, aumentar el n´umero de sensores hace que el problema de optimizaci´on sea m´as duro (a pesar de que desde el punto de vista te´orico, el conformado del haz deber´ıa ser m´as eficiente). Actas de la XVI Conferencia CAEPIA, Albacete Nov 2015 167 El art´ıculo est´a organizado de la siguiente manera. La Secci´on 2 describe el modelo de formaci´on de haz utilizado para WSN. La Secci´on 3 describe brevemente los algoritmos de optimizaci´on utilizados. En la Secci´on 4 se analizan y discuten los resultados obtenidos. Finalmente, las conclusiones se resumen en la Secci´on 5. 2. Conformado del haz en redes de sensores Esta secci´on detalla brevemente en qu´e consiste la t´ecnica de conformado del haz y define formalmente el problema de optimizaci´on que se aborda en el trabajo. 2.1. Conformado del haz Para la obtenci´on de un patr´on de radiaci´on altamente directivo con t´ecnicas de conformaci´on de haces, es necesario que el campo de cada elemento individual interfiera constructivamente en las direcciones deseadas y destructivamente en el espacio restante. Para conformar el patr´on general de la agrupaci´on de antenas, es posible configurar 5 variables. Estas 5 variables se pueden agrupar en dos categor´ıas diferentes (configuraci´on del elemento individual y situaci´on espacial del elemento individual): Configuraci´on del elemento individual: 1. El patr´on de radiaci´on de los elementos individuales. Es decir, diferentes tipos de antenas tienen patrones diferentes de radiaci´on (dipolo, grupo de parches, etc.) 2. Amplitud de excitaci´on de los elementos individuales. 3. Fase de excitaci´on de los elementos individuales. Situaci´on espacial del elemento individual: 1. La geometr´ıa de la red de antenas (lineal, circular, rectangular, esf´erica, etc.). 2. Separaci´on entre los distintos elementos (distancia entre los diversos elementos de array). La forma m´as f´acil y m´as conveniente para colocar los elementos de una matriz es una l´ınea recta, con la misma separaci´on entre los elementos y la misma excitaci´on de amplitud. Con esta configuraci´on o cualquier otra disposici´on relativamente simple (circular, matriz cuadrada con igual espaciado entre los elementos), es bastante f´acil de calcular la fase de la alimentaci´on de los elementos con el fin de obtener un patr´on de radiaci´on deseado. Sin embargo, en el contexto de las WSNs, los nodos se despliegan de forma arbitraria en un ´area cerrada (la mayor´ıa de las veces incluso al azar) y, como consecuencia, el uso de la formaci´on de haz no es una tarea f´acil. De hecho, las primeras aproximaciones aplicando el conformado de haz a las redes de sensores solo tienen unos a˜nos de antiguedad. En [5], los autores demostraron la existencia de una alimentaci´on ´optima para 168 J. Enrique Agudo et al. los elementos individuales (las variables 2 y 3 se han definido anteriormente) para obtener una ganancia m´axima en la direcci´on deseada. El enfoque propuesto en [7] afirma que se ahorra el 80 % de la energ´ıa con la formaci´on de haz. En [1], los autores proporcionan un modelo te´orico para las ganancias obtenidas con la formaci´on de haz mediante el despliegue de nodos usando una distribuci´on gaussiana. En este trabajo el ahorro de energ´ıa es calculado para cada uno de los escenarios planteados. 2.2. Definici´on del problema de optimizaci´on Estamos considerando en este trabajo que la red de sensores se despliega de forma aleatoria, siendo el ´area de trabajo de una cuadr´ıcula. Una vez desplegada la red de sensores, los sensores no se mueven (es decir, son redes de sensores est´aticas). El despliegue aleatorio de sensores es una estrategia muy com´un en WSNs, ampliamente utilizado en la literatura publicada (por ejemplo, [1]). Los sensores est´an equipados con una antena que tiene un determinado diagrama de radiaci´on y se alimenta con una amplitud y fase determinadas. Cada sensor tiene la bater´ıa limitada que se utiliza tanto para monitorizar el entorno, como para transmitir estos datos a la HECN. Se supone que la potencia total disponible para todos los sensores es la misma, pero hemos considerado diferentes tipos de sensores. Se diferencian entre s´ı en la cantidad de energ´ıa dedicada a la detecci´on y por tanto la energ´ıa que queda disponible para la transmisi´on de datos. Hemos modelado esta energ´ıa con un n´umero aleatorio distribuido uniformemente entre [0.4,0.6] (debe existir al menos un m´ınimo de energ´ıa para transmitir). Por lo tanto, la energ´ıa disponible (Eax) para el sensor n(n= 1,2,..., hasta el m´aximo n´umero de sensores) es la siguiente: Ean=En t×Fn,(1) donde En tes la energ´ıa total disponible en el sensor nyFnes el factor aleatorio descrito anteriormente. Se puede obtener la energ´ıa consumida el sensor n(Ecn) como Ecn=Pn tx ×tn,(2) donde Pn tr es la potencia para transmitir los datos en el sensor n,tnes el tiempo de transmisi´on de ny, por tanto, la potencia disponible en n(P an) es P an=Pn tr ×Fn.(3) As´ı, el m´aximo tiempo de vida (tn lifex) un sensor n(es decir, el tiempo m´aximo que pueden operar sin consumir su bater´ıa) se define igualando la energ´ıa consumida igual a la energ´ıa disponible, esto es: En t×Fn=Pn tx ×tn life .(4) Por tanto, dado un sensor n, su tiempo de vida se puede expresar como sigue: tn life =En t×Fn Pn tx .(5) Actas de la XVI Conferencia CAEPIA, Albacete Nov 2015 169 En la Ecuaci´on 5, Pn tx es la potencia necesaria para transmitir los datos cuando no se usa la t´ecnica de conformado de haz. Sin embargo cuando se usa conformado de haz Pn tx es la excitaci´on en amplitud de cada sensor. Adem´as cuando se usa la t´ecnica de conformado de haz, se produce una ganancia de potencia en unas direcciones y una p´erdida de potencia en otras direcciones. Por tanto la potencia utilizada para transmitir datos al receptor es PnBA tx =Pn tx ×GB , (6) donde PnBA tx es la excitaci´on en amplitud de cada sensor, PnB tx es la excitaci´on en amplitud y fase de cada sensor y GB es la ganancia del array en la direcci´on de recepci´on. Por tanto cuando se usa la t´ecnica de conformado de haz, Pn tx es Pn tx =PnB tx GB (7) Y el tiempo de vida de los sensores con conformado de haz (tnB life) se define como: tnB life =En t×Fn×GB PxB tx .(8) El objetivo de este trabajo es maximizar el tiempo de vida de la red completa de sensores. Esto significa que buscaremos las excitaciones en modulo y fase para cada sensor de forma que m´ax tW SN = m´ın ntnB life, n ∈[1,max sensors] ,(9) esto es, el tiempo de vida de la red de sensores viene determinado por el primer sensor que se queda sin bater´ıa y, por tanto, el problema de optimizaci´on consiste en maximizar el tiempo de vida de los sensores, un aspecto cr´ıtico en las redes de sensores. 3. Algoritmos Esta secci´on esboza brevemente los cuatro algoritmos utilizados para abordar el problema: dos GAs est´andar [3], uno generacional (gGA) y estado estacionario (ssGA), as´ı como dos algoritmos del estado del arte, DE [12] y CMA-ES [9]. Todos los algoritmos considerados son metaheur´ısticas basadas en poblaci´on que manejan un conjunto de soluciones tentativas al problema (en este trabajo, un vector de reales con las amplitudes y fases de las antenas instaladas en los sensores), que se modifican con operadores de b´usqueda, normalmente estoc´asticos, para encontrar mejores soluciones. Los GAs usan operadores de selecci´on, cruce y mutaci´on. La diferencia fundamental entre un gGA y un ssGA es que, en el primero, en cada iteraci´on se genera una poblaci´on completamente nueva a partir de la anterior (mejorado con alg´un tipo de estrategia elitista que impide que las mejores soluciones se pierdan), mientra en un ssGA se genera una soluci´on en cada iteraci´on y se inserta en la poblaci´on, permitiendo la recombinaci´on entre padres e hijos. DE, por su parte, es un algoritmo especializado en optimizaci´on num´erica que utiliza 170 J. Enrique Agudo et al. 0 −5 −10 −15 −20 −25 −30 −35 15 30 45 60 75 90 105 120 135 150 165 −180 −165 −150 −135 −120 −105 −90 −75 −60 −45 −30 −15 −0 Phi = 0 Theta TOT pattern cuts for specified Phi Freq 300 MHz 0 −5 −10 −15 −20 −25 −30 −35 15 30 45 60 75 90 105 120 135 150 165 −180 −165 −150 −135 −120 −105 −90 −75 −60 −45 −30 −15 −0 Phi = 0 Theta TOT pattern cuts for specified Phi Freq 300 MHz 0 −5 −10 −15 −20 −25 −30 −35 15 30 45 60 75 90 105 120 135 150 165 −180 −165 −150 −135 −120 −105 −90 −75 −60 −45 −30 −15 −0 Phi = 0 Theta TOT pattern cuts for specified Phi Freq 300 MHz (a) (b) (c) Figura 1. Diagramas de radiaci´on de los tres tipos de antenas utilizadas: (a) isotr´opica, (b) dipolo y (c) h´elice una recombinaci´on especial en el que la diferencia ponderada entre dos individuos de la poblaci´on se a˜naden a un tercer individuo. Por ´ultimo, CMA-ES es una aproximaci´on de segundo orden que estima una matriz de covarianza de forma iterativa, y que sirve para muestrear el espacio de b´usqueda mediante transformaciones en base a dicha matriz. 4. Experimentaci´on Esta secci´on incluye la metodolog´ıa seguida para la realizaci´on de los experimentos, as´ı como los detalles necesarios para su reproducibilidad, detallando la parametrizaci´on de los mismos. La ´ultima secci´on se dedica al an´alisis y evaluaci´on de los resultados obtenidos. 4.1. Metodolog´ıa y parametrizaci´on Por cada algoritmo y n´umero de sensores de la WSN se han realizado 30 ejecuciones independientes para obtener suficiente confianza estad´ıstica. Dado que el despliegue de la WSN es aleatorio, se ha garantizado que todos los algoritmos se enfrentan a los mismos 30 escenarios en cada configuraci´on (posicionamiento de los sensores, tipo de antena instalada y energ´ıa disponible para transmisi´on en cada uno de ellos: ver Sec. 2.2). La Figura 1 muestra el diagrama de radiaci´on de los tres tipos de antenas que pueden instalar los sensores. Se ha optado por una configuraci´on homog´enea, es decir, todos los sensores usan el mismo tipo. En cuanto a la configuraci´on de energ´ıa de cada nodo, la energ´ıa disponible en cada sensor, Et= 3600 Jul., la potencia necesaria para la transmisi´on P txx= 0.1 Watt, y la direcci´on del HECN para conformar el haz: 135o. Despu´es de realizar alguna experimentaci´on preliminar, los par´ametros de funcionamiento de los algoritmos se incluye en la Tabla 1. En todos los casos, la condici´on de parada se ha definido en base al n´umero de sensores. Queda claro que m´as sensores implica un espacio de b´usqueda m´as grande y, por tanto, el muestreo debe ser mayor. El an´alisis de los experimentos previos nos ha llevado a fijar la condici´on de parada en el c´omputo de, como m´aximo, N×2500 evaluaciones de funci´on, donde Nes el n´umero de sensores de la instancia. Actas de la XVI Conferencia CAEPIA, Albacete Nov 2015 171 Tabla 1. Parametrizaci´on de los algoritmos. Nes el n´umero de sensores. Parametrizaci´on de gGA y ssGA Tama˜no de poblaci´on 100 individuos Selecci´on tornero binario + tornero binario Recombinaci´on SBX, pc= 0.9 Mutaci´on Polinomial, pm= 1.0/2.0∗N Parametrizaci´on de DE Tama˜no de poblaci´on 100 individuos Variante rand/1/bin” CR 0.5 F0.5 Parametrizaci´on de CMA-ES Tama˜no de poblaci´on 10 individuos 0 20 40 60 80 100 120 140 160 180 0 2 4 6 8 10 12 14 16 18 20 Ángulo Ganancia Figura 2. Conformado del haz con una WNS de 20 sensores que instalan h´elices Recordar, por ´ultimo, que las soluciones tentativas que manejan los algoritmos son vectores de valores reales con la amplitud y la fase de excitaci´on de las antenas instaladas en los Nsensores, y en ese orden. Es decir, primero est´an representadas las amplitudes y despu´es las fases. Los valores que pueden tomar los primeros van entre 0.1 y 1.0, y los segundos entre -1.0 y 1.0. 4.2. Resultados Las Tablas 2, 3 y 4 incluyen el tiempo de vida de la WSN cuando se utilizan 2, 3, 4, 5, 6, 7, 10 y 20 sensores para realizar el conformado del haz usando, respectivamente, antenas isotr´opicas, dipolos y h´elices. El an´alisis de los resultados se van a estructurar, primero, en base al tipo de antena instalada y, segundo atendiendo al n´umero de sensores. Atendiendo al tipo de antena Hay una conclusi´on clara que se extrae directamente de los resultados num´ericos incluidos en las tablas. Es mucho m´as f´acil conformar un haz con una gran ganancia que nos aumente el tiempo de vida 172 J. Enrique Agudo et al. Tabla 2. Tiempo de vida de la WSN alcanzado por los cuatro algoritmos cuando los sensores instalan antenas isotr´opicas. Isotr´opica #s ssGA gGA DE CMA-ES 2 454.527±41.166 454.522±41.166 454.527±41.166 453.329±42.123 3444.028±35.576 444.018±35.576 444.005±35.570 443.298±35.724 4437.289±32.252 437.277±32.249 437.006±32.198 427.926±43.386 5429.544±25.801 429.661±25.807 428.690±25.950 421.052±27.875 6427.550±23.478 427.527±23.480 425.535±23.960 398.573±39.368 7427.340±27.832 428.234±26.810 427.175±27.938 404.521±35.269 10 413.947±21.945 418.158±18.544 418.010±18.610 376.856±30.186 20 398.489±18.491 408.183±11.676 409.756±11.042 335.923±27.925 Tabla 3. Tiempo de vida de la WSN alcanzado por los cuatro algoritmos cuando los sensores instalan antenas de tipo dipolo. Dipolo #s ssGA gGA DE CMA-ES 2 454.341±41.154 454.338±41.154 454.341±41.154 454.290±41.212 3443.607±35.604 443.819±35.581 443.802±35.588 443.415±35.686 4437.110±32.230 437.046±32.091 436.805±32.075 431.887±32.929 5429.485±25.807 429.460±25.779 429.079±25.848 419.927±30.547 6427.283±23.476 427.340±23.465 426.611±23.417 408.752±29.314 7427.699±26.422 428.122±26.740 425.858±27.529 398.004±58.138 10 418.109±18.799 417.853±18.683 416.652±18.891 375.524±34.459 20 402.623±14.298 405.581±41.183 409.764±11.300 331.743±37.817 Tabla 4. Tiempo de vida de la WSN alcanzado por los cuatro algoritmos cuando los sensores instalan antenas de tipo h´elice. H´elice #s ssGA gGA DE CMA-ES 2 3.755±0.841 3.755±0.841 3.755±0.841 3.755±0.841 33.509±0.740 3.509±0.740 3.509±0.740 3.478±0.755 43.591±0.550 3.591±0.550 3.589±0.550 3.510±0.532 53.563±0.490 3.563±0.490 3.555±0.490 3.466±0.482 63.501±0.416 3.501±0.416 3.486±0.421 3.347±0.406 73.642±0.450 3.641±0.450 3.625±0.428 3.442±0.413 10 3.413±0.329 3.428±0.317 3.425±0.318 3.032±0.432 20 3.240±0.224 2.552±0.262 3.293±0.218 2.604±0.309 de la WSN cuando se utilizan antenas isotr´opicas o dipolos. De forma general, los tiempo de vida de la WSN, atendiendo a la energ´ıa disponible en los nodos y al modelado de la misma utilizado (ver Sec. 2), est´an por encima de las 400 horas (en promedio). En el caso de tener instaladas antenas de tipo h´elice, el tiempo de vida cae dram´aticamente a poco m´as de tres horas. La justificaci´on de este resultado tiene que ver con que la fase a la que se excitan este tipo de antenas tienen una influencia casi nula en la conformaci´on del haz [4], es decir, Actas de la XVI Conferencia CAEPIA, Albacete Nov 2015 173 0 20 40 60 80 100 120 140 160 180 0 10 20 30 40 50 60 70 80 90 100 Ángulo Ganancia (a) Conformado del haz cuando se utilizan 5 sensores 0 20 40 60 80 100 120 140 160 180 0 10 20 30 40 50 60 70 80 90 100 Ángulo Ganacia (b) Conformado del haz cuando se utilizan 20 sensores Figura 3. Conformado del haz cuando se utilizan (a) 5 y (b) 20 sensores es muy dif´ıcil cambiar la direcci´on a la que apunta cuando se instala. Dado que el despliegue es aleatorio, cada una puede irradiar en una direcci´on diferente y, por tanto, la ganancia en 135oes muy baja. Esto implica m´as energ´ıa para transmitir informaci´on, lo que reduce as´ı el tiempo de vida. La Figura 2 ilustra este hecho: la mayor ganancia se obtiene en ´angulos donde no se encuentra el HECN, por la disposici´on inicial de los sensores. Atendiendo al n´umero de sensores para conformar el haz Para WSNs que instalan la misma antena, el n´umero de sensores que se utilizan para conformar el haz tambi´en ha mostrado una tendencia clara: m´as sensores supone un menor tiempo de vida. Adem´as este descubrimiento es consistente para cualquiera de los cuatro algoritmos utilizados. Estos resultados se pueden justificar desde dos puntos de vista: el de teor´ıa de la se˜nal y el de la complejidad del problema para los algoritmos de optimizaci´on. En el primer caso, desde el punto de vista te´orico, cuando la posici´on de las antenas no es aleatoria, conformar el haz con un mayor n´umero de elementos es m´as f´acil. Sin embargo, el despliegue aleatorio supone un escollo importante, ya que sincronizar las excitaciones de las antenas para que las se˜nales que generan sumen en una direcci´on concreta (135o en nuestro caso) es complejo. Es decir, a m´as sensores, m´as dif´ıcil sincronizar.