SIR-based multiple access with cascade yielding avoidance for distributed device-to-device communications

Abstract

As the demands for efficient distributed device-to-device (D2D) communications increase, signal-to-interference ratio (SIR)-based multiple access (SBMA) technique has been proposed. By enabling SIR-aware multiple access control in distributed D2D communication, SBMA can improve utilization of the shared wireless medium in comparison with the conventional carrier sense multiple access technique. However, SBMA suffers from the cascade yielding problem which adversely affects the performance gain expected from SBMA. Cascade yielding is caused due to the limited knowledge available to each device about the medium access decisions of the neighboring devices. In order to reduce this problem, this paper enhances SBMA by taking into account the yielding relationships between neighboring devices during medium access decisions. The yielding relationships enable each device to more precisely estimate the SIRs and hence more effectively determine medium accessibility. Our simulation results show that the enhanced SBMA can allow more devices to simultaneously access the shared medium and improve the overall performance of D2D communications.

1 Introduction

In order to accommodate the burgeoning traffic in the existing network capacity, device-to-device (D2D) communication is being examined [1–8, 10, 11]. By enabling direct data transfer between adjacent mobile devices, D2D communication relieves the central base station from unnecessary relaying of information to and from mobile devices. Since D2D setup allows direct communication, more users may be accommodated within the network without increasing overall bandwidth requirements. Due to its apparent advantages, the 3rd generation partnership project (3GPP) is considering to standardize D2D communication for the next generation communication systems [3–7]. Various use cases and potential requirements for D2D communication in 3GPP Rel. 12 of long term evolution (LTE) system have been introduced in [3].

In order to get maximum benefit, D2D communications should have the ability to offload the burden of cellular systems without introducing high control overhead. Secondly, D2D services should be available even in the environments where cellular coverage is not available. In such cases, D2D communication may be able to provide extended coverage to other nodes by means of relaying, as envisaged in public safety communications [3]. Taking these issues into account, exploring distributed D2D communications shall be of more interest. In distributed D2D communications, a pair of a transmitting (Tx) device and a receiving (Rx) device is defined as a D2D connection. The Tx and Rx devices in a D2D connection do not require coordination from a centralized entity, e.g. a base station or central network controller, for communicating with each other. The D2D connection must occupy wireless medium consisting of certain time and frequency resources. The medium of a network is often shared by multiple D2D connections to increase the spectral efficiency of the network. Techniques such as carrier sense multiple access with collision avoidance (CSMA/CA) can be used to accommodate multiple D2D connections on the shared medium. It is well known that CSMA/CA allows each user to access the shared medium if the carrier for an ongoing transmission is not sensed on the shared medium [9, 12]. A serious drawback of CSMA/CA is that the devices may back off even when the ongoing transmission and the devices’ transmission could be performed at the same time with a sufficiently high signal-to-interference ratios (SIRs). Therefore, CSMA/CA based D2D communication results in underutilization of the wireless resources [10].

SIR-based multiple access (SBMA) technique, which provides fully distributed medium access coordination for peer-to-peer and infrastructure-less communications, is newly introduced for efficient distributed D2D communications [10, 11]. In the previous studies, SIR is considered mostly in transmission power and call admission control techniques, especially for the CDMA systems [13, 14]. Different from such pervious works, SMBA allows D2D connections to determine their medium accessibility based on instantaneous SIR that is measured by each device before transmission in order to utilize the shared medium more efficiently. SBMA intends to achieve what is known as the maximal matching distributed scheduling [15–17]. The purpose of maximal matching is to find a maximal set of devices that can access the shared medium simultaneously without violating predefined interference constraints [15–17]. In other word, the purpose of SBMA is to allow as many devices as possible to simultaneously access the shared medium while guaranteeing certain level of transmission quality. By allowing more devices to simultaneously access the shared medium compared to the legacy CSMA/CA, SBMA improves resource utilization while still keeping interference within a tolerable limit.

In SBMA, multiple access to the shared medium is conditioned on the SIR values of the D2D connections that intend to transmit simultaneously. Let us consider a D2D connection $i$ consisting of a Tx device (${\rm Tx}_{i}$) and a Rx device (${\rm Rx}_{i}$). According to SBMA, ${\rm Tx}_{i}$ makes a decision to transmit data to ${\rm Rx}_{i}$ during a certain medium access period, only if the estimated SIR of its own connection as well as the estimated SIRs of its neighboring connections (that will simultaneously access the medium) are higher than the specified thresholds. A big limitation to this scheme is that a device cannot determine which neighboring connections will simultaneously transmit data on the shared medium. Since the calculations of SIRs are done by multiple distributed connections in parallel, a device cannot know whether each of its neighboring connections eventually decides to access the medium or not. Each device simply assumes that all of its neighboring connections attempting data transmission will transmit data simultaneously during the medium access period. Because of this assumption, the device includes interferences from all of its neighboring connections in the calculations of SIRs. The calculated SIR values may force some connections to back off even when they could have transmitted successfully with sufficiently high SIRs. This phenomenon in SBMA is called cascade yielding problem [18]. Since the cascade yielding problem limits the reuse of the shared medium and reduces the frequency of data transmissions for each connection, it should be avoided in order to improve the performance of distributed D2D communications.

For achieving improved maximal matching, this paper proposes SBMA with cascade yielding avoidance (SBMA/CYA) which is an enhanced version of the SBMA technique. In order to reduce the occurrence of cascade yielding, the proposed technique introduces yielding relationship indicator (YRI). YRI indicates whether a connection can concurrently access the shared medium with an adjacent high priority connection. In other words, YRI is an indicator that enables each device to predict whether each high priority connection shall simultaneously transmit data. Each device can empirically obtain YRI in a distributed manner. The use of YRI helps the devices to avoid unnecessary back offs through enabling more accurate calculation of SIRs. With the help of simulations, we show that the SBMA/CYA can allow more connections to simultaneously access the shared medium as compared to the conventional SBMA as well as the legacy method based on iterations in [10]. It has been shown that the proposed scheme improves the performance of distributed D2D communications in terms of the number of concurrent transmissions, throughput, and delay.

The rest of this paper is organized as follows. An overview of system model and techniques for medium access decisions in legacy SBMA are introduced in Sect. 2, and the cascade yielding problem is discussed in Sect. 3. In Sect. 4, the proposed SBMA/CYA technique is introduced. The performance of the proposed SBMA/CYA is evaluated in Sect. 5 and the conclusion is given in Sect. 6.

2 Preliminaries

In this section, we discuss the basic system model for SBMA. SBMA operates on the synchronous PHY/MAC network architecture introduced in [10]. For enabling SIR measurements, a single-tone analog signal that is transmitted on a single sub-channel in orthogonal frequency division multiplexing (OFDM) signal structure is defined in the PHY/MAC network architecture. By measuring the received signal strengths of single-tone analog signals sent by Tx devices, Rx devices can calculate their respective connection’s SIR. Similarly, Tx devices can estimate the SIRs of their neighboring connections by measuring the received signal strengths of single-tone analog signals sent by the Rx devices. More details on SIR measurements have been given in Sects. 2.1 and 2.2. Since the single-tone signal occupies only a narrow bandwidth (a sub-channel), it can be transmitted with much higher power spectral density (Watts/Hz) than other signals occupying multiple sub-channels. Single-tone analog signal is also used for the purposes of peer discovery and connection management.

In order to enable distributed D2D communications based on SBMA, superframe structure has been introduced in [10] and [19] as illustrated in Fig. 1(a). In primary synchronization phase, coarse timing of devices is synchronized for superframe alignment. In the discovery and paging phase, devices perform secondary timing synchronization and broadcast peer discovery signals to discover each other. In addition, some of the devices establish D2D connections during the peer paging phase. In order to enable distributed coordination of medium access for D2D transmission from a Tx device to a Rx device, SBMA defines D2D connection, which is an unit of multiple access, as a logical link for one-way D2D communication. For bidirectional communication between two devices, they need to establish two unidirectional connections having opposite directions. Note that the two D2D connections should be accessed in different time, since each device can determine availability of only one connection at a time. For connection management, connection identifier (CID), which is an identifier of a D2D connection, is defined in SBMA [10]. The value of CID typically ranges from 1 to 112, and it is used by Tx and Rx devices to determine their D2D connection’s priority of medium access. Tx and Rx devices of the newly establishing D2D connections acquire CID by observing single-tone analog signals that are broadcasted by Tx and Rx devices of the existing D2D connections during CID broadcast OFDM block. The data transfer phase consists of 20 traffic channel (TCCH) frames, and all connections access the medium according to SBMA in each of these frames.

Fig. 1

Structures of superframe and traffic channel (TCCH) frame. a Superframe, b TCCH frame

The structure of a TCCH frame is shown in Fig. 1(b) [10, 20]. In the connection scheduling period, devices on each active connection perform signaling using the single-tone analog signals in the Tx and Rx OFDM blocks. The SBMA technique uses this signaling to decide medium access for different devices. After the decisions are made, in the rate scheduling period, connections that have decided to access the medium determine their modulation scheme and coding rate for data transmission. The pilot signals and channel quality indicator (CQI) reports help a connection in choosing an appropriate modulation and coding technique. Finally, during the data segment transfer and acknowledgment periods, Tx devices send actual data to Rx devices, and the Rx devices acknowledge the received data. The data and the acknowledgment are transmitted through the entire system bandwidth.

As mentioned earlier, in SBMA, each connection distributively decides whether to access the medium during a TCCH frame based on SIRs of its own connection as well as the adjacent higher priority connections. In order to allow calculation of the SIRs in each TCCH frame, SBMA defines Tx and Rx OFDM blocks that enable devices to exchange direct power (DP) and inverse power echo (IPE) single-tone analog signals without interfering each other. DP and IPE signals are used by the devices to determine (1) SIRs of its own connection and neighboring connections, and (2) whether other devices access the medium or not. Figure 2 shows the structure of Tx and Rx OFDM blocks, where an OFDM block is defined to contain 28 sub-channels in the frequency domain and 4 OFDM symbols in the time domain [10]. It consists of 112 resource elements (REs), where one RE corresponds to a sub-channel and an OFDM symbol in frequency and time domains respectively. Tx (or Rx) device in each connection occupies a RE in Tx (or Rx) OFDM block for transmitting DP (or IPE) single-tone analog signal. Tx and Rx devices can locate REs in Tx and Rx OFDM blocks from CID of their connection. At the beginning of each TCCH frame, Tx and Rx devices in connection $i$ substitute their connection’s CID in the hash function commonly known by all devices to determine geographically unique priority value of connection $i\, (\eta _i)$. This priority value lies between 1 and 112, where lower value indicates higher priority. The hash function is such that the priority of each connection having a certain CID changes over the TCCH frames in order to give each connection an even opportunity to access the shared medium. The numeric value shown in each RE in Fig. 2 represents the priority value of the connection that occupies that RE for exchanging single-tone analog signals. For example, Tx and Rx devices in connection $i$ with $\eta _i$ = 5 transmit DP and IPE signals through RE no. 5 in Tx and Rx OFDM blocks, respectively.

Fig. 2

Tx and Rx OFDM blocks

For a clear explanation of SBMA procedure introduced in [10], we consider two connections, $i$ and $j$ shown in Fig. 3, where priority values of connections $i$ and $j$ are $\eta _i$ and $\eta _j$ respectively. It has been assumed that connection $j$ has the higher priority than connection $i$ ($\eta _j < \eta _i$). Recall that a lower priority value indicates higher priority. In addition, it is assumed that both Tx devices of connections $i$ (Tx$_i$) and $j$ (Tx$_j$) have data for their peer Rx devices $\hbox {Rx}_i$ and Rx$_j$ in the $k$th TCCH frame. $|h_{ab}|^2$ in Fig. 3 is defined as the channel gain between Tx device of connection $a$ (Tx$_a$) and Rx device of connection $b$ (Rx$_b$). If $b$ = $a$, it follows that $|h_{ab}|^2\,=\,|h_{aa}|^2$, which represents the channel gain between Tx$_a$ and Rx$_a$ in the same connection $a$. For medium access, a connection should make two decisions, namely Rx- and Tx-yielding [10]. A connection can access the medium only if the both conditions defined in Rx- and Tx-yielding decisions are satisfied. These yielding decisions dictate simultaneous medium access for different connections. Rx- and Tx-yielding decision procedures for determining medium access of the connection $i$ are given in the following. Note that (1–5) in the following descriptions are based on the discussion given in [10].

Fig. 3

Example of two D2D connections $i$ and $j$

2.1 Rx-yielding decision

Firstly, in the Tx OFDM block of $k$th TCCH frame, Tx$_i$ and Tx$_j$ transmit DP signals in $\eta _i$th and $\eta _j$th REs with $P_{i}$ and $P_{j}$ (Watts) transmission powers respectively. $\hbox {Rx}_i$ listens to the Tx OFDM block and measures received signal strengths of the DP signals from Tx$_i$ and Tx$_j$ as $P_{i} \cdot |h_{ii}|^{2}$ and $P_{j} \cdot |h_{ji}|^{2}$ (Watts). Then, if SIR for its connection $i$ satisfies:

$$\begin{aligned} {{P_{i} \cdot |h_{ii}|^{2}}\over {P_{j} \cdot |h_{ji}|^{2}}} > \gamma _{\rm Rx}, \end{aligned}$$

(1)

$\hbox {Rx}_i$ considers that the transmission from its peer $\hbox {Tx}_i$ is possible, where $\gamma _{\rm Rx}$ is a predefined threshold. Upon deciding that the transmission is possible, $\hbox {Rx}_i$ transmits IPE signal through $\eta _i$th RE in the following Rx OFDM block. This IPE signal serves as a response to Tx$_i$’s DP signal. On the contrary, if the condition given in (1) is not satisfied, $\hbox {Rx}_i$ yields to connection $j$ and does not transmit the IPE signal. This phenomenon is known as Rx-yielding.

If there exist multiple connections having the higher priorities in close vicinity of connection $i$, (1) can be expanded as:

$$\begin{aligned} {{P_{i} \cdot |h_{ii}|^{2}}\over {\sum _{l \in \mathbb {S}_{\rm DP}, i}\left( P_{l} \cdot |h_{li}|^{2}\right) } }> \gamma _{\rm Rx} , \end{aligned}$$

(2)

where $\mathbb {S}_{{\rm DP}, i}$ is a set of connections that send DP signals in the Tx OFDM block and have higher priorities than the connection $i$ ($\eta _i >\eta _l$, $\forall l \in \mathbb {S}_{{\rm DP},i}$) [10].

2.2 Tx-yielding decision

Tx-yielding decision enables a low priority connection (in this case connection $i$) to determine its impact on high priority connections in its close vicinity (in this case connection $j$). This decision is based on IPE signal sent by Rx$_j$ with signal power ${K/ ({P_{j} \cdot |h_{jj}|^{2}})}$ (Watts), where $K$ is a system constant.¹ This IPE signal is received by Tx$_i$ as the power of $r_{ji} ={ |h_{ij}|^{2} \cdot K /({P_{j} \cdot |h_{jj}|^{2}})}$ (Watts). From this, Tx$_i$ can estimate SIR of the connection $j$ as:

$$\begin{aligned} \left( r_{ji} \cdot {P_{i}\over K} \right) ^{-1} \approx {{P_{j} \cdot |h_{jj}|^{2}} \over {P_{i} \cdot |h_{ij}|^{2}}}. \end{aligned}$$

(3)

If the estimated SIR satisfies:

$$\begin{aligned} \left( r_{ji} \cdot {P_{i}\over K} \right) ^{-1} > \gamma _{\rm Tx}, \end{aligned}$$

(4)

Tx$_i$ considers that its transmission to $\hbox {Rx}_i$ is possible. On the contrary, if the condition given in (4) is not satisfied, it follows that connection $i$ may reduce the SIR of connection $j$ below the predefined threshold $\gamma _{\rm Tx}$. Therefore, Tx$_i$ gives up its transmission during the current TCCH frame (Tx-yielding). For a network with multiple connections, the condition given in (4) can be expanded as:

$$\begin{aligned} \left( r_{li} \cdot {P_{i}\over K} \right) ^{-1} > \gamma _{\rm Tx}, \forall l \in \mathbb {S}_{{\rm IPE}, i}, \end{aligned}$$

(5)

where $\mathbb {S}_{{\rm IPE}, i}$ is a set of connections that send IPE signal in the Rx OFDM block and have higher priorities than the connection $i$ ($\eta _i>\eta _l$, $\forall l \in \mathbb {S}_{{\rm IPE},i}$) [10].

3 Problem statement and related works

3.1 Cascade yielding problem in SBMA

This section introduces the concept of maximal matching that is intended for SBMA. Let us denote $\mathbb {L}$ as a set of D2D connections simultaneously accessing the shared medium in the same TCCH frame and $|\mathbb {L}|$ as the number of D2D connections in $\mathbb {L}$, where the cardinality of a set ($|\cdot |$) denotes the number of elements in the set. SBMA intends to maximize $|\mathbb {L}|$ while satisfying Rx- and Tx-yielding constraints in (2) and (5) for all connections in $\mathbb {L}$. The optimal $\mathbb {L}$ can be obtained by determining the medium accessibility of each connection sequentially (from the connection with the highest priority to the connection with the lowest priority). The procedure for obtaining optimal $\mathbb {L}$ in a certain TCCH frame is shown in Algorithm 1, where $\mathbb {M}$ denotes a set of connections attempting data transmission in the same TCCH frame and $R_{ij}$ denotes $P_{i} \cdot |h_{ij}|^{2}$ (Watts).

In distributed D2D communications, optimal $\mathbb {L}$ is practically difficult to be computed by each device because the sequential determinations of devices’ medium accessibility is very time consuming. For example, in the system introduced in Sect. 2, $2 \cdot |\mathbb {M}|$ OFDM symbol durations are required for the sequential determinations in $|\mathbb {M}|$ connections. This is because (1) each connection requires two OFDM symbol durations for exchanging DP and IPE signals to enable SIRs calculations and (2) the transmissions of DP and IPE signals in $|\mathbb {M}|$ connections are performed in different OFDM symbol durations. In order to enable determination of medium accessibility in a shorter time duration, SBMA adopts Tx and Rx OFDM blocks (see Fig. 2) and allows multiple devices to simultaneously determine their connections’ medium accessibility. This operation results in cascade yielding problem, where some connections unnecessarily back off their medium access even when they satisfy both constraints of SBMA.

Let us consider D2D connections 1, 2, and 3 ($\eta _1<\eta _2<\eta _3$) shown in Fig. 4 to explain the cascade yielding problem in SBMA technique. All Tx devices shown in the figure intend to transmit data to their corresponding Rx devices in the same TCCH frame. In this case, all Tx devices transmit DP signals in the Tx OFDM block and follow the SBMA procedure explained in Sect. 2. It is assumed that Rx$_2$ and Rx$_3$ yield to connections 1 and 2 respectively due to the differences in connection priorities and interference from the neighboring connections. Therefore, connection 2 (connection 3) has to back off medium access if connection 1 (connection 2) accesses the medium. In this case, if Tx- and Rx-yielding decisions for connections 1, 2, and 3 are made sequentially, both connections 1 and 3 can access the medium during the current TCCH frame. However, in legacy SBMA, because all Tx and Rx devices have to perform Tx- and Rx-yielding decisions in parallel, connection 3 yields to connection 2, even though connection 2 will give up the medium access due to connection 1. Consequently, both connections 2 and 3 will back off and only connection 1 accesses the medium during the current TCCH frame. This problem is known as the cascade yielding problem [18].

Fig. 4

A scenario resulting in cascade yielding problem

3.2 Related works

Several studies have been conducted to reduce the occurrence of cascade yielding in SBMA [10, 18]. SBMA allows an iterative method for Tx- and Rx-yielding as an optional feature in order to reduce cascade yielding phenomenon [10]. The iterative method allows D2D connections to perform multiple iterations of medium access decision in each medium access decision. For the purpose, in the iterative method, more than one pair of Tx and Rx OFDM blocks are allocated in each TCCH frame. All connections perform Tx- and Rx-yielding decisions in multiple iterations rather than in a single attempt. In each iteration, Tx and Rx devices in each connection calculate a new value of SIR for their own connection as well as the estimated SIR values of its neighboring connections without considering the neighboring connections that have already yielded in the previous iteration. Based on the calculations of SIRs, the conditions given in (2) and (5) are examined. By allowing exclusion of connections that have already yielded during the previous iterations in the calculations of SIRs, the iterative method can reduce the occurrence of cascade yielding. However, the iterative method with $N_{{\rm iter}}$ iterations of medium access decision requires an additional allocation of $N_{{\rm iter}} - 1$ pairs of Tx and Rx OFDM blocks. Each pair occupies 102.4 $\upmu$s, which is approximately 5.12 % of the length of a TCCH frame. Consequently, the duration of data transmission in one TCCH frame is reduced by $N_{{\rm iter}}\,\times \,102.4\,\upmu$s for the iterative method with $N_{{\rm iter}}$ iterations. It is likely to reduce the throughput of D2D connections.

Cho et al. propose a multilevel thresholding technique in [18] to reduce the occurrence of cascade yielding in SBMA. In this technique, Rx device performs Rx-yielding decision for multiple iterations in each TCCH frame, while Tx device does not perform Tx-yielding decision. This excludes only the neighboring connections, which will not simultaneously transmit data, from the calculation of the SIR of its own connection. Moreover, this technique uses a different SIR threshold value for determining medium access in each iteration. Consequently, the D2D connections having lower SIRs are preemptively backed off in favor of high SIR connections. This improves the possibility of medium access for the D2D connections that have higher SIRs, because the D2D connections having lower SIRs are preemptively backed off in favor of D2D connections having higher SIR. However, this can reduce fairness in terms of medium accessibility of D2D connections, since the D2D connections with relatively low SIR may hardly transmit their data. Performing only Rx-yielding decision in the multilevel thresholding technique may increase interference from D2D connections with low priorities to those with high priorities. This is because each D2D connection does not consider effects of its transmission on the neighboring connections with higher priorities. Like the iterative method reported in [10], the multilevel thresholding technique with $N_{{\rm iter}}$ levels may reduce the throughput of D2D communications, because it requires $N_{{\rm iter}}-1$ additional Rx OFDM blocks for enabling $N_{{\rm iter}}$ iterations of the Rx-yielding decisions. Note that each Rx OFDM block occupies 51.2 $\upmu$s, which is approximately 2.56 % of the length of a TCCH frame. Finding a new value of SIR threshold for each iteration may be difficult in the multilevel thresholding technique, because the optimal threshold value varies according to the network environment. Parameters like the number of D2D connections in an area and channel conditions may affect the SIR threshold value.

4 SIR-based multiple access with cascade yielding avoidance

In order to avoid cascade yielding problem without a large overhead and to achieve improved maximal matching, we propose SBMA with cascade yielding avoidance (SBMA/CYA) technique in this paper. Like the conventional SBMA, the proposed SMBA/CYA operates on the wireless PHY/MAC network architecture introduced in [10]. SBMA/CYA enables devices to predict whether a neighboring connection contending for the same medium shall yield to some other connection or not by using YRIs. Based on the predictions, SBMA/CYA helps each device to more accurately estimate SIR of its own connection as well as SIRs of adjacent connections. The proposed technique is possible to further reduce the occurrence of the cascade yielding in comparison with the iterative method used in conventional SBMA [10]. Moreover, different from the methods in [10] and [18], the proposed SBMA/CYA technique does not require multiple iterations of medium access decisions in each medium access period. SBMA/CYA requires only one additional OFDM block (51.2 $\upmu$s) in a TCCH frame for gathering the YRIs.

The functionality of SMBA/CYA may be split into two parts: (1) it develops a method for gathering YRIs for neighboring connections and (2) it proposes enhanced Tx- and Rx-yielding decision making procedures that do not consider negligible connections.

4.1 Gathering yielding relationship indicator (YRI) in SBMA/CYA

YRI is utilized in Rx- and Tx-yielding decisions to identify negligible connections that should be excluded in the calculations of SIRs. A new OFDM block, scheduling results broadcasting (SRB) block, has been defined to gather YRIs for neighboring connections. It can be seen from Fig. 5 that SRB block has the same structure as the usual Tx (or Rx) OFDM block. Recall that the yielding decisions are finalized after IPE signals are transmitted in the Rx OFDM blocks. An additional SRB block after Rx OFDM block indicates which Tx devices have not yielded and are ready to transmit on the shared medium. Tx devices that have not yielded to other connections transmit DP signals in their respective REs of the SRB block. Like Tx (and Rx) OFDM blocks, different devices are assigned different REs in SRB block based on their priorities. This additional SRB block shortens the length of data transmission time by 51.2 $\upmu$s.

Fig. 5

Scheduling results broadcasting (SRB) block

For managing the YRIs, each device stores and updates W, a square matrix of dimension 112$\times$112 with $w_{ij} \in \{-1,0,1\}$. The value of YRI $w_{ij}$ indicates whether connection $i$ can access the medium ($w_{ij}=1$) without violating the SIR constraints of SBMA (2 and 5) if connection $j$ with the higher priority ($\eta _{j} < \eta _{i}$) accesses the medium. $w_{ij}=0$ indicates that connection $i$ cannot access the medium in the presence of connection $j$. All elements in the matrix except $w_{ij}$ for $i$ = $j$ are initialized to ‘$-$1’, where $w_{ij}=-1$ implies that the relationship between connections $i$ and $j$ has not been identified. It is obvious that $w_{ij}$ for $i$ = $j$ is always ‘1’ because a connection would not back off due to its own transmission.

Procedure of updating W in every TCCH frame is shown in Algorithm 2. At the beginning of each TCCH frame, each device firstly determines whether it already has formed W or not. If the device has not formed W, it initializes W as $w_{ij}=1$ for all $i=j$ and $w_{ij}=-1$ for all $i\ne j$. Then, each device identifies priorities of all connections ($\eta _{j}$, $1\le \eta _{j} \le 112$) in order to know the REs used by itself and neighboring connections in Tx, Rx, and SRB OFDM blocks of the current TCCH frame. After determining respective REs, devices identify a set of connections that simultaneously attempt medium access ($\mathbb {S}_{{\rm AL}}$) through observing Tx or Rx OFDM block. Upon receiving the SRB block, all devices, except Tx devices transmitting DP signals in the SRB block, identify a set of connections that have transmitted DP signals in the SRB block ($\mathbb {S}_{{\rm SRB}}$).

Next, all devices determine the connections with the highest priority ($j^{*}$) and second highest priority ($j^{**}$) in $\mathbb {S}_{{\rm SRB}}$, such that $j^{*}={{\rm arg}} \min _{j \in {\mathbb {S}_{{\rm SRB}}}} \eta _j$ and $j^{**}={{\rm arg}} \min _{j \in {\mathbb {S}_{{\rm SRB}}} - \{j^{*}\}} \eta _j$. Finally, the YRIs are determined as follows:

• $w_{ij} = 1\,\,{\rm for all}\,\,i, j \in \mathbb {S}_{{\rm SRB}}$, because all connections in $\mathbb {S}_{{\rm SRB}}$ can concurrently access the shared medium.

• $w_{ij^*}=0$ if $i \in \mathbb {S}_{{\rm AL}}\cap (\mathbb {S}_{{\rm SRB}})^{\rm c}$ and $\eta _{j^*}<\eta _{i}<\eta _{j^{**}}$, where $(\cdot )^{{\rm c}}$ is operator for set complement. This is because the connection $i$ has yielded only due to connection $j^*$. Note that the medium access of connections with priorities lower than $\eta _{j^{**}}$ are restricted by more than one connections. Hence these relationships cannot be identified in the current TCCH frame.

The devices update their relationship matrix W by continually observing SRB blocks in every TCCH frame. The extent to which cascade yielding problem is avoided depends on how updated the entries in the W matrix are.

4.2 Medium access decisions of SBMA/CYA

Based on the matrix W representing YRIs for neighboring connections, each device performs Rx- or Tx-yielding decision in each TCCH frame without considering neighboring connections that will Rx- or Tx-yield due to other high prioritized connections. The disregard of the connections expected to yield helps devices to avoid unnecessary deferment of medium access through enabling more accurate estimations of SIRs in yielding decisions. The followings describe the procedures of Rx- and Tx-yielding decisions based on the YRIs.

At the beginning of each TCCH frame, Tx devices willing to access the medium transmit DP signals in the Tx OFDM block. Upon observing the Tx OFDM block, $\hbox {Rx}_i$, which has detected DP signal from Tx$_i$, performs Rx-yielding decision as follows:

• $\hbox {Rx}_i$ identifies $\mathbb {S}_{{\rm DP}, i}$, which is a set of connections which have transmitted DP signals in the Tx OFDM block and have higher priorities than the connection $i$.

• Among the connections contained in $\mathbb {S}_{{\rm DP}, i}$, $\hbox {Rx}_i$ identifies the connection having the highest priority as $j^{*}_{{\rm DP}}={{\rm arg}} \min _{j \in {\mathbb {S}_{{\rm DP}, i}}} \eta _j$.

• $\hbox {Rx}_i$ identifies a connection having the second highest priority among the connections that will not yield to connection $j^{*}_{\rm DP}$ as $j_{{\rm DP}}^{**} ={{\rm arg}} \min _{j} \eta _j$, where $j \in {\mathbb {S}_{{\rm DP}, i}} - \{j_{{\rm DP}}^{*}\}$ and $w_{jj^*_{DP}} \ne 0$.

• $\hbox {Rx}_i$ identifies a set of connections expected to Tx- or Rx-yield in the current TCCH frame as:

  $$\begin{aligned} \mathbb {D}_{{\rm DP},i}=\{j|j\in \mathbb {S}_{{\rm DP}, i}\,{\rm and}\,w_{jj_{{\rm DP}}^{*}} \cdot w_{jj_{{\rm DP}}^{**}} = 0 \}. \end{aligned}$$

  (6)

• Finally, $\hbox {Rx}_i$ performs Rx-yielding decision as:

  $$\begin{aligned} {{P_{i} \cdot |h_{ii}|^{2}}\over {\sum _{l \in \left( \mathbb {S}_{{\rm DP},i} - \mathbb {D}_{{\rm DP},i} \right) }P_{l} \cdot |h_{li}|^{2}}} > \gamma _{{\rm Rx}}, \end{aligned}$$

  (7)

  and transmits IPE signal in Rx OFDM block only if the condition (7) is satisfied.

Note that only the connections which will yield to the connection $j_{{\rm DP}}^{*}$ or connection $j_{{\rm DP}}^{**}$ are identified and excluded from SIR calculation in (7). This is because $\hbox {Rx}_i$ cannot identify whether the connections having lower priorities than $j_{{\rm DP}}^{**}$ can simultaneously access the medium in presence of $j_{{\rm DP}}^{*}$ and $j_{{\rm DP}}^{**}$. If the total interference from ${{\rm Tx}}_{j_{{\rm DP}}^{*}}$ and ${{\rm Tx}}_{j_{{\rm DP}}^{**}}$ is higher than a certain value, connection $k$ (which has a lower priority than connection $j_{\rm DP}^{**}$) may yield even when both $w_{kj_{\rm DP}^{*}}$ and $w_{kj_{\rm DP}^{**}}$ are equal to ‘1’.

Upon reception of Rx OFDM block, Tx$_i$ determines whether $\hbox {Rx}_i$ has transmitted IPE signal or not. Tx$_i$ decides to back off if the IPE signal from $\hbox {Rx}_i$ is not detected in the Rx OFDM block. If the IPE signal from $\hbox {Rx}_i$ is detected, Tx$_i$ performs Tx-yielding decision as follows:

• Tx$_i$ receiving IPE signal from $\hbox {Rx}_i$ identifies $\mathbb {S}_{{\rm IPE},i}$, a set of connections which have transmitted IPE signal in the Rx OFDM block and have higher priorities than connection $i$.

• Among $\mathbb {S}_{{\rm IPE},i}$, Tx$_i$ finds the connection having the highest priority as $j^{*}_{\rm IPE}={\rm arg} \min {j \in {\mathbb {S}_{{\rm IPE},i}}} \eta _j$.

• Tx$_i$ identifies the connection having second highest priority among the connections in $\mathbb {S}_{{\rm IPE},i}$ expected to concurrently access the medium with connection $i^{*}_{\rm IPE}$ as $j_{\rm IPE}^{**} ={\rm arg} \min _{j} \eta _j$, where $j \in {\mathbb {S}_{{\rm IPE},i}} - \{j_{\rm IPE}^{*}\}$ and $w_{jj^*_{IPE}} \ne 0$.

• Tx$_i$ identifies a set of connections expected to give up the medium access in the current TCCH frame as:

  $$\begin{aligned} \mathbb {D}_{{\rm IPE},i}=\{j|j\in \mathbb {S}_{{\rm IPE},i}\,{\rm and} w_{jj_{\rm IPE}^{*}} \cdot w_{jj_{\rm IPE}^{**}} = 0 \}. \end{aligned}$$

  (8)

• Tx$_i$ performs Tx-yielding decision as

  $$\begin{aligned} \left\{ r_{li} \cdot {P_{i}\over K} \right\} ^{-1}> \gamma _{\rm Tx}, \forall l \in \left( \mathbb {S}_{{\rm IPE},i} - \mathbb {D}_{{\rm IPE},i} \right) , \end{aligned}$$

  (9)

  and transmits pilot signal in the rate scheduling period if the condition given in (9) is satisfied. If the condition (9) is not satisfied, Tx$_i$ gives up its medium access in the current TCCH frame.

5 Performance evaluation

This section reports the C++ based simulation results in order to evaluate the performance of the proposed SBMA/CYA.² The simulation setup is a 3-by-3 grid of nine square planes, such that each plane has an area of 1 ${\rm km}^2$. The number of D2D connections that are uniformly distributed in each plane is given by $N_{\rm c}$. In order to remove the boundary effect, the simulation results are obtained from the devices located in the center plane of the grid. Note that SIR calculations for devices located at the center plane consider interferences from other devices in surrounding planes. Distance between Tx and Rx devices of each D2D connection is uniformly determined from the range [1, $d_{\rm max}$] m. We consider saturated traffic condition, where Tx devices of all connections always have data to transmit. Each simulation run lasts for 1,000 s, where positions of all devices are rearranged at every 10 s. ITU-R outdoor upper bound model [22] is used for calculating the path loss between two devices. The discrete spectral efficiency look up table, as given in [23], is used to obtain spectral efficiency (bps/Hz) of a wireless channel having a certain SINR. For fair comparison, we set the values of the simulation parameters in Table 1 same as those in [10].

The performance of SBMA/CYA is compared with the legacy SBMA scheme that uses iterative method ($N_{\rm iter} =1$, 4, and 8) as given in [10]. The performance for optimal $\mathbb {L}$, which is obtained from Algorithm 1 through sequentially determining connections’ medium accessibility, is also compared with that of proposed SBMA/CYA. In order to obtain the optimal $\mathbb {L}$, it has been assumed that all devices can identify medium access results of other high-priority connections via a single pair of Tx and Rx OFDM blocks. For the comparisons, all Tx devices use the same transmission power $P_{\rm Tx}$. Note that the multilevel thresholding technique in [18] is not evaluated in this paper, because the method for determining SIR threshold values for different iterations and environments is not specified. Instead, we discuss the expected performance of the multi-level thresholding technique, in terms of fairness index for data rates, signal interference, and throughput, in Sect. 3.2.

Table 1 Simulation parameters

In order to evaluate the effectiveness of SBMA/CYA, we evaluate the average number of connections concurrently transmitting data on the shared medium in each TCCH frame. The simulation results as varying $N_{\rm c}$ have been shown in Fig. 6. The optimal $\mathbb {L}$ enables medium access of all connections satisfying the Tx- and Rx-yielding conditions in SBMA without cascade yielding. Therefore, it can be seen from the figure that the optimal $\mathbb {L}$ achieves the highest results. In the conventional SBMA, some of connections unnecessarily give up their medium access due to the cascade yielding problem. As the result, legacy SBMA with $N_{\rm iter} = 1$ achieves the lowest results. It must be noted that the goal of iterative SBMA ($N_{\rm iter}=4\,and\,8$) is same as that of SBMA/CYA. However, from a set of connections that have decided to yield, iterative SBMA excludes only a few from SIR calculations. Thus, it cannot highly improve the number of concurrent transmissions in comparison with legacy SBMA ($N_{\rm iter}=1$). SBMA/CYA allows more devices to concurrently access the shared medium in comparison with legacy SBMA schemes. This is because SBMA/CYA does not include the yielded connections in the SIR calculations by distinguishing between the connections that shall and shall not yield to the highest and second highest priority connections. Thus, SBMA/CYA reduces the occurrence of cascade yielding. Also note that as $N_{\rm c}$ increases, the frequency of cascade yielding increases. Because SBMA/CYA can relieve more devices from the cascade yielding, the gap between the results of SBMA/CYA and SBMA widens as $N_{\rm c}$ increases.

Fig. 6

Average number of concurrent transmissions as varying $N_{\rm c}$. a $d_{\rm max}$ = 300 m, b $d_{\rm max}$ = 500 m

The mean number of connections concurrently accessing the shared medium in each TCCH frame with different values of $d_{\rm max}$ is shown in Fig. 7. It can be seen that the number of concurrent transmissions decreases as $d_{\rm max}$ increases. On the one hand, for a smaller $d_{\rm max}$, the connections have higher probability to access the shared medium over shorter distances with higher SIRs. Note that high SIRs reduce the occurrence of Rx- and Tx-yieldings. On the other hand, for a higher $d_{\rm max}$, some connections may have low SIRs due to a longer separation between Tx device and its peer Rx device. It follows that Rx- and Tx-yieldings occur more frequently in the environments with higher $d_{\rm max}$. Moreover, since cascade yielding due to the highest and second highest priority connections frequently occurs for higher $d_{\rm max}$, the gain of SBMA/CYA increases as $d_{\rm max}$ increases. For $d_{\rm max}$ = 1,000 (m), the number of connections concurrently accessing the medium increases by 83.9 % in SBMA/CYA in comparison with the legacy SBMA with $N_{\rm iter}$ = 1.

Fig. 7

Average number of concurrent transmissions for $N_{\rm c}$ = 80 as varying $d_{\rm max}$

The achieved total throughput with varying $N_{\rm c}$ has been shown in Fig. 8. Total throughput is defined as the sum of throughputs for all $N_{\rm c}$ connections. Difference between the total throughputs for optimal $\mathbb {L}$ and SBMA/CYA is smaller than the difference between the numbers of concurrent transmissions for those cases. This is because, even though more connections can simultaneously access the medium with optimal $\mathbb {L}$, the enhancement of throughput is limited by the increased interferences among the connections. By reducing cascade yielding, SBMA/CYA achieves higher total throughput as compared to the legacy SBMA. This improved performance has been observed despite the fact that the data segment transfer period of each TCCH frame is reduced by 51.2 $\upmu$s due to the addition of the SRB block. This is because the performance improved by the mitigation of cascade yielding is higher than the performance degradation caused by shortening the length of the data transmission time. It can be seen that the total throughputs for iterative SBMA ($N_{\rm iter}$ = 4 and 8) are less than that of legacy SBMA ($N_{\rm iter} = 1$). The total throughput of iterative SBMA with $N_{\rm iter}$ = 8 is less than that of iterative SBMA with $N_{\rm iter} = 4$. This is because the performance degradation caused by the allocation of additional pairs of Tx and Rx OFDM blocks ($3\,\times \,102.4\,\upmu$s for $N_{\rm iter}$ = 4 and $7\,\times \,102.4\,\upmu$s for $N_{\rm iter} = 8$) to detect connections that have yielded is higher than the performance improved by the mitigation of cascade yielding in iterative SBMA.

Fig. 8

Total throughput as varying $N_{\rm c}$. a $d_{\rm max}$ = 300 m, b $d_{\rm max}$ = 500 m

The average MAC delays for the connections with optimal $\mathbb {L}$, SBMA/CYA, SBMA with $N_{\rm iter} = 1$, 4, and 8 are shown in Fig. 9. MAC delay is defined as the time duration required for a MAC frame to be successfully transmitted after it is placed at the top of the transmission buffer. SBMA/CYA helps each connection to transmit data more frequently than legacy SBMA by helping the connection to avoid cascade yielding. Thus, SBMA/CYA results in lower MAC delay than the legacy SBMA as shown in Fig. 9.

Fig. 9

Average MAC delay as varying $N_{\rm c}$. a $d_{\rm max}$ = 300 m, b $d_{\rm max}$ = 500 m

In order to investigate the effects of SBMA and SBMA/CYA on the fairness among connections in terms of throughputs, we evaluate Jain’s fairness index [24]. The results are shown in Fig. 10. In the legacy SBMA with $N_{\rm iter} = 1$, 4, and 8, only some of the connections having higher priorities can communicate in each TCCH frame due to cascade yielding problem. On the contrary, by allowing more connections to concurrently communicate with the high priority connections, SBMA/CYA increases the throughputs of the connections having relatively lower priorities. Consequently, SBMA/CYA can achieve higher fairness in terms of throughputs in comparison with the legacy SBMA schemes.

Fig. 10

Fairness index as varying $N_{\rm c}$

6 Conclusion

In this paper, an enhanced SBMA technique, named SBMA/CYA, has been proposed to enhance the utilized of wireless medium through reducing occurrence of cascade yielding. In the proposed SBMA/CYA scheme, YRIs for neighboring connections are firstly acquired through the newly introduced SRB OFDM block. These relationships are then utilized by the connections in making medium access decisions. It has been shown via simulation results that SBMA/CYA can improve the number of connections concurrently accessing the shared medium by 83.9 % in comparison with the legacy SBMA. This has been made possible by mitigating the cascade yielding problem. Performance indicators such as average number of concurrent transmissions, total throughput, MAC delay and fairness index have verified the performance of SBMA/CYA.