一種基于幾何精度因子的三維室內(nèi)定位方案

楊明 劉中令 俞暉

摘要： 提出了一種基于幾何精度因子（GDOP）的三維室內(nèi)定位方案來解決室內(nèi)定位系統(tǒng)中的錨節(jié)點布置問題.通過該方案可以得到錨節(jié)點的雙圓錐構(gòu)型.利用兩種測距誤差模型來對該方案的性能進(jìn)行評估，仿真結(jié)果表明該方案可以應(yīng)用于大小不同的場景，而且在相同的定位場景下，該方案的定位精度優(yōu)于現(xiàn)有的布置方法.

關(guān)鍵詞：

室內(nèi)定位； 幾何精度因子（GDOP）； 雙圓錐構(gòu)型； 錨節(jié)點布置

中圖分類號： TN 929.5文獻(xiàn)標(biāo)志碼： A文章編號： 10005137（2018）02018606

A geometric dilution of precision based 3D indoor positioning scheme

Yang Ming， Liu Zhongling， Yu Hui*

（School of Electronic Information and Electrical Engineering，Shanghai Jiao Tong University，Shanghai 200240，China）

Abstract：

A geometric dilution of precision（GDOP） based 3D indoor positioning scheme was proposed for the layout of anchor nodes.Through the proposed scheme，the biconical configuration could be obtained.The performance of the scheme was evaluated by utilizing two different ranging error models.Simulation results indicated that the scheme can be applied to various scenes with different sizes.Furthermore，the proposed scheme had considerable accuracy improvement in the same positioning environment compared with existing layout scheme.

Key words：

indoor positioning； geometric dilution of precision（GDOP）； biconical configuration； layout of anchor nodes

收稿日期： 20180131

作者簡介： 楊明（1995-），男，碩士研究生，主要從事室內(nèi)定位和無人機(jī)自組織網(wǎng)絡(luò)方面的研究.Email：648121252@sjtu.edu.cn

導(dǎo)師簡介： 俞暉（1969-），男，高級工程師，主要從事無線通信技術(shù)方面的研究.Email：yuhui@sjtu.edu.cn

*通信作者

引用格式： 楊明，劉中令，俞暉.一種基于幾何精度因子的三維室內(nèi)定位方案 [J].上海師范大學(xué)學(xué)報（自然科學(xué)版），2018，47（2）：186-191.

Citation format： Yang M，Liu Z L，Yu H.A geometric dilution of precision based 3D indoor positioning scheme [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：186-191.

0引言

近年來，室內(nèi)定位的相關(guān)應(yīng)用得到了飛速發(fā)展，火災(zāi)救援[1]，博物館導(dǎo)游[2]，超市導(dǎo)航[3]等場景都需要室內(nèi)定位技術(shù)的支持.通常，定位系統(tǒng)中使用幾何精度因子（GDOP）來衡量定位精度[4]，對于GDOP的最小化研究也在衛(wèi)星的選擇和水下定位中得到應(yīng)用[5-6].GDOP的大小僅與錨節(jié)點的構(gòu)型有關(guān)，在室內(nèi)定位系統(tǒng)中，可以通過計算GDOP來分析錨節(jié)點構(gòu)型對定位精度的幾何影響.

基于GDOP的室內(nèi)定位已經(jīng)得到了廣泛研究，許多研究都將GDOP視作一個指標(biāo)來評估定位算法或系統(tǒng)[7-9].文獻(xiàn)[10]提出了一種可以用于二維場景下的基于GDOP的室內(nèi)定位方法.文獻(xiàn)[11]通過對GDOP的分析得到一系列場景簡潔的，能用來設(shè)計追蹤系統(tǒng)的解析表達(dá)式.文獻(xiàn)[12]則使用GDOP來確保定位系統(tǒng)中錨節(jié)點的構(gòu)型是高質(zhì)量的.盡管之前的研究已經(jīng)解決了很多室內(nèi)定位的問題，但是很少有文獻(xiàn)借助GDOP或者其他指標(biāo)的幫助提出具體的三維室內(nèi)定位解決方案，研究者們也很少關(guān)注給定場景的最優(yōu)錨節(jié)點構(gòu)型.

本文作者基于雙圓錐構(gòu)型，提出適用于三維場景的布置錨節(jié)點方案.使用兩種測距誤差模型（高斯測距誤差模型和與距離相關(guān)的非對稱雙指數(shù)誤差模型）對該定位方案的性能進(jìn)行評估.仿真結(jié)果表明該方案可以應(yīng)用于大小不同、信道條件不同的場景，而且定位精度均優(yōu)于現(xiàn)有的定位方法.

1GDOP

1.1GDOP介紹和推導(dǎo)

假設(shè)有N個錨節(jié)點，其中第i個錨節(jié)點（i=1，2…，N，N>3）的坐標(biāo)為（Xi，Yi，Zi），定位目標(biāo)的坐標(biāo)為（X，Y，Z）.那么第i個錨節(jié)點與定位目標(biāo)之間的距離

Pi=（X-Xi）2+（Y-Yi）2+（Z-Zi）2.（1）

由于噪聲（如測距誤差）的影響，實測的目標(biāo)位置和真實的位置之間會有偏差，將實測的定位目標(biāo)的坐標(biāo)設(shè)為（Xu，Yu，Zu），第i個錨節(jié)點和實測的定位目標(biāo)位置的距離為

Pui=（Xu-Xi）2+（Yu-Yi）2+（Zu-Zi）2.（2）

假定定位誤差相比于整個定位空間的尺度相對較小，對（1）式，在定位目標(biāo)實測位置使用泰勒展開，取一階近似，可得：

Pi=Pui+PiXXu（X-Xu）+PiYYu（Y-Yu）+PiZZu（Z-Zu）.（3）

測距誤差dP=[dP1，dP2，…，dPi]T，其中dPi=Pi-Pui，定位誤差dL=[dX，dY，dZ]T，其中dX=X-Xu，dY=Y-Yu，dZ=Z-Zu.再定義

H=P1XXuP1YYuP1ZZuPNXXuPNYYuPNZZu=aX1aY1aZ1aXNaYNaZN，（4）

其中aXi=Xi-XuPui，aYi=Yi-YuPui，aZi=Zi-ZuPui，則

HdL=dP.（5）

由于N>3，（5）式是一個超定線性方程組，能夠通過最小二乘法求解：

dL=（HTH）-1HTdP.（6）

根據(jù)協(xié)方差的定義，

cov（dL）=E（dLdTL）=（HTH）-1HTE（dPdTP）H（HTH）-1.（7）

假定在同一場景下，測距誤差dP各分量同分布.因此，

E（dPdTP）=Iδr2，（8）

其中δr為測距誤差因子，I是一個單位矩陣，則

cov（dL）=（HTH）-1HTIδr2H（HTH）-1=δr2（HTH）-1.（9）

（9）式反映了測距誤差與定位誤差之間的映射關(guān)系.測距誤差相同，定位誤差僅與（HTH）-1的值有關(guān).文獻(xiàn)[13]將GDOP定義為定位誤差的均方根（RMS）與測距誤差均方根的比值，

GDOP=Tr（（HTH）-1），（10）

其中Tr（·）表示一個矩陣主對角線上元素的總和.

1.2GDOP定理

定理1

[14]當(dāng)且僅當(dāng)HTH=nIm，n個錨節(jié)點在m維空間中的幾何精度因子GDOP（n，m）能得到最小值mn，其中m表示維度（m=2或3），n是錨節(jié)點數(shù)（n>3）.

定理2

[14]當(dāng)錨節(jié)點的構(gòu)型固定時，各點的GDOP是一個連續(xù)函數(shù).

由定理2可知在給定場景中，當(dāng)錨節(jié)點構(gòu)型固定時，GDOP的分布呈一系列有規(guī)律的同心圓.

2室內(nèi)定位方案

2.1雙圓錐構(gòu)型

根據(jù)（9）式可知定位誤差由測距誤差和由（HTH）-1導(dǎo)出的GDOP共同決定.而GDOP僅與錨節(jié)點的幾何構(gòu)型有關(guān)，當(dāng)錨節(jié)點放置完畢后，定位場景各點處的GDOP為常量.

根據(jù)定理2可以推出：如果定位場景中心的GDOP是最小的，那么場景中其他點的GDOP也是相對均勻和相對小的.為了最小化定位場景整體的GDOP，采用一種雙圓錐構(gòu)型，如圖1所示，該構(gòu)型由一個正圓錐和一個倒圓錐組成，連接處是兩個圓錐的頂點.雙圓錐構(gòu)型在定位場景的中心處的GDOP可以達(dá)到或接近理論最小值，文獻(xiàn)[15]證明了當(dāng)圓錐張角為54.7°時，雙圓錐構(gòu)型中心處的GDOP可以達(dá)到理論最小值3n.

2.2節(jié)點布置方案

提出一種基于雙圓錐構(gòu)型的室內(nèi)定位方案來布置錨節(jié)點，由于定位空間的尺度不是非常大，時間誤差忽略不計.

在布置錨節(jié)點之前，構(gòu)建一個長方體空間，其長度與寬度相同，需要定位的區(qū)域包含于長方體空間內(nèi).當(dāng)長方體空間確定后，可以求出所要構(gòu)建的雙圓錐構(gòu)型的圓錐張角，通過圓錐張角的大小可以判斷所要構(gòu)建的雙圓錐構(gòu)型是否適用于定位.圖2為圓錐張角與GDOP之間的關(guān)系.

如圖2所示，用GDOP密度來評估三維場景下室內(nèi)定位方案的性能，該指標(biāo)定義為三維場景中各點GDOP的均值，即

GDOP=1VΩGDOPdV.（11）

由圖2可知GDOP密度與雙圓錐構(gòu)型的圓錐張角密切相關(guān)，而且構(gòu)型的中心點的GDOP與構(gòu)型的GDOP密度的趨勢相似.圖2的結(jié)果表明GDOP密度在圓錐張角在35°～70°范圍內(nèi)取到的值較小.因此，應(yīng)確保所要構(gòu)建的雙圓錐構(gòu)型的圓錐張角在合適的區(qū)間內(nèi)，如果張角值超出了區(qū)間，應(yīng)調(diào)整長方體空間的大小，直到新的張角值落在合適區(qū)間內(nèi).

選擇長方體空間的上下平面中的一個平面（正方形），將任意一個錨節(jié)點放在該平面的一條邊的中心上，將另外2個錨節(jié)點放在以正方形邊長為直徑，平面中心為圓心的圓周上.調(diào)整圓周上2個錨節(jié)點的位置，使得同一平面上的3個錨節(jié)點組成等邊三角形，構(gòu)成的三角形的中心即上下平面的中心.上下平面兩個對應(yīng)的點的連線應(yīng)該穿過長方體空間的中心.以圖1為例，錨節(jié)點1對應(yīng)錨節(jié)點6，錨節(jié)點2對應(yīng)錨節(jié)點5，錨節(jié)點3對應(yīng)錨節(jié)點4，長方體空間的中心為坐標(biāo)軸的原點.如果存在多余錨節(jié)點，應(yīng)盡可能放置于靠近長方體空間中心的位置，這樣可以有效提高定位精度.

圖3為錨節(jié)點數(shù)和平均定位誤差的關(guān)系曲線.根據(jù)圖3可以發(fā)現(xiàn)定位精度會隨著錨節(jié)點數(shù)的增加而提高，但是增量在遞減，因此，在設(shè)計室內(nèi)定位系統(tǒng)時，應(yīng)該平衡定位精度和支出的關(guān)系.

3仿真結(jié)果及分析

根據(jù)GDOP的定義和定理1，在錨節(jié)點數(shù)一定且測距誤差的均方根值給定的情況下求得理論上最小的定位誤差.在仿真中，使用6個錨節(jié)點并且選用高斯測距誤差模型，選擇一個長方體空間作為待定位空間，該長方體空間的大小是可變的.此外，將測距誤差的均方根值設(shè)為0.03.因此，可以得到理論上最小的定位誤差值為0.212 m.將提出的定位方案與文獻(xiàn)[16]所提方案進(jìn)行比較.文獻(xiàn)[16]所提方案的構(gòu)型如圖4所示，該構(gòu)型由6個錨節(jié)點構(gòu)成，其中2個錨節(jié)點位于上下平面的中心，余下4個錨節(jié)點放置在空間中，與上下平面平行，且位于上下平面中間的矩形平面的4個頂點上.定位精度的仿真結(jié)果如圖5所示.

圖5中，x軸的角度值為arctanac，其中a為待測空間的長度，c為待測空間的高度，該角度值可以歸一化地表示長方體空間的大小.而且雙圓錐構(gòu)型的圓錐張角也與該角度值相一致.圖5展示了兩種布置方法的定位精度，并且將平均定位誤差與理論最小定位誤差作比較.從圖5中，可以發(fā)現(xiàn)文獻(xiàn)[16]所提方案在較小的角度定位精度較好，但是在本方案中，需要調(diào)整長方體空間的尺寸使圓錐張角落在合適的區(qū)間，當(dāng)張角較小時，誤差較大的情況可以得到解決.在其他圓錐張角區(qū)間，提出的方案明顯優(yōu)于文獻(xiàn)[16]所提方案，定位精度提升15%左右.另一方面，在合適的區(qū)間里，本方案的定位誤差接近于理論上最小的定位誤差.

為了讓仿真環(huán)境更接近于真實場景，選擇與距離相關(guān)的非對稱雙指數(shù)測距誤差模型進(jìn)行分析[17]，該模型的表達(dá)式為：

PADE（d，r）=

1λp（r）+λN（r）exλN（r），x≤0

1λp（r）+λN（r）e-xλp（r），x≥0

，（13）

式中λp（r）=apr+bp，λN（r）=aNr+bN，d是測距誤差，r是測量的距離，ap，bp，aN，bN為配置參數(shù)，這些參數(shù)的值決定了仿真環(huán)境的信道質(zhì)量.

選擇兩個不同尺寸的長方體（空間的角度分別為40°與70°），比較兩種布置方法的定位精度.在仿真中，選擇多組不同的參數(shù)來確保仿真結(jié)果的準(zhǔn)確性和可信賴性，仿真結(jié)果如表1所示.對于不同的場景，所提方案均優(yōu)于現(xiàn)有的布置方法.另外，定位誤差值與測距誤差模型的參數(shù)密切相關(guān)，這也與GDOP的定義相吻合.仿真結(jié)果驗證了所提方案可以在各種大小、信道條件的場景下使用，且都可以獲得較好的定位精度.

4結(jié)束語

基于可以獲得較小GDOP的雙圓錐構(gòu)型，提出了一種室內(nèi)定位方案用于解決三維場景下的錨節(jié)點布置問題.分析和仿真結(jié)果表明該構(gòu)型的圓錐張角對定位誤差有直接的影響.調(diào)整雙圓錐構(gòu)型后該方案可應(yīng)用于不同大小的場景.另外，利用兩種不同的測距誤差模型來評估定位方案的性能，并與現(xiàn)有的布置方法進(jìn)行比較，在各種大小、信道條件下的場景中，所提定位方案均能得到更高的定位精度.

參考文獻(xiàn)：

[1]Moon G B，Hur M B，Jee G I.An indoor positioning system for a first responder in an emergency environment [C].Proceedings of the 12th International Conference on Control，Automation and Systems，JeJu Island：IEEE，2012.

[2]Kawaji H，Hatada K，Yamasaki T，et al.An imagebased indoor positioning for digital museum applications [C].Proceedings of the 16th International Conference on Virtual Systems and Multimedia，Seoul：IEEE，2010.

[3]Wirola L，Laine T A，Syrjrinne J.Massmarket requirements for indoor positioning and indoor navigation [C].Proceedings of 2010 International Conference on Indoor Positioning and Indoor Navigation，Zurich：IEEE，2010.

[4]Torrieri D J.Statistical theory of passive location systems [J].IEEE Transactions on Aerospace and Electronic Systems，1984，AES20（2）：183-198.

[5]Kihara M，Okada T.A satellite selection method and accuracy for the global positioning system [J].Navigation，1984，31（1）：8-20.

[6]Luo T J，Chen W J，Chen F J，et al.CramérRao bounds of source localization with distributed sensors in underwater multipath environment [C].Proceedings of 2016 Shanghai OCEANS.Shanghai：IEEE，2016.

[7]Feng G A，Shen C，Long C H，et al.GDOP index in UWB indoor location system experiment [C].Proceedings of 2015 IEEE Sensors，Busan：IEEE，2015.

[8]Rajagopal N，Chayapathy S，Sinopoli B，et al.Beacon placement for rangebased indoor localization [C].Proceedings of 2016 International Conference on Indoor Positioning and Indoor Navigation，Alcala de Henares：IEEE，2016.

[9]Anwar A K，Ioannis G，Pavlidou F N.Evaluation of indoor location based on combination of AGPS/HSGPS [C].Proceedings of the 3rd International Symposium on Wireless Pervasive Computing，Santorini：IEEE，2008.

[10]Kirchhof N.Optimal placement of multiple sensors for localization applications [C].Proceedings of 2013 International Conference on Indoor Positioning and Indoor Navigation，MontbeliardBelfort：IEEE，2013.

[11]Sharp I，Yu K，Guo Y J.GDOP analysis for positioning system design [J].IEEE Transactions on Vehicular Technology，2009，58（7）：3371-3382.

[12]Syafrudin M，Walter C，Schweinzer H.Robust locating using LPS LOSNUS under NLOS conditions [C].Proceedings of 2014 International Conference on Indoor Positioning and Indoor Navigation，Busan：IEEE，2014.

[13]Lee H B.A novel procedure for assessing the accuracy of hyperbolic multilateration systems [J].IEEE Transactions on Aerospace and Electronic Systems，1975，AES11（1）：2-15.

[14]Xue S Q，Yang Y X.Positioning configurations with the lowest GDOP and their classification [J].Journal of Geodesy，2015，89（1）：49-71.

[15]薛樹強(qiáng)，楊元喜，陳武，等.正交三角函數(shù)導(dǎo)出的最小GDOP定位構(gòu)型解集 [J].武漢大學(xué)學(xué)報（信息科學(xué)版），2014，39（7）：820-825.

Xue S Q，Yang Y X，Chen W，et al.Positioning configurations with minimum GDOP from orthogonal trigonometric functions [J].Geomatics and Information Science of Wuhan University，2014，39（7）：820-825.

[16]Zwirello L，Janson M，Ascher C，et al.Accuracy considerations of UWB localization systems dedicated to largescale applications [C].Proceedings of 2010 International Conference on Indoor Positioning and Indoor Navigation，Zurich：IEEE，2010.

[17]Li S H，Hedley M，Collings I B.New efficient indoor cooperative localization algorithm with empirical ranging error model [J].Journal on Selected Areas in Communications，2015，33（7）：1407-1417.

（責(zé)任編輯：包震宇，顧浩然）