基于Mobius立方体的最短路径路由算法

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

交叉立方体全端口虫洞路由广播算法

交叉立方体(crossed cube)是超立方体(hypercube)的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半。广播通信是并行计算机系统最基本的通信方式。在全端口虫洞模型下,利用递归将交叉立方体分解为互不相交的子交叉立方体的方法,提出了交叉立方体的广播路由算法。其所需时间步为o(n/log2(n 1)),在常数因子范围内是最优的。仿真实验结果进一步说明了算法具有很好的通信性能。     

具有混合故障的超立方体网络中的高效路由

针对容借超立方体网络中的同时具有大量节点和链路故障模式，提出了两类“局部弱连通眇：即缸维局部弱连通性和任意局部弱连通性的概念；并在基于局部弱连通性的基础上，给出了两个满足局部弱连通性条件的超立方体网络的分布式容错路由算法。同时证明了新提出的两个局部弱连通性概念分别是原有的两个局部连通性概念的扩展。     

基于XOR选择重传ARQ的网络编码多播路由算法

针对XOR选择重传ARQ协议,提出了一种基于网络编码的多播路由算法,有效地恢复链路传输错误。该算法分为两种情况：一是信源发送正常的数据包,在信源节点与各接收节点之间建立多播路径族,并考虑不同路径族之间链路的共享;二是信源发送XOR数据包,搜索信源节点到各接收节点的最短路径,并考虑最短路径之间的链路共享。仿真结果表明,该算法有效地提高了网络吞吐量,在资源消耗方面较传统的多播路由算法有更好的表现,非常接近基于网络编码的最小费用多播算法。数学分析表明,该算法的复杂度远小于最小费用多播算法。     

基于Petersen图互连的超立方体网络及其路由算法

提出了一种新型互联网络PGCH(Petersen Graph Connected Hypercube),并对其特性进行了研究。证明了PGCH(k)网络不但具有正则性以及良好的可扩展性,同时还具有比Qk、TQk、CQk、以及HP(k)网络更短的直径和更好的可连接性。另外,还基于PGCH(k)网络分别给出了其上的单播、广播和容错路由算法,证明了其上的单播、广播路由算法的通信效率分别为k-2和k-2.且仿真实验表明,PGCH(k)上的容错路由算法具有良好的容错性能。     

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

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

基于纹理技术生成立方体表面全景图的算法

为了在军事模拟和教育训练等三维场景中有效地使用全景图,提出了采用二维纹理和三维纹理生成立方体全景图的两个模拟算法(立方体全景图是比球面和柱面全景图效果更佳的环境影射).二维纹理模拟算法生成的立方体全景图由同时建立的6个二维正方形纹理数据组成,算法的关键在于解决两个相邻纹理的连续性问题.三维纹理模拟算法首先生成三维立方体纹理数据,进而获取该立方体的6个表面纹理,组成立方体全景图.通过分析比较算法的时间及空间复杂度,得出二维模拟算法优于三维模拟算法的结论.采用两种算法生成的以天空背景为例的全景图能够满足模拟仿真系统的实际需要.     

基于区域不相交的无线传感网任播路由算法

在无线传感器网络(wireless sensor networks, WSN)中采用任播技术可以均衡数据流及能耗。传统算法常采用节点不相交路由策略,但隐终端问题仍会造成任播路径间的传递碰撞。针对该问题,提出基于区域不相交策略的WSN任播路由算法。该算法采用扇形通道技术和基于不同时隙的区域不相交发送策略以减少任播路径传递碰撞问题。仿真实验数据表明,相比较节点不相交路由策略和最短路径优先区域不相交路由策略,本文算法在分组投递成功率和节点平均能耗上具有较好的性能优势,从而提高网络生存期。     

基于带宽剩余率的脉冲耦合神经网络最短路径算法

利用脉冲耦合神经网络（pulse coupled neural network, PCNN）寻找最短路径是一种非确定性算法,运算的复杂度只和最短路径的长度有关,和路径图的复杂程度无关。已有的PCNN最短路径算法只考虑路径长度,而未考虑其他参数,如带宽和时延等。这里除了考虑路径长度,同时考虑实际中带宽剩余量对网络的影响,提出了一种基于带宽剩余率的最短路径算法,用带宽剩余率参数来控制神经元阈值,寻找最短路径。仿真结果表明,该算法可以寻找到全局最优解。     

基于模糊网络环境的一种FSPP算法

讨论了有限支撑的正模糊数表示路径长度的最短路问题,接着基于Harisen的双标准路径问题的多标号法和Dijkstra的最短路算法,提出了模糊网络环境下一种具有有限模糊教的模糊最短路径算法,它以某种扩展原则找到所有非劣路径,这种算法在有圈和无圈的网络上都能使用,因此比常规曩短路径算法更加有效和符合实际.     

基于位置感知的大规模LEO星座分布式路由算法

针对传统星座路由算法应用在大规模低地球轨道(low earth orbit, LEO)星座中, 存在鲁棒性差、资源开销大、路由效率低等缺点。根据卫星运行时的位置可预测特性, 提出了基于位置感知的分布式路由算法。考虑卫星资源受限, 大规模LEO星座具有卫星节点多、动态性大等特点, 基于位置感知提出一种路径预选机制, 初步确定数据包的传输路径。在此基础上, 考虑业务服务质量(quality of service, QoS)需求, 基于状态和传播矢量函数提出一种路径收敛机制, 无重合确定数据包传输主路径和备用路径。理论和仿真结果证明, 相比于传统路由算法, 所提算法降低了路由存储和开销, 随着中断概率的增大, 提高了星座的吞吐量, 降低了端到端时延。     

基于加权路由策略的复杂网络拥塞控制研究

复杂网络的最短路由策略易导致网络吞吐量低,流量分布不均,在关键节点处产生拥塞.本文提出一种基于加权路由策略的拥塞控制机制,用节点的介数作为节点边的权重,将网络变成加权网络,数据包按加权网络最短路径路由.介数的计算采用基于区域中心节点近似估算法,降低了介数计算的复杂度.仿真结果表明,加权路由策略能有效避开拥塞程度严重的节点,克服了介数较大节点成为网络传输瓶颈的问题,显著改善了网络的拥塞情况,提高了网络的吞吐量和传输能力.     

基于超立方体弱连通性质的多态网络研究

针对超立方体互联网络可能出现的链路故障以及实现本地化处理的需要,分析了3类已有的子立方体弱连通性质.通过探讨由于不同的维度序列而产生的多种节点集团,提出了基于子立方体弱连通性质的多态网络及其基本特征.仿真实验表明,所提出的多态网络比基于单一维度序列的网络,更能准确地反映实际存在的满足弱连通性质的节点集团.     

机器人救援的目标吸引动态路径规划蚁群算法

地震发生后城市的道路状况未知而且复杂多变,因此,在震后机器人救援中,如何快速地找到最短路径以拯救更多的伤员,成为研究的热点问题。提出一种目标吸引的动态路径规划蚁群算法,在动态变化的震后救援环境中找到最短路径,减少救援时间。利用原有城市交通地图的全局信息建立目标吸引函数,对蚂蚁在复杂动态环境下的路径搜索进行引导,提高其选择离目标点更近邻节点的概率,减小蚂蚁对非最短路径的选择概率。通过与MMAS算法进行仿真实验对比,验证了提出的算法可以更快地收敛到最短路径并具有较好的动态性能。     

不确定情形下通信网络最短路径关键点问题

在通信网络中，因突发事件造成通信路由节点毁坏或者中断的现象时有发生，传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点，在这种情形下，哪个路由节点中断使得数据包实际行进的总路程最长呢？从通信网络管理的角度来看这是一个非常重要的问题。对该问题．以前的文献都是从确定情形（事先具有节点中断的完全信息）下进行研究的，本文从不确定情形（只有数据包行进到中断节点的邻接点时才获得该节点中断的信息）的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念，给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析，比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题，指出了不确定情形下最短路径关键点问题更具有实际意义。     

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

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

含结点等待费用的离散时变最短路径

研究了结点等待费用、弧费用和弧通过时间均为离散时变函数的最短路径问题.基于动态规划原理,给出了一种标号更新算法,可在O(n3M3)时间复杂度内求出所有结点到指定终点的最小费用路径,其中n为网络结点数、M为时间间隔数.     

一种新的最小干扰选路算法及仿真研究

提出了一种新的最小干扰选路算法 JMIRA,该算法由离线网络优化和在线动态路由选路两部分组成.其中在线路由部分算法采用接纳控制机制,利用最短最窄选路方法定位多条关键链路,根据链路上各业务类型的已用与可用带宽比值来计算链路权重,旨在实现最小干扰目的的同时降低算法的复杂度.经仿真研究表明,该算法在网络可用带宽和请求拒绝率等方面明显优于传统路由选路算法.     

车辆导航系统的动态最优路径搜索方法研究

对车辆导航系统中线路引导信息的供给与需求进行了综合分析,提出了一种新的具有真实最短路径意义的实时动态最优路径,并设计了搜索该路径的改进Ｄｉｊｋｓｔｒａ算法与改进Ａ＾＊算法,前者适用于多车导航,后者适用于单车导航。     

变分辨率的曲面重建算法

在研究平均二次误差与曲面曲率关系的基础上,提出了变分辨率的曲面重建算法。该算法首先在给定的平均二次误差门限下,自适应于曲面曲率大小,将最小立方体包围盒按八叉树结构分割成许多大小不同的立方体,并在立方体内部用Marching cubes（MC）算法进行等值面提取;然后用垂直投影法对大小不同且又相邻的立方体间产生的缝隙进行拼接,并输出最终的网格模型。算法的主要优点是能自动用较大和较小的三角形分别去逼近曲面的小曲率和大曲率区域,不但能够恢复模型的细节,而且大量减少了三角形数目。应用实例表明,算法效果良好。