Deployment and assessment of wireless mesh networks

Multi-tier wireless mesh network deployments are a popular, cost-effective means to provide wireless broadband connectivity to neighborhoods and cities. Client devices within the coverage area of a mesh network connect wirelessly to fixed mesh nodes, which then forward traffic directly or via multi-hop paths to capacity injection points. The small number of capacity points act as Internet gateways and reduce overall network cost by limiting the amount of costly wired infrastructure needed. Non-uniform wireless signal propagation and the contention caused by multi-hop traffic contribute the challenge of deploying mesh networks with both high performance and low cost. This dissertation presents and evaluates cost-efficient algorithms for deployment planning and measurement-based assessment of wireless mesh networks. The mesh node placement problem requires mesh nodes to provide ubiquitous network coverage to clients, as well as connectivity amongst mesh nodes. The first contribution of this thesis is to present a graph-theoretic formulation of the NP-hard mesh node placement problem. This is the first formulation which considers the case in outdoor networks where signal propagation is non-uniform and enables the design of graph-theoretic approximation algorithms in order to minimize the deployment size or average contention. Secondly, deployment planning must select locations for the placement of capacity points, as their locations determine the path lengths in the networks and the resulting capacity available to transmit data to and from the Internet. To choose capacity point locations, I first present a technique to efficiently calculate network capacity and then two local search algorithms adapted from solutions to the facility location problem. Third, this thesis presents a framework for the measurement-based verification of a deployed network's performance. To avoid relying on expensive and exhaustive measurement studies, I consider the assessment problem with a limited number of measurements. The framework uses terrain-informed estimation, per-node virtual sectorization, and measurement refinement to accurately predict the network's performance at any given location. I evaluate the presented algorithms on realistic network topologies and with a large-scale measurement study of two currently deployed mesh networks: the TFA network and GoogleWiFi network. The thesis results demonstrate the essential nature of incorporating measurements, realistic propagation, and wireless contention into mesh network planning and assessment techniques