一種改進的Eddystone?TLM質心室內三邊定位算法

周杰 楊帆 李均濤

摘 ?要： 為了解決在室內環境中利用三邊定位技術定位精度不高，以及基于質心定位改進三邊定位算法后參考點難以確定在待測點外側的問題，提出一種利用Eddystone?TLM對三邊定位算法進行改進。首先利用Eddystone框架的TLM優化質心定位算法;其次通過優化后的質心定位算法解決三邊定位算法已知的不足;最終實現定位精度的提高。實驗結果表明，該算法改善了室內定位的精準性，可及時準確地獲取目標終端的位置數據，有效保證了室內定位與其他領域之間定位數據的互聯互通。

關鍵詞： 室內定位; Eddystone?TLM; 三邊定位算法; 質心定位; 仿真實驗; 誤差分析

中圖分類號： TN141.2?34; TP301.6 ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）02?0179?03

An improved indoor trilateral localization algorithm based on Eddystone?TLM centroid

ZHOU Jie， YANG Fan， LI Juntao

Abstract： An improved trilateral localization algorithm based on Eddystone?TLM is proposed to solve the low accuracy of positioning with the trilateral localization technology in the indoor environment and the problem that it is difficult to determine the reference point outside the point to be measured by means of the improved trilateral localization algorithm based on the centroid localization. First， the TLM of the Eddystone frame is used to optimize the centroid localization algorithm， by which the known deficiency of the trilateral localization algorithm is solved to realize the improvement of the localization accuracy. The experimental results show that this algorithm can improve the accuracy of the indoor localization， and obtain the localization data of the target terminal timely and accurately， which effectively ensures the data interconnection between indoor localization and other field localization.

Keywords： indoor localization; Eddystone?TLM; trilateral localization algorithm; centroid localization; simulation experiment; error analysis

0 ?引 ?言

定位即是獲取目標的位置信息，以實現目標位置的及時追蹤以及信息的傳輸。在定位技術還未成熟階段，定位主要應用在室外條件下，室內環境并未得以應用，而室內定位是指在非室外環境下獲取目標位置，結合無線通信、基站定位等技術實現室內位置的定位，從而實現對室內環境中目標位置的追蹤。

隨著室內定位技術的不斷發展，諸如藍牙、WiFi、質心定位、三邊定位等技術，彌補了在室內環境中衛星無法實現定位的缺陷，解決了衛星無法穿透障礙物，信號衰減等無法實現室內定位的問題。由此相關學者、企業將定位技術的發展方向延伸到室內定位中，實現了在室內環境下對目標位置獲取以及信息的推送。而定位的方法也具有多樣性，主要有按距離定位的、參考點定位的、特征匹配（由先驗的數據支撐當前的定位）等方式。

現階段，一部分學者利用三邊定位技術實現室內環境下目標定位[1]，但其存在定位精度不高的問題;另一部分學者利用質心定位算法優化三邊定位[2?4]，改善了精度不高的缺陷，但在參考點選擇過程中，卻無法保證其處于質心的外側。這將是決定優化算法能否執行的關鍵一步，為了確保其定位精度，本文提出利用Eddystone?TLM來確定參考節點的新思路。

1 ?算法分析

1.1 ?技術介紹

1.1.1 ?Eddystone?TLM

Eddystone是一種低功耗藍牙技術，其采用廣播的方式發送特定的ID，接收到該ID的設備將發送反饋信號。在此過程中，由于Eddystone結構段的段尾框架中分為4種不同的框架，每個框架可以生成4種數據包，以4種不同數據包的形式實現Eddystone 4種不同的功能，分別為UID，URL，TLM，EID[5?6]。TLM表示遙測管理，在Eddystone中，TLM主要起到管理的作用，通過這一框架可實現對Beacon設備數據的記錄與管理[7]，記錄信號強度參數并根據信號強度準確選取定位所需參考節點。

1.1.2 ?三邊定位技術

所謂三邊定位技術，是利用三邊測量（Trilateration）原理實現，是數學學科上測量位置的一種，即選取三個基站，以基站為圓心，并以基站到待測終端的距離為半徑畫圓，建立方程即可求解出待測終端的位置，多應用在室內定位中。三邊定位算法由兩部分組成：測距階段（測量基站到待測終端距離的確定）與定位階段（待測點最終位置的確定）。

1.2 ?三邊定位算法的改進

三邊定位算法根據測距階段與定位階段可測量出待測點的位置。但由于信號在傳輸過程中存在損耗，影響了測距階段的數值準確度，難以產生三圓相交的結果，主要原因是在測距階段存在誤差。針對此問題，本文提出一種利用Eddystone?TLM對三邊定位算法進行改進。該方法首先利用Eddystone框架的TLM優化質心定位算法，其次通過優化后的質心定位算法解決三邊定位算法已知的不足。

所謂的質心定位算法，指的是待測點通過記錄的形式判斷周圍的參考點（基站），并將這些參考點組成多邊形來估算自身的位置。質心定位算法原理圖如圖1所示。

假設待測節點T記錄的一組參考節點為P1（X1，Y1），P2（X2，Y2），…，Pn（Xn，Yn），則待測節點T計算公式為：

[X，Y=1ni=1nXi，1ni=1nYi] ? （1）

雖然質心定位算法思想簡單，能夠解決一定的問題，但在提高待測點的高精度方面，需要大量的參考節點作為支撐，這也是其最大的弊端。針對待測點外圍參考節點的選取問題，前文已介紹Eddystone的TLM框架，Eddystone?TLM可針對信號強度實時管理Beacon設備，并以信號強度的大小對Beacon進行排序。可將Eddystone?TLM引入到質心定位算法中，解決參考節點密度大難以選取的問題。

首先，上文中提到待測點記錄外側的參考節點，并組成多邊形來估算自身的位置，這是產生質心定位算法無法提高定位精度的問題根源。現通過Eddystone?TLM來記錄參考節點的信號強度，待測點通過信號強度來確定參考節點，確保參考節點位于其外側，且可保證參考節點至少在3個以上。改進后的質心定位算法示意圖如圖2所示。可選取的參考節點即為圖中組成三角形區域的節點P1，P3，P4。

其次，將改進后質心定位算法應用到三邊定位算法中，可提高待測點T的精確度。具體的實現過程如下，將已選取的參考節點（基站）P1，P3，P4的坐標代入到式（2）～式（4）：

[（x0-x1）2-（y0-y1）2=d21] ? ?（2）

[（x0-x2）2-（y0-y2）2=d22] ? （3）

[（x0-x3）2-（y0-y3）2=d23] ? （4）

計算出三圓兩兩相交的交點，然后分別將交點代入式（5）中：

[（X-Xi）2+（Y-Yi）2] ? ? ?（5）

分別求出兩點中距離圓心B1最近的點[（Xb2b3，Yb2b3）]，兩點中距離圓心B2最近的點[（Xb1b3，Yb1b3）]，兩點中距離圓心B3最近的點[（Xb1b2，Yb1b2）]。最后通過將[（Xb2b3，Yb2b3）]，[（Xb1b3，Yb1b3）]，[（Xb1b2，Yb1b2）]代入到式（1）中，得到如下結果：

[（x0，y0）=13（Xb2b3+Xb1b3+Xb1b2），13（Yb2b3+Yb1b3+Yb1b2）]

最后可計算出待測點T的準確位置。

1.3 ?實驗結果與分析

本文用Matlab 2012b進行仿真實驗，實驗在12 m×12 m的區域里，通過對算法進行仿真，分別實現利用或未利用Eddystone?TLM情況下待測點實際位置與估算位置的情況。由圖3可發現，在未利用Eddystone?TLM情況下，實際與估算之間存在明顯的誤差，而在利用Eddystone?TLM的情況下，實際位置與估算位置幾乎零誤差，如圖4所示。

由實驗結果可以看出，引入Eddystone?TLM優化質心三邊定位算法可有效提升定位的精度。

2 ?結 ?論

針對三邊定位在室內環境下定位精度不高的問題，本文基于三邊定位算法提出改進版的三邊定位算法，即由Eddystone四種框架中的Eddystone?TLM優化質心定位算法，并將優化后的算法引入到三邊定位算法中，實現定位精確度的提高。最終改善室內定位的精準性，及時準確地獲取目標終端的位置數據，也有效保證了室內定位與其他領域之間定位數據的互聯互通。這對改善室內環境下難以獲取用戶行為數據方面具有重要的意義。

參考文獻

[1] 藍威濤，張衛強，羅健宇.一種自適應智能三邊定位算法的設計與實現[J].傳感技術學報，2017，30（7）：1089?1094.

[2] 藍茂俊，陳正銘，戴經國，等.基于質心的改良WiFi三邊定位算法設計與分析[J].軟件工程，2016，19（11）：1?3.

[3] 王艷麗.基于藍牙信標和指紋庫匹配的室內定位算法研究[D].重慶：重慶理工大學，2017.

[4] 陸霞.WiFi定位技術：基于質心定位的三邊定位算法的研究[J].電腦知識與技術，2013（25）：5765?5767.

[5] STIAN Sandve. Indoor positioning system using BLE beacons [D]. Stavanger： University of Stavanger， 2016.

[6] PR Newswire. Swirl announces support for Eddystone??EID beacon format from Google [N]. PR Newswire， 2016?04?14 （10）.

[7] AKINSIKU A， JADAV D. BeaSmart： A beacon enabled smarter workplace [C]// IFIP Network Operations and Management Symposium. Istanbul： IEEE， 2016： 1269?1272.

[8] PROF S P B， NEELAY R W， YASH R S， et al. Indoor navigation system with augmented reality using Eddystone beacons [J]. International education & research journal， 2017， 12（3）： 10?12.

[9] KATEVAS K， HADDADI H， TOKARCHUK L. SensingKit： evaluating the sensor power consumption in iOS devices [C]// 2016 12th International Conference on Intelligent Environments. London： IEEE， 2016： 222?225.

[10] NICK J， TIM Z. Best practices to select an IoT beacon implementation： google Eddystone versus apple iBeacon [EB/OL]. [2016?08?05]. https：//www.gartner.com/en/documents/3402517.