如今，具备信息快速回传功能的遥感卫星正处在快速发展的趋势中，不仅被各国用来实现全球范围的对地观测、侦察和测绘，而且在国防监视、精确测图、情报搜集和战场目标导引等方面也能发挥重要作用^{[1, 2]}.这类卫星传感网是一种低轨道卫星星座，具有传输延时大、流量分布不均匀的特性，大量流量负载集中在高纬度区域^[3].因此，在研究这类卫星传感网的路由机制时，不能像传统的卫星网络路由算法一样只考虑寻找最短路径，还需要考虑网络资源受限的情况，以流量均衡为目的的路由机制可能会更好地优化网络传输性能^{[4, 5]}.

为了更好地利用网络资源，提升网络容量利用率，Kucukates等提出了最小流量最大剩余带宽路由算法^[6]；后来，研究者们基于多协议标签技术(MPLS)提出了最宽-最短路径WSP算法和最短-最宽路径SWP算法^[7]，算法综合考虑了带宽权重和最短传输路径2个方面的因素，但缺点是没有考虑将来可能的流量请求，也会导致网络拥塞；针对高延时、链路通断频繁的行星际网络，NASA喷气推进实验室的研究人员Burleigh提出了一种连接图路由算法CGR，该算法利用已知的连接计划(contact plan)，根据这些确定信息来计算路径的路由算法^[8].目前卫星网络路由算法采用虚拟拓扑结构策略已经取得了一定的成果，但是对网络传输性能的优化效果不明显，大负载情况下依然容易导致网络拥塞，这样会严重影响网络服务质量和性能指标^{[9, 10]}.因此，有必要针对卫星网络高动态性、高延迟的特点，对路由算法展开进一步的研究.

本文采用快照聚合多路径路由(snapshot integration multipath routing，SIMR)算法，它是对单路径路由SIR^{[11, 12]}算法改进拓展后的结果，解决了SIR算法在网络传输数据量不断增大时，易出现链路剩余容量不足，从而导致端到端时延增大、网络拥塞的问题.

SIRM算法本质是实现多商品流网络中数据的分流传输；可分流的多商品流问题实际上是一种多路径路由，所以可以借鉴多路径路由算法的思想来实现快照聚合拓扑图^[13]中的数据分流传输，即将连续多个快照片段连接在一起，形成快照聚合拓扑图，然后再进行路由规划.本文提出的SIMR算法不仅可以减少单一快照片段路由规划带来的网络开销，还能够通过更合理的路径选择，避免网络拥塞，为信息快速回传卫星网络的发展提供更好的技术基础.

1 SIMR关键技术

多路径路由的关键技术主要包括路径发现、路径维护和流量分配3个方面，而本文提出的快照聚合拓扑图是一个静态网络，故不考虑路径维护的问题.因此仅从路径发现和流量分配这2个方面说明SIMR算法的数学模型与实现.

1.1 路径发现

路径发现是指路由算法在源、目的节点间寻找出多条路径，构成多路径集合供路由传输使用的过程.在SIR算法中，利用模拟退火算法的思想在快照聚合拓扑图中寻找最优解；而对于扩展后的SIMR算法，不仅要找到最优解，还需要寻找多个次优解，来提供多条有效的传输路径.

由于新解都是由邻域函数产生的，邻域函数一般是在当前解的邻域内进行随机搜索，通过比对寻找比当前解更优的解作为新的当前解，所以这里初始化1个数组f[n]，记录SIMR算法寻找的n个较优解，其中n为算法发现的参与流量分配的路径数.

对SIMR算法的修改具体过程如下：

步骤1  在算法开始时，定义并初始化一个数组f[n]，并将初始解S插入到数组的第1位；

步骤2  在邻域函数得到新解，并通过Metropolis准则进行对比，不论新解是否被当作新的当前解，都将新解与数组f[n]中的解比较，从数组的第1位开始按比较排序的方式插入新解；

步骤3  当算法终止时，得到的数组f[n]保存了n个较优解并包括最优解.

1.2 流量分配

选择好源、目的结点间的路径集后，需要根据路径上的链路信息来分配传输流量.流量分配机制用来处理在多路径间如何对源节点数据进行分配的问题，是多路径路由实现流量均衡的重要部分.该过程中最为关键的问题就是分流比的确定，合理的分流比例不仅可以减少网络中的拥塞状况，还能够进一步优化网络性能.

通过对SIR算法的拓展，SIMR得到了记录n个较优解的数组f[n]，每个解对应着1条路由路径，其评价函数设定为最大链路利用率，则这n条路径对应的最大链路利用率数组表示为ρ[n].对于同一个源节点的数据包，根据数组ρ[n]的值进行流量分配，分流的比例也可以用数组r[n]记录.对于数组中的某一条路径m，m=1, 2, …, n，它的最大链路利用率可表示为ρ[m]，那么它对应的流量分配的比例r[m]可以用下式计算：

2 SIMR算法原理 2.1 数学模型的建立

由于SIMR算法与SIR算法都是对快照聚合拓扑图进行路由规划，所以可采用同样的数学模型对这个商品流问题进行建模与分析，如文献[11]中的式(3-4)~(3-9)所描述，唯一的区别是，SIMR是支持多路径传输的路由算法，故数据传输路径的变量x_de的约束条件应满足：

2.2 SIMR算法实现过程

SIMR算法解决的是可分流的多商品流问题，以下是对SIMR算法的步骤描述.

1) 初始化阶段，设置模拟退火计划表：初始温度T(充分大)，初始解S(令它为当前解，是循环迭代过程的起点)，每个T值的循环次数L，并初始化数组f[n](记录n个较优解).

2) 对k=1, 2, …, L执行步骤(3)~(6).

3) 执行邻域函数，得到新解S^*.

4) 首先，将新解S^*与数组f[n]中的解进行比较，若大于某一解，则插入S^*；然后，计算增量：

其中，C(S)为评价函数.

5) 执行Metropolis接受准则：若Δt < 0，则令S=S^*，接受S^*为新的当前解；否则，以概率exp(－Δt/T)接受S^*作为新的当前解.

6) 如果满足终止条件，则输出当前解作为最优解，算法终止.终止条件通常设定为连续若干个新解都没有被接受时算法终止.

7) T逐渐减小，当T>0时转至步骤(2).

3 SIMR算法的仿真实验及分析 3.1 仿真环境

在仿真实验中，首先利用STK设计出信息快速回传卫星传感网的场景图，并得出卫星的可见性分析，如图 1所示；然后根据星间链路随时间的变化，设计配置文件；最后，将SIRM算法与应用在卫星网络中性能比较好的CGR算法进行对比，在机会网络环境ONE中进行仿真实验，并统计仿真结果.

因为“节点存储空间”可以反映卫星节点的数据存储能力，“单位时间源产生数据流量”可以反映链路的数据传输能力.所以，仿真实验将选取这2个配置参数作为变量，在其他配置参数(如仿真时长、仿真节点的分类、仿真事件的设置等)固定的情况下，来分别说明这2个配置参数的变化对算法性能所造成的影响.

3.2 结果分析 3.2.1 数据流量对算法性能的影响分析

通过改变源节点产生的数据流量，来分析算法性能指标的变化，修改表 1中的该配置参数为4~13 Mb.

1) 网络性能指标

如图 2所示，SIMR的成功交付率要高于SIR，而SIR要高于SWP和CGR.当单位数据包比较大时，SIR的成功交付率开始明显低于SIMR，开始接近于CGR和SWP，甚至略低.这是因为在传输数据量较大的时候，SIR也出现了网络拥塞，SIMR采用了数据“分流”的多路径传输方法，能够更大程度地实现流量的均匀分布，更好地避免网络拥塞，从而保持了相对较高的成功交付率.

如图 3所示，SIMR和SIR的平均网络延时要高于SWP和CGR，因为SIMR和SIR是利用DTN特性对连续多个快照进行整体的路由规划，为了使网络流量均衡并减少丢包率而采用了“存储—等待—再转发”的路由机制.

2) 资源占用指标

如图 4所示，SIMR和SIR相比于WSP和CGR剩余更多的存储空间，这是SIR实现网络流量均衡的结果；随着数据量的增大，SWP和SIR的平均节点存储占用率上升较快，并在传输数据量到达一定值的时候超过了CGR.这是因为CGR出现了网络拥塞，丢弃了大量数据包；而SWP的路由机制导致了只有在数据量较小时，才能实现流量均衡，不能很好地适应大数据量请求的网络环境；SIMR和SIR一直保持比较低的丢包率，所以相应的平均节点存储占用率会不断增大.

如图 5所示，在最大链路利用率的折线图中，应用CGR算法的网络中一直都有链路利用率过高、剩余带宽不足的链路存在；而对于能够实现流量均衡的SWP、SIR以及SIMR算法，网络中最大链路利用率虽然也比较高，但也还保留了一部分的剩余带宽，只是当传输数据量较大时，才出现了剩余带宽不足的链路.其中，在实现网络流量均衡的能力上，SIMR要优于SIR，SIR优于SWP.

3.2.2 节点存储空间对算法性能的影响分析

通过改变节点的存储空间，来分析算法性能指标的变化规律，表 1中的存储空间改为40~200 Mb.

1) 网络性能指标

如图 6所示，从整体来看，SIMR和SIR的成功交付率要高于CGR和SWP, 并且在节点存储空间增大到一定值时，SIMR的成功交付率将维持在一个定值，因为网络中已经不存在节点拥塞的情况，但其他3种算法的成功交付率还处在上升阶段，仍然会出现节点拥塞的情况，需要更大的节点存储空间.对于网络时延，SIMR的平均网络延时要低于SIR，这是因为SIMR对源节点产生的数据进行分流操作，使得来自同一个源节点的数据包不需要通过同一条路径进行传输，这样大大缓解了节点的存储压力以及链路的传输压力，从而减少了网络时延.

2) 资源占用指标

如图 7所示，4种算法都会出现剩余存储空间不足、节点拥塞的情况，当节点存储空间增大到一定值后，SIMR算法首先避免了网络拥塞，已经不存在拥塞的网络节点，而其他3种算法对节点的存储空间要求更高，仍然存在拥塞的节点.

如图 8所示，随着节点存储空间的增大，算法的成功交付率不断上升，使得链路的带宽需求开始增大，对于整个网络来说，它的平均链路利用率也随之上升.其中SIMR和SIR算法的平均链路利用率要低于CGR和SWP算法.不同之处在于，SIMR和SIR算法为了实现网络的流量均衡，是以最小化最大链路利用率作为快照聚合模型的目标函数，来计算路由路径进行流量分配的，故平均链路利用率要低于CGR和SWP算法.

4 结论

面对信息快速回传卫星资源受限的情况，SIMR算法和SIR算法以最小化最大链路利用率作为目标建立的快照聚合模型，能够有效地实现流量均衡，避免网络拥塞.虽然增加了一部分的网络延时，但SIMR算法和SIR算法相较于SWP算法和CGR算法，在消息的成功交付率、节点的存储占用率以及链路的带宽利用率上都实现了一定程度的优化.同样从仿真结果可以看出，当传输数据量很大时，SIMR仍然能够实现网络流量均衡，保持较好的性能优化能力，而SIR的网络优化效果并不理想.所以，在数据请求量不大时，SIMR和SIR都能够实现网络流量均衡, 但在大负荷数据请求的情况下，信息快速回传卫星传感网应该应用支持多路径传输的SIMR算法.