METHOD FOR A PLACEMENT OF INTERNET GATEWAY (IGW) IN A BACKBONE WIRELESS MESH NETWORKS (BWMNS)

Abstract

The present innovation relates to a method for a placement of Internet Gateway (IGW) in a Backbone Wireless Mesh Networks (BWMNs) comprising: selecting the proper IGW (100); calculating the largest path the one degree nodes can reach with delay constraint (200); assigning Web Mesh Routers (WMRs) nodes to the identified IGW (300); forming a cluster with the largest degree node is the identified IGW (400); recalculating the position of IGW for intra-load balancing (500); assigning the node that has the maximum load radio to be the new IGW of the cluster (600); updating the rest of BWMN nodes (700); and forming the next clusters until no more WMR left (800). The present invention provides IGWs placement in the design phase while satisfying load balancing among IGWs and WMRs and under QoS constraints. The balancing acts encompass balancing over the load among IGWs of the entire BWMN and balancing over the load among WMRs of the entire BWMN.

Claims

1. A method for a placement of Internet Gateway (IGW) in a Backbone Wireless Mesh Networks (BWMNs) comprising: selecting the proper IGW by looking for one degree nodes (100); calculating the largest path the one degree nodes can reach with delay constraint (200); assigning Wireless Mesh Routers (WMRs) nodes to the identified IGW (300); forming a cluster with the largest degree node is the identified IGW (400); recalculating the position of IGW for intra-load balancing by looking for the total load radio for each WMR in the cluster including the identified IGW (500); assigning the node that has the maximum load radio to be the new IGW of the cluster (600); updating the rest of BWMN nodes by removing the identified IGW and its member set and their links from other nodes outside the boundary of the cluster from adjacency matrix (700); and forming the next clusters until no more WMR left (800).

2. The method for a placement of Internet Gateway (IGW) in a Backbone Wireless Mesh Networks (BWMNs) as claimed in claim 1, wherein the step of selecting the proper IGW by looking for one degree nodes (100) further comprising selecting the largest degree node to be the IGW (100A) if the network registers no one degree nodes.

3. The method for a placement of Internet Gateway (IGW) in a Backbone Wireless Mesh Networks (BWMNs) as claimed in claim 1, wherein the step of selecting the proper IGW by looking for one degree nodes (100) further comprising selecting the largest degree node to be the IGW (100B) if the network registers a plurality of nodes having the same delay hops.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] The present invention will be fully understood from the detailed description given herein below and the accompanying drawings as follows:

[0017] FIG. 1 illustrates a flowchart of the method of the present invention.

[0018] FIG. 2 illustrates algorithms which are involved in the method of the present invention.

[0019] FIG. 3 illustrates exemplary model of implementation of the method of the present invention.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

[0020] Generally, the present invention relates to a method for a placement of Internet Gateway (IGW) in a Backbone Wireless Mesh Networks (BWMNs) comprising: selecting the proper IGW by looking for one degree nodes (100); calculating the largest path the one degree nodes can reach with delay constraint (200); assigning WMRs to the identified IGW (300); forming a cluster with the largest degree node is the identified IGW (400); recalculating the position of IGW for intra-load balancing by looking for the total load radio for each WMR in the cluster including the identified IGW (500); assigning the node that has the maximum load radio to be the new IGW of the cluster (600); updating the rest of BWMN nodes by removing the identified IGW and its member set and their links from other nodes outside the boundary of the cluster from adjacency matrix (700); and forming the next clusters until no more WMR left (800). This provision is illustrated in FIG. 1. In the case if there is no one degree nodes registered in the network, or the network registers a plurality of nodes having the same delay hops, then the step (100) further comprising selecting the largest degree node to be the IGW (100A), (100B).

[0021] BWMN design starts by collecting some information such as number of nodes, connection radius and minimum distance, location size, and Quality of Service (QoS) parameters to generate the network graph as an adjacency matrix. All of these information act as inputs to proposed heuristic IGW placement algorithm of the present invention and the outputs are of the form number of IGWs and their clusters, intra-load balance ratio, Inter-load balance ratio, total load-balance ratio, largest IGW-WMR hop, and IGW-IGW hop.

[0022] As in FIG. 2, load-balanced algorithm solves the IGW placement problem by iteratively 5 and incrementally identifying IGWs and assigns WMRs to identified IGWs considering QoS constraints based on the degree of nodes and their locations in the network model, then reallocating the IGWs within their clusters depending on the delay hops and relay links (i.e. balancing the intra-load), finally balancing the inter-load of WMRs assigned to each identified IGW. Algorithm 1 shows an iterative behavior, such that in each iteration, it identifies an IGW 10 from the current unassigned WMRs using IGW_selection algorithm, which is provided in Algorithm 2. Then forming IGW cluster by assigning WMRs to the identified IGW using clustering algorithm, which is provided in Algorithm 3. After that, the Re-balancing algorithm in which is provided in Algorithm 4 reallocates the IGW for load balancing task. Finally, the system updates the adjacency matrix by removing the identified IGW and its WMRs. It continues to do so until the adjacency matrix is empty.

IGW Selection Algorithm

[0023] The algorithm shown in Algorithm 2 looks for the node which one degree nodes visit 20 more, considering the delay and relay constraints to select it as an IGW, otherwise the largest degree node will be selected as IGW. This mechanism of selecting IGWs ensure avoiding zero degree nodes at early stages and achieving objective of placing IGW closest to each other.

WMRs Clustering Algorithm

[0024] Algorithm 3 assigns WMRs according to some ordered priorities; first priority is given to the location of nodes if they are closest to one degree nodes; the second priority is given for the largest degree nodes; and the last priority is given for smallest degree of nodes' neighbors, considering QoS constraints.

Re-Balancing Algorithm

[0025] The purpose of this step is to ensure achieving the objective of maximizing the load balancing among IGWs and WMRs by evenly distributing WMRs to their IGWs and evenly distributing WMRs within their clusters. Algorithm 4 re-balances the load of a cluster by reallocating IGW based on the number of WMRs, their delay hops, and relay links. Calculating the load ratio for each WMR in the cluster and the largest WMR load ratio will be the new IGW of the cluster. The cluster C is fully load-balanced if and only if v.sub.iC has the same upper limit hops to the IGW of that cluster.

[0026] The present invention is best described in exemplary networking model as follows.

[0027] We consider a sample network topology with 13 nodes and we set the values of delay, relay, and capacity to be D.sub.QoS3, R.sub.QoS2, and C.sub.QoS7 respectively. The first step of our proposed algorithm of the present invention is to select the proper IGW by looking for one degree nodes if they are exist (100). Then, calculating the largest path the one degree nodes can reach with delay constraint (200). As shown in FIGS. 3(a), 5,6, and 9 are one degree nodes (i.e. each one has one connection) so the longest path with delay length 3 the node 5 can pass through is [5,4,6]; [5,4,3,7]; and [5,4,3,2]. Also longest path with delay length 3 the node 6 can pass through is [6,4,5]; [6,4,3,7]; and [6,4,3,2]. Similarly the path of node 9 can pass through is [9,2,8,12]; [9,2,8,1]; [9,2,1,8]; [9,2,1,7]; [9,2,1,12]; [9,2,3,7]; and [9,2,3,4]. Therefore, the most visited nodes are 2, 3, 4, and 7, so the node 2 is selected as an IGW as the largest degree node than nodes 3, 4, and 7. The next step is to assign WMRs to the identified IGW (300). The node 9 is assigned first as the smallest degree node. For the same reason the node 3 is assigned to the IGW as the second WMR. The third node to assign is 4 although 7 has the same degree but the node 4 is the nearest to one degree nodes 5 and 6. Therefore, nodes 5 and 6 are selected following the same rules. Finally, no more nodes can be assigned to the IGW due to the constraint of relay, which is R.sub.QoS2. Therefore, the first cluster is formed with the node 2 as an IGW and a member set of {3,4,5,6,9} (400).

[0028] FIG. 3(b) shows the cluster boundary, disconnected links, and the member nodes of the cluster. The next step is recalculating the position of IGW for intra-load balancing by looking for the total load radio for each WMR in the cluster including its IGW (500). However the load-radio of nodes 2, 3, 4, 5, 6, 9 is 0.527, 0.583, 0.639, 0.430, 0.430, 0.389, respectively. Noticing clearly that the node 4 has the maximum load radio, thus the node 4 will be selected as the new IGW of the cluster as shown in FIG. 3(c) (600). However, this step guarantees balancing the load among WMRs in the cluster. The next step is to update the rest of BWMN nodes by removing the identified IGW and their member set [2,3,4,5,6,9] and their links from other nodes outside the boundary of the cluster from adjacency matrix (700). Similarly the next clusters will be formed until no more WMR left (800). FIG. 3(d) shows the final BWMN model with its clusters set.

[0029] Although the innovation has been described with reference to particular embodiment, it is to be understood that the embodiment is merely illustrative of the principles and applications of the present innovation. It is therefore to be understood that numerous modifications may be made to the illustrative embodiment that other arrangements may be devised without departing from the scope of the present innovation as defined by the appended claims.