On optimizing wireless mesh networks : from theoretical capacity analysis to practical algorithm design

A wireless mesh network (WMN) is a hierarchical network consisting of mesh clients, mesh routers and gateways. Mesh routers constitute a wireless mesh backbone, to which mesh clients are connected, and gateways are chosen among mesh routers providing Internet access. In this dissertation, throughput performance of WMNs has been investigated from theoretical capacity analysis to practical algorithms' design. For such a network with Nc randomly distributed mesh clients, regularly placed mesh routers and Ng gateways, assuming that each mesh router can transmit at W bits/s, the per-client throughput capacity has been derived as a function of Nc, Nr, Ng and W. The result illustrates that, in order to achieve high capacity performance, mesh backbone network must be optimally designed. An innovative gateway placement algorithm is thus developed. It determines the location of a gateway based on a new performance metric. Therefore, given a certain number of gateways, the proposed gateway placement scheme provides a framework of maximizing the throughput of WMNs through proper placement of these gateways. Experimental results show that it constantly outperforms other schemes with a large margin. Algorithms on choosing the optimal number of mesh routers are also presented. Two problems are investigated. In Maximum Throughput Partition problem, the ideal throughput is achieved by optimally partitioning the network with a proper number of backbone nodes. In Maximum Throughput Partition with Hops' number Constraint problem, a similar problem is studied but with constraint on the average number of hops in the backbone network. The results show that it is critical to find an appropriate size of the backbone network for a WMN, especially when the hops' number constraint is imposed. The research findings and results can be used as guidelines for protocol design and deployment of WMN