# MC-GiV2V: Multichannel Allocation in mmWave-Based Vehicular Ad Hoc Networks

Authors: Wooseong Kim
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

During last several years, mobile communications using mmWave spectrum have been intensively researched for 5G wireless networks. Now the mmWave wireless technologies are evolved into direct device-to-device communications for a single or multihop communication via Giga-bit links. Vehicular ad hoc networks (VANETs) are one of the most attractive areas to apply the direct mmWave communications. In this paper, we propose a Giga-V2V (GiV2V) network, in which vehicles query and deliver high quality video and sensor data of smart and self-driving cars using mmWave communications instead of current dedicated short-range communications (DSRC). In the GiV2V networks, vehicles probably form a grid topology along lanes of a road, which leads to align mmWave beams of the vehicles and cause mutual interference among them. As channel diversity can resolve effectively the interference between mmWave beams, we propose several heuristic algorithms for channel assignment of each beam in the GiV2V networks. We investigate the proposed algorithms using simulation and compare performance with well-known metaheuristic algorithms for this NP-Hard problem.


---

## Body

## 1. Introduction

5G wireless technology opens a new era of Giga-bit rate data communications using mmWave spectrums for high quality and real-time multimedia data. Many companies and universities built testbeds for measurement study of the mmWave communications and made efforts to demonstrate feasibility of beam forming and tracking developed for mobile communications. The 5G mobile communications are now being standardized in ITU [1], 5GPPP [2], 3GPP [3], and so forth and ready to commercialize. The mmWave communications are also developed for local area communications (e.g., WPAN and WLAN) using 60 GHz unlicensed bands such as IEEE 802.15.3 Task Group 3c (TG3c) [4] and IEEE 802.11ad [5].Due to severe penetration loss and reflection from short wavelength, mmWave communications are almost feasible only in Line-of-Sight (LoS) environment. When a mmWave link between a sender and receiver is blocked (i.e., non-LoS), relay operation is necessary; in 802.11ad WLAN, the mobile station can access to an access point (AP) via a relay station. Such Device-to-Device (D2D) direct communications using the mmWave spectrum attract attentions to support Giga-bit data rate in proximity services and offloading in cellular networks.For dissemination of safety messages over roads, V2X communications (e.g., vehicle-to-vehicle, infrastructure, or pedestrian) have been researched and developed intensively during the last decade. At the end, auto companies recently release solutions based on the IEEE 802.11p/WAVE standard which satisfy requirements of safety messages (e.g., low-latency delivery less than 100ms) and support infotainment communications up to 6-27 Mbps using separate service channels. However, a future smart car capable of autonomous driving demands much higher data rate and low latency for vehicle control technology, which relies on large amount of data from near or medium range radars and camera sensors of neighboring vehicles. In particular, higher resolution visual data like Ultra High Definition (UHD) video can enable precise vehicle control; for example, if using 2 M pixel camera instead of 0.3 M in the lane keeping system, curvature recognition accuracy on the front road increases from 30 to 50 m, which leads to more safe and fuel efficient driving.In this paper, Giga-bit vehicle-to-vehicle communication (GiGaV2V or GiV2V) using the mmWave is proposed to support aforementioned high quality multimedia data. Research on the GiV2V has not been conducted popularly and not matured yet to the best of our knowledge. The GiV2V can improve network throughput because of spatial frequency reuse by directional antennas that are typically used to compensate high path loss of the mmWave. However, the spatial division may not occur constructively since vehicles are mostly aligned along lanes of roads and form a grid topology where mmWave beams are also aligned and cause mutual interference. Directivity of the directional antenna increases not only the antenna gain and signal to noise ratio (SNR), but also interferences to other nodes. To mitigate the interference, we propose multichannel- (MC-) GiV2V, a channel diversity scheme in GiV2V networks. Here we introduce several multichannel allocation algorithms with many available channels in the mmWave spectrum; for example, IEEE 802.11ad has 6 channels of each 2 GHz bandwidth.Our proposed algorithms are distributed, centralized greedy and hybrid algorithms. The distributed algorithm searches a local optimal allocation within an interference region and the greedy algorithm assigns channels based on global information (i.e., SINR of all receive nodes). The hybrid approach is a mixed algorithm of the above two algorithms. Details of algorithms are explained in Section6. According to simulation results in Section 7, the hybrid approach shows best throughput among them since it probably searches a globally optimal allocation with well-distributed initial conditions. Furthermore, three well-known metaheuristic algorithms are investigated for comparison study with our proposed algorithms.


## 2. Related Works

Directional antenna was exhaustively exploited for a MAC protocol in multihop ad hoc networks. Most of those researches assume 2.4 or 5 GHz Wi-Fi, but similar challenges also exist in mmWave-based WLANs. Ko et al. [6] first propose a modified 802.11 Distributed Coordination Function (DCF) for directional antennas, which maintains directional channel availability based on the GPS information. Takai et al. [7] use Angle of Arrivals (AOAs) of Request to Send (RTS) and Clear To Send (CTS) instead of GPS information. Choudhury et al. [8] propose a basic directional MAC (DMAC) which includes Directional Network Allocation Vector (DNAV) and listens incoming packets omnidirectionally to trace their Direction of Arrival (DoA). Kolar et al. [9] introduce a greed queuing to solve a Head of Line (HoL) problem with the DNAV table of beam directions. Ramanathan et al. [10] suggest different backoff algorithms for different events such as busy channel and missing CTS or ACK and also tight power control scheme. In order to solve a hidden terminal problem in the DMAC, Circular Directional RTS (CDR) [11], CRCM [12], and DtD-MAC [13] conduct sequential RTS and CTS transmissions to all directions, which deals with deafness and directional hidden terminals from unheard nodes or asymmetric antenna gain. But the circular transmissions suffer from control overhead and excessive delay according to number of sectors. Gossain et al. [14] propose simultaneous circular RTS/CTS to reduce the delay with Diametrically Opposite Direction (DOD) which removes duplicate transmissions of RTSs and CTSs in the overlapped area. Furthermore, Deafness Avoidance and Collision Avoidance (DMAC-DACA) [15] and DMAC with Deafness Avoidance (DMAC/DA) [16] reduce circular transmission overhead by DNAV reservation and beam direction information, with which nodes can determine spatial diversity and schedule pending transmitters. Singh et al. [17] propose a Memory-guided DMAC (MDMAC), as a fully distributed MAC protocol, which enables approximate TDM scheduling for wireless meshes using the memory about transmission success or fail.Recently, mmWave communications emerge as one of the key 5G technologies. Its feasibility has been explored by many universities and companies. Rappaport et al. [18] perform measurement campaign in New York City on the 28 GHz, 38 GHz, and 73 GHz bands [19, 20] and establish a channel model of the mmWave communications. The mmWave links are considered not only for access links of mobile devices, but also for backhaul links that can constitute wireless mesh networks [21, 22]. 3GPP [3] completes standards of a new radio (i.e., mmWave communications) and now moves into device-to-device communications for the mmWave which can be applied to legacy proximity services in cellular networks.The mmWave for WLANs has already been explored for home and mobile appliances at indoor environment. Also, several standards using 60 GHz unlicensed bands were released such as IEEE 802.15.3 Task Group 3c (TG3c) [4] and IEEE 802.11ad [5], which specify physical and MAC protocols (Carrier Sensing Multiple Access/Collision Avoidance (CSMA/CA), Time Division Multiple Access (TDMA), etc.). Also, those WPAN/WLAN standards define relay operation that can be utilized for multihop ad hoc networks. For instance, an access point (AP) arranges service periods (SPs) for Directional Multi-Giga-bit (DMG) mobile stations (STAs), when the AP receives a request of Relay DMG STA (RDS) search from a STA for NLOS environment. During the SPs, a source and destination STA exchange the packets with candidate RDSs nearby. Then, the source STA asks several RDSs with good channel (i.e., high SNR) to report channel condition to both source and destination STAs. Finally, the source STA selects a best RDS that has highest SNR in both links.In [23], demanded rate-based coordination of the directional or omnidirectional transmissions is proposed with allocation of time slots for spatial and time reuse of frequency in mmWave WLANs. Sing et al. [24] propose a multihop MAC protocol for indoor mmWave environment where diffraction and blockage highly occur due to fixed or moving obstacles (e.g., people and furniture). They develop a diffraction model to estimate link connectivity and decide multihop relays. From simulation, it is proved that proposed approach improves network throughput with low overhead rather than an AP-based single hop communication. Reference [25] describes tactical scenarios using mmWave links for a secure channel in military ad hoc networks and relay operation in NLOS environment. In [26], a CSMA/CA-like MAC protocol for directional mmWave is proposed. Chen et al. [27] propose a spatial reuse strategy with directional antennas in IEEE 802.11 ad networks. Son et al. [28] propose a Frame based Directive MAC protocol (FDMAC) which is a centralized scheduling algorithm for the Pico-Net Controller (PNC) based on greedy coloring providing multiple concurrent transmissions. Thornburg et al. [29] analyze throughput of ad hoc networks using mmWave communications. Authors establish a 2D-PPP model of nodes and obstacles deployment and evaluate performance of one- or two-way communications in terms of SINR and coverage with simulation. In [30], Park et al. propose a Multiband Directional Neighbor Discovery (MDND) for self-organization of ad hoc networks, which utilizes dual radios with different bands and antenna types, a 2.4 GHz band with an omnidirectional antenna and 60 GHz band with a directional antenna. Reference [31] proposes a stochastic model of vehicular communications at highway for mmWave communications, where mmWave-based road side units are deployed for infrastructure to vehicle communications with high data rate rather than vehicle-to-vehicle communications. Blockage probability according to vehicle density and speed is shown from the model. In [32], authors show design and implementation of a long-range and broadband aerial communication system with directional antennas (ACDA), which enables unmanned aerial vehicle (UAV) to extend communication range, increase throughput, and reduce interference. In the testbed, the ACDA achieves 48 Mbps throughput at a distance of 300 m and 2 Mbps at 5000 m, promising long-distance Wi-Fi aerial communication. Reference [33] proposes joint optimization to select relay and link to get around obstacle and reduce delivery latency in 60 GHz mmWave networks and develops a less complex algorithm by decomposing the problem into subproblems. In [34], research results on propagation characteristics for V2V channels, particularly shadowing effects induced by obstructing vehicles between transmitter (Tx) and receiver (Rx), are introduced. In [35], measurement campaign is conducted in the mmWave band for the 12 most common railway materials; influence of typical objects to the mmWave propagation channel is analyzed for railway scenarios with various configurations. Reference [36] proposes an IEEE 802.11ad-based radar for long-range radar (LRR) applications at the 60 GHz unlicensed band, which enables a joint waveform for automotive radar and mmWave vehicle-to-vehicle communications reusing hardware.


## 3. GiV2V Network Architecture

Figure1 depicts an architecture of GiV2V networks, in which vehicles deployed at an intersection form mmWave beams toward neighbor vehicles to exchange safety and infotainment data. Also, they can share own storage or processing power to maintain floating data and process those data. For instance, video clips captured in the intersection area are held and analyzed by vehicles or road side units (RSUs) for object or event detection [37]. In order to query and deliver the floating data in this vehicular cloud, the Information Centric Networking (ICN) mechanism can be used [37–39].Figure 1
GiV2V network architecture.Due to road structure, neighbor vehicles are located on limited positions, which are mostly front, back, and side directions as shown in Figure2. First, a simple convoy model of Figure 2(a) is a typical traffic pattern at roads and appropriate to create a vehicle flow (i.e., vehicle train) for autonomous driving of smart cars. In this model, transmission direction is also limited, forward or backward, which can cause considerable interference among vehicles without transmission power control. However, de- and acceleration of vehicle speed lead to varying distance between vehicles, so the power control probably makes vehicle connectivity unstable. Second, a vehicle searches vehicles in next lanes with side beams to couple partitioned networks along the lanes as shown in Figure 2(b). This scenario can cause more interference than the convoy model due to small lane width. The beam directions are more various according to road shapes (e.g., curve and intersection), road width (e.g., multilane highway), and vehicle speed. Accordingly, vehicles can be located on front side or rear side in next lanes as shown in Figure 2(c). Such diagonal beams diverse beam directions like a random topology that has lower interference than a grid topology of Figures 2(a) and 2(b). However, the grid topology has advantages in connection establishment with small efforts to sweep beam directions compared to the random topology. As a consequence, most of the beams in GiV2V communications belong to scenarios in Figure 2, and considerable interference can exist due to limited beam directions.Figure 2
GiV2V topology and beam pattern at road.
(a)
Front-rear beam (b)
Side beam (c)
Front-rear side beam


## 4. Directional Antenna

### 4.1. Directivity Model

In this paper, a beamforming model is expressed by a sectorized directional antenna following ITU-R reference [40] that covers 400 to 70 GHz spectrum as below. The radiation intensity at azimuthal F(ϕ) and elevation plane F(θ) is modelled by two different radiation intensity functions: rectangular and exponential sectoral radiation.Directivity of omnidirectional and sectoral antennas is(1)D=UMU0,where D is directivity (i.e., gain) and U0 is radiation intensity of an isotropic source.(2)Pt=∫02π∫0πFθFϕsin⁡θdθdϕ,then the omnidirectional power is U0=1/4πPt.Here those two different radiation intensity functions in the azimuthal plane can be considered while the elevation plane is assumed to be an exponential function. In rectangular sectoral radiation, the azimuthal power intensity is derived as(3)Fϕ=0ifϕs2-ϕ≥01ifϕs2-ϕ<0And elevation power is(4)Fθ=e-aθ2,a=-ln⁡0.54θbw,where θbw is beamwidth.Accordingly, the omnidirectional intensity is calculated approximately as(5)U0=ϕsθbw4ππ2.773e-θ2/11.09The directivityDr of the rectangular radiation model is(6)Dr=38750ϕsθbweθbw2/36400,when UM is 1.In the exponential function for sectoral radiation, the azimuthal functionF(ϕ) is replaced by the following exponential function:(7)Fϕ=ebϕ2,b=ln⁡0.54ϕs2Here the gainDe of the exponential radiation model is(8)De=36400ϕsθbweθbw2/36400Side lobes are smaller than the main lobes with the front-to-back ratio (FBR) (i.e., ratio of front-side lobes) denoted byγ (0 <γ≤ 1, 1 for omnidirection). Accordingly, the gains of a main lobe and side lobes are Gm=(1-γ)D(θbw) and γGm, respectively. Table 1 shows gains of main and side lobes with varying γ values.Table 1
Gain of main and side lobes.
Directivity (Gain) γ=0.2 γ=0.5 γ=0.7 90 5.613824327 1.122765 2.806912 3.929677  60 8.42073649 1.684147 4.210368 5.894516  45 11.22764865 2.24553 5.613824 7.859354  30 16.84147298 3.368295 8.420736 11.78903  15 33.68294596 6.736589 16.84147 23.57806  10 50.52441894 10.10488 25.26221 35.36709For our experiment that appeared in Section7, 30, 60, and 90 degrees of beam width are used; the directivity antenna gains are 16.8, 8.4, and 5.6 dBi, respectively. While the widths of those beams are in a linear scale, gains increase exponentially as shown in Figure 3.Figure 3
Directivity (gain) of rectangular and exponential radiation models.


### 4.2. Coverage in GiV2V Networks

Figure4 shows an example of communication range in GiV2V networks. The coverage is varying according to beam directions of neighbor vehicles in contrast to a coverage using omnidirectional antenna. In the figure, 10 vehicles exit near the transmitter Vt but only 4 vehicles, from Vr1 to Vr4, have connection to the transmitter. Supposing that the transmitter vehicle, Vt, forms a beam shadowed among 4 sectors (i.e., 90 degrees), the receiver vehicle Vr1 located on the transmission sector is reachable even with its different beam direction in the d2 coverage. However, other Vr2 and Vr3 that are not on the first quarter sector but within the d2 must create beams toward the transmitter Vt for connections. In the d3 coverage, only the Vr4 has a connection to the Vt since both the transmitter and receiver have to beam to each other.Figure 4
Varying coverages in GiV2V networks.Table2 describes beamforming gain and corresponding reachable radio ranges. When antenna gain from bore sight of a main lobe is denoted as G and gain from other directions is g as a side lobe, vehicles in d3 should have beamforming to each other and in d2, one of a sender and receiver has to make a beam to a peer node at least.Table 2
Beam direction and radio range.
Gain Range GtGr d3  Gtgr d2  gtGr d2  gtgr d1


## 4.1. Directivity Model

In this paper, a beamforming model is expressed by a sectorized directional antenna following ITU-R reference [40] that covers 400 to 70 GHz spectrum as below. The radiation intensity at azimuthal F(ϕ) and elevation plane F(θ) is modelled by two different radiation intensity functions: rectangular and exponential sectoral radiation.Directivity of omnidirectional and sectoral antennas is(1)D=UMU0,where D is directivity (i.e., gain) and U0 is radiation intensity of an isotropic source.(2)Pt=∫02π∫0πFθFϕsin⁡θdθdϕ,then the omnidirectional power is U0=1/4πPt.Here those two different radiation intensity functions in the azimuthal plane can be considered while the elevation plane is assumed to be an exponential function. In rectangular sectoral radiation, the azimuthal power intensity is derived as(3)Fϕ=0ifϕs2-ϕ≥01ifϕs2-ϕ<0And elevation power is(4)Fθ=e-aθ2,a=-ln⁡0.54θbw,where θbw is beamwidth.Accordingly, the omnidirectional intensity is calculated approximately as(5)U0=ϕsθbw4ππ2.773e-θ2/11.09The directivityDr of the rectangular radiation model is(6)Dr=38750ϕsθbweθbw2/36400,when UM is 1.In the exponential function for sectoral radiation, the azimuthal functionF(ϕ) is replaced by the following exponential function:(7)Fϕ=ebϕ2,b=ln⁡0.54ϕs2Here the gainDe of the exponential radiation model is(8)De=36400ϕsθbweθbw2/36400Side lobes are smaller than the main lobes with the front-to-back ratio (FBR) (i.e., ratio of front-side lobes) denoted byγ (0 <γ≤ 1, 1 for omnidirection). Accordingly, the gains of a main lobe and side lobes are Gm=(1-γ)D(θbw) and γGm, respectively. Table 1 shows gains of main and side lobes with varying γ values.Table 1
Gain of main and side lobes.
Directivity (Gain) γ=0.2 γ=0.5 γ=0.7 90 5.613824327 1.122765 2.806912 3.929677  60 8.42073649 1.684147 4.210368 5.894516  45 11.22764865 2.24553 5.613824 7.859354  30 16.84147298 3.368295 8.420736 11.78903  15 33.68294596 6.736589 16.84147 23.57806  10 50.52441894 10.10488 25.26221 35.36709For our experiment that appeared in Section7, 30, 60, and 90 degrees of beam width are used; the directivity antenna gains are 16.8, 8.4, and 5.6 dBi, respectively. While the widths of those beams are in a linear scale, gains increase exponentially as shown in Figure 3.Figure 3
Directivity (gain) of rectangular and exponential radiation models.


## 4.2. Coverage in GiV2V Networks

Figure4 shows an example of communication range in GiV2V networks. The coverage is varying according to beam directions of neighbor vehicles in contrast to a coverage using omnidirectional antenna. In the figure, 10 vehicles exit near the transmitter Vt but only 4 vehicles, from Vr1 to Vr4, have connection to the transmitter. Supposing that the transmitter vehicle, Vt, forms a beam shadowed among 4 sectors (i.e., 90 degrees), the receiver vehicle Vr1 located on the transmission sector is reachable even with its different beam direction in the d2 coverage. However, other Vr2 and Vr3 that are not on the first quarter sector but within the d2 must create beams toward the transmitter Vt for connections. In the d3 coverage, only the Vr4 has a connection to the Vt since both the transmitter and receiver have to beam to each other.Figure 4
Varying coverages in GiV2V networks.Table2 describes beamforming gain and corresponding reachable radio ranges. When antenna gain from bore sight of a main lobe is denoted as G and gain from other directions is g as a side lobe, vehicles in d3 should have beamforming to each other and in d2, one of a sender and receiver has to make a beam to a peer node at least.Table 2
Beam direction and radio range.
Gain Range GtGr d3  Gtgr d2  gtGr d2  gtgr d1


## 5. mmWave Channel Propagation Model

The mmWave pathloss model at 60 GHz was established for LoS environment based on measurement study [41].(9)LddB=A+20log10⁡fMHz+10αlog10⁡d,where the A is 32.5 dB and no shadow factor. d is a distance between a transmitter and receiver (km) and α is a pathloss exponent of LoS (e.g., 2).In outdoor GiV2V communication, additional attenuation from vapour water (Lvap), oxygen (LO2), and rain (LR) is considered as below. Total pathloss can be PL(d)=L(f,d)+La.(10)LadB=dLvap+LO2+LR.Those atmosphere parameters (dB/km) for further loss are assumed constant for relatively short communication period in this study [42, 43]. From simplicity of the constant La during the short communication period, the path loss is only determined by the distance, d, at a given operational frequency, f (e.g., 60 GHz).(11)Pr=Pt-PLd-NF+GR+GT-IL-CB,where Pr and Pt are transmission and receive power and NF and Nth are noise floor and thermal noise. Maximum antenna gain, GT, GR of a transmitter T and receiver R is assumed to be the same (i.e., same antenna array). IL is implementation loss like from cables CB.In the LoS environment, the radio range can be derived by the following outage probability with a required SNR of a target Modulation Coding Scheme (MCS).(12)PPr≥T=PPLd≤Pt+GR+GT-T-Gn,where PL(d) is pathloss of distance d, T is sensitivity for the required MCS level, and Gn = NF+IL+CB. For instance, minimum T is -78 or -68 dBm for control signals and data with lowest MCS, π/2-BPSK, respectively.In the above equation, maximum coveraged can be calculated by PL-1(Pt+GR+GT-T-Gn). Accordingly, the effective range is decided by only antenna gain of transmission and reception (i.e., beamforming factor) as shown in Table 2 while other parameters are assumed to be constant; in this study, no transmission power control is achieved between vehicles. From (12), maximum range, d, can be expressed as follows.(13)d=PtGRGTTGn1/αConsequently, the coverage is exponentially increasing with beamforming gain according to the (13).


## 6. Multichannel Beamforming for GiV2V Networks

The GiV2V enables multiple vehicles to create mmWave links to near vehicles with directional beams for concurrent Giga-bit communications. Those beams can be aligned or diversified according to network topologies and interference also occurs by the beam patterns.Figure5(a) illustrates an example of interfering 3 pairs of communication vehicles with directional beams, where each vertex indicates a vehicle node, sender Sn, and receiver Rn, and receive interference is different to each pair because of adjacent beam directions; R2 receives interference from both transmitters S1 and S3 denoted as dashed lines, while R3 has interference only from S2 and there is no interference for R1. The interference among nodes can be expressed by a directed graph as in Figure 5(b) in which each vertex indicates a pair of communication nodes, i.e., a link or beam.Figure 5
GiV2V topology and interference.
(a)
Network topology (b)
Interference relationIn the interference graph of the GiV2V networks, multiple channels can be assigned to the vertices for collision and interference avoidance. For example, only 2 channels can remove the mutual interference completely in Figure5(b): CH1 for vertexes 1 and 3 and CH2 for vertex 2. This channel assignment for each communication pair is a coloring problem of the interference graph, which is a combinatorial problem known as a NP-Hard. Accordingly, we propose several algorithms that can be realized in centralized or distributed manners and compare their performance through simulation.


### 6.1. System Model

We build a system model to design and analyze our algorithms. We define variables according to the directed interference graph in Figure5(b). Each communication link is denoted as a vertex and directional interference as an edge; there are i vertices and ij directional edges. Symbols of the our system model are described in Table 3.Table 3
System model parameters.
Symbol Description N A set of communication links C A set of available channels G Directional antenna gain P Power of transmission B Bandwidth ri Data rate at linki L Path loss d Distance between vehiclesThe channel assignment for each linki∈N can be expressed by xic. If the link i is tuned to the channel c,(14)xic=1,ionc0,otherwise.Data rate of a communication link,i, on a channel c, ric, can be calculated approximately by Shannon and Friis transmission equation as follows:(15)ric=Bclog2⁡1+PiGiΛLixicσ2+∑j:j∈HiPkGjΛLjxjc,where Λ = (λ/4π)2 and Li=diα. The α is an exponent for free-space pathloss and d is distance of a communication link or an edge of Figure 5(b). Other parameters are denoted in Table 3. Afterwards the distance term is only used for the interference edge rather than the other. Hi is a hyperarc that consists of set of incoming edges at the vertex i in the interference graph. For an example of Figure 5(b), H1=, H2={1,3}, and H3={2}. System bandwidth Bc can be 2.1 GHz for each channel according to IEEE 802.11ad.In this study, our objective is maximizing sum of utility of each communication link.(16)max⁡∑iUricThe utility functionU is defined as follows.(17)Uric=γ+κ∑i∈N∑c∈Cxicric,where γ is minimum data rate for a pair of communication nodes on a channel c and κ is a small value like 1e-3 for max-min fairness among links [43].


### 6.2. Random Channel Assignment

Each link is the same as a vertex. To clarify, each link (a vertex in the interference graph) chooses a channel randomly in a distributed manner, which is mostly simple and powerful compared to complicated channel assignment algorithms. In addition, vehicle nodes can use position information (i.e., GPS) for random seeds to diversify channel selection within an interference region.


### 6.3. Distributed Channel Assignment

As the same distributed approach, neighboring nodes can exchange channel selection information to avoid collisions rather than the random selection, which enables nodes to select a minimum used channel within interference region. In this section, we introduce a simple Distributed Channel Assignment (DCA) algorithm.The achievable rate of each link is varying by the channel assignment in the system model, which is intractable. Accordingly, the objective is redefined as a local general assignment problem to minimize maximum aggregated gain within interference region from (15). For the simplicity, fixed transmission power and constant parameters are omitted. This local solution from the redefined problem does not guarantee to find a global optimum, but it is valuable for notable throughput and easily realized in the distributed architecture.(18)minimizemaxc⁡∑i∈Hwixic(19)subjecttowi=Gidi-α(20)∑c∈Cxic=1,i∈N(21)xic∈0,1,i∈N,c∈C,where the interference weight wi is decided by distance to an interferer and beam direction. The hyperarch H is one of interference regions in a whole network. Equation (18) can be reformulated into an equivalent epigraph form and solved by Lagrangian relaxation as follows.(22)minimizet(23)subjectto∑i∈Hwixic≤t(24)Eq.20-21Partial Lagrangian can be derived for relaxation by dualizing first constraint (23),(25)Lt,x,λ=t+∑c∈Cλc∑i∈Hwixic-t=t1-∑c∈Cλc+∑i∈H∑c∈Cλcwixic,where λ is nonnegative Lagrange multiplier for the first inequality constraint (23). Accordingly, we can have a dual function g(λ)=L(t,x,λ) by minimizing above partial Lagrangian with regard of x and t, where the dual function can have -∞ by t if ∑c∈Cλc≠1. Therefore, we can redefine the dual function with constraint for λ.(26)maximizegλ(27)subjectto∑c∈Cλc=1(28)λc≥0In this dual problem, the analytical solution for the combinatorial problem can be derived in a closed form expression. For optimalx∗,(29)xic∗=1,c=c∗0,otherwise,where the optimal channel (c∗=arg⁡minc⁡λcwi) from (25) can be easily found, which is one minimizing sum of weight within the interference range by choosing minimum prices, λ. Accordingly, the derivation of the x only takes O(N) linear time.The dual function is convex although it is not differentiable. Therefore optimalλ value in (26) can be acquired using a subgradient method. A following projected subgradient method updates the λ value by given channel allocation, x, with which the algorithm newly assigns channels to nodes to converge into an optimum.(30)λct+1=λct+αt∑i∈Hwixic∗,where t indicates an algorithm iteration and αt is a tth step size (αt>0).Above the closed form solution can be realized in distributed manner as shown in Algorithm1.Algorithm 1:Distributed channel selection algorithm.
1:procedure  VehicleChannelSelectFunc 2:Initialization: λc(t) for all c, and estimate wi 3:loop: 4:Select c←arg⁡minc⁡λcwi according to Eq.(29) 5:Broadcast the selected channel c, xic 6:Update λc(t+1) according to Eq.(30). 7:if  λc(t)=λc(t+1)then 8:stop; 9:Broadcast λc(t) 10:goto  loop.


### 6.4. Interference-Aware Channel Assignment

In contrast to the local solution introduced in Algorithm1, we propose a greedy SINR-based Channel Assignment (SCA) algorithm in a centralized architecture, where vehicles report chosen channels to a controller and then the controller calculates optimal allocation for the objective. As shown in (17) and (18), our objective is minimizing maximum aggregated interference. Thus, the controller chooses a link with maximum aggregated interference and assigns a separate channel first as a greedy manner. Algorithm 2 explains a procedure of the algorithm to assign a channel to each link based on degree of interference. First, the algorithm selects a pair of vehicles that suffer from highest interference and assigns a channel that brings maximum throughput enhancement in overall networks. The algorithm continues until no more link can have gain after changing own channel.Algorithm 2:Greedy channel selection algorithm.
1:procedure  ControllerGreedyScheduleFunc 2:Initialization: c=1 and xi1=1 3:Receive ∑j∈Hiwj from i 4:MAX = ∑i∑j∈Hiwj 5:loop: 6:i←arg⁡maxi⁡∑j∈Hiwj 7:c∗←arg⁡minc⁡∑j∈Hiwjxjc 8:if  MAX >∑i∑j∈Hiwi) then 9:Update c=c∗, xec=0 and xec∗=1 10:MAX = ∑i∑j∈Hiwj) 11:goto  loop. 12:else 13:stop;


### 6.5. Hybrid Channel Assignment

Previously proposed SCA algorithm assumes no initial channel distribution; all vehicles have the same channel (e.g., channel 1) at the beginning. However, it is not realistic and able to lead the algorithm to reach local maxima. Therefore, we propose an initialized SCA (InitSCA) algorithm as a hybrid approach that utilizes the DCA and SCA in sequence; the DCA allows vehicles to find a local optimum and then a controller of the SCA adjusts channel allocation based on SINR of each pair of communication vehicles to enhance total network throughput.


## 6.1. System Model

We build a system model to design and analyze our algorithms. We define variables according to the directed interference graph in Figure5(b). Each communication link is denoted as a vertex and directional interference as an edge; there are i vertices and ij directional edges. Symbols of the our system model are described in Table 3.Table 3
System model parameters.
Symbol Description N A set of communication links C A set of available channels G Directional antenna gain P Power of transmission B Bandwidth ri Data rate at linki L Path loss d Distance between vehiclesThe channel assignment for each linki∈N can be expressed by xic. If the link i is tuned to the channel c,(14)xic=1,ionc0,otherwise.Data rate of a communication link,i, on a channel c, ric, can be calculated approximately by Shannon and Friis transmission equation as follows:(15)ric=Bclog2⁡1+PiGiΛLixicσ2+∑j:j∈HiPkGjΛLjxjc,where Λ = (λ/4π)2 and Li=diα. The α is an exponent for free-space pathloss and d is distance of a communication link or an edge of Figure 5(b). Other parameters are denoted in Table 3. Afterwards the distance term is only used for the interference edge rather than the other. Hi is a hyperarc that consists of set of incoming edges at the vertex i in the interference graph. For an example of Figure 5(b), H1=, H2={1,3}, and H3={2}. System bandwidth Bc can be 2.1 GHz for each channel according to IEEE 802.11ad.In this study, our objective is maximizing sum of utility of each communication link.(16)max⁡∑iUricThe utility functionU is defined as follows.(17)Uric=γ+κ∑i∈N∑c∈Cxicric,where γ is minimum data rate for a pair of communication nodes on a channel c and κ is a small value like 1e-3 for max-min fairness among links [43].


## 6.2. Random Channel Assignment

Each link is the same as a vertex. To clarify, each link (a vertex in the interference graph) chooses a channel randomly in a distributed manner, which is mostly simple and powerful compared to complicated channel assignment algorithms. In addition, vehicle nodes can use position information (i.e., GPS) for random seeds to diversify channel selection within an interference region.


## 6.3. Distributed Channel Assignment

As the same distributed approach, neighboring nodes can exchange channel selection information to avoid collisions rather than the random selection, which enables nodes to select a minimum used channel within interference region. In this section, we introduce a simple Distributed Channel Assignment (DCA) algorithm.The achievable rate of each link is varying by the channel assignment in the system model, which is intractable. Accordingly, the objective is redefined as a local general assignment problem to minimize maximum aggregated gain within interference region from (15). For the simplicity, fixed transmission power and constant parameters are omitted. This local solution from the redefined problem does not guarantee to find a global optimum, but it is valuable for notable throughput and easily realized in the distributed architecture.(18)minimizemaxc⁡∑i∈Hwixic(19)subjecttowi=Gidi-α(20)∑c∈Cxic=1,i∈N(21)xic∈0,1,i∈N,c∈C,where the interference weight wi is decided by distance to an interferer and beam direction. The hyperarch H is one of interference regions in a whole network. Equation (18) can be reformulated into an equivalent epigraph form and solved by Lagrangian relaxation as follows.(22)minimizet(23)subjectto∑i∈Hwixic≤t(24)Eq.20-21Partial Lagrangian can be derived for relaxation by dualizing first constraint (23),(25)Lt,x,λ=t+∑c∈Cλc∑i∈Hwixic-t=t1-∑c∈Cλc+∑i∈H∑c∈Cλcwixic,where λ is nonnegative Lagrange multiplier for the first inequality constraint (23). Accordingly, we can have a dual function g(λ)=L(t,x,λ) by minimizing above partial Lagrangian with regard of x and t, where the dual function can have -∞ by t if ∑c∈Cλc≠1. Therefore, we can redefine the dual function with constraint for λ.(26)maximizegλ(27)subjectto∑c∈Cλc=1(28)λc≥0In this dual problem, the analytical solution for the combinatorial problem can be derived in a closed form expression. For optimalx∗,(29)xic∗=1,c=c∗0,otherwise,where the optimal channel (c∗=arg⁡minc⁡λcwi) from (25) can be easily found, which is one minimizing sum of weight within the interference range by choosing minimum prices, λ. Accordingly, the derivation of the x only takes O(N) linear time.The dual function is convex although it is not differentiable. Therefore optimalλ value in (26) can be acquired using a subgradient method. A following projected subgradient method updates the λ value by given channel allocation, x, with which the algorithm newly assigns channels to nodes to converge into an optimum.(30)λct+1=λct+αt∑i∈Hwixic∗,where t indicates an algorithm iteration and αt is a tth step size (αt>0).Above the closed form solution can be realized in distributed manner as shown in Algorithm1.Algorithm 1:Distributed channel selection algorithm.
1:procedure  VehicleChannelSelectFunc 2:Initialization: λc(t) for all c, and estimate wi 3:loop: 4:Select c←arg⁡minc⁡λcwi according to Eq.(29) 5:Broadcast the selected channel c, xic 6:Update λc(t+1) according to Eq.(30). 7:if  λc(t)=λc(t+1)then 8:stop; 9:Broadcast λc(t) 10:goto  loop.


## 6.4. Interference-Aware Channel Assignment

In contrast to the local solution introduced in Algorithm1, we propose a greedy SINR-based Channel Assignment (SCA) algorithm in a centralized architecture, where vehicles report chosen channels to a controller and then the controller calculates optimal allocation for the objective. As shown in (17) and (18), our objective is minimizing maximum aggregated interference. Thus, the controller chooses a link with maximum aggregated interference and assigns a separate channel first as a greedy manner. Algorithm 2 explains a procedure of the algorithm to assign a channel to each link based on degree of interference. First, the algorithm selects a pair of vehicles that suffer from highest interference and assigns a channel that brings maximum throughput enhancement in overall networks. The algorithm continues until no more link can have gain after changing own channel.Algorithm 2:Greedy channel selection algorithm.
1:procedure  ControllerGreedyScheduleFunc 2:Initialization: c=1 and xi1=1 3:Receive ∑j∈Hiwj from i 4:MAX = ∑i∑j∈Hiwj 5:loop: 6:i←arg⁡maxi⁡∑j∈Hiwj 7:c∗←arg⁡minc⁡∑j∈Hiwjxjc 8:if  MAX >∑i∑j∈Hiwi) then 9:Update c=c∗, xec=0 and xec∗=1 10:MAX = ∑i∑j∈Hiwj) 11:goto  loop. 12:else 13:stop;


## 6.5. Hybrid Channel Assignment

Previously proposed SCA algorithm assumes no initial channel distribution; all vehicles have the same channel (e.g., channel 1) at the beginning. However, it is not realistic and able to lead the algorithm to reach local maxima. Therefore, we propose an initialized SCA (InitSCA) algorithm as a hybrid approach that utilizes the DCA and SCA in sequence; the DCA allows vehicles to find a local optimum and then a controller of the SCA adjusts channel allocation based on SINR of each pair of communication vehicles to enhance total network throughput.


## 7. Experiments

In this section, we evaluate channel allocation algorithms introduced in Section6 using simulations. In GiV2V networks, vehicles communicate with one-hop neighbors regardless of a final destination at a certain time. Previous studies about a directional MAC show that a HoL problem can be solved by a neighbor location table and scheduling order [9, 44]. From this, we assume that a vehicle has a communication peer nearby and establish a beam toward the peer node.We consider an exemplary scenario at highway that has a simple vehicle traffic pattern with varying vehicle densities and uses wireless local area (WLAN) networking for V2V communications. This GiV2V network topology at the highway follows 2D-PPP that is shown similar with a PPP model along multiple lanes in terms of average throughput [45]. For simulation parameters, the highway space is 20 x 400 m and vehicle density is varying from 3 to 11e-3. Transmission power of each node is configured as 20 dBm in the WLAN and the channel model is applied as shown in Section 5.Average distanceE(D) between vehicles can be derived by the PPP model as follows. 2D-Poisson distribution with density λ is(31)PΦA=n=e-λAλAnn! Then the CCDF of the distance of the nearest point of the process is the same as probability of empty set in circle area of a radius, r, P(Φ(πr2)=0).(32)PD>r=e-λπr2Hence average distance can be calculated as(33)ED=∫0∞frrdr=12λ,where the PDF f(r) of the nearest point is given from the CCDF as below.(34)fr=2πrλe-λπr2Figure6 shows the average distance with varying vehicle density. Density 3e-3 shows average 9 m distance to the nearest node while density 11e-3 shows less than 5 m. According to this average distance, SNR of a link to the nearest node is plotted in Figure 7 based on the channel model discussed in Section 5. The SNR increases as the vehicle density grows because path loss reduces by decreasing link distance to a neighbor node. Furthermore, the SNR is varying by directivity gain as shown in Figure 3 (also refer to Table 1). The SNR increases as the number of sectors decreases; in 4 sectors, the SNR is around 6 dB while it is much higher in 6 and 12 sectors, about 10 and 27 dB, respectively, in Figure 7. Also, beam alignment affects the SNR; in particular, a narrower beam causes more difference in SNR. For instance, there is only a 4 dB gap between Gg and gg in 4 sectors, but 15 dB in 12 sectors (beam alignments Gg and gg described at Table 2). In this study, the Gg or gg case is only for interference since we assume that all communication pairs tune to each other. Here we can conclude that the GiV2V can suffer from higher interference by the aligned network topologies, in which a node can receive GG interference in addition to the Gg and gg.Figure 6
Average distance by vehicle density.Figure 7
Average SNR of the shortest GiV2V link.
(a)
4 sectors (b)
6 sectors (c)
12 sectors


### 7.1. Comparison of Proposed Algorithms

We compare our 4 channel assignment algorithms in a PPP highway model with varying density of vehicles. To obtain average throughput, total 200 runs with random topologies are conducted. Each vehicle chooses nearest another randomly as a receiver or relay and transmits data. Transmission power is 20 dBm, and topology change due to vehicle mobility is not considered.Figure8 shows average SINR of transmission links at different node densities when applying each algorithm with 3 channels. Performance shows a similar pattern regardless of number of sectors. The random allocation achieves the lowest throughput while the InitSCA mostly outperforms others. Noninitialized SCA (later called just SCA) and DCA approaches are comparable. In particular, the SCA shows better throughput in 12 sectors than the InitSCA because of increasing interference from narrow beams.Figure 8
Average SINR with 3 channels.
(a)
4 sectors (b)
6 sectors (c)
12 sectorsHere we observe that the node density and antenna directivity affect SINR with different degree of interference. For instance, node density 3e-3 has about 6 dB for SNR in Figure7(a) and 4 dB as SINR in Figure 8(a) with interference in case of the random assignment, while node density 11e-3 has almost 12 dB SNR but only 7 dB for SINR. In other words, the higher node density 11e-3 suffers more interference, 2 versus 5 dB reduction. For the directivity, Figure 7(c) shows more or less 30 dB SNR in node density 3e-3 and SINR of the same density is 20 dB in case of the random algorithm in Figure 8(c). Thus, almost 10 dB reduction occurs due to the interference in 12 sectors, which is much higher than the case of 4 sectors, 2 dB reduction because nodes can cause stronger interference and interference coverage expansion with high directivity. The interference becomes severe as the density increases; in 12 sectors, node density 11e-3 shows that 35 dB SNR is degraded to only 23 dB SINR in case of the random algorithm.Figure9 shows experiment results with 6 channels (e.g., IEEE 802.11ad channels), which allows more degree of freedom for interference avoidance. Compared to 3 channel results, low density allows comparable throughput among all algorithms because of orthogonality in space and channel divisions. However, as density grows, gaps among algorithms increase; the SCA achieves lower throughput than others including the random algorithm. From this, the SCA algorithm is assumed to stop at a local maximum while the random or DCA mechanism searches a solution closer to a global optimum. However, the SCA shows bit better performance in 12 sectors than the random and DCA distributed algorithms since the high interference avoidance may reduce overall average SINR.Figure 9
Average SINR with 6 channels.
(a)
4 sectors (b)
6 sectors (c)
12 sectorsFigures10 and 11 show standard deviation and 0 dB probability (i.e., a level of lowest MCS) of SINR of results in Figure 9. Standard deviation indicates difference of SINR among transmission links. Thus, the max-min-like SCA reduces the difference effectively because it assigns a channel first to a link that has worst SINR compared to others. The InitSCA shows lower deviation than the DCA by adjusting channel assignment for some links with low SINR. In low density, the deviation is affected mostly by length of each link while the deviation is determined by interference in high density. Figures 10(a) and 10(b) show that the deviation of the SCA and InitSCA is consistent or decreasing while the deviation of others increases; increasing interference from node density is effectively managed in case of the SCA and InitSCA compared to others. Furthermore, the probability that is less than 0-dB shows clearly max-min fairness achievement of the SCA in Figures 11(a) and 11(b). Similar with the deviation, the SCA has the lowest probability of 0-dB SINR among algorithms and shows robustness with increasing density. In 12 sectors, the 0-dB probability of the SCA is almost zero because of high spatial diversity; other algorithms’ probabilities are also quite lower than ones of 6 sectors. Note that the probability decreases as the density grows because of path loss reduction. As a result, multihop relays can be effective rather than direct communications in dense GiV2V networks.Figure 10
Standard deviation with 6 channels.
(a)
Deviation (dB) with 6 sectors (b)
Deviation (dB) with 12 sectorsFigure 11
Zero SINR probability with 6 channels.
(a)
SINR 0 dB probability with 6 sectors (b)
SINR 0 dB probability with 12 sectorsFigure12 depicts throughput with reduced transmission power, 10 dBm instead of 20 dBm. A total of 6 channels are assigned to nodes. Compared to results in Figure 9(a), SINR decreases, for an example of the 4 sectors, from 9 to 2 dB in high density due to Tx power reduction as shown in Figure 12(a). In low density, SINR shows less than 0 dB, i.e., -4 dB. Also, SINR difference among algorithms decreases, which implies that throughput difference from varying channel diversity gain becomes reduced as interference effect reduces. However, the throughput gap increases again as the interference increases due to high beam directivity in Figure 12(c). Transmission power control can reduce interference but together with receive signal strength that mainly affects the throughput rather than the interference that can be avoidable by spatial or channel diversity.Figure 12
Average SINR with Tx power, 10 dBm.
(a)
4 sectors (b)
6 sectors (c)
12 sectors


### 7.2. Comparison of Global Optimization Algorithms

According to experiment results in Section7.1, the InitSCA is the most effective algorithm among proposed algorithms across all densities and sectors. In this section, we compare the InitSCA performance with three well-known metaheuristic algorithms for seeking a global optimum, which are popularly used for large scale optimization and NP-Hard problems. For this comparison, we apply the same parameters used in the simulation of Section 7.1. Actual global optimum can be found by exhaustive search algorithms like brand and bound, but its average value (e.g., from 200 runs) requires much computation time due to the complexity of experiment scenario.Here we introduce briefly those three algorithms: Simulated Annealing (SA) [46], Generic Algorithm (GA) [47], and Particle Swarm Optimization (PSO) [48]. First, the SA follows a physical annealing analogy, in which heated particles in a liquid state are cooled down slowly to reach thermal equilibrium. In the algorithm, the particles are converged into lowest energy level by probability that moves to a new state, which decreases to zero along the cooling temperature. Here final energy level is determined by cooling speed; slow cooling leads to acquire a global optimum but delay might not be negligible for real-time systems. In our system, we limit number of iterations as 1e4. Second, the GA follows a process of natural DNA evolution, which is based on DNA operations such as mutation, crossover, and selection. Candidate solutions are evolved and selected by such bio-inspired operations until finding a global optimum. Third, PSO generates similarly swarm of particles as candidate random solutions, in which particles search for better solutions in the search space according to swarm’s best known position and find optima by updating generations. Compared to the GA, PSO is easy to implement with a few parameters to adjust for simple formulae.Figure13 shows average SINR of algorithms with varying channels and sectors. In all cases, PSO outperforms other algorithms, especially for 12 sectors. InitSCA is comparable with the GA or SA in case of 3 channels regardless of sectors. With 6 channels, the InitSCA shows slightly better throughput, about 1 dB than the GA and SA. Consequently, the GA and SA probably do not reach a global optimum although they are good solutions. Optimization of SA and GA such as cooling speed and crossover strategy in order to find the optimum is left for our future works.Figure 13
Average SINR of global optimization algorithms.
(a)
6 sectors and 3 channels (b)
12 sectors and 3 channels (c)
6 sectors and 6 channels (d)
12 sectors and 6 channelsMetaheuristic algorithms require conventionally considerable search time which is inappropriate for real-time applications like wireless communications. In the GiV2V networks, channels should be reassigned according to topology change; the GiV2V can have a new topology in a couple of seconds considering vehicle speed. Time complexity of our algorithm is shown asO(n) in Section 6.5, but other metaheuristic algorithms have different complexity with a population size (refer to [49] for each complexity). Table 4 and Figure 14 show average elapsed time for the global algorithms at each node density. The initialized SCA takes only several ten milliseconds for all density cases, but SA and GA consume about 5 to 35 seconds; time increases drastically according to the node density. Due to this long delay, those two algorithms are hard to apply to the GiV2V networks. PSO delay, less than 2 seconds at highest density, seems competitive considering its performance shown in our simulation.Table 4
Elapsed time of global algorithms.
3e-3 5e-3 7e-3 9e-3 11e-3 InitSCA 0.006994 0.014559 0.024938 0.041612 0.067441  SA 4.525196 8.652447 14.37165 22.30713 32.49279  GA 1.811456 4.840629 13.46396 24.10401 37.83527  PSO 0.385824 0.625597 0.92461 1.237252 1.665746Figure 14
Average computation time of algorithms with increasing density (5λ from 3e-3 to 11e-3).


## 7.1. Comparison of Proposed Algorithms

We compare our 4 channel assignment algorithms in a PPP highway model with varying density of vehicles. To obtain average throughput, total 200 runs with random topologies are conducted. Each vehicle chooses nearest another randomly as a receiver or relay and transmits data. Transmission power is 20 dBm, and topology change due to vehicle mobility is not considered.Figure8 shows average SINR of transmission links at different node densities when applying each algorithm with 3 channels. Performance shows a similar pattern regardless of number of sectors. The random allocation achieves the lowest throughput while the InitSCA mostly outperforms others. Noninitialized SCA (later called just SCA) and DCA approaches are comparable. In particular, the SCA shows better throughput in 12 sectors than the InitSCA because of increasing interference from narrow beams.Figure 8
Average SINR with 3 channels.
(a)
4 sectors (b)
6 sectors (c)
12 sectorsHere we observe that the node density and antenna directivity affect SINR with different degree of interference. For instance, node density 3e-3 has about 6 dB for SNR in Figure7(a) and 4 dB as SINR in Figure 8(a) with interference in case of the random assignment, while node density 11e-3 has almost 12 dB SNR but only 7 dB for SINR. In other words, the higher node density 11e-3 suffers more interference, 2 versus 5 dB reduction. For the directivity, Figure 7(c) shows more or less 30 dB SNR in node density 3e-3 and SINR of the same density is 20 dB in case of the random algorithm in Figure 8(c). Thus, almost 10 dB reduction occurs due to the interference in 12 sectors, which is much higher than the case of 4 sectors, 2 dB reduction because nodes can cause stronger interference and interference coverage expansion with high directivity. The interference becomes severe as the density increases; in 12 sectors, node density 11e-3 shows that 35 dB SNR is degraded to only 23 dB SINR in case of the random algorithm.Figure9 shows experiment results with 6 channels (e.g., IEEE 802.11ad channels), which allows more degree of freedom for interference avoidance. Compared to 3 channel results, low density allows comparable throughput among all algorithms because of orthogonality in space and channel divisions. However, as density grows, gaps among algorithms increase; the SCA achieves lower throughput than others including the random algorithm. From this, the SCA algorithm is assumed to stop at a local maximum while the random or DCA mechanism searches a solution closer to a global optimum. However, the SCA shows bit better performance in 12 sectors than the random and DCA distributed algorithms since the high interference avoidance may reduce overall average SINR.Figure 9
Average SINR with 6 channels.
(a)
4 sectors (b)
6 sectors (c)
12 sectorsFigures10 and 11 show standard deviation and 0 dB probability (i.e., a level of lowest MCS) of SINR of results in Figure 9. Standard deviation indicates difference of SINR among transmission links. Thus, the max-min-like SCA reduces the difference effectively because it assigns a channel first to a link that has worst SINR compared to others. The InitSCA shows lower deviation than the DCA by adjusting channel assignment for some links with low SINR. In low density, the deviation is affected mostly by length of each link while the deviation is determined by interference in high density. Figures 10(a) and 10(b) show that the deviation of the SCA and InitSCA is consistent or decreasing while the deviation of others increases; increasing interference from node density is effectively managed in case of the SCA and InitSCA compared to others. Furthermore, the probability that is less than 0-dB shows clearly max-min fairness achievement of the SCA in Figures 11(a) and 11(b). Similar with the deviation, the SCA has the lowest probability of 0-dB SINR among algorithms and shows robustness with increasing density. In 12 sectors, the 0-dB probability of the SCA is almost zero because of high spatial diversity; other algorithms’ probabilities are also quite lower than ones of 6 sectors. Note that the probability decreases as the density grows because of path loss reduction. As a result, multihop relays can be effective rather than direct communications in dense GiV2V networks.Figure 10
Standard deviation with 6 channels.
(a)
Deviation (dB) with 6 sectors (b)
Deviation (dB) with 12 sectorsFigure 11
Zero SINR probability with 6 channels.
(a)
SINR 0 dB probability with 6 sectors (b)
SINR 0 dB probability with 12 sectorsFigure12 depicts throughput with reduced transmission power, 10 dBm instead of 20 dBm. A total of 6 channels are assigned to nodes. Compared to results in Figure 9(a), SINR decreases, for an example of the 4 sectors, from 9 to 2 dB in high density due to Tx power reduction as shown in Figure 12(a). In low density, SINR shows less than 0 dB, i.e., -4 dB. Also, SINR difference among algorithms decreases, which implies that throughput difference from varying channel diversity gain becomes reduced as interference effect reduces. However, the throughput gap increases again as the interference increases due to high beam directivity in Figure 12(c). Transmission power control can reduce interference but together with receive signal strength that mainly affects the throughput rather than the interference that can be avoidable by spatial or channel diversity.Figure 12
Average SINR with Tx power, 10 dBm.
(a)
4 sectors (b)
6 sectors (c)
12 sectors


## 7.2. Comparison of Global Optimization Algorithms

According to experiment results in Section7.1, the InitSCA is the most effective algorithm among proposed algorithms across all densities and sectors. In this section, we compare the InitSCA performance with three well-known metaheuristic algorithms for seeking a global optimum, which are popularly used for large scale optimization and NP-Hard problems. For this comparison, we apply the same parameters used in the simulation of Section 7.1. Actual global optimum can be found by exhaustive search algorithms like brand and bound, but its average value (e.g., from 200 runs) requires much computation time due to the complexity of experiment scenario.Here we introduce briefly those three algorithms: Simulated Annealing (SA) [46], Generic Algorithm (GA) [47], and Particle Swarm Optimization (PSO) [48]. First, the SA follows a physical annealing analogy, in which heated particles in a liquid state are cooled down slowly to reach thermal equilibrium. In the algorithm, the particles are converged into lowest energy level by probability that moves to a new state, which decreases to zero along the cooling temperature. Here final energy level is determined by cooling speed; slow cooling leads to acquire a global optimum but delay might not be negligible for real-time systems. In our system, we limit number of iterations as 1e4. Second, the GA follows a process of natural DNA evolution, which is based on DNA operations such as mutation, crossover, and selection. Candidate solutions are evolved and selected by such bio-inspired operations until finding a global optimum. Third, PSO generates similarly swarm of particles as candidate random solutions, in which particles search for better solutions in the search space according to swarm’s best known position and find optima by updating generations. Compared to the GA, PSO is easy to implement with a few parameters to adjust for simple formulae.Figure13 shows average SINR of algorithms with varying channels and sectors. In all cases, PSO outperforms other algorithms, especially for 12 sectors. InitSCA is comparable with the GA or SA in case of 3 channels regardless of sectors. With 6 channels, the InitSCA shows slightly better throughput, about 1 dB than the GA and SA. Consequently, the GA and SA probably do not reach a global optimum although they are good solutions. Optimization of SA and GA such as cooling speed and crossover strategy in order to find the optimum is left for our future works.Figure 13
Average SINR of global optimization algorithms.
(a)
6 sectors and 3 channels (b)
12 sectors and 3 channels (c)
6 sectors and 6 channels (d)
12 sectors and 6 channelsMetaheuristic algorithms require conventionally considerable search time which is inappropriate for real-time applications like wireless communications. In the GiV2V networks, channels should be reassigned according to topology change; the GiV2V can have a new topology in a couple of seconds considering vehicle speed. Time complexity of our algorithm is shown asO(n) in Section 6.5, but other metaheuristic algorithms have different complexity with a population size (refer to [49] for each complexity). Table 4 and Figure 14 show average elapsed time for the global algorithms at each node density. The initialized SCA takes only several ten milliseconds for all density cases, but SA and GA consume about 5 to 35 seconds; time increases drastically according to the node density. Due to this long delay, those two algorithms are hard to apply to the GiV2V networks. PSO delay, less than 2 seconds at highest density, seems competitive considering its performance shown in our simulation.Table 4
Elapsed time of global algorithms.
3e-3 5e-3 7e-3 9e-3 11e-3 InitSCA 0.006994 0.014559 0.024938 0.041612 0.067441  SA 4.525196 8.652447 14.37165 22.30713 32.49279  GA 1.811456 4.840629 13.46396 24.10401 37.83527  PSO 0.385824 0.625597 0.92461 1.237252 1.665746Figure 14
Average computation time of algorithms with increasing density (5λ from 3e-3 to 11e-3).


## 8. Conclusion

In this study, we propose a new VANET architecture, GiV2V, using mmWave spectrum and investigate its performance with simulation. Beamforming for mmWave links can increase receive signal quality and overcome high propagation loss of the mmWave. However, it can also cause higher interference in beam-aligned ad hoc networks, especially in high node density. In this study, we propose a simple distributed algorithm and centralized greedy algorithm based on SINR. Although the centralized algorithm outperforms distributed one, the distributed algorithm is still competitive at high degree of freedom from many channels and less complicated to implement. The centralized greedy algorithm shows comparable throughput with several metaheuristic algorithms while its complexity is lower and appropriate for real-time GiV2V systems. We will experiment further to evaluate the proposed algorithms under vehicle mobility simulation and look for optimum values using branch and bound algorithm to compare as future works.



---

*Source: 2753025-2018-07-17.xml*