Location information recovery and management for mobile networks

• US 20040185871A1
• Filed: 01/30/2004
• Published: 09/23/2004
• Est. Priority Date: 09/30/1999
• Status: Active Grant

• Current Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Original Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Inventors: Krishnamurthi, Govindarajan, Somani, Arun K.
• Granted Patent: US 7,113,795 B2
• Time in Patent Office: Days
• 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 at the end of successive retry intervals until one of the location update retry messages is received.

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 5, 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.

9. The method of claim 8, wherein the plurality of location databases comprises n location databases, D₁, . . . , D_n, 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.

10. The method of claim 9, wherein Γ

=(γ

₁,γ

₂, . . . , γ

_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 γ

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

for i=1, . . . , k−

1, selecting γ

_i+1 according to γ

_i⊕

└

n/k┘

+a_i, wherein;

⊕

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

displacement vector â

=(a₁,a₂, . . . , a_k) is a binary vector having a Hamming weight of β

; and

β

=n−

└

n/k┘

*k; and

transmitting location update messages to the k location databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>.

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

1, . . . , D<sub>γ

k</sub>, deleting any location information previously stored in the n location databases, D₁, . . . , D_n, for the mobile device.

12. The method of claim 10, wherein γ

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

13. The method of claim 12, further comprising, before transmitting location update messages to the k location databases, D_γ

1, . . . , D<sub>γ

k</sub>. determining if all of the databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k), are accessible, and if all of the databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, , , , , γ

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

=(γ

₁, . . . , γ

_k).

14. The method of claim 13, wherein if no placement vector, Γ

=(γ

₁, . . . , γ

_k), can be found in which all the databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

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

=(γ

₁, . . . , γ

_k), having the most number of databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, that are accessible.

15. The method of claim 10, wherein the displacement vector â

comprises;

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

β</sub>

; and

1, for a<sub>k−

β

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

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

17. The method of claim 16, 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.

18. The method of claim 16, 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.

19. 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.

20. The mobile communication network of claim 19, 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.

21. The mobile communication network of claim 20, 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.

22. The mobile communication network of claim 21, 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.

23. The mobile communication network of claim 22, 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.

24. The mobile communication network of claim 23, further comprising a plurality of location database servers each having a location database for storing location information indicative of the location of the mobile device.

25. The mobile communication network of claim 24, wherein the plurality of location database servers comprises n location database servers, D₁, . . . , D_n, 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 Γ

=(γ

₁γ

₂, . . . , γ

_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.

26. The mobile communication network of claim 25, wherein the message processor:

selects γ

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

for i=1, . . . , k−

1, selects γ

_i+1 according to γ

_i⊕

└

n/k┘

+a_i, wherein;

⊕

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

displacement vector â

=(₁,a₂, . . . , a_k) is a binary vector having a Hamming weight of β

; and

β

=n−

└

n/k┘

*k; and

transmits location update messages to the k location databases, D<sub>γ

1</sub>, . . . , D_yk, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k).

27. The mobile communication network of claim 26, wherein the message processor deletes any location information previously stored in the n location databases, D₁, . . . , D_n, for the mobile device, before transmitting the location update messages to the k location databases, D_γ

1, . . . , D_yk, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k).

28. The mobile communication network of claim 27, wherein γ

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

29. The mobile communication network of claim 28, wherein the message processor determines if all of the databases, D_γ

1, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k)k, are accessible, and if all of the databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub> referred to. by the placement vector, Γ

=(γ

₁, . . . , γ

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

=(γ

₁, . . . , γ

_k) before transmitting location update messages to the k location databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>.

30. The mobile network of claim 29, wherein the message processor selects the placement vector, Γ

=(γ

₁, . . . , γ

_k), having the most number of databases, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, that are accessible, if no placement vector, Γ

=(γ

₁, . . . , γ

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

1, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k), are accessible.

31. The mobile network of claim 30, wherein the displacement vector â

comprises;

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

β

; and</sub>

1, for a<sub>k−

β

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

32. The mobile network of claim 30, 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.

33. The mobile network of claim 30, 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.

34. The mobile network of claim 31, 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.

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

36. The mobile network of claim 19 wherein the location database server comprises a home location register.

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

38. A location database server that receives location update messages having time stamps transmitted by a location update processor when a mobile device enters a location area associated with the location update processor and location update retry messages transmitted at the end of successive retry intervals by the location update processor in the event one of the location update messages is not received by the location database server, wherein the location update retry messages include the time stamps from the unreceived location update message, the location database server comprising:

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

a recovery processor, for recovering location information for the mobile device after a failure in the mobile communication network is fixed, that;

in the event that a location update message is received before the retry interval has passed since the failure was fixed, stores in the location database the location information for the mobile device from the location update message; and

in the event that the retry interval has passed since the failure was fixed 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.

39. 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.

40. In a distributed database system having n database servers, D₁, . . . , D_n, arranged in a logical ring, a method of updating k of the database servers, D_γ

1, . . . , D<sub>γ

k</sub>, referred to by a placement vector Γ

=(γ

₁, . . . , γ

_k), wherein γ

i ε

{1, . . . ,n} is the index of the ith database server updated by the method, the method comprising;

selecting γ

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

for i=1, . . . , k−

1, selecting γ

_i+1 according to γ

⊕

└

n/k┘

+a_i, wherein;

⊕

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

displacement vector â

=(a₁, . . . , a_k) is a binary vector having a Hamming weight of β

; and

β

=n−

└

n/k┘

*k; and

updating the k database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector Γ

=(γ

₁, . . . , γ

_k), with updated information.

41. The method of claim 40, wherein the database servers are location database servers for storing location information about a mobile device.

42. The method of claim 41, wherein updating the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, includes updating the k location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector Γ

=(γ

₁, . . . , γ

_k, with current location information for a mobile device.

43. The method of claim 42, wherein updating the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, includes transmitting location update messages to the k location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>.

44. The method of claim 43, further comprising, before transmitting location update messages to the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, deleting any location information previously stored in the n location database servers, D₁, . . . , D_n, for the mobile device.

45. The method of claim 43, wherein γ

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

46. The method of claim 45, further comprising, before transmitting location update messages to the k location database servers, D_γ

1, . . . , D<sub>γ

k</sub>, determining if all of the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

_k), are accessible, and if all of the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

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

=(γ

₁, . . . , γ

_k).

47. The method of claim 46, wherein if no placement vector, Γ

=(γ

₁, . . . , γ

_k), can be found in which all the location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, referred to by the placement vector, Γ

=(γ

₁, . . . , γ

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

=(γ

₁, . . . , γ

_k), having the most number of location database servers, D<sub>γ

1</sub>, . . . , D<sub>γ

k</sub>, that are accessible.

48. In a distributed database system having n database servers, D₁, . . . . D_n, arranged in a logical ring for storing information about a first group of items in k, of the database servers and for storing information about a second group of items in k₂ of the database servers, wherein k₁>

k₂, a method of querying the database servers for information about a given item, the method comprising;

selecting a first database server D_i;

determining in parallel if any of ┌

n/k₁┐

successive database servers, D_i, D_i+1, . . . , D<sub>i⊕

┌

n/k1┐</sub>

, on the logical ring contain information about the given item;

if at least one of the ┌

n/k₁┐

successive database servers, D_i, . . . , D<sub>i⊕

┌

n/k1┐</sub>

, does not contain information about the given item then determining in parallel if any of the next (┌

n/k₁┐

−

┌

n/k₂┐

) successive database servers, D<sub>i⊕

┌

n/k1┐

⊕

1</sub>, . . . , D<sub>i⊕

┌

n/k2┐</sub>

, on the logical ring contain information about the given device; and

if at least one of the next (┌

n/k₂┐

−

┌

n/k₁┐

) successive database servers, D<sub>i⊕

┌

n/k1┐

⊕

1</sub>, . . . , D<sub>i⊕

┌

n/k2┐</sub>

, does not contain information about the given item, then until information for the given item is found or until all the database servers D₁, . . . , D_n, have been checked, determining in parallel if successive groups of ┌

n/k₂┐

database servers, D<sub>i⊕

(j*┌

n/k2┐

)⊕

1</sub>, . . . , D<sub>i⊕

(j+1)*┌

n/k2┐</sub>

, on the logical ring contain information for the given item wherein j represents the jth group of ┌

n/k₂┐

database servers that are checked.

49. The method of claim 48, wherein the database servers are location database servers for storing location information about a first group of mobile device in k₁ of the location database servers and for storing location information about a second group of mobile devices in k₂ of the location database servers, and wherein the method queries the location database servers for location information about a given mobile device.

50. A method of updating a database over a network with information from a device, the method comprising:

receiving update messages from the device via a processor connected to the network;

transmitting the update messages to the database; and

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