1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2015年第1期, 刊出日期:2018-11-14
  
综述
基于MapReduce框架的海量数据相似性连接研究进展
庞俊,于戈,许嘉,谷峪
计算机科学. 2015, 42 (1): 1-5.  doi:10.11896/j.issn.1002-137X.2015.01.001
摘要 ( 137 )   PDF(516KB) ( 431 )   
参考文献 | 相关文章 | 多维度评价
海量数据相似性连接作为海量数据处理的基本操作,在文本聚类、剽窃检测、实体解析等研究领域具有重要作用。另一方面,MapReduce编程模型因为具有良好的可扩放性、容错性和易用性,被广泛地应用于海量数据处理。因此,基于MapReduce框架的海量数据相似性连接查询技术成为海量数据处理领域的热点问题之一。首先,概括了海量数据固有特点和MapReduce编程框架的缺陷给现有相似性连接查询技术带来的巨大挑战;其次,提出了海量数据相似性连接的定义,按3种不同的分类标准对其进行了分类;接着,重点分析了集合、字符串和向量数据类型的海量相似性连接查询最新技术,并从效率和适用范围等方面分别对这些技术进行了比较;最后,讨论了海量数据相似性连接查询技术亟待解决的关键问题,并提出了一些有前景的解决方案。
无线传感器网络中的聚类协议综述
海沫,张艳梅,张悦今
计算机科学. 2015, 42 (1): 6-11.  doi:10.11896/j.issn.1002-137X.2015.01.002
摘要 ( 118 )   PDF(574KB) ( 316 )   
参考文献 | 相关文章 | 多维度评价
无线传感器网络中的聚类是将传感器网络划分成多个簇的过程,可用于延长网络生存期。每个聚类中都存在一个称为聚类头的节点。聚类头可由同一聚类中的节点选出,也可由网络设计人员预先指定。首先给出了无线传感器网络中聚类协议的分类特性;接着对已有的聚类协议从聚类头选择方式上进行了分类,并对已有的聚类协议从基本特性、聚类属性和聚类头选择方式3个方面进行了比较; 最后总结了已有聚类协议研究的不足之处,并指出了未来有待研究的关键问题。
时间Petri网的可调度分析及在FMS中的应用
翟正利,丁志军
计算机科学. 2015, 42 (1): 12-18.  doi:10.11896/j.issn.1002-137X.2015.01.003
摘要 ( 107 )   PDF(492KB) ( 335 )   
参考文献 | 相关文章 | 多维度评价
在实时系统中,检查任务执行的计划是否满足要求的时间约束称为可调度分析。通过把时间特性与其他行为特性分离,提出了一种 以时间Petri网建模的实时系统调度分析方法。如果特定任务的执行是可调度的,则可以计算任务执行的时间跨度,否则确定出不可调度的变迁以便于调整时间约束和纠正设计错误。提出了一种通过把复杂的任务序列分解成一些子序列来进行可调度性分析的综合时序分析技术,它不仅提高了效率,也有助于关于调度的可达性问题的讨论。讨论了柔性制造系统FMS中的车间装配子系统的可调度性。
基于参数化模型的设计计算服务
张明喜,左兵权,吴紫俊,黄正东
计算机科学. 2015, 42 (1): 19-22.  doi:10.11896/j.issn.1002-137X.2015.01.004
摘要 ( 96 )   PDF(921KB) ( 277 )   
参考文献 | 相关文章 | 多维度评价
针对工程设计中设计者需要学会操作过多的仿真分析软件并需要在具备其它学科专业知识的基础上为设计对象建模的问题,提出了一种让设计者借助网络服务平台完成工程设计计算任务的方法。设计者可以通过服务平台,选择由外部其他专业人员已构建好的参数化设计计算模型,在适当地进行远程外部定制函数链接和模型参数在线设置之后,即时获得服务器远程计算后的仿真计算结果。上述思想方法通过开发计算服务平台提供发动机设计仿真分析服务得到了验证。结果表明,这种服务平台可以为机械领域设计者进行诸多仿真计算工作,大大减轻了设计者的建模工作量,提高了设计工作效率,同时避免了因专业知识不够而无法正确建模的问题。
基于扩展DPN的CPS混成行为时效建模与综合评估
宋翠叶,杜承烈,李刚
计算机科学. 2015, 42 (1): 23-27.  doi:10.11896/j.issn.1002-137X.2015.01.005
摘要 ( 94 )   PDF(397KB) ( 316 )   
参考文献 | 相关文章 | 多维度评价
信息物理融合系统行为是一种由离散计算过程与连续物理动态过程深度融合并紧密交互的混成行为。在CPS设计早期对信息系统实体的信息实体的关键监控参数、实时指标,以及物理系统设施的连续行为规律进行综合评估,是这类系统进一步设计与实现的基础。基于扩展DPN语义,以某智能车CPS系统自主行进紧急避障过程为研究对象,建立了其信息物理混成行为的Petri网模型,以融合并集中体现各关键参数和指标的时序协作效应;通过对该模型的仿真运行,实现了CPS行为的在线观测与综合评估。该方法为CPS子系统关键设计指标的综合合理性评估及其组合设计提供了一种解决途径。
信息物理融合系统的动态多优先级调度
刘纯尧,张立臣
计算机科学. 2015, 42 (1): 28-32.  doi:10.11896/j.issn.1002-137X.2015.01.006
摘要 ( 125 )   PDF(379KB) ( 236 )   
参考文献 | 相关文章 | 多维度评价
信息物理融合系统(Cyber-physical Systems,CPS)的复杂和异构性给设计者带来了不少挑战,其中任务的多样性使得传统的调度策略不能满足CPS的性能需求。提出了专门针对基于大规模传感器网络的CPS的动态多优先级调度策略。根据任务类型分配4级缓存队列:第1级是来自控制器待处理的实时任务,拥有最高的可抢占式优先级;第2级是来自控制器待转发的实时任务,拥有次高的可抢占式优先级;第3级是来自其他节点待转发的非实时任务,拥有第三高的非抢占式优先级;第4级是来自本地待发送的非实时任务,拥有最低的非抢占式优先级。设计了抢占与非抢占混合的动态调度策略来减少任务的平均等待时间,加入了等待时间阈值机制来保证第4级任务的公平性。通过理论分析和仿真实验对调度策略的性能做了评价。仿真结果显示,动态多优先级调度策略在提高系统性能和稳定性上要优于传统优先级调度。
2013年全国理论计算机科学学术年会
基于随机Petri网的高性能计算系统作业调度及InfiniBand网络互连的性能分析
李智佳,胡翔,焦莉,王伟锋
计算机科学. 2015, 42 (1): 33-37.  doi:10.11896/j.issn.1002-137X.2015.01.007
摘要 ( 171 )   PDF(489KB) ( 440 )   
参考文献 | 相关文章 | 多维度评价
基于模型的分析技术在系统研究和设计中发挥着重要作用,它具有简单灵活、可扩展性强、高效等优点,其中随机Petri网在性能评价方面得到了广泛的应用。使用随机Petri网为高性能计算机的作业调度系统进行抽象和建模,并将其与InfiniBand网络互连结构相结合来整体分析用户作业的延迟等性能指标。实验表明,该方法是可行的,且具有相对较高的精度。
二阶多面体网格中关键特征控制的表面重建技术
刘鹤丹,王成恩
计算机科学. 2015, 42 (1): 38-43.  doi:10.11896/j.issn.1002-137X.2015.01.008
摘要 ( 112 )   PDF(972KB) ( 264 )   
参考文献 | 相关文章 | 多维度评价
针对基于二阶多节点多面体网格的表面重建过程中存在的准确拓扑及绘制、传输代价等问题,提出了一种基于关键特征控制的表面重建技术。研究并分析了二阶多节点多面体单元等参插值函数的性质特征,在网格单元棱边插值计算曲面轮廓点,在网格表面及体内提取曲面的几何特征关键点;根据3类插值关键点间的逻辑关系制定了令拓扑准确唯一的面片三角化规则及修复策略,设计了基于关键点的三角面片压缩索引结构。实验结果表明,该方法可准确计算并描述基于二阶多节点多面体网格单元的曲面几何拓扑结构,反映网格单元内部面片的真实凹凸性质,克服了拓扑二义性,具备对不同精度要求的适应性,并有效降低了绘制与传输代价。
基于Julia语言的并行计算方法初探
巩庆奎,张常有,张先轶,张云泉
计算机科学. 2015, 42 (1): 44-46.  doi:10.11896/j.issn.1002-137X.2015.01.009
摘要 ( 209 )   PDF(497KB) ( 523 )   
参考文献 | 相关文章 | 多维度评价
Julia语言是一种在MIT许可证下免费的开发中脚本语言(beta 0.2.0),目标是降低并行程序的编程难度。基于Julia现有语法机制,逐步增强Julia语法特性,结合公交线路的平均走行时间统计案例,研究Julia并行编程框架和程序逐步精化的方法。Julia程序支持本地多核心/多CPU并行计算。为充分发挥实验平台的计算潜能,尝试了提高Julia程序计算性能的策略。对案例程序的实验分析表明,Julia并行程序在管理计算核心方面耗费了一定的工作时间,但随着问题规模的增大,其影响可逐渐忽略,从而可获得接近线性的加速比。
考虑虚拟机间性能互扰基于排队网的多层Web应用性能分析模型
杨雷,代钰,张斌,王昊
计算机科学. 2015, 42 (1): 47-49.  doi:10.11896/j.issn.1002-137X.2015.01.010
摘要 ( 113 )   PDF(218KB) ( 250 )   
参考文献 | 相关文章 | 多维度评价
多层Web应用性能分析是实现资源动态分配和管理、保证多层Web应用性能的重要因素之一。传统的多层Web应用性能分析模型往往假设服务器部署在无性能互扰的服务器环境中且忽略了逻辑资源服务能力对多层Web应用性能的影响。随着云计算的发展,底层物理资源可以通过虚拟化方式形成虚拟资源并向外提供服务,这为多层Web应用的性能保证提供了有效支撑。因此,如何考虑虚拟机性能互扰以及逻辑资源服务能力对多层Web应用性能的影响已经成为云计算环境中多层Web应用性能分析所需解决的关键问题。为此,构建了一个基于排队网的多层Web应用性能分析模型,该模型通过丢弃队列来对目前多层Web应用性能分析模型在并发数限制方面进行扩展,在考虑虚拟机间性能互扰的基础上,提出了多层Web应用性能分析模型参数求解方法。实验结果验证了所提出的多层Web应用性能分析模型的有效性。
渐进式智能回溯向量化代码调优方法
赵博,赵荣彩,徐金龙,高伟
计算机科学. 2015, 42 (1): 50-53.  doi:10.11896/j.issn.1002-137X.2015.01.011
摘要 ( 110 )   PDF(682KB) ( 250 )   
参考文献 | 相关文章 | 多维度评价
为了充分发挥高性能计算机的计算能力,缓解程序员设计和编写并行程序的压力,扩充可用软件集合,设计并实现了利用交互界面深入挖掘程序中的可向量化语句,优化生成代码中的向量化语句,提高生成代码的执行效率。该方法对充分发挥高性能计算机的计算能力,增强系统可用性和扩展应用范围具有重要的意义,同时能够提供有效的辅助手段和工具支持。渐进式智能回溯向量化代码调优架构通过对用户提交的串行程序进行程序分析和变换,采用串行程序分析、数据依赖分析、向量化分析等技术手段,根据分析结果对程序进行变换和优化,自动生成最终的向量化代码。该方法通过分析串行程序中潜在的并行性,将其自动变换为等价的向量化代码形式,大大简化了程序员的工作。
高能物理计算环境中存储系统的设计与优化
程耀东,汪璐,黄秋兰,陈刚
计算机科学. 2015, 42 (1): 54-58.  doi:10.11896/j.issn.1002-137X.2015.01.012
摘要 ( 158 )   PDF(705KB) ( 427 )   
参考文献 | 相关文章 | 多维度评价
高能物理是典型的数据密集型计算,数据访问性能对整个系统至关重要并 与应用的计算模式密切相关。从剖析高能物理的典型计算模式入手,总结出其数据访问的特点,提出针对操作系统I/O调度、分布式文件系统缓存等多个因素的优化措施,优化后数据访问性能和CPU利用率明显提高。大规模存储系统对于元数据管理、数据可靠性、扩容等可管理性等功能也有较高要求,结合现有Lustre并行文件系统的不足,提出了Gluster的高能物理存储系统设计,在进行数据管理以及扩容等方面的优化后,系统已经正式投入使用,数据访问性能能够满足高能物理计算的需求,同时具有更好的可扩展性和可靠性。
基于CUDA的并行AES算法的实现和加速效率探索
费雄伟,李肯立,阳王东,杜家宜
计算机科学. 2015, 42 (1): 59-62.  doi:10.11896/j.issn.1002-137X.2015.01.013
摘要 ( 163 )   PDF(386KB) ( 957 )   
参考文献 | 相关文章 | 多维度评价
网络应用服务(尤其是电子银行和电子商务)需要数据加密提供安全通信。很多应用服务器面临着执行大量计算稠密的加密挑战。CUDA(统一计算架构)是在GPU进行并行和通用计算的平台,能够利用现有显卡资源,以低成本的方式提升加密性能。在Nvidia GeForce G210显卡上实现CUDA的AES(高级加密标准)并行算法并且在AMD Athlon 7850上实现串行AES算法。实现的AES并行算法避免了同一线程块的线程同步和通信,提升了GPU的加速性能,加速比要比Manavski的AES-128并行算法提升2.66~3.34倍。在大数据量(至32MB)加密环境下探索AES并行算法的性能模型,并首次从加速效率角度分析加速性能。该并行AES算法在16核的GPU上能最高达到15.83倍的加速比和99.898%的加速效率。
一种基于实测的自动负载建模算法
刘旭,莫则尧,安恒斌,曹小林,张爱清
计算机科学. 2015, 42 (1): 63-66.  doi:10.11896/j.issn.1002-137X.2015.01.014
摘要 ( 101 )   PDF(878KB) ( 300 )   
参考文献 | 相关文章 | 多维度评价
负载平衡是影响大规模并行计算效率的一个关键因素,准确的负载建模是负载平衡的基础。提出了一种基于实测的自动负载建模算法。该算法无需用户提供信息,具有良好的理论保证以及近似线性的计算复杂度和完全的并行性。2400个进程上的分子动力学模拟表明,该算法执行速度快,同时能够保证60%以上的负载平衡效率。
高能物理计算环境中KVM虚拟机的性能优化与应用
黄秋兰,李莎,程耀东,陈刚
计算机科学. 2015, 42 (1): 67-70.  doi:10.11896/j.issn.1002-137X.2015.01.015
摘要 ( 102 )   PDF(594KB) ( 470 )   
参考文献 | 相关文章 | 多维度评价
高能物理是典型的高性能计算的应用,对CPU计算能力要求很高,并且CPU利用率的高低直接影响高能物理的计算效率。虚拟化技术在实现资源共享和资源高利用率方面表现出很大的优势。基于KVM(Kernel-based Virtual Machine)虚拟机进行性能测试和性能优化。首先对KVM虚拟机的处理器、磁盘IO和网络IO等参数进行测试,给出虚拟机和物理机的性能差异和定量分析,然后从KVM虚拟机架构上分析影响KVM性能的各种因素,从硬件级、内核级对影响性能的因素包括扩展页表EPT(Extented Page Table)和CPU的亲和性(CPU affinity)展开研究,以对KVM进行性能优化。优化结果表明,KVM的CPU性能的损失率可以降低至3%左右。最后,给出了高能物理计算的虚拟集群,结果显示虚拟机群的计算性能能够满足高能物理计算的需求。
程序阶段性分析和阶段检测技术
张海博,安虹,贺松涛,孙涛,王涛,彭毅,程亦超
计算机科学. 2015, 42 (1): 71-74.  doi:10.11896/j.issn.1002-137X.2015.01.016
摘要 ( 175 )   PDF(572KB) ( 297 )   
参考文献 | 相关文章 | 多维度评价
对称多处理器的飞速发展和近年来提出的动态异构处理器(DHMP)为性能优化提供了新的机遇。一个机遇是找出程序每个阶段的性能瓶颈,提出了静态程序阶段分析方法,即通过分析结构参数和计算相似度矩阵来找出程序每个阶段的资源瓶颈;另一个机遇是给出动态异构处理器重构的时间节点,提出了DPDA和HTPD两种动态阶段检测算法,检测出阶段的变化能够为动态可重构处理器提供重构的时间节点。DPDA算法效果很好且软硬件实现代价小,而HTPD算法是目前为止第一个使用统计学方法进行动态检测阶段的算法。实验表明,与BBV相比,DPDA和HTPD能避免BBV离线、动态算法需添加额外硬件、结果与编译器相关等限制,并且阶段划分的稳定性和正确率与BBV相当。DPDA和HTPD算法由于本身不依赖额外硬件,因此都能直接在主流处理器和动态异构处理器(DHMP)中使用。
在Intel Knights Corner和NVIDIA Kepler架构上OpenACC的性能可移植性分析
王一超,秦强,施忠伟,林新华
计算机科学. 2015, 42 (1): 75-78.  doi:10.11896/j.issn.1002-137X.2015.01.017
摘要 ( 116 )   PDF(321KB) ( 460 )   
参考文献 | 相关文章 | 多维度评价
OpenACC 是一套基于指导语句方式的并行编程语言标准。编程者可以通过在代码中添加符合该标准的指导语句,经OpenACC编译器的编译,将串行代码并行化地移植到加速器或者协处理器上,进而获得异构加速器所带来的加速效果。OpenACC与CUDA和OpenCL这类异构并行编程技术的不同之处在于,它的目的是使编程者在应用移植过程中不需要考虑加速器或协处理器的底层硬件架构,从而降低编程难度。同时它也具有仅需维护一套代码便可在不同硬件平台上运行的优良跨平台性。因此,OpenACC是一个值得研究的并行编程标准。如今的异构加速硬件设备呈现出多元化趋势。在2013年11月的Top500榜单上排名第一的“天河二号”使用了48000块构建在Intel Knights Corner架构之上的协处理器。与此同时,发布不久的NVIDIA公司最新的Kepler架构GPU产品由于多年来的GPU市场积累也迅速形成了可观的用户群体。对于并非追求性能极限的应用移植者而言,寻求应用性能和移植简易性之间的平衡是相当重要的议题。只需要编写一套代码便可运行在这两种硬件平台上的OpenACC正迎合了用户在移植简易性上的需求。解决了移植的简易性之后,同一个应用在不同硬件平台上的性能表现便成了用户最想了解的问题。通过实验和构建性能模型向读者展示使用OpenACC移植的应用在Intel Knights Corner和NVIDIA Kepler架构硬件上的性能可移植性。
GF(2m)上椭圆曲线标量乘的硬件结构实现
邬贵明,郑方,谢向辉,吴东,严忻恺
计算机科学. 2015, 42 (1): 79-81.  doi:10.11896/j.issn.1002-137X.2015.01.018
摘要 ( 116 )   PDF(299KB) ( 422 )   
参考文献 | 相关文章 | 多维度评价
基于Reyhani-Masoleh提出的GF(2m)高斯正规基乘法实现了三拍非流水的正规基乘法器,并基于该乘法器实现了一种高性能López-Dahab标量乘硬件结构。Reyhani-Masoleh算法利用乘法矩阵的对称性降低了乘法的复杂度;而López-Dahab标量乘算法由于采用投影坐标,计算速度快且可以有效降低存储需求。基于Reyhani-Masoleh乘法器的López-Dahab标量乘结构可以有效利用两种算法的优势,可以达到目前最好的标量乘硬件结构的性能。
一种基于GPU集群的深度优先并行算法设计与实现
余莹,李肯立,郑光勇
计算机科学. 2015, 42 (1): 82-85.  doi:10.11896/j.issn.1002-137X.2015.01.019
摘要 ( 149 )   PDF(330KB) ( 448 )   
参考文献 | 相关文章 | 多维度评价
深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低。为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排。提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡。为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作。实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销。在一个GPU集群中,它可以对含有数十亿节点的图有效地执行分布式DFS。
基于布谷鸟搜索的多处理器任务调度算法
杨辉华,张晓凤,谢谱模,韦向远
计算机科学. 2015, 42 (1): 86-89.  doi:10.11896/j.issn.1002-137X.2015.01.020
摘要 ( 138 )   PDF(311KB) ( 275 )   
参考文献 | 相关文章 | 多维度评价
多处理器系统在高性能计算中扮演着重要角色。为提高系统的并行性能,基于布谷鸟搜索算法,提出一种新的多处理器任务调度算法。该算法以全部任务的最晚完成时间最小为目标,利用基于任务优先权的编码方式使连续的布谷鸟搜索算法适用于离散的多处理器任务调度问题。实验结果表明,所提算法不仅求解质量高,而且求解速度最快,与目前广泛采用的遗传算法和粒子群算法相比其执行时间缩短超过60%。
基于Pthreads的并行DSRC压缩算法设计与实现
詹科,张云泉,王婷,郑晶晶,张鹏
计算机科学. 2015, 42 (1): 90-91.  doi:10.11896/j.issn.1002-137X.2015.01.021
摘要 ( 126 )   PDF(235KB) ( 285 )   
参考文献 | 相关文章 | 多维度评价
高通量测序仪产生大量的DNA数据,FASTQ是被广泛使用的 存储DNA数据的数据格式。对FASTQ格式的数据进行压缩处理,能有效地节省存储空间。DSRC算法具有压缩比高的优点,因此对DSRC算法进行并行能提高压缩FASTQ格式的DNA数据的效率。基于Pthreads,实现了并行DSRC算法。测试结果表明,当使用4线程时加速比达到3.5。
混合云中的一个高效协调器
王宗江,郑秋生,曹健
计算机科学. 2015, 42 (1): 92-95.  doi:10.11896/j.issn.1002-137X.2015.01.022
摘要 ( 85 )   PDF(655KB) ( 228 )   
参考文献 | 相关文章 | 多维度评价
云计算提供了4种部署模型:公有云、私有云、社区云和混合云。通常,一个私有云中可用的资源是有限的,因此云用户不得不从公有云租用资源。这意味着云用户将会产生额外的费用。越来越多的企业选择混合云来部署它们的应用。在混合云中,为了实现用户的利益最大化,必须满足使用资源的费用最小化和用户的QoS,为此为混合云用户提供了一个既能最小化资源费用又能保证满足QoS的资源分配方法。实验结果表明,该算法在保持低操作成本的同时还满足了用户的QoS。
网络与通信
B-RPL:低存储开销的RPL路由协议
杨红,朱红松,孙利民
计算机科学. 2015, 42 (1): 96-100.  doi:10.11896/j.issn.1002-137X.2015.01.023
摘要 ( 101 )   PDF(663KB) ( 365 )   
参考文献 | 相关文章 | 多维度评价
针对低功耗易失网络(Low-power and Lossy Networks,LLNs)中存储式RPL路由的大存储开销问题,提出了一种基于存储式RPL的改进型路由协议B-RPL。该协议充分利用了LLNs网络无线通信的广播特性,将RPL中的路由表简化为目的节点集合,并利用布隆过滤器(Bloom Filter)管理该目的节点集合,极大地减少了节点的存储开销。此外,B-RPL还包含了一些针对网络拓扑动态变化的自适应机制。实验及分析表明:与存储式RPL相比,B-RPL节约了97.8%的存储开销,而通信开销仅增加2.4%。
一种基于二分编码的无线传感器与执行器网络移动覆盖算法
杜景林,郑若钦,谢立,李娟
计算机科学. 2015, 42 (1): 101-105.  doi:10.11896/j.issn.1002-137X.2015.01.024
摘要 ( 101 )   PDF(407KB) ( 215 )   
参考文献 | 相关文章 | 多维度评价
在无线传感器与执行器网络中,可以通过调整剩余节点的位置来提高目标区域覆盖率,以更好地为sensor节点服务。提出了一种基于二分编码的网络移动覆盖算法(SMR算法)。在每次搜索中,试探性地调整失效节点区域的临近执行器节点位置来寻找最佳位置,重复此搜索过程直到覆盖数不再增加,以实现近似的局部最优覆盖。本算法提高了剩余节点的覆盖率,减少了执行器节点移动的消耗,与已有算法相比也表现出了较好的性能。
基于rLFA技术的性能优化及重路由选择算法研究
王明鸣,孟相如,徐有,崔文岩
计算机科学. 2015, 42 (1): 106-109.  doi:10.11896/j.issn.1002-137X.2015.01.025
摘要 ( 144 )   PDF(403KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
为进一步提高网络单故障快速恢复能力,基于改进的Remote Loop-Free Alternates(rLFA)重路由技术,提出一种采用混沌粒子群并考虑网络物理传输代价和拥塞代价的重路由选择算法。首先基于rLFA的隧道建立方法对其进行改进,结合引入隧道技术的链路增补方法来实现故障全覆盖,通过设置权重因子来保证在不同业务量下的重路由选择针对性。实验表明,改进的rLFA能进一步提高网络单故障覆盖率,同时结合链路增补方法在保证故障完全覆盖的情况下能够大幅度减少链路增补数量;路由选择算法能够动态选择不同业务量下的重路由路径,在提高网络单故障环境下的传输效率的同时也实现了负载均衡。
两个点对点(PTP)网络并存时的自由度研究
周璐娜,刘锋,曾连荪
计算机科学. 2015, 42 (1): 110-112.  doi:10.11896/j.issn.1002-137X.2015.01.026
摘要 ( 111 )   PDF(266KB) ( 246 )   
参考文献 | 相关文章 | 多维度评价
自由度来源于使用多天线系统时引入的空间复用概念,体现了通信系统对空间资源的利用效率。认知无线电中,主、次网络的同时存在,将使其在传输过程中相互干扰,从而降低系统自由度。为此,研究了两个点对点网络(PTP)并存时的自由度以及对应的干扰消除方法。得出在主网络的自由度资源还有空余时,次网络在同一频谱资源上利用剩余的空间资源进行消息传递时可获得的自由度范围;同时给出了当主网络的自由度资源完全占用时,次网络可获得的最大自由度。在此基础上,还研究了主、次网络在接收端进行协作,通过某种方式借用主网络剩余的天线来提高整个网络的自由度。分析比较表明,当M1≤N1或N1≥M1+M2 时,接收端的协作能提高网络的总自由度。
基于P2P环境下的Web服务选择信任模型研究
陈卫东,李敏强,赵庆展
计算机科学. 2015, 42 (1): 113-118.  doi:10.11896/j.issn.1002-137X.2015.01.027
摘要 ( 105 )   PDF(449KB) ( 248 )   
参考文献 | 相关文章 | 多维度评价
为了适应互联网服务资源“成长、自治”的自然特征,以基于P2P技术的电子商务供应链等为代表的自组织系统的实践表现出巨大潜力,但自组织系统的动态开放等固有特征使其面临严重的行为可信问题。提出了一种P2P环境的基于反馈的Web服务选择信任模型。基于用户对服务的评价,利用局部信誉及全局信誉基本数据,综合考虑时间等因素,结合k-mean聚类算法分类比较用户的服务评价与第三方评价、历史评价等,建立了基于信誉的信任系统。设计了服务的可信模型与评价者的可信模型,并根据不同情况使用适当处罚函数,得到Web services使用的信誉评价模型。通过实验分析发现P2P环境下的基于信誉的信任系统为企业应用提供了自组织服务管理的基础,同时信誉评价模型为用户选择服务提供了科学可靠的依据。系统对恶意用户的使用有一定的对抗能力,能保证P2P环境下服务的可持续运营。
基于核心图的标签传播算法
马杰良,韩路,潘贞贞,宋艳
计算机科学. 2015, 42 (1): 119-121.  doi:10.11896/j.issn.1002-137X.2015.01.028
摘要 ( 154 )   PDF(584KB) ( 339 )   
参考文献 | 相关文章 | 多维度评价
网络中的社团发现是当前的一个研究热点。在众多社团发现算法中,标签传播算法因简单快速而被广泛应用,但标签传播算法也存在结果稳定性较差的问题。基于此对标签传播算法的初始化过程进行改进,提出了基于核心图的标签传播算法。通过计算图中任意两点的k阶公共邻居,将具有最大相似性的节点及k阶邻居作为初始核心社团,并为其分配初始标签。通过上述过程,提取一些较为紧密的子结构来作为标签传播的初始社团,并给这些结构分配初始社团标签。在真实网络中的实验结果表明,该算法可以大幅提高结果的稳定性。
一种基于EMD和RVM的自相似网络流量预测模型
柏骏,夏靖波,赵小欢
计算机科学. 2015, 42 (1): 122-125.  doi:10.11896/j.issn.1002-137X.2015.01.029
摘要 ( 107 )   PDF(308KB) ( 249 )   
参考文献 | 相关文章 | 多维度评价
针对自相似网络流量提出了一种基于EMD(经验模态分解)和RVM(相关向量机)的自相似时间序列预测模型。该模型利用EMD将滑动窗口内的小时间尺度网络流量序列分解为多个IMF(固有模态函数)分量,以去除流量序列长相关性;然后采用RVM 对其中的高频分量进行拟合,而对低频分量则使用ARMA构建预测模型;最后合成各分量的预测结果。实验表明,该模型能准确地预测流量时间序列的幅值及其趋势,与同类型预测方法相比,其预测性能更好。
DPA:一种动态环境下QoS单播路由算法
易猛,陈庆奎,章刚,赵海燕
计算机科学. 2015, 42 (1): 126-128.  doi:10.11896/j.issn.1002-137X.2015.01.030
摘要 ( 91 )   PDF(331KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
目前Internet网络环境下,网络参数的随时变化容易造成路由过期,从而使提供的QoS路由无效,为此提出了一种适合参数动态变化的单播QoS路由算法(DPA),该算法在路径代价随时间不断变化的情况下能够自主地选择最优路由节点,解决多约束QoS单播路由选择不精确的问题。实验表明,本路由算法自适应性和扩展性较好,同时在路由选择方面比传统的路由算法能够提供更好的QoS路由。
信息安全
基于CBR和描述逻辑的网络安全应急响应
蒋菲,古天龙,徐周波,常亮
计算机科学. 2015, 42 (1): 129-136.  doi:10.11896/j.issn.1002-137X.2015.01.031
摘要 ( 112 )   PDF(853KB) ( 262 )   
参考文献 | 相关文章 | 多维度评价
网络安全应急响应是未来信息安全策略的重心。目前应急响应主要依靠应急响应团队和安全管理者,他们虽能够有效处理部分安全事件,但不能给出在具体环境下 合理、快速、有效地处理 安全事件的方法。针对该问题,提出了智能化的基于案例推理和描述逻辑的网络安全应急响应方法,用以实现对具体安全事件的自动处理。首先用描述逻辑刻画网络安全应急响应领域知识,然后设计了基于细化算子和细化图的相似度匹配算法,给出了基于案例的推理(Case based reasoning,CBR)在应急响应中的具体实现过程,最后用具体实例检验了提出的方法。结果表明该方法具有清晰语义、自动分类概念和良好推理能力等特性,能够从过去的安全事件中获得目前所遇到的安全事件的解决方案,并能够给出具体环境下安全事件的处理方法。
一种基于椭圆曲线的轻量级身份认证及密钥协商方案
郭松辉,牛小鹏,王玉龙
计算机科学. 2015, 42 (1): 137-141.  doi:10.11896/j.issn.1002-137X.2015.01.032
摘要 ( 215 )   PDF(414KB) ( 547 )   
参考文献 | 相关文章 | 多维度评价
无证书公钥密码体制不存在用户密钥托管问题,也不需要使用证书,可以解决传统公钥密码体制在应用过程中耗时耗资源都比较多的问题。基于素域上的椭圆曲线加法群,提出了一个无证书的身份认证及密钥协商方案,其主要包括认证协议与核心算法。该方案消除了双线性对运算,完成双向认证只需要两次通信,提高了认证和密钥产生的效率,效率比已有协议提高了至少10%;充分利用椭圆曲线上的点加运算,加快了计算速度,在不考虑网络通信耗时的情况下双向认证及产生共享密钥只需要20ms左右。同时该方案能满足已知会话密钥的通信安全、主密钥的前向保密性、抗密钥泄露后的伪装攻击等安全属性。该方案尤其适合于不活跃网络对象之间的安全通信。
基于信息熵的加密会话检测方法
陈利,张利,班晓芳,梁杰
计算机科学. 2015, 42 (1): 142-143.  doi:10.11896/j.issn.1002-137X.2015.01.033
摘要 ( 124 )   PDF(275KB) ( 1533 )   
参考文献 | 相关文章 | 多维度评价
传统协议分析方法在检测网络加密会话时大都通过端口识别,在加密应用使用非常规端口或者在周知明文端口出现加密流量时无法进行有效的检测。为此,提出基于信息熵的加密会话检测方法。该方法先对数据流按端口进行会话重组,再计算会话数据包字符熵,进而统计出整个会话字符熵,判断熵值是否属于训练模型正态分布置信区间,通过信息分布均匀度来检测加密会话。实验表明,该方法无需特征指纹库,且检测准确率高,并能实现实时检测和处理。
基于标签速度和滑动子窗口的RFID数据清洗算法
顾韵华,高宝,张俊勇,杜杰
计算机科学. 2015, 42 (1): 144-148.  doi:10.11896/j.issn.1002-137X.2015.01.034
摘要 ( 161 )   PDF(403KB) ( 302 )   
参考文献 | 相关文章 | 多维度评价
为提高非匀速RFID(Radio Frequency Identification)数据流情形下的数据清洗准确性,在传统数据清洗算法SMURF(statistical SMoothing for unreliable RFID data)的基础上,提出了一种基于标签速度和滑动子窗口的RFID数据清洗方法。该方法考虑到标签速度对滑动窗口调整的影响,依据标签速度动态调整置信度δ,同时进一步划分 滑动窗口,对子窗口中的标签数据进行统计采样,并将其与整个滑动窗口的统计采样处理结果联合起来,以及时检测出标签的跃迁现象,从而准确判断标签的运动情况。实验表明,该方法有效地降低了平均错误率和积极读现象的出现频度,提高了数据准确性。
一种适用于嵌套加密协议分析的强认证测试方法
宋巍涛,胡斌
计算机科学. 2015, 42 (1): 149-154.  doi:10.11896/j.issn.1002-137X.2015.01.035
摘要 ( 113 )   PDF(595KB) ( 236 )   
参考文献 | 相关文章 | 多维度评价
认证测试是一种新型的在串空间模型基础上提出来的用于分析协议认证属性的形式化方法,该方法因简单实用而受到学者的广泛关注,但其不能分析协议中认证测试组件嵌套加密的情况,这极大地限制了它的应用范围。而现存的针对该局限性的改进方案,由于没有从本质上对串空间模型中关于消息项结构关系方面的语义进行完善,很难彻底突破认证测试的局限性。为此,通过在串空间模型中引入等价类、类组件、安全加密元及安全包裹元等概念,提高了串空间刻画消息项之间及内部结构关系的能力,并结合实例来阐明引入这些概念的必要性。在此基础上,提出一种可以分析测试组件嵌套加密的通用的认证测试方法,并从形式化证明与实例分析两方面验证了新测试方法的正确性与有效性。
基于分层API调用的Android恶意代码静态描述方法
魏松杰,杨铃
计算机科学. 2015, 42 (1): 155-158.  doi:10.11896/j.issn.1002-137X.2015.01.036
摘要 ( 77 )   PDF(418KB) ( 670 )   
参考文献 | 相关文章 | 多维度评价
针对Android APK的静态描述,目前主要是采用权限、数据以及API调用序列的方法,而忽视了代码本身的层级结构,因此无法有效地通过这些静态特征来揭示应用程序的可能行为和恶意属性。设计并实现了一种基于代码层次结构的系统API调用描述方法,其主要是提取APK文件中API调用在应用包、对象类、类函数层面的信息,并将这些信息以树形结构表示,通过将不同应用程序的描述树进行逐层对比来计算相似度,揭示恶意应用程序由于在类型和族群上的差异所带来的API调用特征上的区别,从而为Android应用程序的特征描述和恶意检测提供新的视角。实验采用真实多样的已知Android恶意程序来验证描述方法的正确性和系统实现的效果,分析了不同层次和检测情况下该方法的利弊以及可能的改进之处。
基于动态分集的中国墙模型研究
姜路,鹤荣育,魏彦芬
计算机科学. 2015, 42 (1): 159-163.  doi:10.11896/j.issn.1002-137X.2015.01.037
摘要 ( 103 )   PDF(386KB) ( 333 )   
参考文献 | 相关文章 | 多维度评价
BN(Brewer-Nash)中国墙模型对写操作有着严格的限制,它只从客体方面考虑了冲突关系,且需要事先静态划分访问区域,不适宜动态变化的系统。定义“分集”的概念,并在此基础上提出基于分集的中国墙模型,该模型能够从主体和客体两方面出发研究系统中的冲突关系,并动态地扩充访问区域。证明了该模型是冲突安全的,并通过一个实例说明了该模型的应用。
基于游程检测与快速傅里叶变换的加密比特流识别
邢萌,吴杨,王韬,李进东
计算机科学. 2015, 42 (1): 164-169.  doi:10.11896/j.issn.1002-137X.2015.01.038
摘要 ( 115 )   PDF(479KB) ( 246 )   
参考文献 | 相关文章 | 多维度评价
为获得链路层中的加密与未加密比特流样本,首先提出了基于游程检测方法的链路层加密比特流识别方案,解决了未知网络环境下的加密与未加密比特流样本获取问题。同时,采用快速傅里叶变换分别对加密与未加密比特流样本进行处理,根据最大差异原则确定了快速傅里叶变换结果的特征点位置,并基于正态分布原理确定了特征点的取值,建立了特征模板。最后,以某无线网络链路层加密比特流为识别对象,对提出的方案的有效性进行了验证。结果表明,该方案对链路层加密与未加密比特流的识别率均可达到95%以上。
主观信任评估模型与决策方法的研究
杨玉丽,彭新光,王峥
计算机科学. 2015, 42 (1): 170-174.  doi:10.11896/j.issn.1002-137X.2015.01.039
摘要 ( 136 )   PDF(418KB) ( 227 )   
参考文献 | 相关文章 | 多维度评价
在网上交易中,针对传统的信用度评估方法不能有效地描述商家信用度的时效性和风险性等特征的问题,提出基于多属性正态云的信任评估方法。首先生成包含5个等级的信任基云;然后引入时间衰减因子,分别从平均水平和变化率两个角度描述商家信用度历史信息,生成对应的声誉云和风险云;最后,由声誉云和风险云合成综合信任云,并计算其信任等级及信任分值。实验结果表明,该评估模型具有可行性和有效性,可为用户提供直观、有效的信任决策依据。
软件与数据库技术
基于群体智慧的软件开发间层模型及其架构实现
何炎祥,杨建康,鲍海洲,冉亚洛,郭波波,杨建喜
计算机科学. 2015, 42 (1): 175-179.  doi:10.11896/j.issn.1002-137X.2015.01.040
摘要 ( 99 )   PDF(452KB) ( 221 )   
参考文献 | 相关文章 | 多维度评价
减少或者避免重复劳动是应对软件危机的一个重要方法。对软件重用技术进行研究,以避免重复劳动为目标,提出利用群体智慧的间层模型来试图解决软件危机问题。提出的柠檬框架是间层模型的一个实现,具有一定的实用性。同时柠檬框架也是正在进行的一个项目。
一种策略驱动的BPEL流程异常处理框架
王权于,吕国斌,应时,周峰
计算机科学. 2015, 42 (1): 180-186.  doi:10.11896/j.issn.1002-137X.2015.01.041
摘要 ( 107 )   PDF(659KB) ( 245 )   
参考文献 | 相关文章 | 多维度评价
如何提高BPEL流程异常处理的开发效率是策略驱动的BPEL流程异常处理方法亟待解决的关键问题之一。首先分析了基于策略的BPEL流程异常处理机制,设计了一种新的BPEL流程异常处理策略描述语言BPEH/PDL,然后结合BPEH/PDL异常处理策略,给出了一种新的BPEL流程异常处理框架BPEH/F,它具有一定的应用意义。
基于相识度的恶意代码检测
杜楠,韩兰胜,付才,张忠科,刘铭
计算机科学. 2015, 42 (1): 187-192.  doi:10.11896/j.issn.1002-137X.2015.01.042
摘要 ( 104 )   PDF(445KB) ( 279 )   
参考文献 | 相关文章 | 多维度评价
特征码的识别方法仅能识别已知的恶意代码,并未解决恶意代码的判别问题。当前基于行为的扫描和启发式扫描也只是关注恶意代码的单个的危险行为点,误报率很高。侧重挖掘行为之间的关系,采用矩阵将待测代码的行为及行为之间的关系进行描述、测量,由此提出一种基于相识度的恶意代码检测方法。相识度是系统对待测代码的熟悉程度。根据相识度的大小来判断待测代码是否为恶意代码,相识度越大,待测代码是恶意代码的可能性就越小。在此基础上,提出了相应的恶意代码检测算法,通过实例验证了该方法的有效性。
基于场景的联锁软件形式化模型生成方法
董昱,高雪娟
计算机科学. 2015, 42 (1): 193-195.  doi:10.11896/j.issn.1002-137X.2015.01.043
摘要 ( 119 )   PDF(319KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
为保证列车运行安全和旅客生命财产安全,对车站联锁控制系统进行有效的分析、验证和测试是必不可少的,而形式化模型是联锁系统分析、验证和测试的基础。以计算机联锁软件的UML半形式化模型为基础,以事件确定有限自动机模型作为描述系统的形式化模型,研究UML2.0顺序图转换为事件确定有限自动机模型的方法。首先选取一组与交互行为相关的全局变量作为状态向量来分析和消解顺序图各个场景的消息以及不同场景间的同一消息的前后置状态向量值是否存在矛盾,从而得到一致性的需求场景;然后提取各对象的事件序列生成对应的事件确定有限自动机;最后通过组合系统中对象的自动机模型得到系统的事件确定有限自动机模型。该方法改善了安全苛求软件的设计与开发,为软件质量评估提供了技术支撑。
基于本体的构件化软件演化信息获取及度量研究
钟林辉,宗洪雁
计算机科学. 2015, 42 (1): 196-200.  doi:10.11896/j.issn.1002-137X.2015.01.044
摘要 ( 116 )   PDF(495KB) ( 247 )   
参考文献 | 相关文章 | 多维度评价
软件演化信息是一种重要的、能反映软件变化历史的信息。然而,传统的软件演化信息以文件或者项目作为跟踪软件变化的基本单元,不能有效地支持构件化软件演化信息的存储和检索。提出了采用本体概念表示构件化软件演化信息的策略,并利用Jena推理机实现构件化软件演化信息的获取。该方法不仅能检索构件化软件的基本演化信息,而且可以通过定义规则的方式检索出蕴含的演化信息。同时,文中也提出了一种构件化软件演化度量的模型,该模型通过对演化属性的计算分析来预测构件化软件的演化趋势。
室内概率阈值反向最近邻查询
王丽,秦小麟,许建秋
计算机科学. 2015, 42 (1): 201-205.  doi:10.11896/j.issn.1002-137X.2015.01.045
摘要 ( 114 )   PDF(458KB) ( 221 )   
参考文献 | 相关文章 | 多维度评价
室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求。目前已有文献提出了针对室内空间环境的范围查询和最近邻查询, 而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究。为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型。在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率。
M-相点数据索引SPindex
陈瑛,陈钊滢,叶小平
计算机科学. 2015, 42 (1): 206-209.  doi:10.11896/j.issn.1002-137X.2015.01.046
摘要 ( 99 )   PDF(363KB) ( 246 )   
参考文献 | 相关文章 | 多维度评价
空间数据索引是空间数据管理的关键技术,其性能决定空间数据库的使用效率。由于可将时间维度转化为空间维度处理,空间数据索引在时空数据库和移动对象数据库管理方面有广泛的应用。因此研究空间数据索引具有理论意义和应用价值。现有空间索引多是基于R-树技术,为快速有效地访问海量空间数据,提出一种基于空间相点分析的空间数据索引方法SPindex。首先,将空间区域所对应的最小外接矩形(MBR)集合与相平面中相点集合建立对应;其次,通过相点关系对相应MBR进行相互位置分析,进而提出一种基于相点的空间数据结构MROB;以此为基础,提出一种新的基于M-相点分析的空间数据索引SPindex;最后,通过与常规索引进行实验,评估表明了该工作的可行性与有效性。
人工智能
情感不确定词句的分类方法比较研究
李飏,苗夺谦,张志飞
计算机科学. 2015, 42 (1): 210-214.  doi:10.11896/j.issn.1002-137X.2015.01.047
摘要 ( 101 )   PDF(632KB) ( 304 )   
参考文献 | 相关文章 | 多维度评价
语义不确定的词和句子在中文情感分析中有着重要意义。语义不确定的词一般是一个语义十分丰富的词,在表达中隐含着某种倾向性的评价;而语义不确定的句子一般表现为褒贬情感词相当,极性倾向不明显。以不确定词“好”为例对不确定句子进行特征设计,然后通过4种监督学习的分类方法对比实验说明支持向量机在处理不确定词和不确定句子的情感分析上有较好的效果。
具有属性析取扩展特征的内逆P-信息智能挖掘
路英,李备友,史开泉
计算机科学. 2015, 42 (1): 215-219.  doi:10.11896/j.issn.1002-137X.2015.01.048
摘要 ( 96 )   PDF(365KB) ( 216 )   
参考文献 | 相关文章 | 多维度评价
逆P-集合(inverse packet sets)是由内逆P-集合F(internal inverse packet set F)与外逆P-集合(outer inverse packet set )构成的集合对;或者,()是逆P-集合;逆P-集合具有动态特性。它是研究另一类动态信息与应用的新模型。逆P-集合中元素的属性满足属性析取。利用内逆P-集合的结构,给出了元素的属性析取扩展形式与特征、属性析取扩展条件下的内逆P-信息智能挖掘,以及挖掘定理与智能挖掘原理;给出了满足内逆P-推理与非完整信息条件下的完整信息的智能挖掘-发现。利用这些结果,给出了具有属性析取扩展特征的信息智能挖掘的应用。
一种基于ILP和ASP的学习B语言描述的动作模型方法
刘振,张志政
计算机科学. 2015, 42 (1): 220-226.  doi:10.11896/j.issn.1002-137X.2015.01.049
摘要 ( 122 )   PDF(533KB) ( 297 )   
参考文献 | 相关文章 | 多维度评价
动作模型学习可以使Agent主动适应动态环境中的变化,从而提高Agent的自治性,同时也可为动态域建模提供一个初步模型,为后期的模型完善和修改提供了基础。通过结合归纳逻辑程序设计(Inductive Logic Programming,ILP)和回答集程序设计(Answer Set Programming,ASP),设计了一个学习B语言描述的动作模型算法,该算法可以在混合规模的动态域中进行学习,并采用经典规划实例验证了该学习算法的有效性。
面向用户查询意图的句子相似度分层计算
李景玉,张仰森,陈若愚
计算机科学. 2015, 42 (1): 227-231.  doi:10.11896/j.issn.1002-137X.2015.01.050
摘要 ( 115 )   PDF(399KB) ( 237 )   
参考文献 | 相关文章 | 多维度评价
为进一步提高句子相似度算法的准确性并提升其在复杂语境中的适用性,综合编辑距离、关键词及同义词语义方法,设计出面向用户查询意图的句子相似度分层算法。在充分分析实验数据用途的基础上,研究数据的特征分布,借助自然标注将句子相似度计算建模为多层次优化问题。经仿真实验证实该算法是有效的,F值可达到0.6019。
一种AP算法的改进:M-AP聚类算法
甘月松,陈秀宏,陈晓晖
计算机科学. 2015, 42 (1): 232-235.  doi:10.11896/j.issn.1002-137X.2015.01.051
摘要 ( 125 )   PDF(386KB) ( 564 )   
参考文献 | 相关文章 | 多维度评价
Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类。与传统聚类方法相比,对于大规模数据集,AP是一种快速、有效的聚类方法。但是AP算法在聚类结构复杂的(非团状)数据集上得到的效果并不是很好。因此,在AP的基础上加入一个merge过程,将AP算法改进为M-AP算法,可以有效地解决这种问题。而当样本数目比较大时,将CVM压缩算法融入其中,可以有效地解决大样本问题。
基于朴素贝叶斯的差分隐私合成数据集发布算法
陈旋,刘健,冯新淇,赵雪美
计算机科学. 2015, 42 (1): 236-238.  doi:10.11896/j.issn.1002-137X.2015.01.052
摘要 ( 182 )   PDF(230KB) ( 850 )   
参考文献 | 相关文章 | 多维度评价
差分隐私保护模型中,非交互式数据发布是一个研究的热点。提出了一个基于朴素贝叶斯的差分隐私合成数据集发布算法。该算法首先采用朴素贝叶斯的条件独立假设来计算原数据集的联合分布,然后采用指数机制生成发布的数据集。仿真实验表明,随着隐私预算的增加,使用合成数据集训练得到的分类器在测试数据集时分类正确率逐渐提高,并且趋于稳定。
基于Bagging-SVM集成分类器的网页作弊检测
唐寿洪,朱焱,杨凡
计算机科学. 2015, 42 (1): 239-243.  doi:10.11896/j.issn.1002-137X.2015.01.053
摘要 ( 107 )   PDF(656KB) ( 229 )   
参考文献 | 相关文章 | 多维度评价
网页作弊不仅造成信息检索质量下降,而且给互联网的安全也带来了极大的挑战。提出了一种基于Bagging-SVM集成分类器的网页作弊检测方法。在预处理阶段,首先采用K-means方法解决数据集的不平衡问题,然后采用CFS特征选择方法筛选出最优特征子集,最后对特征子集进行信息熵离散化处理。在分类器训练阶段,通过Bagging方法构建多个训练集并分别对每个训练集进行SVM学习来产生弱分类器。在检测阶段,通过多个弱分类器投票决定测试样本所属类别。在数据集WEBSPAM-UK2006上的实验结果表明,在使用特征数量较少的情况下,本检测方法可以获得非常好的检测效果。
信息产品质量测量动态衍变模型研究
刘婧,赵嵩正
计算机科学. 2015, 42 (1): 244-248.  doi:10.11896/j.issn.1002-137X.2015.01.054
摘要 ( 105 )   PDF(446KB) ( 227 )   
参考文献 | 相关文章 | 多维度评价
信息产品质量测量是信息产品质量全面管理Total Data Quality Management(TDQM)的重要组成部分,为日后信息质量提升奠定了基础。基于信息产品质量测量静态传递模型,在关系数据库基础上,“选择”关系代数作用下,引入了时间变量,分析了信息产品及时性对信息产品质量的影响,构建了信息产品质量测量动态衍变模型。该模型包括信息产品在t时刻的及时性矩阵、过时数据集质量衍变映射、基于过时数据集质量衍变映射模型的信息产品质量测量方法。利用应用实例验证了本模型的可行性和有效性。
面向模块重用的描述逻辑SHJF本地性规则研究
徐德智,廖晖寰,徐连君
计算机科学. 2015, 42 (1): 249-252.  doi:10.11896/j.issn.1002-137X.2015.01.055
摘要 ( 105 )   PDF(299KB) ( 242 )   
参考文献 | 相关文章 | 多维度评价
可重用本体模块的抽取是本体重用的一个关键环节。与传统工程应用中使用的基于本体层次的结构化方法抽取本体模块相比,使用逻辑的方法能充分利用本体提供的语义信息,抽取的本体模块更具完整性和正确性。在研究保守扩展的本体模块理论基础上,根据Grau B C提出的 SHOJQ 本地性规则,提出并证明了描述逻辑SHJF对应的语义本地性规则和句法本地性规则,为基于该规则抽取可重用本体模块提供了理论基础。
一种动态和自适应公交到站时间预测方法
谢玲,李培峰,朱巧明
计算机科学. 2015, 42 (1): 253-256.  doi:10.11896/j.issn.1002-137X.2015.01.056
摘要 ( 102 )   PDF(401KB) ( 276 )   
参考文献 | 相关文章 | 多维度评价
公交到站时间预测是实现智能化公交信息服务的基础,可靠地预测公交到站时间有利于提高公共交通的服务水平,以吸引更多的城市居民选择公共交通。以某城市公交系统海量的历史数据为基础,建立了基于SVM的集合了静态和动态数据的公交预测模型,该模型引入上游路段速度、下游路段最新速度、下游路段最新花时、时间段和路况拥挤程度等动态信息作为模型特征。在此基础上,根据大量公交到站时间历史数据的波动性,提出了一个基于波动性的自适应预测模型。实验结果表明,自适应预测模型优于现有模型,提高了预测的精确度和效率。
基于一维距离像的弹道中段目标特征提取
赵振冲,王晓丹,毕凯,邢雅琼
计算机科学. 2015, 42 (1): 257-260.  doi:10.11896/j.issn.1002-137X.2015.01.057
摘要 ( 135 )   PDF(274KB) ( 283 )   
参考文献 | 相关文章 | 多维度评价
针对目标的HRRP投影长度提取不精确的问题,首先研究了中段目标的进动特性及其一维距离像在不同雷达视线角下的变化规律,提出了一种基于差分算法的目标投影长度提取方法。该方法利用了目标一维距离像散射中心的峰值效应,使处理后的一维距离像只会 在散射中心处出现震荡效应,以此准确提取散射中心,克服了传统长度提取方法在散射中心周围重复搜索造成的误差。在此基础上,分析了目标投影长度随进动的变化规律,提出了一种进动角和目标真实长度提取方法。仿真实验表明以上方法具有很好的提取精度。
基于搜索引擎的词汇语义相似度计算方法
陈海燕
计算机科学. 2015, 42 (1): 261-267.  doi:10.11896/j.issn.1002-137X.2015.01.058
摘要 ( 149 )   PDF(541KB) ( 423 )   
参考文献 | 相关文章 | 多维度评价
词汇语义相似度的计算在网页浏览和查询推荐等网络相关工作中起着重要的作用。传统的基于分类的方法不能处理持续出现的新词。由于网络数据中隐藏着大量的噪音和冗余,鲁棒性和准确性仍然是一个挑战,因此提出了一种基于搜索引擎的词汇语义相似度计算方法。语义片段和检索结果的页数被用来去除词汇语义相似度计算过程中的噪音和冗余。此外,还提出了一种方法来整合查询结果页数、语义片段和显示的搜索结果的数量,该方法不需要任何先验知识与本体。实验结果显示,所提出的方法在Rubenstein-Goodenough测试集的相关系数为0.851,优于现有的基于网络的词汇语义相似度计算方法,同时在搜索引擎的查询扩展任务中具有较为良好的应用效果。
基于双极偏好占优的阵列天线优化方法
王丽萍,林思颖,邱飞岳
计算机科学. 2015, 42 (1): 268-271.  doi:10.11896/j.issn.1002-137X.2015.01.059
摘要 ( 94 )   PDF(373KB) ( 207 )   
参考文献 | 相关文章 | 多维度评价
传统进化算法在解决4个或4个以上目标的阵列天线综合问题时,出现了选择压力不足的难题。给出了一种基于双极偏好占优的阵列天线优化设计方法,该方法借助决策者根据解决实际问题的经验给出的目标值偏好,采用TOPSIS方法,比较Pareto解之间的相对贴近度值,建立了严格的非支配关系,引导种群向高的定向辐射方向图及低的零陷值靠近。为了可视化高维空间中的解集,用高维空间对角技术法对高维空间上的解进行可视化,并将该方法与现有的3种多目标优化方法进行解集质量优劣的比较与分析。仿真结果显示,该方法在解决4个以上目标的阵列天线综合问题时具有更好的收敛性以及更多的优秀解个数。
网络敏感信息自适应多重过滤模型研究
胡传志, 程显毅, 曹小峰
计算机科学. 2015, 42 (1): 272-275.  doi:10.11896/j.issn.1002-137X.2015.01.060
摘要 ( 108 )     
参考文献 | 相关文章 | 多维度评价
敏感信息过滤是既重要又复杂的任务。针对当前一些敏感信息过滤模型所存在的时间滞后、准确性低、自适应性差等问题,提出了一个敏感信息自适应多重过滤模型。该模型以互联网中文文本媒体为研究对象,采用意见挖据、机器学习、高性能计算和自然语言处理等技术,从整体和语义角度自适应识别敏感信息。对敏感信息自适应多重过滤模型的研究将为舆情监控、商业智能、辅助决策等应用系统开发提供技术支持。
不完备形式背景上的知识表示
智慧来
计算机科学. 2015, 42 (1): 276-278.  doi:10.11896/j.issn.1002-137X.2015.01.061
摘要 ( 113 )   PDF(229KB) ( 225 )   
参考文献 | 相关文章 | 多维度评价
不完备形式背景中包含有不确定性信息,其上的知识表示与完备形式背景上的知识表示既有区别又有联系。为了研究两者的内在联系,定义了偏小近似形式背景与偏大近似形式背景,以及偏小近似概念格与偏大近似概念格,提出了偏大近似概念格上粗糙概念的识别方法,研究了偏小近似概念格与偏大近似概念格之间的蕴含关系。结论表明,可以用偏大近似概念格来作为不完备形式背景的知识表示工具。
规则实例集上警示传播算法的收敛性
王晓峰,李强,丁红胜
计算机科学. 2015, 42 (1): 279-284.  doi:10.11896/j.issn.1002-137X.2015.01.062
摘要 ( 116 )   PDF(469KB) ( 337 )   
参考文献 | 相关文章 | 多维度评价
信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄。然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛。对于这种现象,至今缺少系统的理论解释。警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的。基于(3,4)-SAT问题的规则结构性质,分析 WP算法的收敛性。选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高。
基于限界传递相似度图的FCA概念相似度计算方法
黄宏涛,吴忠良,万庆生,黄少滨
计算机科学. 2015, 42 (1): 285-289.  doi:10.11896/j.issn.1002-137X.2015.01.063
摘要 ( 91 )   PDF(383KB) ( 254 )   
参考文献 | 相关文章 | 多维度评价
使用相似度图计算FCA概念相似度需要构造相似关系的传递闭包,对于复杂问题会导致相似度图规模过大,从而影响相似度评价的效率。为了降低相似度图规模,提出一种基于限界传递相似度图的FCA概念相似度计算方法。该方法首先通过限定传递相似关系的长度来避免构造相似关系的传递闭包,得到的限界传递相似度图中忽略了长度超过界限且对区分FCA概念无用的传递相似关系,能够有效压缩相似度图的规模;然后给出了动态传递相似度计算方法和由限界传递相似度图构建二部图的方法。实验结果表明,使用限界传递相似度图能够在不损失计算结果准确度的情况下有效提高FCA概念相似度计算的效率。
反一致可能性C均值聚类算法
文传军,汪庆淼,詹永照
计算机科学. 2015, 42 (1): 290-292.  doi:10.11896/j.issn.1002-137X.2015.01.064
摘要 ( 113 )   PDF(304KB) ( 298 )   
参考文献 | 相关文章 | 多维度评价
可能性C均值聚类(PCM)因存在聚类中心一致性问题而导致PCM算法聚类失效。提出了反一致可能性C均值聚类算法(ACPCM),它将各聚类中心间距离的倒数之和构造为反一致性项,将反一致性项和PCM目标函数之和构成ACPCM目标函数,利用粒子群算法估计聚类中心,利用梯度法建立模糊隶属度迭代公式。理论分析和仿真实验验证了所提算法的聚类有效性及反一致性。
图形图像与模式识别
基于稀疏表示的多示例图像分类
宋相法,焦李成
计算机科学. 2015, 42 (1): 293-296.  doi:10.11896/j.issn.1002-137X.2015.01.065
摘要 ( 108 )   PDF(567KB) ( 298 )   
参考文献 | 相关文章 | 多维度评价
为了有效地解决多示例图像分类问题,基于稀疏表示提出了一种新的多示例图像分类方法。该方法将图像看作多示例包,图像中的区域作为包中示例,利用示例嵌入策略计算包特征;然后将待分类图像包特征表示为训练图像包特征集上的稀疏线性组合,利用1优化方法求得稀疏解;最后根据稀疏系数提出一个为待分类图像预测标记的方法。在Corel数据集上的实验结果表明,与其他方法相比,所提方法具有更高的分类精度。
一种融合语义距离的最近邻图像标注方法
吴伟,高光来,聂建云
计算机科学. 2015, 42 (1): 297-302.  doi:10.11896/j.issn.1002-137X.2015.01.066
摘要 ( 136 )   PDF(498KB) ( 237 )   
参考文献 | 相关文章 | 多维度评价
传统的基于最近邻的图像标注方法效果不佳,主要原因在于提取图像视觉特征时,损失了很多有价值的信息。提出了一种改进的最近邻分类模型。首先利用距离测度学习方法,引入图像的语义类别信息进行训练,生成新的语义距离;然后利用该距离对每一类图像进行聚类,生成多个类内的聚类中心;最后通过计算图像到各个聚类中心的语义距离来构建最近邻分类模型。在构建最近邻分类模型的整个过程中,都使用训练得到的语义距离来计算,这可以有效减少相同图像类内的变动和不同图像类之间的相似所造成的语义鸿沟。在ImageCLEF2012图像标注数据库上进行了实验,将本方法与传统分类模型和最新的方法进行了比较,验证了本方法的有效性。
基于自适应窗口的裁剪中值滤波方法
黄燕,雷涛,樊养余,卢西盼
计算机科学. 2015, 42 (1): 303-307.  doi:10.11896/j.issn.1002-137X.2015.01.067
摘要 ( 114 )   PDF(932KB) ( 225 )   
参考文献 | 相关文章 | 多维度评价
基于决策的非对称裁剪中值滤波方法(MDBUTMF)能有效复原被高密度椒盐噪声污染的彩色图像,然而该方法采用固定大小的滤波窗口并利用均值替代中心像素,因此导致算法鲁棒性较低,对部分图像滤波失效。针对该问题,提出了一种基于自适应窗口的裁剪中值滤波方法,通过增加对单色区域的判断,有效解决了已有算法对单色区域滤波失效的问题,使得新方法具有较高的鲁棒性和实用性;并采用自适应窗口解决了MDBUTMF采用单一3×3窗口易导致滤波效果差的问题。实验数据表明,与经典的多种矢量以及标量的中值滤波方法相比,提出的裁剪中值滤波方法不仅具有较高的PSNR,而且具有较低的MAE和NCD,在抑制椒盐噪声的同时能有效保护图像的色调和细节。
基于图像差分特征的彩色图像差分预测与信息提取算法研究
杨单
计算机科学. 2015, 42 (1): 308-311.  doi:10.11896/j.issn.1002-137X.2015.01.068
摘要 ( 111 )   PDF(1180KB) ( 229 )   
参考文献 | 相关文章 | 多维度评价
图像特征提取预测技术一直是图像处理领域研究的热点与难点。提出了一种包含图像归一化特征融合的图像差分预测算法。基于色彩的图像差分特征测量方法充分利用了图像的色彩信息,将色彩信息全部转换到一个色彩空间中,然后将图像归一化到特定的视角距离范围内来提取出图像差分特征(IDF)信息。最后做了大量的仿真实验,结果表明,提出的方法可以极大地提高彩色图像差分预测性能;同时对图像的色域映射所造成的亮度失真进行的多尺度分析结果表明,以不同尺度提取的基于亮度的图像差分特征比一般的图像失真具有更高的尺度间相关性。
一种自适应的双门限场面运动目标检测方法
吴敏,吴宏刚,姚辉,王凯,蒋李
计算机科学. 2015, 42 (1): 312-316.  doi:10.11896/j.issn.1002-137X.2015.01.069
摘要 ( 84 )   PDF(661KB) ( 265 )   
参考文献 | 相关文章 | 多维度评价
为了有效解决在复杂环境下机场场面运动目标的精确检测问题,提出了一种自适应的双门限场面运动目标检测方法。首先采用混合高斯背景模型的方法来提取背景图像,然后使用两个门限值对差分图像进行前景目标分割,低门限阈值用于粗分割以检测出较明显的运动目标,在粗分割的基础上再用高门限阈值进行细分割以去除噪声目标和伪目标,最终得到场面运动目标的准确检测和分割结果。在复杂条件下的场景进行的实验,验证了该方法具有良好的噪声抑制能力和对慢目标良好的鲁棒性,同时能有效地分割出前景目标。