论文部分内容阅读
无线Mesh网络是下一代无线网络的一个关键技术,相比其它无线网络具有巨大的优势,无线Mesh网络是一种动态自组织和自配置的多跳无线网络,有着带宽高、可靠性好、覆盖范围广、部署成本低、可扩展性好等优势。在无线Mesh网络的网格体系结构中,由Mesh路由器和网关组成骨干网络,为不同的Mesh客户端节点提供连接服务。无线Mesh网络的性能和可操作性以及网络的连通性和稳定性在很大程度上取决于Mesh路由器节点的地理位置,也就是说骨干网络的拓扑结构是实现网络连接和网络覆盖率的一个决定性因素。因此,找到最优或接近最优的Mesh路由器节点的位置是该网络的关键。无线Mesh网络骨干节点部署问题是一个典型的NP-hard组合优化问题。目前针对无线Mesh网络骨干节点部署问题的优化算法比较多,其主要的求解算法包括:动态规划算法、数学建模法等精确算法;启发式搜索算法、蚁群算法、粒子群算法、遗传算法和模拟退火算法等随机搜索算法。但是这些算法未能完全满足某些约束条件(如流量需求),而且它们把MR和MG的部署优化问题分别考虑。本文针对无线Mesh网络骨干节点部署优化问题,在满足流量需求和网络连接的前提下,以最小化Mesh路由器数量为目标提出了一种有效的MR部署算法。算法分为两个阶段,第一阶段使用离散粒子群算法产生满足性能约束的网关的部署方案;在第二阶段,首先筛选出当前拓扑网络的相邻节点集并计算每一个相邻节点的权重,然后添加权重最大的相邻节点到骨干网络并更新骨干网络拓扑结构及候选节点信息,使用迭代的方式不断添加节点到骨干网络直至覆盖所有流量需求。以第二阶段MR部署结果作为第一阶段网关部署方案性能优劣的评估指标,不断改进网关部署方案。实验对比测试了算法在均匀分布、正态分布、指数分布和Weibull分布场景下的性能,实验结果表明,当部署规模较小时,本文算法能找到最佳部署方案,当规模较大时,本文算法部署MR的数量远小于ILSearch算法,比NF-Greedy算法部署的MR数量少5%-8%。