摘要:偶图是由Robin Milner在2001年提出的一种基于图形的形式化理论模型,试图为普适计算提供一个设计、模拟和分析的平台以及为现有的进程代数提供一个统一的可扩展的框架.介绍了偶图的基本概念,揭示了偶图的数学基础——预范畴、范畴、s-范畴、对称偏幺半范畴之间的关系,对偶图的代数系统进行总结,简化了偶图的离散范式的表述形式,并给予证明.综述了偶图的发展及其应用概况.对偶图范畴的定义、商变换等基本理论中存在的一些问题提出讨论,指出偶图范畴应该属于小范畴而不是大范畴,并给出商变换得出的大范畴转换为小范畴的方法.最后简述了偶图模型的扩展、应用的拓广.

摘要:中介逻辑是朱梧槚先生提出的一个3-值逻辑.给出了一个命题中介逻辑,其中引入中介连接词~、反对连接词◁以及蕴涵连接词→,并且定义否定连接词.给出了一个Gentzen-型的推导系统,使得该系统关于中介逻辑的3-值语义是可靠的和完备的.

摘要:软错误是高辐照空间环境下影响计算可靠性的主要因素,结果错误(silent data corruption,简称SDC)是软错误造成的一种特殊的故障类型.针对SDC难以检测的问题,提出了一种基于不变量的检测方法.不变量是运行时刻保持不变的程序特征.在软错误发生后,由于程序受到影响,不变量一般不再满足.根据该原理,在源代码中插入以不变量为内容的断言,利用发生软错误后断言报错来检测软错误.首先,根据错误传播分析确定了检测位置,提取了检测位置的不变量;定义了表征不变量检测能力的渗透率,在同一检测位置依据渗透率将不变量转化为断言.通过错误注入实验,验证了该检测方法的有效性.实验结果表明:该检测方法具备较高的检出率和较低的检测代价,为星载系统的软错误防护提供了新的解决思路.

摘要:随着分布式计算技术的发展,以自治的服务协同与互操作为主要构造手段、结构与行为随需而变的面向服务的软件系统已成为当前主流的软件架构,分析并理解服务交互行为对于这类复杂软件系统的开发、维护和运营具有重要意义.针对面向服务的软件系统中基本构成元素Web服务的复杂交互执行行为,考虑到服务自治性及系统规模化所带来的复杂性,借鉴复杂网络建模分析方法,提出了一种考虑服务行为特征的服务动态行为生长演化模型.模型首先以真实服务的服务结构数据为基础,以服务间参数关联关系为核心,通过参数匹配建立服务结构网络作为基本连通性约束,代表可能发生交互关系的服务.然后,基于服务间的择优选择、组合交互及动态重组等特性,对面向服务的软件系统生长演化及动态执行行为进行了仿真建模.在Seekda及QWS数据集上进行了仿真实验,结果表明:与传统的软件系统的层次性结构有所不同,由自治的Web服务所构成的软件系统具有更强的模块性;与系统中个体服务演化规则,如择优连接及动态重组相比,服务结构网络的性质对系统最终形态有更重要的影响,相关结果对大规模服务软件的构建及分析具有重要的指导意义.

摘要:微博已经逐渐成为人们获取信息、分享信息的重要社会媒体,深刻影响并改变了信息的传播方式.针对微博信息传播预测问题展开综述.该研究对舆情监控、微博营销、个性化推荐具有重要意义.首先概述微博信息传播过程,通过介绍微博信息传播的定性研究工作,揭示微博信息传播的特点;接着,从以信息为中心、以用户为中心以及以信息和用户为中心这3个角度介绍微博信息传播预测相关研究工作,对应的主要研究任务分别是微博信息流行度预测、用户传播行为预测和微博信息传播路径预测;继而介绍可用于微博信息传播预测研究的公开数据资源;最后,展望微博信息传播预测研究的问题与挑战.

摘要:多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.

摘要:中文事件触发词抽取是一项具有挑战性的任务.针对中文事件触发词抽取中存在的事件论元语义信息难以获取以及部分贫信息事件实例难以抽取的问题,提出了基于语义的中文事件触发词抽取联合学习模型.首先,根据中文句子结构灵活和句法成分多省略的特点,提出了基于模式匹配的核心论元和辅助论元抽取方法,这两类论元可以较好地表示论元语义,进一步提高中文事件触发词抽取性能;其次,根据同一文档中关联事件实例间存在的高度一致性,构造了一个关联事件语义驱动的中文事件触发词识别和类型分配二维联合模型,用于抽取贫信息事件实例.在ACE 2005中文语料上的实验结果表明:与现有最好的中文事件抽取系统相比,所提出方法的性能得到了明显提升.

摘要:Pawlak教授提出的粗糙集理论是解决集合边界不确定的重要手段,他构建了边界不确定集合的两条精确边界,但没有给出用已有知识基来精确或近似地构建目标概念(集合)X的方法.在前期的研究中提出了寻找目标概念X的近似集方法,但并没有给出最优的近似集.首先,回顾了集合间的相似度概念和粗糙集的近似集R_λ(X)的构建方法,提出并证明了R_λ(X)所满足的运算性质.其次,找到了R_λ(X)比上近似集R(X)和下近似集R(X)更近似于目标概念X的λ成立的区间.最后,提出了R_0.5(X)作为目标概念的最优近似集所满足的条件.

摘要:目前,信息抽取研究主要面向肯定性信息,而自然语言文本中包含了大量否定性和不确定性信息,为了将此类信息与肯定性信息区分开,有必要针对否定性与不确定性信息抽取进行深入研究.针对这一任务,首次构建了一个16 841句的汉语语料资源,利用序列标注模型与卷积树核模型,系统地探索了各种序列化依存特征和结构化句法树特征的有效性,并提出了元决策树模型,对二者进行融合.实验结果显示,该方法在否定性和不确定性信息抽取任务上的精确率分别达到69.84%和58.57%,为相关研究打下了坚实的基础.

摘要:由于越来越多的数据具有位置和文本双重属性,空间关键词查询(spatial keyword query,简称SKQ)应运而生.一个SKQ以一个地理位置和若干关键词作为参数,返回满足空间与文本约束的结果,这些结果往往根据指定公式排列.对现有的空间关键词搜索技术进行了梳理,首先对问题进行了描述,对挑战进行了分析;然后分析了基本空间关键词搜索技术.将文献中提出的各种空间关键词查询进行了划分,对现有的查询处理技术进行分类,对每种类型的技术,从索引技术和查询算法两个方面进行了总结,并从多个角度对它们进行了比较.其后介绍了扩展空间关键词搜索技术,还介绍了与该问题相关的其他研究工作.最后指出了研究中存在的不足以及以后的研究方向.

摘要:移动对象聚集模式是指由移动对象参与的一组群体事件,通常用来预测交通系统中出现的异常现象.然而由于海量移动轨迹数据的产生,已有的研究方法难以准确、高效地挖掘特定的聚集模式.为此,提出一种基于时空图的移动对象聚集模式挖掘方法.该方法首先通过改进的空间聚类算法(DBScan)分析轨迹数据,从而获得移动对象聚类;然后,利用时空图模型代替单独存储轨迹数据的方式,用于实时观测移动对象聚类的时空变化特征.最后提出基于最大完全子图查找的聚集检索算法及其改进算法,用于查找满足时空约束的最大完全子图.基于真实大规模轨迹数据集上的实验结果表明,所提出的方法在移动对象聚集模式挖掘的准确性和高效性方面优于其他方法.

摘要:语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.

摘要:基于差分隐私保护模型,已经存在多种静态数据集上的直方图发布方法,而目前着重考虑数据流环境下的直方图发布方法却很少.由于数据流本身潜在的复杂性,直接利用现有的满足差分隐私的直方图发布方法处理数据流存在着很多不足,例如发布直方图的可用性低、发布误差大等.基于此,提出了一种基于滑动窗分割的流式直方图发布方法SHP(streaming histogram publication).该方法通过连续分割每个滑动窗中的桶计数,使其构成不同的分组.根据不同的范围计数查询敏感性,提出了3种拉普拉斯噪音添加机制以实现差分隐私保护,分别是滑动窗机制、时间点机制以及自适应抽样机制.在自适应抽样机制中,SHP算法基于当前的滑动窗,依赖于一种自适应抽样方法对下一时刻的计数进行预测,若预测值与真实值的差异小于给定的阈值则发布预测值,否则发布噪音值.该抽样方法可以有效地节省整体的隐私预算.在真实数据集上对SHP算法的可用性进行度量,结果显示,基于抽样的SHP算法的可用性高于另外两种方式.

摘要:作为一种新型网络架构,软件定义网络(software defined network,简称SDN)将网络的数据层和控制层分离,通过集中化控制和提供开放控制接口,简化网络管理,支持网络服务的动态应用程序控制.流量工程通过对网络流量的分析、预测和管理,实现网络性能的优化.在SDN中开展流量工程,可以为网络测量和管理提供实时集中的网络视图,灵活、抽象的控制方式以及高效、可扩展的维护策略,具有突出的研究意义.对基于SDN的流量工程相关工作进行综述.分别从测量的方法、应用和部署角度出发,对SDN中流量测量的基本框架、基于测量的正确态检测以及测量资源的管理进行概述.分析传统网络流量调度方案的问题,介绍SDN中数据流量和控制流量调度的主要方法.从数据层和控制层两个方面概述SDN中故障恢复方法.最后,总结并展望未来工作.

摘要:覆盖与连通问题是无线传感器网络的基本问题.研究考虑连通性的概率覆盖增强算法,构建覆盖空洞的修补半径,提出了移动距离和修补半径的关系模型.通过这个关系模型,移动节点在修补圆上选择保持连通的修补位置;根据这个移动距离和空洞面积,移动节点进一步创建空洞的优先级,选择优先级最高的空洞进行修补,节能而高效地实现覆盖增强.仿真结果表明,所提出的算法既能得到较高的覆盖率,又能保证整个网络的连通性.

摘要:车载自组织网络(vehicular ad hoc networks,简称VANETs)具有网络间歇连通、节点高速移动及动态的网络拓扑结构等特性,如何有效地实现车辆间的数据传输,成为VANETs的重大挑战.现有研究工作基于历史交通流量或历史延迟预测路段当前交通状况的方法并不可靠.此外,要实现高效的数据路由传输,配置大量路边基础设施节点(deploying roadside unit,简称RSU)是一种可行方案,但通常需要额外开销.基于城市区域长时间拥有大量地上停放车辆这一事实,提出了基于停车骨干网络的数据传输策略PBBD(parking backbone based data delivery),不需要配置任何地面基础设施,而是把地面的停放车辆组成一个虚拟的停车覆盖网络,通过该停车覆盖网实现数据的传输.为此,首先,对于每一条道路,把路边和非路边停放车辆组成一个尽可能长的停车簇,并基于这些停车簇组织城市停车骨干网络.其次,设计基于停车覆盖网络的全新数据传输算法来实现车辆间的有效数据传输.基于真实城市地图和交通数据的模拟实验结果表明,与现有的几种数据传输算法相比,PBBD能够以较低的网络传输开销和较小的传输延迟获得较高的数据传输成功率.

摘要:分析传统的匿名漫游认证协议,指出其匿名不可控和通信时延较大的不足.针对上述不足,提出异构无线网络可控匿名漫游认证协议,远程网络认证服务器通过1轮消息交互即可完成对移动终端的身份合法性验证,当移动终端发生恶意操作时,家乡网络认证服务器可协助远程网络认证服务器撤销移动终端的身份匿名性.该协议在实现匿名认证的同时,还具有恶意匿名的可控性,有效防止了恶意行为的发生,且其通信时延较小.安全性证明表明,该协议在CK安全模型中是可证安全的.相对于传统漫游机制而言,该协议更适合于异构无线网络.

摘要:随着云计算的兴起,虚拟化技术使用也越来越广泛,虚拟机正逐步取代物理机,成为应用服务的部署环境.出于灵活性、可靠性等方面的需求,虚拟机镜像急剧增长,如何高效地、经济地管理这些镜像文件已成为一个很有挑战性的研究热点.由于虚拟机镜像之间存在大量重复性的数据块,高效的去冗余方法对于虚拟机镜像管理至关重要.然而,传统的去冗余方法由于需要巨大的资源开销,会对平台中托管的虚拟机性能造成干扰,因而并不适用于云环境.提出了一种局部去冗余的方法,旨在优化镜像去冗余过程.其核心思想是:将全局去冗余变成局部去冗余,从而降低去冗余算法的空间复杂度,以达到减少操作时间的目的.该方法利用虚拟机镜像相似性作为启发式规则对虚拟机镜像进行分组,当一个新的镜像到来时,通过统计抽样的方法为镜像选取最为相似的分组进行去冗余.实验结果表明:该方法可以通过牺牲1%左右的存储空间,缩短50%以上的去冗余操作时间.

摘要:传统的基于虚拟化内核监控模型存在两个方面的不足:(1) 虚拟机监控器(virtual machine monitor,简称VMM)过于复杂,且存在大量攻击面(attack surface),容易受到攻击;(2) VMM执行过多虚拟化功能,产生严重的性能损耗.为此,提出了一种基于硬件虚拟化的安全、高效的内核监控模型HyperNE.HyperNE舍弃VMM中与隔离保护无关的虚拟化功能,允许被监控系统直接执行特权操作,而无需与VMM交互;同时,HyperNE利用硬件虚拟化中的新机制,在保证安全监控软件与被监控系统隔离的前提下,两者之间的控制流切换也无需VMM干预.这样,HyperNE一方面消除了VMM的攻击面,有效地削减了监控模型TCB(trusted computing base);另一方面也避免了虚拟化开销,显著提高了系统运行效率和监控性能.