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

(重慶郵電大學移動通信技術重慶市重點實驗室， 重慶 400065)

?

基于冗余避免的高效網絡編碼廣播重傳方法

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

(重慶郵電大學移動通信技術重慶市重點實驗室， 重慶 400065)

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

關鍵詞：無線網絡; 廣播重傳; 網絡編碼; 編碼組合; 冗余避免

0引言

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

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

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

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

1網絡模型及問題描述

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

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

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

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

(1)

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

證畢

文獻[13]提出的機會式網絡編碼多組合分組廣播傳輸算法ONCMB，在對丟失數據包進行編碼重傳時包含以下2個階段。

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

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

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

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

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

2NCRA方法的編碼原理

2.1NCRA基本思想與方法描述

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

NCRA算法的主要創(chuàng)新思想如下：

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

(2) 源節(jié)點利用接收節(jié)點的緩存編碼包信息來實現優(yōu)先對解碼緩存編碼包貢獻較大的丟失數據包進行編碼，提高緩存編碼包解碼效率。

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

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

設計緩存集合C和緩存隊列Q，分別用以記錄接收節(jié)點緩存的編碼組合信息和存儲丟失數據包對解碼緩存編碼包的貢獻優(yōu)先級。

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

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

NCRA算法具體步驟如下：

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

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

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

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

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

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

首先根據接收狀態(tài)矩陣，查找出SF中包含的接收節(jié)點丟失數據包組成的不能解碼的編碼組合，然后查找出SF中已經在原緩存集合C中該節(jié)點對應的編碼組合的丟失數據包，得到當前接收節(jié)點在SF中不能解碼的組合。如果沒有找到這樣的組合，表示該節(jié)點能夠解碼SF組成的編碼包，再根據解碼出的丟失數據包對該節(jié)點在C中的組合進行更新。

更新完緩存集合C后，將緩存隊列Q清零。然后統(tǒng)計C中各丟失數據包在C中出現的頻率，然后按照頻率升序排列，如果頻率一樣，則將數據包序號大的排在前面，組成新的緩存隊列Q。

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

(2)

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

2.2NCRA算法的應用分析

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

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

圖1　NCRA與ONCMB算法的應用

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

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

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

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

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

定理 2當同一接收節(jié)點的多個丟失數據包被編碼在全部編碼包中的編碼組合信息都一樣時，該接收節(jié)點將不能解碼這多個丟包的編碼組合。

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

證畢

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

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

圖2　NCRA與ONCMB算法的應用

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

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

3NCRA算法性能的理論分析

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

3.1平均傳輸次數

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

(3)

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

(4)

(5)

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

(6)

代入式(3)可得

(7)

由于ONCMB在將所有丟失數據包編碼重傳后，有接收節(jié)點緩存的編碼包不能被解碼，源節(jié)點需要再重傳丟失數據包來解碼緩存編碼。所以ONCMB的平均傳輸次數UB為

(8)

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

3.2數據包平均傳輸時延

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

如果數據包Pn在Ri節(jié)點沒有出現丟失，Pn的傳輸時延dx為

(9)

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

若Pn在Ri出現丟失，當N個數據包發(fā)送完以后，則需要通過重傳恢復Pn的時延dx為

(10)

式中，Ha表示原始數據包的平均重傳次數(見式(6))；n×Ha為n個數據包的重傳次數。

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

(11)

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

(12)

使用ONCMB算法時，有一部分丟失數據包是在編碼重傳階段結束后，源節(jié)點通過單獨重傳這些丟失數據包來恢復的，這些丟失數據包的傳輸時延較大，為Δt×(N+N×Ha)，因此這一部分丟失數據包的平均傳輸時延為

(13)

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

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

3.3算法復雜度

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

4仿真實驗及分析

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

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

4.2仿真結果及分析

(1) 重傳次數

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

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

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

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

圖4　不同丟包率下的重傳次數

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

圖5　不同接收節(jié)點個數下的重傳次數

(2)數據包平均傳輸時延

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

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

圖6　數據包平均恢復時延

(3)重傳階段網絡開銷

重傳網絡開銷包括重傳階段發(fā)送的編碼包，用以解碼緩存編碼包的丟失數據包，以及控制包的總比特數。

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

圖7　網絡重傳開銷

5結束語

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

參考文獻：

[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.(肖瀟, 王偉平, 楊路明,等. 基于網絡編碼的無線網絡廣播重傳方法[J]. 通信學報, 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]. 通信學報, 2012,33(1):64-70. )

姚玉坤(1964-)，女，教授，主要研究方向為寬帶無線移動通信網絡及網絡編碼。

E-mail:yaoyk@cqupt.edu.cn

陳曦(1989-)，女，碩士研究生，主要研究方向為無線網絡編碼。

E-mail:xiflycn@sina.cn

任智(1971-)，男，教授，博士，主要研究方向為寬帶無線移動通信網絡。

E-mail:renzhi@cqupt.edu.cn

易建瓊(1986-)，女，碩士，主要研究方向為無線網絡編碼。

E-mail:464257824@qq.com

雷宏江(1976-)，男，副教授，博士，主要研究方向為無線自組織網絡。

E-mail:191792320@qq.com

網絡優(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

作者簡介：

中圖分類號：TP393

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.30

基金項目：重慶市自然科學基金項目(CSTC2012jjA40040)；長江學者和創(chuàng)新團隊發(fā)展計劃資助(IRT1299)；重慶市科委重點實驗室專項經費(D2011-24)

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