计算机科学

47卷第7期目录

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

摘要 ( 330 )

PDF(278KB) ( 679 )

相关文章 | 多维度评价

数据科学导论的课程设计及教学改革

朝乐门

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

摘要 ( 581 )

PDF(1296KB) ( 1592 )

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

数据科学与大数据技术、大数据管理与应用等新兴专业的建设,以及计算机科学与技术、统计学、信息资源管理等传统专业的改革,均需引入一门关键课程——数据科学导论。在调查分析哥伦比亚大学、纽约大学、哈佛大学和中国人民大学等高校开设的具有一定代表性的数据科学导论课程的基础上,作者结合自己开设的数据科学导论课程以及国家同名精品在线开放课程建设的经验,探讨了该课程的教学目的、教学内容、试验操作、考核方法、教材选择、特色与创新等课程设计问题。现阶段已开设的相关课程的教学改革重点在于培养学生的数据能力,重视数据产品的研发,加强课程建设模式的创新,加快与社会人才需求的接轨,凸显其导论类的课程特征,重视编写代码能力的培育和数据沟通能力的训练。

哈密顿图判定问题的多项式时间算法

姜新文

计算机科学. 2020, 47 (7): 8-20. doi:10.11896/jsjkx.191200176

摘要 ( 5874 )

PDF(1760KB) ( 11698 )

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

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP＝P有重要和积极的意义。

一种基于模糊集和概率分布的不确定XML模型及其代数运算

胡磊, 严丽

计算机科学. 2020, 47 (7): 21-30. doi:10.11896/jsjkx.190700164

摘要 ( 529 )

PDF(1635KB) ( 1103 )

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

XML作为一种信息表示和交换的事实标准已被广泛用作不同应用之间的统一数据交换格式,其在实际应用中已经发挥着重要的作用。由于现实中很多信息包含有不确定性,而经典的XML不能表示和处理不确定信息,因此有必要对经典XML模型进行扩展。考虑到现实世界的复杂性,不确定信息往往同时包含有随机不确定性和模糊不确定,而概率理论和模糊集理论是处理不确定信息的有力工具,因此文中在现有的模糊XML和概率XML数据模型的基础上,综合利用概率和模糊理论建立一个新的不确定XML模型和相关代数,所提出的新的不确定性XML模型既能与现有的XML模型兼容,又能表达更复杂的不确定信息。

k元n方体的子网络可靠性研究

冯凯, 李婧

计算机科学. 2020, 47 (7): 31-36. doi:10.11896/jsjkx.190700170

摘要 ( 492 )

PDF(1909KB) ( 877 )

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

k元n方体是并行计算机系统最常用的互连网络拓扑结构之一。为了精确度量k元n方体中子网络的容错能力,研究了概率故障条件下k元n方体中k元(n－1)方体子网络的可靠性。当k(k≥3)为奇整数时,通过厘清k元n方体中不同k元(n－1)方体子网络之间的相交情形,得出了k元(n－1)方体子网络的可靠性的一个下界,并给出了该可靠性的一个近似结果。实验结果表明,得出的近似结果与仿真结果十分接近,并且随着顶点可靠性的降低两者趋于一致。进一步地,提出了在发生点故障的k元n方体中搜寻k元(n－1)方体子网络的算法,并通过实例验证了该算法的有效性。

噪声信道下的盲量子计算

罗文俊, 雷爽

计算机科学. 2020, 47 (7): 37-41. doi:10.11896/jsjkx.190600020

摘要 ( 475 )

PDF(1468KB) ( 859 )

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

盲量子计算(Blind Quantum Computation,BQC)区别于传统的量子计算(Quantum Metrology),它将客户端的计算任务通过量子信道委托给服务器端完成,解放客户端的计算压力,这就要求在信道的传输过程中,量子尽量精确传输。由于量子信道的噪声问题,理想情况下的无噪传输协议是不可能实现的,需要使用量子纠错码(Quantum Error-Correcting Code,QECC)来纠正由噪声信道引起的量子比特翻转和量子相位翻转错误。在盲量子计算协议的基础上,文中针对噪声比特翻转信道和噪声相位翻转信道分别设计抗噪声的盲量子计算协议,客户端通过不同的方式编码量子比特,利用编码后的量子比特传输量子信息给服务器,服务器利用量子纠错码恢复正确的量子信息与客户端完成盲量子计算。协议分析表明,文中提出的两个盲量子计算协议分别在量子比特翻转和量子相位翻转噪声信道中,通过纠错计算达到了盲量子计算协议对于量子尽量精确传输的要求,并且不改变盲量子计算的正确性和盲特性,不会降低量子计算的无条件安全性。最后展望所提协议可以适用于其他量子纠错码。

基于奖励机制的SAT求解器分支策略

沈雪, 陈树伟, 艾森阳

计算机科学. 2020, 47 (7): 42-46. doi:10.11896/jsjkx.190700191

摘要 ( 478 )

PDF(1450KB) ( 994 )

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

分支决策是CDCL(Conflict Driven Clause Learning)求解器一个十分关键的环节,一个好的分支策略可以减少分支决策次数进而提高SAT求解器的效率。目前,先进的分支策略大都结合了冲突分析过程,但分支策略对参与冲突分析的变量奖励方法有所不同,因此所挑选出的决策变量会有所差异。文中考虑到决策变量总是在未赋值变量中选取的这一重要事实,在EVSIDS(Exponential Variable State Independent Decaying Sum)分支策略的基础上提出了一种新的分支策略,称为基于奖励机制的分支策略(简称RACT分支策略)。RACT分支策略对冲突分析中被撤销赋值的变量再次给予奖励,以增大未赋值变量中频繁参与冲突分析的变量被选择为分支变量的可能性。最后,将所提出的分支策略嵌入到Glucose4.1求解器中以形成新的求解器Glucose4.1+RACT,以2017年SAT竞赛中的350个实例为实验数据集来测试RACT分支策略的有效性。实验结果表明,求解器Glucose4.1+RACT比原版求解器能求解出更多的实例个数,尤其在求解可满足实例的个数上增加了13.5％,此外在求解350个竞赛实例上所花费的总时间较Glucose4.1减少了3.9%,以上实验数据均说明所提分支策略可以有效减少搜索树的分支决策次数并给出正确的搜索空间,进而提高了 SAT 求解器的求解能力。

个性化推荐系统技术进展

刘君良, 李晓光

计算机科学. 2020, 47 (7): 47-55. doi:10.11896/jsjkx.200200114

摘要 ( 644 )

PDF(1473KB) ( 2675 )

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

推荐系统通过获取用户的历史行为数据,如网页的浏览数据、购买记录、社交网络信息、用户地理位置等,来推断用户偏好。随着计算机技术的发展,推荐系统所采用的推荐技术由早期的基于用户-项的数据矩阵分解技术为主,逐渐向与数据挖掘、机器学习、人工智能等技术相融合的方向发展,从而深度挖掘用户行为的潜在偏好,以构建更加精准的用户偏好模型。推荐过程也从静态预测发展到实时推荐,通过与用户实时交互来使推荐结果更加丰富。文中重点回顾了推荐系统在不同时期所采用的关键技术,主要包括基于内容过滤的推荐技术、基于协同过滤的推荐技术、基于深度学习的推荐技术、基于强化学习的推荐技术和基于异构网络的推荐技术等。最后对比和分析了关键技术的优缺点,并对推荐系统的未来发展进行展望。

大数据风险访问控制研究进展

王静宇, 刘思睿

计算机科学. 2020, 47 (7): 56-65. doi:10.11896/jsjkx.190700157

摘要 ( 313 )

PDF(1848KB) ( 1198 )

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

大数据访问控制是确保大数据数据安全与信息共享的重要技术之一,但由于传统的访问控制策略无法满足动态环境下访问信息的实时性与动态性,因此在访问控制中引入风险评估方法,以协调访问控制策略,提高访问控制在动态环境中的应用。鉴于此,文中对国内外风险访问控制研究的主要工作进行系统的回顾与总结,分析近年来最新研究成果。首先,分析总结了扩展到传统的访问控制模型和基于XACML框架的访问控制模型的风险访问控制,及其在不同环境中的应用;其次,对风险访问控制的技术与方法进行总结与分析,并且对风险自适应访问控制(Risk-Adaptable Access Control,RAdAC)进行分析与研究;最后,对未来大数据环境下风险访问控制的研究进行了展望,提出一些具有研究价值的问题。文中认为,在未来大数据访问控制研究技术中,基于风险的访问控制仍然是大数据访问控制的重要研究内容。

一种基于块对角表示和近邻约束的子空间聚类方法

高方远, 王秀美

计算机科学. 2020, 47 (7): 66-70. doi:10.11896/jsjkx.190600155

摘要 ( 392 )

PDF(1709KB) ( 1270 )

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

聚类分析是机器学习与数据挖掘中的重要工具,而子空间聚类是高维数据分析中常用的聚类方法。基于谱图的子空间聚类方法首先学习数据在子空间中的自表示系数矩阵,然后基于此进行谱聚类分析。通过研究子空间聚类的过程和模型设计,发现基于子空间的聚类方法存在难以保持数据非线性和局部几何结构的问题。为此,文中提出了一种可以提取非线性结构的子空间聚类方法。首先,使用非线性映射函数将原始数据空间映射到高维的线性空间,利用块对角表示保持子空间的独立性。此外,为了对聚类过程中数据的局部结构进行约束,文中引入了基于拉普拉斯矩阵的流形正则项。然后,采用3种计算拉普拉斯矩阵的方法设计不同的基于流形正则和块对角约束的非线性子空间聚类模型。最后,在不同数据集上的实验结果验证了所提算法的有效性。

基于预处理的超图非负矩阵分解算法

李向利, 贾梦雪

计算机科学. 2020, 47 (7): 71-77. doi:10.11896/jsjkx.200200106

摘要 ( 508 )

PDF(2446KB) ( 974 )

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

随着多媒体技术的发展,信息越来越多的以图片的形式出现。如何对海量的无标签图片进行聚类,是机器学习领域的热点问题。而图像聚类在人脸识别、手写数字识别等领域也有着重要的作用。由于图片数据通常以非负矩阵的形式存储,因此非负矩阵分解算法(NMF)在图像聚类领域得到了广泛的应用。但是NMF算法直接在数据的原始空间进行处理,这就导致NMF算法所得的图片标签易受到数据采集过程中含有的噪声等不利因素的影响。为了解决这些问题,提出了一种基于预处理的超图非负矩阵分解算法(Nonnegative Matrix Factorization with Hypergraph Based on Per-treatments,PHGNMF)。PHGNMF算法将预处理操作和超图的思想引入到NMF算法。在预处理的过程中,使用灰度处理来去除图片中不同光线条件所带来的影响,采用小波分析来提取图片的低时频子图,同时降低了算法所处理的矩阵维度。采取构建超图的方法来进一步保留对聚类结果有重要影响的数据局部结构。最后在5个主流数据集上的实验验证了PHGNMF算法相对于传统算法的有效性,结果显示聚类精度提升了2%～7%,标准互信息在部分数据集上提升了2%～5%。

基于成本对齐的业务流程变化挖掘方法

刘静, 方贤文

计算机科学. 2020, 47 (7): 78-83. doi:10.11896/jsjkx.190600140

摘要 ( 433 )

PDF(1408KB) ( 648 )

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

变化挖掘是业务流程管理的核心,从事件日志中挖掘出业务流程的变化尤为重要。已有对变化挖掘的分析方法大多集中在源模型或目标模型已知的基础上。文中从系统日志的角度提出了一种基于成本最优对齐的业务流程变化挖掘方法。首先,根据事件日志提取出有效的高频形态学发生片段,计算出各迹对齐时的最高成本函数值,并在此基础上发现最优迹对齐;然后,通过度量最优对齐时变化日志与源日志间的相似性度,快速且高效地挖掘出变化集。最后通过实例分析显示了该方法的有效性。

视觉图像显著性检测综述

袁野, 和晓歌, 朱定坤, 王富利, 谢浩然, 汪俊, 魏明强, 郭延文

计算机科学. 2020, 47 (7): 84-91. doi:10.11896/jsjkx.190900006

摘要 ( 1005 )

PDF(2690KB) ( 2025 )

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

当今图像数据呈爆炸式增长,如何利用计算机高效地获取、处理图片信息成为领域内重要的研究课题。在人类视觉注意机制的启发下,研究人员发现将这种机制引入机器图像处理任务中可以大大提高信息提取的效率,从而更好地节省有限的计算资源。视觉图像显著性检测即利用计算机模拟人类的视觉注意机制,对图片中各部分信息的重要程度进行计算。其在图像分割、视频压缩、目标检测、图像索引等领域得到了广泛的应用,有着重要的研究价值。文中介绍了图像显著性检测算法的研究现状,首先以信息驱动来源为切入点,对显著性检测模型进行概述,之后分析了现有几种典型的显著性检测算法,并根据是否基于学习的模型将其分为基于非学习模型、基于传统机器学习模型以及基于深度学习模型3类。针对第一类,文中较为详细地对基于局部对比度和基于全局对比度的显著性检测算法进行了分类比较,指出了各自的优势与不足;针对后两类,分析了机器学习算法及深度学习在显著性检测中的应用。最后对现有的显著性检测算法进行了总结比较,对该领域研究的下一步发展方向进行了展望。

基于半监督深度卷积生成对抗网络的注塑瓶表面缺陷检测模型

谢源, 苗玉彬, 许凤麟, 张铭

计算机科学. 2020, 47 (7): 92-96. doi:10.11896/jsjkx.190700093

摘要 ( 620 )

PDF(2129KB) ( 889 )

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

注塑瓶表面缺陷检测是注塑成型工艺流程中的重要环节,但生产中存在缺陷的注塑瓶样本数量相对匮乏,使得应用深度学习算法进行缺陷检测时容易产生过拟合现象。针对上述问题,文中提出并构建一种半监督(Semi-supervised)深度卷积生成对抗网络(Deep Convolutional Generative Adversarial Network,DCGAN)模型。该模型首先使用HSV(Hue Saturation Va-lue)颜色空间转换与大津算法(Otsu)对原始注塑瓶图像进行预处理得到训练集;然后组合学习任务,使得DCGAN的无监督判别器与注塑瓶表面缺陷检测的监督分类器共享卷积层参数,同时修改损失函数,在DCGAN模型的Wasserstein距离中加入交叉熵;最后使用Adam优化器进行模型训练。实验结果表明,该模型能够准确分辨具有缺陷的注塑瓶样本,分类准确率达到98.65%。与传统的机器学习算法以及采用数据增强的卷积神经网络模型相比,所提模型的分类准确率更高,且较好地避免了过拟合现象,能满足注塑瓶生产中表面缺陷的自动检测需求。

基于标准路牌的车辆自定位

张善彬, 袁金钊, 陈辉, 王玉荣, 王杰, 屠长河

计算机科学. 2020, 47 (7): 97-102. doi:10.11896/jsjkx.190900011

摘要 ( 440 )

PDF(2013KB) ( 1057 )

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

车辆自定位是自动驾驶及高级辅助驾驶的关键技术之一,快速准确的车辆自定位可及时为导航或智能驾驶系统提供自车位置信息。针对自动驾驶和高级辅助驾驶领域中复杂环境下的车辆定位问题,提出了一种基于标准路牌的车辆自定位方法。设计了一个包含标准路牌的简易数据库,该数据库中预存标准路牌的字符、尺寸和控制点坐标等信息。通过车载单目相机采集包含标准路牌的视频流图像,提取标识区域质心坐标为控制点,计算每一帧视频流图像与数据库基准图像之间的平面投影变换矩阵,采用运动约束和矩阵分解求取车载相机的稳定位置。在真实道路环境中对该方法进行实验测试,结果表明,所提方法在30m以内定位精度可以达到0.1m,在20m以内时定位精度可以达到0.05m。该方法成本低、简单可靠,可利用车载单目相机与标准路牌实现车辆在复杂交通路段的精准自定位。

基于自适应多分类器融合的手势识别

刘肖, 袁冠, 张艳梅, 闫秋艳, 王志晓

计算机科学. 2020, 47 (7): 103-110. doi:10.11896/jsjkx.200100073

摘要 ( 438 )

PDF(3637KB) ( 1055 )

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

为了提高基于可穿戴设备手势识别的性能,针对单分类器在手势识别时会出现偏向性的问题,提出了基于自适应多分类器融合的手势识别方法(Self-adaptive Multi-classifiers Fusion,SAMCF)。首先,针对统计特征无法表征复杂手势之间类内变异性和相似性的问题,SAMCF使用卷积神经网络(Convolutional Neural Network,CNN)自动提取具有强表征能力的深度特征;然后,采用多个基本分类器对提取的特征向量进行识别,并通过自适应融合算法决策出最优识别结果,解决了单分类器的偏向性问题;最后,基于数据手套采集的数据集,验证了模型的鲁棒性和泛化能力。实验结果表明,SAMCF能够有效地提取手势的深度特征,解决单分类器的偏向性问题,提高了手势识别的效率,增强了手势识别的性能,对字符级手势(美国手语和阿拉伯数字)识别的准确率达到98.23%,较其他算法平均提高了5%;对单词级手势(中国手语)识别的准确率达到97.81%,较其他算法平均提高了4%。

复杂环境下基于聚类分析的人脸目标识别

高玉潼, 雷为民, 原玥

计算机科学. 2020, 47 (7): 111-117. doi:10.11896/jsjkx.190500004

摘要 ( 256 )

PDF(2560KB) ( 911 )

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

在现代社会,人脸目标识别技术在各大领域应用得越来越广泛;同时,社会治安环境和国际安全问题也愈发严峻,人脸目标识别面临着越来越严峻的挑战。在复杂环境下,检测目标和背景场景都是复杂且动态变化的,传统的人脸目标识别技术已无法满足日益增长的需求。对此,文中通过聚类分析方法对传统SIFT(Scale Invariant Feature Transform)算法进行优化改进,利用聚类分析的原理将对象特征点进行归类,使得聚类结果更加符合设定阈值,从而提高匹配效率。为了验证优化改进后算法的匹配效果,将改进后的算法和传统SIFT算法进行对比检测分析。结果表明,改进后的SIFT算法能够消除无关书籍的干扰,实现图像匹配点的完整连接。为了验证改进算法的有效性,基于几个常用库将其与常用算法进行对比分析,结果显示聚类SIFT算法在CASPEAL-R1,CFP,Multi-PIE方面都要优于其他算法,具有更好的应用效果和适用性。

基于堆叠式双向LSTM的心电图自动识别算法

王文刀, 王润泽, 魏鑫磊, 漆云亮, 马义德

计算机科学. 2020, 47 (7): 118-124. doi:10.11896/jsjkx.190600161

摘要 ( 639 )

PDF(3409KB) ( 1551 )

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

针对日趋增长的心电图数据分析需求,提出了一种新的心电图分类算法。首先对原始数据进行截断固定长度、样本均衡、求取信号的瞬时频率和光谱熵等预处理操作,数据经过预处理后模型能够更好地从其中提取特征进行学习;在训练过程中采用两个双向LSTM(BILSIM)网络堆叠组成的模型,堆叠式的双向LSTM(BILSIM)模型是一种改进的循环神经网络模型,相较于卷积神经网络,循环神经网络更加适合用来处理像心电图这样的序列数据。该模型在Windows下的MATLAB2018b上进行训练和测试,CUDA版本为9.0,采用分类准确率作为衡量模型性能的指标在两个数据集上进行了测试,一个是2017年生理信号挑战赛的数据(下文简称2017数据集),该模型在此数据集上最终分类准确率为97.4%;另一个是2018年生理信号挑战赛的数据(下文简称2018数据集),最终的分类准确率为77.6%,并在所属的MATLAB组获得了第三名的成绩。该算法与传统LSTM网络的结果相比,在2017数据集上提升了5.6%的准确率,在2018数据集上提升了7.6%的准确率;与单层的双向LSTM网络的结果相比,在2017数据集上提升了4.2%的准确率,在2018数据集上提升了5.7%的准确率,这充分验证了该算法的可行性和优势。

基于聚类网络的文本-视频特征学习

张衡, 马明栋, 王得玉

计算机科学. 2020, 47 (7): 125-129. doi:10.11896/jsjkx.190700006

摘要 ( 346 )

PDF(1539KB) ( 667 )

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

综合理解视频内容和文本语义在很多领域都有着广泛的研究。早期的研究主要是将文本-视频映射到一个公共向量空间,然而这种方法所面临的一个问题是大规模文本-视频数据集不足。由于视频数据存在较大的信息冗余,直接通过3D网络提取整个视频特征会使网络参数较多且实时性较差,不利于执行视频任务。为了解决上述问题,文中通过良好的聚类网络聚合视频局部特征,并可以同时利用图像和视频数据训练网络模型,有效地解决了视频模态缺失问题,同时对比了人脸模态对召回任务的影响。在聚类网络中加入了注意力机制,使得网络更加关注与文本语义强相关的模态,从而提高了文本-视频的相似度值,更有利于提高模型的准确率。实验数据表明,基于聚类网络的文本-视频特征学习可以很好地将文本-视频映射到一个公共向量空间,使具有相近语义的文本和视频距离较近,而不相近的文本和视频距离较远。在MPII和MSR-VTT数据集上,基于文本-视频召回任务来测评模型的性能,相比其他模型,所提模型在两个数据集上进行精度均有提升。实验数据表明,基于聚类网络的文本-特征学习可以很好地将文本-视频映射到一个公共向量空间,从而用于文本-视频召回任务。

三维块匹配波域调和滤波图像去噪

吴静, 周先春, 徐新菊, 黄金

计算机科学. 2020, 47 (7): 130-134. doi:10.11896/jsjkx.190600120

摘要 ( 283 )

PDF(3688KB) ( 919 )

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

针对当前图像去噪算法缺乏对整体结构的分析以及运算量过大的不足,提出了一种利用波域调和滤波扩散模型改进BM3D去噪技术的新算法。首先,利用传统的欧氏距离法将相似二维图像块合并,得到三维数组,再将联合滤波后的三维数组进行逆变换,得到图像的预估计数据。其次,通过小波分解变换提取预估计图像中的高频部分进行滤波,为避免边缘模糊,引用拉普拉斯高斯算法构建新算子并将其代入扩散模型。最后,进行小波重构,以得到原始图像的最终逼近,从而均衡运算速度和去噪性能,保护图像完整的结构信息。实验结果表明,新算法的去噪性能优异,内部信息保护更具完整性,运算速度合理,有利于实际应用。

基于注意力机制的复杂场景文本检测

刘燕, 温静

计算机科学. 2020, 47 (7): 135-140. doi:10.11896/jsjkx.190600157

摘要 ( 418 )

PDF(3555KB) ( 1534 )

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

传统的文本检测方法大多采用自下而上的流程,它们通常从低级语义字符或笔画检测开始,然后进行非文本组件过滤、文本行构建和文本行验证。复杂场景中文字的造型、尺度、排版以及周围环境的剧烈变化,导致人的视觉系统是在不同的视觉粒度下完成文本检测任务的,而这些自底向上的传统方法的性能很大程度上依赖于低级特征的检测,难以鲁棒地适应不同粒度下的文本特征。近年来,深度学习方法被应用于文本检测中来保留不同分辨率下的文本特征,但已有的方法在对网络中各层特征提取的过程中没有明确重点特征信息,在各层之间的特征映射中会有信息丢失,造成一些非文本目标被误判,使得检测过程不仅耗时,而且会产生大量误检和漏检。为此,提出一种基于注意力机制的复杂场景文本检测方法,该方法的主要贡献是在VGG16中引入了视觉注意层,在细粒度下利用注意力机制增强网络内全局信息中的显著信息。实验表明,在载有GPU的Ubuntu环境下,该方法在复杂场景文本图片的检测中能保证文本区域的完整性,减少检测区域的碎片化,同时能获得高达87%的查全率和89%的查准率。

基于深度学习的信息级联预测方法综述

张志扬, 张凤荔, 谭琪, 王瑞锦

计算机科学. 2020, 47 (7): 141-153. doi:10.11896/jsjkx.200300130

摘要 ( 706 )

PDF(2128KB) ( 2045 )

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

在线社交媒体极大地促进了信息的产生和传递,加速了海量信息之间的传播与交互,使预测信息级联的重要性逐渐突显。近年来,深度学习已经被广泛用于信息级联预测(Information Cascade Prediction)领域。文中主要对基于深度学习的信息级联预测方法的研究现状与经典算法进行分类、梳理与总结。根据信息级联特征刻画的侧重点不同,将基于深度学习的信息级联预测方法分为时序信息级联预测方法与拓扑信息级联预测方法,并进一步将时序信息级联预测方法分为基于随机游走(Random Walk)的方法与基于扩散路径的方法,将拓扑信息级联预测方法分为基于全局拓扑结构的方法与基于邻域聚合的方法;并对每类方法进行详细的原理阐述与优缺点介绍,介绍了信息级联预测领域常用的数据集与评价指标,在宏观与微观两种信息级联预测场景下对基于深度学习的信息级联预测算法进行实验对比,并讨论了一些信息级联预测算法中常用的算法实现细节。最后,总结了该领域未来可能的研究方向与发展趋势。

基于Levy飞行策略的改进樽海鞘群算法

张严, 秦亮曦

计算机科学. 2020, 47 (7): 154-160. doi:10.11896/jsjkx.190600068

摘要 ( 584 )

PDF(1874KB) ( 924 )

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

针对樽海鞘群算法(Salp Swarm Algorithm,SSA)在寻优过程中存在的收敛速度较慢、容易陷入局部最优的缺点,提出了一种改进的采用莱维飞行策略的条件化更新的樽海鞘群算法(Levy Flight-based Conditional Updating Salp Swarm Algorithm,LECUSSA),并将其运用于分类算法的特征子集选择过程。首先,利用莱维飞行策略的长短跳跃特点对领导者位置进行随机更新,以增强全局最优的搜索能力;其次,增加对追随者位置的更新条件,让追随者不再盲目地跟随,从而加快收敛速度。在23个优化基准函数上对LECUSSA算法与其他算法进行了性能比较实验;并把算法运用到支持向量机(Support Vector Machine,SVM)算法的分类特征子集选择中,采用8个UCI数据集对特征选择后的分类结果进行了性能比较实验。实验结果表明,LECUSSA具有良好的全局最优搜索能力和较快的收敛速度,利用LECUSSA算法进行特征选择后,能够找到最佳分类准确率的特征子集。

蛋白质构象空间的多模态优化算法

李章维, 肖璐倩, 郝小虎, 周晓根, 张贵军

计算机科学. 2020, 47 (7): 161-165. doi:10.11896/jsjkx.190600100

摘要 ( 402 )

PDF(2542KB) ( 941 )

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

蛋白质能量模型的不精确性导致数学上的最优解并不一定对应其稳定的天然态结构,同时其巨大的构象空间使得现有方法也极易收敛到局部最优解。针对蛋白质结构能量模型不精确和高维构象空间采样可靠性低的问题,在进化算法的基础上,提出了一种基于二面角相似度的蛋白质构象多模态优化方法。首先,执行模态探测,将Rosetta粗粒度能量模型作为筛选高质量新个体的标准,进行种群更新,增加种群构象的多样性;然后,建立二面角相似度模型,用于评价不同构象间的相似程度,以满足多模态优化算法中相似个体快速判定的要求,并基于排挤更新策略实现模态增强,获得结构更为合理的构象。10个测试蛋白质的实验结果表明:所提算法能够达到较高的预测精度,并且可以使种群具有良好的模态分布,得到尽可能多的高质量局部极值解,从而获得一些较好的蛋白质亚稳态结构。

基于差分进化的金字塔演化策略求解一维下料问题

侯改, 何朗, 黄樟灿, 王占占, 谈庆

计算机科学. 2020, 47 (7): 166-170. doi:10.11896/jsjkx.190500014

摘要 ( 403 )

PDF(1601KB) ( 891 )

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

一维下料问题是组合优化中一类经典的NP-hard问题,被广泛用于机械制造及工程应用等领域。针对传统群智能算法在求解该类问题时难以平衡种群内部个体及种群之间开采与探索、竞争与协作矛盾的问题,在金字塔演化策略(Pyramid Evolution Strategy,PES)的基础上,提出了求解一维下料问题的基于差分进化的PES算法。该算法充分利用PES算法的优势,很好地解决了以上两个矛盾;但是由于PES算法未考虑种群当前个体与最优个体之间的协作关系,因此其收敛速度较慢。为此,在PES算法的加速过程中引入差分进化的变异、交叉操作,并对产生的不可行试验个体进行修复,使得算法能够充分利用种群个体间的差异信息,这一方面有利于加快算法的收敛速度,另一方面可以实现对新个体附近区域的局部开采,有利于提高算法的求解精度。将提出的算法应用于6组一维下料算例,实验结果表明,与其他8种算法相比,所提算法在求解精度和收敛速度上均有更好的性能表现,验证了该算法求解一维下料问题的可行性和有效性。

基于双估计器的改进Speedy Q-learning算法

郑帅, 罗飞, 顾春华, 丁炜超, 卢海峰

计算机科学. 2020, 47 (7): 179-185. doi:10.11896/jsjkx.190500143

摘要 ( 678 )

PDF(2109KB) ( 693 )

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

Q-learning算法是一种经典的强化学习算法,更新策略由于保守和过估计的原因,存在收敛速度慢的问题。Speedy Q-learning算法和Double Q-learning算法是Q-learning算法的两个变种,分别用于解决Q-learning算法收敛速度慢和过估计的问题。文中基于Speedy Q-learning算法Q值的更新规则和蒙特卡洛强化学习的更新策略,通过理论分析及数学证明提出了其等价形式,从该等价形式可以看到,Speedy Q-learning算法由于将当前Q值的估计函数作为历史Q值的估计,虽然整体上提升了智能体的收敛速度,但是同样存在过估计问题,使得算法在迭代初期的收敛速度较慢。针对该问题,文中基于Double Q-learning算法中双估计器可以改善智能体收敛速度的特性,提出了一种改进算法Double Speedy Q-learning。其通过双估计器,分离最优动作和最大Q值的选择,改善了Speedy Q-learning算法在迭代初期的学习策略,提升了Speedy Q-learning算法的整体收敛速度。在不同规模的格子世界中进行实验,分别采用线性学习率和多项式学习率,来对比Q-learning算法及其改进算法在迭代初期的收敛速度和整体收敛速度。实验结果表明,Double Speedy Q-learning算法在迭代初期的收敛速度快于Speedy Q-learning算法,且其整体收敛速度明显快于对比算法,其实际平均奖励值和期望奖励值之间的差值最小。

求解高维多目标调度的新型人工蜂群算法

郑友莲, 雷德明, 郑巧仙

计算机科学. 2020, 47 (7): 186-191. doi:10.11896/jsjkx.190600089

摘要 ( 335 )

PDF(2027KB) ( 701 )

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

高维多目标连续优化问题已得到广泛研究,而高维多目标组合优化问题的进展相对较小,虽然人工蜂群(Artificial Bee Colony,ABC)算法已成功应用于多种生产调度问题,但很少被用来求解高维多目标调度问题,而且高维多目标调度自身的研究进展也非常小。针对高维多目标柔性作业车间调度问题,文中提出了一种新型ABC算法以同时优化最大完成时间、总延迟时间、总能耗和机器总负荷。与常规柔性作业车间调度问题不同,上述问题考虑了总能耗,使其成为绿色调度问题。新型ABC具有明显不同于现有ABC算法的新特点,其跟随蜂(onlooker bee)的数量小于引领蜂(employed bee),引领蜂侧重于全局搜索,而跟随蜂只进行局部搜索,通过两类蜜蜂彼此各异的搜索方式来避免算法陷入局部最优。同时,该算法将跟随对象限定为质量较好的部分引领蜂和外部档案成员,其他引领蜂无法成为跟随对象,以避免计算资源浪费在较差解的搜索上,并给出了侦查蜂(scout)新的处理策略。测试实例的仿真实验表明,高维多目标调度问题中非劣解数量占种群规模的比例明显低于高维连续优化问题。将新型ABC与多目标遗传算法和变邻域搜索进行比较,实验结果表明,新型ABC在求解高维多目标调度方面比对比算法更有优势,计算结果更好。

基于动态图卷积和空间金字塔池化的点云深度学习网络

朱威, 绳荣金, 汤如, 何德峰

计算机科学. 2020, 47 (7): 192-198. doi:10.11896/jsjkx.190700180

摘要 ( 651 )

PDF(3273KB) ( 1236 )

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

点云数据的分类和语义分割在自动驾驶、智能机器人、全息投影等领域中有着重要应用。传统手工提取点云特征的方式,以及将三维点云数据转化为多视图、体素网格等数据形式后再进行特征学习的方式,都存在处理环节多、三维特征损失大等问题,分类和分割的精度较低。目前可以直接处理点云数据的深度神经网络PointNet忽略了点云的局部细粒度特征,对复杂点云场景的处理能力较弱。针对上述问题,提出了一种基于动态图卷积和空间金字塔池化的点云深度学习网络。该网络在PointNet的基础上使用动态图卷积模块来替换PointNet中的特征学习模块,增强了网络对局部拓扑结构信息的学习能力;同时设计了一种基于点的空间金字塔池化结构来捕获多尺度局部特征,该方式比PointNet++的多尺度采样点云、重复分组进行多尺度局部特征学习的方法更加简洁高效。实验结果表明,在点云分类和语义分割任务的3个基准数据集上,所提网络相较于现有网络具有更高的分类和分割精度。

基于可调Q因子小波变换和迁移学习的癫痫脑电信号检测

罗婷瑞, 贾建, 张瑞

计算机科学. 2020, 47 (7): 199-205. doi:10.11896/jsjkx.200200104

摘要 ( 445 )

PDF(2645KB) ( 900 )

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

针对癫痫脑电信号的检测问题,提出一种基于可调Q因子小波变换和迁移学习的癫痫脑电信号检测方法。首先,对EEG信号进行可调Q因子小波变换,并选择能量差异较大的子带进行部分重构,重排重构信号,将其表示为二维彩色图像数据;其次,通过对现有的癫痫发作自动检测算法和深度可分离卷积网络Xception模型的分析,使用ImageNet数据集分类的预训练模型参数进行网络参数初始化,得到深度可分离卷积网络Xception的预训练模型;最后,利用迁移学习方法将Xception模型的预训练结果迁移至癫痫发作自动检测任务。所提方法在BONN癫痫数据集上的准确度达到99.37%,敏感度达到100%,特异度达到98.48%,证明了该模型在癫痫发作自动检测任务上具有良好的泛化能力。与传统检测方法和其他深度学习方法相比,所提自动检测方法达到了较高的准确率,避免了人工设计和提取特征的过程,具有较好的应用价值。

SDN多控制器放置问题研究综述

贾吾财, 吕光宏, 王桂芝, 宋元隆

计算机科学. 2020, 47 (7): 206-212. doi:10.11896/jsjkx.200200075

摘要 ( 325 )

PDF(1964KB) ( 982 )

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

随着软件定义网络(Software Defined Network,SDN)的迅猛发展,单控制器部署的固有缺陷逐渐显露出来,多控制器部署已成为必然趋势。但由于控制器数量以及放置位置对网络性能具有决定性的影响,且在解决该问题时权衡因素多、计算复杂度高,严重阻碍了SDN在数据中心和广域网的应用。首先阐述了放置问题的本质和通用的求解步骤;其次基于网络模型详述了部署策略的核心构件,即优化目标、搜索算法;然后综合国内外的研究,将部署策略分为静态部署和动态部署两大类,并着重对比了典型策略的优缺点;最后展望未来的研究方向。

限时点到多点跨数据中心传输的多源树调度算法

庄奕, 杨家海

计算机科学. 2020, 47 (7): 213-219. doi:10.11896/jsjkx.200300069

摘要 ( 409 )

PDF(2261KB) ( 748 )

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

随着各种云应用的数据规模的增大,越来越多的云服务提供商开始关注跨数据中心的大数据块传输(bulk transfer)。跨数据中心的大数据块传输面临的主要挑战是:如何找到最佳的资源调度算法,在用户指定的时限内,用最少的传输资源将用户的数据传输到指定的地点。文中设计了一种有效的带传输时限(transfer deadlines)的、点到多点(Point-to-MultiPoint,P2MP)的跨数据中心数据传输调度算法MSTB(Multi-Source Tree-Based algorithm)。在多源机制和多播转发树的帮助下,MSTB表现得比现有的最优方法更好。仿真实验结果表明,MSTB可以在保证低传输完成时间和低计算复杂度的同时,增加最高达91%的传输请求接受数,增加最高达54%的有效吞吐量。

一种基于4Bit编码的深度学习梯度压缩算法

蒋文斌, 符智, 彭晶, 祝简

计算机科学. 2020, 47 (7): 220-226. doi:10.11896/jsjkx.200300097

摘要 ( 341 )

PDF(2745KB) ( 994 )

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

对梯度数据进行压缩,是一种减少多机间通信开销的有效方法,如MXNet系统中的2Bit方法等。但这类方法存在一个突出的问题,即过高的压缩比会导致精度及收敛速度下降,尤其是对规模较大的深度神经网络模型。针对上述问题,提出了一种新的4Bit梯度压缩策略。该方法采用4个比特位表示一个具体的梯度值(通常为32位的浮点数)。相对于2Bit,该方法能够对梯度值进行更细粒度的近似,从而提高训练结果的准确率和收敛性。进一步地,根据网络模型每一层梯度特性的不同,选择不同的近似阈值,使得压缩后的数值更合理,从而进一步加快模型的收敛速度并提高最终准确率;具体地,兼顾操作的方便性和分布的合理性,根据每层梯度特性的不同,设置3组不同的阈值,以满足不同层梯度差异化特性的需求。实验结果表明,使用多组阈值的4Bit梯度压缩策略虽然在加速方面略逊于2Bit方法,但其准确率更高,实用性更强,能够在保持模型更高精度的前提下减少分布式深度学习系统的通信开销,这对于在资源受限环境下实现性能更好的深度学习模型非常有意义。

基于最长公共子串挖掘的未知链路层协议帧切割算法

陈庆超, 王韬, 冯文博, 尹世庄

计算机科学. 2020, 47 (7): 227-230. doi:10.11896/jsjkx.190600073

摘要 ( 216 )

PDF(1745KB) ( 577 )

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

在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并且实验过程中常常需要预先设定一些阈值。为此,文中提出了一种基于最长公共子串挖掘的未知链路层协议帧切割算法,该算法通过统计一定长度的比特流的最长公共子串,逐步精确前导码和帧起始定界符,从而实现帧切分。实验数据表明,该算法相较于基于频繁序列挖掘以实现帧切分的算法,相关候选序列数量呈指数级下降,最终使得候选序列唯一。该算法的时间复杂度为O(n),且只需单次扫描,充分说明该算法可以高效地实现帧切分。

基于融合元路径图卷积的异质网络表示学习

蒋宗礼, 李苗苗, 张津丽

计算机科学. 2020, 47 (7): 231-235. doi:10.11896/jsjkx.190600085

摘要 ( 473 )

PDF(1874KB) ( 1197 )

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

近年来,网络表示学习(Network Representation Learning,NRL)作为一种在低维空间中表示节点来分析异质信息网络(Heterogeneous Information Networks,HIN)的有效方法受到越来越多的关注。基于随机游走的方法是目前网络表示学习常用的方法,然而这些方法大多基于浅层神经网络,难以捕获异质网络结构信息。图卷积神经网络(Gragh Convolutional Network,GCN)是一种流行的能对图进行深度学习的方法,能够更好地利用网络拓扑结构,但目前的GCN设计针对的是同质信息网络,忽略了网络中丰富的语义信息。为了有效地挖掘异质信息网络中的语义信息和高度非线性的网络结构信息,进而提高网络表示的效果,文中提出了一种基于融合元路径的图卷积异质网络表示学习算法(MG2vec)。该算法首先通过基于元路径的关联度量方法来获取异质信息网络中丰富的语义信息;然后采用图卷积神经网络进行深度学习,捕捉节点和邻居节点的特征,弥补浅层模型捕捉网络结构信息能力不足的缺陷,从而实现将丰富的语义信息和结构信息更好地融入低维的节点表示中。在数据集DBLP和IMDB上分别进行实验,相比DeepWalk,node2vec和Metapath2vec算法,所提MG2vec算法在多标签分类任务上的分类精确率更高且性能更优,精确率和Macro-F1值分别达到了94.49%和94.16%,且与DeepWalk相比分别最高提升了26.05%和28.73%。实验结果证明,MG2vec算法的性能优于经典的网络表示学习算法,具有更好的异质信息网络表示效果。

拓扑综合评估与权值自适应的虚拟网络映射算法

史朝卫, 孟相如, 马志强, 韩晓阳

计算机科学. 2020, 47 (7): 236-242. doi:10.11896/jsjkx.190600022

摘要 ( 236 )

PDF(2209KB) ( 636 )

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

针对现有虚拟网络映射算法对节点拓扑特征考虑得不够全面、节点评价方式较为单一且指标权值不能根据网络环境自适应调整等问题,提出一种拓扑综合评估与权值自适应的虚拟网络映射算法。文中在节点映射阶段综合考虑节点中心度、就近度与邻近聚集度等拓扑属性,结合节点CPU与邻接带宽和等资源属性对节点进行多指标重要度排序,根据网络环境的变化利用熵权法自适应调整指标权值。仿真结果表明,相较于最新的和经典的虚拟网络映射算法,所提算法的映射成功率提高了2%～23%,长期平均收益开销比提升了3%～17%,且该算法对不同资源需求类型的虚拟网络请求都能保持良好性能。

基于自适应粒子群的WSN覆盖优化

齐薇, 虞慧群, 范贵生, 陈亮

计算机科学. 2020, 47 (7): 243-249. doi:10.11896/jsjkx.200200133

摘要 ( 490 )

PDF(2830KB) ( 950 )

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

数据感知层的无线传感器网络覆盖范围对感知服务质量具有非常重要的意义。鉴于无线传感器网络初始部署的随机性所造成的覆盖冗余、覆盖空洞以及粒子群算法自身的早熟收敛等问题,提出一种基于二项感知覆盖的自适应虚拟力粒子群优化算法,以优化网络的有效覆盖率。该算法通过在网络中添加移动节点来进行位置调度的重部署分布,并计算种群进化程度和相对聚合程度以自适应调节惯性权重,同时利用适应度方差阈值判断当前状态是否需要引入虚拟力策略的干扰。文中重点分析了初始部署类别和移动节点占比对重部署覆盖性能的影响,并给出了相应的算法实现。仿真实验表明,相比ACPSO,DACPSO,DVPSO算法,改进的粒子群算法的覆盖率达到了98.33%,并且具有较高的移动效率,充分证明了该算法的有效性。

三维无线自组织网络中最小虚拟骨干的近似算法

易梦, 梁家荣, 覃斌

计算机科学. 2020, 47 (7): 250-256. doi:10.11896/jsjkx.190700059

摘要 ( 311 )

PDF(2021KB) ( 697 )

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

在均质无线自组织网络中,虚拟骨干(Virtual Backbone,VB)的大小是衡量无线自组织网络质量的一个重要因素,虚拟骨干越小,网络路由开销越少。最小虚拟骨干的求取问题能够抽象为最小连通控制集问题。针对二维无线自组织网络上的单位圆盘图(Unit Disk Graph,UDG)中最小连通控制集问题,目前已有很多研究成果,但是在现实中的某些情况下,单位圆盘图并不能准确地抽象网络。因此,文中提出了在单位球图(Unit Ball Graph,UBG)中构建高质量的连通控制集(Connected Dominating Set,CDS)的算法ST-CDS,给出了单位球图中独立节点个数的一个优化上界,并进一步利用该优化上界得到连通控制集的性能比。所提算法主要运用构造最小斯坦纳节点的斯坦纳树(Steiner Tree with Minimum Number of Steiner Nodes)方法来优化节点之间的连通部分。理论分析表明,ST-CDS算法的性能比为11.8080＋ln11,是目前已知该方向研究中最好的结果。仿真结果也验证了ST-CDS算法的可行性。

一种新的设备指纹特征选择及模型构建方法

王萌, 丁志军

计算机科学. 2020, 47 (7): 257-262. doi:10.11896/jsjkx.190900107

摘要 ( 916 )

PDF(1838KB) ( 1834 )

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

近年来,随着移动互联网的快速发展,越来越多的业务从浏览器端转移到了移动端。但是,寄生在移动互联网上的黑色产业链也达到了泛滥的地步。设备指纹技术应运而生,即利用设备的特征属性为每个设备生成独一无二的标识。其间涌现了很多利用机器学习方法进行设备唯一性认证的策略,其中大部分方法注重于模型的建立,很少对特征选择部分展开深入研究,而特征选择直接关系到最终模型的性能。针对该问题,文中提出了一种新的设备指纹特征选择及模型构建方法(Feature Selection Based on Discrimination and Stability and Weight-based Similarity Calculation,FSDS-WSC),即根据不同设备的特征区分度和相同设备的特征稳定性选出最具价值的一些特征,并将这些特征的重要程度作为特征权重应用到模型建立的后续过程中。在真实场景中的6424台Android设备上,将FSDS-WSC与当今主流的其他特征选择方法进行了对比实验。结果表明,FSDS-WSC相比其他方法有了较大改进,设备唯一性认证的准确率达到了99.53%,证实了FSDS-WSC的优越性。

PFP算法改进的不可能差分分析

沈璇, 王欣玫, 何俊, 孙志远

计算机科学. 2020, 47 (7): 263-267. doi:10.11896/jsjkx.200200034

摘要 ( 724 )

PDF(2489KB) ( 1010 )

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

目前资源受限环境的应用场景越来越多,该场景下的数据加密需求也随之增加。以国际标准PRESENT算法为代表的一大批轻量级分组密码应运而生。PFP算法是一种基于Feistel结构的超轻量级分组密码算法,它的轮函数设计借鉴了国际标准PRESENT算法的设计思想。PFP算法的分组长度为64比特,密钥长度为80比特,迭代轮数为34轮。针对PFP算法,研究了其抵抗不可能差分分析的能力。在该算法的设计文档中,设计者利用5轮不可能差分区分器攻击6轮的PFP算法,能够恢复32比特的种子密钥。与该结果相比,文中通过研究轮函数的具体设计细节,利用S盒的差分性质构造出7轮不可能差分区分器,并攻击9轮的PFP算法,能够恢复36比特的种子密钥。该结果无论在攻击轮数还是恢复的密钥量方面,均优于已有结果,是目前PFP算法最好的不可能差分分析结果。

一种基于拓扑结构及分配机制设计的多子块激励共识机制

刘帅, 甘国华, 刘明熹, 房勇, 汪寿阳

计算机科学. 2020, 47 (7): 268-277. doi:10.11896/jsjkx.200200027

摘要 ( 401 )

PDF(1628KB) ( 857 )

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

对经典的PoW共识机制进行改进,改变了矿工所挖出区块接入主链的条件和收益分配策略,从而提出了一种改进共识机制。与PoW不同,在该改进共识机制中,首个生成的由N个子区块相连的子链将被整体接入主链,从而用更为复杂的网状结构来代替原有的单一链结构;改进了传统共识机制的收益分配策略,将分配策略分为3个步骤,以期提高算力小的矿工的预期收益,从而激励算力小的矿工积极参与挖矿,提升区块链的安全性。此外,该改进共识机制引入的网状结构,使矿工有了更多的挖矿策略选择。文中分别讨论了挖矿策略的选择、恶意矿工分拆算力、合谋等对区块链的安全与效能产生的影响。最后,通过设置多种市场情景对改进算法进行了仿真实验,分析在各种市场特征下各类矿工的挖矿收益,也就是挖矿策略的种类、选择各挖矿策略的矿工算力之比、算力分布的极差、大小矿工的划分标准等参数对矿工收益的影响效果,以为矿工后期选择挖矿策略提供指导。

一种基于云端加密的FPGA自适应动态配置方法

陈利锋, 朱路平

计算机科学. 2020, 47 (7): 278-281. doi:10.11896/jsjkx.190700110

摘要 ( 376 )

PDF(1914KB) ( 743 )

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

在需要进行大量数据并行计算的算法(如云计算、机器学习算法、人工智能算法等)中,FPGA作为一种提升性能的重要技术手段,得到了广泛的应用。FPGA配置方式中,需要在存储器中读取配置数据,然后将其写入FPGA中。作为技术成果的实际体现,FPGA的配置数据可能被非法获取,从而导致研究成果泄露的问题。为了较好地应对这个问题,文中提出了一种有效的基于云加密的FPGA配置方法。该方法通过云端加密APP对配置数据文件进行加密管理,在需要配置FPGA的时候,由微处理器通过云端服务器的访问端口获取加密的配置数据,并使用内置在微处理器的解密算法进行解密,然后用解密后的数据对FPGA进行动态配置。该方法将FPGA的配置数据存储于云端服务器,在云服务器上通过加密手段进行严格的数据保护和文件保护,由此提供了灵活而强大的加密保护功能;微处理器从云端通过加密通道获取数据,将加密数据解密后再用于FPGA的配置,整个过程中配置数据都是处于加密状态,数据泄密的风险得到了有效控制。这样,既实现了对配置数据最大限度保护,防止其被非法获取和使用,又实现了对FPGA的远程动态配置。所提方法在阿里云和腾讯云平台得到了实际验证,其不仅保密效果好,而且能灵活配置。

一种基于强化学习的嵌入式系统抗拒绝服务攻击的缓存调度方案

黄锦灏, 丁钰真, 肖亮, 沈志荣, 朱珍民

计算机科学. 2020, 47 (7): 282-286. doi:10.11896/jsjkx.200100135

摘要 ( 455 )

PDF(1904KB) ( 753 )

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

在多核嵌入式操作系统中,中央处理器对共享最后一级缓存(Last Level Cache,LLC)的资源调度决定了各用户进程的指令周期数(Instructions Per Cycle,IPC),以及对拒绝服务(Denial-of-Service,DoS)攻击的鲁棒性。但是,现有缓存调度方案依赖于具体的LLC调度模型和DoS攻击模型,使中央处理器难以在不同调度环境中的每个调度周期及时获得用户进程的运行信息。因此,文中提出一种基于强化学习的嵌入式系统LLC调度技术,以抵御拒绝服务攻击。该技术根据用户进程的LLC占用起始位置和终止位置,结合反馈的指令周期数、载入未命中率和存储未命中率等信息,优化LLC的占用位置和占用空间。在动态LLC调度环境下,中央处理器不需要预知DoS攻击模型,即可提高指令周期数并同时降低恶意进程的DoS攻击成功率。在多租户虚拟机共同参与的多核嵌入式操作系统中的仿真结果表明,所提技术可以显著提高指令周期数并降低DoS攻击的成功率。

基于改进隐马尔可夫模型的网络安全态势评估方法

李欣, 段詠程

计算机科学. 2020, 47 (7): 287-291. doi:10.11896/jsjkx.190300045

摘要 ( 449 )

PDF(1743KB) ( 968 )

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

网络安全态势感知作为网络安全防护措施的有效补充,是近年来的研究热点之一,而准确地评估网络安全状态已成为网络安全领域的一个重要课题。隐马尔可夫模型(Hidden Markov Model,HMM)可用于网络安全态势评估,能实时评估网络状态,但其存在模型参数难以配置、评估准确率较低等问题。因此,文中提出了一种改进隐马尔可夫模型的态势评估方法,将模型Baum-Welch(BW)参数优化算法与人群搜索算法(Seeker Optimization Algorithm,SOA)相结合,利用SOA随机搜索能力强的特点,解决传统参数优化算法容易陷入局部最优解的问题,将优化后的参数代入HMM中,通过量化分析得出网络安全态势值。基于DARPA2000数据集采用MATLAB软件对提出的方法进行实验验证,结果表明,与BW算法相比,所提方法能够提高模型准确率,对网络安全态势的量化更加合理。

一种基于漏洞威胁模式的网络表示学习算法

黄易, 申国伟, 赵文波, 郭春

计算机科学. 2020, 47 (7): 292-298. doi:10.11896/jsjkx.190600156

摘要 ( 343 )

PDF(3415KB) ( 726 )

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

威胁情报分析可为网络攻防提供有效的攻防信息,而细粒度的挖掘即网络威胁情报数据中的安全实体及实体间的关系,是网络威胁情报分析研究的热点。传统的机器学习算法,在被应用到大规模网络威胁情报数据分析中时,面临着稀疏、高维等问题,进而难以有效地捕获网络信息。为此,针对网络安全漏洞的分类问题,文中提出了一种基于漏洞威胁模式的网络表示学习算法——HSEN2vec。该算法旨在最大限度地捕获异构安全实体网络的结构和语义信息,并从中获得安全实体的低维向量表示。该算法首先基于漏洞威胁模式获取异构安全实体网络的结构信息,随后通过Skip-gram模型建模,并通过负采样技术进行有效预测进而得到最终的向量表示。实验结果表明,在国家安全漏洞数据上,与其他方法相比,利用所提算法进行漏洞分类的准确率等评价指标有所提升。

基于流量指纹的物联网设备识别方法和物联网安全模型

杨威超, 郭渊博, 李涛, 朱本全

计算机科学. 2020, 47 (7): 299-306. doi:10.11896/jsjkx.190700199

摘要 ( 361 )

PDF(2338KB) ( 3126 )

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

物联网(Internet of Things,IoT)的大规模部署应用,使得有漏洞的物联网设备也可能联入网中。攻击者利用有漏洞的设备接入目标内部网络,就可潜伏伺机发起进一步的攻击。为防范这类攻击,需要开发一种对可疑设备接入控制并管理内部设备的安全机制。首先,为实现对可疑设备的接入控制,文中给出了一种设备识别方法,通过设置白名单,构建通信流量特征指纹,使用随机森林方法来训练设备识别模型;其次,为管理内部设备,提出了一种智能安全管理模型,构建基于资产、漏洞、安全机制等的本体威胁模型;最后,通过实验验证了设备识别模型的检测效果,其识别准确率达到96%以上,并将其与已有类似方法进行对比,结果证明了所提方法具有更好的检测稳定性。

基于改进蚁群算法的WSN源位置隐私保护

郭蕊, 芦天亮, 杜彦辉, 周杨, 潘孝勤, 刘晓晨

计算机科学. 2020, 47 (7): 307-313. doi:10.11896/jsjkx.200100056

摘要 ( 386 )

PDF(1991KB) ( 696 )

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

面向目标监测任务的无线传感网(Wireless Sensor Network,WSN)通常部署在无人监管和关键敏感的环境中,无线通信的开放性严重威胁了监测目标的安全性,因此需要对源节点位置隐私进行有效保护。针对现有WSN源位置隐私保护方案普遍存在的高延迟和高能耗问题,提出了一种基于改进蚁群算法的源位置隐私保护方案EESLP-ACA(Energy Efficient Source Location Privacy based on Ant Colony Algorithm)。传感器节点接收到数据包时,将根据信息素浓度和改进的路径启发素含量选择转发节点,以最小化和均衡化网络能耗;同时通过引入参照距离并改进信息素更新机制,增大未选中节点成为转发节点的可能性,构建低概率重复动态路由,减少攻击者能够接收到的数据包数目,增加反向追踪的难度。性能分析表明,所提方案不但能有效提高蚁群算法(Ant Colony Algorithm,ACA)的性能,使其更好地应用于WSN源位置隐私保护领域;而且相较于CDR和ELSP方案,在延长网络生存周期和缩短传输延迟的同时,能有效提升源位置隐私的安全性。

一种基于量子GHZ态的防窃听网络编码

徐光宪, 崔俊杰

计算机科学. 2020, 47 (7): 314-321. doi:10.11896/jsjkx.190500168

摘要 ( 244 )

PDF(2704KB) ( 699 )

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

经典网络编码在传输过程中的编码效率低,容易被窃听。虽然Hayashi提出的在发送端共享EPR的方式提高了信息传输过程中的编码效率,但其不能实现传输信息的完全恢复,也没有对信息进行安全处理,信息很容易被窃听。为此,文中提出了基于GHZ三粒子最大纠缠态,利用量子的不可克隆定理及隐形传态技术来防止信息被窃听的量子网络编码方案。首先,从经典的蝶形网络编码出发,在发送端对待发送粒子与GHZ态粒子进行直积操作;其次,对运算后的粒子进行Bell测量,并根据测量结果得到预编码信息,再将预编码信息传输给中间节点;然后,在接收端引入用于测量的辅助粒子,对接收到的粒子进行量子纠缠运算,并对粒子簇进行联合幺正运算;最后,依据编码信息选取相应的酉矩阵对粒子簇进行恢复。实验数据表明,基于GHZ态的量子网络编码在单次传输成功率上有了明显的提高,在编码效率上只需6个量子比特即可完成量子信息在蝶形网络中的交叉传输;在安全性方面,其提升了信息是否被窃听的可检测概率。实验数据充分表明,所提方案提高了网络编码系统的编码效率,有效地解决了信息传输的窃听问题。

基于物理层安全的空间调制系统天线选择算法

丁青锋, 奚韬, 连义翀, 吴泽祥

计算机科学. 2020, 47 (7): 322-327. doi:10.11896/jsjkx.190600133

摘要 ( 246 )

PDF(2130KB) ( 626 )

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

针对基于最优安全容量的天线选择算法复杂度较高的问题,提出一种低复杂度的基于列范数平方之差的天线选择算法。该算法首先通过归一化固定量以及简化安全容量解析式,得到合法信道范数平方与窃听者信道范数平方的差值;然后根据向量范数的性质,将差值转换为各信道系数平方之差的和;接着遍历信道系数之差并进行排序,选出使得信道范数平方之差最大的天线组合;最后通过结合该算法和人工噪声(Artificial Noise,AN)技术,将人工噪声矢量设计在筛选后余下天线的合法信道零空间,从而获得最优的安全容量。仿真结果表明,与传统的天线选择算法相比,该算法在显著提升安全容量的同时,大大降低了运算的复杂度;并在维持合法接收者误比特率较低的情况下,最大化限制窃听者的误比特率性能,从而有效地增强了系统的安全性能。

一种零高分辨率3D网格模型的信息隐藏算法

任帅, 王萌, 范傲雄, 高泽, 徐解, Shahzad KHURRAM, 张弢

计算机科学. 2020, 47 (7): 328-334. doi:10.11896/jsjkx.190800021

摘要 ( 514 )

PDF(3395KB) ( 752 )

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

针对目前3D网格模型信息隐藏算法抗分析性弱的问题,提出一种零高分辨率的信息隐藏算法。首先,利用改进半边折叠网格简化算法对网格模型进行多分辨率分析,将3个分辨率层表示为High-layer,Mid-layer,Low-layer;其次,在High-layer进行同心球面分割,提取特征向量,在Mid-layer计算顶点突出度,确定嵌入信息的特征点;再次,通过将特征向量中特征值的最高位与Chebyshev置乱的加密信息建立联系以形成关联信息;最后,利用分段映射函数将关联信息嵌入到特征点球面坐标r值的DCT变换交流系数中。算法将高分辨率层的特征向量与置乱信息所构建的关联信息隐藏于能量小于15%中分辨率层的鲁棒特征点的仿射变换不变量中,有利于算法的不可见性、鲁棒性和抗分析性。采用一阶拉普拉斯平滑的隐写分析方法检测不到点、面特征的明显变化,表明所提算法的抗分析性好。