CN114124716A - 面向软件定义网络的均衡分域方法 - Google Patents

Abstract

本发明公开的一种面向软件定义网络的均衡分域方法，旨在提供一种收敛快、效率高、能减小网络控制时延，提升网络性能的均衡分域方法，本发明通过下述技术方案实现：在给定网络拓扑、节点位置、预估的流量矩阵和单个域允许的最大规模后，执行基于K均值算法框架的初始分域阶段，使用宽度优先的图遍历初始化分布的域中心节点，反复进行距离优先的域增长和域中心节点更新；在初始分域结果的基础上执行基于商图的局部调优阶段，将分域结果中域边界节点在相邻域的移动进行的局部调优转换为商图，反复在分域结果转换得到的商图上寻找负权环或计算最小成本路径，直到商图中无负权环且分域结果达到绝对均衡为止，实现目标函数的优化和保证域规模的绝对均衡。

Description

面向软件定义网络的均衡分域方法

技术领域

本发明属于通信网络拓扑分域领域，涉及网络路由域或管理域划分、无线自组网分 簇方法。

背景技术

随着网络技术的进步和新的应用场景的出现，通信网络的规模越来越大。网络规模 过大，对网络的管理与控制算法的可扩展性带来了严峻的挑战，因此，通常需要将规模过大 的网络划分为多个规模较小的路由域(或管理域)，以便于网络的管理与控制。现有的分域 (或分簇)算法主要针对传统的分布式通信网络设计，受通信开销、计算资源与功耗预算的 限制，无法确保分域的均衡性，导致分域结果中域的规模差异很大、网络资源得不到均衡利 用，加剧了网络的局部拥塞和局部电量的过度使用，对整个网络性能和生命周期造成了不利 影响。软件定义网络(Software Defined Network,SDN)，通过将控制逻辑从网络设备中剥离并 集中到网络控制器，实现了控制平面与数据平面的分离，网络也由传统的分布式控制转变为 集中式控制。随着相关技术的不断发展，SDN技术的应用不再仅仅局限于校园网、数据中 心网络等小型网络，更大规模的SDN组网已经成为当前的研究热点。软件定义网络技术在 固网与无线网络的兴起，对大网分域提出了新的需求，主要包括：域规模尽量均衡，这样有 利于实现域控制器的负载均衡和提升整网性能或生命周期；域节点在空间分布上尽量集中且 具有凸包特征，这样有利用减小域控制器到域内节点的最大与平均控制时延；预估的网络流 量尽量集中在域内，这样可减小域间路由对域控制器之间信息同步开销和减小路由的响应时 间。此外，软件定义网络通过逻辑集中的控制平面对全网进行集中式管控，与传统的分布式 控制相比可大大减小控制开销，而且，网络控制器通常具有更强的计算资源与更大的功率预 算，因此可打破分布式控制对传统分域(或分簇)算法的限制，具有运行更复杂的分域算法 的能力。

软件定义网络中的均衡分域问题，是一个集中式的多目标均衡图划分问题。最经典 的大规模图划分算法是散列划分，即每个顶点首先赋予唯一的ID号，将图的顶点散列划分 到相应的分区中。采用散列方法进行图划分的优势在于简单且易于实现，不需要额外的开销， 分区的大小是均衡的。但是散列方法没有考虑到图的内部结构，顶点会被随机地划分到分区 中，没法保证分区规模的均衡性、分区内部的连通性和分区中节点分布尽量集中与凸包性。 传统的基于扩散的图划分算法，无法保证子图的节点空间分布的尽量集中和凸包特性。传统 的K均值聚类算法，节点选择加入距离最近的中心对应的域，可保证节点的空间分布的尽 量集中于凸包特性，但无法保证域节点的连通性和域规模的均衡性。

从数学的角度看，分域或图划分结果可表示为网络节点集合上的等价类，可导出网 络节点集合上的一个等价关系。商图是图论中的一个术语，它定义在图节点集合的等价关系 之上，商图中每个节点表示图节点集合的一个等价类，如果图节点的两个等价类所包含的节 点之间有连边，则商图中两个等价类对应的节点之间存在一条边。分域结果对应的商图为： 商图的每个节点对应分域结果中的1个域，商图中每条边对应两个相邻域之间存在域间链路。 商图可用于建模通过域边界节点移动的方式对分域结果进行的局部调优。现有的基于商图的 局部调优方法，以最小化割边作为唯一的优化目标，没有考虑域节点的空间分布和域内流量 的最大化和域节点的连通性，域边界节点移动后可能导致域节点不连通。

基于商图的局部调优的基本原理是将域边界节点的移动表示成商图，然后通过在商 图上使用最短路算法计算最小成本路径的方式找出代价最小的增加域规模均衡性的多个域边 界节点移动组合。基于商图的局部调优的难点在于商图边权值的设计。最短路算法能够正确 运行要求路径成本必须等于路径中每条边成本(即边权值)之和。对应到分域问题中，相当 于要求多个边界节点同时移动后目标函数的增量必须等于每个域边界节点单独移动后目标函 数的增量之和。然后，在要求域内节点空间分布尽量集中、域内流量尽量大的多目标均衡分 域问题中，这个条件是无法满足的，因为多个域边界节点同时移动会影响域中心节点的位置， 从而影响域边界节点到域中心节点的位置计算，多个域边界节点同时移动也会影响域内流量 的计算。换言之，直接将单个域边界节点移动后目标函数的增量作为商图中边的权值，会导 致商图上的最小路径成本与真实的多个域边界节点移动后目标函数的增量之间存在偏差，直 接的后果是导致局部调优过程中出现“死锁”问题，即：本轮迭代中节点v需要从域A移 动到域B，下轮迭代中节点v又需要从域B移动到域A，算法将出现死循环，分域结果将得 不到优化，域规模的均衡性也无法保证。

发明内容

本发明针对上述的软件定义网络中的集中式均衡分域问题和现有技术存在的不足之 处，提供一种收敛快、效率高、应用范围广、能保证域节点连通性和减小网络控制时延以及 提升网络性能的面向软件定义网络的均衡分域方法，解决了多个域边界节点同时移动时因精 确移动成本的相互依赖导致的“死锁”问题。

本发明实现上述目的一种面向软件定义网络的均衡分域方法，具有如下技术特征： 将面向软件定义网络的均衡分域分为两个阶段，阶段1：基于K均值聚类算法框架的初始分 域阶段；阶段2：基于商图的局部调优阶段；在给定网络拓扑、节点位置、预估的流量矩阵 和每个域允许的最大规模后，进行基于K均值算法框架的初始分域阶段，首先，根据网络节点数量和单个域允许的最大规模计算域的数量K,并从随机选择的一个节点出发，使用宽度优先的图遍历初始化K个分布较均匀的域中心节点，然后，反复进行距离优先的域增长和域中心节点更新，直到相邻两次迭代的分域结果完全相同为止，则得到K个域节点连通、空间分布集中，具有凸包特性的初始分域结果；在初始分域结果的基础上进行基于商图的局 部调优阶段，首先，将分域结果中域边界节点在相邻域的移动进行的局部调优过程建模为在 图论中的商图上计算最小成本路径的过程，然后，反复在分域结果转换得到的商图上寻找负 权环或计算最小成本路径，并在保证域节点连通性的条件下，根据负权环或最短路径执行同 时对1个或多个域边界节点的移动，直到商图中无负权环且分域结果达到绝对均衡为止，从 而实现目标函数的优化和保证域规模的绝对均衡。

阶段1，即基于K均值算法框架的初始分域阶段，其特征在于包含如下步骤：

步骤1：初始化域中心节点，即：阶段1首先根据给定的单个域允许的最大规模计算域数量 K，然后使用宽度优先图遍历随机初始化K个在空间上分布相对均匀的域中心节点。

步骤2：距离优先的域增长，即：阶段1使用距离优先图遍历，以K个域中心节点为起点，遍历网络拓扑图进行域增长，得到K个连通的、节点分布尽量集中、具有凸包特性 的域。

步骤3：收敛性判断，即：如果新得到的K个域与上次的K个域完全相同，表明已 经收敛，则已得到初始的分域结果，退出阶段1并转基于商图的局部调优阶段(即步骤5)； 否则，继续执行步骤4。

步骤4：更新域中心节点，即：阶段1计算每个域的所有节点位置的算术平均值得到K个域的中心位置，然后选离中心位置最近的节点作为新的域中心节点；转步骤2。

阶段2，即基于商图的局部调优阶段，其特征在于包含如下步骤：

步骤5：构造商图，即：阶段2根据分域结果中域边界节点在相邻域间的移动构造商图；在 商图中，每个节点表示1个域，每条有向边e_ij表示域i的域边界节点v移动到相邻的域j，边权值w_ij表示v从域i移动到域j的移动成本；移动成本的计算同时考虑了域边界节点与域中心节点的距离、和域边界节点与域中其它节点之间的流量，且具有线性可加性，可防止基于商图的局部调优出现“死锁”；如果域i有多个域边界节点与域j相邻，则v为移动成本最小域边界节点；为了保证域边界节点移动后域仍然是连通的，商图中的边对应的域边界节点 不能是禁忌列表中的割节点。

步骤6：负权环检测，即：阶段2使用SPFA算法在商图中进行负权环检测，负权环 对应可以提升优度、且保持或提升当前分域结果均衡性的1个或多个域边界节点移动；如果找到负权环，则转步骤9；否则，继续执行步骤7。

步骤7：域规模绝对均衡判断，即：如果当前的K个域的规模已经达到绝对均衡，表明已得到绝对均衡、且无法进一步调优的分域结果，退出阶段2；否则，继续执行步骤8。

步骤8：更新商图，然后在更新后的商图上计算最小成本路径，该路径对应可增加域 的均衡性且具有最小成本的1个或多个域边界节点移动。

步骤9：域边界节点移动，即：阶段2首先检测负权环或最小成本路径中每个条边对应的域边界节点是否是域的割节点，如果检测出割节点，则将割节点加入禁忌列表，转步骤5；否则，按负权环或最小成本路径实施域边界节点移动，得到更新后的分域结果，并检测有域边界节点移入或移出的域在禁忌列表中的节点是否为割节点，如果不是割节点了，则将 其从禁忌列表中移除，转步骤5。

本发明相比于现有技术具有如下有益效果：

收敛快。本发明利用本发明可将规模过大的通信网络划分为多个规模绝对均衡的路由域(或 管理域)，同时保证每个域节点的连通性、域边界节点及其连边组成凸多边性(即图包特性)， 达到域节点分布集中和最大化域内流量的目的。使用上述的宽度优先的图遍历初始化K个 中心节点，可使中心节点分布尽量均匀，有利于加快收敛；解决了传统的K均值聚类算法， 随机选择K个节点作为中心，无法保证K个中心节点分布相对均匀，可能导致需要更多的 迭代才能收敛的问题。

保证域节点连通性。本发明使用上述的距离优先图遍历进行域增长得到的是K个路 径树，可保证每个域中的节点是连通的；在域边界节点移动前，先检测域边界节点是否是割 节点，并通过禁忌列表禁止割节点的移动，确保了域边界节点移动过程中域节点的连通性； 解决了传统的K均值聚类算法和传统的基于商图的局部调优，无法保证域节点的连通性的 问题。

减小网络控制时延。本发明使用上述的距离优先图遍历进行域增长方法，可保证每 个域的节点分布尽量集中和凸包特性(即域边界节点及其连边构成凸多边形)，有利于减小 域节点与域控制器的通信时延。

提升网络性能。本发明使用基于商图的局部调优，通过域边界节点在相邻域间的移 动可保证最终分域结果中域的规模绝对均衡，有利于域控制器的负载均衡、提升网络性能和 延长无线网络的生命周期；将最大化域内流量最为优化目标，可减少需要控制器之间协同路 由的域间流量，有利于全网的平均路由响应时间；解决了传统的K均值聚类算法无法保证 域规模的均衡性，分域结果中可能存在规模过大或过小的域弊端。

效率高。本发明通过将商图中边的权值设置为域边界节点移动成本，该移动成本是 根据目标函数计算的精确移动成本的上界，具有线性可加性，解决了多个域边界节点同时移 动时因精确移动成本的相互依赖导致的“死锁”问题，实现了每次同时移动多个域边界节点， 提高了局部调优的效率。

应用范围广。本发明提出的面向软件定义网络的均衡分域方法，可用于软件定义光 传送网(即TSDN)的路由域划分、软件定义蜂群无人机网络的分簇等场景。

附图说明

下面结合附图对本发明进一步说明。

图1是本发明提出的面向软件定义网络的均衡分域的流程图。

图2是本发明提出的基于商图的局部调优示例图。

图3是本发明仿真验证100个节点网格状网络得到的分域示意图。

图4是本发明仿真验证500个节点的随机网络得到的分域示意图。

为使本发明要解决的技术问题、技术方案和要点更加清楚，下面将结合附图及具体 实施例进行详细描述。

具体实施方式

参阅图1。根据本发明，将面向软件定义网络的均衡分域分为两个阶段，阶段1：基于K均值聚类算法框架的初始分域阶段；阶段2：基于商图的局部调优阶段；在给定网络拓扑、节点位置、预估的流量矩阵和每个域允许的最大规模后，进行基于K均值算法框架的 初始分域阶段，首先，根据网络节点数量和单个域允许的最大规模计算域的数量K,并从随 机选择的一个节点出发，使用宽度优先的图遍历初始化K个分布较均匀的域中心节点，然 后，反复进行距离优先的域增长和域中心节点更新，直到相邻两次迭代的分域结果完全相同为止，则得到K个域节点连通、空间分布集中，具有凸包特性的初始分域结果；在初始分 域结果的基础上进行基于商图的局部调优阶段，首先，将分域结果中域边界节点在相邻域的移动进行的局部调优过程建模为在图论中的商图上计算最小成本路径的过程，然后，反复在 分域结果转换得到的商图上寻找负权环或计算最小成本路径，并在保证域节点连通性的条件 下，根据负权环或最短路径执行同时对1个或多个域边界节点的移动，直到商图中无负权环 且分域结果达到绝对均衡为止，从而实现目标函数的优化和保证域规模的绝对均衡。

阶段1：基于K均值算法框架的初始分域阶段包含如下步骤：

步骤1：初始化域中心节点，即：阶段1首先根据给定的单个域允许的最大规模计算域数量 K，然后使用宽度优先图遍历随机初始化K个在空间上分布相对均匀的域中心节点；

步骤2：距离优先的域增长，即：阶段1使用距离优先图遍历，以K个域中心节点为起点，遍历网络拓扑图进行域增长，得到K个连通的、节点分布尽量集中、具有凸包特性的域。

步骤3：收敛性判断，即：如果新得到的K个域与上次的K个域完全相同，表明已 经收敛，则已得到初始的分域结果，退出阶段1并转基于商图的局部调优阶段(即步骤5)； 否则，继续执行步骤4。

步骤4：更新域中心节点，即：阶段1计算每个域的所有节点位置的算术平均值得到K个域的中心位置，然后选离中心位置最近的节点作为新的域中心节点；转步骤2。

阶段2，即基于商图的局部调优阶段，包含如下步骤：

步骤5：构造商图，即：阶段2根据分域结果中域边界节点在相邻域间的移动构造商图；在 商图中，每个节点表示1个域，每条有向边e_ij表示域i的域边界节点v移动到相邻的域j，边权值w_ij表示v从域i移动到域j的移动成本；移动成本的计算同时考虑了域边界节点与域中心节点的距离、和域边界节点与域中其它节点之间的流量，且具有线性可加性，可防止基于商图的局部调优出现“死锁”；如果域i有多个域边界节点与域j相邻，则v为移动成本最小域边界节点；为了保证域边界节点移动后域仍然是连通的，商图中的边对应的域边界节点 不能是禁忌列表中的割节点。

步骤6：负权环检测，即：阶段2使用最短路快速算法SPFA在商图中进行负权环检测，负权环对应可以提升优度、且保持或提升当前分域结果均衡性的1个或多个域边界节点移动；如果找到负权环，则转步骤9；否则，继续执行步骤7。

步骤7：域规模绝对均衡判断，即：如果当前的K个域的规模已经达到绝对均衡，表明已得到绝对均衡、且无法进一步调优的分域结果，退出阶段2；否则，继续执行步骤8。

步骤8：更新商图，然后在更新后的商图上计算最小成本路径，该路径对应可增加域 的均衡性且具有最小成本的1个或多个域边界节点移动。

步骤9：域边界节点移动，即：阶段2首先检测负权环或最小成本路径中每个条边对应的域边界节点是否是域的割节点，如果检测出割节点，则将割节点加入禁忌列表，转步骤5；否则，按负权环或最小成本路径实施域边界节点移动，得到更新后的分域结果，并检测有域边界节点移入或移出的域在禁忌列表中的节点是否为割节点，如果不是割节点了，则将 其从禁忌列表中移除，转步骤5。

本实施例的初始化域中心节点具体方法为：在初始化域中心节点中，首先，根据网络 的节点数量n和每个域允许的最大规模m，计算出域数量K，当分域结果中K个域的节点数量 都为

或

且K个域的节点数量总和为n时，则该分域是绝对均衡的，即

然后，随机初始化K个域中心：从网络的n个节点中，随机选择1个节点作为种子节点，以 种子节点为起点进行宽度优先图遍历，将最后1个被遍历的节点作为第1个域中心节点，接 下来，同时以当前已有的k个域中心节点为起点进行宽度优先图遍历，把最后1个被遍历的 节点作为第k+1个域中心节点，从k＝1开始重复以上过程，直到找到K个域中心节点，其中，

表示向上取整，

表示向下取整。通过以上方法随机初始化K个域中心节点，可使域中心 节点在网络中分布更均匀，有利于基于K均值算法框架的初始化分域的快速收敛。

在可选的本实施例中，为了保证分域结果中域节点在空间上分布尽量集中以及域节 点的凸包特性，在距离优先的域增长同时以节点到域中心节点的物理距离进行距离优先图遍 历搜索，将得到以K个域中心节点为根的K棵路径树，对应的节点作为此轮迭代的分域结 果，并将域中心节点的距离值都为0的K个域中心节点加入以距离为键值的优先队列，第k 个域中心节点加入第k个域；并从优先队列中取出距离值最小的节点v，从v的邻节点中， 找出没有加入任何域的节点，将这些节点加入v所在的域，并计算这些节点到所加入域的域 中心节点的距离值，最后将这些节点加入优先队列，重复上述过程，直到优先队列为空。

距离优先的域增长具体方法为：同时以K个域中心节点为起点，使用距离优先图遍历，得到以K个域中心节点为根的K棵路径树，对应的节点作为此轮迭代的分域结果。以 节点到域中心节点的物理距离进行距离优先搜索，是为了保证分域结果中域节点在空间上分布尽量集中以及域节点的凸包特性。上述的距离优先图遍历方法，包括如下步骤：

(1)将K个域中心节点加入以距离为键值的优先队列，域中心节点的距离值都为0，第k个域 中心节点加入第k个域；

(2)从优先队列中取出距离值最小的节点v，从v的邻节点中，找出没有加入任何域的节点， 将这些节点加入v所在的域，并计算这些节点到所加入域的域中心节点的距离值，最后将这 些节点加入优先队列。重复第(2)步骤直到优先队列为空。

本实施例的更新域中心节点的具体方法为：对K个域的每个域，通过计算域中所有节点位置的算法平均值作为域中心位置，然后找离中心位置最近的节点作为新的域中心节点。 当域中节点数量过大时，计算每个节点到中心位置的距离比较耗时。为了解决此问题，本实 施例使用宽度优先遍历以原域中心节点为起点寻找可调参数k₁个节点作为新域中心节点的 候选节点，然后从候选节点中找一个离中心位置最近的节点作为新的中心节点。注意k₁是 一个可调参数，除优化计算新的域中心节点的时间性能外，还可限制新的域中心节点与原来 的域中心节点的差异大小，有利于网络拓扑变化后在原来的分域结果上做渐近的增量分域。

参阅图2。在基于K均值聚类算法框架的初始分域阶段将18个节点的网络划分为A、B、C3个域，域规模分别为8、4、6。然后构造分域结果对应的商图，在商图中，每个节点 代表1个域，从域B到域A的有向边权值表示从域B移动1个域边界节点到域A的最小成 本，移动成本代表节点移动后目标函数的近似增加量。负权环A-B-C-A表示保持域规模不 变，且可减少目标函数值(减少7)的域边界节点移动组合，即：从域A移动1个节点到域 B，从域B移动一个节点到域C，从域C移动一个节点到域A，移动完成后域规模不变，依 然分别为8、4、6。为了便于寻找负权环，在商图中加入虚节点s和s到其它节点的虚边、 以及规模过小的域B到虚节点s的虚边，虚边不表示节点移动，因此移动代价为0。然后以 虚节点s为起点，使用SPFA算法寻找负权环。包含虚节点s的负权环s-C-B-s,表示从域C 移动一个节点到域B，既可减少目标函数值(减少5)，也可提升域规模的均衡性(域C变 小、域B变大)。如果商图中无负权环，则需要更新商图，在商图中增加虚节点t,虚节点s 改为只连向规模过大的域对应的节点A，规模过小的域对应的节点B连向虚节点t。然后计 算从s到t的最小成本路径s-A-C-B-t,表示从域A移动1个节点到域C，从域C移动1个节 点到域B，从而以最小的代价1提升域规模的均衡性。

在可选实施例中，构建商图的具体步骤为：

(1)在分域结果中寻找每个域的域边界节点，从找到的域边界节点中去除掉禁忌列表包含的 割节点，然后将剩余的域边界节点按其邻接的域进行分组，用B_ij表示域i中与域j邻接的所 有边界节点；注意，某个域i的域边界节点v可同时邻接多个邻域，即与多个域的域边界节 点有连边。

(2)对以上的每个组B_ij的每个域边界节点v计算移动成本(即节点v从域i移动到域j， 目标函数的近似增加量)。

(3)构造商图，商图中的每个节点对应1个域，每条有向边e_ij对应上述的域边界节点 组B_ij，表示B_ij中移动成本最小的节点v从域i移入域j，边权值w_ij为对应的最小移动成本。

(4)向商图中添加虚节点s，s与商图中的其余节点分别通过一条有向边相连，规模过小 的域对应的节点与s分别通过一条有向边相连；虚节点s只作为后面寻找负权环的起点，无 对应的域，s的邻边权值都为0，无对应的域边界节点移动；注意：规模过小是指域规模小于

或当所有域规模都不小于

时域规模等于

在可选实施例中，负权环检测的具体方法为：在商图中以虚节点s为起点，使用业界 已有的SPFA算法进行负权环检测。SPFA即最短路快速算法是Bellman-Ford算法的队列优 化版本实现，具有负权环检测能力。商图中有两种负权环，一种不包含虚节点s，另外一种 负权环包含虚节点s。不包含虚节点s的负权环对应可保证域规模不变的2个或多个域边界 节点的移动组合。包含虚节点s的负权环对应的是可改善域规模均衡性的1个或多个域边界 节点的移动组合。两种负权环都可让分域问题的目标函数减小，即让分域结果的优度得到提 升。

在可选实施例中，更新商图的具体方法为：从商图中移除虚节点s的所有邻边，然后 向商图中增加从虚节点s到所有规模过大的域所对应的节点的有向边，边权值为0，这些变 不对应节点的移动。向商图中增加虚节点t，以及规模过小的域所对应的节点到虚节点t的 有向边，边权值为0，这些变也不对应边界节点的移动。注意：规模过大是指域规模大于或 当所有域规模都不大于时域规模等于。

在可选实施例中，域边界节点移动的具体方法为：检测负权环或最小成本路径中是 否有割节点的移动，如果有则将对应的割节点加入到禁忌列表中，不执行节点移动直接进入 下一轮迭代。如果没有检测到割节点移动，则执行负权环或最小成本路径的每条边所对应的 域边界节点移动，得到新的分域结果，并重新检测有变化(即有域边界节点移出或移入)的 域在禁忌列表中的域边界节点是否仍然是割节点，如果不再是割节点则将其从禁忌列表中移 除，然后进行下一轮迭代。

以上为本实施例面向软件定义网络的均衡分域方法的详细描述，现介绍本发明最核 心方法，即域边界节点移动成本计算方法。前面提到域边界节点的移动成本是指节点移动后 目标函数值的增加量，可能为正也可能为负。这里的目标函数是指分域问题的目标函数，由 两部分组成：每个节点到其所在域的域中心节点的距离之和，用于刻画域内节点空间分布的 集中程度，越小越好；全网的域内流量总和，越大越好。注意：域内节点的凸包特性是通过 这两部分相对大小保证的，当第1部分的值远远大小第2部分的值时，可保证域内节点的凸 包特性。域内流量是根据作为已知输入的流量矩阵计算的，该流量矩阵是事先估算的网络的 流量矩阵，可从网络规划工具中获得。直接使用商图进行局部调优导致的“死锁”问题，原 因在于商图中路径成本即可能高估也可能低估真实的多个域边界节点移动成本，通过合理设 计商图中边权值，让商图中路径成本是真实的多个域边界节点移动成本的上界可避免“死 锁”。

本实施例通过以下方法估算域边界节点移动成本，解决上述的“死锁”问题。域边界 节点v从域i移动到域j的成本c_v,i→j计算公式为：

其中：α为目标函数中的比例系数，可选取值范围为α∈[100,1000]；1/A,1/B为目标函数中的距离和流量的归一化系数，A为全网1个域时每个节点到所有节点的位置中心点的距离之和，B为全网的总流量；

和

分别为域边界节点v到分域结果中域j的中心节点和域i的中心节点的距离；

和

分别为域边界节点v与域j和域i中其余节点流量之和；

和

分别为域j中的节点到v的流量的最大值、域i之外的节点到v的流量的最大值。上述计算公式已通过理论推导证明是真实移动成本的上界。

参阅图3。使用面向软件定义网络的均衡分域方法对100个节点组成的网格网络进行 分域。每个节点与上下左右方向的4个节点相邻，距离为300km，每个域允许的最大规模为 20，随机生成500个带宽为0～100Mbps均匀分布的流量需求。仿真结果中，不同域的节点用不同的形状表示，网络中的100个节点被分成5个绝对均衡的域，每个域20个节点，域 节点连通、空间分布集中，且具有凸包性。

参阅图4。使用面向软件定义网络的均衡分域方法对500个位置在[1,4000]km范围内 均匀分布的节点组成的随机网络进行分域。每个节点与350km内的节点相邻，每个域允许 的最大规模为85，随机生成2000个带宽为0～100Mbps均匀分布的流量需求。仿真结果中， 网络中的500个节点被分成6个绝对均衡的域，不同域的节点用不同的形状表示，域规模分 别为84，84，83，83，83，83，域节点连通、空间分布集中，且具有凸包性。

以上所述仅为本发明的较佳实施例，对本发明而言仅仅是说明性的，而非限制性的。 本专业技术人员理解，在本发明权利要求所限定的精神和范围内可对其进行许多改变、修改、 甚至等效，但都将落入本发明的保护范围内。

Claims (10)

1.一种面向软件定义网络的均衡分域方法，具有如下技术特征：将面向软件定义网络的均衡分域分为两个阶段，阶段1：基于K均值聚类算法框架的初始分域阶段；阶段2：基于商图的局部调优阶段；在给定网络拓扑、节点位置、预估的流量矩阵和每个域允许的最大规模后，进行基于K均值算法框架的初始分域阶段，首先，根据网络节点数量和单个域允许的最大规模计算域的数量K,并从随机选择的一个节点出发，使用宽度优先的图遍历初始化K个分布较均匀的域中心节点，然后，反复进行距离优先的域增长和域中心节点更新，直到相邻两次迭代的分域结果完全相同为止，得到K个域节点连通、空间分布集中，具有凸包特性的初始分域结果；在初始分域结果的基础上进行基于商图的局部调优阶段，首先，将分域结果中域边界节点在相邻域的移动进行的局部调优过程建模为在图论中的商图上计算最小成本路径的过程，然后，反复在分域结果转换得到的商图上寻找负权环或计算最小成本路径，并在保证域节点连通性的条件下，根据负权环或最短路径执行同时对1个或多个域边界节点的移动，直到商图中无负权环且分域结果达到绝对均衡为止，从而实现目标函数的优化和保证域规模的绝对均衡。

2.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：基于K均值算法框架的初始分域阶段，初始化域中心节点，首先根据网络的节点数和给定的单个域允许的最大规模计算域数量K，然后从随机选择的节点开始，使用宽度优先图遍历随机初始化K个在空间上分布相对均匀的域中心节点。

3.如权利要求2所述的面向软件定义网络的均衡分域方法，其特征在于：在初始化中心节点后使用距离优先图遍历，以K个域中心节点为起点，遍历网络拓扑图进行距离优先的域增长。

4.如权利要求3所述的面向软件定义网络的均衡分域方法，其特征在于：根据距离优先的域增长对初始化分域进行快速收敛性判断，如果新得到的K个域与上次的K个域完全相同，表明初始化分域已经收敛，则已得到初始的分域结果，退出阶段1并转基于商图的局部调优阶段；否则，更新域中心节点，计算每个域的所有节点位置的算术平均值，获取K个域的中心位置，然后选离中心位置最近的节点作为新的域中心节点，返回距离优先的域增长，继续进行收敛性判断。

5.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：在分域结果收敛后进入部调优阶段，根据分域结果中域边界节点在相邻域间的移动构造商图；在商图中，如果域i有多个域边界节点与域j相邻，则v为移动成本最小域边界节点，每个节点表示1个域，每条有向边e_ij表示域i的域边界节点v移动到相邻的域j，边权值w_ij表示v从域i移动到域j的移动成本；为了保证域边界节点移动后域仍然是连通的，商图中的边对应的域边界节点不能是禁忌列表中的割节点。

6.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：在负权环检测中，使用最短路快速算法SPFA在商图中进行负权环检测，判断是否找到负权环，如果找到负权环，先对负权环的每条边对应的域边界节点进行割节点检测，如果发现割节点，则将其加入禁忌队列，转入构造商图，继续进行负权环检测；如果没有发现割节点，执行负权环对应的域边界节点移动，并检查有节点移入或移出的域在禁忌列表中的割节点是否仍然是割节点，将已经不是割节点的节点从禁忌列表中移除，转入构造商图，继续进行负权环检测。

7.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：如果没有找到负权环，执行域规模绝对均衡判断，如果当前的K个域的规模已经达到绝对均衡，表明已得到绝对均衡、且无法进一步调优的分域结果，退出阶段2，否则，更新商图，在更新后的商图上计算最小成本路径，对先对最小成本路径中的每条边对应的域边界节点进行割节点检测，如果发现割节点，则将其加入禁忌队列，转入构造商图，继续进行负权环检测；如果没有发现割节点，执行最小成本路径对应的域边界节点移动，并检查有节点移入或移出的域在禁忌列表中的割节点是否仍然是割节点，将已经不是割节点的节点从禁忌列表中移除，转入构造商图，继续进行负权环检测。

8.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：在初始化域中心节点中，首先，根据网络的节点数量n和每个域允许的最大规模m，计算出域数量K，当分域结果中K个域的节点数量都为

或

且K个域的节点数量总和为n时，则该分域是绝对均衡的，即

然后，随机初始化K个域中心：从网络的n个节点中，随机选择1个节点作为种子节点，以种子节点为起点进行宽度优先图遍历，将被遍历的节点作为第1个域中心节点，同时以当前已有的k个域中心节点为起点进行宽度优先图遍历，把被遍历的节点作为第k+1个域中心节点，从k＝1开始重复以上过程，直到找到K个域中心节点，其中，

表示向上取整，

表示向下取整。

9.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：为了保证分域结果中域节点在空间上分布尽量集中以及域节点的凸包特性，在距离优先的域增长同时以节点到域中心节点的物理距离进行距离优先图遍历搜索，将得到以K个域中心节点为根的K棵路径树，对应的节点作为此轮迭代的分域结果，并将域中心节点的距离值都为0的K个域中心节点加入以距离为键值的优先队列，第k个域中心节点加入第k个域；并从优先队列中取出距离值最小的节点v，从v的邻节点中，找出没有加入任何域的节点，将这些节点加入v所在的域，并计算这些节点到所加入域的域中心节点的距离值，最后将这些节点加入优先队列，重复上述过程，直到优先队列为空。

10.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：域边界节点v从域i移动到域j的成本c_v,i→j计算公式为：

其中：α为目标函数中的比例系数，A为全网1个域时每个节点到所有节点的位置中心点的距离之和，B为全网的总流量；

和

分别为域边界节点v到分域结果中域j的中心节点和域i的中心节点的距离；

和

分别为域边界节点v与域j和域i中其余节点流量之和；

和

分别为域j中的节点到v的流量的最大值、域i之外的节点到v的流量的最大值。

Images