Algoritmus Brooks – Iyengar - Brooks–Iyengar algorithm

The Algoritmus Brooks – Iyengar nebo Hybridní algoritmus Brooks – Iyengar ^[1] je distribuovaný algoritmus který zlepšuje přesnost i přesnost intervalová měření přijato a distribuovaná síť senzorů, a to i za přítomnosti vadných senzorů.^[2] Síť senzorů to provádí výměnou naměřené hodnoty a hodnoty přesnosti v každém uzlu se všemi ostatními uzly a ze všech shromážděných hodnot vypočítá rozsah přesnosti a naměřenou hodnotu pro celou síť. I když jsou některá data z některých senzorů vadná, síť senzorů nebude fungovat správně. Algoritmus je odolný vůči chybám a distribuovaný. Mohlo by to být také použito jako metoda fúze senzorů. Přesnost a přesnost vázaná na tento algoritmus byla prokázána v roce 2016.^[3]

Pozadí

Brooks – Iyengar hybridní algoritmus pro distribuované řízení za přítomnosti hlučných datových kombajnů Byzantská dohoda s fúze senzorů. Překlenuje propast mezi fúzí senzorů a byzantskou odolností proti chybám.^[4] Tento klíčový algoritmus poprvé sjednotil tato různorodá pole. V podstatě kombinuje Dolevovy^[5] algoritmus pro přibližnou shodu s Mahaneyovým a Schneiderovým algoritmem rychlé konvergence (FCA). Algoritmus předpokládá N zpracovatelské prvky (PE), t z nichž jsou vadné a mohou se chovat zlomyslně. Bere jako vstup buď skutečné hodnoty s inherentní nepřesností nebo šumem (které mohou být neznámé), nebo skutečnou hodnotu s apriori definovanou nejistotou nebo interval. Výstupem algoritmu je skutečná hodnota s výslovně stanovenou přesností. Algoritmus běží Ó(NlogN) kde N je počet PE. Je možné upravit tento algoritmus tak, aby odpovídal Crusader's Convergence Algorithm (CCA),^[6] požadavek na šířku pásma se však také zvýší. Algoritmus má aplikace v distribuovaná kontrola, spolehlivost softwaru, Vysoce výkonná výpočetní technika, atd.^[7]

Algoritmus

Algoritmus Brooks – Iyengar se provádí v každém procesním prvku (PE) distribuované sítě senzorů. Každý PE si vyměňuje svůj měřený interval se všemi ostatními PE v síti. „Sloučené“ měření je váženým průměrem středů nalezených oblastí.^[8] Konkrétní kroky algoritmu Brooks – Iyengar jsou uvedeny v této části. Každý PE provádí algoritmus samostatně:

Vstup:

Měření zaslané PE k do PE i je uzavřený interval ${ displaystyle [l_ {k, i}, h_ {k, i}]}$, ${ displaystyle 1 leq k leq N}$

Výstup:

Výstup PE i zahrnuje odhad bodu a odhad intervalu

1. PE i přijímá měření od všech ostatních PE.
2. Rozdělte spojení shromážděných měření do vzájemně se vylučujících intervalů na základě počtu protínajících se měření, který se označuje jako váha intervalu.
3. Odstraňte intervaly s hmotností menší než ${ displaystyle N- tau}$, kde ${ displaystyle tau}$ je počet vadných PE
4. Pokud existují L intervaly zbývají, nech ${ displaystyle A_ {i}}$ označit množinu zbývajících intervalů. My máme ${ displaystyle A_ {i} = {(I_ {1} ^ {i}, w_ {1} ^ {i}), tečky, (I_ {L} ^ {i}, w_ {L} ^ {i }) }}$, kde interval ${ displaystyle I_ {l} ^ {i} = [l_ {I_ {l} ^ {i}}, h_ {I_ {l} ^ {i}}]}$ a ${ displaystyle w_ {l} ^ {i}}$je váha spojená s intervalem ${ displaystyle I_ {l} ^ {i}}$ . Také předpokládáme ${ displaystyle h_ {I_ {l} ^ {i}} leq h_ {I_ {l + 1} ^ {i}}}$.
5. Vypočítejte bodový odhad ${ displaystyle v_ {i} '}$ PE i tak jako ${ 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}}}}$ a odhad intervalu je ${ displaystyle [l_ {I_ {1} ^ {i}}, h_ {I_ {L} ^ {i}}]}$

Příklad:

Zvažte příklad 5 PE, ve kterých PE 5 (${ displaystyle S_ {5}}$) posílá nesprávné hodnoty ostatním PE a všichni si tyto hodnoty vyměňují.

Hodnoty přijaté uživatelem ${ displaystyle S_ {1}}$ jsou v následující tabulce.

	${ displaystyle S_ {1}}$	${ displaystyle S_ {2}}$	${ displaystyle S_ {3}}$	${ displaystyle S_ {4}}$	${ displaystyle S_ {5}}$
${ displaystyle S_ {1}}$hodnoty	${ displaystyle [2.7,6,7]}$	${ displaystyle [0,3,2]}$	${ displaystyle [1.5,4.5]}$	${ displaystyle [0.8,2,8]}$	${ displaystyle [1.4,4.6]}$

Z těchto intervalů nakreslíme diagram vážených oblastí (WRD), který pak můžeme určit ${ displaystyle A_ {1}}$ pro PE 1 podle Algoritmu:

${ displaystyle A_ {1} = {([1,5,2,7], 4), ([2,7,2,8], 5), ([2,8,3,2], 4) }}$

který se skládá z intervalů, kde alespoň 4 (= ${ displaystyle N- tau}$ = 5−1) měření se protínají. Výstup PE 1 se rovná

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

a odhad intervalu je ${ displaystyle [1.5,3.2]}$

Podobně bychom mohli získat všechny vstupy a výsledky 5 PE:

PE	Vstupní intervaly	Odhad výstupního intervalu	Odhad výstupního bodu
${ displaystyle S_ {1}}$	${ Displaystyle [2,7,6,7], [0,3,2], [1,5,4,5], [0,8,2,8], [1,4,4,6]}$	${ displaystyle [1.5,3.2]}$	2.625
${ displaystyle S_ {2}}$	${ displaystyle [2,7,6,7], [0,3,2], [1,5,4,5], [0,8,2,8], [- 0,6,2,6]}$	${ displaystyle [1.5,2,8]}$	2.4
${ displaystyle S_ {3}}$	${ displaystyle [2,7,6,7], [0,3,2], [1,5,4,5], [0,8,2,8], [0,9,4,1]}$	${ displaystyle [1.5,3.2]}$	2.625
${ displaystyle S_ {4}}$	${ displaystyle [2,7,6,7], [0,3,2], [1,5,4,5], [0,8,2,8], [- 0,7,2,5]}$	${ displaystyle [1.5,2,8]}$	2.375
${ displaystyle S_ {5}}$	${ displaystyle [2.7,6.7], [0,3,2], [1,5,4,5], [0,8,2,8], [{ text {-}}, { text {-}}]}$	——	——

Související algoritmy

Byzantský problém z roku 1982:^[5] Byzantský obecný problém ^[9] jako rozšíření Problém dvou generálů lze považovat za binární problém.

Přibližný konsenzus 1983:^[10] Metoda odstraní některé hodnoty ze sady sestávající ze skalárů na tolerantní vadné vstupy.

Přesný konsenzus z roku 1985:^[7] Metoda také používá jako vstup skalární.

Algoritmus Brooks-Iyengar 1996:^[1] Metoda je založena na intervalech.

Konsenzus byzantských vektorů z roku 2013:^[11] Metoda používá jako vstup vektory.

Multidimenzionální dohoda z roku 2013:^[12] Metoda také používá vektory jako vstup, zatímco míra vzdálenosti je jiná.

K řešení vstupů do intervalů jsme mohli použít přibližný konsensus (skalární), Brooks-Iyengarův algoritmus (založený na intervalech) a byzantský vektorový konsensus (založený na vektorech) a papír ^[3] dokázal, že Brooks – Iyengarův algoritmus je zde nejlepší.

aplikace

Algoritmus Brooks – Iyengar je klíčovým dílem a významným mezníkem v distribuovaném snímání a lze jej použít jako řešení odolné vůči chybám pro mnoho scénářů redundance.^[13] Je také snadné jej implementovat a vložit do všech síťových systémů.^[14]

V roce 1996 byl algoritmus použit v systému MINIX k zajištění větší přesnosti a přesnosti, což vede k vývoji první verze RT-Linux.

V roce 2000 byl algoritmus také ústředním bodem distribuovaného sledovacího programu programu DARPA SensIT. Akustické, seismické a detekce pohybu z více senzorů jsou kombinovány a přiváděny do distribuovaného sledovacího systému. Kromě toho bylo použito ke kombinování heterogenních vstupů senzorů v aplikaci, kterou využívají BBN Technologies, BAE systems, Penn State Applied Research Lab (ARL) a USC / ISI.

Kromě toho společnost Thales Group, britský výrobce obrany, využila tuto práci ve své globální laboratoři pro operační analýzu. Aplikuje se na programy společnosti Raytheon, kde mnoho systémů potřebuje extrahovat spolehlivá data ze nespolehlivé sítě senzorů, což vylučuje rostoucí investice do zlepšování spolehlivosti senzorů. Výzkum při vývoji tohoto algoritmu také vede k nástrojům, které používá US Nav ve svém softwaru pro zvyšování povědomí o námořní doméně.

Ve výuce byl algoritmus Brooks – Iyengar široce používán ve výuce tříd jako University of Wisconsin, Purdue, Georgia Tech, Clemson University, University of Maryland atd.

Kromě oblasti senzorové sítě by mohly také těžit další oblasti, jako je časem spouštěná architektura, bezpečnost kyberfyzikálních systémů, fúze dat, konvergence robotů, vysoce výkonné výpočty, spolehlivost softwaru / hardwaru, učení souborů v systémech umělé inteligence z algoritmu Brooks – Iyengar.

Charakteristika algoritmu

Viz také

Ocenění a uznání

Vynálezci algoritmu Brooks Iyengar Dr Brooks a Dr. SS Iyengar obdrželi prestižní 25letou cenu Test of Time Award za průkopnický výzkum a vysoký dopad algoritmu Brooks-Iyengar. Výzkum s velkým dopadem a to, jak tato práce ovlivnila řadu vládních programů a komerčních produktů v USA.

• Dr SS Iyengar obdržel ocenění od profesora Steva Yau, IEEE

Cena za test času pro algoritmus Brookse Iyengara

• Dr. SS Iyengar se svým studentem Dr. Brooksem

Dr. Brooks a Dr. SS Iengar na slavnostním ceremoniálu

Reference