Method and apparatus for location estimation using region of confidence filtering

• US 20040248589A1
• Filed: 03/02/2004
• Published: 12/09/2004
• Est. Priority Date: 06/05/2003
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: DOCOMO Communications Laboratories USA, Inc.
• Inventors: Jain, Ravi Kumar, Kawahara, Toshiro, Gwon, Youngjune Lee
• Granted Patent: US 7,395,073 B2
• Time in Patent Office: Days
• 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:

receiving RF signals from at least two transmitters in the wireless communication environment;

calculating a number of location estimate candidates by a location estimation algorithm; and

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.

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

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

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

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

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

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

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

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

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

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

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

a candidate processor, calculating a number of location estimate candidates by a location estimation algorithm; and

a region of confidence (RoC) formation module, forming a RoC for the location estimate candidates.

25. The apparatus according to claim 24, further comprising an off-line signal processor for calibrating the wireless network and outputting data to the RoC formation module.

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

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

28. The apparatus according to claim 24, 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.

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

30. A wireless communication device having the apparatus according to claim 24.

31. A handheld terminal having the apparatus according to claim 24.

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