Systems, methods and apparatus for detecting time slot interference and recovering from time slot interference in an ad hoc wireless communication network
View Patent ↗In a network comprising a source, a destination, and intermediate nodes along a route between the source and the destination, techniques are provided for allocating one or more time slots to transmit a particular data stream along the route based on the QoS requirements to transmit the particular data stream. In one implementation, a Scout Request message (SRM) is sent from the source to the destination to allocate time slots along the route to transmit a particular data stream to the destination. The SRM can include QoS requirements to transmit the particular data stream. Each intermediate node along the route can allocate one or more time slots to transmit the particular data stream based on the QoS requirements needed to transmit the particular data stream along the route.
1. In an ad hoc network comprising a first node which is assigned a particular time slot for transmission of a first data stream and a second node which has been assigned the particular time slot for transmission of a second data stream, a method comprising:
detecting time slot interference on the particular time slot at either one or more of:
a receiver node that receives on the particular time slot when the transmission of the first data stream on the particular time slot interferes with the transmission of the second data stream on the particular time slot;
a transmitter node that transmits on the particular time slot when the transmission of the first data stream on the particular time slot interferes with the transmission of the second data stream on the particular time slot; and
recovering from time slot interference on the particular time slot, wherein recovering from time slot interference on the particular time slot, comprises:
marking the status of the particular time slot as interfered at any of the nodes which detect time slot interference upon detecting time slot interference such that the particular time slot is not used for a time period after being designated as interfered and is designated as being free after the time period; and
transmitting, from either the transmitter node or the receiver node which detect time slot interference on the particular time slot, either:
a broadcast Slot Interference message to all the neighbor nodes upon detecting time slot interference on the particular time slot; or
Slot Interference messages upon detecting time slot interference on the particular time slot, wherein the Slot Interference messages comprise: a unicast reverse Slot Interference message transmitted towards source node, and a unicast forward Slot Interference message transmitted towards destination node.
2. A method according to claim 1 , wherein each of the Slot Interference messages comprise:
at least one interfered slot number when the transmission of the first data stream on the particular time slot interferes with the transmission of the second data stream on the particular time slot;
a stream number; and
a flag indicating whether the Slot Interference message is a forward Slot Interference message or reverse Slot Interference message.
3. A method according to claim 1 , further comprising:
performing a full interference recovery process by:
clearing the time slots being used at each of the nodes along the route between the source node and the destination node by marking each of the currently allocated time slots as being free at each of the nodes which receive at least one of the unicast reverse and forward Slot Interference messages; and
re-allocating new time slots at each of the nodes along the route between the source node and the destination node.
4. A method according to claim 3 , wherein re-allocating new time slots comprises:
transmitting, from the source node, a Scout Request message to start a new time slot allocation process; and
re-scheduling non-interfered time slots to either the first node or the second node.
5. A method according to claim 1 , further comprising:
performing a local interference recovery process by:
clearing the particular time slots being interfered with by marking, at each of the neighboring nodes which receive the broadcast Slot Interference message, each of the particular time slots being interfered with as being free; and
re-allocating new time slots for each of the currently interfered time slots.
6. A method according to claim 5 , wherein re-allocating new time slots comprises:
transmitting, from the node which detected interference, a Scout Request message to start a new time slot allocation process, wherein the Scout Request message has a local recovery flag enabled; and
re-scheduling new time slots which are interference free to either the first node or the second node.
7. A method of operation of a node to detect time slot interference on a particular time slot within an ad hoc network comprising:
maintaining a Local Slot Allocation Table in a memory of the node, wherein the local slot allocation table comprises time slot allocation, previous hop node information, and next hop node information for receiving and transmitting one or more data streams;
receiving a Hello message from a neighbor node, wherein the Hello message includes a Time Slot Utilization Map of the neighbor node;
detecting interference on the particular time slot when the particular time slot is marked for transmission in the Time Slot Utilization Map of the received Hello message and is marked for transmission in the Local Slot Allocation Table;
prior to the detecting interference operation:
assigning the particular time slot for transmission of a first data stream by the node; and assigning the particular time slot for transmission of a second data stream by the neighbor node;
detecting time slot interference on the particular time slot comprises:
detecting collisions on the particular time slot when the transmission of the first data stream on the particular time slot interferes with the transmission of the second data stream on the particular time slot;
counting a number of consecutive collisions on the particular time slot, wherein the count is reset upon successful transmission on the particular time slot; and
determining that the number of consecutive collisions on the particular time slot exceeds a predetermined number.
8. The method of operation of a node as claimed in claim 7 , wherein detecting time slot interference on the particular time slot further comprises:
determining a packet completion rate for a predetermined number of packets sent;
measuring an average packet completion rate for the predetermined number of packets sent on the particular time slot; and
determining that the average packet completion rate is less than a threshold.
9. The method of operation of a node as claimed in claim 7 , wherein the Time Slot Utilization Map of the received Hello message indicates that more than one neighbor node of the node is receiving on the particular time slot.
10. The method of operation of a node as claimed in claim 7 , comprising:
checking a list of intended destination nodes in the Local Slot Allocation Table for a data stream being multicast by the node; and
determining that the neighbor node is not on the list of intended destination nodes for the multicast data stream.
11. The method of operation of a node as claimed in claim 7 , further comprising:
receiving a packet at the node on the particular time slot;
detecting an error packet within the received packet, wherein the error packet is detected each time the node receives energy on the particular time slot but can not decode the packet;
accumulating a number of consecutive error packets received on the particular time slot; and
determining that the number of consecutive error packets exceeds a threshold received on the particular time slot.
12. The method of operation of a node as claimed in claim 7 , wherein the node maintains a list of identifiers for neighbor nodes the node is currently receiving from, the method further comprising:
receiving, at the node, a Hello message from each of a plurality of neighbor nodes; and
comparing an identifier for each of the neighbor nodes of which the Hello messages were received to the list of identifiers to determine if more than one neighbor node of the node is transmitting on the particular time slot.
13. The method of operation of a node as claimed in claim 7 , further comprising:
transmitting at least one Slot Interference message when the number of consecutive collisions on the particular time slot exceeds the predetermined number.
14. The method of operation of a node as claimed in claim 8 , further comprising:
transmitting at least one Slot Interference message when the average packet completion rate for a predetermined number of packets sent on a particular time slot is less than the threshold.
15. The method of operation of a node as claimed in claim 9 , further comprising:
transmitting at least one Slot Interference message when the node receives the Hello message indicating that more than one neighbor node is receiving on the particular time slot.
16. The method of operation of a node as claimed in claim 10 , further comprising:
transmitting at least one Slot Interference message when the node receives the Hello message indicating that the neighbor node is receiving on the particular time slot and the neighbor node is not on the list of intended destination nodes for the multicast data stream.
17. The method of operation of a node as claimed in claim 11 , further comprising:
transmitting at least one Slot Interference message when the number of consecutive error packets received on the particular time slot exceeds the threshold.
18. The method of operation of a node as claimed in claim 12 , further comprising:
transmitting at least one Slot Interference message when it is determined that more than one neighbor node is transmitting on the particular time slot.
19. The method of operation of a node as claimed in claim 7 , wherein the detecting interference operation further comprises detecting interference when:
the particular time slot is marked for transmission in the Time Slot Utilization Map of the received Hello message,
the particular time slot is marked for reception in the Local Slot Allocation Table, and a previous hop node associated with the particular time slot in the Local Slot Allocation Table is not the neighbor node from which the Hello message was received.
20. The method of operation of a node as claimed in claim 7 , wherein the detecting interference operation further comprises detecting interference when:
the particular time slot is marked for reception in the Time Slot Utilization Map of the received Hello message,
the particular time slot is marked for transmission in the Local Slot Allocation Table,
a next hop node associated with the particular time slot in the Local Slot Allocation Table is not the neighbor node from which the Hello message was received, and
a data stream being transmitted is not a multicast data stream.