Abstract:
Ultra-wide bandwidth (UWB) transmission is a promising technology for indoor localization due to its fine delay resolution and obstacle-penetration capabilities. However, the presence of walls and other obstacles present a significant challenge in terms of localization, as they result in positively biased distance estimates. Measurement campaigns with FCC-compliant UWB radios can quantify effects of non-line-of-sight (NLOS) propagation. Features of waveforms measured during a campaign can be extracted for use in distinguishing between NLOS and line-of-sight situations in embodiments of the present invention. Embodiments further include classification and regression methods based on machine learning that improve the localization performance while relying solely on the received signal. Applications for systems employing an example embodiment of the invention include indoor or outdoor search and recovery with high accuracy and low cost.

Description:
GOVERNMENT SUPPORT 
       [0001]    The invention was supported, in whole or in part, by grants ANI-0335256 and ECCS-0636519 from the National Science Foundation and Young Investigator Award N00014-1-0489 from the Office of Naval Research. The Government has certain rights in the invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    Location-awareness is fast becoming a fundamental aspect of wireless networks and will enable a myriad of applications, in both the commercial and the military sector. Localization in harsh environments and accuracy-critical applications requires robust signaling, through-wall propagation, and high-resolution ranging capabilities, such as ultra-wide bandwidth (UWB) transmission, which operates in the 3 to 10 GHz band. In practical scenarios, however, a number of challenges remain before UWB localization and communication can be deployed. 
       SUMMARY OF THE INVENTION 
       [0003]    Embodiments of the present invention include methods of and apparatuses for characterizing a medium comprising learning a function that is nonparametric with respect to features representing aspects of a waveform transmitted between two wireless devices. In alternative embodiments, the function may be feature-based, i.e., based on features of transmitted waveforms. The medium is characterized by evaluating the function with a feature vector extracted from a waveform received at a first wireless device from a second wireless device. Function evaluation yields information about the waveform, including, but not limited to: an estimate of the distance between the first and second wireless devices; a decision regarding a presence of an obstruction between the first and second wireless devices; a likelihood of an obstruction between the first and second wireless devices; an estimate of distance estimation error; and a distribution of distance estimation error. 
         [0004]    This information may be reported to a user or a module configured to use the reported information. For example, the module may be configured to mitigate distance estimate error by subtracting the distance estimate error from the distance estimate. 
         [0005]    In further embodiments, the function is learned using machine learning techniques, such as support vector machine techniques or Gaussian processes techniques. Functions may be chosen from a classes of functions including, but not limited to, polynomials and linear combinations of kernel functions. Learning may include accessing data in a training database, including line-of-sight/non-line-of-sight labels and feature vectors representing aspects of a waveform transmitted between at least one pair of wireless devices. The training database may be assembled from waveforms transmitted between pairs of wireless devices distributed throughout a model environment. 
         [0006]    Embodiments may employ first and second wireless devices that are matched pairs of wireless devices with compatible transceivers. Features representing aspects of a waveform include, but are not limited to: estimated distance; energy of a received signal; maximum amplitudes; rise time; mean excess delay; root-mean-square delay spread; and kurtosis. In some embodiments, all the features may be extracted from the received waveform; in other embodiments, features may include information from other sources, such a priori information about the environment or the transmitted waveform. 
         [0007]    Further embodiments include methods of and apparatuses for supporting distance estimation between wireless devices. Example methods include evaluating an identification function to determine a presence or likelihood of an obstruction between wireless devices. A mitigation function can be evaluated based on a result of evaluating the identification function. Results of evaluating the mitigation function may then be used to provide an estimate of distance estimation error (or distribution of distance estimation error) of an estimate of a distance between wireless devices to support distance estimation between wireless devices. 
         [0008]    The identification and mitigation functions may learned using machine learning techniques. In certain instances, the identification function may be learned using an identification training database that includes at least line-of-sight/non-line-of-sight labels of waveforms received in a training environment. The mitigation function may be learned using a mitigation training database that includes at least true distances of waveforms received in a training environment. The identification and mitigation training databases may be coupled to identification and mitigation units, respectively; they may, in fact, be the same database. 
         [0009]    For example, evaluating the identification function may include providing labels identifying a received waveform as being line-of-sight (LOS) or non-line-of-sight (NLOS); these labels may be used to determine whether to evaluate the mitigation function. Still further embodiments may correct the estimate of the distance between wireless devices based on results of evaluating the mitigation function. Similarly, the estimate of distance estimation error (or distribution of distance estimation error) may be used to localize a wireless device. 
         [0010]    In example embodiments, evaluating the identification and mitigation functions occurs in one of plural layers in a communications network between wireless devices. The estimate or distribution of distance estimation error may be forwarded to a different layer in the communications network. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]    The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the present invention. 
           [0012]      FIG. 1  is a schematic diagram illustrating an example wireless network that provides identification and mitigation for errors in non-line-of-sight (NLOS) distance estimation in an indoor office environment. 
           [0013]      FIG. 2A  is a flow diagram illustrating learning and evaluating a nonparametric function to report decisions relating to a presence of obstructions between wireless devices according to embodiments of the present invention. 
           [0014]      FIG. 2B  is a flow diagram illustrating learning and evaluating a nonparametric function to report decisions relating to a presence of obstructions between wireless devices according to alternative embodiments of the present invention. 
           [0015]      FIG. 3A  is a block diagram illustrating an obstruction determination apparatus according to embodiments of the present invention. 
           [0016]      FIG. 3B  is a block diagram illustrating an alternative obstruction determination apparatus according to embodiments of the present invention. 
           [0017]      FIG. 4A  is a flow diagram illustrating learning and evaluating a feature-based function to report decisions relating to a presence of obstructions between wireless devices according to embodiments of the present invention. 
           [0018]      FIG. 4B  is a flow diagram illustrating learning and evaluating a feature-based function to report decisions relating to a presence of obstructions between wireless devices according to alternative example embodiments of the present invention. 
           [0019]      FIG. 5A  is a block diagram illustrating a distance estimation apparatus according to embodiments of the present invention. 
           [0020]      FIG. 5B  is a block diagram illustrating an alternative distance estimation apparatus according to embodiments of the present invention. 
           [0021]      FIG. 6A  is a flow diagram illustrating evaluating identification and mitigation functions to report estimates of distance estimation errors or distributions of distance estimation errors according to embodiments of the present invention. 
           [0022]      FIG. 6B  is a flow diagram illustrating evaluating identification and mitigation functions to report estimates of distance estimation errors or distributions of distance estimation errors according to alternative embodiments of the present invention. 
           [0023]      FIG. 7A  is a block diagram illustrating a further alternative distance estimation apparatus according to embodiments of the present invention. 
           [0024]      FIG. 7B  is a block diagram illustrating yet another alternative distance estimation apparatus according to embodiments of the present invention. 
           [0025]      FIG. 8  is schematic diagram illustrating clusters throughout an office environment used for capturing training measurements between wireless devices under different signal propagation conditions. 
           [0026]      FIG. 9  is a plot illustrating a cumulative distribution function (CDF) of ranging error for line-of-sight (LOS) and NLOS conditions. 
           [0027]      FIG. 10  is a pair of plots illustrating amplitudes of received LOS (upper plot) and NLOS (lower plot) signals. 
           [0028]      FIG. 11  is a CDF of ranging error for NLOS propagation condition before (dotted/dashed line) and after (dashed line) mitigation according to embodiments of the present invention. 
           [0029]      FIG. 12  is a plot of outage probability for an example NLOS identification and mitigation system with five anchors, where the probability of a NLOS condition between anchors is 20%. 
           [0030]      FIG. 13  is a plot of outage probability for an example NLOS identification and mitigation system with five anchors, where the probability of a NLOS condition between anchors is 80%. 
           [0031]      FIG. 14  is a plot of outage probability for an example NLOS identification and mitigation system with five anchors and a fixed allowable position error of e th =2 m. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0032]    A description of example embodiments of the invention follows. 
         [0033]    The teachings of all patents, published applications and references cited herein are incorporated by reference in their entirety. 
         [0034]    Example embodiments of the present invention compensate for non-line-of-sight (NLOS) propagation effects that corrupt measurements made using high-resolution localization systems. Typically, NLOS propagation introduces positive biases in distance estimation calculations, thus seriously affecting the localization performance. Typical harsh environments, such as enclosed areas, urban canyons, or under trees canopies, inherently have a high occurrence of NLOS situations. It is therefore useful to understand the impact of NLOS conditions on localization systems and to develop techniques that counter their effects. 
         [0035]    A generic localization system comprises two stages: a ranging stage and a localization stage. In the ranging stage, signals are exchanged between UWB devices, based on which relative angles or distances can be estimated. Ranging is often based on estimating the time of arrival (TOA) or the round-trip time of arrival (RTOA) of a packet. Based on the TOA or the RTOA, the distance can be inferred when the signal propagation speed is known. When the direct line-of-sight (LOS) path between the devices is unobstructed, this velocity can be assumed to be constant. On the other hand, under NLOS conditions, the direct signal path is obstructed, so the signal arrives either by propagation through a material or via a reflected path. In both cases, the distance estimate is positively biased. In the former case, this bias is due to reduced propagation speed, which depends on material permittivity and permeability, both of which can be frequency-dependent. In the latter case, the bias is due to the spatial configuration of reflectors. 
         [0036]    Example embodiments of the present invention include identification and mitigation methods and systems to deal with ranging bias in NLOS conditions. For instance, disclosed identification methods include a non-parametric approach to non-line-of sight (NLOS) identification based on machine learning. Because these embodiments are based on machine learning, they (i) do not require a statistical characterization of line-of-sight (LOS) and NLOS channels; (ii) are based on the ultrawideband (UWB) channel impulse response (CIR), and thus avoid any latency issues; and (iii) perform identification and mitigation under a common framework. Further, the disclosed techniques are based on an extensive UWB measurement campaign performed in a typical office environment with FCC-compliant UWB radios, not on statistical channel models, so the results shown in  FIGS. 9-14  realistically indicate real-world performance. 
         [0037]      FIG. 1  is a diagram of a floor plan of an indoor office environment  100  featuring various wireless devices that employ NLOS identification and mitigation. The wireless devices may be, for example, associated with individual firemen during a search and rescue mission. Fixed wireless devices, or anchors  110   a - c , may have known positions. Mobile wireless devices, or agents  111   a  and  111   b , typically have unknown positions. 
         [0038]    In preferred embodiments, the anchors  110   a - c  and agents  111   a ,  111   b  can transmit and receive wideband signals, including UWB signals. A given pair of wireless devices may exchange wideband signals to determine their separation distance by multiplying the measured the round-trip signal propagation time by the signal propagation speed, c. Agents  111   a  and  111   b  may use distance estimates to three or more anchors  110   a - c  to localize their positions within the network. 
         [0039]    These signals may be LOS signals, such as an LOS signal  122 , which propagates along an unobstructed path directly from the anchor  110   b  to the agent  111   a . Wireless devices may also transmit and receive NLOS signals obstructed by walls  102  or other obstacles, such as an obstructed signal  124  transmitted from the anchor  110   a  to the agent  111   a . Because the obstructed signal  124  travels at lower speed through the obstacle than through air, the corresponding distance estimate is too big. NLOS signals may also include signals that follow indirect paths between wireless devices, such as reflected signal  126  transmitted from the anchor  110   c  to the agent  111   a . For the reflected signal  126 , the signal propagation distance is greater than the straight-line separation, so the estimated distance is again too big. 
         [0040]    Wireless devices  110   a - 110   e  of the present invention can identify NLOS signals as such and mitigate the effects of obstacles, reflections, etc., on received signal. For example, identification and mitigation can be used to more accurately estimate distances between pairs of wireless devices or to more accurately localize a wireless device using any three other wireless devices. 
         [0041]      FIG. 2A  is a flow diagram illustrating learning ( 205 ) and evaluating ( 210 ) a nonparametric function  207  according to embodiments of the present invention. In preferred embodiments, the nonparametric function  207  is learned ( 205 ) using machine learning techniques, such as support vector machine (SVM) or Gaussian processes. Evaluating ( 210 ) the nonparametric function  207  yields a decision regarding or likelihood of the presence of an obstacle  212 . This decision or likelihood  212  is reported ( 215 ), possibly to a user, another wireless device, or a different physical or logical layer in a wireless network including multiple wireless devices. 
         [0042]      FIG. 2B  is a flow diagram illustrating learning ( 260 ) and evaluating ( 275 ) a nonparametric function  262  according to alternative embodiments of the present invention. In this example, a training database is assembled ( 255 ) from measurements of signals, or waveforms, transmitted between pairs of prototype wireless devices (or perhaps other devices altogether) at different locations throughout a training environment, such as an indoor office environment. The training database includes information about received waveforms including, but not limited to: estimated distance between wireless devices; received energy; maximum amplitude of the received waveform; waveform rise time; mean excess delay; root-mean-square (RMS) delay spread; and kurtosis. The training database may also include actual distance measurements and NLOS/LOS condition information. 
         [0043]    Training data  257  is used to learn ( 260 ) a nonparametric function  262  using machine learning techniques, such SVMs or Gaussian processes. Once learning ( 260 ) ends, the training database does not have to be accessed again, although it may be used to further refine function performance or to learn a different function. 
         [0044]    When learning ( 260 ) is complete, the nonparametric function  262  may be used to evaluate waveforms  267  received ( 265 ) at a wireless device. Feature vectors  272  are extracted ( 270 ) from the received waveform  267 ; example feature vectors  272  may include, but are not limited to: estimated distance between wireless devices; received energy; maximum amplitude of the received waveform; waveform rise time; mean excess delay; RMS delay spread; and kurtosis. 
         [0045]    The extracted feature vector  272  is used to evaluate ( 275 ) the nonparametric function  262 , possibly according to the further description below. Evaluating ( 275 ) the nonparametric function  262  may yield either a decision regarding the presence of an obstacle between wireless devices or a probability that such an obstacle exists  277 . This decision or likelihood  277  is reported ( 280 ), possibly to a user, another wireless device, or a different physical or logical layer in a wireless network including multiple wireless devices. 
         [0046]    In some embodiments, once the function is learned, no more training occurs. Learning is done once, during development of the wireless device, on a different computer than the wireless device itself. Function evaluation ( 275 ), however, is done by the wireless device every time a waveform is received during normal operating conditions. To speed processing, the function may be evaluated ( 275 ) for new incoming signals only. 
         [0047]      FIG. 3A  is a block diagram illustrating an obstruction determination device  300  according to embodiments of the present invention. The obstruction determination device  300 , which may operate according to the flow diagrams shown in  FIGS. 2A and 2B , learns a nonparametric function  312  with a learning unit  310  using machine learning techniques. The learning unit  310  forwards the learned nonparametric function  312  to an evaluating unit  315 , which evaluates a feature vector extracted from a received waveform  305  using the nonparametric function  312 . The evaluating unit  312  produces a decision  325  regarding the presence of an obstacle in the waveform&#39;s path (or possibly a probability of the presence of an obstacle in the waveform&#39;s path) and forwards the decision  325  (or probability) to a reporting unit  320 . The reporting unit  320  forwards the decision to a user, processor, different wireless device, or different layer in the wireless network through which the waveform  305  was transmitted. 
         [0048]      FIG. 3B  is a block diagram illustrating an alternative obstruction determination apparatus  350  according to embodiments of the present invention. As shown in  FIG. 3B , a learning unit  360  receives training data, including LOS/NLOS labels  382  and feature vectors  384 , from a training database  380 . Example feature vectors  384  may include information collected from training signals, such as: estimated distance between wireless devices; received energy; maximum amplitude of the received waveform; waveform rise time; mean excess delay; RMS delay spread; and kurtosis. 
         [0049]    The learning unit  360  uses the training data to learn a nonparametric function  362  using machine learning techniques, such as SVMs or Gaussian processes. The learning unit  360  forwards the learned nonparametric function  362  to an evaluating unit  365 , which evaluates the function  362  for a feature vector extracted from a waveform  355 . By evaluating the function  362  for a given feature vector, the evaluating unit  360  determines whether an obstacle obstructed the waveform&#39;s path. The evaluating unit  362  forwards a decision or probability  375  regarding obstacles in the waveform&#39;s path to a reporting unit  370 , which may forward the decision or probability  375  to a user, different module, different layer, or memory. 
         [0050]      FIG. 4A  is a flow diagram illustrating learning ( 405 ) and evaluating ( 410 ) a feature-based function  407  according to embodiments of the present invention. In preferred embodiments, the feature-based function  407  is learned ( 405 ) using machine learning techniques, such as support vector machine (SVM) or Gaussian processes. Evaluating ( 410 ) the feature-based function  407  yields an estimate of distance estimation error or a distribution of a distance estimation error  412 . The estimate of the distance estimation error  412  may be derived from the distribution of the distance estimation error; for example, it may be the mean or median of the distribution. This error or distribution  412  is reported ( 415 ), possibly to a user, another wireless device, or a different physical or logical layer in a wireless network including multiple wireless devices. 
         [0051]      FIG. 4B  is a flow diagram illustrating learning ( 455 ) a feature-based function  457  using machine learning techniques according to alternative embodiments of the present invention. A wireless device or other suitable receiver receives ( 460 ) a waveform from which a distance estimate is prepared ( 470 ) and a feature vector is extracted ( 465 ). The extracted feature vector may include, but is not limited to: estimated distance between wireless devices; received energy; maximum amplitude of the received waveform; waveform rise time; mean excess delay; RMS delay spread; and kurtosis. 
         [0052]    Evaluating ( 475 ) the feature vector using the feature-based function  457  produces an estimate of distance estimation error or a distribution of distance estimation error  477 , which can be used to mitigate ( 480 ) error in the distance estimate. The mitigated distance estimate and the estimate of distance estimation error (and/or the distribution of distance estimation error)  477  are reported ( 485 ,  490 ) to a user, another wireless device or processor, or another layer in the wireless network. 
         [0053]      FIG. 5A  is a block diagram illustrating a distance estimation apparatus  500  according to embodiments of the present invention. The distance estimation apparatus  500 , which may operate according to the flow diagrams shown in  FIGS. 4A and 4B , learns a feature-based function  512  with a learning unit  510  using machine learning techniques. The learning unit  510  forwards the learned nonparametric function  512  to an evaluating unit  515 , which evaluates a feature vector extracted from a received waveform  505  using the feature-based function  512 . The evaluating unit  512  produces an estimate of distance estimation error (or a distance estimation error distribution)  525  and forwards the error estimate (distribution)  525  to a reporting unit  520 . The reporting unit  520  forwards the error estimate (distribution)  525  to a user, processor, different wireless device, or different layer in the wireless network through which the waveform  505  was transmitted. 
         [0054]      FIG. 5B  is a block diagram illustrating an alternative distance estimation apparatus  550  according to embodiments of the present invention. The distance estimation apparatus  550  receives a waveform  555 , then extracts a feature vector from the received waveform. An evaluation unit  565  evaluates the feature vector with a feature-based function  562 , learned by a learning unit  560  using machine learning techniques, such as SVMs and Gaussian processes. The evaluation unit  565  forwards distance estimation error information  575 , such as error estimate or distribution, to a reporting unit  570 , which reports the error information  575 , and a mitigation unit  580 . The mitigation unit  580  uses the error information  575  to mitigate error in estimated distance; the mitigation unit  580  then reports the mitigated distance estimate  585 . 
         [0055]      FIG. 6A  is a flow diagram illustrating evaluating identification ( 605 ) and mitigation ( 610 ) functions according to embodiments of the present invention. The identification function is evaluated using features  603  extracted from a received waveform. The features may be arranged in a feature vector and may include, but are not limited to: estimated distance between wireless devices; received energy; maximum amplitude of the received waveform; waveform rise time; mean excess delay; RMS delay spread; and kurtosis. 
         [0056]    Next, the mitigation function is evaluated ( 610 ) using results  612  from evaluating ( 605 ) the identification function to produce, for example, an estimate of distance estimation error or a distribution of distance estimation errors. The mitigation function results  612  are then provided ( 615 ) to a user, wireless device, localization system, or different layer in the wireless network. 
         [0057]      FIG. 6B  is a flow diagram illustrating an alternative method of evaluating identification ( 655 ) and mitigation ( 665 ) functions, where the identification and mitigation functions are each functions of waveform features. The identification and mitigation functions may be separate functions learned using machine learning techniques, such as those described in greater detail below. The identification function may be learned using a database that includes LOS and NLOS labels of training waveforms, as described above. The mitigation function may be learned using true distances of received training waveforms, possibly stored in the same database used to learn the identification function. Each function may be learned once before evaluation ( 655 ). 
         [0058]    The identification function is evaluated ( 655 ) using features  653  extracted from a received waveform to determine whether or not an obstruction exists between the pair of wireless devices associated with the received waveform. If evaluating ( 655 ) the identification function shows a strong likelihood that an obstruction exists, the waveform is identified as an NLOS waveform ( 660 ). Otherwise, the waveform is identified as an LOS waveform ( 660 ). 
         [0059]    For NLOS waveforms, the mitigation function is evaluated ( 665 ) using results from evaluating ( 655 ) the identification function to produce, for example, an estimate of distance estimation error or a distribution of distance estimation errors. The mitigation function results  667  are then used to correct ( 670 ) error in the distance estimate. For example, positively biased offset errors may be subtracted from the distance estimate. In some embodiments, distance estimates for LOS waveforms may be corrected ( 670 ) without being mitigated ( 665 ). 
         [0060]    The corrected distances estimates for both LOS and NLOS waveforms may then be used to localize ( 675 ) a wireless device within a wireless network. Localization ( 675 ) requires inputs from three or more devices (or three or more device locations) to triangulate the location of a given wireless device relative to other devices on the network. Using the estimate of distance estimation error or distribution of distance estimation error improves localization precision. Localization, error information, and distance estimates are then reported to a different layer in the network. 
         [0061]      FIG. 7A  is a block diagram illustrating a distance estimation apparatus  700  according to embodiments of the present invention. The distance estimation apparatus  700 , which may operate according to the flow diagrams shown in  FIGS. 6A and 6B , evaluates identification and mitigation functions teamed using machine learning techniques. An identification unit  710  and a mitigation unit  715  each evaluate a feature vector extracted from a received waveform  705 . The mitigation unit  715  may condition its evaluation on data from the identification unit  710  to produce an estimate of distance estimation error (or a distance estimation error distribution)  725 . The mitigation unit  715  and forwards the error estimate (distribution)  725  to a reporting unit  720 , which forwards the error estimate (distribution)  725  to a user, processor, different wireless device, or different layer in the wireless network through which the waveform  705  was transmitted. 
         [0062]      FIG. 7B  is a block diagram illustrating another alternative distance estimation apparatus  750 , which may operate according to the flow diagrams shown in  FIGS. 6A and 6B . The distance estimation apparatus  750  evaluates identification and mitigation functions learned using machine learning techniques, such as SVMs and Gaussian processes. The identification and mitigation functions may be learned using LOS/NLOS labels  762  and true distances  768 , respectively, that are stored in an identification database  763  and a mitigation database  767 , respectively. An identification unit  760  evaluates a feature vector extracted from a received waveform  755 , then forwards an LOS/NLOS label  762  to a mitigation unit  765 . 
         [0063]    If the label  762  identifies the waveform  755  as an NLOS signal, the mitigation unit  765  mitigates NLOS effects, then forwards mitigated distance data to a reporting unit  770 , a correction unit  780 , and a localization unit  790 . Otherwise, the mitigation unit  765  may forward raw distance data directly to units  770 ,  780 , and  790 . The reporting unit  770  reports estimates of distance estimation error (or a distributions of distance estimation error)  775 ; the correction unit  780  corrects error in the distance estimate to produce a corrected distance estimate  785 ; and the localization unit  790  localizes a wireless device associated with the waveform  755  using data from multiple devices or multiple device locations to produce a localization estimate  795 . 
       Problem Statement and System Model 
       [0064]    This section includes a description of ranging and localization and the corresponding need for NLOS identification and mitigation. A network consists of two types of nodes: anchors are nodes with known positions, while agents are nodes with unknown positions. For notational convenience, the focus here is from the point of view of a single agent, with unknown position p, surrounded by N anchors, with positions, p i , i=1, . . . , N. The distance between the agent and anchor i is denoted by d i =|p−p i | and the agent&#39;s estimate of this distance by {circumflex over (d)} i . The ranging error is ε i ={circumflex over (d)} i −{circumflex over (d)} i , and its estimate is {circumflex over (ε)} i . The channel condition between the agent and anchor i is λ i ε{LOS, NLOS}, and its estimate is {circumflex over (λ)} i . The mitigated distance estimate of d i  is {circumflex over (d)} i   m ={circumflex over (d)} i −{circumflex over (ε)} i . The ranging error after mitigation is defined as ε i   m ={circumflex over (d)} i   m −d i . 
         [0065]    As shown below, localization requires knowledge of distance estimates and anchor positions. For that reason, a set of useful neighbors Γ consisting of couples (p i , {circumflex over (d)} 1 ), can be useful. 
       Ranging Procedure 
       [0066]    Suitable UWB radios include those that use a round-trip time of arrival (RTOA) method to perform ranging between two nodes without a common time reference: the first node, the requester, sends a ranging request to the second node, the responder. The ranging request consists of a packet with a time stamp t Req,send  corresponding to the instant the request is sent. The value of t Req,send  is expressed in the time reference of the requester. The responder receives the packet at time t Req,rec  and sends a second packet back to the first node at time t Res,send =t Res,rev +Δ. This packet is called a ranging response and contains information about the duration of the interval Δ. The requester receives the ranging response at time t Req,rec  and is able to estimate the round-trip time using only its own internal clock reference: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                       ^ 
                     
                     
                       Res 
                       - 
                       Req 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                     × 
                     v 
                     × 
                     
                       ( 
                       
                         
                           t 
                           
                             Req 
                             , 
                             rec 
                           
                         
                         - 
                         
                           t 
                           
                             Req 
                             , 
                             send 
                           
                         
                         - 
                         Δ 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where ν is the signal propagation speed. Typically, ν is taken to equal c, the speed of light, but this becomes inaccurate under NLOS propagation. 
       Localization Procedure 
       [0067]    Once the agent has estimated distances with respect to N≧3 anchor nodes, it can estimate its position using Γ={p i , {circumflex over (d)} i |1≦i≦N}. Many methods can achieve this goal, including the least squares (LS) technique, which is simple and requires no assumptions regarding ranging errors. The agent can infer its position by solving the LS cost function, 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                     ^ 
                   
                   = 
                   
                     arg 
                      
                     
                         
                     
                      
                     
                       
                         min 
                         p 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     d 
                                     ^ 
                                   
                                   i 
                                 
                                 - 
                                 
                                    
                                   
                                     p 
                                     - 
                                     
                                       p 
                                       i 
                                     
                                   
                                    
                                 
                               
                               ) 
                             
                             2 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    This optimization problem can be solved numerically using steepest descent. In particular, setting the derivative of the cost function with respect to p to zero leads to the following iterative procedure: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       ^ 
                     
                     
                       ( 
                       l 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         p 
                         ^ 
                       
                       
                         ( 
                         
                           l 
                           - 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                       δ 
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             ( 
                             
                               
                                 
                                   d 
                                   ^ 
                                 
                                 i 
                               
                               - 
                               
                                  
                                 
                                   
                                     
                                       p 
                                       ^ 
                                     
                                     
                                       ( 
                                       
                                         l 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                   - 
                                   
                                     p 
                                     i 
                                   
                                 
                                  
                               
                             
                             ) 
                           
                            
                           
                              
                             i 
                             
                               ( 
                               
                                 l 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where e i   (l−1)  is a unit vector oriented from p i  to {circumflex over (p)} i   (l−1)  and δ is a step size controlling the convergence speed. Equation ( 3 ) can be interpreted as follows: every term in the summation is zero when the distance estimate {circumflex over (d)} i  matches the distance between the estimates ∥{circumflex over (p)} i   (l−1) −{circumflex over (p)} i ∥. When the distance between the estimates is larger than the distance estimate, the LS procedure corrects this by moving the estimated position of the agent towards anchor i. Conversely, when the distance between the estimates is smaller than the distance estimate {circumflex over (d)} i , the LS procedure corrects this by moving the estimated position of the agent away from anchor i. 
       Sources of Error 
       [0068]    Localization leads to erroneous results when the ranging errors are large. In practice the estimated distances are not equal to the true distances, because of a number of effects, including thermal noise, multipath propagation, obstructions, and ranging artifacts. Additionally, the direct path between requester and responder may be obstructed, leading to NLOS signals. In NLOS conditions, the direct path is either attenuated, due to through-material propagation, or completely blocked. In the former case, the distance estimates are positively biased due to the reduced propagation speed (i.e., less than the expected c). In the latter case, the distance estimate is also positively biased, as it corresponds to the first reflected path. These bias effects can be accounted for in either the ranging phase or the localization phase. 
         [0069]    Embodiments of the present invention include techniques that work during the ranging phase to identify and mitigate the effects of NLOS signals. In NLOS identification, the terms in Eq. (3) corresponding to NLOS distance estimates are omitted. In NLOS mitigation, the distance estimate corresponding to NLOS signals are corrected, resulting in a range estimate that is more accurate. The localization equation, Eq. (3), can then adopt different strategies, depending on the quality and the quantity of available range estimates. 
       Measurement Campaigns and Training Databases 
       [0070]      FIG. 8  shows topological organization of clusters within an indoor office environment at the Massachusetts Institute of Technology that were used by the Wireless Communications Research Group for a UWB LOS/NLOS measurement campaign. As shown in  FIG. 8 , several offices, hallways, one laboratory, and a large lobby constituted the physical setting of this campaign. The scope of the campaign matched the so-called indoor office environment. The Wireless Communications Research Group conducted the measurement campaign by collecting waveforms sent from a wireless transmitter to a wireless receiver at a variety of positions and propagation conditions in the indoor office environment. The associated range estimate and the actual distance were also recorded for each waveform. The waveforms were then post-processed in order to reduce dependencies on the specific hardware. 
         [0071]    The measurements were made using two Time Domain Corporation PulsOn  210  (P 210 ) radios capable of performing communications and ranging using UWB signals. These radios are off-the-shelf transceivers that comply with the emission limit set forth by the FCC. Specifically, the 10 dB bandwidth spans the band from 3.1 GHz to 6.3 GHz. The P 210  radio is equipped with a bottom-fed planar elliptical antenna known as the BroadSpec P 200 . This kind of dipole is well-matched and radiation efficient. Most importantly, the antenna is omni-directional and thus suited for ad-hoc networks with arbitrary azimuthal orientation. The radio runs a RTOA ranging protocol and is capable of capturing a waveform while performing the ranging procedure. 
         [0072]    Measurements were take at over one hundred points in the considered area using radios, or nodes, mounted on top of plastic carts at a height of 90 cm above the ground. Points were placed randomly, but were restricted to areas which are accessible by the carts. The distance between the transmitter and receiver varied from roughly 0.6 m up to 18 m. In about half the positions, obstacles between the transmitter and receiver created NLOS conditions. The measurement points were grouped into clusters, as shown in  FIG. 8 , where a given cluster corresponds to a room or a region of a hallway. Each point belongs only to a single cluster. Overall, around one thousand point-to-point measurements were performed, including measurements within a single cluster and between neighboring clusters. For each pair of points, several received waveforms and distance estimates were recorded, along with the actual distance. During each measurement, the radios remained stationary and care was taken to limit movement of other objects in the nearby surroundings. 
         [0073]    A database was created from measurements collected during the measurement campaign and used to develop and evaluate the proposed identification and mitigation techniques. The database included 1024 measurements: 512 LOS and 512 NLOS. The term LOS is used to denote the existence of a visual LOS. Specifically, a measurement is labeled as LOS when the straight line between the transmitting and receiving antenna is unobstructed. Each waveform r(t) is affected by thermal noise and sampled at T sample =41.3 ps over an observation window of 190 ns. The ranging estimate was obtained by a RTOA process created by Time Domain Corp. and 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 a computer-aided design (CAD) software. The collected waveforms were then aligned in the delay domain using a simple threshold-based method for leading edge detection. The alignment process creates a common time reference which enables the subsequent extraction of the metrics used for identification and mitigation. 
       NLOS Identification and Mitigation 
       [0074]      FIG. 9  shows the empirical cumulative distribution functions (CDFs) of the ranging error under the two different channel conditions. The collected measurement data shows that NLOS propagation conditions significantly impact ranging performance. In LOS conditions, the ranging error is less than a meter more than 95% of the time. In the NLOS case, on the other hand, the ranging error is less than a meter less than 30% of the time. Clearly, LOS and NLOS range estimates have very different characteristics. 
         [0075]      FIGS. 10-14  show result of mitigation using techniques developed below to distinguish between LOS and NLOS situations and to mitigate the positive biases present in NLOS ranges estimates. The techniques include non-parametric techniques, and rely on least-squares support-vector machines (LS-SVM). The derivations below include a description of features used to distinguish between LOS and NLOS situations. This is followed by a brief introduction into LS-SVM and a description of how LS-SVM can be used for NLOS identification and mitigation in a localization application. 
         [0076]      FIG. 10  shows signals received under LOS (upper plot) and NLOS (lower plot) conditions. Although there is wide variation in signal characteristics, a number of features can be extracted from every received waveform r(t); these features (collectively, “a feature vector”) capture the salient differences. In general, NLOS signals are considerably more attenuated and present smaller energy and amplitude due to reflections or obstructions. In the LOS case, the strongest path corresponds to the first path and the received signal presents a steep rise. In the NLOS case, some weak components precede the strongest path, resulting in a longer rise time. The RMS delay spread, which captures the temporal dispersion of the energy of the signal due to the multipath channel, is larger in NLOS signals. 
         [0077]    Taking these considerations into account, the extracted features may include: 
         [0078]    1. Energy of the received signal: 
         [0000]    
       
         
           
             
               
                 
                   
                     ɛ 
                     r 
                   
                   = 
                   
                     
                       ∫ 
                       
                         - 
                         ∞ 
                       
                       
                         + 
                         ∞ 
                       
                     
                      
                     
                       
                         
                            
                           
                             r 
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                            
                         
                         2 
                       
                        
                       
                          
                         t 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0079]    2. Maximum amplitude of the received signal: 
         [0000]    
       
         
           
             
               
                 
                   
                     r 
                     max 
                   
                   = 
                   
                     
                       max 
                       t 
                     
                      
                     
                        
                       
                         r 
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                        
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0080]    3. Rise time: 
         [0000]        t   rise   =t   H   −t   L   (6)
 
         [0000]    where
       t L =min {t:|r(t)|≧ασ n }   t H =min {t:|r(t)|≧βτ max },
 
where σ n  is the standard deviation of the thermal noise. The values of α&gt;0 and 0&lt;β≦1 are chosen empirically; here, α=6 and β=0.6.
       
 
         [0083]    4. Mean excess delay: 
         [0000]    
       
         
           
             
               
                 
                   
                     τ 
                     MED 
                   
                   = 
                   
                     
                       ∫ 
                       
                         - 
                         ∞ 
                       
                       
                         + 
                         ∞ 
                       
                     
                      
                     
                       t 
                        
                       
                           
                       
                        
                       
                         ψ 
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                        
                       
                          
                         t 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where ψ(t)=|r(t)| 2 /E r . 
         [0084]    5. RMS delay spread: 
         [0000]    
       
         
           
             
               
                 
                   
                     τ 
                     RMS 
                   
                   = 
                   
                     
                       ∫ 
                       
                         - 
                         ∞ 
                       
                       
                         + 
                         ∞ 
                       
                     
                      
                     
                       
                         
                           ( 
                           
                             t 
                             - 
                             
                               τ 
                               m 
                             
                           
                           ) 
                         
                         2 
                       
                        
                       
                         ψ 
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                        
                       
                          
                         t 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0085]    6. Kurtosis: 
         [0000]    
       
         
           
             
               
                 
                   κ 
                   = 
                   
                     
                       
                         1 
                         T 
                       
                        
                       
                         
                           ∫ 
                           T 
                         
                          
                         
                           
                             
                               ( 
                               
                                 
                                    
                                   
                                     r 
                                      
                                     
                                       ( 
                                       t 
                                       ) 
                                     
                                   
                                    
                                 
                                 - 
                                 
                                   μ 
                                   
                                      
                                     r 
                                      
                                   
                                 
                               
                               ) 
                             
                             4 
                           
                            
                           
                              
                             t 
                           
                         
                       
                     
                     
                       σ 
                       
                          
                         r 
                          
                       
                       4 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where μ |r| =(1/T)∂ T  |r(t)|dt and σ |r| =(1/T)∂ T  (|r(t)|⊕μ |r|   2 dt. 
         [0086]    These features can be learned and evaluated with machine learning techniques, including support vector machines (SVMs), a supervised learning technique used both for classification and regression problems. SVMs are robust, have a rigorous underpinning, require few user-defined parameters, and have superior performance compared to other techniques, such as neural networks. LS-SVM is a low-complexity variation of the standard SVM that has been applied successfully to classification and regression problems. 
         [0087]    Classification: A linear classifier is a function □ n →{−1,+1} of the form 
         [0000]        l ( x )=sign [ y ( x )]  (10)
 
         [0000]      with 
         [0000]        y ( x )= w   T φ( x )+ b   (11)
 
         [0000]    where φ(•) is a predetermined function, and w and b are unknown parameters of the classifier. These parameters are estimated based on the training set {x k ,l k } k=1   N , with inputs x k ε□ n  and labels l k  ε{−1,+1}. 
         [0088]    The SVM classifier is a maximum-margin classifier, obtained by solving the following optimization problem: 
         [0000]    
       
         
           
             
               
                 
                   
                     arg 
                      
                     
                       
                         min 
                         
                           w 
                           · 
                           b 
                           · 
                           ɛ 
                         
                       
                        
                       
                         
                           1 
                           2 
                         
                          
                         
                           
                              
                             w 
                              
                           
                           2 
                         
                       
                     
                   
                   + 
                   
                     γ 
                      
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         ξ 
                         k 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           l 
                           ky 
                         
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                     ≥ 
                     
                       1 
                       - 
                       
                         ξ 
                         k 
                       
                     
                   
                   ; 
                   
                     ∀ 
                     
                       k 
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ξ 
                       k 
                     
                     ≥ 
                     0 
                   
                   , 
                   
                     ∀ 
                     k 
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where γ controls the trade-off between minimizing training errors and model complexity. (The margin is given by 1/∥w∥, and is defined as the smallest distance between the decision boundary w T φ(x)+b=0 and any of the training samples φ(x k ).) The Lagrangian dual turns out to be a quadratic program (QP). The LS-SVM replaces the inequality in Eq. ( 13 ) by an equality: 
         [0000]    
       
         
           
             
               
                 
                   
                     arg 
                      
                     
                       
                         min 
                         
                           w 
                           , 
                           b 
                           , 
                           e 
                         
                       
                        
                       
                         
                           1 
                           2 
                         
                          
                         
                           
                              
                             w 
                              
                           
                           2 
                         
                       
                     
                   
                   + 
                   
                     γ 
                      
                     
                       1 
                       2 
                     
                      
                     
                       
                          
                         e 
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           l 
                           ky 
                         
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                     ≥ 
                     
                       1 
                       - 
                       
                         e 
                         k 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       k 
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0089]    The Lagrangian dual is now a linear program (LP): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             0 
                           
                           
                             
                               l 
                               T 
                             
                           
                         
                         
                           
                             l 
                           
                           
                             
                               Ω 
                               + 
                               
                                 I 
                                 / 
                                 γ 
                               
                             
                           
                         
                       
                       ] 
                     
                      
                     
                       [ 
                       
                         
                           
                             b 
                           
                         
                         
                           
                             α 
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           0 
                         
                       
                       
                         
                           
                             1 
                             N 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Ω is an N×N matrix with Ω kl =y k y l K(x k , x l ) where K(x k , x l )=φ(x k ) T φ(x l ) is the kernel function. Solving the LP given in Eq. (17) yields the LS-SVM classifier: 
         [0000]    
       
         
           
             
               
                 
                   
                     l 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       sign 
                        
                       
                         [ 
                         
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                               
                                 α 
                                 k 
                               
                                
                               
                                 l 
                                 k 
                               
                                
                               
                                 K 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     
                                       x 
                                       k 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           b 
                         
                         ] 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0090]    Regression: A linear regressor is a function □ n →□ of the form 
         [0000]        y ( x )= w   T  φ( x )+ b   (19)
 
         [0000]    where φ(•) is a predetermined function, and w and b are unknown parameters of the regressor. These parameters are estimated based on the training set {x k ,l k } k=1   N , with inputs x k ε□ n  and outputs y k ε□. The LS-SVM regressor is obtained by solving the following optimization problem: 
         [0000]    
       
         
           
             
               
                 
                   
                     arg 
                      
                     
                       
                         min 
                         
                           w 
                           , 
                           b 
                           , 
                           e 
                         
                       
                        
                       
                         
                           1 
                           2 
                         
                          
                         
                           
                              
                             w 
                              
                           
                           2 
                         
                       
                     
                   
                   + 
                   
                     γ 
                      
                     
                       1 
                       2 
                     
                      
                     
                       
                          
                         e 
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                         
                             
                         
                          
                         y 
                       
                       = 
                       
                         
                           y 
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                         + 
                         
                           e 
                           k 
                         
                       
                     
                     ; 
                     
                       ∀ 
                       k 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where γ controls the trade-off between minimizing training errors and model complexity. The Lagrangian dual is again a LP: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             0 
                           
                           
                             
                               1 
                               T 
                             
                           
                         
                         
                           
                             1 
                           
                           
                             
                               Ω 
                               + 
                               
                                 I 
                                 / 
                                 γ 
                               
                             
                           
                         
                       
                       ] 
                     
                      
                     
                       [ 
                       
                         
                           
                             b 
                           
                         
                         
                           
                             α 
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           0 
                         
                       
                       
                         
                           y 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0000]    with corresponding LS-SVM regressor 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       y 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           N 
                         
                          
                         
                           
                             α 
                             k 
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 
                                   x 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                       
                       + 
                       b 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where α and b are the solution of the linear system in Eq. (22). 
         [0091]    Since it is not possible to determine parametric joint distributions of the features given above for LOS and NLOS conditions, embodiments of the present invention use non-parametric LS-SVM instead. A 10-fold cross-validation is used to assess the performance of the features and the SVM. This allows measurement of the performance of LS-SVM for certain features and for subsets of the available features. 
         [0092]    Classification: A LS-SVM classifier is trained to distinguish between LOS and NLOS with inputs x k  (for training examples k) and corresponding labels l k =+1 when λ k =LOS and l k =−1 when λ k =NLOS. The input x k  is composed of a subset of the following features: energy of the received signal; the maximum amplitude of the received signal; rise time; mean excess delay; RMS delay spread; and kurtosis. A trade-off between classifier complexity and performance can be made by using a different size feature subset. 
         [0093]    Regression: A LS-SVM regressor is trained to mitigate the effect of NLOS propagation with inputs x k  (for training examples k, which were classified as being NLOS), and corresponding outputs y k =ε k . Analogous to the classification case, x k  is composed of the range estimate, {circumflex over (d)} k , and a subset of the following features: energy of the received signal; the maximum amplitude of the received signal; rise time; mean excess delay; RMS delay spread; and kurtosis. Again, the performance achieved by the regressor depends on the size of the feature subset and the combination of features used. 
       Localization Strategies 
       [0094]    The LS-SVM classifier and regressor allow development of the following localization strategies: i) localization via identification, where only classification is employed; ii) localization via identification and mitigation, where the received waveform is first classified and error mitigation is performed only on NLOS estimates; and iii) a hybrid approach which discards mitigated NLOS estimates when a sufficient number of LOS estimates are present. 
         [0095]    In the standard strategy, all the range estimates {circumflex over (d)} i  from neighboring anchor nodes are used by the LS procedure for localization. In other words, 
         [0000]      Γ S ={( p   i   ,{circumflex over (d)}   i ): 1 ≦i≦N}.   (24)
 
         [0096]    In the identification strategy, signals associated with range estimates are classified as LOS/NLOS using the LS-SVM classifier. Range estimates are used in localization only if the associated signal was classified as LOS, while NLOS signals are discarded: 
         [0000]      Γ I ={( p   i   ,{circumflex over (d)}   i ): 1 ≦i≦N, {circumflex over (λ)}   i =LOS}.  (25)
 
         [0000]    Whenever the cardinality of Γ I  is less than three, the agent is unable to localize. In this case, the localization error is set to +∞. Note that measurements from three different points (e.g., three anchor nodes) are needed to localize an agent in two-dimensions. 
         [0097]    The identification and mitigation strategy is an extension to the previous strategy, where the received signal is first classified as LOS or NLOS, and then mitigation is applied to those signals where {circumflex over (λ)} i =NLOS. For this case Γ IM =Γ I ∪Γ M  where 
         [0000]      Γ M ={( p   i   ,{circumflex over (d)}   i   m ): 1≦ i≦N, {circumflex over (λ)}   i =NLOS}.  (26)
 
         [0000]    This approach is motivated by the observation that there is no need to mitigate LOS waveforms since their accuracy is already extremely high. 
         [0098]    In the hybrid approach, range estimates are mitigated as in the previous strategy. However, mitigated range estimates are only used when less than three LOS anchors are available: 
         [0000]    
       
         
           
             
               
                 
                   
                     Γ 
                     H 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             Γ 
                             1 
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                  
                                 
                                   Γ 
                                   1 
                                 
                                  
                               
                             
                             ≥ 
                             3 
                           
                         
                       
                       
                         
                           
                             Γ 
                             IM 
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
         [0000]    (In practice the angular separation of the anchors should be sufficiently large to obtain an accurate estimate. If this is not the case, more than three anchors may be needed.) This approach is motivated by the fact that mitigated range estimates are often still less accurate than LOS range estimates. Hence, only LOS range estimates should be used when they allow an unambiguous location estimate to be made. 
       Performance Evaluation and Discussion 
       [0099]    This section includes quantification of the performance of the LS-SVM classifier and regressor and the four localization strategies given above. Identification is considered first, then mitigation, and finally localization. The relevant performance measures and quantitative details of how the results were obtained are provided for every technique. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE I 
               
             
             
               
                   
               
               
                 FALSE ALARM PROBABILITY (p F ), PROBABILITY OF 
               
               
                 MISSED DETECTION (PM) AND OVERALL ERROR 
               
               
                 PROBABILITY (P err ) FOR DIFFERENT NLOS 
               
               
                 IDENTIFICATION TECHNIQUES. THE SET S i  DENOTES 
               
               
                 THE SET OF i FEATURES WITH THE SMALLEST P err   
               
             
          
           
               
                 Identification Technique 
                 p F   
                 pM 
                 P err   
               
               
                   
               
               
                 Parametric method 
                 0.184 
                 0.143 
                 0.164 
               
               
                 LS-SVM using features 
                 0.129 
                 0.152 
                 0.141 
               
               
                 LS-SVM S 1  = {r max } 
                 0.137 
                 0.123 
                 0.130 
               
               
                 LS-SVM S 2  = {r max , t rise } 
                 0.092 
                 0.109 
                 0.100 
               
               
                 LS-SVM S 3  = {ε r , t rise , κ} 
                 0.082 
                 0.090 
                 0.086 
               
               
                 LS-SVM S 4  = {ε r , r max , t rise , κ} 
                 0.082 
                 0.090 
                 0.086 
               
               
                 LS-SVM S 5  = {ε r , r max , t rise , τ MED , κ} 
                 0.086 
                 0.090 
                 0.088 
               
               
                 LS-SVM S 6  = {ε r , r max , t rise , τ MED , τ RMS , κ} 
                 0.092 
                 0.090 
                 0.091 
               
               
                   
               
             
          
         
       
     
         [0100]    Table 1 shows false alarm probability (p F ) probability of missed detection (p M ) and overall error probability (P err ) for different NLOS identification techniques and feature set sizes. The set S i  denotes the set of i features with the smallest P err . The kernel used here is a radial basis function (RBF) kernel of the form K(x, x k )=exp(−∥x−x k ∥ 2 ). The training error/model complexity tradeoff is set to γ=0.1. Features are first converted to the log domain to reduce the dynamic range. 
         [0101]    For the sake of comparison, the performance of the parametric identification technique from I. Guvenc et al., “NLOS identification and weighted least-squares localization for UWB systems using multipath channel statistics,”  EURASIP J. on Advances in Signal Processing , vol. 2008, 2008. This reference relies on the mean excess delay, the RMS delay spread, and the kurtosis of the waveform. For fair comparison, these features are extracted from the training database described above. The performance is measured in terms of the misclassification rates P err =(p F +p M )/2, where p F  is the false alarm probability (i.e., deciding NLOS when the signal was LOS), and p M  is the miss probability (i.e., deciding LOS when the signal was NLOS). 
         [0102]    LS-SVM significantly reduces the false alarm probability, compared to the parametric approach. The best set of features reduces the miss probability and achieves a total correct classification rate of above 90%, compared to roughly 85% of the time for the parametric approach. The feature set of size three provides the best performance. It turns out that among all feature sets of size three (results not shown), six sets yield roughly equal P err . All six of these sets contained rise time (t rise ), while four contained maximum amplitude (r max ), indicating that these two features play an important role. This is also corroborated by the presence of maximum amplitude and rise time in the selected sets listed in Table 1. 
         [0000]    
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 MEAN OF RESIDUAL RANGING ERROR AND AVERAGE 
               
               
                 SQUARED RESIDUAL RANGING ERROR FOR LS-SVR 
               
               
                 MITIGATION. THE SET S i  DENOTES THE SET OF 
               
               
                 i FEATURES WHICH ACHIEVES THE MINIMUM RMS RRE. 
               
             
          
           
               
                 Mitigation Technique with LS-SVR 
                 mean [m] 
                 RMS RRE [m] 
               
               
                   
               
             
          
           
               
                 No Mitigation 
                 2.6322 
                 3.589 
               
               
                 S 1  = {{circumflex over (d)}} 
                 −0.0004 
                 1.718 
               
               
                 S 2  = {κ, {circumflex over (d)}} 
                 −0.0042 
                 1.572 
               
               
                 S 3  = {t rise , κ, {circumflex over (d)}} 
                 0.0005 
                 1.457 
               
               
                 S 4  = {t rise , τ MED , κ, {circumflex over (d)}} 
                 0.0029 
                 1.433 
               
               
                 S 5  = {ε r , t rise , τ MED , κ, {circumflex over (d)}} 
                 0.0131 
                 1.425 
               
               
                 S 6  = {ε r , t rise , τ MED , τ RMS , κ, {circumflex over (d)}} 
                 0.0181 
                 1.419 
               
               
                 S 7  = {ε r , r max , t rise , τ MED , τ RMS , κ, {circumflex over (d)}} 
                 0.0180 
                 1.425 
               
               
                   
               
             
          
         
       
     
         [0103]    Table 2 shows means of residual ranging error (RRE) and average squared RRE for LS-SVM mitigation, including results for different feature set sizes. The performance is measured in terms of the RMS RRE, 
         [0000]    
       
         
           
             
               
                 
                   1 
                   / 
                   N 
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     N 
                   
                    
                   
                     
                       ( 
                       
                         ɛ 
                         i 
                         m 
                       
                       ) 
                     
                     2 
                   
                 
               
             
             . 
           
         
       
     
         [0000]    The set S i  denotes the set of i features which achieves the minimum RMS RRE. The kernel used here is K(x, x k )=exp(−∥x−x k ∥ 2 /256). The training error/model complexity tradeoff is set to γ=10. Features are first converted to the log domain to reduce the dynamic range. 
         [0104]    A detailed analysis of the experimental data indicates that large range estimates are likely to exhibit large positive ranging errors. This means that {circumflex over (d)} is a useful feature by itself, as confirmed by the table. Increasing the feature set size can further improve the RMS RRE. The feature set of size six (energy; maximum amplitude; rise time; mean excess delay; RMS delay spread; and kurtosis) offers the best performance.  FIGS. 11-14  show NLOS mitigation results achieved with feature set of size six. 
         [0105]      FIG. 11  shows the CDF of the ranging error before and after mitigation using this feature set. Without mitigation, around 30% of the NLOS waveforms achieved an accuracy of less than one meter (|ε|&lt;1). However, after the mitigation process, 60% of the cases have an accuracy less than 1 m. 
         [0106]    Simulation Setup The localization performance for varying number of anchors (N) and a varying probability of NLOS condition 0≦P NLOS ≦1 is evaluated with an agent at a position p=(0, 0). For every anchor i (1≦i≦N), a waveform is drawn from the training databases: waveforms are drawn from the NLOS database with probability P NLOS  and drawn from the LOS database with probability 1−P NLOS . The true distance d i  corresponding to that waveform are then used to place the ith anchor at position p i ={d i  sin [2π(i−1)/N], d i  cos [2λ(i−1)/N]}, while the estimated distance {circumflex over (d)} i  is provided to the agent. The agent estimates its position, based on a set of useful neighbors Γ, using the LS procedure given above, with the median of the anchor positions as the initial position estimate {circumflex over (p)} (0) . 
         [0107]    Performance Measure: The notion of outage probability is useful for capturing the accuracy and availability of localization. For certain scenarios (N and P NLOS ) and certain allowable errors (say, e th =2 m), the agent is said to be in outage when its position error ∥p−{circumflex over (p)}∥ exceeds e th . The outage probability is then given by 
         [0000]        P   out ( e   th )=         {II {∥ p−{circumflex over (p)}∥&gt;e   th }}  (28)
 
         [0000]    where I{P} is the indicator function, which, for a proposition P, is zero when P is false and one otherwise. The expectation in Eq. (28) is evaluated through Monte Carlo simulations. 
         [0108]    Results:  FIGS. 12 and 13  show outage probability as a function of the allowable error e th  for the different localization methods using the simulation setup described above evaluated with N=5 anchors for different values of P NLOS . When P NLOS =0.2 ( FIG. 12 ), on average one anchor is NLOS, possibly deteriorating the performance. When identification is employed, only the reliable LOS anchors are used. The standard strategy suffers from performance degradation compared to the identification strategy. The identification strategy does lead to an error floor phenomenon, due to the fact that the probability that less than three LOS anchors are available is approximately 0.06. 
         [0109]    Identification with mitigation does not suffer from the error floor, since all the anchors are used, but leads to some performance degradation for allowable errors below 1.5 m. The hybrid approach combines the benefits of the previous two strategies and leads to the lowest outage probability at all allowable errors. When P NLOS =0.8 ( FIG. 13 ), the identification strategy does not perform well, since the probability that less than three LOS anchors are available is approximately 0.94. 
         [0110]    The standard strategy does not fare much better, and both are outperformed by the identification and mitigation strategy. Again, the hybrid strategy leads to the best performance. As P NLOS  →1, the latter two strategies have very similar performance because most of the anchors tend to an NLOS condition, so that Γ H ≈Γ IM . 
         [0111]      FIG. 14  shows outage probability for a fixed value of error, e th =2, as a function of P NLOS . The Identification strategy is useful only when P NLOS  is very small, due to the error floor phenomenon. Identification with mitigation drastically improves the performance, and gives outages below 20%, even when all the anchors are in NLOS. The hybrid approach can further improve the performance, especially when a significant fraction of anchors are in LOS conditions. 
         [0112]    It should be readily appreciated by those of ordinary skill in the art that the aforementioned blocks are merely examples and that the present invention is in no way limited to the number of blocks or the ordering of blocks described above. For example, some of the illustrated flow diagrams may be performed in an order other than that which is described. It should be appreciated that not all of the illustrated flow diagrams is required to be performed, that additional flow diagram(s) may be added, and that some may be substituted with other flow diagram(s). 
         [0113]    It should also be apparent that methods involved in the invention may be embodied in a computer program product that includes a computer readable medium. For example, such a computer readable medium may be a read-only memory device, such as a CD-ROM disk or convention ROM devices, or a random access memory, such as a hard drive device, computer diskette, or memory having a computer readable program code stored thereon. The computer may load the program code and execute it to perform some or all of the example operations described herein or equivalents thereof. 
         [0114]    While this invention has been particularly shown and described with references to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.