Method for scheduling transmissions in wireless networks

• US 10,462,808 B2
• Filed: 04/13/2017
• Issued: 10/29/2019
• Est. Priority Date: 04/13/2017
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Aijaz, Adnan, Raza, Usman
• Primary Examiner(s): Pasia, Redentor
• Assistant Examiner(s): Fayed, Rasha K
• Application Number:
  US15/487,144
• Publication Number:
  US 20180302911A1
• Time in Patent Office: 929 Days
• Field of Search: 370336, 370350, 370458, 370337, 370431, 370329, 370341, 370348, 370349, 370442, 370443, 370444, 370 44, 370 5, 370255, 370235
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 72/566 of the information or information source or recipient
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Arrangements described herein provide a distributed means of scheduling communications directed towards a sink node from other nodes in a multi-hop wireless network. By listening for other messages assigning schedules to other nodes, each node is able to create its own local record of scheduled transmissions in its area. This allows each node to determine a preliminary schedule. Having said this, the parent node of the node will have additional information regarding the scheduled local transmissions. Accordingly, the node sends the preliminary schedule to its parent node for confirmation that it provides no collisions/conflicts with other scheduled transmissions. As the parent node is involved in the scheduling of each child node, it is better able to determine whether the child nodes are proposing schedules that may conflict with each other.

Claims

1. A method for determining a transmission schedule for one or more transmissions from a first child node to a first parent node in a multi-hop wireless network, wherein each node is a child node to a corresponding parent node, each child node being configured to send one or more messages directed to a sink node via its corresponding parent node and wherein the method comprises the first parent node:

listening for signals indicating scheduled timeslots for transmission between nodes in the network and, if a signal is detected, updating a record of scheduled transmissions;

receiving from the first child node a preliminary schedule specifying a timeslot for transmission of each of the one or more messages to the first parent node;

determining, based on the record of scheduled transmissions, whether the preliminary schedule includes any scheduled transmissions that would conflict with any scheduled transmissions in the record of scheduled transmissions or whether the length of the preliminary schedule can be reduced without conflicting with any other scheduled transmissions in the record of scheduled transmissions;

responsive to a determination that there would be a conflict or that the length of the preliminary schedule can be reduced without conflict;

determining an updated schedule for the first child node by determining a set of scheduled timeslots that minimizes the number of scheduled timeslots without conflicting with any of the scheduled transmissions in the record of scheduled transmissions; and

sending the updated schedule to the first child node to assign the updated schedule to the first child node.

2. The method of claim 1, wherein the method further comprises, responsive to a determination that there would be no conflict and that the length of the preliminary schedule cannot be reduced without conflict, sending to the first child node a signal to confirm the assignment of the preliminary schedule.

3. A method according to claim 1, wherein:

determining the updated schedule comprises scheduling at least one transmission during the same timeslot as another transmission whilst avoiding conflict with any scheduled transmission in the record of scheduled transmissions; and

/or

the method further comprises the first parent node, in response to it overhearing one of its child nodes sending a signal assigning a schedule to another node, sending a message to a corresponding parent node of the first parent node to inform the corresponding parent node of the assigned schedule.

4. The method of claim 1, wherein the method further comprises the first parent node:

prior to receiving from the first child node a preliminary schedule, receiving a build command from a corresponding parent node of the first parent node, the build command instructing the first parent node to build a preliminary schedule and including a scheduling priority assigned to the first parent node relative to any other children of the corresponding parent node; and

in response to the receipt of the build command, forwarding the build command on to all child nodes of the first parent node, the forwarded build command including corresponding scheduling priorities for each child node of the first parent node.

5. A method according to claim 4, further comprising the first parent node:

determining whether all of its child nodes have had their schedules assigned; and

in response to a determination that all of its child nodes have had their schedules assigned;

determining a second preliminary schedule, the second preliminary schedule being for the transmission of messages from the first parent node to a corresponding parent node of the first parent node;

determining a signalling timeslot for sending the second preliminary schedule to the corresponding parent node, the signalling timeslot being determined based on the scheduling priority assigned to the first parent node;

during the signalling timeslot, sending the preliminary schedule to the corresponding parent node; and

receiving from the corresponding parent node either a confirmation that the preliminary schedule is approved, or an alternative schedule assigned by the corresponding parent node.

6. A method according to claim 5, wherein determining the second preliminary schedule comprises determining a set of scheduled timeslots that minimizes the number of scheduled timeslots without conflicting with any of the scheduled transmissions in the record of scheduled transmissions.

20. A wireless node comprising:

a wireless transceiver configured to communicate wirelessly with other nodes in a wireless network;

memory; and

a controller configured to control the wireless node to perform the method of claim 1.

7. A method for determining a transmission schedule for a first node in a multi-hop wireless network, wherein each node is a child node to a corresponding parent node, each child node being configured to send messages directed to a sink node via its corresponding parent node, and wherein the method comprises the first node:

listening for signals indicating scheduling timeslots for transmission between nodes in the network and, if a signal is detected, updating a record of scheduled transmissions;

determining whether to schedule a transmission for each of one or more messages to the corresponding parent node of the first node;

in response to a determination to schedule, determining a preliminary schedule specifying a timeslot for transmission of each of the one or more messages to the corresponding parent node, the preliminary schedule being based on the record of scheduled transmissions;

sending the preliminary schedule to the corresponding parent node for approval; and

setting an assigned schedule based on a response from the corresponding parent node.

8. A method according to claim 7, wherein determining the preliminary schedule comprises determining a set of scheduled timeslots that minimizes the number of scheduled timeslots without conflicting with any of the scheduled transmissions in the record of scheduled transmissions.

9. A method according to claim 7, wherein the response indicates either that the preliminary schedule has been approved by the corresponding parent node or provides a new schedule that is assigned to the first node by the corresponding parent node.

10. A method according to claim 7, wherein the method further comprises the first node, in response to it overhearing a signal, from a corresponding child node of the first node, assigning a schedule to another node, sending a message to the corresponding parent node of the first node to inform the corresponding parent node of the assigned schedule.

11. A method according to claim 7, wherein the first node determines to schedule a transmission for one or more messages to the corresponding parent node of the first node in response to:

a determination that the first node has no child nodes and the receipt of a build command from the corresponding parent node;

or

a determination that the first node has one or more child nodes and that a schedule has been assigned for each of the one or more child nodes of the first node.

12. A method according to claim 7, wherein the method further comprises the first node, in response to a determination to schedule, determining a signalling timeslot for sending the preliminary schedule that avoids conflicts with other scheduled transmissions in the record, wherein the preliminary schedule is sent during the signalling timeslot.

13. A method according to claim 12, wherein the method comprises the first node, in response to a detection that the sending of the preliminary schedule to the corresponding parent node for approval collided with another transmission in the network, resending the preliminary schedule during the next signalling timeslot that is free according to the record of scheduled transmissions.

14. A method according to claim 12, wherein the signalling timeslot for sending the preliminary schedule is determined based on a priority assigned to the first node in a build command received from the corresponding parent node, the priority indicating a scheduling priority relative to other child nodes of the corresponding parent node.

15. A method according to claim 14, wherein, in response to the build command being received and the first node having one or more child nodes, the first node sends a further build command to each of the child nodes.

16. A method according to claim 15 wherein the build command comprises a next available build timeslot the method further comprises the first node determining a build timeslot for sending the build command based on the scheduling priority, the next available build timeslot, such that the build timeslot avoids conflict with any scheduled transmissions in the record, wherein the further build command is sent during the build timeslot.

17. A method according to claim 7, wherein the method comprises the first node determining a number of overprovisioned timeslots based on one or more of a communication link quality with the corresponding parent node, a total number of transmissions scheduled to be sent by the first node and distance to the sink node, the overprovisioned timeslots being for use by the first node for resending failed transmissions.

18. A method according to claim 17, wherein the first node:

in response to a determination that a number of overprovisioned timeslots are not required, sends a request to reduce the number of overprovisioned timeslots to the corresponding parent;

in response to a determination that more overprovisioned timeslots are required, sends a request to increase the number of overprovisioned timeslots to the corresponding parent; and

in response to the receipt from the corresponding parent of an approval to change the number of overprovisioned timeslots, changes the number of overprovisioned timeslots according to the approval.

19. A method according to claim 17, wherein the method further comprises the first node, in response to a determination that a communication link with the corresponding parent node has failed:

sending a request to a neighbouring node to request that the neighbouring node become the new parent node for the first node, the request including the schedule of transmissions previously assigned between the corresponding parent node and the first node; and

setting a new assigned schedule for transmissions to the neighbouring node based on a response from the neighbouring node.