Kablosuz Algılayıcı Ağlarda Maksimum Kapsama Alanı Probleminin Genetik Algoritma İle Çözümü

Abstract

Kapsama, ilgi alanlarını takip etmek ve veri toplamak için kablosuz sensör düğümleri kullanarak elde edilir. Sensörler veri toplama, gönderme ve alma yeteneğine sahiptir. En büyük kapsama alanı, mümkün olan en az sayıda sensör kullanarak izlenebilecek en büyük alanı kapsar. Bu hedefe ulaşmak için, birçok algoritma kullanılabilir. Genetik algoritma, en iyi sonuçları elde etmek için kullanılan bir yöntemdir. Bu algoritma, her nesilde en iyi verileri seçerek optimum çözüme ulaşmaya çalışır. Bu aşamalar seçim, çaprazlama ve mutasyon aşamalarıdır. Seçim aşamasında, uygunluk fonksiyonuna göre en iyi veriler seçilir. Bu veriler kromozomlar şeklinde temsil edilir. Çaprazlama aşamasında, bir sonraki nesil için yeni kromozomlar oluşturulur. Mutasyon aşamasında ise benzer kromozomların oluşmasını önlemek için rastgele veriler girilir. Bu aşamalar, en iyi verileri elde etmek için tekrarlanır ve yeni nesiller oluşturulur. Bu işlem optimum çözüme ulaşılıncaya kadar devam eder. Bu tez çalışmasında, farklı özelliklere sahip sensör düğümleri kullanılarak genetik algoritmanın farklı aşamaları incelenmektedir. Her aşama için birden fazla yöntem seçilerek kullanılmaktadır. Seçim aşamasında, Rulet çarkı ve turnuva yöntemleri kullanılmaktadır. Çaprazlama aşamasında, tek noktalı, iki noktalı, düzenli, aritmetik, Min-Max aritmetik ve BLX-α gibi altı yöntem kullanılmaktadır. Mutasyon aşamasında ise rastgele nokta, ters çevirme, takas ve karıştırma yöntemleri tercih edilmektedir. Bu çalışmanın sonucunda, rastgele nokta mutasyon yöntemi uygulanırken BLX-α ve aritmetik yöntemlerinin en iyi sonuçları verdiği gözlemlenmiştir. Seçim aşamasında kullanılan Rulet çarkı ve turnuva yöntemleri sonucu etkilemede benzer bir performans sergilemiştir. Uygulamalar sırasında algoritma benzer sonuçlar vermiş ve kapsama oranı %13 artmıştır. En kötü sonuç, Rulet çarkı seçim yöntemi, Min-Max aritmetik çaprazlama yöntemi ve karıştırma mutasyonu kullanıldığında elde edilmiş ve kapsama alanı değişmemiştir.Coverage is achieved by using wireless sensor nodes to track areas of interest and collect data. The sensors have the ability to collect, transmit, and receive data. The largest coverage area covers the largest possible area that can be monitored with the least number of sensors. To achieve this goal, many algorithms can be used. Genetic algorithm is a method used to obtain the best results. This algorithm tries to reach the optimum solution by selecting the best data in each generation. These stages are selection, crossover, and mutation stages. In the selection stage, the best data is selected based on the fitness function. These data are represented in the form of chromosomes. In the crossover stage, new chromosomes are created for the next generation. In the mutation stage, random data is entered to prevent the formation of similar chromosomes. These stages are repeated to obtain the best data and new generations are created. This process continues until the optimum solution is reached This thesis examines different stages of genetic algorithms using sensor nodes with different features. Multiple methods are selected and used for each stage. For the selection stage, both the roulette wheel and tournament methods are utilized. Six methods are used for the crossover stage, including single-point, two-point, uniform, arithmetic, Min-Max arithmetic, and BLX-α. The mutation stage employs four methods: random point, inversion, swap, and shuffle. The results of this study indicate that the random point mutation method produced the best results with the BLX-α and arithmetic methods. The roulette wheel and tournament methods had similar performance during the selection stage. The algorithm produced similar results during the applications and increased coverage by 13%. The worst result was obtained when using the roulette wheel selection method, Min-Max arithmetic crossover method, and shuffle mutation, with no change in coverage area.