Methods for locating transmitters using backward ray tracing

• US 20080224930A1
• Filed: 03/13/2007
• Published: 09/18/2008
• Est. Priority Date: 03/13/2007
• Status: Active Grant

• Current Assignee: Piece Future Pte., Ltd.
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Chizhik, Dmitry, Valenzuela, Reinaldo A.
• Granted Patent: US 7,764,230 B2
• Time in Patent Office: Days
• US Class Current: 342/417
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/12 by co-ordinating position lines of different shape, e.g. hyperbolic, circular, elliptical or radial

Abstract

According to a method for localizing a transmitter inside a building, a transmitter emits rays which undergo multiple reflections with the walls, ceilings and floors of the building. Each of K receivers receives rays from the transmitter, and the receivers estimates the AOA (Angle of arrival), TOA (Time of Arrival) and power of each ray. At least one of the receivers uses a known blueprint of the building and material characteristics of the walls to localize the transmitter to a higher degree of accuracy by applying a backward ray tracing algorithm.

Claims

1. A method for locating a transmitter, the method comprising:

generating, at a receiver, a plurality of candidate locations for the transmitter based on signal ray characteristics of a plurality of signal rays, the candidate locations being points along an estimated path traversed by the plurality of signal rays from the transmitter to the receiver;

calculating, for each candidate location, at least one weighted metric by summing a plurality of location metrics associated with each respective candidate location; and

locating the transmitter based on the at least one weighted metric associated with each candidate location.

2. The method of claim 1, wherein the generating step further comprises:

tracing back, from the receiver, each of the plurality of signal rays received from the transmitter until a stopping condition is met;

identifying points of incidence traversed during the tracing back step, the points of incidence being points at which the plurality of signal rays impinge with a structure or wall of a building; and

selecting at least one point of intersection as a candidate location based on locations of the points of incidence.

3. The method of claim 2, wherein the selecting step further comprises:

comparing the locations of each point of incidence to identify the points of intersection common to at least two back-traced signal rays; and

selecting the points of incidence common to at least two back-traced rays as candidate locations.

4. The method of claim 2, wherein the tracing back step further comprises:

launching a simulated virtual ray toward a first point of incidence on the reverse path of a received signal ray, the first point being a last point traversed by a received signal ray; and

simulating a reverse path of the received signal ray until a stopping condition is met;

wherein

during the simulating step, each point of incidence on the reverse path is recorded in a memory at the receiver.

5. The method of claim 4, wherein the simulating step further comprises:

determining whether a stopping condition has been met at the first point of incidence based on known system parameters and predicted characteristics of the simulated virtual ray; and

deciding whether to terminate simulation of the reverse path of the received signal ray based on the determining step.

6. The method of claim 5, wherein the determining step further comprises:

determining whether the simulated virtual ray exits a structure in which the transmitter is located at the first point of incidence; and

wherein

the stopping condition is met if the first simulated virtual ray segment is determined to have left the structure.

7. The method of claim 5, wherein the determining step further comprises:

counting a number of points of incidence traversed by the simulated virtual ray prior to and including the first point of incidence;

comparing the number of points of incidence with a threshold value; and

wherein

the stopping condition is met if the number of points of incidence is greater than or equal to the threshold value.

8. The method of claim 5, wherein the determining step further comprises:

calculating a predicted power for the simulated virtual ray at the first point of incidence;

wherein

the stopping condition is met if the predicted power is greater than or equal to a transmission power of the received signal ray.

9. The method of claim 1, wherein the generating step further comprises:

estimating signal ray characteristics associated with a signal ray at each candidate location traversed by the signal ray based on known system parameters and predicted signal ray characteristics of the signal ray at each traversed candidate location; and

generating the at least one metric based on the estimated signal ray characteristics.

11. The method of claim 1, wherein the locating step further comprises:

generating the plurality of location metrics based on known system parameters and predicted signal ray characteristics of a received signal ray at each candidate location traversed by the received signal ray.

13. The method of claim 1, wherein the locating step further comprises:

comparing weighted metrics associated with each candidate location; and

wherein

the candidate location with the highest weighted metric determined to be the location of the transmitter.

14. The method of claim 1, wherein the location metric is one of a neighboring candidate location metric, a power difference metric, an expected-predicted power metric and a delay metric.

15. The method of claim 1, wherein the signal ray characteristics include at least one of transmission power and receiving power.

16. The method of claim 1, wherein the virtual signal ray characteristics include at least one of power, distance, arrival time and locations of intersecting virtual rays.

10. (canceled)

12. (canceled)

17. A transceiver for locating a transmitter, the transceiver comprising:

a location estimation unit configured to generate a plurality of candidate locations for the transmitter based on signal ray characteristics of a plurality of signal rays, the candidate locations being points along an estimated path traversed by the plurality of signal rays from the transmitter to the receiver, calculate, for each candidate location, at least one weighted metric by summing a plurality of location metrics associated with each respective candidate location, and locate the transmitter based on the at least one weighted metric associated with each candidate location.

18. The transceiver of claim 17, further comprising:

a memory coupled to the location estimation unit;

wherein

the location estimation unit is further configured to trace back a received signal ray by launching a simulated virtual ray toward a first point of incidence on the reverse path of a received signal ray, the first point being a last point traversed by a received signal ray, and simulate a reverse path of the received signal ray until a stopping condition is met; and

wherein

during the simulating, each point of incidence on the reverse path is recorded in the memory.

19. The transceiver of claim 18, further comprising:

a receiving unit configured to calculate signal ray characteristics of signal rays received from the transmitter;

wherein

the location estimation unit is further configured to determine whether a stopping condition has been met at the first point of incidence based on known system parameters and predicted characteristics of the simulated virtual ray, the predicted characteristics being determined based at least partially on the signal ray characteristics calculated by the receiving unit, and the location estimation unit being further configured to decide whether to terminate simulation of the reverse path of the received signal ray based on whether a stopping condition is met.

20. The transceiver of claim 19, wherein the location estimation unit terminates simulation of at least one virtual ray segment of the simulated virtual ray if a stopping condition is met.