US 7,031,731 B2 · Methods and systems for concurrent paging of mobile users in cellular networks

Abstract

Methods for concurrent paging, in a cellular system having a number of users, where the users are paged to determine a location of each user, are disclosed. The paging from one cell to one of the users occurs within one of a number of time slots. The time slot in which one of the users is paged from one of the cells is a characteristic of that cell and that user. An array encompassing the totality of the characteristics time slots constitutes a search schedule. One method comprises minimizing a characteristic function of paging performance, the function depending on the search schedule and the probability of finding a user in a cell, and, determining, from the minimization of the characteristic function, the search schedule. Two other methods for determining a search schedule, which are more computationally efficient and which reduce the paging cost, the simple heuristic and the conditional probability heuristic, are disclosed.

Claims32

Dependent claims

A method for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and wherein, in one of said time slots, only one of the users is paged from one of the cells, the method comprising the steps of:

minimizing a characteristic function of paging performance, said function depending on a search schedule and the probability of finding a user in a cell;
wherein said search schedule comprises a two dimensional array of indices of a time slot in which one user is paged from one cell;
determining, from the minimization of the characteristic function, an optimal search schedule;
whereby users from said plurality of users are paged simultaneously.

1 more element

A method for concurrently paging in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the method comprising the steps of:

minimizing a characteristic function of paging performance:
wherein the step of minimizing a characteristic function of paging performance comprises the steps of:
A) selecting a pair of users, a first user and a second user, from the plurality of users;
B) selecting a pair of time slots, a first time slot and a second time slot, from the plurality of time slots;
C) determining, from the unique probability of any of the users being located in any of the cells, which of said first and said second users has a higher probability of being located in a pre-selected range from the plurality of cells;
D) if it is more probable that said first user be located in said pre-selected range, performing the following steps:
paging said first user from said first time slot in each cell from said pre-selected range;
paging said second user from said second time slot in each cell from said pre-selected range;
paging said first user from said second time slot in each cell from another pre-selected range of said plurality of cells;
and,
paging said second user from said first time slot in each cell from said another pre-selected range;
E) if it is more probable that said second user be located in any cell from said pre-selected range, performing the following steps:
paging said first user from said second time slot in each cell from said pre-selected range;
paging said second user from said first time slot in each cell from said pre-selected range;
paging said first user from said first time slot in each cell from said another pre-selected range;
and,
paging said second user from said second time slot in each cell from said another pre-selected range;
F) repeating steps A through E for a next pair of users and a next pair of time slots until all pairs of users are selected;
whereby, from the minimization of the characteristic function, a search schedule is determined;
wherein said search schedule comprises a two dimensional array of indices of a time slot in which one user is paged from one cell.

17 more elements

A method for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the method comprising the steps of:

minimizing a characteristic function of paging performance:
wherein the step of minimizing a characteristic function of paging performance comprises the steps of:
A) obtaining a probability array having as initial value an array comprising a totality of the unique probabilities;
B) selecting an initial time slot from the plurality of time slots;
C) selecting, for each one cell from the plurality of cells, one user to be paged from the plurality of users;
D) paging the selected user in said each one cell;
E) determining from said paging whether the selected user has been located;
F) updating the probability array according to said paging;
G) proceeding to a next time slot from the plurality of time slots;
H) repeating the steps C through G unless a predetermined condition is satisfied;
and determining, from the minimization of the characteristic function, a search schedule;
wherein said search schedule comprises a two dimensional array of indices of a time slot in which one user is paged from one cell.

9 more elements

A computer program product comprising:

a computer usable medium having computer readable code embodied therein for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the computer program product:
comprising:
computer readable code means for causing a computer system to minimize a characteristic function of paging performance;
wherein said computer readable code means for causing said computer system to minimize a characteristic function of paging performance cause said computer system to:
A) select a pair of users, a first user and a second user, from the plurality of users;
B) select a pair of time slots, a first time slot and a second time slot, from the plurality of time slots;
C) determine, from the unique probability of any of the users being located in any of the cells, which of said first and said second users has a higher probability of being located in a pre-selected range from the plurality of cells;
D) if it is more probable that said first user be located in said pre-selected range, perform the following steps:
page said first user from said first time slot in each cell from said pre-selected range;
page said second user from said second time slot in each cell from said pre-selected range;
page said first user from said second time slot in each cell from another pre-selected range of said plurality of cells;
and,
page said second user from said first time slot in each cell from said another pre-selected range;
E) if it is more probable that said second user be located in any cell from said pre-selected range, perform the following steps:
page said first user from said second time slot in each cell from said pre-selected range;
page said second user from said first time slot in each cell from said pre-selected range;
page said first user from said first time slot in each cell from said another pre-selected range;
and,
page said second user from said second time slot in each cell from said another pre-selected range;
F) repeat steps A through E for a next pair of users and a next pair of time slots until all pairs of users are selected;
computer readable code means for causing said computer system to determine, from the minimization of the characteristic function, a search schedule;
wherein said search schedule comprises a two dimensional array of indicies of a time slot in which one user is paged from one cell which enables concurrent paging.

19 more elements

A computer program product comprising:

a computer usable medium having computer readable code embodied therein for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the computer program product comprising:
computer readable code means for causing a computer system to minimize a characteristic function of paging performance;
wherein said computer readable code means for causing said computer system to minimize a characteristic function of paging performance are capable of causing said computer system to:
A) obtain a probability array having as initial value an array comprising a totality of the unique probabilities;
B) select an initial time slot from the plurality of time slots;
C) select for each one cell from the plurality of cells, one user to be paged from the plurality of users;
D) page the selected user in said each one cell;
E) determine from said paging whether the selected user has been located;
F) update the probability array according to said paging;
G) proceed to a next time slot from the plurality of time slots;
H) repeat the steps C through G unless a predetermined condition is satisfied;
computer readable code means for causing said computer system to determine, from the minimization of the characteristic function, a search schedule;
wherein said search schedule comprises a two dimensional array of indices of a time slot in which one user is paged from one cell, which enables concurrent paging.

10 more elements

A system for concurrently paging in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the system comprising:

at least one processor:
at least one computer readable medium, having computer readable code embodied therein, said code causing the at least one processor to:
A) select a pair of users, a first user and a second user, from the plurality of users;
B) selecting a pair of time slots, a first time slot and a second time slot, from the plurality of time slots;
C) determining, from the unique probability of any of the users being located in any of the cells, which of said first and said second users has a higher probability of being located in a pre-selected range from the plurality of cells;
D) if it is more probable that said first user be located in said pre-selected range, performing the following steps:
paging said first user from said first time slot in each cell from said pre-selected range;
paging said second user from said second time slot in each cell from said pre-selected range;
paging said first user from said second time slot in each cell from another pre-selected range of said plurality of cells;
and,
paging said second user from said first time slot in each cell from said another pre-selected range;
E) if it is more probable that said second user be located in any cell from said pre-selected range, performing the following steps:
paging said first user from said second time slot in each cell from said pre-selected range;
paging said second user from said first time slot in each cell from said pre-selected range;
paging said first user from said first time slot in each cell from said another pre-selected range;
and,
paging said second user from said second time slot in each cell from said another pre-selected range;
F) repeating steps A through E for a next pair of users and a next pair of time slots until all pairs of users are selected;
wherein a search schedule is determined;
wherein said search schedule comprises a two dimensional all of indices of a time slot in which one user is paged from one cell, which enables concurrent paging.

17 more elements

A system for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the system comprising:

at least one processor;
at least one computer readable medium, having computer readable code embodied therein, said code causing the at least one processor to:
A) obtain a probability array having as initial value an array comprising a totality of the unique probabilities;
B) select an initial time slot from the plurality of time slots;
C) select for each one cell from the plurality of cells, one user to be paged from the plurality of users;
D) page the selected user in said each one cell;
E) determine from said paging whether the selected user has been located;
F) update the probability array according to said paging;
G) proceed to a next time slot from the plurality of time slots;
H) repeat the steps C through G unless a predetermined condition is satisfied;
wherein a search schedule is determined;
wherein said search schedule comprises a two dimensional array of indices of a time slot in which one user is paged from one cell, which enables concurrent paging.

9 more elements

A concurrent paging schedule for concurrently paging, in a cellular system having a plurality of users, the users being paged to determine a location of each user, the paging to one of the plurality of users originating from one of a plurality of cells, any of the users being located in any of the cells with a given unique probability corresponding to the user and the cell, the paging from the cell to one of the users occurring within one of a plurality of time slots, the time slot in which one of the users is paged in one of the cells being a characteristic of the one cell and the one user, and, wherein, in one of said time slots, only one of the users is paged from one of the cells, the concurrent paging schedule obtained by the steps of:

A) selecting a pair of users, a first user and a second user, from the plurality of users;
B) selecting a pair of time slots, a first time slot and a second time slot, from the plurality of time slots;
C) determining, from the unique probability of any of the users being located in any of the cells, which of said first and said second users has a higher probability of being located in a pre-selected range from the plurality of cells;
D) if it is more probable that said first user be located in said pre-selected range, performing the following steps:
paging said first user from said first time slot in each cell from said pre-selected range;
paging said second user from said second time slot in each cell from said pre-selected range;
paging said first user from said second time slot in each cell from another pre-selected range of said plurality of cells;
and,
paging said second user from said first time slot in each cell from said another pre-selected range;
E) if it is more probable that said second user be located in any cell from said pre-selected range, performing the following steps:
paging said first user from said second time slot in each cell from said pre-selected range;
paging said second user from said first time slot in each cell from said pre-selected range;
paging said first user from said first time slot in each cell from said another pre-selected range;
and,
paging said second user from said second time slot in each cell from said another pre-selected range;
F) repeating steps A through E for a next pair of users and a next pair of time slots until all pairs of users are selected
whereby said concurrent paging schedule enables concurrent paging.

14 more elements

Dependencies are inferred from the claim text.

Methods and systems for concurrent paging of mobile users in cellular networks

Life of this patent

Methods and systems for concurrent paging of mobile users in cellular networks

Life of this patent

Abstract

Claims32