A Geometric Deployment and Routing Scheme for Directional Wireless Mesh Networks

This paper first envisions the advent of the wireless mesh networks with multiple radios and directional antennas in future. Then, based on the observation that simplicity induces efficiency and scalability, the paper proposes a joint geometric deployment and routing strategy for such mesh networks, and also gives a concrete approach under this strategy. The main idea of this strategy is to deploy mesh networks in certain kind of geometric graph, and then design a geometric routing protocol by exploiting the routing properties of this graph. The proposed concrete approach comprises two parts: (1) a topology generation algorithm based on Delaunay triangulations and (2) a geometric routing protocol based on the greedy forwarding algorithm. Both parts are characterized by simplicity and appealing properties, with formal proofs provided when possible. The simulation results validate our proposed approach.