Ultrawide-band (UWB) based localization is a promising approach to creating an “indoor GPS”. These systems localize a mobile transmitter using receivers at fixed, known locations. Currently, many systems require these receivers to be time synchonized.

Synchonization is acheived by designating certain receivers as masters, which synchonize other receivers within range to their own clock. Indoor environments have complicated signal propagation properties. So, which receivers should be designated as masters to maximize the quality of the localization across the entire venue?

We can formulate this as a combinatorial optimization problem. Let \(X\) be an \(m\times n\) matrix where \(m\) is the number of receivers and \(n\) is the number of potential master receivers. Let \(x_{ij} = 1\) if receiver \(i\) syncs with master \(j\), and 0 otherwise. Let \(D \subseteq \mathbb{R}^2\) represent the venue. We want to find a master configuration that maximizes the localization quality \(q\) over \(D\):

\[\max_{X} \sum_{d \in D}q(d, X)\]

Subject to the constraints that each receiver syncs with at least one master:

\[\sum_{i \in X_i}x_{ij} > 1\]

and each potential master syncs with at least 3 receivers, or none:

\[\sum_{j \in X_j}x_{ij} > 3 \lor \sum_{j \in X_j}x_{ij} = 0\]

This is a difficult optimization problem, especially as we’d like the localization quality \(q\) to accurately represent reality. Here are some results (masters are blue, receivers are red):


Good configuration

Poor configuration
Heatmaps of approximated localization quality for different master configuations

This work done during my time at Tenera Care.