无线局域网内组播场景中最小丢包重传方法

(19)中华人民共和国国家知识产权局(12)发明专利说明书(10)申请公布号CN104219032A

(43)申请公布日2014.12.17(21)申请号CN201410407682.8(22)申请日2014.08.19(71)申请人北京邮电大学地址100876北京市海淀区西土城路10号(72)发明人谢刚杨亚霖高锦春刘元安胡碧波刘凯明刘芳袁东明(74)专利代理机构北京同恒源知识产权代理有限公司代理人张水俤(51)Int.CI H04L1/18权利要求说明书说明书幅图(54)发明名称 无线局域网内组播场景中最小丢包重传方法(57)摘要 本发明公开了一种无线局域网内组播场景中最小丢包重传方法，主要用于解决具有反馈链路的组播场景中的丢包恢复问题。该方法特征为：在多个用户同时向一个AP请求相同数据传输服务的组播场景中，AP在接收到所有用户反馈的丢包信息后，先根据本发明中的编码方法生成一个编码矩阵，然后再将编码矩阵与原始数据包进行比特按位异或形成组合重传包，用户在收到组合重传包后根据本发明中的解码方法进行相应地异或解码恢复出丢包。该方法可以将多播场景中AP每次发送的重传包的数量降到理论下限。法律状态法律状态公告日法律状态信息法律状态

权利要求说明书1.无线局域网内组播场景中最小丢包重传方法，其特征在于：

组播网络中AP同时为P个用户服务，广播N个原始数据包；

每个用户分别生成接收状态向量，并向AP反馈丢包情况，其中单个用户 丢失的数据包数量至多为K；

AP根据P个用户反馈的丢包情况生成一个P×N的丢包信息统计矩阵；AP 生成一个N×K的编码矩阵，其中编码矩阵中的每一列代表一个重传数据包的组 合情况，所有用户的丢包序号与编码矩阵相对应的行向量形成的子矩阵满秩，且 不影响其他子矩阵的秩；AP将生成的编码矩阵与原始数据包进行比特按位异或， 得出组合重传包并向P个用户进行广播；

每个用户分别接收所述组合重传包，并将所述组合数据包与该用户已正确接 收到的数据包进行异或解码，恢复出所丢失的数据包。

2.根据权利要求1所述的方法，其特征在于，该方法适用于具有反向反馈 链路的无线多播系统。

3.根据权利要求1所述的方法，其特征在于所述编码矩阵的生成具体包括 以下步骤：

步骤101：从编码矩阵M中提取第i号用户的子矩阵SM；具体地，从丢 包矩阵表中查得第i号用户丢包序号，从编码矩阵M中提取出丢包序号对应 的行向量组合成该用户的编码子矩阵SM；

步骤102：计算SM的行数r、列数c和秩rank；如果rank等于0则进 行步骤103；如果0<rank<r则进行步骤104；否则进行步骤113；

步骤103：将SM赋值为单位阵，根据SM更新M相应的行向量；

步骤104：判断子矩阵SM是否有全零行zr和全零列zc；是则进行步骤 105，否则进行步骤106。

步骤105：将SM内第一个全零行和第一个全零列交叉处的元素值置1， 进行步骤111。

步骤106：令j＝1，其中j是子矩阵SM的列号；

步骤107：将SM第j列中的零值置1，并重新计算秩rank；

步骤108：判断rank是否增加，是则进行步骤110，否则进行步骤109。

步骤109：令j＝j+1，返回步骤107。

步骤110：判断是否影响其他用户的秩，是则进行步骤109，否则进行 步骤111；

步骤111：更新M和SM；具体地，根据SM更新M相应的行向量。

步骤112：判断更新后的子矩阵SM的秩rank的大小是否等于r；如果 等于则进行步骤113，否则进行步骤114。

步骤113：判断i是否大于用户总数；是则结束，否则进行步骤114。

步骤114：令i＝i+1。

4.根据权利要求3所述的方法，其特征在于，所述不影响其他子矩阵的 秩的判断步骤包括：

步骤201：查看步骤107中置1的数值所对应的数据包编号m；

步骤202：找出所述丢包信息统计矩阵含有m的所有用户的集合S，以及 S中用户总数k。

步骤203：令u＝1，jump＝1；u代表S内的用户编号；jump是程序的返 回值；

步骤204：提取用户u对应的子矩阵SM，计算其行值h和秩rank；

步骤205：判断rank＝h是否成立，是则进行步骤207，否则进行步骤206；

步骤206：令jump＝-1；

步骤207：判断u＝k是否成立，是则进行步骤209，否则进行步骤208；

步骤208：令u＝u+1；

步骤209：返回jump的值；其中，jump的值为1，则不影响其他子矩阵 的秩；jump的值为-1，则影响其他子矩阵中至少一个子矩阵的秩。

5.根据权利要求1所述的方法，其特征在于，所述进行异或解码包括以 下步骤：

步骤301：用户生成接收状态向量并反馈丢包；其中，如果正确接收到 原始数据包i，则将接收状态向量中第i个值置1，否则置0；

步骤302：用户统计接收到的AP所发送的异或组合包总个数，K的初始 值置为该异或组合包总个数；

步骤303：判断组合包包头是否含有接收状态向量中置0的包号，是则 进行步骤305，否则进行步骤304；

步骤304：丢弃该组合包，更新K；

步骤305：令j＝1，其中j代表当前的异或组合包序号；

步骤306：将组合包j与已正确接收的数据包异或，并修改组合包包头； 具体地，将组合包中包头标志位为1且接收状态向量中置1的已正确接收的 数据包与组合包异或，并将包头标志位中参与异或的数据包的包头标志位置 0；

步骤307：判断当前组合包包头标志位是否只有一个1，是则进行步骤 308，否则进行步骤310；

步骤308：将当前组合包包头标志位对应的数据包的接收状态向量的值 置1，并令K＝K-1；

步骤309：判断K＝0是否成立，是则进行步骤312，否则进行步骤305；

步骤310：判断j＝K是否成立，是则进行步骤312，否则进行步骤311；

步骤311：令j＝j+1；

步骤312：判断接收状态向量是否有0值，是则进行步骤313，否则进 行步骤314；

步骤313：检查接收状态向量中的0值，并反馈丢包信息；

步骤314：反馈ACK。

说明书<p>技术领域

本发明属于无线通信技术领域，特别涉及一种具有反馈链路的组播场景丢包 恢复中生成最少数量重传包的方法。

背景技术

信息高效可靠传输问题是任意通信系统都需要研究的重要问题。很多应用要 求完全可靠的传输数据，即不能有数据包的丢失，例如文件传输，财务应用，电 子邮件，远程主机访问等应用。丢失文件数据或财务交易数据的后果严重。与有 线网络相比，在无线通信网络中，有很多因素例如衰落、干扰、多径效应和碰撞 会导致无线传输丢包率增高，这就增加了传输的开销，而这种开销在无线组播场 景中是比较严重的。目前，无线传输系统中都是采用直接重传的方式，即每个用 户丢什么包就向该用户重传该包。例如在一个AP同时为三个用户服务的组播系 统中，AP广播了三个数据包P1、P2和P3，用户一丢失P1，用户二丢失P2，用 户三丢失P3，根据现有802.11机制需要向用户一重传P1，向用户二重传P2， 向用户三重传P3，所以AP需要广播三个重传包。当组播网络内用户增加，链路 状况的差异会造成各个用户丢包不同且极度分散，尤其是在高密度情况下，传统 的丢包恢复机制会导致重传包的数量极大，严重的增加了系统的开销，传输效率 大大降低。当信道条件很差或者网络很拥堵的情况下，这样极低的传输效率会导 致重传次数增加，时延加大，甚至传输失败。因此，对无线传输系统组播场景下 的丢包恢复进行最优化研究无疑具有重要意义。

近些年提出了一种基于网络编码的组播重传方法，AP只需要重传一个数据 包，即将P1、P2和P3进行异或组合操作形成异或组合包Q。用户一将Q与已正 确接收到的P2、P3进行异或解码则可以恢复出丢包P1，同理用户二和用户三也 能以相应的方式恢复出各自丢包。许多无线传输系统中基于网络编码的组播重传 策略的研究已经开展。Nguyen等人和Tran等人在《Wireless

Broadcast

Using

Network

Coding》提出了一种无线组播中基于网络编码的丢包重传策略，发送节 点根据接收节点反馈的丢包信息，机会的选择不同接收节点丢失的数据包进行编 码，进而使得不同的接收节点在正确接收到编码重传数据包后，能恢复出其丢失 的数据包。然而这种方法灵活性不好，不能在无线多播场景下根据各个接收节点 的实际情况发送其需要的重传数据包，仅仅将一个无线多播数据帧内的所有数据 包先按照一定方式进行编码再广播给所有接收节点，对于丢包较少的接收节点， 会接收到大量多余的重传数据包。中南大学肖潇等人在《一种低丢包率无线网络 中基于网络编码的广播重传方法》和《基于网络编码的无线网络广播重传方法》 中提出了基于网络编码的无线网络广播重传方法(BRANC),对将每个用户的i 号丢包异或组合形成重传包依次发送，如果无法恢复出丢包则更换组合方式再次 发送。使用该方法不能保证系统内重传包数量最低，而且重传次数较多。在某些 特殊丢包情况下这种机制不能保证所有接收节点都能恢复出丢失的数据包，因为 采用这种机制的编码方案，不能保证重传包之间是线性独立的，因此导致重传包 数量增多和重传次数增加。北京邮电大学曹震的硕士论文中基于包比特移位设计 了一种改进范德蒙矩阵的编码方案，运用此方案能够保证发送最少编码重传数据 包后，所有接收节点都能恢复出丢失的数据包。但是这种方案在接收端恢复丢包 时的复杂度极大，并且数据包中一旦有一个比特位发生误码，此误码会严重蔓延。 本申请人之前也提出过相关申请CN201410097774.0，提出了组播场景下丢包重 传机制的框架和流程，以及重传包帧格式的设计。该申请中使用的生成异或组合 包的方法是将每个用户的第i个丢包异或组合生成第i个重传包，此方法在某些 特殊丢包情况下无法保证重传包之间线性无关，因而用户无法正确恢复出丢包。 例如一个AP向四个用户广播了四个数据包P1、P2、P3和P4，用户一丢失P1、 P2，用户二丢失P1、P4，用户三丢失P2、P3，用户四丢失P1、P4。根据该申请 中的方法生成的重传包为P1⊕P2⊕P3和P2⊕P3⊕P4，对于用户三来说，根据重 传包和自身已接收到的数据包无法正确恢复出任何丢包。利用上述BRANC的方法 可以正确恢复出丢包，但是需要发送三个重传包P1⊕P2⊕P3、P2⊕P3⊕P4和P1 ⊕P2，因此重传包数量并不是最低。

为此，本发明设计了一种多播场景下最小丢包重传方法，这种方法适用于所 有丢包情况。对于上文所述的丢包情况，根据本发明的编码方法得到的重传包为 P1⊕P3和P2⊕P4，AP将重传包数量压缩到二个。本发明可以保证在所有用户成 功恢复出丢包的情况下，AP每次生成的重传包数量低至理论最低值。并且，由 于本发明编码和解码都是简单地进行比特按位异或操作，因此编译码复杂度均很 低，额外硬件开销几乎为零。

发明内容

为了解决上述技术问题，本发明提供了一种具有反馈链路的组播场景中最小 丢包重传方法，运用原始数据包的按位异或获得重传包，在使得所有的接收端都 能正确的恢复出丢包的情况下，发送的重传数据包达到理论最小值。

本发明提供的一种具有反馈链路的组播场景中最小丢包重传方法，其中，

组播网络中AP同时为P个用户服务，广播N个原始数据包；

每个用户分别生成接收状态向量，并向AP反馈丢包情况，其中单个用户 丢失的数据包数量至多为K；

AP根据P个用户反馈的丢包情况生成一个P×N的丢包信息统计矩阵；AP 生成一个N×K的编码矩阵，其中编码矩阵中的每一列代表一个重传数据包的组 合情况，所有用户的丢包序号与编码矩阵相对应的行向量形成的子矩阵满秩，且 不影响其他子矩阵的秩；AP将生成的编码矩阵与原始数据包进行比特按位异或， 得出组合重传包并向P个用户进行广播；

每个用户分别接收所述组合重传包，并将所述组合数据包与该用户已正确接 收到的数据包进行异或解码，恢复出所丢失的数据包。

本发明除了给出该技术方案的具体实施例以外，还给出了给无线广播网络最 小丢包重传方法的一个应用实例。

附图说明

下面将通过参照附图详细描述本发明的示例性实施例，使本领域的普通技术 人员更清楚本发明的上述及其它特征和优点，附图中：

图1为本发明中AP产生异或组合重传包的编码流程图。

图2为本发明判断修改编码矩阵是否影响其它用户的秩的流程图。

图3为本发明中用户进行异或解码恢复出丢包的解码流程图。

图4为本发明中使用最小丢包重传方法的组播场景重传机制的示意图。

图5为本发明中AP生成编码矩阵以及异或组合包的具体实例说明图。

图6为本发明中用户根据异或组合包进行异或解码恢复出丢包的具体实例 说明图。

具体实施方式

下面结合附图对本发明作进一步详细描述。

图1为本发明中AP产生异或组合重传包的编码流程图，具体流程如下：

步骤101：从编码矩阵M中提取第i号用户的子矩阵SM。具体地，从丢 包矩阵表中查得第i号用户丢包序号，从编码矩阵M中提取出丢包序号对应 的行向量组合成该用户的编码子矩阵SM。

步骤102：计算SM的行数r、列数c和秩rank。如果rank等于0则进行 步骤103；如果0<rank<r则进行步骤104；否则进行步骤113。

步骤103：将SM赋值为单位阵，更新M。此时子矩阵SM秩为r且对其他 用户的秩不造成影响，用SM更新M对应的行向量。

步骤104：判断子矩阵SM是否有全零行zr和全零列zc。有则进行步骤 105，否则进行步骤106。

步骤105：将SM内第一个全零行和第一个全零列交叉处的元素值置1。 进行步骤111。

步骤106：令j＝1。j＝1代表子矩阵的第1列，j是子矩阵列号。

步骤107：将SM中j列零值分别置1，计算秩rank。该步骤是通过将SM 的零值修改为1来增加其秩大小。

步骤108：判断rank是否增加，是则进行步骤110，否则进行步骤109。

步骤109：令j＝j+1，即对子矩阵SM的下一列进行处理，返回步骤107。

步骤110：判断是否影响其他用户的秩，是则进行步骤109，否则进行步 骤111。该判断可以通过提取出相关用户的子矩阵，重新计算其秩大小来判 断修改当前零值是否会影响其他用户的秩。具体过程由步骤201至209来说 明。

步骤111：更新M和SM。具体地，根据SM更新M对应的行向量。

步骤112：判断更新后的子矩阵SM的秩rank的大小是否等于r。如果等 于则进行步骤113，否则进行步骤104。

步骤113：判断i是否大于用户总数，即判断是否已对所有用户进行完赋 值操作。是则进行步骤115，否则进行步骤114。

步骤114：令i＝i+1，即对下一个用户进行以上赋值操作。

步骤115：结束。

通过以上步骤对所有用户进行赋值完毕，将本流程所得到的编码矩阵与原 始数据包进行比特按位异或便可得出组合重传包。

图2为本发明判断修改编码矩阵是否影响其它用户的秩的流程图，具体流程 如下：

步骤201：查看修改的数值所对应的数据包编号m。具体地，在步骤107 中对子矩阵SM的j列中的某一零值置1，查看该零值对应的行代表的数据包 编号m。

步骤202：找出丢包矩阵含有m的所有用户集合S，以及S中用户总数k。

步骤203：令u＝1，jump＝1。u代表S内的用户编号；jump是程序的返 回值，用来判断是否影响S内用户的秩大小。

步骤204：提取用户u对应的子矩阵SM，计算其行值h和秩rank。

步骤205：判断rank＝h是否成立，即判断用户u的子矩阵的秩是否等于 其行值。是则进行步骤207，否则进行步骤206。

步骤206：令jump＝-1，即将-1赋值给jump。

步骤207：判断u＝k是否成立，即判断是否已处理完所有用户。是则进 行步骤209，否则进行步骤208。

步骤208：令u＝u+1，即对下一个用户进行处理。

步骤209：返回jump的值。jump的值为1，表示对S内用户的秩无影响； jump的值为-1，则该对当前零值的修改影响了某一用户的秩。

图3为本发明中用户进行异或解码恢复出丢包的解码流程图，具体流程如 下：

步骤301：用户生成接收状态向量并反馈丢包。用户在收到AP广播的原 始数据包后，根据自身接收情况生成接收状态向量，如果正确接收到原始数 据包i，则将向量中第i个值置1，否则将第i个值置0。

步骤302：用户统计接收到的AP所发送的异或组合包总个数K。

步骤303：判断组合包包头是否含有接收向量中置0的包号，是则进行 步骤305，否则进行步骤304。其中，接收向量中第i个值置0代表用户未 正确接收数据包i，如果组合包包头中包含未正确接收的数据包i，则将组 合包放入缓冲区待处理，否则直接丢弃。

步骤304：丢弃该组合包，更新组合包总个数K。

步骤305：令j＝1。j代表当前的异或组合包序号。

步骤306：将组合包j与已正确接收的数据包异或，并修改组合包包头。 具体地，将组合包中包头标志位为1且接收向量中置1的数据包与组合包异 或，并将包头标志位中参与异或的数据包的包头标志位置0。

步骤307：判断当前组合包包头标志位是否只有一个1，是则进行步骤 308，否则进行步骤310。

步骤308：将该标志位对应的数据包的接收状态向量的值置1，并令 K＝K-1。其中，组合包包头标志位只有一个1，表示该组合包经过异或解码之 后就会变成原始数据包，即包头标志位为1的数据包。

步骤309：判断K＝0是否成立，是则进行步骤312，否则进行步骤305。 K等于0表示没有待处理的异或组合包。

步骤310：判断j＝K是否成立，是则进行步骤312，否则进行步骤311。 j等于K表示已经对所有的组合包进行解码处理。

步骤311：令j＝j+1，即已对j号组合包进行异或解码，跳转到对下一 个组合包进行处理。

步骤312：判断接收状态向量是否有0值，是则进行步骤313，否则进 行步骤314。其中，接收状态向量中有0值表示0值代表的数据包仍未正确 接收。

步骤313：检查接收状态向量中的0值，并反馈丢包信息。

步骤314：反馈ACK。接收状态向量中没有0值，则代表所有数据包已 经成功接收，反馈正确应答ACK。

图4为本发明中使用最小丢包重传方法的组播场景重传机制的示意图，具体 流程如下：

首先，在一个AP四个用户的组播场景中，AP广播一组数据包P1、P2、P3、 P4、P5、P6。由于四个组播用户所处的位置不同导致四个用户无线信道差异，所 以各自正确接收到的数据包不同。用户一正确接收了数据包P3、P4、P6；用户 二正确接收了数据包P1、P4、P5；用户三正确接收了数据包P1、P2、P5、P6； 用户四正确接收了数据包P1、P2、P3。每个用户临时生成了自己的接收状态向 量，数据包被正确接收则将向量对应值置1否则置0。

其次，四个用户根据各自接收情况反馈丢包信息。AP收到如下丢包反馈： 用户一反馈丢包P1、P2、P5；用户二反馈丢包P2、P3、P6；用户三反馈丢包P3、 P4；用户四反馈丢包P4、P5、P6。AP根据三个用户的丢包反馈信息临时生成一 个丢包统计表。

最后，AP根据丢包统计表，按照本发明中的编码方法生成异或组合重传包， 重传包Q1由P1、P3、P5按位异或得出，重传包Q2由P2、P4按位异或得出，重 传包Q3由P5、P6按位异或得出。由于所有用户最大丢包个数为3，所以AP此 时只需生成三个重传包。各个用户根据本发明中的解码方法将异或组合重传包与 自己已经成功接收的数据包做相应的异或解码即可恢复出丢包。

图5为本发明中AP生成编码矩阵以及异或组合包的具体实例说明图。

在上述AP和四个用户的组播场景中，AP广播六个数据包后根据用户反馈的 丢包情况生成丢包统计表，由于单个用户最大丢包个数为3，所以AP生成一个 6×3的编码矩阵M，初始化为全零阵。

用户一丢包P1、P2、P5，提取出编码矩阵的1、2、5行形成用户一的子矩 阵SM。此时SM为全零阵，将SM赋值为单位阵，然后再用SM更新M的1、2、5 行。

用户二丢包P2、P3、P6，提取出编码矩阵的2、3、6行形成用户二的子矩 阵SM。此时SM秩为1，小于行值3，且有全零行3、6和全零列Q1、Q3。首先将 3行Q1列值的置1，SM秩增加但是仍然小于行值；经检测仍有全零行6和全零 列Q3，然后将6行Q3列值置1，SM满秩；最后再用SM更新M的2、3、6行。

用户三丢包P3、P4，提取出编码矩阵的3、4行形成用户三的子矩阵SM。此 时SM只有3行Q1列值为1，小于行值2，且有全零行4和全零列Q2、Q3。首先 将4行Q2列的值置1，SM满秩；然后再用SM更新M的3、4行。

用户四丢包P4、P5、P6，提取出编码矩阵的4、5、6行形成用户二的子矩 阵SM。此时SM的秩为2，小于行值3，且没有全零行只有全零列Q1。首先将4 行Q1列值置1，SM秩不增加，此种修改方案不可行。