Burst-mode weighted sender scheduling for ad-hoc wireless medium access control protocols

• US 20050018627A1
• Filed: 07/14/2003
• Published: 01/27/2005
• Est. Priority Date: 07/14/2003
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kazi, Sabera, Cardei, Ionut E.
• Granted Patent: US 7,274,676 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of scheduling transmissions in an ad-hoc wireless network is invoked when a frame is received by a medium access control layer of a receiving node. The method includes determining a next node to transmit based on a schedule and a bandwidth allocation. When the next node is different from a node that sent the received frame, the current burst is terminated and the next node is invited to transmit the next burst. When the next node is the node that sent the received frame, the current burst is allowed to continue to be transmitted. Such an approach is suitable for use in applications that require transmissions with a specified quality of service (QOS).

Claims

1. A method of scheduling transmissions in a wireless network, the method comprising:

when a frame is received by a medium access control layer of a receiving node;

determining a next node to transmit based on a schedule;

when the next node is different from a node that sent the received frame, terminating a current burst, wherein the received frame is a part of the current burst, and inviting the next node to transmit a next burst; and

when the next node is the node that sent the received frame, allowing the current burst to continue to be transmitted.

2. The method of claim 1, wherein the wireless network is an ad-hoc wireless network.

3. The method of claim 1, wherein terminating the current burst includes, when the current burst is a burst that is terminated with an acknowledgement frame, transmitting an acknowledgement frame to terminate the current burst.

4. The method of claim 1, wherein terminating the current burst includes terminating the current burst without transmitting an acknowledgement frame.

5. The method of claim 1, further comprising, when the frame is received by the medium access control layer of the receiving node:

when the next node is the receiving node, terminating the current burst, and initiating a transmission by the receiving node.

6. The method of claim 1, wherein inviting the next node to transmit includes transmitting a ready-to-receive control frame.

7. The method of claim 1, wherein determining the next node to transmit based on the schedule includes using a bandwidth allocation in which each of a plurality of nodes is assigned a fraction of a schedule cycle.

8. The method of claim 7, wherein the receiving node suspends transmissions for the remainder of a current schedule cycle when all nodes assigned a fraction in the bandwidth allocation have used up their assigned allocation for the current schedule cycle.

9. The method of claim 8, wherein the schedule specifies a transmit order for the plurality of nodes.

10. The method of claim 9, wherein determining the next node to transmit based on the schedule includes:

when there is additional data to be transmitted in the current burst;

updating a cycle time associated with a current node, wherein the current node is the node that transmitted the received frame and the cycle time is the amount of transmission time allocated to the current node that is remaining in the current schedule cycle;

updating a burst time associated with the current node, wherein the burst time is the amount of time that the current node has used to transmit the current burst;

calculating a next frame time for the next data frame to be transmitted in the current burst, wherein the next frame time is the expected amount of time required to transmit the next data frame in the current burst;

when there is enough remaining cycle time for the current node to transmit the next data frame and when the expected burst time after the transmission of the next data frame is less than a specified maximum burst time, determining that the next node is equal to the current node; and

otherwise, selecting a node having remaining cycle time for the current schedule cycle in accordance with the transmit order specified by the schedule.

11. A receiving node that schedules transmissions in a wireless network, comprising:

a radio frequency subsystem; and

a control subsystem coupled to the radio frequency subsystem;

wherein the control subsystem, when a frame is received by a medium access control layer of the receiving node;

determines a next node to transmit based on a schedule;

when the next node is different from the node that sent the received frame, terminates a current burst, wherein the received frame is a part of the current burst, and invites the next node to transmit a next burst; and

when the next node is the node that sent the received frame, allows the current burst to continue to be transmitted.

12. The node of claim 11, wherein the wireless network is an ad-hoc wireless network.

13. The node of claim 11, wherein the control subsystem terminates the current burst by transmitting an acknowledgement frame to terminate the current burst when the current burst is a burst that uses acknowledgement frames.

14. The node of claim 11, wherein the control subsystem terminates the current burst by omitting transmission of a ready-to-receive control frame to terminate the current burst when the current burst is a burst that does not use acknowledgement frames.

15. The node of claim 11, wherein when the frame is received by the medium access control layer of the receiving node and when the next node is the receiving node, the control subsystem:

terminates the current burst; and

initiates a transmission by the receiving node.

16. The node of claim 11, wherein the control subsystem invites the next node to transmit the next burst by transmitting a ready-to-receive control frame.

17. The node of claim 11, wherein the schedule species a transmit order for the plurality of nodes.

18. The node of claim 11, wherein the control subsystem determines the next node to transmit based on the schedule by using a bandwidth allocation in which each of a plurality of nodes is assigned a fraction of a schedule cycle.

19. The node of claim 18, wherein the control subsystem invites the next node to transmit the next burst by:

when all nodes assigned a fraction in the bandwidth allocation have used up their assigned allocation for the current schedule cycle, deferring transmission; and

when all nodes assigned a fraction in the bandwidth allocation have not used up their assigned allocation for the current schedule cycle, transmitting a ready-to-receive control frame to the next node.

20. The node of claim 18, wherein the control subsystem determines the next node to transmit based on the schedule by:

when there is additional data to be transmitted in the current burst;

updating a cycle time associated with a current node, wherein the current node is the node that transmitted the received frame and the cycle time is the amount of transmission time allocated to the current node that is remaining in the current schedule cycle;

updating a burst time associated with the current node, wherein the burst time is the amount of time that the current node has used to transmit the current burst;

calculating a next frame time for the next data frame to be transmitted in the current burst, wherein the next frame time is the expected amount of time required to transmit the next data frame in the current burst;

when there is enough remaining cycle time for the current node to transmit the next data frame and when the expected burst time after the transmission of the next data frame is less than a specified maximum burst time, determining that the next node is equal to the current node; and

otherwise, selecting a node having remaining cycle time for the current schedule cycle in accordance with the transmit order specified by the schedule.

21. A wireless network, comprising:

a dynamic set of nodes, wherein each of the set of nodes communicates with at least one other node over a wireless communication link;

wherein the set of nodes includes a receiving node that, when a frame is received by a medium access control layer of the receiving node;

determines a next node to transmit based on a schedule;

when the next node is different from a node that sent the received frame, terminates a current burst, wherein the received frame is a part of the current burst, and invites the next node to transmit a next burst; and

when the next node is the node that sent the received frame, allows the current burst to continue to be transmitted.

22. The network of claim 21, wherein at least one node, when the at least one node transmits, selects a frame to transmit from a plurality of queued frames based on a priority assigned to each queued frame.

23. The network of claim 21, wherein at least one node, when the at least one node transmits, drops a time-critical frame that is not expected to be received at a destination node in a specified time period.

24. The network of claim 23, wherein the specified time period is a time-to-live field included in a medium access control header of the time-critical frame.

25. The network of claim 21, wherein at least one node enqueues data frames that are to be transmitted unless the data frame to be transmitted is a time-critical data frame and the data frame is not expected to be received at a destination node within a specified time period.

26. The network of claim 21, wherein each of the set of nodes, when each node wishes to transmit a data frame, waits for a request-to-send lead time before transmitting a request-to-send control frame;

and

wherein the request-to-send lead time used by each node is variable and is a function of whether the data frame is a time-critical function and when that node last successfully transmitted a burst.

27. A method of scheduling nodes to transmit in a network, the method comprising:

when a frame is received at a first node, scheduling nodes to determine a next node to transmit based on a bandwidth allocation and a schedule that specifies a transmit order; and

wherein scheduling nodes to determine the next node to transmit based on the bandwidth allocation and the schedule includes allowing an out-of-order node to transmit out of the transmit order when the receiver is otherwise idle; and

wherein scheduling nodes to determine the next node to transmit based on the bandwidth allocation and the schedule further includes allowing a new node that is not specified in the bandwidth allocation to transmit when the receiver is otherwise idle.

28. A receiving node that schedules transmissions in a network, comprising:

a radio frequency subsystem; and

a control subsystem coupled to the radio frequency subsystem;

wherein the control subsystem, when a frame is received at a first node, schedules nodes to determine a next node to transmit based on a bandwidth allocation and a schedule that specifies a transmit order; and

wherein the control subsystem allows an out-of-order node to transmit out of the transmit order when the receiver is otherwise idle; and

wherein the control subsystem allows a new node that is not specified in the bandwidth allocation to transmit when the receiver is otherwise idle.

29. A receiving node, comprising:

means for receiving and transmitting data frames; and

means for scheduling nodes to determine the next node to transmit based on a bandwidth allocation and a schedule that specifies a transmit order, including;

means for allowing an out-of-order node to transmit out of the transmit order when the receiver is otherwise idle; and

means for allowing a new node that is not specified in the bandwidth allocation to transmit when the receiver is otherwise idle.