基于社交网络结合贪心策略的车辆D2D通信中继选择算法

Relay Selection Algorithm Based on Social Network Combined with Greedy Strategy for Vehicle D2D Communication

摘要: 在基于车辆的设备到设备(D2D)中继通信系统中，以中断概率最小化为目标提出了一种社交网络结合贪心策略的车辆D2D通信中继选择算法。该算法首先根据物理传输距离和社交关系强度阈值对所有潜在中继节点进行预筛选过程，从而有效降低中继节点的平均探测次数；然后根据备选中继集合的大小进行选择优先权的排序，并结合贪心策略进行最优中继节点的选择。仿真结果表明，与已有中继选择算法相比，所提出的算法能够有效降低系统的中断概率，实现较好的连通性。

Abstract: In vehicle-based device-to-device (D2D) relay communication system, a vehicle D2D communication relay selection algorithm based on social networks combined with greedy strategy is proposed with the goal of minimizing the probability of interruption. The algorithm first performs a pre- screening process on all potential relay nodes according to the physical transmission distance and the threshold of social relationship strength, thereby effectively reducing the average probing times of the relay nodes; then, the selection priority is sorted according to the size of the candidate relay set. And combined with the greedy strategy, the optimal relay node is selected. The simulation results show that compared with the existing relay selection algorithm, the proposed algorithm can effectively reduce the system outage probability and achieve better connectivity.

1. 引言

移动互联网和无线通信的迅猛发展需要庞大的网络流量，这种需求对现有的移动通信系统带来了巨大的挑战。由于无线频谱资源的稀缺，各种无线移动应用也对无线网络造成了严重的压力 [1]。设备到设备(Device to Device, D2D)通信技术可以使现实世界中物理距离较近的终端设备绕过基站(eNB)进行直连通信 [2]。D2D通信允许D2D对复用蜂窝用户的资源，这能够有效的提高频谱资源利用率，降低通信网络中的功率损耗 [3]。此外，D2D通信也能够起到降低eNB负载的作用。随着车辆用户的增多，将D2D通信技术引入车辆通信中可以有效的提升车辆通信系统的传输距离和安全性。然而，在车辆D2D两端用户距离较远或者信道条件很差的情况下，直连的D2D通信往往并不能取得很好的效果。因此，为了扩大蜂窝网络的通信范围，提高通信的可靠性和灵活性，需要采用中继技术来辅助车辆D2D通信 [4]。

具有中继辅助的D2D通信技术能够有效的延长两终端的通信距离。在车辆通信系统中，D2D中继通信技术将作为智能交通的重要支撑得到广泛应用 [5]。文献 [6] 以D2D通信网络总吞吐量最大化为目标提出了一种基于Q-learning的中继选择算法。文献 [7] 以蜂窝上行链路和D2D链路的总吞吐量最大化为目标，提出了一种两级最优中继选择方案。但以上方案都没有考虑D2D对用户和中继用户之间的社会关系强度。在当今万物互联的社会，随着智能移动终端数量的激增以及各式各样的社交网络应用的层出不穷，人与人之间构成了复杂的社会关系网络，使得移动社交网络和人们的日常生活息息相关 [8] [9]。因此，中继辅助的D2D通信网络不仅要考虑传统的物理传输距离对通信系统的影响，还要考虑用户之间的社会关系强度对通信系统的影响。拥有更高社会关系强度的用户可能更愿意为D2D用户转发数据，因此将社交网络引入车辆D2D通信系统中对于数据传输的保密性以及用户体验满意度等方面具有重要的意义。文献 [10] 提出了一种基于社交感知的中点中继选择方案，以提高D2D通信系统的吞吐量。文献 [11] 通过在D2D通信中引入一种新的分布式社会关系架构，讨论和分析了动态社会关系和信任管理机制的新方法，得出了高效可靠的社会D2D中继网络能够显著提高毫米波5G无线网络容量的结论。文献 [12] 提出了一种基于D2D通信的中继协作系统模型，该模型不仅可以提高通信网络无线电资源效率，还可以为临近用户提供更高的传输速率。

但以上文献都很少关注车辆D2D中继通信系统的连通性问题，即中断概率最小化问题，在现实世界中车辆D2D用户往往需要的是稳定且安全的连接。因此，本文以车辆D2D通信网络中断概率最小化为目标，提出了一种基于社交网络结合贪心策略的车辆D2D通信中继选择算法。首先根据物理传输距离和社交关系强度阈值对小区内所有的中继节点进行预筛选，以降低算法的计算复杂度，加快算法的执行过程。然后根据每一对车辆D2D用户备选中继集合的大小进行中继选择优先权的排序，在每一对车辆D2D用户的选择过程中都选择当前最优的节点作为该车辆D2D用户对的中继节点进行通信，以保证局部最优化，最终达到降低车辆D2D通信系统中断概率的目的。

2. 系统模型

在本节中，建立两个表示用户终端设备之间关系的通信网络模型。第一个是D2D通信系统模型，详细描述了D2D中继通信的通信链路和干扰链路。第二个是社交网络模型，它表示终端用户之间的社交关系强度。

2.1. 社交网络模型

车辆用户的关系可以映射到社交关系网络和物理传输网络中。在物理传输层，终端设备只要在通信范围内就可以连接。但是在社交关系网络中，只有两个终端设备的社交关系达到一定强度才能连接。物理传输层的设备和社交网络层的用户之间存在相对稳定的对应关系。在车辆D2D中继选择的过程中，不仅要考虑物理传输层的关系，还有必要考虑社交网络层的关系。因为两终端用户之间的社交信任度越强，就代表转发数据的意愿就越高。选择社交关系强度高的用户作为中继用户，可以有效降低用户隐私泄漏的风险。相反，若选择社交强度低的空闲用户作为中继节点，可能会导致用户的隐私泄漏，甚至影响D2D连接的稳定性。因此，在中继节点的选择策略中，社交强度可以作为一个关键的决策因素。

车辆用户的社交关系网络模型如图1所示。从社交网络层可以看出，用户4与用户2具有一定的社交关系强度，而用户4与用户3之间没有社交关系强度。这意味着用户2与用户4可能是亲戚或者是朋友的关系，而用户3与用户4可能是陌生人的关系。那么用户2替用户4转发数据的意愿要高于用户3，隐私泄露的风险也相对低一点。但是在物理传输层中，用户4与用户3之间的距离要明显的小于用户4与用户2之间的距离。因此，选择哪个空闲用户作为中继节点进行车辆D2D通信要综合考虑用户社交关系和物理位置信息。从直观上看，选择物理距离较近或者社交关系越强的空闲用户作为中继节点在车辆D2D通信中的收益越高。

Figure 1. The projection relationship of vehicle social network

图1. 车辆社交网络映射关系

对于任何车辆用户i和k来说，社会关系包括交互频次、每次交互的平均时间、社会距离以及兴趣等。为了更好的表述各车辆用户之间的社交关系，本文定义一个变量 ${\omega }_{i,k}$ 来表示车辆用户i和k之间的社会关系强度。但是，车辆用户之间的社会关系强度很难通过具体的手段进行测量，因此有必要对其中的权重系数进行量化。在衡量车辆用户社会关系强度时，用户间的交互次数以及每次交互的平均时间的影响最大。因此，本文以车辆用户间的交互次数和每次交互的平均时间来对社会关系强度进行量化。表达式如下所示：

${\omega }_{i,k}=\frac{1}{2}\cdot \frac{C_{i,k}}{{\displaystyle \sum C_i}}+\frac{1}{2}\cdot \frac{D_{i,k}}{{\displaystyle \sum D_i}}$ (1)

其中， $C_{i,k}$ 表示车辆用户i和k之间的交互次数， ${\displaystyle \sum C_i}$ 表示车辆用户i和其他车辆用户的交互总次数。 $D_{i,k}$ 表示车辆用户i和k每次交互的平均时间， ${\displaystyle \sum D_i}$ 表示车辆用户i和其他车辆用户每次交互的平均时间。假设eNB可以记录每个车辆用户的交互信息，并计算 ${\omega }_{i,k}$ 的值。假设通信网络中中继节点在对应不同的车辆D2D链路时具有不同的发射功率，且这个发射功率与D2D源端 $D2D\text{\_}{T}_i$ 和中继节点 $n_j$ 之间的社会关系强度密切相关。社会关系强度越高的中继节点可以触发中继节点更高的发射功率。则中继节点 $n_j$ 的发射功率与社会关系强度呈线性正相关，如下式所示：

$P_{n_j}=\left(\frac{1}{2}+{\omega }_{D2D_{T_i},n_j}\right)P_{bm}$ (2)

其中， ${\omega }_{D2D\text{\_}{T}_i,n_j}$ 表示车辆D2D用户发送端 $D2D\text{\_}{T}_i$ 和中继节点 $n_j$ 之间的社交关系强度， $P_{bm}$ 表示中继节点发射功率的基准。

2.2. D2D中继通信系统模型

D2D通信系统模型如图2所示。其中，eNB位于小区中央，小区半径为500 m。该模型采用正交频分复用(Orthogonal Frequency Division Multiplexing, OFDM)技术以减少小区内蜂窝用户(Cellular User, CUE)之间的干扰。此外，为了提升蜂窝系统的频谱资源利用率，本文让所有的车辆D2D链路都复用蜂窝资源的上行链路(Up Link, UL)。在小区内，随机分布有M对等待接入的车辆D2D用户以及N ( $M\le N$ )个空闲用户，小区内的所有空闲用户都可以作为潜在的中继用户。如图中所示，车辆用户在复用CUE的UL资源进行D2D中继通信时会受到来自CUE的干扰。根据文献 [13] [14]，在车辆D2D链路中小尺度信道衰落难以测量。因此，在本模型中，以大尺度衰落下自由空间中的路径损耗来表示通信网络中的信道增益。假设 $\left(x_C,y_C\right)$ 和 $\left(x_D,y_D\right)$ 分别表示任意两个在小区内终端设备的坐标，那么这两个终端设备之间的信道增益可以表示为：

$h_{C,D}={\left(\sqrt{{\left(x_C-x_D\right)}^2+{\left(y_C-y_D\right)}^2}\right)}^{-\alpha }={\left(d_{C,D}\right)}^{-\alpha }$ (3)

其中， $d_{C,D}$ 表示两个终端设备之间的距离， $\alpha$ 表示路径损耗指数。

在D2D中继通信系统模型中，假设一个车辆用户终端，也就是源端 $D2D\text{\_}{T}_i$，向eNB请求一个数据，另一个拥有该数据的车辆用户终端愿意通过D2D通信响应该源端的请求，被称为目的端 $D2D\text{\_}{R}_i$。但是，源端和目的端之间的距离可能过远或者信道条件很差。为了更好的传输数据，需要在源端和目的端之间选择一个空闲用户作为中继节点来辅助D2D通信。此外，多对D2D复用连接同一个CUE的时候会引起大量的同频干扰。为了减少这些不必要的同频干扰，本文规定小区内的蜂窝用户只能单独让最多一个D2D对进行复用。且由于小区内采用OFDM技术，所以CUE之间不存在相互干扰。假设小区内车辆D2D用户的源端、目的端以及空闲节点的位置信息都可以通过GPS获取。那么当D2D链路 $m_i$ 连接中继节点 $n_j$ 进行D2D通信时，信干躁比(Signal to Interference plus Noise Ratio, SINR)表达式如下所示：

$S_{D2D_{T_i},n_j}=\frac{P_{D2D_{T_i}}\cdot h_{D2D_{T_i},n_j}}{P_C{h}_{C,n_j}+N_0}$ (4)

$S_{n_j,D2D_{R_i}}=\frac{P_{n_j}\cdot h_{n_j,D2D_{R_i}}}{P_C{h}_{C,D2D_{R_i}}+N_0}$ (5)

其中， $N_0$ 表示通信链路的平均噪声功率， $h_{D2D\text{\_}{T}_i,n_j}$ 表示D2D链路 $m_i$ 的源端 $D2D\text{\_}{T}_i$ 到中继用户 $n_j$ 之间的信道增益， $h_{n_j,D2D\text{\_}{R}_i}$ 表示中继用户 $n_j$ 到D2D链路目的端 $D2D\text{\_}{R}_i$ 之间的信道增益， $h_{C,n_j}$ 表示CUE到中继节点之间的信道增益， $h_{C,D2D\text{\_}{R}_i}$ 表示CUE到D2D对接收端 $D2D\text{\_}{R}_i$ 之间的信道增益。 $P_{D2D\text{\_}{T}_i}$ 、 $P_{n_j}$ 、 $P_C$ 分别表示D2D链路 $m_i$ 的发送端 $D2D\text{\_}{T}_i$ 、中继用户 $n_j$ 和CUE的发射功率， $P_{n_j}$ 可以由式(2)得到。

Figure 2. Vehicle D2D relay communication system model

图2. 车辆D2D中继通信系统模型

车辆D2D通信系统连通性的高低通常用中断概率来衡量。因此，本文定义D2D通信的中断概率为瞬时信干躁比S小于规定阈值S_TH的概率。其表达式如下：

$P_{out}=P\left[S=\min \left\{S_{D2D_{T_i},n_j},S_{n_j,D2D_{R_i}}\right\}<S_{TH}\right]$ (6)

根据式(6)，当D2D链路进行通信时，只有瞬时信干躁比S大于或者等于S_TH才能正常通信。若不满足式该条件，则视为通信链路出现异常而处于中断状态。

3. 中继选择算法

3.1. 预筛选过程

本文的目的是在考虑物理传输距离和社会关系强度的前提下为每个车辆D2D对选择中断概率最小的中继节点以使得整体D2D网络的中断概率最小化，且本文只考虑单中继的选择。在整个小区范围内，由于作为潜在中继节点的空闲用户是随机分布的，因此在小区边缘位置或者远离D2D对的位置可能也会分布有若干空闲用户。在现实世界中，当D2D对选择这些距离比较远的空闲用户作为中继节点时，信号传输过程中遇到障碍物的可能性就越大，通信链路的中断概率也会增大。而且，若考虑这些远离D2D对用户的空闲用户，算法的探测次数也会增加，不利于算法的快速选择。因此，在算法的开始阶段有必要依据物理传输距离对小区内所有的空闲用户做出预筛选。预筛选的范围如图1所示，以车辆D2D对用户的源端和目的端的中心为圆心，并以源端和目的端的直线距离为直径作圆，位于该圆所覆盖区域内的中继节点即为满足车辆D2D对物理传输距离的节点。对于车辆D2D对用户 $m_i$，所有满足其物理传输距离约束的中继节点可以用集合 $R_{m_i}$ 表示，表达式如下：

$R_{m_i}=\left\{{\left(x_j-\frac{x_{R_i}+x_{T_i}}{2}\right)}^2+{\left(y_j-\frac{y_{R_i}+y_{T_i}}{2}\right)}^2\le {\left(\frac{d_{T_i,R_i}}{2}\right)}^2,\forall n_j\in N,\forall m_i\in M\right\}$ (7)

其中， $d_{T_i,R_i}$ 表示D2D对 $m_i$ 的源端和目的端之间的距离，且 $\left(x_{T_i},y_{T_i}\right)$ 和 $\left(x_{R_i},y_{R_i}\right)$ 分别表示该D2D对源端和目的端的坐标。 $\left(x_j,y_j\right)$ 表示小区内任意一个空闲中继节点 $n_j$ 的坐标。

在车辆D2D中继通信系统中，不仅要考虑D2D用户和中继用户之间的物理传输距离约束，还要考虑D2D用户和中继用户之间的社交关系强度。因此，在得到经过物理距离筛选后的中继集合 $R_{m_i}$ 后，还要对其进行社交关系强度的筛选。在这个过程中，我们采用设置社交关系强度阈值 ${\omega }_{TH}$ 来对 $R_{m_i}$ 中的中继节点进行筛选。对于D2D对用户 $m_i$，若源端 $D2D\text{\_}{T}_i$ 和中继用户 $n_j$ 之间的社交关系强度 ${\omega }_{i,j}$ 大于或者等于 ${\omega }_{TH}$，则在中继集合中保留该中继节点；相反，若 ${\omega }_{i,j}$ 小于 ${\omega }_{TH}$，则在中继集合中删除掉该中继节点。社交关系强度阈值表达式如下所示：

${\omega }_{TH}=\theta \cdot \frac{{{\displaystyle \sum }}_{n_j=1}^{N_i}{\omega }_{m_i,n_j}}{N_i}$ (8)

其中， $N_i$ 表示集合 $R_{m_i}$ 中中继节点的数量， $\theta$ 用来控制社交关系强度阈值 ${\omega }_{TH}$ 的大小。

对于车辆D2D对用户 $m_i$，经过物理传输距离筛选和社交关系强度筛选之后，适合作为该D2D链路的中继节点的集合用 ${R^{\prime }}_{m_i}$ 表示。

与社交关系强度阈值 ${\omega }_{TH}$ 的定义类似，本文定义各D2D中继通信链路的瞬时信干躁比阈值S_TH为该链路遍历备选中继集合中所有中继节点的平均信干躁比：

$S_{TH}=\delta \cdot \frac{{{\displaystyle \sum }}_{n_j=1}^{{N^{\prime }}_i}\min \left\{S_{D2D_{T_i},n_j},S_{n_j,D2D_{R_i}}\right\}}{{N^{\prime }}_i}$ (9)

其中， ${N^{\prime }}_i$ 表示备选中继集合 ${R^{\prime }}_{m_i}$ 中中继节点的数量， $\delta$ 用来控制信干躁比阈值S_TH的大小。

3.2. 中继选择过程

在对小区中空闲用户进行预筛选过程之后，每一对车辆D2D用户都得到一个属于自己的备选中继节点集合，本文在中继节点的选择上采取贪心策略以局部最优化求得全局最优化。为了尽可能的使所有的D2D对都能选择到中继节点，基于备选中继集合 ${R^{\prime }}_{m_i}$ 的大小升序排序得到D2D对的选择优先顺序，优先权高的D2D对用户可以优先选择自己的中继节点。即优先为备选中继数量较少的D2D对分配中继节点，这样可以避免那些备选中继较少的D2D对最后无中继节点可用。当第一个D2D对在自己的备选中继集合中选择中继节点时，选取瞬时信干躁比S最大的空闲用户作为自己的中继节点进行D2D通信，以此来选择局部的最优中继节点。因为瞬时信干躁比最大的中继节点对于该D2D链路来说最容易满足式(6)，即中断概率最小。并在其余D2D对的备选中继集合中删去该中继节点。然后第二个D2D对在自己的备选中继集合中继续以该策略进行中继的选择，以此类推，直到所有的D2D对都选择到属于自己的中继节点。此外，若D2D对在选择中继节点的过程中出现两个或两个以上的中继节点的S大小相等，则选择社交关系强度高的那个作为中继节点进行D2D通信。

基于社交网络结合贪心策略的车辆D2D通信中继选择算法伪代码如表1所示。

Table 1. Vehicle D2D relay selection algorithm

表1. 车辆D2D中继选择算法

4. 仿真结果及分析

在本节中，使用matlab仿真软件对第3节中所提出的算法进行仿真分析。仿真模型采用第2节中所建立的车辆D2D中继通信系统模型，单蜂窝小区的拓扑仿真模拟图如图3所示。仿真过程中所使用的各项参数如表2所示。为了不失一般性，整个仿真过程进行10,000次随机模拟。为了衡量本文所提出中继选择算法在中断概率方面的性能，本文与已有研究中的随机中继选择算法(RRS) [15]、最优停止选择算法(SSOS) [16] 以及最短距离中继选择算法(SDRS)进行了对比仿真。RRS算法在没有考虑通信链路信干躁比大小的前提下，在所有潜在中继节点中随机选取一个作为中继节点，SSOS算法利用最优停止理论进行中继节点的选择，SDRS算法选择距离车辆D2D发送端最近的节点作为中继节点。

Figure 3. System model simulation diagram

图3. 系统模型仿真图

Table 2. Simulation parameter setting

表2. 仿真参数设置

图4展示了在不同的社交关系强度阈值下，本文所提出的算法随着中继节点数量不断增加所需要的平均探测次数。可以看出，在社交关系强度阈值一定的条件下，随着中继节点数量的增加，系统需要探测的中继节点数量随之增加。主要是因为随着小区范围内随机中继节点数量的增加，每个车辆D2D对的备选中继集合中的中继节点数量也会增加，为了选择出最合适的中继节点，本文所提出的算法需要将备选中继集合中的节点全部探测一遍。从图中还可以看出在中继节点数量一定的时候，随着社交关系强度阈值的增加，需要探测的平均次数会有所降低。主要原因在于，随着社交关系强度阈值的提高，在预筛选过程中会筛除掉更多的空闲节点，在每个车辆D2D对的备选中继集合中的中继节点数量会减少。这在一定程度上加快了算法的执行过程，有利于中继节点的快速选择。

Figure 4. Average probing numbers with different number of relay nodes

图4. 不同中继节点数量下平均探测次数

图5所示为在社交关系强度阈值 $\theta =0.5$ 的情况下，本文所提出的算法在不同中节点数量下所对应的中断概率，其中每条曲线对应了不同的信干躁比阈值。从图中可以看出，在信干躁比阈值一定的情况下，系统的中断概率随着中继节点数量的增加而降低。这说明中继节点数量越多，车辆D2D用户选择到满足连通性的中继节点的概率越高。但并不是中继节点数量越多越好，因为从图4可以看出随着中继节点数量的增多，系统的探测次数也会提高，这会增加算法计算的复杂度以及系统的调度成本。此外，在小区内中继节点数量一定的情况下，系统的中断概率随着信干躁比阈值的增大而增大。这是因为随着信干躁比阈值的增大，即系统判定通信链路中断的条件越严苛，备选中继集合内能够满足连通性的中继节点数量将会越少，则系统的中断概率会增加。综合图4和图5的仿真结果可知，本文所提算法在潜在中继节点数量为100个左右时可以达到平均探测次数和中断概率的折中。

Figure 5. Outage probability with different number of relay nodes

图5. 不同中继节数量下的中断概率

Figure 6. Average outage probability of each algorithm with different number of relay nodes

图6. 不同中继节数量下各个算法的平均中断概率

图6展示了各个算法在不同中继节点数量下的中断概率。从图中可以直观的看出，在小区内潜在中继节点数量一定的情况下，本文所提算法在中断概率方面的性能要优于SSOS、SDRS以及RRS算法。由于RRS没有考虑系统的中断概率性能而随机在通信范围内选取中继节点，因此在中断概率方面的表现最差。相对于SDRS算法，本文不仅考虑了车辆D2D对源端到中继节点之间的信干躁比，还考虑了中继节点到目的端之间的信干躁比，并在二者之间选择了较小的一个作为通信链路是否中断的依据，因此表现要比SDRS算法好。对于SSOS算法而言，本文所提出的算法是在完全探测备选中继集合之后选择了表现最好的节点作为中继节点，因此在中断概率方面的性能要优于SSOS算法。

5. 总结

为了有效降低车辆D2D中继通信系统的中断概率，提升通信网络的连通性，本文提出了一种基于社交网络结合贪心策略的车辆D2D通信中继选择算法。该算法首先通过物理传输距离和社交关系强度阈值进行预筛选过程，筛除掉那些距离较远和社交关系强度较低的中继节点，使每对车辆D2D对形成自己的备选中继集合，从而有效的降低中继节点的平均探测次数。然后根据备选中继集合的大小对车辆D2D对进行中继选择优先权的排序，备选中继集合小的车辆D2D对具有优先选择中继节点的权利，以保证尽可能多的车辆D2D对都能够选择到中继节点。最后结合贪心策略进行中继节点的选择，每个车辆D2D对都选择最优的节点进行D2D中继通信，以局部最优化推得全局最优化。仿真结果表明，本文所提出的中继选择算法与其他算法相比在中断概率方面具有更好的表现。但目前的研究仅考虑了单跳中继的选择，在后续的研究中将会进行多跳中继选择算法的研究。