Kablosuz algılayıcı düğüm dağıtımında evrimsel algoritma tabanlı optimizasyon
Evolutionary algorithm-based optimization of wireless sensor node deployment
Yazar: SİBEL BİRTANE AKAR
Danışman: PROF. DR. HAYRİYE KORKMAZ ; PROF. DR. ÖZGÜR KORAY ŞAHİNGÖZ
Marmara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Doktora, 2024
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Son yıllarda Kablosuz Algılayıcı Ağlarının yeteneklerini artırmak amacıyla iletişim protokolleri, enerji verimliliği, optimal dağıtım, veri analitiği ve Nesnelerin İnterneti gibi yeni teknolojilerle entegrasyon üzerine önemli çalışmalar yapılmaktadır. Algılayıcı düğümlerin doğru bir şekilde dağıtılması, sistemlerin etkinliğini, ölçeklenebilirliğini ve kapasitesini önemli ölçüde artırabilmektedir. Bu dağıtım süreci aynı zamanda Kablosuz Algılayıcı Ağlarının maliyetini düşürmekte, performansını artırmakta ve güvenliği sağlamaktadır. Düğüm yerleştirme/dağıtım işleminde, algılayıcı düğümler arası  bağlantısallık korunurken bir taraftan maksimum kapsama alanı sağlanmaya çalışılırken, diğer taraftanda da  düğüm sayısının en aza indirilmesi amaçlanmaktadır. Ancak düğümlerin etkili bir şekilde yerleştirilmesi konusunda bazı zorluklarla karşılaşılmaktadır. Bu zorluklar arasında çevresel engeller, enerji kısıtlamaları, düğüm sayısı ve kapsama alanının optimizasyonu ile dinamik ağ koşulları bulunmaktadır.

Bu çalışma, Kablosuz Algılayıcı Ağlarda algılayıcı düğümlerin etkili yerleştirilmesinin önemini vurgulamakta ve genetik algoritma tabanlı bir çözüm önermektedir. Literatürde genellikle iki boyutlu kare veya dikdörtgen şeklinde düzgün hedef alanlarda düğüm dağıtımı üzerine çalışmalar yapıldığı gözlemlenmektedir. Ancak bu yaklaşım, gerçek uygulama koşullarından oldukça uzak olup, gerçek hayatı yeterince temsil edememektedir.  Bu sebeple, bu çalışmada hem düzgün alanlarda hem de gerçek dünya problemlerine uygun koşulları simüle etmek amacıyla düzgün sınırları olmayan gerçek haritalar üzerinde, homojen ve heterojen özelliğe sahip düğümler rastgele dağıtılmıştır. Daha sonra, bu düğümler Genetik Algoritma ve Titreşimsel Genetik Algoritma kullanılarak kapsama alanı optimize edecek şekilde yeniden konumlandırılmıştır.

Kapsama alanı hesabında deterministik yöntemle ideal duruma göre dağıtılmış (yani hiçbir algılayıcı diğerinin kapsadığı alanı kapsamamaktadır) düğümlerin kapsadığı alan geometrik formüller kullanılarak ve görüntü işleme teknikleri ile hesaplanmıştır. Daha sonra benzer koşullarda  alan hesabı için nokta sayma yöntemi önerilmiş ve bu yöntem kullanılarak yapılan hesaplama sonucu elde edilen hata değerleri, ideal değer ve görüntü işleme yöntemi ile hesaplanan kapsama alanı sonuçları ile karşılaştırılmıştır. Elde edilen sonuçlar, nokta sayma yönteminin görüntü işlemeye kıyasla  daha hızlı ve doğruluğu daha yüksek sonuçlar verdiğini göstermiştir.

Kapsama alanı hesaplamaları için, deterministik yöntemle ideal düzende dağıtılmış (yani hiçbir algılayıcının diğerinin kapsadığı alanı kapsamadığı durumlarda) düğümlerin kapsadığı alan geometrik formüller kullanılarak ve görüntü işleme teknikleri ile hesaplanmıştır. Daha sonra benzer koşullarda  alan hesabı için nokta sayma yöntemi önerilmiş ve bu yöntem kullanılarak yapılan hesaplama sonucu elde edilen hata değerleri, ideal değer ve görüntü işleme yöntemi ile hesaplanan kapsama alanı sonuçları ile karşılaştırılmıştır. Elde edilen sonuçlara göre nokta sayma yöntemi görüntü işlemeye kıyasla  daha hızlı ve doğruluğu daha yüksek sonuçlar vermiştir.


Elde edilen bulgular, Titreşimsel Genetik Algoritma'nın Genetik Algoritma'ya kıyasla dağıtım optimizasyonunda daha etkili sonuçlar verdiğini göstermiştir. Titreşimsel Genetik Algoritma'nın yerel minimumlardan kaçınması ve en optimum değere ulaşma yeteneği sayesinde ilgili problem alanı için daha iyi performans sergilediği tespit edilmiştir. Ayrıca heterojen düğümlerin özellikle gerçek hayat uygulamalarına daha yakın koşullar oluşturan düzgün olmayan sınırlara sahip haritalar üzerinde yapılan dağıtım senaryolarında, homojen düğümlere kıyasla daha iyi uyum ve esneklik sağladığı gözlemlenmiştir. Bu durum heterojen düğümlerin farklı batarya gücü, enerji tüketimi ve algılama kapasiteleri sayesinde, karmaşık ve dinamik ortamlarda daha etkili performans göstermeleri ile ilişkilendirilebileceği görülmektedir. 

Bu çalışma, Kablosuz Algılayıcı Ağlarda düğüm yerleşiminin optimizasyonu için yeni yaklaşımlar sunmakta, daha verimli ve etkili ağlar oluşturulmasına katkıda bulunmaktadır. Gelecekte bu yöntemlerin daha da geliştirilmesi ve farklı uygulama alanlarında test edilmesi, Kablosuz Algılayıcı Ağların performansını ve uygulanabilirliğini artırabileceği değerlendirilmektedir.

Abstract:
In recent years, significant studies have been carried out on integration with new technologies such as communication protocols, energy efficiency, optimal distribution, data analytics and the Internet of Things to increase the capabilities of Wireless Sensor Networks. Proper deployment of sensor nodes can significantly increase the efficiency, scalability and capacity of the systems. This placement process also reduces costs, increases performance and ensures security. The node placement/deployment process aims to minimize the number of nodes while maintaining connectivity between sensor nodes and maximizing coverage. However, there are some challenges in effectively placing nodes. These challenges include environmental obstacles, energy constraints, optimization of the number of nodes and coverage area, and dynamic network conditions. 

This thesis emphasizes the importance of efficient placement of sensor nodes in Wireless Sensor Networks and proposes a genetic algorithm-based solution. The literature generally shows that studies on node deployment in two-dimensional square or rectangular-shaped target areas have been conducted. However, this approach is far from real application conditions and cannot adequately represent real life.  Therefore, in this study, nodes with homogeneous and heterogeneous characteristics are randomly distributed on both regular-shaped and real maps with irregular-shaped target areas to simulate real-life conditions. Then, these nodes are repositioned to optimize the coverage area using Genetic Algorithm and Vibrational Genetic Algorithm. 

In calculating the coverage area, the area covered by the nodes distributed according to the ideal situation (i.e. no sensor covers the area covered by the other) with the deterministic method was calculated using geometric formulas and image processing techniques. Subsequently, for area calculation under similar conditions, a point counting method was proposed, and the error values obtained from the calculations using this method were compared with the ideal values and the coverage area results calculated by the image processing method. The results obtained showed that the point-counting method provided faster and more accurate results compared to image processing.
 
The findings have shown that the Vibrational Genetic Algorithm provides more effective results in node deployment optimization compared to the Genetic Algorithm. It has been determined that the Vibrational Genetic Algorithm performs better for the relevant problem area, thanks to its ability to avoid local minima and reach the most optimum value. In addition, it has been observed that heterogeneous nodes provide better adaptation and flexibility compared to homogeneous nodes, especially in node deployment scenarios on maps with irregularly shaped areas that create conditions closer to real-life applications This situation can be attributed to the fact that heterogeneous nodes perform more effectively in complex and dynamic environments, thanks to their different battery power, energy consumption, and sensing capacities. 

This study presents new approaches for optimizing node deployment in Wireless Sensor Networks and contributes to creating more efficient and effective networks. It is evaluated that in the future, further development of these methods and testing in different application areas can increase the performance and applicability of Wireless Sensor Networks.