时延及时延抖动限制的最小代价多播路由策略

满足多种服务质量请求的多播路由问题是目前多播通信中的重要课题之一。该文作者在研究受端到端时延及时延抖动限制的多播路由问题的过程中，发现当前许多算法所普遍使用的两个最佳链路选择函数并不能完全体现路由的动态过程，同时它们还存在一定的缺陷。而正是由于这种缺陷，在某些情况下通过这两个最佳链路选择函数所得到的结果树可能不包含所有的目标节点，文中称这种情况为“多播不可达”。针对上述问题，该文提出了“多播可达”的假设条件以及一个新的最佳链路选择函数，并在此基础上提出了一个满足时延及时延抖动双重限制的最小代价多播树的建立算法（DDVBMRA）以及一种动态重组多播组目标节点的方法。仿真结果表明本算法具有很好的延抖动及代价性能。     

一种高可靠性的组播树恢复方法

应用层组播树中某个非叶子节点失效后,需要重新构建组播树保证失效节点的子孙节点能够正确接收数据。针对这一问题,考虑满足高可靠性环境中保证恢复完整性的情况,提出一种基于备用父节点的组播树预先式恢复方法,即为每个非根节点找到一个备用父节点,使得当某一非叶节点失效时可以迅速的恢复组播树。首先建立模型并对其求解构造恢复方法,然后论证此方法保证组播树恢复的完整性,最后通过仿真实验验证了此方法的有效性以及其在恢复延迟和管理代价上的改进。     

QoS-driven multicast tree generation using Tabu search

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.     

异构无线传感器网络中一种可扩展的代码分发技术

代码分发一直是无线传感器网络研究的热点问题.目前的研究工作主要集中在同构场景下的代码分发,广播是这些研究工作中最常用的手段.而对于异构场景下的代码分发问题,研究工作则相对较少,传统的基于广播的方法很难直接适用.文中针对异构网络下的代码分发问题,把该问题归约为最小非叶节点MNN(minimum nonleaf nodes)Steiner树问题,并设计了一种基于多播的代码分发协议HSR(heterogeneous sensor networks scalable reprogramming protocol).该协议利用组件化的思想,为不同类型节点(或代码模块)建立了多棵最优代码分发多播树.并证明了在解决MNN问题时,HSR达到了理论最优近似率ln|R|(R为目标节点数),有效的降低了异构网络下代码分发过程中的通信开销和能耗.在此基础上,文中还设计了两种压缩编码机制:特殊路由日志机制SRL(special routinglog)和跳步受限的局部广播机制HLB(hops-restricted local broadcast),使得多播树的信息可以被无损压缩,增强了HSR协议的可扩展性.在实时性方面,提出了基于多播树的3阶段流水线调度方法,有效缓解了隐藏终端和干扰问题.仿真结果证明了协议的正确性和有效性.     

A scalable code dissemination protocol in heterogeneous wireless sensor networks

Code dissemination is currently a major research issue in wireless sensor networks (WSNs).Many studies focus on code dissemination in homogeneous WSNs,mainly using a broadcast approach to solve this problem;few studies on code dissemination in heterogeneous WSNs.Furthermore,broadcasting cannot readily be used to solve the heterogenous WSN code dissemination problem directly,which is where we have focused our attention.We transformed this problem into a minimum non-leaf nodes (MNN) Steiner tree problem.We designed a scalable multicast protocol,named Heterogeneous Sensor Networks Scalable Reprogramming Protocol (HSR) to solve the MNN problem.HSR can build different multicast trees according to different nodes or code modules to disseminate different codes to them.HSR is able to approximate the MNN tree problem to a ratio of ln|R| (R is the set of all destinations) best known lowest bound.Therefore,the communication cost is significantly decreased and the total energy required by WSNs is reduced.We further designed two scalable schemes,special routing log and hops-restricted local broadcast,which compress the multicast tree information and deliver the multicast messages without loss.We also designed a 3-stage pipeline to speed up the transmission of packets,which alleviated interference and hidden terminal issues.We evaluated our design through comprehensive simulations and prototype implementations on Mica2 motes.Experimental results demonstrate that HSR outperforms previous protocols including the most recent studies on Sprinkler and uCast.     

基于遗传算法的QoS组播路由选择方法

考虑了组播通信服务质量需求与网络资源约束,将满足不同约束的QoS组播路由选择过程转化为一个多目标优化问题,使用一种基于QoS的最小网络费用组播路由树生成算法来寻找最小Steiner树。该方法可以在满足多约束的情况下,寻找费用最小的组播路由树,仿真结果表明该算法有较好的性能。     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

覆盖组播的最小覆盖代价路由算法

与IP组播相比,覆盖组播通常会消耗更多的底层网络资源。因此,在覆盖网中构造组播转发树时,考虑合理地利用底层网络资源具有一定的实际意义。给出覆盖代价的概念,把覆盖组播路由问题归结为求无向完全图的度和延迟受限、具有最小覆盖代价的生成树问题,求解的目标是在满足应用需求和端用户主机性能要求的同时使所消耗的底层网络资源最少。给出了求解该问题的启发式遗传算法,通过仿真实验验证了该算法的有效性。     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

Energy efficient multicast routing in ad hoc wireless networks

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. Each node in the network is assumed to have a fixed level of transmission power. The problem of our concern is: given an ad hoc wireless network and a multicast request, how to find a multicast tree such that the total energy cost of the multicast tree is minimized. We first prove this problem is NP-hard and it is unlikely to have an approximation algorithm with a constant performance ratio of the number of nodes in the network. We then propose an algorithm based on the directed Steiner tree method that has a theoretically guaranteed approximation performance ratio. We also propose two efficient heuristics, node-join-tree (NJT) and tree-join-tree (TJT) algorithms. The NJT algorithm can be easily implemented in a distributed fashion. Extensive simulations have been conducted to compare with other methods and the results have shown significant improvement on energy efficiency of the proposed algorithms.     

Modelling Multicast QoS Routing by using Best-Tree Search in And-or Graphs and Soft Constraint Logic Programming

We suggest a formal model to represent and solve the multicast routing problem in multicast networks. To attain this, we model the network adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a packet on the network link modelled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framework as a convenient declarative programming environment in which to specify related problems. In particular, we show how the semantics of an SCLP program computes the best tree in the corresponding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reaching all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multi-dimensional costs), each component representing a different Quality of Service metric value. Therefore, the construction of the best tree may involve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.     

Performance evaluation of multisource Application Layer Multicast (ALM): Theoretical and simulative aspects

Multisource ALM routing protocol is an indispensable mechanism for efficient distribution of data from many sources to many receivers. The growing of Internet multimedia applications (e.g. videoconference and multiparty online game) which demand large network resources and call for multisource multicasting, has explicitly developed the necessity of an effective method to evaluate and compare the efficiency of various multisource multicast routings. We define a routing cost to be the total number of underlying hops traversed by multicast data over a multicast delivery tree. This study explores a multiplicative property to obtain the minimum cost of various multisource ALM routing protocols by simply multiplying the number of sources to the minimum cost in the single-source multicast. From theoretical and simulative studies, the multiplicative property has been proven through examining the minimum cost of multisource multicast delivery trees constructed by different multisource ALM routing protocols with source-specific tree (SST), core-based group-shared tree (GST-C) and bidirectional group-shared tree (GST-B), which are employed in the design of multisource ALM routing protocols.     

基于遗传算法的一种组播路由算法

在计算机通信中，越来越多的多媒体应用如视频会议、多媒体教学系统、视频点播等需要组播技术，这就需要研究如何构造有效组播树的问题。首先给出基于受限时延的最小代价组播树问题的网络模型及其数学描述。然后提出了一种采用启发式算法和遗传算法的混合算法来解决该问题。该方法可以在满足时延约束的情况下，寻找费用最小的组播路由树。数值仿真实验结果表明该算法有较好的性能，快速有效。     

A tree-based particle swarm optimization for multicast routing

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to finding paths and integrating them to generate a multicast tree. Our algorithm also applies particle swarm optimization to the solution to control the optimization orientation of the tree shape. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.     

动态优化的分布式组播路由算法

为了在真实的网络环境中寻找一棵延迟受限、耗费最小的组播转发树,以便更好地支持组播通信,提出了一个可以动态优化的分布式组播路由算法,该算法利用蚁群思想解决上述组播路由问题.由于不同代的蚂蚁之间可以通过信息素来实现间接通信,而信息素又是一种可以反映环境变化的媒介质,因此,该算法能够根据网络环境的变化及时做出调整.结合实际的网络拓扑,进行仿真实验,实验结果表明,通过蚂蚁一代代的进化,算法可以找到一棵满足延迟约束并且耗费尽可能小的组播树.     

多约束QoS动态多播路由算法

YAM和QoSMIC是支持QoS动态多播路由算法,允许多播组成员动态地加入/退出,同时为接收方提供多个可选择的多播接入路径,以满足不同应用的QoS需求。该文在分析这些算法的基础上,研讨了具有延迟、延迟抖动、带宽和代价等多约束QoS的多播路由问题,描述了一种适应于研究QoS多播路由的网络模型,提出了一种具有多约束QoS的动态多播路由算法(MQDMR),MQDMR试图有效地减少生成多约束QoS的多播树的开销。在MQDMR中,一个多播组成员能动态地加入/退出一个多播会晤,且不干扰现有的多播树。仿真实验结果表明,MQDMR比YAM和QoSMIC具有较小的延时和较少的代价。     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

A multipopulation parallel genetic simulated annealing-based QoS routing and wavelength assignment integration algorithm for multicast in optical networks

In this paper, we propose an integrated Quality of Service (QoS) routing algorithm for optical networks. Given a QoS multicast request and the delay interval specified by users, the proposed algorithm can find a flexible-QoS-based cost suboptimal routing tree. The algorithm first constructs the multicast tree based on the multipopulation parallel genetic simulated annealing algorithm, and then assigns wavelengths to the tree based on the wavelength graph. In the algorithm, routing and wavelength assignment are integrated into a single process. For routing, the objective is to find a cost suboptimal multicast tree. For wavelength assignment, the objective is to minimize the delay of the multicast tree, which is achieved by minimizing the number of wavelength conversion. Thus both the cost of multicast tree and the user QoS satisfaction degree can approach the optimal. Our algorithm also considers load balance. Simulation results show that the proposed algorithm is feasible and effective. We also discuss the practical realization mechanisms of the algorithm.     

一个基于应用层的单源组播协议设计

由于IP组播在实现过程中遭遇了很多困难,所以应用层组播就成了Internet应用研究的热点。本文在简单地论述了应用层组播的优缺点后,提出了一个基于应用层的单源组播协议ALSSMP。此协议设计的目的是能够实现大规模直播视频。在ALSSMP中采用树拓扑优先的方法来构造组播转发树。在组播树的维护方面,利用为转发树中每一个结点预先选择一个"备用父结点"以设置预留链路思想的PCP算法。该协议既继承了应用层组播的优点,又在一定程度上克服了应用层组播的不稳定性的特点,使组播树的稳定性和可靠性大大提高。