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

• US 20100105414A1
• Filed: 12/08/2009
• Published: 04/29/2010
• Est. Priority Date: 07/16/2001
• Status: Active Grant

• Current Assignee: Smith Micro Software Incorporated
• Original Assignee: Wavemarket Incorporated (Gen Digital Inc.)
• Inventors: Roumeliotis, Tasso, Hotes, Scott Allen, Susal, Joel A., Klein, Philip Nathan, Ioppe, Igor V.
• Granted Patent: US 7,941,161 B2
• Time in Patent Office: Days
• US Class Current: 455/456.300
• 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 is provided for determining an expected earliest future time at which at least one alert condition is capable of being met by a particular mobile station and outputting 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. Also provided is a scheduler for receiving expiry times data indicative of a plurality of expiry times relating to respective location requests, processing the expiry times data for determining an order for servicing the location requests by positioning determining equipment (PDE) at least in part on a basis on the expiry times of the location requests and an output for interfacing with the PDE, allowing it to service the location requests according to the order determined.

Claims

1. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) an input for receiving expiry times data indicative of a plurality of expiry times relating to respective location requests;

b) a scheduler processing the expiry times data for determining an order for servicing the location requests by the PDE at least in part on a basis on the expiry times of the location requests; and

c) an output for interfacing with the PDE allowing the PDE to service the location requests according to the order determined by said scheduler.

2. An apparatus as defined in claim 1, wherein said scheduler includes a storage medium defining a sequence of slots for holding data elements according to the order for servicing the location requests by the PDE.

3. An apparatus as defined in claim 2, wherein each data element in said storage medium is associated to a location request.

4. An apparatus as defined in claim 2, wherein said scheduler is operative to re-compute the order of the data elements in said storage medium when new expiry times data associated with a new location request is received at said input.

5. An apparatus as defined in claim 4, wherein each slot in said sequence of slots corresponds to a point in time at which the position determination equipment is expected to service the location request of a data element stored in the slot.

6. An apparatus as defined in claim 5, wherein the re-computation includes for a new location request identifying a slot in said sequence of slots that corresponds to a point in time for servicing the new location request that is within the expiry time of the new location request.

7. An apparatus as defined in claim 6, wherein the re-computation includes identifying a slot in said sequence of slots that corresponds to a latest point in time for servicing the new location request, without exceeding the expiry time of the location request.

8. An apparatus as defined in claim 7, wherein if the slot that corresponds to the latest point in time for servicing the new location request is vacant, said scheduler is operative for storing a data element associated to the new location request in the slot that corresponds to the latest point in time.

9. An apparatus as defined in claim 8, wherein if the slot that corresponds to the latest point in time for servicing the new location request is occupied by a data element associated with a prior location request, then said scheduler is operative for:

a) displacing the data element associated with the prior location request to a slot corresponding to an earlier point in time for servicing the prior location request to vacate the slot containing the data element associated with the prior location request;

b) inserting the data element associated with the new location request in the vacated slot.

10. An apparatus as defined in claim 2, wherein the data elements are arranged according to a search tree.

11. An apparatus as defined in claim 10, wherein each data element is associated to a location request and each data element is represented by a node in said search tree.

12. An apparatus as defined in claim 11, wherein the nodes of said search tree are ordered according to the expiry times of the respective location requests.

13. An apparatus as defined in claim 12, wherein each data element includes a first label containing information about a number of descendants of the node associated with the data element.

14. An apparatus as defined in claim 13, wherein each data element includes a second label containing information identifying a time slot at which a location request is to be serviced.

15. An apparatus as defined in claim 14, wherein said scheduler is operative to compute an actual time to service a given location request based at least in part on the first and second labels of nodes in said search tree.

16. A computer readable storage medium including a program element for execution by a processor to implement an apparatus for scheduling servicing of location requests by a PDE, comprising:

a) a scheduling module for accepting as input expiry times data indicative of a plurality of expiry times relating to respective location requests for computing an order for servicing the location requests by the PDE at least in part on a basis on the expiry times of the location requests; and

b) an output module for interfacing with the PDE allowing the PDE to service the location requests according to the order determined by said scheduler.

17. A computer readable storage medium as defined in claim 16, wherein said scheduling module is operative to insert and remove data elements in a storage medium defining a sequence of slots such that the data elements are arranged according to the order for servicing the location requests computed by said scheduling module.

18. A computer readable storage medium as defined in claim 17, wherein each data element is associated to a location request.

19. A computer readable storage medium as defined in claim 18, wherein said scheduling module is operative to re-compute the order of the data elements in the storage medium when new expiry times data associated with a new location request is received by said scheduling module.

20. A computer readable storage medium as defined in claim 19, wherein each slot in the sequence of slots corresponds to a point in time at which the PDE is expected to service the location request of a data element stored in the slot.

21. A computer readable storage medium as defined in claim 20, wherein the re-computation includes for a new location request identifying a slot in the sequence of slots that corresponds to a point in time for servicing the new location request that is within the expiry time of the location request.

22. A computer readable storage medium as defined in claim 21, wherein the re-computation includes identifying a slot in the sequence of slots that corresponds to a latest point in time for servicing the new location request, without exceeding the expiry time of the new location request.

23. A computer readable storage medium as defined in claim 21, wherein if the slot that corresponds to the latest point in time for servicing the new location request is vacant, said scheduling module is operative for storing a data element associated to the new location request in the slot that corresponds to the latest point in time.

24. A computer readable storage medium as defined in claim 23, wherein if the slot that corresponds to the latest point in time for servicing the new location request is occupied by a data element associated with a prior location request, then said scheduling module is operative for:

a) displacing the data element associated with the prior location request to a slot corresponding to an earlier point in time for servicing the prior location request to vacate the slot containing the data element associated with the prior location request; and

b) inserting the data element associated with the new location request in the vacated slot.

25. A computer readable storage medium as defined in claim 17, wherein the data elements are arranged according to a search tree.

26. A computer readable storage medium as defined in claim 25, wherein each data element is associated to a location request and each data element is represented by a node in said search tree.

27. A computer readable storage medium as defined in claim 26, wherein the nodes of said search tree are ordered according to the expiry times of the respective location requests.

28. A method for scheduling servicing of location requests by a PDE, comprising:

a) receiving expiry times data indicative of a plurality of expiry times relating to respective location requests;

b) processing the expiry times data for determining an order for servicing the location requests by the position determination equipment at least in part on a basis on the expiry times of the location requests; and

c) interfacing with the PDE for allowing the PDE to service the location requests according to the determining.

29. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) an input for receiving data elements from an entity, the data elements indicative of respective location requests;

b) the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

c) a scheduler for determining when location requests are to be serviced, the determining being such that the servicing of at least some delayed-type location requests is postponed artificially; and

d) an output for interfacing with the PDE allowing the PDE to service the location requests according to the determining.

30. An apparatus as defined in claim 29, wherein the determining is such that the servicing of the delayed-type location requests is postponed artificially without exceeding the expiry time data of the respective delayed-type location requests.

31. An apparatus as defined in claim 29, wherein said scheduler includes a storage medium defining a sequence of slots for holding data elements according to the determining.

32. An apparatus as defined in claim 31, wherein each data element in said storage medium is associated to a location request.

33. An apparatus as defined in claim 32, wherein said scheduler is operative to re-compute the order of the data elements in said storage medium when new expiry times data associated with a new location request is received at said input.

34. An apparatus as defined in claim 30, wherein the data elements are arranged according to a search tree.

35. An apparatus as defined in claim 34, wherein each data element is associated to a location request and each data element is represented by a node in said search tree.

36. An apparatus as defined in claim 35, wherein the nodes of said search tree are ordered according to the expiry times of the respective location requests.

37. A method for scheduling servicing of location requests by a PDE, comprising:

a) receiving data elements from an entity, the data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

b) determining when location requests are to be serviced, the determining being such that the servicing of at least some delayed-type location requests is postponed artificially; and

c) interfacing with the PDE allowing the PDE to service the location requests according to the determining.

38. A method as defined in claim 37, wherein the determining is such that the servicing of the delayed-type location requests is postponed artificially without exceeding the expiry time data of the respective delayed-type location requests.

39. A computer readable storage medium including a program element for execution by a processor to implement an apparatus for scheduling servicing of location requests by a PDE, comprising:

a) a scheduling module for accepting as input data elements from an entity, the data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data, said scheduling module being operative for determining when location requests are to be serviced, the determining being such that the servicing of at least some delayed-type location requests is postponed artificially; and

b) an output module for interfacing with the PDE allowing the PDE to service the location requests according to the determining.

40. A computer readable storage medium as defined in claim 39, wherein the determining is such that the servicing of the delayed-type location requests is postponed artificially without exceeding the expiry time data of the respective delayed-type location requests.

41. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) an input for receiving a plurality of data elements from an entity, the plurality of data elements indicative of respective location requests;

b) the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

c) a scheduler for;

i) identifying among the delayed-type location requests, two or more delayed-type location requests that can be serviced by a common location query to the PDE; and

ii) determining at least in part on the basis of the respective expiry times of the delayed-type location requests identified at (i) when to issue the common location query to the PDE; and

d) an output for issuing the common location query.

42. A method for scheduling servicing of location requests by a PDE, comprising:

i) receiving a plurality of data elements from an entity, the plurality of data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

ii) identifying among the delayed-type location requests, two or more delayed-type location requests that can be serviced by a common location query to the PDE;

iii) determining at least in part on the basis of the respective expiry times of the delayed-type location requests identified at (ii) when to issue the common location query to the PDE; and

iv) issuing the common location query.

43. A computer readable storage medium including a program element for execution by a processor to implement an apparatus for scheduling servicing of location requests by a PDE, comprising:

a) a scheduling module for accepting a plurality of data elements from an entity, the plurality data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data, said scheduling module being operative for;

i) identifying among the delayed-type location requests, two or more delayed-type location requests that can be serviced by a common location query to the PDE; and

ii) determining at least in part on the basis of the respective expiry times of the delayed-type location requests identified at (i) when to issue the common location query to the PDE; and

b) an output module for issuing the common location query.

44. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) Input means for receiving expiry times data indicative of a plurality of expiry times relating to respective location requests;

b) Scheduler means for processing the expiry times data for determining an order for servicing the location requests by the PDE at least in part on a basis on the expiry times of the location requests;

c) output means for interfacing with the PDE allowing the PDE to service the location requests according to the order determined by said scheduler.

45. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) input means for receiving data elements from an entity, the data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

b) scheduling means for determining when location requests are to be serviced, the determining being such that the servicing of at least some delayed-type location requests is postponed artificially;

c) output means for interfacing with the PDE allowing the PDE to service the location requests according to the determining.

46. An apparatus for scheduling servicing of location requests by a PDE, comprising:

a) input means for receiving a plurality of data elements from an entity, the plurality of data elements indicative of respective location requests, the location requests including delayed-type location requests, a location request data element associated with a delayed-type location request including expiry time data;

b) scheduling means for;

i) identifying among the delayed-type location requests, two or more delayed-type location requests that can be serviced by a common location query to the PDE; and

ii) determining at least in part on the basis of the respective expiry times of the delayed-type location requests identified at (i) when to issue the common location query to the PDE; and

c) output means for issuing the common location query.

47. A memory for storing data for access by an application program being executed on a data processing device used in a communications network adapted to provide alert-based services for which corresponding alert conditions to be met by mobile stations are defined, comprising:

a secondary memory for holding a plurality of data structures, the data structures being associated with respective non-overlapping time intervals, each of the data structures containing information relevant to a respective category of alert conditions that requires a current time to be included in the time interval associated with that data structure; and

a primary memory for storing the one data structure associated with the time interval that includes the current time.

48. A method of creating a data structure for access by an application program being executed on a data processing device used in a communications network adapted to provide alert-based services for which corresponding alert conditions to be met by mobile stations are defined, each alert condition corresponding to an alert region, comprising:

defining a subdivision of the network into nodes;

computing, for each node, the nearest alert region;

merging together into a single cell for each alert region, those nodes having that alert region as the nearest alert region; and

maintaining a data structure that is indicative of the locations covered by each cell and the alert condition associated with that cell.

49. A method as defined in claim 48, each alert condition further corresponding to an alert time, the method further comprising maintaining separate data structures for at least two sets of alert conditions corresponding to respective disjoint time blocks, each set of alert conditions including those alert conditions corresponding to alert times contained within the respective time block.

50. A method of delivering an alert-based communications service relevant to a mobile station in a communications network, wherein the alert-based communications service is associated with an alert condition to be satisfied by the mobile station, comprising:

obtaining location data about the mobile station for a first time instant;

predicting location data about the mobile station for a second time instant after the first time instant based on the location data about the mobile station for the first time instant; and

if the mobile station is predicted to be within the alert region at the second time instant, triggering the firing of an alert at or after the second time instant.

51. A method as defined in claim 50, wherein predicting location data is based on recent information regarding the mobile station.

52. A method as defined in claim 50, wherein predicting location data is based on historical information regarding the mobile station.

53. A method as defined in claim 50, wherein predicting location data is based on current information regarding other mobile stations in the network.