计算机科学

47卷第1期目录

计算机科学. 2020, 47 (1): 0-0.

摘要 ( 155 )

PDF(470KB) ( 735 )

相关文章 | 多维度评价

高性能计算与天文大数据研究综述

汪洋, 李鹏, 季一木, 樊卫北, 张玉杰, 王汝传, 陈国良

计算机科学. 2020, 47 (1): 1-6. doi:10.11896/jsjkx.190900042

摘要 ( 1493 )

PDF(2333KB) ( 3138 )

参考文献 | 相关文章 | 多维度评价

数据是天文学发展的重要驱动。分布式存储和高性能计算(High Performance Computing,HPC)为应对海量天文数据的复杂性、不规则的存储和计算起到推动作用。天文学研究中多信息和多学科交叉融合成为必然,天文大数据已进入大规模计算时代。高性能计算为天文大数据处理和分析提供了新的手段,针对一些传统手段无法解决的问题给出了新的方案。文中根据天文数据分类和特征,以高性能计算为支撑,对天文大数据的数据融合、高效存取、分析及后续处理、可视化等问题进行了研究,总结了现阶段的技术特点,提出了处理天文大数据的研究策略和技术方法,并对天文大数据处理面对的问题和发展趋势进行了探讨。

并行程序设计语言中局部性机制的研究

袁良,张云泉,白雪瑞,张广婷

计算机科学. 2020, 47 (1): 7-16. doi:10.11896/jsjkx.181202409

摘要 ( 723 )

PDF(1560KB) ( 1418 )

参考文献 | 相关文章 | 多维度评价

大规模并行应用程序的性能优化和并行化的关键瓶颈之一在于多核CPU中越来越深和越来越复杂的存储层次。文中系统地分析和总结了当前主要多核CPU和并行程序设计语言中的局部性设计方法,提出了两种局部性,即横向局部性和纵向局部性,从这两种局部性的视角深入分析了当前的主要并行程序设计语言的局部性设计机制,进一步总结对比了其优缺点,并指出了新一代并行程序设计语言应具有的特点,重点提出了新语言应同时综合考虑两种局部性支持的设计机制的研究观点。

基于Python的大规模高性能LBM多相流模拟

徐传福,王曦,刘舒,陈世钊,林玉

计算机科学. 2020, 47 (1): 17-23. doi:10.11896/jsjkx.190500009

摘要 ( 927 )

PDF(2190KB) ( 1946 )

参考文献 | 相关文章 | 多维度评价

Python由于具有丰富的第三方库、开发高效等优点,已成为数据科学、智能科学等应用领域最流行的编程语言之一。Python强调了对科学与工程计算的支持,目前已积累了丰富的科学与工程计算库和工具。例如,SciPy和NumPy等数学库提供了高效的多维数组操作及丰富的数值计算功能。以往,Python主要作为脚本语言,起到连接数值模拟前处理、求解器和后处理的“胶水”功能,以提升数值模拟的自动化处理水平。近年来,国外已有学者尝试采用Python代码实现求解计算功能,并在高性能计算机上开展了超大规模并行计算研究,取得了不错的效果。由于自身特点,高效大规模Python数值模拟的实现和性能优化与传统基于C/C++和Fortran的数值模拟等具有很大的不同。文中实现了国际上首个完全基于Python的大规模并行三维格子玻尔兹曼多相流模拟代码PyLBMFlow,探索了Python大规模高性能计算和性能优化方法。首先,利用NumPy多维数组和通用函数设计实现了LBM流场数据结构和典型计算内核,通过一系列性能优化并对LBM边界处理算法进行重构,大幅提升了Python的计算效率,相对于基准实现,优化后的串行性能提升了两个量级。在此基础上,采用三维流场区域分解方法,基于mpi4py和Cython实现了MPI+OpenMP混合并行;在天河二号超级计算机上成功模拟了基于D3Q19离散方法和Shan-Chen BGK碰撞模型的气液两相流,算例规模达百亿网格,并行规模达1024个结点,并行效率超过90%。

基于十亿亿次国产超算系统的流体力学软件众核适应性研究

李芳,李志辉,徐金秀,范昊,褚学森,李新亮

计算机科学. 2020, 47 (1): 24-30. doi:10.11896/jsjkx.181102176

摘要 ( 689 )

PDF(3218KB) ( 1324 )

参考文献 | 相关文章 | 多维度评价

国产众核处理器提供了两种移植难度相差较大的众核级并行编程语言。不同流体力学软件对众核架构适应性的不同,决定了它们在移植优化过程中适合于不同的编程语言。首先介绍了国产众核处理器的体系结构、编程模型和并行编程语言;然后分析了流体力学软件应用于国产众核处理器存在的挑战性问题,包括隐格式带来的数据相关性、大型稀疏矩阵线性代数方程组求解、多重网格方法和非结构网格等,这些问题限制了软件对众核架构的适应性。文中针对这些难题分别提出了创新的优化算法,并通过理论分析和实验得到了几种典型流体力学软件的众核适应性研究结论。实践证明,多数流体力学软件对国产众核处理器的适应性良好,能够采用OpenACC编译器自动移植,并扩展到百万核并行规模,能保持较高的并行效率。

一种偶数基Cooley-Tukey FFT高性能实现方法

龚彤艳,张广婷,贾海鹏,袁良

计算机科学. 2020, 47 (1): 31-39. doi:10.11896/jsjkx.190900179

摘要 ( 882 )

PDF(2671KB) ( 1732 )

参考文献 | 相关文章 | 多维度评价

快速傅里叶变换(Fast Fourier Transform,FFT)是最重要的基础算法之一,在科学计算、信号处理、图像处理等领域都有着广泛的应用。随着这些应用领域对实时性需求的进一步提高,FFT算法面临着越来越高的性能要求。在现有的FFT算法库中,FFT算法的求解速度和计算精度受到一定程度的限制,而且也少有研究者对偶数基Cooley-Tukey FFT的高性能实现提出相应的优化策略并对技术进行深入研究。基于此,文中提出了一套针对偶数基的Cooley-Tukey FFT的优化策略和方法。首先构建一个SIMD(Single Instruction Multiple Data)友好、支持混合基的蝶形网络,然后根据偶数基旋转因子特性最大限度地降低蝶形计算的复杂度,接着通过SIMD汇编优化、汇编指令重排及选择、寄存器分配策略制定、高性能矩阵转置算法等方法来优化应用,最后实现一个高性能的FFT算法库。目前,最流行、应用最广的FFT有FFTW和Intel MKL。实验结果表明,在X86计算平台上,新提出的这套针对偶数基Cooley-Tukey FFT的技术所实现的FFT算法库的性能全面优于MKL和FFTW。所提出的这套高性能算法优化和实现技术体系,可推广到除偶数基以外的其他基的实现和优化上,为进一步的研究开发工作奠定一定的基础,进而突破FFT算法在硬件平台上的性能瓶颈,实现一套针对特定平台的高性能FFT算法库。

量子计算与不确定性原理

Renata WONG

计算机科学. 2020, 47 (1): 40-50. doi:10.11896/jsjkx.190400432

摘要 ( 644 )

PDF(1494KB) ( 1974 )

参考文献 | 相关文章 | 多维度评价

对量子计算的计算潜力的高度期望源于量子力学的各种特性,如叠加原理、纠缠现象、破坏性和建设性的量子干扰。相对于经典计算,量子计算具有某些假定的优势,例如量子算法的运行速度比经典算法快;但另一方面却似乎存在影响经典算法但不影响量子算法的障碍,障碍之一是传统上归因于Werner Heisenberg的两个不确定性原理。Heisenberg最初制定的不确定性原理涉及用于测量量子系统的非量子仪器必然会对该系统造成影响。这个原理与其后来的发展有所不同,因为后来发现的不确定性所假定的是不交换可观察量在测量方面存在固有的不能精确测量的特性。在目前的技术发展状况以及当前对量子力学的形式表述与诠释的情况下,这两种不确定性皆有可能对量子计算的速度造成不良影响。近年来,针对这两种不确定性原理有了新的研究成果:1)Ozawa对Heisenberg原理提出了修改,将两种不确定性纳入其内进行并列考虑,从而可以减小Heisenberg原理的不确定性程度;2)在考虑到熵不确定性的情况下,Heisenberg不确定性可被视为Hirschmann不确定性的下界,因此除了在测量上的不确定性之外,量子计算还必须考虑来自其他如信息学的不确定性因素。

GSOS算子下共变-异变模拟的公理刻画

李苏婷,张严

计算机科学. 2020, 47 (1): 51-58. doi:10.11896/jsjkx.181102026

摘要 ( 463 )

PDF(1448KB) ( 634 )

参考文献 | 相关文章 | 多维度评价

进程的行为理论是进程演算研究的核心内容之一,其侧重于讨论进程间的行为等价和模拟关系。共变-异变模拟(Covariant-Contravariant Simulation,CC-模拟)的概念是对经典(互)模拟概念的推广,它通过区分动作类型,刻画了规范与实现对系统主动、被动和通讯动作在精化关系中的不同要求。行为关系的(前)同余性和公理刻画是进程演算代数特征的集中体现,它们对规范及实现的分析和推理至关重要。一般而言,行为关系(前)同余性的证明和公理系统的构造需要基于不同进程演算系统的结构化操作语义(Structural Operational Semantics,SOS)分别展开。为了避免这类研究工作中的重复劳动,学术界针对一般化SOS规则形式的元理论开展了研究,GSOS是其中被广泛研究的规则形式之一。文中在考量了动作类型的基础上,基于CC-模拟对GSOS规则形式做出扩充,提出了CC-GSOS规则类型,证明了CC-模拟相对于CC-GSOS算子具有前同余性,并给出了在这些算子下CC-模拟的可靠完备公理系统的一般性构造方法。

基于接触图残基对距离约束的蛋白质结构预测算法

谢腾宇,周晓根,胡俊,张贵军

计算机科学. 2020, 47 (1): 59-65. doi:10.11896/jsjkx.181202395

摘要 ( 618 )

PDF(2519KB) ( 1497 )

参考文献 | 相关文章 | 多维度评价

从头预测是蛋白质结构建模的一种重要方法,该方法的研究有助于人类理解蛋白质功能,从而进行药物设计和疾病治疗。为了提高预测精度,文中提出了基于接触图残基对距离约束的蛋白质结构预测算法(CDPSP)。基于进化算法框架,CDPSP将构象空间采样分为探索和增强两个阶段。在探索阶段,设计基于残基对距离的变异与选择策略,即根据接触图的接触概率选择残基对,并通过片段组装技术对所选择的残基对的邻近区域进行变异;将残基对距离离散化为多个区域并为其分配期望概率,根据期望概率确定是否选择变异的构象,从而增加种群的多样性。在增强阶段,利用基于接触图信息的评分指标,结合能量函数,衡量构象的质量,从而选择较优的构象,达到增强CDPSP近天然态区域采样能力的效果。为了验证所提算法的性能,通过CASP12中的10个FM组目标蛋白质对其进行了测试,并将其与一些先进算法进行比较。实验结果表明,CDPSP可以预测得到精度较高的蛋白质三维结构模型。

基于日志自动机的业务流程混沌活动过滤方法

李娟,方贤文,王丽丽,刘祥伟

计算机科学. 2020, 47 (1): 66-71. doi:10.11896/jsjkx.181102110

摘要 ( 347 )

PDF(1800KB) ( 752 )

参考文献 | 相关文章 | 多维度评价

业务流程事件日志有时包含混沌活动,混沌活动是独立于流程状态且不受流程约束,会随时随地发生的一类活动。混沌活动的存在会严重影响业务流程挖掘的质量,因此过滤混沌活动成为业务流程管理的关键内容之一。目前,混沌活动的过滤方法主要是从事件日志中过滤不频繁行为,以高频优先为基础的过滤方法并不能有效地过滤日志中的混沌活动。为了解决上述问题,提出了一种基于日志自动机和熵的方法来过滤日志中的混沌活动。首先,根据活动的直接前集率和直接后集率计算得到熵值大的可疑混沌活动集;然后,基于事件日志构建日志自动机,利用日志自动机模型计算得到不频繁弧的活动集与日志中熵值大的活动集,对其取交集得到混沌活动集;最后,运用条件发生概率和行为轮廓确定该混沌活动与其他活动之间的依赖关系,从而决定是在日志中完全删除该混沌活动还是保留该混沌活动在日志中的正确位置而删除其他位置的此活动。案例分析验证了该方法的有效性。

基于局部有限搜索的无向图近似最大团快速求解算法

钟茂生,江超,陶兰,何雄,罗远胜

计算机科学. 2020, 47 (1): 72-78. doi:10.11896/jsjkx.181102109

摘要 ( 427 )

PDF(1449KB) ( 1099 )

参考文献 | 相关文章 | 多维度评价

无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。

时间依赖路网上的移动对象K近邻查询算法

张彤,秦小麟

计算机科学. 2020, 47 (1): 79-86. doi:10.11896/jsjkx.181102231

摘要 ( 594 )

PDF(2656KB) ( 1005 )

参考文献 | 相关文章 | 多维度评价

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。

基于差别矩阵和mRMR的分步优化特征选择算法

樊鑫,陈红梅

计算机科学. 2020, 47 (1): 87-95. doi:10.11896/jsjkx.181202320

摘要 ( 529 )

PDF(2161KB) ( 1012 )

参考文献 | 相关文章 | 多维度评价

分类问题普遍存在于现代工业生产中。在进行分类任务之前,利用特征选择筛选有用的信息,能够有效地提高分类效率和分类精度。最小冗余最大相关算法(mRMR)考虑最大化特征与类别的相关性和最小化特征之间的冗余性,能够有效地选择特征子集;但该算法存在中后期特征重要度偏差大以及无法直接给出特征子集的问题。针对该问题,文中提出了结合邻域粗糙集差别矩阵和mRMR原理的特征选择算法。根据最大相关性和最小冗余性原则,利用邻域熵和邻域互信息定义了特征的重要度,以更好地处理混合数据类型。基于差别矩阵定义了动态差别集,利用差别集的动态演化有效去除冗余属性,缩小搜索范围,优化特征子集,并根据差别矩阵判定迭代截止条件。实验选取SVM,J48,KNN和MLP作为分类器来评价该特征选择算法的性能。在公共数据集上的实验结果表明,与已有算法相比,所提算法的平均分类精度提升了2%左右,同时在特征较多的数据集上能够有效地缩短特征选择时间。所提算法继承了差别矩阵和mRMR的优点,能够有效地处理特征选择问题。

融合用户自身因素与互动行为的微博用户影响力计算方法

王新胜,马树章

计算机科学. 2020, 47 (1): 96-101. doi:10.11896/jsjkx.181202253

摘要 ( 482 )

PDF(2085KB) ( 951 )

参考文献 | 相关文章 | 多维度评价

由于微博高影响力用户在商品营销、社会舆论引导等方面起着重要的作用,因此挖掘高影响力用户成为了微博社交网络中的热点研究问题。针对微博用户影响力计算中存在交互行为与用户自身因素分析不全面的问题,提出了微博用户影响力计算方法MBUI-SFIM(Micro-blog userinfluence based on user’s self-factors and interaction computing model)。该方法考虑了微博用户直接影响力和间接影响力两个方面:在用户直接影响力计算中,通过对用户的自身因素如微博用户粉丝数、用户活跃度、近期微博质量等的分析,计算出用户的初始影响力,然后分析用户互动行为如用户的微博可见率、微博用户互动系数,计算出用户传播能力,最后将初始影响力与用户传播能力相结合,基于改进PageRank算法计算出用户直接影响力;在用户间接影响力计算中,通过对用户网络图连接结构进行分析,根据不相邻用户连接路径的不同,将用户间接影响具体分为简单路径、重复路径、复杂路径3种情况进行讨论,从而计算出用户间接影响力。实验结果表明,相比PageRank算法和MR-UIRank算法,所提算法在用户排名准确性上分别提高了14.8%和8.3%。

基于海林格距离和SMOTE的多类不平衡学习算法

董明刚,姜振龙,敬超

计算机科学. 2020, 47 (1): 102-109. doi:10.11896/jsjkx.190600060

摘要 ( 545 )

PDF(2396KB) ( 1610 )

参考文献 | 相关文章 | 多维度评价

数据不平衡现象在现实生活中普遍存在。在处理不平衡数据时,传统的机器学习算法难以达到令人满意的效果。少数类样本合成上采样技术(Synthetic Minority Oversampling Technique,SMOTE)是一种有效的方法,但在多类不平衡数据中,边界点分布错乱和类别分布不连续变得更加复杂,导致合成的样本点会侵入其他类别区域,造成数据过泛化。鉴于基于海林格距离的决策树已被证明对不平衡数据具有不敏感性,文中结合海林格距离和SMOTE,提出了一种基于海林格距离和SMOTE的上采样算法(Based on Hellinger Distance and SMOTE Oversampling Algorithm,HDSMOTE)。首先,建立基于海林格距离的采样方向选择策略,通过比较少数类样本点的局部近邻域内的海林格距离的大小,来引导合成样本点的方向。其次,设计了基于海林格距离的采样质量评估策略,以免合成的样本点侵入其他类别的区域,降低过泛化的风险。最后,采用7种代表性的上采样算法和HDSMOTE算法对15个多类不平衡数据集进行预处理,使用决策树的分类器进行分类,以Precision,Recall,F-measure,G-mean和MAUC作为评价标准对各算法的性能进行评价。实验结果表明,相比于对比算法,HDSMOTE算法在以上评价标准上均有所提升:在Precision上最高提升了17.07%,在Recall上最高提升了21.74%,在F-measure上最高提升了19.63%,在G-mean上最高提升了16.37%,在MAUC上最高提升了8.51%。HDSMOTE相对于7种代表性的上采样方法,在处理多类不平衡数据时有更好的分类效果。

攻击标签信息的堆栈式支持向量机

金耀,徐丽亚,吕慧琳,顾苏杭

计算机科学. 2020, 47 (1): 110-116. doi:10.11896/jsjkx.181001921

摘要 ( 395 )

PDF(1551KB) ( 688 )

参考文献 | 相关文章 | 多维度评价

真实数据集中存在的对抗样本易导致分类器取得较差的分类性能,但如果其能够被合理利用,分类器的泛化能力将得到显著提高。针对现有大部分分类器并没有涉及对抗样本信息的问题,提出一种攻击标签信息的堆栈式支持向量机。该方法从给定的初始数据集中选取一定比例的样本,并攻击所选取样本的标签,使之成为对抗样本,即将样本标签替换成其他不同类型的标签,利用支持向量机训练包含对抗样本的数据集,从而生成对抗支持向量机。计算对抗支持向量机的输出误差相对于输入样本的一阶梯度信息,并将其嵌入到输入样本特征中以更新输入样本。将更新后的样本输入到下一个对抗支持向量机中,并重新训练。以堆栈方式级联一定数目的对抗支持向量机,直至取得最好的分类性能。原理分析与实验结果表明,基于对抗样本的一阶梯度信息不仅提供了分类器输出与输入之间的一种正相关关系,而且为堆栈式支持向量机中的子分类器提供了一种新的堆栈方式,并提高了分类器的整体性能。

基于内容的视频检索综述

胡志军,徐勇

计算机科学. 2020, 47 (1): 117-123. doi:10.11896/jsjkx.190100231

摘要 ( 738 )

PDF(1484KB) ( 3561 )

参考文献 | 相关文章 | 多维度评价

视频是携带信息量最大的媒体,随着抖音短视频等APP的兴起,网络以及数据库的视频数量急剧增加,人工标注的方法已经无法胜任视频检索的任务。视频检索通过提取视频帧的空间特征或者帧与帧之间的时间特征,使得用户能够更客观、更高效地进行视频查找与归类。文中概述了基于内容的视频检索算法,归纳总结了视频检索的一些经典算法,并总结了深度学习在基于内容的视频检索中的研究与应用,最后分析了深度学习在视频检索中的发展前景。

高分辨率SAR图像道路提取综述

周岳勇,程江华,刘通,王洋,陈明辉

计算机科学. 2020, 47 (1): 124-135. doi:10.11896/jsjkx.190100033

摘要 ( 472 )

PDF(2733KB) ( 1429 )

参考文献 | 相关文章 | 多维度评价

在遥感领域,SAR(Synthetic Aperture Radar,SAR)图像道路提取具有很高的研究意义和应用价值,特别是随着SAR成像技术的不断发展、SAR图像分辨率的逐步提高,该课题的研究更加备受关注。然而,从目前的情况看,高分辨率SAR图像的道路提取研究还不够完善,许多低分辨率SAR图像的道路提取方法在处理高分辨图像时并不适用,因此文中归纳总结了高分辨率SAR图像道路提取的一般流程,列举了一些具体的方法,同时有针对性地分析其优缺点和适用范围,指出该研究课题目前存在的主要问题,并展望其发展趋势。

融合三元卷积神经网络与关系网络的小样本食品图像识别

吕永强,闵巍庆,段华,蒋树强

计算机科学. 2020, 47 (1): 136-143. doi:10.11896/jsjkx.181202316

摘要 ( 556 )

PDF(2929KB) ( 1089 )

参考文献 | 相关文章 | 多维度评价

食品识别在食品健康和智能家居等领域获得了广泛关注。目前大部分的食品识别工作是基于大规模标记样本的深度神经网络,这些工作无法有效地识别只有少量样本的类别,因此小样本食品识别是一个亟待解决的问题。目前基于度量学习的小样本识别方法着重于探究样本之间的相似度信息,忽略了类内与类间更加细粒度的区分。学习类内与类间区分信息的主流方法是基于线性度量函数的三元卷积神经网络,然而对于食品图像而言,线性度量函数的鉴别能力不足。为此,引入可学习的关系网络作为三元卷积神经网络的非线性度量函数,进一步提出了一种基于非线性度量的三元神经网络用于小样本食品识别方法。该方法使用三元神经网络学习图像的特征嵌入表示,然后采用鉴别能力更强的关系网络作为非线性度量函数,基于端到端的训练方式来学习类内与类间更加细粒度的区分信息。此外,提出了一种可以使模型训练更加稳定的三元组样本在线采样方案。通过在Food-101,VIREO Food-172和ChineseFoodNet食品数据集上的实验结果可知,相比基于孪生网络的小样本学习方法,所提方法的性能平均提高了3.0%,相比基于线性度量函数的三元神经网络的方法,所提方法的性能平均提升了1.0%。文中还探究了损失函数的阈值、三元组采样的参数和初始化方式对实验性能的影响。

基于多延迟四阶累积量倍频程谱线的腭裂语音咽擦音自动检测算法

何飞,孟雨璇,田维维,王熙月,何凌,尹恒

计算机科学. 2020, 47 (1): 144-152. doi:10.11896/jsjkx.180701349

摘要 ( 432 )

PDF(2133KB) ( 828 )

参考文献 | 相关文章 | 多维度评价

为了实现对腭裂语音咽擦音及正常音节的自动分类检测,通过对腭裂咽擦患者发音特点的研究,提出了基于多延迟四阶累积量倍频程谱线(Fourth-order Cumulant One-third Octave Spectra Line,FTSL)的腭裂语音咽擦音自动检测算法。目前,咽擦音的研究多基于咽擦音的辅音时长及其在频域的能量分布等特征,实现了咽擦音及正常擦音自动检测的其他研究较少。文中实验基于腭裂语音咽擦音的发音特性,通过研究语音信号的多延迟四阶累计量,利用1/3倍频程算法提取特征谱线,实现了腭裂语音咽擦音与正常擦音的自动分类检测。实验提取了200个正常擦音辅音和194个腭裂语音咽擦音辅音的FTSL特征谱线,使用SVM(Support Vector Machine)分类器进行分类,并设计了FTSL谱线与其他传统语音特征的对比实验,进行了充分的分析讨论。实验结果表明,FTSL谱线对咽擦音的自动分类检测正确率高达92.7%,具有较优的性能,能为临床腭咽功能评估提供有效、客观、无创的辅助依据。

一种根据图像能量调整的图像融合方法

李笑宇,高清维,卢一相,孙冬

计算机科学. 2020, 47 (1): 153-158. doi:10.11896/jsjkx.181202437

摘要 ( 443 )

PDF(4248KB) ( 1048 )

参考文献 | 相关文章 | 多维度评价

针对传统图像融合算法无法对能量差异较大的图像取得良好融合效果的问题,文中根据图像的能量划分,利用多尺度变换和稀疏表示相结合的方式分解两幅图像的高低频信号,在低频部分自动调整不同能量图像块的稀疏融合规则,并在高频部分加入一致性检验,从而进一步约束对应局部空间能量MSD系数的复合过程,最后通过小波逆变换重构得到融合图像。使用红外图像、医学图像和多聚焦图像分别进行融合性能的验证,并分析稀疏分解层数和窗口步长等条件对融合效果的影响,最终取得该框架下的最优分解方式,获得了具备优秀的主观效果和客观指标的融合图像。实验结果表明,该算法在对任意两种类型传感器获得的图像进行融合时均能获得更加优秀的融合效果,且不仅局限于某两种图像的融合,其在SF,SSIM和EFQI等客观指标上优于传统融合算法和一般多尺度结合稀疏表示的算法。

环境辅助的多任务混合声音事件检测方法

高利剑,毛启容

计算机科学. 2020, 47 (1): 159-164. doi:10.11896/jsjkx.190200365

摘要 ( 656 )

PDF(1842KB) ( 887 )

参考文献 | 相关文章 | 多维度评价

在混合声音事件检测任务中,不同事件的声音信号相互混杂,从混合语音信号中提取的全局特征无法很好地表达每种单独的事件,导致当声音事件数量增加或者环境变化时,声音事件检测性能急剧下降。目前已存在的方法尚未考虑环境变化对检测性能的影响。鉴于此,文中提出了一种基于多任务学习的环境辅助的声音事件检测模型(Environment-Assisted Multi-Task,EAMT),该模型主要包含场景分类器和事件检测器两大核心部分,其中场景分类器用于学习环境上下文特征,该特征作为事件检测的额外信息与声音事件特征融合,并通过多任务学习方式来辅助声音事件检测,以此提高模型对环境变化的鲁棒性及多目标事件检测的性能。基于声音事件检测领域的主流公开数据集Freesound以及通用性能评估指标F1分数,将所提模型与基准模型(Deep Neural Network,DNN)及主流模型(Convolutional Recurrent Neural Network,CRNN)进行对比,共设置了3组对比实验。实验结果表明:1)相比单一任务的模型,基于多任务学习的EAMT模型的场景分类效果和事件检测性能均有所提升,且环境上下文特征的引入进一步提升了声音事件检测的性能;2)EAMT模型对环境变化具有更强的鲁棒性,在环境发生变化时,EAMT模型事件检测的F1分数高出其他模型2%～5%;3)在目标声音事件数量增加时,相比其他模型,EAMT模型的表现依旧突出,在F1指标上取得了2%～10%的提升。

基于无偏线性最优估计的PET图像重建

王宏霞,徐英婕,赵云波,张文安

计算机科学. 2020, 47 (1): 165-169. doi:10.11896/jsjkx.181202329

摘要 ( 674 )

PDF(2610KB) ( 768 )

参考文献 | 相关文章 | 多维度评价

正电子发射断层成像(Positron Emission Tomography,PET)技术在实体肿瘤的定性诊断和病灶转移的检查中具有举足轻重的作用,因此非常有必要提高PET的成像质量。然而,已有的迭代重建算法基本上都严重依赖于PET的线性模型。考虑到探测器效率、探测系统的几何尺寸、生物组织对光子的衰减以及散射效应等诸多物理因素,该模型无法真实地刻画示踪剂与正弦图数据之间的复杂关系。文中首先提出了一种新的观测模型,通过在原来的线性模型中引入未知输入项来刻画示踪剂与正弦图数据之间的关系。该项由两部分组成:1)系数矩阵,用于进一步描述投影的线性部分;2)未知输入,用于刻画示踪剂的浓度分布和投影数据之间的一些非线性关系。在此新模型的基础上,PET图像重构问题被转化成一个线性无偏的最优估计问题。然后,给出了具有待定增益的线性迭代估计模型,通过将正弦数据向未知输入项的系数矩阵的零空间零域上进行投影,消除了未知输入给线性最优估计带来的困难,借助卡尔曼滤波的设计思路,推导出了前述的估计增益。基于此估计模型,提出了一种基于无偏线性最优估计的重建算法。最后,通过仿真实验,将所提重建算法与期望极大估计算法(Expectation-Maximization reconstruction,EM)、核化的EM算法(Kernel method,KEM)以及基于标准卡尔曼滤波(Kalman Filtering method,KF)的重建算法从均方误差(Mean Square Error,MSE)、信噪比(Signal-Noise-Rate,SNR)两个方面进行了比较。实验结果表明:与其他3种算法相比,所提算法重建的图像具有更大的信噪比、更小的均方误差,视觉上更加清晰,更好地重建了肿瘤的形状和尺寸,因此具有更好的重构质量。

基于非局部相似联合低秩表示的高光谱图像去噪

张显,叶军

计算机科学. 2020, 47 (1): 170-175. doi:10.11896/jsjkx.181202337

摘要 ( 486 )

PDF(4064KB) ( 1006 )

参考文献 | 相关文章 | 多维度评价

高光谱图像(Hyperspectral Images,HSI)在采集过程中常受到多种类型的噪声干扰,会直接影响其在后续应用中的精度,因此HSI的去噪是一项十分重要的预处理过程。低秩表示(Low-Rank Representation,LRR)模型能很好地满足HSI的光谱性质,但该框架下字典的选择尤为重要,在当下仍是一个开放性的问题。同时,典型去噪方法仅考虑了图像的局部相关性,已不能满足去噪要求,非局部相似性在图像中也是不可忽略的。基于LRR,文中提出了一种新的HSI去噪算法。首先,综合考虑噪声的类型,选取具有更全面的噪声判别能力的字典;其次,在对图像分块处理的前提下,通过聚类的方式引入非局部相似信息,将相似的图像块联合起来进行低秩表示。在模拟Indian Pines数据集以及EO-1 Hyperion真实数据集上的实验结果均表明,相较于目前主流的HSI去噪方法,无论是在图像的目视效果还是在模拟数据集的定量评价指标下,所提方法均有显著提升。

自适应匹配追踪图像去噪算法

李桂会,李晋江,范辉

计算机科学. 2020, 47 (1): 176-185. doi:10.11896/jsjkx.181202280

摘要 ( 474 )

PDF(4198KB) ( 913 )

参考文献 | 相关文章 | 多维度评价

针对目前的稀疏去噪算法分解效率低、去噪效果不理想的问题,提出了一种基于自适应匹配追踪的图像去噪算法。该算法首先通过自适应匹配追踪算法求解稀疏系数,然后利用K奇异值分解算法将字典训练成能够有效反映图像结构特征的自适应字典,最后将稀疏系数与自适应字典相结合来重构图像。在重构过程中,将噪声对应的系数去除,最终达到去噪的效果。算法引入Spike-Slab先验来引导稀疏系数矩阵的稀疏性,并利用两个权重矩阵促使去噪模型更加真实。鉴于字典在稀疏算法中的重要性,将自适应字典与DCT冗余字典、Global字典进行比较。实验结果显示,选择自适应字典的去噪结果比传统字典在峰值信噪比上高出约4.5dB;与目前6种主流的稀疏去噪方法相比,文中提出的方法在3种评价指标上均有不同程度的提高,其中峰值信噪比平均提高了约0.76~6.24dB,特征相似度平均提高了约0.012~0.082,结构相似性平均提高了约0.015~0.108。对图像去噪算法进行定性的评价,结果显示所提算法保留了更多的有用信息,视觉效果最佳。实验充分证明了自适应匹配追踪图像去噪算法对图像去噪的有效性和鲁棒性。

基于注意力机制的评论情感分析及情感词检测

李苑,李智星,滕磊,王化明,王国胤

计算机科学. 2020, 47 (1): 186-192. doi:10.11896/jsjkx.181002011

摘要 ( 715 )

PDF(1731KB) ( 1406 )

参考文献 | 相关文章 | 多维度评价

评论情感分析是用户生成内容分析的一个研究热点。评论对象的多样性与评论者用语的随意性,导致评论情感分析成为一个非常具有挑战性的任务。现有方法主要通过预先构建情感词表来计算评论的情感极性,但这类方法无法处理同一个词语在不同语境下情感极性存在差异的问题。针对这一问题,文中提出了一种基于注意力的卷积-递归神经网络模型,对评论的情感极性和词语在不同语境下的情感极性进行了建模。通过结合词语在句子中的上下文语境,所提方法可以将注意力集中在主要情感词周围的一个小范围内,并以一种自适应的方式对情感词的情感极性进行计算,提高了词语情感极性判断的准确率,进而提高了短文本的情感极性准确率。与CRNN,CNN以及基于情感词典的方法相比,所提方法在中文数据集(美团评论、党建评论)和英文数据集(亚马逊商品评论数据集)上都达到了更好的效果。

一种基于注意力机制的中文短文本关键词提取模型

杨丹浩,吴岳辛,范春晓

计算机科学. 2020, 47 (1): 193-198. doi:10.11896/jsjkx.181202261

摘要 ( 1078 )

PDF(1568KB) ( 3227 )

参考文献 | 相关文章 | 多维度评价

关键词抽取技术是自然语言处理领域的一个研究热点。在目前的关键词抽取算法中,深度学习方法较少考虑到中文的特点,汉字粒度的信息利用不充分,中文短文本关键词的提取效果仍有较大的提升空间。为了改进短文本的关键词提取效果,针对论文摘要关键词自动抽取任务,提出了一种将双向长短时记忆神经网络(Bidirectional Long Shot-Term Memory,BiLSTM)与注意力机制(Attention)相结合的基于序列标注(Sequence Tagging)的关键词提取模型(Bidirectional Long Short-term Memory and Attention Mechanism Based on Sequence Tagging,BAST)。首先使用基于词语粒度的词向量和基于字粒度的字向量分别表示输入文本信息;然后,训练BAST模型,利用BiLSTM和注意力机制提取文本特征,并对每个单词的标签进行分类预测;最后使用字向量模型校正词向量模型的关键词抽取结果。实验结果表明,在8159条论文摘要数据上,BAST模型的F1值达到66.93%,比BiLSTM-CRF(Bidirectional Long Shoft-Term Memory and Conditional Random Field)算法提升了2.08%,较其他传统关键词抽取算法也有进一步的提高。该模型的创新之处在于结合了字向量和词向量模型的抽取结果,充分利用了中文文本信息的特征,可以有效提取短文本的关键词,提取效果得到了进一步的改进。

基于SA-BP算法的本体概念语义相似度综合计算

许飞翔,叶霞,李琳琳,曹军博,王馨

计算机科学. 2020, 47 (1): 199-204. doi:10.11896/jsjkx.181202351

摘要 ( 607 )

PDF(1583KB) ( 920 )

参考文献 | 相关文章 | 多维度评价

不同作战部队在指挥信息系统测试评估中建立的指标存在异构问题,导致在信息交互和测试数据共享上存在较大困难。实现指标本体概念的映射和集成,建立一个统一的全局指标本体树可以有效地解决该问题,其中本体概念相似度计算的准确性至关重要。针对现有本体概念相似度计算模型中存在的精度不高的问题,提出了基于模拟退火改进BP(Back Propagation)神经网络(Simulated Annealing Back Propagation,SA-BP)算法的相似度综合计算模型。首先,对经典的基于语义距离、信息内容和概念属性的相似度计算模型进行改进,同时提出了基于概念子节点重合度的相似度计算模型;然后,采用SA-BP算法进行相似度综合计算,避免现有方法中人为确定权重的主观性和简单线性加权的不准确性问题;最后,从某作战部队不同单位建立的各异的指挥信息系统评估指标的本体概念中提取样本数据,对相似度综合计算模型进行训练测试。实验数据表明,相比于PSO-BP计算模型和主成分分析确定权值的线性加权计算模型,基于SA-BP算法的相似度综合计算模型的计算结果与专家评价结果的Pearson相关系数分别提升了0.0695和0.1351,达到了极强相关的一致性。实验数据充分说明,模拟退火算法改进的BP神经网络在训练后可以较好地收敛,在综合计算本体概念相似度时更加准确,从而有效地解决了本体概念集成的关键问题。

基于上下文信息的口语意图检测方法

徐扬,王建成,刘启元,李寿山

计算机科学. 2020, 47 (1): 205-211. doi:10.11896/jsjkx.181202269

摘要 ( 523 )

PDF(2063KB) ( 1411 )

参考文献 | 相关文章 | 多维度评价

近年来,随着人工智能的发展与智能设备的普及,人机智能对话技术得到了广泛的关注。口语语义理解是口语对话系统中的一项重要任务,而口语意图检测是口语语义理解中的关键环节。由于多轮对话中存在语义缺失、框架表示以及意图转换等复杂的语言现象,因此面向多轮对话的意图检测任务十分具有挑战性。为了解决上述难题,文中提出了基于门控机制的信息共享网络,充分利用了多轮对话中的上下文信息来提升检测性能。具体而言,首先结合字音特征构建当前轮文本和上下文文本的初始表示,以减小语音识别错误对语义表示的影响;其次,使用基于层级化注意力机制的语义编码器得到当前轮和上下文文本的深层语义表示,包含由字到句再到多轮文本的多级语义信息;最后,通过在多任务学习框架中引入门控机制来构建基于门控机制的信息共享网络,使用上下文语义信息辅助当前轮文本的意图检测。实验结果表明,所提方法能够高效地利用上下文信息来提升口语意图检测效果,在全国知识图谱与语义计算大会(CCKS2018)技术评测任务2的数据集上达到了88.1%的准确率(Acc值)和88.0%的综合正确率(F1值),相比于已有的方法显著提升了性能。

有限值终态递归神经网络计算

孙明轩,翁丁恩,张钰

计算机科学. 2020, 47 (1): 212-218. doi:10.11896/jsjkx.181001898

摘要 ( 531 )

PDF(2092KB) ( 656 )

参考文献 | 相关文章 | 多维度评价

通常的递归神经网络计算方法采用渐近收敛的网络模型,误差函数渐近收敛于零,理论上需经过无穷长的计算时间才能获得被求解问题的精确解。文中提出了一种终态递归神经网络模型,该网络形式新颖,具有有限时间收敛特性,用于解决时变矩阵计算问题时可使得计算过程快速收敛,且计算精度高。该网络的另一特点是动态方程右端函数值有限,易于实现。首先,分析渐近收敛网络模型在时变计算问题求解方面的缺陷,说明引入终态网络模型的必要性;然后,给出终态网络动态方程,推导出该网络收敛时间的具体表达式。对于时变矩阵逆和广义逆求解,定义一个误差函数,并依据误差函数构造终态递归神经网络进行求解,使计算过程在有限时间内收敛便能得到精确解。在将任意初始位置下的冗余机械臂轨迹规划任务转换为二次规划问题后,利用所提出的神经网络进行计算,得出的关节角轨迹导致末端执行器完成封闭轨迹跟踪,且关节角严格返回初始位置,以实现可重复运动。使用MATLAB/SIMULINK对时变矩阵计算问题和机器人轨迹规划任务分别进行仿真,通过比较分别采用渐近网络模型和终态网络模型时的计算过程与结果可以看出,使用终态网络模型的计算过程收敛快且显著提高了计算精度。对不同时变计算问题的求解体现了所提神经网络的应用背景。

求解函数优化问题的改进布谷鸟搜索算法

李煜,尚志勇,刘景森

计算机科学. 2020, 47 (1): 219-230. doi:10.11896/jsjkx.181102165

摘要 ( 521 )

PDF(3966KB) ( 1128 )

参考文献 | 相关文章 | 多维度评价

在工程优化中,大多问题是连续优化问题,即函数优化问题。针对布谷鸟算法求解函数优化问题时存在的收敛速度慢、求解精度不高和易陷入局部最优等问题,文中提出非线性惯性权重对数递减和随机调整发现概率的布谷鸟搜索算法(Cuc-koo Search Algorithm with Logarithmic Decline of Nonlinear Inertial Weights and Random Adjustment Discovery Probability,DWCS)。首先,在布谷鸟寻窝的路径和位置更新公式中,设计一种随进化迭代次数非线性递减的惯性权重来改进鸟巢位置的更新方式,以协调布谷鸟算法的探索和开发能力;其次,引入随机调整发现概率代替固定值发现概率,使较大和较小的发现概率随机出现,从而有利于平衡算法的全局探索和局部开发能力,加快算法收敛速度,增加种群多样性;最后,分析对数递减参数和随机调整发现概率,选取对数递减最佳参数组合和随机调整发现概率的最佳取值范围,此时,函数的优化效果最好。与BA,CS,PSO,ICS算法相比,所提算法极大地提高了寻优精度,显著地减少了迭代次数,有效地提高了收敛速度和鲁棒性。在16个测试函数中,DWCS均能收敛到全局最优解,证明了DWCS在求解连续复杂函数优化问题上具有较强的竞争力。

采用改进粒子群优化的SVM方法实现中文文本情感分类

王立志,慕晓冬,刘宏岚

计算机科学. 2020, 47 (1): 231-236. doi:10.11896/jsjkx.181102130

摘要 ( 611 )

PDF(1755KB) ( 930 )

参考文献 | 相关文章 | 多维度评价

近年来,随着网络用户量的不断增加,用户评论数量也呈爆炸式增长,伴随而来的是大量可用于参考和深度挖掘的信息,文本情感分类应运而生。分类模型的预测精度和执行速度是衡量模型优劣的关键。使用传统的SVM进行文本情感分类,算法简单,易于实现,但其模型参数决定了分类准确率。针对这种情况,文中将改进粒子群优化算法与SVM分类方法相结合,采用了改进粒子群算法优化的SVM方法对影视剧评论的情感进行了研究分析。首先,通过网络爬虫获取豆瓣电影评论数据,将数据预处理后利用加权word2vec向量化文本信息,将其作为支持向量机可识别的输入;然后,使用自适应惯性递减策略并引入交叉算子来改进粒子群算法,并对SVM模型的损失函数、惩罚参数及核函数的参数进行优化;最后,实现文本的情感分类。在同一数据集上的实验结果表明,所提方法有效规避了传统的情感词典方法受词语顺序和不同语境影响的缺陷及使用卷积出现梯度消失或弥散的问题,同时也克服了粒子群算法易陷入局部最优的不足。相较于其他方法,所提分类模型的执行速度更快,有效地提高了分类准确率。

SDN在车载网中的应用综述

谷晓会,章国安

计算机科学. 2020, 47 (1): 237-244. doi:10.11896/jsjkx.190100178

摘要 ( 439 )

PDF(1660KB) ( 1700 )

参考文献 | 相关文章 | 多维度评价

随着车载应用、移动设备和物联网的快速发展,开发处理车载网大数据的高效架构已成为未来智慧城市关注的重要问题。然而,车载网复杂且不灵活的架构面临一系列挑战,如高移动性、间歇性连接、应用程序的异构性。在这种背景下,软件定义网络(Software Defined Network,SDN)可编程和灵活的网络架构,在有线网络管理和异构无线通信中受到学术界和工业界的广泛关注。在车载网中应用SDN可以提高灵活性、可靠性、可编程性和可扩展性,增强车载网提供应用和服务的能力,提高用户服务质量。文中首先描述了SDN的体系结构,然后从架构和数据传播角度出发概括了软件定义车载网络(Software Defined Vehicular Networks,SDVN)的研究进展,随后概述了结合移动边缘计算(Mobile Edge Computing,MEC)的SDVN研究现状,接着讨论了SDVN存在的问题和挑战,最后介绍了SDVN的应用前景。

高斯干扰下GNSS信号码跟踪精度分析

叶旅洋,樊战友,张瀚青,刘岩,武文俊,胡永辉

计算机科学. 2020, 47 (1): 245-251. doi:10.11896/jsjkx.190100193

摘要 ( 498 )

PDF(4843KB) ( 786 )

参考文献 | 相关文章 | 多维度评价

码跟踪精度是导航系统兼容互操作评估的重要参数。为定量分析高斯干扰下GNSS信号的码跟踪精度,从常见的高斯干扰信号出发,针对CELP,NELP及DP环路模型,基于MATLAB软件对GNSS信号的码跟踪精度进行仿真分析,并给出了NELP及DP环路的CT-SSC表达式,同时对环路模型的CT-SSC及Cramer-Rao下界进行分析。仿真结果表明:在相同条件下,GNSS信号的码跟踪误差受高斯窄带干扰及宽带干扰比较明显,而在一定信干比范围内,受高斯匹配谱干扰和带限白干扰比较稳定;在DP环路下,GNSS信号的CT-SSC三维曲面较CELP及NELP显得“平滑”,相应的跟踪性能也最好。对GNSS信号的码跟踪性能进行分析,有助于给GNSS系统的兼容与互操作评估及现代GNSS接收机的设计提供重要参考;给出的NELP及DP的码CT-SSC表达式,可作为与CELP的CT-SSC进行并行分析的参照依据。

基于合作博弈的认知卫星网络信道分配与上行功率控制算法

钟旭东,何元智,任保全,董飞鸿

计算机科学. 2020, 47 (1): 252-257. doi:10.11896/jsjkx.181202352

摘要 ( 497 )

PDF(2195KB) ( 831 )

参考文献 | 相关文章 | 多维度评价

随着通信业务需求的不断增长,频谱资源的有限性使得卫星通信网络和地面网络都面临着严重的频谱危机。认知无线电技术的出现,使得卫星网络与地面网络共用频率资源以提升网络效用成为可能。文中对认知接入分配给地面网络作为主用户的同一频谱资源的认知卫星网络的功率控制和信道分配问题进行了研究。根据卫星网络和地面网络的特性构建了合理的系统模型,并利用中断概率门限表征了信道估计误差对系统容量的影响。为了保护主基站的通信性能,在考虑信道估计误差、信道资源约束、认知卫星用户最大发射功率和微波基站干扰约束的条件下,根据议价博弈理论设计了优化函数。其次,根据凸优化理论推导了最优发射功率和信道分配的闭式解,并在此基础上设计了一种对偶迭代算法来求解该优化问题。最后,根据卫星网络的特性设置了合理的网络参数,并根据参数利用Matlab仿真平台对提出的算法进行了仿真实验。仿真结果表明:所提方法在不同到达速率的条件下均具备良好的收敛性;信道估计误差会降低网络的总容量;所提方法在波束数多于15个时,相比比例公平性算法容量提升超过50bps/Hz,相比最大容量法公平性能提升超过一倍,因此,相较于这两种方法,该方法能在系统容量和用户间公平性之间获得较好的折中。

一种基于LEACH的低延迟和低功耗的WSN分簇算法

熊成彪,丁洪伟,董发志,杨志军,保利勇

计算机科学. 2020, 47 (1): 258-264. doi:10.11896/jsjkx.190100060

摘要 ( 548 )

PDF(2420KB) ( 810 )

参考文献 | 相关文章 | 多维度评价

针对经典分簇LEACH协议的不足,提出了低延迟、低功耗和网络能耗均匀的改进算法。该算法主要从两个方面对LEACH进行了改进:在稳定数据传输阶段采用CSMA机制,降低了数据传输延迟;在能量均衡和能耗方面,混入小部分初始能量高的高级节点,在簇头选举阶段首先对节点进行能量感知,并综合考虑节点剩余能量和平均能量,从而延长了网络的生命周期。文中首先对LEACH协议进行简单介绍,利用平均周期法对LEACH中使用的CSMA机制进行分析,从而得到了改进算法的延迟计算方法;然后对改进算法的数据传输阶段的能耗和算法复杂度进行分析,并对改进算法的簇头选举阈值的计算进行讨论;最后对改进算法的数据传输阶段的延时和功耗进行建模分析,并利用MATLAB进行仿真对比。仿真结果显示,改进算法使得第一个节点死亡的时间延长了31%,全部节点死亡的时间延长了24.7%,并且网络能耗更加均匀,因此,该算法有效地解决了LEACH中的热区问题,改进了实际WSN应用中节点集中死亡带来的区域信息缺失问题。相比于LEACH,改进算法的数据传输延迟平均降低了78.6%,保证了WSN应用中数据的实时性,因此改进算法在延迟、生命周期、网络能耗均匀性以及吞吐量等性能上都得到了优化提升。

基于交通路网的TASEP模型的扩展研究

阮子瑞,阮中远,沈国江

计算机科学. 2020, 47 (1): 265-269. doi:10.11896/jsjkx.181202418

摘要 ( 388 )

PDF(2160KB) ( 600 )

参考文献 | 相关文章 | 多维度评价

完全非对称的简单排它过程(Totally Asymmetric Simple Exclusion Process,TASEP)模型是一种描述一维晶格上粒子运输的一种经典模型,其主要考虑了粒子之间的体积排斥效应,已被广泛应用到生物、交通等领域。文中主要对传统的TASEP模型进行了扩展研究,结合实际交通网络的结构和特性对TASEP模型进行了如下改进:1)粒子在各条边上的跳跃率是异质的,即设置各条边上的跳跃率不同且符合泊松分布;2)在交叉路口的粒子在选择下一个路段时是非随机的。具体地,设计了一种实时路径策略,结合各个时刻各条边上的流量值与粒子数得到对应边上粒子的平均移动“速度”;在此基础上引入“理性”参数α来控制粒子的路径选择:α的值越大,粒子越倾向于运动到平均速度越快的连边上。结果显示,随着参数α值的增大,网络中粒子的整体运动得到了优化,使得系统的流量有较大的提升,从而可以缓解网络拥塞。文中通过结合复杂网络的概念和方法,对传统TASEP模型做出了两点改进:1)设计出粒子在交叉口处的路径策略优化其行驶路径;2)为研究城市交通流模型提供了新的思路和方向。

基于FAHP与规划图融合的Web服务组合方法

范国栋,祝铭,李静,崔晓柳

计算机科学. 2020, 47 (1): 270-275. doi:10.11896/jsjkx.181102228

摘要 ( 441 )

PDF(1656KB) ( 766 )

参考文献 | 相关文章 | 多维度评价

近年来,随着云计算的发展,越来越多的服务被发布在网上。如何将不同的Web服务组合在一起并使其满足功能性需求和非功能性需求成为了一个研究难点。Web服务质量 (Quality of Service,QoS)感知的Web服务组合问题属于NP难问题。为了解决这个问题,文中提出一种融合FAHP与改进Graphp lan算法的方法(FAHP and Improved Graphplan,FIGP)。首先,根据用户偏好使用模糊分析层生成服务的综合QoS;其次,在Graphplan向前扩展中,使用动态阈值对竞争力较差的服务进行剪枝,在保留关键服务的同时降低了时间复杂度;最后,在Graphplan向后搜索阶段,在满足功能性需求的前提下选择综合QoS最好的服务加入到组合中。实例分析和实验结果表明,与普通的Graphplan,Skyline及其他方法相比,FIGP不仅较好地提高了服务组合的质量,而且显著缩短了程序的执行时间。

基于分布式压缩感知的无线传感器网络异常数据处理

侯明星,亓慧,黄斌科

计算机科学. 2020, 47 (1): 276-280. doi:10.11896/jsjkx.180901667

摘要 ( 442 )

PDF(1537KB) ( 637 )

参考文献 | 相关文章 | 多维度评价

无线传感器网络的海量数据采集、传输和处理,对传感器节点的处理能力和功耗提出了严峻挑战,而且现实环境中传感器故障或者环境因素的突变会导致部分采集数据异常,而传统的数据处理方法无法对包含异常的数据进行有效的处理。针对上述问题,文中提出了两类无线传感器网络的异常数据模型,以及相应的基于分布式压缩感知的异常数据处理方法。通过协同的多个传感器进行数据压缩采样,当多个传感器采集的数据包含异常成分时,分布式压缩感知技术对数据中相同的正常分量进行一次统一重构,仅对不同的异常分量进行单独重构,从而避免了对相同数据分量的重复处理,提高了对包含异常成分数据处理的效率。另外,分布式压缩感知技术充分利用数据间的相关性,可有效减少传感器网络的数据采集量,加强其对抗异常数据的鲁棒性。对两类异常数据模型的数值仿真结果表明:相比于传统的基于单组测量值的压缩感知技术,基于分布式压缩感知技术的数据处理方法在提高异常数据重构准确率的同时,将采样数据量减少了约33%,证明了该方法的有效性。

基于GAN-LSTM的APT攻击检测

刘海波,武天博,沈晶,史长亭

计算机科学. 2020, 47 (1): 281-286. doi:10.11896/jsjkx.181102103

摘要 ( 1235 )

PDF(1508KB) ( 1351 )

参考文献 | 相关文章 | 多维度评价

高级持续性威胁(Advanced Persistent Threat,APT)带来的危害日趋严重。传统的APT检测方法针对的攻击模式比较单一,处理的APT攻击的时间跨度相对较短,没有完全体现出APT攻击的时间序列性,因此当攻击数据样本较少、攻击持续时间较长时准确率很低。为了解决这个问题,文中提出了基于生成式对抗网络(Generative Adversarial Netwokrs,GAN)和长短期记忆网络(Long Short-term Memory,LSTM)的APT攻击检测方法。一方面,基于GAN模拟生成攻击数据,为判别模型生成大量攻击样本,从而提升模型的准确率;另一方面,基于LSTM模型的记忆单元和门结构保证了APT攻击序列中存在相关性且时间间距较大的序列片段之间的特征记忆。利用Keras开源框架进行模型的构建与训练,以准确率、误报率、ROC曲线等技术指标,对攻击数据生成和APT攻击序列检测分别进行对比实验分析。通过生成式模型生成模拟攻击数据进而优化判别式模型,使得原有判别模型的准确率提升了2.84%,与基于循环神经网络(Recurrent Neural Network,RNN)的APT攻击序列检测方法相比,文中方法在检测准确率上提高了0.99个百分点。实验结果充分说明了基于GAN-LSTM的APT攻击检测算法可以通过引入生成式模型来提升样本容量,从而提高判别模型的准确率并减少误报率;同时,相较于其他时序结构,利用LSTM模型检测APT攻击序列有更好的准确率和更低的误报率,从而验证了所提方法的可行性和有效性。

基于深度森林与CWGAN-GP的移动应用网络行为分类与评估

蒋鹏飞, 魏松杰

计算机科学. 2020, 47 (1): 287-292. doi:10.11896/jsjkx.181102118

摘要 ( 576 )

PDF(1774KB) ( 799 )

参考文献 | 相关文章 | 多维度评价

针对目前移动应用数目庞大、功能复杂,并且其中混杂着各式各样的恶意应用等问题,面向Android平台分析了应用程序的网络行为,对不同类别的应用程序设计了合理的网络行为触发事件以模拟网络交互行为,提出了网络事件行为序列,并利用改进的深度森林模型对应用进行分类识别,最优分类准确率可达99.03%,并且其具有高精确率、高召回率、高F1-Score和低训练时间的特点。此外,为了解决应用样本数量有限且数据获取时间开销大等难题,还提出了一种使用CWGAN-GP的数据增强方法。与原始生成对抗网络相比,该模型训练更加稳定,仅需一次训练即可生成指定类别的数据。实验结果表明,在加入生成数据共同训练深度森林模型后,其分类准确率提高了9%左右。

利用基于身份的密码算法+短信验证码的移动安全支付方案

刘亚强,李晓宇

计算机科学. 2020, 47 (1): 293-301. doi:10.11896/jsjkx.181202414

摘要 ( 564 )

PDF(1883KB) ( 3719 )

参考文献 | 相关文章 | 多维度评价

针对移动支付过程中短信验证码被盗导致资金失窃,以及在基于证书的密码体制下建立移动支付系统时移动设备和移动网络面临巨大压力的问题,文中提出了利用基于身份的密码算法+短信验证码的移动安全支付方案。该方案中,用户和银行服务器加入一个基于身份的密码系统,它们不再需要基于数字证书的身份认证,这将大大减小移动设备以及移动网络的存储和计算开销。用户首先到银行柜台注册开通手机银行业务,设置用户名、密码,预留安全问题,在银行工作人员的帮助下完成手机银行APP的首次安装和初始化。登录时,银行服务器对用户进行身份认证,保证用户合法。支付时,手机银行APP利用用户的私钥生成对短信验证码的数字签名,并用银行服务器的公钥对数字签名和短信验证码的组合加密后发送给银行服务器以进行验证,只有银行服务器验证通过后才允许用户支付。在本方案中,短信验证码和数字签名将共同为用户提供安全保证,即使验证码泄露,攻击者也不可能根据验证码生成数字签名,从而保证了移动支付的安全。理论分析和实验结果表明,本方案不但能够大大提高移动支付的安全性,而且随着移动终端的增加,系统的平均响应时间也不会急剧增长,因此所提方案具有较好的健壮性和可行性。

自动纠错CRO PUF密钥生成方案

张向阳,孙子文

计算机科学. 2020, 47 (1): 302-308. doi:10.11896/jsjkx.181202390

摘要 ( 484 )

PDF(1815KB) ( 800 )

参考文献 | 相关文章 | 多维度评价

针对射频识别(Radio Frequency Identification,RFID)安全问题中的加密技术,设计了自动纠错CRO PUF密钥生成方案。该方案将数字通信系统中重复码的纠错思想应用到可配置环形振荡器物理不可克隆函数(Configurable Ring-oscillator Physical Unclonable Function,CRO PUF)结构中,对相邻CRO的最终振荡频率进差行分运算得到3位输出响应值,然后对输出响应值进行纠错处理,得到一位自动纠错CRO PUF输出信息,从而实现CRO PUF电路自动纠错;利用模糊提取器中注册阶段和重构阶段的纠错码编解码技术的纠错特性来纠正复现输出信息向量存在的比特跳变误差,然后使用Hash模块对纠错后的PUF复现输出信息向量进行数据加密以生成密钥。基于Linux系统,利用Cadence virtuoso中specture环境下的TSMCO 0.18um,1.8V CMOS0工艺库对自动纠错CRO PUF电路进行Monte Carlo模拟仿真,使用MATLAB对PUF电路复现输出信息向量进行模糊提取器处理。由仿真实验数据可得,自动纠错CRO PUF电路在电源电压影响下的最高、最低可靠性分别为98.96%和92.71%;在温度影响下的最高、最低可靠性分别为99.10%和93.75%。实验结果表明,相对于CRO PUF电路,自动纠错CRO PUF的可靠性与均匀性有了明显提高;从整体情况看,自动纠错CRO PUF与CRO PUF电路的唯一性没有一方处于明显的优势或劣势,但对两组数据进行方差计算和比较后发现,自动纠错CRO PUF的唯一性与标准值50%之间有着更好的逼近效果。经模糊提取器处理后的PUF复现输出响应向量的可靠性进一步提高,且高达99.8%,其受环境因素干扰非常小,可直接用作密钥。

基于身份标识的特殊数字签名方案及其应用

左黎明,陈兰兰

计算机科学. 2020, 47 (1): 309-314. doi:10.11896/jsjkx.181202416

摘要 ( 594 )

PDF(2038KB) ( 1105 )

参考文献 | 相关文章 | 多维度评价

传统的基于身份标识的密码体制存在着密钥托管问题,当私钥生成器出现安全问题时,易造成整个密码系统瘫痪,因此解决密钥托管问题一直是密码学研究的一个热点。对此,文中提出了一种基于身份标识的特殊数字签名方案,该方案无需可信的第三方介入。首先,在随机预言机模型以及计算性Diffie-Hellman(Computational Diffie-Hellman,CDH)困难问题的假设下,证明了方案的安全性;然后,与几种基于身份的数字签名进行理论上的性能比较和分析;最后,基于PBC(Pairing-Based Cryptography)库,采用C语言实现了签名方案,并对几种签名方案的实际运行效率进行了分析。实验结果表明,文中提出的方案平均总耗时约为0.148s,相比Subhas和Neetu方案的平均总耗时分别减少了约11.9%和13.5%,与Shamir和Boneh方案的耗时接近。因此,所提方案的计算复杂度较低,效率较高,适用于危险品运输监测等数据保护要求较高的应用场景。

基于区块链的环境监测数据安全传输方案

周万锴, 龙敏

计算机科学. 2020, 47 (1): 315-320. doi:10.11896/jsjkx.190100195

摘要 ( 470 )

PDF(1292KB) ( 945 )

参考文献 | 相关文章 | 多维度评价

随着物联网的飞速发展,环境监测系统极大地提高了政府日常运作的效率和透明度。但是,大多数现有的环境监测系统都是以集中的方式提供服务,并且严重依赖人工控制。高度集中的系统架构容易受到外部攻击;此外,不法分子破坏数据真实性相对容易,导致公众对环境监测数据的信任度不高。针对这些问题,文中首先提出一种基于区块链的环境监测数据传输方案,监测设备获取的数据经过签名发送至数据采集终端,数据采集终端验证数据后将其写入区块链,智能合约对公众关心的数据进行实时分析并对外发布结果;其次,提出一种基于分组的PBFT共识算法,以提高系统的可扩展性。文中对方案进行了分析,结果表明,环境监测区块链保障了环境监测数据的安全性、真实性、完整性;同时结合具体案例验证了该方案的可行性。

基于FPGA的7-Zip加密文档高能效口令恢复方法

陈晓杰,周清雷,李斌

计算机科学. 2020, 47 (1): 321-328. doi:10.11896/jsjkx.190100027

摘要 ( 639 )

PDF(2346KB) ( 781 )

参考文献 | 相关文章 | 多维度评价

随着7-Zip压缩软件的广范使用,破解7-Zip加密文档的口令对信息安全有着非常重要的意义。目前,破解7-Zip加密文档主要采用CPU和GPU平台,而潜在的口令空间大,计算复杂度高,在有限的时间内找到正确的口令需要更高性能的计算平台。因此,文中通过分析解密算法的PMC特性,采用可重构的FPGA硬件计算平台,使用流水线技术来实现数据拼接和SHA-256算法,并利用预计算和CSA方法优化SHA-256算法的关键路径,同时使用双端口RAM存储校验数据,从而满足算法的计算需求和存储需求,实现高效能的7-Zip解密算法。实验数据表明,文中提出的优化方法能大幅提升SHA-256算法的性能,使其吞吐量达到110.080Gbps,并且通过多种方法对解密算法进行优化,最终破解10位长度口令的速率达到了10608个/s,是CPU的226倍,GPU的1.4倍,且能效比是GPU的8倍,极大地提升了算法的性能,降低了高功耗需求。