Equations
EquationsWorking Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein, head of Europe’s Galileo Operations and Evolution.
Radio frequency interference (RFI) represents a serious threat for the satellite industry. In satellite communications (SATCOM), though a small amount of satellite capacity is affected at any time by interference, 85–90 percent of the SATCOM customer issues are related to RFI (see M. Coleman in the Additional Resources section near the end of this article). According to the Open 2015 SA Users Meeting General Forum, this represents the single most important operational problem affecting customer service on geostationary satellites.
The majority of interference cases still come down to human error or equipment failure, with intentional interference (jamming) counting for less than five percent of interference cases. However, this is increasing dramatically. Detecting and localizing the source of RFI is becoming a priority in today’s satellite industry generally and in the GNSS community in particular. Indeed, localization provides the required essential information to the authorities on the location of the RFI source and the time of such interference events, enabling them to take appropriate actions to eliminate such interference sources and prevent them from re-appearing.
This article discusses the theoretical background on interference localization, focusing on the single interferer case. The traditional approach to localize the source of an interference signal requires two steps:
1) generation of location measurements: first the interference signal must be processed in order to extract some features providing information on the interferer state (position and, possibly, velocity);
2) localization of the interference source: multiple collected measurements (generated simultaneously and/or at different time instants) are used as the inputs of a localization algorithm in order to generate an estimate of the interferer state.
Both steps are described in detail throughout the article, providing examples of location measurement types and of techniques to estimate such location measurements and perform the final localization. A second article in this Working Papers series will appear in a subsequent issue of Inside GNSS and discuss the application of the techniques described here to GNSS interference localization. That article will present simulation results for both the ground and space GNSS interference localization architectures.
As an illustrative example, the left side of Figure 1 depicts a set of location measurements, represented by black crosses, and the associated interferer location estimate, represented by a red point. In Figure 1, a single location measurement coincides with a point in the space, allowing us to simplify the representation; however, in general a location measurement defines a loci of points in the space, which we will discuss in more detail later in this article.
If multiple interferers are present and must be localized, an additional intermediate step is required: different location measurements must be assigned to different interferers, such that different subsets of the collected measurements are exploited to localize different interferers. The right side of Figure 1 illustrates this situation in which the total set of measurements is divided into two subsets, and two independent localizations are performed exploiting the two subsets of measurements.
There are many ways of splitting a set of n measurements into two subsets (precisely 2n–1 including the possibility of assigning all measurements to a single interferer). The situation gets worse if the number of interferers is larger, and even worse if the number is unknown. Multiple-hypothesis tracking techniques jointly perform the assignation step (including the interferer number estimate, in cases where it is unknown) and the localization step, keeping in memory multiple assignation possibilities (named “hypotheses”). This results in multiple possibilities for the estimated number of interferers and the estimated location for each of them. We will not treat the case of multiple interferer localization here, but interested readers may learn more in the article by L. D. Stone et alia (Additional Resources).
Location Measurement Generation
The localization of an interferer requires the extraction of features from the inference signal providing information on the state (position and, possibly, velocity) of the interferer. We will now present a series of location-dependent measurements that can be obtained from an interfering signal.
A time of arrival (ToA) measurement represents the time a signal takes to travel from the transmitting source to the receiver (i.e., the propagation time), and can be written as:
Equation (1) (See inset photo, above right, for all equations)
where is the transmitter-to-receiver distance, which depends on the transmitter position (x,y,z); c is the speed of light, and ε represents a possible measurement error.
All the points that are equidistant from the receiver are associated with the same ToA value as shown in the upper-left sub-figure of Figure 2, where the blue cross represents the transmitter position, the red triangle represents the receiver position, and the green circle is the ToA locus of points assuming ε = 0. Because the ToA requires an accurate knowledge of the time at which the signal is transmitted, in the context of interferer localization we can generally not estimate such a measurement unless the signal itself contains a timing feature.
A time difference of arrival (TDoA) measurement represents the difference of the time instants at which a signal is received at two different receivers, and can be written as:
Equation (2)
where and are the distances from the transmitter to the first and second receivers, respectively, which depend on the transmitter position (x,y,z); c is the speed of light, and ε represents a possible measurement error.
All the points such that the difference between the distances to each receiver is constant are associated with the same TDoA value. Hence, the locus of points satisfying a given TDoA measurement is a hyperbola in a two-dimensional space and a hyperboloid in a 3D space. The upper-right sub-figure of Figure 2 illustrates this measurement, where the blue cross is the transmitter position, the red triangles are the receiver positions, and the green circle is the TDoA locus of points assuming ε = 0 (For details, see the article by Y. T. Chan and K. C. Ho in Additional Resources.)
A frequency of arrival (FoA) measurement represents the frequency shift (i.e., the Doppler) at which a signal is received by a receiver and can be written as:
Equation (3)
where v(x,y,z) is the relative speed vector between the receiver and the transmitter, α(x,y,z) is the angle between v(x,y,z) and the vector connecting the receiver to the transmitter, f0 is the carrier frequency, c is the speed of light, and ε represents a possible measurement error.
In the case where the transmitter is static, the vector v(x,y,z) does not depend on the transmitter position (x,y,z), and all the points with constant angle α(x,y,z) are associated with the same FoA value. Hence, in this case the locus of points satisfying a given FoA measurement is represented by two half-lines departing from the receiver position. It is symmetrical with respect to the receiver velocity in a 2D space and by a cone whose apex is the receiver position and axis is the receiver velocity in a 3D space. In the case where ε = 0 such a curve crosses the actual position of the transmitter.
The lower-left sub-figure of Figure 2 shows this situation, where the blue cross is the transmitter position, the red triangle is the receiver position, the black arrow is the receiver velocity, and the yellow half-lines represent the TDoA locus of points, assuming ε = 0. Because the FoA requires an accurate knowledge of the signal carrier frequency (otherwise the Doppler cannot be subtracted from the received frequency), in the context of interferer localization we generally cannot estimate such a measurement.
A frequency difference of arrival (FDoA) measurement represents the difference between the frequency shifts (i.e., the Doppler) at which a signal is received by two different receivers and can be written as:
Equation (4)
where v1(x,y,z) and v2(x,y,z) are the relative speed vectors between the two receivers and the transmitter, α1(x,y,z) is the angle between v1(x,y,z) and the vector connecting the first receiver to the transmitter (analogous to α2(x,y,z), f0 is the carrier frequency, c is the speed of light, and ε represents a possible measurement error. In the case of a static transmitter, the vectors v1(x,y,z) and v2(x,y,z) do not depend on the transmitter position (x,y,z).
The locus of points of an FDoA measurement is not a standard geometric shape as seen in brown in the lower-right sub-figure of Figure 2 assuming ε = 0, where the blue cross is the transmitter position, the red triangles are the receiver positions, and the black arrows are the receiver velocities. Note that the exploitation of an FDoA measurement requires the knowledge of the carrier frequency (f0 appears in the above equation); however, a small relative error on the carrier frequency estimation causes only a small perturbation of the locus of points.
A received signal strength (RSS) measurement represents the attenuation associated with the signal propagation from the transmitter to the receiver and can be written as:
RSS = 10nplog10(ρ(x,y,z)) + ε (5)
where ρ(x,y,z) is the transmitter-to-receiver distance, which depends on the transmitter position (x,y,z), np is the path loss factor, and ε represents a possible measurement error.
All the points that are equidistant from the receiver are ascribed the same RSS value. Hence, similarly to the ToA case, the locus of points satisfying a given RSS measurement is a circle in a 2D space (as shown by the upper-left sub-figure of Figure 2), and a sphere in a 3D space. Because the RSS requires an accurate knowledge of the power at which the signal is transmitted, in the context of interferer localization we generally cannot estimate such a measurement.
A received signal strength difference (RSSD) measurement represents the difference of the attenuations associated with the signal propagation from the transmitter to two different receivers, and can be written as:
Equation (6)
where ρ1(x,y,z) and ρ2(x,y,z) are the distances from the transmitter to the first and second receivers, respectively, which depend on the transmitter position (x,y,z); np is the path loss factor, and ε represents a possible measurement error.
All the points whose ratio between the distances to each receiver is constant are associated with the same TDoA value. Hence, the locus of points satisfying a given RSSD measurement form a circle in a 2D space (a sphere in a 3D space), centered along the line connecting the two receivers and including only one of the two receivers, the one closer to the transmitter. If the transmitter is equidistant to the receivers, such a circle (sphere) degenerates to the line (plane) that is the perpendicular bisector to the segment connecting the two receivers. The RSSD requires an accurate knowledge of the path loss factor np. This factor is impacted by effects that are difficult to predict and compensate for, such as shadowing and multipath.
An angle of arrival (AoA) measurement represents the angle of the vector connecting a receiver to the transmitter with respect to a reference direction (in a 2D or 3D space) or a reference system (3D space). Denoting such an angle as α(x,y,z), which is a function of the transmitter position (x,y,z), the AoA measurement can be written as:
AoA = α(x,y,z) + ε (7)
Where ε represents a possible measurement error.
If the AoA is computed with respect to a reference direction, the AoA locus of points is equivalent to the FoA locus of points: two half lines in a 2D space (as shown by in the lower-left sub-figure of Figure 2, where the black arrow represents in this case the reference direction), or a cone in a 3D space. If the AoA is computed with respect to a reference Cartesian system in a 3D space, then α(x,y,z) is actually a pair of angles, representing the azimuth and elevation with respect to the Cartesian system. In this case, the locus of points is a half-line departing from the reference position, or two half-lines if the sign of the elevation angle is uncertain.
Choosing and Generating the Measurement Types
In the context of interferer localization, because the information about the state of the signal at the transmitter is in general not available (e.g., transmitting time, transmitting power, carrier frequency), the most promising measurement types are the TDoA, FDoA, and AoA. We will now address possible signal processing to estimate such measurements.
A single TDoA measurement and a single FDoA measurement associated with a transmitter and a pair of receivers can be obtained by computing the cross ambiguity function (CAF) χs,g(Δt, Δf) between the signals s(t) and g(t) received by the two antennas during a common acquisition time interval [t1, t1 + T] (as discussed in the paper by G. D. Hartwell in Additional Resources):
Equation (8)
The values Δt* and Δf* at which χs,g(Δt, Δf) is maximized represent the estimated TDoA and FDoA measurements, respectively. For a given value of Δf, the CAF is equivalent to a correlation between the signal s(t) shifted in frequency by an amount Δf and the signal g(t). As this correlation is in general performed after the signals are acquired and sampled, in practice the integral is actually a sum:
Equation (9)
where Ts is the sampling time, n1Ts is the beginning of the acquisition time interval, which corresponds to the time at which the TDoA measurement is evaluated, and K ⋅ Ts is the length of the acquisition time interval.
The foregoing function must be computed for a range of possible time and frequency shifts. For example, the TDoA cannot be larger, in absolute value, than the time a signal takes to travel from one antenna to the other, i.e., |TDoA| ≤ d/c, where d is the distance between the two antennas and c is the speed of light. The CAF function can be fitted or interpolated in the time domain in order to estimate the CAF peak with a time resolution that is better than the sampling time Ts.
We can obtain an AoA measurement in multiple ways. The most intuitive approach consists of taking and comparing amplitude measurements at different angles. This can either be performed by a single moving antenna scanning sequentially different angles, or by a set of fixed antennas that are oriented toward different angles. The latter approach is often referred to as amplitude comparison monopulse (ACM).
Figure 3 (left side) presents a possible planar architecture of the ACM technique, which is taken from A. De Martino (see Additional Resources). In this 2D example, four antennas are employed to estimate the AoA of a signal. Each antenna faces toward a specific quadrant. This means that the angle between the pointing directions of adjacent antennas, often referred to as the “squint angle,” is 90 degrees. In this example, 90 degrees is also the three-decibel beamwidth of each antenna pattern, meaning that at least one antenna receives the signal within the three-decibel beamwidth of the main lobe. As a consequence, this antenna architecture covers a span of 360 degrees.
The AoA of the signal lies in the angular area between the antenna receiving the largest power and the antenna receiving the second largest power. This AoA can be obtained more accurately by computing the difference between these two received powers, and normalizing the results with respect to the sum of the two powers. If the antenna patterns and squint angle are properly designed, such a normalized difference is about linear with respect to the AoA (at least in the 90-degree angular span between the two antenna pointing directions). Hence, the AoA value can be unequivocally retrieved from the normalized difference. Smaller squint angles allow for achieving better accuracies, at the cost of requiring a larger number of antennas to cover the required angular span.
A similar approach can be adopted for a 3D space. In this case, in order to find both the azimuth and elevation angles with respect to an x-y-z Cartesian system, the antenna pointing directions must not lie in the same plane. The illustration on the right-hand side of Figure 3 shows a four-antenna implementation of the ACM technique to estimate the AoA of a signal coming from below of an airplane. In this representation, the four antennas are located at the same point and oriented to four different angles covering a limited angular span. Note that antenna colocation is not a requirement, in particular if the interferer is located far below the airplane.
We can also derive the AoA from a TDoA measurement if the interferer is much farther away than the distance d separating the two receivers. Indeed, under this assumption the interferer signal can be approximated by a planar wave, which arrives at a certain angle with respect to the segment connecting the two receivers, and such an angle unequivocally defines the extra path that the signal must cover to reach the farther antenna.
Another way to realize that the TDoA is linked to the AoA for a far transmitter is by considering the fact that the hyperbola (hyperboloid), defining the locus of points of a TDoA measurement, has a linear (conical) asymptote, which corresponds to the locus of points of an AoA measurement. Mathematically, the AoA and the TDoA are linked by:
Equation (10)
Finally, there exist different techniques with which to exploit the phase of a narrowband signal transmitted by a far source and received by multiple receivers. This approach is similar in philosophy to the TDoA approach just described. Indeed, for a continuous signal (which is on the extreme of the narrowband signal class) a one-to-one correspondence exists between the differential time and the differential phase at which a signal is received at two receivers, assuming that the receiver separation is not larger than half a wavelength.
Among all the techniques exploiting the different phases of the signals acquired by multiple receivers, the most famous and widely adopted one is probably the MUltiple SIgnal Classification (MUSIC) technique (described in M. Hajian et alia). MUSIC was devised as a form of super-resolution direction-finding technique for processing the signals received by an antenna array of M antenna elements, to obtain estimates of the AoA of multiple signal components. It is in a family of processes called subspace-based processing and is based on an eigen-decomposition of the covariance matrix derived from data samples to obtain two orthogonal matrices, which represent the signal-subspace and the noise-subspace.
The MUSIC algorithm can be summarized as follows:
Step 1: Collect input samples x(k) at multiple time instants k = 1, … , N and estimate the input covariance matrix
Equation (11)
Step 2: Perform eigen-decomposition of R̂xx in order to get the M eigenvalues λ1 ≥ λ2 ≥ … ≥ λM and the M associated eigenvectors ν1, ν2 … νM .
Step 3: Estimate the number of incident signals D̂ = M − K, where K is ideally the multiplicity of the smallest eigenvalue.
In practice, because R̂xx is estimated through a finite number of samples and therefore is affected by estimation errors, the eigenvalues will all be different. In this case K can be estimated as the number of small eigenvalues that are closely spaced.
Step 4: For each possible pair of angles of arrival (θ, ϕ), representing azimuth and elevation with respect to the reference Cartesian system, compute the MUSIC spectrum:
Equation (12)
Equation (13)
Equation (14)
is the phase shift observed by the i-th antenna with respect to the origin of the reference system, for an incoming wave with frequency f and incident angles (θ, ϕ).
Step 5: Find the D̂ largest peaks of P̂MUSIC (θ) to obtain the estimates of the AoA of the incident signals.
A common antenna arrangement for the MUSIC algorithm is the uniform circular array geometry in which the M antennas are placed along a circumference at equispaced distances. Such a disposition is shown for M = 5 antennas on the left side of Figure 4, and in this case the antennas represent the vertex of a pentagon.
It is important to note that, for a planar array, the MUSIC spectrum is symmetric with respect to the plane in which the antennas lie. As a consequence, a pair of peaks appears for each incident signal component: one is associated with the actual direction of arrival, while the other is a “ghost peak” (see right side of Figure 3), which must be somehow discarded.
In fact, to remove such ambiguity, the planar array should be placed such that no signal can reach the array from one of the two sub-spaces defined by the plane in which the antennas lie. In this case, we can limit the search for the MUSIC spectrum peaks to only the relevant sub-space and more specifically to the relevant angles coming from the relevant subspace. (By limiting the field of view, we can also limit the angles at which we need to look.)
Localization
Figure 2 shows that a single location-dependent measurement does not allow for accurately localizing an interferer: all the points belonging to the loci of points of the measurement represent possible positions of the interferer. In order to resolve such ambiguity multiple location measurements are required. Such measurements may be collected simultaneously (e.g., N receivers collecting N-1 TDoA measurements), or sequentially at different instants (e.g., two receivers collecting a single TDoA every 10 seconds), or with both approaches (e.g., N receivers collecting N-1 TDoA measurements every second). Also, they may be of the same type or of different types (e.g., N receivers collecting N-1 TDoA and N-1 FDoA measurements every second).
Once a set of measurements is available, the goal of a localization technique is to find a point in the space that agrees with the observed measurements, with said point representing the estimate of the transmitter position. Geometrically, this is equivalent to finding the intersection of the loci of points associated with the measurements.
The left side of Figure 5 shows, in a unique picture, the loci of points that Figure 2 shows in different sub-figures. The ToA and FoA measurements refer only to the first receiver (two ToA and two FoA measurements could be taken by two receivers). In this specific scenario, all the loci intersect exactly at two points: one represents the actual interferer position, the other one is a point that is symmetric to the interferer position with respect to the x-axis. This symmetry occurs because both segments connecting the two receivers and the receiver velocities lie along the x-axis.
Unless prior knowledge on the interferer position allows for excluding all the subspace y < 0, this example shows the necessity of having a “heterogeneous geometry” (e.g., receivers not aligned in space, velocity vectors not aligned with respect to the segment connecting the receivers, and so forth) in order to avoid symmetric scenarios that may lead to ambiguities.
A fundamental point missing in the above discussion is that measurements are in general affected by errors. This means that the loci of points associated with the noisy measurements do not pass exactly through the actual interferer position, and they do not cross exactly on the same point.
This situation is represented on the right side of Figure 5. In this case the localization technique must find the point of the space that “best fits” the observed measurements. This concept of “fitting” is usually expressed, in mathematical terms, through a least-squares problem, which tries to minimize the sum of the squares of the distances of the loci of points from the estimated position. Geometrically, this means finding a point in the space as close as possible to all the loci.
With more measurements available, the more precise the solution of such a least-squares problem will become. Moreover, if the accuracies associated with the collected measurements are available (e.g., if TDoA and FDoA measurements are affected by i.i.d. Gaussian errors with standard deviations σTDoA and σFDoA), we can weight each measurement appropriately by considering how much the loci of points of that measurement can oscillate around the actual interferer position. This requires rescaling each measurement type by an appropriate geometric factor and solving a weighted least-squares problem.
Multiple ad hoc solutions have been proposed and studied in the literature to aggregate specific types of measurements. See, for example, as cited in the Additional Resources section, M. Hajian et alia considered a two-stage maximum likelihood technique to aggregate TDoA measurements, I. Guvenc et alia studied an approximate maximum likelihood technique for TDoA and FDoA measurements to overcome the required computational burden by translating the non-convex problem to a convex function, and D. Musicki and W. Koch used a Gaussian mixture measurement filter approach to aggregate TDoA and FDoA measurements.
This article, instead of considering different ad hoc approaches, focuses on two general techniques that can be adopted to aggregate whatever measurements types are available. The first technique, the Taylor Series (TS), is a batch technique that is particularly useful when the target to locate is stationary or moving slowly. The second technique, the extended Kalman filter (EKF), is a sequential technique that is able to track the trajectory of a moving target, estimating both its position and its velocity.
(For the next two sections, including figures and equations, please download the PDF using the link at the top of this article)
Taylor Series Technique
The Taylor-Series (TS) estimation discussed by W. H. Foy (Additional Resources) (or Gauss-Newton interpolation) is an iterative scheme to compute the solution of a set of algebraic (in general non-linear) equations…
…
Extended Kalman Filter Technique
The extended Kalman filter (EKF) is the non-linear version of the Kalman filter, in which non-linearities are approximated by a linearized version around the current state estimate. It is a sequential technique that produces estimates of unknown variables by using Bayesian inference…
…
Conclusions and Future Work
This article discussed the theoretical aspects associated with single-interferer localization approaches, describing how to extract different types of location measurements from the received interference signal and how to compute a position fix by aggregating the collected location measurements.
We focused on two techniques to aggregate the collected location measurements: the Taylor Series and the extended Kalman filter techniques. The former is a batch and iterative scheme to compute the solution of a set of algebraic equations, starting with a rough initial guess of the position estimate and iteratively improving it by determining local corrections. The latter is a sequential technique that produces estimates of unknown variables by using Bayesian inference, keeping in memory a state estimate that is updated as soon as a new location measurement is available. Both techniques have the great advantage that they can incorporate heterogeneous types of location measurements, weighting each measurement appropriately.
The application of the techniques discussed in this article to GNSS interference localization will be examined in a subsequent Working Papers column, which will present simulation results for both the ground and space GNSS interference localization architectures. In addition to this follow-on article, the authors are currently working on developing and analyzing multiple hypothesis tracking techniques for space systems that are required to detect and localize multiple sources of interference.
Acknowledgments
The Ground to Space Threat Simulator (GSTS) project received funding from the European Space Agency under Contract No. 4000113560/15/NL/HK. The project started on April 30, 2015, and is due to be completed by the end of 2016. The information appearing in this document has been prepared in good faith and represents the opinions of the authors. The authors are solely responsible for the content of this publication, which does not represent the opinions of ESA. Neither the authors nor ESA are responsible for any use that might be made of the content appearing herein.
Additional Resources
[1] Canzian, L., and S. Ciccotosto, S. Fantinato, A. Dalla Chiara, G. Gamba, O. Pozzobon, R. Ioannides, and M. Crisci, “Interference Localization from Space: Application,” to appear in Inside GNSS
[2] Chan, Y. T., and K. C. Ho, “A Simple and Efficient Estimator for Hyperbolic Location,” IEEE Transaction in Signal Processing, Volume: 42, Issue: 8, August 1994
[3] Coleman, M., “Satellite Interference – Issues of Concern,” Talk Satellite – EMEA, June 23, 2014
[4] De Martino, A., Introduction to Modern EW Systems, Artech House, 2012
[5] Einicke, G. A., “Smoothing, Filtering and Prediction: Estimating the Past, Present and Future,” Intech, 2012
[6] Foy, W. H., “Position-Location Solutions by Taylor-Series Estimation,” IEEE Transactions on Aerospace and Electronic Systems, Volume: AES-12, Issue: 2, 1976
[7] Guvenc, I., and Y. T. Chan, H. Y. C. Hang, and P. C. Ching, “Exact and Approximate Maximum Likelihood Localization Algorithms,” IEEE Transaction on Vehicular Technology, Volume: 55, Issue: 1, January 2006
[8] Hajian, M., and C. Coman, and L. P. Ligthart, L. P., “Comparison of Circular, Uniform- and non-Uniform Y-Shaped Array Antenna for DOA Estimation using Music Algorithm,” 2006 European Conference on Wireless Technology, Manchester, 2006
[9] Hartwell, G. D., “Improved Geo-Spatial Resolution Using a Modified Approach to the Complex Ambiguity Function (CAF),” Thesis, Naval Postgraduate School, Monterey, CA, September 2005
[10] Jakhu, R. S., “Satellites: Unintentional and Intentional Interference,” Radio Frequency Interference and Space Sustainability, June 2013
[11] Musicki, D. and Koch, W., “Geolocation using TDOA and FDOA measurements,” 11th International Conference on Information Fusion, Cologne, 2008
[12] Open 2015 SDA Users Meeting General Forum
[13] Poisel, R. A., Electronic Warfare Target Location Methods, Artech House, 2012
[14] Schmidt, R., “Multiple Emitter Location and Signal Parameter Estimation,” IEEE Transactions on Antennas and Propagation, Volume: AP-34, Issue: 3, March 1986
[15] Stone, L. D., and R. L. Streit, T. L. Corwin, and K. L. Bell, Bayesian Multiple Target Tracking, 2nd Ed., Artech House, 2014
