Multiple Base Station Placement with k-means Local+ - ISL

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.