一種基于幾何精度因子的三維室內定位方案

楊明 劉中令 俞暉

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

關鍵詞：

室內定位； 幾何精度因子（GDOP）； 雙圓錐構型； 錨節點布置

中圖分類號： TN 929.5文獻標志碼： 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-），男，碩士研究生，主要從事室內定位和無人機自組織網絡方面的研究.Email：648121252@sjtu.edu.cn

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

*通信作者

引用格式： 楊明，劉中令，俞暉.一種基于幾何精度因子的三維室內定位方案 [J].上海師范大學學報（自然科學版），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引言

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

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

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

1GDOP

1.1GDOP介紹和推導

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

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

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

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

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

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）

根據協方差的定義，

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）式反映了測距誤差與定位誤差之間的映射關系.測距誤差相同，定位誤差僅與（HTH）-1的值有關.文獻[13]將GDOP定義為定位誤差的均方根（RMS）與測距誤差均方根的比值，

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

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

1.2GDOP定理

定理1

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

定理2

[14]當錨節點的構型固定時，各點的GDOP是一個連續函數.

由定理2可知在給定場景中，當錨節點構型固定時，GDOP的分布呈一系列有規律的同心圓.

2室內定位方案

2.1雙圓錐構型

根據（9）式可知定位誤差由測距誤差和由（HTH）-1導出的GDOP共同決定.而GDOP僅與錨節點的幾何構型有關，當錨節點放置完畢后，定位場景各點處的GDOP為常量.

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

2.2節點布置方案

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

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

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

GDOP=1VΩGDOPdV.（11）

由圖2可知GDOP密度與雙圓錐構型的圓錐張角密切相關，而且構型的中心點的GDOP與構型的GDOP密度的趨勢相似.圖2的結果表明GDOP密度在圓錐張角在35°～70°范圍內取到的值較小.因此，應確保所要構建的雙圓錐構型的圓錐張角在合適的區間內，如果張角值超出了區間，應調整長方體空間的大小，直到新的張角值落在合適區間內.

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

圖3為錨節點數和平均定位誤差的關系曲線.根據圖3可以發現定位精度會隨著錨節點數的增加而提高，但是增量在遞減，因此，在設計室內定位系統時，應該平衡定位精度和支出的關系.

3仿真結果及分析

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

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

為了讓仿真環境更接近于真實場景，選擇與距離相關的非對稱雙指數測距誤差模型進行分析[17]，該模型的表達式為：

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為配置參數，這些參數的值決定了仿真環境的信道質量.

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

4結束語

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

參考文獻：

[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]薛樹強，楊元喜，陳武，等.正交三角函數導出的最小GDOP定位構型解集 [J].武漢大學學報（信息科學版），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.

（責任編輯：包震宇，顧浩然）