基于图论和PSO算法的无线Mesh网络网关部署研究及其推广

摘要

在无线Mesh网络中，网络的大部分流量汇聚于网关，网关部署直接影响到网络的服务质量，合理的网关部署对网络性能的提升具有重要意义。无线Mesh网络网关部署和K中心选址问题类似，科学合理的设施选址可以有效地节约资源、降低成本、提高社会效益和经济效益。本文将围绕无线Mesh网络网关部署以及K中心选址问题进行研究，主要工作有：
　　（1）将Mesh网络的网关部署方式进行分类，在相同的网络拓扑结构中，分别用节点K中心和几何K中心两种方式进行网关部署，通过对比发现，几何K中心更具有普遍性，理论上可获得全局最优解；同样地，对K中心选址问题进行分类，结果分析得出，与离散K中心选址相比，连续K中心选址的灵活性较大，选取的设施位置较好。此外，用PSO算法对不同的测试函数进行优化，仿真结果表明，初值对PSO算法的收敛状态影响显著。因此，采用PSO算法求解几何K中心网关部署问题时，改进粒子群的初始位置，可降低网络的覆盖半径。
　　（2）对几何K中心的无线Mesh网络网关部署问题进行了研究，并提出了中心粒子群优化（CPSO）算法。该算法归结为在给定的网络拓扑中寻找全连通子图，并筛选出功能最完备的极大全连通子图，求得初始中心点位置，然后结合PSO算法，利用这些初始中心点位置对PSO算法进行初始化，并引入随机生成的惯性权重，使得算法更容易获得最优解。通过仿真实验，将所提的CPSO算法与其它算法进行对比,结果表明本文所提方法具有更好的优化效果和收敛速度。
　　（3）针对连续K中心选址问题，本文构建了新的求解模型，并以服务站到需求节点的加权距离最小作为优化目标，提出了基于模拟退火的粒子群优化（PSOwSA）算法。在 PSOwSA算法中引入了模拟退火机制和惯性权重等改进策略，使算法不易陷入局优、收敛速度加快。通过仿真和对比发现，PSOwSA算法优化得到的加权距离小，稳定性强，收敛速度快。
　　通过对以上两个经典问题进行分析和研究，并提出了可行的解决办法，所提方法同样可应用于社交网络、无线传感器网络和物流网络等复杂网络中。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 研究内容及创新点

1.3 本文的组织结构

第二章 相关理论与工作

2.1 无线Mesh网络

2.2 设施选址问题

2.3 网关部署与K中心选址问题的关系

2.4 粒子群优化算法

2.5 本章小结

第三章 基于图论的无线Mesh网络网关部署研究

3.1 引言

3.2 无线Mesh网络的网关部署模型

3.3 基于极大全连通子图的中心点

3.4 基于CPSO算法的几何K中心网关部署

3.5 仿真分析

3.6 本章小结

第四章 基于PSO算法的设施选址问题研究

4.1 引言

4.2 连续K中心选址问题的模型

4.3 基于PSOwSA算法的连续K中心选址问题

4.4 仿真分析

4.5 本章小结

第五章 总结与展望

参考文献

在研究生期间发表论文及科研情况

致谢