基于改进蚁群算法的QoS单播路由优化

对现代通信网中具有时延和带宽约束的QoS单播路由问题提出了一种基于改进蚁群算法的路由优化.该算法结合蚁群系统的特点对基本蚁群算法进行了三方面的改进:在信息素初始化中考虑食物源(目的节点)向周围散发气味的过程;将时廷和带宽信息加入启发式函数;引入"弱淘汰"法则全局更新信息素.仿真实验表明该算法可以更快地找到满足时延和带宽请求的最小费用路由.     

基于Mbius立方体的最短路径路由算法

Mbius立方体是超立方体的一种变形结构。Mbius立方体除了具有超立方体本身的可扩展性和路由简单等优点外,它与含有相同数目的点和边的超立方体相比具有更好的性能。文中提出一种新的用于Mbius立方体网络的最短路径路由算法,避免了递归调用。分析和实验证明,相对于Cull P提出的最短路径算法有更高的效率,并易于硬件实现,且时间复杂度为O(n)。     

传感器网络中基于链路层服务的最短路由算法

无线传感器网络中,链路通信质量随时空变化很大,并且有5%-15%的非对称链路存在。链路层服务不但可以发现邻居传感器节点,测量和预测邻居节点间的链路通信质量,而且还提供链路数据转发机制来减轻单向链路对其它协议的影响。利用链路层服务,采用分布式最短路由路径建立算法,为每个传感器节点建立了到汇聚节点的最短路由路径,然后从理论上分析了该算法的性能,最后在无线传感器网络模拟器TOSSIM上进行了模拟。实验结果表明,基于链路层服务的最短路由路径建立算法,不仅可以有效地避免建立断路由路径,还可以充分利用单向链路来建立更短的路由路径,有多于15%的传感器节点建立了更短的路由路径,路由跳数也减少了14%-100%。     

模拟退火算法求解最短路径填挖问题

在大型的工程和建筑项目中，经常要进行场地平整工作。这引出了一个最短路径填挖问题，目标是找到一个最小车辆路径，使得整个施工过程的总运输距离最短。该问题属于NP—hard问题。本文采用模拟退火算法求解该问题。最后通过算例计算，并同贪婪算法的求解结果进行比较，验证了模拟退火算法的高效性。     

基于决策图贝叶斯的多目标QoS组播路由算法

随着实时组播通信需求的不断增长，要求网络能够提供更加严格高效的QoS(Quality of Service)路由保证，需要设计一个能够同时满足不同QoS约束的高效组播路由算法。此问题可归结为图论中的NP(Non-Polymenital)问题，一般方法是把多个QoS参数加权合并为一单目标函数进行优化。提出了一种基于决策图贝叶斯的多目标QoS组播路由算法，算法在不需做预处理的情况下可对多个不同的QoS参数同时进行优化。仿真结果表明，所提出的算法能够快速收敛于一组满足不同QoS约束的非支配解。     

网络中一边长度改变的最短路算法

本文提出了网络中一边长度改变的最短路算法，适合于大型网络中一边或几条边长度改变后各点对之间最短路的校正计算。     

改进A*算法及其在GIS路径搜索中的应用

路径选择在实际运用中主要追求的是最优而不是最短.为此通常采用精度换效率的策略.这种策略虽然在一定程度上达到了路径搜索的任务要求,但如果能在精度和效率之间综合取值的话,效果往往会更令人满意.采用了一种改进的A*算法来实现这一目的.主要是通过变权值的方式来控制算法的搜索精度和搜索效率.实验证明,改进的A*算法可以实现最优路径的选择,且效率有很大的提高.     

基于SDN的卫星网络多QoS目标优化路由算法

针对传统卫星网络中业务类型多样化导致的网络配置复杂和业务服务质量(quality of service, QoS)无法得到有效保障的问题,研究了基于软件定义网络(software-defined networking, SDN)的卫星网络架构,提出了一种能够满足多种QoS需求的自适应路由算法。首先,建立了软件定义卫星网络多约束条件路由选择优化模型;然后,使用拉格朗日松弛法对模型进行松弛处理;最后,使用梯度法进行迭代求解,搜索出满足带宽、时延、丢包率等多种QoS的最优路径。研究结果表明,该优化算法在QoS满意度方面相比近地轨道卫星路由算法提高了64%,在时延满意度和丢包率满意度方面相比软件定义路由算法提高了28%。     

基于动态路径规划的物流仿真控制技术

针对传统的静态路径规划与车间复杂的物流网络不一致的问题,提出了基于动态路径规划的物流仿真控制技术.通过对物流运行过程的分解,建立了基于物流的装载、运输和卸载等动作传感器触发的物流仿真控制逻;利用轨道选择规则和工件选择规则,实现了物流运行的调度控制;以轨道交叉点的计算为基础,利用Dijkstra算法实现了最短路径计算;通过在动态传感器中加入路径规划算法,实现了基于动态路径规划的物流仿真控制.最后通过建立物流仿真模型,验证了上述方法的有效性.     

组播最优QoS划分问题及其混合遗传算法

最优QoS划分研究基于性能的价格体系下的资源分配问题，组播最优QoS划分（MOPQ）是将组播树上端到端QoS要求划分到本地链路，使得总代价最小。研究了求解MOPQ问题的遗传算法，设计了由树代价与叶结点缮罚因子构成的适应度函数，提出了双子群混合遣传算法。该算法充分利用了遗传算法的全局搜索优势，模拟退火算法的局部搜索优势以及双子群的协作优势。仿真结果表明该算法的有效性。     

不确定信息QoS路由的概率遗传算法的研究

QoS路由是保证网络服务质量的重要组件。但网络状态信息具有固有的不确定性,因此有必要研究不确定信息对QoS路由的影响。通过假设网络带宽和时延的分布符合某种随机变量的特点,分别用概率方法表示出带宽和时延的不确定性,然后求出路径满足给定QoS约束的概率,最后在遗传算法的计算过程中,选择合理的适应度函数,找出满足QoS约束的最大概率解。仿真结果表明该方法能够保证得到满意解的同时缩短搜索时间。     

A Heuristic Algorithm for QoS Multicast Routing

In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.     

Shortest Path Routing Algorithm Based on Chaotic Neural Network

A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.     

两种带多约束的组播路由算法

组播对其成员节点能够提供服务质量,且组播在未来通信网络当中起到越来越重要的角色.对多约束斯坦利最小树问题,提出了基于Boruvka方法的多约束组播算法(BMCMRA)与基于Kruskal方法的多约束组播算法(KMCMRA).仿真试验表明算法具有良好代价性能,且能够很好地满足多约束条件.     

QoS路由仿真器的设计与实现

随着QoS路由技术的发展，研究人员不断地提出新的QoS路由算法以满足多媒体业务的服务质量需求。实用的QoS路由算法在应用之前除了严密的理论分析之外，还需要足够的实验来进行实际验证。在没有实际的路由实验环境下，有必要设计性能良好的QoS路由仿真平台进行仿真实验。设计并实现了一个通用的、简单的、开放性强的QoS路由仿真器QRSIM，为QoS路由算法的性能测试构建出真实、准确的仿真平台。对随机网络拓扑生成算法进行了研究，重点分析了QRSIM的总体框架和各功能模块的实现，并给出仿真实例验证了QRSIM的可靠性和有效性。     

基于节点度和边权值比率的网络搜索算法

基于加权网络特性,以Internet网络为例,提出了一种基于节点度和边权值比率(Degree and Weighted Ratio,DWR)的搜索算法.通过理论分析与仿真实验得出:DWR搜索算法在搜索时间和搜索代价上均优于最大度搜索算法和最大局部介数搜索算法.通过数值仿真分析发现,DWR搜索算法的搜索时间随着设置参数的增大而逐渐增大.因此,在Internet网络中,DWR搜索算法既可以提高网络信息传输的速度,又可以增强网络的传输能力.     

基于脉冲耦合神经网络的Live wire新方法的仿真研究

提出了一种基于脉冲耦合神经网络(PCNN)的Live wire分割新方法,Live wire方法是把图像当作一个连通图,在边上定义一个代价函数,然后通过搜索最短路径来找物体的边界,把用户指定的物体边界上的两点之间的最短路径当作物体的边界。最短路径是Live wire方法的重要步骤,本文在介绍脉冲耦合神经网络的基本工作原理和特性的基础上,将改进的脉冲耦合神经网络算法引入到Live wire边缘检测的算法中,用于最短路径算法的研究。并在改进算法中应用路径封锁和在线训练来提高算法的准确性和应用性。     

非线性约束最短路问题的启发式算法

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。     

A New Algorithm for Solving Multicriteria Shortest Path Problem

１　ＩｎｔｒｏｄｕｃｔｉｏｎＭｕｌｔｉｃｒｉｔｅｒｉａｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｉｓａｐａｒｔｉｃｕｌａｒｄｉｓｃｒｅｔｅｌｉｎｅａｒｍｕｌｔｉｏｂｊｅｃｔｉｖｅｐｒｏｂｌｅｍ［１～４］．Ｕｐｔｏｎｏｗ,ｉｔｈａｓｎｏｔｂｅｅｎｗｉｄｅｌｙｓｔｕｄｉｅｄｉｎｌｉｔｅｒａｔｕｒｅ．Ｔｈｅｄｉｆｆｅｒｅｎｃｅｂｅｔｗｅｅｎｍｕｌｔｉｃｒｉｔｅｒｉａｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍａｎｄｔｈｅｃｌａｓｓｉｃａｌｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｉｓｔｈａｔｔｈｅｒｅａｒｅｍｏｒｅ…