CN101714915A

CN101714915A - 一种数据重传方法及系统

Info

Publication number: CN101714915A
Application number: CN 200910237038
Authority: CN
Inventors: 张婧垚; 樊平毅
Original assignee: Tsinghua University
Current assignee: Tsinghua University
Priority date: 2009-11-02
Filing date: 2009-11-02
Publication date: 2010-05-26
Anticipated expiration: 2029-11-02
Also published as: CN101714915B

Abstract

本发明提供了一种数据重传方法和系统，其中的方法具体包括：每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；每发送W个原始数据包，发送端依据接收到的所有接收端的丢包信息，通过网络编码，生成组合包，W为自然数；发送端重传所述组合包。本发明能够用以提高无线广播的数据重传效率。

Description

一种数据重传方法及系统

技术领域

本发明涉及无线通信技术领域，特别是涉及一种用于无线通信中的数据重传方法以及一种数据重传系统。

背景技术

广播操作在无线通信中扮演着非常重要的角色，它不仅是按需路由协议进行路由发现的基础，其自身也可以作为传输单播或多播信息的有效手段。与传统的有线通信相比，无线通信丢包现象较为严重，因而具有较高的比特出错率和传输时延。因此，在无线通信广播中必须采用合适的策略来提高广播操作的可靠性。目前，重传技术常被用来提高传输的可靠性。普通重传技术的思想基于：发送方通过反馈得到接收方的出错情况，重传出错的数据报文以恢复出错的报文。

实际应用中，在低丢包率无线通信广播中，丢失数据包通常分散分布在多个接收节点上。此时，多个接收节点的任意一个节点的丢包都要求源节点重传数据包。这样，现有的重传方法需要多次广播数据包来进行错误处理，需要数量很大的重传次数，且对无线信道的占用率很高，因此需要占用大量带宽，消耗较多的能量，从而影响重传效率。

总之，需要本领域技术人员迫切解决的一个技术问题就是：如何能够提供一种用于无线广播的数据重传方案，用以提高重传效率。

发明内容

本发明所要解决的技术问题是提供一种数据重传方法和系统，用以提高无线广播的数据重传效率。

为了解决上述问题，本发明公开了一种数据重传方法，包括：

每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；

每发送W个原始数据包，发送端依据接收到的所有接收端的丢包信息，通过网络编码，生成组合包，W为自然数；

发送端重传所述组合包。

优选的，所述方法还包括：

建立丢包矩阵，所述丢包矩阵用于存放所有接收端的丢包信息；

所述生成组合包的步骤包括：

接收来自某个接收端的丢包信息；

依据所述丢包信息对所述丢包矩阵进行更新；

每发送W个原始数据包，对所述丢包矩阵进行检测，并在检测到丢包信息时，依据所述丢包信息，通过网络编码，生成组合包。

优选的，所述丢包矩阵的行对应每个接收端，所述丢包矩阵的列对应每个数据包的ID，所述丢包矩阵的初始值为0；

所述丢包信息包括丢包ID；

所述更新丢包矩阵的步骤包括：

在接收到来自第i个接收端的丢包信息时，依据其中的丢包ID，依次将第i行中与该丢包ID对应的元素置1，并将第i行中的其它元素置0。

优选的，所述依据丢包矩阵中丢包信息，通过网络编码，生成组合包的步骤包括：

判断步骤：判断当前丢包矩阵中是否含有非0列，若是，则执行查找步骤，否则，执行组合步骤；

查找步骤：在当前丢包矩阵中查找对应ID最小的非0列，并将所述ID对应的原始数据包作为组合成员；

找到该列中非0元素对应的行，以及这些行中的非0元素对应的列；

划掉这些行和列，以剩下的矩阵作为当前丢包矩阵，并返回判断步骤；

组合步骤：对所述组合成员作模2和，得到组合包。

优选的，所述方法还包括：接收端对收到的组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理。

优选的，所述反馈报告还包括重传成功信息；

所述更新丢包矩阵的步骤包括：

在接收到来自第i个接收端的反馈报告时，检查该反馈报告的内容，若为丢包信息，则依据其中的丢包ID，依次将第i行中与该丢包ID对应的元素置1，并将第i行中的其它元素置0；

若为重传成功信息，则将第i行的元素全部置0。

优选的，所述每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告的步骤包括：

初始化步骤：预置检测参数a＝0；

接收步骤：在接收一个数据包时，如果该数据包是未曾收到过的原始数据包，则令a＝a+1；

暂停步骤：如果a＜K，则返回接收步骤，否则，令a＝0，并执行检测步骤；

检测步骤：判断收到的所有数据包的ID是否连续，若是，则返回接收步骤，否则，执行反馈步骤；

反馈步骤：从收到的所有数据包中找到丢包信息，并将所述丢包信息以反馈报告的形式反馈到发送端。

本发明实施例还公开了一种数据重传系统，包括：

检测和反馈模块，用于每收到K个原始数据包，进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；

组合包生成模块，用于每发送W个原始数据包，依据接收到的所有接收端的丢包信息，通过网络编码，生成组合包，W为自然数；

重传模块，用于重传所述组合包。

优选的，所述系统还包括：

建立模块，用于建立丢包矩阵，所述丢包矩阵用于存放所有接收端的丢包信息；

所述组合包生成模块包括：

第二接收单元，用于接收来自某个接收端的丢包信息；

更新单元，用于依据所述丢包信息对所述丢包矩阵进行更新；

组合单元，用于每发送W个原始数据包，对所述丢包矩阵进行检测，并在检测到丢包信息时，依据所述丢包矩阵中的丢包信息，通过网络编码，生成组合包。

优选的，所述系统还包括：

解码模块，用于对收到的组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理。

优选的，所述检测和反馈模块包括：

初始化单元，用于预置检测参数a＝0；

第一接收单元，用于在接收一个数据包时，如果该数据包是未曾收到过的原始数据包，则令a＝a+1；

暂停单元，用于在a＜K时，返回第一接收单元，否则，令a＝0，并执行检测单元；

检测单元，用于判断收到的所有数据包的ID是否连续，若是，则返回第一接收单元，否则，执行反馈单元；

反馈单元，用于从收到的所有数据包中找到丢包信息，并将所述丢包信息以反馈报告的形式反馈到发送端。

与现有技术相比，本发明具有以下优点：

本发明将网络编码减少无线传输信息量的特性应用在无线网络广播重传中，采用定期反馈的方式在发送端和多个接收端之间交流丢包情况，将多个待重传的数据包，用网络编码的方式组合起来广播给所有的接收端，达到用一个时隙重传多个数据包的目的，从而实现提高重传效率的目的；

再者，本发明采用丢包矩阵来存放所有接收端的丢包信息，并在依据所述丢包信息生成组合包时遵循如下策略，即对任一个接收端R_i而言，每个组合包最多含有一个R_i的丢包，因此，只要该组合包与R_i的丢包有关，就能够保证R_i能从收到的组合包中解出自己所需的丢包；

此外，本发明采用模2和来生成和解析组合包，运算和操作简单，对硬件和操作系统没有任何特殊要求。

附图说明

图1是本发明一种广播数据包的包头格式；

图2是本发明一种数据重传方法实施例1的流程图；

图3是本发明一种数据重传方法实施例2的流程图；

图4是本发明一种一对多的无线广播传输示例；

图5是本发明一种丢包矩阵示例；

图6是本发明一种发送端基于所述丢包矩阵进行重传工作的流程图；

图7是本发明一种反馈报告FP的格式；

图8是本发明一种数据重传方法实施例3的流程图；

图9是本发明一种数据重传系统实施例的结构图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

在实际中，网络编码通过允许对来自不同链路的信息进行编码组合，使得网络节点既实现路由功能又实现编码功能，从而提高网络性能。在网络编码这种全新的体系结构下融合了编码和路由的概念，网络性能可以达到最大流传输的理论极限。因此，无线链路的不可靠性和物理层的广播特性非常适合使用网络编码的方法。

综上分析，本专利发明人创造性地提出了本发明实施例的核心构思之一，即利用无线传输介质的广播特性，将多个待重传的数据包，用网络编码的方式组合起来广播给所有的接收端，达到用一个时隙重传多个数据包的目的，从而最大限度地提高重传效率。

为了清楚地说明本发明重传方案的实现过程，首先引入如下符号：

R_i，i＝1，2，...，M：M个接收端；

BPH：Broadcast Packet Head，广播数据包的包头；

FP：Feedback Packet，接收端向发送端发送的反馈报告；

ACK，NACK：如果接收端所有的丢包都已被成功地重传，此时其发送的FP称为ACK，如果接收端还有没收到的丢包，其发送的FP称为NACK。

D_j，j＝1，2，3，...：发送端广播的原始数据包(非组合包)；

L_j，j＝1，2，3，...：数据包D_j的长度(字节数)；

l：组合包中包含的数据包的个数；

Σ_{k = 1}^{l} &CirclePlus; D_{j_{k}} = D_{j_{1}} &CirclePlus; D_{j_{2}} &CirclePlus; . . . &CirclePlus; D_{j_{l}}

表示l个数据包的模2和，如果这l个数据包的长度不一致，则在短数据包后面补零，使之与长数据包对齐。例如数据包D₁为1111，D₂为01，则在D₂后补零，使之变为0100，结果为

D_{1} &CirclePlus; D_{2} = 1011 .

P_i：发送端到接收端R_i的丢包率。

参考图1，示出了本发明一种广播数据包的包头(BPH)格式。BPH的第一个字节用来表示该包是否为组合包以及包含多少个原始数据包。如果l＝1，表示非组合包；如果l＞1，表示该包是组合包，并且里面包含l个原始数据包。包头后面的部分包括l个6字节的段，每段包含两个部分，其中前4个字节表示原始数据包的编号(ID)，这里用j_i表示，后2个字节表示表示数据包

的长度。值得注意的是，根据上面提到的“补零”原则，整个数据包(加上包头)的长度为

1 + 6 l + \max_{i = 1}^{l} L_{j_{i}} .

参照图2，示出了本发明一种数据重传方法实施例1的流程图，具体可以包括：

步骤201、每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；

除了接收数据包以外，每个接收端还应定期向发送端反馈丢包情况。为了减轻反馈信道的负载，本发明并不采用一包一反馈的方式，而是每收到K个原始数据包检查一下当前是否有丢包。如果有丢包，就发送一个FP，集中反馈当前的丢包情况NACK；如果没有丢包，则不作反馈。这样可以大大减轻链路的负担，提高能量和带宽效率。K的值可由每个接收端设定，每个接收端可以不同。为了能及时将丢包情况反馈给发送端，其值不能过大，对于接收端R_i，以K＜1/P_i为宜。

由于BPH里包含数据包的ID，并且数据包是用整数按顺序编号的，因此，接收端可以根据收到的数据包ID是否连续来判定有没有丢包。在本发明的一种优选实施例中，所述接收端的检测和反馈步骤可以通过以下子步骤来实现：

初始化子步骤A1：预置检测参数a＝0；

接收子步骤A2：在接收一个数据包时，如果该数据包是未曾收到过的原始数据包，则令a＝a+1；

暂停子步骤A3：如果a＜K，则返回接收步骤，否则，令a＝0，并执行子步骤A4；

检测子步骤A4：判断收到的所有数据包的ID是否连续，若是，则返回子步骤A2，否则，执行子步骤A5；

反馈子步骤A5：从收到的所有数据包中找到丢包信息，并将所述丢包信息以反馈报告的形式反馈到发送端。

步骤202、每发送W个原始数据包，发送端依据接收到的所有接收端的丢包信息，通过网络编码，生成组合包，W为自然数；

与接收端类似，发送端也并非一发现丢包就启动重传。为了提高效率，我们采用如下策略。发送端每发送W个原始数据包后，检查一下收到的反馈报告，如果有需要重传的数据包，就启动编码重传。与接收端类似，W不宜过大，以避免待重传包无限制堆积。在

Σ_{i = 1}^{M} P_{i} < 1

的情况下，要求

W < 1 / Σ_{i = 1}^{M} P_{i} .

步骤203、发送端重传所述组合包。

在具体实现中，发送端可以基于数字喷泉码实现所述组合包的重传。所谓数字喷泉码，是指该种编码可以由k个原始数据分组生成任意数量的编码分组，而接收方只要收到其中任意m个编码分组，即可通过译码以高概率成功恢复全部原始数据分组。其中，k，m为自然数，一般情况下，m＞k。上述编码过程如同源源不断产生水滴(编码分组)的喷泉(编码器)，而只要用杯子(译码器)接收足够数量的水滴，即可达到饮用(成功译码)的目的。基于喷泉码的解决方案由于单向组播没有反馈，接收端增长对于发送端来说没有任何影响，具有很强的健壮性。因此，采用数字喷泉码技术，在一个时隙内，可以向多个接收端同时重传多个数据包，因此重传效率大大提高。

本发明的重传方案，采用定期反馈的方式在发送端和多个接收端之间交流丢包情况，能够在保证灵活性的同时，尽量减少信令开销和运算复杂度。

参照图3，示出了本发明一种数据重传方法实施例2的流程图，具体可以包括：

步骤301、每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；

步骤302、建立丢包矩阵，所述丢包矩阵用于存放所有接收端的丢包信息；

步骤303、接收来自某个接收端的丢包信息；

步骤304、依据所述丢包信息对所述丢包矩阵进行更新；

本实施与实施例1的区别在于，发送端采用丢包矩阵来存放所有接收端的丢包信息，具体而言，每接收到来自某个接收端的丢包信息，就对所述丢包矩阵进行更新。

在本发明的一种优选实施例中，所述丢包矩阵的行可以对应每个接收端，所述丢包矩阵的列可以对应每个数据包的ID，所述丢包矩阵的初始值可以为0；

所述丢包信息可以包括丢包ID；

所述更新丢包矩阵的步骤可以包括：

步骤305、每发送W个原始数据包，对所述丢包矩阵进行检测，并在检测到丢包信息时，依据丢包信息，通过网络编码，生成组合包；

在掌握丢包情况后，发送端的下一步工作是组合包的生成。如何选取重传数据包并生成组合包是整个重传方案的关键所在。

参考图4，示出了本发明一种一对多的无线广播传输示例。设发送端S通过无线广播链路向M个接收端R₁，R₂，...，R_M发送一系列数据包，并按发送顺序用数字1，2，3，...对这些数据包进行编号。由于信道衰落等原因，某些数据包不能正确到达某些接收端，也即发生丢包现象。因此，为了保证传输的可靠性，需要发送端及时了解到接收端的丢包情况，并由发送端进行必要的重传。在图1的示例中，接收端R₁丢失了数据包1，接收端R₂丢失了数据包3。注意到R₁正确接收到了数据包3，而R₂正确接收到了数据包1。如果把每个数据包看成由有限域元素组成的矢量，并对用该矢量表示的数据包1和3作线性组合(例如模2和)，生成一个新的组合包，然后广播出去，那么接收端R₁接收到该组合包后，由于R₁先前已收到过数据包3，R₁可以利用数据包3和组合包，通过线性变换将自己所需的数据包1从组合包中解出来。例如，如果组合包是通过对数据包1和3作模2和生成的，那么R₁只需要对组合包和数据包3作模2和，就可以得到数据包1。同理，R₂也可以用类似的方式从组合包中解出其所需的数据包3。可见，本发明采用这种“编码-广播”的方式，仅用1个时隙(传输1个数据包的时间)，就能将丢失的两个数据包重传给不同的接收端，从而能够最大限度地节省系统资源。

从上述示例可以看出，参与线性组合的数据包数目并不限于2个，可以为1(l为＞2的自然数)个。只要目标接收端R_i已知其中的l-1个，就可以按照上述线性变换的方式解出自己丢失的那个包。如果R_i已知的数据包数目为k＜l-1个，那么R_i将无法解出自己丢失的数据包。根据高斯定理，R_i至少需要再接收l-1-k个组合包(或原始数据包)才能解出所有的丢包。这样R_i需要将收到的组合包暂存，直到能解出丢失的数据包为止。但如此一来，势必会占用大量的存储空间，而且运算过程非常复杂。

针对上述困难，为简洁起见，本发明的重传方案遵循如下原则，即对任一个接收端R_i而言，每个组合包最多含有一个R_i的丢包。这样就保证了R_i每接到一个组合包，只要该组合包与R_i的丢包有关，R_i总能从中解出一个自己的丢包。在这一原则基础上，可以将数据包看成由1和0排列成的矢量，然后用2元域上的非零线性组合，即模2和来生成组合包。在接收端，同样可以用模2和“消去”已知的数据包，解出所需的丢包。相比多元域GF(q)(q＞2)上的线性组合，模2和明显简单许多。因此，在本发明中，可以采用模2和来生成和解析组合包。

为满足这一原则，对应上述优选实施例，本发明的步骤305可以通过以下子步骤实现：

判断子步骤B1：判断当前丢包矩阵中是否含有非0列，若是，则执行子步骤B2，否则，执行子步骤B3；

查找子步骤B2：在当前丢包矩阵中查找对应ID最小的非0列，并将所述ID对应的原始数据包作为组合成员；

划掉这些行和列，以剩下的矩阵作为当前丢包矩阵，并返回子步骤B1；

组合子步骤B3：对所述组合成员作模2和，得到组合包。

步骤306、发送端重传所述组合包。

为使本领域技术人员更好地理解本发明，以下以图5所示的本发明一种丢包矩阵为例，对发送端的工作过程进行说明。

该丢包矩阵G_M×N的大小为M×N，其中M为接收端的数目，N是窗口长度，其第i行第j列元素用g_ij表示，g_ij＝1表示接收端R_i丢失了数据包D_j+kN(k为0或正整数，大小由当时所处的窗口期决定)，反之g_ij＝0说明说明R_i已经正确接收到了D_j+kN。这样数据包D_j的丢失情况可以由G_M×N第(j-1)modN+1列完全反映出来。从中也可以看出，G_M×N最多只能同时显示N个包的丢失情况。N的大小根据实际需要确定，N应该足够大，使得第j个包发出之后，并且j＞N时，第j-N个包的重传(如果需要重传的话)已经成功进行完，也就是说窗口期必须足够长以容纳同一时期所有的丢包信息。

参考图6，示出了本发明一种发送端基于所述丢包矩阵进行重传工作的流程，具体可以包括以下：

步骤601、接收来自某个接收端的FP，所述FP中包括丢包ID；

步骤602、如果FP中含有ID_j，则g_{i((j-1)modN+1)}＝1，否则g_{i((j-1)modN+1)}＝0；

步骤603、每发送W个原始数据包，判断G_M×N中是否含有非0列，若是，则步骤604，否则，执行步骤607；

步骤604、在G_M×N中查找对应ID最小的非0列，将该列作为组合成员设其对应的ID值为j₁，则将IDj₁作为组合成员；

步骤605、找到该列中非0元素对应的行，以及这些行中的非0元素对应的列；

假设

共m₁个接收端丢失了

需要重传，则确定j₁列中非0元素对应的行i₁，i₂，...，i_m1，并找到i₁，i₂，...，i_m1行中的非0元素对应的列；

步骤606、划掉这些行和列，以剩下的矩阵作为当前丢包矩阵，并返回步骤603；

例如，划掉行i₁，i₂，...，i_m1和对应的列，以剩下的矩阵作为当前丢包矩阵。

步骤607、对所述组合成员作模2和，得到组合包；

所述组合包可以用下公式计算：

D_{z} = Σ_{i = 1}^{l_{m}} &CirclePlus; D_{j_{i}};

例如，从G_M×N中可以看出，R₁丢失了D₁，D₂，D₃三个数据包，R₄丢失了D₁，D₅两个数据包，因此，我们将第1行和第4行，第1、2、3、5列从G_M×N中划掉。剩下的矩阵中，第4列是非0列。因此最后得到的组合包：

D_{z} = D_{1} {&CirclePlus; D}_{4}

步骤608、重传所述组合包。

在实际中，可以按图1的格式为组合包D_z加上包头，并广播出去。

本实施例采用丢包矩阵来存放所有接收端的丢包信息，并在依据所述丢包信息生成组合包时遵循如下策略，即对任一个接收端R_i而言，每个组合包最多含有一个R_i的丢包，因此能够保证R_i每接到一个组合包，只要该组合包与R_i的丢包有关，R_i总能从中解出一个自己所需的丢包。

此外，本实施例采用模2和来生成和解析组合包，运算和操作简单，对硬件和操作系统没有任何特殊要求。在实施时，可以很方便地集成到各种无线MAC层协议中，为有可靠性要求的广播会话提供服务，也可以编成动态链接库，由应用程序在需要时调用。

在实际应用中，除了原始数据包外，接收端接收的数据包还会包括重传的组合包，在这种情况下，接收端还可以对收到的组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理。

例如，组合包

D_{z} = Σ_{i = 1}^{l_{m}} &CirclePlus; D_{j_{i}},

其中

是R_i丢失的包，l_m是该组合包中包含的原始数据包数，则可通过如下的模2和运算得到原始数据包

D_{j_{k}} = (Σ_{i = 1}^{l_{m}} &CirclePlus; D_{j_{i}}) &CirclePlus; ({\underset{i = 1}{Σ}}_{i &NotEqual; k}^{l_{m}} &CirclePlus; D_{j_{i}})

相应地，如果接收端所有的丢包都已被成功地重传，此时，其发送的反馈报告FP中还可以包括重传成功信息，这里用ACK表示。参考图7示出了本发明一种反馈报告FP的格式。第一个字节表示该FP是ACK还是NACK。如果n＝0，表示该FP是个ACK；如果n＞0，表示该FP是个NACK，并且当前有n个丢包需要重传。后面用n个四字节的段分别表示n个需要重传的丢包的ID。因此，整个FP的长度为1+4n。

在上述情况下，发送端依据反馈报告FP中的具体信息对丢包矩阵进行更新时，所述更新丢包矩阵的步骤可以包括：

子步骤C1、在接收到来自第i个接收端的反馈报告时，检查该反馈报告的内容，若为丢包信息，则依据其中的丢包ID，依次将第i行中与该丢包ID对应的元素置1，并将第i行中的其它元素置0；

子步骤C2、若为重传成功信息，则将第i行的元素全部置0。

此外，为了实现重传工作，每个接收端可以维护一个缓存队列，以便于将收到的原始数据包按照ID顺序插到队列里。同理，发送端也需要一个缓存队列，将发送过的原始数据包按ID顺序存入队列。为简单起见，以下将数据包依ID顺序存入队列成为“入队”，将删除队列头部数据包称为“出队”。

参考图8，示出了上述队列情况下，本发明一种数据重传方法实施例3的流程图，其中，接收端的工作流程具体可以包括：

第一初始化步骤801：预置第一检测参数a＝0，i＝0，初始化接收缓存队列；

第一接收步骤802：在接收一个数据包时，如果该数据包是未曾收到过的原始数据包，则令a＝a+1，并将该数据包入队；

如果该数据包是重传的组合包，则对所述组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理，否则，将该原始数据包插入队列；

暂停步骤803：如果a＜K，则返回步骤802，否则，令a＝0，并执行步骤804；

检测步骤804：从头到尾检查缓存队列中的数据包，如果检查到数据包ID不连续，则令i＝1，然后执行子步骤851；

如果检查到数据包ID连续，且i＝1，则令i＝0，并执行子步骤852；

如果检查到数据包ID连续，且i＝0，则返回第一接受步骤802。

反馈步骤805：

第一反馈子步骤851：从缓存队列中的所有数据包中找到丢包信息，并将所述丢包信息以NACK的形式反馈到发送端；

第二反馈子步骤852：向发送端反馈ACK；

相应地，发送端的工作流程可通过以下步骤来实现：

第二初始化步骤806、预置第二检测参数a′＝0，初始化发送缓存队列，建立丢包矩阵G_M×N，其元素初始值为0；

数据通信步骤807，可以包括：

发送子步骤871、发送一个原始数据包，令a′＝a′+1，并将该数据包入队，如果a′＜W，则重复步骤871，否则，令a′＝0，执行步骤808；

接收子步骤872、

接收来自R_i的FP；

如果该FP为ACK，则将G_M×N的第i行全部置0；如果该FP为NACK，且NACK中含有IDj，则g_{i((j-1)modN+1)}＝1，否则g_{i((j-1)modN+1)}＝0；

如果G_M×N的第j列是全0列，设该列对应数据包D_j+kN，那么若对应数据包ID＜j+kN的所有列均为全0列，则D_j+kN和之前所有的数据包出队；

检查步骤808、检查G_M×N，如果有需要重传的包，则图6所述方法生成组合包并广播出去；

清理步骤809：检查发送缓存队列长度，如果长度Q＞T，则删除队列头部Q-T个包。

在实际中，发送端还需要定期清理发送缓存队列中的无用包，以免在长时间未收到FP时，缓存队列变得过长。这里采用的策略是，每发送W个数据包检查一下缓存队列长度，必要时删除队列头部的若干包，使得队列长度总是小于等于一个设定值T。T的大小可根据实际情况设定，要求T＞N以保证所有丢包都能被正确地重传。

在以上的实现方案中，有几个问题需要注意：

1)在BPH和FP中，均用4个字节来表示一个数据包ID，这样发送4294967295个包以后，ID会发生溢出。应对的办法是在溢出时，ID号重新置为0。

2)BPH中用2个字节表示数据包的长度，这要求每个数据包的长度不能大于65535。为了控制丢包率，无线传输的包长一般都能满足这个要求。

3)与发送端一样，接收端也需要定期清理缓存队列中的无用包以节省空间。因为接收端可能接收到组合包，缓存队列里必须保存一定数量的数据包用于解码。接收端可以通过收到的BPH来判断哪些包已经过期。设j_min是BPH所包含的最小ID，即

j_{\min} = \min_{i = 1}^{m} j_{i}

那么根据组合包的生成过程，可以断定所有ID小于j_min的数据包都已经被所有R_i正确接收，以后发的组合包里不会再出现这些数据包了，因此，也就可以出队了。

参考图9，示出了本发明一种数据重传系统实施例的结构图，具体可以包括：

检测和反馈模块901，用于每收到K个原始数据包，进行丢包检测，并在检测到丢包时，向发送端发送反馈报告，所述反馈报告包括该接收端的丢包信息，K为自然数；

由于BPH里包含数据包的ID，并且数据包是用整整数按顺序编号的，因此，接收端可以根据收到的数据包ID是否连续来判定有没有丢包。在本发明的一种优选实施例中，所述检测和反馈模块可以包括：

初始化单元911，用于预置检测参数a＝0；

第一接收单元912，用于在接收一个数据包时，如果该数据包是未曾收到过的原始数据包，则令a＝a+1；

暂停单元913，用于在a＜K时，返回第一接收单元，否则，令a＝0，并执行检测单元；

检测单元914，用于判断收到的所有数据包的ID是否连续，若是，则返回第一接收单元，否则，执行反馈单元；

反馈单元915，用于从收到的所有数据包中找到丢包信息，并将所述丢包信息以反馈报告的形式反馈到发送端。

在具体实现中，所述检测和反馈模块801可以位于接收端内部，也可以作为一个独立的模块位于接收端外，本发明对此不加以限制。

组合包生成模块902，用于每发送W个原始数据包，依据接收到的所有接收端的丢包信息，通过网络编码，生成组合包，W为自然数；

在本发明的另一种优选实施例中，采用丢包矩阵来存放所有接收端的丢包信息，因此，所述系统还可以包括：

建立模块904，用于建立丢包矩阵，所述丢包矩阵用于存放所有接收端的丢包信息；

在这种情况下，所述组合包生成模块902可以包括：

第二接收单元921，用于接收来自某个接收端的丢包信息；

更新单元922，用于依据所述丢包信息对所述丢包矩阵进行更新；

组合单元923，用于每发送W个原始数据包，对所述丢包矩阵进行检测，并在检测到丢包信息时，依据所述丢包矩阵中的丢包信息，通过网络编码，生成组合包。

重传模块903，用于重传所述组合包。

在具体实现中，所述模块902-904可以位于发送端内部，也可以作为一个独立的模块位于接收端外，本发明对此不加以限制。

在实际应用中，除了原始数据包外，接收端接收的数据包还会包括重传的组合包，在这种情况下，所述系统还可以包括：

解码模块905，用于对收到的组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理。

本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。对于装置实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

以上对本发明所提供的一种数据重传方法和一种数据重传系统，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims

1.一种数据重传方法，其特征在于，包括：

发送端重传所述组合包。

2.如权利要求1所述的方法，其特征在于，还包括：

所述生成组合包的步骤包括：

接收来自某个接收端的丢包信息；

依据所述丢包信息对所述丢包矩阵进行更新；

3.如权利要求2所述的方法，其特征在于，所述丢包矩阵的行对应每个接收端，所述丢包矩阵的列对应每个数据包的ID，所述丢包矩阵的初始值为0；

所述丢包信息包括丢包ID；

所述更新丢包矩阵的步骤包括：

4.如权利要求3所述的方法，其特征在于，所述依据丢包矩阵中丢包信息，通过网络编码，生成组合包的步骤包括：

组合步骤：对所述组合成员作模2和，得到组合包。

5.如权利要求1所述的方法，其特征在于，还包括：接收端对收到的组合包进行解码，得到原始数据包，若该原始数据包已存在，则丢弃处理。

6.如权利要求3所述的方法，其特征在于，所述反馈报告还包括重传成功信息；

所述更新丢包矩阵的步骤包括：

若为重传成功信息，则将第i行的元素全部置0。

7.如权利要求1所述的方法，其特征在于，所述每收到K个原始数据包，接收端进行丢包检测，并在检测到丢包时，向发送端发送反馈报告的步骤包括：

初始化步骤：预置检测参数a＝0；

8.一种数据重传系统，其特征在于，包括：

重传模块，用于重传所述组合包。

9.如权利要求8所述的系统，其特征在于，还包括：

所述组合包生成模块包括：

第二接收单元，用于接收来自某个接收端的丢包信息；

10.如权利要求9所述的系统，其特征在于，还包括：

11.如权利要求8所述的系统，其特征在于，所述检测和反馈模块包括：

初始化单元，用于预置检测参数a＝0；