肖 巍，梅中輝

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

一種改進的即時解碼網(wǎng)絡編碼的無線重傳策略

肖 巍，梅中輝

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

為了充分利用網(wǎng)絡編碼的優(yōu)勢，文中提出一種改進的基于即時解碼網(wǎng)絡編碼的無線重傳策略。該策略從圖論(編碼機會)的角度出發(fā)，為了減少編碼數(shù)據(jù)包的重傳次數(shù)，在考慮剩余編碼機會和剩余數(shù)據(jù)包需求的條件下選擇編碼數(shù)據(jù)包，使每一步選擇的重傳編碼數(shù)據(jù)包組合能夠保證剩余編碼密度(實際編碼機會和最大編碼機會之比)最大，并且針對同等編碼密度的情況，進一步考慮平均解碼時延最小者為所選擇的網(wǎng)絡編碼重傳方式。研究表明，所提出的策略相對于服務最大需求數(shù)據(jù)包策略和隨機編碼子集選擇策略，能夠進一步減少重傳次數(shù)，降低平均解碼時延。

網(wǎng)絡編碼；重傳策略；解碼時延；編碼密度

0 引 言

在無線廣播信道中，網(wǎng)絡編碼[1]能夠顯著提高吞吐量和傳輸效率，吞吐量和傳輸效率的優(yōu)化是目前的研究熱點之一[2-9]。針對在無線網(wǎng)絡中由于存在刪除信道(Erasure Channel)而導致信宿節(jié)點不能成功收到所有的數(shù)據(jù)包的問題，已有人提出利用隨機線性網(wǎng)絡編碼[10]去解決，但在隨機線性網(wǎng)絡編碼模型下，信宿節(jié)點需要收到足夠多的數(shù)據(jù)包才能進行解碼，因此這種模型下的解碼時延非常大。為了確保無線傳輸?shù)目煽啃?，同時盡量提高傳輸效率，一種基于反饋矩陣的即時解碼網(wǎng)絡編碼(Instantly Decodable Network Coding,IDNC)[11]方案被提出。

為了優(yōu)化某一給定的性能指標，大部分的基于IDNC的數(shù)據(jù)包重傳策略只考慮每次傳輸解碼出的需求數(shù)，并未考慮重傳的編碼數(shù)據(jù)包組合對剩余編碼機會的影響。然而隨著編碼機會的減少，從中獲取的網(wǎng)絡編碼增益就會減少?；谶@一點，文獻[12]通過緩存未即時解碼的數(shù)據(jù)包來達到增加編碼機會的目的。由于文獻[12]中的方法并不適用于IDNC，Sorour S等提出一種基于IDNC的服務最大需求數(shù)據(jù)包策略(Most Wanted Packet Serving Strategy,MoWPS)[13]。該策略與隨機編碼子集選擇策略(Random clique selection,RND)[3]相比，能夠減少重傳次數(shù)；但是在出現(xiàn)同等編碼密度的情況下并沒有考慮選取哪種編碼數(shù)據(jù)包組合進行重傳。

基于上述原因，文中提出一種改進的基于即時解碼網(wǎng)絡編碼的無線重傳策略(Improved Retransmission Strategy based on Instantly Decodable Network Coding,IRS-IDNC)。IRS-IDNC每次選取的編碼數(shù)據(jù)包組合能夠最大化剩余編碼密度，并且在某一次出現(xiàn)多個同等剩余編碼密度的情況下，以最小化平均解碼時延為優(yōu)化目標去選取最優(yōu)編碼數(shù)據(jù)包組合。

1 系統(tǒng)模型

1.1 無線廣播傳輸模型

圖1 無線廣播傳輸模型

在上述廣播模型中，信源節(jié)點S首先用N個時隙依次將N個原始數(shù)據(jù)包廣播給M個信宿節(jié)點，此階段稱為系統(tǒng)傳輸階段。由于無線網(wǎng)絡下的信道衰落，并不能確保每個信宿節(jié)點都能全部接收到所有的原始數(shù)據(jù)包。在信源節(jié)點S將所有原始數(shù)據(jù)包廣播傳輸之后，信宿節(jié)點會將自身所接收到的原始數(shù)據(jù)包信息反饋給信源節(jié)點。

(1)

在經(jīng)歷了系統(tǒng)傳輸階段之后，接下來是編碼重傳階段。得到反饋矩陣F，圖2為一反饋矩陣示例，其中M=5，N=6。

圖2 反饋矩陣F

(1)j=l，說明i節(jié)點和k節(jié)點需要同一個數(shù)據(jù)包，如F中的V11和V21；

(2)j∈Hk,l∈Hi，說明i節(jié)點想要的數(shù)據(jù)包在k節(jié)點已接收的數(shù)據(jù)包集合中，并且k節(jié)點想要的數(shù)據(jù)包在i節(jié)點已接收的數(shù)據(jù)包集合中，如F中的V11和V42。

定義1(最大編碼子集C)：如果某一個編碼數(shù)據(jù)包組合滿足IDNC編碼約束條件，并且再加入任何一個數(shù)據(jù)包到該編碼組合都會導致信宿節(jié)點不能即時解碼，那么把這樣的編碼數(shù)據(jù)包組合稱為一個最大編碼子集。

圖3 IDNC無向圖

1.2 IDNC圖論思想

眾所周知，網(wǎng)絡編碼不僅能夠顯著提高傳輸效率和吞吐量，而且可以減少時延。很顯然，應該盡可能利用每一個編碼機會。

圖4 編碼數(shù)據(jù)包傳輸方式示例

從圖4(b)和(c)可以看出，為了充分利用網(wǎng)絡編碼的優(yōu)勢，選擇編碼數(shù)據(jù)包組合不僅要考慮單次傳輸解決的需求數(shù)目，還要考慮剩余的編碼機會數(shù)目。從(c)和(d)可以看出，在剩余編碼機會數(shù)相同的情況下，應選擇剩余頂點(需求)少的編碼數(shù)據(jù)包組合以減少傳輸次數(shù)。

2 IRS-IDNC編碼方案

2.1 IRS-IDNC思想與分析

根據(jù)1.2節(jié)的描述可知，為了充分利用網(wǎng)絡編碼機會，同時減少傳輸次數(shù)，選擇的編碼數(shù)據(jù)包組合應使剩余的編碼機會越大越好，同時使剩余的頂點數(shù)越少越好(此時剩余的最大編碼機會也相應變少)。也就是說，在傳輸完選取的編碼數(shù)據(jù)包組合之后，剩余的編碼密度應該越大越好。

(2)

(3)

引理3：系統(tǒng)平均解碼時延[15]為：

(4)

2.2 IRS-IDNC方案

為了能夠充分利用網(wǎng)絡編碼機會并且降低系統(tǒng)平均解碼時延，文中提出的IRS-IDNC方法如下：

(1)根據(jù)某一時刻得到的反饋矩陣，利用Bron-Kerbosch算法[16]找出該反饋矩陣對應的所有最大編碼子集；

(2)選擇某一個最大編碼子集C(稱為最優(yōu)編碼子集)進行傳輸，確保該最大編碼子集能夠包含盡量多的同求數(shù)據(jù)包，并且解碼盡量多的需求，也就是使式(5)的目標函數(shù)最大[13]：

(5)

其中，Ωj是需要數(shù)據(jù)包j的信宿節(jié)點數(shù)目。

如果在通過Bron-Kerbosch算法得到的最大編碼子集中，有兩個或多個最優(yōu)編碼子集，那么將保留該組最優(yōu)編碼子集，并假定系統(tǒng)分別選擇這些最優(yōu)編碼子集進行傳輸。后續(xù)每一次出現(xiàn)多個最優(yōu)編碼子集時，都按照此策略選擇編碼數(shù)據(jù)包直到反饋矩陣F更新全零矩陣。

(3)依次記錄由上述策略所得到的最大編碼子集傳輸序列。

(4)根據(jù)式(4)，分別計算每一個記錄下的最大編碼子集傳輸序列對應的平均解碼時延，并最終選取平均解碼時延最小的最大編碼子集序列進行重傳。

圖5 反饋矩陣和最大編碼子集樹圖

3 仿真結果及分析

為了驗證IRS-IDNC方案的有效性，文中使用MATLAB對圖1中的無線廣播信道傳輸模型進行仿真。主要對RND方案、MoWPS方案和文中提出的IRS-IDNC方案的平均傳輸次數(shù)和系統(tǒng)平均解碼時延進行仿真，并且對三者進行性能比較和分析。

首先，為確保能夠觀察性能指標在不同信宿節(jié)點M下的變化趨勢，設定每個信宿節(jié)點的丟包率Pe=0.2，原始數(shù)據(jù)包N=15，信宿節(jié)點M在5到30之間變化，并選取200個樣本數(shù)進行仿真，仿真結果如圖6(a)所示。

同樣，設定每個信宿節(jié)點的丟包率Pe=0.2，信宿節(jié)點個數(shù)M=15，數(shù)據(jù)包個數(shù)N在5到30之間變化，并選取200個樣本數(shù)進行仿真，仿真結果如圖6(b)所示。

(a)不同信宿節(jié)點時的系統(tǒng)性能

(b)不同數(shù)據(jù)包數(shù)目時的系統(tǒng)性能

從圖6中可以看出，三種方案的傳輸次數(shù)和平均解碼時延都隨著信宿節(jié)點或數(shù)據(jù)包個數(shù)增加而增加。其中，IRS-IDNC方案的傳輸次數(shù)和平均解碼時延優(yōu)于RND方案和MoWPS方案。這是因為RND方案在選擇最大編碼子集時是進行隨機選取的，而沒有考慮剩余的編碼機會，MoWPS方案的最大編碼子集選擇雖然考慮了剩余編碼機會，但是沒有進一步考慮當多個最大編碼子集的剩余編碼密度相同時，如何使系統(tǒng)平均解碼時延最??；而IRS-IDNC方案既充分利用了編碼機會，而且當出現(xiàn)多個最大編碼子集而導致編碼密度相同的情況時，以最小化系統(tǒng)平均解碼時延為目標去選取最大編碼子集，從而可相應降低系統(tǒng)平均解碼時延。

4 結束語

文中主要借助圖論思想從編碼機會的角度對基于IDNC的無線廣播重傳問題進行了研究。為了充分利用網(wǎng)絡編碼的優(yōu)勢，針對MoWPS策略沒有考慮如何處理出現(xiàn)多個最大編碼子集對應的剩余編碼密度相同的情況，文中結合編碼密度和平均解碼時延，提出了IRS-IDNC方案。仿真結果與分析表明，與RND方案和MoWPS方案相比，IRS-IDNC能夠有效減少重傳次數(shù)，降低系統(tǒng)平均解碼時延。

[1] Ahlswede R,Cai N,Li S Y R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.

[2] Sundararajan J K,Shah D,Medard M.Online network coding for optimal throughput and delay-the three-receiver case[C]//Proc of international symposium on information theory and its applications.[s.l.]:IEEE,2008.

[3] Keller L,Drinea E,Fragouli C,et al.Online broadcasting with network coding[C]//Proc of fourth workshop on network coding theory & applications.Hong Kong:[s.n.],2008.

[4] Drinea E,Fragouli C,Keller L.Delay with network coding and feedback[C]//Proceedings of ISIT.[s.l.]:[s.n.],2009:844-848.

[5] Rouayheb S E,Chaudhry M A R,Sprintson A,et al.On the minimum number of transmissions in single-hop wireless coding networks[C]//Proc of information theory workshop.[s.

l.]:IEEE,2007:120-125.

[6] Dong N,Nguyen T,Xue Y.Multimedia wireless transmission with network coding[C]//Packet video 2007.Lausanne,Switzerland:IEEE,2007:326-335.

[7] Seferoglu H,Markopoulou A.Video-aware opportunistic network coding over wireless networks[J].IEEE Journal on Selected Areas in Communications,2009,27(5):713-728.

[8] Seferoglu H,Markopoulou A.Opportunistic network coding for video streaming over wireless[C]//Packet video 2007.Lausanne,Switzerland:IEEE,2007:191-200.

[9] Sundararajan J K,Sadeghi P,Médard M.A feedback-based adaptive broadcast coding scheme for reducing in-order delivery delay[C]//Proc of IEEE workshop on network coding,theory and application.Lausanne:IEEE,2009:1-6.

[10] Ho T,Medard M,Koetter R,et al.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[11] Sadeghi P,Shams R,Traskov D.An optimal adaptive network coding scheme for minimizing decoding delay in broadcast erasure channels[J].EURASIP Journal on Wireless Communications & Networking,2010,2010:50-50.

[12] Wang C C.On the capacity of 1-to-K broadcast packet erasure channels with channel output feedback[J].IEEE Transactions on Information Theory,2010,58(2):1347-1354.

[13] Sorour S,Valaee S.Coding opportunity densification strategies for instantly decodable network coding[J].IEEE Transactions on Communications,2013,61:5077-5089.

[14] Harris J M,Hirst J L,Mossinghoff M J.Combinatorics and graph theory[M]//Undergraduate texts in mathematics.Berlin:Springer,2008.

[15] Yu M,Sadeghi P,Aboutorab N.On the throughput and decoding delay performance of instantly decodable network coding[J].IEEE/ACM Trans on Networking,2013,67:1309-1310.

[16] Bron C,Kerbosch J.Algorithm 457:finding all cliques of an undirected graph[J].Communication of the ACM,1973,16(9):575-577.

An Improved Wireless Retransmission Strategy Based on Instantly Decodable Network Coding

XIAO Wei,MEI Zhong-hui

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

To take full advantage of the advantages of network coding,an improved wireless retransmission strategy based on instantly decodable network coding is proposed in this paper.This strategy is researched with graph theory.In order to reduce the numbers of broadcast retransmissions,when doing the selection of a coding combination，the remaining coding opportunity and remaining packet requests are considered.So each coding packet of selection can maximize the remaining coding density (the ratio of the number of actual coding opportunities to the maximum number of coding opportunities).If the number of optimal selection is large with the same coding density,the retransmissions will be chosen to minimize the average decoding delay.Research illustrates that the strategy proposed in this paper is possible to reduce the numbers of retransmissions and average decoding delay compared with most wanted packet serving strategy and random clique selection strategy.

network coding;retransmission strategy;decoding delay;coding density

2015-06-13

2015-09-18

時間：2016-02-18

國家科技重大專項(2010zx03003-003)

肖 巍(1990-)，男，碩士研究生，研究方向為網(wǎng)絡編碼技術、資源優(yōu)化等；梅中輝，副教授，碩士研究生導師，研究方向為網(wǎng)絡編碼技術、協(xié)助通信技術等。

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

TP301

A

1673-629X(2016)03-0144-05

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