计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2009年第01期杂志 文档列表

计算机学报杂志综论

不确定性数据管理技术研究综述1-16

摘要：随着数据采集和处理技术的进步，人们对数据的不确定性的认识也逐步深入．在诸如经济、军事、物流、金融、电信等领域的具体应用中，数据的不确定性普遍存在．不确定性数据的表现形式多种多样，它们可以以关系型数据、半结构化数据、流数据或移动对象数据等形式出现．目前，根据应用特点与数据形式差异，研究者已经提出了多种针对不确定数据的数据模型．这些不确定性数据模型的核心思想都源自于可能世界模型．可能世界模型从一个或多个不确定的数据源演化出诸多确定的数据库实例，称为可能世界实例，而且所有实例的概率之和等于1．尽管可以首先分别为各个实例计算查询结果，然后合并中间结果以生成最终查询结果，但由于可能世界实例的数量远大于不确定性数据库的规模，这种方法并不可行．因此，必须运用排序、剪枝等启发式技术设计新型算法，以提高效率．文中介绍了不确定性数据管理技术的概念、特点与挑战，综述了数据模型、数据预处理与集成、存储与索引、查询处理等方面的工作．

基于复杂性科学基本概念的MAS涌现性量化研究17-29

摘要：在MAS（Multi—Agent System）领域，面向涌现的MAS研究将MAS看成一类特殊的复杂系统，其关注点是MAS宏观层面的涌现性问题．这类研究需要借用复杂性科学研究中的一些基本概念描述、阐述MAS涌现性研究中的问题．文中着重对几个常用的基本概念及其量化研究做一概览，以深化对它们的认识，并结合这些概念及其量化研究在MAS涌现性研究中的应用特点，阐明它们对面向涌现的MAS研究的作用，以促进进一步的研究．这些概念包括复杂性、混沌边缘、自组织、涌现、适应和进化等．

计算机学报杂志研究论文与技术报告

无线传感器网络中基于散列链的随机密钥预分发方案30-41

摘要：密钥管理是无线传感器网络安全机制和服务的基石，随机密钥预分发是当前最有效的密钥管理机制，但目前的随机密钥预分发方案存在一个潜在的挑战：无法同时获取理想的网络安全连通性和网络抗毁性．文中提出了一种基于散列链的随机密钥预分发方案，通过有效调节散列链长度、公共辅助节点数、散列链数量等参数，节点仅需预分发数量较少的密钥信息，就能够以较高的概率建立对偶密钥．而且，即使存在大量的受损节点仍能保持较强的网络抗毁性．理论分析和模拟实验证明了所提出方案的有效性和安全性．

Web服务工作流中基于信任关系的QoS调度42-53

摘要：不确定或恶意欺骗的服务节点对服务工作流调度的影响常常是致命的，因此仅从性能Qos角度研究工作流调度存在片面性．针对当前工作流调度中存在信任机制与调度机制分离的缺陷，提出了基于信任关系的工作流QoS调度方法，通过建立信任调度模型，利用D—S理论进行信任度计算，同时阐述了工作流路径级信任关系的概念及其传递、合并的计算方法，并将信任关系作为Qos调度的重要指标来综合考虑．该方法在保证工作流性能Qos要求的同时兼顾信任QoS的要求，大量实验结果表明：该算法较传统的基于性能QoS的调度而言，不仅具有更优的QoS性能，而且显著提高了调度的成功率．

基于非合作博弈的无线网络路由机制研究54-68

摘要：无线网络因其分布性、独立性、移动性等特点，网络性能容易受到自私节点的影响．文中综述了无线网络中因自私节点的存在而带来的一些关键问题，特别对含有自私节点的无线环境中基于非合作博弈理论的路由机制进行了分析和研究．为了解决网络中自私节点的问题，目前研究人员主要提出了两种机制：基于信任度的机制和基于非合作博弈的激励机制．文中对上述两类机制进行了总结和分析，特别地，针对无线自组织网络和无线网状网络中各种激励机制进行了详细的研究．网络编码作为一种有效的技术有助于提高无线网络的性能，文中探讨了基于网络编码的优化对含有自私节点的无线网络性能的影响．同时还分析了非合作无线网络中节点共谋的问题，最后提出了当前非合作无线网络研究中存在的理论挑战及潜在的热点方向．

基于随机行走的无线传感器网络簇间拓扑演化69-76

摘要：无线传感器网络中的容错机制可防止节点出现因能量的耗尽而失效或链路因网络的入侵而失灵的现象．目前无线传感器网络中的一些容错机制被相继提出，这些方法的主要思想是采用冗余策略．文中借助于复杂网络理论，提出了一个基于随机行走的无线传感器网络簇间拓扑演化模型．拓扑生长的动态特性分析表明：由该模型演化成的网络拓扑具有无标度（scale—free）网络的性质．许多研究工作已经表明，容错能力不仅仅存在于有冗余的系统中，而且同样也存在于无标度网络中．

分片支撑矢量机77-85

摘要：文中借鉴了分段线性识别的基本思想，提出了分片支撑矢量机模型．该模型首先将特征空间剖分成若干子空间，在每个子空间中基于支撑矢量机构造一个最优分类面，然后，将各个分类面链接起来构成一个分片最优分类面以逼近理论上的最优分类超曲面．同时，文中还从理论上分析探讨了其推广能力的界，为分片支撑矢量机模型提供了坚实的基础．最后，经典双螺旋线数据实验结果表明，相对于传统支撑矢量机，分片支撑矢量机的计算速度、分类能力以及推广能力均有了明显提高．

关于CTL与EAGLE两种规划扩展目标表示语言的语义比较86-96

摘要：在不确定的智能规划领域中，CTL和EAGLE是两种重要的扩展目标表示语言．虽然与CTL相比EAGEE具有可以表示规划意图和失败处理机制的特点，但是有关严格比较这两种目标表示语言语义的研究工作还不多．文章在规划的执行结构这一语义层次上对这两种语言做了严格的比较，证明了对于许多包括原来曾被认为无法用CTL表示的EAGLE规划目标而言，都存在着一个与之语义等价的CTL规划目标，并且进一步分析了这两种语言在表示规划目标和指导规划求解这两个层次上的优缺点．

Bigraph理论在自适应软件体系结构上的应用97-106

摘要：现有的软件体系结构形式化方法对体系结构的动态性、自适应性支持有限，并不能很好地验证系统演化过程中的一致性、完整性等动态特征．Bigraph理论融合了”演算和移动Ambient演算的优势，重点强调计算的位置和连接两方面因素，具有较为完整、可扩展的理论框架．这使得Bigraph不仅在概念上能够满足现有自适应软件对结构和行为的需求，而且还提供了直观、普适的表达能力．文中简要介绍了Bigraph的基本概念和现状，利用Bigraph理论对自适应软件体系结构进行了形式化规约，分析和验证了系统动态演化的性质，并探讨了Bigraph理论在自适应软件体系结构形式化方面的优势和拓展方向．

基于视觉感知的时空联合视频拷贝检测方法107-114

摘要：视频拷贝检测在视频信息检索和版权保护等方面有着重要意义．文中依据视觉感知特性，认为现有的基于单帧的拷贝检测方法未充分利用视频的时空相关性，进而在利用这一重要特性进行拷贝检测方面进行了探讨．依据自然图像序列的时空相关性以及视觉系统对时空信息的感知特性，通过对时空切片单元块Sub进行DCT分析得到与视频内容相关的时空联合特征，并基于该特征提出视频拷贝检测算法．实验表明，文中所提出的视频拷贝检测方法对视频内容变化敏感而对相同内容视频格式上的变化鲁棒，表现出优于现有方法的性能．

一种基于对象属性关注度的QoS传输控制方法115-123

摘要：针对分布式虚拟环境中几何资源分配不均匀的问题，提出一种基于对象属性关注度的QoS传输控制方法以及模型传输Qos管理模型．该方法扩展了基于几何属性的模型传输控制传统方法，将对象几何属性与非几何属性综合作为传输中QoS控制参数，结合动态QoS控制的思想，针对分布式虚拟环境实时性要求较高的特点，在运行时刻考虑网络带宽对服务质量的影响，进行动态的QoS协商，并给出了一种针对该问题的动态协商算法．实验结果表明该方法能够全面反映用户对虚拟对象的关注程度，并随着网络带宽变化，在保证实时性的前提下更好地进行模型传输．

具有期望容错域的前向掩蔽联想记忆模型的设计方法124-131

摘要：联想记忆的综合问题是目前没有很好解决的难题．文中用作者提出的通用前馈网络和排序学习算法，提出了一种设计具有期望容错域的前向掩蔽联想记忆模型的方法．该方法一般性地解决了信息空间上联想记忆的综合难题，使设计出的联想记忆模型具有任意期望的记忆样本容错域．

基于目标增量的无等待流水调度快速迭代贪婪算法132-141

摘要：最小化总完工时间无等待流水调度是典型的NP-完全问题，广泛存在于实际生产系统．改变传统求解调度序列目标函数的模式，提出目标增量法，通过目标函数变化量判断新解的优劣，大大降低算法所需计算时间；通过证明启发式算法基本操作的目标增量性质，设计两种基本目标增量法以快速评估新产生解的质量．提出快速迭代贪婪算法FIG（Fast Iterative Greedyalgorithm）求解该问题，构造初始解生成算法，提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量．基于110个经典Benchmark实例，将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较，实验结果表明FIG在性能上优于SRTS和PH1P，略逊于DPSOvnd；在效率上优于SRTS和DPSOvnd，略逊于PH1p．

通用处理器的高带宽访存流水线研究142-151

摘要：存储器访问速度的发展远远跟不上处理器运算速度的发展，日益严峻的访存速度问题严重制约了处理器速度的进一步发展．降低load—to—use延迟是提高处理器访存性能的关键，在其他条件确定的情况下，增加访存通路的带宽是降低load—to—use延迟的最有效途径，但增加带宽意味着增加访存通路的硬件逻辑复杂度，势必会增加访存通路的功耗．文中的工作立足于分析程序固有的访存特性，探索高带宽访存流水线的设计和优化空间，分析程序访存行为的规律性，并根据这些规律性给出高带宽访存流水线的低复杂度、低延迟、低功耗解决方案．文中的工作大大简化了高带宽访存流水线的设计，降低了关键路径的时延和功耗，被用于指导Godsonx处理器的访存设计．在处理器整体面积增加1．7％的情况下，将访存流水线的带宽提高了一倍，处理器的整体性能平均提高了8．6％．

自动映射多循环程序到有限FPGA资源的参数化流水线模板152-160

摘要：FPGA为加速计算密集型应用提供了一个灵活高效的平台．然而，由于片上资源有限，在一些情况下，需要将大规模应用中包括的多个循环程序分别映射到FPGA上执行，当一个循环程序执行完毕后，需要重新配置FPGA以执行下一个循环程序，FPGA重构过程在整个程序执行过程中占用了较多时间．文中设计了一个参数化流水线模板，并提出了相应的指令分配调度策略，实现了自动将多循环程序顺序映射到目标FPG上系统，同时在程序切换时，不需要进行FPGA重构．实验结果表明，对每个循环程序，文中设计的流水线模板能达到与专用硬件结构相当的执行节拍，同时节约了程序切换时的重构时间．

一种高效、容错的通用量子计算机体系结构161-168

摘要：通用量子计算机（universal quantum computer）在求解某些在经典计算机上具有超多项式复杂度的问题方面存在着潜在的巨大优势．通用量子计算机体系结构在很大程度上影响量子计算功效和量子程序设计风格．文中提出一种通用量子计算机的体系结构，并考虑了在该体系结构下计算能力的扩展和容错性能等问题．

一种基于博弈论模型的Ad Hoc网络功率控制算法169-176

摘要：在Adhoc网络中，采用控制数据报文向相邻节点的发射功率的方法来提高能量的使用效率是一种常用的方法，但是采用功率控制也会对网络连通性、延迟和容量带了负面影响．文中对Adhoc网络中能量控制机制进行了讨论，给出了Adhoc网络基于非合作博弈的功率控制问题模型．提出了一种以满足网络连通性、容量最大化、网络半径最小为目标的分布式非合作功率控制博弈算法，并给出了对该算法纳什均衡的存在性和唯一性的证明．实验表明该算法具有较好的综合性能．

一种用于空间数据多尺度表达的R树索引结构177-184

摘要：针对现有R树无法支持空间数据多尺度表达的问题，提出了一种用于空间数据多尺度表达的R树变形索引结构：（1）允许空间对象出现在非叶结点上；（2）利用树的深度反映空间分辨率的变化，提供分辨率维的支持；（3）树的分支结构考虑对自动制图综合算法的支持．分析了该变形R树索引结构的空间数据多尺度查询过程，并着重对该索引结构生成算法中的约束条件、插入算法和分裂算法进行了讨论．针对相同数据源，使用该方法与基于四叉树的空间数据多尺度索引方法进行了对比实验，结果表明，该索引方法能有效检索多分辨率形式组织的空间数据，具有综合结果记忆功能，效率明显．