Methods and systems for signal diffusion modeling for a discretized map of signal strength

• US 9,357,520 B2
• Filed: 01/31/2014
• Issued: 05/31/2016
• Est. Priority Date: 01/31/2014
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Le Grand, Etienne, Williams, Brian Patrick
• Primary Examiner(s): Patel, Nimesh
• Application Number:
  US14/169,175
• Publication Number:
  US 20150223189A1
• Time in Patent Office: 851 Days
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 64/003 locating network equipment
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]
• CPC Class Codes: H04W 92/10 between terminal device and access point, i.e. wireless air interface

Abstract

Examples herein include methods and systems for signal diffusion modeling for a discretized map of signal. An example method includes receiving data related to RSSI for a wireless AP for a plurality of locations of an area, associating the data to a diagram of the area based on the plurality of locations of the area, determining a given partition of the diagram in which a magnitude of a given RSSI associated with the given partition is greater than or equal to a highest magnitude of a given RSSI associated with any partitions of the plurality of partitions, assigning a location of the wireless AP to be within the given partition, and applying a constraint such that a magnitude of a given RSSI associated with other respective partitions is less than or equal to a highest magnitude of a given RSSI associated with neighboring partitions of the other respective partitions.

Claims

1. A method comprising:

receiving data related to received signal strength indication (RSSI) for a wireless access point for a plurality of locations of an area;

associating the data to a diagram of the area based on the plurality of locations of the area, wherein the diagram is divided into a plurality of partitions;

determining, by a processor, a first partition of the plurality of partitions of the diagram in which a magnitude of an RSSI associated with the first partition is greater than or equal to a highest magnitude of an RSSI associated with any other partitions of the plurality of partitions;

assigning a location of the wireless access point to be within the first partition; and

assigning RSSI magnitudes to the diagram to generate an RSSI map of signal strength for the wireless access point over the plurality of locations of the area by applying, by the processor, a constraint such that a magnitude of an RSSI associated with partitions of the diagram other than the first partition is less than or equal to the magnitude of the RSSI associated with the first partition and such that the magnitude of the RSSI associated with partitions of the diagram other than the first partition is also less than or equal to a highest magnitude of an RSSI associated with neighboring partitions that are adjacent to the partitions.

2. The method of claim 1, wherein receiving the data related to received signal strength indication (RSSI) for the wireless access point comprises receiving scans of a WiFi access point collected from the area, wherein the data further includes a WiFi access point identifier.

3. The method of claim 1, wherein the diagram of the area is a geographical map.

4. The method of claim 1, further comprising determining the RSSI map for the wireless access point in which the RSSI map includes a single local maximum RSSI value indicative of the location of the wireless access point.

5. The method of claim 1, further comprising determining the RSSI map for the wireless access point including indications of a diffusion of signal strength over the area away from the location of the wireless access point.

6. The method of claim 1, further comprising, for partitions of the plurality of partitions that are a threshold distance away from the first partition including the location of the wireless access point, applying a given constraint such that a magnitude of a given RSSI associated with the partitions that are the threshold distance away is about zero.

7. The method of claim 1, further comprising dividing the area into a grid including cells, and wherein the plurality of partitions include the cells, and the method further comprises:

assigning a value of an RSSI per cell.

8. The method of claim 1, further comprising determining the RSSI map for the wireless access point including assigned RSSI values per the plurality of partitions based on application of the constraint.

9. The method of claim 1, further comprising applying the constraint such that the magnitude of the RSSI associated with partitions of the diagram other than the first partition is less than the highest magnitude of the RSSI associated with neighboring partitions that are adjacent to the partitions.

10. The method of claim 1, wherein associating the data to the diagram of the area based on the plurality of locations of the area comprises generating the RSSI map of signal strength of the area for the wireless access point based on the received data being associated to the plurality of partitions corresponding to the plurality of locations of the area, and the method further comprising:

applying the constraint to the data of the diagram so as to modify values of the received data associated with the plurality of partitions; and

providing the RSSI map for the wireless access point including indications of a diffusion of signal strength over the area away from the location of the wireless access point based on the modified values of the received data.

11. A non-transitory computer readable memory having stored therein instructions, that when executed by a computing device, cause the computing device to perform functions comprising:

receiving data related to received signal strength indication (RSSI) for a wireless access point for a plurality of locations of an area;

associating the data to a diagram of the area based on the plurality of locations of the area, wherein the diagram is divided into a plurality of partitions;

determining a first partition of the plurality of partitions of the diagram in which a magnitude of an RSSI associated with the first partition is greater than or equal to a highest magnitude of an RSSI associated with any other partitions of the plurality of partitions;

assigning a location of the wireless access point to be within the first partition; and

assigning RSSI magnitudes to the diagram to generate an RSSI map of signal strength for the wireless access point over the plurality of locations of the area by applying a constraint such that a magnitude of an RSSI associated with partitions of the diagram other than the first partition is less than or equal to the magnitude of the RSSI associated with the first partition and such that the magnitude of the RSSI associated with partitions of the diagram other than the first partition is also less than or equal to a highest magnitude of an RSSI associated with neighboring partitions that are adjacent to the partitions.

12. The non-transitory computer readable memory of claim 11, wherein receiving the data related to received signal strength indication (RSSI) for the wireless access point comprises receiving scans of a WiFi access point collected from the area, wherein the data further includes a WiFi access point identifier.

13. The non-transitory computer readable memory of claim 11, wherein the functions further comprise determining the RSSI map for the wireless access point in which the RSSI map includes a single local maximum RSSI value indicative of the location of the wireless access point.

14. The non-transitory computer readable memory of claim 11, wherein the functions further comprise determining the RSSI map for the wireless access point including indications of a diffusion of signal strength over the area away from the location of the wireless access point.

15. The non-transitory computer readable memory of claim 11, wherein the functions further comprise, for partitions of the plurality of partitions that are a threshold distance away from the first partition including the location of the wireless access point, applying a given constraint such that a magnitude of a given RSSI associated with the partitions that are the threshold distance away is about zero.

16. A system comprising:

one or more processors;

data storage configured to store instructions that, when executed by the one or more processors, cause the system to perform functions comprising;

receiving data related to received signal strength indication (RSSI) for a wireless access point for a plurality of locations of an area;

associating the data to a diagram of the area based on the plurality of locations of the area, wherein the diagram is divided into a plurality of partitions;

determining a first partition of the plurality of partitions of the diagram in which a magnitude of an RSSI associated with the first partition is greater than or equal to a highest magnitude of an RSSI associated with any other partitions of the plurality of partitions;

assigning a location of the wireless access point to be within the given partition; and

assigning RSSI magnitudes to the diagram to generate an RSSI map of signal strength for the wireless access point over the plurality of locations of the area by applying a constraint such that a magnitude of an RSSI associated with partitions of the diagram other than the first partition is less than or equal to the magnitude of the RSSI associated with the first partition and such that the magnitude of the RSSI associated with partitions of the diagram other than the first partition is also less than or equal to a highest magnitude of an RSSI associated with neighboring partitions that are adjacent to the partitions.

17. The system of claim 16, wherein the functions further comprise dividing the area into a grid including cells, and wherein the plurality of partitions include the cells, and the method further comprises:

assigning a value of an RSSI per cell.

18. The system of claim 16, wherein the functions further comprise determining the RSSI map for the wireless access point including assigned RSSI values per the plurality of partitions based on application of the constraint.

19. The system of claim 16, wherein associating the data to the diagram of the area based on the plurality of locations of the area comprises generating the RSSI map of signal strength of the area for the wireless access point based on the received data being associated to the plurality of partitions corresponding to the plurality of locations of the area, and the functions further comprise:

applying the constraint to the data of the diagram so as to modify values of the received data associated with the plurality of partitions; and

providing the RSSI map for the wireless access point including indications of a diffusion of signal strength over the area away from the location of the wireless access point based on the modified values of the received data.