###
DOI:
Journal of Software:2010.21(1):84-97

基于二分决策图的特征模型验证方法
闫华,张伟,赵海燕,梅宏
(高可信软件技术教育部重点实验室(北京大学),北京 100871;北京大学 信息科学技术学院 软件研究所,北京 100871)
BDD-Based Approach to the Verification of Feature Models
YAN Hua,ZHANG Wei,ZHAO Hai-Yan,MEI Hong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 5579   Download 4762
Received:May 16, 2008    Revised:October 28, 2008
> 中文摘要: 特征模型是领域分析活动产生的具有复用价值的软件需求模型.对特征模型的复用通常采用定制的方式.特征模型定制中的一个重要问题是验证问题.该问题的存在是因为特征之间往往具有一定的约束关系,而一个合法的定制结果必须保证特征之间所有约束关系的被满足性.由于特征模型验证问题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.
文章编号:     中图分类号:    文献标志码:
基金项目: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)) 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))
Foundation items:
Reference text:

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

YAN Hua,ZHANG Wei,ZHAO Hai-Yan,MEI Hong.BDD-Based Approach to the Verification of Feature Models.Journal of Software,2010,21(1):84-97