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

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

0 引 言

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

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

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

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

1.1 系統(tǒng)模型

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

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

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

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

(1)

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

(2)

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

(3)

1.2 POMDP模型

為估計(jì)不完美反饋下接收端的真實(shí)接收狀態(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);

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

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

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

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

1.3 IDNC圖

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

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

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

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

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

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

(9)

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

(10)

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

(11)

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

2.1 置信點(diǎn)更新算法

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

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

2.2 快速生成算法

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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