幾何估算和RSSI相結合的室內定位算法

徐 馳 邱 添 曹廣成

1(上海應用技術大學 上海 201418)2(上海京頤科技股份有限公司 上海 200240)

幾何估算和RSSI相結合的室內定位算法

徐 馳1邱 添2曹廣成1

1(上海應用技術大學 上海 201418)2(上海京頤科技股份有限公司 上海 200240)

提出一種基于幾何估算和RSSI相結合的定位方法。方法中，未知節點的位置可以通過參考節點的通信范圍進行幾何估算。參考節點的通信重疊區域可以估算出未知節點位置。在幾何估算方法的基礎上又引入了RSSI值優化。利用RSSI值對幾何估算區域進行劃分，運用改進公式計算出新的未知節點位置。實驗結果表明，該方案優于基礎定位算法，擁有較高的精度。同時在醫院場景進行了初步系統測試，獲得了良好的定位效果。

幾何估算 接收信號強度 室內定位

0 引 言

近年來，硬件技術的發展促使微型化傳感器設備通信能力的提升。無線傳感網絡是由大量的無線傳感器對空間進行數據檢測、信息收集。因此，無線傳感網可以進行實時數據采集、分析、監控和即時響應時間。由于上述優勢，無線傳感網成為了目前一個非常活躍的研究課題，在諸如醫療、工業、樓宇自動化、環境監測和商品位置跟蹤等領域廣泛運用。節點定位是無線傳感網絡中最重要的問題之一。因為位置信息在許多基于位置的服務和應用中扮演重要的角色。例如，當火災或者搶劫事件發生在無線傳感器網絡環境中，為了處理此事件，可能需要知道處理此事件傳感器節點的位置。GPS是非常有用的定位技術。但是在很多情況下，由于節點的便捷性與能耗無法用GPS和其他定位儀器滿足所有情況。因此，如何在不使用GPS技術的情況下解決傳感器位置問題變得非常重要。

為了有效解決室內定位這一難題，各種新型室內定位技術層出不窮。如藍牙定位技術(谷歌方案)、紅外定位技術[1]、地磁定位技術[2](IndoorAtlas方案)、UWB定位技術[3]、3G/4G信號定位技術[4](Qubulus方案)、WiFi定位技術[5]、LiFi定位技術[6]、WiMax定位技術[7]、ZigBee定位技術[8]等。其中藍牙[9]、WiFi、ZigBee[10]等技術應用最為廣泛，地磁、LiFi等技術是異軍突起的新技術。為了降低硬件成本，進而提出了基于非測距的定位。其無需專用測距、測角度的硬件設施與基于測距的定位相比成本更低、復雜度更小。但是目前大多數的基于非測距的定位仍然成本高且定位精度偏低。

本文提出了一種基于幾何估算和RSSI相結合的定位算法，利用參考節點幾何估算方案[11]的幾何測算，RSSI值方案的距離計算，綜合考量環境等多種因素，從而實現高精度的室內定位系統。需要事先設定參考節點與未知節點的參數信息，同時算法只需知道各節點之間RSSI大小的關系，而并不關心RSSI值具體的數值，所以所付出的硬件代價較小。下面將對算法進行詳細的介紹。

1 相關工作

室內定位技術很多，根據其定位采用的方案可以分為兩種：基于測距和基于非測距的定位技術。基于測距的方案需要計算得到兩個通信節點之間的距離信息或者角度信息，通過得到的位置信息計算未知節點的坐標[12]。基于非測距的方案則利用節點和網絡的自身屬性對未知節點的位置進行估算[13]。

1.1 基于測距定位方案

基于測距定位利用節點間的距離或角度信息來計算位置節點位置。典型的方案如到達時間(TOA[14])、到達時差(TDOA)[15]、到達角度(AOA)和接收信號強度(RSSI)[16]。TOA通常是測量范圍內兩個通信節點之間信號傳播時間。一般使用超聲波此類低速信號。TDOA與TOA非常相似，它利用不同速度的兩個信號到達時間差來計算距離。AOA是通過估計相鄰節點之間的相對角度。其最初被廣泛應用于蜂窩網絡，要求每個接收器都必須具備額外的天線才能檢測到發射器的信號。RSSI是目前最廣泛、最低廉的距離測量方案。接收機接收信號的RSSI值后通過信號傳播衰減模型計算出距離。但是，在實際環境中由于許多不可預測的因素，如噪聲、信號干擾、多徑傳播延遲等，使用RSSI進行距離估計往往是不準確的。上述基于測距定位方案需要一些額外的昂貴、復雜的硬件設施，因此這樣的定位方案不適合網絡資源有限的無線傳感器網絡。

1.2 基于非測距定位方案

基于非測距定位方案不需要任何時間、角度、信號強度等數據。文獻[17]通過鄰居節點的位置信息并利用質心公式來估計未知節點的位置。其主要依靠鄰居節點的數量來提升定位精度，在鄰居節點數量少時精度很低。這類利用通信重疊區域的非測距定位方案被稱為幾何估算方法。DV-Hop的定位方案[18]是利用無線網絡自身的屬性來測定距離，其核心思想是用網絡數據每跳的距離和參考節點到未知節點跳數的乘積，表示參考節點到未知節點的距離。未知節點的位置計算依靠參考節點的位置、跳數、每一跳平均距離等參數。APIT算法[19]核心思想是未知節點從它所有通信的參考節點中選擇三個參考節點，計算它是處于這三個參考節點組成的三角形內部還是外部，然后再選擇其他三個參考節點進行同樣的計算，直到計算完所有的三角形組合或者達到設定的閾值，最后未知節點將包含其所有的三角形的相交區域的質心作為自己的估計位置。

2 定位算法

2.1 幾何估計算法

幾何估算方法其主要是利用參考節點與未知節點之間所處于的幾何位置關系對未知節點位置進行估算。其幾何描述如圖1所示。本文排除了未知節點僅被一個參考節點所感知的情況，因為上文利用參考節點的位置擺放已經有效地預防了該極端情形。圖1描述的是未知節點只被兩個參考節點所感知，其中A1和A2為參考節點，圓形位置為未知節點M的實際位置，方形位置為未知節點M的估算位置。

圖1 未知節點被兩個參考節點感知

其方法過程描述如下，首先參考節點必須具備相同的通信半徑R，且不能移動。未知節點被兩參考節點感知，說明其存在于兩參考節點通信圓重疊部分。但重疊部分為凸型結構無法估算未知節點幾何位置。兩通信圓的交點分別為點E和點F。已知參考節點A1和A2的坐標分別為(x1,y1)和(x2,y2)，列方程求解得到E和F的坐標分別為(xe,ye)和(xf,yf)。計算公式(1)如下所示：

(1)

圖形中點A、點B、點C和點D分別是直線A1E、A2E、A1F和A2F與兩圓的交點，通過式(2)計算出點A的坐標，同理可以計算出點B、點C和點D的坐標。

(2)

通過聯立直線和圓的方程能計算出兩個A的坐標，去除在A1通信圓之外的坐標，剩余的則為A點的坐標。得到A-F點的坐標后構造出一個多邊形，這個多邊形的質心則為幾何估計法的未知節點位置。未知節點的坐標如式(3)所示：

(3)

下面介紹另一種情況，未知節點被三個參考節點所感知。同時特例的情況是未知節點被多個參考節點所感知后，根據實現設置好的閾值選取最優的前三個參考節點進行定位計算。未知節點被三個參考節點定位的效果如圖2所示。還有一種三個參考節點通信區域幾乎重疊的文章并未給出，因為此種情況無法進行定位，且在參考節點位置布置階段已經剔除此種可能。在理論模型當中，參考節點均勻分布，且重疊區域處于三個通信圓的中間位置。圖2中圓形代表未知節點的實際位置，方形代表未知幾點的估計位置。

圖2 未知節點被三個參考節點感知

已知參考節點A1、A2、A3的坐標分別為(x1,y1)、(x2,y2)、(x3,y3)，其通信圓兩兩之間的交點為A、B、C，坐標計算公式如下：

(4)

解方程可得A的坐標為(xa,ya)和(xa′,ya′)，濾除不在A1通信范圍內的點，最終得到A的坐標為(xa,ya)。同理可以計算出B和C的坐標，分別為(xb,yb)和(xc,yc)。最終利用幾何估算方法，未知節點M的坐標為(xm,ym)：

(5)

2.2 幾何估算和RSSI值結合算法

2.2.1 前置條件

第一是網絡中參考節點的功率必須相同。在幾何估算方法中需要使用參考節點的通信半徑進行換算，而通信半徑與參考節點的功率之間有關系。前期需要實驗室測量節點的通信半徑。實驗室測量的通信半徑和理論通信半徑誤差在30 cm內為標準。參考節點的功率與參考節點的電源供給和天線功率正比關系。所以本文中所有參考節點電源全部采用220 V轉5 V供電。使用PCB天線和2.4G無線技術。

第二是網絡中參考節點的位置擺放。參考節點數量少于3個時，未知節點定位誤差特別大或無法定位。參考節點擺放過密時，網絡通信冗余，網絡質量下降，網絡定位的實時性下降。在定位系統實施需要進行參考節點位置擺放的設計與實施。保障整個網絡中未知節點都能被三個以上的參考節點掃描。

第三是對RSSI值的修正。基于RSSI值定位算法在網絡運行過程中每個節點對收集的RSSI值也需要進行修正，去除波動和奇異值點。文獻[18，19]中利用卡爾曼濾波、最小均方差等方法對RSSI值進行處理。文章運用最簡單的方法對RSSI值進行處理。每個節點收集3個RSSI值，然后利用均值法去除波動。

第四是對RSSI值的排序。RSSI值的排序分為兩部分，一部分是未知節點的排序。未知節點在收到三個以上參考節點的信息后，針對RSSI值小的前三個參考節點進行組網通信。因為RSSI值越小說明參考節點與未知節點的距離越近，所以篩選出未知節點最近的前三個參考節點作為定位算法的前置條件。另一部分是上位機軟件對參考節點接收到未知節點的RSSI值進行排序。該排序的作用是為了減少幾何估算的區域，提高算法的精度。

2.2.2 算法模型

未知節點被兩個參考節點所掃描。如圖3所示是兩個參考節點的模型。其中未知節點的實際位置為圓形點。方形點是幾何估算方法的估算點。

圖3 兩參考節點模型

根據未知節點與參考節點的實際位置可知RSSIA1>RSSIA2。實際位置中未知節點離參考節點A1更近。所以連接EF將多邊形ABCDEF分為兩個部分，而未知節點處于多邊形AEFC的概率大于未知節點處于多邊形EBDF的概率。所以幾何估算只需要在左邊圖形當中進行，能夠有效地減少定位誤差。圖中所示方形為優化后的估計位置，很明顯誤差減少了一半。改進后的未知節點M的坐標如式(6)所示：

(6)

如圖4所示是三個參考節點的模型。其中圓形是未知節點的實際位置，方形是未知節點的估計位置。上位機收集了參考節點與未知節點的RSSI值，并對三個RSSI值進行排序。排序結果為RSSIA1>RSSIA3>RSSIA2。排序結果可知未知節點離參考節點A1最近，其次是參考節點A3，最后是參考節點A2。

圖4 三參考節點模型

C、H是圓A1和圓A2的交點，A、G是圓A2和圓A3的交點，B、I是圓A3和圓A1的交點。連接CH、AG、BI將三圓重疊部分分割成6個區域。我們將其中的1、2區域劃分到圓A1的范圍內，3、4區域劃分到圓A2的范圍內，5、6區域劃分到圓A3的范圍內。根據上文當中的排序，未知節點最靠近參考節點A1，所以先把未知節點的區域劃分到靠近參考節點A1的1、2區域。然后進行下一步判斷，未知節點比較靠近參考節點A3，所以將未知節點的區域劃分到靠近參考節點A3的1區域。所以未知節點最后的估算區域為1區域。1區域的質心坐標即為未知節點的估計坐標。

各點坐標計算過程如下：

A、G點的坐標計算如式(7)所示：

(7)

B、I點的坐標計算如式(8)所示：

(8)

O點的坐標計算如式(9)所示：

(9)

D點的坐標計算如式(10)所示：

(10)

最后通過質心算法求出未知節點的坐標。上述方法是將幾何估算方法的估算區域縮小至之前的六分之一。在此基礎上繼續加入構造三角形優化進一步提高算法的精度。連接A1A2、A2A3、A3A1后形成構造三角形，將陰影部分縮小如圖5所示，形成了新的陰影區域1、2、3、4、5、6。經過構造三角形優化過后的算法比優化之前的精度進一步提高。縮小了估算范圍，最終利用質心法得出了未知節點的坐標。最終估算坐標與實際坐標非常接近，誤差很小。

圖5 構造三角形優化

3 仿真實驗與實際檢測

3.1 仿真實驗與分析

利用Matlab仿真軟件將本文算法與基于RSSI值方法、幾何估算方法進行對比。分別就定位算法的精度和穩定性做了詳細的仿真測試，下面分別介紹仿真測試的結果。

設置參考節點的通信半徑為10 m，參考節點數量50個，未知節點數量50個隨機分布在網絡當中。定位范圍為50 m×50 m的正方形區域。圖中“+”表示未知節點的實際位置，“*”表示未知節點的估計位置。圖6是RSSI方法的仿真結果。圖7是幾何方法的仿真結果。圖8是本文方法的仿真結果。RSSI方法定位精度的波動很大，在某些區域內參考節點分布密集，定位效果好，某些區域內參考節點分布稀疏，定位效果差。幾何方法定位的精度普遍偏低，在整個覆蓋范圍內定位誤差較大，但受參考節點分布影響較小，比較穩定。本文算法效果較好，定位精度和穩定性較之RSSI方法和幾何方法都有提升。保留了RSSI方法的定位精度，幾何方法的穩定性。

圖6 RSSI方法仿真結果

圖7 幾何方法仿真結果

圖8 本文方法仿真結果

選取10～100個參考節點，10～100個未知節點，通信半徑為5 m，在50 m×50 m的方形范圍內進行定位測試。設置實際位置與估計未知距離在2 m內的為定位成功。圖9中是仿真結果，橫坐標為節點數量，縱坐標為定位成功率。RSSI方法隨著節點數量的增加定位效果產生波動，但整體維持在80%水平。幾何方法定位精度隨著節點的增加而提高。節點數量為10個是定位精度只有30%。隨著節點的數量增加，幾何方法中覆蓋區域越來越小所以定位精度越來越高。本文方法不受節點數量的影響，維持在90%的水平。

圖9 參考節點數量變化

選取20個參考節點與20個未知節點，節點通信半徑在1～10 m內變化，在10 m×10 m的方形范圍內進行定位測試。設置實際位置與估計未知距離在2 m內的為定位成功。橫坐標為節點通信半徑，縱坐標為定位成功率。如圖10所示隨著節點的通信半徑逐漸增大，RSSI方法和幾何方法的定位精度逐漸減小。節點通信半徑越大，未知節點能夠監測到的參考節點越多，參考節點越多，在密集的區域內會影響定位精度。本文方法限制了未知節點監測的參考節點數量，參考節點的上線數量為3個，所以并不受此干擾因素的影響。

圖10 參考節點通信半徑變化

3.2 醫院場景運行檢測

如圖11所示中紅圈內為實際定位產品。其功能是保障醫療器械、醫院資產的安全，監控醫療設備的使用情況等。

圖11 實際產品圖

幾何方法在實際運用當中定位精度遠遠不能滿足商業需求，所以這里并沒用將幾何方法加入實際檢測當中。圖12中RSSI方法的實際運用，采用的是三邊定位方法。其中方形點表示的是醫療器械的估計位置。我們在處置室存放了11臺醫療設備，每個設備都貼有定位產品。通過圖很明顯能夠看出11臺設備處于5個不同的位置，但是實際情況是11臺設備都處于同一地點。產生此類現象的原因是醫院環境內參考節點都布置在樓層的集成吊頂內，未知節點處于房間內。未知節點與參考節點不處于同一個平面；未知節點與參考節點中間間隔兩堵墻；未知節點與參考節點之間存在大量人員流動。所以上位機收集的RSSI值一直處于變動狀態，導致了多個節點的定位錯誤。

圖12 基于RSSI值定位效果

圖13是改進后的基于RSSI值定位算法。對RSSI值進行了濾波、去抖，去除了奇異值點和擾動。圖中6個未知節點都處于同一位置，但圖中仍然顯示了6個未知節點處于4個不同的地方。但圖中很明顯看到誤差范圍減小，未知節點的誤差區域縮小了。去除了環境因素的影響可以提高定位精度。但此種定位精度仍然不能滿足實際運用的需求。

圖14中是采用了本文算法后的定位效果截圖。兩個未知節點擺放在護士站附近位置，實際位置與估計位置誤差1 m左右，定位精度可以滿足實際運用需求。

圖14 基于本文方法定位效果

4 結 語

本文提出了一種幾何估算與RSSI值相結合的定位算法。有效彌補了幾何估算方法的不足。并進行了仿真測試和實際測試。與RSSI方法和幾何方法進行了詳細的對比和分析。結果表明本文方法要優于其他兩種定位方法。定位精度和穩定性都有顯著的提升。在實際運用當中也取得了良好的定位效果。

[1] Want R,Hopper A,Falcao V,et al. The active badge location system[J]. ACM Transactions on Information Systems, 1992, 10(1):91-102.

[2] 楊云濤, 石志勇, 關貞珍,等. 地磁場在導航定位系統中的應用[J]. 中國慣性技術學報, 2007, 15(6):686-692.

[3] 劉琪, 閆麗, 周正. UWB的技術特點及其發展方向[J]. 現代電信科技, 2009, 39(10):6-10.

[4] 易前旭. 移動蜂窩網絡的無縫切換技術[J]. 無線互聯科技, 2014(7):32-32.

[5] 張利. 基于WiFi技術的定位系統的設計與實現[D]. 北京：北京郵電大學，2009.

[6] 林琪. “LiFi”,讓燈泡變成無線路由[J]. 環境, 2013(11):77-79.

[7] 王茜, 王巖.無線城域網WiMAX技術及其應用[J].電信科學, 2004, 20(8)：27-30.

[8] 周怡颋, 凌志浩, 吳勤勤.ZigBee無線通信技術及其應用探討[J].自動化儀表, 2005, 26(6)：5-9.

[9] 馬建倉, 羅亞軍, 趙玉亭.藍牙核心技術及應用[M].北京: 科學出版社, 2003.

[10] 蔣挺, 趙成林. 紫蜂技術及其應用[M].北京：北京郵電大學出版社, 2006.

[11] 任克強, 莊放望. 移動錨節點凸規劃定位算法研究及改進[J]. 傳感技術學報, 2014(10)：1406-1411.

[12] 周怡颋, 凌志浩, 吳勤勤. ZigBee無線通信技術及其應用探討[J].自動化儀表, 2005, 26(6)：5-9.

[13] 彭宇, 王丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報, 2011, 25(5)：389-399.

[14] Blanco L, Serra J, Najar M. SPC12-2: Low Complexity Toa Estimation for Wireless Location[C]// Global Telecommunications Conference, 2006. GLOBECOM’06, San Francisco, Ca, Usa, 27 November-1 December. DBLP, 2006:1-5.

[15] 史小紅.基于TDOA的無線定位方法及其性能分析[J].東南大學學報, 2013, 43(2)：252-257.

[16] 方震, 趙湛, 郭鵬, 等.基于RSSI測距分析[J].傳感器學報, 2007, 20(11)：2526-2530.

[17] 陳維克,李文鋒,首珩, 等.基于RSSI的無線傳感器網絡加權質心定位算法[J]. 武漢理工大學學報(交通科學與工程版), 2006, 32(2): 265-268.

[18] Li J, Zhang J, Xiande L. A Weighted DV-Hop Localization Scheme for Wireless Sensor Networks[C]// International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded Computing. IEEE Computer Society, 2009:269-272.

[19] Zhou Y, Ao X, Xia S. An improved APIT node self-localization algorithm in WSN[C]// Intelligent Control and Automation, 2008. Wcica 2008. World Congress on. IEEE, 2008:7582-7586.

INDOOR LOCATION ALGORITHM BASED ON GEOMETRICAL ESTIMATION AND RSSI

Xu Chi1Qiu Tian2Cao Guangcheng1

1(ShanghaiInstituteofTechnology,Shanghai201418,China)2(ShanghaiKyeeCo.,LTD,Shanghai200240,China)

This paper presents a new method based on geometric estimation and RSSI. The location of the unknown node can be estimated by the communication range of the reference node. An unknown node location can be estimated by reference to the communication overlap area of the node. The RSSI value optimization is introduced based on the geometric estimation method. The RSSI value is used to divide the geometric estimation region, and the new unknown node position is calculated by using the improved formula. The experimental results show that the proposed scheme is superior to the basic localization algorithm and has a high accuracy. At the same time, a preliminary system test is conducted in the hospital scene which gets a good positioning effect.

Geometrical estimation RSSI Indoor localization

2016-05-15。徐馳，碩士，主研領域：室內定位。邱添，學士。曹廣成，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.06.053