SYSTEM FOR PROVIDING ALERT-BASED SERVICES TO MOBILE STATIONS IN A WIRELESS COMMUNICATIONS NETWORK

• US 20120315925A1
• Filed: 06/11/2012
• Published: 12/13/2012
• Est. Priority Date: 07/16/2001
• Status: Active Grant

• Current Assignee: Smith Micro Software Incorporated
• Original Assignee: Wavemarket Incorporated (Gen Digital Inc.)
• Inventors: Ioppe, Igor V., Roumeliotis, Tasso, Hotes, Scott Allen, Klein, Philip Nathan, Susal, Joel A.
• Granted Patent: US 8,606,302 B2
• Time in Patent Office: Days
• US Class Current: 455/456.3
• 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 64/006 with additional information processing, e.g. for direction or speed determination
• CPC Class Codes: H04W 8/08 Mobility data transfer
• CPC Class Codes: H04W 8/10 between location register and external networks
• CPC Class Codes: H04W 88/18 Service support devices; Network management devices

Abstract

System for providing alert-based communication services for which corresponding alert conditions to be met by mobile stations are defined. The system includes an alert engine capable of firing alerts associated with the alert-based communication services if location data regarding the mobile stations is indicative of the mobile stations meeting the alert conditions corresponding to the alert-based communication services. A requirements engine determines an expected earliest future time at which at least one alert condition is capable of being met by a particular mobile station and outputs a data element indicative of a requirement to obtain updated location data about the particular mobile station in advance of the expected earliest future time. A scheduler receives expiry times data and processes the expiry times data for determining an order for servicing the location requests.

Claims

1. A method of accessing a data structure for obtaining an earliest expected travel time between a current location of a mobile station and a plurality of alert regions, the data structure comprising data regarding a subdivision of a network into cells for which a respective alert region is the nearest to all points in a respective cell, the method comprising:

(a) using a point-location data structure to determine which cell contains the current location;

(b) using a table to determine the alert region associated with the cell found in step (a); and

(c) determining the travel time from the current location to the alert region found in step (b).

2. The method of claim 1, wherein the data structure comprises a subdivision into cells of a two-dimensional space in which mobile stations may roam.

3. The method of claim 1, wherein the table comprises at least one of an array, a hash table, and a balanced search tree.

4. The method of claim 1, wherein:

the point-location data structure is representative of a relationship between the cells and a set of discrete nodes assigned to positions within the cells; and

the table is indexed by the cells, with at least one entry specifying the alert region nearest to the nodes.

5. The method of claim 1, further comprising creating the data structure by:

computing for each node the nearest alert region;

finding a planar subdivision in which each cell comprises at least one node;

merging together cells of the subdivision having the same nearest alert region; and

populating the table using the merged-together cells of the subdivision.

6. The method of claim 5, wherein the planar subdivision comprises a Vornoi diagram.

7. The method of claim 5, wherein computing the nearest alert region comprises applying a shortest-path algorithm.

8. The method of claim 5, further comprising applying heuristics to reduce the number of line segments defining the planar subdivision.

9. The method of claim 8, further comprising reducing the number of line segments defining the planar subdivision by replacing a plurality of line segments with a line if an area formed by the plurality of line segments does not comprise a node.

10. The method of claim 8, further comprising reducing the number of line segments defining the planar subdivision by replacing a plurality of line segments with a line, wherein a new cell is created, if for each node in an area formed by the plurality of line segments a travel time to an alert region associated with the new cell is not a predetermined percentage or amount greater than the travel time to the nearest alert region.

11. The method of claim 5, further comprising updating the data structure based on the existence of a new alert region by:

finding a set of nodes whose travel time to the new alert region is less than the travel time to an alert region previously corresponding to the set of nodes; and

creating at least one polygon enclosing the set of nodes and excluding other nodes.

12. The method of claim 11, further comprising finding the set of nodes by performing a shortest-path search rooted at the new alert region.

13. The method of claim 11, wherein the at least one polygon is created by finding the convex hull of the set of nodes found and perturbing the boundary of the convex hull to exclude other nodes.

14. The method of claim 11, wherein the at least one polygon is created by:

defining a subset of the planar subdivision comprising boundaries of cells comprising the set of nodes whose travel time to the new alert region is less than the travel time to an alert region previously corresponding to the set of nodes; and

merging together adjacent ones of the cells comprising the set of nodes.

15. The method of claim 1, further comprising using a cost function to determine the travel time from the current location to the alert region found in step (b).

16. A computer readable storage medium including a program element for execution by a processor to implement an apparatus configured to access a data structure for obtaining an earliest expected travel time between a current location of a mobile station and a plurality of alert regions, the data structure comprising data regarding a subdivision of a network into cells for which a respective alert region is the nearest to all points in a respective cell, the program element comprising instructions for performing a method comprising:

using a point-location data structure to determine which cell contains the current location;

using a table to determine the alert region associated with the cell containing the current location; and

determining the travel time from the current location to the alert region associated with the cell containing the current location.

17. A data processing device used in a communications network for providing alert-based services for which corresponding alert conditions to be met by mobile stations are defined, the data processing device configured to execute an application program to access a data structure for obtaining an earliest expected travel time between a current location of a mobile station and a plurality of alert regions, the data structure comprising data regarding a subdivision of a network into cells for which a respective alert region is the nearest to all points in a respective cell, the application program comprising instructions for performing a method comprising:

using a point-location data structure to determine which cell contains the current location;

using a table to determine the alert region associated with the cell containing the current location; and

determining the travel time from the current location to the alert region associated with the cell containing the current location.