基于遗传算法的无线Mesh网络仿真拓扑演化方法EvoTopo研究

《Simulation Modelling Practice and Theory》：Evolving realistic topologies for wireless mesh network simulation with EvoTopo

本文综述了无线Mesh网络（WMN）仿真中拓扑模型的重要性，指出传统均匀或网格拓扑与真实网络的差异，并介绍了一种基于遗传算法的新工具EvoTopo。该工具能够从单一真实网络节点位置生成大量相似拓扑，通过评估节点分布均匀性、最近邻距离和节点密度等参数，显著提升仿真结果的统计显著性。研究为WMN协议测试提供了更可靠的拓扑生成方法，适用于无线传感器网络和工业无线安装等场景。

　　

问题描述

对于（无线）路由协议的网络仿真，需要网络拓扑。为了获得良好的仿真效果，应使用大量不同的拓扑进行仿真，以便上层协议不会仅针对某一特定拓扑实例的特性进行设计。通常需要执行多次仿真运行（通常在几十次到几百次之间）。因此，有必要使用或创建大量无线网络拓扑。并非所有拓扑都适用。

EvoTopo算法

EvoTopo使用输入拓扑的节点位置，并采用遗传算法生成所需数量的“相似”拓扑，用于仿真（图6）。这意味着至少需要一张包含节点位置的近似地图作为输入。这或许被视为一个缺点，但实际上，无线Mesh网络的节点位置通常比包含顶点和边的完整网络拓扑更容易获得。许多Mesh网络项目在其社区网页上提供了网络地图。

评估

对于每个真实世界的“目标”拓扑（柏林、莱比锡、维也纳、MIT），我们生成了10个相应的均匀分布拓扑、1个网格拓扑以及若干演化拓扑。我们为MIT Roofnet生成了10个演化拓扑，为维也纳生成了10个，为柏林生成了8个，为莱比锡生成了6个，遗传算法运行了300代（MIT，30个候选个体）、350代（维也纳，35个候选个体）、400代（柏林，50个候选个体）和500代（莱比锡，50个候选个体）。

相关工作

在许多仿真中，拓扑是使用均匀分布或网格布局生成的。以下描述一些更复杂的拓扑生成方法：在[23]中，Bettstetter、Gyarmati和Schilcher针对非均匀节点分布，提出了一种细化算法，该算法可从均匀分布中创建出非均匀分布。在[24]中，作者描述了针对无线传感器网络的拓扑生成器GENSEN。GENSEN支持网格...

结论

本文介绍了一种基于进化算法的新方法，用于生成用于仿真的社区无线Mesh网络节点位置的现实人工拓扑。首先，分析真实世界拓扑的相关参数。我们使用节点密度、不均匀性和最近邻距离分布作为相关度量，这些度量我们在先前的工作中已提出。在我们的进化算法EvoTopo中，随机拓扑被创建...

致谢

这项工作是在研究集群Lakeside Labs的项目“无线网络中的协作中继”中进行的，并部分由欧洲区域发展基金、克恩顿州经济促进基金（KWF）和奥地利政府根据拨款号20214/15935/23108资助。