朱小燕，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

反饋丟失下基于子代劃分的網(wǎng)絡編碼

朱小燕，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

考慮在反饋丟失的情況下，根據(jù)即時解碼的網(wǎng)絡編碼(Instantly Decodable Network Coding，IDNC)和隨機線性網(wǎng)絡編碼(Random Linear Network Coding，RLNC)不同的特性，提出一種新的網(wǎng)絡編碼模型來建立兩者之間的關(guān)系。該模型依賴于反饋丟失下IDNC圖的建立以及最優(yōu)IDNC解決方案下子代概念的提出，子代劃分后在每個子代中應用RLNC的編碼模型，且IDNC和RLNC只是該模型下具有特定子代大小的兩個極端例子。這種機制把IDNC和RLNC聯(lián)系在一起，便于更好地理解在反饋丟失下吞吐量與時延之間的權(quán)衡。仿真結(jié)果反映了反饋信息丟失情況下子代大小在不同信宿節(jié)點數(shù)量以及不同包丟失率時對系統(tǒng)性能的影響,且結(jié)果表明理論分析與實際計算相吻合，子代大小介于1和UIDNC之間的系統(tǒng)性能(如編碼傳輸次數(shù)、平均譯碼時延)則介于IDNC和RLNC的系統(tǒng)性能之間。

網(wǎng)絡編碼；反饋丟失；子代劃分；編碼傳輸；譯碼時延

0 引 言

網(wǎng)絡編碼[1]在提升無線廣播系統(tǒng)的性能方面有較大優(yōu)勢,這些系統(tǒng)中信宿節(jié)點需快速可靠地接收數(shù)據(jù)包[2]。信源節(jié)點或中間節(jié)點對數(shù)據(jù)包進行編碼處理后發(fā)送能提高網(wǎng)絡中的吞吐量，但這往往會以較大譯碼時延為代價[3-5]。在各類文獻中，基于不同應用系統(tǒng)采用了多種網(wǎng)絡編碼，例如RLNC[6]和IDNC[2,7-8]。

RLNC最先由Tracy等[6]提出，在一個給定有限域內(nèi)隨機選取編碼系數(shù),當接收節(jié)點收到一定數(shù)量的編碼向量線性無關(guān)的數(shù)據(jù)包時，即可完成網(wǎng)絡譯碼。同IDNC比較,RLNC編碼傳輸次數(shù)[9]較少。但是因為必須在所有編碼數(shù)據(jù)包傳輸完后才能譯碼出原始數(shù)據(jù)包，所以RLNC的譯碼時延較大。

IDNC通過選擇合適的編碼數(shù)據(jù)包來保證一部分或所有信宿節(jié)點在成功接收編碼包后即時譯碼出所需的數(shù)據(jù)包，因而譯碼時延相對較小。但是IDNC的編碼傳輸次數(shù)較RLNC多，因為一次編碼傳輸對于部分信宿節(jié)點來說可能無用。

網(wǎng)絡編碼系統(tǒng)中吞吐量與譯碼時延間的權(quán)衡為當前一大研究熱點。且以前的大多數(shù)有關(guān)網(wǎng)絡編碼的研究都是假設來自信宿節(jié)點的反饋是非丟失的，但這個假設在許多實際情況中有其局限性。因為在信源端，反饋丟失很可能會由于無線鏈路的不可靠性而發(fā)生[10]。

因此，文中在考慮反饋丟失下研究IDNC圖，根據(jù)RLNC與IDNC的特點建立RLNC與IDNC相關(guān)聯(lián)的網(wǎng)絡編碼模型。此模型有助于更好地理解吞吐量與時延間的權(quán)衡。模型的建立基于最優(yōu)IDNC解決方案下子代概念的提出，RLNC和IDNC只是該模型下具有特定子代大小的兩個極端例子。文中提及的IDNC均為廣義即時譯碼網(wǎng)絡編碼(Generalized Instantly Decodable Network Coding，G-IDNC[2])。

1 無線廣播系統(tǒng)反饋模型

如圖1所示的無線廣播系統(tǒng)中，一個信源節(jié)點S廣播發(fā)送N個源數(shù)據(jù)包至M個信宿節(jié)點，源數(shù)據(jù)包集合P={P1,P2,…,PN}，信宿節(jié)點集合R={R1,R2,…,RM}，每個信宿節(jié)點都需接收所有數(shù)據(jù)包。

圖1 無線廣播傳輸模型

此模型分為兩個傳輸階段。首先是系統(tǒng)傳輸階段：信源節(jié)點S利用N個時隙廣播發(fā)送N個原始未編碼數(shù)據(jù)包至每個信宿節(jié)點。第一階段后，每個信宿節(jié)點有三種包集合：

(1)集合Hi：信宿節(jié)點Ri成功收到并告知信源節(jié)點已收到的數(shù)據(jù)包集合；

(2)集合Wi：信宿節(jié)點Ri未收到或收到卻未成功告知信源節(jié)點已收到(即反饋丟失)的數(shù)據(jù)包集合；

(3)集合Ui：數(shù)據(jù)包狀態(tài)未知，Ui?Wi。

信源節(jié)點通過反饋矩陣(SenderFeedbackMatrix,SFM)儲存以上信息，反饋矩陣F=[fij]：

(1)

在編碼傳輸階段，信源節(jié)點發(fā)送Wi中數(shù)據(jù)包的編碼組合，編碼包分為：

(1)非創(chuàng)新型：此編碼包不包含Wi中的源數(shù)據(jù)包；

(2)即時譯碼型：此編碼包只包含Wi中的一個源數(shù)據(jù)包；

(3)非即時譯碼型：此編碼包包含Wi中的兩個或多個源數(shù)據(jù)包。

定義1：在任意一次編碼傳輸中，集合Wi非空的信宿節(jié)點Ri若成功收到一個非創(chuàng)新型或非即時譯碼型數(shù)據(jù)包，則Ri會增加一個單位的譯碼時延[2]。

這里假設傳輸與反饋信道都是無記憶可擦除信道，信宿節(jié)點Ri丟失數(shù)據(jù)包的概率為pi，反饋丟失概率為qi。信道中所有接收節(jié)點間相互獨立，且只有目標接收節(jié)點才發(fā)送反饋信息。

2 反饋丟失下IDNC圖的建立

文中在反饋丟失下進行研究，那么IDNC圖就不能如文獻[2]簡單得出。

通過三種盲IDNC圖更新法[10]的比較，可得出無頂點忽略(No Vertex Elimination,NVE)盲更新法的性能優(yōu)于其他兩種，所以反饋矩陣SFM中的所有非0(包括x)頂點都包含在IDNC圖中。通過比較傳輸數(shù)據(jù)包Pj⊕Pl與分別傳輸Pj和Pl的譯碼時延[11]，決定是否將圖中頂點νij和νkl相連。

2.1 譯碼時延的增加

pi(j)表示數(shù)據(jù)包Pj對于信宿節(jié)點Ri來說是創(chuàng)新型的概率。其在反饋丟失下表示為[12]：

(2)

其中，λij為信源節(jié)點最近一次從接收節(jié)點Ri收到反饋信息后嘗試發(fā)送數(shù)據(jù)包Pj至Ri的次數(shù)[12]。

對于任意一個信宿節(jié)點及隨機數(shù)據(jù)包，此數(shù)據(jù)包可帶來新信息的概率為：

(3)

信宿節(jié)點Ri成功接收到其所需所有數(shù)據(jù)包的概率[12](由于反饋丟失)為：

(4)

利用式(4)，對于任意一個信宿節(jié)點，其仍需接收數(shù)據(jù)包的概率為：

(5)

以下探討分別傳輸數(shù)據(jù)包Pj和Pl與傳輸編碼包Pj⊕Pl的譯碼時延。D(j)表示信源節(jié)點發(fā)送數(shù)據(jù)包Pj后，信宿節(jié)點Ri和Rk總的譯碼時延增加：

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

(6)

結(jié)合譯碼時延定義，發(fā)送數(shù)據(jù)包Pj后，若Ri成功接收到一個非創(chuàng)新型數(shù)據(jù)包且其仍需接收數(shù)據(jù)包，則有一個單位的譯碼時延增加，如下：

(7)

同理

(8)

所以

同理可得發(fā)送數(shù)據(jù)包Pl后，信宿節(jié)點Ri和Rk總譯碼時延增加：

信宿節(jié)點Rk的譯碼時延增加與Ri類似，所以傳輸Pj⊕Pl后，Ri和Rk總的譯碼時延增加如下：

(11)

2.2 圖的建立

由2.1可得新的IDNC圖中頂點νij和νkl可由一條邊相連的條件：

(1)C1：j=l，即兩個不同信宿節(jié)點需要同一個數(shù)據(jù)包Pj；

(2)C2：dij,kl(j⊕l)≤min(dij,kl(j),dij,kl(l))，即傳輸數(shù)據(jù)包Pj⊕Pl后，信宿節(jié)點Ri和Rk總的譯碼時延增加少于分別傳輸Pj和Pl的譯碼時延增加。

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

3.1 子代劃分及其編碼模型

通過第2節(jié)討論得出新的IDNC圖，利用啟發(fā)式算法[13-14]找出所得反饋丟失下圖中的IDNC最優(yōu)解決方案。文中子代概念是在IDNC最優(yōu)解決方案的基礎上提出的。

定義2：子代是最優(yōu)的IDNC解決方案中最大編碼子集的集合，用G表示。

定義3：子代大小是指一個子代中最大編碼子集的數(shù)量，用g表示。

則子代數(shù)量M=「UIDNC/g?，g∈[1,UIDNC]，第m個子代為Gm。其中，UIDNC是最優(yōu)的IDNC解決方案下最大編碼子集的數(shù)量，即最小編碼傳輸次數(shù)。

構(gòu)建的編碼模型如下：最優(yōu)的IDNC解決方案S={M1,M2,…,MUIDNC}，第一個子代G1={M1,M2,…,Mg}，第二個子代G2={Mg+1,Mg+2,…,M2g}，以此類推。再在每個子代中運用RLNC編碼方法。劃分子代[15]的方法如下：

初始化：輸入IDNC編碼模型下的最優(yōu)解S={M1,M2,…,MUIDNC}和N個空的子代G1,G2,…,GN。

將S中UIDNC個最大編碼子集按其在所有信宿節(jié)點處覆蓋的需被解碼的數(shù)據(jù)包數(shù)的降序排列。

Forn=1:N

Fori=1:g

若查找到了M′，則將M′加入Gn中；若未查找到M′，則將S中第一個最大編碼子集加入Gn中。

將選中的最大編碼子集從S中刪除。

If集合S為空

算法終止。

End If

End

End

子代劃分后在每個子代中應用RLNC模型，這種劃分方法對系統(tǒng)吞吐量及時延性能的影響討論如下。

3.2 子代劃分對吞吐量及時延的影響

推論1：?g∈[1,UIDNC]，Ug∈[URLNC,UIDNC]。

4 仿真結(jié)果及分析

仿真中，主要研究了反饋信息丟失情況下子代大小在不同信宿節(jié)點數(shù)量以及不同包丟失率時對系統(tǒng)性能的影響。所有信宿節(jié)點的包丟失率pi及反饋丟失率qi在一幀發(fā)送期間是保持不變的，且在每次仿真期間它們的平均值P和Q保持不變[13]。

在第一個仿真中，設信宿節(jié)點的包丟失率平均值P和反饋丟失率平均值Q分別為0.25、0.15，源數(shù)據(jù)包N=15，信宿節(jié)點數(shù)在5到40之間變化。分析子代的大小g分別取1,2,…,UIDNC時的系統(tǒng)吞吐量和數(shù)據(jù)包的平均譯碼時延，仿真結(jié)果如圖2所示。

圖2 P=0.25和Q=0.15時的系統(tǒng)性能

從圖2(a)中可觀察到，子代g大時比g小時吞吐量性能好，且吞吐量的變化都在IDNC與RLNC吞吐量之間，進一步驗證了推論1。由圖2(b)可知，當信宿節(jié)點數(shù)M>22時，子代大小g=1時的平均譯碼時延比g=UIDNC時的平均譯碼時延大，子代大小g=2和g=3時系統(tǒng)平均譯碼時延介于IDNC系統(tǒng)和RLNC系統(tǒng)的平均譯碼時延之間，與3.2節(jié)推論一致。

在第二個仿真中，設源數(shù)據(jù)包N=15，信宿節(jié)點數(shù)M=50，信宿節(jié)點的反饋丟失率的平均值Q=0.5P，包丟失率pi在0至0.8之間變化。分析子代的大小g分別取1,2,…,UIDNC時的系統(tǒng)吞吐量和包的平均譯碼時延性能，仿真結(jié)果如圖3所示。

圖3 Q=0.5P不同包丟失率時的系統(tǒng)性能

從圖3(a)中可以觀察到，子代g大時比g小時吞吐量性能要好，且吞吐量的變化都在IDNC與RLNC吞吐量之間，與第一個仿真中類似，進一步驗證了推論1。如圖3(b)所示，當pi≥0.1時，子代大小g=1時的平均譯碼時延比g=UIDNC時的平均譯碼時延要大，而當pi≥0.65后，則g越小平均譯碼時延也越小，且平均譯碼時延仍介于IDNC系統(tǒng)和RLNC系統(tǒng)的平均譯碼時延之間,仍符合3.2節(jié)推論。

5 結(jié)束語

文中主要研究在反饋信息丟失情況下構(gòu)建新的IDNC圖，在圖的基礎上得出最優(yōu)的IDNC解決方案，進一步提出子代的概念以及子代的劃分，從而構(gòu)建IDNC與RLNC相聯(lián)系的網(wǎng)絡編碼模型。此模型考慮了IDNC與RLNC系統(tǒng)在吞吐量與時延性能方面完全不同的特性，它們只是在特定子代大小下的兩個極端例子，可通過選擇子代大小在吞吐量與時延之間進行權(quán)衡。

[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] 楊葉舒，梅中輝.無線網(wǎng)絡中網(wǎng)絡編碼子圖優(yōu)化問題的研究[J].計算機技術(shù)與發(fā)展，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-)，女，碩士研究生，研究方向為網(wǎng)絡編碼技術(shù)、資源優(yōu)化等；梅中輝，副教授，研究生導師，研究方向為網(wǎng)絡編碼技術(shù)、協(xié)助通信技術(shù)等。

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