Брукс - Алгоритм Брукса

Алгоритм Брукса -Ийенгара или алгоритм фусекпа или гибридный алгоритм Брукса - Иенгара ^{[ 1 ]} является распределенным алгоритмом , который повышает как точность, так и точность интервальных измерений, сделанных распределенной датчикой сетью , даже в присутствии неисправных датчиков. ^{[ 2 ]} Сенсорная сеть делает это, обменивая измеренное значение и значение точности на каждом узле с любым другим узлом, и вычисляет диапазон точности и измеренное значение для всей сети со всех собранных значений. Даже если некоторые данные от некоторых датчиков неверны, сенсорная сеть не будет неисправна. Алгоритм является неисправным и распределенным. Это также может быть использовано в качестве метода слияния датчика. Точность и точность, связанная с этим алгоритмом, была доказана в 2016 году. ^{[ 3 ]}

Фон

Брукса - Иенгара Гибридный алгоритм для распределенного контроля в присутствии шумных данных объединяет византийское согласие с слиянием датчика . Это соединяет зазор между слиянием датчика и византийской толерантностью разлома. ^{[ 4 ]} Этот основополагающий алгоритм объединил эти разрозненные поля впервые. По сути, он сочетает в себе Долев ^{[ 5 ]} Алгоритм приблизительного согласия с Алгоритмом быстрого конвергенции Махани и Шнайдера (FCA). Алгоритм предполагает элементы обработки ( PE ), T из которых неисправны и могут вести себя злонамеренно. Он принимает в качестве входных значений либо реальных значений с неотъемлемой неточности, либо шумом (что может быть неизвестно), либо реальным значением с определенной неопределенностью Apriori или интервалом. Вывод алгоритма является реальным значением с явной точности. Алгоритм работает в O ( n log n ) , где n - количество PES. Можно изменить этот алгоритм, чтобы соответствовать алгоритму конвергенции крестоносца (CCA), ^{[ 6 ]} Тем не менее, требование пропускной способности также увеличится. Алгоритм имеет приложения для распределенного управления , надежности программного обеспечения , высокопроизводительных вычислений и т. Д. ^{[ 7 ]}

Алгоритм

Алгоритм Brooks -Iyengar выполняется в каждом элементе обработки (PE) распределенной сенсорной сети. Каждый PE обменивает свой измеренный интервал со всеми другими PE в сети. Измерение «плавленого» - это средневзвешенное средние точки обнаруженных областей. ^{[ 8 ]} В этом разделе показаны бетонные ступени алгоритма Брукса - Иенгара. Каждый PE выполняет алгоритм отдельно:

Вход:

Измерение, отправленное PE K To PE I, является закрытым интервалом $[l_{k,i},h_{k,i}]$ , $1\leq k\leq N$

Выход:

Выход PE I включает в себя точечную оценку и интервальную оценку

PE I получает измерения от всех остальных PES.
Разделите объединение собранных измерений на взаимно исключительные интервалы на основе количества пересекающихся измерений, которые известны как вес интервала.
Удалить интервалы с весом меньше, чем $N-\tau$ , где $\tau$ это количество неисправно
Если остались интервалы L , пусть $A_{i}$ Обозначите набор оставшихся интервалов. У нас есть $A_{i}=\{(I_{1}^{i},w_{1}^{i}),\dots ,(I_{L}^{i},w_{L}^{i})\}$ , где интервал $I_{l}^{i}=[l_{I_{l}^{i}},h_{I_{l}^{i}}]$ и $w_{l}^{i}$ вес, связанный с интервалом $I_{l}^{i}$ Полем Мы также предполагаем $h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}$ .
Рассчитайте оценку точки $v_{i}'$ из Pe i как $v_{i}'={\frac {\sum _{l}{\frac {(l_{I_{l}^{i}}+h_{I_{l}^{i}})\cdot w_{l}^{i}}{2}}}{\sum _{l}w_{l}^{i}}}$ И оценка интервала $[l_{I_{1}^{i}},h_{I_{L}^{i}}]$

Пример:

Рассмотрим пример 5 PE, в котором PE 5 ( $S_{5}$ ) отправляет неправильные значения другим PES, и все они обмениваются значениями.

Значения, полученные $S_{1}$ в следующей таблице.

	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$
$S_{1}$ ценности	$[2.7,6.7]$	$[0,3.2]$	$[1.5,4.5]$	$[0.8,2.8]$	$[1.4,4.6]$

WRD от Brooks-Iyengar Algorithm — WRD by Brooks-Iyengar Algorithm

Мы проводим взвешенную область диаграммы (WRD) этих интервалов, затем мы можем определить $A_{1}$ Для PE 1 в соответствии с алгоритмом:

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

который состоит из интервалов, где не менее 4 (= $N-\tau$ = 5–1) измерения пересекаются. Вывод PE 1 равен

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

И оценка интервала $[1.5,3.2]$

Аналогично, мы могли бы получить все входные данные и результаты 5 PE:

НА	Входные интервалы	Оценка выходного интервала	Оценка выходной точки
$S_{1}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[1.4,4.6]$	$[1.5,3.2]$	2.625
$S_{2}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.6,2.6]$	$[1.5,2.8]$	2.4
$S_{3}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[0.9,4.1]$	$[1.5,3.2]$	2.625
$S_{4}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.7,2.5]$	$[1.5,2.8]$	2.375
$S_{5}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[{\text{--}},{\text{--}}]$	——	——

Связанные алгоритмы

1982 Византийская проблема: ^{[ 5 ]} Византийская общая проблема ^{[ 9 ]} В качестве расширения проблемы двух генералов можно рассматривать как бинарную проблему.

1983 Приблизительное согласие: ^{[ 10 ]} Метод удаляет некоторые значения из набора состоит из скаляров до толерантных неисправных входов.

1985 г. в эксплуатации: ^{[ 7 ]} Метод также использует скаляр в качестве входа.

1996 Алгоритм Брукса-Ийенгара: ^{[ 1 ]} Метод основан на интервалах.

2013 Византийский векторный консенсус: ^{[ 11 ]} Метод использует векторы в качестве входа.

2013 многомерное соглашение: ^{[ 12 ]} Метод также использует векторы в качестве входа, в то время как мера расстояния отличается.

Мы могли бы использовать приблизительный консенсус (на основе скаляр), алгоритм Brooks-Iyengar (на основе интервала) и византийский векторный консенсус (на основе вектора) для работы с интервалы и бумагой ^{[ 3 ]} Доказал, что алгоритм Брукса - Иенгара здесь лучший.

Приложение

Алгоритм Brooks - Iyengar - это основополагающая работа и основная веха в распределенном зондировании, и он может использоваться в качестве устойчивого к разлому решения для многих сценариев избыточности. ^{[ 13 ]} Кроме того, его легко внедрить и внедрять в любые сетевые системы. ^{[ 14 ]}

В 1996 году алгоритм использовался в Minix для обеспечения большей точности и точности, что приводит к разработке первой версии RT-Linux.

В 2000 году алгоритм также был центральным в программе распределенного отслеживания программы DARPA Sensit. Акустические, сейсмические показания и показания обнаружения движения от нескольких датчиков объединяются и подаются в распределенную систему отслеживания. Кроме того, он использовался для комбинирования гетерогенных подачи датчиков в приложении, выставленном BBN Technologies, BAE Systems, Penn State Applied Research Lab (ARL) и USC/ISI.

Thales Group, производитель обороны Великобритании, использовал эту работу в своей глобальной лаборатории оперативного анализа. Он применяется к программам Raytheon, когда многие системы должны извлечь надежные данные из ненадежной сенсорной сети, что освобождает от растущих инвестиций в повышение надежности датчиков. Кроме того, исследование в разработке этого алгоритма приводит к инструментам, используемым ВМС США в его программном обеспечении осведомленности о морской области.

В образовании алгоритм Брукса - Иенгара широко использовался в таких занятиях, как Университет Висконсина, Пердью, Джорджия Тех, Университет Клемсона, Университет Мэриленда и т. Д.

В дополнение к области сенсорной сети, другие поля, такие как архитектура, вызванная временем, безопасность киберфизических систем, слияние данных, конвергенция роботов, высокопроизводительные вычислительные вычисления, надежность программного обеспечения/оборудования, обучение ансамбля в системах искусственного интеллекта также может выиграть. из алгоритма Брукса - Ийенгара.

Характеристики алгоритма

Неисправные pes переносят < n /3
Максимальный неисправный PE <2 н /3
Сложность = O ( n log n )
Порядок пропускной способности сети = O ( n )
Конвергенция = 2 т / н.
Точность = ограничена подход
Итераты для точности = часто
Точность над точности = нет
Точность над точностью = нет

Смотрите также

Награды и признание

Изобретатели алгоритма Брукса Айенгара доктора Брукс и доктора С.С. Айенгара получили престижную 25-летнюю награду «Время времени» за его новаторское исследование и высокое влияние алгоритма Брукса-Ийенгара. Исследование с высоким воздействием и то, как эта работа повлияла на многочисленные правительственные программы США и коммерческие продукты.

Доктор С.С. Айенгар получает награду от профессора Стива Яу, IEEE

Доктор С.С. Айенгар со своим учеником доктором Бруксом

Ссылки

^ Подпрыгнуть до: ^а ^{беременный} Ричард Р. Брукс и С. Стюрама Айенгар (июнь 1996 г.). «Надежный распределенный алгоритм вычислений и зондирования» . Компьютер 29 (6): 53–60. doi : 10.1109/2.507632 . ISSN 0018-9162 . Архивировано из оригинала 2010-04-08 . Получено 2010-03-22 .
^ Мохаммад Ильяс; Имад Махгуб (28 июля 2004 г.). Справочник по сенсорным сетям: Compact Wireless и Swield Sensing Systems (PDF) . CRC Press . стр. 25–4, 33–2 из 864. ISBN 978-0-8493-1968-6 Полем Архивировано из оригинала (PDF) 27 июня 2010 года . Получено 22 марта 2010 года .
^ Подпрыгнуть до: ^а ^{беременный} АО, Бук; Ван, Юнкай; Ю, Лу; Брукс, Ричард Р.; Iyengar, SS (2016-05-01). «На точной границе алгоритмов слияния датчика распределенного устойчивого датчика». ACM Comput. Выживший 49 (1): 5: 1–5: 23. doi : 10.1145/2898984 . ISSN 0360-0300 . S2CID 13760223 .
^ Д. Долев (январь 1982). «Византийские генералы поражают снова» (PDF) . J. Алгоритмы . 3 (1): 14–30. doi : 10.1016/0196-6774 (82) 90004-9 . Получено 2010-03-22 .
^ Подпрыгнуть до: ^а ^{беременный} Л. Лампорт; Р. Шостак; М. Пиз (июль 1982). «Проблема византийских генералов». Транзакции ACM на языках и системах программирования . 4 (3): 382–401. Citeseerx 10.1.1.64.2312 . doi : 10.1145/357172.357176 . S2CID 55899582 .
^ Д. Долев; и др. (Июль 1986). «Достижение приблизительного соглашения в присутствии разломов» (PDF) . Журнал ACM . 33 (3): 499–516. Citeseerx 10.1.1.13.3049 . doi : 10.1145/5925.5931 . ISSN 0004-5411 . S2CID 496234 . Получено 2010-03-23 .
^ Подпрыгнуть до: ^а ^{беременный} С. Махани; Ф. Шнайдер (1985). «Неточное соглашение: точность, точность и изящная деградация». Материалы четвертого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '85 . С. 237–249. Citeseerx 10.1.1.20.6337 . doi : 10.1145/323596.323618 . ISBN 978-0897911689 Полем S2CID 10858879 .
^ Сартадж Сахни и Сяохун Сюй (7 сентября 2004 г.). «Алгоритмы для беспроводных сенсорных сетей» (PDF) . Университет Флориды, Гейнсвилл . Получено 2010-03-23 .
^ Лампорт, Лесли; Шостак, Роберт; Пиз, Маршалл (1982-07-01). «Проблема византийских генералов». ACM Trans. Программа Ланг Система 4 (3): 382–401. Citeseerx 10.1.1.64.2312 . doi : 10.1145/357172.357176 . ISSN 0164-0925 . S2CID 55899582 .
^ Долев, Дэнни; Линч, Нэнси А.; Pinter, Shlomit S.; Старк, Юджин У.; Weihl, William E. (1986-05-01). «Достижение приблизительного соглашения в присутствии разломов». J. Acm . 33 (3): 499–516. Citeseerx 10.1.1.13.3049 . doi : 10.1145/5925.5931 . ISSN 0004-5411 . S2CID 496234 .
^ Вайдья, Нитин Х.; Гарг, Виджай К. (2013-01-01). «Византийский векторный консенсус в полных графиках». Материалы симпозиума ACM 2013 года о принципах распределенных вычислений . PODC '13. Нью -Йорк, Нью -Йорк, США: ACM. С. 65–73. Arxiv : 1302.2543 . doi : 10.1145/2484239.2484256 . ISBN 9781450320658 Полем S2CID 5914155 .
^ Мендес, Хаммураби; Herlihy, Maurice (2013-01-01). «Многомерное приблизительное соглашение в византийских асинхронных системах». Материалы сорока пятого годового симпозиума ACM по теории вычислений . STOC '13. Нью -Йорк, Нью -Йорк, США: ACM. С. 391–400. doi : 10.1145/2488608.2488657 . ISBN 9781450320290 Полем S2CID 13865698 .
^ Кумар, Виджай (2012). «Вычислительные и сжатые оптимизации зондирования для обработки информации в сенсорной сети» . Международный журнал вычислений следующего поколения .
^ АО, Бук (июль 2017 г.). «Сильные системы мониторинга штата железнодорожных дверей, применяя алгоритм зондирования Brooks-Iyengar к транспортным приложениям». Международный журнал вычислений следующего поколения . 8 S2CID 13592515 .

[:0-1] Подпрыгнуть до: ^а ^{беременный} Ричард Р. Брукс и С. Стюрама Айенгар (июнь 1996 г.). «Надежный распределенный алгоритм вычислений и зондирования» . Компьютер 29 (6): 53–60. doi : 10.1109/2.507632 . ISSN 0018-9162 . Архивировано из оригинала 2010-04-08 . Получено 2010-03-22 .

[2] Мохаммад Ильяс; Имад Махгуб (28 июля 2004 г.). Справочник по сенсорным сетям: Compact Wireless и Swield Sensing Systems (PDF) . CRC Press . стр. 25–4, 33–2 из 864. ISBN 978-0-8493-1968-6 Полем Архивировано из оригинала (PDF) 27 июня 2010 года . Получено 22 марта 2010 года .

[:1-3] Подпрыгнуть до: ^а ^{беременный} АО, Бук; Ван, Юнкай; Ю, Лу; Брукс, Ричард Р.; Iyengar, SS (2016-05-01). «На точной границе алгоритмов слияния датчика распределенного устойчивого датчика». ACM Comput. Выживший 49 (1): 5: 1–5: 23. doi : 10.1145/2898984 . ISSN 0360-0300 . S2CID 13760223 .

[4] Д. Долев (январь 1982). «Византийские генералы поражают снова» (PDF) . J. Алгоритмы . 3 (1): 14–30. doi : 10.1016/0196-6774 (82) 90004-9 . Получено 2010-03-22 .

[:2-5] Подпрыгнуть до: ^а ^{беременный} Л. Лампорт; Р. Шостак; М. Пиз (июль 1982). «Проблема византийских генералов». Транзакции ACM на языках и системах программирования . 4 (3): 382–401. Citeseerx 10.1.1.64.2312 . doi : 10.1145/357172.357176 . S2CID 55899582 .

[6] Д. Долев; и др. (Июль 1986). «Достижение приблизительного соглашения в присутствии разломов» (PDF) . Журнал ACM . 33 (3): 499–516. Citeseerx 10.1.1.13.3049 . doi : 10.1145/5925.5931 . ISSN 0004-5411 . S2CID 496234 . Получено 2010-03-23 .

[:3-7] Подпрыгнуть до: ^а ^{беременный} С. Махани; Ф. Шнайдер (1985). «Неточное соглашение: точность, точность и изящная деградация». Материалы четвертого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '85 . С. 237–249. Citeseerx 10.1.1.20.6337 . doi : 10.1145/323596.323618 . ISBN 978-0897911689 Полем S2CID 10858879 .

[8] Сартадж Сахни и Сяохун Сюй (7 сентября 2004 г.). «Алгоритмы для беспроводных сенсорных сетей» (PDF) . Университет Флориды, Гейнсвилл . Получено 2010-03-23 .

[9] Лампорт, Лесли; Шостак, Роберт; Пиз, Маршалл (1982-07-01). «Проблема византийских генералов». ACM Trans. Программа Ланг Система 4 (3): 382–401. Citeseerx 10.1.1.64.2312 . doi : 10.1145/357172.357176 . ISSN 0164-0925 . S2CID 55899582 .

[10] Долев, Дэнни; Линч, Нэнси А.; Pinter, Shlomit S.; Старк, Юджин У.; Weihl, William E. (1986-05-01). «Достижение приблизительного соглашения в присутствии разломов». J. Acm . 33 (3): 499–516. Citeseerx 10.1.1.13.3049 . doi : 10.1145/5925.5931 . ISSN 0004-5411 . S2CID 496234 .

[11] Вайдья, Нитин Х.; Гарг, Виджай К. (2013-01-01). «Византийский векторный консенсус в полных графиках». Материалы симпозиума ACM 2013 года о принципах распределенных вычислений . PODC '13. Нью -Йорк, Нью -Йорк, США: ACM. С. 65–73. Arxiv : 1302.2543 . doi : 10.1145/2484239.2484256 . ISBN 9781450320658 Полем S2CID 5914155 .

[12] Мендес, Хаммураби; Herlihy, Maurice (2013-01-01). «Многомерное приблизительное соглашение в византийских асинхронных системах». Материалы сорока пятого годового симпозиума ACM по теории вычислений . STOC '13. Нью -Йорк, Нью -Йорк, США: ACM. С. 391–400. doi : 10.1145/2488608.2488657 . ISBN 9781450320290 Полем S2CID 13865698 .

[13] Кумар, Виджай (2012). «Вычислительные и сжатые оптимизации зондирования для обработки информации в сенсорной сети» . Международный журнал вычислений следующего поколения .

[14] АО, Бук (июль 2017 г.). «Сильные системы мониторинга штата железнодорожных дверей, применяя алгоритм зондирования Brooks-Iyengar к транспортным приложениям». Международный журнал вычислений следующего поколения . 8 S2CID 13592515 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]