Congestion dispersion in device-to-device discovery for proximity-based services

Abstract

Proximity service (ProSe) enables the development of various applications that exploit proximity of the mobile devices. In ProSe, devices are expected to communicate with each other on device-to-device (D2D) links and make use of proximity information for the provision of a variety of services. An essential functionality in ProSe is the ability of a device to identify its neighbors. This process is referred to as D2D discovery. This paper investigates distributed D2D discovery based on greedy resource selection. In order to facilitate rapid and efficient distributed D2D discovery, we propose group-based peer discovery resource selection range restriction (GPSRR) scheme. GPSRR scheme disperses the devices concentrated at a certain discovery resource over multiple resources. This is done by limiting the resource selection of a device to a specified group of resources. We also propose group reselection (GR) scheme to resolve the unbalance of congestion among different groups of resources. Simulation results show that the proposed schemes can improve the speed of discovery and the number of discovered devices, especially in densely populated environments.

1 Introduction

The prevailing development trends in mobile communication systems mainly focus on improving parameters like system capacity, communication performance, and cost efficiency. Consequently, most of the studies as well as the standardization efforts are inclined towards developing performance-enhancing techniques such as carrier aggregation, multiple input multiple output (MIMO), small cell, etc. [1–3]. With the help of these techniques, 3GPP LTE-Advanced is expected to achieve up to 3- and 1.5-Gbps peak data rates on downlink and uplink transmissions, respectively [4]. With massive improvements in the overall system capacity and performance, the research focus has now shifted towards exploring new types of services.

Proximity service (ProSe) being developed by 3GPP is a good example of new capabilities that are envisaged for the next-generation mobile communication systems [5]. In addition to enabling communications between user equipments (UEs), ProSe allows the identification of UEs in close proximity. It also enables discovery of the specific applications running on adjacent UEs. These features allow the use of ProSe for enabling commercial/social networking, offloading regional traffic from legacy infrastructure, enhancing performance, extending the coverage of cellular networks, and so on.

New communication and discovery protocols to support ProSe are being considered in the standardization of next-generation mobile communication system [5]. In the current cellular systems, user plane data path between two communicating UEs is set up via the operating network even though the UEs are in close proximity. It is obvious that this setup causes unnecessary delay for UEs and additional overhead for the operating network. Therefore, device-to-device (D2D) communication is also being considered to realize ProSe. As the name indicates, D2D communication enables adjacent UEs to communicate directly without relaying their data through the operating network.

The first step in allowing communication between adjacent UEs is neighbor discovery. The so-called D2D discovery enables UEs to discover the existence of neighboring UEs, determine their identification, and the applications being executed. Determining the proximity of a UE is also a part of D2D discovery process. Determining proximity, however, requires UEs to perform direct signaling with other UEs. For this purpose, D2D discovery protocols that define how UEs exchange discovery messages should be investigated. For D2D discovery, centralized as well as distributed modes of operation can be used. In the centralized approach, a centralized controller (such as eNB) will coordinate transmissions and receptions of the discovery messages for all UEs. While the centralized approach may result in improved performance, it may degrade the performance of the controller and the access networks due to signaling overheads for the centralized control. Additionally, since the centralized control is possible within cell coverages of eNBs, it cannot be used for the environments where eNB is not available [5]. Due to these reasons, distributed discovery control allowing each UE to autonomously perform transmission and reception of discovery messages is preferred.

Most of the previous works related with discovery focus on ad hoc networks [6–9]. Since discovery in such schemes is performed as a part of routing mechanism in the IP layer, they may not be suitable for D2D discovery in mobile communication systems [5]. In [10], Baccelli et al. introduce a distributed D2D discovery protocol based on greedy discovery resource selection. In this protocol, each UE observes discovery resources during a period, selects a discovery resource that has least energy in a greedy manner, and finally uses that resource for discovery message broadcasting in the following discovery period. Since the protocol considers OFDM resource structure, it can be easily implemented in OFDM-based mobile communication systems, e.g., LTE and mobile WiMAX. However, in the environments that host dense UE deployments, the greedy manner of resource selection may congest the discovery message broadcasting in a few preferred resources. The congestion caused by greedy resource selection limits the overall performance of the distributed D2D discovery. For example, the parameters like the number of discoverable UEs and the time required for successful discovery resource acquisition may get adversely affected.

In order to alleviate the problem caused by greedy discovery resource selection in the environments with dense UE deployments, dispersion of the congestion over multiple resources may be required. The dispersion shall enable each UE to quickly discover more UEs by reducing the interference among discovery messages. For the purpose, this paper proposes group-based peer discovery resource (PDR) selection range restriction (GPSRR) scheme. GPSRR scheme divides the available resources into several groups and makes each UE entering D2D discovery to select one group of resources. Each UE is allowed to select resources from one group only. In addition to GPSRR scheme, this paper also proposes group reselection (GR) scheme to avoid unbalance of congestion in different groups of resources. GR scheme helps UEs experiencing excessive collisions in the congested groups to reselect less congested groups.

The rest of this paper is organized as follows. The next section introduces previously studied discovery resource structure and distributed D2D discovery protocol. New schemes for congestion dispersion are proposed in Section 3, and their performance is evaluated in Section 4. This paper is concluded in Section 5.

2 Preliminaries

2.1 OFDM-based resource structure for D2D discovery

It follows from our earlier discussion that there are at least three important design considerations related to D2D discovery process. Firstly, D2D discovery is considered as a preceding step of the link establishment procedure which finally allows UEs to directly exchange data [9]. Note that D2D discovery shall be performed without explicit link establishment. Secondly, due to the massive increase in the number of mobile devices, UEs should be able to discover each other simultaneously even in the densely populated regions. Finally, the resource structure for D2D discovery should be compatible with that used in the legacy mobile communication systems. In order to maintain compatibility, the resource structure of D2D discovery based on orthogonal frequency division multiplexing (OFDM) is considered. Figure 1 shows an example of the resource structure in 3GPP LTE system where 10-MHz bandwidth is assigned for uplink [11]. One discovery period on the physical uplink shared channel (PUSCH) has 44 subchannels (n _f = 44) and 64 subframes (n _t = 64). The discovery period is repeated at 10-s interval in PUSCH so that UEs may adapt to the changes in topology.

Fig. 1

An example of discovery resource structure in 3GPP LTE system with 10 MHz uplink bandwidth

The basic unit of the discovery resource within one discovery period is referred to as peer discovery resource (PDR). A PDR contains two physical resource blocks (PRBs) that occupy one subchannel on one subframe in 3GPP evolved-UMTS terrestrial radio access (E-UTRAN) [12]. The numeric value marked in each PDR is used as the indexing number to represent the location of the PDR in each discovery period (see Fig. 1). Each UE uses a PDR to broadcast its discovery message which may include information on its identification and applications. PRBs in PUSCH are allocated by eNB of each cell for D2D discovery. Moreover, since UE uses one PDR occupying only one subchannel, the discovery message can be transmitted with higher power spectral density (W/Hz). Thus, the signal shall propagate farther compared with the signal transmitted through multiple subchannels. Ideally, a discovery period consisting of 2816 PDRs (N _PDR = n _f×n _t = 44 ×64) enables a maximum of 2816 UEs to simultaneously transmit interference-free discovery messages in the same region.

2.2 Distributed D2D discovery protocol

The distributed D2D discovery protocol that complies with the OFDM-based resource structure (Fig. 1) has been proposed by Baccelli et al. [10]. The protocol defines how each UE acquires a PDR in each discovery period and distributively broadcasts discovery message through that PDR. The protocol assumes that all UEs are synchronized by the help of other systems such as cellular networks.

The distributed D2D discovery protocol consists of three types of operations: PDR selection, discovery message broadcasting and receiving, and PDR reselection. In PDR selection, UE acquires a PDR according to a certain PDR selection strategy. A random PDR selection strategy that allows UEs to randomly choose a PDR among [1, N _PDR] with uniform distribution can be considered. However, since this scheme does not consider the prevailing occupation of PDRs, it is likely that several UEs acquire the same PDR and interfere with each other. For efficient PDR selection, Baccelli et al. in [10] introduce a greedy PDR selection scheme. Greedy PDR selection scheme intends to enable spatial reuse of each PDR. Every UE willing to participate in the discovery process first measures the energy at each PDR in a discovery period. It then randomly selects one PDR out of 5 % of the PDRs that contain lower energy in comparison with others.

In the discovery message broadcasting and receiving phase, UE that has selected a PDR broadcasts discovery message in each discovery period through that PDR. It discovers other UEs by observing the rest of the PDRs. It also measures energy received through each PDR for possible PDR reselection. If more than one UE in close proximity occupy the same PDR, collision may take place. In order to determine whether its broadcast discovery message has faced collision, each broadcasting UE measures the energy received through a subchannel during an arbitrary OFDM symbol in its current PDR. The UE considers that a collision has taken place if the measured energy level is greater than fifth percentile of the measured energy levels of all PDRs in the same discovery period. The UE that detects collision of its discovery message broadcasting performs PDR reselection. In PDR reselection, UE reselects a new PDR in the next discovery period according to the aforementioned PDR selection scheme.

3 Group-based congestion dispersion for D2D discovery

3.1 Motivation

In mobile communication systems, it is possible that a large number of mobile UEs enter and/or leave a region during a discovery period. In this case, a bulk of UEs may simultaneously have to perform PDR selection within the same discovery period. In this case, UEs that are located close to each other may observe similar received energy in each PDR. Recall that in greedy PDR selection, each UE selects a PDR from 5 % of N _PDR PDRs that contain lower energy in comparison with others. If a large number of UEs simultaneously select PDRs from the same 5 % of N _PDR PDRs, the PDRs shall get considerably congested. All UEs experiencing congestion perform PDR reselection in the following discovery period. Thus, it is likely that congestion gets worse in the following discovery period because, in addition to the UEs newly entering the region, the UEs performing PDR reselection also contend for PDR acquisition. Therefore, congestion degrades not only the performance of discovery in those PDRs but also reduces the utilization of other unselected PDRs.

The adjustment of percentage for greedy PDR selection, e.g., increasing it from 5 to 10 %, may help in alleviating the congestion problem. However, it is difficult to be realized in a distributed D2D discovery protocol due to the following reasons. Firstly, the optimal value of percentage is difficult to determine since the communication environment varies almost unpredictably. Parameters like channel fading, UEs mobility, participation and withdrawal of UEs in discovery, etc., all vary in different setups. Secondly, during distributed D2D discovery, it is impossible for the UEs to share the same value of percentage. This is because there is no central entity that determines the optimal percentage and informs the determined value to all UEs that are participating in the discovery process.

In order to reduce the congestion in preferred PDRs as well as the underutilization in nonpreferred PDRs in greedy PDR selection, we consider congestion dispersion based on grouping of PDRs and UEs. Let us assume that UEs are deployed in an area according to homogeneous Poisson point process (HPPP) with intensity λ [UEs/m ²] [13]. A probing UE performing discovery is deployed at the center of the area. The probing UE can successfully decode a received discovery message if its received signal-to-interference ratio (SIR) is higher than the decoding threshold T _SIR [dB]. The environment assumes free-space path loss model with exponent α (>2) and Rayleigh fading [14]. In lth discovery period, all of UEs except the probing UE start PDR selection and broadcast discovery messages through the selected PDRs. It has been assumed that the UEs sense the same channel and decide to use the same PDR $i^{*}_{l}$ in which the lowest energy is measured among N _PDR PDRs. In this case, according to Eq. (20)¹, the probing UE can discover other UEs only through PDR $i^{*}_{l}$ with the mean coverage (m ²) of:

$$ \tilde{A} (\lambda ) = \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi\cdot \lambda \cdot T_{\text{SIR}}^{2/\alpha}}. $$

(1)

The mean number of UEs that can be discovered in a discovery period is obtained from Eq. (22) ¹ as:

$$ \tilde{M} = \lambda \cdot \tilde{A} \left( \lambda \right ) = \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi \cdot T_{\text{SIR}}^{2/\alpha}}. $$

(2)

Note that $\tilde {M}$ is independent of the intensity of UEs (λ).

Now, we consider a case in which N _PDR PDRs in a discovery period are categorized into two equally sized groups, $G_{1}^{\text {PDR}}$ and $G_{2}^{\text {PDR}}$. Each UE randomly chooses one of the groups and selects one PDR among the PDRs in the selected group. In this case, in the lth discovery period, UEs that have chosen $G_{1}^{\text {PDR}}$ ($G_{2}^{\text {PDR}}$) select the same PDR $i^{*}_{l,1}$ ($i^{*}_{l,2}$) according to the greedy PDR selection. Let us consider that the UEs are evenly distributed. Since the grouping reduces density of UEs occupying a PDR by half, the probing UE shall detect UEs in each of the PDRs $i^{*}_{l,1}$ and $i^{*}_{l,2}$ with detectable area of:

$$ \tilde{A} \left( 0.5 \cdot \lambda \right ) = 2 \cdot \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi\cdot \lambda \cdot T_{\text{SIR}}^{2/\alpha}}. $$

(3)

Moreover, since UEs are dispersed into two PDRs rather than being concentrated in one, the probing UE can discover UEs through two PDRs ($i^{*}_{l,1}$ and $i^{*}_{l,2}$) rather than one PDR ($i^{*}_{l}$) if PDR grouping is not performed. Therefore, the number of discoverable UEs in a discovery period is doubled by classifying PDRs into two groups and limiting each UE’s PDR selection range to a group of PDRs, as:

$$\begin{array}{@{}rcl@{}} \tilde{M} &=& 2 \cdot 0.5 \cdot \lambda \cdot \tilde{A} \left( 0.5 \cdot \lambda \right ) \\ &=&2 \cdot \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi \cdot T_{\text{SIR}}^{2/\alpha}}. \end{array} $$

(4)

Because some of UEs in close proximity may measure received energy differently due to channel noise and fading, all UEs may not be concentrated on single PDR in real environments. Note that dividing N _PDR PDRs into multiple groups may limit spatial reuse of PDRs. As mentioned in Section 2.2, in greedy PDR selection, a UE will select a PDR that has been measured with lesser energy than the other PDRs in order to avoid selection of PDR that has been already occupied by the nearby UEs. This allows spatial reuse of each PDR by allowing maximum possible distance between UEs occupying the same PDR. However, the increase in the number of groups reduces PDR selection range of each UE. This is because the number of selectable PDRs is inversely proportional to the number of groups. Consequently, the possibility that a UE selects a PDR that is less occupied than the others from all PDRs reduces as the number of groups increases. Therefore, trade-off between the gain of congestion dispersion and the loss of selection range restriction should be considered in determining an appropriate number of groups.

The aforementioned example intuitively establishes that congestion dispersion by grouping PDRs and limiting the selection range of each UE to a group of PDRs can enhance the number of discoverable UEs in a discovery period.

3.2 PDR selection range restriction for newly joining UEs

This section describes the proposed group-based PDR selection range restriction (GPSRR) scheme. The scheme intends to disperse congestion on the preferred PDRs through allowing each UE to select a PDR from only one group of PDRs. In GPSRR scheme, each discovery period consisting of N _PDR (= n _f×n _t) PDRs is divided into N _grp equally sized groups. Figure 2 shows a typical discovery period in which resource architecture given in Fig. 1 is divided into N _grp = 8 groups.

Fig. 2

An example of discovery period with N _grp = 8 groups

The proposed GPSRR scheme operates in two phases, i.e., PDR grouping phase and PDR selection phase. Figure 3 shows the operation of a UE that is newly participating in the distributed D2D discovery process in the GPSRR scheme. In PDR grouping phase, each new UE participating in the distributed D2D discovery: (i) identifies the number of groups (N _grp) defined in a discovery period, (ii) locates the subframes allocated to each group, and finally (iii) chooses a group from which one PDR shall be selected. Since we consider distributed D2D discovery, a centralized controller such as eNB is not used by the UEs. Consequently, each UE dispersively performs the aforementioned three operations in the PDR grouping phase. For this purpose, each UE considers the default value of N _grp that is agreed to by all UEs (operation (i)). Based on the value of N _grp, the UE locates subframes allocated to each group through preconfigured subframe allocation for each group, which is also agreed to by all UEs (operation (ii)). Finally, UE randomly decides a group index from [1, N _grp] with uniform distribution, and finally decides to join the group (operation (iii)).

Fig. 3

GPSRR operations of a UE newly participating in distributed D2D discovery

Each UE which has finished the PDR grouping phase enters PDR selection phase. In this phase, each UE selects a PDR belonging to the joined group according to the greedy PDR selection introduced in Section 2.2. For the purpose, each UE measures the energy received through each PDR in the current discovery period (lth discovery period in Fig. 3). Then, the UE randomly selects on PDR out of 5 % of the N _PDR/N _grp PDRs that contain lower energy in comparison with others. Finally, the UE performs discovery message broadcasting and receiving in the following discovery period ((l+1)th discovery period in Fig. 3).

3.3 Group reselection for UEs in congested groups

In GPSRR, each UE shall select a PDR from a certain group of PDRs only. Since UEs can participate in or leave from D2D discovery at any time according to users’ decisions or their mobility, some groups may end up getting more congested than the others. If this happens, UEs joining the congested group may not successfully acquire a PDR even if available PDRs exist in the other groups. The unbalance of congestion among different groups may degrade the performance of discovery process (e.g, the number of discoverable UEs).

In order to maintain a uniform level of congestion in all groups, some UEs in the congested group should reselect another less congested group. For this purpose, UEs should have the ability to detect occurrence of congestion in its assigned group and reselect another group by itself. Here, we propose group reselection (GR) scheme to resolve the unbalance of congestion among groups that were formed using GPSRR. GR scheme consists of two operations: congestion detection and probabilistic group reselection. Through the operations, the proposed GR scheme disperses UEs, which could not acquire a PDR in the congested group, to other less congested groups. Such UEs are referred to as floating UEs. A floating UE is defined as a UE that has joined a certain group but has failed to successfully acquire the PDR during the previous discovery period due to collisions. In other words, floating UE is a UE that has not currently acquired a PDR due to two or more consecutive collisions during the previous discovery period.

Procedure for congestion detection and probabilistic group reselection of a floating UE is shown in Fig. 4. Congestion detection is performed as follows. During each discovery period (lth discovery period in Fig. 4), a floating UE in group n ^∗ (UE _float), that has not successfully acquired its own PDR among N _PDR/N _grp PDRs in group n ^∗, measures energy received through each PDR consisting the discovery period. The energy measurements can be done in parallel with receiving discovery messages that are broadcasted from other UEs [10]. Therefore, these measurements do not cause additional delay in the discovery message reception of the floating UE. At the end of the discovery period, the floating UE computes $\tilde {E}_{n}$ for all n (1≤n≤N _grp) and $\tilde {E}$ based on the measurements. $\tilde {E}_{n}$ is the average received energy for all PDRs in the group n where as $\tilde {E}$ is the average energy of all PDRs in the discovery period. Then, UE _float verifies if:

$$ \tilde{E}_{n^{*}} \leq \tilde{E} $$

(5)

or not. If the condition is satisfied, UE _float decides that its currently assigned group (n ^∗) is not excessively congested, and it continuously tries to acquire a PDR in the currently assigned group of the following discovery period ((l+1)th discovery period in Fig. 4). On the other hand, if the condition is not satisfied, UE _float decides that its current group n ^∗ is excessively congested than the other groups, and then it performs probabilistic group reselection at the beginning of the following discovery period ((l+1)th discovery period in Fig. 4).

Fig. 4

Procedure for congestion detection and probabilistic group reselection of a floating UE

Probabilistic group reselection assists the floating UE in the excessively congested group to reselect other less congested group. In order to evenly distribute floating UEs over less congested groups without much affecting D2D discovery of other UEs in the less congested groups, probabilistic group reselection makes each floating UE to select a new group with a certain probability. How the probability for group reselection is defined is introduced in the followings.

The currently less congested groups may become highly congested in the following discovery period if all floating UEs in the congested groups simultaneously select the less congested groups. In order to avoid this problem, each floating UE in the congested group n ^∗ ($\tilde {E}_{n^{*}} > \tilde {E}$) remains in the same group with probability:

$$ q_{n^{*}} = \min \left( \frac{\tilde{E}_{n^{*}} - \tilde{E}}{\tilde{E}}, 1 \right). $$

(6)

If the floating UE decides to leave the current group with probability 1−q _n∗, it should select one group from $\mathbb {G}$(=$\{ n | \tilde {E}_{n}\leq \tilde {E}, n\in \{1, ..., N_{\text {grp}}\}\}$). The group with lower mean energy should be selected with higher probability. Therefore, the probability that the floating UE that has decided to leave the current group selects a group m out of $\mathbb {G}$ is defined as:

$$ r_{m} = \frac{\tilde{E} - \tilde{E}_{m}} {{\sum}_{\forall n \in \mathbb{G}} \left( \tilde{E} - \tilde{E}_{n} \right) } \text{~ for ~} m\in \mathbb{G}, $$

(7)

where the numerator and the denominator represent the margin of energy in group m and the sum of margins for all groups in $\mathbb {G}$, respectively.

Finally, probability that a floating UE in group n ^∗ selects group m is defined as:

$$\begin{array}{@{}rcl@{}} p_{n^{*},m} &=& \left\{ \begin{array}{ll} 1 & \text{~if~} n^{*} = m \text{~and~} \tilde{E}_{n^{*}} \leq \tilde{E}, \\ q_{n^{*}} & \text{~if~} n^{*} = m \text{~and~} \tilde{E}_{n^{*}} > \tilde{E},\\ \left (1 - q_{n^{*}} \right ) \cdot r_{m} & \text{~if~} n^{*} \neq m, \tilde{E}_{n^{*}} > \tilde{E}, \text{~and~} m \in \mathbb{G}, \\ 0 & \text{elsewhere}. \end{array} \right . \end{array} $$

(8)

Floating UE (UE _float in Fig. 4) performed probabilistic group selection tires to select PDR in the upcoming group selected in the probabilistic group selection. The congestion detection and probabilistic group reselection are repeated until the floating UE successfully broadcasts its discovery message without collision.

4 Numerical analysis

This section discusses the performance of the proposed scheme using C++-based simulations. For all simulation results, our simulation environment consists of 19 hexagonal-shaped areas with 500-m intersite distance, as shown in Fig. 5. In each hexagonal area, N _UE UEs that try discovery message broadcasting are randomly deployed with uniform distribution. For example, if N _UE = 3,000, a total of 19⋅3,000 UEs are deployed in 19 hexagonal areas². These UEs try PDR acquisition and broadcasting of their discovery messages. In addition to these UEs, one probing UE that performs discovery of other UEs for all 19 hexagonal areas is randomly deployed at the center hexagonal area (area 1 in Fig. 5) with uniform distribution. The discovery period is such that n _f = 44 and n _t = 64, which leads to N _PDR = 44 ⋅64 = 2816. The discovery period is repeated at an interval of 10 s.

Fig. 5

Nineteen hexagonal areas considered in the simulation environments

During each simulation run, one probing UE deployed in the center hexagonal area of 19 areas performs discovery of other UEs. The discovery is done by observing entire PDRs in every discovery period. The probing UE as well as 19 ⋅N _UE UEs trying to broadcast discovery message move within initially deployed area according to the pedestrian mobility [16]. The direction of UE’s motion is randomly determined between [0, 2 π] with uniform distribution, while its velocity is determined according to the truncated normal distribution with mean 3 km/h, standard deviation 0.3 km/h, and minimum velocity 0 km/h. At every 8 s, each UE decides to update its direction and velocity values with a probability of 0.2, while it retains the previously determined values with a probability of 0.8. Each UE stays in a hexagonal area where the UE is initially located. If a UE approaches the edge of the hexagonal area while moving inside the area, it randomly determines a new moving direction that is directed inwards of the hexagonal area.

For all simulation results, we consider that each UE transmits discovery messages with transmission power of 23 dBm [17, 18]. In order to model signal attenuation, free-space path loss model with exponent 4 is applied. Successive interference cancellation (SIC) technique with perfect cancellation is considered for decoding the discovery messages received through each PDR [19]. Firstly, the probing UE identifies $\mathbb {S}_{i}$, a set of signals received through PDR i. Then, it finds a signal g ^∗ having the highest received signal strength (RSS) in $\mathbb {S}_{i}$. The probing UE successfully decodes the signal g ^∗ if SIR of the signal satisfies:

$$ \frac{R_{g^{*}}}{{\sum}_{\forall g\in \mathbb{S}_{i} - \{g^{*} \}} R_{g} } > T_{\text{SIR}}, $$

(9)

where R _g is RSS for signal g. If the signal g ^∗ is successfully decoded, the probing UE sets $\mathbb {S}_{i}$ to $\mathbb {S}_{i}$- {g ^∗}. The above process is repeated until there exists no more signal in $\mathbb {S}_{i}$ that satisfies the condition (9). In the simulations, T _SIR is set to 4.5 dB as specified in [10]. Note that the SIC technique may be used by each UE to decode discovery messages that are received through the PDR that is not occupied by the UE in the real environment.

We evaluate the performance of the distributed D2D discovery scheme introduced by Baccelli et al. [10], GPSRR scheme without GR scheme, and GPSRR scheme with GR scheme. For all three cases, all UEs perform greedy PDR selection introduced in Section 2.2. In all simulations, a discovery period is divided into N _grp equally sized groups and each UE randomly selects one of the groups with uniform distribution.

The UEs cannot receive and transmit messages at the same time due to half-duplex constraint of the transceiver. It follows that a UE broadcasting a discovery message through a certain PDR cannot receive the messages sent by other UEs in the same subframe. In order to overcome this problem, a hopping method is proposed in [10]. The hopping method allows changes in the position of a PDR selected by a UE in different discovery periods. In the following simulations, the same hopping method is applied for both the conventional scheme (Baccelli’s protocol [10]) and the proposed schemes (GPSRR without GR and GPSRR with GR). In the proposed scheme, the hopping method makes the position of a PDR acquired by a UE to change to the other position in the same group of PDRs that the UE belongs to in different discovery periods.

Figure 6 illustrates the number of UEs discovered in lth discovery period (M(l)) for N _grp = 64. It has been assumed that all N _UE UEs start D2D discovery and perform PDR selection simultaneously in the initial discovery period (l = 1). In order to evaluate the speed of convergence, we evaluate convergence point l ^∗ for each scheme. Based on the transient and steady-state response analysis [20], convergence point l ^∗ is defined as the index of discovery period (l) that M(l) reaches and settles within ±5 % range of the average number of detected UEs in steady state. In other words, l ^∗ is the smallest l that satisfies $0.95 \cdot ({\sum }_{l=101}^{200} M(l) ) \leq M(l^{*}) \leq 1.05 \cdot ({\sum }_{l=101}^{200} M(l) )$. In D2D discovery, competitions of N _UE UEs for PDR acquisition and discovery message broadcastings cause congestions. The smaller value of l ^∗ indicates that the congestions are resolved faster. For l<l ^∗, M(l) increases as l increases because additional UEs successfully acquire PDRs in each discovery period. On the other hand, for l≥l ^∗, most of the PDRs are occupied. Note that M(l) fluctuates due to the UEs that enter and leave the peripheral region of the probing UE. By distributing UEs to different groups of PDRs, GPSRR scheme allows more UEs to successfully acquire PDRs. Thus, as given in Table 1, GPSRR scheme can stabilize the network more quickly compared with the Baccelli’s protocol. For example, if 4000 UEs are deployed in each area, l ^∗ is 47 and 51 for GPSRR scheme with and without GR scheme, respectively, while l ^∗ is 71 for the Baccelli’s protocol. For N _UE = 3000 and 4000, all PDRs are highly congested because N _UE is much larger than N _PDR. Thus, the congestion dispersion through the group reselection has low effect on the convergence speed for N _UE = 3000 and 4000. However, for the environment with N _UE = 2000 where N _UE<N _PDR, GR reduces l ^∗ of GPSRR scheme by 20 %. In addition to the increase in the convergence speed, both GPSRR scheme with and without GR enable more UEs to be discovered by reducing PDR acquisition time for the newly joining UEs.

Fig. 6

The number of discovered UEs in each discovery period

Table 1 Convergence point l ^∗ for the number of discovered UEs

The number of collisions occurred in the lth discovery period is illustrated in Fig. 7. Like Fig. 6, it has been assumed that all N _UE UEs simultaneously start D2D discovery and PDR selection processes in the initial discovery period (l = 1). The number of collisions is evaluated as the number of UEs that have been discovered in (l-1)th discovery period but have not been discovered in the lth discovery period by the probing UE, due to the collisions in their PDRs³. Note that the collision occurring when multiple UEs simultaneously select the same PDR is not considered in Fig. 7. This is because how fast UEs can acquire PDR without selecting the same PDR is already evaluated in Fig. 6 and Table 1. During the early discovery periods following the initial discovery period, e.g., 1 < l < 20, UEs rapidly start acquiring PDRs as shown in Fig. 6. As the number of UEs occupying the PDRs increases, the probability that the occupied PDRs are selected by other UEs (that have not acquired PDRs) also increases. Due to this reason, the number of collisions sharply increases during the early discovery periods as can be seen from Fig. 7. For N _UE = 2000, the number of collisions is much less than those for N _UE = 3000 and 4000. This is because N _PDR is larger than N _UE. Thus, the gain of the proposed GPSRR and GR is not significant for N _UE = 2000 or less. Note that the collisions occurring for the case with N _UE = 2000 are mostly due to the mobility of UEs. If UEs reusing the same PDR are getting closer due to mobility, collision can occur. For N _UE = 3000 and 4000, several UEs may occupy PDRs that are already occupied by other UEs since the number of PDRs is less than that of UEs. Therefore, in addition to the collisions due to the UEs’ mobility, more than N _UE- N _PDR collisions occur for N _UE = 3000 and 4000. For these cases, both GPSRR schemes with and without GR achieve lower collisions when compared with the Baccelli’s protocol by distributing UEs evenly over PDRs. The GPSRR scheme with GR results in lowest collisions because UEs in congested groups are moved to other less congested groups.

Fig. 7

The number of collisions in each discovery period

The mean of the number of discovered UEs in each discovery period for different values of N _UE is shown in Fig. 8. Note that the mean number of discovered UEs is similar to N _UE in all three cases for a smaller value of N _UE. This is because sufficient numbers of PDRs exist and all UEs eventually acquire a PDR. On the other hand, for large number of N _UE, the mean number of discovered UEs decreases as N _UE increases. The reason is that the number of UEs far greater than N _PDR results in a lot of floating UEs. Worse still, the number of floating UEs increases the risk of collisions which results in PDR reselections. GPSRR scheme allows the probing UE to discover more UEs by dispersing them over multiple groups of PDRs. Therefore, for N _grp = 8 and 64, GPSRR scheme without GR always has a higher mean number of discovered UEs than the legacy scheme for all values of N _UE.

Fig. 8

Mean number of UEs discovered in a discovery period with different numbers of UEs

To determine the impact of the number of groups (N _grp) on the discovery process, we evaluate the mean number of discovered UEs with different values of N _grp as shown in Fig. 9. The results for N _UE = 2000 is not included in Fig. 9 because the mean numbers of discovered UEs for Baccellis protocol, GPSRR w/o GR, and GPSRR with GR are similar, as shown in Fig. 8. For both GPSRR schemes with and without GR, the mean numbers of discovered UEs for varying N _grp exhibit concave nature. This is because of the trade-off between the gain of congestion dispersion and the loss of selection range restriction in determining N _grp ⁴. There exist more floating UEs in the environments with N _UE≫N _PDR than those with N _UE≤N _PDR. By effectively dispersing the floating UEs over multiple groups, GR can further improve the mean number of discovered UEs for GPSRR scheme, especially for the environments where N _UE≫N _PDR. Thus, compared with the results for N _UE = 3000, GR highly improves the number of discovered UEs in GPSRR scheme for N _UE = 4000.

Fig. 9

Mean number of UEs in a discovery period with different numbers of groups

Note that the gain of the proposed schemes compared with Baccellis protocol in Fig. 9 is less than that expected in accordance with Eqs. (1)–(4) of Section 3.1. While deriving Eqs. (1)–(4), it is assumed that all UEs in close proximity select the same PDR according to greedy PDR selection. However, in simulations, all UEs are not always located in close proximity due to their mobility. Moreover, some of the UEs in close proximity measure different received energy due to channel noise and fading. Due to these reasons, which are not accounted for in Eqs. (1)–(4), some UEs may select different PDRs in simulations. This reduces the gain of the proposed schemes when compared with that expected from Eqs. (1)–(4). Uneven distribution of UEs over N _grp groups in GPSRR scheme also affects the expected gain.

5 Conclusion

3GPP has recently started the standardization of ProSe that utilizes proximity information of a UE as well as its neighboring UEs for supporting different applications. UEs are envisaged to communicate over D2D links to support ProSe services. Therefore, developing protocols and schemes for the new D2D discovery is of utmost significance in the standardization process. In order to enable efficient D2D discovery in the environments with dense UE deployment, this paper proposes group-based PDR selection range restriction (GPSRR) scheme based on grouping of discovery resources and UEs. In the environments where the number of UEs participating in D2D discovery is less than the number of PDRs in each discovery period, the proposed scheme has similar performance compared with the Baccellis protocol. On the other hand, for the cases where the number of UEs competing for PDR acquisition is higher than the number of PDRs in a discovery period, it has been shown that the proposed scheme significantly reduces congestion. This has been made possible by allowing UEs to choose resources only from their respective groups. The group reselection (GR) scheme proposed in this paper further enhances the discovery process by balancing congestion in different resource groups. For further study, we will deal with semidistributed D2D discovery protocol. It will enable determination of the optimal portion of selectable PDRs in greedy PDR selection.

Appendix: Developing models for performance metrics in D2D discovery

In order to analyze the impact of various parameters on the performance of distributed D2D discovery, we develop simple analytical model to derive the number of discoverable UEs. The analysis is performed based on the previous studies reported in [10, 13, 14], and [21]. It has been assumed that UEs are deployed in an area according to HPPP with intensity λ (UEs/m ²) [13]. A probing UE (UE 0) deployed at the center (0, 0) of the area performs discovery for other UEs. Euclidean distance from UE 0 to other UE k positioned at (x _k , y _k ) in $\mathbb {R}^{2}$ is denoted by d _k (=$\sqrt {x{_{k}}{{~}^{2}}+y{_{k}}{{~}^{2}}}$). Free-space path loss model with exponent α, where α is an integer larger than 2, and Rayleigh fading with mean 1 are considered. In addition, it has been assumed that each UE broadcasts discovery message with transmission power P _tx [W]. In this case, the received power at UE 0 from another UE k is expressed as $P_{\text {tx}} h_{k} d_{k}^{-\alpha }$ [W], where the random variable h _k follows an exponential distribution with mean 1 [14]. For simplicity, we consider random PDR selection, where each UE randomly selects a PDR between [1, N _PDR] with uniform distribution.

We firstly find detection probability P _dct(d _k ) in order to derive the number of detectable UEs [13, 21]. P _dct(d _k ) is defined as the probability that UE 0 will successfully receive discovery message sent by UE k which is d _k [m] apart from the UE 0. The received SIR of the discovery message sent from UE k to UE 0 (SIR _k ) should be larger than T _SIR for successful decoding of the message. Thus, P _dct(d _k ) can be expressed as:

$$\begin{array}{@{}rcl@{}} P_{\text{dct}} (d_{k}) &=& \text{Pr}\left( \text{SIR}_{k} >T_{\text{SIR}} \right ) \\ &=& \text{Pr}\left( \frac{P_{\text{tx}} h_{k} d_{k}^{-\alpha}}{{\sum}_{j\in {\Phi}} P_{\text{tx}} h_{j} d_{j}^{-\alpha} }>T_{\text{SIR}} \right) \\ &=& \text{Pr}\left( \frac{h_{k} d_{k}^{-\alpha}}{{\sum}_{j\in {\Phi}} h_{j} d_{j}^{-\alpha} }>T_{\text{SIR}} \right), \end{array} $$

(10)

where Φ is a set of UE j, ∀j≠0 and k. Equation 10 is rewritten as follows:

$$\begin{array}{@{}rcl@{}} P_{\text{dct}} (d_{k}) &=& \text{Pr}\left( h_{k} > d_{k}^{\alpha}T_{\text{SIR}{\sum\limits_{j\in {\Phi} } h_{j} d_{j}^{-\alpha} }} \right) \\ &=& 1-\text{Pr}\left( h_{k} \leq d_{k}^{\alpha}T_{\text{SIR}{\sum\limits_{j\in {\Phi}} h_{j} d_{j}^{-\alpha} }} \right). \end{array} $$

(11)

Since cumulative distribution function of h _k ($\text {Pr}\left (h_{k} \leq b \right )$) is 1−e ^−b [14], Eq. (11) can be rewritten as follows:

$$\begin{array}{@{}rcl@{}} P_{\text{dct}} (d_{k}) &=& E \left[ \text{exp} \left( -d_{k}^{\alpha} T_{\text{SIR}{\sum\limits_{j\in {\Phi} } h_{j} d_{j}^{-\alpha} }} \right) \right ]. \end{array} $$

(12)

where h _j and d _j are independent random variables. Thus, Eq. (12) becomes:

$$\begin{array}{@{}rcl@{}} P_{\text{dct}} (d_{k}) &=& E \left [ \prod\limits_{j\in {\Phi}} E \left [ \text{exp} \left( - d_{k}^{\alpha}T_{\text{SIR}} d_{j}^{-\alpha} h_{j} \right) | d_{j} \right ] \right]. \end{array} $$

(13)

Through calculating the expectation for h _j which follows an exponential distribution with mean 1, Eq. (13) can be rewritten as follows:

$$\begin{array}{@{}rcl@{}} P_{\text{dct}} (d_{k}) &=& E \left [ \prod\limits_{j \in {\Phi}} \frac{1}{1+d_{k}^{\alpha}T_{\text{SIR}} d_{j}^{-\alpha}} \right ]. \end{array} $$

(14)

By using the probability generating function for PPP [22], Eq. (14) is approximated to:

$$\begin{array}{@{}rcl@{}} &&P_{\text{dct}} (d_{k}) \cong\\ &&\text{exp} \left (- \lambda {\int}^{\infty}_{-\infty} {\int}^{\infty}_{-\infty} \left (1-\frac{1}{1 + d_{k}^{\alpha} T_{\text{SIR}} \left( {x_{j}^{2}} + {y_{j}^{2}}\right)^{-\alpha/2} } \right ) dx_{j} dy_{j}\right ). \end{array} $$

(15)

Let us denote $x_{j} = d_{k} T_{\text {SIR}}^{1/ \alpha } r_{j} \cos \theta _{j}$ and $y_{j} = d_{k} T_{\text {SIR}}^{1/ \alpha } r_{j} \sin \theta _{j}$. Then, we can find $dx_{j} dy_{j} = {d^{2}_{k}} T^{2/\alpha }_{\text {SIR}} r_{j} dr_{j} d\theta _{j}$ and ${x^{2}_{j}}+{y^{2}_{j}}={d^{2}_{k}} T^{2/\alpha }_{\text {SIR}} {r_{j}^{2}}$. By substituting these into Eq. (15), we can obtain:

$$ P_{\text{dct}} (d_{k}) \cong \exp \left (- \lambda {\int}^{2\pi}_{0} {\int}^{\infty}_{0} \left (1-\frac{1}{1 + r_{j}^{-\alpha}} \right ) {d^{2}_{k}} T^{2/\alpha}_{\text{SIR}} r_{j} d r_{j} d \theta_{j} \right ). $$

(16)

Through solving the integration for 𝜃 _j , Eq. (16) is simplified as follows:

$$ P_{\text{dct}} (d_{k}) \cong \exp \left (- 2 \pi \lambda {d^{2}_{k}} T^{2/\alpha}_{\text{SIR}} {\int}^{\infty}_{0} \left (\frac{r_{j}}{r_{j}^{\alpha} + 1} \right ) d r_{j} \right ). $$

(17)

By using the techniques of complex analysis, we can find that the integration ${\int }^{\infty }_{0} {r_{j}}/\left ({r_{j}^{\alpha } + 1}\right ) d r_{j}$ equals to $\pi / \left (\alpha \cdot \sin (2\pi / \alpha ) \right )$. Finally, the detection probability for UE k is obtained as follows:

$$ P_{\text{dct}} (d_{k}) \cong \exp \left (- \frac{2\pi^{2} \cdot \lambda \cdot {d^{2}_{k}} \cdot T_{\text{SIR}}^{2/\alpha}}{\alpha \cdot\text{sin} \left (2 \pi / \alpha \right ) } \right ). $$

(18)

Detectable area of UE k is defined as an area where the UE 0 can successfully receive discovery message from the UE k [13]. Mean detectable area for UE k ($\tilde {A}_{k} \left ({\Phi }, T_{\text {SIR}} \right )$ [m ²]) is expressed as follows:

$$\begin{array}{@{}rcl@{}} \tilde{A}_{k} \left ({\Phi}, T_{\text{SIR}} \right ) = \qquad \qquad \qquad \qquad \qquad \qquad \qquad\\ \qquad \left \{ (x_{k}, y_{k}) \in {\mathbb{R}}^{2} : \frac{h_{k} \left(\sqrt{{x_{k}^{2}} + {y_{k}^{2}}}\right)^{-\alpha}}{{\sum}_{j\in {\Phi} } h_{j} \left(\sqrt{{x_{j}^{2}} + {y_{j}^{2}}}\right)^{-\alpha} } > T_{\text{SIR}} \right\}. \end{array} $$

(19)

Averaging $\tilde {A}_{k} \left ({\Phi }, T_{\text {SIR}} \right )$ for all possible positions of UE k, we can obtain the mean volume of the detectable area for UE intensity λ as

$$\begin{array}{@{}rcl@{}} \tilde{A} \left( \lambda \right ) &=& E \left[ \tilde{A}_{k} \left ({\Phi}, T_{\text{SIR}} \right ) \right] \\ &=& {\int}^{\infty}_{-\infty} {\int}^{\infty}_{-\infty} 1\cdot P_{\text{dct}} \left( \sqrt{{x_{k}^{2}} + {y_{k}^{2}}} \right) dx_{k} dy_{k} \\ &=& \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi\cdot \lambda \cdot T_{\text{SIR}}^{2/\alpha}}. \end{array} $$

(20)

Let us denote the intensity of UEs occupying a PDR i as λ _i [UEs/m ²]. The mean number of discoverable UEs in a PDR i can be obtained by multiplying $\tilde {A} \left (\lambda _{i} \right )$ [m ²] with λ _i [UEs/m ²] as:

$$\begin{array}{@{}rcl@{}} \tilde{M}_{i} &=& \lambda_{i} \cdot \tilde{A}\left( \lambda_{i} \right ) \\ &=& \frac{\alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi\cdot T_{\text{SIR}}^{2/\alpha}}. \end{array} $$

(21)

Finally, the mean number of discoverable UEs in a discovery period consisting of N _PDR PDRs is obtained as:

$$\begin{array}{@{}rcl@{}} \tilde{M} &=& \sum\limits_{i=1}^{N_{\text{PDR}}} \tilde{M}_{i} \\ &=&N_{\text{PDR}} \cdot \frac{ \alpha \cdot \text{sin} (2\pi /\alpha)}{2\pi\cdot T_{\text{SIR}}^{2/\alpha}}. \end{array} $$

(22)