
Working Papers • November/December 2016
Interference Localization from SpaceTheoretical BackgroundRadio Frequency Interference causes the satellite industry to lose millions of dollars per year due to detrimental effects, ranging from a degradation in the quality of service to the complete loss of service. As a consequence, it is becoming critical important to design space systems that are able to localize the source of interference, allowing actions that can prevent future repetitions of similar behaviors. This is the first of a series of articles on the issue of interference localization. This article discusses the theoretical aspects associated with singleinterferer localization approaches, describing how to extract those features providing information on the interference source location from the received interference signal itself, and how to compute a position fix by merging the collected information.
Share via: Slashdot Technorati Twitter Facebook 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 reappearing. 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 2^{n–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. Multiplehypothesis 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 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 transmittertoreceiver 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 upperleft subfigure 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 twodimensional space and a hyperboloid in a 3D space. The upperright subfigure 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, f_{0} 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 halflines 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 lowerleft subfigure 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 halflines 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 v_{1}(x,y,z) and v_{2}(x,y,z) are the relative speed vectors between the two receivers and the transmitter, α_{1}(x,y,z) is the angle between v_{1}(x,y,z) and the vector connecting the first receiver to the transmitter (analogous to α_{2}(x,y,z), f_{0} 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 v_{1}(x,y,z) and v_{2}(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 lowerright subfigure 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 (f_{0} 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 = 10n_{p}log_{10}(ρ(x,y,z)) + ε (5) where ρ(x,y,z) is the transmittertoreceiver distance, which depends on the transmitter position (x,y,z), n_{p} 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 upperleft subfigure 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); n_{p} 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 n_{p}. 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 lowerleft subfigure 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 halfline departing from the reference position, or two halflines if the sign of the elevation angle is uncertain.
Choosing and Generating the Measurement Types 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 [t_{1}, t_{1} + 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 T_{s} is the sampling time, n_{1}T_{s} is the beginning of the acquisition time interval, which corresponds to the time at which the TDoA measurement is evaluated, and K ⋅ T_{s} 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 T_{s}. 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 threedecibel beamwidth of each antenna pattern, meaning that at least one antenna receives the signal within the threedecibel 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 90degree 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 xyz Cartesian system, the antenna pointing directions must not lie in the same plane. The illustration on the righthand side of Figure 3 shows a fourantenna 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 onetoone 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 superresolution directionfinding 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 subspacebased processing and is based on an eigendecomposition of the covariance matrix derived from data samples to obtain two orthogonal matrices, which represent the signalsubspace and the noisesubspace. 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 eigendecomposition 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) is the phase shift observed by the ith 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 subspaces 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 subspace 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 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 subfigures. 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 xaxis. This symmetry occurs because both segments connecting the two receivers and the receiver velocities lie along the xaxis. 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 leastsquares 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 leastsquares 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 leastsquares 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 twostage 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 nonconvex 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 …
Extended Kalman Filter Technique …
Conclusions and Future Work 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 followon 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
Additional Resources Author Profiles
Luca Canzian, Stefano Ciccotosto, Samuele Fantinato, Andrea Dalla Chiara, Giovanni Gamba, Oscar Pozzobon
Rigas Ioannidesa and Massimo Crisci Copyright © 2018 Gibbons Media & Research LLC, all rights reserved. 
