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网络的数据重传次数。