Date Added: Dec 2009
Wireless mesh networks are popular as a cost-effective means to provide broadband connectivity to large user populations. A mesh network placement provides coverage, such that each target client location has a link to a deployed mesh node, and connectivity, such that each mesh node wirelessly connects directly to a gateway or via intermediate mesh nodes. Prior work on placement assumes wireless propagation to be uniform in all directions, i.e., an unrealistic assumption of circular communication regions. In this paper, the authors present approximation algorithms to solve the NP-hard mesh node placement problem for non-uniform propagation settings.