SELECTING WIRELESS ACCESS POINTS FOR GEOFENCE MONITORING

• US 20120307645A1
• Filed: 06/03/2011
• Published: 12/06/2012
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Grainger, Morgan, Mayor, Robert, Huang, Ronald K., Grosman, Yefim, Marti, Lukas M.
• Granted Patent: US 9,019,984 B2
• Time in Patent Office: Days
• US Class Current: 370/241
• 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;

determining a plurality of geographic regions corresponding to 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 an access point allowance for each of the geographic regions, the access point allowance indicating a maximum number of wireless access points to be selected for the geographic region;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points using a wireless processor; 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 using an application processor of the mobile device.

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 selecting the one or more wireless access points comprises:

determining the maximum number of wireless access points to be selected based at least in part on a monitoring capacity of the wireless processor.

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;

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.

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. 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;

determining a plurality of geographic regions corresponding to 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 an access point allowance for each of the geographic regions, the access point allowance indicating a maximum number of wireless access points to be selected for the geographic region;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points using a wireless processor; 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 using an application processor of the mobile device.

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

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

determining the maximum number of wireless access points to be selected based at least in part on a monitoring capacity of the wireless processor.

18. The method of claim 15, 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.

19. The method of claim 18, 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.

20. The method of claim 19, 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.

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

22. The method of claim 21, 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.

23. The method of claim 22, 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.

24. The method of claim 20, 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.

25. The method of claim 15, 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.

26. The method of claim 25, 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.

27. The method of claim 15, 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.

28. The method of claim 15, wherein the wireless processor is a wireless chip.

29. A system, comprising:

a mobile device configured to perform operations comprising;

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

determining a plurality of geographic regions corresponding to 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 an access point allowance for each of the geographic regions, the access point allowance indicating a maximum number of wireless access points to be selected for the geographic region;

determining a tentative location of the mobile device relative to the geofence, including monitoring the selected one or more wireless access points using a wireless processor; 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 using an application processor of the mobile device.

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

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

determining the maximum number of wireless access points to be selected based at least in part on a monitoring capacity of the wireless processor.

32. The method of claim 29, 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.

33. The method of claim 32, 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.

34. The method of claim 33, 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.

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

36. The method of claim 35, 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.

37. The method of claim 36, 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.

38. The method of claim 34, 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.

39. The method of claim 29, 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.

40. The method of claim 39, 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.

41. The method of claim 29, 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.

42. The method of claim 29, wherein the wireless processor is a wireless chip.