Selecting wireless access points for geofence monitoring

• US 9,019,984 B2
• Filed: 06/03/2011
• Issued: 04/28/2015
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Grosman, Yefim, Marti, Lukas M., Grainger, Morgan, Mayor, Robert, Huang, Ronald K.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Mais, Mark A
• Application Number:
  US13/153,268
• Publication Number:
  US 20120307645A1
• Time in Patent Office: 1,425 Days
• Field of Search: None
• US Class Current: 370/437
• CPC Class Codes: H04B 7/2643 using time-division multiple access [TDMA] H04B7/2615, H04B7/2618 take precedence
• CPC Class Codes: H04M 1/72463 to restrict the functionality of the device
• 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 48/20 Selecting an access point

Abstract

Methods, program products, and systems for monitoring geofence exits using wireless access points are disclosed. In general, in one aspect, the mobile device can select, from multiple wireless access points, one or more wireless access points for monitoring a geofence. Selecting the one or more wireless access points can include determining multiple geographic regions corresponding to the geofence. The mobile device can select the one or more wireless access points based on a maximum total number of wireless access points to be selected and an access point allowance for each of the geographic regions. The access point allowance can indicate a maximum number of wireless access points to be selected for the geographic region. The mobile device can detect a potential entry or exit of the geofence by monitoring the selected one or more wireless access points using a wireless processor.

Claims

1. A method performed by a mobile device, comprising:

selecting, from a plurality of wireless access points, one or more wireless access points for monitoring a geofence, including;

obtaining representations of a plurality of geographic regions corresponding to the geofence, wherein each geographic region is a portion of a geographic area enclosed by the geofence; and

selecting the one or more wireless access points based on a maximum total number of wireless access points to be selected and a respective access point allowance for each of the geographic regions, each access point allowance indicating a maximum number of wireless access points to be selected for the corresponding geographic region, the access point allowance being distributed among the geographic regions in a grid in which an access point allowance of a geographic region that is located closer to a center of the geographic area enclosed by the geofence is higher than an access point allowance of a geographic region that is located farther away from the center;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points, wherein during the monitoring, the mobile device accommodates a wireless scan capacity of a processor performing the monitoring by distributing the wireless scan capacity among the geographic regions according to the grid and the access point allowances, the grid causing the mobile device to distribute more wireless scan capacity to monitoring wireless access points that are detectable in the geographic region that is closer to the center of the geographic area; and

upon determining the tentative location of the mobile device relative to the geofence by the wireless processor, determining whether the mobile device is inside of the geofence.

2. The method of claim 1, wherein the geofence is defined by a fence location and a fence dimension.

3. The method of claim 1, wherein

the processor performing the monitoring is a wireless processor of the mobile device.

4. The method of claim 1, wherein determining a plurality of geographic regions corresponding to the geofence comprises dividing a geographic area associated with the geofence into a plurality of tiles, each geographic region corresponding to a tile.

5. The method of claim 4, wherein each wireless access point is associated with:

an access point location associated with one of the geographical regions for monitoring; and

an access point score indicating a worthiness of the wireless access point in monitoring the geofence.

6. The method of claim 5, wherein selecting the one or more wireless access points comprises:

iteratively performing scoring operations, the scoring operations comprising;

setting or increasing the access point allowance for each of the geographic regions;

been added to a geographic region;

ordering, based on the access point scores, wireless access points that have not yet

adding, based on the access point allowance of each geographic region, a not yet added wireless access point to a destination geographic region, wherein the access point location associated with the not yet added wireless access point corresponds to the destination geographic region;

designating already added access points as candidate wireless access points; and

calculating a detection probability based on the candidate wireless access point; and

selecting the one or more wireless access points from the candidate wireless access points based on the maximum total number of wireless access points and the detection probabilities calculated in the iterative scoring operations.

7. The method of claim 6, wherein selecting the one or more wireless access points is further based on communication channels between the mobile device and the wireless access points.

8. The method of claim 7, wherein selecting the one or more wireless access points comprises:

determining one or more preferred wireless access points for each of the communication channels using a probability density function; and

selecting the one or more wireless access points from the preferred wireless access points.

9. The method of claim 8, wherein determining one or more preferred wireless access points for each of the communication channels comprises:

determining a popularity score of each of the communication channels using a probability density function and a number of wireless access points using the communication channel; and

determining the one or more preferred wireless access points based on the popularity scores of the communication channels.

10. The method of claim 6, wherein the calculating the detection probability comprises:

designating at least one point in each of the geographic regions as a probing point;

calculating a probing point detection probability for each probing point, the probing point detection probability indicating a likelihood that a mobile device located at the probing point can detect any chosen access point for monitoring the geofence; and

calculating the detection probability based on the probing point detection probabilities of the probing points, including calculating a probability of not detecting any of the selected access points at any of the probing points.

11. The method of claim 1, comprising selecting one or more wireless access points for monitoring another geofence, such that a total number of the selected wireless access points representing the geofence and the selected wireless access points representing the other geofence does not exceed the maximum number of wireless access points.

12. The method of claim 11, comprising iteratively determining whether to select one or more candidate wireless access points for monitoring the geofence or to select the one or more candidate wireless access points for monitoring the other geofence in each iteration based on an amount of improvement that results from each selection.

13. The method of claim 1, wherein monitoring the selected one or more wireless access points comprises scanning, on one or more channels, a signal from the selected one or more wireless access points.

14. The method of claim 1, wherein the wireless processor is a wireless chip.

15. The method of claim 1, comprising performing an action or stopping performing an action based on whether the mobile device is inside of the geofence.

16. A non-transitory computer-readable medium storing a computer program product configured to cause a mobile device to perform operations comprising:

selecting, from a plurality of wireless access points, one or more wireless access points for monitoring a geofence, including;

obtaining representations of a plurality of geographic regions corresponding to the geofence, wherein each geographic region is a portion of a geographic area enclosed by the geofence; and

selecting the one or more wireless access points based on a maximum total number of wireless access points to be selected and a respective access point allowance for each of the geographic regions, each access point allowance indicating a maximum number of wireless access points to be selected for the corresponding geographic region, the access point allowance being distributed among the geographic regions in a grid in which an access point allowance of a geographic region that is located closer to a center of the geographic area enclosed by the geofence is higher than an access point allowance of a geographic region that is located farther away from the center;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points, wherein during the monitoring, the mobile device accommodates a wireless scan capacity of a processor performing the monitoring by distributing the wireless scan capacity among the geographic regions according to the grid and the access point allowances, the grid and the access point allowances causing the mobile device to distribute more wireless scan capacity to monitoring wireless access points that are detectable in the geographic region that is closer to the center of the geographic area; and

upon determining the tentative location of the mobile device relative to the geofence by the wireless processor, determining whether the mobile device is inside of the geofence.

17. The non-transitory computer-readable medium of claim 16, wherein the geofence is defined by a fence location and a fence dimension.

18. The non-transitory computer-readable medium of claim 16, wherein

the processor performing the monitoring is a wireless processor of the mobile device.

19. The non-transitory computer-readable medium of claim 16, wherein determining a plurality of geographic regions corresponding to the geofence comprises dividing a geographic area associated with the geofence into a plurality of tiles, each geographic region corresponding to a tile.

20. The non-transitory computer-readable medium of claim 19, wherein each wireless access point is associated with:

an access point location associated with one of the geographical regions for monitoring; and

an access point score indicating a worthiness of the wireless access point in monitoring the geofence.

21. The non-transitory computer-readable medium of claim 20, wherein selecting the one or more wireless access points comprises:

iteratively performing scoring operations, the scoring operations comprising;

setting or increasing the access point allowance for each of the geographic regions;

ordering, based on the access point scores, wireless access points that have not yet been added to a geographic region;

adding, based on the access point allowance of each geographic region, a not yet added wireless access point to a destination geographic region, wherein the access point location associated with the not yet added wireless access point corresponds to the destination geographic region;

designating already added access points as candidate wireless access points; and

calculating a detection probability based on the candidate wireless access point; and

selecting the one or more wireless access points from the candidate wireless access points based on the maximum total number of wireless access points and the detection probabilities calculated in the iterative scoring operations.

22. The non-transitory computer-readable medium of claim 21, wherein selecting the one or more wireless access points is further based on communication channels between the mobile device and the wireless access points.

23. The non-transitory computer-readable medium of claim 22, wherein selecting the one or more wireless access points comprises:

determining one or more preferred wireless access points for each of the communication channels using a probability density function; and

selecting the one or more wireless access points from the preferred wireless access points.

24. The non-transitory computer-readable medium of claim 23, wherein determining one or more preferred wireless access points for each of the communication channels comprises:

determining a popularity score of each of the communication channels using a probability density function and a number of wireless access points using the communication channel; and

determining the one or more preferred wireless access points based on the popularity scores of the communication channels.

25. The non-transitory computer-readable medium of claim 21, wherein the calculating the detection probability comprises:

designating at least one point in each of the geographic regions as a probing point;

calculating a probing point detection probability for each probing point, the probing point detection probability indicating a likelihood that a mobile device located at the probing point can detect any chosen access point for monitoring the geofence; and

calculating the detection probability based on the probing point detection probabilities of the probing points, including calculating a probability of not detecting any of the selected access points at any of the probing points.

26. The non-transitory computer-readable medium of claim 16, the operations comprising selecting one or more wireless access points for monitoring another geofence, such that a total number of the selected wireless access points representing the geofence and the selected wireless access points representing the other geofence does not exceed the maximum number of wireless access points.

27. The non-transitory computer-readable medium of claim 26, the operations comprising iteratively determining whether to select one or more candidate wireless access points for monitoring the geofence or to select the one or more candidate wireless access points for monitoring the other geofence in each iteration based on an amount of improvement that results from each selection.

28. The non-transitory computer-readable medium of claim 16, wherein monitoring the selected one or more wireless access points comprises scanning, on one or more channels, a signal from the selected one or more wireless access points.

29. The non-transitory computer-readable medium of claim 16, wherein the wireless processor is a wireless chip.

30. The non-transitory computer-readable medium of claim 16, the operations comprising performing an action or stopping performing an action based on whether the mobile device is inside of the geofence.

31. A system, comprising:

a processor; and

a non-transitory storage device storing instructions configured to cause the processer to perform operations comprising;

selecting, from a plurality of wireless access points, one or more wireless access points for monitoring a geofence, including;

obtaining representations of a plurality of geographic regions corresponding to the geofence, wherein each geographic region is a portion of a geographic area enclosed by the geofence; and

selecting the one or more wireless access points based on a maximum total number of wireless access points to be selected and a respective access point allowance for each of the geographic regions, each access point allowance indicating a maximum number of wireless access points to be selected for the corresponding geographic region, the access point allowance being distributed among the geographic regions in a grid in which an access point allowance of a geographic region that is located closer to a center of the geographic area enclosed by the geofence is higher than an access point allowance of a geographic region that is located farther away from the center;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points, wherein during the monitoring, the mobile device accommodates a wireless scan capacity of a processor performing the monitoring by distributing the wireless scan capacity among the geographic regions according to the grid and the access point allowances, the grid and the access point allowances causing the mobile device to distribute more wireless scan capacity to monitoring wireless access points that are detectable in the geographic region that is closer to the center of the geographic area; and

upon determining the tentative location of the mobile device relative to the geofence by the wireless processor, determining whether the mobile device is inside of the geofence.

32. The system of claim 31, wherein the geofence is defined by a fence location and a fence dimension.

33. The system of claim 31, wherein

the processor performing the monitoring is a wireless processor of the mobile device.

34. The system of claim 31, wherein determining a plurality of geographic regions corresponding to the geofence comprises dividing a geographic area associated with the geofence into a plurality of tiles, each geographic region corresponding to a tile.

35. The system of claim 34, wherein each wireless access point is associated with:

an access point location associated with one of the geographical regions for monitoring; and

an access point score indicating a worthiness of the wireless access point in monitoring the geofence.

36. The system of claim 35, wherein selecting the one or more wireless access points comprises:

iteratively performing scoring operations, the scoring operations comprising;

setting or increasing the access point allowance for each of the geographic regions;

ordering, based on the access point scores, wireless access points that have not yet been added to a geographic region;

adding, based on the access point allowance of each geographic region, a not yet added wireless access point to a destination geographic region, wherein the access point location associated with the not yet added wireless access point corresponds to the destination geographic region;

designating already added access points as candidate wireless access points; and

calculating a detection probability based on the candidate wireless access point; and

selecting the one or more wireless access points from the candidate wireless access points based on the maximum total number of wireless access points and the detection probabilities calculated in the iterative scoring operations.

37. The system of claim 36, wherein selecting the one or more wireless access points is further based on communication channels between the mobile device and the wireless access points.

38. The system of claim 37, wherein selecting the one or more wireless access points comprises:

determining one or more preferred wireless access points for each of the communication channels using a probability density function; and

selecting the one or more wireless access points from the preferred wireless access points.

39. The system of claim 38, wherein determining one or more preferred wireless access points for each of the communication channels comprises:

determining a popularity score of each of the communication channels using a probability density function and a number of wireless access points using the communication channel; and

determining the one or more preferred wireless access points based on the popularity scores of the communication channels.

40. The system of claim 36, wherein the calculating the detection probability comprises:

designating at least one point in each of the geographic regions as a probing point;

calculating a probing point detection probability for each probing point, the probing point detection probability indicating a likelihood that a mobile device located at the probing point can detect any chosen access point for monitoring the geofence; and

calculating the detection probability based on the probing point detection probabilities of the probing points, including calculating a probability of not detecting any of the selected access points at any of the probing points.

41. The system of claim 31, the operations comprising selecting one or more wireless access points for monitoring another geofence, such that a total number of the selected wireless access points representing the geofence and the selected wireless access points representing the other geofence does not exceed the maximum number of wireless access points.

42. The system of claim 41, the operations comprising iteratively determining whether to select one or more candidate wireless access points for monitoring the geofence or to select the one or more candidate wireless access points for monitoring the other geofence in each iteration based on an amount of improvement that results from each selection.

43. The system of claim 31, wherein monitoring the selected one or more wireless access points comprises scanning, on one or more channels, a signal from the selected one or more wireless access points.

44. The system of claim 31, wherein the wireless processor is a wireless chip.

45. The system of claim 31, the operations comprising performing an action or stopping performing an action based on whether the mobile device is inside of the geofence.