#  DynoLoc: Infrastructure-free RF Tracking in Dynamic Indoor Environments

Md. Shaifur Rahman1, Ayon Chakraborty2, Karthikeyan Sunderasan3, Sampath
Rangarajan4  1Stony Brook University  2IIT Madras  3Georgia Tech  4Peraton
Labs

###### Abstract

Promising solutions exist today that can accurately track mobile entities
indoor using visual inertial odometry in favorable visual conditions, or by
leveraging fine-grained ranging (RF, ultrasonic, IR, etc.) to reference
anchors. However, they are unable to directly cater to “dynamic” indoor
environments (e.g. first responder scenarios, multi-player AR/VR gaming in
everyday spaces, etc.) that are devoid of such favorable conditions. Indeed,
we show that the need for “infrastructure-free”, and robustness to “node
mobility” and “visual conditions” in such environments, motivates a robust RF-
based approach along with the need to address a novel and challenging variant
of its infrastructure-free (i.e. peer-to-peer) localization problem that is
latency-bounded – accurate tracking of mobile entities imposes a latency
budget that not only affects the solution computation but also the collection
of peer-to-peer ranges themselves.

In this work, we present the design and deployment of DynoLoc that addresses
this latency-bounded infrastructure-free RF localization problem. To this end,
DynoLoc unravels the fundamental tradeoff between latency and localization
accuracy and incorporates design elements that judiciously leverage the
available ranging resources to adaptively estimate the joint topology of
nodes, coupled with robust algorithm that maximizes the localization accuracy
even in the face of practical environmental artifacts (wireless connectivity
and multipath, node mobility, etc.). This allows DynoLoc to track (every
second) a network of few tens of mobile entities even at speeds of 1-2 m/s
with median accuracies under 1-2 m (compared to 5m+ with baselines), without
infrastructure support. We demonstrate DynoLoc’s potential in a real-world
firefighters’ drill, as well as two other use cases of (i) multi-player AR/VR
gaming, and (ii) active shooter tracking by first responders.

##  1 Introduction

Dynamic indoor environments. Several promising solutions exist for indoor
localization today that leverage various modalities (RF [2, 3, 4, 5, 2],
ultrasonic [6], optical (IR) tracking [7], etc.) and multiple dimensions
(antennas, channels, access points, etc.) to provide fine-grained (sub-meter,
decimeter-level) localization. A natural question that arises is do we really
need another indoor localization solution? The answer indeed depends on the
capabilities of the environment, where the solution is deployed. The bulk of
today’s localization solutions rely on the deployment of static anchor nodes
(in known locations) that provide distance estimation to a target client
(a.k.a. ranging), which are then aggregated to deliver its location. However,
ranging is a latency-bound operation and localization without taking into
consideration the cost of operation, node mobility, link quality (LOS/NLOS)
can cause poor accuracy in localization even with fixed anchors, see path-1
vs. path-2 in Fig. 1 which are derived by without and with consideration of
the above factors for a mobile node.  On the other hand, infra-free solutions
based on inertial sensors are prone to accumulating errors of tens of meters
over time [8, 9]; Even the high-accuracy (cm-level) solutions for AR/VR that
are based on Visual Inertial Odometry (VIO) [10] (fuse cameras and IMUs),
suffer appreciably (as shown in Fig. 2) when the environment is not well-
lit/textured, has motion blur and/or dynamic entities in screen, etc.
Unfortunately, these existing anchor-based and infra-free solutions do not
lend themselves to “dynamic” indoor environments that are inherently
characterized by the lack of reference anchors, unfavorable visual conditions,
and mobile entities.

Figure 1:  (a) Two paths on the floormap dotted by fixed anchors- the mobile
node on i) path 1 ranges with all anchors ii) on path 2, ranges with
nearest/LOS 3 anchors (b) Avg. localization errors for the 2 derived paths
Figure 2:  A simple experiment to demonstrate persistent localization errors
in a VIO based system (Intel RealSense [1]). VIO exhibits high tracking
accuracy under good lighting conditions, but deteriorates greatly when
traversing a dim-lit region, from which it is unable to recover. Fusing RF-
based (UWB anchors) localization with VIO can curtail such accumulation of
errors.  Figure 3: DynoLoc was deployed and tested in a real firefighters’
drill attended by 10$+$ firefighters in a 2-storey building (100 m$\times$50
m). The basic building blocks of DynoLoc’s algorithm are shown as a schematic
that estimates absolute locations of the firefighters. The fire chief at the
command and control station gets a real-time visual feedback through our
dashboard application.

RF-based localization for dynamic environments: Localization and tracking in
such dynamic environments, especially with mobile clients, are not only
central to all first responder scenarios, but also enable new capabilities in
emerging consumer applications like mixed-reality (MR) gaming, where multiple
players engaged in an AR/VR game can be freely tracked in real-time across
large, everyday (unmapped) indoor spaces that span multiple rooms in less-
than-favorable visual conditions. An RF-based localization solution that can
deliver high accuracies (sub-m if not cm) without relying on anchors, can fill
this critical need as a stand-alone solution for first responder applications,
and a complementary solution to VIO (for alleviating its errors) for MR gaming
applications, owing to its robustness in unfavorable visual conditions.

Gap between ranging and localization. Obtaining accurate ranges (i.e.
distances) between the clients and anchors in infrastructure solutions,
automatically leads to accurate localization of clients (also referred to as
nodes) through multilateration. However, in the absence of such anchor
infrastructure, nodes are capable of ranging only with respect to each other.
There exists a large technical gap in going from such relative ranging to
localization in dynamic environments, where existing multilateration
approaches cannot be leveraged.

Challenges in addressing the gap. Localizing nodes in an absolute frame of
reference may be challenging without one or more reference nodes. However,
existing works in the sensor literature have shown that if one can estimate
the relative geometry of nodes (called relative localization, e.g. Fig. 5(a))
using their pair-wise measured ranges; then, additional information (such as
IMU data, floor plan, etc.) can be used to potentially rotate, translate or
flip this relative geometry to obtain the absolute localization of the nodes.
The resulting efforts that focused on relative localization albeit amenable to
theoretical analysis, however, do not account for a critical dimension needed
for practical deployments, namely node mobility. Incorporating the latter
however, significantly changes the nature of the problem, requiring one to
solve the latency-bounded version of the infrastructure-free RF localization
problem, which has not been addressed before. Indeed, infrastructure-free
localization solutions today are unable to track even a network of around 10
mobile nodes (at just 1 m/s speed) with an accuracy of under 6m (as shown
later in Fig. 12b). This can be attributed to the following key challenges:

(i) Latency vs. accuracy tradeoff: Accurate location of the nodes needs to be
tracked at least every second (i.e. refresh rate of 1 Hz) for a node mobility
of 1-1.5 m/s. The corresponding latency constraint restricts the number of
node-pairs that can be ranged (before computing a localization solution),
thereby lowering the accuracy of localization significantly by several folds
(Fig. 6a). Further, the quality of links (edges) and hence the ranges
measured, are in turn impacted by the geometry of the induced topology, node
mobility as well as the multi-path wireless channel, and have a large impact
on the accuracy as well (Figs. 8a, 8b).

(ii) Overhead of range measurements: Ranging between node pairs is typically
accomplished through sequential packet exchanges and time-of-flight estimation
techniques , thereby incurring a large latency and hence reduced ability to
track a large network of mobile nodes (Fig. 6b) .

(iii) Partial information degrades accuracy: Existing solutions for relative
localization (e.g. techniques using Euclidean distance matrices, EDM ) work
well when network topologies are a complete graph and all range estimates are
available and accurate. However, in the absence of such features in practical
deployments, the accuracy can suffer appreciably (Figs. 7a, 7b).

$\blacksquare$ DynoLoc (Dynamic Indoor Localization) design. Towards
addressing these challenges, we present DynoLoc– a system for latency-bounded
infrastructure-free localization that can be readily deployed in dynamic
indoor environments. While DynoLoc’s framework is agnostic to the underlying
wireless technology (e.g. WiFi, UWB, mmWave) used for ranging, it currently
employs UWB, given the latter’s ability to offer good ranging resolution (tens
of cm) at reasonable indoor penetration (70-90m LOS, 30-50m NLOS). DynoLoc
equips each of the nodes that need to be tracked with a tag that encompasses a
UWB radio (for ranging), WiFi radio (for control/orchestration), and IMU.
While UWBs are the primary source of active ranging, IMUs are used in a
limited scope (heading and mobility indication) only to resolve ambiguities in
localization. DynoLoc’s design involves three key components:

Topology estimation for ranging: DynoLoc intelligently uses its available
ranging resources on critical links that will contribute the most to
topology’s localization accuracy. The critical nature of a link varies spatio-
temporally and is determined by DynoLoc by fusing three dimensions of
information, namely (a) mobility of nodes in the link (that affect the
staleness of its range measurement), (b) certainty of range estimates being
LOS vs. NLOS (inferred from channel impulse response measurements), and (c)
link’s contribution to the topology’s geometry in creating a robust and
maximally rigid (where relative location of nodes are fixed in the topology)
sub-graph that in turn leads to increased localization accuracy.

Aggregated and concurrent ranging: DynoLoc redesigns the traditional pair-wise
and sequential ranging protocol for reduced measurement latency. It aggregates
(and amortizes), the process of ranging (and associated overhead) for a node
with all its neighbors into a single compacted process, while links that are
spatially separated, can enable such ranging concurrently.

Robust relative localization: Instead of applying EDM-completion techniques on
the entire topology that is incomplete, DynoLoc leverages the graph rigidity
construct of k-core sub-graphs to identify maximal rigid sub-graphs of the
topology, and applies EDM on these separately and combines them to provide a
robust, accurate solution. Given the relative localization of nodes in the
rigid sub-graphs, DynoLoc devises additional mechanisms to localize the
remaining nodes in the topology by leveraging geometric constraints driven by
range, physical connectivity as well as heading data from IMUs.

Finally, with little additional meta information, contributed by IMU heading
data or floor plans, DynoLoc efficiently transforms the relative localization
solution into absolute coordinate system without affecting the solution’s
refresh rate.

$\blacksquare$ DynoLoc’s potential. We have built and deployed DynoLoc in
real-world dynamic environments, including in a live firefighters’ drill (Fig.
3), where its accuracy and value in saving lives was well-appreciated (Sec.
4.2.1). Designed with mobility (and hence latency) in mind, DynoLoc delivers
superior performance in infra-free tracking across multiple dimensions of node
density, mobility, application refresh rate, etc. In particular, evaluation in
two real-world use-cases, reveal that (i) first-responder scenarios: DynoLoc
is able to track a network of 12 (20) responders, operating with speeds upto 1
m/s (2 m/s) with a median localization error of under 1 m (2 m), while
delivering a refresh rate of 1 Hz; existing solutions suffer in accuracy (6m+
error) even for a node mobility of 1 m/s; (ii) AR gaming: DynoLoc tracks
translational motion of users accurately across a free-flowing indoor space of
20m$\times{}$20m with latencies of under 64 msec to enable a highly-
responsive, dynamic 3-player AR game even in sub-optimal lighting conditions -
a scenario that is challenging for VIO, especially in the multi-player
context. In future, we aim to fuse VIO with DynoLoc to deliver on VIO’s
performance even in realistic everyday scenarios. A short video demonstrating
DynoLoc’s capabilities is available at the following link:
http://sites.google.com/view/dynoloc

Our contributions in this work are two fold.

  * $\bullet$

We introduce and address the problem of latency-bounded, infrastructure-free
localization that is critical for tracking in several dynamic indoor
applications.

  * $\bullet$

We build and demonstrate the viability of such a system called DynoLoc, in two
real world use-cases targeting first responders (a real firefighters’ drill
and active shooter tracking) and multi-player AR/VR gaming.

##  2 Motivation & Challenges

We consider the problem of tracking mobile entities (nodes) in dynamic indoor
environments, namely those that are un-calibrated, lack externally deployed
localization infrastructure, and characterized by node mobility. This features
a pressing need in first responder situations (as evident from NIST programs
[11]), with the potential to enable anchor-less user tracking in multi-player
AR/VR gaming applications in the future.

Figure 4: Localization accuracy is shown as a function of dependence on
deployed infrastructure (left) and dynamics of the environment (right)

###  2.1 Background on Related Works

The rich literature in the area of active (locating and identifying) indoor
localization can be broadly categorized as (i) Anchor-based, and (ii)
Infrastructure-free approaches, as shown in Fig. 4.

Anchor-based: These approaches often surpass their infra-free counterparts in
accuracy at the expense of a-priori deployed infrastructure for localization –
a tradeoff captured in Fig. 4. Here, beacons are deployed at known locations
and serve as reference points or anchors. A node estimates its distances (also
called ranges) from three such anchors, which are then combined with the
anchors’ locations to estimate its own location by a technique typically known
as multilateration. Given a technology to perform accurate ranging,
localization can be seen as a trivial extension. Hence, most of the prior
works in this space has focused on the accurate estimation of such ranges,
particularly using WiFi access points as beacons, while some have also
leveraged ultrasonic beacons [6]. The WiFi-based works leverage signal
information across multiple dimensions – frequency ( [12], [3]), antenna
arrays ( [2], [13]), or both ( [4]), to improve accuracy in the face of
limited WiFi bandwidth and multipath. Some of them [14] adopt a finger-
printing approach (using RSSI, CSI, etc.) to calibrate the environment
a-priori that is later used for for real-time location inference. Optical
tracking systems (e.g. HTC Vive [7]) that are popular in the AR/VR industry,
employ multiple IR beacons (LEDs/ cameras) to provide mm-level tracking
accuracy, but are restricted to line-of-sight and expensive to deploy.

The fundamental dependence on pre-deployed anchors (mostly static, but
sometimes mobile – e.g. outdoor drones [15]), prevents such approaches from
catering to our target environment.

Infrastructure-free: Works in this category are more amenable to our target
environment, but exhibit a different tradeoff between accuracy and robustness,
as captured in Fig. 4. Inertial sensor-based solutions [8, 9, 16, 17] are
inherently local to a node (no ranging needed), and hence popular. However,
with only dead-reckoning of nodes, errors accumulate significantly over time
[18], especially in case of pedestrian mobility. State-of-the-art AR/VR
solutions (e.g. ARCore [19]) leverage visual inertial odometry (VIO) that
combines both cameras and IMUs to provide accurate cm-level tracking [10] in
favorable conditions. However, they often require anchors [20] and their
performance suffers significantly in poorly illuminated and/or poorly textured
environments [21], in presence of motion-blur [22] and/or multiple moving
objects in the video-frames [23], as shown in Fig. 2. Such practical
conditions result in various errors relating to drift, loop-closure, scale
ambiguity etc. (for SLAM-based approaches) [24], and errors related to
projection, parameterization etc. (for optical-flow based approaches) [25].
[26] uses CSI of WiFi to determine LOS. [27] uses P2P UWB ranging for
localization of mobile node considering dilution of precision. [28] uses
Gaussian Mixture and MDS to solve indoor localization using UWB ranges.
Hence, dynamic environments, particularly those in first responder scenarios
can significantly benefit from an alternate RF modality that can deliver good
accuracies (sub-1-2m), and which is robust to the lacking of such favorable
conditions. In AR/VR gaming applications, such a modality can be complementary
in helping to eliminate the accumulating errors faced by VIO, with periodic
absolute location fixes.

###  2.2 Role of RF in Infra-free Localization:

The recent popularity of ultra wide-band (UWB [29]) technology, and its
ability to span a wide 500-1000 MHz bandwidth with superior multipath
suppression (owing to its impulse transmissions), has made it a popular
candidate for sub-m localization [30, 31, 32, 33], albeit with the help of
infrastructure anchors. Existing works in this space are largely concerned
with scalable ranging (SurePoint [34], SnapLoc [35]) and tracking of
individual mobile nodes (e.g., indoor drone, PolyPoint [36]). However, in the
absence of reference anchors, UWB’s two-way-ranging (TWR [37]) mechanism can
enable the nodes to only range with each other. Hence, localization in dynamic
environments presents a different challenge, which, beyond the estimation of
accurate ranges, needs to translate the ranges to an accurate localization
solution. Indeed, the key focus of infra-free RF localization comes down to
bridging this gap between estimated ranges and node localization that arises
in the absence of anchors.

Primer on Relative Localization: In contrast to anchor-based approaches, where
nodes are absolutely localized in the coordinate space defined by the anchors,
localization in infra-free set-up is a two-step process. First, the nodes are
relatively localized among themselves, following which some meta information
(e.g. orientation of the nodes, or floorplans) is leveraged to transform such
relative localization to the absolute coordinate space. Relative localization
refers to the geometry or a topology among the nodes, where the pairwise
distance between nodes as well as their relative orientation are preserved. In
determining such a relative localization, the construct of a rigid body comes
handy.

Figure 5: (a) Clique (rigid) (b) non-clique (rigid) (c) 2 choices for node 5
(not rigid)

Let $G=(V,E,d)$ be a weighted graph, where $d$ is the set of range
measurements (weights) for the —E— edges defined on the —V— nodes. A
realization is a function $x:V\rightarrow{}\mathbb{R}^{2}$ that maps the set
of vertices $V$ to the 2D Euclidean space such that each range value is
preserved i.e $\forall(u,v)\in E,\;||x(u)-x(v)||=d(u,v)$ where $||.||$ is the
Euclidean norm. The graph $G=(V,E,d)$ is “rigid” if there is only one
realization, discounting any translation, rotation and flip. Thus, a rigid
topology gives us a unique relative localization solution. As shown in the
Figure 5, the complete graph or clique in (a) is rigid because given the 10
ranges between all pairs of nodes, this graph is the only realization,
although it can be rotated, translated and/or flipped. Similarly, given the 9
ranges, the graph in (b) is rigid. However, (c) is not rigid, since given the
8 ranges, there are two choices to fix node 5 relative to the edge (2,3)
resulting in two potential realizations.

(a)

(b)

Figure 6: Localization error for (a) various refresh rates (b) various no. of
nodes

(a)

(b)

Figure 7: Localization error after using various low-rank matrix completion
techniques for(a) various topologies and (b) various set of edges from same
topology

(a)

(b)

Figure 8: Localization error for (a) various levels of link noises (b) various
fractions of mobile nodes

If all possible ranges between nodes are available, computing the relative
localization is straight-forward in a static environment. The edge weights of
the graph are maintained in the form of an adjacency matrix, EDM (a.k.a.
Euclidean Distance Matrix), where each entry represents a measured range
between two nodes. Then, an approach called Multidimensional Scaling (MDS) is
applied on the EDM matrix, whereby an EVD (Eigen Value Decomposition) results
in an embedding of the nodes (i..e. relative localization) in a 2D Cartesian
space. While such a framework of relative localization is appropriate for our
dynamic environments, the theoretical approaches in this space are built on
several assumptions111e.g. static nodes, accurate range estimates of all node
pairs at no cost, etc. that do not hold in practice.

###  2.3 Challenges in a Dynamic Environment

To accurately localize/track mobile nodes, the localization solution needs to
be computed and refreshed at a granularity finer than node mobility. For
instance, a 1 Hz refresh rate is appropriate to track nodes with speeds of
1-1.5 m/s, targeting a 1-2 m error. However, the refresh rate automatically
enforces a latency-bound (cost) for the whole process of relative
localization, which involves both the range estimation/collection as well as
the solution computation. This results in a latency-bounded version of the
infra-free localization problem (referred to as LB-IFL) that has not been
addressed before. To understand the impact of such a latency cost on existing
approaches in practice, we conduct an experimental study (details of testbed
described in Section 4) comparing a genie/anchor-aided localization solution
(with all possible range estimates available instantaneously, TDOA) with the
one described above, i.e., MDS applied on EDM constructed with a random set of
edges (called Base), whose ranges are measured within the latency budget
offered by the refresh rate.

Latency vs. accuracy: Every ranging operation takes a finite amount of time to
complete. For instance, with a popular UWB hardware [29], it takes
approximately 40 ms to complete a single range estimate, i.e. a two-way-
ranging (TWR) operation. This inherently limits the number of ranges that can
be estimated/collected per second to 25 to support a localization update rate
of 1 Hz. The results in Fig. 6a and 6b show that when budget restrictions
increase for a given topology size or vice versa, the accuracy degrades by
several folds, clearly exposing a trade-off between latency (cost) and
accuracy. This can be attributed to the lack of intelligent topology
estimation (edge selection) and robust relative localization schemes that are
needed to work with limited latency budgets and hence incomplete range
estimates respectively – aspects that have not been addressed thus far. We now
further dissect the specific factors contributing to this performance
degradation.

Incomplete range estimates: In practice, the physical communication range
between nodes will limit the topology from being complete. This is further
compounded by the limited number of edges (ranges) that can be estimated due
to the latency budget. Since an incomplete EDM (i.e. estimated topology is not
a clique) can lead to localization inaccuracies, matrix completion methods
(e.g., SDR [38], OptSpace [39]) are used to complete the EDM before the nodes
can be relatively localized. However, the latter are not designed keeping in
mind the geometrical implications relevant to a localization problem. This can
lead to large localization errors as shown in Fig. 7a, thereby advocating the
need for relative localization schemes that are robust to incomplete range
estimates.

Impact of geometry: The interesting result in Fig. 7b further indicates that
the specific set of edges selected, albeit incomplete, has a large impact on
the localization solution as well. This indicates that the geometry of the
topology (particularly its rigidity) associated with the edges measured, has a
direct impact on the solution and must be factored into the edge and hence
topology selection process.

Inaccurate range estimates: Inaccurate estimates of even a small set of ranges
can lead to degraded accuracy for the entire topology. Here, two key
environmental factors, namely LOS blockages (due to body, concrete, etc.), and
node mobility, can significantly affect the accuracy of the range estimates.
Given the limited budget for range estimation, it is clear that when the edges
are picked randomly without taking into account their channel or mobility
characteristics, the performance degrades quite rapidly even with a small set
of affected edges, as seen in Fig. 8a. Thus, characterizing the nature of the
edges with respect to their channel and mobility is essential for improved
localization accuracy.

###  2.4 Design Requirements

From the above discussions, it is clear that the combination of
“infrastructure-free” and “node mobility” in practical, dynamic indoor
environments, makes the latency-bounded version of the localization problem,
highly challenging. In addressing these challenges, two key design
requirements emerge for DynoLoc, (a) Support a reasonable number of nodes in a
practical deployment setting ($\approx$ few 10s), many of them being mobile
($\leq$ 2 m/s), and (b) Offer a location update rate ($\geq$1 Hz), tolerable
to the underlying location based service that eventually consumes such
information.

##  3 DynoLoc: Design

At a high level, DynoLoc models the topology among nodes collectively as a
graph of rigid components, and tracks it accurately over time as the topology
evolves subject to node mobility and channel conditions. Within a limited time
(determined by the application’s refresh rate), DynoLoc’s task is to gather as
much UWB ranging information (on links) from the network as possible at a
master222One of the nodes doubles up as a master node. node (using WiFi for
control), so as to accurately estimate the underlying topology (See Fig. 3).

###  3.1 DynoLoc in a Nutshell

DynoLoc operates in epochs (rounds), where the locations of all nodes are
estimated at the end of each epoch, the duration of which is determined by the
application’s refresh rate (e.g., 0.5-2 Hz). In every epoch, the following
sequence of operations is executed.

(i) Topology estimation for ranging (Sec 3.2) Given the underlining physical
topology (based on connectivity), DynoLoc prioritizes edges which contribute
to the resulting topology being maximally rigid, while avoiding those, whose
ranges could be corrupted by multi-path; and it is adaptive in that it
prioritizes edges associated with nodes that have been mobile in the recent
past thereby leading to a good localization accuracy.

(ii) Concurrent ranging (Sec 3.3) The selected edges are then ranged using a
concurrent ranging protocol that amortizes the overhead of ranging from a node
across its neighbors, while enabling concurrent ranging in non-interfering
neighborhoods, to minimize the overall latency.

(iii) Robust relative localization (Sec 3.4) After the estimated topology has
been ranged, DynoLoc’s localization algorithm intelligently identifies and
applies EDM only on sub-graphs of the topology that are rigid and combine them
effectively, to deliver both a robust and accurate relative localization.

(iv) Absolute localization (Sec 3.5) DynoLoc finally transforms the relative
localization solution into an absolute one with little additional meta
information (contributed by floor plans or a single reference node), while
still delivering the desired refresh rate for the solution.

###  3.2 Estimation of Ranging Topology

DynoLoc’s innovation lies in leveraging the graph theoretic construct of
geometric rigidity to help identify the set of edges that would collectively
contribute to the accurate localization of the topology as a whole while also
adapting itself to track the topology as it evolves with node mobility and
channel conditions. DynoLoc accomplishes this by first characterizing the
links in the physical connectivity topology, followed by leveraging such a
characterization for adaptive link selection.

A. Characterizing the Connectivity Topology: Every link is characterized based
on the mobility of its nodes, the multipath nature of its wireless channel, as
well as its contribution to the topology’s rigidity.

Figure 9: First Path Detection in UWB receiver

LOS vs. NLOS: Every node maintains a list of its neighbors, identified by
overhearing their transmissions, whose channel impulse response (CIR) is also
collected. A node $i$ can thus directly range with any of its neighbors $j$,
whose link quality ($L_{ij}$) is estimated from its corresponding CIR.
$L_{ij}$ captures the potential accuracy of ranging on the link based on the
certainty of it being a LOS (direct) or NLOS (indirect) path. This NLOS
probability is computed by as
$p_{NLOS}=(f_{1}\times{}f_{2}\times{}f_{3}\times{}f_{4})$, where $f_{1}=$ avg.
peak count before the detected first path (FP) in the preceding window (See
Figure 9), $f_{2}=$ ratio of std-noise to FP amplitude, $f_{3}=$ ratio of peak
to FP amplitude and $f_{4}=$ ratio of total received power to FP power. The
link quality is the inverse of this probability. Initially, during the
bootstrapping phase, every node sequentially broadcasts a beacon packet that
is heard by its neighbors. Once the system reaches a steady state, the
neighborhood list is implicitly maintained by all nodes without the need for
additional ranging. This helps realize a physical connectivity graph across
the nodes, where every edge is a potential candidate for range estimation, and
is weighted by its quality (i.e. certainty for delivering accurate ranges).

Mobility: In addition, every node $i$ also maintains a mobility metric $M_{i}$
that capture its location uncertainty since its last localization. This metric
increases as a function of the time-since-localization (TsL) and is computed
using the node’s acceleration, $a_{i}$ (obtained from its IMU). In particular,
for every IMU read (indexed by $k$), $M_{i}(k)\leftarrow
M_{i}(k-1)+v_{i}(k)\cdot\Delta t$, where node velocity $v_{i}(k)\leftarrow
v_{i}(k-1)+a_{i}\cdot\Delta t$, and $\Delta t$ is the elapsed time since the
last IMU read. $M_{i}$ and $v_{i}$ are reset to zero, whenever the node is
localized. When $a_{i}$ is zero (static nodes), we assign an exponential
function to $M$ as follows: $M_{i}\leftarrow(e^{TsL}-1)$. This allows the node
to be prioritized for ranging, even if it is static, but sufficient time has
elapsed since its last localization.

Geometric Rigidity: Recall that a rigid graph admits a unique relative
localization solution. Since the connectivity topology of nodes might not be a
rigid graph in practice, DynoLoc aims to select edges from this underlying
connectivity that ensures maximal rigidity to the resulting node topology. It
does so by identifying maximal rigid sub-graphs from the physical connectivity
graph, by leveraging the construct of $k$-core sub-graphs that are used to
ensure graph rigidity [40]. In a $k$-core sub-graph, every vertex has a degree
of at least $k$. It is known that a $k$-core sub-graph is rigid in $k-1$
dimensional space [41]. Hence, for rigidity in 2D, we seek to obtain 3-core
sub-graphs333This allows DynoLoc to also be extended for 3D localization,
where 4-core sub-graphs will be leveraged instead.. Note that a 2-core sub-
graph will not be rigid in 2D and will admit multiple localization solutions.

DynoLoc identifies the maximal 3-core sub-graphs by starting with the
connectivity graph and partitioning it into $k$-core subgraphs for k = 1,2 and
3 sequentially. It starts with identifying 1-core nodes (one by one) that have
a degree of 1 and removes them and their incident edges iteratively till no
more 1-core nodes can be found. Then, it repeats the process for 2-core nodes
with degree 2. After the removal of 1-core and 2-core nodes, we are left with
maximal 3-core sub-graphs (as shown in the example in Fig. 10) that are rigid.

Figure 10: Example of k-core Decomposition

B. Estimating the Ranging Topology: We now describe DynoLoc’s algorithm for
edge and hence topology selection that will be used for ranging. At a high
level, DynoLoc aims to devote its ranging resources to links, whose ranges are
outdated (due to mobility), followed by those that contribute the most to the
topology’s rigidity, while also avoiding those with potentially inaccurate
ranges (due to NLOS). Specifically, at every iteration, DynoLoc picks the node
(say $i$) with the highest mobility $M$ (location uncertainty) metric. If $i$
is part of the 3-core, and has more than three edges, then three of its edges
with the highest $L$ metric (range accuracy) are selected. Otherwise, its
incident edges ($\leq$ 3) are directly selected. When multiple nodes have the
same $M$ metric, the node selection is done based on the $k$-core metric, with
nodes belonging to a higher core (ties broken with higher node degree)
prioritized over those belonging to a lower core. The process repeats until
the ranging budget is exhausted by the edges selected for ranging. Initially,
when the system is bootstrapped and no information on node mobility is
available, all nodes are assumed to have outdated $M$ metric and edge
selection is done primarily based on their contribution to rigidity and their
LOS nature. The complete DynoLoc method is presented in Algorithm 1.

Algorithm 1 DynoLoc Algorithm

1:Make every node send hello frame

2:Collect and initialize link quality metric $L$

3:Run core-decomposition based on $L$

4:Build initial rigid graph $G_{R}$

5:Initialize mobilty metric $M$

6:while True do

7: Choose node $i$ with the highest metric $M(i)$

8: Remove $i$ (with its edges) from $G_{R}$ or $V^{{}^{\prime}}$

9: if $i$ has $\geq$ 3 edges with $G_{R}$ then

10: Select 3 edges for $i$ with max. $L$

11: Add $i$ back to $G_{R}$ with selected edges

12: else

13: Put $i$ in the excluded node list $V^{{}^{\prime}}$

14: Select $i$’s edge(s)

15: end if

16: Range for the above-selected edges [§3.3]

17: Set $M(i)\leftarrow 0$

18: Update $M$ & $L$ metrics from collected data

19: Compute core-decomposition

20: Remove nodes which are not in 3-core, from $G_{R}$

21: if Refresh interval elapsed then

22: Complete EDM for $G_{R}$ [§3.4.A]

23: Determine relative locations [§3.4.B]

24: Determine & output absolute locations [§3.5]

25: end if

26:end while

###  3.3 Aggregated and Concurrent Ranging

DynoLoc optimizes its ranging protocol using two key mechanisms as follows.

Aggregated Ranging: DynoLoc employs two-way ranging (TWR) mechanism [37]
further optimized for tight TDMA control. See Appendix A for details.

Concurrent Ranging: We use concurrent ranging to increase ranging budget and
hence support more nodes for a given refresh rate. Discussion about concurrent
ranging is presented in Appendix B.

###  3.4 Robust Relative Localization

DynoLoc employs the latest (epoch) ranges collected from the ranging topology,
along with other ranges from prior epochs that are accurate and not outdated,
to determine the relative localization of nodes. Existing solutions require a
complete $m\times m$ EDM matrix of ranges for a $m$ node topology to determine
the relative localization (embedding) of nodes. Matrix completion techniques
(e.g. OptSpace [38], SDR [39]) are used to complete the missing EDM entries in
practice, but deliver poor accuracies, owing to the lack of (i) rigidity over
the entire topology, and (ii) incorporation of geometric structure. DynoLoc
innovates in both these aspects to deliver a robust relative localization
solution as follows.

A. Estimating Missing Ranges: DynoLoc performs EDM completion only on the
rigid sub-graphs (3-core sub-graphs) of the topology, individually. The
rigidity of the sub-graph (say, with $n$ nodes) enables a more accurate EDM
completion of $n\times n$. Further, it leverages the geometric topology of the
nodes to complete the missing EDM entries as follows (Algorithm 2). The
algorithm starts by initializing the EDM with the measured ranges and then
fills in the missing ranges through sequential multilateration. In the
process, it also computes the relative locations of all the nodes. It
maintains two copies of the EDM, one based on the inter-node ranges obtained
solely from the computed relative node locations, and the other including the
actual measured ranges, where available. It then iteratively perturbs or
updates the relative location of each node to minimize the gap between these
two EDMs, and further updates the EDM from the subsequent node locations.
Thus, the error in the estimation of missing ranges is minimized. See Appendix
C for EDM completion algorithm.

B. Relative Localization: Having identified the rigid and non-rigid components
of the topology, DynoLoc first solves for the relative localization of nodes
in the rigid sub-graphs individually, followed by those in the non-rigid
components.
Rigid Component: Having completed the EDM for the rigid component, DynoLoc
employs the Multi-dimensional Scaling (MDS) solver [42] to find the node
embedding (relative localization) solution. Note that while sequential
multilateration is appropriate for EDM completion, it is not employed for the
eventual localization itself, as the location error tends to increase rapidly
for the nodes being mulitlaterated later. In contrast, with MDS solvers, the
order of the multilateration does not matter – with the multilateration error
being part of the objective function, it is equally distributed across all
steps of the multilateration process. The MDS problem can be defined as: Given
a squared EDM $\mathbf{D^{2}}$, find the corresponding relative location
matrix $\mathbf{X}$. In matrix notation, this is equivalent to solving for
$\mathbf{B}=\mathbf{XX^{T}}$ where $\mathbf{X^{T}}$ is the transpose of matrix
$\mathbf{X}$. DynoLoc employs the Classical MDS (CMDS) solver [42, 41], which
works as follows:

  * $\bullet$

Given square-distance matrix $\mathbf{D^{2}}$, compute Gram matrix
$\mathbf{B}$ of $\mathbf{X}$ as $\mathbf{B}=-\frac{1}{2}\mathbf{JD^{2}J}$,
where $\mathbf{J}=\mathbf{I}-\frac{1}{n}\mathbf{1\,1^{T}}$

  * $\bullet$

Find the Eigenvalue decomposition of
$\mathbf{B}=\mathbf{Q}\,\Lambda\,\mathbf{Q^{T}}$,

  * $\bullet$

Finally, compute $\mathbf{X}=\mathbf{Q}\sqrt{\Lambda}$ for Eigenvector matrix
$\mathbf{Q}$ and diagonal Eigenvalue matrix $\Lambda$.

Due to the “centering” assumption, each column of solution $\mathbf{X}$ sums
to zero i.e, the origin of $\mathbf{X}$ coincides with the centroid of the $n$
locations. Note that CMDS minimizes the loss function (also called strain)
$L(\mathbf{X})=||\mathbf{XX^{T}}-\mathbf{B}||=||\mathbf{XX^{T}}-\frac{1}{2}\mathbf{JD^{2}J}||$.
In doing so, it updates the range entries only for the missing edges but
leaves the edges with measured ranges untouched. The CMDS can result in local
minima, which are more likely to occur, when the dimension is low (2 as in our
case) [42, 41]. Hence, DynoLoc cross-validates the locations using heading
data retrieved from the IMUs of nodes and also employs a smoothing filter on
the successive node locations over a small window.

Non-Rigid Component: Having solved for the relative locations of the 3-core
nodes, DynoLoc now considers the nodes in the non-rigid components, namely the
2-core and 1-core nodes. By definition, every 2-core node has two edges to the
rigid component(s). It employs these two ranges to find the relative location
of the 2-core node. However, with just two ranges, there are two possible
solutions. DynoLoc eliminates one of these solutions easily by leveraging the
link quality of edges in the neighborhood of the solution. If the solution has
a neighboring rigid node (other than the rigid nodes of its two edges), this
would contradict its 2-core status (as another edge to a rigid component
exists) and the solution can hence be eliminated. Once the 2-core nodes are
also solved, the remaining 1-core nodes are determined using the angle that
the corresponding edge (to the rigid component) makes with the North-South
axis of the earth using the IMU data. This computation is done as part of the
absolute localization procedure discussed in §3.5.
Continuous Link Info. Update: DynoLoc nodes continuously overhear all wireless
frames and decode the sources and update the link quality metrics as per Line
18 of Algorithm 1. If no frame is received or overheard within a threshold
period (30 seconds for our operation), then the link metric value for the
source node is set to zero, which means reachability of the node. The
controller forces a node which has not sent any frame within the threshold
period, to range with neighbors, thus facilitating continuous update of
physical connectivity.

###  3.5 Absolute Localization

DynoLoc needs to transform the localization solution from a relative
coordinate system to a target absolute coordinate system. This is achieved by
translating, rotating, and flipping the rigid graph derived in the previous
step with the help of IMUs (on the nodes) or floormap information [43].
Details is presented in Appendix D.

##  4 Implementation and Evaluation

###  4.1 System Implementation and Prototype

DynoLoc system consists of a set of UWB tags, interfaced with an embedded
computer (e.g., a smartphone or a Raspberry-Pi) and a central controller that
orchestrates range measurements and runs the localization algorithms. Both,
the controller and the embedded computer are connected to a local WiFi network
for exchanging control information and application data (e.g., sensor
readings, video feeds).

Figure 11: Prototype of DynoLoc node

(a)

(b)

(c)

(d)

Figure 12: Comparison of localization error for various method of
localization, default values: no. of nodes = 12, velocity = 1m/s, refresh rate
= 1Hz, fraction of mobile nodes =50%

$\blacksquare$ DynoLoc UWB Tag: The tag consists of a Decawave DW1000 [29]
ultra-wideband radio (costs $\approx$10$) that houses an extremely precise
picosecond crystal (for TOF calculation), which can achieve a distance
resolution as high as 2.2 mm [44]. We interface the DW1000’s SPI pins (serial
clock, master output, master input and slave select), Vcc and GND pins to a
low power ARM Cortex-M based microcontroller unit STM32 NUCLEO-F042K6 (costs
$\approx$10$), where the latter acts as the SPI master. DynoLoc’s optimized
ranging protocol is implemented in about 4000 lines of C code and runs on the
STM32 microcontroller. Additionally, the STM32 sends and receives specific
ranging instructions or estimated ranges through its serial port from an
external host device. While most commercially available UWB tags cost
somewhere between $100–200, DynoLoc tags show that it is feasible to keep the
cost to under 20$ (10-20% of the COTS tags) without compromising any feature.
Our tags can use the UWB permissible channels spanning from 3–7 GHz (with 500
MHz bandwidth). In most of the experiments, we use 3.5 GHz as the center
frequency for improved range.

$\blacksquare$ Tag Host: An embedded computer (e.g., a smartphone) acts as a
USB host for the DynoLoc Tag. It sends specific ranging instructions to the
tag (e.g., range with 5 specific neighboring nodes) and receives measured
ranges. The tag host also keeps track of the node’s mobility from the inertial
sensors as well as the link quality information as obtained from the tag ($M$
and $L$ metrics). The device driver for our tag is implemented on the Android
platform and runs as a background service intercepting commands from the
controller and passing it on to the tag and vice versa. The tag host also
houses a pressure sensor to identify the vertical elevation, i.e., floor
number which is useful in a multi-storeyed deployment scenario.

$\blacksquare$ Controller: The controller is in charge of the overall topology
estimation, gathering ranges from individual tags and running the localization
engine. Depending on the application (see more in § 5), the controller sends
the information back to the individual nodes, displays them locally in a
dashboard or offload it to a cloud service for remote visualization or
decision making. The controller logic is implemented in about 1000 lines of
Python code.

###  4.2 System Evaluation

DynoLoc is evaluated comprehensively spanning in-the-wild deployments to
controlled experiments in realistic indoor settings (supplemented by
simulations only for larger topologies of over 16 nodes). In the following, we
describe our methodology followed by some key performance results.

####  4.2.1 In-the-wild Deployment

DynoLoc has been deployed and tested in a real firefighter’s drill. A total of
ten firefighters, each carrying a DynoLoc tag individually, enter the test
building (2 floors, each $\approx$50 m$\times$100 m) emulating a severe fire
incident. A pressure-sensor+UWB based mechanism (See Appendix E) for floor
identification at each node locally, was added to DynoLoc for this drill. The
fire chief, stationed outside the building, tracks every move of the personnel
crawling through the dark and smoky passages through DynoLoc’s real-time
dashboard and instructs them accordingly through a walkie-talkie. In one
specific incident, a firefighter who was lost and separated from his
colleagues issued an SOS call. The chief knowing his location from the
breadcrumb feature of DynoLoc app (See Fig. 24(b) in Appendix E) was able to
intervene and immediately assist by redirecting his crew accurately towards
the lost firefighter. We learned (from the fire chief) DynoLoc’s true value in
such challenging scenarios, which are common and often lead to firefighter
fatalities. A snapshot of the drill is shown in Fig. 3.

####  4.2.2 Controlled Experiment

Here, we describe results derived from known path and speed of the mobile
nodes.
Testbed: The testbed consists of eight pre-planned navigable routes (marked
with adhesive tapes on the floor) in an indoor area of about 50 m$\times$40 m.
The collective length of the routes is $\approx$500 meters The routes
encompass various types of indoor areas: open hallways, corridors, meeting
rooms, lab spaces and so on, such that we have a fair representation of
typical indoor settings (both LOS and NLOS). In addition to the DynoLoc tag (+
smartphone host), each volunteer carries another UWB tag operating at a
different frequency (6.5 GHz) for ground truth collection.
Baselines: The ground-truth is collected using a system of densely placed,
synchronized, static anchor nodes (by multilateration using TDOA information),
deployed throughout the building floor, which gives a localization accuracy in
the order of 10–20 cm, thereby serving as a lower bound on performance for
infrastructure-free solutions. Further, the volunteers carrying the DynoLoc
nodes followed paths of known shapes (see Fig.23 in Appendix D). As such, any
deviation from the target shape was considered as the error in TDOA itself,
which is $\leq$10cm. We also consider two heuristics that are subsets of
DynoLoc, namely H-Agnos and H-Dyn. H-Agnos employs DynoLoc’s relative
localization component but adopts a naive edge selection approach (ranges
every pair of possible edges through round-robin) that does not account for
node dynamics and link quality. In contrast, H-Dyn’s edge selection accounts
for node mobility by ranging on edges incident with the most dynamic nodes,
but disregards the geometric rigidity requirement in its relative
localization.  Note that, SnapLoc[35] and TrackIO[15] are two recent works
that uses UWB-range based indoor localization. However, SnapLoc is fixed
anchor-based and only considers a small indoor space with constant LOS,
whereas TrackIO is infrastructure-full (drone-based) yet is outperformed by
DynoLoc for similar node count and mobility.
Overall Localization Performance: Fig. 12 highlights the overall performance
of DynoLoc as a function of various factors, namely number of nodes, fraction
of mobile nodes, their velocity and the targeted location update rate. DynoLoc
scales well for a reasonable number of nodes (Fig. 12a) that is practical in
most real life contexts. Even in challenging scenarios, where all the nodes
are mobile (at 1 m/s), DynoLoc provides an average localization error of under
2 meters for a 1 Hz update rate, while H-Agnos and H-Dyn incur an error of 6–7
meters and 5–6 meters respectively (Fig. 12b). Lack of DynoLoc’s robust
relative localization component (included in H-Agnos and H-Dyn), will only
lead to further degradation. While H-Agnos accounts for underlying graph
rigidity, it is devoid of the notion of node mobility and link-quality and
hence, renders poor accuracy; whereas H-Dyn takes into consideration the node
mobility, but renders poor accuracy due to lack of enforcing rigidity
requirement. Also note that, even for a more demanding location update rate of
2 Hz, DynoLoc maintains a sub-meter localization accuracy (Fig. 12c), even
when half the nodes are mobile. DynoLoc’s ranging algorithm being mobility-
aware, adaptively expends the available time resources in collecting the most
critical ranges. This allows it to deliver under 2m accuracy even when 4 times
the update rate is desired.
Benefits of DynoLoc’s Design: DynoLoc’s design components are benchmarked in
isolation as follows.

Adaptive Ranging:  Fig. 12 clearly shows the significant merits and usefulness
of DynoLoc’s adaptive ranging (edge selection) mechanism (compared to random
selection in Rand). We now explore the merits of its mobility and link quality
metrics as part of its topology estimation.

$\bullet$ Mobility Metric: Fig. 14a demonstrates that performing the edge
selection (purely based on rigidity constraints) without considering mobility
metric ($M$) results in a sub-optimal localization accuracy. Additionally,
Fig. 13a shows the reactive nature of the $M$ metric in tracking node mobility
through its acceleration.

$\bullet$ Link Quality Metric: Similarly, Fig. 14b shows the impact of link
quality metric ($L$) on edge selection. $L$ acts as a classifier for NLOS
versus LOS ranges. Particularly in NLOS scenarios, $L$ plays a critical role
in selecting non-noisy edges, thereby leading to a better localization
accuracy. Fig. 14b indicates that introducing the L metric improves accuracy
by 30 – 40% in two different NLOS scenarios (meeting rooms/office space and
lab spaces denoted by NLOS1 and NLOS2 respectively).

Robust Relative Localization: Fig. 15a shows that DynoLoc’s EDM-completion
approach is able to bound the range estimation (for missing entries) to within
2m in most cases. This can be attributed to its approach of targeting the
rigid sub-graphs individually, while using a sequential multilateration
approach that exploits the node geometry for estimating the missing ranges.
Its rigid sub-graph based relative localization further contributes to a much
improved accuracy over existing approaches as seen in Fig. 15b.

(a)

(b)

Figure 13: (a) Consistency of Mobility Metric (b) Correlation of Link Quality
metric with ranging error

(a)

(b)

Figure 14: Comparision of DynoLoc without Mobility (M) and Link Quality (L)
metrics

Concurrent Ranging: As seen in Fig. 16(b), DynoLoc’s aggregated and concurrent
ranging directly contributes to a larger ranging budget and hence localization
accuracy. DynoLoc’s tag supports two data rates (low, 100 Kbps and high, 6.8
Mbps, Fig. 16(a)). The high data rate results in a lower latency per ranging
(2 ms vs 8 ms for low data rate case). While it restricts the maximum
communication range (about 10 m) and allows for more concurrent ranging, it
also requires a higher node density to ensure a reasonably connected topology.
This is reflected in the results presented in Fig. 16.

Absolute Localization: Conversion of relative to absolute localization incurs
an additional error of 10–20%, as shown in Fig. 17a. As expected, it increases
as the network size grows larger. Fig. 17b shows how the value of heading is
tracked over time as the user moves (walk and sprint). While noisy heading
values lead to higher additional errors, this is still restricted to just
40-60 cm even for a user sprinting at 2 m/s.
End-to-End System Latency: Fig. 18a breaks down DynoLoc’s overall latency
broadly into three categories. In table 18b, we present some battery life
benchmarks for different components of the system.

(a)

(b)

Figure 15: (a) EDM completion Error, (b) Relative localization error

(a)

(b)

Figure 16: (a) Ranging error for different modes of UWB, (b) Loc. accuracy &
node dis-connectivity for concurrent ranging, UWB datarates & node densities

(a)

(b)

Figure 17: (a) Accuracy of absolute Localization, (b) Impact of heading error

(a)

(b)

Figure 18: (a) Breakdown of latency components (b) Power benchmarks for
various system components

##  5 Applications

DynoLoc enables a host of location-based applications that benefit from
minimal setup time, preferably without any infrastructure deployment, realtime
support, and adaptation to an unknown environment. We demonstrate two such use
cases that would benefit from DynoLoc.

###  5.1 Multiplayer AR/VR Gaming

Today’s multiplayer AR/VR gaming systems, do not support features that have
bearing to players’ location in the physical coordinate space. Given the
growing demand for ‘location-based entertainment’ [45], recent solutions make
use of visual SLAM (using VIO) to localize players with respect to their
individual reference frames [46]. However, for a collaborative multiplayer
setting, a global coordinate system is essential. This is accomplished today
using either visual markers or anchors that do not offer a smooth multiplayer
experience, or expensive/extensive installation of IR cameras and laser tags
that do not offer a cost-effective, on-demand deployment (e.g. consumer
homes).

Figure 19:  Top: DynoLoc enables location-based multiplayer gaming. Bottom:
Mobility-aware range scheduling distributes time slots heterogeneously across
nodes, thus improves overall interactivity of the game.

We create a simple Android based multiplayer VR game called DynoSoccer to
demonstrate the value that DynoLoc can bring to such gaming systems.
DynoSoccer transforms ordinary physical spaces, like a living room that is not
particularly well-lit or textured , into a gaming arena, where players can
interact with each other based on their real physical locations. The game
consists of a virtual ball that is bounced around by the players. Each player
needs to adjust their position to be in the proximity of the ball in order to
‘kick’ it. However, this requires the system to be responsive to the players’
and the ball’s movement, otherwise resulting in a ‘missed kick’. We show (Fig.
19) that even for high ball speeds, DynoLoc results in 50% to 90% less ‘missed
kicks’ compared to the H-Agnos baseline, increasing the VR experience
significantly. DynoLoc adaptively schedules the relevant ranges (compared to
round-robin in H-Agnos) in the topology based on the mobility of individual
players. We plan to fuse VIO with DynoLoc to overcome VIO’s challenges in
less-favorable visual environments (Fig. 2), especially in the multi-player
context.

###  5.2 Active Shooter Scenario

Figure 20: DynoLoc enables real time geofencing in an active shooter scenario
helping in safe evacuation.

We demonstrate in Fig. 20 how DynoLoc can create a realtime geofence for safe
evacuation of trapped victims in a chaotic situation like spotting an active
shooter. A person mimicking an active shooter runs in a specified path. Four
volunteers (unaware of the shooter’s path) equipped with DynoLoc tags and body
camera scout the general area (corridors, hallways etc.). If the shooter is
detected in the video frame, we mark the respective location as unsafe and
update the geofence (a polygon connecting the unsafe points). We show in Fig.
20 (right), how localization error can lead to inaccurate geofencing resulting
in ‘exposed areas’ or zones that are potentially dangerous but marked safe.
Even a 2 m median localization error can lead to a few hundred sq. ft. of
exposed area, compared to the DynoLoc’s limited exposure.

##  6 Conclusion

We introduced the problem of latency-bounded infrastructure free localization
that is central to several dynamic indoor applications. Towards addressing the
fundamental tradeoff between latency and localization accuracy that arises in
these problems, we presented the design and practical realization of our
DynoLoc system. Through various design innovations, DynoLoc has demonstrated
its ability to accurately track a large network of highly mobile entities,
without any infrastructure support, in real-world firefighters’ drill, as well
as applications of multi-player AR gaming, and active shooter tracking.

## References

  * [1] L. Keselman, J. I. Woodfill, A. Grunnet-Jepsen, and A. Bhowmik, “Intel(R) RealSense(TM) Stereoscopic Depth Cameras,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_. IEEE Computer Society, 2017, pp. 1267–1276.
  * [2] M. Kotaru, K. Joshi, D. Bharadia, and S. Katti, “SpotFi: Decimeter Level Localization Using WiFi,” _ACM SIGCOMM_ , pp. 269–282, 2015.
  * [3] D. Vasisht, S. Kumar, and D. Katabi, “Decimeter-level Localization with a Single WiFi Access Point,” in _USENIX NSDI_ , 2016, pp. 165–178.
  * [4] Y. Xie, J. Xiong, M. Li, and K. Jamieson, “mD-Track: Leveraging Multi-Dimensionality for Passive Indoor Wi-Fi Tracking,” in _ACM MobiCom_ , 2019, pp. 1–16.
  * [5] J. Xiong and K. Jamieson, “ArrayTrack: A Fine-grained Indoor Location System,” in _USENIX NSDI_ , 2013, pp. 71–84.
  * [6] F. Ijaz, Hee Kwon Yang, A. W. Ahmad, and Chankil Lee, “Indoor positioning: A review of indoor ultrasonic positioning systems,” in _International Conference on Advanced Communications Technology (ICACT)_ , 2013, pp. 1146–1150.
  * [7] T. Taketomi, H. Uchiyama, and S. Ikeda, “The Accuracy and Precisionof Position and Orientation Tracking in the HTC ViveVirtual Reality System forScientific Research,” _SAGE i-Perceptron_ , 2017.
  * [8] C. Bo, X.-Y. Li, T. Jung, X. Mao, Y. Tao, and L. Yao, “Smartloc: Push the limit of the inertial sensor based metropolitan localization using smartphone,” in _Proceedings of the 19th annual international conference on Mobile computing & networking_. ACM, 2013, pp. 195–198.
  * [9] R. Zhang, F. Hoflinger, and L. Reindl, “Inertial sensor based indoor localization and monitoring system for emergency responders,” _IEEE Sensors Journal_ , vol. 13, no. 2, pp. 838–848, 2012.
  * [10] S. A. S. Mohamed, M. Haghbayan, T. Westerlund, J. Heikkonen, H. Tenhunen, and J. Plosila, “A Survey on Odometry for Autonomous Navigation Systems,” _IEEE Access_ , vol. 7, pp. 97 466–97 486, 2019\.
  * [11] U. NIST, “Location-based Services,” https://tinyurl.com/u6ersg5.
  * [12] J. Xiong, K. Sundaresan, and K. Jamieson, “ToneTrack: Leveraging Frequency-Agile Radios for Time-Based Indoor Wireless Localization,” in _ACM MobiCom_ , 2015, pp. 537–549.
  * [13] E. Soltanaghaei, A. Kalyanaraman, and K. Whitehouse, “Multipath Triangulation: Decimeter-level WiFi Localization and Orientation with a Single Unaided Receiver,” in _ACM MobiSys_ , 2018, pp. 376–388.
  * [14] R. Ayyalasomayajula, A. Arun, C. Wu, S. Rajagopalan, S. Ganesaraman, A. Seetharaman, I. K. Jain, and D. Bharadia, “LocAP: Autonomous Millimeter Accurate Mapping of WiFi Infrastructure,” in _17th USENIX Symposium on Networked Systems Design and Implementation_. USENIX Association, 2020, pp. 1115–1129.
  * [15] A. Dhekne, A. Chakraborty, K. Sundaresan, and S. Rangarajan, “TrackIO: tracking first responders inside-out,” in _16th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 19)_, 2019, pp. 751–764.
  * [16] S. Shen, H. Wang, and R. R. Choudhury, “I am a smartwatch and I can track my user’s arm,” in _14th Annual International Conference on Mobile Systems, Applications, and Services (MobiSys)_ , R. K. Balan, A. Misra, S. Agarwal, and C. Mascolo, Eds. ACM, 2016, pp. 85–96.
  * [17] S. Shen, M. Gowda, and R. R. Choudhury, “Closing the gaps in inertial motion tracking,” in _24th Annual International Conference on Mobile Computing and Networking (MobiCom)_ , R. Shorey, R. Murty, Y. J. Chen, and K. Jamieson, Eds. ACM, 2018, pp. 429–444.
  * [18] R. Harle, “A Survey of Indoor Inertial Positioning Systems for Pedestrians,” _IEEE Communications Surveys Tutorials_ , vol. 15, no. 3, pp. 1281–1293, 2013.
  * [19] P. Nowacki and M. Woda, “Capabilities of ARCore and ARKit Platforms for AR/VR Applications,” W. Zamojski, J. Mazurkiewicz, J. Sugier, T. Walkowiak, and J. Kacprzyk, Eds., vol. 987. Springer, 2019, pp. 358–370.
  * [20] N. Rajagopal, J. Miller, K. K. R. Kumar, A. Luong, and A. Rowe, “Improving Augmented Reality Relocalization Using Beacons and Magnetic Field Maps,” in _2019 International Conference on Indoor Positioning and Indoor Navigation (IPIN)_ , 2019, pp. 1–8.
  * [21] P. Nelson, W. Churchill, I. Posner, and P. Newman, “From dusk till dawn: Localisation at night using artificial light sources,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_ , 2015, pp. 5245–5252.
  * [22] M. Milford, E. Vig, W. Scheirer, and D. Cox, “Vision-based Simultaneous Localization and Mapping in Changing Outdoor Environments,” _Journal of Field Robotics_ , vol. 31, no. 5, pp. 780–802, 2014.
  * [23] Z. Fang and Y. Zhang, “Experimental Evaluation of RGB-D Visual Odometry Methods,” _International Journal of Advanced Robotic Systems_ , vol. 12, no. 3, p. 26, 2015.
  * [24] T. Taketomi, H. Uchiyama, and S. Ikeda, “Visual SLAM algorithms: a survey from 2010 to 2016,” _IPSJ Trans. Computer Vision and Applications_ , vol. 9, p. 16, 2017.
  * [25] D. Fortun, P. Bouthemy, and C. Kervrann, “Optical flow modeling and computation: A survey,” _Comput. Vis. Image Underst._ , vol. 134, pp. 1–21, 2015.
  * [26] Z. Zhou, Z. Yang, C. Wu, W. Sun, and Y. Liu, in _IEEE INFOCOM_.
  * [27] A. Dhekne, U. Ravaioli, and R. R. Choudhury, “P2ploc: Peer-to-peer localization of fast-moving entities,” _IEEE Computer_ , 2018.
  * [28] C. Di Franco, A. Prorok, N. Atanasov, B. Kempke, P. Dutta, V. Kumar, and G. J. Pappas, “Calibration-free network localization using non-line-of-sight ultra-wideband measurements,” in _ACM/IEEE IPSN_ , 2017\.
  * [29] DecaWave, “DecaWave,” http://www.decawave.com/.
  * [30] S. Spieker and C. Rohrig, “Localization of pallets in warehouses using Wireless Sensor Networks,” in _2008 16th Mediterranean Conference on Control and Automation_ , June 2008, pp. 1833–1838.
  * [31] J.-A. Fernandez-Madrigal, E. Cruz-Martin, J. Gonzalez, C. Galindo, and J.-L. Blanco, “Application of UWB and GPS technologies for vehicle localization in combined indoor-outdoor environments.” in _ISSPA_ , 2007, pp. 1–4.
  * [32] M. Gowda, A. Dhekne, S. Shen, R. R. Choudhury, L. Yang, S. Golwalkar, and A. Essanian, “Bringing IoT to Sports Analytics.” in _NSDI_ , 2017, pp. 499–513.
  * [33] A. Prorok, A. Arfire, A. Bahr, J. R. Farserotu, and A. Martinoli, “Indoor navigation research with the Khepera III mobile robot: An experimental baseline with a case-study on ultra-wideband positioning,” in _2010 International Conference on Indoor Positioning and Indoor Navigation_ , Sept 2010, pp. 1–9.
  * [34] B. Kempke, P. Pannuto, B. Campbell, and P. Dutta, “SurePoint: Exploiting ultra wideband flooding and diversity to provide robust, scalable, high-fidelity indoor localization,” in _Proceedings of the 14th ACM Conference on Embedded Network Sensor Systems CD-ROM_. ACM, 2016, pp. 137–149.
  * [35] B. Gro$\beta$windhager, M. Stocker, M. Rath, C. A. Boano, and K. Römer, “SnapLoc: an ultra-fast UWB-based indoor localization system for an unlimited number of tags,” in _2019 18th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)_. IEEE, 2019, pp. 61–72.
  * [36] B. Kempke, P. Pannuto, B. Campbell, J. Adkins, and P. Dutta, “PolyPoint: High-precision indoor localization with UWB,” in _Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems_. ACM, 2015, pp. 483–484.
  * [37] Z. Sahinoglu and S. Gezici, “Ranging in the IEEE 802.15.4a standard,” in _2006 IEEE Annual Wireless and Microwave Technology Conference_. IEEE, 2006, pp. 1–5.
  * [38] R. H. Keshavan, A. Montanari, and S. Oh, “Matrix completion from noisy entries,” _Journal of Machine Learning Research_ , vol. 11, no. Jul, pp. 2057–2078, 2010.
  * [39] A. Y. Alfakih, A. Khandani, and H. Wolkowicz, “Solving Euclidean distance matrix completion problems via semidefinite programming,” _Computational optimization and applications_ , vol. 12, no. 1-3, pp. 13–30, 1999.
  * [40] T. Eren, O. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. Anderson, and P. N. Belhumeur, “Rigidity, computation, and randomization in network localization,” in _IEEE INFOCOM 2004_ , vol. 4. IEEE, 2004, pp. 2673–2684.
  * [41] I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli, “Euclidean distance matrices: essential theory, algorithms, and applications,” _IEEE Signal Processing Magazine_ , vol. 32, no. 6, pp. 12–30, 2015.
  * [42] J. A. Costa, N. Patwari, and A. O. Hero III, “Distributed weighted-multidimensional scaling for node localization in sensor networks,” _ACM Transactions on Sensor Networks (TOSN)_ , vol. 2, no. 1, pp. 39–64, 2006\.
  * [43] Y. Xie, J. Xiong, M. Li, and K. Jamieson, “xD-track: leveraging multi-dimensional information for passive wi-fi tracking,” in _Proceedings of the 3rd Workshop on Hot Topics in Wireless_. ACM, 2016, pp. 39–43.
  * [44] DecaWave, “DW1000 User Manual,” https://decawave.com/content/dw1000-user-manual”.
  * [45] “Malls have a future: location-based entertainment,” https://tinyurl.com/sjz9nbz, 2019.
  * [46] “VR and AR will converge, says Unity XR lead,” https://tinyurl.com/wrw375k, 2019.
  * [47] S. Kumar, S. Gil, D. Katabi, and D. Rus, “Accurate Indoor Localization with Zero Start-up Cost,” in _ACM MobiCom_ , 2014, pp. 483–494.
  * [48] J. Gjengset, J. Xiong, G. McPhillips, and K. Jamieson, “Phaser: Enabling Phased Array Signal Processing on Commodity WiFi Access Points,” in _ACM MobiCom_ , 2014, pp. 153–164.
  * [49] L. Yang, Y. Chen, X.-Y. Li, C. Xiao, M. Li, and Y. Liu, “Tagoram: Real-time Tracking of Mobile RFID Tags to High Precision Using COTS Devices,” in _ACM MobiCom_ , 2014, pp. 237–248.
  * [50] S. Kumar, E. Hamed, D. Katabi, and L. Erran Li, “LTE Radio Analytics Made Easy and Accessible,” _ACM SIGCOMM_ , pp. 211–222, 2014.
  * [51] K. Joshi, S. Hong, and S. Katti, “PinPoint: Localizing Interfering Radios,” in _USENIX NSDI_ , 2013, pp. 241–254.
  * [52] J. Wang and D. Katabi, “Dude, Where’s My Card?: RFID Positioning That Works with Multipath and Non-line of Sight,” in _ACM SIGCOMM_ , 2013, pp. 51–62.
  * [53] A. Rai, K. K. Chintalapudi, V. N. Padmanabhan, and R. Sen, “Zee: Zero-effort Crowdsourcing for Indoor Localization,” in _ACM MobiCom_ , 2012, pp. 293–304.
  * [54] S. Sen, B. Radunovic, R. R. Choudhury, and T. Minka, “You are facing the Mona Lisa: spot localization using PHY layer information,” in _ACM MobiSys_ , 2012, pp. 183–196.
  * [55] K. Chintalapudi, A. Padmanabha Iyer, and V. N. Padmanabhan, “Indoor Localization Without the Pain,” in _ACM MobiCom_ , 2010, pp. 173–184.

##  Appendix A Aggregate Ranging

Figure 21: Two-way ranging (a): Single-sided (SS) (b) Double-sided (DS) (c)
Sequential Double-sided (SEQ-DS) and (d) Optimized Double-sided (OPT-DS) Two
Way Ranging (TWR).

UWB employs a two-way ranging (TWR) mechanism [37] , standardized in IEEE
802.15.4, to estimate the distance between a node pair based on Time of Flight
(TOF). Further, each node pair needs to be separately ranged following a
strict TDMA schedule to avoid interference. This leads to a sequential ranging
for the desired node pairs, consuming significant latency and hindering
scalability. TWR involves exchanging 4 messages for a single range estimation.
See Figure 21. DynoLoc instruments an aggregated version of TWR where an
initiator node sends a broadcast INIT message that also contains IDs of other
nodes that it wants to range with in tandem. The receiving nodes take turns
individually to send a POLL message, which is followed by a broadcast RESPONSE
message from the initiator node. On receiving the RESPONSE message, the nodes
take turn once again to send a FINAL message. Based on the timestamps in the
above messages the initiator node calculates the distance estimates to
individual nodes. Thus, our aggregated optimized TWR (OPT-DS-TWR in Fig. 21)
can range N nodes in (2N+2) time slots compared to the 4N slots for its
sequential counterpart. Given that each transmission slot time can be 10 ms,
this substantial saving in turn allows for twice as many links to be ranged
with the same latency budget.

##  Appendix B Concurrent Ranging

We use concurrent ranging to increase ranging budget and hence support more
nodes for a given refresh rate. While, the UWB protocol employs TDMA to avoid
wireless contention, it does not account for spatial reuse, wherein node pairs
outside each others interference domain can be operated simultaneously.
DynoLoc can easily compute such link concurrency information based on the
neighborhood information for each node as discussed earlier. Hence, a set of
initiator nodes and their corresponding ranging nodes are logically
partitioned into non-interfering groups, with every group containing an
initiator node. Each of the initiator nodes executes the aggregated TWR
process concurrently to range relevant nodes in its group. Such concurrent
ranging, that makes use of spatial reuse, provides a significant increase in
the ranging budget that is beneficial for large node topologies.

DynoLoc employs the above ranging protocol to collect ranges for links in its
ranging topology. Such optimizations also result in a significantly larger
ranging budget (within the application’s refresh rate) for use by its edge
selection component that in turn contributes to a larger localization
accuracy.

##  Appendix C EDM Completion Algorithm

Following the discussion in Section 3.4(A), Algorithm 2 describes the steps of
EDM completion.

Algorithm 2 EDM Completion Algorithm

1:Initialize EDM $D$ with measured ranges

2:Compute node locations using multilateration on the rigid graph

3:Fill in the missing values in $D$ using node locations

4:Initialize EDM $D_{cur}$ using node locations

5:while $\Delta D=|D-D_{cur}|$ is significant do

6: Update location of node i, j for each edge (i, j) in proportion to the
$\Delta D(i,j)$

7: Recompute $D_{cur}$ from node locations

8: Fill in missing values in $D$ from node locations

9:end while

10:Output Complete EDM $D$

##  Appendix D Absolute Localization

DynoLoc needs to transform the localization solution from a relative
coordinate system to a target absolute coordinate system. By translating,
rotating and flipping (if needed) the relative coordinate axis, the absolute
localization solution can be determined in one of two ways.

Figure 22: Finding the slope of an edge

Fixed reference node. One of the static nodes in the topology is made to serve
as the reference node. This could be a node that is placed on an entrance door
(e.g. when responders enter a building).

Translation: The reference node becomes the origin of the absolute coordinate
axis by translating the relative coordinate axis accordingly.

Rotation and Flip: DynoLoc rotates the translated coordinates by an angle
$\theta$, determined as follows. Assume the positive x-axis of the absolute
coordinate system to be aligned with earth’s magnetic North direction. The
heading from the IMU gives the angle its axis makes with this direction
($\theta_{2}$ & $\theta_{3}$ in Figure 22). When the nodes are in motion, the
heading and the direction of motion can be assumed to be the same (contrast
this with sideways motion, which is however, atypical). Using inter-node
distances ($r_{12}$ & $r_{13}$ in Figure 22) and the headings, the slope of an
edge (e.g. $\theta_{23}$ for edge (2,3)) with the north direction and its
slope (say $\theta^{{}^{\prime}}_{23}$) in the relative coordinate are
determined. The required rotation angle is then the difference between these
two slopes ( i.e $\theta=\theta_{23}-\theta^{{}^{\prime}}_{23}$). DynoLoc also
corrects the flip by considering the vertex-ordering of the nodes with respect
to the centroid of the coordinates in a clockwise direction. If the two
orderings (corresponding to the relative and absolute coordinates) do not
match, the relative coordinates are flipped across the x-axis to derive the
final absolute coordinates of the nodes.

Floormap. If the floormap is available, DynoLoc first applies the rotation and
flip correction. Additionally, the trajectory traversed by each node is saved.
To fix the translation, DynoLoc tries to place the joint set of trajectories
within the bounding box of the floormap by finding a location such that none
of the trajectories cross any walls and the distances among various points
across the trajectories are satisfied according to the measured ranges [43].
Note that this approach does not require any fixed static node as a
reference/origin. The floormap and the paths used in the controlled experiment
is illustrated in Fig.23.

Figure 23: Floorplan with the a subset of the loops traversed by the mobile
nodes in the controlled experiments

##  Appendix E In The Wild Experiment

As shown in Fig.24(a), absolute localization is run by DynoLoc in each floor
independently. To determine the the current floor, the reading from the
pressure sensors (also available in the smart-phones) in conjunction with the
available UWB connectivity information are used by DynoLoc. Ideally, nodes
from each floor form a disjoint connected graph. However, due to shared
vertical space among floors i.e. staircase, a node may have links with nodes
on more than one floor. In those cases, floor of the node in question is
determined by pressure sensors. To facilitate uncalibrated operation, during
boot-up of DynoLoc, each node’s initial pressure at the ground level is
recorded and then continuously tracked for changes in shorter period (actual
floor change) and longer period (typically $\geq$20 minutes, which signifies
atmospheric pressure change). This pressure sensor data is piggy-backed with
the range data just like link quality and mobility metric information.

Figure 24:  (a) DynoLoc operation across multiple floors, (b) GUI of DynoLoc
Android app showing node locations on input floormap with breadcrumb and geo-
tagging features.