动态拓扑图的卫星网络可视化方法

动态拓扑图的卫星网络可视化方法*

胡华全1，2，吴玲达1，2，杨 超2，宋汉辰1

【摘 要】摘 要:针对高度动态变化的卫星网络，提出一种基于动态拓扑图的可视化方法。动态拓扑图可视化的难点在于如何保持动态可视化过程中的稳定性，从而使用户容易地感知到网络中所发生的拓扑变化。根据卫星网络的动态变化特点，构建连续的动态拓扑图模型;设计一种保持布局稳定性的策略，并基于力引导思想提出一种动态拓扑图布局算法;以Iridium系统为典型实例，验证本文的可视化方法的合理性和可行性。实验表明，该方法能够以清晰的可视化图像支持用户对卫星网络动态拓扑的感知和理解。 【期刊名称】国防科技大学学报 【年(卷),期】2014(000)004 【总页数】6

【关键词】关键词:卫星网络;动态网络;网络可视化;动态拓扑图

卫星网络具有高度持续变化的拓扑结构，是一种典型的动态网络［1-2］。通常的卫星网络可视化重点是模拟真实场景，展示卫星的轨道运动，以及数据包的路由状态等［3］。STK软件是解决此类需求的著名工具包，但是缺乏针对抽象网络信息的可视化研究，且没有关注动态网络拓扑的演化特性。

即使对于数据量小、结构较单纯的网络，较差的网络布局也会降低可视化结果的可读性，从而增加用户理解网络结构的困难程度［4］。不同于静态网络可视化，动态特征给拓扑可视化带来了挑战，因为数据的不断变化会给原来的可视化效果带来不可估计的影响［5-6］。从技术上而言，不仅要在美学标准的指导下实现清晰的网络布局［7］，而且要保持网络布局的动态稳定性，从而维持用

户意象图(Mental map)［8］。

本文作者在之前的研究中对动态网络可视化技术的研究现状进行了综述［9］。其中，动态网络数据最典型的描述方法是基于时间索引的图序列［9-10］，序列中的帧表示瞬时网络快照。图序列的可视化结果一般是动画或者并列小图(Small multiples)。文献［10］对这两种方式进行比较，结论是:在保持意象图的能力上两者差别不大;在信息描述方面，动画方式更加准确。然而，图序列需要通过插值才能转换为动画，而这种转换过程缺乏流畅性。此外，提取图序列的过程中有可能丢失部分动态信息。

卫星网络可视化可分为两个层次:一是直观地模拟动态场景，基于数字地球或地图背景(记为V1、V2视图)，展示卫星的轨道运动和覆盖范围等;二是展示抽象信息的时变特征，例如:拓扑图随时间的演化、节点对间的路径变化、网络中元素对整体的影响等。本文试图以抽象的卫星网络拓扑为研究对象，构建动态拓扑可视化视图(记为V3视图)，专注于抽象信息的可视化展示。V3视图被定位为对V1、V2视图的重要补充。在信息展示上，三个视图相互关联，同时又各有侧重点。

1 卫星网络动态拓扑图模型

1.1 动态拓扑图基本模型

卫星网络具有周期性、规律性、可预测性等特点，将网络中的卫星节点抽象为图节点，将网络中的信息传输链路抽象为图边，从而建立起基于图论的动态拓扑图模型。

定义1 卫星网络动态拓扑图G(t)定义为:

其中，V(t)表示有限的网络节点集;E(t)⊆V(t)×V(t)表示有限的网络边集(不考虑

自环和平行边);W(t)={wij(t)}表示每条边定义在周期上的状态函数，本文中表示连通状态;T表示卫星网络的运转周期。

在任意时刻tk∈［0，T］，动态拓扑图的快照表示为:

其中，若网络快照中两节点相邻，则边的状态wij(tk)=1，否则 wij(tk)=0。 1.2 时变特征与拓扑更新

根据卫星网络中数据传输的路由策略，分析拓扑建立和断开的条件，可以计算出网络拓扑发生变化的时刻点。

定义2 在tk∈［0，T］时刻，en(tk)表示连接事件，其中n∈E(tk)。连接事件序列表示为Son={en(tk)|n∈Eon(tk)}，其中Eon(tk)表示新增边的集合，Eon(tk)⊆E(tk)。

定义3 在 tk∈［0，T］时刻表示断开事件，其中m∈E(tk)。断开事件序列表示为Soff中Eoff(tk)表示删除边的集合，Eoff(tk)⊆E(tk)。

定义4 任意时刻tk的总事件序列表示为S={Son∪Soff|Eon(tk)∩Eoff(tk)=∅}。 本文采用基于事件驱动的拓扑更新方法，每个发生拓扑变化的时刻点都将触发一个动态更新事件，动态变化包括节点或边的增删操作，每个动态更新事件都将驱动动态拓扑图的更新操作，从而更新动态拓扑的可视化结果。

2 基于动态拓扑图的可视化方法

2.1 保持布局稳定性的策略

在网络布局过程中的任何时刻，动态拓扑图都试图在布局算法的作用下趋向于全局的能量平衡状态，也是最符合美学标准的状态，如图1(a)所示。但是，在事件序列S的驱动下，网络拓扑将被更新，因此已经形成的平衡状态A将被破坏，在布局算法的作用下，刷新为新的平衡状态B。在两个平衡状态的转换过

程中，若有大量的节点产生剧烈运动，则用户很难将前一状态作为参考，而从后一状态中理解到网络的演化过程，如图1(b)所示。因此，动态稳定性模型的核心任务就是通过对布局算法进行修正或改进，使得网络布局既满足美学标准的要求，同时保持用户感知网络的意象图，使得用户能够从平衡状态的平滑过渡中，感知到网络拓扑所产生的演化，如图1(c)所示。

图序列布局模式要求节点位移不能太远，但是动态拓扑图模式下，节点可以相对平滑地移动更远的距离，而不会破坏稳定性，因为动画本身缓解了用户追踪节点移动的难度。因此，本文的稳定性模型不考虑对节点位置加以约束，而考虑对边的断开和连接过程进行约束，采用淡出式断开，淡入式连接的策略。 布局算法没有修正的情况下，每次拓扑更新事件都将促使网络布局产生剧烈震荡，其本质原因是网络中相互作用力的剧烈变化。为了减缓这种震荡，实现拓扑的平滑转换，本节提出一种称为“先淘汰再增量”的视觉处理方案，步骤如下:

(a)对初始图G进行布局，得到布局Lold，如图2(a)所示。

(b)淡出式的断开。在断开事件的驱动下，以淡出方式淘汰需要删除的边e14，得到剩余子图G'。随着边的淡出，布局也平滑地演变，如图2(b)所示。 (c)淡入式的连接。在连接事件en(tk)的驱动下，以剩余子图G'的布局结果为基础，增加连接边e13，更新形成图Gnew。随着边e13的淡入，Gnew的布局也平滑的演变，如图2(c)所示。

(d)形成最终布局Lnew，如图2(d)所示。 2.2 动态拓扑图布局算法

Fruchterman-Reingold(FR)算法［11-12］具有两个特点:一是改进了经典的

弹簧嵌入模型，引入粒子物理理论，通过模拟原子间的力场来计算节点位置;二是引入“温度”概念来影响节点的位移，温度越低，节点移动的步长越小。随着布局质量的提高，温度函数cool(t)将控制着温度以逆线性方式从初始值逐渐衰减到零。但是，该算法基于固定的力施加模式来计算引力和斥力，不考虑网络拓扑演变和外力对布局计算的干扰，因此无法适用于动态网络的布局问题。 本文对FR算法进行动态化改进，使其适应动态拓扑图的布局。只考虑边的断开或连接，暂不考虑节点的删除或增加。FR算法中，边仅对引力造成影响，不会影响斥力。根据保持动态稳定性的策略，在淡出式断开的过程中，为断开的边设计淡出函数;在淡入式连接的过程中，为新增的边设计淡入函数。

根据FR算法中力的定义，边没有断开时，两个节点之间的距离为d，引力为d2/k，设迭代次数为M，则最后一次迭代时引力应该为0。因此，淡出函数定义为:

其中，i表示迭代索引，1≤i≤M，x≡d。

边没有连接时，两个节点之间的引力为0，设迭代次数为M，则最后一次迭代时引力应该为x2/k。因此，淡入函数定义为:

其中，x表示两节点之间的距离，i表示迭代索引，1≤i≤M。 动态FR算法的设计步骤如下:

(1)算法初始化:绘图的画布面积为area=W·L，其中，W和L分别表示画布的宽度和长度;参数

(2)力函数定义:动态拓扑图中邻居节点之间的引力函数为fa(x)=x2/k;所有节点对之间的斥力函数为fr(x)=k2/x;淡出函数为fout(x)，淡入函数为fin(x)。 (3)迭代更新，循环计算下面的第(4)～(7)步，共循环迭代M次。

(4)计算斥力。为每个节点分配两个向量:保存节点位置的向量pos和保持位移的向量disp。以节点v为例，遍历节点集的所有节点u∈V，u≠v，计算节点 v的位移中，δ表示两点位置之差。

(5)计算引力。遍历边集e∈E，每条边均为有序的节点对(v，u)，计算引力对节点位移的影响:

其中，δ表示两端点的位置之差。断开事件触发布局计算时，根据公式(3)可得接事件触发布局计算时，根据公式(4)可得

(6)限制节点的最大移动距离，阻止其布局到绘图画布之外。遍历节点，计算: (7)根据函数t:=cool(t)，降低动态拓扑图的布局温度，使所有节点逐渐收敛到最佳布局位置。

3 实验结果与讨论

Iridium系统是最成熟的支持星间链路的卫星网络，本文将其作为卫星网络的典型实例，验证可视化算法的有效性。系统的空间段包括66颗低轨卫星，分布在6个圆形轨道平面上(每个轨道平面11颗卫星)。系统轨道周期约为6000s。将Iridium系统抽象为包括66个节点和若干条边的动态拓扑图(边的建立遵循星间链路建立规则)。 3.1 可视化效果

(1)第一个平衡状态的布局

从启动网络可视化布局到获得第一个平衡状态，动态布局过程的快照如图3所示。图3(a)表示节点的初始位置;图3(b)表示斥力使节点快速散开;图3(c)和图3(d)表示引力和斥力共同作用，使节点逐渐趋向于平衡位置;图3(e)表示所有节点布局到最终的平衡位置;图3(f)表示用户对布局结果的旋转、缩放、平移等交

互操作。

在布局过程中，共迭代计算413次，每100次迭代耗时约1s。图4描述了每次迭代所对应的网络布局温度值，其中图4(a)表示全局趋势，图4(b)表示局部细节。图中点A～E分别表示对应于图3中网络快照(a)～(e)的图像采集点。从图4(a)可见:在动态可视化过程启动的瞬间，网络布局温度最高;从点A到点B实现了快速收敛(约15次迭代);点B到E的动态过程表示布局的微调，因为单个节点的温度(位移步长)逐渐趋向于零，因此整体布局温度也逐渐趋向于零。 (2)断开事件驱动的布局

断开事件将打破现有的平衡状态，并形成新的平衡状态，如图5所示。图5(a)表示断开事件触发布局更新的瞬间，网络还处于上一个平衡状态。图5(b)和图5(c)分别表示随着需要淘汰的四条边的淡出，网络布局的平滑演变。图5(d)表示最终形成的新平衡状态。从布局过程可见，在稳定性策略的指导下，网络布局没有产生突变，而是平滑地转换到新的平衡状态，保持了用户对网络拓扑中所发生变化的感知和理解。

在断开事件驱动网络布局的过程中，网络布局温度的变化情况如图6所示。图中点A～D分别表示对应于图3中网络快照(a)～(d)的图像采集点。从图6中可见，断开事件产生的瞬间，温度伴随着突变并快速收敛。 (3)连接事件驱动的布局

连接事件同样会破坏现有的平衡状态，并建立新平衡状态，如图7所示。图7(a)表示连接事件触发布局更新的瞬间，网络还处于上一个平衡状态。图7(b)和图7(c)分别表示随着增加的五条边的淡入，网络布局的平滑演变。图7(d)表示最终形成的新平衡状态。连接事件的更新同样是平滑地转换到新的平衡状态，

保持了用户对网络拓扑所发生的变化的感知和理解。

连接事件驱动下的网络布局温度变化情况如图8表示。从整体趋势上看，图8与图6具有相似性:都具有温度的突变点(B点)，并且事件产生后，均能快速收敛到平衡状态。与图6不同的是，此处新增了5条边，拓扑事件所涉及的节点数量多于更多，因此突变点处的温度更高。

此外，在断开事件和连接事件同时出现的情况下，可视化布局将首先处理断开事件，然后处理连接事件，以避免出现动态的视觉杂乱现象。综上所述，实验结果证明本文算法实现美学布局的同时保持了动态稳定性，且这种平衡没有以布局质量为代价。 3.2 交互设计

在可视化布局过程中，卫星网络的动态拓扑图以动画的方式呈现在视图中，节点位置不断地平滑更新。动态实时的特点避免了布局计算带来的交互延迟，用户可以随时参与到布局过程中，交互式地拖动节点到所期望的位置。基本的交互操作通过鼠标完成，用户拖动节点时，节点跟随鼠标移动;释放鼠标时，节点在力的作用下重新参与到动态布局过程中，用户可随时修正动态布局的过程。 3.3 应用分析

在应用对象方面，由于放松了地理位置对网络节点的约束，因此，本文的卫星网络可视化方法既能够应用于单层卫星网络，也可以应用于多层卫星网络;既支持对单个天基子网的分析，也能够同时分析多个天基子网。

在支持的可视化任务方面，本文的可视化结果既是为了信息的呈现，同时也支持用户从可视化结果中发现一些新的信息模式。表1列出了本文的可视化方法能够支撑用户完成的可视化分析任务［13］。

如表1所示，在用户的分析目标明确，能够(不能够)定位网络元素的位置时，可以从可视化结果中查找(定位)到需要的信息。

在用户的分析目标不明确，能够(不能够)定位网络元素的位置时，可视化结果能够辅助用户浏览(探索)到感兴趣的模式。

4 总结

本文提出了一种基于动态拓扑图的卫星网络可视化方法，目标是有效地绘制出稳定并且美观的卫星网络布局，用于支持后续的网络可视化分析以及辅助决策。和传统的卫星网络可视化方法相比，本文的创新之处在于重点关注卫星网络动态拓扑结构的可视化。该方法具有以下几个优点:动态拓扑图模型易于被用户接受和理解;采用动画式的网络可视化布局，比较直观;基于事件驱动的拓扑更新策略保证了不丢失拓扑变化信息;实现了保持动态稳定性的网络布局，同时符合基本的美学标准。

本质上，本文方法仅利用前一帧的布局和当前更新信息，属于在线可视化方法;而离散的图序列动画不仅利用前一帧的布局和当前更新信息，还利用后续网络帧的更新信息，属于离线方法。相对于离散图序列通过插值形成的不自然的伪动画描述，本文的连续动态拓扑动画的优势在于更加自然和流畅，并且避免了网络离散化为图序列过程中可能存在的信息丢失。

下一步的研究是将算法扩展到对空地一体的整个天基网络的可视化研究，增加网络节点的数量，进一步优化迭代计算的速度，同时设计更加美观的可视化界面，支持可视化推理与分析，更好地辅助用户决策。 参考文献(References)

［1］ 佘春东，王俊峰，刘立祥，等.Walker星座卫星网络拓扑结构动态性分

析［J］.通信学报，2006，27(8):45-51.SHE Chundong， WANG Junfeng， LIU Lixiang， et al.Topological dynamics analysis of Walker-constellation satellite networks［J］.Journal on Communications，2006，27(8):45-51.(in Chinese)

［2］ 张涛，张军，柳重堪.一种基于卫星节点的时变拓扑网络模型［J］.遥测遥控，2006，27(3):14-19.ZHANG Tao，ZHANG Jun，LIU Zhongkan.A satellite node based time-varying topological network model［J］.Journal of Telemetry，Racking，and Command，2006，27(3):14-19.(in Chinese)

［3］ 李娜娜，安志勇，崔广才.卫星网络可视化方案研究［J］.情报科学，2009，27(3):421-425.LI Nana， AN Zhiyong， CUI Guangcai. Research on the program of the satellite network visualization［J］.Information Science，2009，27(3):421-425.(in Chinese)

［4］ 孙扬，蒋远翔，赵翔，等.网络可视化研究综述［J］.计算机科学，2010，37(2):12-18.SUN Yang，JIANG Yuanxiang，ZHAO Xiang，et al.Survey on the research of network visualization［J］.Computer Science，2010，37(2):12-18.(in Chinese)

［5］ Casteigts A，Flocchini P，Quattrociocchi W，et al.Timevarying graphs and dynamic networks［C］//Proceedings of 10th International Conference on Ad-hoc，Mobile，and Wireless Networks，Paderborn，Germany，2011，6811:346-359.

［6］ 陈为，沈则潜，陶煜波，等.数据可视化［M］.北京:电子工业出版社，

2013，353-381.CHEN Wei， SHEN Zeqian， TAO Yubo， et al. Data visualization［M］.Beijing:Electronic Industry Press，2013:353-381.(in Chinese)

［7］ Huang WD，Peter E，Hong SH，et al.Improving multiple aesthetics produces better graph drawings［J］.Journal of Visual Languages and Computing，2013，24(4):262-272.

［8］ Xu KS，Mark K，Hero AO III.A regularized graph layout framework for dynamic network visualization［J］.Data Mining and Knowledge Discovery，2013，27(1):84-116.

［9］ 胡华全，吴玲达，杨超，等.时变网络可视化研究综述［J］.系统仿真学报，2013，25(9):1-7.HU Huaquan，WU Lingda，YANG Chao，el al.Survey on time-varying network visualization［J］. Journal of System Simulation，2013，25(9):1-7.(in Chinese)

［10］ Archambault D，Purchase H，Pinaud B.Animation，small multiples，and the effect of mental map preservation in dynamic graphs［J］.IEEE Transaction on Visualization and Computer Graphics，2011，17(4):539-552.

［11］ Tamassia R.Handbook of graph drawing and visualization［M］.London:Chapman and Hall/CRC，2013:385-387.

［12］ Li HB，Geng WJ，Wu Y，et al.An improved force-directed algorithm based on emergence for visualizing complex network［C］//Proceedings of 2013 Chinese Intelligent Automation Conference，

Springer Berlin Heidelberg，2013，305-315.

［13］ Brehmer M，Munzner T.A multi-level typology of abstract visualization tasks［J］.IEEE Transactions on Visualization and Computer Graphics，2013，19(12):2376-2385. doi:10.11887/j.cn.201404020 http://journal.nudt.edu.cn

基金项目:国家自然科学基金资助项目(61103081)

吴玲达(通信作者)，女，教授，博士，博士生导师，E-mail:wld@nudt.edu.cn