US 8,059,593 B2Granted

Distributed channel allocation method and wireless mesh network therewith

AssigneeIndustrial Technology Research Institute

InventorsYung-Chien Shih, Jen-Shun Yang, Chien-Chao Tseng

Life of this patent

Estimating the term…

Loading patent…

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.

Claims18

Dependent claims

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:
∑
t
=
1
k
⁢
⁢
U
x
,
t
I
x
×
k
,
wherein xεV;
the global utilization is:
∑
x
=
1
n
⁢
⁢
∑
t
=
1
k
⁢
⁢
U
x
,
t
(
∑
x
=
1
n
⁢
⁢
I
x
)
×
k
,
wherein xεV,
wherein V is a set of all the nodes in a network, and |V| is n, T representing the number of divided timeslots, wherein T=k, which is assumed to be k, T>0, Ix representing the number of NICs on a node x, Ux,t representing a number of allocated channels on the node x at a t-th timeslot, in which Ux,t≦Ix and 0<t≦T.

57 more elements

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.

4 more elements

Dependencies are inferred from the claim text.