Self configuring high throughput medium access control for wireless networks

• US 7,190,686 B1
• Filed: 12/20/2000
• Issued: 03/13/2007
• Est. Priority Date: 12/20/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Beals, Andrew
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): SEFCHECK, GREGORY B
• Application Number:
  US09/742,888
• Time in Patent Office: 2,274 Days
• Field of Search: 370/310, 370/319, 370321-322, 370/326, 370328-329, 370/331, 370336-337, 370345-350, 370/395.4, 370/428, 370/431, 370442-443, 370/458, 370461-463, 370/498, 455/421, 455/432.1, 455433-434, 455/435.1, 455/449, 455/456.1, 455/500, 455/507, 455515-517
• US Class Current: 370/337
• CPC Class Codes: H04B 7/2687 Inter base stations synchronisation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 74/0816 with collision avoidance
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A network architecture that coordinates shared access to a wireless transmission medium while avoiding collisions between simultaneous transmissions even where network nodes cannot hear one another. There is also the capability of readily reconfiguring a wireless network to accommodate new nodes. In one embodiment, there is a hierarchy of master nodes that coordinate wireless transmissions by the other nodes. Since the need for retransmission is minimized, throughput is improved.

Claims

1. In a wireless communications network, a method for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, each of said slave nodes and said submaster node controlled by said master node, wherein at least one of said plurality of slave nodes is able to communicate directly with said master node, said method comprising:

upon admission of a new slave node able to communicate directly with said submaster node and out of range of said master node, recording at said master node a contact path from said master node to said new slave node, wherein said contact path includes said submaster node;

at said master node, generating a schedule of wireless transmission for nodes of said wireless communication network, said schedule precluding collisions between simultaneous transmission by any pair of nodes controlled by said master node including pairs of nodes that do not hear each other'"'"'s transmissions; and

distributing said schedule from said master node to nodes controlled by said master node;

wherein said schedule generated at said master node includes a transmission schedule for at least two levels of hierarchy comprising said submaster node, said plurality of slave nodes, and said new slave node, said transmission schedule configured such that only one only one of said hierarchy is permitted to transmit at a time.

2. The method of claim 1 wherein said schedule comprises time slots allocated to nodes that can be directly contacted by said master node, at least one of said time slots includes a subslot allocated for transmission by a node that cannot be directly contacted by said master node.

3. The method of claim 1 wherein recording said contact path comprises registering a link usable to communicate to said new node to a routing client.

4. The method of claim 1 wherein said schedule comprises time slots allocated to said plurality of slave nodes that can be directly contacted by said master node, said time slots being expandable, wherein generating said schedule comprises determining when to expand a first time slot associated with said nodes that can be directly contacted by said master node to accommodate said new node and expanding said first time slot when it is determined that said first time slot is to be expanded.

5. The method of claim 1 wherein said schedule is for transmission over a single channel.

6. The method of claim 1 wherein said transmission schedule for said new slave node is included within said transmission schedule for said submaster node.

7. In a wireless communication network, a method for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, each of said slave nodes and said submaster node controlled by said master node, wherein at least one of said plurality of slave nodes is able to communicate directly with said master node, said method comprising:

at said submaster node, receiving registration information from a newly contactable slave node, said newly contactable slave node in direct communication with said submaster node and out of range of said master node;

forwarding said registration information from said submaster node to said master node;

at said submaster node, receiving from said master node a registration response;

at said submaster node, receiving from said master node a time allocation for transmission by said newly contactable slave node; and

transmitting said time allocation for transmission by said newly contactable node to said newly contactable slave node;

wherein said newly contactable slave node, said plurality of slave nodes, said submaster node, and said master node define three levels of a transmission control hierarchy and said time allocation is scheduled such that only a single node in said transmission control hierarchy is allowed to transmit at a time.

8. The method of claim 7 further comprising:

at said submaster node, receiving a data transmission during a timeslot defined by said time allocation; and

forwarding said data transmission to said master node.

9. The method of claim 7 wherein said registration information includes a MAC layer address of said newly contactable node and said registration response includes an IP address.

10. In a wireless communication network, a method for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, wherein at least one of said slave nodes is able to communicate directly with said submaster node and is out of range of said master node, said method comprising:

generating a transmission schedule at said master node; and

distributing said transmission schedule from said master node to other nodes of said wireless communication network;

wherein said transmission schedule generated at said master node is divided into a plurality of time slots, each of said plurality of slave nodes within communication range of said master node having at least one of said plurality of time slots allocated thereto for transmission from said slave node to said master node, at least one of said plurality of time slots being allocated for said submaster node and said slave node that is out of range of the master node and able to communicate directly with said submaster node;

wherein said schedule generated at said master node includes a transmission schedule for at least two levels of hierarchy comprising said submaster node and said plurality of slave nodes, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.

11. Apparatus for operating a master node of a wireless communication network comprising a plurality of slave nodes and at least one submaster node in direct communication with said master node, each of said slave nodes and said submaster node controlled by said master node, said apparatus comprising:

a wireless interface that communicates information via a wireless transmission medium and that receives a transmission originating with a new slave node of said wireless communication network; and

a processor that;

records a contact path from said master node to said new node, said contact path including said submaster node;

generates a schedule of transmission via a shared transmission medium by nodes of said wireless communication network, said schedule precluding simultaneous transmission by any pair of nodes controlled by said master node including pairs of nodes that do not hear each other'"'"'s transmissions; and

distributes said schedule to other nodes of said wireless communication network;

wherein said schedule includes a transmission schedule for at least two levels of hierarchy comprising said submaster node, said plurality of slave nodes, and said new node, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.

12. The apparatus of claim 11 wherein said schedule comprises time slots allocated to nodes that can be directly contacted by said master node and at least one of said time slots includes a subslot allocated for transmission by a node that cannot be directly contacted by said master node.

13. The apparatus of claim 11 wherein said processor registers a link usable to communicate to said new node to a routing client.

16. The apparatus of claim 12 wherein said schedule is for transmission over a single channel.

14. In a wireless communication network, apparatus for operating a selected node of a wireless communication network, said wireless communication network comprising a master node, a plurality of slave nodes, and at least one submaster node, each of said slave nodes and said submaster node controlled by said master node, said apparatus comprising:

a wireless interface that communicates information via a wireless transmission medium and that receives a transmission from a new node of said wireless communication network, said new node of said wireless communication network in direct communication with said submaster node and out of range of said master node, said transmission comprising registration information for said new node; and

a processor at said submaster node that;

forwards said registration information to said master node;

receives from said master node a registration response;

receives from said master node a time allocation for transmission by said new node; and

transmits to said new node said time allocation for transmission by said new node;

wherein said new node, said plurality of slave nodes, and said master node define three levels of a transmission control hierarchy and said time allocation is scheduled such that only a single node in said transmission control hierarchy is allowed to transmit at a time.

15. The apparatus of claim 14 wherein said processor:

receives a data transmission during a time slot defined by said time allocation; and

forwards said data transmission to said master node.

17. In a wireless communication network, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, wherein at least one of said slave nodes is able to communicate directly with said submaster node and is out of range of said master node, apparatus for operating a master node of said communication network, said apparatus comprising:

a wireless interface that transmits and receives via a wireless transmission medium; and

a processor that;

generates a transmission schedule for nodes of said communication network; and

distributes said transmission schedule from said master node to other nodes of said wireless communication network;

wherein said transmission schedule generated at said master node is divided into a plurality of time slots, each of said plurality of slave nodes within communication range of said master node having at least one of said plurality of time slots allocated thereto for transmission from said slave node to said master node, at least one of said plurality of time slots being allocated for said submaster node and said slave node that is out of range of the master node and able to communicate directly with said submaster node;

wherein said schedule includes a transmission schedule for at least two levels of hierarchy comprising said submaster node and said plurality of slave nodes, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.

18. In a wireless communication network, a computer program product for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, each of said slave nodes and said submaster node controlled by said master node, wherein at least one of said plurality of slave nodes is able to communicate with said master node, said product comprising:

code that, upon admission of a new slave node in direct communication with said submaster node and out of range of said master node, to said wireless communication network, records at said master node a contact path from said master node to said new slave node, wherein said contact path includes said submaster node;

code that, at said master node, generates a schedule of wireless transmission for nodes of said wireless communication network, said schedule precluding simultaneous transmission by any pair of nodes controlled by said master node including pairs of nodes that do not hear each other'"'"'s transmissions;

code that distributes said schedule from said master node to nodes controlled by said master node; and

a computer readable storage medium that stores the codes;

wherein said schedule generated at said master node includes a transmission schedule for at least two levels of hierarchy comprising said submaster node, said plurality of slave nodes, and said new slave node, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.

19. The product of claim 18 wherein said schedule comprises time slots allocated to nodes that can be directly contacted by said master node and at least one of said slots includes a subslot allocated for transmission by a node that cannot be directly contacted by said master node.

20. The product of claim 18 wherein said code that records said contact path comprises code that registers a link usable to communicate to said new node to a routing client.

21. The computer program product of claim 18 wherein said schedule comprises time slots allocated to nodes that can be directly contacted by said master node and at least one of said time slots comprises a subslot allocated for transmission by one of said slave nodes that cannot be directly contacted by said master node.

22. In a wireless communication network, a computer program product for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node in direct communication with said master node and one of said plurality of slave nodes that is out of range of said master node, said product comprising:

code that generates a transmission schedule at a master node;

code that distributes said transmission schedule from said master node to said plurality of slave nodes; and

a computer-readable storage medium for storing the codes;

wherein said transmission schedule generated at said master node is divided into a plurality of time slots, each of said plurality of slave nodes within communication range of said master node having at least one of said plurality of time slots allocated thereto for transmission from said slave node to said master node, at least one of said plurality of time slots being allocated for said submaster node and said slave node that is out of range of the master node and able to communicate directly with said submaster node;

wherein said schedule includes a transmission schedule for at least two levels of hierarchy comprising said submaster node and said plurality of slave nodes, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.

23. In a wireless communications network, apparatus for coordinating access to a shared transmission medium, said wireless communications network comprising a master node, a plurality of slave nodes, and at least one submaster node, each of said slave nodes and said submaster node controlled by said master node, wherein at least one of said plurality of slave nodes is in direct communication with said master node, said apparatus comprising:

means for recording at said master node a contact path from said master node to a new slave node, wherein said contact path includes said submaster node;

means for, at said master node, generating a schedule of wireless transmission for nodes of said wireless communication network, said schedule precluding simultaneous transmission by any pair of nodes controlled by said master node including pairs of nodes that do not hear each other'"'"'s transmissions; and

means for distributing said schedule from said master node to nodes controlled by said master node;

wherein said schedule generated at said master node includes a transmission schedule for at least two levels of hierarchy comprising said submaster node, said plurality of slave nodes, and said new slave node, said transmission schedule configured such that only one node of said hierarchy is permitted to transmit at a time.