Steiner树的数学模型及问题定义——数学建模论文专区

1、Steiner树的数学模型及问题定义数学建模论文专区    基于共享边的时延约束组播路由算法 摘要:为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题。分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH。该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价。仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能

2、较好。 关键词:组播通信  Steiner树 最短路径启发式算法 服务质量 路由优化 Abstract:In order to optimize cost and decrease time complexity, the delay-constrained Steiner tree problem wasdiscussed. The implementation ofMinimum Path Heuristic (MPH) algorithm was analyzed firstly, then a delay-constrainedmulticast rout

3、ing algorithm based on shared edges named ESAMPH was presented. ESAMPH preferentially selected the nodesthroughwhichmore shortest path was contained when constructing a multicast routing tree, therefore, the next node to themulticast treemay be also the shortestpath through these nodes to reduce the

4、 cost ofmulticast tree. Simulation results showthatESAMPH balances cost, delay and computing time and has better overall performance.Key words:multicast communication; Steiner tree; Minimum Path Heuristic (MPH) algorithm; Quality of Service(QoS); route optimization 0引言随着网络技术的飞速发展,特别是多媒体网络应用业务的急

5、剧扩展,客观上要求基础通信网络提供组播服务。组播通信技术以有效降低网络带宽需求、减轻网络负载为主要特点,在当今网络业务中有着广泛的应用。多媒体通信业务数据量大,需要消耗大量的网络带宽,并且在应用上有较严格的服务质量(Quality ofService,QoS)约束条件。因此,组播是最佳的解决方式。组播是一种实现从源节点同时向多个目标节点发送信息的通信形式,同时,组播应用还需要满足端到端时延限制、优化网络资源利用率等约束条件。从路由的角度来说,这些约束条件可以转化为构建一棵组播树,即在满足QoS约束条件下,不断选取使目标函数达到最优的链路并入到正在构建的组播树中,直至所有参与组播的目的节点都进入

6、组播树。受时延约束的组播路由问题可以形式化为约束的Steiner树问题,它是一个NP完全问题1。Steiner树的典型算法有:KMB算法2,时间复杂度为O(mn2);最短路径启发式(Minimum Path Heuristic, MPH)算法3-4,时间复杂度为O(mn2);平均距离启发式(Average DistanceHeuristic, ADH)算法5,时间复杂度为O(n3)等。KMB算法、MPH算法和ADH算法都属于可在多项式时间内解决问题的有效算法,由于mn,因此KMB和MPH算法在时间复杂度上ADH算法好,而MPH算法的代价优于KMB算法5,因此,MPH算法是一种较优的启发式算法6

7、。本文分析了MPH算法的执行过程及其局限性,将其扩展为时延受限的组播路由算法。仿真实验表明,从生成树代价、时延约束和算法复杂性等方面考虑,本文提出的改进算法是一个较好的求解时延约束最小代价树的启发式算法。 1Steiner树的数学模型及问题定义一般地,网络可表示为赋权无向图G = (V,E),其中V是网络中节点的集合,n =|V |表示节点数,E为网络中通信链路即边的集合。对于E中的每一条边e = (x,y)(eE,x,yV),定义了代价函数C(e):ER+和时延函数D(e):ER+。由图G = (V,E)生成的树T中,若路径P(vi,vj) =p(vi,vj),则路径P的时延为各链

8、路时延的和,即D(p(u,v) =ep(u,v)D(e)。定义1Steiner树。给定图G = (V,E)和源节点s,目的节点集DV-s,m =|D |表示目的节点个数。若从图G中找出覆盖D中所有节点的最小生成树T,即使得:m invD, eTC(e)(1)成立,该最小生成树T称为Steiner树。定义2时延约束Steiner树。定义1的Steiner树T中,给定时延阈值(正实数),若T满足: 2基于共享边的时延约束组播路由算法MPH算法的基本思想是每次从目的节点D中尚未添加到生成树的节点中选取到树T具有最小代价路径节点v,将其及其最小代价路径加入树T中。基本算法如下:1) viD, i =1

9、,初始组播树Tivi,Vivi;2)对于节点vi(viD-vi-1, i=2,m),选择到Ti-1的最小代价路径p = (vi,Vi-1),将其加入到树Ti中,即TiTi-1p;3)重复2)直到所有的目的节点都加入到Ti中。MPH算法代价较低,是公认的求解Steiner树问题的优秀启发式算法。但由于每次添加目的节点时都通过最短路径连接到树上,因此有可能把那些非最短路径,或与最短路径的代价相同而搜索次序在后的路径漏掉,而这些路径有可能实现更多的链路共享而降低整棵树的代价。通过研究网络中端到端最短路径发现:网络中有些节点有较多的最短路径经过,而另一些则有较少的最短路径通过。若在MPH算法中,能够在一定条件下优先选择包含有较多的最短路径经过的节点集