一種特殊GDOP場景下的NLOS傳播識別算法*

鄧水發,鄧 平,芮 洋

(西南交通大學信息編碼與傳輸重點實驗室,成都610031)

一種特殊GDOP場景下的NLOS傳播識別算法*

鄧水發**,鄧 平,芮 洋

(西南交通大學信息編碼與傳輸重點實驗室,成都610031)

在地面無線定位中,影響定位精度的最大因素是電波的非視距(NLOS)傳播誤差,定位估計前識別收發信機之間電波是視距(LOS)還是NLOS傳播是提升定位精度需要研究的重要課題。為此,先對一種基于交叉面積的NLOS識別算法進行改進,然后提出了一種針對特殊幾何精度因子(GDOP)場景下的NLOS識別算法——分步檢驗算法。該算法采用兩步進行識別,先用數據檢驗篩選出測量樣本中的LOS測量值,再用改進的交叉面積算法進行識別。仿真結果表明,分步檢驗算法在特殊GDOP場景下具有良好的識別性能。

地面無線定位;非視距傳播;特殊GDOP;分步檢驗;識別算法;交叉面積算法

目前在研究NLOS場景下的定位問題時,通常假定距離測量值較多,偵測站在被定位目標周圍, GDOP條件較好。但是在海岸、邊境、戰場等偵測站較少(最多4個偵測站),目標在偵測站組成的多邊形外這種GDOP條件較差的特殊場景下(見本文的仿真場景),可供選擇的測量值樣本數也極少,NLOS誤差對定位精度的不利影響會更大[7]。

為此,本文首先對一種交叉面積算法進行了改進,在此基礎上提出了NLOS傳播識別算法——分布檢驗算法,在特殊GDOP場景下取得了較好的LOS/NLOS識別性能。

2 NLOS系統模型

收發信機之間進行距離測量時,影響測距精度的誤差主要源于設備測量誤差和NLOS誤差。一般認為NLOS誤差遠大于測量誤差。假設系統中有N個偵測站,第i個偵測站到目標的測量距離可采用如下模型:

3 交叉面積算法

交叉面積算法由文獻[10]提出,但該算法是基于蜂窩網絡的場景,并不能直接應用于本文研究的特殊GDOP場景中。該算法根據LOS條件下相對于NLOS條件下3個基站構成的圓(以基站為圓心,測得的距離為半徑)所形成的交叉面積較小的原理,找到一個門限面積STH,然后將交叉面積與STH相比較進行LOS/NLOS識別。

設一門限概率Pd=0.98,使得LOS條件下三基站的交叉面積在概率Pd下小于某門限面積 STH。LOS條件下3個基站測距的誤差都是服從高斯分布的測量誤差:e～N(0,σ2)。

假設ei小于r的概率等于P。3個基站的測量誤差都達到r時,它們的交叉面積最大,近似形成如圖1(a)所示以C為圓心、半徑為r的圓,由此我們可以得到

式中:P=Φ(z)為高斯累積分布函數值?？梢郧蟮胷=zσ,那么近似的門限面積為

在實際的距離測量中,3個圓交叉所形成的形狀并不規則,但近似看作是一個三角形,假設3個交叉點為(x1,y1)、(x2,y2)、(x3,y3),可以求得交叉面積

在特殊場景下,如圖1(b)所示,所謂的交叉面積不是指它們的共同面積,而是不同兩圓相交的3個交點之間最小的面積,無論在 LOS條件還是NLOS條件下,它們之間交叉的共同面積往往是非常大的,但在LOS條件下,會有3個點趨向于同一點,從而這3個點所圍成的面積很小,選擇該面積作為與門限面積STH相比的值。

圖1　交叉面積示意圖Fig.1 Intersection area diagram

文獻[10]通過判斷小于門限面積的組合個數k進行識別,假設識別的LOS基站個數為m。

(1)k=0

由于沒有組合的交叉面積小于STH,認為m＜3。

(2)1≤k≤3

設交叉面積的3個交點坐標分別為(x1,y1)、(x2,y2)、(x3,y3),目標位置估計為

可以得到一個殘差:

式中:(xi,yi)表示第i個基站的坐標;ri表示各個基站的測量距離;~ri=(x~-xi)2+(y~-yi)2。如果某個組合中全為LOS基站,那么

找出交叉面積小于STH且符合式(7)的組合集合{Si},算出集合中元素個數w。如果w=0,認為m＜3;如果w=1,則集合中唯一的組合的3個基站為LOS基站,如果w＞1,則將集合中交叉面積最小的3個基站判決為LOS基站。

(3)k≥4

計算第i個基站所在的組合(共有C2n-1個組合, n表示基站個數)中的交叉面積小于STH的組合個數t,如果t≥3則認為該基站為LOS基站,否則判定該基站為NLOS基站。

4 基于交叉面積的改進算法

本文研究只有4個偵測站的情況,文獻[10]算法需要C34=4個組合的交叉面積全部小于STH才認為4個偵測站全為LOS傳播的偵測站。偵測站較多時,組合數會成倍增加,包含某一個偵測站的組合數較多。但偵測站只有4個時,包含某一特定偵測站的組合只有C23=3個,樣本較少,故文獻[10]算法不適合這種特殊場景,對于特殊GDOP場景應當考慮小于STH的組合數k的每一種情況。假設偵測站個數為4,LOS偵測站個數為m,交叉面積小于STH的組合個數為k,本文進行粗略估計。

(1)當k=4時,很大概率上m=4。

(2)當k=1時,很大概率上m=3。

(3)當k=0時,最可能的是m＜3。

(4)當k=3時,假設m=4,則其中有一個組合的交叉面積大于STH,則

假設m=3,則pn表示包含NLOS偵測站的組合的交叉面積大于STH概率,如果P(k=3|m=3)＞0.08,則pn＜0.815,pn明顯太小,不符合實際情況,所以m=4。

(5)當k=2時,則有

這個概率非常低,假設m=3時,假設pn=0.999,那么

在很大的pn概率下,P(k=2|m=3)＞P(k=2|m= 4),故當k=2時,應當認為m=3。

通過上述分析判斷,可得到以下判決:

當k=2時,還需要判斷哪個組合為LOS組合,為此,本文采用數據檢驗(Data Test,DT)方法[6]進行處理。

假設某個組合中有3個偵測站,并且假設前2個偵測站為LOS傳播,第3個偵測站的LOS/NLOS傳播情況未知,這3個偵測站測得的距離為

式中:di表示偵測站到目標的視距距離;εi表示測量誤差;ni為NLOS誤差(n1=n2=0)。令

將式(9)寫成矩陣形式可得

其中:

通過式(12)和式(13)可以求得Δ3。如果3個偵測站為LOS偵測站,即n3=0,那么Δ3≈0,否則Δ3＞0,通過Δ3可以判斷3個偵測站視距與非視距可能的情況。

當1≤k≤2時,求出的LOS組合的交叉面積的3個交點應在第4個偵測站所形成的圓內,因為第4個偵測站為NLOS偵測站,其測得的距離應大于視距距離,否則判斷該組合為LOS組合不成立。

5 分步檢驗算法

包含NLOS偵測站的組合的交叉面積也可能小于STH,造成一定的過判(判決的LOS偵測站數大于其實際個數),上面所述的算法很難進行判斷。如圖2所示,3個偵測站分別為C1、C2、C3,假設真實位置與測得的位置分別為P點、P′點,包含NLOS誤差的測量值R′1、R′2、R′3組成的3個圓也交于一點P′,但離真實位置較遠,誤差較大。在這樣的情況下,對于LOS偵測站比較少,而識別為LOS條件下的測量結果,我們需要通過多次測量進行判別,這就是本文提出的分步檢驗算法。

圖2　LOS/NLOS三圓都交于一點示意圖Fig.2 Diagram of three circles intersected at one point in LOS/NLOS situation

假定被定位目標位置在短時間內是靜止的,對目標進行N次距離測量,測量模型如式(1)所示。

對第i個偵測站的N個測量值從小到大進行排序,令排序后的測量值序列表示為

式中:di1為最小值;diN為最大值。那么從統計學角度來講,如果這N次測量數據全部為LOS測量值,那么它們的標準差應該不大于σ,然而,這些測量值中很可能存在一定的NLOS測量值。因為LOS測量值比NLOS測量值要小,那么Di中的值越排在前面為LOS測量值的概率就越大,假設Di中的第m+1個值開始帶有NLOS誤差,即

根據式(15),找到一個m,使得Di中前m個值的方差小于或者等于σ2,前m+l(1≤l≤N-m)個值的方差大于σ2。但是,找到m后也不能說明Di中前m個值都為LOS測量值,如果m比較小,也可以認為m之前的值都是NLOS測量值,所以需要一個門限M,使得m＞M時才認為前m個值都為LOS測量值。假設我們以測量樣本中至少6%以上的測量值為LOS測量值才認為m之前的數據為LOS測量值,那么

將符合m＞M的偵測站進行組合求交叉面積,需要的距離用Di中前m個值的平均值ˉdi:

隨機變量ˉdi的標準差σ′i為

式中:mi表示第i個偵測站的m值。由于mi是不一樣的,但mi＞M成立,所以

那么所有LOS條件下的組合的交叉面積應該在最小為Pd概率下小于S′TH。將滿足m＞M的偵測站進行組合求交叉面積,假設這樣偵測站個數為n,根據n的大小作不同的處理:

(1)當n＞3時,采用第4節所述的改進算法;

(2)當n=3時,則只有一個組合可以用來求交叉面積,將交叉面積與S′TH相比較,如果小于S′TH就按照上節中k=1的情況進行判決,否則認為LOS偵測站數小于3;

(3)當n＜3時,沒有足夠的偵測站來求交叉面積,那么認為LOS偵測站數小于3。

6 仿真結果及分析

仿真場景如圖3所示,假設4個偵測站的坐標分別為(500,300)、(2 000,10)、(3 000,300)、(4 000,10),目標位于(2 500,2 000),單位均為m。為了避免NLOS偵測站位置對性能的影響,隨機選取n個測量值為NLOS的偵測站。測量誤差服從均值為0、標準差分別為10 m、15 m、20 m、25 m、30 m、35 m、40 m的高斯分布,NLOS誤差服從0.05×d～0.9×d(d表示視距距離)之間的均勻分布,進行獨立1 000次仿真實驗。

圖3　偵測站與目標位置圖Fig.3 Diagram of measuring stations and target position

6.1 交叉面積算法及其改進算法

仿真參數如表1所示,我們判斷正確識別的標準為:當LOS偵測站數目為3個以上時,能將所有LOS偵測站分別識別出來為識別正確;當LOS偵測站數小于3個時,判決LOS偵測站數小于3為識別正確。

表1　交叉面積算法及其改進算法仿真參數Tab.1 Simulation parameters for the intersection area based algorithm and its improved algorithm

兩種算法的正確識別次數如表2所示,其中n表示NLOS偵測站個數,σ為測量誤差的標準差。

表2 交叉面積算法及其改進算法仿真結果Tab.2 Simulation results of the intersection area based algorithm and its improved algorithm

從仿真結果可以看出,兩種算法對于全為LOS偵測站的情況下識別度非常高,測量誤差參數對其性能影響不是很明顯;存在NLOS偵測站時,其性能隨著測量誤差的標準差增大而明顯下降,但改進算法正確識別的次數明顯優于原算法。

6.2 分步檢驗算法

對于分步檢驗算法,仿真參數與前面的仿真參數一樣,在每次仿真中,偵測站測量的數據樣本個數為100,NLOS偵測站與LOS偵測站所測數據中產生的NLOS誤差概率分別為100%和80%,即LOS偵測站數據樣本中只有20%的LOS測量值,其LOS測量值越多,測量樣本平均值越接近視距距離,我們選擇一種條件較差的參數進行仿真實驗。

正確識別標準與之前的標準一樣,仿真結果如表3所示。

表3　分步檢驗算法仿真結果Tab.3 Simulation results of the step by step algorithm

從表3中可以看出,分步檢驗算法的正確識別性能明顯得到更大幅度提升,且測量誤差標準差對識別性能影響不大。

6.3 3種算法識別性能比較

為了直觀比較本文中3種算法的識別性能,以標準差作為自變量,每種標準差下不同NLOS偵測站個數的正確識別概率的平均值作為因變量,結果如圖4所示。從圖4中可以看出,隨著標準差的增大,分步檢驗算法的性能下降緩慢,其正確識別概率明顯高于其他兩種算法。

圖4　三種算法性能比較Fig.4 Performance comparison among three algorithms

7 結束語

本文針對一種GDOP場景下LOS/NLOS測量值的識別問題開展研究,詳細分析和改進了一種交叉面積的識別算法,在此基礎上提出了一種分步檢驗算法,并通過仿真驗證了分步檢驗算法對于識別性能提升的優良性。在算法計算復雜性方面,交叉面積計算最復雜的是圓與圓的交點,而分步檢驗算法的第一步過濾了一定的NLOS偵測站,使得NLOS偵測站沒有與其他圓進行求交點的計算步驟,大大降低了算法計算復雜度,仿真實驗過程也驗證了這一點。

本文雖然是針對4個偵測站的情況進行討論的,但本文算法也可以推廣到其他情況。當只有3個偵測站時,相當于分步檢驗算法1個NLOS偵測站的情況;當有5個偵測站或者更多偵測站時,通過分布檢驗都可以先排除一定的NLOS傳播的偵測站,然后再通過改進的交叉面積算法提高識別精度,其中小于門限面積的組合個數k可以根據原算法進行判斷。

[1] CHEN P C.A non-line-of-sight error mitigation algorithm in location estimation[C]//Proceedings of 1999 Wireless Communications and Networking Conference. New Orleans,LA:IEEE,1999:316-320.

[2] LI X.An iterative NLOS mitigation algorithm for location estimation in sensor networks[C]//Proceedings of 15th IST Mobile&Wireless Communications Summit.Mykonos, Greece:IST,2006:1-5.

[3] ZHENG X N,HUA J Y,ZHENG Z L.LLOP localization algorithm with optimal scaling in NLOS wireless propagations[C]//Proceedings of 4th IEEE International Conference on Electronics Information and Emergency Communication.Beijing:IEEE,2013:45-48.

[4] XIAO Z,WEN H,MARKHAM A,et al.Non-line-ofsight identification and mitigation using received signal strength[J].IEEE Transactions on Wireless Communications,2014,14(3):1689-1702.

[5] TIAN S,ZHAO L,LI G.A support vector data description approach to NLOS identification in UWB positioning[J]. Mathematical Problems in Engineering,2014(1):1-6.

[6] CHAN Y T,TSUI W Y,SO H C.Time-of-arrival based locali-zation under NLOS conditions[J].IEEE Transactions on Vehicular Technology,2006,55(1):17-24.

[7] MUQAIBEL A H,AI-NIMNIM R A,LANDOLSI M A,et al.Mobile localization based on improved non-line-ofsight classification[C]//Proceedings of 29th International Conference on Thermoelectrics.Shanghai:IEEE,2010: 368-374.

[8] YU K,GUO Y J.Statistical NLOS identification based on AOA,TOA,and signal strength[J].IEEE Transactions on Vehicular Technology,2009,58(1):274-286.

[9] WANG Y,CHENG L,HU N.Bayes sequential test based NLOS localization method for wireless sensor network[C]// Proceedings of 2015 27th Chinese Control and Decision Conference(CCDC).Qingdao:IEEE,2015:5230-5234.

[10] KUANG L,HUANG J Y,YANG W L.Line-of-sight identification based on area measurements[C]//Proceedings of 2012 International Conference on Automatic Control and Artificial Intelligence(ACAI 2012).Xiamen: IET,2012:1306-1309.

鄧水發(1990—),男,湖南衡陽人,碩士研究生,主要研究方向為無線定位中NLOS傳播識別與誤差減弱技術;

DENG Shuifa was born in Hengyang,Hunan Province,in 1990.He is now a graduate student. His research concerns NLOS identification and mitigation in wireless location.

Email:dengshuif.a@163.com

鄧 平(1964—),男,四川宜賓人,教授,主要研究方向為無線傳感網絡定位技術、室內定位技術;

DENG Ping was born in Yibin,Sichuan Province,in 1964. He is now a professor.His research concerns wireless sensor networks for localization and indoor location.

芮 洋(1990—),男,江蘇南京人,碩士研究生,主要研究方向為無線定位中NLOS傳播識別與誤差減弱技術。

RUI Yang was born in Nanjing,Jiangsu Province,in 1990. He is now a graduate student.His research concerns NLOS identification and mitigation in wireless location.

A NLOS Propagation Identification Algorithm for Special GDOP Scene

DENG Shuifa,DENG Ping,RUI Yang
(Key Laboratory of Information Coding and Transmission,Southwest Jiaotong University,Chengdu 610031,China)

In ground-based wireless positioning,a crucial factor influencing the positioning accuracy is the non-line-of-sight(NLOS)error of radio propagation.Before location estimation,determining the radio propagation between transmitter and receiver is LOS or NLOS is an important issue for improving positioning accuracy.Firstly,a NLOS identification algorithm based on intersection area measurements is improved.Then,for special geometric dilution of precision(GDOP)scene,a NLOS identification algorithm named step by step test algorithm is proposed.This algorithm realizes the NLOS identification by two steps. The LOS measurements are selected by data test(DT)method in the first step,and then the improved intersection area measurements algorithm is utilized to make the identification in the second step.The simulation results show that this algorithm possesses high identification performance under special GDOP scene.

ground-based wireless positioning;non-line-of-sight propagation;special GDOP;step by step test;identification algorithm;intersection area based algorithm

1 引 言

在城市環境中利用蜂窩基站對移動手機進行無線定位,以及海岸、邊境、戰場等場景利用地面偵測站對地面輻射源進行無線定位時,由于收發信機之間電波的非視距(Non-Line-of-Sight,NLOS)傳播普遍存在,使得偵測站測得的距離通常為具有較大誤差的NLOS距離,大于兩者之間的視距距離,從而引起定位精度嚴重下降。降低NLOS是無線定位領域提高定位精度的一個重要課題,目前針對NLOS誤差采用直接消除及先識別后消除兩種方法處理。由于直接消除方法如殘差加權算法[1]、迭代最小殘差算法[2]、二次規劃算法[3]等在 NLOS誤差較大及LOS偵測站較少時很難取得滿意的性能。本文主要研究后一種方法,通過先對電波的LOS/NLOS傳播進行識別,再采用適當的NLOS誤差減弱算法來提高定位精度。例如:對LOS測量值賦予更大的權值,或者定位估計時直接排除NLOS誤差較大的測量值。在現有先識別后消除類算法中,基于信號特征算法[4-5],需要事先在某環境下進行大量的數據采集,記錄某點的信號特征,然后建立一個數據庫進行LOS/NLOS識別;基于位置殘差算法[6-7]要求基站數量較多;基于先驗概率算法[8-9]要求事先知道LOS發生概率和NLOS發生概率,同樣需要事先的大量樣本采集,這些算法還沒能取得滿意的性能。

**通信作者:dengshuif.a@163.com dengshuif.a@163.com

TN92

A

1001-893X(2016)11-1195-06

10.3969/j.issn.1001-893x.2016.11.003

2016-01-23;

2016-07-22

date:2016-01-23;Revised date:2016-07-22

引用格式:鄧水發,鄧平,芮洋.一種特殊GDOP場景下的NLOS傳播識別算法[J].電訊技術,2016,56(11):1195-1200.[DENG Shuifa,DENG Ping,RUI Yang.A NLOS propagation identification algorithm for special GDOP scene[J].Telecommunication Engineering,2016,56(11):1195-1200.]