0 概述

随着互联网技术的发展, 软件众包作为一种新型的开发模式, 已经引起各领域的广泛关注。软件众包模式^[1]的发展使得软件开发不再局限于孤立的开发者团体, 而是由一个组织或社区中的开发者合作完成。高效的开发和低价的成本使得越来越多的用户选择众包模式发布软件任务^[2]。

复杂的软件众包任务为了吸引更多的工人参与开发, 需要进行合理的任务分解, 而分解的好坏直接影响众包模式的开发效率。如果分解不当, 则会增加通信成本, 增大任务整合难度, 提高工人参加众包任务的门槛。因此, 如何将复杂的软件众包任务分解为若干微任务是亟待解决的问题^[3-5]。

文献[6]提出基于设计结构矩阵(Design Structure Matrix, DSM)的解耦理论。文献[7]修正了DSM并使用增广约束网络(Augmented Constrained Network, ACN)衡量模块间的依赖关系。文献[8]基于ACN将DSM分解为多层结构。文献[9]提出一种ArchDRH设计规则。以上研究均证明了基于DSM进行任务解耦合的有效性, 但上述方法较复杂。在此基础上, 文献[10]简化了DSM的设计方法, 提出一种基于解耦水平(Decoupling Level, DL)的度量方法, 但该方法对任务粒度考虑不足。文献[11]综合考虑了任务粒度、任务耦合性以及任务均衡度, 但对任务耦合性的度量说明不明确。文献[12]针对单输入多输出的耦合模型进行研究, 但增加了额外的通信开销。文献[13]提出多阶段混合模型, 但对如何构建解耦集说明不具体。本文在研究众包模式与传统外包模式差异的基础上, 综合考虑任务粒度与解耦性, 提出一种基于动态解耦的软件众包任务分解算法(CTDL)。

1 问题模型

本文研究的软件众包任务基于竞标模式, 相关定义及问题描述具体如下:

定义1(软件任务)  软件任务是指经过众包平台架构师分解的任务集合。软件任务是一个三元组:M={DL_m, GR_m, DS_m}, 其中, DL_m为任务解耦水平, GR_m为任务粒度, DS_m表示对任务的描述。

定义2(任务网络)  本文研究的任务网络是指由类、接口和包构成的依赖关系网络, 任务网络定义为一个有向网络G_d=(V_d, E_d), 其中结点v_d(v_d∈V_d)代表软件的类或者接口, 如果2个结点之间存在关系, 则构成有向边e_ij(e_ij∈E_d)。为量化依赖关系, 本文主要考虑以下4种情况^[14]:

1) 实现, 假设v₁类实现了v₂接口, 则存在有向边e₁₂= < v₁, v₂>, 边的权值用α表示。

2) 泛化, 假设v₃类继承了v₄类的功能, 则存在有向边e₃₄= < v₃, v₄>, 边的权值用β表示。

3) 依赖, 假设v₅类的变化会引起v₆类的变化, 则存在有向边e₅₆= < v₅, v₆>, 边的权值用γ表示。

4) 关联, 假设v₇类和v₈类之间有一定的联系, 该关系使得一个类知道另一个类的属性和方法, 则存在有向边e₇₈= < v₇, v₈>, 边的权值用φ表示。

考虑到上述4种关系在实际开发中依赖程度不同, 因此本文约定α+β+γ+φ=1。本文研究的包是具有相关性的一组类或接口的集合, 定义G_p=(V_p, E_p), 其中结点v_p(v_p∈V_p)代表包。如果2个包之间存在依赖关系, 则构成有向边e_ab(e_ab∈E_p), 该边从一个结点内部指向另一个结点内部, 边的权值用δ表示, 示例如图 1所示, 其中, Package₁、Package₂表示包名, 简称为P₁、P₂, class表示类名, impl表示接口, 权值均为关联关系。

定义3(设计结构矩阵)  为能更好地反映各任务之间的依赖关系, 本文定义DSM, DSM是一个方阵。该矩阵的行和列使用相同的顺序标记任务名称, 该矩阵分为上下两层, 上层任务对其他任务有依赖关系, 下层任务对其他任务没有依赖关系。单元格(x, y)表示x依赖y。DSM示例如图 2所示, 横纵坐标的含义一一对应, √表示2个子任务之间有关系, 由于子任务本身不构成任何关系, 因此本文用灰色部分加以区分。

文献[8]证明通过UML用例图可以快速得到DSM。本文假设众包平台的软件架构师已根据用例图构建DSM, 后续研究重点是对DSM矩阵的调整。

定义4(包关联矩阵)  为能更好地反映包之间的联系关系, 便于对包的聚类, 本文定义一个包关联矩阵, 包关联矩阵是一个方阵。该矩阵的单元格表示包之间的关联关系, 具体如图 3所示。

2 基于任务网络的任务粒度计算

由于众包模式下发包方希望较多的工人参与项目开发, 以便从中选出完成情况最优的任务, 因此降低项目开发的门槛, 让更多工人参与进来显得尤为重要。任务粒度表征任务内部聚合情况, 也可以反映任务组织规模和数量, 每个软件任务中的类和包是影响任务粒度的主要因素, 类和包的数量越多任务粒度越小^[11], 本文基于任务网络进行任务粒度计算。假设某个软件众包项目由g个子任务构成, K_g表示第g个子任务的粒度系数, 该任务的粒度计算如下:

$ G R=\sum\limits_{i=1}^{g} K_{g} \times\left(c_{g}\right)^{-1} $

(1)

其中, c_g表示第g个子任务内的类和接口数量。

对于一个任务而言, 类、接口、包之间的依赖关系越复杂, 任务内部的关联性就越大^[15]。本文使用内聚函数S(t)描述任务t内部的关联程度, 具体如下:

$ S(t) = \left\{ {\begin{array}{*{20}{l}} {\frac{1}{{ph}}\sum\limits_{i = 1}^p {\sum\limits_{j = 1}^h {\left( {{e_{ij\alpha }} + {e_{ij\beta }} + {e_{ij\gamma }} + {e_{ij\varphi }}} \right)} } , {e_{ij}} \in {E_{\rm{d}}}}\\ {\frac{1}{q}\sum\limits_{l = 1}^q {{e_{l\delta }}} , {e_l} \in {E_{\rm{p}}}} \end{array}} \right. $

(2)

其中, p表示一个任务内部包的个数, h表示第i个包内的边数目, q表示连接包之间的边个数, e_ijα、e_ijβ、e_ijγ、e_ijφ、e_lδ表示边的权值。e_ijα+e_ijβ+e_ijγ+e_ijφ是出于对2个类(接口)之间可能存在多种依赖关系的考虑, 在实际计算中, 若只有一种关系, 则其他项为0即可。

任务粒度主要取决于任务的内聚性^[10], 因此对于任务中的第r个任务, 其粒度计算如下:

$ K_{r}=\exp \left(-S(r)^{-1}\right) $

(3)

将式(3)代入式(1)得到任务粒度计算公式如下:

$ GR = \sum\limits_{i = 1}^g {\exp } \left( { - S{{(g)}^{ - 1}}} \right) \times {\left( {{c_g}} \right)^{ - 1}} $

(4)

3 基于解耦水平的任务耦合度计算 3.1 计算方法描述

假设软件众包项目由n个任务组合而成, 整个项目的解耦水平值即为上下层任务的DL值之和:

$ DL = \sum\limits_{{L_i} = 1}^n D {L_{{L_i}}} $

(5)

其中, DL值越大表示解耦程度越高, 即任务越独立。

由于上下两层依赖情况截然不同, 因此需要采用不同的计算方式, 本文在文献[10]的式(2)~式(5)的基础上做了部分简化。由于下层任务是独立任务, 对于整个项目而言, 下层任务数量越多, DL值越大, 具体计算如下:

$ D L_{L_{i}}=\frac{L L M}{A M} $

(6)

其中, LLM表示下层任务总数, AM表示任务总数量。

由于每个上层任务依赖下层的任务, 因此依赖越多, DL值越小, 具体计算如下:

$ D{L_{{L_i}}} = \sum\limits_{j = 1}^k {\left[ {\frac{1}{{AM}} \times \left( {1 - \frac{{De{p_j}}}{{LLM}}} \right)} \right]} $

(7)

其中, Dep_j表示依赖于第j个任务的任务总数。

3.2 算例介绍

本文以湖北省教育信息化发展水平监测系统为例进行说明, 如图 4所示。

在图 4中, 横纵坐标的含义一一对应, √表示横轴对应的模块依赖纵轴对应的模块, 黑色方框表示页面管理依赖信息化主体发展, DL具体计算如下:

$ \begin{aligned} D L_{下层}=& \frac{1}{12} \times[\left(1-\frac{7}{5}\right)+\left(1-\frac{3}{5}\right) \times 4+\left(1-\frac{2}{5}\right)+\\ &\left(1-\frac{1}{5}\right) ]=\frac{13}{60} \end{aligned} $

$ D L_{下层}=\frac{5}{12}\\ DL=(DL_{下层}+DL_{上层})×100\%=63.33\% $

4 基于动态解耦的众包任务分解

考虑到软件众包任务分解过程中, 如果任务解耦不足会出现修改一个模块需要同时修改相关联的模块的情况, 则会增加工人之间的通信, 导致任务延期, 甚至增加软件风险; 如果解耦过度, 则会增加任务整合难度; 如果分解后任务粒度太大, 则会提高工人参与任务的门槛。

4.1 算法分解过程

本文分解算法首先给定解耦阈值并根据任务粒度动态调整解耦阈值进行分解, 直到满足任务粒度阈值和解耦阈值, 在分解过程中基于包关联矩阵对包进行聚类形成新任务。

考虑到不同类别的软件分解情况不同, 较难基于经验衡量任务粒度与解耦水平, 因此本文用集合GR_r表示第r类软件的粒度。鉴于众包模式的独特性, 在实际开发中众包平台可根据工人数量对任务粒度进行调整, 因此本文引入调节参数η₀, 每类软件的任务粒度均值用λ_r表示, 具体如下:

$ {\lambda _r} = \left( {\frac{1}{b}\sum\limits_{i = 1}^b {{W_b}} \times G{R_b}} \right) \times {\eta _0} $

(8)

其中, W_b表示权值, 实际开发中由众包平台指定, 调节参数η₀取值为(0, 2)。

本文用集合DL_r表示第r类软件的解耦水平, 假设第r类软件包含a个已成功开发的软件, 则每类软件的解耦水平均值ε_r表示如下:

$ {\varepsilon _r} = \frac{1}{a}\sum\limits_{i = 1}^a {{W_a}} \times D{L_a} $

(9)

其中, W_a表示权值, 实际开发中由众包平台指定。

在对任务进行分解时, 为考虑分解的均衡性, 选取任务内部关联系数排名前K的包进行聚类, 如图 3所示选择关联系数最大的包进行聚类后, P₁、P₂、P₃和P₄、P₅可构成2个新任务。在实际开发中K值可由众包平台指定。

4.2 CTDL算法描述

CTDL算法具体描述如下:

输入  待分解的软件项目P的用例图、解耦阈值、任务粒度阈值λ_r

输出  任务分解集合T

1.将用例图转化为DSM矩阵;

2.构建软件项目P的任务网络;

3.计算DSM内每个任务的解耦值DL;

4.计算DSM的解耦值DSM_DL;

5.基于任务网络计算任务粒度G;

6.判断DSM_DL是否大于解耦阈值ε_r, 若大于则转步骤7, 若小于则转步骤9;

7.判断任务粒度G是否小于任务粒度阈值λ_r, 若小于则转步骤8, 若大于则转步骤13;

8.ε_r=ε_r+L转步骤6;//增大阈值, L表示步长

9.按照DSM内各任务的DL值进行升序排序, 选择解耦值最大的任务Maxtask;

10.将Maxtask内关联系数排名前K的包进行聚合构成新任务t₁, 剩余任务构成t₂;

11.用t₁替换任务i, 将t₂加入DSM矩阵, 计算解耦值DSM_DL;

12.计算任务粒度G转步骤6;

13.输出任务分解集合T

5 实验结果与分析

因为软件众包领域缺乏基准实验数据, 本文从GitHub社区选取了108个已成功开发的软件作为实验数据集, 经分解后累计微任务数达到1 237个。本文首先使用PowerDesigner对这些软件进行逆向工程, 然后使用SourceCounter软件统计其规模及缺陷密度, 最后计算解耦值和任务粒度。实验对比本文解耦方法与其他解耦方法的效果, 并给出任务粒度阈值和解耦阈值的取值范围。

5.1 动态分解算法的性能对比

由于本文提出的基于动态分解的软件众包任务分解算法核心为解耦, 为证明分解算法的有效性, 实验将本文提出分解算法与基于传播成本(Propagation Cost, PC)的分解算法^[16]、基于独立水平(Independent Level, IL)的分解算法^[17]进行对比, 主要对比以下2项指标:

1) 风险判定值, 该值参考文献[18-19]提出的软件风险评估方法计算得出。

2) 缺陷密度, 该值反映每千行代码可能产生的软件缺陷数量, 对于衡量软件的可维护性、软件漏洞具有一定的参考价值。

基于PC与IL的分解算法均基于DSM矩阵计算, PC值为非空单元格除以总单元格, IL值为下层的非空单元格数量除以DSM内的任务总数。由于同一类软件的解耦维度具有较高的相似度, 因此本文按照软件类型对其进行聚类, 并以同一类软件解耦值的平均值作为该类软件解耦值的等价值。

为比较图 5中3个指标与风险判定值、缺陷密度的相关性, 本文使用皮尔逊值^[20]进行比较。皮尔逊值计算方法如下:

$ r=\frac{\sum a b-\frac{\sum a \sum b}{N}}{\sqrt{\left(\sum a^{2}-\frac{\left(\sum a\right)^{2}}{N}\right)\left(\sum b^{2}-\frac{\left(\sum b\right)^{2}}{N}\right)}} $

(10)

其中, r表示相关系数, N表示变量取值个数, a、b表示变量。

由表 1可以看出，DL变化更能反映风险判定值和缺陷密度的变化。基于DL的分解算法相对基于IL的分解算法风险判定值提升0.244 0，缺陷密度提升0.014 6；相对于基于PC的分解算法风险判定值提升0.362 6，缺陷密度提升0.319 4。

5.2 阈值确定

图 6、图 7分别对比了DL值、任务粒度与风险判定值和缺陷密度的关系, 根据实验结果可知, 任务粒度取0.003 0~0.003 9, DL值取53.51~71.21, 此时软件风险和缺陷密度较小。

6 结束语

本文给出任务粒度和解耦水平的定义, 提出一种基于动态解耦的软件众包任务分解算法。实验结果表明, 与基于IL和PC的分解算法相比, 本文算法能更好地降低软件风险、缺陷密度以及工人参与任务的门槛, 提高软件众包模式的开发效率。下一步将优化解耦水平与任务粒度的度量方式, 在此基础上综合考虑子任务定价等因素, 以提升任务完成质量, 降低发包方成本。