Methods for locating transmitters using backward ray tracing

• US 7,764,230 B2
• Filed: 03/13/2007
• Issued: 07/27/2010
• Est. Priority Date: 03/13/2007
• Status: Expired due to Fees

• Current Assignee: Piece Future Pte., Ltd.
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Chizhik, Dmitry, Valenzuela, Reinaldo A.
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Nguyen; Nga X
• Application Number:
  US11/717,007
• Publication Number:
  US 20080224930A1
• Time in Patent Office: 1,232 Days
• Field of Search: 342/453
• US Class Current: 342/453
• 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;

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

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, a point of incidence being a point at which a signal ray impinges with a structure or wall of a building; and

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

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,

wherein a location metric for a first candidate location among the plurality of candidate locations is calculated, at least in part, based on a comparison between a prediction metric for a signal ray at the first candidate location and a prediction metric for the signal ray at a second of the plurality of candidate locations.

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; 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:

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 additionally 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 also being 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 also being met if the number of points of incidence is greater than or equal to the threshold value.

8. 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 weighted metric based on the estimated signal ray characteristics.

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

10. 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.

15. The method of claim 1, wherein the prediction metric for a candidate location is a ratio of a first power level metric for the signal ray at the first candidate location and a second power level metric for the signal ray at the second candidate location, the power level metrics including at least one of a power difference metric and an expected-predicted power metric.

16. The method of claim 15, wherein, the first power level metric is one of a predicted power and a power deviation for the signal ray at the first candidate location and the second candidate location is a candidate location among the plurality of candidate locations with which a signal ray having at least one of a maximum predicted power and a maximum power deviation is associated.

11. 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 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;

wherein

a location metric for a first candidate location among the plurality of candidate locations is calculated, at least in part, based on a comparison between a prediction metric for a signal ray at the first candidate location and a prediction metric for the signal ray at a second of the plurality of candidate locations.

12. The transceiver of claim 11, 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.

13. The transceiver of claim 12, 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.

14. The transceiver of claim 13, 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.