D2D网络中基于截止时间约束的网络编码重传方法*

王鹏飞，张冬梅，许 魁，沙 楠

(中国人民解放军陆军工程大学 通信工程学院，江苏 南京 210007)

0 引言

近年来，随着无线接入和移动互联网的普及，移动数据流量呈爆发性增长趋势[1]。流量的持续增长，使现有的蜂窝网络变得拥挤不堪，从而降低服务质量和影响用户体验。为此，终端直通技术(Device to Device，D2D)应运而生，并被确定为下一代移动通信系统中的关键技术。D2D技术[2-3]允许终端设备直接通信，可以提供更可靠的传输链路、更低的传输延迟以及更高的能量效率。

网络编码作为一种跨层技术，能够显著地提高无线网络吞吐量以及可靠性[4-6]。现有文献研究表明，结合D2D与网络编码技术有许多优势，如降低重传次数、减少译码时延、提高系统吞吐量等。文献[7]、[8]研究了D2D网络中基于立即可译网络编码(Instantly Decodable Network Coding,IDNC)的协作传输方法，以降低重传过程中的译码时延。其中，终端通过重传编码包来加快丢失数据包的恢复。文献[9]利用随机最短路径建模来研究重传次数最小化问题，提出了联合选择广播源与网络编码包的启发式重传方法。为提高D2D协作重传的性能，文献[10]研究了基于网络编码的最小延时调度问题，提出了低复杂度的集中式算法，并进一步给出了分布式解决方法。

然而，随着无线网络业务需求的深入与发展，诸如视频直播、在线游戏等实时应用被广泛使用。此类应用有鲜明的特征，即数据包具有严格的截止时间限制，超过截止时间后的数据包往往是无效的。因而，针对数据包具有截止时间约束的实时应用，设计高效的网络编码策略是进一步提高服务质量，满足用户多样化需求的关键。

本文结合IDNC策略，研究D2D网络中基于截止时间约束的网络编码重传(Deadline Constrained Network Coding Retransmission，DCCR)方法，以最大化用户能够及时收到的数据包总数。文章的主要贡献如下：首先，将问题建模为整数线性规划问题，并证明该问题是一个NP-hard问题；其次，构建了新的IDNC图模型，用于表示所有满足截止时间约束的编码组合，提出了基于最大权重团搜寻的重传调度方法；最后，仿真结果验证了提出方法的有效性。

1 系统模型与问题示例

1.1 系统模型

考虑如图1所示无线D2D网络。该模型包含一个基站(Broadcast Source，BS)以及M个终端设备R={r1,r2,…,rM}，所有设备都有兴趣从基站处获取N个原始数据包P={p1,p2,…,pN}。设备彼此之间非常接近，位于相同的传输范围内，可以通过WiFi或者蓝牙等D2D链路相互连接。

图1 D2D网络示意图

由于之前的广播传输，假设设备在初始时刻已经成功接收到部分数据包。其中，H(ri)表示设备ri拥有的数据包集合，W(ri)表示设备ri仍然需要的数据包集合，存在H(ri)∩W(ri)=φ，H(ri)∪W(ri)=P。对于数据包pj∈P，定义Tj表示该数据包的接收截止时间。超过截止时间Tj后，数据包pj对于所有设备都是无效的。

设备可通过D2D链路进行合作重传来恢复所需丢失数据包。每次传输过后，设备向基站反馈边信息(ACK/NACK)，用于更新数据包接收状态，假设反馈信息没有损耗。各D2D传输对(ri,rk)之间的丢包概率表示为εi,k，且εi,k=εk,i。为避免产生干扰，每个时隙仅允许单个设备进行广播传输，其余设备都处于侦听状态。

1.2 问题示例

如图1所示，基站向设备{r1,r2,r3}广播数据包{p1,p2,p3,p4}。广播阶段过后，设备拥有的数据包分别为：H(r1)={p1,p3}，H(r2)={p2,p3,p4}，H(r3)={p1,p2,p4}。若不考虑数据包的截止时间限制，给定三种不同的传输策略:

策略A:r3广播p1⊕p2，r2广播p3⊕p4；

策略B:r2广播p2⊕p3，r3广播p1⊕p4；

策略C：r2广播p3⊕p4，r3广播p1⊕p2。

以上三种传输策略都能够保证设备在两个时隙恢复所有丢包。然而，若考虑数据包具有截止时间限制，并且假设数据包{p1,p2,p3,p4}的截止时间为{1,1,2,2}。对于策略A，三个设备都能在截止时间限制内恢复所有丢包；对于策略B，在第二个时隙r2才能恢复丢包p1，超过了p1的截止时间；对于策略C，p1和p2都超过了截止时间。显然，策略A是最佳传输策略，因为所有数据包都能在截止时间之前成功接收。

因此，本文要解决问题的核心就在于，根据数据包接收状态信息、D2D链路丢包概率以及数据包截止时间，如何设计最佳的传输策略，使得设备能够在截止时间之前收到的数据包总数最大化。为便于描述，将上述问题简称为DCCR问题。

2 问题建模与分析

本节将给出DCCR问题的整数线性规划建模，并分析求解问题的复杂度。在建模之前，对于∀ri∈R,pj∈P，定义以下变量：

(1)

(2)

(3)

(4)

(5)

根据上述定义，若设备ri能够在第t次传输中恢复丢失数据包pj，需满足下列四个条件：设备ri不作为t时刻的发送设备；设备ri需要数据包pj；数据包pj参与t时刻的编码；设备ri拥有编码包中除pj之外的所有数据包。具体可描述如下：

(6)

综上所述，DCCR问题可建模如下：

(7)

(8)

(9)

(10)

如式(7)所示，DCCR问题的优化目标是最大化设备能够在截止时间之前成功接收的数据包总数。式(8)表示为避免产生干扰，每个时刻只允许单个设备作为广播源；式(9)表示发送设备需要拥有参与编码的数据包；式(10)表示数据包若能够在截止时间之前正确接收，则表示该数据包在之前的某一时刻已被成功解码。

引理：DCCR问题是一个NP-hard问题。

证明：考虑DCCR问题的一种特殊情况，存在某个设备拥有所有原始数据包，即∃ri∈R,H(ri)=P；对于∀pj∈P，数据包的截止时间都满足Tj=1。在给定的假设下，DCCR问题简化为：固定发送设备，如何最大化能够从单次传输中解码出丢失数据包的设备数量。文献[11]中的研究表明，该问题是一个NP-hard的索引编码问题。因此，DCCR问题同样也是一个NP-hard的问题，寻找最优解的复杂度是指数级的。

3 IDNC图的构建

对于IDNC策略而言，为寻找最佳编码包，一个有效的方法是构建IDNC图。文献[9]通过在每个设备处构建IDNC子图以寻找该设备可生成的最佳编码包，并选择能够带来最大编码增益的设备作为发送设备。然而，文献[9]中的模型并不能直接运用于DCCR问题，因为在构建图的过程中没有考虑数据包截止时间的限制。本节将给出新的IDNC图模型，在构建过程中同时考虑数据包接收状态以及截止时间的限制。

(1)pl∈Ht(ri)，设备ri拥有数据包pl；

(2)∃k≠i,pl∈Wt(rk)，至少存在一个除ri之外的设备仍需要数据包pl；

(3)Tl≥t，数据包pl还未超过截止时间Tl。

(1)l=n，设备rk与rm需要同一个数据包pl=pn；

(2)pl∈Ht(rm)且pn∈Ht(rk)，设备rk与rm分别拥有彼此需要的数据包。当正确接收编码包pl⊕pn时，rk可通过pn⊕(pl⊕pn)解码出丢失数据包pl。同理，rm可解码出丢失数据包pn。

(11)

基于以上分析，同样以图1为例，第1个传输时隙设备处的IDNC图可构造如图2所示。因此，每个设备可生成的最佳编码包可以转化为对应IDNC图中的最大权重团(Maximal Weight Clique)选择问题。

图2 设备处的IDNC图示例

4 提出方法

基于构造的IDNC图，为最大化设备可及时接收的数据包数量，本节针对DCCR问题提出了启发式的传输调度方法。

4.1 最大权重团搜寻算法

当设备数量与数据包个数较大时，IDNC图中的顶点数也会增多，拆分IDNC图可得到许多最大团，遍历所有最大团来寻找最大权重团的计算量非常高，不适用于能耗与计算能力受限的D2D设备。为此，提出了启发式的最大权重团搜寻算法，降低寻找最佳编码包的计算量与复杂度。

将式(11)给出的权重视为顶点的初始权重。此外，定义顶点vi,j与vk,l之间的连接邻接系数如下：

(12)

最终，定义顶点vi,j的混合权重为：

(13)

由式(13)可见，图中顶点的权重不仅与自身权重有关，还取决于其相邻顶点的权重之和。顶点的混合权重越大，表明其带来的传输增益越高，更应该参与到当前编码。最大权重团搜寻算法的具体步骤如下：

(1)构建IDNC图G(V,E)，初始化最大权重团Cmax为空，根据式(11)计算出每个顶点的初始权重。

(2)根据式(12)、(13)计算出每个顶点的混合权重。其次，选择混合权重最大的顶点vi,j，将其放入最大权重团Cmax中。

(4)输出算法最终得到的最大权重团，确定需要发送的最佳编码包。

4.2 重传调度方法

对于DCCR问题，每个传输时隙都需要确定发送设备以及广播的编码包，整个传输过程由多个这样的单次传输构成，直到所有设备都恢复丢失数据包。就单次传输而言，每个设备都可能被选为发送设备，因此需要尝试所有可能性并选择能够实现最大编码增益的设备作为当前时隙的发送设备。基于以上分析，给出了DCCR问题的重传调度方法，如下：

1 输入:H(ri)、W(ri)、Tj2 初始化t←0,H0(ri)=H(ri),W0(ri)=W(ri);3 当∪ri∈RWt(ri)≠ϕ或者t>max(Tj),执行循环:4 对于∀ri∈R,构建IDNC图Gti(Vti,Eti);5 找出图Gti(Vti,Eti)中的最大权重团Cti;6 计算Cti中顶点的权重和wti;7 选择发送设备rs=argmaxri∈R{wti};8 广播编码包Pc=j∈{vi,j∈Cts}pj;9 t←t+1;10 更新Ht+1(ri)、Wt+1(ri);11 输出:超过截止时间的数据包总数

5 仿真结果分析

本节以及时接收的数据包总数、截止时间超出率η为评价指标，对提出的方法进行仿真比较。截止时间超出率可由式(14)计算：

(14)

其中，Se表示超过截止时间的数据包总数，Sn表示初始时刻所有设备需要的数据包总数。

设备在初始广播阶段后丢失部分原始数据包，各终端的丢失数据包根据概率ρ=0.4从N个数据包中随机选择。重传阶段，各D2D传输对(ri,rk)之间的丢包概率设置为εi,k=[0.1,0.2]。将本文方法与以下三种方法作对比：不采用网络编码(No-Coding)的方法，每次重传最接近截止时间的数据包；传统的协作重传(Traditional Cooperation Retransmission,TCR)方法[9]，该方法不考虑数据包截止时间的约束，以最小化设备恢复丢包所需的重传次数为目标设计传输策略；随机选择发送设备(Random Device Selection,RDS)的方法，该方法在每次传输时随机选择发送设备，与本文采用相同的编码策略。

固定设备数量M=10，图3和图4给出了截止时间超出率随数据包个数的变化。其中，截止时间的取值范围分别为[1,15]、[1,30]。仿真结果表明，DCCR方法的截止时间超出率远远低于其他方法。由于在设计编码策略时未考虑截止时间的约束，相较于DCCR以及RDS方法，TCR方法的性能较差。此外，随着数据包个数的增加，截止时间超出率逐渐变大，因为在相同的时间内有更多的数据包需要接收。

图3 截止时间区间为[1,15]时的性能比较

图4 截止时间区间为[1,30]时的性能比较

固定数据包个数N=20，图5和图6给出了及时接收的数据包总数随设备数量的变化。其中，截止时间取值范围分别为[1,5]、[1,10]。同样地，相比于其他方法，DCCR方法能够使更多的数据包及时接收。此外，随着截止时间的取值范围增大，可以及时接收的数据包总数会进一步增多。

图5 截止时间区间为[1,5]时的性能比较

图6 截止时间区间为[1,10]时的性能比较

6 结论

针对数据包具有截止时间限制的实时应用，为进一步提高服务质量，本文设计了D2D网络中基于网络编码的重传调度方法。为表示所有满足截止时间约束的编码组合，本文构建了新的IDNC图模型，给出了基于最大权重团搜寻的重传调度方法。仿真结果表明，与其他方法相比，本文提出的方法能够有效地增加接收的数据包数量，降低超过截止时间约束率。