Kablosuz Sensör Ağında Düğüm Yerelleştirme Algoritmasının Analizi
Shi Wenjin, Zhang Jing, Li Guandi, Zeng Jianmei
(Elektronik Bilgi ve Otomasyon Okulu, Chongqing Teknoloji Üniversitesi, Chongqing 400054)
Düğüm konumlandırma, kablosuz sensör ağlarının temel teknolojilerinden biridir ve askeri ve sivil uygulamalarda yaygın olarak kullanılmaktadır. Kablosuz sensör ağı konumlandırma teknolojisinin yurtiçi ve yurtdışındaki mevcut durumu tartışıldı ve çapa düğümü / çapa olmayan düğüm konumlandırma, merkezi / dağıtılmış konumlandırma, aralıklı / aralıksız konumlandırma algoritmalarından kablosuz sensör ağ düğümü konumlandırma teknolojisi üzerine araştırma ve araştırma yaptı. Konumlandırma doğruluğu, ölçek ve güç tüketimi gibi farklı düğüm konumlandırma perspektiflerinden çeşitli algoritmaları açıkladı ve karşılaştırdı. Odak noktası, RSSI tabanlı ağırlık merkezi konumlandırma algoritmasıdır ve simülasyon sonuçları, konumlandırma doğruluğunun önemli ölçüde iyileştirildiğini göstermektedir.
Kablosuz sensör ağı; düğüm konumlandırma; değişen / aralıksız
Chongqing Belediye Eğitim Komisyonu Bilim ve Teknoloji Araştırma Projesi (KJ1500917) Kablosuz Sensör Ağı (Kablosuz Senor Ağı, WSN), veri toplama yetenekleri, kablosuz iletişim aktarım veri yetenekleri ve veri işleme yetenekleri olan çok sayıda mikro sensör düğümünden oluşan bir ağdır [1]. İzlenen alana binlerce mikro sensör düğümü yerleştirilir ve düğümler kablosuz bir bağlantı iletim ağı oluşturmak için birbirleriyle iletişim kurar. Harici değişiklikleri algılamak veya izlemek için düğümlerin yardımıyla, toplanan bilgiler önceden işlenir ve veriler, baz istasyonu aracılığıyla kullanıcıya gönderilir.
WSN, hedef algılama ve izleme, hedef izleme ve konumlandırma gibi ilgili alanlarda yaygın olarak kullanılmak üzere bilgi toplama ve işleme teknolojisini kullanır. Örneğin, askeri soruşturma, ekolojik çevre izleme, hedef konumlandırma, hedef izleme, özel hastaların izlenmesi ve kurtarılması, konum izleme ve küçük çocukların kurtarılması vb. Kablosuz sensör ağının hedef konum tanıma, izleme veya hedef konumlandırma, dağıtım alanındaki düğümlerin fiziksel koordinatları aracılığıyla GPS uydu konumlandırmasına benzer bir kablosuz sensör ağ haritasının oluşturulmasını ifade eder [2].
WSN'de bir düğüm, etrafındaki komşu düğümlere bilgi gönderir ve kendi düğümünün konumunu belirlemelidir. Ağdaki geniş dağılım ve geniş ölçekli düğümler nedeniyle, düğümlerin konumunun merkezi bir baz istasyonu aracılığıyla sorgulanması kısa sürede tamamlanamaz. WSN'deki sensör düğümlerinin donanım yapılandırması düşüktür ve geleneksel GPS, yüksek kullanıcı maliyetleri nedeniyle WSN konumlandırma uygulamaları için uygun değildir [3]. Bu nedenle, düğümün gönderilen verilere kendi koordinat bilgilerini dahil etmesi gerekir. Ek olarak, WSN'de düğüm konumlandırma, konumlandırma doğruluğunu, düğüm boyutunu, hata toleransını ve sağlamlığı ve enerji tüketimini içerir. Dengeli konumlandırma doğruluğu, kablosuz sensör ağ konumlandırmasının anahtarıdır [4]. Pek çok konumlandırma teknolojisi türü vardır ve bu makale çapa düğümü / çapa olmayan düğüm, merkezi / dağıtılmış, değişen / aralıksız düğüm hakkında ayrıntılı bilgi vermektedir.
1.1 Çapa düğümü algoritması / çapa olmayan düğüm algoritması
Çapa düğümü konumlandırma yöntemi, bağlantı düğümünü referans düğümü olarak kullanır. İlk önce bilinmeyen düğüm ile bağlantı düğümü arasındaki mesafeyi tahmin edin ve bilinmeyen düğümün koordinatlarını başlatmak için farklı gereksinimleri olan operatörleri seçin ve son olarak ilk bilinmeyen düğümün konumunu optimize edin. Çapa düğümlerinin yoğunluğu ne kadar yüksek ve referans düğümleri ne kadar fazlaysa, konumlandırma o kadar doğru olur. Ancak düğüm sayısının artması nedeniyle sistem maliyeti artacaktır.
Ankrajsız düğüm algoritmasının bir eşleme oluşturması ve düğümler arasındaki eşleme ilişkisi aracılığıyla ölçülen düğümler arasındaki mesafeyi tahmin etmesi gerekir. Farklı haritalama ilişkilerinin farklı hassasiyetleri olacaktır. Bazen eşleme ilişkisi döndürme, çevirme, çevirme vb. İle oluşturulur. NISSanka [5] tarafından önerilen algoritma, çapa düğümleri olmayan bir konumlandırmadır, koordinat sistemindeki her düğümün koordinatlarını elde etmek için çoklu atlama yoluyla bir eşleme ilişkisi kurar ve son olarak yinelemeli optimizasyon için kütle-yay modelini kullanır.
1.2 Merkezi algoritma ve dağıtılmış algoritma
Merkezi konumlandırma algoritması: Konumlandırma bilgileri bir merkezi baz istasyonuna iletilir ve ardından konumlandırma hesaplaması gerçekleştirilir. Merkezi bilgi işlem genel durumdan başlar ve hesaplama ve depolama miktarı neredeyse sınırsızdır ve gerçek zamanlı konumlandırmayı gerçekleştirir. Hesaplamayı tamamlamak için yalnızca bir baz istasyonu olduğundan, büyük bir iletişim ve depolama tüketimine yol açar ve sonunda elektrik enerjisinin tükenmesine yol açar, bu da uzun vadeli gerçek zamanlı konumlandırma elde etmeyi imkansız hale getirir.
Dağıtılmış konumlandırma algoritması: Düğümlerin konum koordinatlarını hesaplamak ve tahmin etmek için düğümler arasındaki iletişim düğümlerini kullanan, merkezi konumlandırma algoritmasına karşılık gelen bir algoritma. Tablo 1, merkezi ve dağıtılmış konumlandırma algoritmaları arasındaki karşılaştırmayı göstermektedir.
1.3 Değişen / aralıksız konumlandırma
1.3.1 Değişen teknolojiye dayalı konumlandırma algoritması
Bu tür konumlandırma algoritması, düğümler arasındaki mesafeyi veya açıyı ölçerek konumlandırma gerçekleştirir. Düğümler arasındaki mesafe sensörler tarafından tahmin edilir. Aralık teknolojisine dayanan yaygın konumlandırma algoritmaları arasında Alınan Sinyal Gücü Göstergesi (RSSI), Varış Zamanı (TOA) ve Varış Açısı (Varış Açısı) bulunur. AOA), sinyal iletiminin zaman farkına dayalı bir yöntemdir (Varış Zaman Farkı, TDOA).
(1) Alınan sinyal gücü algoritması (RSSI): Bu yöntem, alınan sinyal enerji gücüne (RSSI) göre mesafeyi belirler ve yüksek iletişim kanalı parametreleri gerektirir. Bilinen sinyal iletim gücüne ve düğümün aldığı sinyal gücüne göre düğümler arasındaki mesafe ölçülebilir. A'dan B'ye düğümlerin sinyal gücü için özel formül aşağıdaki gibidir:
Pr, B düğümünün alınan sinyal gücü olduğunda, Pt gönderme gücü, Gt ve Gr sırasıyla A ve B'nin anten kazançları, dalga boyu, R mesafe ve L kayıp faktörüdür. Sinyalin yayılması sırasında mesafenin ve engellerin etkisine bağlı olarak, sinyalin güç yoğunluğu azalacak ve bu da doğruluğu dolaylı olarak etkiler. Bu nedenle, kısa mesafeli iletişim için iyi bir doğruluk elde edilebilir.
(2) Sinyalin varma zamanına (TOA) dayalı yöntem: TOA, TOF (Uçuş Süresi) olarak da adlandırılır. Bu yöntemin dayanağı, düğümler arasında saat senkronizasyonudur Mobil terminal, ölçüm sinyallerini baz istasyonuna iletir ve mobil terminalin konumlandırılmasını gerçekleştirmek için özel algoritma hesaplamaları uygular. Mesafe aşağıdaki formülle hesaplanabilir:
D düğümler arasındaki mesafe, c yayılma hızı ve t zaman aralığıdır.
(3) Sinyalin varış açısına dayalı yöntem (AOA): AOA, düğümün konum bilgisini elde etmek ve son olarak konumlandırmayı tamamlamak için verici ve alıcının açısını ölçmeyi ifade eder. Ölçüm açısı, düğüme takılı anten dizisi aracılığıyla uygun üçgenleme algoritması seçilerek elde edilir. AOA yönteminin alıcı ve verici uçlarda anten dizileri kurması gerektiğinden, maliyet ve enerji tüketimi sorunları buna göre artacaktır, bu nedenle AOA'nın pratikliği zayıftır.
(4) Sinyal iletim zaman farkına (TDOA) dayalı yöntem: TDOA yöntemi, aynı hedefe veya farklı hedeflere ulaşan iki dalga arasındaki zaman aralığına dayalı olarak mesafeyi ölçer. Düğümün uzaklık formülü aşağıdaki gibidir:
Bunlar arasında, d düğümler arasındaki mesafedir, t alma zaman aralığıdır, S = (C1 × C2) / (C1 C2), C1 ve C2 iki dalganın yayılma hızlarıdır.
Farklı aralıklandırma yöntemleri için, konumlandırma algoritmalarının doğruluk gereksinimlerine göre seçilmesi gerekir Tablo 2, farklı konumlandırma algoritmalarının doğruluk karşılaştırmasını gösterir.
1.3.2 Teknolojiyi değiştirmeyen algoritmalar
Bu tür bir algoritmanın, düğümler arasındaki iletişim mesafesine dayalı olarak konumlandırılmasına gerek yoktur Bilgi, çok sekmeli bir şekilde gönderilebildiğinden, iki düğüm arasındaki iletişim mesafesi, sekme sayısı bilgisinin işlenmesiyle tahmin edilir ve ardından bilinmeyen düğümün koordinat pozisyonu, algoritmaya göre elde edilir. Bu algoritma aralık gerektirmez, avantajları düşük güç tüketimi ve düşük maliyettir, ancak dezavantajı konumlandırma doğruluğunun yüksek olmamasıdır. Yaygın yöntemler arasında DV-Hop [6] ve Centroid Location (CL) bulunur.
(1) DV-Hop: DV-Hop algoritması, bir mesafe vektörüne bağlı olarak atlama sayısını hesaplamak için bir algoritmadır. DV-Hop algoritması genellikle üç adıma bölünür: (1) Düğümler arasındaki minimum atlama sayısını hesaplayın; (2) Her bağlantı düğümü kendi ortalama sıçrama mesafesini hesaplar; (3) Üç taraflı yöntem ve maksimum olasılık yöntemi aracılığıyla , En küçük kareler yöntemi [7] vb. Bilinmeyen düğümlerin koordinatlarını tahmin eder.
(2) Centroid algoritması (CL): Centroid algoritması, ağın bağlanabilirliğine dayanır, çapa düğümlerini geometrik merkez olarak bilinmeyen düğümün etrafına alır ve çapa düğümünün koordinat bilgilerini her döngüde komşu düğümlere gönderir ve son olarak bilinmeyen düğümün bir poligon olduğu belirlenir. Bilinmeyen düğümlerin konumunu tahmin etmek için göreli geometrik ağırlık merkezleri. Bilinmeyen düğüme bağlı çapa düğümünün koordinatlarının (x1, y1) (x2, y2) ... (xn, yn) olduğunu, ardından n çapa düğümünden oluşan n-1 yan çokgenin ağırlık merkezinin (x, y) olduğunu varsayalım:
Ağırlık merkezi konum algoritması, ağırlıklı ağırlık merkezi algoritmasından ve üç taraflı ölçüm yönteminden [8] daha basittir, ancak konum hatası oranı yüksektir.
RSSI tabanlı 2 Centroid konumlandırma algoritması
Geleneksel ağırlık merkezi konumlandırma algoritması basit ve uygulanabilirdir, ancak konumlandırma doğruluğu yüksek değildir ve hedef genellikle bulunmaz. Konumlandırma doğruluğunu iyileştirmek için RSSI'ye dayalı bir centroid konumlandırma algoritması önerilmiş ve centroid algoritması RSSI ile birleştirilmiştir RSSI'nin sinyal gücünü iletim mesafesine dönüştürerek konumlandırma doğruluğu iyileştirilebilir. Yani, bilgiyi aldıktan sonra komşu düğüm, çapa düğümünün RSSI değerini kaydeder, çemberin merkezi olarak çapa düğümüyle iletim mesafesini hesaplar ve yarıçap olarak iletim mesafesi ile tüm dairelerin kesişme düğümlerini kaydeder. Kesişme noktası için centroid algoritması kullanılarak bilinmeyen düğüm koordinatları tahmin edilebilir. Şekil 1'de gösterildiği gibi, A, B ve C bağlantı düğümleridir ve bilinmeyen düğüm P1, O1O2O3 üçgeninin içine düşmelidir. Bu algoritma ayrıca simüle edilmiş ve doğrulanmıştır.
3 Simülasyon doğrulama
Deney ortamı simülasyon yazılımının MATLAB2010b versiyonunu kullanır. 100 mx100 m'lik bir alanda, 30 bilinmeyen düğüm rastgele dağıtılır ve ağırlık merkezi konumlandırma algoritmasını, RSSI konumlandırma algoritmasını ve RSSI centroid konumlandırma algoritmasının hatasını karşılaştırmak için ortalama hata değeri alınır. Simülasyon sonuçları Şekil 2'de gösterilmektedir.
Şekil 2'de, katı nokta çapa düğümüdür, yıldız işareti bilinmeyen düğümdür, daire algoritmanın tahmini konumudur ve çizgi, konumlandırma hatasıdır. Sonuçlar, centroid algoritmasının ve RSSI konumlandırma algoritmasının, bilinmeyen düğümün konumunu tahmin etmede genel özelliklere sahip olduğunu, RSSI centroid konumlandırma algoritmasına dayalı bilinmeyen düğümün konumlandırma etkisinin önemli ölçüde iyileştirildiğini göstermektedir.
İletişim yarıçapının değiştirilmesi, farklı iletişim yarıçapları altında RSSI tabanlı centroid ve centroid konumlandırma algoritmaları arasındaki hata karşılaştırması, simülasyon sonuçları Şekil 3'te gösterilmektedir.
Simülasyon sonuçları, RSSI tabanlı centroid konumlandırma optimizasyon algoritmasının, sıradan centroid konumlandırma algoritmasına göre daha küçük hataları olduğunu göstermektedir.İletişim mesafesinin artmasıyla birlikte konumlandırma hatası giderek azalmakta ve iletişim yarıçapı belirli bir değere ulaştıktan sonra hata kararlı hale gelmektedir. Bilinmeyen mobil düğüm referans düğüme daha yakınsa ve daha fazla çapa düğümü varsa, sonuç hatası daha küçüktür.
4. Sonuç
Konumlandırma teknolojisinin gelişmesiyle birlikte, ucuz kablosuz konumlandırma hizmetlerinin yaygınlaşması yoğunlaşmıştır. RSSI tabanlı centroid konumlandırma algoritmasının simülasyonu, konumlandırma doğruluğunun geleneksel merkez algoritmasına göre daha yüksek olduğunu ve düşük maliyetli, daha az ekipman, uzun mesafe ve kolay erişim özelliklerine sahip olduğunu göstermektedir. Bu algoritma temel olarak yüksek hassasiyetli konumlandırma gereksinimlerini karşılar ve nispeten yüksek konumlandırma doğruluğu ve iletim verimliliği ile kablosuz konumlandırma sistemleri için uygundur. Şu anda birçok algoritma yalnızca belirli ortamlar için uygundur veya katı koşullar gerektirir ve enerji tüketimi, ağ güvenliği, aralıklı parazit, konumlandırma optimizasyonu, üç boyutlu konumlandırma sorunları vb. Gibi hala çözülmemiş birçok sorun vardır, bu nedenle farklı konumlandırma ihtiyaçlarına ve konumlandırma ortamlarına göre Uygun bir konumlandırma algoritması seçmek gerekir.
Referanslar
1 Qiu Yan, Zhao Chongchong, Dai Guilan Kablosuz Sensör Ağının Düğüm Yerelleştirme Teknolojisi Araştırması J. Bilgisayar Bilimi, 2008, 35 (5): 47-50.
2 KOTWAL S B, VERMA S, ABROL R K. Kablosuz sensör ağlarında kendi kendine yerelleştirme yaklaşımları ve 3 boyutlu yönler J. International Journal of Computer Applications, 2012, 50 (11): 1-10.
3 YAN L Q, GIANNAKIS G B. Ultra geniş bant iletişim, zamanı gelmiş bir fikir J. IEEE Signal Processing Magazine, 2005, 21 (6): 26-54.
[4] Peng Bao Kablosuz sensör ağlarında mobil düğüm konumlandırma ve güvenli konumlandırma teknolojisi üzerine araştırma D Harbin: Harbin Teknoloji Enstitüsü, 2009.
[5] PRIYANTHA N B, BALAKRISHNAN H, DEMAINE E, ve diğerleri. Sensör ağlarında çapa içermeyen dağıtılmış yerelleştirme C. Gömülü Ağa Bağlı Sensör Sistemleri 1. Uluslararası Konferansı İşlemleri. ACM, 2003: 340-341.
[6] Tu Qiaoling, Mou Xiaoyan, Song Jia. Geliştirilmiş bir DVHop geliştirilmiş algoritması J. Journal of Chongqing University of Technology (Natural Science), 2014, 28 (11): 84-88.
[7] Sun Limin Kablosuz sensör ağı [M]. Pekin: Tsinghua University Press, 2005.
[8] Xu Lin, Fu Chenghua, Zigbee tabanlı üç taraflı ölçüm algoritması hatasının araştırılması ve iyileştirilmesi J. Mikrobilgisayar ve Uygulama, 2012, 31 (21): 68-70.
AET üyeleri için yıl sonu avantajları!
