D2D網絡中基于犧牲節點的網絡編碼協作重傳策略 *

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

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

0 引 言

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

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

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

1 網絡模型及相關定義

1.1 網絡模型

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

圖1 蜂窩網絡下的D2D通信

該網絡場景下,通信過程分為兩個階段：

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

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

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

第二階段，在BS依次廣播數據包P后，Z個終端中滿足建立D2D鏈路的設備集合為M，其中各源數據包至少被M的一個終端正確接收。基站授權用戶頻段，建立D2D鏈路。終端設備通過D2D鏈路合作傳輸恢復丟失數據包。

本文中主要符號及含義如表1所示。

表1 全文主要符合及含義

1.2 相關定義

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

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

2 基于犧牲節點的D2D協作重傳策略

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

(5)

由公式(5)可知，總解碼時延與協作發送集合終端選取和接收終端的鏈路質量有關。由文獻[7]可知，最優編碼包的選取方式會影響整個系統的平均解碼時延，進而影響到重傳次數，所以降低重傳次數要從協作發送終端集合和最優編碼包的選取入手。

2.1 本地IDNC圖中最優編碼包選擇策略

在PC-D2D網絡中，發送終端Di根據本地狀態反饋矩陣構建本地IDNC圖，用LGi(v,e)來表示，頂點用Vm,k(?Dm∈Ci,pk∈Wm∩Hi)表示。在圖中，頂點Vm,k與頂點Vn,l滿足以下其中之一條件就相連：

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

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

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

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

(6)

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

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

(7)

最優編碼包搜尋原則如下：

此時最優編碼包為

(8)

2.2 PC-D2D網絡中協作節點搜尋策略

本節引入終端協作圖(記為SG(v,e))來求解PC-D2D網絡中的最優協作發送集合。

在終端協作圖中：

(1)頂點對應為PC-D2D網絡中的終端(在1.2節中，終端對應頂點)；

(2)獨立集合可以作為PC-D2D網絡中的發送終端集合；

(3)頂點的權重為

(9)

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

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

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

本節提出以下兩個定義：

2.2.1備選協作終端

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

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

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

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

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

(10)

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

2.2.2 備選協作終端的權重

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

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

|Bn| ；

(11)

(12)

(13)

2.2.3搜尋備選協作終端方法

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

ACM矩陣描述如下：

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

(14)

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

2.4 協作重傳步驟

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

Step2 根據最優編碼包，計算各終端權重值。

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

Step4 判斷獨立集合中終端的最優編碼包對其接收集合是否全為立即可解編碼包，如果不是，轉Step 5；如果是，接收集合對最優編碼包全為立即可解編碼包，該獨立集合S為協作發送集合。

Step5 搜索備選協作終端，如果存在備選協作終端，轉Step 6；如果不存在備選協作終端，該獨立集合S為協作發送集合。

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

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

2.3 解碼時延分析

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

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

(15)

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

一次重傳的平均解碼時延

(16)

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

圖2 流程圖

2.4 算法復雜度分析

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個終端作為信宿。第一階段，基站向各個終端連續發送N個數據包，發送完畢后等待各個終端反饋的ACK幀，建立SFM，根據網絡連接情況建立LSFM。仿真將平均解碼時延和重傳次數作為仿真的性能指標，分別在網絡連通度θ不同、終端數量N不同、發送數據包數量M不同的情況下，將NSCR與DRNC和CTRBC進行性能對比。仿真參數設置如表2所示。

表2 仿真參數設置

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

圖3 平均解碼時延與網絡連接度

圖4 重傳次數與網絡連接度

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

圖5 平均解碼時延與終端數量

圖6 重傳次數與終端數量

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

圖7 平均解碼時延與源數據包

圖8 重傳次數與源數據包

4 結 論

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