Positioning network availability and reliability based routing

• US 8,645,060 B2
• Filed: 09/07/2010
• Issued: 02/04/2014
• Est. Priority Date: 09/07/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Venkatraman, SaiPradeep
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): PECHE, JORGE O
• Application Number:
  US12/876,453
• Publication Number:
  US 20120059578A1
• Time in Patent Office: 1,246 Days
• Field of Search: 701/411, 701/412, 701/420, 701/421, 701/468, 455/456.3, 455/456.1, 455/456.2
• US Class Current: 701/468
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01S 19/28 Satellite selection
• CPC Class Codes: G01S 19/39 the satellite radio beacon positioning system transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO
• CPC Class Codes: G01S 19/396 Determining accuracy or reliability of position or pseudorange measurements

Abstract

A routing system can be configured to determine a route based on availability and reliability of location reference devices to determine a most reliable route between a source and a destination. Visibility information that is indicative of availability of at least a threshold number of location reference devices along the route can be determined. For each of a plurality of routes between the source and the destination, a reliability rating associated with the route can be determined based on the visibility information associated with the route. The reliability rating is indicative of a reliability of the route and an ability of the routing system to maintain continuous connectivity to the at least the threshold number of location reference devices along the route. The reliability ratings of the plurality of routes are compared to identify and to present one of the plurality of routes with a highest reliability rating.

Claims

1. A method comprising:

determining, at a navigation device, a plurality of routes between a source location and a destination location;

for each of the plurality of routes,

determining visibility information associated with the route, wherein the visibility information is indicative of availability of a threshold number of navigation satellites along the route, wherein the navigation satellites communicate reference signals that enable estimating a position of the navigation device;

determining a reliability rating of the route based, at least in part, on the visibility information associated with the route, wherein the reliability rating is indicative of an ability of the navigation device to maintain continuous connectivity to the threshold number of navigation satellites along the route;

comparing the reliability ratings of the plurality of routes to identify a first route of the plurality of routes with a preferred reliability rating; and

presenting the first route with the preferred reliability rating at the navigation device.

2. The method of claim 1, further comprising:

for each of the plurality of routes, determining an additional route characteristic of the route in addition to the reliability rating;

presenting a subset of the plurality of routes at the navigation device including the reliability rating of the subset of the routes and the additional route characteristic of the subset of the routes;

receiving a user selection of one of the subset of the routes; and

presenting the selected route at the navigation device.

3. The method of claim 1, wherein said determining the visibility information associated with each of the plurality of routes, comprises:

for each of the plurality of routes,

determining a plurality of route segments associated with the route, wherein each of the plurality of route segments comprises a subset of the route;

determining visibility information associated with each of the plurality of route segments; and

combining the visibility information associated with each of the plurality of route segments for said determining the reliability rating of the route.

4. The method of claim 3, wherein said determining the visibility information associated with each of the plurality of route segments for each of the plurality of routes comprises:

for each of the plurality of route segments and for each of the plurality of routes,

receiving the visibility information associated with the route segment from a centralized location server, or

calculating the visibility information associated with the route segment at the navigation device.

5. The method of claim 1, wherein the location reference communication devices comprises one or more of a navigation satellite of a satellite navigation system, an access point in a wireless communication network, and a base station in a cellular network.

6. The method of claim 1, wherein the visibility information is indicative of a quality of the reference signals received from the navigation satellites.

7. The method of claim 1, wherein said determining the visibility information comprises:

for each of the plurality of routes,

identifying a plurality of navigation satellites that are visible above a predetermined mask angle associated with the navigation device at each of a plurality of sample points along the route; and

for each of the plurality of sample points along the route, analyzing each of the plurality of navigation satellites to determine whether to use the navigation satellite for navigating the navigation device.

8. The method of claim 7, wherein for each of the plurality of routes and for each of the plurality of sample points along the route, said analyzing each of the plurality of navigation satellites further comprises:

determining coordinates of the navigation device and coordinates of the navigation satellite;

determining an elevation angle and an azimuth angle to the navigation satellite based, at least in part, on the coordinates of the navigation device and the coordinates of the navigation satellite; and

determining whether an obstacle is located in a line-of-sight path between the navigation device and the navigation satellite based, at least in part, on location coordinates of each of a plurality of obstacles, an elevation of each of the plurality of obstacles, the elevation angle and the azimuth angle to the navigation satellite, the coordinates of the navigation device, and the coordinates of the navigation satellite.

9. The method of claim 8, wherein for each of the plurality of routes and for each of the plurality of sample points along the route, said determining whether the obstacle is located in the line-of-sight path between the navigation device and the navigation satellite further comprises:

determining that the navigation satellite is unavailable and cannot be used for navigating the navigation device, in response to determining that the obstacle is located in the line-of-sight path between the navigation device and the navigation satellite; and

determining that the navigation satellite is available and can be used for navigating the navigation device, in response to determining that there are no obstacles in the line-of-sight path between the navigation device and the navigation satellite.

10. The method of claim 1, further comprising:

for each of the plurality of routes,

determining whether the threshold number of navigation satellites are visible to the navigation device at each of a plurality of sample points along the route;

determining a first reliability rating associated with the route in response to determining that the threshold number of navigation satellites are visible to the navigation device at each of the plurality of sample points along the route; and

determining a second reliability rating associated with the route, in response to determining that the threshold number of navigation satellites are not visible to the navigation device at each of the plurality of sample points along the route, wherein the first reliability rating indicates greater reliability than the second reliability rating.

11. The method of claim 10, further comprising:

in response to determining that the threshold number of navigation satellites are not visible to the navigation device at each of the plurality of sample points along the route, determining whether connectivity to a second threshold number of access points of a wireless communication network is available;

determining that the route between the source location and the destination location is not reliable based, at least in part, on determining that the threshold number of navigation satellites are not visible to the navigation device along the route and determining that connectivity to the second threshold number of access points is not available; and

calculating the second reliability rating of the route based on at least one of visibility information associated with at least one navigation satellite visible to the navigation device and visibility information associated with at least one access point, in response to determining that connectivity to the second threshold number of access points is available.

12. The method of claim 11,

wherein the visibility information associated with the at least one access point is indicative of a quality of reference signals received from the at least one access point, and

wherein determining the visibility information associated with the at least one access point for calculating the second reliability rating of the route comprises determining at least one of an effect of multipath and attenuation on the reference signals, a number of the access points available along the route, a distribution of the at least one access point along the route, a distance between the one or more access points and the navigation device, a strength of the reference signals, and authentication of the navigation device at at least one access point.

13. The method of claim 1, further comprising:

determining that the visibility information associated with the first route between the source location and the destination location is not available from a centralized location server;

determining, at the navigation device, the visibility information associated with the first route; and

communicating the visibility information associated with the first route to the centralized location server.

14. The method of claim 1, wherein said presenting the first route comprises presenting the first route with the preferred reliability rating on a display unit of the navigation device.

15. The method of claim 1, wherein for each of the plurality of routes, said determining the visibility information associated with the route comprises determining one or more of dilution of precision, multipath, availability of the navigation satellites, positioning accuracy, number of navigation satellites that are visible to the navigation device, signal to noise ratio, elevation angles, and impact of time of day on the reference signals.

16. A navigation device comprising:

a processor;

a routing unit coupled with the processor, the routing unit operable to;

determine a plurality of routes between a source location and a destination location;

a route reliability calculation unit coupled with the processor, the route reliability calculation unit operable to;

for each of the plurality of routes,

determine visibility information associated with the route, wherein the visibility information is indicative of availability of a threshold number of navigation satellites along the route, wherein the navigation satellites communicate reference signals that enable estimating a position of the navigation device; and

determine a reliability rating of the route based, at least in part, on the visibility information associated with the route, wherein the reliability rating is indicative of an ability of the navigation device to maintain continuous connectivity to the threshold number of navigation satellites along the route; and

the routing unit further operable to;

compare the reliability ratings of the plurality of routes to identify a first route of the plurality of routes with a preferred reliability rating; and

present the route with the preferred reliability rating at the navigation device.

17. The navigation device of claim 16, wherein the routing unit is further operable to:

determine an additional route characteristic of each of the plurality of routes in addition to the reliability rating;

present a subset of the plurality of routes at the navigation device including the reliability rating of the subset of the routes and the additional route characteristic of the subset of the routes;

receive a user selection of one of the subset of the routes; and

present the selected route at the navigation device.

18. The navigation device of claim 16, wherein the route reliability calculation unit operable to determine the visibility information associated with each of the plurality of routes, comprises the route reliability calculation unit operable to:

for each of the plurality of routes,

determine a plurality of route segments associated with the route, wherein each of the plurality of route segments comprises a subset of the route;

determine visibility information associated with each of the plurality of route segments; and

combine the visibility information associated with each of the plurality of route segments for the route reliability calculation unit to determine the reliability rating of the route.

19. The navigation device of claim 16, wherein the route reliability calculation unit operable to determine the visibility information comprises the route reliability calculation unit operable to:

for each of the plurality of routes,

identify a plurality of navigation satellites that are visible above a predetermined mask angle associated with the navigation device at each of a plurality of sample points along the route; and

for each of the plurality of sample points along the route, analyze each of the plurality of navigation satellites to determine whether to use the navigation satellite for navigating the navigation device.

20. The navigation device of claim 19, wherein for each of the plurality of routes and for each of the plurality of sample points along the route, the route reliability calculation unit operable to analyze each of the plurality of navigation satellites further comprises the route reliability calculation unit operable to:

determine coordinates of the navigation device and coordinates of the navigation satellite;

determine an elevation angle and an azimuth angle to the navigation satellite based, at least in part, on the coordinates of the navigation device and the coordinates of the navigation satellite; and

determine whether an obstacle is located in a line-of-sight path between the navigation device and the navigation satellite based, at least in part, on the elevation angle and the azimuth angle to the navigation satellite.

21. The navigation device of claim 20, wherein for each of the plurality of routes and for each of the plurality of sample points along the route, the route reliability calculation unit operable to determine whether the obstacle is located in the line-of-sight path comprises the route reliability calculation unit operable to:

determine that the navigation satellite is unavailable and cannot be used for navigating the navigation device, in response to determining that the obstacle is located in the line-of-sight path between the navigation device and the navigation satellite; and

determine that the navigation satellite is available and can be used for navigating the navigation device, in response to determining that there are no obstacles in the line-of-sight path between the navigation device and the navigation satellite.

22. The navigation device of claim 16, wherein the route reliability calculation unit is further operable to:

for each of the plurality of routes,

determine whether the threshold number of navigation satellites are visible to the navigation device along the route at each of a plurality of sample points along the route;

determine a first reliability rating associated with the route in response to the route reliability calculation unit determining that the threshold number of navigation satellites are visible to the navigation device along the route at each of the plurality of sample points along the route; and

determine a second reliability rating associated with the route, in response to the route reliability calculation unit determining that the threshold number of navigation satellites are not visible to the navigation device along the route at each of the plurality of sample points along the route, wherein the first reliability rating indicates greater reliability than the second reliability rating.

23. The navigation device of claim 22, wherein the route reliability calculation unit is further operable to:

in response to the route reliability calculation unit determining that the threshold number of navigation satellites are not visible to the navigation device at each of the plurality of sample points along the route, determine whether connectivity to a second threshold number of access points of a wireless communication network is available;

determine that the route between the source location and the destination location is not reliable based, at least in part, on the route reliability calculation unit determining that the threshold number of navigation satellites are not visible to the navigation device along the route and that connectivity to the second threshold number of access points is not available; and

calculate the second reliability rating of the route based on at least one of visibility information associated with at least one navigation satellite visible to the navigation device and visibility information associated with at least one access point, in response to the route reliability calculation unit determining that connectivity to the second threshold number of access points is available.

24. The navigation device of claim 16, further comprising a display unit, wherein the routing unit operable to present the first route comprises the routing unit operable to present the first route with the preferred reliability rating on the display unit of the navigation device.

25. A non-transitory machine-readable storage medium, having instructions stored therein, which, when executed by a processor causes the processor to perform operations that comprise:

determining a plurality of routes between a source location and a destination location;

for each of the plurality of routes,

determining visibility information associated with the route, wherein the visibility information is indicative of availability of a threshold number of navigation satellites along the route, wherein the navigation satellites communicate reference signals that enable estimating a position of a navigation device;

determining a reliability rating of the route based, at least in part, on the visibility information associated with the route, wherein the reliability rating is indicative of and an ability of the navigation device to maintain continuous connectivity to the threshold number of navigation satellites along the route;

comparing the reliability ratings of the plurality of routes to identify a first route of the plurality of routes with a preferred reliability rating; and

presenting the first route with the preferred reliability rating at the navigation device.

26. The machine-readable storage medium of claim 25, wherein said operation of determining the visibility information associated with each of the plurality of routes, comprises:

for each of the plurality of routes,

determining a plurality of route segments associated with the route, wherein each of the plurality of route segments comprises a subset of the route;

determining visibility information associated with each of the plurality of route segments; and

combining the visibility information associated with each of the plurality of route segments for determining the reliability rating of the route.

27. The machine-readable storage medium of claim 25, wherein said operation of determining the visibility information comprises:

for each of the plurality of routes,

identifying a plurality of navigation satellites that are visible above a predetermined mask angle associated with the navigation device at each of a plurality of sample points along the route; and

for each of the plurality of sample points along the route, analyzing each of the plurality of navigation satellites to determine whether to use the navigation satellite for navigating the navigation device.

28. The machine-readable storage medium of claim 27, wherein, for each of the plurality of routes and for each of the plurality of sample points along the route, said operation of analyzing each of the plurality of navigation satellites further comprises:

determining coordinates of the navigation device and coordinates of the navigation satellite;

determining an elevation angle and an azimuth angle to the navigation satellite based, at least in part, on the coordinates of the navigation device and the coordinates of the navigation satellite; and

determining whether an obstacle is located in a line-of-sight path between the navigation device and the navigation satellite based, at least in part, on the elevation angle and the azimuth angle to the navigation satellite.

29. The machine-readable storage medium of claim 28, wherein for each of the plurality of routes and for each of the plurality of sample points along the route, said operation of determining whether the obstacle is located in the line-of-sight path between the navigation device and the navigation satellite further comprises:

determining that the navigation satellite is unavailable and cannot be used for navigating the navigation device, in response to determining that the obstacle is located in the line-of-sight path between the navigation device and the navigation satellite; and

determining that the navigation satellite is available and can be used for navigating the navigation device, in response to determining that there are no obstacles in the line-of-sight path between the navigation device and the navigation satellite.

30. The machine-readable storage medium of claim 25, wherein the operations further comprise:

for each of the plurality of routes,

determining whether the threshold number of navigation satellites are visible to the navigation device at each of a plurality of sample points along the route;

determining a first reliability rating associated with the route in response to determining that the threshold number of navigation satellites are visible to the navigation device at each of the plurality of sample points along the route; and

determining a second reliability rating associated with the route, in response to determining that the threshold number of navigation satellites are not visible to the navigation device at each of the plurality of sample points along the route, wherein the first reliability rating indicates greater reliability than the second reliability rating.

31. The machine-readable storage media of claim 30, wherein the operations further comprise:

determining whether connectivity to a second threshold number of access points of a wireless communication network is available in response to determining that the threshold number of navigation satellites are not visible to the navigation device at each of the plurality of sample points along the route;

determining that the route between the source location and the destination location is not reliable based, at least in part, on determining that the threshold number of navigation satellites are not visible to the navigation device along the route and determining that connectivity to the second threshold number of access points is not available; and

calculating the reliability rating of the route based on at least one of visibility information associated with at least one navigation satellite visible to the navigation device and visibility information associated with at least one access point, in response to determining that connectivity to the second threshold number of access points is available.