最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求...最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。展开更多
Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tre...Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.展开更多
A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree...A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.展开更多
In this paper,Steiner minimal trees for point sets with special structure are studied. These sets consist of zigzag lines and equidistant points lying on them.
In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on t...In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least;if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.展开更多
针对基于树的组播路由协议中组播树鲁棒性不好,扩展能力差的特点,又结合无线传感器网络自身能量、计算、存储能力有限的特点,提出了基于虚拟Steiner树的组播随机路由协议VMRRP(Virtual-steiner-tree based Multicast Random Routing Pro...针对基于树的组播路由协议中组播树鲁棒性不好,扩展能力差的特点,又结合无线传感器网络自身能量、计算、存储能力有限的特点,提出了基于虚拟Steiner树的组播随机路由协议VMRRP(Virtual-steiner-tree based Multicast Random Routing Protocol)。该协议的随机路由思想,使得组播树中源节点到各个组成员节点的路径是动态变化的,与GMP(Geographic Multicast Routing)协议相比,增加了组播树的鲁棒性,也均衡了网络能量,增加了网络生命周期,并通过NS-2仿真试验得到了验证。展开更多
文摘最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。
基金supported by the National High-Tech R&D Program(863Program)No.2015AA01A705the National Natural Science Foundation of China under Grant No.61202079+1 种基金the China Postdoctoral Science Foundation under Grant No.2014T70031the Fundamental Research Funds for the Central Universities of China No.2015JBM111
文摘Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.
基金the National Natural Science Foundation of China (70471065)the Shanghai Leading Academic Discipline Project (T0502).
文摘A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.
基金Supported by NSF of China(1 970 1 0 2 8) and National973Fundamental Research Project
文摘In this paper,Steiner minimal trees for point sets with special structure are studied. These sets consist of zigzag lines and equidistant points lying on them.
文摘In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least;if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.
文摘针对基于树的组播路由协议中组播树鲁棒性不好,扩展能力差的特点,又结合无线传感器网络自身能量、计算、存储能力有限的特点,提出了基于虚拟Steiner树的组播随机路由协议VMRRP(Virtual-steiner-tree based Multicast Random Routing Protocol)。该协议的随机路由思想,使得组播树中源节点到各个组成员节点的路径是动态变化的,与GMP(Geographic Multicast Routing)协议相比,增加了组播树的鲁棒性,也均衡了网络能量,增加了网络生命周期,并通过NS-2仿真试验得到了验证。
