Sensör yerleştirme probleminin genetik algoritma ve parçacık sürü optimizasyonu ile çözümü

Abstract

Askeri ve sivil alanda, çesitli sensörlerin, bir arazi üzerine, o araziyi en etkin sekilde gözetlemesi için yerlestirilmesi oldukça önemlidir. Sensör yerlestirme probleminde bir arazi üzerine, belirli sayıda sensörün araziyi maksimum kapsaması için konuslandırılabileceği en uygun noktaların bulunması hedeflenmektedir. Yapılan çalısmada arazi modellenirken sayısal yükseklik haritalarıyla gerçek yükseklik verileri kullanılmıstır. Sensör modeli olarak çok yönlü bir sensör modeli gelistirilmis ve görülebilirlik hesaplamalarıyla arazinin sensörler tarafından ne oranda kapsandığı hesaplanmıstır. En uygun sensör pozisyonlarının bulunması için literatürde optimizasyon problemleri için sıklıkla kullanılan Genetik Algoritma (GA) ve Parçacık Sürü Optimizasyonu (PSO) yöntemleri probleme uyarlanmıstır. Ayrıca bu yöntemleri daha da gelistirmek amacıyla, ?ndirgenmis Değisken Komsuluk Arama Metodu, GA ve PSO yöntemlerinin iterasyonlarında uygulanmıstır. Problem algoritmalara uyarlanırken, çözüm kümesinin gösteriminde kullanılan sensör pozisyonları için reel sayılar kullanılmıstır. Haritalarda bulunmayan yükselti bilgileri doğrusal ara değerleme ile hesaplanmıs ve problemin çözümü için reel sayı yaklasımı getirilmistir. Problemin GA ve PSO uyarlamalarında reel sayı yaklasımının getirilmesi literatürdeki diğer arastırmalara göre farklılık göstermektedir. Yapılan deneylerde elde edilen sonuçlara göre GA yönteminin PSO yöntemine göre daha iyi sonuçlar verdiği gözlemlenmistir. Ayrıca yerel arama yönteminin farklı arazi çesitleri için PSO yöntemini iyilestirdiği fakat GA yöntemini iyilestirmediği görülmektedir.Surveillance of a terrain with various sensors and finding the most suitable positions of sensors is so important in military and public domains. ?Given n observers and a terrain, where should we place them in order to maximize the overall coverage of terrain?? is the main question of the sensor placement problem. In this study, the terrain is modelled with digital elevation maps. Sensors are modelled as an omnidirectional obsever and the visibility of terrain is computed using line of sight algorithms. In order to find the most efficient sensor positions, Genetic Agorithm (GA) and Particle Swarm Optimization (PSO) methods are applied to the problem. Also Reduced Variable Neighborhood Search is applied as a local search routine in GA and PSO iterations. In problem representation, real valued numbers are used to represent sensor positions. Moreover, lineer interpolation method is applied for missing elvation information in digital maps. Main difference of GA and PSO aplication for sensor placement problem from literature is applying real valued sensor position representation on the problem. In experiments, GA is outperformed PSO method according to the results. Also local search improves PSO method for different kinds of terrains but does not improve GA.