Distributed bandwidth allocation and transmission coordination method for quality of service provision in wireless AD HOC networks

• US 20040156312A1
• Filed: 12/17/2003
• Published: 08/12/2004
• Est. Priority Date: 12/17/2002
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Tassiulas, Leandros, Salonidis, Theodoros
• Granted Patent: US 7,961,702 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04W 28/20 Negotiating bandwidth
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Methods, devices, systems, and computer programs are provided that allow for optimally allocating bandwidth in an ad hoc, wireless network configured to support at least one guaranteed feasible flow allocation. According to some of these methods, devices, systems, Quality of Service guarantees may be provided across the network. Also, in many instances, the methods are iterative and allow for convergence to an optimized bandwidth allocation.

Claims

1. A method of allocating bandwidth in a first node that is operable in an ad hoc, wireless network configured to support at least one guaranteed feasible flow allocation, the method comprising the steps of:

initiating a communication between the first node and a second node in the network that, together, are endpoints of a link, the communication being related to possible bandwidth allocation adjustment of a flow sharing the link;

determining, in the first node, a first new bandwidth allocation that approaches a first optimization condition for the flow;

communicating with the second node to determine a mutually-agreed upon optimal bandwidth allocation for the flow;

notifying neighbor nodes in the network of the mutually-agreed upon optimal bandwidth allocation when reallocation is needed; and

adopting the mutually-agreed upon optimal allocation for the flow when reallocation is needed.

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

re-performing the initiating, determining, communicating, notifying, and adopting steps at a later point in time.

3. The method of claim 1 wherein the determining step comprises determining, in the first node, a first new bandwidth allocation that approaches at least one of a Max Min Fair condition and a Quality of Service guarantee condition.

4. The method of claim 1, wherein the initiating step comprises initiating a communication between the first node and the second node in a slotted, ad hoc, wireless network.

5. The method of claim 1, wherein the initiating step comprises initiating a communication between the first node and the second node in a network on which a Time Division Multiple Access (TDMA) schedule is implemented.

6. A network device configured to allocate bandwidth in an ad hoc, wireless network configured to support at least one guaranteed feasible flow allocation, the device comprising:

a first communication unit configured to initiate a communication between the device and a node in the network that, together, are endpoints of a link in the network, the communication being related to possible bandwidth allocation adjustment of a flow sharing the link;

a first processing unit configured to determine a first new bandwidth allocation that approaches a first optimization condition for the flow, wherein the first processing unit is operably connected to the first communication unit;

a second communication unit configured to communicate with the node to determine a mutually-agreed upon optimal bandwidth allocation for the flow, wherein the second communication unit is operably connected to the first communication unit;

a third communication unit configured to notify neighbor nodes in the network of the mutually-agreed upon optimal bandwidth allocation when reallocation is needed, wherein the third communication unit is operably connected to the first communication unit; and

a second processing unit configured to adopt the mutually-agreed upon optimal allocation for the flow when reallocation is needed, wherein the second processing unit is operably connected to the first communication unit.

7. A computer program embodied on computer-readable media, with the computer program configured to allocate bandwidth in an ad hoc, wireless network configured to support at least one guaranteed feasible flow allocation, the computer program comprising:

a first sub-routine for initiating a communication between the first node and a second node in the network that, together, are endpoints of a link, the communication being related to possible bandwidth allocation adjustment of a flow sharing the link;

a second sub-routine for determining, in the first node, a first new bandwidth allocation that approaches a first optimization condition for the flow;

a third sub-routine for communicating with the second node to determine a mutually-agreed upon optimal bandwidth allocation for the flow;

a fourth sub-routine for notifying neighbor nodes in the network of the mutually-agreed upon optimal bandwidth allocation when reallocation is needed; and

a fifth sub-routine for adopting the mutually-agreed upon optimal allocation for the flow when reallocation is needed.

8. A network device configured to allocate bandwidth in an ad hoc, wireless network configured to support at least one guaranteed feasible flow allocation, the device comprising:

initiation means for initiating a communication between the first node and a second node in the network that, together, are endpoints of a link, the communication being related to possible bandwidth allocation adjustment of a flow sharing the link;

determination means for determining, in the first node, a first new bandwidth allocation that approaches a first optimization condition for the flow;

determination means for communicating with the second node to determine a mutually-agreed upon optimal bandwidth allocation for the flow;

notification means for notifying neighbor nodes in the network of the mutually-agreed upon optimal bandwidth allocation when reallocation is needed; and

adoption means for adopting the mutually-agreed upon optimal allocation for the flow when reallocation is needed.