Algoritmo de Brooks-Iyengar

El algoritmo Brooks-Iyengar , también conocido como 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 distribuida , incluso en presencia de sensores defectuosos ^{[ 2 ]} . La red de sensores logra esto intercambiando el valor medido y el valor de exactitud en cada nodo con todos los demás nodos, y calcula el rango de exactitud y un valor medido para toda la red a partir de todos los valores recopilados. Incluso si algunos de los datos de algunos sensores son defectuosos, la red de sensores no sufrirá un mal funcionamiento. El algoritmo es tolerante a fallos y distribuido. También podría utilizarse como método de fusión de sensores. Los límites de precisión y exactitud de este algoritmo se demostraron en 2016 ^{[ 3 ].}

El algoritmo híbrido Brooks-Iyengar para el control distribuido en presencia de datos ruidosos combina la concordancia bizantina con la fusión de sensores . Cierra la brecha entre la fusión de sensores y la tolerancia a fallos bizantinos. ^{[ 4 ]} Este algoritmo seminal unificó estos campos dispares por primera vez. Esencialmente, combina el algoritmo de Dolev ^{[ 5 ]} para la 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 forma maliciosa. Toma como entrada valores reales con imprecisión inherente o ruido (que puede ser desconocido), 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 de software , computación de alto rendimiento , etc. ^{[ 7 ]}

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

Aporte:

La medición 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:

El resultado de PE i incluye una estimación puntual y una estimación por intervalos.

1. PE i recibe mediciones de todos los demás PE.
2. Divide la unión de las mediciones recopiladas en intervalos mutuamente excluyentes en función del número de mediciones que se intersecan, lo que se conoce como el peso del intervalo.
3. Eliminar intervalos con peso menor que${\displaystyle N-\tau }$, dónde${\displaystyle \tau }$es el número de PE defectuosos
4. Si quedan L intervalos, dejemos${\displaystyle A_{i}}$denotemos el conjunto de los intervalos restantes. Tenemos${\displaystyle A_{i}=\{(I_{1}^{i},w_{1}^{i}),\dots ,(I_{L}^{i},w_{L}^{i})\}}$donde intervalo${\displaystyle I_{l}^{i}=[l_{I_{l}^{i}},h_{I_{l}^{i}}]}$y${\displaystyle w_{l}^{i}}$es el peso asociado con el intervalo${\displaystyle I_{l}^{i}}$También asumimos${\displaystyle h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}}$.
5. Calcular la estimación puntual${\displaystyle v_{i}'}$de PE i como ${\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}}}}$y la estimación del intervalo es${\displaystyle [l_{I_{1}^{i}},h_{I_{L}^{i}}]}$

Ejemplo:

Consideremos un ejemplo de 5 PE, en el que PE 5 (${\displaystyle S_{5}}$) está enviando valores incorrectos a otros PE y todos intercambian los valores.

Los valores recibidos por${\displaystyle S_{1}}$están en la siguiente tabla.

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

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

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

${\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 datos de entrada y los resultados de los 5 PE:

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.

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

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

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

Consenso vectorial bizantino de 2013: ^{[ 11 ]} El método utiliza vectores como entrada.

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

Podríamos usar 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 en este caso.

El algoritmo de Brooks-Iyengar es un trabajo fundamental y un hito importante en la detección distribuida, y podría utilizarse como una solución tolerante a fallos 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 condujo al desarrollo de la primera versión de RT-Linux.

En el año 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 datos de sensores heterogéneos en la aplicación desarrollada por BBN Technologies, BAE Systems, Penn State Applied Research Lab (ARL) y USC/ISI.

El Grupo Thales , fabricante británico de equipos de defensa, utilizó este trabajo en su Laboratorio Global de Análisis Operacional. Se aplica a los programas de Raytheon, donde numerosos sistemas necesitan extraer datos fiables de redes de sensores poco fiables, lo que reduce la creciente inversión en la mejora de la fiabilidad de los sensores. Asimismo, la investigación para el desarrollo de este algoritmo dio como resultado las herramientas utilizadas por la Armada de los Estados Unidos en su software de conocimiento del dominio marítimo.

En el ámbito educativo, el algoritmo Brooks-Iyengar se ha utilizado ampliamente en la enseñanza en universidades como la de Wisconsin, Purdue, Georgia Tech, Clemson, Maryland, etc.

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