NOVID
Augmenting Pandemic Response with Network Theory and Ultrasound
With everyone’s phone glued to their person every hour of the day, it would seem that contact tracing would be a nearly solved problem for modern pandemic response. But in GPS-denied indoor and obstructed environments and with Bluetooth being a false-positive frenzy for proximity detection, how can you build a physical proximity graph with accurately estimated distance between phones?
In the early months of the pandemic in spring and early summer 2020, I worked with a team led by CMU math professor Po-Shen Loh to answer this question. Soon after joining, I redesigned and implemented NOVID’s BLE+ultrasonic ranging protocol on iOS, allowing NOVID reliable sub-meter mobile ranging accuracy for the first time, making it one the world’s most accurate contact tracing apps.
*Images courtesy of NOVID (Expii Inc.) unless otherwise notedTLDR: NOVID
Problem: Contact tracing as a pandemic response mechanism requires high-accuracy and robust proximity sensing, which cannot be reliably accomplished using typical sensing mechanisms on smartphones (e.g. GPS, BLE).
Solution & Contribution: Joining the NOVID team in March 2020, I redesigned and implemented a novel bilateral BLE+ultrasonic ranging protocol for iOS & Android, allowing NOVID to reliably range other devices with inch-level (sub-meter) accuracy, making it one of the world’s most accurate contact tracing apps. By fall 2020, we had letters of support from several universities, health departments, & public officials, and were officially deployed in various schools & cities across the country from Georgia Tech to Carnegie Mellon to the City of Santa Fe.
Featured in:
“A startup called NOVID has developed a world-leading, contact-tracing capability with a number of important features - including the use of ultrasonic ranging to provide inch-level understanding of the distance between phones running their app. That’s roughly 100x better than the accuracy being provided today by BLE measurements. But they don’t just stop there…”
“NOVID leverages a combination of ultrasound and Bluetooth technology to note other devices that are within 6 feet, and only if they remain that close for 15 minutes or more. By briefly using the device’s microphone and measuring the time sound takes to travel, ultrasound can accurately measure the distance between devices. The benefit of this combined method is avoiding false positives that would be generated from Bluetooth alone, such as contacts that may be on the other side of a wall – nearby, but not creating a risk of exposure.”
“NOVID, a contact tracing app that anonymously traces users' exposure to COVID-19, is the first such app in the world to demonstrate the distance accuracy required to perform contact tracing without significant false positives. In a newly released systematic experiment, the app correctly classified 99.8% of the faraway interactions as such.”
A Fundamental Weakness in Contact Tracing Deployments
Bluetooth signal strength alone is a poor way to range mobile devices
Without the ability to fingerprint environments or ultra-wideband antennas for RF ranging, received signal strength indicator (RSSI) between two antennas is simply a poor means of estimating distance due to multi-path reflections and attenuation from the surrounding environment.
This is a fundamental weakness in the sensing infrastructure of contact tracing deployments that can’t be avoided without compromising accuracy and privacy, leading to high false positive rates and decreased trust in the system.
Figure showing RF Signal Strength vs. Antenna Distance: top blue is ideal free space Friis propagation model, orange is realistic Friis model modeled by "Pister Hack" (Friis equation minus a random loss uniformly distributed between 0-40 dB) meant to model the random effects of multi-path attenuation in real-world environments that plague RSSI-based ranging methods.
A Solution with Inch-Level Accuracy
The Robust Bilateral Ultrasonic Ranging Protocol
Robust Inch-Level Accuracy with the Bilateral Ranging Protocol
Time Synchronization Troubles
When I joined, the team’s paradigm for ultrasonic ranging was to attempt global time synchronization between the mobile devices (using NTP synchronization, GPS time, or some Bluetooth handshake) to measure the ultrasonic signal’s time-of-flight, methods which proved either inaccurate or infeasible on Android & iOS.
The Bilateral Ranging Protocol
Recognizing we could achieve a synchronized timebase simply by sending chirps back and forth between each phone, with ranging accuracy limited only by the resolution of each audio buffer and SNR of the transmitted and received chirps, I worked with Professor Loh to design NOVID’s inch-level accurate ultrasonic ranging protocol.
Using BLE to handshake between two devices potentially within 6 feet of one another and communicate relevant metadata, the two devices engage in the bilateral ultrasonic ranging protocol, sending cleverly-designed ultrasonic chirps back and forth to achieve inch-level accuracy ranging robust to attenuation and multi-path reflections.
When proximity below 6 feet is measured twice over an extended period, the interaction and its BLE and ultrasonic ranging metadata is uploaded to the anonymous interaction network.
Using iOS’s Core Bluetooth & Core Audio libraries and the vDSP Accelerate framework for signal processing, I developed and tested the ranging protocol on iOS, subsequently working with the Android developers to ensure parity and compatibility on both mobile OS platforms. We submitted a successful patent application on NOVID’s contact tracing system in June 2021.
Active Deployments 2020-21
Within weeks, NOVID and its ultrasonic-ranging backed network theory approach garnered letters of support from health officials and medical institutions, including USC’s Keck School of Medicine and the City of Pittsburgh’s Mayor’s Office.
By fall 2020, NOVID was deployed to cities and schools including the city of Santa Fe local government, Carnegie Mellon University & Allegheny County, Georgia Tech, and Grand Valley State University, alongside various private deployments.
