基于云计算的智慧校园虚拟网络节点定位研究*

李海舟

（陕西省行政学院 西安 710068）

1 引言

智慧校园是近年新兴的一种基于可编程网络的新型网络体系架构，具有“控制与转发分离”、“设备资源虚拟化”和“通用硬件及软件可编程”这三大特性［1］，能够灵活满足不同用户的应用需求，为核心网络及应用的创新提供了良好的平台。

智慧校园架构分为应用层、控制层和转发层。其中控制层负责处理数据平面资源的编排、维护网络拓扑状态信息等，转发层负责基于流表的数据处理转发和状态收集［2］。目前智慧校园转发层网络大多通过Mininet仿真平台虚拟实现，或者通过多台Openvswitch交换机搭建实现［3］。Mininet能够快速创建一个大规模网络，但是不能完全反映真实网络的特点［4］；Openvswitch交换机能够创建真实网络，但是构建更新大规模网络时，资源消耗过大［5］。结合上述两种技术的优点和缺陷，本研究将Mininet虚拟网络与Openvswitch真实交换机融合，搭建一个虚实结合的智慧校园网络环境，以同时满足网络大规模和真实性的需求。在搭建智慧校园虚实网络过程中，Openvswitch交换机连接多个Mininet虚拟网络且Openvswitch通常个数有限，因此关键问题是如何选择Openvswitch交换机，即真实节点的位置。

本文首先基于图论和社交网络等领域的定义，研究真实节点的特点，设计了智慧校园虚实网络拓扑中真实节点的定义。在网络建模中，进一步解释了真实节点的特点。然后通过研究节点介数、重叠社区发现等算法，提出适用于智慧校园虚实网络拓扑的真实节点定位算法。最后实验验证，通过两种适用于智慧校园虚实网络拓扑的真实节点定位算法，有效发现了拓扑中真实节点的位置。

2 准备工作

在智慧校园虚实网络拓扑中，节点分为虚拟节点和真实节点。其中，虚拟节点代表Mininet仿真的虚拟交换机，主要展示网络的规模［6］；真实节点代表Openvswitch真实交换机，主要展示网络的真实性［7］。搭建智慧校园虚实网络时，Mininet可以仿真任意拓扑的大规模网络，但是真实性较低。Openvswitch交换机能够提高网络真实性，但是个数有限［8］。为了通过有限个Openvswitch交换机和Mininet，搭建大规模且真实性高的网络环境，提前确定网络拓扑中真实节点的位置尤为重要。

2.1 算法基础

将智慧校园虚实网络拓扑建模为一个无向连通图 G(V，E)，其中V={v1，v2，…，vn}是图 G 中所有顶点的集合，E={e1，e2，…，em}是所有边的集合。设集合 S={s1，s2，…，sh}是图G中的边缘节点集合，为V的子集。

定义1（节点介数）：网络中所有最短路径中经过该节点的路径数目占最短路径总数的比例［9］，公式如下：

其中，σst表示节点s和t之间所有的最短路径数目，σst(v)表示这些路径中经过节点v的数目。

定义2（节点度）：节点度是指G中与节点v相关联的边数目，即邻居数目。

定义3（社区重叠度）：设 A、B为两个社区，则这两个社区的重叠度over(A，B)为［10］

其中， ||A和 ||B分别代表A和B社区中的节点个数。

定义4（节点连接度）：设有节点u和社区c，节点u与社区c之间的连接度connect(u，c)为

其中，ku为节点u的度，如果u与c中的任一节点v相邻接，则wuv=1，否则wuv=0。

定义5（真实节点）：设真实节点个数为r个。图G中的节点v如果满足以下两个条件之一，则称节点v为G的一个真实节点。

条件一：v处于G中边缘节点对(si，sj)之间的最短路径上，且所有节点按介数递减排序后，v位于前r个。

条件二：v为社区重叠节点，且节点按照重叠次数（至少为2）从大到小排序后，v位于前r个。

如果v仅满足上述两个条件之一，则v为普通真实节点；如果v同时满足上述两个条件，则v为高级真实节点。

2.2 网络建模

假设智慧校园虚实网络拓扑如图1所示。圆代表交换机，包括真实节点和虚拟节点。方块代表主机，与主机相连的交换机为边缘节点。按照真实节点定义，查找真实节点的结果如图2所示。根据条件一，真实节点位于边缘节点对之间的最短路径上，且所有节点按介数递减排序时，真实节点为前r个。图2中，黑粗边代表边缘节点对之间的最短路径。3个浅色节点和1个深色节点经过的最短路径数最多，满足条件一，因此选为真实节点。根据条件二，真实节点为社区重叠节点，且所有节点按照重叠次数递减排序后，真实节点为前r个。图2中，深色节点是唯一一个社区重叠节点，满足条件二，因此也选为真实节点。另外，由于深色节点同时满足条件一和条件二，所以为高级真实节点，其它3个浅色节点为普通真实节点。搭建智慧校园虚实网络时，应该优先在深色节点位置，配置Openvswitch真实交换机。

图1 智慧校园虚实网络拓扑

图2 真实节点查找结果图

3 关键算法

考虑到真实节点传输的网络流量较大且通常连接多个局部网络，本文设计了两种适用于智慧校园虚实网络拓扑的真实节点定位算法，分别为基于节点介数分析的真实节点查找算法和基于重叠社区发现的真实节点查找算法。

3.1 基于节点介数分析的节点查找算法

算法一为基于节点介数分析的真实节点查找算法。为了提高智慧校园虚实网络拓扑的真实性，需要最大程度增加真实节点上的网络流量。在智慧校园网络中，流量由边缘节点连接的主机产生，所以可以把边缘节点看作流量的起点和终点［11］。网络流量通常经过源节点和目的节点的最短路径进行传输，因此为了承载最多的网络流量，真实节点应该选择边缘节点间最短路径最多交叠的位置，即介数最大的节点［12］。算法一为每个节点增加了前驱节点、最短路径经过次数等属性，有效解决了一个节点可能存在多个前驱节点的问题。每找到一条最短路径，则回溯更新每个节点出现次数，最后通过各节点最短路径经过次数和最短路径总数计算节点介数，返回候选真实节点集合。

算法一：基于节点介数分析的节点查找算法输入：网络G=(V，E)，边缘节点个数h，真实节点个数r

输出：候选真实节点集合R1

方法：

步骤1：计算所有边缘节点间最短路径总数，及所有最短路径上，每个节点的出现次数；

1）Fori=1 to h

2）For所有节点初始化节点属性。（节点状态=white，权重=+∞，前驱节点集合 p）

3）边缘节点i的权重=0，p=null

4）节点i入队列Q

5）WhileQ不为空

6）Q中首元素t出列

7）For与t相邻接的所有节点k

8）If k的状态=white

9）K入队列Q

10）If k的权重＞t的权重+1

11）K的权重=t的权重+1，k的前驱节点集合 p清空，t入集合p

12）Else k的权重=t的权重+1

13）If k的前驱节点集合 p不包含t，t属于集合p

14）End If 15）End For

16）t的状态=black

17）Forj=i+1 to h

18）计算从 j到i的最短路径数，计算路径上每个节点出现次数

19）End For

20）返回所有边缘节点间最短路径总数sum，及所有最短路径上每个节点的出现次数nodeTimes。

步骤2：计算所有节点的介数，按从大到小排序，选择排序靠前的节点放入候选真实节点集合R1。

1）For i=1 to ||V 计算节点介数：

2）根据节点的betweeness从大到小排序；

3）选择Top r个节点作为候选真实节点，放入R1；

4）返回候选真实节点集合R1。

算法一中，步骤1首先根据节点的权重，计算每个节点的前驱节点集合。然后回溯边缘节点间的每条路径，统计边缘节点间最短路径总数以及每个节点在最短路径上的出现次数。步骤2首先计算每个节点的介数，然后通过优先级队列，对所有节点从大到小排序，最后选择top r个节点，存入候选真实节点集合R1。

3.2 基于重叠社区发现的节点查找算法

算法二为基于重叠社区发现的真实节点查找算法。智慧校园虚实网络是为了模拟真实的计算机网络而设计的网络仿真环境，其中，Mininet模拟紧密关联的局部子网，Openvswitch模拟子网之间的连接节点。一个真实节点连接多个子网，也可以看作是多个子网的重叠节点。这里引入社交网络中的社区来代表子网，则真实节点为重叠社区之间的重叠节点。算法二引入重叠度阈值和连接度阈值，其中，重叠度阈值［13］控制邻近社区的融合，保证一个子网由一个社区表示。得到初始社区集合后，连接度阈值［14］则有效解决了剩余节点的社区归属问题。

算法二：基于重叠社区发现的节点查找算法

输入：网络G=(V，E)，边缘节点个数h，真实节点个数r，重叠度阈值overlayT，连接度阈值connectT

输出：候选真实节点集合R2

方法：

步骤1：计算以边缘节点为核心的社区，根据重叠度阈值，融合邻接的社区。根据连接度阈值，划分节点到相应社区，返回所有社区的集合；

1）For i=1 to h计算边缘节点的度degree

2）边缘节点根据degree，从大到小排序，放入数组top

3）候选社区C0={top[0]}

4）For i=1 to ||V If（top［0］，Vi）∈ E

C0=C0∪{Vi}

5）C0入社区集合AllC

6）For i=2 to top.length

7）临时社区C={top[i]}

8）For j=1 to ||V If（top[i]，Vj）∈ E

C=C∪{Vj}

9）For集合AllC中的每个社区k

10）计算 over(c，k)

11）If over(c，k)＞overlayT

12）社区c与k合二为一，去掉重复节点，break

13）End For

14）If AllC中没有社区与C融合C入社区集合AllC

15）End For

16）If存在节点没有分到AllC任一社区节点放入restNode数组

17）For数组restNode的每个节点n

18）For集合AllC中的每个社区k

19）计算connect(n，k)

20）If connect(n，k)＞connect节点 n放入社区k

21）End For

22）End For

23）循环17）～22），直到AllC中所有社区的节点不再变化

24）返回社区集合AllC

步骤2：计算所有节点隶属社区的个数，按从大到小排序，选择排序靠前的节点放入候选真实节点集合R1。

1）For集合AllC中的每个社区k

2）For社区k中的每个节点n，计算n隶属社区的个数communityNum

3）根据节点的communityNum从大到小排序4）选择Top r个节点作为候选真实节点，放入R2

5）返回候选真实节点集合R2

算法二中，步骤1首先计算所有边缘节点的度，并使用优先级队列对边缘节点从大到小排序。然后选择度最大的边缘节点及其邻接节点构成初始社区C0，将C0放入社区集合AllC中。之后依次选择剩余的度最大的边缘节点及其邻接节点，构成临时社区C。计算C与AllC中每个社区的重叠度over，如果over超过重叠度阈值，则两个社区合二为一，去掉相同节点；如果over未超过重叠度阈值，则AllC增加一个社区C。所有的边缘节点都计算完成后，如果还存在不属于任一社区的节点，则计算节点与AllC中每个社区的连接度connect，如果connect超过连接度阈值，则将节点加入该社区［15］。循环这个过程，知道AllC中所有社区的节点不再变化。步骤2首先计算所有节点隶属社区的个数，然后使用优先级队列，对所有节点从大到小排序，最后选择top r个节点，存入候选真实节点集合R2。

3.3 算法对比

由于智慧校园虚实网络拓扑中，流量主要由边缘节点，即连接主机的交换机节点产生，因此相对于传统计算介数的算法，算法一只计算边缘节点对之间的最短路径，而不是所有节点间最短路径。另外，与Dijkstra算法［16］不同，本文网络拓扑中，边的权值统一为1，所以部分节点的前驱节点不止一个，算法一为每个节点配置前驱结点集合属性，解决了部分节点存在多个前驱结点的问题。

网络拓扑中，任一子网一定包含多个主机，等价于包含多个边缘节点，因此相较于其它基于局部拓展的重叠社区发现算法，算法二没有选择所有节点中度最大的节点为种子节点，而只对边缘节点按度排序，选择度最大的边缘节点作为种子节点。这样不仅降低了节点排序的复杂度，而且以边缘节点为社区中心能够更准确地模拟包含多个子网的大规模网络。

算法一和算法二分别基于真实节点定义的两个条件设计。其中，算法一针对真实节点承载大网络流量的特点，算法二针对真实节点连接多个子网的特点。两者相比，算法一和算法二分别关注网络拓扑的局部特性和全局特性。算法一适用于网络流量大的小规模网络，算法二适用于包含多个子网的大规模网络，对于不同的网络拓扑结构，应该选择两者中更适合的算法。

4 实验与分析

为了验证算法的可行性和有效性，本文选取3个不同的网络拓扑，对基于节点介数分析的真实节点查找算法和基于重叠社区发现的真实节点查找算法进行验证。

4.1 网络拓扑一

如图3，网络拓扑一中共7个节点，7条边。其中，节点1、2、3和4为边缘节点。设真实节点个数为2，算法一和算法二的实验结果如表1所示，算法一的候选真实节点集合为｛5，6｝，算法二的候选真实节点集合为空，因此对于网络拓扑一，节点5和6为真实节点。

图3 网络拓扑一

表1 网络拓扑一实验结果表

1）算法一流程分析（设真实节点个数为2）

首先计算边缘节点之间的最短路径。节点1为起点时，到其他边缘节点的最短路径有3条，分别为1-5-2、1-5-6-3和1-5-6-4。回溯这三条路径，更新每个节点经过最短路径的次数。其他所有边缘节点也循环这个过程，可得最短路径总数为6，各节点经过最短路径的次数依次为3、3、3、3、5、5、0。然后计算每个节点的介数，并按照递减排序。由于真实节点个数是2，所以最后选择介数最大的两个节点，即节点5和节点6作为候选真实节点。

2）算法二流程分析（设真实节点个数为2、重叠度阈值为0.45，连接度阈值为0.5）

首先计算所有节点的度，并将边缘节点按照度递减进行排序。节点1、2、3、4的度相等，可以从任一边缘节点开始形成初始社区，这里选择节点1及其邻接点构成初始社区C0=｛1，5｝，并放入社区集合AllC中。然后其他边缘节点及其邻接点依次构成临时社区C，与AllC中的社区计算重叠度。节点2形成的社区C=｛2，5｝，与C0的重叠度为0.5，超过重叠度阈值，因此C与C0融合为一个社区，C0=｛1，2，5｝。节点3形成的社区C=｛3，6｝，与C0的重叠度为0，小于重叠度阈值，因此形成新的社区C1=｛3，6｝，同理节点 4形成的社区与 C1融合，C1=｛3，4，6｝。剩余节点7，计算与社区C0和C1的连接度都为0.5，未超过连接度阈值，因此节点7不属于任何社区。由于社区C0和C1间不存在重叠节点，因此最后返回的候选真实节点集合为空。

4.2 网络拓扑二

如图4，网络拓扑二中共7个节点，8条边。其中，节点1、2、3和4为边缘节点。设真实节点个数为2，算法一和算法二的计算结果如表2所示。算法一的候选真实节点集合为｛2，5｝，算法二的候选真实节点集合为｛5｝，因此对于网络拓扑二，节点5为高级真实节点，节点2为普通真实节点。

图4 网络拓扑二

表2 网络拓扑二实验结果表

1）算法一流程分析（设真实节点个数为2）

首先计算边缘节点之间的最短路径。节点1为起点时，到其他边缘节点的最短路径有3条，分别为1-2、1-2-5-3和1-2-5-7-4。回溯这三条路径，更新每个节点经过最短路径的次数。其它所有边缘节点也循环这个过程，可得最短路径总数为6，各节点经过最短路径的次数依次为3、5、3、3、4、0、3。然后计算每个节点的介数，并按照递减排序。由于真实节点个数是2，所以最后选择介数最大的两个节点，即节点2和节点5作为候选真实节点。

2）算法二流程分析（设真实节点个数为2，重叠度阈值为0.45，连接度阈值为0.5）

首先计算所有节点的度，并将边缘节点按照度递减进行排序，依次为节点2、3、4、1，这里选择节点2及其邻接点构成初始社区C0=｛1，2，5，6｝，并放入社区集合AllC中。然后其他边缘节点及其邻接点依次构成临时社区C，与AllC中的社区计算重叠度。节点3形成的社区C=｛3，5，7｝，与C0的重叠度为0.33，小于重叠度阈值，因此形成新的社区C1=｛3，5，7｝，节点4形成的社区C=｛4，7｝，与C1的重叠度为0.5，超过重叠度阈值，因此与C1融合，C1=｛3，4，5，7｝。C0和C1包含所有节点，没有剩余节点。由于社区C0和C1间存在重叠节点5，因此最后返回的候选真实节点集合为｛5｝。

4.3 网络拓扑三

图5 网络拓扑三

如图5，网络拓扑三为大规模网络，共100个节点，130条边。其中，节点1～35为边缘节点。设真实节点个数为10，算法一和算法二的实验结果如表3所示，算法一的候选真实节点集合为｛67，76，17，47，91，18，31，53，25，12｝，算法二的候选真实节点集合为｛41，65，71，74，75，79，89，91，53，55｝，因此对于网络拓扑三，节点53和91为高级真实节点，其它节点为普通真实节点。

表3 网络拓扑三实验结果表

1）算法流程分析

通过算法一，计算网络拓扑三的最短路径总数为1198条，各节点的介数如图6所示。由于真实节点个数为10，所以选择介数最大的10个节点，即图6中空心点，为候选真实节点。

图6 节点介数

通过算法二，计算网络拓扑三中各边缘节点的度，如图7所示。依次选择度最大的边缘节点及其邻接点形成临时社区，与社区集合AllC中的每个社区计算重叠度，来决定融合社区或者形成新的社区。剩余节点计算同每个社区的连接度，来决定节点是否归属某社区，最后得到表3中的17个社区。选择社区之间重叠次数最大的10个节点，为候选真实节点。

图7 边缘节点度

2）实验分析

实验中，如果改变重叠度阈值，算法二得到的社区总数和候选真实节点集合会发生变化。设置重叠度阈值范围为0.01～0.5时，实验结果如表4所示。

表4 重叠度阈值分析实验结果表

由表4可知，重叠度阈值越小，网络拓扑划分的社区总数越少，相应的候选真实节点集合也会发生变化。当重叠度阈值范围为［0.3，0.5）时，社区划分总数和候选真实节点集合最为稳定，因此本文设置重叠度阈值为0.45是合理的。

实验中，算法一和算法二得到的候选真实节点集合R1和R2通常不完全一致。如果R1和R2中存在相同的节点，则为高级真实节点，在搭建智慧校园虚实网络时，应该在节点位置优先部署Openvswitch交换机。R1和R2中剩余节点则为普通真实节点，可以根据用户为R1和R2集合设置的不同权重，来选择其他真实节点。

5 结语

本文基于Openvswitch交换机和Mininet仿真平台，搭建智慧校园虚实网络环境，其中“虚”代表的Mininet保证网络的规模性，“实”代表的Openvswitch保证网络的真实性。为了模拟大规模且真实性高的网络，本文提出了针对智慧校园虚实网络的真实节点定位方法。首先基于图论和社交网络等领域的定义，设计了智慧校园虚实网络拓扑中真实节点的定义。然后通过网络建模，进一步解释了真实节点的特点，并基于其特点，设计了两种适用于智慧校园虚实网络拓扑的真实节点定位算法。最后本文选取3个不同的网络拓扑进行实验分析，实验表明，本文提出的算法能够有效发现拓扑中真实节点的位置，验证了算法的可行性和有效性。目前本文使用拓扑图中，所有节点和边的属性均一致，接下来可以区分不同节点和边的属性，进一步研究。