Efficient Mesh Router Placement and Interface Configuration in Wireless Mesh Networks
Junfang Wang, Dharma P. Agrawal and Bin Xie
Mesh router (MR) placement is one of the fundamental issues that can greatly affect the performance of a wireless mesh network (WMN). A MR placement strategy aims at systematically determining the optimal positions and number of MRs and the optimal number of radio interfaces each MR needs, while taking into account various constraints such as network coverage, connectivity, and traffic demand. In this paper, we study the problem in three network models respectively: (1) Homogeneous network: MRs could be placed anywhere in a network area and traffic demand is uniformly distributed; (2) Heterogeneous network: MRs could be placed anywhere but traffic is non-uniformly distributed; and (3) Constraint network: MRs could be placed only in those pre-decided locations and need to support different traffic demands. We first analyze the problem in homogeneous network to get the theoretical lower bound results. Then we extend our work into heterogeneous network and propose a heuristic algorithm called RTSB (Relaying Traffic Set Based) to obtain the heterogeneous interface configuration. Furthermore, we investigate the problem in constraint network and introduce an algorithm called MCAM (Minimal Coverage plus Add-and-Merge) to achieve MR placement. Our simulation shows that the proposed algorithms can effectively generate the MR placement that meets all the constraints in various network settings.
Keywords: Internet Gateway, Mesh Router Configuration, Mesh Router Placement, Network Connectivity, Network Coverage,Wireless Mesh Network.