Abstract:
In one embodiment, techniques approximate concurrent monitoring of a large number of geo-fences, potentially beyond a number supported by a mobile device, The mobile device may obtain a set of geo-fences and maintain a first subset of the geo-fences as an active subset of geo-fences and a second subset of the geo-fences as an inactive subset of geo-fences. The mobile device may also establish and monitor an envelope geo-fences that excluded the inactive subset of geo-fence. In response to detecting that the mobile device has moved to a new location proximate to the envelope geo-fence, one or more geo-fences are moved between the active subset of geo-fences and the inactive subset of geo-fences to produce a new active subset of geo-fences and a new inactive subset of geo-fences.

Description:
RELATED APPLICATIONS 
       [0001]    The present application is a continuation of U.S. patent application Ser. No. 14/593,403, filed on Jan. 9, 2015 by Christopher Steger et al., titled “Active Geo-Fence Management”, which claims priority to U.S. Provisional Patent Application No. 61/925,437, filed on Jan. 9, 2014 by Christopher Steger et al., titled “Active Geo-Fence Management and Geo-Fence Splitting”, the contents of both of which are incorporated by reference herein in their entirety. 
     
    
     BACKGROUND 
       [0002]    Technical Field 
         [0003]    The present disclosure relates generally to location-based services, and more specifically to geo-fences. 
         [0004]    Background Information 
         [0005]    Location-based services are a field of mobile applications that leverage the ability of many mobile devices to determine their current location and perform actions based on that location. Location-based services may involve supplying location-dependent content (e.g., advertisements, weather forecasts, driving directions, traffic updates, or other content) on the mobile device itself, providing location information for the mobile device to other devices (e.g., to enable “buddy” finding, child monitoring, or other services), collecting location-based statistical information (e.g., consumer demographic data, traffic data, or other data), or other types of operations. 
         [0006]    Some location-based services utilize geo-fences. A geo-fence is a virtual perimeter that may be established around a real-world geographic area. Crossing a geo-fence may cause a service to be provided, cause a service to be withheld, or trigger some other sort of action, depending on the particular application. However, there are several shortcomings in the present implementation of geo-fences on many mobile devices. Two prominent shortcomings involve limits on the number of geo-fences that a mobile device may concurrently monitor, and restrictions on the shape and/or size of geo-fences that the mobile device may monitor. 
         [0007]    In order to support geo-fences, mobile devices typically repeatedly determine their current location and compare that location to the virtual perimeter defined by the geo-fence. Such location determination and comparison consumes resources of the mobile device, including processing resources, and, often more importantly, power resources. Given the importance of battery life for many mobile devices, there may be practical limits on how many geo-fences can be concurrently monitored. In some cases, these practical limits are codified into restrictions imposed by the mobile device&#39;s operating system or firmware. For example, some mobile devices currently allow concurrent monitoring of about 20 geo-fences for a given application and about 100 geo-fences across all applications. These geo-fence limits are becoming increasingly problematic, as geo-fences are being utilized in more and more location based services. However, increasing these limits has proven difficult, given the compelling desire to even further reduce power consumption of mobile devices. 
         [0008]    Further, in order to simplify processing and achieve other efficiencies, some mobile devices impose limits on the possible shapes and sizes of monitored geo-fences. While geo-fences may theoretically be defined to have any of a wide variety of shapes and sizes, some mobile devices only support monitoring of geo-fences having certain supported shapes and sizes. For example, a mobile device may only support circular-shaped geo-fences having a radius of 100 meters. This limitation is becoming increasingly burdensome on developers and users, who may desire to utilize geo-fences having shapes and/or sizes other than those natively supported. 
         [0009]    Accordingly, there is a needed for improved techniques that may allow for monitoring of a number of geo-fences beyond a mobile device&#39;s geo-fence limit, and for using geo-fences of shapes and/or sizes other than those natively support by the mobile device. 
       SUMMARY 
       [0010]    In one example embodiment, a client on a mobile device selectively obtains and activates geo-fences to approximate concurrent monitoring of a larger number of geo-fences, potentially beyond a geo-fence limit of the mobile device. The client obtains a set of N1 geo-fences from a server, where N1 is either a predetermined number of geo-fences or the number of geo-fences within a predetermined radius of the mobile device. For example, the client may send a request to the server for geo-fences from one or more collections and provide its current location. The server may respond with a set of N1 geo-fences that are within a distance D 1  that location, where D 1  is a distance value. The client adds the set of N1 geo-fences to a geo-fence cache maintained on the mobile device. Initially, all the geo-fences in the cache may be inactive (i.e., not currently monitored by the mobile device). The client activates (i.e. causes to be monitored) a subset of N2 geo-fences from the set of N1 geo-fences, which are most proximate the location of the mobile device. N2 is generally a number less than or equal to the total number of geo-fences in the geo-fence cache, and less than or equal to the number of geo-fences that can be simultaneously monitored by the mobile device. In addition to the N2 geo-fences, the device further activates an “envelope” geo-fence. The envelope geo-fence may contain all of the N2 geo-fences, or it may contain a proximate subset of the N2 geo-fences. The envelope geo-fence provides a basis for determining when the activated subset of N2 geo-fences may need to be updated to select a new activated subset of N2 geo-fences. 
         [0011]    If the mobile device is moved to new location proximate one of the activated subset of N2 geo-fences (e.g., has crossed one of the geo-fence in the activated subset), an application that utilizes that geo-fence is notified. If the mobile device is moved to new location proximate the envelope geo-fence (e.g., has crossed the envelope geo-fence), the subset of N2 geo-fences is updated. For example, the client may activate a new subset of N2 geo-fences selected from the set of N1 geo-fences, which are most proximate the new location of the mobile device. The new subset of geo-fences may include new geo-fences as well as some geo-fences that were previously included in the old subset of N2 geo-fences. The client may de-activate geo-fences of the old subset of N2 geo-fences that are not included in the new subset of N2 geo-fences. The client also updates the envelope geo-fence, establishing a new envelope geo-fence about the new subset of N2 geo-fences, and de-activating the old envelope geo-fence. 
         [0012]    The set of N1 geo-fences maintained in the geo-fence cache on the mobile device is periodically refreshed. When it is detected that the mobile device has moved to a new location more than a distance D 2  from the location where geo-fences were previously obtained, the client may refresh its cached geo-fences to ensure there is a set of N1 geo-fences about the new location. The new set of N1 geo-fences may include some geo-fences already in the geo-fence cache, as well as new geo-fences obtained from the server. 
         [0013]    It should be understood that the example embodiments discussed in this Summary may include a variety of other features, including other features discussed below, and variations thereof. This Summary is intended simply as a brief introduction to the reader, and does not imply that those specific features mentioned herein are all the features of the invention, or are necessary, or essential, features of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The Detailed Description below refers to the accompanying drawings of example embodiments, of which: 
           [0015]      FIG. 1  is a block diagram of an example system that may implement techniques to approximate concurrent monitoring of a large number of geo-fences, and/or to approximate use of geo-fences of various shapes and/or sizes; 
           [0016]      FIG. 2  is a flow diagram of an example sequence of steps for initially obtaining and activating geo-fences, as part of a technique to approximate concurrent monitoring of a large number of geo-fences; 
           [0017]      FIG. 3  is an example arrangement of geo-fences illustrating quantities discussed in  FIG. 2 ; 
           [0018]      FIG. 4  is a flow diagram of an example sequence of steps for updating active geo-fences when a mobile device is moved to a new location; 
           [0019]      FIG. 5  is an example arrangement of geo-fences illustrating quantities discussed in  FIG. 4 ; 
           [0020]      FIG. 6  is a flow diagram of an example sequence of steps for refreshing a geo-fence cache on a mobile device; 
           [0021]      FIG. 7  is an example arrangement of geo-fences illustrating quantities discussed in  FIG. 6 ; 
           [0022]      FIG. 8  is a flow diagram of an example sequence of steps for approximating use of geo-fences of various shapes and/or sizes; and 
           [0023]      FIG. 9  is an illustration of an initial geo-fence being approximated with a group of other geo-fences. 
       
    
    
     DETAILED DESCRIPTION 
       [0024]      FIG. 1  is a block diagram of an example system  100  that may implement techniques to approximate concurrent monitoring of a large number of geo-fences, and/or to approximate use of geo-fences of a variety of shapes and/or sizes. The system includes a mobile device  110  and a server  120 , that communicate over a network  130 , such as the Internet. As used herein, the term “mobile device” refers to an electronic device designed to be carried on one&#39;s person or in a vehicle and having wireless communication capability, such as a smartphone, a tablet computer, an electronic book reader, or other similar device. A mobile device  110  may include a processor coupled to a memory that stores machine-executable instructions, and a network interface (e.g., a cellular, Wi-Fi or other interface) that allows the mobile device to communicate with the network  130 . Likewise, the server may include a processor coupled to a memory that stores further machine-executable instructions, and have its own network interface to the network  130 . 
         [0025]    The machine-executable instructions on the mobile device  110  may include instructions for a mobile operating system  140 , for example the iOS® operating system available from Apple Computer Inc., the Android® operating system available from Google Inc., or another operating system that functionally organizes the mobile device. The machine-executable instructions may also include instructions for a client application (or simply a “client”)  145  that implements client-side portions of the presently described techniques. The client  145  may include a geo-fence cache  150  that maintains geo-fences, including a number of active geo-fences  152  and a number of in-active geo-fences  154 . As discussed in more detail below, a request process  160  of the client  145  may initially load the geo-fence cache  150  with geo-fences, and replenish the geo-fence cache  150  with additional geo-fences, when needed. Further, as discussed in more detail below, an activation process  170  of the client may move geo-fences between the active geo-fences  152  and the inactive geo-fences  154  as needed. Likewise, in some implementations, some or all of an approximation process  195  may be included in the client and operate to approximate use of geo-fences of various shapes and/or sizes. 
         [0026]    The machine-executable instructions on the server  120  may include instructions for maintaining one or more collections of geo-fences  180  that store geo-fences used with one-or more location based services. The machine-executable instructions may also include instructions for a response process  190  that may interact with the request process  150  on the mobile device  110 , to supply geo-fences from the geo-fence collections  180  on the server  120  to the geo-fence cache  150  on the mobile device  110 . In some implementations, some or all of the approximation process  195  may be resident on the server  120 . 
         [0027]      FIG. 2  is a flow diagram of an example sequence of steps  200  for initially obtaining and activating geo-fences, as part of a technique to approximate concurrent monitoring of a large number of geo-fences.  FIG. 2  may be better understood by reference also to  FIG. 3 , which is an example arrangement of geo-fences  300  illustrating quantities discussed in  FIG. 2 . At step  210  the client  145  sends a request to the server  120  for geo-fences from the one or more collections  180 , and provides the mobile device&#39;s current location. For example, as shown in  FIG. 3 , the mobile device may be initially located at a location  310 . This location may be learned using any of a variety of location determination systems, including wireless local area network (WLAN)-based systems, global positioning system (GPS)-based systems, hybrid systems, and/or other systems. At step  220 , the server  120  responds with the set of N1 geo-fences from that are within a distance D 1  of the current location of the mobile device  110 , where D 1  is a distance value, and N1 is a predetermined value or based on the number of geo-fences that happen to be within distance D 1 . For example, as shown in  FIG. 3 , a distance D 1  from the location of the mobile device  310  may define a circumference  320  that includes the set of N1 geo-fences represented as geo-fences  330 - 346 . The value of D 1  may be predetermined, or dynamically selected. 
         [0028]    At step  230 , the client  145  adds the set of N1 geo-fences to the geo-fence cache  150  maintained on the mobile device  110 . Initially, all the geo-fences in the geo-fence cache  150  may be inactive (i.e., not currently monitored). At step  240 , the client  145  activates (i.e. causes to be monitored) a subset of N2 geo-fences from the set of N1 geo-fences that are most proximate the location of the mobile device  145 , where N2 is generally a number less than or equal to N1 (i.e. N2&lt;=N1). For example, as shown in  FIG. 3 , an activated subset of N2 geo-fences may include the geo-fences  330 - 333 , while geo-fences  340 - 346  may remain inactive. The value of N2 may be predetermined, or dynamically selected. In one implementation, the value is based on a device-imposed geo-fence limit. Alternatively, the value may be based on some other factor. 
         [0029]    At step  250 , the client  145  establishes and monitors an “envelope” geo-fence that provides a basis for determining when the activated subset of N2 geo-fences may need to be updated to select a new activated subset of N2 geo-fences. The envelope geo-fence may contain all of the N2 geo-fences, or it may contain a proximate subset of the N2 geo-fences. When the envelope geo-fence contains all of the N2 geo-fences it will generally encompass the N2 geo-fences. For example, as shown in  FIG. 3 , an envelope geo-fence  350  may encompass geo-fences  330 - 333 , but exclude geo-fences  340 - 346 . In one implementation, the envelope geo-fence may be arranged as a minimum bounding geo-fence (e.g., a geo-fence whose perimeter forms a minimum bounding circle, minimum bounding polygon or other minimum bounding shape) around the geo-fences of the activated subset of N2 geo-fences. Alternatively, the envelope geo-fence may be arranged as a maximum bounding geo-fence whose perimeter forms a maximum bounding shape around the subset of geo-fences while not containing any geo-fences that are not in the subset. The minimum bounding geo-fence (or maximum bounding geo-fence) may have a predetermined shape (e.g., always be circular), or its shape may be dynamical dependent upon the geo-fences it bounds (e.g., a shape selected from a set of possible shapes based on which shape will most efficiently enclose the geo-fences). The envelope geofence may be formed in a variety of different manners. In one embodiment, the envelope geo-fence may be formed based on a union of one or more tiles (i.e. discrete regions used by a location determination systems, e.g. a WLAN based system). 
         [0030]    At step  260 , the mobile device is moved to a new location proximate one of the activated subset of N2 geo-fences (e.g., has crossed one of the geo-fences in the activated subset, for example by entering a new tile (e.g., a boundary tile)), and an application that utilizes that geo-fence is notified. 
         [0031]      FIG. 4  is a flow diagram of an example sequence of steps  400  for updating active geo-fences when the mobile device is moved to a new location.  FIG. 4  may be better understood by reference also to  FIG. 5 , which is an example arrangement of geo-fences  500  illustrating quantities discussed in  FIG. 4 . At step  410 , the mobile device  110  is moved to new location proximate the envelope geo-fence (e.g., has crossed the envelope geo-fence). For example, as shown in  FIG. 5 , the mobile device may be moved from location  310  to location  510  which is outside of the envelope geo-fence  350 . At step  420 , the client activates a new subset of N2 geo-fences based on proximity to the new location  510  and de-activate geo-fences of the old subset of N2 geo-fences that are not included in the new subset of N2 geo-fences. The new subset of N2 geo-fences may include new geo-fences as well as some geo-fences that were previously included in the old subset of N2 geo-fences. The client may de-activate geo-fences of the old subset of N2 geo-fences that are not included in the new subset of N2 geo-fences. At step  430 , the client  145  establishes and monitors a new envelope geo-fence about the new subset of N2 geo-fences, and de-activates the old envelope geo-fence. For example, as shown in  FIG. 5 , new envelope geo-fence  520  may be activated, while old envelope geo-fence  310  may be de-activated. The sequence of steps  400  may be repeated as the mobile device moves about and crosses successive envelope geo-fences 
         [0032]      FIG. 6  is a flow diagram of an example sequence of steps  600  for refreshing the geo-fence cache  150  on the mobile device  110 .  FIG. 6  may be better understood by reference also to  FIG. 7 , which is an example arrangement of geo-fences  700  illustrating quantities discussed in  FIG. 6 . At step  610 , it is detected that the mobile device has moved to a new location more than a distance D 2  from the location where geo-fences were previously obtained, where D 2  is a number less than D 1  (i.e. D 2 &lt;D 1 ). For example, as shown in  FIG. 7 , the mobile device may be moved to a new location  510  that is more than a distance D 2  from the original location  310 . In one implementation, the value of D 2  is a function of D 1 . The function may try to balance between frequency of access to the server  120  and the likelihood that the mobile device  110  may move beyond those geo-fences that are cached before additional geo-fences can be obtained from the server  120 . 
         [0033]    At step  620 , the geo-fence cache is updated to ensure there is a set of N1 geo-fences. The new set of N1 geo-fences may include some geo-fences already in the geo-fence cache, as well as new geo-fences obtained from the server. Obtaining the new geo-fences may be performed using operations similar to as discussed above in relation to  FIG. 2 . When new geo-fences are added the geo-fence cache  150  on the mobile device  110  they may potentially displace existing geo-fences in the cache that are not a part of the new set of N1 geo-fences. For example, as shown in  FIG. 7 , new geo-fences  720 - 722  may be added to the geo-fence cache as they are within distance D 1  of new location  510 . Other geo-fences  343 ,  344 ,  345  previously in the geo-fence cache may be displaced as they are not a part of the new set of N1 geo-fences. The sequence of steps  600  may be repeated as the mobile device moves about and the geo-fence cache needs to be refreshed. 
         [0034]    In another example embodiment, the client on the mobile device approximates use of geo-fences of various shapes and/or sizes, potentially including shapes and/or sizes other than those natively support by the mobile device  110 .  FIG. 8  is a flow diagram of an example sequence of steps  800  for approximating use of geo-fences of various shapes and/or sizes.  FIG. 8  may be better understood by reference also to  FIG. 9 , which is an illustration  900  of an initial geo-fence being approximated by a group of other geo-fences. At step  810 , the approximation process  195  (included in the client  145  or resident on the server  120 ) receives an initial geo-fence having a given shape and/or size. The given shape and/or size may be one that is not natively support by the mobile device  110 , such that the initial geo-fence is considered a “non-supported geo-fence”. For example, as shown in  FIG. 9 , an initial geo-fence (e.g., non-supported geo-fence)  910  may have a cross-like shape (e.g., which may not be supported on a mobile device that only supports circular geo-fences). It should be understood that the initial geo-fence (e.g., non-supported geo-fence) may have any of a variety of other shapes, for example, an irregular user-defined shape, a multi polygonal shape, or other shape that software and/or hardware on the mobile device does not natively accept. Likewise, the initial geo-fence (e.g., non-supported geo-fence) may have any of a variety of sizes, including sizes larger than a mobile device will accept, sizes smaller than a mobile device will accept, or other sizes. 
         [0035]    At step  820 , the approximation process generates a group of M geo-fences whose union approximates the initial geo-fence (e.g., non-supported geo-fence), where M is a value greater than or equal to one (i.e. M&gt;=1). The group of M geo-fences may be natively supported by the mobile device  110 , such that the geo-fences are considered “supported geo-fences.” For example, as shown in  FIG. 9 , five circular geo-fences (e.g., a group of five supported geo-fences)  920 - 924  may approximate the initial geo-fence (e.g., non-supported geo-fence)  910 . The group of M geo-fences may be considered to “approximate” the initial geo-fence based on one or more standards. In one implementation, the M geo-fences may “approximate” the initial geo-fence by their union defining a minimum bounding shape that encloses the initial geo-fence. In another implementation, the M geo-fences may “approximate” the initial geo-fence by their union including a given percentage (e.g., 95%) of the initial geo-fence. A variety of other standards may also be employed. 
         [0036]    At step  830 , the group of M geo-fences (e.g., the group of M supported geo-fences) are mapped to a single identity. At step  840 , whenever it is detected that mobile device  110  is moved to new location proximate to (e.g., has crossed) the union of the M geo-fences (e.g., M supported geo-fences), an application that utilizes the initial geo-fence (e.g., the non-supported geo-fence) is notified. For example, if the mobile device has crossed one of the M geo-fences, and has not crossed into another of the M geo-fences, but has instead left the union of the M geo-fences, an application that utilizes the initial geo-fence (e.g. the non-supported geo-fence) may be notified. In this manner, the union of the group of M geo-fences (e.g., the group of M supported geo-fences) is effectively treated as an equivalent and the initial geo-fence (e.g., non-supported geo-fence). For example, in reference to  FIG. 9 , the group of five geo-fences  920 - 924  whose union is  930  is treated as an equivalent of initial geo-fence  910 , and an application using initial geo-fence  910  is notified when the union  930  is triggered. The sequence of steps  800  may be repeated for each initial geo-fence (e.g., non-supported geo-fence) that is to be utilized in connection with the mobile device  110 . 
         [0037]    In summary, the above described techniques may be used to approximate concurrent monitoring of a large number of geo-fences, potentially beyond a number supported by a mobile device, and to approximate use of geo-fences of various shapes and/or sizes, potentially other than those natively support by the mobile device. It should be understood that the techniques, and portions, thereof may be utilized together, individually, or in combination with other techniques, depending on the implementation. Further, it should be understood that aspects of the techniques may be modified, added to, removed, or otherwise changed depending on the implementation. 
         [0038]    For example, while some of the examples discussed above involve two-dimension (2-D) geo-fences, it should be understood that the techniques are readily applicable to three-dimensional (3-D) geo-fences. For instance, rather than circles, polygons, and the like, the geo-fences may be arranged as spheres, prisms and similar 3-D shapes. 
         [0039]    Further, while certain processes  160 ,  170   190 ,  195  discussed above, are described as resident on the mobile device  110  and/or the server  120 , it should be understood that the processes, and portions thereof, may be otherwise located, such that operations may be performed on different devices. For instance, at least portions of the activation process  170  may performed on the server  120  rather than on the mobile device  110 . Likewise, an additional server (not shown) or other electronic device may be called upon to perform some operations. 
         [0040]    In general, while specific example hardware and software is discussed above, it should be understood that the technique may be implemented using a variety of different types of hardware, software, and combination thereof. Such hardware may include a variety of types of processors, memory chips, programmable logic circuits, application specific integrated circuits, and/or other types of hardware components that support execution of software. Such software may include executable instructions that implement applications stored in a non-transitory computer-readable medium, such as a volatile or persistent memory device, a hard-disk, or other data store. Combinations of software and hardware may be adapted to suit different environments and applications. 
         [0041]    Accordingly, it should be understood that the above descriptions are meant to be taken only by way of example.