不完美反饋下基于立即可解網絡編碼的多播重傳機制

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

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

0 引 言

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

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

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

1 系統模型和參數

1.1 系統模型

如圖1所示,無線多播網絡模型中發送端S將N個數據包發送給M個接收端,每個接收端需接收N個原包或N個原包的子集。定義原包集P={Pi|1≤i≤N},信宿節點集R={Ri|1≤i≤M}。

圖1 無線多播網絡模型Fig.1 Wireless multicast network model

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

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

(1)

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

(2)

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

(3)

1.2 POMDP模型

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

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

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

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

狀態轉移概率T(s,a,s′):T表示發送編碼包a后,編碼包接收狀態由s轉移到s′的概率：

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

1.3 IDNC圖

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

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

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

3個接收端接收4個數據包的反饋狀態及其IDNC圖,如圖2所示。當建立IDNC圖后,分別在主圖和次圖執行最大權團搜索算法生成最佳重傳編碼包,重復該過程直到所有的接收端都接收到其所需的數據包。

圖2 狀態反饋矩陣及其對應的IDNC圖Fig.2 SFM and IDNC graph

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

(9)

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

(10)

式中:aij,kl為vij和vkl的鄰接指數,

(11)

2 不完美反饋下基于立即可解網絡編碼的重傳方案

2.1 置信點更新算法

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

算法 1 置信點更新算法輸入:狀態反饋矩陣SFM,觀測狀態矩陣OSM;最佳重傳編碼包a*輸出:優先發送集合M',置信狀態子集b',估計狀態矩陣OEM,更新后的置信狀態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 將接收端對應的置信點狀態加入置信點狀態子集:b'=b'∪bi步驟 7 end if步驟 8 end for步驟 9 for i=1∶M步驟 10 if發送端S接收到目的接收端Ri的反饋步驟 11 更新估計狀態矩陣OEM步驟 12 else if目的接收端是優先發送集合的成員:Ri?M'步驟 13 由式(7)計算可能的置信度bi步驟 14 更新估計狀態矩陣OEM步驟 15 end if步驟 16 end if步驟 17 end for

2.2 快速生成算法

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

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

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

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

3 算法復雜度分析

4 仿真實驗

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

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

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

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

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

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

5 結 論

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