Distributed Bluetooth Scatternet Formation based on Device
Transkript
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.