基于CHAN與粒子群算法的協(xié)同定位研究

江 鳳，吳 飛，王昌志

(上海工程技術(shù)大學(xué) 電子電氣學(xué)院，上海 201600)

?

基于CHAN與粒子群算法的協(xié)同定位研究

江 鳳，吳 飛，王昌志

(上海工程技術(shù)大學(xué) 電子電氣學(xué)院，上海 201600)

針對利用CHAN算法進行TOA定位時，其定位的精度受環(huán)境條件的影響程度較大的問題，提出了一種利用粒子群與CHAN算法協(xié)同定位的方法。通過粒子群估算出移動終端的初始解，利用初始解構(gòu)建殘差方程，篩選出LOS 環(huán)境下對應(yīng)的基站，并用該基站結(jié)合CHAN定位模型對移動終端進行二次定位最終得到位置估計。由實驗結(jié)果可知，基于融合算法的定位精度比單一算法的定位結(jié)果，其定位誤差至少降低5 m。

協(xié)同定位；CHAN算法；殘差分析法；粒子群算法

隨著無線通信網(wǎng)絡(luò)與移動互聯(lián)網(wǎng)的發(fā)展，提供基于地理位置信息的服務(wù)(Location Based Service，LBS)已成為具有發(fā)展?jié)摿Φ姆较蛑弧Ｊ覂?nèi)定位系統(tǒng)無法通過GPS系統(tǒng)實現(xiàn)，源自室內(nèi)的建筑結(jié)構(gòu)復(fù)雜，障礙物會阻擋信號的正常傳輸?；跓o線局域網(wǎng)(WLAN)的定位技術(shù)由于部署成本低，因此擁有廣泛的應(yīng)用市場，成為室內(nèi)定位主要采用的方法。鑒于終端設(shè)備與基站通信時長(TOA)與地理環(huán)境密切相關(guān)，使用未經(jīng)過濾的TOA數(shù)據(jù)進行定位將會導(dǎo)致較大誤差[1]。

為有效抑制非視距的環(huán)境對信號通信時長所產(chǎn)生的影響，特別是在環(huán)境復(fù)雜的地理區(qū)域中，傳統(tǒng)的無線電波傳播模型和NLOS分布模型均很難適用，為保證定位的精度，需要對采集的信號通信時長進行分類以篩選出視距環(huán)境下的基站，以減少非視距的基站對定位結(jié)果造成的誤差[2]。

1 模型建立

非視距誤差是影響基于無線通信基站定位精度主要而又難以消除的因素之一，也是基于無線通信基站定位系統(tǒng)提高定位精度必須要解決的關(guān)鍵問題之一[3-4]。基于TOA定位的CHAN算法在LOS環(huán)境和短距離情況下，測量距離的精度較高，誤差較小，但是該算法卻必須是在LOS環(huán)境下使用才能有較好的定位精度，在NLOS定位時，信號在傳輸過程中受到障礙物的遮擋，反射或吸收，出現(xiàn)多路徑傳播的現(xiàn)象，將會導(dǎo)致無法準確定位終端位置坐標[5]。LOS和NLOS的傳播示意圖如圖1所示。

圖1 LOS徑與非LOS徑示意圖

本文針對較大NLOS誤差會導(dǎo)致位置坐標計算受到影響而引入殘差分析法[6]，而針對NLOS誤差無法避免的特性引入基站篩選的方式，以濾除非視距造成的定位誤差。CHAN算法由于只考慮了系統(tǒng)的高斯噪聲誤差，沒有考慮NLOS誤差，因此當實際的環(huán)境中出現(xiàn)障礙物遮擋等因素時，僅采用CHAN算法估計終端位置坐標將會造成較大誤差。

2 視距與非視距定位描述

本文的TOA數(shù)據(jù)來源于測量多個基站到同一個移動終端的信號到達時間，根據(jù)到達時間計算移動終端到基站的距離，再根據(jù)多個距離值估計移動終端的位置[8]。在視距傳播的情況下若信號在移動終端和第i個基站之間的傳播時間為ti，無線電信號傳播速度為c(c=3×108m/s)，設(shè)移動終端與基站之間的距離為ri，則ri=c×ti，其傳播示意圖如圖2所示。

圖2 TOA示意圖

在不存在測量誤差的理想情況下，(xi,yi,zi)假設(shè)為某個基站的坐標，(x,y,z)為手持終端的位置，定位方法的數(shù)學(xué)表達式可以表示為

(1)

其中，ri為所測的距離；di是手持終端和基站之間的實際距離。在理想情況下，di=ri。

當存在 NLOS 傳播時， NLOS 誤差在 TOA 定位方法中是一個正的附加延時超量，所以測得的終端到基站的距離就會大于終端到基站的實際距離。此時di0且≤1的誤差因子。即終端位于以基站(xi,yi,zi)為圓心，ri為半徑的圓圈內(nèi)。 在視距傳播時，ai= 1， 此時式(1)與式(2)相同

(2)

3 CHAN優(yōu)化定位模型

為使定位的結(jié)果更加的精準,引入了粒子群算法與CHAN算法進行協(xié)同定位估計終端位置坐標。

3.1 基于粒子群的定位算法描述

在分析CHAN等定位算法的基礎(chǔ)上，本文提出了基于粒子群優(yōu)化及其改進的目標定位算法。使用的粒子群的基本核心是：將群體中每個飛行個體視為D維搜索空間中的一個點稱之為粒子。粒子在空間搜索過程中按照一定的飛行速度，該速度根據(jù)粒子本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗進行動態(tài)調(diào)整，從而形成群體尋找最優(yōu)值的反饋，這樣會依據(jù)每個粒子對環(huán)境的適應(yīng)度將個體逐步遷到較好的區(qū)域，并最終在搜索空間中尋找到研究問題的最優(yōu)解[9]。將PSO算法應(yīng)用在本文中，即將目標定位方程轉(zhuǎn)換成優(yōu)化求解的問題[10]。但是同樣粒子群算法也存在著一定的局限性：由于缺乏局部精細搜索能力，算法在搜索后期容易陷入局部最優(yōu)，出現(xiàn)收斂停滯現(xiàn)象。所以本文將在粒子群的基礎(chǔ)上引入CHAN算法對一次定位結(jié)果加以修正。

圖3 粒子群基本定位流程圖

粒子群(PSO)算法描述：

步驟1 PSO算法先生成N個代表潛在問題解的粒子從而組成一個種群。設(shè)定種群規(guī)模為500，空間維數(shù)為3，迭代次數(shù)1 000、飛行速度范圍及學(xué)習(xí)因子等參數(shù)。第i個粒子表示一個D維的向量，即：第i個粒子的位置是xi=[xi,1,xi,2,…,xi,D]T，(i=1,2,…,N) ；飛行速度是,vi=[vi,1,vi,2,…,vi,D]T,i=1,2,…,N

步驟2 計算每個粒子的適應(yīng)度值，即使下式取得最小值

(3)

步驟3 計算當前每個粒子的適應(yīng)度值，將此保存在pi中，pi=[pi,1,pi,2,…,pi,D]T,i=1,2,…,N將所有粒子的適應(yīng)度值進行比較，群體中最優(yōu)適應(yīng)度值所代表的最優(yōu)位置，保存在pg,pg=[pg,1,pg,2,…,pg,D]T,i=1,2,…,N; 種群中的粒子追隨當前的最優(yōu)粒子在目標搜索空間中，通過迭代方式搜索最優(yōu)解；

步驟4 更新每個微粒的位置和速度

(4)

其中，c1和c2代表粒子個體和粒子群體的加速度權(quán)重系數(shù)；r1、r2分別代表與粒子個體及群體的加速度權(quán)重系數(shù)相關(guān)的隨機初值；xi,j(t+1)，xi,j(t)，vi,j(t+1)，vi,j(t)分別表示第i個粒子在t+1和t時刻的位置和速度；

步驟5 計算所有基站與第 個終端的測試距離與實際距離之間的誤差之和，然后更新粒子位置，從而使得誤差最小，直至最終收斂于某個坐標；

步驟6 判斷是否滿足收斂條件，如果滿足則繼續(xù)進行；

步驟7 將最后全局最優(yōu)個體輸出，輸出結(jié)果即為目標位置，運行結(jié)束。

3.2 基于CHAN算法描述

CHAN 算法是基于TOA 估計的定位算法，該算法采用最小二乘算法實現(xiàn)對終端位置的三維坐標估計，在噪聲服從高斯分布的環(huán)境中，定位精度較高[11]。對于實際環(huán)境中因存在障礙物的影響而造成測量的時差存在較大誤差的情況，該算法的精度將受到很大影響。

假定在三維空間中任意的分布著M個接收基站(BS)，待定位的手持終端(MS)坐標為(x,y,z)，已知第i個BS位置為(xi,yi,zi)和MS之間的距離為Ri，則根據(jù)測量得到的TOA 測量值τi可建立方程[12]

2Yiy-2Ziz+R=cτi,i=1,2,3,…,M

(4)

采用加權(quán)最小二乘法(WLS)，用TOA測量值的協(xié)方差矩陣Q近似代替誤差ψ的協(xié)方差矩陣，可得

za=argmin{(h-Gaza)|Q-1(h-Gaza)|}=

(5)

由于za中R實際上是與(x,y,z)有關(guān)的量，用Q矩陣近似代替誤差矢量ψ的協(xié)方差矩陣也會帶來一定誤差。為得到更精確的估計位置，當TOA測量誤差比較小時，M個TOA 測量值對應(yīng)的誤差矢量為

ψ=2Bn+n×n≈2Bn

(6)

3.3 粒子群/CHAN協(xié)同定位

鑒于在實際的定位系統(tǒng)中，測量數(shù)據(jù)的過程中會受到周圍障礙物的隨機干擾?？紤]非視距(NLOS)誤差對定位精度的影響，需要對基于 TOA 測量處理后的數(shù)據(jù)構(gòu)建殘差方程以進行分析，篩選出每個終端所對應(yīng)的視距(LOS)情況下的基站，在只采用視距測量數(shù)據(jù)來定位終端的位置坐標，其定位精度將會有極大的改善[13-15]。

首先基于粒子群算法估算出位置信息，并通過對估計結(jié)果的殘差計算均值，篩選出小于均值的以鑒別出NLOS與LOS所對應(yīng)的基站坐標,從而濾除受到非視距環(huán)境影響的基站。其次，再對篩選出的符合條件的基站測量數(shù)據(jù)，利用CHAN方法二次計算出位置坐標。算法實現(xiàn)的基本描述：

步驟1 獲取在 LOS 或 NLOS 環(huán)境下，某一終端和各個基站間的 TOA 測量值；

步驟2 利用粒子群算法初步估計移動終端的一次位置坐標估計；

步驟3 利用殘差鑒別法對獲取的 TOA 測量值進行數(shù)據(jù)分類，篩選出LOS環(huán)境下對應(yīng)的基站；

步驟4 根據(jù)篩選出的LOS環(huán)境下的基站利用CHAN算法進行定位，來進一步提高終端坐標的定位精度；

步驟5 利用均值法對得出的結(jié)果進行驗證。

4 實驗結(jié)果與分析

結(jié)合仿真實驗對算法的性能進行評估。測試數(shù)據(jù)來源于2016年全國研究生數(shù)學(xué)建模競賽C題。

針對復(fù)雜環(huán)境下所采集的諸多的信號到達時間值，結(jié)合本文所提出的終端位置估計算法進行位置計算與定位。利用提出的基于粒子群與CHAN混合的定位算法模型，具體實現(xiàn)步驟入如下：

步驟1 在LOS或NLOS環(huán)境下，將與某一待定位終端通信的所有基站的TOA測量值，結(jié)合基站的坐標，利用粒子群算法首先估算出一次坐標值，再根據(jù)估計的坐標值與基站的坐標值，結(jié)合移動終端與基站之間的通信時間計算出通信距離，再利用提出的殘差鑒別法進行 LOS 和 NLOS 數(shù)據(jù)分類；

步驟2 根據(jù)步驟1的分類結(jié)果，鑒別出相應(yīng)的LOS和NLOS通信基站；

步驟3 由于NLOS環(huán)境下的TOA測量值包含較大的噪聲，嚴重影定位算法的性能。因此，保留LOS環(huán)境下的定位基站，排除NLOS環(huán)境下的定位基站；

步驟4 根據(jù)步驟3保留的LOS環(huán)境下的基站,利用CHAN算法對待定終端的位置進行二次計算；

步驟5 輸出待定位終端的位置坐標。

為檢驗文中提出的算法是否能有效抑制NLOS的干擾，結(jié)合粒子群算法、CHAN算法，以及本文所設(shè)計的混合定位算法，將最終得到的定位結(jié)果與5組終端原位置，分別計算其定位結(jié)果誤差，并進行比較分析。結(jié)果如圖4所示，基于粒子群算法的兩次位置坐標估計值，以及與真實值之間的均方根差值。

圖4 基于粒子群的估算誤差圖

圖5顯示了基于CHAN算法的兩次位置坐標估計值，分別于真實坐標之間的均方根差值。

圖5 基于CHAN算法的估算誤差圖

圖6顯示的為基于本文所提出的混合算法計算的差值。從圖中能清楚的顯示出基于本文所提出的混合算法在終端坐標估計精度上面有了較大提高。

通過3種方法得到的結(jié)果可以看出，基于混合的定位方法，其定位結(jié)果未出現(xiàn)較大的偏差，基本保持在較穩(wěn)定的一個波動范圍之內(nèi)，波動幅度小，進一步證明了NLOS得到了有效的抑制。

圖6 基于混合算法的估算誤差圖

5 結(jié)束語

本文結(jié)合CHAN算法、粒子算法特點，改進現(xiàn)有的算法提出一種混合定位方法，通過時長計算和定位方程組求解完成移動終端節(jié)點的三維空間定位。對受NLOS污染嚴重的基站測量數(shù)據(jù)，通過篩選之后進行濾除，減少NLOS影響，提高定位精度等。通過對粒子群算法和CHAN算法進行綜合優(yōu)化，計算終端移動節(jié)點的坐標，解決移動終端在混合環(huán)境下的定位精度較低的問題。相比傳統(tǒng)的定位算法，本文提出的方法在混合環(huán)境下能夠較好的克服環(huán)境干擾因素的影響。實驗結(jié)果表明，文中提出的混合定位方法能有效抑制室內(nèi)環(huán)境下的NLOS干擾，具有較高的定位精度，具有良好的穩(wěn)定性，在室內(nèi)定位具有一定的實用價值。

[1] 王正.基于TDOA的無線傳感器網(wǎng)絡(luò)定位算法研究[D].南京:南京航空航天大學(xué),2014.

[2] 宋玉,王洪雁.NLOS環(huán)境下基于到達時間差(TDOA)的定位算法[J].系統(tǒng)仿真技術(shù),2006(3):125-129,143.

[3] 劉林.非視距環(huán)境下的無線定位算法及其性能分析[D].成都:西南交通大學(xué),2007.

[4] 林國軍.蜂窩網(wǎng)無線定位算法及其性能分析[D].成都:西南交通大學(xué),2008.

[5] 鄒杰,李珊君,陳曉明.一種改進的室內(nèi)無線定位算法[J].計算機工程,2011(14):76-78.

[6] 沈郭浩,馬永濤,劉開華,等.非視距環(huán)境下室內(nèi)RFID標簽定位算法研究[J].計算機工程與科學(xué),2016(3):454-459.

[7] 王彪,傅忠謙.基于超寬帶技術(shù)的TDOA室內(nèi)三維定位算法研究[J].微型機與應(yīng)用,2013(14):83-86.

[8] 姚金杰.基于地面基站的目標定位技術(shù)研究[D].太原:中北大學(xué),2011.

[9] 羅平,向鳳紅,毛劍琳,等.基于自然選擇的線性遞減權(quán)重PSO與Taylor算法的TDOA協(xié)同定位算法研究[J].計算機應(yīng)用研究,2014(4):1144-1146,1150.

[10] 潘燁煬.基于分布式傳感器網(wǎng)絡(luò)的地下淺層定位算法研究[D].太原:中北大學(xué),2015.

[11] 陸音,王寶全,丘覲瑋.CHAN算法在LOS和NLOS環(huán)境下的定位研究[J].計算機技術(shù)與發(fā)展,2015(9):61-65.

[12] Chan Y T,Ho K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing,1994,42(8):1905-1915.

[13] 鄭飛,鄭繼禹.基于TDOA的CHAN算法在UWB系統(tǒng)LOS和NLOS環(huán)境中的應(yīng)用研究[J]. 電子技術(shù)應(yīng)用,2007(11):110-113,132.

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

[15] 常戎,呂善偉,張江林.提高NLOS環(huán)境下定位精度的TOA數(shù)據(jù)處理方法[J].北京航空航天大學(xué)學(xué)報,2006(8):946-949.

Research on Collaborative Localization Based on CHAN and Particle Swarm Optimization Algorithm

JIANG Feng,WU Fei,WANG Changzhi

(School of Electronic and Electrical Engineering，Shanghai University of Engineering Science，Shanghai 201600,China)

In view of the TOA positioning using CHAN algorithm, the accuracy of the positioning is affected by the environmental conditions greatly. Based on this, a method of cooperative localization based on particle swarm optimization and CHAN algorithm is proposed. Firstly, through particle swarm to estimate the mobile terminal using the initial solution, construction of initial solution residual equation, and screened under the environment of LOS corresponding to the base station, and the base station combined with CHAN positioning model was two times of mobile location final location estimation. The result showed that The positioning accuracy of the fusion algorithm based on the fusion algorithm is better than that of the single algorithm, and the positioning error is significantly reduced at least 5 meters.

location;CHAN algorithm;residual analysis method;particle swarm algorithm

2016- 10- 04

國家自然科學(xué)基金 (61272097)；上海市科委重點支撐項目 (13510501400)

江鳳(1990-)，女，碩士研究生。研究方向：無線傳感網(wǎng)絡(luò)定位。吳飛(1968-)，男，博士，教授。研究方向：計算機并行處理與節(jié)能控制等。王昌志(1990-)，男，碩士研究生。研究方向：無線傳感網(wǎng)絡(luò)定位。

10.16180/j.cnki.issn1007-7820.2017.08.001

TN926+.3;TP306.1

A

1007-7820(2017)08-001-05