# Range Estimation Based on Distance Differences

It is a range estimation problem, as shown in the figure. The blue circles are the anchor node' positions, which are produced by one moving anchor (the moving direction is shown with black arrow). The brown circle is the unknown user.

I set the interval of each virtual anchor node is 0.2m, the distance from the unkown user to the trajactery is about 3.0m. I obtain the distance differences between any two adjacent anchor nodes, for example, using TDOA metric. There are three cases in the figure, which mean different anchor start points corresponding to user.

Generally, we can calculate the distances from any anchor postion to the user based on distance differences, such as the least square (LS) method. But since the distance difference between two adjacent anchors is small, using the LS method will cause great errors in practical measurement (noise, measurement errors, etc involved).

An intuitive method is choosing two groups of anchor positions with large distance differences to calculate the distance, then obtain all distance estimations based on the other distance differences. But for three cases above, there seems no unified standard.

So, is there any standard/method to solve this problem? or somebady can provide some guides/tips?

Clarify the question: I have the distance differences $$\Delta d_{(i+1,i)}=d[i+1]-d[i]$$ to the user of adjacent virtual antennas (where $$d[i]$$ is the distance from $$i$$-th antenna position to the user), and want to estimate the distances from antennas to user $$d[i], i=1,2,...,N$$, where $$N$$ is the number of antenna positions.

To clarify the question further, I would like to say how I solved this problem before, and also a figure is showed the parameters involved.

As I mentioned above, I know the distance difference $$\Delta d_{(i+1,i)}=d[i+1]-d[i]$$, and the moving distance (I set 0.2m here). To solve this problem, I set the distance from the user to the antenna is $$y$$, namely $$|UO|=y$$, and the distance from point $$O$$ to the antenna psotion $$A_i$$ is $$x$$, namely $$|OA_i|=x$$. So we can obtain the distance $$d_i$$, that is $$d_i=\sqrt{x^2+y^2},$$ then we can also obtain $$d_{i+1}=\sqrt{(x+0.2)^2+y^2}.$$ Now we have the distance difference $$\Delta d_{(i+1,i)}$$. So we can solve this problem with one more formula (one more position). It is what I said Hyperbolic Positioning. Then if we have $$N$$ positions, so we can construct $$N-1$$ fomulas. So I used the least square to combine these fomulas and overestimate the result, namely $$x, y$$. It is easy to understand my method, so I do not input all the details here.

Note that: In my case, the distance of any two adjacent antenna positions is small compared with $$y$$ (the distance from user to antenna trajactory).

One specific example:

I set $$|A_iA_{i+1}|=0.2$$m, $$y=3$$m, $$x=0.1$$m, then you see $$d_i=\sqrt{3^2+0.1^2}$$ and $$d_{i+1}=\sqrt{3^2+0.3^2}$$, so the distance difference $$\Delta d_{(i+1,i)}$$ will be very small. Once the measurement errors, noise, or other error source involved, if we use two adjacent differeces to calculate the distance, just like I used hypobolic+LS above, the results are not good enough.

The intuitive idea is choosing two positions with large distance differences to do the job, since the difference will suffer little from errors relatively.

Using Cedron's method, I did the preliminary work as follow. Some differenct setting: the antenna's moving step is 0.1m, the distance from the user to trajactery is about 1m. Here the distance differences are given as $$y_{1\times 20}$$:

y=[-0.043423795 -0.039331481 -0.035474273 -0.025309761 -0.019823501 -0.017748271 -0.010301581 -0.004165145 0.002257333 0.009348566 0.008298607 0.022343171 0.035716244 0.043296065 0.039169621 0.042370574 0.041379915 0.045609152 0.079869062 0.064377786].

Matlab code to fit function $$f(n)$$ is given here:

%% data fitting


clear;clc; load('y.mat'); % replace with the provided data above **NOTE: it's a column here** t=[1:1:numel(y)]'; plot(0.1*t-0.1,y,'ro') % 0.1 is the moving step in meter %% fitting F=@(x,xdata)(sqrt((xdata*0.1-x(1)).^2+x(2))-sqrt(((xdata-1)*0.1-x(1)).^2+x(2))); x0=[1 1]; [x,~,~,~,~] = lsqcurvefit(F,x0,t,y); title('F(n)-Fitting') hold on plot(0.1*t-0.1,F(x,t)); % 0.1 is the moving step in meter xlabel('X [m]'); ylabel('Distance difference [m]'); %% find zero-crossing zci = @(v) find(v(:).*circshift(v(:), [-1 0]) <= 0); % Returns Zero-Crossing Indices t_find=[1:1e-6:numel(y)]; fitFunc=sqrt((t_find*0.1-x(1)).^2+x(2))-sqrt(((t_find-1)*0.1-x(1)).^2+x(2)); zx = zci(fitFunc); plot(0.1*t_find(zx(1))-0.1, fitFunc(zx(1)), 'kp'); legend('Distance difference','F(n)-fitting curve','Zero-crossing'); hold off

The first fitting result (without toss the outlier) is shown in the figure below.

As expected, the user's coordinate $$x$$ is accurate while $$y$$ is far from the truth (the definition of user's position $$(x,y)$$ is given in Cedron's method below). One tip: we dont't need to calculate the slope of $$f(n)$$, since we can obtian it with $$y=\sqrt{x(2)}$$, where $$x(2)$$ is the second fitting parameter in my matlab codes, also $$x(2)=(y_{ant}-y_{user})^2$$. Indeed, I also obtained similar results using LS, namely, the estimation of $$y$$ is not good, also the distance estimation. I do believe which results from no relative motion along Y-scale.

So the question turns a reasonable outlier detection method and improving the fitting effect, if the zero-crossing method is adopted. It may be not easy...

I'd like to share my results as above. So this question is still open...

• The Extended Kalman Filter is a possible solution.
– user28715
Jun 21 '19 at 15:10
• I would not rule out least squares either. noise doesn’t rule out LS
– user28715
Jun 21 '19 at 15:15
• Hi Stanley, I tried LS, but the estimated distance is longer than actual distance. It may results from possible multipath. But I think there are better methods than LS. Why you think EKF is good? Thank you!
– Land
Jun 21 '19 at 18:49
• I recall a similar example in a book by Bar Shalom
– user28715
Jun 21 '19 at 20:08
• Could you try clarifying the question? What measurements do you have? What are you trying to estimate?
– Royi
Jun 26 '19 at 6:52

Without loss of generality, let's define your anchor positions to be on the $$x$$ axis with $$x_0=0$$ and the gap between each position be $$g$$. Thus

$$x[n] = n \cdot g$$

Obviously, this can be exactly interpolated with the equivalent linear function.

$$x(n) = n \cdot g$$

Let $$(x_u,y_u)$$ be the position of the user.

Now the distance from any position can be found using pythagorean theorem.

$$d(n) = \sqrt{(x(n) - x_u)^2 + y_u^2} = \sqrt{ (gn - x_u)^2 + y_u^2}$$

Define a function to represent the differences of two adjacent anchor positions.

$$f(n) = d(n+1/2) - d(n-1/2)$$

From your measurements, you know the value of this function at integer values plus one half.

$$f(n) = \sqrt{ (g(n+1/2) - x_u)^2 + y_u^2} - \sqrt{ (g(n-1/2) - x_u)^2 + y_u^2}$$

$$f(n) = \sqrt{ (gn + g/2 - x_u)^2 + y_u^2} - \sqrt{ (gn - g/2 - x_u)^2 + y_u^2}$$

It is obvious from inpection that when $$f(n)=0$$ that $$(gn-x_u)=0$$. Thus when you plot your points and find the zero crossing, this will mark where $$x_u$$ is.

Let $$n_*$$ be the n value at the zero crossing.

$$x_u = g \cdot n_*$$

Let $$A = (gn + g/2 - x_u)^2 + y_u^2$$ and $$B = (gn - g/2 - x_u)^2 + y_u^2$$

This makes:

$$f(n) = \sqrt{ A } - \sqrt{ B }$$

Take the derivative:

$$f'(n) = \frac{ A' }{2\sqrt{ A }} - \frac{ B' }{2\sqrt{ B }}$$

Let $$m=f'(n)$$ at the zero crossing. Also, at the zero crossing $$A = B = (g/2)^2 + y_u^2$$

$$m = \frac{ 2 (gn + g/2 - x_u)(g) - 2 (gn - g/2 - x_u)(g) }{2\sqrt{(g/2)^2 + y_u^2 }}$$

$$m = \frac{ 2 g^2 }{2\sqrt{(g/2)^2 + y_u^2 }}$$

Solving for $$y_u$$:

$$\sqrt{(g/2)^2 + y_u^2 } = \frac{ g^2 }{m }$$

$$(g/2)^2 + y_u^2 = \frac{ g^4 }{m^2 }$$

$$y_u^2 = \frac{ g^4 }{m^2 } - (g/2)^2$$

$$y_u = \sqrt{\frac{ g^4 }{m^2 } - (g/2)^2 }$$

$$y_u = g \sqrt{ \left( \frac{ g }{m } \right)^2 - \frac{1}{4} }$$

So all you have to do is find a best fit function for $$f(n)$$, locate its zero crossing($$n_*$$), find the slope at that crossing (m) and plug them into these equations.

The plus or minus possibility for the $$y_u$$ value reflects that your user could be on either side of the line of anchor positions.

I think I've done the math right, but I haven't tested this numerically.

I made no such assumption. What I said is you can find a best fit function to your points, and find the zero crossing and slope of that.

In a bit of hindsight (spanning minutes), you have a better option.

Define an error function as the sum of the squares of $$f(n) - F_n$$ and solve for the $$y_u$$ that minimizes that, with a best guess $$x_u$$ from doing a plot/approximation function. Where $$F_n$$ is your measurement and n is having a value of an integer plus a half. That's much easier and will be more accurate too. You can take it a step further and do it Olympic style, that is, toss out your worst fitting points and recalculate.

This might be equivalent to what you did.

With a little more thought, this is the approach I think will get the most accurate results while doing it most efficiently.

Putting things back on an even integer definition (I'm using $$k$$ instead of $$i$$, $$F$$ instead of $$\Delta d$$).

$$F_k = d_{k+1} - d_{k}$$

$$f_k(x,y) = \sqrt{ (g(k+1) - x)^2 + y^2} - \sqrt{ (gk - x)^2 + y^2}$$

Define the error function as:

$$E(x,y) = \sum_k (f_k(x,y) - F_k)^2$$

Step 1. Do a linear regression on the set of points to get a zero crossing and slope estimate

Step 2. Calculate and initial $$(x,y)$$ using equations above (adjust for the half)

Step 3. Toss any obvious outliers [Optional]

Step 4. Do a gradient search on $$(x,y)$$ to minimize $$E$$

[Optional]

Step 5. Toss outliers

Step 6. Do another gradient search

This is using my first method.

I was getting errors in my calculations until I realized the slope has to be calculated in respect to "n" not "x".

...

g = 0.1

xu = 0.7427
yu = 1

For k = 0 To 19
f = Sqr((g * (k + 1.0) - xu) ^ 2 + yu ^ 2) - Sqr((g * (k) - xu) ^ 2 + yu ^ 2)
Print k, f, act[k]

If f > 0 And p < 0 Then
k_low = k - 1
f_high = f
f_low = p
Endif

p = f
Next

m = (f_high - f_low)

k_zero = -f_low / m + k_low

xu = (k_zero + 0.5) * g
yu = g * Sqr((g / m) ^ 2 - 0.25)

Print m, xu, yu

' Slope is calculated in respect to k not x.
' (0.7, -0.004165145)
' (0.9, 0.009348566)
'
' m = (0.009348566 - -0.004165145) / 2
'
' m = 0.0067568555

Print 0.1 * Sqr((0.1 / 0.0067568555) ^ 2 - 0.25)



So here is the output. Notice, I do a calculation of the slope and zero crossing using just the two nearest values. They results are well within


0       -0.056910303472078      -0.043423795
1       -0.050952192617567      -0.039331481
2       -0.04416098469313       -0.035474273
3       -0.036518307009086      -0.025309761
4       -0.028061635538779      -0.019823501
5       -0.018899933629743      -0.017748271
6       -0.009219103344785      -0.010301581
7       0.000729069878335       -0.004165145
8       0.010655748886048       0.002257333
9       0.020275154761491       0.009348566
10      0.02934371319808        0.008298607
11      0.037686506689843       0.022343171
12      0.045205674043678       0.035716244
13      0.05187301452176        0.043296065
14      0.057713482721506       0.039169621
15      0.06278645770196        0.042370574
16      0.067169358140174       0.041379915
17      0.070945504755915       0.045609152
18      0.074196271508027       0.079869062
19      0.076996687578137       0.064377786
0.009948173223119       0.742671319025281       1.00396538599696
1.47913352351712



With noiseless synthetic data, with the actual user firmly at ( 0.7427, 1.0 ) yields a result of (0.742671319025281 , 1.00396538599696) from just the two points surrounding the zero crossing.

With your values, a rough similar calculation for y is 1.48. There is something wrong with your data. (Shifting by a index isn't the whole issue)

I suggest you add a plot of the theoretical distance difference given using your test (xu,yu) so you can compare what your data should be to what you are getting.

• Hi Cedron, Thank you! You method can obtain the distance from the antenna to the user indeed. But you made a assumption that there was an antenna with $n^*$ (you defined it) at zero crossing point. Actually, it is not a truth, I cannot promise it will happen. Moreover, actually, we can also use hyperbolic positioning method to do this job, since we know the distance differences.
– Land
Jun 27 '19 at 17:09
• My question is how to solve this problem with higher precision. I used hyperbolic method combining with least square. It works, but the result is not satisfied. Why you think your method is good?
– Land
Jun 27 '19 at 17:14
• @Land, see my followup. Jun 27 '19 at 17:18
• I got it! Thanks again. I will check it later~
– Land
Jun 27 '19 at 17:41
• @Land, You're welcome. I'm curious about how it turns out so perhaps you could email me a dataset and your results to cedron at exede dot net. Jun 27 '19 at 17:55