摘要:分析了语义Web语义表示理论的研究现状及存在的问题,提出了一种新的面向语义Web语义表示的模糊描述逻辑FSHOIQ(fuzzy SHOIQ).给出了FSHOIQ的语法和语义,提出了FSHOIQ的模糊Tableaux的概念,给出了一种基于模糊Tableaux的FSHOIQ的ABox约束下的可满足性推理算法,证明了可满足性推理算法的正确性.提出了FSHOIQ的TBox扩展和去除方法,并证明了FSHOIQ的TBox约束下的包含推理问题可以转化为ABox约束下的可满足性推理问题.FSHOIQ为语义Web表示和推理模糊知识提供了理论基础.

摘要:模型检验和精化检验是两种重要的形式验证方法,其应用的主要困难在于如何缓解状态爆炸问题.基于分而治之的思想进行组合模型检验和组合精化检验是应对这个问题的重要方法,它们利用系统的组合结构对问题进行分解,通过对各子系统性质的检验和综合推理导出整个系统的性质.在一个统一的框架下对组合模型检验和组合精化检验作了系统的分析和归纳,从模块检验的角度阐述了上述两种组合验证方法的原理及其相应的组合验证策略.同时总结了各类问题的复杂性,并对上述两种方法作了比较分析,揭示了它们之间的内在联系.最后展望了组合模型检验与组合精化检验的发展方向.

摘要:研究了基于量子逻辑的自动机理论(简称l-值自动机理论)的拓扑性质.给出了successor算子和source算子的另一种定义,讨论了successor算子、source算子和l-值子自动机之间的关系,得到了successor算子、source算子和l-值子自动机的某种等价性.进一步描述了由successor算子、source算子和l-值子自动机来构造拓扑.得出了successor算子、source算子和l-值子自动机的一些基本性质,证明了在&关于(分配时,successor算子、source算子以及l-值子自动机的某些特殊性质.因而得到了由它们构造拓扑的一个较弱的条件,并且澄清了三者构造拓扑时的等价性.

摘要:针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0＜m/N＜1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN²)和O(Nlog^(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.

摘要:从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.

摘要:提出了一种基于方向性天线的分布式拓扑控制算法,可以同时通过调整网络中各节点的发射功率和改变节点天线的方向来对网络的拓扑进行控制,每个节点逐渐增大它的发射功率直到该节点在其方向性天线的每个扇区内找到足够数量的邻节点为止.在这种基于方向性天线的分布式拓扑控制算法的基础上又使用了两种不同的拓扑平面化优化算法,进一步删除了拓扑图中多余的交织边,使得网络最终的结构为一幅平坦图.由于每个节点使用了较低的发射功率以及算法形成的网络拓扑图中的平均节点度数较小,从而提高了整个网络的使用寿命,减少了节点间的干扰.仿真结果充分说明了算法的有效性.

摘要:将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.

摘要:以规划领域中的动作为研究对象,提出了描述动作前提条件和效果之间关系的方法,定义了动作前提和效果之间的基本关系:直接伴随关系、条件伴随关系和直接阻碍关系等,这些基本关系反映了规划动作中所隐含的领域知识.对动作效果的基本关系,定义了进行关系组合的运算,产生出间接阻碍关系和绝对阻碍关系.间接阻碍关系反映出动作前提条件的传递性;绝对阻碍关系表达出实现一个谓词对其他谓词实现的影响.最后给出动作效果关系在规划求解过程中的具体运用,这些动作效果关系为目标实现顺序的排序、目标状态可解性的判定以及动作选择策略的优化等提供了必要的理论依据.

摘要:引入了梯形的一个仿射不变量,并利用这个不变量,建立了梯形的相似不变量与摄像机内参数之间的约束关系.基于这个约束关系,利用摄像机内参数的知识或梯形相似不变量的知识,可以线性确定摄像机的内参数、运动参数和梯形的相似不变量.由于梯形是由一对平行线段唯一确定的,平行线段在许多场景中经常出现,因而该方法有很广泛的适用性.实验结果表明了该算法的有效性.该工作提供了一个基于平行性约束的框架,以往的基于平行四边形、平行六面体的方法都可以纳入到这个框架中.

摘要:检测器生成是非选择算法的关键步骤.已有检测器生成算法在生成检测器时存在"漏洞"区域和冗余检测器问题.提出了一种检测器长度可变的检测器生成算法,不仅可以消除"漏洞"区域,还可以通过相应的检测器优化算法减少冗余检测器,进而提高检测器生成效率和检测效率.对算法进行了分析和实验证明,结果表明,该算法比传统的非选择算法及r可变的非选择算法具有更好的性能.

摘要:针对现有入侵检测算法中存在着对不同类型攻击检测的不均衡性以及冗余或无用特征导致的检测模型复杂与检测精度下降的问题,提出了一种基于改进多目标遗传算法的入侵检测集成方法.利用改进的多目标遗传算法生成检测率与误报率均衡优化的最优特征子集的集合,并采用选择性集成方法挑选精确的、具有多样性的基分类器构造集成入侵检测模型.实验结果表明,该算法能够有效地解决入侵检测中存在的特征选择问题,并在保证较高检测精度的基础上,对不同类型的攻击检测具有良好的均衡性.

摘要:P2P(peer-to-peer)的组织模式已经成为新一代互联网应用的重要形式,它为应用带来了更好的扩展性、容错性和高性能.P2P存储系统一直是研究界所关注的热点,被认为是P2P最具前途的应用之一.数据的持久存储是制约P2P存储系统发展的关键问题,也是其研究的难点.综述了P2P存储系统及数据持久存储相关技术的研究现状.首先概述了P2P存储系统的基本技术组成及其在不同应用环境中的优势,并介绍了数据冗余、数据分发、错误检测和冗余数据维护等多种持久存储的基本技术.在一个P2P存储系统研究框架下,介绍了目前知名的P2P存储系统及其使用的持久存储技术.对各种技术进行了详细综述和对比讨论,分析了各种技术的适应环境及优劣,指出了存在的问题和未来研究的方向.

摘要:XML规范已成为当前网络应用(包括数字图书馆、Web服务以及电子商务)中事实上的数据表达、交换的标准.针对XML数据的查询在当前XML数据管理研究中占有重要的地位,也是当前XML数据处理研究领域的热点方向,相关的研究文献有很多.根据查询模式描述的不同,将当前XML查询技术归入两大类:XML Query方式和XML IR方式.后者又进而可分以为3个子类:XML IR/keyword方式、XML IR/fragment和XML IR/query方式,并从中挑选出3个研究者关注的问题进行了简述,它们是:Twig查询模式的处理、SLCA(smallest lowest common ancestor)节点的获取以及对所获取的XML片段相似性的度量.以方便普通用户使用为准则探讨了相关XML查询技术的优、缺点,将如下4个问题作为需要进一步关注的研究内容:结构化关键字查询及相应的结构相似性度量方法,如何消除XML Query查询处理模式(包含XML IR/query)和XML IR/keyword查询处理模式间数据冗余的问题,XML Query查询方式的理论探讨及其实现以及针对特定应用的XML数据的有效管理.

摘要:在基于高维索引技术的相似性查询处理中,通常通过过滤那些不包含任何查询结果的非活动子空间来不断缩减搜索空间.但是在活动子空间中,有些可能根本就不包含任何查询结果,这样的活动子空间被称为假活动子空间.显然,查询处理性能会随着假活动子空间访问次数的增加而下降.这一问题在高维数据情况下将会变得更加严重,实验显示出随着维数的增加,假活动子空间的访问次数也会增加.为了解决这一问题,提出了一种空间映射方法来减少这种不必要的访问.对于一个给定的查询,可以通过在映射空间内进一步精炼该查询来过滤假活动子空间.为了提高映射空间内查询精炼的处理效率,提出了一个最大间隙空间映射策略--MaxGapMapping.基于这种映射方法,设计并实现了一种新的索引结构--MS-tree,给出了索引的构建算法和范围查询处理算法.最后对MS-tree及其他索引结构的性能进行了详细的比较和分析.

摘要:如何快速、有效地处理twig形式的查询是XML查询处理的关键问题,通过过滤与查询无关的元素可以减少查询中需要处理的元素数目,从而提高查询的执行效率.提出一种扁平结构索引F-Index,能够快速过滤所有与查询无关的索引结点,进而过滤掉查询无关的元素,在处理深度嵌套的复杂结构XML文档时具有很大的优势.提出一种新的查询算法,能够有效处理过滤后剩余元素的匹配问题.基于不同数据集的实验表明,使用F-Index进行过滤可以极大地提高查询处理的性能.

摘要:对等计算数据管理中的一个重要问题是如何有效地支持多维数据空间上的相似性搜索.现有的非结构化对等计算数据共享系统仅支持简单的查询处理方法,即匹配查询处理.将近似技术和路由索引结合在一起,设计了一种简单、有效的索引结构EVARI(扩展近似向量路由索引).利用EVARI,每个节点不仅可以在本地共享的数据集上处理范围查询,而且还可以将查询转发给最有希望获得查询结果的邻居节点.为了建立EVARI,每个节点使用空间划分技术概括本地的共享内容,并与邻居节点交换概要信息.而且,每个节点都可以重新配置自己的邻居节点,使得相关节点位置相互邻近,优化了系统资源配置,提升了系统性能.仿真实验证明了该方法的良好性能.

摘要:针对大量数据副本所带来的资源管理问题,提出一种基于有限编码的多副本分簇管理方法.在该方法中,根据单副本复制产生新副本的过程对副本分级和分簇,通过定义"副本级别+副本顺序"的编码规则对划分后的副本进行编码和组织,并依据编码规则对由于副本的动态调整(增加或撤消)而引起的簇的动态变化进行有效管理.通过该方法,在大量副本之间建立局域集中、广域对等的管理模式,再结合定义的"最小更新传播时间"可以降低大量副本的一致性维护开销.讨论了方法中编码规则与副本规模之间的关系,以及副本失效和恢复时的解决方法.性能测试结果表明,该方法能够有效组织大规模的数据副本,具有较好的可扩展性,对适度的结点失效不敏感,适合更新频繁的应用.

摘要:通过对数据时态特性及其对事务调度的影响进行分析,提出了基于数据时态特性的实时事务并发控制算法.该算法根据数据截止期及事务的执行时间估算,改进了事务的验证规则,对事务的提交顺序进行调整,提高了系统的实时性能.理论分析与实验结果表明:该算法降低了事务重启个数及超截止期百分率,性能要优于已有的实时并发控制算法.

摘要:车用自组织网络--VANET(vehicle ad-hoc network)作为移动自组织网络和传感器网络在道路交通领域的应用,不具备完整协议体系结构,没有专门的传输控制协议.为提供VANET传输协议设计参考,研究了VANET传输协议设计应具备的目标和要素.首先介绍了VANET的特点、研究内容及其传输控制所面临的挑战.然后提出了无线传输协议的分类方法,使用分析和比较的方式讨论了各类无线传输协议用于VANET的利弊,并针对VANET应用及特性提出了VANET传输控制协议设计目标和设计要素.最后展望了VANET传输控制未来的研究方向.

摘要:基于强化学习的方法,提出一种无线多媒体通信网适应带宽配置在线优化算法,在满足多类业务不同QoS(quality of service)要求的同时,提高网络资源的利用率.建立事件驱动的随机切换分析模型,将无线多媒体通信网中的适应带宽配置问题转化为带约束的连续时间Markov决策问题.利用此模型的动态结构特性,结合在线学习估计梯度与随机逼近改进策略,提出适应带宽配置在线优化算法.该算法不依赖于系统参数,如呼叫到达率、呼叫持续时间等,自适应性强,计算量小,能够收敛到全局最优,适用于复杂应用环境中无线多媒体通信网适应带宽配置的在线优化.仿真实验结果验证了算法的有效性.

摘要:安全性和灵活性是各种改进的BLP模型追求的目标.如何在保持安全性的前提下增加BLP模型的灵活性,一直是安全操作系统研究人员研究的重点.安全模型是系统设计的基础,如果在系统中实现了不安全的"安全模型",其后果是严重的.结合多级安全(MLS)的核心思想,通过实例列举的方式深入分析了两个改进的BLP模型--DBLP(dynamic BLP)和SLCF(security label common framework).尽管这两个模型都提出了在系统运行时动态地调整主体安全级的规则,但是分析表明,它们还是不安全的.在这两个模型的规则控制下,特洛伊木马可以通过显式地读和写操作将高安全等级的信息泄漏给低安全等级的主体,从而违反了多级安全(MLS)策略.研究结果为人们避免选用不安全的模型提供了有意义的理论支持.

摘要:随着网格计算、普适计算、P2P计算、Ad Hoc等大规模的分布式应用系统的深入研究,系统表现为由多个软件服务组成的动态协作模型.在这种动态和不确定的环境下,PKI(pubic key infrastructure)中基于CA(certificate authority)的静态信任机制不能适应这种需求,动态信任模型是新的研究热点.分析了动态信任关系的相关概念、主要问题和研究方法;选取新的、典型的动态信任模型及其使用的数学方法进行评述,并进行了各种算法的比较性总结;分析了目前研究中的问题,并展望了其未来的发展方向.研究表明,动态性是信任关系量化与预测的最大挑战.今后的工作重点是对信任动态性的本质属性作进一步的理论研究,为实际应用提供坚实的理论基础.

摘要:TLS(transport layer security)协议的基本设计目标是为两个通信实体之间提供数据的保密性和完整性.由于在传输层安全握手协议中最耗费计算资源的步骤是服务器RSA解密运算,优化的批处理的RSA方法提出可以用于加速TLS会话的初始化.首先指出了以前的批处理方法由于要求多证书实现而实用性不强.然后提出了单一证书策略的方法,从而克服了这一问题.还提出结合用户对于因特网服务质量的要求优化了批处理参数.为了选择优化的批处理的参数,不仅考虑了服务器的性能,而且还考虑了客户可容忍的等待时间.通过分析并在阐述平均排队时间、批处理服务时间和系统稳定性的基础上提出了一种新颖的优化批处理调度算法,已部署在服务器上.最后通过分析和模拟两种方法验证了所提出方案的实用性和有效性.

摘要:提出一种完全基于GPU(graphics processing unit)的实时深度图像绘制流程.该方法利用GPU的并行计算特性对深度图像的绘制过程进行加速.推导出一种在vertex shader上进行的三维前向映射方法,对输入像素进行前向映射,以得到更高的绘制性能,并利用图形硬件流水线的光栅化功能高效地进行图像的插值重构,以得到连续无洞的结果图像.在pixel shader上进行逐像素的光照计算,生成高品质的光照效果.实验表明,该方法可以高速地进行满屏绘制,准确地保留物体轮廓信息和正确的遮挡关系.还实现了基于该方法的实时漫游系统.该系统能够实时地绘制多个基于柱面深度图像表示的对象,并能对其进行视相关的动态LOD(level of detail)操作.

摘要:提出了一种基于测地线的多边形网格模型的约束变形方法.首先给定一系列的变形约束源(可以是点、线或者面)以及约束源的有效半径及变形目标(偏移量、缩放比例、旋转轴和旋转角度),然后通过计算三角形网格的各顶点到约束源的测地距离来确定各顶点的场值,这个场值将作为变形的权值.在基于欧氏距离的传统约束变形中,对某一约束区域的变形往往导致对约束源附近区域不需要的变形结果,而利用测地距离来计算各点的变形权值,可以很好地避免这种现象的出现.实验结果表明,这种变形方法是直观而且有效的.