POSITIONING NETWORK AVAILABILITY AND RELIABILITY BASED ROUTING

• US 20120059578A1
• Filed: 09/07/2010
• Published: 03/08/2012
• Est. Priority Date: 09/07/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Atheros Communications Incorporated (Qualcomm, Inc.)
• Inventors: Venkatraman, SaiPradeep
• Granted Patent: US 8,645,060 B2
• Time in Patent Office: Days
• US Class Current: 701/411
• 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 routing device, a plurality of routes between a source location and a destination location;

for each of the plurality of routes between the source location and the destination location,

determining visibility information associated with the route, wherein the visibility information is indicative of availability of at least a threshold number of location reference communication devices along the route, wherein the location reference communication devices communicate reference signals that enable estimating a position of the routing device;

based on the visibility information associated with the route, calculating a reliability rating of the route, wherein the reliability rating is indicative of a reliability of the route and an ability of the routing device to maintain continuous connectivity to the at least the threshold number of location reference communication devices along the route;

comparing the reliability ratings of the plurality of routes to identify one of the plurality of routes with a highest reliability rating; and

causing at least the route with the highest reliability rating to be presented at the routing device.

2. The method of claim 1, further comprising:

for each of the plurality of routes between the source location and the destination location, determining, in addition to the reliability rating, one or more additional route characteristics of the route;

causing at least a subset of the plurality of routes to be presented at the routing device including an indication of the reliability rating of the subset of the plurality of routes and an indication of the one or more additional route characteristics of the subset of the plurality of routes;

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

causing the selected route to be presented at the routing device.

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

for each of the plurality of routes between the source location and the destination location,

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 calculating the reliability rating of the route.

4. The method of claim 2, wherein said determining the visibility information associated with each of the plurality of route segments for each of the plurality of routes between the source location and the destination location comprises one of:

receiving the visibility information associated with each of the plurality of route segments for each of the plurality of routes between the source location and the destination location from a centralized location server, and

calculating the visibility information associated with each of the plurality of route segments for each of the plurality of routes between the source location and the destination location at the routing 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 location reference communication devices comprise navigation satellites, wherein the visibility information is indicative of a quality of the reference signals received from the navigation satellites, and wherein 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, navigation satellites visible to the routing device, signal to noise ratio, elevation angles, and impact of time of day on the reference signals.

7. The method of claim 1, wherein the location reference communication devices comprises a plurality of navigation satellites, wherein said determining the visibility information associated with each of the plurality of routes between the source location and the destination location comprises:

for each of the plurality of routes between the source location and the destination location,

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

for each of the plurality of navigation satellites, and for each of the plurality of sample points along the route,

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

calculating an elevation angle and an azimuth angle to the navigation satellite based on the coordinates of the routing device and the coordinates of the navigation satellite;

determining whether one or more obstacles are located in a line of sight path between the routing device and the navigation satellite based, at least in part, on the elevation angle and the azimuth angle to the navigation satellite;

determining that the navigation satellite is unavailable and cannot be used for navigating the routing device, in response to determining that one or more obstacles are located in the line of sight path between the routing device and the navigation satellite; and

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

8. The method of claim 7, wherein said determining whether one or more obstacles are located in the line of sight path between the routing device and the navigation satellite comprises identifying the one or more obstacles in the line of sight path from a plurality of obstacles based at least in part, on location coordinates of each of the plurality of obstacles, an elevation of each of the plurality of obstacles, the coordinates of the routing device, and the coordinates of the navigation satellite.

9. The method of claim 7, further comprising:

for each of the plurality of routes between the source location and the destination location,

determining whether at least the threshold number of navigation satellites is visible to the routing device at each of the plurality of sample points along the route;

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

calculating the reliability rating of the route to determine a second reliability rating associated with the route, in response to determining that the threshold number of navigation satellites are not visible to the routing 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.

10. The method of claim 9, further comprising:

in response to determining that the threshold number of navigation satellites are not visible to the routing 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 on determining that the threshold number of navigation satellites are not visible to the routing device along the route and based on determining that the threshold number of navigation satellites are not visible to the routing device along the route; and

calculating the reliability rating of the route based on one or more of visibility information associated with one or more navigation satellites visible to the routing device and visibility information associated with one or more access points of the wireless communication network, in response to determining that connectivity to the second threshold number of access points of the wireless communication network is available.

11. The method of claim 1, further comprising:

determining that the visibility information associated with one or more of the plurality of routes between the source location and the destination location is not available from a centralized location server;

determining, at the routing device, the visibility information associated with the one or more of the plurality of routes; and

communicating the visibility information associated with the one or more of the plurality of routes to the centralized location server.

12. The method of claim 1, wherein the location reference communication devices comprise a plurality of access points located along the route for wireless network communication, wherein the visibility information is indicative of a quality of the reference signals received from the plurality of access points, and wherein said determining visibility information associated with the route comprises determining one or more of effect of multipath and attenuation on the reference signals, a number of the plurality of access points available along the route, a distribution of the plurality of access points along the route, a distance between the plurality of access points and the routing device, a strength of the reference signals, and authentication of the routing device at the plurality of access points.

13. A communication network device comprising:

a routing unit operable to;

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

a route reliability calculation unit operable to;

for each of the plurality of routes between the source location and the destination location,

determine visibility information associated with the route, wherein the visibility information is indicative of availability of at least a threshold number of location reference communication devices along the route, wherein the location reference communication devices communicate reference signals that enable estimating a position of the communication network device;

based on the visibility information associated with the route, calculate a reliability rating of the route, wherein the reliability rating is indicative of a reliability of the route and an ability of the communication network device to maintain continuous connectivity to the at least the threshold number of location reference communication devices along the route; and

the routing unit further operable to;

compare the reliability ratings of the plurality of routes to identify one of the plurality of routes with a highest reliability rating; and

cause at least the route with the highest reliability rating to be presented at the communication network device.

14. The communication network device of claim 13, wherein the routing unit is further operable to:

determine, in addition to the reliability rating, one or more additional route characteristics of each of the plurality of routes between the source location and the destination location;

cause at least a subset of the plurality of routes to be presented at the communication network device including an indication of the reliability rating of the subset of the plurality of routes and an indication of the one or more additional route characteristics of the subset of the plurality of routes;

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

cause the selected route to be presented at the communication network device.

15. The communication network device of claim 13, wherein the route reliability calculation unit operable to determine the visibility information associated with each of the plurality of routes between the source location and the destination location, comprises the route reliability calculation unit operable to:

for each of the plurality of routes between the source location and the destination location,

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 calculate the reliability rating of the route.

16. The communication network device of claim 13, wherein the location reference communication devices comprises a plurality of navigation satellites, wherein the route reliability calculation unit operable to determine the visibility information associated with each of the plurality of routes between the source location and the destination location comprises the route reliability calculation unit operable to:

for each of the plurality of routes between the source location and the destination location,

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

for each of the plurality of navigation satellites, and for each of the plurality of sample points along the route,

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

calculate an elevation angle and an azimuth angle to the navigation satellite based on the coordinates of the communication network device and the coordinates of the navigation satellite;

determine whether one or more obstacles are located in a line of sight path between the communication network device and the navigation satellite based, at least in part, on the elevation angle and the azimuth angle to the navigation satellite;

determine that the navigation satellite is unavailable and cannot be used for navigating the communication network device, in response to the route reliability calculation unit determining that one or more obstacles are located in the line of sight path between the routing communication network device and the navigation satellite; and

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

17. The communication network device of claim 16, wherein the route reliability calculation unit is further operable to:

for each of the plurality of routes between the source location and the destination location,

determine whether at least the threshold number of navigation satellites is visible to the communication network device along the route at each of the 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 at least the threshold number of navigation satellites are visible to the communication network 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 communication network 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.

18. The communication network device of claim 17, 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 communication network 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 on the route reliability calculation unit determining that the threshold number of navigation satellites are not visible to the communication network device along the route and based on the route reliability calculation unit determining that the threshold number of navigation satellites are not visible to the communication network device along the route; and

calculate the reliability rating of the route based on one or more of visibility information associated with one or more navigation satellites visible to the communication network device and visibility information associated with one or more access points of the wireless communication network, in response to the route reliability calculation unit determining that connectivity to the second threshold number of access points of the wireless communication network is available.

19. One or more machine-readable storage media, having instructions stored therein, which, when executed by one or more processors causes the one or more processors 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 between the source location and the destination location,

determining visibility information associated with the route, wherein the visibility information is indicative of availability of at least a threshold number of location reference communication devices along the route, wherein the location reference communication devices communicate reference signals that enable estimating a position of a routing device;

based on the visibility information associated with the route, calculating a reliability rating of the route, wherein the reliability rating is indicative of a reliability of the route and an ability of the routing device to maintain continuous connectivity to the at least the threshold number of location reference communication devices along the route;

comparing the reliability ratings of the plurality of routes to identify one of the plurality of routes with a highest reliability rating; and

causing at least the route with the highest reliability rating to be presented at the routing device.

20. The machine-readable storage media of claim 19, wherein said operation of determining the visibility information associated with each of the plurality of routes between the source location and the destination location, comprises:

for each of the plurality of routes between the source location and the destination location,

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 calculating the reliability rating of the route.

21. The machine-readable storage media of claim 19, wherein the location reference communication devices comprises a plurality of navigation satellites, wherein said operation of determining the visibility information associated with each of the plurality of routes between the source location and the destination location comprises:

for each of the plurality of routes between the source location and the destination location,

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

for each of the plurality of navigation satellites, and for each of the plurality of sample points along the route,

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

calculating an elevation angle and an azimuth angle to the navigation satellite based on the coordinates of the routing device and the coordinates of the navigation satellite;

determining whether one or more obstacles are located in a line of sight path between the routing device and the navigation satellite based, at least in part, on the elevation angle and the azimuth angle to the navigation satellite;

determining that the navigation satellite is unavailable and cannot be used for navigating the routing device, in response to determining that one or more obstacles are located in the line of sight path between the routing device and the navigation satellite; and

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

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

for each of the plurality of routes between the source location and the destination location,

determining whether at least the threshold number of navigation satellites is visible to the routing device at each of the plurality of sample points along the route;

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

calculating a second reliability rating associated with the route, in response to determining that the threshold number of navigation satellites are not visible to the routing 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.

23. The machine-readable storage media of claim 22, 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 routing 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 on determining that the threshold number of navigation satellites are not visible to the routing device along the route and based on determining that the threshold number of navigation satellites are not visible to the routing device along the route; and

calculating the reliability rating of the route based on one or more of visibility information associated with one or more navigation satellites visible to the routing device and visibility information associated with one or more access points of the wireless communication network, in response to determining that connectivity to the second threshold number of access points of the wireless communication network is available.