AP düzen optimizasyonu ve K-ortalama kümeleme algoritmasına dayalı iç mekan konumlandırma araştırması
Özet: Geleneksel iç mekan konumlandırmada, kümeleme algoritması, konumlandırma ortamındaki erişim noktalarının (AP) sayısına pasif olarak dayanır, bu da düşük konumlandırma verimliliği ve büyük hatalarla sonuçlanır.İç mekan konumu parmak izi konumlandırma araştırmasında, AP düzeni konumlandırma doğruluğunu etkileyen önemli bir faktördür. Bu nedenle, Intel çiplerini kullanan gömülü mikro sistem ve Amerika Birleşik Devletleri'nde Signal Hound tarafından üretilen SA44B ölçüm alıcısı bir sensör ağı oluşturur.İç mekan konumlandırmanın amaç işlevi, radyo dalgası yolu kaybına göre belirlenir.Amaç fonksiyonu gerçekleştirmek için simpleks yöntemi ve benzetilmiş tavlama algoritması füzyon algoritması kullanılır. En makul AP iç mekan konum düzenini elde etmek için optimize edin ve ardından sistemin konumlandırma verimliliğini ve doğruluğunu iyileştirmek için ilk kümeleme merkezi olarak optimize edilmiş AP konum koordinatlarını kullanmak için K-ortalama kümeleme algoritmasını geliştirin. Deneysel sonuçlar, geleneksel K-ortalamaları algoritmasıyla karşılaştırıldığında, AP konum optimizasyonundan sonra kümeleme konumlandırma algoritmasının doğruluğunun% 13,8 oranında arttığını göstermektedir.
TN966.3
Bir
10.16157 / j.issn.0258-7998.173642
Çince alıntı biçimi: Chen Yunfei, Du Taihang, Jiang Chundong ve diğerleri.AP düzen optimizasyonu ve K-ortalamalı kümeleme algoritmasına dayalı iç mekan konumlandırma araştırması. Elektronik Teknoloji Uygulaması, 2018, 44 (3): 68-71.
İngilizce alıntı biçimi: Chen Yunfei, Du Taihang, Jiang Chundong ve diğerleri.AP düzen optimizasyonuna ve K-ortalamalı kümeleme algoritmasına dayalı iç mekan konum araştırması.Elektronik Teknik Uygulaması, 2018, 44 (3): 68-71.
0 Önsöz
Konum parmak izi konumlandırma şu anda iç mekan konumlandırmada en yaygın kullanılan konumlandırma yöntemidir.Online konumlandırma aşamasında tespit edilen değerlerin veritabanı ile hızlı bir şekilde eşleştirilmesi, konumlandırma verimliliğini belirler. Kümeleme algoritması, büyük miktarda verinin boyutluluğunu azaltabilir ve eşleştirme hesaplamalarının miktarını azaltabilir. birçok.
Literatür, KNN yöntemini geliştirmek için K-ortalamalı kümeleme yöntemini kullanır Bu yöntem, başlangıç noktası komşuluğunu taramak için K-ortalamalı kümeleme kullanır ve algoritma, hesaplama üzerindeki tekil noktaların etkisini azaltır, ancak konum verimliliği yüksek değildir. Literatür, parmak izi alanını kümelemek ve tüm çözüm alanını birkaç alt alana bölmek için K-ortalamalı kümeleme yöntemini uygulamayı önermektedir. Bu yöntem, eşleştirme için hesaplama miktarını azaltır, ancak kümeleme algoritmasının en uygun çözümü alacağını garanti edemez. Dahası, yukarıdaki iki K-ortalamalı kümeleme algoritması pasif olarak ortamdaki AP koşullarına bağlıdır ve kümeleme sonucunun başlangıç değerinden büyük ölçüde etkilendiği ve yerel maksimuma düşmesinin kolay olduğu bir problem vardır. Test edilecek ortamdaki AP sayısı büyükse, algoritma en iyi noktaları filtrelemek ve en uç noktaları filtrelemek için kullanılabilir; ortamdaki AP sayısı azsa yukarıdaki yöntem tatmin edici değildir.
Deneyde, AP konum düzenindeki değişikliğin, konumlandırma doğruluğu üzerinde daha büyük bir etkiye sahip olacağı bulundu ve bu konuda çok az araştırma var. Bu makale, AP'lerin sayısını artırmadan, gelişmiş bir K-ortalamalı kümeleme algoritması ile konumlandırma sisteminin genel performansını ve konumlandırma doğruluğunu artıran bir AP etkin yerleşim optimizasyon yöntemi önermektedir.
1 İç mekan konumlandırma AP dağıtım optimizasyon modeli
1.1 Dağıtım optimizasyonu hedef işlevi
Uzaydaki radyo yayılım kayıp modeli genellikle aşağıdaki formülle ifade edilir:
Bunlar arasında s ve t, konumlandırma alanının sınır uzunluğudur.
1.2 Hesaplama adımları
Simpleks yöntemi (SM) nispeten eksiksiz bir optimizasyon hesaplama teorisine sahiptir, ancak iç mekan parmak izi konumlandırma araştırmalarında daha az literatür içerir. Geleneksel simpleks yönteminin yinelemeli hesaplama sürecinde, ilk üçgen uzatılır, daraltılır, simetriktir, vb. Modelde en büyük kalıntı hatası olan köşe kaldırılır, yeni bir üçgen oluşturmak için yeni bir köşe eklenir ve bu arama işlemi sürekli tekrarlanır. Amaç fonksiyonu değeri kısıtlama koşulunu sağladığında, en iyi yaklaşım çözümü olan yinelemeli hesaplama ile elde edilen üçgen için en küçük kalıntı hataya sahip nokta seçilir.
Simüle tavlama (Simüle Tavlama, SA) algoritması, fiziksel soğutma sürecini simüle eden bir optimizasyon algoritmasıdır. Temel fikri şudur: Başlangıç sıcaklığı yükseldiğinde, parçacıkların enerjisi daha yüksektir ve parçacıklar yavaş yavaş soğuduğunda daha düzenli hale gelir ve sonunda parçacıklar ulaşır. Son kararlı durum. Benzetilmiş tavlama algoritması temel olarak üç bölümden oluşur: çözüm alanı, amaç işlevi ve ilk çözüm.
Simüle edilmiş tavlama algoritması genel kontrol için kararlıdır ancak yakınsaması daha yavaştır. Simpleks yöntemi hızlı bir hesaplama hızına sahiptir, ancak yerel olarak optimize edilmesi kolaydır. İkisinin avantajları tamamlayıcıdır. Simpleks benzetimli tavlama (SMSA) füzyon algoritması fikri, ilk önce simpleks algoritmasını yerel minimumu aramak için kullanmak ve ardından benzetilmiş tavlama algoritmasının ani atlamasını kullanarak yerel minimumdan atlamak ve yeni yerel simpleks aramaktır. Minimum ekstremum, aramaya devam etmek için başlangıç değerinin yerini alan bir nokta varsa, sıcaklık düşürme işlemi döngü boyunca global optimal çözüme yaklaşacaktır. Hesaplama adımları aşağıdaki gibidir:
2 Geliştirilmiş K-ortalamalı kümeleme algoritması
Geleneksel K-ortalamalı kümeleme algoritması, rastgele K alt kategorilerinin merkezlerini oluşturur ve kalan her nesneyi, her alt kategorinin merkezinden uzaklığa göre en kısa mesafeyle alt kategoriye böler ve ardından her bir alt kategorideki tüm nesnelerin ortalama değerini yeniden hesaplar. Bunu yeni bir küme merkezi olarak kullanın ve kareler fonksiyonunun hata toplamı yakınlaşana kadar işlemi tekrarlayın. Geleneksel yöntemin dezavantajları, büyük miktarda hesaplama ve düşük verimliliktir ve yerel bir optimal çözüm elde etmek mümkündür.Bunun nedeni, ilk kümeleme merkezinin seçiminde yatmaktadır.Kümeleme merkezi, yoğun uzamsal veri dağılım noktasına yakın olduğunda, konumlandırma verimliliği yüksek ve hesaplama süresi kısadır. Uzamsal veriler seyrek olarak dağıtıldığında etki zayıftır.
Çalışmada, kümeleme algoritmasının ilk kümeleme merkezi geliştirilmiş ve rastgele seçilmek yerine ayarlanmıştır, bunun yerine ilk merkez olarak konuşlandırılmış ve optimize edilmiş AP kullanılmış ve kümelenmenin amaç işlevi olarak test noktasından AP'ye Öklid uzaklığı kullanılmış ve kümeleme süreci atılmıştır. Tekillik. AP'nin konuşlandırılmasını optimize ederken amaç fonksiyonunun özü, mesafe hatasının en aza indirilmesidir, bu nedenle, veritabanını kümelemek için AP'ye en yakın koordinata karşılık gelen RSS sinyal özelliği vektörünün seçilmesi en verimli olanıdır.
K-ortalamalı kümeleme algoritmasını iyileştirme adımları aşağıdaki gibidir:
(1) Çevrimdışı edinim aşaması
Giriş: Sinyal örnekleme veri kümesi X = {X1, X2, ..., Xn}
Çıktı: Cn türleri (1sn)
Programdaki kümeleme parametrelerini başlatın ve küme sayısını planlayın k (2 < k < q < n) Numune noktalarını rastgele seçin ve bunları ilk işlem sınıfı merkezleri h1, h2, ..., hk olarak ayarlayın ve yineleme eşik koşulunu minimum ortalama kare hatası olarak veya eşik değerine ulaşan yineleme sayısı olarak ayarlayın.
Xp (p = 1, 2, ..., n) ile her bir ilk sınıfın merkezinin koordinatları arasındaki Öklid uzaklığını dij hesaplayın, azalan sırada ortalama değeri bulun ve her bir sıralama noktasını en yakın komşu sınıf merkezinin alt sınıfına atayın.
Alt sınıftaki tüm referans noktaları arasındaki Öklid mesafelerinin toplamını hesaplayın ve yeni küme merkezi olarak minimum değere karşılık gelen noktayı seçin.
Yinelemeyi durdurma koşulunun yargısı: Minimum ortalama varyans karşılanmazsa veya yineleme eşiği koşulu karşılanmazsa, adımına dönün ve yeni küme merkeziyle yeniden kümelendirin; aksi takdirde prosedürü sonlandırın.
(2) Çevrimiçi konumlandırma aşaması
Giriş: hedef sinyal örnekleme örnek noktası verileri Xrssi
Çıktı: çıktı konumu koordinat değerini karşılaştırın
Konumlandırma hedefi Xrssi ile her bir küme merkezi arasındaki Öklid mesafesini drssi hesaplayın ve ardından hedef noktanın alt kategorilerini ayırın.
Xrssi ile kategori merkezi arasındaki Öklid mesafesini hesaplayın, hedef noktanın konum koordinatlarını eşleştirmek için KNN yöntemini kullanın ve hesaplama sonucunu çıkarın.
3 Deneysel sonuçlar ve analiz
3.1 Deneysel platform
Sinyal toplama ve işleme modülü, Birleşik Devletler'den Signal Hound'un SA44B spektrum analizör ölçüm alıcısı ve Intel'in Minnow Board Turbott gömülü mikro sisteminden oluşur.USB bağlantı noktası, diğer toplama modülleri AP düğümleri ile bir kablosuz sensör oluşturan Tenda'nın W311MA kablosuz ağ kartına bağlanır. İnternet. Toplanan veriler, JCG'nin JHR-N926R kablosuz yönlendiricisi aracılığıyla Lenovo ThinkPad E440 dizüstü sunucusuna gönderilir.
AP konum optimizasyon algoritmasının etkinliğini doğrulamak için deney, Şekil 1'de gösterildiği gibi, deney binasında 10 mx 13 m'lik açık bir sınıfta gerçekleştirildi, referans koordinat noktası aralığı 0,8 m aralıklarla ayarlandı (bu, ölçüm için yer karolarının boyutudur) , Konum noktaları sırasıyla A, B, C, D olarak ayarlanmıştır. Literatür, daha küçük bir konumlandırma alanında 4 AP seçildiğinde maliyet performansının en yüksek olduğunu doğrulamaktadır. Bu nedenle, 4 AP seçilmiştir ve her bir AP'nin başlangıç koordinatları A (2.0, 2.0), B ( 2.0, 8.0), C (6.6, 8.0), D (6.6, 2.0) ve dikdörtgen bir dizi oluşturur.
Sinyal kaynağı USPRB200 tipi jeneratörü kullanır ve merkez frekansı 70 MHz 6 GHz olarak ayarlanabilir. İletim kaynağının frekansı, cep telefonunun parazit kaynağı frekansını simüle etmek için 840 MHz olarak modüle edilmiştir. Sinyal gücü 15 dB'dir. Sinyal kaynağının gimbal anteni, braketin merkez ekseniyle çakışmaktadır. Braket düzlemi yerden 0,5 m'dir. Daha düşük sinyal kaynağı yüksekliği zemini azaltabilir Yansıyan dalganın ölçüm bozukluğu için, parmak izi bilgisi veri toplama için 1 m aralıklarla referans koordinatları seçilir.Kapağın merkez ekseni referans noktası işareti ile hizalanır.Toplama süresi 15 saniyedir.Toplama süresi boyunca, radyo dalgası ortamını temizlemek ve harici paraziti azaltmak için personelin cep telefonu kapatılır. Çevrimdışı aşamada toplam 40 referans konumu toplandı ve her bir parmak izi konumu 3 kez toplandı, bu da bina köşelerine yakın alanlar ve biriken enkaz ile AP'ye çok yakın ve örtüşen referans konumları hariç tuttu.
3.2 Deney ve hata analizi
Konumlandırma ortamındaki parmak izi noktaları ve referans noktaları sıralı olarak toplanan verilerdir ve ilk koordinatlar simpleks yöntemle optimize edilmiştir.Optimize edilmiş konum koordinatları A1 (3.8, 0.4), B1 (11.3, 1.9), C1 (1.9, 9.6), D1 (7.8, 12.3), Şekil 2'de gösterildiği gibi, konumlandırma için K-araç kümeleme algoritmasını kullanarak alıcıyı optimize edilmiş yeni koordinat noktasına yerleştirin. Literatürün doğrulama sonucuna göre, K = 3 olduğunda, hedefin konumlandırma doğruluğu nispeten en yüksektir, bu nedenle bu yazıda konumlandırma algoritmasının K parametresi 3 olarak ayarlanmıştır.
SMSA algoritması uygulandıktan sonra test noktalarının ortalama konumlandırma hatasının biraz azaldığı Şekil 3'ten görülebilmektedir.AP konumu optimize edildiğinde, konumlandırma doğruluğu da önemli ölçüde artmaktadır.K-ortalama konumlandırma hatası 1.5 m olduğunda, olasılık% 68'e ulaşmaktadır. , Optimizasyon öncesine göre% 13,8 daha yüksek. Aynı zamanda, SMSA algoritması tarafından optimize edilen K-ortalamalı kümeleme algoritmasının hesaplama verimliliği önemli ölçüde geliştirilir Şekil 4'te gösterildiği gibi, düzen optimizasyonundan sonraki AP koordinatları ilk kümeleme merkezi olarak kullanıldığından, ilk kümeleme hesaplama hızı çok hızlıdır. İyileştirilmiş K-ortalamalı kümeleme algoritmasının toplam süresi 55,23 saniyedir, bu da optimizasyon öncesine göre 13,26 s daha azdır ve iç mekan konumlandırma sonuçları konumlandırma gereksinimlerini karşılar.
4. Sonuç
Bu makale, bir iç mekan konumlandırma sistemi oluşturmak için gelişmiş gömülü ve spektrum alıcıları kullanır, iç mekan konumlandırma modelini optimize etmek için SMSA füzyon algoritmasını kullanır ve iç mekan ortamının en uygun düzenini belirler. Deneyler, önerilen iç mekan AP aktif yerleşim optimizasyon yönteminin ve geliştirilmiş K-ortalamalı kümeleme algoritmasının, AP kaynaklarını makul şekilde kullandığını ve konumlandırma doğruluğunu iyileştirdiğini göstermektedir. AP'lerin karmaşık iç mekan ortamları ve yoğun şekilde akan insanlar bulunan alanlarda nasıl optimize edileceği ve dinamik hedeflerin doğru konumlandırılmasının gelecekteki deneylerde doğrulanması gerekir.
Referanslar
Deng Zhongliang. İç mekan konumlandırmanın statüko ve gelişim eğilimi üzerine araştırma China Communications, 2013, 10 (3): 42-55.
He Haiping, Guo Hang, Fang Shuang.ZigBee Kapalı Konumlandırma Sisteminin Bulanık Kümelenmeye Dayalı Tasarımı. Elektronik Teknoloji Uygulaması, 2016, 42 (5): 71-73, 77.
Cui Bin, Zhao Xi'an Yayılma modeli ve konum parmak izine dayalı hibrit bir iç mekan konumlandırma yöntemi Etüt ve Haritalama Bülteni, 2015, 43 (6): 35-38.
Du Yilin. Bulanık bir kümeleme KNN konumu parmak izi konum algoritması Mikrobilgisayar ve Uygulama, 2012, 31 (23): 55-58.
Sun Feng, Shi Weibin, Huang Lingfeng.Kablosuz sensör ağına dayalı iç mekan konumlandırma teknolojisi araştırması Elektronik Teknoloji Uygulaması, 2013, 39 (10): 80-83.
Li Jian, Gao Yongtao, Xie Yuling, vd.Hız ölçümü olmaksızın simpleks yöntemine dayalı mikrosismik konumun iyileştirilmesi üzerine araştırma.Çin Kaya Mekaniği ve Mühendisliği Dergisi, 2014, 33 (7): 1336-1346.
Liu Yanlong, Lu Xianpeng, Wang Xiangguo. WSN'lerin Konumunda Hibrit Genetik Algoritmanın Uygulanması. Sensörler ve Mikrosistemler, 2014, 33 (2): 150-153.
Chen Kong, Song Chunlei, Chen Jiabin. Gelişmiş WKNN'ye dayalı konum parmak izi iç mekan konumlandırma algoritması. Navigasyon konumlandırma ve zamanlama, 2016, 3 (4): 58-64.
Zhou Mu, Pu Qiaolin, Tian Zengshan. İç mekan WLAN konumlandırmada konum parmak izi optimizasyonu için erişim noktası dağıtım yöntemi. Journal of Communications, 2015, 36 (Z1): 30-41.
Chen Wang, Jia Zhenhong, Qin Xizhong, vd.Geliştirilmiş K-ortalamalı kümeleme algoritmasına dayalı iç mekan WLAN konumlandırması üzerine araştırma Laser Journal, 2014, 39 (7): 11-14.
yazar bilgileri:
Chen Yunfei 1, 2, Du Taihang 1, 3, Jiang Chundong 1, 3, Wang Jingyu 1, Li Juanmei 1
(1. Kontrol Bilimi ve Mühendisliği Okulu, Hebei Teknoloji Üniversitesi, Tianjin 300130; 2. Elektrik Mühendisliği Bölümü, Xingtai Mesleki ve Teknik Koleji, Xingtai 054000, Hebei;
3. Hebei Eyaleti Kontrol Mühendisliği Araştırma Merkezi, Tianjin 300130)
