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

软件学报 2007年第09期杂志 文档列表

软件学报杂志算法设计与分析

量子克隆多播路由算法2063-2069

摘要：BSMA（boundedshortestmulticastalgorithm）被认为是最好的受限多播路由算法；然而，过长的计算时间限制了其应用．作为一种全局优化算法，遗传算法（GA）被越来越多地应用于解决多播路由问题．与传统的算法相比，遗传算法的全局搜索能力更强，但其易“早熟”的特点使它并不总是能够得到最优多播树．提出量子克隆多播路由算法，有效地解决了“遗传”多播路由算法中的“早熟”问题，量子交叉的引入，加快了算法的收敛速度．算法实现简单、控制灵活．仿真结果表明，该算法的性能优于BSMA算法和传统的遗传算法．

有Mate-Pairs的个体单体型MSR问题的参数化算法2070-2082

摘要：个体单体型MSR（minimumSNPremoval）问题是指如何利用个体的基因测序片断数据去掉最少的SNP（single—nucleotidepolymorphisms）位点，以确定该个体单体型的计算问题对此问题，Bafna等人提出了时间复杂度为O（2^kn^2m）的算法，其中，m为DN断总数，n为SNP位点总数，k为片断中洞（片断中的空值位点）的个数由于一个Mate—Pair片段中洞的个数可以达到100，因此，在片段数据中有Mate—Pair的情况下，Bafna的算法通常是不可行的．根据片段数据的特点提出了一个时间复杂度为D（n-1）（足广1）k22^2k＋（k1＋1）^2k＋nk2＋mkl）的新算法，其中，k1为一个片断覆盖的最大SNP位点数（不大于n），k2也为覆盖同一SNP位点的片段的最大数（通常不大于19），h为覆盖同一SNP位点且在该位点取空值的片断的最大数（不大于也）．该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系，在有Mate—Pair片断数据的情况下仍然能够有效地进行计算，具有良好的可扩展性和较高的实用价值．

Seventeenth International World Wide Web Conference （WWW2008）2082-2082

三维装箱问题的组合启发式算法2083-2089

摘要：通过组合拟人启发式和模拟退火算法，提出了三维装箱问题的组合启发式算法．拟人启发式算法的主要思想来源于日常砌墙中的策略，利用找点法以及水平和垂直参考线规则来控制装填过程-用模拟退火算法改进拟人启发式．经过一些数据的测试，实验结果表明，该算法能够同文献中的优秀算法竞争．

三元家庭基因数据的单体分型和单体型频率估计2090-2099

摘要：研究了在门德尔遗传定理和哈代—维恩伯格平衡假设下，三元家庭基因型数据的单体分型和单体型频率估计问题．过去的研究仅仅关注个体间没有联系或者含有一般家系信息的基因型数据，而对这种特殊的三元家庭关注得不够．考虑到HAPMAP数据库中有一部分数据就基于这种三元家庭，现在有越来越多的需求要求直接分析这种特殊的家系结构．提出一个两段式的三元家庭中单体型频率的估计方法：i）分型阶段，找出每一个三元家庭零重组单体构型；ii）频率估计阶段，在前一阶段得到的单体构型基础上，应用EM算法来估计单体型频率．在程序包TRIOHAP中用c语言实现了单体分型算法和EM算法，并且使用模拟和实际数据测试了TRIOHAP的有效性和效率．实验结果表明，TRIOHAP要比其他那些忽略了三元家庭信息的常见单体型频率估计软件运行快很多．进一步地，由于TRIOHAP利用了这些信息，其估计结果更加可靠．

P3P问题的多解现象的概率研究2100-2104

摘要：一般情况下，P3P问题可能出现1，2，3或4个解．但是，若3个控制点和摄像机光心这4点共圆，则会出现无穷多组解彳1用“蒙特卡洛，，方法模拟出P3P问题分别出现1,2，3，4个解的概率为0．9993，0、0007，0．0000，0．0000.结果论证了如下的事实，即在大多数情况下，P3P问题有唯一解．

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

高效的部分冗余容错编译：复制错误流关键子图2105-2116

摘要：传统的容错编译通常复制所有的计算并且使用完全冗余的存储单元来保证容错．这种完全冗余在存储空间和性能上的开销都是相当大的．在错误流分析的基础上提出错误流图的关键子图的概念以及通过关键结点和关键路径生成关键子图的方法，并设计了通过复制错误流关键子图实现部分冗余的算法．在保证有效容错能力的同时，部分冗余明显减小了经过容错编译的程序在存储空间和性能上的开销．实验显示，与复制全部错误流图的完全冗余相比，在结点覆盖率降低6．25％的情况下，部分冗余算法最多能够减少寄存器的使用数量6．25％，减少功耗超过17％，减少执行时间接近26％同时提高性能超过22％．

一种基于性能模型的中间件自配置框架2117-2129

摘要：高动态的计算环境使得QoS（quality of service）保障对于基于组件的分布式系统越来越重要，软件系统需要具备自我调整的能力以适应外部环境的变化．给出一种自适应的中间件配置框架，能够动态感知负载变化，并自动调整系统参数配置以保持用户所要求的服务质量．该框架的核心是一个基于分层排队网络的性能预测模型，用于指导搜索最优的资源配置，使性能需求得到最大的满足．在OnceAS应用服务器上进行原型实现，并以StockOnline应用做实验．比较了在使用和不使用该框架时的性能需求的满足情况、结果显示，在负载增加时，通过自配置框架的调控，应用性能需求的保障程度得到了较大的提升．

基于Assume—Guarantee搜索复用的C程序验证方法2130-2140

摘要：提出了一种基于Assume．Guarantee搜索复用的验证方法，对C程序源代码进行验证．其思想是，在程序的每点处都引入一个保守假设条件，并假设从任意点出发，变量取值满足该点假设条件的所有执行路径都不会违背给定性质，然后根据这些假设条件遍历所有可能的执行路径以验证给定的时序安全性质，并在遍历的过程中验证这些假设条件是否满足，如果不满足，则不断对其精化和加强．验证方法总是在保证假设条件可靠的前提下尽量使用较弱的条件，使得大量的执行路径由于满足假设条件而可以搜索复用，从而降低验证代价．应用该方法验证了Linux操作系统中SSL协议的实现程序openssl-0．9．6c满足ssL协议的初始握手规范．实验结果表明，该方法具有良好的实用性和可扩展性．

基于SPEM2XPDL模型转换的软件过程执行2141-2152

摘要：SPEM（soft ware process engineering metamodel）是国际标准化组织制定的标准元模型，正日益成为软件过程建模领域的行业标准，但在过程执行方面，SPEM还存在不足．将软件过程看作是一种特殊的工作流，提出了一种应用X-作流运行机制支持软件过程执行的方法．通过将SPEM模型转换为XPDL（XMLprocessdefinitionlanguage）模型，利用XPDL引擎支持SPEM模型的执行．制定了SPEM和XPDL之间的映射规则，设计了转换算法并开发了转换引擎．该方法被应用在SoftPM项目中，成功地基于XPDL引擎Shark实现了对软件过程模型的执行支持．

工作流时序约束模型分析与验证方法2153-2161

摘要：为了解决工作流时间建模与时序一致性验证问题，以时序逻辑和模型检查为基础，提出了一种工作流时间建模与时序一致性验证方法．该方法用一阶逻辑描述工作流模型及其时间信息，用时序逻辑描述工作流的时序约束用模型检查算法对时序约束进行验证与分析．该方法不是针对某一种时序约束提出来的，而是能够验证任何用时序逻辑描述的工作流时序约束．该方法还能够对未通过验证的时序约束提供工作流运行实例作为反例，帮助用户定位模型的问题．以一个工作流时间建模和时序一致性验证的实例证实了所提出方法的有效性．

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

基于多通道融合的连续手写识别纠错方法2162-2173

摘要：在基于识别的界面中用户的满意度不但由识别准确度决定，而且还受识别错误的纠正过程的影响提出一种基于多通道融合的连续手写笔迹识别错误的纠正方法．该方法允许用户通过口述书写内容纠正手写识别中的字符提取和识别的错误．该纠错方法的核心是一种多通道融合算法．该算法通过利用语音输入约束最优手写识别结果的搜索，可纠正手写字符的切分错和识别错．实验评估结果表明，该融合算法能够有效纠正错误，计算效率高与另外两种手写识别错误纠正方法相比，该方法具有更高的纠错效率．

形式概念分析对粗糙集理论的表示及扩展2174-2182

摘要：侧重于建立形式概念分析与粗糙集之间融合的理论基础．利用形式概念分析中名义梯级背景（nominalscale）的概念，对信息系统进行平面梯级（plainscaling）得到了衍生的形式背景．证明了粗糙集理论中的划分、上下近似、独立、依赖、约简等核心概念都可以在相应的衍生背景中进行表示．揭示了粗糙集理论在分析处理数据时的局限性．指出了利用梯级的方法可以扩展粗糙集理论．

交互式进化计算的适应值噪声及收敛鲁棒性2183-2193

摘要：噪声是影响进化计算（evolutionary computation，简称EC）算法性能的一个重要因素对于传统EC中的噪声，已有许多研究成果，但交互式进化计算（interactiveevolutionarycomputation，简称IEC）的噪声研究成果却较少．首先回顾了传统EC中噪声的定义、来源、类型及各种处理噪声的方法；其次，从IEC的理性用户观点出发，研究了IEC的适应值噪声及收敛鲁棒性．其中，空间的映射关系、个体间的占优关系以及IEC的收敛等是研究收敛鲁棒性的两个定理（强条件定理和弱条件定理）的基础．这两个定理表明，理性用户条件下的噪声不会影响算法全局收敛性在这两个定理的基础上进一步得出了如下结论：有效的适应度尺度变换是弱条件定理的一部分，IEC中“真”适应值是用户偏好等．并以不满足弱条件定理，即破坏算法收敛性为依据，给出了IEC中适应值噪声的狭义定义．实验进一步验证了这两个定理上述结论为进一步研究IEC作了必要的铺垫，

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

Xmesh：一个mesh—like片上网络拓扑结构2194-2204

摘要：针对片上网络（networkonchip，简称NoC）的节点数量少、距离近、物理实现复杂度受到限制的特点，提出了一种新的Xmesh拓扑结构，并为该结构提出了XM路由算法．该结构在经典的mesh结构的基础上添加了两个对角线型的回边，缩短了节点间的距离，而且路由计算的复杂性不高，实现的复杂度基本没有增加‘将Xmesh与经典的Mesh和Torus结构进行了理论分析比较，同时，在Popnet模拟器上基于均衡负载和热点负载两种负载模式进行性能比较．模拟结果表明Xmesh平均延时不到Mesh结构的70％对于均衡负载，当网络规模较小时，Xmesh的延时比Torus的更小；对于热点负载，当热点距离网络中心或者对角线比较近时，Xmesh的延时比Torus的小10％～30％．反之，其延时比Torus的大10％～30％．总的来说，Xmesh的性能与Torus比较接近，但其物理实现更为简单．Xmesh比Mesh结构的性能更好．

可扩展路由器控制平面的高性能通信模型2205-2215

摘要：可扩展路由器控制平面节点间通信的瓶颈问题是制约软件体系结构大规模扩展的关键因素．针对此问题，在传统的软件体系结构的支撑模型中引入了传输适配子层的结构，上行的数据流经特征抽取与已注册的任务进行模式匹配，从而完成了对控制信息流基于内容的分类与分流，提高了其有效通信率．进一步根据任务的分布率、分散数和流量率这3个特征对模型进行了性能分析，表明了适配层的引入可以消除面间冗余流量和通信的可扩展瓶颈，后通过实验验证了理论分析的正确性．

一种P2P环境下基于用户行为的语义检索方案2216-2225

摘要：受资源类型多样化、搜索复杂度的制约，现有的P2P文件共享系统中的搜索机制是基于文件名的关键字匹配，这种方法不能发现关键字与资源内容之间的深层关系，因此不能实现语义检索．针对这个问题，提出一种新的搜索方案，该方案建立在已有的搜索机制之上，利用用户的搜索行为和下载行为的规律自动发现关键字和资源间的深层关系，在底层的P2P网络上构建一个元数据空间以辅助搜索．该方案具有实现代价小、时间复杂度低、可进化和支持语义搜索的优点．在Maze系统上的实验表明，该方案具有较高的查询命中率和查询准确率．

一种基于覆盖网络拓扑的无结构P2P主动复制策略2226-2234

摘要：无结构P2P覆盖网络并非规则网络，也非纯粹的随机网络，结点在拓扑结构中体现出非对等性，在接收查询消息的数量上具有非均衡性研究了结点连接度分布、数据流行程度与搜索成功率之间的关系，并针对数据的不同流行程度给出了结点连接度的最优分配模型、最后给出了一种实现最优结点度分配的主动复制策略．实验结果表明，基于拓扑信息的主动复制是一种提高无结构P2P搜索性能的可行方法．