摘要:近年来,随着网络技术的快速发展和广泛应用,人工智能领域中的诸多问题,如时序安排、计划编制、资源分配等,越来越多地以分布形式出现,从而形成一类多主体系统.相应地,求解该类问题的传统约束满足问题也发展为分布式约束满足问题,分布式约束满足已经成为多主体系统求解的一般框架.首先,简要介绍了分布式约束满足问题的基本概念,总结了该问题的基本算法及其改进算法,并对这些算法的效率和性能进行了比较分析.然后,讨论了近年来分布式约束满足问题的若干典型应用;最后,给出了分布式约束满足问题基本形式的扩展和今后的研究方向.分布式约束满足问题最新研究进展表明:今后的工作将着重于面向现实问题求解的理论研究,为实际应用提供坚实的理论基础.

摘要:异构分布式实时仿真系统是一类特殊的实时系统,基于改进的SP(spare processor)容错模型(checkpoint-based spare processor,简称CSP)对其容错问题进行了研究.首先,根据仿真系统的特点提出了两个命题,这是后续工作的基础;而后,基于Markov链对仿真任务的最坏反应时间进行了分析,并提出了仿真任务的可调度性分析规则;最后,基于CSP容错模型和上述可调度分析规则提出了异构分布式实时仿真系统的容错调度算法CSP-RTFT.算法的仿真结果表明:该算法较之基于SP模型的算法SP-RTFT可获得更好的稳定性、更高的任务接收率;缺点是资源利用率比PB模型下的算法要低.

摘要:多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.

摘要:算法的平滑复杂度能够更合理地反映算法的实际性能.在运行高斯算法求解线性系统过程中,矩阵条件数是导致求解误差偏大的一个因素.Sankar等人用0-保留高斯扰动进行对称矩阵条件数平滑分析.然而,Sankar等人给出的平滑复杂度过高而且复杂.为了解决这个问题,首先提出了两个关键的不等式;然后将这两个不等式用于对称矩阵条件教的平滑分析,得到更简单、更低的平滑复杂度;并利用该结果对高斯算法求解精度进行平滑分析,从而得到更低的平滑复杂度.

摘要:考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).

摘要:XML已经成为网络上信息描述和信息交换的标准.由于网络上信息的本质特性和XML数据内在的灵活性,很多用XML编码的数据都是半结构化的.随着XML应用得越来越广泛,人们提出了多种XML数据的存储模型.与此同时,XML的查询优化也是数据库领域研究的一个重要课题.综合论述了XML数据查询优化技术的现状,指出了XML查询优化的特点和研究的关键性问题.描述了查询优化技术各个方面的重要研究成果以及存在的问题,进一步展望了未来的研究方向,并在此基础上提出了对XML查询优化方法的一些观点.

摘要:对等用户参与P2P(peer-to-peer)文件共享应用的自由性,影响着该类系统的可用性.作为国内教育网上Maze系统的开发者,试图利用收集到的系统日志深入分析Maze用户特性,发现影响资源可用性的关键点,以指导Maze系统的演进.从用户需求的角度重新定义了P2P文件共享系统可用性的概念,并结合Maze系统日志,率先采用聚类技术对P2P文件共享系统的用户进行了量化分类,且深入研究了占用户总数大约0.77%的活跃型用户对Maze系统可用性的影响.发现活跃型用户具有服务器性质,可大幅提升系统的可用性,是改进P2P文件共享系统设计可利用的资源.

摘要:目前,大多数Web文献不能满足不同层次科研人员的查询要求.分析了这一问题产生的原因,提出建立辅助的Web文献检索结构以帮助用户更准确地获取所需文献的思想.基于该思想,设计了通过挖掘最长顺序频繁词组抽取文献特征的算法,提出了能够表现特征之间、文献之间、特征与文献之间关系的扩展的特征层次树结构及其构建方法.实验表明,挖掘最长顺序频繁词组在抽取文献特征方面比常用的TFIDF具有更大的优势.理论分析说明,扩展的特征层次树具有压缩的存储结构、词组与文献关系的表现方式和更好的辅助检索功能.

摘要:语义路由是P2P路由技术的关键研究内容之一.智能化路由策略语义表达灵活,但可扩展性和查全率较低;语义覆盖网络可扩展性好,但要么难以组织,要么维护开销很大.提出一种新的基于匹配路径和概率平衡树的P2P语义路由模型(match path and probability balance tree,简称MPPBTree),通过层次化和匹配路径组织资源存储结构和节点排布方式,达到一种近似平衡的分布特征,使节点能够根据查询内容本身进行路由决策,并同时保持较低的维护开销.模型支持灵活的语义搜索,拥有良好的可扩展性,保证任意节点的路由都能覆盖全网络.模型不要求任何中心服务的存在,所有的节点只需维护少量局部信息,且都会同时承担索引、存储、中继的功能,以均摊系统运行的负荷.

摘要:随着即时通信(instant messaging)应用的日益广泛和用户数量的迅速增加,即时通信蠕虫(IM蠕虫)的发生频率也相应提高,传播范围变广以及危害程度加深,其正成为网络安全的重要威胁.首先综合论述IM蠕虫的研究概况;然后剖析IM蠕虫的基本定义、功能结构和工作机理以及IM蠕虫与其他网络蠕虫的区别与联系;讨论IM蠕虫的网络拓扑和传播模型;归纳目前防范IM蠕虫的最新技术;最后给出IM蠕虫研究的若干热点问题与展望.

摘要:Peer-to-Peer(P2P)技术的发展引发了Internet应用模式的变革.为了寻求网络运营商、内容提供商和Internet用户三方共赢的解决方案,必须从他们各自的角度出发对P2P应用进行系统的测量与分析.首先概述了P2P测量的研究内容,并将现有的P2P测量研究划分为P2P拓扑特征的测量、P2P流量特征的测量、P2P可用性的测量3类.在对P2P测量方法进行对比分析之后,详细综述了P2P测量的研究现状,对现有的各种测量方案以及研究成果进行了深入的分析,指出了其中存在的问题和缺陷.最后讨论了P2P测量未来的研究方向.

摘要:基于流特性的测量在网络行为分析中发挥着越来越重要的作用.超时策略作为流识别的主要标志之一,对流特性测量的正确性和性能具有重要的影响.通过对现有流超时策略进行比较和分析,指出这些超时策略的适用范围和存在的问题.在详细分析网络中流长分布和速度测度各项指标的基础上,针对短流占总体流量很大比例的特点,提出了一种动态超时策略(dynamical timeout strategy,简称DToS).该策略通过实时综合分析网络使用状况,针对不同特性的流采用不同的超时方式,从而增加网络测量性能,提高测量系统的资源利用率;并可以有效地感知可能存在的网络异常,启动应急措施,保证测量系统的安全;然后通过理论分析的方法验证该策略的可行性和鲁棒性;最后通过实验论证该超时策略在实际测量中的性能,并进一步分析其适用范围.

摘要:近年来提出的许多面向单个数据源设计的多播树并不能简单扩展到任意源多播系统中,因为针对每个源建立一个树代价高昂.而已存在的一些允许多数据源的P2P(peer-to-peer)系统的维护量大,在体现结点能力差异等方面缺少灵活性.提出一个任意源覆盖多播服务方案,并具有结点能力约束性能.它建立在非DHT(distributed hash table)覆盖网络上,无须建立显式的多播树.设计了两种分布式多播算法,它们将任意源的多播信息传送到所有结点的期望跳数是O(log_cn),其中,c是平均结点能力,n是多播组中的结点个数.

摘要:主动兴趣管理将主动路由技术应用于兴趣管理领域,采用通信和兴趣管理相结合的方式确定分布式虚拟环境中对象间的通信关系.在对主动兴趣管理、层次式兴趣管理及其相关技术进行总结的基础上,层次式主动兴趣管理引入了兴趣层次的概念,提出了适用于虚拟环境中多个对象的兴趣层次评价模型,并根据兴趣层次控制通信细节,减少了不必要的网络通信,进一步提高了系统的可扩展性.

摘要:提出了一种用k次B样条曲线全局逼近实平面k次代数曲线的算法,每个连通部分用一条B样条曲线逼近.它适合于任意亏格的不可约的实平面代数曲线(包括含奇异点的曲线).这种逼近建立在所提出的代数曲线胀开采样的基础上,这种胀开采样算法从本质上解决了奇异点周围采样难的问题.实验结果表明,该方法的逼近精度高于已有算法.

摘要:使用运动数据驱动虚拟人模型运动是人体运动仿真的常用方法.通常,运动数据本身定义了适合该运动数据的骨架结构,这要求被其驱动的虚拟人模型也必须有相匹配的骨架定义.提出了一种推迟到运动数据导入时再为模型生成骨架结构的基于语义分析的懒匹配算法(lazy match based on semantic analysis,简称LMSA),该算法先用一组平行平面切分人体模型以生成备选关节点集,并在导入运动数据后对备选关节点集和运动数据的骨架结构进行语义分析,匹配具有相同语义的备选关节点和骨架结构的各关节,使已有的虚拟人几何模型能够直接应用于具有不同骨架结构的人体运动数据.

摘要:针对细节高度复杂模型的特点,提出一种视点相关的渐进传输方法.根据人的视觉特征,算法将模型表示为多分辨率的四边形参数面片和表面法向细节纹理.该算法利用法向映射提高传输和绘制的效率,然后随着视点的变化动态细化和传输当前视点下轮廓部分的参数面片信息,从而最大限度地减少了模型传输时面片的数量.参数面片的结构规则,面片之间关联性低,因此能够按任意顺序高效地传输,从而实现真正的视点相关传输,并可以采用有效的编码方法对其结构和几何信息进行压缩.实验结果表明了该算法的有效性,特别适合于表面细节复杂的表面模型的交互传输和绘制.

摘要:高效地选取可见面,对于复杂场景的快速绘制是非常重要的.提出一种可见面的选择方法,能将基于图像空间或基于物体空间的可见面选择进行高效的结合,实现可见面的快速高精度的选取.首先,它对场景中的面片进行基于法向的分类,并根据面片的空间位置,为每一类面片分别建立一种层次形式的索引结构进行管理;然后在绘制过程中,基于像素驱动对可见面片进行由近及远的选取.由于索引结构对面片进行了有序的管理,这种选取计算很快,并能将可见面都选取出来,而已绘制的可见面的集合又能自动地成为遮挡者,隐含地剔除了大量的不可见面.与目前国际上关于可见性处理的方法相比,新方法对可见面的选取具有很高的精度,速度很快,并且能够方便地处理带有动态物体的场景.

摘要:提出一种以任意三角剖分为控制网格的二元箱样条曲面算法.二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向四次箱样条在CAGD等领域有着广泛的应用.其规范的箱样条曲面计算仅适用于控制点的价数均为6的网格.从规范的算法出发,提出了一种任意价数控制网格的曲面计算算法,并对算法的连续性等进行了详细的分析.生成的曲面具有保凸性,且是分片C¹连续的.该算法可进行3D离散点全局或局部插值,并可应用于3D曲面重构等领域.