一个基于逆向搜索的分布式证书路径构建算法

数字证书的验证是公钥基础设施(PKI)安全实施的关键,PKIX规定证书的验证一般分为证书路径的构建和证书路径的验证这2个步骤,然而标准中对证书路径的构建方法未加阐释,该文在分析了现有证书路径构建算法的基础上,提出了一个基于逆向搜索的分布式证书路径构建算法。     

A Parallel Implementation of the Push-Relabel Algorithm for the Maximum Flow Problem

We describe an efficient parallel implementation of the push-relabel maximum flow algorithm for a shared-memory multiprocessor. Our main technical innovation is a method that allows the "global relabeling" heuristic to be executed concurrently with the main algorithm; this heuristic is essential for good performance in practice. We present performance results from a Sequent Symmetry for five input distributions. On these five input distributions we achieve speedups in the range 6.2-8.8 with 16 processors, relative to the parallel program with 1 processor (4.1-7.2 when compared to our best sequential program). We consider these speedups very good and we provide evidence that hardware effects and insufficient parallelism in certain inputs are the main obstacles to achieving better performance.     

基于随机游走路径的分布式SimRank算法

SimRank算法是一种常用的相似性度量模型,它基于图的拓扑结构信息来衡量任意两个对象之间的相似程度。随着数据规模的不断增大,集中式SimRank算法已不适用,而已有的分布式SimRank算法在运行效率和扩展性等方面存在缺陷。针对上述问题,提出了一种两阶段的基于随机游走路径的分布式SimRank算法。第一阶段基于BSP（bulk synchronous parallel）模型建立随机游走路径索引信息,支持新路径的动态添加,并通过阈值过滤尽可能减少生成路径的数量;第二阶段利用第一阶段生成的索引信息,提出了基于MapReduce的分布式SimRank算法。最后,通过实验验证了算法的可行性和有效性。     

无线传感器网络中的分布式动态路径规划算法

利用无线传感器网络(WSN)根据环境变化为移动主体规划优化路径在实际应用中具有重要意义.针对现有梯度势场算法在动态调整方面的不足,综合考虑路径长度、安全性和通信代价,结合环境因素构造梯度势场函数,提出了一种分布式动态路径规划算法,使网络在环境变化时依据局部信息动态调整梯度势场,为每个节点提供优化路径.仿真结果显示了本文算法可使WSN在环境变化情况下,能够规划出较短路径,有效降低通信代价并灵活处理路径安全性.     

A Log (N) Distributed Mutual Exclusion Algorithm Based on Path Reversal

In this paper, we present a distributed algorithm for mutual exclusion based on path reversal. The algorithm does not use logical clocks to serialize the concurrent events, and all the variables are bounded. When a process invokes a critical section, it sends a request to the tail of a queue. A dynamical rooted tree gives the path to this tail. The algorithm requires onlyO(log(n)) messages on average, wherenis the number of processes in the network. The performance analysis of the algorithm is based on generating formal power series.     

基于最短路径树的分布式功率控制路由算法

当节点不能获知与邻居节点的距离时,为解决节点能量消耗过快而过早失效,从而减少网络生存时间的问题,提出基于最短路径树的分布式功率控制路由算法(DPCRA_SPT)。该算法综合考虑网络中节点间传输数据的能耗和邻居节点的剩余能量,引入新的权值函数和功率线性衰减模型。运用分布式非同步Bellman-Ford算法构建最短路径树,所有节点沿着最短路径树将数据汇集到Sink节点。仿真结果表明:在密集分布的无线传感网中,通过调整参数,DPCRA_SPT算法可以延长网络生存时间,将能耗保持在较低的水平。在一定的条件下,DPCRA_SPT算法比Ratio_w_FTP、BFFTP、BFSAM、BFPAM算法更优。     

A Two-Level Distributed Detection Algorithm of AND/OR Deadlocks

Numerous algorithms on distributed deadlock detection in distributed systems have been proposed for various deadlock models such as the AND model, OR model, and AND/OR model. This paper describes a new distributed algorithm for the AND/OR model by two levels of deadlock detection procedures. In every deadlock model, the existence of a cycle in a wait-for graph is a necessary condition. At the first level of our algorithm, a wait-for cycle is detected with a very simple operation. If no cycle is found, a deadlock does not exist. In this level, deadlocks consisting of AND-requested nodes are detected, and for the cycle of AND- and OR-requested nodes, an initiator is elected and the second-level algorithm is initiated by the initiator. The second-level algorithm uses the deadlock detection method of Herman and Chandy, but the communication cost is reduced even in the worst case because the second-level operation can be initiated by only qualified initiators.     

基于改进PSO-TrICP算法的点云配准

针对传统迭代最近点（Iterative Closest Point,ICP）算法在初始空间位置偏差大时,容易陷入局部最优的问题,提出一种基于改进PSO-TrICP算法的点云配准方法。首先,对传统粒子群（Particle Swarm Optimization,PSO）算法进行改进,引入适应度的相似度测量准则调整粒子的更新方式,然后加入历次迭代的全局最优解的均值作为新的学习因子避免求解过程中出现“早熟”现象;其次用刚性变换参数和点云间的重叠率组成粒子,利用改进PSO算法为配准提供良好的初始相对位置;最后,通过裁剪迭代最近点（Trimmed Iterative Closest Point,TrICP）算法估计点云间的空间变换。实验结果表明,改进PSO-TrICP算法的配准精度与运行效率优于近年提出的同类配准算法,且具有较好的鲁棒性。     

一个适用于分布式系统的快照算法

本文论述一个记录分布式系统状态的快照算法.     

一种支持DiffServ模型的全分布式调度算法

调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combinedinput-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.     

基于分组的分布式节点调度覆盖算法

当部署的传感器节点服从随机分布时,现有的基于分组的节点调度算法不能保证各个组内的节点均匀分布在目标区域.基于以上原因,建立了极大相似分布模型,并提出了极大相似分布的一种近似求解算法:基于分组的分布式节点调度覆盖算法.算法仅需要簇内的节点维持时钟同步,簇之间节点的时钟异步对于覆盖效果的影响可以忽略,因此适用于难以维持整个网络保持时间同步的大型传感器网络.此外,给出了在节点随机分布的条件下,采用分组调度时平均覆盖率的理论上界值.仿真实验表明,提出的这种算法能使各个组内的传感器节点较为均匀地分布在目标区域,获得的平均覆盖率接近于上界值.     

分布式互斥算法的研究与改进

在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法的性能进行分析验证了该算法是高效的,并给出了正确性证明。     

一种面向Agent的分布式路由算法

随着Internet的爆炸式增长,现有的路由算法RIP和OSPF已难以满足用户的多QoS要求。在分析经典分布式路由算法的基础上,提出了一种面向Agent的分布式路由算法。该算法的路径选择策略不是采用“源节点控制算法”,而是依据路由中所得到的时延实测值,由各节点独立地选择下一个节点(最佳节点)。仿真表明该算法是有效的。     

动态路网中基于实时路况信息的分布式路径生成算法

动态路网中的寻路问题在交通诱导和交通流仿真中有重要意义。提出一种基于实时路况信息的分布式路径规划算法,根据安装在道路路口的智能摄像头所采集到的交通参数对路口的畅通程度进行建模,估算车辆在路口间通行需要的时间。当有车辆需要交通诱导时,通过智能摄像头之间的网络进行基于网络路由思想的分布式最短路径寻路,在寻路过程中加入延时发送机制。网络中的智能摄像头根据车辆所在路口的畅通程度和到邻近路口的距离设置一定的延时,来广播路径询问数据包,使数据包能模拟当前的路况,从而有效、迅速地获得路径规划的结果。     

一种多限制路径的预计算路由算法

该文研究了多限制路径选择问题,提出了一种基于有限选择洪泛的源路由预计算的服务质量路由算法。算法通过限制节点保存的优化路径的数目和链路的广播次数降低计算复杂性。计算机仿真表明算法是有效的,可扩展的,并能提供满意的呼叫阻塞性能。     

一类分布式队形控制及其稳定性分析

针对一类具有二阶动态行为的多机器人系统的队形控制问题, 提出了一种分布式离散协同控制算法, 并应用代数图论和矩阵论的方法对该系统的渐近稳定性和算法的一致收敛性进行分析. 应用上述方法, 证明了确保多智能体系统渐近收敛的充要条件,得到了反馈控制参数的取值范围. 同时证明了在该充要条件下多机器人将逐步收敛到期望队形和同一运动速度. 仿真部分通过一个六机器人系统的队形控制验证了本文研究结果的正确性.     

可伸缩分布式动态区间映射算法

提出一种支持权重分布数据的可伸缩分布式动态区间映射算法.该算法能够在存储节点发生变化时,根据可用的资源情况立即重新均衡数据对象分布,从所有存储节点中并行迁移数据对象,且迁移的数据对象数目是最少的.在此基础上提出分布式节点地址计算算法,支持计算节点通过视图校正算法自主学习,自动适应新的系统规模,消除了现有的集中式访问性能瓶颈,使系统具有高可伸缩性.     

基于A*算法的全局路径搜索

解决路径搜索问题有许多算法。本文基于A*算法,选择不同的估价函数进行路径搜索,找出在不同环境下的尽可能优化的路径,确定一种合适的估价函数,解决移动机器人的避障与导航问题。通过VC 6.0程序语言进行仿真实验,验证所选择的路径。     

基于负载均衡和最短路径的异构无线传感器网络成簇算法

针对节点负载不均衡和数据传输距离的问题,提出一种适用于异构网络的基于负载均衡和最短路径的分布式成簇算法DUBP(distributed and unequal clustering algorithm based on load balance and shortest path)。DUBP首先基于节点的能耗因子对网络动态分区,以均衡负载;然后结合网络拓扑结构和图论,利用Floyd算法求出节点间的最短距离作为路径因子;最后以节点的能量因子和路径因子作为辅助参数来竞争簇头,以避免低能量节点担任簇头,节省传输能耗。仿真表明,DUBP算法能显著延长网络寿命,有良好的适应性和能效性。     

结合双语义数据增强与目标定位的细粒度图像分类

细粒度图像分类旨在对属于同一基础类别的图像进行更细致的子类划分,其较大的类内差异和较小的类间差异使得提取局部关键特征成为关键所在。提出一种结合双语义数据增强与目标定位的细粒度图像分类算法。为充分提取具有区分度的局部关键特征,在训练阶段基于双线性注意力池化和卷积块注意模块构建注意力学习模块和信息增益模块,分别获取目标局部细节信息和目标重要轮廓这2类不同语义层次的数据,以双语义数据增强的方式提高模型准确率。同时,在测试阶段构建目标定位模块,使模型聚焦于分类目标整体,从而进一步提高分类准确率。实验结果表明,该算法在CUB-200-2011、FGVC Aircraft和Stanford Cars数据集中分别达到89.5%、93.6%和94.7%的分类准确率,较基准网络Inception-V3、双线性注意力池化特征聚合方式以及B-CNN、RA-CNN、MA-CNN等算法具有更好的分类性能。