無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼與Hash查找的廣播重傳研究

,

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

隨著移動通信技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)技術(shù)已經(jīng)由傳統(tǒng)的互聯(lián)網(wǎng)過渡到移動互聯(lián)網(wǎng)時代。相對于有線網(wǎng)絡(luò)傳輸，無線鏈路本身有著獨特的傳輸特性，比如廣播傳輸、易受天氣的影響、不穩(wěn)定、丟包率大等。由于無線網(wǎng)絡(luò)傳輸?shù)膸捰邢?，為了提高整個網(wǎng)絡(luò)系統(tǒng)資源的利用率，學(xué)者們從各個方面提出了諸多辦法以提高無線網(wǎng)絡(luò)的傳輸效率。在負載均衡方面，孟利民等[1]借鑒已有的負載均衡算法，并在其基礎(chǔ)之上，引入了任務(wù)分類、任務(wù)加權(quán)等策略，使網(wǎng)絡(luò)中各個節(jié)點之上的負載分配更為合理，從而提高了資源利用率，提高了系統(tǒng)性能。在用戶體驗方面，孟利民等[2]針對宏基站和家庭基站組成的無線異構(gòu)網(wǎng)絡(luò)，從用戶體驗的角度入手，將業(yè)務(wù)分為視頻、語音和數(shù)據(jù)等3 個部分，采用模擬退火智能算法，對有限的頻譜資源和功率資源進行分配，在保證無線視頻用戶體驗的前提下，達成了不同業(yè)務(wù)的用戶體驗之和最大化，實現(xiàn)了無線資源的最優(yōu)分配。在網(wǎng)絡(luò)傳輸方面，孟利民等[3]在LT碼基礎(chǔ)上，提出了一種改進的度分布Raptor編譯碼策略，改善了無線視頻信息的傳輸質(zhì)量，降低了由丟包引起的視頻實時性問題。但是，以上改善網(wǎng)絡(luò)傳輸性能的方法都是在網(wǎng)絡(luò)傳輸鏈路質(zhì)量得到保證的前提下進行的，由于無線網(wǎng)絡(luò)引起的數(shù)據(jù)丟包不可避免，而傳統(tǒng)的OSI模型的鏈路層是采用自動重傳請求(ARQ)技術(shù)來進行差錯恢復(fù)的，ARQ需要對數(shù)據(jù)包進行一一重傳，因此，在無線網(wǎng)絡(luò)中采用傳統(tǒng)的ARQ重傳技術(shù)難免造成資源的浪費，且效率低下，近些年發(fā)展起來的網(wǎng)絡(luò)編碼理論為解決提高無線網(wǎng)絡(luò)的重傳效率問題提供了新的啟發(fā)。

2000年，Ahlswede等[4]首次提出了網(wǎng)絡(luò)編碼(NC)的概念，允許網(wǎng)絡(luò)節(jié)點在傳統(tǒng)數(shù)據(jù)轉(zhuǎn)發(fā)的基礎(chǔ)上參與數(shù)據(jù)處理，可以有效地提高網(wǎng)絡(luò)吞吐量，降低傳輸時延。網(wǎng)絡(luò)編碼的提出為無線數(shù)據(jù)的重傳提供了另一種思路，在某些特定情形下，利用無線信道的廣播性質(zhì)和NC技術(shù)，在N個接受端丟失的N個數(shù)據(jù)包，通過簡單的編碼，僅需要1 次重傳就能有效恢復(fù)。由此可見：基于NC的ARQ(NC-ARQ)方案提高了重傳的系統(tǒng)性能。近年來，NC-ARQ方案在單發(fā)多收(Single-sender-multiple-receiver，SSMR)及多發(fā)多收(Multiple-sender-multiple-receiver，MSMR)無線網(wǎng)絡(luò)中，都得到了廣泛運用。隨后，研究者們[5-8]提出了一些NC-ARQ方案，用以提升重傳效率及重傳可靠性。隨后，Li等[9]提出了一種在MSMR場景下的機會式NC重傳機制。此外，Tutgun等一批學(xué)者[10-12]結(jié)合空間分集與NC技術(shù)，提出了單源中繼多播場景下的重傳方案。Song等[13]結(jié)合空間分集與NC技術(shù)，設(shè)計了多源中繼多播中的重傳方案，可以有效減少重傳次數(shù)，增加吞吐量。Ren等[14]和Niu等[15]討論了緩存器輔助的NC-ARQ機制，該機制將當前無法解碼的組合編碼重傳包存儲在緩存器中，在一些新的特定編碼重傳包到來后，就可以成功解碼恢復(fù)出原始數(shù)據(jù)包，可以有效降低所需重傳包的數(shù)量，提升重傳效率。為了保證每一次重傳的收益最大化，筆者在現(xiàn)有NC-ARQ方案之上作了改進，設(shè)計了一種新的基于Hash查找無塊化重傳方法(Hash searching based non-block retransmission，HSNBR)。其基本思想是根據(jù)反饋信息對發(fā)送緩存器內(nèi)的數(shù)據(jù)包生成反饋矩陣，并由反饋矩陣生成丟包權(quán)值表，再通過Hash鄰域搜索找到使重傳收益最大編碼組合。若經(jīng)過Hash鄰域搜索未能找到使重傳收益最大的編碼組合，則對發(fā)送緩存器中的數(shù)據(jù)包進行更新，將已被成功接收的數(shù)據(jù)包移除，發(fā)送相等數(shù)量的新數(shù)據(jù)包填滿發(fā)送緩存器，更新反饋矩陣與丟包權(quán)值表，再進行1 次Hash鄰域搜索。最后得到的編碼組合就是最優(yōu)的重傳編碼組合。該方法可以確保每一次重傳收益最大化，有效提高了NC-ARQ的平均重傳效率。

1 網(wǎng)絡(luò)模型

如圖1所示的無線單跳廣播網(wǎng)絡(luò)，發(fā)送節(jié)點，即基站(Base station，BS)負責向N個接收節(jié)點發(fā)送數(shù)據(jù)包，N個接收節(jié)點記為Rs={Ri，i=1, 2,…,N}。廣播基于數(shù)據(jù)包傳輸，數(shù)據(jù)包會受到物理層信道噪聲、衰落和干擾的影響，因此，從高層看，由BS到Rs的廣播傳輸可以視為包刪除信道。假設(shè)BS到Ri之間數(shù)據(jù)包被刪除的概率相互獨立，設(shè)BS的發(fā)送緩存器大小為M，可以發(fā)送M個原始數(shù)據(jù)包，記為Pi(i=1, 2,…,M)。Rs根據(jù)M個數(shù)據(jù)包的接收情況反饋ACK或NACK至BS，為了模型的簡便，這里假定ACK，NACK總能被BS正確地接收。BS根據(jù)反饋信息構(gòu)建反饋矩陣A，A是N×M的矩陣。行號和列號分別代表接收節(jié)點序號和數(shù)據(jù)包序號。此外，A是一個二進制矩陣，A(i,j)=1表示Ri沒有成功接收Pj數(shù)據(jù)包。反之則表示Ri成功接收了Pj數(shù)據(jù)包。表1為N=3，M=10的一個反饋矩陣示例。假設(shè)，只有當所有接收者全都正確接收數(shù)據(jù)包Pi，Pi才被視為成功發(fā)送，否則算作丟失。每當數(shù)據(jù)包丟失，BS需要重傳這些數(shù)據(jù)包。根據(jù)反饋矩陣A，BS生成并發(fā)送由原始數(shù)據(jù)包線性組合的編碼包。原始數(shù)據(jù)包的編碼采用簡單的異或機制。設(shè)一次重傳中參與編碼的丟失數(shù)據(jù)包為X1,X2,…,Xk，每個數(shù)據(jù)包長度均為L，Y為編碼包。Xi可以表示為[xi1,xi2,…,xiL]，Y可以表示為[y1,y2,…,yL]，Xi與Y之間的關(guān)系式為

(1)

式中amodb為a對b求模。接收端通過將已成功接收的數(shù)據(jù)包和收到的編碼包進行異或操作解碼出自己丟失的數(shù)據(jù)包。即不同的接受者可以從一個編碼重傳包中恢復(fù)出不同的丟包。由此可見NC-ARQ機制可以有效地減少重傳次數(shù)，提高無線網(wǎng)絡(luò)資源的利用率。設(shè)計重傳算法的主要目的在于設(shè)計出一種選包策略，可以讓盡可能多的接收節(jié)點從一次重傳中獲得收益，以此減少重傳次數(shù)。

圖1 無線廣播網(wǎng)絡(luò)模型Fig.1 Wireless broadcast network model with packet-erasure channels

接收節(jié)點原始數(shù)據(jù)包P1P2P3P4P5P6P7P8P9P10R10000011000R20101101010R31000100111

2 HSNBR 重傳算法

2.1 基于Hash鄰域搜索的選包策略

定義1受益節(jié)點(Benefit node， BN)：若1 個接收節(jié)點可以從該編碼包中成功恢復(fù)1 個丟包，則稱該節(jié)點為此編碼重傳包的BN。

定義2完美編碼包(Perfect encoding package，PEP)：若所有的接收節(jié)點都是該編碼包的BN，則該編碼包稱為PEP。

定義3最優(yōu)編碼包(Optimum encoding package，OEP)：若1 個編碼包，從發(fā)送緩存器內(nèi)尚未參與編碼的原始丟包中，選取任意組合的原始丟包加入編碼，都無法增加BN的數(shù)量，則稱該編碼包為OEP。

從定義3可以看出：OEP未必是PEP，而PEP必定是OEP。

在第1 節(jié)提到，BS會根據(jù)反饋信息構(gòu)建反饋N×M的矩陣A。A的第j列表示數(shù)據(jù)包Pj相對于Rs的接收狀態(tài)。根據(jù)數(shù)據(jù)包Pj的接收狀態(tài)，生成特定的Hash值hj，Hash值的計算函數(shù)式為

(2)

BS根據(jù)式(2)計算每個丟包的Hash值hj，然后根據(jù)每個丟包對應(yīng)的Hash值hj創(chuàng)建權(quán)值表，如表2所示。表2是根據(jù)表1反饋矩陣生成的權(quán)值表，表2中cj表示丟失數(shù)據(jù)包Pj數(shù)據(jù)包的接收節(jié)點的數(shù)量。

表2 丟包權(quán)值表Table 2 The lost weight table

為了盡可能提高重傳的效率，HSNBR算法應(yīng)當確保每一次發(fā)送的重傳編碼包為PEP或OEP。若1 個編碼包Y由原始丟包X1,X2, … ,Xk編碼而成，它們對應(yīng)的Hash值為h1,h2, … ,hk，若接收節(jié)點Ri可以從Y中成功恢復(fù)出{X1,X2, … ,Xk}中之一的原始數(shù)據(jù)包，則必須滿足

Fi(h1,h2,…,hk)=1

(3)

式中：Fi表示h1,h2, … ,hk全部轉(zhuǎn)換為二進制后它們的第i位之和。

定理1如果1 個編碼數(shù)據(jù)包Y1，對于所有的i=1, 2, …,N，均能滿足式(3)則編碼包Y1是PEP，即PEP滿足

Fi(h1,h2,…,hk)=1i=1, 2, …,N

(4)

定理2若數(shù)據(jù)包Y2滿足

Fi(h1,h2,…,hk)≤1i=1, 2, …,N

(5)

并且當發(fā)送緩存器中任意的其他原始丟包加入到組合中時，式(5)都不再滿足，則Y2是OEP。

證明由定義1～3可知：Fi指示了Ri和X1,X2, …,Xk之間的接收狀態(tài)，若Fi(h1,h2,…,hk)=0，則表示Ri已經(jīng)成功接收了這k個參與編碼的原始數(shù)據(jù)包，即這次重傳對于Ri來說沒有收益。此外，若Fi(h1,h2,…,hk) ≥2，則表明Ri在{X1,X2,…,Xk}中丟失了兩個以上的數(shù)據(jù)包，即使成功接收了重傳，也無法通過亦或解碼從中回復(fù)出原始數(shù)據(jù)包。因此，只有滿足式(3)，即Ri在{X1,X2,…,Xk}中僅丟失1 個數(shù)據(jù)包。假設(shè)Ri丟失的數(shù)據(jù)包為Xj(1≤j≤k)，編碼包Y=X1⊕…⊕Xj⊕…⊕Xk，則Ri可以通過Xj=Y⊕X1⊕…⊕Xj-1⊕Xj+1⊕…⊕Xk恢復(fù)出Xj。

特別地，如果編碼包Y1滿足式(4)，表示所有N個接收節(jié)點可以從中恢復(fù)1 個原始數(shù)據(jù)包，由PEP的定義2可知Y1是PEP。而如果Y2滿足式(5)，表示一部分節(jié)點已經(jīng)成功接收了Y2編碼組合中所有的數(shù)據(jù)包，另一些只丟失了Y2編碼組合中1 個數(shù)據(jù)包，而將發(fā)送緩存器中其他任意原始丟包加入編碼組合，都無法使式(5)繼續(xù)滿足，即組合中加入新的原始丟包時，會導(dǎo)致對于一些接收節(jié)點丟失的數(shù)據(jù)包在編碼組合中不止1 個，因此無法恢復(fù)出原始丟包，根據(jù)OEP的定義，Y2是OEP。證畢。

由定義2可知：PEP可以使重傳的效率最大化，因此所提出的HSNBR需要盡可能從發(fā)送緩存器中搜尋PEP。為了高效地從發(fā)送緩存器中找到PEP或OEP，需要引入Hash鄰域的概念。

定理3若Hash值的集合U滿足

(6)

那么U為Hash值h1,h2,…,hk的Hash鄰域。

對于1 個原始丟包Pj，Rs中未能成功接收Pj的接收節(jié)點越多，則Pj對重傳效率的貢獻越大，因此應(yīng)該被優(yōu)先選擇加入編碼組合，而Hash值hj無法直觀地體現(xiàn)丟失Pj的接收節(jié)點的數(shù)量cj。因為hj與cj即不成正相關(guān)，也不成負相關(guān)。舉兩個例子，如果優(yōu)先選擇Hash值大的包，當接收節(jié)點{R1,R2,R3}丟失了P1，接收節(jié)點{R3,R4}丟失了P2，h1=7，h2=12，優(yōu)先選擇的是P2，但顯然P1更應(yīng)當被優(yōu)先選擇。而若優(yōu)先選擇Hash值較小的包，當接收節(jié)點{R1,R2}丟失了P3，接收節(jié)點{R2,R3,R4}丟失了P4，h3=3，h4=14，優(yōu)先選擇的是P3，但顯然P4更應(yīng)當被優(yōu)先選擇。因此，如果只選用Hash值作為選包的依據(jù)是不妥的。

為了提高重傳效率，又考慮到選包算法的復(fù)雜度不宜過大，提出一種Hash鄰域搜索算法，過程如下：

步驟1首先從權(quán)值表中選擇1 個cj最大的丟包，并取得其Hash值。

步驟2計算已選擇的Hash值的鄰域U。

步驟3從權(quán)值表2中挑選1 個屬于U的最大的Hash值。重復(fù)步驟2，3直到所選擇的Hash值滿足式(4)，或遍歷了權(quán)值表。

執(zhí)行完上述過程，如果挑選的包不滿足式(4)，則由定義可知所選的編碼包為OEP，否則為PEP。

2.2 HSNBR算法流程

HSNBR算法的具體流程如圖2所示。

圖2 HSNBR流程Fig.2 Flowchart of HSNBR

HSNBR算法的具體步驟如下：

步驟1BS逐個廣播M個原始數(shù)據(jù)包。

步驟2根據(jù)Rs返回的ACK或NACK創(chuàng)建反饋矩陣A。

步驟3根據(jù)A計算每一個丟包的Hash值并生成權(quán)值表并將成功發(fā)送的數(shù)據(jù)包從發(fā)送緩存器中清除。

步驟4對生成的權(quán)值表進行Hash查找，如果找到PEP組合，則對選中原始數(shù)據(jù)包亦或編碼后重傳，隨后跳轉(zhuǎn)至步驟2。

步驟5如果未找到PEP組合，則檢查發(fā)送緩存器是否已滿。

步驟6如果發(fā)送緩存器已滿，則根據(jù)Hash查找的結(jié)果發(fā)送OEP，隨后跳轉(zhuǎn)至步驟2。

步驟7如果發(fā)送緩存器未滿且傳輸尚未完成，則廣播新的原始數(shù)據(jù)包填滿，隨后跳轉(zhuǎn)至步驟2。

HSNBR算法與普通NC-ARQ重傳的主要區(qū)別在于步驟5，因為普通的NC-ARQ方案都根據(jù)發(fā)送緩存器的容量M將原始數(shù)據(jù)依次按大小為M的塊進行發(fā)送，只有在一個塊的所有數(shù)據(jù)包都被成功接收后才會發(fā)送下一個塊的數(shù)據(jù)，因此，每次Hash鄰域搜索的只能在一個單一的塊內(nèi)進行，這會限制每一次重傳的平均效率，這些方案可以被視為塊內(nèi)NC-ARQ(Block NC-ARQ，BNC-ARQ)。而HSNBR只有在找到PEP組合或者在發(fā)送緩存器已滿而不得不發(fā)送OEP的時候才會發(fā)送重傳編碼包。換言之，HSNBR會盡可能發(fā)送PEP，以此提高重傳效率。

以表1反饋矩陣對應(yīng)重傳為例。

BNC-ARQ首先選擇Hash值最大的P5，再對其進行Hash鄰域搜索，則第1 個重傳包Y1=P5⊕P6，BN1=3。依次地，Y2=P9，BN2=2；Y3=P1⊕P7；BN3=3；Y4=P8⊕P2；BN4=2；Y5=P10⊕P4，BN5=2。5 次重傳的平均受益節(jié)點數(shù)BNavg=12/5。

HSNBR首先生成如表2所示的權(quán)值表，選擇權(quán)值最大的P5，再對其進行Hash鄰域搜索，則第1 個重傳包Y1=P5⊕P6，BN1=3。隨后選擇權(quán)值最大的P9，進行Hash鄰域搜索后Y2tmp=P9，并非PEP，根據(jù)HSNBR算法，會將發(fā)送緩存器中成功接收的數(shù)據(jù)包清除，并發(fā)送新的數(shù)據(jù)包，更新后的反饋矩陣如表3所示。

表3 更新后的反饋矩陣Table 3 The updated feedback matrix

更新后的權(quán)值表如表4所示。

表4 更新后的丟包權(quán)值表Table 4 The updated lost weight table

更新權(quán)值表后再對Y2tmp進行Hash鄰域搜索，Y2=P9+P11，BN2=3。依次地，Y3=P7⊕P1；BN3=3；Y4=P8⊕P2⊕P12；BN4=3，Y5=P10⊕P4⊕P13，BN5=3。5 次重傳的平均受益節(jié)點數(shù)BNavg=3。

可見HSNBR每一次重傳的平均受益節(jié)點數(shù)要大于BNC-ARQ。換言之，HSNBR相較于BNC-ARQ可以有效減少重傳次數(shù)，具有更高的重傳效率。

3 實驗仿真結(jié)果

為了驗證所提出的HSNBR算法在有限緩存的情況下能有效地提高重傳效率。采用Matlab仿真軟件對ARQ，BNC-ARQ，HSNBR等3 種重傳算法進行仿真以分析算法之間的性能差異。分析可知：在發(fā)送緩存器大小(M)、接收節(jié)點數(shù)(N)、信道平均丟包率(Average packet loss rate，APLR)以及發(fā)送數(shù)據(jù)包總量相同的情況下，不同算法所需的平均重傳次數(shù)是重傳算法重傳效率高低最直觀的體現(xiàn)，但其值隨著發(fā)送數(shù)據(jù)包數(shù)量呈線性增長而浮動過大。因此，采用平均重傳率(Average retransmission rate，ARR)作為衡量算法重傳效率的指標。ARR定義為

(7)

式中：NR為重傳總次數(shù)；NP為原始數(shù)據(jù)包的總數(shù)。ARR越低重傳效率越高。為了便于分析，這里假設(shè)每一個重傳包都能被各個接收節(jié)點百分之百正確接收，并且忽略接收端的定時誤差。

圖3反應(yīng)了3 種重傳算法的ARR隨著發(fā)送緩存器大小變化的規(guī)律，其中接收節(jié)點數(shù)N為5，平均丟包率APLR為0.2，發(fā)送原始數(shù)據(jù)包總數(shù)為1×105。由圖3可見：ARQ重傳方案的ARR并不會隨發(fā)送緩存器大小M變化而有顯著改變，而僅僅是在一個固定值上有微弱的浮動，可以視為其ARR與M無關(guān)，但其ARR一直保持在一個很高的值，重傳性能低下。在緩存器容量較小的區(qū)間，HSNBR的ARR會明顯低于BNC-ARQ，因為理論上HSNBR相較于BNC-ARQ對于發(fā)送緩存器空間利用得更充分。隨著發(fā)送緩存器大小M逐漸增大，HSNBR與BNC-ARQ的ARR均逐步下降，而HSNBR的ARR始終低于BNC-ARQ。當M進一步增大，HSNBR的ARR將非常接近理論下限的APLR。由此可見：在整個區(qū)間HSNBR的表現(xiàn)優(yōu)于ARQ和NC-ARQ，在發(fā)送緩存器較小的情況下對重傳性能的提升尤為明顯，并且不需要非常大的緩存容量，HSNBR就可以非常接近理論的重傳效率上限。

圖3 重傳效率隨發(fā)送緩存器大小變化的規(guī)律Fig.3 Retransmission efficiency against the size of transfer buffer

圖4為3 種重傳算法的ARR隨接收節(jié)點數(shù)N變化的規(guī)律。其中M固定為50，APLR為0.2，發(fā)送原始數(shù)據(jù)包總數(shù)為1×105。由圖4可見：3 種算法的ARR均會隨著接收節(jié)點數(shù)N的增大而增加。ARQ方案的ARR隨N增大最快，且很快接近100%。HSNBR和BNC-ARQ隨節(jié)點數(shù)量增加的增長速度較之于ARQ都更為緩慢，而HSNBR的ARR在N變化的情況下相較于BNC-ARQ更為穩(wěn)定并且ARR始終低于BNC-ARQ，并不會隨著N的增加有很大的漲幅，僅僅是隨著N增加而有細微增長并且始終接近于ARR的理論值下限APLR。

圖4 重傳效率隨接收節(jié)點數(shù)變化的規(guī)律Fig.4 Retransmission efficiency against number of receivers

圖5為3 種重傳算法ARR隨著平均丟包率APLR變化的規(guī)律。其中發(fā)送緩存器大小M為50，接收節(jié)點數(shù)N為5，發(fā)送元數(shù)據(jù)包總數(shù)為1×105。APLR的區(qū)間在0.05～0.5。由圖5可知：ARQ算法的ARR隨著APLR的增長最快，并且會很快地接近100%。HSNBR與BNC-ARQ的ARR在該APLR區(qū)間內(nèi)近似地呈線性增長，并且HSNBR的ARR始終非常接近理論值的下限APLR，可見HSNBR在重傳效率方面依然始終優(yōu)于BNC-ARQ。

以上仿真結(jié)果表明：所提出的HSNBR重傳算法的重傳效率在各種環(huán)境下均優(yōu)于ARQ和BNC-ARQ，且ARR通常都非常接近于理論值的APLR，這證明了方案的合理性與有效性。若傳輸時信道的丟包率高且面向的接收節(jié)點較多，只要適當增加緩存器容量就可以使重傳效率保持在較為理想的水平，即通過增加硬件資源以彌補信道資源，這在信道資源受限的場景下是具有實際意義的。

圖5 重傳效率隨平均丟包率變化的規(guī)律Fig.5 Retransmission efficiency against the APLR

4 結(jié) 論

針對BNC-ARQ存在的不足，提出了一種無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼與Hash查找的優(yōu)化廣播重傳算法。在發(fā)送緩存器容量有限的情況下，通過動態(tài)地更新發(fā)送緩存器中的數(shù)據(jù)包，充分地利用了發(fā)送緩存器的空間，提高了丟包之間組合編碼的概率，提升了重傳包的重傳效率，降低了重傳丟包的次數(shù)，從而有效提高了SSMR網(wǎng)絡(luò)中的傳輸效率。仿真結(jié)果表明：所提出的HSNBR重傳算法的重傳效率在各種環(huán)境下均優(yōu)于ARQ和BNC-ARQ，證實了該方案的合理性和有效性。