User priority based preemption techniques in a time division multiple access multi-hop ad hoc network

In a multi-hop time division multiple access (TDMA) network comprising a source node seeking to transmit a first communication stream having one or more quality of service (QoS) requirements to a destination node, a method for allowing an intermediate node to preempt a lower priority communication stream for use by the source node, the method comprising:

• transmitting, from the source node, a scout request message to initiate a slot allocation procedure for the first communication stream;
• receiving, at an intermediate node along a route between the source node and a destination node, the scout request message;
• determining, at the intermediate node, whether one or more free time slots are available to support the first communication stream of the source node;
• when the intermediate node determines that free time slots are not available to support the first communication stream of the source node and when the intermediate node is not supporting a communication stream through the intermediate node:
• identifying a lowest priority stream supported at a neighbor node by evaluating a Neighbor Table containing one or more supported stream identifiers (IDs) and their respective stream priority values supported streams and their priorities, wherein the lowest priority stream has a lower priority than the first communication stream;
• and
• transmitting a PREEMPT message to the neighbor node to free one or more TDMA slots being used for the lowest priority stream for use in communicating the first communication stream;
• when the intermediate node determines that the free time slots are not available to support the first communication stream and when the intermediate node is supporting a communication stream through the intermediate node:
• identifying a lowest priority stream supported at the intermediate node by evaluating a Slot Allocation Table (SAT) of the intermediate node, wherein the lowest priority stream has a lower priority than the first communication stream, and
• transmitting one or more Scout Error messages including a stream identification (ID) which uniquely identifies the communication stream to free one or more nodes along a path of the identified lowest priority stream to free one or more TDMA slots used by the lowest priority stream for use in communicating the first communication stream.

In a multi-hop time division multiple access (TDMA) network comprising a source node seeking to transmit a first communication stream to a destination node, a method for allowing the source node to preempt a lower priority communication stream, the method comprising:

• supporting user priorities during slot scheduling in the multi-hop TDMA network based on stream-identifiers (IDs) and stream priority values exchanged by each of the nodes in the multi-hop TDMA network;
• transmitting, a scout request message to a next-hop node along a route towards the destination node, wherein the scout request message comprises a stream ID and a user priority value of the node that initiated time slot scheduling procedure;
• determining, if free time slots are available along the route between the source node and the destination node to meet QoS requirements of the first communication stream;
• when free time slots are not available at a node along the route towards the destination node, determining, based on the stream priorities in a Slot Allocation Table (SAT) when the node is serving as an intermediate node for a communication stream
• and determining based on a neighbor table containing one or more supported stream identifiers (IDs) and their respective stream priority values when the node is not serving as an intermediate node for a communication stream, whether there is a lower priority communication stream in the neighborhood which is using one or more time slots;
• when there is a lower priority communication stream, freeing the one or more time slots currently being used by the lower priority communication stream;
• and allocating the one or more time slots for the first communication stream originated by the source node.