无线虚拟网络中的邻近节点分组映射算法

李 铮,丁 升,王潇潇,刘期烈

(重庆邮电大学 通信与信息工程学院,重庆 400065)

0 概述

随着智能终端及其相关业务的发展，未来无线网络将呈现密集部署、多样业务、异构网络并存的多元化形态。在不断扩大的网络规模和更为密集的网络部署下，传统的因特网网络架构和协议难以满足网络融合的需求，并且面临网络僵化的问题[1-2]。网络虚拟化技术通过对共用的底层基础设施进行抽象，并提供统一的可编程接口，将多个彼此隔离且具有不同拓扑结构的虚拟网络同时映射到共用的基础设施上，为用户提供差异性服务，实现资源共享，已成为未来网络关键技术之一[3-4]。

网络虚拟化是在物理网络(Substrate Network,SN)上运行多个异构虚拟网络(Virtual Network,VN)的技术,通常在网络虚拟化之后有两个逻辑角色,即基础设施提供商(Infrastructure Provider,InP)和网络服务提供商(Service Provider,SP)[5-6]。InP负责向SP提供无线网络资源;SP根据租用和分配的资源自行创建和部署虚拟资源,以满足端到端的服务要求[7]。

然而,随着无线流量和服务量的巨大增长,无线异构网络的管理愈加繁琐,将虚拟化扩展到无线网络中可以简化异构网络管理中出现的问题。无线网络虚拟化是将无线物理基础设施和无线电资源抽象并隔离成多个虚拟资源池,再将这些虚拟资源提供给不同SP[8]。在有线网络虚拟化中,其带宽资源的抽象和隔离可以在硬件基础上完成(例如端口和链路);但在无线网络虚拟化中,由于无线通信的固有传播性质和随机波动,无线资源的抽象和隔离并不简单[9-10]。文献[11]提出一种无线环境下虚拟网络的嵌入框架,但没有给出解决问题的具体算法。文献[12]引入基于卡诺图的频率和时间块分配算法,将二维资源分配给VN请求。文献[13]提出一种重新配置信道从而在无线网状网络中嵌入虚拟网络的算法。上述方法都促进了无线网络虚拟化的发展。

由于多个VN请求共享底层的物理资源,因此为了提高物理资源的利用率和InP收益,高效地在线嵌入VN请求是至关重要的。文献[14]提出基于约束的虚拟网络设计和映射到基板网络的算法以及本文使用的迭代设计算法。文献[15]提出细分启发式算法和自适应优化策略。文献[16]提出两阶段协调性较好的VN嵌入算法。文献[17]提出一种基于负载平衡感知的虚拟网络嵌入算法。以上4种算法基于启发式算法，在使用贪婪方法预选节点映射之后，大多数算法主要关注链路映射。但是，预先选择节点映射可能导致算法性能不佳。文献[18]提出一种基于虚拟节点和链路的分布式协同映射算法,但是该算法的稳定性和性能不如集中式算法。

为解决无线虚拟网络的映射问题,同时更有效地利用物理资源,本文提出邻近节点分组映射(Packet Mapping of Adjacent Nodes,P-AN)算法。将节点分为中心节点和与其相连的边缘节点,两者共同组成映射子集合。在此基础上,依次进行中心节点和边缘节点的映射,并在所有节点映射完成后进行链路映射,从而提高无线虚拟网络映射接受率、收益开销比和物理资源利用率。

1 无线虚拟网络模型和问题描述

1.1 无线网络模型

1.1.1 无线物理网络模型

1.1.2 无线虚拟网络模型

1.2 问题分析

1.2.1 物理网络可用资源

物理网络可用资源主要包含节点剩余可用资源和链路剩余可用资源。虚拟映射是指虚拟请求到达后根据物理网络可用资源,选取合适的物理节点和链路进行映射。

对于每一个节点nS∈NS,它的可用资源为:

(1)

与节点相同,不同虚拟请求的链路可以映射到同一物理链路上,对于每一条链路lS∈LS,它的可用资源为:

(2)

(3)

1.2.2 链路干扰

在无线环境下,无线链路间存在干扰。本文只考虑相邻链路间的干扰,定义物理网络中每一条链路的干扰为:

(4)

其中,dl表示与链路lS直接相连而产生干扰的物理链路个数,1表示自身的干扰,σ为常数。链路干扰将在最短路径算法中作为链路的一部分权值,用于寻找最优的路径。

1.3 无线虚拟网络映射

当一个VN请求到达时,物理网络必须决定是否接受该虚拟请求。如果接受,那么物理网络在资源池中需要为虚拟请求选择满足要求的物理节点和路径,当虚拟请求完成后,相应物理资源将被释放。

节点映射过程定义为MapN:NV→NS,∀nV∈NV。存在如下约束:

d(l(nV),l(n:nV→nS))≤D

c(nV)≤cN(nS)(∀nV→nS)

(5)

其中,d(l(nV),l(n:nV→nS))表示虚拟节点nV与待映射的物理节点nS间的实际矢量距离,D为虚拟节点的映射范围矢量值。

链路映射过程定义为MapL:LV→LS,∀lV∈LV。存在如下约束:

b(lV)≤BL(lS),∀lV→lS,lS∈PS

(6)

1.4 收益与开销

1.4.1 基础设施商的收益

虚拟请求到达InP时,InP希望通过高效地分配资源来部署更多的虚拟请求从而获得更多的收益。本文假设一组InP服务一个虚拟请求得到的收益为:

(7)

其中,α和β分别表示平衡节点资源和链路带宽的加权系数,由InP确定。

1.4.2 映射开销

VN请求的映射开销定义为请求映射到物理资源池上时消耗的节点资源和链路资源,即映射开销为:

(8)

其中,αb和βb是加权系数,用于平衡节点资源和链路资源的影响,l(lV)表示虚拟链路映射到物理路径的长度。

收入与开销的比值可以用来表示物理资源利用率。用GV(T)表示在时间T内到达的VN的收益开销比集合,可得长期收益开销比为:

(9)

收益开销比数值较大表示VN的映射集中在一片较小的物理区域内,此时网络的负载均衡性能比较差。

2 中心度与拓扑势分析

在映射过程中,现有的映射算法大多是先寻找可用资源多的节点映射,再进行链路映射,这种方式下节点映射和链路映射相互独立,虽然节点能够得到较好利用,但是由于底层资源的动态变化,链路资源可能无法得到合理利用。为避免资源分配不合理,本文首先选择中心节点及其边缘节点组成一个子集。

2.1 节点中心度

中心度是用来衡量人或物在其关系网络中重要程度的一个指标。本文借鉴社会关系网中的节点中心度,来反映节点在网络拓扑中的重要程度。

本文介绍3种相关的中心度的度量方法,即度数、连接强度和接近度。因为所使用的方法和针对的问题不同,所以在相同的环境下节点中心度可能会出现不同的排序[19]。

1)节点的度数

节点的度数DC是指与该节点直接相连的邻近节点的个数,即:

DCni=drg(ni)

(10)

虚拟节点的度数描述了该节点在网络中的局部重要性,较高度数的虚拟节点具有更多的相邻节点和链路,可以接受更多的资源请求。

2)节点的连接强度

在虚拟网络拓扑图GV中,任意节点ni的连接强度Qni定义为与节点ni连接的所有链路的带宽之和,定义式如下:

(11)

节点的连接强度反映了目标节点与其他节点相互关联的可能性。

3)节点的接近度

节点在网络中所处位置的重要性可以用节点与网络中其他节点之间的最短路径来描述。以dij表示节点ni与节点nj之间通信所需的最短路径的矢量值,如果i=j,则dij=0。

2.2 拓扑势的引入

场是英国物理学家法拉第在1837年为解释电磁感应现象而提出的一个概念。受法拉第电磁场思想的启发,可将网络拓扑看作是一个包含节点集合以及节点间链路集合的场,位于场中的任何节点都将受到其他节点的联合作用[20]。

对于网络拓扑G=(N,L),根据场的势函数定义,任意节点ni的拓扑势TP可表示为:

(12)

其中,影响因子σ表示每个节点的作用范围;mj≥0,用来描述每个节点所拥有的属性。

将拓扑势引入虚拟映射网络中,其节点考虑4个属性:节点的剩余计算能力大小,该节点到其他节点的最短路径矢量值,该节点的度数以及该节点的连接强度,表示如下:

(13)

由以上定义可知,节点的拓扑势值越大代表其附近的连接越密集,那么该节点在网络中的位置越重要,越有可能成为中心节点。

3 无线虚拟网络映射算法

3.1 目标节点的选取

在处理虚拟请求的操作中,通过计算拓扑势选出中心节点。在进行中心节点的映射部署时,选出符合约束要求的物理节点集合,并根据物理节点的扩展资源公式,优先选择集合中扩展资源值比较大的承载节点进行中心节点的映射。其中,物理节点的扩展资源定义为:

(14)

在中心节点映射完成后,进行边缘节点的映射部署。边缘节点的映射需求能力用虚拟节点的扩展资源表示,其定义为:

(15)

边缘节点按照扩展资源大小降序排列,等待映射。根据文献[17]提出的链路聚合负载压力来为排在首位的边缘节点选择合理的物理节点。负载应力LP由新SN路径上影响距离加权的总带宽要求来度量,其定义为:

(16)

其中,b(lV)是中心节点与要映射的节点间的虚拟链路带宽值。选择最小的LP值,代表选择被嵌入的物理节点与中心节点的链路带宽较大而干扰较小,P表示节点间的路径。

3.2 算法流程

该算法的映射步骤如下:

步骤1将虚拟网络请求按照收益大小降序排列,选取当前收益最大的虚拟请求进行映射。

步骤2计算当前虚拟网络中虚拟节点的拓扑势并降序排列,选取序列中拓扑势最大的虚拟节点设为中心节点。

步骤3遍历物理网络,根据节点约束条件寻找虚拟中心节点的可映射物理节点集合,并选取集合中物理可扩展资源最大的物理节点作为中心节点的承载节点。

步骤4将与中心节点直接相连的虚拟节点称为关联节点,将中心节点的所有关联节点放在一个集合内,组成虚拟节点映射子集,并按其扩展资源的大小降序排列。

步骤5选取当前序列中排在首位的虚拟节点,寻找该节点的可映射物理节点集合,并计算该集合中的LP值,取最小值作为该虚拟节点的承载节点进行映射,并用最短路径K算法进行中心节点与该边缘节点间的链路映射。

步骤6重复步骤4和步骤5直到子集内节点映射完毕。

步骤7重复步骤2～步骤5直到该虚拟网络请求内的节点映射完毕。

步骤8选出已映射的虚拟节点中度数大于等于2的虚拟节点,分别计算物理网络中每条链路的干扰权值。在满足带宽需求的链路中,用最短路径K算法进行子集间的链路映射。若无法满足映射要求则映射失败,否则更新底层物理网络资源状态信息。

步骤9重复步骤1～步骤9直到所有的虚拟请求映射完毕。

4 仿真与结果分析

本文使用MATLAB对P-AN算法进行仿真。为验证P-AN算法的性能,将其与经典的D-ViNE[15]算法进行对比。

4.1 仿真场景设置

利用MATLAB生成具有100个节点的物理网络拓扑,节点随机分布在4 km×4 km的范围内。任意两个物理节点之间随机连接,连接成功率为0.5。物理拓扑网络的节点与链路的大小是均匀分布在[50,100]之间的实数。

假设VN请求到达是一个λ=5的泊松过程。每个VN请求具有指数分布的生命周期和平均时间单位。在每个VN请求中,虚拟节点的数量在[2,20]之间均匀分布且随机确定,平均VN连接率为固定值0.5。虚拟节点的计算能力要求和虚拟链路的带宽要求都均匀分布在[0,50]之间。虚拟节点位于(25×25)网格上。设定虚拟节点的可映射范围D=800 m。每次仿真运行的时间为10 000个时间单位。对于每组实验,进行100次仿真,取实验结果的平均值。

4.2 仿真结果

本文从虚拟请求接受率、平均收益、平均开销和收益开销比4个方面来对比两种算法的仿真结果,并考虑不同虚拟网络规模对结果的影响。

图1展示了两种算法的虚拟请求接受率,可以看出两种算法的接受率先随时间下降而后趋于平稳。这是由于映射刚开始时物理资源比较充足,但随着资源的消耗,接受率逐渐降低直至达到一个平稳的状态。由图1可知,本文算法P-AN与对比算法D-ViNE相比,具有更高的虚拟请求接受率,这是因为P-AN算法充分考虑了在动态的底层资源中节点与链路映射的协同作用。

图1 两种算法的虚拟请求接受率Fig.1 Virtual request acceptance rate of two algorithms

图2和图3分别对比了两种算法的虚拟网络平均收益和平均开销。图2显示了为VN提供物理资源的基础设施商的收益随时间的变化,图3显示了一段时间内的平均开销,可以看出两种算法的收益和开销均随着时间的推移而增加直至平稳,同时本文算法要明显优于对比算法,因为本文提出的P-AN算法在动态的映射过程中提高了物理资源的利用率,从而提升了收益也节省了开销。

图2 两种算法的平均收益Fig.2 Average revenue of two algorithms

图3 两种算法的平均开销Fig.3 Average cost of two algorithms

图4描述了两种算法的收益开销比,其表示底层物理资源利用率,可以看出,本文算法的收益开销比较对比算法高出约60%。由此得出,在相同的资源环境下,P-AN算法充分考虑了节点与链路的资源特性,使之有较高的物理资源利用效率,提高了映射成功率。

图5描述了两种算法在不同虚拟网络规模的情况下映射接受率的变化趋势,可以看出,当虚拟网络请求中节点个数增加时,虚拟网络请求接受率整体下降。这是由于虚拟网络请求中的节点越多,对物理资源的消耗就越多,底层网络中的可用资源减少,导致后期生成的虚拟网络请求的部署失败率增加,从而使得虚拟网络请求的整体接受率降低。如图5所示,本文算法在虚拟请求接受率上优于对比算法。

图5 VN规模对两种算法虚拟请求接受率的影响Fig.5 Effect of VN size on virtual request acceptance rate of two algorithms

图6描述了两种算法在不同虚拟网络规模的情况下收益开销比的变化趋势。由于当虚拟网络请求中节点个数增加时,虚拟网络请求接受率整体下降,因此收益开销比也随之下降。从图6可以看出,本文算法的收益开销比高于对比算法,原因在于本文采取节点链路的半协同映射,节点映射时利用拓扑势首先映射在虚拟拓扑中对信息交换比较重要的节点,提高了映射接受率和物理资源利用率。

图6 VN规模对两种算法收益开销比的影响Fig.6 Effect of VN size on revenue/cost ratio of two algorithms

5 结束语

网络虚拟化是解决无线网络僵化问题的一种有效而具有前景的技术,虚拟网络的嵌入则是其重要组成部分。本文对已有虚拟网络映射算法进行改进,提出一种新的邻近节点分组映射算法,充分考虑动态底层资源中节点与链路的协同作用,提高了物理资源利用率、虚拟网络的映射成功率以及收益开销比。下一步将设计针对节点和链路出现故障时的应对机制和预测方案,并且实现5G网络中异构无线网络的虚拟化。