FORM 2
The Patent Act 1970
(39 of 1970)
&
The Patent Rules, 2005

COMPLETE SPECIFICATION
(SEE SECTION 10 AND RULE 13)

TITLE OF THE INVENTION
“Resource allocation in wireless mesh networks over diverse and fragmented spectrum”
APPLICANTS:
Name Nationality Address
Alcatel Lucent France 3, avenue Octave Gréard 75007 Paris,
France.

The following specification particularly describes and ascertains the nature of this invention and the manner in which it is to be performed:-

TECHNICAL FIELD
[001] The present invention relates to wireless mesh networks and, more particularly, to allocating resources in wireless mesh networks.

BACKGROUND
[002] Wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways. Present day mechanisms employ WMN for communication extensively. As a result, considerable research has gone into theory and implementation of multi hop wireless mesh networks over the past decade. However, much of the efforts have been in designing mesh networks that operate over a homogenous and contiguous frequency band. Further, these mechanisms do not address the problem of propagation over non homogenous and diverse spread frequency spectrum.
[003] Recent technological developments have paved the way for design and development of mesh networks over spectrum that is neither homogenous nor contiguous due to large range of available spectrum. As a result, multi band WIMAX mesh networks, mesh networks over DTV whitespace, microwave mesh for backhauling and the like have been proposed. However, the above mechanisms do not allocate resources in case of diverse and fragmented spectrum. This is due to the fact that communication graph in a mesh network models the possible communicating neighbors of every node. In single band wireless network, it is reasonable to assume that the set of communicating neighbors of a node is ?xed, and the average data rate between a transmit-receive pair is constant (perhaps slowly varying with time). On the other hand, in wireless networks over diverse spectrum, this assumption does not hold good since propagation path loss critically depends on the frequency of operation, the communicating neighbors of a node and the data rate between two mesh nodes both depend on the frequency of operation of the node. This has implications on routing because, routing protocols not only have to choose the routes, but also the frequency of operation over every hop. Indeed, by operating at a lower frequency, a node can reach out to nodes further away. However, this mechanism would not be effective in the present day scenario of diverse spectrum. Hence, the aforementioned mechanisms do not take into account the diverse and fragmented nature of the spectrum.
[004] Further, present day mechanisms do not address the problem of interference of the nodes in the spectrum. The interference graph of a mesh network models the nodes that have transmissions interfering with each other and hence the respective nodes cannot transmit simultaneously. In single band wireless networks, with ?xed transmission power, interference graph is a ?xed graph that only depends on node locations. In networks with diverse spectrum, two nodes that interfere in one frequency band need not interfere in another frequency band. This has implications on MAC design and spectrum allocation to mesh nodes and hence would not prove to be effective. Frequency dependent communication graph and interference graph together have implications on cross-layer optimized routing, ?ow-control, and MAC.
[005] Further, there exists a large body of work on scheduling in mesh networks. Some of them consider single-radio single-channel networks with node-exclusive spectrum sharing and some consider single-radio single-channel with general interference constraints. Some recent works on resource allocation in multi-radio multi-channel mesh networks are also available in literature. There are schemes for joint routing, congestion control and resource allocation in multi-radio multi-band mesh. One of them considers the number of radios at each node to be equal to the number of links, which is not practical as there may be plurality of nodes and the node count may not be equal to the count of the links. Another solution gives a greedy scheme for channel allocation in multi-channel mesh and shows good performance through simulations. But none of the above considers the diverse characteristics of the available spectra and use a single communication and interference graph for the network. The above schemes for multi-radio multi-channel spectrum allocation treat all part of the spectra to be same. None of the above discussed schemes deal with frequency dependent spectrum allocation which incorporates the diverse nature of the available spectrum.
[006] Due to the aforementioned reasons present day mechanisms for resource allocation do not take into consideration the varying frequency distribution patterns over the bandwidths.

SUMMARY
[007] In view of the foregoing, an embodiment herein provides a system for allocation of resources in wireless mesh networks in a centralized scheme over a diverse and fragmented spectrum, the system comprising at least one gateway node, where the node comprises at least one means configured for fetching information related to available resources from a plurality of mesh nodes; generating groups for at least one selected band as per a pre defined criteria; choosing a group from the generated groups at random; choosing a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; allocating bandwidth for the link if the link satisfies the condition; and broadcasting bandwidth allocation information to plurality of the mesh nodes. The system is further configured for fetching the information from the plurality of mesh nodes, where the information comprises frequency bands available for allocation, range of frequencies over which the bands are spread, nodes are operating over the bands, number of links available on the bands, interference information on the links, load distribution in the bands. The system is further configured for generating the groups based on the criteria where the criteria comprises at least one of every link belongs to at least one the group; interfering links of the link belong to at most same group; and number of groups in every band is a polynomial in number of the nodes. The system is further configured for choosing a link from the group to determine the condition for maximum bandwidth allocation, where the condition checks for the performance of the link when the link is allocated the entire available bandwidth. The system is further configured for choosing a group leader from the groups, wherein the group leader is configured for choosing a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; and allocating bandwidth for the link if the link satisfies the condition.
[008] Disclosed herein is a method for allocation of resources in wireless mesh networks in a centralized scheme over a diverse and fragmented spectrum, the method comprising fetching information related to available resources from a plurality of mesh nodes; generating groups for at least one selected band as per a pre defined criteria; choosing a group from the generated groups at random; choosing a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; allocating bandwidth for the link if the link satisfies the condition; and broadcasting bandwidth allocation information to plurality of the mesh nodes. The method fetches the information from the plurality of mesh nodes, where the information comprises frequency bands available for allocation, range of frequencies over which the bands are spread, nodes are operating over the bands, number of links available on the bands, interference information on the links, load distribution in the bands. The method generates the groups based on the criteria where the criteria comprises at least one of every link belongs to at least one the group; iinterfering links of the link belong to at most same group; and number of groups in every band is a polynomial in number of the nodes. The method chooses the link from the group to determine the condition for maximum bandwidth allocation, where the condition checks for the performance of the link when the link is allocated the entire available bandwidth. The method chooses a group leader for the groups; wherein the group leader chooses a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; and allocates bandwidth for the link if the link satisfies the condition.
[009] Disclosed herein is a gateway node for allocation of resources in wireless mesh networks over a diverse and fragmented spectrum, the node comprising at least one means configured for fetching information related to available resources from a plurality of mesh nodes; generating groups for at least one selected band as per a pre defined criteria; choosing a group from the generated groups at random; choosing a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; allocating bandwidth for the link if the link satisfies the condition; and broadcasting bandwidth allocation information to plurality of the mesh nodes. The gateway node is further configured for fetching the information from the plurality of mesh nodes, where the information includes which frequency bands are available for allocation, the range of frequencies over which the bands are spread, which nodes are operating over the bands, number of links available on the bands, interference information on the links, load distribution in the bands. The gateway node is further configured for generating the groups based on the criteria where the criteria comprises at least one of every link belongs to at least one the group; interfering links of the link belong to at most same group; and number of groups in every band is a polynomial in number of the nodes. The gateway node is further configured for choosing the link from the group to determine the condition for maximum bandwidth allocation, where the condition checks for the performance of the link when the link is allocated entire available bandwidth. The gateway node is further configured for choosing a group leader from the groups, wherein the group leader is configured for choosing a link from the group to determine if a condition for maximum bandwidth allocation for the link is satisfied; and allocating bandwidth for the link if the link satisfies the condition.
[0010] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings.

BRIEF DESCRIPTION OF THE FIGURES
[0011] The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:
[0012] FIG. 1 illustrates architecture of a wireless mesh network, according to an embodiment as disclosed herein;
[0013] FIG. 2 is a gateway node, according to an embodiment as disclosed herein;
[0014] FIG. 3 is a flow diagram depicting resource allocation in wireless mesh networks for a centralized scheme, according to an embodiment as disclosed herein;
[0015] FIG. 4 is a flow diagram depicting resource allocation in wireless mesh networks for a distributed scheme, according to an embodiment as disclosed herein;
[0016] FIG.5a, 5b and 5c illustrate simulation results for average rate of allocation for different channels over different frequency bands, according to an embodiment as disclosed herein; and
[0017] FIG. 6a illustrates simulation results for average delay comparison under different scenarios, according to an embodiment as disclosed herein.

DETAILED DESCRIPTION OF EMBODIMENTS
[0018] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
[0019] The embodiments herein disclose a mechanism for allocation of resources in wireless mesh networks spread over diverse and fragmented spectrum by providing systems and methods thereof. Referring now to the drawings, and more particularly to FIGS. 1 through 6, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments.
[0020] A mechanism for allocation of resources in wireless mesh networks is disclosed. The mechanism allocates resources in wireless mesh networks wherein the operating frequency is diverse and fragmented. The mechanism discusses resource allocation for centralized and distributed schemes. In case of the centralized scheme, the mechanism comprises a gateway node that is provided with intelligence in order to determine the available frequency bands for operation over the diverse and fragmented spread spectrum. The gateway node contacts other mesh nodes/routers that are in its vicinity. The mesh nodes/routers provide information as to which of the frequencies are available for allocation, interference patterns and so on. The information is made available to the gateway node. The gateway node then determines the best bands available for allocation. The gateway node further chooses a band at random. Further, for the chosen band groups are generated. During the grouping process links are organized into groups. On performing grouping, resources are re-allocated to the groups and randomly chosen bands. In another embodiment, for a distributed scheme a group leader is chosen. This group leader then decides the best link for a group. Re-allocation of resources is performed for the groups and the chosen bands. Further, the performance is examined. In this manner, iterations are continued for re-allocation in bands until the performance of the bands is improved. Finally, the best possible allocation is performed in the diverse and fragmented frequency spectrum.
[0021] FIG. 1 illustrates architecture of a wireless mesh network, according to an embodiment as disclosed herein. The wireless mesh network comprises plurality of gateway nodes 102a, 102b, 102c and 102d, plurality of mesh nodes/routers 103a, 103b, and plurality of access points 104a, 104b and internet 101. The mesh network components are connected to the access points 104a, 104b for allocation of resources to clients. The internet 101 acts as a means for communication between the elements of the mesh network with the clients. The internet 101 connects to gateway nodes 102, mesh nodes 103 and access point 104. The internet 101 helps data flow between the components of the mesh network and the external world.
[0022] The gateway node 102a, 102b, 102c and 102d acts as the first point of contact to all the components of the mesh network. All messages and data flows through the gateway node 102 to other components of the mesh network. The gateway node 102 is provided with the intelligence to fetch information from other mesh network modules and allocate resources to the available clients. The gateway node 102 interfaces with the mesh nodes 103, access points 104 in order to determine the part of the spectrum that is available for allocation. The gateway node 102 contacts the mesh node 103 to fetch information related to the available frequency bands, the range of frequencies over which the bands are spread, which nodes are operating over the bands, number of links available on the bands, interference information on the links, load distribution in the bands and so on. On fetching the information, the gateway node 102 determines which bands are suitable for allocation. The gateway node 102 then chooses bands at random. From the chosen bands, grouping is performed. During the grouping process, the links available are formed into groups based on a pre defined criterion. In an embodiment, the criterion may be that every link must belong to at least one group, interfering links of any link belong to at most number of groups and the number of groups in each band must be equal to a polynomial in the number of nodes. On grouping, initialization is performed. Further, bands are chosen at random from the grouped bands and check for the maximum allocation condition for the links of the chosen band. If the link satisfies maximum allocation condition then the entire bandwidth is allocated to the link. If the condition is not satisfied the allocation to all other interfering links are cancelled. On similar lines, the best possible allocation is made for other bands chosen at random. Thus, the gateway node 102 ensures that the allocation is efficient even when the frequency spectrum is diverse and fragmented.
[0023] The mesh nodes 103 communicate with each other and use some sort of ad-hoc networking protocol to route messages amongst themselves without the need for a traditional, hierarchical routing model. The mesh nodes 103 also allow for nodes to join, move among, and drop out of the network without having to make administrative changes. The mesh node 103 provides information related to the available frequency bands, the range of frequencies over which the bands are spread, which nodes are operating over the bands, number of links available on the bands, interference information on the links, load distribution in the bands and so on. This information is sent to the gateway nodes 102. In an embodiment, the mesh nodes 103 also interact among other mesh nodes to upgrade network resource information within itself.
[0024] The access points 104 acts as a point of contact for the clients. Different clients communicate with the mesh network through the access point 104. Further, it is through the access points 104 that resource allocation to clients is done over the diverse and fragmented frequency spectrum.
[0025] FIG. 2 is a gateway node, according to an embodiment as disclosed herein. The gateway node 102 comprises of an interface 201, a signal processing unit 202, a storage unit 203 and an intelligent module 204. In addition, the gateway node 102 may also comprise of other elements, and thus the depicted modules do not aim to introduce any limitations to the gateway node. The gateway node 102 acts as the key component of the mesh network and houses all the intelligence within it.
[0026] The interface 201 provides a means for various mesh network components in order to interact with the gateway node 102. Mesh network components such as mesh nodes 103, access points 104 and the like interact with the gateway node 102 through the interface 201. The interface 201 connects to signal processing unit 202, storage unit 203, and intelligent module 204.
[0027] The signal processing unit 202 receives various processing instructions through the interface 201. The signal processing unit 202 performs analysis on the received instructions and contacts the intelligent module 204 for addressing the same. The signal processing unit 202 may also send signals to the modules of the gateway node 102 for performing the required processing.
[0028] The storage unit 203 is like a memory unit that stores different information or data needed by the intelligent module 204 for performing the required activity.
[0029] The intelligent module 204 is the key component of the gateway node 102 and is responsible for performing the resource allocation. The intelligent module 204 contacts mesh nodes 103 in order to fetch information on the bands available, the number of links in the band, range over which the bands are spread, the time slots at which specific bands are free and the like. Based on the obtained information the intelligent module 204 performs groupings of the bands. For every band, the intelligent module 204 chooses different links and forms groups. In an embodiment, the bands may be chosen at random.
[0030] FIG. 3 is a flow diagram depicting resource allocation in wireless mesh networks centralized scheme, according to an embodiment as disclosed herein. In case of the centralized scheme, the entire intelligence lies within the gateway node 102 and the gateway node 102 takes care of the allocation of links to different clients. The gateway node 102 is provided with the intelligence in order to allocate resources over the available diverse and fragmented spectrum. The embodiment herein is described with reference to single radio network but does not aim to limit the scope of the application for the single radio case. A band is chosen at random by the gateway node 102, for the chosen band grouping is performed (301). During grouping, the links corresponding to the bands are grouped. The grouping is performed such that a pre defined criterion is satisfied. The criterion may be stated as every link must belong to at least one group, interfering links of any link belong to at most number of groups and the number of groups in each band must be equal to a polynomial in the number of nodes. The grouping is required as a pre-processing step where we iteratively improve the quality of the spectrum allocation. The key idea behind this grouping is to treat links in a single group as one entity, so that, in each iteration of local search we can do spectrum reallocation to links in an entity in an optimal manner without affecting the allocation to too many other entities. Further, to be able to do an optimal allocation of spectrum to links in an entity or a group restricts a group to have some special structure, for example, cliques. Also, since we require that spectrum reallocation to links in a group does not affect too many other groups essentially imply that a group’s interfering links lie in a small number of groups.
[0031] In an embodiment, grouping may be performed in a number of ways. One is location-based grouping, in which if nodes are within interfering distance (for a frequency band) of each other then they are in the same group in that band. Similarly grouping of nodes can be done over all the bands. In another embodiment, a non-location based approach may be employed for grouping. In this case, a node and its all interfering neighbors are put into a group and this is continued until all nodes are exhausted. This is also done over all frequency bands. In both of the above methods, any link (generalized) with its head (transmitters) in a given node-group for a given band and having band of operation same as the band of the node-group, belongs to the link-group corresponding to the node-group.
[0032] For a frequency band m groups of links are denoted by , where k is an index for the groups in band m. Note that in the grouping procedures, for a given frequency band m, each group of links is associated with a unique group of nodes (transmitters). For a group associated nodes are denoted by .
[0033] Further, various parameter are initialized (302). Let bl(0) be the allocation to link l initially. Set bl(0):=0. Let Wv(0) be the total wl sl bl of all ingress and egress links of node. Clearly, Wv(0) = 0 initially.
[0034] Further, a band and group is chosen (303) at random. The band is the band that was grouped earlier. A link lmax is chosen (304) based on pre defined maximum link condition. This condition states that link lmax is the link which if allocated the entire band Bjc will have the maximum improvement. Further, note that allocating spectrum to lmax has multiple negative effects, i) There may be need to cancel allocations of head and tail of lmax and ii) Cancel allocation of any link (generalized) interfering with lmax. Note that for any l interfering with lmax, the communication between head and tail nodes of l can potentially happen on a different band other than band (lmax) and hence effect of (ii) is not predominant. So we consider the effect of (i) and find the best link lmax that gives maximum net gain when allocated the total spectrum of band jc,
[0035] As a result, the link that satisfies the condition below is chosen

[0036] Further, a check is made (305) if maximum condition is satisfied by the link. If an lmax which gives a positive value of the argument in previous equation is found, Bjc is assigned to lmax and all available bandwidths are assigned (307) to lmax. On the other hand, allocations of interfering links are cancelled (306). Further, the same process is carried out for other bands that are grouped and iterations are performed and the best possible allocations for every band are determined (308). The gateway node 102 then broadcasts (309) the information on re-allocation to other nodes and clients which are under the gateway node 102.
[0037] In an embodiment, the extension of the algorithm above to multi-radio network from single radio network is also possible. Grouping is done in the same way as discussed above. Instead of nodes radios are treated as individual entities and the same steps as previous are carried out with an additional constraint of ‘adjacent channel interference’. During an iteration of spectrum allocation, if a radio of a node is assigned to transmit (receive) on a band, any co-located radio (i.e., radio of the same node) has to cancel its reception (transmission) on any adjacent part of the spectrum to avoid adjacent channel interference. This effect of adjacent channel interference take care by doing,

[001] Here Adj(l) is the set of links that have co-located radios with link l and are adjacent channel interferers of link l. The various actions in method 300 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 3 may be omitted.
[0038] FIG. 4 is a flow diagram depicting resource allocation in wireless mesh networks distributed scheme, according to an embodiment as disclosed herein. In case of the distributed scheme, the function of the gateway node 102 is distributed among individual nodes. The individual nodes take care of re-allocation by employing a group leader. The group leader allocates links to different clients. The scheme takes care of resource allocation over the available diverse and fragmented spectrum. The embodiment herein is described with reference to single radio network but does not aim to limit the scope of the application for the single radio case. A band is chosen at random by the gateway node 102, for the chosen band grouping is performed (401). During grouping, the links corresponding to the bands are grouped. The grouping is performed such that a pre defined criterion is satisfied. The criterion may be stated as every link must belong to at least one group, interfering links of any link belong to at most number of groups and the number of groups in each band must be equal to a polynomial in the number of nodes. The grouping is required as a pre-processing step where we iteratively improve the quality of the spectrum allocation. The key idea behind this grouping is to treat links in a single group as one entity, so that, in each iteration of local search we can do spectrum reallocation to links in an entity in an optimal manner without affecting the allocation to too many other entities. Further, to be able to do an optimal allocation of spectrum to links in an entity or a group restricts a group to have some special structure, for example, cliques. Also, since we require that spectrum reallocation to links in a group does not affect too many other groups essentially imply that a group’s interfering links lie in a small number of groups.
[0039] In an embodiment, grouping may be performed in a number of ways. One is location-based grouping, in which if nodes are within interfering distance (for a frequency band) of each other then they are in the same group in that band. Similarly grouping of nodes can be done over all the bands. In another embodiment, a non-location based approach may be employed for grouping. In this case, a node and its all interfering neighbors are put into a group and this is continued until all nodes are exhausted. This is also done over all frequency bands. In both of the above methods, any link (generalized) with its head (transmitters) in a given node-group for a given band and having band of operation same as the band of the node-group, belongs to the link-group corresponding to the node-group.
[0040] For a frequency band m groups of links are denoted by , where k is an index for the groups in band m. Note that in the grouping procedures, for a given frequency band m, each group of links is associated with a unique group of nodes (transmitters). For a group associated nodes are denoted by .
[0041] Further, various parameter are initialized (402). Let bl(0) be the allocation to link l initially. Set bl(0):=0. Let Wv(0) be the total wl sl bl of all ingress and egress links of node. Clearly, Wv(0) = 0 initially.
[0042] Further, a band and group is chosen (403) at random. The band is the band that was grouped earlier. For the chosen group, a group leader is chosen (404). The group leader resides within every node of the network. Due to this, the information on broadcasting need not be broadcasted to the individual nodes. The group leader is then responsible for performing re-allocation of the resources. The group leader then chooses the best link corresponding to the band. The link lmax is chosen (405) by the group leader based on pre defined maximum link condition. This condition states that link lmax is the link which if allocated the entire band Bjc will have the maximum improvement. Further, note that allocating spectrum to lmax has multiple negative effects, i) There may be need to cancel allocations of head and tail of lmax and ii) Cancel allocation of any link (generalized) interfering with lmax. Note that for any l interfering with lmax, the communication between head and tail nodes of l can potentially happen on a different band other than band (lmax) and hence effect of (ii) is not predominant. So we consider the effect of (i) and find the best link lmax that gives maximum net gain when allocated the total spectrum of band jc,
[0043] As a result, the link that satisfies the condition below is chosen

[0044] Further, a check is made (406) if maximum condition is satisfied by the link. If an lmax which gives a positive value of the argument in previous equation is found, Bjc is assigned to lmax and all available bandwidths are assigned (407) to lmax. On the other hand, allocations of interfering links are cancelled (408). Further, the same process is carried out for other bands that are grouped and iterations are performed and the best possible allocations for every band are determined by the group leader (409). In this case, the nodes themselves comprise of group leaders and hence the re-allocation information needed not be sent (410) to the nodes again.
[0045] In an embodiment, the extension of the algorithm above to multi-radio network from single radio network is also possible. Grouping is done in the same way as discussed above. Instead of nodes radios are treated as individual entities and the same steps as previous are carried out with an additional constraint of ‘adjacent channel interference’. During an iteration of spectrum allocation, if a radio of a node is assigned to transmit (receive) on a band, any co-located radio (i.e., radio of the same node) has to cancel its reception (transmission) on any adjacent part of the spectrum to avoid adjacent channel interference. This effect of adjacent channel interference take care by doing,

[002] Here Adj(l) is the set of links that have co-located radios with link l and are adjacent channel interferers of link l. The various actions in method 400 may be performed in the order presented, in a different order or simultaneously. Further, in some embodiments, some actions listed in FIG. 4 may be omitted.
[003] FIG.5a, 5b and 5c illustrate simulation results for average rate of allocation for different channels over different frequency bands, according to an embodiment as disclosed herein. In the simulation results discussed herein the available channel and radios per node are varied and the performance is observed. The channels are considered to be operating at 20 MHz. In this case, the results are compared for the average data rates obtained under our proposed centralized and distributed algorithms and the well known greedy algorithm. Fig 5a, represents the scenario where operating spectrum is made of three channels in 2.4 GHz and one in 900 MHz ISM band. Further, the figure depicts the behavior of the algorithm for centralized, distributed and greedy schemes. It is observed that the average data rate is much better with the proposed centralized and distributed schemes as compared to the greedy scheme. Further, 5a shows 2.4x average improvement given by distributed scheme over greedy scheme for 2-3 radios/node.
[004] Similarly ?g 5b shows the simulation results when available spectrum consists of two channels each in 2.5and 3.5 GHz unlicensed WiMAX band. The figure depicts the behavior of the algorithm for centralized, distributed and greedy schemes. In addition, it is observed that the average data rate is much better with the proposed centralized and distributed schemes as compared to the greedy scheme. Figure 5b shows 2.6X improvement. The proposed algorithm takes into account the frequency dependent PHY rate and interference in the network unlike the greedy scheme. This is the key reason for its better performance.
[005] Fig 5c is for simulations done over a diverse set of channels, one in 900 MHz, two 2.4 GHz and one in 5.8 GHz ISM band. The figure depicts the behavior of the algorithm for centralized, distributed and greedy schemes. It is observed that the average data rate is much better with the proposed centralized and distributed schemes as compared to the greedy scheme. In fig 5c improvement of 4.8x for 2-3 radios/node is observed. Note that diversity of operating spectrum is in increasing order for the ?gures.
[006] FIG. 6a illustrates simulation results for average delay comparison under different scenarios, according to an embodiment as disclosed herein. The simulation results discussed herein are for delay performance comparison for proposed centralized, distributed and greedy schemes. Further, from the comparison of average end to end delay in the network under different settings it is observed that delay performance of our proposed algorithm is comparable to greedy scheme under cross-layer optimization framework and proportional fairness.
[007] In an embodiment, although there are methods to tackle the resource allocation problem in multi-radio multi-channel mesh networks, none of them considers a network over diverse spectra. The proposed solution is feasible (linear in size of the network) and has a provable performance guaranty for multi-radio multi-band network over diverse spectra. For femto-backhaul, home-networking (streaming of media, data connection, smart home), rural broadband etc. wireless mesh is a highly potent and viable option. But due to over-crowding of ISM bands and scarcity of ‘good’ available spectra, in future most of these networks will have to operate on diverse and fragmented spectra and method may be very useful.
[008] In future with the upcoming of smart city applications where every utility will be monitored remotely through wireless connection, a high performance mesh will be a need of time. In such case, the method will come handy to operate over diverse spectra for avoiding interference in ISM bands.
[009] Further, the proposed scheme is capable of operating in joint routing, congestion control and resource allocation framework. The advantages of the proposed scheme are as follows. The scheme is frequency aware and hence can adapt to the diverse spectrum characteristics, scheme gives much better throughput performance (2.5x-5x). Further, the proposed algorithm performs much better compared to the greedy scheme as the diversity in the spectrum increases. Delay performance is comparable, sometimes better.
[0046] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the network elements. The network elements shown in Fig. 1 and 2 include blocks which can be at least one of a hardware device, or a combination of hardware device and software module.
[0047] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the claims as described herein.

WE CLAIM :¬-
1. A system for allocation of resources in wireless mesh networks in a centralized scheme over a diverse and fragmented spectrum, said system comprising
at least one gateway node, where said node comprises at least one means configured for
fetching information related to available resources from a plurality of mesh nodes;
generating groups for at least one selected band as per a pre defined criteria;
choosing a group from said generated groups at random;
choosing a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied;
allocating bandwidth for said link if said link satisfies said condition; and
broadcasting bandwidth allocation information to plurality of said mesh nodes.

2. The system, as claimed in claim 1, wherein said system is further configured for fetching said information from said plurality of mesh nodes, where said information comprises frequency bands available for allocation, range of frequencies over which said bands are spread, nodes are operating over said bands, number of links available on said bands, interference information on said links, load distribution in said bands.

3. The system, as claimed in claim 1, wherein said system is further configured for generating said groups based on said criteria where said criteria comprises at least one of
every link belongs to at least one said group;
interfering links of said link belong to at most same group; and
number of groups in every band is a polynomial in number of said nodes.

4. The system, as claimed in claim 1, wherein said system is further configured for choosing a link from said group to determine said condition for maximum bandwidth allocation, where said condition checks for the performance of said link when said link is allocated the entire available bandwidth.

5. The system, as claimed in claim 1, wherein said system is further configured for choosing a group leader from said groups, wherein said group leader is configured for
choosing a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied; and
allocating bandwidth for said link if said link satisfies said condition.

6. A method for allocation of resources in wireless mesh networks in a centralized scheme over a diverse and fragmented spectrum, said method comprising
fetching information related to available resources from a plurality of mesh nodes;
generating groups for at least one selected band as per a pre defined criteria;
choosing a group from said generated groups at random;
choosing a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied;
allocating bandwidth for said link if said link satisfies said condition; and
broadcasting bandwidth allocation information to plurality of said mesh nodes.

7. The method, as claimed in claim 6, wherein said method fetches said information from said plurality of mesh nodes, where said information comprises frequency bands available for allocation, range of frequencies over which said bands are spread, nodes are operating over said bands, number of links available on said bands, interference information on said links, load distribution in said bands.

8. The method, as claimed in claim 6, wherein said method generates said groups based on said criteria where said criteria comprises at least one of
every link belongs to at least one said group;
interfering links of said link belong to at most same group; and
number of groups in every band is a polynomial in number of said nodes.

9. The method, as claimed in claim 6, wherein said method chooses said link from said group to determine said condition for maximum bandwidth allocation, where said condition checks for the performance of said link when said link is allocated the entire available bandwidth.

10. The method, as claimed in claim 6, wherein said method chooses a group leader for said groups; wherein said group leader
chooses a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied; and
allocates bandwidth for said link if said link satisfies said condition.

11. A gateway node for allocation of resources in wireless mesh networks over a diverse and fragmented spectrum, said gateway node comprising at least one means configured for
fetching information related to available resources from a plurality of mesh nodes;
generating groups for at least one selected band as per a pre defined criteria;
choosing a group from said generated groups at random;
choosing a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied;
allocating bandwidth for said link if said link satisfies said condition; and
broadcasting bandwidth allocation information to plurality of said mesh nodes.

12. The gateway node, as claimed in claim 11, wherein said gateway node is further configured for fetching said information from said plurality of mesh nodes, where said information includes which frequency bands are available for allocation, the range of frequencies over which said bands are spread, which nodes are operating over said bands, number of links available on said bands, interference information on said links, load distribution in said bands.

13. The gateway node, as claimed in claim 11, wherein said gateway node is further configured for generating said groups based on said criteria where said criteria comprises at least one of
every link belongs to at least one said group;
interfering links of said link belong to at most same group; and
number of groups in every band is a polynomial in number of said nodes.

14. The gateway node, as claimed in claim 11, wherein said gateway node is further configured for choosing said link from said group to determine said condition for maximum bandwidth allocation, where said condition checks for the performance of said link when said link is allocated entire available bandwidth.

15. The gateway node, as claimed in claim 11, wherein said gateway node is further configured for choosing a group leader from said groups, wherein said group leader is configured for
choosing a link from said group to determine if a condition for maximum bandwidth allocation for said link is satisfied; and
allocating bandwidth for said link if said link satisfies said condition.

Dated 29th JUNE,2011


Dr. Kalyan Chakravarthy
Patent Agent

ABSTRACT
Resource allocation in wireless mesh networks over diverse and fragmented spectrum is disclosed. The present invention relates to wireless mesh networks and, more particularly, to allocating resources in wireless mesh networks. The mechanism employs a gateway node that allocates resources in wireless mesh networks wherein the operating frequency is diverse and fragmented. The gateway node contacts other mesh nodes/routers that are in its vicinity. The mesh nodes/routers provide information as to which of the frequencies are available for allocation, interference patterns and so on. The information is made available to the gateway node. The gateway node then determines the best bands available for allocation. Iterations are continued for re-allocation in bands until the performance of the bands is improved. Finally, the best possible allocation is performed in the diverse and fragmented frequency spectrum. FIG. 1