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

软件学报 2011年第05期杂志 文档列表

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

求解VLSI电路划分问题的混合粒子群优化算法833-842

摘要：电路划分是VLSI物理设计过程中的一个关键阶段．该问题本质上是一个NP困难的组合优化问题．针对该问题，提出了一种带FM策略的混合粒子群优化算法．引入遗传算法的两点交叉算子和随机两点交换变异算子，保证了粒子在位置更新后依然可行；为了提高算法的局部搜索能力，将具有较强局部搜索能力的FM策略融入算法的位置更新；设计了种群多样性变异策略，提高了种群多样性，避免了易陷入局部最优的缺陷．对ISCAS89标准测试电路的仿真实验结果表明，所构造的算法是有效的．

求解长方体Packing问题的捆绑穴度算法843-851

摘要：在穴度方法的基础上结合捆绑策略，为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法．试算了由Loh和Nee于1992年提出的15个经典算例，对其中的困难算例LN2，取得了98．2％的空间利用率，比目前的最好纪录高1．6个百分点；对另一个困难算例LN6，取得了96．2％的空间利用率，与目前的最好纪录持平；对其他13个较为容易的算例均取得了最优的布局，与目前的最好纪录持平．总体而言，15个算例的平均空间利用率为70．96％，在整体空间利用率上达到了较好的效果．

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

基于偏好推荐的可信服务选择852-864

摘要：针对现有服务选择中服务推荐技术的不足，提出一种基于偏好推荐的服务选择（trustworthy services selection based on preference recommendation，简称TSSPR）方法．首先搜索一组偏好相似的推荐用户，并通过皮尔逊相关系数计算用户的评价相似度，然后基于用户的推荐等级、领域相关度和评价相似度等对用户的推荐信息进行过滤，从而使推荐信息更为可信．模拟实验结果表明，通过正确的参数设置，该方法能够有效地解决推荐算法中冷启动、拒葬信息不缝确等问颗．

开放环境特性感知技术865-876

摘要：提出了一个开放环境特性描述框架．该框架支持便捷地、形式化地描述异步环境的各种特性，包括那些既有技术不能处理的时序特性．该框架还引入了谓词检测技术，支持高效的环境特性感知机制的实现．开发了一个开放环境特性感知中间件平台，并通过详细的案例分析展示了如何基于所提出的环境特性描述框架与中间件平台，高效地感知环境特性，支持可信软件系统的构建．

量子程序设计语言NDQJava-2877-886

摘要：简述了量子程序设计语言NDQJava-2．该语言是在NDQJava的基础上增添了量子条件语句、量子循环语句、量子子程序、量子模块以及量子异常处理机制等量子成分，使其成为一种结构化的量子程序设计语言．书写量子程序的实践表明，相对于NDQJava而言，NDQJava．2是一种更为实用、易读，其成分设定更为合适的量子程序设计语言．

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

基于句法路径的情感评价单元识别887-898

摘要：不同于已有的基于手工模板和规则的方法，提出了一种基于句法路径的情感评价单元自动识别方法．该方法自动获取句法路径来描述评价对象及其评价词语之间的修饰关系，并通过计算句法路径编辑距离来改进情感评价单元抽取的系统性能．实验语料来自数码相机和MP3播放器两个典型的电子产品领域．实验结果表明：（1）句法路径能够有效描述评价对象及其评价词语之间的关系，对情感评价单元的识别有很大帮助；（2）基于编辑距离的句法路径改进策略能够进一步提高情感评价单元识别的系统性能．

用态势模型预测基因表达式编程的进化难度899-913

摘要：在基因表达式编程（gene expression programming，简称GEP）中，由于不同问题得到的适应度-距离相关系数（fitness—distance correlation．简称FDC）值很相近，所以难以用FDC预测GEP求解不同问题的进化难度．为了解决该问题，提出了态势模型及其区间密度指标来预测GEP的进化难度．主要工作包括：（1）提出了GEP染色体之间的距离和态势模型的新概念；（2）提出了态势模型中的区间密度指标：（3）从动力学角度证明了态势模型是对GEP原搜索空间的一种映射，并且该映射保持了种群在原搜索空间中移动的动力学性质；（4）分析了用态势模型区间密度预测GEP进化难度的合理性：（5）用实验验证了区间密度能够准确预测GEP求解问题的进化难度．

智能规划中的可纳子目标排序914-928

摘要：提出了一种称为可纳子目标排序（admissible subgoal ordering，简称ASO）的排序关系，给出了可纳排序的形式化定义并讨论其对增量式规划的重要性．随后介绍了原子依赖关系理论和原子依赖图技术，能够在多项式时间内近似求解可纳子目标排序关系．最后给出了一种计算可纳子目标序列的算法．其所有思想已经在规划系统ASOP中实现通过在国际规划大赛标准测试领域问题上的实验,其结果表明，该方法能够有效地求解大规模的规划问题，并能极大地改善规划性能．

基于等价类划分的配置求解与解释计算929-937

摘要：基于约束的配置模型中会有一些变量之间不存在任何直接或间接的约束关系，这样的变量之间进行约束传播不会互相影响取值．基于配置问题的这一特点，提出了一种等价类划分的思想，用于构造产品模型时的预处理技术，可以有效地将原问题划分为若干子问题，证明了这些子问题可以分别处理．分别采用两种回溯策略对求解效率进行了测试，结果表明能够有效地提高求解效率．最后，等价类划分方法与计算解释的QUICKXPLAIN算法集成计算冲突解释，测试结果表明，经过等价粪划分后，同样可以有效地提高计算解释的效率．

一种O（2．983^n）时间复杂度的最优联盟结构生成算法938-950

摘要：首先，在有限整数集上建立有效拆分关系，在联盟集上建立有效二部分解关系，并设计了一种EOCS（effectlve oprimal coalition structure）算法．该算法采用自底向上方式，只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值，从而降低了二部分解的数量．随后，利用函数的克林闭包特性证明了EOCS算法的正确性，利用积分极限定理证明了EOCS算法时间复杂度的下界是Ω（2．818^n），用时间序列分析方法求出了EOCS算法的上界是D（2．983^n）．最后，将EOCS算法与其他算法作了对比，指出无论联盟值满足何种概率分布，EOCS算法都能在O（2．983^n）时间内找出最优联盟结构．Rothkopf提出的DP（dynamic programming）算法和Rahwan提出的IDP（improved dynamic programming）算法能够在O（3^n）时间内求出最优联盟结构．所作的EOCS算法设计、正确性证明、时间复杂度的上下界分析都是对Rothkopf及Rahwan等人相关工作的改进和提高．

软件学报杂志数据库技术

从链接密度遍历序列中挖掘网络社团的层次结构951-961

摘要：提出一种称为TRAVEL的网络聚类算法．它能够产生包含所有可能密度聚类的网络链接遍历序列，并从中自动发现网络的全局优化聚类．然后，遍历序列被转换为连续子区间堆结构．在此基础上，提出一种聚类算法HCLU，可以无须用户干预地从连续子区间堆中自动发现网络的层次聚类边界．在真实网络以及计算机生成的仿真网络数据集上的实验结果表明，所提出的算法比目前的基准方法具有更高的聚类精度．此外，算法能够从各种带有噪声的网络中发现无冗余且鲁棒的层次社团结构．

紧致依赖与内涵亏值962-971

摘要：提出了“内涵亏值”与“紧致依赖”的概念，证明了由“紧致依赖”组成的依赖基对于“左部加属性、右部枣属性”这一规则的公理系统是无冗余而完整的，由此发现了除Guigues-Duquenne基以外还有其他无冗余完整依赖基，改变了只有唯一的一个无冗余完整依赖基的传统观念，揭开了寻找多种无冗余完整依赖基以满足多样化需求的序幕．

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

支持多点交互同步的应用层组播路由算法972-985

摘要：提出了在多源组播路由过程中解决交互同步问题而无须使用同步控制器的思想，在这种思想的基础上进一步实现低延迟组播．主要贡献包括：（1）建立面向多点交互过程的同步模型及证明支持多点交互同步的组播路由定理；（2）提出一种有效的、低延迟的、支持多点交互同步的应用层组播路由算法；（3）采用教学方法对新算法和现有相关算法进行性能分析和对比．最后，通过仿真实验和实际应用表明，新算法是正确和有效的．

无锁同步的细粒度并行介度中心算法986-995

摘要：通过结合体系结构和算法进行研究发现，基于锁的同步机制是细粒度并行介度中心（betweenness centrality,简称BC）算法在现有多核平台上高效执行的主要瓶颈．提出了一种消除锁同步的数据驱动（daca-centric）并行算法，在AMD32核SMP和Intel 8核SMP两个平台上获得了2倍左右的加速比．

用于自动证据分析的层次化入侵场景重构方法996-1008

摘要：为了能够自动分析入侵证据，提出了一种层次化入侵场景重构方法．其原理是：首先，基于报警关联技术重构出入侵者的抽象攻击步骤及步骤间关系；然后，基于攻击特征和依赖追踪技术重构出各步骤的行为细节；最后，通过两层重构结果的彼此映射，调整获得完整的入侵行为图．基于DARP A2000的实验结果表明，该方法的重构结果准确性和完备性均比较高，而且抽象与细节相结合的表示方法更易理解，也更适合作为法律证据．而与现有方法相比，该方法在重构场景的完整性、适用行为的复杂性以及方法安全性等方面也有一定的改善．

拓扑隐藏的MANET安全多路径路由协议1009-1019

摘要：分析了移动自组网（mobile ad hoc network，简称MANET）暴露拓扑带来的安全问题，提出了一种拓扑隐藏的安全多路径路由协议．在路由发现过程中，不在路由包中携带任何路径信息，从而有效隐藏网络拓扑通过按需的邻居发现进行身份认证并建立路由表项，最终采用排除节点的方法实现多路径的选取：在路由维护过程中，设计了专门的错误发现机制以检验所选路径的有效性和安全性．该协议综合考虑时间因素和路径长度因素，实现了安全的最短路径确定．安全分析表明，该方案可以抵御黑洞攻击、虫洞攻击、mshmg攻击和sybil等典型攻击，同时对一般类型的攻击也具有抵御能力．仿真结果表明，与SRP（secure routing protocol）这种典型的安全多路径方案相比，该方案能够找到更多节点不相交的多路径；在普通场景中，该方案没有对协议性能带来额外影响；在黑洞攻击场景中，该方案只需付出一定的信令开销即可大幅度提高数据包转发率，可有效抵御黑洞攻击．

多级安全中敏感标记的最优化挖掘1020-1030

摘要：提出了一种自底向上的方法来实现系统迁移过程中自动和科学的访问控制策略转换．首先对多级安全中敏感标记最优化挖掘问题作了形式化描述，证明了该问题是NP完全问题，不存在多项式时间算法．然后，在此基础上提出了基于层次聚类和遗传算法的近似最优化挖掘算法，将该问题分解为范畴划分和密级分配两个阶段．最后，实验结果表明，算法能够有效地挖掘出最优的敏感标记．该方法可以应用于等级保护工作中的系统迁移工程．

高效的标准模型下基于身份认证密钥协商协议1031-1040

摘要：在Waters的基于身份加密方案的基础上提出了一种高效的基于身份认证密钥协商协议，并在标准模型下证明了该协议的安全性．与目前已有的同类协议相比，该协议具有更高的效率和更弱的安全假设，并具有已知密钥安全和前向安全性等安全性质，同时能够抵抗未知密钥共享和密钥泄露伪装攻击.在该协议基础上，构造了防止用户密钥生成中心获取会话密钥的协议，以满足需要防止密钥托管的应用需求，并采用安全的消息认证码算法为该协议增加了密钥确认过程．