王　驍

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

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

王驍

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

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

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

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

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

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

1系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

2INCBRRA方法

2.1INCBRRA基本原理

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

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

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

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

2.2INCBRRA算法步驟

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

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

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

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

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

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

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

3應(yīng)用分析

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

M1M2M3M4M5M6M7M8M9M10R10110011000R20010010100R31101000100R41010100010R50010001001

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

3.1NCRA算法應(yīng)用

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

源節(jié)點(diǎn)第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。此時(shí)的IF2包含了R1的丟包M6和M7，據(jù)此更新緩存后，C={(M2,M3),(M6,M7)}，Q={M7,M6,M2,M3}。

源節(jié)點(diǎn)第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。此時(shí)，每個(gè)接收節(jié)點(diǎn)都可以解碼，因此C和Q更新為空集。

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

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

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

3.2INCBRRA算法應(yīng)用

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

M3M2M6M8M7M1M4M5M9M10R11110100000R21011010000R30101011000R41000000110R51000100001

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

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

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

M6M2M8M7M1M5M9M10M4M3R11101000000R21010100000R30110100000R40000011000R50001000100

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

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

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

M7M8M1M6M2M9M10M4M3M5R11001100000R20110000000R30110000000R40000010000R51001000000

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

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

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

M1M6M2M10M4M3M5M7M8M9R10110000000R21000000000R31000000000R40000000000R50000000000

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

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

M2M10M4M3M5M7M8M9M6M1R11000000000R20000000000R30000000000R40000000000R50000000000

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

[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é)報(bào),2009,30(9):69-75.

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

[7]孫偉,張更新,邊東明,等.衛(wèi)星通信中基于網(wǎng)絡(luò)編碼改進(jìn)的廣播重傳策略[J]. 宇航學(xué)報(bào),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é)報(bào):自然科學(xué)版,2014,34(6):9-14.

[10]盧冀,吳成柯,肖嵩,等.基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的高效廣播傳輸算法[J].通信學(xué)報(bào),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

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

doi:10.16180/j.cnki.issn1007-7820.2016.06.018

中圖分類號(hào)TN926

文獻(xiàn)標(biāo)識(shí)碼A

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