Method and apparatus for hierarchical map tiling

• US 9,247,379 B2
• Filed: 01/27/2014
• Issued: 01/26/2016
• Est. Priority Date: 01/27/2014
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Chen, Yin, Pakzad, Payam, Holm, Eric K.
• Primary Examiner(s): DOAN, KIET M
• Application Number:
  US14/165,386
• Publication Number:
  US 20150215731A1
• Time in Patent Office: 729 Days
• Field of Search: 455/456.1, 455/67.7, 455/440, 455/456.3, 455/417, 370/338, 370/310, 702/150, 702/321, 379/265.11, 340/928, 340/573.4, 715/728, 718/103
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02523 Details of interaction of receiver with radio-map
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A method for processing assistance data associated with positioning of a mobile device as described herein includes estimating an initial location of the mobile device within an area; designating the initial location of the mobile device as a focal point; retrieving a subset of hierarchical assistance data as a function of the focal point; and generating a multi-level assistance data structure for the area centered at the focal point.

Claims

1. A method for processing assistance data associated with positioning of a mobile device, the method comprising:

estimating an initial location of the mobile device within an area;

retrieving a subset of hierarchical assistance data associated with the area based on the initial location of the mobile device, wherein a resolution of the retrieved subset of the hierarchical assistance data changes as a function of a distance from the initial location of the mobile device; and

generating a multi-level assistance data structure, for the area, centered at the initial location of the mobile device using the retrieved subset of the hierarchical assistance data wherein the hierarchical assistance data comprise a plurality of levels having mutually distinct resolutions, each level of the plurality of levels including assistance data for an arrangement of points within the area defined according to the resolution for the each level.

2. The method of claim 1 further comprising:

computing an updated location of the mobile device based on the multi-level assistance data structure; and

updating the multi-level assistance data structure if the updated location is outside of a first region within the area or a determined accuracy of the updated location is below a threshold by designating the updated location as the initial location and repeating at least one of the retrieving or the generating.

3. The method of claim 1 wherein generating the multi-level assistance data structure comprises:

populating a first region within the area, the first region spanning a predefined distance from the initial location, with respective first ones of the retrieved subset of the hierarchical assistance data; and

populating at least a second region within the area, the second region being located outside the first region, with respective second ones of the retrieved subset of the hierarchical assistance data that are different from the first ones of the retrieved subset of the hierarchical assistance data.

4. The method of claim 3 wherein:

the first ones of the retrieved subset of the hierarchical assistance data are associated with a first level thereof and a first resolution; and

the second ones of the retrieved subset of the hierarchical assistance data are associated with at least a second level thereof and at least a second resolution that is coarser than the first resolution.

5. The method of claim 1 wherein:

a finest resolution associated with the hierarchical assistance data is based on a signal measurement accuracy for a communications system associated with the area; and

at least one of the plurality of levels of the hierarchical assistance data or one or more resolutions associated with the hierarchical assistance data are based on at least one of network transfer limitations associated with the area or mobile device operating capacity.

6. The method of claim 1 wherein each of the plurality of levels of the hierarchical assistance data are associated with a rectangular grid, the rectangular grid comprising points spaced apart at an interval defined by the resolution for the level.

7. The method of claim 1 wherein:

the method further comprises storing the hierarchical assistance data at a storage device at the mobile device; and

the retrieving comprises loading the retrieved subset of the hierarchical assistance data into a working memory of the mobile device.

8. The method of claim 1 wherein the retrieving comprises receiving the retrieved subset of the hierarchical assistance data over a communications network associated with the area.

9. A mobile device operable in a wireless communication network, the mobile device comprising:

a location estimation module configured to estimate an initial location of the mobile device within an area;

an assistance data retrieval module communicatively coupled to the location estimation module and configured to retrieve a subset of hierarchical assistance data associated with the area based on the initial location of the mobile device, wherein a resolution of the retrieved subset of hierarchical assistance data changes as a function of a distance from the initial location of the mobile device; and

an assistance data population module communicatively coupled to the assistance data retrieval module and configured to generate a multi-level assistance data structure, for the area, centered at the initial location of the mobile device using the retrieved subset of the hierarchical assistance data, wherein the hierarchical assistance data comprise a plurality of levels having mutually distinct resolutions, each level of the plurality of levels including assistance data for an arrangement of points within the area defined according to the resolution for the each level.

10. The mobile device of claim 9 wherein:

the location estimation module is further configured to compute an updated location of the mobile device based on the multi-level assistance data structure;

the mobile device further comprises a location comparator module communicatively coupled to the location estimation module and the assistance data retrieval module and configured to compare the initial location to the updated location; and

the assistance data retrieval module is further configured to retrieve an updated subset of hierarchical assistance data associated with the area based on the updated location of the mobile device if the initial location of the mobile device and the updated location of the mobile device differ by at least a threshold amount.

11. The mobile device of claim 10 wherein:

the location comparator module is further configured to determine an accuracy associated with the updated location; and

the assistance data retrieval module is further configured to retrieve the updated subset of hierarchical assistance data associated with the area based on the updated location of the mobile device if the accuracy associated with the updated location is below a threshold.

12. The mobile device of claim 10 wherein the assistance data population module is configured to generate the multi-level assistance data structure by populating a first region within the area, the first region spanning a predefined distance from the initial location, with respective first ones of the retrieved subset of the hierarchical assistance data and populating at least a second region within the area, the second region being located outside the first region, with respective second ones of the retrieved subset of the hierarchical assistance data that are different from the first ones of the retrieved subset of the hierarchical assistance data.

13. The mobile device of claim 12 wherein:

the first ones of the retrieved subset of the hierarchical assistance data are associated with a first level thereof and a first resolution; and

the second ones of the retrieved subset of the hierarchical assistance data are associated with at least a second level thereof and at least a second resolution that is coarser than the first resolution.

14. The mobile device of claim 9 wherein:

a finest resolution associated with the hierarchical assistance data is based on a signal measurement accuracy for the wireless communication network; and

at least one of the plurality of levels of the hierarchical assistance data or one or more resolutions associated with the hierarchical assistance data are based on at least one of network transfer limitations associated with the area or an operating capacity of the mobile device.

15. The mobile device of claim 9 wherein each of the plurality of levels of the hierarchical assistance data are associated with a rectangular grid, the rectangular grid comprising points spaced apart at an interval defined by the respective resolution for the level.

16. The mobile device of claim 15 wherein resolutions for respective ones of the plurality of levels are associated with exponentially increasing intervals.

17. The mobile device of claim 9 wherein:

the mobile device further comprises a working memory and a local storage unit communicatively coupled to the working memory and the assistance data retrieval module and configured to store the hierarchical assistance data; and

the assistance data retrieval module is further configured to instruct loading of the retrieved subset of the hierarchical assistance data from the local storage unit to the working memory.

18. The mobile device of claim 9 wherein:

the mobile device further comprises a transceiver communicatively coupled to the assistance data retrieval module; and

the assistance data retrieval module is further configured to instruct communication of the retrieved subset of the hierarchical assistance data to the mobile device over the wireless communication network via the transceiver.

19. An apparatus for processing assistance data associated with a positioning operation, the apparatus comprising:

means for estimating an initial location of the apparatus within an area;

means for retrieving a subset of hierarchical assistance data associated with the area based on the initial location of the apparatus, wherein a resolution of the retrieved subset of hierarchical assistance data changes as a function of a distance from the initial location of the apparatus; and

means for generating a multi-level assistance data structure for the area centered at the initial location of the apparatus using the retrieved subset of the hierarchical assistance data, wherein the hierarchical assistance data comprise a plurality of levels having mutually distinct resolutions, each level of the plurality of levels including assistance data for an arrangement of points within the area defined according to the resolution for the each level.

20. The apparatus of claim 19 wherein the means for generating comprises:

means for populating a first region within the area, the first region spanning a predefined distance from the initial location, with respective first ones of the retrieved subset of the hierarchical assistance data; and

means for populating at least a second region within the area, the second region being located outside the first region, with respective second ones of the retrieved subset of the hierarchical assistance data that are different from the first ones of the retrieved subset of the hierarchical assistance data.

21. The apparatus of claim 20 wherein:

the first ones of the retrieved subset of the hierarchical assistance data are associated with a first level thereof and a first resolution; and

the second ones of the retrieved subset of the hierarchical assistance data are associated with at least a second level thereof and at least a second resolution that is coarser than the first resolution.

22. The apparatus of claim 19 wherein:

the apparatus further comprises means for locally storing the hierarchical assistance data; and

the means for retrieving comprises means for loading the retrieved subset of the hierarchical assistance data into a working memory of the apparatus.

23. The apparatus of claim 19 wherein the means for retrieving comprises means for receiving the retrieved subset of the hierarchical assistance data over a communications network associated with the area.

24. A mobile communications device comprising:

at least one processor configured to execute instructions which, when executed, cause the at least one processor to;

estimate an initial location of the mobile communications device within an area;

retrieve a subset of hierarchical assistance data associated with the area based on the initial location of the mobile communications device, wherein a resolution of the retrieved subset of hierarchical assistance data changes as a function of a distance from the initial location of the mobile communications device; and

generate a multi-level assistance data structure, for the area, centered at the initial location of the mobile communications device using the retrieved subset of the hierarchical assistance data, wherein the hierarchical assistance data comprise a plurality of levels having mutually distinct resolutions, each level of the plurality of levels including assistance data for an arrangement of points within the area defined according to the resolution for the each level; and

a memory coupled to the at least one processor and configured to store the instructions.

25. The mobile communications device of claim 24 wherein the instructions further comprise instructions which, when executed, cause the at least one processor to generate the multi-level assistance data structure by populating a first region within the area, the first region spanning a predefined distance from the initial location, with respective first ones of the retrieved subset of the hierarchical assistance data and populating at least a second region within the area, the second region being located outside the first region, with respective second ones of the retrieved subset of the hierarchical assistance data that are different from the first ones of the retrieved subset of the hierarchical assistance data.

26. The mobile communications device of claim 24 wherein:

the first ones of the retrieved subset of the hierarchical assistance data are associated with a first level thereof and a first resolution; and

the second ones of the retrieved subset of the hierarchical assistance data are associated with at least a second level thereof and at least a second resolution that is coarser than the first resolution.