基于随机线性网络编码的无线可靠广播方法

摘要

一种基于随机线性网络编码的无线可靠广播方法，包括两个阶段：广播原始数据包和重传编码包；也就是该方法先对丢失的数据包进行线性网络编码，然后重传编码包；各接收节点收到设定数量的编码包后，利用高斯消元法分别求解各自丢失的原始数据包。本发明既解决了传统重传方法不适用于点到多点广播场景的缺陷，还克服了基于异或编码的重传方法的性能不稳定、系统开销大的局限。本发明能以较低的编码算法复杂度和系统开销，对各接收节点丢失的原始数据包进行线性网络编码并重传；接收节点用解线性方程组的方法从编码包中解出原始数据包，改善无线广播的重传性能和减少平均重传次数。该方法性能稳定，不受数据包丢失分布的影响，推广应用前景看好。

说明书

技术领域

本发明涉及一种基于随机线性网络编码的无线可靠广播方法，属于无线 通信的技术领域。

背景技术

组播和广播都是从单个数据源向多个目标传送数据报文的技术。该技术广 泛应用于数据分发业务(如视频点播和电视广播)。可靠的多播要求所有用户都 接收到正确的信息后，才终止传输。由于广播通信环境的用户数量众多，差错 控制机制也比点到点通信的复杂得多。  自动请求重传ARQ(Automatic  Repeat-reQuest)方法是通信系统常用的实现差错控制的技术手段。然而，这种 传统的重传方法主要适用于点对点的通信链路，即对出错的数据包逐一重传。 在广播场景下应用传统的ARQ方法效率极低，因为即使只有一个用户未能接收 某个数据包，广播源就必须再次重传该数据包，导致网络吞吐量的急剧下降。

近年来，网络编码(Network Coding)技术已被证明是一种可以有效改善无 线通信系统传输效率的方法。2000年，Ahlswede等首次提出网络编码的概念， 其核心思想是允许网络节点对传输信息进行编码处理；并从理论上证明：如果 允许网络节点对传输的信息按照合适方式进行编码处理，而非限于存储和转发， 则基于该方式的网络多播总能够实现理论上的最大传输容量。

D.Nguyen等人将网络编码和ARQ相结合，提出了基于异或网络编码(XOR  Network Coding)的重传方法，其核心思路是广播源根据广播批次内的数据包在 各个接收节点的接收情况，生成一个接收反馈矩阵，并采用异或网络编码方式 对发送失败的数据包进行异或编码后重传，接收失败的节点在收到该编码包后 进行解码操作，从而解出其丢失的原始数据包。

参见图1，介绍一个典型的无线广播系统模型：该系统设有1个广播源和K 个用户节点(K＞1)，广播源将一组M个数据包(又称为一个广播批次)以设定 时间间隔Δt发送给所有用户节点。每广播完一个数据包，各接收节点都通过控 制帧ACK/NAK将该数据包的接收情况反馈给广播源。

参见图2，介绍广播源依次发送4个数据包P₁，P₂，P₃，P₄给4个用户节点后， 根据各用户节点的反馈而生成的三个数据包接收反馈矩阵的实例，矩阵中的每 个元素V(i，j)(1≤i≤M，1≤j≤K)的值表示节点R_i是否成功接收P_j，如果接收成功， 则V(i，j)＝1，否则为0。以V₁为例，节点R₁接收到P₁、P₂和P₃，节点R₂接收到P₁、 P₂和P₄，节点R₃接收到P₁、P₃和P₄，节点R₄接收到P₂、P₃和P₄。在不计重传损 耗的情况下，若采用传统的重传方法，则广播源要分别重传数据包P₁、P₂、P₃和 P₄，共需4次发送才能完成重传过程。若采用异或网络编码的重传方法，根据 各接收节点的丢包分布情况，广播源可以对这4个数据包进行1次异或编码后 重传，即发送编码包则每个节点均可通过对编码包P和自己 已成功接收的原始包进行异或运算，以解出各自丢失的原始数据包。以节点R₁为例，通过运算可解出丢失的数据包P₄。同理，节 点R₂、R₃、R₄都可以通过异或运算分别解出各自所需的数据包P₃、P₂、P₁。显 然，异或网络编码的重传方法减少了重传次数，具有更高的传输效率。

然而，D.Nguyen并未给出对于任意给定的接收反馈矩阵V，如何合并丢失的 数据包才能使重传次数最少。X.Xiao等人提出了一种基于异或网络编码的无线广 播重传方法NCWBR(Network Coding for Wireless Broadcast Retransmission)。该 方法能够对接收的任何一个反馈矩阵按照设定算法合并丢失数据包。也就是， 广播源先根据广播批次内各数据包的接收情况建立一个接收反馈矩阵V，如果反 馈矩阵V中有元素为0，则进入重传阶段。在重传阶段，广播源又遍历反馈矩阵 V，将每一行中首个为0的元素所对应的数据包进行异或运算后发送；各个接收 节点收到该编码包后，如果能够解码出原始数据包，则广播源根据反馈将反馈 矩阵V中对应位置的元素赋为1，否则，仍然置为0。这样，广播源在这一轮重 传结束后，根据所有接收节点的反馈信息更新反馈矩阵V。广播源重复执行上述 的“遍历反馈矩阵V-选择数据包进行合并-发送编码包-根据接收节点的反馈 信息更新接收反馈矩阵V”的操作步骤，直至反馈矩阵V的元素全部为1。

以图2的右侧反馈矩阵V₂为例，由于该接收反馈矩阵V₂中有元素为0，因此 进入重传阶段时，源节点先遍历该反馈矩阵每行首个0元素，对应的数据包为P₁、 P₂和P₃，生成编码包并发送。各接收节点收到该编码包后，将解码情 况反馈给广播源。在该例中，不计重传损耗，只有R₂可以通过解得P₃，因此经过反馈后，广播源将V₂(2，3)置为1。由于其他节点不能解码，广 播源根据反馈，仍然将相应元素置0(如V₂(1，1)，V₂(1，2))。至此，第一轮重传结 束，源节点根据各节点的解码情况更新了接收反馈矩阵V₂。然后，重复执行上 述的“遍历反馈矩阵V₂-选择数据包进行合并-发送编码包-根据接收节点的反 馈信息更新反馈矩阵”过程，直至反馈矩阵V₂中元素全部为1，该批次的数据包 广播完毕。

以NCWBR为代表的基于异或编码的广播重传方法的优点是解码简单、传 输时延小。但也存在多种缺陷：在每一轮重传的生成编码包阶段，根据接收反 馈矩阵寻找最优编码方案的算法复杂度较高。在每一轮重传结束后，广播源都 要根据各个节点的解码情况更新接收反馈矩阵，这个过程是由各个节点反馈 ACK/NAK控制帧实现的。当系统中存在较多用户时，该过程会消耗大量的控制 帧，带来较大的系统开销。再者，基于异或网络编码的重传方法受到数据包丢 失分布的影响比较大，某个(或某几个)节点的丢包率比较高时，该方法的系 统传输性能会受到严重影响，因此不具备普遍的实用性。

下面以图2中的V₁实例进行说明：各个节点的丢包率都比较低，此时仅需发 送一个编码包就可使所有接收节点都恢复出各自丢失的数据包。 而在V₂实例中，R₃和R₄的丢包率较高，这时根据NCWBR重传方法需要依次重 传P₂，P₃共9个数据包。 可见：这时基于异或编码的重传方法不仅没有体现出优势，反而比普通重传(即 分别重传P₁P₂P₃P₄)还要多传输5个数据包，其传输性能大大降低。

发明内容

有鉴于此，本发明的目的是提供一种基于随机线性网络编码的无线可靠 广播方法LNCR(Linear Network Coding for Retransmission)，该方法不仅解 决了传统重传方法不适用于点到多点广播场景的缺陷，还克服了基于异或编 码的重传方法的性能不稳定、系统开销大的局限。本发明能以较低的编码算 法复杂度和系统开销，对各接收节点丢失的原始数据包进行线性网络编码并 重传；接收节点用解线性方程组的方法从编码包中解出原始数据包，改善无 线广播的重传性能和减少平均重传次数。此外，该方法的性能稳定，不受数 据包丢失分布的影响。

为了达到上述发明目的，本发明提供了一种基于随机线性网络编码的无 线可靠广播方法，其特征在于：先对丢失的数据包进行线性网络编码，然后 重传编码包；各接收节点收到设定数量的编码包后，利用高斯消元法分别求 解各自丢失的原始数据包；该方法将广播数据包的过程划分为下述两个阶段：

第1阶段是广播原始数据包：广播源以设定时间间隔地逐个顺序广播当前批 次内的每个数据包，直至将其中所有数据包都发送完毕；且在广播过程中，若 有数据包丢失，广播源也不立即重传，而继续发送该批次内的下一个数据包；

第2阶段是重传编码包：广播源对所有接收节点丢失的数据包进行线性编码 后发送，接收节点在接收到设定数量的编码包后，通过解码方式从编码包中恢 复出各自丢失的原始数据包。

本发明基于随机线性网络编码的无线可靠广播方法LNCR的创新技术关键 是：利用各个接收节点可解线性方程组的条件，减少反馈帧的数量，即各接收 节点只需要在接收完每组N个编码包后，反馈为使其编码系数矩阵达到满秩仍 需的编码包的数量N_i即可。这样，与基于异或编码的重传方法相比，本发明省 却了频繁的更新接收反馈矩阵、遍历反馈矩阵、确定编码数据包集合的多个环 节，降低了编码的复杂度。因为基于异或编码的重传方法的每一轮都要根据接 收节点的反馈信息，更新接收反馈矩阵并重新确定编码对象集合，复杂度较高； 而本发明方法的编码对象集合始终为该批次内所有节点的丢失数据包集合，并 且编码运算简单。因此，本发明LNCR与基于异或编码的广播重传方法相比较 的主要特点是：有效减少重传次数，改善无线广播的重传性能；而且，编码复 杂度低，性能稳定，减少了接收节点要发送的反馈信号数量，降低了系统开销。

下面具体说明上述各个优点：

(一)LNCR的重传效率更高：在不计重传损耗的情况下，LNCR的重传 次数取决于所有节点中的最大丢包数，且该方法的性能不受数据包丢失分布的 影响。而基于异或编码的重传方法受到数据包丢失分布的影响较大，因此其随 机性也较大，不能完全保证性能，影响了重传效率。

以图2所示的数据包接收反馈矩阵V₂为例，如果采用基于异或编码的 NCWBR方法，需要分别重传P₂、P₃共9个数据包，而采用LNCR方法，在不考虑重传损耗 的情况下，  只需重传3个线性编码包：  Y₁＝g₁₁P₁+g₁₂P₂+g₁₃P₃+g₁₄P₄， Y₂＝g₂₁P₁+g₂₂P₂+g₂₃P₃+g₂₄P₄和Y₃＝g₃₁P₁+g₃₂P₂+g₃₃P₃+g₃₄P₄，就能够使得各接收节点 解析出各自丢失的数据包。

(二)LNCR的编码复杂度较低：在基于异或编码的重传方法中，每一轮 重传结束后，广播源都要根据接收节点的反馈信息，更新接收反馈矩阵，并重 新遍历矩阵，以确定下一轮重传的编码数据包集合。而本发明LNCR方法不需 要每次都对接收反馈矩阵进行遍历，它的编码对象集合始终为各个接收节点丢 包集的并集。因此LNCR省却了频繁的更新矩阵、遍历矩阵、确定编码数据包 的相应操作环节，降低了编码的复杂度。

(三)LNCR减少了控制帧带来的系统开销：基于异或编码的重传方法在 重传阶段，广播源每发送一个编码包，接收节点都要将接收与解码情况反馈给 广播源。在接收节点较多时，由ACK/NAK等控制帧带来的系统开销也是相当 大的。本发明LNCR利用了线性方程组可解的条件，接收节点只需要在接收一 组N个编码包以后，反馈其仍然需要重传的编码包的数量N_i即可。因为在此之 前，肯定有接收节点的编码系数矩阵达不到满秩，即不满足下述公式 的可解性条件：矩阵G的m行向量线性无关。例 如，假设接收节点有K个，如果发送每个编码包也都需要接收节点反馈，则所 需的ACK/NAK控制帧的数量为KN，而本发明LNCR方法只需K个。可见， 本LNCR方法显著减少了ACK等控制帧带来的系统开销。

附图说明

图1是无线广播系统模型示意图；

图2(A)、  (B)、  (C)分别是三个4×4数据包接收反馈矩阵的实施例 示意图。

图3(A)、  (B)分别是图2(B)所示接收节点R₃的原始的编码系数矩 阵示意图和经过矩阵初等变换后的编码系数矩阵示意图。

图4是本发明基于随机线性网络编码的无线可靠广播方法操作流程图。

图5是本发明实施例中接收节点数为4，一组广播包数量为20时的三种 重传方法的平均传输次数随节点丢包率的对比图。

图6是本发明实施例中一个广播批次内数据包数量为20，各节点的丢包 率都为0.2时，三种重传方法的平均传输次数随接收节点数量变化的曲线图。

图7(A)、(B)分别是在低丢包率场景(接收节点数为4，其丢包率都为 0.1)时和高丢包率场景(接收节点数为4，其丢包率分别为p₁＝0.1，p₂＝0.2，p₃＝0.3， p₄＝0.4)时，本发明LNCR方法和NCWBR方法的平均传输次数随批次内广播包 数量的变化曲线图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图和实施例对 本发明作进一步的详细描述。

本发明基于随机线性网络编码的无线可靠广播方法是：先对丢失的数据包进 行线性网络编码，然后重传编码包；各接收节点收到设定数量的编码包后，利 用高斯消元法分别求解各自丢失的原始数据包；该方法将广播数据包的过程划 分为下述两个阶段：

第1阶段是广播原始数据包：广播源以设定时间间隔地逐个顺序广播当前批 次内的每个数据包，直至将其中所有数据包都发送完毕；且在广播过程中，若 有数据包丢失，广播源也不立即重传，而继续发送该批次内的下一个数据包。

第2阶段是重传编码包：广播源对所有接收节点丢失的数据包进行线性编码 后发送，接收节点在接收到设定数量的编码包后，通过解码方式从编码包中恢 复出各自丢失的原始数据包。

参见图4，介绍本发明方法具体操作步骤，其中第1阶段包括下列操作内容：

(11)初始化设置：广播源建立一个K行M列的接收反馈矩阵V，并初始 化设置其中所有元素V_i，j都为0；再初始化设置当前广播批次内的第一个原始数 据包P_i的序号j＝1；每个接收节点R_i也分别建立各自的编码系数矩阵G_i，并初始 化设置G_i为空矩阵；式中，自然数i和K分别是接收节点的序号及其总数，即i 的最大值为K，自然数j和M分别是当前广播批次内的原始数据包的序号及其 总数，即j的最大值为M。

(12)广播源顺序发送当前广播批次内的每个数据包：

先定义该广播批次内的全部共M个数据包构成原始数据包矩阵 P＝[P₁，P₂，...P_j，...，P_M]^T，式中，上标T表示转置矩阵，其中每个数据包P_j表示为 P_j＝g_jP＝[0，0，...，1，0，...，0][P₁，P₂，...，P_j，P_j+1，...，P_M]^T，也就是定义g_j＝[0，0，...，1，0，...，0]为原 始数据包P_j的编码系数向量：只有第j个分量为1、其余分量均为0的单位向量；

广播源以设定时间间隔顺序广播当前批次内的每个数据包P_j，每个接收节 点R_i若正确接收到该数据包P_j，则提取其对应的编码系数向量g_j，并将g_j作为行 向量加入各自的编码系数矩阵G_i中，并向广播源反馈ACK控制帧；否则，仅向 广播源反馈NAK控制帧。

(13)广播源根据接收节点R_i的反馈信息建立接收反馈矩阵V：广播源根据 每个接收节点R_i反馈的ACK或NAK控制帧对其设置的接收反馈矩阵V中各元 素赋值：若是反馈ACK，则将接收反馈矩阵V中的对应元素V(i，j)设置为1；若 是反馈NAK，则将V(i，j)设置为0。

(14)广播源判断该批次内的数据包是否已经全部广播完毕，即j＝M是否 成立；若是，则顺序执行步骤(15)；否则，返回步骤(12)，继续广播下一个 数据包P_j+1。

(15)广播源检测接收反馈矩阵V中是否有元素为0，若是，则继续执行第 2阶段重传编码包的操作；若否，表示该当前批次内的所有数据包已经全被各个 接收节点正确接收，则进入下一批次数据包的广播发送、或者结束广播过程。

本发明方法的第2阶段包括下列操作内容：

(21)广播源根据接收反馈矩阵V确定所有丢失的数据包，并据此确定编 码对象包矩阵：广播源将第1阶段中所有节点丢失的数据包视为需要编码的对 象，并用一个编码对象包矩阵X＝[x₁，x₂，...x_j...，x_M]^T来描述之，以便对其进行编码 处理；该编码对象包矩阵X中的每个元素x_j都取决于下述选择公式： 式中，V(i，j)为接收反馈矩阵V中的第i行第j列元素；该公 式涵义是：若所有接收节点都正确接收该广播批次内的数据包P_j，也就是接收 反馈矩阵V中第j列元素全都为1，则该P_j就不加入编码对象包矩阵X中而设置 x_j＝0；若有接收节点未正确接收P_j、即存在V(i，j)＝0时，则将P_j加入编码对象包 矩阵X中，且设置x_j＝P_j。

(22)广播源根据原始数据包矩阵P对编码对象包矩阵X中的每个元素进行 线性编码处理：  因原始数据包X＝[x₁，x₂，...x_j...，x_M]^T经由下述公式 的线性运算而得到编码对象包矩阵X＝[x₁，x₂，...x_j...，x_M]^T： 式中，M阶系数转换方阵中的每行均为M维的向量，即 h_j＝[h_j1，h_j2，...，h_jM]；其中的分量h_j数值的确定规则是：若x_j＝0，则h_j为M维的0 向量，即h_j＝[0，0，...，0]；否则，如果x_j＝P_j，则h_j为一个第j个分量为1、其余分 量均为0的M维单位向量。

(23)广播源计算所有接收节点中的单个节点的最大丢包数N。

(24)广播源生成编码包并进行重传广播，直至将N个编码包都重传完毕。 该步骤包括下列具体操作内容：

(24A)广播源初始化设置重传的编码包Y的序号k＝1，并按照下述步骤生成 序号为k的编码包：广播源从有限域F_q中随机选取M个编码系数g_k1′，g_k2′，...，g_kM′， 分别对编码对象包矩阵X中的各个元素x₁，x₁，...，x_M进行线性编码，得到编码包 Y_k＝g_k1′x₁+g_k2′x₂+...+g_kM′x_M，即$Y_k=[{g_{k1}}^{\prime },{g_{k2}}^{\prime },...,{g_{\mathrm{kM}}}^{\prime }]\left(\begin{array}{c}{x}_1\\ x_2\\ .\\ .\\ .\\ x_M\end{array}\right)={g_k}^{\prime }X;$式中，F_q为仅含有 限个元素的域，其自然数下标q为该有限域的大小，此处设置q＝2⁸；自然数k为 编码包序号，g_k′＝[g_k1′，g_k2′，...，g_kM′]是基于编码包对象矩阵X的编码系数向量，即 g_k1′，g_k2′，...，g_kM′分别为编码包对象矩阵X中各元素x₁，x₁，...，x_M的加权系数。

(24B)广播源将每个编码包Y_k对应的编码系数向量g_k′按照公式g_k＝g_k′H变换为基 于原始数据包矩阵P的编码系数向量g_k，然后广播发送该编码包Y_k；其中，H是 步骤(22)中的M阶系数转换方阵。

(24C)每个接收节点R_i接收到编码包Y_k后，提取其中的编码系数向量g_k作为行 向量加入自己的编码系数矩阵G_i中。

(24D)广播源判断是否已经将编码包全部发送完毕，即判断k＝N是否成 立；若是，则顺序执行后续步骤(25)；否则，设置k＝k+1后，返回执行步骤(24B)， 继续生成下一个编码包。

(25)每个接收节点R_i分别计算各自编码系数矩阵G_i的秩r_i，并按照公式 $N_i=\left(\begin{array}{c}M-r_i,r_i\le M\\ 0,r_i\ge M\end{array}\right)$计算为使其编码系数矩阵达到满秩，所需要的重传编码包的数 量N_i，并将该数值N_i反馈给广播源。

(26)广播源从每个节点的反馈N_i中选取其中最大值、即按照公式 N＝max_{i∈{1，2，...，K}}N_i来提取最大丢包数值N。

(27)广播源检测N是否为0，若是，表示所有接收节点的编码系数矩阵都 已达到满秩，则各接收节点分别采用公式：计算 求解各自丢失的原始数据包；然后，广播源广播下一批次的数据包、即返回第1 阶段的操作；或者结束广播过程；否则，返回执行步骤(24)。

本发明已经进行了多次实施试验，主要是研究本发明LNCR方法与基于异 或网络编码的NCWBR方法和传统的ARQ重传方法的传输性能分别受到丢包 率、广播包数量和接收节点数量的不同影响，并给出这三种方案的性能对比。

众所周知，衡量重传方法的性能指标是传输一个数据包给所有节点时，所 需要的平均传输次数。

参见图5，该图是在4个接收节点，一组广播包数量为20时的三种重传方 法随节点丢包率的变化曲线，实施例中假设各个节点的丢包率相等。

从图5可以看到，当接收节点的丢包率较低时，这三种重传方法的平均传 输次数比较接近。但随着丢包率增大，LNCR的性能渐渐优于其他两者。这是因 为LNCR会将各个节点丢失数据包进行合并处理，而不是像ARQ方法逐个传输 每个包；另外，不同于NCWBR方法，LNCR重传的编码包的数量决定于丢包 率最高的节点，而且不受各个节点丢失数据包的分布的影响。

参见图6，该图是批次内广播包数量为20，各个节点的丢包率都为0.2时， 三种重传方法的平均传输次数随接收节点数量变化的曲线。

从图中可以看出，当只有两个或较少的接收节点时，本发明方法的性能优 势并不明显。随着节点K的数量增大，优势才显现出来，并愈发显著。这是因 为对于NCWBR来说，随着接收节点数量增多，各节点丢包的分布变得愈加复 杂，而且单个节点不能从XOR包中成功解析出其所需要的原始包的概率变大， 这样就需要更多的编码包。而本发明LNCR方法的平均传输次数主要决定于丢 包率最高的节点。在实施例的仿真场景下，各个节点丢包率相等且恒定，因此 LNCR的平均传输次数并没有太大的增长。

参见图7，该图是在不同场景下的平均传输次数随每个广播批次内数据包个 数N变化的曲线。从两张图中可以看出：NCWBR和LNCR的平均传输次数都 随着N的增大而减小，并且LNCR的性能要优于NCWBR。在低丢包率场景下 (图7(A))，LNCR的优势并不明显；在高丢包率场景下(图7(B))，LNCR的 优势比较明显。这是因为丢包率较低时，只有少量包丢失和需要重传，因此两 种方法要合并的数据包的数量并不多、且概率也较小。但是，在高丢包率场景 下，一方面接收反馈矩阵中为0的元素增多，另一方面各节点丢包的分布变得 愈加复杂，都使得NCWBR需要更多的次数来完成重传。

总之，本发明的仿真实施试验是成功的，实现了发明目的。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本 发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在 本发明保护的范围之内。