Method and device for routing and scheduling in a multi-hop network

• US 10,448,326 B2
• Filed: 11/18/2016
• Issued: 10/15/2019
• Est. Priority Date: 11/18/2016
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Jin, Yichao, Raza, Usman
• Primary Examiner(s): Abelson, Ronald B
• Application Number:
  US15/355,287
• Publication Number:
  US 20180146489A1
• Time in Patent Office: 1,061 Days
• CPC Class Codes: H04B 7/022 Site diversity; Macro-diversity using two or more spaced independent antennas H04B7/04
• CPC Class Codes: H04L 5/0091 Signaling for the administration of the divided path
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

There is provided a wireless device and a method for managing a wireless device for wireless transmission over a multi-hop wireless network, the wireless device comprising a wireless interface and a controller. A schedule of timeslots for transmitting and timeslots for receiving messages is determined based on which layer of the network the wireless device occupies. A transmission from a first node is received during a scheduled timeslot for receiving messages, the transmission comprising a message. The message is added to a queue of messages. In response to a signal being received via the wireless interface indicating that another node in the network has received the message, the message is removed from the queue of messages. During a scheduled timeslot for transmitting messages, at least one message from the queue of messages is transmitted to nodes in a layer closer to the sink than the wireless device.

Claims

1. A wireless device for wireless transmission over a multi-hop wireless network, the wireless network comprising nodes configured to forward messages towards a sink node, wherein the nodes are grouped in successive layers, each layer representing the distance of the nodes in the layer from the sink node, the wireless device comprising:

a wireless interface for wirelessly communicating with nodes in the network; and

a controller configured to;

determine a schedule of timeslots for transmitting and timeslots for receiving messages based on which layer the wireless device occupies;

receive, via the wireless interface and during a scheduled timeslot for receiving messages, a transmission from a first node, the transmission comprising a message;

during the scheduled timeslot for receiving messages and in response to the receipt of the transmission;

determine whether, during an acknowledgement contention period after receipt of the message, any signals are received via the wireless interface that indicate that an additional node has received the transmission; and

in response to no signals being received, during the acknowledgement contention period, that indicate that an additional node has received the transmission, transmit to the first node, via the wireless interface, an acknowledgement of receipt of the transmission;

add the message to a queue of messages for transmission by the wireless device;

in response to a signal being received via the wireless interface indicating that another node in the network has received the message, remove the message from the queue of messages; and

during a scheduled timeslot for transmitting messages;

cause the wireless interface to transmit at least one message from the queue of messages for transmission to nodes in a layer closer to the sink than the wireless device;

determine whether, during a transmission contention period, a further transmission is received via the wireless interface; and

in response to a further transmission being received during the transmission contention period, inhibit transmission for the duration of the scheduled timeslot for transmitting messages.

2. The wireless device of claim 1 wherein the signal indicating that another node has received the message is a transmission from the other node comprising the message and/or an acknowledgement from the other node that the message has been received.

3. The wireless device of claim 1 wherein the acknowledgement contention period is based on one or more of a random value, the number of messages in the queue, a priority of a message in the queue, or a communication link quality.

4. The wireless device of claim 1 wherein the determination during the acknowledgement contention period and the transmission of the acknowledgement are in response to a determination of whether the device is located an odd or even number of layers away from the sink.

5. A wireless device according to claim 1 wherein the schedule comprises alternating timeslots for transmitting messages and timeslots for receiving messages.

6. A wireless device according to claim 1 wherein the schedule is based on whether the wireless device occupies a layer which is an odd or even number of layers away from the sink.

7. A wireless device according to claim 1 wherein the controller is configured to determine a channel for transmission and/or a channel reception based on which layer the wireless device occupies.

8. The wireless device of claim 7 wherein the controller is configured to set the channel for transmission based on a channel offset (CH_offset) calculated according to:

9. The wireless device of claim 7 wherein the controller is configured to set the channel for reception based on a channel offset (CH_offset) calculated according to:

10. The wireless device of claim 1 wherein the controller is configured to:

store an indication of the message after transmission;

compare a later received message to the indication of the message, to determine whether the later received message is a duplicate of the message;

in response to determining that the later received message is a duplicate of the message, inhibit transmission of the later received message by the wireless device.

11. The wireless device of claim 1 wherein the controller is configured to:

determine whether the wireless device occupies the last layer before the sink;

in response to the wireless device occupying the last layer before the sink, request a last layer schedule from a central scheduler; and

,

in response to receiving the last layer schedule, communicate with the sink according to the last layer schedule.

12. The wireless device of claim 1 wherein the controller is configured to:

in response to the wireless interface detecting no transmissions during two consecutive scheduled timeslots for receiving messages, powering down the wireless interface during the following n scheduled timeslots for receiving messages to conserve energy, wherein n is a positive integer.

13. The wireless device of claim 12 wherein the controller is configured to:

in response to no transmission being received during a scheduled timeslot for receiving messages, increase the number of scheduled timeslots for receiving messages during which the wireless interface is powered down by k, wherein k is a positive integer.

14. The wireless device of claim 12 wherein the controller is configured to, in response to the wireless interface detecting a transmission during a scheduled timeslot for receiving messages, reset the number of scheduled timeslots for receiving messages during which the interface is powered down to a default value.

15. The wireless device of claim 1 wherein the controller is configured to:

in response to the wireless interface detecting no transmissions during a scheduled timeslot for receiving messages, increase a probability of the wireless interface being powered down during a subsequent scheduled timeslot for receiving messages; and

in response to the wireless interface detecting a transmission during a scheduled timeslot for receiving messages, decrease the probability of the wireless interface being powered down during subsequent timeslots receiving messages.

16. The wireless device of claim 1 wherein the controller is configured to, during a scheduled timeslot for transmitting messages, in response to the queue containing no messages, powering down the wireless interface for the duration of the scheduled timeslot for transmitting messages.

17. A multi-hop wireless network comprising a plurality of wireless devices according to claim 1.

18. The wireless device of claim 1 wherein the transmission contention period is based on one or more of a random number, a number of messages in the queue, a priority of the at least one message from the queue, or a communication link quality.

19. A method for managing a wireless device for wireless transmission over a multi-hop wireless network, the wireless network comprising nodes configured to forward messages towards a sink node, wherein the nodes are grouped in successive layers, each layer representing the distance of the nodes in the layer from the sink node, the wireless device comprising a wireless interface for wirelessly communicating with nodes in the network and a controller configured, the method comprising the controller:

determining a schedule of timeslots for transmitting and timeslots for receiving messages based on which layer the wireless device occupies;

receiving, via the wireless interface and during a scheduled timeslot for receiving messages, a transmission from a first node, the transmission comprising a message;

during the scheduled timeslot for receiving messages and in response to the receipt of the transmission;

determining whether, during an acknowledgement contention period after receipt of the message, any signals are received via the wireless interface that indicate that an additional node has received the transmission; and

in response to no signals being received, during the acknowledgement contention period, indicating that an additional node has received the transmission, transmitting to the first node, via the wireless interface, an acknowledgement of receipt of the transmission;

adding the message to a queue of messages for transmission by the wireless device;

in response to a signal being received via the wireless interface indicating that another node in the network has received the message, removing the message from the queue of messages; and

during a scheduled timeslot for transmitting messages;

causing the wireless interface to transmit at least one message from the queue of messages for transmission to nodes in a layer closer to the sink than the wireless device;

determining whether, during a transmission contention period, a further transmission is received via the wireless interface; and

in response to a further transmission being received during the transmission contention period, inhibiting transmission for the duration of the scheduled timeslot for transmitting messages.

20. A computer readable medium comprising instructions that, when executed by a processor, cause the processor to enact the method of claim 19.