Transmission-scheduling coordination among collocated internet radios

• US 6,928,061 B1
• Filed: 10/31/2000
• Issued: 08/09/2005
• Est. Priority Date: 09/06/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Mobile Phones UK Limited (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Garcia-Luna-Aceves, Jose J., Fullmer, Chane L.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Philpott, Justin M.
• Application Number:
  US09/703,075
• Time in Patent Office: 1,743 Days
• Field of Search: 370/329, 370/336, 370/337, 370/347, 370/350, 370/395.4, 370/458, 370/236, 370/445, 370/238, 370/256, 370/345, 370/352, 370/355
• US Class Current: 370/329
• CPC Class Codes: H04L 1/16 in which the return channel carries supervisory signals, e.g. repetition request signals
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 84/22 with access to wired networks
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals

Abstract

A method for collocated nodes communicating over a first interface to agree on a conflict-free transmission schedule among themselves, which they can then use to collaborate with neighbors accessed through a second interface, for example through wireless links in order to obtain collision-free transfers of unicast, multicast and broadcast packets over wireless channels, and channel access delay guarantees. The collocated nodes behave as a single virtual node for the purpose of establishing a consistent transmission schedule throughout the nodes of a multihop wireless network.

Claims

1. A method, comprising:

scheduling transmissions in a network including a plurality of collocated nodes and a plurality of non-collocated nodes, wherein the plurality of collocated nodes communicate between one another over a first interface and the plurality of non-collocated nodes communicate with the plurality of collocated nodes over a second interface;

exchanging first scheduling information between the plurality of collocated nodes over the first interface, wherein each collocated node maintains a schedule entry for each neighboring collocated node, the schedule entry specifying a neighboring collocated node identifier and a timer, the timer determines a remaining time that the neighboring collocated node and its schedule information can be assumed to be valid, a value of the timer being updated with a reception of a schedule packet from a corresponding neighboring collocated node and the value of the timer being reduced each of a predefined unit of time, wherein the collocated node determines that the corresponding neighboring collocated node is not reachable when the value of the timer is equal to zero;

exchanging second scheduling information associated with transmissions between the plurality of collocated nodes and each of the plurality of non-collocated nodes on the second interface; and

determining, based at least in part on the first scheduling information, a schedule for the plurality of collocated nodes for transmissions between the plurality of collocated nodes and each of the plurality of non-collocated nodes on the second interface;

wherein the schedule includes information on when and in what order the transmissions may occur in the network, and

wherein the exchanging of scheduling information between the plurality of collocated nodes over the first interface comprises sending a schedule packet from a first collocated node to a second collocated node of the plurality of collocated nodes, the schedule packet including an indication of all known nodes in the two-hop neighborhood of the first node, incoming and outgoing collision-free links of the first node that are already scheduled, time slots and data channels in which new links with the first node can be reserved, and time slots and data channels on which the first node will be listening while not active in scheduled links.

2. The method of claim 1, further comprising:

exchanging scheduling information between the plurality of collocated nodes over the first interface during a time frame while the plurality of non-collocated nodes send data packets to, and receive data packets from, one or more of the plurality of collocated nodes over the second interface.

3. The method of claim 2, wherein the exchanging of scheduling information between the plurality of collocated nodes over the first interface occurs prior to the determining the schedule for the plurality of collocated nodes for transmissions between the plurality of collocated nodes and each of the plurality of non-collocated nodes on the second interface.

4. The method of claim 1, wherein communications over the second interface are performed using a plurality of time frames, each comprising a control and data portion, wherein the scheduling information comprises a first scheduling information, wherein the exchanging of scheduling information comprises exchanging the first scheduling information over the first interface during the data portion of a first time frame, and wherein the method further comprises the exchanging of a second scheduling information between the plurality of non-collocated nodes and each of the plurality of collocated nodes over the second interface during the control portion of the first time frame, the second scheduling information associated with transmissions between the plurality of collocated and each of the plurality of non-collocated nodes.

5. The method of claim 1, wherein the exchanging of scheduling information between the plurality of collocated nodes over the first interface comprises:

sending a schedule packet from a first collocated node of the plurality of collocated nodes to a second collocated node of the plurality of collocated nodes over the first interface; and

sending, in response to receiving the schedule packet, an acknowledgement packet from the second collocated node to the first collocated node over the first interface.

6. The method of claim 5, wherein the exchanging of scheduling information between the plurality of collocated nodes over the first interface further comprises:

setting, in the second collocated node, a sequence number of a last received schedule packet to a value of a sequence number of the schedule packet received from the first collocated node;

sending a hello packet from the first collocated node to the second collocated node, the hello packet identifying the first collocated node and a sequence number of a last sent schedule packet from the first collocated node;

determining if the sequence number of the last sent schedule packet indicates that the sequence number of the last sent schedule packet is less than the sequence number of the last received schedule packet;

and, in response to a positive determination;

transmitting a hello-response from the second collocated node to the first collocated node, the hello-response including the sequence number for the last received schedule packet.

7. The method of claim 6, wherein the hello packet comprises a first hello packet and the exchanging of scheduling information between the plurality of collocated nodes over the first interface further comprises:

receiving the hello-response at the first collocated node;

resetting the sequence number of the last sent schedule packet to the larger of the sequence number of the last sent schedule packet or 1 plus the sequence number of the last received schedule packet received in the hello-response; and

sending a second hello packet from the first collocated node to the second collocated node, the hello packet identifying the first collocated node and the sequence number of the last sent schedule packet as reset.

8. The method of claim 5, wherein the exchanging of scheduling information between the plurality of collocated nodes over the first interface further comprises:

setting, in the second collocated node, a sequence number of a last received schedule packet to a value of a sequence number of the schedule packet received from the first collocated node;

sending a hello packet from the first collocated node to a second collocated node, the hello packet identifying the first collocated node and a sequence number of a last sent schedule packet from the first collocated node;

determining if the sequence number of the last sent schedule packet indicates that the sequence number of the last sent schedule packet is less than the sequence number of the last received schedule packet;

and, in response to a negative determination, setting the sequence number of the last received schedule packet to the sequence number of the last sent schedule packet.

9. The method of claim 1, wherein the first interface comprises a wired link and the second interface comprises a wireless link.

10. The method of claim 9, wherein the wireless link comprises a plurality of RF channels and the plurality of collocated nodes communicates with at least two of the plurality of non-collocated nodes simultaneously over orthogonal channels of the plurality of RF channels.

11. The method of claim 1, wherein the schedule for the plurality of collocated nodes for transmissions between the plurality of collocated nodes is a conflict-free transmission schedule.

12. A communications network, the network comprising:

a plurality of non-collocated nodes, each of the plurality of non-collocated nodes capable of receiving and transmitting transmissions on a first interface; and

a plurality of collocated nodes, the plurality of collocated nodes each capable of communicating between one another over a second interface, each of the plurality of collocated nodes further capable of receiving and transmitting transmissions to and from the plurality of non-collocated nodes on the first interface, wherein the plurality of collocated nodes exchanges scheduling information with one another over the second interface, the scheduling information associated with transmissions between the plurality of collocated nodes and each of the plurality of non-collocated nodes on the first interface, and determines, based at least in part on the scheduling information, a schedule for the plurality of collocated nodes for transmission between the plurality of collocated nodes and each of the plurality of non-collocated nodes on the first interface;

wherein each collocated node maintains a schedule entry for each neighboring collocated node, the schedule entry specifying a neighboring collocated node identifier and a timer, the timer determines a remaining time that the neighboring collocated node and its schedule information can be assumed to be valid, a value of the timer being updated with a reception of a schedule packet from a corresponding neighboring collocated node and the value of the timer being reduced each of a predefined unit of time, wherein the collocated node determines that the corresponding neighboring collocated node is not reachable when the value of the timer is equal to zero,

and wherein the plurality of collocated nodes exchanges scheduling information comprising a schedule packet, the schedule packet including an indication of all known nodes in the two-hop neighborhood of a sending collocated node, incoming and outgoing collision-free links of the sending collocated node that are already scheduled, time slots and data channels in which new links with the sending collocated node can be reserved, and time slots and data channels on which the collocated node will be listening while not active in scheduled links.

13. The network of claim 12, wherein the plurality of collocated nodes exchanges the scheduling information over the second interface during a time frame while the plurality of non-collocated nodes send data packets to, and receive data packets from, each of the plurality of collocated nodes over the first interface.

14. The network of claim 13, wherein the time frame comprises a first time frame and wherein the schedule determined by the plurality of collocated nodes comprises a schedule for the plurality of collocated nodes for transmissions between the plurality of non-collocated nodes on the first interface, wherein the transmissions occur during a second time frame subsequent to the first time frame.

15. The network of claim 12, wherein communications over the first interface are performed using a plurality of time frames, each comprising a control and data portion, wherein the scheduling information comprises a first scheduling information, wherein the plurality of collocated nodes exchanges the first scheduling information over the second interface during the data portion of a time frame, and wherein the plurality of collocated nodes further exchanges a second scheduling information with each of the plurality of non-collocated nodes over the first interface during the control portion of the time frame, the second scheduling information associated with transmissions between the plurality of collocated nodes and each of the plurality of non-collocated nodes.

16. The network of claim 12, wherein the first interface comprises a wireless link and the second interface comprises a wired link.

17. An apparatus in a communications network including a plurality of non-collocated routers capable of communicating over a first interface, the apparatus comprising:

at least two collocated routers, the at least two collocated routers capable of communications between one another over a second interface, and the at least two collocated routers capable of communications with each of the plurality of non-collocated routers over the first interface, wherein the at least two routers exchange scheduling information over the second interface, the scheduling information associated with transmissions between the at least two collocated routers and the plurality of non-collocated routers on the first interface, and wherein the at least two collocated routers determine, based at least in part on the scheduling information, a schedule for transmission between the at least two collocated routers and each of the plurality of non-collocated routers on the first interface,

wherein each collocated router maintains a schedule entry for each neighboring collocated router, the schedule entry specifying a neighboring collocated router identifier and a timer, the timer determines a remaining time that the neighboring collocated router and its schedule information can be assumed to be valid, a value of the timer being updated with a reception of a schedule packet from a corresponding neighboring collocated router and the value of the timer being reduced each of a predefined unit of time, wherein the collocated router determines that the corresponding neighboring collocated router is not reachable when the value of the timer is equal to zero, and

wherein the plurality of collocated nodes exchanges scheduling information comprising a schedule packet, the schedule packet including an indication of all known nodes in the two-hop neighborhood of a sending collocated node, incoming and outgoing collision-free links of the sending collocated node that are already scheduled, time slots and data channels in which new links with the sending collocated node can be reserved, and time slots and data channels on which the collocated node will be listening while not active in scheduled links.

18. The apparatus of claim 17, wherein the first interface comprises a wireless link and the second interface comprises a wired link.

19. The apparatus of claim 18, wherein the at least two collocated routers exchange the scheduling information over the wired link at substantially the same time as the at least two collocated routers exchange data with the plurality of non-collocated nodes over the wireless link.

20. The apparatus of claim 17, wherein the at least two collocated routers and the plurality of non-collocated routers communicating over the first interface use a plurality of time frames, each of the plurality of time frames including a control portion and a data portion, and wherein the at least two collocated routers exchange the scheduling information over the second interface at approximately the same time that one or more frames associated with the data portion of the plurality of frames are transmitted on the first interface.

21. The apparatus of claim 20, wherein the schedule for transmission between the at least two collocated routers and each of the plurality of non-collocated routers on the first interface occurs in a second frame that occurs subsequent to a first frame in which the exchange of schedule information on the second interface occurs.