斯坦纳树模型在含DG配电网规划中的应用

不确定性分布式电源的接入,给配电网规划带来新的挑战。首先将含分布式电源的配电网规划归纳为求解斯坦纳树问题,提出了一种新的配电网规划建模方法。其次通过DG供电分区的划定,将分区内的负荷节点处理为一个不接DG的负荷节点,消除DG对配电网规划的影响。针对斯坦纳树问题传统解法求解时间会随着斯坦纳点的规模成倍增加的缺陷,采用一种改进的粒子群优化(PSO)算法解决斯坦纳树N-P完全问题。结合54节点算例并与传统方法计算结果比较,验证了该方法的有效性。

基于四边形斯坦纳树的无线传感器网络连通恢复

在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.

基于斯坦纳树的雷场网络大面积损坏修复策略

战场环境下预先设定的智能雷场网络易受到敌方攻击而导致大面积损坏,雷场网络被分割成数个互不相连的部分从而丧失了通讯功能。通过将问题映射到斯坦纳最小树问题,提出了一种新颖的雷场网络修复策略。首先采用雷场区域网格模型限制算法的搜索空间,随后引入蛙跳和离散量子粒子群混合优化(JF-QDPSO)算法确定中续节点位置,修复受损网络。仿真实验表明该策略能够有效的恢复网络拓扑结构,算法计算较快,与其它算法相比,重建后的网络通信能耗小,网络生存周期长。

基于三角形斯坦纳树的分区连通性恢复算法

无线传感器网络中的节点由于自身能量的消耗,及外部因素影响会导致节点出现大规模的失效,从而把无线传感器网络分割成几个独立的不能相互通信的分区。为恢复网络,重建分区之间的通信链路,提出基于三角形斯坦纳树连通恢复算法。该算法首先利用传统算法实现分区连通,然后通过构建三角形斯坦纳树以减少部署的中继节点数量。与现有的一些算法相比,该方法形成的网络拓扑不仅减少了部署中继节点的数量,能够使分区重新连通,而且能够减少网络通信的能量消耗。实验结果表明,所提方法相对于传统算法在构建网络拓扑时更加有效。

一种含浮动端点的斯坦纳树的构造算法

在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接．斯坦纳树（ＳｔｅｉｎｅｒＴｒｅｅ）的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线．根据已有的研究，构造斯坦纳树的问题，是一个ＮＰ完全问题［４］．随着集成电路工艺的发展，人们越来越多地考虑多层布线的问题．本文从多层布线出发，利用在单元或模块内部已有的连线所提供的可用通孔集合作为布线资源，引入浮动端点的概念，提出了一种处理浮动端点的斯坦纳树构造算法ＡＦＬＯＳＴ．该算法能先后生成含浮动端点的最小生成树和含浮动端点的斯坦纳树．根据给定的算法，文中给出了相应的图例来演示构造过程．

八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长.使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优.实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.

矩形斯坦纳树的统计分析法

矩形斯坦纳树是集成电路布图设计的重要问题之一.本文利用统计分析法,提出求解矩形斯坦纳树问题的多项式时间算法.该算法对平面上给定的任意分布的节点集合,得到了统计最优的矩形斯坦纳树.

基于图论的VLSI中最小斯坦纳树问题及其改进算法

超大规模集成电路(VLSI)中,对于多端线网的最佳布线结果是构造最小直角斯坦纳树,该问题是典型的NP组合优化问题.利用图论中直角斯坦纳树的性质,在采用斯坦纳点编码方案寻找优化点位置的基础上,增加粒子趋同性判定及惯性权重系数调整策略,提出改进的粒子群优化算法,对一些实例模型进行了仿真测试,表明该算法的效果良好.

斯坦纳树问题及其推广

斯坦纳树问题是组合优化学科中的一个问题. 组合优化学科包含许许多多的问题,它们都来源于生活,是许多实际问题的某种抽象.这类问题中任何一个问题的解决都会给实际生产带来影响;另一方面,其中大部分是一些非常困难的数学问题,对于这些问题的解决,那些传统的抽象性强的数学似乎无能为力,而要求广泛的数学基础和大量的数学训练.

网格空间瓶颈斯坦纳树问题快速近似（英文）

指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.

基于斯坦纳树和泰森多边形的连通恢复算法

针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法(CRAST)。首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后,用关键节点构建Delaunay三角网,通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性。

VLSI布线中有障碍斯坦纳树的优化方法

以集成电路设计中应用较多的有障碍直角斯坦纳树为切入点,对模拟退火法和最小生成树法得到的斯坦纳树进行绕障碍优化,提出进一步缩减总体线长的方法。根据边与障碍的相交关系,对初始直角斯坦纳树进行分类,利用改变直角化方式和绕行障碍边界方式变化布线图;提出检测线路空U并对其进行缩进和变换的方法,清除冗余的线段,将现有斯坦纳树的总体线长缩短到更加接近最优的地步。

欧氏平面快速k-瓶颈斯坦纳树近似算法

瓶颈k-Steiner树问题描述如下:给定n个点和一个正整数k,寻找一棵Steiner树用至多k个Steiner点将n个点连接起来,使得此Steiner树的最长边最短。L.Wang和D.-Z.Du证明了适用于欧几里得平面瓶颈斯坦纳树算法的近似性能比为2,并且给出了一个适用于该问题时间复杂度为(nlogn+kn)的算法,在欧几里得平面上和近似性能比为2的前提下,通过引入最大堆和斐波那契堆分别对该算法进行优化,优化后算法的时间复杂度分别达到(nlogn+klogn)和(nlogn+k),优化后的算法在现实中可以更好地应用。

谈谈斯坦纳树

谈谈斯坦纳树堵丁柱中国科学院应用数学研究所１０００８０）１费尔马的问题最短网络是项历史悠久的数学课题．它的历史可以追溯到费尔马．１６４０年，费尔马提出如下问题：于平面上给出Ａ，Ｂ，Ｃ三点，求一点Ｓ使距离和ＳＡ＋ＳＢ＋ＳＣ达到最小．该问题引起了许多人的...

斯坦纳树和凸多边形的WSN分区双连通恢复

针对无线传感器网络分区在恢复连通后仍然容错不足的问题,提出斯坦纳树和凸多边形的分区双连通恢复方法.首先,以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区;然后,将分区抽象成点后枚举出所有的非退化型四边形,进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点,使分区实现单连通;最后,利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接,形成凸多边形实现分区的双连通,并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上,简化网络结构并降低数据通信延迟.通过仿真,将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比,对比结果表明所提出方案可减少中继节点的部署数量,延长网络寿命.

一种多层绕障直角斯坦纳最小树启发式算法

直角斯坦纳树问题是大规模集成电路物理设计中重要的基本模型.现代集成电路设计需要同时考虑障碍和多层布线等约束条件.通过构造布线图,提出一种多层绕障直角斯坦纳最小树启发式算法.为了避开障碍和连通各布线层之间的引脚,本文引入了三种候选通孔位置.在同一布线层内,通过扩展满直角斯坦纳树网格来构造单层布线图,再使用候选通孔互联成多层布线图.在多层布线图中,引入候选斯坦纳点来构造斯坦纳树,并以标记的引导点执行局部搜索策略来提高求解质量.实验结果表明,本文算法能够有效求解多层绕障直角斯坦纳最小树问题.本文算法所得总布线权重与最新的两种算法相比,改进率可达2.34%和5.48%.

两种斯坦纳问题的近似算法

本文对图的斯坦纳问题和直角斯坦纳问题各设计了一个近似算法。算法不是以构造为主，而是先利用一简单方法构造出斯坦纳树，再用回路修改法对其进行全面改造，从而克服了以局部优化为目标的局限性。

带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中,最小风险和模型以及最小最大风险模型下的斯坦纳树问题.它们推广了相应模型下的最短路问题和最小支撑树问题,在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法,并对算法性能儆了理论分析和证明.结果显示我们的算法具有优良的常数逼近的性质,能在多项式时间内算出令人满意的解.

几类特殊的斯坦纳最小树问题

通过三角形3个顶点和正方形4个顶点的斯坦纳最小树设计的讨论,总结斯坦纳最小树的性质.在此基础上,给出了不多于4个点的斯坦纳最小树的设计和算法.

无线Ad Hoc网络Steiner树实现协议研究

针对无线Ad hoc网络多跳,拓扑结构随时可能动态变化,协作节点间数据传输需实时性强等问题,利用Netlog语言宣告声明最小Steiner树协议的构造算法方法适应解决。协议可快速构造一棵近似最小的Steiner树,每个节点独立运行声明Steiner树协议,构造Steiner节点间的虚拟全联通网络,在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边,继续构造最小代价生成树,最后将此树上的非Steiner节点的叶子节点删除,近似得到最小代价Steiner树,该方法在实验平台上得以验证,为无线移动网络中资源的选择利用提供了一种新的可尝试性的新方法。