NLOS Identification and Mitigation for Localization Bad on UWB Experimental Data Stefano Maran`o,Student Member,IEEE,Wesley M.Gifford,Student Member,IEEE,Henk Wymeersch,
Member,IEEE,Moe Z.Win,Fellow,IEEE
Abstract—Sensor networks can benefit greatly from location-awareness,since it allows information gathered by the nsors to be tied to their physical locations.Ultra-wide bandwidth(UWB) transmission is a promising technology for location-aware nsor networks,due to its power efficiency,fine delay resolution,and robust operation in harsh environments.However,the prence of walls and other obstacles prents a significant challenge in terms of localization,as they can result in positively biad distance estimates.We have performed an extensive indoor measurement campaign with FCC-compliant UWB radios to quantify the effect of non-line-of-sight(NLOS)propagation.From the channel pul respons,we extract features that are reprentative of the propagation conditions.We then develop classification and regression algorithms bad on machine learning techniques, which are capable of:(i)asssing whether a signal was trans-mitted in LOS or NLOS conditions;and(ii)reducing ranging error caud by NLOS conditions.We evaluate the resulting performance through Monte Carlo simulations and compare with existing techniques.In contrast to common probabilistic approaches that require statistical model
s of the features,the propod optimization-bad approach is more robust against modeling errors.
Index Terms—Localization,UWB,NLOS Identification,NLOS Mitigation,Support Vector Machine.
I.I NTRODUCTION
L OCATION-AW ARENESS is fast becoming an esntial aspect of wireless nsor networks and will enable a myr-iad of applications,in both the commercial and the military ctors[1],[2].Ultra-wide bandwidth(UWB)transmission [3]–[8]provides robust signaling[8],[9],as well as through-wall propagation and high-resolution ranging capabilities[10], [11].Therefore,UWB reprents a promising technology for localization applications in harsh environments and accuracy-critical applications[10]–[15].In practical scenarios,however, a number of challenges remain before UWB localization and communication can be deployed.The include signal Manuscript received15May2009;revid15February2010.This rearch was supported,in part,by the National Science Foundation under grant ECCS-0901034,the Office of Naval Rearch Presidential Early Career Award for Scientists and Engineers(PECASE)N00014-09-1-0435,the Defen University Rearch Instrumentation Program under grant N00014-08-1-0826, and the MIT Institute for Soldier Nanotechnologies.
S.Maran`o was with Laboratory for Information and Decision Systems (LIDS),Massachutts Institute of Technology(MIT),and is now with the Swiss Seismological Service,ETH Z¨u rich,Z¨u rich,Switzerland(e-mail: stefano.hz.ch).
H.Wymeersch was with LIDS,MIT,and is now with Chalmers University of Technology,G¨o teborg,Sweden(e-mail:henkw@chalmers.).
Wesley M.Gifford and Moe Z.Win are with LIDS,MIT,Cambridge,MA 02139USA(e-mail:wgifford@mit.edu,moewin@mit.edu).
Digital Object Identifier10.1109/JSAC.2010.100907.acquisition[16],multi-ur interference[17],[18],multipath effects[19],[20],and non-line-of-sight(NLOS)propagation [10],[11].The latter issue is especially critical[10]–[15]for high-resolution localization systems,since NLOS propagation introduces positive bias in distance estimation algorithms, thus riously affecting the localization performance.Typical harsh environments such as enclod areas,urban canyons, or under tree canopies inherently have a high occurrence of NLOS situations.It is therefore critical to understand the impact of NLOS conditions on localization systems and to develop techniques that mitigate their effects.
There are veral ways to deal with ranging bias in NLOS conditions,which we classify as identification and mitigation. NLOS identification attempts to distinguish between LOS and NLOS conditions,and is commonly bad on range estimates[21]–[23]or on the channel pul respon(CPR) [24],[25].Recent,detailed overviews of NLOS identification techniques can be found in[22],[26].NLOS mitigation goes beyond identification and attempts to counter the positive bias introduced in NLOS signals.Several techniques[27]–[31]rely on a number of redundant range estimates,both LOS and NLOS,in order to reduce the impact of NLOS range estimates on the estimated agent position.In[32]–[34]the geometry of the environment is explicitly taken into account to cope with NLOS situations.Other approaches,such as[35],attempt to detect the earliest path in the CPR in order to better estimate the TOA in NLOS conditions.Comprehensive overviews of NLOS mitigation techniques can be found in[26],[36]. The main drawbacks of existing NLOS identification and mitigation techniques are:(i)loss of information due to the direct u of ranges instead of the CPRs;(ii)latency incurred during the collection of range estimates to establish a history; and(iii)difficulty in determining the joint probability distribu-tions of the features required by many statistical approaches. In this paper,we consider an optimization-bad approach. In particular,we propo the u of non-parametric ma-chine learning techniques to perform NLOS identification and NLOS mitigation.Hence,they do not require a statistical characterization of LOS and NLOS channels,
and can perform identification and mitigation under a common framework.The main contributions of this paper are as follows:•characterization of differences in the CPRs under LOS and NLOS conditions bad on an extensive indoor mea-surement campaign with FCC-compliant UWB radios;•determination of novel features extracted from the CPR that capture the salient properties in LOS and NLOS conditions;
0733-8716/10/$25.00c 2010IEEE
•
demonstration that a support vector machine (SVM)clas-si fier can be ud to distinguish between LOS and NLOS conditions,without the need for statistical modeling of the features under either condition;and
•
development of SVM regressor-bad techniques to mit-igate the ranging bias in NLOS situations,again without the need for statistical modeling of the features under either condition.
The remainder of the paper is organized as follows.In Section II,we introduce the system model,prob
lem statement,and describe the effect of NLOS conditions on ranging.In Section III,we describe the equipment and methodologies of the LOS/NLOS measurement campaign and its contribu-tion to this work.The propod techniques for identi fication and mitigation are described in Section IV,while different strategies for incorporating the propod techniques within any localization system are discusd in Section V.Numerical performance results are provided in Section VI,and we draw our conclusions in Section VII.
II.P ROBLEM S TATEMENT AND S YSTEM M ODEL In this ction,we describe the ranging and localization algorithm,and demonstrate the need for NLOS identi fication and mitigation.
A.Single-node Localization
A network consists of two types of nodes:anchors are nodes with known positions,while agents are nodes with unknown positions.For notational convenience,we consider the point of view of a single agent,with unknown position p ,surrounded by N b anchors,with positions,p i ,i =1,...,N b .The distance between the agent and anchor i is d i = p −p i .
The agent estimates the distance between itlf and the anchors,using a ranging protocol.We denote the estimated
distance between the agent and anchor i by ˆd
元宵佳节的诗句i ,the ranging error by εi =ˆd
i −d i ,the estimate of the ranging error by ˆεi ,the channel condition between the agent and anchor i by λi ∈{LOS ,NLOS },and the estimate of the channel佩恩壁纸
condition by ˆλ
i .The mitigated distance estimate of d i is ˆd m i
=ˆd i −ˆεi .The residual ranging error after mitigation is de fined as εm i =ˆd m i −d i .
Given a t of at least three distance estimates,the agent will then determine its position.While there are numerous positioning algorithms,we focus on the least squares (LS)criterion,due to its simplicity and becau it makes no assumptions regarding ranging errors.The agent can infer its position by minimizing the LS cost function
ˆp
=arg min p
(p i ,ˆd
i )∈S
ˆd i − p −p i 2
.
(1)
Note that we have introduced the concept of the t of uful neighbors S ,consisting of couples
p i ,ˆd
i .The optimization problem (1)can be solved numerically using steepest descent.
B.Sources of Error
The localization algorithm will lead to erroneous results when the ranging errors are large.In practice the estimated distances are not equal to the true distances,becau of a number of effects including thermal noi,multipath propa-gation,interference,and ranging algorithm inaccuracies.Ad-ditionally,th
e direct path between requester and responder may be obstructed,leading to NLOS propagation.In NLOS conditions,the direct path is either attenuated due to through-material propagation,or completely blocked.In the former ca,the distance estimates will be positively biad due to the reduced propagation speed (i.e.,less than the expected speed of light,c ).In the latter ca the distance estimate is also positively biad,as it corresponds to a re flected path.The bias effects can be accounted for in either the ranging or localization pha.
In the remainder of this paper,we focus on techniques that identify and mitigate the effects of NLOS signals during the ranging pha.In NLOS identi fication,the terms in (1)corre-sponding to NLOS distance estimates are omitted.In NLOS mitigation,the distance estimates corresponding to NLOS signals are corrected for improved accuracy.The localization algorithm can then adopt different strategies,depending on the quality and the quantity of available range estimates.
中收
III.E XPERIMENTAL A CTIVITIES
This ction describes the UWB LOS/NLOS measurement campaign performed at the Massachutts Institute of Tech-nology by the Wireless Communication and Network Sciences Laboratory during Fall 2007.A.Overview
The aim of this experimental effort is to build a large databa containing a variety of propagation conditions in the indoor of fice environment.The measurements were made using two FCC-compliant UWB radios.The radios repre-nt off-the-shelf transceivers and therefore an appropriate benchmark for developing techniques using currently available technology.The primary focus is to characterize the effects of obstructions.Thus,measurement positions (e Fig.1)were chon such that half of the collected waveforms were cap-tured in NLOS conditions.The distance between transmitter and receiver varies widely,from roughly 0.6m up to 18m,to capture a variety of operating conditions.
Several of fices,hallways,one laboratory,and a large lobby constitute the physical tting of this campaign.While the campaign was conducted in one particular indoor of fice envi-ronment,becau of the large number of measurements and the variety of propagation scenarios encountered,we expect that our results are applicable in other of fice environments.The physical arrangement of the campaign is depicted in Fig.1.In each measurement location,the received waveform and the associated range estimate,as well as the actual distance are recorded.The waveforms are then post-procesd in order to reduce dependencies on the speci fic algorithm and ,on the leading edge detection (LED)algorithm embedded in the radios.
Fig.1.Measurements were taken in clusters over veral different rooms and hallways to capture different propagation conditions.
B.Experimental Apparatus
The commercially-available radios ud during the data collection process are capable of performing communications and ranging using UWB signals.The radio complies with the emission limit t forth by the FCC[37].Specifically, the10dB bandwidth spans from3.1GHz to6.3GHz.The radio is equipped with a bottom fed planar elliptical antenna. This type of dipole antenna is reported to be well matched and radiation efficient.Most importantly,it is omni-directional and thus suited for ad-hoc networks with arbitrary azimuthal orientation[38].Each radio is mounted on the top of a plastic cart at a height of90cm above the ground.The radios perform a round-trip time-of-arrival(RTOA)ranging protocol1and are capable of capturing waveforms while performing the ranging procedure.Each waveform r(t)captured at the receiving radio is sampled at41.3ps over an obrvation window of190ns.
C.Measurement Arrangement
Measurements were taken at more than one hundred points in the considered area.A map,depicting
the topological organization of the clusters within the building,is shown 1RTOA allows ranging between two radios without a common time reference;and thus alleviates the need for network
synchronization.Fig.2.The measurement tup for collecting waveforms between D675CA and H6around the corner of the WCNS Laboratory.
in Fig.1,and a typical measurement scenario is shown in Fig.2.Points are placed randomly,but are restricted to areas which are accessible by the carts.The measurement points are grouped into non-overlapping ,each point only belongs to a single cluster.Typically,a cluster corresponds to a room or a region of a hallway.Within each cluster,
measurements between every possible pair of points were captured.When two clusters were within transmission range, every inter-cluster measurement was collected as well.Overall, more than one thousand unique point-to-point measurements were performed.For each pair of points,veral received waveforms and distance estimates are recorded,along with the actual distance.During each measurement the radios remain stationary and care is taken to limit movement of other objects in the nearby surroundings.
D.Databa
Using the measurements collected during the measurement pha,a databa was created and ud to develop and evaluate the propod identification and mitigation techniques. It includes1024measurements consisting of512waveforms captured in the LOS condition and512waveforms captured in the NLOS condition.The term LOS is ud to denote the existence of a visual path between transmitter and , a measurement is labeled as LOS when the straight line be-tween the transmitting and receiving antenna is unobstructed. The ranging estimate was obtained by an RTOA algorithm embedded on the radio.The actual position of the radio during each measurement was manually recorded,and the ranging error was calculated with the aid of computer-aided design(CAD)software.The collected waveforms were then procesd to align thefirst
path in the delay domain using a simple threshold-bad method.The alignment process creates a time reference independent of the LED algorithm embedded on the radio.
IV.NLOS I DENTIFICATION AND M ITIGATION
The collected measurement data illustrates that NLOS prop-agation conditions significantly impact ranging performance. For example,Fig.3shows the empirical CDFs of the ranging error over the enmble of all measurements collected under the two different channel conditions.In LOS conditions a ranging error below one meter occurs in more than95%of the measurements.On the other hand,in NLOS conditions a ranging error below one meter occurs in less than30%of the measurements.
Clearly,LOS and NLOS range estimates have very dif-ferent characteristics.In this ction,we develop techniques to distinguish between LOS and NLOS situations,and to mitigate the positive bias prent in NLOS range estimates. Our techniques are non-parametric,and rely on least-squares support-vector machines(LS-SVM)[39],[40].Wefirst de-scribe the features for distinguishing LOS and NLOS situa-tions,followed by a brief introduction to LS-SVM.We then describe how LS-SVM can be ud for NLOS identification and mitigation in localization applications,without needing to determine parametric joint distributions of the features for both the LOS and NLOS conditions.
A.Feature Selection for NLOS Classification
We have extracted a number of features,which we expect to capture the salient differences between LOS and NLOS signals,from every received waveform r(t).The features
Fig.3.CDF of the ranging error for the LOS and NLOS condition. were lected bad on the following obrvations:(i)in NLOS conditions,signals are considerably more attenuated and have smaller energy and amplitude due to reflections or obstructions;(ii)in LOS conditions,the strongest path of the signal typically corresponds to thefirst path,while in NLOS conditions weak components t
ypically precede the strongest path,resulting in a longer ri time;and(iii)the root-mean-square(RMS)delay spread,which captures the temporal dispersion of the signal’s energy,is larger for NLOS signals. Fig.4depicts two waveforms received in the LOS and NLOS condition supporting our obrvations.We also include some features that have been prented in the literature.Taking the considerations into account,the features we will consider are as follows:
1)Energy of the received signal:
E r=
韩国real
+∞
−∞
|r(t)|2dt(2) 2)Maximum amplitude of the received signal:
r max=max
t
|r(t)|(3) 3)Ri time:
t ri=t H−t L(4) where
t L=min{t:|r(t)|≥ασn}
t H=min{t:|r(t)|≥βr max},
andσn is the standard deviation of the thermal noi.
The values ofα>0and0<β≤1are chon empirically in order to capture the ri time;in our ca, we udα=6andβ=0.6.
4)Mean excess delay:
τMED=
+∞
−∞
tψ(t)dt(5) whereψ(t)=|r(t)|2/E r.
Fig.4.In some situations there is a clear difference between LOS(upper waveform)and NLOS(lower waveform)signals.
5)RMS delay spread:
τRMS=
+∞
−∞
(t−τMED)2ψ(t)dt(6)
6)Kurtosis:
κ=
1
σ4|r|T
T
|r(t)|−μ|r|
4
dt(7)
where
μ|r|=1
T
T
|r(t)|dt
σ2|r|=1
T
T
|r(t)|−μ|r|
2
dt.
B.Least Squares SVM
The SVM is a supervid learning technique ud both for classification and regression problems[41]
.It reprents one of the most widely ud classification techniques becau of its robustness,its rigorous underpinning,the fact that it requires few ur-defined parameters,and its superior performance compared to other techniques such as neural networks.LS-SVM is a low-complexity variation of the standard SVM, which has been applied successfully to classification and regression problems[39],[40].
脊柱侧弯矫正六个动作
1)Classification:A linear classifier is a function R n→{−1,+1}of the form
l(x)=sign[y(x)](8) with
y(x)=w Tϕ(x)+b(9) whereϕ(·)is a predetermined function,and w and b are unknown parameters of the classifier.The parameters are de-termined bad on the training t{x k,l k}N k=1,where x k∈R n and l k∈{−1,+1}are the inputs and labels,respectively.In the ca where the two class can be parated the SVM determines the parating hyperplane which maximizes the margin between the two class.2Typically,most practical problems involve class which are not parable.In this ca,the SVM classifier is obtained by solving the following optimization problem:
arg min
w,b,ξ
1
2
w 2+γ
N
k=1
ξk(10)
ξk≥0,∀k,(12) where theξk are slack variables that allow the SVM to tolerate misclassifications andγcontrols the trade-off between minimizing training errors and model complexity.It can be shown that the Lagrangian dual is a quadratic program(QP) [40,eqn.2.26].To further simplify the problem,the LS-SVM replaces the inequality(11)by an equality:
arg min
w,b,e
1
2
w 2+γ
1
2
N
k=1
蚂蚁作文400字>香肠嘴怎么变薄
e2k(13)
3.5],which can be solved efficiently by standard optimization toolboxes.The resulting classifier can be written as感恩作文600字
l(x)=sign
N
k=1
αk l k K(x,x k)+b
,(15)
whereαk,the Lagrange multipliers,and b are found from the solution of the Lagrangian dual.The function K(x k,x l)=ϕ(x k)Tϕ(x l)is known as the kernel which enables the SVM to perform nonlinear classification.
2)Regression:A linear regressor is a function R n→R of the form
y(x)=w Tϕ(x)+b(16) whereϕ(·)is a predetermined function,and w and b are unknown parameters of the regressor.The parameters are determined bad on the training t{x k,y k}N k=1,where x k∈R n and y k∈R are the inputs and outputs,respectively. The LS-SVM regressor is obtained by solving the following optimization problem:
arg min
w,b,e
1
2
w 2+γ
1
2
e 2(17)
< k=y(x k)+e k,∀k,(18) whereγcontrols the trade-off between minimizing training errors and model complexity.Again,the Lagrangian dual is an LP[40,eqn.3.32],who solution results in the following LS-SVM regressor
y(x)=
N
k=1
αk K(x,x k)+b.(19)
2The margin is given by1/ w ,and is defined as the smallest distance between the decision boundary w Tϕ(x)+b=0and any of the training examplesϕ(x k).
