Method for dynamically allocating carriers in a wireless packet network, with reuse of carriers

• US 6,496,490 B1
• Filed: 07/09/1998
• Issued: 12/17/2002
• Est. Priority Date: 07/09/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Dominique, Francis, Borst, Simon C., Jelenkovic, Predrag, Kumaran, Krishnan, Whiting, Philip Alfred, Andrews, Daniel Matthew
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Pham, Brenda
• Application Number:
  US09/112,547
• Time in Patent Office: 1,622 Days
• Field of Search: 370/227, 370/228, 370/302, 370/329, 370/341, 370/431, 370/437, 370/450, 370/464, 455/450, 455/455, 455/464, 455/509, 455/516, 455/447
• US Class Current: 370/329
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

We disclose a method of dynamic channel assignment for wireless transmission systems that employ time or frequency multiplexing, or both time and frequency multiplexing. The invention is specifically addressed to the problem of avoiding interference in the channels of such systems. In a broad aspect, the invention involves partitioning base stations of a network into non-interfering sets. Channels are allocated to the non-interfering sets according to need. Stages of channel reallocation take place periodically. The reallocation takes place through coordinated activity by the base stations. That is, the channel reallocation is carried out in response to information that is exchanged between base stations, or it is centrally directed by the network in response to information passed to the network by the base stations.

Claims

1. A method for allocating multiple communication channels among a plurality of base stations belonging to a wireless communication network of the kind in which a queue of waiting units of buffer content can accumulate for each base station, each said queue having a respective queue length, the method comprising:

assigning channels to base stations according to a rule that forbids concurrent use of the same channel by interfering base stations; and

at least once, reassigning one or more channels to at least one of said base stations according to said rule, wherein said reassignment of channels is carried out in response to a communication between said base station and at least one other network entity, and said reassignment of channels is carried out in a manner responsive to the queue length of said base station, wherein;

the reassignment of channels to at least one base station comprises reassigning at least one channel to a base station from a neighboring base station;

each said communication between a base station and a network entity comprises a meassage issued to said base station, by at least one neighboring base station, identifying channels that are available for reassignment; and

the reassignment of channels to said base station comprises selecting one or more channels for reassignment from those channels identified as available.

2. The method of claim 1, wherein:

the method further comprises calculating a target number of channels for each of at least some of the base stations; and

each message issued by a base station to identify channels available for reassignment is responsive to the excess, if any, of channels currently assigned to said base station over the target number of said base station.

3. The method of claim 2, wherein:

the plurality of base stations is subdivided into at least two distinct non-interfering sets, to be referred to as reuse groups; and

the reassignment of channels to any given base station is limited to reassignment from neighbors which do not belong to the same reuse group as the given base station.

4. The method of claim 3, wherein:

in an initial allocation, a distinct subset of channels is allocated to each reuse group;

the method further comprises, for each base station, designating channels, if any, that are available for reassignment; and

designated channels are channels that belong to the subset initially allocated to the pertinent base station and are in excess over the target number calculated for said base station.

5. The method of claim 4, wherein:

the reassignment of channels comprises reassigning channels to those base stations for which the target number exceeds the number of channels initially allocated to the reuse group of said base stations.

6. The method of claim 5, wherein the reassignment of channels is carried out such that no base station receives more channels than necessary to meet said base station'"'"'s target number.

7. The method of claim 6, wherein:

the reassignment of channels takes place in response to channel requests sent to its neighbors by each base station having a target number that exceeds its current number of assigned channels, such base station to be referred to as a borrower.

8. The method of claim 7, wherein the reassignment of channels takes place in one or more concerted rounds, including a first round.

9. The method of claim 8, wherein:

a superframe is specified as a fixed, integer number of frames; and

each round must be completed within one superframe.

10. The method of claim 9, wherein:

each borrower belongs to a reuse group;

each reuse group has an image reuse group under a permutation of the reuse groups; and

in the first round, each borrower sends channel requests only to base stations belonging to a corresponding one of said image reuse groups.

11. The method of claim 10, wherein:

there are two or more rounds;

in each round after the first, each borrower sends channel requests to the same neighbors as in all previous rounds; and

in each round after the first, each borrower sends further channel requests to base stations belonging to a corresponding image reuse group under a further permutation.

12. The method of claim 11, wherein:

in each round, borrowers of all reuse groups actively send channel requests.

13. The method of claim 12, wherein:

all rounds must be completed within one superframe.

14. The method of claim 9, wherein:

in each superframe, the base stations of only one reuse group actively send channel requests.

15. The method of claim 14, wherein:

each borrower, during a superframe in which it actively sends channel requests, sends channel requests to base stations of all reuse groups not its own.

16. The method of claim 1, wherein each said communication between a base station and a network entity comprises a message, to be referred to as an upstream message, from said base station to a network entity, wherein:

the upstream message is derived from the queue length of said base station; and

the reassignment of channels is responsive to upstream messages received by the network entity from at least some of the base stations.

17. The method of claim 16, wherein the reassignment of channels comprises:

(a) determining a non-interfering set of base stations, to be referred to as an MIS, having a maximal aggregate queue length;

(b) allocating at least one channel to the base stations of the MIS; and

(c) reducing the queue lengths of said base stations according to the capacity of the allocated channel or channels.

18. The method of claim 17, further comprising:

repeating steps (a)-(c) at least once.

19. The method of claim 18, further comprising:

repeating steps (a)-(c) until all channels are allocated.

20. The method of claim 1, wherein:

the plurality of base stations is subdivided into at least two distinct non-interfering sets, to be referred to as reuse groups;

the reassignment of channels to any given base station is limited to reassignment from neighbors which do not belong to the same reuse group as the given base station;

a superframe is specified as a fixed, integer number of frames; and

in each superframe, channels are reassigned to base stations of only one reuse group, said reuse group to be referred to as the active reuse group, the remaining reuse groups to be referred to as passive reuse groups.

21. The method of claim 20, further comprising, in each superframe:

for each base station of the passive reuse groups, determining which of the channels currently allocated to said base station will be retained in the next superframe by said base station.

22. The method of claim 21, wherein, in each superframe:

via communications between neighboring base stations, each active base station determines which channels will not be retained in the next superframe by its neighboring base stations; and

each active base station allocates to itself said non-retained channels.