联合最大度机会传输与网络编码ARQ的数据广播方法

摘要

本发明公开了一种联合最大度机会传输与网络编码ARQ的数据广播方法，包括以下步骤：基站广播数据包；接收端进行解码并将数据包的正确解码情况反馈给基站；基站将丢失原始信息进行最大度网络编码生成网络编码数据包，并采用最大度机会重传策略重传网络编码数据包，接收端将重传阶段恢复出的数据包情况反馈给基站；重复步骤3)直至所有接收端都正确接收到所有数据包。本发明确保了网络编码后的数据包能够给接收端提供尽可能多的译码机会，对于不能够给接收端提供很多译码机会的网络编码数据包则不重传，等待下一轮重新进行网络编码重传。本发明具有平均重传次数小、广播效率高等特点，能够很好的应用于无线数据广播场景中。

说明书

技术领域

本发明属于无线通信技术领域，涉及无线数据广播通信中的反馈重传技术，为一种联合 最大度机会传输与网络编码ARQ，尤其涉及一种联合最大度机会传输与网络编码ARQ的数 据广播方法。

背景技术

自动重传请求技术(Automatic-Repeat-reQuset，ARQ)是用于在不可靠信道中提高通信 可靠性的一种简单而有效的技术。“林舒,科斯特洛.差错控制编码(晏坚等译).北京：机械 工业出版社，2007.6”，“Cam,R.；Leung,C.；,"ThroughputanalysisofsomeARQprotocolsinthe presenceoffeedbackerrors,"Communications,IEEETransactionson，vol.45,no.1,pp.35-44,Jan 1997”，“Yu,P.；ShuLin；,"AnEfficientSelective-RepeatARQSchemeforSatelliteChannelsand ItsThroughputAnalysis,"Communications,IEEETransactionson,vol.29,no.3,pp.353-363,Mar 1981”。ARQ通过接收端请求基站重传出错的数据单元以达到正确接收的目的，其实现方式 简单，复杂度较低，常与前向纠错联合起来用于保证实际系统通信的可靠性“S.B.Wicker， ErrorControlSystemsforDigitalCommunicationsandStorage,PrenticeHall,EnglewoodCliffs, N.J.,1995”。

文献“Larsson,P.,&Johansson,N.Multi-userARQ.InVehicularTechnologyConference, 2006.VTC2006-Spring.IEEE63rd,2006(Vol.4,pp.2052-2057):IEEE”针对两个接收端的单播 场景提出了一种适用于多用户系统的ARQ方案。该方案利用了网络编码的思想，在数据包重 传阶段将不同接收端的数据包异或合并的方式来减小重传数据包的发送数量，提高系统的吞 吐量，接收端利用已知的信息解出自己所需要的信息的方式来恢复自己需要的数据包。文献 “肖潇,王伟平,杨路明,&张帅(2009).基于网络编码的无线网络广播重传方法.通信学报 (9),69-75.”提出了一种基于网络编码的ARQ方法，其思想是在保证多个接收端能够解码并 获得有用数据包的前提下，将多个需要重传的数据包进行异或合并，从而极大的减少了数据 包的平均重传次数。

通过将网络编码的思想应用在无线广播通信中，能够有效的提高广播的效率，现阶段已 有的专利成果如下：

1.西安电子科技大学提出的基于网络编码的广播重传系统及其方法，公开了一种基于网 络编码的广播重传系统及其方法，主要解决现有广播重传技术重传效率较低的问题。该发明 的系统包括基站和多个接收端，基站包括协商模块、动态列表模块、重传缓存模块、译码模 块、反馈模块。该发明的实现步骤包括：(1)发送测试包；(2)获取系统单帧最大存活时间； (3)动态链表初始化；(4)发送信息帧；(5)更新动态列表；(6)构造重传帧；(7)发送重 传帧；(8)再次更新动态列表；(9)处理动态列表中的剩余信息；(10)传输前准备；(11) 接收数据帧；(12)重传帧译码。

2.哈尔滨工业大学提出的基于网络编码的发射端广播重传方法及系统，通过构建重传缓 冲池、初始化重传缓冲池、组合重传数据包，然后发送重传数据包，减少了传输次数，提高 了能量效率，当数据量较大时，减小了网络时延，提高了网络传输效率，减少了网络丢包率， 增加了传输的可靠性，能达到网络最大信息流。

3.电子科技大学提出的WSN中引入基于同步机制的网络编码的广播方法，本发明公开 了一种WSN中引入基于同步机制的网络编码实现高效率可靠方法，在广播的建立阶段，中 心节点发送含有下次唤醒时间的同步数据包SYNC，来实现所有邻居节点的周期同步唤醒以 及休眠；发送节点向其他节点广播第1到底N个数据包，并将这些数据包储存起来；返回 ACK包，并储存收到的数据包；估算重传次数；重传所有终端都丢失的数据包；选择丢包进 行编码组合；接收节点反馈。本发明在WSN中引入基于同步机制的网络编码实现高效率可 靠广播方法，通过广播的建立，原始数据的广播，以及重传过程三个阶段的实现，减少了整 个网络的能耗，实现了信息的可靠广播。

4.中国人民解放军理工大学提出的基于网络编码的加权广播重传方法，本发明公开了一 种基于网络编码的加权广播重传方法，包括如下步骤：根据各接收节点数据包反馈的数据包 状态信息和链路状态信息，构建加权数据包分布矩阵；以加权数据包分布矩阵为基础，在源 节点进行编码数据包的选取；源节点将选取的数据包进行XOR编码后，广播重传给各接收节 点；各接收节点在接收到编码数据包后进行译码，并将译码后的数据包状态信息和链路状态 信息反馈给源节点；源节点根据接收节点的反馈信息，判断传输是否完成，如未完成则重新 开始新一轮的编码重传。本发明的方法，能在链路状态不均衡的网络环境下，以低的计算复 杂度实现高的传输效率。可广泛用于各种具有反馈的广播网络。

4.中国人民解放军理工大学提出的一种基于有限集合网络编码ARQ的大规模接收端数 据广播方法，本发明公开了一种基于有限集合网络编码ARQ的大规模接收端数据广播方法， 包括以下步骤：1)基站广播数据包；2)接收端进行解码并根据解码情况计算各个预置网络 编码方案的解码增益，然后反馈解码增益最大的方案序号；3)基站通过统计接收端的反馈信 息来确定本次重传采用的网络编码方案。本发明需要在基站和接收端预置有限集合网络编码 方案，并且将预置有限集合网络编码ARQ引入广播通信中，减小了反馈信息数量，降低了数 据包平均重传次数，提高了广播通信的效率，主要解决了现有广播重传技术在有大量接收端 的情况下重传效率低、反馈信息数量过大的问题。

现有的网络编码ARQ方案在进行网络编码时没有考虑丢失数据包在各个接收端间的分 布情况，并且生成的网络编码数据包无论能够提供给接收端的译码机会多少都进行广播。由 于丢失数据包在各个接收端之间分布的差异性，丢失接收端较多的数据包在进行网络编码时 不容易和其他数据包进行配对，并且这类数据包重传时在接收端能够提供更多的译码机会， 因此对于这类数据包在进行网络编码时需要进行优先考虑。同时，传统的网络编码ARQ方法 在进行重传阶段将生成的所有网络编码数据包一次发送，没有考虑这些网络编码数据包在接 收端能够提供的译码机会，从而造成广播通信的频谱效率低下。

发明内容

本发明要解决的问题是针对上述现有技术的不足提供一种联合最大度机会传输与网络编 码ARQ的数据广播方法，本联合最大度机会传输与网络编码ARQ的数据广播方法具有平均 重传次数小、广播效率高等特点。

为解决上述技术问题，本发明的技术方案为：联合最大度机会传输与网络编码ARQ的数 据广播方法，其特征在于包括以下处理步骤：

步骤(1.1)，基站广播数据包：

基站将原始信息进行信道编码、调制后形成原始数据包，然后基站向所有接收端广播原 始数据包；

步骤(1.2)，接收端处理与反馈：接收端对接收到的原始数据包进行软解调、信道译码， 并且通过译码后的信息尾部的CRC校验判断是否正确译码；

若一个原始数据包在一个接收端能够被正确译码，则该接收端存储译码后的原始信息， 并利用反馈信道反馈给基站以告知基站该数据包已经正确译码；反之，若该接收端无法正确 该原始数据包，则该接收端利用反馈信道反馈给基站以告知基站该原始数据包丢失；

若一轮数据广播结束后，一个接收端正确接收到所有的原始数据包，则该接收端进入静 默状态；反之，若该接收端存在原始数据包丢失，则该接收端等待基站重传数据包；

步骤(1.3)，结束广播或者基站重传：

基站根据接收到的各个接收端反馈的数据包正确接收情况进行判断，如果所有接收端都 已经正确接收到所有原始数据包，则基站广播结束；反之，如果接收端存在原始数据包丢失， 则基站将丢失的原始数据包所对应的原始信息进行最大度网络编码生成网络编码数据包，并 采用最大度机会重传策略重传网络编码数据包给接受端；

接收端从接收到的网络编码数据包的包头处信息获知参与网络编码的原始数据包集合， 并对接收到的网络编码数据包进行软解调，之后利用本地存储的已正确译码的原始信息对软 解调得到的网络编码数据包的软信息进行联合信道-网络译码，并且通过译码后的信息尾部的 CRC校验判断是否正确译码；

如果正确译码，则接收端将恢复的原始信息进行存储，同时利用反馈信道反馈给基站以 告知基站该数据包已经正确译码；反之，若该接收端无法正确译码该网络编码数据包，则该 接收端等待基站重传数据包；

若一轮重传结束后，一个接收端已经正确接收到所有的原始数据包，则该接收端进入静 默状态；

反之，若该接收端仍然存在原始数据包丢失，则该接收端等待基站重传数据包；

然后重复步骤(1.3)，直到广播结束。

作为本发明进一步改进的技术方案，步骤(1.3)中所述的最大度网络编码包括以下步骤：

基站将所有接收端的数据包接收到与否的情况存储在一个M×λ的反馈矩阵T中， T(i,j)＝0表示接收端i正确接收到第j个数据包，T(i,j)＝1表示接收端i没有正确接收第j 个数据包；定义CodingList用于存储参与网络编码的丢失数据包的序号集合，定义UserList 用于存储丢失相应数据包的接收端序号集合；第s个参与网络编码的丢失数据包的序号集合 CodingList可以由如下步骤产生：

令s＝1；

步骤(2.1)，选择参与网络编码的第一个数据包：

所述网络编码的第一个数据包为具有最大度的数据包；

删除反馈矩阵T中元素全为“0”的列；

定义度为反馈矩阵T每列中“1”的个数，如第j列中“1”的个数可以表示为 D_j＝sum(T(:,j))；

从反馈矩阵T中选择度最大的列P_max，即将最大度存储到 MaxDegree中，将具有最大度的数据包序号存储到CodingList中，将丢失该数据包的相应接 收端序号存储到UserList中；

从反馈矩阵T中删除CodingList中存储的数据包序号对应的列；

令j＝1；

步骤(2.2)，更新CodingList和UserList

如果反馈矩阵T中的第j列中“1”的个数等于MaxDegree，则将该列中元素为“1”的 行所对应的接收端序号存储到UserList_Temp中；UserList_Temp是一个临时变量集合。

如果则UserList＝UserList∪UserList_Temp，且 CodingList＝CodingList∪j，并从反馈矩阵T中删除第j列；

如果则UserList＝UserList，且CodingList＝CodingList；

其中表示“空集”，∩表示集合“交集”运算符,∪表示集合“并集”运算符；

如果j+1＜λ，则清空UserList_Temp，令j＝j+1，重复步骤(2.2)；

如果j＝λ，则清空UserList_Temp，令j＝1，MaxDegree＝MaxDegree-1；

如果MaxDegree>0，则重复步骤2.2)；

如果MaxDegree＝0，则CodingList为生成的第s个参与网络编码的丢失数据包的序号集 合，记为CodingList(s)＝CodingList；

如果反馈矩阵T中存在不为“0”的元素，即sum(T(:))≠0，则令s＝s+1，重复步骤(2.1) 和步骤(2.2)，生成第s+1个参与网络编码的数据包序号集合；

反之，如果反馈矩阵T中所有元素均为“0”，即sum(T(:))＝0，则最大度网络编码结束。

作为本发明进一步改进的技术方案，步骤(1.3)中所述的最大度机会重传策略包含以下 步骤：

步骤(3.1)，计算所有根据最大度网络编码方法生成的S个参与网络编码的数据包序号 集合CodingList(s)，s＝{1,2,…,S}中，度最大的一个网络编码集合，即

$CodingList\left(d\right)=\arg \underset{s\in \{1,2,...,S\}}{max}\underset{k\in CodingList\left(s\right)}{\Sigma }\underset{m=1}{\overset{M}{\Sigma }}T(m,k)$

步骤(3.2)，将CodingList(d)中存储的序号所对应的所有原始信息向量进行异或(XOR) 运算，即

$a_c=a_o\oplus a_p\oplus ...\oplus a_q,o,p,...,q\in CodingList\left(d\right)$

a_c是经过网络编码的原始信息，将a_c经过信道编码、调制后构成一个网络编码数据包；

步骤(3.3)，基站将该网络编码数据包重新广播给所有接收端。

作为本发明进一步改进的技术方案，步骤(1.3)中所述的联合信道-网络编码包括以下步 骤：

如果a_c是经过网络编码的原始信息，假设一个接收端丢失了其中的一个原始信息向量a_o；

第l个用户接收到的网络编码数据包为y_l,c，则编码后的信息向量b_o的软信息可以由下式 得到

其中，sign(·)表示取符号运算，表示集合差集运算，表示调制符号 x_c{o}(n)中与信息比特b_c{o}(m)对应的部分，且

本发明针对现有的网络编码ARQ方案在进行网络编码时没有考虑丢失数据包在各个接 收端间的分布情况，并且生成的网络编码数据包无论能够提供给接收端的译码机会多少都进 行广播等问题，提出了一种联合最大度机会传输与网络编码ARQ的数据广播方法。本发明采 用最大度网络编码方法对所有的错误数据包进行网络编码，利用丢失数据包在各个接收端之 间分布的差异性，将度最大的丢失数据包选择为第一个参与网络编码数据包，并将度较小的 数据包与之配对构成网络编码包，从而确保网络编码后的数据包能够给接收端提供尽可能多 的译码机会。在进行网络编码包重传时，采用基于最大度的机会重传策略，即仅发送能够给 接收端提供更多译码机会的网络编码数据包，对于那些不能够给接收端提供很多译码机会的 网络编码数据包则不重传，等待下一轮重新进行网络编码重传。本发明联合最大度机会传输 与网络编码ARQ的数据广播方法具有平均重传次数小、广播效率高等特点，能够很好的应用 于无线数据广播场景中。

附图说明

图1是本发明的实现框图。

图2是本发明的无线数据广播系统模型示意图。

图3是本发明的信号流程示意图。

图4是本发明的不同信噪比下平均传输次数性能图。

图5是本发明的不同数据包总数情况下平均传输次数性能图。

图6是本发明的不同接收端个数情况下平均传输次数性能图。

下面结合附图及具体实施例对本发明的具体实施方式作进一步描述。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，一下结合实施例，对本发明进行 进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定 本发明。

实施例1

如图1所示，本联合最大度机会传输与网络编码ARQ的数据广播方法，其特征在于包括 以下处理步骤：

步骤(1.1)，基站广播数据包：

基站将原始信息进行信道编码、调制后形成原始数据包，然后基站向所有接收端广播原 始数据包；

步骤(1.2)，接收端处理与反馈：

接收端对接收到的原始数据包进行软解调、信道译码，并且通过译码后的信息尾部的CRC 校验判断是否正确译码；

若一个原始数据包在一个接收端能够被正确译码，则该接收端存储译码后的原始信息， 并利用反馈信道反馈给基站以告知基站该数据包已经正确译码；反之，若该接收端无法正确 该原始数据包，则该接收端利用反馈信道反馈给基站以告知基站该原始数据包丢失；若一轮 数据广播结束后，一个接收端正确接收到所有的原始数据包，则该接收端进入静默状态；反 之，若该接收端存在原始数据包丢失，则该接收端等待基站重传数据包；

步骤(1.3)，结束广播或者基站重传：

基站根据接收到的各个接收端反馈的数据包正确接收情况进行判断，如果所有接收端都 已经正确接收到所有原始数据包，则基站广播结束；反之，如果接收端存在原始数据包丢失， 则基站将丢失的原始数据包所对应的原始信息进行最大度网络编码生成网络编码数据包，并 采用最大度机会重传策略重传网络编码数据包给接受端；

接收端从接收到的网络编码数据包的包头处信息获知参与网络编码的原始数据包集合， 并对接收到的网络编码数据包进行软解调，之后利用本地存储的已正确译码的原始信息对软 解调得到的网络编码数据包的软信息进行联合信道-网络译码，并且通过译码后的信息尾部的 CRC校验判断是否正确译码；

如果正确译码，则接收端将恢复的原始信息进行存储，同时利用反馈信道反馈给基站以 告知基站该数据包已经正确译码；反之，若该接收端无法正确译码该网络编码数据包，则该 接收端等待基站重传数据包；

若一轮重传结束后，一个接收端已经正确接收到所有的原始数据包，则该接收端进入静 默状态；反之，若该接收端仍然存在原始数据包丢失，则该接收端等待基站重传数据包；

然后重复步骤(1.3)，直到广播结束。

作为优选方案，步骤(1.3)中所述的最大度网络编码包括以下步骤：

基站将所有接收端的数据包接收到与否的情况存储在一个M×λ的反馈矩阵T中， T(i,j)＝0表示接收端i正确接收到第j个数据包，T(i,j)＝1表示接收端i没有正确接收第j 个数据包；定义CodingList用于存储参与网络编码的丢失数据包的序号集合，定义UserList 用于存储丢失相应数据包的接收端序号集合；第s个参与网络编码的丢失数据包的序号集合 CodingList由如下步骤产生：

令s＝1；

步骤(2.1)，选择参与网络编码的第一个数据包：(具有最大度的数据包)

删除反馈矩阵T中元素全为“0”的列；

定义度为反馈矩阵T每列中“1”的个数，如第j列中“1”的个数可以表示为 D_j＝sum(T(:,j))；

从反馈矩阵T中选择度最大的列P_max，即将最大度存储到 MaxDegree中，将具有最大度的数据包序号存储到CodingList中，将丢失该数据包的相应接 收端序号存储到UserList中；

从反馈矩阵T中删除CodingList中存储的数据包序号对应的列；

令j＝1；

步骤(2.2)，更新CodingList和UserList：

如果反馈矩阵T中的第j列中“1”的个数等于MaxDegree，则将该列中元素为“1”的 行所对应的接收端序号存储到UserList_Temp中；UserList_Temp是一个临时变量集合；

如果则UserList＝UserList∪UserList_Temp，且 CodingList＝CodingList∪j，并从反馈矩阵T中删除第j列；

如果则UserList＝UserList，且CodingList＝CodingList；

其中表示“空集”，∩表示集合“交集”运算符,∪表示集合“并集”运算符；

如果j+1＜λ，则清空UserList_Temp，令j＝j+1，重复步骤2.2)；

如果j＝λ，则清空UserList_Temp，令j＝1，MaxDegree＝MaxDegree-1；

如果MaxDegree>0，则重复步骤2.2)；

如果MaxDegree＝0，则CodingList为生成的第s个参与网络编码的丢失数据包的序号集 合，记为CodingList(s)＝CodingList；

如果反馈矩阵T中存在不为“0”的元素，即sum(T(:))≠0，则令s＝s+1，重复步骤(2.1) 和步骤(2.2)，生成第s+1个参与网络编码的数据包序号集合；

反之，如果反馈矩阵T中所有元素均为“0”，即sum(T(:))＝0，则最大度网络编码结束。

作为优选方案，步骤(1.3)中所述的最大度网络编码包括以下步骤：

步骤(3.1)，计算所有根据最大度网络编码方法生成的S个参与网络编码的数据包序号 集合CodingList(s)，s＝{1,2,…,S}中，度最大的一个网络编码集合，即

$CodingList\left(d\right)=\arg \underset{s\in \{1,2,...,S\}}{max}\underset{k\in CodingList\left(s\right)}{\Sigma }\underset{m=1}{\overset{M}{\Sigma }}T(m,k)$

步骤(3.2)，将CodingList(d)中存储的序号所对应的所有原始信息向量进行异或(XOR) 运算，即

$a_c=a_o\oplus a_p\oplus ...\oplus a_q,o,p,...,q\in CodingList\left(d\right)$

a_c是经过网络编码的原始信息，将a_c经过信道编码、调制后构成一个网络编码数据包；

步骤(3.3)，基站将该网络编码数据包重新广播给所有接收端。

作为优选方案，步骤(1.3)中所述的联合信道-网络编码包括以下步骤：

如果a_c是经过网络编码的原始信息，假设一个接收端丢失了其中的一个原始信息向量a_o；

第l个用户接收到的网络编码数据包为y_l,c，则编码后的信息向量b_o的软信息可以由下式 得到

其中，sign(·)表示取符号运算，表示集合差集运算，表示调制符号 x_c{o}(n)中与信息比特b_c{o}(m)对应的部分，且

作为优选方案，对本联合最大度机会传输与网络编码ARQ的数据广播方法进一步说明如 下：

图2中显示一个基站、多个接收端的无线广播场景。基站通过前向信道向大量接收端广 播数据，假设接收端的数量为M，需要广播的数据包的个数为λ。系统采用TDMA协议，在 每个TDMA时隙内，刚好可以发送一个数据包，并假设一个时隙内信道增益不变，不同时隙 内信道系数相互独立。

步骤(1.1)，基站广播数据包：

如图3所示，在广播阶段，基站将待发送信息进行CRC校验后构成原始信息a₁,a₂,…,a_λ， 原始信息经过卷积码(RSC)编码器后构成原始数据包b₁,b₂,…,b_λ，原始数据包经过调制后的 信号为x₁,x₂,…,x_λ；基站在广播阶段占用独立的λ个TDMA时隙完成数据包的广播，第 l(1≤l≤M)个接收端接收到的第k(1≤k≤λ)个数据包为

$y_{l,k}=h_{l,k}\sqrt{P_s}{x}_k+n_l$

其中x_k表示基站广播的第k个数据包，P_s为基站的发送功率，h_l,k和n_l分别表示第k个接收 端在第i个时隙内的信道系数和噪声，假设它们分别服从不同的复高斯分布，即 由于接收端的分布具有随机性，因此我们假设所有接收 端到基站的无线链路具有相同的分布，即

步骤(1.2)，接收端处理与反馈：

在完成数据包的接收后，接收端l对数据包进行软解调，接收数据包b_k的软信息可以表 示为

将得到的软信息L_l(b_k(i))送入RSC译码器得以恢复出原始信息并通过添加在原始信息尾部的CRC校验判断是否正确译码，其中表示恢复出的原始信息a_k；

若一个原始数据包b_k在一个接收端l能够被正确译码，则该接收端存储译码后的原始信 息a_k，并利用反馈信道反馈给基站该数据包已经正确译码；反之，若该接收端无法正确该原 始数据包，则该接收端利用反馈信道反馈给基站该原始数据包丢失；

若一轮数据广播结束后，一个接收端正确接收到所有的原始数据包，则该接收端进入静 默状态；

反之，若该接收端存在原始数据包丢失，则该接收端等待基站重传数据包。

步骤(1.3)，结束广播或者基站重传：

基站根据接收到的各个接收端反馈的数据包正确接收情况进行判断，如果所有接收端都 已经正确接收到所有原始数据包，则基站广播结束；

反之，如果接收端存在原始数据包丢失，则基站将丢失原始信息进行最大度网络编码生 成网络编码数据包，并采用最大度机会重传策略重传网络编码数据包a_c；

最大度网络编码方法的实现步骤如下：

基站将所有接收端的数据包接收到与否的情况存储在一个M×λ的反馈矩阵T中， T(i,j)＝0表示接收端i正确接收到第j个数据包，T(i,j)＝1表示接收端i没有正确接收第j 个数据包；

定义CodingList用于存储参与网络编码的丢失数据包的序号集合，定义UserList用于存 储丢失相应数据包的接收端序号集合；

第s个参与网络编码的丢失数据包的序号集合CodingList可以由如下步骤产生：

令s＝1；

步骤(2.1)，选择参与网络编码的第一个数据包：(具有最大度的数据包)

删除反馈矩阵T中元素全为“0”的列；

定义度为反馈矩阵T每列中“1”的个数，如第j列中“1”的个数可以表示为 D_j＝sum(T(:,j))；

从反馈矩阵T中选择度最大的列P_max，即将最大度存储到 MaxDegree中，将具有最大度的数据包序号存储到CodingList中，将丢失该数据包的相应接 收端序号存储到UserList中；

从反馈矩阵T中删除CodingList中存储的数据包序号对应的列。

令j＝1。

步骤(2.2)，更新CodingList和UserList：

如果反馈矩阵T中的第j列中“1”的个数等于MaxDegree，则将该列中元素为“1”的 行所对应的接收端序号存储到UserList_Temp中；UserList_Temp是一个临时变量集合；

如果则UserList＝UserList∪UserList_Temp，且 CodingList＝CodingList∪j，并从反馈矩阵T中删除第j列；

如果则UserList＝UserList，且CodingList＝CodingList；

其中表示“空集”，∩表示集合“交集”运算符,∪表示集合“并集”运算符；

如果j+1＜λ，则清空UserList_Temp，令j＝j+1，重复步骤1.3.1.2)；

如果j＝λ，则清空UserList_Temp，令j＝1，MaxDegree＝MaxDegree-1；

如果MaxDegree>0，则重复步骤1.3.1.2)；

如果MaxDegree＝0，则CodingList为生成的第s个参与网络编码的丢失数据包的序号集 合，记为CodingList(s)＝CodingList；

如果反馈矩阵T中存在不为“0”的元素，即sum(T(:))≠0，则令s＝s+1，重复步骤(2.1)， 步骤(2.2)，生成第s+1个参与网络编码的数据包序号集合；

反之，如果反馈矩阵T中所有元素均为“0”，即sum(T(:))＝0，则最大度网络编码结束。

最大度机会重传策略重传的实现步骤如下：

步骤(3.1)，计算所有根据最大度网络编码方法生成的S个参与网络编码的数据包序号 集合CodingList(s)，s＝{1,2,…,S}中，度最大的一个网络编码集合，即

$CodingList\left(d\right)=\arg \underset{s\in \{1,2,...,S\}}{max}\underset{k\in CodingList\left(s\right)}{\Sigma }\underset{m=1}{\overset{M}{\Sigma }}T(m,k)$

步骤(3.2)，将CodingList(d)中存储的序号所对应的所有原始信息向量进行异或(XOR) 运算，即

$a_c=a_o\oplus a_p\oplus ...\oplus a_q,o,p,...,q\in CodingList\left(d\right)$

a_c是经过网络编码的原始信息，将a_c经过信道编码、调制后构成一个网络编码数据包x_c；

步骤(3.3)，基站将该网络编码数据包x_c重新广播给所有接收端。

接收端从接收到的网络编码数据包x_c的包头处信息获知参与网络编码的原始数据包集 合，并对接收到的网络编码数据包进行软解调，之后利用本地存储的已正确译码的原始信息 对软解调得到的网络编码数据包的软信息进行联合卷积码-网络译码，得到编码后的信息向量 b_o。

联合卷积码-网络译码器的实现如下：

如果a_c是经过网络编码的原始信息，假设一个接收端丢失了其中的一个原始信息向量a_o； 第l个用户接收到的网络编码数据包为y_l,c，则编码后的信息向量b_o的软信息可以由下式得到

其中，sign(·)表示取符号运算，表示集合差集运算，表示调制符号 x_c{o}(n)中与信息比特b_c{o}(m)对应的部分，且

将得到的软信息L_l(b_o(n))送入RSC译码器得以恢复出原始信息并通过添加在原始 信息尾部的CRC校验判断是否正确译码，其中表示恢复出的原始信息a_o；通过译码后 的信息a_o尾部的CRC校验判断是否正确译码。

如果正确译码，则将恢复的原始信息进行存储，同时利用反馈信道反馈给基站该数据包 已经正确译码。

反之，若该接收端无法正确译码该网络编码数据包，则该接收端等待基站重传数据包。

若一轮重传结束后，一个接收端已经正确接收到所有的原始数据包，则该接收端进入静 默状态；

反之，若该接收端仍然存在原始数据包丢失，则该接收端等待基站重传数据包。

重复步骤(1.3)，直到广播结束。

仿真验证:

为了验证提出的联合最大度机会传输与网络编码ARQ的数据广播方法的性能，仿真了数 据包平均传输次数与接收信噪比、接收端个数M以及所有数据包个数λ之间的关系。

图4分别给出了瑞利信道条件下，联合最大度机会传输与网络编码ARQ的数据广播方法 (联合最大度方法)、传统不考虑度分布的网络编码方法(传统网络编码)和XORing网络编 码方法(XORing网络编码)方案的数据包平均传输次数的性能对比。可以看出，在相同的信 噪比和接收端个数情况下，提出的联合最大度机会传输与网络编码ARQ的数据广播方法可以 有效降低数据包的重传次数，提高广播通信的效率。

图5给出了信噪比为-2dB时，三种方案的平均传输次数性能随着数据包个数λ的变化曲 线。可以看出，在相同的信噪比和接收端个数情况下，提出的联合最大度机会传输与网络编 码ARQ的数据广播方法具有最低的数据包的平均传输次数。

图6给出了数据包个数λ＝100时，三种方案的平均传输次数性能随着接收端个数M的变 化曲线。可以看出，在相同的信噪比和数据包个数情况下，提出的联合最大度机会传输与网 络编码ARQ的数据广播方法具有最低的数据包的平均传输次数。

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