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

引言

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

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

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

1模型建立與求解

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

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

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

根據(jù)弦交點法預(yù)測初始坐標值；

用變尺度法對初始值進行迭代精化，提高定位精度。

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

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

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

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

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

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

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

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

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

1.3弦交點法初步定位

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

為在不影響精度的情況下簡化計算，可以選擇其中三個不等式組成方程組式(5),選擇的標準就是提出距離值最大的一個。原因是：若參考節(jié)點組成的區(qū)域為矩形區(qū)域，待測節(jié)點與某一參考節(jié)點距離最大，則必定在另外三個參考節(jié)點組成的三角形中。

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

1.4變尺度法(DFP)精化

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

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

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

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

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

2.1實驗環(huán)境

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

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

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

2.2定位結(jié)果

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

表1環(huán)境實驗結(jié)

注:誤差是指兩點冋的距離

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

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

圖4倉庫環(huán)境中實驗結(jié)果對比圖

4結(jié)語

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

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