• 2012年第23卷第4期文章目次
    全 选
    显示方式: |
    • 短文本信息流的无监督会话抽取技术

      2012, 23(4):735-747. DOI: 10.3724/SP.J.1001.2012.04031

      摘要 (5658) HTML (0) PDF 704.01 K (6455) 评论 (0) 收藏

      摘要:文本会话抽取将网络聊天记录等短文本信息流中的信息根据其所属的会话分检到多个会话队列,有利于短文本信息的管理及进一步的挖掘.现有的会话抽取技术主要对基于文本相似度的聚类方法进行改进,面临着短文本信息流的特征稀疏性、奇异性和动态性等挑战.针对这些挑战,研究无监督的会话抽取技术,提出了一种基于信息流时序特征和上下文相关度的抽取方法.首先研究了信息流的会话生命周期规律,提出基于信息产生频率的会话边界检测方法;其次提出信息间的上下文相关度概念,采用基于实例的机器学习方法计算该相关度;最后综合信息产生频率和上下文相关度,设计了基于Single-Pass 聚类模型的会话在线抽取算法SPFC(single-pass based on frequency and correlation).真实数据集上的实验结果表明,SPFC算法与已有的基于文本相似度的会话抽取算法相比,F1 评测指标提高了30%.

    • 监督式谱空间分类器

      2012, 23(4):748-764. DOI: 10.3724/SP.J.1001.2012.04039

      摘要 (4086) HTML (0) PDF 968.33 K (6190) 评论 (0) 收藏

      摘要:提出了一种非线性的监督式谱空间分类器(supervised spectral space classifier,简称S3C).S3C 首先将输入数据映射到融合了训练数据判别信息的低维监督式谱空间中,然后在该监督式谱空间中构造最大化间隔的最优分割超平面,并把测试数据以无监督的方式也映射到与训练数据相同的新特征空间中,最后,直接应用之前构建的分类超平面对映射后的测试数据进行分类.由于S3C 使研究者可以直观地观察到变化后的特征空间和映射后的数据,因此有利于对算法的评价和参数的选择.在S3C 的基础上,进一步提出了一种监督式谱空间分类器的改进算法(supervised spectral space transformation,简称S3T).S3T 通过采用线性子空间变换和强迫一致的方法,将映射到监督式谱空间内的数据再变换到指定的类别指示空间中去,从而获得关于测试数据的类别指示矩阵,并在此基础上对其进行分类.S3T 不仅保留了S3C 算法的各项优点,而且还可以用于直接处理多分类问题,抗噪声能力更强,性能更加鲁棒.在人工数据集和真实数据集上的大量实验结果显示,S3C 和S3T 与其他多种著名分类器相比,具有更加优越的分类性能.

    • 双精英协同进化遗传算法

      2012, 23(4):765-775. DOI: 10.3724/SP.J.1001.2012.04040

      摘要 (4912) HTML (0) PDF 629.00 K (7379) 评论 (0) 收藏

      摘要:针对传统遗传算法早熟收敛和收敛速度慢的问题,提出一种双精英协同进化遗传算法(double elitecoevolutionary genetic algorithm,简称DECGA).该算法借鉴了精英策略和协同进化的思想,选择两个相异的、高适应度的个体(精英个体)作为进化操作的核心,两个精英个体分别按照不同的评价函数来选择个体,组成各自的进化子种群.两个子种群分别采用不同的进化策略,以平衡算法的勘探和搜索能力.理论分析证明,该算法具有全局收敛性.通过对测试函数的实验,其结果表明,该算法能搜索到几乎所有测试函数的最优解,同时能够有效地保持种群的多样性.与已有算法相比,该算法在收敛速度和搜索全局最优解上都有了较大的改进和提高.

    • 基于词语距离的网络图词义消歧

      2012, 23(4):776-785. DOI: 10.3724/SP.J.1001.2012.04116

      摘要 (4893) HTML (0) PDF 574.53 K (6032) 评论 (0) 收藏

      摘要:传统的基于知识库的词义消歧方法,以一定窗口大小下的词语作为背景,对歧义词词义进行推断.该窗口大小下的所有词语无论距离远近,都对歧义词的词义具有相同的影响,使词义消歧效果不佳.针对此问题,提出了一种基于词语距离的网络图词义消歧模型.该模型在传统的网络图词义消歧模型的基础上,充分考虑了词语距离对消歧效果的影响.通过模型重构、优化改进、参数估计以及评测比较,论证了该模型的特点:距离歧义词较近的词语,会对其词义有较强的推荐作用;而距离较远的词,会对其词义有较弱的推荐作用.实验结果表明,该模型可以有效提高中文词义消歧性能,与SemEval-2007:task #5 最好的成绩相比,该方法在MacroAve(macro-average accuracy)上提高了3.1%.

    • 面向性能剖析的Web 应用自动性能建模方法

      2012, 23(4):786-801. DOI: 10.3724/SP.J.1001.2012.04027

      摘要 (4395) HTML (0) PDF 964.05 K (7499) 评论 (0) 收藏

      摘要:提出了一种面向性能剖析的Web 应用自动性能建模方法.该方法考虑了用户行为与系统中不同服务之间的关联,动态地构造与应用实际状态相符的性能模型,并利用Kalman 滤波所具备的过滤“噪声”和适应变化的特性,精确估算各服务所需CPU 时间.实验结果表明,该方法可以适应Web 应用内、外部环境的变化,分析结果可为瓶颈定位和容量规划等性能保障技术提供高质量数据.

    • 自主构件自适应策略的在线定制及动态评估

      2012, 23(4):802-815. DOI: 10.3724/SP.J.1001.2012.04029

      摘要 (4397) HTML (0) PDF 823.33 K (5251) 评论 (0) 收藏

      摘要:开放分布式环境下自适应软件的研究已引起学术界、工业界的广泛关注.但分布在网络上的软件实体是由不同的组织独立开发并部署的,它们代表各自的组织(或所有者)自主地采取行动,在构造分布式环境下的自适应系统时,不能再将构成单元视为被动的受管对象,而应将其建模为具有主动行为能力的计算实体,并在这一层面设计和封装系统的自适应逻辑.然而,在现阶段对于自主计算实体的研究中,大多缺乏对于自适应策略的动态加载和动态演化的支持.提出了一种支持策略动态加载的自主构件模型,使得自主构件能够在运行时习得新的自适应策略和行为,实现了一种基于质量运行时动态评估的自主构件的自适应机制,使得自主构件能够自行评估自适应策略的优劣并选择最佳的策略加以适应,在保证自身目标得以实现的同时,提高了服务质量.另外,还详细描述了自主构件的实现方案及其运行支撑,通过实验展示了自主构件基于质量动态评估的自适应过程以及自适应策略的动态加载过程.

    • 一种支持多种模型转换技术的组合方法

      2012, 23(4):816-830. DOI: 10.3724/SP.J.1001.2012.04041

      摘要 (3905) HTML (0) PDF 1.37 M (6099) 评论 (0) 收藏

      摘要:模型转换是模型驱动开发中的核心技术.为了解决复杂的转换问题,需要将多个相对简单的转换组合起来构成组合转换.目前存在多种转换技术,它们之间存在异构性,阻碍了组合转换的实现.首先分析实现组合转换的必要条件,进而提出一个组合转换模型,其中主要包括公共类型表示、公共模型表示、公共转换描述和组合转换定义语言等部分,用以实现支持多种转换技术的组合.另外,还介绍了一个组合转换平台的设计与实现,并通过一个案例说明所提方法及工具的可行性.

    • 基于MOF 的软件体系结构分析结果集成框架

      2012, 23(4):831-845. DOI: 10.3724/SP.J.1001.2012.04043

      摘要 (3844) HTML (0) PDF 3.98 M (5380) 评论 (0) 收藏

      摘要:运行在网络环境下的软件在自适应过程中,需要集成多种分析方法来进行分析、规划和决策.由于自适应的决策程序或者设计人员以SA(software architecture)模型作为解析和理解分析结果的上下文,这使得分析结果与SA 模型的集成尤为重要.但是,现有的分析方法集成框架多关注于提供输入、执行分析、从而得到分析结果的过程,对分析结果的集成关注不够.针对分析结果与SA 模型集成中元模型、模型和视图3 个层次的挑战,提出一种软件体系结构分析结果集成框架.框架使用MOF(meta-object facility)元建模技术提供ADL(architectural descriptionlanguage)的扩展机制;使用自动生成模型转换实现SA 模型与分析结果的合成;使用代码生成技术扩展建模工具为扩展后的ADL 提供模型视图.最后以3 种分析方法——两种可靠性评估方法和容错风格的规划方法为例,使用集成框架将其加以集成并应用于Ecperf 系统的SA 模型的分析中,从而展示集成框架的可行性和有效性.

    • 一种软件演化过程模型的代数语义

      2012, 23(4):846-863.

      摘要 (5497) HTML (0) PDF 0.00 Byte (6547) 评论 (0) 收藏

      摘要:随着大量的软件演化过程模型被软件演化过程元模型建模产生,如何验证过程模型的正确性,是摆在人们面前的一个重要任务.针对软件演化过程元模型,引入进程代数ACP(algebra of communicating processes)对其扩展,提出软件演化过程元模型代数,使用进程项指定软件演化过程模型的代数语义,在进程代数的统一框架下,基于等式推理验证软件演化过程模型的行为,使行为验证方式从模型推导变为代数推导.这种方法充分结合了Petri 网和ACP 的长处,可以有效地支持软件演化过程的形式验证.

    • >综述文章
    • 虚拟网络映射模型及其优化算法

      2012, 23(4):864-877. DOI: 10.3724/SP.J.1001.2012.04063

      摘要 (8132) HTML (0) PDF 852.58 K (10192) 评论 (0) 收藏

      摘要:网络虚拟化被视为构建新一代互联网体系架构的重要技术,它使得能在一个共享的底层物理网络上同时运行多个网络架构或网络应用,从而能为用户提供多样化的端到端定制服务.虚拟网络映射是实现网络虚拟化的关键环节,其目的是在满足虚拟网络资源需求的前提下,将虚拟网络植入到合适的底层物理节点和链路.虚拟网络映射需要解决资源约束、准入控制、在线请求和拓扑多样性等多方面的问题.根据应用场景、优化目标、映射方式和约束条件的不同,可以得到不同类型的虚拟网络映射优化问题.这些优化问题通常是NP 难的.通过形式化建立了虚拟网络映射模型,归纳了虚拟网络映射的方法和算法.总结了解决虚拟网络映射模型优化问题的几条技术途径,指出了该领域中需要进一步研究的热点问题.

    • 基于零打扰测试背板的无线传感器网络测试平台

      2012, 23(4):878-893. DOI: 10.3724/SP.J.1001.2012.04013

      摘要 (3911) HTML (0) PDF 1.08 M (5056) 评论 (0) 收藏

      摘要:精确的网络运行状态监视和性能评估对于无线传感器网络的研究和实际部署具有极为关键的意义,而现有的测试技术和测试平台对无线传感器网络的自身运行存在一定的打扰,测试数据的精度也受限于传感器节点的硬件配置.针对现有测试技术和测试平台的缺陷,提出了内部侦听的测试方式,并进一步研发了基于零打扰测试背板的无线传感器网络测试平台.测试平台首先通过由额外的测试背板直接捕获传感器节点内部互连信号,产生测试数据;然后测试数据经由额外的传输网络传送到测试服务器,进行解析和预处理;最后,远程访问客户端通过订阅机制访问测试服务器上的测试数据,并对其分析和处理.测试平台在避免对无线传感器网络正常运行产生干扰的前提下,实现对运行时刻的无线传感器网络的高精度零打扰的透明测试.实验结果表明,基于零打扰测试背板的无线传感器网络测试平台可以对无线传感器网络进行信号分析、协议验证,并对性能进行精确的评估.

    • 面向非结构化P2P 网络的双向随机漫步搜索机制

      2012, 23(4):894-911. DOI: 10.3724/SP.J.1001.2012.04086

      摘要 (4705) HTML (0) PDF 1.02 M (5363) 评论 (0) 收藏

      摘要:为解决目前Random Walk 改进算法中过于依赖历史搜索记录而导致动态网络环境下搜索命中率低、网络开销过高和稀有资源的搜索成功率提高不明显等问题,通过分析随机漫步的基本性质和易转向高度数节点的搜索特性,提出了一种双向随机漫步搜索机制——BRWS(bidirectional random walk search),并证明了其能够提高包括稀有资源在内的搜索成功率,抗扰动性强.分别在静态和动态网络环境中,将Random Walk,APS(adaptive probabilisticsearch),PQR(path-traceable query routing),P2PBSN(peer-to-peer based on social network)和BRWS 基于RandomGraph、Scale Free 网络、Small World 网络3 种拓扑进行了对比实验.结果表明,BRWS 可以以较少的网络搜索代价,极大地提高搜索成功率;并在动态网络环境中,对稀有资源的搜索成功率也有显著提高.所提出的方法可适用于P2P文件分发网络应用中.

    • 基于良基语义的安全策略表达与验证方法

      2012, 23(4):912-927. DOI: 10.3724/SP.J.1001.2012.04023

      摘要 (4168) HTML (0) PDF 822.81 K (5026) 评论 (0) 收藏

      摘要:提出了一种基于一阶逻辑的安全策略管理框架.首先,研究安全策略的语法和语义,给出将安全策略转换成扩展型逻辑程序的算法,进而构造出安全策略基本查询算法;其次,给出将安全策略复杂查询转换成基本查询的算法,进而构造出安全策略验证算法.在良基语义下,上述算法是可终止的、可靠的和完备的,且计算复杂度都是多项式级的.该框架可以在统一的良基语义下实现安全策略表达、语义查询和验证,保证安全策略验证的有效性.此外,该框架不仅兼容现有主流的安全策略语言,还能够管理具有非单调和递归等高级特性的安全策略.

    • 多元合同签署协议

      2012, 23(4):928-940. DOI: 10.3724/SP.J.1001.2012.04024

      摘要 (3942) HTML (0) PDF 656.30 K (4893) 评论 (0) 收藏

      摘要:利用Cha-Cheon 的基于身份的签名方案提出了一个可证安全的基于身份的可验证加密签名(verifiablyencrypted signature,简称VES)方案,并利用该方案和基于身份的代理可验证加密签名(proxy verifiably encryptedsignature,简称PVES)方案提出了一个新颖的多元合同签署协议.信息交换过程中,原始签名者或代理签名者分别利用VES 或PVES 实现承诺消息的交换与认证,并未使用复杂的零知识证明系统,从而有效避免了大量运算.当争议发生时,可信第三方从VES 或PVES 中恢复出有效的合同签名,以保证签署者的公平性.安全性分析结果表明,协议满足不可否认性、时效性以及公平性.

    • 相继干扰消除的无线网络中的调度算法

      2012, 23(4):941-951. DOI: 10.3724/SP.J.1001.2012.04035

      摘要 (4738) HTML (0) PDF 595.68 K (4605) 评论 (0) 收藏

      摘要:相继干扰消除(successive interference cancellation,简称SIC)是一种多包接收技术,它从冲突信号中解码报文.SIC 可有效减轻无线网络中的干扰. SIC 的顺序解码特性给链路调度带来了新的挑战.提出并发图以刻画SIC 导致的链路相关性.基于并发图,定义链路的干扰数并据此设计有效的调度机制.证明了基于并发图的链路调度是NP-hard 的,而最大干扰数提供了极大贪婪算法的性能下界.在讨论了一类基于独立集的贪婪算法之后,结合干扰数对链路排序,给出了一种理论上性能更好的算法.仿真结果表明,仅需略高于现有模型的开销,与IEEE 802.11 相比,新调度算法的性能提高可达110%.

    • 一类本原σ-LFSR 序列的构造与计数

      2012, 23(4):952-961. DOI: 10.3724/SP.J.1001.2012.04006

      摘要 (3895) HTML (0) PDF 556.34 K (4551) 评论 (0) 收藏

      摘要:有限域GF(2k)上本原σ-LFSR 序列的分量序列均是二元域上具有相同极小多项式的m-序列,已知一条GF(2k)上本原σ-LFSR 序列的距离向量,就可以用二元域上的m-序列构造它.研究了一类本原σ-LFSR 序列——Z 本原σ-LFSR 序列距离向量的计算问题.给出了一种GF(2k)上n 级Z 本原σ-LFSR 序列距离向量的计算方法,其主要思想是,利用GF(2k)上1 级Z 本原σ-LFSR 序列的距离向量来计算n 级Z 本原σ-LFSR 序列的距离向量.与其他现有方法相比,该方法的效率更高.更有价值的是,该方法也适用于GF(2k)上nm-序列距离向量的计算.最后给出了GF(2k)上n 级Z 本原σ-LFSR 序列的计数公式,说明其个数比GF(2k)上nm-序列更多.

    • >综述文章
    • 云计算环境下的分布存储关键技术

      2012, 23(4):962-986. DOI: 10.3724/SP.J.1001.2012.04175

      摘要 (18673) HTML (0) PDF 2.09 M (31571) 评论 (0) 收藏

      摘要:云计算作为下一代计算模式,在科学计算和商业计算领域均发挥着重要作用,受到当前学术界和企业界的广泛关注.云计算环境下的分布存储主要研究数据在数据中心上的组织和管理,作为云计算环境的核心基础设施,数据中心通常由百万级以上节点组成,存储其上的数据规模往往达到PB 级甚至EB 级,导致数据失效成为一种常态行为,极大地限制了云计算的应用和推广,增加了云计算的成本.因此,提高可扩展性和容错性、降低成本,成为云计算环境下分布存储研究的若干关键技术.针对如何提高存储的可扩展性、容错性以及降低存储的能耗等目标,从数据中心网络的设计、数据的存储组织方式等方面对当前分布存储的关键技术进行了综述.首先,介绍并对比了当前典型的数据中心网络结构的优缺点;其次,介绍并对比了当前常用的两种分布存储容错技术,即基于复制的容错技术和基于纠删码的容错技术;第三,介绍了当前典型的分布存储节能技术,并分析了各项技术的优缺点;最后指出了当前技术面临的主要挑战和下一步研究的方向.

    • DMStone:一个分级存储系统性能测试工具

      2012, 23(4):987-995. DOI: 10.3724/SP.J.1001.2012.04046

      摘要 (4909) HTML (0) PDF 1.05 M (5897) 评论 (0) 收藏

      摘要:对分级存储系统的性能测试,需要提供真实的系统状态和有代表性的访问负载.已有的分级存储系统测试方法通过播放一段时间的文件访问请求来生成系统状态.因为彻底忽略了近期未被访问的文件而与分级存储的真实场景不符,使得测试结果没有说服力.提出了一种分级存储系统性能测试工具DMStone,它使用文件系统快照生成某一时刻的系统状态,并根据后续的相邻快照之间的差异提取访问负载特征,进而生成有代表性的I/O 负载.DMStone 能够提供某一时刻真实的文件系统状态,涵盖了近期访问过的和长期不用的所有文件.而且,它能够保证后续文件访问的特征与真实应用场景相符合.

    • 多核系统中基于Global EDF 的在线节能实时调度算法

      2012, 23(4):996-1009. DOI: 10.3724/SP.J.1001.2012.04054

      摘要 (3753) HTML (0) PDF 728.03 K (5670) 评论 (0) 收藏

      摘要:随着多核系统能耗问题日益突出,在满足时间约束条件下降低系统能耗成为多核实时节能调度研究中亟待解决的问题之一.现有研究成果基于事先已知实时任务属性的假设,而实际应用中,只有当任务到达之后才能够获得其属性.为此,针对一般任务模型,不基于任何先验知识,提出一种多核系统中基于Global EDF 在线节能硬实时任务调度算法,通过引入速度调节因子,利用松弛时间,结合动态功耗管理和动态电压/频率调节技术,降低多核系统中任务的执行速度,达到实时约束与能耗节余之间的合理折衷.所提出的算法仅在上下文切换和任务完成时进行动态电压/频率调节,计算复杂度小,易于在实时操作系统中实现.实验结果表明,该算法适用于不同类型的片上动态电压/频率调节技术,节能效果始终优于Global EDF 算法,最多可节能15%~20%,最少可节能5%~10%.

    • 一种可行的分布式硬实时容错调度算法

      2012, 23(4):1010-1021. DOI: 10.3724/SP.J.1001.2012.04004

      摘要 (4440) HTML (0) PDF 637.87 K (5084) 评论 (0) 收藏

      摘要:针对分布式硬实时系统发生处理机故障后,当前周期内的任务实例和后续实例相对截止期限的不同紧迫程度,提出非紧迫周期内延迟策略——DNUP(delay in non-urgent period).该策略能够尽可能地推迟非紧迫实例的执行,使得低优先级实例有更多的机会完成其紧迫周期内的执行,从而实现处理器空闲(slack)资源的合理挪动.仿真实验结果表明,与其他几个著名的分布式容错调度算法相比,DNUP 策略能够提高任务的可调度性,从而有效减少了所需处理机的数目.

    • 大规模MPI 并行计算的可扩展三模冗余容错机制

      2012, 23(4):1022-1035. DOI: 10.3724/SP.J.1001.2012.04011

      摘要 (4604) HTML (0) PDF 721.23 K (5692) 评论 (0) 收藏

      摘要:随着系统规模的扩大,并行计算的性能不断提高,但可靠性却也在不断下降,因此需要采用某种容错机制来容忍或恢复硬件故障和数据错误.目前常用的容错机制Checkpoint/Restart 和多模冗余均引入了额外的开销,这些开销均在某种程度上制约了并行计算的可扩展性.因此,在高性能计算需求不断增长的今天,可扩展容错机制的设计显得尤为迫切和重要.以三模冗余(triple modular redundancy,简称TMR)为典型案例,描述了传统TMR 在大规模MPI并行计算上的实现方法,分析了该机制所面临的实际问题,进而指出传统TMR 制约了并行计算的扩展.根据该技术所面临的问题,设计了可扩展三模冗余(scalable triple modular redundancy,简称STMR),并进一步验证了其有效性和可扩展性.该机制不仅能够处理Checkpoint/Restart 针对的fail-stop 故障,还能够解决绝大部分硬件不能直接感知的数据错误.最后,借用BlueGene/L 的系统参数进行模拟,预测当系统规模增大时,在分别采用TMR和STMR的情况下并行计算可扩展性的变化,结果进一步验证了STMR 是可扩展的容错机制.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号