基于最小二乘法的室內(nèi)三維定位算法研究

王桂杰，焦良葆，曹雪虹,

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003;2.南京工程學(xué)院 人工智能產(chǎn)業(yè)技術(shù)研究院，江蘇 南京 211167)

0 引 言

近幾年，隨著智能電子設(shè)備在日常生活中的廣泛應(yīng)用，提供一套完整可靠的室內(nèi)位置服務(wù)系統(tǒng)變得尤為必要。全球衛(wèi)星定位系統(tǒng)(GPS)[1-2]作為一種發(fā)展成熟的室外定位技術(shù)，能夠提供室外米級的定位精度。但由于室內(nèi)環(huán)境因素的干擾，GPS信號被大大削弱，使其難以提供精確的室內(nèi)定位服務(wù)。國內(nèi)外專家學(xué)者對室內(nèi)定位技術(shù)進(jìn)行了大量研究，使得室內(nèi)定位技術(shù)得到了快速的發(fā)展。

基于無線傳感網(wǎng)絡(luò)的室內(nèi)定位技術(shù)包括紅外線、藍(lán)牙、WiFi、超聲波、超寬帶(UWB)等[3-4]?；跍y距模型的定位系統(tǒng)提高定位精度的方式有如下兩點(diǎn)：(1)選擇最優(yōu)的測距模型，盡可能克服室內(nèi)環(huán)境的因素干擾，提高測距的精確度；(2)選擇最優(yōu)的定位算法對測距結(jié)果進(jìn)行處理，求得最終的定位坐標(biāo)。目前常用的室內(nèi)測距模型包括如下幾種[5-8]：接收信號強(qiáng)度(RSSI)測距模型、到達(dá)角度差(AOA)測距模型、到達(dá)時間/到達(dá)時間差(TOA/TDOA)測距模型等；常用的室內(nèi)定位算法主要包括如下幾種：三角質(zhì)心定位算法、最小二乘定位算法、Chan氏定位算法[9]等。不同的定位算法都可以在一定精度范圍內(nèi)實(shí)現(xiàn)室內(nèi)定位，也都存在一些需要被完善和解決的問題。

最小乘法是一種計算相對簡單，便于實(shí)現(xiàn)的定位處理算法，但利用最小二乘法求解矩陣方程時要求系數(shù)矩陣應(yīng)為非奇異矩陣，在具體的三維應(yīng)用場景中即要求基站坐標(biāo)選取時必須避免所有基站處在同一高度平面，即要求基站間在布局時必須存在一定的高度差值，且高度差值將直接影響標(biāo)簽高度坐標(biāo)定位的精確度。首先介紹了到達(dá)時間(TDOA)測距模型和最小二乘法定位算法的原理并闡述了超寬帶(UWB)[10-11]利用最小二乘法實(shí)現(xiàn)定位的具體方法，通過分析現(xiàn)實(shí)應(yīng)用場景中傳統(tǒng)最小二乘法所產(chǎn)生的定位誤差及其產(chǎn)生的原因，提出了一種改進(jìn)的最小二乘定位算法。該算法旨在降低最小二乘法對于基站三維幾何布局的依賴關(guān)系，提高三維定位坐標(biāo)的精確度。最后通過實(shí)驗(yàn)證明，該算法比傳統(tǒng)最小二乘法定位算法在三維定位精度上有了明顯的提升。

1 定位模型

1.1 基于UWB的TDOA測距模型

到達(dá)時間(TOA)方式利用標(biāo)簽發(fā)射信號到接收基站，通過到達(dá)基站時所用的時間求得信號發(fā)射點(diǎn)與接收點(diǎn)之間的距離。而TOA要求被測點(diǎn)與接收機(jī)保持嚴(yán)格的時間同步，多數(shù)應(yīng)用場合無法滿足這一要求。與TOA類似，TDOA只是測量得到時間差而非絕對時間[12]。這種方法只需接收基站之間保持同步，不要求與被測標(biāo)簽間時間同步，使系統(tǒng)相對簡化，所以在定位系統(tǒng)中應(yīng)用最廣。

UWB是以相比較于傳統(tǒng)統(tǒng)通信方式更寬的頻譜進(jìn)行通信的，其可以使用更少的電能，更快地進(jìn)行數(shù)據(jù)傳輸，其脈沖寬度非常短，且在抗多徑以及穿透性等諸多方面有著傳統(tǒng)無線通信方式無法實(shí)現(xiàn)的優(yōu)勢[11]。TDOA模型通過UWB通信方式測量標(biāo)簽到每兩個基站之間的距離差，距離差等于常量即可繪制出雙曲線，而曲線交點(diǎn)即可確定標(biāo)簽坐標(biāo)。該方法在實(shí)現(xiàn)過程中，標(biāo)簽只需要廣播一次無線信號即可，因此有利于標(biāo)簽的功耗及標(biāo)簽并發(fā)數(shù)量。

1.2 最小二乘法

最小二乘法(least square method)是一種數(shù)學(xué)優(yōu)化算法，又被稱為最小平方法。它利用最小化誤差的平方來尋找數(shù)據(jù)最佳匹配結(jié)果。通過最小二乘法求解未知變量的過程相對比較簡便，且所求得的結(jié)果與實(shí)際數(shù)據(jù)之間誤差的平方和為最小值。最小二乘法還可用于曲線擬合，以及其他優(yōu)化類問題的求解[13-15]。

利用最小二乘法求解超限定方程組(未知數(shù)個數(shù)大于方程個數(shù))十分方便，假設(shè)有m個等式，n個未知數(shù)x，m>n，則有方程組：

(1)

其中，i=1,2,…,m。將上式向量化得：

AX=B

(2)

(3)

取誤差向量δ無窮小時，X有最優(yōu)解，令：

f=δ2=δTδ=(AX-B)T(AX-B)

(4)

對式(4)進(jìn)行求導(dǎo)，并令其結(jié)果等于0，可得：

(5)

如果ATA為非奇異矩陣，則AX=B有唯一解，由下式可求解得：

X=(ATA)-1ATB

(6)

2 基于UWB的最小二乘定位算法

假設(shè)三維空間中有n(n≥4)個固定基站節(jié)點(diǎn)，基站節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1,z1),(x2,y2,z2)，…，(xn,yn,zn)，設(shè)待求的移動標(biāo)簽節(jié)點(diǎn)坐標(biāo)為p(xp,yp,zp)，標(biāo)簽節(jié)點(diǎn)與基站節(jié)點(diǎn)之間的距離為d1,d2,…,dn。為保證最小二乘法在求解矩陣方程時，系數(shù)矩陣滿足非奇異的要求，按照相鄰基站不在同一水平高度的分布原則進(jìn)行基站布局，如圖1所示。

圖1 室內(nèi)基站分布于不同水平面

則有：

(7)

整理后得：

(8)

其中，kn=x2n+y2n+z2n，n=1,2…。

由相鄰兩式相減可得：

(9)

其中，xn(n-1)=xn-xn-1,yn(n-1)=yn-yn-1,zn(n-1)=zn-zn-1,kn(n-1)=kn-kn-1,n=2,3…。

令：

(10)

(11)

(12)

將式(10)～(12)帶入式(6)求解矩陣方程，可得移動標(biāo)簽節(jié)點(diǎn)坐標(biāo)p(xp,yp,zp)。

3 算法優(yōu)化及實(shí)驗(yàn)分析

3.1 最小二乘法的定位優(yōu)化

前面提到，為保證矩陣方程在求解時能夠求得唯一解，系數(shù)矩陣應(yīng)滿足為非奇異矩陣的要求。在基站布局的時候就要求基站不能處在同一高度平面，基站間的水平高度差值如果太小會對最終標(biāo)簽Z軸的定位精度產(chǎn)生很大的干擾，所以為保證三維坐標(biāo)的精確度，可以通過優(yōu)化基站的幾何分布，來提高標(biāo)簽垂直方向上的定位精度。但在實(shí)際的室內(nèi)環(huán)境下，受室內(nèi)高度限制，最小二乘法定位算法將無法滿足三維定位精度的要求。為了降低最小二乘法對于基站幾何布局的依賴性，基于最小二乘定位算法，選擇由二維到三維分步求解的方式來實(shí)現(xiàn)三維坐標(biāo)的定位。

在不考慮基站水平高度差對定位精度帶來的影響的情況下，為保證系數(shù)矩陣不為奇異矩陣的同時，基站的水平高度差值可取得相對小一點(diǎn)，將基站布置在近似相同的水平高度上，如圖2所示。

圖2 室內(nèi)基站分布

已知基站A、B、C、D的坐標(biāo)分別為(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)、(x4,y4,z4)，分別測得它們與標(biāo)簽p點(diǎn)(xp,yp,zp)之間的距離為d1、d2、d3、d4。根據(jù)最小二乘法可以求得標(biāo)簽p的二維坐標(biāo)(xp,yp)，假設(shè)標(biāo)簽與不同基站之間的水平高度差值為Δhi,i=1,2…；則Δhi可由式(13)求得：

(13)

由式(14)可得標(biāo)簽的高度坐標(biāo)hi：

hi=zi-Δhi

(14)

同理，可分別根據(jù)不同的基站坐標(biāo)對標(biāo)簽高度進(jìn)行求解，最后通過利用不同基站求得的標(biāo)簽高度取平均值，便可得到標(biāo)簽近似精確的三維坐標(biāo)p(xp,yp,zp)：

(15)

3.2 實(shí)驗(yàn)分析

為驗(yàn)證優(yōu)化算法的定位表現(xiàn)，選取12個標(biāo)簽將其均勻分布于15*6.5*4.5的室內(nèi)環(huán)境中，標(biāo)簽坐標(biāo)分別為(3.59,2.64,1.12),(2.74,3.98,0.87),(1.95,5.64,1.90),(7.87,2.43,2.35),(7.21,4.30,1.81),(8.17,5.86,1.50),(10.2,1.98,2.88),(11.02,3.53,2.56),(9.78,6.06,1.25),(12.77,2.59,0.56),(13.50,4.33,2.01),(14.66,6.18,3.14)。

室內(nèi)設(shè)置4個基站節(jié)點(diǎn)，進(jìn)行最小二乘法定位實(shí)驗(yàn)，基站坐標(biāo)設(shè)置為(15,0,3.25),(0,0,4.5), (0,6.5,3.25),(15,6.5,4.5)，相鄰基站間水平高度差值為1 m；利用最小二乘定位算法進(jìn)行定位，每個標(biāo)簽進(jìn)行1 000次的定位測試，表1為1 000次實(shí)驗(yàn)結(jié)果的平均值。

表1 最小二乘法定位算法實(shí)驗(yàn)結(jié)果 m

優(yōu)化最小二乘法定位實(shí)驗(yàn)中，基站坐標(biāo)設(shè)置為(15,0,4.25),(0,0,4.5),(0,6.5,4.25),(15,6.5,4.5)，相鄰基站間水平高度差值為0.25 m；每個標(biāo)簽進(jìn)行1 000次的定位測試，表2數(shù)值為1 000次實(shí)驗(yàn)結(jié)果的平均值。

表2 優(yōu)化的最小二乘定位算法實(shí)驗(yàn)結(jié)果 m

從表1和表2所得到的實(shí)驗(yàn)結(jié)果可知，最小二乘定位算法求得的坐標(biāo)最小誤差值為0.785 m，最大誤差值為1.048 m，平均誤差值為0.897 m；而文中提出的優(yōu)化最小二乘定位算法的最小誤差值為0.226 m，最大誤差值為0.362 m，平均誤差值為0.279 m。受基站水平高度差值影響，最小二乘定位算法在工作過程中定位誤差波動比較大，定位效果不佳；相比于直接利用最小二乘法求解三維定位坐標(biāo)，文中提出的優(yōu)化最小二乘定位算法在定位精度提升68.90%，穩(wěn)定性提升52.90%，兩種算法的定位誤差曲線如圖3所示?？梢妰?yōu)化后的定位算法定位誤差明顯要低，且誤差曲線趨于平穩(wěn)狀態(tài)。

圖3 誤差曲線

4 結(jié)束語

文中提出的基于最小二乘法的定位優(yōu)化處理算法在一定程度上解耦了室內(nèi)三維坐標(biāo)定位精度對于基站幾何布局的依賴關(guān)系。通過構(gòu)建實(shí)驗(yàn)?zāi)Ｐ?，對算法進(jìn)行實(shí)驗(yàn)分析，對比實(shí)驗(yàn)結(jié)果能夠看出，優(yōu)化后的最小二乘定位算法在定位精度方面性能提升了64.28%，穩(wěn)定性方面性能提升了60.32%，由此證明該方法能夠顯著降低室內(nèi)三維定位精度對于基站幾何布局的依賴性，提高了三維坐標(biāo)定位精度，定位效果明顯優(yōu)于未優(yōu)化前的定位方法。