Enhanced worst case cell elimination in zone paging within a cellular communication system

• US 6,122,522 A
• Filed: 02/19/1998
• Issued: 09/19/2000
• Est. Priority Date: 11/06/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Lee, Hee C.
• Primary Examiner(s): Hunter, Daniel S.
• Assistant Examiner(s): TRAN, PABLO N
• Application Number:
  US09/026,089
• Time in Patent Office: 943 Days
• Field of Search: 455/458, 455/422, 455/426, 455/432, 455/434, 455/436, 455/446, 455/453, 455/456, 455/466
• US Class Current: 455/458
• CPC Class Codes: H04W 68/00 User notification, e.g. alerting and paging, for incoming communication, change of service or the like

Abstract

A method for reducing the paging load in a cellular communication system is described. The cell C with the largest paging load L is first identified. Since this cell is usually included in more than one paging zone, the paging zones including cell C are identified. Thereafter, cell C is removed tentatively from each identified zone and a ratio R calculated which represents the decrease in loading on cell C due to being removed from zone z divided by the maximum increase in loading on any other cell in the network. The zone for which the ratio R is the largest is the best candidate for removing cell C therefrom. After doing so tentatively, the cell C'"'"' with the largest paging load L'"'"' thereon is identified. If the loading L is greater than L'"'"', cell G is removed permanently from the zone having the highest ratio R therefor and the process is repeated until L'"'"' is greater than L at which point the process is stopped without removing cell C from the zone with the highest ratio R. In another operation, cell C, a largest paging load L, and a most favorable zone P from which to remove cell C are first identified. Cell C is then tentatively removed from zone P and the identities of Cell C and zone P stored. Should the removal reduce overall paging load, cell C is removed from zone P. If not, operation continues by identifying new cell C and zone P, performing a tentative removal of cell C from zone P and storing such tentative removal. Such operations continue until the overall paging load decreases, at which point all stored cells C are removed from stored zones P. Should paging load cease to improve until a terminating condition is satisfied, none of the stored cells C are removed and operation ends.

Claims

1. A method for minimizing the paging load in a multicell wireless telephone network comprising the steps of:

(a) determining a cell C in the cellular telephone network having a maximum paging load W thereon;

(b) identifying zones in which cell C is located;

(c) of the zones in which cell C is located, determining a zone P that reduces paging load in cell C the most and that increases the paging load in other cells of the network the least;

(d) tentatively removing cell C from zone P and storing the identity of removed cell C in conjunction with zone P;

(e) determining a maximum paging load W'"'"' based upon all previous tentative cell removals included;

(f) when W exceeds W'"'"', permanently executing all tentative cell removals and repeating steps (a) through (e); and

(g) when W does not exceed W'"'"', selecting a new cell C with a maximum paging load thereon based upon all previous tentative cell removals and repeating steps (b) through (f).

2. The method of claim 1, further comprising the step of exiting the process when the paging load on cell C is at least as large as W or when each cells in the network has been removed from at least one zone.

3. The method of claim 1, wherein the paging load on each cell due to paging is determined by counting the number of pages occurring in each cell in the network during a given time period.

4. The method of claim 1, wherein the paging load on each cell due to paging is determined using the equation:

##EQU3## where;

I_i is the probability that the last known cell of mobile m is i;

CZ(x) is the set of zones containing the cell x;

NC(Z(x)) is all other zones;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is in cell i contained in zone Z(i).

5. The method of claim 1, wherein determining the zone P that reduces paging load in cell C the most and that increases the paging load in other cells of the network the least includes maximizing the ratio of the decreased paging load on cell C (p_z) divided by the maximum increase in paging load on any other network cell (m_z).

6. The method of claim 5, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">P.sub.z =I.sub.i -I.sub.i (1-[P(Z(i))-P(i,x)]r)

where;

I_i is the probability that the last known cell of mobile m is i;

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is cell i contained in Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

7. The method of claim 6, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

8. The method of claim 5, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

9. The method of claim 5, wherein the paging load on each cell due to paging is determined using the equation:

##EQU4## where;

I_i is the probability that the last known cell of mobile m is i;

CZ(x) is the set of zones containing the cell x;

NC(Z(x)) is all other zones;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is in cell i contained in zone Z(i).

10. The method of claim 9, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">p.sub.z =I.sub.i -I.sub.i (1-[P(Z(i))-P(i,x)]r)

where;

I_i is the probability that the last known cell of mobile m is i;

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is cell i contained in Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

11. The method of claim 10, wherein m_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

12. The method of claim 9, wherein m_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

13. A method for minimizing the paging load in a multicell wireless telephone network comprising the steps of:

(a) determining the probability P(i,j), for all cells in the network that a given mobile is in cell j given the fact that its last known position was zone i and order the list of probabilities P(i,j) from largest to smallest;

(b) defining a plurality of paging zones Z(i) for each cell i in the network, each particular cell k being included in the zone Z(i) if the following inequality is true;

space="preserve" listing-type="equation">k+(1-(P(i,j)+P(i,j.sub.2)+ . . . +P(i,j.sub.k)))*n<

=k-1+(1-(P(i,j.sub.1)+P(i,j.sub.2)+ . . . +P(i,j.sub.k-1)))*n

and the order of successive probabilities used in the inequality is defined by said ordered list of probabilities P(i,j);

(c) determining a cell C in the cellular telephone network having a maximum paging load W thereon;

(d) identifying zones in which cell C is located;

(e) of the zones in which cell C is located, determining a zone P that reduces paging load in cell C the most and that increases the paging load in other cells of the network the least;

(f) tentatively removing cell C from zone P and storing the identity of removed cell C in conjunction with zone P;

(g) determining a maximum paging load W'"'"' based upon all previous tentative cell removals included;

(h) when W exceeds W'"'"', permanently executing all tentative cell removals and repeating steps (c) through (g); and

(i) when W does not exceed W'"'"', selecting a new cell C with a maximum paging load thereon based upon all previous tentative cell removals and repeating steps (d) through (h).

14. The method of claim 13, further comprising the step of exiting the process when the paging load on cell C is at least as large as W or when each cells in the network ha been removed from at least one zone.

15. The method of claim 13, wherein the paging load on each cell due to paging is determined by counting the number of pages occurring in each cell in the network during a given time period.

16. The method of claim 13, wherein the paging load on each cell due to paging is determined using the equation:

##EQU5## where;

I_i is the probability that the last known cell of mobile m is i;

CZ(x) is the set of zones containing the cell x;

NC(Z(x)) is all other zones;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is in cell i contained in zone Z(i).

17. The method of claim 13, wherein determining the zone P that reduces paging load in cell C the most and that increases the paging load in other cells of the network the least includes maximizing the ratio of the decreased paging load on cell C (p_z) divided by the maximum increase in paging load on any other network cell (m_z).

18. The method of claim 17, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">p.sub.z =I.sub.i -I.sub.i (1-[P(Z(i))-P(i,x)]r)

where;

I_i is the probability that the last known cell of mobile m is i;

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is cell i contained in Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

19. The method of claim 18, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

20. The method of claim 17, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

21. The method of claim 17, wherein the paging load on each cell due to paging is determined using the equation:

##EQU6## where;

I_i is the probability that the last known cell of mobile m is i;

CZ(x) is the set of zones containing the cell x;

NC(Z(x)) is all other zones;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is in cell i contained in zone Z(i).

22. The method of claim 21, wherein p_z is calculated using the equation:

space="preserve" listing-type="equation">p.sub.z =I.sub.i -I.sub.i (1-[P(Z(i))-P(i,x)]r)

where;

I_i is the probability that the last known cell of mobile m is i;

P(Z(i)) is the probability that the mobile m is in zone Z(i) given the last known location of mobile m is cell i contained in Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

23. The method of claim 22, wherein m_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.

24. The method of claim 21, wherein m_z is calculated using the equation:

space="preserve" listing-type="equation">m.sub.z =I.sub.i (P(i,x)r)

where;

I_i is the probability that the last known cell of mobile m is i;

r is the probability that the mobile will respond given it is in zone Z(i); and

P(i,x) is the probability that the mobile will be in cell x given the last known location was cell i.