姚玉坤，馮 鑫 ，甘澤鋒，滿 巧

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

2000年，Ahlswede等人[1]提出了網(wǎng)絡(luò)編碼(Network Coding,NC)，證明其不僅可以提高網(wǎng)絡(luò)吞吐量，還能顯著減少擦除信道上數(shù)據(jù)恢復(fù)的時(shí)延?，F(xiàn)有文獻(xiàn)中將網(wǎng)絡(luò)編碼分為兩類，即隨機(jī)網(wǎng)絡(luò)編碼(Random Network Coding,RNC)[2-3]和機(jī)會(huì)網(wǎng)絡(luò)編碼(Opportunistic Network Coding,ONC)[5-6]。RNC編碼使用非零獨(dú)立隨機(jī)系數(shù)，優(yōu)勢(shì)在于在減少傳輸次數(shù)。由于RNC不允許幀的漸進(jìn)譯碼，因此不適用于低時(shí)延的網(wǎng)絡(luò)。在ONC中，發(fā)送方根據(jù)接收方丟失數(shù)據(jù)包的情況來(lái)生成編碼包并使用漸進(jìn)解碼，適用于對(duì)時(shí)延要求高的網(wǎng)絡(luò)。

立即可解網(wǎng)絡(luò)編碼(Instantly Decodable Network Coding,IDNC)是ONC的一個(gè)子類。由于IDNC的發(fā)送端以二進(jìn)制異或?qū)?shù)據(jù)包進(jìn)行編碼，接收端使用同樣的方式進(jìn)行譯碼的特性，有效降低了編碼和解碼的時(shí)延，成為最近十幾年的研究熱點(diǎn)[9-15]。

在D2D網(wǎng)絡(luò)中，由于終端發(fā)射功率有限，不能做到所有終端之間直接通信。然而，在PC-D2D網(wǎng)絡(luò)的研究中[12,16-17]，未曾考慮到發(fā)送終端集合使用IDNC編碼廣播后，接收終端收到無(wú)效編碼包或不可解編碼包對(duì)PC-D2D網(wǎng)的協(xié)作終端選擇的影響。為此，本文考慮到PC-D2D網(wǎng)絡(luò)中接收終端收到無(wú)效解碼包和不可解碼編碼包對(duì)擴(kuò)展協(xié)作終端的影響，提出基于犧牲節(jié)點(diǎn)的協(xié)作重傳策略(Nodes Sacrifice Collaboration Retransmission，NSCR)。在重傳階段，NSCR犧牲部分無(wú)效解碼或不可解碼的接收終端，擴(kuò)展出備選協(xié)作終端加入?yún)f(xié)作發(fā)送集合，可以有效降低平均解碼時(shí)延，從而減少了系統(tǒng)的重傳次數(shù)。

1 網(wǎng)絡(luò)模型及相關(guān)定義

1.1 網(wǎng)絡(luò)模型

D2D網(wǎng)絡(luò)模型，包含一個(gè)作為信源的基站(Broadcast Source,BS)和Z個(gè)終端。Z個(gè)終端需求的數(shù)據(jù)包相同，需求為N個(gè)數(shù)據(jù)包P={p1,p2，…，pN}?；镜礁鹘K端的鏈路丟包率為qi,j(?i∈Z,?j∈Z)。網(wǎng)絡(luò)模型如圖1所示。

圖1 蜂窩網(wǎng)絡(luò)下的D2D通信

該網(wǎng)絡(luò)場(chǎng)景下,通信過程分為兩個(gè)階段：

第一階段，基站廣播發(fā)送數(shù)據(jù)包P，等待數(shù)據(jù)傳輸完畢后，接收終端使用ACK幀向基站反饋數(shù)據(jù)包接收情況，基站建立狀態(tài)反饋矩陣(State Feedback Matrix,SFM)。第一階段結(jié)束后，各接收終端數(shù)據(jù)包可以分為兩類：

(1)已正確接收的數(shù)據(jù)包集合(Hi)：終端Di正確接收的數(shù)據(jù)包集合；

(2)未正確接收的數(shù)據(jù)包集合(Wi)：終端Di未正確接收的數(shù)據(jù)包集合。

第二階段，在BS依次廣播數(shù)據(jù)包P后，Z個(gè)終端中滿足建立D2D鏈路的設(shè)備集合為M，其中各源數(shù)據(jù)包至少被M的一個(gè)終端正確接收?；臼跈?quán)用戶頻段，建立D2D鏈路。終端設(shè)備通過D2D鏈路合作傳輸恢復(fù)丟失數(shù)據(jù)包。

本文中主要符號(hào)及含義如表1所示。

表1 全文主要符合及含義

1.2 相關(guān)定義

定義1部分連接D2D網(wǎng)絡(luò)(Partially Connected D2D Network,PC-D2D)：?Dm∈Ci,j,Di≠Dj,Di?Cj,Dj?Ci,其中Ci為Di的通信范圍，Cj為Dj的通信范圍，Ci,j為設(shè)備Di與Dj共同的通信范圍。表述為Di與Dj互不在對(duì)方通信范圍內(nèi)，但是可以通過Dm中繼通信。

定義2狀態(tài)反饋矩陣(State Feedback Matrix,SFM):各個(gè)終端反饋給基站的描述數(shù)據(jù)包接收情況的矩陣，定義為

SMF=[fi,j]M×N(?i∈M,?j∈N)；

(1)

定義3解碼時(shí)延(Decoding Delay,DD)：在發(fā)送端采用IDNC編碼發(fā)送編碼包時(shí)，如果接收端Wi≠?，則接收終端Di接收到的編碼包有以下三種可能，分別為：

一次數(shù)據(jù)重傳中，如果接收終端Di收到的編碼包為不可解編碼包，無(wú)效編碼包或沒有收到編碼包時(shí)終端解碼時(shí)延會(huì)增加一個(gè)單位，具體描述為

(2)

定義4平均解碼時(shí)延(Average Decoding Delay,ADD)：一次數(shù)據(jù)重傳中，所有接收終端的解碼時(shí)延的平均值，定義為

(3)

定義5本地狀態(tài)反饋矩陣(Local State Feed-back Matrix,LSFM)：在終端Dk通信范圍內(nèi)終端的數(shù)據(jù)包接收情況，定義為

LSMFk=[fi,j]L×N(?Di∈Ck,?j∈N)，

(4)

2 基于犧牲節(jié)點(diǎn)的D2D協(xié)作重傳策略

在PC-D2D網(wǎng)絡(luò)中，理想情況下，一次重傳過程中編碼包在所有接收終端都是立即可解編碼包，接收終端的總解碼時(shí)延增加為0；最差情況下，編碼包在所有接收終端都是不可解編碼包或者無(wú)效編碼包，接收終端的解碼時(shí)延增加1，總解碼時(shí)延為Wm。一般情況下，一次重傳的解碼時(shí)延的增加量為：最差情況下的總解碼時(shí)延增量減去成功接收立即可解編碼包的終端數(shù)量。這里，引入文獻(xiàn)[16]關(guān)于實(shí)際總解碼時(shí)延增量的表達(dá)式：

(5)

由公式(5)可知，總解碼時(shí)延與協(xié)作發(fā)送集合終端選取和接收終端的鏈路質(zhì)量有關(guān)。由文獻(xiàn)[7]可知，最優(yōu)編碼包的選取方式會(huì)影響整個(gè)系統(tǒng)的平均解碼時(shí)延，進(jìn)而影響到重傳次數(shù)，所以降低重傳次數(shù)要從協(xié)作發(fā)送終端集合和最優(yōu)編碼包的選取入手。

2.1 本地IDNC圖中最優(yōu)編碼包選擇策略

在PC-D2D網(wǎng)絡(luò)中，發(fā)送終端Di根據(jù)本地狀態(tài)反饋矩陣構(gòu)建本地IDNC圖，用LGi(v,e)來(lái)表示，頂點(diǎn)用Vm,k(?Dm∈Ci,pk∈Wm∩Hi)表示。在圖中，頂點(diǎn)Vm,k與頂點(diǎn)Vn,l滿足以下其中之一條件就相連：

(1)l=k，即終端Dm與Dn同時(shí)缺失數(shù)據(jù)包pl；

(2)l∈Hn，k∈Hm，即終端Dm與Dn相互擁有對(duì)方丟失的數(shù)據(jù)包。

定義7終端數(shù)據(jù)包權(quán)重(Terminal Packet We-ight,TPW)：計(jì)算過程如下：

在頂點(diǎn)Vi,j對(duì)應(yīng)終端Di的LSFMi中，將對(duì)應(yīng)終端Di的一行刪除，記為剩余矩陣(Residual Matrix,RM)。在RM中將數(shù)據(jù)包pk對(duì)應(yīng)的列由1變?yōu)?-qi,j，qi,j為終端Di到其鄰居中終端Di(j≠i)的丟包率，矩陣記為增益矩陣(Gain Matrix，GM)。

(6)

表述為在終端Di恢復(fù)數(shù)據(jù)包pk對(duì)LSFMi的影響。則在LGi(v,e)上，每一個(gè)頂點(diǎn)的權(quán)重為

W(vj,k)=(1-qi,j)×TCj×TPWj,k。

(7)

最優(yōu)編碼包搜尋原則如下：

此時(shí)最優(yōu)編碼包為

(8)

2.2 PC-D2D網(wǎng)絡(luò)中協(xié)作節(jié)點(diǎn)搜尋策略

本節(jié)引入終端協(xié)作圖(記為SG(v,e))來(lái)求解PC-D2D網(wǎng)絡(luò)中的最優(yōu)協(xié)作發(fā)送集合。

在終端協(xié)作圖中：

(1)頂點(diǎn)對(duì)應(yīng)為PC-D2D網(wǎng)絡(luò)中的終端(在1.2節(jié)中，終端對(duì)應(yīng)頂點(diǎn))；

(2)獨(dú)立集合可以作為PC-D2D網(wǎng)絡(luò)中的發(fā)送終端集合；

(3)頂點(diǎn)的權(quán)重為

(9)

終端協(xié)作圖中頂點(diǎn)相連的條件如下：

(1)Dm≠Cn，Dm∈Cn,Dn∈Cm,即Dm,Dn，任意一個(gè)終端在另一個(gè)終端的通信覆蓋范圍之內(nèi)，使用實(shí)線相連；

(2)Dm≠Cn,?Dk≠Dm&Dn,Dk∈Cm,n,即存在一個(gè)終端，同時(shí)在Dm和Dn的通信范圍之內(nèi)，使用虛線相連。

本節(jié)提出以下兩個(gè)定義：

2.2.1備選協(xié)作終端

備選協(xié)作終端在終端協(xié)作圖上，滿足以下條件：

(1)備選協(xié)作終端與獨(dú)立集合中的終端虛線相連；

(2)備選協(xié)作終端與獨(dú)立集合中的終端，通信范圍交集內(nèi)的終端都屬于犧牲集合；

(3)備選協(xié)作終端的增益判斷(Gain Judgment,GJ)和權(quán)重值要大于0。

對(duì)于終端增益判斷的解釋：對(duì)于接收終端端Di緩存不可解碼編碼包，在未來(lái)重傳過程中，接收終端解碼緩存的不可解碼編碼包，獲取數(shù)據(jù)包的情況，提出增益判斷:

(10)

GJ>0的時(shí)候，才保證在一次重傳中，犧牲不可解碼終端擴(kuò)展出協(xié)作發(fā)送終端的增益大于緩存不可解編碼碼包的犧牲終端未來(lái)解碼的增益。

2.2.2 備選協(xié)作終端的權(quán)重

在一次數(shù)據(jù)重傳中，犧牲集合子集Bn(Bn=SNS∩NSn,其中NSn為Dn的接收集合)中的終端對(duì)備選協(xié)作終端Dn發(fā)送的最優(yōu)編碼包解碼后，有以下三種情況；

由于以上三種解碼情況的存在，備選協(xié)作終端Dn權(quán)重值計(jì)算方式分為以下三種：

|Bn| ；

(11)

(12)

(13)

2.2.3搜尋備選協(xié)作終端方法

首先,將與獨(dú)立集合中的終端虛線相連的終端作為矩陣的列元素，獨(dú)立集合的接收集合中立即可解碼的終端作為行元素建立矩陣，記為備選協(xié)作矩陣(Alternative Collaboration Matrix,ACM)，記列數(shù)為L(zhǎng)。

ACM矩陣描述如下：

?j∈SG(v,e)∧?Dk∈Ci,j,Di∈S)。

(14)

然后，將列元素求和，列元素和小于L的行刪除，剩余矩陣的列對(duì)應(yīng)的終端為擴(kuò)展的備選協(xié)作終端。

2.4 協(xié)作重傳步驟

Step1 基站建立SG(v,e)，執(zhí)行本地IDNC圖上最優(yōu)編碼包選擇策略，計(jì)算各終端(頂點(diǎn))最優(yōu)編碼包。

Step2 根據(jù)最優(yōu)編碼包，計(jì)算各終端權(quán)重值。

Step3 在SG(v,e)中找出權(quán)重之和最大的獨(dú)立集S。

Step4 判斷獨(dú)立集合中終端的最優(yōu)編碼包對(duì)其接收集合是否全為立即可解編碼包，如果不是，轉(zhuǎn)Step 5；如果是，接收集合對(duì)最優(yōu)編碼包全為立即可解編碼包，該獨(dú)立集合S為協(xié)作發(fā)送集合。

Step5 搜索備選協(xié)作終端，如果存在備選協(xié)作終端，轉(zhuǎn)Step 6；如果不存在備選協(xié)作終端，該獨(dú)立集合S為協(xié)作發(fā)送集合。

Step6 計(jì)算備選協(xié)作終端GJ和權(quán)重值。將GJ和權(quán)重值都大于0的備選協(xié)作終端相互比較，將權(quán)重值最大的備選協(xié)作終端加入獨(dú)立集合S。如果所有備選協(xié)作終端的GJ都小于0，獨(dú)立集合S作為協(xié)作發(fā)送集合。

Step7 接收終端集合向發(fā)送終端集合反饋接收情況，然后發(fā)送終端集合向基站發(fā)送反饋消息。重復(fù)Step 1～7，直到所有終端恢復(fù)所需數(shù)據(jù)包。

2.3 解碼時(shí)延分析

為了方便分析，假設(shè)降低解碼時(shí)延的編碼重傳方案[17](Delay Reduction in multi-hop device-to-device communication using Network Coding,DRNC)的協(xié)作發(fā)送集合為S,使用NSCR后的協(xié)作發(fā)送集合為S′,總解碼時(shí)延Dsum。

一次重傳，解碼時(shí)延減少量

(15)

由于S∈S′,即DRNC的所得的協(xié)作發(fā)送集合是NSCR策略所得協(xié)作發(fā)送集合的子集，所以ΔD≥0。

一次重傳的平均解碼時(shí)延

(16)

一次重傳流程如圖2所示。

圖2 流程圖

2.4 算法復(fù)雜度分析

3 仿真與分析

本文使用OPNET 14.5將NSCR策略與降低解碼時(shí)延的編碼重傳方案[17](Delay Reduction in Multihop Device to Device Communication Using Network Coding,DRNC)和降低完成時(shí)延的編碼重傳方案[12](Completion Time Reduction for Partially Connected D2D Enabled Network Using Binary Codes,CTRBC)進(jìn)行仿真分析對(duì)比。

仿真模型包括一個(gè)基站作為信源S，M個(gè)終端作為信宿。第一階段，基站向各個(gè)終端連續(xù)發(fā)送N個(gè)數(shù)據(jù)包，發(fā)送完畢后等待各個(gè)終端反饋的ACK幀，建立SFM，根據(jù)網(wǎng)絡(luò)連接情況建立LSFM。仿真將平均解碼時(shí)延和重傳次數(shù)作為仿真的性能指標(biāo)，分別在網(wǎng)絡(luò)連通度θ不同、終端數(shù)量N不同、發(fā)送數(shù)據(jù)包數(shù)量M不同的情況下，將NSCR與DRNC和CTRBC進(jìn)行性能對(duì)比。仿真參數(shù)設(shè)置如表2所示。

表2 仿真參數(shù)設(shè)置

圖3和圖4給出了平均解碼時(shí)延和重傳次數(shù)隨著網(wǎng)絡(luò)連接度變化的情況，選取參數(shù)M=40,N=30,qs,i=0.3,qi,j=0.2。仿真結(jié)果表明，在網(wǎng)絡(luò)連接度較低的PC-D2D網(wǎng)絡(luò)中，NSCR充分利用部分終端對(duì)最優(yōu)編碼包的不可解性和無(wú)效解碼性擴(kuò)展協(xié)作集合，在網(wǎng)絡(luò)連接度θ為0.3～0.6時(shí)可以有效降低平均解碼時(shí)延，并降低重傳次數(shù)。

圖3 平均解碼時(shí)延與網(wǎng)絡(luò)連接度

圖4 重傳次數(shù)與網(wǎng)絡(luò)連接度

圖5和圖6給出了平均解碼時(shí)延和重傳次數(shù)隨著終端數(shù)量變化的情況,選取仿真參數(shù)N=30,qs,i=0.3,qi,j=0.2，θ=0.3。仿真結(jié)果表明，三種方案平均解碼時(shí)延和重傳次數(shù)隨著終端數(shù)量增多而上升。在θ=0.3時(shí)，隨著終端數(shù)量的增加，NSCR可利用的不解碼和無(wú)效解碼的終端數(shù)量增多。NSCR可以在DRNC的協(xié)作集合的基礎(chǔ)上，擴(kuò)展出更多協(xié)作終端參與到協(xié)作傳輸?shù)倪^程中。由此，NSCR可以有效抑制平均解碼時(shí)延和重傳次數(shù)的上升趨勢(shì)。

圖5 平均解碼時(shí)延與終端數(shù)量

圖6 重傳次數(shù)與終端數(shù)量

圖7和圖8給出了三種方案平均解碼時(shí)延和重傳次數(shù)隨著源數(shù)據(jù)包的變化情況。在qs,i=0.3、θ=0.3、M=40、qi,j=0.2時(shí)，各個(gè)終端丟包數(shù)量隨著源數(shù)據(jù)包數(shù)量的增加而增多，導(dǎo)致平均解碼時(shí)延升高和重傳次數(shù)的增加。此時(shí)，NSCR策略與其他兩種方案相較，平均解碼時(shí)延和重傳次數(shù)的上升速度稍慢。

圖7 平均解碼時(shí)延與源數(shù)據(jù)包

圖8 重傳次數(shù)與源數(shù)據(jù)包

4 結(jié) 論

本文針對(duì)PC-D2D網(wǎng)絡(luò)提出了基于犧牲節(jié)點(diǎn)的D2D協(xié)作重傳策略。該策略在本地IDNC圖上綜合考慮各終端連通度、鏈路質(zhì)量和終端數(shù)據(jù)包權(quán)重等因素選取發(fā)送終端的最優(yōu)編碼包，并利用部分終端對(duì)發(fā)送終端的最優(yōu)編碼包的不可解碼/無(wú)效解碼的特性，擴(kuò)展了協(xié)作發(fā)送集合。仿真實(shí)驗(yàn)表明，在網(wǎng)絡(luò)連接度較低的PC-D2D網(wǎng)絡(luò)中，NSCR較其他方案能有效降低系統(tǒng)的平均解碼時(shí)延，一定程度上減少重傳次數(shù)。本文策略可以推廣到無(wú)線傳感器網(wǎng)絡(luò)和Ad Hoc網(wǎng)絡(luò)之中，以減少無(wú)線傳感器網(wǎng)絡(luò)和Ad Hoc網(wǎng)絡(luò)的數(shù)據(jù)重傳次數(shù)。