1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2018年第11期, 刊出日期:2018-11-20
  
综述
面向无人机自组网编队控制的通信组网技术
程潇, 董超, 陈贵海, 王蔚峻, 戴海鹏
计算机科学. 2018, 45 (11): 1-12.  doi:10.11896/j.issn.1002-137X.2018.11.001
摘要 ( 194 )   PDF(2323KB) ( 476 )   
参考文献 | 相关文章 | 多维度评价
随着技术的发展,多无人机系统协同作业的研究得到越来越多的关注。编队控制是无人机协同作业的关键技术,对具有动态信道与拓扑特征的无人机自组网的通信组网技术提出了极高的要求。首先介绍了无人机自组网编队控制的相关模型;基于此,从编队保持和重组、任务更新、编队可靠性等方面综述并分析了5种编队控制策略以及它们对无人机自组网通信组网技术的不同需求;最后展望了面向无人机自组网编队控制的通信组网技术的发展前景和方向。
网络信任研究进展
刘建生, 游真旭, 乐光学, 王结太, 刘建华
计算机科学. 2018, 45 (11): 13-28.  doi:10.11896/j.issn.1002-137X.2018.11.002
摘要 ( 116 )   PDF(2614KB) ( 220 )   
参考文献 | 相关文章 | 多维度评价
网络的迅速发展为人们提供了自由、开放的交互方式,互联网服务已经成为大众日常生活的重要组成部分,如何评价表征节点交互的可信度已成为网络应用的核心问题之一。由于开放式网络环境具有匿名性、随机性和动态性等特点,用户在网络中选择目标节点进行交互时面临诸多风险,因此基于节点交互行为的信任评价机制成为抑制网络恶意虚假行为的有效策略机制。首先,概述信任的相关性质,根据网络节点间的交互行为及其产生的信任关系特征,形式化定义与构建信任网络。其次,分析信任机制的框架体系,依次讨论信任机制在P2P网络、电子商务、社会网络中的研究要点与安全威胁。最后,重点对比分析不同领域中的典型信任模型,详述其抗攻击效用与不足,从改进模型算法、提高模型抗攻击能力等方面指出信任机制在未来的研究方向。
孪生支持向量机综述
安悦瑄, 丁世飞, 胡继普
计算机科学. 2018, 45 (11): 29-36.  doi:10.11896/j.issn.1002-137X.2018.11.003
摘要 ( 158 )   PDF(1468KB) ( 496 )   
参考文献 | 相关文章 | 多维度评价
孪生支持向量机(Twin Support Vector Machine,TWSVM)是在支持向量机(Support Vector Machine,SVM)的基础上发展而来的一种新的机器学习方法。作为一种二分类的分类器,其基本思想为寻找两个超平面,使得每一个分类面靠近本类样本点而远离另一类样本点。作为一种新兴的机器学习方法,孪生支持向量机自提出以来便引起了国内外学者的广泛关注,已经成为机器学习领域的研究热点。对孪生支持向量机的最新研究进展进行综述,首先介绍了孪生支持向量机的基本概念与基本模型;然后对近几年来新型的孪生支持向量机模型与研究进展进行了总结,并对其代表算法进行了优缺点分析和实验比较;最后对将来的研究工作进行了展望。
库操作系统的研究及其进展
舒红梅, 谭良
计算机科学. 2018, 45 (11): 37-44.  doi:10.11896/j.issn.1002-137X.2018.11.004
摘要 ( 215 )   PDF(1601KB) ( 1164 )   
参考文献 | 相关文章 | 多维度评价
最早的库操作系统(Library OS,LibOS)基于外内核架构,目的是验证在用户空间管理系统资源的可行性和高性能性。但是,由于外内核还停留在研究上,实际应用中仍以宏内核和混合内核为主,因此LibOS一开始并没有引起学术界和产业界的过多关注。伴随云计算的快速发展和物联网的兴起,为了构建安全高效的Unikernel云服务和物联网微服务,LibOS成为了新的研究热点。首先总结了LibOS的基本定义和基本特点;然后提出了LibOS分类模型;接着总结了LibOS的系统架构,并详细阐述了LibOS的关键技术,包括LibOS内核基中的线程管理、CPU调度和虚拟内存管理以及LibOS功能系中的网络服务功能、文件I/O功能和设备访问功能等;最后结合已有的研究成果,探讨了LibOS面临的问题和挑战。
基于D2D通信的流量卸载技术综述
颜学文, 董超, 屈毓锛
计算机科学. 2018, 45 (11): 45-51.  doi:10.11896/j.issn.1002-137X.2018.11.005
摘要 ( 136 )   PDF(1687KB) ( 842 )   
参考文献 | 相关文章 | 多维度评价
随着各类移动终端与高带宽需求业务的普及,蜂窝网流量已呈现出爆炸性增长的趋势;同时,由于网络用户分布不均匀,蜂窝网流量分布也存在不均衡的现象。基于D2D(Device-to-Device)通信的流量卸载(Traffic offloading)是解决数据流量急剧增加和不均匀分布的一种经济、有效的技术。首先,根据D2D通信在流量卸载中所承担的任务,将基于D2D通信的流量卸载技术分为以D2D通信为目标和以D2D通信为中继两类;然后,详细介绍每一类技术的研究现状并分析讨论各自的优缺点;最后,提出下一步的潜在研究方向。
基于区块链的身份管理认证研究
董贵山, 陈宇翔, 张兆雷, 白健, 郝尧
计算机科学. 2018, 45 (11): 52-59.  doi:10.11896/j.issn.1002-137X.2018.11.006
摘要 ( 297 )   PDF(2876KB) ( 2403 )   
参考文献 | 相关文章 | 多维度评价
针对网络空间中的身份管理问题,分析了通用的基于区块链的身份管理认证模型。首先,概述了身份管理的定义要求,回顾了网络空间中身份管理在区块链应用方面的早期尝试,总结了其发展经验并分析了身份管理所面临的问题,对比了区块链的优缺点及其在身份管理方面的验证项目。然后,分析了通用的区块链身份管理模型及每个模块。最后,重点对较为成熟的ShoCard公司的应用场景和DIMS(Decentralized Identity Management System)做了分析对比,并对未来进行了展望。
网络与通信
基于虚拟网格的无线传感器网络分簇路由算法
陈战胜, 沈鸿
计算机科学. 2018, 45 (11): 60-65.  doi:10.11896/j.issn.1002-137X.2018.11.007
摘要 ( 117 )   PDF(2742KB) ( 308 )   
参考文献 | 相关文章 | 多维度评价
针对WSNs路由协议中链路通信负载不均引发的能量空洞问题,提出一种基于虚拟网格的动态聚簇策略IDCS和考虑数据转发延迟的最大化网络生命周期的动态负载均衡路由算法DCDLB。IDCS依据节点的通信半径将网络划分成若干虚拟网格,采用考虑节点能量和位置因素的分布式簇首选举策略,并引入基于簇首能量水平的动态簇首轮换机制。DCDLB综合考虑簇首间能耗均衡和数据多跳转发延迟来构建路由,实现网络生命周期的最大化。实验结果表明,DCDLB路由算法在延长网络生命周期和降低数据转发延迟方面优于LEACH,HEED和CRVB路由算法。
一种改进的自适应多叉树防碰撞算法
王汉武, 于涛
计算机科学. 2018, 45 (11): 66-69.  doi:10.11896/j.issn.1002-137X.2018.11.008
摘要 ( 63 )   PDF(1524KB) ( 157 )   
参考文献 | 相关文章 | 多维度评价
针对传统自适应多叉树防碰撞算法在标签识别过程中存在的空闲时隙过多、阅读器与电子标签间的通信负载量过大等不足,提出了一种改进的自适应多叉树防碰撞算法(Improved Adaptive division Collision Tree algorithm,IACT)。该算法通过计算碰撞因子决定采用二叉树或四叉树。当采用二叉树时,若阅读器检测到碰撞位只有一位,则无需再次发送命令即可以直接识别出标签;采用四叉树时,阅读器首先发送一命令,要求标签返回最高两个碰撞位对应的编码,然后根据编码得到碰撞信息。在标签中加入计数器,使用最高两个碰撞位和计数器值作为查询命令,响应的电子标签将序列号的后缀信息发送给阅读器处理。算法性能分析和实验仿真表明,IACT算法能有效减少系统总时隙,降低了通信负载开销,提高了标签识别效率。
分忙闲站点的限定(K=2)轮询控制系统分析研究
杨志军, 孙洋洋
计算机科学. 2018, 45 (11): 70-74.  doi:10.11896/j.issn.1002-137X.2018.11.009
摘要 ( 94 )   PDF(2171KB) ( 180 )   
参考文献 | 相关文章 | 多维度评价
为了保障系统公平性并提高轮询控制系统的工作效率,提出了区分忙闲站点的限定(K=2)轮询控制系统。系统在限定(K=2)轮询服务的基础上,依托站点忙闲状态,采用并行调度控制方式仅对有数据分组的忙站点提供发送服务。采用概率母函数和嵌入式马尔科夫链的方法建立了系统的数学模型,并精确解析了系统平均排队队长和平均等待时延等重要性能参数。仿真实验结果表明:理论计算值与模拟仿真值近似相等,说明理论分析正确合理。该模型既能保障系统公平性,又能避免对空闲站点查询,同时还能节省转换查询时间,从而提高了系统利用率和工作效率。与已有限定(K=1)轮询控制方式相比,所提系统具有更好的QoS保障。
面向智慧医疗云的SDN动态负载均衡方法
李雄英, 董庆贺, 何倩, 周水明
计算机科学. 2018, 45 (11): 75-81.  doi:10.11896/j.issn.1002-137X.2018.11.010
摘要 ( 111 )   PDF(1907KB) ( 418 )   
参考文献 | 相关文章 | 多维度评价
文中引入软件定义网络(Software Defined Network,SDN)对智慧医疗云进行网络管理,并且针对传统SDN控制器存在单点失效和负载均衡的问题,设计了智慧医疗分布式SDN控制器系统。SDN控制系统分为SDN控制器集群、数据转发平面和智慧医疗云服务系统3层。在此基础上,提出一种实时负载动态自调节的快速负载均衡算法DAF(Dynamic Adaptive and Fast Load Balancing)。在该算法中,负载信息感知组件周期性地采集自己的负载信息,自动地进行控制器间的负载信息交互;控制器的负载值超过阈值时,会触发交换机迁移动作,以动态配置交换机与控制器之间的映射关系。实验结果表明,面向智慧医疗云的分布式SDN控制系统的性能良好,且DAF算法能够快速地实现SDN控制器间的负载均衡,提升了智慧医疗云的网络吞吐量。
一种新的传感器网络能量收集优化技术
王艳丽, 阴国富, 金蓉
计算机科学. 2018, 45 (11): 82-86.  doi:10.11896/j.issn.1002-137X.2018.11.011
摘要 ( 105 )   PDF(1699KB) ( 251 )   
参考文献 | 相关文章 | 多维度评价
针对无线传感器网络能量严格受限和节点间能量不均衡的问题,建立无线信息和功率同时传输的协作MIMO通信模型;针对如何获取系统的最佳能量效率的问题,提出一种新的有效资源分配算法。仿真分析和原型实验结果表明,新的有效资源分配算法在迭代次数达到12时收敛,能量效率随发射功率额度的增加而迅速增加,当最大发射功率额度达到3dBm时能量效率趋向平稳;与SISO传输的能耗相比,采用协作MIMO信息和功率同时传输的技术能节省1个以上的能量级,并能得到较高的网络效用。
虚拟网映射问题的计算复杂性分析
余建军, 吴春明
计算机科学. 2018, 45 (11): 87-91.  doi:10.11896/j.issn.1002-137X.2018.11.012
摘要 ( 79 )   PDF(1244KB) ( 164 )   
参考文献 | 相关文章 | 多维度评价
虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。
基于节点亲密度的链路预测算法
吕亚楠, 韩华, 贾承丰, 完颜娟
计算机科学. 2018, 45 (11): 92-96.  doi:10.11896/j.issn.1002-137X.2018.11.013
摘要 ( 148 )   PDF(2339KB) ( 567 )   
参考文献 | 相关文章 | 多维度评价
链路预测作为复杂网络分析的一个重要分支,在不同领域中有着广泛的应用。现有的链路预测算法通常根据共同邻居节点的结构信息来度量节点对之间的相似性,忽略了节点对与其共同邻居节点之间的连接紧密程度。针对此问题,提出了一种基于节点亲密度的链路预测算法。该算法利用边聚集系数来测量节点对与其共同邻居节点之间的紧密程度,以AUC值作为链路预测的精确度评价指标。在4个真实网络上的实验结果表明,相比于其他相似性算法,所提出的算法提高了链路预测的预测精度。
认知无线传感器网络中基于稳定性的能效路由协议
朱江, 雷云, 王雁
计算机科学. 2018, 45 (11): 97-102.  doi:10.11896/j.issn.1002-137X.2018.11.014
摘要 ( 96 )   PDF(1795KB) ( 171 )   
参考文献 | 相关文章 | 多维度评价
在认知传感器节点构建无线传感器网络的过程中,为了降低节点的能量消耗和提高数据的传输能力,提出一种基于稳定性的能效路由协议。该协议引入了稳定性因子,通过采用授权用户占用信道模型建模,并不断调整稳定性因子来研究路径选择与系统能量消耗的关系,找出一种受主用户影响最小的合理路径选择方案,减少链路失效的次数,提高数据传输能力,且保证较小的能量消耗,从而有效地均衡网络能量,延长网络生命周期。模拟的结果与理论分析结果一致,且表明所提出的协议在能量消耗和数据传输能力方面都具有更好的表现。
煤矿井下WSN中基于自适应粒子群聚类算法的多sink节点部署
胡长俊, 袁树杰
计算机科学. 2018, 45 (11): 103-107.  doi:10.11896/j.issn.1002-137X.2018.11.015
摘要 ( 76 )   PDF(2209KB) ( 141 )   
参考文献 | 相关文章 | 多维度评价
多sink节点的部署是井下传感器网络的重要研究课题,对网络性能的影响很大。针对目前采用的部署方法存在计算过程复杂、收敛速度慢、容易陷入局部最优等问题,在标准粒子群聚类算法的基础上,提出一种基于自适应粒子群聚类算法的井下多sink节点部署算法(简称A-PSOCA算法),在惯性权重系数中考虑了粒子的进化和聚合状况,使改进的算法的自适应能力更强,并在算法迭代过程中引入预防粒子位置重叠策略,防止粒子搜索局部最优化。仿真结果表明,A-PSOCA算法可以得到合理的sink节点位置,算法的收敛速度比标准粒子群聚类算法快1倍,所对应的网络的平均能耗和均衡性以及网络生存期也优于其他基于粒子群算法,适用于井下通信环境。
信息安全
基于Web操作系统的移动瘦终端多安全策略模型
杨莹, 夏剑锋, 朱大立
计算机科学. 2018, 45 (11): 108-114.  doi:10.11896/j.issn.1002-137X.2018.11.016
摘要 ( 107 )   PDF(1509KB) ( 204 )   
参考文献 | 相关文章 | 多维度评价
高安全级移动办公对信息系统不断提出更高的安全需求,在此背景下出现了瘦终端(Thin-Client)解决方案。其采用云存储、分布式终端系统和集中管理,为用户提供了更好的安全性。当前的主要技术包括虚拟桌面和Web终端,其中前者是主流。近年来,Web操作系统(Web OS)的发展促使Web终端受到业界重视,但Web OS还存在机密性和完整性保护不足的问题。基于Web OS系统的特点抽象建模,提出了混合机密性模型BLP和完整性模型Biba的多安全策略模型。首先利用格将机密性标签、完整性标签和范畴集合相结合,解决了BLP与Biba信息流相反的问题;然后提出可信主体的最小特权原则来进一步约束可信主体的权限,并给予特定可信主体临时权限,以提高灵活性和可用性;最后分析模型的安全性和适用性。
有限理性公平数据交换协议的设计与仿真
陆正福, 普艳红, 倪盛斌, 许辰铭, 杨春尧
计算机科学. 2018, 45 (11): 115-123.  doi:10.11896/j.issn.1002-137X.2018.11.017
摘要 ( 92 )   PDF(1718KB) ( 241 )   
参考文献 | 相关文章 | 多维度评价
理性交换协议(REP)因使用了理想化的理性假设,在现实中有可能失效。为解决此协议失效的问题,基于与现实更为接近的有限理性假设(BRH),定义了有限理性公平概念,并首次基于BRH设计了有限理性公平数据交换协议(FDEP-BR)。理论分析表明,与REP相比,FDEP-BR虽然牺牲了一定效率(轮复杂度为O(l*v)),但具有容错性和有限理性公平性,能够抵抗非合作攻击。对FDEP-BR构造自动机模型,并改进经验加权吸引(EWA)学习模型的决策方式,设计了EWA学习决策算法;在此基础上,基于Jade-Repast集成平台对FDEP-BR进行了仿真,仿真结果表明FDEP-BR的均衡状态与预期具有一致性。
基于公私属性的多授权中心加密方案
初晓璐, 刘培顺
计算机科学. 2018, 45 (11): 124-129.  doi:10.11896/j.issn.1002-137X.2018.11.018
摘要 ( 92 )   PDF(2176KB) ( 223 )   
参考文献 | 相关文章 | 多维度评价
基于属性的加密方法可以简化云计算环境中的密钥管理和访问控制问题,是适用于云环境的加密方案。文中提出了一种基于公私属性的多授权中心加密方案。该方案将属性分为公有属性和私有属性,将用户的角色权限信息等作为用户的公有属性,将用户登录密码、设备上的标识码等作为用户的私有属性。利用公有属性实现访问控制,在云服务器上安全地共享数据;利用私有属性实现信息流的安全控制,确保只有特定用户在特定设备上使用数据。提出的方案可以实现密钥追踪和属性撤销,基于私有属性的加密还可以实现抗合谋攻击。
一种支持完美隐私保护的批处理数据拥有性证明方案
庞晓琼, 任孟琦, 王田琪, 陈文俊, 聂梦飞
计算机科学. 2018, 45 (11): 130-137.  doi:10.11896/j.issn.1002-137X.2018.11.019
摘要 ( 108 )   PDF(2791KB) ( 192 )   
参考文献 | 相关文章 | 多维度评价
数据拥有性证明技术是当前云存储安全领域中的一项重要研究内容,可使用户无须下载所有文件就能高效地远程校验用户数据是否完整存储于云服务器。现实中,用户趋向于委托第三方验证机构TPA代替自己来验证数据的完整性;然而,多数支持第三方公开审计的数据拥有性证明方案通常只考虑恶意服务器是否能够伪造标签或证明的问题,鲜有考虑恶意TPA可能会窃取用户隐私的情况。近几年,一些既针对服务器保证数据的安全性又针对TPA实现数据隐私保护的数据拥有性证明方案逐渐被提出,但多应用于单云服务器环境下;个别应用在多云服务器环境下可支持批量审计的方案,或者不能有效抵抗恶意云服务器的攻击,或者无法实现针对TPA的零知识隐私保护。因此,文中在Yu等工作的基础上,提出了一个多云服务器环境下支持批量审计的数据拥有性证明方案。所提方案既可保证针对恶意云服务器的安全性,还可实现针对TPA的完美零知识隐私保护。性能分析及仿真实验表明所提方案是高效且可行的。
基于人工免疫危险理论的微博水军用户检测研究
杨超, 秦廷栋, 范波, 李涛
计算机科学. 2018, 45 (11): 138-142.  doi:10.11896/j.issn.1002-137X.2018.11.020
摘要 ( 118 )   PDF(2328KB) ( 225 )   
参考文献 | 相关文章 | 多维度评价
将人工免疫危险理论引入到用户行为特征的分析中,以有效地识别微博水军用户。以新浪微博为例,分析了新浪微博水军的行为特征,选取微博总数、微博等级、是否认证、阳光信用、粉丝数等特征属性,将属性分析结果作为区别水军与正常用户的特征信号,并基于树突状细胞算法(Dendritic Cells Algorithm,DCA)实现新浪微博水军的识别。使用新浪微博用户的真实数据对算法的有效性进行了验证和对比实验,结果表明该方法能够有效检测出新浪微博中的水军用户,具有较高的检测准确率。
基于攻击图的信息物理融合系统渗透测试方法
徐丙凤, 何高峰
计算机科学. 2018, 45 (11): 143-148.  doi:10.11896/j.issn.1002-137X.2018.11.021
摘要 ( 122 )   PDF(2049KB) ( 255 )   
参考文献 | 相关文章 | 多维度评价
信息物理融合系统(Cyber-Physical System,CPS)多为安全攸关系统,是网络攻击的高价值目标,需要对其进行有效的安全评估。为此,提出一种基于攻击图的信息物理融合系统渗透测试方法。首先,对传统攻击图进行改进,考虑物理攻击、攻击持续时间以及物理系统的连续变量值,提出适用于CPS的攻击图建模技术AGC(Attack Graph for CPS),并在图中增加攻击可行性参数以表示单步攻击的成功率;其次,基于AGC提出最优攻击路径选择策略,包括最小攻击代价、最短攻击时间等,并设计面向CPS的智能渗透测试算法;最后,通过应用实例对方法的有效性进行验证。分析结果表明,该方法能够根据渗透测试目标选择最优攻击路径,并能根据实际反馈结果自动调整后续攻击步骤,有效实现CPS的安全评估。
基于CP-ABE的利益冲突数据集的访问控制
陈成, 努尔买买提·黑力力
计算机科学. 2018, 45 (11): 149-154.  doi:10.11896/j.issn.1002-137X.2018.11.022
摘要 ( 262 )   PDF(1407KB) ( 135 )   
参考文献 | 相关文章 | 多维度评价
云存储允许数据拥有者将数据储存在云端,以便为用户提供数据共享服务。然而,同一个数据拥有者储存的不同数据之间可能会出现利益冲突。鉴于此,文中提出针对利益冲突数据集的基于密文策略属性基加密(CP-ABE)的访问控制方案。在该方案中,数据拥有者将虚拟属性用“与”门嵌入访问树中以得到修正的访问树,并在修正的访问树下对利益冲突数据集中的各个数据加密,从而避免了一个用户访问利益冲突数据集中的部分或全部数据而导致的错误、欺骗或风险。最后,从理论上对所提方案的效率和安全性进行了分析,分析结果表明了其是高效且安全的。
单云服务器下的安全外包模幂运算
王健一, 王箭
计算机科学. 2018, 45 (11): 155-159.  doi:10.11896/j.issn.1002-137X.2018.11.023
摘要 ( 93 )   PDF(1389KB) ( 181 )   
参考文献 | 相关文章 | 多维度评价
模幂运算是加密和签名系统中最基础的运算。由于模幂运算需要耗费很大的计算成本,因此很多方案提出将模幂运算安全外包给云服务器。但是,现存的大多方案都需要两个不共谋的服务器来实现安全的模幂运算,一旦服务器共谋,就会导致外包隐私数据泄露。此外,很多现有方案都假设底数和指数都是保密的,但这并不适合于大多数现实应用场景。通常来说,为了减轻计算负担,只有敏感消息才需要被保密。为了解决上述问题,分别提出了固定底数(底数公开、指数保密)和固定指数(指数公开、底数保密)的安全外包方案。在该方案中客户端只需要使用一个云服务器,从而避免了两个服务器的共谋攻击。理论分析及实验结果证明了该方案的安全性和高效性。
基于能力度量的网络安全实验环境多仿真规划
曾子懿, 邱菡, 朱俊虎, 周天阳
计算机科学. 2018, 45 (11): 160-163.  doi:10.11896/j.issn.1002-137X.2018.11.024
摘要 ( 69 )   PDF(2276KB) ( 167 )   
参考文献 | 相关文章 | 多维度评价
多种仿真技术的融合使用可为网络安全实验环境的构建提供灵活的资源分配,其难点在于如何兼顾逼真度需求。针对该问题,文中提出了一种“按需分配”的多仿真规划方法。首先,以仿真能力定义逼真度需求,将复杂、抽象、无结构化的需求表示为简单、具体、结构化的形式;接着,给出了一种基于默认拒绝策略的逼真度需求满足性判定准则以及一种基于贪心策略的多仿真方案求解算法。在蠕虫样本传播的仿真环境构建实验中,运用该方法求解的仿真方案可在满足逼真度需求的条件下取得最小的仿真代价。
网电空间中基于IFTS预测模型的IDS方法
邢瑞康, 李成海, 范晓诗
计算机科学. 2018, 45 (11): 164-168.  doi:10.11896/j.issn.1002-137X.2018.11.025
摘要 ( 75 )   PDF(1311KB) ( 191 )   
参考文献 | 相关文章 | 多维度评价
网电空间是在信息化发展条件下随着世界军事的重大变革而产生的新兴作战空间,尤其是在防空反导对抗方面具有十分重要的影响。由于安全机制不尽完善,网络空间所要面对的威胁也不断增多。基于此背景,文中提出一种基于IFTS预测模型的入侵检测方法,该方法通过计算网络数据各特征属性的直觉模糊来预测误差,并通过直觉模糊预测误差来区分正常数据和入侵攻击,从而达到检测预警的目的。在此基础上,建立了入侵检测框架,并通过搭建仿真实验模拟平台来模拟一个抽象的、简化的网电空间对抗模型,对算法的有效性及效能进行验证。实验结果表明,该方法是一种有效的方法,并且在一定程度上提高了模型的检测率。
基于整数的轻量级分组密码电路的同态运算
毛和风, 胡斌
计算机科学. 2018, 45 (11): 169-175.  doi:10.11896/j.issn.1002-137X.2018.11.026
摘要 ( 99 )   PDF(1392KB) ( 206 )   
参考文献 | 相关文章 | 多维度评价
基于Gentry等在EUROCRYPT 2010上提出的整数上的全同态加密DGHV方案,结合批处理技术,给出了轻量级分组密码SIMON电路的状态切割同态运算实现方法;提出了半字节切割概念,给出了PRINCE电路的半字节切割同态运算实现方法。最后将PRINCE,SIMON-64/128,SIMON-128/256和AES-128电路的同态运算进行对比,分析给出了不同分组密码电路和不同实现方法的同态计算次数。
基于CP-ABE的可撤销属性加密访问控制算法
屠袁飞, 高振宇, 李荣雨
计算机科学. 2018, 45 (11): 176-179.  doi:10.11896/j.issn.1002-137X.2018.11.027
摘要 ( 112 )   PDF(1604KB) ( 205 )   
参考文献 | 相关文章 | 多维度评价
为了增强计算机网络的安全性,保证网络中的信息资源不被非法使用,需要进行访问控制。当前基于网格虚拟组织的访问控制算法通过在网格中建立不同的信任域、在主机之间建立基于身份和行为的访问控制策略,实现以任务发起者为中心的网格虚拟组织的跨域访问控制,建立互信的核心算法并进行逻辑推理,从而实现访问控制算法。但是,这类算法可能会使非法使用的网络被判定为安全网络,因此访问控制的准确度不高。为此,提出一种基于CP-ABE的可撤销属性加密访问控制算法,为实现访问控制,首先构建基于CP-ABE的可撤销属性加密访问控制的访问树,并通过CP-ABE完成访问控制的初始构建和密钥生成。在此基础上,为提高可撤销属性加密访问控制算法的访问控制效果,在加密算法以及解密算法中写入新文件创建、新用户授权、吊销用户、文件访问等方面过程的设计,实现基于CP-ABE的可撤销属性加密访问控制算法。实验结果表明,采用所提算法进行访问控制时耗时缩短,控制效果较好,且实现过程有所简化,对该领域的研究发展起到了积极作用。
个性化(α,l)-多样性k-匿名隐私保护模型
曹敏姿, 张琳琳, 毕雪华, 赵楷
计算机科学. 2018, 45 (11): 180-186.  doi:10.11896/j.issn.1002-137X.2018.11.028
摘要 ( 133 )   PDF(1801KB) ( 181 )   
参考文献 | 相关文章 | 多维度评价
针对传统隐私保护模型对个性化匿名缺乏考虑的问题,对现有的两种个性化匿名机制进行了分析。在k-匿名和l-多样性匿名模型的基础上,提出一种个性化(α,l)-多样性k-匿名模型来解决存在的问题。在该模型中,依据敏感程度的不同,对敏感属性的取值划分类别;设置相应的约束条件,并为特定的个体提供个性化的隐私保护。实验结果表明,所提模型在有效提供个性化服务的同时,具有更强的隐私保护能力。
一种混合云环境下基于Merkle哈希树的数据安全去重方案
张桂鹏, 陈平华
计算机科学. 2018, 45 (11): 187-192.  doi:10.11896/j.issn.1002-137X.2018.11.029
摘要 ( 145 )   PDF(2377KB) ( 284 )   
参考文献 | 相关文章 | 多维度评价
重复数据删除技术是云存储系统中一种高效的数据压缩和存储优化技术,能够通过检测和消除冗余数据来减少存储空间、降低传输带宽消耗。针对现有的云存储系统中数据安全去重方案所采用的收敛加密算法容易遭受暴力攻击和密文计算时间开销过大等问题,提出了一种混合云环境下基于Merkle哈希树的数据安全去重方案MTHDedup。该方案通过引入权限等级函数和去重系数来计算去重标签,高效地实现了支持访问控制的数据安全去重系统;同时通过执行额外的加密算法,在文件级和数据块级的数据去重过程中构造Merkle哈希树来生成加密密钥,保证了生成的密文变得不可预测。安全性分析表明,该方案能够有效地抵制内部和外部攻击者发起的暴力攻击,从而提高数据的安全性。仿真实验结果表明,MTHDedup方案能有效地降低密文生成的计算开销,减少密钥的存储空间,而且随着权限集数目的增加,性能优势将更加明显。
软件与数据库技术
一种基于文本分类和评分机制的软件缺陷分配方法
史小婉, 马于涛
计算机科学. 2018, 45 (11): 193-198.  doi:10.11896/j.issn.1002-137X.2018.11.030
摘要 ( 98 )   PDF(2592KB) ( 216 )   
参考文献 | 相关文章 | 多维度评价
开源软件项目的缺陷管理和修复是保障软件质量及软件开发效率的重要手段,而提高软件缺陷分配的效率是其中亟需解决的一个关键问题。文中提出了一种基于文本分类和评分机制的开发者预测方法,其核心思想是综合考虑基于机器学习的文本分类和基于软件缺陷从属特征的评分机制来构建预测模型。针对大型开源软件项目Eclipse和Mozilla的十万级已修复软件缺陷的实验表明,在“十折”增量验证模式下,所提方法的最好平均准确率分别达到了78.39%和64.94%,比基准方法(机器学习分类+再分配图)的最高平均准确率分别提升了17.34%和10.82%,从而验证了其有效性。
基于动态调整简化粒子群优化的组合测试用例生成方法
包晓安, 鲍超, 金瑜婷, 陈春宇, 钱俊彦, 张娜
计算机科学. 2018, 45 (11): 199-203.  doi:10.11896/j.issn.1002-137X.2018.11.031
摘要 ( 95 )   PDF(1345KB) ( 161 )   
参考文献 | 相关文章 | 多维度评价
优化的组合测试中的一个关键是生成的测试用例能够覆盖更多的组合,而粒子群算法在生成强组合覆盖用例方面有其独特的优势和能力。文中提出了一种基于动态调整简化粒子群优化的组合测试用例生成方法。该方法基于粒子群算法生成测试用例,结合混合的优先级one-test-at-a-time策略和基于动态调整的简化粒子群算法生成组合测试用例集,排除了速度因素对粒子优化过程的影响。定义了一个粒子收敛指标,以粒子群早熟收敛程度为依据来动态调整惯性权值,以防止粒子陷入局部最优和后期出现收敛速度慢的情况,从而提高粒子群算法所生成的覆盖表的覆盖组合能力。通过对比实验表明,基于动态调整的简化粒子群优化算法在用例规模和时间成本上具有一定的优势。
基于可变时间窗口的增量数据抽取模型
刘杰, 王桂玲, 左小将
计算机科学. 2018, 45 (11): 204-209.  doi:10.11896/j.issn.1002-137X.2018.11.032
摘要 ( 75 )   PDF(2787KB) ( 311 )   
参考文献 | 相关文章 | 多维度评价
基于合适的数据抽取模型持续不断地将变化的数据从各个数据源系统进行抽取集成,是各个异构系统之间进行数据共享融合的关键,也是构建增量式数据仓库来进行数据分析的关键。传统的时间戳变化数据捕获方式存在因数据抽取过程中发生异常而导致数据抽取失效,进而影响数据抽取效率的问题。鉴于此,文中借鉴时间窗口的思想,采用先抽取少量重复记录再去重的做法,对传统的时间戳增量数据捕获模型进行了改进,提出了基于可变时间窗口的增量数据抽取模型。该模型减少了异常对数据抽取的影响,增强了时间戳增量数据抽取ETL流程的可靠性,在一定程度上提高了数据的抽取效率。
方向感知的路网移动对象范围查询算法
董天阳, 尚跃辉, 程强
计算机科学. 2018, 45 (11): 210-219.  doi:10.11896/j.issn.1002-137X.2018.11.033
摘要 ( 84 )   PDF(2528KB) ( 175 )   
参考文献 | 相关文章 | 多维度评价
路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。
人工智能
基于合作作者与隶属机构信息的同名排歧方法
尚玉玲, 曹建军, 李红梅, 郑奇斌
计算机科学. 2018, 45 (11): 220-225.  doi:10.11896/j.issn.1002-137X.2018.11.034
摘要 ( 83 )   PDF(2117KB) ( 208 )   
参考文献 | 相关文章 | 多维度评价
同名排歧是实体分辨领域的重要研究内容之一,其旨在分辨出相同姓名对应的不同人。针对传统同名排歧方法需要丰富的信息以及无法解决信息缺乏时的排歧问题,提出了一种基于合作作者和隶属机构信息的同名排歧方法。根据作者间的合作关系以及作者与机构间的隶属关系构造实体关系图,采用广度优先搜索策略搜索图中两两同名作者间的有效路径;根据有效路径长度、数目及路径上边的类型,计算两个同名作者间的连接强度,并将其与阈值进行比较,实现同名排歧。实验结果表明,所提方法比当前最好的方法具有更好的同名排歧效果,且能够实现单一作者的同名排歧。
基于注意力卷积的神经机器翻译
汪琪, 段湘煜
计算机科学. 2018, 45 (11): 226-230.  doi:10.11896/j.issn.1002-137X.2018.11.035
摘要 ( 104 )   PDF(1466KB) ( 290 )   
参考文献 | 相关文章 | 多维度评价
现有神经机器翻译模型普遍采用的注意力机制是基于单词级别的,文中通过在注意力机制上执行多层卷积,从而将注意力机制从基于单词的级别提高到基于短语的级别。经过卷积操作后的注意力信息将愈加明显地体现出短语结构性,并被用于生成新的上下文向量,从而将新生成的上下文向量融入到神经机器翻译框架中。在大规模的中-英测试数据集上的实验结果表明,基于注意力卷积的神经机翻译模型能够很好地捕获语句中的短语结构信息,增强翻译词前后的上下文依赖关系,优化上下文向量,提高机器翻译的性能。
融合模拟退火机制的自适应花朵授粉算法
刘景森, 刘丽, 李煜
计算机科学. 2018, 45 (11): 231-237.  doi:10.11896/j.issn.1002-137X.2018.11.036
摘要 ( 89 )   PDF(2892KB) ( 229 )   
参考文献 | 相关文章 | 多维度评价
针对基本花朵授粉算法存在的不足,为提高其收敛速度与寻优精度,提出一种融合模拟退火机制的并且根据迭代进化来动态调整全局步长和局部繁衍概率的自适应花朵授粉算法。首先,在基本算法的全局授粉莱维飞行中使用变形指数函数的缩放因子来控制步长,使得花朵个体随迭代次数的增加自适应地进行位置更新;然后,通过瑞利分布函数结合迭代次数对繁衍概率影响因子进行改进,使得在避免早熟收敛的同时能够在后期向着最优解靠近;最后,在已改进的花朵授粉算法中融入模拟退火降温操作,这不仅增加了种群的多样性,而且改善了算法的整体寻优性能。仿真结果表明,改进后的算法具有较快的收敛速度和较高的收敛精度,寻优性能得到了显著提高。
两类动态信息模型及其应用
张凌, 任雪芳, 史开泉
计算机科学. 2018, 45 (11): 238-243.  doi:10.11896/j.issn.1002-137X.2018.11.037
摘要 ( 66 )   PDF(1325KB) ( 143 )   
参考文献 | 相关文章 | 多维度评价
P-集合(P-sets)是一类具有动态特征的集合模型,在P-集合中,元素的属性满足数理逻辑中的合取范式。P-集合是把动态特性引入到有限普通元素集合(有限Cantor set)X内,来改进有限普通元素集合X而提出的。逆P-集合(Inverse P-sets)是另一类具有动态特征的集合模型,在逆P-集合中元素的属性满足数理逻辑中的析取范式。逆P-集合是把动态特性引入到有限普通元素集合X内,来改进有限普通元素集合X而提出的。逆P-集合是P-集合的对偶形式。定义P-集合是一类动态信息模型,定义逆P-集合是另一类动态信息模型。文中主要介绍P-集合与逆P-集合的结构、生成与动态特征;给出P-集合、逆P-集合存在的事实;利用P-集合,给出具有属性合取范式的信息的递推-搜索发现与应用;利用逆P-集合,给出具有属性析取范式的信息的挖掘-获取与应用。P-集合、逆P-集合是研究动态信息(动态数据)应用的新模型、新方法。
基于核密度估计的K-CFSFDP聚类算法
董晓君, 程春玲
计算机科学. 2018, 45 (11): 244-248.  doi:10.11896/j.issn.1002-137X.2018.11.038
摘要 ( 155 )   PDF(1778KB) ( 333 )   
参考文献 | 相关文章 | 多维度评价
快速搜索和发现密度峰值的聚类算法(Clustering by Fast Search and Find of Density Peaks,CFSFDP)是一种新的基于密度的聚类算法,它通过发现密度峰值来有效地识别类簇中心,具有聚类速度快、实现简单等优点。针对CFSFDP算法的准确性依赖于数据集的密度估计和截断距离(dc)的人为选择问题,提出一种基于核密度估计的K-CFSFDP算法。该算法利用无参的核密度估计分析数据点的分布特征并自适应地选取dc,从而搜索和发现数据点的密度峰值,并以峰值点数据作为初始聚类中心。基于4个典型数据集的仿真结果表明,K-CFSFDP算法比CFSFDP,K-means和DBSCAN算法具有更高的准确度和更强的鲁棒性。
SNS:一种快速无偏的分层图抽样算法
朱君鹏, 李晖, 陈梅, 戴震宇
计算机科学. 2018, 45 (11): 249-255.  doi:10.11896/j.issn.1002-137X.2018.11.039
摘要 ( 98 )   PDF(4842KB) ( 389 )   
参考文献 | 相关文章 | 多维度评价
抽样作为一种有效的统计分析方法,常被用于大规模图数据分析领域以提升性能。现有的图抽样算法大多存在高度节点或低度节点过度入样的问题,较大程度地影响了算法的性能。复杂网络具有无标度特性,即节点的度服从幂律分布,节点个体之间存在较大差异。在基于点选择策略的抽样方法的基础上,通过结合节点的近似度分布策略,设计并实现了高效无偏的分层图抽样算法SNS。在3个真实的图数据集上的实验结果表明,SNS算法比其他图抽样算法保留了更多的拓扑属性,且执行效率比FFS更高。SNS算法在度的无偏性、抽样结果拓扑属性近似性方面的表现均优于现有算法。
基于稀疏表示和特征加权的大数据挖掘方法的研究
蔡柳萍, 解辉, 张福泉, 张龙飞
计算机科学. 2018, 45 (11): 256-260.  doi:10.11896/j.issn.1002-137X.2018.11.040
摘要 ( 124 )   PDF(1896KB) ( 242 )   
参考文献 | 相关文章 | 多维度评价
为了提高大数据挖掘的效率及准确度,文中将稀疏表示和特征加权运用于大数据处理过程中。首先,采用求解线性方程稀疏解的方式对大数据进行特征分类,在稀疏解的求解过程中利用向量的范数将此过程转化为最优化目标函数的求解。在完成特征分类后进行特征提取以降低数据维度,最后充分结合数据在类中的分布情况进行有效加权来实现大数据挖掘。实验结果表明,相比于常见的特征提取和特征加权算法,提出的算法在查全率和查准率方面均呈现出明显优势。
分级意见领袖下的微博信息传播与数学建模
黄贤英, 杨林枫, 刘小洋
计算机科学. 2018, 45 (11): 261-266.  doi:10.11896/j.issn.1002-137X.2018.11.041
摘要 ( 85 )   PDF(2122KB) ( 235 )   
参考文献 | 相关文章 | 多维度评价
为了有效地分析意见领袖在微博在线社交网络传播中所起的作用及微博信息传播的生命周期,提出了一种OLL分级意见领袖模型。首先,爬取微博数据,并进行数据统计分析;其次,将传播力构建为转发数、活跃度与粉丝量3个因素相关的函数,并建立一种基于层次分析的权重计算方法;最后,利用计算的传播力并结合OLL模型,对意见领袖传播作用及微博生命周期进行了实验分析。仿真结果表明:意见领袖在微博信息传播中有很强的传播效应,通过计算得出OLL模型仿真与3组真实数据的误差分别为9.6%,13.4%,4.5%,从而证明了所提OLL模型对于分析意见领袖在微博信息传播中的生命周期是合理且有效的。
图形图像与模式识别
基于监督学习深度自编码器的图像重构
张赛, 芮挺, 任桐炜, 杨成松, 邹军华
计算机科学. 2018, 45 (11): 267-271.  doi:10.11896/j.issn.1002-137X.2018.11.042
摘要 ( 79 )   PDF(5245KB) ( 244 )   
参考文献 | 相关文章 | 多维度评价
针对数字图像受损信息的重构问题,提出一种将经典无监督学习自编码器(Auto-Encoder,AE)用于监督学习的新方法,并对深度模型结构与训练策略进行了研究。通过设计多组监督学习单层AE模型,提出了逐组“递进学习”和“关联编码”的学习策略,构建了一个新的基于监督学习的深度AE模型结构;对于新模型结构,采用多对一(一个输入样本的多种形式对应一个输出)的训练方法代替经典AE中一对一(一个输入样本对应一个输出)的训练方法。将该模型的结构和训练策略用于部分数据受损或遮挡的图像中进行数据重构测试,提高了模型对受损数据特征编码的表达能力和重构能力。实验结果表明,提出的新方法对于受损及遮挡样本的图像具有良好的重构效果和适应性。
用于图像分割的多分类高斯混合模型和基于邻域信息的高斯混合模型
柴五一, 杨丰, 袁绍锋, 黄靖
计算机科学. 2018, 45 (11): 272-277.  doi:10.11896/j.issn.1002-137X.2018.11.043
摘要 ( 141 )   PDF(5277KB) ( 353 )   
参考文献 | 相关文章 | 多维度评价
高斯混合模型是一种简单有效且被广泛使用的图像分割工具。然而,传统的高斯混合模型在混合成分个数确定时的拟合结果不够精确;此外,由于没有考虑像素间的空间关系,导致分割结果易受噪声干扰,且分割精度不高。为弥补传统高斯混合模型的缺陷,文中提出多分类高斯混合模型和基于邻域信息的高斯混合模型用于图像分割。多分类高斯混合模型对传统混合模型进行二重分解:传统混合模型由M个分布加权混合得到,多分类混合模型进一步将M个分布中的每一个分布分解成R个分布。即多分类高斯混合模型由M个高斯分布混合组成,而这M个分布分别由R个不同的分布混合得到,提高了模型的拟合精度。基于邻域信息的高斯混合模型通过对模型中的先验概率和后验概率添加空间信息约束,增强了像素间的信息关联和抗噪性。采用结构相似性、误分率和峰值信噪比等指标来评价分割结果。通过实验发现:与现有的混合模型分割方法相比,文中方法大幅提高了分割精度,且有效地抑制了噪声干扰。
结合核函数与非线性偏微分方程的图像去噪方法
陈鹏, 张建伟
计算机科学. 2018, 45 (11): 278-282.  doi:10.11896/j.issn.1002-137X.2018.11.044
摘要 ( 124 )   PDF(4910KB) ( 190 )   
参考文献 | 相关文章 | 多维度评价
传统的非线性扩散滤波方法在图像去噪时使用传统的梯度算子,易导致细节缺失。针对该缺点,以非线性偏微分方程和图像结构信息为基础,构造一类带有自适应权值的非线性扩散滤波去噪方式。这种方式选用多方向的拉普拉斯算子模板,结合核函数,自适应地调节权重系数;利用非局部信息选取合适的搜索窗宽,以减小图像噪声的影响。实验证明,该方法既能较好地保存图像纹理细节,又可以达到很好的去噪效果。
一种新型的基于深度学习的单幅图像去雨方法
钟菲, 杨斌
计算机科学. 2018, 45 (11): 283-287.  doi:10.11896/j.issn.1002-137X.2018.11.045
摘要 ( 136 )   PDF(2320KB) ( 530 )   
参考文献 | 相关文章 | 多维度评价
雨滴严重影响了图像的视觉效果和后续的图像处理应用。目前,基于深度学习的单幅图像去雨方法能够有效挖掘图像的深度特征,其去雨效果优于传统方法;然而,随着网络深度的增加,网络容易出现过拟合的现象,使得去雨效果遇到瓶颈。文中在继承深度学习优点的基础上,学习有雨/无雨图像之间的残差,然后将残差与源图像进行重构,从而获得无雨图像。该方式大幅增加了网络深度,并加快了算法的收敛速度。分别利用通过不同方式获取的雨滴图像对所提方法进行实验验证,并将该方法与当前最新的去雨滴方法作比较,结果表明所提算法的去雨效果更好。
结构森林边缘检测与渗流模型相结合的混凝土表面裂缝检测
瞿中, 鞠芳蓉, 陈思琪
计算机科学. 2018, 45 (11): 288-291.  doi:10.11896/j.issn.1002-137X.2018.11.046
摘要 ( 94 )   PDF(3843KB) ( 290 )   
参考文献 | 相关文章 | 多维度评价
针对现有混凝土表面裂缝检测方法对不同环境下采集的裂缝图像集检测效果鲁棒性不强的问题,引入基于结构森林的学习框架来提取裂缝边缘,并融合改进的快速渗流算法检测裂缝,以保证检测精确率和效率。使用分段函数对彩色图像进行线性变换以增强裂缝,根据包含裂缝块的局部结构特征及彩色图像积分通道特征,利用结构森林边缘检测器快速提取裂缝边缘,同时结合改进的渗流模型快速渗流边缘并去噪。最后,利用形态学方法,连接较小断裂并填充孔洞。在收集的各类裂缝图像集上的实验结果表明,该算法处理速度快、鲁棒性好,且裂缝提取的精确度优于现有算法。
交叉与前沿
基于CUDA的k-means算法并行化研究
刘端阳, 郑江帆, 沈国江, 刘志
计算机科学. 2018, 45 (11): 292-297.  doi:10.11896/j.issn.1002-137X.2018.11.047
摘要 ( 79 )   PDF(1353KB) ( 353 )   
参考文献 | 相关文章 | 多维度评价
k-means算法在面对大规模数据集时,计算时间将随着数据集的增大而成倍增长。为了提升算法的运算性能,设计了一种基于CUDA(Compute Unified Device Architecture)编程模型的并化行k-means算法,即GS_k-means算法。对k-means算法进行了并行化分析,在距离计算前,运用全局选择判断数据所属聚簇是否改变,减少冗余计算;在距离计算时,采用通用矩阵乘加速,加快计算速度;在簇中心点更新时,将所有数据按照簇标签排序分组,将组内数据简单相加,减少原子内存操作,从而提高整体性能。使用KDDCUP99数据集对改进算法进行实验,结果表明,在保证实验结果的准确性的情况下,改进算法加快了计算速度,与经典的GPUMiner算法相比加速比提升5倍。
结合GPU技术的并行CP张量分解算法
武昱, 闫光辉, 王雅斐, 马青青, 刘宇轩
计算机科学. 2018, 45 (11): 298-303.  doi:10.11896/j.issn.1002-137X.2018.11.048
摘要 ( 106 )   PDF(2380KB) ( 379 )   
参考文献 | 相关文章 | 多维度评价
随着高维数据的涌现,张量和张量分解方法在数据分析领域中受到了广泛关注。然而,张量数据的高维度和稀疏特性,导致算法的复杂度较高,阻碍了张量分解算法在实际中的应用。许多学者通过引入并行计算来提升张量分解算法的计算效率。在现有研究的基础上,给出一种简化计算Khatri-Rao乘积的GPU并行CP张量分解算法,称为ParSCP-ALS。在模拟数据集和真实数据集上的实验结果显示,相比现有并行算法,文中设计的ParSCP-ALS算法能有效提高CP张量分解的计算效率,其中在Movielens数据集上的计算时间减少了约58%。
基于车联网的数据动态压缩采集策略
黄志清, 李梦佳, 田锐, 张严心, 王伟东
计算机科学. 2018, 45 (11): 304-311.  doi:10.11896/j.issn.1002-137X.2018.11.049
摘要 ( 81 )   PDF(2672KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
车联网能高效地实现感知区域的覆盖,因此被应用于大规模城市感知。同时,为了解决车联网难以传输大量数据的问题,一些研究者使用压缩感知对具有时空相关性的数据进行压缩。但是,目前在车联网中应用压缩感知的研究并没有考虑数据和车辆分布变化的特性,很可能导致不可接受的误差。为了保证数据的重构精度,提出面向车联网的动态压缩感知方法。该方法能自动分析感知对象的数据特征、车辆分布和观测数量之间的关系。在压缩感知的基础上加入观测数量调整功能,通过对当前感知对象的数据特征和车辆分布的分析,实时调整压缩感知中观测矩阵的参数,从而控制观测数据的数量,提升重构精度,实现更高质量的数据传输。实验表明与现有车联网中的压缩感知方法相比,面向车联网的动态压缩感知方法在重构精度上提升了15.3%。
用于求解正则(3,4)-SAT实例集的修正警示传播算法
佘光伟, 许道云
计算机科学. 2018, 45 (11): 312-317.  doi:10.11896/j.issn.1002-137X.2018.11.050
摘要 ( 74 )   PDF(1450KB) ( 161 )   
参考文献 | 相关文章 | 多维度评价
利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。