Brooks – Iyengar algoritması - Brooks–Iyengar algorithm

Brooks – Iyengar algoritması veya Brooks-Iyengar hibrit algoritması [1] bir dağıtılmış algoritma hem hassasiyetini hem de doğruluğunu artıran aralık ölçümleri tarafından alındı dağıtılmış sensör ağı Hatalı sensörlerin varlığında bile.[2] Sensör ağı bunu, her düğümde ölçülen değeri ve doğruluk değerini diğer düğümlerle değiştirerek yapar ve toplanan tüm değerlerden tüm ağ için doğruluk aralığını ve ölçülen değeri hesaplar. Bazı sensörlerden bazı veriler hatalı olsa bile sensör ağı arızalanmayacaktır. Algoritma, hataya dayanıklıdır ve dağıtılmıştır. Aynı zamanda bir sensör füzyon yöntemi olarak da kullanılabilir. Bu algoritmanın hassasiyet ve doğruluk sınırı 2016 yılında kanıtlanmıştır.[3]

Arka fon

Brooks-Iyengar hibrit algoritma gürültülü verilerin varlığında dağıtılmış kontrol için birleştirir Bizans anlaşması ile sensör füzyonu. Sensör füzyonu ve Bizans hata toleransı arasındaki boşluğu kapatır.[4] Bu ufuk açıcı algoritma, bu farklı alanları ilk kez birleştirdi. Esasen, Dolev'in[5] Mahaney ve Schneider'in hızlı yakınsama algoritması (FCA) ile yaklaşık anlaşma için algoritma. Algoritma varsayar N işleme elemanları (PE'ler), t bunlardan hatalı ve kötü niyetli davranabilir. Girdi olarak ya doğal yanlışlığı olan gerçek değerleri ya da gürültüyü (bilinmeyen olabilir) ya da önceden tanımlanmış belirsizliğe sahip gerçek bir değeri ya da bir aralığı alır. Algoritmanın çıktısı, açıkça belirtilen doğrulukta gerçek bir değerdir. Algoritma çalışır Ö(NgünlükN) nerede N PE'lerin sayısıdır. Bu algoritmayı Crusader'in Yakınsama Algoritmasına (CCA) karşılık gelecek şekilde değiştirmek mümkündür.[6] ancak, bant genişliği gereksinimi de artacaktır. Algoritmanın uygulamaları var dağıtılmış denetim, yazılım güvenilirliği, Yüksek performanslı bilgi işlem, vb.[7]

Algoritma

Brooks – Iyengar algoritması, dağıtılmış bir sensör ağının her işleme elemanında (PE) yürütülür. Her PE, ölçülen aralıklarını ağdaki diğer tüm PE'lerle değiştirir. "Kaynaşmış" ölçüm, bulunan bölgelerin orta noktalarının ağırlıklı ortalamasıdır.[8] Brooks – Iyengar algoritmasının somut adımları bu bölümde gösterilmektedir. Her PE, algoritmayı ayrı ayrı gerçekleştirir:

Giriş:

PE tarafından gönderilen ölçüm k PE'ye ben kapalı bir aralık ,

Çıktı:

PE çıkışı ben bir nokta tahmini ve bir aralık tahmini içerir

  1. PE ben diğer tüm PE'lerden ölçümler alır.
  2. Toplanan ölçümlerin birleşimini, aralığın ağırlığı olarak bilinen, kesişen ölçümlerin sayısına dayalı olarak, birbirini dışlayan aralıklara bölün.
  3. Daha az ağırlığa sahip aralıkları kaldırın , nerede hatalı PE'lerin sayısıdır
  4. Eğer varsa L bırakılan aralıklar kalan aralıkların kümesini gösterir. Sahibiz nerede aralık ve aralık ile ilişkili ağırlıktır . Ayrıca varsayıyoruz .
  5. Nokta tahminini hesaplayın PE ben gibi ve aralık tahmini

Misal:

Bir 5 PE örneği düşünün, burada PE 5 () diğer PE'lere yanlış değerler gönderiyor ve hepsi değerleri değiş tokuş ediyor.

Brooks-Iyengar Algoritmasına Bir Örnek

Tarafından alınan değerler sonraki Tabloda.

değerler
Brooks-Iyengar Algoritması ile WRD

Bu aralıklardan Ağırlıklı Bölge Diyagramı (WRD) çizeriz, sonra belirleyebiliriz Algoritmaya göre PE 1 için:

en az 4 (= = 5−1) ölçümler kesişir. PE 1 çıkışı şuna eşittir:

ve aralık tahmini

Benzer şekilde, 5 PE'nin tüm girdilerini ve sonuçlarını elde edebiliriz:

PEGiriş AralıklarıÇıktı Aralığı TahminiÇıkış Noktası Tahmini
2.625
2.4
2.625
2.375
————

İlgili algoritmalar

Brooks-Iyengar Algorithm.png Tarihçesi

1982 Bizans Sorunu:[5] Bizans Genel Sorunu [9] bir uzantısı olarak İki Generalin Sorunu ikili bir problem olarak görülebilir.

1983 Yaklaşık Konsensüs:[10] Yöntem, toleranslı hatalı girişlere kadar skalerden oluşan kümeden bazı değerleri kaldırır.

1985 Tam Fikir Birliği:[7] Yöntem ayrıca girdi olarak skaler kullanır.

1996 Brooks-Iyengar Algoritması:[1] Yöntem, aralıklara dayanmaktadır.

2013 Bizans Vektör Konsensüsü:[11] Yöntem, vektörleri girdi olarak kullanır.

2013 Çok Boyutlu Anlaşması:[12] Yöntem ayrıca, mesafe ölçüsü farklıyken vektörleri girdi olarak kullanır.

Aralıklı girdilerle başa çıkmak için Yaklaşık Konsensüs (skaler tabanlı), Brooks-Iyengar Algoritması (aralık tabanlı) ve Bizans Vektör Konsensüsü (vektör tabanlı) kullanabiliriz. [3] Brooks – Iyengar algoritmasının burada en iyisi olduğunu kanıtladı.

Uygulama

Brooks – Iyengar algoritması, ufuk açıcı bir çalışma ve dağıtılmış algılamada önemli bir kilometre taşıdır ve birçok artıklık senaryosu için hataya dayanıklı bir çözüm olarak kullanılabilir.[13] Ayrıca, herhangi bir ağ sistemine uygulanması ve yerleştirilmesi kolaydır.[14]

1996 yılında, algoritma daha fazla doğruluk ve hassasiyet sağlamak için MINIX'te kullanıldı ve bu da RT-Linux'un ilk sürümünün geliştirilmesine yol açtı.

2000 yılında, algoritma aynı zamanda DARPA SensIT programının dağıtılmış izleme programının merkeziydi. Birden çok sensörden gelen akustik, sismik ve hareket algılama okumaları birleştirilir ve dağıtılmış bir izleme sistemine beslenir. Ayrıca BBN Technologies, BAE sistemleri, Penn State Applied Research Lab (ARL) ve USC / ISI tarafından sağlanan uygulamada heterojen sensör beslemelerini birleştirmek için kullanıldı.

Ayrıca İngiliz Savunma İmalatçılarından Thales Group, bu çalışmayı Global Operasyonel Analiz Laboratuvarı'nda kullandı. Raytheon'un birçok sistemin güvenilmez sensör ağından güvenilir veriler çıkarması gereken programlarına uygulanır, bu, sensör güvenilirliğini artırmaya yönelik artan yatırımı muaf tutar. Ayrıca, bu algoritmanın geliştirilmesiyle ilgili araştırma, US Nav'in denizcilik alan farkındalık yazılımında kullandığı araçlarla sonuçlanıyor.

Eğitimde Brooks-Iyengar algoritması, Wisconsin Üniversitesi, Purdue, Georgia Tech, Clemson Üniversitesi, Maryland Üniversitesi, vb. Gibi derslerin öğretiminde yaygın olarak kullanılmaktadır.

Sensör ağı alanına ek olarak, zamanla tetiklenen mimari, siber-fiziksel sistemlerin güvenliği, veri füzyonu, robot yakınsaması, yüksek performanslı bilgi işlem, yazılım / donanım güvenilirliği, yapay zeka sistemlerinde toplu öğrenme gibi diğer alanlar da faydalanabilir. Brooks – Iyengar algoritmasından.

Algoritma özellikleri

  • Hatalı PE'ler tolere edilir < N/3
  • Maksimum hatalı PE <2N/3
  • Karmaşıklık = O (N günlükN)
  • Ağ bant genişliği sırası = O (N)
  • Yakınsama = 2t/N
  • Doğruluk = girişle sınırlı
  • Kesinlik için yinelenir = sık sık
  • Doğruluk üzerinde hassasiyet = hayır
  • Kesinlik yerine doğruluk = hayır

Ayrıca bakınız

Ödüller ve takdirler

Brooks Iyengar Algoritmasının Mucitleri Dr Brooks ve Dr SS Iyengar, Öncü Araştırmaları ve Brooks-Iyengar Algoritmasının yüksek etkisi nedeniyle 25 yıllık prestijli Test of Time Ödülünü aldı. Yüksek etkili araştırma ve bu çalışmanın çok sayıda ABD hükümeti programını ve ticari ürününü nasıl etkilediği.

  • Dr. SS Iyengar, IEEE'den Prof Steve Yau'dan ödül alıyor
Brooks Iyengar Algorithm için Test of Time Ödülü
  • Dr SS Iyengar, öğrencisi Dr Brooks ile
Dr Brooks ve Dr SS Iengar Törende

Referanslar

  1. ^ a b Richard R. Brooks & S. Sithrama Iyengar (Haziran 1996). "Sağlam Dağıtık Hesaplama ve Algılama Algoritması". Bilgisayar. 29 (6): 53–60. doi:10.1109/2.507632. ISSN  0018-9162. Arşivlenen orijinal 2010-04-08 tarihinde. Alındı 2010-03-22.
  2. ^ Mohammad İlyas; Imad Mahgoub (28 Temmuz 2004). Sensör ağları el kitabı: kompakt kablosuz ve kablolu algılama sistemleri (PDF). bit.csc.lsu.edu. CRC Basın. s. 25–4, 33–2 / 864. ISBN  978-0-8493-1968-6. Arşivlenen orijinal (PDF) 27 Haziran 2010. Alındı 22 Mart, 2010.
  3. ^ a b Ao, Buke; Wang, Yongcai; Yu, Lu; Brooks, Richard R .; İyengar, S. S. (2016-05-01). "Dağıtılmış Hata Toleranslı Sensör Füzyon Algoritmalarının Hassas Bağlantısı Üzerine". ACM Comput. Surv. 49 (1): 5:1–5:23. doi:10.1145/2898984. ISSN  0360-0300.
  4. ^ D. Dolev (Ocak 1982). "Bizans Generalleri Yeniden Grevde" (PDF). J. Algoritmalar. 3 (1): 14–30. doi:10.1016/0196-6774(82)90004-9. Alındı 2010-03-22.[kalıcı ölü bağlantı ]
  5. ^ a b L. Lamport; R. Shostak; M. Pease (Temmuz 1982). "Bizans Generalleri Sorunu". Programlama Dilleri ve Sistemlerinde ACM İşlemleri. 4 (3): 382–401. CiteSeerX  10.1.1.64.2312. doi:10.1145/357172.357176.
  6. ^ D. Dolev; et al. (Temmuz 1986). "Arıza Durumunda Yaklaşık Anlaşmaya Ulaşma" (PDF). ACM Dergisi. 33 (3): 499–516. CiteSeerX  10.1.1.13.3049. doi:10.1145/5925.5931. ISSN  0004-5411. Alındı 2010-03-23.
  7. ^ a b S. Mahaney ve F. Schneider (1985). Hatasız Sözleşme: Doğruluk, Kesinlik ve Uygun Bozulma. Proc. Dördüncü ACM Semp. Dağıtık Hesaplamanın İlkeleri. s. 237–249. CiteSeerX  10.1.1.20.6337. doi:10.1145/323596.323618. ISBN  978-0897911689.
  8. ^ Sartaj Sahni ve Xiaochun Xu (7 Eylül 2004). "Kablosuz Sensör Ağları İçin Algoritmalar" (PDF). Florida Üniversitesi, Gainesville. Alındı 2010-03-23.
  9. ^ Lamport, Leslie; Shostak, Robert; Pease, Marshall (1982-07-01). "Bizans Generalleri Sorunu". ACM Trans. Program. Lang. Sist. 4 (3): 382–401. CiteSeerX  10.1.1.64.2312. doi:10.1145/357172.357176. ISSN  0164-0925.
  10. ^ Dolev, Danny; Lynch, Nancy A .; Pinter, Shlomit S .; Stark, Eugene W .; Weihl, William E. (1986-05-01). "Arıza Durumunda Yaklaşık Anlaşmaya Ulaşma". J. ACM. 33 (3): 499–516. CiteSeerX  10.1.1.13.3049. doi:10.1145/5925.5931. ISSN  0004-5411.
  11. ^ Vaidya, Nitin H .; Garg, Vijay K. (2013-01-01). Tam Grafiklerde Bizans Vektör Konsensüsü. Dağıtık Hesaplama İlkeleri 2013 ACM Sempozyumu Bildirileri. PODC '13. New York, NY, ABD: ACM. s. 65–73. arXiv:1302.2543. doi:10.1145/2484239.2484256. ISBN  9781450320658.
  12. ^ Mendes, Hammurabi; Herlihy Maurice (2013-01-01). Bizans Asenkron Sistemlerinde Çok Boyutlu Yaklaşık Anlaşma. Bilgisayar Kuramı Üzerine Kırk beşinci Yıllık ACM Sempozyumu Bildirileri. STOC '13. New York, NY, ABD: ACM. sayfa 391–400. doi:10.1145/2488608.2488657. ISBN  9781450320290.
  13. ^ Kumar, Vijay (2012). "Sensör Ağında Bilgi İşleme için Hesaplamalı ve Sıkıştırılmış Algılama Optimizasyonları". Uluslararası Yeni Nesil Hesaplama Dergisi.
  14. ^ Ao, Buke (Temmuz 2017). "Sağlam Hata Toleranslı Ray Kapısı Durum İzleme Sistemleri: Brooks-Iyengar Algılama Algoritmasının Ulaşım Uygulamalarına Uygulanması". Uluslararası Yeni Nesil Hesaplama Dergisi. 8. S2CID  13592515.