• 2008年第19卷第4期文章目次
    全 选
    显示方式: |
    • >综述文章
    • 自主计算概念模型与实现方法

      2008, 19(4):779-802.

      摘要 (8950) HTML (0) PDF 1.01 M (8412) 评论 (0) 收藏

      摘要:自主计算是一个新兴的热点研究领域,旨在通过"技术管理技术"的手段隐藏系统管理复杂性,建立用户可指导的、状态觉察的和自适应的计算机系统.目前,自主计算的研究仍处于起步阶段,尚缺乏系统而成熟的理论体系.在阐明自主计算概念的基础上,提出一个自主计算概念模型.该模型刻画了自主元素和自主计算系统的基本工作机制和原理.以该模型为依据,概括性地提出了两类分别基于知识模型和数学模型的自主计算系统,分析它们的优点和不足.最后,给出了自主计算研究展望.

    • 伪球滤波和边缘检测

      2008, 19(4):803-816.

      摘要 (4862) HTML (0) PDF 884.93 K (4588) 评论 (0) 收藏

      摘要:提出了一种图像滤波器——伪球滤波器.在伪球滤波器中,除了尺度参数外,还引入了边缘保持参数,因而它能较好地解决传统滤波器的平滑性能与边缘定位精度之间的矛盾.以伪球滤波器取代经典Canny边缘检测算子中的高斯滤波器,得到一种基于伪球的边缘检测算子.模拟图像和真实图像的实验结果表明,与经典的Canny边缘检测算子相比,在具有相当平滑性的条件下,基于伪球的边缘检测算子对边缘定位具有更高的精度.

    • 基于词元再评估的新事件检测模型

      2008, 19(4):817-828.

      摘要 (4231) HTML (0) PDF 737.02 K (4951) 评论 (0) 收藏

      摘要:新事件检测(new event detection,简称NED)的目标是从一个或多个新闻源中检测出报道一个新闻话题的第一个新闻.初步实验发现,在对不同类别的新闻报道进行新事件检测时,其不同类型的词元往往具有不同的敏感程度.而传统方法往往将所有的词元等同看待.重点研究在新事件检测模型中,对于不同词元的权重设定问题.提出利用统计方法优化不同类别新闻对于不同词性词元的权重参数;提出利用已有新闻簇信息动态更新词元权重的方法,采用在新闻之间(而非新闻与新闻簇之间)计算相似度的形式,发挥两种比较形式的优点.在Linguistic Data Consortium(LDC)公共数据集TDT2与TDT3上进行实验,实验结果表明,这两种改进方法的效果明显,性能与同类系统相比有显著提升.

    • 二值alpha平面辅助的视频对象快速运动估计算法

      2008, 19(4):829-841.

      摘要 (4235) HTML (0) PDF 778.81 K (4627) 评论 (0) 收藏

      摘要:提出了一种任意形状视频对象的快速运动估计方法.详细分析了alpha平面在视频对象的快速运动估计过程中起到的指导性作用,采用边界扩展和边界掩码技术,提出了一种新的二值alpha平面匹配衡量准则WBAMC (weighted binary alpha-plane matching criterion).结合优先搜索策略,提出了二值alpha平面辅助的视频对象快速运动估计算法BAAME(binary alpha-plane assisted motion estimation).首先,利用alpha平面和WBAMC准则,将边界宏块的搜索范围缩小至两个搜索起点的单调区域,再采用传统的快速运动估计算法确定其运动向量;然后,用边界宏块的运动向量预测内部宏块的搜索起点;最后,采用快速运动估计算法搜索内部宏块的运动向量.这种方法可与多种空间域和频率域运动估计算法相结合,有效地应用于基于对象的视频编码器中.实验结果表明,对于多种类型的标准测试视频流,BAAME算法始终能够保持较高的估计精度和主观质量,运动补偿的平均PSNR(peak signal-to-noise ratio)较DS(diamond search)和PSA(priority search algorithm)(BAAS(binary alpha-plane assisted search)+DS)高出0.1dB~ 0.8dB,略低于FS(full search),但是其计算复杂度与FS相比降低了20倍.

    • 基于分类间隔的特征选择算法

      2008, 19(4):842-850.

      摘要 (4897) HTML (0) PDF 483.37 K (8317) 评论 (0) 收藏

      摘要:对于二类目标特征选择问题,首先讨论了特征空间的线性可分性问题,并给出了其判别条件;其次,通过借鉴支撑矢量机原理,分析了特征可分性判据的基本性质;最后,依据各特征对分类间隔的贡献大小定义了特征有效率,并以此进行特征选择和特征空间降维.实测数据与网络公开UCI(University of California,Irvine)数据库的实验结果表明,与经典的Relief特征选择算法相比,该算法在识别性能和推广能力上明显有所提高.

    • 基于图像类推的超分辨技术

      2008, 19(4):851-860.

      摘要 (4918) HTML (0) PDF 1.41 M (5456) 评论 (0) 收藏

      摘要:目前的图像超分辨技术都依赖于从适当的外部数据集合中提取信息以对图像进行增强,然而这个条件在很多实际应用中难以得到满足.通过对理想边缘模型与纹理内容的分析,发现图像在尺度空间上具有局部结构的自相似性及可传递性.基于这个特点,应用图像类推技术(image analogies,简称IA),可以将图像的局部特性在不同尺度上进行传递,从而为低分辨图像补充结构信息.在实现上,利用原图像和退化图像建立训练集合,用能量图构建学习网络,将图像类推问题转化为求解最小图能量问题.实验结果表明,这种自我类推方法不仅可以有效地提高放大图像的清晰程度,而且较一般的IA算法速度大为加快,更为重要的是,它可以摆脱一般方法对训练集合的依赖,完全独立进行.

    • 基于模糊商空间的聚类分析方法

      2008, 19(4):861-868.

      摘要 (4340) HTML (0) PDF 442.03 K (5153) 评论 (0) 收藏

      摘要:在商空间理论基础上,提出了基于Fuzzy相似关系和归一化距离的聚类分析方法,用以解决复杂系统的数据结构分析问题.得到了如下结论:(1) 通过引入基于Fuzzy相似关系和归一化距离的分层递阶结构,建立了严格的聚类分析理论描述;(2) 给出了有效的分层递阶结构聚类的快速算法;(3) 给出了两个Fuzzy相似关系或由两个归一化距离诱导的Fuzzy相似关系是同构的充分条件.其中所研究的理论和方法适应于建立在相似关系之上的任何复杂系统的数据结构分析.

    • 一个带破圈启发方法的回答集编程系统

      2008, 19(4):869-878.

      摘要 (5651) HTML (0) PDF 594.14 K (4545) 评论 (0) 收藏

      摘要:回答集编程(answer set programming,ASP)是一种回答集语义下的逻辑编程范例,可应用于非单调推理,叙述式问题求解等领域.本文为ASP提出并实现了一种破圈启发方法与一种基部限制式前向搜索过程,所得到的系统称为LPS.实验结果显示,相对于其他经典的ASP系统,LPS能够有效地解决处于相变难区域中的逻辑程序,通常这些程序被认为是计算困难的.除此以外,通过使用被称为动态变元过滤(dynamic variable filtering,DVF)的技术,LPS可以在计算过程中极大地缩小搜索树的尺寸.

    • >综述文章
    • 传感器网络节点定位系统安全性分析

      2008, 19(4):879-887.

      摘要 (7459) HTML (0) PDF 498.92 K (7934) 评论 (0) 收藏

      摘要:正确的节点位置信息是传感器网络构建和维护、监测事件定位、目标跟踪等模块实现的前提和基础.节点的定位过程极易受到各种攻击,在资源受限的传感器网络中,如何安全、有效地获取节点位置信息,是一个极具挑战性的安全问题.着重分析了不同类型的传感器网络节点定位系统所面临的安全攻击,讨论了近年来该领域具有代表性的安全措施的原理、特点和局限,并简要介绍了该领域今后的研究热点.

    • 无线网络邻近图综述

      2008, 19(4):888-911.

      摘要 (8404) HTML (0) PDF 2.09 M (10049) 评论 (0) 收藏

      摘要:网络拓扑结构可由邻近图表述,定义其为一个包含点集V和边集E的图,某有向边(u,v)属于该图当且仅当点v位于点u的邻域内,这个邻域是在某事先定义的邻近测度作用下产生的.回顾了迄今为止一些重要图结构,内容主要集中在5个方面,包括邻近图的定义或概念、构造算法、图例、隶属关系、拓扑参数,还谈到进一步的研究方向.

    • Blog研究

      2008, 19(4):912-924.

      摘要 (8046) HTML (0) PDF 613.84 K (8562) 评论 (0) 收藏

      摘要:Blog信息源和信息量迅速增长,并已通过频繁的链接和信息交互在互联网上构建了一个动态且紧密的社会网络,成为现实世界一个重要的信息来源.目前,Blog领域的研究主要集中在Blog的定义与识别、内容挖掘、社区发现、重要性分析、Blog搜索和作弊Blog识别等几个方面.大部分研究采用或借鉴了链接分析、自然语言处理等方面的技术和方法,也提出了一些针对Blog领域的特定方法.分析和比较了Blog领域的相关研究,并且讨论了研究中存在的问题,展望了未来的研究方向.

    • 基于双向令牌的可扩展及可靠的群组成员管理

      2008, 19(4):925-945.

      摘要 (3668) HTML (0) PDF 1.26 M (4285) 评论 (0) 收藏

      摘要:面向有线因特网的群组通信已研究多年,目前仍是研究热点之一,尤其是将现有研究成果扩展到移动与无线网络环境方面.研究了移动群组通信,该问题涉及群组成员关系动态性(成员加入及退出)、成员位置动态性(移动主机的移动性)和网络动态性(结点或链路出错).提出了适合于移动群组通信的基于双向令牌的层次环模型(也称为层次环结构)以解决该问题.该模型是逻辑环与逻辑树的结合模型,它利用了逻辑环的简单性和逻辑树的可扩展性.更为重要的是,这样的结合使得基于层次环结构的群组通信协议比现有的基于树结构的协议更可靠.理论分析和模拟研究表明:(1) 当群组规模增大时,该协议的可扩展性很好;(2) 该协议具有很高的可靠性.该协议特别适合于服务提供者和网络运营商将其计算设备分层次部署的情况,这时就要求每台计算设备都能局部化地维护其兄弟和父亲设备的信息.

    • 一种直接评价节点诚信度的分布式信任机制

      2008, 19(4):946-955.

      摘要 (4292) HTML (0) PDF 587.37 K (5006) 评论 (0) 收藏

      摘要:基于信誉的信任机制能够有效解决P2P网络中病毒泛滥和欺诈行为等问题.现有信任机制大多采用单个信誉值描述节点的诚信度,不能防止恶意节点用诚信买行为掩盖恶意卖行为;而且从信誉值上无法区分初始节点和恶意节点.提出一种新的分布式信任机制,基于交易历史,通过迭代求解,为每个节点计算全局买信誉值和卖信誉值,根据信誉值便能判断节点的善恶.仿真实验对比和性能分析表明,与EigenTrust算法相比,该算法能够迅速降低恶意节点的全局信誉值,抑制合谋攻击,降低恶意交易概率.

    • En-Route Transcoding缓存的优化放置和替换

      2008, 19(4):956-966.

      摘要 (3727) HTML (0) PDF 630.23 K (4481) 评论 (0) 收藏

      摘要:对en-route transcoding缓存中的缓存路由和协同放置及替换问题进行了研究.提出了CCRA(cost-aware cache routing algorithm)缓存路由算法,能以可控的探测开销来发现潜在的、具有最小访问开销的缓存对象.在此基础上,建立了en-route transcoding缓存的分析模型,将缓存放置和替换问题形式化为一个最优化问题,并利用一种基于动态规划的方法来求解最佳缓存放置策略.仿真结果表明,与已有的元算法放置策略相比,该协同放置和替换策略可以获得更好的CSR性能.

    • 用描述逻辑进行语义Web服务组合

      2008, 19(4):967-980.

      摘要 (4796) HTML (0) PDF 779.52 K (6728) 评论 (0) 收藏

      摘要:针对面向服务功能的语义Web服务组合问题,特别是经典的人工智能规划方法无法有效地处理Web服务执行过程中动态产生的新个体,以及基于服务匹配的方法则无法充分利用服务I/O参数类型之间大量的语义关联等关键问题,通过动态逻辑和描述逻辑之间的对比研究,采用描述逻辑公理来刻画Web服务的IOPR(inputs,outputs, preconditions and results),扩展了基于动态逻辑的人工智能规划方法,提出了把语义Web服务组合问题转化为描述逻辑推理问题的方法,克服了经典的人工智能规划方法中的困难和基于服务匹配的服务组合方法的缺点.

    • 对等网络拓扑测量与特征分析

      2008, 19(4):981-992.

      摘要 (4474) HTML (0) PDF 675.82 K (5276) 评论 (0) 收藏

      摘要:测量分析对等网络(peer-to-peer networks)拓扑特征是解决P2P优化、网络监管等问题的基础.对等网络是一类大规模、自组织、并且高度动态的复杂网络系统,准确、完整地测量所有对等网络拓扑面临很大困难.研究对等网络的协议特点,分析特定P2P拓扑实例成为认识P2P拓扑特性的一种可选研究方案.以Gnutella网络为测量对象,定义了对等网络拓扑测量系统准确性、完整性的衡量指标,设计、实现了基于正反馈的分布式Gnutella拓扑爬行器——D-Crawler;分析了Gnutella网络拓扑图的度等级分布特征、度频率分布特征以及小世界特性.实验和分析结果表明,对等网络拓扑图属性特征与其使用的协议和客户端软件行为密切相关;Gnutella网络中不同层次的节点之间的拓扑关系表现出不同的特性:上层节点组成的子图具有度等级幂律特征,但在其度频率分布上却呈现出正态分布的特性;下层节点在度等级分布上的幂律特征表现不强烈,而在其度频率分布特征上具有明显的幂律特性.拟合结果表明:幂律能够较好地拟合度等级分布和下层节点度频率分布,然而对于上层节点度概率密度分布,Gaussian拟合效果最好.Gnutella网络具有小世界特性,即:较大的聚集系数和较小的特征路径长度,但它不是无尺度图,不符合BA(Barabási-Albert)生长模型,其发展遵循一种不同于BA模型的生长过程.

    • 基于分布式学习的大规模网络入侵检测算法

      2008, 19(4):993-1003.

      摘要 (5016) HTML (0) PDF 598.33 K (5684) 评论 (0) 收藏

      摘要:计算机网络的高速发展,使处理器的速度明显低于骨干网的传输速度,这使得传统的入侵检测方法无法应用于大规模网络的检测.目前,解决这一问题的有效办法是将海量数据分割成小块数据,由分布的处理节点并行处理.这种分布式并行处理的难点是分割机制,为了不破坏数据的完整性,只有采用复杂的分割算法,这同时也使分割模块成为检测系统新的瓶颈.为了克服这个问题,提出了分布式神经网络学习算法,并将其用于大规模网络入侵检测.该算法的优点是,大数据集可被随机分割后分发给独立的神经网络进行并行学习,在降低分割算法复杂度的同时,保证学习结果的完整性.对该算法的测试实验首先采用基准测试数据circle-in-the-square测试了其学习能力,并与ARTMAP(adaptive resonance theory supervised predictive mapping)和BP(back propagation)神经网络进行了比较;然后采用标准的入侵检测测试数据集KDD'99 Data Set测试了其对大规模入侵的检测性能.通过与其他方法在相同数据集上的测试结果的比较表明,分布式学习算法同样具有较高的检测效率和较低的误报率.

    • 可变材质的实时全局光照明绘制

      2008, 19(4):1004-1015.

      摘要 (6455) HTML (0) PDF 709.40 K (4827) 评论 (0) 收藏

      摘要:现有的基于预计算的全局光照明绘制算法都假设场景中物体的材质固定不变,这样,从入射光照到出射的辐射亮度之间的传输变换就是线性变换.通过对这种线性变换的预计算,可以在动态光源下实现全局光照明的实时绘制.但是,当材质可以改变时,这种线性变换不再成立,因此,现有算法无法直接用于动态材质的场景.提出了一种方法:在修改场景中的物体材质时,可以实时得到场景在直接光照和间接光照下的绘制效果.将最终到达视点的辐射亮度根据其之前经过的反射次数及相应的反射材质分为多个部分,每个部分和先后反射的材质的乘积成正比,从而把该非线性问题转化为线性问题.又将所有可选的材质都表示为一组基的线性组合.将这组基作为材质赋予场景中的物体,就有各种不同的组合方式,预计算每种组合下所有部分的出射辐射亮度.在绘制时,根据各物体材质投影到基上的系数线性组合预计算的数据就能实时得到最终的全局光照明的绘制结果.该方法适用于几何场景、光照和视点都不发生变化的场景.使用双向反射分布函数来表示物体的材质,不考虑折射或者半透明的情况.该实现最多包含两次反射,并可以实时绘制得到一些很有趣的全局光照明效果,比如渗色、焦散等等.

    • 基于可变模版的三角网格拓扑压缩

      2008, 19(4):1016-1025.

      摘要 (4282) HTML (0) PDF 695.98 K (5308) 评论 (0) 收藏

      摘要:针对三角网格模型的拓扑信息,提出了一种高效压缩方法.不同于以往的单纯利用算术编码或霍夫曼编码对遍历三角网格生成的拓扑流进行编码压缩,根据三角网格模型(特别是规则三角网格模型)的特点,自适应地提高编码过程中对当前编码字符发生的预测准确率,实现对三角网格模型的拓扑信息的高效压缩.算法首先遍历三角网格模型,得到操作符序列;然后对得到的操作符序列的每个操作符作模版可变的自适应算术编码.在编码过程中,根据当前编码字符的前一个操作符、三角网格模型的特点以及网格遍历方法为当前编码操作符计算一个模版,在这个模版中,预测准确率高的操作符用较短的二进制串表示.根据当前编码操作符的可变模版,可以得到该操作符的二进制表示,并对这个二进制表示的每个比特作自适应算术编码.该方法是针对流形三角网格模型的拓扑信息作单分辨率的基于面的无损压缩,可以得到很好的三角网格拓扑信息的压缩结果,其压缩比甚至比拓扑压缩领域压缩比方面最好的TG算法的压缩比还要好.

    • 几个多面体网格剖分问题的NP难度证明

      2008, 19(4):1026-1035.

      摘要 (4348) HTML (0) PDF 524.97 K (5018) 评论 (0) 收藏

      摘要:主要讨论了两类多面体网格剖分问题——网格表面单调剖分和地形多面体剖分.首先研究了判定一个多面体表面能否被剖分成k个单调片的问题,通过构造与SAT问题(satisfiability problem)相应的几何模型,证明出该判定问题是NP完全的,而与之对应的最优剖分问题是NP-hard的.然后将证明方法推广到地形多面体剖分的问题:将一个带洞多面体或者简单多面体剖分成最小数量的地形多面体,这两个问题都被证明是NP-hard的.

    • 高性能交换与调度仿真平台的设计与实现

      2008, 19(4):1036-1050.

      摘要 (8316) HTML (0) PDF 1009.20 K (5296) 评论 (0) 收藏

      摘要:仿真实验已成为交换结构和调度策略性能评价的重要手段,而目前存在的交换结构与调度策略的仿真软件在可继承性与可扩展性方面还存在缺陷.基于Crossbar交换结构,建立数学模型,引入系统级设计方法,采用面向对象技术,设计并实现了用于研究交换结构和调度策略的仿真平台——SPES(switching performance evaluation system).该平台集成了输入排队、输出排队、联合输入输出排队、联合输入交叉点排队等多种交换结构以及相应调度策略.设计上实现了业务流、交换结构和调度策略三者之间的分离,具有良好的可继承、可扩展特性.用户通过与仿真平台之间的简单交互,完成模块的添加与仿真环境参数的配置,在支持变长业务、区分服务质量模型和多交换平面仿真方面具有良好的特性.通过简单扩展,该平台还可以实现网络级性能仿真.最后给出了基于该平台,在CICQ(combined input and crosspoint queuing)交换结构下,对所提出的支持DiffServ模型的分布式调度策略DS(DiffServ supporting algorithm)在不同业务流模型下的性能测试结果,并与输入、输出排队交换结构进行了比较,展示了DS良好的性能,验证了仿真平台的合理性.

    • >综述文章
    • 计算机体系结构软件模拟技术

      2008, 19(4):1051-1068.

      摘要 (8142) HTML (0) PDF 693.29 K (10750) 评论 (0) 收藏

      摘要:在现代处理器或计算机系统设计中,体系结构软件模拟技术已成为一个不可缺少的环节.与不使用模拟技术的计算机系统或处理器设计方法相比,软件模拟技术可以极大地降低设计成本和缩短设计周期.然而,由于开发计算机体系结构软件模拟器通常十分困难,模拟器运行标准性能测试程序的时间很长以及模拟结果精度差等3个主要问题,限制了体系结构软件模拟技术在计算机系统设计中的有效性.许多研究人员已经提出了各种各样的方法和技术来解决这些问题,但是,到目前为止,这些问题还并未得到根本性解决.同时,未来体系结构模拟技术的新挑战已经开始显现.研究了体系结构软件模拟技术的由来和历史,对现有的技术和方法进行了分类和比较,对未来的挑战也进行了分析,指出了该领域今后的发展方向,以帮助计算机体系结构设计师或研究人员选择、开发体系结构模拟器或对该技术进行研究.基于这些调查分析,正在使用较为先进的技术开发一个适合于安腾系列架构的体系结构模拟器SimIPF.

    • 一种分片式多核处理器的用户级模拟器

      2008, 19(4):1069-1080.

      摘要 (4405) HTML (0) PDF 570.70 K (5480) 评论 (0) 收藏

      摘要:随着片上晶体管资源的增多和互连线延迟的加大,分片式多核微处理器已成为多核处理器设计的新方向.为了对这种新型处理器进行体系结构的深入研究和设计空间的探索,设计并实现了针对分片式多核处理器的用户级多核性能模拟器.该多核模拟器在龙芯2号单处理器核的基础上,完整地模拟了基于目录的Cache一致性协议和存储转发式片上互联网络的结构模型,详细地刻画了由于系统乱序处理各种请求应答和请求之间的冲突而造成的时序特性,可以通过运行各种串行或并行的工作负载对多核处理器的各种重要性能指标加以评估,为多核处理器的结构设计提供了快速、灵活、高效的研究平台.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号