Distributed Bluetooth Scatternet Formation based on Device

Distributed Bluetooth Scatternet Formation based on Device

Aygıt ve Bağ Özelliklerine Dayalı
Dağıtık Bluetooth Multipikonet Formasyon Algoritması
Canan Pamuk ve Ezhan Karaşan
Elektrik ve Elektronik Mühendisliği
Bilkent Üniversitesi
Ankara, Türkiye
{canan, ezhan}@ee.bilkent.edu.tr
Özetçe
Bluetooth, kısa mesafelerde gelecek vadeden bir tasarsız ağ
teknolojisi olduğundan, son yıllarda oldukça popülerlik
kazanmıştır.
Bluetooth pikonetlerinin oluşumu ve işleyişi Bluetooth
spesifikasyonlarında belirlenmiş olmasına rağmen, çok sayıda
aygıtın birbirine bağlanıp multipikonet oluşturmalarının ve
multipikonet işleyişinin henüz bir standardı yoktur ve bunlar
çözülmesi gereken problemlerdir [1].
Çalışmamızda, aygıt ve bağ özelliklerini kullanarak
multipikonet oluşumunu sağlayan bir algoritma geliştirdik.
SF-DeviL (Scatternet Formation algorithm based on Device
and Link characteristics) algoritması, aygıt sınıfı ve alınan
sinyal gücü bilgilerini kullanarak, düğümlerin enerji
verimliliğini arttırıyor.
1. Giriş
Bluetooth kablo bağlantısını ortada kaldıran kısa mesafe
Radyo Frekansı(RF) teknolojisinin adıdır. Bluetooth çipi,
cihazların birbirleri ile görüş doğrultusu dışında bile olsalar
haberleşmelerine olanak sağlar. Bluetooth teknolojisi 2.4 GHz
ISM frekans bandında, hızlı frekans hoplaması yayılı
spektrumuyla (FHSS) çalışmakta olup, ses ve veri iletimi
yapabilmektedir.721 Kbps'a kadar veri aktarabilen Bluetooth
destekli cihazların etkin olduğu mesafe yaklaşık 10 ya da 100
metredir.
Bluetooth’un en küçük çalışma birimi pikonettir. Bir
pikonet, bir ana (master) ve en fazla yedi köle (slave) görevini
üstlenen cihazlardan oluşur. Her pikonetin kendine özgü
frekans hoplama dizisi vardır ve bu nedenle ayni yer ve
zamanda birden fazla pikonet bulunabilir. Birden fazla
pikonetin birbirine bağlanmasıyla oluşan ağa multipikonet
(scatternet) ve pikonetler arası iletişimi üstlenen düğümlere
köprü (bridge) adı verilir.
Multipikonet oluşturma problemi, ana, köle ve köprü
rollerinin
aygıtlara
atanmasıdır.
Multipikonet
formasyonundaki temel problemler şöyledir:
•
Aygıtlar ilk kullanıma açıldıklarında, komşuları hakkında
bir bilgiye sahip değildir. Bu nedenle multipikonet
formasyonunda dağıtık bir yaklaşım kullanılmalıdır.
•
•
•
Aygıtlar devingendir. Öyleyse, düğüm eklenmelerini ve
ayrılmalarını idare edebilmek için, multipikonet dinamik
bir biçimde oluşturulmalıdır.
Bluetooth modülü genellikle pille beslenen aygıtlarda
kullanıldığından enerji verimliliği sağlanmalıdır.
Multipikonet
oluşumu
makul
bir
sürede
tamamlanmalıdır.
2. İlgili Çalışmalar
Bluetooth Topoloji Oluşturma Protokolü (BTCP) [2] ve LMS
[3], önerilen dağıtık multipikonet formasyon yöntemleri olup
bu algoritmalarda bütün düğümlerin birbirlerini duyabildikleri
varsayılmıştır.
[4], [5] and [6] daha geniş ölçüde ağlar için önerilmiş
multipikonet formasyon protokolleridır. Ağaç topolojisi
oluşturan bu protokollerin temel zayıflığı, kök ve köke yakın
düğümlerin aşırı yüklenmeye ve dolayısıyla bu düğümlerin
pillerinin tükenmesine karşı dayanıksız olmasıdır. SF-DeviL
ile, ağaçtaki yerlerine belli bir hiyerarşiyle yerleştirilen
düğümler aşırı yüklenme ve pil tüketimine karşı daha
dayanıklıdır.
Bu güne kadar önerilen hiçbir multipikonet formasyon
algoritması, enerji verimliliğini ele almamıştır. SF-DeviL’de
aygıtların türü göz önüne alınarak, güç kontrolü yapılıp yakın
aygıtlar birbirine bağlanarak enerji verimliliği sağlanmaktadır.
3. SF-DeviL Algoritmasının Temelleri
3.1. Aygıt Derecesi (AD)
Bluetooth modülünün konakladığı aygıtın sınıfı, multipikonet
formasyonunda kullanılabilir. Bir aygıtın pil kapasitesi ve
trafik üretim oranı aygıt sınıfı bilgisinden tahmin edilebilir.
Yüksek pil kapasitesine ve yüksek trafik üretim oranına sahip
bir aygıtın ana ya da köprü düğümü seçilmesiyle oluşturulan
multipikonet, Şekil 1’de görüldüğü üzere, daha kararlı ve güç
açısından daha verimli olacaktır.
Aygıt sınıfı bilgisi, Bluetooth modülünce bilinmektedir.
Ayrıca bağ oluşturma esnasında, frekans hoplama
eşzamanlama (FHS) paketinin aygıt/servis alanıyla, komşu
aygıtlarla da değiş tokuş edilmektedir [7].
oluşturulmuş olur ve bağlanmamış kök düğümleri
multipikoneti oluşturmak amacıyla birbirlerini ararlar.
SF-DeviL, her aygıt X’in aşağıdaki ASIL procedürüyle
başlattığı dağıtık çalışan bir algoritmadır:
Şekil 1: Aygıt özelliklerine
(multipikonet) formasyonu.
dayalı
pikonet
SF-DeviL her düğüme bir Aygıt Derecesi (AD) atar. AD,
aygıtın sınıfı ve pil seviyesi bilgileri kullanarak hesaplanır.
AD = wp*AygıtPilDerecesi*PilSeviyesi
+ wt*TrafikÜretimOranı
(1)
(0 ≤ wp , wt ≤ 1)
wp ve wt , güç ve trafik için ağırlıklardır. AygıtPilDerecesi
aygıtın pil kapasitesini, PilSeviyesi kullanılabilir pil kesimini
belirtir. TrafikÜretimOranı ise aygıtın üreteceği tahmini
ortalama
trafik
oranıdır.
AygıtPilDerecesi
ve
TrafikÜretimOranı aygıt sınıfı bilgisinden elde edilir.
Yüksek kapasiteli ve/veya daha dolu pillere sahip, ve
yüksek trafik üreten aygıtların daha yüksek bir AD’leri vardır.
3.2. Alınan Sinyal Gücü Derecesi (ASGD)
Bluetooth modüllerinin güç kontrol özellikleri vardır [1].
Birbirinden daha güçlü sinyaller alan aygıtların bağlanması
durumunda (Şekil 2), sinyal iletmek için daha az güç harcanır.
Böylece multipikonetin ömrü uzar ve karışma azalır.
Şekil 2: Bağ
formasyonu.
özelliklerine
dayalı
multipikonet
Bluetooth modülü alınan sinyalin gücünü ölçme özelliğine
sahiptir (RSSI) [1]. SF-DeviL’de her aygıt, komşularından
paket aldıkça alınan sinyalin gücünü ölçerek her komşusuna
bir AlınanSinyalGücüDerecesi (ASGD) atar. Komşulara
atanan ASGD değerleri, her aygıtın bağlanacağı en yakın
komşuyu seçmek için kullanılır. ASGD sinyal gücüne göre
nicemlenmiştir.
4. SF-DeviL Algoritması
Çalıştırılan bütün aygıtlar ASIL prosedürünü başlatırlar. ASIL
procedürüne son verildiğinde yol atama çizelgeleri
ASIL:
1
Çalıştırılan X, AD(X)’i hesaplar.
2
yap {
3
x = rastgele bir sayı
4
eğer x çift ise
5
keşif soruşturmasına başla
6
yoksa
7
keşif dinlemesine başla
8
Bir Y aygıtı bulana dek keşif sorgulaması ve
dinlemesi arasında almaş
9
Y.AD(Y).ASGD(Y)’i, komşu_listesi(X)’e ekle
10
Eğer (Y==EnİyiAna(X’in eski anası,Y) )
11
Y’ye bağlan
12
Ana/köle değişimi yap
13
}devam et eğer (zamanaşımı dolmamışsa)
Birinci satırda, çalıştırılan X, kendi aygıt sınıfını ve pil
seviyesi göstergesini kullanarak AD’sini hesaplar (1). Her
aygıt sınıfına ait AygıtPilDerecesi and TrafikÜretimOranı
Bluetooth modülünün hafızasına kaydedilen bir tablodan elde
edilir.
Satır 3-9, Bluetooth spesifikasyonlarında yer alan
aygıtların birbirini keşfetmesi için gerekli işlemleri
kapsamaktadır. Komşularının adresini bilmeyen bir aygıt ya
keşif soruşturması (inquiry) yapar. Karşıdaki aygıt ise keşif
soruşturması yapan aygıta cevap verebilmek için keşif
dinlemesi (inquiry scan) yapar. Gerekli komşu adresi elde
edildiğinde, adresi belirli komşuya bağlanmak için bağlanma
soruşturması (page) yapılır. Bu durumda karşıdaki aygıt da
sadece kendi adresini içeren paketleri dinlemek suretiyle
bağlanma dinlemesi (page scan) yapar.
9.satır ile, X, komşusuna ait bilgileri kendi komşu_listesine
ekleyerek bulduğu komşuların bir listesini yapar. X’in komşu
listesinde
Y’ye
ait
bilginin
saklanma
biçimi
“Y.AD(Y).ASGD(Y)” şeklindedir, yani Y’nin Bluetooth aygıt
adresi, Y’nin AD’si ve Y’den algılanan sinyalin gücü, bir
başka deyişle, Y’nin X’e uzaklığı. Satır 10’da yer alan
EnİyiAna prosedürü, yeni keşfedilen Y’nin X için daha iyi bir
ana olup olmadığını bulmaktadır. Y daha iyi bir ana olduğu
takdirde X, Y’ye bağlanmaktadır.
Bağlanma talebinde bulunan aygıtın otomatik olarak ana
olması dolayısıyla [1], X Y’ye bağlanma talebinde
bulunduğundan, X, Y’nin anası olur. Bu nedenle 12.satırda X
ve Y rolleri değiştirir. Böylece Y, X’in anası olur. Bu işlemin
nedeni, ağaç topolojisi oluştuğunda bütün yaprakların köle, ara
düğümlerin köprü ve kök düğümün ana rolünde çalışmasını
sağlamaktır.
EnİyiAna(önceki_ana, komşu) prosedürü, X için hangi
aygıtın daha iyi bir ana olacağını belirlemek için kullanılır:
EnİyiAna(önceki_ana, komşu)
1 eğer (AD(komşu) >AD(X))
2
//X’in komşusu kendisinden daha büyük AD’ye
3
//sahipse X’in anası seçilebilir.
4
eğer (önceki_ana== φ )
5
//X’in henüz bir anası yok
6
komşu’yu seç
7
yoksa eğer (ASGD(komşu)==ÇokGüçlüSinyal)
5.
Simulasyon Sonuçları
C++’a dayalı ve Bluetooth spesifikasyonlarına uygun bir
simulatör geliştirildi [1]. SF-DeviL ve LMS algoritmalarının
performansları karşılaştırıldı. Multipikonet formasyon
gecikmesi, pikonet sayısı, ağ çapı, düğümler arası ortalama
uzaklık ve ilk aygıt pilinin tükendiği zaman performans
ölçütleri olarak kullanıldı.
Farklı aygıt sınıflarından seçilen düğümler 10x10m alana
rasgele dağıtıldı. Aygıtların tamamının pille çalıştığı
düşünüldü ve hepsine tamamen dolu piller atandı.
ASIL prosedürü sırasında henüz komşu aygıtların keşfi
tamamlanmadığından güç kontrolü yapılmıyor. ASIL
prosedürü sonrasında güç kontrolü yapılıp alınan güç
-60dBm’de sabitlendi. Aşağıdaki yol kaybı modeli kullanıldı:
PL(d)=PL(d0)+10.γ.log(d/d0) ,
PL(d0=1m)=-30dBm ve γ=2.5 alındı. Güç kontrolüyle, verici
gücü 0dBm’den –30dBm’e kadar, 2dB’lik basamaklarla [1]’e
uygun olarak değiştirildi.
Ppaket = Pstandby + Px ,
Bu denklemde Px , vericiler için Pverici , alıcılar için Palıcı ve ara
düğümler için Paradüğüm şeklindedir. Pstandby ise standby
modunda tüketilen güçtür. Bu değerler arası ilişki şu şekilde
kabul edilmiştir:
Pstandby = Palıcı =Pverici /316
Paradüğüm = Palıcı + Pverici
Her aygıtın TrafikÜretimOranı’na orantılı rasgele trafik
üretilmiştir. 300 Kbps’lık ortalama trafik varsayılarak, Şekil
3’te, ilk aygıt pilinin tükendiği zaman araştırıldı.
AD’si büyük olan aygıtların ana ve köprü olarak
atanmaları ve yakın aygıtların birbirine bağlanması nedeniyle
SF-DeviL’le oluşturulan multipikonetler, ilk aygıt pili
tükeninceye kadar LMS’ten daha çok trafik taşıyor. Açıkça
görülüyor ki SF-DeviL, gücü LMS’ten daha verimli
kullanıyor.
İlk Pil Tükenme Zamanı (saat)
Eğer X belli bir zamanaşımına (keşifZA) kadar yeni bir
aygıt keşfedemezse, ASIL prosedürünü durdurur. ASIL
prosedürü tamamlandığında, X kendine ya bir ana düğüm
bulup onun kölesi olmuştur ya da kendisini kök düğüm ilan
etmiştir.
ASIL prosedürü sırasında, her yeni bağlantı sonucunda yol
atama çizelgeleri yenilenir; koparılan bağların girişleri yol
atama çizelgelerinden silinirken yeni bağlar için girişler
eklenir. Bir düğümün yol atama çizelgesinde, o düğümün
bütün torunları, her toruna kaç bağla, hangi düğüm üzerinden
bağlanıldığı bilgileri bulunur.
Kendisini kök düğüm ilan eden bir aygıt, yol atama
çizelgesine bakarak AD’si kendisine eşit ve büyük olan
aygıtları tespit eder ve onları bağlantı için soruşturmaya (page)
başlar. Ayrık ağaçların kök düğümleri bağlanma soruşturması
ve dinlemesi (page / page scan) modlarında almaşarak
kendilerine uygun en iyi anaya bağlanmak suretiyle
multipikoneti oluştururlar. EnİyiAna prosedürünü birinci
satırda AD(komşu) >= AD(X) farklılığıyla çalıştırırlar.
AD(X’in anası) ve AD(X) birbirine eşit olduğu taktirde,
hangisinin kölesi çoksa o diğerinin anası olur.
Sonuçta oluşan ağaç topolojisinde, en büyük AD’ye sahip
aygıtlar kök düğümü ve çevresinde, en küçük AD’ye sahip
aygıtlar da ağacın yapraklarında konumlanmış olur. Böylece
yüksek trafikleri idare etmek zorunda kalan kök ve ara
düğümlere, pili daha güçlü ve/veya daha çok trafik
üretebilecek aygıtlar yerleştirilmiş olur.
Her aygıtın PilSeviyesi AygıtPilDerecesi’yle ters orantılı
olarak azaltıldı. Paket başına harcanan güç aşağıdaki
denklemle ifade edildi:
SF-DeviL
25
LMS
20
15
10
5
0
10
20
30
40
50
Düğüm Sayısı
Şekil 3: İlk aygıt pilinin tükendiği zaman
9,00
8,00
Ortalama Düğümlerarası
Uzaklık (m)
8
//eğer X’in komşusu X’e çok yakınsa
9
//X’in anası olur
10
komşu’yu seç
11
yoksa eğer ( [AD(komşu)+ASGD(komşu)] >
12
[AD(önceki_ana)+ASGD(önceki_ana)])
13
komşu’yu seç
14
yoksa
15
//X’in komşusu X’in önceki anasından
16
//daha iyi bir ana değil
17
önceki_ana’yı seç
18 yoksa
19
önceki_ana’yı seç
SF-DeviL
7,00
LMS
6,00
5,00
4,00
3,00
2,00
1,00
0,00
10
20
30
40
50
Düğüm Sayısı
Şekil 4: Düğümler arası ortalama uzaklık
SF-DeviL her aygıtı en yakınındaki AD’si büyük olan
aygıtla bağlanmaya zorlamaktadır. Bu nedenle, SF-DeviL’de
alan sabit tutulduğundan, Şekil 4’te görüldüğü gibi, aygıtlar
arsı ortalama uzaklık artan aygıt sayısıyla azalmaktadır. Ancak
LMS’te düğümlerin konumlarıyla ilgili bir parametre
olmadığından bu değer yüksektir ve düğüm sayısından
bağımsızdır.
SF-DeviL ve LMS’in pikonet sayıları ve ağ çapları (iki
aygıt arası maximum bağ sayısı) Şekil 5 ve 6’da görüldüğü
gibi birbirine yakındır.
18,00
Pikonet Sayısı
16,00
SF-DeviL
LMS
14,00
12,00
10,00
8,00
6,00
4,00
2,00
0,00
10
20
30
40
50
Düğüm Sayısı
Şekil 5: Pikonet sayısı
Ağ Çapı
10,00
9,00
8,00
7,00
6,00
5,00
4,00
3,00
2,00
1,00
0,00
SF-DeviL
LMS
10
20
30
40
50
Düğüm Sayısı
Şekil 6: Ağ çapı
Şekil 7’de SF-DeviL için zamanaşımını içermeyen
multipikonet formasyon gecikmesi verilmiştir. Bu değerlere
keşifZA=1dak eklendiğinde asıl formasyon gecikmesi elde
edilmiş olur. SF-DeviL’de, LMS ile karşılaştırıldığında büyük
bir gecikmeyle multipikonet oluşturuluyor. Ancak düğüm
sayısı küçük olduğunda gecikme idare eder düzeydedir.
120,00
SF-DeviL
Formasyon
Gecikmesi(saniye)
100,00
LMS
80,00
60,00
40,00
20,00
0,00
10
20
30
40
Düğüm Sayısı
Şekil 7: Multipikonet formasyon gecikmesi
50
6. Sonuçlar ve Yorumlar
SF_DeviL, aygıt ve bağ özelliklerini kullanarak enerji
verimliliğini
arttıran
Bluetooth
multipikonetleri
oluşturmaktadır. Spesifikasyonlara uyumlu olduğundan
günümüz Bluetooth teknolojisine uygulanabilir [1]. Dağıtık
bir biçimde çalışmaktadır ve güçlü düğümlerin kök ya da
köprü olduğu bir ağaç topolojisi oluşturmaktadır.
Simulasyonlar göstermiştir ki, multipikonet formasyonu
sırasında aygıt ve bağ özelliklerinin kullanılması, multipikonet
işleyişi sırasında enerji verimliliğini sağlamıştır. SF-DeviL
makul pikonet sayısına, ağ çapına ve formasyon gecikmesine
sahip multipikonetler oluşturmaktadır.
SF-DeviL’in formasyon gecikmesi aygıtların komşu
listelerinin büyüklüğüne bağlıdır. Keşif için belirlenen
zamanaşımının azaltılmasıyla daha az sayıda komşu
keşfedilerek multipikonet oluşturulmasının ve Bluetooth
spesifikasyonlarında belirtilen bağlantı kurma prosedürünün
hızlandırılması üzerinde yapılan çalışmaların SF-DeviL’in
daha kısa sürede tamamlanmasına yardımcı olacağını
düşünülmektedir [8].
SF-DeviL’deki ASIL prosedürünün periyodik olarak
çalıştırılmasıyla, azalan pil seviyeleriyle aygıtların AD’leri
değişecektir ve böylece pili azalan aygıtlar ağacın
yapraklarına yerleştirilecektir. Böylece multipikonetin
ömrünün uzaması beklenmektedir. Ayrıca bu şekilde SFDeviL, aygıt eklenmesi ve silinmesini de idare edecektir.
8. Kaynakça
[1] Bluetooth SIG, “Specification of the Bluetooth System”,
Version 1.1, http://www.bluetooth.com
[son erişim 14/05/03]
[2] Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas,
Richard LaMaire. “Proximity Awareness and Ad Hoc
Network Establishment in Bluetooth”, Institute of Systems
Research, University of Maryland Technical Report
[3] Ching Law, Amar K. Mehta, Kai-Yeung Siu, “A New
Bluetooth Scatternet Formation Protocol”, ACM Mobile
Networks and Applications Journal, 2002
[4] Godfrey Tan, Allen Miu, John Guttag, Hari Balakrishnan,
“Forming Scatternets from Bluetooth Personal Area
Networks” MIT Technical Report, 2001
[5] Gergely V.Zaruba, Stefano Basagni, Imrich Chlamtac.
“Bluetrees-Scatternet Formation to Enable Bluetooth Based
Ad Hoc Networks” In Proceedings of IEEE International
Conference on Communications, pages 273–277, 2001.
[6] Zhifang Wang, Robert J. Thomas, and Zygmunt Haas,
“Bluenet – A New Scatternet Formation Scheme” In
Proceedings of the 35th Annual Hawaii International
Conference on System Sciences, January 2002.
[7] Bluetooth SIG, “Assigned numbers- Bluetooth baseband,“
http://www.bluetoothsig.org/assigned-numbers/baseband.htm
[son erişim 14/05/03]
[8] Yelena Gelzayd, “An Alternate Connection Establishment
Scheme in the Bluetooth System”, M.S Thesis submitted to
Polytechnic University, 2002.