# Optimization Framework and Parameter Determination for Proximity-Based Device Discovery in D2D Communication Systems

Authors: Minjoong Rim; Seungyeob Chae; Chung G. Kang
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

One of the most important processes in device-to-device communications of cellular devices is that of discovery, which determines the proximity of devices. When a discovery process is performed, there are several parameters to determine, including the discovery range, the discovery period, and the modulation and coding scheme of the discovery messages. In this paper, we address the relationships between these parameters and describe an optimization framework to determine them. In the proposed procedure, it is important to first optimize the discovery rate, which is defined as the number of discoverable devices per unit time. Once the discovery rate is maximized, the discovery period can be determined accordingly based on the device density and the target discovery range. Since the discovery rate is not affected by many of discovery parameters such as the discovery range, the device density, and the discovery period, it can be used as a performance metric for comparing discovery schemes with different discovery ranges or different discovery periods.


---

## Body

## 1. Introduction

Cellular-assisted device-to-device (D2D) communications refer to direct communications among mobile devices without transferring data through a base station (BS) [1–6]. One of the most important processes in D2D communications is that of discovery, which finds devices located nearby [7–16]. In order to determine the proximity of devices, each device transmits a discovery message periodically, and other devices check if the message can be received successfully.Consider peer discovery applications such as friend finding in a densely populated urban area. If we have unlimited discovery resources or allow an unlimited discovery time, a resource unit dedicated for discovery message transmissions, simply calledresource block (RB) in this paper, can be occupied by at most one device so as to avoid the interference from other transmitting devices. In this case, the discovery range can be governed by the transmission power and the noise level. However, in practice, the discovery resources are limited and the discovery time should not be too long, while there can be a large number of devices participating in the discovery process. In this paper, we assume that discovery processes need to be performed with a reasonably short discovery time and limited discovery resources, while a large number of devices participate in a limited area, that is, the device density can be high. If the number of devices using the same RB is large, the discovery range might be limited by the interference from other transmitting devices.In interference-limited environments, a transmitting device may perform carrier sensing for each RB available within a single discovery period, before transmitting the discovery message, assuming that the interference conditions remain unchanged for a certain amount of time [17–20]. Then, it can select the RB with the least amount of interference so that the discovery range can be maximized. If there is no specific carrier sensing threshold used for a discovery or the carrier sensing threshold is too high, the discovery range may be determined by the density of transmitting devices per RB, assuming interference-limited environments. If a certain discovery range needs to be maintained, then the corresponding carrier sensing threshold can be used so as to satisfy the target signal-to-interference ratio (SIR) of the neighbor devices within the discovery range. If no RB satisfying the carrier sensing threshold can be found due to a high density of transmitting devices, the discovery period needs to be increased so that more RBs can be included in a single period. The discovery period can be adjusted by the centralized control of the network or by the distributed control of mobile devices. An increased discovery period means a large discovery range assuming still interference-limited environments, but it also results in a longer discovery time.Similarly, if a lower modulation and coding scheme (MCS) is used for a discovery message, the discovery range can be extended, since a lower SIR is allowed at the receivers. However, a low MCS may increase the size of each RB, resulting in an increased discovery time as well. We can see that the discovery range is related to the device density, the discovery period, and the target SIR of the discovery messages. In order to determine discovery parameters for a discovery process, it is important to understand the relationships among them.A number of recent works have focused on various issues on the discovery process. Scenarios and requirements for the discovery process have been discussed in [7–10] and some efficient discovery schemes have been proposed in a centralized manner [10] or in a distributed manner [11]. Efficient discovery patterns have been investigated [12] and energy efficiency discovery process has been intensely addressed [13–15]. However, most of these approaches do not adequately address the relationships among these discovery parameters. Above all, most of them simply assume a low MCS for a discovery message to increase the discovery coverage. A low MCS is surely helpful for noise-limited environments where the device density is very low. However, this may not be true with limited discovery resources and a high device density, since a low MCS means a small number of RBs with given discovery resources and thus there can be a large number of transmitting (and thus interfering) devices per RB. In this paper, we discuss how these discovery parameters are related and how they can be determined, assuming a high device density and interference-limited environments. The contribution of the paper includes the following.(a)
We address the relationships between the discovery parameters.(b)
We describe an optimization framework to determine the discovery parameters.(c)
We define a performance metric called discovery rate to compare discovery schemes with different discovery parameters.(d)
We show that the MCS should be carefully determined since a low MCS can be harmful when the device density is high.The rest of this paper is organized as follows. Section2 describes the system model considered in this paper and Section 3 discusses the design and performance metrics for the discovery process. Section 4 proposes an optimization framework to determine the discovery parameters. Simulation results are presented in Section 5 and conclusions are drawn in Section 6.


## 2. System Model

In order to determine the proximity of devices in D2D communication systems, devices transmit discovery messages periodically so that neighbor devices check if the messages can be received successfully [7–16]. In particular, when the number of devices is large, the network may not be able to take full control of D2D devices. The system model considered in this paper is based on network-assisted but distributed-control D2D communications. We assume that devices are all synchronized and provided with discovery resources orthogonal to those for cellular communications. While discovery parameters can be provided by the network, each device selects its own resource for discovery message transmissions.Figure1(a) illustrates a part of a D2D frame structure for discovery resources. In practice, there can be separate resources dedicated for cellular communications or D2D data transmissions, which are not shown here. We assume that the total amount of discovery resources is fixed and discovery resources are partitioned into RBs specialized for transmitting discovery messages. Each RB can include one discovery message with a fixed length of LMessage (bits) and its time length, denoted by TRB (seconds), depends on the MCS of a discovery message. While TRB is relatively static, the discovery period may be adjusted at run time if necessary. If the discovery period is chosen as TPeriod,0 (seconds), then the number of RBs in a single discovery period is given as NRB,0=TPeriod,0/TRB. Each device selects an appropriate RB among NRB,0 RBs within a single discovery period and transmits a discovery message periodically over the selected RB. For the remaining (NRB,0-1) RBs, each device tries to receive discovery messages so as to discover its proximate devices.Figure 1
Resource for discovery message transmissions with different discovery periods.
(a)
Initial discovery period
(b)
Increased discovery periodWhen a device starts the discovery process, it may perform carrier sensing for each RB available in a single discovery period and select the RB with the least amount of interference to maximize the discovery range [17–20]. If the measured interference power at a transmitter for the selected RB is lower than a predefined carrier sensing threshold ITransmitter, then the RB can be used for periodic discovery message transmissions with the assumption that a desired discovery range R can be satisfied. Otherwise, the discovery period needs to be increased so that a greater number of RBs can be included in an enlarged discovery period and the density of transmitters per RB can be reduced. Figure 1(b) illustrates an increased discovery period of  TPeriod,1 (seconds), in which NRB,1 RBs are included.There can be several different scenarios to adjust the discovery period. For example, devices may voluntarily reduce the number of discovery message transmissions by detecting the congestion of the discovery resources or a BS may adjust the discovery parameters upon the request of devices or using the information gathered from devices. Since the locations of devices can be steadily changed, devices need to reselect RBs after multiple transmissions of discovery messages. For reselecting an RB, a device may stop sending a discovery message, wait for a random time if necessary, and restart the discovery process with performing carrier sensing.


## 3. Design and Performance Metrics

### 3.1. Discovery Period

Consider discovery resources with an initial discovery period shown in Figure1(a). The average time length (in seconds) for one RB, denoted by TRB, can be written as(1)TRB=LMessageC(SIRTarget),where SIRTarget is the target SIR at the worst position inside the discovery range and C(SIRTarget) is the data rate achieved with SIRTarget. C(SIRTarget) can be determined by an MCS to meet a prespecified frame error rate and roughly predicted by Shannon capacity as (2)C(SIRTarget)=Blog2(1+SIRTarget),where B is the average bandwidth assigned for the discovery process. If there is no specific target discovery range or the device density is too low, the discovery process is performed with a minimum discovery period. The initial (and minimum) discovery period, denoted by TPeriod,0, can be written as (3)TPeriod,0=NRB,0TRB=NRB,0LMessageC(SIRTarget),where NRB,0 is the number of RBs included in the initial discovery period TPeriod,0. With a fixed TRB, the discovery period can be enlarged by increasing NRB if necessary.


### 3.2. Discovery Range

If carrier sensing is performed with a prespecified carrier sensing level, a minimum distance between two transmitting devices over the same RB is guaranteed [19, 20]. Suppose that devices transmitting discovery messages through the same RB are placed in a hexagonal form, as shown in Figure 2. Let R0 be the discovery range and let d0 be the distance between adjacent devices using the same RB. Consider a transmitter, six neighbor interferers, and a receiver located at the worst position inside the discovery range. The signal power at the receiver can be written as (4)SReceiver=K1R0-αand the interference power can be expressed as (5)IReceiver=K1d0-R0-α+d0+R0-α34d02+12d0+R02-α/2mmcc+234d02+12d0-R02-α/2mcmc+234d02+12d0+R02-α/2,where K1 is a constant determined by the system parameters and α is the path-loss exponent. Assuming interference-limited environments, the SIR at the receiver can be written as a function of R0/d0; that is, (6)SIRTarget=fR0d0,where function f(x)(x>0) is defined as(7)fx≡x-α1-x-α+1+x-α34+12+x2-α/2mmcmmcc+234+12-x2-α/2mmcmmcc+234+12+x2-α/2-1.Carrier sensing may be performed before the transmitter selects an RB and the interference power measured at the transmitter can be written as (8)ITransmitterHexagonal=6K1d0-α=6K1R0f-1(SIRTarget)-α,assuming that the inverse function f-1(•) exists over an acceptable range of SIRTarget. If the measured interference power at the transmitter is lower than the carrier sensing threshold ITransmitterHexagonal in (8), then the desired discovery range R0 can be satisfied, assuming that devices are placed in a hexagonal pattern.Figure 2
Interference with a hexagonal distribution.LetDDevice be the device density (the number of devices per unit area) for all devices participating in a discovery process assuming that devices are uniformly distributed. Each device selects an RB and transmits a discovery message over the selected RB. Assuming that devices are uniformly allocated over NRB,0 RBs, the density of transmitting devices for each RB, denoted by DDevice/RB,0, can be written as DDevice/RB,0=DDevice/NRB,0. In particular, for a hexagonal distribution of devices allocated on the same RB, it can be expressed as(9)DDevice/RB,0=1(3/2)d02=DDeviceNRB,0and, using (6) and (9), the discovery range R0 can be expressed as follows: (10)R0=d0f-1(SIRTarget)=23f-1(SIRTarget)DDevice/RB,0=23NRB,0DDevicef-1(SIRTarget).In practice, devices using the same RB may not be placed in a hexagonal form even with carrier sensing and thus (10) may not be very accurate. However, we can conjecture that the distance between two devices can be inversely proportional to the square of the density even for other distributions. It can be justified by the following argument. Consider a distribution of devices as shown in Figure 3(a) with density DDevice,0. Let dij be the distance between device i and device j, and NDevice,i(r) denote the number of devices included in the circle with radius r and centered at device i. Then, the device density can be expressed as (11)DDevice,0=limr→∞NDevice,i(r)πr2.Consider a β-times (β>0) expanded or shrunk version of the distribution as shown in Figure 3(b), where the distance between device i and device j, denoted by dijNew, is now given as dijNew=βdij. Then, the number of devices included in the circle centered at device i with radius r, denoted by NDevice,iNew(r), can be written as NDevice,iNew(r)=NDevice,i(r/β). Hence, the new device density, denoted by DDevice,1, can be expressed as(12)DDevice,1=limr→∞NDevice,iNew(r)πr2=limβr→∞NDevice,iNew(βr)πβr2=limβr→∞1β2NDevice,i(r)πr2=1β2DDevice,0and thus(13)β=DDevice,0DDevice,1,which means that the distance between two devices can be inversely proportional to the square of the density. Let us assume that the discovery range R0 is inversely proportional to DDevice/RB,0. Then, it can be expressed as (14)R0=g(SIRTarget)DDevice/RB,0=g(SIRTarget)NRB,0DDevice,where the function g(SIRTarget) can be found by simulations to take care of actual distributions of transmitting devices for an RB or for the special case of a hexagonal distribution, g(SIRTarget) can be given as (15)g(SIRTarget)=23f-1(SIRTarget).Figure 3
Device density with varying the distance between two devices.
(a)
Low device density
(b)
High device density


### 3.3. Discovery Rate

Let us define thediscovery rate as the number of discoverable devices per unit time. The discovery rate for a discovery process can determine the number of discoverable devices with a given discovery time and a device density. For other purpose, it can determine the discovery time with a given discovery range and a device density.Suppose that all devices inside the discovery rangeR0 are discoverable and other devices are not discoverable. The density of receiving devices inside the circle can be written as DDevice, since there can be no other transmitting device within the discovery range. The discovery rate per unit distance at distance r from the transmitter, denoted by ρDistance,0(r), can be written as (16)ρDistance,0(r)=2πrDDeviceTPeriod,0ifr<R00otherwise.Hence, the discovery rate, denoted by ρ0, can be determined by taking the integration of (16) as follows: (17)ρ0=∫0∞ρDistance,0(r)dr=∫0R02πrDDeviceTPeriod,0dr=πR02DDeviceTPeriod,0=πg2(SIRTarget)NRB,0DDeviceC(SIRTarget)NRB,0LMessageDDevice=πLMessageg2(SIRTarget)C(SIRTarget).Note that the discovery rate is a function of the target SIR SIRTarget, while it is independent of other discovery parameters such as the discovery period TPeriod,0 and the device density DDevice.If there is no specific target discovery range or the device density is very low, the minimum discovery period can be used. On the other hand, if the device density becomes too high with a given target discovery range, then the discovery period may need to be increased. If the device density is hard to estimate, the carrier sensing process may be used to determine whether the discovery period needs to be increased or not. If the interference measured at the transmitter is above a predefined threshold (e.g.,ITransmitterHexagonal in (8)) for all RBs, then a greater number of RBs need to be assigned so that a smaller number of devices are assigned to each RB. If the number of RBs within the discovery period is increased to NRB,1(>NRB,0), then the new discovery period can be written as (18)TPeriod,1=NRB,1LMessageC(SIRTarget)and the corresponding discovery range can be represented as follows: (19)R1=g(SIRTarget)NRB,1DDevice.Note that the discovery range can be enlarged by increasing the discovery period, assuming still interference-limited environments. The discovery rate per unit distance at distance r from the transmitter with the increased discovery period, denoted by ρDistance,1(r), can be written as (20)ρDistance,1(r)=2πrDDeviceTPeriod,1ifr<R10otherwiseand the discovery rate with the increased discovery period, denoted as ρ1, can be expressed as follows: (21)ρ1=∫0∞ρDistance,1(r)dr=∫0R12πrDDeviceTPeriod,1dr=πR12DDeviceTPeriod,1=πLMessageg2(SIRTarget)C(SIRTarget)=ρ0.The discovery rate is independent of the discovery period. If the discovery period increases with a fixed device density, the device density per RB decreases and the discovery range can be extended. This results in the increased number of discoverable devices but it will take more time to discover neighbors due to the increased discovery period. Similarly, the discovery rate is independent of the device density. If the discovery period is fixed, a high device density can result in a reduced discovery range. However, the discovery rate remains unchanged since the device density in the reduced discovery range is increased and the number of discoverable devices does not change.


## 3.1. Discovery Period

Consider discovery resources with an initial discovery period shown in Figure1(a). The average time length (in seconds) for one RB, denoted by TRB, can be written as(1)TRB=LMessageC(SIRTarget),where SIRTarget is the target SIR at the worst position inside the discovery range and C(SIRTarget) is the data rate achieved with SIRTarget. C(SIRTarget) can be determined by an MCS to meet a prespecified frame error rate and roughly predicted by Shannon capacity as (2)C(SIRTarget)=Blog2(1+SIRTarget),where B is the average bandwidth assigned for the discovery process. If there is no specific target discovery range or the device density is too low, the discovery process is performed with a minimum discovery period. The initial (and minimum) discovery period, denoted by TPeriod,0, can be written as (3)TPeriod,0=NRB,0TRB=NRB,0LMessageC(SIRTarget),where NRB,0 is the number of RBs included in the initial discovery period TPeriod,0. With a fixed TRB, the discovery period can be enlarged by increasing NRB if necessary.


## 3.2. Discovery Range

If carrier sensing is performed with a prespecified carrier sensing level, a minimum distance between two transmitting devices over the same RB is guaranteed [19, 20]. Suppose that devices transmitting discovery messages through the same RB are placed in a hexagonal form, as shown in Figure 2. Let R0 be the discovery range and let d0 be the distance between adjacent devices using the same RB. Consider a transmitter, six neighbor interferers, and a receiver located at the worst position inside the discovery range. The signal power at the receiver can be written as (4)SReceiver=K1R0-αand the interference power can be expressed as (5)IReceiver=K1d0-R0-α+d0+R0-α34d02+12d0+R02-α/2mmcc+234d02+12d0-R02-α/2mcmc+234d02+12d0+R02-α/2,where K1 is a constant determined by the system parameters and α is the path-loss exponent. Assuming interference-limited environments, the SIR at the receiver can be written as a function of R0/d0; that is, (6)SIRTarget=fR0d0,where function f(x)(x>0) is defined as(7)fx≡x-α1-x-α+1+x-α34+12+x2-α/2mmcmmcc+234+12-x2-α/2mmcmmcc+234+12+x2-α/2-1.Carrier sensing may be performed before the transmitter selects an RB and the interference power measured at the transmitter can be written as (8)ITransmitterHexagonal=6K1d0-α=6K1R0f-1(SIRTarget)-α,assuming that the inverse function f-1(•) exists over an acceptable range of SIRTarget. If the measured interference power at the transmitter is lower than the carrier sensing threshold ITransmitterHexagonal in (8), then the desired discovery range R0 can be satisfied, assuming that devices are placed in a hexagonal pattern.Figure 2
Interference with a hexagonal distribution.LetDDevice be the device density (the number of devices per unit area) for all devices participating in a discovery process assuming that devices are uniformly distributed. Each device selects an RB and transmits a discovery message over the selected RB. Assuming that devices are uniformly allocated over NRB,0 RBs, the density of transmitting devices for each RB, denoted by DDevice/RB,0, can be written as DDevice/RB,0=DDevice/NRB,0. In particular, for a hexagonal distribution of devices allocated on the same RB, it can be expressed as(9)DDevice/RB,0=1(3/2)d02=DDeviceNRB,0and, using (6) and (9), the discovery range R0 can be expressed as follows: (10)R0=d0f-1(SIRTarget)=23f-1(SIRTarget)DDevice/RB,0=23NRB,0DDevicef-1(SIRTarget).In practice, devices using the same RB may not be placed in a hexagonal form even with carrier sensing and thus (10) may not be very accurate. However, we can conjecture that the distance between two devices can be inversely proportional to the square of the density even for other distributions. It can be justified by the following argument. Consider a distribution of devices as shown in Figure 3(a) with density DDevice,0. Let dij be the distance between device i and device j, and NDevice,i(r) denote the number of devices included in the circle with radius r and centered at device i. Then, the device density can be expressed as (11)DDevice,0=limr→∞NDevice,i(r)πr2.Consider a β-times (β>0) expanded or shrunk version of the distribution as shown in Figure 3(b), where the distance between device i and device j, denoted by dijNew, is now given as dijNew=βdij. Then, the number of devices included in the circle centered at device i with radius r, denoted by NDevice,iNew(r), can be written as NDevice,iNew(r)=NDevice,i(r/β). Hence, the new device density, denoted by DDevice,1, can be expressed as(12)DDevice,1=limr→∞NDevice,iNew(r)πr2=limβr→∞NDevice,iNew(βr)πβr2=limβr→∞1β2NDevice,i(r)πr2=1β2DDevice,0and thus(13)β=DDevice,0DDevice,1,which means that the distance between two devices can be inversely proportional to the square of the density. Let us assume that the discovery range R0 is inversely proportional to DDevice/RB,0. Then, it can be expressed as (14)R0=g(SIRTarget)DDevice/RB,0=g(SIRTarget)NRB,0DDevice,where the function g(SIRTarget) can be found by simulations to take care of actual distributions of transmitting devices for an RB or for the special case of a hexagonal distribution, g(SIRTarget) can be given as (15)g(SIRTarget)=23f-1(SIRTarget).Figure 3
Device density with varying the distance between two devices.
(a)
Low device density
(b)
High device density


## 3.3. Discovery Rate

Let us define thediscovery rate as the number of discoverable devices per unit time. The discovery rate for a discovery process can determine the number of discoverable devices with a given discovery time and a device density. For other purpose, it can determine the discovery time with a given discovery range and a device density.Suppose that all devices inside the discovery rangeR0 are discoverable and other devices are not discoverable. The density of receiving devices inside the circle can be written as DDevice, since there can be no other transmitting device within the discovery range. The discovery rate per unit distance at distance r from the transmitter, denoted by ρDistance,0(r), can be written as (16)ρDistance,0(r)=2πrDDeviceTPeriod,0ifr<R00otherwise.Hence, the discovery rate, denoted by ρ0, can be determined by taking the integration of (16) as follows: (17)ρ0=∫0∞ρDistance,0(r)dr=∫0R02πrDDeviceTPeriod,0dr=πR02DDeviceTPeriod,0=πg2(SIRTarget)NRB,0DDeviceC(SIRTarget)NRB,0LMessageDDevice=πLMessageg2(SIRTarget)C(SIRTarget).Note that the discovery rate is a function of the target SIR SIRTarget, while it is independent of other discovery parameters such as the discovery period TPeriod,0 and the device density DDevice.If there is no specific target discovery range or the device density is very low, the minimum discovery period can be used. On the other hand, if the device density becomes too high with a given target discovery range, then the discovery period may need to be increased. If the device density is hard to estimate, the carrier sensing process may be used to determine whether the discovery period needs to be increased or not. If the interference measured at the transmitter is above a predefined threshold (e.g.,ITransmitterHexagonal in (8)) for all RBs, then a greater number of RBs need to be assigned so that a smaller number of devices are assigned to each RB. If the number of RBs within the discovery period is increased to NRB,1(>NRB,0), then the new discovery period can be written as (18)TPeriod,1=NRB,1LMessageC(SIRTarget)and the corresponding discovery range can be represented as follows: (19)R1=g(SIRTarget)NRB,1DDevice.Note that the discovery range can be enlarged by increasing the discovery period, assuming still interference-limited environments. The discovery rate per unit distance at distance r from the transmitter with the increased discovery period, denoted by ρDistance,1(r), can be written as (20)ρDistance,1(r)=2πrDDeviceTPeriod,1ifr<R10otherwiseand the discovery rate with the increased discovery period, denoted as ρ1, can be expressed as follows: (21)ρ1=∫0∞ρDistance,1(r)dr=∫0R12πrDDeviceTPeriod,1dr=πR12DDeviceTPeriod,1=πLMessageg2(SIRTarget)C(SIRTarget)=ρ0.The discovery rate is independent of the discovery period. If the discovery period increases with a fixed device density, the device density per RB decreases and the discovery range can be extended. This results in the increased number of discoverable devices but it will take more time to discover neighbors due to the increased discovery period. Similarly, the discovery rate is independent of the device density. If the discovery period is fixed, a high device density can result in a reduced discovery range. However, the discovery rate remains unchanged since the device density in the reduced discovery range is increased and the number of discoverable devices does not change.


## 4. Optimization Framework

Since the discovery rateρ is independent of other discovery parameters, including the discovery range R, the device density DDevice, and the discovery period TPeriod, it is important to first maximize the discovery rate. With a given bandwidth and a message length, the discovery rate depends on the target SIR and the distribution of devices allocated on the same RB. Hence, we need to first find the target SIR that maximizes the discovery rate, expressed as follows: (22)SIRTargetOptimal=argmax⁡SIRTargetρ=argmax⁡SIRTargetg2(SIRTarget)C(SIRTarget).The target SIR found by (22) determines the MCS of a discovery message and the length (in seconds) of an RB. For example, if a hexagonal distribution is assumed for devices using the same RB and (2) is used to calculate the data rate for the discovery message, then the optimal target SIR is found as follows:(23)SIRTargetOptimal=argmax⁡SIRTargetf-1(SIRTarget)2log2(1+SIRTarget)≈9dB.Other parameters can be subsequently determined. For example, if the target discovery range R and the device density DDevice are given, then the number of RBs within the discovery period can be determined as(24)NRB=max⁡NRB,0,DDeviceR2g2(SIRTargetOptimal)and the discovery period can be obtained as (25)TPeriod=NRBTRB=max⁡TPeriod,0,LMessageDDeviceR2g2(SIRTargetOptimal)C(SIRTargetOptimal).If the target discovery range R is given, but the device density DDevice is unknown, carrier sensing can be performed with the corresponding sensing threshold. If a device is unable to find an RB satisfying the carrier sensing threshold, then the discovery period needs to be increased. If the target discovery range R is not specified, the discovery range can be simply determined by the device density.The proposed procedure for discovery parameter determination is summarized in Figure4. In the figure, the solid rectangular boxes represent the determination of discovery parameters using (1), (8), (19), and (22). First, the target SIR (SIRTarget) at receivers needs to be optimized by (19), which in turn can determine the MCS of a discovery message and the length of an RB (TRB) by using (1). Note that these are static system parameters, which are hardly modified at run time. If there is no target discovery range, there are no more discovery parameters to determine. The discovery range can be simply determined by the device density. If the target discovery range is given and the device density can be estimated by the BS, the discovery period can be determined by adjusting the number of RBs in a single discovery period. However, it may not be easy to estimate the device density. Then, a BS simply provides a carrier sensing threshold, which can guarantee a minimum distance between two adjacent devices allocated on the same RB.Figure 4
Optimization framework for discovery process.In practice, the discovery range is not clearly defined due to fading, shadowing, and irregular distributions of transmitting devices. Hence, some simulations might be required to obtain more accurate values of discovery parameters with a precise definition of the discovery range. However, the procedure described in Figure4 can be still applicable for determining discovery parameters even with simulations.Notice that the optimal SIR obtained in (23) is not very low even when a large (but still interference-limited) discovery range is required. Although a low target SIR is helpful to receive a message with severe interference, a low MCS increases the average time length for one RB (TRB) and decreases the number of RBs (NRB) in a single discovery period. Hence, the density of transmitting devices for each RB (DDevice/RB) is increased and the discovery range might be even reduced due to the increased interference. A low MCS does not mean a large discovery range if the discovery process is performed in a heavily populated area.


## 5. Simulation Results

In this section, we find discovery rates by Monte-Carlo simulations, in which devices are randomly distributed over a wide square area of 1000 m × 1000 m and interferences are generated with a wrap-around pattern. For the simulations, the length of an RB is determined by (2) with a given target SIR, and resource allocation for each device is performed sequentially based on carrier sensing results. Each device selects an RB with the least amount of interference and transmits a discovery message if a given carrier sensing threshold is satisfied. The initial (and minimum) number of discovery RBs in the discovery period is 8 and the number of RBs can be increased if there is no RB satisfying the carrier sensing threshold. Some simulation parameters are chosen to show substantially different shapes of curves having different discovery ranges. Rayleigh fading is used for channels but shadowing is not applied for the simplicity of simulations. The detailed simulation parameters are summarized in Table 1.Table 1
Simulation parameters.
Parameter
Value
Simulation region
1000 m × 1000 m (wrap-around)
Device density (DDevice)
Figures4 and 7
0.005/m2
Figure5
0.001~0.004/m2
Figure6
0.002/m2
Path loss exponent (α)
4
Shadowing
Not applied
Fading
Flat Rayleigh fading
Bandwidth (B)
10 KHz
Message length (LMessage)
100 bits
Initial number of RBs in discovery period (NRB,0)
8
Target SIR (SIRTarget)
Figures4 and 5
0 dB
Figure6
−10~20 dB
Figure7
7 dBFigure5(a) shows the discovery rates per unit distance at distance r from the transmitting device, with four different sensing thresholds (Γ1, Γ2, Γ3, and Γ4), when 0 dB is used for the target SIR. The sensing thresholds are chosen to show substantially different shapes of curves with different discovery ranges. While Γ1 is a high value that allows for the large interference, Γ4 is low to maintain a large discovery range at the expense of an increased discovery time. The area under each curved line in Figure 5(a) shows the discovery rate, which has been redrawn as a bar graph in Figure 5(b) for the purpose of easy comparisons. The shapes of the four graphs in Figure 5(a) are quite different, indicating different discovery ranges. However, their areas, which represent the discovery rates, are very similar as shown in Figure 5(b).Figure 5
Discovery rates with varying sensing thresholds.
(a)
Discovery rates per unit distance
(b)
Discovery ratesFigure6 illustrates the discovery rates with varying device densities (DDevice = 0.001, 0.002, 0.003, and 0.004/m2). The device densities are chosen to show substantially different shapes of curves. The target SIR is set to 0 dB and no specific carrier sensing threshold is used. If there is no specific carrier sensing threshold, a large discovery range can be obtained with a low device density and the discovery range decreases as the device density increases. From the figures, we can see that the discovery rate is also independent of the device density. While very different values of discovery ranges can be obtained by changing other discovery parameters, the discovery rates do not significantly vary. Hence, the discovery rate can be used as a performance metric for comparing discovery schemes with different discovery parameters. We can say that similar discovery performances can be obtained among the four schemes in Figure 5 (or among the four schemes in Figure 6) although they have quite different discovery ranges.Figure 6
Discovery rates with varying device densities.
(a)
Discovery rates per unit distance
(b)
Discovery ratesFigure7(a) shows the discovery rates per unit distance with several different target SIR values (−10 dB, 0 dB, 10 dB, and 20 dB) at receivers, when there is no specific sensing threshold. As expected, a discovery range also depends on the corresponding target SIR and a low target SIR can achieve a longer discovery range. However, unlike Figures 5(a) or 6(a), the curved lines in Figure 7(a) have substantially different areas. Figure 7(b) represents the discovery rates according to target SIR values from −10 dB to 20 dB. In the figure, the discovery rate can be maximized with the target SIR of 7 dB, which is close to the theoretical optimal target SIR (9 dB) found by (23) assuming a hexagonal distribution of devices allocated on the same RB. Discovery schemes with the optimal target SIR will provide the best performances and other parameters can be subsequently determined.Figure 7
Discovery rates according to target SIR values.
(a)
Discovery rates per unit distance
(b)
Discovery ratesFigure8 shows the results with the target SIR of 7 dB (the optimal target SIR found from Figure 7(b)). In order to obtain similar discovery ranges as those for Figure 5, threshold values Γi/SIRTarget(i=1,2,3,4) are used. Other simulation parameters are the same as those for Figure 5. Note that the discovery rates are considerably improved as compared to those in Figure 5, in which 0 dB is used for the target SIR. If we want to obtain a reasonably long discovery range with a high device density, we need to use a long discovery period or a low carrier sensing threshold with the optimal target SIR instead of using a low target SIR.Figure 8
Discovery rates with the optimal target SIR.
(a)
Discovery rates per unit distance
(b)
Discovery ratesWhen the device density is very low, we can use a low MCS to maximize the discovery range. However, if we consider discovery processes in an urban area where the device density can be very high, we would better not use a too low MCS since it may eventually reduce the discovery range with a discovery time limit. The discovery rate (the number of discoverable devices per unit time) for discovery process is analogous to the received data rate (the amount of successfully received data per unit time) for data transmissions. A too low MCS is not desirable since only small amount of data can be transmitted per unit time and a too high MCS is also not recommended since receivers become too vulnerable to the interference from other transmitters. An appropriate MCS needs to be used to maximize the system performance for data transmissions. So is true for device discovery and the discovery rate can be maximized with an appropriate MCS.


## 6. Conclusion

The discovery rate, which is defined as the number of discoverable devices per unit time, does not depend on the device density, the discovery range, or the discovery period assuming interference-limited environments. Hence, it can be used as a performance metric for comparing discovery methods with different discovery parameters. While the discovery rate is independent on many other discovery parameters, its value can significantly vary with the target SIR at receivers. Hence, the MCS of a discovery message should be optimized first.While a low MCS of a discovery message is considered in many of previous works, this paper shows that a low MCS can be harmful when the device density is high. The number of discovery RBs is reduced with a lower MCS with given discovery resources and a greater number of devices may be assigned to each RB. This increases the interference from other transmitting devices and the discovery range might be eventually reduced. The discovery rate for discovery process is analogous to the received data rate in data transmissions. While a too high MCS makes receivers vulnerable to interference, a too low MCS is also not desirable since only small amount of data can be transferred per unit time.The analysis given in this paper may be extended with considering a clearer definition of discovery ranges, more realistic channel models with fading and shadowing, more practical distributions of transmitting devices, and more complicated discovery processes including multihop discovery, device cooperation, and intelligent network assistance. Also, half-duplexing and adjacent-channel-interference problems need to be considered in the future for orthogonal frequency division multiple access (OFDMA) systems. A slightly lower value of the target SIR might be required with severe adjacent channel interference, since more robust MCS may be beneficial to mitigate the interference from other OFDMA subchannels.



---

*Source: 102049-2015-04-07.xml*