HAI Han(海 涵)， QIAN Hongzhi(钱鸿志)， FENG Hongzhan(冯泓崭)， YU Jinming(郁进明)

College of Information Science and Technology, Donghua University, Shanghai 201620, China

Abstract: To improve the connectivity of device-to-device(D2D) communication between delay-assisted vehicles, a multi-hop D2D relay selection strategy based on outage probability is proposed. The algorithm firstly clusters the relay users based on the distance of D2D users, and determines the number of one-hop relay nodes through the outage probability threshold. Two-hop relay nodes directly select the same number of relays as one-hop relay nodes according to the descending order of signal noise ratio(SNR) to establish a square matrix. The Hungarian algorithm is used to assign the relay nodes of two clusters to complete the inter relay communication. Finally, the information is sent to the D2D receiver by combining technology. The simulation results show that this algorithm can reduce the cost of relay probing process and the outage probability of system in multi-hop D2D relay communication.

Key words: multi-hop device-to-device (D2D) ; vehicle communication; relay selection; Hungarian algorithm

Introduction

With the popularization of voice navigation, vehicle entertainment system, driving assistance technology and other real-time vehicle applications, new requirements have been put forward on vehicle communication. Vehicle-to-vehicle (V2V) communication can make direct interaction between vehicles and reduce the cost of network transmission, which has become one of the research hotspots of vehicle communication[1]. With the advent of 5G mobile communication network era, the performance features of the high data transfer rate, low latency and low power consumption will continuously improve the user experience[2]. As an important technology of 5G network, device-to-device(D2D) communication can improve network capacity by reusing cellular network resources, which plays a positive role in reducing base station (BS) load and improving spectrum resource utilization[3-4].

When effective direct communication is not allowed between vehicle D2D users with long distance or poor link quality, relay-assisted D2D communication can improve the communication quality[5]. In Ref. [6], the author proposed a multi-metric quality of service balancing relay selection algorithm in vehicle-to-everything (V2X) network, which improved the packet dropping rate of the system by comprehensively considering the link stability, channel capacity and end-to-end delay. Zhouetal.[7]proposed an auction-matching based joint relay selection and spectrum allocation algorithm in the two-hop relay transmission mode to maximize the total spectrum efficiency in the vehicle network. In the 5G vehicular communication, Zhangetal.[8]proposed a centralized hierarchical deep reinforcement learning to solve the problem of multi-hop D2D relay selection and power distribution, so as to effectively reduce the additional coordination cost of the system. Songetal.[9]provided a relay selection scheme based on unsupervised learning to help BS automatically select relay nodes based onK-means algorithm. In vehicle D2D communication system, vehicle mobility leads to rapid change of network topology structure, and relay-assisted multi-hop D2D communication has higher flexibility. However, how to reduce the outage probability of the system is still the focus of the research.

In this paper, we study the vehicle multi-hop D2D relay selection from the perspective of connectivity. By clustering the potential relay nodes between D2D user pairs, proposes a multi-hop D2D relay selection algorithm based on connectivity, which is referred to as BCRS. First, we analyze the outage probability of the sender in D2D one-hop relay communication in detail. Then we obtain the node selection in the one-hop relay cluster based on the outage probability threshold. For the selection in the two-hop relay cluster, in order to select the relay nodes with better signal noise ratio (SNR) and the same number of one-hop relay nodes, the nodes in the cluster are sorted in descending order by SNR, and then Hungarian algorithm is used to complete optimal 0-1 assignment, so as to complete the communication between the relay clusters. The main contribution of this paper is to improve the connectivity of multi-hop D2D communication system by relay screening based on outage probability, and to complete the assignment problem between relay clusters by maximizing the strength of social relationship, which can further improve the communication quality and security.

1 System Model

In this paper, D2D communication between two vehicles in a single cell is considered, and a three-hop D2D communication scenario is taken as an example for modeling, as shown in Fig. 1. The system model includes a BS, a vehicle D2D transmitting node D2D_t1, a vehicle D2D receiving node D2D_r1, and a large number of potential relay user nodes distributed randomly. The BS obtains the communication distance by obtaining the location information of D2D user pairs. Combined with the maximum distancedmaxof direct D2D communication, the relay between D2D user pairs is divided into two clusters (A and B). It is assumed that the number of potential relay nodes in both clusters A and B isx.And in the three-hop D2D relay communication, the distance between D2D_t1 and cluster A relay is not more thandmax.Similarly, the distance from cluster A relay to cluster B relay and the distance from cluster B relay to D2D_r1 are not more thandmax.In addition, we stipulate that the communication link from D2D_t1 to cluster A relay and the communication link from cluster B relay to D2D_r1 use the same spectrum resource, and another spectrum resource is used between cluster A relay and cluster B relay to avoid the mutual interference between transmission hops. This section also makes the following assumptions.

Fig. 1 Multi-hop D2D relay communication system model

(1) When D2D initiates a communication request, all relay nodes will be in a static state to avoid the influence of relay user mobility on the system model.

(2) Orthogonal frequency division multiplexing (OFDM) is adopted, and the interference to D2D user is ignored when the relay user performs traditional cellular communication.

(3) The data transmission mode between two-hop relays is decode-and-forward (DF), and the receiving node use the maximum ratio combining technology to merge the multi-channel relay signals, without considering outage probability in the last hop signal merging process.

1.1 Channel model

In a single cell, considering the path loss model based on the communication distance, the channel gain from the transmitting node D2D_t1 to the cluster A relay nodeaican be expressed as

(1)

wheredD2D_t1, airepresents the distance between the transmitting node D2D_t1 and the relay nodeai, andαrepresents the path loss coefficient. Similarly, the channel gain from cluster A relay nodeaito cluster B relay nodebican be expressed as

(2)

The channel gain from cluster B relay nodebito receiving nodeD2D_r1 can be expressed as

(3)

Therefore, when the transmitting nodeD2D_t1 sends signals with the powerPtto establish one-hop relay communication request, the received power of the cluster A relay nodeaican be obtained according to Eq. (1), as

PD2D_t1, ai=PtGD2D_t1, ai.

(4)

Similarly, when a cluster A relay nodeaiadopts the DF strategy to send a signal to a cluster B relay nodebi, the received power of the cluster B relay nodeycan be obtained according to Eq. (2) and Eq. (4), as

Pai, bi=PD2D_t1, aiGai, bi.

(5)

When the cluster B relay nodebisends a signal to the receiving node D2D_r1, the received power of the receiving node D2D_r1 can be obtained according to Eqs. (3) and (5), which can be expressed as

Pbi, D2D_r1=Pai, biGbi, D2D_r1.

(6)

At this time, the SNR at the relay nodeaiof cluster A can be expressed as

(7)

whereγrefers to SNR, andN0is the white gaussian noise power. The SNR at cluster B relay nodebican be expressed as

(8)

Based on the above analysis, it can be concluded that the information transmission rate between a cluster A relay nodeaiand a cluster B relay nodebican be written as

νai, bi=B·log2(1+min(γai,γbi)).

(9)

1.2 Social network model

Social network is a complex network reflecting a series of features of users, such as daily social status, personal interest, behavioral trajectory and interpersonal relationship, and it is one of the important dimensions in communication system design. With the rapid development of online social networking platforms and mobile intelligent devices, social relations participate in the vehicle network and gradually form the vehicle social network[10-11]. More and more people participate in social interactions actively, and provide massive data for social relationships. These massive data provide great convenience to analyze users’ mobile behavior characteristics and social relationships. When there are social relations between users, on the one hand, the maintainability and periodicity of social relationship make the structure of users’ social networks stable relatively. On the other hand, a node with a social relationship is more likely to be willing to act as a relay for data forwarding than other ordinary nodes. Therefore, the introduction of social network into the vehicle D2D communication system is of great significance to the reliability of data transmission and the improvement of user experience. The strength of social relationships can be measured[12]by comprehensively reflecting the interest similarity between users through the interactive frequency and the number of common friends on the vehicle software, which can be expressed as

(10)

where vectorIirepresents the useri’s interest table for things, and vectorIjrepresents the userj’s interest table for the same things.

1.3 D2D outage probability model

In spatial diversity technology, single-input multiple-output (SIMO) uses single-antenna transmission and multi-antenna reception for the same signal, and the processed multichannel received signals are superposed to overcome fading effect[13], it improves SNR to achieve the purpose of improving performance. SIMO is widely used in the relay-assisted D2D communication system. In this paper, when D2D communication request is initiated between vehicle users, transmitting node D2D_t1 uses SIMO to send data information to several relay nodes in cluster A for DF, which can maximize the broadcast nature of the source node’s transmission process. Therefore, how to select suitable nodes among the large number of relay nodes in cluster A for data receiving and forwarding is crucial to improving transmission reliability.

The connectivity of D2D communication system is usually reflected by outage probability, which is defined as the probability that the instantaneous SNRris less than the specified thresholdrth, which can be expressed as

Pout=P(rrth),

(11)

when D2D carries out data transmission, according to Eq. (11), only when the instantaneous SNRris higher thanrth, the transmitted signal can be received normally. Otherwise, the transmitted signal will be in the interrupt state due to abnormal reception. Then, when transmitting node D2D_t1 establishes one-hop D2D connection with relay nodeaiin cluster A, the node outage probability is expressed

(PD2D_t1, ai)out=P(γairth).

(12)

According to Eq. (11), the outage probability of the relay node in cluster B is expressed as

(Pai, bj)out=P[min(γbj)rth].

(13)

In the system model, it has been assumed that the outage probability sent to receiving nodeD2D_r1 is not considered. Then the outage probability of the whole three-hop D2D relay communication can be expressed as

(Psys)out=max((PD2D_t1, ai)out,(Pai, bj)out).

(14)

The purpose of this paper is to reduce the outage probability of D2D system, which can be expressed as

min((Psys)out)=

min{max[(PD2D_t1, ai)out,(Pai, bj)out]}.

(15)

2 Multi-Hop D2D Relay Selection Algorithm

For the solution of problem Eq. (15), a relay selection algorithm based on the interrupt probability is proposed to solve the problem of reducing the outage probability of multi-hop D2D communication. The core of BCRS algorithm is to quickly determine the candidate nodes in the relay cluster to reduce the outage probability and improve the system connectivity and communication speed. Firstly, the selection of relay nodes in relay cluster A is discussed. On the one hand, due to the large number of nodes in the cluster, its received SNR is determined by the lowest node in the cluster. However, we do not need each node as a relay user for data transmission. On the other hand, the more relay nodes are selected, the higher the outage probability of the system affected by channel quality and other conditions. Therefore, we assume that the average rate obtained by the source node traversing all relay nodes in cluster A is (vD2D_t1, ai)avg.according to Shannon formula, there is an equivalent SNRγavg.Useγavgas the threshold value of node selection in one-hop D2D communication relay cluster. When one-hop node satisfiesγavgγai, it is used as a relay for resource transmission. In this case, the outage probability of the node is expressed as

(PD2D_t1, ai)out=P(γavgrth).

(16)

To sum up, through the screening of SNR threshold valueγavg,wrelays in cluster A are selected, wherew

We assume thatwrelay nodes are selected in cluster A form setΑ=[a1,a2,...,aw], and cluster B selects the firstwrelay nodes from large to small according to SNR to form setB=[b1,b2,...,bw].In the three-hop D2D relay communication scenario, a relay in cluster A only forwards data to a relay node in cluster B, and a relay node in cluster B only receives the forwarding data of a relay node in cluster A, so as to avoid interference. And no data are forwarded between relays within the same cluster. In this way, the relay nodes of cluster A and cluster B can be modeled as bipartite graphG, as shown in Fig. 2.

Fig. 2 Bipartite graph Gof relay clusters A and B

For the relay communication path selection between cluster A and cluster B, we will assign the bipartite graphGaccording to the strength of the social relationship to maximize the social relationship strength of the system and improve the communication quality among relays. According to the social relationship strength model in section 1.2, assume thatθaibj, wherei∈[1,w],j∈[1,w], represents the social relationship strength value of cluster A relay nodeaiand cluster B relay nodebjrespectively. Then, the strength of social relationship between relay nodes in cluster A and cluster B can be expressed in Table 1. Based on this, aw×wmatrixZ=(ai,bj) is established, wherei,j=1, 2,...,w.The problem of maximizing the social relationship strength of the system can be expressed as

Table 1 Strength of relay social relationship between cluster A and cluster B

(17)

The constraint conditions are shown in Eqs. (18)-(20).

(18)

When a relay in cluster A only forwards data to a relay node in cluster B, the following formula can be obtained as

(19)

When a relay node in cluster B only receives forwarding data from one relay node in cluster A, it can be concluded as

(20)

For the solution of problem Eq. (17), the Hungarian algorithm is used to transform the matrixZ=(ai,bj).The less selective one makes the first choice in this process obtain the optimal assignment to maximize the strength of the system’s social relationship, so as to realize the communication path selection between three-hop D2D relay clusters A and B. The transmission information ofwrelays in relay cluster B is forwarded to the receiving node D2D_r1 by maximum ratio merging technology to complete the whole multi-hop D2D relay communication.

The complexity of the BCRS algorithm mainly depends on the cluster A relay node screening and the Hungarian algorithm relay matching for clusters A and B, ignoring the complexity of SNR descending sorting for cluster B relay nodes and the complexity of obtaining the social relationship. In the filtering of relay nodes in cluster A, the instantaneous SNRγaiof each node in the cluster need to be compared withγavg. Considering that there arexpotential relay users in cluster A, the complexity isO(x).The complexity of relay node allocation between cluster A and cluster B based on Hungarian algorithm isO(V·E).Therefore, the overall complexity of BCRS algorithm isO(x+V·E).

3 Simulation Results

In order to better reflect the performance of the proposed algorithm, this section simulates and compares the performance of multi-hop relay selection algorithms such as BCRS algorithm and random relay selection algorithm, and makes a more detailed analysis of the results. Random relay selection algorithm is to randomly select a relay node in the cluster for communication. The relay node is used if it meets the requirement of outage probability. Otherwise, a relay will be selected again until it meets the requirement of outage probability. The relay selection algorithm based on SNR selects one node with the lowest SNR in each cluster until it meets the outage probability requirement. The relay selection algorithm based on the optimal speed[14]is to maximize the communication speed of the system.

In the scene simulation through MATLAB, we consider a circular cell system with a radius of 500 m. There is a BS in the system to obtain the SNR of relay nodes and the strength of social relations between relay nodes to schedule resources. Simulation parameters are listed in Table 2.

Table 2 Simulation parameters

Figure 3 compares the outage probabilities of one-hop and two-hop in D2D communication when the number of relays in the clusterx=50.Abscissa is thresholdrthand ordinate is outage probability. It can be seen from Fig. 3 that the outage probabilities of one-hop and two-hop in D2D communication decrease with the increase ofrth, and the outage probability of two-hop is always greater than that of one-hop. This is because the largerrthis, the larger the SNR of relay nodes screened byrthin one-hop of BCRS algorithm, so the outage probability of the system is lower. From the communication process of the system, the two-hop communication is determined by the two-hop links from D2D source node to cluster A relay node and the relay node of cluster A to the relay node of cluster B. In other words, the outage probability of two-hop communication is always affected by the outage probability of one-hop.

Fig. 3 Outage probability of one-hop and two-hop in D2D communication

Figure 4 shows the variation of D2D outage probability with thresholdrthunder different relay numbers in the cluster. It can be seen that the outage probability of the system decreases gradually with the increase of SNR thresholdrthunder the premise that the number of relay nodes remains unchanged, which has been illustrated in Fig. 3. It can also be seen from Fig. 4 that for the same condition, the outage probability decreases with the increase of the number of relay nodes in the cluster. However, this can only show that the selectivity will increase as the number of relay nodes increase, but it does not mean that the more relay nodes in the cluster lead to a better result. Because the complexity of the BS for relay SNR sorting, and the cost of interference management and scheduling will also increase when the number of relay nodes increase.

Fig. 4 Outage probability of different relay numbers

Figure 5 shows the cumulative distribution function of D2D transmission rate of different algorithms. It is stipulated thatrth=10, the maximum transmission power of D2D source node isPt=24 dBm, and the maximum communication distance between D2D user pairs isdmax=100.It can be seen from Fig. 5 that compared with the random relay selection algorithm, the relay selection algorithm based on SNR is an improvement on the random relay selection algorithm, and its transmission rate performance is better than the random relay selection algorithm. Compared with the relay selection algorithm based on SNR, the BCRS algorithm and the relay selection algorithm based on the optimal speed find the relay nodes with higher SNR to communicate in the cluster, so the transmission rate performance is better.

Fig. 5 Comparison the transmission rate of different algorithms

In order to further illustrate the performance of BCRS algorithm, based on Fig. 5, a comparison of average numbers of one-hop probing of different algorithms is presented in Fig. 6, wherex=10, 20, 30, 40, 50 andrth=10.It can be seen from Fig. 6 that with the increase of the number of relay nodes, the number of one-hop relay probing of each algorithm is shown as follows: random relay selection>relay selection based on SNR>relay selection based on optimal speed>BCRS algorithm. Based on the optimal speed and BCRS algorithm, the number of probing is significantly lower than that of the other two algorithms due to the selection of SNR threshold. The proposed BCRS algorithm has less probing times than the speed optimal relay selection algorithm. The reason is that BCRS algorithm carries out data transmission after SNR threshold filtering directly, and the optimal speed relay selection algorithm tries to reduce the number of relay nodes to reach the goal of optimal speed, so the number of relay probing is more than that of BCRS algorithm.

Fig. 6 Average numbers of one-hop probing

Fig. 7 Outage probability of different D2D maximum distance constraint

Figure 7 compares the performance of D2D outage probability under different algorithms by changing the maximum distance constraint of D2D receiver and transmitter. It can be seen that the greater the maximum distance constraint of D2D receiver and transmitter is, the longer the transmission distance is, the greater the path loss will be, the transmission speed and quality of signal will be affected, and the outage probability of the system will also increase. The BCRS algorithm can effectively reduce the outage probability because it combines the maximum distance constraint of D2D for relay clustering and relay screening based on SNR. Moreover, the Hungarian algorithm based on social relationship is used for 0-1 assignment between relay clusters A and B, which also improves the communication quality of D2D and improves the system connectivity, so its outage probability is smaller than other three algorithms.

4 Conclusions

In this paper, we proposed outage probability-based relay selection strategy for multi-hop D2D in vehicle communication, and described how to construct a bipartite graph based on the SNR and the candidate relay set of clusters A and B. And we set the weight of the edge to the strength of the social relationship, then used the Hungarian algorithm to perform the relay selection of each cluster to reduce the complexity of relay selection. The simulation results showed that the proposed algorithm can reduce the interrupt probability in the multi-hop relay selection process.