基于时空图的天基网络拓扑动态可视化

刘 军，高玉嵩，王 皓，姜向宏

(1. 东北大学计算机科学与工程学院，辽宁 沈阳110819；2.湖北工业大学工程技术学院，湖北 武汉430068)

1 引言

随着空间技术的不断突破，天基网络发挥的作用已经得到了各个国家的广泛认可。天基网络作为空天一体化网络的重要一环，在服务于国家战略的同时，也悄然的影响着民用和商业通信领域的建设与发展。可以说不论是从国家战略利益，还是航天测控、通信保障，均离不开天基网络的服务保障[1]。

针对静态网络的拓扑布局已经有了相当深入的研究，但静态布局很难保证天基网络拓扑结构的相对稳定性。针对天基网络的动态特性，需要找出既能突出拓扑结构的差异性又能保持视觉上的稳定的布局方法，本论文提出了一种基于动态特征的可视化布局方法。天基网络的动态特征就是天基网络的星间链路的变化情况，这种变化是在时间维度上的。为了将天基网络的差异性进行突出显示，提出一种分阶段的动画转换策略；同时为保证拓扑结构的稳定性提出一种动画布局稳定性策略，对天基网络的时空图模型进行展示。通过对动画转换的稳定状态和过渡状态分析，研究天基网络的分阶段动态可视化方法和动画布局稳定策略，实现天基网络的递进式动态可视化方法。

目前，研究者对动态网络可视化进行了一些研究。刘真等人[2]指出通过动态图模型解决动态网络展示问题的解决办法，结合可视化的目标和需求，探讨动态网络可视分析法在不同领域的应用。于少波等人[3]阐述了多层网络可视化和动态网络可视化的特点、发展现状和主要技术，并分析了当前存在的主要问题。Friedrich和EADES[4]开发了一款Marey的可视化工具，主要采用线性插值法与分步转换法相结合的思想实现动画的过渡。Bach等人[5]构建了Graph Diaries的软件包，实现方法与Friedrich的方法类似，均采用了先消除旧元素后增加新元素的办法，不同的是Graph Diaries为突出拓扑变化情况采用对新元素的突出显示加以实现。Huang等人[6]提出了中间过度实现动画转化的方法，主要操作是调整新元素的位置到布局的中心，根据力导向布局算法对与新元素相连的旧元素进行同步移动。

现阶段的可视化研究仅限于对卫星的运动轨迹的展示，缺乏对逻辑拓扑结构及变化规律等抽象信息的研究。因此很难从天基网络中挖掘出需要的信息。而且天基网络的拓扑结构的动态变化展示过程还不够平稳、一些方法也存在迭代次数过多达到稳态缓慢的问题。

2 基于空间变化事件的时空图模型

2.1 空间变化事件概述

时空变化过程实质是一系列沿时间轴的天基网络拓扑结构的变化过程。时空图的描述包括节点、边和属性三个基本方面，因此，时空变化包括沿时间轴的节点变化、边变化和属性变化。事实上，后一时刻的节点、边、属性特征均与前一状态的相应值有关系。在不同的时刻，时空图的节点、边和属性特征可能全部变化、两项变化或单项变化。

2.2 基于空间变化事件构建天基网络时空图模型

空间变化事件是天基网络时空图模型演化过程中的关键事件，能通过空间变化事件展现天基网络的动态转换过程。天基网络的时空图序列如图1所示，G(ti)表示ti时刻的时空图模型的拓扑结构图[7]。在时空图的演化过程中网络的边随着时间的变化不断出现、消失。但相邻时刻时空图模型的拓扑结构可能是相同的，也可能是不同的[8]。文章所关注的是拓扑结构的差异性，因此需要将相邻的具有差异性的拓扑结构提取出来，剔除掉相邻的相同的拓扑结构。空间变化事件主要用于表述相邻时刻之间网络拓扑的差异性，其原理如图2所示。

图1 天基网络时空图序列

图2 空间变化事件构建示意图

空间变化事件的主要作用有：

1)将时空图中的数据进行简化处理，找出相邻的差异的拓扑结构；

2)对相邻时刻未发生拓扑变化的结构进行弱化处理，减少布局的工作量的同时对天基网络的拓扑变化情况进行突出显示。

空间变化事件仅记录增加或者删除的边，不记录保持不动的边[9]。

根据空间变化事件构建的方法，在天基网络时空图模型中，两个相邻的时刻G(ti-1)=(V(ti-1)，E(ti-1))和G(ti)=(V(ti)，E(ti))的空间变化事件记为D(ti)，定义为

D(ti)=ED(ti)=G(ti)-G(ti-1)

(1)

其中，ED(ti)为ti时刻发生变化的边集，DS={D(ti)|i=1，…，n}是空间变事件序列，D(ti)中包括边的增加状态和减少状态，Eadd(ti)表示增加的边，Edis(ti)表示删除的边，则ED(ti)=Eadd(ti)+Edis(ti)。

3 基于时空图的动态可视化布局

仅仅利用针对静态网络的拓扑布局方法进行布局，相邻的两个时刻的布局效果可能会产生视觉上的跳变，从而很难保证天基网络拓扑结构的相对稳定性。针对天基网络的动态特性，需要找出既能突出拓扑结构的差异性又能保持视觉上的稳定的布局方法。本节提出了一种基于动态特征的可视化布局方法。天基网络的动态特征就是天基网络的星间链路的变化情况，这种变化是在时间维度上的。为了将天基网络的差异性进行突出显示，提出一种分阶段的动画转换策略；同时为保证拓扑结构的稳定性提出一种动画布局稳定性策略。

3.1 稳定状态和过渡状态分析

根据文章建立的时空图模型，将空间变化事件作为动画布局转换的关键帧，简化了天基网络的时空图模型的时间序列，同时将连续时间序列划分为间断的区间，在动画过程中体现为稳定和过渡两个状态：

1)稳定状态：天基网络拓扑结构更新完毕，网络的边不再发生变化，此时进行天基网络拓扑布局，并根据分阶段动画转换布局算法使布局趋于稳定。

2)过渡状态：G(ti)分阶段动画转换算法根据空间变化事件，更新天基网络拓扑结构的布局，此时主要完成天基网络拓扑结构的更新。

3.2 分阶段的动画转换策略

分阶段的动画转换策略通过分阶段的显示边的变化过程，实现网络差异化的突出显示。因此，分阶段动画转换的核心需要对边的增加和删除状态实现平稳过度，例如“淡入”增加边，“淡出”减少边，如图3所示。通过引入四叉树空间分解法[10]，节省了排斥力的计算量[11]。为避免造成长时间布局，通过引入淬火算法来加速整体的布局效率。淬火算法的基本思想是利用温度进行布局控制，温度为整体布局的控制函数，当温度降到低于0或者迭代次数为0时，布局结束。分阶段动画转换包括以下4个主要步骤：

第1步：上一时刻的平衡状态。为ti时刻的网络布局，通过动画转换布局法的作用下的网络节点受力达到平衡，得到上一时刻的布局G(ti-1)，如图3(a)所示；

第2步：删除边。受空间变化事件的影响，令Edis(ti)中的边逐渐消失，生成过渡图G′。通过将消失的边e23∈Edis(ti)做淡出处理，布局图完成平滑过渡，如图3(b)所示。FR算法是实现网络拓扑布局最常用的方法[12]。根据快速多层次FR算法[13]和引力公式，设当前温度值为t，利用温度对引力进行约束，直至温度降为0引力消失。因此，可以将淡出函数fdis(d)定义为

(2)

可见，由于温度的降低，节点间的引力减小至0，在布局图中边e23已经彻底消失。在布局过程中，节点2和节点3 的引力逐渐减弱，造成受力失衡，两节点受斥力的影响而相互远离。

图3 分阶段的动画转换模型

第3步：增加边。受空间变化事件的影响，Eadd(ti)中的边逐渐出现，生成新的过渡图G′，根据过渡实现G(ti-1)的更新。如图3(c)所示，由于边e24∈Eadd(ti)的出现，天基网络拓扑布局随之而变，进行平滑过渡。

第4步：形成新的平衡状态。布局图完成平滑过渡，生成下一时刻ti的布局图G(ti)，如图3(d)所示。可以将淡入函数fadd(d)定义为：

(3)

可见，由于温度的降低，节点间的引力逐步增加，在布局图中边e24已经“淡入”至图中。在布局过程中，节点2和节点4的引力逐渐增强，再次造成受力失衡，两节点受引力的影响而相互靠近。

因此，以空间变化事件为基础，通过将引力函数变为淡出函数为fdis(d)和淡入函数为fadd(d)实现动画布局的过渡，以实现布局过度的平滑稳定。

3.3 动画布局稳定性策略

动画布局稳定性策略的基本思想是在分阶段动画转换过程中约束时空图演化过程中的节点移动距离，以保证布局过程的稳定性。假设L(ti-1)为ti-1时刻拓扑布局G(ti-1)的位置信息，动画布局稳定性策略就是以L(ti-1)为基础，通过节点的稳定度确定各节点的移动范围，根据移动范围确定下一时刻ti的拓扑布局G(ti)中各个节点的位置信息L(ti)。动画布局稳定性策略具体步骤如下：

第1步，根据上一时刻拓扑布局的位置信息L(ti-1)，对此时刻的拓扑布局G(ti)中的所有边进行遍历，根据空间变化事件，对每个节点连接边的变化情况进行计算计算，得到节点稳定度ξ(v，ti)。ξ={ξ(vi，ti)|vi∈V(ti)}表示拓扑布局G(ti)的稳定度的集合。节点稳定度的计算方法如下

首先，根据空间变化事件D(ti)对各节点连接边的变化情况进行统计，边的变化相当于与节点相关的权值相应的改变。假设变化的边ejk∈ED(ti)对应的两个节点分别为vj与vk，下面对节点vj的权值变化Δwj情况进行计算

(4)

图4 动画布局稳定策略示意图

其次，wjk(ti)表示节点vj与vk在时间片G(ti)边的权重。根据节点的权值变化Δwj计算节点vj确定稳定度ξ(vj，ti)，计算公式如下

(5)

ξ(vj，ti)是归一化的数值，0≤ξ(vj，ti)≤1，max(Δwk)为空间变化事件中所有节点权重变化最大值。

第2步，依据节点稳定度ξ(vj，ti)，为每个节点vj∈V(ti)计算节点动态边界值。根据节点动态边界值对FR算法的节点位移进行约束，生成具有稳定性的天基网络动态拓扑布局。节点动态边界值的计算方法如下：

(6)

4 动态可视化布局结果仿真

美国的STK(Satellite Tool Kit)作为一款商用航天领域的可视化平台，是目前航天领域应用最为广泛的仿真和可视化工具，通过其强大的轨道计算功能可用于分析复杂的航空航天任务。

仿真选择中轨卫星和低轨卫星双层星座(MEO/LEO)[14]作为天基网络架构并建立通信链路[15]，LEO星座有6个轨道面，每个轨道有8颗卫星，MEO星座有2个轨道面，每个轨道面有4颗卫星。利用SQL sever 2008和STK卫星仿真软件实现天基网络拓扑演化过程的动态展示。

1)启动网络可视化布局

通过STK建模获取到星座模型和星间链路数据，选取任意时刻的数据建立时空图模型，对时空图模型进行拓扑提取，得到未平衡的初始布局。再根据动画布局稳定性策略计算节点动态边界值。以算得的节点动态边界值对快速多层次FR算法的节点位移进行约束，FR算法多次迭代后得到平衡的初始布局。

从开始初始布局到布局图中各个节点受力平衡，对初始布局过程进行分阶段显示如图5所示。在算法开始运行之前，所有节点均集中在图布局的中心，如图5(a)所示。在经过8次迭代后，布局图已经展开，在10-20次后变化已经趋于平稳，如图5(b)所示；此时由于节点与节点间相距较近，互相之间主要受斥力的影响发生位移，主要表现为从中心迅速向外扩张。随着节点的逐步散开，间距逐渐变大，节点间的引力开始发挥作用，由于节点的位移受引力与斥力的合力共同影响，随着布局逐渐完善节点的所受的合力逐渐减小，布局逐渐趋于平衡，如图5(c)和图5(d)所示。最终所有节点合力为零，布局结束，整体的变化过程十分平稳，达到初步稳定和最终平衡的迭代次数较小。

图5 初始布局过程进行分阶段显示

图6(a)～(d)展示了动画初始布局的全过程，20-40次时已经初步稳定，100次时可达到基本平衡。受迭代次数的影响，迭代次数越多布局效果越好高，体现了布局逐渐趋于完善的全部动态流程。

图6 初始布局移动距离变化曲线

2)分阶段的动画转换布局

根据空间变化事件的影响，将动画布局分为删除边和增加边两个阶段，当动画布局处于删除边阶段时，由于边的删除将会使节点受力失衡，造成节点位移，直到节点受力重新达到平衡。图7分别是删除边阶段动画转换布局动画转换布局的仿真结果，增加边阶段与之类似。可以看到随着迭代的进行，布局逐渐收敛，所有节点的位移量趋于平缓；布局经过一段时间后，整体布局自动进行微调，所有节点的位移量趋于稳定。最终所有节点的受力达到平衡。

图7 减少边阶段移动距离变化图

图中记录了删除变过程中节点移动距离的变化情况。在开始布局之前即图7(a)点，边未发生变化，整体动画布局处于平衡状态，所有节点的移动距离之和为零。当边逐渐消失时即图7(b)点，各个节点受力产生位移，此时受影响的节点较多，节点的位移量迅速发生变化；从图7(b)到(c)，布局逐渐收敛，所有节点的位移量趋于平缓；布局经过一段时间后，即从图7(c)到(d)，整体布局自动进行微调，所有节点的位移量趋于稳定。最终所有节点的受力达到平衡，布局结束。动画布局过程中没有出现剧烈波动，而是实现了整体动画的平稳转换，兼顾网络结构视图的动态稳定性的同时实现了网络拓扑变化情况的突出展示。

5 结束语

针对天基网络的动态特征提出了一种基于空间变化事件的时空图模型，再以此提出一种分阶段的动画转换策略；同时为保证拓扑结构的稳定性提出一种动画布局稳定性策略。从布局效果可以发现，通过动画布局使天基网络的空间动态特性得以展现，减弱了认知难度；通过空间变化事件驱动动画转换，突出了天基网络的拓扑结构变化情况，利用分阶段动画转换策略以及动画布局稳定策略保证了整体布局的稳定性。本论文对天基网络的研究仅考虑到了通信链路变化的情况，某个卫星发生损坏等突发情况是下一阶段研究的目标。