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

朱小燕，梅中輝

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

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

朱小燕，梅中輝

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

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

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

0 引 言

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

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

IDNC通過(guò)選擇合適的編碼數(shù)據(jù)包來(lái)保證一部分或所有信宿節(jié)點(diǎn)在成功接收編碼包后即時(shí)譯碼出所需的數(shù)據(jù)包，因而譯碼時(shí)延相對(duì)較小。但是IDNC的編碼傳輸次數(shù)較RLNC多，因?yàn)橐淮尉幋a傳輸對(duì)于部分信宿節(jié)點(diǎn)來(lái)說(shuō)可能無(wú)用。

網(wǎng)絡(luò)編碼系統(tǒng)中吞吐量與譯碼時(shí)延間的權(quán)衡為當(dāng)前一大研究熱點(diǎn)。且以前的大多數(shù)有關(guān)網(wǎng)絡(luò)編碼的研究都是假設(shè)來(lái)自信宿節(jié)點(diǎn)的反饋是非丟失的，但這個(gè)假設(shè)在許多實(shí)際情況中有其局限性。因?yàn)樵谛旁炊耍答亖G失很可能會(huì)由于無(wú)線鏈路的不可靠性而發(fā)生[10]。

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

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

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

圖1 無(wú)線廣播傳輸模型

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

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

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

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

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

(1)

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

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

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

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

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

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

2 反饋丟失下IDNC圖的建立

文中在反饋丟失下進(jìn)行研究，那么IDNC圖就不能如文獻(xiàn)[2]簡(jiǎn)單得出。

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

2.1 譯碼時(shí)延的增加

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

(2)

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

對(duì)于任意一個(gè)信宿節(jié)點(diǎn)及隨機(jī)數(shù)據(jù)包，此數(shù)據(jù)包可帶來(lái)新信息的概率為：

(3)

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

(4)

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

(5)

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

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

(6)

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

(7)

同理

(8)

所以

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

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

(11)

2.2 圖的建立

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

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

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

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

3.1 子代劃分及其編碼模型

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

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

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

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

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

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

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

Forn=1:N

Fori=1:g

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

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

If集合S為空

算法終止。

End If

End

End

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

3.2 子代劃分對(duì)吞吐量及時(shí)延的影響

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

文中主要研究在反饋信息丟失情況下構(gòu)建新的IDNC圖，在圖的基礎(chǔ)上得出最優(yōu)的IDNC解決方案，進(jìn)一步提出子代的概念以及子代的劃分，從而構(gòu)建IDNC與RLNC相聯(lián)系的網(wǎng)絡(luò)編碼模型。此模型考慮了IDNC與RLNC系統(tǒng)在吞吐量與時(shí)延性能方面完全不同的特性，它們只是在特定子代大小下的兩個(gè)極端例子，可通過(guò)選擇子代大小在吞吐量與時(shí)延之間進(jìn)行權(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ú)線網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼子圖優(yōu)化問(wèn)題的研究[J].計(jì)算機(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

時(shí)間：2016-10-24

國(guó)家科技重大專項(xiàng)(2010zx03003-003)

朱小燕(1990-)，女，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)編碼技術(shù)、資源優(yōu)化等；梅中輝，副教授，研究生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)編碼技術(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