Available online at www.sciencedirect.

com

ScienceDirect
Procedia Computer Science 87 (2016) 184 – 189

4th International Conference on Recent Trends in Computer Science and Engineering

Unknown radio source localization based on a modified closed form

Abstract

There have been huge advances in the development of positioning applications after the success of GPS. Accurate positioning
capability of a radio source is in great demand in the fields of medicine, defence, automation etc. Especially in the Indian
subcontinent, localization of an unknown enemy Radio Source such as an enemy radar system, tracking of Unmanned Aerial
Vehicle (UAV) etc are essential capabilities for the defence wing. The time difference of arrival (TDOA) technique used for
location determination makes use of the method of hyperbolic multilateration. Position accuracy is affected by various factors
such as choice of number of sensors, measurement noise, algorithm employed for positioning and sensor geometry. A number of
positioning algorithms are available for this purpose. These include iterative algorithms, evolutionary algorithms and many others
that are not particularly feasible as the run time of the hardwired code is a major constraint in real time applications. A closed
form algorithm proposed in the literature achieves considerable speed in implementation but falters in the resolution of the
altitudinal estimate. Hence, a modified algorithm is proposed in this paper that resolves the altitude of the unknown radio source.
For better understanding, an example of localizing an unknown radio source using the proposed algorithm is explained.

Keywords:Radio Source Localization, TDOA, Sensor geometry, Direct Solution.

1. Introduction

The precise location of any fixed or moving object/radiating source is the primary concern of a number of fields
like medicine, automation, Electronic Warfare etc. In order to locate moving sources, a number of position location
techniques are employed and hyperbolic position location technique1 is one among them. It is also known as

* Corresponding author. Tel.: +91-9705817692

1877-0509 © 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
(http://creativecommons.org/licenses/by-nc-nd/4.0/).
Peer-review under responsibility of the Organizing Committee of ICRTCSE 2016
doi:10.1016/j.procs.2016.05.146
 D. Eswara Chaitanya and G. Sasibhushana Rao / Procedia Computer Science 87 (2016) 184 – 189 185

Hyperbolic Multilateration or time difference of arrival (TDOA)2,3 position determination method. The TDOA based
positioning method is hugely popular because of its relatively high accuracy despite the fact that it does not require
information about the transmitted signal. However, a number of choices with respect to design are to be made during
implementation of any positioning technique. The first is the choice of arrangement or deployment of sensors i.e.
sensor geometry. The second is the number of sensors to be deployed. Further, the choice of reference sensor is also
significant. However, a major design issue is the positioning algorithm to be used or developed.
This paper is divided into 6 sections. The second section introduces the method of TDOA positioning. The third
section details the proposed algorithm for hyperbolic multilateration. The working methodology used for carrying
out the required analysis is presented in section 4. Section 5 details the results obtained. In section 6, the conclusions
pertaining to the discussion that follows are presented.

2. TDOA positioning technique

Among the various positioning technologies available, Hyperbolic Multilateration (TDOA positioning) is most
widely used for Automatic Source/Object Location. Hyperbolic position location estimation is accomplished in two
stages4. The first stage involves estimation of the time difference of arrival (TDOA) between receivers through the
use of time delay estimation techniques. The estimated TDOAs are then transformed into range difference
measurements between base stations, resulting in a set of nonlinear hyperbolic range difference equations. The
second stage utilizes efficient algorithms to produce an unambiguous solution to these nonlinear hyperbolic
equations. The solution produced by these algorithms result in the estimated position location of the source.
In order to solve for the unknown source position in the space, three coordinates i.e. x, y and z are required to be
determined with the help of four receivers that could be either fixed or mobile. In this paper, the location of the four
fixed receivers i, j, k and l has been taken as and respectively and by
considering the speed of EM waves as ‘c’, the distances of the receivers from the unknown source will be as
follows:

The above equations are a set of Time of Arrival (TOA) values multiplied by the velocity of light, c to form the
corresponding range difference values. They can be combined so as to form expressions for the corresponding
Range difference of arrival (RDOA = TDOA*c) equations as follows:-

where
Each TDOA equation will represent a hyperboloid (as shown in Fig. 1) indicating the presence of the target
anywhere on this hyperboloid. The above equation is nonlinear and can be solved using a closed-form solution or
can be linearised and approximated to 1st order Taylor’s series5. A major advantage of this method is that it does not
require knowledge of the transmit time from the source, as do the Time of Arrival (TOA) method which is the
principle behind the development of the Global Positioning System (GPS). Consequently, strict clock
synchronization between the source and receiver is not required. As a result, hyperbolic position location techniques
186 D. Eswara Chaitanya and G. Sasibhushana Rao / Procedia Computer Science 87 (2016) 184 – 189

do not require additional hardware or software implementation within the mobile unit.
However, clock synchronization is required of all receivers used for the position location estimate. Furthermore,
unlike TOA methods, the hyperbolic position location method is able to reduce or eliminate common errors
experienced at all receivers due to the channel.

F F

Figure 1 Hyperboloid with its two foci

3. Proposed algorithm

Ezzat’s approach 6 gives a unique solution to the 3D problem from the TDOA perspective. It does not depend
upon range data. It is necessary to know the time of transmission and the time of arrival to get the amount of time
travelled from the transmitter to the receiver. For the most part, it is impossible to know the time of transmission,
which can be defined as . Many 3D solutions currently available are based on range data 7-9. Some other solutions
in the literature are in 2D and can’t be extended to 3D10. The TDOA method is the only technique that can be used
without the range data. Thus, even without , it is possible to find the location of the emitter. The closed-form
solution presented does not require the calculation of range data and does not depend on the availability of any
information other than the times of arrival. The basic form of time of arrival equation is as follows

where
is the time of arrival at receiver i ,
is the distance between the emitter and the receiver,
c is the speed of light.
is the time of the transmission
Two or more receivers are needed to be able to calculate the TDOA as mentioned before. When this condition is
satisfied, it is possible to eliminate from any pair of two equations, which results in the TDOA equation

A propagation mode between any two points in which the path of the signal is not a straight line will be
mathematically equivalent to propagation along a straight line but with a velocity that is less than c, as the time of
arrival is important. The TDOA equation for the case in which the path of the signal is nonlinear will be written as
follows after adding the path delay:

( )= =

where,
represents path delay coefficients whose value is less than or equal to 1. α is one when there is no path effect on
 D. Eswara Chaitanya and G. Sasibhushana Rao / Procedia Computer Science 87 (2016) 184 – 189 187

the propagating signal like in the case where the signal propagates through air. In this paper, all the path delay
coefficients are assumed to be one. A minimum of five receivers are required for position computation. This
approach involves mathematics of substitution and direct computation by elimination which finally result in
equations of the following form.

(1)

where

The remaining coefficients can also be determined from similar equations. Equations in (1) can be
expressed as AX = B and can be solved using least square estimation as shown

However, the above approach doesn’t obtain good resolution in the altitudinal estimate. This is of major concern.
Hence, the above approach is modified accordingly to obtain unknown source location estimate in three dimensions.
The TDOA location in three dimensions can be derived/extended from the solution obtained in 2D. Now that the
emitter can be located in a plane with the x and y coordinates available, it is the altitude that has to be estimated. The
maximum possible search space with respect to the altitude is usually pre decided.
In the proposed algorithm, the altitude is estimated by a search process in which the altitude is varied in steps of a
step size which can be pre-determined considering various parameters such as accuracy of the estimate required,
computation time etc. For each value of z considered, the sum of squares of residuals obtained by the difference of
true and calculated rdoas is determined. The ‘z’ coordinate estimate for which the lowest value is obtained is chosen
to be the altitude of the emitter.

4. Methodology

In order to analyse the performance of the proposed modified closed form algorithm with regards efficacy and
convergence, the following methodology is used. The entire coding process required for this work is done in
MATLAB. The first assumption is to randomly choose the location of the unknown source. Here, two such locations
are chosen at random. This approach requires no initial guess. The number of receivers used is fixed at 5. The
sensors are assumed to be arranged in Pentagon configuration.
For the given sensor configuration, the RDOA values were calculated with respect to the pre decided source
location. These values were then input to the code. However, since we are not working with real time data, errors
are introduced into the TDOA values by the addition of Gaussian noise. These errors reflect in the RDOA values in
terms of range difference errors. The estimated source position is then estimated for all the configurations and
related observations are made. The measured parameters are location coordinates of the unknown source in
Cartesian coordinate system i.e. x, y and z. However, since only the x and y estimates obtained from the closed form
solution are close to the true values, the altitude is now estimated using the following procedure.
188 D. Eswara Chaitanya and G. Sasibhushana Rao / Procedia Computer Science 87 (2016) 184 – 189

The height of the source is estimated from a search method that minimizes the sum of squares of differences in
observed and calculated estimates. Since, the x-y planar location of the unknown source is now available, what
remains is the height of the source from the reference zero level. Depending on the possible unknown sources that
are to be identified, an estimate of the maximum height can be determined. The application for which the algorithm
is intended will decide the accuracy of altitudinal estimate required. The maximum possible height of the unknown
source is divided into steps of a pre decided step size. Since the observed RDOA values are available, at each step
(altitudinal value), a new set of RDOAs are calculated. That value of altitudinal choice which minimizes the sum of
squares of the differences in observed and calculated RDOAs is our height estimate. This above process can be
regarded as minimization of the following function OF (Optimization function)

Where (x, y, z) is the estimate, (xref, yref, zref) is the reference sensor and (xi, yi, zi) are the other sensors.

5. Results and discussion

Two different unknown source locations are used in this section. The simulation constraints used in evaluating
the proposed algorithm are given below.
Sensor Coordinates in meters:
X Coordinates = [0, -19021, -11756, 11756, 19021]
Y Coordinates = [-20000, -6180, 16180, 16180, -6180]
Z Coordinates = [25, 35, 40, 30, 45]
Reference Sensor Coordinates = [0, -20000, 25]
Assumed Source Location 1 = [5000, 15000, 7000]
Assumed Source Location 2 = [20000, -15000, 7000]
Step size (for resolution in ‘z’) = 1000m
The noise to be introduced in the TDOA measurements is a random choice of either 2ns or 4ns. The height of the
source is however fixed at 7kms. Table 1 lists the errors in location estimate of assumed unknown source 1. The
variation can be observed in the altitudinal estimate of the proposed algorithm. Similarly, Table 2 lists the errors in
location estimate of assumed unknown source 2. From Table 1 and 2, it is evident that the error in z is zero since we
have opted for a true value of ‘z’ which is a multiple of 1000 (7000 in our example). Any other value of source
height, say 7250m would indicate an error of 250m for each TDOA error combination since our assumed step size
was 1000m. Similarly, if the assumed true value of source height is 7700m, the error indicated in the results would
have been 200m and 300m if the step size is 500m and 1000m respectively.

Table. 1 Performance analysis of proposed algorithm for Assumed Unknown Source Location 1
Error in Z Error in Z
Error in Error in Error in Error in
Error in X Error in Y (mts) (mts)
TDOA1 TDOA2 TDOA3 TDOA4
(mts) (mts) (Direct (Proposed
(ns) (ns) (ns) (ns)
soln) algorithm)
2 2 2 2 2.88 8.49 4163.45 0
2 2 2 4 2.87 9.36 5049.19 0
2 2 4 2 3.42 10.10 4519.66 0
2 2 4 4 3.41 10.98 5405.28 0
2 4 2 2 0.97 2.61 2478.45 0
2 4 2 4 0.97 3.48 3364.58 0
2 4 4 2 1.51 4.23 2835.23 0
4 2 2 2 7.14 19.47 7879.73 0
4 2 2 4 7.13 20.34 8764.80 0
 D. Eswara Chaitanya and G. Sasibhushana Rao / Procedia Computer Science 87 (2016) 184 – 189 189

Table. 2 Performance analysis of proposed algorithm for Assumed Unknown Source Location 2
Error in Z
Error in Error in Error in Error in Error in Z
Error in X Error in Y (mts)
TDOA1 TDOA2 TDOA3 TDOA4 (mts)
(mts) (mts) (Proposed
(ns) (ns) (ns) (ns) (Direct soln)
algorithm)
2 2 2 2 3.33 2.49 2060.07 0
2 2 2 4 3.62 2.72 2422.43 0
2 2 4 2 7.38 5.10 2919.25 0
2 2 4 4 7.67 5.33 3281.79 0
2 4 2 2 6.07 5.16 1283.80 0
2 4 2 4 5.78 4.93 921.89 0
2 4 4 2 2.03 2.56 425.38 0
4 2 2 2 11.44 9.58 5883 0
4 2 2 4 11.73 9.81 6245.78 0

6. Conclusions

This paper presented the TDOA method of obtaining the position fix of any unknown source. The direct solution
approach available in literature was presented and its disadvantage in obtaining the altitudinal estimate was
illustrated with two clear examples. The main advantage of the direct solution approach lies in its ability to converge
to a solution in a single iteration. The proposed algorithm tries to keep the advantage of this approach intact while
trying to obtain a proper altitudinal estimate of the unknown radio source. Though the speed of the closed form
approach was sacrificed to an extent and the estimation of unknown source height requires more than a single
iteration, the proposed work is of great use in applications that involve accurate 3D estimate of the unknown source.
The trade-off between speed of implementation and accuracy is for the designer to choose. The number of iterations
required by the proposed algorithm to estimate the height can be reduced by a proper choice of the step size
depending on the altitudinal resolution required.

References

1. Seyed A. (Reza) Zekavat and R.Michael Buehrer, “Hand book of Position Location-Theory, Practice, and Advances”, IEEE Press, John
Wiley & Sons, Inc., Publications, New Jersey-54, Edition- 2012.
2. Gaarder, N. T., “On estimating the location of a signal source.”, IEEE Transactions on Information Theory, IT-15, 5 (1969)
3. Torrieri, D. J., “Statistical theory of passive location systems.”, IEEE Transactions on Aerospace and Electronic Systems, AES-20, 2 (1984).
4. D.Eswara Chaitanya, M.N.V.S.S.Kumar, G.Sasibhushana Rao and Rajkumar Goswami, “Convergence Issues of Taylor Series Method in
Determining Unknown Target Location Using Hyperbolic Multilateration”, ICSEMR 2014, ISBN:978-1-4799-7613-3/14/IEEE-2014.
5. G. Shen, R. Zetik, and R. Thoma, “Performance comparison of toa and tdoa based location estimation algorithms in los environment”, In
Proceedings of Positioning, Navigation and Communication, WPNC 2008, pages 71 -78, IEEE, 2008
6. Ezzat G.Bakhoum, “Closed-Form Solution of Hyperbolic Geolocation Equations”, IEEE Transactions on Aerospace and Electronic Systems
Vol.42, No.4, Oct-2006.
7. Schau, H. C., and Robinson, A. Z., “Passive source localization employing intersecting spherical surfaces from time-of-arrival differences.”,
IEEE Transactions on Acoustics, Speech and SignalProcessing, ASSP-35, 8 (1987).
8. Smith, J. O., and Abel, J. S., “Closed-form least squares source location estimation from range-difference measurements.” IEEE Transactions
on Acoustics, Speech and SignalProcessing, ASSP-35, 12 (1987).
9. Chan, Y. T., and Ho, K. C., “A simple and efficient estimator for hyperbolic location.”, IEEE Trans. on Signal Processing, V. 42, 8, 1994.
10. Schmidt, R. O. “A new approach to geometry of range difference location”, IEEE Transactions on Aerospace and Electronic Systems, AES-
8, 6 (1972).