一種提高室內(nèi)定位精度的算法

引言

室內(nèi)定位技術(shù)是物聯(lián)網(wǎng)感知層的基礎(chǔ)支撐技術(shù)，因其可以提供室內(nèi)物品的與位置相關(guān)的信息，贏得了廣大學(xué)者的關(guān)注和研究。同時(shí)隨著物聯(lián)網(wǎng)相關(guān)概念的推廣，室內(nèi)物品的聯(lián)網(wǎng)與定位開始提出了新的需求與挑戰(zhàn)，即更加便捷的部署方式、更高精度的定位信息。采用室內(nèi)定位系統(tǒng)，可以實(shí)現(xiàn)室內(nèi)物品的實(shí)時(shí)在線、遠(yuǎn)程監(jiān)管，使得物聯(lián)網(wǎng)從理論概念走到現(xiàn)實(shí)世界中。

完整的室內(nèi)定位系統(tǒng)一般包括室內(nèi)定位技術(shù)、室內(nèi)定位算法、數(shù)據(jù)管理軟件和硬件設(shè)備等。其中定位算法是核心,定位算法的精度是決定系統(tǒng)實(shí)施與應(yīng)用的關(guān)鍵。根據(jù)定位過程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，把算法分為：基于距離的(Range-Based)算法和距離無關(guān)的(Range-Free)算法。距離無關(guān)的定位機(jī)制只利用節(jié)點(diǎn)間的連通性來估測(cè)自身的位置，用最優(yōu)化方法來提高定位精度，比較經(jīng)典的算法如凸規(guī)劃算法和MDS-MAP算法，但整體的精度沒有基于距離的定位算法高，雖然有些算法利用了循環(huán)方式來提高精度，然而應(yīng)用的范圍遠(yuǎn)不及前者。因而基于距離的定位機(jī)制，因具有高精度、部署方便和組網(wǎng)靈活的特點(diǎn)，備受研究者們的關(guān)注。

本文研究重點(diǎn)是基于距離的室內(nèi)定位算法。根據(jù)定位算法原理，定位精度主要受兩個(gè)因素影響:距離測(cè)算與坐標(biāo)計(jì)算。本工作建立基于距離的坐標(biāo)估計(jì)、計(jì)算模型，采用數(shù)值分析理論對(duì)距離進(jìn)行誤差補(bǔ)償，利用運(yùn)籌學(xué)方法對(duì)初步定位結(jié)果做進(jìn)一步的求精，并通過模擬實(shí)驗(yàn)驗(yàn)證算法精度。

1模型建立與求解

提高基于距離的室內(nèi)定位算法精度存在兩個(gè)難點(diǎn)：距離數(shù)據(jù)的處理和坐標(biāo)值的推導(dǎo)，本節(jié)所述模型將通過以下4個(gè)步驟完成對(duì)原始距離值的統(tǒng)計(jì)、還原，初始坐標(biāo)的預(yù)測(cè)與進(jìn)一步精化：

利用最小二乘估計(jì)準(zhǔn)則求解距離的統(tǒng)計(jì)優(yōu)化值；

通過三次樣條插值優(yōu)化距離值，提高測(cè)距精度；

根據(jù)弦交點(diǎn)法預(yù)測(cè)初始坐標(biāo)值；

用變尺度法對(duì)初始值進(jìn)行迭代精化，提高定位精度。

1.1最小二乘求解距離的統(tǒng)計(jì)值

從終端獲取某個(gè)點(diǎn)的n次待測(cè)節(jié)點(diǎn)到4個(gè)參考節(jié)點(diǎn)的距離信息：

然后求使(1)式取最小值的di作為此刻的最優(yōu)估計(jì)值。

1.2三次樣條插值優(yōu)化距離值

三次樣條插值基于樣條曲線，樣條曲線實(shí)際上是由分段三次曲線并接而成，在連接點(diǎn)即樣點(diǎn)上要求二階導(dǎo)數(shù)連續(xù)，從概念上概括就得到數(shù)學(xué)中的三次樣條函數(shù)這一概念。把(1)式得出的最優(yōu)值dt通過三次樣條插值擬合運(yùn)算，使之更加接近真實(shí)值，即對(duì)距離進(jìn)行“求真運(yùn)算”該方法主要設(shè)計(jì)以下關(guān)鍵步驟：

（1）確定邊界條件：邊界條件設(shè)置為y'1=1，y'n=1，即假定測(cè)量值和真實(shí)值是相一致的；

（2）計(jì)算：構(gòu)造滿足步驟1邊界條件的三次樣條插值函數(shù)；

（4）把結(jié)果代入步驟2內(nèi)即可。實(shí)驗(yàn)時(shí)，在范圍50m以內(nèi)選取了10個(gè)點(diǎn)進(jìn)行實(shí)際的測(cè)量，以此10點(diǎn)數(shù)據(jù)進(jìn)行插值求解關(guān)系表達(dá)式，然后，選取額外的15點(diǎn)進(jìn)行插值計(jì)算，求插值后的距離值。得出實(shí)際距離、測(cè)試距離和插值距離的關(guān)系如圖1所示。

由圖1可以看出,經(jīng)過插值之后得出距離非常接近真實(shí)值,誤差的絕對(duì)值丨知哄1<0.6m，可為下一步的坐標(biāo)計(jì)算提供較精確的數(shù)值輸入。

1.3弦交點(diǎn)法初步定位

由三次樣條插值得出待測(cè)節(jié)點(diǎn)與各個(gè)參考節(jié)點(diǎn)的距離dge，(i=1,2,3,4)之后，以參考節(jié)點(diǎn)為圓心、待測(cè)節(jié)點(diǎn)到參考節(jié)點(diǎn)的距離為半徑作圓，初步判定待測(cè)點(diǎn)在4個(gè)圓所交的公共區(qū)域U內(nèi)，即X。eU,并有不等式方程組式(4)成立,其中(x,y)為第i個(gè)參考節(jié)點(diǎn)的坐標(biāo)。

為在不影響精度的情況下簡(jiǎn)化計(jì)算，可以選擇其中三個(gè)不等式組成方程組式(5),選擇的標(biāo)準(zhǔn)就是提出距離值最大的一個(gè)。原因是：若參考節(jié)點(diǎn)組成的區(qū)域?yàn)榫匦螀^(qū)域，待測(cè)節(jié)點(diǎn)與某一參考節(jié)點(diǎn)距離最大，則必定在另外三個(gè)參考節(jié)點(diǎn)組成的三角形中。

(5)為了在待選區(qū)域U選擇合適的迭代初始值，該算法思路是：兩圓相交必有公共弦，三圓相交則有三條公共弦，此三條公共弦L1，L2,L3必相交于一點(diǎn)。(x,y),可由三條公共弦的直線方程聯(lián)立方程組進(jìn)行證明，就以此交點(diǎn)作為迭代初始值X0(x0,y0)°

1.4變尺度法(DFP)精化

分析不等式方程組式(4),在該方程組的解空間中找出在一定準(zhǔn)則下的理論最優(yōu)值，可以把此方程組轉(zhuǎn)換為無約束最優(yōu)化問題。

于是，設(shè)有以下求極小值問題：

由最優(yōu)估計(jì)理論分析可知，該無約束極小值問題的最優(yōu)解滿足不等式方程組式(4),把該解作為初始點(diǎn)求精后的最優(yōu)值。對(duì)無約束極小值問題式(6)的求解，可采用變尺度法(DFP法)，該方法是求解無約束極值問題的一種有效方法[12]。由于它避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過程，又比梯度法的收斂速度快，特別是對(duì)高維問題具有顯著優(yōu)越性，因此可以對(duì)該問題進(jìn)行有效求解。

DFP法主要涉及兩個(gè)主要的算法，分別是利用黃金分割法進(jìn)行一維捜索和利用DFP法計(jì)算最小點(diǎn)對(duì)應(yīng)的自變量的值。其中，DFP算法流程如圖2所示：其中s為控制誤差,X。為輸入的初始值,E是與X。同維的單位矩陣。黃金分割法流程如圖3所示。

2算法驗(yàn)證與結(jié)果分析

2.1實(shí)驗(yàn)環(huán)境

為驗(yàn)證本算法的定位精度，選取并設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)場(chǎng)景來模擬不同環(huán)境。理想環(huán)境:驗(yàn)證定位算法在無信號(hào)折射反射、視距傳播的環(huán)境中的定位精度；復(fù)雜環(huán)境：驗(yàn)證定位算法在室內(nèi)(封閉環(huán)境)受多徑影響下的定位精度。

理想環(huán)境：室外較寬闊空間，在50X50m2的空曠場(chǎng)地上選取4.8X10.8m2的一個(gè)矩形區(qū)域作為測(cè)試范圍，周圍除了自然輻射以外沒有額外影響射頻信號(hào)發(fā)射、傳播、接收的電磁波。參考節(jié)點(diǎn)和待測(cè)節(jié)點(diǎn)放在離地面約3m的位置。

復(fù)雜環(huán)境：封閉的倉(cāng)庫(kù)環(huán)境，在10X8m2的倉(cāng)庫(kù)內(nèi)對(duì)選取4.8X10.8m2的一個(gè)矩形區(qū)域作為測(cè)試范圍，除了室內(nèi)的信號(hào)傳播造成的多徑現(xiàn)象，無其他額外信號(hào)干擾，參考節(jié)點(diǎn)同樣放置在離地面3m的地方。

2.2定位結(jié)果

理想環(huán)境中，計(jì)算出的實(shí)驗(yàn)數(shù)據(jù)如表1所列。

表1環(huán)境實(shí)驗(yàn)結(jié)

注:誤差是指兩點(diǎn)冋的距離

由表1可發(fā)現(xiàn)，該算法在理想環(huán)境中能實(shí)現(xiàn)對(duì)待定目標(biāo)位置的估計(jì)，弦交點(diǎn)法初步定位的誤差在0.68m以內(nèi)，而經(jīng)過DFP法精化后，誤差縮小到在0.22m以內(nèi)，達(dá)到了提高精度的目的。同時(shí)經(jīng)過實(shí)驗(yàn)，由弦交點(diǎn)預(yù)估出的初始坐標(biāo)，可以明顯縮短DFP迭代次數(shù)并節(jié)約算法整體運(yùn)行時(shí)間。

復(fù)雜環(huán)境中，測(cè)出的距離數(shù)據(jù)經(jīng)過DFP求精計(jì)算后的坐標(biāo)比初始坐標(biāo)也有更好的精度，最優(yōu)情況能達(dá)到0.22m，而在矩形區(qū)域的邊緣部分精度有所下降，控制在0.8m以內(nèi)，如圖4所示。

圖4倉(cāng)庫(kù)環(huán)境中實(shí)驗(yàn)結(jié)果對(duì)比圖

4結(jié)語(yǔ)

本文把三次樣條插值算法和DFP迭代算法引入到室內(nèi)定位算法的距離補(bǔ)償和坐標(biāo)的精化運(yùn)算，并通過模擬實(shí)驗(yàn)對(duì)本算法進(jìn)行了實(shí)現(xiàn)與驗(yàn)證。從算法研究和實(shí)驗(yàn)數(shù)據(jù)分析可以看出，DFP精化算法確實(shí)提高了定位精度?；诒舅惴Ｐ偷木_室內(nèi)定位技術(shù)結(jié)合計(jì)量檢測(cè)技術(shù)、GIS技術(shù)、網(wǎng)絡(luò)傳輸技術(shù)和云計(jì)算技術(shù)等技術(shù)，可以搭建一個(gè)集實(shí)時(shí)監(jiān)控和信息管理于一體的管理平臺(tái)，一改傳統(tǒng)人工操作規(guī)程，保障物資安全，真正達(dá)到室內(nèi)物品實(shí)時(shí)、有效監(jiān)控和管理的目的。

20211118_619644fd9f0bf__一種提咼室內(nèi)定位精度的算法