王 磊， 李鵬濤， 賈宗璞

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

基于全質(zhì)心—Taylor的UWB室內(nèi)定位算法*

王 磊， 李鵬濤， 賈宗璞

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

針對室內(nèi)環(huán)境下的非視距(NLOS)傳播給定位精度造成較大誤差的問題，通過對超寬帶(UWB)定位模型進行分析，提出了一種基于全質(zhì)心—Taylor的混合定位算法。采用對測距誤差不敏感的全質(zhì)心算法將錨點測距數(shù)據(jù)分組運算，獲得目標(biāo)節(jié)點的初始粗定位信息，采用質(zhì)心修正算法對粗定位節(jié)點進行優(yōu)化運算,從而確定Taylor級數(shù)展開初值，再進行迭代求解，進行第二次精細定位。實驗結(jié)果表明：與Chan-Taylor算法、最小二乘估計(LSE)—Taylor算法相比，本文算法定位精度有明顯提高。

超寬帶； 室內(nèi)定位； 泰勒算法； 全質(zhì)心算法； 質(zhì)心修正算法； 混合定位

0 引 言

隨著移動通信和無線傳感網(wǎng)絡(luò)的快速發(fā)展，室內(nèi)環(huán)境下基于位置的服務(wù)(location-based service，LBS)應(yīng)用受到越來越多重視。室內(nèi)定位技術(shù)[1]在智能家居、智慧超市、倉庫安全存儲等方面的應(yīng)用都需要獲得高精度的定位信息，但是室內(nèi)環(huán)境復(fù)雜，信號傳播很容易受到人員、墻體以及其他障礙物的阻擋產(chǎn)生非視距(non-line-of-sight,NLOS)傳播的現(xiàn)象，嚴(yán)重影響定位精度，所以,需要尋找高精度和高魯棒性的室內(nèi)定位技術(shù)。

現(xiàn)有室內(nèi)定位技術(shù)主要包括無線局域網(wǎng)(wireless area netorks,WLAN)定位,Bluetooth定位,射頻識別(RFID)定位和超寬帶(ultra wideband，UWB)定位[2,3]，其中，UWB技術(shù)[4]具有高分辨率、抗多徑效應(yīng)、穿透力強、頻譜利用率高、成本低、功耗低的特點，非常適用于高精度的室內(nèi)定位[5]。

UWB定位技術(shù)采用相對帶寬大于20 %或者絕對帶寬大于500 MHz的ns級窄帶脈沖進行通信，具有較高的時間分辨率。利用這一特性，采用基于信號到達時間(time of arrival,TDOA)或者到達時間差(time difference of arrival,TOA)的測距方式，建立錨點與目標(biāo)點之間距離的非線性方程組，一般采用最小二乘法估計(LSE)[6]、Fang算法[7]、Chan算法[8,9]和Taylor算法[10]對非線性方程組進行求解。LSE法求得的是次優(yōu)解；Chan算法采用2次最大似然估計，在噪聲服從高斯分布的情況下定位精度高，但是在NLOS環(huán)境下Chan算法定位精度顯著下降；Fang算法為基于TDOA的定位算法，測距過程中如果某個測量值誤差很大會導(dǎo)致定位結(jié)果出現(xiàn)極大偏差；Taylor算法求解精度高、收斂速度快是求解非線性方程的有效方法，但是Taylor算法對初始值有很強的依賴性，只有通過迭代運算的初始值有一定的準(zhǔn)確度才能有較快的收斂速度。

室內(nèi)環(huán)境下NLOS傳播大量存在，UWB脈沖信號在NLOS傳播時引起附加時延，產(chǎn)生測距誤差。因此，本文提出了一種基于全質(zhì)心—Taylor的UWB定位算法，算法先采用全質(zhì)心算法[11]將參考節(jié)點分組運算獲得目標(biāo)節(jié)點的初始粗定位信息，然后通過質(zhì)心修正算法對初始定位信息進行數(shù)據(jù)處理，并將處理結(jié)果作為Taylor級數(shù)展開的初值進行迭代求解，進行第二次精細定位獲得高精度的定位結(jié)果。

1 方案設(shè)計

圖1是UWB定位系統(tǒng)原理圖。錨點位置信息已知，定位過程中錨點和目標(biāo)節(jié)點之間進行脈沖通信并將測量的TOA信息傳送給上位機，由上位機對測量的數(shù)據(jù)進行處理計算出目標(biāo)節(jié)點的位置坐標(biāo)。

圖1 UWB定位系統(tǒng)原理

為解決常規(guī)TOA測量方式中收發(fā)兩端時鐘同步的問題，采用來回程的定位方式。原理為錨點先向目標(biāo)節(jié)點發(fā)送定位序列，目標(biāo)節(jié)點接收到序列幀以后經(jīng)過一個固定時延發(fā)出響應(yīng)信號，錨點接收響應(yīng)信號后根據(jù)式(1)計算一次來回程時間(round-trip time,RTT)，并根據(jù)式(2)求出錨點和目標(biāo)節(jié)點間的距離di如下

tRTT=2tRU+tD

(1)

di=0.5c(tRTT-tD)

(2)

式中tRU為單程到達時間；tD為目標(biāo)節(jié)點轉(zhuǎn)發(fā)前的固定時延；c為電磁波在真空中的傳播速度。已知錨點坐標(biāo)為(X1,Y1),(X2,Y2)，…，(Xn,Yn)，目標(biāo)節(jié)點的坐標(biāo)為(X0,Y0)，根據(jù)已知條件可以列出定位方程組，如式(3)所示

(3)

但是室內(nèi)環(huán)境復(fù)雜，NLOS傳播大量存在，導(dǎo)致TOA測量存在偏差，因此，需要一種高精度的定位算法對定位方程組求解來獲得目標(biāo)節(jié)點的坐標(biāo)信息

2 算法實現(xiàn)

由于單一的定位算法不能滿足對室內(nèi)定位精度越來越高的要求，而混合定位算法可以將不同算法的特征有效結(jié)合，在提高定位精度方面有獨特的優(yōu)勢，成為室內(nèi)定位算法研究的主流方向。

2.1 Taylor算法

假設(shè)定位目標(biāo)的真實坐標(biāo)為(X,Y)，通過迭代估計出位置坐標(biāo)為(X0,Y0)，真實坐標(biāo)和估計坐標(biāo)關(guān)系如式(4)所示

(4)

算法從一個假定的初值坐標(biāo)(X0,Y0)開始進行迭代運算，將式(3)中的方程進行Taylor展開求出估計坐標(biāo)與真實坐標(biāo)的差(ΔX,ΔY)

(5)

式中

A=

(6)

(7)

在下一次迭代運算中令X0=X0+ΔX，Y0=Y0+ΔY，直到滿足|ΔX|+|ΔY|

Taylor算法進行迭代運算求解定位方程可以獲得高精度的定位結(jié)果，但Taylor初值選取不精確會出現(xiàn)不收斂的問題。一些學(xué)者采用最小二乘法[12]、質(zhì)心算法[13]、Fang算法[14]、Chan算法[15]進行初值的選取。質(zhì)心算法是一種無須測距的方法定位精度十分有限；Fang算法對運算過程中提取的定位參數(shù)要求比較高，在NLOS測距誤差比較大的情況下定位精度明顯下降；LSE法和Chan算法不僅容易受NLOS環(huán)境影響，而且計算量比較大。對Taylor算法來說取得初值越快越好，所以，本文采用全質(zhì)心算法為Taylor級數(shù)展開提供初值，對于NLOS環(huán)境對定位誤差的影響，采用質(zhì)心修正的方式減少定位誤差。

2.2 全質(zhì)心算法

定位區(qū)間內(nèi)任何3個不在一條直線上的錨點，都可以用3點定位法，如圖2所示已知參考節(jié)點A，B，C到定位節(jié)點O(xo,yo)的距離為da,db,dc，可以得到式(8)

(8)

理想情況下，當(dāng)采用三邊測量時，以A,B,C為圓心，以da,db,dc為半徑的3個圓會交于點O，但在應(yīng)用環(huán)境中，由于NLOS的干擾，信號在傳輸?shù)倪^程中產(chǎn)生正向誤差，使3個圓不能很好地交于一個公共點，如圖3所示。

圖2 LOS和NLOS下三邊測距

非視距誤差將導(dǎo)致三邊測量時交匯出公共區(qū)域，而目標(biāo)節(jié)點位于公共區(qū)域內(nèi)的某一點上，全質(zhì)心算法是求3個圓所有交點坐標(biāo)的質(zhì)心，而且計算出來的解均為實數(shù)解，其計算結(jié)果具有很高的精度和魯棒性。將式(8)用矩陣表示

(9)

(10)

定義

(11)

則有

Qθ=b

(12)

其最小二乘解為

θ=(QTQ)-1QTb

(13)

最終求得坐標(biāo)值(x0,y0)。

2.3 質(zhì)心修正算法

定位過程中3個錨點可以確定目標(biāo)節(jié)點的二維坐標(biāo)值，但是NLOS傳播時在部分錨點測距誤差比較大的情況下，直接采用3點定位的方法精度并不理想，為了提高定位精度設(shè)置更多的錨點協(xié)同定位，并提出了對錨點分組運算的方法削弱NLOS的影響。

將定位區(qū)間內(nèi)所有錨點以3個為一組(不在同一條直線上)進行分組，得到n組三邊測量數(shù)據(jù)，采用全質(zhì)心算法分別求出每一組錨點對目標(biāo)節(jié)點的定位坐標(biāo)值(x1,y1),(x2,y2)，…，(xn,yn),每一組測量數(shù)據(jù)不同求出的定位坐標(biāo)值偏離真實節(jié)點的距離也不相同，為了確保Taylor初值的可靠性，采用質(zhì)心修正算法對已知的定位節(jié)點進行優(yōu)化處理。首先，求出所有定位坐標(biāo)值的質(zhì)心值(x′,y′)，如式(14)

(14)

直接用質(zhì)心算法對每組錨點求得目標(biāo)節(jié)點的坐標(biāo)值求解計算出所有錨點定位初值的質(zhì)心值，但是部分嚴(yán)重偏離定位節(jié)點的定位初值的計算影響定位精度，所以，采用質(zhì)心修正的方式對求得的質(zhì)心值進行多次循環(huán)優(yōu)化處理。

1)計算當(dāng)前定位坐標(biāo)值(xi,yi)到其質(zhì)心值(x′,y′)的距離di為

(15)

2)對距離值d1,d2，…，dn從大到小進行排序，找出最大距離值dk對應(yīng)的定位坐標(biāo)值(xk,yk)，對(xk,yk)以外的其他位坐標(biāo)值再次質(zhì)心求解得到質(zhì)心值(x″,y″)。

3)計算2次質(zhì)心值(x′,y′),(x″,y″)之間的距離dz，并和設(shè)定的閾值p進行比較。

4)當(dāng)dz

5)當(dāng)dz>p時，剔除定位坐標(biāo)值(xk,yk)，并從步驟(1)對當(dāng)前定位坐標(biāo)值計算直到滿足要求。

3 實驗結(jié)果與算法分析

為了驗證算法的有效性，采用DecaWave公司開發(fā)的UWB模塊DWM1000(圖4)對本文算法進行實驗驗證。DWM1000模塊集成了DW1000芯片、石英晶體、天線、無源元件和平衡/不平衡轉(zhuǎn)換器。采用ST公司生產(chǎn)的處理器STM32f103實現(xiàn)系統(tǒng)控制，外接8 MHz晶振實現(xiàn)時鐘控制。

圖4 DWM1000模塊

基于全質(zhì)心—Taylor的UWB室內(nèi)定位算法,采用全質(zhì)心算法作為初步位置計算，采用質(zhì)心修正算法對初定位結(jié)果進行優(yōu)化處理并為Taylor算法求出Taylor初值的3步定位算法。為了確保定位精度的穩(wěn)定性,在室內(nèi)環(huán)境中選取6個相距一定距離的位置作為定位節(jié)點，在每個位置均實現(xiàn)100次定位計算，求出定位節(jié)點的平均定位坐標(biāo)值并和真實坐標(biāo)比較,計算其定位誤差,即

(16)

式中 (xp,yp)和(xq,yq)分別為目標(biāo)節(jié)點的真實坐標(biāo)和定位坐標(biāo)。

圖5為在實驗室對4個均勻分布的目標(biāo)節(jié)點用3種室內(nèi)定位算法在相同情況下定位誤差的比較。3種室內(nèi)定位算法均以Taylor展開算法為核心，區(qū)別在于對所選取的初始值算法不同，LSE和Chan氏算法沒有對測距信息進行篩選，而本文算法采用質(zhì)心優(yōu)化算法削減了NLOS對定位精度的影響，從圖5可以看出：本文提出的算法和另外2種算法相比定位精度有明顯的提高。

圖5 3種定位算法比較

當(dāng)測距誤差增加時，定位誤差也將增加，定位精度隨之降低，為了獲得高精度的室內(nèi)定位，可以通過在定位區(qū)域增加錨點數(shù)量，引入測距數(shù)據(jù)冗余來實現(xiàn)。如圖6所示，隨著錨點數(shù)的增加定位精度不斷提高，當(dāng)錨點數(shù)目從4個增長到7個時，定位精度有明顯提高；當(dāng)錨點數(shù)目從7個到9個定位精度變化趨于緩慢。隨著錨點數(shù)目的增加，雖然定位精度有顯著的提高，但是算法復(fù)雜度增加，硬件成本也隨著增加，在實際應(yīng)用中應(yīng)該根據(jù)具體環(huán)境確定錨點個數(shù)。

圖6 不同錨點數(shù)下精度變化

4 結(jié)束語

針對室內(nèi)定位過程中存在的NLOS問題，提出了基于全質(zhì)心—Taylor的UWB室內(nèi)定位算法。利用UWB技術(shù)時間分辨率高的特點，獲得參考節(jié)點和目標(biāo)節(jié)點的TOA測量值[16]，并用全質(zhì)心算法實現(xiàn)對目標(biāo)節(jié)點的原始粗定位，然后用質(zhì)心修正算法對粗定位坐標(biāo)進行優(yōu)化，并將優(yōu)化后的值作為Taylor展開的初值，最后采用Taylor算法得到最終的定位結(jié)果。仿真結(jié)果表明，文中提出的算法和傳統(tǒng)的Chan-Taylor算法,LSE-Taylor算法相比明顯提高了定位精度。

[1] 洪 雁，王培康.基于稀疏表示多分類的室內(nèi)定位算法[J].無線電工程，2014，4(2)46-49.

[2] 韓下林,趙衛(wèi)東,季 軍，等.基于RFID技術(shù)的室內(nèi)定位算法及其改進[J].計算機工程,2015,34(22):266-267.

[3]CetinO,NazhH,GurcanR,etal.AnexperimentalstudyofhighprecisionTOA-basedUWBpositioningsystems[C]∥Proceedingsof2012IEEEInternationalConferenceonultra-wideband(ICUWB),Syracusem,NY:IEEE,2012:357-361.

[4] 宋廣儀.超寬帶高速數(shù)據(jù)傳輸技術(shù)研究[J].無線電工程,2014,44(5):23-25.

[5]DengZhongliang,YuYanpei,YuanXie,etal.Situationanddevelopmenttendencyofindoorpositioning[J].ChinaCommunications,2013,10(3):42-55.

[6] 謝勝東,胡愛群,黃 毅,等.基于到達時間差的兩步最小二乘定位算法[J].東南大學(xué)學(xué)報:自然科學(xué)版,2013,43(6):1157-1161.

[7] 鄒 杰,李珊君,陳曉明.一種改進的室內(nèi)無線定位算法[J].計算機工程,2011,37(14):76-79.

[8] 劉春紅,陸萍萍.基于Chan氏算法和最近鄰居算法的協(xié)同定位算法[J].無線通信技術(shù),2012(3):8-15.

[9] 楊天池,金 梁,程 娟.一種基于TOA定位的Chan改進算法[J].電子學(xué)報,2009,37(4):819-822.

[10] 王瑞榮,鄭書萬,陳浩龍,等.一種基于Taylor和Kalman的室內(nèi)協(xié)同定位方法[J].傳感技術(shù)學(xué)報,2014,27(11):1557-1561.

[11] 朱 浩,顧宗海,蘇 金,等.一種基于交點質(zhì)心求解的RSSI定位算法及其優(yōu)化[J].鄭州大學(xué)學(xué)報:工學(xué)版,2010,31(6):43-46.

[12] 任 斌,徐會彬.基于總體最小二乘的泰勒級數(shù)展開的TOA的UWB定位方法[J].科學(xué)技術(shù)與工程,2013(21):6129-6133.

[13] 張瑞峰,張忠娟，呂辰剛.基于質(zhì)心—Taylor的UWB室內(nèi)定位算法研究[J].重慶郵電大學(xué)學(xué)報:自然科學(xué)版,2011,23(6):717-721.

[14] 王 彪,傅忠謙.基于超寬帶技術(shù)的TDOA室內(nèi)三維定位算法研究[J].微型機與應(yīng)用,2013,32(14):83-86.

[15] 陳德章,唐 皓,吳季達.基于Chan和Taylor的TDOA協(xié)同定位算法研究[J].計算機科學(xué),2011,38(10A):406-411.

[16] 楊小鳳，陳鐵軍，陳宇寧.基于TOA估計的超寬帶快速定位方法[J].現(xiàn)代雷達,2016,38(3):28-31.

UWB indoor localization algorithm based on full centroid and Taylor*

WANG Lei, LI Peng-tao, JIA Zong-pu

(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,China)

A novel full centroid and Taylor cooperative positioning algorithm of ultra wideband(UWB)is proposed aiming at problem of big error of localization precision caused by NLOS propagation in indoor environment.The full centroid positioning algorithm that is not sensitive to localization error is used as the initial rough localization by using anchol point ranging data grouping operations,and then Centroid scheme and selecting the rough localization nodes are applied to coarse localization node preliminary optimization,and the optimized value as the Taylor initial value.Simulation results show that this method has superior positioning precision than Chan-Taylor and LSE-Taylor algorithm.

ultra wideband(UWB); indoor localization; Taylor algorithm; full centroid algorithm; centroid correction algorithm; cooperative localization

2017—04—14

河南省重點科技攻關(guān)資助項目(152102210102)；河南省教育廳科技攻關(guān)計劃資助項目(13A520321)；河南省科技廳公關(guān)計劃資助項目(132102210123)

10.13873/J.1000—9787(2017)06—0146—04

TP 393

A

1000—9787(2017)06—0146—04

王 磊(1977-)，男，博士后，副教授，從事物聯(lián)網(wǎng)，計算機網(wǎng)絡(luò)技術(shù),E-mail:wang_leiqjy@163.com。

賈宗璞(1963-)，男，通訊作者，教授，博士生導(dǎo)師，從事計算機網(wǎng)絡(luò)技術(shù)研究工作。