基于二分决策图的特征模型验证方法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60528006, 60703065, 60873059 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant Nos.2006AA01Z156, 2007AA01Z123 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2005CB321805 (国家重点基础研究发展计划(973))


BDD-Based Approach to the Verification of Feature Models
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    特征模型是领域分析活动产生的具有复用价值的软件需求模型.对特征模型的复用通常采用定制的方式.特征模型定制中的一个重要问题是验证问题.该问题的存在是因为特征之间往往具有一定的约束关系,而一个合法的定制结果必须保证特征之间所有约束关系的被满足性.由于特征模型验证问题NP-hard所具有的性质,如何高效地进行特征模型的验证就成为一件相对困难的事情.在深入挖掘特征模型验证问题特殊性的基础上,将这种特殊性和二分决策图的结构特点进行了有效的结合,提出了一种通过对二分决策图的一次遍历即能实现特征模型验证的方法.需要指出的是,该方法并非试图在一般意义上解决特征模型验证问题中NP-hard的困难性,而是尽可能地利用该问题的特殊性,以提高处理特征模型定制问题的规模和效率.实验数据表明,相比较以前采用的验证方法,基于BDD(binary decision diagram)的方法在处理特征模型验证问题的规模和效率上都具有显著的提高.

    Abstract:

    The feature model is a reusable requirements model generated from the domain analysis. The reuse of feature models is usually achieved by a customizing-based approach. One important issue in feature models’ customization is the verification problem, caused by the fact that there are usually constraints among features, and that a valid customizing result must satisfy all these constraints. Because of the NP-hard nature of this problem, it is usually difficult to verify feature models in an efficient way. This paper presents a BDD (binary decision diagram)-based approach to verifying feature models by only traversing once to the nodes in BDDs, an approach that makes an efficient use of the BDD data structures based on the unique characteristics of feature models’ verification. It should be pointed out that this approach does not attempt to resolve the NP-hard difficulty of the verification problem in a general sense, but just tries to improve the scalability and efficiency of methods for feature models’ verification based on the utilization of this problem’s uniqueness. Experimental results show that this BDD-based approach is more efficient and can verify more complex feature models than the previous method.

    参考文献
    相似文献
    引证文献
引用本文

闫华,张伟,赵海燕,梅宏.基于二分决策图的特征模型验证方法.软件学报,2010,21(1):84-97

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2008-05-16
  • 最后修改日期:2008-10-28
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号