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

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

0 引言

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

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

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

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

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

1.1 系統(tǒng)模型

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

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

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

設(shè)備可通過D2D鏈路進行合作重傳來恢復(fù)所需丟失數(shù)據(jù)包。每次傳輸過后，設(shè)備向基站反饋邊信息(ACK/NACK)，用于更新數(shù)據(jù)包接收狀態(tài)，假設(shè)反饋信息沒有損耗。各D2D傳輸對(ri,rk)之間的丟包概率表示為εi,k，且εi,k=εk,i。為避免產(chǎn)生干擾，每個時隙僅允許單個設(shè)備進行廣播傳輸，其余設(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ù)包的截止時間限制，給定三種不同的傳輸策略:

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

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

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

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

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

2 問題建模與分析

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

(1)

(2)

(3)

(4)

(5)

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

(6)

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

(7)

(8)

(9)

(10)

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

引理：DCCR問題是一個NP-hard問題。

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

3 IDNC圖的構(gòu)建

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

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

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

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

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

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

(11)

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

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

4 提出方法

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

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

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

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

(12)

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

(13)

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

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

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

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

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

對于DCCR問題，每個傳輸時隙都需要確定發(fā)送設(shè)備以及廣播的編碼包，整個傳輸過程由多個這樣的單次傳輸構(gòu)成，直到所有設(shè)備都恢復(fù)丟失數(shù)據(jù)包。就單次傳輸而言，每個設(shè)備都可能被選為發(fā)送設(shè)備，因此需要嘗試所有可能性并選擇能夠?qū)崿F(xiàn)最大編碼增益的設(shè)備作為當(dāng)前時隙的發(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 對于?ri∈R,構(gòu)建IDNC圖Gti(Vti,Eti);5 找出圖Gti(Vti,Eti)中的最大權(quán)重團Cti;6 計算Cti中頂點的權(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ù)據(jù)包總數(shù)

5 仿真結(jié)果分析

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

(14)

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

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

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

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

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

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

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

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

6 結(jié)論

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