立即可解網絡編碼應用于無線網絡重傳中的時延分析

王 練,彭代淵,陳 巧

(1.西南交通大學 信息科學與技術學院，成都 611756；2.重慶郵電大學 計算機科學與技術學院，重慶 400065)

0 引 言

2000年，Ahlswede等[1]提出了網絡編碼技術(network coding，NC)，其核心思想是允許網絡中間節(jié)點對信息進行編碼組合并轉發(fā)，信宿節(jié)點可對編碼包進行解碼。NC的技術特點為無線網絡重傳提供了新思路，不同信宿節(jié)點可根據相同編碼包解碼出各自丟失數據包，進而提高數據包恢復效率，改善重傳性能?；诰W絡編碼思想，Ho等[2]提出了隨機線性網絡編碼(random linear network coding，RLNC)，RLNC編碼方式是將數據包進行隨機線性組合生成多個線性無關的編碼包，當信宿節(jié)點收到所有編碼包后可進行解碼進而得到原始信息，RLNC已被證明是一種能實現最優(yōu)吞吐量的網絡編碼機制[3]，但RLNC要求每個信宿節(jié)點必須收到足夠多編碼包后才能恢復原始數據包，導致信宿節(jié)點等待解碼的時延較大，對于時延敏感的應用場景RLNC并不適用。Katti等[4]則利用異或(exclusive OR,XOR)運算的特點，提出了機會式網絡編碼(opportunistic network coding，ONC)，與RLNC不同的是，ONC是將多個不同的數據包進行XOR運算從而生成編碼包，如果某個信宿節(jié)點只丟失該編碼包集合中的某一數據包，則該信宿節(jié)點能對編碼包解碼并恢復丟包，信宿節(jié)點不需等待所有編碼包到達就能恢復丟失數據包，因而等待解碼所需的時延相比RLNC少。

隨著無線網絡的發(fā)展，基于無線網絡的實時應用被廣泛使用，例如實時多播服務、車聯網中道路單元與汽車之間的實時安全信息、傳感網絡中節(jié)點之間的實時信息傳輸等。針對實時應用，文獻[5-6]首先考慮了基于網絡編碼重傳中的時延問題，并提出了立即可解網絡編碼(instantly decodable network coding，IDNC)思想，IDNC已作為網絡編碼的一個子類問題被廣泛研究。按照編碼條件不同，IDNC思想分為2類，第1類是狹義立即可解網絡編碼(strict instantly decodable network coding， S-IDNC)[5-6]，S-IDNC編碼條件苛刻，要求生成的編碼包在其所有目標信宿節(jié)點都能立即解碼。第2類是廣義立即可解網絡編碼(generalized instantly decodable network coding，G-IDNC)[7]，不同于 S-IDNC的是，G-IDNC的編碼條件不限制編碼包的即時可解性，信宿節(jié)點可將不可解編碼包直接丟 棄，G-IDNC對數據包的編碼機會利用率更高，滿足編碼條件的編碼包更多，但編碼包生成過程的復雜度也更大。 S-IDNC和G-IDNC都利用機會式網絡編碼思想，使用XOR運算進行編解碼操作，編解碼簡單。文獻[8-11]具體研究了IDNC問題中最小化完成時延問題，文獻[12-13]研究了IDNC問題中最小化解碼時延問題，文獻[14-15]則分析了完成時間和解碼時延折中的問題。

為比較S-IDNC和G-IDNC的時延性能差異。本文針對無線單跳網絡廣播場景，在考慮信宿節(jié)點丟包率情況下，分別提出2種IDNC加權算法，并以所提算法為支撐,間接比較S-IDNC和G-IDNC在信宿節(jié)點的平均解碼時延、信宿節(jié)點平均完成時延、系統(tǒng)完成時延和信宿節(jié)點完成時延大小分布上的差異。以期所得結論為基于IDNC在無線網絡重傳中應用選擇提供參考。

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

3)無效編碼包。集合C不包含Ri丟失的數據包，即C∩Wi=?，則P*在Ri處無效。

(1)

(2)

在IDNC問題研究中，數據包之間的編碼關系用IDNC圖刻畫，圖1給出了S-IDNC和G-IDNC圖。對于S-IDNC編碼思想，要求生成的編碼包P*在Ri(i∈{1,2,…,M})處是立即可解或無效，其IDNC圖用GS-IDNC(v,ε)表示，頂點vi表示一個丟包Pi∈L，L表示丟失包集合，滿足L=W1∪W2∪…∪WM，邊εi,j表示滿足S-IDNC編碼條件的一個二元編碼包，圖1a中任意一個團則表示一個多元S-IDNC編碼包。頂點vi和vj之間存在邊εi,j∈ε必須滿足條件1。

條件1在任何信宿節(jié)點，vi和vj所對應數據包Pi和Pj都不同時丟失，稱Pi和Pj滿足結合關系，否則為互斥關系。

例1：圖1a中狀態(tài)矩陣對應的GS-IDNC(v,ε)如表1所示。

表1 狀態(tài)矩陣Tab.1 System matrix

0表示丟包，1表示接收

圖1a中頂點v1和v4之間存在一條邊，表明P*=P1⊕P4滿足S-IDNC編碼條件的二元編碼包，P*在P1目標信宿節(jié)點R2，R4和P4目標信宿節(jié)點R3處都立即可解，R2和R4由P4⊕(P1⊕P4)解碼出P1，R3由P1⊕(P1⊕P4)解碼出P4。v4，v5和v6以及之間的邊組成一個團，則表明P*=P4⊕P5⊕P6滿足S-IDNC編碼條件的多元編碼包。

G-IDNC允許編碼包在某些信宿節(jié)點不可解，對應IDNC圖用GG-IDNC(v,ε)表示，頂點vi,j表示數據包Pj∈Wi，頂點vi,j和vk,l之間存在一條邊εi,j;k,l∈ε則必須滿足條件2或條件3。

條件2j=l，Ri和Rk丟失相同的數據包Pj=Pl。

條件3當Pj∈Wi且Pl∈Wk時，有Pj∈Hk且Pl∈Hi。

GG-IDNC(v,ε)中的任意一條邊εi,j;k,l表示編碼包Pj⊕Pl在Ri和Rk處是立即可解的。表1所示的狀態(tài)矩陣所對應的GG-IDNC(v,ε)如圖1b所示，頂點v1,5和v2,1之間存在一條邊，即編碼包P1⊕P5在R1和R2處可以立即解碼，盡管P1⊕P5在R4處不可解，但G-IDNC允許這種情況，這也是G-IDNC區(qū)別于S-IDNC的地方。由圖1a和圖1b對比可知,GG-IDNC(v,ε)的復雜度高于GS-IDNC(v,ε)，G-IDNC刻畫的編碼關系更為詳細。

圖1 S-IDNC圖和G-IDNC圖Fig.1 S-IDNC graph and G-IDNC graph

2 基于IDNC的最大權重團算法

2.1 時延問題描述

基于立即可解網絡編碼的重傳思想對時延要求較高，時延分為完成時延和解碼時延，完成時延指恢復所有丟包系統(tǒng)所經歷的重傳次數[8]，文獻[7]給出了解碼時延定義，是指編碼包P*在某個丟包信宿節(jié)點Ri處是不可解或無效的，則Ri會產生一個單位的解碼時延，該定義沒考慮編碼包丟失的情況，忽略了鏈路丟包率對時延的影響，本文在該定義基礎上，對解碼時延定義進行擴展。

(3)

(4)

(5)

(6)

(7)

以上分析可知，信宿節(jié)點完成時延由其解碼時延和丟失數據包集合大小|Wi|決定，初始傳輸后|Wi|已確定，因而本文從解碼時延角度分析時延問題。

(8)

(8)式中，pi表示信宿節(jié)點Ri的丟包率。由(2)式、(8)式可得

(9)

用LR表示有丟包的信宿節(jié)點集合，則(9)式滿足

(10)

(11)

2.2 相關定理

(12)

定理1得證。

(13)

綜合1)，2)可知定理2得證。

(14)

2.3 算法設計

利用啟發(fā)式算法把尋找最大權重編碼包問題轉化為IDNC權重圖中尋找最大權重團問題，S-IDNC權重圖和G-IDNC權重圖定義分別如下。

S-IDNC權重圖GS-IDNC(ν,ε,ω) 在GS-IDNC(ν,ε)中增加頂點權重值ω，頂點vi的權重ωi計算方式如下。

1)用ai,j表示S-IDNC圖中2個頂點vi和vj的連接關系，若vi和vj相連，有ai,j=1，否則ai,j=0；

4)頂點權重定義為ωi=rici。

G-IDNC權重圖GG-IDNC(ν,ε,ω) 在GG-IDNC(ν,ε)中增加頂點權重值ω，頂點vi,j的權重ωi,j的計算方式如下：

1)定義ai,j;k,l表示頂點vi,j和vk,l的連接關系，若vi,j和vk,l之間存在一條邊，有ai,j;k,l=1，否則ai,j;k,l=0；

2)定義接收權重ri,j表示數據包Pj在信宿節(jié)點Ri被成功接收的概率期望值，有ri,j=1-pi；

4)頂點權重定義為ωi,j=ri,jci,j。

基于以上分析以及IDNC權重圖定義，提出2種數據包選擇算法生成S-IDNC編碼包和G-IDNC編碼包，分別為S-IDNC帶權重頂點搜索算法(weighted search algorithm for S-IDNC，WSAS)和G-IDNC帶權重頂點搜索算法(weighted search algorithm for G-IDNC，WSAG)。2種算法在執(zhí)行的過程中都會更新權重圖，更新方式是刪除與當前權重最大頂點不相連的頂點以及邊。算法偽代碼如下。

WSAS算法生成S-IDNC編碼包。

輸入：Ω//狀態(tài)矩陣

1：初始化：CS-IDNC=? //編碼數據包集合

2：if |TPk|=|LR|

3：P*=Pk

4：else

5： GenerateGS-IDNC(v,ε,ω)

6： while (ε≠?)

8：CS-IDNC=CS-IDNC∪Pmax//Pmax→CS-IDNC

9： updatesGS-IDNC(v,ε,ω)

10：end while

12：end if

13：transmitP*

14：all receivers decodeP*

15：SupdatesΩ

16：Repeat the above steps until all lost packets recovered.

WSAG算法生成G-IDNC編碼包。

輸入：Ω//狀態(tài)矩陣

1：初始化：CG-IDNC=? //編碼數據包集合

2：if |TPk|=|LR|

3：P*=Pk

4：else

5： GenerateGG-IDNC(v,ε,ω)

6： while (ε≠?)

8：CG-IDNC=CG-IDNC∪Pmax//Pmax→CG-IDNC

9： updatesGG-IDNC(v,ε,ω)

10：end while

12：end if

13：transmitP*

14：all receivers decodeP*

15：SupdatesΩ

16：Repeat the above steps until all lost packets recovered.

2.4 計算復雜度

綜上，2種算法的計算復雜度都由IDNC權重圖構建情況決定，2種算法的計算復雜度對比如表2所示。

表2 計算復雜度Tab.2 Computation complexity

3 仿真實驗與分析

本節(jié)對所提WSAS和WSAG算法進行時延性能仿真，并同文獻[6]中的算法Algorithm_1，ARQ重傳算法，以及理想情況下性能值進行比較。理想情況下的性能值用Lower表示，其對應的信宿節(jié)點平均解碼時延、信宿節(jié)點平均完成時延和系統(tǒng)完成時延理想性能值大小已在(5)式、(6)式和(7)式中給出。仿真平臺為MATLAB 2014a，比較的時延性能有信宿節(jié)點平均解碼時延，信宿節(jié)點平均完成時延和系統(tǒng)完成時延，同時也比較了WSAS和WSAG在信宿節(jié)點處的時延大小分布。通過比較WSAS和WSAG的重傳性能，間接比較S-IDNC和G-IDNC 2種編碼思想的區(qū)別。本文進行以下2個實驗。

實驗1測試信宿節(jié)點數對時延性能影響。數據包數N=40，信宿節(jié)點丟包率pi(0≤pi≤0.4)，信宿節(jié)點數M從10增加到100，每次遞增10，圖2給出了實驗結果，其中，圖2d和圖2e分別表示信宿節(jié)點在不同情況下的完成時延大小分布。

由圖2a和圖2b對比可以看出，信宿節(jié)點平均完成時延和平均解碼時延的變化趨勢相同，這間接證明了信宿節(jié)點完成時延大小由其解碼時延以及丟失數據包數決定，完成時延大小的變化由解碼時延大小的變化決定。隨著信宿節(jié)點數增加，WSAS，WSAG和Algorithm_1的時延性能都逐漸變差，因為隨著M增加，相同數據包在更多信宿節(jié)點丟失，數據包丟失分布更密集，編碼機會減少，最后導致基于網絡編碼重傳機制的重傳性能下降。WSAG在平均解碼時延和平均完成時延上都要優(yōu)于對比算法，系統(tǒng)完成時延卻高于Algorithm_1和WSAS。進一步，由圖2d和圖2e可看出，WSAS的信宿節(jié)點完成時延大小分布相對較集中，且時延值較大，但信宿節(jié)點的完成時延最大值小于WSAG的完成時延最大值，與圖2c所反映結果相同；WSAG的信宿節(jié)點完成時延大小分布更為分散，完成時延均值優(yōu)于WSAS的，與圖2b所反映結果相同。

實驗2測試數據包數對時延性能的影響。信宿節(jié)點M=40，數據包數N從10變化到100，每次遞增10，圖3給出了實驗結果。

由圖3可以看出，隨著數據包數增加，算法時延性能值都逐漸增大，因為在信宿節(jié)點數和丟包率不變情況下，數據包數N增加必然導致每個信宿節(jié)點丟失數據包更多，最后導致解碼時延均值、完成時延均值和系統(tǒng)完成時延都增加。WSAS和WSAG時延性能都比較好，因為數據包數增加，數據包丟失分布越分散，數據包之間結合性越好，編碼機會更多。

圖2 信宿節(jié)點數對時延性能的影響 (N=40)Fig.2 Transmission performance versus the number of receivers(N=40)

WSAS和WSAG分別是S-IDNC和G-IDNC編碼思想體現，以上分析間接比較了S-IDNC和G-IDNC在重傳時延性能上的區(qū)別，綜合以上分析結果可得以下結論。

1)G-IDNC編碼方案在信宿節(jié)點平均解碼時延和平均完成時延上要優(yōu)于S-IDNC編碼方案。

2)G-IDNC編碼方案的系統(tǒng)完成時延要高于S-IDNC編碼方案。

3)G-IDNC編碼方案使得信宿節(jié)點的時延(解碼時延和完成時延)大小分布比較分散，S-IDNC的時延大小分布較為集中。

4)平均完成時延、平均解碼時延和系統(tǒng)完成時延都受信宿節(jié)點丟包分布情況影響，丟包分布越分散，數據包之間的可結合性越好，基于IDNC重傳方案在重傳性能上表現越好。

4 結束語

本文分析了S-IDNC和G-IDNC這2種典型的IDNC編碼思想，并針對這2種思想分別提出了2種IDNC重傳算法WSAS和WSAG，為使每次重傳的編碼包在信宿節(jié)點處產生解碼時延最小，2種算法都將數據包選擇問題轉換為IDNC權重圖中選擇最大權重團問題。通過實驗對比了WSAS和WSAG的重傳時延性能，結果表明WSAS和WSAG都能有效改善重傳性能。同時，以實驗結果間接分析了S-IDNC和G-IDNC的差異，基于G-IDNC重傳方案在信宿節(jié)點完成時延均值和解碼時延均值上要優(yōu)于基于S-IDNC的重傳方案，但前者在系統(tǒng)完成時延上要弱于后者；基于S-IDNC和G-IDNC的重傳方案都不能在信宿節(jié)點時延均值和系統(tǒng)完成時延上同時達到最優(yōu)。

圖3 數據包數對時延性能的影響(M=40)Fig.3 Transmission performance versus the number of packets(M=40)

參考文獻：

[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. Information Theory, IEEE Transactions on, 2000, 46(4): 1204-1216.

[2] HO T, MéDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413-4430.

[3] ERYILMAZ A, OZDAGLAR A, MéDARD M, et al. On the delay and throughput gains of coding in unreliable networks[J]. IEEE Transactions on Information Theory, 2008, 54(12): 5511-5524.

[4] KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 243-254.

[5] SADEGHI P, TRASKOV D, KOETTER R. Adaptive network coding for broadcast channels[C]//Proc. 5th Workshop on Network Coding, Theory and Applications. New York: IEEE Press, 2009: 80-86.

[6] SADEGHI P, SHAMS R, TRASKOV D. An optimal adaptive network coding scheme for minimizing decoding delay in broadcast erasure channels[J]. EURASIP Journal on Wireless Communications and Networking, 2010(1): 1.

[7] SOROUR S, VALAEE S. Minimum Broadcast Decoding Delay for Generalized Instantly Decodable Network Coding[C]//IEEE Global Telecommunications Conference. New Youk: IEEE Press, 2010:1-5.

[8] SOROUR S, VALAEE S. On Minimizing Broadcast Completion Delay for Instantly Decodable Network Coding[C]//IEEE International Conference on Communications. New York: IEEE Press, 2010:1-5.

[9] SOROUR S, DOUIK A, VALAEE S, et al. Partially blind instantly decodable network codes for lossy feedback environment[J]. IEEE Transactions on Wireless Communications, 2014, 13(9): 4871-4883.

[10] LE A, TEHRANI A S, DIMAKIS A G, et al. Instantly decodable network codes for real-time applications[C]//2013 international symposium on network coding (NetCod). New York: IEEE Press, 2013: 1-6.

[11] SOROUR S, VALAEE S. Completion delay minimization for instantly decodable network codes[J]. IEEE/ACM Transactions on Networking (TON), 2015, 23(5): 1553-1567.

[12] DOUIK A, SOROUR S, Al-NAFFOURI T Y, et al. A lossy graph model for delay reduction in generalized instantly decodable network coding[J]. IEEE Wireless Communications Letters, 2014, 3(3): 281-284.

[13] ZHAN C, XIAO F. Coding based wireless broadcast scheduling in real time applications[J]. Journal of Network and Computer Applications, 2016, 64: 194-203.

[14] YU M, ABOUTORAB N, SADEGHI P. From instantly decodable to random linear network coded broadcast[J]. IEEE Transactions on Communications, 2014, 62(11): 3943-3955.

[15] ABOUTORAB N, SADEGHI P, SOROUR S. Enabling a tradeoff between completion time and decoding delay in instantly decodable network coded systems[J]. IEEE Transactions on Communications, 2014, 62(4): 1296-1309.