Алгоритм Брукса-Айенгара
Распределенный алгоритм для сенсорных сетей

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

Фон

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

Алгоритм

Алгоритм Брукса–Айенгара выполняется в каждом элементе обработки (PE) распределенной сенсорной сети. Каждый PE обменивается своим измеренным интервалом со всеми другими PE в сети. «Объединенное» измерение представляет собой взвешенное среднее значение средних точек найденных областей. [8] Конкретные шаги алгоритма Брукса–Айенгара показаны в этом разделе. Каждый PE выполняет алгоритм отдельно:

Вход:

Измерение, отправленное PE k на PE i, представляет собой закрытый интервал , [ л к , я , час к , я ] {\displaystyle [l_{k,i},h_{k,i}]} 1 ≤ к ≤ Н {\displaystyle 1\leq k\leq N}

Выход:

Выходные данные PE i включают точечную оценку и интервальную оценку.

  1. PE i получает измерения от всех остальных PE.
  2. Разделите объединение собранных измерений на взаимоисключающие интервалы на основе количества пересекающихся измерений, что называется весом интервала.
  3. Удалить интервалы с весом меньше , где - количество неисправных ПЭ Н − τ {\displaystyle N-\tau } τ {\displaystyle \тау}
  4. Если осталось L интервалов, обозначим множество оставшихся интервалов. Имеем , где интервал и — вес, связанный с интервалом . Также предполагаем . А я {\displaystyle A_{i}} А я = { ( я 1 я , ж 1 я ) , … , ( я Л я , ж Л я ) } {\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}}]} w l i {\displaystyle w_{l}^{i}} I l i {\displaystyle I_{l}^{i}} h I l i ≤ h I l + 1 i {\displaystyle h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}}
  5. Рассчитаем точечную оценку PE i как и интервальную оценку v i ′ {\displaystyle v_{i}'} v i ′ = ∑ l ( l I l i + h I l i ) ⋅ w l i 2 ∑ l w l 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}}}} [ l I 1 i , h I L i ] {\displaystyle [l_{I_{1}^{i}},h_{I_{L}^{i}}]}

Пример:

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

Пример алгоритма Брукса-Айенгара
Пример алгоритма Брукса-Айенгара

Полученные значения приведены в следующей таблице. S 1 {\displaystyle S_{1}}

S 1 {\displaystyle S_{1}} S 2 {\displaystyle S_{2}} S 3 {\displaystyle S_{3}} S 4 {\displaystyle S_{4}} S 5 {\displaystyle S_{5}}
S 1 {\displaystyle S_{1}} ценности [ 2.7 , 6.7 ] {\displaystyle [2.7,6.7]} [ 0 , 3.2 ] {\displaystyle [0,3.2]} [ 1.5 , 4.5 ] {\displaystyle [1.5,4.5]} [ 0.8 , 2.8 ] {\displaystyle [0.8,2.8]} [ 1.4 , 4.6 ] {\displaystyle [1.4,4.6]}
WRD по алгоритму Брукса-Айенгара
WRD по алгоритму Брукса-Айенгара

Рисуем диаграмму взвешенных областей (WRD) этих интервалов, затем можем определить PE 1 в соответствии с алгоритмом: A 1 {\displaystyle A_{1}}

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

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

4 ∗ 1.5 + 2.7 2 + 5 ∗ 2.7 + 2.8 2 + 4 ∗ 2.8 + 3.2 2 13 = 2.625 {\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}

и интервальная оценка равна [ 1.5 , 3.2 ] {\displaystyle [1.5,3.2]}

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

ЧПИнтервалы вводаОценка выходного интервалаОценка выходной точки
S 1 {\displaystyle S_{1}} [ 2.7 , 6.7 ] , [ 0 , 3.2 ] , [ 1.5 , 4.5 ] , [ 0.8 , 2.8 ] , [ 1.4 , 4.6 ] {\displaystyle [2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[1.4,4.6]} [ 1.5 , 3.2 ] {\displaystyle [1.5,3.2]} 2.625
S 2 {\displaystyle S_{2}} [ 2.7 , 6.7 ] , [ 0 , 3.2 ] , [ 1.5 , 4.5 ] , [ 0.8 , 2.8 ] , [ − 0.6 , 2.6 ] {\displaystyle [2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.6,2.6]} [ 1.5 , 2.8 ] {\displaystyle [1.5,2.8]} 2.4
S 3 {\displaystyle S_{3}} [ 2.7 , 6.7 ] , [ 0 , 3.2 ] , [ 1.5 , 4.5 ] , [ 0.8 , 2.8 ] , [ 0.9 , 4.1 ] {\displaystyle [2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[0.9,4.1]} [ 1.5 , 3.2 ] {\displaystyle [1.5,3.2]} 2.625
S 4 {\displaystyle S_{4}} [ 2.7 , 6.7 ] , [ 0 , 3.2 ] , [ 1.5 , 4.5 ] , [ 0.8 , 2.8 ] , [ − 0.7 , 2.5 ] {\displaystyle [2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.7,2.5]} [ 1.5 , 2.8 ] {\displaystyle [1.5,2.8]} 2.375
S 5 {\displaystyle S_{5}} [ 2.7 , 6.7 ] , [ 0 , 3.2 ] , [ 1.5 , 4.5 ] , [ 0.8 , 2.8 ] , [ -- , -- ] {\displaystyle [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] Метод также использует векторы в качестве входных данных, хотя мера расстояния отличается.

Для работы с интервальными входными данными мы могли бы использовать приближенный консенсус (на основе скаляров), алгоритм Брукса-Айенгара (на основе интервалов) и византийский векторный консенсус (на основе векторов), и в статье [3] доказано, что алгоритм Брукса-Айенгара здесь является наилучшим.

Приложение

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

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

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

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

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

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

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

  • Допустимое количество неисправных ПЭ < N /3
  • Максимальное количество неисправных ПЭ < 2 N /3
  • Сложность = O( N  log  N )
  • Порядок пропускной способности сети = O( N )
  • Сходимость = 2 т / Н
  • Точность = ограничена входными данными
  • Итерации для точности = часто
  • Точность превыше точности = нет
  • Точность превыше точности = нет

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

Ссылки

  1. ^ ab Richard R. Brooks & S. Sithrama Iyengar (июнь 1996 г.). "Надежные распределенные вычисления и алгоритмы зондирования". Computer . 29 (6): 53– 60. doi :10.1109/2.507632. ISSN  0018-9162. Архивировано из оригинала 2010-04-08 . Получено 2010-03-22 .
  2. ^ Мохаммад Ильяс; Имад Махгуб (28 июля 2004 г.). Справочник по сенсорным сетям: компактные беспроводные и проводные сенсорные системы (PDF) . CRC Press . стр.  25–4 , 33–2 из 864. ISBN 978-0-8493-1968-6. Архивировано из оригинала (PDF) 27 июня 2010 г. . Получено 22 марта 2010 г. .
  3. ^ ab Ao, Buke; Wang, Yongcai; Yu, Lu; Brooks, Richard R.; Iyengar, SS (2016-05-01). "О границе точности распределенных отказоустойчивых алгоритмов слияния датчиков". ACM Comput. Surv . 49 (1): 5:1–5:23. doi :10.1145/2898984. ISSN  0360-0300. S2CID  13760223.
  4. ^ Д. Долев (январь 1982 г.). «Византийские генералы снова наносят удар» (PDF) . J. Algorithms . 3 (1): 14– 30. doi :10.1016/0196-6774(82)90004-9 . Получено 22.03.2010 .
  5. ^ ab L. Lamport; R. Shostak; M. Pease (июль 1982 г.). «Проблема византийских генералов». Труды ACM по языкам и системам программирования . 4 (3): 382– 401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582. 
  6. ^ D. Dolev; et al. (Июль 1986). "Достижение приблизительного соглашения при наличии разломов" (PDF) . Журнал ACM . 33 (3): 499– 516. CiteSeerX 10.1.1.13.3049 . doi :10.1145/5925.5931. ISSN  0004-5411. S2CID  496234 . Получено 23.03.2010 . 
  7. ^ ab S. Mahaney; F. Schneider (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) . Университет Флориды, Гейнсвилл . Получено 23.03.2010 .
  9. ^ Лампорт, Лесли; Шостак, Роберт; Пиз, Маршалл (1982-07-01). «Проблема византийских генералов». ACM Trans. Program. Lang. Syst . 4 (3): 382– 401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. ISSN  0164-0925. S2CID  55899582. 
  10. ^ Долев, Дэнни; ​​Линч, Нэнси А.; Пинтер, Шломит С.; Старк, Юджин В.; Вайль, Уильям Э. (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. ^ Vaidya, Nitin H.; Garg, Vijay K. (2013-01-01). "Византийский векторный консенсус в полных графах". Труды симпозиума ACM 2013 года по принципам распределенных вычислений . PODC '13. Нью-Йорк, штат Нью-Йорк, США: ACM. стр.  65–73 . arXiv : 1302.2543 . doi :10.1145/2484239.2484256. ISBN 9781450320658. S2CID  5914155.
  12. ^ Мендес, Хаммурапи; Херлихи, Морис (2013-01-01). «Многомерное приближенное соглашение в византийских асинхронных системах». Труды сорок пятого ежегодного симпозиума ACM по теории вычислений . STOC '13. Нью-Йорк, штат Нью-Йорк, США: ACM. стр.  391– 400. doi :10.1145/2488608.2488657. ISBN 9781450320290. S2CID  13865698.
  13. ^ Кумар, Виджай (2012). «Вычислительная и сжатая оптимизация измерений для обработки информации в сенсорной сети». Международный журнал вычислений следующего поколения .
  14. ^ Ао, Буке ( июль 2017 г.). «Надежные отказоустойчивые системы мониторинга состояния железнодорожных дверей: применение алгоритма зондирования Брукса-Айенгара к транспортным приложениям». Международный журнал вычислений следующего поколения . 8. S2CID  13592515.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Brooks–Iyengar_algorithm&oldid=1272362286"