브룩스-아이옌가 알고리즘

더 브룩스-아이옌가 알고리즘이나 브룩스-아이옌가르 하이브리드 알고리즘은 고장 센서가 있더라도 분산 센서 네트워크가 취한 간격 측정의 정밀도와 정확도를 모두 향상시키는 분산 알고리즘이다.^[2]센서 네트워크는 다른 모든 노드와 모든 노드에서 측정된 값과 정확도 값을 교환함으로써 이를 수행하고 수집된 모든 값에서 전체 네트워크에 대한 정확도 범위와 측정값을 계산한다.일부 센서의 데이터 중 일부에 결함이 있다고 해도 센서 네트워크는 오작동하지 않는다.알고리즘은 내결함성이 있고 분산되어 있다.그것은 또한 센서 융합 방법으로도 사용될 수 있다.이 알고리즘의 정밀도와 정확도는 2016년 입증됐다.^[3]

배경

더 브룩스-소음이 많은 데이터가 존재하는 곳에서 분산 제어를 위한 아이옌가 하이브리드 알고리즘은 비잔틴의 동의와 센서 융합이 결합된다.센서 융합과 비잔틴 내결함성 간극을 메운다.^[4]이 세미날 알고리즘은 처음으로 이러한 이질적인 분야를 통일했다.본질적으로, 대략적인 합의를 위한 Dolev의 알고리즘과^[5] Mahaney, Schneider의 빠른 컨버전스 알고리즘(FCA)을 결합한다.알고리즘은 N 처리 요소(PE)를 가정하며, 그 중 결함이 있고 악의적으로 동작할 수 있다.이 값은 고유의 부정확성 또는 잡음을 가진 실제 값(알 수 없음) 또는 정의 불확실성을 가진 실제 값 또는 간격을 입력으로 사용한다.알고리즘의 출력은 명시적으로 지정된 정확도를 가진 실제 값이다.알고리즘은 O(NlogN)에서 실행되며, 여기서 N은 PE의 수입니다.이 알고리즘을 CRCA(Convergence Algorithm)에 대응하도록 수정할 수 있지만 대역폭 요구사항도 늘어난다.^[6]알고리즘에는 분산 제어, 소프트웨어 신뢰성, 고성능 컴퓨팅 등에 응용 프로그램이 있다.^[7]

알고리즘.

더 브룩스-Iyengar 알고리즘은 분산 센서 네트워크의 모든 처리 요소(PE)에서 실행된다.각 PE는 측정된 간격을 네트워크의 다른 모든 PE와 교환한다."fused" 측정은 발견된 지역의 중간점에 대한 가중 평균이다.^[8]브룩스의 구체적 단계Iyengar 알고리즘은 이 절에 나와 있다.각 PE는 알고리즘을 별도로 수행한다.

입력:

PE k에서 PE i로 보내는 측정은 닫힌 간격${\displaystyle }$[${\displaystyle {}_{}}$ ${\displaystyle {k,}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle h_{}}$ ${\displaystyle {k,}_{}}$ i ${\displaystyle {}_{}}$ ${\displaystyle [l_{k,i,h_{k,i}],$1 ${\displaystyle 1}$ ${\displaystyle \le }$ ${\displaystyle N}$ ${\displaystyle$ N ${\leq$ k\leq k$\leq$ N$}]$이다.

출력:

PE i의 출력에는 점 추정치와 구간 추정치가 포함된다.

1. PE i는 다른 모든 PE로부터 측정을 받는다.
2. 수집된 측정값의 조합을 교차하는 측정값의 수에 따라 상호 배타적인 간격(구간의 무게)으로 나눈다.
3. $무게$가 ${\displaystyle N}$ - ${\displaystyle -}$ ${\displaystyle N-\tau$}보다 작은 간격을 제거하십시오$.$ 여기서 $\tau {\displaystyle }$ ${\displaystyle \tau }$은(는) 결함 있는 PE의 수입니다.
4. L 간격이 남아 있는 $경우{\displaystyle {}_{}}$ ${\displaystyle A_{}}$ i ${\$에 남아 있는 간격의 집합을 표시하십시오$$.우리는 $A{\displaystyle {}_{}{i}_{}}$= {${\displaystyle }$( ${\displaystyle {I\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$, ${\displaystyle {w\mathrm{}}_{}^{}}$ 1${\displaystyle {}_{}^{}}$ )${\displaystyle }$… ,${\displaystyle }$(${\displaystyle }$I ${\displaystyle L_{}^{}}$ ${\displaystyle {}_{}^{}}$, w ${\displaystyle L_{}^{}}$ ${\displaystyle {}_{}^{}}$ )${\displaystyle {}_{}^{}\}}$ ${\displaystyle A_{i}=\{{1}^{i}}}}}}}{{1}^{i})\$dots , ($I_{L}^{{L}^{{L}^{i$}{i$}}{$i}}}}}}}{i}}}}}}}{i}}}}}}}}}}}}}}}}}}}{i}}}}}}}}}}}}$\backslash \}\}\},$ 여기서 interval $I{\displaystyle {}_{}^{}}$ ${\displaystyle l_{}^{}}$ ${\displaystyle {}_{}^{}}$=${\displaystyle }$[ l ${\displaystyle {l{}_{}^{}}_{}}$ ${\displaystyle {{}_{}^{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {{}_{}^{}}_{}}$ l$$ {\$displaystyle I_{l}^{$i}=[$l_{$l]$I_{l}^{i}},h_{}$$I_{l}^{i}}}$과(${\displaystyle {와}_{}^{}}$) ${\displaystyle {}_{}^{}}$ ${\$은(는) 구간 $I{\displaystyle {}_{}^{}}$ {\$displaystyle I_{l}^{$i}}}과(와) 관련된 중량이며$$,$$ $또한{\displaystyle {}_{}}$ h I ${\displaystyle {{}_{}^{}}_{}}$ ${\displaystyle {{}_{}^{}}_{}}$ ${\displaystyle {}_{l_{}^{}}}$ + ${\displaystyle {{}_{}^{}}_{}}$ ${\displaystyle {{\mathrm{i}}_{}^{}}_{}}${\$displaystyle h_{{{{{{{{{}}$라고 가정한다.$I_{l}^{i}}}\leq h_{I_{l+1}^{i$
5. PE i의 점 추정치 $v{\displaystyle {}_{}^{}}$ ${\displaystyle i_{}^{}}$ {\$displaystyle v_{i}$를 v ${\displaystyle i_{}^{}}$v${\displaystyle {}_{}^{}}$= ${\displaystyle \sum \frac{\underset{}{}}{}}$ ${\displaystyle \frac{\underset{}{l}}{}}$ ( ${\displaystyle \frac{\frac{{}_{}}{}}{}}$ l${\displaystyle \frac{\underset{}{}\frac{{l_{}^{}}_{}}{}}{}}$+ ${\displaystyle \frac{\frac{{}_{}}{}}{}}$ ${\displaystyle \frac{\frac{{I_{}^{}}_{}}{}}{}}$ ${\displaystyle \frac{\frac{{{}_{}^{}}_{}}{}}{}}$) ${\displaystyle \frac{\frac{\cdot }{}}{}}$ ${\displaystyle \frac{\frac{{}_{}^{}}{}}{}}$ ${\displaystyle \frac{\underset{}{}{}_{}^{}}{}}$ ${\displaystyle \frac{l_{}^{}}{}}$ ${\$}}}\$frac {(l_{$l_{}){{{{{{}}}}}.$I_{l}^{i}}+h_{{}$$I_{l}^{i}})\cdot w_{l}^{i}}{2}}:{{}}{{l$}^{$i$$\}\}\}\}\}\}\}\}\}\}\{\backslash {\displaystyle }$sum$$ _${\displaystyle {{}_{}^{}}_{}{{l\mathrm{}}_{}^{}}_{}}$$}$${\displaystyle {{}_{}^{}}_{}{{}_{}^{}}_{}{{}_{}^{}}_{}}$$}^{i}}}}}}}}}}}}$ 간격 추정치는 [$L_{\displaystyleale$]이다$.$$I_{1}^{i},h_{{}$$I_{L}^{i}}}}$

예:

PE 5(${\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$ ${\$가 잘못된 값을 다른 PE에 보내고 모두 값을 교환하는 5 PE의 예를 들어보자.

$S{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에 의해 수신된 값은 다음 표에 있다$$.

	${\displaystyle S_{1}.$	${\displaystyle S_{2}}$	${\displaystyle S_{3}}$	${\displaystyle S_{4}}$	${\displaystyle S_{5}}$
${\displaystyle {S\mathrm{}}_{}}$ 1 ${\$값	$[2.7,6.7]}$	${\디스플레이 스타일 [0,3.2]}$	${\displaystyle [1.5,$	${\displaystyle [0.8,2.8]}$	${\디스플레이 스타일 [1.4,4,4.6]}$

이러한 간격의 가중 영역 다이어그램(WRD)을 그리고 나서 알고리즘에 따라 PE 1에 ${\displaystyle {대해\mathrm{}}_{}}$ $A{\displaystyle {}_{}}$ 1 ${\$1}를 결정할 수 있다.

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

최소 4(= $N{\displaystyle }$ -${\displaystyle \tau }$ ${\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 }$[${\displaystyle 1.}$5,${\displaystyle 3}$.2${\displaystyle }$] ${\디스플레이$스타일 $[1$.5$,3$.2$]}$이다.

마찬가지로, 우리는 5개의 PE의 모든 입력과 결과를 얻을 수 있었다.

PE	입력 간격	출력 간격 추정	출력 점 추정
${\displaystyle S_{1}.$	구문 분석 실패(SVG 또는 PNG 폴백(현대 브라우저 및 내게 필요한 옵션 도구에 권장):잘못된 응답("산술 확장자는 Restbase에 연결할 수 없음"): 서버 "/mathoid/local/v1/"): {\displaystyle [2.7, 6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[1.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{-}}}}$	——	——

관련 알고리즘

1982년 비잔틴 문제:^[5]비잔틴 일반 문제는 '두 장군 문제'의 연장선상으로 이항적인 문제로 볼 수 있다.

1983년 대략적인 합의:^[10]이 방법은 세트에서 일부 값을 제거하여 내구성 있는 결함 입력을 허용한다.

1985년 실제 컨센서스:^[7]그 방법은 또한 스칼라를 입력으로 사용한다.

1996 Brooks-Iyengar 알고리즘:^[1]방법은 간격을 기준으로 한다.

2013년 비잔틴 벡터 컨센서스:^[11]메소드는 벡터를 입력으로 사용한다.

2013년 다차원 계약:^[12]이 방법은 거리 측정이 다른 동안 벡터도 입력으로 사용한다.

근사치 컨센서스(scalar 기반), 브룩스-아이옌가 알고리즘(인터벌 기반), 비잔틴 벡터 컨센서스(vector 기반)를 사용하여 간격 입력을 처리할 수 있으며, 논문은 브룩스-빅토르-빅토르(vector 기반)를 입증했다.여기는 아이옌가 알고리즘이 최고야.

적용

Brooks-Iyengar 알고리즘은 분산 센싱의 중요한 이정표로서 많은 이중화 시나리오의 내결함성 솔루션으로 사용될 수 있다.^[13]또한, 어떤 네트워킹 시스템에도 구현하고 내장하는 것이 쉽다.^[14]

1996년 MINIX에서 알고리즘을 사용하여 보다 정확하고 정밀하게 제공함으로써 RT-리눅스의 첫 번째 버전을 개발하게 되었다.

2000년에는 알고리즘이 DARPA Sens의 중심이기도 했다.IT 프로그램의 분산 추적 프로그램.여러 센서의 음향, 지진 및 동작 감지 판독값이 결합되어 분산 추적 시스템에 공급된다.이외에도 BBN 테크놀로지스, BAE 시스템, 펜 스테이트 어플리케이션 연구실(ARL), USC/ISI가 보유한 애플리케이션 분야의 이기종 센서 피드를 결합하는 데 사용되었다.

영국 국방 제조업체인 탈레스 그룹은 이 연구를 글로벌 운영 분석 연구소에서 사용했다.신뢰할 수 없는 센서 네트워크로부터 신뢰할 수 있는 데이터를 추출해야 하는 시스템이 많은 레이시온 프로그램에 적용돼 센서 신뢰성 향상에 대한 투자가 늘어나는 것을 면제한다.또한, 이 알고리즘을 개발하기 위한 연구는 미 해군이 해양 도메인 인식 소프트웨어에서 사용하는 도구로 귀결된다.

교육 분야에서는 브룩스-아이옌가 알고리즘은 위스콘신대, 퍼듀, 조지아공대, 클렘슨대, 메릴랜드대 등과 같은 강의 시간에 널리 사용되어 왔다.

센서 네트워크 영역 외에도 시간 트리거 아키텍처, 사이버-물리적 시스템의 안전성, 데이터 융합, 로봇 융합, 고성능 컴퓨팅, 소프트웨어/하드웨어 신뢰성, 인공지능 시스템의 앙상블 학습 등의 다른 분야도 Brooks-의 혜택을 받을 수 있다.아이옌가 알고리즘.

알고리즘 특성

참고 항목

수상 및 인정

브룩스 아이옌가 알고리즘의 발명가 브룩스 박사와 SS 아이옌가 박사는 그의 선구적 연구와 브룩스 아이옌가 알고리즘의 높은 효과로 권위 있는 25년 테스트 오브 타임 상을 받았다.높은 영향의 연구와 이 연구가 수많은 미국 정부 프로그램과 상용 제품에 어떻게 영향을 끼쳤는지.

• 스티브 야우, IEEE 교수로부터 상을 받는 SS Iyengar 박사

• SS 아이옌가 박사는 그의 제자인 브룩스 박사와 함께

참조