Method and apparatus for location estimation using region of confidence filtering

• US 7,395,073 B2
• Filed: 03/02/2004
• Issued: 07/01/2008
• Est. Priority Date: 06/05/2003
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Jain, Ravi Kumar, Kawahara, Toshiro, Gwon, Youngjune Lee
• Primary Examiner(s): Ramakrishnaiah; Melur
• Application Number:
  US10/792,450
• Publication Number:
  US 20040248589A1
• Time in Patent Office: 1,582 Days
• Field of Search: 455/456.1, 455/456.2, 455/456.3, 342/463, 342/464, 342/357.12, 342/357.06, 342/462, 701/213
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method for location estimation employs filtering in both the radio signal domain and the space domain separately. The method filters raw values of the run-time radio signal measurements to reject distorted inputs. A region of confidence (RoC) is formed according to certain algorithms. Only location estimates falling within the RoC are considered for further processing. The location estimate candidates filtered by the RoC are put in a number of time-indexed bins. Each of the bins contains location estimate candidates obtained at similar times. A shortest route connecting a candidate from each bin is calculated to further improve the accuracy of the location estimation.

Claims

1. A method for location estimation in a wireless communication environment, comprising:

at a plurality of known locations, receiving RF signals from a plurality of transmitters in the wireless communication environment to provide a site survey according to a predetermined set of metrics, the site survey characterizing the wireless communication environment by the RF signals received at the known locations;

at a mobile station, receiving RF signals from the transmitters;

using the RF signals received at the mobile station and based in part on the site survey, (a) calculating a number of location estimate candidates for the mobile station by a location estimation algorithm; and

(b) forming a region of confidence (RoC) for the location estimate candidates.

2. The method according to claim 1, wherein the RF signals are selected from the group consisting of cellular phone signals, WLAN signals, and Bluetooth signals.

3. The method according to claim 1, further comprising filtering the RF signals to remove distorted signals.

4. The method according to claim 1, wherein the location estimation algorithm for calculating the location estimate candidates is selected from the group consisting of a triangulation algorithm, a K-nearest neighbor averaging algorithm, and a smallest m-polygon algorithm.

5. The method according to claim 1, wherein the RoC is at least a part of a circle.

6. The method according to claim 4, wherein the center of the RoC is a location estimate determined by a location estimation algorithm.

7. The method according to claim 6, wherein the location estimation algorithm for determining the center of the RoC is a triangulation algorithm.

8. The method according to claim 7, wherein a first circle, a second circle and a third circle are used to determine the center of the RoC.

9. The method according to claim 8, wherein, when the three circles intersect at six points, the center of the RoC is a centroid of a smallest triangle formed by the six points.

10. The method according to claim 9, wherein a radius of the RoC is the longest distance between the centroid and one of the vertices of the smallest triangle.

11. The method according to claim 8, wherein when the first and second circles intersect at two points, and the second and third circles intersect at another two points, the center of the RoC is a centroid of the smallest triangle formed by the four points.

12. The method according to claim 11, wherein a radius of the RoC is the longest distance between the centroid and one of the vertices of the smallest triangle.

13. The method according to claim 8, wherein when the first and second circles intersect at two points, but do not intersect with the third circle, the center of the RoC is a midpoint of the line joining the two points.

14. The method according to claim 13, wherein a radius of the RoC is half the distance between the two points.

15. The method according to claim 6, wherein the location estimation algorithm for determining the center of the RoC is the K-nearest neighbor averaging algorithm.

16. The method according to claim 6, wherein the location estimation algorithm for determining the center of the RoC is the smallest M-polygon algorithm.

17. The method according to claim 1, further comprising filtering the location estimate candidates that fall out of the RoC.

18. The method according to claim 1, further comprising segmenting the location estimate candidates by the time it takes to obtain them, and searching for a shortest route connecting one location estimate candidate at each of the times.

19. The method according to claim 18, further comprising searching for a shortest route according to a pair-wise algorithm.

20. The method according to claim 18, further comprising searching for a shortest route according to a non-pair-wise algorithm.

21. The method according to claim 18, further comprising generating a new RoC whenever the shortest route exceeds the radius of the RoC.

22. The method according to claim 1, further comprising generating a new RoC whenever the period of the RoC expires.

23. The method according to claim 1, further comprising generating a new RoC at a certain period of time before the period of the RoC expires.

24. A computer program product containing program code for performing the method according to claim 7.

25. A computer program product containing program code for performing the method according to claim 15.

26. A computer program product containing program code for performing the method according to claim 16.

27. A computer program product containing program code for performing the method according to claim 17.

28. A computer program product containing program code for performing the method according to claim 18.

29. A computer program product containing program code for performing the method according to claim 21.

30. A computer program product containing program code for performing the method according to claim 22.

31. A computer program product containing program code for performing the method according to claim 23.

32. A computer program product containing program code for performing the method according to claim 1.

33. In a wireless network, a location estimation apparatus comprising:

a RF signal receiver, receiving RF signals from transmitters in the wireless network;

an off-line signal processor for calibrating the wireless network based on the RF signals received by the RF signal receiver at known locations and outputting the calibration data;

a candidate processor, calculating a number of location estimate candidates for the RF receiver by a location estimation algorithm, using the RF signals and the calibration data; and

a region of confidence (RoC) formation module, forming a RoC for the location estimate candidates using the RF signals and the calibration data.

34. The apparatus according to claim 33, further comprising a statistical signal processor, receiving signals from the RF signal receiver and filtering distorted RF signals.

35. The apparatus according to claim 33, further comprising a RoC filter, receiving signals from the RoC formation module and filtering bad location estimate candidates.

36. The apparatus according to claim 33, further comprising a shortest route calculator for segmenting the location estimate candidates according to the time it takes to obtain them, and searching for a shortest route connecting one location estimate candidate at each of these times.

37. The apparatus according to claim 33, wherein the off-line signal processor creates a location information database and updates it by storing acquired signal metrics at knows portions.

38. A wireless communication device having the apparatus according to claim 33.

39. A handheld terminal having the apparatus according to claim 33.

40. An access point for use in a wireless communication network, wherein the access point comprises the apparatus according to claim 33.