一種改進的網(wǎng)絡(luò)編碼廣播重傳算法

王　驍

(中國電子科技集團公司第20研究所 通信事業(yè)部， 陜西 西安 710068)

一種改進的網(wǎng)絡(luò)編碼廣播重傳算法

王驍

(中國電子科技集團公司第20研究所 通信事業(yè)部， 陜西 西安 710068)

摘要在無線網(wǎng)絡(luò)廣播傳輸中，為了提升效率提出改進的基于冗余避免的網(wǎng)絡(luò)編碼廣播重傳算法(INCBRRA)。對接收狀態(tài)矩陣進行重排列后，再主動避免重傳不可解碼的編碼組合，從而優(yōu)先編碼有助于接收節(jié)點解碼的丟失數(shù)據(jù)包組合。分析結(jié)果表明，INCBRRA算法相比于現(xiàn)有算法能有效減少重傳次數(shù)，提升了傳輸效率。

關(guān)鍵詞無線網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；冗余避免；廣播重傳

網(wǎng)絡(luò)編碼[1]使得網(wǎng)絡(luò)中間節(jié)點能夠?qū)D(zhuǎn)發(fā)信息進行編碼，在接收節(jié)點進行解碼，從而提高網(wǎng)絡(luò)吞吐率，并帶來安全方面的優(yōu)勢?；诰W(wǎng)絡(luò)編碼在提升無線傳輸效率方面的優(yōu)點[2]，近年來出現(xiàn)了多種網(wǎng)絡(luò)編碼應(yīng)用于無線廣播重傳[3-5]的相關(guān)研究。

無線網(wǎng)絡(luò)廣播可使多個終端同時收到數(shù)據(jù)，是一種廣泛應(yīng)用的數(shù)據(jù)傳輸技術(shù)，尤其在衛(wèi)星通信中應(yīng)用普遍。然而，由于無線鏈路容易受到各種干擾，影響了無線廣播的可靠性，重傳則是提高可靠性的重要手段。現(xiàn)有的無線廣播重傳有兩類：自動重傳請求和基于網(wǎng)絡(luò)編碼的重傳方法。2006年，Nguyen[3]等將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于重傳策略中，提出了兩個接收節(jié)點情況下的編碼重傳策略，減少了平均傳輸次數(shù)，提高了重傳效率。文獻[5～6]利用反饋丟包的信息，節(jié)點對多個需要重傳的數(shù)據(jù)包進行編碼組合，再廣播重傳，稱為NCWBR方法。文獻[7]針對編碼包不可譯且接收節(jié)點較多的情況，提出改進的基于網(wǎng)絡(luò)編碼的廣播重傳策略，稱為INCBR方法。文獻[8]提出主動避免編碼冗余的高效網(wǎng)絡(luò)編碼廣播重傳策略，優(yōu)先編碼重傳對解碼貢獻較大的丟失數(shù)據(jù)包，稱為NCRA方法。文獻[9]提出一種基于并行機會式網(wǎng)絡(luò)編碼重傳方案，利用并行機制降低算法復(fù)雜度。文獻[10]實現(xiàn)了基于機會式網(wǎng)絡(luò)編碼的單組合分組廣播傳輸算法和多組合分組廣播傳輸算法，有效降低了廣播傳輸所需的傳輸帶寬。

本文提出改進的基于冗余避免網(wǎng)絡(luò)編碼的廣播重傳方法，接收節(jié)點將不能解碼的編碼包進行緩存，并且每次重傳前對接收狀態(tài)矩陣進行重新排列，優(yōu)先發(fā)送傳輸中損耗率較高的數(shù)據(jù)包同時避免不能解碼的編碼組合被重復(fù)編碼，從而提升廣播重傳的性能。

1系統(tǒng)模型

假設(shè)有一個衛(wèi)星作為信源節(jié)點S，并有N(N≥2)個在S廣播范圍內(nèi)的用戶作為接收節(jié)點，構(gòu)成一個衛(wèi)星廣播網(wǎng)絡(luò)。

衛(wèi)星廣播重傳階段如下:

階段1 源節(jié)點S向N個接收節(jié)點廣播M個原始數(shù)據(jù)包，且各接收節(jié)點的丟包率相互獨立。

階段2 固定間隔Δt后，每個接收節(jié)點通過發(fā)送ACK/NACK反饋數(shù)據(jù)包的丟失情況，并且ACK/NACK不存在丟失情況，丟失情況包括數(shù)據(jù)包是否丟失，丟失數(shù)據(jù)包序列號和丟失節(jié)點序列號。

階段3 根據(jù)ACK/NACK生成廣播接收狀態(tài)矩陣R。

階段4 源節(jié)點S根據(jù)廣播接收狀態(tài)矩陣R進行數(shù)據(jù)包編碼重傳。

階段3中的數(shù)據(jù)包廣播接收狀態(tài)矩陣R定義如下：

定義1 數(shù)據(jù)包廣播接收狀態(tài)矩陣R是每個接收節(jié)點對M個原始數(shù)據(jù)包的接收情況反饋生成的N×M矩陣。矩陣的元素為0或1，其中R(i,j)=0表示第i個接收節(jié)點接收到了第j個原始數(shù)據(jù)包，R(i,j)=1則表示第i個接收節(jié)點未能接收到第j個原始數(shù)據(jù)包。

文獻[7]的NCRA算法基本思想是接收節(jié)點將不能解碼的編碼包進行緩存，源節(jié)點 在對丟失數(shù)據(jù)包進行編碼重傳時，主動避免已經(jīng)重傳過的不能解碼的編碼組合，同時優(yōu)先選擇最有助于解碼接收節(jié)點已緩存編碼包的丟失數(shù)據(jù)包進行異或編碼，并確保每個重傳編碼包都至少包含每個接收節(jié)點的一個丟失數(shù)據(jù)包。

引理1 根據(jù)本文的系統(tǒng)模型，當(dāng)n(n≤N)個接收節(jié)點丟失某個原始數(shù)據(jù)包，而另外N-n個接收節(jié)點丟失另一個原始數(shù)據(jù)包，那么應(yīng)用網(wǎng)絡(luò)編碼技術(shù)對這個兩個原始數(shù)據(jù)包進行組合，則可以在重傳后使得編碼包在接收節(jié)點具有可解性。

引理2 根據(jù)本文的系統(tǒng)模型，當(dāng)n(n≤N)個接收節(jié)點丟失某個原始數(shù)據(jù)包，而另外N-n個接收節(jié)點丟失另外多個原始數(shù)據(jù)包，且這些原始數(shù)據(jù)包在廣播狀態(tài)矩陣中每行當(dāng)且僅有一個原始數(shù)據(jù)包丟失。那么將所有丟失的原始數(shù)據(jù)包進行網(wǎng)絡(luò)編碼組合后，所有的接收節(jié)點都可以解碼。

2INCBRRA方法

2.1INCBRRA基本原理

本文提出一種改進的冗余避免網(wǎng)絡(luò)編碼廣播重傳方法(Improved Network Coding Broadcasting Retransmission Algorithm Based Redundancy Avoiding, INCBRRA)，在NCRA算法的基礎(chǔ)上提高原始數(shù)據(jù)包的編碼效率。

首先，在ACK/NACK反饋原始數(shù)據(jù)包丟失情況的基礎(chǔ)上對其進行編碼重傳，編碼時避免重傳不能解碼的丟失原始數(shù)據(jù)包的編碼組合。

其次，在對原始數(shù)據(jù)包進行編碼組合時，通過調(diào)整廣播接收狀態(tài)矩陣的列向量，實現(xiàn)優(yōu)先發(fā)送損耗率較高的原始數(shù)據(jù)包。

最后，在廣播接收狀態(tài)矩陣調(diào)整后的基礎(chǔ)上基于NCRA算法設(shè)計緩存集合C和緩存隊列Q。其中，緩存集合C記錄所有接收節(jié)點成功接收但不能解碼的編碼組合的集合，初始化C=Φ。緩存隊列Q，用來標(biāo)記出現(xiàn)在緩存集合 中的丟失數(shù)據(jù)包對于解碼緩存中所有編碼包的貢獻程度，當(dāng)貢獻程度一樣時，將序號越小的數(shù)據(jù)包優(yōu)先級設(shè)置越高，丟失數(shù)據(jù)包按照優(yōu)先級從低到高組成緩存隊列Q，初始化隊列Q=Φ。

2.2INCBRRA算法步驟

步驟1 源節(jié)點S依據(jù)ACK/NACK生成廣播接收狀態(tài)矩陣R。

步驟2 源節(jié)點S對R按照每一列元素“1”的多少進行從大到小前后調(diào)整。

步驟3 源節(jié)點S在R的每一行尋找第一個“1”數(shù)據(jù)的位置且該數(shù)據(jù)包滿足可解性條件，并將其組成初始編碼序列I。

步驟4S檢查緩存集合C，如果C為空，進入步驟 6。否則，判斷I中是否包含有C中的組合，如果沒有，則進入步驟5。如果I中包含有C中的組合，則對這些組合進行刪除，按照緩存隊列Q中的順序依次刪除組合中的丟失數(shù)據(jù)包，直到I中不再包含C中的組合，不將這個組合包含的所有丟失數(shù)據(jù)包都刪除。

步驟5S檢查I是否至少包含了每個接收節(jié)點的一個丟失數(shù)據(jù)包。如果是，則將數(shù)據(jù)包編碼后廣播發(fā)送；如果不是，選取該接收節(jié)點對應(yīng)行的第一個還未參與過編碼的丟失數(shù)據(jù)包加入I，組成重傳編碼序列IF，將IF中的數(shù)據(jù)包編碼后廣播發(fā)送。

步驟6 源節(jié)點S根據(jù)ACK判斷編碼包是否被各接收節(jié)點成功接收。如果編碼包被成功接收，S依據(jù)重傳編碼序列IF和接收狀態(tài)矩陣R，更新緩存集合C和緩存隊列Q。隨后將R中參與編碼的對應(yīng)位置元素置為“0”。

在步驟6中需要更新緩存集合C和緩存隊列Q。緩存集合C和緩存隊列Q的具體更新方法如下：首先根據(jù)接收狀態(tài)矩陣，查找出IF中包含的接收節(jié)點丟失數(shù)據(jù)包組成的不能解碼的編碼組合，然后查找出IF中已經(jīng)在原緩存集合C中該節(jié)點對應(yīng)的編碼組合的丟失數(shù)據(jù)包，得到當(dāng)前接收節(jié)點在IF中不能解碼的組合。如果沒有找到這樣的組合，表示該節(jié)點能夠解碼IF組成的編碼包，再根據(jù)解碼出的丟失數(shù)據(jù)包對該節(jié)點在C中的組合進行更新。更新完緩存集合C后，將緩存隊列Q清零。然后統(tǒng)計C中各丟失數(shù)據(jù)包在C中出現(xiàn)的頻率，再按照頻率升序排列，如果頻率一樣，則將數(shù)據(jù)包序號大的排在前面，組成新的緩存隊列Q。

3應(yīng)用分析

在一個由單個信源節(jié)點和5個接收節(jié)點組成無線廣播網(wǎng)絡(luò)中，信源節(jié)點向接收節(jié)點R1,R2,R3,R4,R5廣播10個數(shù)據(jù)包M1,M2,M3,M4,M5,M6,M7,M8,M9,M10，用圖1表示接收節(jié)點的初始接收狀態(tài)矩陣。

M1M2M3M4M5M6M7M8M9M10R10110011000R20010010100R31101000100R41010100010R50010001001

圖1初始接收狀態(tài)矩陣

3.1NCRA算法應(yīng)用

針對圖1的初始接收狀態(tài)矩陣，NCRA算法首先初始化緩存集合C和緩存隊列Q為空集，并根據(jù)接收狀態(tài)矩陣選取每行第1個丟包的序號組成第1次編碼序列I1={M1,M2,M3}。第1次最終編碼序列IF1=I1，第1次發(fā)送的編碼包為M1⊕M2⊕M3，通過與表1對比可知，IF1包含了R1的丟包M2和M3，R3的丟包M1和M2，以及R4的丟包M1和M3。這3個接收節(jié)點不能對該編碼包進行解碼，從而根據(jù)算法更新緩存后，C={(M2,M3),(M1,M2),(M1,M3)}，Q={M3,M2,M1}。

源節(jié)點第2次選擇初始編碼序列I2={M2,M6,M1,M7}，I2中包含了C中的(M1,M2)組合，按照Q中數(shù)據(jù)包的順序，刪除I2中的M2后得到第2次最終編碼序列IF2={M6,M1,M7}，第2次發(fā)送的編碼包為M6⊕M1⊕M7。此時的IF2包含了R1的丟包M6和M7，據(jù)此更新緩存后，C={(M2,M3),(M6,M7)}，Q={M7,M6,M2,M3}。

源節(jié)點第3次選擇初始編碼序列I3={M2,M8,M3.M10}，I3中包含C中的(M2,M3)組合，從而根據(jù)Q中數(shù)據(jù)包順序刪除I3中的M2后得到第3次最終編碼序列IF3={M8,M3,M10}，發(fā)送的編碼包為M8⊕M3⊕M10。此時，每個接收節(jié)點都可以解碼，因此C和Q更新為空集。

源節(jié)點第4次選擇初始編碼序列I4={M2,M5}，IF4=I4，發(fā)送的編碼包為M2⊕M5。此時，每個接收節(jié)點都可以解碼，因此C和Q更新為空集。

源節(jié)點第5次選擇初始編碼序列I5={M6,M4,M9}，IF5=I5，發(fā)送的編碼包為M6⊕M4⊕M9。此時，每個接收節(jié)點都可以解碼，因此C和Q更新為空集。

源節(jié)點第6次選擇初始編碼序列I6={M7}，IF6=I6，發(fā)送的編碼包為M7，至此5個接收節(jié)點均收到10個原始數(shù)據(jù)包。

3.2INCBRRA算法應(yīng)用

首先按照算法步驟對圖1所示的初始接收狀態(tài)矩陣進行重新排序后，得到如表2所示的接收狀態(tài)矩陣。

M3M2M6M8M7M1M4M5M9M10R11110100000R21011010000R30101011000R41000000110R51000100001

圖2第1次重排序的接收狀態(tài)矩陣

源節(jié)點針對圖2所示，第1次選擇初始編碼序列I1={M3，M4}。在R3所處的行選擇數(shù)據(jù)包時，考慮到令I(lǐng)1不包含R1和R2兩個丟失數(shù)據(jù)包，因此不選擇M2，M8，M1，最終選擇數(shù)據(jù)包M4。此時，第1次發(fā)送的編碼包為M3⊕M4，所有接收節(jié)點均能解碼，那么C和Q為空集。

編碼包被接收節(jié)點解碼后，接收狀態(tài)矩陣會有相應(yīng)的變化，針對其變化按照算法對其進行重新排序后得到如圖3所示的接收狀態(tài)矩陣。

M6M2M8M7M1M5M9M10M4M3R11101000000R21010100000R30110100000R40000011000R50001000100

圖3第2次重排序的接收狀態(tài)矩陣

源節(jié)點針對表3，第2次選擇編碼序列I2={M6,M2,M5,M10}，在R3所處的行選擇數(shù)據(jù)包時，所有可選擇的數(shù)據(jù)包M2,M8,M1均會令I(lǐng)2包含R1和R2兩個丟失數(shù)據(jù)包，因此按照算法，仍舊選擇第一個數(shù)據(jù)包M2；在R5所處的行選擇數(shù)據(jù)包時，考慮到選擇M7會令I(lǐng)2包含R1的兩個丟失數(shù)據(jù)包，因此選擇M10；最終發(fā)送的編碼包為M6⊕M2⊕M5⊕M10；此時I2包含R1的兩個丟失數(shù)據(jù)包M6和M2，更新緩存后C={(M6,M2)}，Q={M6,M2}。

編碼包被接收節(jié)點解碼后，接收狀態(tài)矩陣會有相應(yīng)的變化，針對其變化按照算法對其進行重新排序后得到如圖4所示的接收狀態(tài)矩陣。

M7M8M1M6M2M9M10M4M3M5R11001100000R20110000000R30110000000R40000010000R51001000000

圖4第3次重排序的接收狀態(tài)矩陣

源節(jié)點針對圖4所示，第3次選擇編碼序列I3={M7,M8,M9}，發(fā)送的編碼包為M7⊕M8⊕M9，所有接收節(jié)點均能解碼，那么C和Q更新為空集。

編碼包被接收節(jié)點解碼后，接收狀態(tài)矩陣會有相應(yīng)的變化，針對其變化按照算法對其進行重新排序后得到如表5所示的接收狀態(tài)矩陣。

M1M6M2M10M4M3M5M7M8M9R10110000000R21000000000R31000000000R40000000000R50000000000

圖5第4次重排序的接收狀態(tài)矩陣

源節(jié)點針對圖5所示，第4次選擇編碼序列I4={M6,M1}，發(fā)送的編碼包為M6⊕M1，所有接收節(jié)點均能解碼，C和Q仍為空集。編碼包被接收節(jié)點解碼后，接收狀態(tài)矩陣會有相應(yīng)的變化，針對其變化按照算法對其進行重新排序后得到如圖6所示的接收狀態(tài)矩陣。

M2M10M4M3M5M7M8M9M6M1R11000000000R20000000000R30000000000R40000000000R50000000000

圖6第5次重排序的接收狀態(tài)矩陣

源節(jié)點針對圖6所示，第5次選擇編碼序列I5={M2}，發(fā)送的編碼包為M2。

至此，所有5個接收節(jié)點均收到10個原始數(shù)據(jù)包。從算法應(yīng)用分析可以看出，INCBRRA算法相比于NCRA算法，減少了重傳次數(shù)，提高了廣播重傳效率。

4結(jié)束語

本文利用網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)傳輸中的應(yīng)用，提出一種改進的基于冗余避免網(wǎng)絡(luò)編碼廣播重傳方法，根據(jù)接收節(jié)點反饋的緩存編碼包信息，同時考慮傳送損耗率較高的丟失數(shù)據(jù)包和避免傳送不能被解碼的丟失數(shù)據(jù)包組合，達到了減少廣播重傳次數(shù)和提升傳輸效率的目的。

參考文獻

[1]Ahlswede R,Cai N, SYR L, et al. Network information flow [J]. IEEE Transactions on Information Theory,2000 (46): 1204-1206.

[2]Katti S, Rahul H, Hu W, et al. Xors in the air: practical wireless network coding[C].Shanghai: SIGCOMM,2006.

[3]Neguyen D,Nguyen T,Bose B,Wireless broadcasting using network coding [R].Oregan: Technical Report: OSU-TR-2006-06, Oregon State University,2006.

[4]Wu Y, Chou P A, Kung S Y. Information exchange in wireless networks with network coding and physical-layer broadcast [R].CA,USA: Technical Report MSR-TR -2004-78, Microsoft Research,2004.

[5]肖瀟,王偉平,楊路明,等.基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)廣播重傳方法[J]. 通信學(xué)報,2009,30(9):69-75.

[6]肖瀟,楊路明,王偉平.高損耗無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的廣播重傳策略[J].中南大學(xué)學(xué)報:自然科學(xué)版,2008,39(6):1291-1295.

[7]孫偉,張更新,邊東明,等.衛(wèi)星通信中基于網(wǎng)絡(luò)編碼改進的廣播重傳策略[J]. 宇航學(xué)報,2013,34(2):231-236.

[8]姚玉坤,陳曦,任智,等.基于冗余避免的高效網(wǎng)絡(luò)編碼廣播重傳方法[J].系統(tǒng)工程與電子技術(shù),2015,37(5):1170-1176.

[9]王斌,王文鼐.一種基于并行網(wǎng)絡(luò)編碼的無線廣播重傳方案[J]. 南京郵電大學(xué)學(xué)報:自然科學(xué)版,2014,34(6):9-14.

[10]盧冀,吳成柯,肖嵩,等.基于機會式網(wǎng)絡(luò)編碼的高效廣播傳輸算法[J].通信學(xué)報,2012,33(1):64-70.

An Improved Broadcast Retransmission Algorithm Based on Network Coding

WANG Xiao

(Communications Division，China Electronics Technology Group Corporation No.20 Institute, Xi’an 710068, China)

AbstractFor the purpose of improving the transmission efficiency of the network coding broadcasting retransmission method, thus reducing the retransmission times, an improved network coding broadcasting retransmission algorithms based on redundancy avoiding(INCBRRA) is proposed. After rearrange the receive matrix, it voluntarily avoids redundant transmission of the combination which can not decoded by the receiving nodes, and preferentially codes the lost packets which are conducive to decoding. The analysis results shows that compared to existing algorithms, INCBRRA can reduce the number of retransmission times and improve the transmission efficiency.

Keywordswireless network; network coding; redundancy avoiding; broadcasting retransmission

收稿日期:2015-04-29

作者簡介:王驍(1984-)，男，博士，工程師。研究方向：網(wǎng)絡(luò)編碼，數(shù)據(jù)通信。

doi:10.16180/j.cnki.issn1007-7820.2016.06.018

中圖分類號TN926

文獻標(biāo)識碼A

文章編號1007-7820(2016)06-061-04