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

• US 20060146718A1
• Filed: 01/04/2005
• Published: 07/06/2006
• 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
• Granted Patent: US 7,471,633 B2
• Time in Patent Office: Days
• 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, 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, the path selection circuitry to select a next-hop node and an associated transmission channel based on metrics of the combined matrix.

2. The router of claim 1 further comprising more than one transceiver, wherein each of the transceivers is adapted 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 adapted 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 adapted 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 adapted 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 adapted 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 adapted 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. The router of claim 2 wherein the path selection circuitry is adapted to 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 and separately retaining cost contributions of each of the communication channels in the form of a channel metric vector for each candidate path.

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

receiving a packet over a wireless communication channel, 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; and

selecting a next-hop node and an associated transmission channel based on metrics of the combined matrix.

13. The method of claim 12 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.

14. The method of claim 13 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.

15. The method of claim 13 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.

16. The method of claim 13 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.

17. The method of claim 16 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.

18. The method of claim 17 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.

19. The method of claim 17 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.

20. The method of claim 19 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.

21. The method of claim 19 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.

22. The method of claim 13 further comprising generating the channel-metric matrices for destination nodes of the network by construction of paths through the network to destination nodes on a hop-by-hop basis and separately retaining cost contributions of each of the communication channels in the form of a channel metric vector for each candidate path.

23. 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, 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 and to select a next-hop node and an associated transmission channel based on metrics of the combined matrix.

24. The system of claim 23 further comprising more than one transceiver, wherein each of the transceivers is adapted 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.

25. The system of claim 24 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.

26. The system of claim 25 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.

27. A machine-accessible medium that provides instructions, which when accessed, cause a machine to perform operations comprising:

receiving a packet over a wireless communication channel, 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; and

selecting a next-hop node and an associated transmission channel based on metrics of the combined matrix.

28. The machine-accessible medium of claim 27 wherein the instructions, when further accessed cause the machine to perform operations,

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.

29. The machine-accessible medium of claim 28 wherein the instructions, when further accessed cause the machine to perform operations 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.

30. The machine-accessible medium of claim 29 wherein the instructions, when further accessed cause the machine to perform operations,

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.