Sound-based Positioning

This project is an attempt at automatic localization of components, with the intention of enabling easy machine calibration when the different machine parts have possibly unknown locations (e.g. cable driven winches in a random environment).

Concept

Sound travels in the air (and other media) at a specific speed. It can thus be used to measure distance between different locations. The most common system for distance measurement through sound consists of sonars that measure the roundtrip time for a sound wave to go from source to target and back, although the target is not necessarily known in this case.

Another common range measurement approach is related to acoustic room calibration. Calibrating the sound in a room usually involves multiple microphones together with one or multiple sound emitters (such as clapping hands). Given a set of synchronized microphones and emitters, the distance between each pair can be recorded, and the position of each of these further computed using signal processing techniques such as multidimensional scaling for Euclidean Distance Matrices - see this tutorial for a review of algorithms.

The main challenges of multi-node range measurement include (i) time synchronization between the nodes, and (ii) environment noise mitigation.

Time Synchronization

Time synchronization is often coupled with range measurement. When it is not, then there is usually an assumption that the transfer time between two nodes is negligible (e.g. for short-distance light transport).

In the case of GPS, the fourth satellite that is required for accurate positioning comes from the receivers usually having poor clocks. While the clock frequency skew can be estimated from individual satellite signals, the timing offset cannot be disambiguated from the distance with three satellites alone. Thus the clock offset is an additional unknown which is found (with the three spatial coordinates x, y, z) by using a set of at least four satellites.

Wireless Sensor Networks often require time synchronization and have thus developed a lot of algorithms for that. Various recent surveys present existing protocol variants such as RBS that uses a master broadcasting a periodic beacon and nodes messaging their timings, and TPSN that uses a sender-receiver protocol with timestamping at the MAC layer for increased accuracy. One common challenge (noted in conclusion of this survey) is measuring the transfer delay, which is tightly coupled with the distance between the nodes. Both can be jointly estimated.

Sound nodes should probably be wireless nodes (i.e. using for example the nRF52). Since RF signals are much faster than sound, we can use a beacon from the nRF52's soft device to synchronize the nodes. Fortunately, this tutorial explains exactly how to do that.

Noise Mitigation

For reliable data transmission, various spread spectrum methods provide protection against environment noise. The main idea is to modulate the original signal with a key that is only known/used by the sender and receiver.

For the specific application of range measurement, a good technique is Chirp Spread Spectrum which uses wideband linear frequency modulated chirp pulses to encode the signal. Beyond protecting against multi-user and multi-path interferences, it also often comes with the ability to infer the target speed from the Doppler effect. The challenge is to accurately generate a loud enough chirp, and then eventually decode it on the receiver (probably with some automatic gain control).

Implementation

WIP