联合蜂窝与D2D链路的网络编码广播重传方案

王鹏飞 张冬梅 许 魁 徐健卉

(解放军陆军工程大学通信工程学院, 江苏南京 210007)

1 引言

伴随着多媒体业务的兴起以及智能终端设备的普及,移动数据流量将迎来爆发性增长[1]。海量的设备接入使得现有的蜂窝网络变得越来越拥挤,从而恶化服务质量(Quality of Service,QoS)和降低用户体验(Quality of Experience,QoE)。与此同时,随着终端设备在计算、存储与连接方面的能力不断提高,D2D(Device-to-Device)技术[2-3]有望满足下一代无线通信网络中不断增长的吞吐量需求。D2D技术允许终端设备配备双接口:一个接口使用远程无线通信技术(如WLAN、LTE等)与基站连接;另一个接口使用短距离无线通信技术(如WiFi、蓝牙等)与其他设备直接通信。鉴于蜂窝和D2D链路可以使用不同频段同时运行,这样的系统能够极大地减轻基站负载,增加网络的吞吐量和能量效率。

受益于无线通信的广播性质,通过对不同的源数据包进行编码合并,网络编码技术[4-5]可以有效地提高系统吞吐量和减少传输延迟。由于上述优势,无线广播网络中基于网络编码的数据传输已成为近年来的热门话题。目前主要的网络编码策略有如下两类:随机线性网络编码(Random Linear Network Coding,RLNC)[6- 8]与立即可译网络编码(Instantly Decodable Network Coding,IDNC)[9-11]。RLNC策略在提升吞吐量性能方面有着显著优势,但是其缺点也很明显:对于要求低译码时延的应用来说,RLNC难以满足要求,因为它不支持数据包的逐个解码。此外,译码过程(矩阵求逆)带来的的高复杂度也不可避免。相比之下,尽管在吞吐量方面的提升不如RLNC,IDNC策略的优势在于编解码操作简单,支持数据包逐个解码,能够极大地降低译码时延。

网络编码最初应用于基站集中式的广播/多播网络[12-14],现有文献表明,结合D2D技术可以进一步的提高系统性能[15-19]。文献[15-16]分别针对基于D2D的无线广播场景提出了随机性和确定性算法,以最小化传输次数。文献[17]结合IDNC 策略与D2D技术,旨在提高数据合作交换系统中的传输效率,降低译码时延。文献[18]考虑不同数据对于视频质量的贡献来设计编码策略,提出了一种联合发送设备与数据包的选择算法,使每个传输时隙后的整体视频质量达到最大。文献[19]研究了基于网络编码的实时视频序列广播问题,考虑数据传输具有截止时间的限制。然而,上述研究都是基于设备使用单个接口的场景,即在传输阶段每次只能收到一个数据包(通过蜂窝链路或者D2D链路),针对设备配备双接口,在数据包重传阶段联合使用蜂窝与D2D链路的研究很少。

综上所述,本文考虑设备配备有双接口的网络编码广播(Network coding for dual interfaces,NCDI)场景,重传阶段可以同时利用蜂窝与D2D链路恢复丢失数据包。在此场景下,结合网络编码技术可以提高系统吞吐量,联合利用蜂窝与D2D链路能够进一步的提高传输效率。然而,如何合理的进行编码调度,充分发挥网络编码的潜力显得至关重要。因此,文章旨在设计联合蜂窝与D2D链路进行调度的网络编码广播重传方案,主要贡献如下:

本文主要研究重传阶段NCDI方案的设计,通过分析与推导,我们首先给出了重传次数的理论下限。

其次,针对RLNC策略下的联合蜂窝与D2D链路调度,提出了NCDI-RLNC方案;针对IDNC策略下的联合蜂窝与D2D链路调度,构建了用于表示所有编码组合的IDNC图,并给出了基于最大权重团搜寻的NCDI-IDNC方案。

不同条件(设备数量、数据包数目、以及链路丢包概率)下的仿真结果表明所提方案能够极大地提高重传效率,减少重传次数。

2 系统模型

图1 无线广播网络示意图Fig.1 Example for wireless broadcast network

假设设备之间彼此邻近,每个设备都属于其他设备的传输覆盖区域内,从而构成了一个完全连接的D2D网络。因此,为避免D2D链路产生干扰,每个时隙只允许单个设备在D2D通信频谱中进行广播传输,而其余设备都处于侦听状态。此外,文中将物理信道的条件(例如衰落,阴影,信道估计误差等)抽象为数据包能否成功接收,以擦除(丢包)概率来衡量信道条件,并假设各擦除信道之间彼此独立。其中,基站到设备Ri之间的丢包概率表示为δi,设备Ri与Rj之间的丢包概率表示为δi, j,且假设δi, j=δj,i。

重传阶段,为迅速恢复丢失数据包的同时减轻基站负载,设备同时使用双接口,联合利用蜂窝链路与D2D链路进行重传。换句话说,设备在每个重传时隙最多能收到两个编码包,分别来自于基站与发送设备。重复上述“编码—重传—更新状态信息”过程,直到所有设备都能正确接收到N个源数据包。

例 1 以图1为例说明联合蜂窝与D2D链路进行重传的优势。基站将四个数据包{P1,P2,P3,P4}广播给终端设备{A,B,C},设备将正确接收到的数据包放入缓存中。重传时假设无“丢包”的理想信道,考虑只使用蜂窝链路进行数据包恢复重传,基站依次重传编码包P1⊕P2⊕P3和P4,用户需要两个时隙能接收到完整数据;考虑只使用D2D链路进行合作恢复重传,设备A广播编码包P3⊕P4、设备B广播编码包P1⊕P2,两次重传后所有设备能够恢复丢失数据包。然而,考虑在重传阶段联合蜂窝与D2D链路进行调度,基站广播编码包P1⊕P2的同时用户A广播编码包P3⊕P4,则传输次数可以减少为一次,进一步提高了重传效率。

为了更有效地利用有限资源(如设备的能量、带宽等),减少重传次数,我们需要在每个时隙做出最佳的调度决策。因此,本文的重点是设计和开发高效的网络编码调度方案,并对其吞吐量性能进行研究。

定义 1 重传次数T—由于无线广播信道的“丢包”影响,广播阶段结束后,用户只能接收到部分数据包,我们将设备恢复所有数据包所需的传输时隙定义为重传次数。

3 重传次数下界

本节我们将给出重传次数的下界,其反映了在理想情况下,设备同时利用蜂窝与D2D通信接口来恢复丢失数据包所需的最小重传次数Tlb。值得注意的是,文章推出的下限并不一定保证能够达到,但是它保证没有其他任何方案可以优于此下界。为了评估所提方案的有效性,可以将此下界视为一个很好的度量。

(1)

若系统中存在多个设备,那么系统总的重传次数由所需重传次数最大的设备决定,可表示为:

(2)

(3)

综上所述,且考虑重传次数为整数值,得出设备恢复所有丢失数据包的重传次数下界为:

Tlb≥

(4)

4 方案描述

为充分发挥网络编码增益,最小化重传次数,基站需要充分利用收集到的数据包状态信息,在每个时隙做出最优调度决策。为此,本节针对随机线性网络编码(RLNC)与立即可译网络编码(IDNC)两种不同的编码策略,分别提出了NCDI-RLNC和NCDI-IDNC方案。

4.1 NCDI-RLNC方案

定义 3 有效编码包—当设备接收到一个编码包时,首先判断该编码包是否包含其丢失数据包的信息,我们将满足此条件的编码包称为有效编码包。换句话说,也就是判断该编码包是否与设备已有的数据包线性独立,能否帮助设备解码出丢失数据包。

表1 NCDI-RLNC方案调度流程

4.2 NCDI-IDNC方案

针对IDNC策略,本小节给出了基于最大权重团搜寻的NCDI-IDNC编码调度方案。不同于RLNC,IDNC的核心思想为发送端对数据包采用简单的异或(XOR)操作,以接收端直接可译为目标进行编码,无法译码的编码包直接丢弃,不再用于后续译码过程中。因而,NCDI-IDNC方案更适用于要求数据包逐个解码的实时多媒体应用。

(1)j=l,设备Ri与设备Rk需要同一个数据包Pj=Pl;

图2 基站及设备A侧的IDNC图示例Fig.2 Example of IDNC Graph (a) IDNC Graph (b) IDNC Graph of Device A

对于NCDI场景下的广播重传,每个时隙我们需要确定两个最佳编码包,分别来自于蜂窝链路与D2D链路,使尽可能多的用户能够从中解码出丢失数据包。表2中给出了NCDI-IDNC方案的具体调度流程,其核心思想在于分两阶段依次找出基站端与设备端的最大权重团CB、CD。其中,CB对应的编码包由基站通过蜂窝链路广播给所有设备,CD对应的编码包由发送设备通过D2D链路广播给其余设备。具体步骤描述如下:

表2 NCDI-IDNC方案调度流程

5 开销与复杂度分析

5.1 通信开销

文中系统采用基站集中控制的方式,即在每个时隙,基站依据收集到的反馈信息做出调度决策,并且将决策广播给相应的D2D发送设备。因而,在实际环境下,重传阶段每个时隙的额外开销主要由三个部分组成:发送决策信息的开销,收集反馈信息的开销以及编码系数的包头开销。

对于NCDI-RLNC方案而言,重传阶段,基站选取一个设备作为D2D链路中的发送设备,该设备向其余设备广播其已有数据包的线性组合。因而决策信息仅需要1比特,以告知该设备是否作为发送设备。其次,两个RLNC编码包分别由基站与设备广播,编码系数的包头开销为2Nlog(F)比特。最后,由于基站需要根据各个设备反馈的数据包接收状态以便做出下一时隙的调度决策,设备需要向基站反馈接收状态信息,指示两个接口中的每一个接收/丢失数据包。每个设备需要使用2比特来确认两个接收/丢失的数据包,对于网络中的M个设备而言,收集反馈信息的开销为2M比特。因此,重传阶段采用NCDI-RLNC方案的通信开销为1+2Nlog(F)+2M比特每时隙。

对于NCDI-IDNC方案而言,每个时隙基站需要确定发送设备以及该设备需要广播的编码组合。实际上,一个IDNC编码包最多由N个数据包异或,因此发送的决策信息包含N比特。由于IDNC策略采用的是二进制编码,两个IDNC编码包的包头开销可视为2N比特。同样,用于收集反馈信息的开销为2M比特。综上,重传阶段采用NCDI-IDNC方案的通信开销为3N+2M比特每时隙。

5.2 计算复杂度

对于NCDI-RLNC方案来说,基站侧构建编码包的复杂度为O(N);计算设备作为发送设备时可提供的有效编码包数量,其复杂度为O(M-1);对每个设备都重复此操作,从而选出发送设备的复杂度为O(M(M-1));设备侧构建编码包的复杂度为O(N)。因此,NCDI-RLNC方案的计算复杂度为O(N+M(M-1)+N)=O(M2+N)。

文献[9]中的讨论结果表明构建IDNC图并求解最大权重团的复杂度为O(M2N)。为寻找最佳编码策略,NCDI-IDNC方案首先需要在基站侧构建IDNC图并确定最佳编码包,复杂度为O(M2N);其次,选择Has集合最大的设备作为发送设备的复杂度为O(M),构建设备侧IDNC图并确定最佳编码包,其复杂度最多为O((M-1)2N)。因此,NCDI-IDNC方案的计算复杂度为O(M2N+M+(M-1)2N)=O(M2N)。

6 仿真结果

表3 不同方案的计算复杂度比较

图3 重传次数vs.设备数量MFig.3 The retransmission times versus the number of devices

图4 重传次数vs.数据包数目NFig.4 The retransmission times versus the number of packets

图5 重传次数vs.蜂窝、D2D链路平均丢包概率δFig.5 The retransmission times versus mean cellular/D2D erasure probabilities

7 结论

本文对联合蜂窝与D2D链路的网络编码广播重传方案进行了研究。考虑移动设备配备有双接口的无线网络编码广播场景,设备之间彼此靠近,因此在重传阶段可以同时利用蜂窝与D2D链路来恢复丢失内容。为最小化重传次数,合理的进行编码调度,文章针对RLNC策略下的联合蜂窝与D2D链路调度,提出了NCDI-RLNC方案;针对IDNC策略下的联合蜂窝与D2D链路调度,提出了基于最大权重团搜寻的NCDI-IDNC方案。仿真结果表明,与其他方案相比,提出的两种方案均能有效提高重传效率、减少重传次数。