Ultra-Wideband

  More research...
Home
UWB Overview
People
Research at MPRG
       - Channel Modeling
       - Receiver Design
       - Position Location
       - UWB MIMO
Publications
Facilities
Links

UWB Position-Location Networks (U-PoLoNets)

 

This project is funded by the National Science Foundation (NSF) under Grant #0515019.

 

Introduction to U-PoLoNets

 

Impulse-based UWB (henceforth simply referred to as UWB) has some unique advantages over traditional narrowband systems:

• The received pulses are relatively immune to the multipath effects that narrowband systems suffer from, due to the fine time resolution provided by UWB signals, which allows the resolution of multipath components. Additionally, UWB signals have strong material penetration capabilities (particularly in the lower bands approved by the FCC), which is desirable in indoor networks.

• Due to the short duration of the pulses, UWB can be used for precise positioning and tracking of devices and offers the potential to fuse communications, positioning and sensing functionalities.

• UWB has the potential to support high data rates while appearing noise-like to other RF technologies, and offers inherent data security due to covertness with applications in battlefield communications.

 

In the following, we describe the applications of Position-Location Networks (PoLoNets), where UWB is envisioned as an ideal physical layer (PHY) solution.

 

UWB Position Location Networks (U-PoLoNets)   

 

Position-location has historically been a desired feature in many commercial and military applications. Navigation was the primary use of position information with man-made systems being used as early as the 1950’s (e.g., Loran-C Navigation system) and exploding with the advent of the Global Positioning System (GPS). More recently, position location has been an active area of research in many areas including cellular E-911, sensor networks, ad hoc networks, robotics, and ubiquitous computing. Current applications of PoLoNets include inventory control, home automation, safety networks, tracking personal items, personnel monitoring, command and control in emergency situations, the guidance of robots in remote locations, and many others. In fact, the IEEE 802.15.4a standard, a standard for low power, low-data rate wireless is primarily focused on position location applications.

 

In outdoor environments, accurate position information can be obtained via GPS. However, there are many situations where GPS is either unreliable (e.g., indoor scenarios), or impractical (e.g., where GPS receivers are too bulky or expensive), requiring the development of other solutions. As one example, consider the command and control of a firefighter operation where multiple personnel are deployed into a building. For safety and efficiency purposes, it would be extremely helpful for a command center outside the building to be established for not only communication but also position tracking as shown in the Figure below. In such a case, we require an ad hoc position location and communication network that is independent of GPS and is not reliant on pre-existing infrastructure.

 

The goal of such a network would be to:

  1. equip each firefighter with awareness of his own location,
  2. equip command-and-control with knowledge of each firefighter’s location,
  3. allow the exchange of short messages between firefighters and command-and-control.

Therefore, these networks extend location-awareness within the area of interest, in addition to serving as a communications network. Traditional ranging (and position location) applications have relied on optical (laser), ultrasound, or narrowband RF physical layers. It is well known that optical and ultrasound have limited range in harsh environments and may fail completely when the line-of-sight (LOS) is blocked. Additionally, narrowband RF solutions have difficulty in dense multipath due to severe multipath fading. However, UWB is an excellent physical layer solution because of its usefulness in harsh multipath environments, material penetration capabilities, its ability to fuse accurate position-location with low-data rate communication and its covertness for tactical applications. Due to the nature of the indoor propagation environment and the power restrictions on UWB systems, in order to provide the mentioned features over a sizable area, we would require a multi-hop network of nodes that serve as a location network. The following section provides the description of a network solution that can be used for the discussed application.

 

  

Network Architecture:

 

A specific network architecture that can be used for the described application is shown above . The network consists of a small number of “location-aware” or “localized”1   fixed anchors located outside the area of interest. The locations of fixed anchors maybe be available via GPS or by setting up a local coordinate system.

Starting from the setup instant, the network evolves in two phases:  

  • Phase 1: Nodes called propagated anchors or reference nodes, whose locations are unknown a priori, are deployed  in the region of interest2. The deployed reference nodes, depending on the available connectivity to other nodes, triangulate their locations using range estimates from fixed anchors or other reference nodes whose locations have already been estimated. Reference nodes that estimate their location provide range-estimates to other unlocalized reference or mobile nodes. Each “layer” of location-aware reference nodes serves as a source of range information for the subsequent layer, thereby “propagating” location-awareness, even in the absence of direct connectivity with fixed anchor nodes.
  • Phase 2: After the reference nodes have estimated their own locations by ranging to one another or to fixed anchors, the second phase of the network involves assisting any mobile node that enters the area by providing a framework to estimate its location. Mobile nodes, depending on their location and available connectivity, communicate with a subset of fixed anchors and/or reference nodes whose locations have been estimated in order to obtain range information. These range estimates are used to triangulate their locations. Additionally, in this phase the reference nodes provide a multi-hop communication network to relay the mobiles’ position information to, and short messages from, the data-sink (command-and-control).

In this manner, through the network of reference nodes, (i) location-awareness is propagated from the fixed anchors located outside the area of interest to the mobile nodes within the area of interest, and (ii) mobile node location information is passed from the mobile nodes to the data-sink. It is important to point out the shift in emphasis on location-estimation in PoLoNets vis-a-vis traditional sensor and mobile ad hoc networks. In sensor and ad hoc networks, location-estimates are typically used in order to improve performance of the medium access control (MAC) and routing algorithms, but are not the main objectives of the network.

 

One can view a PoLoNet as a generic sensor network where the physical parameter being sensed is the location of the mobile nodes. However, unlike sensor networks the expected lifetime of such networks may be limited (e.g., position location in emergency scenarios) and thus energy efficiency is not always the primary focus. On the other hand, PoLoNets are different from typical mobile ad hoc networks where large quantities of data may have to be transported across the network with a certain Quality-of-Service (QOS) while minimizing latency. In contrast, in PoLoNets, (i) while energy efficiency may be one metric of interest, in a majority of cases localization accuracy3 , reliability of communication, survivability and scalability may take priority over energy efficiency and (ii) brief messages are assumed to be exchanged between the nodes of the network at low data rates.

 

Classification of PoLoNets : The networks described in the previous subsection can be classified on the basis of infrastructure, range-information, synchronization and the computational capabilities of the nodes.

  • Infrastructure-based Vs. Ad hoc reference node network: In the case where the network of reference nodes is deployed in the area of interest in advance, with each reference node placed in a known location (thereby serving as a fixed anchor within the area of interest), such a network is called an infrastructure-based network. It must be noted that in most cases it may not be possible to have an infrastructure of stationary location-aware reference nodes within the area of interest a priori. In such a case, reference nodes can be deployed at the time of use in an ad hoc fashion. 
  •  Range Information: Range information of several kinds can be used to estimate node locations. The most important categories are (i) Time-of-Arrival (TOA)-based range estimates, (ii) Time-Difference-of-Arrival (TDOA) based range estimates, (iii) Received Signal Strength (RSS) based range estimates and (iv) Connectivity based range information. UWB signals can be used for accurate TOA-based range estimation. RSS-based are typically used in narrowband sensor networks.
  • Synchronous Vs. Asynchronous: If all nodes share a common clock, they are said to be synchronous; if each node possesses a unique clock, they are said to be asynchronous.
  • Centralized Vs. Distributed Solver: Due to constraints on the hardware complexity or limited connectivity of the radios, it may not be possible for each node to estimate its location. Therefore, range and location information have to be routed to a centralized “location-solver”. If all nodes are capable of solving for their coordinates, then we call such a scenario a distributed solver as opposed to a centralized solver.  

1. A node is said to be “location-aware” or “localized” if its location is known or can be estimated based on available range information. A node whose location is unknown and cannot be estimated is said to be “unlocalized”. 

 2. Deployment options are not considered here but reference nodes could either be pre-existing, deployed manually as in a fire-fighter scenario, via tiny robots, dispersed via UAV, or launched into the area of interest.

3. For instance, in a fire-fighter [1] position-tracking system, the knowledge of whether a firefighter is on one side of a door or the other, could be critical.

 

 

Summary of Objectives

 

The main objective of this project is the design and modeling of ad hoc position-location networks in which position information is propagated through a network of reference nodes in order to track the locations of mobile nodes. This creates a framework for the tracking of mobile nodes and well as a multi-hop message-passing infrastructure between mobile nodes and control nodes located outside the area of deployment. The main goal is to derive design principles and analytical models for the performance of such networks that serve as useful tools in the development of practical solutions.

 

Overview of research and education activities

 

 

  1. Simulation Platform: Developed simulation software for the evaluation and testing of the performance of protocols and algorithms implemented on ad hoc U-PoLoNets.
  2. UWB Ranging:
    1. Measurement results confirming accurate ranging capabilities using UWB signals.
    2. Investigation of the performance of practical range estimators using UWB multipath profiles.
    3. Modeling of the accuracy of practical range estimators in LOS and NLOS conditions.
  3. Localization Accuracy:
    1. Localization Bounds and Performance of various practical Location Estimators.
    2. Impact of different parameters on localization accuracy.
    3. Insights into other design areas from the perspective of localization accuracy.
  4. Multiple-Access Design in U-PoLoNets:
    1. Proposed a new time-hopping spread spectrum MAC protocol.
    2. Comparison with CSMA from the perspective of localization accuracy based on simulations under realistic scenarios.
  5. Power Control in U-PoLoNets:
    1. Devised adaptive power control schemes based on localization-accuracy to improve robustness of location estimates.
  6. NLOS mitigation:
    1. Studied the impact of the NLOS propagation environment on localization accuracy.
    2. Proposed a new linear-programming approach that mitigates the effect of NLOS propagation and outperforms least-squares location estimators.

 

 Overview of findings resulting from these activities

 

  1. UWB Ranging:

Indoor UWB Measurement results were conducted in order to demonstrate the accuracy of UWB time-of-arrival (TOA) based ranging. Using practical low-complexity TOA estimators, range errors of less than 5 centimeters were observed at a distance of 5 meters. Analysis and simulation of practical range estimators were carried out to arrive at models for range measurement errors in U-PoLoNets. Specifically, an analysis of the energy-threshold range estimator provided the characterization of the accuracy of range estimates in terms of the width of transmitted pulses, node distances, signal-to-noise ratios and applied thresholds (see Figures 1 and 2).

 

 

 

Figure 1: Modeling of the probability density functions of the range errors in UWB systems for different values of the pulse-widths employed and for different distances. A simple energy- threshold range estimator was used. We see that as the distance between transmit and receive nodes or the pulse-width increases, the mean and variance of the absolute range error increases.

Figure 2: Sensitivity of the mean range error to the threshold applied. We see that the threshold needs to be chosen well above the noise level in order to obtain reasonable range accuracy.

 

 

  1. Localization Accuracy:

Based on the range error models obtained in Item 1 above, we studied bounds on localization accuracy and the performance of various practical location estimators. The impact of different network parameters such as node density, geometry (see Figure 4), and the accuracy of range estimates was studied and insights into other design areas such as multiple-access and power-control schemes from the perspective of localization accuracy were developed [5]. It was found that the number of range estimates available plays a crucial role in determining localization accuracy (see Figure 3), and that increasing the number of available range estimates improves the average localization accuracy. Further, it was demonstrated that practical estimators such as the least-squares estimator exhibit similar trends (see Figure 3).

Figure 3: Comparison of the LS estimator with the CRLB for two-dimensional location estimation given m unbiased Gaussian range estimates.Figure 4: Impact of Geometry on the LS location Estimate. As the number of range estimates (m) increases, the localization accuracy is less sensitive to geometry of the nodes.

Figure 3: Comparison of the LS estimator with the CRLB for two-dimensional location estimation given m unbiased Gaussian range estimates.

Figure 4: Impact of Geometry on the LS location Estimate. As the number of range estimates (m) increases, the localization accuracy is less sensitive to geometry of the nodes.

 

 

 

  1. Multiple-Access Design in U-PoLoNets:

Based on the findings in Item 2 above, a new spread-spectrum multiple-access access scheme was devised [1] that ensures a high throughput of range estimates to unlocalized nodes, thereby ensuring high localization accuracy. This scheme relies on the assignment of time-hop codes to different transmitting nodes and was designed for the case where the network (distributed, ad hoc PoLoNet) is asynchronous. Using the U-PoLoNet simulator, this scheme was shown to outperform the carrier-sense multiple access (CSMA) protocol with respect to localization accuracy (Figure 5) as a function of time. Further, it was verified that the improvement achieved by the proposed scheme over the CSMA-based scheme in terms of localization accuracy can be attributed to a higher throughput of range estimates (Figure 6), confirming the insights gained from Item 2.

A video of the simulation of the deployment of  the proposed multiple access scheme in a U-PoLoNet with the described architecture can be found here.

 

Figure 5: A comparison of the performance of the proposed protocol and CSMA in terms of the average network localization error versus time for different values of the path loss exponent. We see that the network localization error decreases much faster for the proposed approach than for the CSMA scheme.

Figure 6: A comparison of the performance of the proposed protocol and CSMA in terms of the average number of ranging packets received successfully within the network versus time. The proposed approach clearly has a much higher effective throughput of ranging packets.

 

 

 

  1. Power Control in U-PoLoNets:

From Item 2, it was observed that the localization error of a node is dependent on the geometry of reference nodes, connectivity with localized reference nodes and range estimate variances (which depend on the distances between nodes from Item 1). As a mobile node moves through a network of reference nodes, all these quantities can vary with time and therefore, the localization error of a mobile node fluctuates with the progression of time. Figure 7 illustrates an example of the variation of a mobile node’s localization error as it moves through an area containing randomly distributed reference nodes. The localization error fluctuation is analogous to the spatial fading of received signal power in wireless propagation channels. An adaptive power control scheme based on localization-accuracy was developed [2] which makes the obtained location estimates more robust (Figure 8) and accurate. This power control scheme attempts to determine the optimal transmit power [2] that an unlocalized node needs to use to ensure a given localization accuracy.

 

Figure 7: “Spatial Fading” of Localization Accuracy. The localization error of the mobile node fluctuates with time due to the variation of the relative geometry of reference nodes, connectivity with localized reference nodes and range estimate variances.

Figure 8: (a) Trajectory of Mobile Nodes, and  (b) Reduction in “Spatial Fading” of localization error using power control [2].

 

 

  1. NLOS mitigation:

The NLOS propagation environment is known (from previous work in cellular systems) to severely degrade the accuracy of TOA-based range estimates. Since significant envisioned applications of U-PoLoNets rely on indoor location tracking, the indoor non-line-of-sight (NLOS) propagation environment poses a formidable challenge in attaining the requisite localization accuracy. A new linear-programming (LP) approach [4], [6], was devised which mitigates the impact of the NLOS propagation environment on localization accuracy. The efficacy of this scheme was demonstrated in the simulation of a U-PoLoNet deployed in a dense multipath environment (Figure 9) where it was observed that the proposed approach not only mitigates the effect of NLOS propagation, but can take advantage of biased NLOS range estimates to improve localization accuracy (Figure 10). This is in contrast to the least-squares (LS) estimator, whose performance degrades if NLOS range estimates are incorporated without mitigation of bias errors (Figure 10).

 

A video of a sample simulation of NLOS mitigation can be found here.

 

Figure 9: 2D NLOS mitigation in a NLOS propagation environment: The mobile node moves through the network of anchor nodes at a speed v = 2.5 m/s. Every Ts=1 second, the mobile computes its location based on available range estimates.

Figure 10: Variation of the localization error obtained using different approaches with time. On the average, the LP approaches outperform the LS approaches.

 

 

 

 

Publications

 

 

[1] “Multiple-Access Design for Ad hoc UWB Position-Location Networks”, S. Venkatesh and R. M. Buehrer; Proceedings of the 2006 IEEE Wireless Communications and Networking Conference (WCNC 2006), vol. 4, pp. 1866-1873, April 3-6, 2006, Las Vegas, USA.

 

[2] “Power-Control for UWB Position-Location Networks”, S. Venkatesh and R. M. Buehrer; Proceedings of the 2006 IEEE International Conference on Communications (ICC 2006), vol. 9, pp. 3953-3959, June 11-15, 2006, Istanbul, Turkey.

 

[3] “A Linear Programming Approach to NLOS Error Mitigation in Sensor Networks”, S. Venkatesh and R. M. Buehrer, Proceedings of the Fifth International Conference on Information Processing in Sensor Networks (IPSN), pp. 301-308, April 19-21, 2006, Nashville, USA.

 

[4] “NLOS Mitigation in UWB Position Location Networks Using Linear Programming”, S. Venkatesh and R. M. Buehrer, Invited Paper, to appear in the Proceedings of the IEE Seminar on Ultra Wideband Systems, Technologies and Applications, April 20, 2006, London.

 

[5] “Multiple-Access Insights from Bounds on Sensor Localization”, S. Venkatesh and R. M. Buehrer; to appear in the Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp. 3-12, Niagara-Falls, Buffalo-NY, June 26-29, 2006.

 

[6] “NLOS Mitigation in UWB Location-aware Networks Using Linear Programming”, S. Venkatesh and R. M. Buehrer, to appear in IEEE Transactions on Vehicular Technology, November 2007.



Mobile & Portable Radio Research Group
Virginia Tech
Tel: (540) 231-2971
FAX: (540) 231-2968
Email: mprg@vt.edu