非視距環(huán)境下基于粒子群的超寬帶定位算法

張 然， 宋來亮， 冉龍俊

(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院，北京 100191)

非視距環(huán)境下基于粒子群的超寬帶定位算法

張 然， 宋來亮， 冉龍俊

(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院，北京 100191)

將智能算法應(yīng)用到無線傳感器網(wǎng)絡(luò)定位技術(shù)中是一種全新的嘗試，粒子群算法是其中的一種典型算法。根據(jù)超寬帶(UWB)定位原理，建立基于粒子群算法的定位模型，在非視距(NLOS)環(huán)境下，利用NLOS誤差導(dǎo)致的附加時(shí)延和由信道決定的均方根時(shí)延擴(kuò)展的聯(lián)合統(tǒng)計(jì)特性，進(jìn)行NLOS誤差補(bǔ)償，在迭代過程中采用線性遞減的慣性權(quán)重，粒子群通過不斷追蹤個(gè)體極值和局部極值，更新自身的位置與速度，從而找到全局最優(yōu)解，仿真結(jié)果表明正確率達(dá)90 %以上。

粒子群算法； 超寬帶定位； 非視距； 線性遞減； 慣性權(quán)重

0 引 言

隨著無線電技術(shù)的發(fā)展，無線定位技術(shù)越來越受到人們的關(guān)注，在社會(huì)各個(gè)領(lǐng)域已獲得了廣泛的應(yīng)用[1]。超寬帶(UWB)信號(hào)具有豐富的帶寬,在定位方面表現(xiàn)出很強(qiáng)的優(yōu)勢(shì)[2]，理論上定位精度可達(dá)2 cm，因此,UWB技術(shù)在精確定位方面具有廣闊的發(fā)展前景[3]。常用的UWB定位測(cè)距方法有基于到達(dá)信號(hào)強(qiáng)度(RSSI)、到達(dá)信號(hào)角度(AOA)、到達(dá)信號(hào)時(shí)間(TOA)和到達(dá)時(shí)間差(TDOA)等方法[4]?；赥DOA定位算法主要的誤差來源主要由2方面組成：系統(tǒng)測(cè)量誤差，服從均值為零的高斯分布，對(duì)定位精度的影響較??；由于室內(nèi)環(huán)境復(fù)雜，信號(hào)在傳播過程中受到障礙物的阻隔，發(fā)生反射和折射等現(xiàn)象引起的非視距(non-line of sight,NLOS)誤差，NLOS誤差引起的附加時(shí)延對(duì)定位精度影響較大，是算法的主要誤差來源。因此，減小NLOS誤差的影響是研究UWB室內(nèi)定位的首要任務(wù)。

本文介紹粒子群算法的基本原理及其TDOA模型，并對(duì)UWB信號(hào)傳播信道IEEE 802.15.4a室內(nèi)居住環(huán)境進(jìn)行仿真，分析NLOS誤差對(duì)UWB信號(hào)傳播過程的影響，獲得室內(nèi)NLOS環(huán)境下的均方根時(shí)延擴(kuò)展，利用NLOS誤差導(dǎo)致的附加時(shí)延和由信道決定的均方根時(shí)延擴(kuò)展的聯(lián)合統(tǒng)計(jì)特性，估計(jì)附加時(shí)延的均值與方差[6]，修正TDOA測(cè)量值，根據(jù)修正后的數(shù)據(jù)，利用具有時(shí)變權(quán)重的粒子群算法進(jìn)行定位，該算法抑制了NLOS誤差的影響，提高了室內(nèi)定位精度，滿足室內(nèi)定位的要求。

1 粒子群算法

粒子群算法[7]是智能算法中應(yīng)用較為廣泛的算法，它計(jì)算量小、收斂速度快，是求解非線性、組合優(yōu)化問題的有效方法[8]。該算法適用于求解TDOA非線性方程組，將雙曲線方程組作為粒子群算法待優(yōu)化函數(shù)，求得的最優(yōu)解即為目標(biāo)位置坐標(biāo)。

1.1 基于粒子群算法的TDOA模型

粒子群算法模仿鳥群的捕食行為，將每個(gè)優(yōu)化問題的解比作搜索空間內(nèi)的一只鳥，稱為“粒子”。每個(gè)粒子都有一個(gè)由待優(yōu)化函數(shù)決定的適應(yīng)度值，該適應(yīng)度值越大越好。每個(gè)粒子都有一個(gè)決定其飛行方向和距離的速度，粒子追隨當(dāng)前的最優(yōu)值在解空間中搜索[9]。

UWB室內(nèi)定位系統(tǒng)采用TDOA算法，不要求基站之間時(shí)鐘的精確同步。定位原理為先測(cè)量出兩個(gè)不同基站和目標(biāo)節(jié)點(diǎn)之間的傳播時(shí)間差，該傳播時(shí)間差對(duì)應(yīng)一個(gè)距離差，由此得到一組以這兩個(gè)基站為焦點(diǎn)的雙曲線。在有3個(gè)基站的情況下，得到2條雙曲線，交點(diǎn)即為目標(biāo)節(jié)點(diǎn)位置，TDOA計(jì)算公式為

(1)

式中 (x0,y0)，(xi,yi)為待定位的目標(biāo)節(jié)點(diǎn)和固定已知的基站坐標(biāo);c為傳播速度;τi,1為目標(biāo)節(jié)點(diǎn)到第i個(gè)基站和第1個(gè)基站之間的傳播時(shí)延差。可以利用粒子群算法求解TDOA的非線性方程，假設(shè)有4個(gè)基站，設(shè)

(2)

求解目標(biāo)節(jié)點(diǎn)問題轉(zhuǎn)化為利用粒子群算法求解函數(shù)f的最大值問題，個(gè)體的適應(yīng)度值直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值。

1.2 粒子群算法流程

1)初始化種群和設(shè)置參數(shù):設(shè)定參數(shù)的運(yùn)動(dòng)范圍，最大進(jìn)化代數(shù)G，當(dāng)前的進(jìn)化代數(shù)kg。在一個(gè)D維的搜索空間中，種群規(guī)模大小為Size;第i,i=1,2,…,Size個(gè)粒子的位置為Xi;速度為Vi;從初始到當(dāng)前迭代次數(shù)產(chǎn)生的個(gè)體極值Pi;整個(gè)種群目前最優(yōu)解為BestS。隨機(jī)產(chǎn)生初始種群的位置矩陣和速度矩陣。

2)個(gè)體適應(yīng)度評(píng)價(jià)，并求出群體最優(yōu)位置。

3)更新粒子的速度和位置，產(chǎn)生新群體，并對(duì)每個(gè)粒子的位置和速度進(jìn)行越界檢查。加入一個(gè)調(diào)整因子局部自適應(yīng)變異算子，避免算法陷入局部最優(yōu)

(3)

(4)

式中 w為慣性權(quán)重，本文采用時(shí)變權(quán)重[10]，即在迭代過程中慣性權(quán)重采用從0.90線性遞減到0.10的策略;kg=1,2,…,G;i=1,2,…,Size;r1和r2為0～1的隨機(jī)數(shù);c1為局部學(xué)習(xí)因子;c2為全局學(xué)習(xí)因子。

4)計(jì)算更新后的粒子的適應(yīng)度值，比較當(dāng)前適應(yīng)值f(Xi)與自身歷史最優(yōu)值pi，如果f(Xi)較好，則置pi為當(dāng)前值f(Xi)，并更新粒子位置。

5)比較粒子當(dāng)前適應(yīng)值f(Xi)與種群最優(yōu)值BestS，如果f(Xi)優(yōu)于BestS，則更新BestS的值。

6)檢查終止條件，若滿足預(yù)設(shè)條件，則結(jié)束尋優(yōu)；否則,kg=kg+1，轉(zhuǎn)至步驟(3)。

2 UWB傳播信道模型

UWB通信是一種利用ns級(jí)窄脈沖攜帶傳輸數(shù)據(jù)的技術(shù)，其信道特征與傳統(tǒng)的窄帶通信系統(tǒng)有所不同[11]。IEEE802.15.4a工作小組提出的UWB信道模型，共分為4種環(huán)境：居住環(huán)境、室內(nèi)辦公環(huán)境、戶外環(huán)境和工業(yè)環(huán)境，每種環(huán)境均分為視距(LOS)情況和NLOS情況[12]。本文主要研究室內(nèi)居住環(huán)境LOS與NLOS情況下UWB信號(hào)的傳輸。圖1(a),(b)分別為室內(nèi)LOS(CM1)和NLOS(CM2)情況下信道的連續(xù)時(shí)間沖激響應(yīng)。

圖1 CM1信道和CM2信道沖激響應(yīng)

從圖1(a),(b)可以看出:發(fā)射機(jī)發(fā)出一個(gè)脈沖信號(hào)時(shí)，在接收端生成了多個(gè)多徑分量。在LOS情況下，首徑的幅度最大，傳遞的能量也最高，多徑分量的幅度衰減服從指數(shù)分布；在NLOS情況下，幅度最大的徑不是第一個(gè)到達(dá)的，多徑幅度衰減也較慢，時(shí)間彌散性強(qiáng)，這是由于信號(hào)在傳播過程遇到障礙物發(fā)生反射和折射現(xiàn)象引起的。為了分析NLOS誤差對(duì)信號(hào)傳輸所造成的影響，在CM1和CM2信道下，采用基于脈沖序列最大能量徑的到達(dá)時(shí)間測(cè)距算法估計(jì)能量最高徑的到達(dá)時(shí)間，算法流程如圖2所示。

圖2 基于脈沖序列最大能量到達(dá)時(shí)間測(cè)距算法流程

發(fā)送信號(hào)為二階微分高斯脈沖，直接序列編碼調(diào)制，發(fā)射信號(hào)波形如圖3(a)所示，可知產(chǎn)生的隨機(jī)直接序列碼為-1，在無噪無多徑的環(huán)境下接收端接收到的UWB傳播時(shí)延波形如圖3(b)所示，圖中虛線為發(fā)射端發(fā)射信號(hào)，實(shí)線為接收端接收到的脈沖信號(hào)。

圖3 發(fā)射端與接收端的單脈沖波形

取發(fā)射機(jī)與接收機(jī)的實(shí)際距離為14.142m，基于脈沖序列最大能量的到達(dá)時(shí)間測(cè)距算法能量塊仿真結(jié)果如圖4(a)，(b)所示，通過Matlab軟件仿真，測(cè)得LOS和NLOS情況下，脈沖序列最大能量值對(duì)應(yīng)的時(shí)延分別為t1=4.735×10-8s，t2=5.015×10-8s，測(cè)距誤差分別為e1=0.062 9m，e2=0.902 9m?？梢?，NLOS誤差對(duì)于UWB信號(hào)室內(nèi)傳播產(chǎn)生了很大的影響。

圖4 基于脈沖序列最大能量到達(dá)時(shí)間測(cè)距算法能量塊圖

3 NLOS誤差的補(bǔ)償

NLOS誤差在不同信道下服從指數(shù)分布、均勻分布及Delta分布[13]。本文認(rèn)為其近似服從指數(shù)分布進(jìn)行分析，概率密度函數(shù)為

(5)

(6)

由此可計(jì)算NLOS誤差的均值和方差[14]

(7)

(8)

在TDOA算法中，Ri,1表示第1個(gè)和第i個(gè)基站到目標(biāo)位置的距離差，則有

Ri,1=cτi,1=Ri-R1,i=2,3,…,M

(9)

(10)

(11)

(12)

可以看出τNLOSi,1服從正均值的高斯分布，使得整體誤差均值不為零，即位置的估計(jì)是有偏的，使得定位精度受到很大影響，因此，需要對(duì)TDOA測(cè)量值進(jìn)行修正

(13)

將修正后的TDOA測(cè)量值代入粒子群算法的解析式中，進(jìn)行目標(biāo)節(jié)點(diǎn)位置估計(jì)。

4 仿真實(shí)驗(yàn)與分析

4.1 仿真參數(shù)設(shè)置

本文用Matlab仿真工具進(jìn)行算法驗(yàn)證，在粒子群算法仿真中，取粒子群個(gè)數(shù)為Size=50；最大迭代次數(shù)G=100；粒子移動(dòng)的最大速度為Vmax=1.0，即速度范圍為[-1.0,1.0]；學(xué)習(xí)因子取c1=1.3，c2=1.7；采用從0.90線性遞減到0.10的慣性權(quán)重。信道選取為IEEE 802.15.4a信道模型的CM1和CM2信道，設(shè)定在一個(gè)20 m×20 m的二維空間中，存在4個(gè)基站(BS)和1個(gè)目標(biāo)位置，目標(biāo)位置真實(shí)坐標(biāo)取(10，10)，其位置信息如圖5所示。

圖5 基站位置信息

4.2 仿真結(jié)果與分析

誤差累積分布函數(shù)(CDF)表示隨機(jī)變量小于等于某個(gè)數(shù)值的概率，在此用均方根誤差(RMSE)來計(jì)算誤差CDF，來對(duì)定位的結(jié)果進(jìn)行衡量。仿真結(jié)果由100次獨(dú)立估計(jì)過程得到，均方根誤差定義如下

(14)

在室內(nèi)LOS和NLOS環(huán)境下，利用粒子群算法對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行位置估計(jì)，其定位性能對(duì)比如圖6所示，可見，NLOS對(duì)定位性能有較大影響，收斂速度慢，定位精度較低。

圖6 粒子群算法在室內(nèi)LOS與NLOS下定位性能對(duì)比

在NLOS環(huán)境下，利用式(13)對(duì)NLOS誤差進(jìn)行補(bǔ)償，修正TDOA測(cè)量值，將修正值代入粒子群算法的TDOA模型中，對(duì)目標(biāo)節(jié)點(diǎn)位置進(jìn)行估計(jì)，NLOS誤差補(bǔ)償前與補(bǔ)償后的定位性能對(duì)比如圖7所示，可見，該算法在一定程度上抑制了NLOS誤差的影響，提高了定位精度，滿足室內(nèi)定位的要求。

圖7 NLOS誤差補(bǔ)償前后定位性能對(duì)比

在粒子群算法中，個(gè)體的適應(yīng)度值直接取對(duì)應(yīng)的目標(biāo)函數(shù)值，值越大越好。在粒子群算法的TDOA模型中，修正TDOA測(cè)量值，適應(yīng)度函數(shù)F的優(yōu)化過程如圖8所示，由仿真結(jié)果可知，在迭代過程中，粒子群通過不斷追蹤個(gè)體極值和局部極值，更新自身的位置與速度，從而找到全局最優(yōu)解。通過采用線性遞減的時(shí)變權(quán)重和環(huán)形領(lǐng)域法，增強(qiáng)了算法的局部搜索能力，有效地避免了陷入局部最優(yōu)解，仿真結(jié)果表明正確率達(dá)90 %以上。

圖8 適應(yīng)度函數(shù)F的優(yōu)化過程

5 結(jié) 論

本文以粒子群算法求解非線性方程組的理論為基礎(chǔ)，結(jié)合TDOA定位原理，建立基于粒子群算法的UWB定位模型。根據(jù)IEEE 802.15.4a信道仿真，分析NLOS誤差對(duì)定位精度的影響，用NLOS誤差導(dǎo)致的附加時(shí)延和信道決定的均方根時(shí)延擴(kuò)展的聯(lián)合統(tǒng)計(jì)特性，修正TDOA測(cè)量值。在粒子群算法中，個(gè)體的適應(yīng)度值直接取其對(duì)應(yīng)的目標(biāo)函數(shù)值，在迭代過程中采用線性遞減的慣性權(quán)重，增強(qiáng)了算法的局部搜索能力，有效地避免了早熟現(xiàn)象，仿真結(jié)果表明:該算法容易實(shí)現(xiàn)、收斂速度快、定位精度高，適用于NLOS環(huán)境下的UWB定位模型中。

[1] 鄔春明,耿 強(qiáng),劉 杰,等.DGPS與UWB混合精確無縫定位技術(shù)研究[J].傳感器與微系統(tǒng),2012,31(3):74-77.

[2] Immoreev I Y.Ultrawideband radars:Features and capabilitie-s[J].Journal of Communications Technology and Electrnics,2009,54(1):1-26.

[3] 韓培培,張 申,張永政.超寬帶無線傳感器網(wǎng)絡(luò)性能分析[J].傳感器與微系統(tǒng),2009,28(2):31-34.

[4] Li C,Zhuang W H.Hybrid TDOA/AOA mobile user location for wideband CDMA cellular systems[J].IEEE Transactions on Wireless Communications,2002,1(3):439-447.

[5] Molisch A F.IEEE 802.15.4a channel model subgroup final report[J].IEEE P802,2004,15:943-968.

[6] 段凱宇,張力軍.一種在NLOS環(huán)境下提高精度的TDOA定位方法[J].南京郵電學(xué)院學(xué)報(bào),2005,25(5):15-19.

[7] Kennedy J.Encyclopedia of machine learning[M].New York: Springer,2011:760-766.

[8] Kulkarni R V,Venayagamoorthy G K.Particle swarm optimization in wireless sensor networks:A brief survey[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2011,41(2):262-267.

[9] 張 偉.基于粒子群優(yōu)化的三維測(cè)向交叉定位算法[J].傳感器與微系統(tǒng),2014,33(5):141-147.

[10] 劉金琨,沈曉蓉,趙 龍.系統(tǒng)辨識(shí)理論及Matlab仿真[M].北京:電子工業(yè)出版社,2014,215-227.

[11] Batra A,Balakrishnan J,Aiello G R,et al.Design of a multiband OFDM system for realistic UWB Channel environments[J].IEEE Transactions on Microwave Theory and Techniques,2004,52(9):2123-2138.

[12] Molisch A F,Foerster J R,Pendergrass M.Channel models for ultrawideband personal area networks[J].Wireless Communications,IEEE,2003,10(6):14-21.

[13] Greenstein L J,Erceg V,Yeh Y S,et al.A new path-gain/delay-spread propagation model for digital cellular channels[J].IEEE Transactions on Vehicular Technology,1997,46(2):477-485.

[14] 楊北亞,熊 輝,丁 宏,等.應(yīng)用NLOS鑒別補(bǔ)償?shù)臒o線傳感器網(wǎng)絡(luò)TDOA定位算法[J].重慶理工大學(xué)學(xué)報(bào),2015,29(10):120-126.

UWB localization algorithm based on particle swarm optimization in NLOS environment

ZHANG Ran， SONG Lai-liang， RAN Long-jun

(School of Instrumentation Science and Opto-electronics Engineering,Beihang University,Beijing 100191,China )

Appling intelligent algorithm to wireless sensor networks(WSNs)positioning technology is a new attempt,particle swarm optimization(PSO)algorithm is one of the typical algorithms.According to the principle of ultra wideband(UWB)localization,positioning model based on PSO algorithm is established,in non-line-of-sight(NLOS)environment,use joint statistical properties of additional time delay caused by NLOS error and the root mean square delay spread decided by channel for NLOS error compensation,in the process of iterative,linear decreasing inertia weight is used,particle swarm update their own position and velocity by continuously tracking individual extremum and local extremum,so as to find the global optimal solution and the simulation results show that the accuracy is above 90 %.

particle swarm optimization(PSO)algorithm; ultra wideband(UWB)localization; non-line-of-sight(NLOS); linear decreasing; inertia weight

10.13873/J.1000—9787(2017)09—0117—04

2016—07—27

TN 929.5

A

1000—9787(2017)09—0117—04

張 然(1990-)，女，碩士研究生，研究方向?yàn)榛诔瑢拵У氖覂?nèi)定位技術(shù),E-mail：524118920@qq.com。