劉中令, 徐超杰, 俞　暉

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

?

基于測距的定位系統(tǒng)中位置解算研究

劉中令, 徐超杰, 俞暉

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

摘要:在現(xiàn)有的基于測距的位置解算算法中,定位精度受測距誤差的影響較大.為了提高定位精度,提出了一種基于根心的位置解算算法.該算法中,首先根據(jù)位置未知的節(jié)點(diǎn)(Target節(jié)點(diǎn))與每三個位置已知的節(jié)點(diǎn)(Anchor節(jié)點(diǎn))之間的距離測量值,計算出對應(yīng)的根心坐標(biāo);在根心集合中,濾除誤差較大的部分根心;根據(jù)剩余根心的坐標(biāo)及其權(quán)重值,計算平均值作為解算結(jié)果.仿真結(jié)果表明,在相同的誤差下,提出的位置解算算法相比于現(xiàn)有的基于測距的位置解算算法有效地降低了解算誤差,提高了定位精度.

關(guān)鍵詞:位置解算算法; 根心; Anchor節(jié)點(diǎn); Target節(jié)點(diǎn)

0概述

隨著GPS系統(tǒng)、北斗系統(tǒng)以及伽利略系統(tǒng)等衛(wèi)星系統(tǒng)基本解決室外定位的問題,越來越多的人開始關(guān)注室內(nèi)定位.但是,由于衛(wèi)星信號在室內(nèi)衰減非常嚴(yán)重,同時室內(nèi)環(huán)境復(fù)雜,對衛(wèi)星信號有很大的干擾,所以通過衛(wèi)星信號定位的方法不適于室內(nèi)情況.然而隨著通信技術(shù)、互聯(lián)網(wǎng)技術(shù)的高速發(fā)展,國內(nèi)外的研究者提出了很多基于短距離無線通信技術(shù)的定位方法,比如:WiFi[1]、藍(lán)牙[2]、Zigbee[3]、超寬帶[4](UWB)等,并且精度也在日漸提高.

在眾多室內(nèi)定位方法中,位置解算算法主要分為兩種算法:Range-free和Range-based.Range-free算法通過測量信號的Received Signal Strength Indication(RSSI)來估計被測物體位置,以基于WiFi的定位方法為代表.雖然定位精度無法很高,但使用WiFi的設(shè)備十分普遍,所以這種方法很受歡迎.Range-based算法是測量位置已知的節(jié)點(diǎn)和位置未知的節(jié)點(diǎn)之間的距離、角度或距離差,計算位置未知的節(jié)點(diǎn)相對位置已知的節(jié)點(diǎn)的坐標(biāo),從而得到位置未知的節(jié)點(diǎn)的位置信息.近幾年,隨著UWB技術(shù)被引入室內(nèi)定位,測量的距離的精度可以達(dá)到分米級甚至厘米級,Range-based算法的定位精度已經(jīng)可以做到很高,同時由于算法容易編程實現(xiàn),所以Range-based算法也十分受青睞,不過,Range-based算法對硬件設(shè)備的要求比Range-free算法更高.

本文作者將介紹一種基于根心的Range-based算法,并通過Matlab仿真實驗,將本文作者提出的算法與已有的Range-based定位解算算法進(jìn)行對比,觀察算法性能.

1基本算法介紹

1.1經(jīng)典算法介紹

設(shè)位置已知的節(jié)點(diǎn)(Anchor節(jié)點(diǎn))坐標(biāo)分別為(x1,y1)、(x2,y2)、…、(xn,yn),測量的位置未知的節(jié)點(diǎn)(Target節(jié)點(diǎn))到各個位置已知的節(jié)點(diǎn)的距離分別為d1、d2、…、dn.兩種經(jīng)典的算法如下.

1.1.1三邊測量法

選取3個Anchor節(jié)點(diǎn),其坐標(biāo)為(x1,y1)、(x2,y2)、(x3,y3),測量的Target節(jié)點(diǎn)到這3個Anchor節(jié)點(diǎn)之間的距離分別為d1、d2、d3,設(shè)Target節(jié)點(diǎn)坐標(biāo)為(x,y),可以得到表達(dá)式:

(1)

將式(1)化簡,可得:

(2)

求解式(2),即可得到三邊測量法的定位解算結(jié)果.

1.1.2極大似然估計法

選取n個Anchor節(jié)點(diǎn),可以得到表達(dá)式:

(3)

將式(3)化簡,可得:

(4)

將式(4)寫成矩陣的形式,即AX=b,其中:

極大似然估計法的解算結(jié)果為:

(5)

1.2根心介紹

1.2.1根心定理

定義1點(diǎn)對圓的冪:平面上一點(diǎn)P(x,y)對一個圓心為O(x0,y0),半徑為r的圓的冪為:

定義2根軸:對平面式2個不同心的圓等冪的點(diǎn)集稱為根軸.

根據(jù)上述定義,可以計算出2個不同心的圓的根軸.設(shè)2個不同心的圓的圓心分別為(x1,y1)、(x2,y2),半徑分別為r1、r2,這2個圓的根軸的表達(dá)式為:

定理1根心定理(蒙日定理):平面上任意3個圓,若這3個圓圓心不共線,則3條根軸相交于一點(diǎn),這個點(diǎn)叫它們的根心;若3圓圓心共線,則3條根軸互相平行.

1.2.2計算根心

設(shè)3個兩兩不同心的圓的圓心分別為(x1,y1)、(x2,y2)、(x3,y3),半徑分別為r1、r2、r3,根據(jù)定義2可以得到3條根軸的表達(dá)式:

(6)

假設(shè)3條根軸兩兩相交,根據(jù)定理1,則3條根軸必相交于一點(diǎn),所以,選取式(1)中的前兩個方程,可得:

(7)

根據(jù)克萊姆法則,可以計算出根心坐標(biāo):

(8)

2算法改進(jìn)

2.1算法模型

2.2選取根心坐標(biāo)

設(shè)3個圓心不共線的圓,其圓心分別為O1、O2、O3,半徑分別為r1、r2、r3,這3個圓在平面上的相交情況有以下幾種情況:

如圖1所示.

圖1　平面上3個圓相交的情況示意圖

根據(jù)根心定理,由于3個圓的圓心不共線,可知以上4種情況,根心都必定存在,以圖1(1)為例,根心如圖2所示.

圖2　根心示意圖

設(shè)計算出的根心為P(xp,yp),圓Oi(圓心為Oi(xi,yi),半徑為ri,i=1,2,3)與射線OiP相交于點(diǎn)Qi,可以得到Qi的坐標(biāo)為:

(9)

圖3　交點(diǎn)構(gòu)成的三角形及其外接圓示意圖

由3個圓的圓心坐標(biāo)和半徑可以算出3個交點(diǎn)坐標(biāo),再根據(jù)這3個交點(diǎn)坐標(biāo),可以得到一個以這3個交點(diǎn)為頂點(diǎn)的三角形以及三角形的外接圓,如圖3所示.

在定位算法中,圓心坐標(biāo)為Anchor節(jié)點(diǎn)的坐標(biāo),圓的半徑為測距值,可以由式(8)得到根心坐標(biāo),由式(9)得到3個交點(diǎn)的坐標(biāo).經(jīng)過仿真實驗,3個交點(diǎn)構(gòu)成的三角形面積與三角形外接圓半徑之比和定位解算精度成正相關(guān),所以,認(rèn)為交點(diǎn)構(gòu)成的三角形面積與三角形外接圓半徑之比越大,所對應(yīng)的根心坐標(biāo)誤差越小.

2.3算法流程

第二步:根據(jù)式(9)計算出以Anchor節(jié)點(diǎn)為圓心Oi(xi,yi)、Anchor節(jié)點(diǎn)與Target節(jié)點(diǎn)間的測距值為半徑ri的圓與射線OiP的交點(diǎn)Qi(xQi,yQi).

第三步:由3個交點(diǎn)Q1、Q2、Q3可以圍成一個三角形和三角形的外接圓,計算三角形面積S和外接圓半徑r.

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

3.1仿真實驗

本文作者提出了一種基于根心的位置解算算法,為了評估算法性能,采用Matlab進(jìn)行實驗仿真,并與其他幾種算法進(jìn)行對比,觀察提出的算法的優(yōu)化幅度.從文獻(xiàn)[5]中可知,在視距情況下,測距誤差的分布呈高斯分布,所以仿真實驗中所加噪聲為高斯噪聲.仿真實驗的相關(guān)參數(shù)如下:假設(shè)定位范圍是20m×20m,Anchor節(jié)點(diǎn)的總數(shù)量為10個,Anchor節(jié)點(diǎn)彼此之間都可以通信并且不存在3個共線的Anchor節(jié)點(diǎn),Target節(jié)點(diǎn)的數(shù)量為1個,Target節(jié)點(diǎn)與Anchor節(jié)點(diǎn)之間的距離加上高斯噪聲作為測量值,通過更改測距誤差最大值觀察算法性能.

評估算法性能使用如下的定位誤差公式:

(10)

其中,(xTarget,yTarget)為Target節(jié)點(diǎn)的實際坐標(biāo),(x,y)為解算坐標(biāo).式(10)表示的是解算出的坐標(biāo)與Target節(jié)點(diǎn)實際坐標(biāo)之間的距離.

仿真實驗中使用的算法包括:極大似然估計法[6]:使用10個Anchor節(jié)點(diǎn)的坐標(biāo)和10個Anchor節(jié)點(diǎn)與Target節(jié)點(diǎn)之間的測距值,由式(5)計算出解算坐標(biāo);文獻(xiàn)[7]中的基于根心的位置解算算法(以下簡稱根心法);優(yōu)化算法:保留較大的10%的W值對應(yīng)的根心坐標(biāo),求其加權(quán)平均值作為解算結(jié)果.

3.2實驗結(jié)果分析

基于3.1中的仿真環(huán)境,本實驗對上述3種算法:極大似然估計法、根心法以及優(yōu)化算法進(jìn)行仿真,結(jié)果如圖4所示.

圖4　仿真結(jié)果

如圖4仿真結(jié)果所示,測距誤差最大值由0 m增大至2 m.從圖4中可以看出,優(yōu)化算法相比極大似然估計法有了顯著提高,通過計算,定位精度提高了60%;相比根心法,優(yōu)化算法也有明顯提高,通過計算,定位精度提高了28%.同時,是仿真實驗中,優(yōu)化算法的定位誤差始終小于1 m,定位精度可以達(dá)到分米級,可見優(yōu)化算法的改進(jìn)幅度很大.

4結(jié)束語

本文作者研究了一種基于根心的位置解算算法:將Anchor節(jié)點(diǎn)每三個一組,計算出對應(yīng)的根心坐標(biāo);計算3個圓心到根心的射線與圓的交點(diǎn),可以得到一個以3個交點(diǎn)為頂點(diǎn)的三角形以及三角形的外接圓;計算三角形面積與外接圓半徑之比,將其作為權(quán)值;保留較大權(quán)值對應(yīng)的根心坐標(biāo),求其平均值作為解算結(jié)果.通過仿真實驗,本文作者將優(yōu)化算法與極大似然估計法、文獻(xiàn)[7]中的根心法進(jìn)行對比,實驗結(jié)果表明,優(yōu)化算法相比上述兩種算法有了很大改善,定位精度有顯著提高.

參考文獻(xiàn):

[1]Niu J W,Wang B W,Cheng L,et al.WicLoc:an indoor localization system based on WiFi fingerprints and crowdsourcing [C]//IEEE.2015 IEEE International Conference on Communications(ICC).London:IEEE,2015.

[2]Oksar I.A Bluetooth signal strength based indoor localization method [C]//IEEE.2014 International Conference on Systems,Signals and Image Processing(IWSSIP).Dubrovnik:IEEE,2014.

[3]Hu X,Cheng L L,Zhang G C.A Zigbee-based localization algorithm for indoor environments [C]//IEEE.2011 International Conference on Computer Science and Network Technology(ICCSNT).Harbin:IEEE,2011.

[4]Irahhauten Z,Nikookar H,Klepper M.A joint ToA/DoA technique for 2D/3D UWB localization in indoor multipath environment [C]//IEEE.2012 IEEE International Conference on Communications(ICC).Ottawa:IEEE,2012.

[5]Chehri A,Fortier P,Tardif P M.UWB-based sensor networks for localization in mining environments [J].Ad Hoc Networks,2009,7(5):987-1000.

[6]Huang Y F,Jheng Y T,Chen H C.Performance of an MMSE based indoor localization with wireless sensor networks [C]//IEEE.2010 Sixth International Conference on Networked Computing and Advanced Information Management(NCM).Seoul:IEEE,2010.

[7]Chen Y S,Chin C C,Deng D J.Efficient localization algorithm in wireless ad hoc sensor networks by utilizing radical centers [C]//IEEE.2012 IEEE International Conference on Communications(ICC).Ottawa:IEEE,2012.

(責(zé)任編輯：顧浩然)

Study on position computing in range-based localization system

LIU Zhongling, XU Chaojie, YU Hui

(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

Abstract:In the existing range-based position computing algorithm,the localization accuracy is greatly influenced by the error of measured distance.In order to improve the localization accuracy,this paper presents an optimized indoor localization algorithm based on radical center.In the algorithm,firstly,calculating the radical center bases on the measured distance between every three anchor nodes and the target node.Then,percentage of the radical centers in the set which have large localization error are filtered out.Finally,computing the average of the remaining radical centers′ coordinates as the result bases on their weight.The result of simulation showed that compared with the existing range-based position computing algorithm,the presented position computing algorithm reduces the localization error and improves the localization accuracy effectively.

Key words:position computing algorithm; radical center; anchor node; target node

中圖分類號:TN 929.5

文獻(xiàn)標(biāo)志碼:A

文章編號:1000-5137(2016)02-0209-06

通信作者:俞暉,中國上海市閔行區(qū)東川路800號,上海交通大學(xué)電子信息與電氣工程學(xué)院,郵編:200240,E-mail:yuhui@sjtu.edu.cn.

收稿日期:2016-03-04