卫星网络拓扑时变性对网络性能影响分析

卫星网络拓扑时变性对网络性能影响 张涛柳重堪张军 ()北京航空航天大学电子学院 北京 100083 文 摘 卫星网络的拓扑时变性会影响网络的性能 ,导致现有的许多网络技术在卫星网络上不能有效地使用 。文 中从卫星网络特点出发 ,给出一个可以反映卫星网络时变拓扑特点的网络模型 。利用该模型具体地分析了拓扑时变性 对卫星网络性能的影响 ,并进行相应的仿真试验 ,指出造成这些影响的主要因素是卫星节点间的切换 ,而卫星网络的连 续状态主要影响节点间的传输时延大小 ,且变化缓慢 。 主题词 卫星通信网络 时变拓扑网络模型 网络性能 切换 前 言 新一代的卫星网络具有全球可见性和按需分配带宽的能力 ,可以承载语音 、数据 、视频以及宽带多媒 体等业务 ,是未来天空地一体化信息平台不可缺少的基本组成部分 。 () 由于卫星节点本身的特点 如节点的运动性,卫星通信网具有拓扑时变的特点 ,这使它与传统的以固定节点为基础的通信网络有着很大的区别 。目前 ,许多学者已经意识到这种拓扑时变性会直接影响网络 1 - 3 通信的各个方面 ,例如 :路由特性 、接入策略以及用户寻址等。文献 1 - 3 都指出卫星网络具有拓扑 2 3 ( ) 动态性 ,并且这种动态性会对网络的性能带来影响 ,需要使用虚拟节点、有限状态自动机 FSA等方法 将其静态化 。 目前 ,许多学者已经注意到时变网络的特殊性 ,并且从不同的角度对其进行了研究 ,文献 4 5分别 ( ) 以通信网络和交通网络为背景 ,指出由于网络的时变性将影响最短路径算法 如 Dijkstra 算法在网络中的 适用性 ,由此将影响以最短路径算法为基础的网络路由性能 。但他们的研究主要集中在理论分析上 ,使用 的时变网络与卫星时变网络也有所差别 。本文通过对卫星网络的拓扑时变特点进行分析 ,侧重研究拓扑 的时变性对网络路由性能的影响 ,这对进一步研究卫星时变拓扑网络的通信问题有着重要的参考价值 。 本文首先根据卫星节点的特点给出卫星时变拓扑网络的网络模型 ;其次利用该模型 ,将卫星网络分为 连续状态和切换状态 ,并分别从连续状态和切换状态分析拓扑时变性对网络性能的影响 ,给出仿真结果 , 最后给出相应的结论 。 1 网络模型 1 . 1 卫星时变拓扑网络模型定义 以卫星为节点的网络有如下特点 : ?网络各节点的位臵以及节点间的相对距离都是以时间为变量的 函数 ; ?节点的邻居状况遵循一定的规则 ; ?整个网络节点总数不会发生变化 ; ?节点间距比较大 ,且距离 变化也很大 ,不能忽略 ; ?网络各节点间的拓扑关系呈周期变化 。这里把具有这些特点的网络称为卫星时 变拓扑网络 。 ( 定义 1 :卫星时变拓扑网络是一个各边权值都是以时间为变量的周期函数的无向图 其中若两节点不 ) ( ( ) ) V }是有限节点集 ,表示网相邻 ,则其边的权值定义为 ?,其模型为 : G V , A , W t 。其中 , V = { V, V n 1 2 ( ) ( ) 络的节点 ; A 是有限边集 , A Α V ×V ; W t{ Wt } 表示每一边在区间 [ t, t] 上定义的函数 。这里 ,区间 ij 0 1 () ()基金项目 :国家 863 资助项目 2002AA717017,国家自然科学基金 10377005 收稿日期 :2004207213 收修改稿日期 :2004 - 09 - 07 ( ) [ t, t]为讨论网络 G 时所需要关注的时间区间 ,而 Wt 可以表示节点 i 与 j 间的距离 、代价 、邻居以及 0 1 ij 其他状态情况 ,它是一个以 T 为周期的函数 ,称 T 为卫星时变拓扑网络模型的周期 。1. 2 卫星时变拓扑网络模型中的邻居 ( ) ( ) 定义 2 : t时刻网络 G 中若两不相同节点 V 与 V间的边 i , k存在 ,且 Wt ??,则称节点 V 是节 0 k i ij k Γ( ) 点 V在 t时的邻居 。t时节点 V的全部邻居组成的集合称为节点 V在 t时的邻居集 ,记作 t,并 i 0 0 i i 0 i 0 Γ称周期 T 内节点 V的全部邻居组成的集合为 V的完全邻居集 ,记作 。 i i i Γ卫星时变拓扑网络节点的邻居以及邻居集是依赖于时间的 。若对于任何 t ?[ 0 , T ] 的节点 V?, m i ( ) 满足 Wt??,则称节点 V为节点 V的永久邻居 ,否则称为临时邻居 。其相应的集合分别称为永久邻 im m i ΓΓΓΓΓ居集和临时邻居集 ,记作 :L 和T,且 = L ?T。 i i i i i 在实际卫星网络中 ,邻居可根据一定的规则得到 ,这是由每个卫星通信网具体规定的 。例如 ,同一轨 道高度的卫星网可以规定相邻的 4 颗星为 4 个邻居节点 ,其中同一轨道前后两个距离最近的卫星节点为 永久邻居 ,左右两个距离最近的卫星节点为临时邻居 ;不同高度的移动卫星网可以规定高层卫星所覆盖的 所有低层卫星都为它的邻居 ,且都是临时邻居 。 1. 3 卫星时变拓扑网络模型中节点间的关系 ( ) 在周期 T 内 ,若节点 V 与 V间的边始终不存在 ,则称 V 与 V间处于断开关系 ,这时 Wt = ?;若 k i k i ik ( ) V 与 V间的边始终存在 ,则称 V 与 V间处于连接关系 ,这时 Wt 为一连续函数或者常数 ; 若 V 与 Vk i k i ik k i 间的边存在状态在某时刻 t会发生改变 ,则称 V 与 V间处于切换关系 。这里 ,时刻 t称为切换时间 ,记 0 k i 0 ( ) 为 T。一般 ,在周期 T 内 ,切换时间可以有多个 ,记为 T, T等 ,这时 Wt在 t ?[ 0 , T ]上为一个分段阶 s s0 s1 ik 跃函数 ,分段点为 T, T等 。 s0 s1 1. 4 卫星时变拓扑网络模型中的路 定义 3 :在 t时刻 ,若 G 中存在一个顶点和边的非空有限交错序列 0 U = VAV A V 0 1 1KK ) ( k , 满足 : ?A= V, i = 1 , i i - 1 , V i ?V, V,, V 为节点集 V 中的任意元素 ,且 V?V? ?V 0 1 k 0 1 K ?V是 V的邻居 , i = 1 ,, k i i - 1 则称 U 为 V- V 的一条路 ,记为 U。 0 K ok ) ( 若 U中的任一节点 V都是 V的永久邻居 i = 1 ,, k,则称 U为永久路 ,这时路 U将始终存在 ; ok i i - 1 ok ok 反之 ,称 U为临时路 。临时路具有生命期 ,且生命期以 T 为周期 ,对于时刻 t, t?[ 0 , T ] ,若 t时临时路 ok 1 2 1 U通过某节点切换而产生 ,又在 t时通过某节点切换而死亡 ,而称 t为 U的产生时间 , t为 U的死亡 ok 2 1 ok 2 ok 时间 , t- t为 U的生存时间 ,记作 TL , TL 可表示卫星时变拓扑网络中一条通信线路的稳定性和存在的 2 2 ok 时间 ,是时变网络特有的参数 。 ( ) ( k , t是指源节点 V为时刻 t时 ,到达节点 V的, t时刻 ,路 U各边的代价 Wti = 1 , i - 1 0 0 i - 1 0 ok i - 1 , i i - 1 ) ( ) 时间与各节点的代价之和称为路 U在 t时的代价 ,记为 Dt。其中节点的代价与网络负载 、节点自 ok 0 ok 0 k ( ) Σ ( ) ( ) 身特性等有关 ,可暂不考虑 ,则 DtWt。对于任一时刻 t 的 Dt U的代价函= 称为路 ok 0 i - 1 , i i - 1 ok ok i = 1 ( ) ( ) ( ) 数 。显然 Dt为一周期函数 ,周期为 T ,且对于永久路 , Dt 为连续函数 ; 对于临时路 , Dt 为一个 ok ok ok 分段的不连续函数 。 2 拓扑时变性对网络性能影响的分析及仿真 ( ) ( ) 在卫星时变拓扑网络 G 中 ,根据矩阵函数 W t中的各个元素函数 Wt 在时间区间 [ t, t] 内的连ij 0 1 续性 ,可将卫星时变拓扑网络 G 分为连续状态和切换状态两种不同的情况 ,连续状态指在时间区间 [ t, 0 ( ) ( ) t]内矩阵函数 W t中的各个元素函数 Wt 均连续 。这时 ,拓扑的时变性对网络的影响主要表现为对 1 ij ( ) ( ) 网络边的传输时延 W的影响 ;切换状态是指在时间区间 [ t, t] 内矩阵函数 W t 中有一对或多对元素 ij 0 1 ( ) ( ) ( 函数 Wt不连续 ,即存在一点 t ,在 t 时刻元素函数 Wt发生阶跃突变 ,由 ?变到 a ,或 a 变到 ?a 为 ij ij ) 节点间的时延 ,为一有限值。这时 ,拓扑的时变性对网络的影响主要表现为对网络中某些路的通断的影 () 响以及切换点附近网络局部性能的影响 如吞吐率 、拥塞 、丢包等。 2. 1 连续状态 卫星网络中的卫星节点在相应的轨道上不断地运动 ,节点间的距离也随时间的变化而变化 ,且变化是 连续的 。所以 ,若对于时间区间 [ t, t]网络 G 为连续状态 ,则该区间内各节点的邻居不发生变化 ,且网络 0 1 ( ) ( ) G 中矩阵函数 W t 中的元素函数 Wt 变化也是连续的 。 ij ( ) 命题 1 :对于时间区间 [ t, t] ,若卫星时变拓扑网络 G 为连续状态 ,则网络中各边的 Wt 将随时间 0 1 ij δ连续变化 ,且该变化很缓慢 ,对于某一可以接受的误差 ,存在一个最大的时间区间 t,使得在经过时间 max 间隔 t后 ,网络 G 的变化不影响网络的路由性能 。 max 证明 :所谓不影响网络的路由性能 ,是指对于卫星时变拓扑网络 G 连续状态中的任意时间 t ,经过一 段时间间隔 ?t 后 ,满足下面三个条件 : ??t ?t; ?在 t + ?t 时刻 , G 仍为连续状态 ; ?存在一个可以 max δ( ( ) ) δ接受的误差 。对于网络 G 中任意两点间的最短路径 U 的代价为 D ,满足关系| D t + ?t | - D t 。| ? ( ) 设网络 G 中各节点都处于同一轨道高度 h 。若路 U 由 N 条边组成 ,则 D t < N 〃w。其中 , w为 max max () ( ( ) ) ) ( 节点间的最大代价值 ,而| D t +D t N 〃?w= N 〃?S Πc , c 为光速。这?t | -这里为时延 | ? max max 里 , ?S 为 ?t 相邻节点间的最大距离变化值 。所以 ,上述命题可转化为经过时间间隔 ?t 后 ,若网络 G max δ 中任一边的距离变化值 ?S ?〃cΠN ,则可认为该变化不影响网络的路由性能 。 由于在 t 以及 t + ?t 时刻网络 G 都为连续状态 ,则由卫星运行的规律可知 ,此时网络 G 中边的距离 ( ) 为时间 t 的连续函数 ,所以 ?S 也是 ?t 的连续函数 。因此 ,对于连续函数 ?S ?t ,总可以找到一个最大 δδ 的 t,使得对于 ?t ?t满足 ?S ?〃cΠN ,且仅当 ?t = t时有 ?S ?〃cΠN 成立 。当然 ,这时的 t大max max max max δ小与星座 、轨道高度等因素有关 。若取 为 3ms 、N = 4 ,几种典型的星座的 t取值列于表 1 。 max 表 1 几种典型的卫星网络 t的取值 max 铱系统 全球星 Teledesic ICO ( )轨道高度 km 1375 778 1414 10390 ()轨道倾角 ? 84. 7 86 52 45 ( )ts 181 82 147 77 max 由表 1 可知 ,在网络连续状态时 ,若网络路由的平均跳数为 4 ,存在一个比较大的时间间隔 t,使得该路 max 的传输时延变化值不会超过 3ms ,此时 ,可认为间隔 t内网络拓扑没有改变 。在实际应用中 ,可以根据星 max () 座选取一个合适的间隔 如 60s,将连续状态时的卫星时变拓扑网络静态化 ,文献 1 - 3 中使用的方法正 是基于上述结论 。 这里使用“铱系统”的轨道数据 ,利用卫星轨道专用软件 STK 进行仿真 。 ?验证连续状态下网络 G 某边的传输时延变化情况 ,实验选用相邻轨道间相近纬度的两节点 ,在继续 时间区间内 ,计算其节点间的距离变化 ?l 。结果示于图 1 。 图 1 所取的数据为两卫星节点从南极区运行到北极区的连续状态区间 ,由图 1 看出 ,节点间的距离变 化在赤道附近最缓慢 ,每 100s 距离变化不超过 10km 。而在高纬度时变化最剧烈 ,每 100s 距离变化大约 ( ) 250km 。这与前面所给出的理论推导值 t值相符 。由实验看出 :虽然整个运行过程中 ,节点间的时延变max ((( ) ) ) 化不能忽略 约 8ms,但在一段较短的时间内 如 100s,节点间的时延变化很小 < 1ms,可以忽略 。 ?验证连续状态下卫星网中某条通信路的传输时延 变化情况 。实验假设北京与土耳其 lzmir 的两用户进行 通信 ,在连续时间区间内 ,计算其通信时延变化情况 ,结 果示于图 2 。 图 2 假设用户可通信的最小仰角为 10?。实验过程中没有发生链路切换 ,所得数据包括地面用户到卫星的 距离 。这 样 一 个 完 整 的 不 间 断 通 信 时 间 区 间 大 约 为 440s ,其中最短的传输时延大约为 28ms ,最大的传输时延 大约为 34ms ;在整个通信过程中 , 传输时延的变化值约 为 6ms ,这对于大多数业务来说是可以忍受的 。 上述的试验表明 ,连续状态下节点的运动对卫星时 1 连续状态下卫星节点间边的传输时延变化图 变拓扑网络 G 的影响是缓慢的 、不显著的 。一般它不影 响网络的路由性能 ,也不是影响网络性能的主要因素 。 2 . 2 切换状态 卫星网络中的卫星节点在运行过程中 ,不仅节点间 的距离会发生变化 ,而且某一节点相邻的节点也会发生 ( 变化 ,包括轨间节点运行过程中发生的位臵颠倒 如左边 ) 的节点在经过某一点后会变成右边节点、相向运行轨道 ( ) 间相邻节点的不断变化 如极轨道中的相向运行轨道、 () 层间相邻节点的变化 如中轨道与低轨道之间。这种变 化在网络 G 中可以用节点邻居的变化来表示 。此时 ,对 图 2 北京与 Jzmir 通信时延变化情况 ) (应的边的 W t 是一个阶跃函数 ,其突变点为节点间的 ij 切换时刻 T。s 对于卫星时变拓扑网络 G ,若在 T时刻发生节点切换 ,则该变化将影响网络的拓扑结构和网络的路 S 由性能 。网络中相关的节点需要重新计算路由 。假设时刻 t 为 T前某一时刻 ,且 t 时刻网络 G 中某节点s ( ) ( ) v、v的最短路 U的代价 Dt存在 ,设为 D ,若在 T时 ,路 U上某段边 v, v发生切换 ,此时如果节点0 k ok ok S ok i j v到 v仍按原来的最短路 U走行 ,则代价为 ?。所以 ,节点 v、v的最短路发生了变化 ,需要重新计算 。 0 k ok 0 k 卫星时变拓扑网络 G 中 ,节点间的切换影响了网络路由性能 ,改变了节点 v与节点 v间的网络接连 0 k 情况 ,从而对网络性能带来多方面的的影响 ,包括丢包 、TCP 时延 、网络吞吐量 、非数据信息量 、面向连接的 通信性能等 。仿真和分析结果如下 。 本实验使用“铱系统”轨道数据作为卫星网轨道数据 , 利用 STK 和 OPNET 进行仿真 。实验中假设两不同运行方向的相邻轨 () 道间具有星间链路 这与实际的“铱系统”不同,且令两通信用户 分别居于两侧 ,同时 ,不考虑卫星与用户间的接入切换 ,重点研究 卫星切换后对网络通信的影响 ,相邻轨道的临时邻居为距离最近 的节点 ,且切换不需要时间 。 ?丢包 设在时刻 T网络 G 中两相邻节点 v、v发生切换 ,S i j 若路 U为网络 G 某一经过节点 v、v的路 。则 T时刻路 U的 ok i j S ok ( ) 代价函数 Dt发生突变 。这时路 U中有节点发生断路 ,原先 ok ok 的路将不再存在 。此时 ,若路 U是采用逐跳路由方式建立起来ok 图 3 节点切换时的丢包情况 的 ,则网络会有大量丢包现象发生 ,切换点附近处于路由瞬态 ,直 至动态路由收敛 ,新的路建立起来 ; 若路 U是 面 向 连 接 的 通 路 , 如 ATM 中 的 虚 通 路 或 MPLS 中 的 有 序 ok LSP ,则连接将中断 ,此时也会发生丢包情况 。 实验中考虑的切 换主要为不同运行方向的相邻轨道间卫星 节点的切换 ,且简单地认为距离最近为节点切换的条件 。对于 “铱系统”,大约 260s 左右就会出现一次切换 。如图 3 所示 ,丢 包主要集中在切换的时候 。 ?TCP 时延 假设网络的动态路由收敛的平均时间为 ?t , 则在时间区间 [ T, T+ ?t ] 内 ,节点 v、v及附近节点将处于S S i j 路由瞬态 ,存在局部拥塞以及路由环路等现象 ,这些都会大大增 加 TCP 时延 ; 同时 ,若在时刻 T时 ,节点 v、v断开后 ,节点 vS i j i 与另一个节点 v建立连接 ,此时的路 U将经过 v与 v,这时 , m ok i m 各节点中的路由表仍为切换前的路由表 。所以 , 此时的路 U ok 图 4节点切换时的 TCP 时延变化情况 有可能不是最优的路径 ,这也将使 TCP 时延变大 。时延变化示 于图 4 。 ?网络吞吐量 由于在切换状态时 , 网络大量丢包 , 这使 TCP 将减小发送窗口的大小 ,从而降低 TCP 的吞吐量 ,即网络吞 吐量将下降 。图 5 为 TCP 吞吐量的变化 。 ?非数据信息量 非数据信息量包括 OSPF 相关信息包 、 () 一些信令信息 如 MPLS等 。对于切换状态 ,由于发生了拓扑变 化 ,OSPE 相关信息包将大量增加 ,直到新的路由建立起来 。同 时 ,由于许多连接被中断 ,需要重新连接 ,这就产生大量的信令信息 。所以在切换状态 ,非数据信息量将增加 ,网络有效带宽下 降 。图 6 为信息包发送量的变化 。 由图 6 可知 ,在初始时 ,网络开始启动 ,这时有大量的 OSPF 信息包 ,当各节点的路由表建立起来之后 ,OSPF 信息包发送量 图 5节点切换时的 TCP 吞吐量变化情况 处于稳态 ,网络中 OSPF 信息包数量很少 , 在节点切换时 , 由于 部分节点需要重建路由表 ,这时又会产生大量的 OSPF 信息包 , 直至再次稳定 。实验中只考虑 OSPF 信息包 , 对于非数据信息 () 包 如信令等没有考虑 ,如果考虑这些信息包 ,结果会更明显 。 节点间切换的的影响还可涉及面向连接的通信性能 。若路 U是面向连接的通路 ,在 T时 ,路 U中有节点发生断路 。此ok S ok 时 ,通路上正在进行的业务将中断 ,正在申请的业务将被拒绝或 等待 ,这将大大降低 卫 星 时 变 拓 扑 网 络 G 面 向 连 接 的 通 信 质 量 ,同时也会使呼损率增加 。 因此 ,卫星时变拓扑网络 G 中节点间的切换将直接导致网 络结构的改变 ,影响网络局部节点的路由情况 ,从而对网络各方 () 面性能 如丢包 、吞吐率 、有效带宽等造成影响 。因此 ,节点间 的切换是影响卫星时变拓扑网络性能的主要因素 。 图 6节点切换时 OSPF 信息包发送情况 3 结论 卫星网络具有拓扑时变的特性 ,这种拓扑时变性会影响网 络的通信性能 ,从而导致现有的许多网络通信技术在卫星网上不能有效地使用 。本文从分析卫星网络特 点出发 ,给出一个可以反映卫星网络时变拓扑特点的网络模型 ,利用该模型具体地分析了拓扑时变性对卫 星网络性能的影响 ,并指出造成这些影响的主要因素是卫星节点间的切换 ,为今后进一步研究卫星时变网 络的通信问题有着重要的参考价值 。 本文将卫星时变拓扑网络分为连续状态和切换状态分别进行分析 ,通过理论分析和仿真验证 ,指出对 于连续状态 ,网络的时变性主要影响节点间的传输时延的大小 ,这种变化是缓慢的 ,在一定条件下 ,可以忽 略 ;而对于切换状态 ,网络的时变性将导致网络结构改变 ,并影响网络局部节点的路由情况 ,从而影响网络 [ 1 - 3 ] 各方面性能 。文中还指出将卫星时变拓扑网络静态化的可能性 ,并给出了静态化间隔的选取方法 。 参考文献 Sanctis M De ,Cianca E ,Ruggier M. IP2Based Routing Algorithms for Leo Satellite Networks in Near2Polar orbits. Aerospace Confer2 1 ence . 2003. P :3 - 1273,1280 Mauger R. QoS Guarantees for Multimedia Services on a TDMA - Based Satcllite Network . IEEE Communication Magazine . 1997 , 2 () 35 7:56,65 Chang S , Kim W. ESA - Based Link Assignment and Routing in Low Earth Orbitsatellite Networks. IEEE Transactions on Vchicular 3 () Technology. 1998 ,47 3:1037,1048 () Orda A ,Rom R. Distributed Shortest Path Protocols for Time2Dependent Networks Distributed Computing. 1996. 101:49,624 () 谭国真 ,高 文 . 时间依赖的网络中最小时间路径算法 . 计算机学报 ,2002 ,25 2:165,1725 Analysis of the Effect of Satellite Net work Topological Time2varying on the Perf ormance of Net work Zhang Tao Liu Zhongkan Zhang J un Abstract The toplolgical time2varying of satellite network is able to affect the performance of network ,so a lots of existing network techniques can not be applied to satellite network . In this paper , the characteristic of satellite network is analyzed ,and a network model which can express the characteristic of satellite network topological time2varying is proposed . Based on this model ,the effect of topological time2varying on the performance of satellite network is analyzed and some simulation are given. It is indicated that the main factor that affect the performance of satellite network is the switching of the satellite node ,and the continuous state of satellite network mainly affect the transport delay of the satel2 lite node which the change is small . Subjeet terms Satellite communication network Time2varying topological network model Performance of net2 work Switch 。 [ 作者介绍 ] 张 涛 1973 年生 ,2000 年北京航空航天大学电子信息工程学院博士研究生 ,研究方向为网络通信 、 移动通信 、卫星通信 。 柳重堪 1941 年生 ,教授 ,博士生导师 ,研究方向为信息传输与处理 ,信号与系统中的反问题 。 张 军 1965 年生 ,教授 ,博士生导师 ,北京航空航天大学电子信息工程学院副院长 、民航数据通信及 新航行系统科研基地主任 ,研究方向为通信网络 ,天空地一体化通信 ,遥控遥测 。