一種改進的即時解碼網絡編碼的無線重傳策略

肖 巍，梅中輝

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

一種改進的即時解碼網絡編碼的無線重傳策略

肖 巍，梅中輝

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

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

網絡編碼；重傳策略；解碼時延；編碼密度

0 引 言

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

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

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

1 系統模型

1.1 無線廣播傳輸模型

圖1 無線廣播傳輸模型

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

(1)

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

圖2 反饋矩陣F

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

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

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

圖3 IDNC無向圖

1.2 IDNC圖論思想

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

圖4 編碼數據包傳輸方式示例

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

2 IRS-IDNC編碼方案

2.1 IRS-IDNC思想與分析

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

(2)

(3)

引理3：系統平均解碼時延[15]為：

(4)

2.2 IRS-IDNC方案

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

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

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

(5)

其中，Ωj是需要數據包j的信宿節點數目。

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

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

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

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

3 仿真結果及分析

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

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

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

(a)不同信宿節點時的系統性能

(b)不同數據包數目時的系統性能

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

4 結束語

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

[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-)，男，碩士研究生，研究方向為網絡編碼技術、資源優化等；梅中輝，副教授，碩士研究生導師，研究方向為網絡編碼技術、協助通信技術等。

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