用Excel演示Floyd算法

Floyd算法是计算最短路径长度的基本算法之一,若用Excel实现,算法的核心部分只需填写一个公式,比通常的四重循环结构算法简单、直观。     

动态网络中的最短路径改进算法

本文在对动态网络进行理论分析的基础上,指出动态网络中可能出现的非FIFO弧是传统最短路径算法无法求得最优解的原因;通过对非FIFO弧进行理论分析,提出了等待时域和最佳出发时间理论,并将非FIFO弧变换成FIFO弧,给出了改进的Dijkstra算法。对比实验结果证明,该算法可以有效求得动态网络最短路径问题的最优解。     

无标度网络上的队列资源重分配策略

在实际的通信系统中,由于物理条件的限制,每个节点都具有有限长度的队列。研究了在有限队列资源的条件下,队列资源对无标度数据流动力学的影响。提出了一种队列资源重分配策略,策略中节点的队列长度与节点的介数成正比。仿真结果表明,在无标度网络中使用最短路径路由的条件下,所提出的重分配策略可以有效地改进网络的容量。同时对有限队列资源条件下的网络容量进行了理论分析。     

无线传感网络中基于Dijkstra算法的分簇路由

无线传感网络（Wireless Sensor Networks,WSNs）的网络寿命与节点的能耗直接相关。分簇路由是缓解节点能耗速度的有效措施。但是若分簇路由所选择的簇头位置以及数据传输路径的不合理,会加剧节点能量消耗,缩短网络寿命。为此,提出一种基于Dijkstra算法的分簇路由（Clustering Routing-based Dijkstra,CRBD）。CRBD路由先利用节点的剩余能量及离汇聚节点距离信息选择部分节点作为簇头,并禁止拥塞节点担任簇头。利用贪婪启发式算法构建簇。利用Dijkstra算法构建簇头间的最短路径,缓解簇头的能量消耗。仿真结果表明,相比于基于改进萤火虫聚类的能效路由（Energy Efficient Routing based on Improved Firefly Clustering,EIFC）,CRBD路由中节点的平均能耗下降了约12.3%,并且CRBD路由的数据包传递率保持在85%以上。     

基于信息熵TOP SIS法的无线传感器网络节点自定位技术

在无线传感器网络的应用中，节点的定位是一个关键的问题。但是，利用已知节点对未知节点定位的算法存在着定位精度不高，定位计算量大等缺点。针对该问题，提出了一种基于信息熵TOPSIS法的节点自定位算法，该算法利用TOPSIS法按已给的传感器属性进行排序，只取最靠前的3个节点代入标准最小二乘公式中进行计算，既缩短了计算时间，又保证了计算精度。仿真实验证明，该算法是一种有效可行的算法。     

作战体系超网络模型及应用

作战体系是由实体节点、各节点之间的物理、逻辑关系,以及实体节点之间的“流”交互、输送、聚集、融合所构成的复杂系统,基于单一要素的网络模型不能反映作战体系的复杂构成和整体结构。本文从军事需求出发,提出了社会任务—指挥控制—物理资源多层超网络模型,用以反映作战体系的复杂构成及结构形态。并通过形式化描述对网络之间的相互交互与映射关系进行规范,接着对模型应用中的关键技术作了初步探讨,模型为研究军事组织指挥、控制问题提供了一种新的工具和思路。     

基于相遇时间感知的延时容忍网络路由

延时容忍网络(Delay-tolerant Networks,DTNs)是稀疏的移动自组织网络,其无法建立源节点至目的节点整条路径。目前多数工作是在分析转发算法,而基于短相遇接触时间(Contact Duration Time,CDT)事实下的转发算法的研究工作甚少。为此,提出基于相遇接触时间的时延容忍网络路由(Contact Duration-Aware Routing,CDAR)。利用CDT、相遇间隔时间以及消息的时效计算一跳和两跳传递概率,再依据当前接触的和过去接触的节点中选择转发节点,从而构建低成本路由。实验数据表明,与同类的PROPHET路由相比,提出的CDAR路由的消息传递率提高了10%、平均时延缩短了12%和路由成本下降了23%。     

基于多蚁群的无线传感器网络路由算法

无线传感器网络的快速发展,对于其路由协议有了更高的要求,关键是在节省能耗的情况下提高数据传输效率.提出了一种基于多蚁群无线传感器网络路由算法,采用多种群并行搜索,并在种群中采用基于目标函数值得启发式信息素分配策略和根据目标函数自动调整蚂蚁搜索路径,利用蚁群的分布式特点,通过有限寿命蚂蚁的协作在源节点与目的节点之间的运动获取主路径和备选路径,然后根据节点信息适时更新路由表.仿真结果显示MACRA降低了能耗,延长了网络寿命.     

双层智能优化算法求解时变网络最短路径问题

边成本为一般函数的时变网络最短路径问题(TDSP),已被证明不存在多项式时间算法。同时智能优化算法被广泛地用于求解该类问题,但多数没有考虑节点的可等待约束。提出了求解TDSP问题的双层智能优化算法,内层遗传算法优化每条可行路径的各节点离开时间,外层蚁群算法优化构建的路径,最终搜索到从起始点到终点的最短时间路径。实验结果表明:双层智能优化算法能快速寻优,并且收敛速度和最优路径较同类算法更优秀。     

道路网络分层的快速路径诱导算法

路径诱导在现代交通和部队机动过程中具有重要应用,传统路径诱导算法(如Dijkstra算法)具有很高的计算复杂度和搜索空间,所规划路径仅仅是数学意义上的最短路径,很难满足实际道路交通导航诱导要求.为了降低路径诱导算法的搜索空间,同时使得规划的结果更能体现驾驶人员行车偏好,提出一种基于道路网络分层的快速路径诱导算法,在利用道路网络中道路的不同等级特性对路网进行分层处理基础上,通过限制算法搜索区域达到快速路径规划的目的.实验结果表明,该算法解算出导航路径中大部分是由快速路段组成,能很好地满足驾驶人员的选路偏好,路径搜索时间和搜索空间也大大减少.     

时变道路网最短路径算法的研究

道路或区域通行限制在日常交通和部队兵力机动过程中普遍存在。通行限制情况下的最短路径问题属于时变道路网最短路径研究的范畴,对时变道路网最短路径算法及算法效率的研究有着广泛而现实的意义。重点讨论了道路网的模型描述、时变道路网拓扑结构的构建技术,最短路径算法的高效实现等内容,并给出了该算法的应用实例。试验结果显示,该算法有效可行。     

Finding the Kth shortest path in a time‐schedule network

We consider the problem of finding the Kth shortest path for a time‐schedule network, where each node in the network has a list of prespecified departure times, and departure from the node can take place only at one of these departure times. We develop a polynomial time algorithm independent of K for finding the Kth shortest path. The proposed algorithm constructs a map structure at each node in the network, using which we can directly find the Kth shortest path without having to enumerate the first K − 1 paths. Since the same map structure is used for different K values, it is not necessary to reconstruct the table for additional paths. Consequently, the algorithm is suitable for directly finding multiple shortest paths in the same network. Furthermore, the algorithm is modified slightly for enumerating the first K shortest paths and is shown to have the lowest possible time complexity under a condition that holds for most practical networks. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

LEO 卫星网络路径选择策略研究

路由算法在选择路径时,主要考虑传输延迟和跳数这两个因素,分别选取最短延迟路径(Least Delay Path, LDP)或最少跳数路径( Least Hops Path, LHP)。在卫星网络中,基于LHP选径策略实现更加简单,但其应用在LEO卫星网络中合理性的研究成果不多。本文对极轨道LEO卫星网络中,LDP和LHP之间关系进行详细的理论分析,验证了LHP选径策略的合理性。并在此基础上,提出一种基于横向传输优先级（Horizontal Transmitting Priority, HTP）的LHP最短路径选择策略,利用横向链路长短特性简化路径决策流程。通过仿真,该方法能够快速寻找到最短LHP路径,为LEO卫星网络路由算法提供一定的研究基础。     

一种基于节点资源利用率的无标度网络路由策略

本文研究了节点负载处理能力异质条件下的无标度网络交通动力学过程,提出了一种基于节点资源利用率的全局动态路由策略。该策略利用网络中节点资源利用率构建了一种全局代价函数,选择使该代价函数最小的路径来传输负载。实验结果表明该路由策略在略微增加平均路径长度的情况下成倍地提高了网络负载传输能力,与有效路由策略的比较进一步验证了该策略的有效性。     

MANET多路径路由中最大可靠性路径选择算法

如何选择路径的数量和质量对多路径路由机制的性能有着重要的影响。已有的多路径算法没有深入研究如何选择多路径的问题。对目前存在的两个典型问题进行了分析,在此基础上研究了路径可靠性模型和虚拟完全非交叉多路径模型,然后提出一个最大可靠性多路径选择算法。算法利用路径权重作为路径可靠性的近似解决方案,以此克服路径可靠性度量问题(NP难题)研究的复杂性,根据路径可靠性模型和完全非交叉多路径模型来选择可靠的路径集,使用这组路径集并行分布流量。应用OPNET模拟平台实现了算法,结果表明,本算法能增加聚合带宽,优化网络带宽的应用,提高网络的吞吐率和多路径路由的性能。     

网络图的自动生成算法及其系统实现

研究了网络自动生成的实现算法和系统实现技术。该算法按路线来画结点 ,将其区分为不同的层 ,再绘制路径。先画出所有关键路 ,确定关键节点的坐标 ;然后对于未确定坐标的结点 ,寻找其由关键结点出发再回到关键结点的最短路径 ,将该路径上的结点画为一层 ,按不同的路线分为不同的层次进行绘制 ,直到所有结点均确定坐标。然后确定路线的层次 ,最后统一协调规整。以此算法开发的软件系统可节省时间 ,并可保证生成规范的网络图。     

基于动态流能量高效的无线传感网路由算法

针对无线传感网中结点能量受限,提出了一种基于动态流能量高效的路由算法DFEERA(Dynamic Flow-based Energy-Efficient Routing Algorithm)。该算法通过在无线传感网内设置多个基站收集区域内传感器结点的数据流拓扑结构建立数据传输能量消耗模型,将该模型转换为最大流问题求解最优传输路径,作为某时期内结点数据传输路径。随着结点能量的消耗,动态调整该能量消耗模型重新规划路径,作为新的传输路径,从而平衡结点间的能量消耗,提高网络结点的存活率。仿真结果表明,与其他典型的路由算法相比,DFEERA能够更好地平衡结点的能耗,获得更高的能量消耗率和更长的网络生存期。     

分段线性凸费用网络流的两个算法

本文讨论了分段线性凸费用网络流问题,推广了线性费用网络流中的负回路方法和最小费用路方法,从而得到了求分段线性凸费用网络的最小费用流的两个算法。     

Robust shortest path problems with two uncertain multiplicative cost coefficients

We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual‐variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a K ‐shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed, and the solution methods are illustrated by numerical examples. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013