## 4 Least Squares Methods for Ultrasound Time Difference of Arrival (TDOA) Trilateration  
In our scenario of quickly and accurately locating a mobile phone indoors, ToA (Time-of-Arrival) or _synchronous_ approaches require that times from two separate systems with two separate clocks have to be synchronized--a major source of error. As such, it is desirable to compare only the time of signal arrival at each of the microphones and ignore completely the time the signal was originally sent from the phone, making Lok8 a TDOA (Time-Difference-of-Arrival) or _asynchronous_ approach. The problem is illustrated in Figure 1 and the final matrix solution follows. More detail on this approach can be found in [29, 30]. \begin{table}
\begin{tabular}{c c c c} \hline
**Positioning System** & **Best Accuracy** & **Underlying Technology** & **Available on Smartphones** \\ \hline Wide signal strength & & 2.48 m & GSM & no \\ fingerprinting & & & \\ Skyhook(GSM) & 200 m & GSM & yes \\ Navizon(GSM) & 50 m & GSM & yes \\ Skyhook(Wi-Fi) & 10 m & Wi-Fi & yes \\ Navizon(Wi-Fi) & 20 m & Wi-Fi & yes \\ Hybrid Fingerprinting & 3 m & Wi-Fi & yes \\ RADAR & 2 m & WaveLan & no \\ GP for Signal & & & \\ Strength-Based & 2 m & Wi-Fi & yes \\ Location Estimation & & & \\ Goodtry & 4 m & Wi-Fi & no \\ Ekahau & 1 m & Wi-Fi & no \\ Bluetooth Direction of & & & \\ Arrival & 72 cm & Bluetooth & no \\ Nokia High Accuracy & 20 cm & Bluetooth 4.0 & not yet \\ Indoor Positioning & & & \\ The Bat & 3 cm & Ultrasound & no \\ The Cricket & 3 cm & Ultrasound & no \\ DOLPHIN & 15 cm & Ultrasound & no \\ High Performance & & & \\ Privacy Oriented & 2 cm & Ultrasound & no \\ location system & & & \\ Low Cost Indoor & & & \\ Positioning System & 10 cm & Ultrasound & no \\ SNoW Bat & 15 mm & Ultrasound & no \\
**Lok8** & **\textless{10 cm}** & **Ultrasound** & **YES** \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison of indoor positioning system accuracy. Problem:  
* Mobile phone (\(P\)) has unknown position (\(X_{P}\),\(Y_{P}\)). * Four microphones (\(M1\), \(M2\), \(M3\), \(M4\)) have known positions (\(X_{M1}\),\(Y_{M1}\)), (\(X_{M2}\),\(Y_{M2}\)), (\(X_{M3}\),\(Y_{M3}\)), (\(X_{M4}\),\(Y_{M4}\)). * Four distances (\(d_{1}\), \(d_{2}\), \(d_{3}\), \(d_{4}\)) from \(P\) to \(M1\), \(M2\), \(M3\), \(M4\) are unknown but the differences between them (\(m_{2}\), \(m_{3}\), \(m_{4}\)) are measured ultrasonically; these are the observations. * Find coordinates of \(P=(X_{P}\),\(Y_{P}\)) by solving a system of equations (mathematical model) that relates the \(m=\) three observations (\(m_{2}\), \(m_{3}\), \(m_{4}\)) to the \(n=\) two unknown parameters (\(X_{P}\),\(Y_{P}\)). Solution:  
* Although the coordinates of \(P\) could be found using readings from only three microphones (two observations), four or more mics can be effectively used in the method of Least Squares to determine the Most Probable Value (MPV) for the coordinates of \(P\), plus a Standard Deviation for the MPV. The _observation equations_ are represented in Matrix Methods for Least Squares as: \[{}_{m}\,A_{n}\,{}_{n}\,X_{1}{=}_{m}\,L_{1}{+}_{m}\,V_{1}\] where in our case:
* \(m=3\), \(n=2\)
* \({}_{m}\,A_{n}\,\)contains the coefficients of the unknowns (\(X_{P}\), \(Y_{P}\))
* \({}_{n}\,X_{1}\,\)contains the corrections to be applied to the initial estimates for the unknowns (\(dX_{P}\), \(dY_{P}\))
* \({}_{m}\,L_{1}\,\)contains the measurements (\(m_{2}\), \(m_{3}\), \(m_{4}\))
* \({}_{m}\,V_{1}\,\)contains the residuals (one for each measurement)  
Figure 1: Time Difference of Arrival Trilateration. Control points \(M1\), \(M2\), \(M3\) and \(M4\) are known microphone positions. Point \(P\) is the unknown mobile phone’s position, coordinates of which we are trying to find. Lines \(d_{1}\), \(d_{2}\), \(d_{3}\) and \(d_{4}\) are unknown distances between the phone and each microphone. However, what are known are the differences between the three measurements: \(m_{2}\), \(m_{3}\) and \(m_{4}\). Solving for \(X\) gives the solution:  
\[X=\left(A^{T}A\right)^{-1}A^{T}L \tag{1}\]  
where:  
\[A=