Multichannel, mesh router and methods for path selection in a multichannel mesh network

• US 7,471,633 B2
• Filed: 01/04/2005
• Issued: 12/30/2008
• Est. Priority Date: 01/04/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Conner, W. Steven, Yarvis, Mark, Rangarajan, Anand
• Primary Examiner(s): Pham; Brenda
• Application Number:
  US11/030,593
• Publication Number:
  US 20060146718A1
• Time in Patent Office: 1,456 Days
• Field of Search: 370/389, 370/349, 370/229, 370/235, 370/238, 370/238.1, 370/351, 370/400, 370/401, 370/431, 370/437
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04W 88/18 Service support devices; Network management devices

Abstract

A wireless mesh network router comprises at least one transceiver to receive a packet over a wireless communication channel and path selection circuitry. The packet identifies a source node and a destination node in a multichannel mesh network. The path selection circuitry combines a channel-metric matrix associated with the packet'"'"'s source node and a channel-metric matrix associated with the packet'"'"'s destination node to determine a bottleneck channel for the source-destination pair. The next-hop node and associated transmission channel may be selected from the destination node matrix based on the bottleneck channel.

Claims

1. A wireless mesh network router comprising:

at least one transceiver to receive a packet over a wireless communication channel of a plurality of wireless channels, the packet identifying a source node and a destination node in a multichannel mesh network; and

path selection circuitry to combine a first channel-metric matrix associated with the packet'"'"'s source node and a second channel-metric matrix associated with the packet'"'"'s destination node to identify a bottleneck channel of the plurality of channels for source-destination pair, the path selection circuitry to select a next-hop node and an associated transmission channel based on metrics of the combined matrix including based on the identified bottleneck channel,

wherein the path selection circuitry is configured to generate a channel-metric matrix for destination nodes of the network by construction of paths through the network to the destination nodes on a hop-by-hop basis by separately retaining cost contributions of each of the communication channels in the form of a channel metric vector for each candidate path for use in identifying bottleneck channels for source-destination pairs.

2. The router of claim 1 further comprising more than one transceiver, wherein each of the transceivers is configured to receive and transmit packets on one of a plurality of wireless communication channels,

wherein the wireless mesh network router is one node of a plurality of nodes of the multichannel mesh network, and

wherein at least some of the nodes of the plurality communicate therebetween over more than one of the wireless communication channels.

3. The router of claim 2 wherein the wireless communication channels used by the nodes of the network comprise orthogonal frequency division multiplexed communication channels, each having a plurality of subcarriers.

4. The router of claim 2 wherein the path selection circuitry is configured to select the next-hop node and associated transmission channel to increase diversity among the wireless communication channels used on a route to the destination node.

5. The router of claim 2 further comprising a storage element to store a channel-metric matrix for each node of the network,

wherein at least some of the channel-metric matrices identify more than one next-hop node and an associated one of the wireless communication channels for reaching the associated destination node.

6. The router of claim 5 wherein the channel-metric matrices are stored for each destination node and comprise a channel metric vector for next-hop nodes,

wherein the channel metric vectors comprise a channel metric for each of the communication channels indicating a usage of the communication channel for a path through the network to the destination node associated with the channel-metric matrix.

7. The router of claim 6 wherein elements of the channel metric vectors are each associated with one of the communication channels and comprise a weighted combination of one or more of a hop count, link bandwidth, airtime estimate, and data rate for the associated channels.

8. The router of claim 6 wherein the path selection circuitry is configured to combine the first channel-metric matrix associated with the packet'"'"'s source node and the second channel-metric matrix associated with the packet'"'"'s destination node to generate a new channel-metric matrix,

wherein each channel metric vector of the new channel-metric matrix has a maximum channel metric,

wherein the path selection circuitry is configured to select one of the channel metric vectors having a minimum value of the maximum channel metrics, and

wherein the selected vector is associated with the next-hop node and a transmission channel for routing the packet.

9. The router of claim 8 wherein the path selection circuitry is configured to combine elements of the first channel-metric matrix associated with the packet'"'"'s source node and elements of the second channel-metric matrix associated with the packet'"'"'s destination node to generate the new channel-metric matrix by weighting the elements equally.

10. The router of claim 8 wherein the path selection circuitry is configured to combine elements of the first channel-metric matrix associated with the packet'"'"'s source node and elements of the second channel-metric matrix associated with the packet'"'"'s destination node to generate the new channel-metric matrix by weighting the elements in accordance with a weighting algorithm.

11. A method of forwarding packets in a multichannel mesh network comprising:

receiving a packet over a wireless communication channel of a plurality of wireless channels, the packet identifying a source node and a destination node in a multichannel mesh network;

combining a first channel-metric matrix associated with the packet'"'"'s source node and a second channel-metric matrix associated with the packet'"'"'s destination node to identify a bottleneck channel of the plurality of channels for the source-destination pair,

selecting a next-hop node and an associated transmission channel based on metrics of the combined matrix including based on the identified bottleneck channel, and

generating a channel-metric matrix for destination nodes of the network by construction of paths through the network to destination nodes on a hop-by-hop basis by separately retaining cost contributions of each of a plurality of communication channels in the form of a channel metric vector for each candidate path for use in identifying bottleneck channels for source-destination pairs.

12. The method of claim 11 wherein the receiving, combining and selecting are performed by a wireless mesh network router that is one node of a plurality of nodes of the multichannel mesh network, and

wherein at least some of the nodes of the plurality communicate therebetween over more than one of a plurality of wireless communication channels.

13. The method of claim 12 wherein the wireless communication channels used by the nodes of the network comprise orthogonal frequency division multiplexed communication channels, each having a plurality of subcarriers.

14. The method of claim 12 wherein selecting comprises selecting the next-hop node and associated transmission channel to increase diversity among the wireless communication channels used on a route to the destination node.

15. The method of claim 12 further comprising storing a channel-metric matrix for each node of the network,

wherein at least some of the channel-metric matrices identify more than one next-hop node and an associated one of the wireless communication channels for reaching the associated destination node.

16. The method of claim 15 wherein the channel-metric matrices are stored for each destination node and comprise a channel metric vector for next-hop nodes,

wherein the channel metric vectors comprise a channel metric for each of the communication channels indicating a usage of the communication channel for a path through the network to a destination node associated with the channel-metric matrix.

17. The method of claim 16 wherein elements of the channel metric vectors are each associated with one of the communication channels and comprise a weighted combination of one or more of a hop count, link bandwidth, airtime estimate, and data rate for the associated channels.

18. The method of claim 16 wherein combining comprises combining the first channel-metric matrix associated with the packet'"'"'s source node and the second channel-metric matrix associated with the packet'"'"'s destination node to generate a new channel-metric matrix,

wherein each channel metric vector of the new channel-metric matrix has a maximum channel metric, and

wherein the method further comprises selecting one of the channel metric vectors having a minimum value of the maximum channel metrics, the selected vector being associated with the next-hop node and a transmission channel for forwarding the packet.

19. The method of claim 18 wherein combining comprises combining elements of the first channel-metric matrix associated with the packet'"'"'s source node and elements of the second channel-metric matrix associated with the packet'"'"'s destination node to generate the new channel-metric matrix by weighting the elements equally.

20. The method of claim 18 wherein combining comprises combining elements of the first channel-metric matrix associated with the packet'"'"'s source node and elements of the second channel-metric matrix associated with the packet'"'"'s destination node to generate the new channel-metric matrix by weighting the elements in accordance with a weighting algorithm.

21. A system comprising:

one or more substantially omnidirectional antennas;

at least one transceiver coupled to the at least one antenna to receive a packet over a wireless communication channel of a plurality of wireless channels, the packet identifying a source node and a destination node in a multichannel mesh network; and

path selection circuitry to combine a first channel-metric matrix associated with the packet'"'"'s source node and a second channel-metric matrix associated with the packet'"'"'s destination node to identify a bottleneck channel of the rlurality of channels for the source-destination pair, and to select a next-hop node and an associated transmission channel based on metrics of the combined matrix, wherein the path selection circuitry is configured generate the channel-metric matrix for destination nodes of the network by construction of paths through the network to destination nodes on a hop-by-hop basis by separately retaining cost contributions of each of a plurality of communication channels in the form of a channel metric vector for each candidate path for use in identifying bottleneck channels for source-destination pairs.

22. The system of claim 21 further comprising more than one transceiver, wherein each of the transceivers is configured to receive and transmit packets on one of a plurality of wireless communication channels,

wherein the wireless mesh network router is one node of a plurality of nodes of the multichannel mesh network, and

wherein at least some of the nodes of the plurality communicate therebetween over more than one of the wireless communication channels.

23. The system of claim 22 further comprising a storage element to store a channel-metric matrix for each node of the network,

wherein at least some of the channel-metric matrices identify more than one next-hop node and an associated one of the wireless communication channels for reaching the associated destination node.

24. The system of claim 23 wherein the channel-metric matrices are stored for each destination node and comprise a channel metric vector for next-hop nodes,

wherein the channel metric vectors comprise a channel metric for each of the communication channels indicating a usage of the communication channel for a path through the network to the destination node associated with the channel-metric matrix.

25. A computer-readable medium that stores executable instructions for execution by one or more processors to perform operations comprising:

receiving a packet over a wireless communication channel of a plurality of wireless channels, the packet identifying a source node and a destination node in a multichannel mesh network;

combining a first channel-metric matrix associated with a packet'"'"'s source node and a second channel-metric matrix associated with the packet'"'"'s destination node to identify a bottleneck channel of the plurality of channels for the source-destination pair;

selecting a next-hop node and an associated transmission channel based on metrics of the combined matrix including based on the identified bottleneck channel; and

generating the channel-metric matrices for destination nodes of the network by construction of paths throucih the network to destination nodes on a hop-by-hop basis by separately retaining cost contributions of each of a plurality of communication channels in the form of a channel metric vector for each candidate path for use in identifying bottleneck channels for source-destination pairs.

26. The computer-readable medium of claim 25,

wherein the receiving, combining and selecting are performed by a wireless mesh network router that is one node of a plurality of nodes of the multichannel mesh network, and

wherein at least some of the nodes of the plurality communicate therebetween over more than one of a plurality of wireless communication channels.

27. The computer-readable medium of claim 26 further comprising:

storing a channel-metric matrix for each node of the network, wherein at least some of the channel-metric matrices identify more than one next-hop node and an associated one of the wireless communication channels for reaching the associated destination node.

28. The computer-readable medium of claim 27,

wherein the channel-metric matrices are stored for each destination node and comprise a channel metric vector for next-hop nodes,

wherein the channel metric vectors comprise a channel metric for each of the communication channels indicating a usage of the communication channel for a path through the network to the destination node associated with the channel-metric matrix.