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

软件学报 2010年第03期杂志 文档列表

软件学报杂志理论计算机科学

一种多到一子图同构检测方法401-414

摘要：提出一种方法来解决从多个小图到一个大图的子图同构检测问题，其中多个小图是预先给定的，而大图是用户在线提交的．首先，基于DFS编码提出一种小图集合的压缩组织方法：其次，提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法．另外，给出一种有效的基于数据挖掘的索引技术．分析和实验结果证实，所提出方法的在线计算代价远小于现有方法，在线执行时间比现有方法快约一个数量级，离线构造时间快一个数量级以上．

一种用于指针程序验证的指针逻辑415-426

摘要：本文改进并扩展先前为验证指针程序提出的指针逻辑，主要贡献是提出了合法访问路径集合的概念，极大地简化了访问路径上的基本运算，并使得指针逻辑推理规则变得易理解．另外，增加了局部推理规则和函数构造的推理规则，使得指针逻辑可以方便地用于有函数调用的场合．

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

一种宋词自动生成的遗传算法及其机器实现427-437

摘要：主要针对宋词这种特殊的汉语诗歌体裁，开展了有关自动生成算法及其实现方法的探索性研究．研究工作主要根据宋词特点设计了基于平仄的编码方式、基于句法和语义加权值的适应度函数、基于精英主义和赌算法的选择策略，采用部分映射和启发式交叉算子和启发式变异算子，从而构建了一种基于遗传算法的宋词生成计算模型并进行了系统实现．实验结果表明，所建立的计算模型及其软件系统，初步实现了机器自动生成宋词的目标，对于给定的主题词和词牌，基本上能够自动生成有一定欣赏价值的宋词．论文的工作也填补了我国在汉语诗歌自动生成研究方面的不足．

基于动态概率路径事件模型的RFID数据填补算法438-451

摘要：RFID数据采集过程中漏读现象频频发生，降低了RFID（radio frequency identification）应用中查询结果的准确性．目前解决漏读问题的算法主要是以RFID原始读数为粒度，并基于标签自身历史读数进行窗口平滑，这种作法会填补许多与查询无关的冗余数据，并且在多逻辑区域参与的复杂应用中，填补准确率较差．为解决上述问题，首次将RFID数据从数据层抽象到逻辑区域层作为处理的粒度，提出3种基于动态概率路径事件模型的数据填补算法，通过挖掘已知的区域事件的顺序相关性来对后续发生的事件进行判断和填补．进一步，增加对时间因素的考虑，对概率路径事件模型进行扩展．大量实验证明，提出的各个算法在不同的情况下有着不同的性能优势，并且在精简性和准确性上要高于现有的策略．

一种基于特征捆绑计算模型的物体识别方法452-460

摘要：利用一种特征捆绑计算模型，以Gabor特征作为模型的初级特征，将相关统计量作为实现特征捆绑的基础，提出了一种物体识别方法．并实现了一组物体识别实验，结果显示，该方法能够进行较快速而准确地识别，说明了此方法和所使用的特征捆绑计算模型的有效性．

多线程程序时序分析的隐Markov模型461-472

摘要：针对多线程程序数据竞争分析与检测困难的问题，提出一种基于隐Markov模型的多线程程序时序分析方法．用随机变量不确定性刻画不同线程之间时序上的交互关系，分析数据竞争条件下程序不确定结果的概率分布情况；建立多线程程序时序分析的隐Markov模型，使用Baum—welch和前向算法仿真上下文对程序实际运行状态的影响．实验结果表明，该模型能够快速有效反映多线程执行时序，用于指导多线程程序时序竞争检测过程．

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

传感器网络中基于蚁群算法的实时查询处理473-489

摘要：无线传感器网络因不同应用而被广泛部署于各种场合，通常被视为分布式数据库．可以通过向该类数据库查询请求来获取事件相关的响应信息．一些具有实时需求的应用对查询时延要求较高，而目前存在的查询算法通常不能很好地满足实时查询应用的需求．针对此类特定应用，提出了基于蚁群优化的实时查询处理算法，该算法采用基于事件重要性的分环存储策略和基于蚁群算法的分布式搜索机制，充分利用蚁群优化算法的自组织和正反馈等特征，综合提高查询处理算法的节能性、实时性及查询请求接受率，为分布式动态并行实时查询应用提供新的思路．执行过程仅需局部环境信息即可有效获取指定事件信息并动态确定事件副本的数目及其位置．理论分析和实验表明，此算法既能在一定程度上提高节能性和查询成功率，又能显著缩短查询时延，与现有的算法相比，具有明显的优越性．

延迟容忍传感器网络基于相对距离的数据传输490-504

摘要：延迟容忍移动无线传感器网络（delay tolerant mobile sensor network，简称DTMSN）用于广泛数据收集．一与传统的传感器网络不同，DTMSN具有节点移动性、间歇连通性并且能够容忍适当的延迟，因此传统传感器网络的数据收集算法不能适用．提出了一种基于相对距离感知的动态数据传输策略RDAD（relative distance-aware data deliveryscheme）．RDAD采用传感器节点到汇聚点（sinknoae）的相对距离来计算节点传输概率的大小，并以此作为消息（message）传输时选择下一跳的依据，为优化复本管理，RDAD引入消息的生存时间ST（survival time）和消息最大复制数MR（maximal repljcation）决定队列中消息传递的优先顺序和丢弃原则．模拟实验表明，与现有的几种DTMSN数据传输算法相比，RDAD能够以较低的数据传输能耗和传输延迟获得较高的数据传输成功率，并且具有相对较长的网络寿命．

基于信誉机制的域间路由安全协同管理方法505-515

摘要：如何抑制虚假路由的传播和恶意路由行为的发生，是域间路由安全管理的重要研究内容，对自治系统路由行为进行可信性评价和监督是其中的关键技术．设计了一种用于评价自治系统路由行为可信性的分布式协同信誉机制．该机制基于历史路由的有效性统计结果，采用后验概率分析的方法，由多个自治系统按照自组织协同的方式完成对目标自治系统的信誉计算，并将信誉计算结果作为度量该自治系统路由行为可信性的依据．实验结果表明，该机制能够抑制不良路由行为，有效提高域间路由系统的总体安全性，还能够为路由可信性分析和故障诊断提供依据，支持渐进式部署，无须修改BGP协议，具有良好的可实施性．

基于时间部署的无线传感器网络密钥管理方案516-527

摘要：提出一种基于时间部署的随机密钥管理方案．该方案采用了特殊的两级随机密钥预分配和清除机制以及按时间顺序的成组部署方法：每个传感器节点从多个密钥池中随机选择密钥并在一定条件下删除相关的密钥；所有传感器节点被组织成部署组并按时间顺序被部署到网络中．与经典的随机密钥管理方案相比，该方案在为成对密钥的生成提供了较高的节点连通度的同时，提高了节点资源利用率并且增强了网络抵抗节点受损攻击的能力．

一种保证时延的关键流路由调整算法528-538

摘要：互联网中流量分布的不均衡会导致网络拥塞、网络资源得不到有效利用．而为了负载均衡，现有算法调整路由又会造成新路径过长，服务质量降低．提出了一种路由调整算法LCBA（length-constrained most balanced algorithm），在保证时延的基础上降低网络最大带宽利用率．基于Abilene2网络拓扑和真实流量的实验结果表明，LCBA算法能够有效缓解骨干网拥塞，最多可以降低最大带宽利用率近50％．仿真实验结果显示：与现有算法相比，该算法能够同时满足关键流路径长度和最大带宽利用率两方面的要求．此外，算法复杂度为O（N^2 logN），好于大部分路由调整算法．

一种基于安全状态转移的简并测试集生成方法539-547

摘要：在总结前人工作的基础上，结合安全操作系统对测试的特殊需求，提出了简并测试集（degenerate test set，简称DTS）的概念，设计了一种使用模型检测的基于安全状态转移的高效测试集生成方法．该方法以状态转移为化简对象，在利用模型检测技术生成测试用例的同时，归并相同的状态转移并化简需求集中的冗余属性，从而最终达到化简测试集的目的．在此基础上，探讨了单个用例失败时用例集的有效性问题，并对DTS生成算法进行了改进．实验结果表明，该方法可以有效地对测试集中的冗余进行化简．

基于冲突分类模型的冲突解析算法548-563

摘要：IEEE802．11网络中的传统退避算法利用竞争窗口机制进行冲突解析，冲突节点被重新分布在一个更大的窗口范围内以避免冲突．然而，只要这些分布窗口之间存在着交集，就仍有可能引发冲突．为了解决一个问题，提出了一种冲突分类模型，将网络中的分组冲突分成交叉冲突和同级冲突，并且提出针对这两种不同类型的冲突应该采取不同的策略进行解析，利用顺序离散窗口分布机制（sequential discrete window distribution，简称SDWD）解析交叉冲突，通过节点分布窗口的离散化避免交叉冲突；同时，通过设置合适的分布窗口大小在同级冲突概率和分组延迟之间取得折衷．在此基础上，实现了两种冲突解析算法：冲突分类解析算法（cross collision resolution，简称CR）和无冲突分类解析算法（collision-free CCR，简称CF-CCR）．仿真结果表明，同IEEE802．11DCF协议相比，CCR和CF-CCR在冲突率、吞吐量、分组延迟、公平性以及延迟抖动方面均有提高．并且，这两个算法在不同场合表现出不同的优越性．

基于定长时隙的多跳AdHoc网络DCF协议马尔可夫链模型564-574

摘要：指出了现有的基于不定长时隙的DCF协议马尔可夫链模型的局限性，并在详细分析多跳adhoc网络环境中DCF协议建模的难点问题基础上，提出了一种基于定长时隙的多跳adhoe网络DCF协议马尔可夫链模型．通过模型的求解，得到了反映多跳adhoe网络饱和吞吐量性能的相关性能指标的理论值，并结合GloMoSim网络仿真环境中的仿真实验，证明了模型的有效性．

本刊实行在线出版的通知F0004-F0004

摘要：为了加快出版速度，提高传播时效，促进学科发展，本刊对审查通过待发表的文章实行在线出版。录用文章在完成版式和内容的编辑加工及校对之后将在我刊网站上提前在线出版。在线出版，亦称网上预发表，指的是在印刷版出版之前，文章的电子版本在网上提前发表，除没有年、卷、期、页码之外，其内容与印刷版完全一致，