反馈丢失下基于子代划分的网络编码

朱小燕，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

反馈丢失下基于子代划分的网络编码

朱小燕，梅中辉

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

考虑在反馈丢失的情况下，根据即时解码的网络编码(Instantly Decodable Network Coding，IDNC)和随机线性网络编码(Random Linear Network Coding，RLNC)不同的特性，提出一种新的网络编码模型来建立两者之间的关系。该模型依赖于反馈丢失下IDNC图的建立以及最优IDNC解决方案下子代概念的提出，子代划分后在每个子代中应用RLNC的编码模型，且IDNC和RLNC只是该模型下具有特定子代大小的两个极端例子。这种机制把IDNC和RLNC联系在一起，便于更好地理解在反馈丢失下吞吐量与时延之间的权衡。仿真结果反映了反馈信息丢失情况下子代大小在不同信宿节点数量以及不同包丢失率时对系统性能的影响,且结果表明理论分析与实际计算相吻合，子代大小介于1和UIDNC之间的系统性能(如编码传输次数、平均译码时延)则介于IDNC和RLNC的系统性能之间。

网络编码；反馈丢失；子代划分；编码传输；译码时延

0 引 言

网络编码[1]在提升无线广播系统的性能方面有较大优势,这些系统中信宿节点需快速可靠地接收数据包[2]。信源节点或中间节点对数据包进行编码处理后发送能提高网络中的吞吐量，但这往往会以较大译码时延为代价[3-5]。在各类文献中，基于不同应用系统采用了多种网络编码，例如RLNC[6]和IDNC[2,7-8]。

RLNC最先由Tracy等[6]提出，在一个给定有限域内随机选取编码系数,当接收节点收到一定数量的编码向量线性无关的数据包时，即可完成网络译码。同IDNC比较,RLNC编码传输次数[9]较少。但是因为必须在所有编码数据包传输完后才能译码出原始数据包，所以RLNC的译码时延较大。

IDNC通过选择合适的编码数据包来保证一部分或所有信宿节点在成功接收编码包后即时译码出所需的数据包，因而译码时延相对较小。但是IDNC的编码传输次数较RLNC多，因为一次编码传输对于部分信宿节点来说可能无用。

网络编码系统中吞吐量与译码时延间的权衡为当前一大研究热点。且以前的大多数有关网络编码的研究都是假设来自信宿节点的反馈是非丢失的，但这个假设在许多实际情况中有其局限性。因为在信源端，反馈丢失很可能会由于无线链路的不可靠性而发生[10]。

因此，文中在考虑反馈丢失下研究IDNC图，根据RLNC与IDNC的特点建立RLNC与IDNC相关联的网络编码模型。此模型有助于更好地理解吞吐量与时延间的权衡。模型的建立基于最优IDNC解决方案下子代概念的提出，RLNC和IDNC只是该模型下具有特定子代大小的两个极端例子。文中提及的IDNC均为广义即时译码网络编码(Generalized Instantly Decodable Network Coding，G-IDNC[2])。

1 无线广播系统反馈模型

如图1所示的无线广播系统中，一个信源节点S广播发送N个源数据包至M个信宿节点，源数据包集合P={P1,P2,…,PN}，信宿节点集合R={R1,R2,…,RM}，每个信宿节点都需接收所有数据包。

图1 无线广播传输模型

此模型分为两个传输阶段。首先是系统传输阶段：信源节点S利用N个时隙广播发送N个原始未编码数据包至每个信宿节点。第一阶段后，每个信宿节点有三种包集合：

(1)集合Hi：信宿节点Ri成功收到并告知信源节点已收到的数据包集合；

(2)集合Wi：信宿节点Ri未收到或收到却未成功告知信源节点已收到(即反馈丢失)的数据包集合；

(3)集合Ui：数据包状态未知，Ui⊆Wi。

信源节点通过反馈矩阵(SenderFeedbackMatrix,SFM)储存以上信息，反馈矩阵F=[fij]：

(1)

在编码传输阶段，信源节点发送Wi中数据包的编码组合，编码包分为：

(1)非创新型：此编码包不包含Wi中的源数据包；

(2)即时译码型：此编码包只包含Wi中的一个源数据包；

(3)非即时译码型：此编码包包含Wi中的两个或多个源数据包。

定义1：在任意一次编码传输中，集合Wi非空的信宿节点Ri若成功收到一个非创新型或非即时译码型数据包，则Ri会增加一个单位的译码时延[2]。

这里假设传输与反馈信道都是无记忆可擦除信道，信宿节点Ri丢失数据包的概率为pi，反馈丢失概率为qi。信道中所有接收节点间相互独立，且只有目标接收节点才发送反馈信息。

2 反馈丢失下IDNC图的建立

文中在反馈丢失下进行研究，那么IDNC图就不能如文献[2]简单得出。

通过三种盲IDNC图更新法[10]的比较，可得出无顶点忽略(No Vertex Elimination,NVE)盲更新法的性能优于其他两种，所以反馈矩阵SFM中的所有非0(包括x)顶点都包含在IDNC图中。通过比较传输数据包Pj⊕Pl与分别传输Pj和Pl的译码时延[11]，决定是否将图中顶点νij和νkl相连。

2.1 译码时延的增加

pi(j)表示数据包Pj对于信宿节点Ri来说是创新型的概率。其在反馈丢失下表示为[12]：

(2)

其中，λij为信源节点最近一次从接收节点Ri收到反馈信息后尝试发送数据包Pj至Ri的次数[12]。

对于任意一个信宿节点及随机数据包，此数据包可带来新信息的概率为：

(3)

信宿节点Ri成功接收到其所需所有数据包的概率[12](由于反馈丢失)为：

(4)

利用式(4)，对于任意一个信宿节点，其仍需接收数据包的概率为：

(5)

以下探讨分别传输数据包Pj和Pl与传输编码包Pj⊕Pl的译码时延。D(j)表示信源节点发送数据包Pj后，信宿节点Ri和Rk总的译码时延增加：

D(j)=P(di(j)=1)+P(dk(j)=1)

(6)

结合译码时延定义，发送数据包Pj后，若Ri成功接收到一个非创新型数据包且其仍需接收数据包，则有一个单位的译码时延增加，如下：

(7)

同理

(8)

所以

同理可得发送数据包Pl后，信宿节点Ri和Rk总译码时延增加：

信宿节点Rk的译码时延增加与Ri类似，所以传输Pj⊕Pl后，Ri和Rk总的译码时延增加如下：

(11)

2.2 图的建立

由2.1可得新的IDNC图中顶点νij和νkl可由一条边相连的条件：

(1)C1：j=l，即两个不同信宿节点需要同一个数据包Pj；

(2)C2：dij,kl(j⊕l)≤min(dij,kl(j),dij,kl(l))，即传输数据包Pj⊕Pl后，信宿节点Ri和Rk总的译码时延增加少于分别传输Pj和Pl的译码时延增加。

3 提出的子代划分模型的思想

3.1 子代划分及其编码模型

通过第2节讨论得出新的IDNC图，利用启发式算法[13-14]找出所得反馈丢失下图中的IDNC最优解决方案。文中子代概念是在IDNC最优解决方案的基础上提出的。

定义2：子代是最优的IDNC解决方案中最大编码子集的集合，用G表示。

定义3：子代大小是指一个子代中最大编码子集的数量，用g表示。

则子代数量M=「UIDNC/g⎤，g∈[1,UIDNC]，第m个子代为Gm。其中，UIDNC是最优的IDNC解决方案下最大编码子集的数量，即最小编码传输次数。

构建的编码模型如下：最优的IDNC解决方案S={M1,M2,…,MUIDNC}，第一个子代G1={M1,M2,…,Mg}，第二个子代G2={Mg+1,Mg+2,…,M2g}，以此类推。再在每个子代中运用RLNC编码方法。划分子代[15]的方法如下：

初始化：输入IDNC编码模型下的最优解S={M1,M2,…,MUIDNC}和N个空的子代G1,G2,…,GN。

将S中UIDNC个最大编码子集按其在所有信宿节点处覆盖的需被解码的数据包数的降序排列。

Forn=1:N

Fori=1:g

若查找到了M′，则将M′加入Gn中；若未查找到M′，则将S中第一个最大编码子集加入Gn中。

将选中的最大编码子集从S中删除。

If集合S为空

算法终止。

End If

End

End

子代划分后在每个子代中应用RLNC模型，这种划分方法对系统吞吐量及时延性能的影响讨论如下。

3.2 子代划分对吞吐量及时延的影响

推论1：∀g∈[1,UIDNC]，Ug∈[URLNC,UIDNC]。

4 仿真结果及分析

仿真中，主要研究了反馈信息丢失情况下子代大小在不同信宿节点数量以及不同包丢失率时对系统性能的影响。所有信宿节点的包丢失率pi及反馈丢失率qi在一帧发送期间是保持不变的，且在每次仿真期间它们的平均值P和Q保持不变[13]。

在第一个仿真中，设信宿节点的包丢失率平均值P和反馈丢失率平均值Q分别为0.25、0.15，源数据包N=15，信宿节点数在5到40之间变化。分析子代的大小g分别取1,2,…,UIDNC时的系统吞吐量和数据包的平均译码时延，仿真结果如图2所示。

图2 P=0.25和Q=0.15时的系统性能

从图2(a)中可观察到，子代g大时比g小时吞吐量性能好，且吞吐量的变化都在IDNC与RLNC吞吐量之间，进一步验证了推论1。由图2(b)可知，当信宿节点数M>22时，子代大小g=1时的平均译码时延比g=UIDNC时的平均译码时延大，子代大小g=2和g=3时系统平均译码时延介于IDNC系统和RLNC系统的平均译码时延之间，与3.2节推论一致。

在第二个仿真中，设源数据包N=15，信宿节点数M=50，信宿节点的反馈丢失率的平均值Q=0.5P，包丢失率pi在0至0.8之间变化。分析子代的大小g分别取1,2,…,UIDNC时的系统吞吐量和包的平均译码时延性能，仿真结果如图3所示。

图3 Q=0.5P不同包丢失率时的系统性能

从图3(a)中可以观察到，子代g大时比g小时吞吐量性能要好，且吞吐量的变化都在IDNC与RLNC吞吐量之间，与第一个仿真中类似，进一步验证了推论1。如图3(b)所示，当pi≥0.1时，子代大小g=1时的平均译码时延比g=UIDNC时的平均译码时延要大，而当pi≥0.65后，则g越小平均译码时延也越小，且平均译码时延仍介于IDNC系统和RLNC系统的平均译码时延之间,仍符合3.2节推论。

5 结束语

文中主要研究在反馈信息丢失情况下构建新的IDNC图，在图的基础上得出最优的IDNC解决方案，进一步提出子代的概念以及子代的划分，从而构建IDNC与RLNC相联系的网络编码模型。此模型考虑了IDNC与RLNC系统在吞吐量与时延性能方面完全不同的特性，它们只是在特定子代大小下的两个极端例子，可通过选择子代大小在吞吐量与时延之间进行权衡。

[1]AhlswedeR,CaiN,LiSYR,etal.Networkinformationflow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216.

[2]SorourS,ValaeeS.Minimunbroadcastdecodingdelayforgeneralizedinstantlydecodablenetworkcoding[C]//IEEEglobaltelecommunicationsconference.[s.l.]:IEEE,2010:1-5.

[3]KoetterR,MédardM.Analgebraicapproachtonetworkcoding[J].IEEE/ACMTransactionsonNetworking,2003,11(5):782-795.

[4]FragouliC,LunD,MédardM,etal.Onfeedbackfornetworkcoding[C]//2007 41stannualconferenceoninformationsciencesandsystems.[s.l.]:IEEE,2007:248-252.

[5]EryilmazA,OzdaglarA,MédardM,etal.Onthedelayandthroughputgainsofcodinginunreliablenetworks[J].IEEETransactionsonInformationTheory,2008,54(12):5511-5524.

[6]HoT,MédardM,KoetterR,etal.Arandomlinearnetworkcodingapproachtomulticast[J].IEEETransactionsonInformationTheory,2006,52(10):4413-4430.

[7]SadeghiP,ShamsR,TraskovD.Anoptimaladaptivenetworkcodingschemeforminimizingdecodingdelayinbroadcasterasurechannels[J].EURASIPJournalonWirelessCommunicationsandNetworking,2010(1):14.

[8]SadeghiP,YuM.Instantlydecodableversusrandomlinearnetworkcoding:acomparativeframeworkforthroughputanddecodingdelayperformance[J].InformationTheory,2012,39(8):2387.

[9]YuMingchao,AboutorabN,SadeghiP.Rapprochementbetweeninstantlydecodableandrandomlinearnetworkcoding[C]//IEEEinternationalsymposiumoninformationtheory.[s.l.]:IEEE,2013:3090-3094.

[10]SorourS,ValaeeS.Effectoffeedbacklossoninstantlydecodablenetworkcoding[C]//7thinternationalwirelesscommunicationsandmobilecomputingconference.[s.l.]:[s.n.],2011.

[11]DouikA,SorourS,Al-NaffouriTY,etal.Alossygraphmodelfordelayreductioningeneralizedinstantlydecodablenetworkcoding[J].IEEEWirelessCommunicationsLetters,2014,3(3):281-284.

[12]SorourS,DouikA,ValaeeS,etal.Partiallyblindinstantlydecodablenetworkcodesforlossyfeedbackenvironment[J].IEEETransactionsonWirelessCommunications,2014,13(9):4871-4883.

[13]DouikA,SorourS,AlouiniMS,etal.Delayminimizationforinstantdecodablenetworkcodinginpersistentchannelswithfeedbackintermittence[J].InformationTheory,2013,1309:1-15.

[14]DouikA,SorourS,AlouiniMS,etal.Delayreductioninlossyintermittentfeedbackforgeneralizedinstantlydecodablenetworkcoding[C]//IEEEinternationalconferenceonwirelessandmobilecomputing,networkingandcommunications.[s.l.]:[s.n.],2013:388-393.

[15] 杨叶舒，梅中辉.无线网络中网络编码子图优化问题的研究[J].计算机技术与发展，2014，24(3):86-89.

Network Coding Based on Sub-generation Partition with Feedback Loss

ZHU Xiao-yan，MEI Zhong-hui

(College of Telecommunication & Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Considering the different characteristics of IDNC and RLNC,a new network coding model is proposed to establish the relationship between them with feedback loss.This model is based on the construction of IDNC graph and the definition of sub-generation,which is built upon optimal IDNC solutions.RLNC is applied in each sub-generation after the sub-generation partition.IDNC and RLNC are only two extreme examples with specific sub-generation sizes.Throughput and delay measured by the number of coded transmissions and average packet decoding delay respectively,which fills the gap between IDNC and RLNC,provides a good understanding on the throughput-delay tradeoff of the network coding on consideration of feedback loss.Simulation results illustrate that how the sizes of sub-generation affect the overall system performance with the number of receivers and packet loss rate under the condition of feedback loss,and the theoretical analysis is in conformity with the actual calculation.The system performance of different sizes of sub-generation from 1 toUIDNCisbetweenthatofIDNCandRLNC.

network coding;feedback loss;sub-generation partition;coded transmission;decoding delay

2016-01-24

2016-05-18

时间：2016-10-24

国家科技重大专项(2010zx03003-003)

朱小燕(1990-)，女，硕士研究生，研究方向为网络编码技术、资源优化等；梅中辉，副教授，研究生导师，研究方向为网络编码技术、协助通信技术等。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1114.056.html

TP

A

1673-629X(2016)11-0072-05

10.3969/j.issn.1673-629X.2016.11.016