Optimitzación multi-objetivo de redes de sensores basada en simulates annealing

T rabajo F in al de G rad o

GRADO DE INGENIERÍA INFORMÁTICA

Optimización multi-objetivo de redes de sensores basada en simulated annealing

ISABEL LÓPEZ RAMÍREZ

Tutor

Sebastià Galmés Obrador

Escuela Politécnica Superior

Universidad de las Islas Baleares

i

En primer lugar quiero agradecer a todo aquel que me ha acompañado durante este largo camino. Haciendo especial mención a mis amigos de la carrera, a mis profesores y a mi tutor, el cual ha sido un gran apoyo, ya que durante toda esta etapa me ha ayudado , aconsejado y confiando siempre en mi.

Por último me gustaría dedicárselo también a mis padres y en especial a mi hermana, la cual me ha brindado su ayuda incondicional. Ellos han hecho que todo fuera más

Í NDICE GENERAL

Índice general iii

Índice de figuras v

Índice de cuadros vii

Acrónimos ix

Resumen xi

1 Introducción 1

1.1 Descripción básica de las redes de sensores y su relevancia actual en el

ámbito de las TIC . . . 1

1.2 Formulación del problema . . . 2

1.3 Objetivo general del proyecto . . . 2

1.4 Objetivos concretos . . . 2

1.5 Estructura de la memoria . . . 3

2 Redes de sensores 5 2.1 Descripción . . . 5

2.1.1 Modelo energético . . . 7

2.1.2 Arquitectura de red . . . 8

2.1.3 Taxonomía de las redes de sensores . . . 13

2.2 Diseño de una red de sensores . . . 14

2.3 Aplicaciones . . . 15

2.4 Hardware . . . 17

2.5 Software. . . 20

2.6 Seguridad . . . 20

2.6.1 Ataques . . . 20

2.6.2 Defensas . . . 22

2.6.3 Conclusiones . . . 22

3 Simulated annealing 23 3.1 Introducción a las técnicas de optimización . . . 23

3.2 Versión estándar desimulated annealing . . . 24

3.3 Extensión multi-objetivo . . . 26 4 Aplicación deSimulated Annealingal diseño de una red de sensores 29

iv ÍNDICE GENERAL

4.1 Selección de objetivos . . . 29

4.2 Caracterización de los objetivos . . . 29

4.3 Tecnología utilizada . . . 30

4.4 Diseño a nivel de pseudocódigo . . . 31

4.5 Resultados . . . 32

5 Aplicación al diseño de una red de prevención de incendios forestales 39 5.1 Descripción del escenario . . . 39

5.2 Plataformashardware. . . 43

5.3 Análisis de resultados . . . 45

6 Conclusiones 49

A Código. 51

Bibliografía 59

Í NDICE DE FIGURAS

2.1 Componentes de un nodo. . . 6

2.2 Esquema de despliegue de nodos de un entorno. . . 7

2.3 Modelo de red OSI. . . 9

2.4 Arquitectura de los diferentes planos de la pila. . . 11

2.5 Esquema de red activada por usuario. . . 13

2.6 Esquema de red activada por eventos. . . 13

2.7 Esquema de red activada por tiempo. . . 14

2.8 Ejemplo de despliegue de sensores, cuya información trata luego la aplica- ción Sentilo. . . 14

2.9 Aplicaciones de redes de sensores. . . 16

2.10 EjemploCenWits. . . . 17

2.11 SensorMica2. . . . 17

2.12 SensorParticles. . . . 19

2.13 SensorSHIMMER-2. . . . 19

3.1 Diagrama del funcionamiento del SA. . . 25

4.1 Conjunto de Pareto-2 Nodos . . . 32

4.2 Conjunto de Pareto-4 Nodos . . . 33

4.3 Conjunto de Pareto-6 Nodos . . . 33

4.4 Conjunto de Pareto-8 Nodos . . . 34

4.5 Conjunto de Pareto-10 Nodos . . . 34

4.6 Conjunto de Pareto-12 Nodos . . . 35

4.7 Conjunto de Pareto-15 Nodos . . . 35

4.8 Conjunto de Pareto-20 Nodos . . . 36

4.9 Nodos repetidores . . . 37

4.10 Tiempo en ejecución en horas. . . 37

4.11 Soluciones conjuntos Pareto. . . 38

5.1 Mapa de riesgo de incendio forestal en Mallorca. . . 40

5.2 Ubicación de Estellencs en el mapa de Mallorca. . . 41

5.3 Despliegue de la red de sensores en Estellencs. . . 41

5.4 Eje temporal con ejemplos de sensores. . . 43

5.5 Esquema conexión mediante tecnologíaLoRaWAN. . . . 44

5.6 Esquema del despliegue generado por el MOSA. . . 45

5.7 Ejemplo de distribución nodos dominante respecto al despliegue de Este- llencs. . . 46

vi Índice de figuras

5.8 Ejemplo 2 de distribución de nodos dominante respecto al despliegue de Estellencs. . . 47

Í NDICE DE CUADROS

2.1 Ejemplos de protocolos por capas del modelo OSI. . . 11

2.2 Descripción técnica del sensor Mica2 . . . 18

2.3 Descripción técnica del sensor TinyNode 584 . . . 19

3.1 Diseño de objetivos y criterios de optimización. . . 27

5.1 Coordenadas GPS de cada nodo y coordenadas XY en metros . . . 42

5.2 Especificaciones técnicas TEHU-2121 . . . 44

A ^CRÓNIMOS

ARQ Automatic Repeat Request CPU Central Processing Unit

CMOS Complementary metal-oxide-semiconductor CTP Collection Tree Protocol

DoS Denial of Service

FEC Forward Error Connection FIFO First in First Out

GPS Global Positioning System IoT Internet of Things

IO Investigación Operativa IP Internet Protocol

MAC Medium Access Control MST Minimun Spanning Tree

MOSA Multi-objective Simulated Annealing OSI Open System Interconnection

PER Packet Error Rate PLR Packet Loss Rate SPR Shortest Path Routing

TIC Tecnologías de la Información y las Comunicaciones USB Universal Serial Bus

VLSI Very-larg-scale integration WIFI Wireless Fidelity

R ^ESUMEN

El propósito principal de este trabajo es desarrollar una solución al problema de la planificaci ´n de la topología de una red de sensores para monitorización ambiental, con el fin de satisfacer varios objetivos de diseño. En particular, se han abordado conjunta- mente la maximización del tiempo de vida de la red y la minimización del número de nodos repetidores adicionales, mediante la técnica heurística consistente en la exten- sión multi−objetivo deSimulated Annealing. Este trabajo permite sumergir al lector en el mundo de las redes de sensores, cuya descripción se aborda en el primer capítulo.

A continuación, se explican con detalle las bases del algoritmoSimulated Annealing, en su versión original, y su extensión multi−objetivo conocida comoMulti−Objective Simulated Annealing, para los objetivos de diseño seleccionados. Después de comentar los resultados obtenidos al ejecutar la versión extendida para topologías genéricas, finalmente toda la teoría expuesta es ilustrada con una aplicación a un caso de uso relacionado con los incendios forestales.

C

1

I NTRODUCCIÓN

1.1 Descripción básica de las redes de sensores y su relevancia actual en el ámbito de las TIC

Las redes de sensores constituyen la tecnología de información y comunicaciones más atractiva para aquellas aplicaciones en las que la interacción con el mundo físico es esencial.

Esta tecnología, surgida a principios de los años 90, permite la monitorización de alta resolución y en tiempo real de una gran cantidad de variables ambientales, físicas o químicas.

Las características más intrínsecas de las redes de sensores, como son las limitadas prestaciones y la escasez de recursos energéticos de los nodos que las integran, así como la necesidad de cooperación entre ellos, plantean nuevos retos a la investigación que conduce al desarrollo de mecanismos y protocolos que contrastan claramente con los utilizados en las redes convencionales.

En la actualidad, esta tecnología ha alcanzado un alto grado de maduración en lo que se refiere a aplicaciones terrestres y transmisión de datos alfanuméricos, pero es objeto de mucha actividad investigadora cuando se trata de abordar nuevos modelos de interacción con presencia de elementos actuadores y robots, nuevos escenarios de despliegue, como es el caso de las redes subterráneas o submarinas, o la trans- ferencia de información en formatos más completos, como ocurre con las redes de sensores multimedia gracias al desarrollo de cámaras Complementary metal-oxide- semiconductor (CMOS) y nuevos micro-sensores de audio.

Podemos observar la relevancia de las redes de sensores de una manera más clara es en Internet of Things (IoT). IoT se puede definir como la red de objetos físicos con la tecnología necesaria integrada para llevar a cabo la comunicación e interacción con sus estados internos, el entorno u otros componentes de esta red. (8)

1. INTRODUCCIÓN

1.2 Formulación del problema

Las redes de sensores constituyen uno de los nuevos paradigmas con más expectativas en el ámbito de las TIC. Tal y como hemos comentado en el punto anterior, el coste bajo y la capacidad de procesamiento limitada, hacen esencial la cooperación entre los nodos, otorgando así de robustez a la red.

Habitualmente cada nodo funciona con una batería, y como el reemplazo de cada batería es generalmente una operación engorrosa, sobre todo cuando hay muchos nodos, o incluso inviable, cuando el campo sensorial es de difícil acceso, el tiempo de vida de los nodos está limitado por su batería. Además, el tiempo de vida limitado de los nodos limita, a su vez, el tiempo de vida de la red de sensores de la que forman parte, cualquiera que sea la definición específica de ese tiempo de vida de la red.

El problema fundamental es el tiempo de vida de las redes de sensores, aunque también podemos encontrar otros problemas como, por ejemplo, el alcance limitado de los nodos no sólo obliga a que las comunicaciones se basen en múltiples saltos (mul- tihop), sino que también se tengan que añadir nodos repetidores cuando la longitud de estos saltos es excesiva.

1.3 Objetivo general del proyecto

Podemos definir como objetivo general del proyecto, el desarrollo y la implementación de un algoritmo que permita determinar la topología de una red de sensores, de tal manera que obtengamos un árbol de encaminamiento el cual ofrezca un balance óptimo entre el tiempo de vida y el número de nodos repetidores a insertar. Dicho problema es NP−Completo, por ese motivo el algoritmo está basado en la extensión multi−objetivo de una técnica heurística llamadaSimulated Annealing, que permite alcanzar una solución aceptable en un tiempo polinómico.

1.4 Objetivos concretos

A partir del objetivo general podemos extraer los siguientes objetivos, los cuales son más concretos:

• Familiarización con las redes de sensores.

• Aprendizaje de la técnicaSimulated Annealing.

• Aprendizaje de los fundamentos de la optimización multi−objetivo.

• Familiarización con la herramientaMathematica, ya que el código será desarro- llado con ésta.

• Desarrollo, depuración y ejecución del código diseñado en base a un conjunto de pruebas.

• Aplicación en un caso de uso.

2

1.5. Estructura de la memoria

1.5 Estructura de la memoria

El presente proyecto consta de un total de seis capítulos. El primero, Capítulo 1, corres- ponde a la introducción, donde hay una descripción breve de las redes de sensores y su relación con las TIC y el IoT.

A continuación, en el Capítulo 2, se estudian las redes de sensores. Se abarca desde el diseño topológico, la comunicación lógica entre nodos, elhardwarehasta elsoftware que se utilizan, incluyendo ejemplos de aplicaciones reales. Finalmente, se explica el ámbito de la seguridad en las redes de sensores.

En el Capítulo 3, se introducen las técnicas de optimización. Se hace hincapié en la técnica heurísticaSimulated Annealingy su extensión al multi-objetivo, ya que no solamente se tiene en cuenta el tiempo de vida de la red, sino que también el número de nodos repetidores a insertar.

Una vez introducida la técnica deSimulated Annealing, el Capítulo 4 está dedicado a su aplicación al diseño topológico de las redes de sensores. Se considera la versión multi- objetivo de dicha técnica, con una descripción de los objetivos y la tecnología utilizada.

Además, en este capítulo se describen el pseudocódigo y los resultados obtenidos.

En el capítulo 5, se expone la aplicación real, el diseño de una red de prevención de incendios forestales. Describimos el escenario del caso de uso y aplicamos lo explicado en el capítulo anterior. Además, analizamos los efectos en el diseño de utilizar diversas las plataformashardware.

Finalmente, se incluye un último capítulo donde se resumen las conclusiones del proyecto en base a los objetivos fijados.

C

2

R EDES DE SENSORES

Las redes de sensores han proliferado gracias a los avances tecnológicos en el diseño de sensores, en las comunicaciones sin hilos y en la integración de circuitos (tecnologías Very-larg-scale integration (VLSI)) de las tecnologías de la información. Estas redes enlazan el mundo físico con el mundo virtual y permiten el desarrollo de infinidad de aplicaciones: monitorización de entornos, cuidado médico avanzado, agricultura de precisión y el mundo de IoT entre otras. Además, abren nuevos campos de investi- gación donde convergen la electrónica y la ingeniería informática. El progreso de los componentes electrónicos que forman las redes de sensores ha permitido el desarrollo de sensores de un coste más reducido y a su vez de bajo consumo. También, gracias a los avances, se ha miniaturizado considerablemente su tamaño y se han logrado dis- positivos multifuncionales con capacidad de comunicación a distancias cortas. Estos aparatos o nodos están constituidos generalmente por un circuito de sensores, una unidad de procesamiento y un módulo de comunicación. Una red de sensores inalám- brica es un despliegue de nodos y la interconexión de éstos. Dicha red representa una mejora significativa sobre las redes de sensores tradicionales. En este capítulo descri- biremos los componentes de una red de sensores, su funcionamiento y los diferentes factores y protocolos para su diseño. Comentaremos algunas aplicaciones implantadas o en vías de instalación, así como varios modelos dehardwareysoftwarede los nodos.

Finalmente concluiremos con el tema de seguridad en dichas redes, explicando las amenazas y de qué modo podemos defendernos ante éstas.

2.1 Descripción

Una red de sensores está formada por nodos desplegados sobre un entorno determina- do. El número puede oscilar desde pocos hasta centenares, dependiendo del objetivo de su implementación, de las condiciones ambientales e incluso del presupuesto. La implementación de una red con un gran número de nodos conlleva que estos sean más económicos frente a una de un despliegue menor, debido a que al comprar una mayor

2. REDES DE SENSORES

cantidad el precio por unidad se reduce. Además, se ha de considerar que las capacida- des de computación, de la memoria y la potencia de estos nodos están limitadas.

Un nodo contiene una estructura básica (Figura 2.1) en la que podemos diferen- ciar cuatro elementos esenciales: una tarjeta de sensores, que son los encargados de monitorizar el ambiente, una unidad de procesamiento de datos, un módulo de comunicaciones y una batería que proporciona energía para su funcionamiento.

Figura 2.1: Componentes de un nodo.

1

Se realizan estudios para minimizar el consumo energético y, por ende, aumentar el tiempo de vida de la red o su duración. Opcionalmente algunos nodos incorporan entre sus elementos un generador alternativo de energía, como puede ser una placa solar o un aerogenerador, aunque su incorporación no es muy frecuente debido al encarecimiento del sistema. Tal y como hemos comentado anteriormente, el nodo está formado por elementos, cada uno de los cuales tiene su función, que detallamos a continuación:

El sensor es el encargado de captar la medida ambiental, y la convierte a un valor discreto mediante un conversor analógico−digital. Actualmente existen sensores para monitorizar todo tipo de fenómenos, como por ejemplo: la luz, la temperatura, la humedad, la presión, el movimiento,etc. Su tamaño puede variar, puede ser igual de grande que un libro o por lo contrario como una moneda.

Las muestras captadas llegan a la unidad de procesamiento de datos, la CPU de bajo consumo. Con el objetivo de minimizar costes, este procesador empotrado suele estar limitado en términos de potencia computacional y suele emplear un sistema operativo específico. Muchos de los procesadores ya incorporan métodos de ahorro energético, que suspenden la ejecución e inhiben los componentes.

La memoria de acceso aleatorio guarda las instrucciones ejecutadas por el proce- sador y la memoria de lectura−escritura almacena el sistema operativo y datos tem- porales. Finalmente, el procesador transfiere los datos al módulo de comunicaciones que transmite la información. El coste de los nodos, su despliegue y los objetivos de la red determinan los protocolos (Zigbee,Bluetooth, 802.11, GPRS, etc) y la electrónica de comunicación, que determinan el consumo energético final. Por otro lado, algunos módulos permiten graduar el voltaje utilizado de forma proporcional a la distancia a transmitir, con el fin de ahorrar energía.

Adicionalmente, algunos nodos van equipados con un módulo de posicionamiento GPS conectado directamente al procesador de datos. En ocasiones sólo son una parte de los nodos de una red los que poseen GPS y la ubicación del resto de nodos se obtiene mediante algoritmos de localización. Aunque la forma más sencilla de obtener la posición de cada uno de los nodos es preestablecerla inicialmente, pero con esta 6

2.1. Descripción

medida lo que conseguimos es limitar muchos ámbitos. Por ejemplo, las aplicaciones de rastreo, éstas precisan de GPS, así pues, el coste de cada nodo aumenta y el tiempo de vida disminuye debido al consumo energético.

La posición de los nodos puede ser predeterminada o aleatoria. Una disposición predefinida genera una topología conocida, pero a su vez acarrea un estudio previo mayor sobre la ubicación. Por otro lado, una dispersión al azar, implica un descubri- miento topológico de la red. Cabe recordar que los nodos también pueden ser móviles, como los que se utilizan en un despliegue sobre la superficie marina o en animales para rastrear su posición. La estación base es el dispositivo que recibe y procesa los paquetes que contienen las muestras enviadas por los nodos. Suele ser un dispositivo diferente a los sensores, ya que posee más capacidad de procesamiento y una batería con mayor energía o conectada a la red eléctrica. Un encaminamiento óptimo de datos desde los nodos hasta la base reduce el consumo general de la red. La topología más sencilla conecta los nodos directamente con la estación base y conforma una estrella de un único salto (single-hop star). Las redes desplegadas en un área más extensa utilizan una topología multi−salto en árbol (Figura 2.2). Esta topología se caracteriza por que los nodos transmiten sus datos a la estación base a través de otros nodos que reenvían los paquetes. En algunos casos, los nodos no actúan sólo como repetidores, sino que además examinan el contenido para la compresión de datos o mejorar la calidad de la información.

Figura 2.2: Esquema de despliegue de nodos de un entorno.

2.1.1 Modelo energético

La red de sensores tiene como prioridad minimizar el consumo de cada nodo. Éste depende de varios factores como la distancia entre nodos y el número de paquetes a reenviar de sus vecinos. Por tanto, seag(i) el número de paquetes generados por ciclo yEG(i) la energía que gasta para transmitirlos. Además, tal y como hemos explicado en el punto anterior, el nodo consume una energíaEF(i)) para recibir y reenviar los paquetes de sus vecinosσ(i). Podemos definir el gasto energético como:

E(i)=g(i)·E_G(i)+σ(i)·E_F(i) ,∀i=1,· · ·,N (2.1) dondeNes el número total de nodos de la red.

Cuando un nodo recibe un paquete consume una energíaER, la cual coincide con el resto de nodos debido a que asumimos que todos ellos tienen las mismas especi-

2. REDES DE SENSORES

ficaciones técnicas. Por lo tanto, consumen la misma energía para recibir cualquier paquete independientemente de la distancia. Por otro lado, cuando un nodo transmi- te o reenvía un paquete consume una energíaET(i), que sí depende de la distancia d(i). Así pues, estas premisas nos permiten reescribir las energíasE_G(i) yE_F(i) de la siguiente manera:

E_G(i)=E_T(i) ,∀i (2.2)

EF(i)=ER+ET(i) ,∀i (2.3) La energía disipada en transmisión depende de la distancia a transmitir y varía de nodo a nodo. El modelo de radio propuesto en (1) determina la energía de recepción y la de transmisión como:

ER=Eel ec·m (2.4)

ET(i)=Eel ec·m+Ew·m·d^f(i) ,∀i (2.5) En estas fórmulas (2.4) y (2.5) se defineEel eccomo la energía disipada por el módulo de comunicaciones para transmitir o recibir un bit ymcomo el tamaño de los paquetes en bits.Ew·d^f(i) es la energía radiada al medio inalámbrico para transmitir un bit a distanciad(i) y f es el exponente de pérdida de potencia. Esta última componente depende de la distancia de referenciad0:

d≤d0⇒Ew=Ef s, f =2 (2.6)

d>d₀⇒E_w=E_mp, f >2 (2.7) Las distancias menores a la de referencia utilizan el modelo de propagación en espacio libre. Por el contrario, las distancias superiores utilizan modelos de efectos de propaga- ción multicamino, cuyo exponente habitual es 4. Finalmente, la combinación de las fórmulas (2.1), (2.2), (2.3), (2.4) y (2.5) da lugar a la expresión del consumo total de un nodoipara cada ronda de comunicación:

E(i)=¡

g(i)+2σ(i)¢

·E_{el ec}·m+¡

g(i)+σ(i)¢

·E_w·m·d^f(i) ,∀i (2.8) Esta formulación no incluye técnicas de ahorro energético, ya que no son genéricas y dependen de cada aplicación. A pesar de ello podemos observar que la fórmula (2.8) refleja los tres factores de consumo energético de un nodo: carga de trabajo, tamaño del paquete y distancia de transmisión.

2.1.2 Arquitectura de red

Es un modelo de referencia para los protocolos de la red de arquitectura en capas.

Este modelo estándar describe el encaminamiento de los datos, su integridad con los protocolos de red y una comunicación eficiente en el medio inalámbrico. La pila OSI consiste en 7 capas o niveles: física, de enlace de datos, de red, de transporte, de sesión, de presentación y de aplicación. Este último nivel está formado por las subcapas de sesión, presentación y aplicación.

8

2.1. Descripción

Figura 2.3: Modelo de red OSI.

El nivel físico proporciona una interfaz para la transmisión de bits a través del medio inalámbrico. Éste interactúa con la capa de enlace de datos para detectar y corregir errores, y, además, se responsabiliza de la detección de la señal, su modulación y la generación de la frecuencia portadora. En referencia al consumo, el ahorro energético de los nodos comienza por la capa física.

Cabe comentar que la circuitería y la transmisión de bits consumen gran parte de la batería. El mantenimiento energético de los circuitos permanece constante, pero la energía de transmisión puede graduarse según la pérdida del canal, la distancia de transmisión y las interferencias.

Así pues, el diseño de la capa física debe considerar los requerimientos de la red de sensores. El módulo de comunicaciones debe ser pequeño puesto que va encapsulado en el nodo y, también, ha de ser económico si se trata de un despliegue masivo. Además, la radio debe de ser de bajo consumo y su elección depende de la potencia, el ratio de datos la distancia de transmisión y la confiabilidad.

La capa de enlace es la encargada de detectar y multiplexar los datos, además con- trola los errores y gestiona el acceso al medio inalámbrico. El protocolo MAC (Medium Access Control) sincroniza las tramas y determina la utilización del canal. Este protocolo establece el enlace para la transferencia de datos y forma la estructura básica para una comunicación salto a salto.

El diseño del protocolo MAC está sujeto al consumo energético, la topología y los cambios en la red. Por ello el diseño debe minimizar el malgasto de energía por colisio- nes de paquetes, exceso de retransmisiones o escuchas innecesarias del canal. Un claro ejemplo de ahorro energético es el apagado del módulo de comunicaciones cuando no se precise. No obstante, la operación encendido-apagado para la transmisión puede consumir más energía que si se hubiera dejado encendido el tiempo por el cual ha estado el módulo inactivo. Por este motivo, el diseño recomienda diferentes modos de voltaje según los estados del procesador y la memoria, y propone transiciones interme- dias de ahorro. Estos niveles dependen de los tiempos de transmisión y del consumo individual de los modos de cada nodo.

Aparte del acceso al medio, la capa de enlace, tal y como hemos comentado, con- trola los errores en la transmisión. Los sistemas más habituales están basados en el FEC (Forward Error Connection), ARQ(Automatic Repeat Request) o en híbridos de los

2. REDES DE SENSORES

mismos. La técnica ARQ habilita un temporizador y una espera de respuesta para que el destinatario confirme o rechace la llegada correcta de la trama. La expiración del temporizador o la respuesta negativa obliga al emisor a retransmitir sus datos, aunque sólo haya fallado un bit. Por otro lado, el FEC reduce el número de transmisiones ya que cada nodo incluye datos redundantes para que el destinatario pueda detectar y corregir errores. La elección de los sistemas de control de errores depende del objetivo de la red y del coste energético de cada nodo.

La capa de red dictamina el encaminamiento de datos a través de la red desde un nodo hasta la estación base. Los protocolos basados en el enrutamiento tradicional apenas se utilizan debido a que los nodos no suelen disponer de dirección IP. El diseño de protocolos de red debe respetar la escalabilidad, dirigir los datos hasta la estación base y atender a los requisitos de eficiencia, tolerancia a fallos y seguridad.

La capa de transporte garantiza la confiabilidad y la calidad de los datos tanto en los nodos como en la estación base. Los protocolos de transporte deben soportar múltiples aplicaciones, recuperación de paquetes perdidos y mecanismos de control de congestión. Esta capa adquiere mayor necesidad cuando la red está planeada para el acceso a internet. El diseño debe ser independiente de la capa de aplicación, es decir, cada aplicación debe tolerar distintos umbrales de pérdida de paquetes, porque cada dato perdido causa un malgasto energético. El protocolo de transporte detecta y recupera paquetes perdidos para mejorar el rendimiento y el consumo energético. Con redes de sensores el uso de protocolos de transporte se reduce.

La capa de sesión es la que proporciona los mecanismos para controlar el diálogo entre las aplicaciones de los sistemas finales. Además, puede proporcionar un procedi- miento de puntos de comprobación, de forma que si ocurre algún tipo de fallo entre puntos de comprobación, la entidad de sesión puede retransmitir todos los datos desde el último punto de comprobación y no desde el principio.

La capa de presentación tiene como objetivo encargarse de la representación de la información de manera que, aunque distintos equipos puedan tener diferentes representaciones internas de caracteres, los datos lleguen de manera reconocible. Esta capa es la primera en trabajar más el contenido de la comunicación que el cómo se establece la misma. En ella se tratan aspectos tales como la semántica y la sintaxis de los datos transmitidos, ya que distintas computadoras pueden tener diferentes formas de manejarlas. También permite cifrar los datos y comprimirlos. Por tanto, podría decirse que esta capa actúa como un traductor.

Finalmente, la capa de aplicación ofrece a las aplicaciones la posibilidad de acceder a los servicios de las demás capas y define los protocolos que utilizan las aplicaciones para intercambiar datos. Hay tantos protocolos como aplicaciones distintas y, puesto que continuamente se desarrollan nuevas aplicaciones, el número de protocolos crece.

Cabe aclarar que el usuario normalmente no interactúa directamente con el nivel de aplicación, únicamente con programas que a su vez interactúan con el nivel de aplicación, pero ocultando la complejidad subyacente.

En la siguiente tabla se muestran algunos ejemplos de protocolos por capas del modelo OSI.

10

2.1. Descripción

Cuadro 2.1: Ejemplos de protocolos por capas del modelo OSI.

CAPA PROTOCOLO

1. Física −

2. Enlace de datos ETHERNET, TOKEN RING, PPP, HDLC, Frame Relay, RDSI, ATM, IEEE 802.11 3. Red IP, UCMP, IGMP, X.25, ARP,

RARP, OSPF, RIP, IGRP, ELGRP, IPX 4. Transporte TCP, TDP, RTP, SCTP, SPX

5. Sesión TLS, SSH, RPC, NetBIOS, TELNET, SCP, ASP 6. Presentación XDR, ASN.1, SMB, AFP

7. Aplicación HTTP, DNS, SMPT, SNMP, FTP, POP3

Las redes de sensores implementan un modelo distinto de la capa OSI, el cual podríamos definir siguiendo la estructura de la Figura 2.4

Figura 2.4: Arquitectura de los diferentes planos de la pila.

Podemos apreciar que a parte de las capas anteriormente descritas, adquirimos otra dimensión y pasamos a tener una pila con planos nuevos.

Estos planos ayudan a que los nodos sensores coordinen la tarea de detección y reduzcan el consumo total de energía.

• El plano de datos gestiona el flujo de datos normal desde los nodos del sensor has- ta el nodo recolector, también denominado sink node, el cual, como su nombre indica se encarga de recolectar la información del los nodos.

• El plano de administración de energía controla cómo un nodo sensor utiliza su energía y la coordinación de nodos con el fin de compartir recursos y reducir el consumo total de energía.Por ejemplo, el nodo sensor puede apagar su receptor después de recibir un mensaje de uno de sus vecinos. Esto es para evitar recibir mensajes duplicados. Además, cuando el nivel del nodo del sensor es bajo, el nodo del sensor transmite a sus vecinos que tiene poca energía y así la energía restante está reservada para la detección.

2. REDES DE SENSORES

• El plano de gestión de la movilidad detecta y registra el movimiento de los nodos de los sensores, por lo que una ruta de regreso al usuario se mantiene siempre, y los nodos del sensor pueden realizar un seguimiento de quiénes son sus nodos de sensores vecinos. Al saber quiénes son los nodos de sensores vecinos, los nodos sensores pueden equilibrar su uso de energía y tareas.

• El plano de gestión de tareas equilibra y programa las tareas de detección asigna- das a una región específica.

• El plano de localización: intercambio de datos entre nodos con fines de localiza- ción.

• El plano de sincronización: intercambio de datos entre nodos con fines de sin- cronización.

12

2.1. Descripción 2.1.3 Taxonomía de las redes de sensores

Las redes de sensores pueden clasificarse siguiendo diferentes pautas, como por ejem- plo el entorno del despliegue o su posicionamiento. El entorno distingue entre redes inalámbricas, acuáticas, subterráneas o terrestres, donde varían elhardwarede los nodos y su encapsulación. A su vez la red puede ser estática o dinámica, según los cambios posicionales de los sensores. También pueden clasificarse según el modelo de flujo de datos, que engloba las redes de sensores activadas por usuario, por eventos y por tiempo.

Las redes activadas por usuario (query−driven) ejecutan las mediciones o la descar- ga de los datos cuando se solicitan. Un ejemplo sería el proyectoCitySense(2), donde la captura de medidas ambientales depende directamente de las peticiones entrantes.

Figura 2.5: Esquema de red activada por usuario.

Las redes activadas por eventos (event−driven) esperan a que ocurra un aconteci- miento para captarlo y notificarlo. Por ejemplo, una red inalámbrica compuesta por detectores de humo sólo se activa cuando registra ciertos niveles de éste. Otro ejemplo sería una red de sensores de movimiento, la cual espera la aceleración de algún objeto para activarse. Generalmente estos nodos permanecen en un estado de hibernación hasta que ocurre el evento en sí, que es cuando lo captan.

Figura 2.6: Esquema de red activada por eventos.

Por último, las redes activadas por tiempo (time−driven) monitorizan un área de estudio a intervalos constantes o aleatorios. Podemos destacar como ejemplo de este tipo de redes las aplicaciones de monitorización de entornos, comoSentilo(3), donde están monitorizadas desde plazas de parking hasta niveles contaminación, temperatura, etc.

2. REDES DE SENSORES

Figura 2.7: Esquema de red activada por tiempo.

En este tipo de aplicaciones el sensor capta, almacena y transmite la muestra pe- riódicamente, ya sea cada pocos segundos o con un intervalo más largo de minutos o incluso horas. El conocimiento del instante y del orden de transmisión facilita determi- nados aspectos en el diseño de una red de sensores.

Figura 2.8: Ejemplo de despliegue de sensores, cuya información trata luego la aplica- ción Sentilo.

2.2 Diseño de una red de sensores

La aplicación final de la red inalámbrica de sensores especifica los atributos prioritarios para un diseño adecuado. Estos atributos son comunes en la gran mayoría de los proyectos considerando las limitaciones tanto energéticas como computacionales. Aun así, en cada aplicación se debe hacer un estudio para adaptarlos según los objetivos definidos.

Los atributos más destacables en el diseño de una red de sensores son:

• Consumo energético:el diseño debe minimizar el consumo de cada nodo con tal de alargar el tiempo de vida general de la red, ya que la vida de una red se define por el nodo de vida más corta. La búsqueda de una topología eficiente, la transmisión del mínimo número de datos necesarios y la frecuencia de envío son aspectos fundamentales para el ahorro de energía de los nodos.

14

2.3. Aplicaciones

• Coste:por un lado, el coste computacional ya que, tal y como hemos comentado anteriormente, los nodos poseen procesadores y memoria limitados, lo cual hace que las operaciones posibles se vean reducidas y que las instrucciones costosas no se puedan llevar a cabo. Por otro lado, está el coste relacionado con el coste económico; por lo tanto, el diseño debe estudiar el coste individual del nodo, el presupuesto del despliegue total de la red y el mantenimiento de la misma.

• Escalabilidad:la aplicación puede incorporar a posteriori nuevos nodos, y la red ha de proveer mecanismos de actualización topológica. Al igual que si el número de nodos se reduce, se han de proporcionar también estos mecanismos.

Estas actualizaciones probablemente plantearán nuevos cálculos del consumo energético y del tiempo de vida de la red, así como el coste del proyecto al ser renovado.

• Tolerancia a fallos:el despliegue debe establecer un diseño que contemple la tolerancia a fallos sin que suponga la caída total del sistema. Cuando se trata de un despliegue masivo, la probabilidad de nodos inactivos es mayor que la de un despliegue con un menor número de nodos. Los sensores pueden inhabilitarse o funcionar con un peor rendimiento por inclemencias meteorológicas, finaliza- ción de la batería, golpes, errores de alguno de sus componenteshardware, etc.

En consecuencia, los nodos de redes reducidas deben ir equipados con una pro- tección extra. Aunque hemos comentado que la probabilidad de nodos inactivos era menor que la de una red con un gran despliegue, en este caso, un fallo podría suponer la caída de la red.

• Procesamiento cooperativo:para lograr el objetivo de la red de una manera efi- ciente, los nodos trabajan colectivamente. El proceso cooperativo entre nodos es un factor indispensable para despliegues dinámicos puesto que aportan métodos de localización aproximada sin recurrir al posicionamiento GPS.

• Autoconfiguración de la red:los factores de tolerancia a fallos y escalabilidad hacen que la red tenga que ser autoconfigurable, ya que, por ejemplo, la in- corporación de nuevos nodos hace que se tengan que crear nuevas rutas de encaminamiento de datos y, por ende, una gestión autónoma en la creación de la topología.

• Agregación de datos:algunas redes dividen su trabajo en subredes oclusters para descongestionar la red. En esta distribución los nodos transmiten sus datos alclusterhead que los agrega y los envía bien a otrocluster heado a la estación base. Esta configuración restringe las transmisiones de los nodos exclusivamente a sus superiores y reduce las posibilidades de congestión en la red.

2.3 Aplicaciones

Las aplicaciones de una red inalámbrica de sensores suelen categorizarse en dos gran- des grupos: la monitorización y el rastreo (Figura 2.9). El primer grupo incluye las aplicaciones de monitorización industrial, inventariado, control de procesos automáti- cos, etc. Por el otro lado, las aplicaciones que pertenecen al grupo de rastreo abarcan el seguimiento de objetos, animales o incluso personas, entre otras aplicaciones.

2. REDES DE SENSORES

Figura 2.9: Aplicaciones de redes de sensores.

En este apartado expondremos ejemplos reales de cada uno de los grupos de aplicaciones. Gericasa (3) pertenece al grupo de aplicaciones de monitorización, es un proyecto que tiene como objetivo poner en marcha una “solución integral” que mejore la atención a personas dependientes en los entornos hospitalarios; la empresa tecnológica Inycom, en colaboración con el Hospital San Juan de Dios de Zaragoza y la Universidad San Jorge, han desarrollado un nuevo sistema que facilita la atención hospitalaria a pacientes geriátricos.

Se han incorporado distintos mecanismos para la monitorización de la sala y el paciente: sensores de bajo coste para la medición de condiciones de temperatura, luz, humedad, aire y ruido en la sala que puedan afectar al estado de salud del enfermo, una pulsera inteligente que deberá llevar puesta el paciente para la monitorización de las constantes vitales, el seguimiento de su actividad física a lo largo del día (con un contador de pasos, distancia, calorías y monitorización del sueño del paciente), así como un inclinómetro para medir la inclinación del respaldo de la cama.

Por otro lado, un ejemplo de aplicación de rastreo esCenwits(4), el cual es un sistema de búsqueda y rescate de personas en espacios naturales basado en sensores y testigos. Este sistema identifica el lugar y la hora donde la persona fue vista por última vez, el cual es un dato crítico para su rastreo; cada usuario está equipado con un sensor GPS y otro de radiofrecuencia, que es el encargado de trasmitir sus datos a los puntos de acceso (los testigos) instalados en puntos clave. La localización GPS y el rastro en los testigos marca la ruta de la persona. El proyecto fue diseñado y evaluado con sensores Berkeley Mica2, reduce el área de búsqueda y facilita el rescate de excursionistas perdidos o esquiadores lesionados.

Otra aplicación relacionada con la salud esFireLine, un sistema inalámbrico que monitoriza y registra el latido del corazón en los bomberos. Cada trabajador posee uno de estos sensores, el cual tiene tres electrodos que captan el pulso. El nodo transmite 16

2.4. Hardware

Figura 2.10: EjemploCenWits.

los datos directamente a la estación base que está situada en el vehículo de extinción y en caso de detectar alguna actividad anormal, la aplicación alerta al bombero y al resto del equipo.

Finalmente, la aplicaciónZebraNet(5) rastreó migraciones de animales en la saba- na de Kenia durante semanas. Dotaron a una decena de cebras de collares con sensores GPS que enviaban su posicionamiento. Después de la adaptación del collar a los ani- males, los sensores recolectaron datos de estudio y, gracias al análisis de los datos, los biólogos entendieron mejor los movimientos de las cebras.

2.4 Hardware

Los componentes físicos de un nodo están caracterizados por la búsqueda de un con- sumo mínimo de energía y un tamaño reducido. Los fabricantes dehardwaremejoran las prestaciones, abaratan los costes y disminuyen las dimensiones año tras año. Estos avances, juntamente con el progreso de suministros alternativos de energía, miniaturi- zan los sensores y alargan la vida de cada dispositivo. Siguiendo con la tendencia actual, en un futuro los sensores procesarán información a mayor velocidad, con un menor consumo y transmitiendo datos a distancias mayores.

En este apartado mostraremos las características de algunos sensores reales.

El sensorMica2(Figura 2.11) (6) posee dos bateríasAAy un módulo de comuni- caciones multicanal de 433, 868/916 o 310 MHz. Este nodo puede acoplar diferentes sensores que monitorizan presión barométrica, luz, sonido, aceleración, posiciona- miento, etc. Sus características técnicas las podemos observar en la tabla 2.2 que se muestra a continuación.

Figura 2.11: SensorMica2.

2. REDES DE SENSORES

Cuadro 2.2: Descripción técnica del sensor Mica2

Processor/Radio Board MRP400CB Remarks

Processor Performance

Program Flash Memory 128K bytes

Measurement (Serial) Flash 512K bytes >100, 000 Measurements Configuration EEPROM 4K bytes

Serial Communications UART 0−3V trabsmission levels Analog to Digital Converter 10 bit ADC 8 channel,0−3V input

Current Draw 8mA Active model

<15µA Sleep mode

Multi-Channel Radio

Center Frequency 868/916MHz ISM bands

Number of Channels 4/50 Programmable, country specific

Data Rate 38.4 Kbaud Manchester encoded

RF Power −20 to+5 dBm Programmable, typical Receive Sensitivity −98 dBm Typical, analog RSSI at AD Ch. 0

Outdoor Draw 27 mA Transmit with maximum power

10 mA Receive

<1µA Sleep

Electromechanical

Battery 2X AA batteries Attached pack

External Power 2.7-3.3 V Connector provided

User Interface 3 LEDs User programmable

Size (in) 2.25 x1.25 x 0.25 Excluding battery pack

(mm) 58 x 32 x 7 Excluding battery pack

Weight (oz) 0.7 Excluding batteries

(grams) 18 Excluding batteries

Expansion Connector 51-pin All major I/O signals

El sensorTinyNode 584(7) fabricado porShockfishes un nodo compacto basado en un microcontrolador MSP430 con un transmisor receptor de radioXemics XE1250. Este nodo suele integrar un sensor que monitoriza la temperatura, pero también pueden agregarse más elementos. En la tabla 2.3 podemos observar algunas de sus característi- cas técnicas.

18

2.4. Hardware

Cuadro 2.3: Descripción técnica del sensor TinyNode 584

TinyNode 584

Battery Supply 1 lithium, 2 alkaline batteries or 3 rechargable cells Minimum Vin 2.4 V (min. 2.7V during flash programming)

Battery Capacity n.a.

Regulated Supply only for Vin>2.7V

Current Draw Power Consumption

uC sleep with timer on 6.5uA 0.0195 mW

uC active, radio off 2.1 mA 6.3 mW

uC active, radio idle listening 16 mA 48 mW

uC active, radio TX/RX at +12dBm 62 mA 186 mW

Max.Power (uc Active, radio TX/RX at +12dBm + flash white) 76.9 mA 230.7 mW

Otros ejemplos de sensores son el de la Figura 2.12 que es elParticles, el cual monitoriza luz, temperatura, aceleración y el de la Figura 2.13, el cual podemos apreciar que tiene un tamaño reducido y sirve para registrar signos vitales.

Figura 2.12: SensorParticles. Figura 2.13: SensorSHIMMER-2.

2. REDES DE SENSORES

2.5 Software

Los sensores tienen integrado el software, el cual gestiona las tareas y administra el consumo de los componentes. Para este tipo de redes, las condiciones del sistema operativo han de tener en cuenta las limitaciones computacionales de los nodos y han de proporcionar herramientas que manejen el módulo de comunicaciones, el sensor, la memoria y la batería. Los avances en elhardwaremejoran la calidad del software, como por ejemplo la agregación de una librería para una mayor velocidad de cálculo o mecanismos de codificación de datos más robustos.

El principal sistema operativo implantado en redes inalámbricas de sensores es TinyOs. Este sistema operativo diseñado para sistemas empotrados es de código abier- to y está escrito en una variante deC, que esnesC, el cual está optimizado para las limitaciones de memoria. El origen deTinyOsse remonta a 1999 cuando la Universidad de Berkeley (California) necesitaba un sistema operativo de bajo consumo para sus recientes nodos. Desde entonces, las compañías Intel y Crossbow Technology han apoyado el proyecto y han adaptado el sistema a sus exigencias sobre redes de sensores.

Aparte del núcleo central,TinyOsañade herramientas suplementarias como el com- pilador denesCy algunas librerías enC. Este sistema operativo provee interfaces para abstracciones comunes: comunicación de paquetes, monitorización de los sensores, encaminamiento de datos y almacenamiento de información.

Además, este sistema operativo utiliza tareas e interrupciones ejecutadas en orden First in First Out (FIFO). Por otra parte, algunos estudios desarrollados con procesadores más potentes proponen la incorporación de hilos al sistema operativo para ejecutar paralelamente varias tareas en los nodos.

2.6 Seguridad

Como se ha comentado en apartados anteriores, las redes de sensores están compuestas por un conjunto de dispositivos electrónicos, pequeños y de bajo coste.

Por este motivo, si se desea añadir algún tipo de mecanismo de seguridad a la red ante los posibles ataques, no puede basarse en las técnicas clásicas (pensadas para máquinas más potentes) y requiere la aplicación de soluciones alternativas.

2.6.1 Ataques

Las redes de sensores son un caso particular de redeswireless, por ello, sufren sus mismas debilidades. Asimismo, la naturaleza peculiar de los sensores y su elevado número añaden otro tipo de problemas.

Una red de sensores está compuesta típicamente por una gran cantidad de nodos desplegados en un entorno no controlado e incluso hostil. Los sensores suelen ser dispositivos simples, de poca potencia, cosa que provoca que no sea posible aplicar las técnicas de seguridad que se utilizan en otro tipo de entornos. Asimismo, su simplicidad los hace más vulnerables a ataques.

Una lista de los posibles ataques que puede recibir una red de sensores es la pre- sentada a continuación. Además, cabe decir que algunos de los ataques pueden ser producidos de forma no intencionada.

20

2.6. Seguridad

• Compromiso de un nodo: Se asume que, debido a la simplicidad de los sensores, así como al entorno incontrolado dónde se encuentran, un atacante puede ganar el control de un nodo y obtener todos sus datos (claves criptográficas incluidas).

Además de la obtención de los datos privados del nodo, el atacante podría intro- ducir datos falsos en la red o realizar una denegación de servicio a base de no retransmitir los paquetes que le lleguen de otros nodos.

• Destrucción de un nodo: Debido a la falta de control del entorno donde la red está desplegada, un sensor puede ser destruido (o simplemente transportado fuera del alcance de la red) ya sea de forma voluntaria o involuntaria, por un atacante o por condiciones de contorno (clima, incendios, animales, etc.). Podría ser causa de una denegación de servicio si ese nodo fuera una pieza importante en el enrutado de los datos hacia la estación base o si el nodo destruido fuera la misma estación base.

• Escucha o modificación de los datos: Como pasa en cualquier redwireless, no se puede evitar que los datos que viajan entre nodos sean escuchados por cualquier receptor situado dentro del rango de transmisión del emisor. Es también posible que cualquier emisor no autorizado emita paquetes que sean recibidos por los nodos de la red.

• Acceso o alteración de la red: Consiste en introducir un nuevo nodo en la red con propósitos maliciosos como: obtener datos, falsear datos, impedir el servicio, etc.

• Denegación de servicio (DoS): Impedir que la red lleve a cabo su funcionalidad de forma correcta. Estos ataques pueden ser de distinta naturaleza e incluso no intencionados.

Por otro lado, los puntos de ataque a una red de sensores son los siguientes:

• Estación base: Elemento de mayor potencia de la red. Es el elemento encargado de hacer de puente entre la red y el exterior. Su caída imposibilita el correcto funcionamiento de la red. Puede existir más de una estación base en una red, pero siempre será un número mucho menor que la cantidad de sensores desplegados.

• Sensores: Elementos formantes de la red. Tienen poca capacidad y son muy vulnerables. Debido a la gran cantidad de ellos la caída de un sensor no debe afectar sustancialmente a la red si su topología es suficientemente densa. El mayor riesgo consiste en el compromiso de un nodo por parte de un atacante, que le permitirá atacar la red desde dentro.

• Comunicaciones: De forma similar a una redwireless, las comunicaciones entre nodos pueden ser objeto de ataques de escucha, de introducción de datos falsos o de anulación de las comunicaciones (mediante DoS).

Finalmente, un último aspecto relacionado con la seguridad consiste en la protección frente a ataques de redes de sensores. Por tanto, es necesario el desarrollo de sistemas que permitan la detección de la presencia de redes de sensores hostiles e incluso la anulación de sus funcionalidades.

2. REDES DE SENSORES

2.6.2 Defensas

Una vez introducida la tipología de ataques que puede recibir una red, se puede pasar al estudio de posibles mecanismos de defensa. La solución a los problemas presentados es abordada con distintas propuestas, todas ellas bastante independientes entre sí, aunque con autores similares. Por un lado, se ha intentado asegurar elrouting con iniciativas distintas a las propuestas para redeswirelesscomunes.

Asimismo, se intentará proteger los elementos formantes de la red, ya sea protegien- do la estación base o tratando de detectar intrusos presentes en la red. Por otro lado, hay iniciativas que se focalizan en la protección de la información o en la protección de la agregación de la información.

Finalmente, otros esfuerzos se dedican a la predistribución de claves para la comu- nicación entre las distintas partes.

A continuación, se presentan las distintas estrategias que pretenden ofrecer protec- ción a algunos de los ataques presentados en la sección anterior.

La primera trata de conseguir un enrutado seguro en una red de sensores. Con él se trata de evitar que un atacante pueda alterar el enrutado y conseguir hacer un ataque DoS, escuchas, alteraciones de mensajes, etc. La segunda intenta proteger la estación base ocultándola a los atacantes, así como el acceso de los nodos a la misma.

Se trata de evitar que el atacante comprometa la funcionalidad de la estación base. La tercera trata de detectar los intrusos en la red de sensores para posteriormente poder actuar en consecuencia (ignorándolo, marginándolos, etc). La cuarta trata de proteger la agregación de la información realizada por los nodos.

Y, finalmente, la quinta estrategia trata de proteger la información en sí.

2.6.3 Conclusiones

Las redes de sensores ofrecen una interesante funcionalidad y por ello se está traba- jando en su desarrollo y perfeccionamiento. Por la naturaleza de estas redes y del entorno donde suelen estar desplegadas, puede ser objetivo de multitud de ataques.

Así, La defensa está condicionada y fuertemente limitada por las características de los dispositivos que forman la red.

Se han desarrollado mecanismos de protección de la red, tanto para proteger sus elementos como para proteger sus comunicaciones y, en particular, para proteger el enrutado. No obstante, el incremento en las medidas de seguridad comporta un incremento en el consumo de batería, un recurso muy limitado en los sensores. Se debe poner énfasis en el uso de soluciones que no requieran un alto coste (como usar criptografía simétrica y funciones dehashpara el cifrado y autenticación en lugar de criptografía asimétrica, reducir el tamaño y la cantidad de mensajes a enviar, etc).

Asimismo, existen esfuerzos para la solución de aspectos concretos de seguridad, pero no hay ninguna propuesta que trate de proporcionar una solución completa que dé el nivel de seguridad que necesita una red.

Las soluciones actuales pueden ser suficientes para el despliegue en entornos poco hostiles. No obstante, en entornos con atacantes poderosos la protección de las redes de sensores se convierte en un tema complicado de mantener durante el tiempo completo de vida de la red.

22

C

3

Simulated annealing

3.1 Introducción a las técnicas de optimización

La Investigación Operativa (IO) (9) (10) es una ciencia moderna interdisciplinaria, que, mediante la aplicación de teoría, métodos y técnicas especiales, busca la solución óptima de problemas complejos. Luego, el objetivo más importante de la IO es dar apoyo a la toma óptima de decisiones. En cuanto a la metodología que emplea la IO, puede reducirse a los siguientes pasos:

1. Análisis de la realidad y formulación del problema: el analista debe observar el problema desde diferentes puntos de vista, consciente de las realidades sociopo- líticas y económicas, para definir de forma clara los objetivos y limitaciones.

2. Modelado matemático representativo: se deben identificar las variables de deci- sión, la función objetivo y las restricciones del problema.

3. Resolución del modelo: en esta fase se elige la técnica de resolución y se generan las soluciones.

4. Presentación de resultados: se lleva a cabo el análisis y verificación de soluciones, se analiza la representatividad del modelo y se realiza análisis de sensibilidad.

5. Implementación de resultados: se preparan los informes y presentaciones y se supervisa la aplicación.

Como la realidad es compleja, muchos de estos modelos son de dimensiones enormes y, además, son estocásticos, es decir, hay parámetros cuyos valores no pueden ser controlados por la persona que toma la decisión y son desconocidos. También son no lineales e intervienen variables enteras.

Cada una de estas características, (dimensión, estocasticidad, integralidad y no linealidad), dificultan enormemente la resolución del problema, considerándose pro- blemas de complejidad computacional elevada.

3. Simulated annealing

La optimización es una parte fundamental de la IO, por tanto, ésta incluye gran can- tidad de ramas como la Programación Lineal, Programación no Lineal, Programación Dinámica, Simulación, Teoría de Colas, Teoría de Inventarios, Teoría de Grafos, etc.

En la optimización confluyen las Matemáticas y las Ciencias de la Computación. El propósito de ésta es construir y resolver de forma efectiva modelos realistas de la situa- ción que se estudia, con objeto de permitir que los tomadores de decisiones exploren una amplia variedad de posibles alternativas. Más concretamente, la optimización se refiere al análisis y resolución de problemas en que se debe tomar una solución entre un conjunto de soluciones factibles. El objetivo es encontrar la mejor solución (no necesariamente única) y las elecciones se comparan de acuerdo a una cierta función, llamada función objetivo.

Entre los objetivos de esta ciencia interdisciplinaria, están los clásicos de maxi- mización de beneficios o rendimiento y minimización de pérdida, costes o riesgo, a los que se suman, entre otros, los objetivos de eficiencia (asignación de recursos a actividades), la optimización espacio-temporal (por ejemplo, mínima espera en una cola o mínima distancia a recorrer en un viaje) y la mejora en términos de equidad (como la minimización de diferencias entre individuos en cuanto al reparto de trabajo o la distribución de vacaciones).

Finalmente, cabe comentar que el reconocimiento de la importancia de este tipo de problemas coincidió con el desarrollo en 1947 de un método eficiente, el méto- do simplex, por George Bernard Dantzig (1914-2005), y un medio, el ordenador, para aplicarlo.

3.2 Versión estándar de simulated annealing

Son muchos los algoritmos que pueden aplicarse en busca de soluciones óptimas.

Éstos han ido evolucionando desde el uso de métodos exactos, hacia heurísticos y metaheurísticos finalmente.

Existe una clase de problemas cuyo coste computacional es NP, esto se debe a que no se conocen algoritmos exactos con tiempos de convergencia en tiempo polinómico.

Es decir, aunque existiera un algoritmo que encontrara la solución exacta al problema, tardaría tanto tiempo en encontrarla que lo hace completamente inaplicable.

Además, un algoritmo exacto es completamente dependiente del problema que resuelve, de forma que cuando se cambia el problema se tiene que diseñar un nuevo algoritmo exacto y demostrar su optimalidad de nuevo. Por este motivo, para la mayoría de problemas de interés no existe un algoritmo exacto con complejidad polinómica que encuentre la solución óptima. Además, el espacio de búsqueda de estos problemas suele ser muy grande. Debido a estos dos motivos, se necesitan utilizar algoritmos aproximados o heurísticos, los cuales permiten obtener una solución de calidad en un tiempo razonable.

El algoritmoSimulated Annealing(10), pertenece al grupo de algoritmos heurísticos.

Éste se basa en principios de la termodinámica y el proceso de recocido del acero. Dicho algoritmo considera los problemas de optimización combinatoria como problemas que buscan un óptimo global.

El algoritmoSimulated Annealingcombina el Hill-Climbing(11) con el seguimien- to de un camino aleatorio de modo que se pueda conseguir tanto eficiencia como 24

3.2. Versión estándar desimulated annealing

optimalidad.

Tal y como hemos comentado anteriormente, el modelo de funcionamiento del algoritmo procede del proceso físico del templado de metales. Para conseguir que la estructura molecular del metal tenga las propiedades deseadas de resistencia o flexibilidad, es necesario controlar la velocidad del proceso de templado (enfriamiento).

Si se hace adecuadamente, el estado final del metal es un estado de mínima energía.

A continuación, explicaremos detalles más concretos del algoritmo. Éste consta de 2 elementos clave:

1. El bucle interno: es un método que permite obtener nuevas configuraciones (estados) a partir de la actual. Obtenemos el esquema de exploración del espacio de configuraciones.

2. El bucle externo: es un esquema de descenso de temperatura, enfriamiento, que garantiza la convergencia a óptimos globales correspondientes a mínima energía.

Figura 3.1: Diagrama del funcionamiento del SA.

3. Simulated annealing

El objetivo es encontrar la mejor configuración para la temperatura fijada. Para ello se exploran caminos de longitud máxima prefijada. Para evitar elegir mínimos relativos, no elige el mejor sucesor si no que elige uno aleatorio.

La probabilidad de que una configuración sea elegida depende de su energía (fun- ción de calidad) y de la temperaturaT de la iteración:

• SiT→ ∞más o menos todas las configuraciones tienen igual probabilidad de ser elegidas, independientemente de su calidad.

• SiT→0 sólo las configuraciones de coste mínimo tienen probabilidad no nula.

El sucesor aleatorio generado se convierte en el siguiente, si supone una pérdida de energía (estamos minimizando y, por tanto, es mejor que su antecesor) pero con una cierta probabilidad también puede ser elegido aunque suponga un incremento (es peor que su antecesor); esto se debe a lo descrito anteriormente, haciendo este proceso evitamos obtener una solución óptima relativa y, así, podemos seguir buscando la solu- ción óptima global. La secuencia de configuraciones del bucle más interno reproduce un camino aleatorio para una temperaturaTdada. La condición de equilibrio se puede alcanzar fijando un número máximo de pasos.

El esquema de la temperatura,T, es una función que regula su descenso. Ha de garantizar la convergencia al mínimo global, independientemente de la configuración inicial. Normalmente el valor deT se obtiene como una función del tiempo.

Finalmente cabe comentar que se puede demostrar que, si el esquema de la tempe- raturaT disminuye lo bastante despacio, el algoritmo encuentra el óptimo global con probabilidad cercana a 1.

función SA( problema , esquema ) ret ( estados_solución ) act := ESTADO_INICIAL ( problema );

T:= teemperatura_inicial ( esquema ); tope := num_iteraciones ( esquema );t :=0;

r e p e t i r

est := act ;it :=0;

r e p e t i r

sig := sucesor_aleatorio ( est );

E:= valor ( sig )-valor ( est );

si E <0 enotnces est := sig ; sino q:= min {1,e^{E/T }};

si aleatorio (0 ,1) < q entonces est := sig ; it := it +1;

h a s t a it := tope ;

act := epst ; T:= ENFRIAR (T, esquema );t:=t +1;

h a s t a T( aprox )0 ret act

3.3 Extensión multi-objetivo

Durante los primeros capítulos de este proyecto, se ha hecho hincapié en que uno de los problemas de las redes de sensores es el tiempo de vida. Pero, también, han surgido otros problemas, relacionados con el despliegue de éstas, por ese motivo en este apartado proponemos la extensión a multi-objetivo (12).

26

3.3. Extensión multi-objetivo

Cuadro 3.1: Diseño de objetivos y criterios de optimización.

Diseño de objetivos Criterios de optimización MHS MST SPR STML

Tiempo de vida • • •

PER, PLR • •

Path delay • •

Rendimiento •

Número de nodos de transmisión •

Si analizamos algoritmos tradicionales como el MST apreciamos que la carga del tráfico soportado por cada nodo es ignorada, solo se centra exclusivamente en las distancias. El CTP es un algoritmo que no tiene como objetivo maximizar el tiempo de vida de la red, ya que se enfoca a encontrar el camino de rendimiento más alto entre los nodos. Finalmente, otro ejemplo sería el SPR, el cual homogeniza la distribución de la energía consumida.

Con estos ejemplos podemos observar que su denominador común es que solo se enfocan en un único objetivo de optimización,y los demás se satisfacen a expensas del primero; en la optimización multi-objetivo se abordan dos o más objetivos principales.

La solución más completa para el problema de optimización multi-objetivo viene dada por lo que denominaremos conjunto de Pareto. Éste estará compuesto por un conjunto de soluciones no dominantes.

La variable de los objetivos la formularemos comoo=[o1,· · ·,om]. En nuestro caso, aplicaremos solamente dos objetivos, estos serán el de maximizar el tiempo de vida de la red y el de minimizar el número de nodos intermedios que necesite el despliegue de la misma.

Finalmente, para construir el conjunto de Pareto, nos basaremos en el concepto de dominancia. De esta manera, diremos que una solución es dominante sobre otra si cada uno de los objetivos de una es mejor que en la otra solución. Si no se cumple en su totalidad, diremos que las soluciones son co-dominantes, debido a que ninguna es mejor que la otra. Estas soluciones co-dominantes serán las que formen el conjunto de Pareto.

A continuación, explicaremos el pseudocódigo del MOSA Set PS ={t}; T= T_0 ; /t is any initil spanning tree / w h i l e(T > T_{f})

for i=1, ... , LE t ’= Pertub (t)

if(t’ > t o t’ ( aprox ) t) t=t’

PS= UpdatePS (t,PS)

e l s e if(exp(- delta_0 /T))>R a n d o m(0 ,1) t=t’

end if end for T = alplha T end w h i l e

3. Simulated annealing

En el código anteriorP Srepresenta el conjunto de Pareto actual yT la temperatura, la cual utilizaremos como parámetro de control, siendoT0temperatura inicial yTf

temperatura final. El parámetro αdesigna un número real menor que 1,LE es la longitud de cada iteración y, finalmente,δ0es una función positiva que cuantifica la variación multi-objetivo.

Podemos observar que en el pseudocódigo hay dos métodos, El primero de ellos es Perturb(i,t), donde dados un nodoiy un árbolt, determina el padre de dicho nodo. Y el segundo método es el de Update(PS)que tal y como su nombre indica, actualiza el valor del conjunto de Pareto.

28

C

4

A PLICACIÓN DE Simulated Annealing ^AL

DISEÑO DE UNA RED DE SENSORES

4.1 Selección de objetivos

A la hora de aplicar el algoritmo MOSA nos hemos decantando por la maximización del tiempo de vida y la minimización de los nodos repetidores a insertar.

La maximización del tiempo de vida es un objetivo principal de diseño en toda red de sensores, dado que cada nodo tiene una autonomía limitada, tal y como hemos co- mentado a lo largo del proyecto. Además, el reemplazo de las baterías es una operación tediosa y a veces inviable que conviene aplazar lo máximo posible. Es cierto que hoy en día se producen nodos con sistemas de abastecimiento propio, pero estos no son actualmente muy utilizados debido a su elevado coste.

Por otro lado, la minimización del número de nodos repetidores también tiene importancia ya que es sabido que los nodos tienen una alcance limitado y cada vez las redes de sensores tienen como objetivo alcanzar coberturas más grandes. Esto obliga a utilizar nodos repetidores incrementando de esta forma el coste del despliegue.

4.2 Caracterización de los objetivos

La caracterización de los objetivos escogidos considera que el tiempo de vida de los nodos de una red de sensores tiene muchas definiciones, pero la que nosotros aplica- remos en este proyecto es la más común, la que corresonde al tiempo que transcurre hasta que el primer nodo deja de funcionar o bien, en otras palabras, dura mientras todos los nodos son operativos.

Para definir el tiempo de vida, utilizaremos la fórmula 4.1, dondeBes la cantidad de energía de todos los nodos, es decir, la batería. Si utilizáramos otro tipo de nodos, que tuvieran abastecimiento propio, esta definición de tiempo de vida no tendría sentido.

Por un lado,Ldesigna el tiempo de vida expresado en número de rondas y, por otra