Scheduling techniques for receiver directed broadcast applications

• US 6,781,967 B1
• Filed: 08/29/2000
• Issued: 08/24/2004
• Est. Priority Date: 08/29/2000
• Status: Expired due to Term

• 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: Young, C. David
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LEE, TIMOTHY L
• Application Number:
  US09/650,332
• Time in Patent Office: 1,456 Days
• Field of Search: 370/312, 370/314, 370/336, 370/347, 370/348, 370/390, 370/432, 370/437, 370/442, 370/443, 370/458
• US Class Current: 370/312
• CPC Class Codes: H04H 20/42 Arrangements for resource management
• CPC Class Codes: H04H 60/06 Arrangements for scheduling broadcast services or broadcast-related services
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

Scheduling techniques for communication applications using receiver directed broadcast schemes are disclosed. The invention includes techniques for the implicit reservation of receive slots and techniques for the optimization of receiver directed broadcast schedules. The implicit reservation scheme includes the mechanics of implicit reservation. Implicitly reserved slots can be reclaimed by their owners. Further, simultaneous implicit reservations can be identified and resolved. Procedures are also provided for determining the number of channels and slots required to optimize a receiver directed broadcast schedule for a neighborhood of a given number of nodes.

Claims

1. A method for optimizing a communication schedule in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising the steps of:

establishing a receiver directed broadcast communication schedule having a plurality of communication slots;

associating a communication link between at least two nodes with at least one communication slot of the communication schedule; and

optimizing the communication schedule to prevent collisions by determining the number of communication slots required to maximize the number of simultaneous transmissions in the network, wherein said optimizing step comprises determining how many communication slots are required for a given number of communication channels by solving S=N(N−

1)/C, where C represents the number of channels, S represents the number of communication slots being determined, and N represents the number of nodes in the neighborhood of the receiving nodes.

2. The method of claim 1, wherein said optimizing step further comprises constructing the receiver directed broadcast communication schedule such that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against said node'"'"'s needs to use a communication slot associated with another node.

3. The method of claim 1, wherein said optimizing step results in a nesting of communication schedules such that a communication schedule for a smaller number of nodes is imbedded within a communication schedule for a larger number of nodes.

4. A communication apparatus capable of participating in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising:

a wireless communication component;

a memory component, storing a receiver directed broadcast communication schedule of a plurality of communication slots and also storing data associating at least one communication slot of the plurality of communication slots with a communication link between at least two network nodes, said memory component also storing instructions for dynamically managing the receiver directed broadcast communication schedule and for optimizing the receiver directed broadcast communication schedule to prevent collisions by determining how many communication slots are required to maximize the number of simultaneous network transmissions; and

a processor component, coupled with said wireless communication component and with said memory component, capable of executing the instructions for dynamically managing the receiver directed broadcast communication schedule and capable of executing the instructions for optimizing the receiver directed broadcast communication schedule, wherein said memory component stores instructions for optimizing that determine how many communication slots are required for a system having a given number of communication channels by solving S=N(N−

1)/C, where C represents the number of communications channels, S represents the number of communication slots being determined, and N represents the number of neighboring nodes.

5. The communication apparatus according to claim 4, wherein said memory component stores instructions for optimizing that ensure that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against its needs to use a communication slot with which it has not been associated.

6. The communication apparatus according to claim 4, wherein said memory component stores instructions for optimizing such that a receiver directed broadcast communication schedule for a network with a smaller number of nodes is imbedded within a receiver directed broadcast communication schedule with a larger number of nodes.

7. A method for optimizing a communication schedule in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising the steps of:

establishing a receiver directed broadcast communication schedule having a plurality of communication slots;

associating a communication link between at least two nodes with at least one communication slot of the communication schedule; and

optimizing the communication schedule to prevent collisions by determining the number of communication slots required to maximize the number of simultaneous transmissions in the network, wherein said optimizing step comprises determining how many communication slots are required for a given number of communication channels by solving C=N/2, and calculating how many communication slots are required by solving S=2(N−

1), where C represents the number of communication channels being determined, S represents the number of communication slots being determined, and N represents the number of nodes in the neighborhood of the receiving nodes.

8. The method of claim 7, wherein said optimizing step further comprises constructing the receiver directed broadcast communication schedule such that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against its needs to use a communication slot associated with another node.

9. The method of claim 7, wherein said optimizing step results in a nesting of communication schedules such that a communication schedule for a smaller number of nodes is imbedded within a communication schedule for a larger number of nodes.

10. A method for optimizing a communication schedule in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising the steps of:

establishing a receiver directed broadcast communication schedule having a plurality of communication slots;

associating a communication link between at least two nodes with at least one communication slot of the communication schedule; and

optimizing the communication schedule to prevent collisions by determining the number of communication slots required to maximize the number of simultaneous transmissions in the network, wherein said optimizing step results in a nesting of communication schedules such that a communication schedule for a smaller number of nodes is imbedded within a communication schedule for a larger number of nodes.

11. The method of claim 10, wherein said optimizing step further comprises constructing the receiver directed broadcast communication schedule such that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against its needs to use a communication slot associated with another node.

12. The method of claim 10, wherein said optimizing step comprises determining how many communication slots are required for a given number of communication channels.

13. The method of claim 12, wherein said optimizing step solves S=N(N−

1)/C to determine how many communication slots are required, where C represents the number of channels, S represents the number of communication slots being determined, and N represents the number of nodes in the neighborhood of the receiving nodes.

14. The method of claim 12, wherein said optimizing step comprises the step of calculating how many communication channels are required by solving C=N/2, and calculating how many communication slots are required by solving S=2(N−

1), where C represents the number of communication channels being determined, S represents the number of communication slots being determined, and N represents the number of nodes in the neighborhood of the receiving nodes.

15. A communication apparatus capable of participating in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising:

a wireless communication component;

a memory component, storing a receiver directed broadcast communication schedule of a plurality of communication slots and also storing data associating at least one communication slot of the plurality of communication slots with a communication link between at least two network nodes, said memory component also storing instructions for dynamically managing the receiver directed broadcast communication schedule and for optimizing the receiver directed broadcast communication schedule to prevent collisions by determining how many communication slots are required to maximize the number of simultaneous network transmissions; and

a processor component, coupled with said wireless communication component and with said memory component, capable of executing the instructions for dynamically managing the receiver directed broadcast communication schedule and capable of executing the instructions for optimizing the receiver directed broadcast communication schedule, wherein said memory component stores instructions for optimizing that determine how many communication slots are required for a system having a given number of communication channels according to C=N/2 and S=2(N−

1), where C represents the number of channels being determined, S represents the number of communication slots being determined, and N represents the number of neighboring nodes.

16. The communication apparatus according to claim 15, wherein said memory component stores instructions for optimizing that ensure that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against said node'"'"'s needs to use a communication slot with which it has not been associated.

17. The communication apparatus according to claim 15, wherein said memory component stores instructions for optimizing such that a receiver directed broadcast communication schedule for a network with a smaller number of nodes is imbedded within a receiver directed broadcast communication schedule with a larger number of nodes.

18. A communication apparatus capable of participating in a network having nodes communicating via scheduled communication slots on a time multiplex basis, comprising:

a wireless communication component;

a memory component, storing a receiver directed broadcast communication schedule of a plurality of communication slots and also storing data associating at least one communication slot of the plurality of communication slots with a communication link between at least two network nodes, said memory component also storing instructions for dynamically managing the receiver directed broadcast communication schedule and for optimizing the receiver directed broadcast communication schedule to prevent collisions by determining how many communication slots are required to maximize the number of simultaneous network transmissions; and

a processor component, coupled with said wireless communication component and with said memory component, capable of executing the instructions for dynamically managing the receiver directed broadcast communication schedule and capable of executing the instructions for optimizing the receiver directed broadcast communication schedule;

wherein said memory component stores instructions for optimizing such that a receiver directed broadcast communication schedule for a network with a smaller number of nodes is imbedded within a receiver directed broadcast communication schedule with a larger number of nodes.

19. The communication apparatus according to claim 18, wherein said memory component stores instructions for optimizing that ensure that a node'"'"'s needs to communicate with nodes in its own neighborhood are balanced against said node'"'"'s needs to use a communication slot with which it has not been associated.

20. The communication apparatus according to claim 18, wherein said memory component stores instructions for optimizing that determine how many communication slots are required for a system having a given number of communication channels.

21. The communication apparatus according to claim 20, wherein said memory component stores instructions for optimizing that determine how many communication slots are required by solving S=N(N−

1)/C, where C represents the number of communications channels, S represents the number of communication slots being determined, and N represents the number of neighboring nodes.

22. The communication apparatus according to claim 20, wherein said memory component stores instructions for optimizing that calculate how many communication channels are required according to C=N/2, and that calculate how many communication slots are required according to S=2(N−

1), where C represents the number of channels being determined, S represents the number of communication slots being determined, and N represents the number of neighboring nodes.