Solving mesh router nodes placement problem in Wireless Mesh Networks by Tabu Search algorithm

摘要

Wireless Mesh Networks (WMNs) are an important networking paradigm that offer cost effective Internet connectivity. The performance and operability of WMNs depend, among other factors, on the placement of network nodes in the area. Among the most important objectives in designing a WMN is the formation of a mesh backbone to achieve high user coverage. Given a number of router nodes to deploy, a deployment area and positions of client nodes in the area, an optimization problem can be formulated aiming to find the placement of router nodes so as to maximize network connectivity and user coverage. This optimization problem belongs to facility location problems, which are computationally hard to solve to optimality. In this paper we present the implementation and evaluation of Tabu Search (TS) for the problem of mesh router node placement in WMNs. The experimental evaluation showed the efficiency of TS in solving a benchmark of instances.