基于网络编码的卫星网络容量提升方法*

王瑞松，钟志聪，刘功亮，马若飞

（哈尔滨工业大学，山东 威海 264209）

0 引言

空间动态网络[1-3]是伴随着人们日益增长的服务需求而不断发展的，网络用户数量的增长、节点类型的多样化、数据传输的高质量要求以及网络资源的受限等一系列的特点使得空间动态网络在网络扩展、资源共享、一体化组网和网络传输能力等方面面临着更大的挑战。因此，在不增加卫星网络节点数量、频带、存储、功率等资源的情况下，探索有效提升网络传输容量和服务质量的网络传输方法是目前国内外在卫星领域研究的热点问题，也是空间动态网络发展的关键。

在卫星通信系统中也有一些关于网络容量方面的研究，文献[4]针对多波束卫星-地面通信系统提出了一种自适应功率控制方法，通过优化传输功率来降低系统间的干扰，可以增加系统总容量。文献[5]根据负载集中地区的位置，结合卫星的发射功率和卫星点波束的峰值增益来进行功率资源的分配，在发射功率和波束方向性之间进行权衡，与传统的分配方法相比可以容纳更多的流量。文献[6]在多波束卫星通信系统中针对传统的迭代注水算法存在的运算量和复杂性高的问题，提出了一种低复杂度的改进功率分配算法，可以减少计算的开销并保证网络容量的最大化。文献[7]研究了利用智能网关分集设置在多波束高通量卫星系统中实现最佳容量分配的方法。上述研究虽然在资源分配和容量优化方面进行了深入研究，提供了一些相应的解决方案，但是这些研究都集中在多波束卫星对地通信的场景，且这些场景中的卫星数量比较少，没有考虑在卫星网络中进行星间通信的情况，这也是目前研究中的特点，大多数研究都主要针对星地通信而缺少对星间通信方面的研究。文献[8]虽然建立了具有星间链路的星间通信模型，研究了卫星功率和带宽联合分配的优化算法，提高了卫星的资源利用率和系统容量，但是没有考虑卫星网络的动态特性，结构比较简单，缺乏具体的空间动态网络分析模型。

网络编码是一种有效地提升网络容量的工具，自提出以来，学者们对网络编码理论的研究和完善从未间断，取得了许多重要的研究成果。Katti等人在文献[9]中提出一种完全机会编码方案（COPE,Completely Opportunity Encoding），对网络编码的基础理论研究提供了重要参考。受到COPE的启发，研究者们相继提出了一些通过将路由与流间网络编码相结合来提升网络容量的方法[10-13]。但是这些流间网络编码的方法中网络流通常是通过最短路径进行传输，节点只能被动地等待可用的编码机会，无法利用其它潜在的编码机会。文献[14-17]提出了能够感知编码机会的路由算法来克服COPE方法的缺点。近些年来，有大量的研究利用网络编码技术来探索地面网络中包括无线自组网、无线网状网和无线传感器网络的网络传输性能提升方法，文献[18]提出一种网络编码路由协议（NCRT,Network Coding Routing），利用编码感知和负载感知路由度量来充分利用网络编码的优势，并提出一种增强的编码条件用以查找更多的编码结构来传输更多的编码分组，提高网络容量。

综合上面的分析，本文考虑了一个单源多目的的动态卫星网络场景，然后针对网络编码与非网络编码情况对网络容量进行了分析。本文的主要贡献包含下面几点：1）利用时间扩展图对网络的动态性进行了分析；2）针对网络编码的情形，分析了网络容量并获得最优解；3）针对非网络编码情形，分析了网络容量并提出基于二分法的最优容量解；4）提供了仿真场景来评估网络编码对性能的影响。

1 系统模型

1.1 网络场景

考虑一个单源多播的传输场景，其中源节点S向包含多个目的节点的目的节点集合D={di|i=1,2,…,N}传输同一段数据，利用线性网络编码的方法提高网络的传输容量。业务在源节点产生时，源节点将原始数据划分为多个分段，每个分段包含相同数量的数据包，然后源节点将每个分段的原始数据包进行随机的线性组合后依次发送出去，这个将原始数据进行线性组合的过程就是编码；中间节点收到编码数据包之后，将编码数据包存储在本地，并与其他编码数据包一起重新进行线性组合生成新的编码数据包，然后发送出去；最后目的节点收到编码数据包之后不再进行转发，当其收到足够多的非线性相关的编码数据包便可以解码得到原始数据包。

卫星网络的动态特性是卫星网络相关算法研究都需要处理的难点，动态性便意味着复杂性，如何处理卫星网络复杂的动态变化是研究过程中首先要解决的问题。本文采用基于虚拟拓扑策略的动态拓扑分析方法，关键在于将卫星网络连续的运行周期离散化，分解为多个时间片段，相应地，卫星网络的动态特性也随之离散静止化。

为了刻画网络的动态性，本文将卫星网络建模为一个时间扩展图G(V,E,C,T,B)。具体的符号含义如下所示。T={1,2,...,n}表示时隙集合。对于卫星网络的运行周期T，本文将其等间隔地划分为n个时隙，每个时隙的持续时长为τ，即：

时隙的划分是为了静态化处理卫星网络拓扑，在每个时隙内卫星之间的可见关系认为是固定不变的，一颗卫星A若在一个时隙的时间内持续可见另一颗卫星B，才认为卫星A在该时隙可见卫星B。对于卫星网络的节点可见关系，这里可以用一个时间相关的矩阵集合表示，即V={vi,1≤i≤M}，表示卫星节点i。

卫星网络中星间链路的存在与否也可以用一个时间相关的矩阵集合来表示，其中为第t个时隙的卫星网络的星间链路矩阵。

星间链路的建立需要满足卫星双方相互可见的条件，也就是必须在的条件下，卫星i和卫星j才有可能建立星间链路。若不考虑其他建链约束，认为卫星之间相互可见即存在星间链路：

C={C(t)|t∈T }为卫星网络在每个时隙的链路容量集合，为第t时隙的链路容量集合。其中可以根据香农公式计算：

其中GT、GR、P分别表示传输增益、接收增益以及发射功率。k、T、B分别表示玻尔兹曼常数、噪声温度以及带宽，为两个节点在第t个时隙的自由空间路损。

综合以上的分析和总结，本文利用时间扩展图对动态卫星网络进行静态地刻画。首先，引入存储弧的概念将网络中不同时隙的同一节点连接起来，用以表示数据可以从上一时隙传输到下一时隙，将不同时隙的静态拓扑相连接，实现数据的跨时隙传输，因此存储弧必然是单向的，因为数据只能从上一时隙往下传，而不能逆时间传输。图1所示为包含5个节点的卫星网络时间扩展图。

图1 卫星网络时间扩展图

图1中存在两种类型的弧，其中黑色的弧表示链路弧，用来反映卫星网络的连通关系，其权重为星间链路传输容量，红色的弧为存储弧，用来反映节点在转发受限时自身的缓存能力，是连通相邻时隙拓扑图的关键，其权重为卫星节点的缓存空间的大小。

时间扩展图通将分隔的各时隙拓扑图联系起来，能够反映数据跨时隙传输的过程，真正实现了卫星网络从动态到静态的转化，基于此，用于分析网络容量的最大流算法便可以直接应用，至此我们完成了对卫星网络动态拓扑处理模型的描述。

1.2 优化目标与约束条件

对于给定的网络传输模型，由于空间动态网络中的数据传输采用的是“接收-存储-转发”的机制，因此，在每个时隙中，每个中间节点从上一跳节点中接收到的流量与从上一个时隙缓存下来的流量之和应该等于该节点在本时隙转发出去的数据量加上存储在本节点中缓存到下一时隙的数据量。因此，对于每个目的节点的网络流而言，中间节点的流守恒约束为：

对于网络流的源节点来说，每个时隙传输的数据总量应该由两部分组成，一是本时隙成功发送的数据量，二是在本节点中缓存到下一时隙的数据量：

其中vs表示源节点，表示第t时隙源节点传输的数据总量。

对于网络流的目的节点来说，目的节点只接收数据，数据到达目的节点之后不再转发，因此也不会缓存到下一时隙，则有：

考虑到卫星节点的存储空间有限，每个时隙各节点缓存到下一时隙的数据量应满足以下约束：

除此之外，还需要添加上网络流容量的约束。对于网络编码的场景，流量约束为：

对于非网络编码的场景，网络流约束为：

对于单源多目的的卫星网络多播场景，网络容量实际上是卫星网络在指定的时间内从源卫星节点发送相同数据到多个目的卫星节点的数据量上限。利用网络编码的链路资源共享特性，基于线性网络编码方案下的系统多播容量，实际上仅受各通向目的节点的网络流中单播容量最小的一个限制，因此基于网络编码的优化问题可以表示为：

非网络编码的优化问题可以表示为：

2 求解方法

2.1 基于网络编码的求解方法

对于优化问题(12)，可以看出它是一个可分离的问题。根据目的节点的不同，可以将其分解为N并行的子问题，也就是：

假设对于每个目的节点d而言，问题(14)的最优目标函数值为,d∈D。则优化问题(14)的最优目标函数值为。因此，求解问题(12)的关键是求解问题(14)。

通过分析问题(14)，这是一个单源多目的最大流问题。有多个目的节点的主要原因是卫星网络是随时间变化的，尽管卫星是相同的，但是在每一个时刻卫星的状态是不同的。为了求解这一问题，可以添加一个虚拟节点，然后添加虚拟边来连通每一个目的节点，并将虚拟边的容量设置为无穷大。为了说明这一过程，本文给出一个例子。

如图2所示，图中有一个源节点S两个，目的节点D1、D2，三个中继节点。网络周期被划分为3个时隙，在每个时隙中，尽管目的节点没有改变，但是对于两个不同的时隙，我们认为这是两个不同的节点。然后，添加虚拟节点R1、R2。对于不同时隙的目的节点D1，添加单向弧将其与虚拟节点R1连接；对于目的节点D2，添加单向弧将其与虚拟节点R2连接，然后将虚拟边的容量设置为无穷大。

图2 网络编码的时间扩展图

数据只能通过各时隙目的节点传输到达虚拟节点，因此从源节点S传输到达虚拟目的节点R的数据量即为从源节点到各时隙目的节点的数据量之和，利用Ford-Fulkerson最大流算法求节点S到节点R的最大流即可求得动态卫星网络中源卫星到目的卫星的最大流。

2.2 非网络编码的求解方法

对于优化问题(13)，情况则变得更加复杂。这是由于约束(11)是一个耦合约束。为了处理这个问题，我们在下面提出一种方法来获得该问题的最优解。

首先，假设y*是问题(13)的最优目标值。然后，必然存在一个最优解使得对于任意的d∈D，满足。进一步，原问题(13)可以转换如下：

然后，根据2.1节中的思路进一步刻画相应的时间扩展图。如图3所示，进一步添加一个虚拟节点R，并添加虚拟边将其与R1、R2连接，边的容量设置为y。

图3 非网络编码的时间扩展图

然后，根据上面的方法可以定义一个y-最大流函数F(y)。这里，函数F(y)表示当虚拟边容量为y时节点S到节点R的最大流量。然后，很显然地可以得到下面的性质。

性质1：函数F(y)是关于y是非递减的。

这个性质是显然的，因为随着边容量的增加，网络的最大流肯定是非递减的。

性质2：F(y)-Ny≤0

这个性质也是显然的，因为网络的最大流量不可能超过割集的容量。

性质3：存在y*使得当0≤y≤y*时，F(y)-Ny=0；当y＞y*时，F(y)-Ny＜0。

这是因为当y比较小的时候，紫色虚拟边构成的割集是限制网络最大流的最关键因素；而当y趋近于无穷大的时候，网络中的其他边则成了限制网络最大流的主要因素。

然后根据这些性质，我们给出下面的定理。

定理1：假设y*=argmax(F(y)−Ny)，则y*是问题(15)的最优解。

证明：首先根据性质3，F(y*)−Ny*=0是必然成立的。因此，根据前面的叙述，y*对应的解必然是问题(13)的一个可行解。然后，假设它不是最优解，则最优目标值y**＞y*。此时，只需要将紫色虚拟边的容量设置y**，则可得F(y**)−Ny**=0。然而这与前面的假设矛盾，因此完成了该定理的证明。

为了得到这个最优解，我们利用二分法来设计算法。算法的基本步骤如下所示：

3 仿真分析

仿真以导航卫星网络为背景，考虑了一个包含24颗MEO卫星的Walker星座卫星网络，具体相关仿真场景中的常量参数如表1所示。接下来将从空间动态网络的功率资源、缓存资源、运行时长和多播场景中目的节点数量四种因素对网络容量的影响进行仿真分析。

表1 相关仿真场景中的常量参数

本实验采用控制变量的方法，令仿真中的其他参数固定不变，其中假设仿真时长为300 s，即5个时隙，目的节点数量为2个，每颗卫星的最大缓存空间为500 Mbit，仿真在不同传输功率下网络编码方案以及功率分配优化方案对空间动态网络容量的优化性能，各功率值对应场景仿真1 000次取平均，每次仿真源节点及目的节点从所有网络节点中随机选取。仿真结果如图4所示。

图4 网络容量随节点功率变化曲线

从图4中可以看出，随着每颗卫星的总传输功率的增加，平均系统多播容量也随之增加，并且功率从50 W到800 W的大跨度增长下，网络容量仍能继续提升，这是因为节点功率与链路容量息息相关，而只要链路容量持续增大，则网络容量便能随之持续增长。在同一功率情况下，基于网络编码的方法与非网络编码方案相比，网络容量得到了明显的提升。在功率增长时网络编码方案具有更快的网络容量增长速度，明确地展示了网络编码方案的优越性。

然后，为了评估时隙长度对性能的影响，我们给出了图5。假设每颗卫星的最大缓存空间为1 Gbit，每颗卫星的总传输功率为100 W，目的节点数量为2个，仿真在不同仿真时长下网络编码方案以及功率分配优化方案对空间动态网络容量的优化性能。仿真结果见图5。

图5 网络容量随仿真时长变化曲线

从图5可以看出，在一定范围内，随着仿真时长的增加，网络容量也在不断增加，这是因为随着仿真时长的增加，数据可以通过在节点中缓存的形式在后续增加的时隙中传输，使得网络中可传输的数据量更多，但由于节点的存储空间是有限的，随着传输数据量的增加，当某个时隙的节点缓存空间被占用完后，数据不能无限制地往后续时隙缓存，网络中的数据在一定时隙内便会被传输完成，使得即使仿真时长增加也没有数据在后续时隙中传输，因而当仿真时长增加到一定值时，网络容量便不再增长。通过对比发现，网络编码方案与非网络编码方案相比将网络传输容量的极限提升了3倍之多，说明在充分利用仿真时间内的功率资源和缓存资源的情况下，更能凸显网络编码的强大性能。

4 结束语

本文研究了卫星网络的容量提升方法，包括网络编码与非网络编码两种情形。其中，采用网络编码的最优卫星网络容量可以求解多个单源单目的网络最大流问题而得到。对于非网络编码情形，我们提出了基于二分法的最有容量求解方法。根据仿真结果，与非网络编码方案相比，采用网络编码的方案可以明显地提升网络的容量，并且，网络容量提升幅度随着资源以及网络规模的增加而增加。这也充分说明了网络编码技术的使用可以充分利用卫星网络的资源，从而改善卫星网络资源极其受限的情况。