D2D網(wǎng)絡(luò)中基于截止時(shí)間約束的網(wǎng)絡(luò)編碼重傳方法*

王鵬飛，張冬梅，許 魁，沙 楠

(中國人民解放軍陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

0 引言

近年來，隨著無線接入和移動(dòng)互聯(lián)網(wǎng)的普及，移動(dòng)數(shù)據(jù)流量呈爆發(fā)性增長(zhǎng)趨勢(shì)[1]。流量的持續(xù)增長(zhǎng)，使現(xiàn)有的蜂窩網(wǎng)絡(luò)變得擁擠不堪，從而降低服務(wù)質(zhì)量和影響用戶體驗(yàn)。為此，終端直通技術(shù)(Device to Device，D2D)應(yīng)運(yùn)而生，并被確定為下一代移動(dòng)通信系統(tǒng)中的關(guān)鍵技術(shù)。D2D技術(shù)[2-3]允許終端設(shè)備直接通信，可以提供更可靠的傳輸鏈路、更低的傳輸延遲以及更高的能量效率。

網(wǎng)絡(luò)編碼作為一種跨層技術(shù)，能夠顯著地提高無線網(wǎng)絡(luò)吞吐量以及可靠性[4-6]。現(xiàn)有文獻(xiàn)研究表明，結(jié)合D2D與網(wǎng)絡(luò)編碼技術(shù)有許多優(yōu)勢(shì)，如降低重傳次數(shù)、減少譯碼時(shí)延、提高系統(tǒng)吞吐量等。文獻(xiàn)[7]、[8]研究了D2D網(wǎng)絡(luò)中基于立即可譯網(wǎng)絡(luò)編碼(Instantly Decodable Network Coding,IDNC)的協(xié)作傳輸方法，以降低重傳過程中的譯碼時(shí)延。其中，終端通過重傳編碼包來加快丟失數(shù)據(jù)包的恢復(fù)。文獻(xiàn)[9]利用隨機(jī)最短路徑建模來研究重傳次數(shù)最小化問題，提出了聯(lián)合選擇廣播源與網(wǎng)絡(luò)編碼包的啟發(fā)式重傳方法。為提高D2D協(xié)作重傳的性能，文獻(xiàn)[10]研究了基于網(wǎng)絡(luò)編碼的最小延時(shí)調(diào)度問題，提出了低復(fù)雜度的集中式算法，并進(jìn)一步給出了分布式解決方法。

然而，隨著無線網(wǎng)絡(luò)業(yè)務(wù)需求的深入與發(fā)展，諸如視頻直播、在線游戲等實(shí)時(shí)應(yīng)用被廣泛使用。此類應(yīng)用有鮮明的特征，即數(shù)據(jù)包具有嚴(yán)格的截止時(shí)間限制，超過截止時(shí)間后的數(shù)據(jù)包往往是無效的。因而，針對(duì)數(shù)據(jù)包具有截止時(shí)間約束的實(shí)時(shí)應(yīng)用，設(shè)計(jì)高效的網(wǎng)絡(luò)編碼策略是進(jìn)一步提高服務(wù)質(zhì)量，滿足用戶多樣化需求的關(guān)鍵。

本文結(jié)合IDNC策略，研究D2D網(wǎng)絡(luò)中基于截止時(shí)間約束的網(wǎng)絡(luò)編碼重傳(Deadline Constrained Network Coding Retransmission，DCCR)方法，以最大化用戶能夠及時(shí)收到的數(shù)據(jù)包總數(shù)。文章的主要貢獻(xiàn)如下：首先，將問題建模為整數(shù)線性規(guī)劃問題，并證明該問題是一個(gè)NP-hard問題；其次，構(gòu)建了新的IDNC圖模型，用于表示所有滿足截止時(shí)間約束的編碼組合，提出了基于最大權(quán)重團(tuán)搜尋的重傳調(diào)度方法；最后，仿真結(jié)果驗(yàn)證了提出方法的有效性。

1 系統(tǒng)模型與問題示例

1.1 系統(tǒng)模型

考慮如圖1所示無線D2D網(wǎng)絡(luò)。該模型包含一個(gè)基站(Broadcast Source，BS)以及M個(gè)終端設(shè)備R={r1,r2,…,rM}，所有設(shè)備都有興趣從基站處獲取N個(gè)原始數(shù)據(jù)包P={p1,p2,…,pN}。設(shè)備彼此之間非常接近，位于相同的傳輸范圍內(nèi)，可以通過WiFi或者藍(lán)牙等D2D鏈路相互連接。

圖1 D2D網(wǎng)絡(luò)示意圖

由于之前的廣播傳輸，假設(shè)設(shè)備在初始時(shí)刻已經(jīng)成功接收到部分?jǐn)?shù)據(jù)包。其中，H(ri)表示設(shè)備ri擁有的數(shù)據(jù)包集合，W(ri)表示設(shè)備ri仍然需要的數(shù)據(jù)包集合，存在H(ri)∩W(ri)=φ，H(ri)∪W(ri)=P。對(duì)于數(shù)據(jù)包pj∈P，定義Tj表示該數(shù)據(jù)包的接收截止時(shí)間。超過截止時(shí)間Tj后，數(shù)據(jù)包pj對(duì)于所有設(shè)備都是無效的。

設(shè)備可通過D2D鏈路進(jìn)行合作重傳來恢復(fù)所需丟失數(shù)據(jù)包。每次傳輸過后，設(shè)備向基站反饋邊信息(ACK/NACK)，用于更新數(shù)據(jù)包接收狀態(tài)，假設(shè)反饋信息沒有損耗。各D2D傳輸對(duì)(ri,rk)之間的丟包概率表示為εi,k，且εi,k=εk,i。為避免產(chǎn)生干擾，每個(gè)時(shí)隙僅允許單個(gè)設(shè)備進(jìn)行廣播傳輸，其余設(shè)備都處于偵聽狀態(tài)。

1.2 問題示例

如圖1所示，基站向設(shè)備{r1,r2,r3}廣播數(shù)據(jù)包{p1,p2,p3,p4}。廣播階段過后，設(shè)備擁有的數(shù)據(jù)包分別為：H(r1)={p1,p3}，H(r2)={p2,p3,p4}，H(r3)={p1,p2,p4}。若不考慮數(shù)據(jù)包的截止時(shí)間限制，給定三種不同的傳輸策略:

策略A:r3廣播p1⊕p2，r2廣播p3⊕p4；

策略B:r2廣播p2⊕p3，r3廣播p1⊕p4；

策略C：r2廣播p3⊕p4，r3廣播p1⊕p2。

以上三種傳輸策略都能夠保證設(shè)備在兩個(gè)時(shí)隙恢復(fù)所有丟包。然而，若考慮數(shù)據(jù)包具有截止時(shí)間限制，并且假設(shè)數(shù)據(jù)包{p1,p2,p3,p4}的截止時(shí)間為{1,1,2,2}。對(duì)于策略A，三個(gè)設(shè)備都能在截止時(shí)間限制內(nèi)恢復(fù)所有丟包；對(duì)于策略B，在第二個(gè)時(shí)隙r2才能恢復(fù)丟包p1，超過了p1的截止時(shí)間；對(duì)于策略C，p1和p2都超過了截止時(shí)間。顯然，策略A是最佳傳輸策略，因?yàn)樗袛?shù)據(jù)包都能在截止時(shí)間之前成功接收。

因此，本文要解決問題的核心就在于，根據(jù)數(shù)據(jù)包接收狀態(tài)信息、D2D鏈路丟包概率以及數(shù)據(jù)包截止時(shí)間，如何設(shè)計(jì)最佳的傳輸策略，使得設(shè)備能夠在截止時(shí)間之前收到的數(shù)據(jù)包總數(shù)最大化。為便于描述，將上述問題簡(jiǎn)稱為DCCR問題。

2 問題建模與分析

本節(jié)將給出DCCR問題的整數(shù)線性規(guī)劃建模，并分析求解問題的復(fù)雜度。在建模之前，對(duì)于?ri∈R,pj∈P，定義以下變量：

(1)

(2)

(3)

(4)

(5)

根據(jù)上述定義，若設(shè)備ri能夠在第t次傳輸中恢復(fù)丟失數(shù)據(jù)包pj，需滿足下列四個(gè)條件：設(shè)備ri不作為t時(shí)刻的發(fā)送設(shè)備；設(shè)備ri需要數(shù)據(jù)包pj；數(shù)據(jù)包pj參與t時(shí)刻的編碼；設(shè)備ri擁有編碼包中除pj之外的所有數(shù)據(jù)包。具體可描述如下：

(6)

綜上所述，DCCR問題可建模如下：

(7)

(8)

(9)

(10)

如式(7)所示，DCCR問題的優(yōu)化目標(biāo)是最大化設(shè)備能夠在截止時(shí)間之前成功接收的數(shù)據(jù)包總數(shù)。式(8)表示為避免產(chǎn)生干擾，每個(gè)時(shí)刻只允許單個(gè)設(shè)備作為廣播源；式(9)表示發(fā)送設(shè)備需要擁有參與編碼的數(shù)據(jù)包；式(10)表示數(shù)據(jù)包若能夠在截止時(shí)間之前正確接收，則表示該數(shù)據(jù)包在之前的某一時(shí)刻已被成功解碼。

引理：DCCR問題是一個(gè)NP-hard問題。

證明：考慮DCCR問題的一種特殊情況，存在某個(gè)設(shè)備擁有所有原始數(shù)據(jù)包，即?ri∈R,H(ri)=P；對(duì)于?pj∈P，數(shù)據(jù)包的截止時(shí)間都滿足Tj=1。在給定的假設(shè)下，DCCR問題簡(jiǎn)化為：固定發(fā)送設(shè)備，如何最大化能夠從單次傳輸中解碼出丟失數(shù)據(jù)包的設(shè)備數(shù)量。文獻(xiàn)[11]中的研究表明，該問題是一個(gè)NP-hard的索引編碼問題。因此，DCCR問題同樣也是一個(gè)NP-hard的問題，尋找最優(yōu)解的復(fù)雜度是指數(shù)級(jí)的。

3 IDNC圖的構(gòu)建

對(duì)于IDNC策略而言，為尋找最佳編碼包，一個(gè)有效的方法是構(gòu)建IDNC圖。文獻(xiàn)[9]通過在每個(gè)設(shè)備處構(gòu)建IDNC子圖以尋找該設(shè)備可生成的最佳編碼包，并選擇能夠帶來最大編碼增益的設(shè)備作為發(fā)送設(shè)備。然而，文獻(xiàn)[9]中的模型并不能直接運(yùn)用于DCCR問題，因?yàn)樵跇?gòu)建圖的過程中沒有考慮數(shù)據(jù)包截止時(shí)間的限制。本節(jié)將給出新的IDNC圖模型，在構(gòu)建過程中同時(shí)考慮數(shù)據(jù)包接收狀態(tài)以及截止時(shí)間的限制。

(1)pl∈Ht(ri)，設(shè)備ri擁有數(shù)據(jù)包pl；

(2)?k≠i,pl∈Wt(rk)，至少存在一個(gè)除ri之外的設(shè)備仍需要數(shù)據(jù)包pl；

(3)Tl≥t，數(shù)據(jù)包pl還未超過截止時(shí)間Tl。

(1)l=n，設(shè)備rk與rm需要同一個(gè)數(shù)據(jù)包pl=pn；

(2)pl∈Ht(rm)且pn∈Ht(rk)，設(shè)備rk與rm分別擁有彼此需要的數(shù)據(jù)包。當(dāng)正確接收編碼包pl⊕pn時(shí)，rk可通過pn⊕(pl⊕pn)解碼出丟失數(shù)據(jù)包pl。同理，rm可解碼出丟失數(shù)據(jù)包pn。

(11)

基于以上分析，同樣以圖1為例，第1個(gè)傳輸時(shí)隙設(shè)備處的IDNC圖可構(gòu)造如圖2所示。因此，每個(gè)設(shè)備可生成的最佳編碼包可以轉(zhuǎn)化為對(duì)應(yīng)IDNC圖中的最大權(quán)重團(tuán)(Maximal Weight Clique)選擇問題。

圖2 設(shè)備處的IDNC圖示例

4 提出方法

基于構(gòu)造的IDNC圖，為最大化設(shè)備可及時(shí)接收的數(shù)據(jù)包數(shù)量，本節(jié)針對(duì)DCCR問題提出了啟發(fā)式的傳輸調(diào)度方法。

4.1 最大權(quán)重團(tuán)搜尋算法

當(dāng)設(shè)備數(shù)量與數(shù)據(jù)包個(gè)數(shù)較大時(shí)，IDNC圖中的頂點(diǎn)數(shù)也會(huì)增多，拆分IDNC圖可得到許多最大團(tuán)，遍歷所有最大團(tuán)來尋找最大權(quán)重團(tuán)的計(jì)算量非常高，不適用于能耗與計(jì)算能力受限的D2D設(shè)備。為此，提出了啟發(fā)式的最大權(quán)重團(tuán)搜尋算法，降低尋找最佳編碼包的計(jì)算量與復(fù)雜度。

將式(11)給出的權(quán)重視為頂點(diǎn)的初始權(quán)重。此外，定義頂點(diǎn)vi,j與vk,l之間的連接鄰接系數(shù)如下：

(12)

最終，定義頂點(diǎn)vi,j的混合權(quán)重為：

(13)

由式(13)可見，圖中頂點(diǎn)的權(quán)重不僅與自身權(quán)重有關(guān)，還取決于其相鄰頂點(diǎn)的權(quán)重之和。頂點(diǎn)的混合權(quán)重越大，表明其帶來的傳輸增益越高，更應(yīng)該參與到當(dāng)前編碼。最大權(quán)重團(tuán)搜尋算法的具體步驟如下：

(1)構(gòu)建IDNC圖G(V,E)，初始化最大權(quán)重團(tuán)Cmax為空，根據(jù)式(11)計(jì)算出每個(gè)頂點(diǎn)的初始權(quán)重。

(2)根據(jù)式(12)、(13)計(jì)算出每個(gè)頂點(diǎn)的混合權(quán)重。其次，選擇混合權(quán)重最大的頂點(diǎn)vi,j，將其放入最大權(quán)重團(tuán)Cmax中。

(4)輸出算法最終得到的最大權(quán)重團(tuán)，確定需要發(fā)送的最佳編碼包。

4.2 重傳調(diào)度方法

對(duì)于DCCR問題，每個(gè)傳輸時(shí)隙都需要確定發(fā)送設(shè)備以及廣播的編碼包，整個(gè)傳輸過程由多個(gè)這樣的單次傳輸構(gòu)成，直到所有設(shè)備都恢復(fù)丟失數(shù)據(jù)包。就單次傳輸而言，每個(gè)設(shè)備都可能被選為發(fā)送設(shè)備，因此需要嘗試所有可能性并選擇能夠?qū)崿F(xiàn)最大編碼增益的設(shè)備作為當(dāng)前時(shí)隙的發(fā)送設(shè)備。基于以上分析，給出了DCCR問題的重傳調(diào)度方法，如下：

1 輸入:H(ri)、W(ri)、Tj2 初始化t←0,H0(ri)=H(ri),W0(ri)=W(ri);3 當(dāng)∪ri∈RWt(ri)≠?或者t>max(Tj),執(zhí)行循環(huán):4 對(duì)于?ri∈R,構(gòu)建IDNC圖Gti(Vti,Eti);5 找出圖Gti(Vti,Eti)中的最大權(quán)重團(tuán)Cti;6 計(jì)算Cti中頂點(diǎn)的權(quán)重和wti;7 選擇發(fā)送設(shè)備rs=argmaxri∈R{wti};8 廣播編碼包Pc=j∈{vi,j∈Cts}pj;9 t←t+1;10 更新Ht+1(ri)、Wt+1(ri);11 輸出:超過截止時(shí)間的數(shù)據(jù)包總數(shù)

5 仿真結(jié)果分析

本節(jié)以及時(shí)接收的數(shù)據(jù)包總數(shù)、截止時(shí)間超出率η為評(píng)價(jià)指標(biāo)，對(duì)提出的方法進(jìn)行仿真比較。截止時(shí)間超出率可由式(14)計(jì)算：

(14)

其中，Se表示超過截止時(shí)間的數(shù)據(jù)包總數(shù)，Sn表示初始時(shí)刻所有設(shè)備需要的數(shù)據(jù)包總數(shù)。

設(shè)備在初始廣播階段后丟失部分原始數(shù)據(jù)包，各終端的丟失數(shù)據(jù)包根據(jù)概率ρ=0.4從N個(gè)數(shù)據(jù)包中隨機(jī)選擇。重傳階段，各D2D傳輸對(duì)(ri,rk)之間的丟包概率設(shè)置為εi,k=[0.1,0.2]。將本文方法與以下三種方法作對(duì)比：不采用網(wǎng)絡(luò)編碼(No-Coding)的方法，每次重傳最接近截止時(shí)間的數(shù)據(jù)包；傳統(tǒng)的協(xié)作重傳(Traditional Cooperation Retransmission,TCR)方法[9]，該方法不考慮數(shù)據(jù)包截止時(shí)間的約束，以最小化設(shè)備恢復(fù)丟包所需的重傳次數(shù)為目標(biāo)設(shè)計(jì)傳輸策略；隨機(jī)選擇發(fā)送設(shè)備(Random Device Selection,RDS)的方法，該方法在每次傳輸時(shí)隨機(jī)選擇發(fā)送設(shè)備，與本文采用相同的編碼策略。

固定設(shè)備數(shù)量M=10，圖3和圖4給出了截止時(shí)間超出率隨數(shù)據(jù)包個(gè)數(shù)的變化。其中，截止時(shí)間的取值范圍分別為[1,15]、[1,30]。仿真結(jié)果表明，DCCR方法的截止時(shí)間超出率遠(yuǎn)遠(yuǎn)低于其他方法。由于在設(shè)計(jì)編碼策略時(shí)未考慮截止時(shí)間的約束，相較于DCCR以及RDS方法，TCR方法的性能較差。此外，隨著數(shù)據(jù)包個(gè)數(shù)的增加，截止時(shí)間超出率逐漸變大，因?yàn)樵谙嗤臅r(shí)間內(nèi)有更多的數(shù)據(jù)包需要接收。

圖3 截止時(shí)間區(qū)間為[1,15]時(shí)的性能比較

圖4 截止時(shí)間區(qū)間為[1,30]時(shí)的性能比較

固定數(shù)據(jù)包個(gè)數(shù)N=20，圖5和圖6給出了及時(shí)接收的數(shù)據(jù)包總數(shù)隨設(shè)備數(shù)量的變化。其中，截止時(shí)間取值范圍分別為[1,5]、[1,10]。同樣地，相比于其他方法，DCCR方法能夠使更多的數(shù)據(jù)包及時(shí)接收。此外，隨著截止時(shí)間的取值范圍增大，可以及時(shí)接收的數(shù)據(jù)包總數(shù)會(huì)進(jìn)一步增多。

圖5 截止時(shí)間區(qū)間為[1,5]時(shí)的性能比較

圖6 截止時(shí)間區(qū)間為[1,10]時(shí)的性能比較

6 結(jié)論

針對(duì)數(shù)據(jù)包具有截止時(shí)間限制的實(shí)時(shí)應(yīng)用，為進(jìn)一步提高服務(wù)質(zhì)量，本文設(shè)計(jì)了D2D網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的重傳調(diào)度方法。為表示所有滿足截止時(shí)間約束的編碼組合，本文構(gòu)建了新的IDNC圖模型，給出了基于最大權(quán)重團(tuán)搜尋的重傳調(diào)度方法。仿真結(jié)果表明，與其他方法相比，本文提出的方法能夠有效地增加接收的數(shù)據(jù)包數(shù)量，降低超過截止時(shí)間約束率。