软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2009年第10期杂志 文档列表

软件学报杂志系统软件与软件工程

一种基于类型传播分析的泛型实例重构方法2617-2627

摘要：重构泛型实例有利于提高软件的复用性和类型安全，但现有重构方法的时间复杂度较高，不适用于即时持续的重构．分析了变量类型传播分析方法在重构中的不足，提出了一种改进的泛型变量类型传播分析方法．该方法通过引入一种可以描述复杂参数化类型关系的泛型类型传播图，以复制节点的方式实现泛型变量属性敏感的类型分析，并通过解决别名问题来提高分析的精度．实例研究表明，可以在与程序规模呈近似线性增长的时间复杂度内实施重构。取得了较满意的效果．

容错多处理机中一种高效的实时调度算法2628-2636

摘要：针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务，提出了一种高效的调度算法——TPFTRM（task partition based fault tolerant rate-monotonic）算法．该算法将单机实时RM算法扩展到容错多处理机上，并且调度过程中从不使用主动执行的任务副版本，而仅使用被动执行和主副重叠方式执行的任务副版本，从而最大限度地利用副版本重叠和分离技术提高了算法调度性能．此外，TPFTRM根据任务负载不同将任务集合划分成两个不相交的子集进行分配；还根据处理机调度的任务版本不同，将处理机集合划分成3个不相交的子集进行调度，从而使TPFTRM调度算法便于理解、实现以及减少了调度所需要的运行时间．模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试．实验结果表明，TPFTRM与目前所知同类算法相比，在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目．还减少了调度所需垂的运行时间．从而证宴了TpFTRM算法的高效性．

蜕变测试和断言检查的比较与实验研究2637-2654

摘要：在软件测试中，测试预言是一种用于检查程序在测试中是否正常运行的机制．然而在某些实际情况下，还无法制定测试预言或者难以有效地应用测试预言．针对此类测试预言问题，蜕变测试于近年应运而生，但蜕变测试的效率问题还没有被充分地加以研究．作者用控制实验的方法研究了使用蜕变测试的成本及效率，进而将蜕变测试和常用的断言检查两种方法的错误检测率和时间成本进行了比较和分析．实验结果表明，相比于断言检查方法，蜕变测试具有检测到更多错误的潜力．通过分析蜕变测试的效率和性能与断言测试相比，蜕变测试的错误检测率更高效而效率有待提高，可适用于较为粗粒度的测试需求．

软件学报杂志模式识别与人工智能

上下文感知系统中的规则生成与匹配算法2655-2666

摘要：针对现有上下文感知系统中的规则主要依靠开发者或用户手工定义的问题，提出了一种基于粗糙集理论的自动规则生成方法．该方法将上下文感知系统视为一种决策信息系统，并利用可辨识矩阵对上下文信息加以约简，进而自动生成规则．由于可供使用的数据有限，所生成的规则无法完全覆盖上下文的取值范围，因此可能出现找不到与上下文状态相匹配规则的问题．为了解决这一问题，提出了一种基于语义距离的规则匹配算法．最后验证了所提出方法的有效性和效率．

基于函数依赖的结构匹配方法2667-2678

摘要：模式匹配是模式集成、数据仓库、电子商务以及语义查询等领域中的一个基础问题，近来已经成为研究的热点，并取得了丰硕的成果．这些成果主要利用元素（典型的为关系模式中的属性）自身的信息来挖掘元素语义，目前，这方面的研究已经相当成熟．结构信息作为模式中一种重要的信息，能够为提高模式匹配的精确性提供有用的支持，但是目前关于如何利用结构信息提高模式匹配的精确性的研究还很少．将模式元素之间的相似度分为语义相似度（根据元素自身信息得到的相似度）和结构相似度（根据元素之间的关联关系得到的相似度），并采用新的统计方法计算元素间的结构相似度，然后再综合考虑语义相似度得到元素间的相似概率；最后根据相似概率得到模式元素间的映射关系（模式元素之间的对应关系）．实验结果表明，该算法在查准率、查全率及全面性等方面都优于已有的其他算法．

基于动作图的视角无关动作识别2679-2691

摘要：针对视角无关的动作识别，提出加权字典向量描述方法和动作图识别模型．将视频中的局部兴趣点特征和全局形状描述有机结合，形成加权字典向量的描述方法，该方法既具有兴趣点抗噪声强的优点，又可克服兴趣点无法识别静态动作的缺点片艮据运动捕获、点云等三维运动数据构建能量曲线，提取关键姿势，生成基本运动单元，并通过自连接、向前连接和向后连接3种连接方式构成有向图，称为本质图．本质图向各个方向投影，根据节点近邻规则建立的有向图称为动作图．通过NaiveBayes训练动作图模型，采用Viterbi算法计算视频与动作图的匹配度，根据最大匹配度标定视频序列．动作图具有多角度投影和投影平滑过渡等特点，因此可识别任意角度、任意运动方向的视频序列．实验结果表明，该算法具有较好的识别效果，可识别单目视频、多目视频和多动作视频．

基于C4．5决策树的流量分类方法2692-2704

摘要：近年来，利用机器学习方法处理流量分类问题成为网络测量领域一个新兴的研究方向．在现有研究中，朴素贝叶斯方法及其改进算法以其实现简单、分类高效的特点而被广泛应用．但此类方法过分依赖于样本在样本空间的分布，具有潜在的不稳定性．为此，引入C4．5决策树方法来处理流量分类问题．该方法利用训练练数据集中的信息熵来构建分类模型，并通过对分类模型的简单查找来完成未知网络流样本的分类．理论分析和实验结果都表明，利用C4．5决策树来处理流量分类问题在分类稳定性上均具有明显的优势．

软件学报杂志计算机网络与信息安全

一种无线传感器网络分布式安全成簇协议2705-2720

摘要：分簇的层次型拓扑控制方式在无线传感器网络中得到广泛研究和应用．然而，由于传感器网络本身所具有的开放性和资源有限的特点，攻击者可以很容易对成簇协议实施有效的误用和破坏．因此，保证成簇协议安全性是其实际广泛应用的基本前提．针对成簇协议所面临的各种安全威胁，提出了一种分布式安全成簇协议，通过网络安全初始化、可信基站的随机数广播和单向密钥链技术来有效地抵御节点伪装和簇首占据攻击、簇成员恶意征募攻击和多重簇成员身份攻击．对协议的安全性和开销进行了广泛和深入的分析，证明了协议的安全性和有效性．

移动AdHoc网络通信量相关干扰感知路由协议2721-2728

摘要：干扰严重影响移动Adhoc网络的网络吞吐量、能量消耗、网络寿命等性能．在已有基于邻居数目和分布位置的干扰模型基础上，进一步考虑各邻居上的通信量情况，提出通信量干扰模型．并在该干扰模型的基础上，提出一个通信量相关干扰感知路由TIR（traffic load-based interference-aware routing）协议．TIR通过在源节点和目的节点之间选择干扰最小的路径来降低数据包在转发过程中可能受到的干扰．模拟实验结果表明，所提出的通信量干扰模型符合移动Adhoc网络的特性，通信量相关干扰感知路由协议对网络寿命、通信延迟及吞吐量等网络性能有明显改善．

基于蚁群优化解决传感器网络中的能量洞问题2729-2743

摘要：基于多跳的无线传感器网络，越靠近sink的传感器节点因需要转发更多的数据，其能量消耗就越快，从而在sink周围形成了一种称为“能量洞”的现象．“能量洞”问题会导致整个网络由于内部节点能量过旱耗尽而结束寿命，同时，网络中离sink较远的节点仍有大量能量剩余．研究“能量洞”现象，基于改进的分级环模型，总结出调节各环内节点的数据传输距离是实现网络节能的有效方法．证明搜索各区域最优的传榆距离是一个多目标优化问题，即是NP难问题．从而提出一种基于蚁群优化的分布式算法，各区域根据其节点分布情况自适应地探索近似最优的传输距离，延长网络寿命．模拟实验结果表明，该算法在较短的时间内能够收敛到合理的解，并且得到的网络寿命接近于理想情况下的最优时间，与现有的类似算法相比，该算法提供了更长的网络寿命，并能适用于非均匀节点分布情况．

路标迭代提取和剔除的自适应空洞处理算法2744-2751

摘要：针对无线传感器网络贪婪地理路由协议中的路由空洞问题，提出一种高效的基于路标迭代提取和剔除的自适应空洞处理算法．该算法中，当探测包贪婪转发遇到空洞时，在网络拓扑局部平面化的基础上，以左（右）手法则提取空洞边界并沿其逆（顺）时针周边模式双向转发，同时，分布式地进行路标的迭代提取和剔除，直到获取的路标使得后续的数据包依次以它们为中间目标节点进行传输而不再遇到空洞为止．仿真结果表明，该协议能够以较小的控制开销代价获得次最优的传输路径，极大地提高了路由协议的性能，可以应用于无法消除路由空洞的大规模无线传感器网络贪婪地理路由协议．

一种基于磁盘介质的网络存储系统缓存2752-2765

摘要：随着计算规模越来越大，网络存储系统应用领域越来越广泛，对网络存储系统I／O性能要求也越来越高．在存储系统高负载的情况下，采用低速介质在客户机和网络存储系统的I／O路径上作为数据缓存也变得具有实际的意义．设计并实现了一种基于磁盘介质的存储系统块一级的缓存原型D—Cache．采用两级结构对磁盘缓存进行管理，并提出了相应的基于块一级的两级缓存管理算法．该管理算法有效地解决了因磁盘介质响应速度慢而带来的磁盘缓存管理难题，并通过位图的使用消除了磁盘缓存写Miss时的Copy on Write开销．原型系统的测试结果表明，在存储服务器高负载的情况下，缓存系统能够有效地提高系统的整体性能．

网格服务资源多维性能聚类任务调度2766-2775

摘要：网格计算是当前一个重要的研究领域，其中任务调度是一个基本组成部分，其性能直接影响到网格服务质量．为了缩短任务调度完成时间，提高任务调度性能，提出了一种网格资源多维性能聚类任务调度算法MPCGSR（task scheduling algorithm based on multidimensional performance clustering of grid service resources）．该算法根据网格环境下服务资源数量庞大、异构、多样的特点，预先以构建的网格服务资源超图模型为基础，结合小世界理论对服务资源进行多维性能聚类，将任务与聚类资源相匹配并实施调度．模拟实验结果表明，算法较之同类算法具有优越性，是一种有效的网格任务调度算法．

面向分布式证明的信任协商策略语言和方法2776-2786

摘要：现有信任协商语言对复杂的访问控制策略和协商策略以及信任分布式证明方法的支持都不够全面．在RT（role—based trust—management）语言基础上提出一种面向信任分布式证明和协商的策略语言RTP（role-based trust proving），其特点是能够支持信任分布式证明方法，可以定义复杂角色，保护信任证敏感信息并能避免信任证盲目搜索．给出了RTP语言及其推理规贝4的语法语义描述，介绍了一种基于RTP语言的信任分布式证明协商示例算法．实验结果表明，该算法支持RTP语言的功能，且比传统信任协商方法有很大的性能提升．

无线传感器网络中的地址分配协议2787-2798

摘要：地址用来标识节点，使能网络通信协议，在无线传感器网络中扮演重要角色．由于无线传感器网络中节点众多，再考虑其网络动态性，手动地为每个节点分配地址是一件繁琐甚至无法完成的工作，于是，地址分配协议成为必需．由于无线传感器网络自身所具有的特点，传统的DHCP协议和adhoc网络的地址分配协议对其不再适用．分析了无线传感器网络地址分配协议的必要性，总结了地址分配协议需要解决的问题和所面临的挑战，并对已有地址分配协议进行了分类．介绍和比较了当前有代表性的地址分配协议，并指出了它们的问题，分析了地址分配协议下一步研究的重点．

突破认证测试方法的局限性2799-2809

摘要：认证测试是一种用于证明安全协议认证属性的新方法，该方法能够简化协议认证属性的证明过程，但其局限性是无法应用于认证测试元素被多重加密的情况．指出Perrig和Song提出的认证测试改进方案在多个方面所存在的问题．在此基础上提出新的改进方案，并进行了形式化证明．新的认证测试定理突破了认证测试元素在整个协议消息中不能被加密的限制，扩展了认证测试理论的应用范围．

利用类型推理验证AdHoc安全路由协议2822-2833

摘要：提出一种基于类型推理的移动Ad-Hoc网络安全路由协议的形式化验证方法．定义了一种邻域限制通信演算NCCC（neighborhood-constrained communication calculus），包括演算的语法和基于规约的操作语义，在类型系统中描述了移动Ad-Hoe网络路由协议的安全属性，定义了近似攻击消息集用以精简Dolev-Yao攻击模型．还给出了该方法的一个协议验证实例．基于类型推理，该方法不仅能够验证协议的安全性，也可以得出针对协议的攻击手段．因为攻击集的精简，有效地缩减了推理空间．

语义网站点的发现与排序2834-2843

摘要：随着语义网中RDF数据的大量涌现，语义搜索引擎为用户搜索RDF数据带来了便利．但是，如何自动地发现包含语义网信息资源的站点，并高效地在语义网站点中收集语义网信息资源，一直是语义搜索引擎所面临的问题．首先介绍了语义网站点的链接模型．该模型刻画了语义网站点、语义网信息资源、RDF模型和语义网实体之间的关系．基于该模型讨论了语义网实体的归属问题，并进一步定义了语义网站点的发现规则；另外，从站点链接模型出发．定义了语义网站点依赖图，并给出了对语义网站点进行排序的算法．将相关算法在一个真实的语义搜索引擎中进行了初步测试滨验结果表明，所提出的方法可以有效地发现语义网站点并对站点进行排序．