Location information recovery and management for mobile networks

• US 6,718,173 B1
• Filed: 09/30/1999
• Issued: 04/06/2004
• Est. Priority Date: 09/30/1999
• Status: Expired due to Fees

• Current Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Original Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Inventors: Somani, Arun K., Krishnamurthy, Govindarajan
• Primary Examiner(s): Trost, William
• Assistant Examiner(s): TORRES, MARCOS L
• Application Number:
  US09/409,130
• Time in Patent Office: 1,650 Days
• Field of Search: 455/435, 455/432, 455/445, 455/433, 455/456, 707/200, 707/204, 709/40, 370/331, 370/338, 370/407
• US Class Current: 455/456.1
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 60/04 using triggered events
• CPC Class Codes: H04W 8/12 between location registers or mobility servers
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Systems and methods for recovering and managing location information in mobile communication networks using a fast recovery protocol and load balanced query and update processes. According to the fast recovery protocol, if a location update processor does not receive a message from a global database server acknowledging receipt by the global database server of a location update message after a predetermined retry interval has elapsed since the location update message was sent by the location update processor, the location update processor sends a location update retry message after each predetermined retry interval elapses until the location update processor receives an acknowledgement message from the global database server. The global database server can use the location update retry messages and the predetermined retry interval to recover from a database or link failure. The recovery period using the fast recovery protocol is bounded by the predetermined retry interval. The fast recovery protocol can also be used in a system having a distributed location information database architecture. The load balanced query and update processes can be used to query and update, respectively, the databases of the distributed location information database architecture.

Claims

1. A method for managing information concerning the location of a mobile device in a mobile communication network, the method comprising:

maintaining a location database that stores location information indicative of the location of the mobile device;

receiving location update messages from the mobile device via a location update processor associated with a particular location area within the network when the location of the mobile device changes;

transmitting the location update messages to the location database, and

in the event one of the location update messages is not received by the location database, transmitting location update retry messages from the location update processor at the end of successive retry intervals until one of the location update retry messages is received,

wherein the act of maintaining a location database comprises maintaining a plurality of location databases that store location information indicative of the location of the mobile device, and wherein the plurality of location databases comprises n location databases, D1, . . . , Dn, arranged in a logical ring for storing location information about a mobile device, and the act of transmitting the location update messages to the location database comprises transmitting location update messages to k of the n location databases.

2. The method of claim 1, wherein the location update message includes a time stamp and the location update retry messages include the time stamp from the location update message.

3. The method of claim 2, further comprising:

receiving call delivery request messages from the mobile device via the location update processor; and

transmitting at least a subset of the call delivery request messages to the location database.

4. The method of claim 3, further comprising:

recovering location information for the mobile device after a failure in the mobile communication network, wherein the act of recovering includes;

if a location update message or a call delivery request message is received before the retry interval has passed since the failure was removed from the mobile communication network, storing in the location database the location information for the mobile device from the location update message or the call delivery request message; and

if the retry interval has passed since the failure was removed from the mobile communication network without receiving a location update message or a call delivery request message while receiving at least one location update retry message, storing in the location database the location information for the mobile device from the location update retry message having the most recent time stamp.

5. The method of claim 4, wherein the act of recovering location information for the mobile device after a failure in the mobile communication network further includes using the location information stored in the location database for the mobile device just before the failure as the location information for the mobile device, if the retry interval has passed since the failure was removed from the mobile communication network without receiving a location update message or at least one location update retry message.

6. The method of claim 5, further comprising maintaining a local location database that is associated with the location update processor and that stores location information indicative of the location of the mobile device when the mobile device is located in the particular location area associated with the location update processor.

7. The method of claim 6, wherein the act of recovering location information for the mobile device after a failure in the mobile communication network further includes:

freezing the local location database after the failure in the mobile communication network; and

unfreezing the local location database after the location information for the mobile device has been recovered.

8. The method of claim 1, wherein Γ

=(γ

1, γ

2, . . . , γ

k) is a placement vector and γ

iε

{1, 2, . . . , n} is the index of the ith database to which a location update message is transmitted, and the act of transmitting the location update messages comprises;

selecting γ

1 from the set (1, 2, . . . , n);

for i=1, . . . , k−

1, selecting γ

i+1 according to γ

_irFn/kL+a_i, wherein;

r is modulo addition defined over the set (1, 2, . . . , n);

displacement vector â

=(a1, a2, . . . , ak) is a binary vector having a Hamming weight of β

; and

β

=n−

Fn/kL*k; and

transmitting location update messages to the k location databases, Dγ

1, . . . , Dγ

k.

9. The method of claim 8, further comprising, before transmitting location update messages to the k location databases, Dγ

1, . . . , Dγ

k, deleting any location information previously stored in the n location databases, D1, . . . , Dn, for the mobile device.

10. The method of claim 8, wherein γ

1 is selected randomly using a uniform distribution over the set (1, 2, . . . , n).

11. The method of claim 10, further comprising, before transmitting location update messages to the k location databases, Dγ

1, . . . , Dγ

k, determining if all of the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k), are accessible, and if all of the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k), are not accessible, selecting a different placement vector, Γ

=(γ

1, . . . , γ

k).

12. The method of claim 11, wherein if no placement vector, γ

=(γ

1, . . . , γ

k), can be found in which all the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k), are accessible, selecting the placement vector, Γ

=(γ

1, . . . , γ

k), having the most number of databases, Dγ

1, . . . , Dγ

k, that are accessible.

13. The method of claim 8, wherein the displacement vector â

comprises;

0, for a₁, . . . , a<sub>k−

β</sub>

; and

1, for a<sub>k−

β

+1</sub>, . . . , a_k.

14. The method of claim 1, further comprising querying the location databases for location information about the mobile device.

15. The method of claim 14, wherein the act of querying the location databases comprises querying successive location databases on the logical ring for location information about the mobile device until location information about the mobile device is located or until all the location databases have been queried.

16. The method of claim 14, wherein the act of querying the location databases comprises:

querying a first group of successive location databases on the logical ring in parallel;

if location information about the mobile is not located by querying the first group of successive location databases, querying a second group of successive databases on the logical ring in parallel; and

if location information about the mobile is not located by querying the second group of successive location databases, querying additional groups of location databases in parallel until location information for the mobile is located or until all the location databases have been queried.

17. A mobile communication network comprising:

a mobile device;

a location database server having a location database storing location information indicative of the location of the mobile device; and

a location update processor that;

receives location update messages from the mobile device when the location of the mobile device changes,

transmits the location update messages to the location database, and

in the event one of the location update messages is not received by the location database, transmits location update retry messages at the end of successive retry intervals until one of the location update retry messages is received,

and wherein the mobile communication network further comprises a plurality of location database servers each having a location database for storing location information indicative of the location of the mobile device, and wherein the plurality of location database servers comprises n location database servers, D1, . . . , Dn, arranged in a logical ring for storing location information about a mobile device, and wherein the location update processor further includes a message processor that transmits location update messages to k of the n location databases, wherein Γ

=(γ

1, γ

2, . . . , γ

k) is a placement vector and γ

iε

{1, 2, . . . , n} is the index of the ith database to which a location update message is transmitted.

18. The mobile communication network of claim 17, wherein the location update message includes a time stamp and the location update processor transmits the time stamp from the location update message in the location update retry messages.

19. The mobile communication network of claim 18, wherein the location database server includes a recovery processor, for recovering location information for mobile device after a failure in the mobile communication network, that:

if a location update message is received before the retry interval has passed since the failure was removed from the mobile communication network, stores in the location database the location information for the mobile device from the location update message, and

if the retry interval has passed since the failure was removed from the mobile communication network without receiving a location update message while receiving at least one location update retry message, stores in the location database the location information for the mobile device from the location update retry message having the most recent time stamp.

20. The mobile communication network of claim 19, wherein the location update processor includes a local location database that stores location information indicative of the location of the mobile device when the mobile device is located in the particular location area associated with the location update processor.

21. The mobile communication network of claim 20, wherein the recovery processor sends a freeze message to the location update processor after the failure in the mobile communication network and sends unfreeze messages to the location update processor after the location information for the mobile device has been recovered.

22. The mobile communication network of claim 17, wherein the message processor:

selects γ

₁ from the set (1, 2, . . . , n);

for i=1, . . . , k−

1, selects γ

i+1 according to γ

irFn/kL+ai, wherein;

r is modulo addition defined over the set (1, 2, . . . , n);

displacement vector â

=(a1, a2, . . . , ak) is a binary vector having a Hamming weight of β

; and

β

=n−

Fn/kL*k; and

transmits location update messages to the k location databases, Dγ

1, . . . , Dγ

k,

referred to by the placement vector, Γ

=(γ

1, . . . , γ

k).

23. The mobile communication network of claim 22, wherein the message processor deletes any location information previously stored in the n location databases, D1, . . . , Dn, for the mobile device, before transmitting the location update messages to the k location databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k).

24. The mobile communication network of claim 23, wherein γ

1 is selected randomly using a uniform distribution over the set (1, 2, . . . , n).

25. The mobile communication network of claim 24, wherein the message processor determines if all of the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . ,γ

k), are accessible, and if all of the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k), are not accessible, selects a different placement vector, Γ

=(γ

1, . . . , γ

k) before transmitting location update messages to the k location databases, Dγ

1, . . . , Dγ

k.

26. The mobile network of claim 25, wherein the message processor selects the placement vector, Γ

=(γ

1, . . . , γ

k), having the most number of databases, Dγ

1, . . . , Dγ

k, that are accessible, if no placement vector, Γ

=(γ

1, . . . , γ

k), can be found in which all the databases, Dγ

1, . . . , Dγ

k, referred to by the placement vector, Γ

=(γ

1, . . . , γ

k), are accessible.

27. The mobile network of claim 26, wherein the displacement vector â

comprises;

0, for a1, . . . , ak−

β

; and

1, for ak−

β

+1, . . . , ak.

28. The mobile network of claim 26, wherein the message processor includes software comprises instructions that cause the message processor to query the location databases for location information about the mobile device.

29. The mobile network of claim 26, wherein the message processor includes software comprises instructions that cause the message processor to query successive location databases on the logical ring for location information about the mobile device until location information about the mobile device is located or until all the location databases have been queried.

30. The mobile network of claim 27, wherein the software further comprises instructions to cause the message processor to:

query a first group of successive location databases on the logical in parallel;

if location information about the mobile is not located by querying the first group of successive location databases, query a second group of successive databases on the logical ring in parallel; and

if location information about the mobile is not located by querying the second group of successive location databases, query additional groups of location databases in parallel until location information for the mobile is located or until all the location databases have been queried.

31. The mobile network of claim 17, wherein the location update processor comprises a message switching center.

32. The mobile network of claim 17, wherein the location database server comprises a home location register.

33. The mobile network of claim 20, wherein the local location information database is a visitor location register.

34. A location update processor for use in a mobile communication network having a mobile device and a location database server having a location database storing location information indicative of the location of the mobile device, the location update processor comprising:

a location database for comprising;

a receiver that receives location update messages from the mobile device when the location of the mobile device changes;

a message processor that;

transmits location update messages to the location database server; and

in the event one of the location update messages is not received by the location database, transmits location update retry messages at the end of successive retry intervals until one of the location update retry messages is received.

35. A method for managing information concerning the location of a mobile device in a mobile communication network, the method comprising:

maintaining a location database that stores location information indicative of the location of the mobile device;

receiving location update messages from the mobile device via a location update processor associated with a particular location area within the network when the location of the mobile device changes;

transmitting the location update messages to the location database;

in the event one of the location update messages is not received by the location database, transmitting location update retry messages from the location update processor at the end of successive retry intervals until one of the location update retry messages is received, wherein the location update message includes a time stamp and the location update retry messages include the time stamp from the location update message;

receiving call delivery request messages from the mobile device via the location update processor;

transmitting at least a subset of the call delivery request messages to the location database; and

recovering location information for the mobile device after a failure in the mobile communication network, wherein the act of recovering includes;

if a location update message or a call delivery request message is received before the retry interval has passed since the failure was removed from the mobile communication network, storing in the location database the location information for the mobile device from the location update message or the call delivery request message; and

if the retry interval has passed since the failure was removed from the mobile communication network without receiving a location update message or a call delivery request message while receiving at least one location update retry message, storing in the location database the location information for the mobile device from the location update retry message having the most recent time stamp.

36. A mobile communication network comprising:

a mobile device;

a location database server having a location database storing location information indicative of the location of the mobile device;

a location update processor that;

receives location update messages from the mobile device when the location of the mobile device changes;

transmits the location update messages to the location database; and

in the event one of the location update messages is not received by the location database, transmits location update retry messages at the end of successive retry intervals until one of the location update retry messages is received, such that the location update message includes a time stamp and the location update processor transmits the time stamp from the location update message in the location update retry messages; and

wherein the location database server includes a recovery processor, for recovering location information for mobile device after a failure in the mobile communication network, that;

if a location update message is received before the retry interval has passed since the failure was removed from the mobile communication network, stores in the location database the location information for the mobile device from the location update message; and

if the retry interval has passed since the failure was removed from the mobile communication network without receiving a location update message while receiving at least one location update retry message, stores in the location database the location information for the mobile device from the location update retry message having the most recent time stamp.