基于动态可视化的空间信息网络拓扑演化浅析

于少波, 吴玲达, 岑鹏瑞, 李 超, 万秉承

(1. 航天工程大学，北京 101416； 2.北京市遥感信息研究所，北京 100192；3. 61618部队，北京 100094； 4.国防大学研究生院,北京 100036)

0 引 言

现代人类社会和虚拟网络社会的方方面面都存在形式各异的网络，如基于电话、邮件的通信网络，基于媒介的社交网路，基于运输的城市交通网，基于合作的科研学术网，基于交易的金融网，基于军事应用的指挥控制网、信息通信网、预警探测网、导航定位网和综合信息网等。无论是民生需求还是军事应用，无论是工作学习还是文化生活，网络无处不在，也处处彰显着人类对网络极大的依赖。

网络拓扑演化[1]是指对网络拓扑结构的节点和连边随时间的新生、消亡和演变的描述，也是指网络拓扑结构的形成、更新和变化的过程和机制。研究网络拓扑演化的主要目的就是通过建立其动态模型，通过识别并捕捉对网络拓扑结构有影响的关键因素，了解网络的动态变化过程，从而更加深刻地认识网络的拓扑结构。现阶段，关于网络拓扑演化问题的研究，大多数都是结合具体的研究对象而展开，其中特别是以无线传感器网络和在线社会网络最为典型[2]。

空间信息网络(Space Information Networks，SINs)作为网络理论与空间信息科学交叉发展的前沿，已经成为当前的热点研究领域。学术界对空间信息网络的广泛认识是指：空间信息网络是以空间平台为载体，实时获取、传输和处理空间信息的网络系统，是为陆基、海基、空基和天基的各类用户活动提供信息保障的基础设施[3]。空间信息网络作为一个复杂巨型网络系统，作为空间信息系统、天基综合信息网发展的新形态，与其他网络系统相比，有一些显著特征，其中，从时空行为上看，以动态特征最为典型[4]。空间信息网络的动态特征又可以细化为时间域的时变特征和空间域的空变特征。时变特征是指随着时间的推移，组成空间信息网络的卫星、飞机等空间实体的增加、失效和更新，不同空间实体间信息传输的连接断开等现象。空变特征是指随着时间的推移，组成空间信息网络的卫星、气球等空间实体时刻发生位置变化的现象，也即空间信息网络节点的高动态运动。

传统研究复杂网络的拓扑演化只是考虑其时变特征所带来的拓扑结构的改变，而对于空间信息网络来说，其时变特征和空变特征是同时存在且同时发生的，因而这就导致空间信息网络拓扑处于实时的动态变化中，大大增加了其网络拓扑的不规则性，因此，是否能够将研究复杂网络拓扑演化的方法移植到空间信息网络的研究上来，其可行性和有效性还有待验证。

动态网络可视化最早可以追溯到动态图的可视化，主要是指研究随着时间的推移，组成网络的节点和连线的数量和属性等发生改变，所导致的可视化视图发生改变的一个交叉领域。可视化技术在当前时期应用的领域较为广泛，然而应用的方式也较为集中，主要是用于数据分析和可视分析。为此，基于上述思考，本文基于动态可视化技术，提出一种基于动态可视化的空间信息网络拓扑演化思路，简称为可视演化方法，旨在为空间信息网络拓扑演化的研究提供新的思路。

1 基础理论及相关工作

1.1 空间信息网络

引言部分曾给出空间信息网络的广义概念，为了便于后期展开研究和进行验证，因此，需要对空间信息网络的节点和连边进行界定。将空间信息网络的规模控制在有效、适当的范围是后续研究的前提和基础，在空间信息网络广义概念的基础上，从组成和功能出发，我们给出了其狭义概念，如下所示。

定义1(空间信息网络狭义概念)：空间信息网络是以卫星系统(同步卫星或中、低轨道卫星，主要负责处理载荷)为主干网络，连接其他信息系统(临近空间的气球或飞机等)或终端(地面站，主要负责控制)，提供一体化的侦查、导航、通信等服务、实现通信广播、侦查监视、情报探测、导航定位、导弹预警和气象、水文、地形等战场态势感知的综合信息网络系统。结合空间信息网络的狭义概念，我们给出其组成结构划分(如图1所示)，空间信息网络主要由同步卫星系统(GEO层)，中、低轨道卫星系统(MEO/LEO层)，临近空间飞行器系统(Near Space层)和地面终端(Ground层)组成[2]。

图1 空间信息网络组成结构示意图

1.2 网络拓扑及其演化

数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长是短，是弯曲还是平直，有没有相交等现象并不是他们关注的重点。通过长时间的研究和积累，将网络不依赖于节点和具体位置的变动的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做拓扑结构。从200多年来的发展历程来看，关于什么样的拓扑结构适合描述真实系统的问题经历了三个阶段。

第一个阶段，也即规则网络阶段，时间跨度在最初的100年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示。第二个阶段，也即随机网络阶段，自20世纪50年代末到接下来的40年时间里，随机网络被认为是最适宜描述真实系统的网络。第三个阶段，也即复杂网络阶段，直到20世纪90年代后期，源于基于计算机进行数据处理和运算能力的飞速发展，科学家们逐渐发现大量的真实系统既不能用规则网络，也不能用随机网络进行准确描述，因而，复杂网络阶段随即到来[5]。

正如Barabasi的观点：“无标度特性的意义之一在于认识到网络系统的结构和演化是不可分割的”[6]，所以在空间信息网络拓扑结构模型的基础上，研究空间信息网络的演化机制和演化模型就显得尤为重要，同时也是必须要完成的工作。前文曾提到，关于网络拓扑演化问题的研究，大多数都是结合具体的研究对象而展开，其中特别是以无线传感器网络和在线社会网络为最多，通过归纳可知，当前网络拓扑演化研究存在以下问题：

一是针对具体对象的特点展开，方法缺乏普适性；

二是思路较为单一固定，没有脱离复杂网络本身包含的范围之列；

三是演化结果都是通过仿真验证，其结果理解需要一定的背景知识，不适合大多数用户去识记。

综上所述，急需引入新理论、新技术去探索新的思路和方法。

1.3 动态可视化

动态网络数据是流数据的一种，其中“动态”一词可以理解为节点的增加、删除，连边的连接、断开连等几种情形。由于动态网络可视化的数据处于不断的更新状态，且新产生的数据对原先可视化效果带来影响的不可控性和不可估计性，这为动态网络可视化带来了巨大的挑战。结合用户对可视化视图视觉感知的特点，设计动态网络可视化时应该尽量保证帧与帧之间的连续性与一致性。

可视化技术凭借其直观、形象、易于理解的特点而受到众多行业的青睐，经过几十年的发展，逐渐从科学计算可视化、信息可视化发展为当前时期的大数据可视化、动态可视化、可视分析等多个方向和分支。动态可视化主要包含三个方面的内容，也即网络布局、网络属性可视化和用户交互，研究动态网络可视化主要是攻克上述三个方面的内容。与其它可视化技术一样，动态可视化也存在一些基本的功能和性能要求，如要在整个可视化过程中满足基本美学准则的同时，为了不影响可视化结果的展示，要始终能够保持用户的意向图等[7]，本文不再赘述。

2 可视演化关键技术

在第1.3节中曾提到，网络动态可视化主要包含网络布局、网络属性可视化和用户交互，应用到空间信息网络拓扑演化中来，相应的布局方法、可视化方法和交互方法则是实现可视演化的关键技术，同时引入时间轴，将时间属性与图进行融合是贯穿整个演化过程的中心环节。接下来，将从布局技术、可视化技术和交互技术三方面进行阐述，如表1所示为归类列表。

如上表1所示，动态网络布局方法主要包括力导向图方法及其改进；网络可视化方法主要包括动画方法和时间线方法两种；而动态网络交互方法主要包括鱼眼视图方法、焦点上下文方法和多视图关联协调方法等，下面分别进行论述。

表1 可视演化关键技术归类

2.1 基于FDA的网络布局技术

布局 (Layout) 字面上的意思是指对事物的全面规划和安排，也指分布的态势、相对的位置等。在可视化中，布局是一项重要的内容，合理的布局能够轻松制作很多高效的图表。探究布局的实质，发现其是发挥数据转化的作用，而布局的意义就在于计算方便绘图的数据，布局的使用要遵循以下顺序，也即确定初始数据→转换数据→绘制。通过查阅文献可知，针对动态网络布局中最为典型和最基本的布局技术便是力导向图布局，简称力布局 (Force-Directed Layout, FDL)。 大多数动态网络布局方法都是在FDL的基础上进行的延伸和改进。对力的模拟是可视化最令人激动的技术之一，也是进行解决可视演化的有效手段。

2.2 基于动画的可视化技术

基于动画的可视化技术，其核心思想是指在动态网络的动画表示过程中，将其时间序列直接映射到可视化时间戳[8]，该技术又可以细分为在线方法和离线方法，在基于动画的可视化方法中，还有重要一步那便是过渡，激励一个节点-连边算法不仅要求要有一个确定的时间序列布局，同时，布局之间传递的连贯性也需要被模仿，从而确保在同时发生的较多的改变可以被用户追踪和观察，目前广泛应用的是通过阶段过渡实现布局之间的转换。

总的来说，在线方法更加灵活一些，因为它适用的场景不需要考虑动画开始的时间，相反，离线方法具有更优化的布局结构和能够更好的维护思维地图的状态，因为其下一个改变是已知的。然而，不论是在线方法还是离线方法，动画技术都需要过渡技术来支撑其更好的进行动态网络的可视化，动画技术不仅需要决定动态图布局序列，而且需要建模布局序列之间的过渡，如果2个布局之间只是简单地直接转换，不但可视化效果缺乏美感，而且瞬间改变的信息容易给用户造成认知困难，所以只有将上述技术完美的融合在一起，才能实现理想的可视化效果。

2.3 基于时间线的可视化技术

不同于动画技术，一种基于时间线的方法被提了出来，该方法的核心是将网络通过时间到空间映射的方法绘制成时间线，根据不同特征，可以将基于时间线的可视化技术细分为基于节点-连边、基于邻接矩阵和基于邻接表三种方法[9]。基于节点-连边技术是一种在时间线上放置节点-连边图的方法，该技术只需要将节点一个挨着一个放置即可，所以它更适宜一个具有固定布局。基于邻接矩阵技术主要是应用于静态网络的可视化，后来，被用作基于时间线的动态网络可视化，证明是可行的。针对动态需求，其最大的挑战便是连接时间的空间编码和矩阵信息，所以这就比节点-连边方法难度较大，而其原因可以归结为矩阵布局缺乏灵活性。邻接表作为一种数据结构是较为通用的模拟网络的方法，然而却很少被用于实现可视化，基于邻接表技术的现是基于使用带有不同颜色的方格去描述起源和目的的边，这种方法可以以牺牲一些歧义而保证高质量的结构。

发展到当下，尽管大多数动态网络可视化方法可以被很清晰的分为动画方法和时间线法，但是也有部分学者试图将二者结合起来处理动态网络的可视化问题，特别是，通过查阅相关文献可知，公开发表的文献也集中在近几年。交互技术与可视分析密不可分，所有的交互技术，只有与可视化界面相结合才有意义。在对细节信息进行交互式可视分析的具体技术上，也存在一些有代表性的研究，这类研究多数基于变形技术而开展，结合一些研究者的综述可知，目前在可视化领域常用的交互技术可以概括为如下几类：鱼眼视图，焦点+上下文，整体+详细，平移和缩放，多视图关联协调技术等，下面选择几种典型方法进行详细论述。

2.4 基于鱼眼视图的交互技术

鱼眼视图源于鱼眼透镜，截止到目前，鱼眼视图被广泛应用于可视化和可视分析的研究和实现中，特别是在信息可视化领域，鱼眼视图的基本原理是将整个区域内的元素向边界方向进行延伸，延伸程度从中心到边界依次减小，其原理如下图2所示[10]。

图2 鱼眼视图

如图2所示，在鱼眼视图中，中心区域被放大而边缘区域被压缩，从而实现了对中心区域信息的强化，本文选用圆形鱼眼视图来进行基于鱼眼视图的交互技术的说明，在实际操作中，可以根据具体要求，自行定义鱼眼视图的形状。

在广义鱼眼视图的基础上，焦点+上下文技术应运而生，它将用户关注的焦点对象 (Focus) 与整体上下文环境 (Content) 同时显示在一个视图内，通过兴趣度函数对视图中的对象进行选择性变形，而将周围环境上下文的对象逐渐缩小，针对F+C技术，目前已经开展了大量的研究[11]。

2.5 多视图关联协调交互技术

随着数据量的增加，及用户对多个属性的同时关注，研究者提出了多视图关联协调交互技术，也即多侧面关联技术，其基本思想是建立针对多个信息不同侧面的视图，在交互过程中对多侧面视图中的可视化对象进行动态关联，从而实现探索其内在关系的目的。如下图3所示，将多视图关联交互技术进行图像展示，该视图来源于Zhao等人的可视分析工具 PivotSlice[12]。

图3 PivotSlice主界面

如上图3所示，界面被分成多个部分，其中b部分是分析过程的历史追踪，d部分展示了多个侧面的视图，用户与任意一个视图中的节点交互时，可动态链接到其他视图中的节点集合。多侧面关联技术强调从多个角度来分析问题，并且重在建立多个分析角度之间的内在关联关系，这也为突破单一视角来分析动态网络数据提供了相应的可视分析技术的支持。

3 可视演化分析

3.1 关联性分析

空间信息网络拓扑演化和空间信息网络动态可视化本来是针对空间信息网络的两个研究方向，而之所以萌生了基于可视化技术研究其拓扑演化规律的想法，是因为其二者之间存在以下关联。

一是研究思路的相似性。不论是是进行拓扑演化规律的分析，还是进行网络动态可视化的研究，首要条件是将组成空间信息网络的实体装备抽象成节点，将实体之间的相互关系(数据/信息交换)抽象成连边。在此基础上，一方面网络拓扑演化侧重于对网络通过各种简化和约束，建立各自的网络模型，分析网络的聚类性质、度分布性质等统计特征，探索实际系统的结构特征。另一方面则侧重于根据网络结构特性或动力学特征，通过演化模型以揭示网络本质的动力学机制，找到其内在的基本规律，从而最终实现对实际系统更好的预测与控制。而网络可视化侧重于通过形式化、形象化的方式将网络不同时刻的拓扑结构展示出来，进行辅助分析。

二是研究主线的一致性。不论是是进行拓扑演化规律的分析，还是进行网络动态可视化的研究，都是基于空间信息网络的动态特征，以时间为发展主线，通过对比下一时刻与上一时刻的不同，而找寻空间信息网络的发展规律。

3.2 优劣性分析

对比于传统网络拓扑演化方法，我们认为基于动态可视化技术进行空间信息网络拓扑演化研究具有以下优点。

一是增强了演化结果的可理解性。通过与传统演化方法进行对比分析，可以得知传统的演化结果大多都是通过仿真进行验证，最后给出结果分析，对于没有先验知识和背景知识的用户来说，准确理解起来是十分困难的。而人类大部分的数据信息是通过视觉获取的，可视化的演化成果和结果一方面可以给用户直接的视觉刺激，产生深刻的印象，另一方面它也易于用户去理解和掌握，因此，基于动态可视化的空间信息网络拓扑演化能够增强用户的演化结果的可理解性。

二是扩展了演化方法的适用性。通过与传统演化方法进行对比分析，可以得知传统的演化都是结合具体演化对象的特征而展开，不同网络突出的特征不同，因而演化方法和模型的适用性就很局限，同一种方法针对不同对象其效果可能相差较大，而且能否很好的进行移植也是需要验证和加以分析的。而可视演化方法其形式多样，确定了输入以后，其输出就可以根据输入进行形象化、形式化的展示，从而，也更有利于可视演化方法在不同领域之间的移植和推广。

4 结 语

空间信息网络拓扑演化和动态可视化是针对空间信息网络而开展的研究热点，旨在挖掘空间信息网络的发展规律和分析其拓扑特征，从而为空间信息网络的建设和管理提供辅助支撑。通过分析空间信息网络拓扑演化和动态可视化的相似性和一致性，本文探索了一种基于动态可视化研究空间信息网络拓扑演化的思路，提出一种可视演化方法，旨在借助可视化的形式化、形象化、易理解的特点填补传统演化方法单一的不足，同时，通过可视演化方法掌握空间信息网络的拓扑演化整个过程，更好的分析空间信息网络的拓扑结构。最终，实现对空间信息网络的高效建设和有效管理。

本文重点从思路上提出这种方法，在下一步研究中，将依据可视演化方法的关键技术，也即布局—可视化—交互进行基于动态可视化的空间信息网络拓扑演化具体实现。在此基础上，设计和实现一个空间信息网络动态可视演化系统，实现对空间信息网络拓扑可视演化从理论到工程的应用。