不完美反饋下基于立即可解網(wǎng)絡(luò)編碼的多播重傳機制

王 練, 朱朝輝, 吳海蓮, 殷 豪

(重慶郵電大學(xué)計算機科學(xué)與技術(shù)學(xué)院, 重慶 400065)

0 引 言

無線網(wǎng)絡(luò)數(shù)據(jù)傳輸過程存在反饋信息因干擾丟失的情況,反饋信息丟失將導(dǎo)致發(fā)送方無法對接收端的接收狀態(tài)全面了解,導(dǎo)致對后續(xù)重傳包的選擇帶來不確定性。網(wǎng)絡(luò)編碼(network coding,NC)由Ahlswede等人在2000年首次提出[1],網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)中間節(jié)點按一定的規(guī)則對數(shù)據(jù)包進行編碼后轉(zhuǎn)發(fā),該“編碼-轉(zhuǎn)發(fā)”模式有別于傳統(tǒng)的“存儲-轉(zhuǎn)發(fā)”模式,中間結(jié)點的編碼能力能有效提升傳輸鏈路帶寬的利用率[2]。Katti等人提出機會式NC(opportunistic NC, ONC),其編解碼運算采用異或(eXclusive OR,XOR)操作,XOR運算簡單,能有效降低編解碼計算復(fù)雜度[3]。立即可解NC(instantly decodable NC, IDNC)是ONC的子類[4],所生成的編碼包須滿足編解碼條件,避免不可解編碼包的產(chǎn)生,能有效降低完成時延[5-6]。

不完美反饋下,Valaee等人研究反饋丟失對基于IDNC廣播方案完成時延的影響,并在反饋丟失和完成時延降低的情況下設(shè)計了3種即時可解碼網(wǎng)絡(luò)編碼圖更新算法[7]。Gao等人在單跳網(wǎng)絡(luò)中解碼延遲約束和不完美反饋情況下提出上三角網(wǎng)絡(luò)編碼方案,該方案能有效提高吞吐量[8]。Douik等人研究不完美反饋下持續(xù)刪除信道上廣義IDNC(generalized IDNC, G-IDNC)組播譯碼時延問題,并將該問題轉(zhuǎn)換為G-IDNC圖中求最大權(quán)團問題,在此基礎(chǔ)上提出次優(yōu)貪婪算法,以減小譯碼時延[9]。Sorour等人根據(jù)極大似然狀態(tài),在不完美反饋下根據(jù)接收端的接收狀態(tài)推導(dǎo)出最小譯碼時延和完成時延的表達式[10]。Douik 等人在不完美反饋下提出有損G-IDNC圖(lossy G-IDNC graph,LG-IDNC),使用基于LG-IDNC的權(quán)重值公式有效降低譯碼時延[11]。周志恒等人基于部分可觀察馬爾可夫鏈決策過程(partially observable Markov decision processes,POMDP)建立不完美反饋下系統(tǒng)模型,提出一種包含緩存反饋機制和一步前瞻的在線規(guī)劃算法[12]。任志豪等人提出多中繼協(xié)作網(wǎng)絡(luò)中不完美反饋下的重傳方案,通過緩存不可解數(shù)據(jù)包并優(yōu)先發(fā)送丟失最多的數(shù)據(jù)包,以降低解碼時延[13]。朱小燕等人根據(jù)IDNC和隨機線性NC(random linear NC, RLNC)的不同特點提出基于子代劃分的NC,并證明IDNC和RLNC只是該模型的兩個特例[14]。Ahmad 等人將混合自動重傳請求(hybrid automatic repeat request, HARQ)拓展到不完美反饋的場景,并給出在不完美反饋下系統(tǒng)吞吐量的精確表達[15]。

本文以最小化完成時延為目標(biāo),針對不完美反饋下無線組播網(wǎng)絡(luò)中時延最小化問題,在現(xiàn)有研究基礎(chǔ)上提出一種不完美反饋下基于IDNC的時延最小化重傳方案(retransmission scheme to minimize delay under imperfect feedback,MDIF)。在重傳階段,發(fā)送端根據(jù)各接收端接收狀態(tài)、丟包率以及時延等條件,利用POMDP理論建立系統(tǒng)模型,計算不完美反饋下接收端的置信狀態(tài)。本文采用基于置信點的更新方法,通過選取特定的接收端構(gòu)成優(yōu)先發(fā)送集合,并在此集合上進行更新操作。其次,本文優(yōu)化了傳統(tǒng)最大權(quán)團搜索算法,提出的快速生成算法通過將丟失相同數(shù)據(jù)包的接收端進行整合,在降低計算復(fù)雜度的同時,能進一步降低系統(tǒng)時延。

1 系統(tǒng)模型和參數(shù)

1.1 系統(tǒng)模型

如圖1所示,無線多播網(wǎng)絡(luò)模型中發(fā)送端S將N個數(shù)據(jù)包發(fā)送給M個接收端,每個接收端需接收N個原包或N個原包的子集。定義原包集P={Pi|1≤i≤N},信宿節(jié)點集R={Ri|1≤i≤M}。

圖1 無線多播網(wǎng)絡(luò)模型Fig.1 Wireless multicast network model

傳輸過程分為初始傳輸階段和重傳恢復(fù)兩個階段。在初始傳輸階段,發(fā)送端S將N個數(shù)據(jù)包廣播給M個接收端,每個接收端需接收所有的數(shù)據(jù)包,包括未請求的數(shù)據(jù)包,并向發(fā)送端S反饋各包接收的確認信息。令pi為由發(fā)送端S到接收端Ri傳輸鏈路的丟包率,qi為接收端Ri反饋鏈路的丟包率。初始傳輸階段后,接收端可能存在以下4種數(shù)據(jù)包集:① 已接收數(shù)據(jù)包集Hi(接收端Ri已經(jīng)接收到數(shù)據(jù)包的集合);② 請求數(shù)據(jù)包集Wi(接收端Ri請求數(shù)據(jù)包的集合);③ 丟失數(shù)據(jù)包集Li(接收端Ri丟失的所有數(shù)據(jù)包的集合);④ 不確定數(shù)據(jù)包集Ui(反饋信息丟失的數(shù)據(jù)包的集合)。

定義 1狀態(tài)反饋矩陣(state feedback matrix, SFM),發(fā)送端用來表示接收端的接收狀態(tài),矩陣中各狀態(tài)反饋信息fij(?i∈M,j∈N)定義為

(1)

在重傳恢復(fù)階段,發(fā)送端根據(jù)狀態(tài)反饋矩陣生成編碼包,直到所有接收端都接收到其所請求的數(shù)據(jù)包。編碼包有3類:① 非再生包(編碼包a*不包含接收端Ri請求集Wi中任何包,即|a*∩Wi|=0);② 立即可解包(編碼包a*只包含接收端Ri請求集Wi中的一個包,即|a*∩Wi|=1);③ 非立即可解包(編碼包a*包含接收端Ri請求集Wi中兩個及以上包,即|a*∩Wi|≥2)。

(2)

定義 3完成時延(completion delay, CD),所有接收端接收到其請求數(shù)據(jù)包所需的傳輸次數(shù)。定義接收端Ri的完成時延為ci,則系統(tǒng)總的完成時延CD為

(3)

1.2 POMDP模型

為估計不完美反饋下接收端的真實接收狀態(tài),本文采用POMDP理論建立系統(tǒng)模型,POMDP由{S,A,Z,T,O,V}等參數(shù)構(gòu)成,具體參數(shù)定義如下。

系統(tǒng)狀態(tài)集S={s1,s2,…}:S中的元素表示目的接收端Ri在接收編碼包a后可能的接收狀態(tài);

行動集合A={a1,a2,…}:A中的元素表示不同的數(shù)據(jù)包組合;

觀測狀態(tài)集Z={z1,z2,…}:Z中的元素表示發(fā)送端S通過反饋信息獲得編碼包的接收狀態(tài)。由于反饋信息存在丟失,發(fā)送端S的觀測狀態(tài)不一定是編碼包的真實接收狀態(tài)。由此建立觀測狀態(tài)矩陣(observed state matrix,OSM)。

狀態(tài)轉(zhuǎn)移概率T(s,a,s′):T表示發(fā)送編碼包a后,編碼包接收狀態(tài)由s轉(zhuǎn)移到s′的概率：

(4)

觀測轉(zhuǎn)移概率O(s′,a,z):發(fā)送編碼包a并進入接收狀態(tài)s′后,發(fā)送端觀測到接收狀態(tài)為z的概率:

(5)

回報函數(shù)V:發(fā)送編碼包a后,所有目的接收端恢復(fù)請求數(shù)據(jù)包的個數(shù)之和:

(6)

式中：f(si,a,Ri)表示接收端Ri收到編碼包a后恢復(fù)請求編碼包的個數(shù)。

基于上述POMDP模型,根據(jù)丟包率pi、反饋丟失率qi、觀測轉(zhuǎn)移概率O、狀態(tài)轉(zhuǎn)移概率T和置信狀態(tài)b估計不同時隙置信狀態(tài)的置信度[16]:

(7)

因此,選擇最佳重傳編碼包a*即是選擇具有最大回報函數(shù)值的編碼包a:

(8)

1.3 IDNC圖

IDNC圖G(v,ε)用于表示所有可能的原始數(shù)據(jù)包組合。通過為數(shù)據(jù)包Pj(j∈Li)和接收端Ri(i∈M)生成圖中的頂點vij來構(gòu)造IDNC圖。圖中兩個頂點vij和vkl能構(gòu)成最大團需同時滿足以下條件:①j=l即接收端Ri和Rk請求相同的數(shù)據(jù)包;②j∈Hk且l∈Hi,即對應(yīng)頂點的請求數(shù)據(jù)包位于另一個頂點的請求集中。

因此,圖中兩個頂點vij和vkl之間的每條連線表示數(shù)據(jù)包Pj和Pl可組合成編碼包。

根據(jù)接收端對不同數(shù)據(jù)包的請求,可根據(jù)頂點將IDNC圖分為兩類:主圖Gp(主圖由接收端Ri請求集Wi中的數(shù)據(jù)包構(gòu)成);次圖Gs(次圖由接收端Ri丟失集Li且不在其請求集Wi中的數(shù)據(jù)包構(gòu)成)。

3個接收端接收4個數(shù)據(jù)包的反饋狀態(tài)及其IDNC圖,如圖2所示。當(dāng)建立IDNC圖后,分別在主圖和次圖執(zhí)行最大權(quán)團搜索算法生成最佳重傳編碼包,重復(fù)該過程直到所有的接收端都接收到其所需的數(shù)據(jù)包。

圖2 狀態(tài)反饋矩陣及其對應(yīng)的IDNC圖Fig.2 SFM and IDNC graph

定義 4持續(xù)剩余完成時延(persistent residual completion delay, PRCD),接收端Ri收到所有丟失數(shù)據(jù)包預(yù)期的傳輸次數(shù),接收端Ri的持續(xù)剩余完成時延[7]定義為

(9)

定義 5權(quán)重值(weight value, WV),根據(jù)持續(xù)剩余完成時間和IDNC圖中頂點之間的連線關(guān)系,賦予頂點權(quán)重值,頂點vij的權(quán)重值為

(10)

式中:aij,kl為vij和vkl的鄰接指數(shù),

(11)

2 不完美反饋下基于立即可解網(wǎng)絡(luò)編碼的重傳方案

2.1 置信點更新算法

無線多播網(wǎng)絡(luò)中,不同接收端對接收丟失數(shù)據(jù)包的迫切程度可能不一樣,尤其是在實時應(yīng)用中接收端可以容忍一定程度的數(shù)據(jù)包丟失,而數(shù)據(jù)包丟失較多的接收端則需要較長的重傳時間。在重傳階段,本方案使用POMDP理論建立不完美反饋下系統(tǒng)模型。根據(jù)狀態(tài)反饋矩陣、觀測狀態(tài)和狀態(tài)轉(zhuǎn)移概率等計算反饋信息丟失情況下接收端可能出現(xiàn)的置信狀態(tài)。本方案采用基于置信點的更新方法,通過選取請求集大于平均請求集的接收端構(gòu)成優(yōu)先發(fā)送集合,并在此基礎(chǔ)上構(gòu)建置信狀態(tài)子集。在后續(xù)的每一次重傳中通過建立優(yōu)先發(fā)送集合并在置信狀態(tài)子集上進行置信狀態(tài)更新操作,以減小完成時延降低重傳次數(shù)。

算法 1 置信點更新算法輸入:狀態(tài)反饋矩陣SFM,觀測狀態(tài)矩陣OSM;最佳重傳編碼包a*輸出:優(yōu)先發(fā)送集合M',置信狀態(tài)子集b',估計狀態(tài)矩陣OEM,更新后的置信狀態(tài)b步驟 1 初始化:M',OEM=OSM步驟 2 計算平均請求集W=1/M∑Mi=1Wi步驟 3 for i=1∶M步驟 4 if Wi≥Wthen步驟 5 將大于平均請求集的接收端加入:M'=M'∪Ri步驟 6 將接收端對應(yīng)的置信點狀態(tài)加入置信點狀態(tài)子集:b'=b'∪bi步驟 7 end if步驟 8 end for步驟 9 for i=1∶M步驟 10 if發(fā)送端S接收到目的接收端Ri的反饋步驟 11 更新估計狀態(tài)矩陣OEM步驟 12 else if目的接收端是優(yōu)先發(fā)送集合的成員:Ri?M'步驟 13 由式(7)計算可能的置信度bi步驟 14 更新估計狀態(tài)矩陣OEM步驟 15 end if步驟 16 end if步驟 17 end for

2.2 快速生成算法

使用最大權(quán)團搜索算法生成最佳重傳編碼包時,由于只考慮頂點的權(quán)重值并未充分考慮最大團生成與IDNC圖中頂點和邊連線數(shù)的關(guān)系,本方案創(chuàng)建優(yōu)先發(fā)送集合,并采用置信點更新算法,在此基礎(chǔ)上提出快速生成算法,將IDNC圖中丟失相同數(shù)據(jù)包的接收端頂點整合,以減少IDNC圖中頂點和邊連線數(shù)。

算法 2 快速生成算法步驟 1 for ?vij,vkl∈G(v,ε)步驟 2 if k=i then步驟 3 使用新的頂點替換原來兩個頂點:Vmn=Vij步驟 4 新頂點邊集為原頂點邊集之和:εmn=εij+εkl步驟 5 新頂點的權(quán)重值為原頂點權(quán)重值之和:ωmn=ωij+ωkl步驟 6 end if步驟 7 end for

發(fā)送端根據(jù)觀測狀態(tài)矩陣OSM建立IDNC圖模型,然后在主圖中使用最大權(quán)團搜索算法選擇權(quán)重值最大的頂點加入最大團Kp,并在與該頂點相連的頂點中再次選擇權(quán)重值最大的頂點加入團Kp,直到找不到與團Kp中任意頂點直接相連的頂點為止,采用同樣的算法在次圖中找最大團Ks可得到重傳編碼包K=Kp∪Ks。發(fā)送端重傳編碼包K并更新狀態(tài)反饋矩陣,直到所有的接收端都接收到其丟失的數(shù)據(jù)包。

算法 3 最佳重傳編碼包選擇策略輸入:估計狀態(tài)矩陣OEM輸出:系統(tǒng)重傳編碼包K,主圖中最佳重傳編碼包Kp,次圖中最佳重傳編碼包Ks步驟 1 初始化:K=?,Kp=?,Ks=?步驟 2 生成主IDNC圖和次IDNC圖Gp(v,ε),Gs(v',ε')步驟 3 while(ε≠?)步驟 4 找到主圖中權(quán)重最大頂點對應(yīng)的丟失數(shù)據(jù)包:Pmax=argmaxvi,j∈Gp{ωi,j}步驟 5 Kp=Kp∪Pmax步驟 6 end while步驟 7 while(ε'≠?)步驟 8 找到次圖中權(quán)重值最大頂點對應(yīng)的數(shù)據(jù)包:Pmax=argmaxvk,l∈Gs{ωk,l}步驟 9 Ks=Ks∪Pmax步驟 10 end while步驟 11 K=Kp∪Ks步驟 12 傳輸K步驟 13 重復(fù)以上步驟直到所有的接收端都接收到其請求包

3 算法復(fù)雜度分析

4 仿真實驗

仿真實驗在不完美反饋下對所提方案MDIF與全頂點消除方案(full vertex elimination,FVE)[7]、無頂點消除方案(no vertex elimination, NVE)[7]和最大似然網(wǎng)絡(luò)編碼(maximum likelihood network coding,MLNC)[10]進行對比分析,并將完美反饋(perfect feedback,PF)下的性能指標(biāo)作對比。實驗網(wǎng)絡(luò)模型為無線組播網(wǎng)絡(luò),仿真實驗以平均完成時延和平均解碼時延為性能指標(biāo),通過多次仿真實驗取平均值。

如圖3所示,圖3(a)和圖3(b)分別表示平均完成時延和平均解碼時延隨數(shù)據(jù)包個數(shù)N變化的對比情況。參數(shù)設(shè)置為N∈[10,100],M=40,pi∈[0.2,0.3],qi∈[0.1,0.2]。

圖3 數(shù)據(jù)包數(shù)變化對性能的影響Fig.3 Influence of packet number variation on performance

仿真結(jié)果表明,隨著數(shù)據(jù)包數(shù)的增多,重傳恢復(fù)階段接收端成功接收丟包所需的重傳次數(shù)在增加,同時接收端接收到的不可解數(shù)據(jù)包概率也在增加,導(dǎo)致接收端的總解碼時延不斷增大。如圖3(a)所示,在請求數(shù)據(jù)包數(shù)較少時,MLNC性能優(yōu)于FVE和NVE并接近于本方案。

隨著請求數(shù)據(jù)包數(shù)的不斷增加,本方案的優(yōu)勢逐漸顯現(xiàn)并優(yōu)于其他3種方案。由于NVE和FVE需要多次重傳編碼包才能判斷反饋丟失下數(shù)據(jù)包的真實接收狀態(tài),因此其完成時延一直較高。而MLNC則根據(jù)最大似然狀態(tài)確定置信狀態(tài),相比于NVE和FVE可降低重傳次數(shù)。而本方案采用快速生成算法能有效減少完成時延。圖3(b)所示,本方案采用置信點更新算法能有效判斷在反饋信息丟失情況下數(shù)據(jù)包的真實狀態(tài),具有較低解碼時延。MLNC方案僅根據(jù)丟包率p和反饋丟失率q判斷反饋丟失下數(shù)據(jù)包的真實接收狀態(tài),未充分發(fā)揮POMDP的優(yōu)勢,因此對數(shù)據(jù)包的真實狀態(tài)有較高的誤判率,增加接收不可解數(shù)據(jù)包的數(shù)量,與本方案相比具有較高的解碼時延。NVE和FVE多次重傳編碼包雖然能確定反饋狀態(tài),但會增加接收端接收不可解編碼包的數(shù)量,解碼時延也相應(yīng)增加。

如圖4所示,各方案的性能隨著接收端個數(shù)M變化的性能對比。其中,M∈[10,100],N=30,pi∈[0.2,0.3],qi∈[0.1,0.2]。如圖4(a)所示,由于本方案采用基于置信點的更新算法,即通過選取請求集大于平均請求集的接收端構(gòu)造優(yōu)先發(fā)送子集,并在此子集上執(zhí)行更新操作,從而降低完成時延。在接收端數(shù)量較多時,MLNC、NVE及FVE需要多次重傳才能完成整個重傳恢復(fù)階段,而FVE先傳輸反饋狀態(tài)確定的接收端,而反饋狀態(tài)不確定的接收端需要等待較長的時間,完成時延高。如圖4(b)所示,由于MLNC、NVE與FVE采用相同的編碼方案,因此在接收端數(shù)量較少時NVE的性能優(yōu)于FVE并趨近于MLNC。隨著接收端數(shù)量的增加,本方案因采用快速生成算法,所以其解碼時延較低。

5 結(jié) 論

本文針對不完美反饋下多播網(wǎng)絡(luò)模型,提出不完美反饋下基于IDNC的時延最小化重傳方案MDIF。本方案在使用POMDP建立系統(tǒng)模型的基礎(chǔ)上,創(chuàng)建優(yōu)先發(fā)送集合,推導(dǎo)出置信點更新算法。之后,考慮接收端的接收狀態(tài),將丟失相同數(shù)據(jù)包的接收端整合以快速生成編碼包。仿真結(jié)果表明,本文所提方案能綜合考慮各種因素,有效降低系統(tǒng)的平均解碼時延和平均完成時延,為降低無線多播網(wǎng)絡(luò)時延提供了一種解決思路。