Layout design for multiple collocated wireless mesh networks

We consider a fundamental problem in wireless mesh networking that concerns the layout of access points (APs) of multiple simultaneously operable wireless mesh networks located in the same region. For given directional antennas, we are interested in dense and uniform layouts that maximize the number of these wireless mesh networks without introducing radio interference, while providing convenient access to any of them from any location. We describe an optimal layout method, called the "diagonal placement scheme", for wireless meshes of squares under a simplifying interference model. Then we show upper and lower bounds for the performance of any optimal layout without the simplifying assumption. Our solutions have applications in a number of areas, including QoS routing, secure routing, fault-tolerance, and load balancing.