TELSİZ DUYARGA VE AKTÖR AĞLARI İÇİN DAĞITIK K-BAĞLILIK DENETLEME VE RESTORASYON ALGORİTMALARI
Proje no. 536 · Durum: Kapanmış · 2015
Özet
Telsiz Duyarga ve Aktör Ağlarında (TDAA’nda) bazı düğümlerin bozulması ağın bağlantısını koparır ve diğer aktif düğümlerin iletişimlerini engeller. k-bağlı ağlarda herhangi k-1 düğümün bozulması ağın bağlantısını zedelemez. Genel olarak, bu projede iki problemin üzerine odaklanıp, problemlerin çözümü için verimli algoritmalar önerdik. Birinci problem, TDAA için k değerinin tespitidir. Bu projede bağlılık durumunu daha iyi tahmin eden üç farklı algoritma ve k’yı kesin bulan bir algoritma önerdik. Önerdiğimiz CDSCUT algoritmasında bağlı hakim kümeler için yeni kurallar tanımlayarak ağın kesim düğümleri daha etkin bir şekilde tespit edildi. DEV isimli algoritmamızda bir evrimsel arama metodu kullanılarak en küçük kesim kümeler bulunundu. Önerdiğimiz PACK isimli algoritma düğümlerin arasındaki patikaları boyayarak k’yı yüksek oranda doğru buldu. Önerdiğimiz son dağıtık algoritma olan DECK algoritmasında k değeri her zaman doğru bulundu. Üzerinde çalıştığımız ikinci problem düğümleri hareket ettirilerek ağın k-bağlılığının restorasyonunun yapılmasıdır. Bu probleme yeni hareket modelleri tanımlayarak üç hareket tabanlı merkezi algoritma ve üç dağıtık algoritma önerdik. Önerdiğimiz merkezi TAPU1, TAPU2 ve PINC algoritmalarında pozisyon kısıtlı ve pozisyon-kenar kısıtlı hareket modellerinde k-bağlı restorasyon işlemi en iyi şekilde yapılabilir. Dağıtık L-PINC, LINAR ve DKR algoritmalarında restorasyon işlemi her düğümün lokal bilgilerinin üzerinden yapılmaktadır. Önerilen algoritmaların uzay, zaman, bit ve hesaplama karmaşıklık analizleri yapılmıştır. Önerilen algoritmalar TOSSIM benzetim ortamı üzerinde uygulanmıştır. Ayrıca IRIS düğümleri ve Kobuki robotlarından oluşan test yatağı üzerinde uygulanmıştır ve literatürdeki diğer algoritmalarla karşılaştırmıştır.