Router Node Placement With Service Priority in Wireless Mesh Networks Using Simulated Annealing With Momentum Terms

Abstract

In wireless mesh networks (WMNs), mesh clients communicate with each other via the gateway and bridging functions of mesh routers. The performance of a WMN is generally affected by its network connectivity and client coverage, both of which are determined by its router node placement (RNP) in the deployment area. For simplicity, previous works considered only the RNP where each mesh client is served as an equal. In practice, however, mesh clients should be served with different priorities owing to factors such as their importance and their different payments for the service access. To fulfil this requirement, by assuming that each mesh client is also associated with a service priority, this paper investigates an RNP problem with a service priority constraint in which the mesh clients with service priorities higher than a threshold must be served. Given that this problem inherited from the complexity of the original RNP problem is computationally intractable in general, this paper also develops a novel simulated annealing (SA) approach that takes into account momentum terms to improve the efficiency and accuracy of annealing schedules and prevent fluctuations in values of the acceptance probability function. Additionally, the time complexity of the proposed SA algorithm is analyzed. Furthermore, evaluation of different-size instances under various parameters and annealing schedules demonstrates the superiority of the proposed approach.