K-bağlılık problemine yeni yaklaşımlar ve drone ağları üzerindeki uygulamaları
New approaches to k-connectivity problem and its applications on drone networks
Yazar: MUSTAFA AŞÇI
Danışman: DOÇ. DR. ORHAN DAĞDEVİREN ; PROF. DR. BÜLENT TAVLI
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı / Bilgi Teknolojileri Bilim Dalı
Derece: Doktora, 2024
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Mühendislik Bilimleri = Engineering Sciences
Dizin: Ağ tasarımı = Network design ; Ağ yapısı = Network architecture ; Bağlantısallık = Connectivity ; Bilgisayar ağları = Computer networks ; İnsansız hava aracı = Unmanned aerial vehicle

Özet:
Bağlılık, bir ağın en önemli özelliklerinden biridir. Bağlılık sağlanamadığında ağ içerisindeki iletişim sona ermektedir. Ağ içerisindeki iletişimin devam edebilmesi ağın en az 1-bağlı olduğunu göstermektedir. İletişimin gürbüzlüğünün sağlanabilmesi için ağın k-bağlılık değerinin bilinebilirliği son derece önemlidir. k-bağlı ağ, k-1 düğümün çalışmamasına rağmen bağlılık durumunu devam ettirir. 3-bağlı bir ağda iletişimin sona ermesi için en az 3 düğümün bozulması veya ölmesi gerekmektedir. k-bağlılık değerinin artması ağ iletişimini daha güvenli bir hale getirmektedir. k-bağlılık sadece ağın hata tahammülünü arttırmakla kalmaz, aynı zamanda paketlerin alternatif rota performansını da geliştirir. k-bağlılık değerinin hesaplanması ile ağı oluşturan yapıların (düğüm, sunucu, otonom cihazlar, hava aracı, vb.) çökmesi veya hata vermesi halinde alınabilecek önlemler belirlenebilir. Bu durumlarla karşılaşıldığında ağ yeniden bağlı hale getirilebilir ya da çökmeler sonucunda bağlılık sonlanmadan ağ üzerindeki trafik yeniden yönlendirilebilir. 
İnsansız Hava Araçları (İHA) ve drone üzerindeki teknolojik gelişmeler son yıllarda hız kazanmıştır.  Günümüzde drone'lar telekomünikasyon, tarım, inşaat, nakliye, sağlık, askeri vb. alanlarda yaygın olarak kullanılmaktadır. Drone teknolojileri kullanılarak geniş tarım arazileri sulanmakta, belirli bölgelere ürün teslimatları yapılmakta, acil durumlarda ambulans ve yangın söndürme amacıyla bölgeye yardım ulaştırılmakta, telsiz ve tasarsız ağlar oluşturulmakta, askeri alanlar taranmakta ve arama kurtarma operasyonları yapılmaktadır. Askeri arazilerde yapılan keşif, analiz, arama kurtarma gibi operasyonlarda ağın iletişimin devamlılığı ve elde edilen bilgilerin merkeze aktarımı son derece önem arz etmektedir. 
Hareket halinde k-bağlı ağın restorasyon problemi telsiz duyarga ağlarında P karmaşıklık kümesindeki olmasına rağmen drone'lar tarafından oluşturulan ağlarda NP-Zor'dur. Ağın amacına uygun hizmet etmesi ve veri akışının kesintisiz bir şekilde sağlanabilmesi için k-bağlılık özelliğinin sağlanması gerekmektedir. Bu kapsamda drone'lar tarafından oluşturulan bir ağın k-bağlı hale getirilmesi ve herhangi bir koşulda bağlılığın zedelendiği durumlarda ağın tekrardan k-bağlı hale getirilmesi bu tez çalışmasının konusunu oluşturmaktadır. 
Bu tez kapsamında, drone'lar tarafından en az hareket ile k-bağlı ağın oluşturulması ve restorasyonu için matematiksel model ile problem tanımı yapılmıştır. Problemin çözümü için tamsayılı programlama, sezgisel algoritmalar, pekiştirmeli öğrenme metodları ve metasezgisel algoritma geliştirilmiştir. Geliştirilen çözümlerin ızgaralar üzerinde simülasyonu yapılarak elde edilen sonuçlar farklı ızgara boyutları, İHA/drone sayıları, iletişim menzili ve k-bağlılık değerlerine göre karşılaştırılarak analiz edilmiştir.

Abstract:
Connectivity is one of the most important characteristics of a network. When connectivity is not ensured, communication within the network ends. The fact that communication within the network can continue indicates that the network is at least 1-connected. Knowing the k-connectivity value of the network is extremely important to ensure robust communication. The k-connected network can tolerate k-1 nodes being down and the connectivity remains. In a 3-connected network, at least 3 nodes must fail or die for termination of communication. Increasing the k-connectivity value makes network communication more secure. k-connectivity not only increases the fault tolerance of the network, but also improves the alternative route performance of packets. By calculating the k-connectivity value, precautions that can be taken in case the structures that create the network (node, server, autonomous devices, aerial vehicle, etc.) crash or fail can be determined. When these situations occur, the network can be reconnected or traffic on the network can be redirected before the connection is terminated as a result of crashes.
Technological developments on Unmanned Aerial Vehicles (UAV) and drones have accelerated in recent years. Today, drones are widely used in fields such as telecommunications, agriculture, construction, transportation, healthcare and military. Using drone technologies, large agricultural lands are irrigated, product deliveries are made to certain regions, ambulance and fire extinguishing aid is delivered to the region in case of emergency, wireless and ad-hoc networks are created, military areas are scanned and also search rescue operations are carried out. In operations such as reconnaissance, analysis and search rescue carried out on military lands, the continuity of the network's communication and the transfer of the obtained information to the center are extremely important.
The restoration problem of a k-connected network on the move is NP-hard in networks created by drones, even though the wireless sensor network is in the complexity set P. In order for the network to serve its purpose and to ensure uninterrupted data flow, k-connectivity must be ensured. In this context, establishing a network created by drones k-connected and becoming reconnected as a k-connected in cases where the connectivity is damaged under any circumstances is the subject of this thesis.
Within the scope of this thesis, the problem has been defined with a mathematical model for the establishment and restoration of the k-connected network with minimal movement by drone. Integer programming, heuristic algorithms, reinforcement learning methods and metaheuristic algorithms have been developed to solve the problem. The developed solutions were simulated on grids and the results were compared and analyzed according to different grid sizes, UAV/drone numbers, radio distance and k-connectivity values.