Implementación y Evaluación del algoritmo
de sincronización RBS para redes
inalámbricas de sensores
Alumno: Seyed Mohammad Pakdaman
Tutor: Dr. Ing. Ariel Lutenberg
PROYECTO DE TESIS DE MAESTRÍA EN INGENÍERIA DE TELECOMUNICACIONES
Introducción General
¿Que es una red inalámbrica de
sensores?
Una red inalámbrica de sensores, o Wireless Sensor
Network (WSN), se compone de un gran número de nodos
de sensores conectados de forma inalámbrica, con
capacidades de computación y comunicación provistos
de sensores para medir diferentes variables de ambiente
en el que se encuentran.
Limitaciones de los nodos sensores
Capacidad de procesamiento
Energía disponible
Costo
Tamaño
Aplicaciones de redes inalámbricas de
nodos sensores:
Salud
Ambiente
Militar
Domótica
Estándar de comunicaciones IEEE 802.15.4
para las redes inalámbricas de sensores
Estándar de comunicaciones IEEE 802.15.4
para las redes inalámbricas de sensores
Sincronización de reloj en las redes
inalámbricas de sensores
Función de reloj
Función de Reloj ideal (𝑡 es el tiempo de referencia)
En caso que tengamos dos nodos sensores 1 y 2, la relación entre los dos relojes es de la siguiente forma:
Nodo 1 esta perfectamente sincronizado con el nodo 2 cuando:
𝐶(𝑡) = 𝑡
𝐶1(𝑡) = 𝛼12 + 𝛽 12 𝐶2(𝑡
𝛼 12 = 0 𝛽 12 = 0y
Donde 𝛼 12 es el offset relativo y 𝛽 12 es el skew relativo de los dos relojes
Necesidad de sincronizacion
Fusión de datos
Tareas de coordinación
Esquemas de encriptación
…
Sincronización de reloj
Las principales funciones de la sincronización de
tiempo en una red distribuida, como WSN, son:
Asegurar una escala de tiempo común para todos los
nodos de la red.
Proporcionar la correcta coordinación temporal entre
todos los nodos participantes, en una interacción
colaborativa y distribuida con el entorno físico.
Protocolos de sincronización de tiempo
tradicionales
NTP es una arquitectura jerárquica basada en el paradigma cliente-servidor que trabaja sobre el protocolo UDP.
NTP es ampliamente usado en Internet y ha demostrado ser efectivo y robusto.
Las principales ventajas de NTP son su escalabilidad, robusteza la falla, auto-configuración en redes de gran escala y su implementación difundida.
Los protocolos de sincronización de tiempo
tradicionales no son aplicables a las
redes inalámbricas de sensores
Energía disponible
Modo de transmisión
Topología dinámica
Retrasos contribuyentes al error de
sincronización
Los componentes de retraso en la entrega de mensajes
se pueden clasificar de la siguiente manera:
Tiempo de envió
Tiempo de acceso al canal inalámbrico
Tiempo de propagación
Tiempo de recepción
Protocolos de sincronización para
redes inalámbricas de sensores
Los algoritmos propuestos varían principalmente en su
método de estimación y corrección de errores debido a
los retrasos en el proceso de entrega de un mensaje.
Tienen características básicas en común:
Un protocolo de mensajería simple no orientada a la conexión
Un mecanismo para intercambiar la información de reloj entre los
nodos
Una estrategia para minimizar los efectos no determinísticos de
demora en la entrega y procesamiento del mensaje
Un algoritmo en el host que se encarga de ajustar los relojes locales
de los nodos en base de la información recibida de sus vecinos
Métricas para los protocolos de
sincronización para redes inalámbricas de
sensores
Error de fase
Error de frecuencia
Presupuesto energético
Vida útil
Disponibilidad
Alcance
Interno o Externo
Tiempos de convergencia
Clasificación de protocolos de
sincronización de tiempo en las WSNs
Maestro-Esclavo vs. Peer-to-Peer
Corrección de reloj vs. No corrección de reloj
Enfoque de sincronización
Transmisor-Receptor
Receptor-Receptor
Solo Receptor
Sincronización por pares vs. Sincronización de toda la red
Protocolo de sincronización RBS
para las redes inalámbricas de sensores
Principio de funcionamiento:
Protocolo de sincronización RBS
para las redes inalámbricas de sensores RBS directamente remueve del camino crítico a dos fuentes importantes
contribuyentes al error:
Tiempo de envío
Tiempo de demora para acceder al canal inalámbrico compartido
Extensión del algoritmo RBS a las redes
Multi-cluster
Estimación de reloj en RBS
Estimación del offset:n: Cantidad de receptores
m: Cantidad de paquetes de broadcast recibidos (paquetes de
sincronización)
Tr,b: El reloj local del nodo r cuando recibió el paquete de sincronización b
Estimacion del skew
Se lleva a cabo una regresión lineal de mínimos
cuadrados
∀𝑖 ∈ 𝑛, 𝑗 ∈ 𝑛: 𝑂𝑓𝑓𝑠𝑒𝑡[𝑖, 𝑗] =1
𝑚
𝑘=1
𝑚
𝑇𝑗,𝑘 − 𝑇𝑖,𝑘
Implementacion del algoritmo RBS
Nodo sensor utilizado en este estudio está compuesto por el
microcontrolador LPC1769 y el módulo RF Xbee PRO 802.15.4.
Implementación del algoritmo RBS
Implementación del algoritmo RBS
Es necesario que un evento de interés ocurra al mismo tiempo para
ambos nodos. Este evento puede ser otro mensaje de broadcast
que por ejemplo contenga la palabra “Estimar”.
Implementación del algoritmo RBS
Comenzando con 3 paquetes de sincronización por minuto y
aumentando los paquetes de sincronización hasta un máximo de
60 paquetes de sincronización por minuto.
Para poder comprobar el funcionamiento del algoritmo, los
paquetes de “estimar” se envían cada 250ms por un lapso de 7
minutos.
Resultados obtenidos
Desfasaje entre el valor estimado del reloj y el valor real en un lapso
de 30 segundos enviando 3 paquetes de sincronización por minuto
Resultados obtenidos
Histograma de distribución de desfasajes entre los valores de reloj
estimados y los valores reales (µs), enviando 3 paquetes de
sincronización por minuto
Resultados obtenidos
Desfasaje entre el valor estimado del reloj y el valor real en un lapso
de 30 segundos enviando 60 paquetes de sincronización por
minuto
Resultados obtenidos
Histograma de distribución de desfasajes entre los valores de reloj
estimados y los valores reales (µs), enviando 60 paquetes de
sincronización por minuto
Resultados obtenidos
Resutlados obtenidos
Resutlados obtenidos
Comparación con otros trabajos de
investigación
Elson et al., conducen varias simulaciones con objetivo
de evaluar la calidad que se puede conseguir
mediante el protocolo de sincronización RBS y su
respectivo comportamiento al momento de aumentar
la cantidad de paquetes de sincronización.
Comparación con otros trabajos de
investigación
Análisis de dispersión de grupo (máximo error entre los pares) después de
sincronización mediante RBS. Cada punto representa el promedio de 1000
simulaciones. Promedio de dispersión de grupo y el desviación estándar para dos
receptores (arriba) y para 20 receptores (abajo).
¿Por qué existe una diferencia?
¿Por qué existe una diferencia?
Conclusiones
Se pueden lograr un alto grado de precisión mediante el uso de RBS.
La precisión de sincronización va mejorando a medida que las cantidades
de paquetes de sincronización aumentan, sin embargo, tiene un umbral
donde la precisión obtenida se mantiene casi constante.
Tiempo de recepción y procesamiento por el receptor tiene un fuerte
impacto sobre la precisión obtenida mediante el uso de RBS.
Tiempo de recepción y procesamiento por el receptor tiene que ser menor
de la precisión requerida o en todo caso tiene que ser determinístico para
poder lograr mayor grado de precisión mediante el uso de RBS.
RBS es muy austero con el uso de la energía en proceso de sincronización,
es tolerante a varias fuentes no determinísticas de demora en su proceso
de estimación de reloj y no impone una carga excesiva al procesador.
Trabajos futuros
Disminuir la totalidad de energía consumida en la red en el proceso
de sincronización.
Implementar el algoritmo RBS sobre otras plataformas de nodos
sensores.
Continuar la investigación en otras temáticas relacionados con las
redes inalámbricas de sensores que necesitan una red
sincronizada, tales como encriptación, localización, fusión de
datos, etc.
¿PREGUNTAS?
¡¡¡Gracias!!!