面向物联网的能耗感知虚拟网络映射算法

赵季红,吴豆豆,曲 桦,季文君

(1.西安邮电大学 通信与信息工程学院,西安 710121; 2.西安交通大学 电子与信息工程学院,西安 710049)

0 概述

物联网(Internet of Things,IoT)[1]是物物相连的互联网,为满足万物互联的需求,基础设施提供商(Infrastructure Provider,InP)依据网络虚拟化技术[2-3],在多样化现有网络的同时共享基板上的异构网络架构,为多个服务提供商(Service Provider,SP)提供资源。随着业务的增加,节点间规模庞大的数据交换愈加频繁,因此,在虚拟网络映射[4-5]时,合理高效地完成底层物理网络资源分配、减少网络能源消耗、降低网络运维成本并构建绿色节能的网络,成为相关学者关注的热点问题之一。

目前,关于节能的虚拟网络映射算法[6-8]研究较多。其中,文献[9-10]以最小化底层工作节点的链路为目标,采用虚拟网络映射算法(EA-VNE)降低能源消耗。但大量虚拟请求的到来会增加映射排斥率,减少收益。文献[11]以最小化节点与链路能耗为目标,建立能耗模型,并通过能耗感知虚拟网络映射启发式算法(EA-VNEH)求解模型。该算法适应于节点异构网络,但其将所有网络资源的能耗视为相等,在实际应用中不可行。文献[12]提出一种基于流量拟合模型的自适应能量感知VNE方法,通过有选择地整合底层网络资源并关闭链路,从而保证QoS约束并实现节能。但是该算法采用整数线性规划求解问题,映射时间较长。文献[13]出于生态考虑,提出一种绿色能量感知混合虚拟网络映射算法,其将VN部署到与最小排放因子相关联的扇区资源上,该方法旨在解决能源效率和资源整合问题,但对各地区能源类型进行调查会相对困难。以上虚拟网络节能映射算法在互联网场景下达到了较好的节能效果,但无法适用于物联网中节点异构性更突出,初始状态、能量消耗速率不同等能耗特性。

本文针对物联网环境下节点异构性与链路时效性特点,提出一种改进的能耗感知虚拟网络映射算法(Modified-EA-VNE)。在虚拟网络映射之前根据不同业务的服务类型对虚拟请求做拆分处理,依据能耗模型,采用混合整数线性规划方法将虚拟节点映射至同类型且能耗最小的物理节点上,并通过改进的K最短路径算法为不同时延下的链路分配合适的资源。

1 问题描述与能耗模型

1.1 问题描述

为解决物联网环境下的能耗问题,本文提出一种改进的能耗感知虚拟网络映射算法,该算法根据业务的服务类型将每个到来的虚拟请求拆分为若干个小拓扑,并将拆分后的虚拟请求映射至满足其要求的能耗最小的物理节点上。其中,每个虚拟节点与CPU容量约束相关联,每条虚拟链路与带宽容量和所需延迟相关联,每个物理节点与CPU剩余值和识别节点能源类型的地理位置相关联,每条物理路径(连接2个物理节点)与剩余带宽容量和延迟相关联。

1.2 网络拓扑

1.3 能耗模型

虚拟网络请求映射至物理网络的节点时,总能耗PN定义为[14]:

(1)

其中,Nw表示需要从未激活状态变为激活状态的宿主节点数量,Pb表示节点的基础功耗,Pl表示转发节点的能耗,Uutil(nj)表示节点映射所需的CPU利用率。

虚拟网络请求映射至物理网络的链路时,总能耗PL定义为[14]:

PL=NwPn+Nn(Pb+Pn)+d(u,i)α

(2)

其中,Pn是一个值为恒定常量的链路功耗[15],Nn表示需要从未激活状态变为激活状态的转发节点数量,d(u,i)表示节点u到节点i的路径距离,α表示距离因子。

1.4 虚拟网络映射数学模型

在建立虚拟网络映射能耗模型时,以最小化总能耗为目标函数,并满足虚拟网络资源的每个约束,根据混合整数线性规划方法对虚拟网络映射问题进行建模。目标函数为:

min (PN+PL)

(3)

约束条件为:

(4)

∀j∈Nv,Ddis(Lloc(j),Lloc(Mn(j)))≤D(j)

(5)

∀i∈Ns,∀j∈Nv,Ggenre(j)=Ggenre(i)

(6)

(7)

(8)

(9)

(10)

(11)

2 算法设计

本文虚拟网络映射算法包括虚拟请求拆分、节点映射以及链路映射[16]3个部分。

2.1 虚拟网络请求拆分

由于物联网对实时性具有较高的要求,因此在虚拟网络映射中需要考虑链路的时延问题。为了降低映射过程的复杂性并考虑链路的延迟特性,本文根据时延约束,对到来的虚拟网络请求做拆分处理,将每个虚拟请求大拓扑拆分为一组虚拟请求小集群,在后续的节点与链路映射中,并行处理分割后的虚拟请求,缩短映射运行的时间。上述拆分基于虚拟链路Flagf(lv)的服务类型,每条链路用f(lv)做标记以区分该链路对时延的要求。在链路映射中,基于该拆分结果为每条虚拟链路分配满足其服务类型的物理链路。如图1所示,根据业务的需求将虚拟网络拓扑图拆分成S-V1和S-V2 2个小拓扑图。

图1 虚拟请求拆分示意图

在图1中,S-V1的f(lv)=1表示该拓扑图具有延迟属性,S-V2的f(lv)=0表示该拓扑图具有带宽属性,其中,有灰色标记的2个节点为之前S-V1所映射过的节点,不再考虑其节点映射问题。虚拟请求拆分过程伪代码如算法1所示。

算法1虚拟请求拆分算法

1.令Gr=Gv,i=1,Gv(i)=0

2.while 任意一条链路Lr≠φ do

3.lv(u,v)∈Lr,u∈Nr,v∈Nr

4.将Gr分配给Gv(S-V(i)),并标记分配节点Flag{u,v}

5.for与Gr相连接的其他链路lv(u′,v′)∈Lr

6.if (f(u′,v′)=f(u,v)|u′∈Nv(i) & v′∈Nv(i))

7.将新链路分配给Gv(S-V(i)),并标记Flag{u′,v′}

8.end if

9.end for

10.Lr=Lr-Lv(i)

11.i=i+1

12.end while

2.2 节点映射

由于物联网底层是一个自组织网络,因此针对节点异构性问题,本文依据节点的类型对底层资源进行分类。虚拟节点只能映射至同类型的物理节点上,从而避免开启无关类型的节点。这种资源整合的方式可以减少底层资源的浪费,进而达到节能的目的。在节点映射阶段,基于最小能耗和最接近剩余容量原则,将虚拟节点映射至同类型且能耗最小的物理节点上,本文将节点的资源能力[17]定义为:

(12)

Ω(nv)={ns|Ccpu(nv)≤Ccpu(ns)&

Ddis(Lloc(nv),Lloc(ns))≤D(ns),

ns∈Ns}

(13)

映射节点的综合资源能力为:

CCR(ns)=lg (NNR(ns)·PN(ns)+γ)

(14)

其中,γ→0,避免式(14)中对数函数内部出现0的情况。

节点映射算法通过将每个虚拟节点映射到能耗最小且满足CPU需求的最少资源量的物理节点上,以降低网络映射的能耗,提高物理资源的利用率。如图2所示,将虚拟请求S-V2映射至底层网络,首先考虑CPU为10的节点D2,然后选择具有最少但足够的CPU资源的物理节点作为候选节点,最后比较节点类型,将虚拟请求D2映射至物理节点D1上,并计算物理节点D1的剩余资源量。算法伪代码如算法2所示,与以往的能耗感知映射算法相比,该算法通过将虚拟请求映射至CCR最小但满足CPU要求的物理节点上,可有效节省能耗,提高物理资源的利用率。

图2 虚拟节点映射示意图

算法2节点映射算法

输出NodeMappingList,并作为链路映射的输入参数

1.for 每一个虚拟节点nv∈Nvdo

2.计算虚拟节点nv的资源能力NNR(nv)

3.end for

4.将虚拟节点nv按资源能力NNR(nv)降序排列,并将结果存入 VNL中

5.for VNL中的每一个虚拟节点nvdo

6.构建候选节点集合且每个ns满足虚拟节点的CPU资源和位置约束

7.if Ω(ns)≠φ then

8.for Ω(ns)中的每一个候选节点nsdo

9.计算CCR(ns)的值

10.end for

11.将ns按照CCR(ns)的值降序存入NodeList中

12.if Ggenre(nv(i))=Ggenre(ns(j)) then

13.将虚拟节点nv映射至CCR最小且满足约束的物理节点ns上,并将结果集存入NodeMappingList中

14.end if

15.计算CPU剩余资源Ccpu(ns)=Ccpu(ns)-Ccpu(nv)

16.end if

17.end for

18.节点映射结束

2.3 链路映射

针对虚拟链路映射,通常采用K最短路径算法[18-19],但在物联网环境下,需通过传感器实时、准确地传递物体的信息,对网络资源的能耗以及链路的实时性要求较高。因此,在链路映射阶段,本文通过整合链路映射过程中的能源消耗和链路延迟等因素,设计一种能耗优先且满足链路延迟的K最短路径算法。

如图3所示,虚线箭头表示2个节点之间的路径,虚拟网络中的x/y/z分别表示带宽/时延阈值/是否对时延敏感。将虚拟请求S-V1映射至底层物理链路,首先根据节点映射算法确定映射成功的物理节点,然后依据带宽需求优先选取资源需求量较高的虚拟链路进行映射。对于虚拟链路luv∈Lv,采用K最短路径算法计算最短路径集合φ(luv),且对于任意路径Ppath∈φ(luv),需满足虚拟链路luv的带宽需求以及延迟容量,最后通过计算链路能耗PL,将虚拟链路luv映射至能耗最小的路径上。

图3 虚拟链路映射示意图

链路映射算法伪代码如算法3所示,与传统算法相比,该算法考虑链路的时延问题,提高了算法的延展性,能够更广泛地适用于物联网场景。在链路映射过程中,针对不同延迟需求的链路进行分开处理,可缩短链路映射的运行时间,降低网络映射与链路映射的成本,从而增加映射收益。

算法3链路映射算法

输出LinkMappingList,并计算评价指标

NodeMappingList

1.将虚拟链路按带宽需求降序排序,并将结果存入链表VLL中

2.for VLL中的每条虚拟链路luvdo

3.采用K最短路径算法计算底层节点的最短路径集合φ(lij),且对于任意路径Ppath∈φ(lij)

4.if φ(lij)=φ then

5.Return 映射失败

6.else

7.for φ(lij)中的每一条最短路径Ppathdo

9.end for

10.switch (待映射链路lr(flag)) do

11.case 0

12.if b(luv)≤b(lij) then

13.将虚拟链路luv映射至物理链路lij上,并将结果存入LinkMappingList中

14.case 1

15.if b(luv)≤b(lij) & d(luv)≥d(lij) then

16.将虚拟链路luv映射至物理链路lij上,并将结果存入LinkMappingList中

17.end switch

18.计算带宽剩余资源b(ls)=b(ls)-b(lv)

19.end if

20.end for

21.链路映射结束

3 仿真结果与性能分析

在本文仿真中,由GT-ITM[20]生成设定的网络拓扑,通过NS2[21]中的Tk工具生成可视化的网络拓扑,对本文算法以及2种基于能耗感知的虚拟网络映射算法进行对比,在底层物理资源使用数量、虚拟网络请求能耗、映射时间以及底层网络收益开销比等方面验证算法的性能。

3.1 仿真环境设置

本文通过GT-ITM生成网络拓扑,具体实验参数如表1所示,其中,虚拟节点与物理节点间的连通率均为50%,式(3)中的距离因子设置为0.5,K最短路径算法中K的取值为5。针对节点的异构性特点,令Pb=150 W,Pm=300 W,Pn=15 W。每次实验运行时间为30 000个时间单位,约有1 200个虚拟网络请求到达,并运行10次实验,取平均值作为最终结果。

表1 实验参数设置

3.2 性能分析

3.2.1 评价指标

本文实验评价指标具体如下:

1)虚拟网络请求平均能耗:

(15)

其中,E(i)为第i个虚拟请求消耗的能量,N为虚拟请求的个数。

2)收益开销比:

(16)

其中,AT为时间T内接收的虚拟请求数量,R(i)和CCost(i)分别表示虚拟请求i的收益和成本,两者具体定义如下:

(17)

(18)

3.2.2 结果分析

为了评估本文Modified-EA-VNE映射算法的性能,本节将其与EA-VNE、EA-VNEH两种算法进行比较。EA-VNE算法以最小化底层网络工作节点与链路数量为目标,在节点映射阶段采用贪婪算法,链路映射阶段采用最短路径算法。EA-VNEH主要考虑节点能耗的异构特性,通过建立能耗模型使节点和链路均映射至新增能耗最小的底层网络中。本节从工作节点和链路数量、虚拟网络请求映射时间、映射所花费的能耗以及物理网络收益开销比等方面对算法进行比较。

1)工作节点与链路数量

图4、图5分别表示不同算法中虚拟网络映射工作节点和链路的数量。从中可以得出,EA-VNEH算法所需的底层节点数量最多,Modified-EA-VNE算法最少,主要因为EA-VNEH算法着重考虑物理网络节点的异构性,将虚拟请求映射至能耗最小的节点上,而Modified-EA-VNE算法在节点映射时采用资源整合的方式且基于最接近剩余容量原则,故所需的节点数最少。但在链路映射过程中,由于Modified-EA-VNE算法需考虑链路的延迟特性,故工作的链路略高于EA-VNE。Modified-EA-VNE算法考虑节点的异构性,将节点分配给同类型的节点,增加了使用同一物理节点作为映射节点的概率,从而导致了资源整合。

图4 3种算法平均工作节点数量对比

Fig.4 Comparison of average number of working nodes of three algorithms

图5 3种算法平均工作链路数量对比

Fig.5 Comparison of average number of working links of three algorithms

2)虚拟网络请求能耗和映射时间

在物联网环境下,3种算法所消耗的能耗如图6所示。从图6可以看出,Modified-EA-VNE算法的平均能耗约为20.5 kW,较EA-VNE、EA-VNEH分别降低36.90%和18.65%,其原因在于,EA-VNE仅通过最小化工作节点和链路实现节能,但是在节点异构的环境中,该方法并不能实现能耗最优化,而另外2种算法均适用于节点异构环境,但由于Modified-EA-VNE算法不仅采用能耗模型,将节点和链路映射至能耗最小的底层网络中,又基于最接近剩余容量原则,使得底层网络中工作的节点和链路数量尽可能少,从而使得能耗最小。3种算法虚拟网络的映射时间如图7所示,从图7可以看出,EA-VNE算法的映射时间最短,约为50 ms,而Modified-EA-VNE所需的时间较长,约为78 ms,其原因在于,EA-VNE和EA-VNEH采用启发式算法,该算法有效降低了映射所需的时间,而Modified-EA-VNE需考虑节点的异构性以及链路的时延特性,映射节点分布较不均匀,且映射节点之间的路径相对复杂,此外,将VNR拆分为2种类型的子VNR,仿真中只开启了2个线程,并行处理VNR所减少的映射时间远小于在选取节点与路径时所花费的时间。

图6 3种算法虚拟网络请求平均能耗对比

Fig.6 Comparison of average energy consumption of virtual network request of three algorithms

图7 3种算法虚拟网络映射时间对比

Fig.7 Comparison of virtual network mapping time of three algorithms

3)收益开销比

3种算法的物理网络收益开销比对比情况如图8所示。从图8可以看出,当虚拟请求较少时,由于底层资源比较充足,收益开销比较高,但随着资源的逐渐消耗,收益开销比也随之下降,最终达到一个稳定的状态。Modified-EA-VNE算法收益开销比相对较高的原因在于,该算法在虚拟网络映射之前根据不同服务类型将虚拟请求做拆分处理,分别对不同的虚拟请求分配资源,提高了虚拟网络请求的接受率,但由于需将节点分配给同类型的节点,容易产生瓶颈效应,导致其收益开销比趋于EA-VNEH算法,而EA-VNE算法仅考虑工作节点和链路,使得后续节点和链路过于拥塞,降低了虚拟网络映射的成功率。

图8 3种算法物理网络收益开销比对比

Fig.8 Comparison of benefit-expense ratio of physical network of three algorithms

4 结束语

为了解决物联网环境下的能耗优化问题,同时满足节点异构性与链路时效性的要求,本文设计一种能耗感知虚拟网络映射算法Modified-EA-VNE。仿真结果表明,与EA-VNE和EA-VNEH算法相比,Modified-EA-VNE算法能够有效减少虚拟网络映射的能耗,增加底层网络资源利用率,提高物理网络收益,并更细粒度地完成虚拟请求映射。由于实际物联网的网络拓扑为动态拓扑,虚拟请求的到达和离开是动态且顺序不可预测的,因此下一步将结合节点重映射与路径分割技术来设计一种合理的调度算法。