Encoding and compression of a location beacon database

• US 7,502,620 B2
• Filed: 03/01/2006
• Issued: 03/10/2009
• Est. Priority Date: 03/04/2005
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Shyhook Wireless Incorporated
• Inventors: Morgan, Edward James, Payne, Andrew C.
• Primary Examiner(s): Le; Danh C
• Application Number:
  US11/365,540
• Publication Number:
  US 20060200843A1
• Time in Patent Office: 1,105 Days
• Field of Search: 455/456.6, 455/456.5, 455/456.1, 370/328, 709/224, 701/214
• US Class Current: 455/456.6
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

A method of delta-encoding and compressing a table containing 6-byte MAC addresses is provided. The MAC addresses are sorted, a first MAC address is stored, and only the binary differences between succeeding MAC addresses are stored. A method of reading a delta-encoded and compressed MAC address table is provided. A first unencoded MAC address is read. The remaining MAC addresses are generated by successively adding stored binary differences to the result of the previous addition. A method of encoding and compressing a location table is provided. A reference latitude and longitude is selected and stored. The offsets from the reference latitude and longitude are stored for the remaining locations. A method of reading an encoded location table is provided. A stored reference latitude and longitude is read. Stored offsets are read and applied to the reference latitude and longitude to generate a set of latitude and longitude locations.

Claims

1. In a location-based services system having a reference database of Wi-Fi access points in a target area, each access point in the target area identified by a corresponding fixed size MAC address and each Wi-Fi access point positioned at a corresponding geographical location, a method of encoding MAC addresses and geographical locations of the access points to facilitate storage or transmission of the database contents to Wi-Fi enabled devices using the system, the method comprising the acts of:

(a) storing as an entry of the database a reset address entry, said reset address entry including a fixed-size MAC address and marker information to indicate that the entry has a complete MAC address for a corresponding access point;

(b) for each access point in at least a subset of access points in the target area, encoding a mathematical difference between (i) the MAC address of a corresponding access point and (ii) one of the other MAC addresses represented in the database, and storing said encoding, as delta information, in a corresponding delta address entry of the database, said delta address entry further including marker information to indicate that the entry has delta information from which a complete MAC address for a corresponding access point can be reconstituted; and

(c) for each entry in the database, including information to represent the geographical location of the corresponding access point.

2. The method of claim 1, further including storing multiple reset address entries, each reset address defining a boundary of a set of MAC addresses that are delta encoded.

3. The method of claim 1, wherein act (b) encodes the difference between a corresponding MAC address and the MAC address of one of the reset addresses.

4. The method of claim 1, wherein act (b) encodes the difference between a corresponding MAC address and a reconstituted MAC address, said reconstituted MAC address being represented in the database as delta information.

5. The method of claim 1, wherein delta information is encoded into a selected one of multiple delta address formats, each delta format having a corresponding storage size different than the storage sizes of the other delta formats and different than the fixed size, and wherein each delta format has an unique marker information to distinguish itself from the other delta formats.

6. The method of claim 5, wherein each delta format corresponds to a unique range of difference values.

7. The method of claim 6, wherein the unique range of difference values is 1 to 128, the storage size is 1 byte, and the delta format begins with a 0 in a left-most bit position of the 1 byte.

8. The method of claim 6, wherein the unique range of difference values is 129 to 16512, the storage size is 2 bytes, and the delta format begins with a 1 followed by a 0 in two left-most bit positions.

9. The method of claim 6, wherein the unique range of difference values is 16513 to 2113664, the storage size is 3 bytes, and the delta format begins with a 1 followed by a 1, followed by a 0 in three left-most bit positions.

10. The method of claim 6, wherein the MAC address of a corresponding access point is coded as a reset address if the mathematical difference is greater than 2113664.

11. The method of claim 1, wherein the information to represent geographical location includes cluster identification information to identify a cluster having a known corresponding longitude and latitude, and further includes a longitude offset value and latitude offset value, the longitude offset value encoding the distance from the access point longitude to the known longitude of the identified cluster, and a latitude offset value to represent the distance from the access point latitude to the identified cluster latitude.

12. In a location-based services system having a reference database of Wi-Fi access points in a target area, each access point in the target area identified by a corresponding fixed size MAC address and each Wi-Fi access point positioned at a corresponding geographical location, a method of encoding MAC addresses and geographical locations of the access points to facilitate storage or transmission of the database contents to Wi-Fi enabled devices using the system, the method comprising the acts of:

(a) storing cluster identification information to identify a cluster having a known corresponding longitude and latitude;

(b) for each access point in at least a subset of access points in the target area, storing a longitude offset value and latitude offset value, the longitude offset value encoding the distance from the access point longitude to the known longitude of the identified cluster, and a latitude offset value to represent the distance from the access point latitude to the identified cluster latitude; and

(c) for each entry in the database, including information to represent the MAC address of the corresponding access point.

13. The method of claim 12, further including storing multiple cluster identification information records, each record defining the known corresponding longitude and latitude for use in act (b) with a subset of access points.

14. The method of claim 13, wherein access points are placed into subsets on the basis of the access points'"'"' geographic location.

15. A Wi-Fi enabled device comprising:

(a) first logic to determine the MAC addresses of Wi-Fi access points in the vicinity of the Wi-Fi enabled device, by exchanging Wi-Fi messages with Wi-Fi access points in the vicinity of the Wi-Fi enabled device;

(b) second logic to query a reference database of Wi-Fi access points, using the MAC addresses determined by the first logic, said second logic retrieving from the database information representing at least the physical location for each MAC address-identified Wi-Fi access point in the database; and

(c) third logic, using the queried physical location information from the second logic, to calculate the position of the Wi-Fi enabled device;

(d) wherein said reference database includes a reset entry having a complete MAC address for at least one Wi-Fi access point and includes a plurality of delta entries, each delta entry having a mathematical encoding representing a difference between the MAC address of a corresponding Wi-Fi access point and another MAC address represented in the database, each entry in the database further including information representing the physical location of a corresponding Wi-Fi access point.

16. The Wi-Fi enabled device of claim 15, wherein the reference database is for a target geographical area and is stored on the Wi-Fi enabled device.

17. The Wi-Fi enabled device of claim 15, the reference database further including multiple reset entries, each reset entry defining a boundary of a set of MAC addresses that are delta encoded.

18. The Wi-Fi enabled device of claim 15, wherein the other MAC address represented in the database is one of the reset addresses.

19. The Wi-Fi enabled device of claim 15, wherein the other MAC address represented in the database is a reconstituted MAC address, said reconstituted MAC address being represented in the database as delta information.

20. The Wi-Fi enabled device of claim 15, wherein the delta entries are encoded into a selected one of multiple delta address formats, each delta format having a corresponding storage size different than the storage sizes of the other delta formats and different than the fixed size, and wherein each delta format has a unique marker information to distinguish itself from the other delta formats.

21. The Wi-Fi enabled device of claim 20, wherein each delta format corresponds to a unique range of difference values.

22. The Wi-Fi enabled device of claim 21, wherein the unique range of difference values is 1 to 128, the storage size is 1 byte, and the delta format begins with a 0 in a left-most bit position of the 1 byte.

23. The Wi-Fi enabled device of claim 21, wherein the unique range of difference values is 129 to 16512, the storage size is 2 bytes, and the delta format begins with a 1 followed by a 0 in two left-most bit positions.

24. The Wi-Fi enabled device of claim 21, wherein the unique range of difference values is 16513 to 2113664, the storage size is 3 bytes, and the delta format begins with a 1 followed by a 1, followed by a 0 in three left-most bit positions.

25. The Wi-Fi enabled device of claim 21, wherein the MAC address of a corresponding access point is coded as a reset address if the mathematical difference is greater than 2113664.