Method and processing device for optimal interference estimation and scheduling in a multi-hop wireless network with centralized control

1. A device comprising:

a memory configured to store a conflict graph representative of wireless links between nodes of a wireless multi-hop network that interfere with each other when transmitting simultaneously on a same radio channel at given data rates, the nodes represented in the graph being configured to use a MAC protocol supporting a slotted access;

a processing device configured to:

generate a data transmission schedule for each multi-slot frame of a data transmission over the multi-hop network, based on the conflict graph in the memory;

update said conflict graph based on interference information provided by said nodes during said frame; and

refine the conflict graph based on detected failures of data transmissions that were previously scheduled using the conflict graph.

2. The device according to claim 1 , wherein the processing device is further configured to update the conflict graph, the conflict graph further comprising a set of vertices, where each vertex represents a link between two of said nodes transmitting at a given data rate, and a set of edges, where each edge between two vertices represents two links corresponding to these vertices that interfere when they transmit simultaneously on the same channel at corresponding data rates.

3. The device according to claim 1 , wherein the interference information comprises a Received Signal Strength measurement.

4. The device according to claim 1 , wherein to detect the failures in data transmission the processing device is further configured to analyze packet delivery ratios of links between nodes.

5. The device according to claim 1 , wherein the processing device is further configured to:

update a reachability graph during each frame, the reachability graph comprising a set of vertices, where each vertex corresponds to a network node and each directional edge from a first vertex to a second vertex indicates that said second vertex is within transmission range from said first vertex, from at least said interference information provided by said nodes during each frame; and

detect hidden interferer nodes among nodes that are at least two-hops away from a receiver node in said reachability graph.

6. The device according to claim 5 , wherein the processing device is further configured to:

update said reachability graph during each frame by computing directional edges; and

link a first node to a second node when said first node is able to receive chosen packets broadcast by said second node during said frame, based on at least said interference information transmitted by said nodes during said frame.

7. The device according to claim 5 , wherein the processing device is further configured to:

detect, during each frame, a set of hidden interferer nodes from at least feedback information relative to the data transmissions and transmitted by said nodes during at least a previously scheduled frame.

8. The device according to claim 7 , wherein the processing device is further configured to:

label each link associated with a packet delivery ratio equal to zero as a failing link; and

generate a set of failing links.

9. The device according to claim 8 , wherein the processing device is further configure to:

determine for said set of failing links for which a data transmission failure has been detected, a set of hidden interferer nodes that represent transmitter nodes which are at least a chosen number of hops away from the receiver node of each failing link; and

add an edge into said conflict graph between each vertex corresponding to a falling link and the vertices whose corresponding links have as transmitter nodes the nodes in said set of hidden interferer nodes.

10. The device according to claim 8 , wherein the processing device is further configured to:

consider for each said failing link a first set of all link transmission sets of the previous frame where this link succeeded and a second set of all the link transmission sets of the previous frame where this link failed; and

initialize said set of hidden interferer nodes for said failing link by adding only the transmitter nodes of the links that appear in said second set and do not appear in said first set.

11. The device according to claim 10 , wherein the processing device is further configured to:

form a set of hidden interferer nodes by selecting from said initial set of hidden interferer nodes ones that are two-hops away from receiver node of said failing link in said reachability graph; and

add an edge into said conflict graph between the vertex that corresponds to said failing link and the vertices that correspond to links that have as transmitter nodes the nodes in said set of hidden interferer nodes.

12. The device according to claim 11 , wherein the processing device is further configured to:

if said failing link that failed in the previous frame fails again in a current frame, form a set of hidden interferer nodes for the current frame by selecting from said initial set of hidden interferer nodes ones that are three-hops away from receiver node of said falling link in said reachability graph;

update said conflict graph by adding an edge between the vertex that corresponds to said failing link and the vertices that correspond to links that have as transmitter nodes the nodes in said set of hidden interferer nodes; and

if said failing link continues failing in subsequent frames, repeat the forming of a set of hidden interferer nodes and the updating of said conflict graph with an increasing number of hops away from receiver node of said failing link in said reachability graph, until said failing link succeeds in a subsequent frame.

13. A method for transmitting data in a multi-hop wireless network of nodes using a MAC protocol supporting a slotted access, the method comprising:

generating, using a controller, schedules for transmitting data into multi-slot frames, based on a conflict graph representative of wireless links between nodes that interfere with each other when transmitting simultaneously on a same radio channel using certain data rates;

measuring, using the controller, chosen interference information from each node;

receiving, by the controller, from each node, said measured chosen interference information and measured feedback information obtained in a previous frame;

updating, using the controller, said conflict graph based on the received interference information;

refining, using the controller, said updated conflict graph from detection of hidden interferer nodes based on detected failures of data transmissions of the links between said nodes deduced from feedback information measured during at least the previous frame;

computing, using the controller, a data transmission schedule for said nodes; and

transmitting, using the controller, said computed data transmission schedule from said controller to said nodes.

14. A device comprising:

a memory configured to store a conflict graph representative of wireless links between nodes in a multi-hop wireless network of nodes that interfere with each other when transmitting simultaneously on a same radio channel using certain data rates;

a controller configured to:

generate schedules for transmitting data into multi-slot frames, based on a conflict graph representative of wireless links between nodes that interfere with each other when transmitting simultaneously on a same radio channel using certain data rates;

measure chosen interference information from each node;

receive from each node, said measured chosen interference information and measured feedback information obtained in a previous frame;

update said conflict graph based on the received interference information;

refine said updated conflict graph from detection of hidden interferer nodes based on detected failures of data transmissions of the links between said nodes deduced from feedback information measured during at least the previous frame;

compute a data transmission schedule for said nodes; and

transmit said computed data transmission schedule from said controller to said nodes.

15. A network device comprising:

a memory;

at least one processor to:

transmit and receive data to and from other nodes in a multi-hop wireless network using a MAC protocol supporting a slotted access;

measure chosen interference information;

transmit to a controller said measured chosen interference information and measured feedback information obtained in a previous frame;

receive a data transmission schedule for transmitting data into multi-slot frames, based on a conflict graph, the conflict graph being representative of wireless links between nodes that interfere with each other when transmitting simultaneously on a same radio channel using certain data rates;

transmit data during associated time slots in accordance with said received data transmission schedule;

measure feedback information relative to said data transmissions; and

refine the conflict graph based on detected failures of data transmissions that were previously scheduled using the conflict graph.

16. A method comprising:

transmitting and receiving, with at least one processor, data to and from other nodes in a multi-hop wireless network using a MAC protocol supporting a slotted access;

measuring, by the at least one processor, chosen interference information;

transmitting, by the at least one processor, to a controller said measured chosen interference information and measured feedback information obtained in a previous frame;

receiving, by the at least one processor, a data transmission schedule for transmitting data into multi-slot frames, based on a conflict graph, the conflict graph being representative of wireless links between nodes that interfere with each other when transmitting simultaneously on a same radio channel using certain data rates;

transmitting, by the at least one processor, data during associated time slots in accordance with said received data transmission schedule;

measuring, by the at least one processor, feedback information relative to said data transmissions; and

refining the conflict graph based on detected failures of data transmissions that were previously scheduled using the conflict graph.

17. A method comprising:

storing, by a processing device, a conflict graph representative of wireless links between nodes of a wireless multi-hop network that interfere with each other when transmitting simultaneously on a same radio channel at given data rates, the nodes represented in the graph being configured to use a MAC protocol supporting a slotted access;

generating, by the processing device, a data transmission schedule for each multi-slot frame of a data transmission over the multi-hop network, based on the conflict graph;

updating, by the processing device, said conflict graph based on interference information provided by said nodes during said frame; and

refining, by the processing device, the conflict graph based on detected failures of data transmissions that were previously scheduled using the conflict graph.

18. The method according to claim 17 , further comprising:

updating, by the processing device, the conflict graph, the conflict graph further comprising a set of vertices, where each vertex represents a link between two of said nodes transmitting at a given data rate, and a set of edges, where each edge between two vertices represents two links corresponding to these vertices that interfere when they transmit simultaneously on the same channel at corresponding data rates.

19. The method according to claim 17 , wherein the interference information comprises a Received Signal Strength measurement.

20. The method according to claim 17 , further comprising analyzing, by the processing device, packet delivery ratios of links between nodes to detect failures in data transmission.

21. The method according to claim 17 , further comprising:

updating, by the processing device, a reachability graph during each frame, the reachability graph comprising a set of vertices, where each vertex corresponds to a network node and each directional edge from a first vertex to a second vertex indicates that said second vertex is within transmission range from said first vertex, from at least said interference information provided by said nodes during each frame; and

detecting, by the processing device, hidden interferer nodes among nodes that are at least two-hops away from a receiver node in said reachability graph.

22. The method according to claim 21 , further comprising:

updating, by the processing device, said reachability graph during each frame by computing directional edges; and

linking, by the processing device, a first node to a second node when said first node is able to receive chosen packets broadcast by said second node during said frame, based on at least said interference information transmitted by said nodes during said frame.

23. The method according to claim 21 , further comprising:

detecting, by the processing device, during each frame, a set of hidden interferer nodes from at least feedback information relative to the data transmissions and transmitted by said nodes during at least a previously scheduled frame.

24. The method according to claim 23 , further comprising:

labeling, by the processing device, each link associated with a packet delivery ratio equal to zero as a failing link; and

generating, by the processing device, a set of failing links.

25. The method according to claim 24 , further comprising:

determining, by the processing device, for said set of failing links for which a data transmission failure has been detected, a set of hidden interferer nodes that represent transmitter nodes which are at least a chosen number of hops away from the receiver node of each failing link; and

adding, by the processing device, an edge into said conflict graph between each vertex corresponding to a falling link and the vertices whose corresponding links have as transmitter nodes the nodes in said set of hidden interferer nodes.

26. The method according to claim 24 , further comprising:

considering, by the processing device, for each said failing link a first set of all link transmission sets of the previous frame where this link succeeded and a second set of all the link transmission sets of the previous frame where this link failed; and

initializing, by the processing device, said set of hidden interferer nodes for said failing link by adding only the transmitter nodes of the links that appear in said second set and do not appear in said first set.

27. The method according to claim 26 , further comprising:

forming, by the processing device, a set of hidden interferer nodes by selecting from said initial set of hidden interferer nodes ones that are two-hops away from receiver node of said failing link in said reachability graph; and

adding, by the processing device, an edge into said conflict graph between the vertex that corresponds to said failing link and the vertices that correspond to links that have as transmitter nodes the nodes in said set of hidden interferer nodes.

28. The method according to claim 27 , further comprising:

if said failing link that failed in the previous frame fails again in a current frame, forming, by the processing device, a set of hidden interferer nodes for the current frame by selecting from said initial set of hidden interferer nodes ones that are three-hops away from receiver node of said falling link in said reachability graph;

updating, by the processing device, said conflict graph by adding an edge between the vertex that corresponds to said failing link and the vertices that correspond to links that have as transmitter nodes the nodes in said set of hidden interferer nodes; and

if said failing link continues failing in subsequent frames, repeating, by the processing device, the forming of a set of hidden interferer nodes and the updating of said conflict graph with an increasing number of hops away from receiver node of said failing link in said reachability graph, until said failing link succeeds in a subsequent frame.