Bandwidth allocation method and apparatus for fixed wireless networks

• US 20050007991A1
• Filed: 07/10/2003
• Published: 01/13/2005
• Est. Priority Date: 07/10/2003
• Status: Abandoned Application

• Current Assignee: Arcowv Wireless LLC (Intellectual Ventures LLC)
• Original Assignee: Arcowv Wireless LLC (Intellectual Ventures LLC)
• Inventors: Ton, Dat, Rath, Kamlesh
• Application Number:
  US10/619,369
• Publication Number:
  US 20050007991A1
• Time in Patent Office: Days
• US Class Current: 370/349
• CPC Class Codes: H04L 12/14 Charging , metering or billing arrangements for data wireline or wireless communications
• CPC Class Codes: H04L 12/146 using digital cash
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04Q 3/0066 Bandwidth allocation or management
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 72/541 using the level of interference

Abstract

A simple, fair, good-performance bandwidth allocation algorithm for wireless networks is presented. Using a matrix of interlink interference and a list of links'"'"' bandwidth requests, the algorithm can schedule link activities to obtain non-collision transmissions. All bandwidth requests are served fairly and near-optimally based on the heuristic algorithm. Bandwidth granted for each link is prorated based on its requested bandwidth, total requested bandwidth in the network, and network capacity. The algorithm can be used for centralized bandwidth allocation and works with any network topology, including mesh networks.

Claims

1. A method for bandwidth allocation for a wireless network, comprising the steps of:

using a matrix of interlink interference and a list of links'"'"' bandwidth requests to schedule link activities to obtain non-collision transmissions;

wherein bandwidth needed by said links to carry actual traffic over a specific time period is represented as a set of link bandwidth requests;

wherein bandwidth requests are expressed in units of credits; and

wherein a credit is a unit assigned to said bandwidth requests to maintain fair bandwidth distribution between said links; and

prorating bandwidth granted for each link based on said link'"'"'s requested bandwidth, total requested bandwidth in said wireless network, and network capacity.

2. The method of claim 1, further comprising the steps of:

providing a centralized node in said wireless network for coordinating substantially all network activities.

3. The method of claim 2, wherein said hub comprises:

an interference matrix;

a topology matrix for defining valid links that can transmit/receive data; and

a list of credit request tokens, wherein each token represents a directional link that needs bandwidth.

4. The method of claim 3, said hub collecting information from individual nodes and constructing said interference matrix, topology matrix, and list of credit tokens therefrom.

5. A bandwidth allocation method for a network, comprising the steps of:

sorting credit request tokens in descending order of a product of requested credits and degree of interference α

(I_ij, L), where L is a set of links requesting credits;

picking a first token having a largest product, wherein said first token is a first candidate link of a set of links to be allocated credit for a first round;

eliminating all other tokens from said first round that cannot be active due to said first candidate link'"'"'s activity;

walking down a list and picking a next eligible token, wherein said next eligible token comprises a second candidate link of said set of links to be allocated credits for a second round;

eliminating all other tokens from said second round that cannot be active due to said second candidate link'"'"'s activity; and

continuing until said list of links is exhausted;

producing a set of links that can be active at a same time L₁={I₁, I₂, . . . , I_n}.

6. The method of claim 5, further comprising the steps of:

letting β

_Ii be requested credits of link I_j, wherein an amount of credits allocated to each element of set L₁ is γ

₁=min{β

_I1, β

_I2, . . . , β

_In};

adjusting said requested credits for every element in L₁;

β

_Ii=β

_Ii−

γ

₁; and

removing tokens which have zero requested credits from said list of tokens.

7. The method of claim 6, further comprising the step of:

adjusting a degree of interference of affected links, due to the fact that some tokens have been removed.

8. The method of claim 7, further comprising the step of:

repeating all foregoing steps until said list of tokens is empty.

9. The method of claim 8, wherein a list (L₁, γ

₁), (L₂, γ

₂) . . . (L_k, γ

_k) results.

10. The method of claim 9, further comprising the steps of:

prorate said list to attain a final schedule;

letting S be a total resource of a network in terms of credit; and

letting χ

_i=γ

_i*S//Σ

_0,kγ

_j;

wherein said list (L₁, χ

₁), (L₂, χ

₂) . . . (L_k, γ

_k) represents how said links are organized into sets of concurrent active links and how much resource each set of links is supposed to get.

11. The method of claim 10, further comprising the step of:

broadcasting said list (L₁, χ

₁), (L₂, χ

₂) . . . (L_k, χ

_k) to all nodes in said network.

12. An apparatus for bandwidth allocation for a wireless network, comprising:

a matrix of interlink interference;

a list of links'"'"' bandwidth requests;

wherein said matrix of interlink interference and said list of links'"'"' bandwidth requests is used to schedule link activities to obtain non-collision transmissions;

wherein bandwidth needed by said links to carry actual traffic over a specific time period is represented as a set of link bandwidth requests;

wherein bandwidth requests are expressed in units of credits; and

wherein a credit is a unit assigned to said bandwidth requests to maintain fair bandwidth distribution between said links; and

means for prorating bandwidth granted for each link based on said link'"'"'s requested bandwidth, total requested bandwidth in said wireless network, and network capacity.

13. The apparatus of claim 12, further comprising:

a centralized node in said wireless network for coordinating substantially all network activities.

14. The apparatus of claim 12, wherein said hub comprises:

an interference matrix;

a topology matrix for defining valid links that can transmit/receive data; and

a list of credit request tokens, wherein each token represents a directional link that needs bandwidth.

15. The apparatus of claim 13, further comprising:

means for said hub collecting information from individual nodes and constructing said interference matrix, topology matrix, and list of credit tokens therefrom.