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:
-
equip each firefighter with
awareness of his own
location,
-
equip command-and-control with
knowledge of each firefighter’s
location,
-
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
- Simulation
Platform:
Developed simulation software for the evaluation and testing of
the performance of protocols and algorithms implemented on ad hoc
U-PoLoNets.
- UWB Ranging:
- Measurement
results confirming accurate ranging capabilities using UWB
signals.
- Investigation of
the performance of practical range estimators using UWB
multipath profiles.
- Modeling of the
accuracy of practical range estimators in LOS and NLOS
conditions.
- Localization
Accuracy:
- Localization
Bounds and Performance of various practical Location Estimators.
- Impact of
different parameters on localization accuracy.
- Insights into
other design areas from the perspective of localization
accuracy.
- Multiple-Access
Design in U-PoLoNets:
- Proposed a new
time-hopping spread spectrum MAC protocol.
- Comparison with
CSMA from the perspective of localization accuracy based on
simulations under realistic
scenarios.
- Power Control
in U-PoLoNets:
- Devised adaptive
power control schemes based on localization-accuracy to improve
robustness of location
estimates.
- NLOS
mitigation:
- Studied the
impact of the NLOS propagation environment on localization
accuracy.
- 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
-
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.
-
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.
|
-
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.
|
-
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].
|
-
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.
|
