王 練,彭代淵,陳 巧

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

0 引 言

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

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

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

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

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

(1)

(2)

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

條件1在任何信宿節(jié)點(diǎn)，vi和vj所對(duì)應(yīng)數(shù)據(jù)包Pi和Pj都不同時(shí)丟失，稱Pi和Pj滿足結(jié)合關(guān)系，否則為互斥關(guān)系。

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

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

0表示丟包，1表示接收

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

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

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

條件3當(dāng)Pj∈Wi且Pl∈Wk時(shí)，有Pj∈Hk且Pl∈Hi。

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

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

2 基于IDNC的最大權(quán)重團(tuán)算法

2.1 時(shí)延問題描述

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

(3)

(4)

(5)

(6)

(7)

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

(8)

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

(9)

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

(10)

(11)

2.2 相關(guān)定理

(12)

定理1得證。

(13)

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

(14)

2.3 算法設(shè)計(jì)

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

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

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

4)頂點(diǎn)權(quán)重定義為ωi=rici。

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

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

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

4)頂點(diǎn)權(quán)重定義為ωi,j=ri,jci,j。

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

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

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

1：初始化：CS-IDNC=? //編碼數(shù)據(jù)包集合

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=? //編碼數(shù)據(jù)包集合

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 計(jì)算復(fù)雜度

綜上，2種算法的計(jì)算復(fù)雜度都由IDNC權(quán)重圖構(gòu)建情況決定，2種算法的計(jì)算復(fù)雜度對(duì)比如表2所示。

表2 計(jì)算復(fù)雜度Tab.2 Computation complexity

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

由圖3可以看出，隨著數(shù)據(jù)包數(shù)增加，算法時(shí)延性能值都逐漸增大，因?yàn)樵谛潘薰?jié)點(diǎn)數(shù)和丟包率不變情況下，數(shù)據(jù)包數(shù)N增加必然導(dǎo)致每個(gè)信宿節(jié)點(diǎn)丟失數(shù)據(jù)包更多，最后導(dǎo)致解碼時(shí)延均值、完成時(shí)延均值和系統(tǒng)完成時(shí)延都增加。WSAS和WSAG時(shí)延性能都比較好，因?yàn)閿?shù)據(jù)包數(shù)增加，數(shù)據(jù)包丟失分布越分散，數(shù)據(jù)包之間結(jié)合性越好，編碼機(jī)會(huì)更多。

圖2 信宿節(jié)點(diǎn)數(shù)對(duì)時(shí)延性能的影響 (N=40)Fig.2 Transmission performance versus the number of receivers(N=40)

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

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

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

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

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

4 結(jié)束語

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

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

參考文獻(xiàn)：

[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.