FIELD OF INVENTION

The present invention relates to a wireless multi-hop network and more particularly to a system and method for allocating bandwidth in a wireless multi-hop network. BACKGROUND OF THE INVENTION

A wireless multi-hop network generally comprises of client nodes, router nodes and gateway nodes. The router nodes facilitate the connectivity and intercommunication of nodes through multi-hop wireless paths. The gateway nodes are connected to the router nodes or the client nodes for connecting to Internet or other network.

One of the main problems of the wireless multi-hop network is disparity of bandwidth (BW) availability amongst nodes, wherein the bandwidth or BW refers to the amount of data transmission opportunity in bit per second (bps) between a node and the gateway node. As the hop count from the gateway node increases, the throughput decreases due to the links with larger hop counts may subject to starvation by the links with smaller hop count from the gateway node. In addition to that, the nodes having lower BW are penalized by those nodes having larger BW. However, it is difficult to fairly allocate BW in the wireless multi-hop network as different links have different bandwidth or data transmission rates and the allocation of BW at one link affects the allocation of other links. Moreover, the BW demand of each node is dynamic and thus, the BW demand for each node may differ at different point of time. In addition to that, the allocation of BW needs to consider the capability of each node as some nodes provide radio access while others do not provide radio access. Those nodes without radio access only route data packets to its neighbouring nodes.

Therefore, there is a need to provide a system and method to dynamically and fairly allocate BW in a wireless multi-hop network. SUMMARY OF INVENTION

In a first aspect of the present invention, a system (100) for allocating bandwidth in a wireless multi-hop network is provided. The system (100) comprises of at least one gateway ( 10) and a plurality of nodes (120). The at least one gateway (110) and the plurality of nodes (120) include a resource agent (130) for aggregating bandwidth demand from its child nodes and allocating bandwidth to its child nodes. The resource agent (130) further comprises of a bandwidth request module (131) for aggregating bandwidth demand of its node and its child nodes and requesting the aggregated bandwidth demand from its parent node, a bandwidth allocation module (132) for determining the amount of bandwidth to be allocated to its node and child nodes, a bandwidth table (133) for storing information relating to its communication links and the bandwidth demanded and allocated, a bandwidth controller module (134) for configuring its link to enforce the bandwidth allocated, and a communication interface module (135) for communicating with other resource agents (130) of its parent node and child nodes.

Preferably, the plurality of nodes (120) are interconnected in a tree like structure.

In a second aspect of the present invention, a resource agent (130) for allocating bandwidth in a wireless multi-hop network is provided. The resource agent (130) includes a bandwidth request module (131) for aggregating bandwidth demand of its node and its child nodes and requesting the aggregated bandwidth demand from its parent node; a bandwidth allocation module (132) for determining the amount of bandwidth to be allocated to its node and child nodes; a bandwidth table (133) for storing information relating to its communication links and the bandwidth demanded and allocated; a bandwidth controller module (134) for configuring its link to enforce the bandwidth allocated; and a communication interface module (135) for communicating with other resource agents (130) of its parent node and child nodes.

In a third aspect of the present invention, a method for allocating bandwidth in a wireless multi-hop network is provided. The method is characterised by the steps of: (a) acquiring information relating to its node's links and/or access by each resource agent (130); (b) storing and updating the bandwidth table (133) with the information relating to node's links and/or access; (c) aggregating bandwidth demands from its access link or child nodes by the bandwidth request module (131) of each resource agent (130); (d) sending a bandwidth request to its parent node's resource agent (130) through the communication interface module (135); (e) allocating bandwidth to its access link and child nodes by the bandwidth allocation module (132) of each resource agent (130); (f) configuring its link by the bandwidth controller module (134) of each resource agent (130) to enforce the bandwidth allocated; (g) monitoring and detecting changes in its child nodes by each resource agent (130), wherein if there is a change in its child links, updating its bandwidth table (133) and repeating steps (c) to (f); and (h) monitoring and detecting changes in its access links by each resource agent (130), wherein if there is a change in its access links, updating its bandwidth table ( 33) and repeating steps (c) to (g).

Preferably, step (c) starts from the gateway (110) to the nodes (120) at the lowest tier of the wireless multi-hop network. Moreover, step (c) includes the steps of: acquiring and aggregating its node's bandwidth demand and its child node's bandwidth demand; determining whether the parent node has the capacity to provide the total amount of aggregated bandwidth demand; requesting the total amount of aggregated bandwidth demand if the parent node is able to provide the total amount of aggregated bandwidth demand; requesting maximum amount of bandwidth that can be provided by the parent node if the parent node is unable to provide the total amount of aggregated bandwidth demand; and generating and sending a bandwidth request message to its parent node through the communication interface module (135).

Preferably, step (e) starts from the lowest tier of the wireless multi-hop network to the gateway (110). Moreover, step (e) further includes the steps of: comparing its requested bandwidth with the total amount of available bandwidth; if the requested bandwidth is lower than or equal to the available bandwidth, allocating the bandwidth requested for its own node and its child node; if the requested bandwidth is higher than the available bandwidth, determining whether there is a child node in its link, wherein if there is no child node, allocating the available bandwidth for its access links, and wherein if there is at least one child node, computing a fair sharing value and left over value to determine the bandwidth allocation for its own node and computing a base unit to determine the bandwidth allocation for its child nodes; and generating and sending a bandwidth allocation message to its child node through the communication interface module (135).

Preferably, the fair sharing value is computed by dividing the available bandwidth with the total amount of child nodes of all depths plus one.

Preferably, the left over value is computed by deducting all requests made by its child nodes from the available bandwidth. Preferably, the base unit is computed by dividing the remaining bandwidth with the total bandwidth requested from all child nodes, and wherein the base unit is used to determine the bandwidth allocation for its child nodes by multiplying the requested bandwidth of the child node with the computed base unit. Advantageously, the present invention provides fair bandwidth distribution among nodes in a wireless multi-hop network.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.

FIG. 1 shows a block diagram of a system (100) for allocating bandwidth in a wireless multi-hop network according to an embodiment of the present invention.

FIG. 2 shows a block diagram of a resource agent (130) of the system (100) as shown in FIG. 1.

FIG. 3 shows a flow chart of a method for operating the system (100) of FIG. 1.

FIG. 4 shows a flow chart of a method for aggregating bandwidth demand and generating bandwidth request according to an embodiment of the present invention.

FIG. 5 shows a flow chart of a method for allocating bandwidth according to an embodiment of the present invention. FIG. 6 shows a message format of a bandwidth request message. FIG. 7 shows a message format of a bandwidth allocation message.

DESCRIPTION OF THE PREFFERED EMBODIMENT

A preferred embodiment of the present invention will be described herein below with reference to the accompanying drawings. In the following description, well known functions or constructions are not described in detail since they would obscure the description with unnecessary detail.

Referring now to FIG. 1, there is shown a system (100) for allocating bandwidth in a wireless multi-hop network. The system (100) provides fair bandwidth sharing among all nodes in the wireless multi-hop network. Generally, the system (100) comprises of a gateway (110) and a plurality of nodes (120).

The gateway (110) is used to allow connection to the Internet, an Ethernet, local area network (LAN), wide area network (WAN) or any other appropriate network. The gateway (110) is connected to one of the nodes (120). Although the system (100) is shown as having one gateway (110) connected to a node (120a), it is understood that the system (100) may include any suitable number of gateway (110) connected to any suitable number of node.

The plurality of nodes (120) are interconnected in a tree like structure, wherein node A (120a) is connected to node B (120b) and node C (120c), node B (120b) is connected to node E (120e) and node F (120f), and node C (120c) is connected to node D (120d). The nodes (120) can be defined as parent and child nodes relationship, wherein node A (120a) is the parent node of node B (120b) and node C (120c), and node A (120a) is the child node of the gateway (110); node B (120b) is the parent node of node E (120e) and node F (120f), and node B (120b) is the child node of node A (120a); node C (120c) is the parent node of node D (120d), and node C (120c) is the child node of node A (120a); node E (120e) and node F (120f) are the child nodes of node B (120b); and node D (120d) is the child node of node C (120c). Each node (120) is able to transmit and receive data signal to/from its parent and child nodes. Thus, each node (120) may include any suitable hardware, software or any combination thereof to transmit, receive and/or process communications in the wireless multi-hop network. Moreover, each node (120) may communicate with wireless devices if it is equipped with radio access. The wireless devices include but not limited to laptop computers, mobile phones or any other device suitable for communicating wirelessly within the wireless multi-hop network. Although there are only six nodes (120) shown in the system (100), it is understood that the system (100) may include any number of nodes (120). In the following description and the appended claims, the link between a node (120) to another node (120) is defined as either a parent or a child link, whereas the link between one node (120) to a wireless device is defined as an access link.

In each node (120) and gateway (110), there is provided a resource agent (130) which is shown in FIG. 2. The resource agent (130) is used for aggregating bandwidth demand from its child nodes and allocating bandwidth to its child nodes. The resource agent (130) includes a bandwidth request module (131), a bandwidth allocation module (132), a bandwidth table (133), a bandwidth controller module (134), and a communication interface module (135).

The bandwidth request module (131) is used to aggregate bandwidth demand of its node and also its child nodes, and to request the aggregated bandwidth demand from its parent node. More particularly, the bandwidth request module (131) receives bandwidth request message from its child nodes' resource agent (130) and thereon, the bandwidth request module (131) aggregates the bandwidth demand of its node and child nodes and sends a bandwidth request message which includes the aggregated bandwidth demand to its parent node's resource agent (130). The bandwidth request module (131) is connected to the bandwidth allocation module (132), the bandwidth table (133) and the communication interface module (135).

The bandwidth allocation module (132) is used to determine the amount of bandwidth to be allocated to its node and child nodes. More particularly, the bandwidth allocation module (132) receives bandwidth allocation message from its parent node and thereon, the bandwidth allocation module (132) determines the amount of bandwidth to be allocated for its node and each child node and sends a message to the bandwidth controller module (134) to enforce the allocated bandwidth of its child nodes. The bandwidth allocation module (132) is connected to the bandwidth request module (131), the bandwidth table (133), the bandwidth controller module (134) and the communication interface module (135).

The bandwidth table (133) is used to store information relating to its communication links and the bandwidth demanded and allocated. Such information includes link identification, type of link (whether it is a parent link, child link or an access link), current bandwidth of the link, node identification of its child nodes and/or parent node, aggregated number of access from its child nodes, bandwidth demand and aggregated bandwidth demand from its child nodes, and bandwidth allocated to its access and child nodes. Table 1 below shows an example of a bandwidth table for node B (120b) of FIG. 1.

Table 1

The bandwidth controller module (134) is used to configure its links to enforce the bandwidth allocated for each child node or wireless devices. The bandwidth controller module (134) is connected to the bandwidth allocation module (132) and to the links connected to the current node. The communication interface module (135) is used as an interface for communicating with other resource agents (130) of its parent node and child nodes. Referring now to FIG. 3, there is shown a flowchart of a method for operating the system (100) as shown in FIG. 1. Initially, as in step 201 , each resource agent acquires information relating to its node's links and/or access. Such information includes link identification, type of link (whether it is a parent link, child link or an access link), current bandwidth of the link, and node identification of its child nodes and/or parent node. The bandwidth table (133) is updated with such information.

In step 202, the bandwidth request module (131) of the resource agent (130) aggregates bandwidth demands from its access link or child nodes and thereon, sends a request to its parent node's resource agent through the communication interface module (135). This step is repeated on hop-by-hop basis from nodes (120) at bottom of tree up to the gateway (110).

Next, as in step 203, the bandwidth allocation module (132) of the resource agent (130) allocates bandwidth to its access link and child node(s) starting from the gateway (110) down to the nodes (120) at bottom or lowest tier of the network on hop-by-hop basis.

In step 204, the bandwidth allocation module (132) of the resource agent (130) instructs the bandwidth controller module (134) to configure its link to enforce the bandwidth allocated.

Thereon, the resource agent (130) monitors and detects changes in its child nodes. If there is a change in its child links, the resource agent updates its bandwidth table (133) and thereon, returns to step 202 for bandwidth aggregation and allocation (decision 205, and steps 206).

However, if there is no change in its child links, the resource agent (130) monitors and detects changes in its access links. If there is a change in its access links, the resource agent (130) updates its bandwidth table (133) and thereon, returns to step 202 for bandwidth aggregation and allocation (decisions 205 and 207; step 208). Otherwise, the resource agent (130) maintains the bandwidth allocation as it is if there is no change in its child links. Referring now to FIG. 4, there is shown a flowchart of a method for aggregating bandwidth demand and generating bandwidth request as in step 202 of FIG. 3. Initially, as in step 301, a bandwidth request module (131) of a resource agent acquires its node's bandwidth demand and its child node's bandwidth demand. Those bandwidth demands are aggregated to determine the total amount of bandwidth to be requested from its parent node. Thereon, the bandwidth request module (131) determines whether the parent node has the capacity to provide the total amount of bandwidth requested. The link state of the communication channel between child node and parent node can be obtained from MAC layer or by using generic algorithm recommended by IEEE 802.11s. As this information is stored on both child node and parent node, hence it is not required to be relayed between those nodes.

If the parent node is able to provide the total amount of bandwidth requested, the total amount of aggregated bandwidth demand is requested (decision 302, step 303). Otherwise, the maximum amount of bandwidth that can be provided by the parent node is requested (decision 302, step 304). For instance, node E (120e) and node F (120f) of the system (100) as shown in FIG. 1 sends a bandwidth request message to its parent node B (120b) requesting bandwidth of 3Mpbs and 1Mbps to be allocated respectively. Assuming that the link between node B (120b) and node E (120e) has a bandwidth capacity of 4Mbps and the link between node B (120b) and node F (120f) has a bandwidth capacity of 8 Mbps, the bandwidth demands for both nodes can be accommodated by the respectively links to their parent Node B ( 20b). As for node B (120b), the aggregated demand is summed up to a total of 7Mbps which include its own bandwidth demand. Since the link capacity to its parent node A (120a) is only 2Mbps, node B (120b) sends a bandwidth request message of 2Mbps to node A (120a) instead of 7Mbps.

In step 305, the bandwidth request module (131) generates a bandwidth request message and sends it to its parent node through the communication interface module (135). The bandwidth request message includes its node identification, bandwidth requested, aggregated number of link and an extra field which comprises of information for supporting additional bandwidth allocation decision such as the original amount of bandwidth demanded by its child nodes and also their child nodes. FIG. 6 depicts a format of the bandwidth request message. Referring now to FIG. 5, there is shown a flowchart of a method for allocating bandwidth as in step 203 of FIG. 3. Initially, as in decision 401, a bandwidth allocation module (132) of a resource agent (130) compares its requested bandwidth with the total amount bandwidth available to it by the parent node or gateway (110).

If the requested bandwidth is lower than or equal to the bandwidth available, the bandwidth allocation module (132) allocates the bandwidth requested for its own node and its child node as in step 402.

If the requested bandwidth is higher than the available bandwidth, the bandwidth allocation module (132) determines whether there is a child node in its link. If there is no child node, then the bandwidth allocation module (132) allocates the available bandwidth for its access links (decision 403 and step 404). Otherwise, the bandwidth allocation module (132) computes a fair sharing value and left over value to determine the bandwidth allocation for its child nodes and access links (decision 403 and step 405). The fair sharing value is computed by using the formula below: Fair sharing value = Available bandwidth / (total child nodes of total depth + 1 ). On the other hand, the left over value is computed by using the formula below: Left over value = Available bandwidth - Total bandwidth request of all child nodes.

Thereon, the fair sharing value and left over value is compared and the larger value between those two values is provided as the bandwidth allocated for its own node (step 406). As an example by referring to FIG. 1 , assume that the bandwidth requested by node B (120b), node E (120e) and node F (120f) is 3Mbps, 2Mpbs and 5Mbps respectively and the available bandwidth for node B (120b) is 7Mbps, the bandwidth allocation module (132) computes fair sharing value and left over value. The fair sharing value is computed as 2.33Mbps by dividing the available bandwidth 7Mbps with the total amount of child nodes of all depths plus one which is 3. The left over value is computed as 0 by deducting all requests made by its child nodes from the available bandwidth. Since the fair sharing value is larger than the left over value, the bandwidth allocation module (132) of the resource agent (130) of node B (120b) allocates 2.33Mbps from the available bandwidth for its own node.

In step 407, the bandwidth allocation module (132) computes a base unit by dividing the remaining bandwidth with the total bandwidth requested from all child nodes. The formula for computing the base unit is provided below:

Base unit = Remaining Bandwidth / Total bandwidth requested from all child nodes. In step 408, the bandwidth allocation module (132) allocates the remaining bandwidth for each of its child nodes by multiplying the requested bandwidth of the child node with the computed base unit. As an example by referring to FIG. 1, assume that the bandwidth requested by node E (120e) and node F (120f) is 2Mpbs and 5Mbps respectively while the remaining bandwidth of 4.67Mbps is allocated to node E (120e) and node F (120f), the base unit is computed by the bandwidth allocation module (132) of the resource agent (130) of node B (120b). The base unit of 0.67 is obtained by dividing the remaining bandwidth with the total bandwidth requested from all child nodes. Thereon, the allocated bandwidth for node E (120e) and node F (120f) can be determined by multiplying the requested bandwidth of the child node with the computed base unit of 0.67. Therefore, node E (120e) is allocated with 1.34Mbps and node F (120f) is allocated with 3.35Mbps.

Next, as in step 409, the bandwidth allocation module (132) generates and sends a bandwidth allocation message to its child node through the communication interface module (135). The bandwidth allocation message is to inform them regarding the amount of bandwidth made available to them. The bandwidth allocation message includes node identification and bandwidth allocated. FIG. 7 depicts a format of the bandwidth allocation message. While embodiments of the invention have been illustrated and described, it is not intended that these embodiments illustrated and describe all possible forms of the invention. Rather, the words used in the specifications are words of description rather than limitation and various changes may be made without departing from the scope of the invention.