# Capacity Enhancement in 60 GHz Based D2D Networks by Relay Selection and Scheduling

Authors: Waheed ur Rehman; Tabinda Salam; Jin Xu; Xiaofeng Tao
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

Millimeter-wave or 60 GHz communication is a promising technology that enables data rates in multigigabits. However, its tremendous propagation loss and signal blockage may severely affect the network throughput. In current data-centric device-to-device (D2D) communication networks, the devices with intended data communications usually lay in close proximity, unlike the case in voice-centric networks. So the network can be visualized as a naturally formed groups of devices. In this paper, we jointly consider resource scheduling and relay selection to improve network capacity in 60 GHz based D2D networks. Two types of transmission scenarios are considered in wireless personal area networks (WPANs), intra and intergroup. A distributed receiver based relay selection scheme is proposed for intragroup transmission, while a distance based relay selection scheme is proposed for intergroup transmission. The outage analysis of our proposed relay selection scheme is provided along with the numerical results. We then propose a concurrent transmission scheduling algorithm based on vertex coloring technique. The proposed scheduling algorithm employs time and space division in mmWave WPANs. Using vertex multicoloring, we allow transmitter-receiver (Tx-Rx)  communication pairs to span over more colors, enabling better time slot utilization. We evaluate our scheduling algorithm in single-hop and multihop scenarios and discover that it outperforms other schemes by significantly improving network throughput.


---

## Body

## 1. Introduction

The demand for high-bandwidth applications in the recent years has been growing exponentially. The high-speed Internet has raised users expectations to a level, where they are impatient to wait for their data communication requests. 60 GHz communication network promises data rate in gigabits and can be used in both indoor [1] and outdoor scenarios [2]. Device-to-device (D2D), being an emerging technology, helps offload the data from the central node by encouraging direct communication between transceivers. Both 60 GHz and D2D are also seen as enablers for 5G networks [3, 4]. The confluence of 60 GHz with D2D communication can be seen as paragon that satisfies users quality of experience [5] by enhancing network capacity.One of the unique characteristics of 60 GHz networks is its tremendous propagation loss which severely affects the data rates. However, unlike traditional networks [6], this characteristic reduces the impact of interference in  60 GHz. Propagation loss coupled with shortage of multipath signals entails the use of line-of-sight (LOS) communication to achieve higher data rates. Directive antennas are employed to cater for propagation loss and attaining data rates in multigigabits. However, directive antennas result in another nuisance, a signal blockage which may result in signal attenuation up to 40 dB [7]. The network capacity in 60 GHz networks is severely affected by signal blockage and propagation loss. Beamforming (BF) [8–10] can partially rectify the signal blockage problem by steering the signal around the obstacle rather than burning through them. However, in BF, neighbor discovery procedure normally requires significant time for signaling. Thus, system throughput is significantly affected in dense deployment.The use of relays in 60 GHz based D2D networks provides an alternative for signal blockage. Relays not only help in signal blockage but also reduce the tremendous propagation loss [11]. The effect of distance in 60 GHz networks is detrimental as compared to networks operating at lower frequencies. Relays partition a communication link into shorter distances and help achieve the so-called “distance gain.”In short-ranged data-centric communication network, the premise that two parties initiate communication to be in close proximity is acceptable contrary to voice-centric networks. Rather, it would be common to have a situation where several co-located devices (DEVs) would like to share contents such as digital pictures or interact for applications such as video gaming and social networking [12]. As a result, the network can be visualized as naturally formed groups rather than DEVs scattered randomly. In such scenario, usually the transmitter and receiver (Tx,Rx) pair stays for the duration of their transmission. Examples may include file transfer kiosk, home entertainment system, where sound system, HD TV, and gaming devices are in close proximity, along with the people intending to communicate with them. Two types of communication may be seen in such scenario, intra and intergroup transmission. Due to the rationale behind such grouping, it can safely be assumed that most of the times nearby devices would be involved in data communications with occasional distant devices. We devised two algorithms, each for intra and intergroup communication, respectively. A receiver based distributed algorithm is proposed for intragroup communication, while a centralized algorithm is proposed for intergroup transmission. In order to further improve network throughput, we have also proposed a concurrent transmission scheduling algorithm that works jointly with relay selection schemes. It is also argued that network throughput in such short-ranged networks mainly depends on scheduling scheme rather than transmission power control [13], which makes it imperative to have an efficient resource allocation scheme.The main contributions of this paper include the following.(1) To enhance network capacity in order to meet demands of bandwidth craving applications, we have proposed two relay selection algorithms: a novel distributed relay selection scheme for intragroup transmission, where DEVs can effectively select a relay by exploiting the directional nature of  60 GHz based D2D networks, and also simple but an effective intergroup relay algorithm. Both algorithms try to find the midmost relay and try to select the relay to maximize distance gain. (2) Capacity analysis is provided by utilizing our proposed relay selection algorithms in conjunction with our proposed concurrent transmission scheduling algorithm in [5]. The scheduling algorithm is modified to cater multihop scenario. The simulation results show that our proposed algorithms significantly improve the network capacity in single- and multihop scenarios. Multihopping in 60 GHz based D2D networks helps increase the network throughput by encouraging concurrent transmissions. However, induced complexity and varying relay distances may seriously affect the end-to-end data rate of an individual flow. Applications with higher throughput requirement such as uncompressed high-definition videos and real-time audio/video applications have stringent quality of service requirements. Since links in mmWave require high data rate, too many hops that exhibit uniform characteristics are very challenging and can seriously affect the individual flows. Therefore, we are considering a two-hop scenario. Furthermore, we are considering an indoor scenario such as home or office where multiple hops may not be feasible. In this paper two-hop and multihop are interchangeably used.The rest of the paper is organized as follows. Section2 provides an overview of related relay selection and scheduling algorithm research work in 60 GHz networks followed by system model in Section 3. The detailed discussion of our proposed relay selection schemes and scheduling algorithm is provided in Section 4. Numerical results to compare our proposed schemes are given in Section 5, followed by conclusion in Section 6.


## 2. Related Work

Relay selection and scheduling algorithm for 60 GHz have generated sizable literature [7, 11, 14–22] in recent years. Both efforts are made to achieve one goal: capacity enhancement, either directly or indirectly. The first analytical and simulated study on the use of relays in 60 GHz is provided in [11]. The paper shows that at least 33% of free space path loss can be improved by using relays. The paper also signifies the proper positioning of the relay. However, the simulation results are provided on the basis of grid topology and fixed relays, mostly positioned on ceiling. Centralized relay selection approach is proposed in [7], where each sender DEV knows two paths to the destination, direct and relay path. The relay path is discovered in advance and in case of blockage, the data would “deflect” through relay node. Minimum cochannel interference is considered as selection metric. In [15], a relay selection scheme is proposed based on distance and traffic load. The authors propose to replace a long direct path with several multihop paths to improve the network throughput. A diffraction based model to determine network link connectivity is also studied in [16]. It is shown that the proposed multihop protocol works with highly directional antenna arrays and is able to maintain high network utilization with low overhead. Use of beam sectors is proposed in [17] to discover an effective relay. However, the proposed scheme is centralized and involves higher overhead and complexity. A joint relay selection and analog network coding over two-way relay channels are proposed in [23]. In the proposed relay selection amplify-and-forward (RS-AF) scheme, two source nodes first transmit to all the relays at the same time. The selected relay then broadcasts the signal back to both sources to achieve a minimum sum symbol error rate (SER). A suboptimal Max-Min criterion is proposed to facilitate the selection process, where a single relay which minimizes the maximum SER of two source nodes will be selected.Apart from relay selection, scheduling algorithms are also proposed for capacity enhancement in conjunction with/without relay selection. More recently in 60 GHz networks, concurrent transmission is encouraged due to its highly directional nature. The concept of concurrent transmission is not new, but coupled with the directional antenna and short-range nature of 60 GHz networks, its effectiveness can be multifolded. The case of concurrent transmission scheduling has been investigated extensively in the literature [18–22]. The authors in [18] propose a hybrid SDMA/TDMA scalable heuristic scheduling scheme for throughput enhancement in practical mmWave systems. The authors in [19] propose an opportunistic spatial reuse algorithm to allow concurrent transmission in 802.15.3c networks. In [20], the authors define an exclusive region (ER) condition to support concurrent transmission. They further propose a randomized exclusive region (REX) based scheduling scheme for resource allocation. However, REX is a randomized scheduling scheme with unpredictable iteration times based on greedy algorithm (GA). Qiao et al. present a multihop concurrent transmission algorithm in mmWave WPAN [21]. The proposed multihop algorithm improved the network throughput as compared to single-hop concurrent transmission. The authors in [22] propose a concurrent transmission algorithm based on DEVs locations. Upon collecting coordinates and transmission requests of DEVs, piconet network controller (PNC) schedules noninterfered flows in the same time slot.


## 3. System Model

A network based on 802.15.3c with dense deployment of DEVs is considered with one central DEV called PNC. Initially, DEVs are distributed randomly with a PNC in the center with quasi-omni transmission. Over time, due to the tendency of(Tx,Rx) pair to come close, WPAN has naturally formed groups, as shown in Figure 1. It is observed that in such scenarios the communicating DEVs usually stay for the duration of their transmission. Direct transmission is preferred for intragroup transmission. However, if the signal is blocked or the interference at certain antenna element gets greater than a defined threshold, an appropriate relay would be selected, distributively. A DEV may choose to send data to a distant DEV(s), in which case an intergroup relay selection scheme would be initiated by PNC, selecting an appropriate relay to facilitate the transmission.Figure 1
System model for typical D2D WPAN.


### 3.1. Quasi-Omni Transmission for PNC

Devices in 802.15.3c suffer from high path loss at  60 GHz frequency band. Therefore, they should focus radiant energy for the data transmissions in the intended direction. Similarly, they may concentrate on the energy for data receptions at a specific direction to gather more power, making it necessary to employ directional communication technologies at the  60 GHz frequency band. The PNC in 802.15.3c should broadcast beacons in all directions since every device connected with the PNC should receive the beacons for proper operations. Quasi-omni is a directional transmission, but it mimics omnidirectional transmission by consecutively rotating its transmission direction through360° [24]. In the 802.15.3c WPANs, the PNC can adopt quasi-omni transmissions for broadcast message transmissions.


### 3.2. Antenna Model

Highly directional antenna is considered for our model. Directional antennas fall in two categories [25], sectored/switched antenna array and adaptive antenna array. We are considering the former that can intelligently put a main beam in the direction of the desired signal and nullifies in the directions of the interference. In [26], Mudumbai et al. also concluded that a mmWave link can be abstracted as a pesudowired link, which shows support for our flat-top antenna model.Every DEV employs an antenna withN beams, each of which spans an angle of 2π/N radians. The transmitters and receivers will always steer beams to each other. Directional antennas are characterized by their pattern functions that measure the power gain G(ϕ) over the angle ϕ. The normalized pattern function is defined as
(1)g(ϕ)=G(ϕ)Gmax⁡,
where Gmax⁡=max⁡ϕ⁡G(ϕ). In a flat-top antenna model, the antenna gain is constant; that is, g(ϕ)=1 when |ϕ|≤Δϕ/2 and 0 otherwise. Here, Δϕ=2π/N is the antenna beamwidth. Thus the antenna gains for (Tx,Rx) pair will be Gt=Gr=1 within the antenna beamwidth and Gt=Gr=0 outside.


### 3.3. mmWave Transmission Model

The capacity of an additive white Gaussian noise (AWGN) channel with broadband interference assumed as Gaussian distribution is given by(2)C=Wlog⁡2⁡1+PrN0+IW,
where Pr is the received signal power, W is the system bandwidth, and N0 and I are the one-side power spectral densities of white Gaussian noise and broadband interference, respectively. The received signal power can be calculated using Friis transmission equation as
(3)Pr(d)=PtGrGtλ4π21dn,
where Pt is the transmit power, Gr and Gt are the antenna gains of receiver and transmitter, respectively, λ is the wavelength (usually taken as 5 mm), d is the transmission distance between (Tx,Rx) pair, and n is the path loss exponent (usually in the range of 2 to 6 for indoor scenarios). By combining (3) and (4), the data rate can be obtained as
(4)R≤C=Wβlog⁡2⁡1+PtGrGtλ216π2N0+IWdn.
Here β is the data rate loss due to the noncontinuity of time-slot resource, and 0≤β≤1. We can observe from (4) that the flow throughput reduction over distance is more serious in  60 GHz network due to its large bandwidth and small wavelength.


### 3.4. Two-Hop Relay Model

We are considering a typical indoor environment with possibility of concurrent transmissions as shown in Figure1. We can see that flows are scheduled in the same time slot, possibly interfering with one another. All Tx DEVs are transmitting at fixed average power without any power control schemes. We are also considering obstacles that block the direct path and hence no direct path exists between Tx and Rx. In order to improve the DEV’s signal-to-noise ratio (SNR), a relay can be selected using our proposed algorithm. Decode-and-forward (DAF) relays are considered with half-duplex communication; that is, in the first hop Tx transmits data to relay, which is decoded by the relay which then transmits to Rx in the second hop.As we can see in Figures2 and 3, C and A are transmitting data to D and B, respectively, in both inter- and intragroup transmission scenarios. In case of blockage of LOS path between (C,D) flow, data may be relayed through R. If PtC is the transmit power of C, the received SNR at R can be expressed as
(5)γCR=PtCKCRd0/H2+d12nεCRhCR2N0,
where KCR is free space path loss at d0, d0 is reference distance (1 m), n is path loss exponent, H is the height of transmitting DEV (taken as constant for all DEVs except PNC), d1 is the transmitter-relay distance, εCR=10-(ϕdB/10) denotes the shadow fading, ϕdB is zero mean Gaussian random variable, hCR is channel coefficient of the (C,R) link, and N0 is the average background white Gaussian noise power.Figure 2
Intergroup multihop scenario.Figure 3
Intragroup multihop scenario.Assume that relayR has transmit power PtR and the interfering flow has an average transmit power ptI; then the received signal-to-interference-plus-noise ratio (SINR) can be expressed as
(6)γRD=Pr(y)Pr(yI)+N0=PtRKRDd0/d2nεRDhRD2PtIKId0/dInεIhI2+N0,
where Pr(y) is the received desired signal power and Pr(yI) is the interference power at receiver.


## 3.1. Quasi-Omni Transmission for PNC

Devices in 802.15.3c suffer from high path loss at  60 GHz frequency band. Therefore, they should focus radiant energy for the data transmissions in the intended direction. Similarly, they may concentrate on the energy for data receptions at a specific direction to gather more power, making it necessary to employ directional communication technologies at the  60 GHz frequency band. The PNC in 802.15.3c should broadcast beacons in all directions since every device connected with the PNC should receive the beacons for proper operations. Quasi-omni is a directional transmission, but it mimics omnidirectional transmission by consecutively rotating its transmission direction through360° [24]. In the 802.15.3c WPANs, the PNC can adopt quasi-omni transmissions for broadcast message transmissions.


## 3.2. Antenna Model

Highly directional antenna is considered for our model. Directional antennas fall in two categories [25], sectored/switched antenna array and adaptive antenna array. We are considering the former that can intelligently put a main beam in the direction of the desired signal and nullifies in the directions of the interference. In [26], Mudumbai et al. also concluded that a mmWave link can be abstracted as a pesudowired link, which shows support for our flat-top antenna model.Every DEV employs an antenna withN beams, each of which spans an angle of 2π/N radians. The transmitters and receivers will always steer beams to each other. Directional antennas are characterized by their pattern functions that measure the power gain G(ϕ) over the angle ϕ. The normalized pattern function is defined as
(1)g(ϕ)=G(ϕ)Gmax⁡,
where Gmax⁡=max⁡ϕ⁡G(ϕ). In a flat-top antenna model, the antenna gain is constant; that is, g(ϕ)=1 when |ϕ|≤Δϕ/2 and 0 otherwise. Here, Δϕ=2π/N is the antenna beamwidth. Thus the antenna gains for (Tx,Rx) pair will be Gt=Gr=1 within the antenna beamwidth and Gt=Gr=0 outside.


## 3.3. mmWave Transmission Model

The capacity of an additive white Gaussian noise (AWGN) channel with broadband interference assumed as Gaussian distribution is given by(2)C=Wlog⁡2⁡1+PrN0+IW,
where Pr is the received signal power, W is the system bandwidth, and N0 and I are the one-side power spectral densities of white Gaussian noise and broadband interference, respectively. The received signal power can be calculated using Friis transmission equation as
(3)Pr(d)=PtGrGtλ4π21dn,
where Pt is the transmit power, Gr and Gt are the antenna gains of receiver and transmitter, respectively, λ is the wavelength (usually taken as 5 mm), d is the transmission distance between (Tx,Rx) pair, and n is the path loss exponent (usually in the range of 2 to 6 for indoor scenarios). By combining (3) and (4), the data rate can be obtained as
(4)R≤C=Wβlog⁡2⁡1+PtGrGtλ216π2N0+IWdn.
Here β is the data rate loss due to the noncontinuity of time-slot resource, and 0≤β≤1. We can observe from (4) that the flow throughput reduction over distance is more serious in  60 GHz network due to its large bandwidth and small wavelength.


## 3.4. Two-Hop Relay Model

We are considering a typical indoor environment with possibility of concurrent transmissions as shown in Figure1. We can see that flows are scheduled in the same time slot, possibly interfering with one another. All Tx DEVs are transmitting at fixed average power without any power control schemes. We are also considering obstacles that block the direct path and hence no direct path exists between Tx and Rx. In order to improve the DEV’s signal-to-noise ratio (SNR), a relay can be selected using our proposed algorithm. Decode-and-forward (DAF) relays are considered with half-duplex communication; that is, in the first hop Tx transmits data to relay, which is decoded by the relay which then transmits to Rx in the second hop.As we can see in Figures2 and 3, C and A are transmitting data to D and B, respectively, in both inter- and intragroup transmission scenarios. In case of blockage of LOS path between (C,D) flow, data may be relayed through R. If PtC is the transmit power of C, the received SNR at R can be expressed as
(5)γCR=PtCKCRd0/H2+d12nεCRhCR2N0,
where KCR is free space path loss at d0, d0 is reference distance (1 m), n is path loss exponent, H is the height of transmitting DEV (taken as constant for all DEVs except PNC), d1 is the transmitter-relay distance, εCR=10-(ϕdB/10) denotes the shadow fading, ϕdB is zero mean Gaussian random variable, hCR is channel coefficient of the (C,R) link, and N0 is the average background white Gaussian noise power.Figure 2
Intergroup multihop scenario.Figure 3
Intragroup multihop scenario.Assume that relayR has transmit power PtR and the interfering flow has an average transmit power ptI; then the received signal-to-interference-plus-noise ratio (SINR) can be expressed as
(6)γRD=Pr(y)Pr(yI)+N0=PtRKRDd0/d2nεRDhRD2PtIKId0/dInεIhI2+N0,
where Pr(y) is the received desired signal power and Pr(yI) is the interference power at receiver.


## 4. Capacity Enhancement Using Relay and Scheduling Schemes

In this section, we are focusing on relay selection and scheduling mechanism to enhance D2D networks based on  60 GHz to successfully achieve the data rates it promises.


### 4.1. Relay Selection Schemes

We first define the relay selection problem as follows. LetQ be the set of all DEVs in a network. For any pair of DEVs x,y∈Q and a subset P⊂Q, we find another DEV p belonging to P that minimizes the sum of delays in the overlay link of x-p and p-y. In a general selection scheme, a subset P of DEVs of Q is chosen and the two DEVs x and y measure the network distance to all the DEVs in P. Finally, x and y select the DEV that results in the smallest one-hop network distance. The size of the chosen subset P determines the amount of measurement traffic.As mentioned earlier, two types of transmissions are considered, inter- and intragroup. It is observed that in high-speed short-ranged WPANs,(Tx,Rx) pair come close for their transmission [12] and then stay for several minutes during their data transmission. So we can assume that most of the transmission will be based on intragroup with occasional intergroup transmissions. Therefore, we have proposed a novel low complexity distributed relay algorithm for intragroup and a simple but effective centralized distance based relay algorithm for intergroup transmissions.


#### 4.1.1. Intergroup Relay Selection

In this subsection, we propose a relay selection algorithm for intergroup multihop transmission in mmWave WPANs. Midmost relay positioning, distance, and traffic load are considered to take the relay decision, as mentioned in Algorithm1. Our emphasis lies on midmost relay positioning and distance. Traffic flow metric can be considered useful in case that multiple potential relay DEVs yield the same value at step (7) of Algorithm 1. We are considering a two-hop scenario as shown in Figure 2. Suppose that the total number of groups in a network is M. Then each Gi for i=1,…,M contains DEVs which mostly communicate with one another (rationale behind the grouping). The PNC would assign weights to all potential DEVs to evaluate the best relay DEV. Suppose that Prelay is the total number of potential relay DEVs (Pk∀k=(1,2,…,Prelay)). Weights are assigned on the basis of link lengths and traffic load (Algorithm 1 lines 6–8). The terms F(Pk) and EGg represent traffic load at DEV Pk and average traffic load on all DEVs in group Gg, respectively. Traffic load is calculated as a ratio of traffic load on a DEV Pk and sum of traffic load on all DEVs in that group. In (4), data rate is a function of dn, which is also introduced in Algorithm 1 (line 7), where D refers to distance of corresponding pair. The best relay would be the DEV with the smallest weight.Algorithm 1:Distance based intergroup relay selection.
(1)Inputs: link lengths and traffic load
(2)Output: Best relay DEV for (Tx,Rx) pair based on distance and traffic load
(3) With(Tx,Rx) pair
(4)ifTx and Rx belongs to different groupsthen
(5) sayTx∈Gi and Rx∈Gj∀i,j←(1,2,…,M) and i≠j
M is maximum number of groups in WPAN
(6)fork←1 to Prelaydo
(7)w(Tx,Rx)←Dn(Tx,Pk)+Dn(Pk,Rx)Dn(Tx,Rx)+F(Pk)E[Gg]
where g← group i or group j
w(Tx,Rx) is a set of all weights assigned to potential DEVs for (Tx,Rx) pair
(8)end for
(9)  Selectdrelay∈Pk with weight Min⁡[w(Tx,Rx)] and ∀k←(1,2,…,Prelay)
(10)end if


#### 4.1.2. Intragroup Distributed Relay Selection

In this subsection, we propose a receiver based distributed relay selection for intragroup transmission. We are considering an antenna withN=8 beams at each DEV covering, 360 degrees as shown in Figure 3. All DEVs are assumed to be capable of measuring SINR levels on their antenna elements and are aware of the neighboring DEV(s) within their beams’ coverage areas. Discovery of neighboring DEVs can be accomplished either by using some discovery techniques [27] or through learning by successful transmissions and other signaling with the DEVs for some threshold amount of time. During transmission, each Rx DEV is maintaining a table that contains SINR levels and DEVs information on the respective antenna elements as shown in Table 1. The frequency of table updates at Rx depends on its mobility along with the mobility and recurrence of mutual transmissions among neighboring DEVs.Table 1
Table maintained byRx.
Beams
SNR levels
Potential relay DEVs
1
γ
1
DE
V
1
2
γ
2
DE
V
2
3
γ
3
DE
V
3, DEV4
4
γ
4
DE
V
5, DEV6
5
γ
5
DE
V
7
6
γ
6
DE
V
8
7
γ
7
DE
V
9
8
γ
8
DE
V
10The first column in Table1 represents the total number of antenna elements, followed by SINR levels on the respective antenna elements in the second column. The third column represents the location(s) of DEV(s) lying in the area of the corresponding beams. Our algorithm tries to find the minimum distance by exploiting the directional nature of  60 GHz based D2D networks. The rationale behind our best relay is the least distance along with midmost relay placement. As shown in (4) and Figure 4, data rate is severely affected by distance especially for n>2 in  60 GHz networks. As we can see in Figure 4 those relays lying close to midmost between receiver and transmitter result in higher capacity gain. An inequality of both hops of even 5% difference would result in lower capacity. Therefore, relay with least distance along (Tx,drelay,Rx) with midmost placement is encouraged. The intuition of finding the least distance relay for beam sector i is to search the neighboring sectors. Our proposed algorithm tries to search 4 beam sectors (i-2,i-1,i+1,i+2) (for i=1:i-1,i-2 correspond to beams 8 and 7, resp.), with the assumption of the same SINR levels on each antenna element. Other beam sectors, being almost in the opposite direction, would result in a longer relay path and would not be cost effective. Our proposed relay selection scheme is given in Algorithm 2. For an active transmission at sector i,Rx will continuously calculate SINR at all the antenna elements (N=8). If the SINR at ith element (γi) is less than or equal to the threshold SINR (γth), or in case of blockage of LOS path, Rx DEV can check the table for the neighboring four beams. The intuition is that these regions will have the relay DEV with the least distance. Possible relay DEVs on other beams (other than four neighboring beams) will be too far away to be effective. The relay with minimum relay path (Dmin⁡) is considered as the best relay (drelay). In case of more than one such DEV, distance of drelay to Tx and Rx is checked. A DEV which lies at midmost position ((Tx,drelay,Rx)/2) of the link is selected as relay for the corresponding (Tx,Rx) pair.Algorithm 2:Distributed receiver based intragroup relay selection.
(1)Input: Table maintained by Rx
(2)Output: Best Relay drelay for (Tx,Rx) pair
(3) With active reception of signal at sectori
(4)ifγi≤γth or Signal Blockagethen
(5)  Search table for(i-2,i-1,i+1,i+2) rows for potential relays. Let Prelay be total
potential relay DEVs found
(6)  CalculateDistance(Tx,rj,Rx)∀j←(1,2,…,Prelay) that is, end-to-end distance of relay
paths for all Prelay
(7)drelay←Min⁡(Tx,rj,Rx)∀j←(1,2,…,Prelay), where drelay is a set containing one or
more relays with minimum distance Dmin⁡,
(8)if|drelay|>1 that is, more than one relays (say Pmin⁡⊂Prelay) with same minimum
distance Dmin⁡then
(9)forj←1 to Pmin⁡do
(10)Mid(j)←(|12-d(Tx,rj)Dmin⁡|)+(|12-d(rj,Rx)Dmin⁡|)
(11)end for
(12)drelay←Min⁡(Mid)
(13)end if
(14)end ifFigure 4
Relay to(Tx,Rx) distance analysis.Example. We try to explain the algorithm using an example. As mentioned earlier, distance plays a major role in mmWave networks especially for n>2. It is very important to select a relay at the midmost position between Tx and Rx. In Figure 5, we can see that there are different relays placed for the (Tx,Rx) pair at various distances. The distance between Tx and Rx is 6 m. The distance of Tx and Rx from relays varies. However, the sum of their distances from Tx and Rx is the same, that is, 8 m.Figure 5
Relay selection example.ForR1,R2, and R3, Algorithms 1 and 2 will respectively calculate |(22+62)/62|=1.11,|(52+32)/62|=0.944, |(3.52+4.52)/62|=0.902 and |(1/2)-(2/8)|+|(1/2)-(6/8)|=0.5, |(1/2)-(5/8)|+|(1/2)-(3/8)|=0.25, |(1/2)-(3.5/8)|+|(1/2)-(4.5/8)|=0.125. R3 will be selected as relay by both Algorithms 1 and 2 (drelay), depending upon inter- or intragroup transmission.


### 4.2. Vertex Multicoloring Scheduling Algorithm

In this section, we propose an algorithm for concurrent transmission in  60 GHz based D2D networks employing the principle of vertex coloring (VC). Our proposed vertex multicoloring concurrent transmission (VMCCT) algorithm schedules(Tx,Rx) flows in the same time resource. The considered flows have all the distinct transmitters and receivers with no shared transceiver.


#### 4.2.1. Concurrent Transmission Conditions

In this subsection, we discuss the conditions for concurrent transmission. Figure6 shows two concurrent flows scenario in  60 GHz based D2D networks. We can see that two transmitters (A,C) try to send data to two receivers (B,D), in the same time slot. Hence, the sufficient condition 1 for concurrent transmission between pair (A,B) and pair (C,D) with beamwidth θ can be obtained as follows.Figure 6
Concurrent transmission scenario.Concurrent Transmission Sufficient Condition 1. Here we assess whether the flows (A,B) and (C,D) are within the signal beams of each other by using the following condition:
(7)∠DAB>θ2,∠BCD>θ2,
where ∠DAB and ∠BCD could be obtained from the cosine law:
(8)∠DAB=arccosAD¯2+AB¯2-BD¯22AD¯×AB¯,∠BCD=arccosBC¯2+CD¯2-BD¯22BC¯×CD¯.Concurrent flows with mutual interference can be allowed as long as they are apart by a certain threshold distance. The threshold distance is defined as an area where the mutual interference can be seen as background noise. To accomplish this, an exclusive region (ER) around the receiver is defined in [20], which allows concurrent transmission of mutually interfering flows. Hence, we can obtain the sufficient condition 2 for concurrent transmission between pair (A,B) and pair (C,D) as follows.Concurrent Transmission Sufficient Condition 2. If the flows are in conflict with each other then the transmitter-receiver distances of the conflicting flows are checked to see if they are apart a threshold distance by using the following condition:
(9)AD¯>RER∠DAB<θ2,BC¯>RER∠BCD<θ2,
using the ER definition in [20]:
(10)RER=k1GtGrPtN0W1/n,
where RER is the radius of ER as shown in Figure 6 (around DEV D), k1∝(λ/4π)2 is a constant coefficient dependent on the wavelength λ, Gt and Gr are the antenna gains for the transmitter and receiver, respectively, Pt is the transmit power, and n is the pathloss exponent. Here condition 2 will keep the accumulative interference in the network below an acceptable threshold.Both concurrent transmission conditions 1 and 2 realize the possibility of concurrent transmission for different flows. For illustration, as in Figure6, receiver D is inside the beamwidth of transmitter A, but the distance between A and D is larger than RER. Therefore, concurrent transmission of pairs (A,B) and (C,D) would be allowed.


#### 4.2.2. Construction of Conflict Matrix

A conflict matrix (CM) represents the relationship between different flows. The relationship is represented by 1 (conflict) and 0 (no conflict) as shown below:(11)CM(6×6)=010001001000110000001000000000100010.Equation (11) shows a conflict matrix of 6 flows. Element 1 results when the corresponding flows fail to meet concurrent conditions 1 and 2. Therefore, they cannot be allowed to transmit their data concurrently. The rows of the conflict matrix represent the conflict relationship among flows. Each row is constructed by considering the conflict relationship from the corresponding flow to all the other flows unilaterally. Therefore if some flow i has no conflict with flow j, it does not necessarily mean that flow j also has no conflict with flow i. This situation can be seen in matrix as shown in (11) at indices (1,2) and (2,1). The conflict matrix can also be represented as an undirected graph called conflict graph. The conflict matrix in (11) is converted into conflict graph as shown in Figure 7(a). The flows are represented as vertices and their mutual conflicts are represented as edges between them. It should be noted that values in the conflict matrix for flow 1 and 2 at indices (1,2) and (2,1) are not same but they have resulted in a conflict (an edge) in conflict graph.Figure 7
Conflict graph representation of VC and VMCCT.


#### 4.2.3. Time-Slot Allocation Based on VC

Time slot, being scarce resource, requires efficient allocation. We employ VC algorithm to effectively resolve conflict among flows and efficiently assign time resource. VC algorithm has been used for resource allocation in different types of networks [28–31] including mmWave, cognitive radios, and ad hoc networks. VC will color all vertices (flows) in conflict graph with minimum number of colors (time slots). Two directly connected vertices cannot have the same color. We can see in Figure 7(b) that VC colors all the six vertices using three colors. With green, red, and yellow representing first, second, and third time slots, respectively, we can transmit flows 2 and 6 in first time slot, flows 1, 4, and 5 in second time slot, and flow 3 in the third time slot.


#### 4.2.4. Time-Slot Allocation Based on VMCCT

The conservative time-slot allocation based on VC is not efficient. Our proposed multicoloring algorithm allocates time slots more aggressively to improve network throughput. Algorithm3 shows the details of our proposed scheme. Our scheme starts by constructing a conflict matrix (Algorithm 2 lines 3–16). The conflict matrix is then used to resolve conflict and assign time slots based on VC and VMCCT.Algorithm 3:Vertex multicoloring concurrent transmission algorithm.
(1)Inputs: Set of all flows that is, Flow(1) to Flow(V)
(2)Output: vertex multi-color graph for scheduling concurrent transmission
(3)forRow=1; Row<V; Row++do
(4)forColumn=1; Column<V; Column++do
(5)ifRow!=Columnthen
(6)α=Angle(Row,Column)
(7)D=Distance(Row,Column)
(8)ifα<θ/2 and D<ERthen
(9)Use relay selection algorithms, go back and calculate α and D
(10)if no relay found Conflict Matrix(Row, Column) = 1
(11)else
(12)Conflict Matrix(Row, Column) = 0
(13)end if
(14)end if
(15)end for
(16)end for
(17)Color_Graph=Function_VC(ConflictMatrix)
(18)forCnt=1; Cnt<V; Cnt++do
(19)D(Cnt)=Function_Distance(Flow(Cnt))
(20)end for
(21)forCnt=1; Cnt<V; Cnt++do
(22)w(Cnt)=Function_Weight(D(Cnt))
(23)end for
(24)forCnt=1; Cnt<V; Cnt++do
(25)x=Max⁡(w)
(26)Color_V(x)=Color_All-Color_N(x)
(27)w(x)=0
(28)end forThe proposed algorithm can be explained with the help of Figure7. Time-slot allocation based on VC and VMCCT is shown in Figures 7(b) and 7(c), respectively. The basic principle with multiple colors for a vertex is the same as the traditional VC; that is, the color between connected vertices should be different. Hence, the possible colors for a specific vertex should not include matching colors of its neighbors, which can be shown as follows:
(12)Color_V(i)=Color_All-Color_N(i),
where Color_V(i) represents the color assigned to flow i, Color_All holds the set of all colors, and Color_N(i) represents the color of the neighboring vertex.With (12), we can obtain the final multicoloring results for all the vertices. Vertex selection for multicoloring can significantly affect the network throughput because different flows can exhibit different data rates. In order to improve the network throughput, we give each of the vertices a weight based on its intended data rate. Since mutual interference is below the background noise because of the distance and high propagation loss, it is appropriate to use the transmission distance as a metric for color selection:
(13)w(i)=∑i=1Vd(i)d(i),
where V is the number of vertices and d(i) donates the distance between the transmitter and receiver in a flow i. Using (13), flow i with shorter transmission distance will get higher weight. In order to multicolor the vertices as proposed in VMCCT, we will sort the vertices in descending order of their weights.In Figure7(b), weights are shown on the top of each vertex; we can get the Color_All and sorted weights sets from the graph:
(14)Color_All=(RED,GREEN,YELLOW),(15)Weight={20.0(4),13.3(6),6.6(5),5.0(1),4.0(2),3.6(3)}.
Hence, vertex 4 with the largest weight will be considered first. By using (15) we can assign color to vertex 4 as follows:
(16)Color_V4=(RED,GREEN,YELLOW)-(YELLOW),=(RED,GREEN).
This will yield red and green color to vertex 4. Similarly, vertex 6 will be assigned both green and yellow colors. Then the Color_N(6) will be refreshed to (GREEN, YELLOW), so vertex 5 can only be assigned a red color. Similarly, we can get the final results for flows 1, 2, and 3 as shown in Figure 7(c).


## 4.1. Relay Selection Schemes

We first define the relay selection problem as follows. LetQ be the set of all DEVs in a network. For any pair of DEVs x,y∈Q and a subset P⊂Q, we find another DEV p belonging to P that minimizes the sum of delays in the overlay link of x-p and p-y. In a general selection scheme, a subset P of DEVs of Q is chosen and the two DEVs x and y measure the network distance to all the DEVs in P. Finally, x and y select the DEV that results in the smallest one-hop network distance. The size of the chosen subset P determines the amount of measurement traffic.As mentioned earlier, two types of transmissions are considered, inter- and intragroup. It is observed that in high-speed short-ranged WPANs,(Tx,Rx) pair come close for their transmission [12] and then stay for several minutes during their data transmission. So we can assume that most of the transmission will be based on intragroup with occasional intergroup transmissions. Therefore, we have proposed a novel low complexity distributed relay algorithm for intragroup and a simple but effective centralized distance based relay algorithm for intergroup transmissions.


### 4.1.1. Intergroup Relay Selection

In this subsection, we propose a relay selection algorithm for intergroup multihop transmission in mmWave WPANs. Midmost relay positioning, distance, and traffic load are considered to take the relay decision, as mentioned in Algorithm1. Our emphasis lies on midmost relay positioning and distance. Traffic flow metric can be considered useful in case that multiple potential relay DEVs yield the same value at step (7) of Algorithm 1. We are considering a two-hop scenario as shown in Figure 2. Suppose that the total number of groups in a network is M. Then each Gi for i=1,…,M contains DEVs which mostly communicate with one another (rationale behind the grouping). The PNC would assign weights to all potential DEVs to evaluate the best relay DEV. Suppose that Prelay is the total number of potential relay DEVs (Pk∀k=(1,2,…,Prelay)). Weights are assigned on the basis of link lengths and traffic load (Algorithm 1 lines 6–8). The terms F(Pk) and EGg represent traffic load at DEV Pk and average traffic load on all DEVs in group Gg, respectively. Traffic load is calculated as a ratio of traffic load on a DEV Pk and sum of traffic load on all DEVs in that group. In (4), data rate is a function of dn, which is also introduced in Algorithm 1 (line 7), where D refers to distance of corresponding pair. The best relay would be the DEV with the smallest weight.Algorithm 1:Distance based intergroup relay selection.
(1)Inputs: link lengths and traffic load
(2)Output: Best relay DEV for (Tx,Rx) pair based on distance and traffic load
(3) With(Tx,Rx) pair
(4)ifTx and Rx belongs to different groupsthen
(5) sayTx∈Gi and Rx∈Gj∀i,j←(1,2,…,M) and i≠j
M is maximum number of groups in WPAN
(6)fork←1 to Prelaydo
(7)w(Tx,Rx)←Dn(Tx,Pk)+Dn(Pk,Rx)Dn(Tx,Rx)+F(Pk)E[Gg]
where g← group i or group j
w(Tx,Rx) is a set of all weights assigned to potential DEVs for (Tx,Rx) pair
(8)end for
(9)  Selectdrelay∈Pk with weight Min⁡[w(Tx,Rx)] and ∀k←(1,2,…,Prelay)
(10)end if


### 4.1.2. Intragroup Distributed Relay Selection

In this subsection, we propose a receiver based distributed relay selection for intragroup transmission. We are considering an antenna withN=8 beams at each DEV covering, 360 degrees as shown in Figure 3. All DEVs are assumed to be capable of measuring SINR levels on their antenna elements and are aware of the neighboring DEV(s) within their beams’ coverage areas. Discovery of neighboring DEVs can be accomplished either by using some discovery techniques [27] or through learning by successful transmissions and other signaling with the DEVs for some threshold amount of time. During transmission, each Rx DEV is maintaining a table that contains SINR levels and DEVs information on the respective antenna elements as shown in Table 1. The frequency of table updates at Rx depends on its mobility along with the mobility and recurrence of mutual transmissions among neighboring DEVs.Table 1
Table maintained byRx.
Beams
SNR levels
Potential relay DEVs
1
γ
1
DE
V
1
2
γ
2
DE
V
2
3
γ
3
DE
V
3, DEV4
4
γ
4
DE
V
5, DEV6
5
γ
5
DE
V
7
6
γ
6
DE
V
8
7
γ
7
DE
V
9
8
γ
8
DE
V
10The first column in Table1 represents the total number of antenna elements, followed by SINR levels on the respective antenna elements in the second column. The third column represents the location(s) of DEV(s) lying in the area of the corresponding beams. Our algorithm tries to find the minimum distance by exploiting the directional nature of  60 GHz based D2D networks. The rationale behind our best relay is the least distance along with midmost relay placement. As shown in (4) and Figure 4, data rate is severely affected by distance especially for n>2 in  60 GHz networks. As we can see in Figure 4 those relays lying close to midmost between receiver and transmitter result in higher capacity gain. An inequality of both hops of even 5% difference would result in lower capacity. Therefore, relay with least distance along (Tx,drelay,Rx) with midmost placement is encouraged. The intuition of finding the least distance relay for beam sector i is to search the neighboring sectors. Our proposed algorithm tries to search 4 beam sectors (i-2,i-1,i+1,i+2) (for i=1:i-1,i-2 correspond to beams 8 and 7, resp.), with the assumption of the same SINR levels on each antenna element. Other beam sectors, being almost in the opposite direction, would result in a longer relay path and would not be cost effective. Our proposed relay selection scheme is given in Algorithm 2. For an active transmission at sector i,Rx will continuously calculate SINR at all the antenna elements (N=8). If the SINR at ith element (γi) is less than or equal to the threshold SINR (γth), or in case of blockage of LOS path, Rx DEV can check the table for the neighboring four beams. The intuition is that these regions will have the relay DEV with the least distance. Possible relay DEVs on other beams (other than four neighboring beams) will be too far away to be effective. The relay with minimum relay path (Dmin⁡) is considered as the best relay (drelay). In case of more than one such DEV, distance of drelay to Tx and Rx is checked. A DEV which lies at midmost position ((Tx,drelay,Rx)/2) of the link is selected as relay for the corresponding (Tx,Rx) pair.Algorithm 2:Distributed receiver based intragroup relay selection.
(1)Input: Table maintained by Rx
(2)Output: Best Relay drelay for (Tx,Rx) pair
(3) With active reception of signal at sectori
(4)ifγi≤γth or Signal Blockagethen
(5)  Search table for(i-2,i-1,i+1,i+2) rows for potential relays. Let Prelay be total
potential relay DEVs found
(6)  CalculateDistance(Tx,rj,Rx)∀j←(1,2,…,Prelay) that is, end-to-end distance of relay
paths for all Prelay
(7)drelay←Min⁡(Tx,rj,Rx)∀j←(1,2,…,Prelay), where drelay is a set containing one or
more relays with minimum distance Dmin⁡,
(8)if|drelay|>1 that is, more than one relays (say Pmin⁡⊂Prelay) with same minimum
distance Dmin⁡then
(9)forj←1 to Pmin⁡do
(10)Mid(j)←(|12-d(Tx,rj)Dmin⁡|)+(|12-d(rj,Rx)Dmin⁡|)
(11)end for
(12)drelay←Min⁡(Mid)
(13)end if
(14)end ifFigure 4
Relay to(Tx,Rx) distance analysis.Example. We try to explain the algorithm using an example. As mentioned earlier, distance plays a major role in mmWave networks especially for n>2. It is very important to select a relay at the midmost position between Tx and Rx. In Figure 5, we can see that there are different relays placed for the (Tx,Rx) pair at various distances. The distance between Tx and Rx is 6 m. The distance of Tx and Rx from relays varies. However, the sum of their distances from Tx and Rx is the same, that is, 8 m.Figure 5
Relay selection example.ForR1,R2, and R3, Algorithms 1 and 2 will respectively calculate |(22+62)/62|=1.11,|(52+32)/62|=0.944, |(3.52+4.52)/62|=0.902 and |(1/2)-(2/8)|+|(1/2)-(6/8)|=0.5, |(1/2)-(5/8)|+|(1/2)-(3/8)|=0.25, |(1/2)-(3.5/8)|+|(1/2)-(4.5/8)|=0.125. R3 will be selected as relay by both Algorithms 1 and 2 (drelay), depending upon inter- or intragroup transmission.


## 4.1.1. Intergroup Relay Selection

In this subsection, we propose a relay selection algorithm for intergroup multihop transmission in mmWave WPANs. Midmost relay positioning, distance, and traffic load are considered to take the relay decision, as mentioned in Algorithm1. Our emphasis lies on midmost relay positioning and distance. Traffic flow metric can be considered useful in case that multiple potential relay DEVs yield the same value at step (7) of Algorithm 1. We are considering a two-hop scenario as shown in Figure 2. Suppose that the total number of groups in a network is M. Then each Gi for i=1,…,M contains DEVs which mostly communicate with one another (rationale behind the grouping). The PNC would assign weights to all potential DEVs to evaluate the best relay DEV. Suppose that Prelay is the total number of potential relay DEVs (Pk∀k=(1,2,…,Prelay)). Weights are assigned on the basis of link lengths and traffic load (Algorithm 1 lines 6–8). The terms F(Pk) and EGg represent traffic load at DEV Pk and average traffic load on all DEVs in group Gg, respectively. Traffic load is calculated as a ratio of traffic load on a DEV Pk and sum of traffic load on all DEVs in that group. In (4), data rate is a function of dn, which is also introduced in Algorithm 1 (line 7), where D refers to distance of corresponding pair. The best relay would be the DEV with the smallest weight.Algorithm 1:Distance based intergroup relay selection.
(1)Inputs: link lengths and traffic load
(2)Output: Best relay DEV for (Tx,Rx) pair based on distance and traffic load
(3) With(Tx,Rx) pair
(4)ifTx and Rx belongs to different groupsthen
(5) sayTx∈Gi and Rx∈Gj∀i,j←(1,2,…,M) and i≠j
M is maximum number of groups in WPAN
(6)fork←1 to Prelaydo
(7)w(Tx,Rx)←Dn(Tx,Pk)+Dn(Pk,Rx)Dn(Tx,Rx)+F(Pk)E[Gg]
where g← group i or group j
w(Tx,Rx) is a set of all weights assigned to potential DEVs for (Tx,Rx) pair
(8)end for
(9)  Selectdrelay∈Pk with weight Min⁡[w(Tx,Rx)] and ∀k←(1,2,…,Prelay)
(10)end if


## 4.1.2. Intragroup Distributed Relay Selection

In this subsection, we propose a receiver based distributed relay selection for intragroup transmission. We are considering an antenna withN=8 beams at each DEV covering, 360 degrees as shown in Figure 3. All DEVs are assumed to be capable of measuring SINR levels on their antenna elements and are aware of the neighboring DEV(s) within their beams’ coverage areas. Discovery of neighboring DEVs can be accomplished either by using some discovery techniques [27] or through learning by successful transmissions and other signaling with the DEVs for some threshold amount of time. During transmission, each Rx DEV is maintaining a table that contains SINR levels and DEVs information on the respective antenna elements as shown in Table 1. The frequency of table updates at Rx depends on its mobility along with the mobility and recurrence of mutual transmissions among neighboring DEVs.Table 1
Table maintained byRx.
Beams
SNR levels
Potential relay DEVs
1
γ
1
DE
V
1
2
γ
2
DE
V
2
3
γ
3
DE
V
3, DEV4
4
γ
4
DE
V
5, DEV6
5
γ
5
DE
V
7
6
γ
6
DE
V
8
7
γ
7
DE
V
9
8
γ
8
DE
V
10The first column in Table1 represents the total number of antenna elements, followed by SINR levels on the respective antenna elements in the second column. The third column represents the location(s) of DEV(s) lying in the area of the corresponding beams. Our algorithm tries to find the minimum distance by exploiting the directional nature of  60 GHz based D2D networks. The rationale behind our best relay is the least distance along with midmost relay placement. As shown in (4) and Figure 4, data rate is severely affected by distance especially for n>2 in  60 GHz networks. As we can see in Figure 4 those relays lying close to midmost between receiver and transmitter result in higher capacity gain. An inequality of both hops of even 5% difference would result in lower capacity. Therefore, relay with least distance along (Tx,drelay,Rx) with midmost placement is encouraged. The intuition of finding the least distance relay for beam sector i is to search the neighboring sectors. Our proposed algorithm tries to search 4 beam sectors (i-2,i-1,i+1,i+2) (for i=1:i-1,i-2 correspond to beams 8 and 7, resp.), with the assumption of the same SINR levels on each antenna element. Other beam sectors, being almost in the opposite direction, would result in a longer relay path and would not be cost effective. Our proposed relay selection scheme is given in Algorithm 2. For an active transmission at sector i,Rx will continuously calculate SINR at all the antenna elements (N=8). If the SINR at ith element (γi) is less than or equal to the threshold SINR (γth), or in case of blockage of LOS path, Rx DEV can check the table for the neighboring four beams. The intuition is that these regions will have the relay DEV with the least distance. Possible relay DEVs on other beams (other than four neighboring beams) will be too far away to be effective. The relay with minimum relay path (Dmin⁡) is considered as the best relay (drelay). In case of more than one such DEV, distance of drelay to Tx and Rx is checked. A DEV which lies at midmost position ((Tx,drelay,Rx)/2) of the link is selected as relay for the corresponding (Tx,Rx) pair.Algorithm 2:Distributed receiver based intragroup relay selection.
(1)Input: Table maintained by Rx
(2)Output: Best Relay drelay for (Tx,Rx) pair
(3) With active reception of signal at sectori
(4)ifγi≤γth or Signal Blockagethen
(5)  Search table for(i-2,i-1,i+1,i+2) rows for potential relays. Let Prelay be total
potential relay DEVs found
(6)  CalculateDistance(Tx,rj,Rx)∀j←(1,2,…,Prelay) that is, end-to-end distance of relay
paths for all Prelay
(7)drelay←Min⁡(Tx,rj,Rx)∀j←(1,2,…,Prelay), where drelay is a set containing one or
more relays with minimum distance Dmin⁡,
(8)if|drelay|>1 that is, more than one relays (say Pmin⁡⊂Prelay) with same minimum
distance Dmin⁡then
(9)forj←1 to Pmin⁡do
(10)Mid(j)←(|12-d(Tx,rj)Dmin⁡|)+(|12-d(rj,Rx)Dmin⁡|)
(11)end for
(12)drelay←Min⁡(Mid)
(13)end if
(14)end ifFigure 4
Relay to(Tx,Rx) distance analysis.Example. We try to explain the algorithm using an example. As mentioned earlier, distance plays a major role in mmWave networks especially for n>2. It is very important to select a relay at the midmost position between Tx and Rx. In Figure 5, we can see that there are different relays placed for the (Tx,Rx) pair at various distances. The distance between Tx and Rx is 6 m. The distance of Tx and Rx from relays varies. However, the sum of their distances from Tx and Rx is the same, that is, 8 m.Figure 5
Relay selection example.ForR1,R2, and R3, Algorithms 1 and 2 will respectively calculate |(22+62)/62|=1.11,|(52+32)/62|=0.944, |(3.52+4.52)/62|=0.902 and |(1/2)-(2/8)|+|(1/2)-(6/8)|=0.5, |(1/2)-(5/8)|+|(1/2)-(3/8)|=0.25, |(1/2)-(3.5/8)|+|(1/2)-(4.5/8)|=0.125. R3 will be selected as relay by both Algorithms 1 and 2 (drelay), depending upon inter- or intragroup transmission.


## 4.2. Vertex Multicoloring Scheduling Algorithm

In this section, we propose an algorithm for concurrent transmission in  60 GHz based D2D networks employing the principle of vertex coloring (VC). Our proposed vertex multicoloring concurrent transmission (VMCCT) algorithm schedules(Tx,Rx) flows in the same time resource. The considered flows have all the distinct transmitters and receivers with no shared transceiver.


### 4.2.1. Concurrent Transmission Conditions

In this subsection, we discuss the conditions for concurrent transmission. Figure6 shows two concurrent flows scenario in  60 GHz based D2D networks. We can see that two transmitters (A,C) try to send data to two receivers (B,D), in the same time slot. Hence, the sufficient condition 1 for concurrent transmission between pair (A,B) and pair (C,D) with beamwidth θ can be obtained as follows.Figure 6
Concurrent transmission scenario.Concurrent Transmission Sufficient Condition 1. Here we assess whether the flows (A,B) and (C,D) are within the signal beams of each other by using the following condition:
(7)∠DAB>θ2,∠BCD>θ2,
where ∠DAB and ∠BCD could be obtained from the cosine law:
(8)∠DAB=arccosAD¯2+AB¯2-BD¯22AD¯×AB¯,∠BCD=arccosBC¯2+CD¯2-BD¯22BC¯×CD¯.Concurrent flows with mutual interference can be allowed as long as they are apart by a certain threshold distance. The threshold distance is defined as an area where the mutual interference can be seen as background noise. To accomplish this, an exclusive region (ER) around the receiver is defined in [20], which allows concurrent transmission of mutually interfering flows. Hence, we can obtain the sufficient condition 2 for concurrent transmission between pair (A,B) and pair (C,D) as follows.Concurrent Transmission Sufficient Condition 2. If the flows are in conflict with each other then the transmitter-receiver distances of the conflicting flows are checked to see if they are apart a threshold distance by using the following condition:
(9)AD¯>RER∠DAB<θ2,BC¯>RER∠BCD<θ2,
using the ER definition in [20]:
(10)RER=k1GtGrPtN0W1/n,
where RER is the radius of ER as shown in Figure 6 (around DEV D), k1∝(λ/4π)2 is a constant coefficient dependent on the wavelength λ, Gt and Gr are the antenna gains for the transmitter and receiver, respectively, Pt is the transmit power, and n is the pathloss exponent. Here condition 2 will keep the accumulative interference in the network below an acceptable threshold.Both concurrent transmission conditions 1 and 2 realize the possibility of concurrent transmission for different flows. For illustration, as in Figure6, receiver D is inside the beamwidth of transmitter A, but the distance between A and D is larger than RER. Therefore, concurrent transmission of pairs (A,B) and (C,D) would be allowed.


### 4.2.2. Construction of Conflict Matrix

A conflict matrix (CM) represents the relationship between different flows. The relationship is represented by 1 (conflict) and 0 (no conflict) as shown below:(11)CM(6×6)=010001001000110000001000000000100010.Equation (11) shows a conflict matrix of 6 flows. Element 1 results when the corresponding flows fail to meet concurrent conditions 1 and 2. Therefore, they cannot be allowed to transmit their data concurrently. The rows of the conflict matrix represent the conflict relationship among flows. Each row is constructed by considering the conflict relationship from the corresponding flow to all the other flows unilaterally. Therefore if some flow i has no conflict with flow j, it does not necessarily mean that flow j also has no conflict with flow i. This situation can be seen in matrix as shown in (11) at indices (1,2) and (2,1). The conflict matrix can also be represented as an undirected graph called conflict graph. The conflict matrix in (11) is converted into conflict graph as shown in Figure 7(a). The flows are represented as vertices and their mutual conflicts are represented as edges between them. It should be noted that values in the conflict matrix for flow 1 and 2 at indices (1,2) and (2,1) are not same but they have resulted in a conflict (an edge) in conflict graph.Figure 7
Conflict graph representation of VC and VMCCT.


### 4.2.3. Time-Slot Allocation Based on VC

Time slot, being scarce resource, requires efficient allocation. We employ VC algorithm to effectively resolve conflict among flows and efficiently assign time resource. VC algorithm has been used for resource allocation in different types of networks [28–31] including mmWave, cognitive radios, and ad hoc networks. VC will color all vertices (flows) in conflict graph with minimum number of colors (time slots). Two directly connected vertices cannot have the same color. We can see in Figure 7(b) that VC colors all the six vertices using three colors. With green, red, and yellow representing first, second, and third time slots, respectively, we can transmit flows 2 and 6 in first time slot, flows 1, 4, and 5 in second time slot, and flow 3 in the third time slot.


### 4.2.4. Time-Slot Allocation Based on VMCCT

The conservative time-slot allocation based on VC is not efficient. Our proposed multicoloring algorithm allocates time slots more aggressively to improve network throughput. Algorithm3 shows the details of our proposed scheme. Our scheme starts by constructing a conflict matrix (Algorithm 2 lines 3–16). The conflict matrix is then used to resolve conflict and assign time slots based on VC and VMCCT.Algorithm 3:Vertex multicoloring concurrent transmission algorithm.
(1)Inputs: Set of all flows that is, Flow(1) to Flow(V)
(2)Output: vertex multi-color graph for scheduling concurrent transmission
(3)forRow=1; Row<V; Row++do
(4)forColumn=1; Column<V; Column++do
(5)ifRow!=Columnthen
(6)α=Angle(Row,Column)
(7)D=Distance(Row,Column)
(8)ifα<θ/2 and D<ERthen
(9)Use relay selection algorithms, go back and calculate α and D
(10)if no relay found Conflict Matrix(Row, Column) = 1
(11)else
(12)Conflict Matrix(Row, Column) = 0
(13)end if
(14)end if
(15)end for
(16)end for
(17)Color_Graph=Function_VC(ConflictMatrix)
(18)forCnt=1; Cnt<V; Cnt++do
(19)D(Cnt)=Function_Distance(Flow(Cnt))
(20)end for
(21)forCnt=1; Cnt<V; Cnt++do
(22)w(Cnt)=Function_Weight(D(Cnt))
(23)end for
(24)forCnt=1; Cnt<V; Cnt++do
(25)x=Max⁡(w)
(26)Color_V(x)=Color_All-Color_N(x)
(27)w(x)=0
(28)end forThe proposed algorithm can be explained with the help of Figure7. Time-slot allocation based on VC and VMCCT is shown in Figures 7(b) and 7(c), respectively. The basic principle with multiple colors for a vertex is the same as the traditional VC; that is, the color between connected vertices should be different. Hence, the possible colors for a specific vertex should not include matching colors of its neighbors, which can be shown as follows:
(12)Color_V(i)=Color_All-Color_N(i),
where Color_V(i) represents the color assigned to flow i, Color_All holds the set of all colors, and Color_N(i) represents the color of the neighboring vertex.With (12), we can obtain the final multicoloring results for all the vertices. Vertex selection for multicoloring can significantly affect the network throughput because different flows can exhibit different data rates. In order to improve the network throughput, we give each of the vertices a weight based on its intended data rate. Since mutual interference is below the background noise because of the distance and high propagation loss, it is appropriate to use the transmission distance as a metric for color selection:
(13)w(i)=∑i=1Vd(i)d(i),
where V is the number of vertices and d(i) donates the distance between the transmitter and receiver in a flow i. Using (13), flow i with shorter transmission distance will get higher weight. In order to multicolor the vertices as proposed in VMCCT, we will sort the vertices in descending order of their weights.In Figure7(b), weights are shown on the top of each vertex; we can get the Color_All and sorted weights sets from the graph:
(14)Color_All=(RED,GREEN,YELLOW),(15)Weight={20.0(4),13.3(6),6.6(5),5.0(1),4.0(2),3.6(3)}.
Hence, vertex 4 with the largest weight will be considered first. By using (15) we can assign color to vertex 4 as follows:
(16)Color_V4=(RED,GREEN,YELLOW)-(YELLOW),=(RED,GREEN).
This will yield red and green color to vertex 4. Similarly, vertex 6 will be assigned both green and yellow colors. Then the Color_N(6) will be refreshed to (GREEN, YELLOW), so vertex 5 can only be assigned a red color. Similarly, we can get the final results for flows 1, 2, and 3 as shown in Figure 7(c).


## 4.2.1. Concurrent Transmission Conditions

In this subsection, we discuss the conditions for concurrent transmission. Figure6 shows two concurrent flows scenario in  60 GHz based D2D networks. We can see that two transmitters (A,C) try to send data to two receivers (B,D), in the same time slot. Hence, the sufficient condition 1 for concurrent transmission between pair (A,B) and pair (C,D) with beamwidth θ can be obtained as follows.Figure 6
Concurrent transmission scenario.Concurrent Transmission Sufficient Condition 1. Here we assess whether the flows (A,B) and (C,D) are within the signal beams of each other by using the following condition:
(7)∠DAB>θ2,∠BCD>θ2,
where ∠DAB and ∠BCD could be obtained from the cosine law:
(8)∠DAB=arccosAD¯2+AB¯2-BD¯22AD¯×AB¯,∠BCD=arccosBC¯2+CD¯2-BD¯22BC¯×CD¯.Concurrent flows with mutual interference can be allowed as long as they are apart by a certain threshold distance. The threshold distance is defined as an area where the mutual interference can be seen as background noise. To accomplish this, an exclusive region (ER) around the receiver is defined in [20], which allows concurrent transmission of mutually interfering flows. Hence, we can obtain the sufficient condition 2 for concurrent transmission between pair (A,B) and pair (C,D) as follows.Concurrent Transmission Sufficient Condition 2. If the flows are in conflict with each other then the transmitter-receiver distances of the conflicting flows are checked to see if they are apart a threshold distance by using the following condition:
(9)AD¯>RER∠DAB<θ2,BC¯>RER∠BCD<θ2,
using the ER definition in [20]:
(10)RER=k1GtGrPtN0W1/n,
where RER is the radius of ER as shown in Figure 6 (around DEV D), k1∝(λ/4π)2 is a constant coefficient dependent on the wavelength λ, Gt and Gr are the antenna gains for the transmitter and receiver, respectively, Pt is the transmit power, and n is the pathloss exponent. Here condition 2 will keep the accumulative interference in the network below an acceptable threshold.Both concurrent transmission conditions 1 and 2 realize the possibility of concurrent transmission for different flows. For illustration, as in Figure6, receiver D is inside the beamwidth of transmitter A, but the distance between A and D is larger than RER. Therefore, concurrent transmission of pairs (A,B) and (C,D) would be allowed.


## 4.2.2. Construction of Conflict Matrix

A conflict matrix (CM) represents the relationship between different flows. The relationship is represented by 1 (conflict) and 0 (no conflict) as shown below:(11)CM(6×6)=010001001000110000001000000000100010.Equation (11) shows a conflict matrix of 6 flows. Element 1 results when the corresponding flows fail to meet concurrent conditions 1 and 2. Therefore, they cannot be allowed to transmit their data concurrently. The rows of the conflict matrix represent the conflict relationship among flows. Each row is constructed by considering the conflict relationship from the corresponding flow to all the other flows unilaterally. Therefore if some flow i has no conflict with flow j, it does not necessarily mean that flow j also has no conflict with flow i. This situation can be seen in matrix as shown in (11) at indices (1,2) and (2,1). The conflict matrix can also be represented as an undirected graph called conflict graph. The conflict matrix in (11) is converted into conflict graph as shown in Figure 7(a). The flows are represented as vertices and their mutual conflicts are represented as edges between them. It should be noted that values in the conflict matrix for flow 1 and 2 at indices (1,2) and (2,1) are not same but they have resulted in a conflict (an edge) in conflict graph.Figure 7
Conflict graph representation of VC and VMCCT.


## 4.2.3. Time-Slot Allocation Based on VC

Time slot, being scarce resource, requires efficient allocation. We employ VC algorithm to effectively resolve conflict among flows and efficiently assign time resource. VC algorithm has been used for resource allocation in different types of networks [28–31] including mmWave, cognitive radios, and ad hoc networks. VC will color all vertices (flows) in conflict graph with minimum number of colors (time slots). Two directly connected vertices cannot have the same color. We can see in Figure 7(b) that VC colors all the six vertices using three colors. With green, red, and yellow representing first, second, and third time slots, respectively, we can transmit flows 2 and 6 in first time slot, flows 1, 4, and 5 in second time slot, and flow 3 in the third time slot.


## 4.2.4. Time-Slot Allocation Based on VMCCT

The conservative time-slot allocation based on VC is not efficient. Our proposed multicoloring algorithm allocates time slots more aggressively to improve network throughput. Algorithm3 shows the details of our proposed scheme. Our scheme starts by constructing a conflict matrix (Algorithm 2 lines 3–16). The conflict matrix is then used to resolve conflict and assign time slots based on VC and VMCCT.Algorithm 3:Vertex multicoloring concurrent transmission algorithm.
(1)Inputs: Set of all flows that is, Flow(1) to Flow(V)
(2)Output: vertex multi-color graph for scheduling concurrent transmission
(3)forRow=1; Row<V; Row++do
(4)forColumn=1; Column<V; Column++do
(5)ifRow!=Columnthen
(6)α=Angle(Row,Column)
(7)D=Distance(Row,Column)
(8)ifα<θ/2 and D<ERthen
(9)Use relay selection algorithms, go back and calculate α and D
(10)if no relay found Conflict Matrix(Row, Column) = 1
(11)else
(12)Conflict Matrix(Row, Column) = 0
(13)end if
(14)end if
(15)end for
(16)end for
(17)Color_Graph=Function_VC(ConflictMatrix)
(18)forCnt=1; Cnt<V; Cnt++do
(19)D(Cnt)=Function_Distance(Flow(Cnt))
(20)end for
(21)forCnt=1; Cnt<V; Cnt++do
(22)w(Cnt)=Function_Weight(D(Cnt))
(23)end for
(24)forCnt=1; Cnt<V; Cnt++do
(25)x=Max⁡(w)
(26)Color_V(x)=Color_All-Color_N(x)
(27)w(x)=0
(28)end forThe proposed algorithm can be explained with the help of Figure7. Time-slot allocation based on VC and VMCCT is shown in Figures 7(b) and 7(c), respectively. The basic principle with multiple colors for a vertex is the same as the traditional VC; that is, the color between connected vertices should be different. Hence, the possible colors for a specific vertex should not include matching colors of its neighbors, which can be shown as follows:
(12)Color_V(i)=Color_All-Color_N(i),
where Color_V(i) represents the color assigned to flow i, Color_All holds the set of all colors, and Color_N(i) represents the color of the neighboring vertex.With (12), we can obtain the final multicoloring results for all the vertices. Vertex selection for multicoloring can significantly affect the network throughput because different flows can exhibit different data rates. In order to improve the network throughput, we give each of the vertices a weight based on its intended data rate. Since mutual interference is below the background noise because of the distance and high propagation loss, it is appropriate to use the transmission distance as a metric for color selection:
(13)w(i)=∑i=1Vd(i)d(i),
where V is the number of vertices and d(i) donates the distance between the transmitter and receiver in a flow i. Using (13), flow i with shorter transmission distance will get higher weight. In order to multicolor the vertices as proposed in VMCCT, we will sort the vertices in descending order of their weights.In Figure7(b), weights are shown on the top of each vertex; we can get the Color_All and sorted weights sets from the graph:
(14)Color_All=(RED,GREEN,YELLOW),(15)Weight={20.0(4),13.3(6),6.6(5),5.0(1),4.0(2),3.6(3)}.
Hence, vertex 4 with the largest weight will be considered first. By using (15) we can assign color to vertex 4 as follows:
(16)Color_V4=(RED,GREEN,YELLOW)-(YELLOW),=(RED,GREEN).
This will yield red and green color to vertex 4. Similarly, vertex 6 will be assigned both green and yellow colors. Then the Color_N(6) will be refreshed to (GREEN, YELLOW), so vertex 5 can only be assigned a red color. Similarly, we can get the final results for flows 1, 2, and 3 as shown in Figure 7(c).


## 5. Performance Evaluations

In order to evaluate our proposed relay selection schemes and scheduling algorithm, we consider15×15 meters’ room with random distribution of 30 DEVs. All the DEVs are placed using polar coordinates, hence information about their locations and distances from the PNC is known. Data transmission is based on IEEE 802.15.3c standard. We have evaluated our proposed schemes under single- and multihop scenarios. We assume static locations of DEVs for the duration of superframe. The mobility in IEEE 802.15.3c based WPAN is very low (1 meter/sec). In such a scenario, ignoring mobility for the duration of superframe is not impractical. The simulation parameters are shown in Table 2.Table 2
Simulation parameters.
Parameters
Values
System bandwidth(W)
1800 MHz
Transmission power(Pt)
0.1 mW
Background noise(No)
−134 dBm/MHz
Path loss exponent(n)
3
Reference distance(dref)
1.5 m
Path loss atdref  (PLo)
71.5 dB
Slot timeΔt
18μsec
Number of slots in superframe
1000


### 5.1. Single-Hop Scenario

We compare our proposed VMCCT scheme [5] for single-hop scenario with the traditional single-hop GA scheme presented in [20] as well as with the well-known TDMA method under the same assumptions and system model. The reader is referred to [5] for further details while we provide some details for completeness.Figures8 and 9 show the performance of VMCCT average flow rate with respect to increasing flow density and beamwidths, respectively. Beamwidths of 30 and 60 degrees are considered in Figure 8. We can see that the traditional TDMA scheme can only transmit one flow per time slot. While compared to GA, we can see that average flows per slot using VMCCT are better than GA. The average flow per slot is improved by almost one for both 30 and 60 degrees’ beamwidths. VMCCT scheme is also evaluated against increasing beamwidths as shown in Figure 9. By increasing the beamwidth, the signal can span larger area resulting in more interference. Hence, the chances of concurrent transmission will also be reduced. We have used flow densities of 8 and 14 for evaluating the effects of increased beamwidth on flow rate. It can be seen that almost an additional flow can be transmitted per slot with VMCCT than that of the GA scheme.Figure 8
Improved average flows throughput versus flow density.Figure 9
Improved average flow throughput versus increasing beamwidth.Figures10 and 11 show the VMCCT performance by enhancing network throughput with respect to increasing flow density and beamwidth, respectively. It can be seen in Figure 10 that VMCCT improved network throughput as compared to GA and hence can support applications such as HD TV, online gaming, and uncompressed video with stringent bandwidth and quality requirements. On the other hand, TDMA provides a constant data rate as it supports one transmission at any particular time. Similar results can be seen in Figure 11, where VMCCT decreases more gracefully due to increasing beamwidths, as compared to other schemes. On average, our scheme provides throughput improvement of 2 Gbps (60-degree beamwidth) and 3 Gbps (30-degree beamwidth), as compared to GA. The rationale behind better performance gain is the limited interference at 30-degree beamwidth as compared to 60 degrees. In terms of percentage, on average, VMCCT improves network throughput by 19% and average flows per slot by 12% as compared to the GA scheme.Figure 10
Improved network throughput versus flow density.Figure 11
Network throughput versus increasing beamwidth.


### 5.2. Multihop Scenario

In this section, we will evaluate our proposed relay selection schemes. We also have evaluated our proposed VMCCT scheme in multihop scenario using the proposed relay selection schemes. We are considering a typical WPANs scenario, where most of the transmissions are within intragroup with occasional intergroup transmissions. We first evaluate our relay selection schemes and then provide simulation results to show their effectiveness in conjunction with our proposed VMCCT scheme.


#### 5.2.1. Outage Analysis

In order to evaluate our proposed relay selection schemes, we use outage probability (OP) as metric. OP is an important performance indicator in wireless systems. OP can be defined as the probability that the end-to-end SNR falls below a predefined thresholdγth. The type of threshold γth varies according to different quality of service requirements. For example, the value may be based on minimum error rate or a minimum data rate. Since  60 GHz promises data rate in Gbps, therefore we choose achievable transmission rate as a threshold, which can be calculated as
(17)R=Wfηlog⁡2⁡1+γthγf,
where Wf denotes adjustments to the system bandwidth efficiency, γf is the system SINR implementation efficiency, and η is a correction factor to facilitate the derivation. It is chosen to be 1.Since we are considering two-hop scenario, according to (17) in half-duplex relay system, to meet a required end-to-end data rate R, both hops should support a rate greater or equal to 2R. Thus, γth becomes
(18)γth=γf2(2R/Wfη)-1.
In relay assisted transmission in two-hop scenario, the outage is decided by either of the weaker hops. Thus, OP can be expressed as
(19)Pout=Pr(min⁡⁡(γCR,γRD))<γth.
Thus we have
(20)Pout(d1,d2,dI,γth)=Pr(min⁡⁡(γCR(d1),γRD(dI,d2))<γth)=1-(1-FCR(d1,γth))(1-FRD(d1,dI,γth))=FCR(d1,γth)+FRD(d1,dI,γth)-FCRd1,γthFRDdI,d2,γth,
where FCR(d1,γth) and FRD(dI,d2,γth) are the cumulative distribution functions of the received SINR of both hops, that is, CR and R-D, respectively. Rayleigh distribution is considered in [32] to model non-line-of-sight (NLOS) scenario for office, home, and library environment. Hence, the instantaneous received power of the desired signal follows an exponential distribution with probability density function (pdf) expressed as
(21)PγCR(x)=1Pr-exp⁡⁡-xPr-.
The OP of C-R hop can be calculated as
(22)FCR=Pr(x<γthN0)=1-Pr(x>γthN0)=1-∫γthN0∞‍1Pr-exp⁡⁡-xPr-dx=1-exp⁡⁡-γthN0Pr-,
where Pr-(x)=PtCKCRd0/H2+d12nεCR.ForR-D hop, the desired and interfering channel coefficients are considered to be independent and not identically distributed (INID). Both follow Rayleigh distribution. Thus, the OP of the R-D hop can be approximated as
(23)FRD=Pr⁡(x<γth(y+N0))=1-Pr(x>γth(y+N0))=1-∫0∞‍f(y)∫γth(y+N0)∞‍f(x)dxdy=1-∫0∞‍1PrI(RD)exp⁡⁡(-yPrI(RD))×∫γth(y+N0)∞‍1PrRDexp⁡⁡(-xPrRD)dxdy=1-PrRDPrRD+PrI(RD)γthexp⁡⁡(-γthN0PrRD).Hence, OP at a given DEV position can be obtained by inserting (21) and (22) in (19) as follows:
(24)Pout(d1,d2,γth)=1-exp⁡⁡-γthPr(CR)+1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD))-1-exp⁡⁡-γthPr(CD)×1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD)).


#### 5.2.2. Simulation Results

In this subsection, numerical results are employed to evaluate our proposed relay selection and VMCCT schemes. Ergodic capacity and OP are compared for direct transmission, fixed relay, and our proposed relay selection schemes. The simulation parameters are shown in Table2. In Figure 12, OP of our proposed relay schemes is compared with direct transmission and fixed relay selection schemes. The Rx position is fixed at D, while different relays are selected with varying distances. We can see that there is a point where OP is the minimum. When the distance increases, relays help reduce the OP. Our proposed schemes select the minimum relay path with the efforts of finding relay in the midmost position. This helps reduce the OP of our proposed schemes. Figure 13 compares the OP of fixed relay node and direct transmission with our proposed relay selection schemes. We can see that as the distance between Tx and Rx increases, fixed relay node’s performance degrades significantly as compared to our relay selection schemes. Distance plays a major role in 60 GHz based D2D network and the tremendous propagation loss requires careful relay selection in such system. Our proposed scheme outperforms both direct and fixed relay nodes by significantly improving OP. Ergodic capacity is analyzed in Figure 14. We can see that ergodic capacity is very low in direct transmission. As the distances increases, ergodic capacity decreases rapidly. However, our proposed relay selection schemes degrades gracefully as compared to other schemes. The fixed relay node and our relay selection schemes are equal only on the condition that the fixed relay node be located at the optimal position. Overall, our proposed relay selection schemes perform better as compared to other schemes by improving OP and ergodic capacity, significantly.Figure 12
Outage probability with varying relay distance.Figure 13
Outage probability with varyingTx-Rx distance.Figure 14
Ergodic capacity with varyingTx-Rx distances.We used our proposed VMCCT algorithm in multihop scenario. Our proposed algorithms try to find a suitable relay placed at near-equal distance fromTx and Rx. Our algorithm works equally well in multihop scenario and both GA and TDMA. Figures 15 and 16 show performance of VMCCT in single- and multihop scenarios, respectively. Improvement in average flow throughput against traffic flow density can be seen in Figure 15. We evaluated our system with up to 50 flows under the very dense deployment. We can see that the proposed VMCCT algorithm in the multihop scenario performs better as compared to other schemes by significantly increasing average flow throughput. The use of relays helps alleviate network interference and encourages more concurrent transmissions. Similarly, in Figure 16, we can see that the network throughput is significantly improved using VMCCT in multihop scenario. Overall, the performance of our proposed VMCCT scheme outperforms GA by improving the network throughput.Figure 15
Average flow throughput in multihop scenario.Figure 16
Network throughput in multihop scenario.


## 5.1. Single-Hop Scenario

We compare our proposed VMCCT scheme [5] for single-hop scenario with the traditional single-hop GA scheme presented in [20] as well as with the well-known TDMA method under the same assumptions and system model. The reader is referred to [5] for further details while we provide some details for completeness.Figures8 and 9 show the performance of VMCCT average flow rate with respect to increasing flow density and beamwidths, respectively. Beamwidths of 30 and 60 degrees are considered in Figure 8. We can see that the traditional TDMA scheme can only transmit one flow per time slot. While compared to GA, we can see that average flows per slot using VMCCT are better than GA. The average flow per slot is improved by almost one for both 30 and 60 degrees’ beamwidths. VMCCT scheme is also evaluated against increasing beamwidths as shown in Figure 9. By increasing the beamwidth, the signal can span larger area resulting in more interference. Hence, the chances of concurrent transmission will also be reduced. We have used flow densities of 8 and 14 for evaluating the effects of increased beamwidth on flow rate. It can be seen that almost an additional flow can be transmitted per slot with VMCCT than that of the GA scheme.Figure 8
Improved average flows throughput versus flow density.Figure 9
Improved average flow throughput versus increasing beamwidth.Figures10 and 11 show the VMCCT performance by enhancing network throughput with respect to increasing flow density and beamwidth, respectively. It can be seen in Figure 10 that VMCCT improved network throughput as compared to GA and hence can support applications such as HD TV, online gaming, and uncompressed video with stringent bandwidth and quality requirements. On the other hand, TDMA provides a constant data rate as it supports one transmission at any particular time. Similar results can be seen in Figure 11, where VMCCT decreases more gracefully due to increasing beamwidths, as compared to other schemes. On average, our scheme provides throughput improvement of 2 Gbps (60-degree beamwidth) and 3 Gbps (30-degree beamwidth), as compared to GA. The rationale behind better performance gain is the limited interference at 30-degree beamwidth as compared to 60 degrees. In terms of percentage, on average, VMCCT improves network throughput by 19% and average flows per slot by 12% as compared to the GA scheme.Figure 10
Improved network throughput versus flow density.Figure 11
Network throughput versus increasing beamwidth.


## 5.2. Multihop Scenario

In this section, we will evaluate our proposed relay selection schemes. We also have evaluated our proposed VMCCT scheme in multihop scenario using the proposed relay selection schemes. We are considering a typical WPANs scenario, where most of the transmissions are within intragroup with occasional intergroup transmissions. We first evaluate our relay selection schemes and then provide simulation results to show their effectiveness in conjunction with our proposed VMCCT scheme.


### 5.2.1. Outage Analysis

In order to evaluate our proposed relay selection schemes, we use outage probability (OP) as metric. OP is an important performance indicator in wireless systems. OP can be defined as the probability that the end-to-end SNR falls below a predefined thresholdγth. The type of threshold γth varies according to different quality of service requirements. For example, the value may be based on minimum error rate or a minimum data rate. Since  60 GHz promises data rate in Gbps, therefore we choose achievable transmission rate as a threshold, which can be calculated as
(17)R=Wfηlog⁡2⁡1+γthγf,
where Wf denotes adjustments to the system bandwidth efficiency, γf is the system SINR implementation efficiency, and η is a correction factor to facilitate the derivation. It is chosen to be 1.Since we are considering two-hop scenario, according to (17) in half-duplex relay system, to meet a required end-to-end data rate R, both hops should support a rate greater or equal to 2R. Thus, γth becomes
(18)γth=γf2(2R/Wfη)-1.
In relay assisted transmission in two-hop scenario, the outage is decided by either of the weaker hops. Thus, OP can be expressed as
(19)Pout=Pr(min⁡⁡(γCR,γRD))<γth.
Thus we have
(20)Pout(d1,d2,dI,γth)=Pr(min⁡⁡(γCR(d1),γRD(dI,d2))<γth)=1-(1-FCR(d1,γth))(1-FRD(d1,dI,γth))=FCR(d1,γth)+FRD(d1,dI,γth)-FCRd1,γthFRDdI,d2,γth,
where FCR(d1,γth) and FRD(dI,d2,γth) are the cumulative distribution functions of the received SINR of both hops, that is, CR and R-D, respectively. Rayleigh distribution is considered in [32] to model non-line-of-sight (NLOS) scenario for office, home, and library environment. Hence, the instantaneous received power of the desired signal follows an exponential distribution with probability density function (pdf) expressed as
(21)PγCR(x)=1Pr-exp⁡⁡-xPr-.
The OP of C-R hop can be calculated as
(22)FCR=Pr(x<γthN0)=1-Pr(x>γthN0)=1-∫γthN0∞‍1Pr-exp⁡⁡-xPr-dx=1-exp⁡⁡-γthN0Pr-,
where Pr-(x)=PtCKCRd0/H2+d12nεCR.ForR-D hop, the desired and interfering channel coefficients are considered to be independent and not identically distributed (INID). Both follow Rayleigh distribution. Thus, the OP of the R-D hop can be approximated as
(23)FRD=Pr⁡(x<γth(y+N0))=1-Pr(x>γth(y+N0))=1-∫0∞‍f(y)∫γth(y+N0)∞‍f(x)dxdy=1-∫0∞‍1PrI(RD)exp⁡⁡(-yPrI(RD))×∫γth(y+N0)∞‍1PrRDexp⁡⁡(-xPrRD)dxdy=1-PrRDPrRD+PrI(RD)γthexp⁡⁡(-γthN0PrRD).Hence, OP at a given DEV position can be obtained by inserting (21) and (22) in (19) as follows:
(24)Pout(d1,d2,γth)=1-exp⁡⁡-γthPr(CR)+1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD))-1-exp⁡⁡-γthPr(CD)×1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD)).


### 5.2.2. Simulation Results

In this subsection, numerical results are employed to evaluate our proposed relay selection and VMCCT schemes. Ergodic capacity and OP are compared for direct transmission, fixed relay, and our proposed relay selection schemes. The simulation parameters are shown in Table2. In Figure 12, OP of our proposed relay schemes is compared with direct transmission and fixed relay selection schemes. The Rx position is fixed at D, while different relays are selected with varying distances. We can see that there is a point where OP is the minimum. When the distance increases, relays help reduce the OP. Our proposed schemes select the minimum relay path with the efforts of finding relay in the midmost position. This helps reduce the OP of our proposed schemes. Figure 13 compares the OP of fixed relay node and direct transmission with our proposed relay selection schemes. We can see that as the distance between Tx and Rx increases, fixed relay node’s performance degrades significantly as compared to our relay selection schemes. Distance plays a major role in 60 GHz based D2D network and the tremendous propagation loss requires careful relay selection in such system. Our proposed scheme outperforms both direct and fixed relay nodes by significantly improving OP. Ergodic capacity is analyzed in Figure 14. We can see that ergodic capacity is very low in direct transmission. As the distances increases, ergodic capacity decreases rapidly. However, our proposed relay selection schemes degrades gracefully as compared to other schemes. The fixed relay node and our relay selection schemes are equal only on the condition that the fixed relay node be located at the optimal position. Overall, our proposed relay selection schemes perform better as compared to other schemes by improving OP and ergodic capacity, significantly.Figure 12
Outage probability with varying relay distance.Figure 13
Outage probability with varyingTx-Rx distance.Figure 14
Ergodic capacity with varyingTx-Rx distances.We used our proposed VMCCT algorithm in multihop scenario. Our proposed algorithms try to find a suitable relay placed at near-equal distance fromTx and Rx. Our algorithm works equally well in multihop scenario and both GA and TDMA. Figures 15 and 16 show performance of VMCCT in single- and multihop scenarios, respectively. Improvement in average flow throughput against traffic flow density can be seen in Figure 15. We evaluated our system with up to 50 flows under the very dense deployment. We can see that the proposed VMCCT algorithm in the multihop scenario performs better as compared to other schemes by significantly increasing average flow throughput. The use of relays helps alleviate network interference and encourages more concurrent transmissions. Similarly, in Figure 16, we can see that the network throughput is significantly improved using VMCCT in multihop scenario. Overall, the performance of our proposed VMCCT scheme outperforms GA by improving the network throughput.Figure 15
Average flow throughput in multihop scenario.Figure 16
Network throughput in multihop scenario.


## 5.2.1. Outage Analysis

In order to evaluate our proposed relay selection schemes, we use outage probability (OP) as metric. OP is an important performance indicator in wireless systems. OP can be defined as the probability that the end-to-end SNR falls below a predefined thresholdγth. The type of threshold γth varies according to different quality of service requirements. For example, the value may be based on minimum error rate or a minimum data rate. Since  60 GHz promises data rate in Gbps, therefore we choose achievable transmission rate as a threshold, which can be calculated as
(17)R=Wfηlog⁡2⁡1+γthγf,
where Wf denotes adjustments to the system bandwidth efficiency, γf is the system SINR implementation efficiency, and η is a correction factor to facilitate the derivation. It is chosen to be 1.Since we are considering two-hop scenario, according to (17) in half-duplex relay system, to meet a required end-to-end data rate R, both hops should support a rate greater or equal to 2R. Thus, γth becomes
(18)γth=γf2(2R/Wfη)-1.
In relay assisted transmission in two-hop scenario, the outage is decided by either of the weaker hops. Thus, OP can be expressed as
(19)Pout=Pr(min⁡⁡(γCR,γRD))<γth.
Thus we have
(20)Pout(d1,d2,dI,γth)=Pr(min⁡⁡(γCR(d1),γRD(dI,d2))<γth)=1-(1-FCR(d1,γth))(1-FRD(d1,dI,γth))=FCR(d1,γth)+FRD(d1,dI,γth)-FCRd1,γthFRDdI,d2,γth,
where FCR(d1,γth) and FRD(dI,d2,γth) are the cumulative distribution functions of the received SINR of both hops, that is, CR and R-D, respectively. Rayleigh distribution is considered in [32] to model non-line-of-sight (NLOS) scenario for office, home, and library environment. Hence, the instantaneous received power of the desired signal follows an exponential distribution with probability density function (pdf) expressed as
(21)PγCR(x)=1Pr-exp⁡⁡-xPr-.
The OP of C-R hop can be calculated as
(22)FCR=Pr(x<γthN0)=1-Pr(x>γthN0)=1-∫γthN0∞‍1Pr-exp⁡⁡-xPr-dx=1-exp⁡⁡-γthN0Pr-,
where Pr-(x)=PtCKCRd0/H2+d12nεCR.ForR-D hop, the desired and interfering channel coefficients are considered to be independent and not identically distributed (INID). Both follow Rayleigh distribution. Thus, the OP of the R-D hop can be approximated as
(23)FRD=Pr⁡(x<γth(y+N0))=1-Pr(x>γth(y+N0))=1-∫0∞‍f(y)∫γth(y+N0)∞‍f(x)dxdy=1-∫0∞‍1PrI(RD)exp⁡⁡(-yPrI(RD))×∫γth(y+N0)∞‍1PrRDexp⁡⁡(-xPrRD)dxdy=1-PrRDPrRD+PrI(RD)γthexp⁡⁡(-γthN0PrRD).Hence, OP at a given DEV position can be obtained by inserting (21) and (22) in (19) as follows:
(24)Pout(d1,d2,γth)=1-exp⁡⁡-γthPr(CR)+1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD))-1-exp⁡⁡-γthPr(CD)×1-Pr(RD)Pr(RD)+PrI(RD)γthexp⁡⁡(-γthN0Pr(RD)).


## 5.2.2. Simulation Results

In this subsection, numerical results are employed to evaluate our proposed relay selection and VMCCT schemes. Ergodic capacity and OP are compared for direct transmission, fixed relay, and our proposed relay selection schemes. The simulation parameters are shown in Table2. In Figure 12, OP of our proposed relay schemes is compared with direct transmission and fixed relay selection schemes. The Rx position is fixed at D, while different relays are selected with varying distances. We can see that there is a point where OP is the minimum. When the distance increases, relays help reduce the OP. Our proposed schemes select the minimum relay path with the efforts of finding relay in the midmost position. This helps reduce the OP of our proposed schemes. Figure 13 compares the OP of fixed relay node and direct transmission with our proposed relay selection schemes. We can see that as the distance between Tx and Rx increases, fixed relay node’s performance degrades significantly as compared to our relay selection schemes. Distance plays a major role in 60 GHz based D2D network and the tremendous propagation loss requires careful relay selection in such system. Our proposed scheme outperforms both direct and fixed relay nodes by significantly improving OP. Ergodic capacity is analyzed in Figure 14. We can see that ergodic capacity is very low in direct transmission. As the distances increases, ergodic capacity decreases rapidly. However, our proposed relay selection schemes degrades gracefully as compared to other schemes. The fixed relay node and our relay selection schemes are equal only on the condition that the fixed relay node be located at the optimal position. Overall, our proposed relay selection schemes perform better as compared to other schemes by improving OP and ergodic capacity, significantly.Figure 12
Outage probability with varying relay distance.Figure 13
Outage probability with varyingTx-Rx distance.Figure 14
Ergodic capacity with varyingTx-Rx distances.We used our proposed VMCCT algorithm in multihop scenario. Our proposed algorithms try to find a suitable relay placed at near-equal distance fromTx and Rx. Our algorithm works equally well in multihop scenario and both GA and TDMA. Figures 15 and 16 show performance of VMCCT in single- and multihop scenarios, respectively. Improvement in average flow throughput against traffic flow density can be seen in Figure 15. We evaluated our system with up to 50 flows under the very dense deployment. We can see that the proposed VMCCT algorithm in the multihop scenario performs better as compared to other schemes by significantly increasing average flow throughput. The use of relays helps alleviate network interference and encourages more concurrent transmissions. Similarly, in Figure 16, we can see that the network throughput is significantly improved using VMCCT in multihop scenario. Overall, the performance of our proposed VMCCT scheme outperforms GA by improving the network throughput.Figure 15
Average flow throughput in multihop scenario.Figure 16
Network throughput in multihop scenario.


## 6. Conclusion

In order to improve the network capacity in 60 GHz based D2D networks, we jointly consider relay selection and scheduling algorithm. Owing to tremendous propagation loss, distance is used as a main metric for relay selection. Apart from distance, a relay with midmost positioning is encouraged for both inter and intragroup transmission scenarios. A novel distributed relay selection algorithm is proposed for intragroup transmission scenario. The outage probability analysis is provided to compare our relay selection schemes with fixed relay selection schemes. Furthermore, we evaluated our proposed relay selection schemes jointly with scheduling algorithm in single- and multihop scenarios. We have compared our results with GA and TDMA under the same system model. Our proposed scheme outperforms both GA and TDMA in terms of network throughput and average flows per slot. Network throughput and average number of flows per slot are improved by19% and 12%, respectively.



---

*Source: 205163-2015-03-01.xml*