移动卫星网络中的最短路径算法研究

移动卫星网络的拓扑时变性对其最短路径求解带来新的问题。文章利用提出的移动卫星网络模型,证明了基于传统网络的最短路径算法在移动卫星网络中使用存在局限性,提出了一种适用于移动卫星网络的最短路径求解方法和优化算法,并进行了仿真验证。     

动态网络中一种高效的最短路径树维护算法

现有的动态最短路径树算法在某些边的权值频繁变化时,会造成动态网络中的最短路径树频繁更新,而且当网络中的路由器毁坏或增加新的路由器时,该算法难于应用到构造最短路径树中。针对上述问题,提出一种最短路径树的维护算法。对权值频繁变化的边进行处理,避免将其加入到最短路径树中,减少最短路径树的更新次数,当网络中的路由器毁坏或者增加时,通过减少冗余边的入队操作,对网络中的最短路径树进行维护。实验结果表明,与高效的最短路径树动态更新算法相比,该算法的更新时间效率更高。     

卫星时变拓扑网络最短路径算法研究

在提出卫星时变拓扑网络模型的基础上,首先证明了传统网络中的最短路径算法（如Dijkstra算法）在卫星时变拓扑网络中使用存在局限性,给出了一种可适用于卫星时变拓扑网络的最短路径算法并利用卫星节点间邻居关系的相对规律性,对算法进行了优化．相关仿真表明该算法比目前常用的卫星网络路由算法（如DVTR）更适合于切换频繁的卫星网络．     

一个变权路径最优搜索算法

在经典的最短路问题中,诸弧的权是事先给定并固定不变的。但是在最短路径问题的实际应用中,需要求解两点间的最短运行时间或最小费用,这时各路径的权值根据不同情况可能发生变化。本文针对变权路径问题,提出了一个基于知识层次的变权路径最优搜索算法。实验结果很好地验证了算法的有效性。     

基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明: NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。     

基于半边数据结构的最短路径算法及其实现

在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。     

一种综合高效的实时道路导航方案

根据目前道路导航方案以自主车辆型和局部最短路径选择为主的现实,利用GPS技术、分级路由选择算法、移动主机路由选择算法、动态权值修正算法和Dijkstra算法设计了一个综合的道路导航方案.GPS技术实现车辆定位,分级路由选择算法可降低道路的数据复杂性,提高计算机的检索速度,动态权值修正算法可实时修改道路的权值,Dijkstra算法可实现最短路径查找.该方案可实现全国范围内任意两个地点的实时最短路径选择,并能进行实时道路导航.     

量子密钥分发网络端端密钥协商最优路径选择算法

针对量子密钥分发(QKD)网络端端密钥协商路径选择问题,设计了一种基于改进Dijkstra算法的端端密钥协商最优路径选择算法。首先,基于有效路径策略,剔除网络中的失效链路;然后,基于最短路径策略,通过改进Dijkstra算法,得到密钥消耗最少的多条最短路径;最后,基于最优路径策略,从多条最短路径中选择一条网络服务效率最高的最优路径。分析结果表明,该算法很好地解决了最优路径不唯一、最优路径非最短、最优路径非最优等问题,可以降低QKD网络端端密钥协商时密钥消耗量,提高网络服务效率。     

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

基于半空间的最短路径算法模型研究

目前在GIS领域,对最短路径搜索问题的研究和应用较多,其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题.通过对基于Dijkstra最短路径搜索算法的优化途径的分析,提出了基于半空间的最短路径算法,并在VC 环境下设计相应的程序验证了此算法.应用该算法开发了"焦作市地理信息公共查询系统"系统,取得了比较满意的效果.     

一种用于MEO/LEO卫星网络管理的分簇算法

卫星网络是一种新型的无线网络形式,可以看作是一种特殊的ad hoc网络。但由于其本身具有的特殊性质,现有的无线网络管理协议不能高效地应用于卫星网络中。通过引入ad hoc网络中分簇的概念,提出了一种适用于MEO/LEO卫星网络管理的基于地理信息辅助的分簇算法。簇首及管理员由MEO卫星担任,管理代理设置在LEO卫星之上。LEO卫星轨道所处的外层空间被划分成移动的分区,根据结点的密度分区合并为簇,然后在簇内根据组合加权方式选择一个MEO结点作为簇首。该算法考虑了不同层卫星之间的相对移动性及卫星运动的规律性,明确了管理员及管理代理的设置位置,为卫星网络管理提供了一种有价值的研究方法。     

LEO卫星通信网的鲁棒路由算法

针对使用星际链路ISL的LEO卫星系统,许多学者提出基于面向连接结构的路由算法,但这些算法的性能很大程度上依赖于初始路径的建立,健壮性差。该文提出一种基于面向连接结构的增强路由算法,只要源卫星与目的卫星之间存在一条通路,源卫星便可以与目的卫星通信。若源卫星与目的卫星之间存在多条路径,通过该算法一定能在线找到其中的最佳路径。通过仿真实验评价了算法的性能,证明算法比已有的基于面向连接结构的路由算法具有更高的鲁棒性。     

An evolutionary approach towards contact plan design for disruption-tolerant satellite networks

Delay and disruption tolerant networks (DTNs) are becoming an appealing solution for satellite networks where nodes can temporarily store and carry in-transit data until a link with a suitable next-hop becomes available. Since satellite trajectories and orientation can be predicted, on-board routing schemes can base these forwarding decisions on a contact plan comprising all forthcoming communication opportunities. In general, contact plans are previously calculated on ground where their design can be optimized to consider not only available spacecraft resources but also the expected traffic which is largely foreseeable in space applications. Despite optimal contact plan design procedures exist, their computation complexity might result prohibitive even for medium-sized satellite networks. In this work, we propose an evolutionary algorithm to provide sub-optimal yet efficient and implementable contact plans in bounded time. In particular, we depict specific strategies such as encoding and repairing techniques to later evaluate the algorithm performance in a typical scenario demonstrating its usefulness for planning future DTN-based satellite networks.     

分层卫星网络中的接入策略研究

研究了在分层分域卫星网络结构下的用户接入问题,包括网络节点编址、用户位置信息注册和更新、多星接入策略等,通过比较几种单层卫星网络常用的多星接入策略,提出了多层卫星网络的多星接入策略,最后对提出的接入策略在双层卫星网络上进行了仿真分析,得出了接入策略适用于分层卫星网络的结论。     

LEO卫星网QoS遗传算法路由协议

为了满足多媒体应用的QoS要求,卫星路由协议应该更有效地利用网络资源,提供更好的QoS保障。为此提出了一个基于遗传算法的LEO卫星网络QoS路由协议,称为遗传卫星路由协议（GSRP）。改进了新的操作函数,如适应度函数、终止函数,以及变异率和路由表。仿真结果表明,GSRP能够实现较少CBP和HBP的可靠的点对点时延约束,以及比传统的算法更有效的负载平衡。     

基于卫星网的路由算法研究及其伪代码实现

路由问题在通信网中一直是一个核心问题，路由算法的优劣将直接影响到整个通信网络的性能以及通信的质量，在卫星网络中也不例外。由于卫星网络具有区别于地面网络的拓扑结构的动态变化等独有的特点，使得适用于地面网络的路由算法不能用于卫星网络上，因此必须针对卫星网络的特点设计适合于卫星网络的路由算法。本文先阐述了路由算法的影响因素及设计目标，然后提出了一种运行于卫星网络上的基于时空的路由算法，给出了算法的详细步骤，并详细介绍了算法的伪代码实现。实验表明该算法能很好地满足卫星网络的要求。     

动态容量网络中的最小最大时间流问题

动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。     

高分辨卫星图像卷积神经网络分类模型

目的 卫星图像往往目标、背景复杂而且带有噪声,因此使用人工选取的特征进行卫星图像的分类就变得十分困难。提出一种新的使用卷积神经网络进行卫星图像分类的方案。使用卷积神经网络可以提取卫星图像的高层特征,进而提高卫星图像分类的识别率。方法 首先,提出一个包含六类图像的新的卫星图像数据集来解决卷积神经网络的有标签训练样本不足的问题。其次,使用了一种直接训练卷积神经网络模型和3种预训练卷积神经网络模型来进行卫星图像分类。直接训练模型直接在文章提出的数据集上进行训练,预训练模型先在ILSVRC（the ImageNet large scale visual recognition challenge）-2012数据集上进行预训练,然后在提出的卫星图像数据集上进行微调训练。完成微调的模型用于卫星图像分类。结果 提出的微调预训练卷积神经网络深层模型具有最高的分类正确率。在提出的数据集上,深层卷积神经网络模型达到了99.50%的识别率。在数据集UC Merced Land Use上,深层卷积神经网络模型达到了96.44%的识别率。结论 本文提出的数据集具有一般性和代表性,使用的深层卷积神经网络模型具有很强的特征提取能力和分类能力,且是一种端到端的分类模型,不需要堆叠其他模型或分类器。在高分辨卫星图像的分类上,本文模型和对比模型相比取得了更有说服力的结果。     

基于Levenberg-Marquardt算法和最小二乘方法的小波网络混合学习算法

本文针对小波网络现有学习算法的不足,把Levenberg-Marquardt算法(简称LM算法)和最小二乘算法有机地结合在一起,提出了一种新的小波网络混合学习算法.在该混合算法中LM算法用来训练小波网络的非线性参数,而最小二乘算法用来训练线性参数.最后以辩识一个混沌系统为例进行了数值仿真,并与改进的BP算法和单纯LM算法进行了比较,结果说明了所提算法具有很好的收敛性能和收敛速度.