10.8.1 Genetic Algorithms for Topology Planning in Wireless Networks

A wireless mesh network (WMN) is an attractive networking technology, providing with convenient access to the Internet as well as the spontaneous connection of mobile devices to each other. In WMNs, a number of studies have focused on the channel allocation problem because it is not easy to utilize the multi-channel and multi-radio characteristics of WMNs. Since the channel allocation in multi-channel multi-radio WMNs is an NP-Hard problem, most approaches design the network with a mathematical model and solve it with linear programming and some approximation algorithms.

On the other hand, where to deploy mesh routers is also a crucial matter in WMNs since it is directly related to the efficiency and deployment costs. This problem might also be solved by linear programming, however when the size of the target area becomes large, the linear programming method cannot handle this matter in a finite time. Therefore, in most cases, it is not an appropriate approach.

Genetic algorithm (GA)is introduced in deployment of mesh routers, in order to find a feasible solution to this matter in a finite and reasonable time. The target area is regarded with n n grid and the mesh routers can be placed at the center of each rectangle, where n can be set as a larger number when more precision is needed. Each rectangle is assigned a sequence number where the top-left rectangle has the smallest number and the bottom-right the...