• 2009年第20卷第3期文章目次
    全 选
    显示方式: |
    • 描述逻辑εLN 循环术语集的不动点语义及推理

      2009, 20(3):477-490.

      摘要 (5029) HTML (0) PDF 863.13 K (5145) 评论 (0) 收藏

      摘要:循环术语集是描述逻辑长期以来的研究难点,其最基本的问题即语义及推理问题没有得到合理的解决.分析了描述逻辑循环术语集的研究现状和存在的问题,将Baader 的工作扩展到新的方向.针对更大的描述逻辑系统研究了循环术语集的语义及推理机制,即在描述逻辑εL 的基础上添加数量约束构造算子,提出了描述逻辑εLN,给出了εLN 的语义(包括不动点语义和描述语义).针对εLN 的需要,重新定义了描述图(包括语法描述图和语义描述图).使用描述图之间的模拟关系给出了不动点语义下εLN 循环术语集的可满足性和包含关系推理算法,并证明了推理算法是多项式时间复杂的.

    • 描述逻辑μALCQO 的语义及推理

      2009, 20(3):491-504.

      摘要 (4529) HTML (0) PDF 729.56 K (5247) 评论 (0) 收藏

      摘要:循环术语集是描述逻辑长期以来的研究难点,其最基本的问题即语义及推理问题没有得到合理的解决.基于混合分级μ-演算将不动点构造算子引入到含有枚举构造算子的描述逻辑ALCQO 中,提出了一种允许包含循环术语集的描述逻辑μALCQO.给出了μALCQO 的语法、语义和不动点构造算子的性质,证明了μALCQO 的可满足性推理等价于混合分级μ-演算的可满足性推理.基于混合分级μ-演算可满足性推理算法,并利用完全强化自动机给出了μALCQO的可满足性推理算法,以及给出了推理算法正确性证明和复杂性定理.μALCQO为进一步给出同时含有不动点构造算子和枚举构造算子的表达能力强的描述逻辑推理算法提供了理论基础.

    • Petri 网的步问题研究

      2009, 20(3):505-514.

      摘要 (5189) HTML (0) PDF 598.58 K (5669) 评论 (0) 收藏

      摘要:在基于Petri 网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP 完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP 等价性证明.最后分析两类特殊子问题是P 问题.

    • 逻辑系统NMG 的满足性和紧致性

      2009, 20(3):515-523.

      摘要 (4828) HTML (0) PDF 629.28 K (5105) 评论 (0) 收藏

      摘要:紧致性是模糊逻辑的一个重要性质.现已经证明?ukasiewicz 命题逻辑、G?del 命题逻辑、乘积命题逻辑和形式系统L*都是紧的.通过刻画逻辑系统NMG 中的极大相容理论和证明NMG 的满足性,进而证明了NMG也是紧的.

    • >综述文章
    • 软件过程建模方法研究

      2009, 20(3):524-545.

      摘要 (16859) HTML (0) PDF 1.09 M (19896) 评论 (0) 收藏

      摘要:通过软件开发实践,人们逐步地认识到软件产品的质量在很大程度上依赖于产品开发时所使用的过程.软件过程建模是通过特定的方法对软件过程进行抽象、表示和分析以增加对软件过程的理解,同时,可执行的(enactable)软件过程模型可以直接指导实际软件开发活动,进而规范软件开发行为并最终提高软件质量.为了系统地了解软件过程建模方法研究的现状和最新进展,采用系统评价(systematic review)方法对该领域最近10年的主要研究进行了概括和分析.从一系列的相关研究中,选出来自20 个会议和7 种期刊的72 篇文献,作为系统评价的依据.该系统评价回答了如下关于软件过程建模方法的3 个问题,以便从总体上概括和把握该领域的研究:1) 软件过程建模方法主要基于什么范式;2) 软件过程建模方法研究的主要目的集中在哪些方面;3) 软件过程建模方法的研究有哪些新的趋势.同时,在仔细回顾和分析软件过程建模领域研究现状的基础上,给出了一种多维度的集成化软件过程建模方法.该方法有助于解决过程建模领域所面临的主要问题.

    • 随机QoS 感知的可靠Web 服务组合

      2009, 20(3):546-556.

      摘要 (5868) HTML (0) PDF 619.06 K (7556) 评论 (0) 收藏

      摘要:在面向服务的环境下,单个Web 服务往往不能满足用户的要求,这时就需将已有的单个Web 服务进行组合,以便产生满足用户需求的、增值的组合服务.已有的服务组合方法都很少考虑Web 服务的随机性和Internet 环境的动态性,从而在服务选择过程中产生的规划都是静态规划,结果导致在服务组合时都以较大概率出现组合失败.针对上述问题,提出了Web 服务各随机QoS 指标的度量方法和自适应QoS 管理体系结构,并利用随机型离散事件系统唯一的动态控制方法——马尔可夫决策过程(MDP),设计出随机QoS 感知的可靠Web 服务组合算法.实验结果表明,考虑随机性的QoS 度量方法和QoS 管理体系结构,以及平衡了“风险”与“报酬”的MDP 有效地提高了服务组合成功率.

    • 一种用于软件过程建模的适应性Agent 协商

      2009, 20(3):557-566.

      摘要 (4981) HTML (0) PDF 598.65 K (5044) 评论 (0) 收藏

      摘要:大多软件过程模型是预定义的.在变化的应用环境中,需要由相应人员进行适应性调整.提出一种用于软件过程建模的适应性多边协商模型—— AMNM-PA,其采用Agent 封装软件过程中所涉及的个体,包含组织、团队、个人等,通过Agent 间的协商动态、适应地建立针对给定软件项目的软件过程模型.AMNM-PA 基于非静态有限阶段Markov 决策过程,采用模型无关的Q 学习算法选取协商策略,因此能够支持动态、非预知环境下的适应性协商,从而满足软件过程建模对环境的适应性需求.AMNM-PA 已经实施于软件过程管理系统——SoftPM.

    • >综述文章
    • 基础软件平台质量评估

      2009, 20(3):567-582.

      摘要 (7836) HTML (0) PDF 780.38 K (15624) 评论 (0) 收藏

      摘要:关于软件质量模型和软件质量评估模型的研究,一直是软件质量保障和评估领域的研究热点,国内外在这两方面进行了大量的研究,并取得了一定的研究成果.近年来,以操作系统为核心的基础软件呈平台化、体系化的发展趋势,基础软件平台的质量评估成为亟待解决的问题.在总结、分析软件质量模型、软件质量评估模型研究发展现状的基础上,重点归纳和描绘了基础软件平台的质量评估发展历程,并简要探讨了基础软件平台质量评估研究的发展方向,力求为展开基础软件平台的质量评估建立良好的基础.

    • 基于模糊多属性决策理论的语义Web 服务组合算法

      2009, 20(3):583-596.

      摘要 (5239) HTML (0) PDF 827.86 K (7209) 评论 (0) 收藏

      摘要:综合评估数据异构的服务质量(QoS)从而选择出全局最优的执行计划是语义Web 服务组合研究中的难题之一.提出一种基于模糊多属性决策理论的语义Web 服务组合的优化选择算法(FuMuCom)以解决上述难题.该算法能够评价以实数、区间数和语言型数据描述的QoS 信息,从而进行综合决策.FuMuCom 包括3 个步骤:语言型数据的去模糊化、异构决策矩阵的标准化和QoS 综合评估.同时还介绍了一个可扩展的本体用来描述异构的QoS 数据;同时,从本体进化的角度介绍了一种异构QoS 的聚合算法.最后,通过对真实的服务质量数据进行实验,验证了该算法的优越性和有效性.

    • 重构C++程序物理设计

      2009, 20(3):597-607.

      摘要 (5121) HTML (0) PDF 615.94 K (5750) 评论 (0) 收藏

      摘要:整合重构的基本思想和物理设计的基本技术,提出了物理重构的概念.它是对软件物理结构的再设计,目的是在不改变软件外在行为的前提下,调整软件组织结构,从而提高软件的开发效率和可维护性等.在此基础上,提出用“识别-重构-评估”的迭代过程来实施物理重构,并介绍了常用的物理重构方法.实例研究表明,物理重构能够有效地优化系统的物理结构,使开发者从多个角度持续改善软件质量.

    • QoS 区分的自适应p-Persistent MAC 算法对信道利用率的动态优化

      2009, 20(3):608-619.

      摘要 (4882) HTML (0) PDF 727.92 K (5175) 评论 (0) 收藏

      摘要:在无线局域网中提供服务质量(QoS)保证的MAC 算法应该满足业务区分服务的要求和系统性能的整体最优.以往的此类自适应MAC 算法依赖于对不同级别的竞争业务数目进行估计,计算过于复杂.提出一种基于QoS区分的自适应p-persistent MAC 算法,QDA-MAC(QoS differentiation based adaptive MAC scheme).该算法引入了新的参数-坚持因子(persistent factor),其优化值能够实时反映网络负载的变化情况,结合近似优化的自适应方法,每次发送尝试后,该算法不需要估计每类竞争业务的数目,利用坚持因子的优化值实时更新各类优先级业务的发送概率,调整相应的协议参数,系统的性能也能接近最优.仿真结果验证了该算法不仅能够根据竞争业务数目的变化对系统的性能进行整体优化,而且能够提供业务区分服务,在QoS区分的基础上可以为实时业务提供严格的QoS保证,尤其在信道利用率和时延等方面明显优于标准的IEEE 802.11 DCF 和IEEE 802.11e EDCA 机制.

    • 防范前缀劫持的互联网注册机制

      2009, 20(3):620-629.

      摘要 (4862) HTML (0) PDF 605.03 K (5218) 评论 (0) 收藏

      摘要:借鉴IRR(Internet routing registry)机制中注册路由策略的思想,提出了前缀策略(prefix policy)的概念,并由此设计了一种防范前缀劫持的方法—— E-IRR 机制.在E-IRR 中,参与者发布自己的前缀策略,同时利用其他自治系统已注册的前缀策略验证BGP路由,从而防范前缀劫持.提出了维护前缀策略有效性措施,评估了E-IRR机制的安全能力与性能.方法的主要优势是,其在前缀劫持的防范能力与安全机制的实际部署需求之间达到了一个较好平衡,可增量式地部署,并不需要对BGP协议进行任何安全扩展.现有方案都不同时具备这些特性,它们使得E-IRR有望实际可行地解决前缀劫持问题.

    • 基于自适应随机行走的可扩展无偏抽样方法

      2009, 20(3):630-643.

      摘要 (4179) HTML (0) PDF 849.77 K (5202) 评论 (0) 收藏

      摘要:针对非结构化P2P 系统中可扩展的快速无偏抽样问题,提出了一种基于多个peer 自适应随机行走的抽样方法SMARW.在该方法中,基于代理随机行走选择一组临时的peer 执行抽样过程,一次产生一组可调数目的抽样节点,提高了抽样速度,选择每次产生的抽样节点作为临时peer 进行新的抽样过程,这种简单的方法可以保证系统具有近似最优的系统负载均衡程度.同时,SMARW 利用自适应的分布式随机行走修正过程提高抽样过程的收敛速度.理论分析和模拟测试表明,SMARW 方法具有较高的无偏抽样能力以及近似最优的系统负载均衡程度.

    • 公平的有向传感器网络方向优化和节点调度算法

      2009, 20(3):644-659.

      摘要 (4405) HTML (0) PDF 1.08 M (5580) 评论 (0) 收藏

      摘要:为了解决有向传感器网络中点目标覆盖控制问题,分别提出了两种方向优化算法和一个节点调度协议:改进的贪婪(enhanced greedy algorithm,简称EGA)、公平的方向优化(equitable direction optimization,简称EDO)算法和邻居节点调度协议(neighbors sensing scheduling,NSS).EGA 基于覆盖最多未覆盖的目标数选取工作方向,其不足是可能忽略临界目标.EDO 优化算法调节节点的工作方向,优先覆盖临界目标,公平分配感知资源,减小目标覆盖度的差异,EDO 算法使用效用值评价每个方向对网络覆盖质量的贡献大小,影响效用值的因素包括每个方向上的目标数、目标的覆盖度和邻居节点的方向决策,EDO 总是选择效用值最大的方向作为工作方向.NSS 协议引入局部覆盖集的概念,通过局部覆盖集判断当前节点是否为冗余节点,并在考虑节点剩余能量时决定节点是否可以转为睡眠,调度协议允许一个节点加入多个覆盖集,覆盖集轮流工作,使网络生存期最大化.仿真实验结果表明,分布式的EDO 算法比EGA 算法具有更好的方向优化性能,临界目标的覆盖质量提高了30%,同时明显地提高了网络生存期.

    • 一种结构化P2P 协议中的自适应负载均衡方法

      2009, 20(3):660-670.

      摘要 (5550) HTML (0) PDF 801.29 K (6473) 评论 (0) 收藏

      摘要:提出一种自适应负载均衡方法,方法采用一种被动式结点负载统计方法生成局部负载视图;一种文件访问统计方法生成局部文件访问视图;当系统内结点负载存在差异时,重载结点把指向自身的逻辑链路迁移至指向局部负载视图中的轻载结点,通过减小重载结点入度和增加轻载结点入度来减小结点间负载差异;当结点的请求负载较高时,通过局部文件访问视图计算需要缓存的热点文件及目标结点,降低承载热点文件的结点请求负载.实验结果表明,在用户查询服从Zipf 分布的环境下,自适应负载均衡方法可使系统负载达到较好的均衡;缓存方法虽然在一定程度上增加了缓存和更新开销,但在一定条件下比查询消息命中缓存节省的网络开销要小,降低了系统的整体负载.

    • 面向智能空间的位置感知方法研究

      2009, 20(3):671-681.

      摘要 (5109) HTML (0) PDF 706.42 K (6304) 评论 (0) 收藏

      摘要:位置感知是智能空间中的重要技术.在分析了现有基于移动自组网的位置感知方法后,提出了一种基于多维定标(multidimensional scaling,简称MDS)的新的位置感知方法——SSOLA(smart space oriented locationawareness method),可以对智能空间中的无线通信节点进行精确定位,获得节点之间的相对位置(坐标);当有极少数位置已知的锚节点(2 维定标存在3 个以上锚节点,3 维定标存在4 个以上锚节点)时,可以得到全网所有节点的绝对位置(坐标).SSOLA 算法的设计思想是:以MDS 分析为核心,采用Euclidean 测距方法计算节点间距离矩阵,采用1 跳和2 跳局部图相结合的自适应选择机制构建局部图,各节点独立计算局部图,最终合成全局位置图.此外,SSOLA 还可以与OLSR 路由算法相融合,从整体上减轻了SSOLA 算法的执行开销,提高了定位效率.仿真实验结果表明,SSOLA 具有对锚节点依赖小、定位精度高、可扩展性好、执行速度快等优点,对原始测量误差也有较强的鲁棒性,可以应用于战术互联网、智能战场等大规模无线通信环境中.

    • 一种基于分组密码的hash 函数

      2009, 20(3):682-691.

      摘要 (5010) HTML (0) PDF 512.57 K (5451) 评论 (0) 收藏

      摘要:提出了一个基于分组密码的hash 函数体制,它的rate小于1 但却具有更高的效率,同时,这个hash 函数可以使用不安全的压缩函数进行构造,降低了对压缩函数安全性的要求.首先,在黑盒子模型下对这个新的体制的安全性进行了证明,然后给出了能够用于构造该体制的使用分组密码构造的压缩函数,最后通过实验对比发现,新hash 函数的速度比rate为1 的hash 函数快得多.实验结果表明,除了rate以外,密钥编排也是影响基于分组密码hash 函数效率的重要因素,甚至比rate影响更大.该体制只有两个密钥,不需要进行大量的密钥扩展运算,大大提高了基于分组密码hash 函数的效率,而且该体制可以使用现有的分组密码来构造.

    • 可证安全的无证书代理签名方案

      2009, 20(3):692-701.

      摘要 (5488) HTML (0) PDF 549.41 K (7504) 评论 (0) 收藏

      摘要:研究在新提出的无证书公钥密码系统下的代理签名问题,给出了无证书代理签名方案非常强的安全模型.该安全模型下的攻击者是能力最强的超级类型I 和类型II 攻击者.同时,利用双线性映射设计了一个高效的无证书代理签名方案.其安全性基于计算Diffie-Hellman 问题的困难性,并在此安全模型下给出正式的安全证明. 鉴于方案的安全、高效和无证书管理的优点,它可广泛应用于电子商务、移动代理系统等方面.

    • 秋季植物叶子表观的模拟

      2009, 20(3):702-712.

      摘要 (5202) HTML (0) PDF 2.21 M (5325) 评论 (0) 收藏

      摘要:提供了一种采样并生成植物叶子表观的方法,可以非常真实地展现叶子秋季在干枯、老化过程中多种纹理、表观属性的变化.在生成叶子纹理的过程中,有别于以往基于单一材质样本的表观合成技术,采集了大量不同叶子样本表面的双向反射分布函数BRDF 和双向透射分布函数BTDF,最终从这些数据中得到叶子衰老过程在老化空间中的表达式和完全分布图.结合植物学知识和所得到的老化空间中的表达式和分布图,可以很好地指导合成秋季不同衰老程度叶子的表观纹理,并能够外插合成采样范围之外的叶子纹理样式.在生成多种不同种类和衰老程度的植物叶子的过程中验证了这种方法的有效性,得到了大量非常接近真实树叶的各种叶子

    • 支持外观属性保持的三维网格模型简化

      2009, 20(3):713-723.

      摘要 (4767) HTML (0) PDF 797.01 K (6025) 评论 (0) 收藏

      摘要:对已有的三维网格简化技术进行分析,利用半边折叠操作对QEM(quadric error metric)算法进行改进,提出了一种基于二次误差测度(QEM)的网格简化算法,解决了非连续外观属性在简化过程中的畸变问题.通过分析顶点与非连续外观接缝的关系,得出了一个新的边折叠代价公式,使得外观畸变在简化过程中尽可能地推迟;并且在执行半边折叠时给受影响的三角形找到了合适的替换wedge,避免外观畸变的发生.实验结果表明,该算法保持了QEM 算法的高效性,同时在几何属性和外观属性上都取得了令人满意的简化效果.

    • 基于特征点的三维人脸形变模型

      2009, 20(3):724-733.

      摘要 (4648) HTML (0) PDF 927.47 K (9287) 评论 (0) 收藏

      摘要:针对传统三维人脸形变模型效率低的不足,提出了一个基于特征点的线性人脸形变模型.首先,提出一种基于平面模板的对应方法,自动地实现了三维人脸的稠密点对应,建立了人脸线性模型.然后,提出一个基于动态成分的线性形变模型,选择与目标人脸最相关的主成分作为形变模型的基空间.最后,采用一个全局与局部双重形变框架来完成人脸形状建模.实验结果表明,该方法能够获得较好的建模精度,可以通过真实照片上的少量特征点生成逼真的三维人脸模型.

    • 基于概率模型的高动态范围图像色调映射

      2009, 20(3):734-743.

      摘要 (4706) HTML (0) PDF 933.75 K (6670) 评论 (0) 收藏

      摘要:提出了一种概率模型对HDR(high dynamic range)图像进行色调再生.分别对局部像素的色调能量分布与HDR/LDR(low dynamic range)间梯度变化约束建立概率统计模型,通过求解最大后验概率(maximum a posteriori,简称MAP)将整个色调映射过程转化为一个能量最小化问题.实验结果表明,所提出的基于概率模型的色调映射方法能够生成比以往方法具有更多视觉信息的LDR 图像,可用于高级图像编辑、显示设备开发等领域.

    • 一种基于补偿代价的长事务调度算法

      2009, 20(3):744-753.

      摘要 (4565) HTML (0) PDF 620.82 K (5249) 评论 (0) 收藏

      摘要:服务组合应用中的事务具有较长的生命周期,一个事务被划分成多个分布的子事务.补偿机制是保证长事务原子性的一种有效方法,允许在语义上逆转一个已提交子事务的结果.然而,补偿的代价可能是巨大的.针对该问题,在分析并定义事务补偿代价的基础上,提出一种子事务延迟提交算法――STCD(subtransactions committingdelay)算法,与传统子事务执行后立即提交的方法相比,STCD 算法允许某个全局事务的子事务在提交前根据自身的补偿代价和全局事务的运行状态动态确定提交时间,使可能的补偿操作变更为回滚操作.算法的正确性得以证明.模拟实验结果表明,在事务失败时,STCD 算法可以有效地减少补偿活动的数目,降低补偿代价.

    • 一种细粒度高效多版本文件系统

      2009, 20(3):754-765.

      摘要 (3758) HTML (0) PDF 809.72 K (5384) 评论 (0) 收藏

      摘要:提出了基于快照的细粒度版本技术,能够克服已有多版本文件系统无法仅对系统局部目录或文件保留版本的缺点,增加了系统的灵活性;提出了版本空间的反向继承寻径,使用名字与版本独立的检索方案,可以充分利用版本间的相关性,优化数据物理布局,建立版本间的层级结构,既便于管理,又提高系统性能;设计了分别针对目录版本和文件版本的快速索引结构.评测结果表明,THVFS 的历史数据访问性能较著名的多版本文件系统ext3cow 提高了34.4%;Trace 实验中,相对于ext3,THVFS 的读性能提高了12%,同时,在每72 分钟生成一次快照的高频率下,维护所有历史版本仅需要80%的额外空间.

    • 集群软件无线电系统中实时信号处理调度研究

      2009, 20(3):766-778.

      摘要 (5279) HTML (0) PDF 863.05 K (4857) 评论 (0) 收藏

      摘要:在集群软件无线电系统中,当宽带大容量信号数据进入系统后通过在节点上的并行计算实现对强衰弱信号的高增益、低延迟处理.结合集群软件无线电系统中信号处理的特点,研究了以下任务调度方面的问题:1) 提出了一种适合集群软件无线电系统中信号处理的调度器模型.该模型简单、高效,避免了瓶颈问题.2) 提出了一种新的包含3 个步骤的调度策略——RQBB,其中第1 步采用已有的DASAP 算法.3) 提出了两种启发式算法——MQB 和MSD,分别用在RQBB 的第2 步和第3 步操作.MQB 是一种公平算法,用于使所有接收的任务具有较高的QoS 收益(较高的QoS 级别和较小的QoS 级别差异),MSD 算法用于使系统具有较高的吞吐率并达到负载均衡.通过大量实验对RQBB 与DASAP, DALAP 算法和RQRB 策略进行了比较.实验结果表明,RQBB 具有较高的调度成功率,使得所接收任务具有最优的QoS 收益,同时使得系统具有较高的吞吐率并达到负载均衡.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编: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号