一种基于拉格朗日松弛的时延约束多播路由算法

提出了一种基于拉格朗日松弛方法的时延约束最小代价多播路由算法(LR-DLMA)。该算法充分利用拉格朗日松弛方法的特点，通过构建封闭图，对封闭图进行拉格朗日松弛求得满足条件的多播树。仿真实验结果表明本算法性能稳定，其代价性能接近性能最好的BSMA算法，并具有快速、低时延的特点。     

Distributed multicast routing for delay-sensitive applications

A distributed multicast algorithm for constructing minimum cost multicast trees with delay constraints is proposed. The proposed algorithm can always construct a delay-constrained multicast tree, if one exists, and exhibits superior tree cost performance compared to existing algorithms     

一种基于带宽和时延约束的分布式组播路由算法

针对已有分布式组播路由算法在寻找QoS路由时的低成功率问题,本文提出了一种新的基于带宽和时延约束的分布式组播路由算法-QDMR(QoS-based Distributed Multicast Routing).在为新组播成员搜索连接到组播树的可行路径时,QDMR算法使用RBMF(Reverse Best Metric Forwarding)转发算法代替RPF(Reverse Path Forwarding)转发算法,从而优先搜索满足带宽和时延约束要求的路径,然后才考虑代价的优化.模拟分析表明,QDMR提高了路由搜索的成功率,并且降低了协议开销.     

A distributed delay-constrained dynamic multicast routing algorithm

Many new distributed multimedia applications involve dynamic multiple participants, have stringent end-to-end delay requirement and consume large amount of network resources. In this paper, we propose a distributed delay-constrained dynamic multicast routing algorithm (DCDMR) to support these applications. DCDMR scales well because the source of the multicast tree needs only limited computation or may even not be involved in the route computation. When group membership changes, the existing multicast tree is perturbed as little as possible and the resulting tree cost performance is very satisfactory.     

An energy-efficient,distributed wireless multicast protocol based on concurrent CTS and <Emphasis Type="Italic">N</Emphasis><Superscript>2</Superscript> connectivity

Media acquisition process in wireless multicast requires that the sender obtains confirmation replies from a set of receivers. If replies are uncoordinated, the process can be much more time consuming than that of wireless unicast due to packet collisions. We propose a wireless multicast scheme that utilizes a novel concurrent Clear-To-Send (CTS) transmission method and a distributed multicast tree construction method. The concurrent CTS based MAC (Media Access Control) layer design can significantly reduce packet collisions and signaling overhead at the local cell level. Built on top of this new MAC layer protocol, we further propose a distributed multicast tree construction algorithm which grows the tree by maximizing the local multicast gain. The uniqueness of our algorithm is that the tree is constructed implicitly during the media access stage and the algorithm requires little additional message overhead. Extensive simulations are conducted to evaluate the performance of the proposed scheme. Our results indicate that the proposed scheme offers considerable improvement in multicast turnaround time and efficiency. The proposed scheme is also robust against network topology changes caused by node movements.     

A rearrangeable algorithm for the construction of delay-constraineddynamic multicast trees

With the proliferation of multimedia group applications, the construction of multicast trees satisfying quality of service (QoS) requirements is becoming a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support dynamic multicast sessions wherein the membership of the multicast group changes with time. In this paper, we propose and evaluate an algorithm called CRCDM (controlled rearrangement for constrained dynamic multicasting) for on-line update of multicast trees to adjust to changes in group membership. The CRCDM algorithm is based on a concept called quality factor (QF) that represents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree drops below a threshold, a rearrangement technique is used to suitably modify the tree. Our algorithm aims to satisfy the delay constraints of all current group members, at the same time minimizing the cost of the constructed tree. We compare the performance of our algorithm, by simulation, with that of an off-line Steiner heuristic; with ARIES, a previously published algorithm for on-line update of unconstrained trees; and with the algorithm proposed by Hong, Lee and Park (see Proc. IEEE INFOCOM, p.1433-40, 1998) for on-line update of delay-constrained trees. The simulation results indicate that our algorithm provides excellent cost-competitiveness that is better than that provided by the algorithm described by Hong et al., minimizes changes in the multicast tree after each update, and performs favorably even when compared with the unconstrained ARIES heuristic     

一种改进的时延受限低代价光组播路由算法

针对光网络时延受限光组播路由计算复杂度高的问题,提出一种基于改进的和声搜索求解时延受限光组播路由的算法。论文通过引入自适应的和声记忆保留率及微调概率提高和声算法搜寻到全局最优光组播树的能力;算法设计了一个能够保持备选光组播树多样性的动态适应度函数以扩大光组播路由的搜索范围;同时,算法在初始化和声库时采用精英保留策略简化和声迭代过程。仿真结果表明,提出的改进算法能够求得代价更低的光组播路由,且算法在较大光网络规模下具有较好的收敛稳定性。     

QoS multicast routing in cognitive radio ad hoc networks

In this paper, we discussed the issues of QoS multicast routing in cognitive radio ad hoc networks. The problem of our concern was: given a cognitive radio ad hoc network and a QoS multicast request, how to find a multicast tree so that the total bandwidth consumption of the multicast is minimized while the QoS requirements are met. We proposed two methods to solve it. One is a two‐phase method. In this method, we first employed a minimal spanning tree‐based algorithm to construct a multicast tree and then proposed a slot assignment algorithm to assign timeslots to the tree links such that the bandwidth consumption of the tree is minimized. The other is an integrated method that considers the multicast routing together with the slot assignment. Extensive simulations were conducted to show the performance of our proposed methods. Copyright © 2011 John Wiley & Sons, Ltd.     

Efficient solutions to multicast routing in communication networks

An important problem in both wireless and wired communication networks is to be able to efficiently multicst information to a group of network sites. Multicasting reduces the transmission overhead of both wireless and wired networks and the time it takes for all the nodes in the subset to receive the information. Since transmission bandwidth is a scarce commodity especially in wireless networks, efficient and near minimum-cost multicast algorithms are particularly useful in the wireless context. In this paper, we discuss methods of establishing efficient and near minimum-cost multicast routing in communication networks. In particular, we discuss an efficient implementation of a widely used multicast routing method which can construct a multicast tree with a cost no greater than twice the cost of an optimal tree. We also present two efficient multicast tree constructions for a general version of the multicast routing problem in which a network consists of different classes of nodes, where each class can have one or more nodes of the same characteristic which is different from the characteristics of nodes from other classes. Because of their efficient running times, these multicast routing methods are particularly useful in the mobile communication environments where topology changes will imply recomputation of the multicast trees. Furthermore, the proposed efficient and near minimum-cost multicast routing methods are particularly suited to the wireless communication environments, where transmission bandwidth is more scarce than wired communication environments.Partially supported by NSF/LaSER under grant number EHR-9108765, by LEQSF grant number 94-RD-A-39, by NASA under grant number NAG 5-2842.     

基于光森林的弹性光网络能效组播路由频谱分配策略

在弹性光网络中,光树传输组播可以节省链路代价,但较长的光树需要选择更低的调制等级,消耗更多的频谱资源和发射机功耗.提出一种基于遗传算法的光森林组播和光树重配置(GAMF-TR)优化组播的能效路由、调制格式和频谱分配(RMSA)策略.GAMF-TR策略设计染色体编码表示光森林的组播目的节点划分和光路径组合,通过染色体的基因位概率交叉和变异得到更多的光森林RMSA策略,设计了一个频谱分配效率和发射机功耗折中的适应度函数选择能效最高的光森林RMSA策略,并设计在网络资源充足时将组播从光森林重配置到光树传输,进一步减少发射机功耗的消耗.仿真结果表明:提出的GAMF-TR策略获得了组播的最低带宽阻塞率和最高能效性能.     

Performance assessment of multicast node placement for multicast routing in WDM networks with sparse light splitting

This article examines all-optical multicast routing for wavelength-routed optical networks with sparse Multicast Capable (MC) nodes in two phases. The first phase is MC node placement and use of a simple and straightforward Maximum Path Count First (MPCF) algorithm to obtain candidates for MC nodes. The second phase is multicast routing with MC-based schemes that minimizes the number of wavelength channels with minimum transmission delay as required by a given multicast session, in that a light-tree is first constructed to connect MC nodes in a multicast group by using two algorithms, namely, the Pre-computing Minimum Cost (PMC) tree algorithm and the Pre-computing Shortest Path (PSP) tree algorithm. System performance of the proposed MPCF MC node placement algorithm is compared with that of the Normalized Cuts (NC) MC node placement algorithm for both PMC and PSP multicast routing. Furthermore, simulation results compare PMC and PSP multicast routing based on MPCF and NC node placement with Re-route-to-Source (RTS), Re-route-to-Any (RTA), Member-First (MF), and Member-Only (MO) multicast routing based on a light forest for a given multicast session in terms of average number of wavelengths needed, average blocking probability, and mean maximum transmission delay.

一种新的基于虚拟队列的无线多播网络编码调度策略

网络编码由于其传输效率高的特性,近年来在无线多播网络中得到广泛的应用。针对无线多播网络中丢包自动重传效率低的问题,该文提出一种新的基于虚拟队列中数据包到达时间的编码调度策略(CSAT)。在CSAT策略中,为了提高编码效率,采用虚拟队列来存放初始以及未被所有接收者接收到的数据包。考虑到队列的稳定性,CSAT策略按照一定的比率从主次队列选择发送;在次队列发送数据包时,结合了编码和非编码两种方式,根据数据包到达队列的先后,选取能够使较多数据包参与编码的方式发送。仿真结果表明,该文所提的CSAT编码调度策略在有效提高了数据包传输效率的同时,提高了网络的吞吐量并降低了平均等待时延。     

Solve the Tree Setup Problem and Minimize Control Overhead for High-Density Members in Delay-Bounded Distributed Multicast Networks

The multicast routing is one of the important techniques for achieving multicast applications in wireless networks, e.g., real-time video multicasting in Vehicular Ad-hoc NETwork (VANET). The main objective of a delay-bounded multicast algorithm is to determine the least-cost multicast tree while satisfying the delay-bounded requirement for multicasting voice/video transmission. Several multicast algorithms have been proposed, some disadvantages have not yet solved, including: (1) yielding a large numbers of control messages, (2) yielding dangling nodes, (3) exhibiting the cycle-free problem, (4) increasing the tree setup time, (5) suffering from the tree setup-break problem, etc. Thus, this paper proposes an adaptive distributed multicast routing (ADMR) algorithm to guarantee cycle-free, to overcome the tree setup-break and the dangling nodes problems while achieving the least-cost delay-bounded multicast tree for high density member multicast networks. Numerical results demonstrate that ADMR significantly outperforms the compared algorithms in the number of control messages and the setup convergence time. Finally, the worst case time complexity and the number of messages of ADMR are analyzed, which requires O(n · (m?+?c)) time and O(2m?+?2c) messages, respectively. The analyzed results of ADMR are lower than that of the compared algorithms.     

量子进化组播路由算法

近年来,时延受限的代价最小组播树问题备受关注。作为全局优化算法,遗传算法（GA）越来越多的用于解决组播路由问题。GA拥有比经典算法更强的搜索能力,但是它容易陷入＂早熟＂,很难得到最优组播树。基于量子计算的机理和特性并结合进化计算,提出了一种新颖的量子进化组播路由算法（QEA）,有效地解决了遗传组播路由算法中的＂早熟＂问题,并且在每代个体更新中采用量子旋转门策略加速了算法的收敛速度。算法实现简单,控制灵活。仿真结果表明QEA算法性能优于改进的进化算法即克隆多播路由算法（CS）和传统的遗传算法（GA）。     

基于传输路径质量的无线mesh网络可靠多播

提出了一种可靠多播网(RM)模型,探讨了无线链路和节点可靠性对多播路径选择的影响。首先,建立了无线链路的相关性和多播路径的可靠性模型,并提出了多播传输的可靠性判据;同时,结合首树算法和多路径树算法提出了构造可靠多播网的算法。可靠多播网具有并行的多播路径,通过在多播源节点和目的节点之间选择多播链路和节点构成了可靠的多播路径,提供了多播路径的"负荷分担"和"热备份"功能,从而支持了多播业务可靠性。     

A QoS-based HRWA multicast scheme with resource constraint on WDM mesh networks

Several Internet multicast applications, such as teleconferencing and remote diagnosis, have Quality-of-Service (QoS) requirements. It is a challenging task to build QoS constrained multicast trees with high performance and high success ratio. The Dense Wavelength Division Multiplexing (DWDM) can provide high-speed, high-transmission capacity and bandwidth efficiency to proceed with the multipoint-to-multipoint multicast transmission. Reserved paths with the form of a tree are not the ideal topology for the multipoint-to-multipoint multicast transmission because transceivers and reserved wavelength channels will lead to some other new connections that cannot be held at the same time. This paper presents a new Hybrid Routing and Wavelength Assignment with delay constraint (HRWA-DC) multicast algorithm on WDM mesh networks, which reduces the number of searching ring paths to achieve low complexity and the number of links to increase the number of successful connections. Simulation result shows that HRWA-DC is more effective for resource utilization than tree scheme in terms of lower call blocking probability and link utilization even at tight delay constraint. It is suitable for big group size and long holding time for multipoint-to-multipoint multicast transmission.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC94-2213-E-155-045).     

One-to-many multicast restoration based on dynamic core-based selection algorithm in WDM mesh networks

This paper proposes a novel dynamic core-based selection (DCS) algorithm for the multicast restoration in WDM mesh networks. The core-based fault tolerance scheme provides a flexible way to control a number of core nodes with less control overheads for searching the routing path, wavelength assignment (RWA), and restoration paths when fault occurs in the one-to-many multicast domain. Compared with the source-based scheme, core-based schemes are easier to maintain, and specifically scalable in large-scale topologies. In the core-based fault tolerance scheme, k-tuple domination nodes are selected to form a minimum sized vertex subset such that each vertex in the graph is dominated by at least k vertices, where the k is defined as two in this paper. The proposed DCS algorithm is defined as each node in multicast tree session must be directly connected to at least one core node in multicast tree session and also has to be directly connected to at least one core node out of multicast tree session. The primary aim of this work is to provide the scalable and fast local survivability based on the information from core nodes. Simulation results show that the proposed algorithm outperforms the Dual Tree and MRLR algorithms in terms of total hop counts needed for all recovery paths and blocking probability for different network topologies.     

Efficient Retransmission Methods in Wireless MAC Protocol for Multicast

Recent studies on reliable wireless multicast have focused on sending acknowledgement packets from all member stations to the source. Although these studies provide methods of improving the reliability, there have not been any studies on retransmission methods for wireless multicast. Multicast packets are retransmitted based on the unicast transmission rule, which retransmits until all members successfully receive the packet. In this paper, an efficient retransmission method is proposed. The retransmission lasts until the target packet delivery ratio of each member is met. Moreover, the contention window size for retransmission is adjusted based on the reception status of the previous transmission. The performance of the proposed wireless multicast is evaluated by extensive simulations.     

MR2_ODMRP: Improvement of End-to-End Transmission Delay in Wireless Multicast Routing

With recent advances in wireless technology, the importance of the capability to use multiple transmission rates and multiple radios has been widely recognized. In this paper, multi-rate and multi-radio (MR2) characteristics are exploited to improve end-to-end transmission delay for reliable multicasts. To achieve this goal, maximum potential rate based on multiple rates and radio based transmission delay with a different number of available radios are investigated in the construction of multicast routes. Multi-rate multi-radio on-demand multicast routing protocol (MR2_ODMRP), a protocol that makes ODMRP suitable for a MR2 environment, is proposed. An integer linear programming model is proposed to obtain the optimal tree as well as the rate and radios at each node of the tree for each multicast service. The solution is employed to evaluate the performance of the MR2_ODMRP. From the simulation, it is shown that the MR2_ODMRP produces nearly optimal solutions even in environments with a large number of nodes. It outperforms the ODMRP in wireless mesh networks. The end-to-end transmission delay is improved by a factor of four compared to the ODMRP.     

Improved Shuffled Frog-Leaping Algorithm Based QoS Constrained Multicast Routing for Vanets

Prompt and reliable communication between vehicular nodes are essential as its limited coverage and dynamic mobility rate introduces frequent change of network topology. The key feature of vehicular communication that establishes direct connectivity or Road Side Unit-based data transfer among vehicular nodes is responsible for sharing emergency information during critical situations. Multicast routing data dissemination among vehicular nodes is considered to be the potential method of parallel data transfer as they facilitate the option of determining an optimal multicast tree from feasible number of multicast trees established between the source and destinations. This estimation of optimal multicast tree using meta-heuristic techniques is confirmed to improve the throughput and reliability of the network when QoS-based constraints are imposed during multicast routing. An Improved Shuffled Frog-Leaping Algorithm-Based QoS Constrained Multicast Routing (ISFLABMR) is proposed for estimating an optimal multicast tree that confirms effective multi-constrained applied multicast routing between vehicular nodes. ISFLABMR minimizes the cost of transmission to 22% by reducing the number of multicast clusters formed during multicasting through the utilization of local and global-based optimizations. The simulation results of ISFLABMR proveits predominant reduction rate of 24% and 21% in average packet latency and energy consumptions incurred under multicast routing.