Wireless device which selects routes excluding loop routes and a mesh network including the same

• US 8,184,584 B2
• Filed: 10/23/2008
• Issued: 05/22/2012
• Est. Priority Date: 10/25/2007
• Status: Active Grant

• Current Assignee: Advanced Telecommunications Research Institute International, NEC Communication Systems Limited (NEC Corporation)
• Original Assignee: Advanced Telecommunications Research Institute International, NEC Communication Systems Limited (NEC Corporation)
• Inventors: Itaya, Satoko, Davis, Peter, Obana, Sadao, Ito, Tetsuya, Matsumoto, Akira, Kondo, Yoshihisa, Suzuki, Ryutaro
• Primary Examiner(s): Phunkulh, Bob
• Application Number:
  US12/256,753
• Publication Number:
  US 20090109901A1
• Time in Patent Office: 1,307 Days
• Field of Search: None
• US Class Current: 370/330
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04W 40/16 based on interference

Abstract

In wireless communication using links with neighbor wireless devices, a wireless device calculates ratios of throughput to maximum throughput for the links and calculates the costs of the links using the calculated ratios. Then the wireless device finds, for each destination, a route in which the sum of such calculated link costs is the minimum, and sends a packet to the destination using the route. As a consequence, routing can be done according to an isotonic, easy-to-implement routing protocol.

Claims

1. A wireless device which is used in a mesh network including a plurality of wireless devices located in a mesh pattern, and makes wireless communication using a plurality of channels, the device comprising:

a routing table storing route information;

a plurality of interfaces each of which transmits and receives a packet using one channel selected from among the plurality of channels;

a tabulation unit creating the routing table by detecting a route with relatively large ratio of throughput to maximum throughput, considering channel interference in flows, and excluding loop routes, and storing the detected route as the optimum route to a destination; and

a communication unit selecting the optimum route from the routing table and transmits a packet,

wherein the tabulation unit stores, in the routing table, a route metric which is smaller when the ratio of throughput to maximum throughput is larger, and larger when the ratio of throughput to maximum throughput is smaller, and a destination corresponding to the route metric to indicate the optimum route.

2. The wireless device according to claim 1, wherein the tabulation unit calculates, based on channel distributions in all flows passing through a link to be evaluated, ratios of throughput to maximum throughput for wireless communication using the link to be evaluated, and calculates the route metrics from the calculated ratios of throughput to maximum throughput and stores the calculated metrics in the routing table in correspondence with the destinations.

3. The wireless device according to claim 2, wherein the tabulation unit detects, based on the channel distributions, all channel distribution patterns in the flows, and categorizes all the detected channel distribution patterns into a plurality of standard distribution patterns and counts the number of channel distribution patterns categorized to each standard distribution pattern, and based on this counted number, the total number of distribution patterns, and actually measured ratios of throughput to maximum throughput for each standard distribution pattern, calculates ratios of throughput to maximum throughput for wireless communication using the link to be evaluated.

4. The wireless device according to claim 3, wherein the tabulation unit calculates ratios of throughput to maximum throughput for wireless communication using the link to be evaluated, from the number of distribution patterns categorized to each standard distribution pattern, the number of all the distribution patterns, and actually measured ratios of throughput to maximum throughput for each standard distribution pattern, by weighted-averaging of actually measured ratios of throughput to maximum throughput for each standard distribution pattern, with weights that are the ratios of probability that the channel distribution patterns are categorized to standard distribution patterns.

5. The wireless device according to claim 2, wherein the tabulation unit calculates the route metrics which are in inverse proportion to the ratios of throughput to maximum throughput for wireless communication using the link to be evaluated.

6. The wireless device according to claim 2, wherein:

the tabulation unit calculates the link costs of all the links between the wireless device and wireless devices adjacent to it from the calculated ratios of throughput to maximum throughput; and

after the tabulation unit calculates the link costs of all the links, the communication unit broadcasts the calculated link costs.

7. The wireless device according to claim 6, wherein the tabulation unit receives link costs broadcast from other wireless devices and calculates the route metrics from the received link costs.

8. The wireless device according to claim 2, wherein the tabulation unit calculates the route metrics from the ratios of throughput to maximum throughput for wireless communication using the link to be evaluated, by a method which varies according to the type of application using wireless communication.

9. The wireless device according to claim 8, wherein if transmission rate in the wireless communication is relatively high, the tabulation unit calculates a route metric which is in inverse proportion to the ratio of the throughput to the maximum throughput for wireless communication using the link to be evaluated.

10. A mesh network including a plurality of wireless devices located in a mesh pattern which make wireless communication using a plurality of channels, each of the wireless devices comprising:

a routing table storing route information;

a plurality of interfaces each of which transmits and receives a packet using one channel selected from among the channels;

a tabulation unit creating the routing table by detecting a route with relatively large ratio of throughput to maximum throughput, considering channel interference in flows and excluding loop routes, and storing the detected route as the optimum route to a destination; and

a communication unit selecting the optimum route from the routing table and transmits a packet,

wherein the tabulation unit stores, in the routing table, a route metric which is smaller when the ratio of throughput to maximum throughput is larger, and larger when the ratio of throughput to maximum throughput is smaller, and a destination corresponding to the route metric to indicate the optimum route.