DETECTOR DE FALLAS

Resumen: En este artículo se presentan tres algoritmos con elección de agregador y agregación de datos en redes inalámbricas de sensores, donde los sensores pueden chocar y recuperarse. La red se divide en varias regiones. Los algoritmos garantizan la elección de un sensor agregador de datos comunes dentro de cada región, para la recopilación de datos locales, y (ii) la selección de un único superpotente sensor agregador , a cargo de la recopilación de datos globales, entre todos los agregadores. Ambas selecciones se obtienen mediante la aplicación del detector de fallos Omega , que ofrece una auto-organización y tolerancia a fallos elegido como líder del servicio.Cada algoritmo se basa en suposiciones de diferente conectividad.

El primer algoritmo asume que cada par de sensores en una región pueden comunicarse directamente. El segundo algoritmo sólo requiere de algun sensor correcto para comunicarse directamente con el resto de sensores., Finalmente el tercer algoritmo requiere la existencia de un camino bidireccional (telaraña o nodos múlti-hop) de algunos Sensores correctos con el resto de sensores. También se introduce un umbral de agotamiento de la batería para aumentar la calidad de los servicios de red de sensores inalámbricos

Palabras clave: redes de sensores inalámbricas. Elección del agregador tolerante a Fallas, Detector de fallas Omega.

1. Introducción:

1.1 Antecedentes y relación con el trabajo.

Las redes de sensores inalámbricas (WSN). proporcionan aplicaciones para la   recopilación de datos fiables, con la reducción al maximo de la intervención humana ( de la libre organización y auto-mantenimiento). Aplicación que pueden actuar de modo autónomo sobre la configuración a distancia o remotamente de la red de sensores, recuperando la información colectada periódicamente por los sensores  y demandada.

WSN pueden estar expuestas a varias fuentes de problemas, tales como la medición, la comunicación, choques, errores de la fuente de energía. La redundancia de los sensores, permite obtener información de redundancia y luego permite asegurar un cierto nivel   de tolerancia a los fallos. Consideramos un WSN con un cierto grado de agrupaciones donde cada grupo se centra en   áreas o grupos específicas y se recopila la información a partir del esquema ( sensing) distribuido.

Las aplicaciones en red de sensores inalámbricos deben ser fiables y garantizar la recopilación de datos del sensor  asi como la agregación, la satisfacción al costo   y consumo de energía de bajos ,explotación u operación de tales aplicaciones.

El intento de reducir al mínimo el consumo de energía , lleva a reducir la cantidad de datos transmitidos mediante el uso de la agregación de datos . Algunas obras de literatura se centran en la aplicación eficiente de los protocolos de control de agregación calendario.

Como en (6) en (15), tres diferentes esquemas de agregación de datos dentro de la red, basada en ( GRID)redes sociales, en base de datos de agregación híbrida.Hechas con el fin de aumentar el rendimiento, reducir la congestión y para ahorrar energía. Otras obras de la gestión de agregación de datos con la ayuda de un algoritmo de consenso. Como lo hace (8).Los datos del sensor pueden ser recogidos y agregados por algunos nodos de la red de sensores llamados agregadotes (13). Sin embargo de que el trabajo hecho no direcciona la selección de la agregación ,pero se asume simplemente que esto existe. La selección del nodo agregador es analizado en (2).En la que jerárquicamente se presenta el uso de la energía del protocolo de agregación. El protocolo es probabilística y no considera la falla de los sensores. Cualquier esfuerzo destinado a la ampliación de la red e3n su ciclo de vida es requerido por el sensor y de la propia estrategia de colaboración que coordina los nodos en la tarea de detección que se hizo, así como en lo posible el uso eficiente de la energía .

Con respecto a la comunicación propia de los sensores, evitando alguna coalición, Los mecanismos   que pueden ser considerados son   TDMA, CDMA,y CSMA. Los principales inconvenientes de TDMA y CDMA y las técnicas que están relacionadas con los requisitos de los sensores, sincronización y una autoridad central para asignar las ranuras de tiempo y el complejo de la modulación del Hardware( que es difícil de aplicar, debido a la reducción del tamaño y de las prestaciones de los sensores.) respectivamente.

El uso de protocolos CSMA, ASI COMO IEEE 802.11(WiFi) permite reducir al mínimo el consumo de energía, debido a la coalición en WSN sin la necesidad de capacidades especiales y complejidad de los sensores.

La selección de un agregador puede ser considerada como un problema la elecciòn del lider. Lo cual ha sido extensivamente estudiado por la literatura e.g. (9)

A nuestro conocimiento el algoritmo para la primera elección del lider sin que conozca a los demás miembros, es por un sistema distribuido de colisión que ha sido recientemente propuesto por (7). También hemos enfocado varios trabajos en jerarquizaciòn y agrupamiento de redes ad-hoc inalámbricas ,e.eg.(5,14), que pueden ser adaptadas al problema de elección del lider. Estos trabajos no están orientados a los modelos de coalición y resurgimiento.En (3) donde una eficiente comunicación de trabajo probabilista se ha presentado( La cual podría ser usada para la eleccxiñon del lider ) Frecuentemente los cambios de conectividad en la red son considerados.Los posibles resultados en las particiones de la red de trabajo ,son tambiñen considerados la colisión y el resurgimiento del sensor.

Recientemente las redes móviles ad-hoc han introducido un nuevo aspecto sobre el problema de la elección del lider. La movilidad en (4)Los autores presentan un protocolo de la elección de un lider solitario superior, para la movilidad en la red. . Malpani et al.(10) proponen dos algoritmos de elección multi- super lideres,basado en (12) en donde ningun componente suficientemente largo puede ser considerado en una topologia estática, la cual eventualmente tedrà un solo lider . Finalmente el algoritmo propuesto en (16)y en (11)imponen la premisa por de realización por medio de computación por difusión y respectivamente un mejoramiento del proceso.



Http://portal.acm.org/citation.cfm?id=1163629

1.2 Nuestar aportación

Le proponemos tres algoritmos agregadores de elección jerárquicos y algoritmos de agregación de datos en largo WSNs basados en el detector de fallas Omega.

Asi los cambios en el conjunto debido a alcanzables sensores, el sensor agregador de cada región puede cambiar en el tiempo. Los algoritmos aseguran que todos los sensores de cada región designan un agregador común y que todos los agregadotes asignen a un lider super-agregador . Cada algoritmo se basa en diferentes hipótesis de conectividad•

El primer algoritmo asume que cada par de sensores en una región pueden comunicarse directamente.
• El segundo algoritmo relaja esta hipótesis, sólo necesita corregir algunos sensor para comunicarse directamente con el resto de sensores.
• Por último el tercer algoritmoda va más allá, no requieren ningún sensor para comunicarse directamente con el resto, sólo necesitan la existencia de un camino correcto multi-hop bidireccional de unos sensores para el resto de sensores.

1.3 HOJA DE RUTA
El resto de documentos son ordenados como sigue : En la secciòn 2 describimos esl modelo del sistema considerado en el trabajo.En la secciòn 3 se presenta los tres algoritmos de elecciòn de aghregadores y de   agregación de datos, para el nivel local ( dentro de la region ). En la secciòn 4 se presenta el algoiritmo para el nivel global dentro de las regiones ). En la sección 5. se introducen conceptos relacionados con la bateria para cuestionar los aumentos de la calidad del servicio de la red de sensores inalámbrica. Finalmente en la secciòn 6 se concluye el documento. .

2. Modelo del sistema.

Nosotros consideramos una red de sensores inalámbrica , en el que tratan de recopilar datos de sensores para minimizar el consumo de energía.
Vamos en el WSN a dividirlo en diferentes regiones, donde cada sensor sabe a priori su funcionamiento en cada región y trata de transmitir la sensación de sus datos al sensor agregador y cargar todos los datos emitidos a una región específica .Cada sensor tiene un identificador de esta operación en la región que es radiada en los mensajes. Este identificador sigue la reacción de ejecución de mensajes de entrada desde otras regiones. Esta operación del sensor en la región puede ser cambiada o demandada, así como la definición de la región. La comunicación del sensor sigue el protocolo de 802.11(WiFi).

Proponemos el uso de Omega para escoger un agregador común dentro de cada región de acuerdo con la fiabilidad de la batería del sensor. Un sensor es un candidato para ser electo como agregador, si este es un sensosr fiable sin errores durante cada período de la operación. Omega asegura que un único sensor entre todos los candidatos es elegido como agregador. Este agregador de cada regiòn es el encargado de recolectar todos los datos emitidos en su región. Mas formalmente consideramos S un sistema compuesto por un conjunto finito de sensores que se comunican por mensajes de radiodifusión en la redes inalámbricas.

Los sensores pueden fallar solamente cuando se cuelgan (colisión). Las coaliciones no son permanentes. Los cuelgues de los sensores pueden recuperarse i,e. los sensores colgados pueden recobrarse, Consideramos como tipo particular de accidente de colgado es por agotamiento de la batería del sensosr, siendo hipotéticamente remplazada por la recuperación de la bateria de sus asociados. De acuerdo con lo anterior y de la duración de la batería , un sensor puede ser :

*Eventualmente ACTIVO. Este es un sensor que, después de estrellarse y recuperar un número finito de veces, sigue hasta el final de la batería.

Eventualmente CAIDO. Este es un sensor que Después de estrellarse y recuperar un número finito de veces, sigue caído hasta el final de la batería.
Inestable . Este es un sensor que se bloquea continuamente y se recupera, hasta el final de la batería.

Por definición de sensor en (1) son correctos y sensores en (2) y en (3) son incorrectos, Asumimos que el número de sensores correcto es menos uno . Como nosotros veremos los sensores correctos seràn los candidatos para llegar a lider .i,e. de agregación . Asuminos que cada sensor tiene la capacidad para almacenar valores de algunas variables

2.1 El Detector de Fallas OMEGA

Chandra, Hadzilacos y Toueg se define en [1], al detector de fallas Omega. La salida del detector de fallo de módulo
Omega en un proceso p es un proceso único q, que actualmente p, se considera correcto (decimos que p confía q). el detector de fallas Omega cumple con los siguientes propiedades:
Propiedad 1: Hay un tiempo después de que todos los procesos correctos
siempre confianr en el mismo proceso correcto.
La salida del modulo del detector de fallo Omega, el proceso p puede cambiar a través del tiempo, i,e .es decir, p confía en procesos diferentes en momentos diferentes. Además, en cualquier
Momento dado t, y dos procesos p y q puede confiar en diferentes
Procesos.
Observe que esta definición de Omega considera que con el tiempo
El líder común se mantiene siempre como tal .

En nuestro modelo de sistema, Debido a la escasa duración de la batería de sensores, esta definición no es la adecuada para nuestro propósito. Estamos redefiniendo Omega en la propiedad 2. consideramos que eventualmente el lider común se mantendrá hasta el final de su batería.
Propiedad 2: Hay un tiempo después de que todos los correctos
Sensores de confiar en el mismo sensor hasta que el agregador
Final de su batería.
Propiedad 2: Hay un tiempo después en el cual todos los sensores correctos confian en el mismo sensor agregador mientras se agote la bateria.

3.        NIVEL LOCAL (Dentro de la Región )

En esta secciòn presentamos tres algoritmos de elección del agregador y de la agregación de datos para el nivel dentro de la región :

·         El primer algoritmo el cual se asume que cada par de sensores de la regiòn pueden comunicarse directamente.

·         Un segundo algoritmo el cual asume que algun sensor es correcto y puede comunicarse directamente con el resto de sensores de la regiòn.

·         Un tercer algoritmo el cual asume de un camino multi bidireccional de algún sensor correcto para el resto de sensores de la regiòn.

3.1       El primer algoritmo.

Presentamos el primer algoritmo de elecciòn del agregador y de agregación de datos para el nivel local en el cual se asume que los sensores se activan periódicamente y proveen la transmisión de sus datos y el resto de tiempo de hibernación. La hibernación del sensor no se considera una falla mientras este programada su tarea. Esta hipótesis implica una programación de los interruptores de encendido y apagado de los sensores que son ayudados por el reloj, con activación en unidades de tiempo. Asumimos que el perìodo de hibernación es por largo tiempo hasta que se activen. En la figura 1. Asuminos un màximo paro del reloj ε entre un par de sensores.El algoritmo requiere identificadores del sensor para ordenarlos totalmente, pero no necesariamente en forma consecutiva. Màs aùn los sensores no necesitan conocer los identificadores del resto de sensores que actuan. Asumimos que todos los sensores de una regiòn pueden comunicarse directamente , existiendo un desconocimiento obligado de espera del mensaje &.Suponemos que la ejecución de cada linea del algoritmo requiere de la mayoria de unidades de tiempo de ό .

En la figura 2 . se presenta el algoritmo en detalle.

El algoritmo utiliza tanto el almacenaje temporal como el estable. El sensor elegido como sensor agregador p, confia por p, se asigna a una variable liderp. las variables incluyen ( PRIVADAS ) un número de entrada , iniciado en 0(cero),

que se incrementa durante inicialización y cada vez que se recupera de un accidente. Variables Incarnationp, leaderp, incarnationleader y Timeoutp, son persistentemente almacenadas la variable prevista wakeupp, sigue siendo inestable en el almacenamiento. Además de eso, cada sensor tiene temporizador local utilizado para detectar los posibles fallos del sensor agregador. La variable prevista wakeupp mantiene su valor durante los períodos de hibernación, mientras que el sensor fracase o por el agotamiento de la batería puede ser causas de la pérdida de su valor.
(Prevista wakeupp = FALSO). Constante de tiempo de Δ .Determina el crecimiento del tiempo de espera en el fin de llegar a un
Acuerdo. El más alto es este valor, más rápidamente un acuerdo sobre un   agregador común.Sin embargo un valor excesivamente alto del Timeoutp puede inducir a los sensores hasta el agotamiento de sus baterias. Lo que posiblemente demoraria la detección de la falla del agregador. La constante Δ Data-acquisition., Δ constante de la ADQUISICIÓN DE DATOS. representa el màximo tiempo que ha pasado por el agregador durante la recolección de los datos proporcionados por los sensores.

Máximo el tiempo dedicado por el agregador durante la reunión
De los datos proporcionados por los sensores.
Algoritmo de inicialización comienza con el que todos los valores de
Las variables están debidamente recuperados. Después de eso, si el sensor
Considera a sí misma como la actual agregador, el algoritmo comienza
Las tareas 1 y 2. Por otra parte, si el sensor no
Se considera como el actual agregador, el algoritmo se reinicia
El temporizador local y comienza a tareas 2 y 3. Tarea 1 se dedica a la
Anunciar el agregador al resto de los sensores y reunir todos
532
Cada sensor p ejecuta los siguientes:

3.2       El segundo algoritmo.

Presentamos un segundo algoritmo para elecciòn del agregador y de agregación de datos a nivel local. Contrariamente al algoritmo de la sección anterior, asumimos ahora que ningún par de sensores de la región pueden comunicarse directamente, pero hay un subconjunto
de los sensores de la región que es capaz de conectar directamente el resto de los sensores de la región, y también pueden recibir los mensajes emitidos por cada sensor de la región. Así hemos asumido que existe un desconocimiento que obliga a la espera de un mensaje & y que la ejecución de cada línea del algoritmo requiere de la mayor cantidad de unidades de tiempo ό En este algoritmo los sensores deben conocer los identificadores del resto de sensores en ejecución.

El algoritmo trabaja como sigue: Cada sensor p tiene un counterp [q] para cada sensor q, que es la estimación de p´s del número de veces q se ha sospechado. Sensor p selecciona
como su líder en el sensor l ,con los valores más pequeños el counterp[l].
Con el fin de adquirir datos de sensores, y mantener en el Counterp variables de la fecha,de cada sensor p en emisiones cada η unidades de tiempo en cada Mensaje (I-AM-ALIVE, p, counterp, datap) , siendo η el intervalo entre las mediciones del sensor.

Cuando un sensor p recibe un mensaje (I-AM-ALIVE, q, counterq,Dataq), que restablece timerp (q) para cuando se espera recibir el siguiente mensaje (I-AM-ALIVE, q, counterq, dataq), sus actualizaciones Counterp matriz en consecuencia, pide al procedimiento updateLeader (). Si p es el líder, Recoge dataq.
Si timerp (q) expira antes de recibir una nuevo mensaje (I-AM-ALIVE, Q, counterq, dataq), y luego p incrementa su counterp [q],incrementa Timeoutp [q], restablece Timerp (q), y llama también updateLeader (). El siguiente mensaje enviado por p incluirá el incremento de Counterp [q], y este serà el camino para el resto de sensores que saben sobre p´s acerca de las sospechas sobre en q.
El algoritmo incluye un mecanismo para evitar la larga espera inestable de los sensores preocupante de la elección el líder. Este mecanismo se basa en la encarnación en base al número de sensores.
Durante la inicialización, cada sensor p inicializa sus tiempos
Con respecto al resto de los sensores a η + incarnationp (Línea 4).
Además,p inicializa counterp p [p] a incarnationp (línea 7).
Estas initializaciones aseguran que eventualmente (1) cada sensor inestable
P nunca sospechar de un sensor correcto q que se pueden comunicar
directamente con todos los demás sensores (desde el tiempo de p´s
con respecto q sigue aumentando siempre, y por lo tanto el tiempo
Timerp (q) nunca expirará), y, en consecuencia, p no
Incrementara el counterp [q] de ahora en adelante, y (2) cada sensor inestable
P nunca será elegido como el líder en el updateLeader ().

3.3        El tercer algoritmo.

se presenta un tercer algoritmo de elecciòn del agregador y de agregación de datos para nivel Local. Contrariamente al algoritmo anterior, no requiere ningún sensor para comunicarse directamente con el resto, pero necesita la existencia de una ruta multi. bidireccional de algunos Sensor (s) correctos para llegar al resto de sensores. También, de manera similar al primer algoritmo, para los sensores no es necesario conocer los identificadores de la
resto de los sensores de antelación.

Previamente asuminos que hay un desconocimiento de la obligación sobre la espera & de los mensajes y que la ejecución de cada línea del algoritmo requiere de la mayor cantidad de unidades de tiempo ό. Los sensores escogen como agregador al sensor p y es el sensosr con el valor mínimo asociado de membershipp ( min(membershipp )) para romper los lazos . El algoritmo utiliza una variable membershipp para almacenar los identificadores de los diferentes sensores vistos hasta ahora , contiene un conjunto de tuplas (q, v), para
cada uno de los sensores conocidos, donde q es el sensor de identificación y v
es el más o menos el número de veces que los sensores han sospechado q.

4. Nivel GLOBAL) entre Regiones.

Todos los agregadotes usualmente no pueden comunicarse directamente entre ellos para recolectar la información que se emite en las diferentes regiones de la ampli àrea global WSN. Sin embargo para esta parte, suponemos que cada par de agregadores se pueden comunicar, ya sea directamente o indirectamente (por re-emisión). Basados en esta hipótesis presentamos los algoritmos de elecciòn del agregador y de los de agregación de datos para el nivel global.

Consiste en una adaptación del primer algoritmo para el nivel local , suponemos que para hacerlo los agregadores no necesita conocer la identificación del resto de agregadores
de antelación.

Con este algoritmo en el cual , todos los agregadores seleccionan como super-agregador al agregador con el mínimo número de Encarnación , utilizando el Identificador de agregador para el rompimiento de Vínculos. Curiosamente, el algoritmo que permite a distintas regiones
Ejecutar cualquiera de los tres algoritmos para el nivel local (intra-región).

5. Energia consciente En la elecciòn agregador y agregación de datos.

Desde el enfoque jerarquico hemos seguido dos niveles de energia para para la radiodifusión de los mensajes , lo cual corresponde a los niveles de energía gastada en envio de mensajes dentro de la regiòn y entre las regiones respectivamente. En los algoritmos presentados anteriormente eventualmente el sensor agregador permanece como tal hasta que termine la energía de la bateria. Tomando en consideración como un contador de energìa de la bateria del sensor en el acto de agregación y que va decreciendo conforme va pasando el tiempo . El agotamiento de la bateria , el umbral de agotamiento de la bateria puede ser considerado cuando un agregador detecta un nivel bajo del umbral de agotamiento de la bateria. Lo que introduce al sistema para que se elija otro agregador. De esta manera el agregador preserva alguna energía para mantener regularmente en actividad al sensor.

6. Conclusiones

En este trabajo se han presentado tres algoritmos jerárquicos paara la agregación de datos en grandes redes inalámbricas de sensores, donde los sensores pueden caerse y recuperarse.
Los algoritmos, basado en el detector de fallas   Omega, permite la selección de un sensor agregador y la carga de la recopilación de datos de su región de influencia, y la selección de un super-agregador encargado de los datos recogidos por el conjunto de los agregadores de la red. El primer algoritmo asume que cada par de sensores en una región pueden comunicarse directamente, y para los sensores no es necesario saber de los identificadores del resto de los sensores a priori. El segundo algoritmo requiere que algunos sensor (s) puedan comunicarse directamente con el resto de sensores de la región, pero los sensores necesitan conocer los identificadores del resto de los sensores a priori. Por último, el tercer algoritmo sólo requiere la existencia de una ruta bidireccional de algunos Sensor(s)correctos para el resto de los sensores de la región. También hemos presentado un una propuesta el umbral de agotamiento de la batería que ofrece un mecanismo de energía consistente para la elección del agregador y de la agregación de datos.

REFERENCIAS

[1] T. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector

for solving consensus. Journal of the ACM, 43(4):685–722, July 1996.

[2] Y. Chen A.L. Liestman and J. Liu. Energy-efficient data aggregation

hierarchy for wireless sensor networks. In QShine’05: Proceedings of

the 2nd International Conference on Quality of Service in Heterogeneous

Wired/Wireless Networks, page 7, Lake Buena Vista (FL), USA, August

2005. IEEE Computer Society Press.

[3] G. Chockler, S Gilbert, and Boaz Patt-Shamir. Communicationefficient

probabilistic quorum systems for sensor networks. In PerCom

2006 Workshops: Proceedings of the 4th IEEE Conference on Pervasive

Computing and Communications Workshops, pages 111–117, Pisa, Italy,

March 2006. IEEE Computer Society.

[4]K Hatzis, G Pentaris, G Spirakis, V TAMPAKAS. R.tau., Fundamental Control Algorithms in mobile networks.,ACM, Symposium on Parllel Algorithm and Architectures, France June 1999.ACM PRES.

[5] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient

communication protocol for wireless microsensor networks.

In Proceedings of the 33nd Hawaii International Conference on

System Science, (HICSS`2000),Miami, Hawaii, January 2000.

[6] F. Hu, Cao, and C May. Optimized scheduling for data

aggregation in wireless sensor networks. In ITCC’05: Proceedings of

the International Conference on Information Technology: Coding and

Computing, (ITTC2005) volume 2, pages 557–561, Las Vegas (NV), USA, April

2005. IEEE Computer Society.

[7] E. Jimenez.,S. Arévalo and Fernàndez., Implementing Unreliable Failure Detectors with Unknown Membership. Information Processing Letters, 100(2)-60-63,2006

[8] M. Kumar, L. Schwiebert, and M. Brockmeyer. Efficient data aggregation

middleware for wireless sensor networks. In Proceedings of the First

International Conference on Mobile, Ad-Hoc, and Sensor Systems, pages

579–581, Ft. Lauderdale (FL), USA, October 2004. IEEE Computer

Society Press.

[9] N.Lynch.Distributed Algorithms. Boston (MT), usa, July 1996.

[10] B. Przydatek, Dawn Xiaodong Song, and A. Perrig. Sia: secure

information aggregation in sensor networks. In SenSys’03: Proceedings

of the 1st International Conference on Embedded Networked Sensor

Systems, pages 255–265, Los Angeles (CA), USA, November 2003.

ACM.

[11] K Vaidyanathan, Sayantan Sur, Sundeep Narravula, and Prasun

Sinha. Data aggregation techinques in sensor networks. Technical

Report 11/04-TR60, OSU-CISRC,The Ohio University, November 2004.