2015年, 第41卷, 第2期 刊出日期：2015-02-15
-
全选|
-
-
计算机工程. 2015, 41(2): 1-6. https://doi.org/10.3969/j.issn.1000-3428.2015.02.001考虑到成本和灵活性等因素,利用公共云计算系统的资源构建临时私有云代替本地物理集群,已成为用户在特定时间段内处理大量并行作业的一种有效途径。然而现有作业调度算法不能感知并利用临时私有云的逻辑拓扑结构,容易降低紧耦合并行应用的性能。为解决该问题,提出一种逻辑拓扑感知的作业调度算法,根据私有云中虚拟机之间的带宽和延迟等信息构建逻辑拓扑关系,并综合考虑用户所提交作业的类型,进而产生对应的作业调度决策。实验结果表明,该算法在提高临时私有云中紧耦合并行应用性能方面优于开源云计算系统中常用的轮转算法和随机算法。
-
计算机工程. 2015, 41(2): 7-11,16. https://doi.org/10.3969/j.issn.1000-3428.2015.02.002为解决虚拟化条件下云平台故障排除不及时的问题,在开源云平台OpenStack 上设计并实现一种虚拟化 故障检测恢复系统。该系统由GUI 层、调度层、逻辑层和功能层组成,以事件驱动机制为核心,将系统中传递的信息作为事件按时序进行处理。以感知模块、策略模块、执行模块为主体,调用OpenStack API 和Libvirt API 实现与 虚拟机管理层的交互。建立以信息获取、分析处理、故障恢复为主要内容的故障检测恢复体系,通过对云平台运行 环境的实时检测,获取状态参数,根据策略对参数进行分析判断并制定应对措施,实现对故障的自动恢复。实验结 果证明,该系统可以在无代理情况下对云平台进行实时检测和故障自动恢复,增强云环境的安全性,提升云平台的高可用性。
-
计算机工程. 2015, 41(2): 12-16. https://doi.org/10.3969/j.issn.1000-3428.2015.02.003为解决云环境下的资源调度问题,提出一种能改善任务并行性与兼顾任务串行关系的调度模型,将用户提交的动态任务分割成具有制约关系的子任务,按运行次序放到具有不同优先级的调度队列中。针对同一调度队列中的子任务,采用基于最短任务延迟时间的改进蚁群算法(DSFACO)进行调度,在兼顾调度公平性与效率的前提下,最大化缩短任务延迟时间,从而提高用户满意度。实验结果表明,与任务调度增强蚁群算法相比,DSFACO 算法在任务延迟时间、调度公平性及效率方面性能更好,能实现云计算环境下任务的最优调度。
-
计算机工程. 2015, 41(2): 17-20,25. https://doi.org/10.3969/j.issn.1000-3428.2015.02.004为提高云计算资源的利用率,保持负载平衡,提出一种基于改进混沌萤火虫算法的云计算资源调度模型。从任务的完成时间、完成效率、完成安全性3 个方面建立云计算资源调度模型,在萤火虫算法中引入混沌算法,通过对个体进行扰动,加快收敛速度,降低局部最优的概率,并引入拉格朗日松弛函数改进云计算模型。基于Cloudsim 的仿真实验结果表明,该算法能有效避免资源分配的不均衡,缩短任务完成时间,提高系统的整体处理能力。
-
计算机工程. 2015, 41(2): 21-25. https://doi.org/10.3969/j.issn.1000-3428.2015.02.005安全管理平台(SMP)是实现安全管理工作常态化运行的技术支撑平台,在实际应用中需要实时处理来自安全设备所产生的海量日志信息。为解决现有SMP 中海量日志查询效率低下的问题,设计基于云计算的SMP 日志存储分析系统。基于Hive 的任务转化模式,利用Hadoop 架构的分布式文件系统和MapReduce 并行编程模型,实现海量SMP 日志的有效存储与查询。实验结果表明,与基于关系数据的多表关联查询方法相比,该系统使得 SMP 日志的平均查询效率提高约90% ,并能加快SMP 集中管控的整体响应速度。
-
计算机工程. 2015, 41(2): 26-30. https://doi.org/10.3969/j.issn.1000-3428.2015.02.006传统基于文本的类属关系自动抽取算法只简单记录关系出现的位置、频次等信息,而忽略了大量上下文信息,不能有效辨识典型类属关系。为此,提出一种面向互联网文本典型类属关系的识别方法。通过提取实体概念的语言学特征和上下文语义特征构成实体特征集,基于朴素贝叶斯分类器,计算任意实体属于不同概念的可能性,从而识别典型类属关系。实验结果证明,与基于频率的识别方法相比,该方法能将典型类属关系的识别准确率提高5% 以上。
-
计算机工程. 2015, 41(2): 31-35. https://doi.org/10.3969/j.issn.1000-3428.2015.02.007作战任务的分解与分配是指挥决策中的重要过程,随着战场环境复杂度的增加,确定环境下的任务分配方法已不能适应作战需求。针对不确定性任务分配问题,分析作战任务分解、分配和执行过程中的多种不确定性因素,给出相应的形式化描述。在此基础上,提出一种基于概率推理的适应度计算方法,具体分析各种不确定性任务成功执行概率的计算过程,并给出算例进行验证。仿真结果表明,该方法能有效解决任务分配问题,并对任务分配方案进行定量评价。
-
计算机工程. 2015, 41(2): 36-40,46. https://doi.org/10.3969/j.issn.1000-3428.2015.02.008针对Linux 任务调度算法在多核系统中交互性能差的问题,提出一种分组任务调度算法GFS。根据多核系统硬件特性,自动配置物理距离近的一组CPU 共享一个任务运行队列,通过平衡组内CPU 对任务运行队列的访问竞争与任务迁移的代价,实现组间任务运行队列的负载均衡,减少调度延迟。通过优先调度唤醒任务,加快多核系统中交互任务的响应速度。测试结果表明,在不同任务负载下,GFS 能够明显降低交互任务的平均响应时间,从而有效提高多核系统交互应用的调度性能。
-
计算机工程. 2015, 41(2): 41-46. https://doi.org/10.3969/j.issn.1000-3428.2015.02.009随着多处理器系统规模的不断扩大,如何节能成为一个亟待解决的重要问题。为此,基于多处理器系统提出一种针对随机任务的在线节能实时调度算法。使用统计方法,根据已有任务的到达时间和计算量估计新任务在空闲处理器上执行的电压/ 频率,使还未到达的任务能够满足截止期限并有效节能。在考虑单个处理器上执行的任务时,计算执行这些任务所需的平均电压/ 频率,使所有任务的执行速度尽量均衡,当某些任务不能满足截止期限要求时,则调高未执行任务的电压/ 频率。实验结果表明,与EDF,HVEA,MEG 和ME-MC 算法相比,该算法在满足截止期限和节能方面具有明显的优势。
-
计算机工程. 2015, 41(2): 47-51,56. https://doi.org/10.3969/j.issn.1000-3428.2015.02.010在一些特殊领域中需要建立一定的实验环境对软件性能进行测试,因此实验环境与实际环境之间的近似程度对软件的性能起到关键作用。为建立环境之间的近似度量,在进程代数理论基础上,根据软件与环境的交互程度,利用拓扑度量和论域理论中的偏序关系,建立实验环境之间近似程度的量化模型。根据软件与环境之间的部分交互,建立实验环境之间近似程度的度量模型。通过实例对度量模型进行说明,并证明度量模型的代数性质。
-
计算机工程. 2015, 41(2): 52-56. https://doi.org/10.3969/j.issn.1000-3428.2015.02.011现有保护位置隐私的邻近检测算法通常根据网格大小对用户位置进行量化计算,会降低算法结果的准确性。针对该问题,提出2 种准确安全的邻近检测算法。用户将自己的位置分成网格内坐标以及网格编号两部分,并将其分别加密后发送给服务器,服务器利用加密后的网格内坐标在整个地图中筛选出所有满足查询的网格,用户根据服务器的返回结果判断用户之间是否邻近。实验结果表明,算法1 速度快,传输信息少,算法2 更加安全, 但计算和通信开销较大,并且需查询与被查询用户同时在线。用户可根据对服务器的信任程度、查询性能和应用场景需求进行算法选择。
-
计算机工程. 2015, 41(2): 57-62,75. https://doi.org/10.3969/j.issn.1000-3428.2015.02.012故障注入技术是评价系统可靠性的有效方法。现有基于仿真的故障注入平台大多基于现场可编程门阵列 或超高速集成电路硬件描述语言实现,对故障模型的支持非常有限。为此,基于Simics 结构级模拟器,设计并实现 系统级硬件故障注入平台。该平台上层支持不同固件、操作系统以及应用程序,底层支持对处理器典型流水部件 的故障注入,同时实现瞬时故障、永久故障和间歇故障模型以及其他较全面的故障类型,并将一组系统级故障检测 机制集成入平台中。实验通过监测硬件故障在系统级的传播,对比分析了故障对不同部件造成的系统级影响,结果表明,瞬时故障对系统影响较小,永久故障容易引起系统失效,间歇故障对各部件有不同程度的干扰作用。
-
计算机工程. 2015, 41(2): 63-69,80. https://doi.org/10.3969/j.issn.1000-3428.2015.02.013传统混合执行测试方法无法对源代码不可见函数进行符号执行。针对该问题,将符号执行、分段式符号执行以及具体执行按需结合,提出一种分段式混合执行测试方法,将源代码不可见函数以分段式分析法截取为单独代码片段,结合动态执行和回归分析方法推导其相应的程序语义。为验证该方法的有效性,实现sCREST 原型系统,并对5 个应用广泛的开源系统进行测试。实验结果表明,该方法能够产生比传统方法覆盖更多分支数的测试数据。
-
计算机工程. 2015, 41(2): 70-75. https://doi.org/10.3969/j.issn.1000-3428.2015.02.014随着面向服务架构(SOA)的广泛应用,大量采用不同通信技术的遗留系统以服务的方式接入企业服务总线(ESB)。在实时性要求较高的领域,其信息系统一般采用数据分发服务(DDS)通信技术,将它们接入ESB 总线时,必须面对DDS 总线与ESB 总线间信息通信转换的问题。为此,设计一种通信转换适配器模型,该模型是一种三层体系结构,包括SOAP 消息收发层、消息与报文映射转换层及DDS 报文发布订阅层。根据消息与报文名称,遍历Mapping 映射文件,根据映射规则进行消息与报文的相互转换,再遍历消息或报文的信息模型定义文件,将转换后的结果解析成通信所用的标准格式,用于通信交互。构建一个ESB 与DDS 的混合通信系统用于测试该适配器模型性能,实验结果表明,其信息转换耗时低于100 ms,满足实时性要求。
-
计算机工程. 2015, 41(2): 76-80. https://doi.org/10.3969/j.issn.1000-3428.2015.02.015覆盖率是衡量无线传感器网络服务质量的重要指标。为提高网络覆盖率,针对水下三维传感器网络模型,提出一种基于定向移动的虚拟力算法。将虚拟力简化为节点只受邻居节点的斥力作用,定义当2 个邻居节点的感知圆球相切时,其位置为相对理想位置。节点所受虚拟力大小与节点移动到相对该邻居的理想位置所需移动的距离成正比,而节点移动的距离与节点所受到的虚拟力的合力相关。实验结果表明,该算法能有效地对水下传感器网络的布局进行优化,提高网络覆盖率。
-
计算机工程. 2015, 41(2): 81-84. https://doi.org/10.3969/j.issn.1000-3428.2015.02.016为提高接收信号强度指示(RSSI)指纹进行室内定位的准确性,提出一种利用RSSI 指纹抖动量的虚拟标签定位改进算法。给出RSSI 指纹抖动量计算方法,将其应用于待定位标签与参考标签的距离以及虚拟标签RSSI指纹的计算。在实际测试中,将RSSI 指纹抖动量用于虚拟标签定位算法射频指纹(RFFP)的改进。测试结果表明,与RFFP 算法和LANDMARC 算法相比,改进算法的平均定位精度分别提高约0. 35 m ~ 0. 88 m 和 0. 38 m ~0. 94 m,算法耗时仅分别增加约1% 和12% 。
-
计算机工程. 2015, 41(2): 85-90,95. https://doi.org/10.3969/j.issn.1000-3428.2015.02.017为实现无线传感器网络数据的低延时、高可靠性收集,将数据收集时涉及到的收集树构建、链路调度与功率分配联合问题定义为一个使数据收集延时最小化的优化问题。将该问题分成2 个子问题:低延时数据收集树的构建和针对数据收集树的链路调度与功率分配,并为每个子问题提供一种多项式启发算法。仿真结果表明,与现有数据收集策略相比,该算法的数据收集延时明显降低,且可靠性更高。
-
计算机工程. 2015, 41(2): 91-95. https://doi.org/10.3969/j.issn.1000-3428.2015.02.018为提高能量检测算法的性能,提出一种基于全相位快速傅里叶变换(FFT)的频谱感知算法。全相位FFT中的数据预处理过程,考虑了数据段中心样本点所有可能组合的情况,从而减少因信号截断所导致的频谱泄露,提高谱分析精确度。以能量检测法为例,通过Matlab 对基于传统FFT 和全相位FFT 的频谱感知算法进行理论分析和仿真,结果表明,在信噪比相同的条件下,后者的谱间干扰较小,信号的误检率较低;在相同虚警率的条件下,后者可使频谱泄露得到有效抑制,获得的频谱更接近于真实的频谱信息,检测概率相应提高。因此,全相位FFT 能量检测法的检测性能明显优于传统能量检测法。
-
计算机工程. 2015, 41(2): 96-99. https://doi.org/10.3969/j.issn.1000-3428.2015.02.019基于多元二次方(MQ)问题的多变量公钥密码体制是一种可以抵抗量子攻击的系统。分析基于多变量公钥密码体制的环签名方案,指出其存在密钥泄露和安全证明错误的问题。为解决上述问题,对环签名者和其他环 成员采用不同的密钥构造方式,提出一种可证明安全的环签名变体方案。该方案最大程度地去除原方案对IP 问 题的依赖,使得方案的安全性直接规约于MQ 问题,以提升安全性。在环签名的标准安全模型下,分别从正确性、 匿名性和不可伪造性等方面对方案进行分析和安全性证明,结果表明,与原方案相比,该方案有较高的安全性。
-
计算机工程. 2015, 41(2): 100-106. https://doi.org/10.3969/j.issn.1000-3428.2015.02.020针对现有信任评估模型中簇头选择标准单一、不同角色节点信任值难以分配与更新的问题,提出一种多角 色的信任评估模型。将节点分成簇头、簇成员、网关和代理4 种角色,引入节点信任值、移动性、相关度等多影响因子作为簇头、网关和代理的选择标准,采用新颖簇头节点的信任值计算方式。在簇内簇头节点的信任值由代理节点监督计算。在簇间利用由簇头、代理以及网关节点形成简化网络,根据社会网中人际关系的特点分配不同关系节点的可信度。NS2 仿真实验结果表明,该模型能有效检测出恶意节点并将其隔离,保证网络的安全性。
-
计算机工程. 2015, 41(2): 107-112. https://doi.org/10.3969/j.issn.1000-3428.2015.02.021在保证可靠性、匿名性和可审核性的同时,提高执行效率和降低通信成本是车载自组织网络(VANETs)的 研究热点。针对现有匿名认证方案计算量较大和通信成本较高的问题,提出一种通信有效的门限匿名认证方案。采用基于身份的签名算法提高执行效率,使原始信息可从签名中恢复,从而降低通信成本,利用门限转发机制实现 信息的可靠性,使用假名保证发送者的匿名性,通过追踪和撤销机制实现可审核性。分析结果表明,与已有的门限 匿名认证方案相比,该方案在保证安全性的同时,具有较低的通信成本和较高的执行效率。
-
计算机工程. 2015, 41(2): 113-116. https://doi.org/10.3969/j.issn.1000-3428.2015.02.022现有群签名方案存在不能抵抗陷害攻击和伪造攻击的问题。为此,将中国剩余定理用于群签名中,提出一 种新的群签名方案。利用中国剩余定理的数学特性,只需简单计算就能将一些重要的秘密信息进行整合,可以更 好地保证成员私钥和身份的隐密性,同时,能够较好地控制计算过程中数据的长度,从而简化计算过程,在不改变 其他合法群成员密钥的情况下,实现群成员的加入和撤销。分析结果表明,该方案具有匿名性、防伪造性、可跟踪 性、防联合攻击和防重放攻击等优点。
-
计算机工程. 2015, 41(2): 117-121,128. https://doi.org/10.3969/j.issn.1000-3428.2015.02.023针对社交网络的隐私保护问题,采用属性基加密算法,提出一种安全、高效、细粒度的社交网络访问控制方案,并建立社交网络体系结构。通过引入线性秘密共享方案构造访问控制策略,实现灵活的访问控制结构,利用重加密技术,将部分重加密工作转移给社交网络平台执行,在保证用户数据安全的前提下,降低用户的计算代价,通过分析非授权成员与授权成员之间的关系,判定非授权成员的访问权限,进而实现访问权限的传递,并分析方案的安全性和有效性。分析结果表明,与现有基于加密技术的隐私保护方案相比,该方案能提高访问结构的表达能力和解密效率。
-
计算机工程. 2015, 41(2): 122-128. https://doi.org/10.3969/j.issn.1000-3428.2015.02.024基于中国剩余定理提出一种无可信中心可验证门限签名秘密共享方案。该方案无需可信中心的参与,每个成员被视为分发者,通过相互交换秘密份额影子协同产生各自的秘密份额,从而避免可信中心的权威欺骗。成员利用自己的秘密份额产生部分签名,再由部分签名合成组签名,在签名过程中不直接利用或暴露组私钥,从而保证组私钥的可重用性。基于离散对数求解困难性,构造秘密份额影子验证式,从而识别成员之间的欺骗行为,有效防止成员之间的恶意欺诈。实验结果表明,与基于拉格朗日插值的秘密共享方案相比,该方案具有较高的计算效率。
-
计算机工程. 2015, 41(2): 129-134,140. https://doi.org/10.3969/j.issn.1000-3428.2015.02.025由于现有签密方案大多基于双线性对,配对运算计算量较大,且实现效率不高,不能满足对代理签密者的匿名要求,因此无需配对的签密方案是密码学的研究方向。而基于二次剩余的签名方案不仅具有描述简单,能够抵抗选择密文攻击的优点,且相较于基于配对的签名方案具有更高的实现效率。为此,将二次剩余的方法应用到签密方案中,并结合匿名性,提出一种基于二次剩余的匿名代理者签密方案。分析结果表明,该方案具有匿名性与公开验证性。
-
计算机工程. 2015, 41(2): 135-140. https://doi.org/10.3969/j.issn.1000-3428.2015.02.026DNA 编码优化问题是DNA 计算中的核心问题。分析DNA 编码优化的约束条件,在单链DNA 序列集合上引入h 距离,将聚类小生境技术应用于小种群遗传算法的构造,对DNA 编码优化问题进行求解。基于h 距离定义DNA 序列间的相似函数,将碱基字母编码为4 进制整数、DNA 编码序列作为个体编码为4 进制整数向量、种群编码为4 进制整数矩阵,基于模4 算术运算,构造相应的遗传算子,并给出DNA 编码序列的具体计算结果。实验 结果表明,与现有DNA 编码序列优化结果相比,该算法可得到更好的DNA 编码序列且计算效率较高。
-
计算机工程. 2015, 41(2): 141-144. https://doi.org/10.3969/j.issn.1000-3428.2015.02.027传统故障树分析算法存在诊断成本高和耗时长的问题,为此,在研究故障树结构中的特殊规律的基础上,采用深度优先最左遍历算法对故障树进行模块化分解,减小故障树分析的规模。结合if-then-else 运算符,将最左底层模块子树转化为相应的二元决策图结构。运用深度优先最左遍历算法得到该二元决策图结构中的割集和最小割集,用相同故障概率的基本事件替代最左底层模块子树得到新故障树。采用自底向上、从左至右的递归综合分析思想,获得系统元件故障发生的概率,实现对故障树的分析。对故障实例的分析诊断结果表明,该方法可有效提高诊断速度,减少诊断成本。
-
计算机工程. 2015, 41(2): 145-150. https://doi.org/10.3969/j.issn.1000-3428.2015.02.028对海量文本语料进行上下位语义关系自动抽取是自然语言处理的重要内容,利用简单模式匹配方法抽取 得到候选上下位关系后,对其进行验证过滤是难点问题。为此,分别通过对词汇语境相似度与布朗聚类相似度计 算,提出一种结合语境相似度和布朗聚类相似度特征对候选下位词集合进行聚类的上下位关系验证方法。通过对 少量已标注训练语料的语境相似度和布朗聚类相似度进行计算,得到验证模型和2 种相似度的结合权重系数。该 方法无需借助现有的词汇关系词典和知识库,可对上下位关系抽取结果进行有效过滤。在CCF NLP&2012 词汇语 义关系评测语料上进行实验,结果表明,与模式匹配和上下文比较等方法相比,该方法可使F 值指标得到明显提升。
-
计算机工程. 2015, 41(2): 151-156. https://doi.org/10.3969/j.issn.1000-3428.2015.02.029现有词语相似度计算方法未深入考虑义原之间的距离与义原深度的主次关系,或直接指定含具体词概念的相似度,导致计算结果不够精确。针对该问题,通过义原之间的距离限制义原深度对义原相似度的影响,分析统计《知网》中概念的义项表达式,使用第一基本义原(能反映具体词本质)替换概念义项表达式中出现的具体词,从而提出一种改进的词语语义相似度计算算法。实验结果表明,该算法能有效提高词汇相似度计算的精确度。
-
计算机工程. 2015, 41(2): 157-160. https://doi.org/10.3969/j.issn.1000-3428.2015.02.030目前主流的评价搭配抽取方法以句法依存分析为基础,由于中文评价文本的不规范性,导致其句法分析结果不稳定,进而影响评价搭配的抽取效果。针对该问题,提出一种改进的基于核心句的评价搭配抽取方法。设计融合核心句和句法依存关系的评价搭配抽取方法,提高评价语句句法分析结果的稳定性,并且在处理复杂的评价语句时,加入对评价对象之间、情感词之间并列关系的分析。实验结果表明,该方法能提高召回率和准确率。
-
计算机工程. 2015, 41(2): 161-166. https://doi.org/10.3969/j.issn.1000-3428.2015.02.031神经元是神经系统的基本构建和计算单元,神经元几何形态的计算模型对理解大脑的结构功能关系及信息处理极其重要。在总结和分析各种三维神经元几何形态生成算法的基础上,给出三维神经元几何形态生成算法的计算框架。根据神经元几何形态生成机制的不同,将生成算法分为基于统计分析的重建算法、基于文法规则的生成算法和基于生物发育的生长算法3 类,并重点比较和分析现有生成算法的优缺点。
-
计算机工程. 2015, 41(2): 167-172. https://doi.org/10.3969/j.issn.1000-3428.2015.02.032数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop 索引构建方法进行优化,设计maxISCover 启发式方法,给出根据人工节点添加算法建立pp-2-hop 索引的unifyIS 和unifyLS 算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于maxISCover 优化方法和unifyIS 算法建立的索引大小相比于基于原始2-hop索引的方法减小1 个~2 个数量级。
-
计算机工程. 2015, 41(2): 173-177. https://doi.org/10.3969/j.issn.1000-3428.2015.02.033在经典双足被动步行动力学模型的基础上,分析环境和力学参数影响下机器人被动步行的全局稳定性。计算不同模型参数下被动步行稳定不动点,采用胞胞映射计算得到不同模型参数下该动力学模型稳定单周期步态的吸引区域。研究发现双足被动步行的鲁棒性与其环境、力学参数关系密切,同时提出估计不动点吸引域形状的2 个度量:最小半径与最大半径。实验结果给出被动步行稳定区域与斜坡倾角和质量比值的关系,同时通过分析某些偏离不动点较大的稳定吸引胞,以及吸引域的最小半径与最大半径的变化趋势,反映了双足被动步态的鲁棒性。
-
计算机工程. 2015, 41(2): 178-183,188. https://doi.org/10.3969/j.issn.1000-3428.2015.02.034
针对混沌系统参数估计的多峰寻优问题,提出一种改进的多种群差分进化算法。改进差分进化算法的变异操作,使其前期更适合全局性搜索,利用α 核心集对当前种群进行聚类,分别对聚类后的子群选用贪婪的差分变异算子完成深度搜索,比较所选取各子群的最优值,得到全局最优值作为是否结束搜索的判断依据,并将其应用到混沌系统参数估计中。实验结果表明,该算法对于多峰值、大空间的全局性参数估计在收敛速度、精度上优于混合量子进化算法、改进粒子群优化算法以及DE / best / 2 算法。
-
计算机工程. 2015, 41(2): 184-188. https://doi.org/10.3969/j.issn.1000-3428.2015.02.035为克服传统蚁群系统(ACS)在较大规模问题计算中易陷入局部最优,以及求解精度较低等不足,提出一种新的改进蚁群算法。该算法引入最小1-树中的α-邻近概念,能更好地反映给定边属于最优回路的概率,通过转换邻接矩阵,计算出最优回路的下界,以此提高α 值的精度,并给出适应性探索策略,加入3-opt 领域搜索算子,有效提高优化解的精度。实验结果表明,该算法具有更好的全局寻优能力,与ACS 等算法相比能获得更加优化 的解。
-
计算机工程. 2015, 41(2): 189-192,198. https://doi.org/10.3969/j.issn.1000-3428.2015.02.036K-近邻计算在数据集规模较大时计算复杂度较高,因此,利用图形处理器(GPU)强大的并行计算能力对K-近邻算法进行加速。在分析现有K-近邻算法的基础上,针对该算法时间开销过大的问题,结合GPU 的体系结构特征实现基于GPU 的K-近邻算法。利用全局存储器的合并访问特性,提高GPU 全局存储器访问数据的效率,通过事先过滤数据的方法来减少参与排序的数据量,进而减少排序阶段的线程串行化时间。在KDD,Poker, Covertype 3 个数据集上进行实验, 结果表明, 该实现方法在距离计算阶段每秒执行的浮点运算次数为266. 37 ×109 次,而排序阶段为26. 47 ×109 次,优于已有方法。
-
计算机工程. 2015, 41(2): 193-198. https://doi.org/10.3969/j.issn.1000-3428.2015.02.037针对实时、多源、海量数据条件下用户所需信息的获取问题,提出一种面向对象的、基于多智能体协同的多源信息搜索模型,以对象为中心,在反馈循环搜索的过程中,完善对象描述模型并实现多源数据中关联对象信息的获取,提高多源信息获取的全面性和准确性。设计基于Q 学习的协同控制算法,针对马尔科夫对象与非马尔科夫对象给出相应的决策方法。实验结果表明,该协同控制算法比概率转移矩阵及概率统计算法具有更好的信息获取能力。
-
计算机工程. 2015, 41(2): 199-202. https://doi.org/10.3969/j.issn.1000-3428.2015.02.038针对传统形态滤波器滤除高浓度椒盐噪声不足的问题,提出一种基于形态开闭算子自适应的高浓度椒盐噪声去除方法。该方法分为噪声检测和形态开闭自适应滤波2 个阶段。在噪声检测阶段,得到噪声标记图像,并依据噪声标记图像生成自适应的结构元素。在形态滤波阶段,对可能的噪声点进行形态开闭滤波,而对非噪声点不做滤波处理直接输出。通过一个简单的噪声检测方法构造自适应结构元素,提升传统形态滤波器的滤波能力。 仿真结果表明,该方法能有效去除高浓度的椒盐噪声,较好地保留图像的细节信息,并且算法简单,运算时间较短。
-
计算机工程. 2015, 41(2): 203-208. https://doi.org/10.3969/j.issn.1000-3428.2015.02.039鉴于烟雾检测对火灾预警的重要作用,提出一种基于Surfacelet 变换的动态纹理烟雾检测算法。先对图像序列进行Surfacelet 变换,再对变换后的系数进行广义高斯建模,获得与系数相对应的模型参数作为特征,最后使用KL 距离做相似性度量。与其他3 种基于Surfacelet 变换的烟雾检测方法进行对比,包括:使用均值和方差作为特征,支持向量机进行分类;使用均值和方差作为特征,欧式距离进行相似性度量;使用广义高斯模型参数作为特征,欧式距离进行相似性度量。实验结果表明,该算法可以提高烟雾检测准确性,降低误检率,有效去除类烟运动物体的干扰。
-
计算机工程. 2015, 41(2): 209-214. https://doi.org/10.3969/j.issn.1000-3428.2015.02.040在利用分数阶微分进行图像增强时,现有方法大多是基于0 ~1 阶分数阶微分,而基于1 ~2 阶分数阶微分 的方法较少。为此,分析1 ~2 阶分数阶微分对图像增强的作用,基于1 ~2 阶分数阶微分构造一种用于图像增强的 掩模算子。实验结果表明,该算子优于常用的频域法和空域法,比现有的一些0 ~1 阶分数阶微分算子具有更好的图像增强效果。
-
计算机工程. 2015, 41(2): 215-218,223. https://doi.org/10.3969/j.issn.1000-3428.2015.02.041针对传统自动色彩均衡算法运算速度慢、暗区细节不明显的缺点,提出一种基于金字塔分解的自动色彩均衡算法。使用对数运算将暗区图像映射到更适合人眼观察的颜色空间,利用高斯卷积核构造图像金字塔图像序列,从金字塔最顶层图像开始进行自动色彩均衡,并对增强结果逐层进行细化,直至金字塔最底层得到最终的增强图像,细化时只需要少量像素间的比较操作,因而大幅降低了运算复杂度。实验结果表明,该算法能有效改善图像质量,保持图像细节信息,并且计算复杂度较低,便于实际应用。
-
计算机工程. 2015, 41(2): 219-223. https://doi.org/10.3969/j.issn.1000-3428.2015.02.042图像融合算法性能评价是图像融合工程的重要组成部分,现有的融合评价指标从不同方面评价融合图像 质量,这些指标在评价图像融合算法性能时存在片面性,难以对融合算法的综合性能作出评价。为此,运用多指标 决策技术,提出一种加权总分指标,将多个指标评价值综合为单一值,从而对图像融合算法进行综合性能评价。将 加权总分指标的评价结果同逼近理想解排序指标以及秩和比指标的结果相比较,实验结果表明,该指标的评价结 果和主观评价结果一致,其综合评价能力与其他2 种指标相近,提高了融合算法综合性能评价结果的可靠性和准确性。
-
计算机工程. 2015, 41(2): 224-227,233. https://doi.org/10.3969/j.issn.1000-3428.2015.02.043图像待插像素用其邻域内连续方向上像素的Tyler 展开可以得到较好的近似,但是沿着灰度连续和不连 续方向(跨越图像边缘方向)的Tyler 展开近似的线性平均会增加图像边缘宽度,引起图像边缘的视觉模糊以及产 生锯齿边缘。为此,通过一个与灰度距离相关的权函数,自适应选择待插像素邻域内的Tyler 展开,提出一个邻域 滤波图像插值方法。与待插像素位于图像边缘同侧的像素权函数的值较大,像素的Tyler 展开被选择为待插像素 的近似;反之则权函数的值较小,像素的Tyler 展开不用作待插像素的Tyler 展开。实验结果表明,该方法避免了跨 越图像边缘的Tyler 展开的线性平均,可减小插值图像边缘的宽度,增加边缘斜坡坡度,从而获得清晰的插值图像边缘。
-
计算机工程. 2015, 41(2): 228-233. https://doi.org/10.3969/j.issn.1000-3428.2015.02.044在三维阴影绘制中,平行分割阴影图(PSSM)算法存在第一个分割区域过小而导致锯齿现象的缺陷,方差 阴影图(VSM)算法则会引起严重的光渗现象。针对以上不足,提出一种结合PSSM 与VSM 的混合算法。通过设 置扩大系数解决PSSM 算法首个分割区域不足的问题,加入模糊处理,重复渲染过渡区域,以减少边界锯齿现象,采用MRT 技术减少VSM 算法在渲染时引起的光渗现象。由分割方法、渐进方式、纹理大小及混合算法阴影图绘制效果等方面的实验结果表明,与PSSM 等算法相比,该算法绘制的阴影图质量有较大提高。
-
计算机工程. 2015, 41(2): 234-241. https://doi.org/10.3969/j.issn.1000-3428.2015.02.045经典竞争聚集(CA)算法在聚类时对于样本中的少量已知信息没有加以利用,但这些信息往往需要应用到整个聚类过程中。此外,在相似度度量函数的选择上CA 算法使用常见的欧氏距离,然而欧氏距离仅适用于团状数据,制约了算法的应用范围。针对上述问题,通过引入具备半监督学习能力的半监督项对隶属度矩阵进行增强,利用聚类中心和中心邻近的点组成空间,把样本点与该空间的距离替代欧氏距离作为新的相似度度量标准,并给 出判断聚类中心能否合并的阈值参数,最终得到半监督空间化CA 算法。通过在人造图像和真实图像上的分割结果表明,该算法能够更准确地获取聚类类别数以及更好的聚类效果。
-
计算机工程. 2015, 41(2): 242-247. https://doi.org/10.3969/j.issn.1000-3428.2015.02.046To solve the problem that the motion capture data has a large number of data redundancy,this paper proposes a key frame extraction method based on inter-frame pitch. In order to compress,storage,reconstruct and further reuse motion data,key-frame is needed to be extracted which represents the content of the motion. Quaternion is introduced to represent the difference between two rotations. The distance between two frames is defined by the total rotation differences and first frame is regarded as the first key frame. Then,calculate the difference between the current frame and the last key frame continuously. The frame is eliminated when the difference is smaller than the set threshold or the opposite is reserved for the new key frame. Spherical linear interpolation is used to reconstruct the sequence. To express the characteristics of human motion,the joint velocity is introduced. Reconstruction error is defined by the human body posture error of position and the motion speed error between the original frame and the reconstructed frame. Experimental resultdemonstrates that the original motion capture can be compressed in a high ratio and gives a good visual summary erformance.
-
计算机工程. 2015, 41(2): 248-252,257. https://doi.org/10.3969/j.issn.1000-3428.2015.02.047针对异构环境中网络和终端的复杂性,以及用户随机搜索行为造成的视频点播服务中播放进度的突变性,提出一种异构环境中基于用户行为特征的可扩展视频编码分片调度算法。设计2 类调度窗口,即根据当前播放时刻保证顺序播放数据持续功能的播放窗口和依据服从Weibull 分布的用户随机搜索行为设计的加入数据预取机制的锚点窗口。对播放窗口和第一个锚点窗口采用逐层调度策略,以保证数据的及时性,其余锚点窗口使用rarestfirst策略,以平衡整个系统的分片分布。在OverSim 平台上的仿真结果表明,与现有的逐层调度算法和权值调度算法相比,该算法在发生用户随机搜索行为的应用场景中能提高节点分片调度性能,缩短响应时延,降低服务器负载,提高用户观看视频的质量和流畅度。
-
计算机工程. 2015, 41(2): 253-257. https://doi.org/10.3969/j.issn.1000-3428.2015.02.048移动平台上高交互感的三维花卉植物可视化已成为植物研究、园艺设计等领域的重要需求,但现有植物运 动形变方法还不能根据触摸力度对整株花卉植物或单一叶片的受力进行不同的形变过程模拟。为此,提出一种改 进的三维花卉植物触摸反馈可视化模拟方法。根据植物整株交互需求或单一叶片受力情况,研究不同方式的触摸 反馈模拟方法。在模拟触摸反馈时,整株受力应用动力学原理,抽象为杆件模型并计算形变结果。单一叶片受力 时,根据触摸屏获取数据,并结合叶脉骨架旋转模型算法,模拟不同力度触摸造成的叶片形变,过程中无需手动输 入参数。仿真结果表明,该方法应用于移动平台后,帧速率稳定,具有较高的真实感。
-
计算机工程. 2015, 41(2): 258-262,267. https://doi.org/10.3969/j.issn.1000-3428.2015.02.049为降低多视点视频编码(MVC)中过高的计算量,提出基于宏块多相关性的多视点视频编码视间预测与Direct 模式提前终止算法。分析MVC 参考模型(JMVC)中时域预测和视间预测的特点及Direct 模式的分布情况。基于当前宏块的时间和视点之间率失真代价的大小关系判断是否进行视间预测。利用先前已编码宏块的编码模式信息确定是否跳过Direct 模式。实验结果表明,同JMVC 的全搜索算法相比,该算法能降低编码的计算复杂度,平均可达75. 62% ,同时保持几乎相同的编码率失真性能。
-
计算机工程. 2015, 41(2): 263-267. https://doi.org/10.3969/j.issn.1000-3428.2015.02.050电信运营商专用视频内容分发系统是未来承担智能电视视频分发的主力,但急剧上升的成本严重制约电信运营商视频内容分发系统的可持续发展。针对该情况,从成本控制角度对电信运营商视频内容分发系统的分发策略进行评估。提出成本相关的评估指标和相关参数,以上海电信网络电视系统为例分析实际用户行为,构建大规模视频内容分发仿真系统,进行大量仿真实验。实验结果展示了评估指标和相关参数间的定量关系,该分发策 略能够使系统成本最小,为电信运营商选择内容分发策略提供理论依据。
-
计算机工程. 2015, 41(2): 268-271,277. https://doi.org/10.3969/j.issn.1000-3428.2015.02.051传统的远程视频监控系统所需软硬件资源大、视频传输协议和视频采集设备控制协议相互独立,系统传输带宽要求高、时延长、实时性不高。为解决这些问题,利用开放无线监控协议中的信息体结构,将视频信息传输、视频采集设备控制和其他信息融合在一个数据包中,并基于iOS 移动操作系统和H. 264 视频编码标准,设计并实现一种集视频传输与控制于一体的移动视频监控软件。测试结果表明,该移动视频监控软件可有效提高移动视频监控系统的性能,具有控制响应速度快、传输带宽要求低、分辨率自适应以及实时视频播放流畅等特点。
-
计算机工程. 2015, 41(2): 272-277. https://doi.org/10.3969/j.issn.1000-3428.2015.02.052应用协议识别在网络安全领域具有极其广泛的应用,而如何发现协议特征是协议识别的核心问题。为此,提出一种高效准确的协议特征自动发现方法。利用协议自身的格式特点,将消息进行token 化,并根据token 序列对消息进行分类。由分类数的变化曲线大致判别协议的首部长度,从而确定字频统计的范围。对数据流中每个数据包的消息首部进行字节频率统计,并将字节频率进行归一化处理,得到字节频率特征向量。通过计算待测协议与样本协议的余弦相似度对协议进行分类和识别。实验结果表明,用该方法所提取的特征进行识别,准确率超过93. 5% 。
-
计算机工程. 2015, 41(2): 278-281,286. https://doi.org/10.3969/j.issn.1000-3428.2015.02.053传统的超声测距方法基于单频脉冲飞行时间,原理简单、应用灵活,但由于声波易受空气衰减以及电路噪声影响,其测量精度较低,多频连续波相位检测法可以达到较高的精度,但其受限于连续声波发射,应用范围较小。为兼顾测量精度与应用范围,提出一种采用多频超声脉冲发射的方法,利用各频段声波之间的固有时间差值,结合飞行时间法精确估计超声脉冲的到达时间,再通过温度补偿测量现场的声速,即可得到精确的被测距离。该方法能够拓展超声测距的应用范围,简化硬件设计,经实验验证,在3 m 范围内,测量精度可以达到0. 3 mm左右。
-
计算机工程. 2015, 41(2): 282-286. https://doi.org/10.3969/j.issn.1000-3428.2015.02.054超声导波在高速公路护栏立柱检测中存在信噪比低、回波中特征信号不明显等问题,为此,提出一种改进 的子空间匹配追踪算法(ISMP),利用回波信号的先验信息在过完备Chirp 原子库上得到每次迭代的强相关原子 集,经过迭代得到待匹配信号的最佳时频原子,从而实现对立柱回波信号的特征提取。通过对中心频率为128 kHz的检测信号进行算法验证,结果表明,ISMP 可以有效提取出回波信号的特征原子,所得检测长度与实际测量误差小于1% ,满足工程检测要求。
-
计算机工程. 2015, 41(2): 287-291,297. https://doi.org/10.3969/j.issn.1000-3428.2015.02.055皮卫星具有成本低、反应灵敏等特点,是航天领域的研究热点。由于体积和质量的限制,大卫星复杂的星载计算机系统结构并不适用于皮卫星。介绍基于COTS 器件的皮卫星星载计算机系统模块化设计技术,将多准则决策方法TOPSIS 排序法应用于皮卫星的芯片选型。研制2 版基于不同低功耗微控制单元的计算机原理样机,并通过大量实验测试比较2 版原理样机的速度、功耗、运行温度等性能。当工作温度为27℃ ,主频为8 MHz 时,基于MSP430 芯片和ATxmega 芯片的原理样机的MIPS 值分别为7. 449 和6. 781;运行加法运算的时间分别为0. 613 μs和1. 381 μs,功耗分别为38. 224 mW 和54. 411 mW。在-40℃ ~85℃ 时,原理样机均可正常工作。
-
计算机工程. 2015, 41(2): 292-297. https://doi.org/10.3969/j.issn.1000-3428.2015.02.056基于异构GPU 集群的主流编程方法是MPI 与CUDA 的混合编程或者其简单变形。因为对底层的集群架构不透明,程序员对GPU 集群采用MPI 与CUDA 编写应用程序时需要人为考虑硬件计算资源,复杂度高、可移植性差。为此,基于数据流模型设计和实现面向节点异构GPU 集群体系结构的新型编程框架分布式并行编程框架(DISPAR)。DISPAR 框架包含2 个子系统:(1)代码转换系统StreamCC,是DISPAR 源代码到MPI + CUDA 代码的自动转换器。(2)任务分配系统StreamMAP,具有自动发现异构计算资源和任务自动映射功能的运行时系统。实验结果表明,该框架有效简化了GPU 集群应用程序的编写,可高效地利用异构GPU 集群的计算资源,且程序不依赖于硬件平台,可移植性较好。
-
计算机工程. 2015, 41(2): 298-302. https://doi.org/10.3969/j.issn.1000-3428.2015.02.057多色点集划分研究如何将含有不同颜色点的平面划分为各个区域,每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此,提出用直线来划分平面。针对平面上多色点集的直线划分,将其离散化,证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT 问题在多项式时间内归约到组合优化问题,证明多色点集直线划分为NP 难,从而证明其是NP 完全的。利用最优化版本的特有性质,运用贪心方法构造出多项式时间的近似算法,并L 归约到Setcover 问题,以此证明算法的近似比为O(lgn)。
-
计算机工程. 2015, 41(2): 303-307. https://doi.org/10.3969/j.issn.1000-3428.2015.02.058针对射频识别(RFID)系统中标签数量未知的情况,采用传统ALOHA 算法进行标签估计,在标签数量较大而初始帧长度较小造成估计误差较大时,初始帧长度为固定值,通过改变响应标签数量的方式,达到准确估计标签的目的。研究标签鲁棒估计算法和随机前缀查找树(PRQT)防碰撞算法,在此基础上提出基于鲁棒估计的自适应最大前缀查找树(PMQT)防碰撞算法。理论分析和仿真结果表明,该算法系统效率可达50% 以上。PMQT 算法 比PRQT 算系统效率提高18% ~30% ,对标签估计偏差具有较高的鲁棒性。
-
计算机工程. 2015, 41(2): 308-312. https://doi.org/10.3969/j.issn.1000-3428.2015.02.059针对射频识别(RFID)标签防碰撞算法识别效率低的问题,提出一种基于二进制码调制的RFID 标签防碰 撞算法BCMA。对传统多叉树防碰撞算法进行改进,活动标签采用位编码技术把标签ID 在多叉数中的位置信息 调制到一个2m 位的二进制数主控继电器(MCR)上,并把MCR 回送给阅读器;阅读器采用位跟踪技术,定位MCR碰撞发生的数位,从而解调出活动标签的分组信息。阅读器对待识别标签的分组是确定性的,进而避免空闲时隙 的产生,提高系统识别效率。仿真结果表明,与常见的八叉树算法相比,BCMA 算法使系统吞吐率提高168% 。
-
计算机工程. 2015, 41(2): 313-316. https://doi.org/10.3969/j.issn.1000-3428.2015.02.060针对无线自组网的拓扑结构,设计一种基于分簇的无线自组网节点故障检测架构和对应的故障检测算法。分簇时分别确定主用簇和备用簇管理节点,冗余簇管理节点负责对内部成员实施异常检测,给出故障检测模块的心跳发送、心跳监控、心跳预判与实时调整机制,通过增加心跳预判实时调整机制,确保算法能够动态适应自组网易变的拓扑结构,并通过备用簇管理节点和簇间共享异常信息机制,提高系统故障检测的可靠性。利用仿真实验对故障检测机制的性能进行评估,结果表明,提出的故障检测算法具备较好的检测准确率,能够有效满足上层应用在系统可靠性设计方面的需求。
-
计算机工程. 2015, 41(2): 317-321. https://doi.org/10.3969/j.issn.1000-3428.2015.02.061轻量级TCP / IP 协议栈(LwIP)主要应用于资源受限的嵌入式设备。为满足嵌入式设备对实时性的要求,分析LwIP 的内部机制,对其进行性能瓶颈分析,并根据分析结果设计、实施LwIP 的实时性和优先级管理优化方案。LwIP 的主要性能瓶颈是内存拷贝和校验过程,据此给出优化后的内存拷贝算法和校验算法。为满足紧急数据对更高优先级的要求,给出LwIP 协议栈优先级管理机制,能够确保高优先级标记的紧急数据包优先传输于普通数据包。实验结果表明,该优化方法可以显著提高LwIP 的实时性能。
2024
第50卷 第4期
第50卷 第4期
(1975年创刊 月刊)
主管：中国电子科技集团公司
主办：华东计算技术研究所
上海市计算机学会
主编：江波
执行主编：胡冰
电话：021-67092217(费用/发票)
（稿件问题请直接联系栏目编辑） E-mail: ecice06@ecict.com.cn
国内刊号：CN 31-1289/TP
国际刊号：ISSN 1000-3428
主管：中国电子科技集团公司
主办：华东计算技术研究所
上海市计算机学会
主编：江波
执行主编：胡冰
电话：021-67092217(费用/发票)
（稿件问题请直接联系栏目编辑） E-mail: ecice06@ecict.com.cn
国内刊号：CN 31-1289/TP
国际刊号：ISSN 1000-3428