反饋丟失下基于子代劃分的網絡編碼

朱小燕，梅中輝

(南京郵電大學 通信與信息工程學院，江蘇 南京 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