基于模拟退火遗传算法的无线mesh网络路由放置问题研究

摘要

网络的路由放置问题在无线Mesh网络中一直是一个重要研究方向。一个高效的mesh路由节点放置方法能有力地保证网络的连通和用户的全覆盖。因为无线mesh网络可以提供价格低廉的无线带宽，所以在网络基础设施建设上它变得越来越重要。然而，此类问题是NP难题，研究者们通过利用启发式算法去解决这类问题以获得近似最优，希望能在合理的时间内得到高质量的解。
　　 本文首先介绍了无线Mesh网络和路由放置问题的多种模型，并详细讨论了模拟退火算法(SimulatedAnnealingAlgorithm)和遗传算法(GeneticAlgorithm)这两种经典的启发式算法的联系。在此基础上对模拟退火算法和遗传算法进行了改进，进一步提出了模拟退火遗传算法(SimulatedAnnealing-GeneticAlgorithm，SA-GA)去解决无线mesh网络中的路由放置问题。一方面，SA-GA算法在模拟退火算法的降温过程中采用覆盖范围小且处在用户密集区域的路由器与覆盖范围大且处于用户稀疏区域的路由器进行交换，提高大中型网络的局部优化能力；另外，采用覆盖范围最大的路由放置在区域中用户最集中的位置，提高小型网络计算时间；另一方面，在遗传算法种群进化过程中，从已选择好的父系个体中选取适应度值高的两个父系个体以一定大小随机区域为交叉因子进行交叉，提高全局优化能力。最后，以遗传算法流程为主体，融合模拟退火算法进一步对种群进行优化调整，达到增加随机性和提高全局搜索能力的目的，即从父系群体中选取较小比例的父系个数，另外，增加路由器权重为目的的改进适应度函数，优化网络连通性。文章的仿真结果表明，在大、中、小型无线Mesh网络中模拟退火遗传算法与模拟退火算法和其他算法相比，能更好地优化网络资源和满足路由放置问题的需求。