Localization with non-synchronous emission and multipath transmission

Abstract

Directional characterization of a location of a target device makes use of multiple radio transmissions that are received from the target device. In some examples, each radio transmission is received at a first antenna at a fixed location, and is also received at a second moving antenna. The received transmissions are combined to determine the directional characterization, for example, as a distribution of power as a function of direction. In some examples, the received radio transmissions are processed to determine, for each of a plurality of directions of arrival of the radio transmissions, a most direct direction of arrival, for example, to distinguish a direct path from a reflected path from the target.

Claims

1. A computer implemented method comprising: receiving a plurality of radio transmissions from a target device, each radio transmission of the plurality of radio transmissions being received at a first antenna at a fixed location, and received at an antenna at a location other than the fixed location of the first antenna such that the plurality of transmissions are received at a corresponding plurality of locations other than the fixed location of the first antenna; for each radio transmission of the plurality of radio transmissions, determining a first channel characteristic for a first radio channel from the target device to the first antenna, determining a second channel characteristic for a second radio channel from the target device to the antenna at the location other than the fixed location of the first antenna; combining the first channel characteristics and the second channel characteristics for the plurality of radio transmissions to determine a relative channel characteristic associated with each of the radio transmissions; and combining the relative radio characteristics and the corresponding locations other than the fixed location of the first antenna to determine a directional characterization of a location of the target device.

2. The method of claim 1 wherein receiving the radio transmission at a location other than the fixed location of the first antenna comprises receiving said transmission at a second moving antenna, wherein the plurality of locations other than the fixed location of the first antenna comprises a plurality of locations of the second antenna.

3. The method of claim 1 further comprising causing the second antenna to move along a spatial path, the plurality of locations of the second antenna falling on the spatial path.

4. The method of claim 3 wherein the spatial path comprises a repeated path.

5. The method of claim 1 wherein receiving the radio transmission at a location other than the fixed location of the first antenna comprises selecting a second antenna from a set of antennas, wherein the plurality of locations other than the fixed location of the first antenna comprises locations of the selected second antennas.

6. The method of claim 5 wherein the radio transmissions comprise frequency division multiplexed encodings of transmission data.

7. The method of claim 6 wherein the radio transmissions comprise Orthogonal Frequency Division Multiplexed (OFDM) encodings of transmission data.

8. The method of claim 5 further comprising: identifying a plurality of directions of arrival plurality of radio transmissions at the locations of the second antenna, at least one of the directions of arrival corresponding to a reflected path from the target device to the locations of the second antenna.

9. The method of claim 8 further comprising: identifying a most direct direction of arrival from the plurality of directions of arrival.

10. The method of claim 8 wherein identifying a most direct direction of arrival comprises combining the relative radio characteristics and the corresponding locations of the second antenna to determine a channel characteristic corresponding to each of the plurality of directions of arrival, the channel characteristic representing a variation a phase characteristic across different of the different transmission frequencies.

11. The method of claim 1 wherein each radio transmission comprises a plurality of components at different transmission frequencies, and wherein the first channel characteristic, the second channel characteristic, and the relative channel characteristic each comprises channel characteristics corresponding to the different transmission frequencies.

12. The method of claim 1 further comprising: combining the relative radio characteristics and the corresponding locations of the second antenna to identify a most direct direction of arrival from the plurality of directions of arrival.

13. The method of claim 1 wherein the first channel characteristic and the second channel characteristic each comprises a phase characteristic, and the relative channel characteristic comprises a relative phase characteristic.

14. The method of claim 1 wherein determining the directional characterization of location comprises determining a power distribution as a function of direction of arrival.

15. The method of claim 14 wherein determining the directional characterization further comprises identifying a set of one or more directions of peak power of the power distribution.

16. The method of claim 1 wherein the target device comprises at least one of a wide area cellular communication device and a wireless local area network device.

17. A localization system configured to perform all the steps of claim 1.

18. Software, embodied on a non-transitory machine-readable medium, comprising instructions for causing a processor of a localization system to perform all the steps of claim 1.

19. A localization system comprising: a plurality of antenna; a receiver coupled to the plurality of antennas for receiving radio signals acquired at the plurality of antennas and configured to process a plurality radio transmissions from a target radio device, including receiving the plurality of radio transmissions from a target device, each radio transmission of the plurality of radio transmissions being received at a first antenna at a fixed location, and received at an antenna at a location other than the fixed location of the first antenna such that the plurality of transmissions are received at a corresponding plurality of locations other than the fixed location of the first antenna, for each radio transmission of the plurality of radio transmissions, determining a first channel characteristic for a first radio channel from the target device to the first antenna, determining a second channel characteristic for a second radio channel from the target device to the antenna at the location other than the fixed location of the first antenna, combining the first channel characteristics and the second channel characteristics for the plurality of radio transmissions to determine a relative channel characteristic associated with each of the radio transmissions, and combining the relative radio characteristics and the corresponding locations other than the fixed location of the first antenna to determine a directional characterization of a location of the target device.

20. The system of claim 19 further comprising the first fixed antenna at the fixed location, and a second movable to the plurality of locations other than the fixed location of the first antenna.

Description

DESCRIPTION OF DRAWINGS

(1) FIG. 1 is an illustration of a localization system that uses a moving antenna;

(2) FIG. 2 is a diagram that illustrates signal propagation in a two-dimensional implementation;

(3) FIG. 3 is a diagram that illustrates an example with a single target device;

(4) FIG. 4 is a plot of power as a function of direction of arrival for the example shown in FIG. 3;

(5) FIG. 5 is a diagram that illustrates an example with a single target device in which a direct and a reflect path are present;

(6) FIG. 6 is a plot of power as a function of direction of arrival for the example shown in FIG. 5.

(7) FIG. 7 is flow chart of a method for determining a characterization of a location of a target device.

DESCRIPTION

(8) A number of approaches are described below in the context of localization of radio frequency transmitting devices in an indoor environment in which the transmitting devices are independent of a localization receiver and there are generally multiple reflected paths from the transmitting devices to the receiver. A specific embodiment is described in which the transmitting devices are cellular telephones (e.g., LTE transmission in the 700 MHz-2.6 GHz range) or wireless local area network devices (e.g., IEEE 802.11 standard (WiFi) transmission in at 2.4 GHz or 5 GHz). Note that approaches that address the independence of the transmitting devices and the localization receiver and approaches that address multipath effects can be used independently in various applications, and together provide high accuracy in applications such as indoor localization. For reference, the wavelength of a radio signal at 2.4 Ghz and 5.0 Ghz is about 12.5 cm and 6.0 cm, respectively.

(9) A first embodiment is described for two-dimensional localization using directly received signals. A second related embodiment is then described for three-dimensional localization using the same approaches. Further embodiments are then described in which multipath effects are addressed.

(10) As introduced above, conventional Synthetic Aperture Radar (SAR) takes advantage of the feature that the radio signal that is transmitted toward and then reflected from a targeted object is generated by a clock signal that is also used in the processing of the received reflected signal. In particular, the relative phase of the transmitted signal and the received signal can be used to provide range information. In this sense, the emission from a SAR antenna is synchronous with the reception of the echo from the targeted object, thereby providing range information between the location of the transmitter when it emitted the signal to the targeted object and back to the location of the receiver when it received the reflected signal. In the application of localization of independent transmitting devices (e.g., LTE or WiFi devices), the receiver of the emission from the transmitting devices does not share a common clock or oscillator, and therefore the reception of the signal does not provide range information in the same manner as is available in conventional SAR techniques.

(11) Referring to FIG. 1, an embodiment of a localization system 100 makes use of a moving antenna 111 as well as a fixed antenna 112. These antennas provide radio signals to a localization receiver 110, which outputs location information corresponding to one or more transmitting target devices 150 in the environment of the system 100. The target devices 150 (e.g., LTE or WiFi devices) emit transmissions that pass directly to the antennas 111-112 on paths 151-152 and/or that pass on reflected paths 153-154, which reflect off one or more reflecting objects 160 (e.g., walls, buildings, etc.). In the first embodiment, only direct paths 152-153 are considered. The localizing receiver 110 also receives information characterizing the location of the moving antenna 111. In this embodiment, the moving antenna rotates in a circle 132, and its location is characterized by an angle of rotation .sub.R 130 of the antenna relative to a fixed reference direction (.sub.R=0).

(12) In general, each target device 150 makes a series of transmissions, for example, each transmission comprising a transmission frame carrying data (e.g., which may include voice data). For example, in an LTE application, each frame may be 10 milliseconds long and WiFi frames are generally shorter than 10 milliseconds. In this embodiment, the moving antenna 111 is moving relatively slowly as compared to the frame length, and is therefore considered stationary for the duration of a frame for the analysis. For example, the rotating antenna 111 may have a rotation radius of 10 centimeters and a rotation period of 0.5 to 2 seconds (30-120 revolutions per minute), and therefore travels only a fraction of a millimeter during a frame transmission time. In LTE, the estimation procedure can be performed at a sub-frame level such that a separate estimate is performed for each sub-frame (e.g., 1 millisecond) and the antenna is only considered to be stationary for the duration of the sub-frame.

(13) Referring to FIG. 2, in a two-dimensional embodiment in which the target devices 150 and the antennas 111-112 are in (or at least assumed to be in) one plane, a representative direct transmission from a target device 150 is illustrated. In this illustration, the target device is at an angle .sub.T, and the rotating antenna is at an angle .sub.R.sup.(n). The superscript (n) represents that this is the n.sup.th reception from the target. As will be discussed further below, a series of transmissions n=1, . . . , N, with the receiving antenna 111 at different angles .sub.R.sup.(n) are combined in localizing the target device 150. The direct path from the target device 150 follows a path 151 to the moving antenna 111 of length d.sub.1.sup.(n) and a direct path 152 from the target device 150 to the fixed antenna 112 d.sub.0. In this illustration, the difference in these path lengths is
d.sub.1.sup.(n)d.sub.0=d.sup.(n)=D.sub.0r cos(.sub.T.sub.R.sup.(n))).
The constant term D.sub.0 does not vary with .sub.R.sup.(n). In the limit that the target device is far from antennas, D.sub.0=L cos .sub.T, but as is shown below, the specific value of D.sub.0 is not significant. The transmission from the target device is assumed to include a known (complex valued) signal p that is modulated by a carrier, which is represented as the complex exponential exp(jt). For example, the known signal is a pilot signal or an error corrected data signal. The receiver demodulates the received signal at the antennas with an oscillator that is offset in phase by .sup.(n) from the transmitting transmitter. The superscript (n) represents the fact that the receiver does not assume a fixed phase offset between transmissions from the target device. For example, frequency differences may not vary significantly during a single frame but may nevertheless exhibit significant phase drift between transmissions. After demodulation the received signal at moving antenna 111 has a phase offset due to the distance d.sub.1.sup.(n) as well as the phase difference .sup.(n) and the demodulated signal at the fixed antenna 112 has a phase offset due to the distance d.sub.0 as well as the phase difference .sup.(n). Specifically,
q.sub.1=pm.sub.1exp(j(kd.sub.1.sup.(n)+.sup.(n))), and
q.sub.0=pm.sub.0exp(j(kd.sub.0+.sup.(n))).
where k=2/=/c, and c is the propagation speed of the signal, and m.sub.0 and m.sub.1 are complex quantities (i.e., representing constant attenuation and phase offset) that do not depend on n. The receiver forms channel estimates using these demodulated values as
h.sub.1.sup.(n)=q.sub.1/p, and
h.sub.0.sup.(n)=q.sub.0/p.

(14) Note that both these channel estimates, h.sub.1.sup.(n) and h.sub.0.sup.(n) are affected by the unknown phase offset .sup.(n). However, a ratio of the channel differences is only affected by the difference in differences in the distances d.sup.(n)=d.sub.1.sup.(n)d.sub.0

(15) ${\tilde{h}}^{\left(n\right)}=\frac{h_1^{\left(n\right)}}{h_0^{\left(n\right)}}=\frac{m_1}{m_0}\exp \left(-jk{d}^{\left(n\right)}\right)$
This ratio can be represented as
{tilde over (h)}.sup.(n)=h.sub.0exp(jkr cos(.sub.T.sub.R.sup.(n)))
where h.sub.0=(m.sub.1/m.sub.0) exp (D.sub.0) is a complex quantity, in which D.sub.0 depends on .sub.T and L but not on .sup.(n) or .sub.R.sup.(n).

(16) Combination of N channel estimates {tilde over (h)}.sup.(n) at corresponding receiving antenna angles .sub.R.sup.(n) then makes use of a computation analogous to that used in SAR receivers, namely

(17) $P\left(\right)={.Math.\tilde{h}\left(\right).Math.}^2={.Math.\underset{n=1}{\overset{N}{.Math.}}{a}^{\left(n\right)}\left(\right){\tilde{h}}^{\left(n\right)}.Math.}^2,$
where

(18) $\tilde{h}\left(\right)=\underset{n=1}{\overset{N}{.Math.}}{a}^{\left(n\right)}\left(\right){\tilde{h}}^{\left(n\right)},\mathrm{and}{a}^{\left(n\right)}\left(\right)=\exp \left(jkr\cos \left(-{}_R^{\left(n\right)}\right)\right).$
Note that it should be evident that a.sup.(n)(){tilde over (h)}.sup.(n) has a maximum magnitude at =.sub.T, as does the summation over the N receptions from the target device. Therefore, with a single transmitting device 150, estimation of the direction of arrival .sub.T is performed by finding the maximum of the computed P().

(19) When there are multiple target devices 150 in the environment, in some embodiments, content of each received frame identifies the source of the transmission. Therefore, the localizing receiver 110 collects transmissions for each target device and records them separately applying the computation of P() independently for each target device.

(20) In general, the moving antenna moves independently of the transmissions being received, for example, rotating at a constant rate. The localizing receiver 110 receives the angle of rotation .sub.R.sup.(n) corresponding to each received frame.

(21) In the case of an orthogonal frequency division multiplexed (OFDM) transmission from the target device, essentially a set of transmission frequencies (indexed by f) are present in each transmitted frame from a target device, and a set of channels estimates {tilde over (h)}.sub.f.sup.(n) are obtained from a received transmission, and separate directional power estimates P.sub.f () may obtained for each frequency. In some implementations, separate direction estimates may be made from each frequency, or alternatively, the power estimates may be combined to determine a single overall direction estimate.

(22) Referring to FIG. 3, a simulation of a single target device is illustrated in a situation in which: r=10 cm with the antenna rotating about a point (0,0) L=1.0 m such that the fixed antenna is at coordinates (1.0, 0.0) the target device 150 is at coordinates (1.0,3.0) such that .sub.Ttan.sup.1(3.0)=72 the operating frequency is 5 GHz, so 6.0 cm.
A simulation in which N=32 observations equally spaced during one rotation of the moving antenna 111 yields P() as illustrated in FIG. 4. Note that P() has a peak at approximately =72 consistent with the simulated environment shown in FIG. 3.

(23) A second embodiment makes use of the same arrangement of fixed and moving antennas as illustrated in FIG. 1. However, the target devices 150 are not assume to be in the same plane as the antennas, and a three dimensional localization is performed. Specifically, rather than only estimating an azimuth angle , and elevation angle is also estimated. In this embodiment, =0 is in a direction orthogonal to the plane of rotation of the moving antenna 110, and =/2 is in the plane of the rotating antenna. In an example in which a target is in direction (.sub.T, .sub.T), using a similar analysis as presented above for the two-dimensional embodiment, the difference in direct transmission distances from the target device 150 to the moving and fixed antennas, respectively, is
d.sub.1.sup.(n)d.sub.0=d.sup.(n)=D.sub.0r sin .sub.T cos(.sub.T.sub.R.sup.(n))

(24) As in the first embodiment, the ratio of the channel estimates can be represented as
{tilde over (h)}.sup.(n)=h.sub.0exp(jkr sin .sub.T cos(.sub.T.sub.R.sup.(n)))
where h.sub.0=exp (jD.sub.0) is a complex quantity that depends on .sub.T, .sub.T and L but not on .sup.(n) or .sub.R.sup.(n).

(25) Combination of N channel estimates {tilde over (h)}.sup.(n) at corresponding receiving antenna angles .sub.R.sup.(n) then makes use of a computation analogous to that used in SAR receivers, namely

(26) $P\left(,\right)={.Math.\underset{n=1}{\overset{N}{.Math.}}{a}^{\left(n\right)}\left(,\right){\tilde{h}}^{\left(n\right)}.Math.}^2,$
where
a.sup.(n)(,)=exp(jkr sin cos(.sub.R.sup.(n))).
The location of the maximum of P(,) then provides the direction estimate for (.sub.T,.sub.T).

(27) Note that the approach to computing the directional power distribution, P(,), shown above (often referred to as a Bartlett estimator) can be replaced with other procedures. For instance, a covariance-based and/or eigen-decomposition approach (e.g., a MUSIC, MUltiple SIgnal Classifier, algorithm, or ESPRIT, Estimation of Signal Parameters via Rotational Invariance Technique, algorithm) can be used to estimate P(,) from the {tilde over (h)}.sup.(n). Therefore, the procedure used to further process P(,) can be carried out without regard to which approach is used to estimate it.

(28) In the description of the first and second embodiments above, only direct paths 151-152 are considered. In a third embodiment, multiple paths are assumed. Referring back to FIG. 1, both a direct path 151 and a reflected path 153 can pass from the target device 150 to the moving antenna 111, and similarly, both a direct path 152 and a reflected path 154 pass to the fixed antenna 112. Referring to FIG. 5, an example similar to that shown in FIG. 3 further has a reflecting surface 160 at x=2.0. As a result, a direct path from the target device 150 to the moving antenna has approximately an azimuth of .sub.T=72 along path 151, and approximately an angle of .sub.T=45 along reflected path 153. As in the first embodiment, the ratio of channel estimates

(29) ${\tilde{h}}^{\left(n\right)}=\frac{h_1^{\left(n\right)}}{h_2^{\left(n\right)}}$
are computed as described above, and P() is computed as described above.

(30) Referring to FIG. 6, in this example, P() has two peaks as would be expected from the geometry of the simulation. Also, in this simulation, the direct path at =72 corresponds to peak with greater magnitude than a peak corresponding to the indirect path at =45. However, in general, it is not reliable to assume that the greatest energy comes from the direct path. For example, the direct path may be attenuated by an obstacle while the reflected path is not. An approach described below makes use of an estimate of the absolute delay along each path, and the shortest delay path is assumed to be the direct path.

(31) An approach to estimating the absolute delay of a signal arriving from a particular direction makes use of the signal having components transmitted at different frequencies. In this third embodiment, a set of known signals p.sub.f are transmitted at a set of frequencies indexed by f. As introduced above, in one example, an OFDM signal is transmitted in this manner such that signal p.sub.f is transmitted with a wave number k.sub.f=2/.sub.f=.sub.f/c, for example, for integer indices, .sub.f=.sub.0+f.

(32) In order to determine relative delay between paths arriving from different directions, in this third embodiment, the SAR approach is used to determine the (complex) response for each direction of arrival. For example, in the example shown in FIGS. 5 and 6, the complex response is computed at the peaks located at azimuth .sub.T=72 and .sub.T=45. In FIG. 5, the target device 150 to the fixed antenna is d.sub.0, the direct distance from the target device 150 to the center for the circle 132 is d.sub.1 and the distance along the reflected path from the device 150 to the center of the circle is d.sub.2. A vector of wave numbers
k=(.sub.0, . . . ,.sub.F-1).sup.T/c
yields a vector of ideal direct channels
h.sub.1=h(.sub.T1)=exp(jkd.sub.1)h.sub.1
where h.sub.1 is the part of the direct channel not explained by the distance d.sub.1. Similarly,
h.sub.2=h(.sub.T2)=exp(jkd.sub.2)h.sub.2
and the ideal direct channel to the fixed antenna is
h.sub.0=exp(jkd.sub.0)h.sub.0.
Therefore, the quantity computed from the N receptions for all the F frequencies

(33) ${\underset{\_}{\tilde{h}}}_1=\underset{\_}{\tilde{h}}\left({}_{T1}\right)=\underset{n=1}{\overset{N}{.Math.}}{\underset{\_}{a}}^{\left(n\right)}\left({}_{T1}\right){\underset{\_}{\tilde{h}}}^{\left(n\right)}$
is approximately

(34) ${\underset{\_}{\tilde{h}}}_1\exp \left(-j\underset{\_}{k}\left(d_1-d_0\right)\right)\frac{{\underset{\_}{h}}_1^{}}{{\underset{\_}{h}}_0^{}}.$
Under the assumption that the phase (but not necessarily the magnitude) of the elements of h.sub.1 are equal, and the phase of the elements of h.sub.0 are equal (but not necessarily the same as for h.sub.1), then the phase of {tilde over (h)}.sub.1 satisfies
{tilde over (h)}.sub.1k(d.sub.1d.sub.0)+constant.
Therefore because k.sub.f=(+f)/c, the elements of this phase vector {tilde over (h)}.sub.1 vary with a proportionality (d.sub.1d.sub.0)/c (recognizing that phase may need to be unwrapped to provide continuity of the phase elements). Similarly, the elements of this phase vector {tilde over (h)}.sub.2 vary with a slope (d.sub.2d.sub.0)/c. Therefore, if d.sub.1<d.sub.2, as is the case in this example, the slope for =72 is greater than the slope for the path at =45, and therefore the receiver determines that the =72 peak in P() corresponds to the direct path (or more generally, the most direct of possibly reflected paths).

(35) In the description of the third embodiment above, the complex response in a particular direction is computed using a SAR technique. However, it should be understood that alternate approaches, including determining the directional responses from a fixed array of antennas that concurrently receive the same signal, can be used to determine the responses that permit discrimination according to travel path length (e.g., direct versus indirect path lengths).

(36) Note that in some examples, only a two dimensional (single direction angle ) is used. The same approach is applicable in the three dimensional case where peaks in P(,) are first identified, and then the shortest distance is determined by determining the largest slope in the phase variation over frequencies. Note also, that the frequency components are not necessary uniformly spaced in frequency, and the slope determination can take account of this non-uniform spacing in estimating the slope of the phase variation with frequency.

(37) Therefore, referring back to FIG. 1, having identified the peaks in P(), and resolved which of those peaks correspond to the direct (or at least the shortest) path to the target device 150, the localizing receiver 110 provides as output the direction .sub.T to the target as part of its reported device locations 140. As introduced above, because the received signals identify the target device (e.g., by a device identified encoded in the received frames), the localizing receiver separately computes the direction to the targets 150, and the reported device locations 140 can include directions in association with the device identifiers. In some embodiments, a graphical display indicates the locations of the target devices in an area being monitored by one or more localizing receivers 110.

(38) In an alternative embodiment, moving antennas at two (or more) different locations and a corresponding fixed antenna for each moving antenna, or a single fixed antenna, are used to determine multiple different directions to each target, and a triangulation approach is used to combine the direction estimates. In yet other examples, a SAR approach is used to directly determine a distribution P(, , r) where r is the range of the target device. In other embodiments, it is not necessary that the moving antenna or antennas follow circular paths as other repeating of non-repeating (e.g., irregular) patterns of movement of the moving antenna may be used. For example, an antenna may follow a linear path, or may follow an irregular path (e.g., along the path of a vehicle to which it is attached). Furthermore, rather than using one (or a set) of antennas that move, successive selection of different subsets (e.g., selection of successive single) of antennas at different fixed locations can be used. In this way, the mechanical requirements of a moving antenna are essentially replaced with electronic requirements to switch received signals (e.g., at the transmission frequency or at an intermediate or baseband frequency).

(39) Implementations of the approaches described above may use hardware (e.g., application-specific integrated circuits, ASICs), or in software (e.g., using a general purpose processor, a special purpose controller, or a processor in a software defined radio, such as an Ettus Research USRP N210 with a GNU radio), or using a combination of software and hardware. The software includes instructions that are stored on a non-transitory machine readable medium (e.g., semiconductor memory). The hardware, processor, and/or instruction storage can be included within the localizing receiver 110. The system can also include the actuator (e.g., motor) and mechanical linkage required to physically move the antenna as described above. The location (e.g., angle) of the moving antenna can be determined using a sensor (e.g., a rotary encoder) that provides location-indicative measurements to the localizing receiver, or the location (e.g., angle) of the antenna may be inferred according to the commands provided to the actuator.

(40) It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.