2012, 23(10):2533-2549. DOI: 10.3724/SP.J.1001.2012.04228
摘要:针对移动网络对个性化移动网络服务系统的性能提出了更高的要求,但现有研究难以自适应地修改上下文移动用户偏好以为移动用户提供实时、准确的个性化移动网络服务的问题,提出了一种上下文移动用户偏好自适应学习方法,在保证精确度的基础上缩短了学习的响应时间.首先,通过分析移动用户行为日志来判断移动用户行为是否受上下文影响,并在此基础上判断移动用户行为是否发生变化.然后,根据判断结果对上下文移动用户偏好进行修正.在对发生变化的上下文移动用户偏好进行学习时,将上下文引入到最小二乘支持向量机中,进一步提出了基于上下文最小二乘支持向量机(C-LSSVM)的上下文移动用户偏好学习方法.最后,实验结果表明,当综合考虑精确度和响应时间两方面因素时,所提出的方法优于其他学习方法,并且可应用于个性化移动网络服务系统中.
2012, 23(10):2550-2563. DOI: 10.3724/SP.J.1001.2012.04194
摘要:提议对加权库进行分层,一方面符合人类的思维习惯,另一方面能够提高推理效率.首先说明现有的针对非分层加权库的编译方法也适用于编译分层加权库,但是,由于存在较多冗余信息而效率不高.提出一种新的编译方法,能够在编译过程中去除冗余信息,并提出两种优化技术提高时间效率.该方法与现有方法相同,当软约束权值改变时无需重新编译.选择 ROBDD 为目标语言,使用随机问题对该方法进行测试.结果表明:对于非分层加权库,该方法的空间效率高于已存在方法;对于分层加权库,该方法的时间和空间效率均高于已存在方法,且当层数越多时,该方法的效率越高.
2012, 23(10):2564-2571. DOI: 10.3724/SP.J.1001.2012.04182
摘要:为解决定性空间关系的规划问题,在概念邻域图的基础上提出描述动作与定性空间关系交互的邻域划分图.基于邻域划分图,提出了定性空间关系自动规划的形式化表示和推理算法,证明了算法的可靠性,并举例说明了新方法的应用.该方法在处理单方面空间关系规划中具有用通用性,在机器人导航方面具有潜在的应用前景.
2012, 23(10):2572-2585. DOI: 10.3724/SP.J.1001.2012.04181
摘要:关系抽取是信息抽取的一项子任务,用以识别文本中实体之间的语义关系.提出一种利用 DBN(deepbelief nets)模型进行基于特征的实体关系抽取方法,该模型是由多层无监督的 RBM(restricted Boltzmann machine)网络和一层有监督的 BP(back-propagation)网络组成的神经网络分类器. RBM 网络以确保特征向量映射达到最优,最后一层 BP 网络分类 RBM 网络的输出特征向量,从而训练实体关系分类器.在 ACE04 语料上进行的相关测试,一方面证明了字特征比词特征更适用于中文关系抽取任务;另一方面设计了 3 组不同的实验,分别使用正确的实体类别信息、通过实体类型分类器得到实体类型信息和不使用实体类型信息,用以比较实体类型信息对关系抽取效果的影响.实验结果表明,DBN 非常适用于基于高维空间特征的信息抽取任务,获得的效果比 SVM 和反向传播网络更好.
田野 , 王文东 , 饶京海 , 王冠 , 郭亮 , 陈灿峰 , 马建
2012, 23(10):2586-2599. DOI: 10.3724/SP.J.1001.2012.04191
摘要:如何挖掘存储在手机上的大量短信息背后所隐含的会话信息,是一个非常具有挑战性的问题,因为它们并不具备“主题”、“回复”等经常被用于邮件线索分析的元数据.基于此,提出了一种基于时间聚类算法和话题检测的短信息会话识别模型.首先,根据短信息流的时间分布特性,将会话双方的所有短信息划分到一个一个的候选会话中,进而运用基于 latent Dirichlet allocation(LDA)训练出来的语义话题模型,对候选会话进行更深层次的分析;利用该话题模型度量了各个候选会话在话题上的相关度.最后,在综合时间和话题相关度的基础上,通过对候选会话的合并识别出隐含的会话信息.通过对包含了 50 名大学生在 6 个月中产生的 122 359 条短信进行实验验证,证明了该算法的有效性.
2012, 23(10):2600-2611. DOI: 10.3724/SP.J.1001.2012.04187
摘要:为求解二维矩形条带装箱问题,提出了一种新颖而有效的启发式算法.算法主要包括矩形装载适应度的计算规则和树型迭代搜索规则,通过选择最高适应度的矩形来装载空间.对大量国际上公认的 Benchmark 问题实例的计算结果表明,相对于当前的很多著名算法,提出的算法更加有效.
2012, 23(10):2612-2627. DOI: 10.3724/SP.J.1001.2012.04189
摘要:在传统信息抽取的基础上,研究 Web 实体活动抽取,基于格语法对实体活动进行了形式化定义,并提出一种基于SVM(supported vector machine)和扩展条件随机场的Web实体活动抽取方法,能够从Web上准确地抽取实体的活动信息.首先,为了避免人工标注训练数据的繁重工作,提出一种基于启发式规则的训练数据生成算法,将语义角色标注的训练数据集转化为适合 Web 实体活动抽取的训练数据集,分别训练支持向量机分类器和扩展条件随机场.在抽取过程中,通过分类器获得包含实体活动的语句,然后利用扩展条件随机场对传统条件随机场中不能利用的标签频率特征和关系特征建模,标注自然语句中的待抽取信息,提高标注的准确率.通过多领域的实验,其结果表明,所提出的抽取方法能够较好地适用于 Web 实体活动抽取.
2012, 23(10):2628-2642. DOI: 10.3724/SP.J.1001.2012.04192
摘要:在句法分析中,已有研究工作表明,词汇依存信息对短语结构句法分析是有帮助的,但是已有的研究工作都仅局限于使用一阶的词汇依存信息.提出了一种使用高阶词汇依存信息对短语结构树进行重排序的模型,该模型首先为输入句子生成有约束的搜索空间(例如,N-best 句法分析树列表或者句法分析森林),然后在约束空间内获取高阶词汇依存特征,并利用这些特征对短语结构候选树进行重排序,最终选择出最优短语结构分析树.在宾州中文树库上的实验结果表明,该模型的最高 F1 值达到了 85.74%,超过了目前在宾州中文树库上的最好结果.另外,在短语结构分析树的基础上生成的依存结构树的准确率也有了大幅提升.
2012, 23(10):2643-2654. DOI: 10.3724/SP.J.1001.2012.04153
摘要:由 Sch?lkopf 等人提出的ν支持向量回归机具有通过参数ν控制支持向量和错误向量个数的优点,然而与标准的支持向量机相比,其形式更为复杂,迄今为止仍没有有效的算法计算ν解路径.基于ν支持向量回归机的修改形式,提出了一种新的解路径算法,它能够追踪参数ν对应的所有解,并通过理论分析和实验,说明了该算法能够尽可能地避免不可行的更新路径,并在有限步内拟合出所有的ν解路径.
2012, 23(10):2655-2664. DOI: 10.3724/SP.J.1001.2012.04196
摘要:随着软件规模的不断扩大以及复杂度的不断增长,人们越来越关注软件的可信性问题.验证程序是否满足断言所描述的性质,是保证软件可信性的一种常见方法.路径敏感的程序验证由于不可能遍历所有的路径,需要合并路径信息,因此造成精度上的损失.提出一种基于 SMT 求解器的路径敏感程序验证方法,在保证精确度的前提下,有效减少路径搜索空间.其基本思想是,利用最大强连通分量压缩循环路径,然后根据目标断言对控制流图进行切片.使用一种布尔表达式方法对路径空间进行抽象,结合抽象解释和符号执行技术对路径进行验证.结合 F-Soft 平台和 Z3 工具对该方法进行了实验验证,结果表明,该方法在验证的精确度和效率上都有较好的效果.
2012, 23(10):2665-2678. DOI: 10.3724/SP.J.1001.2012.04185
摘要:Web Service 已经成为主要的计算资源和软件的主要存在形态.为了满足用户的各种需求,使得 Web 服务的数量快速增加,而能从大量的服务中准确地发现满足用户需求的服务,成为研究热点和难点.结合成熟的基于概念相似度的服务匹配方法,分别将用户需求和语义 Web 服务描述文档 OWL-S profile 转化为本体树,并采用分层、分类的方式分别计算对应节点的概念相似度、属性相似度和结构相似度,有效地避免了复杂的推理.根据概念相似度和结构相似度之间的关系定义一系列的约束,并利用约束对查询树进行重组,以提高服务发现的查准率和查全率.最后,给出了语义 Web 服务发现的算法,并通过开发原型系统 OWLS-CSR 进行实验,证明了该理论方法的可行性与有效性.
2012, 23(10):2679-2694. DOI: 10.3724/SP.J.1001.2012.04244
摘要:在电子政务项目建设过程中,需方通常会参与供方主导的开发活动,并由此对项目绩效产生重要影响.然而在制定需方参与活动方案时,依赖主观直觉和经验的做法一方面对制定者提出了很高要求,另一方面容易产生争议.为此,提出通过对客观存在的历史数据进行定量分析,建立需方各参与活动对于项目绩效的影响关系,进而为需方参与活动提供建议指导.使用定量方法收集25个中国电子政务项目的数据,提出一种基于变量选择的回归分析方法,建立需方参与活动与项目绩效之间关系的量化模型,并对模型的有效性进行了计量分析.分析结果显示,该模型具有良好的数学性质.进一步地,对相关软件企业进行了回访,结合模型结论对反馈结果进行综合分析,为中国电子政务项目中的需方参与活动给出若干具体建议.
2012, 23(10):2695-2704. DOI: 10.3724/SP.J.1001.2012.04178
摘要:传统的分布存储并行编译系统大多是在共享存储并行编译系统的基础上开发的.共享存储并行编译系统的并行识别技术适合 OpenMP 代码生成,实现方式是将所有嵌套循环都按照相同的识别方法进行处理,用于分布存储并行编译系统必然会导致无法高效发掘程序的并行性.分布存储并行编译系统应根据嵌套循环结构的特点进行分类处理,提出适合 MPI 代码生成的并行识别技术.为解决上述问题,根据嵌套循环的结构和 MPI 并行程序的特点,提出了一种新的嵌套循环分类方法,并针对不同的嵌套循环分别提出了相应的并行识别技术.实验结果表明,与采用传统并行识别技术的分布存储并行编译系统相比,按照所提方法对嵌套循环进行分类,采用相应并行识别技术的编译系统能够更高效地识别基准程序中的并行循环,自动生成的 MPI 并行代码其性能加速比提高了 20%以上.
2012, 23(10):2705-2719. DOI: 10.3724/SP.J.1001.2012.04197
摘要:负载模式的动态变化会影响系统度量,使得异常难以准确检测.针对此问题,提出一种基于负载模式识别、在线检测Web应用异常的方法.该方法基于在线增量式聚类算法,运行时识别动态变化的负载模式,根据特定负载模式对应的度量空间,利用局部异常因数检测异常状态,并量化异常程度,并通过学生 t 测试方法计算度量异常值,以定位异常原因.实验结果表明,所提方法能够准确识别负载模式变化,有效检测出 Web 应用典型错误所引起的异常状态,并定位异常原因.
2012, 23(10):2720-2734. DOI: 10.3724/SP.J.1001.2012.04198
摘要:关于多个 DAG 工作流在异构分布式环境下调度的研究近来有了新的进展,也解决了一些问题,但现阶段还没有考虑和解决根据不同类型 DAG 的需求按优先级进行分类,以及对不同时间到达的多个不同优先级 DAG 进行调度的问题.为解决这些问题,针对各用户对 DAG 工作流的 QoS 需求的不同,在对不同用户的 DAG 工作流进行优先级划分的基础上,首先提出了一种新的调度模型,并改进了已有的公平调度算法,解决在不同时间上被提交的具有相同优先级的多个 DAG 工作流之间调度的公平性问题.为了提高资源利用率和高优先级 DAG 尽可能小地受低优先级 DAG 的影响,又提出了一种适用于多个不同优先级 DAG 之间调度的 Backfill 算法.在新的系统模型和这两种算法的基础上,提出了一种混合调度策略.实验结果表明,这种混合调策略能够兼顾不同时间到达的多个不同类型DAG 调度需求和资源利用率的改善.另外,通过实验发现了关于两个 DAG 调度所特有的“拖尾”规律,具有进一步研究和应用的价值.
2012, 23(10):2735-2745. DOI: 10.3724/SP.J.1001.2012.04170
摘要:可重构系统是指一个系统由构件组成,随着构件被替换以及组合拓扑关系的变化,系统表现出不同的功能.针对可重构系统在形式化和重构建模方面的不足,用代数学方法对可重构构件、构件组合、可重构系统的属性和行为特征进行抽象,把构件组合定义成构件的“运算”实现,结合进程代数中算子的概念,定义了多种构件组合运算,建立了可重构系统的代数模型.在代数模型基础上,提出了重构建模和重构范式,为可重构系统提供理论支持,最后介绍了应用案例.
2012, 23(10):2746-2759. DOI: 10.3724/SP.J.1001.2012.04214
摘要:针对现有空间索引剖分结构复杂、节点重叠率高及对多维实体对象检索及运算支撑较弱等问题,构建了一种边界约束的非相交球实体对象多维统一空间索引;利用球的几何代数外积表达,提出了基于求交算子的直线-平面和直线-球面的相交判定与交点提取方法,建立了多维实体对象体元化剖分方法及包含边界约束的非相交离散球实体填充算法,实现了实体对象空间均匀、非重叠的分割,并在填充球的个数、重叠率以及对象逼近近似度等约束条件上获得了较好的平衡.定义了最小外包球生成与更新的迭代算法与包含球体积修正的批量 Neural Gas 层次聚类算法,在尽可能保证球树各分支平衡性的前提下,实现了索引层次体系的稳健构建.利用几何代数下球对象间几何关系计算的内蕴性与参数更新的动态性,实现了索引结构的动态生成与更新,进而设计了实体对象表面及其内部任意位置及区域的检索策略及基于实体索引的空间关系计算方法.基于不同实体对象的模拟实验显示,基于几何代数的实体对象索引可以有效实现多维实体对象表面及其内部任意位置及区域的快速检索,并能在有限时间内以较高的精度实现多维实体对象最近邻距离和动态实体对象相交状态的检索.相对于常用球树索引,所提出的索引方法在填充率、节点重叠率、填充误差、体元个数、层次球个数、体积百分比和时间占用等方面均具有明显优势,且不同分辨率剖分条件下的索引结构及空间关系计算精度具有更高的稳健性,可运用于具有较强时间约束下复杂多维动态场景中对象检索与空间关系计算.
2012, 23(10):2760-2771. DOI: 10.3724/SP.J.1001.2012.04176
摘要:针对互联网络中媒体语义关联内容的快速查找和聚合方面的问题,提出了一种新的面向网络的关系路由方案.该方案在命名媒体和语义关联的基础上对网络中的语义关联请求进行路由,然后快速返回关联内容.首先介绍了语义媒体模型和基于网络的关系查询模型,设计了关系路由通信协议的数据结构和算法,尤其是对关系匹配算法、路由过程以及关系请求的非完备性返回避免方法进行了重点介绍.然后,对关系路由的关键问题,如媒体命名、查询偏好以及应用等方面的问题进行了讨论和分析.最后,在实际环境中对关系路由的模型和算法进行了实验.结果表明,关系路由方法能够快速获取语义关联内容,并为分布、动态的媒体语义聚合提供了一条有效的途径.
2012, 23(10):2772-2782. DOI: 10.3724/SP.J.1001.2012.04171
摘要:网络虚拟化环境下,底层网络的透明性造成虚拟网提供商不能诊断所有的虚拟网服务故障.为解决此问题,提出了基于映射关系的虚拟网服务故障传播模型.针对故障传播模型中故障集与症状集较大、网络环境动态和噪声大而导致的已有诊断算法误报率高、时间复杂度高的问题,基于网络虚拟化环境下症状内在相关性特点,提出了一种新的基于症状内在相关性的虚拟网服务故障诊断算法 SFDoIC(service fault diagnosis algorithm based oninherent correlation among symptoms).仿真实验结果表明,SFDoIC 算法能够很好地解决底层网络透明性造成的虚拟网服务故障难以定位的问题.SFDoIC 算法可以有效地降低诊断算法的误报率,显著缩短诊断算法的运行时间.
2012, 23(10):2783-2794. DOI: 10.3724/SP.J.1001.2012.04173
摘要:针对传统网络覆盖模型仅以区域覆盖率作为评价标准,而未考察不同覆盖模型下节点能量有效性问题,在协作覆盖模型的基础上,提出了能量有效的分层协作覆盖模型 EEHCCM(energy efficient hierarchical collaborationcoverage model),并应用蚁群优化算法进行求解.该模型通过对目标区域进行分层,并优化各个层内的节点数目来实现节点能量的能耗均衡.提出了基于分层协作覆盖模型的启发式因子和全覆盖条件下节点数量的上下限的计算方法.通过Matlab仿真实验,其结果表明,应用EEHCCM模型实现目标区域节点的部署,在同等覆盖能力下,网络的生存时间可以得到较大的提升,与传统的覆盖算法相比,更适用于实际的节点部署.
陈剑洪 , 陈克非 , 龙宇 , 万中美 , 于坤 , 孙成富 , 陈礼青
2012, 23(10):2795-2804. DOI: 10.3724/SP.J.1001.2012.04183
摘要:对于公钥密码体制来说,私钥泄漏是一种十分严重的威胁.传统密码系统可以通过撤销公钥来应对私钥泄漏,但在属性基密码系统里,公钥由属性集合表示,对这些属性集合的撤销不太可行.目前,密钥隔离机制是减轻密钥泄漏所带来危害的一种有效方法.为了处理属性基密码系统中的密钥泄露问题,将并行密钥隔离机制引入到密文策略的属性基加密中,提出了密文策略的属性基并行密钥隔离加密(ciphertext policy attribute-based parallel key-insulated encryption,简称 CPABPKIE)的概念.在给出 CPABPKIE 的形式化定义和安全模型的基础上,构建了一个不需要随机预言机模型的选择ID安全的CPABPKIE方案.所提方案允许较频繁的临时私钥更新,同时可以使协助器密钥泄漏的几率保持较低,因此增强了系统防御密钥泄漏的能力.
2012, 23(10):2805-2816. DOI: 10.3724/SP.J.1001.2012.04184
摘要:属性撤销是基于属性的加密(attribute based encryption,简称 ABE)在实际应用中所必须解决的问题.在直接撤销模式下,已有的支持属性撤销的 ABE 方案只能以撤销用户身份的方式对用户所拥有的全部属性进行撤销,而无法做到针对属性的细粒度撤销.提出了直接模式下支持完全细粒度属性撤销的 CP-ABE(cipher policy ABE)模型,在合数阶双线性群上,基于双系统加密的思想构造了具体的方案,并在标准模型下给出了严格的安全性证明.该方案能够对用户所拥有的任意数量的属性进行撤销,解决了已有方案中属性撤销粒度过粗的问题.
2012, 23(10):2817-2832. DOI: 10.3724/SP.J.1001.2012.04193
摘要:传统的以单次或几组通信过程为目标进行的密钥管理性能分析的方法具有片面性,且随着网络异构程度的增加将越发复杂,分析结果的参考价值也相对较低.针对该问题,首先概括了异构传感网密钥管理框架,细化了其策略层逻辑结构,并结合 Petri 网理论,通过对库所进行能耗扩展,提出分簇结构下的密钥管理逻辑(key management logic,简称 KML)模型.随后,以带吸收壁的 Top 层密钥管理策略和 Button 层能耗模型为核心,建立了密钥管理协议的KML 模型,该模型支持多种异构性以 token 的形式参与分析和决策.最后,以低能耗协议为例,讨论了所提模型的能耗、时延和寿命的分析方法.实验结果表明,KML 模型能够有效地对协议进行仿真和分析,提供了对协议的短期性能和长期性能的合理估测,从而帮助设计者发现协议瓶颈和性能隐患,为协议改进提供参考.