Medium access control layer protocol in a distributed environment

• US 7,042,897 B1
• Filed: 04/05/2001
• Issued: 05/09/2006
• Est. Priority Date: 04/05/2001
• Status: Active Grant

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Arcwave, Inc. (Azure Communications, Inc.)
• Inventors: Sivaprakasam, Srinivas, Rath, Kamlesh
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): MOORE JR, MICHAEL J
• Application Number:
  US09/828,339
• Time in Patent Office: 1,860 Days
• Field of Search: 370/254, 370/328, 370/338, 370431-463
• US Class Current: 370/462
• CPC Class Codes: H04L 12/403 with centralised control, e.g. polling
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 72/21 in the uplink direction of a wireless link, i.e. towards the network
• CPC Class Codes: H04W 72/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A method for allocating resources of a shared medium in a large distributed network. The nodes make reservation requests in parallel during a series of reservation time slots. For each slot, one node of a pair transmits a request and the other listens. A node transmits its own requests and the requests of nodes from the request it received. The process repeats until all nodes have transmitted their requests for medium access, wherein one node knows the medium access requests of all the nodes in the network. In this fashion, 1024 nodes can make their requests in ten time slots. The last node may be a master node or may transmit to a master node or base station, which transmits a full or partial grant. Alternatively, the nodes may simultaneously transmit their requests to a master node, which passes the groups requests to a master node nearer the base station.

Claims

1. In a network of nodes sharing a medium, a method of reserving access to said medium, said method comprising the steps of:

a) during a first time interval, a first plurality of nodes in said network each transmitting a request for medium allocation;

b) during said first time interval, a second plurality of nodes in said network each receiving one of said requests from said step a);

c) during a second time interval, a first group of said second plurality of nodes transmitting a request for their own medium allocation plus the medium allocation specified in the received request from said step b);

d) during said second time interval, a second group of said second plurality of nodes each receiving one of said requests from said step c); and

e) in further time intervals, pre-determined nodes transmitting requests and pre-determined nodes receiving requests until all nodes have transmitted their requests.

2. The method of claim 1 wherein said step b) comprises the step of:

b1) a node in said second plurality of nodes receiving said request from a node to which it is paired on a basis of physical location.

3. The method of claim 1 wherein said step b) comprises the step of:

b1) a node in said second plurality of nodes receiving said request from a node to which it is paired on a basis of transmission path characteristics.

4. The method of claim 1 wherein said step b) comprises the step of:

b1) a node of said second plurality listening for said request from a node from said first plurality on a pre-determined frequency.

5. The method of claim 1 wherein said step a) comprises the step of:

a1) a node of said first plurality transmitting said request on a predetermined frequency.

6. The method of claim 1 wherein said step a) comprises the step of:

a1) a node of said first plurality transmitting said request at a predetermined power.

7. The method of claim 1 further comprising the steps of:

f) a new node that is not part of said network determining a received signal strength from said nodes in said network at the location of said new node;

g) said new node transmitting said determinations to a master node; and

h) said master node using said data from said new node to determine which nodes of said network of nodes and said new node transmit during each of said time intervals.

8. The method of claim 7 wherein said step f) comprises the steps of:

f1) said new node listening at a first frequency to determine a signal strength of a node in said network of nodes;

f2) repeating said step f1) for each of said time intervals; and

f3) repeating said step f2) for every other frequency being used, wherein the signal strength at the location of said new node for each of said plurality of nodes in said network is determined.

9. The method of claim 7 further comprising the step of:

i) said master node using said data from said new node to determine a power and frequency at which each of said plurality of nodes transmits when making a request for medium allocation.

10. The method of claim 1 further comprising the steps of:

f) a node granting said requests; and

g) said node transmitting an indicator of the resources to which each node of said network has been allocated.

11. The method of claim 1 further comprising the steps of:

f) a node transmitting a scaling factor; and

g) a node in said network scaling its request for medium allocation by said scaling factor.

12. A method of reserving medium access for a network comprising a plurality of nodes, said method comprising the steps of:

a) during a first time interval, pre-determined nodes each transmitting a request for resource allocation;

b) during said first time interval, pre-determined nodes each receiving one of said requests transmitted from said step a);

c) during a second and later time intervals, pre-determined nodes of said nodes which received requests in the previous time interval transmitting a request for its own resource allocation plus the resource allocation specified in the received request from a previous time interval;

d) during said second and later time intervals, pre-determined nodes of said nodes which received requests in the previous time interval receiving requests from nodes transmitting in this time interval;

e) repeating said step c) and said step d) until there are two nodes yet to transmit; and

f) one of said two nodes from said step e) transmitting its requests to the other node, wherein the last receiving node knows the resource allocation requests of all nodes of said network.

13. The method of claim 12 further comprising the steps of:

g) dividing a resource space comprising frequency and time division into packets;

h) assigning an order to each node in said network;

i) assigning an order to said resource packets; and

j) assigning the resource packets to the nodes in corresponding order.

14. The method of claim 13 further comprising the step of:

k) a node listening to the requests of other nodes to determine which of said resource packets will be allocated to it.

15. The method of claim 14 further comprising the steps of:

l) a master node transmitting a scaling factor; and

m) a node in said network scaling its request for resources by said scaling factor.

16. The method of claim 13 further comprising the steps of:

k) a master node granting said requests; and

l) said master node transmitting information describing the resources packets to which each node has been allocated.

17. The method of claim 12 wherein said step c) comprises the step of:

c1) increasing a coding gain with each successive time interval.

18. The method of claim 12 wherein said step c) comprises the step of:

c1) said nodes transmitting with increasing power levels with each successive time interval.

19. The method of claim 12 wherein said step d) comprises the step of:

d1) more than one of said nodes in said network receiving said requests for said resource allocation.