On-demand broadcast protocol

• US 7,382,799 B1
• Filed: 05/18/2004
• Issued: 06/03/2008
• Est. Priority Date: 05/18/2004
• Status: Active Grant

• Current Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Original Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Inventors: Stevens, James A., Young, C. David
• Primary Examiner(s): Backer; Firmin
• Assistant Examiner(s): NGO, NGUYEN HOANG
• Application Number:
  US10/847,786
• Time in Patent Office: 1,477 Days
• Field of Search: 370/229, 370/230, 370/280, 370/294, 370/352, 370/376, 370/468, 370/431, 370/437, 370/458, 370/459
• US Class Current: 370/458
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling

Abstract

A method of communicating over a network of nodes using a plurality of time slots is disclosed. According to the method, at least one of the plurality of time slots are assigned to a first node. The first node communicates, to neighboring nodes within one hop of the first node, which time slots assigned to the first node are scheduled to be used by the first node. Each neighboring node determines whether it has a need to use more time slots than it has been assigned. Each neighboring node communicates its respective need to the first node. At least one of the neighboring nodes is permitted to use one of the unscheduled time slots.

Claims

1. A method of communicating over a network of nodes using a plurality of time slots, wherein nodes are permitted to simultaneously use a time slot only when the nodes are at least three hops apart, the method comprising:

assigning at least one of the plurality of time slots to a first node;

the first node communicating, to neighboring nodes within one hop of the first node, which time slots assigned to the first node are scheduled to be used by the first node;

each neighboring node determining whether said each neighboring node has a need to use more time slots than have been assigned to said each neighboring node;

each neighboring node communicating its respective need to the first node; and

permitting at least one of the neighboring nodes to use a time slot assigned to the first node and not scheduled to be used by the first node;

wherein the permitting step further includes permitting at least one of the neighboring nodes to use the time slot assigned to the first node, and not scheduled to be used by the first node, only when said at least one of the neighboring nodes has not indicated a preference to obtain slots from a node other than the first node.

2. The method of claim 1, wherein the step of each neighboring node communicating its respective need includes transmitting, to nodes within one hop of each said neighboring node, a need indicator expressing relative broadcast need of the neighboring node, and wherein the first node permits at least one of the neighboring nodes, having a need indicator higher than a predetermined level, to use the time slot assigned to the first node and not scheduled to be used by the first node.

3. The method of claim 2, wherein the need indicator for a neighboring node is increased when said neighboring node has a predefined broadcasting priority relative to other nodes in the network.

4. The method of claim 2, wherein the need indicator for a neighboring node is increased when said neighboring node has a time-critical message to transmit.

5. The method of claim 2, wherein the first node determines which neighboring node is to use the time slot by comparing need indicators associated with each neighboring node.

6. The method of claim 1, wherein the first node yields up the time slot for contention among conflict-free neighboring nodes which have no nodes within two hops that are scheduled to use the time slot, and further wherein each of the conflict-free neighboring nodes waits a random amount of time before being permitted to use the time slot.

7. The method of claim 6, wherein the random amount of time is selected from a randomization interval, and further wherein the randomization interval increases as a number of conflict-free neighboring nodes increases.

8. The method of claim 1, wherein the permitting step includes permitting at least one of the neighboring nodes to use the time slot in successive time frames.

9. The method of claim 8, wherein the permitting step includes permitting at least one of the neighboring nodes to use the time slot in successive time frames until no longer needed by the said at least one of the neighboring nodes.

10. The method of claim 1, further comprising:

each neighboring node determining whether no node within two hops of said each neighboring node is scheduled to use said time slot;

wherein the one of the neighboring nodes permitted to use said time slot is at least three hops from any other node in the network scheduled to use the time slot.

11. A method of managing communication resources in a network of nodes, wherein a first node has a communication time slot allocated thereto, the method comprising:

the first node communicating, to a neighboring node within one hop of the first node, whether the first node intends to use the communication time slot;

the neighboring node indicating, to nodes within one hop of said neighboring node, whether the neighboring node needs to use more communication time slots than have been allocated to said neighboring node; and

the first node permitting the neighboring node to use the communication time slot when the first node is not scheduled to use the communication time slot;

wherein the permitting step further includes permitting the neighboring node to use the time slot assigned to the first node, and not scheduled to be used by the first node, only when the neighboring node has not indicated a preference to obtain slots from a node other than the first node.

12. The method of claim 11, wherein the permitting step further includes permitting the neighboring node to use the communication time slot when the first node is not scheduled to use the communication time slot and when the communication time slot is not scheduled to be used by any node within two hops of the neighboring node.

13. The method of claim 11, wherein the neighboring node is a first neighboring node, and further including a second neighboring node within one hop of the first node, and further wherein the indicating step includes:

each of the first and second neighboring nodes transmitting a numeric value expressing a relative need of said each of the first and second neighboring nodes to use the communication time slot;

wherein the first node permits one of the first and second neighboring nodes having a numeric value with a value higher than a predetermined level, to use the communication time slot when the first node is not scheduled to use the communication time slot.

14. The method of claim 13, wherein the numeric value associated with the first neighboring node is increased when the first neighboring node has a predefined broadcasting priority relative to other nodes in the network.

15. The method of claim 13, wherein the numeric value associated with the first neighboring node is increased when the first neighboring node has a message to transmit having a relative size greater than messages other nodes in the network are transmitting.

16. The method of claim 11, wherein the neighboring node is one of a plurality of neighboring nodes, and wherein the first node yields up the communication time slot for contention among conflict-free neighboring nodes which have no nodes within two hops that are scheduled to use the communication time slot and which have a need to use the communication time slot, and further wherein each of the conflict-free neighboring nodes waits a random amount of time before being permitted to use the communication time slot.