肖 巍，梅中輝

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

一種改進(jìn)的即時(shí)解碼網(wǎng)絡(luò)編碼的無線重傳策略

肖 巍，梅中輝

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

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

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

0 引 言

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

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

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

1 系統(tǒng)模型

1.1 無線廣播傳輸模型

圖1 無線廣播傳輸模型

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

(1)

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

圖2 反饋矩陣F

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

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

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

圖3 IDNC無向圖

1.2 IDNC圖論思想

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

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

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

2 IRS-IDNC編碼方案

2.1 IRS-IDNC思想與分析

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

(2)

(3)

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

(4)

2.2 IRS-IDNC方案

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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

時(shí)間：2016-02-18

國(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.20160218.1634.044.html

TP301

A

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

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