新的基于MPH的时延约束Steiner树算法

第30卷第11期 2010年11月 计算机应用 JournalofComputerApplications V01．30No．11 Nov．20lO 文章编号：1001-9081(20LO)11—3056—03 新的基于MPH的时延约束Steiner树算法 杨春德1，康欢2，丁亚南3 (i．重庆邮电大学数理学院，重庆400065；2．重庆邮电大学计算机科学与技术学院，重庆400065) (khuan222@126．conl) 摘要：为了在时延约束条件下进一步优化多播树代价并降低算法的复杂度，研究了时延受限的Steiner树问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。 在DCMPH算法的基础上，通过改进节点的搜索路径，提出了一种新的基于MPH的时延约束Steiner树算法。该算法 中每个目的节点通过最小代价路径加入当前多播树；若时延不满足要求，则通过合并最小时延树进而产生一个满足 时廷约束的最小代价多播树。仿真实验表明，新算法在性能、空问复杂度方面均优于DCMPH算法。 关键词：多播树；时延约束；Steiner树 中图分类号：TP393；TP301．6文献标志码：A NewMPH-baseddelay．constrainedSteinertreealgorithm YANGChun—del。KANGHuan2。DINGYa—Dan。 (1．CollegeofMathematwsandPhysics，ChongqingUniversityofPostsandTelecommunication，Chongqing400065，China； 2．CollegeofComptaerSconceandTechnology,ChongqingUniversityofPostsandTelecommunication，Chongqing400065，China) Abstract：Inordertooptimizecostanddecreasecomplexitywithadelayupperbound．thedelay—constrainedSteinertree problemwasstudied．BasedontheDelay—ConstrainedMinimumPathHeuristic(DCMPH)algorithmandthroughimprovement Oilthesearchpath．anewMPH-baseddelay·constrainedSteinertreealgorithmwaspresentedinthispaper．Withthenew algorithm，adestinationnodecouldjointheexistingmulticasttreebyselectingthepathwhosecostwastheleast；ifthepath’S delaydestroyedthedelayupperbound，theleast·delaypathcomputedbyshortestpathtreealgorithmWasusedtotakethe placeoftheleast—costpathtojointhecurrentmuhicasttree．Bytheway，alow-costmuhicastspanningtreecouldbe constructedandthedelayupperboundwouldnotbedestroyed．r11lesimulationresultsshowthatthenewalgorithmissuperior toDCMPHalgorithmintheperformanceofspanningtreeandspacecomplexity． Keywords：multicasttree；delay·constrained；Steinertree 0 引言 多播是一种允许源节点同时向网络中的多个目的节点发 送相同数据信息的通信方式，多播路由问题实质上就是构建 覆盖源端与接收端的路由树的问题。随着通信网络的发展， 诸如视频点播、电视会议等实时多媒体应用日益增多，这砦应 用服务不仅有严格的端到端时延限制，还需要使用大量的网 络资源。为了有效地支持这些新应用，需要研究既能满足给 定端到端时延又能优化多播路由树代价的多播路由算法。 目前，已经有许多学者提出r构建最小代价树的问题 (即Steiner树问题)，但由于该问题是一个NP—Hard问题⋯， 因此有不少学者提出启发式算法来计算准Steiner树。最为 典型的就是MPH(MinimumPathHeuristic)口。算法，该算法每 一次选择离已有生成树费用较低且尚未添加到生成树上的目 的节点，通过最小代价路径加入到生成树上。文献[3]提出 了KPP算法，该算法首先利用类似Floyd算法的方式求出任 意两个节点之间满足时延约束的最小代价路径，并根据这些 信息构造多播树。文献[4]提出了BSMA(BoundedShortest MuhicastAlgorithm)，该算法首先利用SPT(ShortestPathTree) 算法构造最小时延树，然后利用超边迭代来降低生成树的代 价。KPP和BSMA都能够产生较高性能的多播树，但是计算 量过大，很难应用到实践中去。文献[5]提出了CDKS算法， 该算法通过较为合理地组合最小费用路径和最小时延路径来 构建多播树，计算萤远远低于前两种算法，但是生成树的代价 过大，为此文献[6]提出DCMPH(Delay—ConstrainedMPH)算 法，该算法根据MPH算法的基本思想来构建多播树，计算复 杂度与同类算法相比比较低，但是该算法并不能合理地选择 下一个将要加入的目的节点。为此本文结合了MPH算法在 树性能上的优点以及CDKS算法时间上的优化，对DCMPH 算法进行了改进，提出了一种新的多播路由算法—— DCMPH．．1。 1 多播网络模型和相关定义 给定一个带权无向图G=(y，E)，V是图G的节点集，E 是图c的边集。n=Iyl为图G的节点数，IEI为图G的边 数或链路数。每条边e(e∈E)上定义两个函数：代价函数 cost(e)：E—R+；时延函数delay(e)：E—R+其中R+表示正 实数集。在多播通信网络中，有一个源节点s∈V和一组R的 节点集合肘∈V，目的节点又称端节点，则时延约束Steiner树 r就是一棵以S节点为根，能到达所有目的节点的树，并且在 满足时延约束的条件下，使树的网络费用最小，即V”EM， 在Edelay(e)<△条件下，使得∑cost(e)最小。其中：△ eEp'77．“) 研 为正实数，表示时延约束边界；p(s，口)表示多播树s到。经过 的路径。 定义l Path(U，∥)表示节点U∈V到节点口EV的简单 收稿日期：2010—04—30；修回日期：2010—07—13。基金项目：2009年重庆市教委科学技术研究项目(KJ090509)。 作者简介：杨春德(1964一)，男，重庆人，教授，主要研究方向：网络优化、算法分析；康欢(1986一)，女，河南驻马店人，硕士研究生，主 要研究方向：网络多播路由算法；丁亚南(1986一)，男，河南周口人。硕士研究生，主要研究方向：网络多播路由算法。 万方数据 第11期 杨春德等：新的基于MPH的时延约束Steiner树算法 3057 路径，路径上的时延为路径上各个链路的时延和，记为 Delay(Path(II,，口))，即： Delay(Path(M，F))=∑delay(e) 路径上的代价为路径上各个链路的代价和，记为 Cost(Path(u，口))，即： Cost(Path(M，F))=∑cost(e) c￡正而“．“ 定义2 Steiner节点。多播树中除了源节点和目的节点 以外的节点。 定义3 父边。新产生的，圭成树r中，s为源节点，口∈M， 则在树r上有且仅有一条路径：5，口．，口：，⋯，。；，”，那么边(q， 。)就是”的父边。 2 DCMPH一1算法 2．1 DCMPH算法的分析与改进 DCIVIPH算法的基本思想主要是根据．～IPH算法牛成低代 价Steiner树的特性，结合DijkstraSP'I"算法推广到时延受约束 情况下最小代价的问题。算法首先求得源节点s到所有端节 点的最小时延路径以及每个端节点“到除端节点以外的所有 节点的最／1,4匕价路径；然后把源节点s作为初始多播树r；最 后每次选择距离树7’代价最小且尚未加入到牛成树T上的端 节点m和相虚的路径P，如果／2,通过P到5不能够满足时延限 制．则选择s到rn的最小时延路径作为P，将／2,和P加入到生成 树7'中，重复以j：步骤，直到所有的端节点都加入到丁中。从 以上过程中可以看到算法的两个缺点： 1)每次选择的路径并不一定是满足时延限制的最小代 价路径。 2)最小代价路径巾的不满足时延限制的路径肯定不能 作为候选路径，因此该算法增加了额外的卒问代价。 根据这些问题，本文提出了DCIVIPH一1算法，新算法的简 要描述如下： 引入两个集合D和y，D表示源节点s到各个端节点m的 最小时延路径集合．而V表示每一个端节点m到其余各个节 点满足时延限制的最小代价路径集合。 1)用Dijkstra算法求源节点s到任意端节点m的最小时 延路径，并初始化集合D，如果有一个端节点不满足时延限 制，则市即退出，说明不能够找到满足时延限制的多播树。 2)利用改进的Dijk．stra算法一j求端节点到余下各个节点 满足时延限制的最小代价路径，并初始化集合y。 3)以源节点s为初始多播树r。 4)从集合y中选择满足时延限制、距离树r代价最小且 尚未加入到树r中的端节点／／,以及相关路径P，如果不能找到 这样的“和P，则从集合D中选择代价最小的尚未加人到树r 中的端节点／／,以及相关路径P，将u和P添加到牛成树r中。如 果形成环路，只需要简单地删除形成环路的节点的父边。 5)重复4)直到所有的端节点都加入到牛成树r中。 DCMPH一1首先从满足时延限制的最小路径集合V中选 择最小代价路径，只有在V中找小到满足时延限制的路径时， 才从最小时延路径集合D中选择路径，从而克服了DCMPH 算法在选掸下一个被加入端节点的弱点，另外在算法的第2) 步，并没有求到所有节点的最小代价路径，而仅仅求出满足时 延限制的最小代价路径，所以该算法与DCIVIPH算法相比，具 有相对较低的空间复杂度。另外文献[6]证明r在消除环路 的过程中，并不会破坏生成树r的时延上限。 2．2 DCMPH一1算法的时间空间复杂度分析 DCIVIPH～1算法先利用最小生成树算法求出源节点s到 各个目标节点的最小时延路径，此时的时间复杂度为 0(n2)，其中／／,为网络中节点个数。然后用改进的最小生成树 算法求t!r／个端节点到网络中所有节点满足时延的最小代价路 径，此时的时间复杂度为0(trt／'l,2)。其中，m为端节点个数，n 为网路巾的节点个数。最后求离牛成树代价最小的路径，此时 的时问复杂度为0(t'／'t2rt)。因此该算法的时间复杂度为 0((t?Z+1)t'／2+m2r／．)，而BSlVlA的时间复杂度为0(kn3)， KPP算法的时间复杂度为D(△n3)，其中△为时延}：限的整数 值。所以DCIVIPH-l算法的时间复杂度远低于BSMA和KPP 算法，但是略高于CDKS算法．CDKS算法的时间复杂度为 0(n,2)。DCIVIPH算法∞：的时间复杂度为0((m+1)11,2+ ／71．2凡)，所以DCMPH一1算法的时I'sJ复杂度与DCMPH算法的 时间复杂度相当。 通过对DCMPH和DCMPH_1算法的分析可以发现，算法 的空间代价丰要集中在第1)一2)步，其中DCIVIPH算法要存 放m+mn条路径，而DCMPH—i算法仅仅存放J7l+脚条路 径，其中6为任意端节点m到余下节点满足时延限制最多的 路径个数，所以6≤／7,。因此，DCMPH-l算法的空间复杂度在 最坏的情况下才和DCMPH算法相同。 3 仿真实验及其分析 为了验证DCMPHJ算法的正确性和有效性，本文采用 了文献[7—8]提出的随机网络模型进行实验，在该网络模型 中：n个节点随机分布在直角坐标系中(假设节点的坐标均为 整数)，每条边上的代价取(0，5]中的随机数值，时延与文献 中保持一致。节点之间的连通性由式(1)确定： P(Ⅱ，扩)=口exp(一d(比，口)／(￡口)) (1) 其中：d(“，”)是u和"之间的距离；工是任意两节点问的最大 距离；Or和口是调节网络图特征的参数，为了让随机网络更接 近现实中的网络，本文选用rrl,=0．3，口=0．3。仿真实验中 用到的数据足在相同的条件F，不同的源节点和接收节点进 行50次实验求平均值的结果。 图1显示了多播树代价与网络节点数之间的关系，选择 了20个接收节点不变，网络巾的节点由60增加到120，每一 次网络中的节点个数增加10，时延限制保持0．03s。从图中 可以看到DCMPH_l算法产生的多播树代价小于DCMPH算 法。 当 ￡ 窭 颦 蚺 网络节点数 图1树代价与刚络爷点数之间的关系 图2显示了多播树代价与组成员个数之间的关系，时延 限制保持在0．03s不变，网络中的节点个数保持120不变，但 是多播组中的节点个数由20增加到80，从该图中可以看到， DCMPH一1算法优于DCMPH算法，但是随着接收节点的个数 增加，这种优势逐渐消失。 图3显示了多播树代价与时延约束之间的关系，实验是 在网络环境没有任何变化的情况下，时延限制由4增加到 24，MPH算法是在没有时延限制条件下产生的多播树，所以 它的代价最小．因此本次实验以MPH算法为基准。通过图3 加∞∞∞册∞m o 万方数据 3058 计算机应用 第30卷 可以看到DCMPH-l算法优于DCMPH算法，并且随着时延约 束的增大，DCMPH一1比DCMPH更快地接近MPH算法。 组成员个数 图2树代价与组成员个数之间的关系 时延约束 图3树代价与时延约束之间的关系 图4显示了算法的空间复杂度与网络节点数之间的关 系，本次实验通过统计需要存放最小代价路径的个数来衡量 算法的空问复杂度。 网络节点数 通过图4可以看出算法DCMPH．1的空间复杂度低于 DCMPH算法，并且随着网络节点数的增加，这种趋势更加明 显。 4 结语 由于MPH算法是一个性能优越的Steiner树启发式算法， 本文对时延受限的组播路由环境下的DCMPH算法进行了分 析和改进，提出了DCMPH一1算法。该算法获得了相对优于 DCMPH算法的效果，但是计算复杂度与DCMPH算法相当，如 何进一步降低算法的计算复杂度，将是下一步研究的内容。 参考文献： 【1】LOTABEVDT，UZDEMIRAP．ConversionoftheSteinerproblem ontheEuclideanplanetotheSteinerproblemongraph【J】．Auto- mationandRemoteControl，2005：66(10)：1603—1613． 【2】 WINTERP．Steinerprobleminnetworks：survey【J】．Networks， 1987，17(2)：129—167． 【31 KOMPELLAVP，PASQUALEJC，POLYZOSGC．Muhicastrou— tingformultimediacommunication【J】．IEEE／ACMTransactionsOn Networking，1993，1(3)：286—292． 【4】PABSAM，ZHU0Q，GARCIA—LUNA-ACEVESIJ．Aniteratlve algorithmfordelay·constrainedminimumc06tmulticasting[J】． IEEE／ACMTmnsactiomonNetworking，1998，6(4)：461-474． 【5】 SUNO，LANGENDORFERH．Efficientmulticastroutingfordelay— sensitiveapplications【EB／OL]．【2009一04一lO]．http：／／citese— erx．ist．psu．edu／viewdoe／download；jsessionid=AC50DDEAFE58 41993DFA381CFCAOC6247doi=10．1．1．57．4260&rep=repl& type=哦 【6】周灵，孙亚民．基于MPH的时延约束Steiner树算法【J】．计算机 研究与发展，2008，45(5)：810—816． 【7】 WAXMANBM．Routingofmultipointconnections【J】．IEEEJour- halonSelectedAreasinCommunications，1988，6(9)：1617一 1622． 图4空间复杂度与网络节点数之间的关系 [81余燕平．多播路由算法的研究【D】．杭州：浙江大学，2002． (上接第3055页) 4 结语 宙 譬 厘 拍 忙 ．墨 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 数目 图5算法所占内存空间的比较 现代网络技术的发展使得越来越多的网络设备需要支持 快速准确的包分类，随着光纤通信技术的普及。链路带宽和传 输速率已不再成为问题，路由转发设备正在成为网络瓶颈。 因此研究高效的包分类算法对于未来互联网的发展具有极其 重要的意义。 近年来，国内外很多专家学者针对互联网络的包分类问 题进行了大量研究．提出了一系列有效的算法以应付不同网 络设备和应用环境的需求。EGT．PC算法是一种高效的包分 类算法，本文针对目前高效的包分类算法EGT-PC的优缺点， 提出基于压缩节点的新算法——En．SC，提高了包分类算法 在时空上的性能。 参考文献： 【l】 QIYAXUAN．XUuANGHONG，YANGBAOHUA，et以Packet classificationalgorithms：fromtheorytopractice【EB／OL】．【2009 一04—191．http：／／ieeexplore．ieee．org／xpl／freeabs—a11．jsp?ar- number=5061972． 【21 NECHAYD，POINTURIERY，COATESM．ControHingfalsea． 1arm／discoverymtesinonlineIntemettm岱cflowclassification 【EB／OL】．【2009—04一15】．http：／／ieeexplore．ieee．org／xpl／ freeabs—a11．jsp?arnumber=5061976． 【3】 BABOESCUF。SINGHS，VARGHESEG．Packetclassificationfor coretouters：istheresnalternativetoCAMs?【EB／OL]．【2009— 12-231．http：／／www．ieee—infocom．org／2003／papers／V2_02．阻 【4】 WANGP—C，LEEC—L，CHANC-T．Performanceimprovementof two-dimensionalpacketclassificationbyfilterrephrasing【J】． IEEE／ACMTransactionsonNetworking，2007，15(4)：906—917． 【5】TAYLORDE，TURNERJS．ClassBonch：Apacketclassification benchmark【C]／／IEEE／ACMTransactions011Networking．W8sh— in,on，DC：IEEE，2007：499—511． 【6】 BREMLER·BARRA，HAYD，HENDLERD．Layeredinterval codesfortcam—basedclassification【EB／OL】．【2009—04—22】． hap：Hie*explore．ie优．org／xpl／freeabs—a11．jsp?arnumber=5062 045． 万方数据 新的基于MPH的时延约束Steiner树算法 作者： 杨春德， 康欢， 丁亚南， YANG Chun-de， KANG Huan， DING Ya-nan 作者单位： 杨春德,YANG Chun-de(重庆邮电大学,数理学院,重庆400065)， 康欢,丁亚南,KANG Huan,DING Ya-nan(重庆邮电大学,计算机科学与技术学院,重庆400065) 刊名： 计算机应用 英文刊名： JOURNAL OF COMPUTER APPLICATIONS 年，卷(期)： 2010,30(11) 参考文献(8条) 1.余燕平 多播路由算法的研究 2002 2.WAXMAN B M Routing of multipoint connections[外文期刊] 1988(09) 3.周灵;孙亚民 基于MPH的时延约束Steiner树算法[期刊论文]-计算机研究与发展 2008(05) 4.SUN Q;LANGENDORFER H Efficient multicast routing for delaysensitive applications 2009 5.PARSA M;ZHUO Q;GARCIA-LUNA-ACEVES I J An iterative algorithm for delay-constrained minimum cost multicasting[外文期刊] 1998(04) 6.KOMPELLA V P;PASQUALE J C;POLYZOS G C Muhicast routing for multimedia communication[外文期刊] 1993(03) 7.WINTER P Steiner problem in networks:survey[外文期刊] 1987(02) 8.LOTAREV D T;UZDEMIR A P Conversion of the Steiner problem on the Euclidean plane to the Steiner problem on graph[外文期刊] 2005(10) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyy201011059.aspx