ブルックス・アイエンガーアルゴリズム

Brooks –Iyengarアルゴリズム、FuseCPAアルゴリズム、またはBrooks–Iyengarハイブリッドアルゴリズム^{[ 1 ]}は、分散型センサーネットワークによって取得される間隔測定の精度と正確さの両方を向上させる分散型アルゴリズムであり、センサーに不具合がある場合でも同様です。^{[ 2 ]} センサーネットワークは、各ノードの測定値と正確さの値を他のすべてのノードと交換し、収集されたすべての値からネットワーク全体の正確さの範囲と測定値を計算することによってこれを実現します。一部のセンサーからのデータの一部に不具合があっても、センサーネットワークは誤動作しません。このアルゴリズムは耐障害性があり、分散型です。センサー融合手法としても使用できます。このアルゴリズムの精度と正確さの限界は2016年に証明されています。^{[ 3 ]}

ノイズのあるデータが存在する場合の分散制御のためのBrooks–Iyengarハイブリッド アルゴリズムは、ビザンチン合意とセンサー フュージョンを組み合わせたものです。センサー フュージョンとビザンチン耐障害性の間のギャップを埋めます。^{[ 4 ]}この画期的なアルゴリズムは、これらの異なる分野を初めて統合しました。本質的には、近似合意のための Dolev ^{[ 5 ]}のアルゴリズムと Mahaney および Schneider の高速収束アルゴリズム (FCA) を組み合わせたものです。このアルゴリズムは、N 個の処理要素 (PE) を想定しており、そのうちt 個は故障しており、悪意を持って動作する可能性があります。入力として、固有の不正確さまたはノイズ (未知の場合もある) を持つ実数値、または事前に定義された不確実性を持つ実数値、または区間を受け取ります。アルゴリズムの出力は、明示的に指定された精度を持つ実数値です。このアルゴリズムは、Nを PE の数として、O ( N log N )で実行されます。このアルゴリズムは、クルセイダーの収束アルゴリズム（CCA） ^{[ 6 ]}に対応するように変更することも可能ですが、帯域幅の要件も増加します。このアルゴリズムは、分散制御、ソフトウェアの信頼性、高性能コンピューティングなどに応用されています^{[ 7 ]。}

Brooks–Iyengarアルゴリズムは、分散センサネットワークの各処理要素（PE）で実行されます。各PEは、ネットワーク内の他のすべてのPEと測定された間隔を交換します。「融合」された測定値は、検出された領域の中点の加重平均です。^{[ 8 ]} Brooks–Iyengarアルゴリズムの具体的な手順をこのセクションで示します。各PEは、アルゴリズムを個別に実行します。

入力：

PE kからPE iに送信される測定値は閉区間である${\displaystyle [l_{k,i},h_{k,i}]}$、${\displaystyle 1\leq k\leq N}$

出力：

PE iの出力には、点推定値と区間推定値が含まれます。

1. PE i は、他のすべての PE から測定値を受け取ります。
2. 収集した測定値の集合を、交差する測定値の数に基づいて互いに排他的な区間に分割します。この交差する測定値の数は、区間の重みとして知られています。
3. 重量が以下のインターバルを削除${\displaystyle N-\tau }$、 どこ$\displaystyle \tau }$は、故障したPEの数です。
4. 残りの区間がL個ある場合は、${\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. 点推定値を計算する${\displaystyle v_{i}'}$PE 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}}]}$

例：

5 つの PE の例を考えてみましょう。PE 5 (${\displaystyle S_{5}}$) は他の PE に誤った値を送信し、それらはすべて値を交換します。

受け取った値${\displaystyle S_{1}}$次の表に示されています。

これらの区間の加重領域図（WRD）を描き、${\displaystyle A_{1}}$アルゴリズムによるPE 1の場合：

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

これは、少なくとも 4(=${\displaystyle N-\tau }$= 5−1) 測定値が交差する。PE 1 の出力は

${\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}$

そして区間推定値は${\displaystyle [1.5,3.2]}$

同様に、5つのPEのすべての入力と結果を取得できます。

1982年のビザンチン問題：^{[ 5 ]} 2人の将軍の問題の拡張であるビザンチン将軍問題^{[ 9 ]}は、二項問題と見なすことができる。

1983 近似コンセンサス: ^{[ 10 ]}この方法は、スカラーで構成されるセットからいくつかの値を削除して、不良入力を許容します。

1985年不正確コンセンサス: ^{[ 7 ]}この方法も入力としてスカラーを使用します。

1996年ブルックス・アイエンガーアルゴリズム：^{[ 1 ]}この方法は区間に基づいています。

2013年ビザンチンベクトルコンセンサス: ^{[ 11 ]}この方法は入力としてベクトルを使用します。

2013 多次元合意: ^{[ 12 ]}この方法も入力としてベクトルを使用するが、距離の尺度は異なる。

区間入力を処理するために、近似コンセンサス（スカラーベース）、ブルックス・アイエンガーアルゴリズム（区間ベース）、ビザンチンベクトルコンセンサス（ベクトルベース）を使用できますが、論文^{[ 3 ]}ではブルックス・アイエンガーアルゴリズムが最適であることが証明されています。

Brooks–Iyengarアルゴリズムは、分散センシングにおける先駆的な研究であり、大きなマイルストーンであり、多くの冗長シナリオに対するフォールトトレラントソリューションとして使用できます。^{[ 13 ]}また、あらゆるネットワークシステムに簡単に実装および組み込むことができます。^{[ 14 ]}

1996年、このアルゴリズムはMINIXで使用され、より高い精度と正確性を実現した。これがRT-Linuxの最初のバージョンの開発につながった。

2000年には、このアルゴリズムはDARPAのSensITプログラムの分散型追跡プログラムの中核を成すものでした。複数のセンサーからの音響、地震、および動きの検出データが統合され、分散型追跡システムに入力されます。さらに、BBN Technologies、BAE Systems、ペンシルベニア州立大学応用研究所（ARL）、および南カリフォルニア大学/ISIが開発したアプリケーションにおいて、異種センサーからのデータを統合するためにも使用されました。

英国の防衛関連企業であるタレス・グループは、この研究成果をグローバル運用分析研究所で活用しました。レイセオン社のプログラムでは、多くのシステムが信頼性の低いセンサーネットワークから信頼性の高いデータを抽出する必要があるため、この技術はセンサーの信頼性向上への投資増加を抑制する効果があります。また、このアルゴリズムの開発研究は、米海軍の海上領域認識ソフトウェアで使用されるツールにも活用されています。

教育分野では、ブルックス・アイエンガーアルゴリズムは、ウィスコンシン大学、パデュー大学、ジョージア工科大学、クレムソン大学、メリーランド大学などの授業で広く利用されている。

センサーネットワークの分野に加えて、時間トリガー型アーキテクチャ、サイバーフィジカルシステムの安全性、データ融合、ロボットの融合、高性能コンピューティング、ソフトウェア／ハードウェアの信頼性、人工知能システムにおけるアンサンブル学習といった他の分野も、ブルックス・アイエンガーアルゴリズムの恩恵を受ける可能性がある。