FIELD OF THE INVENTION
The present invention relates to an architecture and corresponding method for wireless mesh that solves channel allocation problem irrespective of mesh topology and also relates to novel approach of local backhauling for wireless mesh networks.
BACKGROUND OF THE INVENTION AND PRIOR ART
Despite considerable research on 802.11 multihop wireless mesh networks (WMN), the scope for efficient utilization of electro magnetic spectrum remains. Because of this reason WMN is not able to match the wired network in terms of bandwidth. High speed broadband connection with seamless handoff and handover is a limitation for 3G and 4G wireless systems.
The solution provided in the present invention has tackled the problem of channel assignment in an entirely different way. The solution has reduced the need of radio spectrum to 'use only when necessary' concept. This has not only simplified the channel assignment problem but also has paved way for a simplified representation of the mesh. It is already shown by Francis De Costa [8], Raniwala et. al. [7], [10], Arindam et. al. [11] and others that efficiency of WMN increases when changed from single radio to multi radio. Raniwala has further solved the channel assignment problem by proposing multiple NIC, Hyacinth architecture and load balancing method.
Overall most of the previous work remains focused on issues such as various channel utilization methods, interference management and better routing protocols. Providing a local backhaul for wireless mesh nodes has received no attention at all. Broadband on powerline (BPL) has gained much popularity after its EMC problem was resolved. BPL can be a potential alternative to ADSL/DSL but can in no way provide the mobility of WMN. However its widespread infrastructure can synergize with WMN. WMN comprises of mesh access points, which are basically pole top devices. This makes them easier to integrate with the powerline due to their deployment in the same physical space.

Problems in existing methods are explained below
A. Channel Assignment Problem
As per Arindam K Das et al. [11] and Raniwala [7], [10] static channel assignment for an 802.11 mesh pertains to allocation of channels to mesh nodes with one or more radio interfaces such that i. Maximize the number of simultaneous transmissions.
ii. Minimize the size of a co-channel interference set
iii. Assign the channels such that load is balanced i.e.
prefer to assign dedicated radio channels over more traffic burdened links whereas lightly loaded links can be shared between the users. Eg. in figure 1. The graph purging method presented in next sections reduces the number of nodes communicating on wireless link thereby simplifying channel allocation method. This is further discussed in section IX A
B. Computation Cost of Routing Path
The routing method requires the calculation of minimum path to reach gateway. Most popular is the minimum spanning tree (MST) algorithm. With the increase in size of the mesh and in the number of hops, spanning tree a--d shortest path calculation gets intensive. The "Graph Purging Method" reduces the size of graph thereby reducing the cost of computing the MST. This is further discussed in section IX B.
C. Performance Degradation over Multiple Hops Problem*
Bandwidth degradation in a Wireless mesh occurs at the rate of 1 /2": n -7 no. of hops [8]. The local backhaul frees the radio links between the nodes thereby conserving bandwidth. The "Graph Purging Method" simplifies the network and reduces the number of hops required to reach the gateway. This is discussed under section IX C
D. Seamless Handoff and Handover Problem
Seamless handoff and handover is a challenging task to provide mobility to end users without being disconnected. This becomes difficult due to the channel assignment problem and constraints posed by the channel assignment method. Further complications

arise due to broadcast packets concerning mobility of the subscriber stations. Using the local backhaul, it is possible to position routers such that the handoff mechanism is administrated locally. This minimizes the need for broadcasting location of end user. This is further discussed subsequently.
The present invention makes use of BPL technology in WMNs to reduce traffic load on radio channels thereby improving the mesh performance. It has been proved in the related research that efficiency of WMN Ciln be improved by reducing the number of radio links. The present invention provides a hybrid architecture wherein a part of the wireless traffic gets offloaded to the local backhaul. The backhaul is also used to localize the handoff and handover procedures as well as reduce the number of hops to reach the gateway.
In wireless mesh there are always some nodes - mostly the ones nearer to gateway which face heavy traffic, also there are many other nodes which might be communicating for triple play voice, video and data- example video conferencing between two nodes. For these wired backhaul availability becomes a boon. As Powerline used in the present invention keeps on popping up all over the mesh we can utilize it as much as possible to connect wireless nodes thus providing high bandwidth and gateway connectivity at the same time.
References
[1] Oleksandr Grygorash, Van Zhou and Zach Jorgensen, "Minimum Spanning Tree Based Clustering Algorithms," Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAr06), pp. 73-81, November 2006.
[2] Jun Han, Zhaohao Sun, Jinpeng Huai, and Xian Li, "An Efficient Node Partitioning Algorithm for the Capacitated Minimum Spanning Tree Problem," lEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), pp. 575-580, July 2007
[3] L.Lovasz, "On decompositions of graphs," Stud. ScL Math. Hung., voU, pp. 237-238,
1966.
[4] P. Gupta and P.R. Kumar, "The capacity of wireless networks," IEEE Trans. Inform.
Theory, vol. 46, no. 2, pp. 388-404, 2000.

[5] Barry Liner, Donald Neilson and Fouad Tobagi, " Issues in packet radio network
design," Proceedings of the IEEE, vol. 75, no. 1, pp. 6-20, January 1987.
[6] Fouad Tobagi, "Modelling and Performance analysis of multihop packet radio
networks," Proceedings of the IEEE, vol. 75, no. 1, pp. 135-155
[7] Ashish Raniwala, Kartik Gopalan and Tzi cker Chiueh, " Centralized channel
assignment and routing algorithms for multi-channel wireless mesh networls,"
SIGMOBILE Mobile computing Communications Review, Vol. 8, no. 2, pp. 50-65, 2004
[8] Mesh Dynamics; http://www.meshdvnamics.com/performanceanalvsis.html
[9] H.Hrasnica, R. Lehnert, Powerline Communications in Telecommunication Access
Area (Powerline Communications im TK-Zugangsbereich), VDE World
Microtechnologies Congress - MICRO, tee 2000 - ETG-Factagungund- Forum:
Verteilungsnetze im liberalisierten Markt - September 25-27, 2000 - Expo 2000,
Hannover, Germany.
[10] Ashish Raniwala and Tzi cker Chiueh, "Architecture and algorithms for an IEEE
802.II-based multi-channel wireless mesh network," Proc, Of IEEE INFOCOM, 2005.
[11] Arindam K. Das, Hamed M.K. Alazemi, Rajiv Vijayakumar, and Sumit Roy,
"Optimization models for fixed channel assignment in wireless mesh networks with
multiple radios," Proc. ofSECON, September 2005.
[12] DuffY, K. Leith, DJ. Li, T. Malone, D. ,"Modeling 802.11 mesh networks",
Communications Letters, IEEE Volume 10, Issue 8, page(s): 635- 637, Aug. 2006
OBJECTS OF THE INVENTION
The primary object of the present invention is to provide solution to the channel
assignment from a different perspective.
Yet another object of the present invention is to provide an architecture and method for
wireless mesh that solves the channel allocation problem irrespective of mesh topology.
Still another object of the present invention is to provide reduce the number of radio
channels and simplify the spanning tree needed for routing.
Still another object of the present invention is to provide novel approach of local
backhauling for wireless mesh networks.

STATEMENT OF THE INVENTION
Accordingly, the present invention provides for an architecture comprising integration of Powerline into wireless mesh network and a method for optimizing channel assignment and routing of a wireless mesh network by integrating Powerline into the wireless mesh network.
BRIEF DESCRIPTION OF ACCOMPANYING DRAWINGS
The invention is further described by means of example but not in any limitative sense
with reference to the accompanying drawings of which:
Figure 1 shows a hyacinth type mesh architecture consisting of multi channel wireless
mesh network.
Figure 2 shows architecture of figure 1 but with broadband powerline running through
the three nodes A, E and D which were earlier connected through radio link 4. Now not
only the radio link 4 is free but also it can be reallocated between A and G and G and F
instead of channel 3 thereby further minimizing the co-channel interference. Also
enables nodes A and E to communicate to multiple neighbors simultaneously.
Figure 3 shows BPL access network with wireless mesh access points.
Figure 4 shows undirected graph (G) with access channel Chi.
Figure 5 shows unidirected graph G representing access node with Rb and edge Ei
represents mesh like radio Ra
Figure 6 shows spanning tree for mobility derived from figure 5.
Figure 7 shows topology of the hybrid access with wireless mesh and powerline where
two vertices V4 and V5, overlap with powerline.
Figure 8 shows hybrid access network with three vertices V4, V5 and Ve.
Figure 8-1 shows graph obtained by purging the three nodes V4, V5 and Ye in figure 6.
Figure 8-2 shows spanning tree obtained by reducing purged graph of figure 8-1.
Figure 9 shows resultant minimized graph obtained by purging adjacent nodes of figure
3.

DETAILED DESCRIPTION OF THE INVENTION
In the foregoing specification, the invention has been described with reference to
specific exemplary embodiments thereof. It will, however, be evident that various
modifications and changes may be made thereto without departing from the broader
spirit and scope of the invention as set forth in the appended claims. Accordingly, the
specification and drawings are to be regarded in an illustrative rather than a restrictive
sense.
The primary embodiment of the present invention is an architecture comprising
integration of Powerline into wireless mesh network.
In yet another embodiment of the present invention, Powerline as a local backhaul is
integrated with strategically located mesh access points.
In still another embodiment of the present invention, the mesh node communicates with
its neighboring node using wireless if and only if no Powerline link is available between
them.
In still another embodiment of the present invention, the strategically located mesh points
preferably connected over the backhaul which are heavily loaded and are unable to
provide the required QoS.
In still another embodiment of the present invention, the architecture provides optimized
channel assignment and routing solution for wireless mesh networks independent of type
of mesh topology.
In still another embodiment of the present invention, the architecture comprises dual
radio link to enable each wireless mesh network to access broadband over both the
Powerline and the wireless mesh.
In still another embodiment of the present invention, plurality of mesh nodes is connected
to their neighbors over the Powerline interface.
In still another embodiment of the present invention, the nodes select either Powerline or
wireless interface for communication using mesh MAC layer.
Another important embodiment of the present invention is a method for optimizing
channel assignment and routing of a wireless mesh network by integrating Powerline into
the wireless mesh network.

In still another embodiment of the present invention, the method comprises acts of;
dividing mesh network into individual cell clusters as sub mesh networks; connecting
plurality of boundary nodes of the resulted sub mesh networks with power line backhaul;
collating the backhaul connected nodes into a single wireless node to optimize channel
assignment and routing for wireless mesh networks.
In still another embodiment of the present invention, the method is recursively repeated
until radio links of all the nodes connected by the backhaul are purged and the network
remains with only those nodes which are communicating over the wireless.
In still another embodiment of the present invention, the mesh node communicates with
its neighboring node using wireless if and only if no Powerline link available between
them.
In still another embodiment of the present invention, the optimized mesh is an
interconnection of sub-nets with star topology, with at least one collated node connected
to the local backhaul.
In still another embodiment of the present invention, the purged nodes control handoffs
without involving entire chain of the mesh nodes.
Network model and assumptions
As shown in Figure-1, WMN architecture consists of fixed wireless router nodes. These static nodes form a multihop ad hoc network. Each node in this multi channel WMN is equipped with multiple 802.11 compliant NIC, and a BPL interface.
Some of the mesh nodes are connected to their neighbors over the powerline interface. A mesh node communicates with its neighboring node using wireless if and only if there is no powerline link available between them. The Powerline as a local backhaul is integrated with strategically located mesh access points. Wherein the strategy used in locating mesh points preferably mesh points are connected over the backhaul which are heavily loaded and are unable to provide the required QoS. The mesh network can be of Hyacinth topology (Raniwala), urban grid type (Francis De Costa), the conventional star, ring or complete mesh. The solution is not dependent on any particular type of mesh topology.

The nodes run a mesh MAC layer which allows them to make a choice between powerline and wireless interfaces.
The mesh access points cater to the mobile clients (subscriber stations) similar to the 802.11 standard. The bandwidth of a single wireless channel is significantly lower than fixed line bandwidth i.e. BPL / ADSL / VDSL access data rate is much higher than mesh node data rate. For example Wifi mesh access node operates at 14 Mbps and BPL access systems operates at 200 to 224 Mbps. Further radio links can be substituted with Broadband Powerline wherever available. This architecture is depicted in figure-2.
It is shown that not only the channel allocation problem gets simplified but also more nodes can communicate with each other simultaneously without interference (using BPL). This is achieved by simply replacing the radio with powerline, i.e. even before
Graph Purging method
Consider the mesh network implementation in the last mile with dual link radio access
nodes - one for the mesh and other for the mobility. From the practical stand point, these
access nodes are pole top devices in the last mile. Each WMN node can have access to
BPL as well as to the wireless mesh with help of dual radio link. Figure-3 is physical
representation of the hybrid WiFi mesh network supported by Powerline backhaul. This
is modeled as a Graph G in the method.
The graph is divided into individual cell clusters Gj using the Min-cut Algorithm [1]. One
instance of this sub graph (cell cluster) is represented in figure 4. To explain the method
lets consider a cell cluster of six nodes with each node connected to three neighbors. The
network is modeled as a graph with six edges and seven nodes (Figure-4).
For the sake of mobility requirements invention make use of an undirected graph as each node has to do table management. This means that the span of the graph can be defined by the numbers of nodes.
V7 V4 Vs - forms a simple cell represented as Gi in G (refer list of symbols).
The spanning tree for mobility is shown in figure-6. [2], [3].So for simple mesh network
with three access channel, we need to have, for mobility, spanning tree (figure 6), for

mesh with 7 nodes, the subsequent sections explain how this graph is simplified using the concept of backhauling and purging. Later will discuss how channel assignment problem gets simplified.
Considering the assumptions mentioned earlier, about BPL access path, add a BPL backhaul line to the topology depicted in figure 4. This is shown in figure 7.
It can be seen in figure 7 that Power line passes through nodes V4 and Vs. Based on the fact that BPL bandwidth is very high as compared to the wireless bandwidth between V4 and Vs, these two nodes can be collated (call it as purging). Also, E7, El and E2 can be collated into one link and can be catered through one mesh channel. Next, let us analyze the simplification that can be achieved if V 4, V s and V 6 were connected using BPL.
In figure 8 the backhaul connects nodes V 4, V sand V 6. These three can be collated in to a single wireless node as three can communicate on the much higher bandwidth backhaul link Figure 8-1 shows the reduced graph. This purged graph is reduced to a spanning tree represented in figure 8-2 [l].This network has not only improved the bandwidth but also has introduced additional handover points. Rebuilding of a mesh network from this spanning tree, results in lowering the hop cost. The rebuilt mesh is represented in figure 8-1.
As discussed earlier, nodes V4, V5 and V6 are collated into one point, the links E1, E2, E3, E7 and Eg also get purged leading into one link or usage of only one channel for the mesh. In a similar manner as explained, if all adjacent channel pairs e.g. (V4, V5), (V3, V2) and (Vi, Ve) in figure 3 are tactically purged, then the total number of links get reduced to 50% of the original number. This leads to simplification of the mesh in figure 5 to the star topology, of figure 9.
This method is repeated for each of the cell clusters. Some of the boundary nodes of the resulting sub-mesh networks (which now have a star topology) will be connected to the power-line back haul.
This generates an opportunity for further collating these nodes across the sub-nets. This

procedure is repeated recursively till the radio links of all the nodes connected by backhaul are purged and a final graph remains with only those nodes which are communicating over wireless.

Improvement over channel bandwidth Estimated Bandwidth gain for complete mesh cell
Total channels required
N: no. ofnodes
Let, N' be the number of nodes in the mesh formed after adding the backhaul
It is imperative that N'« N
Total bands required in the new network = N' (N' -l)/2
For example if new network contains only 80% of the existing nodes communicating on
wireless, the gain will be

Impact on Problems Discussed in background of the invention
A. Channel Assignment Problem
As seen earlier in figures 1 and 2 the usage of radio links between nodes by connecting
them using powerline is reduced. This was just a preliminary derivation. After applying
the Graph purging method the number of nodes communicating over wireless are
reduced. Hence all the three components of channel assignment problem are simplified.
i. Lesser number of nodes communicate over wireless and thereby results in more
number of simultaneous transmission in the network
ii. More nodes communicating on powerline allows for lesser co-channel
interference and a smaller size of co-channel interference set iii. More burdened links can be strategically placed to coincide with the powerline.
B. Computation Cost of Routing Path

It proved in the graph purging method that the spanning tree from purged graph is much easier to calculate as compared to the spanning tree calculation from the normal mesh graph. The reduced mesh is an interconnection of sub-nets with star topology with at least one collated node connected to local backhaul. MST becomes trivial in case of a star topology. Any node can send data to the local edge router (the node connected to the powerline backhaul) in either zero or one hop. Using this premise, the routing path from each node to the edge router can be built recursively.
C. Performance Degradation over Multiple Hops Problem
Since local backhauls created and purged the nodes, the problem of performance degradation with increased distance from gateway gets eliminated. The packet can get routed over the wired backhaul instead of using radio links. Some of the nodes on the powerline backhaul can be designated as edge routers further reducing the hop count.
D. Seamless Handoff and Handover
Mobile stations moving between the purged nodes need not advertise their locations to gateways. Purged nodes (local edge routers) can administrate handoffs without involving the whole chain of mesh nodes. This not only reduces the routing information traffic but also provides for faster and more efficient handoffs. The inter-cell handoff within the cluster need not be advertised to the gateways.

List of Symbols

We Claim:
1. An architecture comprising integration of Powerline into wireless mesh network.
2. The architecture as claimed in claim 1, wherein the Powerline as a local backhaul is integrated with strategically located mesh access points.
3. The architecture as claimed in claim 1, wherein the mesh node communicates with its neighboring node using wireless if and only if no Powerline link is available between them.
4. The architecture as claimed in claim 1, wherein the strategically located mesh points preferably connected over the backhaul which are heavily loaded and are unable to provide the required QoS.
5. The architecture as claimed in claim 1, wherein the architecture provides optimized channel assignment and routing solution for wireless mesh networks independent of type of mesh topology.
6. The architecture as claimed in claim 1, wherein the architecture comprises dual radio link to enable each wireless mesh network to access broadband over both the Powerline and the wireless mesh.
7. The architecture as claimed in claim 1, wherein plurality of mesh nodes is connected to their neighbors over the Powerline interface.
8. The architecture as claimed in claim 1, wherein the nodes select either Powerline or wireless interface for communication using mesh MAC layer.
9. A method for optimizing channel assignment and routing of a wireless mesh network by integrating Powerline into the wireless mesh network.
10. The method as claimed in claim 9, wherein the method comprises acts of;
i. dividing mesh network into individual cell clusters as sub mesh networks;
ii. connecting plurality of boundary nodes of the resulted sub mesh networks
with power line backhaul; iii. collating the backhaul connected nodes into a single wireless node to
optimize channel assignment and routing for wireless mesh networks.

11. The method as claimed in claim 10, wherein the method is recursively repeated until
radio links of all the nodes connected by the backhaul are purged and the network
remains with only those nodes which are communicating over the wireless.
12. The method as claimed in claim 9, wherein the mesh node communicates with its
neighboring node using wireless if and only if no Powerline link available between
them.
13. The method as claimed in claim 9, wherein the optimized mesh is an interconnection
of sub-nets with star topology, with at least one collated node connected to the local
backhaul.
14. The method as claimed in claim 9, wherein the purged nodes control handoffs without
involving entire chain of the mesh nodes.
15. An architecture comprising integration of Powerline into wireless mesh network and
A method for optimizing channel assignment and routing of a wireless mesh network
is substantially as herein above described with reference to the accompanying
drawings and examples.