Communications of the ACM

Research highlights

3D Localization for Subcentimeter-Sized Devices

By Rajalakshmi Nandakumar, Vikram Iyer, Shyamnath Gollakota
Communications of the ACM, March 2021, Vol. 64 No. 3, Pages 117-125
10.1145/3446782
Comments

The vision of tracking small IoT devices runs into the reality of localization technologies—today it is difficult to continuously track objects through walls in homes and warehouses on a coin cell battery. Although Wi-Fi and ultra-wideband radios can provide tracking through walls, they do not last more than a month on small coin and button cell batteries because they consume tens of milliwatts of power. We present the first localization system that consumes microwatts of power at a mobile device and can be localized across multiple rooms in settings such as homes and hospitals. To this end, we introduce a multiband backscatter prototype that operates across 900 MHz, 2.4 GHz, and 5 GHz and can extract the backscatter phase information from signals that are below the noise floor. We build subcentimeter-sized prototypes that consume 93 μW and could last five to ten years on button cell batteries. We achieved ranges of up to 60 m away from the AP and accuracies of 2, 12, 50, and 145 cm at 1, 5, 30, and 60 m, respectively. To demonstrate the potential of our design, we deploy it in two real-world scenarios: five homes in a metropolitan area and the surgery wing of a hospital in patient pre-op and post-op rooms as well as storage facilities.

Back to Top

1. Introduction

Recent years have seen significant advances in wireless localization.^{21, 19} However, existing solutions do not meet the requirements for size-constrained IoT applications. Figure 1 shows battery life of common radio technologies such as BLE, LoRa, ultra-wideband (UWB), and Wi-Fi, each running at a 1% duty cycle with small coin and button cell batteries for equal comparison. The shorter battery life limits the adoption of tracking solutions based on these radio technologies by making them inconvenient for consumer applications and infeasible for large-scale commercial deployments. Requiring large batteries on the other hand prevents scaling down the size of IoT devices. Although RFID tags are attractive from a power and size perspective, they have a limited range and do not work consistently through walls and other barriers. Consumers often deploy devices in rooms throughout homes, and similarly commercial deployments in settings such as hospitals require covering multiple patient rooms with a variety of obstructions and walls. Achieving localization in these scenarios would therefore require readers in every room, which significantly increases deployment cost.

Figure 1. Radio localization battery life. Battery life estimates for different technologies operating at 3 V from coin and button cell batteries running at 1% duty cycle.

This paper presents μLocate, the first wireless localization system that consumes microwatts of power at the mobile IoT devices and can be localized through walls in settings such as homes and hospitals. Our design can achieve 3D localization capabilities while supporting IoT devices that can be scaled to subcentimeter form factor. To achieve this, we design a backscatter-based solution that satisfies all of the above requirements. Specifically, we make the following hardware and systems contributions:

• We design and build a subcentimeter-sized IoT platform that supports low-power localization capabilities. Our platform integrates a low-power microcontroller and RF switch for backscatter rather than an active radio, as well as all required off-chip passive components and antennas. We custom fabricate flexible circuits using laser micromachining techniques and use an off-the-shelf microcontroller available in an ultraminiature 2 mm × 1.5 mm package to achieve the small form factor.
• We achieve low-power long-range backscatter through walls by building on recent work on LoRa Backscatter¹⁷; however, this prior work requires implementing complex computation to perform chirp spread spectrum (CSS) coding on an FPGA platform, which consumes around 5–10 mW using off-the-shelf components. We present a novel backscatter architecture that enables CSS backscatter using off-the-shelf microcontrollers at significantly lower power. Specifically, because these microcontrollers lack the capability to easily implement the complex CSS coding, we instead delegate this coding to the access point, which transmits the CSS signal. By doing this, our low-power microcontroller simply needs to run an oscillator to frequency shift the CSS signal and encode data using ON-OFF keying in reflections.
• Because the localization accuracy is directly proportional to the signal bandwidth, we design and build a novel multiband backscatter hardware system that can concurrently operate across the ISM bands at 900 MHz, 2.4 GHz, and 5 GHz. Specifically, the access point (AP) transmits signals across these frequencies, which are backscattered by our device. We combine the received signals across all of these frequencies to disambiguate between the multipath reflections and extract the direct line-of-sight path.

To summarize, our system works as follows: the AP, which is placed at a known location, transmits a 500 kHz chirp spread spectrum signal. The IoT device uses a low-power microcontroller to shift this signal by 1–2 MHz and backscatter it back to the AP. The AP then extracts the phase information from the weak backscattered signals that are below the noise floor. It repeats this process concurrently across the 900 MHz, 2.4 GHz, and 5 GHz bands and combines the phase to disambiguate the multipath in the environment.

Implementing this system introduces the following three algorithmic challenges: First, in contrast to direct radio signals that attenuate as d², backscatter signals attenuate as d⁴. As a result, we need a way to extract the phase from back-scattered signals, which are below the noise floor at long distances. Second, our IoT devices use small, low-power microcontrollers to shift the chirp spread spectrum signal from the AP. This introduces frequency and sampling offsets in the weak backscattered signals that have to be corrected to accurately estimate phase. Third, querying all the 500 kHz bands sequentially across all the ISM bands requires a total of 572 frequencies, which takes more than four seconds, introducing a significant delay overhead. Concurrently querying all these 572 frequencies requires the AP to proportionally reduce the power at each of the frequencies to be compliant with FCC regulations; this in turn would significantly reduce the range of our system.

In the rest of the paper, we address the above challenges and build multiple prototypes of our design as shown in Figure 2. We build our prototypes using commercial off-the-shelf components such as switches, microcontrollers, and chip antennas. Our first prototype uses the 2.0 × 1.6 mm Kinetis KL03 microcontroller with a 2.4 GHz and 900 MHz dual band chip antenna along with a 5 GHz chip antenna. We miniaturize our second prototype using a laser micromachining method that produces flexible circuits. We use the Kinetis microcontroller with only the 5 GHz chip antenna that limits the range but enables a further miniaturized device. We also present an ASIC design for our multiband backscatter approach to further reduce size and power.

Figure 2. μLocate prototypes. Our miniaturized prototypes require two button cell batteries (left), which are as small as 5.8 mm in diameter. Our multiband prototype based on the KL03 microcontroller is 11.8 × 7.5 × 2.1 mm and includes chip antennas for 900 MHz, 2.4 GHz, and 5 GHz. Our 5-GHz prototype (right) measuring 7.2 × 5.1 × 0.5 mm is designed to operate at shorter ranges and in an even smaller form factor. The prototypes are placed on a U.S. penny for scale.

Our evaluation shows our off-the-shelf hardware and ASIC consume 93 μW and 5 μW, respectively. This translates to an expected operational lifetime of 5–10 years of duty cycled operation on small, 5.8 mm diameter button cell batteries for our off-the-shelf microcontroller hardware and ASIC prototypes. Further, we demonstrate 3D localization accuracy, which scales with the distance. Our system gives localization errors of 2, 12, 50, and 145 cm at 1, 5, 30, and 60 m, respectively, between the AP and our backscatter devices. Finally, across distances up to 60 m from an AP, our algorithm can compute the location values using between 9 and 28 frequencies, which translates to a latency of 25–70 ms.

In addition to the above benchmarks that characterize our system's performance, we also deploy the system in the following two real-world scenarios:

• Five homes in a metropolitan area including three single-story apartments and two multistory townhouses. We select a variety of locations and orientations across different rooms, behind closed doors, in closets, on shelves, and even hidden in couches to determine whether our system can localize objects across an entire home to enable item tracking.
• Surgery wing of a hospital including patient pre-op and post-op rooms as well as storage facilities. We run experiments in various locations for tracking mobile equipment such as on IV poles and vital signs monitors that travel with patients between different rooms.

Back to Top

2. System Design

Our design has three key components: (1) our low-power architecture that delegates the coding operation to the access point, allowing us to decode backscatter signals at large distances using subcentimeter-sized devices, (2) our phase-extraction algorithm that can extract the phase from signals below the noise floor, and (3) our online search algorithm that dynamically queries a different set of frequencies given the signal quality to reduce latency. In the rest of this section, we describe each of these components.

 2.1. Low-power delegating architecture

The goal of our architecture is to enable localization at long ranges with very small, low-power backscattering IoT devices. To achieve this, we have to address two competing requirements: (1) because backscattered signals are orders of magnitude weaker than active radio transmissions, to achieve long range, we need to perform significant amounts of coding, and (2) in order to be compatible with off-the-shelf low-power microcontrollers, the IoT device design must be limited to simple operations.

To achieve this, we delegate the complex coding operations to the access point (AP). Our design works as shown in Figure 3. The μLocate AP transmits a coded narrowband signal, whereas the μLocate IoT device simply backscatters this signal transmitted by the AP with a frequency shift of 1–2 MHz. This shifting can be achieved using the built-in oscillators on commercially available microcontrollers (see Section 3). Our architecture therefore eliminates the need for an active radio on the μLocate device. Shifting the signal on the IoT device has three key advantages: (1) it helps distinguish the backscattered signal from the direct signal transmitted by the AP in the frequency domain, allowing the receiver to easily decode it. More importantly, at the shifted frequencies, the receiver effectively receives a coded backscattered signal that it can use to extract the phase required for localization. Furthermore, we achieve this without requiring the IoT device to perform the complex coding operations itself, allowing for centimeter-scale low-power implementations without a custom ASIC. (2) By shifting the signal to different frequencies, multiple tags can coexist and be localized simultaneously using a single AP, and (3) by using ON and OFF keying at the backscatter device, one can also enable data communication in addition to localization.

Figure 3. Low-power delegating architecture. The access point (AP) transmits a chirp spread spectrum signal with a bandwidth BW to the IoT device with an oscillator and RF switch. The switch backscatters the coded signal back to the AP with a frequency shift of Δf.

What kind of coding do we use at the AP? The objective here is to pick the coding scheme that can be used to decode the phase of backscatter signals that are far below the noise floor. To this end, we use chirp spread spectrum as our coding mechanism. In chirp spread spectrum, we transmit a signal with a linearly changing frequency over bandwidth (BW) varying between and . Chirp signals have the following advantages that make them the best fit for our application: (1) in comparison to phase, amplitude and discrete frequency-shift modulation, chirp spread spectrum (CSS) achieves an efficient trade-off between bandwidth and decoding capability, when the signal is drowned by noise.³ Further, it is resilient to both in-band and out-of-band interference,¹ and (2) unlike direct-sequence spread-spectrum that requires complex synchronization and has a long acquisition time when the signal is below the noise floor,^14,5 CSS receivers have comparatively lower complexity and significantly shorter acquisition times.¹

Specifically, we choose a narrow BW of 500 kHz where the chirp duration T is 7 ms, which we find balances accuracy and latency well. The receiver at the AP samples these signals at 1 MHz. In the next few sections, we first describe how to estimate the phase from CSS signals. We then show how to selectively query across the 900 MHz, 2.4 GHz, and 5 GHz ISM bands to disambiguate the multipath, estimate the range, and achieve 3D localization. Finally, we describe how we can achieve real-time tracking.

 2.2. Below-noise backscatter phase

Assume that the AP, which is placed at a known location, is separated from the IoT device by a distance of d. When the AP transmits the chirp signal, it propagates a total distance of 2d including the time it takes for the backscattered signal from the IoT device to arrive back at the AP. The wireless channel of such a signal is . Here, a is the attenuation, f is the frequency at which the signal is being transmitted, and c is the speed of RF signals in the medium. At a high level, if we can extract the phase of the backscattered signal at a specific frequency, we can estimate the range d.

Thus, if the AP transmits a tone at a single frequency f, in the absence of multipath, the phase of the backscatter signal can be used to estimate the range. However, such single-tone signals (e.g., RFID) have a limited range in the context of backscatter communication and hence cannot achieve the long ranges that are required for IoT localization. As described earlier, the AP instead transmits a linear frequency modulated chirp pulse, which allows our system to operate at longer ranges without further amplifying the signal. As shown in Figure 3, the tag then shifts this chirp signal by a frequency Δf, and the shifted signal is received back at the AP. Hence, the receiver receives a chirp signal whose frequency varies from −BW/2 + Δf to +BW/2 + Δf.

We use correlation to decode this signal. Specifically, the receiver first correlates the received signal with a downchirp, a signal where the frequencies linearly decrease from +BW/2 + Δf to −BW/2 + Δf. This downchirp is synthesized on the receiver. During the multiplication step of the correlation, the linear change in the frequency between the receiver upchirps and the synthesized downchirps cancels each other out. During the addition step of the correlation, we effectively sum the energy across all the chirp frequencies providing coding gain and allowing us to decode the backscatter signals below the noise floor.

Extracting the channel phase information from this signal requires us to address three challenges: (1) because the chirp signal is spread across frequencies, we do not get the phase at a single frequency but rather the chirp phase that is a combination of phases across all the frequencies in the chirp, (2) to decode and estimate the phase of the signal, we need to accurately estimate the beginning of the backscatter chirp, and (3) our small low-power microcontrollers that shift the incoming chirp by Δf introducing an unknown carrier frequency offset (CFO) between the AP and the IoT device that changes the phase of the received signal.

To address the above challenges, at a high level, we first describe how we jointly estimate the carrier frequency offset (CFO) and correct for the start of the backscatter chirp. We then show how to compute the channel phase information given the phase of the backscattered chirp. The details for this are described in our SenSys paper.¹²

 2.3. Multipath disambiguation

In practice, due to multipath, the obtained phase is actually the sum of phase of the direct line of sight signal and the phase of the different multipath reflections. Hence, to accurately localize the IoT device, we should disambiguate the various multipath reflections from the direct line of sight signal. To achieve this, we dynamically send chirps across the ISM bands in 900 MHz, 2.4 GHz, and 5 GHz and estimate the phase of each frequency using the above method. At a high level, by combining the phase information across all these frequencies, we can simulate an ultra-wide band transmission that can be used to disambiguate the multipath in the environment. Because our chirps are 500 kHz wide, we can transmit multiple chirps in adjacent bands across the three ISM bands. This however would significantly increase the latency of localization. Specifically, there are bandwidths of 26 MHz, 80 MHz, and 180 MHz in the 900 MHz, 2.4 GHz, and 5 GHz ISM bands. Dividing them into 500 kHz intervals results in 572 chirps across all these bands, which translates to 4 s using a 7-ms chirp. We instead design a dynamic frequency selection algorithm that significantly reduces the number of queried frequencies by 10–20×.

Dynamic frequency selection. Our algorithm is based on three key principles.

We determine the ISM bands that can be used depending on the distance of the IoT device. Specifically, signals at 5 GHz have very high attenuation and can be decoded using the above method only if the IoT device is in the same room as the AP. Similarly, signals in the ISM band of 2.4 GHz experience a lower attenuation compared to 5 GHz but have a higher attenuation than 900 MHz. Thus, we can prune a number of frequencies depending on the attenuation observed from the IoT device. Specifically, we first send a chirp in the 2.4 GHz band and determine the SNR of the chirp. If the SNR is very high, the device is at a short distance from the AP and hence all three ISM bands can be used. Otherwise, only the 900 MHz band and 2.4 GHz band can be used to estimate the distance of the IoT device. When the receiver cannot decode the initial chirp, we use only the 900 MHz band.

Each new frequency provides a new linear equation for the multipath combination at that frequency. However, picking two frequencies that are next to each other does not provide independent equations because the amplitude and phases of different multipaths are similar for adjacent frequencies. Thus, querying frequencies that are separated by the highest bandwidth provides more useful information than querying adjacent frequencies. Thus, we can reduce the number of frequencies that are queried by picking them such that the gap between them is maximized.

The backscatter device can reflect signals simultaneously across multiple frequencies. Thus, the AP can concurrently transmit four coded signals centered at frequencies f₁, f₂, f₃, and f₄, and the backscattered phase can be decoded at all these frequencies. This is used to parallelize the number of queries. We note however that requiring the AP to transmit multiple concurrent frequencies in the ISM band requires us to reduce the power on each of these frequencies proportionally to comply with FCC regulations. This would reduce the range of our system. We instead use the following rule to opportunistically parallelize our transmissions if the signal can be decoded at 2.4 GHz and then the 900 MHz is much stronger and hence we can query four frequencies concurrently at 900 MHz. Similarly, if the signal can be decoded at 5 GHz, we can query four frequencies concurrently at 2.4 GHz. Finally, if the signal strength is strong at any of these ISM bands, we increase the number of concurrent frequencies in that ISM band in the next round.

Algorithm 1 Dynamic Frequency Selection

1. min_bands,max_bands ⊳ Min and max of available bands
2. range = 0
3. function QUERY(min_bands,max_bands, range)
4.     newrange = Range_estimate (min_bands ∪ max_bands)
5.     if newrange - range < threshold then
6.         return newrange
7.     if newrange - range > threshold then
8.         for i in 1..length (min_bands) do
9.             if max_bands_i < min_bands_i then
10.                 min_i = ∅
11.             else
12.                 
13.     if mid_i = ∅ then ⊳ No more frequencies available
14.         return newrange
15.     min_bands = mid_bands ∪ mid
16.     max_bands = mid ∪ max_bands
17.     return QUERY (min_bands,max_bands,newrange)
18. function Range_estimate(frequency_1..n)
19.     phase_1..n = ESTIMATEPHASE(frequency_1..n) ⊳ §2.2
20.     Channel = DFT(frequency_1..n, phase_1..n)
21.     peaks = FINDPEAKS(Channel,prominencethreshold) return peaks₁

Using the above principles, we can design a binary search algorithm as shown in Algorithm 1. Specifically, once we identify the ISM bands that can be used, the AP first sends a chirp at the minimum and the maximum frequencies of the chosen bands as shown in Figure 4. To improve the distance resolution, the next frequency to query is picked using a recursive binary search function that chooses frequencies at the extremes of the spectrum. After each query, the receiver computes the new distance estimate by using an inverse FFT on the phases at all the queried frequencies to get the time-domain multipath profile. By using a fixed energy threshold over this profile, we identify the closest (and therefore most direct) path from the device. Further implementation details are described in Nandakumar et al.¹²

Figure 4. Dynamic frequency selection. In the first iteration, we start with the frequencies that are most separated. This translates to the frequencies at the edges of the three ISM bands.

Back to Top

3. Prototyping Devices

Off-the-shelf prototypes. We build three different prototypes. The first uses the DE0-Nano FPGA development board to control an RF switch. We use an HMC190BMS8 RF switch for 900 MHz and 2.4 GHz, and a UPG2163T5N switch for 5 GHz. Both switches are mounted on a 2-layer Rodgers 4350 substrate and toggle between open and short impedance states. The switches are connected to the same multiband antenna used at the AP. By using the onboard 50 MHz oscillator and PLL, we use this setup to experiment with different offsets prior to settling on 2 MHz.

The second prototype focuses on achieving our desired centimeter scale form factor and low-power consumption. Specifically, all our low-power IoT device needs is an oscillator and RF switch, as the coding is offloaded to the transmitter. In order to optimize for both size and form factor without custom silicon, we leverage low-power microcontrollers designed for IoT applications. A microcontroller such as the Kinetis KL03 requires roughly 30 μA to run its onboard oscillator at 8 MHz, and only 77 nA in its lowest power sleep mode.¹⁵ Because the platform is programmable, we can adjust the duty cycle to achieve significantly longer lifetimes on platforms with tiny batteries.

We fabricate our off-the-shelf prototype on a standard one-sided FR4 flex PCB material using the Kinetis KL03 microcontroller, which is available in a 2.0 × 1.6 mm WLCSP package, two UPG2163T 5N RF switches, and a 900-MHz and 2.4-GHz dual band chip antenna, as well as a 5-GHz chip antenna. We select these ceramic chip antennas that are specifically designed for small form factor applications and specify antenna gains of up to 3 dBi with efficiencies of 60–70% at 900 MHz and 2.4 GHz² and up to 79% at 5 GHz.¹⁶ The final assembly is as shown in Figure 2, which consumes an average of 93 μW.

The final prototype further miniaturizes the device by focusing on just 5 GHz as shown in Figure 2. We use a fast-turnaround laser micromachining method to produce flexible circuits. We begin by placing a sheet of copper foil on a low-tack adhesive and cut the outline of the desired copper traces using a UV DPSS laser micromachining system. Next, we peel the excess copper off of the adhesive leaving only the desired pattern. We then place a piece of 25- μm-thick Kapton tape, which can withstand high temperatures required for soldering, onto the copper and lift the traces off of the adhesive. This method could be repeated and stacked to produce a multilayer design connected through vias as with a normal PCB. We use only the 5-GHz antenna in this prototype and hence are limited to a smaller range.

IC design. Further miniaturization and power optimization can be achieved by implementing a custom IC, which allows for combining the RF switch and impedances into a single chip. Further, this significantly decreases the required area to only a few mm². The full IC design consists of a frequency synthesizer, RF switch, and at least two impedances states. We design and simulate a complete solution in a TSMC 65 nm LP process as described in Nandakumar et al.¹²

Figure 5 shows the lifetime of both our off-the-shelf and IC designs with different battery sizes. We limit the maximum of the plot to 10 years as this is the typical maximum shelf life of button cell batteries. These battery life values demonstrate that our design is so low power that the system performance is no longer limited by the electronics but rather the battery technology.

Figure 5. Prototype battery life. Battery life estimates for duty cycled operation of our prototypes operating at 3 V from a coin or two button cell batteries. The plot is limited to 10 years, which is the shelf life of a button cell.

Back to Top

4. Evaluation

We evaluate our system in line-of-sight (LOS) and through-wall settings. We then deploy μLocate in five different homes and a hospital to measure real-world performance.

 4.1. Benchmarking accuracy

LOS scenario. We conduct experiments on a 100 × 100 m open field. We place the AP at one end of the field and move our FPGA IoT prototype away from the AP in increments of 10 m along different angles. Figure 6a plots the 3D localization error and shows the following:

Figure 6. The plots show the 3D localization error for our line-of-sight benchmark. The figure (a) shows that our operational range is around 60 m. The figure (b) shows the 3D localization accuracy for distances below 5 m. At these distances, our system ends up using all frequencies across 900 MHz, 2.4 GHz, and 5 GHz.

• We have a 60-m range in LOS scenarios at which the worst-case 3D accuracy is 1.5 m. Beyond that distance, the received power of the backscattered signal was too low to decode even with the chirp spread spectrum coding.
• The accuracy scales with the distance from the IoT prototype. Specifically, we can achieve a localization error of 15 cm at a distance of 10 m, which increases to around 25 cm at a distance of 20 m. This further increases to 78 cm at a distance of 40 m. This change is due to the fact that above 30 m, the received power at 2.4 GHz is noisy due to attenuation in comparison to 900 MHz. This introduces error into the phase measurements reducing the accuracy.

We note that at the above-measured distances our algorithm did not pick any 5-GHz frequencies because the corresponding backscattered signal was very weak at these distances. So we rerun the experiments in a 5-m room with finer increments of 1 m. Figure 6b shows the 3D localization accuracy at these distances. The figure shows that when the IoT prototype is within a meter from the AP, the worst-case localization error was less than two cm. At a distance of 2 m, we could still achieve a 3-cm worst-case accuracy. However, the worst-case error was less than 14 cm up to distances of 5 m. The reason for these low errors was that the algorithm was able to use frequencies in the 5-GHz range, which significantly improve the location accuracies. In particular, 5 GHz helps with the accuracies for two main reasons: (1) higher frequencies translate to smaller wavelengths, which allows for better resolution, and (2) unlike 900 MHz and 2.4 GHz, each of which has a limited amount of bandwidth, our algorithm could query frequencies across a 180-MHz bandwidth in the 5-GHz range. These results demonstrate that for close-range room-scale applications we can leverage extra information from 5 GHz, whereas applications that require longer ranges cannot leverage these signals.

Finally, Figure 7 shows the number of frequencies that were queried by the AP before it converged to the location values for all the distances in the above two experiments. The plot shows the following:

Figure 7. Number of queried frequencies and its corresponding Latency. The plot shows the total number of frequencies and the Latency required for 3D localization across all locations in Figure 6b and a.

• At distances less than 5 m, the AP had to query less than 20 frequencies. In fact, when the IoT devices were 1–2 m away, the number of queries was even less at 15. This is because at short distances, the direct path is stronger than the non-line-of-sight paths for all the three frequency bands and hence the AP converges on the locations quickly. The latency for these locations is less than 35 ms as multiple frequencies can be queried in parallel.
• Between 10 and 20 m, the AP queries both 2.4 GHz and 900 MHz to disambiguate the direct path and this increases the number of frequencies to 25. However, the 900-MHz band frequencies can still be queried simultaneously, leading to a latency of 65 ms.
• An interesting trend happens at longer distances. Here, only 900-MHz frequencies are queried. Further, because the accuracies at these distances are much lower, the threshold values are also lower. As a result, the number of iterations is reduced to 8 for 60 m. However, because the SNR is weak, we have to query these frequencies sequentially. These two factors counteract each other and hence the latency stays between 55 and 70 ms.

Through-walls scenario. Next, we conducted experiments in an office building across multiple office rooms. The offices were separated with dry wall, metal studs, and wooden doors and had typical office furniture such as tables, chairs, and leather couches. Additionally, the tested locations had multiple Wi-Fi access points and 915-MHz RFID readers representing significant interference from other devices. Note that our chirp coding is resilient to both in-band and out-of-band interference.⁵ We place the AP in the first office room as shown in the layout in Figure 8. We then move our IoT prototype to different rooms with their doors closed shown as different points in the layout. For each location, we repeat the localization experiment multiple times and then compute the 3D localization errors.

Figure 8. Through walls setup. Floor plan showing the AP and IoT device in an office environment spanning five rooms. All the doors were closed during the experiments.

Figure 9 plots the 3D localization error as a function of different positions as shown in Figure 8. The figure shows that for the most part the localization accuracy decreases as the distance and the number of walls increase. It is however not always the case due to multipath and fading effects. We note however that the worst-case accuracies at location 6, which has 3 walls separating the AP, and the IoT prototype was still around 33 cm. This is expected because the 900-MHz and 2.4-GHz backscatter signals were strong enough to be able to reliably decode the phase information, which allows us to disambiguate the multipath.

Figure 9. Through walls accuracy. The plot shows the 3D localization accuracy across the points indicated in Figure 8 rather than range due to their arbitrary placement.

 4.2. Real-world deployments

Home deployments. We deploy our system in five homes in a major metropolitan area to understand its performance in realistic use cases. We select a variety of homes including three single-story apartments and two multistory townhouses. The single-story apartments had two to three rooms each, whereas the multistory townhouses had two or more floors with two and three rooms, respectively. In the apartment deployments, we select a central location for the AP to maximize coverage. For the townhouse deployments, we place the AP on the bottom floor for convenience. In each of the homes, we select a variety of locations including different rooms, behind closed doors, in closets, on shelves, and even hidden in couches to understand if our system can actually localize objects across a whole home and enable item tracking applications.

Figure 10 shows CDFs for 3D localization accuracy across each of the five homes. The figure shows that for the first three homes the worst-case localization accuracy was less than 30 cm. These three homes correspond to single-story apartments where all the devices are on the same floor. The worst-case accuracy was around 60 cm and 1.2 m for homes 4 and 5, respectively. These two homes were multistoried town-houses where the devices were on different floors. The higher error is due to two main factors. First, it was difficult to get the baseline distance measurements across floors. This contributed to errors in estimating the actual location of the IoT device. Second, in home 5, different floors were connected through a narrow staircase, whereas the direct path was through thick ceilings that significantly attenuated the signal. This highlights a basic challenge with localization techniques that require some direct path to appear at the receiver. Figure 11 depicts the above results by classifying them into categories across all the homes. We categorize the locations as LOS, NLOS on the same floor, hidden within a couch, in a closed closet, and finally on a different floor. For the reasons described above, the accuracy was lower when the device was on a different floor. When the IoT device was hidden in a couch on the same floor, the error was less than 30 cm.

Figure 10. Accuracy per home. The plot shows a CDF of localization error for all points measured in a home.

Figure 11. Accuracy by scenario. This plot shows a CDF of localization errors across different categories such as LOS placement and locations in closets.

Hospital deployment. In order to evaluate realistic use cases in healthcare scenarios, we deploy our system in a local hospital. Specifically, we perform experiments in the surgery wing of the hospital and perform localization in patient pre-op and post-op rooms as well as storage facilities. Figure 12 shows the floor plan of the approximately 5000-ft² surgery wing. The area includes a waiting room and check-in desk, followed by a hallway with a row of patient rooms for pre-op and post-op care as well as a storage room. We perform measurements at locations that represent realistic use cases as indicated in Figure 12. We select a location for the AP in the side hallway in order to minimize disruption to hospital staff. We select locations in patient rooms and a storage closet as these are typical scenarios where hospital staff maintain a standard inventory of items. Additionally, we select other arbitrary locations in the hallways for tracking mobile equipment such as IV poles and vital signs monitors that travel with patients to different rooms. The majority of these locations do not have direct line of sight to the AP and include barriers such as curtains, sliding glass doors, and standard wooden doors.

Figure 12. Hospital deployment. Deployment in a hospital surgery wing. We select nine points shown on the floor plan (left) including duplicates to test doors and curtains. We include patient pre-/post-op rooms (center) and storage facilities (right).

Figure 13 shows the tracking accuracy across each of these locations that are ordered by distance. We note that the duplicated points represent separate measurements at the same location with barriers such as curtains or doors open and closed. Our system achieves a mean accuracy of 35.12 cm across all of the different locations in this hospital setting. Further, as is expected from our design, the accuracy scales with the distance to the tag: close by locations can achieve an error lower than 20 cm, whereas farther locations have localization error of 70 cm. These errors are small enough that we can track the equipment in the hospital across different rooms as well as the closet area. We note that in hospital post-op and pre-op settings the layout is typically on a single floor. Further, the barriers between the rooms are either curtains or thin doors. Thus, we can achieve high localization accuracy in this application setting.

Figure 13. Hospital accuracy. Localization accuracy results for each of the points marked in Figure 12.

Back to Top

5. Related Work

There has been recent interest in backscatter as a low-power communication mechanism. These techniques either back-scatter existing TV,¹¹ Wi-Fi,^{8, 4} and FM signals²⁰ or generate Wi-Fi-compliant transmissions using techniques such as Passive Wi-Fi^{9, 7, 22} and FS-backscatter.²³ These Wi-Fi-based approaches have a receiver sensitivity of only −90 dBm and hence have a limited range and cannot work across rooms unless the signal source is placed close to the backscatter tag.¹⁰

There has also been recent interest in long-range back-scatter solutions,^{17, 18} which¹⁷ achieve a longer range and are compatible with off-the-shelf LoRa radios. However, this prior work does not support localization. Further, existing implementation of LoRa backscatter requires FPGAs and consumes 5–10 mW of power. By contrast, we introduce a novel architecture that delegates the complex CSS coding operations to the AP and introduce a CSS backscatter design that has orders of magnitude lower power.

The closest related work is Slocalization,¹³ which back-scatters UWB signals to achieve low-power localization. This design however works only with static scenarios and incurs delays on the order of minutes to hours to output the location value. This is because FCC regulations significantly limit the transmitted power of UWB signals compared to typical transmissions in ISM bands. Further, because the backscatter system in Pannuto et al.¹³ does not use coding such as the CSS modulation used in our design, it requires integrating the received signal over 10 min to more than an hour, depending on the deployment, to get the location value. By contrast, our approach can provide the location value within 70 ms while achieving a range of 60 m and thus can support practical applications.

Back to Top

6. Discussion and Conclusion

We present the first wireless localization system that consumes microwatts of power in a subcentimeter form factor and can be localized across a whole home or hospital through walls. In this section, we outline limitations and avenues for future research.

Supporting multiple devices. In addition to using time-division multiplexing, we can also set different backscatter devices to shift the signals by different frequencies to support multiple devices as shown in Figure 14. Specifically, each backscatter device could use a different shift and reflect the incoming signal from the AP at the same time. The receiver can process the received signal across different shifts to concurrently localize multiple devices. More specifically, recent work has demonstrated that up to 256 devices can concurrently transmit using chirp spread spectrum.⁶ Because our design leverages chirp spread spectrum, one can design large-scale networks where devices can concurrently transmit and be localized at the same time.

Figure 14. Feasibility of multiple devices. Snapshot of the chirp signal captured on a spectrum analyzer. The plot shows the baseband spectrum of the original coded transmissions as well as three backscattered signals at frequency offsets of 2, 2.5, and 3 MHz.

Using multiple APs. In order to achieve high accuracies with a single AP, our algorithm relies on knowledge of the floor plan of a room to eliminate infeasible location estimates. We realize however that some applications may require more generalizable solutions, for example where the localized objects might be moved outside of a known set of rooms. The key reason for requiring these constraints however was that we use a single AP for localization. Adding additional access points, or additional antennas with greater separation, would provide better angular resolution and hence address this limitation. For example, an AP placed on the orthogonal wall of a building or on another floor in multifloor scenarios would help disambiguate multipath and provide more information to estimate the location. Future work could build upon the basic techniques we show here to explore the trade-off between the infrastructure overhead of adding additional APs and antennas versus the robustness and accuracy improvements they would contribute.

LOS path. Existing 3D localization algorithms assume that while there is multipath, there is at least some energy from the direct path at the receiver. Our design also makes a similar assumption. We note however that our design also increases the probability that the direct path signal has some energy by leveraging frequency diversity across the three ISM bands. Specifically, while the direct path signal could be weak at a specific frequency, it is likely to be noticeable at at least one of the three ISM bands.

Back to Top

Acknowledgments

This work was funded in part by the National Science Foundation and Google Faculty Research Awards.

Back to Top

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.

---

No entries found