基于复杂梯度网络的能效优化路由算法

宋莎莎,周金和

(北京信息科技大学 信息与通信工程学院,北京 100101)

0 概述

近年来互联网的飞速发展,便利人们生活的同时,伴随着巨大的能源消耗。移动互联网的普及和用户对高质量多媒体的需求更是加剧了网络流量的得增长。据统计,从2007年～2012年,网络能耗的年平均复合增长率达到10.4%,超过了PC和数据中心的能耗增长速度。能源技术咨询和投资顾问公司数字能源小组的研究表明,在不包括数据中心网络在内的运营商网络基础设施的能耗保守估计为250 TWh/年—400 TWh/年。据经济合作与发展组织(OECD)统计,全球互联网设备呈指数增长,预计到2020年将达到50亿,到2030年将达到100亿,且在未来的数十年中将增加至500亿。2015年召开的巴黎大会上,习近平重申了中国此前做出的承诺,2030年单位国内生产总值二氧化碳排放比2005年下降60%～65%。节能减排成为各行业的发展主题,随着能耗的持续增长,信息通信技术(Information Communication Technology,ICT)行业造成的碳排放量也在急剧增长,降低互联网的能耗成为学术研究热点。

自1998年Watts和Strogatz在Nature上提出小世界网络模型[1],文献[2]提出了无标度网络模型,复杂网络成为人们研究的热点。复杂网络的研究主要包括:复杂网络的静态特性,复杂网络的演化机制,网络结构和功能的关系。网络结构和功能的关系是复杂网络动力学的研究内容,网络结构能够影响网络的动力学行为,同时也被网络的动力学行为所影响,因此,复杂网络动力学成为研究重点。

文献[3]基于介数的节点加权策略,便是针对网络结构和功能之间的研究,探讨了无标度网络抵制级联失效的鲁棒性。文献[4]通过分析梯度场和局部网络结构的关系,提出了复杂梯度网络的一种传输优化策略,验证了无标度网络结构和梯度驱动传输模式有利于提高网络的传输容量。文献[5]提出复杂网络上的基于局部信息路由的拥塞梯度驱动传输,分析了多种拥塞感知度的下的传输行为。文献[6]研究了度-度关联性在无标度梯度网络动力学过程中对于拥塞的影响。文献[7]研究权重无标度梯度网络的拥塞,通过构建边权函数,证明了存在一个最佳参数使得拥塞最小,这个参数取决于平均连接度。文献[8]提出有效路由(Efficient Routing)改进了最短路径路由,认为多数网络中节点的度和节点的介数正相关,将路径上所有节点的度作为路由代价函数寻找有效路径。该路由策略提高了网络传输容量,在一定程度上降低;网络拥塞。文献[9]研究了复杂网络的结构和功能,包括小世界网络、无标度网络,以及动力学过程,提出了最大度路由策略,通过仿真验证了在无标度网络中具有较高的传输效率。文献[10]研究了信息传输中的梯度机制,节点的容量依据节点大小分配,并且传输时间随着中心节点数量增加而减少,通过仿真验证梯度机制可以优先缓解网络拥塞。文献[11]通过关闭或者断开一些度大节点之间链路的方法提高无标度网络传输容量,对于全局路由策略,能更好的提高网络容量,缓解网络拥塞。文献[12]提出对易拥塞节点的链路赋予权重,并利用此权重计算有效距离,这种权重分配策略减小了网络的最大负载,提高了网络容量,缓解了网络拥塞,保证传输效率。

以上路由算法大多是针对网络拥塞问题以及网络传输容量和效率的研究,并未涉及网络能耗问题。为此,本文针对网络能耗巨大的问题,借助于复杂网络中关于复杂系统的理论研究,展开对网络结构和功能的关系研究,提出基于复杂梯度网络的能效优化路由算法。

1 复杂梯度网络简介

随着信息化的发展,网络渗透到生活的边边角角,复杂网络的信息流的传输属于典型的动力学过程。在很多真实网络中,信息传输过程并非是随机的,而是倾向更高效的传输方式,某些实体的局部的梯度引起输运过程,网络中的信息、能量和物质的输运就是沿着这些实体的梯度方向进行。综合网络结构特征和信息传输的动态特性提高数据传输效率,却需要掌握全局信息,这对于日渐增大的网络规模很难实现。于是,物理学家试图通过纯量场的梯度分布来研究网络输运[13],梯度输运在日常生活中非常普遍,将物理学与网络科学紧密联系在一起,提供了一种有效的网络输运模式。近年来,很多研究开始将梯度标量场与局域拓扑联系起来提高网络的传输效率。

2004年,Toroczkai和Bassler提出由底网局部梯度引发的输运过程,并称由分布在节点上的区域梯度导出一种有向图之为梯度网络[14]。Toroczkai和Bassler给出的梯度网络的模型定义:首先,选取一个包含N个节点的基网S,给每个节点i赋予一个标量场,随机的选取0到1之间的数值作为节点的标量,数值记为hi,hi用于刻画点i的潜力,从每个节点i,引出一条线,引出的线的方式:从每个节点i引出一条指向底网中与节点i相连的所有邻居里面势最大的点的线。若节点i的势最大,那么就指向自身,这样保证了网络中的每个节点都有一条出线,如图1所示。

图1 梯度网络定义

Toroczkai和Bassler[14]又通过数值模拟发现,不管基网是无标度网络还是随机网络,当hi是独立分布的随机变量,得到的梯度网络均是无标度网络。不同之处在于,若基网是无标度网络,那么得到的梯度网络的与基网有相同的指数,若基网是随机网络,得到的梯度网络的入度分布是指数γ=1的幂率分布。Park和Lai[15]将梯度运输应用于随机网络和无标度网络。研究了随机梯度网络和无标度梯度网络下的网络拥塞,发现无标度梯度网络在平均度大于10时,网络阻塞比随机梯度网络小。

关于梯度驱动机制,以上的研究都是基于随机选取的标量值,没有考虑标量场和网络结构的关系。本文提出基于复杂梯度网络的梯度驱动路由(Gradient Dirven Routing,GDR)算法,运用梯度驱动机制,选取的标量场取决于邻居节点的介数,达到提高网络能效的效果,最终实现节能减排。

2 系统模型和能效优化传输策略

2.1 网络模型

考虑许多现实网络服从幂率分布,即具有无标度网络的特性,本文采用以无标度网络为底网构造的梯度网络模型。网络节点总数为N,为每个节点赋予一个标量场,即节点“势”,节点“势”代表节点的潜力。由于节点的介数能更加具体的体现节点的中心性和负载压力,因此选取节点介数这一结构特性作为影响节点“势”的因素。节点“势”由其邻居节点的介数决定,定义为:

(1)

其中,Bj为节点j的介数,j为i的邻居节点。

2.2 流量模型

在本文采用广泛使用的流量模型,将每一个节点看作路由和主机,即每个节点既可以产生数据包同时也可以转发数据包。网络中每个时间步有R个数据包产生,并且每个数据包随机的选取源节点和目的节点。每个节点的队列长度是一定的,采用先进先出的队列管理策略。每一步每个节点向目的节点最多转发C个数据包,一旦数据包到达目的节点,将被移出网络。数据包的转发速率为:

(2)

其中,ni,j为时间步为(t-1)缓冲区中队列长度,Ri,j为i,j连边的最大带宽。

2.3 梯度驱动能效路由算法

任意节点均可以看作是主机和路由器,即均具有产生和转发数据包的功能。任意源节点s到任意目的节点t的路径可以定义为:

p(s→t):=s≡x0,x1…,xn-1,xn≡t

(3)

其中,(x0,x1,…,xn-1,xn)为(s→t)经过的节点。

采用梯度驱动机制进行数据包的转发,任意节点s转发数据包到节点t是依据节点t的“势”,即节点t是节点s的邻居节点中“势”最小的节点,转发路径可以定义为:

(4)

其中,α为调节因,当α为0时即为最短路径,α不为0时,使得L取得最小值就是本文提出的梯度驱动路由策略。

(5)

由于传输容量的最大值取决于拥塞点,拥塞出现在介数最大的节点,因此:

(6)

对于节点和链路能耗:

(7)

PLij=f(r)=ηerδ,r>0

(8)

总能耗可以表示为:

P=PNi+PLij=f(r)=σe+μerε+ηerδ,r>0

(9)

其中,PNi和PLij分别为节点和链路能耗,σe为基础能耗,ηe,μe,ε为调节因子。

3 仿真及结果分析

本文采用度分布符合幂率分布为P(k)～k-2.5的无标度网络为底网,选取100个节点,使用Python+networkx+matplotlib和Matlab做仿真模拟。本文选取SPR和ER进行实验对比,SPR为最短路径路由算法,ER为Yan等人提出的有效路由算法,GDR为本文提出的梯度驱动路由算法。

数据包产生速率与平均能耗的关系如图2所示,在数据包产生速率较小时,SPR数据包的传输为最短路径的能耗较小,随着数据包产生速率的增加,SPR发生拥塞,而GDR对于数据包产生速率的增长没有SPR敏感,而且由图2看出,比ER算法节能,本文提出的GDR显示了在能耗方面的优势。

图2 数据包产生速率与平均能耗

平均能耗与参数α的关系如图3所示,在α为0.3时,路由选择策略为GDR,由图3可知,此时的平均能耗最小,GDR算法,绕过了介数较大的节点,对于缓解了数据包在产生速率较大时的拥塞,从而达到节能的效果。

图3 α与平均能耗的关系

数据包的产生速率和转发时间的关系如图4所示,在数据包产生速率较小时,网络转发能力足以转发产生的数据请求,随着数据请求的增加,SPR在重要节点就会发生拥塞行为,使数据包不停的等待重发,导致转发时间增加,ER绕过的是节点度较大的节点,节点度大不一定节点介数大,还会在一些节点介数大,但节点度却不大的节点上出现拥塞,而GDR在转发数据包时绕过了介数较大的节点,因此,转发时间得到改善。

图4 数据包的产生速率与平均转发时间的关系

网络节点数和平均路径长度的关系如图5所示,获得收益的同时就要付出代价,GDR降低网络能耗是以牺牲平均路径长度为代价的。GDR绕过介数较大的节点,也即放弃选择最短的路径,以获得能效优化的效果。从图5可以看出,比ER算法的平均路径长度短。

图5 网络节点数与平均路径长度的关系

4 结束语

本文通过对现实网络建模,构造以无标度网络为底网的复杂梯度网络模型,提出梯度驱动路由策略。Python仿真验证了其能取得较好的效果。下一步的主要工作是通过继续探索网络结构,利用网络自身的特性构建绿色网络体系。

[1] WATTS D J,STROGATZ S H.Collective Dynamics of ‘Small-world’ Networks[J].Nature,1998,393(6684):440-442.

[3] 丁 琳,张嗣瀛,鹿江春.加权无标度网络抵制级联失效的鲁棒性研究[J].计算机工程,2012,38(21):261-263,267.

[4] NIU R W,PAN G J.Transport Optimization on Complex Gradient Networks[J].Chinese Journal of Physics,2016,54(2):278-284.

[5] DANILA B,YU Y,EARL S,et al.Congestion-gradient Driven Transport on Complex Networks[J].Physical Review E,2006,74(2).

[6] PIONTTI A L P,BRAUNSTEIN L A,MACRI P A.Jamming in Complex Networks with Degree Correlation[J].Physics Letters A,2010,374(46):4658-4663.

[7] WANG B,AIHARA K,CHEN L.Jamming in Weighted Scale-free Gradient Networks[J].Europhysics Letters,2008,83(2):28006.

[8] YAN G,ZHOU T,HU B,et al.Efficient Routing on Complex Networks[J].Physical Review E,2006,73(4).

[9] NEWMAN M E J.The Structure and Function of Complex Networks[J].SIAM Review,2003,45(2):167-256.

[10] MUKHERJEE S,GUPTE N.Gradient Mechanism in a Communication Network[J].Physical Review E,2008,77(3).

[11] LIU Z,HU M B,JIANG R,et al.Method to Enhance Traffic Capacity for Scale-free Networks[J].Physical Review E,2007,76(3).

[12] LI M,LIU F,REN F Y.Routing Strategy on a Two-dimensional Small-world Network Model[J].Physical Review E,2007,75(6).

[13] ANGHEL M,TOROCZKAI Z,BASSLER K E,et al.Com-petition-driven Network Dynamics:Emergence of a Scale-free Leadership Structure and Collective Efficiency[J].Physical Review Letters,2004,92(5).

[14] TOROCZKAI Z,BASSLER K E.Network Dynamics:Jamming is Limited in Scale-free Systems[J].Nature,2004,428(6984):716-716.

[15] PARK K,LAI Y C,ZHAO L,et al.Jamming in Complex Gradient Networks[J].Physical Review E,2005,71(6).