提高蜂窝网络中数据分发效率的D2D协作转发算法

周 斌 胡宏林

①(中国科学院上海微系统与信息技术研究所 上海 200050)

②(中国科学院无线传感网与通信重点实验室 上海 200335)

③(上海无线通信研究中心 上海 200335)

1 引言

当前的蜂窝移动通信系统是一种基于预设基础设施的集中式通信网络，系统中的移动终端不允许进行点到点直接通信，终端间通信需要经过有线骨干网或中心控制节点的路由和转发。与这种集中式控制的通信方式不同，D2D(Device to Device)通信是一种新颖的应用于蜂窝系统中的终端间直接通信技术，它允许移动终端在蜂窝系统的控制下使用蜂窝系统授权频段进行点到点通信[1-4]。由于具有降低终端发射功率、延长电池使用时间、增强多播和广播传输速率、提高系统频谱效率等诸多优势，D2D通信逐渐成为无线通信领域的研究热点。蜂窝网络中的数据分发(data dissemination)是指网络中某些拥有特定数据的固定节点采用单播、多播或广播的方式将数据通过无线链路发送到多个移动终端上，从而提供用户指定的信息服务[5]。典型场景包括：音乐或电影文件下载、实时音频视频接收、远程教育和分布式会议等。在蜂窝网络中，数据分发的发射方通常为基站，接收方为多个指定的用户终端。

D2D通信可用来提高蜂窝网络中数据分发的效率[5,6](以下简称为D2D增强型数据分发)。以多个终端协作下载同一文件为例：首先，在地理位置上彼此接近的多个终端建立起一个D2D协作簇[7]，簇内各终端间可以进行点到点直接通信；其次，待分发的数据文件在网络侧被切分为多个小数据包，基站以单播的方式将各数据包分别发送给不同的终端；最后，各终端通过D2D通信交换彼此接收到的数据包，重新生成完整的数据文件，达到数据分发的目的。通过上述接收终端间的D2D数据协作转发，多个低速的下行信道被汇聚成了一个虚拟的高速下行信道，数据分发的速率得以大大提高；同时，由于短距离的D2D链路具有较好的信道质量，能支持高速率的簇内数据转发，进而数据分发的频谱利用率也可获得较大的提升。

由于 D2D通信需要使用蜂窝系统的授权频段来确保可控的干扰环境和传输质量[8]，提高D2D增强型数据分发效率的关键在于提高协作簇内终端间数据转发的效率。经典的协作簇内数据转发算法大致可分为两种，D2D单播转发和D2D多播转发。在文献[6]中，协作簇内各终端以单播的方式与其它终端交换视频子流，能够实现接收图像质量的共同提高；然而，该方案没有考虑D2D信道容量的差异性，所有的单播速率均设定为相同值，转发效率受限于簇内最差的D2D链路。文献[5]给出了一种基于多播的D2D转发算法，信源终端能一次性向多个目标终端进行数据转发；但是，多播传输的缺点在于，为了确保所有目标终端的正确接收，多播速率必须取决于链路质量最差的目标终端。上述现有的D2D单播或多播数据转发算法，均没有充分考虑D2D链路的差异性，数据转发的传输速率很容易受限于少数较差的D2D链路，因而无法最大限度地利用宝贵的频谱资源。

为此，本文提出了一种高效的基于多跳中继的D2D协作转发算法，包括多播和单播两种模式。在每次信源终端向簇内所有其他终端进行数据转发的过程中，该算法能根据D2D链路的信道容量自适应地搜索出最优中继节点、转发路由、多播对象和传输跳数，通过充分利用协作簇内的多信道分集增益，达到提高转发速率、增大数据分发吞吐量的目的。

2 系统模型

图1 D2D增强型数据分发

蜂窝系统中 D2D增强型数据分发的通信过程如图1所例示。隶属于同一蜂窝系统且地理位置上彼此接近的终端1，终端2和终端3组成了一个D2D协作簇；其中，簇内任意两个终端可进行点到点直接通信。基站将待分发的数据包D切分为3个小数据包D1,D2和D3，通过下行链路将它们分别发送给终端1，终端2和终端3。在正确接收到各自的小数据包后，终端1向终端2和终端3转发D1，终端2向终端1和终端3转发D2，终端3向终端1和终端2转发D3。最后，每个终端将分别从基站和簇内其他终端处获得的数据包合并，以重新生成完整的数据包D。

当上述D2D增强型数据分发被应用于TD-LTE蜂窝系统中，其帧结构[9]可由图2所例示。工作在时分双工的模式下TD-LTE系统，其每个MAC帧由一个特殊子帧和若干个上行或下行子帧组成。当D2D增强型数据分发需要在某个下行子帧中进行传输时，该子帧可被划分为两个时段。在时段 1，基站以单播的方式向 D2D协作簇内的每个终端分别传输不同的数据包，各个单播占据不同的时频资源；在时段 2, D2D协作簇内的各个终端依次进行数据转发，转发内容为该终端在时段1成功接收到的数据包，转发对象是该簇内的所有其他终端。

3 现有的D2D转发算法和缺陷分析

图2 TD-LTE系统中的D2D通信帧结构

D2D协作簇的拓扑可以看作是由终端(节点)和D2D链路构成的图，记为G=(V,E)，其中V表示簇内节点序号的集合，E表示簇内D2D链路的集合。节点序号是用来唯一标识该节点的自然数。对于任何i,j∈V，符号(i,j)表示连接节点i和节点j的D2D链路。两节点之间的距离d(i,j)定义为在链路(i,j)上传输1 bit信息所需要的调制符号个数。例如，节点1和节点2之间的链路支持QPSK调制和1/3码率的传输，则d(1,2)=3/2。

现有的典型 D2D协作簇内数据转发算法可分为两种：单播模式(如文献[6]所述)和多播模式(如文献[5]所述)。在单播(“一对一”)模式下，每个终端在一次 D2D传输中只能将数据包转发给一个其他终端[6]；因此，对于每个终端而言，为了完成向簇内所有其他终端转发数据包的任务，需要进行多次独立的D2D单播传输。考虑一个包含N个终端的D2D协作簇VN= {1, 2,…,N}，在单播模式下实现每个终端都完成1 bit信息的转发，需要进行N× (N- 1)次D2D单播，总共所需要的调制符号数可表示为

在多播(“一对多”)模式下，信源终端通过一次D2D多播传输即可向簇内所有其他终端进行数据转发[5]；然而，为了确保每个接收终端都能正确接收转发的数据包，D2D多播的传输速率必须由连接信源终端和接收终端的多条链路中最差的那条链路来决定。在上述包含N个终端的D2D协作簇VN内，以多播的模式实现每个终端都完成1 bit信息的转发，需要进行N次D2D多播，总共所需要的调制符号数可表示为

虽然上述 D2D单播和多播转发算法都能实现协作簇内的信息共享，达到数据分发的目的；但是其传输效率并不高。原因在于：(1)D2D链路的信道容量存在较大的差异。尽管D2D协作簇是由位置上彼此接近的终端组成，但由于较低的天线高度、不规则分布的阴影区域以及信道衰落和路损的差异，协作簇内各条 D2D链路所能够支持的传输速率差别很大。(2)现有D2D单播或多播转发算法的效率，如式(1)，式(2)所示，很大程度上取决于协作簇内最差的若干条链路。这些较差的D2D链路，形成了簇内数据转发的容量瓶颈，进而也降低了整个数据分发的效率。

4 本文提出的基于多跳中继 D2D协作转发算法

为了有效提高D2D转发算法的传输效率，需要尽可能地“绕开”簇内那些信道质量较差的链路，通过信道容量较大的D2D链路进行数据包的转发；换言之，根据一定的策略在D2D协作簇内选择合适的终端作为数据包转发的中继节点，适当地增加数据包转发次数，以高速率的多跳传输取代低速率的单跳传输，可有效地提高D2D转发的传输速率。

以图3为例，如果终端1直接向所有其他终端进行 D2D多播转发，多播速率取决于最差链路(1,3)，资源消耗为 5；若以终端 4作为中继，进行两跳的D2D多播传输，则资源消耗可降为3，其中第1跳和第2跳多播的资源消耗分别为1和2。同理，如图4所示，终端1直接终端3进行D2D单播转发的资源消耗为 5，如果选择终端 5为中继进行两跳D2D单播传输，则资源消耗可降为1.5。由此可见，多跳的D2D转发方案能够利用簇内的多信道分集增益，达到提高传输效率的目的；然而，获取多信道分集增益的关键在于选择合适的中继节点和转发路由(对于多播算法还包括了多播接收对象的选择)。上述因素共同决定了D2D转发的实际效率，需要根据 D2D链路的信道质量情况进行自适应的选择。下面具体介绍基于多跳中继的D2D多播和单播协作转发算法。

定义在D2D协作簇VN={1, 2,…,N}中，当终端i需要向簇内所有其他终端转发数据包，信源终端集合可定义为VT= {i}，接收终端集合可定义为VT在VN中的余集，即VR=VNVT。对于VN的任意一个非空子集U以及VN内的任意一个元素i，定义函数：

算法1(基于多跳中继的 D2D多播协作转发算法)：

输入：D2D协作簇G=(VN,E)，信源终端集合VT={i}，接收终端集合VR，簇内任意两终端间距离d。

图3 单跳多播与多跳多播示例

图4 单跳单播与多跳单播示例

输出：在D2D多播转发跳数不大于2的约束下，从VT到VR的最优多播转发路径及相应的资源消耗costopt。

第1步 根据式(4)计算初始门限值T(0)。

第2步 对于第n次迭代的门限值T(n)，根据式(5)和式(6)分别计算“候选中继集合”和“两跳终端集合”。若候选中继集合为空集，转入第6步；否则转入第3步。

第3步 根据式(7)在候选中继集合中寻找最优中继节点，根据式(8)分别计算第1跳D2D多播和第2跳D2D多播的资源消耗。

第4步 根据式(9)，计算并记录当前路径下两跳D2D多播的资源消耗总和。

第5步 根据式(10)，计算第n+1次迭代的门限值T(n+1)，并返回第2步。

第7步 根据式(12)，计算单跳D2D多播方案中的资源消耗。

算法2(基于多跳中继的 D2D单播协作转发算法)：

输入：D2D协作簇G=(VN,E)，信源终端集合VT= {i}，接收终端集合VR，簇内任意两终端间距离d。

输出：在D2D单播转发跳数不大于2的约束下，从VT到VR的最优单播转发路径树及相应的资源消耗costopt。

第1步 对集合VR中的所有元素(节点序号)进行排序，排序后序列记为R={r1,r2,…,rN-1}。排序的规则为：对于任何rm,rn∈R，若m＜n，则d(i,rm)≤d(i,rn)。

第2步 算法初始化：生成一颗空的路径树并将终端i设为该树的根节点；令终端i的资源消耗函数cost(i)=0；令集合VSR={i}，循环变量k=1。

第 3步 根据式(14)，在集合VSR中寻找终端rk的最优父节点xopt。在路径树中，将终端rk添加为节点xopt的子节点。

第4步 根据式(15)，计算终端rk的资源消耗函数。

第5步 若终端rk是终端i(路径树根节点)的子节点，则终端rk加入集合VSR。

第6步 若k＜N- 1，将循环变量k更新为k+1，并返回第3步；否则，根据式(16)计算并记录从VT到VR的最小资源消耗。

由于D2D通信需要在蜂窝系统的控制下进行，过多次数的簇内数据转发可能会增加数据分发业务的时延以及蜂窝系统的信令开销；因此，上述算法在提高 D2D传输效率的同时都对数据包转发的次数进行了限制，即：从任意信源终端到其目标接收终端，D2D传输(单播或多播)的跳数不超过两跳。

5 性能仿真

本文采用 MATLAB语言进行仿真实验，比较了现有的D2D转发方案和基于多跳中继的D2D转发方案的数据转发效率；性能对比分为单播转发方案对比和多播转发方案对比两个部分。不失一般性，本文假设：所有的移动终端在D2D协作簇内均匀分布，D2D链路的小尺度衰落为慢变平坦瑞利衰落模型，终端间的 D2D通信采用自适应编码调制技术(AMC)以充分利用信道容量。参考LTE系统的链路自适应传输方案[10]，编码调制格式共分为15级，因此，仿真中所对应的簇内节点间距离d(定义见第3节)的有效取值如表1所示。

度量 D2D转发效率的性能指标为归一化资源消耗，其定义为：D2D协作簇内的每个终端都向簇内所有其他终端成功转发1 bit信息，所需的调制符号总数。在仿真中，D2D协作簇的大小分别设定为包含4, 6, 8和12个终端，以观察协作簇大小对算法性能的影响。对于每一种进行仿真的簇大小，随机产生 D2D协作簇(包括终端位置和链路质量)100,000次，即每个数据点都进行 100,000次独立仿真，计算平均归一化资源消耗。

表1 对应于LTE系统编码调制格式的节点间距离取值

图5对比了本文所提出的基于多跳中继的D2D多播转发方案(简称为多跳多播算法)和传统的单跳D2D 多播转发方案(简称为单跳多播算法)[5]在不同大小协作簇中的转发效率。图中所示的百分比为资源消耗比值，计算方法为多跳多播算法的归一化资源消耗除以单跳多播算法的归一化资源消耗。结果表明，在所有被仿真的D2D协作簇中，多跳多播算法的传输效率均大大优于传统的单跳多播算法，资源消耗比约为30%；而且，随着D2D协作簇的增大，多跳多播转发算法的优势更加明显，资源消耗比从簇大小等于 4时的 37%逐步降低到簇大小等于 12时24%。

原因在于，尽管传统的单跳多播算法能够最大限度地利用“多播增益”，即仅通过一次多播完成向所有接收终端的转发，但多播的传输速率严重受限于最差的D2D收发链路；多跳多播算法则不然，通过自适应的选择最优中继节点、最优多播接收对象和最优传输跳数，在获取“多播增益”的同时也充分利用了D2D协作簇内的多信道“分集增益”。当D2D协作簇较小时，簇内的D2D链路差异趋同，多信道分集增益相对较小，因此多跳多播算法增益相对较小；随着D2D协作簇逐步增大，D2D链路差异趋于明显，分集增益随之变大，因此多跳多播算法的优势也更加明显。

图6对比了本文所提出的基于多跳中继的D2D单播转发方案(简称为多跳单播算法)和传统的单跳D2D 单播转发方案[6](简称为单跳单播算法)在不同大小协作簇中的转发效率。图中所示的百分比为资源消耗比值，计算方法同上。结果与多播算法仿真类似，在所有被仿真的D2D协作簇中，多跳单播算法的传输效率均大大优于传统的单跳单播算法，随着D2D协作簇的增大，多跳单播转发算法的优势更加明显，平均资源消耗比约为36%。

值得注意的是，本文所提出的多跳单播算法与计算单源最短路径的经典Dijkstra算法不同：(1)通过对接收终端集合VR内元素的排序操作，多跳单播算法不需要在每次循环中反复修正每个节点的资源消耗函数，从而大大降低了算法复杂度；(2)通过算法2的第1步和第5步的操作，该算法将D2D转发次数限制在两跳之内，在降低了D2D转发的时延和信令开销的同时，确保了对簇内多信道“分集增益”的充分利用。

6 结束语

利用 D2D通信提高蜂窝网络中数据分发效率的关键在于设计高效的终端间转发算法。在传统的基于单跳多播或单跳单播的转发方案中，转发速率严重受限于信道质量较差的若干条D2D链路。本文提出了一种高效的基于多跳中继的 D2D协作转发算法，包括多播和单播两种模式。通过自适应地选择最优的中继、路由、接收对象和传输跳数，该算法能充分利用D2D协作簇内的多信道分集增益。仿真结果表明，该算法能明显提高终端间数据转发的资源利用率，进而大幅提升数据分发业务的吞吐量；此外，随着D2D协作簇的增大，该算法的优势愈加明显。

图5 本文算法与文献[5]算法的性能对比

[1]Janis P, Yu C H, Doppler K,et al.. Device-to-Device communication underlaying cellular communications systems [J].International Journal Communications, Network and System Sciences, 2009, 2(3): 169-178.

[2]Doppler K, Rinne M P, Janis P,et al.. Device-to-Device communications; functional prospects for LTE-Advanced networks [C]. Proc. IEEE International Conference on Communications, Dresden, Germany, June 2009: 1-6.

[3]Doppler K, Rinne M, Wijting C,et al.. Device-to-Device communication as an underlay to LTE-advanced networks [J].IEEE Communications Magazine, 2009, 47(12): 42-49.

[4]王彬, 陈力, 张欣, 等. 在 LTE-Advanced网络下的Device-to-Device通信[J]. 现代电信科技, 2010, (7): 24-27.Wang B, Chen L, Zhang X,et al.. Device-to-Device communication as an underlay to LTE-Advanced networks [J].Modern Science and Technology of Telecommunications, 2010,(7): 24-27.

[5]Popova L, Herpel T, Gerstacker W,et al.. Cooperative mobile-to-mobile file dissemination in cellular networks within a unified radio interface [J].Computer Networks, 2008,52(6): 1153-1165.

[6]Fitzek F H P and Katz M. Cognitive Wireless Networks:Concepts, Methodologies and Visions Inspiring the Age of Enlightenment of Wireless Communications [M]. New York:Springer, 2007: 31-59.

[7]Koskela T, Hakola S, Chen T,et al.. Clustering concept using Device-to-Device communication in cellular system [C]. Proc.IEEE Wireless Communications and Networking Conference,Sydney, Australia, April 2010: 1-6.

[8]Wang B, Chen L, Chen X H,et al.. Resource allocation optimization for Device-to-Device communication underlaying cellular networks[C]. Proc. IEEE Vehicular Technology Conference, Budapest, Hungary, May 2011: 1-6.

[9]3GPP TS 36.211v10.2.0-2011. Physical channels and modulation (Release 10) [S]. 2011.

[10]3GPP TS 36.213v10.2.0-2011. Physical layer procedures(Release 10) [S]. 2011.