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

劉中令, 徐超杰, 俞　暉

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

?

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

劉中令, 徐超杰, 俞暉

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

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

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

0概述

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

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

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

1基本算法介紹

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

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

1.1.1三邊測(cè)量法

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

(1)

將式(1)化簡(jiǎn),可得:

(2)

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

1.1.2極大似然估計(jì)法

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

(3)

將式(3)化簡(jiǎn),可得:

(4)

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

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

(5)

1.2根心介紹

1.2.1根心定理

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

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

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

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

1.2.2計(jì)算根心

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

(6)

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

(7)

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

(8)

2算法改進(jìn)

2.1算法模型

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

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

如圖1所示.

圖1　平面上3個(gè)圓相交的情況示意圖

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

圖2　根心示意圖

設(shè)計(jì)算出的根心為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個(gè)圓的圓心坐標(biāo)和半徑可以算出3個(gè)交點(diǎn)坐標(biāo),再根據(jù)這3個(gè)交點(diǎn)坐標(biāo),可以得到一個(gè)以這3個(gè)交點(diǎn)為頂點(diǎn)的三角形以及三角形的外接圓,如圖3所示.

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

2.3算法流程

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

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

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

3.1仿真實(shí)驗(yàn)

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

評(píng)估算法性能使用如下的定位誤差公式:

(10)

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

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

3.2實(shí)驗(yàn)結(jié)果分析

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

圖4　仿真結(jié)果

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

4結(jié)束語(yǔ)

本文作者研究了一種基于根心的位置解算算法:將Anchor節(jié)點(diǎn)每三個(gè)一組,計(jì)算出對(duì)應(yīng)的根心坐標(biāo);計(jì)算3個(gè)圓心到根心的射線與圓的交點(diǎn),可以得到一個(gè)以3個(gè)交點(diǎn)為頂點(diǎn)的三角形以及三角形的外接圓;計(jì)算三角形面積與外接圓半徑之比,將其作為權(quán)值;保留較大權(quán)值對(duì)應(yīng)的根心坐標(biāo),求其平均值作為解算結(jié)果.通過(guò)仿真實(shí)驗(yàn),本文作者將優(yōu)化算法與極大似然估計(jì)法、文獻(xiàn)[7]中的根心法進(jìn)行對(duì)比,實(shí)驗(yà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

中圖分類(lèi)號(hào):TN 929.5

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

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

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

收稿日期:2016-03-04