卫星网络中基于网络编码的机会路由算法

技术领域

本发明涉及一种在MORE、CCACK协议的基础上改进而得到的卫星网络中 基于网络编码的机会路由算法，其适用于对卫星网络提升网络平均吞吐量。

背景技术

随着网络通信的发展，为了适应大数据传输、商务和文娱胡井喷式需求， 使得卫星网络数据传输具有很大的研究意义。相对于传统的路由策略，采用网 络编码可以提高网络的吞吐量，针对卫星网络拓扑动态变化、星际链路间断性 连接等特性，机会路由可以利用链路的多样性来提供更好的路由策略。网络编 码与机会路由的结合可以为提升卫星网络的吞吐量提供一种解决方式，典型的 基于网络编码的机会路由协议有MORE、CCACK协议等。MORE协议通过网 络编码解决了机会路由中链路协作困难的问题。在MORE协议中，源节点利用 转发节点到目的节点的ETX(ExpectedTransmissionCount)值预先计算出每个 转发节点的信誉值，以此来决定节点的转发概率，但这种计算方式只是在链路 初始状态时收集丢包率和计算信誉值，无法适应卫星网络链路的动态变化。 CCACK协议采用的是逐跳反馈的方式来减少编码包的冗余发送，上游节点通过 正交向量运算判断下游转发节点是否已经接受到了足够的信息量，从而及时停 止编码包的发送，减少网络冗余，但CCACK协议中源节点发送速率是启发式 的，没有理论证明最大吞吐量够收敛到最优解，且探测链路连接状态的方式与 MORE相同，所以也不能适应卫星网络链路的动态变化。

发明内容

本发明的目的是提供一种卫星网络中基于网络编码的机会路由算法，其在 保证网络平均吞吐量最大的前提下，能够减少网络中冗余数据包的传输，且能 抵抗一定的链路失败率。

为了实现上述目的，本发明采用的技术方案如下：一种卫星网络中基于网 络编码的机会路由算法，包括

S1：对卫星网络的最大平均吞吐量进行建模，其中建模元素包括节点、信 源的发送速率、平均吞吐量的绩效函数、信誉率、数据包、反馈编码包，所述 节点包括源节点、目的节点和中继节点；

S2：用凸优化理论求出该模型最优解的结构；

S3：采用编码反馈技术将代表接收到数据包的反馈信息压缩在一个反馈编 码包中，同时，利用编码反馈技术在每个节点本地维护一个链路状态表，其中， 链路状态即本节点与相邻节点的信息以及该链路的度量，度量包括本节点与邻 居节点的拉格朗日变量差值；

S4：利用编码反馈算法，中继节点处理决定发送当前数据包的下一跳节点 集和决定集合中节点信誉率的大小；

S5：确认数据段。

进一步的，在所述步骤S1中，通过如下方式建模：

卫星网络的平均吞吐量表示如下：

要求最大值：

MaximizeU(R_S)

约束条件：

${\Sigma }_{v\in V}{X}_{vu}-{\Sigma }_{v\in V}{X}_{uv}\le \left(\begin{array}{cc}-R_S,& u=S\\ 0,& else\end{array}\right)$

其中，$\forall u\in V\backslash D$

$\left(\begin{array}{cc}{\Sigma }_{v\in J}{X}_{uv}\le R_{uJ}& \forall u\in V\backslash D\end{array}\right)$

其中，S为源节点；D为目的节点；R_S为信源的发送速率；U(R_S)为平均吞吐 量的绩效函数；X_uv表示节点u传递给节点v的信誉率，即节点v从节点u接收到的 所有线性无关的数据包中，节点v需要向下一跳节点发送的线性无关数据包的速 率；R_uJ表示节点u发送且集合J中任意节点接收数据包的速率之和；假设节点u有 k个下一跳节点，则有2^k-1个下一跳节点的组合；任意的集合J都属于2^k-1集合中 的一个。

进一步的，在所述步骤S2中，所述凸优化理论采用拉格朗日对偶方法。

进一步的，在所述步骤S3中，所采用的编码反馈技术为采用零空间来实现 编码反馈。

进一步的，在所述步骤S3中，每个所述节点处设置一个计时器，该计时器 计算该节点第一次发送数据包到接收到下一跳节点反馈编码包的时间T，如果在 2T时间内，发送节点收不到下一跳节点的反馈包且该段数据没有发送完成，则 认为该条链路中断，连通状态更新为0，当检测到链路状态表中链路的连通状态 发生改变时，节点重新发送探测信息，及时发现和维护邻站的可达性，并更新 链路状态表，重新发送当前数据段。

进一步的，所述步骤S5具体包括：

S51：目的节点收到反馈编码包后，将其加入到当前数据段的解码矩阵中； 一旦目的节点解码成功时，立刻向源节点发送一个ACK包；

S52：当源节点收到当前数据段的ACK包时，更新缓存，开始下一个数据 段的发送任务，其他中继节点一旦侦听到ACK包或者接收到新数据段的反馈编 码包时，停止当前数据段的发送。

进一步的，在所述步骤S51中：ACK包的优先级高于所有数据包。

进一步的，在所述步骤S51中：使用拉格朗日变量差值最大的节点进行发 送ACK包。

借由上述方案，本发明至少具有以下优点：本发明的卫星网络中基于网络 编码的机会路由算法，在保证网络平均吞吐量最大的前提下，能够减少网络中 冗余数据包的传输，且能抵抗一定的链路失败率。

上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术 手段，并可依照说明书的内容予以实施，以下以本发明的较佳实施例并配合附 图详细说明如后。

附图说明

图1是本发明的卫星网络中基于网络编码的机会路由算法的流程图。

图2是零空间反馈情形；

图3是节点u通过反馈向量建表；

图4是链路发生中断图示；

图5是信誉率分配示例。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以 下实施例用于说明本发明，但不用来限制本发明的范围。

请结合图1，本发明一较佳实施例所述的一种卫星网络中基于网络编码的机 会路由算法包括步骤S1至S5。

S1：对卫星网络的最大平均吞吐量进行建模，其中建模元素包括节点、信 源的发送速率、平均吞吐量的绩效函数、信誉率、数据包、反馈编码包，所述 节点包括源节点、目的节点和中继节点。

其具体通过如下方式建模：

卫星网络的平均吞吐量表示如下：

MaximizeU(R_S)(1)

约束条件：

${\Sigma }_{v\in V}{X}_{vu}-{\Sigma }_{v\in V}{X}_{uv}\le \{\begin{array}{cc}-R_S,& u=S\\ 0,& else\end{array}---\left(2\right)$

其中，$\forall u\in V\backslash D$

$\begin{array}{cc}{\Sigma }_{v\in J}{X}_{uv}\le R_{uJ}& \forall u\in V\backslash D\end{array}---\left(3\right)$

其中，S为源节点；D为目的节点；R_S为信源的发送速率；U(R_S)为平均吞吐 量的绩效函数；X_uv表示节点u传递给节点v的信誉率，即节点v从节点u接收到的 所有线性无关的数据包中，节点v需要向下一跳节点发送的线性无关数据包的速 率；R_uJ表示节点u发送且集合J中任意节点接收数据包的速率之和；假设节点u有 k个下一跳节点，则有2^k-1个下一跳节点的组合；任意的集合J都属于2^k-1集合中 的一个。

S2：用凸优化理论求出该模型最优解的结构；

由公式(2)、(3)可知，约束条件是线性的，且是两个闭半空间的交集， 而该交集是一个凸集，同时，目标函数是个凹函数，所以需要解这个凹函数的 最大值，其方法可以用对偶方法来解决这个问题，那么该问题即为一个凸优化 问题，在本实施例中，所述凸优化理论采用拉格朗日对偶方法。又由于约束条 件的slater条件成立，对偶问题与原始问题不存在对偶间隙，则对偶问题的最优 解是原始问题的最优解。

上述凸优化理论求出该模型最优解的结构的具体方法如下：

用拉格朗日乘法对公式(2)的约束条件乘以拉格朗日乘子λ_u得如下拉格朗 日函数：

L(R,X,λ)＝U(R_S)-λ_SR_S-λ_u(∑_v∈VX_vu-∑_v∈VX_uv)(4)

约束条件为公式(3)。

对公式(4)进行变形，得：

L(R,X,λ)＝U(R_S)-λ_SR_S+∑_v(λ_u-λ_v)X_uv(5)

根据公式(5)可以得到基本算法，如下所述。

源节点算法：当网络中有数据要发送的时候，源节点首先将待发送的数据 分成若干个大小相同的数据段，每个数据段由k(k＞0)个数据包组成。源节点S按 照公式(6)以相同的速率将数据包注入到数据段中，其中，t是指数据段的编 号。

R_S(t)＝argmax[U(R_S)-λ_S(t)R_S](6)

中间节点算法：每个中间节点u根据公式(7)为下一跳节点分配信誉率。

约束条件为公式(3)。

拉格朗日变量更新算法：按照公式(8)用递归法对每个节点的拉格朗日变 量进行更新。

${\lambda }_u(t+1)=\left(\begin{array}{c}{\lambda }_u\left(t\right)+[{\Sigma }_{v\in V}{X}_{vu}\left(t\right)-{\Sigma }_{v\in V}{X}_{uv}\left(t\right)]+R_S\\ ,u=S\\ {\lambda }_u\left(t\right)+[{\Sigma }_{v\in V}{X}_{vu}\left(t\right)-{\Sigma }_{v\in V}{X}_{uv}\left(t\right)]\\ ,else\end{array}\right)---\left(8\right)$

S3：对基本算法的不足之处进行改进：采用编码反馈技术将代表接收到数 据包的反馈信息压缩在一个反馈编码包中，同时，利用编码反馈技术在每个节 点本地维护一个链路状态表，其中，链路状态即本节点与相邻节点的信息以及 该链路的度量，度量包括本节点与邻居节点的拉格朗日变量差值。

由于基本算法有两个不足之处：(1)算法需要大量的反馈信息。例如，当 源节点有数据发送时，首先将数据分割成大小相等的数据段，每个数据段由k个 原始数据包组成。当发送k个包到L个下一跳节点时，每个数据段需要k×L个反 馈信息。此外，由于卫星网络链路有损，也增加了反馈信息的难度；(2)无法 适应卫星网络星间链路间断性连接。

针对问题(1)，采用编码反馈技术将代表接收到数据包的反馈信息压缩在 一个反馈编码包中，以减少反馈信息的发送。

所采用的编码反馈技术为采用零空间来实现编码反馈。矩阵A的零空间是线 性的向量空间，因此，如果向量y属于A的零空间，则Ay^T＝0，其中y^T是y的转置。 请参见图2和图3。

在图2中，每个节点的向量代表编码数据包的系数，如向量[4,3,1]表示编码 数据包"4X₁+3X₂+X₃"，虚线的箭头表示反馈的零空间的任意一个向量。图中节点u 发送3个反馈编码包，节点v收到其中的2个，节点v可以计算出它收到数据包 空间的零空间，并从这个空间里面随机选择一个向量，返回给节点u。

在图3中，节点u收到这个下一跳节点反馈的零空间的向量后，与自身节点 缓存中的数据包做乘积运算，如果结果为0，在表中相应位置做标记，表示节点 u可以推测出这个数据包有很大的概率被节点v接收到。否则，节点u推测出这个 数据包没有被节点v成功接收。

针对问题(2)，利用反馈的方法，在每个节点本地维护一个链路状态表。 当链路状态发生改变时，更新链路状态表以保证邻居节点的可达性。

利用编码反馈技术，在每个节点本地维护一个链路状态表，其中，链路状 态即本节点与相邻节点的信息以及该链路的度量，度量包括本节点与邻居节点 的拉格朗日变量差值。

表1：节点链路状态表格式

在链路状态表中，若节点与下一跳节点链路连接，则连通状态标记为1，若 链路断开，则标记为0。初始化时，节点与探测到的下一跳节点之间的连通状态 都为1。请参见图4。

表2：根据链路状态的变化更新链路状态表

在步骤S3中，每个所述节点处设置一个计时器，该计时器计算该节点第一 次发送数据包到接收到下一跳节点反馈编码包的时间T，如果在2T时间内，发送 节点收不到下一跳节点的反馈包且该段数据没有发送完成，则认为该条链路中 断，连通状态更新为0，如图4和表2所示，当检测到链路状态表中链路的连通 状态发生改变时，节点重新发送探测信息，及时发现和维护邻站的可达性，并 更新链路状态表，重新发送当前数据段。

S4：利用编码反馈算法，中继节点处理决定发送当前数据包的下一跳节点 集和决定集合中节点信誉率的大小；

中继节点需要处理：(1)决定发送当前数据包的下一跳节点集合J；(2)决 定集合J中节点信誉率的大小。

中继节点在处理第一个问题时，需要找出最优的下一跳节点。由公式(3)、 (7)可以看出，目标函数(7)是X_uv的线性函数，为了求目标函数的最大值， 且能够满足约束条件(3)，中继节点u需要通过存储λ_u-λ_v的差值来排列下一跳节 点的优先级。差值大的节点优先被发送数据包。在发送数据的过程中，得到信 誉值的节点集即为步骤S1中所述的集合J，该集合为当前节点的最优下一跳节 点的集合。

针对第二个问题，通过公式(3)可知，如果下一跳节点v收到反馈编码包 且没有其他拥有更大差值的节点收到该数据包，则节点v可以通过这个反馈编码 包来增加信誉率，直到各下一跳节点的信誉率之和等于中继节点要分配的信誉 率，其利用编码反馈的方法来实现这一过程。

如图5所示，节点u有3个编码数据包要发送，即节点u有3个信誉值要分 发给下一跳节点。节点v收到2个反馈编码包，节点w也收到2个反馈编码包。 通过节点v、w反馈的零空间向量，以及节点w具有更大的拉格朗日变量差值， 节点u为w分配2个信誉值，为节点v分配1个信誉值。

S5：确认数据段。

该步骤S5具体包括：

S51：目的节点收到反馈编码包后，将其加入到当前数据段的解码矩阵中； 一旦目的节点解码成功时，立刻向源节点发送一个ACK包；在本步骤中，ACK 包的优先级高于所有数据包，而为了保证ACK快速可靠的传递，使用拉格朗日 变量差值最大的节点进行发送ACK包。

S52：当源节点收到当前数据段的ACK包时，更新缓存，开始下一个数据 段的发送任务，其他中继节点一旦侦听到ACK包或者接收到新数据段的反馈编 码包时，停止当前数据段的发送。

上述卫星网络中基于网络编码的机会路由算法简单来说即：(1)源节点控 制每个数据段的发送速率，使得网络中最大吞吐量能够收敛到最优解，并利用 凸优化理论证明该方法的可行性；(2)下一跳节点根据自己接收到的数据包， 利用编码反馈技术，减少网络中冗余包的传输；(3)每个节点在本地维护一个 下一跳节点的列表，当链路状态发生改变时，更新列表，以保证邻居节点的可 达性。

在具体实施时，可将该算法放在卫星节点上，源节点根据该算法调整发送 速率；中继节点根据该算法最优选择下一跳转发节点集，并通过编码反馈技术 减少网络中冗余包的传输，且保证邻居节点的可达性；目的节点收到足够多数 据包且解码成功时，立即向源节点发送ACK包。当源节点收到当前数据段的 ACK包时，更新缓存，开始下一个数据段的发送任务。其他中继节点一旦侦听 到ACK包或者接收到新数据段的反馈编码包时，停止当前数据段的发送。该算 法从理论上证明可以使最大吞吐量收敛到最优解，且适用于卫星网络，并能抵 抗一定的链路失败。

以上所述仅是本发明的优选实施方式，并不用于限制本发明，应当指出， 对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还 可以做出若干改进和变型，这些改进和变型也应视为本发明的保护范围。