Joint Optimal Channel Allocation, Interface Assignment and Routing in Multi-hop Wireless Networks

Multi-hop wireless networks have advantages over the single-hop ones in terms of reliability and coverage range. Moreover, the capacity of multi-hop wireless network can be substantially increased via multiple radios tuned to non-overlapping channels. However, the channel allocation, network interface cards assignment and routing remain challenging due to the interference of the neighboring transmissions. These three problems have proved to be a NP-hard problem. Previous studies separating the routing from the channel allocation, instead of considering the three problems as a whole, cannot get the overall optimal solution. In this work, we employ an improved Multi-Objective Genetic Algorithm to optimize the channel allocation, interface assignment and the routing, so as to minimize the overall network interference. The proposed algorithm includes two parts: 1) dynamic genetic mutation based on diversity measure; and 2) elite preservation based on ideal points. In order to eliminate illegal solutions, a new individual encoding method is proposed. In addition, an interference model taking into account the effects of channel separation and the traffic of neighbor links is applied to evaluate the quality of the interference of the network. Finally, a fitness function is defined to obtain the best search results. Simulation results show that our improved Multi-Objective Genetic Algorithm can reduce the interference and cost of total network compared to the standard Genetic Algorithm.