Sensör Yerleştirme Probleminin Parçacık Sürü Optimizasyonu ile Çözümü

Sensör Yerleştirme Probleminin Parçacık Sürü Optimizasyonu ile Çözümü
Ali Tozan¹ F. Erdoğan Sevilgen² Onur İnce<sup>3

1,2,3</sup>Bilişim Teknolojileri Enstitüsü, TÜBİTAK Marmara Araştırma Merkezi, Kocaeli

^1,2Bilgisayar Mühendisliği Bölümü, Gebze Yüksek Teknoloji Enstitüsü, Kocaeli

¹e-posta: [e-mail] ² e-posta: [e-mail]

³ e-posta: [e-mail]



Özetçe

Popülasyon temelli sezgisel yöntemlerden biri olan Parçacık Sürü Optimizasyonu (PSO), kullanımı son yıllarda giderek artan ve iyi sonuçlar verdiği gözlemlenen bir yöntemdir. Bu makalede, özellikle askeri sınır gözetleme operasyonlarında önemli bir yere sahip olan sensör yerleştirme probleminin çözümü için bir PSO uygulaması geliştirilmiş ve sonuçları analiz edilmiştir. Problemin çözümü için genel bir sensör modeli geliştirilmiş ve sayısal haritalar ile gerçek bir alan üzerinde görülebilirlik analizleri yapılmıştır. Sensör yerleşim problemi için PSO yönteminin genel arama (exploration) ve detaylı arama (exploitation) işlemlerini yaptığı ve sensörleri arazi üzerinde iyi noktalara yerleştirdiği gözlemlenmiştir.

1.Giriş

Bir arazi üzerine maksimum miktarda alan gözetleme amacıyla, belirli sayıda sensörün konuşlandırılması özellikle askeri operasyonlarda oldukça önem taşır. Sensörler radar, termal kamera gibi bir hedefi tespit edebilen ve belirli bir görüş mesafesi olan cihazlardır. Arazinin çok geniş ve engebeli bir yüzeye sahip olması, problemin mümkün olan en az sayıda sayıda sensör kullanılarak çözülmek istenmesi ve kullanılan bu sensörlerin her birinin, arazi üzerindeki sınırsız sayıda noktadan herhangi birisine konuşlanabilme ihtimaline sahip olması gibi nedenler göz önünde bulundurulduğunda, bu problemin tüm ihtimaller denenerek çözülmesi mümkün olmamaktadır.
Literatürde sensör yerleştirme problemi ile ilgili farklı yaklaşımlar ve çözümler önerilmiştir. Yapılan çalışmalar özellikle arazi özelliklerine göre farklılaşmaktadır. Kullanılan alanlar ızgara (grid) tabanlı sayısal yükseklik haritaları ile modellenmiştir.
Chakrabarty ve arkadaşları verilen ızgara noktalarından oluşmuş bir alanda etkin gözetleme ve hedef takibi yapabilmek için bir kapsama stratejisi önermiştir [1]. Bu çalışmada sensörlerin yerleştirileceği alan ızgara (grid) noktalarından oluşan bir yapıdadır ve hedefler sadece bu noktalardan biri üzerinde bulunabilir.
Dhillon ve Chakrabarty sensörlerin bir alana etkin bir şekilde yerleştirilmesi için çalışmalar yapmışlardır [6]. Bu optimizasyon probleminin çözümünde kullanılacak sensör sayısı ve kullanılan sensörlerin nerelere konuşlandırılacağı bulunmaya çalışılmıştır. Arazi modeli olarak ızgara noktalarından oluşan bir yapı kullanılmıştır. Çalışmada ek olarak sensörlerin tespit edebilmelerine olasılıklı bir yaklaşım getirilmiştir. Geliştirilen algoritmalar kesin olmayan tespit yeteneği ve belirsiz sensör alanı özellikleri gibi kısıtları da göz önünde bulunduracak şekilde tasarlanmıştır.
Can ve arkadaşları yaptıkları çalışmada farklı tiplerdeki sensörlerin sayısal yükseklik haritaları ile oluşturulmuş 3 Boyutlu (3D) bir arazide, istenilen düzeyde kapsamayı gerçekleştirecek şekilde yerleştirilmesini sağlayan bir yöntem geliştirmişlerdir [7]. Bu çalışmada sensör modeli ileriye bakan kızıl ötesi (Forward Looking Infra-Red) kamera olarak tasarlanmıştır.
Marengoni ve arkadaşları çalışmalarında Müze Probleminin (Art Gallery Problem) bir türevi olan 3D versiyonuna bir çözüm yöntemi geliştirmişlerdir [8]. Çalışmalarında problemlerini şu şekilde tanımlamışlardır: “Verilen 3D bir arazi üzerine ne kadar ve nerelere sensör yerleştirelim ki tüm arazi kapsanmış olsun?”. Bu problemde arazi olarak DEM formatında sayısal yükseklik haritası kullanılmıştır. Arazi TIN ( Triangulated Irregular Network ) olarak temsil edilmiş ve bir noktadan bir başka noktanın görülebilirliği LOS (çizgisel görülebilirlik) algoritmalarıyla gerçekleştirilmiştir.
Undeger ve arkadaşları gözetleme işleminin askeri operasyonlardaki önemine dikkat çekmiş ve çalışmalarında geniş alanların ne kadar, hangi tipte sensör kullanarak ve bu sensörlerin nerelere konuşlandırılmasıyla en etkin sonuçları elde edebileceklerini araştırmışlardır [2]. Sistemlerinde belirli görülebilirlik özelliklerine sahip gündüz kamerası, kızıl ötesi kamera ve radar gibi çeşitli sensör sistemleri modellenmiş ve görülebilirlik analizlerine imkan tanımışlardır. Bu problemin çözümü için bir genetik algoritma çözümü geliştirilmiştir. Ayrıca yaptıkları literatür araştırmasında, bu konu hakkında çok fazla çalışma olmadığını belirtmektedirler.
Bu çalışmada, DTED sayısal yükseklik haritaları ile alan modellenmiş ve çizgisel görülebilirlik algoritmaları ile sensörler modellenmiştir. Sensör yerleştirme probleminin çözümü için bir PSO (Parçacık Sürü Optimizayonu) modeli geliştirilmiştir. Test sonuçlarında PSO algoritması ile tüm arama alanının yüzeysel olarak tarandığı ve iyi noktalarda daha detaylı arama yapıldığı gözlemlenmiştir. Sonuç olarak genelde arazi üzerinde yüksekteki noktalar üzerinde yoğun arama yapıldığı ve çözümün bu noktalardan seçildiği görülmektedir. Dolayısıyla PSO algoritmasının hem global aramayı hem de yerel aramayı yaptığı gözlemlenmiştir. Bu makalede PSO metodunun sensör yerleştirme problemine nasıl uyarlandığı anlatılacak ve sonuçları değerlendirilecektir.

2.Problem Tanımı

Gerçek hayatta özellikle askeri operasyonlarda radar, termal kamera, gündüz kamerası vb. sensörlerin ilgili bölgeyi en etkin gözetleyecek şekilde konuşlandırılmaları oldukça önemlidir. Bir araziye belirlenen sayıdaki sensörün azami kapsamayı sağlayacak şekilde yerleştirilmesi problemin genel tanımını oluşturur. Bu kısımda arazi, sensör ve görülebilirlik hesaplarından bahsedilecek ve problem bir optimizasyon problemi olarak ifade edilecektir.

2.1.Arazi

Sensör yerleştirme problemi için önerilen bir çözümün gerçekçi sonuçlar verebilmesi için, arazi verilerinin de gerçeğe yakın modellenmesi gerekmektedir. Bunu sağlamak için pek çok sayısal harita formatı kullanılabilir. Yapılan çalışmada, “National Imagery and Mapping Agency” tarafından sağlanan DTED (Digital Terrain Elevation Data) formatındaki sayısal haritalar kullanılmış ve arazi bu harita üzerinde köşe koordinatları verilen dikdörtgen olarak tanımlanmıştır. Görülebilirlik analizi işlemleri 2 boyutlu bir matris içerisinde tutulan, DTED dosyalarından okunan yükseklik verileri ile yapılmıştır. Bu verilere ait çözünürlük, görülebilirlik hesabının daha kesin sonuçlar verebilmesi için doğrusal ara değerleme (linear interpolation) yöntemi ile daha da artırılmıştır.

2.2.Sensör

Sensörler, genel olarak belirli bir algılama kapasitesi olan ve belirli bir menzil dâhilinde bilgi toplayabilen cihazlardır. Problem çözümünde kullanılacak sensör modeli problemin gereksinimlerine göre farklılık gösterebilir (Termal, Elektromanyetik, Mekanik, Kimyasal, Akustik, Optik vb.). Bu çalışmada belirli bir menzile sahip, menzili içerinde bulunan cisimleri çizgisel görülebilirlik analizi ile görebilen genel bir sensör modeli kullanılmıştır. Çizgisel görülebilirlik (Line of Sight), bir yüzey üzerinde seçilen iki referans noktadan birinde bulunan bir gözlemci tarafından, bu iki nokta arasında kalan kısımların ne kadarının görülebileceğini bulmaya yarayan hesaplamalardır. Bir sensörün menzilinde bulunan herhangi bir nokta çizgisel görülebilirlik içerisinde ise bu noktanın sensör tarafından görüldüğü kabul edilir. Yani sensör menzili içerisinde bir cismin görülebilme ihtimali tüm uzaklıklar için aynıdır. Çizgisel görülebilirlik hesabının hızlı olması problemin çözüm hızı açısından oldukça önemlidir. Yapılan çalışmada çizgisel görülebilirlik hesaplamaları, Bresenham Çizgi Çizme (Bresenham’s Line Drawing) algoritmasının üzerine bina edilmiş olan Bresenham Çizgisel Görülebilirlik algoritması ile yapılmaktadır [5]. Bu algoritma, tamsayı aritmetiğini kullandığı için oldukça hızlı çalışmakta ve bilgisayar grafiklerinde sıklıkla kullanılmaktadır.

2.3.Görülebilirlik Hesabı

Arazinin yerleştirilen sensörler tarafından görülebilirliğinin hesaplanması için, arazi üzerindeki tüm noktaların görülebilirliğinin hesaba katılması gereklidir. Bu işlem uzun süreceği için arazi üzerinde belirli noktalar seçilerek örnekleme yapılır: Tanımlanmış dikdörtgen araziye karşılık gelen Şekil 1’de verilen görülebilirlik ızgarası tanımlanır. Hesaplama iki aşamadan oluşur. Bu aşamanın ilkinde, tanımlanan her bir sensörün bu ızgara üzerindeki herbir hücreyi görüp görmediği hesaplanır. Bu hesaplama sonucunda arazinin görülebilirlik matrisi elde edilmiş olur. İkinci aşamada ise arazinin hangi oranda görülebildiği hesaplanır. Görülebilirlik hesabında her bir hücrenin köşe noktaları ve merkezi olmak üzere 5 noktasına bakılır ve toplam görülen nokta oranında hücrenin görülebilirliği çıkartılır. Toplam alanın görülebilirliği her bir hücrenin görülebilirlik değerinin toplamıyla hesaplanır.


Şekil 1: Görülebilirlik hesabının yapılacağı alanın ızgara haline getirilmesi ve belirlenen noktalar.

2.4.Problemin Formüle Edilmesi

Yukarıda tanımlandığı gibi problemin çözümünde hedeflenen, belirli sayıda sensörle belirli bir alanın azami derecede kapsanmasıdır. Dolayısıyla problem, verilen bir arazi ve sensör kümesi için etkinlik ifadesi olan arazinin görülebilirlik değeri eniyileyecek sensör pozisyonlarının hesaplanmasıdır.
Daha önce ifade edildiği gibi bir alanın görülebilirlik değeri alan içerisindeki hücrelerin görülebilirlik değerinin toplamı şeklinde ifade edilmişti. Bu şekilde kapsamanın tanımı yapılırsa i. ızgara hücresindeki görülen nokta sayısı N_i, bir hücrenin alanı A_i ve optimizasyon yapılacak bölgenin toplam alanı T olarak tanımlanmış olsun. Böylece problemin çözümü için gereken amaç fonksiyonu aşağıdaki şekilde ifade edilmiştir:

(1)

Bu formüle göre Z değeri tanımlı alanın yüzde olarak en fazla hangi oranda görülebileceğini gösterir. 0.2 değeri ile ifade edilmek istenen bir hücre içindeki 5 noktadan her birinin görülebilirliğe etkisidir. 0.2N_i sonuç olarak [0,1] aralığında bir değer almış olur.

3.Parçacık Sürü Optimizasyonu

Son yıllarda kullanım alanı giderek artan ve 1995-1996 yıllarında Kennedy ve Eberhart tarafından ortaya atılan Parçacık Sürü Optimizasyonu (PSO) tekniği, kuş ve balık sürülerinin hareketlerinden esinlenerek oluşturulmuş metasezgisel bir yöntemdir [3]. PSO popülasyon temelli bir yaklaşım olup, bireyler arasındaki sosyal bilgi paylaşımı yöntemin en belirgin özelliğidir. Popülasyondaki her bir birey bir aday çözümü ifade eder ve parçacık olarak adlandırılır. Bireyler pozisyon ve hız bilgisine sahiptir. Pozisyon bilgisi bir çözümü temsil eder ve hız bilgisiyle algoritmanın her iterasyonunda pozisyonlar güncellenir. Popülasyonda bilgi paylaşımı her bir bireyin daha önce bulmuş olduğu en iyi pozisyon bilgisi (p_best) ve tüm sürüde bulunan ve şimdiye kadar bulunmuş en iyi pozisyon bilgisi (g_best) ile gerçekleştirilir. Tüm parçacıklar hız vektörleriyle bu iki en iyi pozisyona yönelmeye çalışırlar. Bir parçacığın hızı v, pozisyonu p olarak tanımlanırsa algoritmanın (t+1)’inci iterasyonunda yeni hız ve pozisyon bilgisi şu şekilde güncellenir:

	(2)
	(3)

Yukarıdaki denklemlerde c₁ ve c₂ öğrenme faktörleridir ve genel kullanım olarak 2 değerini alırlar. r₁ ve r₂, [0,1] aralığında düzgün dağılımlı rasgele sayılardır. w değeri ise atalet faktörü olarak adlandırılır ve zamanla değeri düşürülerek daha önceki hız bilgisinin etkisinin azaltılması kullanılan yöntemlerden biridir. Şekil 2’de standart bir PSO algoritmasının komut dizimi görülmektedir.

Begin

Başlangıç parametrelerini ata

Başlangıç popülasyonunu oluştur

Her bir parçacık için

Uygunluk değerini hesapla

pBest’i bul

gBest’i bul

Do

Her bir parçacık için

(2) denklemine göre parçacık hızını hesapla

(3) denklemine göre parçacık pozisyonunu hesapla

Uygunluk değerini hesapla

pBest’i güncelle

gBest’i güncelle

w değerini güncelle

While Durdurma Kriteri

End

Şekil 2: PSO prosedürü.

4.Problemin Parçacık Sürü Optimizasyonuna Uyarlanması

Bu kısımda, problemin PSO algoritmasına nasıl uyarlandığı anlatılmaktadır. İlk olarak problemin çözüm kümesinin nasıl temsil edileceği anlatılmış ve ardından uygulanan PSO algoritması ve parametreleri gösterilmiştir.

4.1.Parçacık Yapısı ve Çözüm Kümesi Gösterimi

Sensör yerleşim probleminde bir sensörün pozisyonu [0,1] aralığında iki reel sayıdır. Bu sayılar sensörün bulunduğu enlem ve boylam bilgisinin [0,1] aralığına çekilmiş ifadesidir. Böylece çözüm gerçek koordinat değerlerine bağlı olmaksızın yapılabilmektedir. Gerçek koordinatlara dönüştürme uygunluk değerinin hesaplanması esnasında gerçekleştirilmektedir. Problemin olası bir çözümü, probleme girdi teşkil eden sensör sayısında sensör koordinatlarından oluşan bir listesidir. PSO algoritmasında her bir parçacık bu listeyi pozisyon bilgisi olarak tutar. Bir sensör için [0,1] aralığındaki enlem bilgisi s_e ve boylam bilgisi s_b olarak ifade edilirse n adet sensörden oluşan bir problemde herbir parçacığın pozisyon bilgisi şeklinde ifade edilir. Bir parçacığın hız bilgisi yine [0,1] aralığında bir sayıdır ve her bir pozisyon bilgisine karşılık bir hız bilgisi mevcuttur. Dolayısıyla bir parçacığın hız bilgisi şeklinde ifade edilir.

4.2.Problemin PSO’ya uyarlanması

Problemin gösterim biçiminin tanımlanması sonrasında PSO algoritmasını uygulanması için başlangıç popülasyonunun belirlenmesi ve algoritmanın parametrelerinin atanması gerekmektedir. Algoritma başlangıç popülasyonu olarak her bir parçacık için sensörlere alan içerisinde rasgele koordinatlar atayarak başlar. Parçacıkların başlangıç hızları [0,1] aralığında rasgele sayı değerleridir. Her bir iterasyonda sensörlerin koordinat değerleri (2) ve (3) numaralı denklemler kullanarak güncellenir ve böylece çözüm uzayında yeni yerler denenerek küresel eniyi değer araştırılır. PSO algoritmasında atalet sabitinin zamanla düşürülmesi ile daha iyi sonuçlar verdiği gözlemlenmiştir. w değerinin (t+1)’inci iterasyondaki güncellemesi aşağıdaki formüle göre yapılmaktadır.

(5)

Başlangıçta w değeri 1 olarak seçilir. Durdurma kriteri olarak belirli sayıda etkinlik fonksiyonu çağrılması sonucunda algoritma sonlandırılır.

5.Deneysel Çalışmalar

Tüm deneysel çalışmalar AMD Turion 1.8 GHz işlemci ve 1.5 GB RAM’e sahip bir bilgisayarda yapılmıştır. Yazılımlar Sun Java JDK 1.5 dili kullanılarak kodlanmıştır.
Örnek problemler Tablo 1’de verilmiştir. Bu problemlerde arazi, verilen DTED sayısal haritanın tamamı değil, üzerinde tanımlanış bir dikdörtgen alanlardır. Probleme girdi teşkil edecek arazi, ekran üzerinde bir dikdörtgenin sol üst köşesi ve dikdörtgenin en ve boy bilgisinin belirlenmesiyle tanımlanmış olur. Harita formatının kısıtlamasıyla köşe bilgisi gerçek dünya koordinatlarında (enlem, boylam) tanımlanmalıdır. Örneğin bir arazi E008-N37, 10x10 şeklinde ifade edilirse, köşe koordinatı 8 derece doğu meridyeni, 37 derece kuzey paraleli üzerinde olan ve eni 100 km, boyu 150 km olan bir dikdörtgen arazi tanımlanmış olunur. Tüm örnek problemlerde köşe noktaları E037, N37 olarak tanımlanmış ve en ve boy bilgileri Tablo 1’de gösterilmiştir. Tablo 1’de sensör sayısı ve kullanılan sensörlerin menzil bilgileri de bulunmaktadır. Ayrıca her bir sensörün yerden 3 metre yüksekte olduğu kabul edilmektedir. PSO yöntemi için popülasyon büyüklüğü 30, c₁ ve c₂ değerleri 2, popülasyondaki herbir parçacığın başlangıç hız ve pozisyonları [0,1] aralığında rasgele sayılardır. Algoritma durdurma kriteri etkinlik değerlerinin yaklaşık olarak 7020 defa çağrılmasıdır. Tablo 1’de verilen problemlerin her biri için PSO çözümü 10’ar defa çalıştırılmış ve ortalama sonuçlar Tablo 2’de gösterilmiştir.
Tablo 1: Örnek problemler

Test Adı	Alan Büyüklüğü(km^2)	Sensör Sayısı	Sensör Menzili(km)
1	25 (5x5)	2	3
2	100 (10x10)	3	5
3	400 (20x20)	4	10

Tablo 2: PSO ile sonuçlar

Test Adı	Etkinlik (%)	Süre (ms)	Etkinlik F. Çağrıma
1	65,41	7690	7020
2	43,90	36343	7020
3	39,39	164190	7020

Şekil 3: (a) Soldaki resimde 3 numaralı testte kullanılan alan görülmektedir.

(b) Ortadaki resimde 3 numaralı test alanı için bir çözüm esnasında denenmiş sensör pozisyonları beyaz noktalar ile belirtilmiştir.

(c) Sağdaki resimde 3 numaralı test alanı için çözüm sonucunda bulunan sensör noktaları ve kapsanan alan görülmektedir.

Şekil 3-a’da 3 numaralı test için kullanılan alan görülmektedir. Bu şekilde açık renk ile gösterilen bölgeler daha yüksek noktalardır. Normal durumlarda çözüm sonucunda, sensörlerin çoğunun yüksek noktalarda görülmesi beklenmektedir. Sonuçlar incelendiğinde Şekil 3-b ve Şekil 3-c’de görüldüğü gibi yüksek noktalar üzerinde yoğun arama yapılmış ve sensörler yüksek yerlere konuşlanmıştır. Şekil 3-b incelendiğinde PSO algoritmasının en çok Şekil 3-c ile verilen sonuca yakın yerlerde arama yaptığı görülmektedir. Böylelikle PSO algoritmasının iyi sonuçların etrafında daha çok arama yaptığını, yani detaylı aramayı (exploitation) gerçekleştirdiğini söyleyebiliriz. Ayrıca alan üzerinde çok farklı yerlerin denendiği de Şekil 3-b’de görülmektedir ve bu PSO algoritmasının araştırmayı (exploration) da gerçekleştirdiğinin bir göstergesidir.


Şekil 4: 1, 2 ve 3 numaralı test için örnek bir iterasyon-etkinlik grafiği
Diğer göz önünde bulundurulacak husus ise alan büyüklüğü ve sensör sayılarının artırılması sonucunda algoritmanın daha fazla iterasyon ile çalıştırılması gerektiğidir. Şekil 4’te gösterildiği gibi alanının büyüklüğünün ve sensörlerin sayısının artırılması sonucunda algoritma daha fazla iterasyon yaparak yakınsamıştır.

6.Sonuç

Bu çalışmada sensör yerleştirme problemini çözmek için bir Parçacık Sürü Optimizasyonu algoritması önerilmiş ve bu yaklaşımın performansı ve sonuçları incelenmiştir. Bu çalışma benzer çalışmalar için bir temel oluşturmakta ve performans metrikleri açısından daha sonraki çalışmalar için bir altyapı sunmaktadır. Bundan sonraki çalışmalarda problem farklı algoritmalar ile denenecek ve PSO algoritması ile farkları ortaya konmaya çalışılacaktır.

7.Kaynakça

1. 
   Dhillon, S. S. and Chakrabarty, K., “Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks”, IEEE 2003.
   
2. 
   Undeger, C., Balci, M., Girgin S., V., Koc, Polat, F., Bilir, S., and Ipekkan, Z., “Sensor Platform Optimization and Simulation for Surveillance of Large Scale Terrains”, Proceedings of I’ITSEC 2002 Conference on Modeling and Simulation, Orlando, Florida, 2002
   
3. 
   Eberhard, R.C., Kennedy, J., “New optimizer using Particle Swarm Theory”, Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan (1995).
   
4. 
   National Imagery and Mapping Agency. (1999). Digital Terrain Elevation Data (DTED). Standards and Specifications Publications: MIL-PRF-89020A Amendment-1, 27, 1999.
   
5. 
   Bresenham, J. E., “Algorithm for computer control of a digital plotter”, IBM Systems J., 4(1), pp.25-30(1965)
   
6. 
   Dhillon, S. S. and Chakrabarty, K., “Sensor placement for effective coverage and surveillance in distributed sensor networks”, Proc. IEEE Wireless Communications and Networking Conference, pp. 1609--1614, 2003
   
7. 
   Can, T., Isler, V., and Ipekkan, Z., “Sensor Optimization In a Virtual Environment”, in Proceedings of the 9th Conference on Computer Generated Forces and Behavioral Representation, Orlando, FL, May, 2000
   
8. 
   Marengoni, M., Draper, B., Hanson, A., and Sitaraman, R., “Placing Observers to Cover a Polyhedral Terrain in Polynomial Time”, Proceedings of the Third Workshop on Applications of Computer Vision, 1996.