TULIP Trilateration Algorithm
minRTT = propagation delay + extra delay (due to extra circular routes , congestion and router delays)
?T measured= ?t + ?t0
(Pseudo-distance)
PD = ?T measured . ?
(Actual distance)
D = ?T . ?
PD = (?T + ?T0). ?
PD = D + ?T0 .c .................................(1)
D = actual distance from the landmark.
C = speed of light
? = X(c) i.e. Speed of digital info in fiber optic cable
X = factor of c with which digital info travels in fiber optic cable.
?T = actual propagation delay along the greater circle router/paths.
?T0 = the extra delay causing overestimation.
PD = pseudo distance
Graphically,
H: host
L1: Landmark 1
L2: landmark 2
L3: landmark 3
Using distance farmula:
D1= ?(XL1- Xh)^2 + (YL1 - YH)^2 ............................................. (2)
FROM (1) & (2)
PD1= (?(XL1 - XH )^2 + (YL1 - YH)^2) + ?T0 . ? .................... (A)
Similarly for other 2 landmarks:
PD2= (?(XL2 - XH )^2 + (YL2 - YH)^2) + ?t0 . ? .................... (B)
PD3= (?(XL3 - XH )^2 + (YL3 - YH)^2) + ?t0 . ? .....................(C)
We need to linearize (A), (B) & (C) to solve them
Using Taylor Series:
f(x0) . ( x- x0) f ' (x0) . (x - x0)
f( x ) = f (x0) + -------------- + --------------------
1! 2!
Considering the simplified part first
f ( x ) = f (x0) + f(x0)(x - x0)
put (x-x0) = ?x
f ( x ) = f (x0) + f' (x0) delta ( x ) .......................(3)
Hence to compute the original value of X an arbitrary value x0 is required, this is done by simple trilateration
We know that:
Hx = X est + delta ( x )
Hy = Y est + delta ( y )
Also
Est Di = (Lhi - Xest) + (Hy - Yest) .......................(4)
From (3) and (4)
d(EstDi) . delta ( x ) d(EstDi) . delta( y )
PDi = Est Di + -------------- + -----------------
dX dY
After carrying out partial differentiation
(Xest - Xli) (Yest - Yi)
ODi = Est Di + ------------. delta ( x ) + ---------------- delta ( y) + c. delta(To)
dX dY
Now we need to solve ( x , y , ?to)
Solution from (4) is put in eq(D) to get new estimations.
Hx,Hy becomes the new estimated position