Wireless mesh routing is responsible to establish low-cost, high-quality routes in a dynamic environment. At the same time, it needs to consider the efficient usage of network resources. How to find the optimal route(s) with the minimum overhead is a challenging research topic.

There are several types of routing approaches. Proactive approaches are not suitable for dynamically changed networks since valuable network resources are wasted to keep nodes updated with unused links and routes. In flooding-based reactive approaches, as all network nodes are required to participate in the relays of route request packets, substantial control overhead is still inevitable.

In this thesis, we propose a set of progressive route discovery protocols (PRD), which obtains high-quality routes with little overhead in different network situations. The basic idea of PRD is to concentrate route discovery efforts in the regions that most likely contain the optimal route(s). More specifically, PRD divides the route discovery processes into several stages and progressively finds cost-efficient routes. In the network scan, namely, the first stage, the whole network is roughly explored and a preliminary route is set up between each source-destination pair with very little overhead. The network scan stage may not locate the best route, however, it helps locate route discovery regions, thus significantly decreasing route discovery overhead at the subsequent stages. At the optimal route discovery stage, a route discovery region is defined in the neighborhood of each preliminary route; and the source device concentrates route discovery effort on discovering the cost-efficient route towards its desired destination only within this region.

The progressive route discovery protocols can be easily extended to cover multipath routing and route update cases. During multi-path route discovery stage, a one-hop insulating region is built around a single-path route, and a new route is then established outside the region. Since these two paths are isolated by the region, they can effectively avoid inter-path interference, and therefore can, effectively support simultaneous data transmission for throughput aggregation.

Both performance analysis and simulation results show that the progressive route discovery protocols are a set of cost-efficient routing protocols beneficial to various wireless mesh networks.