非視距環境下基于粒子群的超寬帶定位算法

張 然， 宋來亮， 冉龍俊

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

非視距環境下基于粒子群的超寬帶定位算法

張 然， 宋來亮， 冉龍俊

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

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

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

0 引 言

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

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

1 粒子群算法

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

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

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

UWB室內定位系統采用TDOA算法，不要求基站之間時鐘的精確同步。定位原理為先測量出兩個不同基站和目標節點之間的傳播時間差，該傳播時間差對應一個距離差，由此得到一組以這兩個基站為焦點的雙曲線。在有3個基站的情況下，得到2條雙曲線，交點即為目標節點位置，TDOA計算公式為

(1)

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

(2)

求解目標節點問題轉化為利用粒子群算法求解函數f的最大值問題，個體的適應度值直接取為對應的目標函數值。

1.2 粒子群算法流程

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

2)個體適應度評價，并求出群體最優位置。

3)更新粒子的速度和位置，產生新群體，并對每個粒子的位置和速度進行越界檢查。加入一個調整因子局部自適應變異算子，避免算法陷入局部最優

(3)

(4)

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

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

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

6)檢查終止條件，若滿足預設條件，則結束尋優；否則,kg=kg+1，轉至步驟(3)。

2 UWB傳播信道模型

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

圖1 CM1信道和CM2信道沖激響應

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

圖2 基于脈沖序列最大能量到達時間測距算法流程

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

圖3 發射端與接收端的單脈沖波形

取發射機與接收機的實際距離為14.142m，基于脈沖序列最大能量的到達時間測距算法能量塊仿真結果如圖4(a)，(b)所示，通過Matlab軟件仿真，測得LOS和NLOS情況下，脈沖序列最大能量值對應的時延分別為t1=4.735×10-8s，t2=5.015×10-8s，測距誤差分別為e1=0.062 9m，e2=0.902 9m。可見，NLOS誤差對于UWB信號室內傳播產生了很大的影響。

圖4 基于脈沖序列最大能量到達時間測距算法能量塊圖

3 NLOS誤差的補償

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

(5)

(6)

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

(7)

(8)

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

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

(9)

(10)

(11)

(12)

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

(13)

將修正后的TDOA測量值代入粒子群算法的解析式中，進行目標節點位置估計。

4 仿真實驗與分析

4.1 仿真參數設置

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

圖5 基站位置信息

4.2 仿真結果與分析

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

(14)

在室內LOS和NLOS環境下，利用粒子群算法對目標節點進行位置估計，其定位性能對比如圖6所示，可見，NLOS對定位性能有較大影響，收斂速度慢，定位精度較低。

圖6 粒子群算法在室內LOS與NLOS下定位性能對比

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

圖7 NLOS誤差補償前后定位性能對比

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

圖8 適應度函數F的優化過程

5 結 論

本文以粒子群算法求解非線性方程組的理論為基礎，結合TDOA定位原理，建立基于粒子群算法的UWB定位模型。根據IEEE 802.15.4a信道仿真，分析NLOS誤差對定位精度的影響，用NLOS誤差導致的附加時延和信道決定的均方根時延擴展的聯合統計特性，修正TDOA測量值。在粒子群算法中，個體的適應度值直接取其對應的目標函數值，在迭代過程中采用線性遞減的慣性權重，增強了算法的局部搜索能力，有效地避免了早熟現象，仿真結果表明:該算法容易實現、收斂速度快、定位精度高，適用于NLOS環境下的UWB定位模型中。

[1] 鄔春明,耿 強,劉 杰,等.DGPS與UWB混合精確無縫定位技術研究[J].傳感器與微系統,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] 韓培培,張 申,張永政.超寬帶無線傳感器網絡性能分析[J].傳感器與微系統,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環境下提高精度的TDOA定位方法[J].南京郵電學院學報,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] 張 偉.基于粒子群優化的三維測向交叉定位算法[J].傳感器與微系統,2014,33(5):141-147.

[10] 劉金琨,沈曉蓉,趙 龍.系統辨識理論及Matlab仿真[M].北京:電子工業出版社,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] 楊北亞,熊 輝,丁 宏,等.應用NLOS鑒別補償的無線傳感器網絡TDOA定位算法[J].重慶理工大學學報,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-)，女，碩士研究生，研究方向為基于超寬帶的室內定位技術,E-mail：524118920@qq.com。