System and method for determining the geographic location of a device
View Patent ↗A method and apparatus for estimating a location of a device. For each of a plurality of locations of a device, a set of positional data is determined from signals received from a plurality of satellites. The positional data is filtered and compared with data from a road network database. This comparison may be a function of a distance from at least one point defined by a set of the filtered positional data to a road in the road network database and an angle between a line representing a best fit for plural points defined by corresponding plural sets of the filtered positional data to a line defined by a road in the road network database.
1. A method of estimating a location of a device, comprising:
(a) determining for each of a plurality of locations of said device a set of positional data from signals received from a plurality of sources;
(b) filtering said positional data, comprising the steps of:
(i) detecting a jump between consecutive positional data if the speed between the consecutive positional data exceeds a predetermined threshold; and
(ii) correcting the jump with a processor as a function of the angle and the speed between the consecutive positional data,
wherein the step of correcting the jump comprises correcting the jump as a function of the following vector relationship:
vector T ={s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[cos(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* x+{s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[sin(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* y ; and
(c) comparing said filtered positional data with data from a road network database wherein said comparing is a function of:
(i) a distance from at least one point defined by a set of said filtered positional data to a road in said road network database, and
(ii) an angle between a line representing a best fit for plural points defined by corresponding plural sets of said filtered positional data to a line defined by a road in said road network database.
2. The method of claim 1 wherein the step of filtering said positional data further comprises discarding positional data as a function of satellite visibility.
3. The method of claim 1 wherein the step of filtering said positional data further comprises discarding positional data as a function of the visibility of a network element in a communications network.
4. The method of claim 1 wherein the step of filtering said positional data further comprises discarding positional data if the respective Horizontal Dilution of Precision (“HDOP”) is greater than a predetermined threshold.
5. The method of claim 1 wherein the step of filtering said positional data further comprises discarding dead-reckoning based data if the estimated location differs from an actual location by more than a predetermined threshold.
6. The method of claim 1 wherein said positional data comprises both current and past positional data of said device.
7. The method of claim 1 wherein said positional data is selected from the group consisting of latitude, longitude, time of data, number of visible positional satellites, HDOP, altitude, and positional mode information.
8. The method of claim 1 wherein said road network database comprises map-related information is selected from the group consisting of latitudes and longitudes of roads, permissible directional travel on a road, speed limits, allowable turns from a road, curvature of a road, and topographical data.
9. The method of claim 1 further comprising the step of filtering the compared data as a function of topographical information.
10. The method of claim 1 further comprising the step of correcting the compared data by projecting an estimated location on a predetermined road.
11. The method of claim 1 further comprising the step of correcting the compared data as a function of topographical information.
12. The method of claim 1 wherein the step of comparing further comprises the steps of:
(i) identifying positional data having a time of data less than a predetermined threshold;
(ii) reducing candidate roads for an estimated location as a function of a predetermined distance from said identified positional data;
(iii) computing distance probabilities as a function of the identified positional data and reduced candidate roads; and
(iv) computing angle probabilities as a function of identified positional data being on a candidate road based upon the direction of the road and the direction of travel of the device.
13. The method of claim 12 wherein a distance probability is a function of the following relationship:
P dist( d )=exp(− d 2 /DIST_DEV 2 )
wherein DIST_DEV is an estimated standard deviation of distance error.
14. The method of claim 13 wherein an angle probability is a function of the following relationship:
P angle(angle)=exp(−angle 2 /ANGLE_DEV 2 )
wherein ANGLE_DEV is an estimated standard deviation of angle error.
15. The method of claim 13 wherein the step of computing distance probabilities further comprises computing distance probabilities for N candidate roads and M identified positional data as a function of the following relationship:
Proad_d
(
k
,
t
)
=
PD
t
(
k
)
(
∑
j
=
1
N
PD
t
-
1
(
j
)
PT
t
(
j
,
k
)
)
where 1≦t≦M, 1≦k≦N and where Proad_d is an N×M matrix holding probabilities of each candidate road for each positional data.
16. The method of claim 1 wherein at least one of said plurality of sources is a satellite which is a part of a Global Navigation Satellite System (“GNSS”).
17. The method of claim 16 wherein the GNSS is selected from the group consisting of: Global Positioning System (“GPS”), Galileo, GLONASS, and Quasi-Zenith Satellite System (“QZSS”).
18. The method of claim 1 wherein the device is a mobile unit.
19. The method of claim 18 wherein the mobile unit is selected from the group consisting of: cellular device, text messaging device, computer, portable computer, vehicle locating device, vehicle security device, communication device, wireless transceiver, hand-held navigational device, vehicular navigational device.
20. A device comprising:
(a) a receiver for receiving signals from a plurality of sources;
(b) circuitry for determining for each of a plurality of locations of said device a set of positional data from said received signals;
(c) a filter for filtering said positional data, comprising:
circuitry for detecting a jump between consecutive positional data if the speed between the consecutive positional data exceeds a predetermined threshold; and
circuitry for correcting the jump with a processor as a function of the angle and the speed between the consecutive positional data,
wherein said circuitry for correcting the jump comprises circuitry for correcting the jump as a function of the following vector relationship:
vector T ={s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[cos(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* x+{s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[sin(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* y ; and
(d) circuitry for comparing said filtered positional data with data from a road network database to provide an estimated location of said device, said comparing being a function of:
(i) a distance from at least one point defined by a set of said filtered positional data to a road in said road network database, and
(ii) an angle between a line representing a best fit for plural points defined by corresponding plural sets of said filtered positional data to a line defined by a road in said road network database.
21. The device of claim 20 wherein said positional data comprises both current and past positional data of said device.
22. The device of claim 20 wherein said positional data is selected from the group consisting of latitude, longitude, time of data, number of visible positional satellites, HDOP, altitude, and positional mode information.
23. The device of claim 20 wherein said road network database comprises map-related information is selected from the group consisting of latitudes and longitudes of roads, permissible direction of travel on a road, speed limits, allowable turns from a road, curvature of a road, and topographical data.
24. The device of claim 20 wherein the circuitry for comparing further comprises:
(i) circuitry for identifying positional data having a time of data less than a predetermined threshold;
(ii) circuitry for reducing candidate roads for the estimated location as a function of a predetermined distance from said identified positional data;
(iii) circuitry for computing distance probabilities as a function of the identified positional data and reduced candidate roads; and
(iv) circuitry for computing angle probabilities as a function of identified positional data being on a candidate road based upon the direction of the road and direction of travel of the device.
25. The device of claim 20 wherein at least one of said plurality of sources is a satellite that is a part of a Global Navigation Satellite System (“GNSS”).
26. The device of claim 25 wherein the GNSS is selected from the group consisting of: Global Positioning System (“GPS”), Galileo, GLONASS, and Quasi-Zenith Satellite System (“QZSS”).
27. The device of claim 20 wherein the device is selected from the group consisting of: cellular device, text messaging device, computer, portable computer, vehicle locating device, vehicle security device, communication device, wireless transceiver, hand-held navigational device, vehicular navigational device.
28. A system for estimating the location of a mobile station that receives signals from a plurality of sources, comprising:
(a) a receiver for receiving signals from a plurality of transmission sources;
(b) circuitry for determining for each of a plurality of locations of mobile station a set of positional data from said received signals;
(c) a filter for filtering said positional data, comprising:
circuitry for detecting a jump between consecutive positional data if the speed between the consecutive positional data exceeds a predetermined threshold; and
circuitry for correcting the jump with a processor as a function of the angle and the speed between the consecutive positional data,
wherein said circuitry for correcting the jump comprises circuitry for correcting the jump as a function of the following vector relationship:
vector T ={s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[cos(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* x+{s 1 +[( s 2 −s 1 )/( N− 1)]* T }*[sin(θ 1 +((θ 2 −θ 1 )/( N− 1))* T )]* y ; and
(d) circuitry for comparing said filtered positional data with data from a road network database to provide an estimated location of said mobile station, said comparing being a function of:
(i) a distance from at least one point defined by a set of said filtered positional data to a road in said road network database, and
(ii) an angle between a line representing a best fit for plural points defined by corresponding plural sets of said filtered positional data to a line defined by a road in said road network database.
29. The system of claim 28 wherein at least one of said plural sources is a satellite.
30. The system of claim 29 where the satellite is a part of a Global Navigation Satellite System (“GNSS”).
31. The system of claim 30 wherein the GNSS is selected from the group consisting of: Global Positioning System (“GPS”), Galileo, GLONASS, and Quasi-Zenith Satellite System (“QZSS”).
32. The system of claim 28 wherein at least one of said plural sources is a base station.
33. The system of claim 28 wherein the mobile station is selected from the group consisting of: cellular device, text messaging device, computer, portable computer, vehicle locating device, vehicle security device, communication device, wireless transceiver, hand-held navigational device, vehicular navigational device.
34. The system of claim 28 wherein said system is selected from the group consisting of: Universal Mobile Telecommunications System (“UMTS”) network, Worldwide Interoperability for Microwave Access (“WiMax”) network, Global System for Mobile Communications (“GSM”) network, WiFi network, Code Division Multiple Access (“CDMA”) network.
35. The system of claim 34 wherein said system operates under a standard selected from the group consisting of: IS-95, Evolution-Data Optimized (“EDVO”), CDMA2000, and 1 times Radio Transmission Technology (“1×RTT”).