结合集中式与分布式特征的多路径QoS组播路由协议

提出了一个结合集中式算法与分布式算法优点的多路径启发式QoS组播路由算法和协议,它以单播路由协议OSPF传播链路的代价信息为基础,运用最小代价Dijkstra算法计算端节点到当前在树节点的最小代价路径,然后启动一个分布式计算过程得到一个可选路径集,加入节点通过一个综合性启发式选择其中的最佳路径连接到组播树．算法能够有效地支持延时和带宽受限的代价优化组播树构造,具有无环选路、呼叫接收成功率高、呼叫建立时间短、伸缩性好等特点．     

A genetic algorithm for the multiple destination routing problems

The multiple destination routing (MDR) problem can be formulated as finding a minimal cost tree which contains designated source and multiple destination nodes so that certain constraints in a given communication network are satisfied. This is a typical NP-hard problem, and therefore only heuristic algorithms are of practical value. As a first step, a new genetic algorithm is developed to solve the MDR problems without constraints. It is based on the transformation of the underlying network of an MDR problem into its distance complete form, a natural chromosome representation of a minimal spanning tree (an individual), and a completely new computation of the fitness of individual. Compared with the known genetic algorithms and heuristic algorithms for the same problem, the proposed algorithm has several advantages. First, it guarantees convergence to an optimal solution with probability one. Second, not only are the resultant solutions all feasible, the solution quality is also much higher than that obtained by the other methods (indeed, in almost every case in our simulations, the algorithm can find the optimal solution of the problem). Third, the algorithm is of low computational complexity, and this can be decreased dramatically as the number of destination nodes in the problem increases. The simulation studies for the sparse and dense networks all demonstrate that the proposed algorithm is highly robust and very efficient in the sense of yielding high-quality solutions     

一种基于约束优化的虚拟网络映射方法

虚拟网络映射问题将不同的虚拟网络应用映射到相同的基础设施网络中,这是一个极具挑战性的问题.针对该问题,提出了一种基于约束优化的虚拟网络映射方法,将映射问题分解为节点映射和链路映射两个阶段,其中,前者是将虚拟节点映射到物理节点上,后者将虚拟链路映射到物理路径上,它们都是NP难问题.针对节点映射和链路映射分别提出了node-mapping算法和link-mapping算法.node-mapping算法基于贪婪算法的思想,映射时考虑了物理节点所能提供的资源数量以及物理节点间距离两个因素,该算法能够保证基础设施网络中各节点间的负载相对均衡;同时,通过采用访问控制机制,过滤一些异常的虚拟网络请求,能够有效地提高资源的使用效率.link-mapping算法基于人工智能领域中的分布式约束优化思想,其能够保证得到的解是全局最优的,即映射链路的代价最小.最后,通过模拟实验对该方法进行验证,实验结果表明该方法在求解虚拟网络映射问题时的性能良好.     

Approximation algorithm for constructing data aggregation trees for wireless sensor networks

This paper considers the problem of constructing data aggregation trees in wireless sensor networks (WSNs) for a group of sensor nodes to send collected information to a single sink node. The data aggregation tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data aggregation tree is to minimize the number of non-source nodes to be included in the tree so as to save energies. We prove that the data aggregation tree problem is NP-hard and then propose an approximation algorithm with a performance ratio of four and a greedy algorithm. We also give a distributed version of the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithms. The results show that the proposed algorithms can find a tree of a good approximation to the optimal tree and has a high degree of scalability.     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

An orthogonal genetic algorithm for multimedia multicast routing

Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near optimal solutions within moderate numbers of generations     

Coordinated multimedia object replacement in transcoding proxies

Finding replacement candidates for accommodating a new object is an important research issue in web caching. Due to the new emerging factors in the transcoding proxy and the aggregate effect of caching multiple versions of the same multimedia object, this problem becomes more important and complex as audio and video applications have proliferated over the Internet, especially in the environment of mobile computing systems. This paper addresses coordinated cache replacement in transcoding proxies. First, we propose an original model which determines cache replacement candidates on all candidate nodes in a coordinated fashion with the objective of minimizing the total cost loss for linear topology. We formulate this problem as an optimization problem and present a low-cost optimal solution for deciding cache replacement candidates. Second, we extend this problem to solve the same problem for tree networks. Finally, we conduct extensive simulations to evaluate the performance of our solutions by comparing with existing models.     

Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph

If in the Steiner problem on graph the number of terminal nodes is much smaller than that of all graph nodes (say 50 against 1000), then one can see in its solution (the minimum tree) a system of paths on the graph connecting the terminal vertices, rather than a collection of separate edges (or arcs). This path system is similar to the system of segments making up the Steiner tree on the Euclidean plane: the local degree of the terminal nodes usually is 1, and the local degree of some nodes making up the paths is 3 or more. These nodes are the counterparts of the Steiner points in the problem on plane. Structural similarity of the trees in the Steiner problems on the Euclidean plane and on graph enables one to construct the algorithm to solve the Steiner problem on graph along the same lines as in the Steiner problem on the Euclidean plane. On the other hand, the solution of a problem on graph may be regarded as that on the Euclidean plane, provided that the graph satisfies certain requirements.     

Neural network for optimal steiner tree computation

Hopfield neural network model for finding the shortest path between two nodes in a graph was proposed recently in some literatures. In this paper, we present a modified version of Hopfield model to a more general problem of searching an optimal tree (least total cost tree) from a source node to a number of destination nodes in a graph. This problem is called Steiner tree in graph theory, where it is proved to be a NP-complete. Through computer simulations, it is shown that the proposed model could always find an optimal or near-optimal valid solution in various graphs.     

On the bottleneck tree alignment problems

Given a set W of k sequences and a tree T with k leaves labeled with a unique sequence in W, a label tree is used to assign a sequence label to each internal node of the tree T. The cost of a tree edge is defined as the distance, such as the Hamming distance or the Levenshtein (edit) distance, between the sequence labels of a pair of nodes in the edge. The bottleneck edge of a label tree is the edge with the maximum cost in the label tree. The bottleneck tree alignment problem is concerned with the determination of a label tree with minimum cost of the bottleneck edge. A lifted label tree is a label tree in which the sequence label of each internal node is equal to the sequence label of some child of the node. The bottleneck lifted tree alignment problem involves the minimization of cost of the bottleneck edge among all possible lifted label trees of the tree T. This paper shows that when the distance function is a metric, the bottleneck tree alignment problem is NP-complete even when the tree structure resembles a binary tree. For special cases, an exact algorithm is used to solve the bottleneck lifted tree alignment problem in polynomial time. A 2(h-1)-approximation algorithm is used to solve the bottleneck tree alignment problem, where h is the height of the tree T. It is observed that the bound is existentially tight. Finally, this paper shows that any lifted label tree is an optimal solution to the bottleneck tree alignment problem if the distance function is an ultrametric.     

基于节点连通性排序的虚拟网络映射算法

对当今云环境下的数据中心来说,以虚拟资源租赁的运营方式具有极大的灵活性,尤其是以虚拟网络为粒度的资源租赁能够为用户提供更好的个性化需求支持。虚拟网络映射问题是指依据用户资源需求,合理分配底层主机和网络资源。现有的虚拟网络映射算法大多是针对随机拓扑设计的通用算法,未针对数据中心拓扑结构进行优化,映射效率有很大提升空间。针对数据中心的结构特点,提出了一种基于节点连通性排序的虚拟网络映射算法BS-VNE算法。首先,设计了一种最大生成算法来对虚拟节点重要程度进行求解和排序。该算法不仅基于虚拟节点的带宽和连通度,还基于虚拟节点在整个虚拟网络中的连通性来进行节点连通性的计算,以获得更加合理的排序结果。然后,根据虚拟节点连通性排序结果利用离散粒子群优化算法求解虚拟网络的映射解。在求解过程中,引入了针对数据中心结构的物理网络拓扑启发式规则,并将其组合到粒子搜索过程中,以提高映射算法的收敛速度。仿真实验结果表明,与现有算法相比,本文提出的算法可以提高物理网络的收益/成本比和资源利用率。     

面向期限感知分布式矩阵相乘的高效存储方案

分布式矩阵相乘是众多分布式机器学习、科学计算等应用中的关键操作,但其性能会受到系统中常见的落后节点的严重影响。最近研究者提出了基于喷泉码的编码矩阵相乘方法,能够充分利用落后节点的部分计算结果,从而大幅度减轻落后节点问题,但忽略了工作节点的存储开销。在考虑存储开销与计算完成时间之间的权衡关系的基础上,首先提出了面向异构工作节点的计算期限感知的存储优化问题;然后进一步通过理论分析,提出了基于期望近似的解决思路,并通过松弛将问题转化为凸优化问题以方便高效求解。仿真实验表明,在保证较大的任务成功率的情况下,所提方案的存储开销会随着任务期限的放宽迅速下降,并且该方案能够更大幅度降低编码带来的存储开销。也就是说,所提方案能够在保障整体计算在期限内大概率完成的前提下,大幅度降低总体的额外存储负载。     

低空复杂环境下基于采样空间约减的无人机在线航迹规划算法

针对低空复杂环境下障碍物密集且类型多样、带有多通道并存在不确定信息的无人机在线航迹规划问题,为了减少碰撞检测次数,提高航迹搜索速度,降低航迹代价,提出一种基于采样空间约减的无人机在线航迹规划算法. 算法通过引入代价模型,提出约减域逐步构造方法,引导规划树快速有效扩展,改善了基于动态域的快速拓展随机树（Dynamic domain rapidly-exploring random tree,DDRRT） 算法中存在的采样空间过度约减问题. 算法通过密度划分索引的方法逐步构建多棵Kd 树（K-dimensional tree）并采用多近邻节点搜索方法,加快了近邻树节点搜索速度. 仿真实验结果表明,与DDRRT方法相比,该方法在保证对采样空间约减合理性的同时,提高了航迹规划效率和通道内的寻路能力.     

度约束QoS组播路由遗传算法

有度约束的QoS组播路由问题在通信网络中具有重要意义。提出一种基于遗传算法的度约束组播路由算法,采用节点连接路径形式的编码方法构成一棵组播树的表示,设计了相应的具有树形结构的交叉和变异算子,以及节点度的改变算法。算法可以实现具有树形结构染色体的遗传进化。数值实验表明算法具有找到最优解的能力,特别适合于求解大规模网络有度约束的QoS组播路由问题。     

移动社会网络中社会性路由算法研究

在无法部署Sink的无线传感器网络中, 数据采集者(即:能够收集数据的人或移动设备)在网络的任意位置收集数据, 即泛在数据收集。网络区域中的节点数量庞大, 能量有限, 如何能有效地采集到全部节点的数据是一个难点。提出一个网络生命周期最大化的泛在数据收集协议MULAC。MULAC以用户所在当前位置为圆心, 半径为r的区域内选择一个节点v。以v为根构造一棵最大化生命周期树T。网络中的节点可以通过T传送数据给v, 数据采集者可以通过v接收到网络中的全部数据。当数据采集者移动到其他位置, T将根据用户新的位置改变根节点, 并且以最小的能量耗费调整树结构, 从而延长全网的寿命。在收集数据过程中保证无线传感器网络生命周期最大化是一个NP完全问题, MULAC能够近似最优的解决此问题。仿真实验和理论分析表明, MULAC能有效延长网络生命周期。     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

无信号交叉口网联车调度与分布式控制策略

针对多车道无信号交叉口,在高交通流量时易发生拥堵的问题,提出了一种适用于交叉口智能网联车(connected automated vehicle, CAV)通行的解决方案,将问题解耦成顺序决策和分布式控制两个问题。而车辆调度是方案中的关键点,对通行效率有很大的影响,且问题的复杂度是指数级。为解决该问题,提出一种基于队列评价模型的决策方法(queue evaluation spanning tree, QEST),将网联车存到的多个队列模型中,并以通行效率和车辆延迟建立代价函数,以此对队列进行评价,通过不断循环选择最佳的队列,优化车辆在交叉口的通行顺序,有效提升了通行效率。对第二个问题,提出一种分布式控制框架,使得车辆按预定顺序通过交叉口。结果表明,该方案在中高交通流量时能有效提升交叉口的通行效率并降低车辆延迟和能量消耗。     

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.Scope and purposeMulticasting is a mechanism used in communication networks that allows distribution of information from a single source to multiple destinations. The problem of finding a multicast connection for a static group of communicating entities in connection-oriented point-to-point network can be formulated in graph theory as a minimum Steiner tree problem. Due to NP-completeness of the Steiner tree problem multicast, routing algorithms are based on heuristics. The diversity of network environments and the lack of centralised information about network topology require an effective distribution of the multicast routing algorithms among the network nodes. This article presents an alternative to the distributed algorithm proposed by Rugelj and Klavzar that implements the same heuristics for the construction of a minimum cost multicast connection in point-to-point networks. The present algorithm constitutes a substantial improvement over that previously proposed with regard to running time and the amount of the information exchanged between network nodes.     

Efficient assignment and scheduling for heterogeneous DSP systems

This paper addresses high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. We propose a two-phase approach to solve this problem. In the first phase, we solve the heterogeneous assignment problem, i.e., how to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove that the heterogeneous assignment problem is NP-complete. Efficient algorithms are proposed to find an optimal solution when the given DFG is a simple path or a tree. Three other algorithms are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost compared with the previous work.