一种空间飞行器控制系统软件协同演化方法*

周 宇，沈怡颹，张 磊，张增安

(上海航天控制技术研究所·上海·201109)

0 引 言

空间飞行器控制系统软件属于特殊领域软件，同时也是定制型软件，每个型号的控制系统软件都需要根据型号的任务需求进行定制开发，因此控制系统软件的研制工作与控制系统本身的研制工作是紧密结合在一起的，系统设计人员和软件设计人员都处于协同研制的状态下。特别是随着软件规模的扩大，软件复用程度的提高，同一软件中往往存在多个开发组开发的模块同时存在的情况。而传统的基于瀑布模型的软件演化流程并不能很好地协调各模块间的开发顺序，不可避免地导致相关参与人员一拥而上，继而出现资源浪费、管理混乱的问题。

当前对软件的协同开发、协同演化进行的研究主要集中在对开源软件的社区协同、异地协同领域[1-4]。此外在国内，余敦辉等提出了基于众包的软件协同开发方法[5]，王怀民等提出名为Trustie的可信软件协同开发环境[6]，陈洪龙等对面向服务对象的软件演化进行了研究[7]。

另一方面，由于空间飞行器控制系统软件的高可信度的要求以及其瀑布开发模型的固有特性[8]，导致在一个软件开发阶段中就需要达到一定的可信程度，而不能依赖多次迭代来解决软件存在的缺陷。同时控制系统软件的高复杂性也导致了参与人员多、模块间的耦合度高的情况。因此，在空间飞行器控制系统软件在对单一模块或功能进行演化的过程中必须有效识别其影响域，对可能受影响的模块、功能性能等都在一个迭代周期内完成适应修改、验证的工作，从而避免后续高昂的迭代周期，并保证软件在任意开发过程时的可信程度。

为在空间飞行器控制系统软件的演化过程中避免上述的人力资源浪费，同时保证软件可信程度，就必然要求一种能协调各类演化活动有序开展，进而保证人员的有序调配的协同演化方法。图算法中的拓扑排序方法已经被广泛应用于各领域的项目人员调度、管理领域[9-13]，因此，本文提出一种基于拓扑排序的软件协同演化路径确定方法，来实现对空间飞行器控制系统软件的软件演化过程进行有效组织。通过对演化路径的有序化，来保证各演化活动的有序开展，一方面避免了各个演化活动的无序开展所可能导致的资源占用、返工浪费，另一方面，确保了任何演化活动所引入的软件错误及缺陷能被立刻检验和修复。

1 协同演化的方案设计

1.1 软件协同演化的整体架构

本方法是一种适用于空间飞行器控制系统软件的协同演化方法，对软件演化的协同主要表现在两个方面，一是在演化过程中各个演化活动进行步骤的协同，另一方面是相应的软件研制的参与方的工作流程进行协同。而这主要依托于如表1所示的软件开发基本要素和要素间的关联关系[14]。

表1 软件演化基本关联关系表

如图1所示，软件在其演化过程中，根据演化策略提炼出一个初始的演化活动，再基于各演化活动间的RS关系，得到演化过程的活动路径。同时协调各相关参与的角色，最终得到可执行的软件演化过程。其中，软件可信证据来源于软件测试、应用中的数据，将其中一部分能标识软件问题、缺陷的证据作为演化活动的依据。

图1 协同演化过程图

1.2 对空间飞行器控制系统软件演化活动的分析

空间飞行器控制系统软件的演化活动从类别来分，主要包含了对软件需求、设计、编码、测试等多种类型的活动。同时随着当前软件工程化程度的提高，软件开发、测试工作针对的对象粒度逐渐达到了模块级别。此时，软件的演化活动间关系存在如下两类情况。

(1)针对单一对象的软件开发测试工作，由于领域特点，采用瀑布模型，因此其迁移关系首尾相接，演化路径呈一条直线。

(2)在存在模块间耦合等相互依赖的情况下，针对某一模块的演化活动会导致依赖于它的其他模块进行相应的演化。这种模块间相互依赖的情况，可以通过模块设计时定义模块间RS关系来确定。如对模块A进行设计更改会导致依赖模块A的模块B进行设计复查，若需要则进行适应性更改。

在同时考虑上述两类演化活动关系时，可以发现，空间飞行器控制系统软件的演化路径并不一定是一条直线或是树状，由于模块间耦合的情况多变，也可能出现回溯、交叉等现象。

在此能确定的只有存在一组节点，代表不同的演化活动，同时存在一组边，连接两节点，并存在方向，通过这种形式来描述演化活动间的相互关系。因此，演化路径可以用有向图的形式来进行表示。

1.3 对演化策略的建立

对软件协同演化的策略一方面是建立一组策略集，基于一定的阈值、条件等判断标准对可信证据进行筛查，确定不满足判断条件的可信证据，并提供指导性的演化目标，指示软件所亟待进行的演化活动。此种方法自动化程度高，标准明确，仅通过一组“证据-条件-初始演化活动”策略集便可进行，但同时该方法存在适用范围窄的问题，其仅适用软件功能-模块对应良好的情况，若功能模块分割不合理或功能过于复杂，这种方法并不能很好地适应。另一方面，通过在证据采集等过程中增加人力判断、分析等方法，则能有效地满足对演化过程的指导，也与软件工程化中软件变更的问题分析流程相一致。

2 软件协同演化的演化路径构建

2.1 演化路径的模型构建

如上述的软件演化过程中，根据演化策略得到的是指向软件的某一演化活动。依据1.2节中所叙述的各模块的依赖影响关系，软件的演化活动将从一个软件模块的演化活动作为入口出发，依次完成对依赖该演化活动的软件其他演化活动，如对某一个模块的需求设计更改，会引发对该模块的测试和基于该模块的其他功能模块进行修改、验证等演化活动，直到所有受影响的演化活动完成。

因此，本文中采用一种有向图来描述这种软件协同演化路径。如图2所示，图中每一个节点定义为软件的演化活动，每一条边则用于连接存在依赖或影响的两个演化活动，方向指向受影响的一方。由于本文主要关注于演化路径的构建，因此定义所有边的权重均一致。

图2 对演化路径的有向图转换

2.2 演化路径图的拓扑排序

为了演化过程的有序开展，有必要对各项演化活动的开展顺序进行求解，确定各模块对应演化活动的先后开展次序，进而才能协调项目组中各相关方的行动。基于2.1节中利用有向图定义的演化路径图，若假设在演化路径图中不存在环的情况，则演化活动的先后次序可以依靠对该有向图进行拓扑排序得到，如图3所示。常见的有向图的拓扑排序方法包括Kahn算法[15]及深度优先算法，在此基于对后续环处理的便利性，采用Kahn算法对演化路径图进行拓扑排序。

图3 有向图的拓扑排序

Kahn算法基于贪心思想，通过重复遍历所有节点，将没有入度的节点从图中移除并加入FIFO中，最终实现对所有节点的拓扑排序，其具体伪代码可如下所示。

在传统逻辑中，“类比推理是根据两个(或两类)对象在一系列属性上相同或相似，而且已知其中的对象还具有其他特定属性，由此推出另一个对象也具有同样的其他特定属性的结论。[2]”在这个定义中，类比的对象可以是个别的事物，也可以是一类事物，还可以是两种观点或理论。这种对类比对象的描述是简单的定性说明，缺乏细致的分析。类比所依据的是事物属性方面的相似性，没有进一步探讨类比对象在结构上的相似性。可见国内逻辑学领域对类比推理研究还相对薄弱，既缺乏深耕也较少远拓，尤其是对人工智能中类比推理的研究成果关注不够。

算法:Kahn算法输入:依赖关系表中存储的演化活动间的依赖关系,每条依赖关系中,左节点代表被依赖活动,右节点代表存在依赖的活动。输出:排序FIFO中的演化活动的拓扑排序。1 FOREACH 依赖关系 IN 依赖关系表2 节点HASH表[右节点].入度 +=13 节点HASH表[左节点].出队列. APPEND(右节点)4 WHILE 排序FIFO.长度 < 总节点数5 FOREACH 节点 IN 节点HASH6 IF 节点.入度=0 THEN7 排序FIFO.APPEND(节点)8 FOREACH 出节点 IN 节点.出队列9 节点HASH表[出节点].入度 -=1

2.3 演化路径图的并行化

在2.2节中，针对不存在环的演化路径图给出了基于Kahn算法的拓扑排序实现演化路径的构建。在Kahn 算法进行遍历所有没有入度的节点，此时作为节点的演化活动被加入排序队列中。但由于在软件协同演化过程中，同一次Kahn算法遍历到的节点，其相互之间并没有依赖顺序，因此可以作为并行的演化活动进行。

图4 拓扑排序的并行化

为实现Kahn算法对并行化的支持，在此修改Kahn算法中FIFO的数据结构，将其修改为一个桶数组。其中每一个桶指向存储演化活动的链表，数据结构如图5所示。

图5 支持并行的拓扑排序数据结构示意图

通过增加并行处理，保证了演化活动的紧凑性，如当多个模块互相之间没有依赖关系时，完全可以使其同步进行演化，避免了串行处理造成的效率降低。支持并行化的Kahn算法的伪代码可以被修改为如下所示。

算法:支持并行化的Kahn算法输入:依赖关系表中存储的演化活动间的依赖关系,每条依赖关系中,左节点代表被依赖活动,右节点代表存在依赖的活动。输出:桶数组中的二维的演化活动排序。

1 FOREACH 依赖关系 IN 依赖关系表2 节点HASH表[右节点].入度 +=13 节点HASH表[左节点].出队列. APPEND(右节点)4 SET 桶指针 指向 桶数组的头位置5 WHILE 排序FIFO.长度 < 总节点数6 FOREACH 节点 IN 节点HASH7 IF 节点.入度=0 THEN8 桶指针->APPEND(节点)9 FOREACH 出节点 IN 节点.出队列10 节点HASH表[出节点].入度 -=111 桶指针+=1

2.4 演化路径图的环处理

在演化路径图中作为节点的演化活动其互相之间的依赖有可能会导致出现如图6所示的依赖环，形成有向有环图。此时，通常的拓扑排序并不能适用。

图6 有向图的环

但基于2.3节中所设计的数据结构，此处提出一种新的方法来将环转化为一种并行化排序队列。该方法如图7所示。

图7 支持环的拓扑排序策略

首先，通过考察是否存在没有入度的节点，来判断当前有向图中是否形成环。若发现图形成环后，则根据上一次遍历时图中最后被指向的节点，对其所有的入度的边进行变形，转换为指向一临时新节点的边。之后继续进行Kahn算法遍历。最后，将被指向节点与其生成的临时节点都被加入同数组后，在这两个节点间的所有桶内增加该项演化活动。

通过这种新算法可以有效地描述演化过程中，演化活动互相存在依赖环的情况，通过协调某些演化活动同时进行，可以保证，任何软件模块在进行演化时，其依赖的演化活动都已经进行完毕或是正处于进行过程中。增加环处理后的Kahn算法如下所示。

算法:增加环处理的Kahn算法输入:依赖关系表中存储的演化活动间的依赖关系,每条依赖关系中,左节点代表被依赖活动,右节点代表存在依赖的活动。输出:桶数组中的二维的演化活动排序。1 FOREACH 依赖关系 IN 依赖关系表2 节点HASH表[右节点].入度 +=13 节点HASH表[右节点].入队列.APPEND(左节点)4 节点HASH表[左节点].出队列.APPEND(右节点)5 SET 桶指针 指向 桶数组的头位置6 SET 初始节点FIFOA 为 随机一节点7 WHILE 排序FIFO.长度 < 总节点数8 SET 初始节点FIFOB 为 空9 FOREACH 节点 IN 节点HASH 10 IF 节点.入度=0 THEN11 // 环入口节点从并行FIFO移出。12 IF 节点为带∗节点 THEN13 并行FIFO.REMOVE(节点)14 桶指针->APPEND(节点)15 初始节点FIFOB.APPEND(节点)16 FOREACH 出节点 IN 节点.出队列17 节点HASH表[出节点].入度 -=118 IF 初始节点FIFOB=空 THEN // 检测到环的存在。19 FOREACH 初始节点 IN 初始节点FIFOA20 FOREACH 入节点 IN 初始节点.入队列21 IF 入节点.入度 !=0 THEN // 该节点仍在图中存在22 // 将入节点.出队列中的初始节点更改为带∗节点。23 入节点.出队列.REPLACE(初始节点, 初始节点∗) 24 初始节点.入度=025 并行FIFO.APPEND(初始节点)26 ELSE27 初始节点FIFOA 拷贝 初始节点FIFOB 的内容28 // 向排序FIFO中增加并行进行的节点29 FOREACH 并行节点 IN 并行FIFO30 排序FIFO.APPEND(并行节点)31 桶指针+=1

2.5 演化路径图在协同演化过程的应用

通过对空间飞行器控制系统软件的演化过程进行建立演化路径图后，可以得到其各项演化活动的进行次序，进而能确定相应的各个参与方的“入场”顺序，从而使参与方的资源调配和计划能有效开展。保证了演化活动的有序开展和紧凑进行。

如当其中所有模块都由一个单一开发组进行开发时，在完成模块A开发工作后分为两组分别对模块B、C进行开发，并在之后分为三组对D、E、F模块进行开发，从而有效提升了软件演化效率。而当各模块由不同开发组进行开发时，其参与演化过程的时机也可以基于此进行调配，避免了项目演化过程出现空转或等待的情况。

表2 范例软件演化路径表

3 结 论

通过对演化路径的构建，建立了空间飞行器控制系统软件的系统演化方法，特别是解决了演化活动并行进行的表示问题以及有向图存在环的问题，有效保证了软件开展有序过程的有序性。进而确保了软件在进行演化活动时的可信程度，同时避免了演化活动无序导致的人力资源浪费，有效提高软件演化的效率。