SSTT: Efficient local search for GSI global routing

In this paper, a novel global routing algorithm is presented for congestion opti-mization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted,consisting of three optimization sub-strategies: stochastic optimization, deterministic optimiza-tion and local enumeration optimization, to dynamically reconstruct the problem structure. Thus,“transition” can be made from a local minimum point to reach other parts of the search space,traverse the whole search space, and obtain the global (approximate) optimal routing solution.Since any arbitrary initial routing solution can be used as the start point of the search, the initial-ization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.     

一种以电性能优化为目标的Steiner树算法

本文提出了一种以电性能优化为目标的Ｓｔｅｉｎｅｒ树算法，它把从线网的源点到漏点的时间延迟最小作为求解Ｓｔｅｉｎｅｒ树的目标，文中首先给出一种多端线网连线延迟模型，然后导出它的上界，它是线网连线总长和从源点到漏点路径长度的函数。     

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。     

改进的粒子群优化算法在QoS选播路由中的应用

QoS选播路由问题是一个非线性的组合优化问题,已被证明是NP完全问题.提出一种基于改进的粒子群优化的多QoS选播路由算法.算法引入一种特殊相加算子,让较差的路径能够不断向较好的路径学习,使算法尽可能向全局最优者靠近;设计一种随机变异算子,通过对全局极值进行随机变异,保证了粒子的多样性,提高了算法跳出局部最优解的能力.实验结果表明,该算法是可行和有效的,能够在资源预留的基础上较好地满足用户对带宽和时延的要求.     

一种基于DPSO的无线传感器网络QoS路由算法

针对无线传感器网络中不同业务对服务质量(QoS)的不同需求,提出一种基于离散粒子群优化(DPSO)的无线传感器网络QoS路由(DPSO-QR)算法。算法将路由建立过程抽象为多目标优化过程,以节点间通信的传播损耗、时延、带宽、丢包率为优化目标,利用DPSO算法实现多目标优化,为拥有不同QoS需求的网络业务提供满足其特有需求的优化路由。仿真实验表明:与SAR,EQR算法相比,DPSO-QR算法降低了网络平均端到端时延,减小了丢包率,延长了网络寿命。     

PSN网络中基于社会属性的消息路由

PSN（pocket switched network）网络作为一种特殊的DTN（Delay Tolerance Network）网络,除了具有不包含持续端到端连接、高传输时延及节点资源受限的特点以外,具有更强的社会规律性.本文在研究了现有的算法的基础上,提出了一种基于社会信息的路由算法—BridgingCom.为使消息尽快从本地传递到目标节点,我们选择桥接中心度（Bridging Centrality）作为中继节点的选择依据.实验结果表明,与已有相关算法相比,本改进算法能够在网络负载较低的情况下获得较高的传输效率,较低的传输延迟.     

基于SDN与NDN的卫星网络多约束路由算法

针对NDN卫星网络内容传输时延高、丢包率高且请求命中率低的问题,提出了一种基于SDN与NDN的卫星网络多约束路由算法,并命名为SNMcRA。基于SDN的集中控制与全局视图,通过建立多约束路由模型,将链路多约束信息与蚁群算法相结合以求解满足时延、带宽、丢包率多约束的代价最小路径,由节点在包转发的过程中动态完成转发表FIB和待定请求表PIT的构建。实验结果表明,该算法与DSP算法相比时延降低了35%,带宽利用率提升了29%,丢包率降低了17%,并且在请求命中率方面也具有显著优势。     

遗传蚁群算法的WSN移动代理路由算法研究

针对常用路由优化算法存在收敛速度慢、易陷入局部最优等难题,提出了一种遗传蚁群算法的WSN移动代理路由方法(GA-ACA)。首先利用遗传算法的全局搜索能力快速找到较优解,然后将较优解转换成蚁群算法的初始信息素,最后采用蚁群算法收敛速度快的优点,找到移动代理路由全局最优解。仿真结果表明,相对于其他移动代理路由算法,GA-ACA加快了收敛速度,能在更短的时间内找到最优移动代理路由,减少了平均能量消耗和网络延时,提高了WSN整体性能。     

VLSI中高性能X结构多层总体布线器

X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.     

基于禁忌遗传优化的网络拥塞控制算法

为解决网络拥塞问题,提出一种基于禁忌遗传优化的网络拥塞控制算法TSGA。该算法将禁忌搜索和遗传算法相结合,以网络资源消耗最小化和网络负载均衡分布为目标,建立多约束QoS路由优化数学模型。仿真实验结果证明,该算法可实现网络拥塞控制,有效提高网络性能。     

基于遗传算法的WMSNs多路径多目标优化路由算法

针对WMSNs路由算法设计的需求,依据遗传算法的基本原理和Pareto多目标优化方法,提出WMSNs多路径多目标优化路由算法MMOR-GA。该算法充分利用基站的存储空间充裕、能量充足和计算能力强的优势,在全局范围内搜索WMSNs多路径多目标优化路由。同时构建了基于前向邻居概念的网络模型和多目标优化函数,设计特定的编码方案及选择、交叉、变异算子。将MMOR-GA和TPGF进行模拟仿真实验,结果表明MMOR-GA算法能均衡有效地提高WMSNs路由的多QoS参数。     

自组织覆盖网络QoS组播动态路由优化研究

针对覆盖组播节点的动态特性,研究自组织覆盖网络带度和延时约束的组播动态路由问题,提出了动态覆盖组播路由算法AHMQ。组播树由目的节点驱动动态渐近形成,动态路由优化在通信过程中进行。协议是软状态的,仅要求节点维护局部状态信息,同时利用覆盖网络技术和无线媒质的广播能力,降低了网络负载,提高了重构能力。对算法进行了分析研究,通过实验验证了该算法具有较好的性能。     

VHDL延时语句的综合算法研究

为了使得综合系统能够自动综合经设计迭代后由反向标注得到的时序信息,同时提高综合结果与模拟结果的时序一致性,对作为时序信息载体的延时语句的综合方法进行了研究,将延时语句考虑为延时约束,并提出了相应调度模型DTC_DFG及其调度算法。采用启发式机制使得调度算法的解空间搜索过程具有跳出局部最优的能力,此算法可在多项式时间复杂度下得到全局最优调度解。实验结果表明,该制度算法不仅能够有效综合延时语句,使得综合结果能够与模拟结果达到较好的一致,而且提供了一种给出延时约束的方便手段,减少了综合过程中的人工干预,极大地提高了设计效率。     

基于强化学习的SDN路由优化算法

针对SDN控制器中网络路由的优化问题,基于强化学习中的PPO模型设计了一种路由优化算法.该算法可以针对不同的优化目标调整奖励函数来动态更新路由策略,并且不依赖于任何特定的网络状态,具有较强的泛化性能.由于采用了强化学习中策略方法,该算法对路由策略的控制相比各类基于Q-learning的算法更为精细.基于Omnet++仿...     

基于锚节点的车载网地理路由算法

车载网络存在节点移动速度快、拓扑结构变化迅速等特点,直接利用全球定位系统(GPS)进行定位存在误差大和路由连通率低等问题。因此现有的基于地理位置的路由算法包递率不高,无法提供可靠路由。提出一种基于锚节点的车载网地理路由算法(GRAN),利用城市路灯作为锚节点,车辆通过锚节点定位自身位置,结合道路网关及中心数据,建立分层次的路由结构。通过这种方式,GRAN去除了路由发现过程及全网广播,达到降低路由开销、提高路由效率和包递率的目的。利用NS-2软件,选取接近现实的城市场景仿真。实验结果证明,与典型的基于地理位置的路由协议如贪婪转发与周边转发相结合的无状态路由(GPSR)和图形源路由(GSR)协议相比,GRAN能以较低的负荷提供较低的平均时延、较高的包递率和吞吐量。     

Improved cat swarm optimization algorithm for solving global optimization problems and its application to clustering

This paper presents a cat swarm optimization (CSO) algorithm for solving global optimization problems. In CSO algorithm, some modifications are incorporated to improve its performance and balance between global and local search. In tracing mode of the CSO algorithm, a new search equation is proposed to guide the search toward a global optimal solution. A local search method is incorporated to improve the quality of solution and overcome the local optima problem. The proposed algorithm is named as Improved CSO (ICSO) and the performance of the ICSO algorithm is tested on twelve benchmark test functions. These test functions are widely used to evaluate the performance of new optimization algorithms. The experimental results confirm that the proposed algorithm gives better results than the other algorithms. In addition, the proposed ICSO algorithm is also applied for solving the clustering problems. The performance of the ICSO algorithm is evaluated on five datasets taken from the UCI repository. The simulation results show that ICSO-based clustering algorithm gives better performance than other existing clustering algorithms.     

基于QPSO的QoS组播路由算法

对带宽、延时、延时抖动约束最小代价的QoS组播路由问题进行了研究，提出一种基于量子行为微粒群优化（QPSO）算法来设计路由优化算法。该算法采用一种节点序列编码方案，将路由优化问题转化成一种准连续优化问题，并采用罚函数处理约束条件。应用QPSO算法求解QoS组播路由问题的算例，并与遗传算法和改进后的遗传算法进行比较。计算机仿真实验证明，该算法可以更有效地求得QoS组播路由问题的优化解，可靠性较高。     

一种快速准确控制复杂路径延时的方法

在深亚微米超大规模集成电路的物理设计中,为达到时序收敛经常遇到复杂路径延时的准确控制问题,提出了一种新的准确控制复杂路径延时方法,并使用布局布线工具Synopsys Astro实现。实验结果表明,该方法比传统的ECO（Engineer Change Order）精度高,收敛速度快,可广泛应用于超大规模集成电路物理设计。     

多拓扑路由实现IP网络区分服务的优化算法*

在IP网络使用多拓扑技术对不同业务区分服务和路由优化的背景下,提出一种改进的链路权重优化启发式算法,在一定条件下以一定概率接受非可行解,从而引入松弛机制扩大候选解范围,避免搜索陷入局部最优。在仿真中将所提出的算法和已有算法进行了比较,结果证明该算法能够为每个高优先级需求的服务层协定（SLA）提供保证,有效降低全网总时延或提高网络吞吐量。     

基于混合策略的QoS选播流路由优化算法

分析了QoS选播流交错服务问题的产生过程及其对网络资源的浪费，提出了一种基于混合策略的全局路由优化解决方法．在构建路由优化问题模型的基础上，得出了选播流路由端到端时延、服务器负载、网络流量、路径调整等多个优化目标和QoS约束的表达式．给出了GA、SA、TS三种算法有机结合形成的一种混合优化算法，并说明了运用该算法求解的关键步骤和实现过程．实验结果表明，本算法能够在满足QoS约束的前提下实现选播路由的多目标组合优化，与基于GA或者SA的求解算法相比具有更强的稳定性和更高的精确度．