面向大规模多跳网络的虚拟网络拓扑控制方法

罗 涛，王宏波，徐永庆，李泽旭

(1.中国电子科技集团公司第七研究所 网络交换事业部，广东 广州 510310; 2.北京邮电大学 泛网无线通信教育部重点实验室,北京 100876)

随着无线网络技术的不断发展与进步，人类社会正在逐步朝万物互联的美好愿景迈进[1]。然而，海量物理通信设备的接入会严重制约现有通信网络系统内有效信息的识别准确性，并且进一步提升了对诸如节点位置、可用带宽等存在较强时效属性资源可管控方面的复杂度。因此，对物理网络信息资源直接管控的传统技术方案正在被逐步替代，由实体化向虚拟化的转变已成为未来通信网络发展的重要趋势。

虚拟网络是通过对实际物理网络内在逻辑关系进行抽象而得到的逻辑网络。相较于实体网络中节点的物理连接关系，虚拟网络能够更加灵活有效地进行统一化管理。因此，可以极大地降低多跳通信网络信息管理过程的复杂度。目前，国内外相关学者对虚拟网络的构建方法展开了大量研究[2-6]。文献[2]研究了无线多跳蜂窝网络内虚拟网络嵌入问题，通过建立虚拟网络嵌入模型充分利用网络资源，从而有效提高用户服务质量。文献[3]提出了一种虚拟网络资源管理方法以控制网络内的天线的发射功率，该方法能够在最小化虚拟网络之间的干扰的同时满足多用户需求。但是，现有的研究工作大多聚焦于虚拟网络到物理网络的映射[1]，缺乏对虚拟网络本身结构优化的研究。除此之外，对于虚拟网络业务与实体网络资源的映射的研究大多直接采用传统路径规划方案[7-11]，而对网络中业务分布与虚拟网络拓扑结构直接影响的相关研究也较少涉及。这些问题会导致虚拟网络构建不灵活、开销大及资源可用性差等问题。

复杂网络理论研究大规模网络拓扑结构与网络各项性能之间内在联系[12]。在通信网中构建良好的拓扑结构可有效延长网络生命周期，实现负载均衡，增强网络的鲁棒性[13-15]。因此，通过对虚拟网络节点间的连接关系进行调整就能有效优化拓扑结构，提升网络性能。小世界网络作为一类典型的复杂网络结构具有平均路径长度较小而聚类系数较大的特点。较小的平均路径能够提高节点间数据传输的效率，降低通信时延，减少节点能量消耗；较大的聚类系数可以提高网络的容错性，这些都是大规模多跳通信网络所期望的[16]。大规模多跳网络的虚拟网络结构具备小世界特性，有利于提升网络的性能。

针对多跳网络内拓扑连接关系与其主要面向业务的对应关系，拟提出一种能够根据当前业务需求及分布情况而自适应建立并调整虚拟网络连接关系与资源分配策略的虚拟网络拓扑控制方法。重点研究了面向专用网络的虚拟网络拓扑建立过程，用以解决虚拟网络构建开销大、资源用以配置不灵活的问题。该方法通过抽取物理网络信息、优化虚拟网络拓扑、资源自适应分配与虚拟资源的物理映射等步骤，以期能够有效减少虚拟网络构建过程的资源开销，为未来大型多跳通信系统的构建与管理提供一种新思路。

1 系统性能指标定义

针对复杂网络，通常使用无向图G(V,E)表示。其中：V表示网络节点集合；E表示网络中边的集合。同时，基于复杂网络理论，通常利用拓扑图G(V,E)的特征参数评估网络拓扑结构的性能。常见的网络拓扑特征参数包括以下4个方面。

2)网络直径。网络中任意两个节点之间距离的最大值，记为D，即D=max(di,j)。网络直径刻画了网络的最大信息传输时滞特性，在通信网络中，较小的平均路径长度和网络直径有利于优化网络的路由，减少资源开销。

4)介数。节点的介数是指网络中所有的最短路径中经过该节点的数量；边的介数含义与节点介数的含义类似。

相较于传统的物理网络拓扑，虚拟网络是对物理网络进行抽象后得到的逻辑网络。物理网络中通过多跳链路相连的两个节点，在虚拟网络中可以通过逻辑链路一跳相连。因此，基于物理网络的特征参数无法准确描述虚拟网络性能，需要在计算特征参数时结合网络虚实映射关系。

2 虚拟网络构建方法

根据组网请求中虚拟网络节点数量，可以将虚拟网络分为虚链路和虚拟网两种类型，其中虚链路请求需要为用户建立并维护端到端的虚拟链路形态，虚拟网请求需要为多用户提供能够两两互通的虚拟网络。传统虚拟网络构建方案大多基于虚链路的组合，通过在两两用户之间搭建虚链路实现虚拟网络的构建。然而，这种方法没有考虑网络节点的路由转发能力和业务分布，会导致虚拟网络构建开销大、冗余路径多和资源利用率低等问题。

为改善上述问题，基于小世界理论，针对虚拟网络链路效率与潜在业务需求的动态协调进行设计，提出一种灵活的虚拟网络构建方法。基于虚拟网络用户需求及资源池信息，首先，建立以虚拟网络用户为端节点的符合组网需求的虚拟网络拓扑，获取节点间最大链路能力。然后，基于多跳网络的小世界特性，对虚拟网络拓扑进行优化，在保证连通需求和网络效率的前提下，提高链路资源利用率，降低网络带宽开销。再通过网络资源自适应分配，结合节点路由转发能力灵活配置虚拟网络资源。最后，基于多跳网络物理拓扑结构及区域资源池信息，通过端到端的虚拟链路规划，实现虚拟网到物理资源的映射，完成整个虚拟网络构建。

2.1 建立虚拟网络拓扑

在虚拟网络的建立过程中，需要完成实体物理节点向逻辑虚拟网络的转化。逻辑网络在上报的物理信息中，将所需资源信息采取合并、删减和填充等方式进行抽象，构建虚拟资源池信息并采用归一化输出结果进行资源池数据库填充，从而完成虚拟网络的初步构建。

在网络拓扑结构的表达方式中，采用“节点”与“边”组成的图的方式是较为常见且直观的。网络的连通性、端到端的连接关系等通信网中较为关注的属性能够得到更为直观的表达。因此，需要进一步将虚拟资源池中的资源信息抽象为通过图表达的逻辑网络。在资源池中，由于物理节点之间存在多种连接关系，可采用图论中的最大流方法建立网络拓扑关系。假设域内节点数为M，虚拟网络用户数为N，经过资源抽象及虚拟化后，资源池矩阵维度由原始的M×M维降低至N×N维，可显著降低后续拓扑优化和资源分配复杂度。具体的虚拟逻辑网络构建过程如图1所示。

图1 虚拟逻辑网络构建过程

由图1可以看出，虚线表示的是节点间虚拟链路。在每两个虚拟节点之间建立一条直接相连的虚拟链路，作为虚拟网络的初始拓扑结构。

2.2 虚拟网络拓扑结构优化

虚拟网络拓扑优化是通过设计合理的网络拓扑结构，实现可用资源数与网络效率间的最优均衡。以网络效率阈值为限制条件，以最小化构建虚拟网络带宽开销为目标，从初始两两相连的拓扑结构出发，对虚拟网络进行遍历，保留效率较高的链路关系并剔除效率低的虚拟链路，从而将有限的资源更合理地分配至虚拟网络，在保证网络效率的同时尽可能简化虚拟网络拓扑结构。当算法获取到待优化的虚拟网络拓扑结构后，将获取网络系统内每条边的相关拓扑评估指标综合汇总其存在价值。

虚拟网络拓扑结构优化算法主要是基于在冗余链路中删除连接关系的思想进行拓扑优化。根据当前网络连接关系依次计算每条边在此拓扑下的介数，然后将当前网络内介数最低的一条边断开其两端节点的连接关系，从而得到新的网络连接关系，并重复该过程，直至某一边断开导致网络内通行效率为零。通过该方法的不断迭代，网络内对通信效率贡献相对较小的边先被断开，贡献较大的边后断开，从而保证了受限资源的有效分配。具体的基于小世界网络理论的拓扑优化算法的步骤如下。

步骤1获取当前网络连接关系。

步骤2依照边的索引值依次判定网络内是否存在孤立节点。如果是，则跳转至步骤6；如果否，则跳转步骤3。

步骤3依照节点的索引值，依次计算该节点至其他所有节点的最短路径，并且统计所有边在该节点所有最短路径内的出现次数。

步骤4统计当前网络拓扑的通信效率以及所有边的介数，并对边的介数进行逆序排列，最终删除介数最小的一条边。

步骤5更新网络拓扑结构，并返回步骤2。

步骤6输出统计结果。

为验证算法可行性，仿真构建18个节点的网络环境，验证基于小世界网络理论的拓扑优化算法有效性。在仿真系统中检验所提算法“剪除的边的数量”与“通信效率”的映射关系。在仿真实验中，直观地给出了通信效率与算法迭代剪除拓扑边结构数量的内在联系。具体的加权介数逆序剪边仿真结果如图2所示。

图2 加权介数逆序剪边仿真结果

由图2可以看出，仿真中存在两个明显的拐点，即图中“第一拐点”与“第二拐点”。第一拐点前，该网络拓扑通信效率随着虚拟网络边数减少降低的较缓慢，但是第一拐点后，通信效率下降速度明显增加，这是符合小世界网络理论的。该仿真结果证明了基于小世界网络特性相关理论的虚拟网络构建方法中，明显的拐点信息是存在的。而在第二拐点后网络无法保证全连通，因此通信效率骤降为0。仿真结果表明，所提拓扑优化算法能够在保证一定网络效率的同时，尽可能地减少虚拟网络边数，证明了该算法的有效性。

通过观察网络拓扑结构可以更加直观地认识其连接关系，不同连接关系下的网络拓扑结构如图3所示。

图3 加权介数逆序剪边仿真网络拓扑

由图2和图3可知，删除125条边后，网络仍能保证80%的网络效率。所提虚拟网络拓扑优化算法在保障一定网络性能的同时，能够显著简化网络拓扑，降低后续虚拟网络构建的带宽开销。

2.3 虚拟网络资源的自适应分配

虚拟网络资源自适应分配的主要任务是在完成初步的虚拟网络链路结构建立后，采用历史统计数据不断修正虚拟网络各条虚拟链路的资源配置。在该方法中，首先，基于构建好的虚拟网络拓扑结构计算能保证连通的初始化最低资源量，并为初始化拓扑的每条链路依次赋予等额带宽资源。其次，统计每条链路单位时间内传输的业务数量，将其作为链路价值函数衡量用户对不同虚拟链路的资源需求程度。根据统计数据自适应调整链路预留资源，为高价值虚拟链路赋予更多资源，以提升网络资源可用性。最后，将统计结果作为输入反馈的资源控制模块，从而指导下一批次的预留资源分配方法，即预留资源分配的数量与链路内并行业务数成正比。具体虚拟网络资源的自适应分配算法的步骤如下。

步骤1获取当前虚拟网络可分配虚拟资源总数，并计算维持虚拟网络最低资源数量。

步骤2在初始化时刻，将维持虚拟网络最低数量资源等额分配给每条虚链路。

步骤3统计每条虚拟链路单位时间内并行业务传输数量，将其作为链路价值函数。

步骤4将链路资源池内剩余资源按统计价值函数比例灵活分配给每条链路。

步骤5判断时刻是否结束，如果结束跳转至步骤6，否则返回到步骤3。

步骤6输出分配结果。

虚拟网络的自适应性优化策略的目的是保证普通业务与并行模式都能够在该网络内得到保证。其中，初始化时刻的虚拟网络链路资源应配置为能够满足最低组网需求，然后基于业务统计灵活分配预留资源逐渐自适应当前业务状况，最终成功实现整体虚拟网络的优化。

2.4 虚拟网络的实体映射

物理网络资源经过抽象、结构优化和资源分配过程后，得到了优质的虚拟连接关系，但实际作为物理业务载体的还是物理网络。因此，还需要完成由虚拟网络向实体物理网络的映射工作，才能真正承接节点真实业务。

在虚拟网络的拓扑结构中，每一条一跳直连的虚链路在物理网络中都是通过一跳或多跳连接的。那么，可以在每两个具有虚拟连接关系的节点之间寻找最优物理路径。因此，虚拟网络的映射过程实际上可以看作是每条虚链路寻找物理路由的问题。目前，针对多跳网络路由问题研究相对广泛，常用的路由算法包括主动式路由、反应式路由[17]以及基于强化学习的智能路由算法[18-19]等。该问题不是研究的重点，因此所提虚拟网络构建方法采用基于迪杰斯特拉的最小跳算法求解虚实映射问题。

3 建模与仿真分析

为了验证所提虚拟网络拓扑控制方法的可行性，搭建了100个骨干网节点的多跳网络通信系统，采用数值模拟的方式模拟真实的节点和物理环境。下面介绍仿真环境的相关配置，并对仿真结果进行分析。

3.1 仿真环境

选取节点规模为100个的骨干侧多跳网络通信系统作为仿真对象，将100个骨干网节点划分为4个域，每个域包含一个簇首节点。将簇首节点作为每个域的控制节点，根据域内用户的请求进行集中的调度与管理。在网络仿真软件中选取一个域中的5个或10个节点模拟建立虚拟网络，具体的多跳通信网络的单域节点仿真网络拓扑示意图如图4所示。 其中，node_0,node_1,…,node_20表示网络节点。

图4 仿真网络拓扑示意图

由图4可以看出，其中的仿真域包含21个节点，各节点之间通过无线链路或有线链路通信。为符合实际应用场景，仿真设置两种具有不同覆盖范围和通信能力的节点类型。其中，20号节点能够覆盖当前所在域，与其他节点之间均通过无线链路连接，且链路带宽较窄。其余节点均具备无线和有线通信能力，无线链路的带宽为2.4 kB、9.6 kB、8 MB以及2 MB，有线链路带宽则固定为20 MB。所仿真的多跳网络的业务，主要包括报文、环境信息、文件传输以及话音等业务。需要说明的是，包含100个骨干网节点的通信系统，每个域的拓扑结构是类似的。不失一般性，虚拟网络化之后的性能测试在包含100个骨干节点的多域多跳通信系统场景下进行仿真。具体的多跳网络通信系统参数如表1所示。

表1 多跳网络通信系统参数

通信效率下降门限指的是在删除虚拟网络链路之后，网络效率需要始终高于通信效率下降门限。不可用链路带宽指的是该条链路对应的两个节点之间无直连链路。路由有效时间指的是实体网络中每条路由的有效时间。

3.2 仿真结果分析

单域内5个虚拟网络节点通信效率随删边个数变化情况如图5所示。5个虚拟网络节点分别为node_3、node_0、node_8、node_11和node_16。

图5 5个节点通信效率随删边数目变化情况

由图5可以看出，边介数逆序删边算法的通信效率下降曲线存在两个拐点，并且与随机删边通信效率下降曲线相比，通信效率下降更慢。边介数逆序删边算法在每次删边时选择边介数最小的边，对网络的整体通信效率影响较小。为保证每次删边后的通信效率不低于初始效率的80%，在删除5条边后终止。而随机删边通信效率下降趋势不固定，为保证每次删边后的通信效率不低于初始效率的80%，在删除4条边后终止。

图6为单域内10个虚拟网络节点通信效率随删边个数变化的情况。10个虚拟网络节点分别为node_1、node_6、node_18、node_3、node_0、node_8、node_11、node_12、node_16和node_19。

图6 10个节点通信效率随删边数目变化情况

由图6可以看出，边介数逆序删边算法的通信效率下降曲线存在两个拐点，并且与随机删边通信效率下降曲线相比，通信效率下降更慢。为保证每次删边后的通信效率不低于初始效率的80%，在删除26条边后终止。而随机删边通信效率下降趋势不固定，为保证每次删边后的通信效率不低于初始效率的80%，在删除16条边后终止。

为了验证虚拟网络的有效性，进一步对构建的虚拟网络进行多业务性能测试。设置仿真时间为1 700 s，在仿真过程中，虚拟网络节点随机发起调度请求，并接收其他虚拟网络节点传输的业务。以最小生成树、全连接拓扑作为对比方案，假设仿真过程中使用不同方法生成的业务数量相等，则不同虚拟网络拓扑下5个虚拟网络用户的业务的拒绝数和不同拓扑下5个虚拟网络用户的业务时延分别如图7和图8所示。

图7 不同拓扑5个虚拟网络用户的业务拒绝数

由图7可以看出，最小生成树虚拟网络拓扑下，业务的拒绝率为31.42%；基于边介数逆序删边算法的虚拟网络拓扑中，业务的拒绝率为23.74%；全连接的虚拟网络拓扑中，业务的拒绝率为15.08%。基于边介数逆序删边算法的虚拟网络拓扑和最小生成树虚拟网络拓扑的链路数目基本相同，而前者的业务拒绝率比后者低了7.68%。这说明基于边介数进行删边可以在尽可能不影响网络效率的前提下删除冗余的链路。同时，全连接虚拟网络拓扑的链路数目是基于边介数逆序删边算法的虚拟网络拓扑的链路数目的二倍，而前者的业务拒绝率只比后者低了8.66%。这进一步说明了基于边介数进行删边时删去的边对网络效率影响较小。综合考虑业务拒绝率和链路数目，基于边介数逆序删边后动态分配带宽的虚拟网络拓扑性能更优。

图8 不同拓扑下5个虚拟网络用户的业务时延

由图8可以看出，3种拓扑的平均时延相差不大，最小生成树虚拟网络拓扑、基于边介数逆序删边算法的虚拟网络拓扑和全连接的虚拟网络拓扑的业务平均时延分别为0.543 9 s、0.60 s和0.50 s。这说明了在为不同虚拟网络拓扑中的业务提供服务时，所提方法是很稳定的。

在搭建的具有100个骨干网节点的多跳网络通信系统中进行虚拟网络拓扑构建、优化以及资源自适应分配，通过网络初始化时对虚拟网络进行删边和网络运行时的多业务仿真，验证了虚拟网络构建方法的有效性。图5和图6中的仿真结果表明，基于边介数逆序进行删边时，通信效率下降速度逐渐增快，并且具有拐点。边介数逆序删边算法与随机删边算法相比，可删除更多冗余链路，提升带宽资源的利用率。图7和图8是虚拟网络的多业务测试，虚拟网络构建方法可在尽可能提高带宽利用率的前提下有效降低虚拟网络用户业务的拒绝率。

4 结语

针对无线资源受限的多跳网络环境下，网络资源与业务需求难匹配的问题，提出了虚拟网络构建及拓扑控制方法。将实体网络中的繁杂信息抽象为虚拟网络拓扑，并根据业务分布和组网需求优化拓扑结构使其具备小世界网络特性。进行端到端的虚拟链路资源预留，实现虚拟网到物理资源的映射，完成多跳网络中海量物理资源的高效管控。最后，选择节点规模为100的多跳网络通信系统作为仿真对象，选取其中的5个和10个节点作为虚拟网络节点。结合实际参数，仿真分析了所提虚拟网络拓扑控制方法在业务拒绝率方面的有效性。仿真结果表明，边介数逆序删边算法与随机删边算法相比，可删除更多冗余链路，提升带宽资源的利用率。面向大规模多跳网络的虚拟网络拓扑结构控制方法能够为用户合理预留带宽，在提高带宽利用率的同时尽可能地降低用户业务的拒绝率。