A Novel Genetic Algorithm for Stable Multicast Routing in Mobile Ad Hoc Networks

Data transmission among multicast trees is an efficient routing method in mobile ad hoc networks(MANETs). Genetic algorithms(GAs) have found widespread applications in designing multicast trees. This paper proposes a stable quality-of-service(QoS) multicast model for MANETs. The new model ensures the duration time of a link in a multicast tree is always longer than the delay time from the source node. A novel GA is designed to solve our QoS multicast model by introducing a new crossover mechanism called leaf crossover(LC), which outperforms the existing crossover mechanisms in requiring neither global network link information, additional encoding/decoding nor repair procedures. Experimental results confirm the effectiveness of the proposed model and the efficiency of the involved GA. Specifically, the simulation study indicates that our algorithm can obtain a better QoS route with a considerable reduction of execution time as compared with existing GAs.

Multiple constraints-based QoS multicast routing: model and algorithms

Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.

QoS multicast routing algorithm based on GA

The multicast routing problem with multiple QoS constraints in networks with uncertain parameters is discussed, and a network model that is suitable to research such QoS multicast routing problem is described. The QMRGA, a multicast routing policy for Internet, mobile network or other highperformance networks is mainly presented, which is based on the genetic algorithm(GA), and can provide QoSsensitive paths in a scalable and flexible way in the network environment with uncertain parameters. The QMRGA can also optimize the network resources such as bandwidth and delay, and can converge to the optimal or nearoptimal solution within few iterations, even for the network environment with uncertain parameters. The incremental rate of computational cost can be close to a polynomial and is less than exponential rate. The performance measures of the QMRGA are evaluated by using simulations. The results show that QMRGA provides an available approach to QoS multicast routing in network environment with uncertain parameters.

A New Delay-Constrained Multicast Routing Algorithm Based on Shared Edges

In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not satisfy the delay constraint, so we can ensure that all paths be taken into account will meet the limit of delay constraint, then we find the least costly path in order to build a minimum cost multicast tree. Simulation results show that the algorithm is better than ESAMPH algorithm in performance.

Multicast Routing Based on Hybrid Genetic Algorithm

A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.

Constructing Multicast Routing Tree for Inter-cloud Data Transmission：An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for interclouds is proposed. The proposed algorithm leverages an entropybased process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree(MT) on the basis of the shortest path tree(SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.

A multicast routing algorithm with multiple trees

Quality of service (QoS) multicast routing has continued to be a very important research topic in the Internet. A method of multicast routing is proposed to simultaneously optimize several parameters based on multiobjective genetic algorithm, after the related work is reviewed. The contribution lies on that the selection process of such routing is treated with multiobjective optimization. Different quality criterions in IP network are taken into account for multicast communications. A set of routing trees is generated to approximate the Pareto front of multicast problem. Multiple trees can be selected from the final set of nondominated solutions, and applied to obtain a good overall link cost and balance traffic distribution according to some simulation results.

基于流水线计算的3D NoC测试规划研究

为了提高三维片上网络(3D NoC)资源内核的测试效率,提出一种在功耗约束条件下多播流水线并行测试同构核与单播测试异构核相结合的方法对IP核进行测试。为了减少测试数据因资源冲突而进行等待的时间,设计一种改进XYZ路由算法,并采用改进人工蜂群(ABC)算法求解最佳测试规划方案。以国际标准电路测试集ITC'02作为实验对象,结果表明,测试时间最大优化率达到15.45%,与其他测试规划方法相比该文方法能有效地提高并行测试效率。

满足QoS约束的加速加权分布式动态Multicast算法

在计算机网络中高效实现具有延迟等ＱｏＳ约束的Ｍｕｌｔｉｃａｓｔ功能，是计算机网络应该提供的一种基本功能，是保证视频会议系统、多媒体教学系统、视频点播系统（ＶＯＤ）、网上拍卖等应用得以实现的基础．针对这一问题，提出了一种加速加权方法，根据已经经过的部分路径的延迟和剩余延迟，将成本加速加权，利用加权成本构造Ｍｕｌｔｉｃａｓｔ树．利用该算法，可以在计算机网络中以分布式方式建立接近最小成本、满足延迟约束条件、适于实时通信的动态Ｍｕｌｔｉｃａｓｔ连接，避免了传统方法将成本和延迟分别考虑、大量回溯的弊端．

基于遗传-蚁群优化算法的QoS组播路由算法设计

为了提高网络路由性能,提出并设计了一种基于遗传-蚁群优化算法的服务质量(quality of service,QoS)组播路由算法。首先,设计了自适应变频采集策略用于采集网络与节点信息,以此获得网络和节点的状态,为后续路由优化提供数据支持;其次,计算路径代价,将路径代价最小作为优化目标,建立QoS组播路由优化模型,并设置相关约束条件;最后,结合遗传算法和蚁群算法提出一种遗传-蚁群优化算法求解上述模型,输出最优路径,完成路由优化。实验结果表明,所提算法可有效降低路径长度与路径代价,提高搜索效率与路由请求成功率,优化后的路由时延抖动较小。

多级互连网络中的multicast通信

ＭＰＰ系统中的并行通信是目前并行处理研究的热点，改善并行通信性能、提高网络吞吐率是促进ＭＰＰ性能发挥的关键问题．ｍｕｌｔｉｃａｓｔ通信是区别于点到点通信的一对多通信方式，因而功能更强大，使用起来更灵活方便，在并行处理中应用十分广泛．文中以基于开关元件实现结点间动态互连的多级互连网络为背景，研究了ｍｕｌｔｉｃａｓｔ通信路由算法的效率．针对现有路由算法的不足，提出了基于功能扩展的交换开关的ＳＢＭＴ路由算法，并进一步作出了性能分析和比较．

满足延迟约束的加速加权分布式动态Multicast算法

在计算机网络中高效实现具有延迟约束的Multicast功能,是计算机网络应该提供的一种基本功能,是保证视频会议系统、多媒体教学系统、视频点播系统(VOD)等应用得以实现的基础。该文针对这一问题,提出了一种加速加权方法,根据已经经过的部分路径的延迟和剩余延迟,将成本加速加权,利用加权成本构造Multicast树。利用该算法,可以在计算机网络中以分布式方式建立接近最小成本、满足延迟约束条件、适于实时通信的动态Multicast连接,避免了传统方法将成本和延迟分别考虑、大量回溯的弊端。

IP MULTICAST GROUP MANAGEMENT FOR BROADCAST LANS DISTRIBUTION

Problems of the current IGMP mechanism were identified, such as unnecessary periodic probing of hosts and leave latency, which wastes bandwidth and cause more traffic and overhead. Alternative mechanism that preserve the IP multicast model but employ join/leave messages to track local group membership for broadcast LANs (shared medium LANs) was proposed in this paper. We describe the implementation requirements of the new mechanism and compare it to existing one, demonstrating that join/leave approach is uniformly superior for the environment of broadcast LANs.

分层自治的Multicast地址管理和连接控制

Multicast动态地址管理和连接控制是多点会话中的重要问题．基于分层自治结构，文章提出了Multicast地址分配管理机制、主从结构连接管理体系和一种简单的多点连接建立算法，简述了它们的工作过程，并通过模拟实验比较了3种地址分配方式，即集中管理方式、分布方式（由Eleftheri-adis提出）与分层自治方式．分层自治结构与Internet自组织拓扑结构一致，分层自治地址分配机制结合了集中方式和分布方式的优点，具有较高的整体效率，主从结构连接管理体系也具有较高的控制效率，它们都具有较高的鲁棒性、柔韧性和伸缩性．

A Low-Complexity Resource Allocation Scheme for OFDMA Multicast Systems with Proportional Fairness

A low-complexity optimization scheme is proposed to balance the tradeoff between system capacity and proportional fairness in orthogonal frequency division multiple access(OFDMA) based multicast systems. The major challenge is to solve the non-convexity optimization problem with strict proportional fairness. Constrained team progress algorithm(CTPA) solves this non-convexity problem by allocating sub-channels to each group based on sub-channel gains and proportional fairness constraint. Mapping power algorithm(MPA) guarantees strict proportional fairness with efficient power allocation which utilizes the mapping relation between power and throughput. CTPA-MPA is analyzed in three aspects: complexity, fairness and efficiency. We numerically show that when the system capacity is slightly increased in lower power region compared with several previous approaches, CTPA-MPA improves the proportional fairness in a typical scenario with 4 groups over 16 sub-channels, while reducing the complexity from exponential to linear in the number of sub-channels. It is also proved available in a more complicated system.

A Cooperative Evolution of Multiple Operators Based Adaptive Quantum Genetic Algorithm for Network Coding Resources Optimization

In order to optimize the network coding resources in a multicast network, an improved adaptive quantum genetic algorithm (AM-QEA) was proposed. Firstly, the optimization problem was translated into a graph decomposition problem. Then the graph decomposition problem was represented by the binary coding, which can be processed by quantum genetic algorithm. At last, a multiple-operators based adaptive quantum genetic algorithm was proposed to optimize the network coding resources. In the algorithm, the individual fitness evaluation operator and population mutation adjustment operator were employed to solve the shortcomings of common quantum genetic algorithm, such as high convergence rate, easy to fall into local optimal solution and low diversity of the population in later stage. The experimental results under various topologies show that the proposed algorithm has the advantages of high multicast success rate, fast convergence speed and strong global search ability in resolving the network coding resource optimization problems.

A Self-Adaptive Quantum Genetic Algorithm for Network Flow Vehicle Scheduling Problem

Bicycle sharing scheduling is a complex mathematical optimization problem, and it is challenging to design a general algorithm to solve it well due to the uncertainty of its influencing factors. This paper creatively establishes a new mathematical model to determine the appropriate number of vehicles to be placed at each placement point by calculating the traffic weights of the placement points and optimizes the hyperparameters in the algorithm by adaptive quantum genetic algorithm, and at the same time combines the network flow algorithm in graph theory to calculate the most suitable scheduling scheme for shared bicycles by establishing the minimum cost maximum flow network. Through experimental validation, the network flow-based algorithm proposed in this paper allows for a more convenient calculation of the daily bike-sharing scheduling scheme compared to previous algorithms. An adaptive quantum genetic algorithm optimizes the hyperparameters appearing in the algorithm. The experimental results show that the algorithm achieves good results as the transportation cost is only 1/15th of the GA algorithm and 1/9th of the QGA algorithm.

遗传算法与带权搜索融合的QoS组播路由算法

针对传统多约束路由选择算法计算负担重的问题,论文提出了一种基于遗传算法与带权宽度优先搜索融合的QoS组播路由算法.所提方法融合了遗传算法与带权宽度优先搜索方法,在分组丢包率、带宽、时延抖动、时延等QoS条件约束下,通过所提算法快速得到备选路径,并获取最优的组播路径.在仿真实验中,将所提算法与LDT进行了相比,实验结果表明,论文所提算法可以解决多约束条件下的QoS分组路由问题,并能够有效降低计算负载、减少算法执行时间.

一种协同进化的无线传感器网络多播路由算法

物联网促进了无线传感器网络的发展,同时对无线传感器网络在能量损耗和通信质量保证等方面的性能也提出更高的要求.本文提出一个基于多目标协同进化的多播路由算法(CCMRA)来解决同时优化功耗、时延和丢包率3个目标的无线传感器网络多播路由问题.CCMRA算法的种群个体是目标传感器网络其中一颗多播树,将种群分成两个子种群LP和GP,它们针对不同的最优多播树结构分别采用Local操作和Global操作策略生成下一代多播树种群个体,利用竞争性协同进化机制在两个子种群之间通过选择和融合交换种群之间的信息,经过逐代进化最终得到最优的多播树.上述种群内部和种群之间的协同进化机制,增加了种群多样性和随机性,从而提高算法的搜索能力,使算法能够跳出局部最优,获得良好的收敛精度和速度.本文采用8种不同复杂程度的无线传感器网络场景,引入3种对比算法.实验表明CCMRA在功耗、时延和丢包率3个指标上表现出优良的性能.同时在超体积、反向世代距离和世代距离等多目标指标上的表现也优于对比算法,进一步验证CCMRA算法在收敛性和多样性保持上具有竞争力.