tesis de Garbarino

Protocolos para redes inalambricas de sensores

Tesis de Ingenierıa en Informatica

Jimena [email protected]

DirectoraLic. Adriana Echeverrıa

Universidad de Buenos AiresFacultad de Ingenierıa

7 de noviembre de 2011

Agradecimientos

A mi mama Isabel Ubiedo y a mi papa Eduardo Antonio Garbarino.A Sergio.A mi directora de tesis, Lic. Adriana Echeverrıa.A toda mi familia, que hace tiempo que no los veo porque estaba estudiando.A mi hermana Florencia por insistir con que me reciba para reunirnos enuna fiesta.A todos los que me dieron aliento y me ayudaron de distinta manera: Maxi,Julia, Ale, Mariano MP y Naranjita, Valeria, Marcela, Agustın.A los profesores que me inspiraron en los comienzos: Ing. Jorge Alvarez Julia,Ing. Ricardo Sirne, Lic. Rina Lombardi, Ing. Osvaldo Clua, Ing. LeopoldoCarranza. A mis primeros tres jefes.A todos mis otros companeros de facultad o del trabajo, a los que perse-guı por los pasillos o por e-mail con alguna pregunta, especialmente a losque me ayudaron a aprobar la ultima materia.

3

Indice general

1. Introduccion 17

1.1. Motivacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3. Organizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2. Redes inalambricas de sensores 21

2.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.1. Topologıa . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1.2. Nodo sensor . . . . . . . . . . . . . . . . . . . . . . . . 24

2.1.3. Cuestiones de diseno . . . . . . . . . . . . . . . . . . . 26

2.2. Tipos de aplicacion . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.1. Deteccion y reporte de eventos . . . . . . . . . . . . . 29

2.2.2. Recoleccion de datos y reporte periodico . . . . . . . . 31

2.2.3. Consulta iniciada por sumidero . . . . . . . . . . . . . 32

2.2.4. Seguimiento . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2.5. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3. Estandares de comunicacion . . . . . . . . . . . . . . . . . . . 33

2.3.1. Bluetooth y Wi-Fi . . . . . . . . . . . . . . . . . . . . 33

2.3.2. Estandar IEEE 802.15.4-2006 . . . . . . . . . . . . . . 35

2.3.3. ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.3.4. WirelessHART . . . . . . . . . . . . . . . . . . . . . . 47

3. Protocolos de red 55

3.1. Problema del encaminamiento . . . . . . . . . . . . . . . . . . 55

3.2. Encaminamiento jerarquico . . . . . . . . . . . . . . . . . . . 57

3.2.1. Caracterısticas . . . . . . . . . . . . . . . . . . . . . . 57

3.2.2. LEACH . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.3. Encaminamiento geografico . . . . . . . . . . . . . . . . . . . 62


3.3.2. Por coordenadas virtuales . . . . . . . . . . . . . . . . 64

3.4. Encaminamiento centrado en los datos . . . . . . . . . . . . . 69


3.4.2. Energy-Aware Data-Centric Routing . . . . . . . . . . 70

5

INDICE GENERAL

3.5. Diseminacion de interes . . . . . . . . . . . . . . . . . . . . . 74


3.5.2. SPIN . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.6. Consciencia de la energıa . . . . . . . . . . . . . . . . . . . . 82

3.6.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . 82

3.6.2. Metricas de energıa . . . . . . . . . . . . . . . . . . . . 83

3.6.3. Flow Augmentation . . . . . . . . . . . . . . . . . . . 85

4. Diseno de la simulacion con Omnet++ 89

4.1. ¿Que es Omnet++? . . . . . . . . . . . . . . . . . . . . . . . 89

4.1.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . 89

4.1.2. Conceptos de modelado . . . . . . . . . . . . . . . . . 90

4.1.3. Descripcion de red . . . . . . . . . . . . . . . . . . . . 90

4.1.4. Conceptos de simulacion . . . . . . . . . . . . . . . . . 92

4.1.5. Ambiente de desarrollo . . . . . . . . . . . . . . . . . . 94

4.1.6. Definicion de un modulo simple . . . . . . . . . . . . . 94

4.1.7. Simulacion . . . . . . . . . . . . . . . . . . . . . . . . 97

4.1.8. Herramientas de analisis . . . . . . . . . . . . . . . . . 97

4.2. Diseno de la red . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.2.1. MiXiM 2.1 . . . . . . . . . . . . . . . . . . . . . . . . 100

4.2.2. Modelo de dispositivo . . . . . . . . . . . . . . . . . . 102

4.2.3. Topologıa . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.2.4. Tamano del terreno y densidad de nodos . . . . . . . . 105

4.2.5. Modelo de despliegue . . . . . . . . . . . . . . . . . . 106

4.2.6. Modelo de aplicacion . . . . . . . . . . . . . . . . . . . 107

4.2.7. Resumen del diseno . . . . . . . . . . . . . . . . . . . 108

4.3. Metricas de evaluacion . . . . . . . . . . . . . . . . . . . . . . 108

4.3.1. Vida util del sistema . . . . . . . . . . . . . . . . . . . 108

4.3.2. Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.3.3. Uso de la energıa . . . . . . . . . . . . . . . . . . . . . 110

4.3.4. Calidad de servicio . . . . . . . . . . . . . . . . . . . . 111

4.3.5. Metricas no consideradas . . . . . . . . . . . . . . . . 112

4.3.6. Metricas seleccionadas . . . . . . . . . . . . . . . . . . 113

5. Implementacion de modulos de red 115

5.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

5.2. Diseminacion de interes con M-SPIN . . . . . . . . . . . . . . 116


5.2.2. Especificaciones . . . . . . . . . . . . . . . . . . . . . . 118

5.2.3. Complejidad M . . . . . . . . . . . . . . . . . . . . . . 129

5.2.4. Detalles de implementacion . . . . . . . . . . . . . . . 131

5.2.5. Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . 135

5.3. Consciencia de recursos con SAMF . . . . . . . . . . . . . . . 138


6

INDICE GENERAL

5.3.2. Especificaciones . . . . . . . . . . . . . . . . . . . . . . 1425.3.3. Complejidad M . . . . . . . . . . . . . . . . . . . . . . 1465.3.4. Detalles de implementacion . . . . . . . . . . . . . . . 1475.3.5. Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . 149

5.4. Modulo de tecnica mixta: EA-SPIN . . . . . . . . . . . . . . . 1535.4.1. Diseno . . . . . . . . . . . . . . . . . . . . . . . . . . . 1535.4.2. Especificaciones . . . . . . . . . . . . . . . . . . . . . . 1545.4.3. Complejidad M . . . . . . . . . . . . . . . . . . . . . . 1605.4.4. Detalles de implementacion . . . . . . . . . . . . . . . 1615.4.5. Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . 164

5.5. Resumen de modulos desarrollados . . . . . . . . . . . . . . . 167

6. Simulacion y conclusiones 1696.1. Escenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1706.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

6.2.1. Complejidad M . . . . . . . . . . . . . . . . . . . . . . 1706.2.2. Metricas obtenidas . . . . . . . . . . . . . . . . . . . . 1726.2.3. Analisis de confiabilidad . . . . . . . . . . . . . . . . . 1886.2.4. Consciencia de energıa . . . . . . . . . . . . . . . . . . 1896.2.5. Experiencia con MiXiM 2.1 y Omnet++ 4.1 . . . . . . 191

6.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . 1926.4. Resumen de aportes del trabajo . . . . . . . . . . . . . . . . . 1936.5. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Apendices 194

A. Glosario 197

B. Metricas 203B.1. Recopilacion de metricas . . . . . . . . . . . . . . . . . . . . . 203B.2. Metricas de simulaciones especıficas . . . . . . . . . . . . . . 206

C. Modificaciones a MiXiM 2.1 209C.1. Energıa de transmision . . . . . . . . . . . . . . . . . . . . . . 209C.2. Total de mensajes . . . . . . . . . . . . . . . . . . . . . . . . 209C.3. Energıa residual . . . . . . . . . . . . . . . . . . . . . . . . . . 211C.4. Sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Referencias 213

7

INDICE GENERAL

8

Indice de figuras

2.1. Infraestructura de una red inalambrica de sensores . . . . . . 22

2.2. Componentes de hardware del nodo sensor . . . . . . . . . . . 25

2.3. Componentes de software del nodo sensor . . . . . . . . . . . 26

2.4. Pila generica de protocolos del nodo sensor . . . . . . . . . . 27

2.5. Nodo sensor MicaZ de MEMSIC . . . . . . . . . . . . . . . . 28

2.6. Tipos de aplicacion . . . . . . . . . . . . . . . . . . . . . . . . 34

2.7. Estructura del paquete de capa fısica IEEE 802.15.4 . . . . . 36

2.8. Superframe de IEEE 802.15.4 CSMA ranurado . . . . . . . . 37

2.9. Capas de protocolos de ZigBee . . . . . . . . . . . . . . . . . 41

2.10. Red ZigBee estrella . . . . . . . . . . . . . . . . . . . . . . . . 41

2.11. Red ZigBee malla . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.12. Pila de protocolos WirelessHART . . . . . . . . . . . . . . . . 48

2.13. Malla WirelessHART . . . . . . . . . . . . . . . . . . . . . . . 50

3.1. Jerarquıa virtual en una red de sensores . . . . . . . . . . . . 58

3.2. Topologıa de red en LEACH . . . . . . . . . . . . . . . . . . . 59

3.3. Encaminamiento geografico . . . . . . . . . . . . . . . . . . . 62

3.4. Encaminamiento geografico en presencia de obstaculos . . . . 63

3.5. Nodos perımetro . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.6. Maquina de estados del nodo EAD . . . . . . . . . . . . . . . 71

3.7. De estado indefinido a estado hoja . . . . . . . . . . . . . . . 72

3.8. Ejemplo de agregacion de datos camino al sumidero . . . . . 73

3.9. Implosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

3.10. Superposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

3.11. Negociacion SPIN pasos 1 y 2 . . . . . . . . . . . . . . . . . . 79

3.12. Negociacion SPIN pasos 3 y 4 . . . . . . . . . . . . . . . . . 80

3.13. Negociacion SPIN pasos 5 y 6 . . . . . . . . . . . . . . . . . . 80

3.14. Desempeno no optimo de FA . . . . . . . . . . . . . . . . . . 87

4.1. Vista de diseno de una red Omnet++ . . . . . . . . . . . . . 91

4.2. Diseno del nodo como modulo compuesto . . . . . . . . . . . 91

4.3. Perspectiva de Simulacion de Omnet++ en Eclipse . . . . . . 94

4.4. Configuracion de ejecucion en Omnet++ . . . . . . . . . . . . 97

9

INDICE DE FIGURAS

4.5. Grafico de secuencia en Omnet++ . . . . . . . . . . . . . . . 984.6. Navegador de vectores y escalares en Omnet++ . . . . . . . . 994.7. Grafico de barras en Omnet++ . . . . . . . . . . . . . . . . . 994.8. Potencia de transmision del tranceptor TI CC2420 . . . . . . 104

5.1. Etapa de descubrimiento de distancia al sumidero . . . . . . . 1175.2. Jerarquıa de modulos de diseminacion . . . . . . . . . . . . . 132

6.1. Escenario 1 - Latencia media en el sumidero . . . . . . . . . . 1726.2. Escenario 1 - Tasa de exito . . . . . . . . . . . . . . . . . . . 1726.3. Escenario 1 - Overhead . . . . . . . . . . . . . . . . . . . . . . 1736.4. Escenario 1 - Total de energıa de transmision . . . . . . . . . 1736.5. Escenario 1 - Media y maxima de saltos . . . . . . . . . . . . 1746.6. Escenario 1 - Media y desviacion de energıa de transmision . 1746.7. Escenario 2 - Latencia media en el sumidero . . . . . . . . . . 1756.8. Escenario 2 - Tasa de exito . . . . . . . . . . . . . . . . . . . 1756.9. Escenario 2 - Overhead . . . . . . . . . . . . . . . . . . . . . . 1766.10. Escenario 2 - Total de energıa de transmision . . . . . . . . . 1766.11. Escenario 2 - Media y maxima de saltos . . . . . . . . . . . . 1776.12. Escenario 2 - Media y desviacion de energıa de transmision . 1776.13. Escenario 3 - Latencia media en el sumidero . . . . . . . . . . 1786.14. Escenario 3 - Tasa de exito . . . . . . . . . . . . . . . . . . . 1786.15. Escenario 3 - Overhead . . . . . . . . . . . . . . . . . . . . . . 1796.16. Escenario 3 - Total de energıa de transmision . . . . . . . . . 1796.17. Escenario 3 - Media y maxima de saltos . . . . . . . . . . . . 1806.18. Escenario 3 - Media y desviacion de energıa de transmision . 1806.19. Escenario 4 - Latencia media en el sumidero . . . . . . . . . . 1816.20. Escenario 4 - Tasa de exito . . . . . . . . . . . . . . . . . . . 1816.21. Escenario 4 - Overhead . . . . . . . . . . . . . . . . . . . . . . 1826.22. Escenario 4 - Total de energıa de transmision . . . . . . . . . 1826.23. Escenario 4 - Media y maxima de saltos . . . . . . . . . . . . 1836.24. Escenario 4 - Media y desviacion de energıa de transmision . 1836.25. Escenario 1 - Total de energıa vs. distancia al sumidero . . . 1846.26. Escenario 2 - Total de energıa vs. distancia al sumidero . . . 1846.27. Escenario 3 - Total de energıa vs. distancia al sumidero . . . 1856.28. Escenario 4 - Total de energıa vs. distancia al sumidero . . . 1856.29. Escenario 2: Promedio de energıa de transmision por distancia 1906.30. Escenario 4: Promedio de energıa de transmision por distancia 190

10

Indice de cuadros

2.1. Funciones de la pila de protocolos WSN . . . . . . . . . . . . 272.2. Resumen de tipos de aplicacion y caracterısticas . . . . . . . 332.3. Campos de la tabla de encaminamiento ZigBee . . . . . . . . 432.4. Campos de la tabla de descubrimiento de ruta ZigBee . . . . 442.5. Campos de la tabla de nodos vecinos ZigBee . . . . . . . . . . 45

4.1. Modulos MiXiM utilizados . . . . . . . . . . . . . . . . . . . . 1034.2. Densidad mınima de nodos . . . . . . . . . . . . . . . . . . . 1064.3. Resumen de la red a simular . . . . . . . . . . . . . . . . . . . 108

5.1. Metricas de M-SPIN . . . . . . . . . . . . . . . . . . . . . . . 1175.2. Atributos de cada enlace SAMF . . . . . . . . . . . . . . . . . 1405.3. Atributos de cada nodo SAMF . . . . . . . . . . . . . . . . . 1405.4. Metricas de SAMF . . . . . . . . . . . . . . . . . . . . . . . . 1425.5. Contadores para el analisis de SPIN . . . . . . . . . . . . . . 1635.6. Modulos desarrollados . . . . . . . . . . . . . . . . . . . . . . 167

6.1. Escenarios simulados . . . . . . . . . . . . . . . . . . . . . . . 1706.2. Cantidad total de paquetes enviados en cada escenario . . . . 1716.3. Metricas de escenario 1 . . . . . . . . . . . . . . . . . . . . . 1866.4. Metricas de escenario 2 . . . . . . . . . . . . . . . . . . . . . 1866.5. Metricas de escenario 3 . . . . . . . . . . . . . . . . . . . . . 1876.6. Metricas de escenario 4 . . . . . . . . . . . . . . . . . . . . . 1876.7. Total de frames descartados por interferencia . . . . . . . . . 1896.8. Consumo total de energıa en transmisiones . . . . . . . . . . 189

B.1. Metricas de evaluacion de protocolos . . . . . . . . . . . . . . 203B.2. Otras metricas de desempeno . . . . . . . . . . . . . . . . . . 204B.3. Metricas de una revision de criterios de evaluacion . . . . . . 205B.4. Metricas de evaluacion del protocolo SPIN . . . . . . . . . . . 206B.5. Metricas de evaluacion del protoclo PBR . . . . . . . . . . . . 206B.6. Metricas de evaluacion del protocolo EAD . . . . . . . . . . . 207

11

INDICE DE CUADROS

12

Fragmentos de codigo

4.1. Modelo de protocolo de capa . . . . . . . . . . . . . . . . . . 964.2. Definicion de red . . . . . . . . . . . . . . . . . . . . . . . . . 1004.3. Configuracion del decider . . . . . . . . . . . . . . . . . . . . 1014.4. Actividades de capa fısica . . . . . . . . . . . . . . . . . . . . 1054.5. Configuracion del nodo sumidero . . . . . . . . . . . . . . . . 1054.6. Dimensiones del terreno . . . . . . . . . . . . . . . . . . . . . 1055.1. Paquete M-SPIN . . . . . . . . . . . . . . . . . . . . . . . . . 1335.2. Paquete SAMF . . . . . . . . . . . . . . . . . . . . . . . . . . 1475.3. Paquete EA-SPIN . . . . . . . . . . . . . . . . . . . . . . . . 161C.1. Metodo getActivityTotal() . . . . . . . . . . . . . . . . . . . . 209C.2. Redefinicion del modulo de rastreo . . . . . . . . . . . . . . . 210C.3. Herencia publica de ImNotifiable para SimTracer . . . . . . . 210C.4. Total de paquetes a partir de notificaciones . . . . . . . . . . 210C.5. SPIN publica paquetes envıados y de sobreescucha . . . . . . 211C.6. Grabacion de la energıa residual al finalizar . . . . . . . . . . 211C.7. Grabacion del consumo por actividad . . . . . . . . . . . . . . 211C.8. Descarte por baja intensidad en Decider802154Narrow . . . . 212

13

FRAGMENTOS DE CODIGO

14

Algoritmos

1. Ciclo de evento . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

2. M-SPIN Procesar paquete de aplicacion . . . . . . . . . . . . . 1353. M-SPIN Procesar paquete STARTUP . . . . . . . . . . . . . . 1354. M-SPIN Procesar paquete ADV de anuncio . . . . . . . . . . . 1365. M-SPIN Procesar paquete REQ de pedido . . . . . . . . . . . 1366. M-SPIN Procesar paquete DATA de datos . . . . . . . . . . . 1377. M-SPIN Expira temporizador de repeticion o supresion de pedido1378. SAMF Procesar paquete de aplicacion . . . . . . . . . . . . . . 1509. SAMF Procesar paquete INTEREST . . . . . . . . . . . . . . 15010. SAMF Procesar paquete DATA . . . . . . . . . . . . . . . . . 15111. SAMF Recalcular restricciones de enlace . . . . . . . . . . . . 15112. SAMF Actualizar enlace en la tabla . . . . . . . . . . . . . . . 15213. SAMF Obtener la mejor ruta a destino . . . . . . . . . . . . . 15214. EA-SPIN Procesar paquete de aplicacion . . . . . . . . . . . . 16415. EA-SPIN Procesar paquete STARTUP . . . . . . . . . . . . . 16416. EA-SPIN Procesar paquete ADV de anuncio . . . . . . . . . . 16517. EA-SPIN Procesar paquete REQ de pedido . . . . . . . . . . . 16518. EA-SPIN Procesar paquete DATA de datos . . . . . . . . . . . 16619. EA-SPIN Expira temporizador pedido . . . . . . . . . . . . . . 16620. EA-SPIN Expira temporizador de repeticion de anuncio . . . . 167

15

ALGORITMOS

16

Capıtulo 1

Introduccion

1.1. Motivacion

Una red inalambrica de sensores, o Wireless Sensor Network, es una redde un gran numero de pequenos dispositivos capaces de medir diferentesvariables de ambiente en el que se encuentran, y de procesar y comunicar lainformacion de manera inalambrica [1][2].

Existen varios tipos de aplicaciones de esta tecnologıa. Por ejemplo, endefensa, la deteccion de ataque nuclear, biologico y quımico. En medio am-biente, el monitoreo de microclimas, deteccion de fuego, deteccion de inun-daciones, agricultura [3]. En salud, monitoreo de medicos y pacientes, y deinformacion fisiologica. En el hogar, lectura automatica de medidores, y au-tomatizacion del hogar. Entre sus aplicaciones comerciales se encuentran elcontrol de inventario, el seguimiento y deteccion de vehıculos, el monitoreode trafico, el control del medio ambiente en oficinas y edificios industriales.Tıpicamente, la red de sensores sera administrada por una entidad civil, co-mercial, industrial o del gobierno [4].

El modelo de red, en la mayorıa de los casos, esta compuesto por unaestacion base, que es un dispositivo con recursos de energıa y computo noacotados, y un numero de pequenos dispositivos homogeneos, los nodos sen-sores [5].

Un nodo sensor generalmente embebe capacidad de procesamiento y al-macenamiento, y puede tener uno o mas sensores acusticos, sısmicos, de ra-dio, infrarrojos, opticos, magneticos, y quımicos o biologicos. El nodo cuentatambien con una unidad de comunicacion inalambrica, y una baterıa, y posi-blemente es capaz de conocer su posicion geografica apoyandose en un GPSo en un algoritmo de posicionamiento. Invariablemente el nodo se encuentrarestringido en energıa, ancho de banda y en recursos en general [4]. Para

17

1.1. MOTIVACION

poder ser operados, los nodos necesitan un sistema operativo especıfico pararedes de sensores. Tıpicamente, se tienen cinco subsistemas o componen-tes de software: el sistema operativo, controladores de sensor, procesadoresde comunicacion, controladores de comunicacion y pequenas aplicaciones deprocesamiento de datos [4].

El estandar de comunicacion adoptado en los ultimos anos por el merca-do fue desarrollado por la ZigBee Alliance [4] y define una arquitectura decapas para la comunicacion inalambrica. Cada capa brinda un conjunto deservicios especıficos a la capa superior. La capa fısica, responsable del mane-jo de la interfaz inalambrica (frecuencia de operacion, tipo de modulacion,codificacion) y la capa de enlace responsable del manejo de la comunica-cion con nodos vecinos (dentro del radio de un salto) estan definidas porel estandar IEEE 802.15.4-2003. La capa de red, responsable del encamina-miento de paquetes dentro de la red de sensores, y cuya principal restriccionde diseno es la eficiencia energetica [4], soporta, en esta arquitectura, trestopologıas: estrella, arbol y malla.

Para definir el costo de una ruta, el algoritmo de encaminamiento utilizauna metrica de costo para comparar caminos alternativos. Para calcular elvalor de la metrica para un determinado camino, se asocia un costo a cadaenlace entre dos nodos, y se suma el costo de cada uno de los enlaces utili-zados por el camino. El costo de cada enlace individual se define como unafuncion que depende de la probabilidad de que el paquete sea entregado sise utiliza ese enlace. En el estandar se plantea que la cuestion de estimar odefinir esta probabilidad es un problema de implementacion, para el cual,los implementadores son libres de aplicar su ingenio [6]. El algoritmo es muysimilar al algoritmo AODV (Ad hoc On-Demand Distance Vector) el cualno tiene consideraciones respecto de la optimizacion de la energıa [7].

AODV es un protocolo para redes ad hoc donde los nodos se consideranmoviles y se favorecen rutas que utilizan la menor cantidad de enlaces o sal-tos [8]. Aunque las redes inalambricas de sensores tienen aspectos en comuncon las redes cableadas y ad hoc, tienen tambien caracterısticas propias queplantean importantes desafıos de diseno. La densidad de nodos de la red yel area de cobertura pueden variar ampliamente, pudiendo ser instalada demanera no supervisada con una distribucion de nodos al azar en terrenosinaccesibles [4][9]. La red debe organizarse a sı misma y preservar la energıa,para perdurar su vida util operando con limitadas reservas de baterıa.

Dado que gran parte de la energıa se emplea en la transmision de paque-tes de informacion en topologıas multi-salto (multi-hop), numerosas tecnicaspara protocolos de red han sido estudiadas, con el objeto de mejorar la efi-ciencia en las comunicaciones en las redes inalambricas de sensores. Se ha

18

CAPITULO 1. INTRODUCCION

identificado un conjunto de paradigmas que permite clasificar los protocolossegun la estructura de red (plana o jerarquica), por el tipo de direcciona-miento (basado en la ubicacion geografica), por la funcionalidad provista(que mantienen mas de una ruta, basado en la calidad de servicio, que uti-lizan agregacion de datos) [10], por utilizar modelos de flujo de red y/o porser centrados en los datos (basados en consulta, basados en diseminacion deinformacion) [11]. Algunos protocolos que modelan el flujo de red incluyen,en su diseno, el objetivo de maximizar la vida de la red [12][13][14][15]. Peroexisten varios puntos de vista para definir el tiempo de vida de la red, siem-pre influidos por el tipo de aplicacion para el cual se disena. Para algunosautores, se define como el tiempo hasta que se agota la baterıa del primernodo [2][12]. Para otros, esta definicion es muy restrictiva y puede flexibili-zarse para extender aun mas la vida util de la red [13][14].

Una estrategia de maximizacion de la vida de la red consiste en selec-cionar rutas no optimas de manera de posponer la muerte de sus nodos,basando la seleccion en el conocimiento de diferentes metricas de energıa delos nodos de la red [9][16]. Los algoritmos que utilizan este tipo de informa-cion para seleccionar la ruta son conscientes de la energıa.

Los protocolos que se centran en los datos encaminan datos por deman-da, reaccionando a una consulta iniciada por la estacion base [10]. Intentanahorrar energıa disminuyendo las tareas de mantenimiento de la red, porlo que sugieren una topologıa de red plana. El establecimiento de rutas esdinamico, utilizando diferentes estrategias para controlar el proceso de floo-ding o inundacion de la red en la etapa de descubrimiento, y para diseminarel interes por un tipo de informacion [4][17][18].

1.2. Objetivos

Los objetivos generales de la tesis son el estudio de redes inalambricasde sensores y paradigmas de encaminamiento de vanguardia, y la simulaciony analisis de protocolos que utilizan tecnicas de diseminacion y conscienciade energıa.

En este marco se llevo a cabo el siguiente trabajo:

estudio general de las redes inalambricas de sensores

estudio de los tipos de aplicacion

estudio de las principales paradigmas de vanguardia en encaminamien-to, focalizando en las tecnicas de diseminacion y consciencia de laenergıa

evaluacion de Omnet++ como simulador para este tipo de red

19

1.3. ORGANIZACION

configuracion de una red ejemplo, de un sumidero y muchos nodosque ejecutan una aplicacion de tipo consulta, y una pila de protocolosIEEE 802.15.4, incluyendo al canal compartido en el modelo

construccion de modulos de red para los protocolos SAMF, M-SPIN, yun modulo que combina las tecnicas de ambos; construccion de modu-los de utilidades de recoleccion de estadısticas y metricas no incluidasen la herramienta

simulacion de los tres protocolos a partir de varios escenarios de con-sulta

comparacion de su desempeno, analisis y observaciones sobre las tecni-cas seleccionadas

1.3. Organizacion

En el capıtulo 2 se presenta una introduccion a las redes inalambricasde sensores en terminos generales, una clasificacion y caracterizacion de lostipos de aplicacion segun su modelo de entrega de datos y una revision delos estandares y tecnologıas de comunicacion adoptados para este tipo de red.

El capıtulo 3 introduce los problemas del encaminamiento y revisa lostres paradigmas mas comunmente utilizados en taxonomıas de protocolosde red, ilustrando cada paradigma con la descripcion de un protocolo de lafamilia. Luego, se describen las tecnicas de diseminacion y consciencia deenergıa, tambien con protocolos ejemplo.

El cuarto capıtulo trata de la herramienta de simulacion Omnet++, des-cribe el diseno de la red a simular y se enumeran las metricas a obtener parala evaluacion de los protocolos.

En el capıtulo 5 se detalla la implementacion los modulos de red paralos protocolos M-SPIN, SAMF y un protocolo que combina las tecnicas deambos, sus especificaciones, analisis de complejidad y pseudocodigo.

Finalmente, el capıtulo 6 expone los resultados de las simulaciones y lasconclusiones del trabajo.

20

Capıtulo 2

Redes inalambricas desensores

2.1. Introduccion

Una red de sensores es una infraestructura compuesta por elementosde computo, medicion y comunicacion, que permiten al administrador ins-trumentar, observar y reaccionar a eventos y fenomenos en un ambienteespecıfico [4]. Tıpicamente el administrador sera una entidad civil, comer-cial, gubernamental o industrial. El ambiente puede ser un sistema espacioo sistema biologico, y existen variadas aplicaciones [19]:

MedioambientalAlgunos ejemplos son el seguimiento de aves, pequenos animales, in-sectos; monitoreo de condiciones ambientales que afectan cultivos yganado; irrigacion; macroinstrumentos para monitoreo a gran escalay exploracion planetaria; deteccion quımica y biologica; agriculturade precision; deteccion de incendios en bosques; investigacion meteo-rologica o geofısica; deteccion de inundaciones; estudio de la contami-nacion.

MedicinaProvision de interfaces para discapacitados, monitoreo integrado depacientes, diagnostico, administracion de drogas en hospitales, tele-monitoreo de informacion fisiologica.

HogarAutomatizacion del hogar, administracion local y remota de electro-domesticos, ambientes inteligentes.

ComercialMonitoreo de fatiga de material, administracion de inventario, cali-

21

2.1. INTRODUCCION

dad de producto, oficinas inteligentes, control ambiental de edificios,control robot en manufactura automatizada, juguetes interactivos, mu-seos interactivos, control y automatizacion de procesos, monitoreo dearea de desastre, diagnostico de maquinaria, transporte, seguimientode vehıculos.

Figura 2.1: Infraestructura de una red inalambrica de sensores

La infraestructura comprende los siguientes componentes basicos (figu-ra 2.1 obtenida de [20]):

1. un conjunto de nodos sensores

2. una red de interconexion inalambrica

3. un punto central de recoleccion de informacion o estacion base

4. un conjunto de recursos para procesar la informacion recolectada

Los sensores o nodos inalambricos, a veces llamados motes, son dispo-sitivos inteligentes multifuncionales y baratos, equipados con multiples ele-mentos de sensado. Existe tecnologıa de sensado para realizar mediciones de

22

CAPITULO 2. REDES INALAMBRICAS DE SENSORES

campo electrico y magnetico; de frecuencia; optico, electro-opticos e infrarro-jos; radares; laseres; de posicion/navegacion; sısmicas y de ondas de presion;de medio ambiente (viento, humedad, calor). Este tipo de dispositivo po-see recursos restringidos de energıa, comunicacion, memoria y capacidad decomputo [4].

2.1.1. Topologıa

Dentro del area de sensado, los sensores se interconectan por medio en-laces inalambricos multi-salto, de corta distancia y baja potencia de trans-mision, para enviar informacion a estaciones recolectoras o de monitoreo.Tıpicamente se despliegan en grandes cantidades y con una distribuciondensa. Hay dos tipos de redes [21]:

no estructuradasComprende una coleccion de nodos densa, desplegados ad hoc, po-siblemente al azar. Una vez desplegados, la red opera desatendida,monitoreando y reportando informacion. El mantenimiento, la admi-nistracion de la conectividad y deteccion de fallas son difıciles por lagran cantidad de nodos.

estructuradasTodos o algunos de los nodos son desplegados de manera pre-planificada,colocados en posiciones fijas. Tienen la ventaja de requerir una menorcantidad de nodos para lograr la cobertura del area, con un menorcosto de administracion y mantenimiento.

Existen varias configuraciones de redes de sensores [22]. Un nodo fuentees una entidad en la red que puede proveer informacion, el nodo sensor. Porotro lado, un sumidero es la entidad que requiere la informacion. El sumide-ro puede pertenecer a la red de sensores (y es otro sensor), ser una entidadexterna a la red o ser un gateway a otra red mas grande, como Internet.Comunmente, el sumidero o estacion base es un dispositivo que posee recur-sos de energıa y capacidad computacional no acotados [5]. El modelo de redtıpico comprende un sumidero y multiples nodos fuente o sensores, pero enmuchas aplicaciones se utilizan tambien multiples sumideros.

Dadas las limitaciones de alcance de radio, las redes inalambricas desensores en general son multi-salto, y los nodos sensores actuan como enca-minadores, ahorrando la necesidad de dispositivos adicionales. El multi-saltopermite superar problemas con distancias largas y obstaculos, y mejora laeficiencia de la comunicacion. Asimismo, la topologıa de red puede ser planao jerarquica, dependiendo de la aplicacion y el tipo de encaminamiento que

23

2.1. INTRODUCCION

mejor se adecue a sus requerimientos.

La movilidad en las redes de sensores puede aparecer en tres formas prin-cipales [22]:

movilidad del nodo sensorLa movilidad del nodo sensor depende de la aplicacion. Por ejemplo,en el monitoreo medioambiental, los nodos son estacionarios. Sin em-bargo, en el monitoreo de ganado, el sensor esta sujeto al animal y porlo tanto se mueve. Cuando hay movilidad, la red debe reorganizarsefrecuentemente.

movilidad del sumideroEl aspecto importante es la movilidad de un sumidero que no es partede la red, por ejemplo, un humano con un dispositivo personal solicitainformacion mientras se desplaza dentro de un edificio inteligente. Elsumidero movil puede solicitar la informacion en un lugar de la redy luego moverse a otro lugar, y la red debe lograr que los datos loalcancen.

movilidad del eventoEn aplicaciones de seguimiento, los objetos o evento a seguir pueden sermoviles. En este escenario, es importante que los eventos sean cubiertospor una suficiente cantidad de sensores al mismo tiempo. A medida queel objeto se desplaza a traves de la red, es acompanado por un areade actividad dentro de la misma. Los nodos que no detectan nada,alternan a estados de sueno hasta que se requieran transmisiones dela zona en que se encuentran.

2.1.2. Nodo sensor

Hardware

Un nodo sensor basico comprende los siguientes cuatro subsistemas dehardware[4][22] (ver figura 2.2 obtenida de [4]):

EnergıaSuministro o infraestructura de energıa para poder operar desde unashoras hasta meses o anos.

Logica computacional y almacenamientoPara el procesamiento de datos, almacenamiento temporal, cifrado,modulacion y transmision.

24


Figura 2.2: Componentes de hardware del nodo sensor

SensorLa interfaz entre el medioambiente y el nodo es el sensor. Puede serde humedad, luz, flujo magnetico, temperatura, etc.

ComunicacionSe requiere un dispositivo para poder enviar y recibir informacion atraves de un canal inalambrico.

Software

Los sensores generalmente operan con cinco subsistemas de software [4](ver figura 2.3 obtenida de [4]):

Sistema operativoEl microcodigo o sistema operativo, tambien llamado middleware, esel microcodigo comun del dispositivo, utilizado por todos los progra-mas de alto nivel, residentes en el nodo. Usualmente, presentan unaarquitectura que permite una rapida implementacion con un tamanomınimo de codigo. TinyOS es un ejemplo [23].

Controladores de sensoresModulos de software que administran funciones basicas de los trancep-tores de sensores (sensor transceiver).

Procesadores de comunicacionModulos que administran funciones de comunicacion, encaminamiento,almacenamiento y reenvıo de paquetes, mantenimiento de la topologıade red, control de acceso al medio, cifrado, correccion de errores, etc.

25

2.1. INTRODUCCION

Figura 2.3: Componentes de software del nodo sensor

Controladores de comunicacionModulos que administran las tareas de utilizacion del enlace de trans-mision por radio, sincronizacion, codificacion de senales, recuperacionde errores, modulacion.

Mini-aplicaciones de proceso de datosAplicaciones basicas soportadas a nivel nodo para procesamiento dedatos en la red.

Protocolos

Los controladores y procesadores de comunicacion, piezas de softwareque asisten a la interconexion entre nodos, son componentes arquitectonicosde mayor relevancia. Se ha realizado mucha investigacion para desarrollarprotocolos especialmente disenados para las redes inalambricas de sensores.En la figura 2.4 (obtenida de [4]) se ilustra un modelo de protocolos genericoque comunmente es utilizado para describir el aparato de comunicacion [4].

En la tabla 2.1 (obtenida tambien de [4]) se caracterizan brevemente lasfunciones de cada capa de la pila.

2.1.3. Cuestiones de diseno

Para que las redes de sensores lleguen a ser verdaderamente omnipre-sentes se deben encontrar soluciones a problemas propios de diseno, entreellos[4]:

26


Figura 2.4: Pila generica de protocolos del nodo sensor

Capas superiores Aplicaciones residentes en la red,procesamiento, agregacion, proce-samiento de consultas externas, ybase de datos externa.

Capa 4 Transporte, incluyendo disemina-cion y acumulacion de datos, cachey almacenamiento.

Capa 3 Red, administracion dinamica de latopologıa y encaminamiento

Capa 2 Enlace, administracion del canalcompartido, competencia por el ca-nal, y acceso al medio, sincroniza-cion y localizacion

Capa 1 Fısica, canal de comunicacion, pro-cesamiento de senales

Cuadro 2.1: Funciones de la pila de protocolos WSN

Restricciones de hardwareUn sensor podrıa tener que caber en un modulo de unos pocos centıme-tros cubicos de volumen. Los sensores podrıan tambien tener que serdesechables, autonomos y adaptativos al ambiente. Se necesita lograrun empaque confiable a pesar de estas restricciones de hardware. Lafigura 2.5, obtenida de la hoja de datos del nodo MicaZ [24]), corres-ponde a un nodo de 58 mm de largo, 32 mm de ancho y 7 mm dealtura, excluyendo la baterıa.

27

2.1. INTRODUCCION

Figura 2.5: Nodo sensor MicaZ de MEMSIC

Consumo de energıaLa vida util del sensor depende mucho de la duracion de la baterıa,y en muchos casos es limitada y no se puede recargar. Por lo tanto,se deben disenar algoritmos y protocolos conscientes de la energıa.Se pueden definir tres dominios funcionales de consumo de energıa:sensado, comunicacion y procesamiento; todos requieren optimizacionpara minimizar la utilizacion de energıa.

CostoCasi por definicion, la red inalambrica de sensores consiste de un granconjunto de nodos sensores, por lo que el costo de cada unidad afectacrıticamente el costo de la red.

AmbienteSe espera que las redes de sensores operen de manera desatendida enlugares geograficos remotos, con grandes desafıos de administracion, odensamente desplegados, o dentro del ambiente observado.

Canales de transmisionLos medios de comunicacion inalambricos utilizados son restringidosen ancho de banda y desempeno en general. Para facilitar la operacionglobal de estas redes, el canal seleccionado debe estar disponible entodo el mundo.

Conectividad y topologıaSe necesitan protocolos ad hoc disenados para soportar cambios detopologıa debido a la movilidad, disponibilidad de recursos, perdidasde informacion, apagones, mal funcionamiento, interferencia, etc.

EstandaresUn conjunto de protocolos y estandares abiertos son necesarios para las

28


capas fısica, enlace, red y transporte. Historicamente, se han utilizadoprotocolos especıficos de cada aplicacion, con el efecto de retardar lacomercializacion a gran escala.

2.2. Tipos de aplicacion

Por la variedad de aplicaciones que pueden tener las WSNs, existe lanecesidad de desarrollar protocolos especıficos del tipo de aplicacion, con elriesgo de desarrollar un protocolo diferente para cada aplicacion [25]. Porello es importante poder clasificar las aplicaciones, para disenar solucionesde clase. Una clasificacion no sera exhaustiva, puesto que puede haber su-perposicion de clases en algun aspecto, sin embargo, lo mas importante esque permite organizar el diseno.

En [26] se presenta una clasificacion de nueve dimensiones taxonomicas,entre ellas:

Vida utilSi bien existe una variedad de metricas relacionadas al consumo deenergıa, se propone que la medida fundamental debe estar relacionadacon el concepto de vida util de la red, es decir el tiempo que durafuncionando de manera operativa. Puede ser simple o de duracion fija,compleja o de fases multiples.

LatenciaLa latencia, esto es, el tiempo que tarda en recibirse un paquete, esun requerimiento temporal cuantificable en las redes inalambricas desensores. Puede ser despreciable, moderada o estricta.

Ancho de bandaAbarca dos aspectos del patron de trafico. Se refiere al volumen de da-tos requerido y a la frecuencia de las transmisiones. Puede ser episodico-bajo, episodico-alto, continuo-bajo o continuo-alto.

En [25] se presenta una clasificacion algo mas simplificada y basada enlos objetivos de la aplicacion, los requerimientos de entrega de datos y elpatron de trafico, definiendo cuatro tipos de aplicacion descriptos en la si-guientes secciones. Para cada tipo, se especifican los requerminetos de vidautil, latencia, ancho de banda y encaminamiento. Un clasificacion similar seha tratado en [27].

2.2.1. Deteccion y reporte de eventos

Patron de trafico: EpisodicoLatencia: Estricta

29

2.2. TIPOS DE APLICACION

Vida util: Compleja

El objetivo de este tipo de aplicacion es la deteccion de un evento infre-cuente, como pueden serlo la presencia de un intruso, una anomalıa o fallamecanica, un incendio en un bosque. Una vez detectado, el evento debe serprontamente reportado al sumidero. La aplicacion instalada estara inactivacasi todo el tiempo, y se produciran rafagas de actividad cuando un eventosea detectado. Este tipo de aplicacion tiene dos problemas importantes. Elprimero es la necesidad de disminuir la tasa de falsas alarmas que puedanproducirse, posiblemente utilizando el consenso de un grupo de nodos paradetectar el evento, en lugar de un unico nodo. El segundo problema, masimportante aun, es el encaminamiento del evento al vuelo, hacia el sumidero.

Por la infrecuencia de los eventos, el principio de diseno que predomina esel de minimizar el consumo de energıa del resto de las actividades. Entonces,dado que se espera que el volumen de trafico sea muy bajo, la equidad o lascolisiones en el enlace no son muy importantes, pero la escucha ociosa y elintercambio de mensajes de control deben optimizarse.

Direccionamiento y encaminamiento

Para el encaminamiento en este tipo de aplicaciones, en [25] se destacala necesidad de un mecanismo de direccionamiento especial, la construccionde rutas de manera reactiva y la utilizacion de un ciclo de servicio del tran-ceptor que permita el ahorro de energıa.

Un esquema de direcciones es necesario para el enlace y el encaminamien-to, y para etiquetar los datos con informacion sobre el lugar donde fuerongenerados. Por la gran cantidad de nodos, no resulta conveniente utilizaruna direccion para cada nodo, ya que se necesitarıa un tamano de direccionbastante grande. Ademas, los nodos en general se comunican solo localmen-te (con los vecinos) o al sumidero, por lo que no se necesita direccionar decualquier nodo a cualquier nodo.

En aplicaciones de deteccion de eventos, es mas adecuado utilizar en-caminamiento reactivo, pues la transmision de datos es infrecuente, y si seutiliza encaminamiento proactivo, el mantenimiento de rutas genera un cos-to innecesario.

En general, una gran cantidad de energıa es consumida en escucha ocio-sa. Como es raro que ocurra un evento, los nodos utilizan muy poca energıaen transmitir realmente la informacion. Por ello, se busca que los nodosfuncionen en modo ahorro de energıa, apagando sus radios periodicamenteen forma independiente o coordinada, ejecutando un ciclo domir-servir. Co-

30


mo la comunicacion es multi-salto, es necesario que el nodo este despiertoperiodicamente para reenviar datos de otros nodos, aunque no tenga infor-macion propia para transmitir.

2.2.2. Recoleccion de datos y reporte periodico

Patron de trafico: ContinuoLatencia: DespreciableVida util: Simple

Esta clase incluye a las aplicaciones de monitoreo. Por ejemplo, el moni-toreo de cultivos o ganado, o del ambiente (temperatura, humedad y luz) deun edificio. En estos casos, cada sensor produce una cantidad de informa-cion de manera periodica y constante que debe ser encaminada al sumidero.Tambien, el sumidero podrıa requerir el computo distribuido de alguna fun-cion de las lecturas de los nodos sensores. Esta agregacion de datos puedeser implementada utilizando una topologıa de red jerarquica o plana, endonde la comunicacion es multi-salto y los nodos intermedios van agregandola informacion salto a salto.


Para esta clase de aplicacion, es importante que las rutas permitan op-timizar la vida util de la red [25].

Al haber un flujo constante de informacion, la mayor parte de la energıadel nodo se gasta en la transmision. Por ello es importante que las rutassean seleccionadas de manera de maximizar la vida util de la red. En estesentido, en distintos trabajos se ha comprobado que seleccionar la ruta querequiere menor energıa total de transmision, hace que se agote la baterıade los nodos a lo largo del camino, pudiendo acortar el tiempo que la redfunciona sin particionarse. Por ello, se buscan mecanismos para balancear lacarga del encaminamiento entre los nodos.

En redes de topologıa jerarquica de cluster, la cabecera de cluster reco-lecta datos de los nodos y los envıa agregados al sumidero. Ası, el gasto deenergıa en transmision es mucho mas alto en la cabecera que en los nodos,y para uniformizar el patron de agotamiento de energıa, el rol de cabecerapuede rotarse. Tambien, pueden utilizarse nodos con mejores capacidadespara llevar a cabo las tareas de cabecera, simplificando las funciones en losnodos ordinarios, que ya no podrıan cumplir tambien ese rol. Para transmi-tir a la cabecera, los nodos podrıan utilizar comunicacion multi-salto o desalto-unico, y un esquema hıbrido permite, nuevamente, agotar la energıade la red de manera mas uniforme.

31

2.2. TIPOS DE APLICACION

2.2.3. Consulta iniciada por sumidero

Patron de trafico: EpisodicoLatencia: ModeradaVida util: Compleja

En este escenario, el sumidero puede requerir consultar la medicion deun conjunto de sensores en un determinado momento. Esto permite extraerinformacion con diferentes grados de resolucion, de diferentes regiones enel espacio. Desde el punto de vista del encaminamiento, se requiere poderenviar datos a un conjunto dinamico de nodos. Para poder consultar selecti-vamente un subconjunto de datos, el sumidero debe poder expresar el interescon algun esquema de metadatos de la informacion. La consulta se difundea un grupo de nodos que buscaran coincidencias y eventualmente enviaransus respuestas.Una funcionalidad adicional de las redes basadas en consulta puede ser lareprogramacion de nodos, si la mayor parte del hardware puede ser contro-lado por software, las actividades de generacion de datos del nodo puedenser modificadas por el sumidero.


En este tipo de aplicaciones, el esquema de direcciones debe permitirhacer broadcast a una region espacial en particular [25]. Tıpicamente, elsumidero requerira consultar un subconjunto de nodos localizados en unaregion especıfica, en lugar de un nodo en particular, de lo que se deriva la ne-cesidad de un mecanismo de direccionamiento especial que lo permita. Parapoder difundir una consulta a un grupo de nodos, el encaminamiento debepoder soportar el broadcast limitado a una region, utilizando informacion deposicion.

2.2.4. Seguimiento

Patron de trafico: Episodico, ContinuoLatencia: EstrictaVida util: Compleja

El seguimiento con redes inalambricas de sensores tiene muchas apli-caciones en la vigilancia militar o de frontera, donde interesa rastrear elmovimiento de objetos. En medio ambiente las aplicaciones incluyen el se-guimiento de patrones de movimiento de pequenos animales.Esta clase de aplicaciones combinan caracterısticas de las tres anteriores.Cuando se detecta un evento, debe ser prontamente reportado al sumide-ro. El sumidero puede iniciar consultas a la region en donde el evento fuedetectado, para poder calcular la trayectoria del objeto. Una cuestion de

32


diseno importante es determinar un balance entre el costo de calcular rutasal vuelo o mantener alguna topologıa para facilitar el proceso de seguimiento.

El posicionamiento tiene incidencias en dos niveles: el sensor debe deter-minar su propia posicion, para luego colaborar en la localizacion del objetivoen varios momentos. El esquema de posicionamiento debera balancear robus-tez y eficiencia, es decir, la exactitud de la posicion al menor costo energeticoposible.

Para el seguimiento se ha propuesto la utilizacion de clusteres dinamicos,formados por agrupaciones de nodos, segun sus mediciones. Las cabecerascolaboran de manera de activar el cluster mas proximo al objetivo para larecoleccion de datos.


Para facilitar la deteccion del objetivo, nuevamente, la estrategia de en-caminamiento debera estar basada en la posicion geografica de los nodos, enlugar de sus identidades de hardware.

2.2.5. Resumen

A continuacion se resumen las caracterısticas de cada clase de aplicacionWSN presentada en [25], utilizando algunas de las dimensiones taxonomicasde [26].

Tipo de aplicacion Vida util Latencia Ancho de banda

Deteccion y reporte de eventos Compleja Estricta Episodico

Recoleccion de datos y reporte pe-riodico

Simple Baja Continuo

Consulta iniciada por sumidero Compleja Moderada Episodico

Seguimiento Compleja Estricta Episodico

Cuadro 2.2: Resumen de tipos de aplicacion y caracterısticas

Las figuras 2.6a y 2.6b corresponden a tipos de aplicaciones ofrecidaspor una companıa real, y fueron obtenidas de su sitio web [3].

2.3. Estandares de comunicacion

2.3.1. Bluetooth y Wi-Fi

Los sistemas Bluetooth y Wi-Fi (IEEE 802.11) son dos opciones muypopulares y comercialmente disponibles cuya utilizacion en redes inalambri-cas de sensores ha sido evaluada.

33

2.3. ESTANDARES DE COMUNICACION

(a) Deteccion de incendios en un bosque (b) Monitoreo de cultivos

Figura 2.6: Tipos de aplicacion

Bluetooth es un sistema disenado como una red inalambrica de area per-sonal, su principal aplicacion es la conexion de dispositivos a una compu-tadora personal. Se han hecho prototipos de redes de sensores basadas enBluetooth, los nodos organizados en picoredes con un nodo maestro y unmaximo de siete nodos esclavos activos. El maestro elije la secuencia dehopping que deben seguir los esclavos. Puede haber varios nodos esclavos enestado pasivo en la picored, el maestro interroga los nodos esclavos activoscontinuamente.Hay varios inconvenientes de la aplicacion de Bluetooth a redes inalambricasde sensores [22]:

la necesidad de tener un nodo maestro constantemente, con el costode interrogar sus esclavos

la cantidad limitada de esclavos por picored que soporta

para el caso de redes de sensores densas, se necesitarıa un numeroenorme de nodos maestros

un esclavo activo debe permanecer siempre encendido, ya que no puedepredecir cuando sera interrogado por el maestro

un esclavo pasivo debe postularse con el maestro para cambiar a activo,y si ya hay siete nodos activos, sera rechazado

se requiere que cada nodo pueda asumir el rol de maestro o esclavo,agregando una complejidad considerable

los rapidos saltos de frecuencia requieren una sincronizacion estrictaentre los nodos de la picoreds

En la familia de protocolos IEEE 802.11 se especifican varios tipos decapa fısica que comparten un unico protocolo de capa MAC (DCF). En

34


terminos generales, el estandar de protocolos IEEE 802.11 tiene los siguien-tes inconvenientes [22]:

requiere que los nodos esten permanentemente escuchando el medio,ya que podrıan tener que recibir un frame en cualquier momento

los nodos deben sobre-escuchar paquetes RTS y CTS para ajustar sustemporizadores NAV adecuadamente

si bien se proveen algunas funcionalidades de ahorro de energıa, engeneral esta orientado a altas tasas transmision, y los tranceptoresdisponibles requieren una cantidad de energıa que es ordenes de mag-nitud mayores que lo aceptable en aplicaciones de redes de sensores

es un protocolo de salto-unico para redes ad-hoc, cuando lo comun enredes de sensores es el encaminamiento de salto-multiple

2.3.2. Estandar IEEE 802.15.4-2006

El estandar IEEE 802.15.4, finalizado en el 2003 por el Instituto de In-genieros Electricos y Electronicos, define la capa fısica y MAC para redesinalambricas de area personal (WPAN ) de baja tasa de transmision. A ve-ces se confunde el estandar con ZigBee, otro estandar que agrega serviciosde red, seguridad y aplicacion, y esta basado en los servicios ofrecidos porIEEE 802.15.4. Los tipos de aplicacion a los que esta orientado el estandarcomprenden las redes inalambricas de sensores, la domotica, las redes hoga-renas, la conexion de dispositivos a una computadora personal, seguridad,etc. La mayorıa de estas aplicaciones requieren tasas de transmision bajasa medias, retardos de transmision moderados con requerimientos no muyestrictos, y es muy deseable la reduccion al mınimo del consumo de energıaen los nodos.

Capa fısica

El diseno de la capa fısica esta dirigido por los requerimientos de bajocosto y eficiencia, de aplicaciones de control y monitoreo sensibles al costo yde baja tasa de transmision [4]. Bajo el estandar 802.15.4, se pueden operarenlaces inalambricos en tres bandas de frecuencias no licenciadas: 858 MHz,902 a 928 MHz, y 2.4 GHz. Basados en estas frecuencias, se definen tresmedios fısicos:

1. DSSS (Direct Sequence Spread Spectrum) usando modulacion BPSKen la banda 868 MHz a una tasa de 20 Kbps (unico canal)

35


2. DSSS usando modulacion BPSK en la banda de 915 MHz a una tasade 40 Kbps (10 canales)

3. DSSS usando modulacion O-QPSK en la banda 2.4 GHz a una tasade 250 Kbps (16 canales)

El estandar IEEE 802.15.4-2007 es una enmienda que especifica las si-guientes alternativas adicionales de capa fısica (PHY) [28]:

1. Ultra-wide band (UWB) a frecuencias 3 a 5 GHz, 6 a 10 GHz, y < 1GHz

2. CSS (Chirp Spread Spectrum) a 2450 MHz

Figura 2.7: Estructura del paquete de capa fısica IEEE 802.15.4

La estructura del frame IEEE 802.15.4, ilustrada en la figura 2.7 (obte-nida de [4]), comprende los siguientes campos:

1. preambulo: 32 bits que se utilizan para sincronizacion de sımbolos

2. delimitador: 8 bits que se utilizan para sincronizar la recepcion delframe

3. cabecera: 8 bits que especifican la longitud de la unidad de datos(PSDU, PHY Service Data Unit)

4. datos: hasta 127 bytes de datos

Capa de acceso al medio

Arquitectura de red

El estandar distingue dos tipos de nodo [4]:

36


FFD (Full Function Device)dispositivo de funcionalidad completa, que puede operar como coordi-nador de la red PAN, coordinador a secas, o dispositivo

RFD (Reduced Function Device)dispositivo de funcionalidad reducida, solo opera como dispositivo

Un dispositivo debe estar asociado a un nodo coordinador FFD forman-do una red de topologıa estrella. Los coordinadores pueden comunicarsepunto a punto y varios coordinadores pueden formar una red PAN. La redse identifica con un identificador PAN de 16-bits y uno de sus coordinadoreses designado como coordinador PAN.

El coordinador:

mantiene la lista de dispositivos asociados

asigna direcciones cortas a sus dispositivos asociados

en modo ranurado, transmite regularmente el beacon (mensaje baliza),anunciando el identificador de red PAN, y las ranuras reservadas

intercambia frames de datos con dispositivos y con coordinadores

Modo ranurado (beaconed mode)

En modo ranurado, el coordinador de la red estrella organiza el accesoal canal y la transmision de datos especificando un superframe. El super-frame describe un ciclo de actividades que se repite en forma periodica. Elcoordinador arranca cada superframe transmitiendo el frame de senaliza-cion (beacon packet), que incluye la especificacion del superframe, conla duracion de cada actividad.

Figura 2.8: Superframe de IEEE 802.15.4 CSMA ranurado

Como se observa en la figura 2.8 (obtenida de [4]), el superframe se divideen dos perıodos, cuya duracion es configurable:

37


1. Perıodo activoSe divide en 16 ranuras de tiempo (de duracion configurable), la pri-mera ocupada en transmitir el frame de senalizacion, y las restantesse reparten en dos fases: CAP (Contention Access Period), el accesoes por competencia y GTSs (Guaranteed Time Slots), el acceso es ex-clusivo por ranuras de tiempo garantizadas. El coordinador debe estaractivo durante la totalidad del perıodo, y los dispositivos asociadosestan activos en las ranuras de tiempo GTS que le fueron asignadas.En la fase CAP el nodo tambien puede apagar el tranceptor si no tienenada que transmitir o recibir.

2. Perıodo inactivoDurante este perıodo, todos los nodos incluyendo el coordinador pue-den apagar el tranceptor y ponerse a dormir. Los nodos deberan des-pertar justo antes de la transmision del frame de senalizacion pararecibirlo.

Los coordinadores hacen mucho mas trabajo que los dispositivos, el pro-tocolo esta disenado para una topologıa de sensores restringidos en energıaque se comunican con nodos de energıa no acotada.

El coordinador asigna ranuras de tiempo garantizadas a los dispositivosque han enviado paquetes de solicitud durante la fase CAP. Una marca enla solicitud indica si el GTS es para transmitir al coordinador o para recibirdatos del coordinador, y otro campo indica la cantidad de ranuras de tiempocontiguas que se desean reservar.

La respuesta del coordinador ocurre en dos pasos. El primero es unaconfirmacion inmediata de la recepcion de la solicitud. Al recibir la confir-macion, el dispositivo debe rastrear los beacons por un determinado tiempo.Cuando el coordinador tiene suficientes recursos para otorgar las ranurassolicitadas, inserta un descriptor GTS en el siguiente beacon. El descriptorcontiene la direccion del nodo solicitante, y la cantidad y posicion de lasranuras otorgadas dentro de la fase GTS. El dispositivo puede utilizar lasranuras asignadas cada vez que son anunciadas por el coordinador. Asimis-mo, las ranuras permanecen asignadas hasta que el dispositivo solicita suliberacion con un frame de control especial, o el coordinador detecta queno han sido utilizadas durante una determinada cantidad de superframes ylas cancela con un descriptor GTS que contiene una posicion invalida. Siel coordinador no tiene los suficientes recursos, tambien transmite un des-criptor GTS especificando una posicion invalida y los recursos que sı estandisponibles, pudiendo el dispositivo renegociar el GTS.

La transmision de informacion del dispositivo al coordinador ocurre enranuras GTS, o en la fase CAP utilizando CSMA-CA ranurado. En la direc-cion opuesta, la transmision de informacion del coordinador al dispositivoocurre tambien en ranuras GTS, y si no se han reservado, se hace de lasiguiente manera:

38


1. el coordinador anuncia que tiene datos para un dispositivo incluyendola direccion del dispositivo en el campo pending address field del framebeacon

2. cuando el dispositivo encuentra su direccion en el campo, envıa unapeticion de datos durante la fase CAP

3. el coordinador responde con un acuse de recibo y luego envıa el dato

4. cuando el dispositivo recibe el acuse, deja el tranceptor encendido y seprepara para la recepcion del dato

5. al recibir los datos, el dispositivo responde con un acuse de recibo

6. si el dispositivo no recibe el acuse, repite la peticion durante los si-guientes superframes o apaga el tranceptor hasta el siguiente beacon

Para la transmision de datos del dispositivo al coordinador durante lafase CAP se usa el protocolo CSMA. Para evitar colisiones, no se utilizael esquema RTS/CTS (Request To Send / Clear To Send), sino que usanretardos al azar. Las ranuras de tiempo de la fase CAP estan a su vez subdi-vididas en ranuras mas pequenas, llamadas perıodos de backoff. Un perıodode backoff dura lo mismo que la transmision de 20 sımbolos. El dispositivoque desea transmitir espera al comienzo del siguiente perıodo de backoff y apartir de allı espera un numero al azar (del intervalo [0, 2BE−1]) de perıodossiguientes. Luego, en cada perıodo censa el medio (ejecutando la operacionCCA, Clear Channel Assesment), durante dos perıodos seguidos. Si las dosveces el canal esta ocioso, ha ganado la competencia y comienza la transmi-sion de los datos. Si alguna de las veces que el dispositivo censa el medio elcanal esta ocupado, comienza el proceso nuevamente con la espera, eligien-do un numero al azar de perıodos de un intervalo mayor (incrementando elexponente BE). Si es necesario repetir el proceso mas de una determinadacantidad de veces, el dispositivo descarta el frame y declara que se ha pro-ducido una falla.

Modo no ranurado (nonbeaconed mode)

En el modo no ranurado el coordinador no transmite frames beacon, nihay fase GTS. Todos los paquetes de los dispositivos se transmiten utilizandoCSMA-CA no ranurado, por lo que no hay sincronizacion con perıodos debackoff, y solo ejecuta una operacion CCA antes de transmitir. Si el canalesta ocioso, el dispositivo transmite los datos. Los dispositivos pueden seguirsu propio programa de sueno, despertando para transmitir al coordinadoro para recibir datos del coordinador. El dispositivo envıa la solicitud dedatos usando CSMA-CA no ranurado, y el coordinador responde el acuse

39


de recibo inmediatamente. Luego, cuando el coordinador tiene datos parael dispositivo, los transmite usando CSMA-CA y el dispositivo responde elacuse inmediatamente. En este modo, el ciclo de recepcion depende de laaplicacion.

2.3.3. ZigBee

ZigBee [29] es un estandar de comunicacion orientado a aplicaciones cu-yos requerimientos principales son bajas tasas de transmision, bajo costo ylarga duracion de baterıa. Algunos sistemas para los que existen perfiles deaplicacion definidos [30] son:

Domotica

Control remoto (home theatre, media center, etc)

Monitoreo de consumo energetico y de agua en el hogar

Monitoreo de pacientes cronicos no agudos, salud personal y de latercera edad

Los estandares ZigBee son desarrollados por la organizacion ZigBee Allian-ce, conformada por cientos de companıas, y formada en el 2002 como unaorganizacion sin fines de lucro. Algunas empresas promotoras (con el nivel departicipacion mas influyente y representacion en el directorio) son Philips,Emerson y Texas Instruments. Las empresas participantes son numerosas,entre ellas se encuentran AT&T, Cisco, Huawei, Indesit, LG, Samsung, Sie-mens, Whirpool, Intel, GE.

El estandar ZigBee esta definido en capas de protocolos, basadas en elmodelo de referencia OSI. Adoptando la capa fısica (PHY) y de acceso almedio (MAC) IEEE 802.15.4, define capas de servicios de red, aplicacion yseguridad.

La figura 2.9 (obtenida del estandar [6]) esquematiza las capas de laarquitectura ZigBee.

Las caracterısticas fısicas de la red estan determinadas por la capa fısicaIEEE 802.15.4 descripta en la seccion 2.3.2.

Arquitectura de red

Los roles de los nodos en ZigBee se corresponden con los del estandarIEEE 802.15.4, aunque tienen diferente denominacion:

Coordinador ZigBee (coordinator) (Coordinador PAN IEEE 802.15.4)

40


Figura 2.9: Capas de protocolos de ZigBee

Encaminador ZigBee (router) (Coordinador IEEE 802.15.4)

Dispositivo Final ZigBee (end device) (Dispositivo IEEE 802.15.4)

Se soportan las topologıas de red estrella o punto a punto, como seespecifica en IEEE 802.15.4.

Figura 2.10: Red ZigBee estrella

En la red estrella, esquematizada en la figura 2.10 (obtenida de [29]),todos los dispositivos de la red se comunican a traves del coordinador, queal activarse selecciona un identificador de red unico dentro de su alcance deradio y establece la red.

En la red punto a punto, todos los dispositivos pueden comunicarse di-rectamente entre sı. Los dispositivos de funcionalidad reducida participan

41


Figura 2.11: Red ZigBee malla

de la red comunicandose con un coordinador o un encaminador ZigBee, perono encaminan mensajes. En este caso, el encaminador tambien puede tomarel rol de coordinador.La red punto a punto puede tomar diferentes formas:

MallaNo hay restriccion sobre los dispositivos que pueden comunicarse entresı (figura 2.11, obtenida de [29]).

ArbolEl coordinador establece la red inicial. Los encaminadores forman lasramas y los dispositivos finales, que no encaminan datos, las hojasdel arbol. Los encaminadores pueden agregar mas nodos a la red, masalla de la red inicial.

Capa de aplicacion y seguridad

La capa de aplicacion es la mas alta en la pila ZigBee, y aloja los ob-jetos de aplicacion. Los fabricantes desarrollan objetos de aplicacion parapersonalizar los dispositivos para su aplicacion. Estos objetos controlan yadministran las capas de protocolos del dispositivo. El estandar ZigBee hadefinido perfiles de aplicacion, un conjunto de acuerdos sobre formatos demensajes y acciones de procesamiento para promover la interoperabilidadentre diferentes vendedores [30].

ZigBee tambien provee mecanismos para garantizar la confidencialidady autenticidad de la informacion transmitida. El estandar IEEE 802.15.4 so-porta el uso de cifrado AES (Advanced Encryption Standard) de los paquetessalientes. La autenticacion de los datos se puede comprobar incluyendo uncodigo de integridad de mensaje (MIC) en cada frame.

42


Capa de red

La capa de red es responsable de la administracion de la red y del enca-minamiento. El coordinador establece la nueva red, selecciona la topologıa,y asigna direcciones al resto de los dispositivos. Los coordinadores y enca-minadores son los que descubren y mantienen las rutas en la red.

La capa de red mantene los siguientes 3 tipos de tablas:

1. encaminamiento

2. descubrimiento de ruta

3. nodos vecinos

Las rutas se mantienen en tablas de encaminamiento, que se utilizan paradeterminar el siguiente nodo al que se debe reenviar un mensaje, camino aun destino particular.

Campo Tamano Descripcion

Direccion destino 2 bytes La ruta conduce a este destino.

Estado 3 bits Activo, descubrimiento en curso,descubrimiento fallido, inactivo, va-lidacion en curso.

Muchos a uno 1 bits Si el destino ha solicitado encami-namiento muchos a uno, toma valor1.

Grabacion de ruta re-querida

1 bit Si esta prendido, la ruta seguida porel paquete sera grabada y entregadaal dispositivo de destino.

Flag de id de grupo 1 bit Esta prendido si la direccion de des-tino es un id de grupo.

Direccion de siguien-te nodo

2 bytes La direccion de 16 bits del siguientenodo en la ruta.

Cuadro 2.3: Campos de la tabla de encaminamiento ZigBee

En la tabla 2.3 se listan los campos de cada entrada de la tabla deencaminamiento.

43


Campo Tamano Descripcion

Id de peticion de ruta 1 byte El numero de secuencia que identi-fica la peticion de ruta. Cada rutase identifica por un id unico de pe-ticion.

Direccion origen 2 bytes 16 bits de direccion del dispositivoorigen, quien inicia la peticion deruta.

Direccion de emisor 2 bytes 16 bits de direccion del dispositivoemisor, el que ha enviado la peti-cion de ruta en favor del dispositivoorigen. Esta direccion es utilizadapara enviar la respuesta de ruta aldispositivo origen. Si la misma pe-ticion de ruta es recibida de multi-ples emisores, la direccion del emi-sor con el costo total de ruta masbajo sera mantenida.

Costo de reenvıo 1 byte El costo de ruta acumulado desdeel dispositivo origen. Este campo seactualiza cuando se envıa la peti-cion de ruta hacia el dispositivo des-tino.

Costo residual 1 byte El costo de ruta acumulado desdeeste dispositivo al dispositivo des-tino. Este campo se actualiza cuan-do se envıa la respuesta de ruta aldispositivo origen.

Cuadro 2.4: Campos de la tabla de descubrimiento de ruta ZigBee

44


Campo Descripcion

Direccion extendida 64 bits de direccion IEEE 802.15.4

Direccion de red 16 bits de direccion de red

Tipo de dispositivo Coordinador, encaminador o dispo-sitivo final ZigBee

En ocio, receptor en-cendido

Si el dispositivo mantienen encen-dido el receptor cuando esta ocioso,este campo toma valor verdadero.

Relacion Este campo determina la relacioncon el vecino. Padre, hijo, hermano,hijo anterior o ninguna.

Falla de transmision Un valor alto indica que muchos delos intentos de transmision anterio-res fallaron.

LQI La calidad de enlace estimada

Marca de tiempodel ultimo frame desenalizacion recibido

Opcional.

Padre potencial Si el vecino es un padre potencial,opcional.

Cuadro 2.5: Campos de la tabla de nodos vecinos ZigBee

Otra tabla utilizada en el encaminamiento es la tabla de descubrimientode ruta (tabla 2.4). El contenido de esta tabla es temporario y expira cadacierta cantidad de milisegundos.

El costo de ruta se calcula como la suma de los costos de cada enlaceque forma parte de la ruta:

C(P ) =L−1∑i=1

C(li)

L = longitud de la rutaP = ruta (path)li = enlace i (link)

La ruta con el menor costo tiene la mejor chance de entrega exitosa depaquetes. El estandar ZigBee calcula el costo de enlace como un entero enel intervalo [0..7] con la siguiente formula [6]:

C(l) =( 7,

min(7,round( 1(pl)

4 ))

)El costo es o bien constante (7), o bien el mınimo entre 7 y el recıproco depl. Se define a pl como la probabilidad de entrega con buen exito si se utiliza

45


el enlace l.

El estandar menciona que los implementadores pueden optar por utilizarun costo constante de 7 o un valor que refleje la probabilidad pl de recepcion,especıficamente el recıproco de esa probabilidad (a mayor probabilidad, me-nor costo), que a su vez refleja la cantidad esperada de intentos requeridospara pasar un paquete cada vez que se utiliza el enlace. Se plantea la cues-tion de como estimar o medir pl, y se deja abierta a los implementadores,pero se sugiere como manera mas directa y siempre disponible, la estima-cion basada en la promediacion del indicador LQI (Link Quality Indicator)(por frame) que provee el estandar MAC y PHY IEEE 802.15.4-2003. Sise utiliza algun otro metodo de estimacion de pl, el costo inicial debe estarbasado en el LQI promedio. La medida LQI es una caracterizacion de la ca-lidad del paquete recibido [31], que se implementa utilizando una estimacionde la intensidad recibida (ED, Energy Detection), una estimacion de la rela-cion senal/ruido (SNR, Signal to Noise Ratio), o una combinacion de ambos.

Como el metodo para calcular el costo sugerido no tiene en cuenta elconsumo de energıa, el encaminamiento basico no puede considerarse cons-ciente de la energıa [29]. La eficiencia del encaminamiento, y la definiciondel costo del enlace, dependen de la definicion de vida util de la red, queesta determinada por el tipo de aplicacion.

El dispositivo ZigBee mantiene tambien una tercera tabla de nodos ve-cinos, que contiene informacion sobre los dispositivos que se encuentrandentro del alcance, actualizandose cada vez que se recibe un paquete. Cadaentrada tiene campos requeridos y campos opcionales, algunos listados enla tabla 2.5.

La aplicacion puede solicitar el descubrimiento de ruta para tres patronesde comunicacion [29]:

unicastUna ruta unicast comienza en un dispositivo y termina en otro.

multicastEl descubrimiento multicast se realiza si la direccion destino es unidentificador de grupo.

muchos a unoSi la aplicacion no provee una direccion destino, se inicia el descubri-miento muchos a uno, donde el dispositivo solicitante es el sumidero.

Si la aplicacion solicita descubrimiento de ruta para la direccion broad-cast, la peticion se toma como invalida.

46


El descubrimiento unicast se realiza de la siguiente manera:

1. Un dispositivo O (origen) requiere hallar una ruta a un dispositivo D(destino), entonces inicia el descubrimiento emitiendo por broadcast elcomando de peticion de ruta, que contiene el identificador de peticionde ruta, la direccion destino, y el costo de la ruta, inicialmente en cero.

2. El comando de peticion de ruta es recibido por todos los dispositivosdentro del alcance de O. Si el dispositivo es un dispositivo final, ignorael comando. Si es un encaminador, lo procesa.

3. El encaminador E que recibe el comando y no tiene la tabla de enca-minamiento llena, agrega el costo de O a E al comando de peticion deruta y lo vuelve a emitir por broadcast. Ademas, agrega el identificadorde peticion de ruta y la direccion origen a la tabla de descubrimientode ruta, si no existen.

4. Si el encaminador E que recibe el comando tiene la tabla de encamina-miento llena, y la direccion destino no existe en la tabla, asumiendo quese utiliza encaminamiento jerarquico, y la peticion de ruta proviene deuna ruta valida, E reenviara el comando a lo largo del arbol.

5. Si E tiene la tabla de encaminamiento llena, y la peticion de ruta noproviene de una ruta valida, se ignora.

6. Cada encaminador o coordinador C que recibe la peticion, la vuelvea emitir por broadcast. Si la recibe por duplicado, actualiza la tablade descubrimiento de ruta con el costo mas bajo desde el dispositivoemisor hasta C.

7. El reenvıo continua hasta que el dispositivo final D recibe la peticion.De entre todas las peticiones de ruta que recibe D, selecciona la rutaoptima segun el costo acumulado con que llegan, y emitira el comandorespuesta de ruta.

ZigBee tambien soporta encaminamiento en origen (source routing), don-de el nodo origen especifica la lista de dispositivos por los cuales debe enca-minarse el paquete, y cuando un encaminador lo recibe, simplemente obtienela direccion del siguiente nodo de la lista.

2.3.4. WirelessHART

WirelessHART (Wireless Highway Addressable Remote Transducer) esel primer estandar abierto de comunicacion inalambrica especıficamente di-senado para aplicaciones de control de procesos, oficialmente liberado en elano 2007 [32].

47


Conceptualmente, las redes WirelessHART son un tipo especial de redesinalambricas de sensores. A diferencia de las redes de sensores genericas, queasumen que los sensores son desplegados al azar y de manera abundante, eldespliegue de las redes WirelessHART es preciso y con redundancia limita-da. Los nodos WirelessHART estan conectados a dispositivos de campo pararecolectar datos ambientales especıficos de los procesos, por ejemplo, velo-cidades de flujo, niveles de fluido, o temperaturas. Una lectura de un sensorquiza no puede reemplazarse por la lectura de otro sensor cercano. Las re-des genericas son auto-configurables y no tienen requerimientos estrictos detiempo y confiabilidad, como sı lo requieren las aplicaciones inalambricasindustriales.

Capas WirelessHART

Figura 2.12: Pila de protocolos WirelessHART

La arquitectura de WirelessHART, de acuerdo con el modelo de referen-cia OSI, se muestra en la figura 2.12 (obtenida de [32]). La pila de protocoloscomprende cinco capas: fısica, enlace, red, transporte y aplicacion.

La capa fısica esta mayormente basada en la capa fısica DSSS 2.4 GHzdefinida en el estandar IEEE 802.15.4-2006, operando en la banda ISM (In-dustrial, scientific and medical) de uso no licenciado 2400-2483.5 MHz, conuna tasa de transmision de 250 Kbits/s y 16 canales con 5 MHz de separa-cion entre cada canal adyacente.

48


La capa de enlace es propia y opera de manera sincronizada, con ra-nuras estrictas de 10 ms y tecnologıa TDMA (Time-Division MultiplexedAccess) para proveer un sistema de comunicacion determinıstico y libre decolisiones. El superframe comprende un grupo de ranuras consecutivas y serepite sobre la base de su perıodo (que es la suma de la duracion del conjuntode ranuras).

Se utiliza el concepto de transacciones que ocurren en una ranura detiempo, descriptas por el vector:

(FID, I,T,SA,DA,COFF)

FID = Identificador de superframeI = Indice de ranura dentro del superframeT = Tipo de ranura (transmision, recepcion, ocio)SA = Direccion origenDA = Direccion destinoCOFF = Desplazamiento dentro del canal, canal logico para usar en latransaccion

WirelessHART tambien introduce el concepto de lista negra de canales,el administrador puede deshabilitar canales que sufren constantes interfe-rencias.

Para soportar el salto de frecuencias, cada dispositivo mantiene una listade canales activos. El canal verdadero se calcula a partir numero absoluto deranura y el desplazamiento dentro del canal. El numero absoluto de ranuratoma valor cero al iniciarse la red, y se incrementa constantemente.

La capa de enlace mantiene una coleccion de tablas [33]:

tabla de superframeAlmacena atributos del superframe.

tabla de enlaceAlmacena atributos de cada enlace.

tabla de vecinosAlmacena la lista de dispositivos dentro del alcance de radio.

tabla del grafoAlmacena la lista nodos siguientes legales para propagar un paquetehacia su destino.

Las capas de red y transporte colaboran para proveer comunicacionconfiable y segura extremo a extremo. La capa de aplicacion define varios

49


comandos que procesa para generar respuestas, tipos de datos y reportes deestado del dispositivo.

WirelessHART ademas incluye servicios de seguridad en el enlace ya nivel de red. La capa MAC provee integridad nodo a nodo usando MIC(codigo de integridad de mensaje). A nivel de red, los dispositivos y el admi-nistrador de red emplean varias claves para garantizar la confidencialidad eintegridad de las conexiones extremo a extremo: publicas, de red, de union,de sesion. El dispositivo y el administrador de red son dos de los tipos denodo WirelessHART, descriptos en la siguiente seccion.El dispositivo utilizara la clave de union para generar el MIC del paquetede red y encriptar la peticion de union, y la clave publica para generar elMIC de enlace. Luego de ser autenticado, el administrador de red creara unaclave de sesion que utilizaran para comunicarse. Para el trafico normal, losdatos del frame (enlace) se autentican con la clave de red y en la capa dered el paquete se autentica y encripta con la clave de sesion.

Arquitectura de red y encaminamiento

Figura 2.13: Malla WirelessHART

Una red WirelessHART se compone de los siguientes nodos (ver figu-ra 2.13 obtenida de [34]):

50


Dispositivo de campoConectados a un proceso de planta.

Dispositivo de manoComputadora portatil compatible con WirelessHART, utilizada paraconfigurar dispositivos, realizar diagnosticos y calibraciones.

GatewayConecta aplicaciones de computadora con dispositivos de campo.

Administrador de redResponsable de configurar la red, programar y mantener la comunica-cion entre los dispositivos WirelessHART.

Para soportar la topologıa de red malla, todos los dispositivos deben po-der reenviar paquetes en favor del resto.

Se definen dos protocolos de encaminamiento:

Encaminamiento por grafoUn grafo puede pensarse como una coleccion de caminos dirigidos, queconecta los nodos de la red. Una unica red puede tener multiples grafos,y algunos pueden solaparse. El administrador de red crea las rutasasociadas a cada grafo y las almacena en cada dispositivo de la red.Para enviar un paquete, el dispositivo origen especifica un identificadorde grafo en su encabezado. Todos los dispositivos camino al destinodeben ser preconfigurados con la informacion de encaminamiento, parapoder determinar el siguiente nodo al cual reenviar el paquete.

Encaminamiento en origenComplementa el encaminamiento por grafo para asistir al diagnosticode la red. El dispositivo origen especifica la lista de dispositivos porlos cuales debe viajar el paquete en el encabezado. Cada dispositivoutiliza la lista para determinar el siguiente nodo al cual debe reenviarel paquete.

La capa de red mantiene tambien un conjunto de tablas propias:

tabla de sesionCada entrada identifica una sesion segura entre dos dispositivos.

tabla de transporteUtilizada para dar soporte a transacciones extremo a extremo, con con-firmacion. Junto con un numero de secuencia se almacena la ultimapeticion o respuesta, para poder reenviarlos cuando expira el tempo-rizador.

51


tabla de encaminamientoPara cada destino pueden existir mas de una entrada en esta tabla,con un identificador de grafo diferente.

Basandose en la informacion de enlace provista por cada nodo, el admi-nistrador de red crea el grafo total de la red, siguiendo las siguientes reglasen el orden en que se enumeran:

1. minimizar la cantidad de saltos

2. encaminar a traves de dispositivos conectados a la red electrica si esposible

3. utilizar la intensidad de senal para seleccionar las mejores rutas

4. utilizar una combinacion de intensidades de senal ponderadas paraseleccionar entre rutas alternativas

5. podar la cantidad de vecinos a 4 nodos o menos

Luego de crear el grafo total, el administrador crea un grafo que describerutas desde cada dispositivo hasta el gateway, un grafo de broadcast desde elgateway hasta cada dispositivo, grafos desde el gateway a cada dispositivoindividualmente. El administrador de red asigna ranuras de tiempo a cadadispositivo de acuerdo con los grafos derivados.

Comparacion con ZigBee

Los principales argumentos en contra de la utilizacion de ZigBee paraaplicaciones industriales son [35]:

ZigBee utiliza un unico canal, lo que lo hace muy susceptible a interfe-rencias intencionales o no. La grave atenuacion selectiva de frecuenciadebido al ambiente rico en metales propio de las plantas podrıa, po-tencialmente, detener toda comunicacion. El canal unico aumentara lainterferencia con otros sistemas, tales como una red local inalambrica,y aumentara el retardo al crecer la red, ademas de producirse una ma-yor cantidad de colisiones y retransmisiones. En este sentido, Wireless-HART es mas robusto, ya que utiliza saltos de frecuencia y retransmi-siones en diferente frecuencia para reducir los efectos de interferencias.

ZigBee no mantiene diversidad de rutas, si se rompe un enlace, se debeestablecer una nueva ruta de origen a destino, produciendo retardos y

52


costos indirectos, y el descubrimiento de ruta puede llegar a consumirtodo el ancho de banda en ambientes con rutas inestables. El encami-namiento por grafo de WirelessHART provee la redundancia de rutaque permite reducir los efectos de enlaces rotos.

Los encaminadores ZigBee con muchos vecinos deben mantener el re-ceptor encendido durante una gran parte del superframe, en la faseCAP por utilizar CSMA/CA. En cambio, los dispositivos Wireless-HART solo mantienen la radio encendida durante las ranuras de tiem-po asignadas.

Aun con las caracterısticas de robustez y confiabilidad mencionadas deWirelessHART para aplicaciones industriales, en [35] se sugiere su utilizacionen procesos lentos y no crıticos.

53


54

Capıtulo 3

Protocolos de red

3.1. Problema del encaminamiento

Uno de los principales desafıos de diseno en WSNs es la comunicacionde datos intentando al mismo tiempo prolongar la vida util de la red, em-pleando tecnicas agresivas de administracion de energıa. En [10] se resumenalgunas cuestiones de diseno que afectan el proceso del encaminamiento:

DespliegueEl despliegue de los nodos depende de la aplicacion y afecta el desem-peno del protocolo. Cuando el despliegue es determinıstico, los datosse encaminan a traves de rutas predefinidas. Cuando es al azar, la es-tructura de red se crea ad hoc y probablemente las rutas se compongande multiples saltos de enlaces inalambricos.

Conservacion de energıaLos nodos solo cuentan con su limitado suministro de energıa paraprocesar y comunicar datos en un ambiente inalambrico, por lo que sedeben buscar maneras de optimizar esas actividades.

Modelo de reporte de datosEl sensado y reporte de datos depende de la aplicacion y sus reque-rimientos temporales, y pueden clasificarse en continuos, por evento,por consulta o hıbridos. En el modelo continuo, los sensores sensan ytransmiten periodicamente. En los modelos de reporte por evento ypor consulta, los sensores reaccionan a un cambio drastico y repentinodel valor sensado por haber ocurrido un evento, o para responder a unaconsulta iniciada por la estacion base. El protocolo de encaminamientoesta fuertemente influido por el modelo requerido.

Heterogeneidad de nodos o enlacesLos nodos pueden ser homogeneos en capacidad o pueden diferir in-

55

3.1. PROBLEMA DEL ENCAMINAMIENTO

cluso en el rol. Por ejemplo, una aplicacion puede requerir una com-binacion de diversos sensores para monitorear temperatura, presion yhumedad del ambiente, detectando movimiento con senales acusticas,y capturando video de objetos en movimiento. Los sensores puedenser desplegados independientemente, o las diferentes funcionalidadespueden ser incluidas en los mismos nodos sensores.

Tolerancia a fallasCuando los nodos fallan, por falta de energıa, dano fısico o interferen-cia, no deberıan afectar el funcionamiento de la red. Los protocolosde acceso al medio y encaminamiento deben formar nuevos enlacesy rutas al sumidero, lo que puede requerir el ajuste de la intensidadde transmision y el encaminamiento de paquetes a regiones de la redde mayor energıa. Pueden requerirse multiples niveles de redundanciadependiendo de los requerimientos de tolerancia a fallas.

EscalabilidadLa cantidad de nodos sensores desplegados en una determinada areapuede ser del orden de los cientos o miles. El esquema de encamina-miento debe ser capaz de operar con una gran cantidad de nodos.

MovilidadMuchas arquitecturas asumen nodos estacionarios, pero algunas apli-caciones requieren nodos y sumideros moviles. Cuando hay movilidad,la estabilidad de la ruta presenta mayor desafıo.

Canal de transmisionLos problemas tradicionales de un canal inalambrico, atenuacion y altatasa de errores, tambien afectan a las redes de sensores. En general elancho de banda requerido es bajo.

ConectividadPor la gran densidad de nodos se espera que la red este altamenteconectada, aunque habra cambios de topologıa debido a fallas en losnodos.

CoberturaCada nodo obtiene una cierta vista del ambiente, limitada en alcancey exactitud.

Agregacion de datosDado que los nodos pueden generar una cantidad importante de infor-macion redundante, la agregacion de datos permite reducir la cantidadde transmisiones. La agregacion es la combinacion de diferentes fuen-tes de acuerdo a una cierta funcion, por ejemplo, mınimo, promedio,

56

CAPITULO 3. PROTOCOLOS DE RED

maximo. Algunos metodos de procesamiento de senales se pueden uti-lizar para combinar senales y reducir su ruido, tecnica que se conocecomo fusion de datos.

Calidad de servicioAlgunas aplicaciones tienen requerimientos temporales y de latencia.Sin embargo, en muchas otras, la conservacion de energıa, relacionadacon la vida util de la red, es considerada mucho mas importante que lacalidad de servicio. Para cumplimentar este requerimiento se requierenprotocolos conscientes de la energıa.

En la literatura y artıculos de investigacion se pueden encontrar variasmaneras de clasificar protocolos para redes inalambricas de sensores, segunlas premisas de diseno con que se definen y los problemas que intentanresolver. Cada paradigma a menudo se describe respondiendo a las siguientespreguntas:

¿Que modelo de red y tipo de aplicacion asume?

¿Como se elige el siguiente nodo en la ruta?

¿Que fases de operacion tiene?

¿Que cuestiones resuelve?

¿Cuales son sus desventajas?

Asimismo, se han propuesto protocolos que no son exclusivos de un pa-radigma, sino que aplican mas de una tecnica, combinandolas de maneraconveniente para algun tipo de aplicacion. Es por ello que, al analizar unprotocolo, probablemente el mismo pertenezca a mas de una categorıa.

A continuacion, se describiran tres de los paradigmas mas mencionadosen las taxonomıas analizadas [36][11][5][10][25][22].

3.2. Encaminamiento jerarquico

3.2.1. Caracterısticas

Los algoritmos de esta clase se caracterizan por establecer una topologıade red jerarquica. La jerarquıa virtual se construye dividiendo la red enniveles, utilizando un criterio conveniente, por ejemplo, por funcionalidad opor ubicacion de los nodos [36]. En la figura 3.1 se esquematiza esta division.El objetivo de la misma es reducir la carga que se produce en el sumiderosi se utiliza una topologıa plana y la densidad de nodos es muy alta, ya que

57

3.2. ENCAMINAMIENTO JERARQUICO

cada dato sensado se comunicarıa directamente a la estacion base. Ademas,en general, los nodos no tienen un alcance de radio muy largo como parapoder llegar al sumidero en un area muy amplia [11]. En una jerarquıa, losnodos colaboran dentro de un cluster para transmitir los datos, utilizandoun esquema multi-salto, permitiendo hacer un uso mas eficiente de la energıadisponible. Ocasionalmente se aprovecha la topologıa para utilizar tambienla tecnica de fusion o agregacion de datos, y el rol de cabecera o de fusionadorpuede ser asignado dentro del cluster teniendo en cuenta el nivel de residualde energıa que posee el nodo.

Figura 3.1: Jerarquıa virtual en una red de sensores

Este tipo de protocolos es adecuado para aplicaciones que requieren untrafico periodico, donde todos los sensores se encuentran sensando el ambien-te a una tasa de tiempo fija, por lo que continuamente se genera informaciona ser enviada a la estacion base o sumidero. Tambien existen algoritmosdentro de este paradigma especialmente disenados para aplicaciones de de-teccion de eventos [11]. El mantenimiento de la topologıa de red tiene uncosto indirecto asociado, pero esta misma jerarquıa permite reducir el traficode mensajes de control para el calculo de rutas, lo que implica un ahorrode energıa. Es recomendable utilizar esta tecnica en aplicaciones en dondese despliega una gran cantidad de nodos y se requiere escalabilidad, ya queen general la jerarquıa se construye dinamicamente, y puede extenderse oadaptarse.

58


El paradigma frecuentemente se ilustra presentando el algoritmo LEACH(Low Energy Adaptive Clustering Hierarchy), aunque haya sido propuestohace ya 10 anos.

3.2.2. LEACH

Introduccion

LEACH es un protocolo que propone el uso de clusteres de nodos per-mitiendo distribuir el consumo de energıa de manera mas uniforme entre lossensores de la red. Se caracteriza por hacer rotar al azar el rol de cabecera decluster. Dentro de un cluster, la cabecera coordina localmente la transmisiony fusion de datos para comprimir la informacion luego transmitida directa-mente a la estacion base [37], reduciendo el ancho de banda requerido. Latopologıa resultante se esquematiza en la figura 3.2 (obtenida de [4]).

Figura 3.2: Topologıa de red en LEACH

Modelo de red

El modelo de red para el cual se desarrolla LEACH comprende cientos omiles de nodos sensores economicos y eficientes en terminos de energıa. Losnodos son homogeneos y se encuentran restringidos en cuanto a la duracionde la baterıa. La calidad de de la informacion se mejora con la utilizacionde un gran numero de nodos. Una estacion base fija recibe la informacionsensada en lugares distantes.

59

3.2. ENCAMINAMIENTO JERARQUICO

Fases de operacion

LEACH opera en rondas. Cada ronda consta de las siguientes cuatrofases:

1. AnuncioAl comienzo, cada cluster decide si se vuelve cabecera dependiendo delporcentaje de cabeceras que debe tener la red (definido a priori) y elnumero de veces que el nodo ya ha tenido el rol. Cada nodo que se eligea sı mismo como cabecera, hace broadcast del anuncio al resto de losnodos, utilizando CSMA. Los nodos que no son cabecera mantienensu radio encendida, y elijen su cabecera sobre la base de la fuerza dela senal recibida de los anuncios que escuchan (eligen la cabecera cuyasenal se recibe con mayor intensidad, porque es la que estarıa mascerca).

2. Armado del clusterLos nodos eligen la cabecera que requiere la menor energıa de trans-mision e informan a la cabecera seleccionada que se haran miembrodel cluster usando el protocolo CSMA.

3. Planificacion del canalUna vez que la cabecera recibe todos los mensajes de nodos miembros,crea un schedule TDMA asignando un perıodo de tiempo de transmi-sion a cada nodo y lo informa a los nodos haciendo broadcast.

4. Transmision de datosCada nodo envıa la informacion durante la franja de tiempo de trans-mision que le fue asignada. Mientras el nodo no esta transmitiendo,puede apagar su radio. Cuando el nodo cabecera recibe los datos detodos los nodos del cluster, puede combinarlos para comprimir la senalque se enviara a la estacion base en una transmision de alta energıa.Luego de un determinado tiempo de transmision, comienza una nuevaronda. Para minimizar el costo indirecto asociado al mantenimientode la jerarquıa, la fase de transmision es mucho mas larga que la dearmado de clusteres.

Rotacion al azar de la cabecera de cluster

A partir del analisis de primer orden del modelo de radio que se rea-liza en [37], para determinados parametros de radio, los protocolos debenintentar reducir las distancias de transmision, pero tambien la cantidad deoperaciones de transmision y recepcion por cada mensaje.Si todos los nodos se comunican directamente con la estacion base, se reque-rira una gran cantidad de energıa de transmision. Por otro lado, si todos losnodos intentan transmitir a la mas baja energıa posible, es decir, al nodo

60


vecino mas cercano, la suma de la energıa consumida en cada salto puedeterminar siendo mayor que la empleada en la transmision directa. Cuandola energıa de transmision es del mismo orden que la de recepcion, la trans-mision directa es mas eficiente a escala global. Pero debe aclararse que deutilizarse transmision directa, los nodos mas distantes de la estacion basemoriran primero (por ejemplo, en la figura 3.1, los nodos en el nivel n).Asimismo, con un encaminamiento de energıa mınima, son los nodos mascercanos a la estacion base los que se agotan primero, porque encaminandatos provenientes de todos los otros nodos de la red (en la figura 3.1, losnodos en el nivel 0).Sobre la base del analisis anterior, se propone agrupar nodos en clusteres,de manera que los nodos que no son cabecera no estan muy distanciados deella, y emplean menos energıa de la necesaria para transmitir directamentea la estacion base. Como el nodo que tiene rol de cabecera sı realiza trans-misiones de alta energıa a la base, LEACH introduce la rotacion del rol alazar.Cada nodo decide si toma el rol de cabecera o no en la ronda n eligiendoun valor al azar entre 0 y 1. Si el valor es menor a un umbral U(n), el nodose vuelve cabecera. En [37] se muestra que existe una porcentaje optimode cabeceras P, tal que se reduce al mınimo posible la energıa disipada enla transmision. Para LEACH, P es 0.05, es decir, en una ronda, el 5 % delos nodos es cabecera. Entonces, se necesitan al menos 1

P = 20 rondas paraque todos los nodos tengan el rol de cabecera una vez. El umbral U(n) sedefine de manera que en la ronda 0 tiene valor P, y el valor se incrementahasta llegar a 1 en la ronda 1

P − 1. Pero una vez que el nodo tomo el rol, nopodra volver a tomarlo por 1

P rondas.

Problemas que resuelve

LEACH es un algoritmo distribuido y no requiere coordinacion de laestacion base ni conocimiento global de la topologıa de red. Es eficiente aldistribuir el consumo de energıa de manera uniforme a lo largo de la red,lo que incrementa la vida util de la misma. Dado que las cabeceras puedencomprimir o fusionar los datos recibidos de los nodos locales, contribuye areducir el trafico global.

Desventajas

En su primera version, la probabilidad de tomar el rol de cabecera notiene en cuenta la energıa residual en el nodo. Ademas, la comunicacion decabecera a estacion base es de salto-unico [11], lo cual en realidad es unalimitacion, ya que en areas amplias puede que el alcance de la radio no seasuficiente.

61

3.3. ENCAMINAMIENTO GEOGRAFICO

3.3. Encaminamiento geografico


A este paradigma pertenecen los algoritmos que utilizan una posiciongeografica o coordenada, real o virtual, para encaminar datos hacia un pun-to en la red, seleccionando como siguiente nodo al vecino que mas cercaeste del destino [36], minimizando la distancia restante que se debe recorrer[22]. En aplicaciones de recoleccion de datos por demanda, la coordenadapermite difundir una consulta a una determinada region de la red, los no-dos que no estan en la region de interes descartan el mensaje, reduciendoası trafico innecesario [11]. Este tipo de algoritmos permite utilizar tablasde encaminamiento mas pequenas, porque la coordenada geografica tieneimplıcita la informacion sobre a que nodo debe enviarse el mensaje paraencaminarlo al destino.

Figura 3.3: Encaminamiento geografico

En la figura 3.3 (obtenida de [22]) se esquematiza como el encamina-miento basico selecciona cada vez, de manera avida, el nodo mas cercano alpunto de destino. En el ejemplo, el camino seleccionado desde la estacionbase comprende los nodos c, f, g y nodo destino. En la figura puede observar-se una importante deficiencia: si se ignora la topologıa, la ruta seleccionadapuede no ser la mas corta en saltos [22].Otro problema para el cual se han propuesto numerosas soluciones es el delcamino sin salida. En la figura 3.4 (obtenida de [22]), se muestra que aunquela estacion base tiene conectividad con el nodo destino, si se utiliza el al-goritmo avido, el mensaje llega al nodo situado a menor distancia restante,pero a partir de allı el obstaculo impide que el encaminamiento progrese,porque no hay conectividad con ningun otro nodo mas cercano a la posicionfinal.

62


Una solucion intuitiva al problema del camino sin salida es utilizar la reglade la mano derecha para escapar del laberinto. Si se detecta que un mensajeno puede progresar, se lo encamina rodeando la cara definida por los nodosalrededor del obstaculo, usando la regla de la mano derecha. Aun ası, no estrivial determinar a partir de que momento conviene pasar del modo avidoal modo perimetral.

Figura 3.4: Encaminamiento geografico en presencia de obstaculos

El sistema de localizacion es un requisito para poder realizar encamina-miento geografico. En algunas taxonomıas [36][11], dentro del paradigma seenumeran protocolos que asumen nodos con capacidades de posicionamientomuy variadas, donde el nodo:

Es consciente de su posicion y no se aclara que sistema de localizacionutiliza

Calcula una posicion virtual dentro de un sistema de coordenadas

Utiliza un sistema de GPS impreciso

Utiliza un sistema de GPS de bajo consumo

En la mayorıa de los casos, los nodos sensores no cuentan con GPS,debido a sus limitaciones de recursos y energıa inherentes [25][4], por lo queexiste un conjunto de tecnicas de triangulacion que permiten al nodo conocersu posicion. En [38] se propone un algoritmo de encaminamiento geograficobasado en coordenadas virtuales, que no requiere conocer la posicion real delos nodos de la red.

El encaminamiento geografico es escalable, los nodos solo deben mante-ner el estado de sus vecinos [38] (no global) y se soporta la comunicacion any

63


to any sin ser necesario establecer la ruta. Este tipo de protocolos es ade-cuado para aplicaciones en donde la estacion base inicia consultas dirigidasa un subconjunto de nodos, o una region en el espacio en particular[25].

3.3.2. Por coordenadas virtuales

Introduccion

El encaminamiento geografico requiere que los nodos conozcan su posi-cion. Como se ha mencionado anteriormente, existen muchas configuracionesen donde la informacion de posicion no esta disponible. El protocolo presen-tado en [38] hace foco en la asignacion de coordenadas virtuales a los nodosde la red, para utilizar un esquema de encaminamiento geografico estandar.No es necesario que estas coordenadas virtuales sean representaciones exac-tas de la geografıa de los nodos, mientras reflejen la conectividad entre losnodos, en particular la conectividad local o entre nodos vecinos, como seexplicara mas adelante [38]. En el encaminamiento geografico por coordena-das virtuales, los paquetes de red son encaminados de manera avida. De latabla de encaminamiento, siempre se reenvıa al nodo que este mas cerca deldestino, y que tambien esta mas cerca del destino que el nodo actual. Si elnodo actual es el mas cercano al destino, y la capa superior determina queen efecto el paquete debe ser entregado al nodo actual, entonces se conside-ra que el paquete ha llegado a destino. Pero si el paquete no ha llegado adestino y no puede progresar en forma avida, se ha llegado a un punto sinsalida, por lo que el nodo ejecuta el algoritmo expanding ring search o ERShasta encontrar un nodo mas cerca del destino.

Modelo de red

El modelo de red del trabajo original consta de miles de nodos, y unadensidad media, donde cada nodo tiene 16 vecinos [38].

Fases de operacion

Arranque (Bootstrap)

El arranque comprende 4 pasos.

1. Descubrimiento de nodos perımetroDos nodos predeterminados como baliza (beacon nodes) inundan la redcon mensajes HELLO. El mensaje contiene un contador de saltos quese incrementa en cada nodo que lo reenvıa. Al recibirlo, cada nododescubre su distancia en saltos a cada nodo baliza, siendo esta el me-nor valor de contador de entre todos los mensajes recibidos. Entonces,

64


una vez determinada la distancia a la baliza, los nodos deciden si sonperimetrales utilizando el criterio del nodo de perımetro. Si el nodoes el mas alejado del beacon, de entre todos sus vecinos a dos saltos,entonces esta en el perımetro.

2. Vector perımetroCada nodo perimetral inunda la red para permitir al resto de los no-dos calcular su vector perımetro, es decir, la distancia a cada nodoperimetral.

3. Coordenadas normalizadasCada nodo perımetro y baliza inunda la red con sus propios vectoresperımetro. El resto de los nodos utilizan este vector para normalizarlas coordenadas propias y de los nodos perımetros. Luego, los nodosperımetro proyectan las coordenadas en un circulo exterior.

4. Relajacion de coordenadasLos nodos perımetro quedan ahora fijos, mientras todos los otros nodosejecutan el algoritmo de ajuste de coordenadas.

Regimen (Steady State)

Una vez completo el arranque, uno de los nodos beacon inunda periodi-camente la red, cada 50 segundos, con mensajes HELLO. De esta manera,los nodos descubren su distancia a cada beacon y cada nodo decide si es unnodo perimetral o no, utilizando el criterio del nodo de perımetro. Periodi-camente tambien, cada nodo hace broadcast de la lista de sus vecinos a dossaltos, dentro del area de alcance de su radio. Si un nodo no recibe el latidode un vecino por tres intervalos, lo elimina de su lista de vecinos.

Normalizacion de coordenadas

En la normalizacion de coordenadas, todos los nodos calculan las coor-denadas virtuales normalizadas de los nodos perımetro. El proceso se realizaen dos pasos. A partir de la recepcion de los vectores perımetro, primero setriangulan coordenadas iniciales, y luego se normalizan con respecto a uneje de coordenadas definido por los nodos baliza.

1. TriangulacionAl recibir los vectores perımetro, cada nodo perimetral conoce las dis-tancias entre cada par de nodos perımetro. Dichos valores se utilizanen un algoritmo de triangulacion para calcular las coordenadas ini-ciales. El algoritmo define las coordenadas de manera de minimizar ladiferencia entre la distancia en saltos y la distancia euclıdea entre cadanodo perimetral.

65


minimizar{∑

i,jεperametro

(H(i, j)−D(i, j))2}

H es la distancia en saltos entre el nodo i y el nodo jD es la distancia euclıdea entre las coordenadas virtuales del nodo i y j

Esto significa que las coordenadas virtuales deben conservar las rela-ciones de distancia entre los nodos.

Figura 3.5: Nodos perımetro

Para simplificar, por ejemplo, supongamos que solo se descubren tresnodos de perımetro en una red como la de la figura 3.5, P1, P2 y P3,y sus respectivos vectores perımetro son los siguientes:

P1 = (0, 2, 3)P2 = (2, 0, 3)P3 = (3, 3, 0)

Entonces, la triangulacion trata de minimizar la siguiente suma:

( 2−√

(x1 − x2)2 + (y1 − y2)2 )2

+ ( 3−√

(x1 − x3)2 + (y1 − y3)2 )2

+ ( 3−√

(x2 − x3)2 + (y2 − y3)2 )2

Como los nodos que no estan en el perımetro igual reciben el broadcastde vectores perımetro, utilizan el mismo algoritmo de triangulacion

66


para calcular sus propias coordenadas iniciales normalizadas.

2. Normalizacion

Cualquier las coordenadas de cualquier conjunto que minimice las su-ma de la seccion anterior pueden ser rotadas y trasladadas, y aunası continuar satisfaciendo la condicion. Por lo anterior, las coordena-das iniciales se normalizan de manera que todos los nodos lleguen aobtener los mismos valores. La normalizacion se realiza con respectoun nuevo eje de coordenadas, que se forma a partir del centro de grave-dad de las posiciones de los nodos perımetro y baliza. Desde el centrode gravedad, la posicion de una baliza define el eje de ordenadas, y laposicion de la otra, el eje de abscisas. Si bien el calculo no se muestraen [38], se deduce lo expuesto a continuacion.

Supongamos que tenemos las siguientes coordenadas iniciales para nnodos perımetro:

Pn = (xn, yn)

Entonces, el centro de gravedad, o mejor dicho, el centroide del con-junto finito de estos n puntos en <2 es:

(c, d) =

∑n

(xn,yn)

n

Luego, para normalizar las coordenadas (x, y) del nodo perımetro P1,se calcula (x′, y′), realizando un cambio de base, de la base canonica ala base definida por b′1 = (xb1, yb1)− (c, d) y b′2y = (xb2, yb2)− (c, d):

(xb1, yb1) = coordenadas del nodo baliza 1(xb2, yb2) = coordenadas del nodo baliza 2

B′ =

(xb1 − c xb2 − cyb1 − d yb2 − d

)

(x, y)− (c, d) = B′·(

x’y’

)

Se lleva el centro de gravedad al origen, y las nuevas coordenadasse calculan para los ejes definidos por el centro de gravedad y lasposiciones de los dos nodos baliza.

67


Luego de la triangulacion, los nodos perımetro proyectan sus coor-denadas en un cırculo con origen en el centro de gravedad los nodosperımetro, y radio igual a la distancia promedio de los nodos perıme-tro al centro de gravedad calculado. Esta tecnica permite mantener unsistema de coordenadas consistente en presencia de fallas en los nodoso movilidad [38].

Relajacion de coordenadas

En este paso los nodos que no estan en el perımetro ajustan sus coor-denadas virtuales, en unas pocas iteraciones de calculo, partiendo de lascoordenadas iniciales normalizadas, y las coordenadas de los nodos perıme-tro proyectadas en un cırculo, cuyo radio es igual a la distancia promedio deestos nodos al centro de gravedad. Puede hacerse una analogıa del procesocon la teorıa de grafos embebidos, donde cada enlace (arista) representa unafuerza que trata de unir los nodos vecinos.

xi =

∑kεVi

xk

|Vi| yi =

∑kεVi

yk

|Vi|

Vi es el conjunto de vecinos del nodo i|Vi| es la cantidad de vecinos del nodo i

En cada iteracion, el nodo ordinario actualiza sus coordenadas virtuales,x e y, con el promedio del valor de coordenada de sus vecinos. Las coorde-nadas de los nodos perımetro quedan fijas. En [38] se muestra que luego deunas pocas iteraciones (del orden de 10), las coordenadas convergen a tasasde encaminamiento exitoso muy altas.

Conceptualmente, la relajacion produce que todos los nodos que no estanen el perımetro, pero que tienen un nodo perımetro entre sus vecinos, semuevan hacia el nodo perımetro mas cercano en terminos de cantidad desaltos.


En presencia de obstaculos o agujeros, se encontro que el encaminamien-to avido tiene mejor desempeno al utilizar coordenadas virtuales, porqueellas reflejan mejor la conectividad de la red que las posiciones reales [38].Por ejemplo, si bien en coordenadas geograficas reales un nodo puede estarmuy cercano a otro, ambos pueden estar desconectados o fuera de alcancedebido a la presencia de algun obstaculo, como puede verse en la figura 3.3.El algoritmo es escalable, porque luego de la fase de arranque, el costo demantenimiento en cantidad de mensajes, si bien no es despreciable, es inde-pendiente del tamano de la red.

68


Desventajas

En [38] sugiere como desventaja que en regimen, el algoritmo tiene uncosto indirecto asociado bastante alto debido a que todos los nodos inundanperiodicamente la red.

3.4. Encaminamiento centrado en los datos


En aplicaciones en las se instala una gran cantidad de nodos sensores,puede no ser posible asignar un identificador o direccion global, porque sumantenimiento genera un costo indirecto elevado. Sucede tambien que lainformacion generada por sensores instalados en una misma region, puedecontener redundancias que producen trafico innecesario[11]. Ası, este pa-radigma propone dos tecnicas clave para mejorar las cuestiones expuestas:un esquema de direccionamiento basado en propiedades o atributos de lainformacion y la posibilidad de agregar o fusionar datos eliminando redun-dancias.En esta clase de protocolos el encaminamiento se inicia con una consultarealizada por alguno de los nodos. Lo que se direcciona no es un nodo de lared, sino la informacion misma, a traves de algun atributo que posea (porejemplo, la ubicacion geografica en donde se genero), utilizando consultas[36]. Se han dado diferentes definiciones y nombres al encaminamiento cen-trado en datos [5][10][25], y en todas se lo caracteriza , de alguna manera,como basado en el contenido que se transmite. Un paquete se envıa a undeterminado nodo o es descartado, dependiendo de la informacion que con-tiene.

Este tipo de protocolos es adecuado para aplicaciones de deteccion deeventos, como por ejemplo, deteccion de incendios forestales, contaminacion.La tecnica de direccionamiento por atributos no es apropiada para aplica-ciones de monitoreo (reporte periodico), ya que en este tipo de aplicacionse requiere un trafico continuo de datos. Ello implica tener que consultar lamisma informacion periodicamente, y la busqueda de coincidencias entre laconsulta y los datos disponibles acarrea un costo indirecto [11] que puedeevitarse por diseno.El paradigma tambien se ha propuesto como adecuado para aplicaciones querequieren consultas orientadas a eventos, ya que las mismas solo involucranuna parte de la red a la vez, el trafico es eventual por lo que conviene re-ducir al mınimo el costo de direccionamiento y mantenimiento de rutas. Lautilizacion de agregacion de datos permitirıa en cierta manera minimizar laprobabilidad de obtener falsas alarmas en la deteccion de eventos.

69

3.4. ENCAMINAMIENTO CENTRADO EN LOS DATOS

EAD (Enery-Aware Data-Centric Routing) [39] es un algoritmo que per-tenece a este grupo, ya que implementa la tecnica de agregacion de datos.

3.4.2. Energy-Aware Data-Centric Routing

Introduccion

El protocolo se basa en que el mayor consumo de baterıa es realizado porel tranceptor, que consume casi lo mismo al enviar, recibir o en estado ocioso.Para ahorrar energıa, el mismo debe simplemente apagarse. Sin embargo,un nodo dormido no puede retransmitir mensajes, por lo que no se puedenapagar todos los tranceptores al mismo tiempo. EAD propone construir unacolumna vertebral de nodos activos que permita realizar un encaminamientoconsciente de la energıa.

Modelo de red

El modelo de red para el que se plantea EAD esta compuesto por cientoso miles de nodos sensores instalados al azar en el area de sensado, y unaestacion base o gateway que conecta la red con el exterior y se encuentra enlos lımites del area de instalacion, de manera de ser alcanzada por algunossensores [39].

Heurıstica de construccion de la columna

El objetivo de la columna vertebral de nodos es que exista un caminoactivo que permita hacer llegar el dato desde el nodo sensor en donde seorigina hasta el sumidero. Mientras un nodo forme parte de la columna,estara activo, con su radio encendida. Un nodo que no forme parte de lacolumna, puede apagarse periodicamente, y ahorrar energıa. Entonces, esconveniente construir la columna vertebral con la menor cantidad de nodosactivos posibles, o dicho de otro modo, construir con los nodos un arbolrecubridor con el maximo numero de nodos hoja y cuya raız sea el nodosumidero. Este problema es equivalente a construir un conjunto dominante-conexo que es NP-Completo, para lo que en [39] se propone una heurısticadistribuida que permite construir un arbol recubridor de nodos, teniendo encuenta los niveles residuales de energıa.

En la figura 3.6 se esquematiza el algoritmo de cambio de estado del no-do EAD. La columna se construye mediante el envıo de mensajes de controlque contienen 4 valores:

EstadoPuede ser 0 (indefinido), 1 (nodo hoja) o 2 (nodo de columna)

70


Figura 3.6: Maquina de estados del nodo EAD

NivelEl nivel dentro del arbol cuya raız es el nodo sumidero

PadreEl siguiente nodo, en el camino al sumidero

EnergıaEnergıa residual que posee el nodo

Al comenzar, todos los nodos se encuentran en estado 0 y el sumidero(la raız) hace broadcast de la tupla (2, 0, NULL,∞), donde ∞ indica que elemisor es el sumidero.Como se esquematiza en la figura 3.7, cuando un nodo v en estado indefinidorecibe el mensaje (2, nivelu, padreu, Eu) de un nodo de columna u:

1. v se vuelve nodo hoja

2. sensa el canal hasta que este ocioso

71

3.4. ENCAMINAMIENTO CENTRADO EN LOS DATOS

3. espera por T v2

4. si el canal sigue ocioso, v hace broadcast del mensaje (1, nivelv +1, u, Ev)

Figura 3.7: De estado indefinido a estado hoja

Cuando un nodo v en estado indefinido recibe el mensaje (1, nivelu, padreu, Eu)de un nodo hoja u:

1. v se vuelve nodo columna

2. sensa el canal hasta que este ocioso

3. espera por T v1

4. si el canal esta todavıa ocioso, v hace broadcast del mensaje (2, nivelu+1, u, Ev)

5. todos los nodos vecinos de v en estado indefinido se vuelven nodoshoja

72


Mientras el nodo v espera T1 o T2, si el canal es ocupado, el nodo vuelvea sensar hasta que el canal este ocioso.

Cuando un nodo v hoja recibe un mensaje (2, nivelu, v, Ew) de un nodow columna, lo que indica que v es padre de w:

1. v hace broadcast del mensaje (2, nivelv, padrev, Ev) apenas el canalesta ocioso (sin esperar)

El proceso continua hasta que todos los nodos definen su estado. Si unnodo no descubre ningun hijo, automaticamente se vuelve nodo columna.Los tiempos de espera, T v1 y T v2 , se calculan localmente y de modo que losnodos con la mayor cantidad de energıa residual hagan broadcast primero,por lo que se definen inversamente proporcional a Ev.

Encaminamiento centrado en datos

EAD intenta reducir y descartar informacion redundante, utilizandoagregacion de datos en cada nodo que no es hoja a lo largo de la ruta.Cada nodo no-hoja combina los datos producidos en todos los nodos en elsub-arbol del cual es raız, empleando alguna funcion de agregacion (suma,promedio, media, maximo, etc.). De este modo, un paquete de informacionpuede cambiar su contenido durante su recorrido desde un nodo hoja, pa-sando por nodos intermedios hasta alcanzar la raız del arbol.

Figura 3.8: Ejemplo de agregacion de datos camino al sumidero

Incluso dos o mas paquetes pueden ser fusionados o agregados en ununico paquete que sigue la ruta al sumidero, como puede observarse en elejemplo de la figura 3.8 (obtenida de [39]), donde la funcion de agregacionobtiene el maximo valor.

73

3.5. DISEMINACION DE INTERES

Fases de operacion

EAD opera en rondas. La ronda consta de las siguientes dos fases:

1. InicializacionDurante esta fase se ejecuta el algoritmo EAD y se construye la co-lumna vertebral de la red.

2. TransmisionEn esta fase se transmiten los datos al sumidero.

En cada ronda, al ejecutarse la inicializacion, los nodos que no estenactivos ya no seran agregados, y los nodos que han quedado huerfanos sonreincorporados al arbol.


EAD permite ahorrar energıa apagando el tranceptor de los nodos queno pertenecen a la columna de transmision, extendiendo la vida de la red.Asimismo, los nodos en columna agregan los datos recibidos de sus hojas,descartando informacion redundante para reducir trafico innecesario.

Desventajas

Para redes de sensores de gran escala, la ejecucion de EAD puede nece-sitar mucho tiempo para propagarse a toda la red. En [39] se proponen dosenfoques para limitar la ejecucion del algoritmo a un subconjunto de nodosde la red. Sucede tambien que solo los nodos mas cercanos al sumidero seranelegidos como gateways, lo que eventualmente conduce al particionamientode la red [40].

3.5. Diseminacion de interes


Como ya se ha dicho, dentro del paradigma de protocolos centrados endatos, se clasifican aquellos que direccionan la informacion por atributos dela misma, en lugar de direccionar el dispositivo fısico en donde fue generada.En esencia, la identidad del nodo que genera la informacion, o la del nodoque recolectara los datos es irrelevante [22]. El flujo de la informacion quedadeterminado por el interes especıfico del receptor en lugar de la direcciondel emisor [41].

El paradigma que naturalmente se ajusta a ese patron de interacciones el de publisher/subscriber, donde todos los nodos estan conectados a unsoftware bus, en el cual se publican datos notificados a aquellos nodos que

74


previamente se han suscripto como interesados en esos datos [22].

El flooding o inundacion es una tecnica utilizada a menudo para dise-minar informacion, que se basa en un enfoque reactivo donde cada nodoque recibe un paquete lo reenvıa a todos sus vecinos. Es economico en unsentido, no hay descubrimiento y mantenimiento de rutas, ya que se asumeuna topologıa de red plana [4].

La diseminacion de interes es una tecnica que surge a partir del analisisde las falencias del flooding. El desempeno de los algoritmos basados eninundacion empeora rapidamente a medida que crece el tamano de la red[4]. En la literatura se mencionan tres efectos no deseados [42]:

Implosion de traficoComo un nodo siempre envıa el paquete recibido a sus vecinos, sinimportar si alguno ya lo recibio, cuando un nodo recibe mas de unacopia de un paquete, ello significa que se han desperdiciado recursosen transmisiones redundantes. El problema se ilustra en la figura 3.9(obtenida de [42]). En (1) el nodo a envıa el paquete DATA1 a susvecinos, b y c. En (2) el nodo b envıa el paquete recibido DATA1 a suvecino, d. En (3) el nodo c tambien envıa DATA1 al nodo d. El nodod recibe dos veces el mismo paquete.

SuperposicionLos nodos a menudo sensan areas geograficas que se superponen. Cuan-do inundan a sus vecinos con los datos sensados, si dos nodos cercanosposeen un vecino comun, este puede recibir la informacion por dupli-cado. Como puede verse en la figura 3.10 (obtenida de [42]), tanto elnodo a como el nodo b sensan la zona 3, y por lo tanto, al inundar asu vecino comun, el nodo c, este recibe la informacion de la zona 3 porduplicado. Este problema es mas difıcil de resolver que la implosion,porque no solo depende de la topologıa de la red, sino tambien delmapeo del dato sensado a los nodos.

Ceguera de recursosLos nodos no modifican su actividad segun la cantidad de energıa dis-ponible que poseen, produciendo un uso poco eficiente de los recursosde la red.

Ası, para optimizar el trafico, en varios protocolos propuestos tempra-namente para redes de sensores [18][42], la diseminacion se apoya en undireccionamiento basado en atributos. El trafico se negocia por medio delintercambio de meta-datos, o descriptores de alto nivel de la informaciondisponible [42]. La diseminacion de interes es un caso especial de la dise-minacion. Permite implementar consultas a la red, donde por ejemplo, unsumidero inicia una peticion que especifica la informacion de interes por

75


Figura 3.9: Implosion

Figura 3.10: Superposicion

medio de atributos de la misma. La peticion se propaga por la red y pos-teriormente cuando un nodo dispone de informacion que cumple con losatributos, los datos se encaminan hacia el sumidero que origino la consulta.

En la literatura a menudo se ilustra el paradigma centrado en datoscon dos enfoques populares para la diseminacion de informacion, DirectedDiffussion y SPIN[43]. Directed Diffussion disemina consultas de datos ademanda y esta orientado a aplicaciones de consulta de datos frecuente.SPIN es un protocolo conducido por eventos, orientado a aplicaciones deconsulta unica (one-shot query) [22], y se describe en la siguiente seccion[25]. En [44][45] tambien se menciona a Fireworks, un protocolo que diseminainteres o consultas en forma probabilıstica.

76


3.5.2. SPIN

Introduccion

Para poder superar las deficiencias del flooding clasico (implosion, su-perposicion y ceguera de recursos) , SPIN (Sensor Protocols for Informationvia Negotiation) incorpora dos tecnicas innovadoras en su momento [42]:

NegociacionPara evitar la implosion y la superposicion, los nodos negocian entresı la transmision de los datos, utilizando meta-datos para describir lainformacion disponible.

Adaptacion a los recursosCada nodo dispone de un administrador de recursos que mantieneregistro del consumo de recursos. Cuando la energıa es baja, el nodose abstiene de participar de ciertas actividades, por ejemplo, el reenvıode informacion de terceros.

SPIN es disenado sobre la base de dos ideas clave. Primeramente, si bienintercambiar la informacion sensada puede ser una actividad costosa, inter-cambiar informacion sobre la informacion sensada no necesariamente lo es.En segundo lugar, los nodos deben adaptarse a cambios en su disponibilidadde recursos para extender su vida util y la de la red. Sus autores establecenque se toman mejores decisiones de encaminamiento si se utilizan conoci-mientos sobre los datos de la aplicacion y el estado de los recursos en cadanodo, ademas de la topologıa de red [42].

Modelo de red

SPIN asume una topologıa de red plana, donde cualquier nodo sensorpuede cumplir el rol de sumidero. Asimismo, cualquier nodo puede ser fuentede datos, es decir, genera informacion sensando el medio ambiente, y estainformacion debe ser diseminada a toda la red. El tamano del dato quegenera el nodo sensor es relativamente grande [22].

Operacion

Meta-datos sobre la informacion sensada

SPIN no establece el formato que debe tener el meta-dato de la informa-cion generada. Sin embargo, se asume lo siguiente [42]:

Si x es el meta-dato descriptor del dato X, entonces el tamano de xen bytes es mucho menor que el tamano de X

Si dos datos son distinguibles, entonces sus meta-datos tambien lo son

77


De la misma manera, si dos datos son indistinguibles, entonces tienenla misma meta-representacion (el mismo meta-dato)

La ventaja de contar con una representacion sucinta de los datos su-pera ampliamente el costo de almacenar, recuperar y mantener meta-datos

Son interesantes los dos ejemplos de meta-datos que se mencionan en[42]:

Si los sensores cubren regiones geograficas que no se superponen, elmeta-dato puede ser su identificador unico

Un sensor camara podrıa llegar a usar como meta-dato una coordenadade tipo (x, y, Phi) donde (x, y) es una coordenada geografica, y Phies la orientacion

Negociacion

Los nodos SPIN se comunican utilizando 3 tipos de mensajes [46]:

ADVAviso o anuncio de nuevos datos. Cuando un nodo dispone de nue-va informacion, puede notificarlo transmitiendo un mensaje ADV quecontiene meta-datos.

REQPeticion de datos. Se utiliza para indicar que se desea recibir la nuevainformacion.

DATAMensaje de datos. Un mensaje DATA contiene la informacion propia-mente dicha, encabezada por el meta-dato.

En [46] se presentan 4 protocolos SPIN, el mas basico de ellos SPIN-PP(SPIN point-to-point) permite ilustrar el modelo de negociacion. SPIN-PPse disena optimizado para una red teorica que utiliza un medio de trans-mision punto a punto, asumiendo que es posible que dos nodos A y B secomuniquen exclusivamente uno con el otro, sin interferir la comunicacioncon otros nodos. Bajo esta hipotesis, el costo de comunicacion es lineal (co-municarse con n vecinos, es n veces el costo de comunicarse con un vecino).

SPIN-PP trabaja en tres etapas, cada una de las cuales corresponde auno de los mensajes descriptos anteriormente:

78


AnuncioEl protocolo comienza cuando un nodo anuncia que dispone de nuevosdatos para diseminar, enviando un mensaje ADV que contiene el meta-dato de la informacion generada.

PeticionCuando un nodo vecino recibe un mensaje ADV, determina si ya harecibido el mensaje o si ha requerido la informacion que describe elmeta-dato. En caso negativo, responde enviando un mensaje REQ pi-diendo la informacion.

DatosEl protocolo se completa cuando el nodo que lo inicio responde elmensaje REQ con un mensaje DATA que contiene la informacion pro-piamente dicha.

La ronda de negociacion se ilustra en las figuras 3.11, 3.12, 3.13, ob-tenidas del trabajo original [42]. Observando la figura 3.11, la negociacioncomienza en 1), donde el nodo a anuncia que dispone de nuevos datos. En2) el nodo b solicita la transmision de la informacion nueva. Luego, en lafigura 3.12, en 3) el nodo a transmite la informacion propiamente dicha alnodo b, encabezada por el meta-dato. En 4) el nodo b anuncia a sus vecinosque dispone de nuevos datos. Por ultimo, en la figura 3.13, en 5) los nodosc y e solicitan la transmision de los nuevos datos de b. Finalmente en 6) Elnodo b transmite los datos a los nodos que lo han solicitado.

Figura 3.11: Negociacion SPIN pasos 1 y 2

79




Es importante aclarar que el protocolo no requiere que todos los nodosrespondan a todos los mensajes. Por ejemplo, un nodo no enviara un mensajeREQ si ya dispone de la informacion que se anuncia en el mensaje ADVrecibido.

80


SPIN-EC

SPIN-EC[46] agrega logica de conservacion de energıa bastante simple aSPIN-PP. Cuando un nodo observa que su energıa residual se aproxima a unumbral inferior de carga de baterıa, reduce su participacion en el protocolo.Si el nodo recibe un dato nuevo, solo iniciara la ronda de negociacion si puedecompletar las tres etapas (anunciar y responder la peticion). De la mismamanera, si recibe un anuncio, solo enviara la peticion si tiene suficienteenergıa para recibir el dato.

SPIN-BC

SPIN-BC[46] es una version de SPIN que agrega optimizaciones paracuando se utiliza un canal de transmision compartido. Cuando un nodoenvıa un mensaje, este es recibido por todos los nodos dentro del rango dealcance de la radio, sin importar el destino original de mensaje.

Supresion de peticiones

En SPIN-BC todos los nodos envıan a la direccion de broadcast. Si algunnodo A dentro del rango del nodo B requiere el dato, bastarıa con la peticionde A para que todos los nodos en el rango reciban el dato. Si A direcciona lapeticion a B, todos los nodos en el rango sobreescuchan la peticion. Enton-ces, un nodo C que tambien requiere el dato, se abstiene de enviar tambiensu peticion, es decir, suprime la peticion. Ası, cuando un nodo recibe unmensaje ADV, revisa si ya recibio o solicito el dato. Si no lo hizo, estableceun temporizador que expira en un tiempo al azar, elegido de manera unifor-me en un intervalo predeterminado. Al expirar el temporizador el nodo envıaun mensaje REQ a la direccion de broadcast especificando en la cabecera ladireccion del nodo que originalmente anuncio el dato. Cuando otros nodosreciben el mensaje REQ, cancelan sus propios temporizadores y suprimensu peticion redundante.

Otra diferencia importante es que el nodo que recibe peticiones de datosrespondera la informacion a la direccion de broadcast una unica vez.

SPIN-RL

SPIN-RL [46] es una version confiable de SPIN-BC.

Repeticion de pedidosEn SPIN-RL cada nodo mantiene registro de todos los anuncios recibidos.Si no recibe el dato transcurrido un cierto periodo de tiempo posterior alpedido enviado o suprimido, el nodo vuelve a pedir el dato. En la cabecera

81

3.6. CONSCIENCIA DE LA ENERGIA

del pedido indica como nodo origen cualquier vecino que haya anunciado eldato.

Limite de reenvıo de datosSi un nodo envıa un dato, luego espera una cantidad de tiempo predefinidaantes de volver a enviar el mismo dato.

Si no hay confiabilidad en el enlace, y un anuncio se pierde, el protocolono garantiza la completa difusion de los datos.


Una de las ventajas de SPIN es que los cambios en la topologıa de la redson localizados ya que un nodo solo necesita conocer a sus vecinos [11].

Desventajas

No todos los protocolos o heurısticas de diseminacion son confiables. Porejemplo, SPIN no garantiza la entrega de datos, ya que si un nodo interesadoen determinados datos se encuentra muy lejos de la fuente, y los nodosintermedios no tienen el mismo interes, la informacion no sera entregada[11].

3.6. Consciencia de la energıa

3.6.1. Introduccion

Una de las limitaciones fundamentales de las redes de sensores es lacapacidad de baterıa. En [14] se plantea que en las redes moviles y ad hoclos protocolos se disenan con el objetivo de minimizar la cantidad de saltosque atraviesa un paquete. A diferencia de estas redes, en WSN es crucialminimizar el consumo de energıa empleado para la tarea de encaminamiento,o resolver el problema del encaminamiento de menor energıa [12] a partir dediferentes enfoques de diseno, que se manifiestan en las metricas de energıautilizadas.

En los trabajos analizados, especialmente los que presentan una taxo-nomıa de algoritmos, la tecnica de dar consciencia de la energıa al encami-namiento no aparece como un paradigma en sı misma, sino que, la eficienciaen terminos de energıa se busca utilizando tecnicas adicionales. El empleode metricas de energıa en el encaminamiento no siempre aparece en el disenode protocolos que buscan eficientizar el uso de energıa.

Por ejemplo, en el caso de LEACH, el rol de cabecera dentro de un clus-ter de nodos es el que mayor consumo de transmision tiene, por reenviar a

82


la estacion base, la cual no pertenece al cluster y esta a mayor distancia quelos nodos locales. Este rol es rotado sobre la base de la energıa residual queel nodo posee. Aquellos nodos que tengan mayor energıa disponible, tendranmas oportunidades de ser cabecera y entonces, el trafico fluira a la estacionbase siempre a traves de los nodos con mayor energıa residual.En el caso de EAD, que como LEACH es un protocolo jerarquico, el nivel deenergıa residual se utiliza de manera que los nodos con mas energıa tenganmayor probabilidad de ser los nodos de la columna vertebral de transmisionque el protocolo construye. Nuevamente, la informacion fluye a traves de losnodos que poseen mayor energıaEn cambio, con los protocolos de encaminamiento geografico, al encaminarde manera avida, la eficiencia se intenta lograr de manera mas indirecta. Albuscar rutas que utilicen la menor cantidad de saltos, se disminuye la canti-dad de reenvıos de un paquete, y con ello, la energıa de transmision utilizada.

3.6.2. Metricas de energıa

En [47] se presentan varias metricas de diseno que permiten construirrutas eficientes en terminos de energıa, y que aparecen muy frecuentementeen los protocolos para redes de sensores:

1. Minimizar la energıa total de la rutaCon el enfoque de energıa total mınima o MTE (Minimum TotalEnergy), se busca minimizar la energıa de transmision y recepciontotal consumida por un paquete para alcanzar el destino. Sucede quesi todo el trafico se encamina a traves de las rutas mas economicas, losnodos en esa ruta se agotan rapidamente, particionando la red [12],por lo que no se recomienda utilizar esta metrica en forma aislada.

2. Maximizar el tiempo hasta que la red se particionaSe determinan los nodos que al ser removidos causan particiones, y setrata de balancear la carga sobre los mismos.

3. Uniformizar el consumo de energıaSe parte de la hipotesis de que todos los nodos son igualmente im-portantes, y se intenta asegurar que todos los nodos funcionen juntosla mayor cantidad de tiempo, que la carga sea balanceada entre to-dos. Por ejemplo, utilizando rutas compuestas por los nodos de mayorenergıa residual, evitando los nodos de menor capacidad restante, pos-poniendo al maximo posible la muerte del primer nodo. En [14] seaclara que aunque todos los nodos de la red funcionen en conjunto lamayor cantidad de tiempo posible, ello no implica que la utilizacionde la energıa disponible sera optima. Una red densa podrıa operar

83


efectivamente durante mas tiempo sin el total de los nodos desplega-dos inicialmente, recuperando informacion con los nodos que quedenactivos.

4. Minimizar el costo por paqueteSe seleccionan las rutas de menor costo total, que equivale a la sumade los costos de cada enlace que se utiliza. Si se define adecuadamenteel costo del enlace, puede utilizarse la metrica con diferentes objetivos.Por ejemplo, si el costo depende de la energıa residual, puede lograrseaumentar el tiempo hasta el particionamiento de la red.

Ahora bien, en el material de investigacion analizado se hallaron variosalgoritmos que utilizan alguna de las metricas mencionadas en la decisionde encaminamiento. Algunos de ellos [48][49] no fueron desarrollados paraWSN, sino para redes ad hoc. Otros fueron disenados especıficamente pararedes de sensores:

SPIN (Sensor Protocols for Information via Negotiation)SPIN es una familia de protocolos [4] basados en la negociacion parala diseminacion de informacion. SPIN-EC es una variante que limitala participacion del nodo en la secuencia de negociacion segun el nivelde energıa que posee. Podrıa decirse que utiliza una metrica de tipo4, ya que un nodo es reluctante a participar del encaminamiento si suenergıa esta por debajo de un nivel umbral [42].

FA (Flow Augmentation)Modifica periodicamente el trafico dirigido a un nodo segun el costo delenlace. Un enlace menos costoso es aquel que requiere menos energıade transmision y aquel en donde el nodo destino posee una mayor can-tidad de energıa residual [12]. Este costo es una metrica de tipos 1 y4.

MIR (Maximum Information Routing)Define el costo del enlace a partir de una metrica de cantidad de infor-macion que el nodo contribuye, penalizando el costo de aquellos nodosque mas informacion generan, para evitar que sean incluidos frecuen-temente en la ruta [14]. Este algoritmo utiliza una metrica de tipo 4.

Keep ConnectedDefine el costo del enlace a partir de la cantidad de componentes co-nexas que resultarıan si el nodo agota su energıa y muere. Aquel nodo

84


que al morir, produce una mayor cantidad de particiones es mas im-portante y debe evitarse incluirlo en la ruta [13]. Este algoritmo utilizauna metrica de tipo 2.

EBTA-WSN (Energy-Balanced Transmission Algorithm)Selecciona la ruta de menor costo total de transmision, utilizando no-dos cuya energıa residual esta por encima del promedio de la red [9],es decir, utiliza una metrica de tipos 1 y 4.

Flow Augmentation, propuesto en [12] incluye en su diseno el objetivode maximizar la vida util de la red.

3.6.3. Flow Augmentation

Introduccion

El algoritmo de aumentacion de flujo propuesto en [12] es un encamina-miento de camino mas corto, donde el costo del enlace es una combinaciondel consumo de energıa de transmision y recepcion, y los niveles de energıaresidual en los dos nodos extremos. En el trabajo se calcula la solucion opti-ma teorica al problema de maximizar la vida de la red, planteado como unproblema de programacion lineal, y atacando el problema equivalente demaximizar la cantidad de informacion transferida para una tasa de genera-cion de datos constante. La solucion optima se compara con la heurısticadisenada. La heurıstica consiste en calcular la ruta de menor costo. En lu-gar de utilizar como costo eij la energıa consumida cuando se transmite elpaquete por el enlace ij, se utiliza 1

REi−eij yeijREi

, donde REi es la energıa re-

sidual del nodo i. Mediante el algoritmo de camino mas corto Bellman-Forddistribuido, se halla la ruta de menor costo [11].

Modelo de red y tipo de aplicacion

El modelo de red asume un conjunto de nodos estaticos, desplegados alazar, y cuya energıa es empleada mayormente en la transmision y recep-cion de datos. Los nodos generan informacion que debe ser entregada a unconjunto de nodos gateway, siendo posiblemente encaminada a traves demultiples saltos. En [50] se analizan dos escenarios o tipos de aplicacion.En un escenario se asume una tasa de generacion de informacion constante,como sucede con el tipo de aplicacion de reporte periodico de datos. En unsegundo escenario, un objetivo atraviesa la region de despliegue haciendoque los sensores que lo detectan generen cierta cantidad de informacion porsegundo, lo que corresponde al tipo de aplicacion de seguimiento.

85


Costo del enlace

Se elige el nombre Aumentacion de Flujo porque el algoritmo aumentao disminuye el trafico dirigido a un nodo, segun el costo actualizado del en-lace a utilizar. Como el costo del enlace se define en funcion de la energıade transmision, pero tambien en funcion de la energıa residual del nodo autilizar, el efecto es que al comienzo, cuando todos los nodos disponen deenergıa, se encamina minimizando la energıa total consumida por la ruta.A medida que la energıa residual disminuye, el algoritmo trata de evitar losnodos que dispongan de la menor cantidad de energıa.

El costo del enlace se define como:

costoij = (eijt)x1 ·REi−x2 · IEix3 + (eij

r)x1 ·REj−x2 · IEjx3

etij es la energıa de transmision consumida al utilizar el enlace (i,j)

erij es la energıa de recepcion consumida al utilizar el enlace (i,j)

IEi y IEj son las energıas iniciales en los nodos i, j respectivamente

REi y REj son las energıas residuales

x1, x2 y x3 son factores de peso que permiten variar la manera en quese considera el nivel de energıa residual

Ası, IEiREi

+IEjREj

se logra utilizando x1 = 0 y x2 = x3 = 1.IEiREi

es el inverso de energıa residual en i, relativa al total.IEjREj

es el inverso de energıa residual en j, relativa al total.

De esta manera, a menor energıa residual, mayor es el costo del enlace.

Fases de operacion

En [12] no se menciona una fase de arranque, sino unicamente un regimenque comprende varios pasos ejecutados en forma iterativa. En cada iteracion:

commodity : un conjunto de nodos fuente y nodos destino

1. Cada nodo origen calcula la ruta mas economica para cada nodo des-tino que pertenece al commodity c

2. Si algun commodity no puede hallar una ruta a su destino, entoncesparar.

86


3. Aumentar el flujo en cada ruta de menor costoLas rutas de menor costo seran utilizadas hasta la proxima iteracion.Como se asume una tasa constante de generacion de informacion, pue-de conocerse la cantidad de informacion enviada en cada iteracion

4. Actualizar los valores de energıa residualDado que se conoce la cantidad de informacion transmitida en cadaiteracion, puede conocerse tambien la cantidad de energıa consumiday valor de energıa residual resultante

Aunque los resultados de simulaciones muestran que el algoritmo tieneun desempeno cercano al optimo, la mayorıa de las veces, tanto para tasasde generacion de informacion fijas como para un escenario de deteccion deun objetivo en movimiento, el desempeno del algoritmo depende las rutasde generacion de informacion.

Figura 3.14: Desempeno no optimo de FA

Por ejemplo, consideremos la red de la figura 3.14 (obtenida de [12]),donde cada nodo posee cuatro unidades de energıa, y se requiere una unidadde energıa para transmitir un paquete, utilizando cualquier enlace. Si elnodo b genera cuatro paquetes de informacion (Qb = 4), el algoritmo losdivide entre los nodos d y e, empleando dos unidades de energıa en cadanodo. Luego, el nodo a genera ocho paquetes de informacion (Qa = 8), yel algoritmo los divide entre los nodos c y d, pero la energıa en esos nodosahora no es suficiente y quedan dos paquetes de informacion sin entregar.Facilmente puede verse que si los paquetes de b solo se encaminaran a travesde e, podrıa entregarse toda la informacion generada.

Desventajas

En [12] se aclara que el protocolo no es escalable ni aplicable a grandesredes debido a las limitaciones inherentes al encaminamiento dirigido por ta-blas. Cabe senalar que esta restriccion surge de la topologıa planteada, cada

87


nodo debe mantener las rutas mas economicas actualizadas hacia multiplesdestinos (gateways). De igual manera, si se requiere soportar la comunica-cion de peticiones de la estacion base a un conjunto de nodos, cada nododebera mantener el costo de las rutas en tablas que creceran en proporciona la densidad de la red.

88

Capıtulo 4

Diseno de la simulacion conOmnet++

4.1. ¿Que es Omnet++?

4.1.1. Introduccion

Omnet++ es una herramienta de simulacion de redes, de eventos dis-cretos, modular y orientada a objetos. Su arquitectura generica ha permi-tido que sea utilizada para estudiar problemas de diversos dominios, entreellos, el modelado de redes de comunicacion inalambrica y protocolos. Laherramienta no es un simulador de algo en particular, sino que provee lainfraestructura para escribir simulaciones. Los modelos son ensamblados apartir de componentes reutilizables llamados modulos. Los modulos se co-munican entre sı por medio del pasaje de mensajes a traves de compuertasy conexiones, o directamente. Los modulos pueden tener parametros parapersonalizar su comportamiento o parametrizar la topologıa del modelo dered.Al nivel mas bajo de la jerarquıa de modulos se tienen los modulos simplesque encapsulan el comportamiento, se programan en C++ utilizando la li-brerıa de simulacion.Las simulaciones pueden correrse en varios tipos de ambiente. El ambientegrafico animado es util para demostraciones y depuracion. El ambiente delınea de comandos es mejor para ejecucion por lotes.

La herramienta completa es probada en los sistemas operativos mas co-munes (Linux, MAC OS/X y Windows), y tambien soporta simulaciones enparalelo distribuidas. Para este trabajo no se utilizo esta funcionalidad, ylas simulaciones corrieron en una unica computadora con Windows 7. Om-net++ es gratis para uso academico y sin fines de lucro [51], y OMNEST essu version comercial.

89

4.1. ¿QUE ES OMNET++?

4.1.2. Conceptos de modelado

Un modelo de Omnet++ consiste de modulos que se comunican a travesdel pasaje de mensajes.Los modulos que actuan se llaman modulos simples y se escriben en C++utilizando la librerıa de simulacion. A su vez, los modulos simples puedenagruparse en modulos compuestos, creando una jerarquıa. El modelo com-pleto se llama red y es un modelo compuesto.

Los mensajes son enviados por conexiones que comunican los modulos,y pueden contener cualquier informacion. Tıpicamente, son enviados pormodulos simples a traves de compuertas. Las compuertas son las interfacesde entrada y salida de los modulos: los mensajes se envıan a traves de com-puertas de salida y llegan por compuertas de entrada. Una compuerta deentrada y una compuerta de salida se enlazan por una conexion. Se puedendefinir tipos de conexion con propiedades especıficas (retardo de propaga-cion, tasa de transferencia, tasa de errores de bit), modelando un canal.

4.1.3. Descripcion de red

La estructura del modelo de simulacion se describe con el lenguaje NED(Network Description). Con este lenguaje se declaran modulos simples ymodulos compuestos. Un modulo compuesto puede ser etiquetado como red,es decir, como modelo de simulacion auto-contenido. Por ejemplo, se puededefinir una red compuesta por nodos encaminadores, donde en cada nodohay una aplicacion corriendo, que genera paquetes de datos transmitidos atraves de un canal (ver figura 4.1, obtenida del manual de la herramienta[51]).

90

CAPITULO 4. DISENO DE LA SIMULACION CON OMNET++

Figura 4.1: Vista de diseno de una red Omnet++

El nodo es un modulo compuesto por los submodulos que modelan laaplicacion y el encaminamiento (capa fısica, acceso al medio y capa de red).La figura 4.2 es la vista de diseno de un nodo MiXiM (ver seccion 4.2.1).

Figura 4.2: Diseno del nodo como modulo compuesto

91


4.1.4. Conceptos de simulacion

Como ya se ha dicho, los modulos que actuan se llaman modulos simplesy se escriben en C++ utilizando la librerıa de simulacion. Los siguientesconceptos de simulacion de eventos discretos permiten entender como sedisenan los modulos simples.

Simulacion de eventos discretos

Un sistema de eventos discretos es aquel en el que los cambios de estadossuceden en tiempo discreto, y el evento emplea cero cantidad de tiempo ensuceder. Se asume que nada interesante sucede entre dos eventos consecuti-vos, es decir, no se produce ningun cambio de estado. Este tipo de sistemapuede ser modelado usando simulacion de eventos discretos.

El tiempo en el que el evento ocurre se llama marca de tiempo y enOmnet++ se llama tiempo de llegada (ya que en la biblioteca de clases lapalabra marca de tiempo esta reservada para un atributo asignable en laclase evento).

El tiempo en el modelo se llama tiempo de simulacion, tiempo de modeloo tiempo virtual en oposicion al tiempo real, que se refiere al tiempo duranteel cual el programa ha estado corriendo, o el tiempo de CPU que se refierea cuanto tiempo de CPU ha consumido.

Eventos

En Omnet++ los eventos son representados por mensajes, es decir, poruna instancia de la clase cMessage o una subclase de esta. Los mensajesson enviados desde un modulo a otro, lo que significa que el lugar donde“el evento ocurre” es en el modulo destino, y el tiempo de modelo en el queocurre es el tiempo de llegada del mensaje. Los eventos se consumen en elorden que da el tiempo de llegada. Si el tiempo de llegada es el mismo, elorden lo da la prioridad del mensaje. Si la prioridad es la misma, el ordenes aleatorio.

El ciclo de eventos

La simulacion de eventos discretos mantiene una lista de eventos futurosen una estructura comunmente llamada FES (Future Event Set). En Om-net++ se implementa como un montıculo binario, la estructura de datosmas utilizada para este proposito.

El simulador trabaja de acuerdo al pseudocodigo del algoritmo 1.

El paso de inicializacion construye las estructuras de datos que repre-sentan el modelo a simular, ejecuta el codigo de inicializacion que se haredefinido, e inserta eventos iniciales en la lista de eventos futuros. El bu-cle subsiguiente consume eventos de la lista y los procesa. Los eventos se

92


Algoritmo 1: Ciclo de evento

1 inicializar (construye el modelo e inserta eventos iniciales)2 while FES no vacıa Y simulacion no completa do3 obtener primer evento de FES4 t := marca de tiempo de este evento5 procesar evento (inserta nuevos eventos o borra eventos de FES)

6 end7 terminar simulacion (escribir resultados estadısticos, etc.)

procesan en orden estricto dado por la marca de tiempo, para mantener lacausalidad. Procesar eventos involucra la invocacion de codigo provisto porel modulo creado. La simulacion se detiene cuando no hay mas eventos ocuando se alcanza el lımite de tiempo de modelo o CPU. En ese momen-to, antes de terminar la ejecucion, generalmente se graban estadısticas enarchivos de salida.

93


4.1.5. Ambiente de desarrollo

El IDE (ambiente integrado de desarrollo) de Omnet++ esta basado enla plataforma Eclipse [52], y la extiende con editores, vistas y asistentes. EsteIDE provee una Perspectiva de Simulacion (figura 4.3) para trabajar con lostipos de archivo de Omnet++, que deben ser incluidos en un proyecto desimulacion.

Figura 4.3: Perspectiva de Simulacion de Omnet++ en Eclipse

4.1.6. Definicion de un modulo simple

Como se ha dicho, la simulacion ejecuta modulos simples. Un modulosimple es una clase C++ que debe extender de una clase modulo simplede base, y redefinir su comportamiento. La clase debe registrarse con Om-net++.

Los modulos simples son instanciados por el kernel de simulacion, porello la firma del constructor debe tener una forma predefinida. Debe seguirsela siguiente convencion de inicializacion y finalizacion:

constructorEl constructor es invocado para crear el modulo, como parte de la

94


inicializacion del modulo propiamente dicho. En ese momento, todo elmodelo esta siendo construido por lo que no pueden hacerse muchascosas desde el constructor. Por convencion, en el constructor se asignantodas las variables puntero de la clase del modulo a NULL.

inicializadorEl metodo initialize() es invocado justo antes de comenzar la ejecucionde la simulacion, cuando todo el modelo esta listo. Por convencion, enel metodo initialize() se realizan todas las tareas de inicializacion: leerparametros, inizalizar variables, reservar memoria, crear e inicializartimers.

destructorEl destructor siempre se llama al final, sin importar como termino lasimulacion. Se puede asumir que, en ese momento, el modelo de simula-cion esta casi destruido por completo. Por convencion en el destructorse libera la memoria reservada, se eliminan los temporizadores creados(con la funcion cancelAndDelete(msg)).

finalizadorEl metodo finalize() sirve para grabar estadısticas. Solamente se invocacuando la simulacion ha terminado normalmente. Si la simulacion sedetiene por error, no sera invocado. Por convencion, en este metodo segraban estadısticas, y no se deben liberar objectos ni ejecutartareas de limpieza.

Para definir el comportamiento dinamico del modulo simple, se debe re-definir el metodo handleMessage, invocado con un mensaje como parame-tro cada vez que el modulo recibe un mensaje. Se espera que el metodoprocese el mensaje, y retorne. Durante la ejecucion de este metodo notranscurre tiempo de simulacion, solo entre llamadas. La idea es que concada evento (llegada de mensaje) se invoca una funcion definida en el modu-lo. Dentro de la funcion pueden utilizarse otras funciones predefinidas paraenviar mensajes a otros modulos, programar un evento (enviar un mensajea sı mismo), y borrar un evento programado. Los modelos de capas de pro-tocolos tienden a compartir una estructura similar, porque reaccionan a trestipos de eventos fundamentales: mensajes que llegan de capas superiores (laaplicacion), mensajes que llegan de capas inferiores (la red) y varios tempo-rizadores (auto-mensajes).

Generalmente, surge el patron de modelado que se ilustra en el fragmen-to de codigo 4.1:

95


Fragmento de codigo 4.1: Modelo de protocolo de capa

1 class FooProtocol: public cSimpleModule

2 {

3 protected:

4 //state variables

5 //...

6 virtual void processMsgFromHigherLayer(cMessage *packet);

7 virtual void processMsgFromLowerLayer(FooPacket *packet);

8 virtual void processTimer(cMessage *timer);

9 virtual void initialize();

10 virtual void handleMessage(cMessage *msg);

11 };

96


4.1.7. Simulacion

Una vez que se han escrito los fuentes se compila el proyecto obteniendoun ejecutable. La simulacion se realiza corriendo el ejecutable generado, ypuede ser lanzada desde el IDE. Para ello, se define una configuracion deejecucion, especificando algunos detalles como (ver figura 4.4):

directorio de trabajoes el directorio base del cual dependen otras configuraciones

ejecutablela ruta del ejecutable de la simulacion, relativa al directorio del espa-cio de trabajo

archivos de inicializacionarchivos que contienen conguraciones de parametros modificables dela red y los modulos

Figura 4.4: Configuracion de ejecucion en Omnet++

4.1.8. Herramientas de analisis

Graficos de secuencia

Un archivo de log de eventos contiene la bitacora de mensajes enviadosdurante la simulacion, y el detalle de eventos disparados por su envıo o re-cepcion, incluyendo mensajes enviados entre modulos y temporizadores. Sepuede controlar que modulos graban en el log, la cantidad de datos que se

97


graban, el comienzo y fin de la grabacion. Los graficos de secuencia desplie-gan el archivo de log en forma grafica, permitiendo visualizar la causalidadde los eventos. El log de eventos tambien se puede visualizar en forma tabu-lar. Los eventos pueden ser filtrados por diferentes criterios, incluyendo pormodulo, tipo de mensaje y por relacion de causalidad. La figura 4.5 es unfragmento de secuencia de las simulaciones del protocolo SPIN.

Figura 4.5: Grafico de secuencia en Omnet++

Analisis de resultados

Los resultados de la simulacion son grabados como escalares, vectores ehistogramas. Luego, pueden aplicarse metodos estadısticos para extraer in-formacion relevante y obtener una conclusion. En el proceso generalmente sefiltran y transforman datos. Desde la version 4 de Omnet++, la herramientade analisis estadıstico se ha integrado a Eclipse. Los filtros y transformacio-nes de datos se graban en archivos de analisis que permiten reproducirinstantaneamente el post-proceso sobre resultados de nuevas corridas. Conel editor de analisis de Eclipse se navegan los vectores y escalares, se definendatasets a partir de expresiones de filtro, y estos se despliegan en graficos

98


de barras, curvas, histogramas y de dispersion. En la figura 4.6 se muestrala solapa de navegacion de resultados, donde se han filtrado los escalarespara visualizar solamente la tasa de exito de cada simulacion. Luego, en lafigura 4.7 se presenta la tasa de buen exito en un grafico de barras.

Figura 4.6: Navegador de vectores y escalares en Omnet++

Figura 4.7: Grafico de barras en Omnet++

99

4.2. DISENO DE LA RED

Desempeno

Omnet++ ha sido comparado con NS2 y se han recogido metricas queindican que emplea menos memoria y un menor tiempo de ejecucion [53][54].Tambien se ha evaluado la exactitud de los resultados obtenidos con Om-net++ en simulaciones de WSN[55], observandose que cuanto mayor es lafrecuencia de muestreo, la cantidad de eventos que debe manejar el nodoaumenta fuertemente. A una frecuencia de muestreo de 5 ms, los resulta-dos de las simulaciones muestran una distancia significativa respecto de losresultados obtenidos en un campo de pruebas real. A partir de una frecuen-cia de 50 ms, esta distancia es menos evidente, y a partir de los 500 ms esdespreciable.

4.2. Diseno de la red

4.2.1. MiXiM 2.1

MiXiM [56] es un framework de modelado para Omnet++, creado pa-ra redes inalambricas fijas y moviles (redes inalambricas de sensores, redesde area corporal, redes vehiculares, etc). Ofrece modelos detallados de pro-pagacion de ondas, estimacion de interferencias, consumo del tranceptor, yprotocolos de acceso al medio.

Una red MiXiM basica se compone de los siguientes elementos:

modulo de definicion de la red

modulo de definicion del host

modulo de interfaz de red, que define la placa de red del host

la configuracion de la capa fısica, modelo analogico (calculo de atenua-cion) y decider (clasificacion de ruido y calculo de errores de bit).

la configuracion de la simulacion

La figura 4.2 en la seccion 4.1.3 es la vista de diseno de un nodo MiXiM.

Fragmento de codigo 4.2: Definicion de red

1 network WSNRouting {

2 parameters:

3 // x size of the area the nodes are in (in meters)

4 double playgroundSizeX @unit(m);

5 // y size of the area the nodes are in (in meters)

6 double playgroundSizeY @unit(m);

7 // z size of the area the nodes are in (in meters)

8 double playgroundSizeZ @unit(m);

100

9 double numHosts; // total number of hosts in the network

10

11 submodules:

12 world: BaseWorldUtility {

13 parameters:

14 playgroundSizeX = playgroundSizeX;

15 playgroundSizeY = playgroundSizeY;

16 playgroundSizeZ = playgroundSizeZ;

17 @display("p=0,0;i=misc/globe");

18

19 }

20 connectionManager: ConnectionManager {

21 }

22

23 node[numHosts]: Host802154_2400MHz {

24 parameters:

25 numHosts = numHosts;

26 }

27

28 connections allowunconnected:

29 }

En la definicion de red 4.2 se incluyen parametros de definicion de lasdimensiones del terreno, los submodulos de utilidad global y de administra-cion de conexiones, y el tipo de host que compone la red.

El administrador de conexiones verifica si dos hosts pueden oırse uno alotro y actualiza sus conexiones de acuerdo a eso. Si dos hosts estan conec-tados significa que pueden recibir algo de cada uno, pero no significa quepueden entenderse. Si dos hosts no estan conectados, estan fuera del rangode interferencia y no recibiran ninguna senal uno del otro.

Es muy importante diferenciar el rango de interferencia del modelo decomportamiento de la radio. El rango de interferencia define la distancia apartir de la cual un nodo alejado deja de existir para el tranceptor. El modeloanalogico y el decider, junto con los parametros del modulo de interfaz dered, determinan la intensidad de senal combinada y si un frame es recibidoo no.

El decider y los modelos analogicos se definen con un archivo xml queconfigura parametros propios. En el modulo de interfaz se debe especificarque archivo contiene esta configuracion.

Fragmento de codigo 4.3: Configuracion del decider

1 <?xml version="1.0" encoding="UTF-8"?>

2 <root>

3 <AnalogueModels>

4 <AnalogueModel type="BreakpointPathlossModel">

5 

101

6 <parameter name="alpha1" type="double" value="2"/>

7 <parameter name="L01" type="double" value="40.2"/>

8 <parameter name="breakpointDistance" type="double" value="8.0"/>

9 <parameter name="alpha2" type="double" value="3.3"/>

10 <parameter name="L02" type="double" value="58.8"/>

11 <parameter name="carrierFrequency" type="double" value="2.4E+9"/>

12 </AnalogueModel>

13 </AnalogueModels>

14 <Decider type="Decider802154Narrow">

15 

18 <parameter name="sfdLength" type="long" value="8"/>

19

20 

21 <parameter name="berLowerBound" type="double" value="1e-8"/>

22

23 

24 <parameter name="modulation" type="string" value="oqpsk16"/>

25

26 </Decider>

27 </root>

En el fragmento de codigo 4.3 es un ejemplo del contenido del archi-vo xml. En este ejemplo, se declara un modelo analogico de tipo Break-pointPathlossModel, que representa el modelo de atenuacion definido en elestandar IEEE 802.15.4. Como puede observarse, pueden declararse mas deun modelo analogico. Luego se declara el tipo de decider, Decider802154Narrow,que clasifica la senal en bits o ruido, segun el modelo BER definido tambienen el estandar IEEE 802.15.4.

En la tabla 4.1 se enumeran la mayorıa de los modulos de MiXiM utili-zados para modelar la red.

4.2.2. Modelo de dispositivo

Los nodos de la red estan representados por un modulo compuesto porvarios submodulos:

batteryPermite definir una capacidad inicial de baterıa, y que la radio pueda con-sumir energıa descontando de esa capacidad.

nicDefine el comportamiento de la interfaz de red. Es a su vez un modulocompuesto por el modulo de capa de enlace y el modulo de capa fısica. Elmodelo de interfaz utilizado es IEEE 802.15.4-2006 y esta implementado porel modulo ic802154 TI CC2420, descripto mas adelante.

102


Modulo Proposito

WSNRouting Definicion de red para simulacion de redesinalambricas de sensores.

Host802154 2400MHz Definicion de host que utiliza un tranceptor802.15.4 a 2.4 GHz.

BatteryStats Modulo de recoleccion de estadısticas sobre ba-terıa.

SimpleBattery Modelo simple de baterıa.

BaseMobility Administrador de informacion basica de movili-dad y posicion. Este modulo define un patron demovilidad estatico (solo posicion).

Nic802154 TI CC2420 Modelo de interfaz de red Texas Instruments CC2420 IEEE 892.15.4 CSMA.

CSMA802154 Enlace IEEE 802.15.4-2006 CSMA no ranurado.

PhyLayerBattery Capa fısica que consume baterıa.

Decider802154Narrow Decider para clasificacion de senales 802.15.4 debanda estrecha

BreakPointPathlossModel Implementacion del modelo de atenuacion IEEE802.15.4

Cuadro 4.1: Modulos MiXiM utilizados

netDefine el protocolo de red que utiliza el dispositivo. En este trabajo se desa-rrollaron nuevos modulos de red para tres protocolos.

appDefine el comportamiento de la aplicacion que utiliza los servicios de red. Sedesarrollaron dos nuevos modulos para simular una aplicacion de consulta.

Interfaz de red IEEE 802.15.4

El modulo Nic802154 TI CC2420 implementa una interfaz de red TexasInstruments CC 2420 802.15.4 usando el protocolo de enlace CSMA es-pecificado en el estandar IEEE 802.15.4-2006. El modelo CSMA802154 fuevalidado independientemente en una red inalambrica de sensores de prue-ba [57], aunque la validacion fue realizada con una cantidad de nodos muypequena.

Capa fısica

El modulo de capa fısica permite configurar la sensibilidad y potencia detransmision. El tranceptor del chip CC 2420 soporta los siguientes niveles

103


de potencia de transmision segun las especificaciones[58]:

Figura 4.8: Potencia de transmision del tranceptor TI CC2420

La maxima potencia de transmision es 1 mW, y es la que se utilizo parala simulaciones.

No se ha podido hallar el alcance de la radio en la hoja de datos deltranceptor [58]. En la documentacion del nodo sensor MICAz de la companıaMEMSIC [24] se especifica que el alcance del tranceptor es de 75 a 100 m enexteriores, y de 20 a 30 m en interiores. Se configuro un valor de sensibilidadde -95 dBm [58].

El modulo de capa fısica utilizado calcula la atenuacion utilizando el mo-delo establecido en la seccion E.5.3 del estandar IEEE 802.15.4-2006 [31].Esta capa utiliza el modulo decider Decider802154Narrow para filtrar lassenales recibidas segun su intensidad, calcular los errores de bits y clasifi-car las senales en ruido o frames. En la version 2.1 de MiXiM este moduloignora la sensibilidad del tranceptor, por lo que dos nodos que estan a unadistancia bastante mayor que la de la especificacion (recibiendo una senalcon una potencia mucho menor a la que el tranceptor es sensible), puedenconectarse en la simulacion. Este comportamiento fue modificado para quela sensibilidad sea tenida en cuenta.

Se aclara que para las simulaciones realizadas se deshabilito el ruidotermico.

Modelo de baterıa

La baterıa es un modulo independiente, y define cual es la capacidadinicial y el voltaje.

La capa fısica de la interfaz Nic802154 TI CC2420, PhyLayerBattery,descuenta energıa de la baterıa segun tipos de actividades definidas: dormir,recepcion, transmision, cambio de modo, y actividad del decider. El frag-mento de codigo 4.4 muestra la definicion de las posibles actividades en el

104


modulo.

Fragmento de codigo 4.4: Actividades de capa fısica

1 class PhyLayerBattery : public PhyLayer{

2

3 enum Activities {

4 SLEEP_ACCT=0,

5 RX_ACCT,

6 TX_ACCT,

7 SWITCHING_ACCT,

8 DECIDER_ACCT,

9 };

10 ...

4.2.3. Topologıa

Si bien en [59] se utilizan tres tipos de nodo, sensor, encaminador y su-midero; en el trabajo [60] solo se observan dos tipos, sensor y sumidero.

El modelo de red seleccionado para este trabajo esta formado por unsumidero unico y un conjunto de nodos sensores, todos estaticos. Se imple-menta con un unico tipo de nodo sensor-encaminador, y uno de los nodosse configura como sumidero. Para ese nodo sumidero no se contabilizanpaquetes ni consumo de energıa. La seleccion del nodo sumidero se hace es-pecificando su direccion de red, en el archivo de configuracion de simulacion,con la lınea del fragmento de codigo 4.5:

Fragmento de codigo 4.5: Configuracion del nodo sumidero

1 **.node[*].net.sinkAddress = 0

4.2.4. Tamano del terreno y densidad de nodos

En las simulaciones de [59] se modela el algoritmo encaminador de ma-nera aislada, excluyendo el canal, por lo cual no se especifica un tamano deterreno. En [60] tampoco se especifica el tamano de la region cubierta.

En omnet++ se pueden especificar las dimensiones en metros de un es-pacio tridimensional con forma de cubo, en la configuracion de la simulacion,con las lıneas del fragmento de codigo 4.6:

Fragmento de codigo 4.6: Dimensiones del terreno

105


1 **.playgroundSizeX = 500 m

2 **.playgroundSizeY = 500 m

3 **.playgroundSizeZ = 10 m

Para las simulaciones se utilizo un terreno de 500 m de lado.

En [60], para probar M-SPIN se utilizo un tamano de red de 10 a 60nodos, y en [59] se probo SAFM en despliegues de 80 a 1280 nodos.

El modelo de radio asume un alcance de 75-100 m en terreno abierto.Con un alcance de 75 m de nodo a nodo, y un despliegue predefinido estilogrilla, con un nodo en cada vertice de cuadrados de 75 m de lado, la cantidadmınima de nodos sensores para cubrir un terreno de 500 metros de lado es de:

500×50075×75 = 44 nodos

Pero este calculo se aplica cuando se puede hacer un despliegue preciso.Cuando el despliegue es al azar, para cubrir un area cuadrada con alta pro-babilidad, la cantidad de nodos es la siguiente [61]:r = rango de transmision de los nodosa = longitud de lado de un area cuadrada de a× an = (ar )2

m = Θ(n lnn)cantidad de nodos para cubrir el area cuadrada

Dimensiones del te-rreno (m2)

Cantidad de nodos

500 80

Cuadro 4.2: Densidad mınima de nodos

Para cubrir las dimensiones del terreno de prueba se necesitan 80 nodos.

4.2.5. Modelo de despliegue

En ninguno de los trabajos [60][59] se especifica una posicion fısica parael sumidero. En lugar de ello, se define con que nodos sensores tiene conec-tividad.

Para las simulaciones de este trabajo, los nodos sensores son desplegadosal azar, excepto por el sumidero, cuya posicion es cercana a algun punto en elperımetro del terreno definido. Las posiciones son generadas aleatoriamentepor el simulador, y por ello, puede que algun nodo quede desconectado dela red y no participe de la consulta.

106


4.2.6. Modelo de aplicacion

El tipo de aplicacion modelado es el de consulta iniciada por el sumidero,el patron de trafico es episodico y los requerimientos de latencia no sonestrictos.

Se definen dos modulos de aplicacion, uno para el sumidero y otro para elresto de los nodos. La aplicacion del sumidero envıa un mensaje que contieneuna tarea de sensado a diseminar entre los nodos. La aplicacion de los nodosrecibe una tarea de sensado proveniente del sumidero, y responde con losdatos generados.

La tarea de sensado contiene un numero de mediciones a tomar y unperıodo de tiempo entre cada una. Para las estadısticas, solo se contabili-zaran los paquetes de datos generados enviados por los nodos, y se omitenlos paquetes que envıa el sumidero con la tarea.

Los nodos que han quedado sin conexion a sumidero, no generan datos,porque nunca reciben la tarea.

107

4.3. METRICAS DE EVALUACION

4.2.7. Resumen del diseno

Caracterıstica Descripcion

Interfaz de redTI CC 2420 802.15.4 banda estrecha CS-MA no ranurado

Topologıa 1 sumidero y 79 sensores

Terreno 500 m2

Despliegue al azar

Modelo de aplica-cion

Consulta

Cuadro 4.3: Resumen de la red a simular

4.3. Metricas de evaluacion

Puede decirse que las metricas para evaluar protocolos estaran relaciona-das con los requerimientos de la aplicacion para la cual se disenan. En [26] sesugiere que no todas las metricas son utiles para todos los tipos de aplicacion.En algunos artıculos se da una definicion general de la metrica, sin detallarcomo se mide. Del analisis de los trabajos de generalizacion [26][27][4] y delas evaluaciones de protocolos [62][39][63][14], surge el conjunto de metricasenumerado en las siguientes secciones.

4.3.1. Vida util del sistema

Tiempo de vida

Dadas las limitaciones de energıa de los nodos de de las WSNs, se buscaoptimizar los protocolos para extender el tiempo que dura la red en opera-cion, es decir, que puede proveer informacion del fenomeno sensado.

Puede tomarse alguna de las siguientes medidas genericas:

a) Tiempo hasta que un nodo agota su energıa

T1 [segundos]

b) Tiempo hasta que la mitad de los nodos agotan su energıa

Tn2

[segundos]

108


c) Tiempo hasta que algun nodo queda aisladod) Tiempo hasta que algun nodo no posee ruta al sumideroe) Tiempo hasta que la red queda particionada

Tpartition [segundos]

O alguna medida especıfica de la aplicacion:

f) Tiempo hasta que algun requerimiento de calidad de servicio ya no puedegarantizarseEsta metrica se define sobre la base de otra; es el tiempo hasta que unametrica de calidad de servicio supera o cae debajo de un umbral. En [64]se menciona que la cobertura puede utilizarse un parametro para medir lacalidad de servicio en aplicaciones de deteccion de eventos. Entonces, la vi-da util podrıa tambien definirse, por ejemplo, como el tiempo hasta que lacobertura cae al 80 %.

TCov80 [segundos]

Capacidad

Podrıa definirse como el total de paquetes recibidos durante el tiempode vida.

AppT

4.3.2. Eficiencia

Longitud de ruta promedio

Es la cantidad de nodos que forman el camino entre el nodo origen y elnodo destinatario del dato. Puede relacionarse con la cantidad de transmi-siones y energıa necesaria para encaminar un paquete.Una manera de calcularlo es contar la cantidad de saltos totales y la canti-dad total de paquetes recibidos.

Havg = HRec

H = Cantidad de saltos totalesRec = Total de paquetes recibidos

Total de paquetes

Total de paquetes de encaminamiento que genera el protocolo.

Sent = Total de paquetes enviados

109


Transmisiones por consulta

Da una medida del costo promedio en paquetes de una consulta inyec-tada en la red. Este tipo de metrica se utiliza en aplicaciones basadas enconsulta.

QTavg = QSent

Q = Cantidad total de consultasSent = Total de paquetes enviados

Overhead de control

Es la medida del costo indirecto asociado al encaminamiento. Existenvarias metricas que muestran este costo.

Controlt = Total de paquetes de control enviadosDatat = Total de paquetes de datos enviadosSent = Total de paquetes enviadosRec = Total de paquetes recibidosAppr = Total de paquetes de aplicacion entregados

a) Cantidad promedio de paquetes de control por paquete de datos.

ControltDatat

b) Cantidad promedio de paquetes necesarios para encaminar un paquete.

SentRec

c) Cantidad promedio de paquetes del protocolo por paquete de aplicacionentregado.

SentAppr

4.3.3. Uso de la energıa

Costo por paquete

La cantidad promedio de paquetes que pueden ser exitosamente entre-gados por unidad de energıa.

110


eAppavg = ApprE [ 1

mWs ]

E = Consumo total de energıa [mWs]Appr = Total de paquetes de aplicacion entregados

Energıa disipada

La cantidad promedio de energıa que se utiliza al detectar un evento. Esuna medida mas general, que incluirıa otras actividades ademas del encami-namiento.

eEvavg = EEv [mWs]

E = Consumo total de energıa [mWs]Ev = Total de eventos detectados

Energıa total

Energıa disipada total, suma del consumo total de cada nodo.

E = Consumo total de energıa [mWs]

Distribucion de la energıa

Uniformidad de los niveles de energıa de los nodos.

Eσ = Desviacion de la energıa residual

4.3.4. Calidad de servicio

Confiabilidad

Una medida de la tasa de exito en la transmision de paquetes.

Conf = DatarDatat

(0..1)

Datat = Total de paquetes de datos enviadosDatar = Total de paquetes de datos recibidos

111


Perdidas

Tasa de perdidas, indica el porcentaje de paquetes de datos no recibidospor ningun nodo.

Loss = 1− Conf (0..1)

Latencia

Tiempo promedio de recepcion de paquetes (latency, end-to-end delay).

Latavg = Retardo promedio de fuente a sumidero [s,ms]

Tiempo de reaccion

Retardo luego de algun cambio en la red.

Cobertura

Expresa que fraccion de la region a monitorear es alcanzada por los no-dos que quedan activos.

Cov = SubRR (0..1)

R = Espacio total monitoreado inicialmenteSubR = Espacio monitoreado con los nodos activos

Escalabilidad

Variacion del comportamiento del protocolo al variar la densidad y can-tidad de nodos. Podrıa pensarse como la variacion de las metricas de interesen funcion de la cantidad de nodos.

4.3.5. Metricas no consideradas

Conectividad

Fraccion de enlaces activos una vez que la red se particiona. En realidad,la metrica sugiere una medida de cobertura.

112


Particionamiento

Cuantos nodos quedaron aislados. Esta metrica tambien sugiere una me-dida de cobertura.

4.3.6. Metricas seleccionadas

Las siguientes metricas seran extraıdas de los resultados de la simulacion,basadas en la clasificacion presentada al comienzo de la seccion.

Longitud de ruta

Se extraeran estadısticas sobre la longitud de ruta en cantidad de saltosde los paquetes entregados al sumidero.

Hσ = Desviacion de la longitud de rutaHmax = Longitud maxima registradaHmin = Longitud mınima registradaHmean = Longitud media registrada

Total de paquetes

Se contabilizara el total de paquetes de red enviados durante la simula-cion, excluyendo los que envıa el sumidero.

Sent = Total de paquetes de red enviados

Overhead de control

Se extraera una metrica de gasto de control calculada de la siguientemanera:

Overhead = SentAppr

Total de paquetes de red enviados por cada paquete de aplicacion recibido

Costo por paquete

La cantidad de paquetes de aplicacion entregados por unidad de energıa.

eAppavg = ApprEt

113


Distribucion de la energıa

Para analizar la uniformidad de energıa, puede analizarse en su lugar,la uniformidad del consumo de energıa para la transmision, excluyendo alsumidero.

Etσ = Desviacion del consumo total de energıa en transmisionesEtmax = Maximo consumo total de energıa en transmisionesEtmin = Mınimo consumo total de energıa en transmisiones

Etmean = Media del consumo total de energıa en transmisiones

Energıa total de transmision

Puede analizarse el consumo de energıa desglosandolo por actividad.En particular, se extraera el consumo total en transmisiones, excluyendoel sumidero.

Et = Energıa total utilizada en transmisiones

Confiabilidad

Se calculara la confiabilidad a nivel aplicacion, es decir, contabilizandopaquetes de aplicacion.

Conf = ApprAppt

Latencia

Se extraeran estadısticas de latencia a nivel aplicacion, registrando elretardo de todos los paquetes entregados en el sumidero:

Latσ = Desviacion de latenciaLatmin = Latencia mınimaLatmax = Latencia maximaLatmean = Latencia media

114

Capıtulo 5

Implementacion de modulosde red

5.1. Definiciones

Como se presenta en [65], la relacion de vecindad de los nodos define ungrafo no dirigido (por ser los enlaces bidireccionales) G = (V,E), donde Ves el conjunto de vertices y E ⊆ V ×V es el conjunto de aristas. Los verticescorresponden a las entidades (o nodos) y una arista (o enlace) (x, y) exis-te sı y solo sı el nodo x puede transmitir al nodo y, y viceversa. Se denomina:

n(G) al numero de vertices o nodos

m(G) al numero de aristas y

d(G) al diametro de G, la maxima distancia entre dos nodos (para hallarlo,se determina el camino mas corto entre cada par de vertices, y la mayorlogitud de todos ellos es el diametro

N(x) el conjunto de vecinos de x, tal que si y ε N(x), entonces x puedetransmitir a y, y viceversa

Para el analisis de costo de los algoritmos se medira la actividad de co-municacion, contando la cantidad de transmisiones de mensajes realizadas,es decir, el costo en mensajes M.

En las especificaciones se utilizaran los terminos nodo y enlace unica-mente, y se hara referencia al costo en mensajes como complejidad M.

115

5.2. DISEMINACION DE INTERES CON M-SPIN

5.2. Diseminacion de interes con M-SPIN


M-SPIN [60] es una version modificada de SPIN (ver 3.5.2) para trans-mitir informacion unicamente al nodo sumidero (en lugar de propagarla ala totalidad de la red), disminuyendo ası la cantidad de paquetes necesariosy el consumo de energıa. Como SPIN, M-SPIN es un protocolo orientado aaplicaciones de reporte de eventos. La modificacion contribuye a que la in-formacion sea notificada y propagada en direccion al sumidero rapidamente.Para ello, se agrega una etapa previa a las rondas de negociacion de infor-macion de SPIN, donde se asigna la distancia al sumidero, quedando la reddividida en niveles, como puede observarse en la figura 5.1.

Descubrimiento de distancia

En esta etapa, se mide la distancia en saltos al sumidero. Inicialmenteel sumidero hace broadcast de un paquete STARTUP, que contiene la tupla(tipo, id, distancia):

tipoes el tipo de mensaje

ides el identificador del nodo emisor

distanciaes la distancia en saltos al nodo sumidero, el valor inicial es 1

Cuando un nodo recibe el paquete STARTUP, se asigna la distancia quetrae el paquete, incrementa la distancia del paquete en 1 y vuelve a hacerbroadcast del paquete. Si un nodo recibe multiples paquetes STARTUP, seasigna la menor distancia recibida, y cada vez que actualiza su distancia,retransmite el paquete con la distancia incrementada en 1.

En la figura 5.1 (obtenida de [60]), los enlaces que unen los nodos quehan quedado a una misma distancia del sumidero, no seran utilizados parapeticiones y transmisiones de datos, porque siempre se encamina hacia unnodo de menor distancia. Observar que si el nodo que esta a distancia 4genera datos, ambos nodos a distancia 3 solicitaran la informacion. El datodel nodo a distancia 4 sera posiblemente encaminado a traves de ambosnodos a distancia 3.

116

CAPITULO 5. IMPLEMENTACION DE MODULOS DE RED

Figura 5.1: Etapa de descubrimiento de distancia al sumidero

Negociacion, peticion y transmision de datos

La negociacion es similar a la que realiza SPIN-BC, descripto en la sec-cion 3.5.2. El nodo que genera el dato lo notifica haciendo broadcast de unpaquete ADV. Al recibirlo, cada nodo verifica si ya ha recibido o requeridoel dato, y tambien si esta a menor distancia del sumidero que el nodo queenvio el ADV. Solo si esta a menor distancia, el nodo hara la peticion deldato, enviando un paquete REQ.La transmision de datos ocurre de la misma manera que en SPIN-BC. Cuan-do el nodo que genero el dato recibe el paquete REQ, envıa el paquete DATAinmediatamente con la informacion solicitada. Al recibir el dato, el nodo quelo pidio recomienza la negociacion, notificando a sus vecinos con un paqueteADV con la distancia modificada. El proceso continua hasta que el sumiderorecibe los datos.

Evaluacion

En la evaluacion original del protocolo se utilizaron las siguientes metri-cas:

Metrica Descripcion

ADVCantidad total de paquetes ADV transferidos para queun evento alcance el nodo sumidero.

EConsumo total de energıa al variar la cantidad de no-dos.

Cuadro 5.1: Metricas de M-SPIN

Se utilizo una tamano de red mınimo de 10 nodos y un maximo de 60.

En el trabajo [60] se presenta como problema principal de M-SPIN elagotamiento de la energıa en los nodos mas cercanos al sumidero.

117


5.2.2. Especificaciones

SPIN-PP

Valores de estadoS = {INITIATOR, IDLE, DIFFUSE, GATHER, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}

Restricciones{BL, TR, CN, UI }

Tipos de mensajeADV, REQ, DATA

VariablescountADV

BL = Bidirectional LinksEl grafo que definen los enlaces es no dirigido.

TR = Total ReliabilityNo han habido fallas ni las habra.

CN = ConnectivityEl grafo es fuertemente conexo. De cada nodo es posible alcanzar acualquier otro nodo.

UI = Unique InitiatorSolo una entidad comienza el algoritmo.

El nodo en estado INITIATOR posee un nuevo dato para encaminar ycomienza la negociacion anunciando el dato a todos sus vecinos, enviandoun paquete ADV a cada uno. Entonces pasa al estado DIFFUSE.

INITIATORSpontaneouslybegin

send(ADV) to N(x);countADV := |N(x)|;

118


become DIFFUSE;end

Al comenzar, el resto de los nodos se encuentra en estado IDLE. En esteestado, cuando el nodo recibe un paquete ADV que anuncia un nuevo dato,envıa un paquete REQ para solicitar el dato al nodo que lo anuncio. Luegopasa al estado GATHER.

IDLE

Receiving(ADV)begin

send REQ to sender;countADV := |N(x)| − 1;become GATHER;

end

En estado DIFFUSE, el nodo se encuentra a la espera de peticiones porel dato que ha anunciado. Cuando recibe un paquete REQ de peticion, res-ponde con los datos solicitados al nodo que lo emitio. Si recibe un paqueteADV, decrementa un contador que permite determinar cuando todos losnodos vecinos ya poseen el dato, momento en el cual pasa al estado de ter-minacion local DONE.

DIFFUSE

Receiving(REQ)begin

send DATA to sender;end

Receiving(ADV)begin

counter−−;if counter = 0 then

become DONE;endif

end

119


En estado GATHER el nodo se encuentra negociando el dato que ha so-licitado. Si recibe un paquete DATA, envıa un paquete ADV a cada vecinomenos el nodo del cual recibio informacion, anunciando el nuevo dato queposee y pasa al estado DIFFUSE. Si recibe un paquete ADV, decrementaun contador que permitira determinar cuando todos los nodos vecinos yaposeen el dato.

GATHER

Receiving(DATA)begin

Cache(DATA)send ADV to N(x) - {sender};become DIFFUSE;

end

Receiving(ADV)begin

counter−−;end

SPIN-BC

Valores de estadoS = {INITIATOR, IDLE, WAIT, DIFFUSE, GATHER, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}


Tipos de mensajeADV, REQ, DATA

Variables{countADV}

El nodo en estado INITIATOR posee un nuevo dato para encaminar ycomienza la negociacion anunciando el dato a todos sus vecinos, enviandoun paquete ADV por broadcast. Entonces pasa al estado DIFFUSE.

120



send(ADV) to N(x);countADV := |N(x)|;become DIFFUSE;

end

Al comenzar, el resto de los nodos se encuentra en estado IDLE. En esteestado, cuando el nodo escucha un paquete ADV, inicia la alarma de supre-sion de peticion, que expira en un tiempo al azar, y pasa al estado WAIT.

IDLE

Receiving(ADV)begin

set alarm := c(x) + u(I)source := sender;countADV := |N(x)| − 1;become WAIT;

end

En el estado WAIT, el nodo se encuentra esperando oir una peticion porel mismo dato en negociacion, para suprimir la suya. En este estado, si laalarma de supresion expira, el nodo envıa una peticion por broadcast, espe-cificando de que nodo recibio el anuncio. Luego pasa al estado GATHER.Si antes de expirar la alarma, recibe un paquete REQ, el nodo cancela laalarma suprimiendo su peticion y pasa al estado GATHER. Asimismo, siantes de expirar la alarma recibe el paquete DATA, cancela la alarma su-primiendo su peticion, anuncia el nuevo dato por broadcast y pasa al estadoDIFFUSE.Si en el estado WAIT recibe un paquete ADV, decrementa un contador quepermite detectar que todos los vecinos ya poseen el dato.

WAIT

When c(x) = alarmbegin

REQ.source = source;send REQ to N(x);

121


become GATHER;end

Receiving(REQ)begin

//Si escucha un pedido por el mismo datoif source = REQ.source then

unset alarm; //Suprime la peticionbecome GATHER;

endifend


Cache(DATA);unset alarm; //Suprime la peticionsend ADV to N(x);become DIFFUSE;

end

Receiving(ADV)begin

counter−−;end

En el estado DIFFUSE, el nodo se encuentra a la espera de peticionespor el dato que anuncio. Si escucha una peticion que especifica que el origendel anuncio fue el mismo, responde por broadcast un paquete DATA con losdatos y pasa al estado DONE, ya que SPIN-BC solo envıa el dato una vez.Si recibe un paquete ADV, decrementa un contador que permite detectarcuando todos los vecinos ya poseen el dato anunciado.

DIFFUSE

Receiving(REQ)begin

//El pedido debe ser para este nodoif REQ.source = x then

send DATA to N(x);become DONE;

endifend

122


Receiving(ADV)begin

counter−−;if counter = 0 then

become DONE;endif

end

En estado GATHER, el nodo se encuentra negociando el dato que noposee. Si escucha el paquete DATA, anuncia por broadcast el nuevo dato asus vecinos y pasa al estado DIFFUSE. Si escucha un paquete ADV, decre-menta un contador que permite detectar cuando todos sus vecinos ya poseenel dato.

GATHER


Cache(DATA)send ADV to N(x);become DIFFUSE;

end

Receiving(ADV)begin

counter−−;end

M-SPIN Distancia

Segun descripto en [60].

Valores de estadoS = {INITIATOR, IDLE, ITERATE, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}


123


Tipos de mensaje{STARTUP, ACK}

Variables{countAck, parent}

El nodo sumidero o iniciador comienza el algoritmo enviando por broad-cast un paquete STARTUP con valor de distancia 0 a todos sus vecinos.Luego, contabiliza paquetes ACK. Cuando ha recibido un ACK de cadavecino, pasa al estado DONE de terminacion local. En ese momento se al-canzo la convergencia.


STARTUP.hop := 0;send STARTUP to N(x);countAck := |N(x)|;

end

Receiving(ACK)begin

countAck−−;if countAck = 0 then

become DONE;endif

end

Receiving(STARTUP)begin

send ACK to sender;end

Al comenzar, el resto de los nodos se encuentra en estado IDLE. Cuandoel nodo escucha el primer paquete STARTUP, se asigna la distancia del pa-quete, toma al emisor como nodo padre y transmite por broadcast un nuevopaquete STARUP a sus vecinos, que contiene su distancia incrementada en1. Luego pasa al estado ITERATE.

IDLE

124


Receiving(STARTUP)//Recibe el primer STARTUPbegin

distance := STARTUP.hop;parent := sender;countAck := |N(x)|;STARTUP.hop++;send STARTUP to N(x);become ITERATE;

end

En el estado ITERATE, si el nodo recibe un paquete STARTUP quecontiene una distancia menor al sumidero, actualiza su distancia a ese va-lor, y envıa por broadcast un nuevo paquete STARTUP con su distanciaincrementada en 1. Si el nodo recibe un ACK, decrementa un contador quepermite detectar cuando todos sus vecinos menos el padre han alcanzado laconvergencia. En ese momento, envıa su propio ACK al nodo que marco co-mo padre.

ITERATE

Receiving(STARTUP)begin

send ACK to sender;if distance > STARTUP.hop then

distance := STARTUP.hop;countAck += |N(x)|;STARTUP.hop++;send STARTUP to N(x);

endifend

Receiving(ACK)begin


send ACK to parent;become DONE;

endifend

125


Como se explica en la seccion 8.1 de [66], para detectar la terminacionlocal se debe introducir el acuse de recibo. El sumidero, con el rol de inicia-dor, envıa un paquete STARTUP a todos sus vecinos. Cuando un nodo xen estado IDLE recibe el primer STARTUP, actualiza su distancia al sumi-dero, y define como padre al nodo emisor. Luego envıa su nueva distanciaa todos sus vecinos. Para todos los siguiente paquetes STARTUP que reci-be, responde con un ACK. Si la distancia que contiene el paquete es menorque la que el nodo x tiene asignada actualmente, x actualiza su distancia,y vuelve a notificar a sus vecinos por broadcast con un paquete STARTUP.Por cada paquete STARTUP que x ha enviado, debera recibir un ACK decada vecino. Cuando x recibe todos los acuse de recibo pendientes, pasa alestado de terminacion local en x.

M-SPIN Negociacion

Segun descripto en [60]. La negociacion es muy similar a la de SPIN-BC,excepto por el comportamiento del nodo al recibir el paquete ADV. Si elanuncio proviene de un nodo mas cercano al sumidero, no participa de lanegociacion.

Valores de estadoS = {INITIATOR, IDLE, DIFFUSE, GATHER, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}


Tipos de mensaje{ADV, REQ, DATA}

Al comenzar, el nodo que posee un nuevo dato lo anuncia por broadcasta sus vecinos. Luego pasa al estado DIFFUSE.


send(ADV) to N(x);become DIFFUSE;

end

126


El resto de los nodos se encuentra en estado IDLE. Al escuchar un pa-quete de anuncio, el nodo inspecciona la distancia del emisor, y si es mayorque la propia, inicia la alarma de supresion de peticion, pasando al estadoWAIT. Si el emisor del ADV esta a menor distancia del sumidero, el nodopasa al estado DONE de terminacion local, sin participar de la negociacion.

IDLE

Receiving(ADV)begin

if distance < ADV.hop thenset alarm := c(x) + u(I)source := sender;become WAIT;

else//Si no esta a menor distancia,//no participabecome DONE;

endifend

En el estado WAIT, el nodo se encuentra negociando el dato. Si la alarmade supresion expira, el nodo envıa la peticion por broadcast, especificando elnodo origen del anuncio, y pasa al estado GATHER. Si antes de expirar laalarma escucha un paquete REQ, cancela la alarma suprimiendo su propiapeticion, y pasa al estado GATHER. Asimismo, si antes de expirar la alar-ma escucha el paquete DATA, cancela la alarma suprimiendo la peticion,anuncia por broadcast el nuevo dato y pasa al estado DIFFUSE.

WAIT


REQ.source = source;send REQ to N(x);become GATHER;

end

Receiving(REQ)begin

//Si escucha un pedido por el mismo dato

127


if source = REQ.source thenunset alarm; //Suprime la peticionbecome GATHER;

endifend



end

En el estado DIFFUSE, el nodo se encuentra a la espera de peticionespor el dato que anuncio. Si escucha un paquete REQ para sı mismo, res-ponde enviando por broadcast el paquete DATA y pasa al estado DONE determinacion local. Si escucha un paquete ADV que proviene de un nodo mascercano al sumidero, pasa al estado DONE, asumiendo que no es necesariocontinuar con la negociacion.

DIFFUSE

Receiving(REQ)begin



endifend

Receiving(ADV)begin

//Si un nodo mas cerca del sumidero//anuncia el dato, ya no es necesario//continuar activoif ADV.hop < distance then

become DONE;endif

end

128


En el estado GATHER, el nodo se encuentra negociando el dato. Cuandoescucha el paquete DATA esperado, anuncia por broadcast el nuevo dato ypasa al estado DIFFUSE.

GATHER



end

5.2.3. Complejidad M

Como se define en la seccion 5, la complejidad M es el costo en mensajesdel algoritmo, es decir, la cantidad de transmisiones de mensajes necesariaspara completar la ejecucion del protocolo.

Complejidad M de M-SPIN Distancia

Se omite del analisis de M-SPIN Distancia, los mensajes ACK, por seruna construccion teorica que facilita el analisis. Los ACK no son menciona-dos en el trabajo original de M-SPIN [60].Sean n el numero de vertices o nodos de la red, y d el diametro de la red(la mayor distancia entre dos nodos). Un nodo puede actualizar su distan-cia una cantidad maxima de veces equivalente a d, dado que hay d posiblesvalores de distancia al sumidero. Como cada vez que actualiza su distancia,transmite un mensaje STARTUP:

M [M-SPIN D] ≤ n· dn = numero de vertices o nodos de la redd = diametro de la red

Dado que la maxima distancia que puede haber entre dos nodos de ungrafo de n nodos es n − 1, entonces d ≤ n − 1 y la formula anterior puedeexpresarse como:M [M-SPIN D] ≤ n· (n− 1) = n2 − n ≤ n2

Un analisis diferente puede hacerse, observando que M-SPIN Distanciatiene la misma forma que Iterated Construction (Bellman-Ford distribuido),donde todos los enlaces tienen el mismo costo (que es 1 salto). Asumiendo

129


un canal compartido, en cada iteracion, el nodo x envıa su nueva distanciapor broadcast a sus vecinos, transmitiendo un mensaje STARTUP. Como sesabe que el protocolo converge a lo sumo en n− 1 iteraciones [65]:

M [M-SPIN D] ≤ n· (n− 1) = n2 − n ≤ n2

n = numero de vertices o nodos de la redd = diametro de la red

M [M-SPIN D] ∼ O(n2)

Complejidad M de M-SPIN Negociacion

En [42] se analiza el tiempo de convergencia, estableciendo que la longi-tud maxima de ruta que atraviesa un dato es d, que equivale al diametro dela red.

Escenario 1 Para negociar la informacion, cuando un nodo x generaun dato, transmite por broadcast un mensaje ADV anunciandolo. Si todoslos nodos, menos el generador y el sumidero, estan a la misma distancia,el nodo generador esta a distancia 2, el sumidero a distancia 0, y el restode los nodos a distancia 1. Entonces, d = 2. El generador anuncia el datocon un mensaje ADV, n− 2 nodos peticionaran el dato con mensajes REQ,y el generador debera responder las peticiones con mensajes DATA. Luegolos n − 2 nodos anunciaran el dato con mensajes ADV. El primer anuncioque reciba el sumidero iniciara su propia negociacion, agregando un mensajeREQ y un DATA.

ADV = 1 + n− 2REQ = n− 2 + 1DATA = n− 2 + 1M [M-SPIN N] ≤ 3· (n− 1)n = numero de vertices o nodos de la red

M [M-SPIN N] ∼ O(n)

Escenario 2 Puede pensarse que se transmiten como mınimo 3 mensa-jes por cada salto que debe atravesarse. Suponiendo que el diametro de Ges el maximo posible, n− 1, y el nodo mas alejado del sumidero anuncia undato, entonces se ejecutaran n− 1 negociaciones de 3 mensajes cada una.

M [M-SPIN N] ≤ 3· (n− 1)n = numero de vertices o nodos de la red

130


M [M-SPIN N] ∼ O(n)

En ambos escenarios, todos los nodos participan de la negociacion. Encualquier otro escenario, la cantidad de nodos que participan puede ser me-nor que n, por lo que la cantidad de negociaciones serıa menor, y la cantidadde mensajes tambien. Entonces puede decirse que O(n) es el orden M de lacantidad de mensajes de negociacion, y 3· (n− 1) una cota superior.

5.2.4. Detalles de implementacion

Se implemento la familia de protocolos SPIN, SPIN-BC y SPIN-RL.El modulo SPIN implementa la secuencia de negociacion basica. El modu-lo SPIN-BC tiene una secuencia de negociacion diferente, aprovechando elcanal compartido y suprimiendo peticiones, y SPIN-RL lo mejora con larepeticion de peticiones y el lımite de reenvıos. Por simplicidad, todos losprotocolos de la familia almacenan los datos en una cache sin lımite. M-SPINse implementa extendiendo SPIN-RL, con la fase de asignacion de distanciaal sumidero, y la restriccion de participar en la negociacion solo si la distan-cia al sumidero es menor que la del nodo anunciante.

La jerarquıa de clases para los protocolos SPIN desarrollados puede verseen la figura 5.2.

131


Figura 5.2: Jerarquıa de modulos de diseminacion

132


Registro de anuncios

En SPIN-PP se procesan todos los anuncios recibidos, enviando peticio-nes y datos a una direccion especıfica. En SPIN-BC es necesario registrarcada anuncio recibido para poder enviar peticiones no suprimidas. Se utili-zara un temporizador de peticion por cada anuncio recibido, al expirar, seenvıa la peticion. Si se escucha una peticion de otro nodo por un dato cuyoanuncio se registro, se cancela el temporizador, suprimiendo la peticion.

Repeticion de pedidos

En SPIN-BC un nodo puede suprimir sus peticiones si escucha que otronodo ha pedido el mismo dato. Dado que en un canal no ideal puede darseque al transmitir el dato anunciado, algun nodo que lo espera no lo reciba,en SPIN-RL cada nodo mantiene registro de todos los anuncios recibidos.Si no recibe el dato transcurrido un cierto periodo de tiempo posterior alpedido enviado o suprimido, el nodo vuelve a enviar la peticion, indicandoen la cabecera el nodo que originalmente anuncio el dato. Se utilizara untemporizador de recepcion del dato, que se programa a partir del momentoen que se envıa o suprime la peticion. Cuando se suprime la peticion, elloimplica que se ha escuchado un pedido de otro nodo por el mismo dato, o seha recibido el dato directamente. Al expirar el temporizador de recepcion,se repite la peticion solo si el dato no esta ya en la cache, y se vuelve aprogramar el temporizador de recepcion para ese dato.

Lımite de reenvios

En SPIN-RL, si un nodo envıa un dato, luego se debe esperar una can-tidad de tiempo predefinida antes de volver a enviar el mismo dato. Se uti-lizo un registro de envıos con marcas de tiempo, para controlar los reenvıos.Si se recibe un pedido por un dato, y todavıa no ha transcurrido el tiempode espera de reenvıo, simplemente se ignora el pedido. De lo contrario, seresponde el pedido actualizando la marca de tiempo a ese momento.

Paquete M-SPIN

En el fragmento de codigo 5.1 puede observarse la definicion del paqueteM-SPIN:

Fragmento de codigo 5.1: Paquete M-SPIN

1 packet SPINPkt extends NetwPkt {

2

3 int hops;

4 int advSource;

5 int meta;

133


6 int finalDestAddr;

7 int initialSrcAddr;

8 }

Donde:

hopses cantidad de saltos al sumidero

advSourcees la direccion del nodo que originalmente anuncio el dato

metaes el metadato del dato anunciado o solicitado

finalDestAddres la direccion del nodo destino final del paquete

initialDestAddres la direccion del nodo origen del paquete

Se ha definido como longitud de cabecera un valor de 24 bits. El mismovalor se utilizara en todos los modulos de red.

Ajuste de tiempos de espera

Como M-SPIN extiende a SPIN-RL, existen varios tiempos de esperaque pueden ser ajustados para mejorar el desempeno del protocolo:

sendAgainWaites el tiempo para enviar un dato nuevamente si ya se envio

requestAgainWaites el tiempo para volver a pedir un dato

requestSuppressWaites el tiempo para esperar suprimir un pedido, es decir, el tiempo durante elcual se espera que otro nodo solicite el mismo dato, en cuyo caso la propiapeticion no se envıa

requestTimescantidad de veces que se repite el pedido por un dato como maximo

134


Se ha observado que si la espera es muy pequena o muy grande, la tasa deexito se empeora. Se realizo un lote de simulaciones de ajuste que resulto enlos siguientes valores de mejor desempeno:

sendAgainWait 100 msrequestAgainWait 100 msrequestSuppressWait 150 msrequestTimes 4

5.2.5. Pseudocodigo

Algoritmo 2: M-SPIN Procesar paquete de aplicacion

1 agregar datos a cache2 crear paquete ADV3 entregar al enlace para transmision broadcast

Algoritmo 3: M-SPIN Procesar paquete STARTUP

1 if saltos del paquete < mi distancia then2 asignar la distancia del paquete a mi distancia3 incrementar la distancia del paquete4 entregar al enlace para retransmision por broadcast

5 else6 descartar7 end

135


Algoritmo 4: M-SPIN Procesar paquete ADV de anuncio

1 if el dato anunciado no esta en cache Y no esta siendo negociadothen

2 if direccion final = broadcast O distancia del emisor > midistancia then

3 programar temporizador de supresion de peticion4 else5 descartar6 end


Algoritmo 5: M-SPIN Procesar paquete REQ de pedido

1 if origen de anuncio = mi direccion then2 if paso el tiempo mınimo entre reenvıos then3 crear paquete de datos4 entregar al enlace para transmision por broadcast


8 else9 if hay temporizador de supresion de pedido programado then

10 cancelar el temporizador11 programar temporizador de repeticion de pedido


15 end

136


Algoritmo 6: M-SPIN Procesar paquete DATA de datos

1 if el dato esta siendo negociado then2 cancelar temporizador de repeticion de pedido3 agregar el dato a la cache

4 if direccion final = mi direccion O direccion final = broadcastthen

5 entregar el dato a la aplicacion6 end7 crear paquete anuncio8 entregar al enlace para transmision broadcast


Algoritmo 7: M-SPIN Expira temporizador de repeticion o supresionde pedido

1 if el dato no esta ya en cache Y no se supero la cantidad de pedidosrepetidos then

2 crear paquete de pedido3 entregar al enlace para transmision por broadcast4 programar temporizador de repeticion de pedido

5 end

137

5.3. CONSCIENCIA DE RECURSOS CON SAMF

5.3. Consciencia de recursos con SAMF


En el trabajo que desarrolla Flow Augmentation, se mencionan comofuturas direcciones de investigacion [12]:

Efectos de la densidad de nodos y variaciones de energıa residual sobreel algoritmo

Aplicacion de la metrica de enlace a encaminamiento por demanda

Consideracion de cuestiones de la MAC

Utilizacion de niveles discretos de energıa residual

Es importante tener en mente que este es un protocolo que requiere man-tenimiento de tablas de encaminamiento. El costo del camino es la suma decostos de cada enlace y los caminos se calculan con cualquier algoritmo decamino mas corto, como Bellman-Ford. En el trabajo de [12] no se tiene encuenta la energıa para calcular las rutas de menor costo ni de intercambiode mensajes de control.

SAMF (Self-adapting Maximum Flow Routing) [59] es un protocolo masrecientemente investigado que, de manera similar a Flow Augmentation, asig-na costos de enlace relacionados a la energıa residual, y estos costos sonactualizados cada cierta cantidad de tiempo.

En [59] se dice que en general hay dos fases de operacion en una WSN.Una fase de diseminacion, donde se difunde informacion de control paracambiar la tarea de sensado, y la recoleccion, donde se transmiten los datosa un sumidero o punto de recoleccion. SAMF encamina la maxima carga detrabajo sostenible dadas las restricciones de ancho de banda, energıa y re-cursos, y se adapta dinamicamente cambios en estas restricciones. Se modelala red como un grafo dirigido, donde cada nodo es un vertice y los enlacesentre nodos son las aristas. Sean:

e = Un enlacev = El nodo origen de eB(e) = El ancho de banda del enlaceCPU(v) = El poder de computo en el nodo origen (velocidad de proceso,numero de paquetes que puede procesar por unidad de tiempo)E(v, e) = La energıa requerida para recibir o generar un paquete de datosy enviarlo a traves del enlaceP (v) = La energıa en el nodo origenF (e) = Flujo en paquetes que atraviesa el enlace

138


C(e) = Capacidad del enlace (la maxima cantidad de paquetes que puedenenviarse por e en una unidad de tiempo)

El modelo plantea una capacidad de enlace, limitada por el mınimo entretres capacidades:

F (e) <= C(e) = min{B(e), CPU(v), P (v)E(v,e)}

La red entera entonces puede modelarse como una red de flujo [59].

Encaminamiento

El encaminamiento implementa una estrategia avida, siempre encaminapaquetes por el camino al sumidero que tiene la maxima capacidad residual.Entonces, se dice que la capacidad residual es usada como metrica de en-caminamiento. Mas precisamente, el nodo elige el enlace que pertenece alcamino de mayor capacidad residual entre todos los caminos que llevan alsumidero. El mejor enlace es el que pertenece al camino mas corto, entreaquellos caminos de maxima capacidad residual.

Calculo de capacidad por epoca

Para reducir el costo de calcular una y otra vez la capacidad residual delos caminos al sumidero, las metricas de encaminamiento se mantienen sinvariacion por un perıodo de tiempo, la epoca, y se recalculan al comienzode cada epoca.En este sentido, todos los paquetes procesados por un nodo enuna determinada epoca, son encaminados por el mismo camino.Las capacidades residuales se calculan al final de la epoca, substrayendo dela capacidad nominal el costo de todos los paquetes encaminados en esaepoca.

Luego, para el calculo de la capacidad residual de cada camino (cons-traint), de cada enlace se mantienen los atributos enumerados en la tabla 5.2.

Cada nodo, a su vez, tiene los atributos enumerados en la tabla 5.3

139


Atributo Descripcion

residual capacityLa cantidad de paquetes por unidad de tiempo que sepueden enviar por el enlace en la nueva epoca.

link use Cantidad de paquetes enviados por el enlace.

link capacityLa cantidad de paquetes por unidad de tiempo que sepueden enviar por el enlace (ancho de banda).

constraint Capacidad en cantidad de paquetes en la epoca.

path capacityCuando se recibe un mensaje por el enlace, se asigna elmınimo entre constraint y la capacidad que asigno elnodo emisor al mensaje.

path hopCuando se recibe un mensaje por el enlace, se asigna lacantidad de saltos que trae el mensaje, incrementadaen uno.

packet energyLa cantidad de energıa necesaria para transmitir unpaquete.

Cuadro 5.2: Atributos de cada enlace SAMF

Atributo Descripcion

residual energySe actualiza en cada epoca, sumando node power, yrestando energy use.

node power Es lo que el nodo pudo recargar en la epoca anterior.delta T Tiempo que transcurre entre cada epoca.

energy use

Acumula la energıa utilizada en transmisiones duranteuna epoca. Incrementa cada vez la energıa necesariapara transmitir un paquete. Se pone en 0 cada vez quecomienza una nueva epoca.

residual cpuCantidad de paquetes que se pueden procesar por uni-dad de tiempo para la nueva epoca.

packet cpuLa cantidad de energıa necesaria para procesar un pa-quete.

cpu capacityCantidad de paquetes que se pueden procesar por uni-dad de tiempo.

cpu use

Acumula la energıa utilizada en procesamiento. Incre-menta cada vez la energıa necesaria para procesar unpaquete. Se pone en 0 cada vez que comienza una nue-va epoca.

Cuadro 5.3: Atributos de cada nodo SAMF

140


Cuando cambia la epoca, cada nodo vuelve a calcular la capacidad decada enlace (constraint) para la nueva epoca. La energıa residual del nodosuma la energıa que el nodo haya podido cargar y resta el uso en la epocaanterior. La capacidad de un enlace (ancho de banda) para la epoca nuevase calcula como el mınimo entre:

1) transmisiones residuales del nodo:

ErreP

Er = Residual energyeP = Packet energy

Esto es, cuantos paquetes pueden transmitirse con la energıa residual

2) proceso residual del nodo:

CPUrcpup

CPUr = Residual CPUcpup = Packet CPU

Esto es, cuantos paquetes pueden procesarse con la CPU residual

3) transmisiones residuales del enlace:

Cr·∆TCr = Residual capacity

Cuantos paquetes pueden enviarse con el ancho de banda residual

La intencion es que si en la epoca anterior se excedio el uso de la capaci-dad asignada, la capacidad para la epoca que sigue sera menor, intentandocompensar y balancear el flujo.

El sumidero dispara el intercambio de paquetes INTEREST al comienzode cada epoca, que permiten ejecutar en la red el algoritmo Bellmand-Forddistribuido con iniciador unico, para calcular los caminos de costo mınimoal sumidero (con las capacidades actualizadas) con complejidad de mensajespolinomial. El algoritmo pertenece a una clase de estrategias denominadadistance vector. En cada iteracion, la entidad envıa su vector de distanciaque contiene informacion de la ruta y el costo al sumidero. En [65] se diceque este es un enfoque costoso en complejidad M (cantidad de mensajes).

141


Evaluacion

Para la evaluacion se hizo foco en la escalabilidad del protocolo, evaluan-do la respuesta de las siguientes metricas en funcion de la cantidad de nodos:

Metrica Descripcion

flujo maximoConsumo total de energıa al variar la cantidad de no-dos.

longitud de rutaLa cantidad promedio de saltos en el camino al sumi-dero.

deuda maxima

Es la maxima deuda de capacidad observada durantela simulacion. Representa un uso de capacidad supe-rior al asignado para alguna epoca, compensado en lasiguiente.

interesCantidad total de paquetes INTEREST intercambia-dos por epoca. No se aclara si es el promedio de todaslas epocas.

Cuadro 5.4: Metricas de SAMF

La evaluacion se realizo con Omnet++, asumiendo un canal ideal (sinutilizar una pila completa de protocolos). Este trabajo es muy similar al deFlow Augmentation [12], en donde en cada epoca, el flujo hacia un nodose aumenta o disminuye sobre la base de su energıa residual, y la energıade transmision y recepcion necesarias para utilizar el enlace a ese nodo.SAMF innova asumiendo nodos que pueden cosechar energıa, por lo queen cada epoca, la capacidad residual puede aumentar o disminuir. Ademas,incorpora la capacidad de procesamiento y el ancho de banda a la metricade encaminamiento.


SAMF Capacidad

A continuacion se ha elaborado la especificacion del algoritmo de calculode capacidad, segun descripto en [59]. Se asume un canal ideal no compar-tido para este analisis.



142


Tipos de mensaje{INTEREST, ACK}

Variables{countAck, parent}

Al comenzar, el sumidero o nodo iniciador envıa el primer paquete IN-TEREST a todos su vecinos, con un valor inicial de capacidad muy alto, yaque en el sumidero los recursos no son acotados, y el identificador de epocaactual. Cuando el sumidero recibe un paquete ACK, decrementa un conta-dor que permite detectar la terminacion local, cuando llega a cero. Cuandorecibe un paquete INTEREST, simplemente acusa su recibo respondiendocon un ACK al emisor.


send(INTEREST) to N(x);countAck := |N(x)|;

end

Receiving(ACK)begin


become DONE;endif

end

Receiving(INTEREST)begin

send(ACK) to sender;end

El resto de los nodos comienza en estado IDLE. En este estado, al recibirel primer paquete INTEREST, el nodo inspecciona el identificador de epoca,y si difiere de la conocida, actualiza su valor y recalcula las capacidades deenlace para la nueva epoca. Luego, actualiza la tabla de encaminamiento yestablece al nodo emisor como su nodo padre. Entonces, determina la ca-pacidad de la mejor ruta conocida (mayor capacidad, y menor cantidad de

143


saltos a igual capacidad), y transmite un paquete INTEREST con la capaci-dad calculada a todos sus vecinos menos el padre. Finalmente pasa al estadoITERATE.

IDLEReceiving(INTEREST)//Recibe el primer paquetebegin

// Nueva epocaif INTEREST.epoch != epoch then

Recompute contraints;epoch := INTEREST.epoch;

endifUpdate routing table(INTEREST);parent := sender;INTEREST.bestGate := Get best gate();send(INTEREST) to N(x);countAck := |N(x)|;become ITERATE;

end

En el estado ITERATE, si el nodo recibe un nuevo paquete INTER-EST, actualiza la tabla de encaminamiento con la capacidad que contiene elpaquete, y determina si ha cambiado la mejor ruta conocida. En caso afir-mativo, envıa la nueva mayor capacidad a todos sus vecinos, incrementandola cantidad de ACK esperados. Si recibe un paquete ACK, decrementa elcontador. Cuando el contador de ACK llega a cero, el nodo envıa su propioACK al padre y pasa al estado DONE de terminacion local.

ITERATEReceiving(INTEREST)begin

send(ACK) to sender;bestGateUpdated := Update routing table(INTEREST);if bestGateUpdated = true then

INTEREST.bestGate := Get best gate();send(INTEREST) to N(x);countAck += |N(x)|;

endifend

144


Receiving(ACK)begin


send(ACK) to parent;become DONE;

endifend

En SAMF, el establecimiento de las rutas de mayor capacidad se haceutilizando un algoritmo con la estructura de Bellman-Ford distribuido deorigen unico[59], tambien sugerido en Flow Augmentation[12].

Como se describe en la seccion 8.1 de [66], para detectar la terminaciondel algoritmo se debe introducir el acuse de recibo de los mensajes quese envıan con la mejor capacidad conocida. El sumidero, nodo iniciador,comienza el algoritmo enviando el paquete INTEREST conteniendo un valorde capacidad muy grande a los nodos vecinos. Cuando un nodo x recibeel paquete INTEREST por primera vez, define al emisor como su padre,y reenvıa el paquete INTEREST con la mejor capacidad que conoce a suspropios vecino. Cuando el nodo x recibe nuevos paquetes INTEREST de susvecinos, responde con ACK. Si algun paquete INTEREST de los recibidosproviene de una mejor ruta (contiene una capacidad mayor o igual pero conmenor cantidad de saltos) que la que el nodo x conoce, este actualiza sucapacidad, y vuelve a emitir un paquete INTEREST con este nuevo valor, atodos sus vecinos. Una vez que el nodo x recibe los paquetes ACK de cadapaquete INTEREST que envio, transmite su propio ACK al nodo padre, ypasa al estado terminal, alcanzandose la terminacion local.

SAMF Encaminar

Especificacion del algoritmo de encaminamiento de SAMF, segun des-cripto en [59].

Valores de estadoS = {INITIATOR, IDLE, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}


145


Tipos de mensaje{DATA}

El nodo iniciador es el que tiene un nuevo dato para encaminar. Comien-za la ejecucion del protocolo inspeccionando su tabla de encaminamiento yseleccionando la mejor ruta (mayor capacidad) al destino. Luego, envıa elpaquete de datos al siguiente nodo en la ruta y pasa al estado DONE determinacion local, dado que no se requiere alguna otra intervencion.


y := Next hop(DATA);send(DATA)to y;become DONE;

end

El resto de los nodos, comienzan en estado IDLE. Al recibir un paqueteDATA, el nodo revisa su tabla de encaminamiento y selecciona la mejor rutaal destino (siempre el sumidero), y reenvıa el paquete al siguiente nodo enla ruta. Luego pasa al estado DONE, ya que no se requiere otra intervencion.

IDLEReceiving(DATA)begin

y := Next hop(DATA);send(DATA) to y;become DONE;

end

Cabe senalar que solo los nodos a lo largo de la ruta participan en elencaminamiento.


Como se definio en la seccion 5, la complejidad M es el costo en mensajesdel algoritmo, es decir, la cantidad de transmisiones de mensajes necesariaspara completar la ejecucion del protocolo.

146


Complejidad M de SAMF Capacidad

SAMF Capacidad tiene el mismo comportamiento que el protocolo Ite-rated Construction (Bellman-Ford distribuido) presentado en [65], la tablade encaminamiento se construye de forma iterativa. En cada iteracion, cadanodo comunica su mejor capacidad al sumidero a todos sus vecinos y luegode recibir la mayor capacidad de sus vecinos, recalcula ese valor. Asumiendoun canal compartido, en cada iteracion, el nodo x envıa un mensaje porbroadcast, y dado que el proceso converge en n - 1 iteraciones como maximo[65]:

M [SAMF Capacidad] ≤ n· (n− 1) = n2 − n ≤ n2

n = numero de vertices o nodos de la red

M [SAMF Capacidad] ∼ O(n2)

Complejidad M de SAMF Encaminar

SAMF Encaminar se basa en las tablas construidas para la epoca co-rriente. La cantidad de saltos que pueden requerirse para que el paquetede datos llegue a destino esta acotada por el diametro maximo que puedeposeer la red.

M [SAMF Encaminar] ∼ d ≤ n− 1d = diametro de la red

M [SAMF Encaminar] ∼ O(n)


Paquete SAMF

En el fragmento de codigo 5.2 puede observarse la definicion del paqueteSAMF:

Fragmento de codigo 5.2: Paquete SAMF

1 packet SAMFPkt extends NetwPkt {

2 int pathHops;

3 double pathCapacity;

4 long epochId;

5 int finalDestAddr;

6 int initialSrcAddr;

7 }

147


A continuacion se describe cada campo del paquete SAMF:

pathHopses la cantidad de saltos de la mejor ruta conocida

pathCapacityes la capacidad de la mejor ruta conocida

epochIdes la epoca actual

finalDestAddres la direccion del nodo destino final del paquete

initialDestAddres la direccion del nodo origen del paquete

Se utilizara el mismo paquete para representar el mensaje INTEREST yDATA. Se le define como longitud de cabecera un valor de 24 bits. El mismovalor se utiliza para todos los paquetes utilizados en la simulacion.

Mantenimiento de rutas

En SAMF[59] se utiliza una forma del algoritmo Bellman-Ford distribui-do para el mantenimiento de los costos de las rutas, el mismo sugerido enel algoritmo FA (Flow Augmentation)[12], que tambien modela flujo de red.Con cada paquete INTEREST se recibe informacion que permite actualizarel costo del enlace. El paquete trae la capacidad de la ruta conocida por elnodo remoto, y la cantidad de saltos al sumidero. En SAMF, la capacidadde la ruta, es la menor de las capacidades de los enlaces que la componen.El costo de la ruta es inverso a la capacidad, cuanto mas capacidad, menorcosto.

La librerıa de simulacion provee una clase cTopology que permite extraerla topologıa de la red y calcular el camino mas corto de un nodo a cualquierotro, pero la misma no puede utilizarse, porque utiliza como costo de rutala suma de los costos de los enlaces. En el protocolo Flow Augmentation elcosto de la ruta es la suma de los costos de los enlaces que la componen.Pero en SAMF, como se ha dicho, la capacidad de la ruta no es la sumade las capacidades de cada enlace, sino que se restringe a la menor de lascapacidades de los enlaces que la componen. Entonces, en SAMF la tabla deencaminamiento se construye a medida que se reciben paquetes INTEREST

148


con estructuras de datos, sin utilizar cTopology.

Diseno del modulo

Para modelar el protocolo, se ha excluido del modelo la posibilidad de co-sechar energıa. La metrica de encaminamiento solo tiene en cuenta la energıaresidual, y esta siempre va en disminucion. Se han excluido del calculo de lametrica de capacidad, el ancho de banda del enlace y el poder de computoen el nodo, modelando una red de dispositivos homogeneos.

En el SAMF original, al comienzo de cada epoca se define el creditodisponible de cpu, energıa y ancho de banda de cada enlace. Durante laepoca, se registra el consumo de cpu, ancho de banda utilizado por el enlacey la energıa utilizada. Al final de la epoca, si alguno ha excedido el creditoasignado, en la siguiente epoca el credito sera la capacidad nominal menosel exceso anterior, intentando balancear la carga en los enlaces y nodos.Para la implementacion, la metrica se ha simplificado utilizando solamentela energıa residual, con la hipotesis de que los nodos que mas paquetes hanencaminado durante una epoca, tendran un nivel de energıa residual menoral final de la epoca. Si su credito se basa solo en la energıa residual, losnodos mas cargados en una epoca dispondran de menos capacidad para laepoca siguiente, encaminando una menor cantidad de paquetes.

Asimismo, en el trabajo original se define la capacidad en cantidad depaquetes. Para este trabajo, a la capacidad dada por la energıa residual sele da valores discretos multiplos de 5, a partir de la carga de baterıa relativaque va de 0 a 100 %, siguiendo la sugerencia de [12].

Encaminamiento

El encaminamiento de SAMF simplemente selecciona de la tabla, el en-lace con la mejor capacidad al sumidero y reenvıa el paquete.

5.3.5. Pseudocodigo

A continuacion, se detallan los algoritmos 8, 9, 10, 11, 12, 13 implemen-tados en la clase C++ del protocolo.

149


Algoritmo 8: SAMF Procesar paquete de aplicacion

1 crear paquete de red2 if la direccion destino = broadcast then3 guardar paquete en cache de inundacion4 entregar al enlace para transmision broadcast

5 else6 buscar en la tabla la ruta de mejor capacidad al destino7 entregar al enlace para transmision al siguiente nodo

8 end

Algoritmo 9: SAMF Procesar paquete INTEREST

1 if epoca del paquete 6= epoca actual then2 actualizar la epoca actual a la epoca del paquete3 recalcular las restricciones en la tabla de enlace

4 end5 obtener la ruta A, la mejor de la tabla6 actualizar el enlace en la tabla con los datos del paquete7 obtener la ruta B, la nueva mejor de la tabla8 if ruta A 6= ruta B then9 crear paquete INTEREST con los datos de la nueva mejor ruta

10 entregar paquete INTEREST al enlace para transmision porbroadcast

11 end

150


Algoritmo 10: SAMF Procesar paquete DATA

1 if cantidad de saltos del paquete > maxima cantidad de saltos then2 descartar3 else if el paquete es inundacion then4 if el paquete no esta en la cache de inundacion then5 agregar a la cache de inundacion6 entregar al enlace para retransmision broadcast7 entregar a la capa de aplicacion

8 else9 descartar

10 end

11 else12 if destino final = mi direccion then13 entregar a la aplicacion14 else15 buscar la ruta de mejor capacidad en tabla16 entregar al enlace para retransmision al siguiente nodo

17 end

18 end

Algoritmo 11: SAMF Recalcular restricciones de enlace

1 for cada ruta en la tabla do2 actualizar la restriccion al valor de energıa residual3 end

151


Algoritmo 12: SAMF Actualizar enlace en la tabla

1 asignar la capacidad del enlace al mınimo entre la restriccion y lacapacidad que informa el paquete

2 asignar los saltos del enlace a la cantidad que informa el paquete + 1

Algoritmo 13: SAMF Obtener la mejor ruta a destino

1 iterar la tabla y seleccionar la ruta de mayor capacidad2 si hay rutas de igual capacidad, seleccionar la de menor cantidad de

saltos

152


5.4. Modulo de tecnica mixta: EA-SPIN

5.4.1. Diseno

Una manera de combinar las tecnicas de diseminacion de interes y cons-ciencia de energıa es utilizar la negociacion por metadatos de SPIN y elcontrol de flujo por epocas de SAMF en un mismo algoritmo de encami-namiento. En este trabajo se estudia esa posibilidad definiendo EA-SPIN(Energy Aware SPIN), una version de SPIN basada en M-SPIN y SAMF.

SAMF y M-SPIN tienen en comun la difusion de informacion de controlcon el sumidero iniciando el proceso periodicamente. Entonces, en EA-SPIN,ademas de registrarse la distancia al sumidero como lo hace M-SPIN, en lafase periodica de descubrimiento puede registrarse tambien la capacidad dela mejor ruta, como hace SAMF.

Saltear negociacion

Cuando un nodo sensor genera un dato, este se anuncia a todos sus veci-nos. En M-SPIN, solo aquellos vecinos mas cercanos al sumidero requeriranel dato. Si el nodo esta mas lejos del sumidero que el nodo que anuncio, noparticipa de la negociacion.

Con la modificacion que se introduce en EA-SPIN, el nodo que anunciael dato incluye en el anuncio la capacidad de la mejor ruta conocida. Losnodos vecinos que tienen una capacidad mejor o igual a la anunciada sonlos que peticionaran el dato de manera adelantada, utilizando un tiempomaximo de espera de supresion de pedido menor al normal. Los nodos ve-cinos que estan mas cerca del sumidero esperaran escuchar que algun otronodo ha peticionado el dato. Si el nodo mas cercano al sumidero no escuchaningun otro pedido, entonces debera negociar el dato. Si escucha un pedidode un nodo de mejor capacidad, se abstiene de continuar con la negociacion,asumiendo que otro nodo se ha propuesto a sı mismo para encaminar eldato.

Con este enfoque, se espera mejorar el problema de M-SPIN mencionadoen [60], donde unos pocos nodos son utilizados una mayor cantidad de veces,por lo que disipan su energıa mas rapidamente que el resto, intentandomejorar consumo de energıa en los nodos cercanos al sumidero.

Repeticion de anuncios

EA-SPIN ademas agrega la repeticion de anuncios. Si un dato anunciadono es pedido por un nodo vecino durante un intervalo de tiempo, el anuncio serepite hasta un numero maximo de veces. Cuando un nodo envıa un paquetede datos, este puede estar siendo esperado por mas de un vecino. Al recibirun dato, EA-SPIN no lo anunciara inmediatamente, sino que esperara un

153

5.4. MODULO DE TECNICA MIXTA: EA-SPIN

intervalo de tiempo al azar, para evitar colisiones que puedan producirse porla recepcion simultanea del dato enviado por broadcast.

Consciencia de energıa

El protocolo SAMF siempre va a consumir menos energıa por que notiene etapas de negociacion, y por lo tanto se utiliza una menor cantidadde mensajes. Existe una diferencia conceptual entre los dos protocolos debase, que radica en que extremo del enlace entre dos nodos decide el en-caminamiento. En SAMF, el que encamina es el nodo origen, enviando eldato generado al vecino en la mejor ruta al sumidero que el nodo tiene re-gistrado en sus tablas. En cambio en EA-SPIN el que encamina es el nododestino, que escucha un dato anunciado y solicita su recepcion, es decir, unnodo intermedio con mejor capacidad se postula a traves de la peticion paraencaminar el dato. El hecho de que toda la comunicacion en los protocolosEA-SPIN y M-SPIN se realice con broadcast permitirıa una mejor respuestaa cambios en la topologıa, por la naturaleza dinamica de negociacion de losprotocolos SPIN. En SAFM, el encaminamiento es por tablas, pero en EA-SPIN es por negociacion, y las tablas se mantienen para que la negociacionsea consciente de la energıa.


Para el analisis, las siguientes especificaciones se construyen bajo la res-triccion de confiabilidad total, por lo que no se modelan las repeticiones deanuncios ni de peticiones.

EA-SPIN Capacidad



Tipos de mensaje{START, ACK}

Variables{epoch, distance, countAck}

154


Al comenzar, el sumidero o nodo iniciador envıa por broadcast un pa-quete START a todos sus vecinos, que contiene un valor de capacidad muyalto, cantidad saltos al sumidero inicializada en cero, y el identificador deepoca actual. Por cada ACK que recibe, decrementa un contador iniciadoen un valor igual a la cantidad de vecinos. Cuando el contador llega a cero,todos los vecinos han determinado las capacidades de ruta y pasa al estadoDONE de terminacion local. Si recibe un paquete START, envıa un acusede recibo al nodo que lo emitio.


send(START) to N(x);countAck := |N(x)|;

end

Receiving(ACK)begin


become DONE;endif

end

Receiving(START)begin

send(ACK) to sender;end

El resto de los nodos comienza en estado IDLE. En este esstado, al re-cibir el primer paquete START, determina si ha cambiado la epoca. Encaso afirmativo, actualiza su identificador de epoca actual y recalcula lascapacidades de enlace para la nueva epoca. Luego actualiza la tabla de en-caminamiento y establece al nodo emisor como su nodo padre. Para seguir,envıa por broadcast un nuevo paquete INTEREST con la capacidad de lamejor ruta conocida. Finalmente pasa al estado ITERATE.

IDLEReceiving(START)begin

// Nueva epocaif START.epoch != epoch then

155


Recompute contraints;endifUpdate routing table(START);distance := START.hop;parent := sender;countAck := |N(x)|;send(START) to N(x);become ITERATE;

end

En el estado ITERATE, el nodo itera hasta recibir un ACK de cadavecino, para cada una de sus actualizaciones de mejor ruta, transmitidascon paquetes START. Al recibir un paquete START, responde con ACK alemisor y actualiza la tabla de encaminamiento con la informacion que traeel paquete. Si la mejor ruta a cambiado (hay una nueva ruta de mayor capa-cidad, o igual capacidad que la anterior pero con menor cantidad de saltos)o la distancia del nodo es mayor que la cantidad de saltos del paquete, elnodo notifica este cambio transmitiendo por broadcast un nuevo paqueteSTART con el nuevo valor de mayor capacidad y, como cantidad de saltos alsumidero, su distancia incrementada en 1. Cuando recibe un paquete ACK,decrementa el contador de acuses y cuando este llega a cero, envıa su propioACK al nodo definido como padre, pasando al estado DONE de terminacionlocal.

ITERATEReceiving(START)begin

send(ACK) to sender;bestPathChanged := Update routing table(START);if bestPathChanged = true || distance > START.hop then

if distance > START.hop thendistance := START.hop;

endifSTART.bestGate := Get best gate();START.hop = distance + 1;countAck += |N(x)|;send(START) to N(x);

endifend

Receiving(ACK)begin

156



send(ACK) to parent;become DONE;

endifend

EA-SPIN Negociar

La negociacion es similar a la que realiza M-SPIN, excepto por el pedi-do adelantado que realizan los nodos en la mejor ruta al sumidero, y porcancelar la negociacion si un nodo con mejor capacidad la ha iniciado.

Valores de estadoS = {INITIATOR, IDLE, DIFUSE, GATHER, DONE}SINIT = {INITIATOR, IDLE}STERM = {DONE}


Tipos de mensaje{ADV, REQ, DATA}

ParametrosRA = Maximo intervalo de espera para peticionar en forma adelanta-daRS = Maximo intervalo de espera para escuchar otro pedido y supri-mir el propio

Al comenzar, el nodo que tiene un nuevo dato para encaminar lo anunciapor broadcast con un paquete ADV, que incluye la capacidad de la mejorruta. Luego pasa al estado DIFFUSE.


send(ADV) to N(x);become DIFFUSE;

end

157


El resto de los nodos comienza en estado IDLE. Al recibir un paqueteADV, inspecciona la capacidad del emisor que viene en el paquete, y si elnodo conoce una ruta de mejor capacidad, inicia la alarma de supresion depeticion, que expirara en un tiempo al azar seleccionado en un intervalo me-nor que el que se utiliza para la espera normal de supresion de peticiones.Luego pasa al estado WAIT. Si al recibir el ADV, el nodo no posee mejorcapacidad, pero esta a menor distancia, inicia la alarma normal de supersionde pedido y pasa al estado WAIT. Si al recibir el paquete ADV el nodo noposee una ruta mejor ni esta a menor distancia, se abstiene de participarpasando al estado DONE de terminacion local.

IDLE

Receiving(ADV)begin

//Revisa si tiene mejor capacidad que el que anuncioif Better capacity(ADV) then

set alarm := c(x) + u(RA)source := sender;become WAIT;

else if distance < ADV.hop thenset alarm := c(x) + u(RS)source := sender;become WAIT;

else//Si no esta a menor distancia,//ni tiene mejor capacidad,//no participabecome DONE;

endifend

En el estado WAIT, al expirar la alarma de supresion, el nodo envıa porbroadcast el paquete REQ especificando el nodo origen del anuncio y pasaal estado GATHER. Si en estado WAIT escucha un paquete REQ por elmismo dato, cancela la alarma suprimiendo su propia peticion. Si el pedidoescuchado proviene de un nodo con una mejor ruta al sumidero, se detiene lanegociacion pasando al estado DONE de terminacion local. De lo contrario,el nodo pasa al estado GATHER. Si en estado WAIT el nodo escucha el datoesperado, cancela la alarma de supresion y anuncia por broadcast el nuevodato, pasando al estado DIFFUSE.

158


WAIT


REQ.source = source;send REQ to N(x);become GATHER;

end

Receiving(REQ)begin

//Si escucha un pedido por el mismo datoif source = REQ.source then

unset alarm; //Suprime la peticionif Better capacity(REQ) = false then

// Saltea negociacionbecome DONE;

else// Continua la negociacionbecome GATHER;

endifendif

end



end

En estado DIFFUSE, el nodo espera peticiones por el dato en negocia-cion. Si recibe una peticion par sı mismo, responde haciendo broadcast de unpaquete DATA, y luego pasa al estado DONE de terminacion local. Recor-dar que para el analisis se toma la base de SPIN-BC, que solo envıa el datouna vez por broadcast. Si en el estado DFFUSE recibe un paquete ADV deun nodo mas cercano al sumidero, pasa al estado DONE asumiendo que nose requiere mas su intervencion.

DIFFUSE

159


Receiving(REQ)begin



endifend

Receiving(ADV)begin

//Si un nodo mas cerca del sumidero//anuncia el dato, ya no es necesario//continuar activoif ADV.hop < distance then

become DONE;endif

end

En el estado GATHER, el nodo espera recibir el dato en negociacion. Sirecibe un paquete DATA, anuncia el nuevo dato enviando por broadcast unpaquete ADV a todos sus vecinos y pasando al estado DIFFUSE.

GATHER



end


Recordando las definiciones de la seccion 5, la complejidad M es el costoen mensajes del algoritmo, es decir, la cantidad de transmisiones de mensajesnecesarias para completar la ejecucion del protocolo.

Al igual que M-SPIN Distancia, y SAMF Capacidad, EA-SPIN Capaci-dad tiene la estructura de Bellman-Ford y ejecuta a lo sumo n−1 iteraciones(ver secciones 5.2.2 y 5.3.2), por lo que:

M [EA-SPIN Capacidad] ∼ O(n2)

160


EA-SPIN Negociar suprime mas rondas de negociacion que M-SPIN,porque si un nodo escucha que otro a la misma distancia o mayor ha pe-ticionado el dato anunciado, se abstiene de participar. En M-SPIN, si dosnodos a la misma distancia reciben un anuncio de un dato a mayor distan-cia del sumidero, ambos participan de la negociacion. Por lo tanto, puededecirse que la complejidad M de EA-SPIN es tambien:

M [EA-SPIN Negociar] ∼ O(n)


Paquete EA-SPIN

El paquete EA-SPIN extiende el paquete de M-SPIN con la informaciondel paquete SAMF, con la definicion del fragmento de codigo 5.3:

Fragmento de codigo 5.3: Paquete EA-SPIN

1 packet EASPINPkt extends SPINPkt {

2

3 int pathHops;

4 double pathCapacity;

5 long epochId;

6 bool routeType;

7 }

En el modulo de red se define como longitud de cabecera un valor de 24bits, el mismo valor que se utiliza para todos los modulos de red.

Ajuste parametrico de EA-SPIN

Se realizo un lote de simulaciones para ajustar los siguientes tiempos deespera:

sendAgainWaites el tiempo para enviar un dato nuevamente si ya se envio

requestAgainWaites el tiempo para volver a pedir un dato

requestSuppressWaites el tiempo para esperar suprimir un pedido

requestFirstWaites el tiempo de espera para pedir un dato de manera adelantada

161


repeatAdvWaites el tiempo de espera para repetir un anuncio

requestAgainTimescantidad de veces que se repite un pedido como maximo

repeatAdvTimescantidad de veces que se repite un anuncio como maximo

El ajuste de EA-SPIN se realizo independientemente del ajuste realiza-do para M-SPIN. Se observo nuevamente que si la espera es muy corta odemasiado larga, el desempeno empeora. El ajuste se orienta a la asignacionde esperas lo mas cortas posibles que no degraden el desempeno (exito, la-tencia, uniformidad de consumo) por la competencia por el medio. Se tuvoen cuenta el trabajo de [54], que describe los efectos de utilizar una fre-cuencia de muestreo demasiado alta (del orden de los 5ms) en la exactitudde la simulacion: una distancia significativa de los resultados respecto de larealidad.

Para la red definida, se encontro que con la siguiente configuracion selogra un mejor desempeno:

sendAgainWait 50 msrequestAgainWait 200 msrequestSuppressWait 300 msrequestFirstWait 150 msrepeatAdvWait 500 msrequestAgainTimes 7repeatAdvTimes 5

Totalizadores

Para analizar el comportamiento de los protocolos SPIN, se incluyeronen los modulos los siguientes contabilizadores de paquetes:

Algunas relaciones entre ellos:

nbAdvNew = nbAdvReceived - nbAdvNotProcessednbReqReceived = nbReqNotProcessed + nbReqProcessednbCacheSize = nbAdvSent - nbAdvRepeatnbCacheSize = nbDataForMe + ¡cantidad de muestras a sensar¿nbDataForMe = nbDataReceived - nbDataNotProcessed

162


Contabilizador Descripcion

nbAdv2Data Relacion entre la cantidad de paquetes de datosdestinados al nodo y la cantidad de anuncios dedatos que el nodo no posee

nbAdvDuplicated Anuncios recibidos duplicados

nbAdvFar Anuncios recibidos e ignorados por provenir de unnodo mas cercano al sumidero o con mejor capa-cidad

nbAdvNew Anuncios recibidos de datos que el nodo no posee

nbAdvNotProcessed Anuncios recibidos y descartados por alguna razon

nbAdvReceived Total de anuncios recibidos

nbAdvRepeat Anuncios enviados por duplicado

nbAdvSent Total de anuncios enviados

nbDataDuplicated Datos recibidos por duplicado

nbDataForMe Datos recibidos y destinados a este nodo

nbDataMaxHops Datos recibidos y descartados por superar el maxi-mo de saltos permitidos

nbDataNotProcessed Datos recibidos y descartados por alguna razon

nbDataPending Datos esperados y no recibidos

nbDataReceived Total de paquetes de datos recibidos

nbDataSent Total de paquetes de datos enviados

nbReqDuplicated Peticiones recibidas por un dato que ya ha sidoenviado y no ha transcurrido el tiempo de esperaentre reenviıos, por lo tanto se ignoran

nbReqForMe Peticiones recibidas destinadas a este nodo

nbReqImmediate Peticiones enviadas en adelanto

nbReqNotProcessed Peticiones recibidas no procesadas por algunarazon

nbReqProcessed Peticiones recibidas procesadas

nbReqReceived Total de peticiones recibidas

nbReqRepeat Peticiones enviadas por duplicado

nbReqSent Total de peticiones enviadas

nbReqSuppressed Peticiones suprimidas

nbSkipNegotiation Negociaciones salteadas

nbTotalSent Total de paquetes de negociacion enviados: anun-cios, peticiones y datos

nbCacheSize Tamano de la cache

Cuadro 5.5: Contadores para el analisis de SPIN

nbReqProcessed = nbDataSentnbReqRepeat = nbReqRepeat

163


5.4.5. Pseudocodigo

Algoritmo 14: EA-SPIN Procesar paquete de aplicacion

1 agregar datos a cache2 crear paquete ADV especificando la mejor capacidad conocida3 entregar al enlace para transmision broadcast4 programar temporizador de repeticion de anuncio

Algoritmo 15: EA-SPIN Procesar paquete STARTUP

1 if epoca del paquete 6= epoca actual then2 actualizar la epoca actual a la epoca del paquete3 recalcular las restricciones en la tabla de enlace

4 end5 obtener la ruta A, la mejor de la tabla6 actualizar el enlace en la tabla con los datos del paquete7 obtener la ruta B, la nueva mejor de la tabla

8 if ruta A 6= ruta B O cantidad de saltos del paquete < mi distanciathen

9 if cantidad de saltos del paquete < mi distancia then10 asignar a mi distancia la cantidad de saltos del paquete11 end12 crear paquete STARTUP con los datos de la nueva mejor ruta y

mi distancia + 113 entregar al enlace para transmision por broadcast


164


Algoritmo 16: EA-SPIN Procesar paquete ADV de anuncio

1 if el dato anunciado no esta en cache Y no esta siendo negociadothen

2 if direccion final = broadcast then3 programar temporizador de supresion de pedido normal4 else if tengo mejor capacidad que la especificada en el paquete

then5 programar temporizador supresion de pedido adelantado6 else if distancia del emisor > mi distancia then7 programar temporizador de supresion de pedido normal8 else9 descartar

10 end


Algoritmo 17: EA-SPIN Procesar paquete REQ de pedido

1 if direccion final 6= broadcast Y estoy negociando el dato Y no tengomejor capacidad then

2 cancelar temporizador de supresion de pedido3 else if origen de anuncio = mi direccion then4 if paso el tiempo mınimo entre reenvıos then5 crear paquete de datos6 entregar al enlace para transmision por broadcast


10 else if hay temporizador de supresion de peticion programado then11 cancelar el temporizador12 programar temporizador de repeticion de pedido


165


Algoritmo 18: EA-SPIN Procesar paquete DATA de datos

1 if el dato esta siendo negociado then2 cancelar temporizador de repeticion de pedido3 agregar el dato a la cache4 if direccion final = mi direccion O direccion final = broadcast

then5 entregar el dato a la aplicacion6 end7 crear paquete de anuncio8 entregar al enlace para transmision broadcast


Algoritmo 19: EA-SPIN Expira temporizador pedido

1 if el dato no esta ya en cache Y no se supero la cantidad de pedidosrepetidos then

2 crear paquete de pedido3 entregar al enlace para transmision por broadcast4 programar temporizador de repeticion de pedido

5 end

166


Algoritmo 20: EA-SPIN Expira temporizador de repeticion de anun-cio

1 if el dato nunca fue enviado Y no se supero la cantidad de anunciosrepetidos then

2 crear paquete de anuncio3 entregar al enlace para transmision por broadcast4 programar temporizador de repeticion de anuncio

5 end

5.5. Resumen de modulos desarrollados

En la siguiente tabla se enumeran los modulos C++ desarrollados parapoder llevar a cabo la simulacion con Omnet++.

Modulo Proposito

SAMF Modulo que implementa el protocolo de red conconsciencia de energıa SAMF

SPIN Implementa el protocolo de red de diseminacionSPIN

SPIN-BC Protocolo de red SPIN-BC

SPIN-RL Protocolo de red SPIN-RL

M-SPIN Protocolo de red M-SPIN

EA-SPIN Version de diseminacion M-SPIN con conscienciade energıa estilo SAFM

NetworkStudy Modulo de red base, con utilidades para conta-bilizar paquetes y totalizar consumo y niveles deenergıa

NetworkTracer Modulo de recoleccion de estadısticas

NodeApplLayer Modulo de aplicacion de nodo sensor

SinkApplLayer Aplicacion del sumidero

Cuadro 5.6: Modulos desarrollados

167

5.5. RESUMEN DE MODULOS DESARROLLADOS

168

Capıtulo 6

Simulacion y conclusiones

Para las simulaciones se utilizo la interfaz de red Nic802154 TI CC2420(802.15.4-2006) como es sugerido por el ejemplo de encaminamiento enredes de sensores que trae la herramienta, implementando CSMA no ra-nurado (nonbeacon-enabled unslotted CSMA-CA). La interfaz alternativaNic802154A (802.15.4a-2007) es apropiada para redes de muy baja cargasegun el estandar [28], por lo que se decidio no utilizar para los experimen-tos, ya que el patron de trafico seleccionado produce rafagas de transmisionesno soportadas por ALOHA.

Es importante mencionar que el modulo CSMA 802.15.4 que viene conel framework MiXiM 2.1 no implementa el modo ranurado, y solo funcionaen el modo competitivo.

El uso de CSMA no ranurado implica una importante limitacion al mo-delo: los nodos sensores no se sincronizan y deben mantener el tranceptorencendido todo el tiempo para poder recibir los frames. Debido a esta li-mitacion, los efectos del encaminamiento en la vida util de la red no seranevidenciados analizando la cantidad de tiempo que transcurre hasta el ago-tamiento de nodos. En lugar de ello, se utilizaron metricas de consumo entransmisiones.

Con respecto a la capa fısica se debe aclarar que se deshabilito el ruidotermico.

Las caracterısticas completas del modelo son descriptas en detalle en laseccion 4.2.

169

6.1. ESCENARIOS

6.1. Escenarios

Se hicieron simulaciones de red para los siguientes escenarios, con cadauno de los tres protocolos estudiados:

Escenario Descripcion Paquetes de datos1 Sensar 1 muestra en cada uno de los 79 nodos 79

2Sensar 100 muestras en cada uno de los 79 no-dos

7900

3 3 nodos sensan 100 muestras cada uno 300

4Sensar 1 muestra cada 1 m, en cada uno de los79 nodos, durante 24 h

113760

Cuadro 6.1: Escenarios simulados

6.2. Resultados

Se debe tener en cuenta que, en todos los estudios, las estadısticas inclu-yen los paquetes enviados para diseminar la tarea, y todos los paquetes decontrol, STARTUP e INTEREST.


Para la comparacion con las cotas teoricas, se asume que se ejecuto elalgoritmo de asignacion de capacidad/distancia una vez, y las negociacionesnecesarias para encaminar la cantidad total de paquetes de datos, dada porel escenario. La cota de complejidad M es un lımite superior muy alto decantidad de paquetes necesarios para completar la consulta y se espera quela metrica de las simulaciones este lejos de ese valor. Recordando, las cotassuperiores de cantidad de mensajes para la asignacion de distancia y la ne-gociacion son:

M [M-SPIN D] ≤ n· (n− 1) en una iteracion de asignacion de distancian = 80n· (n− 1) = 6,320

M [M-SPIN N] ≤ 3· (n− 1) por cada paquete a encaminar

Escenario 1: 6,320 + 79· 3· 79 = 25,043Escenario 2: 6,320 + 79· 100· 3· 79 ∼ 1, 9 millonesEscenario 3: 6,320 + 79· 3· 3· 79 = 77,420Escenario 4: 6,320 + 79· 1440· 3· 79 ∼ 27 millones

170

CAPITULO 6. SIMULACION Y CONCLUSIONES

Escenario Protocolo M cota M simulacion

1 M-SPIN 25.043 1.688

1 EA-SPIN 25.043 2.088

2 M-SPIN 1,9 millones 150.953

2 EA-SPIN 1,9 millones 153.564

3 M-SPIN 77.420 4.940

3 EA-SPIN 77.420 6.174

4 M-SPIN 27 millones 2,17 millones

4 EA-SPIN 27 millones 2,21 millones

Cuadro 6.2: Cantidad total de paquetes enviados en cada escenario

En la tabla 6.2 se compara la cota M, con la cantidad total de paquetesde red enviados en la simulacion.

171

6.2. RESULTADOS

6.2.2. Metricas obtenidas

Escenario 1

En el escenario 1 todos los nodos responden la consulta con un dato.

Figura 6.1: Escenario 1 - Latencia media en el sumidero

Figura 6.2: Escenario 1 - Tasa de exito

172


Figura 6.3: Escenario 1 - Overhead

Figura 6.4: Escenario 1 - Total de energıa de transmision

173

6.2. RESULTADOS

Figura 6.5: Escenario 1 - Media y maxima de saltos

Figura 6.6: Escenario 1 - Media y desviacion de energıa de transmision

174


Escenario 2

En el escenario 2, todos los nodos responden con 100 paquetes de datos.



175

6.2. RESULTADOS



176




177

6.2. RESULTADOS

Escenario 3

En este escenario, solo 3 nodos responden con 100 paquetes de datos.



178




179

6.2. RESULTADOS



180


Escenario 4

En el escenario 4, todos los nodos responden con 1440 paquetes, a razonde uno por minuto.



181

6.2. RESULTADOS



182




183

6.2. RESULTADOS

Consumo de energıa en transmisiones

Figura 6.25: Escenario 1 - Total de energıa vs. distancia al sumidero


184




185

6.2. RESULTADOS

Resumen de metricas

Escenario 1 SAMF M-SPIN EA-SPIN

Tasa de exito 1 0,87 0,98

Overhead 7 24 26

Energıa total detransmision (mWs)

26 51,9 52,2

Consumo de transmi-sion medio (mWs)

0,33 0,66 0,66

Desviacion estandardel consumo detransmision (mWs)

0,63 0,90 1,05

Latencia media (s) enel sumidero

0,02 0,22 1,91

Media de saltos en elsumidero

4 5 5

Maxima de saltos enel sumidero

8 9 9

Cuadro 6.3: Metricas de escenario 1



Overhead 5 20 20


2037,88 4675,36 3793,43


25,80 59,18 48,02


65,5 94,06 102,53


0,02 0,22 1,86


4 5 5


8 10 9


186




Overhead 5 19 21


86,05 153,38 153,35


1,09 1,94 1,94


3,03 4,33 5,15


0,02 0,25 2,02


5 5 5


6 8 7




Overhead 5 20 20


29.292 67.303 54.526


370,79 851,95 690,20


887,83 1.354,43 1.475,29


0,02 0,22 1,86


4 5 5


8 10 9


187

6.2. RESULTADOS

6.2.3. Analisis de confiabilidad

SPIN es un protocolo disenado originalmente para diseminar informa-cion a la totalidad de la red, y M-SPIN y EA-SPIN intentan transformarla diseminacion en encaminamiento convergente al sumidero. El diseno deEA-SPIN modifica la negociacion en tres etapas ADV-REQ-DATA para quelos nodos con mejor capacidad se ofrezcan primero para encaminar los datos,utilizando el modelo de capacidad de encaminamiento de SAMF.

La confiabilidad en M-SPIN y EA-SPIN nunca alcanza el 100 % en lassimulaciones realizadas. Esto puede deberse a que toda la comunicacionen estos protocolos, tanto en la fase de asignacion de distancia/capacidad,como en las negociaciones se realiza por broadcast. El modulo de enlace CS-MA802154 no envıa ACKs de frames broadcast, porque ası se se encuentraestablecido en el estandar IEEE 802.15.4-2006 [31], y por ello todas las trans-misiones de M-SPIN y EA-SPIN no tienen acuse de recibo en el enlace. Laconfiabilidad entonces depende en mayor medida de los protocolos de red ytransporte.

En la especificacion de SPIN no se aclara que sucede cuando un anun-cio no es respondido por ningun vecino. Para mejorar la tasa de exito seincluyo en el diseno de EA-SPN la repeticion de anuncios por una cantidadconfigurable. Tambien se evaluo la posibilidad de emitir paquetes ADV uni-cast directamente al siguiente nodo en la mejor ruta conocida, produciendoframes CSMA-ACK en el enlace, y de esta manera reducir la cantidad deanuncios perdidos, pero esto no mejoro el desempeno del protocolo. Segun elestandar, los ACK se envıan directamente, sin utilizar el mecanismo CSMA-CA [31], por lo que aumentaba la cantidad de descartes por interferencia.

Se observa que la cantidad de colisiones se ve afectada por la carga delprotocolo de red, e incide significativamente en el nivel de confiabilidad, de-pendiendo del diseno. El modulo de capa de enlace notifica a la capa dered cuando no puede transmitir un mensaje porque la cola esta llena, o seha superado el numero maximo de backoffs, pero en las simulaciones no seprodujeron descartes por esas causas.

Los efectos de repetir anuncios pueden observarse en el resumen de metri-cas de la seccion 6.2.2. En todos los escenarios simulados la tasa de exitode EA-SPIN fue un poco mejor que la de M-SPIN. Intuitivamente puedepensarse que al agregar la repeticion de anuncios, se agregan mas mensajesal ciclo de negociacion y se esperara que el efecto sea un mayor numero decolisiones. Pero no resulto de esa manera en las simulaciones. Por ejemplo,en el escenario 4, se produjeron los siguientes totales de descartes de framespor interferencia:

188



Descartes por interfe-rencia

9.647 410.614 10.476

Cuadro 6.7: Total de frames descartados por interferencia

La menor cantidad de descartes en EA-SPIN puede deberse tambien alas modificaciones a la negociacion: cuando un nodo oye que otro nodo demejor capacidad esta negociando el dato, se abstiene de negociar, reduciendola cantidad de mensaje transmitidos. Probablemente, los tiempos de esperade EA-SPIN bastante largos disminuyen la competencia por el medio, conel efecto no deseado de un gran incremento en la latencia de recepcion delsumidero.

6.2.4. Consciencia de energıa

En los cuatro escenarios simulados, el consumo total de energıa en trans-misiones de EA-SPIN es similar o menor al de M-SPIN. En particular, sintener en cuenta la menor tasa de exito de M-SPIN:

Escenario M-SPIN EA-SPIN Ahorro

1 0,66 0,66 0 %

2 59,18 48,02 18 %

3 1,94 1,94 0 %

4 851,95 690,20 19 %

Cuadro 6.8: Consumo total de energıa en transmisiones

Lo mismo sucede con el consumo medio de energıa para transmisiones,que siempre es menor en EA-SPIN.

Sin embargo, la desviacion estandar del consumo en transmisiones es masalta en EA-SPIN y esto significa que el consumo es mas desparejo entre losnodos, aun habiendo incorporado la capacidad de ruta basada en la energıaresidual en el encaminamiento. Cuanto mas cerca se encuentra un nododel sumidero, encamina una mayor cantidad de paquetes y el consumo deenergıa de transmision difiere significativamente del consumo de los nodosmas alejados.

Ahora bien, las figuras 6.26 y 6.28 sugieren que las negociaciones evi-tadas y el uso de la capacidad de SAMF para decidir la participacion en elencaminamiento contribuyen a ahorrar energıa en los nodos mas cercanos alsumidero.

189

6.2. RESULTADOS

En particular, para los escenarios de respuestas transmitidas al sumiderodesde la totalidad de los nodos, se observan los consumos de transmisionpromedio segun la distancia de las figuras 6.29 y 6.30.

Figura 6.29: Escenario 2: Promedio de energıa de transmision por distancia

Figura 6.30: Escenario 4: Promedio de energıa de transmision por distancia

Es particularmente llamativo que la forma de la curva sea tan similarentre los dos escenarios. Observados los promedios, se debe aclarar que elconsumo total por nodo difiere bastante entre nodos a la misma distancia.Haciendo referencia a las figuras 6.25, 6.26, 6.27 y 6.28, las curvas sugierenque los cambios introducidos al protocolo suavizan el consumo total en tras-mision en los nodos a distancias mas cercanas al sumidero y disminuyen el

190


consumo promedio de nodos a la misma distancia. Un analisis mas extensopermitirıa comprobar si el efecto contribuye a prolongar la conectividad quelos sensores mas cercanos al sumidero proveen, para poder encaminar unamayor cantidad de informacion antes de que la red se particione.

6.2.5. Experiencia con MiXiM 2.1 y Omnet++ 4.1

La herramienta de simulacion seleccionada es gratis y de codigo abierto,tiene una comunidad de usuarios bastante pequena, pero activa. En generallas preguntas a foros de discusion son respondidas. Las utilidades estanda-res que provee (lınea de comandos, ambiente grafico, ambiente de depura-cion) permiten trabajar de manera fluida. En especial, la visualizacion dela transmision de mensajes de un nodo a otro en diagramas de secuencia, ylos archivos de eventos fueron de enorme utilidad para depurar los modulosdesarrollados. La ejecucion por lotes tambien es muy facil de parametrizar,lo que permitio ajustar los protocolos sin mayores dificultades.La gran fortaleza de Omnet++ podrıa decirse que es el desarrollo modular,y la reutilizacion de modulos. Tambien lo es la librerıa de simulacion, que dasoporte a la recoleccion de estadısticas de manera sencilla, si bien requierebastante programacion. Para utilizar variables globales se provee un modulopizarra al cual se accede con un mecanismo publisher/subscriber.Como gran debilidad puede decirse que en MiXiM los modulos agregados seliberan muy tempranamente, y pueden contener errores de diseno o confi-guracion. Algunos modulos provistos por MiXiM 2.1 y utilizados para estetrabajo, se encontraban en su primera version o migracion de frameworksanteriores y, por ejemplo, la plantilla para redes de sensores definıa una fre-cuencia de transmision de 2.4 GHz, y una modulacion BPSK, cuando enel estandar IEEE 802.15.4-2006 se establece que a esa frecuencia se utilizamodulacion O-QPSK. Mas aun, se descubrio que la sensibilidad configuradaen el modulo de capa fısica estaba siendo ignorada, y nodos distantes tenıanalcance de radio para comunicarse. En los foros se hallaron comentarios re-portando errores en otros modulos de capa de enlace y fısica ya liberados.El aprendizaje llevo un tiempo moderado, algunos problemas al comienzo,especialmente con la depuracion, fueron por trabajar en Windows. La docu-mentacion de Omnet++ es bastante completa, y la de MiXiM esta incluidaen el codigo fuente y es buena.

191

6.3. CONCLUSIONES

6.3. Conclusiones

Para extender la vida util de las redes inalambricas de sensores se debeoptimizar el consumo de energıa en todas las actividades que realizan losnodos sensores, y la comunicacion es una de las tareas de mayor consumoenergetico. La optimizacion en las comunicaciones depende en gran partedel diseno de los algoritmos de encaminamiento, por lo que han recibidoespecial atencion en la comunidad cientıfica interesada en este tipo de redesdurante los ultimos anos.En este trabajo se han estudiado los paradigmas de vanguardia en encami-namiento WSN, poniendo especial atencion en las tecnicas de diseminacionde interes y en algoritmos que tienen consciencia de la energıa. Tambien sehan estudiado los requerimientos de trafico de distintos tipos de aplicacio-nes.Utilizando el software de simulacion Omnet++ se ha configurado una redde sensores desplegados al azar con una aplicacion de consulta iniciada porel sumidero, para probar el protocolo de diseminacion, M-SPIN, el proto-colo consciente de la energıa, SAMF, y un protocolo disenado mezclandolas tecnicas de ambos, EA-SPIN. Se desarrollaron modulos C++ para lostres algoritmos, y se agregaron y modificaron modulos de recoleccion de es-tadısticas.Para el modelo de nodo se utilizo una pila de protocolos IEEE 802.15.4 pro-vista por el framework MiXiM 2.1 con algunas limitaciones en el modelo deenlace que condicionaron el analisis. Aun ası, se considero una mejor opcionutilizar este esquema de trabajo, que simular los algoritmos en forma aislada,sin un modelo de canal inalambrico compartido, ya que no se evidenciarıanalgunos importantes efectos como la interferencia.Se realizaron simulaciones de ajuste de los parametros de los protocolosM-SPIN y EA-SPIN para la red de ejemplo y luego se simularon varios es-cenarios de consulta iniciada por el sumidero para comparar su desempeno.La metricas recolectadas indican que las modificaciones realizadas a M-SPINproducen una mayor tasa de exito, pero una latencia mucho mas larga.El analisis de consumo de energıa de transmision mostro que el consumoen general es similar o menor en EA-SPIN y que el ahorro se manifiestaen nodos mas cercanos al sumidero, lo cual es esperable porque son los queencaminan una mayor cantidad de paquetes en favor de nodos mas alejados.Un posterior analisis permitirıa determinar si esta modificacion al patronde consumo es mejor y prolonga la conectividad provista por nodos mascercanos al sumidero.El resultado de tener en cuenta la capacidad de ruta en M-SPIN, ademasde la repeticion de anuncios y la suspension de la negociacion si otro no-do con mejor capacidad la inicia primero, fue un consumo de transmisionmoderadamente menor en algunos escenarios para la red de ejemplo.

192


6.4. Resumen de aportes del trabajo

evaluacion M-SPIN (Modified Sensor Protocols for Information viaNegotiation) y SAMF (Self-adapting Maximum Flow Routing) en si-mulaciones de una red con una pila de protocolos IEEE 802.15.4

evaluacion de SAFM [59] en simulaciones de un escenario de consultapor demanda, adoptando las sugerencias de trabajo de Flow Aumen-tation [12]

evaluacion de una variacion de M-SPIN, agregando un control de flujosimilar al que utiliza SAFM, continuando el trabajo presentado en [60],e incluyendo repeticion de anuncios para aumentar la confiabilidad

comparacion del desempeno en simulaciones de los tres protocolos conmetricas de eficiencia y uso de energıa

6.5. Trabajo futuro

Algunas cuestiones interesantes que han quedado fuera del alcance deeste trabajo son:

analizar la sensibilidad de los protocolos a un mayor tamano de red,escalabilidad

analizar la sensibilidad a los tiempos de espera en SPIN

estudiar el comportamiento de los protocolos utilizando BMAC para elacceso al medio y enlace(actualmente MiXiM 2.1 contiene un moduloBMAC no utilizado en este trabajo)

estudiar el comportamiento utilizando CSMA IEEE 802.15.4-2006 enmodo ranurado (beacon-enabled slotted CSMA-CA)

probar otros patrones de trafico por consulta, consultas a diferentessubconjuntos de nodos, tareas diferentes para cada nodo, etc.

implementar una red experimental real para ajustar el modelo y veri-ficar el comportamiento en cuanto a la utilizacion de la energıa

analizar los patrones de consumo de energıa que sugieren los protocolosy su incidencia en la vida util de la red

193

6.5. TRABAJO FUTURO

194

Apendices

195

Apendice A

Glosario

ASK Amplitude Shift Keying, esquema de modulacion que representa infor-macion digital por medio de variaciones en la amplitud de la onda portadora.

AES Advanced Encryption Standard, estandar de cifrado por bloques.

Beacon Nodo baliza o trama de senalizacion.

BER Bit Error Rate, tasa de errores en los bits en un intervalo de tiempo.

BPSK Binary Phase Shift Keying, esquema de modulacion digital que re-presenta los datos mediante variaciones en la fase de la onda portadora,BPSK utiliza dos fases separadas en 180 grados.

Broadcast En un medio compartido, transmision cuyo destino es la totali-dad de los dispositivos en alcance.

C4ISRT Command, control, communications, computing, intelligence, sur-veillance, reconnaissance and targeting.

CAP Contention Access Period, en enlace CSMA, perıodo de acceso porcompetencia.

197

CCA Clear Channel Assesment, en enlace CSMA, sensado del canal paradeterminar si esta libre.

CDMA Code Divission Multiple Access, tecnica de acceso al medio que per-mite compartir una banda de frecuencias, que dispersa el ancho de banda dela senal combinandola con un codigo pseudo-random de mucha mayor fre-cuencia, utilizando codigos ortogonales transmisiones de diferentes usuariosno interfieren entre sı.Conjunto dominante conexo Subconjunto de vertices de un grafo talque se puede formar un arbol de expansion en el que todos los nodos delsubconjunto no son hojas.

CSMA Carrier Sense Multiple Access, protocolo de acceso al medio.

CSS Chirp Spread Spectrum, tecnica de modulacion digital de espectrodisperso, que utiliza el total del ancho de banda asignado, y codifica la in-formacion mediante pulsos con frecuencia creciente o decreciente.

RTS/CTS Request To Send / Clear To Send, en enlace CSMA, solicitud deenvıo, y respuesta que permite a otros nodos abstenerse de utilizar el medioreduciendo colisiones.

DCF Distributed Coordination Function, tecnica de acceso al medio utili-zada por tecnologıas basadas en el estandar IEEE 802.11.

Desviacion estandar Medida de la distancia de las muestras a la mediaaritmetica (promedio).

DSSS Direct Sequence Spread Spectrum, tecnica de modulacion de espec-tro disperso, que utiliza el total del ancho de banda asignado, y que modulala senal de informacion multiplicandola por una cadena continua de pseudo-ruido, una secuencia de valores 1 y -1 a una frecuencia mucho mayor que lade la senal original.

EAD Energy-Aware Data Centric Routing, protocolo de encaminamientojerarquico centrado en datos.

198

APENDICE A. GLOSARIO

ED Energy Detection, Deteccion de Energıa, mecanismo de deteccion deintensidad de senal de tranceptores.

ERS Expanding Ring Search, busqueda por expansion en anillo, tecnica demulticasting por rondas, donde en cada ronda el paquete transmitido alcan-za nodos a una distancia cada vez mayor del iniciador [67].

Estacion Base Nodo recolector o sumidero de datos.

Flow Augmentation Aumentacion de flujo, protocolo de encaminamientoconsciente de la energıa.

Fuente Nodo que genera datos que deben ser encaminados.

Grafo embebido Un grafo puede ser embebido en una superficie si admiteser dibujado en ella sin interseccion de aristas [68]

Graph Routing Encaminamiento por grafo, propuesto por WirelessHART,donde las rutas se identifican por el grafo al que pertenecen, y el dispositivoadministrador de la red configura multiples grafos de red que pueden sola-parse.

GTS Guaranteed Time Slot, en enlace CSMA, perıodo de acceso al medioexclusivo garantizado.

Hopping Secuencia de saltos de frecuencia.

ISM Industrial Scientific and Medical, banda de frecuencias de uso no li-cenciado.

LEACH Low Energy Adaptive Clustering Hierarchy, protocolo de encami-namiento jerarquico por clusteres.

199

LQI Link Quality Indicator, indicador de la calidad de la senal recibida.

MAC Medium Access Layer, Capa de acceso al medio, segun el modelo dereferencia OSI.

MIC Message Integrity Code, codigo de integridad del mensaje.

Mote Nodo sensor.

Multicast En un medio compartido, transmision con destino de grupo.

NAV Network Allocation Vector, en enlace CSMA, mecanismo de sensadoy espera por acceso al medio.

NP Nondeterministic polynomial time, clase de complejidad computacionalque pueden ser resueltos en tiempo polinomico (que puede acotarse por unpolinomio de las variables implicadas) por una maquina de Turing no deter-minista;.

NP-Completo Subconjunto de problemas NP para los que el mejor algo-ritmo conocido para encontrar una solucion es una busqueda exahustiva.

OQPSK Offset Quadrature Phase Shift Keying, esquema de modulaciondigital que codifica la informacion por medio de cambios de fase en la ondaportadora, utilizando 4 valores diferentes de fase.

PAN Personal Areal Network, red de area personal.

Picored Red en Bluetooth.

PHY Physical Layer, Capa Fısica, segun el modelo de referencia OSI.

200

APENDICE A. GLOSARIO

PSSS Parallel Sequence Spread Spectrum, tecnica de modulacion basadaen el principio CDMA, que codifica una secuencia de datos en paralelo.

Relay Nodo que reenvıa paquetes en favor de otros nodos.

RSSI Received Signal Strength Indicator, medida de la intensidad de lasenal recibida.

schedule Temporizador o programacion de tarea.

SIFS Short Inter Frame Spacing, en redes 802.11, intervalo de tiempo entreuna trama de datos y su acuse de recibo.

SNR Signal to Noise Ratio, relacion senal-ruido.

Software Bus Sistema de comunicacion de datos que permite intercambiarinformacion por broadcast, donde los receptores definen los mensajes quedesean recibir segun su contenido (servicio publish/subscribe) [69].

Source Routing Encaminamiento en origen, el nodo que emite por primeravez el paquete especifica la ruta por la que debe encaminarse.

Spanning tree Arbol recubridor o de expansion.

SPIN Sensor Protocols for Information via Negotiation, protocolo de dise-minacion centrado en datos.

Sumidero Nodo recolector de informacion.

Superframe Especificacion de actividades de comunicacion y acceso al me-dio periodicas.

201

TDMA Time Division Multiplexed Access, tecnologıa de acceso al mediopara canales compartidos por division del tiempo en ranuras.

Trama Frame.

Tranceptor Radio transmisor y receptor.

Unicast En un medio compartido, transmision con destino unico.

UWB Ultra-wideband, tecnologıa inalambrica de comunicacion a baja energıay ancho de banda amplio.

WPAN Wireless Personal Area Network, red inalambrica de area personal.

WSN Wireless Sensor Network, red inalambrica de sensores.

ZigBee Estandar de comunicacion para redes inalambricas de sensores ba-sado en el estandar IEEE 802.15.4-2003.

202

Apendice B

Metricas

B.1. Recopilacion de metricas

En [27] se realiza una taxonomıa de modelos de redes inalambricas desensores. Allı se proponen las siguientes metricas para evaluar protocolospara WSNs:

Metrica Descripcion

Vida util del sistema /Eficiencia

Como los nodos utilizan una baterıa de duracion limitada, losprotocolos deben ser eficientes en terminos de energıa. La vidautil del sistema se puede definir en forma generica o especıficade la aplicacion. De manera generica por ejemplo, puede defi-nirse como el tiempo hasta que la mitad de los nodos de la redagota su baterıa. De manera especıfica, el tiempo hasta quela aplicacion ya no puede proveer informacion del fenomenosensado, por ejemplo, una region queda sin cobertura.

LatenciaSe requiere obtener datos del fenomeno con un determinadoretardo, especıfico de cada aplicacion.

Exactitud

La exactitud requerida de la informacion nuevamente dependedel tipo de aplicacion, e impactara en la latencia y eficienciacon la que se obtendran los datos. Por ejemplo, pueden reque-rirse mediciones mas frecuentes si se utiliza un unico nodo quesi se utiliza un conjunto de nodos.

Tolerancia a fallasLa red debe ser tolerante a fallas en el sentido en que lasfallas no catastroficas (por ejemplo, de algunos nodos) debenocultarse a la aplicacion.

EscalabilidadCuan bueno es el comportamiento de la red al aumentar ladensidad o cantidad de nodos.

Cuadro B.1: Metricas de evaluacion de protocolos

203

B.1. RECOPILACION DE METRICAS

En [4] se presentan las siguientes metricas de analisis de desempeno:

Metrica Descripcion

Vida util del sistema

Definida de varias maneras: a) tiempo hasta que un nodo agotasu energıa; b) tiempo hasta que los requisitos de calidad deservicio de la aplicacion ya no pueden garantizarse; c) tiempohasta que la red se particiona.

Eficiencia energetica

Cantidad de paquetes que pueden ser exitosamente transmiti-dos por unidad de energıa. Las colisiones de frames en la capade enlace, el costo indirecto del encaminamiento, la perdida depaquetes, y las retransmisiones reducen la eficiencia energeti-ca.

ConfiabilidadLa razon de la cantidad de paquetes recibidos con exito vs. eltotal de paquetes transmitidos.

Cobertura

Cobertura total significa que el espacio entero es monitoreadopor los sensores. Si algun sensor deja de ser funcional, debidoal agotamiento de su energıa, ya no se puede monitorear unacierta region. La cobertura es la razon del espacio monitoreadovs. el espacio total.

ConectividadPara redes multi-salto, la red puede particionarse. La conec-tividad es una medida de cuan bien conectada esta la red, ocuantos nodos han quedado aislados.

Calidad de ServicioAlgunas aplicaciones tienen caracterısticas de tiempo real, porlo que pueden requerirse tasas especıficas de retardo, perdidasy ancho de banda.

Cuadro B.2: Otras metricas de desempeno

En [26] se repasan multiples criterios de evaluacion. Casi todas las estra-tegias de evaluacion incluyen alguna forma de metrica de energıa. El autorse sorprende de que no se vinculen las metricas de energıa a la calidad deservicio requerida por la aplicacion.

204

APENDICE B. METRICAS

Cuadro B.3: Metricas de una revision de criterios de evaluacion

Tipo de metricaNombre dela metrica

Descripcion

Uso de energıa y vidautil efectiva

Paquetes antes de laparticion

Cantidad de paquetes de datos envia-dos y recibidos exitosamente antes deque la red se particione (debido al ago-tamiento de energıa de algunos nodos)


Conectividad despuesde la particion

Fraccion de enlaces aun activos luegode la particion. Indica de que maneraun patron de trafico afecta una red.


Recursos gastados porpaquete entregado

En terminos de enlaces (aristas) rotospor agotamiento de nodos: enlaces ro-tos / total de paquetes entregados.


Energıa disipada pro-medio

Energıa total utilizada por nodo / can-tidad de eventos detectados


Energıa disipada totalSuma del total de energıa disipada entodos los nodos


Distribucion de energıaUniformidad de los niveles de energıade los nodos

Overhead y eficiencia Perdida de mensajesPorcentaje de mensajes no recibidospor ningun nodo de la red

Overhead y eficiencia Overhead de control

La razon entre los mensajes de controlvs. los de datos. Algunos autores usanla razon entre el total de mensajes en-viados vs. los recibidos. Otros compa-ran la tasa de paquetes de aplicacioncon la de paquetes de encaminamiento.

Overhead y eficienciaTasa de entrega deeventos

La razon de la cantidad de mensajes deeventos diferentes recibidos por el su-midero vs. la cantidad de mensajes ori-ginalmente enviados por el nodo fuen-te. Algunos autores utilizan la razonperdidas vs. colisiones.

Overhead y eficienciaTransmisiones por con-sulta

La razon del total de paquetes enviadospor la cantidad de consultas inyectadasen la red

Overhead y eficienciaLongitud promedio dela ruta

Numero de saltos, relacionados al usode la energıa, pero cada autor puededar resultados muy diferentes debido ala relacion no lineal entre la potenciade transmision y el alcance.

Overhead y eficienciaCosto en mensajes deprotocolo

La cantidad de paquetes de encamina-miento generados por un algoritmo.

Evaluacion temporal Latencia

El retardo promedio entre la transmi-sion de un evento y la recepcion en elsumidero.

Evaluacion temporal Tiempo de reaccion

Varia segun el autor, esencialmente esel tiempo que tarda el sumidero en re-cibir un mensaje de datos luego de quealgun cambio ocurre en la red.

Otras Facilidad de despliegue Mencionadas en algunos artıculos.

Continua en la pagina siguiente. . .

205

B.2. METRICAS DE SIMULACIONES ESPECIFICAS

Cuadro B.3 – Continuacion

Tipo de metricaNombre dela metrica

Descripcion

OtrasSensibilidad a losparametros

A pesar de que algunas tecnicas re-quieren de la configuracion de un grannumero de parametros, esta metrica noes muy utilizada.

OtrasRequerimientos de al-macenamiento

La cantidad de memoria requerida porcada nodo

Otras Escalabilidad

Como varıa el comportamiento del pro-tocolo al variar la densidad de nodos,la cantidad de nodos, y la cantidad defuentes y sumideros.

B.2. Metricas de simulaciones especıficas

En [62] se evalua a SPIN utilizando las siguientes metricas:

Metrica Descripcion

Tasa de exitoLa probabilidad de entregar exitosamente los paquetesde datos a los nodos interesados.

Eficiencia energeticaLa cantidad de nodos que reenvıan cuando la tasa deexito es 1 (no es lo mismo que hop count?).

Cantidad de saltos dela ruta

La cantidad de saltos entre el nodo origen y el nodoque solicita el dato.

Cuadro B.4: Metricas de evaluacion del protocolo SPIN

Ası mismo, en [63], se evalua un protocolo orientado a mantener la conec-tividad de una red de nodos estacionarios desplegados al azar, maximizandola vida util de la red. Cada nodo sensa el medio ambiente en forma periodi-ca y produce datos que deben ser comunicados a un unico sumidero, a unatasa constante. En este trabajo se compara el desempeno con los protocolosdescriptos en [12].

Metrica Descripcion

Vida util de los nodosSe dice que un nodo sensor muere cuando agota suenergıa o no existe una ruta al sumidero.

Tiempo hasta que lared se particiona

Proceso de coberturaFraccion de el espacio cubierta por los nodos, que de-crece a medida que los nodos mueren.

Cuadro B.5: Metricas de evaluacion del protoclo PBR

206

APENDICE B. METRICAS

Tambien, en [39], se muestran resultados de simulaciones de evaluacionde EAD. El protocolo construye un arbol de encaminamiento para enviardatos a un unico sumidero.

Metrica Descripcion

Cantidad de nodos ac-tivos

Indica la cantidad de fallas de nodo debido a la baja deenergıa con el paso del tiempo. La falla se caracterizapor la incapacidad de generar paquetes, definida porun umbral de energıa disponible.

RendimientoVolumen de datos transmitido al sumidero a medidaque pasa el tiempo.

Consumo de energıaTotal de energıa empleada por la red a medida que pa-sa el tiempo. Muestra la capacidad de ahorrar energıadel algoritmo.

Cuadro B.6: Metricas de evaluacion del protocolo EAD

207

B.2. METRICAS DE SIMULACIONES ESPECIFICAS

208

Apendice C

Modificaciones a MiXiM 2.1

C.1. Energıa de transmision

Para poder totalizar la energıa de transmision, y habilitar el calculo deestadısticas, se modifico el modulo de baterıa, para permitir el acceso publicoa los totales de consumo por actividad, agregando el metodo getActivityTo-tal() que se muestra en el fragmento de codigo C.1:

Fragmento de codigo C.1: Metodo getActivityTotal()

1 double SimpleBattery::getActivityTotal(int act) {

2 double total = 0;

3 for (int i = 0; i < numDevices; i++) {

4 for (int j = 0; j < devices[i].numAccts; j++) {

5 if (j == act) {

6 total += devices[i].accts[j];

7 }

8 }

9 }

10 return total;

11 }

La modificacion permitio tambien a los modulos de protocolo consultarel consumo acumulado por actividad, por ejemplo, en transmisiones.

C.2. Total de mensajes

Para que se graben estadısticas sobre el total de paquetes enviados, senecesita utilizar la utilidad Blackboard. El Blackboard es un modulo quepermite encapsular variables globales, permitiendo un intercambio de infor-macion de estilo pizarra entre los modulos.La red WSNRouting utiliza un modulo de seguimiento, que se suscribe a lapizarra, para ser notificado cuando la aplicacion envıa o recibe un paquete.Para utilizar un modulo de seguimiento mas completo y personalizado, el

209

C.2. TOTAL DE MENSAJES

mismo se hace configurable, modificando la definicion de la red WSNRou-ting.ned, como se muestra en el fragmento de codigo C.2:

Fragmento de codigo C.2: Redefinicion del modulo de rastreo

1 network WSNRouting {

2 parameters:

3 string tracerType = default("SimTracer"); //type of the network layer

4 submodules:

5 simTracer: <tracerType> {}

Para poder extender y mejorar la clase SimTracer se debio hacer que laherencia de ImNotifiable sea publica, como se muestra en el fragmento decodigo C.3:

Fragmento de codigo C.3: Herencia publica de ImNotifiable para SimTracer

1 class SimTracer:public cSimpleModule, public ImNotifiable

2 {

Se creo la clase NetworkTracer que es notificada sobre la publicacion deun ıtem global de tipo cPacket en la pizarra, que comunica cada paqueteenviado y recibido, de red o aplicacion, y cada paquete de red superfluo. Elproceso de las notificaciones se muestra en el fragmento de codigo C.4:

Fragmento de codigo C.4: Total de paquetes a partir de notificaciones

1 class NetworkTracer : public SimTracer

2 {

3 public:

4 virtual void receiveBBItem(int category, const BBItem * details,

5 int scopeModuleId);

6 }

7

8 void NetworkTracer::receiveBBItem(int category, const BBItem * details,

9 int scopeModuleId)

10 {

11 cModule * module = simulation.getModule(scopeModuleId);

12

13 if (category == catPacket) {

14 if (strcmp(module->getName(), "net") == 0) {

15 packet = *(static_cast<const Packet*>(details));

16 if(packet.isSent()) {

17 nbNetwPacketsSent++;

18 } else {

19 nbNetwPacketsOverhear++;

20 }

21 } else {

22 SimTracer::receiveBBItem(category, details, scopeModuleId);

23 }

24 } else if (category == catHostState){

210

APENDICE C. MODIFICACIONES A MIXIM 2.1

25 ...

26 }

Las notificaciones son publicadas en la pizarra por el modulo de red,como se ilustra en el fragmento de codigo C.5:

Fragmento de codigo C.5: SPIN publica paquetes envıados y de sobreescucha

1 void SPIN::publishPacketOverhear(){

2 packet.setPacketSent(false);

3 packet.setNbPacketsSent(0);

4 packet.setNbPacketsReceived(1);

5 packet.setHost(myNetwAddr);

6 world->publishBBItem(catPacket, &packet, getId());

7 }

8

9 void SPIN::publishPacketSent(){

10 packet.setPacketSent(true);

11 packet.setNbPacketsSent(1);

12 packet.setNbPacketsReceived(0);

13 packet.setHost(myNetwAddr);

14 world->publishBBItem(catPacket, &packet, getId());

15 }

C.3. Energıa residual

En MiXiM, el modulo que graba totales de baterıa se llama BatteryS-tats, pero algunos valores necesarios para el analisis en este trabajo no songrabados. Para poder grabar la energıa residual al terminar la simulacion,se modifico BatteryStats.cc como se muestra en el fragmento de codigo C.6:

Fragmento de codigo C.6: Grabacion de la energıa residual al finalizar

1 void BatteryStats::summary(double init, double final, simtime_t lifetime)

2 {

3 recordScalar("final", final, "mW-s");

4 ...

Para poder identificar a que actividad corresponde el consumo registradose modifico la descripcion del valor, segun el fragmento de codigo C.7:

Fragmento de codigo C.7: Grabacion del consumo por actividad

1

2 void BatteryStats::detail(DeviceEntry *devices, int numDevices)

3 {

4 for (int j = 0; j < devices[i].numAccts; j++) {

5 // Record activity energy

6 stringstream activitySummary;

211

C.4. SENSIBILIDAD

7 activitySummary << "activity-" << j;

8 recordScalar(activitySummary.str().c_str(), devices[i].accts[j]);

9 ...

C.4. Sensibilidad

Se modifico el modulo Decider802154Narrow para que se descarten fra-mes que se reciben con una potencia de transmision menor que la sensibili-dad del tranceptor. La modificacion se muestra en el fragmento de codigo C.8

Fragmento de codigo C.8: Descarte por baja intensidad en Decider802154Narrow

1

2 simtime_t Decider802154Narrow::processNewSignal(AirFrame* frame) {

3 Signal& s = frame->getSignal();

4 simtime_t time = MappingUtils::post(s.getSignalStart());

5 double rcvPower = s.getReceivingPower()->getValue(Argument(time));

6 ...

7 // check whether signal is strong enough to receive

8 if ( rcvPower < sensitivity )

9 {

10 // Discard frame

11 return notAgain;

12 }

13 ...

14 }

Con la modificacion mostrada, los frames que no llegan con la intensidadde senal mayor que la sensibilidad son descartados. De esta manera con unapotencia de transmision de 1 mW se logra un alcance aproximado de 85 m.

212

Referencias

[1] Neha Jain. Energy Aware Adaptive Routing Protocols in Wireless Sen-sor Networks. PhD thesis, University of Cincinnati, 2004.

[2] Suyoung Yoon. Power Management in Wireless Sensor Networks. PhDthesis, North Carolina State University, 2007.

[3] Libelium. Libelium Environment - http://www.libelium.com/ applica-tions/Environment, 2010.

[4] Kazem Sohraby, Daniel Minoli, and Taieb Znati. Wireless Sensor Net-works. Wiley, 2007 edition, 2007.

[5] Levente Butty and Gergely Acs. A Taxonomy of Routing Protocols forWireless Sensor Networks, 2007.

[6] ZigBee Alliance. ZigBee Specification, 2008.

[7] Najet Boughanmi and YeQiong Song. Improvement of Zigbee routingprotocol including energy and delay constraints, 2007.

[8] Charles E Perkins and Elizabeth M Royer. Ad-hoc On-Demand Dis-tance Vector Routing. In Proceedings Of The 2nd IEEE Workshop OnMobile Computing Systems And Applications, pages 90–100, 1997.

[9] Ouadoudi Zytoune, Youssef Fakhri, and Driss Aboutajdine. LifetimeOptimization for Wireless Sensor Networks. IEEE/ACS Internatio-nal Conference on Computer Systems and Applications, pages 816–820,2009.

[10] Jamal N Al-Karaki and Ahmed E Kamal. Routing Techniques in Wi-reless Sensor Networks : A Survey. Wireless Communications, IEEE,11(6):6–28, 2004.

[11] K Akkaya and M Younis. A Survey on Routing Protocols for WirelessSensor Networks. Ad Hoc Networks, 3:325–349, 2005.

[12] Jae-hwan Chang and Leandros Tassiulas. Maximum Lifetime Routingin Wireless Sensor Networks. IEEE/ACM Transactions On Networking,12:609–619, 2004.

213

REFERENCIAS

[13] Charles Pandana and K J Ray Liu. Maximum Connectivity and Ma-ximum Lifetime Energy-aware Routing for Wireless Sensor Networks.Global Telecommunications Conference, 2:1034–1038, 2005.

[14] Yeling Zhang, Ramkumar Mahalingam, and Nasir Memon. InformationFlow Based Routing Algorithms for Wireless Sensor Networks. GlobalTelecommunications Conference, 2:742–747, 2004.

[15] Vahid Shah-mansouri and Vincent W S Wong. Distributed MaximumLifetime Routing in Wireless Sensor Networks Based on Regularization.Global Telecommunications Conference, pages 598–603, 2007.

[16] Shinya Ito and Kenji Yoshigoe. Consumed-Energy-Type-Aware Rou-ting for Wireless Sensor Networks. Wireless Telecommunications Sym-posium, pages 1–6, 2007.

[17] Rahul C Shah and Jan M Rabaey. Energy Aware Routing for LowEnergy Ad Hoc Sensor Networks. Wireless Communications and Net-working Conference, 1:350–355, 2002.

[18] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin.Directed Diffusion : A Scalable and Robust Communication Paradigmfor Sensor Networks. In MOBICOM, pages 56–67. ACM, 2000.

[19] I F Akyildiz, W Su, Y Sankarasubramaniam, and E Cayirci. Wirelesssensor networks : a survey. Computer Networks, 38:393–422, 2002.

[20] Tampere University of Technology. WIREPAS Project -http://www.tkt.cs.tut.fi/ research/daci/cp wirepas overview.html,2011.

[21] Jennifer Yick, Biswanath Mukherjee, and Dipak Ghosal. Wireless sen-sor network survey. Computer Networks, 52:2292–2330, 2008.

[22] Holger Karl and Andreas Willig. Protocols and Architectures for Wire-less Sensor Networks. Wiley, 2005.

[23] TinyOS. http://www.tinyos.net/, 2011.

[24] MEMSIC. MICAz Datasheet - http://www.memsic.com/support/documentation/wireless-sensor-networks/ category/7-datasheets.html?download=148 %253Amicaz, 2011.

[25] Yingshu Li, My T. Thai, and Weili Wu, editors. Wireless Sensor Net-works and Applications. Spinger, 2008.

[26] Ronan Mac Ruairı, Mark T Keane, and Gerry Coleman. A WirelessSensor Network Application Requirements Taxonomy. Sensor Techno-logies and Applications, pages 209–216, 2008.

214

REFERENCIAS

[27] Sameer Tilak, Nael B Abu-ghazaleh, and Wendi Heinzelman. A Taxo-nomy of Wireless Micro-Sensor Network Models. ACM Mobile Compu-ting And Communications Review, 6:28–36, 2002.

[28] IEEE. IEEE 802.15.4a-2007 Wireless Medium Access Control (MAC)and Physical Layer (PHY) Specifications for Low-Rate Wireless Per-sonal Area Networks (WPANs) Amendment 1: Add Alternate PHYs.2007(August), 2007.

[29] Shahin Farahani. Zigbee Wireless Networks and Transceivers. Elsevier,2008.

[30] ZigBee Alliance. ZigBee Standards - http://www.zigbee.org/ Standard-s/Overview.aspx, 2011.

[31] IEEE. IEEE 802.15.4-2006 Wireless Medium Access Control (MAC)and Physical Layer (PHY) Specifications for Low-Rate Wireless Perso-nal Area Networks (WPANs). Control, 2006(September), 2006.

[32] Jianping Song, Song Han, Aloysius K Mok, Deji Chen, Mike Lucas,Mark Nixon, and Wally Pratt. WirelessHART : Applying Wireless Te-chnology in Real-Time Industrial Process Control. Real-Time and Em-bedded Technology and Applications Symposium, pages 377–386, 2008.

[33] IEC. IEC 62591 Ed. 1.0 Industrial communication networks - Wirelesscommunication network and communication profiles - WirelessHART,2010.

[34] HARTCOMM. WirelessHART - http://www.hartcomm.org/ protoco-l/wihart/wireless how it works.html, 2011.

[35] Tomas Lennvall and Stefan Svensson. A Comparison of WirelessHARTand ZigBee for Industrial Applications. Factory Communication Sys-tems, pages 85–88, 2008.

[36] Azzedine Boukerche, Mohammad Z Ahmad, Begumhan Turgut, andDamla Turgut. A Taxonomy of Routing Protocols in Sensor Networks,pages 129 –160. Wiley-IEEE Press, 1 edition, 2008.

[37] W Heinzelman, A Chandrakasan, and H Balakrishnan. Energy-EfficientCommunication Protocol for Wireless Microsensor Networks. Procee-dings of the 33rd Hawaii International Conference on System Sciences,2, 2000.

[38] Ananth Rao, Sylvia Ratnasamy, Christos Papadimitriou, Scott Shenker,and Ion Stoica. Geographic Routing without Location Information. InMobile computing and networking, pages 03–218. ACM, 2003.

215

REFERENCIAS

[39] Azzedine Boukerche, George Washington, and Joseph Linus. Energy-Aware Data-Centric Routing in Microsensor Networks. In Modelinganalysis and simulation of wireless and mobile systems, pages 42–49.ACM, 2003.

[40] Tayseer Al-khdour and Uthman Baroudi. A Generalized Energy-AwareData Centric Routing for Wireless Sensor Network. In Signal Processingand Communications, number November, pages 24–27. IEEE, 2007.

[41] Antonio Carzaniga and Alexander L Wolf. Content-Based Networking: A New Communication Infrastructure, 2002.

[42] Wendi Rabiner Heinzelman, Joanna Kulik, and Hari Balakrishnan.Adaptive Protocols for Information Dissemination in Wireless SensorNetworks. pages 174–185, 1999.

[43] F Zabin, S Misra, I Woungang, HF Rashvand, N-W A, and M AhsanAli. REEP: data-centric, energy-efficient, reliable routing protocol forwireless sensor networks. Communications, IET, 2(8):995– 1008, 2008.

[44] Michele Mastrogiovanni, Chiara Petrioli, Michele Rossi, Andrea Vita-letti, and Michele Zorzi. Integrated Data Delivery and Interest Disse-mination Techniques for Wireless Sensor Networks. Global Telecommu-nications Conference, pages 1–6, 2006.

[45] Lorenzo Orecchia, Ro Panconesi, Chiara Petrioli, and Andre Vitaleti.Localized Techniques for Broadcasting in Wireless Sensor. In DIALM-POMC. ACM Press, 2004.

[46] Joanna Kulik and Wendi Heinzelman. Negotiation-Based Protocolsfor Disseminating Information in Wireless Sensor Networks. WirelessNetworks, 8:169–185, 2002.

[47] Mike Woo and Suresh Singh. Power-Aware Routing in Mobile Ad HocNetworks, 1998.

[48] Leandros Tassiulas and Jae-hwan Chang. Routing for Maximum Sys-tem Lifetime in Wireless Ad-hoc Networks. In 37-th Annual AllertonConference on Communication, Control, and Computing, 1999.

[49] C.-K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mo-bile Computing in Wireless Ad Hoc Networks. IEEE CommunicationsMagazine, 39(6):138–147, 2001.

[50] Jae-hwan Chang and Leandros Tassiulas. Energy Conserving Routingin Wireless Ad-hoc Networks. In INFOCOM 2000. Nineteenth AnnualJoint Conference of the IEEE Computer and Communications Socie-ties. Proceedings. IEEE, pages 22–31. ATIRP, 2000.

216

REFERENCIAS

[51] OpenSim. Omnet++ User Manual, 2010.

[52] The Eclipse Foundation. Eclipse - http://www.eclipse.org/, 2011.

[53] Xiaodong Xian, Weiren Shi, and He Huang. Comparison of OMNET++ and Other Simulator for WSN Simulation. In Industrial Electronicsand Applications, pages 1439–1443. IEEE, 2008.

[54] C Mallanda, A Suri, V Kunchakarra, S S Iyengar, R Kannan, and A Du-rresi. Simulating Wireless Sensor Networks with OMNeT ++, 2005.

[55] Ugo Maria Colesanti, Carlo Crociani, and Andrea Vitaletti. On theAccuracy of OMNeT ++ in the Wireless Sensor Networks Domain :Simulation vs . Testbed. In Proceedings of the 4th ACM workshopon Performance evaluation of wireless ad hoc, sensor,and ubiquitousnetworks. ACM, 2007.

[56] MiXiM. MiXiM - http://mixim.sourceforge.net/, 2011.

[57] Jerome Rousselot, Jean-Dominique Decotignie, Marc Aoun, Peter vanDer Stok, Ramon Serna Oliver, and Gerhard Fohler. Accurate Timeli-ness Simulations for Real-Time Wireless Sensor Networks. In EMS ’09Proceedings of the 2009 Third UKSim European Symposium on Com-puter Modeling and Simulation. IEEE, 2009.

[58] Texas Intruments. 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF Trans-ceiver Datasheet, 2010.

[59] Alessandro Bogliolo, Saverio Delpriori, Emanuele Lattanzi, and AndreaSeraghiti. Self-adapting maximum flow routing for autonomous wirelesssensor networks. Cluster Computing, 14(1), 2011.

[60] Zeenat Rehena and Sarbani Roy. A Modified SPIN for Wireless SensorNetworks. In Communication Systems and Networks, pages 1–4, 2011.

[61] Xiangyang Li and Yajun Wang. Random Deployment of Wireless Sen-sor Networks : Power of Second Chance. In The 15th InternationalComputing and Combinatorics Conference, 2009.

[62] Dandan Liu, Xiaodong Hu, and Xiaohua Jia. Energy efficient informa-tion dissemination protocols by negotiation for wireless sensor networks.Computer Communications, 29(11):2136–2149, 2006.

[63] Praveen Kumar, Joy Kuri, Pavan Nuggehalli, Mario Strasser, MartinMay, and Bernhard Plattner. Connectivity-aware Routing in SensorNetworks. Sensor Technologies and Applications, pages 387–392, 2007.

217

REFERENCIAS

[64] Dazhi Chen and Pramod K Varshney. QoS Support in Wireless SensorNetworks: A Survey. In International Conference on Wireless Networks,2004.

[65] Nicola Santoro. Design and Analysis of Distributed Algorithms. Wiley,2007.

[66] Dimitri P. Bertsekas Tsitsiklis and John N. Parallel and DistributedComputation: Numerical Methods. Athena Scientific, 1997.

[67] Damien Magoni and Jean-jacques Pansiot. Oriented Multicast RoutingAlgorithm Applied to Network-level Agent Search. Discrete Mathema-tics And Theoretical Computer Science, pages 255–272, 2001.

[68] Petra Mutzel and Rene Weiskircher. Computing Optimal Embeddingsfor Planar Graphs. In Proceedings COCOON ’00 volume 1858 of LNCS,pages 94–104. Springer Verlag, 2000.

[69] Ivy. Ivy Software Bus - http://www2.tls.cena.fr/ products/ivy/a-bout.shtml, 2011.

218

tesis de Garbarino

Engineering

Transcript of tesis de Garbarino