Kablosuz algılayıcı ağlarda maksimum kapsama alanı probleminin genetik algoritma ile çözümü
Increasing the coverage of  wireless sensor networks by genetic algorithm based deployment
Yazar: OZAN ZORLU
Danışman: DOÇ. DR. ÖZGÜR KORAY ŞAHİNGÖZ
Hava Harp Okulu Komutanlığı / Havacılık ve Uzay Teknolojileri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Yazılım Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Genetik algoritma tekniği = Genetic algorithm technique ; Genetik algoritmalar = Genetic algorithms ; Kablosuz ağlar = Wireless networks

Özet:
Kablosuz iletişim, digital sistemler ve mikro-elektronik-mekanik sistem teknolojilerinin gelişimiyle beraber, kablosuz algılayıcı ağlar (KAA) geliştirilmiş ve sağlık, askeri, endüstri, çevre vb. gibi bir çok gerçek dünya uygulamasında kullanılmıştır. KAA'lar, sınırlı kaynakları ve kısıtları nedeniyle fazla enerji tüketimi, sensör düğümü yerleştirimi, veri birleştirmesi ve iletimi gibi bir çok problemle karşılaşmaktadır. Sensör düğümü yerleştirimi problemi, diğer problem alanlarına doğrudan veya dolaylı olarak etki etmektedir. Bu nedenle, bu çalışmada, sensör düğümlerinin yerleştirimi problemi üzerinde çalışılmış ve  kablosuz algılayıcı ağda sensör düğümlerinin  kapsadığı alanın artırılması organize yerleştirim yöntemiyle gerçeklenmeye çalışılmıştır. Geleneksel matematiksel hesaplamalar ile çözülmesi çok uzun zaman ve kaynak isteyen bu problem NP-zor olarak bilinmektedir. Ayrıca bu problem maksimum kapsama sensör düğümü yerleştirme problemi olarak da literatürde geçmektedir. Çalışmada ilk olarak sensör düğümlerinin kapsama mesafelerinin aynı olduğu -homojen-, daha sonra ise sensör düğümlerinin farklı kapsama mesafelerine sahip olduğu -heterojen- topoloji üzerinde çalışılmıştır. 2 boyutlu alan üzerine yerleştirim yapılması için yeni bir genetik algoritma (GA) ve yerel iyileştirme algoritması geliştirilmiştir. Ele alınan problem, sunulan genetik algoritma ve özgün geliştirilen yerel iyileştirme algoritması derinlemesine anlatılmıştır. Sunulan GA'nın  ilk yerleştirme sonrası oluşan topolojiye uygulanması sonucu, iterasyona bağlı olarak kapsama alanının artışı ve yerel iyileştirme algoritması ile yapılan deneylerin sonuçları sunulmuştur. Organize yerleştirme ve rastgele yerleştirme yöntemleri kısaca açıklanmış olup geliştirilen GA yerel iyileştirme algoritması ile test verilerine uygulanmıştır. Sonuçlara göre; sunulan GA, yerel iyileştirme algoritmasıyla uygulandığında daha hızlı çalışıp, daha iyi kasama sonuçlarına ulaşırken, organize yerleştirmenin rastgele yerleştirmeye oranla daha fazla sensör kapsaması sağladığı ve daha verimli olduğu gözlemlenmiştir.

Abstract:
In consequence of advances in wireless communication, digital systems and micro-electronic-mechanical system technologies wireless sensor networks (WSNs) have been developed and applied in lots of different real-world applications such as military, industrial, environmental, health, etc. Due to their limited resources and constraints, WSNs face with several problems such as energy consumption, node deployment, data aggregation and transmission. Node deployment affects other problem domains in a direct or indirect way. Therefore, in this study, we deal with this problem and try to increase the coverage area of WSN system with an organized deployment approach. This problem is an NP-Hard problem, and it is hard to solve with standard mathematical formulations. Also this problem is known as maximum coverage sensor deployment problem (MCSDP) in literature. In this paper, firstly worked on the topology that consists from sensor nodes which have the same sensing ranges -homogeneous-, then the topology consists from sensor nodes which have different sensing ranges. A novel GA and local optimization algorithm are developed for deploying sensor nodes on 2 dimensional area. Studied problem, proposed genetic algorithm and novel local optimization algorithm are described deeply. The result of applying GA to initial deployment topology, increase of coverage are due to iteration count and results of experiments with local optimization algorithm are represented. Organized and random deployment techniques are described briefly and developed GA with local optimization algorithm is applied to test data. According to results of experiments; proposed GA is performing faster and getting better coverage rates. Also, it is seen that organized deployment technique is more efficient than random deployment technique.