Algoritmo de Brooks-Iyengar

Algoritmo distribuido para redes de sensores.

El algoritmo Brooks-Iyengar o algoritmo FuseCPA o algoritmo híbrido Brooks-Iyengar ^[1] es un algoritmo distribuido que mejora tanto la precisión como la exactitud de las mediciones de intervalo tomadas por una red de sensores distribuidos , incluso en presencia de sensores defectuosos. ^[2] La red de sensores hace esto intercambiando el valor medido y el valor de precisión en cada nodo con todos los demás nodos, y calcula el rango de precisión y un valor medido para toda la red a partir de todos los valores recopilados. Incluso si algunos de los datos de algunos de los sensores son defectuosos, la red de sensores no funcionará mal. El algoritmo es tolerante a fallos y distribuido. También podría utilizarse como método de fusión de sensores. La precisión y exactitud de este algoritmo se demostraron en 2016. ^[3]

Fondo

El algoritmo híbrido Brooks-Iyengar para el control distribuido en presencia de datos ruidosos combina el acuerdo bizantino con la fusión de sensores . Cierra la brecha entre la fusión de sensores y la tolerancia a fallas bizantinas. ^[4] Este algoritmo fundamental unificó estos campos dispares por primera vez. Esencialmente, combina el algoritmo de Dolev ^[5] para una concordancia aproximada con el algoritmo de convergencia rápida (FCA) de Mahaney y Schneider. El algoritmo asume N elementos de procesamiento (PE), t de los cuales son defectuosos y pueden comportarse de manera maliciosa. Toma como entrada valores reales con inexactitud o ruido inherentes (que pueden ser desconocidos), o un valor real con incertidumbre definida a priori, o un intervalo. La salida del algoritmo es un valor real con una precisión especificada explícitamente. El algoritmo se ejecuta en O ( N log N ) donde N es el número de PE. Es posible modificar este algoritmo para que corresponda al algoritmo de convergencia de Crusader (CCA), ^[6] sin embargo, el requisito de ancho de banda también aumentará. El algoritmo tiene aplicaciones en control distribuido , confiabilidad del software , computación de alto rendimiento , etc. ^[7]

Algoritmo

El algoritmo de Brooks-Iyengar se ejecuta en cada elemento de procesamiento (PE) de una red de sensores distribuidos. Cada PE intercambia su intervalo medido con todos los demás PE de la red. La medida "fusionada" es un promedio ponderado de los puntos medios de las regiones encontradas. ^[8] Los pasos concretos del algoritmo de Brooks-Iyengar se muestran en esta sección. Cada PE realiza el algoritmo por separado:

Aporte:

La medida enviada por PE k a PE i es un intervalo cerrado , ${\displaystyle [l_{k,i},h_{k,i}]}$ ${\displaystyle 1\leq k\leq N}$

Producción:

La salida de PE i incluye una estimación puntual y una estimación de intervalo

1. PE i recibe mediciones de todos los demás PE.
2. Divida la unión de mediciones recopiladas en intervalos mutuamente excluyentes en función del número de mediciones que se cruzan, lo que se conoce como peso del intervalo.
3. Elimine los intervalos con un peso inferior a , ¿dónde está el número de PE defectuosos? ${\displaystyle N-\tau }$ ${\displaystyle \tau }$
4. Si quedan L intervalos, denotemos el conjunto de los intervalos restantes. Tenemos , donde intervalo y es el peso asociado al intervalo . También suponemos . ${\displaystyle A_{i}}$ ${\displaystyle A_{i}=\{(I_{1}^{i},w_{1}^{i}),\dots ,(I_{L}^{i},w_{L}^{i})\}}$ ${\displaystyle I_{l}^{i}=[l_{I_{l}^{i}},h_{I_{l}^{i}}]}$ ${\displaystyle w_{l}^{i}}$ ${\displaystyle I_{l}^{i}}$ ${\displaystyle h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}}$
5. Calcule la estimación puntual de PE i as y la estimación de intervalo es ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}'={\frac {\sum _{l}{\frac {(l_{I_{l}^{i}}+h_{I_{l}^{i}})\cdot w_{l}^{i}}{2}}}{\sum _{l}w_{l}^{i}}}}$ ${\displaystyle [l_{I_{1}^{i}},h_{I_{L}^{i}}]}$

Ejemplo:

Considere un ejemplo de 5 PE, en el que PE 5 ( ) envía valores incorrectos a otros PE y todos intercambian los valores. ${\displaystyle S_{5}}$

Un ejemplo del algoritmo de Brooks-Iyengar

Los valores recibidos por se encuentran en la siguiente Tabla. ${\displaystyle S_{1}}$

WRD por el algoritmo de Brooks-Iyengar

Dibujamos un diagrama de región ponderada (WRD) de estos intervalos, luego podemos determinar para PE 1 según el algoritmo: ${\displaystyle A_{1}}$

${\displaystyle A_{1}=\{([1.5,2.7],4),([2.7,2.8],5),([2.8,3.2],4)\}}$

que consta de intervalos donde se cruzan al menos 4 (= = 5−1) mediciones. La salida de PE 1 es igual a ${\displaystyle N-\tau }$

${\displaystyle {\frac {4*{\frac {1.5+2.7}{2}}+5*{\frac {2.7+2.8}{2}}+4*{\frac {2.8+3.2}{2}}}{13}}=2.625}$

y la estimación del intervalo es ${\displaystyle [1.5,3.2]}$

De manera similar, podríamos obtener todos los insumos y resultados de los 5 PE:

Algoritmos relacionados

Problema bizantino de 1982: ^[5] El problema general bizantino ^[9] como una extensión del problema de los dos generales podría verse como un problema binario.

Consenso aproximado de 1983: ^[10] El método elimina algunos valores del conjunto formado por escalares para tolerar entradas defectuosas.

Consenso inexacto de 1985: ^[7] El método también utiliza escalar como entrada.

1996 Algoritmo de Brooks-Iyengar: ^[1] El método se basa en intervalos.

Consenso de vectores bizantinos de 2013: ^[11] El método utiliza vectores como entrada.

Acuerdo multidimensional de 2013: ^[12] El método también utiliza vectores como entrada, mientras que la medida de la distancia es diferente.

Podríamos utilizar el consenso aproximado (basado en escalares), el algoritmo de Brooks-Iyengar (basado en intervalos) y el consenso vectorial bizantino (basado en vectores) para tratar con entradas de intervalo, y el artículo ^[3] demostró que el algoritmo de Brooks-Iyengar es el mejor. aquí.

Solicitud

El algoritmo de Brooks-Iyengar es un trabajo fundamental y un hito importante en la detección distribuida, y podría usarse como una solución tolerante a fallas para muchos escenarios de redundancia. ^[13] Además, es fácil de implementar e integrar en cualquier sistema de red. ^[14]

En 1996, el algoritmo se utilizó en MINIX para proporcionar mayor exactitud y precisión, lo que llevó al desarrollo de la primera versión de RT-Linux.

En 2000, el algoritmo también fue fundamental para el programa de seguimiento distribuido del programa DARPA SensIT. Las lecturas acústicas, sísmicas y de detección de movimiento de múltiples sensores se combinan y se introducen en un sistema de seguimiento distribuido. Además, se utilizó para combinar alimentaciones de sensores heterogéneos en la aplicación realizada por BBN Technologies, BAE Systems, Penn State Applied Research Lab (ARL) y USC/ISI.

El Grupo Thales, un fabricante de defensa del Reino Unido, utilizó este trabajo en su Laboratorio de Análisis Operacional Global. Se aplica a los programas de Raytheon donde muchos sistemas necesitan extraer datos confiables de una red de sensores no confiables, lo que exime la creciente inversión en mejorar la confiabilidad de los sensores. Además, la investigación para desarrollar este algoritmo da como resultado las herramientas utilizadas por la Marina de los EE. UU. en su software de concienciación del dominio marítimo.

En educación, el algoritmo de Brooks-Iyengar se ha utilizado ampliamente en clases de enseñanza como la Universidad de Wisconsin, Purdue, Georgia Tech, la Universidad de Clemson, la Universidad de Maryland, etc.

Además del ámbito de las redes de sensores, también podrían beneficiarse otros campos como la arquitectura activada por tiempo, la seguridad de los sistemas ciberfísicos, la fusión de datos, la convergencia de robots, la informática de alto rendimiento, la fiabilidad del software/hardware y el aprendizaje conjunto en sistemas de inteligencia artificial. del algoritmo de Brooks-Iyengar.

Características del algoritmo

• PE defectuosos tolerados < N /3
• PE defectuosos máximos < 2 N /3
• Complejidad = O ( N  log  N )
• Orden del ancho de banda de la red = O ( N )
• Convergencia = 2 t / N
• Precisión = limitada por la entrada
• Itera por precisión = a menudo
• Precisión sobre exactitud = no
• Precisión sobre precisión = no

Ver también

• Red de sensores distribuida
• Fusión de sensores
• Tolerancia a fallos
• Consenso (informática)
• Algoritmo de consenso Chandra-Toueg
• Protocolo de consenso de Paxos
• Algoritmo de consenso de balsa
• algoritmo de marzullo
• Algoritmo de intersección
• El problema de dos generales

premios y reconocimientos

Los inventores del algoritmo Brooks Iyengar El Dr. Brooks y el Dr. SS Iyengar recibieron el prestigioso premio Test of Time de 25 años por su investigación pionera y el alto impacto del algoritmo Brooks-Iyengar. La investigación de alto impacto y cómo este trabajo ha influido en numerosos programas y productos comerciales del gobierno de EE. UU.

• El Dr. SS Iyengar recibe el premio del profesor Steve Yau, IEEE

Premio Test of Time al algoritmo Brooks Iyengar

• Dr. SS Iyengar con su alumno Dr. Brooks

Dr. Brooks y Dr. SS Iyengar en la ceremonia

Referencias

1. Richard R. Brooks y S. Sithrama Iyengar (junio de 1996). "Algoritmo robusto de detección y computación distribuida". Computadora . 29 (6): 53–60. doi :10.1109/2.507632. ISSN  0018-9162. Archivado desde el original el 8 de abril de 2010 . Consultado el 22 de marzo de 2010 .
2. Mohammad Ilyas; Imad Mahgoub (28 de julio de 2004). Manual de redes de sensores: sistemas compactos de detección inalámbricos y por cable (PDF) . Prensa CRC . págs. 25–4, 33–2 de 864. ISBN 978-0-8493-1968-6. Archivado desde el original (PDF) el 27 de junio de 2010 . Consultado el 22 de marzo de 2010 .
3. Ao, Buke; Wang, Yongcai; Yu, Lu; Brooks, Richard R.; Iyengar, SS (1 de mayo de 2016). "Sobre el límite de precisión de los algoritmos de fusión de sensores distribuidos tolerantes a fallas". Computación ACM. Sobrevivir . 49 (1): 5:1–5:23. doi :10.1145/2898984. ISSN  0360-0300. S2CID  13760223.
4. D. Dolev (enero de 1982). "Los generales bizantinos atacan de nuevo" (PDF) . J. Algoritmos . 3 (1): 14–30. doi :10.1016/0196-6774(82)90004-9 . Consultado el 22 de marzo de 2010 .
5. L. Lamport; R. Shostak; M. Pease (julio de 1982). "El problema de los generales bizantinos". Transacciones ACM sobre lenguajes y sistemas de programación . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582. 
6. D. Dolev; et al. (Julio de 1986). "Llegar a un acuerdo aproximado en presencia de fallas" (PDF) . Revista de la ACM . 33 (3): 499–516. CiteSeerX 10.1.1.13.3049 . doi :10.1145/5925.5931. ISSN  0004-5411. S2CID  496234 . Consultado el 23 de marzo de 2010 . 
7. S. Mahaney; F. Schneider (1985). "Acuerdo inexacto: exactitud, precisión y degradación elegante". Actas del cuarto simposio anual de ACM sobre principios de informática distribuida: PODC '85 . págs. 237–249. CiteSeerX 10.1.1.20.6337 . doi :10.1145/323596.323618. ISBN  978-0897911689. S2CID  10858879.
8. Sartaj Sahni y Xiaochun Xu (7 de septiembre de 2004). "Algoritmos para redes de sensores inalámbricos" (PDF) . Universidad de Florida, Gainesville . Consultado el 23 de marzo de 2010 .
9. Lamport, Leslie; Shostak, Robert; Por favor, Marshall (1 de julio de 1982). "El problema de los generales bizantinos". Transmisión ACM. Programa. Lang. Sistema . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. ISSN  0164-0925. S2CID  55899582. 
10. Dolev, Danny; Lynch, Nancy A.; Pinter, Shlomit S.; Stark, Eugene W.; Weihl, William E. (1 de mayo de 1986). "Llegar a un acuerdo aproximado en presencia de fallas". J. ACM . 33 (3): 499–516. CiteSeerX 10.1.1.13.3049 . doi :10.1145/5925.5931. ISSN  0004-5411. S2CID  496234. 
11. Vaidya, Nitin H.; Garg, Vijay K. (1 de enero de 2013). "Consenso de vectores bizantinos en gráficos completos". Actas del simposio ACM de 2013 sobre principios de informática distribuida . PODC '13. Nueva York, NY, Estados Unidos: ACM. págs. 65–73. arXiv : 1302.2543 . doi :10.1145/2484239.2484256. ISBN 9781450320658. S2CID  5914155.
12. Mendes, Hammurabi; Herlihy, Maurice (1 de enero de 2013). "Acuerdo aproximado multidimensional en sistemas asincrónicos bizantinos". Actas del cuadragésimo quinto simposio anual de ACM sobre Teoría de la Computación . ESTOC '13. Nueva York, NY, Estados Unidos: ACM. págs. 391–400. doi :10.1145/2488608.2488657. ISBN 9781450320290. S2CID  13865698.
13. Kumar, Vijay (2012). "Optimizaciones de detección computacional y comprimida para el procesamiento de información en una red de sensores". Revista internacional de informática de próxima generación .
14. Ao, Buke (julio de 2017). "Sistemas de monitoreo del estado de puertas de ferrocarril robustos y tolerantes a fallas: aplicación del algoritmo de detección de Brooks-Iyengar a aplicaciones de transporte". Revista internacional de informática de próxima generación . 8 . S2CID  13592515.