基于終端差異化與D2D網絡的IDNC協作重傳方案

摘要：為了滿足終端用戶的個性化需求并且降低D2D網絡的傳輸時延，提出了一種基于終端差異化的立即可解網絡編碼（IDNC）協作重傳方案。首先，針對PC-D2D網絡存在的解碼沖突以及傳輸沖突問題提出一種新的IDNC算法框架并且在此框架的基礎上搜索極大獨立集（MIS），綜合考慮數據包的接收情況、終端用戶需求以及鏈路丟包率情況設計權重，衡量權重選取一次重傳時延增量最小的并發協作重傳終端以及數據包組合生成編碼包；同時，考慮不需要數據包提供的未來解碼機會，優化終端不需要的數據包，進一步降低傳輸時延。仿真結果表明，所提方案在滿足終端個性化需求的同時能夠有效地降低解碼時延和完成時間。

關鍵詞：D2D； 立即可解網絡編碼； 協作重傳； 解碼沖突； 傳輸沖突； 終端差異化

中圖分類號：TN919文獻標志碼：A

文章編號：1001-3695（2022）08-035-2448-06

doi：10.19734/j.issn.1001-3695.2021.12.0690

IDNC cooperative retransmission scheme based on terminal differentiation and D2D network

Yao Yukun， Chen Xinyao， Yang Jie

（School of Communication amp; Information Engineering， Chongqing University of Posts amp; Telecommunications， Chongqing 400065， China）

Abstract：In order to meet the individual needs of end users and reduce the transmission delay of D2D networks， this paper proposed an instantly solvable network coding（IDNC） cooperative retransmission scheme based on terminal differentiation. First of all， this scheme proposed a new IDNC algorithm framework for the decoding conflict and transmission conflict in PC-D2D network， and searched for a maximal independent set（MIS） on the basis of this framework. It designed the weights by considering user requirements and link packet loss rate， and selected the weights to generate coded packets by combining the concurrent cooperative retransmission terminal with the smallest retransmission delay increment and data packets. At the same time， considering the future decoding opportunities provided by unnecessary data packets， it optimized the data packets that the terminal didn’t need to further reduce the transmission delay. The simulation results show that the proposed scheme can effectively reduce the decoding delay and completion time while meeting the personalized needs of the terminal.

Key words：D2D; IDNC coding; cooperative retransmission; decoding conflict; transmission conflict; terminal differentiation

0引言

隨著數據的爆炸式增長，用戶的流量需求呈現指數式增長，作為一種提高通信容量和減少回程流量的方法——D2D［1］通信被提出。通過D2D通信，發送設備可以直接與其他設備進行近距離的通信，而不需要基站（BS）。D2D通信由于顯著減少帶寬和回程鏈路的能量消耗的優勢被廣泛應用。

2000年，Ahlswede等人［2］提出了網絡編碼（network coding，NC），改變了原始的中間節點的存儲轉發模式，網絡編碼允許中間節點按照一定的規則對數據包進行編碼轉發，顯著地降低了系統的傳輸時延與次數。立即可解網絡編碼（instantly decoding network coding，IDNC）［3～9］作為異或（ORC）編碼的子類，一直被認為是一種很有前途的技術，尤其是在減少延遲以及增大吞吐量方面。IDNC作為一種瞬時解碼技術被廣泛應用于實時應用，使用XOR二進制操作對文件進行編碼和解碼的簡單性適用于電池受限的終端設備［10～13］。

長久以來，很多學者展開對IDNC應用于D2D網絡以減少數據包重傳次數，降低完成時延的研究。文獻［14］的heristic maximum clique IDNC（HMC-IDNC）算法以鄰接度為考慮因素，總將鄰接度最大的頂點加入選出最大團；文獻［15］的minimum relevancy clique IDNC（HMC-IDNC）算法同樣是以鄰接度為考慮因素，但是為了保證后續的編碼機會，將鄰接度最小的頂點加入選出最大團；文獻［16］以鏈路丟包率為考慮因素，將鏈路丟包率最低的頂點加入選出最大團；文獻［17］綜合考慮信道的質量、終端的能量、穩定性等因素設計了MWP-QE算法，以剩余能量為考慮因素，總將剩余能量最大的頂點加入選出最大團。

但是后續研究發現，終端的發射功率有限，不能做到每個終端之間直接通信，因此許多學者投入到部分連接D2D網絡（PC-D2D）的研究［6，14，15］。在PC-D2D的早期研究中，最小化解碼延遲或完成時間定義為所有用戶獲得他們想要的數據包之前的傳輸數量，前提是所有的用戶對同一組數據包感興趣，但是在現實生活中用戶可能對不同的數據包感興趣，這一興趣可能體現在不同用戶對于流量的需求上，并將不同的流量需求體現在數據包的需求不同上。數據以數據包的形式發送，每個數據包在一個固定的持續時間內發送滿足終端用戶的需求。針對這一發現，本文提出了基于終端差異化與D2D網絡的IDNC協作重傳方案（IDNC cooperative retransmission scheme based on terminal differentiation and D2D network，CRTD）。在重傳階段，考慮終端的需求、鏈路丟包率以及數據包的接收情況并且運用新的IDNC算法框架避免PC-D2D網絡中的傳輸沖突以及編碼沖突，搜索極大獨立集，生成單次重傳可行的并發協作重傳設備以及編碼包。同時，優化終端不需要的數據包，衡量頂點權重選取最優的傳輸以及編碼方案，減小重傳次數，降低系統的解碼時延以及完成時延。

1系統模型及相關定義

1.1系統模型

如圖1所示，PC-D2D網絡模型中包含一個基站V和N個終端。基站V將M個數據包組成的文件發送給N個終端，文件的集合為P={fi|1≤i≤M}，接收端用戶的集合為I={Ri|1≤i≤N}。其中每個終端j有著自己獨特的需求的數據包集fj={pj，j∈I}，且文件由數量為|mi|的數據包pi構成。基站到各終端的鏈路丟包率為qi，j（i∈V，j∈I）。

傳輸模型中，數據包傳輸分為初始階段以及重傳階段。在初始階段，基站廣播數據包給終端，由于第一階段考慮終端的需求數據包的不同，終端不會接收不需要的數據包從而造成終端無法解碼的情況，在這一階段不考慮終端的差異性，并且每個終端都可以監聽到不需要的數據包，終端i監聽到的數據包集為oi。

基站廣播數據包后，接收端可能有如下三種情況：

a）已經接收到的數據包集合qi，即接收端Ri已經接收到的數據包的集合。其中，接收端Ri接收到的需要的數據包集合為ui，接收端Ri接收到的不需要的數據包的集合為oi，顯然qi=ui∪oi。

b）缺失的數據包的集合i，即接收端Ri丟失的不需要的數據包的集合。

c）需求的數據包的集合i，即接收端Ri丟失的需要的數據包的集合。

假設pi∈P，Ri∈I‖pi∈qi，表示每個數據包pi至少被一個設備成功接收；pi∈P，Ri∈I‖pi∈i，表示如果存在所有終端都沒有收到的一個數據包，那么這個數據包需要從基站重新發送；Rj∈I，pi∈P amp;amp; pi∈uj，表示如果所有的用戶都需求此數據包并且都接收到了此數據包，那么將此數據包從數據包集中刪除。

在第二階段，基站對D2D用戶進行頻譜授權，D2D用戶之間進行數據包的互傳從而恢復需求的數據包。假設用戶之間距離很近，在相同的傳輸范圍內，可以通過Wi-Fi、藍牙等D2D鏈路相互連接。定義終端Ri到Rj的鏈路丟包率為Pi，j。

1.2相關定義

定義1部分連接D2D網絡（partially connected D2D network，PC-D2D）。Rj∈Ci，則設備Rj可以直接連接到設備Ri（單跳）；若RnCi amp;amp; RmCj amp;amp; Rn≠Rm，Rk∈Ci，j，則設備Rn可以通過中間設備Rk與終端設備Rm進行通信（多跳）。

定義2狀態反饋矩陣（state feedback matrix，SFM）。接收端將數據包接收情況通過ACK＼NACK反饋給基站，形成的矩陣稱為狀態反饋矩陣，如式（1）所示。

SFM=fk，l=0l∈uk1l∈k，k∈N，l∈M－1l∈k2l∈ok （1）

定義3連接矩陣（system connection matrix，SCM）。將所有設備之間的數據包的接收概率存儲在一個矩陣，此矩陣稱為連接矩陣，定義為

SCM=yi，k=1－pi，kk∈Ci0kCi" （2）

定義4覆蓋區域（Ci）。Ci={Rm|yi，m≠0}， 表示為設備可以通過擦除信道與其他設備集相連。

定義5解碼時延（decoding delay，DD）。當接收端接收到IDNC編碼包且Ri∈I amp;amp; i≠時，終端Ri的解碼存在以下幾種情況：a）不可解編碼包，|p*i∩i|≠1，發送端發送的編碼包不包含終端需求的數據包；b）立即可解編碼包，|p*i∩i|=1，發送端發送的編碼包只包含終端需求的一個數據包；c）非立即可解編碼包，|p*i∩i|≥2，發送端發送的編碼包包含終端需求的多個數據包。當不可解編碼包、非立即可解編碼包被終端接收或者終端未收到編碼包時，解碼時延會增加一個單位，表示為

dtm=0m≠ amp;amp; |m∩p*i|=11其他 （3）

定義6單獨完成時延（individual completion delay，ICD）。在任何時間m內，非空需求集的終端Rm解碼所有需求數據包的總時間，定義為

ICD=|i|+∑tm=1dmi（4）

定義7完成時延（completion delay，CD）。所有非空需求的終端獲得所有需求數據包的傳輸總時間，定義為

CD=∑ni=1IiCD（5）

本文使用的符號及含義如表1所示。

2基于終端差異化的D2D協作重傳方案

在PC-D2D網絡中，由于終端的覆蓋范圍有限，并不是所有的終端都可以直接進行互傳使得彼此獲取需求的數據包。當兩個不同的傳輸設備同時傳輸數據包或者編碼包給兩者覆蓋范圍內的同一個接收設備時會產生傳輸沖突的問題，同樣的終端接收到編碼包面臨著解碼沖突問題，在此用一個示例來說明。

例1如圖2所示的場景，系統由兩個發送設備與五個終端組成，并且發送設備擁有著不同的數據集q1={p1，p2，p3}、q2={p4，p5}。當發送設備發送數據包至接收設備后，由于信道的不完美數據包在傳輸過程中產生了丟失，終端沒有獲取全部需求的數據包，所以需要發送設備對終端進行重傳。接收端首先將數據包的接收情況反饋給發送端，發送端形成各自的狀態反饋矩陣L（s1）和L（s2），矩陣的具體表示如下：

L（s1）=01010－110－1－1010－1－1L（s2）=－1－10－10－1－1－11－1

此時，發送端根據矩陣的反饋情況選取傳輸編碼包的方案：由于終端c2獲取了數據包p2與p4，此終端可以對這兩種類型的編碼包進行異或操作解碼出需求的數據包p1。同樣地，終端c3可以對這兩種編碼包進行異或操作解碼出需求的數據包p1。但是當兩種類型的編碼包p1⊕p2與p1⊕p4同頻同時隙傳輸到終端c2、c3時，終端只能對其中的一種編碼包進行解碼，使得終端獲得需求的數據包，此時產生了傳輸沖突，如圖3所示。

本節針對上述這一問題提出了一種新型的IDNC框架，提出了以下兩個定義：

定義8解碼沖突（decoding conflict，DC）。

Ri，Rj∈S，Rm∈Ti（p*i），|p*i∩qi|=1 amp;amp; |p*i∩qj|=1，|p*i∩um|≠1，表示發送端發送的編碼包無法使得終端獲得需求的數據包。

定義9傳輸沖突（transmission conflict，TC）。Ri，Rj∈S，Rk∈Ti（p*i） amp;amp; Rk∈Tj（p*j），Rk∈Ci，j，表示當發送設備Ri與Rj同時向接收設備Rk傳輸數據包或者編碼包時，它們的傳輸將發生碰撞，此類碰撞稱為傳輸沖突。

2.1IDNC圖框架設計

IDNC圖模型用來表示設備間的傳輸關系以及終端缺少數據包間編碼關系的圖模型， IDNC圖框架的設計主要分為局部發送矩陣的構建和頂點連接條件的構建兩個部分。

2.1.1局部發送矩陣的構建

根據每個時隙t的狀態反饋矩陣生成局部發送矩陣LSM，其形成規則滿足如下定義：

定義10局部發送矩陣（local state matrix，LSM）。針對每個設備為發送設備Ri（i∈I）生成的矩陣，矩陣的行列分別代表發送設備的覆蓋設備集合以及發送設備擁有的數據包集合，表示為

LSMi=0 Rk∈Ci amp;amp; pl∈qk1Rk∈Ci amp;amp; pl∈kxRk∈Ci amp;amp; pl∈k" （6）

根據局部發送矩陣生成IDNC圖的相關頂點表示為vi，l，k，其中i表示特定的發送設備i∈I，l表示發送端發送的數據包pl∈qi，k表示發送端發送數據包的目標終端Rk∈I，且頂點中的vl，k對應圖中的局部發送矩陣1的位置。

2.1.2頂點相連條件

本節考慮同頻同時隙前提下的接收端的解碼沖突以及傳輸沖突，設計了以下的相連條件。

條件1pl≠pn amp;amp; Rk=Rm，表示同一個設備Rk丟失了不同的數據包pl、pn，終端無法在此次傳輸中獲取需求的數據包，產生了解碼沖突。

條件2pl≠pn amp;amp; Rk≠Rm，plqm‖pnqk， 表示不同的設備Rk、Rm丟失了兩個不同的數據包，但是這兩個設備至少有一個不擁有另一個設備需求的數據包，從而產生了解碼沖突。

條件3Ri≠Rr amp;amp; Rk=Rm∈{Ci∩Cr}，表示不同的傳輸設備Ri、Rr同時傳輸數據包到終端設備Rk，且接收設備Rk在發送設備的共同覆蓋區域內。

條件 4Ri≠Rr amp; Rk≠Rm，Rk∈{Ci∩Cr}‖Rm∈{Ci∩Cr}，表示不同的傳輸設備Ri、Rr同時傳輸數據包到不同的接收設備Rk、Rm，但是終端Rk與Rm至少有一個在傳輸設備的共同覆蓋區域內。

條件5Ri≠Rr，Ri=Rm‖Rr=Rk，表示兩個不同的傳輸設備中至少有一個是另一個傳輸設備的目標設備。

2.2基于終端需求的一層IDNC圖

2.2.1一層IDNC圖的總體概述

由于終端之間的差異化，用戶的需求同樣呈現著差異，這一差異體現在數據包的不同需求上，本節針對終端設備需求的數據包進行重傳，設計了基于新型IDNC圖框架與用戶需求的一層IDNC圖。

定義11一層IDNC圖（a layer of IDNC，ALIDNC），用來表示設備間的傳輸關系以及設備需求的數據包間編碼關系的圖模型。當發送設備獲取的不需要的數據包滿足接收端的LSM的頂點產生時，用x表示。

根據定義2基站形成SFM以及SYM，根據定義10生成以每個設備為發送設備的LSM。由于要重傳的數據包滿足終端需求，所以不進行終端設備獲取的非需求的數據包能夠使得終端獲益的步驟，如例2所示。

例2假設終端反饋給基站的狀態反饋矩陣以及連接矩陣分別為S=102－101001012、Y=101011101 ，以每個設備為發送終端生成的局部發送矩陣為

p2p3 p1p3p4p2p4

s1=u1u30001， s2=u2u3000110， s3=u1u30x00

明顯s3中產生了發送設備u3獲取的不需要的數據包滿足接收端的情況，因此此種情況舍棄，不在此討論。

此時，產生的一層IDNC圖如圖4所示。

2.2.2一層IDNC圖頂點權重設計

考慮傳輸的編碼包在終端的解碼性，此處引入終端協作圖的頂點權重表達式［16］：

X（D）={∑Di∈S|Ti（P*i）|－

∑Di∈S{∑Dj∈Ti（p*i）^|p*i∩wj|=11×qi，j+∑Dj∈Ti（p*i）^|p*i∩wj|≠11}} （7）

考慮本文終端差異化的需求并受到式（7）的啟發，將式（7）改為

X（Ri）={∑Ri∈S|Ti（P*i）|－

∑Ri∈S{∑Rj∈Ti（p*i）^|p*i∩uj|=11×qi，j+∑Rj∈Ti（p*i）^|p*i∩uj|≠11}}（8）

式（8）綜合考慮了發送端發送編碼包的目標終端的數量，接收端無法從接收到的編碼包獲得需求的數據包以及在傳送過程中出現丟失并且終端可以從丟失的編碼包獲益的情況。

2.2.3協作重傳發送設備以及編碼包策略選擇

根據上述的相連條件將由局部發送矩陣產生的頂點相連，并且衡量權重選出的最大獨立集即為不產生傳輸沖突以及編碼沖突的最佳重傳方案，表示為

arg max{X（Ri）={∑Ri∈S|Ti（P*i）|－∑Ri∈S{∑Rj∈Ti（p*i）^|p*i∩uj|=11×qi，j+∑Rj∈Ti（p*i）^|p*i∩uj|≠11}}}（9）

此時選取的MIS可能存在以下幾種情況：a）當選中的MIS為{vi，l，k}，重傳方案為發送端Ri傳輸數據包pl至接收端Rk；b）當選中的MIS為{vi，l，k，vi，m，n，vj，x，q}，重傳方案為發送端Ri傳輸數據包pl⊕pm至接收端Rk、Rn，發送端Rj傳輸數據包px至接收端Rq，此時的傳輸為同時進行的傳輸；c）當選中的MIS為{vi，l，k，vt，m，n，vj，x，q}，重傳方案為發送端Ri傳輸數據包pl至接收端Rk，發送端Rt傳輸數據包pm至接收端Rn，發送端Rj傳輸數據包px至接收端Rq，此時的傳輸同樣為同時進行的傳輸。

2.3基于未來解碼機會的二層IDNC圖

本節針對終端設備不需要的數據包進行優化，設計了基于新型IDNC圖框架與用戶不需要的數據包的二層IDNC圖。

定義12二層IDNC圖（second IDNC， SEIDNC），用來表示設備間的傳輸關系以及設備不需要的數據包間編碼關系的圖模型，當發送設備獲取的需求的數據包滿足接收端的LSM的頂點產生時，用x表示。

定義13綜合IDNC圖（comprehensive IDNC，CIDNC），用來表示設備間的傳輸關系、設備需求的數據包間編碼關系以及設備不需要數據包提供未來解碼機會的圖模型，此模型既滿足終端的需求又優化了終端不需要的數據包。

2.3.1不需要數據包的解碼效益

在上節構建的ALIDNC中，只考慮到了接收端的解碼沖突、發送端的傳輸沖突以及接收端可以獲益的需求數據包的情況。本節探討不需要數據包提供的未來的解碼機會，充分利用數據包資源，優化不需要的數據包，從而更好地滿足終端的需求。

不需要的數據包pj與終端用戶Ri的關系有如下兩種情況：

a）pii amp;amp; i∈Ti（P*i）時，表示所有的終端都不需要數據包pj。

b）當數據包pj至少被一個終端Rk所需要，并且此終端至少擁有終端Ri的需求集合中的一個數據包。此種情況表示為

σi，j={k，h∈I|j∈k amp;amp; qk∩i≠

（Rj∈Ci）‖（Rh∈Ci，k amp;amp; Rk≠Rh amp;amp; RiCk amp;amp; Rk∈Ci）}（10）

當滿足情況a）時，不需要的數據包pj無法為終端用戶提供需求的數據包的未來解碼機會，此類數據包稱為無用數據包；當滿足情況b）時，不需要的數據包pj可以為終端用戶提供未來的解碼機會。

2.3.2二層IDNC圖頂點權重設計

在二層IDNC圖的權重衡量引入多播場景下不需要數據包為終端提供未來解碼機會的權重［17］：

si，j=（1－pi）αij（1－kijΠκ∈kij（1－pij）） （11）

考慮本文終端差異化的需求以及部分連接D2D場景，將式（11）改為

∑Rn∈S^j∈i ∑i∈Cn^Ri∈Tn（p*n）（1－pn，i）αij（1－kijΠκ∈kij（1－pn，k）） （12）

其中：kij、αij表示二進制變量，當滿足上述情況b）即滿足仍然存在需要數據包pj的終端Rk至少在終端Ri的想要集合中持有一個包時，二進制變量置為1，其他情況置為0。

因此，選取最佳的傳輸以及編碼方案為在二層IDNC圖中選取MIS，如式（13）所示。

arg max{∑Rn∈S^j∈i ∑i∈Cn^Ri∈Tn（p*n）（1－pn，i）αij（1－kijΠκ∈kij（1－pn，k））}（13）

2.3.3重傳策略的選擇

在考慮不產生傳輸沖突以及編碼沖突的最佳重傳方案時，會產生如下兩種情況：

方案1考慮選取ALIDNC構建的MIS對應的數據包組合、發送設備以及接收設備，只滿足終端用戶需求并不對終端用戶缺失的數據包進行優化，此時的衡量權重為

X（Ri）={∑Ri∈S|Ti（P*i）|－∑Ri∈S{∑Rj∈Ti（p*i）^|p*i∩uj|=11×qi，j+∑Rj∈Ti（p*i）^|p*i∩uj|≠11}}（14）

方案2考慮選取ALIDNC以及CIDNC所構建的MIS對應的數據包組合、發送設備以及接收設備，滿足終端用戶的需求并且對終端用戶不需要的數據包進行優化，此時的衡量權重為

X（Ri）+si，j={∑Ri∈S|Ti（P*i）|-

∑Ri∈S{∑Rj∈Ti（p*i）^|p*i∩j|=11×qi，j+∑Rj∈Ti（p*i）^|p*i∩j|≠11}}+

∑Rn∈S^j∈i ∑i∈Cn^Ri∈Tn（p*n）（1－pn，i）αij（1－kijΠκ∈kij（1－pn，k））（15）

將方案1、2的權重進行對比，選擇最大獨立集對應的傳輸方案，有以下幾種情況：a）若X（Ri）+Si，jgt;X（Ri），選擇方案2的最大獨立集對應的傳輸與編碼方案作為重傳方案；b）若X（Ri）+Si，j≤X（Ri），選擇方案1的最大獨立集對應的傳輸與編碼方案作為重傳方案。

例3繼例2，考慮不需要數據包提供的未來解碼機會，構建的綜合IDNC圖如圖5所示，重傳策略是在圖4的一層IDNC圖中選取最大權重的獨立集以及在圖5的綜合IDNC圖中選取最大權重的獨立集，綜合考慮選取最佳的重傳方案。

2.4協作重傳步驟

a）接收端將接收情況以及連接情況反饋給基站，基站建立SFM以及SYM。

b）構建針對每個用戶為發送端的局部發送矩陣，并根據局部發送矩陣以及用戶需求構建一層G（V，E），圖中的頂點對應的方案滿足終端用戶需求的數據包以及不產生傳輸沖突和解碼沖突。

c）在一層G（V，E）中選擇權重值最大的獨立集。

d）判斷接收終端的需求集是否為空，如果不是，此接收端不滿足條件，不參與G（V，E）的構建。判斷是否存在接收終端不需要的數據包為其提供未來的解碼機會，如果不存在，一層G（V，E）中的權重最大的獨立集為不產生傳輸沖突和解碼沖突的最佳重傳方案，如果存在轉向步驟e）。

e）構建二層G（V，E），并將二層G（V，E）與一層G（V，E）結合構建綜合G（V，E），計算綜合G（V，E）的權重，選出權重值最大的獨立集。

f）將選出的一層G（V，E）的獨立集最大權重與綜合G（V，E）的獨立集的最大權重進行比較，選取兩者中權重值最大的獨立集對應的方案作為不產生傳輸沖突和解碼沖突的最佳重傳方案。

g）基站根據上述IDNC算法選取步驟f）的一組發送端及其數據包組合，并將發送策略以及編碼策略通知各個發送端。

h）發送端傳輸編碼包，接收端接收到編碼包后解碼獲取需求的數據包并將接收狀態反饋給基站，基站更新狀態反饋矩陣，重復步驟a）～h），直到所有的終端得到需求的數據包。

一次協作重傳的流程如圖6所示。

2.5算法復雜度分析

在CRTD策略中，基站生成終端Ri的局部發送矩陣的計算復雜度為O（|qi‖Ci|），因此生成所有終端的局部發送矩陣的計算復雜度為O（∑Ii=1|qi‖Ci|）；構建終端Ri需求數據包相關頂點的計算復雜度為O（（∑Rj∈Ci|i|）2），構建所有終端需求的數據包相關頂點的計算復雜度為O（∑Ni=1（∑Rj∈Ci|i|2）），構建所有終端缺失的數據包相關頂點的計算復雜度為O（∑Ni=1（∑Rj∈Ci|i|2）），構建頂點數為|N|的G（V，E）的計算復雜度為O（|N|）2，在G（V，E）搜索極大獨立集合的計算復雜度為O（|N|）3，因此CRTD整體的計算復雜度為O（∑Ii=1|qi‖Ci|）+O（∑Ni=1（∑Rj∈Ci|i|2））+O（∑Ni=1（∑Rj∈Ci|i|2））+O（|N|）3。由于Ngt;gt;∑Rj∈Cj|i|2 且Ngt;gt;∑Rj∈Cj|i|2，計算復雜度由最高次的部分決定，所以CRTD的計算復雜度為O（|N|）3。

3仿真分析

本文使用OPNET Modeler 14.5進行仿真，將本文所提出的CRTD算法與降低完成時延的編碼重傳方案（completion time reduction for partially connected D2D enabled network using binary codes，CTRBC）［15］和在霧無線電接入網絡中使用即時可解網絡編碼的二進制數據傳輸 （data dissemination using instantly decodable binary codes in fog-ratio access networks，DDAC）［16］進行仿真對比，突出CRTD算法在滿足用戶需求的同時降低完成時延、解碼時延以及提高編碼增益的優勢。

3.1仿真設置

仿真中考慮一個PC-D2D網絡，其中設備隨機分布在一個邊長為500 m的六邊形單元內，D2D設備之間存在Wi-Fi鏈路或者藍牙鏈路可以直接相連。在仿真模型中，包含著一個基站V與N個終端。在基站廣播的第一階段后，每個用戶接收到了一些數據包，并且丟失了一些自己想要的數據包，此種概率是由擦除信道的丟包率的不確定造成的。由于短程的D2D鏈路比基站通信可靠，所以在重傳階段考慮設備間的協作重傳。假設設備到設備之間的擦除概率為基站到設備的擦除概率的一半，定義設備的非空需求的相鄰設備數量與設備總數的比值為G，設置Pi=0.3，Pi，j=0.15。

3.2仿真結果分析

如圖7、8所示，考慮參數N=30，M=20，pi=0.3，pi，j=0.15時平均解碼時延和重傳次數隨著網絡連通度的變化情況。仿真結果表明，在網絡連通度較低的PC-D2D網絡中，CRTD算法明顯降低了開銷，而CTRBC和DDAC算法在降低平均完成時間這一方面的效果較低。這是由于CTRBC算法只考慮了發送設備之間的協作而沒有考慮設備之間可能產生沖突的問題；DDAC算法雖然考慮了多設備之間傳輸可能存在碰撞但是沒有考慮更現實的用戶差異化需求問題。本文算法在DDAC的基礎上進行改進，更進一步的設計是基于沖突的IDNC框架并且以更現實的用戶需求差異化為著手點進行研究，CRTD方案考慮終端的解碼情況以及不需要數據包的優化進而選取最優的方案，尤其在網絡連通度G=0.3～0.6時，可以明顯地降低平均解碼時延、降低重傳次數、提高傳輸效率。

如圖9、10所示，參數連通度G=0.4，給出了數據包數量p=15時隨著終端設備數量的變化平均完成時間的變化情況以及終端設備數R=15時隨著數據包數量的變化平均完成時間的變化情況。仿真結果表明，在G=0.4的前提下，隨著數據包數量以及終端設備數的增加，平均完成時間逐漸增大。由于CTRBC和DDAC算法只考慮到需要數據包的優化，忽略了不需要數據包的優化，本文提出的CRTD算法考慮了上述不足，可以有效提高傳輸效率，優化不需要數據包，為未來傳輸中所需要的文件提供了更好的解碼機會，并且在降低完成時間上有著明顯的優勢。

如圖11、12所示，同樣考慮參數連通度G=0.4，給出了數據包數量為p=15時隨著終端設備數量的變化平均解碼時延的變化情況以及終端設備數R=15時隨著數據包數量的變化平均解碼時延的變化情況。仿真結果表明，平均解碼時延與上述的平均完成時間的趨勢基本相同，隨著數據包數量的增加以及終端數量的增加，平均解碼時延逐漸增大。明顯地，本文算法與對比的其他兩種算法相比，平均時延增長速率降低，說明CRTD算法在降低平均解碼時延有著明顯的優勢。

4結束語

本文針對PC-D2D網絡提出了基于終端差異化的IDNC協作重傳方案，根據終端的傳輸沖突以及解碼沖突提出了新型的IDNC框架，并且基于此框架構建一層IDNC圖以及二層IDNC圖，滿足終端需求并且優化終端不需要的數據包。綜合考慮傳輸方案，選擇最佳的傳輸方案滿足終端用戶的個性化需求。仿真結果表明，本文方案綜合考慮了各種因素，有效降低了完成時間、解碼時延以及重傳次數，為數據包提供未來解碼機會，為降低PC-D2D時延以及滿足終端用戶個性化需求提供了解決方案。下一步將不再以終端需求的差異化作為主要因素，而是針對終端的處理能力、剩余能量、帶寬等差異化因素研究來優化網絡的性能。

參考文獻：

［1］Gao Chuhan， Li Yong， Zhao Yulei， et al. A two-level game theory approach for joint relay selection and resource allocation in network coding assisted D2D communications ［J］. IEEE Trans on Mobile Computing， 2017， 16（10）： 2697-2711.

［2］Ahlswede R， Cai Ning， Li Y R， et al. Network information flow ［J］. IEEE Trans on Information Theory， 2000， 46（4）： 1204-1216.

［3］Denis J， Seferoglu H. Optimal network coding policy for joint cellular and intermittently connected D2D networking ［C］// Proc of IEEE Global Communications Conference. Piscataway， NJ： IEEE Press， 2020： 1-6.

［4］Al-Abiad M S， Hossain M J. A low-complexity multicast scheduling for D2D-aided F-RANs using network coding ［J］. IEEE Wireless Communications Letters， 2021， 10（11）： 2484-2488.

［5］Ahmed D，Sameh S，Tareq Y，et al. Decoding delay controlled completion time reduction in instantly decodable network coding ［J］. IEEE Trans on Vehicular Technology， 2017， 66（3）： 80-96．

［6］Doulk A，Sorour S. Data dissemination using instantly decodable binary codes in fog-radio access networks ［C］// Proc of the 13th International Wireless Communications and Mobile Computing Conference. Piscataway， NJ： IEEE Press， 2017： 604-609．

［7］Keshtkarjahromi Y，Seferoglu H，Ansari R，et al. Device-to-device networking meets cellular via network coding ［J］. IEEE/ACM Trans on Networking，2018， 26（1）： 370-383．

［8］ 牛騰， 張冬梅， 許魁， 等．基于 D2D 的無線多媒體網絡編碼廣播重傳策略 ［J］. 中國科學： 信息科學，2018，48（2）：205-220．（Niu Teng， Zhang Dongmei， Xu Kui， et al. Video distortion reduction with instantly decodable network coding and device-to-device communications ［J］. Science in China： Information Science， 2018， 48（2）： 205-220.

［9］王鵬飛， 張冬梅， 許魁， 等. 聯合蜂窩與 D2D 鏈路的網絡編碼廣播重傳方案 ［J］. 信號處理， 2018，34（6）： 652-660．（Wang Pengfei， Zhang Dongmei， Xu Kui， et al. Network coding retransmission method for cellular and D2D communication based wireless broadcas-ting ［J］. Journal of Signal Processing， 2018， 34（6）： 652-660.

［10］Mei Zhonghui， Zhou Xiaoyan. Maximum decoding clique based maximum weight vertex search algorithm for buffered instantly decodable network codes ［J］. IEEE Communications Letters， 2022， 26（2）： 229-233.

［11］Douik A， Sorour S， Alouini M S， et al. Completion time reduction in instantly decodable network coding through decoding delay control［C］// Proc of IEEE Global Communications Conference. Pisca-taway， NJ： IEEE Press， 2014： 5008-5013.

［12］Al-Abiad M S， Douik A， Hossain M J， et al. Coalition formation game for cooperative content delivery in network coding assisted D2D communications ［J］. IEEE Access， 2020， 8：158152-158168.

［13］Arefi A， Khabbazian M. Packet loss recovery in broadcast for real-time applications in dense wireless networks ［J］. IEEE Open Journal of the Computer Society， 2021， 2： 3-13.

［14］王練， 王萌， 任治豪， 等. D2D網絡中基于立即可解網絡編碼的時延最小化重傳方案 ［J］. 電子與信息學報， 2018， 40（7）： 1691-1698. （Wang Lian， Wang Meng， Ren Zhihao， et al. Delay minimization retransmission scheme based on instantly decodable network coding for D2D communications ［J］. Journal of Electronics amp; Information Technology， 2018， 40（7）： 1691-1698.

［15］Douik A， Tareq Y， Naffouri A. Delay reduction in multi-hop device-to-device communication using network coding ［J］. IEEE Trans on Wireless Communications， 2018， 10（17）： 60-74.

［16］Douik A， Sorour S. Data dissemination using instantly decodable binary codes in fog-radio access networks ［J］. IEEE Trans on Industrial Informatics， 2018， 66（5）： 2052-2064.

［17］Douik A， Al-Abiad M S， Hossain M J， et al. An improved weight design for unwanted packets in multicast instantly decodable network coding ［J］. IEEE Communication letters， 2019， 23（11）： 2122-2125.

收稿日期：2021-12-27；修回日期：2022-03-03基金項目：國家自然科學基金資助項目（61971080）

作者簡介：姚玉坤（1964-），女，教授，碩導，主要研究方向為無線網絡編碼（2605409066@qq.com）；陳鑫垚（2000-），女，碩士研究生，主要研究方向為無線網絡編碼；羊杰（1997-），男，碩士，主要研究方向為無線網絡路由協議.