一种需求变更影响的评估算法

计 算 机 工 程 第 32 卷 第23期

Vol.32 No.23 Computer Engineering · 软件技术与数据库 ·

文章编号：1000—3428(2006)23—0082—03

文献标识码：A

2006年12月

December 2006

中图分类号：TP311

一种需求变更影响的评估算法

杨鹤标，张继敏，朱玉全

(江苏大学计算机科学与通信工程学院，镇江 212013)

摘 要：通过对需求依赖关系的分析与归纳，给出了需求依赖关系的依赖形式；采用回溯法来搜索和界定需求变更的影响范围，给出了变更影响的量化方法；从需求依赖关系的视角，设计了一个可以量化评估需求变更影响的算法。通过一个“样例学习”的例子，展现了该评估算法的稳定性。

关键词：需求变更；依赖关系；评估算法

Evaluation Algorithm for Impact of Requirements Change

YANG Hebiao, ZHANG Jimin, ZHU Yuquan

(School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang 212013)

【Abstract 】The relations of the dependencies are found and formalized. The scope of impact raised by requirements change is confirmed bybacktracing algorithm, and the impact is quantitively described by using impact factor.Then the algorithm is presented to evaluate the impact of thisquantitive description. An example of case study shows the feasibility of this evaluation algorithm. 【Key words】Requirement change; Dependency; Evaluation algorithm

在软件生命周期中发生需求变更是无法回避的[1]。需求变更对软件项目进度控制、成本核算、开发周期等方面有着巨大的影响。需求变更影响评估是指：确定需求变更影响范围及分析变更带来潜在的影响[2]。现有需求变更影响评估的主要方法是借助需求跟踪链或矩阵来确定需求变更给设计、编码等软件产品元素带来的影响[3~5]。由于现有的评估方法极少地考虑依赖因素所带来的影响，给评估结果带来了不确定性。因而在评估过程中，如何搜索和界定依赖关系对评估的影响范围变得尤为重要。

针对上述问题，本文对需求间依赖关系进行了分析与归纳，给出了对需求依赖关系的依赖形式；采用回溯法搜索依赖关系矩阵，确定需求变更的影响范围，并对影响程度进行了量化处理；最后设计了评估变更影响的算法；并在研究实例上进行了验证，对评估结果的可信度进行了分析。

定义3 如果∀R a ∀R b (dep(Ra ，R b ) ∧¬childdep(Ra , R b )) ，则称R b 对R a 完全依赖，记为fulldep(Ra , Rb ) ，需求R a 的变更就会对R b 产生影响。

R a ) ∧¬dep(Ra - Rc , Rb )) ，则称R b 对R a 子集依赖，记为childdep(Ra ,R b ) ；否则R b 对R a 非子集依赖，记为¬childdep (Ra ,R b ) 。

定义4 如果∀R a ∀R b ∃R c (dep(Ra , Rb ) ∧ ( Rc ⊆R b ) ∧¬dep(Ra , Rb - Rc )) ，那么称R b 对R a 父集依赖，记为fardep(Ra ,R b ) 。在需求R a 与需求R b 的依赖关系中，仅R c ⊆ R b 受到R a 的变更影响。

子集依赖和父集依赖的存在，可以认为是需求建模粒度过大而产生的。这种非原子型的需求模型可能掩盖了部分需求间的精确依赖关系，同时也可能导致依赖关系对变更影响描述的不精确性和不同步性。

需求依赖关系具有两个性质： (1)依赖关系传递性

如果∀R a ∀R b ∀R c (dep(Ra ,R b ) ∧¬childdep(Ra , Rb ) ∧dep(Rb ，R c ) ∧¬ childdep(Rb , Rc )) ，则称R c 对R a 传递 依赖。

(2)不可逆性

如果∀R a ∀R b (dep(Ra ，R b ) ∧¬ dep(Ra ，R b )) ，则需求R b 发生变化不会对需求R a 元产生影响。 定义5 如果∀R 1∀R 2…∀R n ((dep(R1, R 2) ∧ ¬childdep(R1, R 2) ∧…∧dep(Ri-1, R i ) ∧¬childdep(Ri-1, R i ) ∧dep(Ri, R 1) ∧¬childdep(Ri, R 1))(i>=2)，则称R 1,R 2,…,Rn 之

1 需求依赖关系

在一个软件系统中，需求依赖关系是普遍存在的，并且存在着多种的依赖关系[6~8]。由于需求之间的依赖关系的存在，使得某需求发生变更后，势必对其相关的需求产生影响。因此，合理的确定需求变更影响范围是评估结果有效性的关键所在。

1.1 需求依赖关系定义

定义1 如果一个需求R s 变更时，要求另一需求R t 也要发生相应的变化，则称为需求R t 依赖于R s ，记为dep(Rs ,R t ) 。如果需求R t 不依赖于需求R s ，则记为¬dep(Rs ,R t ) ，其中R s 称为依赖源需求，R t 称为依赖目标需求。

1.2 需求依赖关系类型及性质

需求依赖关系形式多样，关系复杂，综合起来可将需求依赖关系归纳为4类：子集依赖关系，完全依赖关系，父集依赖关系，回路依赖关系。

定义2 如果∀R a ∀R b (dep(Ra ，R b )) ，仅当∃R c ((Rc ⊆ —82—

作者简介：杨鹤标(1960－) ，男，副教授，主研方向：数据库，软件体系结构，信息系统和软件工程；张继敏，硕士生；朱玉全，博士、副教授

收稿日期：2006-07-24 E-mail ：[email protected]

间的关系为回路依赖关系，记为loopdep(R1,R 2,…,Rn ) 。

回路依赖关系是结构上的一种强耦合关系，它降低了模型对变化的适应能力和可复用的程度。

else

//输出依赖关系集及依赖关系路径;} } }}

2 确定需求变更依赖集

本文采用回溯算法来求解需求间的依赖关系。 2.1 解空间构成

算法中问题的解空间用有向图来表示。有向图G=(NG ,E G ) ，其中N G ={Ri| i=1..n }组成，Ri 为需求，E G ⊆N G ×N G ，对于任意∈E G ，则表示dep(u,v)，且称v 为弧尾，称u 为弧头。以v 为头的弧的数目称为v 的入度；以顶点u 为尾的弧的数目称为u 的出度。用邻接矩阵作为有向图G 的存储结构，邻接矩阵定义为

1，若∈E

A[i,j]=0, 若∉E

3 需求变更影响评估算法

3.1 影响因子

上述算法给出了需求变更的影响范围全集。为度量需求之间的依赖及影响的强度，采用如下的公式量化两个需求间的影响因子：

FI(Rs,Rt)=workload|Rt/workload|Rs,dep(Rs,Rt)∧change(Rs) (1)

{

2.2 解空间结构

将n 个需求按1,2,…,n进行编号，解空间结构可表示为一棵高为n+1的完全n 叉树。解空间第i 层(i≤n) 中每个结点都有n 个儿子，每个儿子对应于用N G 中可能存在的依赖关系之一。n+1层为叶结点。图1示例了一棵三元需求的解空

图1 n=3时的解空间排列树

需求Rs 发生变更后，式(1)中的source|Rs 表示在R s 上追加的工作量，而Rt 受到Rs 变更的影响，workload|Rt为在Rt 上增加的工作量。

在FI(Rs,Rt)量化过程中，由于涉及众多的因素，如开发者的个体能力、工程计划的合理性、功能结构的复杂度规模等都可能影响到FI(Rs,Rt)量化值的准确性，在FI(Rs,Rt)生成过程中应在对经验数据的统计分析结果的基础上，可依据具体情况进行调整。

3.2 影响程度的度量

根据上述影响因子的量化方法，当变更发生时对整个系统的影响程度可用所有由变更而发生的工作量增量来描述。

设Ws 为依赖源R s 工作增量，Rt 依赖于R s ，则变更后工作增量DI 计算公式如下：

DI=∑Ws*FI(Rs,Rt) (2)

图2为一需求依赖关系图，设FI(R1,R 2)=0.5,FI(R2,R 3)=1.4, FI(R2,R 4)=0.8。

其中2到n+1层的结点为需求结点。

2.3 算法描述

算法采用深度优先搜索法遍历解空间进行求解。在算法递归Backtrack 中，当i>n时，算法搜索到叶结点，得到一组依赖关系集。假设搜索的初始需求结点为i 0。

当i ≤n 时，当前扩展结点是解空间内部结点，该结点有n 个儿子，在此检查其可行性，以深度优先的方式对可行子树搜索，或剪去不可行子树。

相互关系的依赖确定，每搜索到一个新的结点i 时，检测图G 是否存在i 0到i 和顶点i 到i 0的边，如果存在，则结点i 0和i 间存在相互依赖关系。

当i>=3时，检测图G 是否存在从顶点i-1到i 和顶点i 到i 0的边，如果存在，找到一条回路。搜索过程中用x[ ]存放当前解。递归算法如下：

Backtrack (i) {

if (i>n) 输出依赖关系集及依赖关系路径 else {

if(A[x[1],x[i]]=1&&A[x[i],x[1]]=1) //输出回路依赖关系及依赖关系路径; if (i>=3)

if(A[x[i-1],x[i]]=1&&A[x[i],x[1]]=1) //输出回路依赖关系及依赖关系路径; else {

for(j:=1;j

x[i]:=j; //选择下一搜索顶点; if(A[x[i-1],x[j]]=1) backtrack(i+1);

图2 需求依赖关系

假定R 1变更的W1 =4，则利用式(2)可得：R 2应增加的

工作量为W1*FI(R1,R 2)=4*0.5=2；R 3应增加的工作量为W2* FI(R2,R 3)=2*1.4=2.8；R 4应增加的工作量为W2*FI (R2,R 4)=2*0.8=1.6。这样，变更后的工作增量DI=2.8+1.6+ 2=6.4。

3.3 评估算法

采用第2节的算法，获得需求依赖关系初始状态下的影响全集用C a 来表示。当系统部分需求发生变更时，评估需求的变更所引起的蔓延现象，对系统所产生的影响的评估的算法步骤如下：

(1)从全集C a 中抽取需要进行评估的需求变更影响集。其方法：抽取以需求变更源为树根的影响集；

(2)消去变更影响集中的冗余依赖关系。其方法：用层叠法消去影响集中重复的结点和路径分枝，得到需求变更所产生影响的最小依赖子集；

(3)采用式(1)，进行影响的量化处理； (4)采用式(2)，进行评估计算。 评估的算法设计如下：

采用邻接矩阵存储变更影响集，初始时a[i, j]=0; i,j=1,2,…,n；假设：需求变更源集合SETcs= {Ri | Ri⊆N}。其中，初始时需求的工作量集InitSet={| Ri∈SETcs }，

Wi 为工作量。变更后需求的工作量集EvaSet={| Ri∈ImpactSet}，其中，Wi 为工作量。

—83—

需求Rs 变更影响的顶点集合ImpactSet(Rs) = {Ri | Ri⊆C a }。

算法1 EliminateRredundance用于消去影响集中冗余依赖关系并进行量化处理。

EliminateRredundance (a,ImpactSet) { for ( each ∈ImpactSet ) { a[Rs,Rt]= FI(Rs,Rt); }}

算法的计算，可得评估数据如表3所示。评估结果为算法计算结果，统计结果为开发过程中测算结果。

表3 评估结果

需求号 评估结果 统计结果

R 14.03.5

R 24.84.0

R 3

R 4

R 5

R 6

R 8 6.417.10

算法2 Evaluation完成评估计算

Evaluation() {

for ( each Ri∈SETcs) {

ImpactSet=Ca (Ri); //获取需求Ri 变更的影响集 EliminateRredundance (a,ImpactSet); //消去冗余依赖 }

for ( each Ri ∈SETcs){ 从IniSet 集中获取Ri 对应的Wi; Rs=Ri; Wsi:=Wi;

EvaSet= EvaSet∪{; //加入评估集

for (∀Rt ∈ImpactSet(Ri)&&∈E(ImpactSet(Ri)){ WtI:= Wsi*a[Rs,Rt];

EvaSet= EvaSet∪{}；//加入评估集 Rs:=Rt; WsI:=WtI; }}

//比较EvaSet 与IniSet 得到影响评估结果}

通过对上表的分析，可得结论：

(1)最小依赖子集与需求变更的影响范围一致。

(2)即便受影响因子的精确性以及评估参数缺失影响，通过表3中统计与评估结果的对比，可以看出，需求变更的影响与工作增量的趋势是一致的。

5 结语

本文从需求依赖关系的角度讨论了需求变更对系统的影响程度，给出了一个基于需求依赖的变更评估算法，在一个实际工程开发阶段中验证了这一算法的稳定性。然而，鉴于需求依赖关系自身存在的多层面多阶段的复杂性，要精确描述需求间的所有依赖关系以及对各种不同的依赖给出一个相对合理的度量体系不是一蹴而就的，它是一个需要不断迭代，不断完善的过程。对于需求间依赖关系定性和定量的分析，依赖关系量度体系的更合理更精确的数学描述，以及需求及需求依赖关系在软件开发过程不同阶段的进化过程中进一步产生的新的依赖关系等，这一系列更复杂的问题还有待在后续的工作中作更深入的研究。

参考文献

4 研究实例

本节通过一个研究实例来验证前节所提出的评估算法。实例中给出了一组需求及其之间的依赖关系，如图3所示。

1 Boehm B W. Software Engineering Economics[M]. New Jersey: Prentice-Hall, Inc., Englewood Cliffs, 1981.

2 Ramzan S, Ikram N. Decision in Requirement Change Management

图3 需求及依赖集实例

Information and Communication Technologies[C]. Proc. of the 1st Inter- national Conference on ICIT, 2005-08: 27-28.

3 Amold R S, Bohner S A. Impact Analysis-towards a Framework for Comparison[C]. Proceedings of the International Conference on Software Maintenance, 1993: 292-301.

4 Strens M R, Sugden R C. Change Analysis: A Step Towards Meeting the Challenge of Changing Requirements[C]. Proceedings of the IEEE Symposium and Workshop on Engineering of Computer Based Systems, 1996.

5 Wen Lian, Dromey R G. From Requirements Change to Design Change: A Formal Path Software Engineering and Formal Methods [C]. Proceedings of the 2nd International Conference on SEFM, 2004: 104-113.

6 Carlshamre P, Sandahl K. An Industrial Survey of Requirements Interdependencies in Software Product Release Planning[C]. Pro- ceedings of the 5th IEEE International Symposium on Requirements Engineering, 2001: 84-91.

假设初始状态下，图3每一需求的工作量如表1所示。表2为需求依赖所产生的影响因子。

表1 需求初态时工作量

需求号 工作量

R 1

R 2

R 3

R 4

R 5

R 6

R 7

R 8

R 9

表2 需求依赖所产生的影响因子

1 2

R 1 R 3

R 3 R 6

R 3 R 8

R 4R 2

R 4 R 5

R 5 R 6

R 7 R 6

R 8R 3

R

9R 6

FI(Rs,

0.380.75

图4给出了需求变更源R1、R4的最小依赖集，虚线表示部分为环路依赖。

7 Giesen J, Volker A. Requirements Interdependencies and Stakeholders Perferences[C]. Proceedings of IEEE Joint International Conference on Requirements Engineering, 2002-09: 206-209.

图4 最小依赖集

8 Ramesh B, Jarke M. Toward Reference Models for Requirements Traceability[J]. IEEE Transactions on Software Engineering, 2001, 27(1): 58-93.

假设R 1、R 4的工作增量分别为4和2，则通过上述评估

—84—