D2D網(wǎng)絡(luò)中基于犧牲節(jié)點的網(wǎng)絡(luò)編碼協(xié)作重傳策略 *

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

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

0 引 言

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

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

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

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

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

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

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

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

第一階段，基站廣播發(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個終端中滿足建立D2D鏈路的設(shè)備集合為M，其中各源數(shù)據(jù)包至少被M的一個終端正確接收?；臼跈?quán)用戶頻段，建立D2D鏈路。終端設(shè)備通過D2D鏈路合作傳輸恢復(fù)丟失數(shù)據(jù)包。

本文中主要符號及含義如表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互不在對方通信范圍內(nèi)，但是可以通過Dm中繼通信。

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

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

(1)

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

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

(2)

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

(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é)點的D2D協(xié)作重傳策略

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

(5)

由公式(5)可知，總解碼時延與協(xié)作發(fā)送集合終端選取和接收終端的鏈路質(zhì)量有關(guān)。由文獻[7]可知，最優(yōu)編碼包的選取方式會影響整個系統(tǒng)的平均解碼時延，進而影響到重傳次數(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)來表示，頂點用Vm,k(?Dm∈Ci,pk∈Wm∩Hi)表示。在圖中，頂點Vm,k與頂點Vn,l滿足以下其中之一條件就相連：

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

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

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

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

(6)

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

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

(7)

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

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

(8)

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

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

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

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

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

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

(9)

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

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

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

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

2.2.1備選協(xié)作終端

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

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

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

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

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

(10)

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

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

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

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

|Bn| ；

(11)

(12)

(13)

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

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

ACM矩陣描述如下：

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

(14)

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

2.4 協(xié)作重傳步驟

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

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

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

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

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

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

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

2.3 解碼時延分析

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

一次重傳，解碼時延減少量

(15)

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

一次重傳的平均解碼時延

(16)

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

圖2 流程圖

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

3 仿真與分析

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

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

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

圖3和圖4給出了平均解碼時延和重傳次數(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充分利用部分終端對最優(yōu)編碼包的不可解性和無效解碼性擴展協(xié)作集合，在網(wǎng)絡(luò)連接度θ為0.3～0.6時可以有效降低平均解碼時延，并降低重傳次數(shù)。

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

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

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

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

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

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

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

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

4 結(jié) 論

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