Patent Publication Number: US-7711371-B2

Title: Method and system for analysis and visualization of a wireless communications network

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to wireless communications systems and more specifically to analyzing and visualizing wireless mesh networks. 
     BACKGROUND 
     A Wireless Mesh Network is a collection of mesh nodes (that may include access points, client devices, and fixed or mobile transceivers, all of which will be referred to herein as APs) that are interconnected by wired or wireless links (mesh links) to form a web-like “mesh” communications network. A number of select APs that form the mesh also serve as Backhaul Anchored Nodes (BANs) that connect the mesh network through wired or wireless backhaul connections to the Internet. Data is communicated through the network from node to node, in “hops”, as it makes its way from a client of one mesh node to one or more clients of another mesh node in the network, or from such a client out to the Internet, or from the Internet back to one or more mesh node clients. 
     Multiple mesh hops, and therefore the services of many mesh nodes, are often required in order for data to reach a particular client. As a result, the overall performance of the network depends not only on the placement of each individual mesh node, but also on the placement of mesh nodes relative to each other and with respect to the environment. The inter-dependence of each mesh link and the overall performance of the network leads to a multitude of possible failure points. In addition, the designer must not neglect coverage of each individual AP to its respective clients. Wireless meshes are high bandwidth networks that are characterized by high traffic loads and high capacity. Wireless mesh networks service applications with stringent delay/jitter constraints, but which are typically distributed over geographical areas. Further complications arise from the fact that mesh network clients naturally exercise the network in varying scales of throughput with varying requirements for Quality of Service (QoS). In short, wireless mesh networks present all of the practical challenges of wired networks, and of non-mesh wireless networks, along with additional complications due to multiple-hop routing of data, and due to the typical physical scale of mesh network deployments. Consequently, a sophisticated design is critical for wireless mesh network performance. 
     In order to resolve such a complex problem, designers often have a set of rules or constraints to ensure that each AP operates correctly and that the mesh as a whole functions properly. For example, the designer might require that each AP must have a maximum of 3 node-to-node hops back to the BAN in order to satisfy a delay threshold. The problem is that correcting for one such basic design constraint might lead to other failures due to the complex relationships between mesh nodes. It is therefore crucial for the designer to envision and manipulate the relationships between changes in individual parameters and the performance of the entire mesh network. Furthermore, the relationship with each of the design constraints and how it affects the entire solution becomes increasingly complex with larger scale deployments. The designer must also consider that mesh networks are deployed across varying geographical areas littered with obstructions such as buildings, terrain, and foliage. Consideration of the location and properties of these obstructions is essential to understanding the performance of a mesh network. Thus, an optimal solution should empower the designer to discern the performance of the network, easily identify problems, and be able to resolve such problem efficiently regardless of the scale of the network and environment in which the network resides. 
     A solution demonstrating these qualities has not yet been disclosed by prior art. Accordingly there exists a need for a new method and system for analysis and visualization of a wireless communications network. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above needs are at least partially met through provision of the method and system for analysis and visualization of a wireless communications network described in the following detailed description, particularly when studied in conjunction with the drawings, wherein: 
         FIG. 1  shows an example method in accordance with an embodiment of the present invention. 
         FIG. 2  shows an example system exemplifying the operation of an embodiment of the present invention. 
         FIG. 3  shows an example system exemplifying the operation of an embodiment of the present invention. 
         FIG. 4  shows an example system exemplifying the operation of an embodiment of the present invention. 
     
    
    
     Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions and/or relative positioning of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of various embodiments of the present invention. Also, common but well-understood elements that are useful or necessary in a commercially feasible embodiment are often not depicted in order to facilitate a less obstructed view of these various embodiments of the present invention. It will further be appreciated that certain actions and/or steps may be described or depicted in a particular order of occurrence while those skilled in the art will understand that such specificity with respect to sequence is not actually required. It will also be understood that the terms and expressions used herein have the ordinary meaning as is accorded to such terms and expressions with respect to their corresponding respective areas of inquiry and study except where specific meanings have otherwise been set forth herein. 
     DETAILED DESCRIPTION 
     Generally speaking, pursuant to these various embodiments, a system and method for analysis of a wireless communications network is disclosed. A map of a physical environment integrating communications hardware for implementing a wireless communications network is defined. Client service requirements and regions for the wireless communications network are defined. Mesh point constraints and mesh linkage constraints for the wireless communications network are defined. The communications hardware is placed on the map at initial locations. Whether at least one of the defined mesh point constraints and mesh linkage constraints have been met by at least one mesh link between communications hardware based upon the initial locations of the communications hardware in the communications network is calculated. In one embodiment, the at least one calculation is displayed as a visualization on the defined map. 
     These and other benefits may become clearer upon making a thorough review and study of the following detailed description. Referring now to the drawings, and in particular to  FIG. 1 , a method for analysis and visualization of a wireless communications network is shown. 
     First, a map of the physical environment must be defined (step  102 ). In one embodiment, a method for generating a map of the physical environment is disclosed in U.S. Pat. No. 6,850,946 entitled “Method and System for a Building Database Manipulator,” which is hereby incorporated by reference and describes a site specific computer model. As described in the patent, the resulting map utilizes a specially formatted raster and/or vector database comprising lines and polygons that represent physical objects within the physical environment. The arrangement of lines and polygons in the database corresponds to physical objects in the environment. For example, a line or other shape in the database could represent a wall, a door, a tree, a building wall, or some other physical object in the physical environment. 
     From the standpoint of radio wave propagation, each obstruction/partition in a physical environment (i.e., each line or polygon in the drawing) has electromagnetic properties that affect a radio wave. When a radio wave signal intersects a physical surface, it interacts with the electromagnetic properties of the surface. A certain percentage of the radio wave reflects off of the surface and continues along an altered trajectory; a certain percentage of the radio wave penetrates through the surface and continues along its course; a certain percentage of the radio wave is scattered once it strikes the surface, etc. The electromagnetic properties assigned to the obstruction/partition define and model this interaction, and thus define the break down in percentages of the radio wave reacting in a given manner upon intersection. In terms of the physical environment map and the database representing the physical environment, each obstruction/partition has several parameters used to define its electromagnetic properties. For example, the attenuation factor of a partition determines the amount of power lost by a radio signal that penetrates through it; the reflectivity of a partition determines the portion of the radio signal reflected from it; and the surface roughness of a partition determines the portion of the radio signal that is scattered upon intersection. 
     Once the physical environment map has been defined, the designer identifies and specifies the location and type of all candidate APs (including access points, network routers, network bridges, network hubs, network switches, client devices, and other fixed or mobile transceivers) and, optionally, Backhaul Anchored Nodes (BANs, which are APs with a wired or wireless connection to a separate communications network and/or the Internet), both collectively termed communications hardware, within the physical environment map (step  104 ). In one embodiment, this step is performed via a point-and-click process by the user selecting desired communications hardware from a computer parts database and then visually positioning, and orienting the selected communications hardware within the physical environment map to form a complete wireless communications system. For example, the communications hardware may be placed in street lamps in the physical environment. Each AP or BAN may consist of one or more individual devices physically connected in a local network, constituting a single node in the broader wireless mesh network. Indeed one skilled in the art may appreciate that each AP, BAN, or other node in the wireless mesh network may itself consist of various hardware devices interconnected by another sub-network or super-network. In one embodiment of the invention, an embodiment of the computer parts database, referred to hereinafter as a parts list library, is more fully described in U.S. Pat. No. 6,493,679 entitled “Method and System for Managing a Real-Time Bill of Materials,” which is hereby incorporated by reference. 
     Further, the additional communications equipment necessary to interconnect and complete the wireless communications system may also be selected via the same process. For example, base station transceivers, cabling, connectors/splitters, amplifiers, antennas, and other RF hardware components are also preferably assembled using either a drag-and-drop or a pick-and-place technique and graphically displayed overlaid with the physical environment map. In one embodiment, the communications hardware and the additional communications equipment are associated with electromechanical information available from the parts list library that fully describes the component in terms of physical operating characteristics (e.g., the noise figure, frequency, radiation characteristics, etc.) which is used to calculate whether client and mesh requirements are met. In any case, the defined communications hardware (step  104 ) is integrated with the defined map (step  102 ) to create a site specific computer model of the wireless communications system. 
     Next, client service requirements and regions are defined (step  106 ) for the created site specific computer model of the wireless communications system. In one embodiment, such a step is performed by a point-and-click process to designate quality of service requirements necessary for a client of the wireless communications system. For example, the client may specify that the wireless communications system operate according to a certain coverage requirement (e.g. received radio signal power) and/or capacity requirement (e.g. sustained network data throughput). Further, the client may specify a certain delay threshold for the wireless communications network. In any event, the client may specify performance parameters such as a number of users of the wireless communications system, a type of traffic, a received signal strength indication, a signal interference ratio, a signal to noise ratio, throughput, etc. In one embodiment, such a step is additionally performed by a point-and-click process to designate the boundary of a region that encapsulates the area of interest within the created site specific computer model. In one embodiment, the region identified by the point-and-click process is a two-dimensional (2-D) plane or three-dimensional (3-D) surface within the site specific computer model where the site specific computer model is a two- or three dimensional representation of the physical environment. Once the region has been identified, the region may be automatically segmented into a grid of vertices where the grid has a size and spacing. 
     Next, mesh point constraints are defined (step  108 ). In one embodiment, such a step is performed by a point-and-click process to designate attributes relating to the communications hardware in the wireless communications system. For example, the wireless communications system may be required to operate with a certain number or a certain range of communications hardware. Such a constraint may be placed to ensure that the wireless communications system be within a certain budget. Other mesh point constraints that may be considered within such a step comprise transmitter, receiver, or transceiver characteristics of the communications hardware, speed of a backhaul connection available at a BAN, and maximum throughput per mesh link. Further mesh constraints comprise locations where the communications hardware can be located, e.g. on street lamps, and locations where the communications hardware can not be located, e.g. inside a concrete reinforced building. 
     Next, mesh linkage constraints are defined (step  110 ). In one embodiment, such a step is performed by a point-and-click process to designate constraints, routing rules, and mesh linkage rules necessary for the wireless communications system to operate properly. For example, the client may specify that there only be a specific number of hops between a mobile subscriber and a BAN. Further, the client may specify a number of redundant hops to a BAN. In any event, the client may specify other rules such as end-to-end latency, a method to choose routes given multiple path choices, etc. 
     In any case, once the requirements from steps  102 - 110  are defined, initial placement of APs (step  112 ) and initial placement of BANs (step  114 ) occurs automatically with respect to the defined locations from step  104 . In one embodiment, steps  112  and  114  are performed by a software algorithm for network design, which automatically selects preferred AP and BAN sites. In an alternative embodiment, the initial placement of APs (step  112 ) and of BANs (step  114 ) is simply performed by automatically placing APs at all available AP locations, and BANs at all available BAN locations. In yet another alternative embodiment, the initial placement of APs and BANs reflects the actual placements of nodes in a mesh network which has already been deployed using other methods, and which is being analyzed for improvement. 
     Next, calculations relating to client constraints, mesh linkage constraints, client service requirements, and mesh linkage are performed (steps  116 - 118 ). At step  116 , calculations relating to client service quality across the selected region are performed so that a visualization of the calculated service quality may be displayed to a user. At step  118 , calculations relating to mesh linkage quality and routing across all mesh points of interest are performed so that a visualization of the calculated mesh linkage quality and routing may be displayed to a user. In on embodiment, the visualization may be a color-coded lines or line thickness. For example, a red link could indicate a 2 Mbps mesh link and a green link could indicate a 54 Mbps mesh link. Similarly, a line of smaller thickness could indicate a mesh link that is performing at 2 Mbps and a much thicker line can indicate a link performance of 54 Mbps. The color code/line thickness can be based on any metric and might not necessarily be throughput. In any case, by displaying the visualization of the calculations, a user may easily determine that requirements from steps  102 - 110  are not met. 
     As can be understood, designing the wireless communications system to take into account the requirements from steps  102 - 110  is a difficult task. In one embodiment, the calculations performed (steps  116 ,  118 ) are facilitated by using graph theory and/or computationally efficient geometrical algorithms to provide real-time calculation and visualization of the wireless communications. 
     In such an embodiment, a fast graph theory algorithm that searches for connectivity based on simulated signal distribution on the physical map is used. The fast graph theory algorithm searches for a shortest path (also termed smallest number of hops) between the communications hardware, e.g. APs and BANs. In the graph, the mesh nodes are represented by graph vertices and the mesh links graph edges. From each BAN mesh node, there is a tree-of-shortest-path search with a BAN as the source (root). In one embodiment, a Dijkastra method is used for tree search as is well known in the art, e.g. see  Network Flow , by R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, 1993, Prentice-Hall. By using a data structure for graph vertices and edges, the fast graph theory algorithm can check the mesh linkage constraints quickly. Thus, mesh links that exceed a limit and isolated communications hardware may be easily identified. 
     In another embodiment, using a data structure where mesh nodes are represented as graph vertices, each mesh node is able to remember a set of its ancestors and remembers the number of hops from the BAN. When a limit is reached, a flag is raised for the violation. A flag is also raised if the mesh node is a BAN itself so that the mesh node can be marked and counted for BAN connectivity calculation. Each mesh node also remembers a list of edges that link to the neighbor mesh nodes. In the edge (link) structure, the end mesh nodes are remembered along with the indices of edge lists that are associated with the two mesh nodes. A flag will be raised if the edge is defined as blocked link. If a mesh node&#39;s root set is empty, the mesh node is isolated. In the process of adding a link between mesh nodes, a flag can be raised if the maximum connectivity of a mesh node with its neighbors is greater than a maximum number. 
     In any case, returning to  FIG. 1 , if client and mesh requirements are not met (step  120 ), then an embodiment of the present invention implements prioritized user/automatic actions that can be used to resolve unsatisfied requirements. In one embodiment, implementing prioritized user/automatic actions means that communications hardware may be moved, reoriented, or reconfigured either automatically or manually in the physical environment so as to meet client and mesh requirements. In another embodiment, implementing prioritized user/automatic actions means that a routing protocol of the communications hardware is changed so that varying the routing protocol allows the designer to meet at least one of mesh point constraints and mesh linkage constraints. In any case, once unsatisfied design requirements are identified (e.g. when mesh point constraints and/or mesh linkage constraints are not met), the invention implements prioritized user/automatic actions that include but are not limited to adding APs, moving APs, promoting APs into a BAN set, demoting APs from a BAN set, or changing different RF characteristics of the AP. Each of these methods will give a designer of the wireless communications system the flexibility to meet client and/or mesh performance requirements. 
     Continuing, once the calculation is made and constraints that have not been met are identified, the result of the calculation is displayed as visualization on the map. As mentioned above, in on embodiment, the visualization may be a color-coded lines or line thickness. Even though the term visualization is singular (as used herein), visualization refers to at least one, but may definitely encompass more than one and is plural. In another embodiment, the visualization may encompass icons and other indicators, such as a ring may be used as the visualization. 
     In one embodiment, the designer is able to filter the problem mesh nodes by only displaying the mesh nodes that are causing a particular constraint or set of constraints (as used below, also termed rules) to be broken. Having such an ability allows the user to see how each problem or set of problems independently affects the entire network. This allows the designer to meet defined constraints when the constraints are filtered. 
     For example, if there are too many links to one mesh node (a situation in which the mesh node in question is referred to as an over-connected node), the mesh node will be visualized with the appropriate graphical icon. If such situation happens, the user can pre-define a blocked pair of mesh nodes to prevent any link between the pairs of mesh nodes from happening. For example, if a mesh node has no linkages that can form with other mesh nodes, such a node is referred to as an isolated node and will be visualized with the appropriate graphical icon. As another example, if each mesh node is not connected to a minimum number of independent BAN nodes (a situation in which the mesh node in question is referred to as an unreliably connected node), then the user may promote any existing mesh node as a BAN, which identifies the mesh node as having a backhaul connection available, to see if the problem can be eliminated. 
     In one embodiment, before a designer determines to promote an AP, the designer may use the mouse cursor hovering over any potential candidate in a promoting mode and cause a calculation to occur to determine whether the promotion will assist with the design of the wireless communications system. This provides guidance to a designer as to what changes or potential changes to the mesh network may be beneficial prior to implementing the changes. After the re-calculation, some of the mesh nodes that were marked as being unreliably connected nodes may be eliminated from the violator list. In one embodiment, if the designer is satisfied with the results, the designer may accept the new design and the AP will be promoted permanently. If the designer is not satisfied, the user may move the mouse cursor over to another AP to see a different effect, until a good BAN candidate is found. 
     Referring now to  FIG. 2 , there is shown a two-dimensional (2-D) simplified layout of a building floor plan. The method uses a two- or three-dimensional (3-D) computer aided design (CAD) representation of a building, a collection of buildings, and/or the surrounding terrain and foliage to provide analysis and visualization of the wireless communications network. In one embodiment of the present invention, a network designer can visualize, in real-time, how rules are preserved or broken on the physical map. As a new mesh node is either added or moved by dynamically placing and moving the mouse cursor around within the map can cause re-calculation of rules to occur in order to take into account the updated number, position, and/or configuration of mesh nodes in the network at that time. For example, the mesh links may emerge or disappear, the colors of the links may change indicating the capacity or overall desirability of the link, the markers for BAN nodes and markers for “Isolated” mesh nodes and/or “Over-Connected” mesh nodes may emerge and disappear. In short, the physical map gives the designer a global perspective of the wireless communications network while making local modifications to a certain portion of the wireless communications network. 
     As an example,  FIG. 2  implements the following rules (also termed constraints, as used above): 
     Rule 1: Based on capacity requirements there shall be a lowest RSSI, SIR, SNR, and throughput values for each link. Any values below the limits invalidate the link. All the isolated mesh nodes should be marked to warn the designer. 
     Rule 2: To control packet delay and other network quality issues, the number of hops that each packet can traverse in a path through the network should be limited by a defined maximum. Based on available links and the limit on the hops, any mesh node beyond the hop limit to a BAN will be considered to not have a path to that BAN. Connectivity to a BAN, as defined as the number of paths to different BAN mesh nodes, shall be calculated as the mesh changes. Although a BAN mesh node is indicated by the above as the desired destination for a packet in this example, the desired destination analyzed by the present invention could be another client device or communications hardware device connected to or part of the mesh network. 
     Rule 3: To increase the network reliability, each mesh node must connect to a minimum number of independent BAN nodes. Any mesh node with BAN connectivity below the limit shall be marked as insufficiently reliable mesh node. 
     Rule 4: Based on how much throughput of an AP can handle and how much bandwidth each link requires, the maximum connectivity of a mesh node with its neighbors shall be defined. Any mesh node with more links than it can handle shall be marked as over-connected mesh node. To solve this problem, some of the potential mesh links should be defined as blocked. 
     Rule 5: Based on clutter/obstruction properties, channel availability for the air interface standards used by the mesh link and client link respectively, and predictive RSSI simulations for client coverage, the client should experience strong signals, smooth hand-over, and a high quality network connection as the client moves. In other words, the coverage of all APs must have minimum holes, sufficient overlapping to guaranty smooth hand-over and minimum interference with each other. The client coverage map shall show the coverage areas with color codes to indicate the quality. 
     Rule 6: When unreachable regions or available points are defined, the AP placement exercises shall observe the restriction rules and only allow the AP placed in the reachable areas/spots. 
     Rule 7: There can be a metric for each mesh node describing the packet delay attributed to that mesh node. If the cumulative end-to-end packet delay from a mesh node to a BAN exceeds a certain threshold then this rule can be in violation 
     Rule 8: There can be a maximum number of blocked links. If a mesh node exceeds the maximum number of blocked links then the rule is in violation 
     Referring back to  FIG. 2 , shown is a wireless mesh network with communications hardware, namely 2 BAN mesh nodes  202 ,  204  and an isolated AP mesh node  206 . In one embodiment, the AP mesh node  206  is surrounded by a blue ring to indicate that there is a violation. Further, the mesh links  208 - 218  are also color coded to indicate throughput. For example, a red line may indicate low throughput and a green line may indicate a high throughput. The grid polygons, e.g.  220 , are clutter objects that obstruct RF propagation. The obstructions may also be unreachable regions for communications hardware placement. As shown in  FIG. 2 , AP mesh node  206  is isolated and a new AP should be added to allow the AP mesh node  206  to connect to the rest of the wireless mesh network. 
     Referring to  FIG. 3 , shown is AP  302  that is placed in the wireless mesh network so that AP  206  may connect to the rest of the wireless mesh network via links  304 ,  306 . AP  206  still has a ring around it because the rules require that there be a maximum of three hops to get back to a BAN. As shown in  FIG. 3 , AP  206  requires at least four hops to reach a BAN, e.g. BAN  202 ,  204 . Thus, there is still a violation of the rules with the design in  FIG. 3 . 
     Referring to  FIG. 4 , shown is a new placement for AP  302  so that there is no violation of the rules and as a result the ring around AP  206  disappears. Specifically, AP  206  is provided a connection to a BAN node within three hops, namely mesh links  404 ,  406 ,  212 . 
     While the given examples are indicative of one embodiment of the invention that utilizes manual interaction by the user as a means of diagnosing and resolving mesh network issues, other embodiments of the present invention may utilize automated analysis capabilities to iteratively consider multiple possible solutions for a problem. For example, one embodiment of the present invention may iteratively consider placing new APs, promoting existing APs to have backhaul connectivity, and moving or reconfiguring existing APs in order to minimize the number of rules being violated by the resulting mesh network. 
     Those skilled in the art will recognize that a wide variety of modifications, alterations, and combinations can be made with respect to the above described embodiments without departing from the spirit and scope of the invention, and that such modifications, alterations, and combinations are to be viewed as being within the ambit of the inventive concept.