System for providing alert-based services to mobile stations in a wireless communications network
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.
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 non-transitory 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.