Kablosuz Algılayıcı Ağlarda En Kısa Yol Algoritmalarının İncelenmesi

Abstract

Son yıllarda mikro-elektromekanik sistemlerde süregelen gelişmelere bağlı olarak üretilen ucuz kablosuz algılayıcılar, Kablosuz Algılayıcı Ağlar (KAA)'ın kullanıldığı uygulama alanlarının artmasına neden olmuştur. Algılayıcı düğümler, fiziksel bir olayın izlenmesini sağlayan veri toplama, veri işleme ve iletişim gibi görevleri yerine getirmektedirler. Farklı alanlara dağıtılan birçok algılayıcı düğüm ise KAA kavramını oluşturmaktadır. Algılayıcıların farklı koşullar altında, altyapı olmadan, erişimden uzak bir şekilde maksimum verimle çalışmaları beklendiğinden enerji kısıtlamaları konusu KAA yapısının oluşturulmasında önemli bir yer tutmaktadır. Karınca Koloni Algoritması (KKA), yapay karıncalardan oluşmaktadır. Bu algoritmada, yapay feromon izlerinin sürekli olarak güncellenmesiyle tekrarlanan bir yapı mevcuttur. Algoritma çalışma süreci; yapay karıncaların bir tur sonunda geçtikleri yolların feromon miktarlarının arttırılması, belirli bir oranda feromon buharlaşmasının gerçekleştirilmesi, optimal çözümün bulunması, çözüme bağlı olarak global feromon güncellemesi ve yenilenmiş feromon miktarlarına bağlı olarak karıncaların yeni turlarını gerçekleştirmeleri şeklinde özetlenebilir. KAA'daki algılayıcıların verimli çalışmaları beklendiğinden ağ yaşam süresinin optimize edilmesi, ele alınması gereken önemli bir problem olarak durmaktadır. Literatürde, bu problemin çözümü için önerilen birçok yöntem bulunmaktadır. Bu tez çalışmasında ise ilgili problemin çözülmesi için KKA ve Genetik Algoritma (GA) hibrit edilip KKA-GA geliştirilmiştir. KKA-GA 10, 30 ve 50 düğüm için test edilmiş ve KKA ile kıyaslamaları yapılmıştır. KKA-GA'da karıncaların daha kısa mesafeden turlarına başladıkları görülmüştür. Geliştirilen algoritmada karıncaların daha kısa mesafeden turlarına başlama özellikleri esas alınarak ilk önce KKA-GA çalıştırılmıştır. Daha sonra KKA ile karıncalar turlarına devam etmişlerdir. Sonuçların daha da iyileştirilmesi amacıyla KKA-GA ile 50 yineleme sonrası elde edilen sonuç, KKA'nın başlangıç değeri olarak alınmıştır. Bunun ardından yapılan 150 yineleme sonrası sonuçlarda gözle görülür iyileşmeler gözlemlenmiştir.In recent years, cheap wireless sensors produced due to continuing developments in micro-electromechanical systems have increased the application areas where Wireless Sensor Networks (WSN) are used. Sensor nodes perform tasks such as data acquisition, data processing, and communication that enable monitoring of a physical event. Many sensor nodes distributed in different areas form the concept of WSN. As the sensors are expected to operate under different conditions, without infrastructure, without access, with maximum efficiency, the subject of energy restrictions has an important place in the formation of the WSN. Ant Colony Algorithm (ACA) consists of artificial ants. In this algorithm, there is a structure that is repeated by constantly updating the artificial pheromone traces. The algorithm study process can be summarized as increasing the pheromone amounts of the roads that artificial ants pass at the end of a tour, performing a certain rate of pheromone evaporation, finding the optimal solution, updating the global pheromone depending on the solution, and performing the new tours based on the renewed pheromone amounts. Optimizing the network lifetime remains an important problem that needs to be addressed, as the sensors in the WSN are expected to work efficiently. There are many proposed methods in the literature for the solution of this problem. In this thesis, ACA and Genetic Algorithm (GA) are hybridized and ACA-GA algorithm is developed to solve the problem. ACA-GA algorithm has been tested for 10, 30 and 50 nodes and compared with ACA. In the ACA-GA algorithm, it was observed that ants started their tours from a shorter distance. In the developed algorithm, the ACA-GA algorithm was first run based on the ants' starting features from shorter distances. Later, ants with ACA continued their tour. In order to further improve the results, the result obtained after 50 iterations with ACA-GA was taken as the initial value of the ACA. Visible improvements were observed in the results after 150 iterations.