Telsiz duyarga ve aktör ağları için dağıtık k-bağlılık denetleme ve restorasyon algoritmaları
Distributed k-connectivity detection and restoration algorithms for wireless sensor and actor networks
Yazar: VAHID KHALILPOUR AKRAM
Danışman: DOÇ. DR. ORHAN DAĞDEVİREN
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı
Derece: Doktora, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Algoritmalar = Algorithms ; Dağıtık sistemler = Distributed systems

Ö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 tezde iki problemin üzerine odaklanıp, problemlerin çözümü için verimli algoritmalar önerdik.  Birinci problem, TDAA için k değerinin tespitidir. Bu tezde 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.

Abstract:
In wireless sensor networks (WSNs), failures in some nodes may separate the network to disconnected parts. In k-connected networks, failures in any k-1 nodes do not destroy the network connectivity. In this thesis, we focused on two problems and proposed new algorithms for each one. The first problem is detecting the k value in WSNs. In this thesis, we proposed 3 new algorithms for efficient estimating of k value in WSNs and also proposed a deterministic algorithm for exact k detection. In the proposed CDSCUT algorithm, we defined new rules to find the critical nodes from connected dominating set information. In the second proposed DEV algorithm, the minimum vertex cut sets of WSNs are found using an evolutionary search based method. The proposed PACK algorithm estimates the k value of the network with high accuracy by coloring the edges between the nodes. Finally, in the last proposed DECK algorithm, the exact k value of the network always is detected correctly. The second problem that we focused on is movement based k-connectivity restoration. For this problem we defined 3 new movement models and proposed 3 central and 3 distributed algorithms. In the proposed central TAPU1, TAPU2 and PINC algorithms, the k-connectivity restoration for position bounded and position-edge bounded models can be done with optimum movements. In the proposed distributed L-PINC, LINAR and DKR algorithms, the k-connectivity restoration is done using local information at each node. The space, bit, time and computation complexities of all proposed algorithms have been analyzed. All proposed algorithms have been simulated in the TOSSIM simulator. Also the proposed algorithms have been implemented in the testbeds of IRIS nodes and Kobuki robots and compared with the existing algorithms in the literature.