姚玉坤， 陳　曦， 任　智， 易建瓊， 雷宏江

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室， 重慶 400065)

?

基于冗余避免的高效網(wǎng)絡(luò)編碼廣播重傳方法

姚玉坤， 陳曦， 任智， 易建瓊， 雷宏江

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室， 重慶 400065)

摘要：為了提高無(wú)線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的廣播重傳方法的編碼效率，從而有效地減少重傳次數(shù)和數(shù)據(jù)包傳輸時(shí)延，提出一種主動(dòng)避免編碼冗余的高效網(wǎng)絡(luò)編碼廣播重傳方法(network coding broadcasting retransmission approach based on redundancy avoiding，NCRA)。NCRA編碼時(shí)主動(dòng)避免不能解碼的編碼組合被重復(fù)編碼重傳，同時(shí)優(yōu)先編碼重傳對(duì)接收節(jié)點(diǎn)已緩存的未解碼編碼包的解碼貢獻(xiàn)較大的丟失數(shù)據(jù)包以充分利用編碼機(jī)會(huì)，在對(duì)解碼貢獻(xiàn)相同的條件下優(yōu)先編碼較早丟失的數(shù)據(jù)包以減小數(shù)據(jù)包傳輸時(shí)延。理論分析和仿真結(jié)果表明，NCRA算法相比于現(xiàn)有算法能有效減小重傳次數(shù)和降低數(shù)據(jù)包傳輸時(shí)延，減少網(wǎng)絡(luò)開(kāi)銷，進(jìn)一步提高了編碼重傳的效率。

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

0引言

在無(wú)線網(wǎng)絡(luò)廣播傳輸中，由于無(wú)線鏈路的不可靠特點(diǎn)，極易造成數(shù)據(jù)包的丟失或者傳輸錯(cuò)誤，重傳是改善傳輸可靠性的有效方法[1]。網(wǎng)絡(luò)編碼(network coding, NC)的提出為提高無(wú)線網(wǎng)絡(luò)廣播重傳效率提供了新的解決思路[2]。

網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)中間節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)信息采用線性或者非線性的方式進(jìn)行編碼處理后轉(zhuǎn)發(fā)以提高數(shù)據(jù)的傳輸效率[3-5]。將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于廣播重傳，源節(jié)點(diǎn)在對(duì)接收節(jié)點(diǎn)丟失的數(shù)據(jù)包進(jìn)行重傳時(shí)，不是重傳單一的某個(gè)丟失數(shù)據(jù)包，而是將多個(gè)接收節(jié)點(diǎn)丟失的不同數(shù)據(jù)包進(jìn)行編碼組合后再重傳，實(shí)現(xiàn)通過(guò)一次發(fā)送就可以同時(shí)恢復(fù)多個(gè)接收節(jié)點(diǎn)的丟失數(shù)據(jù)包的效果，從而達(dá)到減少重傳發(fā)送次數(shù)、提高重傳效率的目的。

文獻(xiàn)[6]使用網(wǎng)絡(luò)編碼技術(shù)提出了在無(wú)線網(wǎng)絡(luò)中優(yōu)化吞吐量的方法。文獻(xiàn)[7]在無(wú)線Mesh網(wǎng)絡(luò)中提出了機(jī)會(huì)式網(wǎng)絡(luò)編碼，可以提高網(wǎng)絡(luò)吞吐量。文獻(xiàn)[8-9]將機(jī)會(huì)式網(wǎng)絡(luò)編碼思想應(yīng)用于無(wú)線網(wǎng)絡(luò)廣播重傳，可以改善重傳的性能。文獻(xiàn)[10]針對(duì)每個(gè)丟失數(shù)據(jù)包賦一個(gè)效用值，提出了基于Sort-By-Utility(SBU)的網(wǎng)絡(luò)編碼廣播重傳算法。但是其要求生成的編碼包必須能被所有接收節(jié)點(diǎn)解碼，因此參與編碼的原始數(shù)據(jù)包的個(gè)數(shù)受到限制，沒(méi)有充分利用每次編碼機(jī)會(huì)。文獻(xiàn)[11]在SBU算法的基礎(chǔ)上，提出了Benefit算法，接收節(jié)點(diǎn)從多個(gè)重傳包中恢復(fù)出丟失數(shù)據(jù)包，有效地提高了網(wǎng)絡(luò)吞吐量，但是其算法判斷條件較為復(fù)雜，不易實(shí)現(xiàn)。文獻(xiàn)[12]提出按照數(shù)據(jù)包的發(fā)送順序依次編碼丟失數(shù)據(jù)包的廣播重傳算法。但是當(dāng)丟包率較大，編碼包不能被解碼的概率較大的情況下，性能不佳。文獻(xiàn)[13]提出了基于機(jī)會(huì)式網(wǎng)絡(luò)編碼多組合分組廣播傳輸算法(opportunistic network coding based multiple combination packets broadcast transmission，ONCMB)，該算法將不能解碼的編碼包進(jìn)行緩存，通過(guò)后續(xù)成功恢復(fù)的丟失數(shù)據(jù)包來(lái)機(jī)會(huì)性地解碼緩存中的編碼包，從而減少重傳次數(shù)。但是該算法存在不能被解碼的丟失數(shù)據(jù)包組合被重復(fù)編碼重傳的情況，導(dǎo)致接收節(jié)點(diǎn)雖然能夠多次成功接收但均無(wú)法解碼這些編碼包的問(wèn)題，且需要單獨(dú)重傳丟失數(shù)據(jù)包來(lái)解碼緩存編碼包，因此降低了網(wǎng)絡(luò)重傳效率。

本文以上述研究工作為基礎(chǔ)，提出了主動(dòng)避免編碼冗余的網(wǎng)絡(luò)編碼廣播重傳方法(network coding broadcasting retransmission approach based on redundancy avoiding，NCRA)。NCRA算法的基本思想是：接收節(jié)點(diǎn)將不能解碼的編碼包進(jìn)行緩存，源節(jié)點(diǎn)在對(duì)丟失數(shù)據(jù)包進(jìn)行編碼重傳時(shí)，通過(guò)主動(dòng)避免已經(jīng)重傳過(guò)的不能解碼的編碼組合的冗余發(fā)送，同時(shí)優(yōu)先選擇能夠最有助于解碼接收節(jié)點(diǎn)已緩存編碼包和降低數(shù)據(jù)包傳輸時(shí)延的丟失數(shù)據(jù)包進(jìn)行編碼，并確保每個(gè)重傳編碼包都至少包含每個(gè)接收節(jié)點(diǎn)的一個(gè)丟失數(shù)據(jù)包，以提高每次編碼的有效性，達(dá)到進(jìn)一步改善重傳性能的目的。

1網(wǎng)絡(luò)模型及問(wèn)題描述

本文研究所使用的網(wǎng)絡(luò)模型與文獻(xiàn)[12-13]相同，是由一個(gè)廣播源節(jié)點(diǎn)和M(M≥2)個(gè)接收節(jié)點(diǎn)組成。廣播傳輸過(guò)程分為2個(gè)階段：原始數(shù)據(jù)包發(fā)送階段和丟失數(shù)據(jù)包編碼重傳階段。在原始數(shù)據(jù)包發(fā)送階段，假設(shè)廣播源節(jié)點(diǎn)以固定的時(shí)間間隔Δt廣播發(fā)送N個(gè)原始數(shù)據(jù)包，各接收節(jié)點(diǎn)通過(guò)同步發(fā)送控制包(acknowledgement/negative acknowledgment，ACK/NACK)到源節(jié)點(diǎn)來(lái)反饋數(shù)據(jù)包的接收狀態(tài)，并假設(shè)ACK/NACK控制包不存在丟失，且各接收節(jié)點(diǎn)的丟包率相互獨(dú)立。在丟失數(shù)據(jù)包編碼重傳階段，源節(jié)點(diǎn)對(duì)所有接收節(jié)點(diǎn)丟失的數(shù)據(jù)包進(jìn)行編碼重傳。源節(jié)點(diǎn)將不同接收節(jié)點(diǎn)的丟失數(shù)據(jù)包進(jìn)行異或運(yùn)算編碼后重傳，這樣不同的接收節(jié)點(diǎn)可以從一個(gè)編碼包中恢復(fù)各自的丟失數(shù)據(jù)包，能夠提高網(wǎng)絡(luò)重傳性能。

定義 1數(shù)據(jù)包接收狀態(tài)矩陣T。是指廣播源節(jié)點(diǎn)根據(jù)各接收節(jié)點(diǎn)對(duì)所有原始數(shù)據(jù)包的接收情況的反饋而生成的矩陣。假設(shè)網(wǎng)絡(luò)中有M個(gè)接收節(jié)點(diǎn)(R1,R2,…,RM-1, RM)，源節(jié)點(diǎn)在原始數(shù)據(jù)包發(fā)送階段發(fā)送了N個(gè)數(shù)據(jù)包(P1,P2,…,PN-1, PN)，則T則為M行N列的0/1矩陣。矩陣中的元素為“0”表示對(duì)應(yīng)行的接收節(jié)點(diǎn)成功接收到了對(duì)應(yīng)列的數(shù)據(jù)包，為“1”則表示丟失了該數(shù)據(jù)包。

定理 1如果編碼包中包含了某個(gè)接收節(jié)點(diǎn)的2個(gè)及以上丟失數(shù)據(jù)包，則該接收節(jié)點(diǎn)將不能解碼編碼包。

證明假設(shè)編碼包A(P1⊕P2…Pi-1⊕Pi…Pj⊕Pj+1…Ps)，包含了接收節(jié)點(diǎn)R1的任意2個(gè)丟失數(shù)據(jù)包Pi和Pj，根據(jù)異或運(yùn)算解碼可得。

(1)

從式(1)可知，R1不能解碼編碼包A，因此不能恢復(fù)出丟失數(shù)據(jù)包Pi和Pj。同理可知，當(dāng)編碼包A包含了R1的2個(gè)以上丟失數(shù)據(jù)包時(shí)也不能被解碼，從而定理1成立。

證畢

文獻(xiàn)[13]提出的機(jī)會(huì)式網(wǎng)絡(luò)編碼多組合分組廣播傳輸算法ONCMB，在對(duì)丟失數(shù)據(jù)包進(jìn)行編碼重傳時(shí)包含以下2個(gè)階段。

階段1：源節(jié)點(diǎn)依次選取接收狀態(tài)矩陣中每行對(duì)應(yīng)的第1個(gè)丟失數(shù)據(jù)包組成重傳編碼包，而后接收節(jié)點(diǎn)反饋ACK/NACK控制包說(shuō)明其是否收到傳輸?shù)木幋a數(shù)據(jù)包。如果收到，則將接收狀態(tài)矩陣中所選取編碼的丟失數(shù)據(jù)包位置置為“0”。接收節(jié)點(diǎn)將不能解碼的編碼包進(jìn)行緩存。依次類推，直到所有編碼包成功發(fā)送。

階段2：源節(jié)點(diǎn)根據(jù)發(fā)送的所有編碼包的信息，查找接收節(jié)點(diǎn)沒(méi)有成功恢復(fù)的ε(ε≥2)個(gè)丟失數(shù)據(jù)包，重傳ε-1個(gè)不可恢復(fù)的丟失數(shù)據(jù)包，接收節(jié)點(diǎn)再通過(guò)解碼緩存的編碼包獲取最后一個(gè)丟失數(shù)據(jù)包。

ONCMB算法有效地提高了重傳性能，但仍存在以下不足。

(1)ONCMB算法編碼時(shí)存在已經(jīng)重傳過(guò)的不能解碼的丟失數(shù)據(jù)包編碼組合被冗余發(fā)送的情況。這樣會(huì)導(dǎo)致已經(jīng)緩存有該編碼組合的接收節(jié)點(diǎn)一定不能解碼該編碼包，且占用了其他丟失數(shù)據(jù)包參與編碼的機(jī)會(huì)。當(dāng)接收狀態(tài)矩陣中所有為“1”位置的丟失數(shù)據(jù)包都參與了編碼后，存在接收節(jié)點(diǎn)仍有緩存編碼包沒(méi)有被解碼，相應(yīng)的丟失數(shù)據(jù)包沒(méi)有被恢復(fù)，源節(jié)點(diǎn)需要再重傳丟失數(shù)據(jù)包來(lái)解碼，從而導(dǎo)致重傳次數(shù)增加，數(shù)據(jù)包傳輸時(shí)延增大等問(wèn)題。

(2)ONCMB算法中接收節(jié)點(diǎn)將不能解碼的編碼包進(jìn)行緩存。該算法沒(méi)有考慮到源節(jié)點(diǎn)如何主動(dòng)利用這些已經(jīng)緩存的編碼包信息來(lái)優(yōu)化源節(jié)點(diǎn)的編碼方法，以較少的發(fā)送次數(shù)通過(guò)后續(xù)的重傳使接收節(jié)點(diǎn)可以較快的將緩存中的編碼包解碼出來(lái)。

2NCRA方法的編碼原理

2.1NCRA基本思想與方法描述

在對(duì)丟失數(shù)據(jù)包進(jìn)行編碼重傳時(shí)，如果要求生成的編碼包必須能被所有接收節(jié)點(diǎn)可解，參與編碼的丟失數(shù)據(jù)包受到限制，影響重傳效率。因此NCRA算法同ONCMB算法一樣，允許接收節(jié)點(diǎn)對(duì)編碼包不能立即解碼的情況存在，且仍將不能解碼的編碼包進(jìn)行緩存。

NCRA算法的主要?jiǎng)?chuàng)新思想如下：

(1) 編碼重傳時(shí)，避免已經(jīng)重傳過(guò)的不能解碼的丟失數(shù)據(jù)包編碼組合的重復(fù)發(fā)送，去除編碼冗余，提高編碼效率。

(2) 源節(jié)點(diǎn)利用接收節(jié)點(diǎn)的緩存編碼包信息來(lái)實(shí)現(xiàn)優(yōu)先對(duì)解碼緩存編碼包貢獻(xiàn)較大的丟失數(shù)據(jù)包進(jìn)行編碼，提高緩存編碼包解碼效率。

(3) 優(yōu)先編碼較早丟失的數(shù)據(jù)包以降低數(shù)據(jù)包傳輸時(shí)延。

(4) 保證每個(gè)編碼包都包含所有存在丟包情況的接收節(jié)點(diǎn)的至少一個(gè)丟失數(shù)據(jù)包，以盡快恢復(fù)所有接收節(jié)點(diǎn)的丟失數(shù)據(jù)包。

設(shè)計(jì)緩存集合C和緩存隊(duì)列Q，分別用以記錄接收節(jié)點(diǎn)緩存的編碼組合信息和存儲(chǔ)丟失數(shù)據(jù)包對(duì)解碼緩存編碼包的貢獻(xiàn)優(yōu)先級(jí)。

定義 2緩存集合C，用來(lái)記錄所有接收節(jié)點(diǎn)成功接收但不能解碼的編碼組合的集合。源節(jié)點(diǎn)根據(jù)接收狀態(tài)矩陣，將參與編碼重傳的丟失數(shù)據(jù)包組合中所有接收節(jié)點(diǎn)不能解碼的編碼組合進(jìn)行記錄。初始化C=?。

定義 3緩存隊(duì)列Q，用來(lái)標(biāo)記出現(xiàn)在緩存集合C中的丟失數(shù)據(jù)包對(duì)于解碼緩存中所有編碼包的貢獻(xiàn)程度。某丟失數(shù)據(jù)包出現(xiàn)在集合C中的頻率越大，說(shuō)明恢復(fù)該丟失該數(shù)據(jù)包能夠解碼出較多的編碼包，因此該丟失數(shù)據(jù)包對(duì)于解碼緩存中的所有編碼包越重要，即貢獻(xiàn)程度越大，編碼優(yōu)先級(jí)越高。如果頻率一樣，為了降低數(shù)據(jù)包恢復(fù)時(shí)延，將包序號(hào)越小的數(shù)據(jù)包設(shè)優(yōu)先級(jí)越高。將出現(xiàn)在緩存集合C中的丟失數(shù)據(jù)包按照優(yōu)先級(jí)從低到高組成緩存隊(duì)列Q。初始化隊(duì)列Q=?。

NCRA算法具體步驟如下：

步驟 1在丟失數(shù)據(jù)包編碼重傳階段，源節(jié)點(diǎn)根據(jù)所建立的數(shù)據(jù)包接收狀態(tài)矩陣，依次選取每行第一個(gè)為“1”的丟失數(shù)據(jù)包組成初始編碼序列S。

步驟 2源節(jié)點(diǎn)檢查緩存集合C，如果集合C為空，則直接進(jìn)入步驟3。否則，判斷S中是否包含有C中的組合，如果沒(méi)有，則進(jìn)入步驟3。如果S中包含有C中的組合，則對(duì)這些組合進(jìn)行刪除。刪除組合時(shí)按照緩存隊(duì)列Q中的順序依次刪除組合中的丟失數(shù)據(jù)包，直到S中不再包含C中的組合，不將這個(gè)組合包含的所有丟失數(shù)據(jù)包都刪除。

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

步驟 4接收節(jié)點(diǎn)通過(guò)ACK向源節(jié)點(diǎn)反饋該編碼包是否成功接收。

步驟 5根據(jù)各接收節(jié)點(diǎn)的反饋，如果成功接收該編碼包，源節(jié)點(diǎn)依據(jù)編碼序列SF和接收狀態(tài)矩陣，更新集合C和隊(duì)列Q。隨后將接收狀態(tài)矩陣中參與編碼的對(duì)應(yīng)位置置為“0”。

緩存集合C和緩存隊(duì)列Q的具體更新方法如下：

首先根據(jù)接收狀態(tài)矩陣，查找出SF中包含的接收節(jié)點(diǎn)丟失數(shù)據(jù)包組成的不能解碼的編碼組合，然后查找出SF中已經(jīng)在原緩存集合C中該節(jié)點(diǎn)對(duì)應(yīng)的編碼組合的丟失數(shù)據(jù)包，得到當(dāng)前接收節(jié)點(diǎn)在SF中不能解碼的組合。如果沒(méi)有找到這樣的組合，表示該節(jié)點(diǎn)能夠解碼SF組成的編碼包，再根據(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。

對(duì)上述方法舉例說(shuō)明如下。假設(shè)Sf={Pr,Pt,Pu,Pv}，接收節(jié)點(diǎn)R1在原緩存集合C中的不可解碼的組合為{(Px,Pr)}，且在接收狀態(tài)矩陣中，R1對(duì)Sf中的對(duì)應(yīng)數(shù)據(jù)包的接收狀態(tài)是{0,1,1,0}。首先依據(jù)接收狀態(tài)矩陣，查找出SF中R1不能解碼的組合{Pt,Pu}。然后查找出SF中的數(shù)據(jù)包出現(xiàn)在R1對(duì)應(yīng)的原緩存集合C中的組合的丟失數(shù)據(jù)包。

(2)

此時(shí)可得Sf中R1不能解碼的編碼組合為(Pr,Pt,Pu)。根據(jù)R1節(jié)點(diǎn)更新C為{(Px,Pr), (Pr ,Pt,Pu)}。

2.2NCRA算法的應(yīng)用分析

下面以圖1為例對(duì)NCRA與ONCMB算法進(jìn)行應(yīng)用分析。圖1表示源節(jié)點(diǎn)根據(jù)5個(gè)接收節(jié)點(diǎn)對(duì)10個(gè)原始數(shù)據(jù)包的反饋信息生成的接收狀態(tài)矩陣。為了便于分析，假設(shè)編碼包不存在丟失。在圖1中，不同的幾何符號(hào)(即三角形、圓形、長(zhǎng)方形、正六邊形)分別用來(lái)標(biāo)記第1、2、3、4次參與編碼重傳的丟失數(shù)據(jù)包。

用圖1(a)來(lái)具體闡述ONCMB重傳方法的應(yīng)用結(jié)果。在階段一中，源節(jié)點(diǎn)依次發(fā)送4個(gè)編碼包(P1⊕P2⊕P3)，(P2⊕P3⊕P6⊕P7)，(P4⊕P5⊕P6⊕P8⊕P10)，(P7⊕P8⊕P9)。將矩陣中所有為“1”位置的丟失數(shù)據(jù)包編碼重傳后，源節(jié)點(diǎn)需要通過(guò)發(fā)送的所有編碼包信息來(lái)計(jì)算是否有接收節(jié)點(diǎn)還有數(shù)據(jù)包未被恢復(fù)，即是否存在接收節(jié)點(diǎn)有緩存編碼包沒(méi)有被解碼。通過(guò)計(jì)算得出R1有數(shù)據(jù)包P2和P3未被恢復(fù)(具體計(jì)算方法見(jiàn)參考文獻(xiàn)[13])。進(jìn)入階段2，重傳丟失數(shù)據(jù)包P2(圖1(a)中用虛線標(biāo)出)，并通過(guò)解碼緩存中的編碼包可恢復(fù)出丟失數(shù)據(jù)包P3，從而恢復(fù)所有丟包。從圖1(a)可知，編碼包P1⊕P2⊕P3和P2⊕P3⊕P6⊕P7均同時(shí)包含了R1節(jié)點(diǎn)的丟包P2和P3，R1不能對(duì)這2個(gè)編碼包解碼，進(jìn)行緩存。P2⊕P3⊕P6⊕P7再次包含了R1不能解碼的編碼組合P2⊕P3，因此這個(gè)組合的發(fā)送對(duì)于R1來(lái)講是冗余的，而且也占用了R1其他丟失數(shù)據(jù)包參與編碼的機(jī)會(huì)。針對(duì)圖1而言，應(yīng)用ONCMB算法一共需要5次重傳才能恢復(fù)所有節(jié)點(diǎn)丟失的數(shù)據(jù)包。

圖1　NCRA與ONCMB算法的應(yīng)用

下面結(jié)合圖1(b)詳細(xì)闡述NCRA重傳算法的應(yīng)用結(jié)果。Si(i=1,2,3…)表示每次編碼重傳NCRA算法選擇的初始編碼序列，SFi表示每次重傳最終發(fā)送的編碼序列。

NCRA算法首先初始化緩存集合C、緩存隊(duì)列Q為空集，并根據(jù)接收狀態(tài)矩陣選取每行第1個(gè)丟包的序號(hào)組成第1次初始編碼序列S1={P1, P2, P3}。由于C、Q為空集，因此第1次最終編碼序列SF1=S1，源節(jié)點(diǎn)第1次發(fā)送的編碼包是P1⊕P2⊕P3。根據(jù)圖1，SF1包含了R1的丟包P2和P3，R3的丟包P1和P2，R4的丟包P1和P3，這3個(gè)接收節(jié)點(diǎn)將不能對(duì)該編碼包進(jìn)行解碼，會(huì)進(jìn)行緩存，所以更新緩存集合C為{( P2,P3),( P1,P2),( P1,P3)}，隊(duì)列Q為{P3, P2, P1}。

源節(jié)點(diǎn)第2次選擇初始編碼序列S2={P2, P3, P6, P7}。對(duì)比集合C，可知S2中包含了C中的(P2, P3)組合。于是按照隊(duì)列Q中的丟失數(shù)據(jù)包順序應(yīng)刪除數(shù)據(jù)包P3，則編碼序列變?yōu)?P2, P6, P7)。由于(P2, P6, P7)僅包含了R1，R2，R3，R5的丟包，未包含R4的丟包。故選擇矩陣的第4行中未在已經(jīng)重傳過(guò)的編碼包中出現(xiàn)的第1個(gè)數(shù)據(jù)丟包“P5”加入編碼序列，組成SF2為{P2, P5, P6,P7}。源節(jié)點(diǎn)第2次發(fā)送的編碼包是P2⊕P5⊕P6⊕P7。這個(gè)編碼包發(fā)送以后，除了R1，其他節(jié)點(diǎn)都能對(duì)其解碼。根據(jù)緩存集合C的更新方法，更新C為{(P2, P3),(P1,P3),(P2, P6, P7)}，更新Q為{P7, P6, P1, P3, P2}。

源節(jié)點(diǎn)第3次選擇編碼序列S3={P3,P4,P8,P10}，未包含集合C中的組合。因此SF3=S3={P3,P4,P8,P10}。隨后更新C為{(P6,P7)}，Q為{P7,P6}。

源節(jié)點(diǎn)第4次選擇編碼組合序列S4={P7,P8,P9}，沒(méi)有包含集合C中的組合，故取SF4=S4為{P7,P8,P9}。至此，所有接收節(jié)點(diǎn)可以通過(guò)解碼緩存中的編碼包成功恢復(fù)出之前的所有丟包。由此可見(jiàn)，對(duì)圖1而言，應(yīng)用NCRA算法一共只需4次編碼重傳，達(dá)到了理論下限值。相比ONCMB，NCRA減少了編碼包的重傳次數(shù)，提高了重傳性能。

定理 2當(dāng)同一接收節(jié)點(diǎn)的多個(gè)丟失數(shù)據(jù)包被編碼在全部編碼包中的編碼組合信息都一樣時(shí)，該接收節(jié)點(diǎn)將不能解碼這多個(gè)丟包的編碼組合。

證明假設(shè)Px和Py是同一接收節(jié)點(diǎn)的2個(gè)丟包，并假設(shè)在全部編碼包中的編碼組合信息都一樣，即 Px和Py要么同時(shí)被編碼在某個(gè)編碼包中，要么同時(shí)不被編碼在編碼包中。根據(jù)異或運(yùn)算解碼，解碼的結(jié)果是Px⊕Py或者0，不能解碼出Px或者Py。同理可知，大于2個(gè)丟包的編碼組合也是如此。

證畢

令Ei(n)=1(1≤i≤k, 1≤n≤N,)表示數(shù)據(jù)包Pn編碼于SFi，反之Ei(n)=0表示Pn 未編碼于SFi。其中，k表示重傳階段生成的重傳編碼包的總數(shù)。Ei(n)=1(1≤i≤k)組成編碼矩陣E，表示數(shù)據(jù)包參與重傳編碼包中的信息。

根據(jù)上圖1(a)和1(b)中，得出ONCMB與NCRA算法的編碼矩陣Ea和Eb，如圖2所示。

圖2　NCRA與ONCMB算法的應(yīng)用

從圖2(a)中可以看出，丟失數(shù)據(jù)包P2和P3,在全部編碼包中的編碼信息都一樣。同理還有P4和P5，P8和P9。但是只有P2和P3同時(shí)是R1節(jié)點(diǎn)的丟包。因此R1節(jié)點(diǎn)接收到所有編碼包以后也不能解碼出P2和P3。

圖2(b)表明的是，由于NCRA算法在編碼時(shí)，不能解碼的丟失數(shù)據(jù)包編碼組合不會(huì)重復(fù)出現(xiàn)在其他編碼包中，所以同一接收節(jié)點(diǎn)的多個(gè)丟包的編碼信息一定會(huì)不一樣。當(dāng)編碼階段結(jié)束，所有的編碼包都將會(huì)被解碼。NCRA算法不需要ONCMB算法第2階段的重傳發(fā)送，減少了重傳發(fā)送次數(shù)，有效地提高了重傳性能。

3NCRA算法性能的理論分析

假定網(wǎng)絡(luò)中有M個(gè)接收節(jié)點(diǎn)，各接收節(jié)點(diǎn)的丟包率服從伯努利分布且互不相關(guān)。令li表示接收節(jié)點(diǎn) Ri(1≤i≤M)的丟包率，lmax=Max(li)，并假設(shè)源節(jié)點(diǎn)在廣播原始數(shù)據(jù)包階段一共發(fā)送了N個(gè)原始數(shù)據(jù)包。

3.1平均傳輸次數(shù)

定義 4數(shù)據(jù)包平均傳輸次數(shù)UA，是指為了使所有接收節(jié)點(diǎn)最終成功接收N個(gè)原始數(shù)據(jù)包，源節(jié)點(diǎn)所需的對(duì)原始數(shù)據(jù)包的平均傳輸次數(shù)，其大小為

(3)

式中，H表示重傳階段的總的傳輸次數(shù)，H/N是原始數(shù)據(jù)包的平均重傳次數(shù)的大小，記為Ha。

(4)

(5)

由式(5)可知，數(shù)據(jù)包平均重傳次數(shù)為

(6)

代入式(3)可得

(7)

由于ONCMB在將所有丟失數(shù)據(jù)包編碼重傳后，有接收節(jié)點(diǎn)緩存的編碼包不能被解碼，源節(jié)點(diǎn)需要再重傳丟失數(shù)據(jù)包來(lái)解碼緩存編碼。所以O(shè)NCMB的平均傳輸次數(shù)UB為

(8)

式中，η表示ONCMB通過(guò)發(fā)送丟失數(shù)據(jù)包來(lái)解碼緩存編碼包的平均傳輸次數(shù)。對(duì)比式(7)和式(8)可知，NCRA算法的平均傳輸次數(shù)小于ONCMB算法。

3.2數(shù)據(jù)包平均傳輸時(shí)延

定義 5數(shù)據(jù)包平均傳輸時(shí)延D(n)，表示所有接收節(jié)點(diǎn)成功接收到第n(1≤n≤N)個(gè)數(shù)據(jù)包Pn的平均傳輸時(shí)延。用dx表示接收節(jié)點(diǎn)Ri(1≤i≤M)成功收到數(shù)據(jù)包Pn的傳輸時(shí)延，di(n)表示該傳輸時(shí)延均值。

如果數(shù)據(jù)包Pn在Ri節(jié)點(diǎn)沒(méi)有出現(xiàn)丟失，Pn的傳輸時(shí)延dx為

(9)

式中，Δt表示源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的時(shí)間間隔大小。

若Pn在Ri出現(xiàn)丟失，當(dāng)N個(gè)數(shù)據(jù)包發(fā)送完以后，則需要通過(guò)重傳恢復(fù)Pn的時(shí)延dx為

(10)

式中，Ha表示原始數(shù)據(jù)包的平均重傳次數(shù)(見(jiàn)式(6))；n×Ha為n個(gè)數(shù)據(jù)包的重傳次數(shù)。

由于Ri節(jié)點(diǎn)的丟包率為li，故，Ri成功收到數(shù)據(jù)包Pn的平均時(shí)延di(n)為

(11)

NCRA在所有接收節(jié)點(diǎn)成功接收Pn的平均傳輸時(shí)延為

(12)

使用ONCMB算法時(shí)，有一部分丟失數(shù)據(jù)包是在編碼重傳階段結(jié)束后，源節(jié)點(diǎn)通過(guò)單獨(dú)重傳這些丟失數(shù)據(jù)包來(lái)恢復(fù)的，這些丟失數(shù)據(jù)包的傳輸時(shí)延較大，為Δt×(N+N×Ha)，因此這一部分丟失數(shù)據(jù)包的平均傳輸時(shí)延為

(13)

對(duì)比式(11)和式(13)可知ONCMB的數(shù)據(jù)包平均傳輸時(shí)延大于NCRA算法。

另外，NCRA算法在對(duì)丟失數(shù)據(jù)包進(jìn)行編碼重傳時(shí)，除了考慮優(yōu)先重傳能夠使得接收節(jié)點(diǎn)緩存中的編碼包解碼的丟失數(shù)據(jù)包以后，還考慮優(yōu)先傳輸數(shù)據(jù)包序號(hào)較小的丟失數(shù)據(jù)包。丟失數(shù)據(jù)包的序號(hào)越小，表明該數(shù)據(jù)包越早被丟失，所以優(yōu)先傳輸數(shù)據(jù)包序號(hào)較小的丟失數(shù)據(jù)包，能夠降低數(shù)據(jù)包傳輸時(shí)延。

3.3算法復(fù)雜度

NCRA算法主要包括編碼和更新2部分。在編碼部分中，由于數(shù)據(jù)包接收狀態(tài)矩陣為M×N矩陣，選取初始編碼序列的時(shí)間復(fù)雜度為o(M×N)。緩存隊(duì)列Q的可能最大長(zhǎng)度為N，根據(jù)緩存優(yōu)先級(jí)來(lái)組成重傳編碼序列的時(shí)間復(fù)雜度為o(N)。在集合C和隊(duì)列Q的更新部分中，由于初始編碼序列的可能最大長(zhǎng)度為M，且需要判斷的次數(shù)即是接收節(jié)點(diǎn)的個(gè)數(shù)為M，所以更新集合C的時(shí)間復(fù)雜度為o(M2)。依據(jù)集合C更新隊(duì)列Q的時(shí)間復(fù)雜度為o(N)。NCRA算法的時(shí)間復(fù)雜度為o(M×N+M2)。

4仿真實(shí)驗(yàn)及分析

4.1仿真環(huán)境及參數(shù)設(shè)置

本文使用的仿真工具是OPNET14.5。采用的網(wǎng)絡(luò)模型是在400m×400m的平面區(qū)域內(nèi)，由1個(gè)廣播源節(jié)點(diǎn)和M(M=5,10,15)個(gè)接收節(jié)點(diǎn)組成的無(wú)線單跳廣播網(wǎng)絡(luò)。節(jié)點(diǎn)MAC層采用IEEE802.11b標(biāo)準(zhǔn)，最高速率為11Mb/s。在原始數(shù)據(jù)包廣播階段和丟失數(shù)據(jù)包編碼重傳階段，發(fā)送數(shù)據(jù)包的時(shí)間間隔為1s，發(fā)送的原始數(shù)據(jù)包的個(gè)數(shù)用N表示。仿真實(shí)驗(yàn)中對(duì)比了以下算法：文獻(xiàn)[]提出的NCWBR算法、文獻(xiàn)[]提出的ONCMB算法、本文提出的NCRA算法。

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

(1) 重傳次數(shù)

重傳次數(shù)是源節(jié)點(diǎn)在重傳階段為了恢復(fù)所有丟失數(shù)據(jù)包發(fā)送的數(shù)據(jù)包的總次數(shù)。

在原始數(shù)據(jù)包發(fā)送階段，設(shè)置接收節(jié)點(diǎn)丟包率l=0.2，網(wǎng)絡(luò)中接收節(jié)點(diǎn)的個(gè)數(shù)M=5，發(fā)送原始數(shù)據(jù)包的個(gè)數(shù)為[100～500]。仿真結(jié)果圖3展示了當(dāng)源節(jié)點(diǎn)發(fā)送不同原始數(shù)據(jù)包個(gè)數(shù)時(shí)，各種算法的重傳次數(shù)。從圖中可以看出隨著原始數(shù)據(jù)包的個(gè)數(shù)不斷增加，接收節(jié)點(diǎn)丟失的數(shù)據(jù)包越多，需要重傳的次數(shù)越大。由于NCRA算法在編碼重傳時(shí)避免不能解碼的編碼組合冗余發(fā)送，且優(yōu)先重傳了有利于解碼緩存中編碼包的丟失數(shù)據(jù)包，所以在重傳次數(shù)方面優(yōu)于其他兩種算法。

圖3　不同原始數(shù)據(jù)包發(fā)送個(gè)數(shù)下的重傳次數(shù)

仿真結(jié)果圖4得出了在不同丟包率下，源節(jié)點(diǎn)發(fā)送500個(gè)原始數(shù)據(jù)包時(shí)的重傳次數(shù)。接收節(jié)點(diǎn)的個(gè)數(shù)M=5，丟包率l設(shè)置為[0.1～0.4]，步長(zhǎng)為0.1。隨著丟包率的增加，接收節(jié)點(diǎn)丟失的原始數(shù)據(jù)包越多，且重傳的編碼包不能被解碼的概率增大。NCWBR算法沒(méi)有利用不能解碼的編碼包，導(dǎo)致重傳次數(shù)的大幅增大。ONCMB算法與NCRA算法都將不能解碼的編碼包進(jìn)行了緩存，從而比NCWBR需要的重傳次數(shù)要少。NCRA算法編碼方法相比ONCMB更優(yōu)化，更有效地利用了編碼機(jī)會(huì)，從而減少了更多的重傳次數(shù)。

圖4　不同丟包率下的重傳次數(shù)

仿真結(jié)果圖5是網(wǎng)絡(luò)重傳次數(shù)在接收節(jié)點(diǎn)個(gè)數(shù)不同的網(wǎng)絡(luò)場(chǎng)景下的仿真結(jié)果。丟包率為0.2，源節(jié)點(diǎn)發(fā)送的原始數(shù)據(jù)包的個(gè)數(shù)為300，接收節(jié)點(diǎn)的個(gè)數(shù)M分別為5,10,15的場(chǎng)景。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增大時(shí)，雖然發(fā)送的原始數(shù)據(jù)包的個(gè)數(shù)沒(méi)有發(fā)生變化，但是由于接收節(jié)點(diǎn)的個(gè)數(shù)增多，原始數(shù)據(jù)包中出現(xiàn)丟失的概率增大。每次參與編碼的丟失數(shù)據(jù)包增多，導(dǎo)致編碼包長(zhǎng)度增大，從而不被解碼的概率增大。從圖中可以看出，當(dāng)接收節(jié)點(diǎn)的個(gè)數(shù)增多時(shí)，NCRA算法通過(guò)接收節(jié)點(diǎn)的緩存包信息來(lái)調(diào)整參與編碼的丟失數(shù)據(jù)包，有效地提高了編碼效率，從而降低了網(wǎng)絡(luò)重傳次數(shù)。

圖5　不同接收節(jié)點(diǎn)個(gè)數(shù)下的重傳次數(shù)

(2)數(shù)據(jù)包平均傳輸時(shí)延

數(shù)據(jù)包傳輸時(shí)延是指從源節(jié)點(diǎn)發(fā)送原始數(shù)據(jù)包開(kāi)始，到所有接收節(jié)點(diǎn)成功收到所有原始數(shù)據(jù)包所用的平均時(shí)間。

圖6得出了在源節(jié)點(diǎn)發(fā)送200個(gè)原始數(shù)據(jù)包，接收節(jié)點(diǎn)的個(gè)數(shù)M=5，丟包率為[0.1～0.4]的情況下，數(shù)據(jù)包平均傳輸時(shí)延。從圖中可以看出，NCRA算法的平均傳輸時(shí)延要比其他算法低，因?yàn)镹CRA算法不僅降低了網(wǎng)絡(luò)重傳次數(shù)，而且優(yōu)先恢復(fù)了較早丟失的數(shù)據(jù)包，所以降低了數(shù)據(jù)包平均傳輸時(shí)延。

圖6　數(shù)據(jù)包平均恢復(fù)時(shí)延

(3)重傳階段網(wǎng)絡(luò)開(kāi)銷

重傳網(wǎng)絡(luò)開(kāi)銷包括重傳階段發(fā)送的編碼包，用以解碼緩存編碼包的丟失數(shù)據(jù)包，以及控制包的總比特?cái)?shù)。

圖7展示了重傳階段的網(wǎng)絡(luò)開(kāi)銷統(tǒng)計(jì)結(jié)果。仿真場(chǎng)景為接收節(jié)點(diǎn)的個(gè)數(shù)M=5，接收節(jié)點(diǎn)的丟包率為0.2，源節(jié)點(diǎn)發(fā)送的原始數(shù)據(jù)包的個(gè)數(shù)為[100～400]。由于NCRA算法相比其他算法，能夠有效地降低重傳次數(shù)，從而減少了編碼包和ACK控制包的發(fā)送，因此降低了重傳階段的網(wǎng)絡(luò)開(kāi)銷。

圖7　網(wǎng)絡(luò)重傳開(kāi)銷

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

針對(duì)現(xiàn)有ONCMB存在的問(wèn)題，本文提出了NCRA算法。NCRA在編碼時(shí)避免了不能解碼的組合的重復(fù)發(fā)送，同時(shí)根據(jù)接收節(jié)點(diǎn)的緩存編碼包信息優(yōu)化了源節(jié)點(diǎn)的編碼方法，能夠有效地提升廣播重傳效率，理論分析和仿真實(shí)驗(yàn)說(shuō)明：NCRA與NCWBR和ONCMB算法相比，能夠有效減少重傳次數(shù)，降低數(shù)據(jù)包的平均傳輸時(shí)延。在下一步的工作中，我們將深入探究如何在原始數(shù)據(jù)包廣播階段同時(shí)對(duì)丟失的數(shù)據(jù)包進(jìn)行編碼重傳，以達(dá)到進(jìn)一步降低丟失數(shù)據(jù)包平均傳輸時(shí)延的目的。

參考文獻(xiàn)：

[1] Dianati M, Ling X H, Naik K, et al. A node cooperative ARQ scheme for wireless ad hoc networks[J].IEEETrans.onVehicularTechnology, 2006, 55(3):1927-1938.

[2] Ahlswede R, Cai N, Li S Y R, et al. Network information flow[J].IEEETrans.onInformTheory, 2000, 46(4):1204-1216.

[3] Mansouri H S, Pakravan M R. Network coding based reliable broadcasting in wireless ad hoc network[C]∥Proc.oftheIEEEInternationalConferenceonNetworks, 2007:525-530.

[4] Ho T, Medard M, Shi J, et al. On randomized network coding[C]∥Proc.ofthe41stAnnualAllertonConferenceonCommunicationControlandComputing,2003:1354-1357.

[5] Koetter R, Medard M. An algebraic approach to network coding[J].IEEE/ACMTrans.onNetworking, 2003, 11(5):782-795.

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

[7] Katti S, Rahul H, Hu W, et al. Xors in the air:practical wireless network coding[J].IEEE/ACMTrans.onNetworking, 2008, 16(3):497-510.

[8] Nguyen D, Nguyen T, Bose B.Wireless broadcasting using network coding[R].Oregon State University,OSU-TR-2006-06.

[9] Nguyen D, Tran T, Nguyen T, et al. Wireless broadcast using network coding[J].IEEETrans.onVehicularTechnology, 2009, 58(2):914-925.

[10] Rozner E, Padmanabha A, Mehta Y, et al. ER:efficient retransmission scheme for wireless LANs[C]∥Proc.oftheACMCoNEXT, 2007:613-625.

[11] Qureshi J, Foh C H, Cai J. An efficient network coding based retransmission algorithm for wireless multicast[C]∥Proc.oftheInternationalSymposiumonPersonal,Indoor,andMobileRadioCommunications, 2009:691-695.

[12] Xiao X, Wang W P, Yang L M, et al. Wireless broadcasting retransmission approach based on network coding[J].JournalonCommunications,2009, 30(9):69-75.(肖瀟, 王偉平, 楊路明,等. 基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)廣播重傳方法[J]. 通信學(xué)報(bào), 2009, 30(9):69-75.)

[13] Lu J, Wu C K, Xiao S, et al. Efficient broadcast transmission algorithms based on opportunistic network coding[J].JournalonCommunications, 2012,33(1):64-70.(盧冀, 吳成柯, 肖嵩等. 基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的高效廣播傳輸算法[J]. 通信學(xué)報(bào), 2012,33(1):64-70. )

姚玉坤(1964-)，女，教授，主要研究方向?yàn)閷拵o(wú)線移動(dòng)通信網(wǎng)絡(luò)及網(wǎng)絡(luò)編碼。

E-mail:yaoyk@cqupt.edu.cn

陳曦(1989-)，女，碩士研究生，主要研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)編碼。

E-mail:xiflycn@sina.cn

任智(1971-)，男，教授，博士，主要研究方向?yàn)閷拵o(wú)線移動(dòng)通信網(wǎng)絡(luò)。

E-mail:renzhi@cqupt.edu.cn

易建瓊(1986-)，女，碩士，主要研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)編碼。

E-mail:464257824@qq.com

雷宏江(1976-)，男，副教授，博士，主要研究方向?yàn)闊o(wú)線自組織網(wǎng)絡(luò)。

E-mail:191792320@qq.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141110.0944.001.html

Efficient network coding broadcasting retransmission

approach based on redundancy avoiding

YAO Yu-kun， CHEN Xi， REN Zhi， YI Jian-qiong， LEI Hong-jiang

(ChongqingKeyLaboratoryofMobileCommunicationTechnology,ChongqingUniversity

ofPostsandTelecommunications,Chongqing400065,China)

Abstract:For the purpose of improving the coding efficiency of the network coding broadcasting retransmission method in wireless network, thus reducing the retransmission times and the packets transmission delay, an efficient network coding broadcasting retransmission approach based on redundancy avoiding (NCRA) is proposed. According to NCRA, when the source node codes the lost packets together, it voluntarily avoids redundant transmission of the combination which cannot be decoded by the receiving node. At the same time, NCRA preferentially codes the lost packets which are conducive to decoding more cached coded packets. Under the condition that multiple lost packets have the same effect on decoding cached coded packets, the source node preferentially encodes the earliest lost packet to reduce the packet transmission delay. The theoretical analysis and simulation results reveal that compared to the existing algorithms, NCRA can significantly reduce the number of retransmission times and the average packets transmission delay.

Keywords:wireless networks; broadcasting retransmission; network coding; coded combination; redundancy avoiding

作者簡(jiǎn)介：

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.30

基金項(xiàng)目：重慶市自然科學(xué)基金項(xiàng)目(CSTC2012jjA40040)；長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助(IRT1299)；重慶市科委重點(diǎn)實(shí)驗(yàn)室專項(xiàng)經(jīng)費(fèi)(D2011-24)

收稿日期：2014-03-18；修回日期：2014-08-26；網(wǎng)絡(luò)優(yōu)先出版日期：2014-11-10。