Trilateration of a signal using Time Difference of Arrival

Question

I am having some trouble to find or implement an algorithm to find a signal source. The objective of my work is to find the sound emitter position.

To accomplish this I am using three microfones. The technique that I am using is multilateration that is based on the time difference of arrival.

The time difference of arrival between each microfones are found using Cross Correlation of the received signals.

I already implemented the algorithm to find the time difference of arrival, but my problem is more on how multilateration works, it's unclear for me based on my reference, and I couldn't find any other good reference for this that are free/open.

If you have some references on how I can implement a multilateration algorithm, or some other trilateration algorithm that I can use based on time difference of arrival it would be a great help.

Thanks in advance.

Answer 1

The point you are looking for is the intersection of three hyperbolas. I am assuming 2D here since you only use 3 receptors. Technically, you can find a unique 3D solution but as you likely have noise, I assume that if you wanted a 3D result, you would have taken 4 microphones (or more).

The wikipedia page makes some computations for you. They do it in 3D, you just have to set z = 0 and solve for system of equations (7).

The system is overdetermined, so you will want to solve it in the least squares sense (this is the point in using 3 receptors actually).

Answer 2

I can help you with multi-lateration in general.

Basically, if you want a solution in 3d - you have to have at least 4 points and 4 distances from them (2-give you the circle in which is the solution - because that is the intersection between 2 spheres, 3 points give you 2 possible solutions (intersection between 3 spheres) - so, in order to have one solution - you need 4 spheres). So, when you have some points (4+) and the distance between them (there is an easy way to transform the TDOA into the set of equations for just having the length type distances /not time/) you need a way to solve the set of equations. First - you need a cost function (or solution error function, as I call it) which would be something like

err(x,y,z) = sum(i=1..n){sqrt[(x-xi)^2 + (y-yi)^2 + (z-zi)^2] - di} 

where x, y, z are coordinates of the current point in the numerical solution and xi, yi, zi and di are the coordinates and distance towards the ith reference point. In order to solve this - my advice is NOT to use Newton/Gauss or Newton methods. You need first and second derivative of the aforementioned function - and those have a finite discontinuation in some points in space - hence that is not a smooth function and these methods won't work. What will work is direct search family of algorithms for optimization of functions (finding minimums and maximums. in our case - you need minimum of the error/cost function).

That should help anyone wanting to find a solution for similar problem.