Distributed channel allocation method and wireless mesh network therewith

• US 8,059,593 B2
• Filed: 07/29/2007
• Issued: 11/15/2011
• Est. Priority Date: 04/02/2007
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Shih, Yung-Chien, Yang, Jen-Shun, Tseng, Chien-Chao
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): ADHAMI, MOHAMMAD SAJID
• Application Number:
  US11/829,952
• Publication Number:
  US 20080240026A1
• Time in Patent Office: 1,570 Days
• Field of Search: None
• US Class Current: 370/329
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04W 40/16 based on interference

Abstract

A distributed channel allocation method and a wireless mesh network with the same are provided herein. By the distributed channel allocation, interference situations are avoided in a wireless network communication, and the allocated bandwidth can then be fully utilized. Besides, unnecessary depletion of an allocated bandwidth due to the interference can be avoided. By this method, a time division technique is applied for dividing a transmission time of each wireless NIC, and different non-overlapping channels can be assigned to different timeslots. Different from other researches that require a symmetrical number of the NICs between a receiving node and a transmitting node, in this method, a unique wireless NIC may communicate with the wireless NICs. The method provides the feature that the number of the NICs on a certain node can be adjusted to meet a communication requirement, by which the efficiency of a network flow is also significantly improved.

Claims

1. A distributed channel allocation method for a WMN system comprising a plurality of nodes, comprising:

determining one free channel or a plurality of free channels between adjacent nodes according to channel utilization of the nodes;

selecting the nodes which a routing path passes through according to the routing path and determining a start node and a target node from the nodes selected;

selecting the free channels to be used in a sequence from the target node to the start node to establish the routing path, wherein the selection of the free channels is in accordance with a requirement of a shortest routing path, and the selected free channels to be used are different from those used by the adjacent nodes;

if a transmission path or a plurality of transmission paths is already allocated on the nodes of the routing path, a priority is given to the transmission path or paths, and during the free channel selection, the transmission path having the priority is considered first;

increasing a number of NICs on the nodes according to a bandwidth requirement wherein the bandwidth requirement is based on network flow; and

selecting the free channels to be used in the sequence from the target node to the start node to establish the routing path satisfying the bandwidth requirement, wherein the selection of the free channels is in accordance with a requirement of the shortest routing path, and the selected free channels to be used are different from those used by the adjacent nodes, wherein

the node utilization is;

2. The distributed channel allocation method as claimed in claim 1, wherein the selection of the free channels satisfies the condition that no repetitive channel is used within three hops.

3. The distributed channel allocation method as claimed in claim 1, wherein a three-tuple (a1, a2, a3) is defined as a combination of the free channels, a3 is a free channel of a present link, a2 is a free channel of a previous link, and a1 is a free channel of previous two links.

4. The distributed channel allocation method as claimed in claim 1, wherein the free channel or channels is/are not in a state of transmitting, receiving or interfered.

5. The distributed channel allocation method as claimed in claim 1, wherein a time division technique is added to the steps of determining the free channel or channels according to the channel utilization of the nodes, so as to increase the applicable free channel or channels.

6. The distributed channel allocation method as claimed in claim 1, wherein the selection of the free channels satisfies the condition that no repetitive channel is used within three hops.

7. The distributed channel allocation method as claimed in claim 1, wherein the free channel or channels is/are not in a state of transmitting, receiving or interfered.

8. The distributed channel allocation method as claimed in claim 1, wherein a time division technique is added to the steps of determining the free channel or channels according to the channel utilization of the nodes, so as to increase the applicable free channel or channels.

9. The distributed channel allocation method as claimed in claim 1, wherein a method of increasing the number of NICs on the nodes according to the bandwidth requirement comprises performing a channel allocation according to the routing path and the bandwidth;

judging if there exists one of the nodes satisfying a condition, wherein the condition is a difference between a node utilization and a global utilization being greater than a threshold value if the channel allocation is unsuccessful; and

adding the NIC to the node if the node exists.

10. The distributed channel allocation method as claimed in claim 1, further comprising:

presetting a network flow and a flow direction of transmitting and receiving from the nodes to the adjacent nodes according to a requirement of a system;

selecting the nodes which a routing path passes through according to the routing path and determining a start node and a target node;

selecting the number of NICs on the nodes according to the network flow and the flow direction; and

selecting a free channel or channels to be used in a sequence from the target node to the start node to establish the routing path satisfying the bandwidth requirement, wherein the selected free channels to be used are different from those used by the adjacent nodes.

11. The distributed channel allocation method as claimed in claim 10, wherein the number of the NICs required for each node is calculated by a following formula:

12. The distributed channel allocation method as claimed in claim 10, wherein the selection of the free channel or channels satisfies the condition that no repetitive channel is used within three hops.

13. The distributed channel allocation method as claimed in claim 10, wherein a time division technique is added to the steps of determining the free channel or channels according to a channel utilization of the nodes to increase the applicable free channel or channels.

14. A WMN system, having a function of a distributed channel allocation, wherein the WMN comprises a plurality of nodes, and the distributed channel allocation comprises:

determining a free channel or a plurality of free channels according to a channel utilization of the nodes;

selecting the nodes which a routing path passes through according to the routing path; and

selecting the free channels to be used from the nodes on the routing path in order to establish the routing path, wherein the selection of the free channels is in accordance with the requirement of a shortest routing path, and the selected free channels to be used are different from those used by the adjacent nodes, if a transmission path or a plurality of transmission paths is already allocated on the nodes of the routing path, a priority is given to the transmission path or paths, and during the free channel selection, the transmission path having the priority is considered first, and the distributed channel allocation further comprises increasing the number of NICs on the nodes according to a bandwidth requirement,

wherein a method of increasing the number of NICs on the nodes according to the bandwidth requirement comprises performing a channel allocation according to the routing path and the bandwidth;

judging if there exists one of the nodes satisfying a condition, wherein the condition is a difference between a node utilization and a global utilization being greater than a threshold value if the channel allocation is unsuccessful; and

adding the NIC to the node if the node exists.

15. The WMN system as claimed in claim 14, wherein the selection of the free channel satisfies the condition that no repetitive channel is used within three hops.

16. The WMN system as claimed in claim 14, wherein the free channel or channels is/are not in a state of transmitting, receiving or interfered.

17. The WMN system as claimed in claim 14, wherein a time division technique is added to the steps of deteiniining the free channel or channels according to the channel utilization of the nodes, so as to increase the applicable free channel or channels.

18. The WMN system as claimed in claim 14, wherein a time division technique is added to the steps of detennining the free channel or channels according to the channel utilization of the nodes, so as to increase the applicable free channel or channels.