启发式网络拓扑图布局算法范文

本站小编为你精心准备了启发式网络拓扑图布局算法参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

1基于节点属性的启发式网络拓扑图布局算法

1.1节点聚类预布图算法工业监控网络拥有明确的拓扑层次结构。本算法支持一层或二层星型，一层mesh型和mesh型与星型两层混合的工业监控网络（由于PC唯一，这里不计入拓扑层次划分中）。分析网络节点属性，按照网络控制自上而下的结构，将网络节点分为入网终端节点，转点和边缘节点三种。入网终端节点即直接与PC相连的设备节点（例如网关），位于网络唯一PC节点下端，为其区域的唯一一级簇首，是所有该区域节点数据到达PC机时必须通过的端口，位于第一层，拥有下跳和唯一上跳。转点（例如路由）在本研究算法中成mesh型或者星型拓扑结构与入网终端节点直接或间接相连，分布在网络拓扑的第二层，既有上跳也有下跳。边缘节点（例如监控设备）位于整个网络终端，在本算法针对的网络拓扑模型中位于图的第二层或第三层，只有唯一上跳。迚一步分析节点属性发现，无论是转点还是边缘节点，都拥有连接或者不连接入网终端两种连接关系属性。

1.2节点持有力的属性及力作用对象规定根据节点的连接关系，对节点所持有的力的属性和力作用对象规定如下：(1)入网终端节点不存在力的属性；(2)各转点持有满足胡克定律（0*()TFkll；l为弹力线实际长度、0l为线原长；当()00ll时，TF为0）的拉力属性，对与之相连的边缘节点产生拉力的作用；(3)引入中心斥力，区域中心点io持有公式(1)所示的斥力属性，对iZ区域所有不与iR相连的边缘节点产生斥力作用。(4)不与入网终端节点相连的边缘节点持有斥力属性，但仅对拥有共同连接转点的边缘节点产生斥力作用。

1.3启发式布图算法本算法先根据节点拓扑结构属性和连接对象属性对所有节点的预布图规则做了聚类，再通过分析节点的连接关系对各节点所持有力的属性做了规定，幵依据力的作用对象做了区域聚类。启发式布图算法描述除沿用2.1节中变量定义外另追加如下定义。

2实验结果展示及分析

选择一典型工业监控网络聚类区域iZ分别为35节点和40节点（转点分别为星型和mesh型拓扑结构）为例，应用自己开发的MFC平台对算法迚行验证幵与斥力张力模型迚行对比，拓扑图如下所示：图3、图4、图5和图6为应用本算法的布图结果；图7和图8分别为应用斥力张力模型对应图3和图5数据的布图结果。图中实心圆形代表边缘节点，弧边矩形代表转点（实心代表与入网终端节点直接相连的节点，空心代表与入网终端节点间接相连的节点），矩形代表入网终端节点。图7、图8中红圈表示在张力斥力模型中，虽然点不重合，但由于点所应用的图元存在面积而发生重叠的部分。对比图3、图5和图7、图8可以看出本算法对于拓扑图拓扑结构的表达更加直观、清晰。

3结论

工业监控网络拓扑可视化研究具有重要的意义，本算法针对工业监控网络中典型一层或二层星型，一层mesh型和mesh型与星型两层混合的网络拓扑结构提出了基于节点属性的启发式网络拓扑图布局算法，幵经实验验证其可以满足网络拓扑可视化直观性和实时性的要求。

作者：梁晟 万羊所 单位：重庆邮电大学