搜索
书书书第３２卷 第９期２００９年９月计 算 机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．３２Ｎｏ．９Ｓｅｐｔ．２００９ 收稿日期：２００９０４１９；最终修改稿收到日期：２００９０７２６．本课题得到国家“九七三”重点基础研究发展规划项目基金（２００７ＣＢ３１０８００）、国家自然科学基金（６０４９６３２３）资助．韩言妮，女，１９８１年生，博士研究生，主要研究方向为复杂网络、软件工程．Ｅｍａｉｌ：ｈｙｎ＠ｎｌｓｄｅ．ｂｕａａ．ｅｄｕ．ｃｎ．李德毅，男，１９４４年生，博士生导师，中国工程院院士，主要研究领域为复杂网络、数据挖掘、人工智能．陈桂生，男，１９６５年，博士，研究员，主要研究领域为复杂网络、人工智能．软件网络的多粒度拓扑特性分析及其应用韩言妮１） 李德毅１），２） 陈桂生２）１）（北京航空航天大学软件开发环境国家重点实验室 北京 １００１９１）２）（中国电子工程系统研究所 北京 １００１４１）摘 要 随着软件与网络的融合，以网络为基础的软件系统在规模、用户数量、组成单元的交互关系方面都成数量级的增长，成为一类重要的复杂系统，超出了开发人员的理解和控制．文中首先分析软件工程４０年来软件开发设计方法学的变迁历程，并给出软件网络的定性描述，提出网络时代软件工程的新观点．然后以ｅＣｏｓ开源系统为分析载体，从不同粒度上对网络模型进行拓扑特性分析，结果表明该载体网络在不同粒度上具有自相似的结构特性．最后针对嵌入式系统的本质特性，从节点异质性、局部抱团性和多粒度的网络规模简约３个方面进行实证分析，用以指导嵌入式软件系统的可配置、可裁剪目标，从而达到资源的最小负载．关键词 软件网络；中心性；社区结构；拓扑势；复杂网络中图法分类号ＴＰ３１１ 犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２００９．０１７１１犃狀犪犾狔狊犻狊狅狀狋犺犲犜狅狆狅犾狅犵犻犮犪犾犘狉狅狆犲狉狋犻犲狊狅犳犛狅犳狋狑犪狉犲犖犲狋狑狅狉犽犪狋犇犻犳犳犲狉犲狀狋犔犲狏犲犾狊狅犳犌狉犪狀狌犾犪狉犻狋狔犪狀犱犐狋狊犃狆狆犾犻犮犪狋犻狅狀ＨＡＮＹａｎＮｉ１） ＬＩＤｅＹｉ１），２） ＣＨＥＮＧｕｉＳｈｅｎｇ２）１）（犛狋犪狋犲犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犛狅犳狋狑犪狉犲犇犲狏犲犾狅狆犿犲狀狋犈狀狏犻狉狅狀犿犲狀狋，犅犲犻犺犪狀犵犝狀犻狏犲狉狊犻狋狔，犅犲犻犼犻狀犵 １００１９１）２）（犐狀狊狋犻狋狌狋犲狅犳犈犾犲犮狋狉狅狀犻犮犛狔狊狋犲犿犈狀犵犻狀犲犲狉犻狀犵，犅犲犻犼犻狀犵 １００１４１）犃犫狊狋狉犪犮狋 ＷｉｔｈｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆｓｏｆｔｗａｒｅａｎｄＩｎｔｅｒｎｅｔ，ｃｏｍｐｌｅｘｉｔｙｏｆｓｏｆｔｗａｒｅｓｙｓｔｅｍｓｂａｓｅｄｏｎｔｈｅＩｎｔｅｒｎｅｔｉｓａｎｅｖｅｒｐｒｅｓｅｎｔｂａｒｒｉｅｒｉｎｓｙｓｔｅｍｄｅｖｅｌｏｐｍｅｎｔａｎｄｅｖｏｌｕｔｉｏｎ．Ｉｔｓｐｒｉｎｃｉｐａｌｍａｎｉｆｅｓｔａｔｉｏｎｉｓｔｈｅｍａｓｓｉｖｅａｃｃｕｍｕｌａｔｉｏｎｏｆｌｏｗｌｅｖｅｌｄｅｔａｉｌｓａｎｄｉｎｔｒｉｃａｔｅｒｅｌａｔｉｏｎｓｈｉｐｓａｍｏｎｇｔｈｅｍｔｈａｔｑｕｉｃｋｌｙｅｘｃｅｅｄｓｈｕｍａｎｕｎｄｅｒｓｔａｎｄｉｎｇ．Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｔｈｅｑｕａｌｉｔａｔｉｖｅｄｅｓｃｒｉｐｔｉｏｎｏｆｓｏｆｔｗａｒｅｎｅｔｗｏｒｋｉｎｔｈｅｃｏｎｔｅｘｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋ，ｔｈｅｎｇｉｖｅｓａｎａｌｙｓｉｓｏｆｔｈｅｃｈａｎｇｅｈｉｓｔｏｒｙｏｆｓｏｆｔｗａｒｅｄｅｖｅｌｏｐｍｅｎｔｍｅｔｈｏｄｏｌｏｇｙａｎｄｉｎｔｒｏｄｕｃｅｓｔｈｅｎｅｗｐｅｒｓｐｅｃｔｉｖｅｏｆｓｏｆｔｗａｒｅｅｎｇｉｎｅｅｒｉｎｇｉｎｎｅｔｗｏｒｋａｇｅ．Ｔｏｖａｌｉｄａｔｅｔｈｉｓｉｄｅａ，ｔｈｅａｕｔｈｏｒｓｓｔｕｄｙｔｈｅｅＣｏｓｏｐｅｎｓｏｕｒｃｅｓｙｓｔｅｍａｎｄａｎａｌｙｚｅｔｈｅｉｒｎｅｔｗｏｒｋｓｔｒｕｃｔｕｒｅａｔｄｉｆｆｅｒｅｎｔｌｅｖｅｌｓｏｆｇｒａｎｕｌａｒｉｔｙ．Ｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｙｅｘｈｉｂｉｔｔｈｅｓｔｒｕｃｔｕｒｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｓｅｌｆｓｉｍｉｌａｒｉｔｙａｔｄｉｆｆｅｒｅｎｔｌｅｖｅｌｓ．Ｆｉｎａｌｌｙ，ｉｎａｃｃｏｒｄａｎｃｅｗｉｔｈｔｈｅｅｓｓｅｎｃｅｏｆｅｍｂｅｄｄｅｄｓｙｓｔｅｍ，ｔｈｅｈｅｔｅｒｏｇｅｎｅｉｔｙｏｆｎｏｄｅｓ，ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅａｎｄｎｅｔｗｏｒｋｒｅｄｕｃｔｉｏｎａｒｅｔｅｓｔｅｄａｔｄｉｆｆｅｒｅｎｔｇｒａｎｕｌａｒｉｔｙ．Ｔｈｅｓｅｒｅｓｕｌｔｓｈａｖｅｓｏｍｅｐｒａｃｔｉｃａｌｖａｌｕｅｉｎｃｌｕｄｉｎｇｔｈａｔｉｔａｌｌｏｗｓｕｓｔｏｉｄｅｎｔｉｆｙｉｍｐｏｒｔａｎｔｃｏｍｐｏｎｅｎｔｓ，ｉｎｓｔｒｕｃｔｓｔｈｅｓｏｆｔｗａｒｅｃｏｎｆｉｇｕｒａｔｉｏｎａｎｄｃｕｔｏｆｆｗｉｔｈｌｅｓｓｌｏａｄｃｏｓｔ，ｔｈｅｒｅｂｙａｓｓｉｓｔｓｔｈｅｍａｉｎｔｅｎａｎｃｅａｎｄｒｅｕｓａｂｉｌｉｔｙｏｆｔｈｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ．犓犲狔狑狅狉犱狊 ｓｏｆｔｗａｒｅｎｅｔｗｏｒｋ；ｃｅｎｔｒａｌｉｔｙ；ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｔｏｐｏｌｏｇｙｐｏｔｅｎｔｉａｌ；ｃｏｍｐｌｅｘｎｅｔｗｏｒｋ１ 引 言在人类五千年的文明中，６０多年前计算机的发明对人类社会的影响是显著的．计算机科学从电子学中脱颖而出，紧接着是软件工程从计算机体系结构中脱颖而出．为克服以手工作坊方式为主的软件生产引发的软件危机，１９６８年在原西德召开的北大西洋公约组织（ＮＡＴＯ）会议上，人们第一次提出了软件工程的概念［１］．软件脱离硬件作为一个独立产业，必然要关注软件的开发效率、大规模定制、大批量生产和自动化检验．软件工程领域中，经过多年的工程实践，人们已经意识到软件结构的重要地位，软件工程进行结构分析研究的根本目的就是为工程实践人员开发高质量的软件提供指导．然而随着软件系统规模和复杂程度的改变，大量堆积的底层元素和它们之间错综复杂的交互关系，已逐渐超出了软件开发人员的理解能力，致使系统难以理解和维护，软件开发经常处于失控状态，软件系统中一个极小的错误都可能带来灾难性的后果，甚至引发“雪崩效应”［２３］．同时，由于缺乏相应的方法，传统的软件开发人员很少从整体和全局的观点来审视软件的结构及其演化规律，导致对软件结构的本质缺乏清晰的认知，软件的动态演化和质量难以保证［４５］．在这种情况下，我们需要转变视角来应对我们遇到的问题，复杂网络的研究成果为探索大规模软件系统的结构特性提供了有力的支持，与传统软件方法中只侧重微观层面的设计不同，复杂网络从整体上把握系统，关注内部属性与外部整体特性之间的映射关系和系统整体涌现出的新特性［６］，为控制软件复杂性与保证软件质量提供了强有力的工具．自２００２年开始，不同领域的研究者对各类软件系统进行研究，将软件系统看作是不同软件单元的自组织、可伸缩、动态演化的复杂系统，发现软件系统的内部结构并不是随机无序的，都表现出复杂系统非常明显的“小世界”和“无标度”特性［７８］，到目前为止，软件系统的拓扑结构分析方面取得了较好的研究进展．但在试验结果的基础上，对软件系统内部结构的复杂特性进行深层的解释却存在挑战，大多数研究者猜测各类现象可能与软件开发过程中的一些规则和决策有关，例如Ｍｙｅｒｓ认为软件结构中存在一些入度大的ｈｕｂ节点是由于软件开发鼓励重用导致的［４］，而Ｖａｌｖｅｒｄｅ则认为ｈｕｂ节点与软件开发过程降低开发成本的目标（分布式开发、“高内聚、低耦合”特性和鼓励重用等）存在着关联［９］．因此，到目前为止，研究者依据软件工程领域的知识，完整系统地对软件系统内部的复杂特性给出令人满意的解释，是一项有待于进一步深入研究的工作．本文选择ＲｅｄＨａｔ公司开发的具有高度模块化和内核可配置特性的ｅＣｏｓ为载体进行拓扑特性及深层挖掘分析，发现其内部结构的共性特征和形成机制，为灵活地配置裁剪提供指导．本文第２节分析网络时代下软件形态和开发方法的改变，对软件网络进行严格定义并提出网络时代软件工程的新观点；第３节在不同粒度上抽象出ｅＣｏｓ的网络模型，从全局和连接特性两个方面进行统计分析，并阐述不同指标在ｅＣｏｓ系统中的具体含义；第４节在统计分析基础上，从节点异质性、局部抱团性和多粒度的网络规模简约３个方面对该载体网络进行实证分析与结果验证；第５节进行总结．２ 网络时代的软件工程观回顾软件工程的发展过程，虽然尚未彻底解决“软件危机”的问题，但也极大地推动了软件开发的工程化以及软件产业的迅速发展．通常，人们把软件工程走过的道路，概括为从面向过程、面向对象、面向构件、直到面向网络服务４个阶段，如图１所示．图１ 软件工程４０多年的发展历程２．１ 软件开发设计方法学的变迁从科学的角度来讲，虽然软件工程发展过程比较发散，但也出现了许多具有里程碑意义的进展．这里从软件开发设计方法的视角来审视软件技术不断演化与发展的过程．２０世纪６０年代软件发展的初期，计算机以单机工作为主，软件开发直接从编码（ｃｏｄｉｎｇ）开始，程序规模较小，很少考虑系统的结构．随着软件规模不断增大，软件开发效率低下，质量难以保证，软件危机产生．２１７１计 算 机 学 报２００９年２０世纪７０年代中后期，Ｙｏｕｒｄｏｎ和Ｃｏｎｓｔａｎｔｉｎｅ提出了结构化分析设计方法（ＳＡＳＤ）［１０］，将一个复杂的程序分解为函数或过程，强调计算流程中的顺序、循环和条件３个基本要素，关注程序开发过程和执行过程，考虑需求分析、结构设计、编码到软件测试整个流程，产生了软件生命周期的概念，形成一整套的软件开发工具，这种面向过程的方法学偏重在编码层面上．２０世纪８０年代，随着软件结构易变性以及软件复用性的需求上升，面向对象的程序设计方法逐渐成熟，软件的设计、编码以类和类的对象之间的关系为核心，封装、继承和多态成为３个重要特征［１１］，面向对象软件开发方法和设计工具的兴起和成熟，产生了许多不同的实施方案，比较著名的有ＣｏａｄＹｏｕｒｄｏｎ方法［１２］、Ｂｏｏｃｈ方法［１３］、Ｒｕｍｂａｕｇｈ等的面向对象建模（ＯＭＴ）方法［１４］、Ｒｅｅｎｓｋａｕｇ的面向对象的角色分析、合成和构造（ＯＯＲＡＳＳ）方法［１５］、Ｊａｃｏｂｓｏｎ的面向软件工程对象的方法（ＯＯＳＥ）［１６］等等．这就把编码层面的方法学上升到软件设计层面的方法学．２０世纪末期，人们寻求比“类”的粒度更大、易于复用的构件，软件工程进入了面向构件的阶段，面向构件的方法将构件的接口与实现进行有效的分离，增加了构件交互和重用的能力，软件行业也形成了３个代表性的构件技术标准，分别是对象管理组织（ＯＭＧ）提出的公共对象请求代理体系结构（ＣＯＲＢＡ）［１７］、Ｓｕｎ公司提出Ｊ２ＥＥ（Ｊａｖａ２ＰｌａｔｆｏｒｍＥｎｔｅｒｐｒｉｓｅＥｄｉｔｉｏｎ）［１８］和Ｍｉｃｒｏｓｏｆｔ公司提出的分布式构件对象模型（ＣＯＭ／ＤＣＯＭ）［１９］．面向对象的软件设计方法学上升到软件体系结构的方法学．进入２０世纪９０年代后期，网络的发展改变了人们对软件的需求，软件产业从制造业转变为服务业，无论是软件自身形态，还是软件的工作环境，都是网络化了的．软件作为服务（ＳｏｆｔｗａｒｅａｓａＳｅｒｖｉｃｅ，ＳａａＳ）已经成为一种趋势，软件工程进入了面向网络服务的时代，它以可扩展标记语言（ＸＭＬ）、简单对象访问协议（ＳＯＡＰ）、超文本传输协议（ＨＴＴＰ）、本体Ｗｅｂ语言（ＯＷＬ）和统一描述、发现和集成（ＵＤＤＩ）、网络服务描述语言（ＷＳＤＬ）和元模型框架（ＭＦＩ）等为主要内容［２０］，软件的开发已经从体系结构的层面上升为了面向网络资源的开发方法学．因此，在过去的４０年中，科学家们对软件工程的关注域总是在“与时俱进”，对软件的思维方式的不断变化导致了软件开发方法的转变，也催生了软件新技术的不断涌现，如图２所示．可以看出随着系统规模和复杂性的提高，个性化和多元化的需求比重越来越大，资源共享与聚合的趋势越来越强，软件的计算模式、应