叶云斐 陈晓建 陈伟青 谷叶
（中国民用航空华东地区空中交通管理局 上海 200335）
摘 要 鉴于传统构架的协同决策（CDM）系统不能适应民航事业快速发展，提出建立基于云计算平台的CDM系统。
首先概述了云计算的基本概念和主要特征，并总结了云计算的关键技术和基本架构。之后，研究了对云计算拓扑设计算法，在树形拓扑结构的基础上对三种算法进行了比较和选择，确定方案为merge-MST。最后，完成云计算平台的初步总体设计，并搭建仿真测试平台，测试结果证明所设计的云计算CDM系统具有较好的性能。
教育期刊网 http://www.jyqkw.com
关键词 民航，协同决策系统，云计算
中图分类号：TP392 文献标识码：A
doi:10.3969/j.issn.1674-7933.2015.04.004
*基金项目：上海市2013 年“ 科技创新行动计划”信息技术领域项目（13511504700） 。
作者简介：叶云斐，1984 年生，本科，助理工程师，主要从事及研究领域：航空计算机信息管理，Email ：leaves616@126.com ；
陈晓建，研究生，高级工程师；
陈伟青，本科，工程师；
谷叶，研究生，助理工程师。
0 引言
近年来我国民航事业快速发展，航班延误现象愈发严重。中国民用航空局发布的《2013年民航行业发展统计公报》显示： 2013年不正常航班占比27.66%，旅客投诉率较2012年增长13.66%。华东区域经济发展迅速，人口密度大，以全国1/9的空域面积承载着1/3的航班流量，问题尤为显著。以发展的眼光看问题，有必要依靠各方可靠、全面、实时的信息，采用高效合理的航班排序、放飞算法，充分利用空域时隙资源，协同决策（CDM）的概念应运而生。
民航华东空管局CDM系统于2012年12月上线运行，系统基础数据多，计算量大，对软硬件资源要求高。以上海虹桥、浦东两个机场为例，每天就有5 000多架航班起落，涉及空域航路点300~400个，各航路点又分3~4个高度层；在此基础上，CDM系统必须结合实时发布的流量控制、气象预报等信息反复计算调整，且任何时刻的航班重新规划都会影响到一整条航路上与之相关的所有航班，使计算量成倍增加。随着航空流量的逐年增加，CDM系统计算量也以指数方式快速增长。
现有系统采用传统架构设计，不能满足前瞻性设计要求。理想的CDM系统架构应具有虚拟化、易扩展、按需部署、高灵活性、高可靠性、高性价比的特点。本文提出一种基于云计算的CDM系统构架，利用自动拓扑设计算法（merge-MST）设计网络拓扑，采用Hadoop开源管理软件实现任务调度，最后通过仿真手段验证了该方案的可行性和适用性。
1 现有民航CDM系统的不足
协同决策是一种技术手段，更是一种基于资源共性和信息交互的多主体（空管、机场、航空公司等）联合协作运行模式。华东空管局CDM系统从各个参与单位引接实时航班数据，建立塔台电子进程单系统、A-CDM系统、飞行计划处理系统等，并形成三大客户端——流量管理客户端、塔台客户端和公司机场客户端，系统构成如图1所示。
`该系统基于传统的关系型数据库，以塔台电子进程单为例，架构示意图如图2所示。尽管其成熟度高、可靠性好，但随着数据量逐渐增大，数据范围逐渐拓宽，其存储和查询效率已不能满足需求。
2 云计算平台及其架构设计
2.1 定义和特点
云计算是一种新的计算模式，由分布式计算、并行计算和网格计算的发展而来。其后台大量采用虚拟机，并通过互联网形成资源池。这些虚拟资源可以根据不同的负载动态重新配置，快速并以最小的管理代价提供服务[1]。从用户角度看，云计算具有可靠的存储技术和严格的权限策略，可为客户提供安全可靠的数据存储中心；对用户端的设备要求低，支持手机、平板电脑等无线通信设备；可实现不同设备间的数据、应用共享。
从硬件的角度看，云计算高度灵活，可按需投入或释放硬件资源，从而提高整体利用率。2.2 类型
云计算按其服务层次分为三类[2]，如图3所示：
1)基础设施即服务（IaaS，infrastructure as a service）
在虚拟化技术的支持下，利用廉价计算机实现大规模集群运算能力，同时按需配置，为用户提供个性化的基础设施服务。此类型的典型代表有亚马逊云计算AWS（Amazon Web Services）、IBM蓝云等。
2) 平台即服务（PaaS，platform as a service）
提供的服务是开发环境，允许用户使用中间商提供的设备开发自己的程序。此类型的典型代表有GoogleApp Engine（GAE）等。
3) 软件即服务（SaaS，software as a service）
通过Internet直接提供运行在云计算设备上的应用程序。用户无需考虑基础设施及软件授权等内容。此类型的典型代表有Salesforce公司的CRM服务、ZohoOffi ce、Webex等。
2.3 关键技术
云计算作为一种集群计算和服务模式，运用了多种计算机技术，以编程模型、数据存储管理、虚拟化最为关键。
1) 编程模型
Google提出的Map-Reduce[3]是一种流行的云计算编程模式，Map（映射）程序将数据分割成不相关的数据块，Reduce（化简）程序则将将数据处理的中间结果进行归并，如图4所示。Map-Reduce可将海量异构数据的分析处理工作分解成任意粒度的子任务，并允许在多个计算节点之间进行灵活的数据调度，此外，程序员无需关心数据块的分配和调度，该部分工作由平台自动完成。
2) 数据存储管理
云计算采用分布式的方法存储和管理数据，并利用冗余存储保证数据的可靠性，常用技术有Google的GFS及Hadoop团队的HDFS[4]，其中后者是前者的开源实现。
GFS系统架构如图5所示，整个系统节点分三类：Client（客户端）是GFS提供给应用程序的访问接口、Master（主服务器）是管理节点， Chunk Server（数据块服务器）则负责具体工作。Chunk Server可有多个，每个Chunk对应一个索引号（Index）。作为对比，HDFS体系结构如图6所示。
云计算的数据管理需满足大规模海量数据的计算和分析，大多采用列存储的数据管理模式。现有技术中最主流的是Google的BigTable，Google对BigTable给出了如下定义：BigTable是一种为了管理结构化数据而设计的分布式存储系统，这些数据可以扩展到非常大的规模。此外，Hadoop团队也开发了类似BigTable的开源产品HBase和Hive。
3) 虚拟化技术
虚拟化技术是云计算区别于一般并行计算的根本性特点，其实质是实现软件应用与底层硬件相隔离，把物理资源变成逻辑可管理资源。目前云计算中虚拟化技术主要包括将单个资源划分成多个虚拟资源的裂分模式，也包括将多个资源整合成一个虚拟资源的聚合模式。根据对象又可分为存储虚拟化、计算虚拟化、应用级虚拟化等等。
将虚拟化的技术应用到云计算平台，使得云计算具有灵活的进程迁移方式，更有效的使用主机资源，在部署上也更加灵活。
2.4 架构设计
云计算体系结构的特点包括：设备众多、规模大、采用虚拟机技术、任意地点、多种设备汇集，并可以定制服务质量等等。文献[5]提出了一种面向市场应用的云计算体系结构，如图7所示：
1) 用户：用户可以在任意地点提交服务请求；
2) SLA资源分配器：充当云后端和用户之间的接口，包括服务请求检测和接纳控制模块、计价模块、会计模块、VM监视器模块、分发器模块和服务请求监视器模块；
3) 虚拟机（VMs）：为实现在一台物理机上的多个服务提供最大弹性的资源分配；
4) 物理设备：包括服务器、存储设备及路由器等。
基于云计算平台的华东CDM系统还处于初步研究阶段，采用本架构进行初步设计及仿真验证。
3 云计算网络拓扑设计
云计算系统后端的网络由大量服务器组成，分布广泛，复杂度高。要保证数据的畅通传输，需要设计一个合理高效的网络拓扑结构。
首先，为保证管理扩展和维护的方便，将云计算系统分成多个子网，各子网采用树形拓扑结构，如图8所示。在此基础上，把每个子网看成一个节点，各个节点具备流量、交换能力、地理位置等属性，将云计算网络拓扑抽象成图论数学模型。如何连接各个节点，才能即满足冗余度要求，又尽可能降低网络架设花销已被证明为NP-hard[6][7]，故只能求解近似最优解。此类问题的解法有两种，一种是在限定网络花销的情况下最大化网络的抗毁能力[8]，另一种是在保证网络一定抗毁能力的条件下尽可能减小花销[7]，本文按照后者进行设计。
在图论领域，该问题可简化为求解特定连通度k时最小生成子图的问题，本文主要考虑基于图论的k-FOREST算法[9]、merge-MST算法[10]和启发式算法TEA[7]。通过理论推导，三种算法的时间复杂度如表1所示，其中TMST=O(m?logm)或O(n2),m代表图边数，n代表点数。
本文教育期刊网 http://www.jyqkw.com
参考文献[11]的仿真手段对三种算法进行比较，考虑7、10、15、25个节点的场景，得到平均边数和平均花销的比较示意图如图9、10所示。
通过比较可看出，在节点数目较少时TEA算法表现最佳，但随着节点数目增多性能迅速下降；在节点数多于20个时，则是merge-MST算法更优。
考虑到CDM系统规模庞大，仅华东区域就需要计算机点80~100个，故选取merge-MST进行网络架构的设计。
4 总方案设计
基于云计算架构的CDM系统，依托中心节点、区域节点和业务集中节点，整合分布的物理资源，形成统一的可调配的逻辑资源。总方案结构如图11所示。包括基础设施、虚拟资源层、信息共享云平台层，应用层以及贯穿始终的安全层和管理层。
1) 基础设施层：既包括支持民航CDM系统运行所必需的基础设施，也包括行业内可整合入CDM系统的其他设施。
2) 虚拟资源层：采用云计算技术，整合分布的硬件资源，形成资源池，灵活调配提供服务。
3) 云平台层：涵盖管理底层资源、支撑上层应用的各个软件和模块，包括平台管理、负载均衡、中间件、业务流程管理软件等等。
4) 应用层：将CDM系统功能进行最后一步封装后提供给用户。
5) 安全层：负责整个CDM系统的安全。
6) 管理层：管理整个CDM系统运行配置，包括资源管理、网络监控、部署管理、内容管理以及用户管理等，监控硬件、软件等多个层次，提高整体运行效率。
5 系统测试与应用
为验证所设计方案的可行性，并测试方案性能，本文搭建了测试环境，针对CDM系统多项业务进行了测试。
CDM系统主要业务涵盖协同决策系统、流量管理系统、统一飞行计划处理系统和塔台电子进程单系统。其中协同决策系统为顶层系统；流量管理系统帮助最大限度利用空中交通服务的容量；统一飞行计划处理系统负责接收、处理和发布飞行计划；塔台电子进程单系统则协助塔台管制员管制飞机的起降。
5.1 硬件环境
云计算集群设有3个master节点，18个slave节点，各节点均是基于X86架构的PC机。PC机配置如表2所示。
所有测试主机均连接在千兆网络中，网络环境中不存在其他设备，干扰因素可忽略不计。
5.2 软件环境
测试采用Hadoop团队开发的开源软件，版本如表3所示。
5.3 测试结果
通过编写程序，在测试环境中进行电报处理、雷达轨迹处理、气象与情报处理、桥位信息处理、航班信息发布、数据查询以及协同航班处理等压力测试，平均日最大处理条目数量如表4所示。
测试结果表明：云计算平台计算能力强，能够弥补现有民航CDM系统的不足，可满足华东地区CDM系统前瞻性设计要求。
6 结束语
本文针对华东地区巨大的航班吞吐量，提出了一套基于云计算平台的CDM系统设计方案。通过测试验证，该系统架构具备良好的计算能力和业务处理能力，使用灵活，更满足系统安全可靠、成本低、易拓展的需求。
基于云计算的华东空管CDM系统是现有CDM系统的发展方向，将在2015年开始详细设计。
教育期刊网 http://www.jyqkw.com
参考文献
Vaquero L, Rodero-Marino L.Caceres J. et al. A break in theclouds: towards a cloud defi nition[J]. SIGCOMM ComputerCommunication Review. 2009,3(1): 50-55.
UC Berkeley 可靠自适应分布式系统实验室, 姚宏宇译. 云端之上——Berkeley对云计算的看法. 2009.
J. Dean, S. Ghemawat, MapReduce: Simplified DataProcessing on Large Cluster[C], OSDI’04, Sixth Symposiumon Operating System Design and Implementation, SanFrancisco, CA, December, 2004.
Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung.The Google File System[C]. Proceedings of 19th ACMSymposium on Operating Systems Principles. 2003, 37(5):20~43.
R. Buyya, C.S. Yeo, S. Venugopal, Market-OrientedCloud Computing: Vision, Hype, and Reality for DeliveringIT Services as Computing Utilities [C], The 10th IEEEInternational Conference on High Performance Computingand Communications.
S. Pierre, G. Legault, A Genetic Algorithm for DesigningDistribute Computer Network Topologies[J], IEEE Trans.Man, Systems, and Cybernetics, 28(2), 1998: 249-258.
E. Szlachcic, Fault Tolerant Topological Design for ComputerNetworks[C], Proceedings of the international Conferenceon Dependability of Computer Systems, DepCos-RELCOMEX’06.
F.M. Shao, X. Shen, and P.H. Ho. Reliability Optimization ofDistributed Access Networks with Constrained Total Cost[J],IEEE Trans. Reliability, 2005,54:412-430.
H. Nagamochi, T. Ibaraki, A linear-time algorithm for fi ndinga sparse k-connected spanning subgraph of a k-connectedgraph [J], Algorithmica 7, 1992, (7): 583-596.
X. Junming. Topological Structure and Analysis ofInterconnection Networks[C], Kluwer Academic Publishers,2001.
邓自立. 云计算中的网络拓扑设计和Hadoop平台研究[D], 中国科技大学, 2009.