Priority-Based Scheduling and Routing in a Wireless Network

• US 20090010205A1
• Filed: 04/10/2008
• Published: 01/08/2009
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: FieldComm Group, Inc.
• Original Assignee: Hart Communication Foundation (FieldComm Group, Inc.)
• Inventors: Blevins, Terrence L., Nixon, Mark J., Rotvold, Eric D., Pratt, Wallace A. JR., Pramanik, Robin S., Lennvall, Tomas P.
• Granted Patent: US 8,406,248 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: G01D 21/00 Measuring or testing not otherwise provided for
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 56/002 Mutual synchronization
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation

Abstract

A method of routing data in a mesh communication network including a plurality of network devices and operating in a process control environment, including assigning one of a plurality of priority levels associated with the communication network to a data packet, sending the data packet from a source network device included in the plurality of network devices to a destination network device included in the plurality of network devices, and routing the data packet to a destination network device via at least one intermediate network device included in the plurality of network devices. The act of routing includes comparing, at each intermediate network device, the priority level of the data packet to a priority mask of the intermediate network device, and modifying at least one of scheduling or routing of the data packet if the priority level of the data packet is not associated with the priority mask of the intermediate network device.

Claims

1. A method of routing data in a mesh communication network including a plurality of network devices and operating in a process control environment, the method comprising:

assigning one of a plurality of priority levels associated with the communication network to a data packet;

sending the data packet from a source network device included in the plurality of network devices to a destination network device included in the plurality of network devices; and

routing the data packet to a destination network device via at least one intermediate network device included in the plurality of network devices, including;

comparing, at each intermediate network device, the priority level of the data packet to a priority mask of the intermediate network device, and

modifying at least one of scheduling or routing of the data packet if the priority level of the data packet is not associated with the priority mask of the intermediate network device.

2. The method of claim 1, wherein modifying at least one of scheduling or routing of the data packet includes rejecting the data packet at the intermediate network device to trigger re-routing of the data packet to the destination network device via another intermediate network device.

3. The method of claim 1, wherein modifying at least one of scheduling or routing of the data packet includes delaying the transmission of the data packet.

4. The method of claim 1, further comprising:

adjusting a priority mask of at least one of the priority of network devices in response to detecting a change in a network condition.

5. The method of claim 4, wherein detecting a change in a network condition includes detecting a network congestion;

wherein modifying at least one of scheduling or routing of the data packet includes rejecting the data packet; and

wherein adjusting a priority mask of at least one of the priority of network devices includes;

excluding at least one priority level previously associated with the priority mask.

6. The method of claim 1, wherein modifying at least one of scheduling or routing of the data packet includes rejecting the data packet, the method further comprising:

adjusting a priority mask of at least one of the priority of network devices to improve performance of the communication network, including;

collecting statistical data indicative of a latency of delivering data packets; and

modifying a priority mask of the network device to thereby cause another network device to route data around the network device.

7. The method of claim 1, wherein the mesh communication network is a wireless network, the method further comprising:

transmitting a first advertisement packet from a first one of the plurality of network devices, including specifying a first join priority of the first one of the plurality of network devices;

transmitting a second advertisement packet from a second one of the plurality of network devices, including specifying a second join priority of the first one of the plurality of network devices;

receiving the first advertisement packet and the second advertisement packet at a joining device not included in the plurality of network devices; and

selecting, at the joining device, a neighbor device between the first one of the plurality of network devices and the second one of the plurality of network devices, including;

comparing the first join priority to the second join priority;

wherein the neighbor device shares a direct wireless connection with the joining device.

8. The method of claim 1, wherein sending the data packet from a source network device includes including a plurality of messages in the data packet, wherein at least two of the plurality of messages have distinct priority levels;

and wherein comparing the priority level of the data packet to the priority mask of the intermediate network device includes;

associating an aggregate priority level with a highest priority level among the plurality of messages; and

comparing the aggregate priority level to the priority mask of the intermediate network device.

9. A method of routing data in a wireless mesh communication network including a plurality of network devices and operating in a process control environment, the method comprising:

assigning one of a plurality of priority levels associated with the communication network to a data packet;

sending the data packet from a source network device included in the plurality of network devices to a destination network device included in the plurality of network devices; and

routing the data packet to a destination network device from the source network device to the destination network device, including;

selecting, at a network device associated with the communication path, a communication link to another network device included in at least one communication path to the destination network device in view of the priority level of the data packet.

10. The method of claim 9, wherein selecting the communication link includes:

identifying a set of neighbor devices included in the plurality of network devices, having a direct wireless connection to the network device, and included in at least one communication path to the destination network device;

comparing the priority level of the data packet to a priority mask of each neighbor device included in the set of neighbor devices; and

excluding each neighbor device whose priority mask does not include the priority level of the data packet from the set of neighbor devices.

11. The method of claim 9, wherein selecting the communication link includes:

identifying a set of communication links, wherein each one in the set of communication links specifies a direct wireless connection to a neighbor device included in the plurality of network devices and having at least one communication path to the destination network device;

comparing the priority level of the data packet to a priority mask of each one of the set of communication links; and

excluding each communication link whose priority mask does not include the priority level of the data packet from the set of communication links.

12. The method of claim 11, wherein each one in the set of communication links is associated with a communication timeslot of a certain duration, a radio frequency, and a priority mask.

13. The method of claim 9, further comprising:

adjusting a priority mask of at least one of a network device or a communication link in response to detecting a change in a network condition.

14. The method of claim 9, the method further comprising:

defining at least one directed routing graph, including, for each graph;

associating a communication path of the graph with a plurality of direct wireless connections between pairs of the plurality of nodes; and

associating one of the plurality of network device with a source of the graph;

associating a different one of the plurality of network device with a destination of the graph, wherein data travels only in a direction from the source of the graph to the destination graph; and

wherein

routing the data packet further includes routing the data packet via a first direct routing graph;

wherein the source network device is the source of the graph and the destination network device is the destination of the graph.

15. A method of routing data in a mesh communication network including a plurality of network devices and operating in a process control environment, the method comprising:

defining a communication timeslot of a certain duration;

defining at least one superframe having a plurality of the communication timeslots;

associating a data packet with one a plurality of priority levels; and

routing the data packet at a first one of the plurality of network devices, including;

selecting a communication timeslot within the first superframe for communicating with another one of the plurality of network devices so that the priority level of the data packet is included in a priority mask associated with the communication timeslot; and

transmitting the data packet in the selected communication timeslot.

16. The method of claim 15, further comprising, for at least one superframe:

associating a first one of the plurality of communication timeslots with a first communication link connecting the first one of the plurality of network devices to a second one of the plurality of network devices and associated with a first link-specific priority mask; and

associating a second one of the plurality of communication timeslots with a second communication link connecting the first one of the plurality of network devices to a third one of the plurality of network devices and associated with a first link-specific priority mask.

17. The method of claim 16, wherein each of the second one of the plurality of network devices and the third one of the plurality of network devices is associated with a respective one of a plurality of directed graphs for routing data to a destination of the data packet;

and wherein selecting a communication timeslot within the first superframe includes selecting between the second one of the plurality of network devices and the third one of the plurality of network devices.

18. A method of routing data in a mesh communication network including a plurality of nodes and operating in a process control environment, the method comprising:

establishing a plurality of direct connections, wherein each of the plurality of direct connections is a unidirectional wireless connection having a transmitting node and a receiving node, wherein each of the transmitting node and the receiving node are included in the plurality of nodes;

generating a plurality of directed graphs defining communication paths between pairs of nodes based on a topology of the wireless network, wherein each directed graph includes at least one of the plurality direct connections;

defining a plurality of concurrent superframes as repeating cycles of consecutively scheduled communication timeslots of a certain duration;

defining a plurality of links to generate a communication schedule of the wireless mesh network, including;

associating each of the plurality of links with one of the plurality of direct connections associated with at least one of the plurality of directed graphs; and

allocating an individual timeslot associated with one of the plurality of superframes to each primary link;

the method further comprising;

routing a data packet from a first one to a second one of a pair of the plurality of nodes along at least one of the plurality of directed graphs, including;

selecting, at least one of the plurality of nodes associated with the one of the plurality of directed graphs, one of the plurality of links associated with the node in view of a priority level of the data packet.

19. The method of claim 18, wherein each of the plurality of links is associated with a priority mask;

and wherein selecting one of the plurality of links includes;

selecting a set of candidate links from the plurality of links, wherein each one in the set of candidate links is associated with at least one of the plurality of directed graphs including the second one of the plurality of nodes and is associated with a priority mask including the priority of the priority level of the data packet; and

selecting a link from the set of candidate links, wherein the selected link is most proximate in time.

20. The method of claim 18, wherein selecting one of the plurality of links includes comparing the priority of the data packet to a priority filter of each of the plurality of nodes associated with each of the plurality of links.

21. The method of claim 18, wherein selecting one of the plurality of links includes comparing the priority of the data packet to a priority of one of the plurality of links.

22. The method of claim 18, wherein selecting one of the plurality of links includes comparing the priority of the data packet to a priority of each one of the plurality of graphs including the node and the second one of the plurality of nodes.