保证高可靠度和低传输开销的DTN拓扑控制

齐小刚，马久龙，刘立芳

(1. 西安电子科技大学 数学与统计学院，陕西 西安 710071；2. 西安电子科技大学 计算机学院，陕西 西安 710071)

时延容忍网络是为设计星际互联网而被研究和发展的，但目前已被扩展到其他领域，其特点是节点持续运动、拓扑时变、链路间歇连通[1-2]．尤其是以卫星网络作为骨干网的空间信息网络[3]，卫星节点周期性移动，网络还面临随机的节点和链路失效问题[4-5]．研究表明，适用于时延容忍网络的许多方案也适用于卫星网络[6-7]．在拓扑周期性变化的时延容忍网络中，基于时间片[8-9]的方案被广泛使用．该方案将网络的周期分割为离散的时间片，在每个时间片内拓扑可视为固定的，这使得一个时间片中只有当两个节点存在端到端路径时，数据才可以正常传输，忽略了时间片间的联系．文献[10]基于连通时序实现了深空网络的最大吞吐量，文献[11]在时间片的基础上提出了几种有效的拓扑控制方案，这些方法都假定了链路是完全可靠的．然而，空间网络节点间的链路在大多数情况下不是完全可靠的，且节点存储受限．

针对这些问题，笔者基于时空图模型，提出了新的适用于拓扑周期性变化的时延容忍网络的拓扑控制方案．它在保证网络连通的条件下，旨在寻找原时空图的一个稀疏子图，该稀疏子图能够满足任意节点对之间的路径的可靠性，同时降低了网络的传输开销．

图1 一个时延容忍网络的序列图示例

1 网络模型和相关定义

1.1 网络模型

假设由6个节点组成的时延容忍网络(Delay Tolerant Network，DTN)，如图1所示，节点分别为一个地面节点T1、两个低轨道卫星节点L1和L2、两个中轨道卫星M1和M2以及一个静止卫星G1．在t0至t1时间段内，节点之间的连接关系是固定的，即拓扑是固定不变的，称该时间段为一个时隙，即时隙1; 在t1时刻，部分节点之间的连接关系发生了变化，即拓扑出现了新的状态，t1～t2时间段内网络维持新的状态，则t1至t2的时间段为一个新的时隙，即时隙2; 在t2时刻，节点之间的连接关系再次发生变化．依此类推，网络在一个周期可能出现图1所示的几种拓扑状态．

按此方法将网络的系统周期T划分为n个时隙s1，s2，…，sn．用V表示网络的m个节点组成的集合，V= {v1，v2，…，vm}；Gs= (Vs，Es)，表示网络在时隙s时的拓扑．其中Vs和Es分别为网络在时隙s时的节点和链路集合，则网络在周期T的拓扑可表示为G= {Gs|s=s1，s2，…，sn}，它可以完整准确地描述网络的拓扑．但这样的离散序列很难进行拓扑控制和路由设计，因为在某些时隙内，网络并不连通，如图1中的时隙3、时隙4和时隙5，此时，L1和L2无法和T1通信．因此，直接将静态图序列用在时延容忍网络是不合适的．现考虑使用时空图来模拟网络的拓扑．将一系列的静态图转化为时空图，为此将任意两个时隙上的任意两个节点看成是不同的．

1.2 相关定义

定义1(时空图) 若时延容忍网络的拓扑表示为G={Gs|s=s1，s2，…，sn}，其中Gs= (Vs，Es)，为网络在时隙s时的拓扑，则G的时空图被定义为一个有向图GTS= (V，E，T)，其中:

(2)E是时空图的有向链路的集合，有向链路指的是时间链路和空间链路，分别定义如下．

图2 时空图的一个示例

(3)T是网络的系统周期．

通过定义时空图，任意两个节点间的通信可在时空图上表示．例如，若T1在t0时刻想发数据给M2，它可能采取的方式是先携带数据至t1时刻，在时隙2内，T1将数据转发给L1，在时隙3内L1转发数据给L2，在时隙4内L2转发数据给M1，最后在时隙5内，M1将数据转发给M2．

实际上网络节点间在传输数据时会有一定的传输开销．因此，给时空图的每一条链路赋予一个权值来代表传输开销．时间链路上的权值代表节点在一个时间段携带数据的开销．类似于卫星网络的时延容忍网络一般运行在极其复杂的空间环境中，卫星及星间链路在任意时刻都可能发生故障，甚至遭受人为攻击．笔者考虑卫星节点失效和链路故障的情形．赋予时空图中的有向链路e一个介于0到1之间的实数r(e)来表示该链路的可靠性，称r(e)为链路e的可靠度．对于时间链路，r(e)表征节点缓存和携带数据的成功率．当节点缓存不够时，数据会被丢失．例如在卫星网络中，轨内星间链路的可靠度比轨间星间链路的可靠度更高; 层间链路的可靠度比层内的星间链路可靠度低．此外，时间链路比空间链路的可靠度高．

定义2(赋权时空图) 称G=(V，E，c，r)为赋权时空图，其中V为时空图的节点集合;E为时空图的链路集合;c为定义在E上的正实值函数，即c:E→R+，称c为开销函数;r为定义在E上取值在[0，1]之间的函数，即r:E→ [0，1]，称r为可靠度函数．

定义5(路径的可靠度和最可靠路径) 在时空图G中，一个从节点u到节点v的路径P(u，v)的可靠度是指该路径上所有链路的可靠度的乘积．从u到v的最可靠路径是指从节点u到节点v的所有路径中可靠度最高的路径．

2 可靠拓扑控制问题

可靠拓扑控制问题可以被描述如下．给定一个连通的赋权时空图G=(V，E，c，r)，拓扑控制的目的是找到一个稀疏时空子图H(V′，E′，c，r)，使其满足:V′=V;H在一个周期T上是连通的;H中任意节点对之间的路径的可靠度最高;子图H的传输开销c(H)最小．

要保证网络任意节点对之间的路径的高可靠度和子图的低传输开销是极其困难的．为使问题简化，假定在每条链路上的传输开销是相等的，笔者提出两个有效的启发式算法解决了该问题．

3 相关算法

解决上面问题的思路是在构造的原始时空图G中寻找各个节点对之间可靠度较高的路径．可以将时空图G中所有节点对之间的最可靠路径添加到子图H．显然，生成的子图H能够满足网络的可靠需求．为此，首先将所有链路的可靠度值取负对数，然后使用Dijkstra算法．算法1显示了详细过程．

算法1 最可靠路径联合算法．

输入：原网络的序列图{Gs}．

输出：时空子图H．

算法2 最可靠路径的贪婪算法．

输入：原网络的序列图{Gs}．

输出：时空子图H．

算法1为了满足节点对之间数据传输的可靠性条件，以最简单的方式向子图中添加最可靠路径．尽管它能够满足可靠条件，但是添加了过多不必要的链路，不能大幅度降低网络的传输开销．算法2通过逐次加入最可靠路径，进一步降低了网络的传输开销，同时保证网络具有一定的可靠性．若用N表示问题的规模，由于时空图最多有n+1 层，所以节点个数为N(n+1)，边的个数最多为nN2．在时空图上运行N次Dijkstra算法，算法1的时间复杂度为N2O(nN+nlog(nN))=O(nN3+nN2log(nN))．同理，算法2的时间复杂度为N2O(nN3+nN2log(nN))=O(nN5+nN4log(nN))．

4 性能评估

拓扑控制的目的是为了构建一个满足任意节点对之间数据传输有可靠性保证的稀疏拓扑，并降低网络的传输开销．仿真采用两种度量来衡量提出算法的性能：一是稀疏时空子图H的传输开销与原时空图G的传输开销的比值，即传输开销比；二是时空子图H的平均可靠度．网络的链路开销越小，可靠度越高，表征拓扑控制算法越有效．

为了模拟真实时延容忍网络的拓扑，采用经典的随机图产生器来模拟产生网络的离散时隙拓扑集G= {Gs|s=s1，s2，…，sn}．设定任意两个节点间存在链路的概率为p，p的大小表明了网络链路的稀疏程度，称p为链路密度．仿真中随机产生具有10个节点的6个离散序列图，每条链路的可靠度值服从0.8到1.0的均匀分布．设定p的值在0.5到1之间变化，并假定每条链路的传输开销相等．仿真随机产生500组满足条件的序列图，并统计网络的平均性能．

图3(a)显示了网络的传输开销比随着链路密度的变化情况．从图3(a)中知，两种算法都能在网络连通时，保证端到端路径的高可靠度，并能有效地降低网络的传输开销，且链路密度越大，算法节省的传输开销就越多．另外，从网络链路的传输开销考虑，算法2比算法1更优，原因是算法1只是简单地向时空图中添加了最可靠路径，可能会导致添加一些不必要的链路．图3(b)显示了平均可靠度随着链路密度变化的情况．随着链路密度的增加，两种算法下的可靠度都有所提高．另外，算法1得到的平均可靠度略高，因为算法1添加了所有节点对之间的最可靠路径．

图3 网络传输开销比和平均可靠度随链路密度的变化曲线

为了获得时隙个数对传输开销比和平均可靠度的影响，固定链路密度p=0.8，保持其他仿真参数不变，统计网络具有不同时隙个数时的性能．图4(a)显示了传输开销比随时隙数目变化的关系．两种算法的传输开销比都随着时隙数量的增大而下降，这表明时隙数目越多，越能体现两种算法在传输开销方面的有效性，且算法2体现的更加明显．图4(b)显示了平均可靠度随时隙数目变化的关系．可以看出，两种算法的网络的平均可靠度呈现下降趋势，这是因为随着时隙数目的增多，网络拓扑表现出较强的间歇连通特征，使得数据传输可靠性下降．由于算法1中含有最高可靠度的路径，所以较算法2可靠度更高．

图4 网络传输开销比和平均可靠度随时隙数目的变化曲线

固定链路密度p=0.8，时隙数量为6，保持其他仿真参数不变，统计网络具有不同节点数目时的性能．图5(a)显示了传输开销比随节点数目的变化关系．两种算法的传输开销比都随着节点数目的增大而下降，这表明了节点数目越多，越能体现两种算法在传输开销方面的有效性，且算法2体现的更加明显．图5(b)显示了平均可靠度随时隙数目变化的关系．两种算法的平均可靠度随着节点数目的增多而变大，因为当网络节点数目增大时，在链路密度一定的情况下，链路数量相对较多，节点对间更有机会选择可靠性高的路径，且算法1具有更高的可靠性．

图5 网络传输开销比和平均可靠度随节点数目的变化曲线

综上，相比原网络来说，在保证网络连通的情况下，两种算法都能保证数据传输的可靠性，同时降低网络的传输开销．算法1在可靠度方面比算法2略显优势，而算法2比算法1在传输开销方面略显优势．

5 结 束 语

时延容忍网络的节点和链路动态性为拓扑控制带来挑战．笔者基于拓扑周期性可预测的时延容忍网络，首先将网络的拓扑结构转化为时空图，进而定义了可靠拓扑控制问题．针对此问题，提出了两种有效的拓扑控制方案．拓扑控制的目的是在不破坏网络连通性的条件下保证网络的可靠性和降低网络的传输开销．最后，仿真验证了提出的方法的有效性．网络拓扑的性能会对网络路由和数据传输产生影响，在拓扑控制的基础上，性能优越的路由技术应该被设计．因此，在未来的工作中，路由的研究将是一个重要话题．