Priority-based scheduling and routing in a wireless network

• US 8,406,248 B2
• Filed: 04/10/2008
• Issued: 03/26/2013
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: FieldComm Group, Inc.
• Original Assignee: Hart Communication Foundation (FieldComm Group, Inc.)
• Inventors: Pratt, Wallace A. Jr., Nixon, Mark J., Rotvold, Eric D., Pramanik, Robin S., Lennvall, Tomas P., Blevins, Terrence L.
• Primary Examiner(s): Rinehart, Mark
• Assistant Examiner(s): HOPKINS, MATTHEW A
• Application Number:
  US12/101,054
• Publication Number:
  US 20090010205A1
• Time in Patent Office: 1,811 Days
• Field of Search: 370/328, 370/344
• US Class Current: 370/444
• 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 at least one intermediate network device upon reception of the data packet at the each at least one intermediate network device, the priority level of the data packet to a priority mask of the each at least one intermediate network device, wherein the priority mask indicates one or more priorities of data packets that are accepted at the each at least one intermediate network device,

accepting the data packet at the each at least one intermediate network device if the comparison of the priority level of the data packet to the priority mask indicates that the priority level of the data packet is accepted at the each at least one intermediate network device, and

modifying at least one of scheduling or routing of the data packet if the comparison of the priority level of the data packet to the priority mask indicates that the priority level of the data packet is not accepted at the each at least one 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 each at least one 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 the priority mask in response to detecting a change in a network condition.

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

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

wherein adjusting the priority mask includes adjusting the priority mask to indicate that data packets of at least one priority level are not accepted at the each at least one intermediate network device.

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

adjusting the 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 the priority mask of the each at least one intermediate network device to thereby cause another network device to route data around the each at least one intermediate 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 each at least one 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 each at least one 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 a priority level 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 particular communication link of a set of communication links 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, including;

identifying a set of neighbor devices included in the plurality of network devices, the set of neighbor devices including the another network device, each neighbor device included in the set of neighbor devices having a direct wireless connection to the source network device, and the each neighbor device 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 the each neighbor device included in the set of neighbor devices; and

excluding, from the set of neighbor devices, each neighbor device whose priority mask does not indicate that the priority level of the data packet is accepted at the each neighbor device.

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

identifying the set of communication links, wherein each communication link of the set of communication links specifies a direct wireless connection to a neighbor device included in the plurality of network devices;

comparing the priority level of the data packet to a priority mask corresponding to the each communication link; and

excluding, from the set of communication links, each communication link whose corresponding priority mask does not indicate that the priority level of the data packet is accepted for travel thereon.

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

12. The method of claim 9, further comprising:

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

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

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

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

associating a respective one of the plurality of network devices with a respective source of the each directed routing graph; and

associating a different respective one of the plurality of network devices with a destination of the each directed routing graph, wherein data travels only in a direction from the source of the each directed routing graph to the destination of the each directed routing graph, wherein;

routing the data packet further includes routing the data packet via a particular direct routing graph; and

the source network device is the source of the particular directed routing graph and the destination network device is the destination of the particular directed routing graph.

14. 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 a particular superframe for communicating with another one of the plurality of network devices,

the selecting based on the priority level of the data packet, a priority of a communication link including the communication timeslot, and a priority mask,

the priority mask specifying the priority of the communication link, and

the communication link defining a connection between the first one of the plurality of network devices and the another one of the plurality of network devices,

wherein the priority mask indicates one or more priorities of data packets that are accepted by the another one of the plurality of network devices and that are accepted for travel over the communication link; and

transmitting the data packet over the communication link in the selected communication timeslot.

15. The method of claim 14, further comprising, for the 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 second link-specific priority mask.

16. The method of claim 15, 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 particular superframe includes selecting between the second one of the plurality of network devices and the third one of the plurality of network devices.

17. 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 of 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; and

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 the first one of the pair of the plurality of nodes, one of the plurality of links in view of a priority level of the data packet and a priority mask, including;

identifying a set of neighbor nodes included in the plurality of nodes, each neighbor node included in the set of neighbor nodes having a direct connection to the first one of the pair of the plurality of nodes, and the each neighbor node included in at least one communication path to the second one of the pair of the plurality of nodes;

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

excluding, from the set of neighbor nodes, each neighbor node whose priority mask does not indicate that the priority level of the data packet is accepted at the each neighbor node.

18. The method of claim 17, wherein selecting the one of the plurality of links further 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 indicating the priority level of the data packet is accepted at the second one of the pair of the plurality of nodes; and

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

19. The method of claim 17, wherein selecting the one of the plurality of links further includes comparing the priority level of the data packet to a priority filter, wherein the priority filter corresponds to each of the plurality of nodes associated with each of the plurality of links.

20. The method of claim 17, wherein selecting the one of the plurality of links further includes comparing the priority level of the data packet to a priority mask that indicates a priority of the one of the plurality of links.

21. The method of claim 17, wherein selecting the one of the plurality of links further includes comparing the priority of the data packet to a priority of each one of the plurality of graphs including the first one and the second one of the pair of the plurality of nodes.