基于时空图的天基网络拓扑动态可视化_刘军.pdf

基金项目:国家自然科学基金(61671141)收稿日期:20210331修回日期:20210521第 40 卷第 2 期计算机仿真2023 年 2 月文章编号:10069348(2023)02002805基于时空图的天基网络拓扑动态可视化刘军1，高玉嵩1，王皓1，姜向宏2(1 东北大学计算机科学与工程学院，辽宁 沈阳 110819;2湖北工业大学工程技术学院，湖北 武汉 430068)摘要:如何对天基网络的动态拓扑结构进行可视化展示，是当前天基网络研究中的热点问题。以时空图概念建立基于空间变化的连接关系模型，并利用空间变化事件作为时空图转换的关键节点，建立起针对天基网络的动态演化过程的时空变化模型。通过分析天基网络的稳定状态和过渡状态，提出分阶段动画转换策略和动画布局稳定性策略。并对天基信息网拓扑模型进行布局分析，精确地描述拓扑的动态性，验证了可视化布局方法适用于实现天基网络拓扑结构的动态、稳定的展示。关键词:时空图;天基网络;动态布局;动态可视化中图分类号:TP393文献标识码:BTopological Modeling and Visualization of SpaceBasedNetwork Based on SpaceTime GraphLIU Jun1，GAO Yusong1，WANG Hao1，JIANG Xianghong2(1 School of Computer Science and Engineering，Northeastern University，Shenyang Liaoning 110819，China;2 College of Engineering and Technology，Hubei university of Technology，Wuhan Hubei 430068，China)ABSTACT:How to visually display the dynamic topology of spacebased networks has been a hot issue in the re-search of spacebased networks Based on the concept of spacetime graphs，we established a connection modelbased on spatial changes in the paper is established Using spatial change events as the key nodes of spacetimegraph transformation，we established a space time variation model for the dynamic evolution of space basednetworks By analyzing the stable state and transition state of the spacebased network，a staged animation conversionstrategy and animation layout stability strategy wereare proposed The layout analysis of the spacebased informationnetwork topology model accurately describes the dynamics of the topology And it verifies that the visual layout methodis suitable for realizing the dynamic and stable display of the spacebased network topologyKEYWODS:Space-time graph;Spacebased networks;Dynamic layout;Dynamic visualization1引言随着空间技术的不断突破，天基网络发挥的作用已经得到了各个国家的广泛认可。天基网络作为空天一体化网络的重要一环，在服务于国家战略的同时，也悄然的影响着民用和商业通信领域的建设与发展。可以说不论是从国家战略利益，还是航天测控、通信保障，均离不开天基网络的服务保障1。针对静态网络的拓扑布局已经有了相当深入的研究，但静态布局很难保证天基网络拓扑结构的相对稳定性。针对天基网络的动态特性，需要找出既能突出拓扑结构的差异性又能保持视觉上的稳定的布局方法，本论文提出了一种基于动态特征的可视化布局方法。天基网络的动态特征就是天基网络的星间链路的变化情况，这种变化是在时间维度上的。为了将天基网络的差异性进行突出显示，提出一种分阶段的动画转换策略;同时为保证拓扑结构的稳定性提出一种动画布局稳定性策略，对天基网络的时空图模型进行展示。通过对动画转换的稳定状态和过渡状态分析，研究天基网络的分阶段动态可视化方法和动画布局稳定策略，实现天基网络的递进式动态可视化方法。目前，研究者对动态网络可视化进行了一些研究。刘真等人2 指出通过动态图模型解决动态网络展示问题的解决办法，结合可视化的目标和需求，探讨动态网络可视分析法82在不同领域的应用。于少波等人3 阐述了多层网络可视化和动态网络可视化的特点、发展现状和主要技术，并分析了当前存在的主要问题。Friedrich 和 EADES4 开发了一款Marey 的可视化工具，主要采用线性插值法与分步转换法相结合的思想实现动画的过渡。Bach 等人5 构建了 Graph Di-aries 的软件包，实现方法与 Friedrich 的方法类似，均采用了先消除旧元素后增加新元素的办法，不同的是 Graph Diaries为突出拓扑变化情况采用对新元素的突出显示加以实现。Huang 等人6 提出了中间过度实现动画转化的方法，主要操作是调整新元素的位置到布局的中心，根据力导向布局算法对与新元素相连的旧元素进行同步移动。现阶段的可视化研究仅限于对卫星的运动轨迹的展示，缺乏对逻辑拓扑结构及变化规律等抽象信息的研究。因此很难从天基网络中挖掘出需要的信息。而且天基网络的拓扑结构的动态变化展示过程还不够平稳、一些方法也存在迭代次数过多达到稳态缓慢的问题。2基于空间变化事件的时空图模型2.1空间变化事件概述时空变化过程实质是一系列沿时间轴的天基网络拓扑结构的变化过程。时空图的描述包括节点、边和属性三个基本方面，因此，时空变化包括沿时间轴的节点变化、边变化和属性变化。事实上，后一时刻的节点、边、属性特征均与前一状态的相应值有关系。在不同的时刻，时空图的节点、边和属性特征可能全部变化、两项变化或单项变化。2.2基于空间变化事件构建天基网络时空图模型空间变化事件是天基网络时空图模型演化过程中的关键事件，能通过空间变化事件展现天基网络的动态转换过程。天基网络的时空图序列如图 1 所示，G(ti)表示 ti时刻的时空图模型的拓扑结构图7。在时空图的演化过程中网络的边随着时间的变化不断出现、消失。但相邻时刻时空图模型的拓扑结构可能是相同的，也可能是不同的8。文章所关注的是拓扑结构的差异性，因此需要将相邻的具有差异性的拓扑结构提取出来，剔除掉相邻的相同的拓扑结构。空间变化事件主要用于表述相邻时刻之间网络拓扑的差异性，其原理如图 2 所示。图 1天基网络时空图序列空间变化事件的主要作用有:图 2空间变化事件构建示意图1)将时空图中的数据进行简化处理，找出相邻的差异的拓扑结构;2)对相邻时刻未发生拓扑变化的结构进行弱化处理，减少布局的工作量的同时对天基网络的拓扑变化情况进行突出显示。空间变化事件仅记录增加或者删除的边，不记录保持不动的边9。根据空间变化事件构建的方法，在天基网络时空图模型中，两个相邻的时刻 G(ti1)=(V(ti1)，E(ti1)和 G(ti)=(V(ti)，E(ti)的空间变化事件记为 D(ti)，定义为D(ti)=ED(ti)=G(ti)G(ti1)(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)分阶段动画转换算法根据空间变化事件，更新天基网络拓扑结构的布局，此时主要完成天基网92络拓扑结构的更新。3.2分阶段的动画转换策略分阶段的动画转换策略通过分阶段的显示边的变化过程，实现网络差异化的突出显示。因此，分阶段动画转换的核心需要对边的增加和删除状态实现平稳过度，例如“淡入”增加边，“淡出”减少边，如图 3 所示。通过引入四叉树空间分解法10，节省了排斥力的计算量11。为避免造成长时间布局，通过引入淬火算法来加速整体的布局效率。淬火算法的基本思想是利用温度进行布局控制，温度为整体布局的控制函数，当温度降到低于 0 或者迭代次数为 0 时，布局结束。分阶段动画转换包括以下 4 个主要步骤:第 1 步:上一时刻的平衡状态。为 ti时刻的网络布局，通过动画转换布局法的作用下的网络节点受力达到平衡，得到上一时刻的布局 G(ti1)，如图 3(a)所示;第 2 步:删除边。受空间变化事件的影响，令 Edis(ti)中的边逐渐消失，生成过渡图 G。通过将消失的边 e23Edis(ti)做淡出处理，布局图完成平滑过渡，如图 3(b)所示。F算法是实现网络拓扑布局最常用的方法12。根据快速多层次 F 算法13 和引力公式，设当前温度值为 t，利用温度对引力进行约束，直至温度降为 0 引力消失。因此，可以将淡出函数 fdis(d)定义为fdis(d)=d2kt(2)可见，由于温度的降低，节点间的引力减小至 0，在布局图中边 e23已经彻底消失。在布局过程中，节点 2 和节点 3 的引力逐渐减弱，造成受力失衡，两节点受斥力的影响而相互远离。图 3分阶段的动画转换模型第 3 步:增加边。受空间变化事件的影响，Eadd(ti)中的边逐渐出现，生成新的过渡图 G，根据过渡实现 G(ti1)的更新。如图 3(c)所示，由于边 e24Eadd(ti)的出现，天基网络拓扑布局随之而变，进行平滑过渡。第 4 步:形成新的平衡状态。布局图完成平滑过渡，生成下一时刻 ti的布局图 G(ti)，如图 3(d)所示。可以将淡入函数 fadd(d)定义为:fadd(d)=d2k(1 t)(3)可见，由于温度的降低，节点间的引力逐步增加，在布局图中边 e24已经“淡入”至图中。在布局过程中，节点 2 和节点 4 的引力逐渐增强，再次造成受力失衡，两节点受引力的影响而相互靠近。因此，以空间变化事件为基础，通过将引力函数变为淡出函数为 fdis(d)和淡入函数为 fadd(d)实现动画布局的过渡，以实现布局过度的平滑稳定。3.3动画布局稳定性策略