无线多播中基于混合网络编码的用户协作方法

摘要

一种无线多播中基于混合网络编码的用户协作方法，主要解决现有技术出现的高传输效率与低寻优复杂度、低计算开销难以兼顾的问题。具体步骤包括：(1)多播数据包；(2)建立数据包分布矩阵；(3)选出重传者；(4)获得数据包稀有度向量；(5)判断是否存在所有用户都丢失的数据包；(6)源节点重传所有用户都丢失的数据包；(7)判断重传者丢失的数据包数是否为0；(8)恢复重传者丢失的数据包；(9)判断重传者丢失的数据包数是否为0；(10)重传者使用混合网络编码方案重传；(11)结束多播过程。本发明在保证高传输效率的条件下，具有寻优简单和计算开销小的优点。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及无线通信技术领域中的一种无线多播中基于混合网络编码的用户协作方法。本发明应用混合网络编码对数据进行编码，使用用户协作技术进行数据传输，用户对收到的数据进行解码后，恢复原始的多播信息，可应用于无线多播中恢复用户丢失的多播数据。

背景技术

无线多播通过源节点广播多个数据包给一组特定的用户，是一种高效的传输方式。针对无线多播中的丢包问题，传统的方案采用源节点重传的方式恢复用户的丢包。用户协作作为一种解决丢包问题的有效方案，近些年得到了大量的关注。相比源节点重传方式，该方案不但消除了源节点的重传压力，而且得益于用户链路的高可靠性，具有很高的传输效率。网络编码通过发送节点对多个数据包进行线性或非线性的编码，增加了单次传输的信息量，提高了传输效率。将网络编码应用于多播系统的重传过程，可以进一步减少重传次数。

西安电子科技大学在其提出的专利申请文献“基于网络编码的多播重传方法”(申请日：2013年1月16日，申请号：201310015456.0,公开号：CN 103067137A)中公开了一种基于异或网络编码的源节点重传方法。该方法的实施步骤是：第一，源节点多播数据包；第二，用户节点接收数据包，并向源节点反馈数据包的接收状态信息；第三，源节点根据反馈信息生成数据包接收状态矩阵，然后通过处理该矩阵进行数据包的分组；第四，源节点对已分组的数据包进行异或网络编码，生成网络编码包，并重传这些编码包；第五，各用户节点对接收到的编码包进行译码，从中恢复出各自的丢失数据包。该方法与传统的ARQ(AutomaticRepeat Request)方法相比，由于异或运算操作简单，因此需要的计算开销很小。该方法存在的不足之处是：首先，由于源节点与用户节点间的链路质量往往比用户节点间的链路质量差，因此源节点重传方法传输效率低。其次，异或网络编码寻找一个最优的调度算法以获得最少的传输次数是NP难的，已有的算法都是次优的，随着数据包数和用户数的增长，寻优复杂度会变得更高，因而导致算法的执行时间过长，带来严重的处理时延。

Yanfei Fan等人在其发表的论文“PIE:Cooperative peer-to-peer informationexchange in network coding enabled wireless networks”(IEEE Transactions onWireless Communications，2010，9:945-950)中提出了一种基于随机线性网络编码的用户协作方法PIE(Peer-to-Peer Information Exchange)。该方法的实施步骤是：第一，每个用户通过共享自己的数据包状态向量的方式建立数据包分布矩阵；第二，用户根据数据包分布矩阵计算每个数据包的稀有度；第三，根据数据包的稀有度，选择拥有稀有度最高数据包的用户作为发送者；第四，发送者使用随机线性网络编码的方法编码自己拥有的所有数据包并发送出去；第五，用户接收发送者发送的编码包，并使用矩阵求逆的方式解码。该方法使用随机线性网络编码，具有很高的传输效率，该方法存在的不足之处是：线性网络编码的编解码运算会带来巨大的计算开销，随机线性网络编码带来的计算开销，不但会导致信息传输的延迟，还会带来较大的能量消耗。

Xiaoli Xu等人在其发表的论文“Two-phase cooperative broadcasting basedon batched network code”(IEEE Transactions on Communications，2016，64(2):285-299)提出了一种基于分组网络编码的用户协作方法。该方法的实施步骤是：第一，源节点使用BATS对多播数据进行编码后，广播编码后的数据包；第二，用户对接收到的编码包进行解码；第三，解码成功的用户对数据包进行随机线性网络编码后，广播编码后的数据包；第四，解码失败的用户接收解码成功的用户广播的编码包后，进行解码；该方法存在的不足之处是：分组网络编码和随机线性网络编码都会带来巨大的计算开销，增加多播系统的计算复杂度。

发明内容

本发明的目的是针对上述现有技术存在的问题，在无限多播系统中提出一种基于混合网络编码的用户协作方法，不仅可以保证多播过程的传输效率，而且可以减小用户协作过程中的计算开销。

实现本发明目的的具体思路是：先在协作簇中选择一个接收数据包总数最多的用户作为重传者，再通过用户协作的方式恢复重传者的丢包，然后再将数据包分布矩阵拆分为两个子矩阵，最后重传者分别使用随机线性网络编码和异或网络编码，编码并发送两个子矩阵中的数据包。

本发明实现上述目的的具体步骤如下：

(1)多播数据包：

无线多播系统中的源节点将待发送的数据包，按照从1开始递增的顺序编号后，依次多播给协作簇内的用户；

(2)建立数据包分布矩阵：

(2a)协作簇内的每个用户接收源节点发送的数据包，同时记录接收过程中数据包的丢失情况，将所有数据包的丢失情况用数据包分布向量表示；

(2b)协作簇内的所有用户依次广播自己的数据包分布向量，每个用户接收其他用户的数据包分布向量；

(2c)每个用户将收到的其他用户的数据包分布向量与自己的数据包分布向量，合并成一个数据包分布矩阵；

(3)选出重传者：

将数据包分布矩阵中成功接收数据包数量最多的用户作为重传者；

(4)获得数据包稀有度向量：

(4a)按照下式，计算接收的每个数据包的稀有度：

其中，PFV(j)表示第j个数据包的稀有度，j的取值为[1,N]范围内任意一个正整数，N表示数据包的总数，M表示协作簇内的用户总数，∑表示求和操作，PDM(i,l)表示数据包分布矩阵PDM中第i行第l列对应的值，l和j的取值对应相等；

(4b)将所有数据包的稀有度作降序排列后，组成数据包稀有度向量；

(5)判断数据包稀有度向量中是否存在与协作簇内用户总数相等的数值，若是，则执行步骤(6)，否则，执行步骤(7)；

(6)重传者将所有用户都丢失的数据包报告给源节点，源节点重传这些数据包后，执行步骤(2)；

(7)判断重传者丢失的数据包数是否为0，若是，则执行步骤(10)，否则，执行步骤(8)；

(8)恢复重传者丢失的数据包：

(8a)设置一个空集合，并命名为原编码集合；

(8b)将重传者丢失的数据包中编号最小的数据包放入原编码集合中，在数据包分布矩阵中，寻找与原编码集合中数据包编号相同的数据包，将拥有该数据包的任意一个用户作为发射者；

(8c)使用编码集合效益值公式，计算原编码集合的效益值；

(8d)将原编码集合包含的数据包与发射者拥有的且不属于原编码集合的任意一个数据包，组成一个新编码集合；

(8e)使用编码集合效益值公式，计算新编码集合的效益值；

(8f)判断新编码集合的效益值是否大于原编码集合的效益值，若是，则执行步骤(8g)，否则，执行步骤(8h)；

(8g)用新编码集合的效益值更新原编码集合的效益值，并用新编码集合替换原编码集合；

(8h)判断替换后的原编码集合中数据包总数是否大于等于3，若是，则执行步骤(8i)，否则，执行步骤(8d)；

(8i)将发射者和和替换后的原编码集合通过广播的方式告知协作簇内的用户；

(8j)发射者使用异或操作，将替换后的原编码集合包含的数据包编码成一个异或网络编码包，采用广播的方式，将异或网络编码包发送出去；

(8k)协作簇内的用户，用接收到的异或网络编码包更新数据包分布矩阵；

(9)判断重传者丢失的数据包数是否为0，若是，则执行步骤(10)，否则，执行步骤(8)；

(10)重传者使用混合网络编码方案重传：

(10a)将更新后的数据包分布矩阵中的所有列，按照数据包稀有度从高到低的顺序进行排列；

(10b)将排序后数据包分布矩阵拆分为高稀有度矩阵和低稀有度矩阵，高稀有度矩阵由排序后数据包分布矩阵的1到αN列组成，α表示拆分因子，α的取值为(0,1)范围内任意一个数，低稀有度矩阵由排序后数据包分布矩阵的αN到N列组成；

(10c)使用随机性网络编码公式，重传者对高稀有度矩阵中的所有数据包进行编码后，得到随机线性网络编码包，广播随机线性网络编码包；

(10d)协作簇内的用户对接收到的编码矩阵进行矩阵求逆操作，得到解码结果；

(10e)判断低稀有度矩阵是否为全0矩阵，若是，则执行步骤(11)，否则，执行步骤(10f)；

(10f)设置一个空集合，并命名为原编码集合；

(10g)将低稀有度矩阵包含的数据包中稀有度最高的数据包，放入原编码集合中；

(10h)利用编码集合效益值公式，计算原编码集合的效益值；

(10i)将原编码集合与重传者拥有的且不属于原编码集合的任意一个数据包，组成一个新编码集合；

(10j)利用编码集合效益值公式，计算新编码集合的效益值；

(10k)判断新编码集合的效益值是否大于原编码集合的效益值，若是，则执行步骤(10l)，否则，执行步骤(10m)；

(10l)将原编码集合的效益值更新为新编码集合的效益值，并将原编码集合用新编码集合替换；

(10m)判断原编码集合中数据包总数是否大于等于3，若是，则执行步骤(10n)，否则，执行步骤(10i)；

(10n)将替换后的原编码集合通过广播的方式告知协作簇内的用户；

(10o)重传者使用异或操作，将替换后的原编码集合包含的数据包编码成一个异或网络编码包，采用广播的方式，将异或网络编码包发送出去；

(10p)协作簇内的用户接收重传者广播的异或网络编码包，用接收到的异或网络编码包更新低稀有度矩阵；

(10q)判断低稀有度矩阵是否为全0矩阵，若是，则执行步骤(11)，否则，执行步骤(10f)；

(11)结束多播过程。

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

第一，本发明通过拆分数据包分布矩阵，得到高稀有度矩阵，对高稀有度矩阵进行随机线性网络编码处理，在保证高传输效率的条件下，克服了现有技术存在的随机线性网络编码计算开销大的问题，使得本发明具有计算开销低的优点。

第二，本发明通过拆分数据包分布矩阵，得到低稀有度矩阵，对低稀有度矩阵进行异或网络编码，在保证高传输效率的条件下，克服了现有技术存在的异或网络编码寻优困难的问题，使得本发明具有寻优简单的优点。

附图说明

图1为本发明的流程图；

图2为本发明中恢复重传者丢失数据包操作步骤的流程图；

图3为本发明中重传低稀有度矩阵中数据包操作步骤的流程图；

图4为本发明与现有方法的传输效率仿真图；

图5为本发明与现有方法的计算开销仿真图。

具体实施方式

下面结合附图对本发明做进一步的描述。

参照图1，本发明的实现方法如下。

步骤1，多播数据包。

无线多播系统中的源节点将待发送的数据包，按照从1开始递增的顺序编号后，依次多播给协作簇内的用户。

所述的协作簇是指，该协作簇由多个有相同多播业务需求的用户组成。

步骤2，建立数据包分布矩阵。

协作簇内的每个用户接收源节点发送的数据包，同时记录接收过程中数据包的丢失情况，将所有数据包的丢失情况用数据包分布向量表示。

所述的数据包分布向量是一个由0和1构成的、长度为N的行向量，其中，0是用于表示数据包接收成功，1是用于表示数据包丢失，N表示数据包的总数。

协作簇内的所有用户依次广播自己的数据包分布向量，每个用户接收其他用户的数据包分布向量。

每个用户将收到的其他用户的数据包分布向量与自己的数据包分布向量，合并成一个数据包分布矩阵。

步骤3，选出重传者。

将数据包分布矩阵中成功接收数据包数量最多的用户作为重传者。

步骤4，获得数据包稀有度向量。

按照下式，计算每个数据包的稀有度：

其中，PFV(j)表示第j个数据包的稀有度，j为[1,N]上的正整数，N表示数据包的总数，M表示协作簇内的用户总数，Σ表示求和操作，PDM(i,l)表示数据包分布矩阵PDM中第i行第l列对应的值，l和j的取值对应相等。

将所有数据包的稀有度作降序排列后，组成数据包稀有度向量。

步骤5，判断数据包稀有度向量中是否存在与协作簇内用户总数相等的数值，若是，则执行步骤6，否则，执行步骤7。

步骤6，重传者将所有用户都丢失的数据包报告给源节点，源节点重传这些数据包后，执行步骤2。

步骤7，判断重传者丢失的数据包数是否为0，若是，则执行步骤10，否则，执行步骤8。

步骤8，恢复重传者丢失的数据包。

下面结合图2对本发明中恢复重传者丢失数据包的具体步骤进行如下描述。

第1步，设置一个空集合，并命名为原编码集合。

第2步，将重传者丢失的数据包中编号最小的数据包放入原编码集合中，在数据包分布矩阵中，寻找与原编码集合中数据包编号相同的数据包，将拥有该数据包的任意一个用户作为发射者。

第3步，利用编码集合效益值公式，计算原编码集合的效益值。

所述编码集合效益值公式如下：

其中，benefit(PS)表示编码集合的效益值，PS表示编码集合，M表示协作簇内的用户数，Σ表示求和操作，need_i表示用户i对编码集合的需求度，need_i的计算公式如下：

其中，l表示编码集合中数据包的编号，PDM(k,l)表示数据包分布矩阵PDM中第k行第l列对应的值，k和i的取值对应相等。

第4步，将原编码集合包含的数据包与发射者拥有的且不属于编码集合的任意一个数据包，组成一个新编码集合。

第5步，利用编码集合效益值公式，计算新编码集合的效益值。

所述编码集合效益值公式如下：

其中，benefit(PS)表示编码集合的效益值，PS表示编码集合，M表示协作簇内的用户数，Σ表示求和操作，need_i表示用户i对编码集合的需求度，need_i的计算公式如下：

其中，l表示编码集合中数据包的编号，PDM(k,l)表示数据包分布矩阵PDM中第k行第l列对应的值，k和i的取值对应相等。

第6步，判断新编码集合的效益值是否大于原编码集合的效益值，若是，则执行本步骤的第7步，否则，执行本步骤的第8步。

第7步，用新编码集合的效益值更新原编码集合的效益值，并用新编码集合替换原编码集合。

第8步，判断替换后的原编码集合中数据包总数是否大于等于3，若是，则执行本步骤的第9步，否则，执行本步骤的第4步。

第9步，将发射者和和替换后的原编码集合通过广播的方式告知协作簇内的用户。

第10步，发射者使用异或操作，将替换后的原编码集合包含的数据包编码成一个异或网络编码包，采用广播的方式，将异或网络编码包发送出去。

第11步，协作簇内的用户，用接收到的异或网络编码包更新数据包分布矩阵。

第12步，判断重传者丢失的数据包数是否为0，若是，则执行步骤8，否则，执行本步骤的第2步。

步骤9，判断重传者丢失的数据包数是否为0，若是，则执行步骤10，否则，执行步骤8。

步骤10，重传者使用混合网络编码方案重传。

下面结合图3对本发明中重传者使用混合网络编码方案重传的具体步骤进行如下描述。

第1步，将更新后的数据包分布矩阵中的所有列，按照数据包稀有度从高到低的顺序进行排列。

第2步，将排序后数据包分布矩阵拆分为高稀有度矩阵和低稀有度矩阵，高稀有度矩阵由排序后数据包分布矩阵的1到αN列组成，α表示拆分因子，α的取值为(0,1)范围内任意一个数，低稀有度矩阵由排序后数据包分布矩阵的αN到N列组成。

第3步，使用随机性网络编码公式，重传者对高稀有度矩阵中的所有数据包进行编码后，得到随机线性网络编码包，广播随机线性网络编码包。

所述随机性网络编码公式如下：

其中，p′表示编码后的随机线性网络编码包，ω_n表示从伽罗华域GF(2⁸)中随机选取的编码系数，p_n表示重传者拥有的第n个数据包。

第4步，协作簇内的用户对接收到的编码矩阵进行矩阵求逆操作，得到解码结果。

第5步，判断低稀有度矩阵是否为全0矩阵，若是，则执行步骤11，否则，执行本步骤的第6步。

第6步，设置一个空集合，并命名为原编码集合。

第7步，将低稀有度矩阵包含的丢失数据包中稀有度最高的数据包，放入原编码集合中。

第8步，利用编码集合效益值公式，计算原编码集合的效益值。

所述编码集合效益值公式如下：

其中，benefit(PS)表示编码集合的效益值，PS表示编码集合，M表示协作簇内的用户数，Σ表示求和操作，need_i表示用户i对编码集合的需求度，need_i的计算公式如下：

其中，l表示编码集合中数据包的编号，PDM(k,l)表示数据包分布矩阵PDM中第k行第l列对应的值，k和i的取值对应相等。

第9步，将原编码集合与重传者拥有的且不属于原编码集合的任意一个数据包，组成一个新编码集合。

第10步，利用编码集合效益值公式，计算新编码集合的效益值。

所述编码集合效益值公式如下：

其中，benefit(PS)表示编码集合的效益值，PS表示编码集合，M表示协作簇内的用户数，Σ表示求和操作，need_i表示用户i对编码集合的需求度，need_i的计算公式如下：

其中，l表示编码集合中数据包的编号，PDM(k,l)表示数据包分布矩阵PDM中第k行第l列对应的值，k和i的取值对应相等。

第11步，判断新编码集合的效益值是否大于原编码集合的效益值，若是，则执行本步骤的第12步，否则，执行本步骤的第13步。

第12步，将原编码集合的效益值更新为新编码集合的效益值，并将原编码集合用新编码集合替换。

第13步，判断原编码集合中数据包总数是否大于等于3，若是，则执行本步骤的第14步，否则，执行本步骤的第9步。

第14步，将替换后的原编码集合通过广播的方式告知协作簇内的用户。

第15步，重传者使用异或操作，将替换后的原编码集合包含的数据包编码成一个异或网络编码包，采用广播的方式，将异或网络编码包发送出去。

第16步，协作簇内的用户接收重传者广播的异或网络编码包，用接收到的异或网络编码包更新低稀有度矩阵。

第17步，判断低稀有度矩阵是否为全0矩阵，若是，则执行步骤11，否则，执行本步骤的第6步。

步骤11，结束多播过程。

本发明提出的方法中，寻优复杂度体现在步骤10中所述的使用异或网络编码处理低稀有度矩阵的过程。低稀有度矩阵包含的数据包是被少数用户丢失的，对于这样的数据包分布矩阵，采用现有的源节点重传方法时，寻优过程的时间复杂度由o(N²×M)降为o((1-α)²N²×M)，其中o表示时间复杂度，N表示数据包总数，M表示协作簇内的用户总数。因此，本发明提出的方法可以降低采用异或网络编码时所需的寻优复杂度。

下面通过本发明的仿真实验对本发明的效果做进一步说明。

1.仿真条件：

本发明的仿真实验设置一个源节点和一个用户总数为M的协作簇。源节点向协作簇内的用户发送多播数据，源节点和用户节点间的数据包丢失情况彼此独立，数据包的丢失概率为0.2，拆分因子α设为0.5。

2.仿真内容：

本发明的仿真实验使用本发明提出的方法、现有技术的源节点重传方法和现有技术的用户协作PIE方法，分别对多播过程中协作簇内用户丢失的数据包进行恢复，得到平均传输次数和基本乘法运算次数的仿真结果。平均传输次数由多播过程中所有数据包的传输总次数与数据包总数的比值确定，平均传输次数越少，传输效率越高。基本乘法运算表示随机线性网络编码过程中一个由伽罗华域GF(2⁸)随机选取的系数和一个数据包相乘的运算，基本乘法运算次数表示多播过程中发生基本乘法运算的总次数。

传输效率如图4所示，图4中的横轴表示数据包的总数，单位是个，纵轴表示平均传输次数，单位是次。图4中分别以圆形、三角形和正方形标示的实线表示在用户总数M等于10时，分别使用现有技术的源节点重传方法、现有技术的用户协作PIE方法和本发明提出的方法，恢复丢失的数据包后得到的平均传输次数曲线。图4中分别以圆形、三角形和正方形标示的虚线表示在用户总数M等于15时，分别使用现有技术的源节点重传方法、现有技术的用户协作PIE方法和本发明提出的方法，恢复丢失的数据包后得到的平均传输次数曲线。

计算开销如图5所示，其中的横轴表示数据包总数，单位是个，纵轴表示平均传输次数，单位是次。由于现有的源节点重传方法需要的的计算开销很小，因此有关计算开销的仿真中，使用了现有技术的用户协作PIE方法和本发明提出的方法。图5中分别以三角形和正方形标示的实线表示在用户数M等于10时，分别使用现有技术的用户协作PIE方法和本发明提出的方法，恢复丢失的数据包后得到的基本乘法运算次数曲线。图5中分别以三角形和正方形标示的虚线表示在用户数M等于15时，分别使用现有技术的用户协作PIE方法和本发明提出的方法，恢复丢失的数据包后得到的基本乘法运算次数曲线。

3.仿真结果分析：

由图4的仿真图可见，当用户数M等于15且数据包总数等于100时，与现有技术的源节点重传方法相比，本发明得到的平均传输次数减少了10％左右，即100个数据包时，本发明所需的传输次数比现有技术的源节点重传方法少10次。此外，无论用户数M等于10或者15，当数据包总数小于80时，本发明得到的平均传输次数略大于现有技术的用户协作PIE方法得到的平均传输次数，而当数据包总数大于80时，本发明得到的平均传输次数略小于现有技术的用户协作PIE方法得到的平均传输次数。由此可见，本发明提出的方法与现有技术的源节点重传方法相比，具有更高的传输效率，与现有技术的用户协作PIE方法相比，具有大致相同的传输效率。

由图5的仿真图可见，当用户数M等于10且数据包总数等于100时，本发明得到的基本乘法运算次数约为现有技术的用户协作PIE方法的20％，而当用户数M等于15且数据包总数等于200时，本发明得到的基本乘法运算次数约为现有技术的用户协作PIE方法的15％。由此可见，本发明与现有技术的用户协作PIE方法相比，显著地降低了采用随机线性网络编码时的计算开销。

综上所述，本发明提出的方法，在保证高多播系统传输效率的条件下，一方面减小了采用异或网络编码方法时的寻优复杂度，另一方面减小了采用随机线性网络编码方法时的计算开销。