一种基于多跳D2D和社交感知的新颖中继选择算法

李良，杨新杰

（宁波大学信息科学与工程学院，浙江 宁波 315211）

0 引言

近年来，随着移动通信技术以及互联网行业的迅速发展，智能无线终端得到了快速发展和普及，蜂窝网络用户数量呈现爆炸式增长。根据《思科年度互联网报告（2018—2023年）》，到2023年，全球手机用户将增加到57亿人（占总人口的71%），全球移动设备将增长到131亿部[1]。如此庞大的用户和设备数量，给蜂窝网络的基站带来了巨大的负载，同时导致无线频谱资源短缺、频谱利用率低下和网络容量不足等问题日益凸显[2]。研究人员因此提出了设备到设备（device-to-device，D2D）通信技术以应对上述问题。不同于只允许设备和基站之间通过上行/下行链路进行通信的传统移动通信技术，D2D允许邻近的移动设备直接进行通信，有效地提高了蜂窝网络的频谱效率或吞吐量[3]。另一方面，D2D设备既可以通过使用非授权频谱或专用蜂窝频谱实现通信，也可以通过复用蜂窝设备使用的频谱实现通信[4]。这种复用模式能够大幅提高频谱利用率，有助于解决频谱短缺问题[5]。由于具有多种优势，D2D技术被3GPP确定为5G关键技术之一，受到越来越多研究人员的关注。

传统的直连D2D具有通信距离短，消耗设备电量多，对蜂窝网络干扰大等问题。另外，在设备间距离较远时，直连D2D的源设备可能无法接入目的设备[6]。一些研究人员在 D2D中引入中继技术，进一步提高了 D2D通信的性能，中继选择由此成为D2D中一个重要的研究方向。

为了减少算法执行给基站带来的负担，研究人员提出了一些不需要基站参与的中继选择算法。文献[7]提出了一种基于计时器的中继选择方法，该方法能够分布式确定并选择最好的中继。文献[8]提出了一种用以设备为中心的中继选择方案。该方案通过交换设备邻居表获得D2D通信设备的共同邻近设备，然后基于信干噪比和剩余电量等多种参数从共同临近设备中选出最佳的设备作为中继，相比传统的以网络/基站为中心的方案，减少了基站负载和网络开销。

另外，为了进一步扩大 D2D通信范围和提升通信性能，研究人员将研究从单跳延伸到多跳D2D 通信[9]。文献[10]提出了一种基于 Dijkstra算法的 D2D多跳路由算法，仿真结果表明与单跳直接 D2D通信相比，多跳路径可以实现更高的吞吐量。文献[11]提出了一种用于D2D通信的自适应干扰感知多跳路径选择算法。该算法通过了解用户位置，使多跳路径从 D2D发射端开始首先到达小区边缘，然后沿小区边缘移动，最后到达接收端附近时返回小区内部。该算法在小幅度牺牲传统蜂窝容量的情况下显著提高了整体网络容量。

考虑在实际的系统中，设备充当中继时具有自身意愿问题，研究人员考虑更加现实的场景并将终端的社交域引入D2D研究中。文献[12]提出了一种利用社交网络的中继选择方法。该方法综合考虑中继的物理域和社交域因素，将根据用户遭遇历史计算得到的链路传输稳定性和根据用户亲密度计算得到的合作意愿作为标准选择中继。相比传统的方法，该方法可以提高中继选择成功的概率，减轻蜂窝网络的负担。文献[13]提出了一种创新的社交感知节能中继选择机制，该机制考虑了移动用户之间隐藏的社交关系，能够确保更多用户愿意参与合作通信。

上述 D2D中继选择算法均应用于蜂窝网络场景，文献[14]提出了一种应用于物联网场景的多跳 D2D通信最优路由算法，在算法中融合了社交域信息，通过使用基于排序的信任模型推导得到 D2D连接的信任概率，由信任概率得到了节点间的可信任连接概率，并在算法中考虑了可信任连接概率的影响。最终所提出的路由算法可以使任意一对 D2D以分布式的方式实现最高的可信任连接概率，几乎达到了通过穷举搜索实现的性能。

综上所述，目前在两跳D2D方面已有一些关于分布式或以设备为中心的中继选择算法的研究，但有关多跳D2D中继选择的研究基本没有考虑算法的执行方式和复杂度这一问题。另一方面，现有关于多跳 D2D中继选择的研究是基于半双工中继，算法的吞吐量性能受到限制。同时，对社交域信息在实际系统中对算法性能的影响的研究还不充分。因此，本文提出了一种用于蜂窝网络下多跳 D2D通信的中继选择算法。通过使用全双工中继，保证了多跳 D2D的吞吐量性能。通过合理地设计执行流程，中继选择算法在工程实现上能够以半分布式的方式执行，有效地减少了基站负载。考虑设备充当中继的意愿问题，在中继选择算法中引入了社交域信息，并与没有引入社交域信息的方案进行了对比。仿真结果表明，相比于对比算法，所提算法在不考虑社交域信息时能够改善系统的吞吐量和能量效率，在考虑社交域信息时能够大幅提升系统的能量效率。

1 系统模型

1.1 网络基础设施模型

一个单小区蜂窝网络中的多跳D2D通信物理模型如图1所示，包括位于小区中心的基站（base station，BS），若干通过上行正交信道与基站通信的蜂窝设备（cellular equipment，CE），若干当前没有通信需求的空闲设备（idle equipment，IE），多跳D2D通信的源（source，S），多跳D2D通信的目的地（destination，D），以及若干为S和D之间的通信转发数据的中继（relay，R）设备。基站配备有全向天线，所有设备配备有两个天线且工作在全双工模式。

图1 多跳D2D通信物理模型

1.2 信道模型

在本文中，假设所有信道均为瑞利衰落信道，同时考虑自由空间传播路径损耗，则任意一个节点x向另一个节点y发送信号时节点y的接收信号功率为：

其中，Px表示x的发射功率，表示x和y之间的信道增益，且h~CN(0,1)，表示x0和y之间的距离，α表示路径损耗指数。

1.3 社交模型

在实际的D2D通信中进行中继选择时，由于自身有通信需求或电池电量有限等原因，持有中继设备的用户可能不愿意充当他人的中继，或者不愿意为转发他人的数据贡献太多的功率。但是，如果持有中继设备的用户和进行D2D通信的用户有亲密的社交关系，那么该用户就很有可能愿意充当中继或为转发D2D通信的数据贡献更多的功率。因此，在实际的系统中，有必要将社交域信息引入多跳D2D通信的中继选择算法中。

在现实生活中，两个关系密切的人之间一般会通过电话或社交软件等频繁地联系，并且每次联系时持续的时间比较长；而两个关系疏远的人之间一般很少联系，并且联系时持续的时间比较短。另一方面，考虑基站可以从数据库中获取用户的通话记录，并且在用户通过社交软件联系时可以很方便地记录次数、时长等数据，因此用持有设备的用户之间通过电话或社交软件进行联系的次数和时长来量化他们之间的社交关系，具体的计算式如下：

其中，ui,j表示用户j与用户i之间的社交关系强度，Ti,j表示用户j与用户i之间的总联系次数，表示用户i与所有用户进行过的联系的次数之和，Di,j表示用户j与用户i之间的总联系时长，表示用户i与所有用户进行过的联系的时长之和。

根据文献[15]的研究，绝大多数用户之间的社交关系强度比较弱，只有少数用户与其他用户之间有着较强的社交关系，类似于帕累托分布。帕累托分布的概率密度函数如下：

其中，尺度参数xmin＞0。

在本文中，用帕累托分布建模用户之间的社交关系强度，并规定中继的发射功率与他们和源、目的地之间的社交关系强度有关。用uS,j和uD,j分别表示设备j与S和D之间的社交关系强度，则由社交关系强度得到的设备j的发射功率为：

其中，max{⋅}表示取最大值，Pmax表示中继的最大发射功率。

2 中继选择算法

在某个时刻设备S想要与D进行D2D通信，由于他们之间的距离过远，因此只能在多个中继的帮助下才能成功建立D2D通信。在这种情况下需要从源和目的地之间的空闲设备中选出合适的设备作为中继，帮助转发S和D之间的数据。但是S和D之间的空闲设备数量众多，而且不同的空闲设备作为中继时D2D通信链路的性能不同，因此如何选择中继成为一个重要的问题。本文提出的中继选择算法主要由候选中继确定方法、被复用频谱的蜂窝设备确定方法以及中继选择算法执行方法3部分组成。

2.1 候选中继确定方法

毫无疑问，如果将源和目的地之间所有的空闲设备当作候选中继，并从中选出最佳的中继可以得到更准确的结果，但这样会导致算法复杂度过高，不利于实际应用。受多跳认知无线网络[16]和认知中继网络[17]中中继选择和路由策略方向相关研究的启发，同时为了减少算法复杂度，本文提出了一种基于中继簇（cluster）的候选中继确定方法，在中继选择时只把某些区域中的空闲设备当作候选中继，然后从中选出最后所需的中继。

假设S到D之间需要进行M（M≥3）跳D2D通信，则共需要从M-1个中继簇中选出M-1个空闲设备作为中继。中继簇的位置由S和D的位置以及事先设定的距离在S和D之间确定，S和D之间的中继簇示意图如图2所示。每一个中继簇均为圆心在S和D的连线上、半径为r的圆形区域。第一个中继簇的圆心与S之间的距离为r，之后的每一个中继簇的圆心与前一个中继簇的圆心之间的距离为L（L＞2r），D与最后一个中继簇的圆心之间的距离用l表示，0＜l≤L。

图2 S和D之间的中继簇示意图

2.2 被复用频谱的蜂窝设备确定方法

在本文中，为了提高频谱利用率，D2D设备通过复用蜂窝设备的频谱实现通信。为了避免多跳链路之间的互干扰以及全双工带来的自干扰，D2D通信的每一跳复用不同蜂窝设备的频谱，即中继工作在频分双工模式。另外，D2D通信复用蜂窝设备的上行频谱，一方面复用下行频谱时蜂窝设备接收干扰信号，复用上行频谱时基站接收干扰信号，而基站处理干扰的能力一般强于蜂窝设备；另一方面，相比于下行频谱，上行频谱通常未被充分利用[18]。另外，D2D通信的每一跳复用不同蜂窝设备的频谱，所以虽然在本文的模型中所有中继均工作在全双工模式，但各跳的信道干扰情况可以单独分析。多跳D2D通信第m跳干扰示意图如图3所示，假设Tm和Rm分别为多跳D2D通信第m跳的发射设备和接收设备，Cm为该跳复用的频谱所对应的蜂窝设备。

图3 多跳D2D通信第m跳干扰示意图

为了保证蜂窝设备的正常通信，BS从Cm处接收的信号的信干噪比（）需要达到一定的门限值，即：

其中，PCm表示Cm的发射功率（假设对于所有m，PCm均等于PC），PTm表示Tm的发射功率，，分别表示Cm和BS之间的距离和信道增益，、分别表示Tm和BS之间的距离和信道增益，rth表示BS能正确解码Cm发送的信号所需要的最小信干噪比（signal to interference plus noise ratio，SINR），N0表示背景高斯白噪声的功率。由式（5）可以得到：

取：

综上所述，多跳D2D通信第m跳复用蜂窝设备选择示意图如图4所示，做一直线连接Rm所在中继簇的圆心和基站并反向延长（在最后一跳Rm即是D，中继簇的圆心即是D的位置），以延长线上一点为圆心、r/2为半径做一与保护区域边界内切的圆，从该圆形区域内的蜂窝设备中选出到基站的接收信号功率最大的蜂窝设备作为第m跳复用的蜂窝设备。合理地设置R的数值既能避免D2D对基站造成严重的干扰，又能减小，增加，由式（8）可知第m跳的将增加，即该跳的吞吐量将增加。综上所述，根据上述过程选取的蜂窝设备可以改善D2D链路的吞吐量性能，同时又能保证蜂窝设备的QoS。

图4 多跳D2D通信第m跳复用蜂窝设备选择示意图

2.3 中继选择算法执行方法

多跳D2D通信在每一跳中既要从多个蜂窝设备中选出被复用频谱的设备，又要从中继簇中的多个空闲设备中选出中继，涉及的设备数量过多，如果完全由基站以集中式完成中继选择过程，必然会给基站带来过量负载和大量信令开销。本文提出的中继选择算法能够以半集中式的方式执行，基站只需完成D2D多跳通信开始时的信道参数、节点位置等信息的收集及少量的数据处理，中继选择则由参与多跳D2D通信的设备自行完成。

假设S和D之间的D2D通信总共M跳，则需要复用M个蜂窝设备的频谱，用F={f1,f2,…,fM}表示第一跳到第M跳复用的频谱。另外需要M-1个中继设备，这M-1个中继设备从M-1个中继簇中选出，从簇 1到簇M-1确定的中继分别用R1,R2,…,RM−1表示，每个中继簇中有N个空闲设备作为候选中继。用Pn′,m表示由式（4）得到的第m个中继簇中第n个空闲设备在考虑社交关系的情况下的发射功率，用P′ ={P1′,1,… ,Pn′,m,… ,PN′,M−1}表示各中继簇内的空闲设备在考虑社交关系情况下的发射功率集。用Pn′′,m表示由式（7）得到的第m个中继簇中第n个空闲设备在考虑干扰的情况下的最大发射功率。

忽略设备发现过程，具体的中继选择过程如下。

步骤1S、D发送D2D多跳通信请求到BS。

步骤2BS首先确定S、D的位置，然后根据第2.1节的方法确定各中继簇的位置、范围、其中包含的空闲设备和各空闲设备的位置，并通知各中继簇中的空闲设备其已被选作对应簇中的候选中继。接着根据数据库内的通话记录计算所有空闲设备与S和D的社交关系并得到集合P'，根据D及各簇的位置由第2.2节的方法确定各跳复用频谱对应的蜂窝设备共M个，记录这些蜂窝设备的频谱F。最后，BS记录S、各簇中的空闲设备与BS之间的信道增益，连同S、D和各簇中空闲设备的位置以及集合P'、F发送给D。

步骤3D将从BS处接收的数据发送给簇M-1中的空闲设备并将自己信号接收频率设为fm。

步骤4簇M-1中的各空闲设备根据式（7）计算在考虑干扰的情况下其发射功率最大值然 后 取{P1,M−1,… ,PN,M−1}=min{{·},{·}}表示取集合对应元素最小值。假设簇M-1中的各空闲设备在从D处收到数据的同时可以获得他们与 D之间的信道增益，则根据{P1,M−1,… ,PN,M−1}、簇M-1中的各空闲设备到D的信道增益由式（1）可得到他们发送信号给D时D的接收信号功率。然后各个空闲设备开启一个终止时间与其到D的接收信号功率成反比的计时器，接收信号功率最大的空闲设备的计时器最先结束，该设备即RM−1。然后RM−1向簇M-1中的其他空闲设备广播一条自己已被选作中继的消息，簇M-1中的其他空闲设备遂停止计数并得知自己未被选中。最后RM−1将从D处接收到的数据发送给簇M-2中的空闲设备，并将自己的信号发送频率设为fM，信号接收频率设为fM−1。

步骤 5各簇中的空闲设备重复步骤 4中的处理过程直至S根据式（7）确定其发射功率，并将其信号发送频率设为f1。

步骤6S开始D2D通信。

可以看出，根据上述步骤确定多跳通信链路后，每一跳的 SINR也即确定，故可用香农公式计算每一跳的吞吐量。假设蜂窝设备频谱带宽用B表示，则第一跳的吞吐量为：

中间第m跳的吞吐量为：

最后一跳的吞吐量为：

由于所有中继设备均工作在全双工模式，因此整条多跳D2D通信链路的吞吐量由吞吐量最小的那一跳的吞吐量决定，即多跳D2D通信的吞吐量为：

3 仿真结果及分析

本节给出所提出的算法通过仿真得到的数值结果，并与对比算法进行比较。仿真模拟了一个半径为 500 m、以配备全方向天线的基站为中心的圆形单小区蜂窝场景，蜂窝设备和空闲设备在小区内随机均匀分布。详细的仿真参数及其取值见表1。仿真中的社交感知（social awareness，SA）和非社交感知（social unawareness，SUA）算法为本文所提算法，SA算法中空闲设备的发射功率既考虑对蜂窝设备的干扰、同时也考虑社交关系，SUA算法中空闲设备的发射功率只考虑对蜂窝设备的干扰，不考虑社交关系；MLS0（max link selection，最大链路选择）、HTPRS0（highest transmit power relay selection，最大发射功率中继选择）为对比算法，由于认知无线网络中的一些多跳中继选择算法所考虑的系统模型与本文的系统模型类似，因此MLS和HTPRS均选自认知无线网络相关文献。

表1 仿真参数及其取值

不同S和D间距离下算法吞吐量比较如图5所示，可以看出所有算法的吞吐量均随着距离的增加而减少，这是因为随着距离的增加，所增加的跳只会导致各跳吞吐量的最小值不变或减少，所以整条链路的吞吐量会相应减少。在距离相等的情况下 SUA算法的吞吐量高于 MLS和HTPRS，这是因为SUA算法选择中继的指标与每一跳的 SINR直接相关，能够选出性能更好的中继。而在距离相等的情况下 SA算法的吞吐量不如SUA，这是因为SA算法对所有空闲设备的发射功率施加了额外的社交关系约束，所以 SA算法选出的中继的发射功率必定小于SUA算法选出的中继。

图5 不同S和D间距离下算法吞吐量比较

不同中继簇中空闲设备数量下算法吞吐量比较如图6所示。结果表明，SUA、SA和MLS 3种算法的吞吐量均随着空闲设备数量的增加而增加，这是因为随着空闲设备数量的增加，这3种算法能有更大的概率选出性能更好的空闲设备作为中继，而HTPRS算法选择中继时随机性更大，无法利用更多的空闲设备这一优势。在空闲设备数量相同的情况下 SUA算法的吞吐量大于MLS和 HTPRS的吞吐量，而 SA算法的吞吐量不如SUA算法的吞吐量。

图6 不同中继簇中空闲设备数量下算法吞吐量比较

不同S和D间距离下算法能量效率比较如图7所示，能量效率定义为链路吞吐量与所有参与多跳D2D通信的设备的实际发射功率之和的比。结果表明所有算法的能量效率均随着距离的增加而减少，这是因为随着距离的增加参与D2D通信的中继数量也在增加，这导致发射功率之和随之增加，而所有算法的吞吐量随着距离的增加而减小，因此能量效率减小。在距离相等的情况下SUA算法的能量效率优于MLS和HTPRS，而SA算法的能量效率远远超过其他3种算法。这是由于SA算法通过对所有空闲设备施加额外的社交关系约束，减少了每一跳被选出的中继的发射功率，因此发射功率之和大幅减少，虽然SA算法比SUA的吞吐量要低，它的能量效率却远远超过了另外3种算法。

图7 不同S和D间距离下算法能量效率比较

不同中继簇中空闲设备数量下算法能量效率比较如图8所示。结果表明SUA、SA和MLS 3种算法的能量效率均随空闲设备数量的增加而增加，HTPRS的能量效率均随空闲设备数量的增加基本保持不变。在空闲设备数量相同的情况下SUA的能量效率优于MLS和HTPRS，而SA算法的能量效率远远超过其他3种算法。

图8 不同中继簇中空闲设备数量下算法能量效率比较

SA和SUA算法性能比较见表2，总结了SA和SUA两种算法在不同S和D之间距离下的性能比较。可以看出，SA和SUA两种算法在吞吐量和能量效率两方面的性能差异很大，且在能量效率方面 SA相比于 SUA有很大优势，因此在D2D中继选择算法的研究中不能忽略社交域信息的作用。

表2 SA和SUA算法性能比较

4 结束语

本文提出了一种用于单小区蜂窝网络下多跳D2D通信的中继选择算法。首先在算法中引入了持有设备的用户之间的社交关系，以解决设备充当中继时的意愿问题，并使算法更具有现实意义；其次为了提高多跳D2D链路的吞吐量，不同于以往假设中继是半双工设备的研究，本文的模型基于全双工中继；然后为了避免全双工带来的严重的干扰，令中继工作在频分双工模式；最后通过合理设计，算法能够在较少依赖基站的情况下运行，有利于实际工程实现。蒙特卡洛仿真验证了所提算法的性能。仿真结果表明所提算法在不考虑社交关系信息时吞吐量和能量效率均优于对比算法，在考虑社交关系信息时吞吐量会小幅下降，但能量效率会大幅提高。这使本文所提算法在电池技术没有突破性进展和倡导节能减排的今天具有一定的实际应用价值。