基于复杂网络理论的软件体系结构描述与质量评估

秦怀斌，郑瑶，郭理

(石河子大学信息科学与技术学院，新疆 石河子 832003)

软件体系结构(Software Architecture，SA)自20世纪90年代提出以来，一直是软件工程领域研究的热点。SA作为软件系统的高层抽象，体现了软件系统设计的整体思想。SA在软件开发早期，从较高的层次定义软件系统的组成部分，并确立各个组成部分之间的交互方式[1-2]。作为软件系统实现的蓝本，SA的设计质量将对软件后续编码、测试、维护等工作产生重要影响。研究者们[1-4]认为，对SA的深入研究将会成为提高软件生产率和解决软件危机问题新的最有希望的途径。

复杂性科学(Science of Complexity)是一种新兴的边缘、交叉学科，国内外许多学者认为复杂性科学是21世纪科学技术发展的前沿。复杂网络(Complex Network，CN)作为复杂性科学研究的一部分，它打破了线性、均衡、简单还原的传统范式，致力于非均衡、非线性等复杂系统的研究。当一个系统由大量相互作用的节点构成，其整体的复杂性超过了对其构成节点行为的简单叠加，那么，这个系统就是复杂系统[4-5]。在自然界中，形式多样的复杂系统都可以通过各种各样的复杂网络来进行刻画和描述。在复杂网络中，每个节点代表各种复杂系统中的不同个体，边表示这些个体之间的某种关系，复杂网络最主要的特性有三个：第一，小世界(Small-World)特性,即网络具有较短的平均路径长度和较大的聚集系数；第二，无标度(Scale-Free)特性,即网络中少数节点拥有大量的连接，而大部分节点的连接却很少，节点的度数分布符合幂率分布；第三，社团(Community)特性，即网络中的众多节点按照某种方式进行分组，组内节点间的连接比较稠密，组间节点的连接比较稀疏[6-9]。

最近几年，国内外研究者通过将软件系统转化为网络模型，其中，节点可以是服务、数据对象、操作、模块、类、构件、子系统等诸元素，边是调用、数据交换、消息传递、语义关联等诸元素。研究[6-8]发现，许多软件系统网络结构既不是规则网络，也不是随机网络，而是具有诸如“小世界”、“无标度”、“分形”等复杂网络特征。这一发现为软件系统结构的分析提供了一个新的视角。基于此，美国卡内基·梅隆大学软件工程研究所于2004年发布了复杂巨系统软件专项调研，将复杂网络引入到软件工程领域[10-11]，2006年他们又开展网络化软件研究；2005年，包括IBM、HP、Nokia、SAP等在内的13个跨国IT公司宣布合作研究开发网络化软件。在国内，2006年何克清等[12-13]最早提出将复杂网络的理论和方法引入到软件工程领域，同时也提出网络化软件的概念。

目前，复杂网络理论与软件体系结构领域相结合的研究工作刚刚起步，特别是将复杂网络理与软件体系结构融合研究，已经引起研究者的关注。在复杂网络理论坚实的数学理论基础上，用形式化的方法来描述软件系统中的各个元素及其之间的关系，分析软件网络模型，更容易洞察其整体的基本性质和规律，这将是未来实现“计算型”软件体系结构的一个研究趋势。

鉴于此，本文在分析复杂网络理论及软件体系结构基础上，基于复杂网络理论从形式化定义、组成元素、整体结构、约束条件、相关思想等方面对软件体系结构进行描述，并主要从模块度的角度对软件体系结构设计质量进行评估。

1 基于复杂网络理论软件体系结构的描述

1.1 复杂网络的定义

复杂网络CN的一般定义如下[1]：

定义1：复杂网络抽象为一个图G=(V，E)，其中：V={V1，V2，…，Vn}为节点集合，V中的元素称为节点；E={E1，E2，…，En}为边集合，E中的元素称为边；N=|V|为节点总数，L=|E|为边总数；E中的每条边Ei与V中的一对节点(u，v)对应，如果E中任意节点对(u，v)和(v，u)对应同一条边，则该网络称为无向网络，否则为有向网络，而如果E中所有的边的长度均为1，即|Ei|=1，则称网络为无权网络，否则为加权网络。

1.2 软件体系结构形式化描述

根据Mary Shaw和David Garlan的定义，SA可表示为三元组SA={构件，连接件，约束}。其中，构件可以是一组代码，如程序模块，也可以是一个独立的程序，如一个完整的系统；连接件表示构件之间的相互关系，它可以是管道、远程过程调用等；约束是指构件及连接件之间连接的限制。

根据上述软件体系结构SA的定义，基于复杂网络理论给出软件体系结构SA的形式化定义为：

定义2:一个三元组SA=(C，L；F)称为一个软件体系结构，当且仅当：

(1)C={C1，C2，…，Cn}是构件的集合，L={L1，L2，…，Lk}是连接件的集合，C和L是有限集，即n、k为任意一个有界自然数；

(2)C∩L=∅，C∪L≠∅；

(3)F⊆{(C×L)∪(L×C)}，其中×为迪卡尔积，表示构件与连接件之间的关系；

(4)C，L⊆F，Ci×Lj×…×Lz×Cy⊆F，其中i、j、z、y为有界自然数。

1.3 组成元素的描述

1.3.1 SA中的构件

构件是可复用的软件组成成份，可被用来构造其他软件。构件可以是被封装的对象类、类树、服务、功能模块、软件框架(framework)、文档、分析件、设计模式(Pattern)、子系统等。开发者可以通过组装已有的构件来开发新的应用系统，从而达到软件复用的目的。

1.3.2 SA中的连接件

连接件是软件体系结构的另一类重要的组成部分，连接件通过对构件之间的交互规则的建模将不同构件进行连接，实现构件之间的通信。连接件可以是管道、过程调用、数据交换、消息传递、语义关联等。

1.3.3 复杂网络的节点

复杂网络是复杂系统的抽象，在复杂网络中节点表示复杂系统中的个体，在不同的系统中节点表示不同的个体，如在科学家合作网中节点表示科学家,在计算机网中节点表示设备(如，服务器、路由器、PC机、打印机等)。

1.3.4 复杂网络的边(Edge)

在复杂网络中，节点之间的边表示的是系统中个体之间按照某种规则而自然形成或人为构造的一种关系,如在科学家合作网中边表示科学家之间的合作关系,在计算机网中边表示设备之间的连接关系。

1.3.5 SA中的构件与复杂网络的节点的结合描述

如前所述，SA中的构件是以多种多样的形式存在的，如对象类、服务、子系统等，为了分析方便，不考虑构件的个性差异，所有构件都抽象为一个点，即将所有构件都转换为复杂网络中的节点，一个构件转换为一个节点。

1.3.6 SA中的连接件与复杂网络的边的结合描述

自上个世纪六十年代起，世界经济飞速发展，产业融合初见规模，全球经济一体化进程加速，国际之间的贸易往来越来越频繁。在此背景下，会展旅游业的市场在进一步扩张。会展旅游业与观光旅游业相比，具有规模大、档次高、持续时间长的特点，而且发展的同时还可以带动一大批相关产业的发展。很多国家已经将会展旅游业列入了国家支柱产业之一，由此可见会展旅游业对于一个国家和地区的重要性。虽然我国的会展旅游业起步较晚，但是乘着经济飞速发展的东风，我国会展旅游业也在迅速增长，已经成为我国第三产业中的一个重要部分，是地区经济发展重要的增长点。

SA中的连接件也是以多种多样的形式存在的，如管道、过程调用、数据交换、消息传递、语义关联等，为了分析方便，不考虑连接件的个性差异，所有连接件都抽象为一条边，即将所有连接件都转换为复杂网络中的边，一个连接件转换为一条边。

1.4 整体结构的描述

根据定义2可知，软件体系结构SA可以看作是由构件和连接件组成的集合，连接件将各个构件连接起来，组成一个完整的结构，同时，根据定义可知，复杂网络CN可以看作是由节点和边组成的集合，边把各个节点连接起来，组成一个完整的网络。

鉴于此，将SA中的构件转换为复杂网络中的节点，SA中的连接件转换为复杂网络中的边,这样就将一个完整的软件结构转换成了一个完整的复杂网络,并且根据边的权值和方向性，又可将软件体系结构SA转化为复杂网络中的无向无权网络、无向加权网络、有向无权网络和有向加权网络4种。

1.5 约束条件的描述

1.5.1 软件体系结构约束

在软件体系结构中，构件和连接件是至关重要的元素,软件体系结构约束主要是构件与连接件的连接约束。

构件通过一个二元组来表示，其中，N是构件的标识，I是构件的接口，I又分为需求接口和供给接口2种。连接件是构件的粘合剂，是构件交互的实现。

软件体系结构约束描述了体系结构的配置和拓扑要求，配置或拓扑是指构件和连接件组成的一个连接图，用于描述软件体系结构的构成，确定了软件体系结构的构件与连接件之间的连接关系。软件体系结构约束提供限制以确定构件是否正确连接、接口是否匹配、连接件构成的通信是否正确，并说明实现所要求行为的组合语义。软件体系结构的生成过程，也就是构件与连接件之间连接组装的过程,组装过程主要分为顺序组装、并行组装和选择组装。

(1)顺序组装。顺序组装是指两个相连构件之间存在先后顺序的组装，提供服务的构件作为主动调用构件，被提供服务的构件为被动构件，顺序组装后形成的构件为复合构件。复合构件的功能是主动构件和被动构件功能的集合。例如，A构件调用B构件所提供的服务，A和B组合后形成C构件，C构件为复合构件，对外界而言，C构件同时提供A构件和B构件的功能，对内部而言，是通过先执行A构件再执行B构件实现的。

(2)并行组装。与顺序组装类似，但并行组装的两个构件没有先后顺序之分，两个构件可以并行执行，以满足系统需求。例如，复合构件C由A构件和B构件组成，对外界而言，C构件同时提供A构件和B构件的功能，对内部而言，是通过同时执行A构件和B构件实现的。

在上述软件系统连接中，不论是顺序组装、并行组装还是选择组装，只要两个构件之间有连接，就需要通过连接件连接。

1.5.2 复杂网络约束

复杂网络中的两个核心网络是小世界(Small-World)网络和无标度(Scale-Free)网络。与软件体系结构约束类似，复杂网络的约束也就是复杂网络的生成过程约束，即节点和边相互连接生产网络的过程。

(1)小世界网络。小世界网络模型是由Watts和Strogatz于1998年提出的，学术界又称其为WS模型。网络具有较短的平均路径长度和较大的簇系数是该模型的主要特征之一。

该网络模型的生成过程为：第1步，从一个有N个节点的环开始，环中的每一个节点与其他节点有m条边相互连接；第2步，对环中的每条边以概率p随机进行重新连接(不允许重复连接和自我连接)；第3步，重新连接后生成新的网络结构，重新计算相关属性值(如平均路径长度、簇系数等)。结果发现，新生成的网络模型，具有小世界网络特征，即网络的平均路径长度较短，但对网络的簇系数影响较小。

(2)无标度网络。无标度网络模型是由Barabási和Albert于1999年提出的，学术界又称其为BA模型。网络节点的度分布服从幂律分布是该模型的主要特征之一，并且，该网络模型具有增长和择优连接的特点，即富者越富效应。

该网络模型的生成过程为：第1步，在初始时刻，假定网络中己有少量节点；第2步，每隔一个时间间隔，在网络中新增一个节点，该节点与网络中己经存在的节点进行连接，一般情况下被选择的节点与新节点连接的概率和被选节点的度成正比，并产生连接边；第3步，在规定的时间内，结束该算法，计算相关属性值，如节点的度分布、平均路径长度、簇系数等。结果发现，生成的网络具有无标度网络特征，即节点的度分布服从幂律分布，度值一般在2-3，并且该网络模型具有较小的平均路径长度，簇系数也相对较小。

1.5.3 两种约束的结合描述

分析软件体系结构约束和复杂网络约束可知，软件体系结构约束描述的是软件体系结构的配置和拓扑要求，以此来确定软件体系结构的构件与连接件之间的连接关系，即构件与连接件的连接约束，也即软件体系结构的生成过程约束；而复杂网络约束，描述的是复杂网络结构的拓扑结构，以此来确定复杂网络中各个节点与各个边之间的连接关系，即节点与边的连接约束，也即复杂网络的生成过程约束。

鉴于软件体系结构约束与复杂网络约束存在本质上的相关性，软件体系结构约束条件与复杂网络约束条件可实现良好的结合。

1.6 相关思想的描述

在软件体系结构领域，核心概念及思想包括模块化、模块、抽象、逐步求精、内聚度、耦合度、软件体系结构演化等，这些概念和思想贯穿于软件开发的自始至终。

在复杂网络理论中，核心概念和思想包括社团、模块度、层次复杂网络、重叠性、强社团、弱社团、稀疏、稠密、网络的动态演化等，这些概念和思想对网络分析至关重要。

SA的模块度用于衡量SA结构的网络划分质量。一般情况下，一个软件系统的SA结构的网络划分模块度值越大，则划分出的网络社团结构越好，越符合“社团内部连接紧密，社团间连接稀疏”的思想[1]。按照软件工程思想，将SA中的构件、类等按照包的语义划分为多个模块或包，模块或包内的构件或类之间的联系紧密，而模块或包之间的关系较松散,即用较少的、简单的连接件进行连接，其中，软件工程中的模块或包的概念与复杂网络的社团概念一致，软件系统模块化的过程类似于复杂网络中社团发现及分解的过程。

复杂网络社团结构的层次性与软件工程的“模块化”、“抽象与逐步求精”等思想相吻合。在分析及设计系统的SA结构过程中，为了减小因为问题的规模和复杂性不断增大而带来的困难，通过包机制，将系统划分为多个模块，包内节点联系紧密，包间关系松散；通过在不同抽象级别考虑和处理问题，用逐步求精的方法不断地分解，逐步确立过程细节，直至某一功能用程序语言描述的算法实现为止，具有不同详细程度的各种描述，组成了系统的层次结构，这与复杂网络社团的层次性特性一致。在复杂网络中，通过分层将复杂网络进行分解，分解的过程也就是复杂网络细化的过程，其中，上层网络是下层网络的抽象，下层网络是上层网络的精华和细化。

复杂网络社团结构的重叠性对应于软件工程中，在软件开发过程中为了减少冗余、提高模块的复用率，将多个模块的公共部分提取出来而设计成一个公共模块，供其它模块调用，这个公共模块就是这些模块(社团)的“骑墙节点”。

簇系数表示复杂网络模型的群组结构，即复杂网络模型中的节点按照群组分布，群组内的节点之间有密集的边相连，而群组之间关联的边较少。按照软件工程思想，将SA中的构件、类等按照包的语义划分为多个包，包内的构件或类之间的联系紧密，而包之间的关系较松散(即用较少的、简单的连接件进行连接)。

复杂网络中某个节点的平均路径长度是指该节点到其他所有节点的最短路径的平均，网络的平均路径长度是指网络中所有节点对之间最短路径的平均值，即任意两个节点之间要经过的边的数目的平均值。在软件体系结构SA中，平均路径长度表明了节点所代表的构件在SA中的中心度，节点的平均距离越短，则该节点所代表的构件与其他节点所代表的构件所需要经过的连接件越少，说明该节点所代表的构件的中心度越高。根据软件工程思想，系统结构层次不能太深，构件尽量调用其紧邻下层构件，避免越级访问，所以，SA所转化的有向复杂网络模型应该具有较小的平均路径长度。

在复杂网络中网络会发生变化，即复杂网络的演化，包括网络节点的增加、删除和修改，及网络中边的增加、修改和删除。同样，软件体系结构也同样面临着演化，即随着用户需求的不断变化，软件体系结构可能也会发生变化，以满足新的软件需求。软件体系结构演化包括构件的增加、删除或修改和构件之间连接件的增加、修改和删除，及构件的更新相互作用关系等。

2 基于复杂网络理论软件体系结构的质量评估

在对软件体系结构设计合理性及质量评价度量中，最常用的评价指标有高内聚、低耦合、模块化、层次性等。本文以高内聚、低耦合度量指标为例，阐述基于复杂网络理论进行软件体系结构设计合理性和质量的度量。

在软件体系结构中，内聚是指一个模块(或复合模块)内部各个元素彼此结合的紧密程度，耦合是指模块(或复合模块)之间的相对独立性。根据软件工程思想，为了便于软件开发、编码和后续维护，软件体系结构设计应该符合“高内聚低耦合”的设计思想，即模块内部的各个部分应尽可能多的连接，模块之间各个部分应尽可能少的连接。

在复杂网络理论中，通过模块度Q来度量一个网络结构划分的好坏。一般情况下，一个网络结构的Q值越大，则划分出的网络结构越好，越是符合“社团(或复合社团)内部连接紧密，社团(或复合社团)之间连接稀疏”。这种度量方法与软件体系结构的“高内聚低耦合”的度量思想[1]一致。

研究及统计表明，一般以Q=0.3作为网络结构具有明显社团结构的下界，并且网络的模块度Q值越大，则划分出的网络结构越好。

根据前述内容，结合定义3，本文提出了一种度量软件体系结构SA结构划分好坏的度量指标：SA的模块度。SA的模块度具体定义如下：

其中，ki和kj是构件i和j的度值；Ci、Cj是构件i和j所属模块(或复合模块)；m是SA总边数。当Ci=Cj时，δ(Ci,Cj)=1，否则为0。

根据定义4可知，QSA值在0和1之间，设定QSA=0.3作为SA结构划分好坏的下界。QSA值越大，SA结构划分越合理。

如上，实现复杂网络的模块度Q与软件体系结构SA的模块度QSA的结合，从内聚度和耦合度角度出发，实现对软件体系结构SA模块划分好坏的度量。同理，基于复杂网络理论，可以实现对软件体系结构SA其他质量指标的度量。

3 结束语

鉴于软件体系结构SA在软件开发中的重要性，其结构的设计质量将对软件开发产生深远影响。基于复杂网络的软件模型[1]具有良好的数学基础，用形式化的方法来描述软件系统中的元素及其之间的关系，从全局视角更容易洞察软件体系结构SA的基本性质和规律，并能有效地将软件系统的结构映射到合适的复杂网络结构上加以度量。

本文首先对复杂网络理论及软件体系结构进行了分析，在此基础上，基于复杂网络理论从形式化定义、组成元素、整体结构、约束条件、相关思想等方面对软件体系结构进行描述，并主要从模块度的角度对软件体系结构设计质量进行评估，这可为后续软件体系结构领域相关研究提供借鉴。