新一代电力ICT网络中基于DiR保护环的生存性路由算法.pdf

  • 文档大小:392.51 KB
  • 文档格式:pdf
  • 约 5页
  • 2021-06-24 发布
  • 举报
新一代电力ICT网络中基于DiR保护环的生存性路由算法1 新一代电力ICT网络中基于DiR保护环的生存性路由算法2 新一代电力ICT网络中基于DiR保护环的生存性路由算法3 新一代电力ICT网络中基于DiR保护环的生存性路由算法4 新一代电力ICT网络中基于DiR保护环的生存性路由算法5
已阅读完毕,您还可以下载文档进行保存
文档单价:6.00 会员免费
开通会员可免费下载任意文档
  1. 1、本文档共5页,内容下载后可编辑。
  2. 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,可选择认领。
  3. 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形,可联系本站下载客服投诉处理。
第39卷第16期2011年8月l6目电力系统保护与控制PowerSystemProtectionandControl、,ol_39No.16Aug.16,2011新一代电力ICT网络中基于DiR保护环的生存性路由算法吴润泽,祁宏鹏,唐良瑞(华北电力大学电气与电子工程学院,北京102206)摘要:电力通信网中对业务的可靠性保护占用过多的网络资源,通过研究智能电网业务的可靠性要求对网络资源利用率的影响,提出了一种基于区分可靠性保护环的生存性路由算法。在网络单链路失效条件下,以链路代价和链路失效概率为约束条件,通过寻找最小通路代价的保护环,使连接请求建立在满足失效概率要求和最小化通路代价的光通道上。仿真结果表明,所提算法提高了网络资源的利用效率,满足智能电网的可靠性需求,减少了网络资源的占用,性能优于传统方法。关键词:智能电网;生存性;保护环;区分可靠性;路由算法SurvivalroutingalgorithmbasedonDiRprotectionringinnovelpowerICTnetworkWURun-ze,QIHong-peng,TANGLiang-rui(SchoolofElectric&ElectronicEngineering,NorthChinaElectricPowerUniversity,Bering102206,China)Abstract:TheprotectionsofservicesinpowercommunicationnetworkoccupySOmanynetworkresources.Throughstudyingtheinfluenceofreliabilityrequirementsofsmartgridservicesonthenetworkresourceutilizationefficiency,thesurvivalroutingalgorithmbasedondifferentiatedreliabilityprotectionringisproposed.Ontheconditionofasinglelinkfailureinthenetworkandundertheconstraintoflinkcostandlinkfailureprobability,throughfiridingaminimumcostpathprotectionring,theconnectionrequestisestablishedonthelightpathwhichcansatisthefailureprobabilityrequirementandminimizethepan1cost.Simulationresultsshowthatthe ̄gofithrncanimprovethenetworkresourcesutilizationefficiencywithmeetingthereliabilityrequirementsofsmartgridandreducingtheoccupyingratioofnetworkresources,andtheperformanceisbetterthanthatoftraditionalmethods.Keywords:smartgrid;survivability;protectionring;differentiatedreliability(DiR):routingalgorithm中图分类号:TM744文献标识码:A文章编号:1674.3415(2011)16.0025.050引言电力信息通信技术是支撑智能电网发展的主要技术之一【lJ,现代信息技术、通信技术与电网技术紧密结合,构建起信息化、自动化、互动化的智能电网【2j,向用户提供更加全面、安全、便捷、舒适的服务。电力企业开展光传送网络、智能光网络、自动交换光网络等信息通信技术的研究,统一规划信息网络和通信网络,使信息通信网更好地服务于电力系统【3J。智能光网络技术在电力通信网中的应用将极大地改变传输网的理念和运行方式,智能化电力光传输网络将是未来发展的必然趋势。由于智能电网中光网络技术的广泛应用,其可靠性问题备受关注。传统的WDM光网络只向用户基金项目:中央高校基本科研业务专项资金(09QG02);国家“”电网项目新一代电力信息通信(ICT)网络模式研究提供两种级别的可靠性服务【4】。随着电力信息通信技术的发展,对网络业务质量要求的多样化,为电力用户提供区分的可靠性服务是智能电力通信网络发展的趋势。文献[5.6】研究单链路失效模型下的环网中的可靠度约束路由问题,文献【7.8】研究单链路失效模型下WDM网状网中有可靠度约束时的静态规划问题,并提出了一种基于模拟退火的两步算法。在文献【9】中提出单链路失效模型下WDM网状网中的提供区分可靠服务时的恢复机制,然而,这些研究仅考虑了可靠度约束下的静态规划问题。由于当前的网络越来越复杂,网络需要动态地进行路由。文献[10】提出了单链路失效模型下WDM网状网中有可靠度约束时的动态路由连接保护问题,但是耗费的网络资源较高。针对电力通信网中智能电网业务的可靠性问题,本文提出了一种基于保护环的区分可靠性路由算法(theroutingalgorithmwithdifferentiated电力系统保护与控制reliabilityrequirementsbasedonprotectionring,DRPR),使得路由连接在满足可靠性要求的前提下,网络资源消耗最低,从而提高网络资源的利用效率。1问题描述假定光网络的物理拓扑为G=(),其中为节点集,为链路集。令n、m分别表示网络G中的节点数和链路数。假定每个网络节点都具有全波长变换能力,并且网络中的每条链路都是可以双向传输的光纤。因此任何一条链路失效意味着该链路上任何一个方向的传输都会中断。另外假设链路的容量足够大,对于每个连接请求,每条链路都满足连接请求的带宽需求。每条链路(i,,)都有两个链路参数:链路代价c(f,,)和链路失效概率(.,)。链路代价c(f,,)代表单位带宽(如一个波长)上数据信息从该链路的一端f传送到另一端,所消耗的代价。给定一条通路P,该通路的代价就是该通路上所有链路的代价之和。链路失效概率尸,(f,,)是指在网络中只有一条链路失效的条件下链路(i,,)失效的条件概率。令表示网络中平均每条链路的单位长度失效时间,令length(i,,)表示链路(f,i,)的长度并令SFP表示网络G中单个失效的概率::∑length(i,(1)链路(i,,)的失效概率:Pf(i,i、)=・length(i,i、iSFP(2、)给定一条通路P,在单链路失效的假设下,该通路的失效概率为该通路上所有链路的失效概率之和。业务请求R=(,)动态的到达网络,其中S为业务请求的源节点号、f为业务请求的目的节点号,表示连接请求允许的最大失效概率值。每个业务请求达到之后,要根据当前的网络状况为该连接请求计算一条路由,使得这条路由的最大失效概率要小于连接请求允许的最大失效概率并且期望这条路由耗费的代价最小。如果一条通路的失效概率不大于连接请求的允许的最大失效概率,则这条通路就可以作为连接请求的路由。然而在有些情况下,一条通路的失效概率会大于连接请求允许的最大失效概率。以图1为例,其中每条边旁边的数字表示该边的链路代价和失效概率,并假定网络中链路带宽足够大。对于连—接请求(1,7,=0_3)而言,由于通路AP=I.2.57的失效概率为0.3,刚好等于连接请求允许的最大失效概率,因而可以选择通路AP作为这个连接请求的路由。如果该连接请求允许的最大失效概率不是0-3而是0.25,则图1中没有任何一条通路的失效概率小于连接请求允许的失效概率,从而没有任何一条通路可以单独用来作为该连接请求的路由。然而,如果通路AP上的链路2.5与路径BS=2.4.5组成一个保护环的话,由于网络中只有单个链路失效,则—当链路25失效后该连接请求可以通过通路——l-2-457来路由。因而通路AP和路径BS一起为连接请求提供的失效概率为0.2,小于连接请求允许的最大失效概率0.25,从而通路AP和路径BS一起可以作为该连接请求的路由。————————————'.AP…….图1单链路失效时链路保护示例Fig.1Thelinkprotectionexampleinsinglelinkfailure当网络中只有单个链路失效,对于一条给定的通路Jp而言,如果P上的某条链路,和一条路径明组成了一个保护环,那么当通路P中的链路Z失效后,连接请求仍然可以利用通路尸上那些没有失效的链路以及保护环中未失效路径来建立路由。因此,可以通过和通路P上的一些链路单独建立保护环的方式来降低整个路由的失效概率,从而满足连接请求的最大失效概率要求,因为在单链路失效的情况下,保护环中的任意链路(i,,)的失效概—率为零。以图l为例,路径2.4.52组成了一个保护环,如果链路2.5失效,可以通过2.4.5来路由。同样,如果2.4失效或者4.5失效,可以通过2.5.4或者4.2.5来路由。这样,在计算这条路由实际失效概率的时候,只需要计算通路P上那些没有单独组成保护环的链路的失效概率即可。令表示通路P上所有未单独形成保护环的链路组成的集合,这条通路P的实际失效概率为:=>。P,(f,,)(3)“』__J√∈(f)印实际失效概率即通路P上所有未单独形成保护环的链路的失效概率之和。2DRPR算法描述由于可以通过建立保护环的方式来降低整个路由的失效概率,那么可以首先对网络进行处理,在吴润泽,等新一代电力ICT网络中基于DiR保护环的生存性路由算法-27-网络中尽可能的建立保护环。经过处理,网络中的链路将分为保护环中的链路和非保护环中的链路,然后在这个处理过的网络中来寻找路由,如果找到保护环中的链路,那么保护环也作为路由的一部分,并且该保护环的链路的失效概率为零。通过构造一个在保护环中的链路和非保护环中的链路构成的模型,就能够在该模型中为连接请求计算一条满足最大失效概率且代价最小的路由。2.1模型的构造算法首先构造一个分层模型,其中的一层称为保护环层;而另一层称为物理层。保护环层包含了网络中所有能够建立的保护环,而物理层是原始网络拓扑。分层模型的建立如下方法:1)对网络中的每一个点分成两个子节点Vi2'RL和Vi,PL,Vi表示保护环层的节点,表示,pRLVi,PL物理层的节点。2)构造物理层。物理层为原始的网络拓扑,每条链路的代价和失效概率与原网络中链路的代价和失效概率相同。3)构造保护环层。由于算法需要寻找最小代价路由,所以对原始拓扑图中的链路代价进行排序,从中选出链路代价最小的链路,然后为这条链路建立保护环。保护环的建立采用寻找最短路径对的方法,即为这条代价最小的链路寻找一条路径完全分离的通路,这条通路与该链路就形成了一个保护环。如果存在该通路,则建立保护环,如果不存在,则无法建立保护环。建立保护环时,或许会存在多条路径完全分离的通路与这条链路形成多个保护环,此时应当判断哪条通路形成的保护环的总代价最小,选择总代价最小的那个保护环作为该链路的保护环。如果成功建立保护环,那么这个环中每条链路的代价是这个环的总代价之和,每条链路的失效概率为零,然后在网络中去掉该链路所在保护环中的所有链路,从而重新形成新的网络拓扑;如果不能建立保护环,那么在网络中去掉该链路,从而重新形成新的网络拓扑。下一次寻找保护环时在新形成的网络拓扑中查找,这样能够保证不会对链路进行重复查找。以图1为例说明如何构造分层模型中的保护环层。先对链路进行排序,按链路代价从4,N大的顺序排列,排列结果如表I所示。从表1中可以得出,链路2.5代价最小,因此为链路2.5建立保护环。建立保护环时,首先使用Floyd算法寻找节点2到节点5的除了链路2.5的最短路径,使用Floyd算法能够保证查找出的路径代价是最小的。通过运行Floyd算法,通路2.4.5的代—价为7,是节点2到节点5的除了链路25的代价—最小路径。这样形成一个保护环2-45-2,保护环中的链路代价为该环的所有链路之和,链路的失效概率为零。然后在网络中去掉该环中的链路,在余下的网络拓扑中用同样方法查找保护环,该网络拓扑的保护环层如图2所示。表1链路排列结果Tab.1Resultofthelinkarray图2图1所示网络拓扑的保护环层Fig.2ProtectionringlayerofthenetworktopologyinFig.14)连接物理层和保护环层的节点。在物理层和保护环层每一个节点对(Vi,PRL,Vi,PL)之间加一条无向边,这些边为连接边,该边的失效概率为0,链路代价为0。建立的分层模型如图3所示。图3分层模型示例Fig.3Exampleofhierarchicalmodel2.2路由的计算在分层模型中计算出一条从源节点到目的节点的路由R,使得这条路由的失效概率不大于连接请.28.电力系统保护与控制求所允许的最大失效概率并且使得这条路由的代价尽可能小。为了寻找路由R,使用Do'kstra算法在分层模型中计算一条从源节点v到目的节点v的链路代价最小的路由。2.3路由的选取在计算从源节点到目的节点的代价最小的路由过程中,判断这条路由的失效概率是否满足要求,不满足则在分层模型中去掉这条路由的所有链路从而形成新的模型,然后在这个新的分层模型中重新计算路由,直到找到一条代价最小且失效概率符合要求的路由为止,如果最终都没有符合要求的路由,则判定从源节点到目的节点不可达。2.4路由的匹配由于路由R是在分层模型中选取的满足最大失效概率的最小代价的路由,如果在路由中存在保护层的边,那么就需要对路由进行匹配,将保护层的边用整个保护环来代替,并且去掉物理层与保护环层之间相连的边。这样得到的路由尺即为满足连接请求所要求的最终路由。3实验分析及性能评价为了验证DRPR算法的性能,采用如图4所示的美国网络作为仿真网络模型。假定网络中每条链路的失效概率与该链路的长度成正比。考虑两种状态的仿真,一种情况是等链路代价,另一种情况是链路的代价与链路的长度有关。连接请求逐个到达且服从泊松分布,假定网路中每条链路的带宽能够完全满足连接请求的带宽需求。图4仿真网络结构图Fig.4Simulationnetworkstructure假定三类连接请求,三类连接请求所允许的最大失效概率分别为Pl、P2、P3,且Pl2<P3,实验中三类连接请求的比例相同。.路由成功率定义为成功地建立路由的次数与路由建立请求的总次数之比。该实验仿真了两种情况下的路由成功率,一种为链路代价相同且为1;另一情况是链路代价不同且与链路长度相等。令pl=0,p2=0.06,P3=0-0.2。实验仿真了两种情况下的平均代价,一次实验在网络中随机生成10000个连接,记录下每次实验的平均代价。l×链路代价相同fI。链路代价不同l()r()),图5两种链路代价情况下的路由成功率曲线Fig.5RoutingSuccessratecurveintwocasesoflinkcost从图5给出的实验结果可见,当失效概率P3变大时,由于可靠性要求的降低,路由连接更容易满足可靠性的要求,因此算法的路由成功率更高。图6中的星形符号实线表示使用DRPR算法在链路代价相同的情况下l0次实验平均代价的分布,图7中的星形符号实线表示使用DRPR算法在链路代价等于链路长度的情况下10次实验平均代价的分布。△lSPPA算法I—i+一DRPR算法l———k~————{——Z二j}一实验次数图6相同链路代价条件下的实验结果曲线Fig.6Experimentalresultscurveinthesamelinkcostcondition在文献[101中作者提出了SPPA算法,图6和图7中三角形符号虚线分布是使用SPPA算法在相同的情况下得到的平均代价。从图6中可以看出实验使用SPPA算法和使用DRPR算法得到的平均代价相差不大,而在图7中,使用DRPR算法得到的平均代价比使用SPPA算法得到的平均代价小很多。●OOOOOO0OO0褂雷裎母密655443¥吴润泽,等新一代电力ICT网络中基于DiR保护环的生存性路由算法一29一’瞄lz—实验次数图7不同链路代价条件下的实验结果曲线Fig.7Experimentalresultscurveinthedifferentlinkcostsconditions在所提DRPR算法中,建立分层模型时首先对链路进行排序,然后寻找最小代价的链路生成保护环层,以此可以最大化地减小链路代价。在图6中,由于链路代价都设为1,无法做到最小代价链路的优先选择,因此两种方法的平均代价相差不大。图7是在假设链路代价等于链路长度的情况下进行仿真所得的结果,由于每条链路的长度各不相同,这样就能够优先的选择代价较小的链路,仿真结果显示本文所提DRPR算法得出的平均代价比使用SPPA算法得出的平均代价低55%,优化了路由选择的结果。4结论通过对区分可靠性的分析,提出了一种基于分层模型的满足不同可靠性需求的保护路由算法,通过与SPPA算法比较,所提DRPR算法在满足最大失效概率的情况下可减少连接请求的代价。通过实验和数据分析,使用DRPR算法得到的平均代价比使用SPPA算法的得到的平均代价小很多,从而能够极大优化网络资源的利用效率,使电力通信网络能够安全、可靠地运行,为智能电网的发展提供强大的通信保障。参考文献[1]李兴源,魏巍,王渝红,等.坚强智能电网发展技术的研究[J】.电力系统保护与控制,2009,37(17):1-7.LIXing-yuan,、IWlei,WANGYu-hong,eta1.Smdyonthedevelopmentandtechnologyofstrongsmartgrid[J].PowerSystemProtectionandControl,2009,37(】7):】.7.[2]施婕,艾芊.智能电网实现的若干关键技术问题研究[J].电力系统保护与控制,2009,37(19):1-4.SHIJie,AIQian.Researchonseveralkeytechnicalproblemsinrealizationofsmartgrid[J].PowerSystemProtectionandControl,2009,37(19):1-4.[3]焦振有,焦艳莉,李严平,等.配电自动化中的光纤载波混合通信方案[J].继电器,2002,30(7):44-46.JIAOZhen.you,JIAOYan.1i,LIYah-ping,eta1.Amixedcommunicationschemeofdistributionautomationbasedonopticalfiberanddistributionlinecarrier[J].Relay,2002,30(7):44.46.[4]罗洪斌.抗毁WDM光网络中的保护算法研究[D】.成都:电子科技大学,2007.LUOHong-bin.Researchonprotectedalgorithmsinsurvivablemeshnetworks[D].Chengdu:UniversityofElectronicScienceandTechnologyofChina,2007.[5]FumagalliA,TaccaM.Optimaldesignofdifferentiated∥reliability(DiR)opticalringnetworks[C].WorkshoponQoSinMultiserviceIPNetworks(QoS-IP)2001,Rome,Italy,Jan.2001.[6]FumagalliA,TaccaM.Differentiatedreliability(DiR)inWDMringswithoutwavelengthconverters[J].’—ICC01,2001:28872891.[7]FumagalliA,TaccaM,UnghvaryF,eta1.Sharedpath’protectedwithdifferentiatedreliability[J】.ICC02,2002,4:2l57.2161.[8]TaccaM,FumagalliA,ParadisiA,eta1.Differentiatedreliabilityinopticalnetworks:theoreticalandexperimentalresults[J].IEEE/LEOSJournaloflightwaveTechnology,2003,21(11):2576-2586.[9]WuK,Valc ̄enghiL,FumagalliA。Restorationschemes’withdifferentiatedreliability【J】.ICC03,2003,3:1968.1972.[10]LUOHong-bin,LILe-min,YUHong-fang.RoutingconnectionswithdifferentiatedreliabilityrequirementsinWDMmeshnetworks[J].IEEE/ACMTransactionsonNetworking,2009:253-266.收稿El期:2010-09-07;修回El期:2010-10-I9作者简介:吴润泽(i975-),女,博士,副教授,硕士生导师,主要研究方向为宽带通信网络技术及其在电力系统中的应用;—Email:wurz@ncepu.edu.cn祁宏鹏(1986-),男,硕士研究生,主要研究方向为电力系统通信中网络的可靠性保护机制;E.mail:qihongpenglbin@163.corn唐良瑞(1966-),男,博士,教授,主要研究方向为电力系统通信、信息安全、无线通信等。
乘风破浪
该用户很懒,什么也没介绍
文档单价:6.00 会员免费
开通会员可免费下载任意文档