王 磊， 李鵬濤， 賈宗璞

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

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

王 磊， 李鵬濤， 賈宗璞

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

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

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

0 引 言

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

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

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

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

1 方案設計

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

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

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

tRTT=2tRU+tD

(1)

di=0.5c(tRTT-tD)

(2)

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

(3)

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

2 算法實現(xiàn)

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

2.1 Taylor算法

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

(4)

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

(5)

式中

A=

(6)

(7)

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

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

2.2 全質心算法

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

(8)

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

圖2 LOS和NLOS下三邊測距

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

(9)

(10)

定義

(11)

則有

Qθ=b

(12)

其最小二乘解為

θ=(QTQ)-1QTb

(13)

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

2.3 質心修正算法

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

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

(14)

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

1)計算當前定位坐標值(xi,yi)到其質心值(x′,y′)的距離di為

(15)

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

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

4)當dz

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

3 實驗結果與算法分析

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

圖4 DWM1000模塊

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

(16)

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

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

圖5 3種定位算法比較

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

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

4 結束語

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

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

[2] 韓下林,趙衛(wèi)東,季 軍，等.基于RFID技術的室內(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ù)傳輸技術研究[J].無線電工程,2014,44(5):23-25.

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

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

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

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

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

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

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

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

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

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

[15] 陳德章,唐 皓,吳季達.基于Chan和Taylor的TDOA協(xié)同定位算法研究[J].計算機科學,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

河南省重點科技攻關資助項目(152102210102)；河南省教育廳科技攻關計劃資助項目(13A520321)；河南省科技廳公關計劃資助項目(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)絡技術,E-mail:wang_leiqjy@163.com。

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