張曉燕， 孫婷婷， 徐新民*

(1. 浙江長征職業(yè)技術(shù)學(xué)院， 浙江 杭州 310023； 2. 浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027)

一種基于多普勒效應(yīng)的擬牛頓室內(nèi)定位算法

張曉燕1， 孫婷婷2， 徐新民2*

(1. 浙江長征職業(yè)技術(shù)學(xué)院， 浙江 杭州 310023； 2. 浙江大學(xué) 信息與電子工程學(xué)院， 浙江 杭州 310027)

針對(duì)現(xiàn)有室內(nèi)定位方法，根據(jù)目標(biāo)節(jié)點(diǎn)在運(yùn)動(dòng)過程中與參考信標(biāo)節(jié)點(diǎn)間產(chǎn)生的多普勒效應(yīng)，得到一種距離差測(cè)量方法，避免了對(duì)目標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間時(shí)鐘同步的要求.為實(shí)現(xiàn)此距離差定位，提出了一種基于擬牛頓法的室內(nèi)定位算法.隨機(jī)選取初始猜測(cè)值，得到一個(gè)測(cè)量點(diǎn)的距離差信息，由此迭代得到單個(gè)測(cè)量點(diǎn)坐標(biāo)，再將所有測(cè)得的相對(duì)位置坐標(biāo)進(jìn)行整體迭代并調(diào)整初始位置，直到得到穩(wěn)定的初始位置，實(shí)現(xiàn)定位.Matlab仿真結(jié)果表明，在信噪比SNR=10時(shí)，定位誤差不超過0.5 m.同時(shí)，為提高定位速度和成功率，嘗試用粒子群算法求初始猜測(cè)值，進(jìn)一步提高算法的性能.

多普勒效應(yīng)；擬牛頓迭代；室內(nèi)定位

Journal of Zhejiang University(Science Edition), 2017,44(3):322-326

0 引 言

隨著社會(huì)發(fā)展和科技進(jìn)步，基于位置的信息服務(wù)備受關(guān)注，在物流監(jiān)控、學(xué)生監(jiān)護(hù)、老弱病殘的追蹤護(hù)理等中有大量需求，室內(nèi)定位技術(shù)已成為關(guān)注和研究的熱點(diǎn).目前，常用的室內(nèi)定位技術(shù)有結(jié)合網(wǎng)絡(luò)基站信息和GPS信息的A-GPS技術(shù)[1]、超聲波測(cè)距法、藍(lán)牙定位[2]及射頻識(shí)別技術(shù)[3]等.以上室內(nèi)定位方法分2步實(shí)現(xiàn)，首先通過RSSI (received signal strength indicator)、TOA(time of arrival)或TDOA (time difference of arrival)測(cè)得目標(biāo)節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的距離或距離差，然后通過三邊定位、質(zhì)心定位等方法計(jì)算目標(biāo)節(jié)點(diǎn)的具體位置.但這些方法對(duì)室內(nèi)環(huán)境及其穩(wěn)定性或收發(fā)目標(biāo)節(jié)點(diǎn)的時(shí)鐘同步和精度要求較高.

為降低對(duì)室內(nèi)環(huán)境和時(shí)鐘同步的要求，本文引入一種基于多普勒效應(yīng)的定位系統(tǒng)模型.文獻(xiàn)[4]所介紹的基于多普勒效應(yīng)的定位方法，主要為運(yùn)動(dòng)觀測(cè)站(信標(biāo)節(jié)點(diǎn))相對(duì)于固定輻射源(目標(biāo)節(jié)點(diǎn))的測(cè)量頻差的定位法，對(duì)硬件要求嚴(yán)格.本模型利用目標(biāo)節(jié)點(diǎn)在運(yùn)動(dòng)過程中與固定信標(biāo)節(jié)點(diǎn)間的多普勒效應(yīng)，測(cè)量運(yùn)動(dòng)過程中目標(biāo)節(jié)點(diǎn)不同位置到同一節(jié)點(diǎn)的距離差并進(jìn)行定位.該距離差測(cè)量值與目標(biāo)節(jié)點(diǎn)在運(yùn)動(dòng)過程中的前后節(jié)點(diǎn)位置有關(guān)，因此無法再利用傳統(tǒng)的三邊定位等算法.本文將定位問題轉(zhuǎn)化為最小值優(yōu)化，采用擬牛頓算法(BFGS)求解.隨機(jī)選取初始值后，基于測(cè)量值信息的累積多次迭代調(diào)整，得到穩(wěn)定初始位置以實(shí)現(xiàn)較高精度的定位.同時(shí)，用粒子群算法進(jìn)一步提高定位精度.實(shí)驗(yàn)和Matlab仿真證明該方法精度較高，是一種可以嘗試的定位方法.

1 定位測(cè)距模型

1.1 測(cè)距原理

多普勒效應(yīng)是指發(fā)射源與觀察者間有相對(duì)運(yùn)動(dòng)時(shí)，觀察者接收到的波的頻率與波源發(fā)出的頻率不相等的現(xiàn)象.當(dāng)觀察者位置保持不變而發(fā)射源在運(yùn)動(dòng)時(shí)，兩者的頻率關(guān)系為

(1)

其中，f′為觀察到的頻率；f為發(fā)射源于該介質(zhì)的原始發(fā)射頻率；v為波在該介質(zhì)中的行進(jìn)速度；vo為觀察者的移動(dòng)速度，若接近發(fā)射源則前方運(yùn)算符號(hào)為‘+’，反之則為‘-’；vs為發(fā)射源移動(dòng)速度，若接近觀察者則前方運(yùn)算符號(hào)為‘-’，反之則為‘+’.

本文以目標(biāo)節(jié)點(diǎn)為發(fā)射源，在運(yùn)動(dòng)過程中發(fā)射同頻率的正弦波，則信標(biāo)節(jié)點(diǎn)接收到的是頻率改變的正弦波.假設(shè)目標(biāo)節(jié)點(diǎn)在Pj位置發(fā)射了正弦波的第j個(gè)過零點(diǎn)(zero-crossing)，此時(shí)刻為tT1，在Pj+1位置發(fā)射正弦波的第j+1個(gè)過零點(diǎn)，此時(shí)刻為tT2，而信標(biāo)節(jié)點(diǎn)Ri(i=1,2,…,N，假設(shè)有N個(gè)信標(biāo)節(jié)點(diǎn))在tR1時(shí)刻接收目標(biāo)節(jié)點(diǎn)發(fā)射的第j個(gè)過零點(diǎn)，在tR2時(shí)刻接收到第j+1個(gè)過零點(diǎn)，如圖1所示，則位置Pj到信標(biāo)節(jié)點(diǎn)i的距離為

圖1 目標(biāo)節(jié)點(diǎn)和一個(gè)信標(biāo)節(jié)點(diǎn)的信號(hào)發(fā)射接收時(shí)間顯示Fig.1 Transmit and receive times of signals between an objective node and a beacon node

(2)

位置Pj+1到信標(biāo)節(jié)點(diǎn)i的距離為

(3)

式(2)-式(3)得：

(4)

1.2 定位模型

設(shè)在二維坐標(biāo)系中，信標(biāo)節(jié)點(diǎn)Ri的坐標(biāo)為(mi, ni)，如圖2所示，目標(biāo)節(jié)點(diǎn)從Pj移動(dòng)至Pj+1.

圖2 目標(biāo)節(jié)點(diǎn)運(yùn)動(dòng)時(shí)相對(duì)于某一信標(biāo)節(jié)點(diǎn)的距離Fig.2 Distance between a beacon node andan objective node in motion

由圖2可得

(5)

由于測(cè)量值為目標(biāo)節(jié)點(diǎn)在不同位置相對(duì)于同一信標(biāo)節(jié)點(diǎn)之間的距離差，與目標(biāo)節(jié)點(diǎn)的位置相關(guān)，可利用最小二乘法的思想將問題轉(zhuǎn)化為求一組解xj,yj,xj+1,yj+1使得目標(biāo)函數(shù)最?。?/p>

(6)

其中，

2 迭代定位算法

2.1 起始位置分析

由于每個(gè)測(cè)量值為目標(biāo)節(jié)點(diǎn)2個(gè)位置坐標(biāo)的函數(shù)，由式(5)可推知：

(7)

將每一步得到的D相加便可得到目標(biāo)節(jié)點(diǎn)起始位置與每一步軌跡點(diǎn)間的測(cè)量值D.若目標(biāo)節(jié)點(diǎn)起始坐標(biāo)P0(x0,y0)已知，則根據(jù)起始位置與運(yùn)動(dòng)位置間的測(cè)量值便可優(yōu)化用算法求得目標(biāo)運(yùn)動(dòng)軌跡[5]，因此定位的關(guān)鍵是求起始位置的坐標(biāo)值.

當(dāng)求得的起始位置使得目標(biāo)節(jié)點(diǎn)的所有測(cè)量點(diǎn)的目標(biāo)函數(shù)之和(式(8))最小時(shí)，該起始位置就是起始坐標(biāo)定位的最優(yōu)解，即全局最優(yōu)解.

(8)

其中，Np為總測(cè)量點(diǎn)數(shù).

由于存在測(cè)量誤差，每增加一個(gè)測(cè)量點(diǎn)優(yōu)化后所得的起始位置可能不同.但隨著軌跡測(cè)量點(diǎn)數(shù)的增多，未知量增多，目標(biāo)函數(shù)最小值優(yōu)化的計(jì)算量增大，同時(shí)當(dāng)計(jì)算到一定的基線長度及增加足夠的軌跡點(diǎn)數(shù)后，起始坐標(biāo)值受測(cè)量誤差的影響將降低，其值與理想值間的差距較小，可以作為定位的最優(yōu)初始位置.

目前，較常用的優(yōu)化算法主要有梯度法、牛頓迭代法等經(jīng)典算法以及遺傳算法、粒子群算法等智能優(yōu)化算法.智能算法是一種啟發(fā)式算法，耗時(shí)長，對(duì)高維問題求解的正確率較低.為提高定位速度和準(zhǔn)確率，本文選用擬牛頓法(BFGS)進(jìn)行目標(biāo)優(yōu)化.擬牛頓算法是一種求解非線性方程最優(yōu)化問題的方法，克服了牛頓算法計(jì)算過程中需要求導(dǎo)、求逆的缺點(diǎn)，將Jacobi矩陣簡化為Hk+1=Hk+ΔH，保持了算法的超線性收斂速度[6].但BFGS算法屬于局部收斂算法，對(duì)初始猜測(cè)值的依賴性很強(qiáng)，越接近精確解，其收斂速度越快.

2.2 迭代算法

為了提高定位精度和收斂性，降低初始猜測(cè)值對(duì)計(jì)算結(jié)果和收斂性的影響，本文設(shè)計(jì)了一種基于擬牛頓法的定位迭代算法，其迭代流程如圖3所示.

圖3 算法流程圖Fig.3 Flow chat of algorithm

隨著測(cè)量值D的增加，每得到一個(gè)新的測(cè)量位置后即對(duì)所有已得坐標(biāo)位置進(jìn)行調(diào)整.不斷將位置信息作為新的信息，使得重新調(diào)整后的P0一步步跳出局部解，更靠近理想初值.當(dāng)調(diào)整前后P0的坐標(biāo)位置變化量小于閾值時(shí)，則認(rèn)為該位置為定位的初始位置解，由該起始位置與運(yùn)動(dòng)位置間的測(cè)量值采用優(yōu)化算法求得目標(biāo)的運(yùn)動(dòng)軌跡.

2.3 定位仿真誤差分析

為驗(yàn)證定位算法的效果，在Dell-T7500，操作系統(tǒng)為Windows 8，仿真軟件Matlab版本為R2013a的環(huán)境下，模擬實(shí)際現(xiàn)場(chǎng)房間進(jìn)行仿真.在仿真中假設(shè)房間為10 m×8 m的長方形，在其四角放置4個(gè)接收器作為信標(biāo)節(jié)點(diǎn)，給節(jié)點(diǎn)人為施予噪聲量.假設(shè)人的行走軌跡分別如圖4(a)、(b)所示.取不同軌跡點(diǎn)相對(duì)于同一信標(biāo)節(jié)點(diǎn)的距離差D作為測(cè)量值，信噪比SNR=10 dB.在長方形內(nèi)隨機(jī)選取一對(duì)坐標(biāo)作為初始位置P0的初始猜測(cè)值.

圖4 (a)對(duì)角路徑，(b)閉合路徑Fig.4 (a)Diagonal path, (b)closed path

圖5 對(duì)角路徑和閉合路徑的定位誤差Fig.5 Error of diagonal path location andclosed path location

2.4 初始值分析

由于擬牛頓迭代算法的局部收斂性，對(duì)于一般的非二次函數(shù)，當(dāng)選取的初始點(diǎn)比較靠近極小點(diǎn)時(shí)，迭代算法可能局部收斂到極小值.為查看隨機(jī)選取初始猜測(cè)值對(duì)定位成功的影響，在對(duì)角路徑中運(yùn)行迭代100次以求取初始位置P0，測(cè)量點(diǎn)數(shù)為70.圖6中橫軸表示測(cè)量點(diǎn)數(shù)，(a)為隨機(jī)取初始猜測(cè)值運(yùn)行100次時(shí),初始位置P0的橫坐標(biāo)x0隨測(cè)量點(diǎn)數(shù)的變化；(b)表示同樣條件下P0的縱坐標(biāo)y0隨測(cè)量點(diǎn)數(shù)的變化.

圖6 隨機(jī)選取初始猜測(cè)值時(shí)，初始位置橫縱坐標(biāo)的收斂情況Fig.6 Convergence of original positions withrandom initial values

由圖6可知，初始猜測(cè)值的不同會(huì)導(dǎo)致初始位置的收斂路徑不同，本實(shí)驗(yàn)95%收斂到同一位置，即正確初始位置并保持穩(wěn)定，但也有小部分圈收斂到局部最優(yōu).圖7展示了初始猜測(cè)值的分布，其中縱坐標(biāo)上三角形表示正確初始位置，小圓圈表示錯(cuò)誤的局部收斂的初始猜測(cè)值，可見它們與正確的初始位置相距較遠(yuǎn).

圖7 隨機(jī)選取的初始猜測(cè)值分布圖Fig.7 Distribution of random initial values

為解決由初始值錯(cuò)誤導(dǎo)致定位不準(zhǔn)的問題，參考文獻(xiàn)[7]提出采用PSO算法縮小初始位置范圍，得到粗略的初始位置x0,y0后，用本文的定位算法經(jīng)迭代得到穩(wěn)定初始位置.圖8為程序運(yùn)行100次時(shí)初始位置x0，y0的迭代結(jié)果，可見引入PSO算法后能準(zhǔn)確算得初始位置，且收斂速度加快，在30個(gè)測(cè)量點(diǎn)時(shí)結(jié)果已穩(wěn)定，可用于計(jì)算后續(xù)軌跡.

圖8 基于PSO算法的初始位置收斂結(jié)果Fig.8 Convergence of original positions based on PSO

3 總 結(jié)

提出了一種根據(jù)多普勒效應(yīng)測(cè)距的新的室內(nèi)定位方法，基于擬牛頓算法設(shè)計(jì)了一種隨機(jī)初始猜測(cè)值的初始位置求解方法，將定位問題轉(zhuǎn)化為最小值優(yōu)化問題.而后采用PSO算法對(duì)初始值進(jìn)行進(jìn)一步改進(jìn).仿真實(shí)驗(yàn)表明，該方法定位誤差小，成功率較高.該方法為研究固定觀測(cè)站對(duì)運(yùn)動(dòng)輻射源的定位應(yīng)用提供了基礎(chǔ).

[1] 汶曉勇,肖越.GPS和A-GPS技術(shù)研討[J].通信技術(shù),2011(8):76-78. WEN X Y, XIAO Y. Research on GPS and A-GPS technology[J]. Communications Technology,2011(8):76-78.

[2] APARICIO S, PéREZ J, TARRO P, et al. An indoor location method based on a fusion map using bluetooth and wlan technologies[C]//International Symposium on Distributed Computing and Artificial Intelligence 2008 (DCAI 2008). Berlin/Heidelberg: Springer,2009:702-710.

[3] 陳聰傳,程良倫.區(qū)域細(xì)化的RFID室內(nèi)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(1):50-52. CHEN C C, CHENG L L. RFID indoor localization algorithm based on region refinement[J]. Computer Applications and Software,2011,28(1):50-52.

[4] 李炳榮,曲長文,蘇峰,等.機(jī)載單站無源定位技術(shù)分析[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2005(6):35-39. LI B R, QU C W, SU F, et al. Analysis of airborne single station passive location technology[J]. Tactical Missile Technology，2005(6):35-39.

[5] 陸洪濤,馬飛.基于多普勒頻率差的三站無源定位技術(shù)[J].艦船電子對(duì)抗,2008,31(1):29-31. LU H T, MA F. Three station passive location technology based on Doppler frequency difference[J]. Shipboard Electronic Countermeasure,2008,31(1):29-31.

[6] YUAN G, LU X. An active set limited memory BFGS algorithm for bound constrained optimization[J]. Applied Mathematical Modelling,2011,35(7):3561-3573.

[7] 魏明生,童敏明,訾斌,等.基于粒子群-擬牛頓混合算法的管道機(jī)器人定位[J].儀器儀表學(xué)報(bào),2013,33(11):2594-2600. WEI M S, TONG M M, ZI B, et al. Pipeline robot localization based on particle swarm quasi Newton hybrid algorithm[J]. Journal of Instrument and Meter,2013,33(11):2594-2600.

A quasi-Newton indoor localization algorithm based on the Doppler effect.

ZHANG Xiaoyan1, SUN Tingting2, XU Xinmin2

(1.ZhejiangChangzhengVocationalandTechnicalCollege,Hangzhou310023,China; 2.CollegeofInformationandElectronicEngineering,ZhejiangUniversity,Hangzhou310027,China)

To avoid the clock synchronization between objective node and beacon nodes in indoor location system, a new distance measuring method based on the Doppler effect is proposed. A quasi-Newton indoor localization algorithm is implemented for distance measurement. The initial parameters for quasi-Newton are obtained randomly. Quasi-Newton is used to get each single position. Then, all the relative positions would be iterated to adjust the original position for localization. Matlab simulations show that the location error is less than 0.5 m when SNR is 10. Then, particle swarm optimization is applied to improve the performance of convergence.

Doppler effect; quasi-Newton; indoor localization

2016-05-23.

浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(2015C31073).

張曉燕(1983-)，ORCID:http://orcid.org/0000-0002-9929-2626，女，碩士，講師，主要從事嵌入式系統(tǒng)研究.

*通信作者，ORCID: http://orcid.org/0000-0002-0910-2375，E-mail：xuxm@zju.edu.cn.

10.3785/j.issn.1008-9497.2017.03.013

TP 301.6

A

1008-9497(2017)03-322-05