摘要:已有的Petri网化简方法需将网的局部结构与化简规则作逐一的比对,步骤较为繁琐,并且所提供的方法不适合于带抑止弧的网.采用一种与传统方法不同的化简思路,首先将网划分为若干个最大无圈子网,将每个最大无圈子网表达为若干个逻辑式.用逻辑代数来完成逻辑式的化简,最后将其结果还原为Petri网回嵌到原网中,完成整个网的化简.给出了寻找最大无圈子网、最大无圈子网的化简算法以及相关的证明.该方法将化简范围扩展到了带抑止弧的无回路的网或网的局部.

摘要:扩展模糊描述逻辑是对描述逻辑的一种模糊扩展,支持对复杂模糊知识的表示和推理,但该逻辑缺乏支持术语公理约束的推理算法.提出扩展模糊描述逻辑EFALC_R+(extended fuzzy attributive concept description language with complements and transitive roles)的受限TBox(terminological box)描述术语公理,给出受限TBox约束下的EFALC_R+推理算法,并对该算法进行优化,证明优化后的算法是正确完备的,时间复杂性不超过指数,最后证明受限TBox约束下的EFALC_R+推理问题是指数时间完全问题.优化算法的最坏时间复杂性已达到该问题推理算法的复杂度下界,是实现术语公理约束下模糊知识库推理的有效算法.

摘要:定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F("Future")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X ("Next")算子的逻辑、含有U("Until")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).

摘要:Web Services正逐渐成为主流的平台独立的软件构件,并广泛地存在于INTERNET分布式环境中,通过组装Web Services生成系统的开发方法正在逐步引起人们的关注并受到重视,但目前还没有提出一套相对成熟的、系统化的组装方案用于指导Web Services组装系统的整个开发过程.将特征模型作为贯穿整个Web Services组装过程的模型工具,利用它驱动Web Services组装系统的需求分析、流程建模、组装、部署和执行,提出了"特征模型驱动的Web Services组装"解决方案,并结合一个具体的实例对FWSC(feature model driven Web Services composition)方案的基本思想、原理以及关键步骤进行了介绍.该工作可以有效地提高Web Services组装系统的建模、开发速度和质量,并增强Web Services组装系统在需求发生变化时的动态调整和演化能力.

摘要:Servlet缓存能够有效地提高Servlet容器的吞吐量,缩短用户请求的响应时间.然而,Servlet缓存的性能受到缓存替换算法的影响.Servlet容器中的Servlet对应着一定的业务功能,挖掘Servlet之间的业务关联来指导缓存替换算法的设计可以提高Servlet缓存的命中率,进而提高Servlet容器的性能.然而,目前常见的LRU(least recently used),LFU(least frequently used),GDSF(greedy dual size frequency)等缓存替换算法均没有考虑上述问题.将Servlet对应的业务关联定义为Servlet容器序列模式,并提出k步可缓存转移概率图的概念加以表示,给出了序列模式发现算法KCTPG_Discovery.最后,基于Servlet容器序列模式设计了缓存替换算法KP-LRU(k-steps prediction least recently used)和KP-GDSF(k-steps prediction least frequently used).实验结果表明,KP-LRU与KP-GDSF算法比对应的LRU算法和GDSF算法具有更高的缓存命中率,有效地提高了Servlet容器的性能.

摘要:二进制翻译可以用于解决遗产代码的迁移问题,也可以实现不同硬件平台之间软件的通用.如果源平台通过标志位进行条件跳转,那么如何处理标志位就成为翻译中的一个重要问题,对翻译的代码质量起着决定性作用.提出标志位线性分析算法,复杂度为线性,基本上能够消除所有的标志位冗余计算,提高了动态执行的效率.基于动态profiling技术,消除了间接跳转的基本块标志位冗余计算.分析了spec 2000中的大部分整点测试例子,实验结果表明,EfLA(Eflag linear analysis)算法对于大运算量的程序是非常有效的.

摘要:TRISO-Model(tridimensional integrated software development model)是为处理软件开发的复杂性和动态性而提出的三维集成软件开发方法学,其中,多维模型之间的语义一致性维护以及对模型应用中公共操作部分的重用,提出了基于一致语义进行模型管理的需求.给出了基于MDA(model driven architecture)进行模型管理的方法MDA-MMMethod(MDA based model management method),应用MDA的4层模型管理结构,基于MDA核心标准MOF(meta object facility)所提供的公共语义基础管理模型和元模型,MDA-MMMethod支持各种MDA模型操作标准实现在TRSIO-model应用中的重用.开发了相应的支持系统MDA-MMSystem(MDA based model management system),应用于SoftPM的项目实践中.与传统方法相比,模型应用的开发效率得到了显著提高,同时降低了开发成本.最后,给出了模型融合的应用实例介绍.

摘要:制造供应链计划是制造供应链管理的关键问题,它不仅需要分配生产任务和控制库存,还需要解决不同工厂(企业)间的运输配套问题.为统一描述具有复杂产品生产过程(包括装配型、分解型和多输入多输出型等)的生产任务、存储任务和不同模式(包括单种物料独立运输模式和多种物料组合运输模式)的运输任务,提出了扩展状态任务网(extended state task network,简称ESTN).扩展状态任务网用比例转化任务统一描述生产任务、存储任务和单种物料独立运输任务,用虚比例转化任务和组合移动任务共同描述多种物料组合运输任务.应用扩展状态任务网,meta启发式方法在求解制造供应链问题时更容易编码和操作.为求解基于ESTN的制造供应链计划模型,提出了具有多样性检测的参考解集更新策略与分散性解变异策略的路径重连算法.路径重连算法维护一个由高质量解(精英解)组成的参考解集,将一个向导精英解的属性逐步引入一个起始精英解而形成的中间解序列(路径),并用此中间解序列更新参考解集以获得进化.计算实例表明,该路径重连算法比标准遗传算法、标准Tabu搜索算法以及普通路径重连算法能够获得更好的解,证明了多样性检测对参考解集更新的关键作用以及分散性解变异策略在提高解的质量上的能力.

摘要:基于特征选择的入侵检测系统处理的数据含有大量的冗余与噪音特征,使得系统耗用的计算资源很大,导致系统训练时间长、实时性差,检测效果不好.特征选择算法能够很好地消除冗余和噪音特征,为了提高入侵检测系统的检测速度和效果,对基于特征选择的入侵检测系统进行研究是必要的.综述了这一领域的研究进展,从过滤器、封装器、混合器3种模式对基于特征选择的轻量级入侵检测系统进行分类比较,分析和总结各种系统的优缺点以及它们各自适用的条件,最后指出入侵检测领域特征选择的发展趋势.特征选择不仅可以提升入侵检测系统的性能,而且使得对入侵检测的研究向特征提取算法的方向转移.

摘要:垂直切换作为多网融合的基础,受到了学术界和工业界的广泛关注.目前,相关工作主要集中于垂直切换算法的研究.但由于各种算法用于自身验证的仿真评测环境各不相同,因此无法公平地予以对比.从节点运动模型出发,提出了一组适合垂直切换算法的仿真评价模型.基于所提出的仿真评价模型,对常用的迟滞电平算法和驻留定时器算法进行了性能分析.在此基础上,提出了一种自适应垂直切换算法(self-adaptive vertical handoff algorithm,简称SAVA).仿真实验结果表明,该算法能够有效地提高垂直切换的性能.

摘要:动态多层Web系统在运行时会受到许多不确定性因素的影响.同时,在不同的负载模式下具有不同的性能特性,需要不同的性能模型进行描述.为消除不确定性因素对系统性能的影响,基于反馈控制原理设计的性能保障机制主要采用单一、固定的系统性能模型,对动态Web系统变化的性能特征考虑不够.在负载呈波动且具有不可预测特性的Internet环境中,这会降低性能目标的精确性和稳定性.采用自适应控制的思想,以满足请求平均响应时间为目标,提出了一种基于在线评估系统性能模型的保障机制,并采用两个不同类型的事务性Web测试基准,对所提方法进行了评价.结果表明,该方法能够有效减轻变化负载模式下响应时间与预期目标的偏离程度.

摘要:解决在没有节点位置信息的情况下,如何能量有效地保证网络连通性覆盖的问题.分析了节点覆盖与区域覆盖之间的关系,并给出了节点覆盖等于区域覆盖的充分必要条件.根据分析结果,基于构建连通支配集CDS(connected dominating set)的Rule K算法,提出了一种与节点位置无关网络连通性覆盖协议LICCP(location-independent connected coverage protocol).在LICCP协议中,每个节点根据本地节点密度选择合适的通信范围,利用Rule K算法选出的工作节点提供高质量的网络连通性覆盖.模拟实验结果表明,LICCP协议能够在较长时间内能量有效地提供高质量的网络覆盖,并保证网络的连通性.

摘要:传统的基于用户的协作过滤推荐系统由于使用了基于内存的最近邻查询算法,因此表现出可扩展性差、缺乏稳定性的缺点.针对可扩展性的问题,提出的基于项目的协作过滤算法,仍然不能解决数据稀疏带来的推荐质量下降的问题(稳定性差).从影响集的概念中得到启发,提出一种新的基于项目的协作过滤推荐算法CFBIS(collaborative filtering based on influence sets),利用当前对象的影响集来提高该资源的评价密度,并为这种新的推荐机制定义了计算预测评分的方法.实验结果表明,该算法相对于传统的只基于最近邻产生推荐的项目协作过滤算法而言,可有效缓解由数据集稀疏带来的问题,显著提高推荐系统的推荐质量.

摘要:当传统TCP协议用于卫星网络时面临各种问题,原因包括:卫星信道的高传输延迟、较大的误码率、带宽不对称、信号衰减等.为了提高卫星网络环境下TCP的性能,在不破坏TCP端到端特性的前提下,提出了一种新的主动代理方案.拥塞控制算法通过具有不同优先级的双报文对实施主动监测,能够根据网络带宽的变化自适应地调整TCP窗口.并且,对代理控制系统进行了稳定性分析.针对卫星网络下的TCP丢包恢复,提出了一种不依赖时钟同步的选择性否定应答算法.模拟实验表明,提出的TCP代理能够充分利用卫星网络的带宽,从而达到获得最佳有效吞吐率的目的.

摘要:目前,门户的功能定位已经从传统的信息集成转向应用集成.门户环境中应用间的进一步集成实际上表现为Portlet互操作问题. 现有Portlet互操作方法在共享范围、标准兼容方面存在不足且难于集成已有应用系统.提出了一种基于语义数据协作的Portlet互操作方法,其基本思想是:将参与互操作的Portlet抽象为ShadowComponent组件,然后基于本体建立ShadowComponent之间的语义数据关联,并使用ECA(event-condition- action)规则实现Portlet互操作.实验证明,该方法无须对已有应用作任何修改即可完成门户中的应用集成.

摘要:基于实时取证的思想,提出了一种安全可取证操作系统(security forensics operating system,简称SeFOS)的概念和实现思路.提出了其总体结构,建立了该系统的取证行为模型,对其取证服务和取证机制进行了分析并作了有关形式化描述,阐述了证据数据的采集和安全保护方法,提出把取证机制置于内核,基于进程、系统调用、内核资源分配和网络数据等获取证据的方法,并通过模拟实验验证了SeFOS的可取证性.可取证操作系统的研究对于进一步研究可取证数据库管理系统(forensic database management system,简称FDBMS)和可取证网络系统(forensic network,简称FNetWork)具有重要意义.

摘要:信任是决定实体双方在互联网上成功交易的一个重要原因,而商家的信誉又是客户选择交易对象的关键因素.传统的信任评估方法对评估对象提出种种假设,不能分辨恶意客户的虚假推荐,因而影响了评估结果的客观性和可信性.针对上述问题,提出了以灰色系统理论为基础、以灰色聚类评估算法为主要内容的信誉报告机制方案,同时证明了实体的灰关联度在t时刻存在的充分必要性.方案首先采用味集群方式采集原始数据,以被评估的实体为聚类实体、以客户对实体关键属性的评分为评估依据,运用灰关联分析得到实体的评估向量,按事先约定的灰类归纳整理,判断聚类实体的灰类,得到相应实体的信任度.方案的评估依据是客户对实体关键属性的实际评分,并且允许用贴近实际的灰数表达形式,避免了种种假设数据;味集群方法采集原始数据,能够有效地避免恶意推荐.实例说明,实体的信任可以被量化,实体间的信任可以具有可比性.方案具有评价可靠、可操作性强、适合软件自动处理等特点,是网络环境中具有实用价值的一种对实体信任度评估的新方法.

摘要:针对密码学中的多变元多项式二次方程系统求解问题,基于扩展Dixon结式提出了一种求解算法DR(Dixon resultants).基本思想为对于MQ(multivariate quadratic)问题,把x₁,x₂,…,x_n-1当作变元,而把x_n当作参数,然后利用和改进扩展Dixon结式方法求解该类系统.分析了该算法对于一般情况的复杂度,并且基于实验证据猜测:对于某些稀疏问题,新算法的复杂度很有可能也是多项式的.实验结果表明,对于m=n的一般和稀疏的问题,DR效率优于已有的两种算法.除了高效性,新算法还具有复杂度容易度量、计算时间可以预测的优点.

摘要:多重集重写MSR(multiset rewriting)模型是一种基于多重集重写的协议形式化建模方法.从目前的研究成果来看,该模型并不完善.针对其攻击者模型验证协议存在的不足,对MSR模型进行了改进,并给出了基于MSR模型的秘密性和认证性描述.实践表明,对模型的改进进一步完善了原模型.

摘要:提出并分析了一种确定的、可并行的消息认证码--DPMAC(deterministic parallelizable message authentication code).它基于分组长度为128-bit的分组密码来构造.使用一个密钥,可以处理任意长度的消息.在底层分组密码是伪随机置换的假设下,使用Game-Playing技术量化了攻击者成功伪造的概率,从而证明了其安全性.

摘要:在移动Ad Hoc网络(mobile ad hoc networks,简称MANETs)中,由于节点的快速移动,网络的物理拓扑结构在不断地变化.各个节点由于不能及时获得网络物理拓扑结构的更新,基于自我剪枝的广播算法难以获得有效的连通支配节点集,而不能保证广播信息的覆盖.为了保证广播信息的覆盖,在自我剪枝的广播算法中考虑链路的有效时间.假设广播存在节点覆盖范围不同和"Hello"信息周期长度不同,并且各节点按各自的方向和速度不断移动的网络,则节点的相对速度和广播半径决定了节点间连通的有效时间.依据链路中各节点的准确计时信息可以获得链路有效时间,从而为每个节点提供肯定有效的网络拓扑结构信息.称其为准确计时的可靠链路方法(reliable links with accurate timing,简称RELAT).利用准确计时的可靠链路方法,可以保证移动Ad Hoc网络广播中的虚拟网络连通性和物理链路的有效性,并基本上保证了本地视图的一致性,使得可以有效地保证广播的覆盖.大量的模拟实验数据表明,RELAT算法能够有效地保证覆盖,且当网络的密度较大时,即使放宽其中的一些条件仍能保持较高的覆盖率.

摘要:考虑有限域上椭圆曲线的构造.设q是一个奇素数的方幂,l是一个素数.证明了,如果GF(q)[x]上的方程U²-D(x)V2=ε(x-a)^l有本原解,其中,D(x)∈GF(q)[x]是一个首1三次无平方因子的多项式,则椭圆曲线y²=D(x)上的点(a,b)的阶是l.由此,给出了一种构造具有给定阶点的椭圆曲线的算法.

摘要:P2P(peer to peer)网络中,节点的自私行为极大地降低了系统的可用性.基于债务关系的文件交换网络,构建了一种促进合作的激励机制.同时,该机制保证了文件交换的公平性.激励机制的关键在于DHT(distributed hash table)网络邻居有限的固有特征,因而节点间的交互易于形成重复博弈.DFFE(debt relationship based fair file exchange in DHT network)协议只需维护很少的本地节点交互信息,协议开销小、网络扩展性好.网络路由采用基于一跳信息的贪婪算法.理性节点间的博弈存在纳什均衡,其策略选择的近似算法具有渐进收敛性.仿真实验表明了激励机制的有效性和在动态网络中性能的稳定性.

摘要:在移动自主网络中,提供服务质量支持是一个核心研究问题.大量研究表明,在移动自主网络中提供服务质量保障具有很大的挑战性.提出一个基于簇的QoS多路径路由协议(CQMRP),通过一种可扩展、灵活的方式为移动自主网络提供服务质量保证.在这个策略中,每个节点只维持局部路由信息而不是整个网络的全局状态信息.它支持多个服务质量约束.采用OPNET模拟器对协议性能进行了评估,结果表明,这个协议能够为移动自主网络提供一个可靠的多路径服务质量保证.

摘要:利用有限域包含的循环群之间的映射,给出了特征为素数p,MOV次数为3的超奇异椭圆曲线上的一类Tate对的两种有效压缩方法,它们分别将Tate对的值从6logp比特长的串压缩到3logp和2logp比特长.两种压缩方法的实现均使用原有Tate对的优化算法的代码,不需要针对压缩对编写新的实现代码,而且两种压缩对的实现均保持原有Tate对的实现速度.

摘要:随着生产工艺的提高,芯片上能集成越来越多的晶体管,多线程技术也逐步成为一种主流的处理器体系结构技术,而多线程处理器的软硬件接口也就成为急需解决的问题.在分析同时多线程的软件需求的基础上,提出龙芯2号同时多线程处理器的软硬件接口协同设计解决方案,给出相应的操作系统实现方案.同时,在Linux 2.4.20的基础上实现了龙芯2号同时多线程处理器相应的操作系统.通过运行SPEC CPU2000等测试程序进行性能评测,充分说明实现软硬件接口的龙芯2号同时多线程处理器极大地提高了多进程负载的性能.分析和设计方案不仅适用于同时多线程处理器,而且对于片内多核处理器的设计也有借鉴作用.

摘要:在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.

摘要:当前,数据流上的实时处理系统大多关心平均元组延时最小化要求,而很少考虑每个元组的截止期要求.提出一种实时的自适应批任务调度策略--ATS(adaptive batch task scheduling),以支持时变突发的数据流上关键任务的严格截止期需求.ATS调度策略可以降低调度开销和过期处理开销,从而实现截止期错失率最小化和有效任务完成率最大化.提出了最优调度单位概念--批粒度,设计了闭环反馈控制机制,以在不可预测的数据流环境中自适应地动态选择最优批大小.理论分析和实验表明了ATS批调度策略的有效性和高效性.

摘要:随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.