K-bağlılık algoritmaları ve ağlar üzerindeki uygulamaları
K-connectivity algorithms and it's applications on networks
Yazar: MUSTAFA TOSUN
Danışman: PROF. DR. ORHAN DAĞDEVİREN ; DR. ÖĞR. ÜYESİ ELİF HAYTAOĞLU
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı
Derece: Doktora, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Ağ benzetimi = Network simulation ; Ağ performansı = Network performance ; Ağ tasarımı = Network design ; Ağ yapısı = Network architecture

Özet:
k-bağlılık bir ağın, hatalara karşı ne kadar dayanıklı olduğunu gösteren önemli bir özelliktir. Özellikle kablosuz ve tasarsız ağlar için, k-bağlılık çok önemli bir rol oynamaktadır. Bir ağdaki düğümlerin birbirleri ile haberleşebilmeleri için ağın en az 1-bağlı olması gerekmektedir. Ancak bu ağlar, bir düğümün ölümü ile, parçalara ayrılarak bağlılık özelliğini yitirebililmektedir. Bu durumda bağlılığı daha yüksek olan ağlara ihtiyaç duyulmaktadır. Örneğin 2-bağlı ağlarda, ağın bağlılığının kopması için en az iki düğümün ölmesi gerekmektedir. k değeri ne kadar artarsa, ağın hatalara karşı direnci de o kadar artmaktadır.
İnsansız hava araçları (İHA) kullanılarak oluşturulan kablosuz ve tasarsız ağlar, İHA teknolojilerinin gelişmesi ile, son dönemlerde, askeri, arama kurtarma, nakliye, inşa ve tarım gibi sektörlerde oldukça yaygın olarak kullanılmaya başlanmıştır. Özellikle askeri ve arama kurtarma operasyonlarında, İHA ağlarının bağlılığı çok kritik öneme sahiptir. Bu uygulamalarda, ağın bağlılığının kopması, ağın amacını yerine getirememesine sebep olmaktadır ve geri dönüşü olmayan zararlara yol açabilmektedir. Bu gibi durumların yaşanmaması için ağın k-bağlılığının, ağın ömrü boyunca korunması gerekmektedir. Bu tez kapsamında, ağın k-bağlılığının zarar gördüğü durumlarda, k-bağlılığı onaracak dağıtık bir algoritma geliştirilmiştir. Algoritmanın geliştirilmesi için, bir dağıtık algoritma benzetim ortamına ihtiyaç duyulmuş ve içerisinde hareket, mesajlaşma ve zamanlayıcı mekanizmaları bulunan basit bir benzetim ortamı da geliştirilmiştir.
Tarım, alan gözetleme, ve kritik olmayan hedef takibi gibi uygulamalarda, ağın k-bağlılığının çok arttırılması istenen bir durum değildir. Bunun sebebi, k-bağlılık arttıkça, ağdaki düğümler tarafından hizmet verilen ya da izlenen (kapsanan) alanın küçülmesidir. Bu gibi uygulamalarda, düğüm ölümü çok sık gerçekleşmediğinden, daha çok alan kapsayan 1-bağlı ağlar tercih edilmektedir. Ancak ağı 1-bağlı hale getirmek, tek başına, kapsanan alanı büyültmeye yetmemektedir. Bu tez kapsamında, kısıtlı düğüm sayısı ile maksimum alan kapsayabilen ve rastgele üretilebilen bir topoloji formasyonu geliştirilmiştir.

Abstract:
k-connectivity is an important metric that indicates how durable a network is against failures. Particularly for wireless and ad hoc networks, k-connectivity plays a crucial role. For nodes in a network to communicate with each other, the network must be at least 1-connected. However, these networks can lose their connectivity immediately by splitting into pieces after a death of a node. In this case, networks with higher connectivity are needed. For instance, in 2-connected networks, at least two nodes must die for the network's connectivity to be lost. As the k increases, the network's resistance to failures also increases.
Wireless and ad hoc networks created using unmanned aerial vehicles (UAVs) have become increasingly common in recent years in sectors such as military, search and rescue, transportation, construction, and agriculture, with the development of UAV technologies. Particularly in military and search and rescue operations, the connectivity of UAV networks is of critical importance. The loss of network connectivity in such applications can prevent the network from achieving its intended task and cause irreversible hazards. To prevent such situations, the k-connectivity of the network must be maintained throughout its lifetime. In this dissertation, a distributed algorithm that repairs k-connectivity when it is compromised is developed. To develop the algorithm, a distributed algorithm simulation environment was required, and a simple simulation environment that consists of movement, messaging, and timer mechanisms was developed.
In applications such as agriculture, area surveillance, and non-critical target tracking, increasing the k-connectivity of the network is not a desirable situation. This is because as k-connectivity increases, the area serviced or monitored (covered) by the nodes in the network decreases. In such applications, since node failure is not a frequent occurrence, 1-connected networks that cover more area are preferred. However, making the network 1-connected alone is not enough to expand the covered area. In this dissertation, a random topology formation that can cover the maximum area with a limited number of nodes has been developed.