Method for allocating identifiers in a cellular wireless network

• US 6,778,833 B1
• Filed: 11/13/2000
• Issued: 08/17/2004
• Est. Priority Date: 11/13/2000
• Status: Expired due to Fees

• Current Assignee: Sprint Spectrum LP (Deutsche Telekom AG)
• Original Assignee: Sprint Spectrum LP (Deutsche Telekom AG)
• Inventors: Fortuna, Frederick
• Primary Examiner(s): Gary, Erika
• Assistant Examiner(s): Afshar, Kamran
• Application Number:
  US09/711,439
• Time in Patent Office: 1,373 Days
• Field of Search: 455/446, 455/444, 455/445, 455/435.2, 455/428, 455/422.1, 455/423, 455/424, 455/500-502, 455/512-513, 455/515-516, 455/524-525, 455/560-561, 455/453, 370/335, 370/342, 370/332, 370/333
• US Class Current: 455/446
• CPC Class Codes: H04W 16/02 Resource partitioning among network components, e.g. reuse partitioning
• CPC Class Codes: H04W 16/12 Fixed resource partitioning
• CPC Class Codes: H04W 16/24 Cell structures

Abstract

A method for allocating identifiers in a cellular wireless network. The method may determine the optimal distribution of identifiers, such as pseudo-random offset numbers, to the sectors and cells of a Code Division Multiple Access cellular wireless system. The method may ensure that those identifiers that are used more than once by the system are allocated to sectors that are as far apart as possible. The method allocates identifiers preferentially to sectors in more tightly packed regions of the network. Then the method determines how widely spread the identifiers are. Sectors with identifiers that are near each other are then preferentially reallocated their identifiers. The method repeats determining the spread of identifiers and reallocating the identifiers until the sectors retain the same identifiers, thereby reflecting a stable allocation of identifiers in the cellular wireless system.

Claims

1. A method for allocating a plurality of identifiers to a plurality of sectors of a cellular wireless network to reduce interference between base stations for the sectors, the method comprising the steps of:

(a) determining a measure of neighbor density for each sector;

(b) ranking the plurality of sectors according to the measure of neighbor density to produce a first rank order of sectors;

(c) allocating identifiers to sectors in the first rank order, beginning with a highest ranked sector in the first rank order;

(d) evaluating an exclusion range for each sector, the exclusion range being a measure of minimal distance between the sector, the sector having an allocated identifier, and other sectors also having the allocated identifier;

(e) ranking the plurality of sectors that have a determined exclusion range to produce a second rank order of sectors in order of their determined exclusion range, wherein each sector retains the identifier that was previously allocated to the sector;

(f) allocating identifiers to the sectors in the second rank order, beginning with lowest ranked sector in the second rank order; and

repeating steps (d), (e), and (f) until each sector of the plurality of sectors retains the identifier that was previously allocated to the sector.

2. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 1.

3. The method of claim 1 wherein step (c) or step (f) comprises the steps of:

creating a pool of available identifiers for the sector;

selecting the identifier for the sector from the pool of available identifiers; and

allocating the identifier to the sector.

4. The method of claim 3 wherein the creating step comprises:

eliminating a first selection of identifiers from the plurality of identifiers to create the pool of available identifiers for the sector, wherein each identifier of the first selection of identifiers was previously allocated to a neighboring sector.

5. The method of claim 4 wherein the neighboring sector is at most three sectors away from the sector.

6. The method of claim 3 wherein the creating step comprises:

eliminating a second selection of identifiers from the plurality of identifiers to create the pool of available identifiers for the sector, wherein each identifier of the second selection of identifiers has been allocated to more than a minimum number of sectors.

7. The method of claim 6 wherein the minimum number of sectors is three.

8. The method of claim 3 wherein the creating step comprises:

eliminating a third selection of identifiers from the plurality of identifiers to create the pool of available identifiers for the sector, wherein each identifier of the third selection of identifiers is reserved.

9. The method of claim 3 wherein the selecting step comprises the steps of:

associating, for each available identifier in the pool of available identifiers for the sector, a reuse range with the available identifier, wherein the reuse range is a measure of minimal distance between two sectors that share the available identifier; and

selecting the available identifier that is associated with greatest reuse range.

10. The method of claim 3 wherein the selecting step comprises the steps of:

associating, for each available identifier in the pool of available identifiers for the sector, a reuse range with the available identifier, wherein the reuse range is a measure of minimal distance between two sectors that share the available identifier; and

determining whether there are more than one available identifiers that are associated with greatest reuse range, and if so,

selecting the identifier randomly from the more than one available identifiers that are associated with greatest reuse range.

11. The method of claim 1 wherein step (a) comprises the steps of:

ascertaining a plurality of neighbors for the sector, wherein each neighbor of the plurality of neighbors is no more than a minimum number of sectors away from the sector;

counting the plurality of neighbors to obtain a total number of neighbors; and

setting the measure of neighbor density equal to the total number of neighbors.

12. The method of claim 11 wherein the ascertaining step comprises the steps of:

examining a neighbor list for the sector; and

retaining the plurality of sectors that are no more than the minimum number of sectors away from the sector.

13. The method of claim 11 wherein the minimum number of sectors is three.

14. The method of claim 1 wherein step (d) comprises:

determining, for each other sector of the plurality of sectors, whether the other sector shares the identifier with the sector, and if so,

estimating a distance from the other sector to the sector, and

determining whether the distance is a minimum distance, and if so,

setting the exclusion range equal to the minimum distance.

15. The method of claim 1 wherein the cellular wireless network is a Code Division Multiple Access cellular wireless system and the plurality of identifiers is a plurality of pseudo-random offset numbers.

16. The method of claim 1 wherein the cellular wireless network is a Time Division Multiple Access cellular wireless system and the plurality of identifiers is a plurality of frequency groups.

17. A method for allocating a plurality of pseudo-random offset numbers to a plurality of sectors of a Code Division Multiple Access cellular wireless network to reduce interference between base stations for the sectors, the method comprising the steps of:

(a) ascertaining a plurality of neighbors for each sector, wherein each neighbor of the plurality of neighbors is no more than three sectors away from the sector;

(b) counting the plurality of neighbors to obtain a total number of neighbors;

(c) setting a measure of neighbor density equal to the total number of neighbors;

(d) ranking the plurality of sectors according to the measure of neighbor density to produce a first rank order of sectors;

(e) allocating pseudo-random offset numbers to sectors in the first rank order, beginning with a highest ranked sector in the first rank order;

(f) evaluating an exclusion range for each sector, the exclusion range being a measure of minimal distance between the sector, the sector having an allocated pseudo-random offset number, and other sectors also having the allocated pseudo-random offset number;

(g) ranking the plurality of sectors that have a determined exclusion range to produce a second rank order of sectors in order of their determined exclusion range, wherein each sector retains the pseudo-random offset number that was previously allocated to the sector;

(h) allocating pseudo-random offset numbers to the sectors in the second rank order, beginning with lowest ranked sector in the second rank order; and

repeating steps (f), (g), and (h) until each sector of the plurality of sectors retains the pseudo-random offset number that was previously allocated to the sector.

18. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 17.

19. The method of claim 17 wherein step (e) or step (h) comprises the steps of:

eliminating a first selection of pseudo-random offset numbers from the plurality of pseudo-random offset numbers to create a first pool of available pseudo-random offset numbers for the sector, wherein each pseudo-random offset number of the first selection of pseudo-random offset numbers is reserved;

eliminating a second selection of pseudo-random offset numbers from the plurality of pseudo-random offset numbers from the first pool to create a second pool of available pseudo-random offset numbers for the sector, wherein each pseudo-random offset number of the second selection of pseudo-random offset numbers was previously allocated to a neighboring sector;

eliminating a third selection of pseudo-random offset numbers from the plurality of pseudo-random offset numbers from the second pool to create a third pool of available pseudo-random offset numbers for the sector, wherein each pseudo-random offset number of the third selection of pseudo-random offset numbers has been allocated to more than a minimum number of sectors;

associating, for each available pseudo-random offset number in the third pool of available pseudo-random offset numbers for the sector, a reuse range with the available pseudo-random offset number, wherein the reuse range is a measure of minimal distance between two sectors that share the available pseudo-random offset number; and

selecting the available pseudo-random offset number that is associated with greatest reuse range.