Multiple Base Station Placement with k-means Local+ - ISL
Transkript
Multiple Base Station Placement with k-means Local+ - ISL
Birden Fazla Baz stasyonunun k-means Local+ Algoritmas ile Yerle tirilmesi Multiple Base Station Placement with k-means Local+ Z.Cihan TAY , M.Amaç GÜVENSAN, A. Gökhan YAVUZ Bilgisayar Mühendisli i Bölümü Y ld z Teknik Üniversitesi {cihan, amac, gokhan}@ce.yildiz.edu.tr Özetçe Alg lay c a uygulamalar nda, a ya$am süresi, baz istasyonu ve alg lay c dü üm say s pekçok farkl k s t mevcuttur. Bu konuda yap lan ara$t rmalar n ana hedefi, en dü$ük bütçe ile en uzun a ya$am süresini elde etmektir. Bu hedefi sa layabilmek için baz istasyonu yerle$tirme ve yönlendirme algoritmas seçimi iki önemli kriterdir. Ak ll tar m, çevre ve hava durumunun izlenmesi gibi birçok telsiz alg lay c a uygulamas sürekli veri iletim modeline dayan r. Bu tür uygulamalarda her alg lay c dü üm genelde ayn büyüklükteki veriyi peridoyik olarak çok atlamal ileti$imle baz istasyonuna gönderir. Bu çal $mada yukar da belirtilen alg lay c a uygulamalar n n ya$am süresinin uzat lmas amac ile birden fazla baz istasyonunun yerle$tirilmesi için k-means Local+ algoritmas önerilmi$tir. Ayn veri seti ile yap lan testlerde önerilen algoritman n kmeans algoritmas na göre a ya$am süresini %45 oran nda uzatt gösterilmi$tir. Abstract Sensor applications have many different constraints such as the network lifetime, the number of sensor nodes and base stations (BS). The main goal of the researchers is to maximize the network lifetime with minimum budget. BS positioning and the choice of routing algorithm are two important criteria in maximizing the lifetime. Many wireless sensor network (WSN) applications, like intelligent agriculture, habitat and weather monitoring, are based on continuous data delivery model. In these applications, each sensor node generally collects data of the same size and periodically transfers this data to BS by multi-hop communication. To maximize the network lifetime of such applications, we propose a new BS placement algorithm for deploying multiple base stations, called k-means Local+, which provides up to 45% longer network lifetime than single k-means algorithm [1] 1. Giri Telsiz alg lay c a lar, ilk olarak askeri uygulamalar için tasarlanm $ ve gerçeklenmi$tir. Günümüzde ise bu a lar do al ya$am n izlenmesinden ak ll tar m uygulamalar na, endüstriyel üretimden güvenlik uygulamalar na kadar birçok alanda kullan lmaktad r. Telsiz alg lay c dü ümler (TAD) genellikle mikroi$lemci, telsiz al c -verici, depolama, alg lay c ve güç yönetim birimlerinden olu$urlar. Bu dü ümlerin amac bulunduklar bölgeden bilgi toplamak ve bilgiyi baz istasyonuna ula$t rmakt r. Bu nedenle farkl pozisyonlarda yer alan alg lay c dü ümlerin birbirleri ile ileti$im kurmas gereklidir. Alg lay c a lar pil gücü, dü üm say s ve istenilen verinin niceli i ve niteli indeki k s tlar aç s ndan di er a lardan farkl d rlar. TAD’lar n boyutunu küçültebilmek için enerji k s t olan dü$ük kapasiteli ve küçük piller kullan l r. Bu nedenle alg lay c a uygulamalar nda a ya$am süresini uzatabilmek için güç tüketimini en dü$ükte tutabilmek temel hedeftir. Literatürde, telsiz alg lay c a larda güç tüketimini azaltabilmek için yap lm $ farkl ara$t rmalar yer almaktad r. Baz çal $malar iletim gücünü azaltmak için alg lay c dü ümlerin s k da t lmas n önerirken, baz lar ise ileri donan m tasar m ve uygun protokoller kullanarak bekleme modunda harcanan enerjiyi azaltmay ba$arm $lard r. Öte yandan minimum enerji yollar n bulmak için algoritmalar geli$tirilmi$tir [3],[4]. Kimi uygulamalar binlerce ayg lay c dü ümün izlenecek bölgeye da t lmas n zorunlu k lar. Bu durumda ölçeklenebilirlik tasar m kriterlerinin ba$ nda yeral r. Bu kriteri sa layabilmek için izlenen bölgeye birden fazla baz istasyonu yerle$tirmesi gereklidir. Bu tür durumlarda baz istasyonlar n n efektif yerle$tirilmesi, a$ lmas gereken önemli bir problem olarak kar$ m za ç kar ve a ya$am süresini do rudan etkiler. Bu çal $mada, birden fazla baz istasyonunu efektif yerle$tirme algoritmalar incelenmi$ ve mevcut a ya$am süresini uzatan yeni bir baz istasyonu yerle$tirme algoritmas önerilmi$tir. 2. bölümde baz istasyonu yerle$tirme problemi ile ilgili literatürdeki çal $malara yer verilmi$tir. 3. bölümde a topolojisi ile ilgili k s tlardan, varsay mlardan ve tan mlardan detayl olarak bahsedilmektedir. 4. bölümde ise önerilen kmeans Local+ algoritmas n n detaylar verilmi$tir ve 5. bölümde de uygulanan test senaryolar ve elde edilen sonuçlar sunulmu$tur. 2. Baz stasyonu Yerle tirme Yakla mlar Telsiz a kurulumunda bir veya daha fazla baz istasyonunun alg lay c dü ümlerin etraf na veya aras na optimum yerle$tirilmesi ile ilgili önemli say da ara$t rma yap lm $t r. Mevcut çal $malar [6],[7],[8] incelendi inde, yap lan varsay mlara, dü$ünülen a modeline, mevcut a durum bilgisine ve optimize edilen metriklere [5] göre farkl l klar oldu u görülmektedir. TAD’lar n s n rl pil kapasitesine sahip olmas sebebiyle, baz istasyonu yerle$tirme yöntemi a ya$am süresini do rudan etkiler. Ayr ca baz istasyonlar n n maaliyetleri tasar mc lar , baz istasyonlar n mümkün oldu u kadar optimum yerle$tirmeye yöneltmektedir. Baz istasyonu yerle$tirme problemi için önerilen baz yakla$ mlar; en iyi baz istasyonu yerlerinin bulunmas , önceden tan mlanm $ bir operasyon süresinin en az say da baz istasyonu ile sa lanmas ve en az say da baz istasyonu ile en uzun a ya$am süresinin elde edilmesi olarak 3 grupta toplanabilir [1]. Ilk De erlerin Atanmas TAD’lar n Da t lmas Baz Istasyonlar n n Yerle$tirilmesi (K-MEANS) A Demas n n Olu$turulmas Rotalama Yap lmas k-means Local+ A Ya$am Süresinin Hesaplanmas 2.1. Birden Fazla Baz stasyonunun Yerle tirilmesi Varsay mlara ve a modellerine ba l olarak, optimum baz istasyonu yerle$tirme problemi çözümlerinin bir ço u NP karma$ kl ndad r. Bu tür karma$ kl n üstesinden gelmek için genellikle yak nsama yap lmas gerekmektedir. Örne in, [9] çal $mas nda arama alan TAD’lar n konumlar ile s n rland r lm $t r ve TAD’lar aras ndaki en iyi pozisyon, a ya$am süresi kriteri göz önüne al narak belirlenmi$tir. Di er yandan, tamsay do rusal programlama yöntemi ile baz istasyonlar n n yerlerini belirleyen metotlar da mevcuttur. Telsiz alg lay c a ya$am süresinin önceden tan mland durumlarda bu ya$am süresini sa layacak minimum say da baz istasyonu kullan lmal d r. Öte yandan baz istasyonu maliyeti telsiz a uygulamalar nda kullan lacak baz istasyonu say s n belirleyen di er bir kriterdir. Bu nedenlerle hem baz istasyonu say s n n hem de baz istasyonu yerinin a ya$am süresi üzerindeki etkisi ara$t r lm $t r. Yap lan çal $malar incelendi inde telsiz alg lay c a larda baz istasyonu yerle$tirilmesi amac ile hiyerar$ik olmayan kümeleme algoritmalar n n [10] tercih edildi i ve en çok kmeans algoritmas n n kullan ld görülmektedir [1]. Bu çal $mada da, k-means algoritmas temel al narak, baz istasyonlar n n kendisine kom$u olan TAD’lardan alt TAD’lar en fazla olan TAD’lara daha yak n olacak $ekilde yerle$tirilmesini sa layacak k-means Local+ algoritmas olu$turulmu$tur. 3. Sistem Modeli Dekil 1’de baz istasyonu yerle$tirilmesi amac ile önerilen kmeans Local+ algoritmas n n testlerinde kullan lan sistemin blok diyagram yer almaktad r. ekil 1: k-means Local+ testlerinde kullan lan sistemin ak $ n gösteren blok diyagram 3.2. Yer Bilgisinin Hesaplanmas ve Toplanmas Baz istasyonlar n n yerle$tirilecekleri noktay hesaplayabilmek için her TAD’ n yer bilgisine ihtiyaç duyulmaktad r. Yer bilgisi GPS, ultrasound, akustik gibi özel donan mlarla ve/veya merkezi veya da t k metotlar elde edebilir [1]. Bu çal $mada yer bilgisinin merkezi yöntemle hesapland kabul edilmi$tir. 3.3. k adet Baz Belirlenmesi stasyonu için En yi Yer Bilgisinin TAD’lar oldukça k sa alg lama masefelerine sahiptirler. Gözlenecek olan bölgenin en iyi $ekilde kontrol edilebilmesi için TAD’lar n birbirlerine mümkün oldu u kadar yak n yerle$tirilmesi gerekmektedir. Bu sayede TAD’lar, baz istasyonu ile do rudan ileti$im kurabilirler ancak ileti$imin enerji tüketimi aç s ndan maaliyeti artar. Bu problemi a$mak için Dekil 2’de gösterildi i gibi çok atlamal bir yap kullan l r. Telsiz alg lay c a larda yeralan tüm TAD’lar ayn miktarda enerjiye sahiptirler. Çok atlamal veri iletiminde baz istasyonuna yak n olan TAD’lar, di er TAD’lara göre daha fazla veri aktard klar için, enerjilerini daha çabuk tüketirler. Bu TAD’lar n enerjilerinin tükenmesi kendisine ba l tüm TAD’lar n da a dan kopmas na neden olur. 3.1. TAD’lar n Da. t lmas Uygulamalar n ihtiyaçlar na ve k s tlar na göre telsiz alg lay c a larda çe$itli da tma teknikleri kullan lmaktad r. Bu teknikler önceden planlama gerektiren belirleyici tarzda veya kendi kendine organize olan tarzda olmak üzere iki grupta toplanabilir. Örne in askeri uygulamalarda, telsiz alg lay c a n dü$man hatt n n arkas nda olu$turulabilmesi için uçak veya uzun mesafe at c lar kullan l rken, tar m uygulamalar nda ise TAD’lar el ile tek tek yerle$tirilirler. TAD’lar n rasgele da t ld , kendi kendine organize olan tekniklerde artan enerji tüketimi, baz istasyonlar n n optimum yerle$tirilmesinin önemini artt r r. TAD Bir atlama uzakl . nda TAD Baz stasyonu ekil 2: TAD’lar aras çok atlamal veri ileti$imi Ya$am süresini artt rmak için, baz istasyonuna kom$u olan TAD’lar n yükü mümkün oldu unca çok say da TAD aras nda payla$t r lmal d r. Bu payla$ m n sa lanmas baz istasyonlar n n TAD’lar n yerle$tirilmesi ile mümkündür. yo un oldu u noktalara 3.4. Rotalama Yap lan çal $man n temel hedefi birden fazla baz istasyonunun telsiz a ya$am süresini en uzun olmas n sa layacak $ekilde yerle$tirmektir. Bu sebeple telsiz alg lay c a larda kullan lan rotalama algoritmalar ndan bu çal $man n ihtiyac n kar$ layacak en k sa yol algoritmas tercih edilmi$tir. TAD’lar k adet baz istasyonundan biri ile ili$kilendirilmekte ve TAD ile ilgili baz istasyonu aras ndaki en k sa yol hesaplanmaktad r. gösterildi i gibi baz istasyonlar kom$ular aras nda en çok veri trafi ine sahip TAD’lara do ru kayd r l r. k-means Local+ algoritmas 3 a$amadan olu$maktad r. Bu a$amalar; k-means s n fland rmas , rotalaman n olu$turulmas ve baz istasyonlar n n yeniden yerle$tirilmesidir. Ilk a$amada k-means kümeleme algoritmas kullan larak baz istasyonlar n n ilk pozisyonlar belirlenir. k-means kümeleme algoritmas ile ilgili detayl bilgi Bölüm 3.3’te verilmi$tir. 3.5. TAD Enerji Modeli TAD’lar, çevresel verileri alg lamak, di er TAD ve/veya baz istasyonlar ile haberle$mek amac yla enerji harcarlar. Buna göre bir TAD’ n enerji modeli Denklem 1’deki gibi olu$turulabilir. Es çevresel verilerin alg lamas için harcanan enerjiyi, Er di er TAD ve/veya baz istasyonlar ndan veri almak için harcanan enerjiyi, Et ise veri yollamak için harcana enerjiyi göstermektedir. E = Es + Er + Et (1) Telsiz haberle$mesinde, veri gönderiminde kullan lan enerji miktar , gönderici ve al c aras ndaki mesafe ile do ru orant l d r ve bu ili$ki Denklem 2’de gösterilmi$tir. Bu sayede TAD’lar mesafeye ba l olarak veri göndermek için gerekli olan enerji miktar n dinamik olarak ayarlayabilirler. Et(d) = kdO (2) Veri alma i$leminde harcanan enerji miktar ise, al c ile gönderici aras ndaki mesafeden ba ms zd r ve sabit bir de er ile Denklem 3’te görüldü ü gibi ifade edilebilir. Er = P (3) Alg lama i$lemleri için gerekli olan enerji miktar , haberle$me için ihtiyaç duyulan enerji miktar na oranla çok daha dü$üktür. Bu yüzden hesaplamalarda ihmal edilmi$tir. 3.6. Ya am Süresinin Hesaplanmas Telsiz alg lay c a larda, TAD’lar ile baz istasyonu aras nda veri iletim modeli olarak sürekli model, olay tabanl model, sorgu tabanl model veya hibrit model kullan lmaktad r. Sürekli modelde, her TAD alg lama verisini periyodik olarak baz istasyonuna gönderir. Olay tabanl ve sorgu tabanl modellerde, TAD alg lama verisini bir olay veya sorgu sonucuna göre baz istasyonuna gönderir. Geli$tirdi imiz sistemde k-means Local+ algoritmas n n performans n test etmek amac yla sürekli veri iletim modeli seçilmi$tir. 4. k-means Local+ Telsiz alg lay c a larda enerji tüketiminin en çok veri iletiminde gerçekle$ti i dü$ünülürse (Bölüm 3.5) baz istasyonu ile kendisine kom$u olan TAD’lar aras ndaki mesafe azalt larak TAD’ n genel enerji tüketiminin azalmas ve ya$am süresinin uzamas sa lan r. k-means Local+ algoritmas nda, öncelikle k-means algoritmas kullan larak baz istasyonlar n n yerleri hesaplan r, daha sonra Dekil 3’te TAD Bir atlama uzakl . nda TAD Baz stasyonu Baz stasyonunun Yeni Yeri ekil 3: TAD’lar aras çok atlamal veri ileti$imi k-means Local+ algoritmas , rotalama algoritmalar ndan ba ms z olarak çal $maktad r; ancak kullan lan yönlendirme algoritmas n n sonucu baz istasyonlar n n yerle$imini do rudan etkileyecektir. Son a$amada rotalama algoritmas sonucunda elde edilen a yap s na göre her TAD taraf ndan aktar lacak olan veri miktar hesaplan r. Elde edilen veri miktarlar na göre baz istasyonlar n n pozisyonlar tekrar hesaplanarak, baz istasyonlar n n daha çok veri trafi ine sahip TAD’lara yak nla$t r lmas sa lanm $ olur. 5. Test Senaryolar k-means Local+ algoritmas n n ba$ar m n ölçülmesi için bir baz istasyonu yerle$tirme ve performans de erlendirme yaz l m olu$turulmu$tur. Bu yaz l m sayesinde TAD’lar n da t laca alan n özellikleri, baz istasyonu say s , TAD’lar n da t lma yöntemi ve TAD’lara ait batarya ve haberle$me karakteristikleri de i$tirilerek farkl senaryolar için a n ya$am süresi ölçülebilmektedir. Yap lan testlerde her TAD’ n 22100J [12] enerjiye sahip oldu u, sürekli veri modeline göre 64 byte uzunlu unda veri üretti i ve bu veriyi 250 kbps h z nda gönderdi i kabul edilmi$tir. Her TAD’ n en fazla 50 metrelik bir yar çaptaki TAD’lar ve/veya baz istasyonu ile haberle$ebildi i öngörülmü$ ve haberle$me için gerekli enerji ihtiyac Denklem 4’ e göre hesaplanm $t r. Denklem 4’teki k de eri 2.5 O de eri ise 2 olarak kabul edilmi$tir. 400 mt kenar uzunlu una sahip kare bir alanda, 100 TAD’den 800 TAD’a 100’erlik art mlarla de i$en TAD say s için farkl say da baz istasyonu kullan larak a ya$am süreleri hesaplanm $t r. Her TAD say s için 10 farkl da t m senaryosu olu$turulmu$ ve ç kan sonuçlar n ortalamas al narak ilgili TAD say s için ortalama a ya$am süresi elde edilmi$tir. Dekil 4 ve Dekil 5’te 400 ve 800 TAD say s için, baz istasyonu say s 1 ile 14 aras nda de i$tirilirken k-means ve k- means Local+ algoritmalar ile elde edilen ortalama a ya$am sürelerinin kar$ la$t r lmas verilmi$tir. 400 adet TAD 4500 A Ya am Süresi 4000 3500 3000 2500 2000 1500 1000 500 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Baz stasyonu Say s K-means K-means Local+ ekil 4: 400 adet TAD için a n ortalama ya$am süresi A Ya am Süresi 800 adet TAD 4000 3500 3000 2500 2000 1500 1000 500 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Baz stasyonu Say s K-means K-means Local+ ekil 5: 800 adet TAD için a n ortalama ya$am süresi Dekil 6 eri$ilemez alg lay c dü üm say s n n zamana göre de i$imini vermektedir. k-means Local+ kullan ld nda eri$ilemez alg lay c dü üm say s n n her zaman k-means algoritmas ndan daha az oldu u görülmektedir. Eri ilemez TAD Say s 700 600 500 400 300 200 100 0 0 200 400 600 800 1000 1200 1400 1600 1800 2000 A Ya am Süresi k-means 5 k-means 6 k-means 7 Local+ 5 Local+ 6 Local+ 7 ekil 6: Farkl say daki baz istasyonlar için eri$ilemez TAD say s Sonuç Bu çal $mada, telsiz alg lay c a larda birden fazla baz istasyonu yerle$tirme problemi üzerinde çal $ lm $ ve k-means algoritmas ndan daha iyi performansa sahip olan k-means Local+ algoritmas önerilmi$tir. Gerçekle$tirilen testlerin sonucunda; k-means Local+ algoritmas n n, a ömrünü kmeans algoritmas na göre %45’e kadar artt rabildi i, telsiz alg lay c a larda, optimum baz istasyonu say s n n TAD’lar n da l m yla yak ndan ili$kili oldu u ve baz istasyonu say s n n artt r lmas n n her zaman a n ömrünü artt rmad , fakat baz istasyonu say s artt kça elde edilen kazanç oran n n azald gözlemlenmi$tir. 6. Kaynakça [1] Oyman, I. and Ersoy, C., “Multiple Sink Network Design Problem in Large Scale Wireless Sensor Networks”, IEEE International Conference on Communications, 6: 3663-3667, 2004. [2] Mendis, C. and Guru, SM. And Halgamuge, S. and Fernando, S. “Optimized Sink node Path using Particle Swarm Optimization”, 20th International Conference on Advanced Information Networking and Applications, 2:5, 2006. [3] Savvides, A. and Park, H. and Srivastava, M. “The n-Hop Multilateration Primitive forNode Localization”, ACM Mobile Networks and Applications, 8: 443-451. [4] Kim, H. and Abdelhazer, T. and Kwon, W., “Minimumenergy asynchronous dissemination to mobile sinks in Wireless Sensor Network”, Sensys, 2003. [5] Akkaya, K. and Younis, M. and Youssef, W., “Positioning of Base Stations in Wireless Sensor Networks” IEEE Communications Magazine, 45(4): 96102 , 2007. [6] Bogdanov, A. and Maneva, E. and Riesenfeld, S. “Poweraware base station positioning for sensor networks”, 23th Annual Joint Conference of the IEEE Computer and Communications, 1, 2004. [7] Pan, J. and Cai, L. and Hou, YT. and Shi, Y. and Shen, SX. “Optimal Base-Station Locations in Two-Tired Wireless Sensor Networks”, IEEE Transactions on Mobile Computing, 4(5):458-473, 2005. [8] Hou, YT. and Shi, Y. and Sherali, HD. “Optimal BaseStation Selection for Anycast Routing in Wireless Sensor Networks”, IEEE Transactions on Vehicular Technology, 55(3): 813-821, 2006. [9] Efrat, A. and Har-Peled, S. and Mitchell, JSB. “Approximation Algorithms for Two Optimal Location Problems in Sensor Networks” 3rd International. Conf. Broadband Communications, Networks and Systems, ,2005. [10] Alpaydin, E., “Machine Learning”, The MIT Press, 2004. [11] Cheng, P. and Chuah, C. and Liu, X. “Energy-aware Node Placement in Wireless Sensor Networks”, IEEE GLOBECOM, 5:3210- 3214, 2004. [12] http://www.allaboutbatteries.com/Energy/tables.html [13] Akkaya, K. and Younis, M. “A survey on routing protocols for wireless sensor networks”, Ad Hoc Networks, 3:325-349, 2005. [14] Tilak, S. and Heinzelman, W. “A Taxonomy of Wireless Microsensor Network Models”, ACM Mobile Computing and Communications Review (MC2R), 2002.