Font Size: a A A

The Research Of Router Nodes Placement Problem Based On Simulated Annealing--Genetic Algorithm In Wireless Mesh Networks

Posted on:2013-11-25Degree:MasterType:Thesis
Country:ChinaCandidate:L M ChenFull Text:PDF
GTID:2248330374968821Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Mesh router nodes placement is a central problem to Wireless Mesh Networks (WMNs). An efficient placement of mesh router nodes is indispensable for achieving network performance in terms of both network connectivity and user coverage. Networking infrastructure is becoming more and more important in WMNs, because of providing cost-efficient wireless broadband. But, this kind of problem is NP-hard. Researchers are paying attention to the resolution of the mesh router placement problem through heuristic approaches in order to achieve near optimal, and hope to get high quality solutions in reasonable time.We firstly introduce Wireless Mesh Networks and models of Router nodes placement problem in this work, and specific discuss inner connections of two kind of classical heuristic approaches:Simulated Annealing Algorithm (SA) and Genetic Algorithm (GA). Based above researchs, we propose improving Simulated Annealing Algorithm and improving Genetic Algorithm, further more, we propose Simulated Annealing-Genetic Algorithm approach to solve router nodes placement in WMNs. On the one hand, in the process of cooling stage of SA algorithm, SA-GA approachs exchange the best router (that of largest radio coverage) of the sparsest area to the worst router (that of smallest radio coverage) in the most dense area, the aim is to improve the capability of local optimization in the big and middle networks; Other, SA-GA approachs select the router of largest radio coverage and places it in the most dense area, the purpose is to speed up the computation time; On the other hand, we take the two highest values of Fitness function from the selected paternal individuals in the evolutionary process of GA, and randomly pick a certain grid area from both of paternal individuals and make them cross, the aim is to improve the capability of global optimization; Finally, based on the main process of the GA, we combine SA algorithm to GA for achieving good performance in terms of population evolution and increasing randomness and the ability of global searching, we select smaller proportion individuals from paternal population. For the purpose of increasing the weight of router, we Improve the Fitness function to optimize the Size of giant component. The results of simulation show that SA-GA Algorithm is better than SA algorithm and other heuristic algorithms in terms of optimal networks resource and meeting the needs of router nodes placement problem in the big, middle, and small WMNs.
Keywords/Search Tags:WMNs, Simulated Annealing Algorithm, GeneticAlgorithm, Simulated Annealing-Genetic Algorithm, Size ofGiant component
PDF Full Text Request
Related items