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

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

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

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

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

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

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

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

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

0 引 言

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

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

1 定位測距模型

1.1 測距原理

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

(1)

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

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

圖1 目標節(jié)點和一個信標節(jié)點的信號發(fā)射接收時間顯示Fig.1 Transmit and receive times of signals between an objective node and a beacon node

(2)

位置Pj+1到信標節(jié)點i的距離為

(3)

式(2)-式(3)得：

(4)

1.2 定位模型

設在二維坐標系中，信標節(jié)點Ri的坐標為(mi, ni)，如圖2所示，目標節(jié)點從Pj移動至Pj+1.

圖2 目標節(jié)點運動時相對于某一信標節(jié)點的距離Fig.2 Distance between a beacon node andan objective node in motion

由圖2可得

(5)

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

(6)

其中，

2 迭代定位算法

2.1 起始位置分析

由于每個測量值為目標節(jié)點2個位置坐標的函數(shù)，由式(5)可推知：

(7)

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

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

(8)

其中，Np為總測量點數(shù).

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

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

2.2 迭代算法

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

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

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

2.3 定位仿真誤差分析

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

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

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

2.4 初始值分析

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

圖6 隨機選取初始猜測值時，初始位置橫縱坐標的收斂情況Fig.6 Convergence of original positions withrandom initial values

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

圖7 隨機選取的初始猜測值分布圖Fig.7 Distribution of random initial values

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

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

3 總 結(jié)

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

[1] 汶曉勇,肖越.GPS和A-GPS技術研討[J].通信技術,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ū)域細化的RFID室內(nèi)定位算法[J].計算機應用與軟件,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].戰(zhàn)術導彈技術，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] 陸洪濤,馬飛.基于多普勒頻率差的三站無源定位技術[J].艦船電子對抗,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].儀器儀表學報,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.

浙江省公益性技術應用研究計劃項目(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