1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2015年第12期, 刊出日期:2018-11-14
  
目次
基于图排序算法的自动文摘研究综述
王俊丽,魏绍臣,管敏
计算机科学. 2015, 42 (12): 1-7, 39. 
摘要 ( 35 )   PDF(740KB) ( 286 )   
参考文献 | 相关文章 | 多维度评价
互联网技术的快速发展使得信息的采集和传播速度达到了空前的水平,海量的数据使得人们获取有价值的信息越发困难。自动文摘技术可以从海量的信息中提取出能代表原文重要内容且简洁精练的一段文字,高度压缩文档是解决信息超载问题的有效方法,因此自动文摘技术的研究引起人们越来越多的关注。目前诸如统计分析、机器学习技术以及语言学知识等在已有的自动文摘系统中都有所应用。对基于图排序算法的自动文摘的研究成果进行综述,首先阐述自动文摘以及图排序算法的基本知识,然后重点从图的构建、图排序、句子选择3个方面系统地介绍基于图排序算法的自动文摘的研究现状,最后在分析 已有自动文摘系统的基础上,探讨了基于图排序算法的自动文摘的未来发展方向。
基于机器学习的肺音分类技术的研究进展
郑明杰,宋余庆,刘毅
计算机科学. 2015, 42 (12): 8-12, 31. 
摘要 ( 42 )   PDF(518KB) ( 71 )   
参考文献 | 相关文章 | 多维度评价
肺音(Lung Sound) 信号是人体呼吸系统与外界在换气过程中产生的一种生理声信号,其因含有大量的生理和病理信息而具有很高的研究价值。近年来,频发的雾霾天气等环境问题所带来的呼吸道疾病发病率的提高,也使得对肺部疾病诊断的快速性与准确性的需求大幅提升。肺部听诊以其迅捷便利和无创等优良特性重新引发人们的广泛关注,而自动肺音诊断技术的发展无疑会对肺部疾病诊断带来重要的帮助。电子听诊器以及其他信号采集技术等硬件方面的发展进一步促进了现代肺音信号的分析和识别技术的研究与进步。主要介绍了肺音的概念、基于计算机的肺音信号处理和模式识别技术,并对近年来基于机器学习的肺音分类技术的发展状况进行了总结与列举;最后,对肺音分类技术的研究和应用发展趋势进行了展望。
GPU矩阵乘法的性能定量分析模型
尹孟嘉,许先斌,熊曾刚,张 涛
计算机科学. 2015, 42 (12): 13-17, 22. 
摘要 ( 40 )   PDF(508KB) ( 121 )   
参考文献 | 相关文章 | 多维度评价
性能评价和优化是设计高效率并行程序必不可少的重要工作,存储系统的性能高低直接影响到处理器的整体性能。利用GPGPU-Sim对GPU的存储层次结构进行了模拟,找出了SM数量与存储控制器数量之间最佳配置关系。矩阵乘法是科学计算领域中的基本组成部分,是一种具有计算和访存密集特点的典型应用,其性能是GPU高性能计算的一个重要指标。性能模型作为并行系统性能评价的新的技术解决方案,具有许多其它性能评价方法无法比拟的优势。建立了一个性能模型,模型通过对指令流水线、共享存储器访存、全局存储器访存进行定量分析,找到了程序运行瓶颈,提高了执行速度。实验证明,该模型具有实用性,并有效地实现了矩阵乘法的优化。
SIMD代码中的向量访存优化研究
徐金龙,赵荣彩,徐晓燕
计算机科学. 2015, 42 (12): 18-22. 
摘要 ( 28 )   PDF(415KB) ( 49 )   
参考文献 | 相关文章 | 多维度评价
向量程序来源于手工编写或由编译器自动生成。受限于编程人员和并行编译器的能力,得到的向量程序都存在一定的优化空间。优化编译器通常关注如何将串行程序向量化,但很少对向量程序进行优化。因此,提出了一种针对SIMD代码的向量访存优化方法。该方法首先分析程序是否需要优化,若存在需求,则对程序同时进行深度冗余优化和对齐优化。实验数据显示,提出的方法可以明显提高程序的运行效率,达到了目标。
第十三届全国软件与应用学术会议
一种基于邮件列表的软件问答信息抽取方法
罗宇翔,邹艳珍,金庸,谢冰
计算机科学. 2015, 42 (12): 23-25, 35. 
摘要 ( 31 )   PDF(597KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
开源项目通常会提供邮件列表来帮助用户更好地理解和使用开源项目。但由于邮件的数量巨大、邮件内容组织繁杂、问题不明确、答案定位困难等问题,用户在邮件查询过程中定位一个特定的软件问答信息要花费大量的时间和精力。为此,提出一种基于邮件列表的软件问答信息抽取方法。该方法通过对邮件的简单分类与标注,实现自动的问题句抽取和答案邮件选取,从而提升了用户进行邮件列表查询以及开源软件项目学习的效率。最后,通过实验验证了该方法的有效性。
功耗感知的自适应粒子群优化虚拟机动态映射
苏宇,高 阳,秦志光
计算机科学. 2015, 42 (12): 26-31. 
摘要 ( 20 )   PDF(513KB) ( 45 )   
参考文献 | 相关文章 | 多维度评价
功耗管理是云计算数据中心的重要问题之一。由于服务器在不同睡眠状态时的功耗及唤醒延迟不同,将空闲服务器节电状态与输入作业负载建立映射,设计并实现了一种新的元启发式调度器,利用适应粒子群优化(SAPSO)检测和跟踪云计算资源池中不断变化的最优目标服务器,考虑了资源动态、工作服务器不同负载时的功耗、空闲服务器不同休眠状态转换时的功耗,使得VM映射中功耗增量最小。仿真实验表明了所提方法的有效性和较好的性能,经比较分析可知,该方法在保证满足SLA的情况下最大限度地减少了功耗且提高了VM映射效率。
一种面向浏览式购物行为模式的LBS购书移动应用
何远舵,陈之昀,王亚沙
计算机科学. 2015, 42 (12): 32-35. 
摘要 ( 26 )   PDF(830KB) ( 56 )   
参考文献 | 相关文章 | 多维度评价
为了提升用户体验,目前涌现了一批辅助购物的移动应用。这些应用为用户补充商品的信息,适用于目标明确的购物行为模式。然而,在现实生活中,还普遍存在没有明确购物目标、将购物作为休闲方式的浏览式购物行为模式。现有应用对此模式支持不足。为此,以书店为应用场景,开发了一种基于室内定位技术的浏览式购物辅助移动应用。此应用后端从书店信息系统和互联网中收集包括书籍摆放位置的各类信息,然后利用关键词提取技术,建立基于位置的关键词库;前端则利用室内定位技术,根据购物者位置向其展示附近书籍概览信息,辅助购物者对附近商品快速认知。案例评估表明,此应用可以提升浏览式购物顾客的购物体验。
基于3D动画的软件演化信息可视化
于涵,王海,彭鑫,赵文耘
计算机科学. 2015, 42 (12): 36-39. 
摘要 ( 42 )   PDF(837KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
可视化是软件维护和演化研究的一个重要组成部分。一个交互式的3D可视化方案能够将软件演化过程更形象地展示给用户。将软件的演化历史比拟成一座城市的发展过程,用户可以自由地在城市中移动,在把握系统宏观变化趋势的同时,很好地掌控其细节的发展情况。在已有相关工作的基础上,利用unity3D实现了一个原型工具,基本实现了预期目标,能为软件管理者提供方便的可视化信息。
一种面向Chrome浏览器的课堂云笔记插件
乔子健,陈德健,孙艳春
计算机科学. 2015, 42 (12): 40-42, 46. 
摘要 ( 42 )   PDF(842KB) ( 52 )   
参考文献 | 相关文章 | 多维度评价
在当今的教学中,课堂教学和互联网教学是两大主流。然而,无论是在课堂教学还是在互联网教学中,当前的学习辅助平台都存在着一个明显的不足:学生无法及时针对讲义细节在云端共享笔记或寻求帮助,没有形成便于学习和交流的知识分享机制。这不利于学生对讲义知识的深刻理解,也不利于形成优质的学习生态系统。针对这一不足,在分析现有教学平台和云笔记产品的基础上,设计了一个面向Chrome浏览器的云笔记插件的系统架构,并采用HTML5、Node.js等关键技术进行实现。该插件能够针对互联网讲义资源中的任意细节记录笔记、提出问题并云端共享,有助于学生在课上、课下对讲义资源中的细节的理解、讨论与最终掌握,加强现有学习辅助平台的功能。最后进行了相应的实例研究,证明了所提出的方案是可行有效的。
开源软件开发者的演化研究
李其锋,李 兵
计算机科学. 2015, 42 (12): 43-46. 
摘要 ( 41 )   PDF(573KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
开源软件的开发主要依靠开发人员的自我管理和志愿贡献。在软件开发过程中,开发人员的组成、分工、能力等会发生经常性的改变,这些改变都会通过交互行为的变化反映出来。已有研究成果表明开源软件存在核心团队,他们主导项目的开发与实施,但对开发团队随时间而发生的结构变化的研究较少。通过观测软件项目生命周期中开发者总体的变化情况,研究了开发者网络与软件的协同演化机理,以GNU/Linux公共数据集为例,讨论了开源软件开发者数量、自愿度、开发者经验与项目的协同演化现象,并给出了演化的合理解释。
基于数据流分析的单链表可达性自动化验证
冬雨辰,王寒非,赵建华
计算机科学. 2015, 42 (12): 47-51. 
摘要 ( 19 )   PDF(432KB) ( 54 )   
参考文献 | 相关文章 | 多维度评价
程序验证中的常见情景是判断某个用户指定的性质在程序执行之后或执行过程中的某个程序点上是否成立。人工的形式化验证过程繁琐且容易出错,因此形式化验证的自动化是提高代码验证效率的重要方法。数据流分析技术是一种能够自动发现程序中某类性质的技术。研究了将一种数据流分析技术(单链表形状分析)和基于Scope Logic的代码验证过程相结合的方法。通过数据流分析获得所有程序点上的单链表可达性性质,将结果表达为带有递归函数的一阶逻辑公式,并将其插入到相应程序点中。分析程序还根据Scope Logic的证明法则设定了这些公式之间的逻辑依赖关系。实例测试表明所提方法可以分析得到单链表可达性性质,并且分析结果能够被基于Scope Logic的代码形式化验证过程有效利用,提高了代码形式化证明的效率。
面向普适计算环境的Android平台服务编排框架
顾敬潇,彭鑫,赵文耘
计算机科学. 2015, 42 (12): 52-55, 64. 
摘要 ( 39 )   PDF(439KB) ( 50 )   
参考文献 | 相关文章 | 多维度评价
普适计算环境下的智能移动设备是面向终端用户的服务资源聚集和编排的主要载体。普适计算环境中的服务资源具有多种不同的形态,包括基于互联网提供的Web服务、终端设备自身服务和资源(例如本地应用、自带传感器)以及所处环境中可访问的服务(例如环境传感器)。此外,不断变化的上下文环境对软件本身的自适应能力提出了新的要求,而移动设备上的服务编排受设备计算能力和资源的限制。为了解决上述问题,提出了一个面向普适计算环境的Android平台服务编排框架ASOF。通过ASOF,移动终端可在运行时获取所需业务流程的服务模板,并对该模板中的抽象服务进行服务绑定,实现轻量级的混合服务编排,使终端能够动态获得调用普适计算环境中各种类型的服务的能力。随后,基于OSGi Felix框架给出了一套ASOF的标准实现,并以一个具体案例验证其有效性。
一种简历语义搜索系统的实现方法
柯叶青,马志柔,伍海江,刘 杰
计算机科学. 2015, 42 (12): 56-59. 
摘要 ( 38 )   PDF(341KB) ( 61 )   
参考文献 | 相关文章 | 多维度评价
政府与企事业单位的人事部门通常面临着如何从大量简历中筛选出合适人选的问题。一些业务部门对人才的需求通常只能表达为标签,比如“具有丰富搜索引擎开发经验”、“985高校毕业”等,这些需求不能通过SQL查询或关键词搜索来实现。为了解决这个问题,提出一种基于语义网的简历搜索方法。通过领域知识库辅助信息提取的方法,对简历信息进行语义分析和标签的自动生成。此外,在大规模人员情况下,提出了多层次缓存的方法, 极大提高 了性能。将该方法应用于某 机构 一万人员简历的筛选,实验结果表明了其有效性。
一种面向PaaS的实例级应用动态更新技术
张婕,曹春,余东亮
计算机科学. 2015, 42 (12): 60-64. 
摘要 ( 21 )   PDF(401KB) ( 50 )   
参考文献 | 相关文章 | 多维度评价
云计算是当前信息技术的重要技术领域,而平台即服务(PaaS)已成为业界研究的热点之一。PaaS平台为用户提供高可用、高可扩展的应用开发、部署和运行环境。然而当部署到云端的应用需要不断更新以修复错误、增加功能时,当前主流PaaS平台却因缺乏对应用在线更新的有效支持而削弱了其自身的高可用特性。为解决该问题,提出一个面向PaaS平台的动态更新技术框架。基于现有软件动态更新技术的研究,通过对PaaS平台中应用的事务管理、动态依赖管理、版本管理等机制的扩展,为PaaS平台提供运行时实例级的应用动态更新支撑,并在Cloud Foundry上进行实现和实验,结果证明了该动态更新技术的有效性。
基于RUCM的软件安全性需求描述方法
吴雪,刘超,吴际
计算机科学. 2015, 42 (12): 65-70. 
摘要 ( 31 )   PDF(761KB) ( 80 )   
参考文献 | 相关文章 | 多维度评价
随着软件在安全关键系统中的应用越来越广泛、承担的安全关键功能越来越多,软件的安全性需求变得越来越重要,成为系统安全性的一个重要的决定性因素。软件安全性需求的正确描述是整个软件安全性工作的关键,它是开展后续软件安全性设计、实现与测试工作的依据。然而现有的安全性需求通常被混同于一般功能性描述中,缺乏独立、规范和明确的描述,缺乏对于故障、失效与安全性需求之间相互关系的描述机制,导致在实际应用中缺乏对安全性需求进行准确描述的方法。设计了一种基于结构化模版和约束规则的安全性需求规约,即基于RUCM的安全性需求描述方法Safety RUCM,该方法以RUCM建模方法为基础,通过扩展用例规约模板和限制规则,添加故障描述模版以及数据描述模版,使其能够支持故障相关描述以及相应的安全性需求描述并形成安全性需求规约,最后通过某机载操作系统的案例研究验证了Safety RUCM建模方法的可行性。
一种结合线性时序逻辑和故障树的软件安全验证方法
王飞,沈国华,黄志球,马 琳,刘 畅,李海峰,廖莉莉
计算机科学. 2015, 42 (12): 71-75. 
摘要 ( 39 )   PDF(407KB) ( 85 )   
参考文献 | 相关文章 | 多维度评价
嵌入式软件在安全关键领域的广泛应用使得保障软件的安全性成为学界的研究热点。故障树技术是工业界常用的传统的安全分析方法之一。然而,传统的故障树无法精确描述安全关键系统中具有时序特征的系统故障。针对此问题,给出了一种结合线性时序逻辑和故障树的安全验证方法。该方法运用线性时序逻辑对故障树进行形式化规约,从中抽取出软件安全属性并用时序逻辑公式进行描述,用以支持对安全关键软件的模型检验。最后,以某机载控制系统软件数据处理故障模块的模型检验为例,来说明该方法的有效性和可行性。
结合运动方程与卡尔曼滤波的动态目标追踪预测算法
王妍,邓庆绪,刘赓浩,银 彪
计算机科学. 2015, 42 (12): 76-81. 
摘要 ( 30 )   PDF(460KB) ( 116 )   
参考文献 | 相关文章 | 多维度评价
针对传统定位技术误差较大且无法预测目标位置等问题,提出了一种结合运动方程与卡尔曼滤波的动态目标追踪预测算法ME-KF。通过运动方程模拟动态目标运动特性,利用卡尔曼滤波来减小干扰噪声对测量结果的影响,并预测下一时刻的目标位置。该算法在辽宁排山楼矿井的人员定位系统中得到了实际应用,并取得了显著成果。实验结果表明,该方法提高了定位精度,能够对人员位置进行预测以及对危险区域进行预警,并且成功地分析判断了障碍物的分布状况。
基于MARTE模型的系统可靠性预测
柴叶生,朱雪阳,晏荣杰,张广泉
计算机科学. 2015, 42 (12): 82-86, 91. 
摘要 ( 58 )   PDF(444KB) ( 52 )   
参考文献 | 相关文章 | 多维度评价
系统的可靠性是系统的重要非功能属性之一。传统的可靠性分析在系统开发结束后进行,可能会发现由于系统开发早期的架构设计不合理而导致的问题,这时再修改系统架构并重做后继开发步骤,将会浪费大量人力和物力。如果能在开发的早期阶段,在系统模型层面进行分析并预测,则可以尽早地发现系统可靠性方面的问题并将其修复。UML是一种通用的、标准化的建模语言,MARTE是UML在嵌入式实时系统领域的扩展。提出了基于MARTE模型的系统可靠性预测方法,该方法考虑的MARTE模型包括用例图、活动图、部署图。先将MARTE模型转换为马尔可夫决策过程网络模型,再利用概率模型检测工具PRISM进行分析,得到系统可靠性的预测结果。实例研究表明,所提方法不仅能够预测系统可靠性的最大值和最小值,还能通过调整各个资源的可靠性值,考察其对系统可靠性的影响,为设计人员的进一步工作提供参考。
本体概念图的展示过程及技术实现
王诗碕,李伊潇,沈立炜,赵文耘
计算机科学. 2015, 42 (12): 87-91. 
摘要 ( 24 )   PDF(659KB) ( 43 )   
参考文献 | 相关文章 | 多维度评价
本体建模是语义网研究与建设中的重要工作。在面对一个大规模的领域时,采用众包以及图形化的编辑方式能够吸引更多人参与本体建模的工作。在为此设计的协同建模平台中,本体概念图的展示应满足相应的特征,包括内容正确性、局部化展示以及轻量级的数据传输。针对概念图展示的实际需求,研究并归纳了基于本体文件的概念图展示过程,该过程旨在将后台保存的本体内容传递到前端的概念图编辑器中,包括本体读取、局部本体抽取、本体数据转换、图形模型转换和图形展示一系列步骤。另外,在采用本体查询、模型转换语言等一系列工具的基础上,给出了概念图展示的实现方案,并将实现该展示过程的模块集成在本体协同建模平台中。
基于RFID的校园导航系统的设计与实现
崔金琦,陶先平
计算机科学. 2015, 42 (12): 92-94, 119. 
摘要 ( 39 )   PDF(583KB) ( 41 )   
参考文献 | 相关文章 | 多维度评价
随着GIS、LBS技术和移动互联网技术等核心技术的发展,服务于普通大众的个人导航系统成为应用热点。室内行走引导是个人导航系统的核心之一,其中涉及的室内定位技术一直是研究的难点之一。基于固定式RFID标签群,生成室内位置地图,将随身移动式RFID读写器和个人智能手机相结合,完成室内定位、路径计算和导航提醒。基于上述设计方案,完成了一个基于RFID的南京大学校园导航系统,并将其投入了实际使用。
基于IMA平台的嵌入式软件设计模型仿真及实时性分析方法
孙磊,杨海燕,吴际
计算机科学. 2015, 42 (12): 95-97, 135. 
摘要 ( 21 )   PDF(295KB) ( 35 )   
参考文献 | 相关文章 | 多维度评价
如何确保机载软件满足其实时性需求一直是一个引人关注的研究问题。根据工业界的报告结果,缺陷发现得越早,用于修复缺陷以提高机载软件不超时的可能性的代价就越小。对于运行在由ARINC653标准所描述的综合模块化航电系统(IMA)上的机载软件可采用以下方法:将机载软件的设计模型(UML模型)转化成仿真模型(Simulink模型),通过在Simulink平台上运行仿真模型来发现潜在的实时性问题。由于机载软件可能与IMA平台之间具有大量的交互(例如接口层和操作系统层)用来申请使用资源或者与其它的应用程序进行通讯,因此设计了一个仿真内核来仿真IMA平台的行为。最后,使用一个工业案例来论证上述方法的有效性。
小车远程控制及自主寻路系统的设计与实现
李晓帆,许畅
计算机科学. 2015, 42 (12): 98-101. 
摘要 ( 39 )   PDF(1085KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
智能机器人可通过传感器获取周围的地形、温度等信息,并加以分析处理而采取对应策略。然而,机器人可能由于本身不具备定位功能而只能进行简单控制,也可能因为障碍物信息采样不足而导致避障算法失败。面对这一类问题,设计并实现了一套能对智能车进行远程控制并令其自主寻路的系统。该系统通过高效的图像处理与识别对智能车自动定位;对现有避障算法进行了改进,并建立了避让策略来保证智能车总能找到一条抵达目标的安全路径。实验结果表明,该系统定位精度较高,控制与寻路功能具有一定的可靠性与实用性。
面向自动修复并融合失效场景的缺陷定位方法
李昂,毛晓光,雷晏
计算机科学. 2015, 42 (12): 102-104, 107. 
摘要 ( 24 )   PDF(590KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
为了应对日益增长的软件修复开销,研究高效的软件自动修复技术成为学术界和工业界的共识。缺陷定位作为自动修复技术的前端,是实现快速准确自动修复的关键,其精度直接影响自动修复的性能。然而,初步研究表明,现有缺陷定位技术缺乏对自修复需求的考虑,对自修复算法支持有限。有必要研究面向自修复的高精度自动化缺陷定位技术,以提升自修复性能。因此,提出了失效场景的缺陷定位方法来应对该问题。提出的方法首先采用程序切片技术,构造出与失效相关的场景;然后对失效场景的各个元素实施可疑值度量;最后将可疑值度量化的场景交给自动修复技术实施修复。初步实验结果表明,本缺陷定位方法能有效提升自动修复性能。
函数抽取重构的自动检测方法
刘阳,刘秋荣,刘辉
计算机科学. 2015, 42 (12): 105-107. 
摘要 ( 33 )   PDF(235KB) ( 46 )   
参考文献 | 相关文章 | 多维度评价
软件重构历史的自动检测是目前软件重构领域的一个研究热点。其主要目的是方便程序员或软件维护人员理解 软件演化的历史,也便于根据服务代码重构历史对其客户代码进行相应的重构操作。虽然相关研究人员已经提出了多种自动化的重构历史检测方法,但目前未见关于函数提取重构历史检测的方法或工具。为此,提出了一种基于版本比较的函数抽取重构自动检测方法,实现并验证了该方法的有效性。在8个开源项目上进行了实验验证,结果表明其查准率为65%~90%。此外,在一个小型项目上通过监控程序员的重构操作获得了全部的函数提取重构操作,进而计算出检测算法的查全率和查准率均为85%。
一种基于层次聚类的子系统划分方法研究
朱锐,廖鸿志,李 彤,代 飞,王一荃,莫 启,林雷蕾
计算机科学. 2015, 42 (12): 108-114. 
摘要 ( 24 )   PDF(1072KB) ( 30 )   
参考文献 | 相关文章 | 多维度评价
信息领域中常常会涉及到子系统的划分问题,而U/C矩阵法是信息系统划分的一种常用方法,但是系统的复杂性以及人为的参与常常导致子系统划分产生低效率、不确定性以及错误划分等问题。因此深入剖析了系统与子系统、子系统与功能、功能与数据等之间的关系与性质,通过对U/C矩阵按照功能相似度进行层次聚类,并引入结构熵和Hpal熵来对聚类形成的子系统进行度量,给出了具体的计算公式,提出了一种新的划分子系统的方法,将原本需要人为参与的事情转变为通过计算来完成。同时,实现了一个原型系统来对所提出的方法进行验证,并给出了具体实例。
Xen虚拟机Credit调度算法的实时性能分析
张天宇,关楠,邓庆绪
计算机科学. 2015, 42 (12): 115-119. 
摘要 ( 25 )   PDF(415KB) ( 96 )   
参考文献 | 相关文章 | 多维度评价
为了降低开销以及增加灵活性,通过虚拟化技术将多个系统运行在一个通用计算平台上已成为复杂实时嵌入式系统的趋势。Xen是近年来应用最广泛的虚拟化技术,对其默认使用的Credit调度算法进行实时性能分析,使得能够直接对运行在Xen上的实时系统进行可调度性测试,并且可以通过形式化的资源界限函数对Credit的实时性进行直观的评估。首先分析了Credit调度算法的基本实现,提出并且证明了一种配置VCPU参数的方法使得Credit的实时性得到提升,在此基础上,通过证明得到了Credit算法的基本性质,并得出其在最坏情况下为VCPU分配的资源函数曲线。
Web服务计算组合流程QoS验证
开金宇,缪淮扣,高洪皓
计算机科学. 2015, 42 (12): 120-123, 147. 
摘要 ( 29 )   PDF(687KB) ( 32 )   
参考文献 | 相关文章 | 多维度评价
在满足功能需求的前提下,Web服务能否赢得市场, 主要取决于其服务质量(Quality of Services,QoS)。采用概率模型检验的方法判断Web服务计算组合流程的服务质量是否满足系统质量需求。依据用户访问Web服务产生的访问日志,采用聚类的方法,构建面向用户群组的Web服务流程的使用行为QoS模型。采用QoS扩展的状态图描述Web服务流程的QoS需求。然后,利用概率模型验证工具PRISM判断Web服务流程的QoS是否满足系统质量需求。验证面向用户群组的Web服务流程的使用行为质量模型是否满足系统质量需求,为服务流程结构的调整提供了依据。
基于多目标协同进化的测试用例优先排序
石宇楠,李征,龚沛
计算机科学. 2015, 42 (12): 124-129. 
摘要 ( 28 )   PDF(777KB) ( 64 )   
参考文献 | 相关文章 | 多维度评价
测试用例优先排序是一种有效的降低回归测试开销的技术,通过对测试用例按照其重要程度排序后可获得更高的测试效率。针对传统多目标遗传算法在测试用例优化排序中存在的收敛较慢、易陷入局部最优、缺乏对不同测试准则的综合权衡等缺点,提出一种基于竞争模式的多目标协同进化算法。该方法采用平均代码覆盖率以及平均变异杀死率作为多个约束目标的测试准则来进行适应度度量,提高算法的错误检测率;使用个体绝对适应度与相对适应度对个体生存能力进行评价,衡量个体优秀程度,利用竞争性的协同进化思想加快算法收敛速度;通过剔除“老年”个体控制个体生存周期来避免陷入局部最优问题。同时,在影响算法执行效率的因素方面也进行了一系列的实验,结果表明该算法能够加快收敛速度,加强了局部搜索能力,相对于传统的优化算法来说具有更好的搜索效率和更高的错误检测率,从而验证了算法的有效性和可行性,证明了该算法具有一定的现实意义。
基于动态镜像的实时数据仓库存取预处理技术研究
毛莺池,闵 伟,接 青,朱沥沥
计算机科学. 2015, 42 (12): 130-135. 
摘要 ( 30 )   PDF(520KB) ( 60 )   
参考文献 | 相关文章 | 多维度评价
实时数据仓库是数据仓库技术的重要分支,而实时数据查询和实时数据导入引发的查询竞争问题一直是实时数据仓库技术研究的重点之一。查询竞争问题严重影响了查询分析的精度和效率,还降低了数据仓库的性能。提出了一种在数据仓库外部构建动态存储区域的方法,它采用动态镜像技术,有效地缓解查询竞争问题。同时,为了提高实时OLAP上的查询分析操作的性能,提出了蝇量级物化方法及蝇量级物化下的表连接算法FWMJoin(Fly-Weight Materialization Join)。基于TPC-H基准的实时数据仓库测试系统,针对动态镜像技术下的动态存储区域的OLAP性能进行分析与评估,并对实验结果进行总结。
问题框架中问题领域因果行为的形式化验证
朱利鲁,李智
计算机科学. 2015, 42 (12): 136-142, 156. 
摘要 ( 29 )   PDF(1720KB) ( 29 )   
参考文献 | 相关文章 | 多维度评价
为问题框架中问题渐变所依赖的问题领域因果行为的确立提出一种形式化验证方法。为了对问题渐变过程中事件间的因果关系提供可验证的证据支持,简化问题表征的复杂度,进而提高计算机领域软件规约的可靠性,采纳了一种基于NuSMV语言的符号模型检验的形式化验证方法。该验证方法采用UML状态机表示问题领域内部状态变化的有限结构空间,用CTL公式描述问题域内状态之间的可达性性质,通过遍历有限结构状态机来检验CTL公式的正确性,筛选出具有因果关系的外部共享事件,为问题渐变提供有效的技术支持。
国内第三方Android应用市场安全性的检测
闫晋佩,何晖,安文欢,张小辉,任建宝,齐勇
计算机科学. 2015, 42 (12): 143-147. 
摘要 ( 29 )   PDF(443KB) ( 60 )   
参考文献 | 相关文章 | 多维度评价
根据目前第三方Android应用市场应用存在的重新打包行为,随机选取国内官方的150个应用以及作为对比的第三方应用市场的572个同款应用,设计了Android重新打包应用安全检测系统。该系统先进行相似性计算,细粒度识别出重新打包应用,再通过逆向工程获得其资源文件,根据系统API与权限之间的映射匹配分析其越权行为,并根据构建的方法控制流图分析其权限滥用行为。系统通过并行化处理检测出第三方应用市场存在33.17%的重新打包应用,其中19.58%修改了权限。在修改过权限的应用中,45.95%存在越权行为,27.03%存在滥用权限行为。
数据感知过程之间差异的检测和解决
张学伟,邢建春,杨启亮,宋 巍,王洪达
计算机科学. 2015, 42 (12): 148-151, 166. 
摘要 ( 26 )   PDF(693KB) ( 37 )   
参考文献 | 相关文章 | 多维度评价
业务驱动开发支持多名业务人员对一项流程进行设计。为获得一个标准的参考数据感知过程,需要将这些变种合并,而检测和解决变种之间的差异是不可或缺的一环。现有方法大多依赖于修改日志从控制流层面检测和解决过程模型之间的差异,而很少研究数据感知过程之间差异的问题。基于程序依赖图和对应关系,提出一种通过比较修改前后的数据感知过程来检测和解决差异的方法。该方法建立一个层次性修改日志,以满足用户友好性的要求。
面向复杂物联网应用的上下文质量感知技术研究
郑笛,贲可荣,王 俊
计算机科学. 2015, 42 (12): 152-156. 
摘要 ( 20 )   PDF(424KB) ( 49 )   
参考文献 | 相关文章 | 多维度评价
随着物联网应用的快速发展,传感信息日益多元化,传感器网络规模广域化,底层传感器网络构成异构化,传感信息数量大数据化,相应地,这也使得底层传感信息中所蕴含的不一致性、不完整性、不准确性等影响信息质量的因素大大增加。而传统的上下文感知技术没有充分考虑上下文质量对感知过程的影响,因此,在现有的上下文感知系统框架的基础上,充分研究不一致性、不完整性、不准确性等低质量传感器上下文的消除问题,通过上下文质量因子分类配置、不准确与不一致上下文丢弃、不完整上下文填充等方法实现了不同层次的控制机制,降低了信息的不确定性,从而有效提高了物联网应用的上下文处理质量。
面向决策的信任融合模型研究
徐培,廉 彬,邵 堃,陈 俊,安 宁
计算机科学. 2015, 42 (12): 157-161. 
摘要 ( 30 )   PDF(389KB) ( 78 )   
参考文献 | 相关文章 | 多维度评价
信任关系模型无论是在现实生活中还是在开放网络中都是最复杂的社会关系模型之一,是一个很难度量的抽象的心理认知,因为它涉及假设、期望、行为和环境等多种因素。借鉴以往的研究经验,综合考虑多种信任关系要素,提出了一种新的面向决策的信任融合模型。该模型基于直接信任度、间接信任度和信誉值的演化,依据信任融合获得决策信任度,为主体评判下一次的交互提供依据。为了证明信任融合模型的有效性,假设客体在ω类活动中以期望为PωX的概率从事该项活动。实验证明,信任融合模型得到的决策信任度和客体可信度的差异明显小于直接信任度、间接信任度或信誉值。
面向组合式软件功能正确性和非功能满足性的统一建模方法
肖芳雄,许 波,夏国恩,李国祥,闵华清
计算机科学. 2015, 42 (12): 162-166. 
摘要 ( 21 )   PDF(434KB) ( 33 )   
参考文献 | 相关文章 | 多维度评价
在Internet动态、开放、异构、多变的环境下,组合式软件不仅要满足功能正确,非功能(时间、代价、概率等)属性的满足也日益成为一个重要的问题。在组合式软件的设计阶段,建立组合式软件功能和非功能的统一模型并验证其功能正确性和非功能满足性,是确保组合式软件可信性的重要手段。在UML序列图的基础上进行时间、代价、概率属性的扩展,提出了一种可对组合式软件的交互行为及其时间、代价、概率属性统一建模的属性序列图,该属性序列图以两层模式进行建模,其中基本属性序列图可对涉及时间、代价属性的具体交互场景建模,高层属性序列图通过概率合成基本属性序列图可形成全局场景。给出了针对BPEL4WS的建模实例以说明所提建模方法的有效性。
一种基于源代码分析的程序变化影响路径集的生成方法
郭丹丹,姜瑛
计算机科学. 2015, 42 (12): 167-170. 
摘要 ( 29 )   PDF(307KB) ( 52 )   
参考文献 | 相关文章 | 多维度评价
在软件生命周期的任意阶段,均可能因为各种原因而导致软件发生变化。当软件发生变化时,必须对其进行回归测试,检查这些变化是否影响了软件原有的正常功能。为了提高回归测试的效率并降低成本,需要尽可能准确地确定软件变化影响的内容。在单元测试中,基于源代码语句分析了程序的变化影响范围,得到了程序的变化集和影响集,提出了生成影响路径集的算法。实验结果表明,该方法能有效产生程序变化影响的路径集,提高了回归测试的效率。
社会网络分析软件研究
刘鹏,李先贤,王利娥
计算机科学. 2015, 42 (12): 171-174. 
摘要 ( 33 )   PDF(836KB) ( 40 )   
参考文献 | 相关文章 | 多维度评价
随着社会网络数据规模的增长,人工处理方式已经不能满足社会网络分析的需求。介绍了4款常用的社会网络分析软件nodeXL、Pajeck、 Gephi和networkX。从支持数据格式、可视化性能、统计分析功能、帮助文档、使用难度等多个方面对以上软件的特性进行对比分析,给出了客观的综合评价,并对选择和使用这些软件提出了相应的建议。
基于抽象解释的服务间消息的数据约减
蒋曹清,肖芳雄,高 荣,应 时,文 静
计算机科学. 2015, 42 (12): 175-180. 
摘要 ( 24 )   PDF(509KB) ( 46 )   
参考文献 | 相关文章 | 多维度评价
面向服务软件中服务间消息的变量值可能存在无穷域的情况,从而导致模型检测时产生状态空间爆炸问题。为了使终止性验证在实践上可行,需要约减模型状态空间的大小,使得计算时间和空间需求合理。为此,基于抽象解释的区间抽象理论扩展了经典区间抽象域方法,并在统一的区间抽象域方法上借助异常控制流图对变量进行区间分析,在此基础上逆向分析得到服务间消息的变量区间集。变量区间上任意值相对于终止性验证是等价性,因此从每一个变量区间集中选取一个代表值,可组成服务间消息变量的约减值,从而为异常处理的终止性验证提供了约减的初始配置,有效避免了状态空间爆炸。
基于人机交互的计算机辅助软件需求分析工具的研发
何正海,李智
计算机科学. 2015, 42 (12): 181-183, 194. 
摘要 ( 27 )   PDF(833KB) ( 29 )   
参考文献 | 相关文章 | 多维度评价
软件需求工程在软件开发项目中起着至关重要的作用,而需求分析活动的主角是人,因此计算机辅助需求分析工具的设计要做到以用户为中心,即以人为本。本原型作品在已有的面向问题的计算机辅助软件需求工程(Computer-Aided Requirements Engineering,CARE)工具的基础上,进一步在支持的平台及易用性等方面进行了扩展。选择安卓平台来开发此工具,理由是移动端应用软件相较于PC端具有一些优势(功能多样性、便捷性等)以及安卓的开源性质,它能够为提高软件质量以及用户体验带来新的技术支持。此外,还具体展示并介绍了该工具是如何基于人机交互的理论模型及设计原则设计的。
基于区域扩散机制的无线传感器网络时间同步算法
汪涛
计算机科学. 2015, 42 (12): 184-188. 
摘要 ( 29 )   PDF(686KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
针对当前无线传感器网络时间同步算法无法满足物联网对于网络实时性的要求,提出了一种基于区域扩散的无线传感器网络时间同步算法。该算法分为两个阶段进行:第一阶段根据生物觅食理论(OFT),按照收益率最高的原理提出一种代言人信息选择算法(SIE)进行区域内时间同步;第二阶段根据时间偏移量最小节点选择区域代言人并在区域之间进行二次同步,同时将同步过程映射到马尔可夫链,提出基于马尔可夫链的代言人加速算法(MarSAA)。理论分析和实验证明,提出的算法具有较好的时间复杂性;并且两阶段算法可以并行进行,相对于传统算法在全网时间同步上具有非常好的性能。
网络与通信
一种用于大规模无线传感器网络的时钟同步算法
郝纲,庄毅
计算机科学. 2015, 42 (12): 189-194. 
摘要 ( 25 )   PDF(502KB) ( 42 )   
参考文献 | 相关文章 | 多维度评价
针对经典的时钟同步算法在大规模无线传感器网络中存在的同步精度低与能量消耗高等问题,提出一种基于簇-树结构的无线传感器网络时钟同步算法。首先,建立一棵以网关为根节点、簇首为子节点的生成树来减少网络中节点同步时的累计跳数;然后,在该生成树的基础上采用簇间双向的SRS和簇内单向的ROS同步机制进行同步,在保证同步精度的前提下减少网络同步所需的消息数量。实验结果表明,相比传统的RBS和TPSN算法,提出的簇-树结构同步算法可使网络的平均同步精度保持在更高的水平,并有效地降低网络同步时节点的能耗。
具有局部特性的传感网链路质量估计方法
李君伟,李士宁,张羽
计算机科学. 2015, 42 (12): 195-200, 206. 
摘要 ( 29 )   PDF(615KB) ( 37 )   
参考文献 | 相关文章 | 多维度评价
重编程是实现无线传感器网络中软件更新的重要手段。传统的重编程协议性能评价方法仍然存在通过实验床和仿真平台评价其性能的优劣。目前,通过对重编程协议的软件更新过程建模并建立分析模型的性能评价方法,相对于传统的实验床和仿真平台,既能准确灵活地评价大规模部署的网络的性能,又能快速高效地给出性能分析结果,是当前重编程协议性能评价方法的新领域。然而,这一分析模型依赖于传感网链路质量的估计值。当前的传感网链路质量估计方法没有考虑到软件更新过程存在的局部特性,因而网络适应性差,无法广泛使用。提出了一种具有局部特性的网络链路质量估计方法,将软件更新过程中任一节点的局部邻居区域的链路质量期望作为这一节点的局部链路质量,能够更准确地反映软件更新过程的网络特征。使用这一具有局部特性的网络链路质量估计方法计算的估计值,将使得分析模型所计算出的重编程性能指标即完成时间与实验床运行时间的吻合度提高。将这一估计方法应用于分析模型,对线型和网格型网络的分析结果显示,分析结果与实验床的运行结果的误差低于5%。因此,与现有的估计方法相比,提出的方法在线型和网格型网络中适用性更强。
多星座卫星导航系统定位方程直接解算算法的研究
汪文雯,张可,黄彬
计算机科学. 2015, 42 (12): 201-206. 
摘要 ( 31 )   PDF(427KB) ( 291 )   
参考文献 | 相关文章 | 多维度评价
在导航定位系统中,传统的最小二乘定位解算算法需要通过线性迭代求解,计算量大且迭代过程不稳定,影响导航定位的实时性以及稳定性。针对此问题,利用多卫星导航系统可获得多颗可见卫星的特点,提出了“3+2+2”和“3+3+2”的直接解算算法,以及当3个星座系统可见卫星数目达到9颗及以上时将导航定位的非线性伪距方程组直接转化为线性方程组的直接解算算法。3种方法均不需要预先假设接收机的初始位置坐标,避免了线性迭代过程,减小了计算量。通过仿真对提出的直接解算算法进行了验证,结果表明所提算法均能够有效实现多星座导航系统定位解算。
无线纳米网中太赫兹电磁波传输特性分析
王万良,吴腾超,姚信威,李伟琨,陈 超
计算机科学. 2015, 42 (12): 207-211. 
摘要 ( 30 )   PDF(435KB) ( 125 )   
参考文献 | 相关文章 | 多维度评价
针对基于太赫兹通信的电磁纳米网络,深入分析太赫兹电磁波路径传输特性以及大气分子吸收特性,从能耗的角度构建太赫兹信道传输的数学模型。分别针对不带反射路径的传输场景和带有反射路径的传输场景来分析路径传输特性;利用大气辐射原理来分析大气分子吸收特性。在不同传输距离和传输频率下,结合路径传输和大气分子吸收对太赫兹电磁波传输能量损耗进行仿真。结果表明:分子吸收损耗是太赫兹电磁波传输能量损耗的重要组成部分,大气分子吸收损耗与传输介质分子组成有关;路径传输损耗受到传输频率和距离的影响。分析结果对太赫兹通信频段的选择以及纳米节点能耗设计有重要参考价值。
一种联合QoS约束及波束形成准则的蜂窝网络高效协作传输技术
宋海龙,张书真
计算机科学. 2015, 42 (12): 212-214, 219. 
摘要 ( 26 )   PDF(314KB) ( 26 )   
参考文献 | 相关文章 | 多维度评价
针对由于通信干扰严重导致的蜂窝网络数据传输效率不高、能耗较大的问题,提出一种联合QoS约束及波束形成准则的蜂窝网络高效协作传输技术。该技术采用了由宏蜂窝、飞蜂窝组成的蜂窝网络系统模型,分析了网络通信过程中的信号干扰及功率情况。基于QoS约束的高效协作传输算法,采用QoS约束把数据传输的能量效率问题优化成波束成形和功率分配问题,并将Qos约束考虑进波束形成准则,从而改善网络的干扰状态,提高能量效率。实验仿真结果的对比情况表明,该技术可以提高蜂窝网络进行数据传输的能量效率,并减少通信干扰。
基于6LoWPAN的边缘路由器设计研究
肖湘宁,王 鹏,李建立,郭 萍
计算机科学. 2015, 42 (12): 215-219. 
摘要 ( 29 )   PDF(895KB) ( 43 )   
参考文献 | 相关文章 | 多维度评价
提出了一种智能6LoWPAN传感网络边缘路由器设计实现方法。该方法基于嵌入式操作系统Linux系统平台和单CPU的方案实现,通过在系统Linux上移植6LoWPAN协议簇,使射频接口LAN承载6LoWPAN网络,本地6LoWPAN传感网络通过边缘路由器接入互联网。6LoWPAN传感网络边缘路由器采用多协议融合的方式实现IPv4/IPv6双栈协议、NAT64协议、6to4隧道协议的统一,实现6LoWPAN网络节点通过6LoWPAN边缘路由器与互联网在不同网络环境下的自适应接入。
信息安全
一种基于模糊策略的自动信任协商方案
马小信,曾国荪
计算机科学. 2015, 42 (12): 220-223, 239. 
摘要 ( 32 )   PDF(441KB) ( 39 )   
参考文献 | 相关文章 | 多维度评价
自动信任协商是一种在开放网络环境下陌生实体之间通过披露属性证书建立双方信任关系的重要手段。针对传统信任协商中协商规则描述较为严格、协商成功率和效率较低的问题,提出了一种基于模糊逻辑的自动信任协商方案,它通过将模糊逻辑引入信任协商,对信任协商规则进行模糊化处理,可以更简单而灵活地描述协商规则,并由此优化协商路径选择。分析表明,这种协商方案能够在一定程度上提高协商成功率和效率。
一种基于描述语言的软件可信发布方法研究
李剑飞,徐开勇,金雷
计算机科学. 2015, 42 (12): 224-228, 262. 
摘要 ( 25 )   PDF(484KB) ( 41 )   
参考文献 | 相关文章 | 多维度评价
目前对于高安全要求的内网环境,如何利用可信计算技术确保软件发布的安全与可靠具有重要的研究意义。由于软件可信发布具有动态性,即不同用户和平台对软件的要求不尽相同,而人为配置发布不仅效率低下而且无法确保其安全可靠,因此提出了一种用户、平台、软件之间相互选择的智能发布策略,其中的软件功能可信度算法可定量计算出软件功能符合用户需求的程度,智能匹配算法根据依赖关系生成安装序列以确保安装运行的顺利进行。同时为了描述发布过程中的软件信息及满足发布算法的需求,设计了一种基于XML的软件描述语言SDDL(Software Distribution Description Language)。通过分析及实例证明了此发布方式确实能增强软件发布的可信性。
深空网络的高效安全通信机制
任方,郑 东
计算机科学. 2015, 42 (12): 229-232, 267. 
摘要 ( 28 )   PDF(414KB) ( 34 )   
参考文献 | 相关文章 | 多维度评价
安全的深空通信网络是实现深空探测的重要保证之一。研究了基于天基网的深空网络体系结构,给出了一种安全通信机制。该机制采用基于属性的公钥加密算法来实现安全的深空数据传输。深空节点为数据选择加密属性集,用户能够解密密文当且仅当该加密属性集满足用户持有的访问树。该方案中用户与深空节点之间无需进行身份认证,大大减少了信息交互次数,比较适用于深空网络通信,以弥补其数据传输代价高昂的缺陷。
一种基于域知识的协议状态机主动推断算法
王辰,吴礼发,洪征,郑成辉,庄洪林
计算机科学. 2015, 42 (12): 233-239. 
摘要 ( 31 )   PDF(620KB) ( 125 )   
参考文献 | 相关文章 | 多维度评价
现有基于L*算法的协议状态机主动推断方法忽略了协议特有的域知识,将协议报文抽象为相互独立、无意义的符号,并完全随机地生成测试样本进行状态机等价判定,导致产生大量的无效询问和测试样本,在真实网络环境下推断效率较低。在L+M算法的基础上提出了一种基于域知识的协议状态机主动推断算法L+N,其改进主要体现在:依据会话样本集提取各报文之间的强顺序约束关系来过滤无效的输出询问,构建会话样本集对应的扩展前缀树接受器(Extended Prefix Tree Accepter,EPTA)对输出询问进行预响应,提出了一种基于正例样本变异的等价询问近似判定算法以提升寻找反例的效率。实验结果表明,L+N算法能够大幅提高推断效率,并且具有与L+M算法相同的推断准确度。
基于马尔可夫链模型的图像拼接篡改盲取证算法
卜江,郑彬,陈海洋
计算机科学. 2015, 42 (12): 240-242. 
摘要 ( 30 )   PDF(251KB) ( 47 )   
参考文献 | 相关文章 | 多维度评价
利用马尔可夫链对图像DCT变换系数的相关性进行建模,提取模型的状态转移概率矩阵作为特征向量,然后采用支持向量机分类器对自然图像和篡改图像进行分类。实验结果表明,该算法的平均准确率达到了86%,性能优于Ng提出的基于双相干特征的拼接图像检测算法。
多线程环境中的二维降密策略
金丽,朱 浩
计算机科学. 2015, 42 (12): 243-246, 282. 
摘要 ( 46 )   PDF(403KB) ( 40 )   
参考文献 | 相关文章 | 多维度评价
降密策略的主要目的在于确保程序中敏感信息的安全释放。目前,降密策略的安全条件和实施机制的研究主要集中在顺序式程序设计语言,它们不能直接移植到多线程并发环境,原因在于攻击者能利用线程调度的某些性质推导出敏感信息。为此,基于多线程程序设计语言模型和线程调度模型,建立了支持多线程并发环境的二维降密策略,有效确保了在合适的程序点降密合适的信息;建立了多线程并发环境下该降密策略的动态监控机制,并证明了该实施机制的可靠性。
一种大数据环境下的新聚类算法
李斌,王劲松,黄玮
计算机科学. 2015, 42 (12): 247-250. 
摘要 ( 46 )   PDF(306KB) ( 45 )   
参考文献 | 相关文章 | 多维度评价
提出了一种新的聚类算法NGKCA,该算法克服了经典聚类算法检测率和稳定性的不足,适用于解决大数据环境下的聚类问题。NGKCA聚类算法包括4个阶段:首先利用谱聚类NJW算法对大数据集进行列降维和数据归一化处理,其次引入对初始值不敏感的粒子群算法对数据集进行行降维从而选出临时的聚类中心集,接着通过全局Kmeans算法对最佳聚类中心集进行聚类以获取聚类中心点,最后使用粒子群算法对聚类中心点进行调整进而获取最终的聚类划分。在一些著名的机器学习数据集和国际标准的网络安全数据集KDDCUP99上进行实验,结果表明:提出的算法比谱聚类、Kmeans、粒子群、全局Kmeans等常见算法具有更好的稳定性和更高的检测率,与全局Kmeans算法相比具有更优的时间复杂度。
一种基于GF(23)的(K,N)有意义无扩张图像分存方案
欧阳显斌,邵利平
计算机科学. 2015, 42 (12): 251-256. 
摘要 ( 28 )   PDF(1012KB) ( 36 )   
参考文献 | 相关文章 | 多维度评价
传统有意义图像分存存在像素扩张,通常只对分存信息以较短的认证信息进行甄别,从而导致重构的秘密像素真实性无法准确鉴别。针对此问题,提出一种基于GF(23)的(K,N)有意义无扩张图像分存方案。在该方案中,首先生成加密映射表并利用秘密像素的位置信息对秘密像素进行加密;然后将秘密像素的认证信息和加密像素在GF(23)有限域下进行(K,N)分存,嵌入到掩体图像对应的像素中;最后将映射表的生成密钥进行(K,N)分存,计算每个子密钥的MD5值并公布到第3方公信方以防止掩体图像持有者作弊。实验结果表明,所提方案能准确地识别出秘密图像攻击区域,不存在任何像素扩张,掩体图像与秘密图像等大且嵌入分存信息的掩体图像具有较好的视觉质量。
面向PaaS云的信息流控制框架设计与实现
邵婧,陈左宁,殷红武,许国春
计算机科学. 2015, 42 (12): 257-262. 
摘要 ( 31 )   PDF(511KB) ( 58 )   
参考文献 | 相关文章 | 多维度评价
分布式信息流控制(DIFC)是实施端到端数据保护的一种有效方法。现有DIFC方法存在信息流控制粒度单一、需要修改语言运行时环境等问题,不能很好地满足PaaS平台的数据安全需求。基于最典型的PaaS云平台GAE,提出了一个信息流控制框架GIFC,其结合了对象级、消息级和SQL级3种控制粒度。组件内基于Python库来控制调用 对象的方法中所涉及的实体间的信息交互;组件间消息代理根据消息安全标记来过滤消息,以此限制组件可以接收的消息集;组件与数据库之间扩展GAE中的数据模式支持标记信息在datastore中的持久化存储。实验表明,多种IFC粒度相结合有效平衡了信息流控制精度和运行性能。
人工智能
基于当前最优解的分段搜索策略的人工蜂群算法
毛力,周长喜,吴滨
计算机科学. 2015, 42 (12): 263-267. 
摘要 ( 32 )   PDF(392KB) ( 50 )   
参考文献 | 相关文章 | 多维度评价
为了克服人工蜂群算法在求解函数优化问题中所存在的局部搜索能力差、收敛精度低的缺点,提出了一种基于当前最优解的分段搜索策略的人工蜂群算法。该算法中跟随蜂利用由全局当前最优解和个体当前最优解引导的局部搜索策略逐维进行变异,并采用基于“分段思想”的局部搜索策略对蜜源进行贪婪更新,以提高蜜源的更新效率,从而提高了人工蜂群算法的局部搜索能力。6个标准测试函数的仿真实验结果表明,与基本人工蜂群算法相比,改进后的人工蜂群算法在寻优精度和收敛速度上均有明显提高。
具有容噪特性的C4.5算法改进
王伟,李磊,张志鸿
计算机科学. 2015, 42 (12): 268-271, 287. 
摘要 ( 30 )   PDF(920KB) ( 39 )   
参考文献 | 相关文章 | 多维度评价
针对有噪声的高维数据引起决策树预测准确率下降的问题,利用容噪主成分分析(Noise-free Principal Component Anlysis,NFPCA)算法思想对C4.5算法改进而形成NFPCA-in-C4.5算法。该算法一方面将高维数据噪声控制问题转化为拟合数据特征与控制平滑度相结合的最优化问题,从而获得主成分空间;另一方面在决策树自顶向下构建新节点的过程中,再将主成分空间恢复到原始数据空间来避免降维过程中属性特征信息永久消失。实验结果表明NFPCA-in-C4.5算法兼具降维和容噪功能,避免了降维中由特征信息损失和噪声残留造成的预测模型准确率大幅降低的问题。
基于线性学习模型的社会媒体流排名算法
张威,李跃新
计算机科学. 2015, 42 (12): 272-274, 291. 
摘要 ( 29 )   PDF(579KB) ( 36 )   
参考文献 | 相关文章 | 多维度评价
在社会媒体中,对用户推荐适合的状态更新不仅降低了用户搜索信息的时间,也可以增加用户对服务的粘性。针对社会媒体中状态更新而推荐的准确性低的不足,提出了一种基于线性学习模型的状态更新排名算法。首先,根据社会媒体的性质定义了相应的偏好属性,并提出了一种基于线性模型的潜在偏好模型;其次,根据状态更新以及接收者的特征定义了相应的线性特征模型;最后,将潜在偏好模型和特征模型相结合,提出了一种引入时间效应的线性模型。通过实验验证表明,提出的算法与其它相关算法相比,算法的预测准确性更高,执行效率更快。
基于改进的排序学习的图片检索算法研究
谭光兴,刘臻晖
计算机科学. 2015, 42 (12): 275-277, 306. 
摘要 ( 30 )   PDF(320KB) ( 36 )   
参考文献 | 相关文章 | 多维度评价
图片检索是图片共享社会网络中的重要研究内容之一。传统的图片检索方法往往通过对用户输入的关键字和图片的文本描述加以匹配来进行图片检索。由于文本信息存在歧义性,图片的文本描述十分困难,因此检索结果的准确性低。为了提高图片检索的准确性,提出了基于排序学习的图片检索方法。将每幅图片通过多种特征描述符进行描述,当用户的输入为图片时,通过对比查询图片和图片库中图片的相似性进行图片检索。采用支持向量机和关联规则两种学习方法对特征描述符的权重组合进行学习,并提出了相应的学习算法。实验表明,提出的基于学习的图片检索方法与相关图片检索方法相比具有更高的准确性。此外,应用支持向量机和关联规则两种方法对分类函数进行学习时,由于两种算法通过相同的数据实例对图片描述符的权重进行学习,因此得到的结果是相关的。
基于动态规划求解时间序列DTW中心
孙焘,夏 斐,刘洪波
计算机科学. 2015, 42 (12): 278-282. 
摘要 ( 35 )   PDF(346KB) ( 160 )   
参考文献 | 相关文章 | 多维度评价
中心时间序列表明了一个时间序列集合中的公共特征,是时间序列聚类的重要手段。提出了一个利用动态规划求解两条时间序列DTW中心的方法,即以最小化中心序列到两条样本序列的DTW距离平方和为目标,递归求解最优解。在此基础上,给出了基于中心与样本匹配度的剪枝方法,降低了时间复杂度。并在理论上证明了该方法可以获得最优解。实验结果显示,相比于DBA算法,该算法能够获得更小的DTW距离平方和,并且有更好的鲁棒性。
有根系统发生树的精确有效比较
李曙光,陈姝颖,朱丽波
计算机科学. 2015, 42 (12): 283-287. 
摘要 ( 57 )   PDF(411KB) ( 405 )   
参考文献 | 相关文章 | 多维度评价
系统发生树代表了不同物种之间进化关系的历史。生物信息学中的一个基本问题是对系统发生树进行比较。一种比较方法是通过定义树空间中两棵系统发生树之间的相似度或相异度来测定这两棵树的同异。Robinson-Foulds距离是目前使用最广泛的相异度。定义了一个用于有根系统发生树比较的新的相异度,该相异度考虑了子类间更精细的相似,而不是如Robinson-Foulds距离那样仅考虑子类相同与否,因此能够提供更精确、清晰的测量。给出了两个能有效计算这个相异度的算法。简单修改之后,这些结果适用于其他5个相关的比较指标。
图形图像与模式识别
一种采用纹理分布特征的标定方法
李娜,耿国华,王小凤
计算机科学. 2015, 42 (12): 288-291. 
摘要 ( 29 )   PDF(817KB) ( 45 )   
参考文献 | 相关文章 | 多维度评价
纹理重建是文物数字化保护工作的重要内容,针对中小型文物纹理重建中多视角纹理采集的自动化标定问题,提出了一种新的用于纹理采集的量化特征标定方法,以提高三维空间点与二维像素点之间拟合的精度。按照实物表面色彩种类及几何图案数量两类重要的纹理特征,进行纹理分布数据的归一化整理;利用归一化后的数据对拍摄角度的标定模板进行标定;最后通过透视投影原理计算三维空间点与二维像素点之间的多视角配准与映射。实验结果表明,量化特征标定方法的非均匀特性与均匀标定模板相比较,在不明显增加计算量的同时,能更好地体现纹理精度。
一种基于相邻匹配的分形图像检索算法
张思思,刘 宇,赵志滨
计算机科学. 2015, 42 (12): 292-296, 311. 
摘要 ( 27 )   PDF(998KB) ( 43 )   
参考文献 | 相关文章 | 多维度评价
分形码用来描述图像内跨尺度相似性冗余信息。通过分形码记录图像特征并将其用于图像相似度判断及图像检索。基于自适应四叉树分割方法,提出了图像快速分形编码方法。所提方法通过邻域内固定块的相似性判别快速提取分形码,减少了图像分割层次,缩短了编码时间并保证了图像解码质量。同时提出了一种新的快速判别图像间相似块的距离公式,提升了图像相似度判断的准确性。实验结果表明,相对于灰度直方图判别法,本算法大幅提高了图像检索的查全-查准率。相比于文献中的分形检索算法,本算法缩短了编码时间并降低了分割块数,从而提高了检索效率。
基于Camshift反馈码本模型的手抓取物跟踪方法
赵翠莲,王洪,范志坚,郭晶
计算机科学. 2015, 42 (12): 297-301. 
摘要 ( 27 )   PDF(683KB) ( 41 )   
参考文献 | 相关文章 | 多维度评价
针对Camshift算法在复杂背景下无法自动跟踪目标的问题,提出一种基于Camshift反馈码本模型的运动目标检测和跟踪算法。该算法首先利用码本模型检测前景目标,然后采用Camshift在颜色概率分布图中跟踪前景区域中的目标,通过窗口尺寸比较和直方图相关性判断来解决自动跟踪,通过窗口位置预测和尺寸扩大来改进下一帧Camshift算法的输入搜索窗口,同时并集操作多个目标处理后的矩形窗口,并将其反馈为下一帧码本模型的图像检测区域。最后将该算法应用于手和目标物的抓取状态判断上,具体过程是在静态背景下利用两个摄像头采集到的图像进行手和目标物的检测和跟踪,通过矩形相交性判断抓取次数,以验证跟踪算法的有效性。实验结果表明,通过信息反馈减小了目标检测和跟踪的搜索区域,提高了算法的实时性,在单摄像头下可提高处理帧频130%。
基于PCA的GHA算法在BP网中的融合应用
范燕,吴小俊,邵长斌,宋晓宁
计算机科学. 2015, 42 (12): 302-306. 
摘要 ( 49 )   PDF(676KB) ( 45 )   
参考文献 | 相关文章 | 多维度评价
针对传统特征提取方法和BP神经网络相结合而存在的缺点,提出一种新的分类器模型“PCABP网”。首先利用PCA特征向量来初始化PCABP网的初始层权值矩阵,由此新模型的初始层起到取代PCA进行特征提取的作用。其次在训练过程中通过GHA和GD算法对初始层投影权值矩阵进行动态调节来优化特征向量。该方法从源头样本来优化“类别分离”和“特征提取”,找到对样本降维和分类的最佳契合点,以此来替代传统模式识别中“首先单独特征提取,其次利用分类器分类”的方式。在FERET人脸库上的实验结果验证了该方法的有效性。
基于改进分块颜色特征和二次提取的关键帧提取算法
刘华咏,李涛
计算机科学. 2015, 42 (12): 307-311. 
摘要 ( 23 )   PDF(931KB) ( 32 )   
参考文献 | 相关文章 | 多维度评价
关键帧提取技术是视频摘要、检索、浏览和理解中的一项重要技术。目前关键帧提取算法存在一些问题,例如特征选择复杂、阈值选择难、自适应性不强等。为了更有效地提取视频关键帧,提出了一种基于改进分块颜色特征和二次提取的关键帧提取算法。首先,对视频帧进行等面积矩形环划分;其次,提取矩形环的HSV量化颜色特征,并由帧图像中心到外依次减小每个矩形环特征的权值以突出图像主体部分;然后,依据相邻视频帧间特征的显著性变化初步选取关键帧;最后,依据初次提取的关键帧在视频中的位置间隔大小进行二次提取优化关键帧。实验结果表明,该方法具有良好的适应性,同时能够有效避免因镜头有突然闪光或物体快速运动而提取过多的关键帧,最终提取的关键帧能够比较全面准确地表达视频内容。