基于能耗感知的路由与频谱分配方法设计.docx
- 文档编号:12780732
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:22
- 大小:253.46KB
基于能耗感知的路由与频谱分配方法设计.docx
《基于能耗感知的路由与频谱分配方法设计.docx》由会员分享,可在线阅读,更多相关《基于能耗感知的路由与频谱分配方法设计.docx(22页珍藏版)》请在冰点文库上搜索。
基于能耗感知的路由与频谱分配方法设计
本科毕业设计(论文)
学院(部)
电子信息学院
题目
基于能耗感知的路由与频谱分配方
法设计
年级
2014级
专业
通信工程
班级
14通信工程
学号
1428404048
姓名
江云飞
指导老师
陈伯文
职称
副教授
论文提交日期
2018.5.29
摘要
伴随着这些年来互联网技术的迅猛发展,人们之间的信息交流愈加频繁,信息交流量急剧增加,带宽需求量以一种不可抑制的速度增长。
这对未来网络的性能、规模和结构提出了更高的要求,同时未来网络也面临着高容量、低能耗等多方面的挑战。
传统的波分复用光网络因为其“一刀切”的固定模式,导致网络运行阻塞严重、频谱利用率低下;而频谱灵活光网络则可以根据用户的实际需求灵活地分配频谱资源,从而降低网络阻塞率、提高频谱利用率,在降低能耗方面也具有显著的优势。
合理的路由与频谱分配算法能够大大提高网络的生存能力、减少能耗,所以路由和频谱分配算法的优化对频谱灵活光网络性能的提高十分重要。
本文提出了2种路由和频谱分配算法:
最短路径首次命中算法以及K条最短路径首次命中算法。
为了比较这两种算法的优劣性,将这2种算法在相同的条件下进行仿真。
仿真中,主要关注网络阻塞率、平均能耗以及总能耗三个参数之间的对比。
仿真结果表明,最短路径首次命中法和K条最短路径首次命中法各有长处。
关键词:
频谱灵活光网络路由和频谱分配算法能耗
ABSTRACT
WiththerapidevolutionofInternettechnologyovertheyears,thecommunicationamongclientsbecomesincreasinglyfrequentandtheamountofinformationincreasesdramatically.Also,thebandwidthdemandhasgrownatanirrepressiblespeed.Thisputsforwardhigherrequirementsontheperformance,scale,andstructureofthefuturenetwork.Atthesametime,thenetworkisalsofacedwithmanychallengessuchashighcapacityandlowenergyconsumption.
Thetraditionalwavelengthdivisionmultiplexingopticalnetworkadoptsa“one-size-fits-all”mode,resultinginhighnetworkcongestionandlowspectrumutilization.However,thespectrumflexibleopticalnetworkcanflexiblyallocatespectrumresources,reducingnetworkblockingrateandimprovingspectrumutilization,whichhassignificantadvantagesinreducingenergyconsumptionaswell.Anintelligentandefficientroutingandspectrumallocationalgorithmcangreatlyimprovethesurvivabilityofthenetworkandreduceenergyconsumption,sotheoptimizationofroutingandspectrumallocation(RSA)isakeyissueinspectrum-flexibleopticalnetworks..
Inthisdissertation,weintroducetwoRSAalgorithms,includingtheshortestpathalgorithmwiththefirst-fitspectrumallocation(SP_FF)andtheKshortestpathalgorithmwiththefirst-fitspectrumallocation(KSP_FF).Forcomparison,wesimulatetheseroutingandspectrumallocationalgorithmsinthesameconditions.Inthesimulation,wefocusonthecomparisonamongthethreeparametersofnetworkblockingrate,averageenergyconsumptionandtotalenergyconsumption.Thesimulationresultsshowthattheshortestpathalgorithmwiththefirst-fitspectrumallocationandtheKshortestpathalgorithmwiththefirst-fitspectrumallocationbothhavetheirownadvantages.
Keywords:
Spectrumflexibleopticalnetwork,routingandspectrumallocationalgorithm,theenergyconsumption
第一章绪论
随着互联网业务的普及,高容量、易分配、低功耗必定会成为今后网络发展的趋势。
其中,能源消耗是目前网络信息传输所面临的严峻挑战之一,也是近年来光网络领域的研究热点。
本章首先介绍了目前频谱灵活光网络的发展状况和未来发展趋势,然后介绍了近年来国内外在光网络阻塞率以及能效性方面的研究成果,最后对本论文的结构进行了初步的规划。
1.1频谱灵活光网络的发展状况
由于传统光网络在带宽的调整、性能的调节以及网络的控制等多方面已经不能适应时代发展的需求,日本电信公司(NTT)在2008年九月首先提出一种新型网络概念即频谱切片弹性光网络(SLICE)[1],这种网络体系架构具有新型、高频谱效率和可扩展的特点,可以有效地解决传统光网络的问题,因此受到各国研究人员的广泛关注并且迅速成为研究的重点。
在美国,GringeriS等人提出了关于FWDM网络的相关架构,描述了FWDM网络的拓扑图,以及业务在传输时所需要的相关技术[2,3]。
与此同时,Finisar公司开展了一种名为FlexGrid的全光网项目,它基于全光网络并且原理与频谱灵活的全光网技术原理相近,同时侧重于灵活栅格网络结构,文献[4]预言该网络必将成为未来骨干网的架构基础。
而在欧盟,这方面研究的弹性光网络项目是由Alcatel-LucentBellLab和OliverRival联合提出的[5],这个项目通过让网络通信参数变得可调节,有效地提高网络的利用率,降低网络付出成本,并且可以使网络变得更加高效节能。
频谱灵活光网络与传统光网络相比具有更加明显的优势。
它的基本思想阐述如下:
在客户需求和实际业务量的基础之上,动态灵活地分配带宽资源,不再限制通道间隔并实现全光交换;精细化的频谱域分割与灵活的控制管理,从而提高频谱灵活光网络的频谱利用率,提高各个路由节点的能源效率,推动绿色发展。
综上所述,新兴的频谱灵活光网络和组网技术是目前各专家及相关产业的研究热点,它完全适应了超大容量、绿色节能的网络发展要求。
它具有不可比拟的优势,同时又顺应了未来全光网络的发展趋势以及社会的需求,是值得探究的发展方案,前景十分广阔。
1.2国内外的研究现状
1.2.1国外研究现状
由于传统光网络的缺陷以及能源的紧缺,国内外的专家和学者很早就开始着手研究性能更加优越的频谱灵活光网络。
这些年来,频谱灵活光网络在能效性和频谱资源分配优化相关技术的发展得到了质的飞跃。
在能源效率方面,文献[6]提出混合线路速率方法来减少IPoverDWDM网络中的转发器总数的功耗。
文献[7]的研究中了解了网络连接中断对于成本以及能源效率的影响,并且制订了相关的升级策略来降低混合线路速率光网络的网络成本和能耗。
在文献[8]中在分析位置距离对多粒度光网络的影响后,提出了绿色节能的优化方法,而这些设计方法的最终目标是将功耗降到最低的程度并把光信号传输中的光学领域限制集中起来。
在文献[9]中,研究人员考虑到最小化混合线路速率光网络的总能耗的目标,同时还解决了节能减损限制再生器放置问题。
在频谱资源分配优化算法方面,通过运用整数线性规划算法和两种启发式算法来实现频谱灵活光网络中的频谱重构,最终结果发现:
在使得受损的连接请求数目最少的条件下,网络频谱重构能够有效地去利用可用频谱并降低频谱碎片出现的概率[10]。
文献[11]提出了一种基于带宽自适应调制的动态频谱重构算法,这种算法可以使得网络阻塞率至少降低10%,可以有效提高网络性能。
1.2.2国内研究现状
在国内,随着互联网技术的不断发展,频谱灵活光网络的阻塞率和能源效率也得到了广泛的关注,产生了不少研究成果。
在文献[12]中,学者们重点研究了在可生存光网络中通过可切换多流量转发器和弹性再生器来来提高能效的问题:
提出了整数线性规划(ILP)模型和最小单位能量子矩阵映射方法,来尽可能地降低功耗和提高能源效率。
文献[13]为了通过联合应用光路旁路和路由卡睡眠策略来降低总能耗,提出了能源消耗较少的IPoverWDM网络。
文献[14]提出了基于可分片带宽可变光转发器(SBVT)的流量疏导整数线性规划算法,验证了SBVT的可分片能力对网络性能的影响,最终结果显示配有SBVT设备的流量疏导技术可以显著地降低电疏导能耗,减少实际网络中的转发器耗能器件成本。
在路由和频谱分配方面,文献[15]里面提出了一种新的路由频谱配置方法,这种配置方法在弹性光网络中运用了自适应分配式子载波的概念,同时在网络的各个链路节点之间自适应地建立起一条或多条光路来进行信息的传递,从而有效地降低网络阻塞率,提高频谱资源利用率。
无论是国内国外,如何提高能源效率、降低阻塞率一直都是光网络的研究重点。
因此,从阻塞率和能源效率的角度来看,优化的路由和频谱分配算法就显得格外重要。
本文即是从这一方面出发,通过改善网络路径来提高能源利用效率、降低网络阻塞率,探究更加有效的算法,进而提高网络性能。
1.3论文结构
本篇论文主要工作安排如下:
第一章主要先介绍了这些年来频谱灵活光网络的发展概况和未来发展前景,然后介绍了国内外在光网络能效性以及频谱资源分配优化方面的优秀研究成果,最后阐述了本论文的整体结构。
第二章重点介绍了频谱灵活光网络中的路由计算算法:
最短路径算法和K条最短路径算法以及频谱分配算法中的首次命中法。
然后根据以上的算法分析,提出基于能耗感知的传统与优化路由和频谱分配算法,以比较它们对网络性能的影响。
第三章将之前提出的传统与优化的路由和频谱分配算法在相同的网络环境中进行仿真,对比这2种算法在网络阻塞率、总能耗和平均能耗三个参数的差别,分析它们的优势和不足之处,并考虑它们在实际生活中的应用之处。
第四章对本篇论文进行系统的总结与展望,并指出今后需要进一步探究的工作。
第二章频谱灵活光网络中基于能耗感知的路由和频谱分配算法
2.1频谱灵活光网络中的路由计算算法
在读取连接请求的相关信息后,首先需要从网络中选取较为合适的路径,这样有利于降低网络阻塞率、提高能源利用率。
这一节介绍的网络的路由计算算法有最短路径算法和K条最短路径算法。
2.1.1最短路径算法
最短路径算法运用的最主要的算法是Dijkstra算法,根据连接请求的源宿节点,在网络中通过依次计算路径长度选取最短的路径。
在网络拓扑图(如图2.1所示,图中各数值为两节点之间的权值并且是双向路径)中根据每个连接请求的源点和宿点,利用Dijkstra算法计算出最短的路径。
图2.1网络拓扑图
根据图2.1的网络拓扑图,使用Dijkstra算法计算最短路径描述如下:
假设选取源点为A,A到各节点(B、C、D、E和F)的直接路径长度依次为1、2、∞、∞和∞(如图2.2所示)。
首先选出与A距离最小的一点B(距离为1),查找B到其他各点的距离,将其与1相加得到A与各点的距离,并与原有的距离数据相比较,实时更新(取较小的值);在除去B之外取与A距离最小的一点C(距离为2),查找C与其他各点的距离,将其与2相加得到A与各点的距离,并且与原有的数据相比较,去较小的距离值进行更新;重复进行以上的操作,直到D、F、E都被使用过为止,这样就可以得到A到其余所有节点的最短距离。
因此,在图2.1中,假设连接请求的源点为A、宿点为F,通过上述方法计算可以得到最短路径为A-B-D-F。
图2.2最短路径算法
2.1.2K条最短路径算法
K条最短路径算法(KSP算法)的基础是最短路径算法,以牺牲路径的长度来降低网络的阻塞率,即先计算得到多条较短的路径作为备用,当最短的路径发生阻塞时,可以选取下一优先级的路径完成连接请求。
算法描述如下,首先利用上述的Dijkstra算法进行计算得到最短路径,然后利用删除算法在最短路径上进行扩展,计算得到第
图2.3网络拓扑图
2条最短路径;再从第2条最短路径进行扩展,以此重复可以计算出多条最短路径。
K条最短路径算法的优势在于可以提高网络的灵活性,同时降低网络的阻塞率。
在图2.3网络拓扑图中,假设K=3,连接请求的源点为1、宿点为7,首先可以通过最短路径算法直接得到最短路径为1-2-3-4-7。
如图2.4所示,通过对最短路径的扩展,可以依次计算得到第2条最短路径1-2-3-6-4’-7’和第3条最短路径1-2-5-6’-4”-7”。
图2.4网络拓扑扩展
2.2频谱灵活光网络中的频谱分配算法
在计算得到相应的最短路径后,需要根据连接请求的需求在该路径上分配频谱资源,分配成功后才可以建立一条合适的光路径。
因此,优化的频谱分配算法十分重要。
2.2.1频谱分配的约束条件
通常情况下,频谱灵活光网络和传统波分复用光网络都存在波长一致性的要求。
但不同的是,传统的路由和波长分配计算只需要满足波长一致性约束条件;而频谱灵活光网络中的路由和频谱分配计算过程中则包括有两个层面的频谱一致性要求:
频谱的连续性和频谱的邻接性。
如图2.5所示,有一条网络路径(A-B-C-D),A、B、C和D均为节点,将这些链路的所有频谱间隙进行编号:
0,1,2,3,...,N。
假设某一连接请求在A-B链路上分配的频谱间隙编号为0和1,那么它在其他链路上分配的频谱间隙编号也必须为0和1。
图2.5频谱连续性
频谱的邻接性是指光路径在频谱轴上占用编号连续的频谱间隙。
如图2.6所示,假设有一个连接请求的带宽需要占用3个频谱间隙,并且从第K个频谱间隙开始分配频谱资源,那么这个连接请求所占用的频谱段编号就是K,K+1和K+2。
因此,在满足频谱连续性和频谱邻接性后,频谱分配算法主要有两种:
随机命中法和首次命中法。
随机命中法是在分割的频谱段中随机选取可用的频谱空间进行使用,往往网络阻塞率会比较大。
本文主要对首次命中法进行阐述。
图2.6频谱的邻接性
2.2.2首次命中法
在首次命中法中,先将所有的可用频谱段依次进行编号,然后在搜索可用频谱段的时候,会先优先选取编号低的频谱段,从而将它作为第一个可用频谱段,所以当新的业务到来时,会自动选取较低位置并且频谱空间足够大的空间来进行。
这种方案核心的思想是,让所有进行业务的频谱段都尽量在频谱空间中编号较低的地方,从而使得频谱空间的高端位置会有连续的更长的路径可用频谱资源,有助于之后连接请求的建立成功。
假设路径A-B-C是如图2.7所示的状态情况,对每一频谱段进行编号并对它们的状态进行标号(“1”代表占用,“0”代表空闲,从编号5开始往后状态均为“0”),根据频谱的连续性,将编号相同的频谱段中的标号依次做逻辑运算中的“并”运算,得出这条路径的总体频谱占用情况。
若某一连接请求需要占用2个频谱段,则可以从最上方开始搜索选取连续的2个频谱段,即占用编号为1和2的频谱段;若这一连接请求需要占用3个频谱段,则占用编号为4、5和6的频谱段。
图2.7首次命中法
2.3基于能耗感知的传统与优化路由和频谱分配算法
为了对比上文路由计算算法与频谱分配算法对网络性能(能效性)的影响,本文将这几种算法组合成2种路由和频谱分配算法:
最短路径首次命中法和K条最短路径首次命中法。
这里主要会对这2种算法的流程进行详细的描述。
1.基于能耗感知的传统路由与频谱分配算法
在这里,传统的路由与频谱分配算法即最短路径首次命中法,通常算法难度较低。
如图2.8所示,基于能耗感知的传统路由与频谱分配算法描述如下:
第一步:
初始化网络,并输入一组连接请求;
第二步:
查询所有连接请求是否都已经遍历,如果全部遍历,则直接转至第六步,否则选取下一连接请求;
第三步:
根据对应连接请求的源点和目的点,利用最短路径算法计算得到一条最短路径,如果无法找到可用路径,则连接阻塞并返回第二步;
图2.8基于能耗感知的传统路由与频谱分配算法
第四步:
在计算得到的最短路径中,首先查找空闲的频谱空间,然后根据对应连
接请求所需的频谱段数,利用首次命中法在相应的链路中分配频谱资源(需满足频谱分配的连续性和邻接性),分配成功后再根据链路的需求设置相应的再生器和转发器;如果没有找到合适的频谱空间,则连接阻塞并返回第二步;
第五步:
计算得到相应的转发器和再生器的能耗,同时在连接请求结束后转至第二步;
第六步:
计算阻塞率、总能耗和平均能耗三个参数。
2.基于能耗感知的优化路由与频谱分配算法
优化的路由与频谱分配算法即K条最短路径首次命中法。
与最短路径算法求得的单一最短路径相比,K条最短路径算法计算得到了多条最短路径,它可以在一条路径阻塞时使用另一条较短路径来完成业务,这样就能达到降低网络阻塞率的效果。
如图2.9所示,基于能耗感知的优化路由与频谱分配算法描述如下:
图2.9基于能耗感知的优化路由与频谱分配算法
第一步:
初始化网络并输入一组连接请求;
第二步:
查询所有连接请求是否都已经遍历,如果全部遍历,则直接转至第六步,否则选取下一连接请求;
第三步:
根据对应连接请求的源点和目的点,利用K条最短路径算法(K=3)计算得到3条具有优先级的最短路径(总权值小的路径优先级会更高),如果1条合适路径都未找到,则连接阻塞并返回第二步;
第四步:
根据对应连接请求所需的频谱段数,利用首次命中法按照优先级顺序在3条最短路径中查找可用的频谱空间并分配频谱资源(需满足频谱分配的连续性的邻接性),直至频谱资源分配成功为止,分配成功需要针对相应的路径设置再生器和转发器;如果没有找到合适的频谱空间,则连接被阻塞并返回第二步;
第五步:
计算得到相应的转发器和再生器的能耗,同时在连接请求结束后转至第二步;
第六步:
计算阻塞率、总能耗和平均能耗三个参数。
3.能耗计算模型
每一连接请求的能耗主要由路由IP层端口(2个)、转发器(2个)和再生器(未确定)所消耗的能耗共同构成。
由于光信号最大传输距离的限制,再生器的数目需要根据具体的路径来进行判断;同时,以上的IP层端口、转发器和再生器的功率是由元器件的参数计算。
总能耗的计算公式如下:
表示根据路径设置的再生器数量,
表示连接请求需要占用的频谱间隙数,
表示IP路由端口功耗,
表示转发器功耗,
表示再生器功耗。
如图2.10所示,有一条网络路径(A-B-C-D),假设光信号的传输距离最大为100,则需要在3号路由节点处设置一个再生器。
如果在正常路径中传输,从源节点开始,每当有两节点(假设为A和B节点)之间的距离大于最大传输距离,就要在B节点的前一个节点处设置再生器。
图2.10再生器的设置
2.4小结
本章先介绍了路由计算算法:
最短路径算法和K条最短路径算法,然后阐述了频谱灵活光网络中频谱分配的两个约束条件,同时详细介绍了较为优化的首次命中法。
为了找到更加高效的算法,将上述算法结合提出基于能耗感知的传统与优化路由和频谱分配算法,并对这2种算法进行了详细的阐述。
第三章仿真与结果分析
在前两章的描述中,分别提出了基于能耗感知的传统与优化路由和频谱分配算法,即最短路径首次命中法(SP_FF)和K条最短路径首次命中法(KSP_FF)。
本次仿真中,在相同的条件下,利用C++编程在VisualStudio2015中对传统与优化的路由和频谱分配算法进行仿真,得到它们在阻塞率、总能耗和平均能耗三个方面的数据表现。
通过这三个参数的对比,来分析传统与优化算法的优劣性。
3.1仿真条件的设置
假设一个网络结构N(V,L,F),在这之中,V表示网络中的各个路由节点,L代表网络中的各条链路,F代表网络中各条链路所分割的频谱间隙数目。
在本次仿真中,会将两种算法在如图3.1所示的网络拓扑图中进行仿真。
其中,该NSFNET网络含有14个网络路由节点,包含21条链路;同时,每条链路被分割成100个频谱间隙,并且每一条链路都是双向的。
设置某一连接请求Con(s,d,w,a,b),s表示某一连接请求的源点,d表示该连接请求的目的节点,w表示该连接请求所要占用的频谱间隙数目,而a和b则分别表示该连接请求的开始时间以及结束时间。
仿真参数设置如下:
(1)每一个连接请求源点和目的节点服从均匀分布,每一连接请求所占用的频
图3.1NSFNET网络拓扑图
谱间隙数目是随机的;
(2)连接请求总数设置为10000,同时为了降低算法的复杂度,设置各条路径的权值均为1,并且设置K=3;
(3)每一连接请求的开始和结束时间也是随机的,但连接请求的开始与结束时间间隔服从负指数分布,而两个连接请求之间的时间间隔服从泊松分布;
根据上述参数的设置,来将传统与优化的路由和频谱分配算法在阻塞率、总能耗和平均能耗三个方面进行网络性能的对比。
3.2仿真结果与讨论
本节将利用传统与优化的路由与频谱分配算法在网络拓扑图中进行仿真,围绕网络阻塞率、平均能耗和总能耗三个参数进行对比,并对结果进行计算分析,得出较为优化的路由和频谱分配算法。
1.网络阻塞率
阻塞率是指被拒绝的连接请求数目与连接请求总数的比值。
比值越小,网络阻塞率越低,网络性能越好。
图3.2NSFNET中传统与优化算法在不同业务量下的网络阻塞率
如图3.2所示,仿真结果显示,优化的路由与频谱分配算法有着较低的阻塞率。
在网络负载压力较小时,优化算法的阻塞率比传统算法大约低70%;在网络负载压力较大时,优化算法的阻塞率比传统算法低约30%。
由于之前将所有链路的权值都设置为1,因此采用最短路径算法时可能会将一些连接请求同时分配到同一条链路上,频谱资源不够分配,从而造成连接请求的阻塞;而采用K条最短路径算法分配业务时,如果某一最短路径发生阻塞,还可以通过使用下一优先级的路径来分配频谱资源,这样就可以有效地降低网络阻塞率。
同时,网络负载增大时,业务建立的成功率会降低,导致最短路径算法和K条最短路径算法都很难在网络中建立业务,所以阻
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 能耗 感知 路由 频谱 分配 方法 设计