电力通信网络中OSPF区域划分问题的研究

李祝红，赵灿明

（国家电网芜湖供电公司，芜湖241000）

1 引言

OSPF协议作为一种基于链路状态的内部网关路由协议，广泛应用于目前的Internet广域网和Intranet企业网中，支持区域划分。AS（自治系统）中的路由器之间通过周期性的hello报文建立邻居关系之后，每个OSPF路由将本地的路由信息（如路由ID，可用端口，邻居列表信息等）通过泛洪LSA（链路状态通告）的形式在自治系统内部传播链路状态信息。收到LSA的路由器将LSA信息结合本地的链路状态通告信息形成LSDB（链路状态数据库），形成本地路由器对整个网络拓扑的理解，通过SPF算法决策出最小代价的无环路由，形成本地路由选择表。

假设电力通信网络作为一个自治系统来运行OSPF协议，随着电力通信网络的进一步扩大，运行OSPF的路由器也会相应地出现数量上的增长，每个路由器维护的庞大的LSDB占用大量的内存空间，路由计算复杂度增加，路由器之间的通信量会占用大量的带宽，导致OSPF协议路由效率低下。为了降低LSDB的数据级别并减少对网络设备CPU和带宽的占用，提高运行效率和网路收敛速度，需要进行合理的区域划分。

现有关注网络收敛速度的路由或者区域搜索技术尚未对区域划分有一个全局的划分方案，包括区域边界的确定等。郑金华等[1]提出，用数学方法难以解决函数优化中的区域划分问题。为此,文献[1]提出了用狭义遗传算法实现区域划分的方法，实现了基于自动区域划分的分区域搜索的狭义遗传算法,从理论上分析了算法是全局收敛的,并具有收敛速度快、搜索过程稳定性高、可控制性强等特点。张丹丹等[2]将所建立的变电站规划模型和求解算法应用于青州地区配网高压变电站优化规划实际算例,算例中分析了权重调整量取值不同对最终规划方案的影响,验证了解耦规划模型的合理性、可行性和PSO算法及加权K求解算法计算速度快、收敛性好等特点。肖迎杰等[3-4]在改进的ZRP路由协议中运用新的域生成算法,通过引入通信节点个数的概念,以通信节点个数较多的节点为中心生成域,减少了域的个数,避免了节点及域的重复归属;以域生成算法中的中心节点为簇首节点,运用改进的路由算法,由簇首节点负责路由转发,避免了路由的冗余转发,路由开销也随之减少,提高了路由效率。胡海洋等[5]提出一种虚拟分布式环境中基于密度聚类的改进型划分算法 (DCCA)。该方法改进密度聚类中的邻域半径(Eps)和最小数目阈值(MinPts)因子，提出了基于移动视窗方法的密度聚类方法。杨帆等[6]分析现有面状数据聚类算法的特点和不足，进而提出一种新的算法，该方法提出将面状统计单元进行网格划分，引入基于网格密度聚类算法的思想，克服现有面状聚类的诸多缺点,进行二维空间平面的区域划分。夏少波等[7]提出一种在无线传感网络中定位算法的改进机制，对网络进行基于跳数的重新区域划分。谢珊珊等[8]对规模较大的无线传感器网络容易产生冗余数据包等问题，提出基于区域划分的连通支配集协议,RPMPR协议中每个节点针对网络拓扑信息，对邻居节点进行区域划分，作为中继转发的选择依据。以上所述算法对于特定的路由或其他协议进行基于区域划分的改进，并不适合OSPF区域划分的特性。研究提出的算法旨在通过结合电力通信网络实际情况，通过选择未来区域内的中心汇聚节点对邻居节点进行区域划分，解决区域划分的覆盖度和合理度问题。

2 相关描述

2.1 问题模型

OSPF协议网络可以划分为逻辑上互连的几个区域，来降低前文所述的影响。路由器LSA泛洪过程在所属区域进行，区域内部路由器只维护此区域的局部拓扑数据库和理解局部网络拓扑图，当网络拓扑变更时，会减少OSPF协议报文的传递数量，减少对带宽的占用。区域之间LSA通告信息的交互，通过域间边界路由器（ABR）完成，如图1所示，R2，R4，R9即为ABR，同时属于多个区域的ABR为每个区域维护各自的LSDB。OSPF协议网络的区域类型可以简化概括为：骨干区域和非骨干区域。如图1中所示区域ID为A0的区域即为骨干区域，负责各个子区域间的通信；A1，A2，A3为非骨干区域。

区域的划分由OSPF协议自动进行，并覆盖网络拓扑中的所有节点，防止区域边界路由器负载过重，均衡链路负载，保证骨干区域能够尽可能与子区域之间建立物理上的链接，以方便子区域间的通信，这是电力信息网络OSPF区域划分需要解决的关键问题。

图1 OSPF区域简化示意图

2.2 相关定义

电力通信网络拓扑区域划分问题实际上可以归结为图的划分问题，即用无向图G=（R,E）来描述电力网络的拓扑结构，其中R表示路由节点集合，E表示节点之间的所有链路集合。

为方便描述，给出以下相关定义：

定义1一跳邻居集合：无向图G=（R,E）中，对于任意节点r∈R，节点r的一跳邻居集合：

定义2E领 域：给定对象节点半径为E的区域为该对象节点的E领域。

定义3 直接密度可达：对于节点集合R，如果节点q在p的E领域内，并且p为核心对象节点，那么节点q 从节点p直接密度可达。

定义4 两跳密度可达：对于节点集合D，给定一串样本节点P1,P2，P3。假如节点P2从P1直接密度可达，节点P3从P2直接密度可达，节点P3从P1两跳密度可达。

3 基于网络密度聚类的区域划分算法

3.1 骨干区域的确定

通过OSPF信息交换（hello报文），每个节点获得一跳邻居信息（包括节点ID等信息），并周期性地与邻居节点交换自身节点维护的一跳邻居列表信息，每个节点也可获得k-跳邻居信息（包括路径上的下一跳信息）。

骨干区域汇总各个子区域的路由信息，并负责完成子区域之间的通信，故骨干区域与各个非骨干区域之间通过物理链路或者虚拟链路直接相连。考虑电力通信网络的实际情况，可以以网络中核心路由器节点作为中心负责节点，以一跳邻居节点集合为半径范围，作为骨干区域的初始边界即如图2所示，此时的可能部分成为骨干区域内部的路由器节点，部分路由器元素节点集合成为区域边界路由器（ABR）。

图2 区域划分结果示意图

3.2 非骨干区域的确定

完成网络拓扑的关于骨干区域的粗粒度分割后，需要对拓扑中为进行区域划分的其他节点集合NB进行细粒度划分。各个非骨干区域内容元素节点的确定，可以采用基于密度（网络跳数）聚类的迭代过程实现。

3.2.1 基于密度的聚类算法

所谓聚类，就是将大量d维数据样本聚集为k个类，使同属一个类的样本相似度最高，不同类中样本的相似性最小。基于密度的聚类算法考虑将空间数据样本中被低密度区域分割开的高密度区域聚集为类（簇），并能识别噪声。

DBSCAN（Density-based Spatial Clustering of Applications with Noise)[9]是一种代表性的聚类算法，其基本思想为：扫描整个数据样本集，选定一个核心点进行聚类，核心点邻域内的所有节点与核心点同属一个簇，并将这些节点作为下一轮扩充的种子节点，迭代聚类，直到找到所有与种子节点密度可达的点，形成一个完整的簇，重复此过程，直到所有种子节点聚类完成。对于数据样本中未聚类的点，继续如上过程，直到所有核心节点聚类过程完成，剩余未聚类的点成为噪声节点。

3.2.2 电力网络聚类算法MDBSC

电力网络中划分后的区域可以看作聚类算法中的簇。虽然网络拓扑中节点密度的特征没有那么明显，但可以通过指定网络跳数作为稀疏的另一种度量，即拓扑中节点之间的跳数作为衡量密度的距离指标。节点同时考虑网络跳数和空间地理位置因素的情况下，每个路由器节点维护一组2维空间数据,表示此节点r与网络中其他节点v 的关系。其中hops表示与目标节点的拓扑距离（网络跳数），dist表示与目标节点的地理空间距离。为简化节点数据取样复杂度，当dist超过一定距离值后，dist等于1，否则dist取值为0。

MDBSC具体的算法描述如下：

1)输入：

2)输出：

DV=｛dv1,dv2,...,dvk｝，代表区域划分的簇集合，以及边界路由器集合

（1）阈值MinPts的确定。考虑链路负载均衡，若MinPts值过大，减少聚类的数目，每个区域集合规模过大，达不到区域划分降低流量和快速收敛的目的。若MinPts值过小，区域数目过多，区域规模过小同样不利于快速收敛的实现。假设电力网络拓扑中节点个数为N ，骨干区域核心节点RC一跳相连的邻居节点个数为M ，负载均衡值为N/M，考虑集合规模为跳的情况下，可设

（2）在区域数量不确定的情况下，选定某些节点作为聚类过程的汇聚节点，称为核心节点（核心点）。中的所有元素均为待选举的核心对象节点，若给定对象E领域内节点元素数量超过一定的阈值MinPts，则将该节点选作核心节点。

对于任意路由节点r∈NB，以E等于一跳邻居距离为半径，即采用欧几里得距离计算方式时，值为1，计算此节点的E 领域集合E（r），若E（r）中包含的元素个数满足核心对象节点的选举条件，则r成为核心对象节点。

（3）核心节点r的E领域E（r）中的所有直接密度可达节点中任意节点v ，作为种子节点寻找所有与之直接密度可达的节点集合W，即W中所有节点与节点r两跳密度可达。中间涉及一些两跳密度可达节点的合并。

（4）重复步骤（2）中的过程，直到所有种子节点聚类过程完成。此时与节点r同属一个区域的被标记节点中有可能包含骨干区域A0的节点，相应的这些交集节点成为区域与骨干区域的边界路由器节点，加入边界路由器集合。NB中未被进行区域划分的其他节点，暂时标记为自由节点。

（5）对于NB中选举的其他核心节点，重复步骤（2），（3），遍历所有核心节点E领域的聚类（区域划分）过程，所有遍历过的节点中，与r直接密度可达或者两跳密度可达的节点组成以r为核心节点的区域（簇）。

（6）步骤（3）中被标记为自由节点的路由器在遍历所有k个核心节点的过程中部分可能会转换为已聚类节点，在此过程中如果出现某一个已聚类节点同时满足另一个核心节点的区域划分条件，则此节点自动成为两个区域的边界路由器节点ABR，即同时属于两个区域集合。

（7）步骤（4）结束后，自由节点通过查询自身维护的一跳邻居集合，选中相距dist等于0的任意一个节点所属区域（簇）dvi为 自由节点的区域（簇）。

以上算法大致描述了聚类（区域划分）过程，完成了对整个网络拓扑的区域划分。返回达到密度要求的区域集合如图2所示，形成Area1区域和Area2区域。当网络中有新节点加入时，根据新节点与边界路由器集合中元素拓扑距离，并比较其直接相邻的路由器节点的主要归属区域，分别计算节点与计算目标区域的相关度，作为区域选择的依据，即相关度最高的区域作为此新加入节点的归属区域。

4 实验

4.1 实验设置

模拟仿真实验采用的网络拓扑为芜湖市电力通信网络的真实广域网拓扑，包括66个子网络节点（支持OSPF协议的路由器节点和三层交换机节点）。实验通过两个步骤来验证，首先将网络拓扑中的节点信息初始化成为数据集合的形式，作为算法的输入，对拓扑中的节点进行区域集合划分。其次，依据上个步骤得到的数据集合，通过OSPF协议验证的网络仿真模拟器，对节点进行IP、接口、区域、网关等配置，并仿真运行OSPF协议。论文中针对协议的性能仿真主要是从路由协议网络收敛性，协议开销方面进行仿真分析，将为划分区域的原始拓扑图作为实验比较对象。

实验的仿真平台基于Visio Studio 2013和OPNET Modeler 14.5，分别用来进行区域划分和OSPF路由协议的仿真。拓扑规模设定为100km×100km大小，路由器间节点链接设置为100Base-T局域网链路，默认每个节点为100Base_TLAN逻辑子网的出口。

4.2 实验运行结果与分析

通过对基于密度的聚类算法DBSCAN进行改进，提出电力网络区域划分的MDBSC算法，实验结果如图3、图4及图5。

图3 OSPF协议路由收敛仿真结果

图4 OSPF协议开销仿真结果（区域划分后）

图5 OSPF协议开销仿真结果（区域划分前）

结合图3的OSPF.Total OSPF Protocol Traffic Sent和 OSPF.Network Convergence Activity可以看到，OSPF网络在仿真进行25秒后开始，在大约100秒时结束，收敛周期大概为75秒，这与OSPF.Network Convergence Duration中显示的大概75秒的周期是一致的，结果显示的收敛周期对于100km×100km规模的企业网络而言，是合理且较为高效的。

从图4的OSPF.Total OSPF Protocol Traffic Sent中可以看出，在OSPF网络收敛周期内，路由数据交换的数据量较大，图4维持在300000～400000bit/s的特定区间内。图5峰值时期数据交换量达到550000bit/s，这是因为OSPF在区域划分的条件下区域内的路由器只需要与区域内路由通信，而不需要洪泛到整个网络拓扑，减少了OSPF形成稳定路由过程中的协议开销。OSPF达到收敛状态后，数据交换量趋于稳定，维持在一个较低的水平，整体的开销也处于一种较低的水平。从图4、图5的对比可以看出，区域划分对提高网络收敛速度，减少协议开销方面的有利影响。

5 结束语

为解决大规模电力通信网络中OSPF区域划分问题，研究提出一种改进的基于网络密度聚类的区域划分算法，并在此基础上实施OSPF协议。算法在大规模复杂网络条件下能较好的实现自动区域划分，避免了对网管经验的过分依赖。算法首先通过周期性信息交换获得一跳邻居信息，然后参考网络跳数和地理位置进行聚类分簇，完成初始区域划分。考虑到网络负载均衡的问题，需要对划分进行细化。区域中节点数量阈值，仍有待于更加准确的测算。

[1]郑金华,蔡自兴.自动区域划分的分区域搜索狭义遗传算法[J].计算机研究与发展,2000,37(4):397-400.ZHENG Jinhua,CAI Zixing.Restricted genetic algorithm of area searching based on automatic area parting[J].Journal of ComputerResearchandDevelopment,2000,37(4):397-400.

[2]张丹丹.基于PSO-加权Kruskal算法的城市电网高压变电站规划[D].济南：山东大学,2012.ZHANG Dandan.High voltage substation planning of urban electric power networks based on PSO-weighted Kruskal algorithm[D].Jinan:Shandong University,2012.

[3]肖迎杰.改进的ZRP路由协议的研究[D].山东大学，2009.XIAO Yingjie.The research based on the improved ZRP routing protocol[D].Shandong University,2009.

[4]付光辉.基于簇域机制的ZRP改进研究[D].西南大学,2011.FU Guanghui.The research of the zone routing protocol based on cluster[D].Southwest University,2011.

[5]胡海洋,许旭,胡华.虚拟环境中一种基于密度聚类的区域划分算法[J].系统仿真学报,2012,24(9):1868-1872.HU Haiyang,XU Xu,HU hua.Density-based clustering approach for partitioning avatars in vitual environments[J].Journal of System Simulation,2012,24(9):1868-1872.

[6]杨帆,米红.一种基于网格的空间聚类方法在区域划分中的应用[J].测绘科学,2007,32(S1):66-69.YANG Fan,MI Hong.A grid-based spatial clustering algorithm for zone parting[J].Science of Surveying and Mapping,2007,32(S1):66-69.

[7]夏少波,连丽君,邹建梅,等.基于区域划分的DV-Hop定位算法的改进[J].山东科学,2015,28(3):110-116.XIA Shaobo,LIAN Lijun,ZOU Jianmei,et al.The improvement for DV-Hop localization algorithm based on regional division[J].Shandong Science,2015,28(3):110-116.

[8]谢珊珊,白光伟,曹磊.基于区域划分的连通支配集协议[J].计算机工程与设计,2012,33(4):1319-1323.XIE Shanshan,BAI Guangwei,CAO Lei.Protocols of determining connected dominating sets based on region partition[J].Computer Engineering and Design,2012,33(4):1319-1323.

[9]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//International Conference on Knowledge Discovery and Data Mining.AAAI Press,1996:226-231.