曲线简化中节点重要性度量方法比较及垂比弦法的改进

在曲线简化过程中,一个最基础的问题是如何度量曲线上节点的重要性程度。该文简要回顾了现有的一些节点重要性度量方法,即角度度量法、面积度量法、弧比弦度量法和垂比弦度量法,指出其局限性。结合弧比弦度量法与垂比弦度量法的优点,提出了一种改进的垂比弦度量方法,并给出具体的评价方法。最后,根据曲线简化实验结果,发现相比于弧比弦度量法,改进后的垂比弦度量法选取的节点能较好地保持曲线的形状。

基于RRT算法的移动机器人安全光滑路径生成

在多障碍物复杂工厂环境中,针对快速探索随机树算法(RRT)生成的路径存在冗余点、贴近障碍物且存在锯齿状转折的问题,改进得到了安全-光滑RRT(Safe-SmoothRRT)路径规划算法。首先,引入目标偏置策略;其次,该算法利用融合目标点引力思想的新节点扩展方式以及改进的近邻点度量策略以减少树的盲目扩展,提高生长的目标性;随后,引入节点安全约束,将安全节点加入树中;改进路径简化方法,剔除冗余点的同时兼顾了安全性;最后通过B样条局部平滑来改善路径的平滑性。在MATLAB仿真实验中分别与标准RRT算法、自适应目标偏向性RRT算法和改进RRT算法相比,在平均路径长度方面最大下降了7.1%,在平均有效节点数方面最大下降了64.1%,且所得路径始终与障碍物保持一定的安全距离,结果表明改进算法有效提升了路径的光滑性和安全性。

一种基于相对熵的随机游走相似性度量模型

针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE model(A random walk similarity measure model based on Relative Entropy).首先根据随机游走模型得到网络中节点的转移概率向量,再计算两个节点转移概率向量的相对熵得到该节点对的相似性.由于转移概率向量给出了从一个特定节点出发经过多步随机游走后到达网络其他所有节点的概率,导致网络中的每个节点在计算相对熵的过程中都被等同看待,并且网络规模的增大会使计算得到的节点间相似性耗时更多且存在较大偏差.根据节点经过多步随机游走后到达网络中影响力较大的节点的转移概率来构造该节点的转移概率分布,计算两个节点的转移概率分布的相对熵以得到网络中节点对之间的差异分数,进而得到网络节点间的相似性矩阵.RE model度量方法降低了传统随机游走相似性度量对于大度节点的依赖性.通过在真实网络数据集上的实验表明,RE model算法在对称性、网络传播及社区发现等方面表现良好.

基于Hosoya指标的城市道路拓扑结构重要度评估

为了评价城市路网中每条道路的重要性,借助于拓扑网络结构,提出了一种评价方法。该方法借助对偶拓扑网络动态变化下的节点度量指标,通过Hosoya指标度量删除的节点对拓扑网络连通性的破坏程度,来评价道路重要性,并根据Hosoya指标对节点度量指标下的重要道路集合进行集合运算得到道路重要等级。以武汉市二环与三环间4个局部路网样本为例,发现集合运算后的Hosoya指标低于单一节点度量指标下的Hosoya指标,验证了该方法的有效性,并表明多指标集成相对于单一指标能更好地表达出道路重要性。

一种自组织时间同步网

基于NTP协议构建大规模网络的时间同步网时,必须在网络每一节点上事先进行参数配置,如同步源地址等。这种网络拓扑是静态的,时间同步操作必然会受到网络环境变化的制约和影响。扩展定义两个新的NTP包SRP和SAP,将同步源抽象为一种资源,应用网格计算中的分布式资源发现方法,动态的根据网络环境变化以及节点的能力差异配置参数,进而构成了一种自组织时间同步覆盖网。该方法不仅对于NTP协议的进一步完善研究有参考价值,而且使时间同步更可靠、经济、灵活。

具有稳定链路的改进AODV路由协议

车载自组织网中节点拓扑动态变化,针对节点间链路不稳定从而影响路由性能问题,提出了具有稳定链路的改进AODV路由协议。该协议构造了由车辆间相对速度、转发角度以及节点负载等关键因素组成的节点稳定度(St)参量;以节点度量为基础,引入随机数筛选机制完成中继节点的选择;进一步构造链路质量度量(LQ)参量,选择最优及次优路由提高数据包投递率;在路由修复中,使用断点修复机制完成最优及次优路由间快速切换以及断链修复,降低网络开销及数据传输延迟。仿真表明,AODV-SL在平均端到端时延、数据包分组投递率以及标准化路由开销上都优于AODV及HLAR路由协议。

基于标签传播的蚁群优化算法求解社区发现问题

社区发现问题对于研究复杂网络的特性具有重要作用。蚁群算法由于其采用分布式正反馈并行机制,具有较强的鲁棒性和稳定性,被越来越频繁地应用于社区发现领域。针对蚁群算法求解社区发现存在求解精度低、收敛速度慢的问题,提出一种基于标签传播的蚁群优化算法(BLP_ACO)。采用一种新的解向量表达方式,其中每个节点位置存放该节点所属社区的标签。在解的构造阶段提出基于节点凝聚性的蚂蚁转移策略,降低蚂蚁转移过程中的随机性,从而提高算法的精确度;将标签传播思想引入到蚁群搜索过程,使算法快速收敛。在解的优化阶段采用基于模块度优化的合并策略,进一步提高算法的求解精度;更新信息素时对所有处于社区内部的边滞留信息素。在真实网络和LFR基准网络上验证,结果表明该算法能够准确高效地挖掘出社区结构。