Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2017年 第54卷 第3期    出版日期:2017-03-01
网络技术
参与式感知:以人为中心的智能感知与计算
于瑞云,王鹏飞,白志宏,王兴伟
2017, 54(3):  457-473.  doi:10.7544/issn1000-1239.2017.20151021
摘要 ( 998 )   HTML ( 6)   PDF (3490KB) ( 648 )  
相关文章 | 计量指标
越来越多的无线智能移动设备集成了大量不同种类的传感器模块,与此同时无线移动网络也迅速普及.这些因素推动了参与式感知概念的提出与发展.参与式感知又被称为城市感知、以用户为中心的感知、群智感知.参与式感知可以解决传统无线传感网络难以大规模部署以及部署成本高昂的问题.参与式感知系统通过利用移动智能设备中的传感器、社交网络以及个人设备使用行为对参与者周围的物理环境、社会环境或者个人状态进行自主式采集、传输和分析,并做出智能化决策.这对未来实现智慧城市、普适计算以及物联网等重大概念具有重要的意义.首先介绍了参与式感知相关概念、理论以及相应的应用原型系统;然后介绍了参与式感知相关研究前沿热点,包括参与式感知的原型设计、感知数据处理、激励机制、隐私保护、恶意攻击以及不同移动网络的问题等;最后给出研究参与式感知的一般方法.
传感网中时延受限的移动式数据收集方法综述
王文华,王田,吴群,王国军,贾维嘉
2017, 54(3):  474-492.  doi:10.7544/issn1000-1239.2017.20150953
摘要 ( 589 )   HTML ( 1)   PDF (3218KB) ( 406 )  
相关文章 | 计量指标
数据收集是无线传感器网络中研究的热点问题之一,然而在传统的无线传感器网络中,基站附近的节点由于承担了大量数据转发任务而导致自身能量过早耗尽,缩短了网络的生命期.不少研究通过引入能量较为充足的移动性节点来收集数据,以节省普通传感器节点的能量,但是却导致了数据收集时延过大,如何在保证数据收集时延的前提下最大化网络生命期已成为近几年研究的热点问题.对目前主要的时延受限的移动式数据收集方法进行了充分调研,通过对这些方法的详细分类和比较,归纳了时延受限的移动式数据收集的各类方法的特点,分析了这些方法的优缺点和适用范围,总结了存在的主要问题,并指出了未来的研究方向.
基于混合压缩感知的分簇式网络数据收集方法
李哲涛,臧浪,田淑娟,李仁发
2017, 54(3):  493-501.  doi:10.7544/issn1000-1239.2017.20150885
摘要 ( 687 )   HTML ( 0)   PDF (3002KB) ( 397 )  
相关文章 | 计量指标
为了减少分簇式传感器网络中的数据传输量并均衡网络负载,提出了一种采用混合压缩感知(compressive sensing, CS)进行数据收集的方法.1)选取各临时簇中距离簇质心最近的一些节点为候选簇头节点,然后依据已确定的簇头节点到未确定的候选簇头节点的距离依次确定簇头;2)各普通节点选择加入距离自己最近的簇中;3)贪婪构建一棵以Sink节点为根节点并连接所有簇头节点的数据传输树,对数据传输量高于门限值的节点使用CS压缩数据传输.仿真结果表明:当压缩比率为10时,数据传输量比Clustering without CS和SPT without CS分别减少了75%和65%,比SPT with Hybrid CS和Clustering with Hybrid CS分别减少了35%和20%;节点数据传输量标准差比Clustering without CS和SPT without CS分别减少了62%和81%,比SPT with Hybrid CS和Clustering with Hybrid CS分别减少了41%和19%.
人工智能
基于模型诊断中结合问题特征的新方法
欧阳丹彤,周建华,刘伯文,张立明
2017, 54(3):  502-513.  doi:10.7544/issn1000-1239.2017.20150952
摘要 ( 620 )   HTML ( 0)   PDF (1738KB) ( 461 )  
相关文章 | 计量指标
基于模型诊断一直是人工智能领域中热门的研究问题.近些年来,随着SAT求解器效率的逐渐提高,基于模型的诊断也被转换成SAT问题进行求解.在对基于模型诊断求解方法CSSE-tree深入研究基础上,结合诊断问题和SAT求解过程的特征,给出先对包含组件个数较多的候选诊断进行求解的方法,进而减小SAT求解问题的规模;在对极小诊断解和非极小诊断解剪枝方法的基础上,首次提出非诊断解定理及非诊断解空间的剪枝方法,有效地实现了对诊断的无解空间进行剪枝.根据组件个数较多的候选诊断先求解及有解无解剪枝方法特征,构建基于反向搜索的LLBRS-tree方法.实验结果表明:与CSSE-tree算法相比,LLBRS-tree算法减少了SAT求解次数、减小了求解问题规模,效率较好,尤其是求解多诊断时效率提高更为显著.
基于GPU的约束网络模型和并行弧相容算法
李哲,李占山,李颖
2017, 54(3):  514-528.  doi:10.7544/issn1000-1239.2017.20150912
摘要 ( 565 )   HTML ( 1)   PDF (1846KB) ( 384 )  
相关文章 | 计量指标
弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4\+GPU与改进算法AC4\+GPU+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案.
线性插值投影次梯度方法的最优个体收敛速率
陶蔚,潘志松,朱小辉,陶卿
2017, 54(3):  529-536.  doi:10.7544/issn1000-1239.2017.20160155
摘要 ( 583 )   HTML ( 0)   PDF (1988KB) ( 412 )  
相关文章 | 计量指标
投影次梯度算法(projected subgradient method, PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method, DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能.
基于保留分类信息的多任务特征学习算法
王珺,卫金茂,张璐
2017, 54(3):  537-548.  doi:10.7544/issn1000-1239.2017.20150963
摘要 ( 729 )   HTML ( 1)   PDF (2041KB) ( 413 )  
相关文章 | 计量指标
在模式识别中,特征选择是一种非常有效的降维技术.特征评价标准在特征选择过程中被用于度量特征的重要性,但目前已有的标准存在着只考虑类之间的分离性而未考虑其相关性、无法去除特征之间的分类冗余性以及多用于单变量度量而无法获取子集整体最优性等问题.提出一种保留分类信息的特征评价准则(classification information preserving, CIP),并使用多任务学习技术进行实现.CIP是一种特征子集度量方法,通过F范数实现已选特征子集的分类信息与原始数据分类信息的差异最小化,并通过l2,1范数约束选择特征个数.近似交替方向法被用于求解CIP的最优解.理论分析与实验结果表明:CIP选择的最优特征子集不仅最大程度上保留了原始数据类别之间的相关性信息,而且有效地降低了特征之间的分类冗余性.
3D打印物体的稳定平衡优化
吴芬芬,刘利刚
2017, 54(3):  549-556.  doi:10.7544/issn1000-1239.2017.20150911
摘要 ( 515 )   HTML ( 0)   PDF (2865KB) ( 284 )  
相关文章 | 计量指标
3D打印日渐流行,赋予大众创造物体的能力.首先通过计算机中3D建模软件构造3D数字模型,再借助3D打印加以制造.虚拟环境中无物理规则的特点使得模型千姿百态,但是通过3D打印之后发现物体无法平衡站立.首次提出3D打印物体的稳定平衡优化问题,针对这一问题,研究不倒翁的原理,提出稳定平衡优化算法,使得物体达到稳定平衡.具体做法为先将物体体素化,迭代式从水平、垂直方向进行逐体素的挖空,选取最佳的挖空方式;对于个别极端例子,再通过对底部小范围内的修改来达到稳定平衡.逐体素的启发式挖空策略避免了挖空可能出现的悬浮、自相交等问题;底部局部小范围的修改也保证了物体的形状基本不变,该方法的可行性通过多个例子的成功优化得到证明.
软件技术
支持室内障碍空间的DSP-Topk查询优化算法研究
李博涵,张潮,李东静,许建秋,夏斌,秦小麟
2017, 54(3):  557-569.  doi:10.7544/issn1000-1239.2017.20150895
摘要 ( 525 )   HTML ( 0)   PDF (3039KB) ( 277 )  
相关文章 | 计量指标
多目标优化查询是目前移动对象数据管理的研究热点.多目标优化查询过程中,用户关心的目标对象属性可能依赖于其他移动对象,因此移动对象之间的相互影响将导致目标对象属性存在不确定性.已有的多目标优化算法需要遍历所有目标对象,且不能有效支持目标对象属性的动态变化.基于以上问题,提出了一种有效的应用于障碍空间的多目标优化算法DSP-Topk (dynamic and support pruning Topk),该算法采用可视区域模型处理障碍空间中移动对象的距离计算,利用基于最大夹角差的可视区域方法,提高了计算距离的效率.进而,利用动态调整机制解决目标对象属性的不确定性,预处理的裁剪策略提高了算法效率.实验结合商场真实商品数据集进行测试,与已有的Topk和DS-Topk算法对比表明:所提算法在查询效率上有显著提高,验证了算法的有效性.
TMS:一种新的海量数据多维选择Top-k查询算法
韩希先,刘显敏,李建中,高宏
2017, 54(3):  570-585.  doi:10.7544/issn1000-1239.2017.20150615
摘要 ( 946 )   HTML ( 0)   PDF (5656KB) ( 419 )  
相关文章 | 计量指标
在许多应用中,Top-k是一种十分重要的查询类型,它在潜在的巨大数据空间中返回用户感兴趣的少量数据.Top-k查询通常具有指定的多维选择条件.分析发现:现有算法无法有效处理海量数据的多维选择Top-k查询.提出了一个基于有序列表的TMS(top-k with multi-dimensional selection)算法,有效计算海量数据上的具有多维选择的Top-k结果.TMS算法利用层次化结构的选择属性网格对原数据表执行水平划分,每一个分片的元组以面向列的模式存储,并且度量属性的列表根据其属性值降序排列.给定多维选择条件,TMS算法利用选择属性网格确定相关网格单元,有效减少需要读取的元组数量,提出双排序方法执行多维选择的渐进评价,并提出有效剪切操作来剪切不满足多维选择条件和分数要求的候选元组.实验结果表明:TMS算法性能优于现有算法.
面向智慧民生领域的增量交互式数据集成方法
夏丁,王亚沙,赵梓棚,崔达
2017, 54(3):  586-596.  doi:10.7544/issn1000-1239.2017.20151048
摘要 ( 594 )   HTML ( 2)   PDF (2394KB) ( 343 )  
相关文章 | 计量指标
智慧民生作为智慧城市的重点领域,包含众多应用系统,积累了大量层次结构数据.为了形成城市范围完整数据集,需要集成并统一异构的数据模式,向用户提供统一的数据视图.针对智慧民生领域的领域知识宽泛、缺乏中文语义匹配支持、模式数量众多、元素标签缺失但实例数据丰富等几方面特点,提出了一种增量交互式模式集成方法.该方法采用增量迭代的方式逐步完成多模式集成任务,大幅降低集成计算量;在模式匹配阶段,综合利用模式信息和实例数据构造了多种适用于中文且能力互补的匹配器,并通过相似度熵来度量机器的决策置信度,适度引入人工干预;在中介模式生成阶段,处理模式间可能出现的各种冲突,最终输出全局统一的中介模式.利用从互联网爬取的多源二手房数据设计并完成实验,实验结果表明:此方法在人工干预程度足够小的前提下,具有较好的模式匹配准确性.
面向微服务架构的容器级弹性资源供给方法
郝庭毅,吴恒,吴国全,张文博
2017, 54(3):  597-608.  doi:10.7544/issn1000-1239.2017.20151043
摘要 ( 969 )   HTML ( 5)   PDF (3223KB) ( 600 )  
相关文章 | 计量指标
容器作为物理资源的逻辑抽象,具有资源占用少、资源供给快等特点,适合工作负载突变的互联网应用模式,特别是面向微服务架构的新型服务范型.已有工作受限于物理机和虚拟化环境,或资源难以弹性供给或资源供给时效性较差,难以应对负载突变(flash-crowds)场景.针对此问题提出了一种服务质量(quality of service, QoS)敏感的、基于前馈的容器资源弹性供给方法,该方法采用排队论刻画工作负载、资源利用率和响应时间的关联关系,构建应用性能模型.其中,响应时间采用模糊自适应卡尔曼滤波进行预测(前馈控制器),预测结果违背QoS是触发资源弹性供给的依据.基于CloudStone基准的实验结果显示,前馈控制器具有快速收敛的特点,对响应时间的预测误差小于10%.在flash-crowds场景下,相对于已有方法可有效保障应用的QoS.
基于接口契约的有状态Web服务用例集生成
李吟
2017, 54(3):  609-622.  doi:10.7544/issn1000-1239.2017.20151045
摘要 ( 482 )   HTML ( 0)   PDF (4631KB) ( 411 )  
相关文章 | 计量指标
Web服务具有对外只提供接口文档、技术规范复杂和运行时态瞬时多变等特性,如何有效地自动化生成测试数据仍旧是个难题.目前,针对有状态Web服务操作序列的测试研究较少,现有的方法对服务的行为信息和操作之间的数据依赖关系考虑不足,且缺乏有效的测试自动化手段,进而导致测试代价较高以及生成的测试数据缺乏针对性.对此,提出一种结合有限状态机(EFSM)模型和操作接口契约的测试数据生成方法,该方法根据标准WSDL文档建立操作模型,形式化描述操作之间的交互关系,并对其进行语义标注,基于EFSM模型生成操作序列测试路径,随后采用操作接口契约关系获取测试路径中的测试数据.通过案例表明,这种有状态Web服务的用例生成方法能够高效地生成合理的测试数据,并在错误检测能力以及用例有效性方面优于现有的方法.
基于捕获/重放的Web应用跨浏览器兼容性检测
吴国全,何妹妹,魏峻,钟华,黄涛
2017, 54(3):  623-632.  doi:10.7544/issn1000-1239.2017.20151051
摘要 ( 568 )   HTML ( 3)   PDF (1597KB) ( 366 )  
相关文章 | 计量指标
由于浏览器实现技术的差异以及对标准支持程度的不同,Web应用的跨浏览器不兼容性(cross-browser incompatibilities, XBI)已成为Web应用开发者面临的严重问题.现有的兼容性检测工具仅考虑用户交互事件而忽略了浏览器内部事件,无法保证在不同的浏览器平台上有相同的执行,导致检测结果出现大量误报和漏报.提出了一种基于捕获/重放技术的Web应用跨浏览器兼容性检测方法,在事件捕获阶段记录Web应用在参考浏览器平台运行时产生的各种非确定性事件,并在重放阶段在测试浏览器平台中进行远程重放.通过在重放过程中采集页面信息,保证了检测结果的准确性.为避免重复检测,设计了一种增量式的检测算法提高了检测效率.实验结果表明了所提出方法的有效性.
基于组合机器学习算法的软件缺陷预测模型
傅艺绮,董威,尹良泽,杜雨晴
2017, 54(3):  633-641.  doi:10.7544/issn1000-1239.2017.20151052
摘要 ( 1056 )   HTML ( 5)   PDF (1940KB) ( 914 )  
相关文章 | 计量指标
软件缺陷预测是根据软件产品中提取的度量信息和已经发现的缺陷来尽早地预测软件可能还存在的缺陷,基于预测结果可合理分配测试和验证资源.基于机器学习的缺陷预测技术能够较全面地、自动地学习模型来发现软件中的缺陷,已经成为缺陷预测的主要方法.为了提高预测的效率和准确性,对机器学习算法的选择和研究是很关键的.对不同的机器学习缺陷预测方法进行对比分析,发现各算法在不同评价指标上有不同的优势,利用这些优势并结合机器学习中的stacking集成学习方法提出了将不同预测算法的预测结果作为软件度量并进行再次预测的基于组合机器学习算法的软件缺陷预测模型,最后用该模型对Eclipse数据集进行实验,表明了该模型的有效性.
一种可定制参考过程模型的自动构建方法
凌济民,张莉
2017, 54(3):  642-653.  doi:10.7544/issn1000-1239.2017.20151047
摘要 ( 462 )   HTML ( 0)   PDF (3481KB) ( 440 )  
相关文章 | 计量指标
过程模型在企事业单位中的应用日益普遍.由于企业为每个特定业务需求单独开发过程模型是复杂并且高成本的工作,因此企业通常使用参考过程模型作为过程模型开发的基础,以有效降低成本并提高开发效率和质量.由于参考模型需要领域专家大量的领域分析和抽象建模工作,如何基于领域内已有的过程模型变体自动创建出初步的参考模型以辅助领域专家的工作成为有意义的研究问题.现有的参考模型构建方法存在输出模型复杂度较高或难以全面表达领域内多样推荐实践等问题.为了创建代表性和可读性更强的参考模型,基于相似过程片段聚合技术,提出了一种支持层次化子过程结构的可定制参考过程模型的自动构建方法,全面支持可定制参考模型中基础过程、变更可选项以及约束关系的自动构建.案例研究结果表明:该方法生成的参考模型具有良好的领域代表性和模型复杂度.
面向DO-178C软件测试过程的目标符合性论证模式
杨阳,吴际,苑春春,刘超,杨海燕,邢亮
2017, 54(3):  654-668.  doi:10.7544/issn1000-1239.2017.20151055
摘要 ( 647 )   HTML ( 0)   PDF (8539KB) ( 336 )  
相关文章 | 计量指标
安全关键软件已广泛应用于众多领域.鉴于其对防范灾害风险方面的特殊要求,必须符合相关领域的安全性标准.但是目前对于如何建立面向标准的目标符合性论证模型,尚缺乏有效的方法.针对DO-178C标准中关于软件测试过程目标的特征描述,提出了一个基于GSN的目标论证模式描述框架,分别从解决问题、解决方案、应用方法和产生效果4个方面对目标论证模式进行描述;同时使用一种扩展的安全案例模式描述方式,用以描述面向标准的目标符合性论证模式.在此基础上,提出了3种面向DO-178C软件测试过程的目标符合性论证模式,分别是代码-需求符合性论证模式、需求测试覆盖率论证模式、结构测试覆盖率论证模式,并提出基于这些模式建立针对特定项目的目标符合性论证结构的实例化方法,为建立面向DO-178C软件测试过程的目标符合性论证结构提供了有效指导.通过一个机载嵌入式实时操作系统的案例,说明了提出的目标符合性论证模式的可用性和有效性.
基于EFSM不定型切片测试用例自动生成的研究
苏宁,郭俊霞,李征,赵瑞莲
2017, 54(3):  669-680.  doi:10.7544/issn1000-1239.2017.20151053
摘要 ( 586 )   HTML ( 1)   PDF (3654KB) ( 360 )  
相关文章 | 计量指标
基于模型的测试是软件测试中一个重要分支,但随着模型规模的增大,测试用例生成也变得越来越困难.扩展有限状态机(extended finite state machine, EFSM)是一种广泛应用的模型,它是对有限状态机(finite state machine,FSM)的扩展,能够更精确地刻画软件系统的动态行为.对EFSM模型的测试主要包含2个部分:测试迁移路径的生成和覆盖测试迁移路径的测试数据的生成.基于搜索的方法已被应用于测试数据的生成.为了提高在大规模EFSM模型中测试用例生成的效率,在前期对EFSM模型非终止性研究新型依赖性分析和切片技术的基础上,提出了基于EFSM模型不定型切片的测试用例生成方法和测试用例补全方法.通过2个案例分析得出:基于模型切片可以更加准确地生成可行路径和提高测试强度.基于7个基准EFSM模型的实验结果表明,在大多数情况下,在切片上生成测试用例的效率都比在原模型上高.