基于K均值聚类的改进Salama网络拓扑生成算法

资 源 简 介

本项目完整实现了对经典Salama网络拓扑生成算法的深度改进与优化，旨在为网络仿真、路由协议研究及流量工程提供更加逼真且数据丰富的拓扑环境。项目的主要功能与改进点包括：首先，创新性地引入K均值（K-Means）聚类算法来控制网络节点的空间分布策略，通过聚类中心的引导，使得生成的节点在仿真区域内的分布疏密有致，有效避免了传统随机生成中常见的局部过于密集或过度稀疏的问题，从而显著提高了生成拓扑的连通概率和结构均匀性。其次，项目极大地丰富了网络拓扑的属性数据，生成的模型不仅包含基础的连接关系，还完整生成了链路属性（通信费用、传输时延、链路带宽）和节点属性（节点处理费用、节点处理时延、时延抖动、数据包丢包率），支持多约束条件的QoS路由算法验证。最后，项目采用了符合物理现实的传播时延计算模型，将链路时延严格定义为节点间的欧几里得距离除以三分之二光速（即光信号在光纤介质中的实际传播速度），从而替代了抽象的随机权重，使得仿真结果更具物理意义。该源码通用性强，支持参数化配置，并提供直观的拓扑可视化展示。

详 情 说 明

基于K均值聚类的改进Salama网络拓扑随机生成算法

项目简介

本项目是一个基于MATLAB开发的通用网络拓扑生成工具。它实现了对经典Salama（亦称Waxman）网络拓扑生成算法的深度改进。项目通过引入K均值（K-Means）聚类思想来控制节点的空间分布，模拟现实网络中节点在地理上呈现“簇状”分布的特性（如城市群或接入热点）。此外，项目摒弃了抽象的随机权重，采用符合物理光学的链路传播时延模型，并生成了包含带宽、费用、丢包率等多维QoS属性的数据集，为网络仿真、路由协议研究及流量工程提供了高逼真度的实验环境。

主要功能特性

1. 基于聚类的节点空间分布

不同于完全随机撒点，本算法采用高斯混合模型策略。算法首先在仿真区域内随机选取K个中心点，然后基于正态分布（高斯分布）在中心点周围生成节点坐标。这种机制使得节点天然呈现聚类特性，有效避免了局部过度稀疏或均匀分布不符合现实的情况。随后，算法内部运行标准K-Means算法对节点进行归类，用于后续的连接策略优化和可视化着色。

2. 改进的Salama拓扑生成策略

在经典的Waxman/Salama概率连接模型基础上，项目引入了“簇内优先连接”机制。算法利用节点的聚类归属信息，对属于同一个簇的节点对，将其建立连接的概率提升50%（乘以系数1.5），从而增强了局部网络的连通紧密度，模拟局域网或城域网内部的高连通特性。

3. 符合物理现实的传播时延模型

链路的传播时延不再是随机生成的数值，而是基于物理距离严格计算得出。 计算公式：时延 = 欧几里得距离 / (光速 / 光纤折射率) 其中光纤折射率设定为1.5，即信号传播速度约为光速的三分之二，确保了仿真数据的物理意义。

4. 完备的多维QoS属性生成

项目不仅生成拓扑结构，还随机生成了丰富的节点和链路属性，支持多约束路由算法验证：

• 链路属性：链路带宽 (Mbps)、通信费用、传播时延 (ms)、物理距离 (km)。
• 节点属性：节点处理费用、节点处理时延 (ms)、时延抖动 (ms)、数据包丢包率 (%)。

5. 连通性自愈机制

算法内置了图连通性检测与修复模块。在初步生成拓扑后，若网络存在孤立的连通分量，算法会自动计算分量间的最短距离，并添加必要的链路将所有分量合并，确保最终生成的网络是全连通图。

6. 直观的可视化展示

脚本运行结束后，会输出两个图表：

• 网络拓扑结构图：展示节点位置（按簇着色）、链路连接（按带宽粗细绘制）及聚类中心。
• 邻接矩阵热力图：直观展示节点间的连接稠密程度。

算法实现与核心逻辑解析

项目的主程序流程经过精心设计，以下是代码内部具体实现的详细逻辑：

第一阶段：参数配置与环境初始化

程序首先定义了仿真区域（1000x1000 km）、节点数量、聚类中心数（K值）、聚类离散程度（Sigma）以及Salama模型的Alpha和Beta参数。同时，定义了QoS属性的随机范围（如带宽100-1000Mbps）。

第二阶段：节点生成与K-Means聚类

1. 高斯分布撒点：随机生成K个中心坐标，遍历每个节点，随机选择一个中心，并基于设定的标准差（ClusterSigma）在该中心周围按正态分布生成坐标。同时包含边界检查，防止节点溢出仿真区域。
2. K-Means归类：虽然节点是按中心生成的，但在几何上尤其是在两个中心重叠区域，节点的归属需要严格判定。代码通过内置的RunKMeans子函数，经过多次迭代，将每个节点重新分配给几何距离最近的中心，确保聚类属性准确。

第三阶段：距离计算与物理时延

计算所有节点对之间的欧几里得距离。利用公式 Delay = (Distance / PropSpeed) * 1000 将距离转换为毫秒级的传播时延。该矩阵既用于后续生成连接概率，也直接作为链路属性的一部分。

第四阶段：改进的连接生成

遍历所有节点对（i, j），计算经典Salama概率：P = Alpha * exp(-Distance / (Beta * MaxDist))。 改进点：检查节点i和节点j是否属于同一个聚类（ClusterID相同）。如果是，则将P乘以1.5（上限为1.0）。根据最终概率P与随机数的比较结果决定是否添加链路。

第五阶段：连通性保证（EnsureConnectivity）

采用BFS（广度优先搜索）算法检测图的连通分量。如果发现多于一个连通分量，算法执行修复逻辑：

1. 找出第一个连通分量。
2. 遍历其余所有连通分量，寻找与第一个分量之间物理距离最近的一对节点。
3. 在最近的这对节点之间强制添加一条链路。

重复该过程直到图中仅剩下一个连通分量。

第六阶段：QoS属性填充

• 链路表构建：遍历邻接矩阵，对存在的每一条链路，随机从设定区间内抽取带宽和费用，并直接读取之前计算好的物理时延和距离，存入LinkTable。
• 节点表构建：遍历每个节点，随机生成处理费用、处理时延、抖动和丢包率，存入NodeTable。

使用方法

1. 确保计算机上安装有 MATLAB 软件。
2. 将提供的源码保存为 main.m 文件。
3. 直接运行 main.m 脚本。
4. 控制台将输出生成的网络特征（节点度、链路数等）以及部分属性数据表。
5. 系统将自动弹出一个包含网络拓扑图和邻接矩阵的可视化窗口。

系统要求

• MATLAB R2016a 或更高版本（代码使用基础绘图和数学函数，兼容性较好）。
• 无需额外的工具箱（Toolbox），代码内部已手动实现了简易K-Means算法和正态分布生成逻辑。