• 2008年第19卷第6期文章目次
    全 选
    显示方式: |
    • 求解大规模TSP问题的自适应归约免疫算法

      2008, 19(6):1265-1273.

      摘要 (5034) HTML (0) PDF 557.92 K (5717) 评论 (0) 收藏

      摘要:从理论上分析了影响多级算法性能的因素,并以此为依据构造了求解TSP问题的自适应归约免疫算法.该算法借助归约集的进化使归约集规模自适应增长,归约边的预测精度不断提高,从而提高了算法在归约后找到全局最优解的概率.实验结果表明,该算法比其他算法获得了质量更高的解.

    • 迭代空间交错条块并行Gauss-Seidel算法

      2008, 19(6):1274-1282.

      摘要 (5676) HTML (0) PDF 450.15 K (5912) 评论 (0) 收藏

      摘要:针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.

    • 基于多重分形的聚类层次优化算法

      2008, 19(6):1283-1300.

      摘要 (5675) HTML (0) PDF 1.02 M (7189) 评论 (0) 收藏

      摘要:大量初始聚类结果之间存在强弱不同的相似性,会给用户理解与描述聚类结果带来不利影响,进而阻碍数据挖掘后续工作的顺利展开.传统聚类算法由于注重聚类形状及空间邻接性,或者考虑全局数据分布密度的均匀性,实际中均难以解决这一类问题.为此,提出了基于分形的聚类层次优化算法FCHO(fractal-based cluster hierarchy optimization),FCHO算法基于多重分形理论,利用聚类对应多重分形维数及聚类合并之后多重分形维数的变化程度来度量初始聚类之间的相似程度,最终生成反映数据自然聚集状态的聚类家族树.此外,初步分析了算法的时空复杂性,基于合成数据集和标准数据集的有关实验工作证实了算法的有效性.

    • 一种评估近似Pareto前沿多样性的方法

      2008, 19(6):1301-1308.

      摘要 (4195) HTML (0) PDF 387.13 K (6444) 评论 (0) 收藏

      摘要:提出了一种评估近似Pareto前沿多样性的方法.它用精确Pareto前沿相对于其近似集合的"暴露程度"来评估多样性,其计算基于精确Pareto前沿,不像其他多样性评估技术基于近似集合进行计算.对于多于两个目标(分量)的近似集合,其他技术不能或者不能很好地评估,计算结果表明,该技术能够很好地评估.并且,在理论上对该方法进行了严格的论证.

    • 基于点的POMDP算法的预处理方法

      2008, 19(6):1309-1316.

      摘要 (4765) HTML (0) PDF 509.82 K (5703) 评论 (0) 收藏

      摘要:基于点的算法是部分可观察马尔可夫决策过程(partially observable Markov decision processes,简称POMDP)的一类近似算法.它们只在一个信念点集上进行Backup操作,避免了线性规划并使用了更少的中间变量,从而将计算瓶颈由选择向量转向了生成向量.但这类算法在生成向量时含有大量重复和无意义计算,针对于此,提出了基于点的POMDP算法的预处理方法(preprocessing method for point-based algorithms,简称PPBA).该方法对每个样本信念点作预处理,并且在生成α-向量之前首先计算出该选取哪个动作和哪些α-向量,从而消除了重复计算.PPBA还提出了基向量的概念,利用问题的稀疏性避免了无意义计算.通过在Perseus上的实验,表明PPBA很大地提高了算法的执行速度.

    • >综述文章
    • 元建模技术研究进展

      2008, 19(6):1317-1327.

      摘要 (9385) HTML (0) PDF 502.00 K (9664) 评论 (0) 收藏

      摘要:随着UML(unified modeling language)与MDA(model driven architecture)的兴起和流行,模型已经成为软件开发的核心制品,而模型重要性的提升使得建模语言以及定义建模语言的元模型逐渐成为软件开发中的一个核心要素.软件开发往往涉及多个领域,而不同的领域往往需要不同的建模语言及其建模工具.但是,手工地为不同的建模语言开发建模工具代价高昂.元建模技术是解决这个问题的方法之一,通过元建模,可以根据领域需要定制合适的元模型以定义领域建模语言,进而自动生成支持该建模语言的建模工具.大量的工程实践表明,与领域建模以及MDA相结合,元建模可以大幅度地提高软件开发效率,基于元建模的MDA比基于通用建模语言的MDA更具潜力.在最近的几年中,元建模及其相关技术发展迅猛,不但在技术上取得了长足的进步,而且在产业界也开始出现大规模的商业应用.总结了元建模的现有研究成果,分析和比较了现有元建模工具,探讨了元建模的可能发展方向.对元建模中存在的问题进行分析,并指出了可能的解决途径.

    • 软件体系结构评估技术

      2008, 19(6):1328-1339.

      摘要 (8768) HTML (0) PDF 427.12 K (13443) 评论 (0) 收藏

      摘要:作为在软件生命周期早期保障软件质量的重要手段之一,软件体系结构评估技术是软件体系结构研究中的一个重要组成部分.将现有的软件体系结构评估方法划分为3类:基于场景的评估方法、基于度量和预测的评估方法以及特定软件体系结构描述语言的评估方法.按照软件体系结构评估技术的评价框架,分别从评估方法的目标、质量属性、关键技术等方面对这3类方法的特点进行介绍和对比.最后分析了现有研究中存在的不足并进一步探讨了软件体系结构评估技术的研究趋势.

    • 一种可定制的自主构件运行支撑框架

      2008, 19(6):1340-1349.

      摘要 (4910) HTML (0) PDF 414.63 K (6184) 评论 (0) 收藏

      摘要:描述了一种动态、可定制的构件自主化的实现手段及运行平台,试图通过对实现自主构件的方法和手段的探索,为开发具有自主性的基于Internet的软件系统提供一定的实践基础和经验.在实现自主构件时,采取了改装已有普通构件的方式,将软件Agent技术和构件技术结合起来,通过为构件定制行为规则和规划来控制和调度构件的行为,使得构件能够根据环境的状态调整自己的行为.同时,通过集成可以解释和执行声明式规则的规则引擎,使得可以在不修改构件源代码和重新部署构件的情况下,动态定制和实现构件的自主性行为能力.

    • 一种面向网构软件体系结构的信任驱动服务选取机制

      2008, 19(6):1350-1362.

      摘要 (4407) HTML (0) PDF 520.71 K (6043) 评论 (0) 收藏

      摘要:基于信任度评估的思想,从软件服务选取的角度对此问题进行了探讨,提出一种面向网构软件体系结构的信任驱动的服务选取机制:首先,给出一种通用的、机器可理解的应用需求及信任演化策略描述规范;其次,采用一种基于反馈的信任形成及决策机制,并给出一个信任驱动的服务选取算法;最后,给出一种面向网构软件体系结构的信任驱动的服务选取支撑框架.初步实践表明,上述机制为开发可信网构软件提供了有效支持.

    • 一种基于对象网的多视角软件过程模型

      2008, 19(6):1363-1378.

      摘要 (4837) HTML (0) PDF 598.72 K (5394) 评论 (0) 收藏

      摘要:基于关注点分离原则,结合多视角软件过程建模与对象网之间的相似性,提出了一种基于对象网的多视角软件过程模型MOPN-SP-net,可以提高软件过程模型的可复用性(reusability).在使用MOPN-SP-net建模时,得到的多视角软件过程模型是一种多维网.直接分析这种多维网比较困难,为此,提供了一种从对象网到平面网的等价转换规则,且转换前后的模型在合理性准则上保持等价.根据这个转换规则,可以通过分析转换后平面网模型的合理性得知转换前的对象网的合理性.

    • 统计测试的软件可靠性保障能力研究

      2008, 19(6):1379-1385.

      摘要 (4646) HTML (0) PDF 329.33 K (5952) 评论 (0) 收藏

      摘要:研究了统计测试对不同软件的测试能力,提出将测试有效性信息综合到软件可靠性评估模型中,以提高可靠性估计的针对性和精度.通过实验证明了该方法的合理性.该方法为高可靠性的软件质量保障要求提供了途径和可能.

    • >综述文章
    • Skyline查询处理

      2008, 19(6):1386-1400.

      摘要 (11608) HTML (0) PDF 518.81 K (13588) 评论 (0) 收藏

      摘要:对目前的Skyline查询方法进行分类和综述.首先介绍Skyline查询处理问题产生的背景,然后介绍Skyline查询处理的内存算法,并从带索引和不带索引两个方面对现有的外存Skyline查询处理方法进行分类介绍,在每组算法后,都对该组算法进行了性能评价,然后介绍不同子空间上的多Skyline查询处理模型——SKYCUBE的概念和相关研究.另外,还介绍了不同应用环境下解决Skyline查询处理的策略以及Skyline查询处理问题的扩展,最后归结出Skyline查询处理后续研究的几个方向.

    • 基于聚类分解的高维度量空间索引B+-Tree

      2008, 19(6):1401-1412.

      摘要 (4889) HTML (0) PDF 571.64 K (7130) 评论 (0) 收藏

      摘要:为了提高索引性能,高维度量空间索引通常采用K-Means等聚类技术来获取数据的分布信息.但是,已知的工作需要根据经验来确定聚类参数,缺乏对聚类与查询性能之间关系的理论分析.提出了一种基于聚类分解的高维度量空间B+-tree索引,通过聚类分解,对数据进行更细致的划分来减少查询的数据访问.对聚类与查询代价的关系进行了讨论,通过查询代价模型,给出了最小查询代价条件下的聚类分解数目等理论的计算方法.实验显示,提出的索引方法明显优于iDistance等度量空间索引,最优聚类分解数的估计接近实际最优查询时所需的聚类参数.

    • 基于能量和频繁模式的数据流预测查询算法

      2008, 19(6):1413-1421.

      摘要 (4197) HTML (0) PDF 391.93 K (5122) 评论 (0) 收藏

      摘要:设计了数据流预测查询的新模型,包括局域流能量预测、能量分布模式挖掘及预测序列的重构和数据流能量的度量方法;设计了融合数据流能量回归与基于频繁模式的小波分解预测新方法,并将新算法推广到强偶合多数据流的预测查询; 提出了最近最频繁序列模式的新概念,并应用于局域流能量分解;在真实数据上的模拟实验,验证了算法的有效性.

    • 一种从XML数据中发现关系信息的方法

      2008, 19(6):1422-1427.

      摘要 (5921) HTML (0) PDF 306.08 K (6023) 评论 (0) 收藏

      摘要:提出了一种发现蕴藏在不同XML文档嵌套结构中的关系信息及其出现模式的新方法.可根据用户兴趣,发现描述不同实体之间联系的关系信息,抽取关系实例及其在文档中的出现模式.具体解决方案是:首先识别和收集包含用户感兴趣的实体的XML文档片段;然后根据文档片段标签的语义和文档片段的结构计算文档片段的相似度,并采用自适应阈值方法按相似度聚类文档片段,使得包含同一种关系的文档片段聚集在同一个片段簇;最后从XML文档片段簇中抽取关系实例及其出现模式.实验结果表明,对于包含有意义标签的各种XML文档,该方法能够准确地识别和抽取出描述指定实体之间联系的各种关系信息.

    • 以活动为中心的个人信息管理

      2008, 19(6):1428-1438.

      摘要 (5076) HTML (0) PDF 469.64 K (5855) 评论 (0) 收藏

      摘要:通过分析用户执行多任务的交互场景,基于活动理论,将任务、任务相关的信息以及任务间的关系统一纳入活动研究的框架,提出了以活动为中心的个人信息管理方式;从活动的静态结构、动态演变过程以及活动间的关系3个方面对活动进行建模;针对多活动场景中的用户交互和活动对象的内容提出了计算活动相关性的方法;并在此基础上,实现了以活动为中心的个人信息管理工具——ACPIM(activity-centered personal information management).评估结果显示:以活动为中心的个人信息管理有助于用户减轻认知和记忆负担,降低交互努力,从而提高工作效率.

    • >综述文章
    • 无线传感器网络传输控制协议

      2008, 19(6):1439-1451.

      摘要 (11517) HTML (0) PDF 483.21 K (13860) 评论 (0) 收藏

      摘要:介绍了无线传感器网络的传输控制问题,总结了近年来提出的各种传输控制协议及主要设计思想.首先引入了传输控制问题的研究背景;然后分别从拥塞控制和可靠保证两个方面介绍代表性的研究工作,对涉及的主要方法进行分类分析;最后进行了各种协议的综合比较,并指出了无线传感器网络传输控制未来的研究方向.

    • 可扩展路由器

      2008, 19(6):1452-1464.

      摘要 (8449) HTML (0) PDF 538.69 K (10054) 评论 (0) 收藏

      摘要:对可扩展路由器的研究现状进行了综述,并在可扩展路由器体系结构和模型研究的基础上提出其分层模型,将可扩展路由器"自底向顶"地划分为互连结构和数据交换层,路由查找层、标准接口层、分布式操作系统层、分布式路由行为层和单映像管理层6层,并综述了每层的研究进展.最后进行了总结并分析了当前可扩展路由器发展的难点.

    • 解决策略冲突导致BGP路由发散的自适应机制

      2008, 19(6):1465-1472.

      摘要 (4439) HTML (0) PDF 388.19 K (5612) 评论 (0) 收藏

      摘要:BGP(border gateway protocol)作为一种基于策略的协议,允许每个自治系统独立地选择本地路由策略.自治系统之间可能存在的路由策略冲突会引起BGP路由持续不稳定.当前提出的解决办法要么需要增加额外的通信开销,要么限制自治系统自由的选择路由策略.提出了一种解决策略冲突引起BGP路由不收敛的自适应方法,既不损害自治系统选择路由策略的灵活性,也不需要在BGP消息中增加额外信息.路由的稳定性被加入到BGP的判决过程中,不稳定路由的优先级被降低,使更加稳定的路由得以被选为最优路由,终止路由策略冲突引起的争执.在网络拓扑发生改变的情况下,这种新方法能够自适应地调整路由选择,重新收敛到新的稳定状态.

    • 一种面向大规模P2P系统的快速搜索算法

      2008, 19(6):1473-1480.

      摘要 (5330) HTML (0) PDF 363.61 K (6109) 评论 (0) 收藏

      摘要:提出一种面向大规模P2P系统的概率搜索小组(probabilistic search team,简称PST)算法.各节点首先发布本节点的资源共享信息,并基于分布式丢弃Bloom Filter技术(distributed discarding bloom filter,简称DDBF)对从其他节点收到的信息进行保存和转发.PST算法把RW算法中漫步者的概念扩充为搜索小组.通过聚合各小组在搜索过程中获得的资源信息,PST算法实现了多个小组之间相互协同的并行搜索.分析模拟结果表明,PST算法在保持低定位开销的同时取得了较好的定位性能.

    • >综述文章
    • 支持网格应用的光网络控制和管理

      2008, 19(6):1481-1490.

      摘要 (8409) HTML (0) PDF 500.10 K (8410) 评论 (0) 收藏

      摘要:在高能物理等科研领域有许多基于网格的科研项目,包括海量数据传输在内的网格应用对网络带宽、延迟等QoS指标等有很高的要求.传统的IP路由网络无法满足这些要求.面向连接的光网络能够较好地满足这些要求,但也面临着许多挑战.分析了科研网格应用的特点及其对光网络控制和管理的特殊要求,重点分析比较了几种现有的光网络控制和管理方式,归纳和总结了此领域尚待研究的问题,最后提出了Lambda Grid和OVPN等新的研究 方向.

    • 移动IPv6网络家乡代理容错方法研究

      2008, 19(6):1491-1498.

      摘要 (4861) HTML (0) PDF 386.78 K (5543) 评论 (0) 收藏

      摘要:移动IPv6基于家乡代理的转发,实现节点移动过程中的可寻址性.提出主动检测和迁移的家乡代理容错方法,通过在家乡代理之间设计环状检测和备份链,使家乡代理之间相互检测失效情况的发生;所有注册信息在家乡链路上仅备份一次;检测到失效后,有效家乡代理自动地暂时接管失效家乡代理的工作,并主动通告给相关移动节点;移动节点收到家乡代理失效信息后,主动启动恢复过程.给出了实现该方法的数据结构和容错算法,描述了具体的容错处理过程.通过理论分析证明了该方法比协议标准中的方法具有更小的容错时间和信令开销,特别是在移动节点的移动频率较慢的情况下更是如此.

    • TCP流竞争拥塞及拥塞链路的缓存需求研究

      2008, 19(6):1499-1507.

      摘要 (4123) HTML (0) PDF 388.15 K (6087) 评论 (0) 收藏

      摘要:针对流竞争拥塞,提出了一种拥塞分析模型FCCM(flow-competing congestion model),给出了TCP竞争流在拥塞链路上的分布特性,推导了流竞争拥塞发生的条件,进而分析了在流竞争拥塞发生时,路由器为维持拥塞链路100%利用率所需的最小缓存.分析结果表明,当流数目不确定时,应对流竞争拥塞所需的缓存将不大于流数目确定时经典BSCL(buffer sizing for congested internet links)方案中的最小缓存需求.

    • 拓扑相关蠕虫仿真分析

      2008, 19(6):1508-1518.

      摘要 (4525) HTML (0) PDF 593.54 K (6519) 评论 (0) 收藏

      摘要:从蠕虫传播的漏洞主机发现、代码传播以及代码启动3个方面提出了一个完整的数据包级拓扑相关蠕虫仿真模型,设计了基于有向图的Small World拓扑结构生成算法,并通过选择性抽象在NS2上实现了一个完整的数据包级拓扑相关蠕虫仿真系统.最后,通过该仿真系统实验分析了逻辑拓扑结构和蠕虫代码启动方式对蠕虫传播的影响.仿真实验结果表明,该仿真系统可以为拓扑相关蠕虫研究提供重要的支持.

    • 基于异常诊断的代码注入攻击自动分析和响应系统

      2008, 19(6):1519-1532.

      摘要 (4213) HTML (0) PDF 522.77 K (5729) 评论 (0) 收藏

      摘要:提出了一种基于进程异常场景分析的代码注入攻击自动分析和响应系统.该系统根据进程异常场景自动分析攻击载荷句法,并生成面向漏洞的攻击特征,由该攻击特征,可以识别和阻断基于同一未知漏洞同种利用方式的各种代码注入攻击的变形.通过在生成攻击特征以及响应攻击的过程中结合网络协议和进程的状态,可以在不升高检测漏警概率的前提下显著地降低响应虚警概率和系统对外服务的响应时间.另外,还简要介绍了基于Linux和Windows 2000的原型系统,并给出了功能和性能的实验结果.

    • 一种传输控制协议中的主动拥塞控制机制

      2008, 19(6):1533-1545.

      摘要 (4960) HTML (0) PDF 895.89 K (6438) 评论 (0) 收藏

      摘要:TCP Reno是当前Internet中流行的TCP(transmission control protocol)版本,为改善其性能,提出一种TCP Reno的改进方案,取名DAA-TCP(dual AMID-based active TCP).DAA-TCP融合了双重AIMD(additive-increase multiplicative-decrease)算法,添加了主动拥塞控制,即在满足给定条件下,可主动降低拥塞窗口,即便此时网络并未发生拥塞.仿真分析了DAA-TCP的性能,结果表明,与TCP Reno相比,使用DAA-TCP可提高吞吐量、减少重传报文、降低报文重传率;DAA-TCP也能与TCP Reno友好共存.另外, DAA-TCP可由TCP Reno发送方作较小修改得到.因此,DAA-TCP容易实现,所增加的额外开销较少.

    • 可扩展的多目标最优化多播路由

      2008, 19(6):1546-1554.

      摘要 (4107) HTML (0) PDF 367.09 K (5229) 评论 (0) 收藏

      摘要:提出了一种提高多播可扩展性的新思路——将多播可扩展性作为一个最优化目标引入到多播路由算法的设计中,采用多目标最优化路由算法,提高现有多播可扩展性方法的效率.采用多目标最优化路由设计方法对AM(aggregated multicast)和DTM(dynamic tunnel multicast)两种方法进行改进,给出了相应的最优化目标、启发式多目标最优化多播路由算法和多目标最优化多播路由遗传算法.对于AM方法,使用该算法可以有效地减少汇聚多播树的数量;对于DTM方法,使用该算法可以有效地增加非分枝节点的数量,减少多播状态.

    • 标准模型下基于身份的强密钥隔离签名

      2008, 19(6):1555-1564.

      摘要 (5303) HTML (0) PDF 335.90 K (5602) 评论 (0) 收藏

      摘要:如何应对基于身份的签名系统中密钥泄漏的问题,是一项非常有意义的工作.为了处理这一问题,利用Dodis等人的密钥隔离机制,提出了一种基于身份的密钥隔离签名.所提出出的签名方案具有两个显著的特点:(i) 满足强密钥隔离安全性;(ii) 其安全性证明无须借助随机预言机模型.

当期目录


文章目录

过刊浏览

年份

刊期

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