摘要:主要研究带mismatch的高阶进程演算的公理化问题.首先,建立存在mismatch时高阶进程的开弱高阶互模拟理论,证明了等价关系、同余性等重要性质;其次,沿用线性的方法,构建得到带mismatch的有限进程上的公理系统;最后,基于对开弱高阶互模拟的刻画,证明了该公理系统的完备性定理.该工作为带mismatch的高阶进程上互模拟判定的有效算法的设计与实现,进而为相关的应用建模工作提供了理论借鉴.

摘要:提出使用事件自动机对C程序的安全属性进行规约,并给出了基于有界模型检测的形式化验证方法.事件自动机可以规约程序中基于事件的安全属性,且可以描述无限状态的安全属性.事件自动机将属性规约与C程序本身隔离,不会改变程序的结构.在事件自动机的基础上,提出了自动机可达树的概念.结合自动机可达树和有界模型检测技术,给出将事件自动机和C程序转化为可满足性模理论SMT(satisfiability modulo theory)模型的算法.最后,使用SMT求解器对生成的SMT模型求解,并根据求解结果给出反例路径分析算法.实例分析和实验结果表明,该方法可以有效验证软件系统中针对事件的属性规约.

摘要:已有的Web服务QoS(quality of service)度量方法由于无法对用户偏好的模糊性予以准确量化,以及对候选服务QoS属性数据分布特征的忽视,导致其度量结果不准确.为此,提出了一种综合考虑主客观权重的Web服务QoS度量算法.该算法利用自适应用户偏好的主观权重计算方法和服务潜能保障的客观权重计算方法,从主观和客观两个角度进行QoS度量,以保障度量结果在符合用户偏好的基础上能够准确地反映服务的整体性能.理论分析和基于QWS真实数据集的实验结果表明,所提出的方法能够准确地获得Web服务QoS的度量结果.

摘要:指针分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础.在基于包含的指针分析算法研究的基础上,对Narse优先权约束评估算法中存在的冗余约束评估和优先权评估模型计算开销较大的问题进行分析,以指针的指向集更新信息确定约束评估的候选集,提出了基于指向更新的约束评估算法.采用约束语句间的解,引用依赖和标量依赖构建约束依赖图,通过依赖关系确定约束评估的优先权,提出了基于约束依赖图的优先权算法,简化了既有算法中复杂的优先权评估模型,进一步给出了优化后算法的整体框架.在基准测试集SPEC 2000/SPEC 2006上进行实验,其结果表明,该算法与Narse优先权算法相比,在时间开销和存储开销上都有明显的性能提升.

摘要:软件在其生命周期中不断地发生变更,以适应需求和环境的变化.为了及时预测每次变更是否引入了缺陷,研究者们提出了面向软件源代码变更的缺陷预测方法.然而现有方法存在以下3点不足:(1) 仅实现了较粗粒度(事务级和源文件级变更)的预测;(2) 仅采用向量空间模型表征变更,没有充分挖掘蕴藏在软件库中的程序结构、自然语言语义以及历史等信息;(3) 仅探讨较短时间范围内的预测,未考虑在长时间软件演化过程中由于新需求或人员重组等外界因素所带来的概念漂移问题.针对现有的不足,提出一种面向源代码变更的缺陷预测方法.该方法将细粒度(语句级)变更作为预测对象,从而有效降低了质量保证成本;采用程序静态分析和自然语言语义主题推断相结合的技术深入挖掘软件库,从变更的上下文、内容、时间以及人员4个方面构建特征集,从而揭示了变更易于引入缺陷的因素;采用特征熵差值矩阵分析了软件演化过程中概念漂移问题的特点,并通过一种伴随概念回顾的动态窗口学习机制实现了长时间的稳定预测.通过6个著名开源软件验证了该方法的有效性.

摘要:信息聚合是信息处理过程中的基本手段,主要讨论若干聚合算子的性态.首先,从广义伴随对的角度讨论了广义聚合算子的性质.从聚合算子A出发,给出两种不同的方法,构造了大于(小于)等于A的新的聚合算子;其次,对于处理双极信息用到的聚合算子、双极t-模和双极蕴涵做了讨论,得出了这两个双极聚合算子可分解为两个单级聚合算子的条件.在此条件下即清晰可见聚合双极信息时对正信息及负信息的聚合过程.这对提取特定信息具有极其重要的意义.

摘要:篇章是论元经过语义关联和结构化组织形成的自然语言文体.篇章分析研究的核心任务之一是解释论元的语义关系,其中,显式关系因具有直观线索而易于检测,目前检测精度高达90%;相对而言,隐式关系因缺乏直观线索而难于检测,目前精度仅约40%.针对这一问题,基于一种“论元平行则关系平行”的假设,并利用显式篇章关系易于检测的特点,通过平行论元的识别与平行关系的消歧,实现了一种显式关系平行推理隐式关系的隐式篇章关系检测方法.利用标准宾州篇章关系树库(Penn discourse TreeBank,简称PDTB)对这一检测方法进行评测,结果显示,精确率提升达17.26%.

摘要:伴随着无线通信技术和智能移动终端的快速发展,基于位置的服务(location-based services,简称LBS)以其移动性、实用性、随时性和个性化的特点,在军事、交通、物流等诸多领域得到了广泛的应用,成为最具发展潜力的移动增值业务之一.在一个基于位置的网络服务推荐框架的基础上,给出了一种基于位置的移动用户偏好相似度计算方法,同时证明了其满足近邻相似测度的一般性质;然后,提出一种符合社会学概念的信任值计算方法.把它们应用于基于移动用户位置的网络服务推荐过程中,从而形成了一种基于移动用户位置的网络服务推荐方法.该方法有效地提高了网络服务推荐的准确性和可靠性,同时缓解了推荐过程中可能存在的数据稀疏性以及冷启动问题.最后,通过公开的MIT数据集验证了该推荐方法的准确度和可行性.

摘要:基于闪存的固态硬盘(solid state driver,简称SSD)已经广泛应用于各种移动设备、PC机和服务器.与磁盘相比,尽管SSD具有数据存取速度高、抗震、低功耗等优良特性,但SSD自身也存在读写不对称、价格昂贵等不利因素,这使得SSD 短期内不会完全取代磁盘.将SSD和磁盘组合构建混合系统,可以发挥不同的硬件特性,提升系统性能.基于MLC型SSD和SLC型SSD之间的特性差异,提出了一种闪存敏感的多级缓存管理策略——FAMC.FAMC将SSD用在内存和磁盘之间作扩展缓存,针对数据库系统、文件管理中数据访问的特点,有选择地将内存牺牲页缓存到不同类型的SSD.FAMC同时考虑写请求模式和负载类型对系统性能的影响,设计实现对SSD友好的数据管理策略.此外,FAMC基于不同的数据置换代价提出了适用于SSD的缓冲区管理算法.基于多级缓存存储系统对FAMC的性能进行了评测,实验结果表明,FAMC可以大幅度降低系统响应时间,减少磁盘I/O.

摘要:时态数据索引是实现时态数据有效管理的关键技术之一.讨论了一种时态数据结构及其在时态数据索引上的应用.常规的时态数据管理技术多基于代数框架.提出了一种基于拟序关系的时态数据结构,该结构能够像常规关系数据那样实现“一次一集合”的数据操作,并可通过多线程提高查询效率.在此基础上,研究了一种时态数据索引TQOindex.首先,提出时间期间集合上拟序关系和线序划分概念,讨论了线序划分的最优(最小)性质和构建算法,并在最小线序划分框架内研究时态拟序结构基于增量式更新的插入和删除算法.其次,研究了时态拟序结构应用——引入基于拟序扩展集的时态数据索引TQOindex.该索引适用于磁盘(外存)数据管理,可在常规数据库平台上有效使用.其增量式更新机制可应用于“大数据”的动态索引技术.另外,对TQOindex进行了基本仿真,实验结果表明了该工作的可行性和有效性.提出的时态拟序数据结构着眼于新型数据,如语义数据、XML数据和移动对象数据中时态处理与整合机制,相应的工作具有较为广泛的应用扩展性.

摘要:信息网络无处不在.通过把网络中的对象抽象为点,把对象之间的关系刻画为边,相应的信息网络就可以用图来表示.图中结点相似度计算是图数据管理中的基本问题,在很多领域都有运用,比如社会网络分析、信息检索和推荐系统等.其中,著名的相似度度量是以Personalized PageRank和SimRank为代表.这两种度量本质都是以图中的路径来定义,然而它们侧重的路径截然不同.为此,提出了一个度量SuperSimRank.它不仅涵盖了这些路径,而且考虑了Personalized PageRank和SimRank两者都没有考虑的路径,从而能够更加体现出这种链接关系的本质.在此基础上对SuperSimRank进行了理论分析,从而提出了相应的优化算法,使得计算性能从最坏情况O(kn⁴)提高到O(knl).这里,k是迭代次数,n是结点数,l是边数.最后,通过实验验证了SuperSimRank优于SimRank和Personalized PageRank,同时验证了优化算法在各种情况下都是有效的.

摘要:传统的基于几何区域分割的报文分类算法在空间切分时,通常只采用一种切分方法,并不会根据每个域的特点选取不同的对策.提出了一种采用混合切分法的报文分类算法HIC(hybrid intelligent cuttings).首先,按照IP前缀长度将规则集分组;然后,在每个分组中根据当前切分域的特点,分别对IP域和端口域采用比特位切分法和精确投影点切分法实现空间分解;最后,构建混合切分结构的决策树.仿真结果表明,HIC算法具有较好的规则集适应性,其时间性能与空间性能分别比代表算法EffiCuts提高了46%和74%.

摘要:针对物联网感知层调度问题,研究和分析三维空间基于四锚点节点定位实解个数的分类问题.利用不等式机器证明理论和研究成果以及不等式机器证明软件DISCOVERER,分析了四锚点定位在特定情形下的实解分类判别问题.首先给出定位问题的数学描述,将传统定位方法中存在的非线性方程组转化为不等式约束的多项式方程组;然后,利用不等式机器证明理论和工具初步探讨了方程组在部分参数固定情况下的解的分类,给出了这种情况下的解的完全分布.分析结果表明:空间四锚点定位存在多解问题,给出的多解分类判别条件对实际应用具有指导作用,对提高节点布局和精确信息感知具有参考价值.

摘要:802.11无线局域网技术的广泛普及,给无线室内定位系统带来了良好的发展契机.提出了一种基于支持向量回归的802.11无线室内定位方法.该方法主要包括离线训练和在线定位两个阶段.离线阶段的主要工作是得到精确的位置预测模型;在线阶段的主要工作是根据移动设备的接收信号强度(received signal strength,简称RSS)进行在线定位.由于存在室内环境复杂、信道拥塞、障碍物影响和节点的通信半径有限等问题,移动设备的接收信号强度易受干扰,复杂多变.针对以上问题,离线阶段对接收信号强度信息进行统计分析,得出数据过滤规则,对训练数据集进行过滤,以此提高训练样本质量,从而提高支持向量回归预测模型的质量.在线阶段使用连续K次测量定位法获取信号强度信息,保证训练样本与在线输入信息之间的一致性,提高最终的定位精度.通过实验对该定位方法进行了综合对比分析,实验结果表明:与常用概率定位法、神经网络法相比,该方法具有更高的定位精度,同时具有对移动设备的存储容量及其计算能力要求较低的特点.

摘要:针对已有检测方法不能有效地检测未知推荐攻击的问题,提出了一种基于仿生模式识别(bionic pattern recognition)的检测方法.首先,依据项目流行度划分项目到不同的窗口,把用户对窗口内项目的评分视为随机事件发生.在此基础上,利用信息熵(information entropy)提取评分分布特征作为检测推荐攻击的通用特征.然后,在特征空间中,利用仿生模式识别技术覆盖真实概貌样本,将覆盖范围外的测试数据判为推荐攻击.在MovieLens数据集上进行实验,结果表明,该方法在检测未知推荐攻击时具有较高的命中率和较低的误报率.

摘要:针对密度非均匀Ad Hoc网络,提出了一种基于预留的时隙混合类MAC——RTV协议.该协议将业务区分为预留和非预留,以提供不同质量的接入传输服务.通过时延调整预留算法来满足多种预留业务的不同时延要求.同时,通过预留机制解决了TDMA技术不适应于密度非均匀网络的问题.最后,通过数学建模分析得到了协议的时隙利用率和系统吞吐量.仿真实验结果表明:在密度非均匀的大型Ad Hoc网络中,RTV协议可以为混合业务的传输提供时延保障,并在时隙利用率和吞吐量方面呈现出较好的性能.

摘要:提出了基于粗糙集模糊聚类与差分免疫克隆聚类的图像分割算法.该算法在差分免疫克隆聚类算法的基础上,通过引入粗糙集模糊聚类,将差分免疫克隆聚类算法中的硬聚类变成模糊聚类,从而获得更丰富的聚类信息.具体来说,由于粗糙集的优势是处理不确定的数据,因此,加入粗糙集模糊聚类后更有利于算法解决不确定性问题.通过对9幅图像分割实验结果与4种算法的对比,验证了该算法在聚类性能稳定性方面的优越性,结果还同时证明了该算法具有更高的分割正确率和更好的分割结果.

摘要:由于视频编码技术趋向于采用越来越复杂的分块模式,多模式决策技术也随之成为一种非常重要的编码技术.多模式决策的优劣不仅会大幅度地影响视频编码的计算消耗,而且也对编码性能的高低起到关键的作用.为使多模式决策在计算能力相差悬殊的平台上都能获得优化的率失真性能,给出一种计算复杂度自适应的优化多模式决策算法.首先,利用视频序列中不同宏块模式间的时空相关性,预测这些宏块多模式决策后的拉格朗日代价和计算复杂度的斜率(Lagrangian cost and complexity slope,简称J-C slope).J-C slope越大,说明在该宏块上的模式决策消耗每单位的计算资源可以获取的率失真收益越多.在计算资源有限的情况下,多模式决策应该按照J-C slope的大小顺序执行,也就是性价比优先的顺序,以便保证计算资源优先分配给率失真收益大的宏块.另外,还通过建立J-C slope阈值与实际计算复杂度的关系模型,设计了一种根据给定计算约束自适应调整计算复杂度的算法.根据实验结果,该方法不仅可以准确地控制多模式决策的计算复杂度,而且还能在不同的计算约束下获得优化的率失真性能.

摘要:随着虚拟化技术的发展与普及,越来越多的企业将关键业务系统部署到了虚拟化平台上.虚拟化技术降低了企业的硬件和管理成本,但同时也给系统的可靠性带来了严峻挑战.传统的方法通过运行时系统状态备份的方法来提高系统的失效恢复能力,但该方法会引入了巨大的系统开销.提出了一种基于隐马尔可夫模型的系统失效恢复性能优化方法.通过对系统运行时状态的预测分析,计算系统未来运行状态的概率趋势,并在运行过程中动态调整系统失效恢复功能与正常业务功能之间的资源分配,从而降低了系统的运行时性能开销,提高了业务系统服务能力.实验分析显示,该方法可以在保障系统可靠性的同时有效地降低系统的性能开销,在系统运行状态稳定的情况下,最高可以降低2/3的系统响应时间.

摘要:随着大数据处理的深入发展,系统单位时间内产生的数据日趋庞大,数据间的关联关系日趋复杂,这使得传统的“存储-查询”或者“发布-订阅”的方式无法很好地满足诸如故障监控、股票分析、医疗及生命保障等对大数据具有实时处理需求的系统.复杂事件处理技术实现的是将用户对特定的事件序列的查询需求映射到特定识别结构上.该结构从多个持续的数据流中分析并提取满足特定模式的事件序列.该技术能够很好地支持对大量数据进行实时在线分析.但由于在数据处理的过程中,系统不可能预置全部的查询语义,许多系统在使用过程中会需要使用新的语义,以查询新产生的模式.因此,一种支持扩展的语义的复杂事件处理模型是非常必要的.同时,现有的复杂事件处理模型仅针对某几类特定的查询进行描述以及优化,对整体模型缺乏统一描述,导致许多模型在多规则复杂查询的情况下效率欠佳.针对上述问题,提出了基于算子的可扩展复杂事件处理模型.该模型能够良好地支持现有的各类查询语义,具有较快的识别速度.基于该模型的形式化描述,对系统在识别过程中的性能消耗进行了详细分析,给出了模型构造最优算法.通过实验验证了算子模型优化方案的正确性.实验结果表明,经过优化后的树结构事件处理速度比开源复杂事件处理引擎Esper快3倍以上.