Research On Topology Structures And Communication Algorithms For Some New Wireless Mesh Networks

Wireless mesh networks (WMN), acting as technology of “ubiquitous” broadbandservices, has been attracting great attention of researchers over the last decade. By theintegration of ad hoc network, cellular network and other early wireless network, WMN wasproposed. But WMN differs from the traditional ad hoc network and cellular network fromthe properties such as the mobility and energy etc. WMN promises higher spectrum usage,and covers larger area under multi-hop relaying. Meanwhile, constructing WMN costs lessthan wired network. As WMN research advances quickly, the corresponding standards aregetting mature. Moreover, some of the key issues are left for special applications, such asscheduling algorithm, routing protocol, topology and node addressing etc.The thesis focuses on some critical problems of multiple input multiple output (MIMO)WMN. WMN transmission characteristics include the interference character, topologystructure, topology planning, and node addressing, as well as on other aspects. The thesispresents unique channel layered graph Cartesian product model. Based on the graph model,the thesis conducts research on MIMO WMN scheduling and routing algorithm. To thetriangular mesh and unit constructed grid mesh, Wavelike scheduling and Destination orientedrouting algorithm are given based on channel layered graph model and node addressingscheme.The main research issues are:(1) Topology planning problem, namely whether the unitstructure can be used to generate WMN topology planning?(2) If there is a certain graphmodel, which can facilitate discussion of MIMO WMN interference free topology.(3) Theproblem on addressing a node in channel layered graph Cartesian product model.(4) Theoptimal scheduling problem, with multi-radio MIMO WMN channel layered graph model, i.e.pursuits the capacity maximization scheduling.(5) The routing problem that encouragesnetwork throughput with graph Cartesian product model. The study on these problems putsforward the corresponding solving methods.The main research content and innovations are as follows:1．The thesis proposes a method to generate mesh topology from a starting point byrecursively growing. Meanwhile, with given basic grid mesh, a method for constructing meshtopology is introduced to replace basic grid node by unit. The given approach to generatemesh topology is helpful to guide network planning. Furthermore, detecting path in generatedtopology is discussed with edge coloring method. Through the study of combination propertyin the alternative lattice mesh, whose node is replaced by basic unit, a general conclusion to count the path number is given between specific topological node pair.2．In order to take advantages of orthogonal channel and MIMO WMN topology, ahierarchical model, graph Cartesian product is proposed. This model virtually maps amulti-radio node into a chain, and each node on the chain represents one of the availableradios. A plane mesh topology and a node chain operate into a channel hierarchical graphCartesian product model, and the scheme simplifies channel allocation. Under the premise ofthe interference avoidance, the model facilitates discussion on MIMO WMN scheduling androuting problems.3．In the channel layered graph model, a mesh node addressing strategy is given. Thenode addressing strategy completely unfolds the symmetry of the logical structure in thetriangular mesh. With the help of node addressing strategy, in general, a formula is raised tocalculate the smallest number of hops between a router node coordinate and the gateway nodecoordinate. In the meantime, WMN scheduling and routing problems can be handled by theoperation of node coordinate vector, which facilitates the description of the communicationproblems and provides a simple effective logical method. In addition, the thesis gives anumber of characteristics of node addressing. For example, the relationship of thecorresponding number of hops and a pair of specific addressing coordinates. The nodes andedges migration characteristics are also discussed under the rotation transformation.4．The thesis presents MIMO wavelike mesh scheduling algorithm. To the WMNbackbone scheduling problem, IEEE802.16standard does not give a solution. The standardsuggests centralized scheduling method. Then, the specific application can develop efficientscheduling. Channel layered model facilitates the discussion on scheduling problem withradio interference free, because each wireless channel is a virtual plane mesh. To encouragemaximum capacity, the traffic scheduling should achieve as many as possible transportconnections in Cartesian product graph layer for all channels. The thesis then proposes thelargest coexisting edge set algorithms. In order to encourage fairness and to minimize thetransmission delay, the thesis explores a brand new wavelike scheduling algorithm relying onthe MIMO channel layered graph model.5. The thesis proposes the destination-oriented routing algorithm based on the channellayer graph model and node addressing. Find a routing path according to node addressing, notrelying on additional routing tables, the new routing algorithm encourages uplink throughputand capacity. While replacing a lattice mesh node with a certain unit to generate new mesh,the feasible path from the source to the destination can be detected hop by hop with predefined next hop correct direction, both for the generated mesh and the channel layeredtriangular mesh. Considering interference and node degree constraints, the path can beselected with minimum hop count metric. The performance of the routing algorithm can beevaluated by the uploading throughput of BS. The destination oriented routing algorithmconsumes small resource, in aspects of theory analysis and simulating experiments.Meanwhile, the routing algorithm encourages capacity. Deploying some more interfaces to theaxis nodes, the algorithm can improve uploading throughput too.