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”¹   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 interest². The deployed reference nodes, depending on the available connectivity to other nodes, trilaterate 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. Alternatively, unlocalized reference nodes could share their connectivity/range information, both to fixed anchors and among themselves, and jointly estimate their locations. This is commonly referred to as collaborative position location.

• 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 trilaterate 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 PoLoNets.
 
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 the PoLoNets 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 accuracy³ , 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.

The research in this project can be divided into two parts. In the first part, we focus on the aforementioned Phase 2 and the main objective 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.

The second part of this project mainly focuses on Phase 1, i.e., estimating the locations of unlocalized reference nodes within the area of interest. This is the key  step of establishing a PoLoNet and the achieved localization accuracy has an immediate impact on the subsequent location estimation of mobile nodes in Phase 2. We are particularly interested in exploiting the idea of collaborative network position location, as it has been shown to hold the potential to both increase the location coverage and improve the localization accuracy, especially in harsh environments such as low inter-node connectivity and NLOS-dense propagation conditions. Our main objective is, via different theoretical analysis and algorithm evaluation, to understand the fundamental role of node collaboration and ultimately develop algorithms to utilize node collaboration in a more effective way.  

Overview of research and education activities:
 

1. UWB Ranging and near-ground propagation measurements:
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.
4. Conducted indoor near-ground UWB propagation measurements.
2. 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.
3. 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.
4. Power Control in U-PoLoNets:
1. Devised adaptive power control schemes based on localization-accuracy to improve robustness of location estimates.
5. NLOS identification and mitigation:
1. Developed a technique to identify NLOS measurement using signal statistical properties.
2. Studied the impact of the NLOS propagation environment on localization accuracy.
3. Proposed a new linear-programming approach that mitigates the effect of NLOS propagation and outperforms least-squares location estimators.
6. Limiting the propagation of localization error:
1. Studied the impact of the propagation of localization error.
2. Developed a novel multi-hop bounding based technique to mitigate the propagation of localization error.
7. Collaborative Position Location:
1. Examined a technique to improve GPS-provided position solutions to nodes based on measurements taken in forests.
2. Proposed a collaborative quasi-linear programming approach to handle both NLOS mitigation and node collaboration.
3. Proposed and examined a method to localize a network of nodes based on global nonlinear optimization using GPS-provided node positions as initial solutions.
4. Developed a probabilistic position location framework. Examined its efficacy in distinguishing localizable and un-localizable nodes. Proposed an NLOS mitigation technique and demonstrated its effectiveness for probabilistic position location.
8. An improved and more realistic CRLB:
1. Derived a new CRLB based on a distance-dependent SNR modeling, which directly relates inter-node distance to the final localization accuracy.
2. Used the new CRLB to interpret the role of node collaboration and demonstrated that the improvement on localization accuracy from node collaboration beyond 3-hop diminishes.
9. Simulation Platform:
1. Developed simulation software for the evaluation and testing of the performance of protocols and algorithms implemented on ad hoc U-PoLoNets.
2. Developed an integrated graphic user interface (GUI) to evaluate the performance of different collaborative position location algorithms.

Overview of findings resulting from these activities:

1. UWB Ranging and near-ground propagation measurements:

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, applying the energy-threshold range estimator to the measurement data, we derived mathematical models for both line-of-sight (LOS) and non-line-of-sight (NLOS) range estimates (see Figures 1 and 2). These models are used later to evaluate position location algorithms.

We also conducted time-domain measurements of the indoor near-ground UWB channel and determine channel characteristics from the data [C2, C10]. We compared the near-ground (NG), middle-ground (MG) and above-ground (AG) signal propagations and observed that as the antenna height decreases, the path loss, shadowing variance increases, which is consistent with existing results, as shown in Figures 3 and 4, respectively. Small scale channel characteristics, on the other hand, do not show a straightforward behavior with respect to antenna height. 
 
 

                                                   (a)                                                                                                   (b)

2. 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 6), 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 [J3]. It was found that the number of range estimates available plays a crucial role in determining localization accuracy (see Figure 5), 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 5).

Figure 5: The effect of node geometry on localization accuracy.

Figure 6: The performance of the LS estimator versus the CRLB.

 

 

3. Multiple-Access Design in U-PoLoNets: 

Based on the findings in Item 2 above, a new spread-spectrum multiple-access access scheme was devised [C1] 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 7) 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 8), 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.

4. Power Control in U-PoLoNets: 

5. NLOS identification and 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. We first developed a technique to identify NLOS range estimates based on the received signal statistics [J2]. With this knowledge, a new linear-programming (LP) approach [J1,C3], 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 11) 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 12). 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 12).

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

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

6. Limiting the propagation of localization error: 

For a network of unlocalized nodes, extending the location coverage, i.e., to localize as many nodes as possible, is a key task. A simple way to achieve that is to use sequential location estimation. We studied the various ways of increasing the area over which the desired localization accuracy can be guaranteed when sequential estimation is used: (i) improving range measurement accuracy, (ii) using a superior (with minimal bias) location estimator, (iii) increasing node density, (iv) increasing transmit power, (v) improving the geometry of anchor nodes, (vi) using methods to mitigate the propagation of error. A novel method of mitigating the propagation of localization error based on linear-programming that incorporates NLOS range estimates was proposed [C7]. This can be seens from Figures 13 and 14.

Figure 14: In the NLOS environment, the sequential LP again outperforms the sequential LS estimator and the performance improvement increases as the portion of NLOS range estimates incresases.

7. Collaborative Position Location: 

   We evaluated a technique for improving the localization performance based on the global positioning system (GPS) for networks of nodes in harsh environments and demonstrate its efficacy via a combination of simulations and measurements in forests [C8]. Specifically, we create a system of range equations based on network connectivity and solve this system of nonlinear equations using a nonlinear least squares (LS) optimization technique, with any available GPS information as the initial estimate. Based on our simulations and measurements, the improved technique results in localization accuracy in forests that is on par with clear-field reference GPS measurements.

Figure 15: The localization error of the nonlinear optimization based approach, compared to positioning error of GPS-alone system, versus the number of collaborating sensors. As can be seen, the more collaborating nodes, the smaller the localization error.

Figure 16: The localization error of the nonlinear optimization based approach, compared to positioning error of GPS-alone system, versus the amout of noise in the range estimates. As the UWB range estimates become worse, the improvement over GPS solution becomes smaller.

The abovementioned technique needs centralized computation in order to solve the system of nonlinear equations. We developed a distributed collaborative quasi-linear programming (CQLP) approach to deal with both NLOS mitigation and node collaboration [C6]. The proposed method is able to handle the degenerate cases in the LP method and significantly increases the location coverage. The improvement can be seen from Figures 17 and 18.

 

Figure 17: The location coverage of the proposed CQLP approach and the sequential LS estimator. The number of hops indicates the degree to which nodes are collaborating to each other. It is observed that the CQLP significantly increases the locatin coverage and the improvement diminishes as the number of hops is greatler than two.
Figure 18: The localization error of the proposed CQLP approach and the sequential LS estimator. It is observed that the CQLP with three-hop node collaboration outperforms the sequential LS estimator. The localization accuracy improves as the number of hops inceases, i.e., more nodes are collaborating,.

In view of some limitations associated with existing algorithms in terms of addressing both node localizability and efficiently incorporating node collaboration, we investigated the framework probabilistic position location. Probabilistic position location differs from existing work in the sense that position solution is no longer a one-shot solution. In stead, a set of possible position solutions, namely particles, is returned and each solution is associated with a probability measure quantifying the uncertain about that solution. We demonstrate that this framework is effective in identifying localizable and un-localizable nodes (Figure 19). In addition, we developed a simple NLOS mitigation technique, which incorporates spatial constraints to the particle updating procedure, and greatly improves the convergence result in NLOS-dense environment (Figure 20).

Figure 19: Illustration of localizability under the framework of probabilistic position location. As shown, particles of the node on the left converged well to within a small area, thus is considered as being localizable. On the other hand, particles of the node on the right are spread over a larger area, therefore will not be regarded as localizable.

Existing work on probabilistic position location has either high computationaly complexity or has not considered practical problems such as NLOS measurements. In lieu of the above results, we are currently developing a probabilistic position location algorithm that can better utilize node collaboration as well as exploit NLOS range estimates, especially for NLOS-dense and low-connectivity environments. In addition, we are also developing methods to incorporate other information such as angle-of-arrival (AOA) and altimeter readings into our probabilistic position location framework.

8. An improved CRLB for indoor collaborative position location

Despite many algorithms that have been developed for collaborative position location, a theoretical framework explaining the fundamental limits and exact role of node collaboration is still not available. Traditional metric such as Cramer-Rao lower bound (CRLB) is not perfectly suitable for this task. In this work, we derived a new CRLB based on a distance-dependent signal-to-noise ratio (SNR) modeling, which equivalently relates the range estimation noise to inter-node distance [C9]. We believe this is a more appropriate model for indoor position location where the difference in inter-node distances could lead to significant difference in the amount of noise to be seen at different range estimates. The fact that the new CRLB is lower than the existing CRLB corroborates our belief that this readily-available knowledge should be exploited in designing indoor position location algorithm. Figure 21 below shows that the new CRLB is in general lower than the old CRLB and the two are almost the same when the path loss exponent is 2. Figure 22 shows that there is still a performance gap between the popular LS estimator and the CRLB. We are currently exploring the possibility of using the new CRLB to investigate the fundamental role of node collaboration.

9. An integrated graphic user interface (GUI): 

We developed an integrated GUI for evaluating different collaborative position location algorithms (Figure 23). The platform provides a uniform interface and simulation settings that can be used to conveniently assess the performance of different algorithms with the help of specially designed visualization and statistics collections tools.

Journal Articles

[J1] “NLOS mitigation using linear programming in ultrawideband location-aware networks”, S. Venkatesh and R. M. Buehrer; IEEE Transaction on Vehicular Technoogy, vol. 56, no. 4, pp. 3182-3198, Sept. 2007.

[J2] “Non-line-of-sight identification in ultra-wideband systems based on received signal statistics”, S. Venkatesh and R. M. Buehrer; IET Microwaves, Antennas and Propagation, vol. 1, no. 6, pp. 1120-1130, Dec. 2007.

[J3] “Multiple-access insights from bounds on sensor localization ”, S. Venkatesh and R. M. Buehrer, Elsevier Journal on Pervasive and Mobile Computing, vol. 4, no. 1, pp. 33-61, 2008.

Conference Publications

[C1] “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, Apr. 2006.

[C2] “Measurement and characterization of the near-ground indoor ultra wideband channel”, A. Hugine, H. I. Volos, J. Gaeddert and R. M. Buehrer; Proceedings of IEEE Wireless Communication and Networking Conference (WCNC 2006), vol. 2, pp. 1062-1067, Apr. 2006.

[C3] “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, Apr. 2006.

[C4] “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, Jun. 2006.

[C5] “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, Jun. 2006.

[C6] “A collaborative quasi-linear programming framework for ad hoc sensor localization”, T. Jia and R. M. Buehrer, Proceedings of IEEE Wireless Communication and Networking Conference (WCNC 2008), pp. 2379-2384, Apr. 2008.

[C7] “Mitigation of the propagation of localization error using multi-hop bounding”, R. M. Buehrer, S. Venkatesh and T. Jia, Proceedings of IEEE Wireless Communication and Networking Conference (WCNC 2008), pp. 3009-3014, Apr. 2008.

[C8] “An improved method for GPS-based network position location in forests”, C. Hutchens, B. Sarbin, A. Bower, J. McKillican, K. Forrester and R. M. Buehrer, Proceedings of IEEE Wireless Communication and Networking Conference (WCNC 2008), pp. 273-277, Apr. 2008.

[C9] “A new CRLB for TOA-based localization”, T. Jia and R. M. Buehrer, Proceedings of IEEE Military Communications Conference (MilCom 2008), Nov. 2008.

[C10] “On the effect of antenna height on the characterization of the indoor UWB channel”, U. K. Shukla, H. I. Volos and R. M. Buehrer, Proceedings of IEEE Global Telecommunications Conference, New Orleans, LA, Dec. 2008.