当期目录

2016年 第36卷 第1期 刊出日期：2016-01-10

上一期   下一期

第32届中国数据库学术会议(NDBC 2015)

集群环境下分布式索引的实现

翁海星, 宫学庆, 朱燕超, 胡华梁

2016, 36(1):  1-7.  DOI: 10.11772/j.issn.1001-9081.2016.01.0001

摘要 ( )   PDF (1303KB) ( )  

参考文献 | 相关文章 | 计量指标

针对分布式存储系统上使用非主键访问数据带来的性能问题,探讨在分布式存储系统上实现索引的相关关键技术。在充分分析分布式存储特征的基础上,提出了分布式索引设计和实现的关键点,并结合分布式存储系统的特点及相关的索引技术,讨论了索引的组织形式、索引的维护和数据一致性等问题;然后基于如上的分析,选择在分布式数据库系统OceanBase开源版本上,设计和实现分布式索引机制,并通过基准测试工具YCSB进行性能测试。实验结果表明,虽然辅助索引会对系统性能产生影响,但因为充分考虑了系统特征及存储特点,在不同数据规模下,该索引都能够将性能影响控制在5%以内。另外,使用冗余列的方式,能进一步将该索引的性能提升100%。

基于概率的大数据查询系统——Probery

伍晋博, 宋杰, 张莉, 鲍玉斌

2016, 36(1):  8-12.  DOI: 10.11772/j.issn.1001-9081.2016.01.0008

摘要 ( )   PDF (802KB) ( )  

参考文献 | 相关文章 | 计量指标

针对大数据环境下完整性查询时间代价消耗过高的问题,提出了一种采用近似完整性查询方法的系统——Probery。Probery所采用的近似完整性查询方法不同于传统的近似查询,其近似性主要体现为数据查全的可能性,是一种新型的数据查询方法。Probery首先将存入系统的数据划分为多个数据分段;然后,根据概率放置模型将各个数据分段的数据存储在分布式文件系统中;最后,对于给定的查询条件,Probery采用一种启发式查询方法进行概率查询。通过与其他主流的非关系型数据管理系统的查询性能进行比较,对Probery进行验证,Probery在损失8%查询完整性的情形下,查询时间较HBase相比节约了51%,较Cassandra相比节约了23%,较MongoDB相比节约了12%,较Hive相比节约了3%。实验结果表明,Probery可以适当地损失查询完整性来提高数据的查询性能,具有较好的通用性、适应性和可扩展性。

基于Supersonic的并行分组聚集

张兵, 孙辉, 范旭, 李翠平, 陈红, 王雯

2016, 36(1):  13-20.  DOI: 10.11772/j.issn.1001-9081.2016.01.0013

摘要 ( )   PDF (1253KB) ( )  

参考文献 | 相关文章 | 计量指标

针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。

压缩数据上的关系代数操作算法

丁鑫哲, 张兆功, 李建中, 谭龙, 刘勇

2016, 36(1):  21-26.  DOI: 10.11772/j.issn.1001-9081.2016.01.0021

摘要 ( )   PDF (923KB) ( )  

参考文献 | 相关文章 | 计量指标

针对在大数据管理中,在压缩的数据上无需解压即可进行相关操作的问题,在数据服从正态分布的前提下,根据列数据存储的特点,提出了一种新的面向列存储的压缩方法——CCA。首先,通过对列数据的长度进行归类;然后,采用抽样的方法获得重复度较高的前缀;最后,使用字典编码进行压缩,提出了列索引(CI)和列实体(CR)作为数据压缩结构来降低大数据存储的空间需求,从而直接有效地在压缩数据上支持选择、投影、连接等基本操作,并实现了基于CCA的数据库原型系统——D-DBMS。理论分析和在1 TB数据上的实验结果表明,该压缩算法能够显著提高大数据的存储效率和数据操作性能,与BAP和TIDC压缩方法相比,在压缩率分别提高了51%、14%;在执行速度上提高了47%、42%。

基于划分的增量式字符串相似性连接方法

燕彩蓉, 朱斌, 王健, 黄永锋

2016, 36(1):  27-32.  DOI: 10.11772/j.issn.1001-9081.2016.01.0027

摘要 ( )   PDF (890KB) ( )  

参考文献 | 相关文章 | 计量指标

字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤。针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——Inc-Join,并对方法的索引技术进行了优化。该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新。实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、 短字符串重复匹配次数减少为√n(n是批处理方式的匹配次数)。 实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小。同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销。

基于深度表示模型的移动模式挖掘

陈勐, 禹晓辉, 刘洋

2016, 36(1):  33-38.  DOI: 10.11772/j.issn.1001-9081.2016.01.0033

摘要 ( )   PDF (960KB) ( )  

参考文献 | 相关文章 | 计量指标

针对时空轨迹中位置顺序和时间对于理解用户移动模式的重要性,提出了一种新的用户轨迹深度表示模型。该模型考虑到时空轨迹的特点:1)不同的位置顺序表示不同的移动模式;2)轨迹有周期性并且在不同的时间段有变化。首先,将两个连续的位置点组合成位置序列;然后,将位置序列和对应的时间块组合成时间位置序列,作为描述轨迹特征的基本单位;最后,利用深度表示模型为每个序列训练特征向量。为了验证深度表示模型的有效性,设计实验将时间位置序列向量应用到用户移动模式发现中,并利用Gowalla签到数据集进行了实验评测。实验结果显示提出的模型能够发现"上班""购物"等明确的模式,而Word2Vec很难发现有意义的移动模式。

基于Markov模型与轨迹相似度的移动对象位置预测算法

宋路杰, 孟凡荣, 袁冠

2016, 36(1):  39-43.  DOI: 10.11772/j.issn.1001-9081.2016.01.0039

摘要 ( )   PDF (939KB) ( )  

参考文献 | 相关文章 | 计量指标

针对低阶Markov模型预测精度较差,以及多阶Markov模型预测稀疏率高的问题,提出一种基于Markov模型与轨迹相似度(MMTS)的移动对象位置预测算法。该方法借鉴了Markov模型思想对移动对象的历史轨迹进行建模,并将轨迹相似度作为位置预测的重要因素,以Markov预测模型的预测结果集作为预测候选集,结合相似度因素得出最终预测结果。实验结果表明,与k阶Markov模型相比,该方法的预测性能不会随着训练样本大小及阶数k的变化受到很大的影响,并且在大幅降低k阶Markov模型预测稀疏率的同时将预测精度平均提高了8%以上。所提方法不仅解决了k阶Markov模型的预测稀疏率高及预测精度不足的问题;同时提高了预测的稳定性。

基于手机轨迹数据的人口流动分析

孔扬鑫, 金澈清, 王晓玲

2016, 36(1):  44-51.  DOI: 10.11772/j.issn.1001-9081.2016.01.0044

摘要 ( )   PDF (1202KB) ( )  

参考文献 | 相关文章 | 计量指标

随着通信技术的发展和智能手机的普及,运营商基站所采集的大规模手机轨迹数据在城市规划、人口迁移等领域中发挥了重要价值。针对城市人口流动问题,提出一种利用手机轨迹数据的基于轨迹行为特征的人口流动判定(MF-JUPF)算法。首先,可对手机轨迹数据进行数据预处理,以提取用户活动轨迹;然后根据进出城市的行为模式提取重要特征,再根据真实标注数据集合利用多种分类模型进行参数训练;最后,根据模型训练结果判定用户轨迹是否为进出城市行为。所提系统使用MapReduce框架进行数据分析,以提高性能和可扩展性。基于真实数据集合的实验结果表明,对于进出城市的判定,该方法的准确率和召回率可达80%以上,与基于信号消失时长的人口流动判定(SD-JUPF)算法相比,在判定进入城市的准确率上提高了19.0%,召回率提高了13.9%;在判定离开城市的准确率上提高了17.3%,召回率提高了6.1%。相比非过滤算法,根据手机轨迹数据特点进行的数据过滤算法可减少处理时间36.1%以上。理论分析和实验结果表明MF-JUPF方法精度高,可扩展性好,因此对城市规划等领域有重要应用价值。

基于贝叶斯模型的多标签分类算法

张洛阳, 毛嘉莉, 刘斌, 吴涛

2016, 36(1):  52-56.  DOI: 10.11772/j.issn.1001-9081.2016.01.0052

摘要 ( )   PDF (869KB) ( )  

参考文献 | 相关文章 | 计量指标

针对二元关联法(BR)未考虑标签之间相关性,容易造成分类器输出在训练集中不存在或次数较少标签的不足,提出了基于贝叶斯模型的多标签分类算法(MLBM)和马尔可夫型多标签分类算法(MMLBM)。首先,建立仿真模型分析BR算法的不足,考虑到标签的取值应由属性置信度和标签置信度共同决定,提出MLBM。其中,通过传统的分类算法计算获得属性置信度,以及通过训练集得到标签置信度。然后,考虑到MLBM在计算属性置信度时必须考虑所有已分类的标签,分类器的性能容易受无关或弱关系的标签影响,所以使用马尔可夫模型简化置信度的计算提出了MMLBM。理论分析和仿真实验表明,与BR算法相比,MMLBM的平均分类精度在emotions数据集上提高约4.8%,在yeast数据集上提高约9.8%,在flags数据集上提高约7.3%。实验结果表明,当数据集中实例的标签基数较大时,相对于BR算法,MMLBM的准确性有较大的提升。

基于画面组单元时序控制算法的H.264实时流关键帧预处理

杜聃, 冯丽君, 刘胤田

2016, 36(1):  57-60.  DOI: 10.11772/j.issn.1001-9081.2016.01.0057

摘要 ( )   PDF (802KB) ( )  

参考文献 | 相关文章 | 计量指标

网络带宽特别是上行带宽受限情况下,基于H.264高压缩率的网络音视频通话或视频会议普遍会出现不同程度的丢包现象,从而造成流媒体播放的花屏等质量问题,影响视频通话或视频会议的效果。针对上述问题,提出了基于关键帧预处理的实时流媒体播放质量控制方法。该方法采用单元时序控制算法对视频关键坏帧进行实时侦测和取舍,进而减少花屏情况。使用该方法将降低后处理计算的时空成本,并提高流媒体播放的流畅性。通过原始帧播放、后处理播放、关键帧预处理播放3种处理方法的实验对比,证明基于播放单元时序控制算法的实时流媒体播放器,不但明显提高了播放的流畅性,播放后处理的计算复杂度也降低了40%以上。结果表明,该方法对提高播放质量、减少花屏情况有着突出的效果。

网络与通信

改进的基于网络编码中继转发方案

国强, 秦月

2016, 36(1):  61-65.  DOI: 10.11772/j.issn.1001-9081.2016.01.0061

摘要 ( )   PDF (715KB) ( )  

参考文献 | 相关文章 | 计量指标

针对双向中继网络中传统中继转发协议放大信号的同时放大了噪声、可能转发错误的解码信号、中继判决结果不可靠等问题,提出两种基于互信息转发(MIF)的网络编码中继转发方案。首先,中继节点转发来自两个源端信息的硬判决结果;同时还转发其可靠度;然后,接收端将来自中继节点转发的信号及其可靠度和源端信号合并,并对合并结果进行检测和判决。详细推导了所提出两种方案接收端信噪比(SNR)的表达式,并在加性高斯白噪声(AWGN)信道两种仿真条件下进行数值仿真;同时分别在AWGN信道和瑞利信道中对各种方案误码率进行蒙特卡罗仿真。结果表明在两种信道条件下所提出方案在误码率(BER)性能上较估计转发(EF)方案相比分别有约1 dB和1~2 dB的增益。仿真实验结果说明基于MIF的网络编码方案在双向中继网络中继转发中对系统的误码性能有显著提升效果。

基于非均匀分簇的无线传感器网络分层路由协议

黄廷辉, 伊凯, 崔更申, 王玉良

2016, 36(1):  66-71.  DOI: 10.11772/j.issn.1001-9081.2016.01.0066

摘要 ( )   PDF (900KB) ( )  

参考文献 | 相关文章 | 计量指标

针对大规模无线传感器网络(WSN)中由于簇首节点分布不合理而导致节点消耗能量过快的问题,设计了一种基于非均匀分簇的无线传感器网络分层路由协议(HRPNC)。HRPNC结合低功耗自适应集簇分层型协议(LEACH)中的分簇思想,并在分层的基础上对能量均衡的无线传感器网络非均匀分簇路由协议(DEBUC)中竞争半径的算法进行改进,即通过分层机制及竞争机制选取簇首,使簇首节点分布更加合理,有效均衡节点的能量消耗。在Matlab上进行的仿真实验中,HRPNC在生存周期上较LEACH协议与DEBUC协议分别提高了约500轮、300轮;HRPNC的节点平均剩余能量高于LEACH协议与DEBUC协议,节点能量的消耗在生存周期间基本保持较低且平稳的能量消耗;HRPNC较LEACH协议与DEBUC协议在数据包传输总量上分别提高了约300%、130%;在不同仿真环境下,HRPNC的丢包率均比LEACH协议和DEBUC协议低。实验结果表明,HRPNC不仅能有效延长网络的生存周期,提高数据的传输数量与网络的稳定性,并且能有效降低数据传输的丢包率。

基于SkipNet支持多属性范围查询的云资源共享设计

孙利华, 陈世平

2016, 36(1):  72-76.  DOI: 10.11772/j.issn.1001-9081.2016.01.0072

摘要 ( )   PDF (737KB) ( )  

参考文献 | 相关文章 | 计量指标

在云资源共享服务模式中,针对云资源多属性范围查询的问题,提出一种改进的E-SkipNet网络。首先,E-SkipNet在传统分布式哈希表(DHT)网络SkipNet的基础上将数据属性引入到节点NameID的设置中,将物理节点加入到单个属性域中,以支持多属性范围查询;其次,在原E-SkipNet网络的基础上,将物理节点同时映射成多个逻辑节点;同时加入多个属性域,并将资源按照不同的属性发布到不同逻辑节点上;最后,采用均匀位置保留哈希函数对资源进行映射存储,从而在各个属性域中保留属性值的顺序关系,从而支持范围查询。仿真结果表明,改进后的E-SkipNet网络与改进前的E-SkipNet和多属性可寻址网络(MAAN)相比,在路由效率方面分别提高了18.09%和20.47%。结果表明,改进后的E-SkipNet网络能支持更加高效的云资源多属性范围查询,在异构环境中能较好地实现负载均衡。

基于剩余能量动态调整前向角度的路由算法

张茂兴, 王海峰, 向凤红, 毛剑琳, 张传龙

2016, 36(1):  77-80.  DOI: 10.11772/j.issn.1001-9081.2016.01.0077

摘要 ( )   PDF (782KB) ( )  

参考文献 | 相关文章 | 计量指标

无线传感器网络(WSN)路由是影响网络寿命的重要因素。关键节点多次通信带来大量能耗,极易导致网络过早瘫痪。针对网络部分关键节点能耗过快问题,提出一种基于下一跳节点剩余能量动态调整前向角度的蚁群路由算法(DAFARE)。首先,节点于初始前向角度范围内根据节点剩余能量和距离来选择下一跳节点;而后,根据前向角度范围内节点剩余能量情况,动态调整前向角度大小;最终达到避免关键节点过早死亡的目的。仿真表明,与基于多目标评价函数与正-负反馈并存机制的蚁群算法(FMEPNF)相比,DAFARE能将网络有效寿命提高约50%。实验结果表明:该算法能有效均衡网络能耗,延长网络生命周期,保证网络有效覆盖范围。

基于非均匀分簇机制的ZigBee混合路由算法

白乐强, 王玉涛

2016, 36(1):  81-86.  DOI: 10.11772/j.issn.1001-9081.2016.01.0081

摘要 ( )   PDF (903KB) ( )  

参考文献 | 相关文章 | 计量指标

针对现有ZigBee网络路由算法存在节点能量消耗不均衡问题,在树路由算法与无线自组网按需距离矢量路由改进(AODVjr)算法的基础上,提出一种基于非均匀分簇机制的ZigBee混合路由算法。该算法将网络分成若干个非均匀的逻辑簇,使距离协调器越近的簇规模越小,从而减少转发任务,使得能量消耗均衡。在分簇的基础上,将节点之间的传输分为簇内传输与簇间传输。簇内传输采用基于邻居表的树路由算法;簇间传输在基于树路由算法无效的情况下,采用AODVjr算法,找到两个簇首之间的较短路径;同时规定只有簇首节点和网关节点才能广播请求分组(RREQ),可以减少冗余的RREQ分组。仿真结果表明,该算法能有效推迟死亡节点出现的时间,延长网络的生存周期,达到提高网络性能的目的。

基于Gerschgorin理论稀疏度估计的宽带频谱感知算法

赵知劲, 陈京来

2016, 36(1):  87-90.  DOI: 10.11772/j.issn.1001-9081.2016.01.0087

摘要 ( )   PDF (706KB) ( )  

参考文献 | 相关文章 | 计量指标

针对在低信噪比(SNR)情况下稀疏度欠估计和高信噪比情况下稀疏度过估计的问题,提出了一种基于Gerschgorin理论稀疏度估计的宽带频谱感知算法。首先,该算法利用Gerschgorin理论分离信号圆盘与噪声圆盘得到稀疏度估计值;然后,利用正交匹配追踪(OMP)算法得到频谱支撑集;最后,完成宽带频谱感知。仿真结果表明,所提算法、AIC-OMP算法和MDL-OMP算法频谱感知的检测概率达到95%信噪比分别需要4.6 dB、8.5 dB和9.7 dB;所提算法频谱感知的虚警概率在信噪比大于13 dB时趋近于0,明显低于BPD-OMP和GDRI-OMP算法的虚警概率,因此,所提算法对于压缩感知(CS)的信号稀疏度估计兼顾了低信噪比和高信噪比时的稀疏度估计性能,频谱感知性能优于AIC-OMP算法、MDL-OMP算法、BPD-OMP算法和GDRI-OMP算法。

卫星信道三状态Markov模型设计与仿真

郭业才, 赵卫娟, 张秀再

2016, 36(1):  91-95.  DOI: 10.11772/j.issn.1001-9081.2016.01.0091

摘要 ( )   PDF (718KB) ( )  

参考文献 | 相关文章 | 计量指标

为研究大气空间环境对卫星通信的影响,将卫星通信的天气状况分为晴朗天气、云雾天气、雨雪天气3种情况,分析不同天气状况下的卫星信道传播特性并建立相应的Rice分布模型、C.Loo分布模型和Suzuki分布模型,引入三状态Markov过程实现因天气变化造成的信道状态的转换,构成卫星信道三状态Markov模型并对该模型的统计特性进行分析。最后,采用正弦波叠加法并利用实测气象卫星云图数据对该卫星信道三状态Markov模型进行仿真实验。仿真结果表明,所建模型可以用来模拟实际的卫星信道传播特性。

面向中间件的组态王远程数据采集驱动设计

刘学多, 焦东来, 吉峰, 杨浩

2016, 36(1):  96-100.  DOI: 10.11772/j.issn.1001-9081.2016.01.0096

摘要 ( )   PDF (925KB) ( )  

参考文献 | 相关文章 | 计量指标

为解决组态网络中存在的下位机兼容性差、数据共享难及客户端展示方式单一性的问题,提出了一种面向中间件的组态王数据采集模型。该模型依据组态软件具有强大的网络连接功能和二次可开发的特点,以通用组态王软件为例,通过深入分析组态软件原理,结合通信中间件与通信协议,定义组态王的设备信息、变量信息,绘制组态王的展示界面对当前组态网络存在的问题进行验证。验证结果表明,该模型相比较于传统的组态网络模型提高了组态网络数据采集模型的可扩展性及兼容性,可以应用于数据共享与客户端的多样展示,有助于组态类软件与物联网技术的融合。

基于非空时隙数的无线射频识别标签估算算法

龙昭华, 宫腾飞

2016, 36(1):  101-106.  DOI: 10.11772/j.issn.1001-9081.2016.01.0101

摘要 ( )   PDF (874KB) ( )  

参考文献 | 相关文章 | 计量指标

针对无线射频识别(RFID)系统中现有标签估计算法估计时间长、误差大的问题,提出了一种基于非空时隙数的标签估算方法。首先,分析了动态帧时隙ALOHA(DFSA)算法的系统模型,指出标签估算的必要性;其次,对当前存在的一些标签估计算法进行了研究,列举其存在的不足;再次,通过在不同帧长条件下对非空时隙平均数与待识别标签数的关系进行研究,得出两者之间存在着的不依赖于帧长的归一化曲线并将其运用于标签估计。而且通过引入精度需求,运用概率分析理论和折半查找的方法来确定不同标签总数下的轮询次数K;最后,对所提标签估计算法进行仿真,从估算精度和估算时间两个方面与现有的标签估算算法作了性能对比分析。仿真结果表明,该算法最大估计误差仅为1%,在帧长为128、标签数为400的情况下,相比Adaptive Slotted ALOHA Protocol(ASAP)、Fast Zero Estimation(FZE)、最大后验概率(MAP)估计算法,其误差率分别减少了66.7%、78.3%和72.2%;此外在识别相同数目标签的情况下,所提算法耗费的估计时间也明显少于上述3种算法。由此可见,基于非空时隙数的标签估算算法具有较高的估算精度和估算效率,能够对RFID系统中的待识别标签进行快速准确的识别。

先进计算

基于离散人工蜂群算法的云任务调度优化

倪志伟, 李蓉蓉, 方清华, 庞闪闪

2016, 36(1):  107-112.  DOI: 10.11772/j.issn.1001-9081.2016.01.0107

摘要 ( )   PDF (1066KB) ( )  

参考文献 | 相关文章 | 计量指标

针对现今云计算任务调度只考虑单目标和云计算应用对虚拟资源的服务的质量要求高等问题,综合考虑了用户最短等待时间、资源负载均衡和经济原则,提出一种离散人工蜂群(ABC)算法的云任务调度优化策略。首先,从理论上建立了云任务调度的多目标数学模型;然后,结合偏好满意度策略并引入局部搜索算子和改变侦察蜂搜索方式,提出多目标离散型人工蜂群(MDABC)算法的优化策略。通过不同的云任务调度仿真实验,显示了改进离散人工蜂群算法相对于基础离散人工蜂群算法、遗传算法以及经典贪心算法,能够得到较高的综合满意度,表明了改进离散人工蜂群算法能够更好地改善虚拟资源中云任务调度系统的性能,具有一定的普适性。

多实例云计算资源市场下超额预订决策方法

陈冬林, 姚梦迪, 邓国华

2016, 36(1):  113-116.  DOI: 10.11772/j.issn.1001-9081.2016.01.0113

摘要 ( )   PDF (626KB) ( )  

参考文献 | 相关文章 | 计量指标

针对现有云供应商数据中心负载率低、云用户需求不确定及多样性的问题,为提高云供应商平均利润,建立了不确定需求下的多实例类型云服务超额预订模型。该模型结合实际云计算资源市场下超额预订对于云供应商负载均衡及云服务等级协议(SLA)的影响,给出超额预订的多重约束条件,提出了各实例类型数量最优分配策略。实验结果表明,采用该模型在预约未使用概率为0.25时,云供应商利润较高,数据中心负载率达到78%,最终确定了各实例类型的最优分配数量。

基于粒子群优化算法的虚拟机部署策略

杨靖, 张宏军, 赵水宁, 占栋辉

2016, 36(1):  117-121.  DOI: 10.11772/j.issn.1001-9081.2016.01.0117

摘要 ( )   PDF (751KB) ( )  

参考文献 | 相关文章 | 计量指标

针对云计算基础设施即服务(IaaS)中的虚拟机部署问题,提出一种基于粒子群优化(PSO)算法的部署策略。由于PSO算法在处理虚拟机部署这类大规模复杂问题时,具有收敛速度慢且容易陷入局部最优的缺点,首先,引入多种群进化模式提高算法收敛速度,并在此基础上加入高斯学习策略避免局部最优,提出了一种多种群高斯学习粒子群优化(MGL-PSO)算法;然后,根据部署模型,使用轮询(RR)算法对MGL-PSO进行初始化,进而提出了一种以负载均衡为目标的虚拟机部署策略。通过在CloudSim中进行仿真实验,验证了在解决虚拟机部署问题时,MGL-PSO相比PSO算法,具有更快的收敛速度,并且负载不均衡度降低了13.1%。在两种实验场景下,所提算法相比随机负载均衡(OLB)算法,其负载不均衡度分别平均降低了25%和15%;相比贪婪算法(GA),使负载不均衡度分别平均降低了19%和7%。

基于运动状态改变的在线全球定位系统轨迹数据压缩

刘磊军, 房晨, 张磊, 鲍苏宁

2016, 36(1):  122-127.  DOI: 10.11772/j.issn.1001-9081.2016.01.0122

摘要 ( )   PDF (999KB) ( )  

参考文献 | 相关文章 | 计量指标

针对基于偏移量计算的轨迹数据压缩算法中对于关键点的评估不足以及基于在线轨迹数据压缩算法中累积误差和对偏移量考虑不足的问题,提出一种基于运动状态改变的在线全球定位系统(GPS)轨迹数据压缩算法——限定同步欧氏距离(SED)的阈值结合算法(SLTA)。该算法通过轨迹点的转向角度大小和速度变化大小来评估轨迹点信息量的大小;同时用SED限制点的偏移量,以达到较好的信息保留度。实验结果表明,SLTA的轨迹压缩率能够达到50%左右,与阈值结合算法(TA)相比,SLTA的平均SED误差(5 m以内)可以忽略不计;相对于基于偏移量计算的轨迹数据压缩算法,SLTA的平均角度误差最小(1.5°~2.3°),运行时间最稳定。SLTA能够稳定有效地进行在线GPS轨迹数据压缩。

基于改进粒子群算法的行李条码阅读器布局优化

高庆吉, 李永胜, 罗其俊

2016, 36(1):  128-132.  DOI: 10.11772/j.issn.1001-9081.2016.01.0128

摘要 ( )   PDF (699KB) ( )  

参考文献 | 相关文章 | 计量指标

针对航空旅客托运行李时,检测行李条码的阅读器数量、位置、姿态存在很多不确定性问题,提出了动态种群-双适应值粒子群优化(DPDF-PSO)算法。首先,建立行李条码检测数学模型;然后,转化为约束优化问题;其次,通过标准粒子群优化(PSO)算法求解此优化问题;最后,依照模型特点对标准粒子群算法进行改进。仿真结果表明,与标准PSO算法相比,DPDF-PSO算法仿真时间降低了23.6%,目标函数值提高了3.7%。DPDF-PSO算法克服了标准粒子群优化算法中仿真时间慢、边界最优解难处理的缺点,阅读器布局方案能以较低的成本准确快速读取行李身份信息。

基于MapReduce的支持向量机态势评估算法

陈珍, 夏靖波, 杨娟, 韦泽鲲

2016, 36(1):  133-137.  DOI: 10.11772/j.issn.1001-9081.2016.01.0133

摘要 ( )   PDF (732KB) ( )  

参考文献 | 相关文章 | 计量指标

支持向量机(SVM)可以解决传统态势评估算法无法兼顾的“维数灾难”“过学习”及“非线性”等难题,却无法应对大规模样本的问题。为了有效应对态势评估中的大数据处理挑战,提出了一种基于MapReduce的SVM(MR-SVM)态势评估算法。该算法利用MapReduce并行计算模型,同时结合SVM可并行化的特点,通过设计主要的map函数和reduce函数,实现了SVM算法的并行化和主要参数的选取。在搭建的Hadoop平台上对改进算法与原算法进行了比较验证:对于小规模样本,改进算法反而"化简为繁",不比原算法效率高;但在大规模样本的处理上,原算法的训练时间随样本规模呈指数型增长,而改进算法的训练时间随样本规模并没有特别明显的增幅,体现出了较好的时间优势。实验结果表明,基于MapReduce改进的SVM很好地弥补了原算法"样本规模"的短板,更适用于大数据环境下的网络态势评估。

人工智能

求解旅行商问题的改进局部搜索混沌离散粒子群优化算法

程毕芸, 鲁海燕, 徐向平, 沈莞蔷

2016, 36(1):  138-142.  DOI: 10.11772/j.issn.1001-9081.2016.01.0138

摘要 ( )   PDF (909KB) ( )  

参考文献 | 相关文章 | 计量指标

针对基本离散粒子群优化(DPSO)算法收敛速度慢、易于陷入局部最优等问题,提出了一种基于优秀系数的局部搜索混沌离散粒子群优化(ILCDPSO)算法并用于求解旅行商问题(TSP)。基于轮盘赌选择原理,给每段路径设定一个合理的优秀系数,以提高短边被选择的概率,从而有利于提高算法的寻优能力和收敛速度;为了进一步提高解的精确性,在算法机制中添加了局部搜索策略,通过调整每个城市在给定邻域内的城市路径,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列来提高粒子的随机性和多样性,增强了算法的全局搜索能力。最后用国际通用的TSP数据库(TSPLIB)中的若干经典实例对算法进行了测试,并与粒子群优化(PSO)算法、改进的PSO(IPSO)算法和混沌PSO(CPSO)算法等进行了比较。实验数据显示,在相同的实验条件下,与其他算法相比,ILCDPSO算法获得最优解的平均迭代次数较少且获得最优解的次数比例最高。研究结果表明,加入优秀系数后,ILCDPSO算法在收敛速度、全局寻优能力以及稳定性方面均优于其他算法。

基于单形正交实验设计的差分演化算法

李康顺, 左磊, 李伟

2016, 36(1):  143-149.  DOI: 10.11772/j.issn.1001-9081.2016.01.0143

摘要 ( )   PDF (1013KB) ( )  

参考文献 | 相关文章 | 计量指标

为了克服传统差分演化(DE)算法在求解约束优化问题时出现的收敛性慢和容易陷入早熟等缺陷,提出一种新的基于单形正交实验设计的差分演化(SO-DE)算法。该算法设计了一种结合单形交叉和正交实验设计的混合交叉算子来提高差分演化算法的搜索能力;同时采用了一种改进的个体优劣比较准则对种群个体进行比较和选择。这种新的混合交叉算子利用多个父代个体进行单形交叉产生多个子代个体,从两者中选择优秀个体进行正交实验设计得到下一代种群个体。改进的个体优劣比较准则对不同状态下的种群采用不同的处理方案,其目的在于能够有效地权衡目标函数值和约束违反量之间的关系,从而选择优秀个体进入下一代种群。通过对13个标准测试函数和2个工程设计问题进行仿真实验,实验结果表明SO-DE算法求解的精度和标准方差都要优于HEAA算法和COEA/OED算法。SO-DE算法具有更高的精度以及更好的稳定性。

基于中点密度函数的模糊聚类算法

周跃跃, 胡婕, 苏涛

2016, 36(1):  150-153.  DOI: 10.11772/j.issn.1001-9081.2016.01.0150

摘要 ( )   PDF (755KB) ( )  

参考文献 | 相关文章 | 计量指标

针对传统模糊C-均值(FCM)聚类算法初始聚类中心不确定,且需要人为预先设定聚类类别数,从而导致结果不准确的问题,提出了一种基于中点密度函数的模糊聚类算法。首先,结合逐步回归思想作为初始聚类中心选取的方法,避免收敛结果陷入局部循环;其次,确定可能的聚类类别数目;最后,对结果进行重叠度和分离度的模糊聚类有效性指标判定,确定最佳的聚类类别数。实验证明该算法与原改进C-均值聚类算法相比,减少了迭代次数,平均准确率提高了12%。实验结果表明该算法能够减少聚类的处理时间,并在平均准确率和聚类性能指标上优于对比算法。

基于递归自编码器的广告短语相关性

胡庆辉, 魏士伟, 解忠乾, 任亚峰

2016, 36(1):  154-157.  DOI: 10.11772/j.issn.1001-9081.2016.01.0154

摘要 ( )   PDF (737KB) ( )  

参考文献 | 相关文章 | 计量指标

针对现有广告短语相关性研究成果多采用字面匹配,忽略了短语所包含的深层语义信息,限制了任务的性能等问题,提出了采用深度学习算法研究广告短语的相关性,采用递归自编码器(RAE)对短语进行深层结构分析,使得短语向量包含深层的语义信息,以此来构建广告语境下的短语相关性计算方法。具体地,给定一个包含若干词的序列,序列中所有相邻的两个元素尝试合并产生一个重构误差,遍历将重构误差最小的元素两两合并,形成类似哈夫曼树结构的短语树。采用梯度下降法最小化短语树的重构误差,采用余弦距离度量短语之间的相关性。实验结果显示,通过引入词语权重信息,加大了重要词语在最终短语向量表示中贡献的信息量,使得RAE更适合短语计算;比起传统LDA和BM25算法,在50%召回率的条件下,提出的算法的准确率分别提高了4.59个百分点和3.21个百分点,这证明了所提算法的有效性。

基于改进堆叠自动编码机的垃圾邮件分类

沈承恩, 何军, 邓扬

2016, 36(1):  158-162.  DOI: 10.11772/j.issn.1001-9081.2016.01.0158

摘要 ( )   PDF (882KB) ( )  

参考文献 | 相关文章 | 计量指标

针对堆叠自动编码机(SA)容易产生过拟合而降低垃圾邮件分类精度的问题,提出了一种基于动态dropout的改进堆叠自动编码机方法。首先分析了垃圾邮件分类问题的特殊性,将dropout算法引入到堆叠自动编码机算法中;同时,根据传统dropout算法容易使部分节点长期处于熄火状态的缺陷,提出了一种动态dropout改进算法,使用动态函数将传统静态熄火率修改为随着迭代次数逐渐减小的动态熄火率;最后,利用动态dropout算法改进堆叠自动编码机的预训练模型。仿真结果表明,相比支持向量机(SVM)和反向传播(BP)神经网络,改进的堆叠自动编码机平均准确率达到了97.66%,各个数据集上马修斯系数都大于89%;与传统堆叠自动编码机相比,改进的堆叠自动编码机的马修斯系数在Error1~6数据集上分别提高了3.27%、1.68%、2.16%、1.51%、1.58%、1.07%。实验结果表明,基于动态dropout算法的改进堆叠自动编码机具有更高的分类精度和更好的稳定性。

健康领域Web信息抽取

李汝君, 张俊, 张晓民, 桂小庆

2016, 36(1):  163-170.  DOI: 10.11772/j.issn.1001-9081.2016.01.0163

摘要 ( )   PDF (1223KB) ( )  

参考文献 | 相关文章 | 计量指标

针对Web信息抽取(WIE)技术在健康领域应用的问题,提出了一种基于WebHarvest的健康领域Web信息抽取方法。通过对不同健康网站的结构分析设计健康实体的抽取规则,实现了基于WebHarvest的自动抽取健康实体及其属性的算法;再把抽取的实体及其属性进行一致性检查后存入关系数据库中,然后对关系数据库中隐含健康实体的属性值利用Ansj自然语言处理方法进行实体识别, 进而抽取健康实体之间的联系。该技术在健康实体抽取实验中,平均F值达到99.9%,在实体联系抽取实验中,平均F值达到80.51%。实验结果表明提出的Web信息抽取技术在健康领域抽取的健康信息具有较高的质量和可信性。

基于位置的非对称相似性度量的协同过滤推荐算法

王付强, 彭甫镕, 丁小焕, 陆建峰

2016, 36(1):  171-174.  DOI: 10.11772/j.issn.1001-9081.2016.01.0171

摘要 ( )   PDF (702KB) ( )  

参考文献 | 相关文章 | 计量指标

为提升推荐系统的准确率,针对传统协同过滤(CF)推荐算法没有有效使用位置信息的问题,提出了一种基于位置的非对称相似性度量的协同过滤推荐算法(LBASCF)。首先,分别利用用户-商品评分矩阵和用户历史消费位置,计算出用户间的余弦相似性和基于位置的非对称相似性;其次,将余弦相似性与基于位置的相似性融合,得到一个新的非对称用户相似性,融合后的相似性能够同时反映用户在位置上和兴趣上的偏好;最后,根据用户的最近邻居对商品的评分向用户推荐新的商品。用某点评数据集和Foursquare数据集对算法的有效性进行了评估。在某点评数据集实验结果证明,与CF相比,LBASCF的召回率和精确率分别提高了1.64%和0.37%;与位置感知协同过滤推荐系统(LARS)方法比较,LBASCF的召回率和精确率分别提高了1.53%和0.35%。实验结果表明,LBASCF相对于CF和LARS在基于位置服务的应用中能够有效提高系统的推荐质量。

面向产品属性的用户情感模型

贾闻俊, 张晖, 杨春明, 赵旭剑, 李波

2016, 36(1):  175-180.  DOI: 10.11772/j.issn.1001-9081.2016.01.0175

摘要 ( )   PDF (903KB) ( )  

参考文献 | 相关文章 | 计量指标

传统情感模型在分析商品评论中的用户情感时面临两个主要问题:1)缺乏针对产品属性的细粒度情感分析;2)自动提取的产品属性其数量须提前确定。针对上述问题,提出了一种细粒度的面向产品属性的用户情感模型(USM)。首先,利用分层狄利克雷过程(HDP)将名词实体聚类形成产品属性并自动获取其数量;然后,结合产品属性中名词实体的权重和评价短语以及情感词典作为先验,利用潜在狄利克雷分布(LDA)对产品属性进行情感分类。实验结果表明,该模型具有较高的情感分类准确率,情感分类平均准确率达87%。该模型与传统的情感模型相比在抽取产品属性和评价短语的情感分类上具有较高的准确率。

基于稠密光流轨迹和稀疏编码算法的行为识别方法

赵晓健, 曾晓勤

2016, 36(1):  181-187.  DOI: 10.11772/j.issn.1001-9081.2016.01.0181

摘要 ( )   PDF (1315KB) ( )  

参考文献 | 相关文章 | 计量指标

针对现有行为特征提取方法识别率低的问题,提出了一种融合稠密光流轨迹和稀疏编码框架的无监督行为特征提取方法(DOF-SC)。首先,在稠密光流(DOF)轨迹提取的基础上,对以轨迹为中心的原始图像块进行采样作为轨迹的原始特征;其次,对轨迹原始特征基于稀疏编码框架训练稀疏字典,得到轨迹的稀疏特征表示,利用词袋(BF)模型对稀疏特征聚类得到轨迹的码书,再根据码书对每个动作中出现的所有轨迹所属的码书类别进行投票,统计该动作中每个码书出现的次数,得到行为特征;最后,对行为特征利用基于直方图交叉核函数的支持向量机(SVM)进行训练得到行为识别模型,再利用该模型对行为进行分类预测,得到最终行为识别的结果。在对轨迹采样10%的情况下,DOF-SC算法得到的行为识别准确率在KTH数据库上高出采用运动边界直方图(MBH)作为特征的行为识别准确率的0.9%,在YouTube数据库上高出MBH作为特征的行为识别准确率的1.2%。实验数据表明了所提方法对行为识别的有效性。

基于自适应改进粒子群优化的数据离散化算法

董跃华, 刘力

2016, 36(1):  188-193.  DOI: 10.11772/j.issn.1001-9081.2016.01.0188

摘要 ( )   PDF (915KB) ( )  

参考文献 | 相关文章 | 计量指标

针对经典粗糙集只能处理离散型属性的问题,提出一种基于自适应混合粒子群优化(AHPSO)的离散化算法。首先,引入自适应调整策略,以克服粒子群易陷入局部解的缺点,提高了粒子群全局寻优能力;然后对每一代全局最优粒子进行禁忌搜索(TS),得到当代最佳全局最优粒子,增强了粒子群局部搜索能力;最后,在保持决策表分类能力不变的情况下,将属性离散化分割点初始化为粒子群体,通过粒子间的相互作用得到最佳的离散化分割点。使用WEKA平台上的J48决策树分类方法,与基于属性重要度、信息熵的离散化算法相比,该算法的分类精度提升了10%~20%;与基于小生境离散粒子群优化(NDPSO)、参数线性递减粒子群的离散化算法相比,该算法的分类精度提升了2%~5%。实验结果表明,该算法显著地提高了J48决策树的分类学习精度,在对数据离散化时也有较好的性能。

网络空间安全

基于攻击模式识别的网络安全态势评估方法

王坤, 邱辉, 杨豪璞

2016, 36(1):  194-198.  DOI: 10.11772/j.issn.1001-9081.2016.01.0194

摘要 ( )   PDF (945KB) ( )  

参考文献 | 相关文章 | 计量指标

通过对已有网络安全态势评估方法的分析与比较,发现其无法准确反映网络攻击行为逐渐呈现出的大规模、协同、多阶段等特点,因此提出了一种基于攻击模式识别的网络安全态势评估方法。首先,对网络中的报警数据进行因果分析,识别出攻击意图与当前的攻击阶段;然后,以攻击阶段为要素进行态势评估;最后,构建攻击阶段状态转移图(STG),结合主机的漏洞与配置信息,实现对网络安全态势的预测。通过网络实例对所提出的网络安全态势评估模型验证表明,随着攻击阶段的不断深入,其网络安全态势值也随之增大,能够更加准确地反映攻击实情;且在态势预测中无需对历史序列进行训练,具有更高的预测效率。

基于和声搜索算法和相关向量机的网络安全态势预测方法

李洁, 张兆薇

2016, 36(1):  199-202.  DOI: 10.11772/j.issn.1001-9081.2016.01.0199

摘要 ( )   PDF (747KB) ( )  

参考文献 | 相关文章 | 计量指标

针对当前网络安全时变性、非线性、预测评估难的现状,提出一种基于和声搜索算法和相关向量机(HS-RVM)的网络安全态势预测方法,以弥补现有预测方法在预测精度方面的不足。在预测过程中,首先对网络安全态势样本集进行归一化处理和相空间重构;然后,通过利用和声搜索(HS)算法搜索相关向量机(RVM)最优的超参数,以得到预测精度和速度都得到提升的网络安全态势预测模型;最后,采用Wilcoxon符号秩检验验证模型预测性能之间的差异性。仿真实例表明,所提预测方法的平均绝对百分误差(MAPE)和均方根误差(RMSE)分别为0.49575和0.02096,预测性能优于改进和声搜索(IHS)算法优化的正则极速学习机(RELM)预测模型和PSO算法优化的支持向量机回归(PSO-SVR)模型,Wilcoxon符号秩检验结果显示预测性能之间具有显著的差异性。所提预测方法能够较为精确描述网络安全态势变化规律,有利于网络管理者及时掌握网络安全态势变化趋势。

基于攻击图的信息物理系统信息安全风险评估方法

武文博, 康锐, 李梓

2016, 36(1):  203-206.  DOI: 10.11772/j.issn.1001-9081.2016.01.0203

摘要 ( )   PDF (608KB) ( )  

参考文献 | 相关文章 | 计量指标

震网病毒等事件实证了信息攻击能对信息物理系统(CPS)带来严重的物理影响。针对这类跨域攻击问题,提出了基于攻击图的风险评估方法。首先,对信息物理系统中的信息攻击行为进行了分析,指出可编程逻辑控制器(PLC)等物理设备中存在的漏洞是信息攻击实现跨域攻击的关键,并给出了信息物理系统中漏洞的利用模式及影响后果;其次,建立风险评估模型,提出攻击成功概率和攻击后果度量指标。综合考虑漏洞固有特性和攻击者能力计算攻击成功概率,根据主机重要程度和漏洞利用模式计算攻击后果。该方法能够将信息域与物理域作为一个整体进行建模,综合考虑多个跨域攻击对系统风险的影响。数值案例表明,多个跨域攻击组合下的风险值是单一攻击下的5倍,计算得到的风险值更为准确。

基于边分割的社交网络敏感边保护技术

范国婷, 罗永龙, 孙丹丹, 王涛春, 郑孝遥

2016, 36(1):  207-211.  DOI: 10.11772/j.issn.1001-9081.2016.01.0207

摘要 ( )   PDF (949KB) ( )  

参考文献 | 相关文章 | 计量指标

用户间的敏感关系是社交网络中用户的重要隐私信息。为了解决社交网络中用户间敏感关系泄露问题,提出一种边分割算法。首先,将已删除敏感边的简单匿名社交网络的非敏感边分割成多条子边;然后,将原非敏感边携带的信息分配到子边上,使得每条子边只携带原非敏感边的部分信息,从而生成具有隐私能力的匿名社交网络。理论分析和仿真实验结果表明,相比cluster-edge和cluster-based with constraints算法,边分割算法在保证数据具有较高可用性的情况下能更大限度降低敏感关系泄露的概率,泄露概率分别降低了约30%和20%,因此所提算法能够有效解决社交网络中敏感关系泄露问题。

基于差分标志字节的无线通信安全策略

汤尚, 李永贵, 朱勇刚

2016, 36(1):  212-215.  DOI: 10.11772/j.issn.1001-9081.2016.01.0212

摘要 ( )   PDF (757KB) ( )  

参考文献 | 相关文章 | 计量指标

针对公共密钥密码系统识别模拟攻击的计算复杂度高,而功率时延模型(PDP)又受限于模型必须存在足够距离差的问题,提出一种基于差分标志字节(DFB)的无线通信安全策略,并给出了生成DFB的差分方程。该策略利用用户传输的数据信息,建立适当的差分标致字节的生成方程,使得当前传输的数据帧的标志字节由已传帧的相关参数决定,最后接收端通过阈值判决验证接收数据帧的差分标致字节,识别模拟攻击。通过理论分析,差分标致字节可以防止攻击者利用已掌握的部分通信参数信息,对用户实施反复的模拟攻击。在时间上,攻击者有效攻击时间更短,攻击达成周期更长。在空间上,攻击者空间位置被限制在有限椭圆内。最后,结合一种具体、简易的DFB进行了仿真分析,结果表明,此种简易模型下,通信系统的信噪比(SNR)高于-4 dB时,系统能够通过设置合适的阈值,能够实现针对模拟攻击的识别与防护。

具有访问权限撤销的外包数据加密方案

李程文, 王晓明

2016, 36(1):  216-221.  DOI: 10.11772/j.issn.1001-9081.2016.01.0216

摘要 ( )   PDF (958KB) ( )  

参考文献 | 相关文章 | 计量指标

对Zhou等提出的方案(ZHOU M, MU Y, SUSILO W, et al. Privacy enhanced data outsourcing in the cloud. Journal of network and computer applications, 2012, 35(4): 1367-1373)进行分析,指出了该方案无法实现对用户访问权限进行撤销的问题。针对该方案的不足,提出一种具有撤销用户访问权限的外包数据加密方案。首先,把数据分成多个数据块并分别对每个数据块加密;其次,通过密钥导出的方法减少数据拥有者管理和保存密钥的数量;最后,对同一个加密数据构造多个解密密钥,实现对某些用户的访问权限撤销,而未被撤销用户无需进行密钥更新。与Zhou等的方案相比,所提方案不仅保持该方案中的外包数据隐私保护优点,而且还实现了用户访问权限的撤销。分析结果表明,在离散对数困难问题(DLP)假设下,所提方案是安全的。

虚拟现实与数字媒体

基于主成分分析方向深度梯度直方图的立体视觉深度图特征提取

段峰峰, 王永滨, 杨丽芳, 潘淑静

2016, 36(1):  222-226.  DOI: 10.11772/j.issn.1001-9081.2016.01.0222

摘要 ( )   PDF (794KB) ( )  

参考文献 | 相关文章 | 计量指标

针对立体视觉深度图特征提取精确度低、复杂度高的问题,提出了一种基于主成分分析方向深度梯度直方图(PCA-HODG)的特征提取算法。首先,对双目立体视觉图像进行视差计算和深度图提取,获取高质量深度图;然后,基于预设大小窗口对所获取的深度图进行边缘检测和梯度计算,获得区域形状直方图特征并量化;同时运用主成分分析(PCA)进行降维;最后,为实现特征获取的精确性和完整性,采用滑动窗口检测方法实现整幅深度图的特征提取,并再次降维。在特征匹配分类实验中,对于Street测试序列帧,该算法比距离样本深度特征(RSDF)算法平均分类准确率提高了1.15%,而对于Tanks、Tunnel、Temple测试序列帧,该算法比测度不变特征(GIF)算法平均分类准确率分别提高了0.69%、1.95%、0.49%;同时与方向深度直方图(HOD)、RSDF、GIF算法相比,平均运行时间分别降低了71.65%、78.05%、80.06%。实验结果表明,该算法不仅能够更精确地检测和提取深度图特征,而且通过降低维数复杂度大大减少了运行时间;同时算法具有较好的鲁棒性。

基于Riemann-Liouville改进的1~2阶分数阶边缘提取新模型

王程啸, 黄辉先, 杨辉, 徐建闽

2016, 36(1):  227-232.  DOI: 10.11772/j.issn.1001-9081.2016.01.0227

摘要 ( )   PDF (962KB) ( )  

参考文献 | 相关文章 | 计量指标

针对数字图像的处理中采用整数步长与0~1阶分数阶微分的掩模算子未能精确定位边缘信息、缺少图像的纹理细节的问题,在Laplacian算子的基础上提出了一种新的边缘检测掩模算子。该算法从Riemann-Liouville(R-L)定义出发,推出1~2阶分数阶微分在中频信号的增强效果优于0~1阶分数阶微分并显著提升了高频信号,最终得到精确的检测效果。仿真结果表明:提出的算子能更好地提取边缘信息,尤其对灰度变化不大的平滑区域中纹理细节丰富的图像,该算子检测到的信息优于现有0~1阶微分算子,针对主观识别有更高的准确率;客观上采用扫描法的定位误差统计,该算子的综合定位误差率为7.41%,低于整数阶微分算子(最低为10.36%)与0~1阶微分算子(最低为9.97%),有效提高了边缘定位精度。该算子尤其适用于具有较高频信息的图像边缘检测中。

结合全变差与自适应低秩正则化的图像压缩感知重构

刘金龙, 熊承义, 高志荣, 周城, 汪淑贤

2016, 36(1):  233-237.  DOI: 10.11772/j.issn.1001-9081.2016.01.0233

摘要 ( )   PDF (789KB) ( )  

参考文献 | 相关文章 | 计量指标

针对基于固定变换基的协同稀疏图像压缩感知(CS)重构算法不能充分利用图像自相似特性的问题,提出了一种改进的联合全变差与自适应低秩正则化的压缩感知重构方法。首先,通过图像块匹配法寻找结构相似块,并组成非局部相似块组;然后,以非局部相似块组加权低秩逼近替代协同稀疏表示中的三维小波变换域滤波;最后,结合梯度稀疏与非局部相似块组低秩先验构成重构模型的正则化项,并采用交替方向乘子法求解实现图像重构。实验结果表明,相比协同稀疏压缩感知重构(RCoS)算法,该方法重构图像的峰值信噪比平均可提升约2 dB,所提算法在准确描述图像非局部自相似结构特征的前提下显著提高了重构质量,更好地保留了图像的纹理细节信息。

快速线结构光中心提取算法

苏小勤, 熊显名

2016, 36(1):  238-242.  DOI: 10.11772/j.issn.1001-9081.2016.01.0238

摘要 ( )   PDF (718KB) ( )  

参考文献 | 相关文章 | 计量指标

在线结构光三维测量系统中,结构光中心提取的速度和精度直接影响到系统的整体性能。基于几何中心法、方向模板法和灰度重心法,提出了一种快速提取结构光中心的算法。首先,先对图像进行预处理,通过几何中心法快速提取结构光中心作为骨架;然后,提出了一种基于位置的法线判断法求取骨架法线方向,与常用的方向模板法比较,在速度上有了大幅度提升;最后,对骨架法线方向上像素进行灰度加权,从而精确提取结构光中心。实验结果表明,该算法不仅在速度上有很大提升,而且精度也达到了亚像素级别。

低剂量CT图像的自适应广义总变分降噪算法

何琳, 张权, 上官宏, 张芳, 张鹏程, 刘祎, 孙未雅, 桂志国

2016, 36(1):  243-247.  DOI: 10.11772/j.issn.1001-9081.2016.01.0243

摘要 ( )   PDF (796KB) ( )  

参考文献 | 相关文章 | 计量指标

针对低剂量计算机断层扫描(CT)重建图像时出现明显条形伪影的现象,提出一种自适应广义总变分(ATGV)降噪算法。该算法考虑了传统广义总变分(TGV)算法在降噪时模糊图像边缘信息的缺点,把可以有效区分图像平滑区和细节区的直觉模糊熵应用到传统TGV中,对图像的不同区域进行不同强度的去噪,从而达到保护图像细节的效果。该算法首先采用滤波反投影(FBP)算法得到低剂量CT重建图像;然后利用基于直觉模糊熵的边缘指示函数对传统TGV模型进行改进;最后用改进后的模型对重建图像进行降噪处理。采用Shepp-Logan模型和数字胸腔模型(thorax phantom)仿真低剂量CT重建图像来验证算法的有效性。实验结果表明,所提算法的归一化均方距离(NMSD)和归一化平均绝对距离(NAAD)均比总变分(TV)降噪算法和广义总变分(TGV)降噪算法小,且可分别获得26.90 dB和44.58 dB的峰值信噪比(PSNR)。该算法在去除条形伪影的同时可以较好地保持图像的边缘和细节信息。

基于同态系统滤波的高分辨率遥感图像河流信息提取

杨宜菩, 杨帆, 潘国峰, 张慧敏

2016, 36(1):  248-253.  DOI: 10.11772/j.issn.1001-9081.2016.01.0248

摘要 ( )   PDF (1143KB) ( )  

参考文献 | 相关文章 | 计量指标

为了解决在高分辨率遥感图像中易受同物异谱现象影响而导致河流信息提取不完整问题,依据河流区域在遥感图像中具有特定频率纹理信息这一特点,提出一种基于同态系统滤波的高分辨率遥感图像河流信息提取方法。该算法通过对遥感图像的频谱分析,确定河流信息在频域中的特征标识,采用一维剖面线加窗短时分析河流定位技术实现了全自动、快速全幅遥感图像河流定位和宽度估计,在同态系统下设计了低通滤波器实现对低频河流信息的提取。该算法采用"高分一号"遥感影像作为实验数据来源,相对于传统利用光谱信息的提取方法具有较高的提取精度,Kappa系数达0.85以上,并且实现全自动提取。实验结果表明所提算法能够快速、有效地提取复杂地貌区域内的河流信息。

行业与领域应用

领域本体驱动下企业联机分析处理系统应用研究

刘馨蕊, 任凤玉, 雷国平

2016, 36(1):  254-259.  DOI: 10.11772/j.issn.1001-9081.2016.01.0254

摘要 ( )   PDF (997KB) ( )  

参考文献 | 相关文章 | 计量指标

传统联机分析处理(OLAP)系统存在着形式化业务知识参与不足的状况,对深度推理分析造成了制约和局限。为了克服上述缺点,提出一种领域本体驱动的OLAP系统构建方法。首先,通过分析现有本体构建方法的局限性,依托实体类多特征加权相似度判断算法,提出先全局设计后局部抽取的半自动本体构建模式,实现矿山生产领域知识形式化;接着在此基础上,以矿山生产能力关键指标为度量,完成负载业务概念多维本体(MDO)建模;最后,在实际矿山决策系统项目建设中,进行了方法检验。实验结果表明,该方法充分发挥领域本体形式化表达与推理优势,有效整合多源异构信息和明晰多维分析过程,实现内隐知识与关联规则深度挖掘;同时借助高频通用概念视图定义,避免重复维度建模,改进了传统OLAP效能。

基于贝叶斯网络的克隆代码有害性预测

张丽萍, 张瑞霞, 王欢, 闫盛

2016, 36(1):  260-265.  DOI: 10.11772/j.issn.1001-9081.2016.01.0260

摘要 ( )   PDF (875KB) ( )  

参考文献 | 相关文章 | 计量指标

在软件开发过程中,程序员的复制、粘贴活动会产生大量的克隆代码,而那些发生不一致变化的克隆代码往往对程序是有害的。为了解决该问题,有效地发现程序中的有害克隆代码,提出一种基于贝叶斯网络的克隆有害性预测方法。首先,结合软件缺陷研究领域与克隆演化领域的相关研究成果,提出了两大类表征克隆代码信息的特征,分别是静态特征和演化特征;其次,通过贝叶斯网络核心算法来构建克隆有害性预测模型;最后,预测有害克隆代码发生的可能性。在5款C语言开源软件共99个版本上对克隆有害性预测模型的性能进行评估,实验结果表明该方法能够有效地实现对克隆代码有害性的预测,降低有害克隆代码对软件的威胁,提高软件质量。

基于群体智能的三维碎片全局最优匹配方法

孙家泽, 耿国华

2016, 36(1):  266-270.  DOI: 10.11772/j.issn.1001-9081.2016.01.0266

摘要 ( )   PDF (781KB) ( )  

参考文献 | 相关文章 | 计量指标

针对传统三维碎片整体匹配过程中误差积累的问题,提出了一种基于群体智能的全局最优匹配方法。该方法对破碎物体的三维多碎片全局匹配建立全局整体碎片匹配的数学模型,将碎片的整体最优匹配求解问题转换为求满足一定约束条件的最优匹配矩阵的组合优化问题,通过将自然社会认知优化算法进行离散化来求解该NP问题。典型实例分析验证了所提方法全局优化能力强,与初始位置无关,有较强的鲁棒性,为三维碎片整体匹配提供一个有效的方法。

城市轨道交通车站序列瓶颈系统优化分析

刘洁, 何胜学, 张皓东

2016, 36(1):  271-274.  DOI: 10.11772/j.issn.1001-9081.2016.01.0271

摘要 ( )   PDF (797KB) ( )  

参考文献 | 相关文章 | 计量指标

针对城市轨道交通车站进站设施瓶颈疏解缺乏系统的定量分析、成本模糊的问题,提出车站瓶颈定量分析模型,并在此基础上提出一种新优化策略。首先,建立乘客进站流程图,基于串联和并联混合的排队网络构建系统优化模型;其次,在现有优化策略基础上提出一种新的控制优化策略——变更设施序列,即交换安检设备和自动检票闸机的物理顺序;最后选取上海莘庄地铁站并根据两种优化策略给出具体优化方案,进行仿真实验。3种优化方案均有效减少了乘客排队时间,但总成本差异很大。到达率一定时,与无优化方案相比,优化方案1增加1台安检设备,减少了92.5%的等待时间,总成本增加了3.2%;优化方案2交换安检设备和闸机顺序,减少了80.3%的等待时间,总成本下降了50.4%;而优化方案3即方案1和2的叠加,几乎完全消除了乘客排队等待时间,但总成本却增加29.6%。结果分析表明,该模型能够很好地模拟瓶颈疏解成本,新策略在降低总成本上明显优于传统策略。

基于局部加权重构的化工过程数据恢复算法

郭金玉, 袁堂明, 李元

2016, 36(1):  282-286.  DOI: 10.11772/j.issn.1001-9081.2016.01.0282

摘要 ( )   PDF (800KB) ( )  

参考文献 | 相关文章 | 计量指标

针对化工过程数据中存在缺失数据的问题,在保持局部数据结构特征的基础上提出了基于局部加权重构的化工过程数据恢复算法。通过定位缺失的数据点并以符号NaN(Not a Number)标记,将缺失的数据集分为完备数据集和不完备数据集。不完备的数据集按照完整性的大小依次找到它们在完备数据集中相应的k个近邻,根据误差平方和最小的原则,求出k个近邻相应的权值,用k个近邻及相应的权值重构出缺失的数据点。将该算法应用在不同缺失率下的两种化工过程数据中并与望最大化主成分分析(EM-PCA)法和平均值(MA)两种传统的数据恢复算法相比较,该算法的恢复数据误差最小,并且计算速度相比EM-PCA算法平均提高了2倍。实验结果表明,局部加权重构的化工过程数据恢复算法可以有效地对数据进行恢复,提高了数据的利用率,适用于非线性化工过程缺失数据的恢复。

基于改进人工势场法的无人机路径规划算法

丁家如, 杜昌平, 赵耀, 尹登宇

2016, 36(1):  287-290.  DOI: 10.11772/j.issn.1001-9081.2016.01.0287

摘要 ( )   PDF (678KB) ( )  

参考文献 | 相关文章 | 计量指标

针对传统的人工势场(APF)法无法适应复杂环境而陷入局部停滞状态、路径不够平滑等不足,提出了改进的人工势场法。首先,该算法对威胁的连通性进行分析,借鉴几何拓扑学思想得到可行解域。其次,该算法在可行解域内进行航迹点预规划。预规划基于威胁分布的全局性信息,弥补人工势场法易陷入局部最小而无法找到可行路径的不足。最后,该算法改进人工势场法引力函数,通过多次迭代,并进行曲率检查以获得足够平滑的可飞路径。仿真结果表明改进算法能够满足无人机路径规划的要求,且简便可行,具有较强寻优能力及适应性。