Millimeter Wave V2V Communications: Distributed Association and Beam Alignment

I Introduction

The last few years have witnessed the advent of wireless communications deployed in the millimeter-wave (mmWave) band, as a means to circumvent the spectrum shortage needed to satisfy the stringent requirements of 5G networks . The large amount of free spectrum available in the 60 GHz band –with 14 GHz of unlicensed spectrum, roughly 15 times as much as all unlicensed Wi-Fi spectrum in lower bands– represents a new opportunity for future communications using channel bandwidths beyond 1 GHz, as evinced by several standards for wireless personal and local area networks (such as IEEE 802.15.3c and IEEE 802.11ad ). This stimulating substrate for high-rate communications is the reason why 5G standardization committees and working groups are actively investing enormous research efforts towards leveraging the inherent advantages of mmWave communications (i.e. improved interference handling by virtue of highly-directive antennas) in cellular scenarios with massive device connectivity.

Among all the above scenarios where mmWave bands have been addressed in the literature, vehicular communications have lately grasped considerable attention due to more wireless technologies being integrated into vehicles for applications related to safety and leisure (infotainment), among others . Although certain safety applications may not require high data rates to be captured by the sensors installed in the vehicle (e.g. blind spot warning), many other applications are foreseen to require vehicular connectivity with very high transmission rates predicted to surpass the 100 Mbps limit of for raw sensor data. For instance, radars designed to operate on the 77-81 GHz band have been shown to enhance certain functionalities of vehicles such as automatic cruise control, cross traffic alert and lane change warning , with operating data rates far beyond the 27 Mbps limit admitted by DSRC (the de facto standard for short-range vehicular communications ) or current 4G cellular communications. More advanced radar technologies such as those relying on laser technology (LIDAR) produce high-resolution maps that require even more demanding data rates (in the order of tens of Mbps, depending on the spatial resolution and scanning rate). Predictions for autonomous vehicles foresee up to 1 TB of generated data per driving hour, with rates achieving more than 750 Mbps , motivating further the adoption of mmWave vehicle-to-everything (V2X) communications in the automotive sector.

Unfortunately, the challenging radio conditions derived from the mobility of vehicles, their relatively high speed with respect to pedestrians, the dynamic topology of vehicular wireless networks and its higher likelihood to produce inter-vehicular line-of-sight blockage are factors that pose significant challenges to be dealt with . It has not been until recently when early findings on the propagation characteristics of mmWave vehicular communications and limited work thereafter highlighted this spectrum band as a promising enabler for high-bandwidth automotive sensing or beamforming in vehicle-to-infrastructure (V2I) communications . Interestingly, to the best of our knowledge the literature on mmWave vehicle-to-vehicle (V2V) communications is so far limited to , where the impact of directionality and blockage on the signal to interference plus noise ratio (SINR) are explored via simulations for unicast V2V transmissions over the 60 GHz band. However their solution is based on a static vehicle association and they do not study the delay and reliability performance associated to data traffic arrivals in the system.

This work can be framed within mmWave V2V communications under the scope of Ultra-Reliable, Low-Latency Communications (URLLC), which refer to transmission technologies allowing for stringently bounded end-to-end latencies within the order of milliseconds and packet error rates on the order of $10^{-5}$ to $10^{-9}$ . Such operational limits could correspond to critical safety information captured by vehicle sensors, likely to be shared among nearby cars for an enhanced reactivity of cars against unexpected eventualities in the road. In this context we face the challenge of guaranteeing stringent latency and reliability levels in a V2V communication scenario considering the dynamic topology entailed by the movement of vehicles. Our goal is to address this challenging problem through a cross-layer information aware (CSI+QSI) vehicle association and mmWave beamwidth optimization scheme, where CSI (Channel State Information) indicates the transmission opportunity and QSI (Queue State Information) reflects the traffic urgency. The proposed Radio Resource Management (RRM) scheme is comprehensive and considers aspects such as the directionality (steering) of the mmWave link, the effect of the selected beamwidths on the interference at the vehicular receivers, the blockage of intermediate vehicles, the throughput versus alignment delay trade-off, the vehicle density and the impact of the speed offset between vehicles on the beam coherence time.

From the algorithmic point of view we first define utility functions that capture all the above aspects, which lay the basis for a matching game to solve the association problem between transmitting and receiving vehicles in a distributed fashion. Beamwidth optimization, on the other hand, is addressed using Swarm Intelligence, a class of nature-inspired optimization algorithms that simulate the collective behavior observed in certain species so as to discover optimum regions within complex search spaces under a measure of global fitness . The performance of our proposed RRM scheme is analyzed and discussed over a comprehensive set of experiments, aimed not only at exploring the quantitative performance obtained under different setups and parameters of the underlying vehicular scenario, but also as a comparison with several baselines, such as minimum-distance matching and novel pairing schemes reported in .

The rest of this manuscript is structured as follows: in Section II we describe the overall system model of the vehicular setup under consideration, and formulate the optimization problem. Section III and subsections therein delve into the proposed resource allocation procedure, including the adopted techniques for vehicle pairing and beamwidth optimization. In Section IV we evaluate the performance of different configurations of the proposed solution under diverse settings of the considered vehicular scenario. Finally, Section V concludes the paper by identifying future research directions.

Notations: The main symbols used throughout the paper are summarized in Table I. Therein onwards the following notation applies: lowercase/uppercase symbols represent scalars, boldface symbols represent vectors and calligraphic uppercase symbols denote sets. The cardinality of a set is denoted by $|\cdot|$.

II System Model and Problem Statement

This section elaborates on the system model for mmWave V2V communications, introduces the main elements that govern the cross-layer RRM policy and formulates the optimization problem that models the allocation of resources, namely, V2V links and their corresponding transmitting and receiving beamwidths.

We consider a multiple lane highway road section where vehicles move at variable speeds in the same direction. Vehicles in the highway incorporate vehicular user equipments (vUEs), further separated into vehicular transmitters (vTx) and vehicular receivers (vRx), which communicate through V2V links established on mmWave frequency band operating under Time Division Duplexing (TDD). A co-channel deployment with bandwidth $B$, uniform transmit power and half-duplex mode are assumed. Let $\mathcal{I}\triangleq\{1,\ldots,I\}$, $\mathcal{J}\triangleq\{1,\ldots,J\}$ and $\mathcal{L}\triangleq\{1,\ldots,L\}$, with $\mathcal{I}\cap\mathcal{J}=\emptyset$, $\mathcal{|L|}\leq\min\{\mathcal{|I|},\mathcal{|J|}\}$ respectively denote the sets of vTx, vRx and links in the system.

In this scenario the relative movement between vehicles causes a varying network topology with changing channel conditions, misalignments between vehicle pairs and uncontrollable blocking effects in the deployed millimeter-wave links. This strong topological variability and the increased complexity of instantaneous, uncoordinated RRM policies impose the need for time-slotted communications, with two different time scales:

Data transmission slots (ms) denoting the intervals $[t,t+T_{t})$, with $T_{t}$ as the duration of the transmission period.

Scheduling slots (ms) which hereafter refers to the intervals $[t,t+T_{s})$, with $T_{s}$ representing the duration of the network-wide enforced control actions.

II-B Channel Modelling

II-C Antenna Pattern

As exemplified in Fig. 2(b) and Fig. 2(c), the likeliness of misalignment impacting on desired links due to a non-continuous steering/beamtracking mechanism may vary depending on several factors, such as the relative speed of the vehicles involved in the link, the width of the mainlobes of the transmitter and receiver antennas, or the length of the scheduling interval. Moreover, the selected beamwidths will impel whether signals from undesired V2V links arrive into the sidelobes or the mainlobe of vRxs, which will severely impact measured SINR levels. For this reason the sought RRM should also include a beamwidth selection strategy that dynamically adapts to the surrounding conditions and, counteracts their negative effect on the transmitted signal –which, in turn, comes along with an impact on the dynamics of the transmission queues–. The latter gains relevance in realistic scenarios, where the dynamics of the vehicle movement involve frequent misalignment events.

II-D Alignment Delay and Transmission Rate

Although numerous alternatives that speed up the beamforming protocol have been proposed in the literature, such as or more recently , a simplified version of the three-step beam codebook-based approach introduced by is employed due to its robustness and compliance with ongoing standards. Specifically, a two-staged beam alignment process will yield the best steering for the refined beams at both ends of the V2V link. These two stages encompass a sequence of pilot transmissions and use a trial-and-error approach where first a coarse sector-level scan detects best sectors for vTx and vRx and, afterwards, within the limits of the selected sector a finer granularity beam-level sweep searches for best beam-level pairs. In this approach the well-known alignment delay versus throughput trade-off is exposed: the selection of narrower beamwidths induces longer training overheads and yields reduced effective transmission rates.

Without loss of generality we assume here that for each vehicle in a V2V link before the beam-level alignment phase itself, either the sector level alignment has already been performed or that coarse location of neighboring vehicles has been learned (e.g. during the learning process in Section III-C), effectively reducing the beam search. By applying a continuous approximation , the alignment time penalty $\tau_{i,j}(t)$ can be quantified as

where $\psi_{i}^{t_{x}}$ and $\psi_{j}^{r_{x}}$ denote the sector-level beamwidths of vTx $i$ and vRx $j$, and $T_{p}$ denotes the pilot transmission duration. Constraints coming from the operational array antenna limits, sector level beamwidths and the fact that $\tau_{i,j}(t)$ should not exceed $T_{t}$ restrict the values taken by the vTx and vRx beamwidths $\varphi_{i,j}^{t_{x}}(t)$ and $\varphi_{i,j}^{r_{x}}(t)$, i.e.

Under these assumptions the maximum achievable data rate $r_{i,j}(t)$ between vTx $i$ and vRx $j$ will depend on whether beam alignment is performed at time slot $t$ with its corresponding induced delay and on the measured SINR at vRx $j$, including the interference of other incumbent vTxs on vRx $j$. The rate for a time slot $t$ of duration $T_{t}$ over which alignment is performed, is given by

where the SINR at time slot $t$ under $Z=|\mathcal{Z}|$ simultaneously transmitting vTxs is given by

II-E Queues and Delay Modeling

Upon its arrival to a certain queue, a packet will be either delivered or dropped within $D_{\max}^{\lambda}$ ms after entering the queue:

with $t_{i}^{p,arr}$, $t_{i,j}^{p,serv}$ respectively denoting the arrival time of packet $P_{i}^{p}$ at the queue and the time when the last of the bits of $P_{i}^{p}$ is transmitted to vRx $j$ i.e, $d_{i,j}^{p}$ is a joint measure of queue waiting time and transmission delayBy a slight abuse in the notation, we keep subindex $j$ in $t_{i,j}^{p,serv}$ and related delay statistics to explicitly refer to the dependence of such terms on the transmission rate $r_{i,j}(t)$ of the channel from vTx $i$ to its paired vRx $j$.. In general, the average delay per packet $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-0.5mu}\mkern 1.5mu_{i,j}(t)$ during transmission slot $t\in\mathcal{T}_{t}$ can be computed by averaging the delays $d_{i,j}^{p}$ of each packet successfully delivered over this link for the slot at hand, as

where $\mathcal{A}_{i}^{\checkmark}(t)$ denotes the subset of packets successfully sent towards vRx $j$ at time $t\in\mathcal{T}_{t}$. From this definition the average delay per delivered packet over the scheduling period $t_{s}\in\mathcal{T}_{s}$ will be given by

II-F Elements of RRM and Problem Statement

In order to formally define an RRM policy we let $\bm{\Phi}(t_{s})\triangleq\{\phi_{i,j}(t_{s}):i\in\mathcal{I}(t_{s}),\>j\in\mathcal{J}(t_{s})\}$ denote the set of all possible vTx/vRx mappings in the system in a given scheduling slot $t_{s}\in\mathcal{T}_{s}$. Note here that $\mathcal{I}(t_{s})$ (corr. $\mathcal{J}(t_{s})$) denotes the subset of vTx and vRx present on the road scenario at scheduling time $t_{s}$. We further define $\mathcal{I}_{j}(t_{s})\subseteq\mathcal{I}(t_{s})$ and $\mathcal{J}_{i}(t_{s})\subseteq\mathcal{J}(t_{s})$ as the subsets of feasible vTxs for vRx $j$ and the feasible vRxs for vTx $i$, where feasibility is due to a circular coverage constraint of radius $R_{c}$ (in meters). In this set $\phi_{i,j}(t_{s})$ will represent the association variable so that for the pair composed by vTx $i$ and vRx $j$

Bearing this in mind, $\bm{\Phi}(t_{s})$ jointly with a proper selection of the beamwidths at both vTx and vRx as defined by

if $t=t_{s}$ (i.e. the first transmission slot after scheduling at time $t_{s}\in\mathcal{T}_{s}$ has been enforced), while for $t\in[t_{s}+1,t_{s}+N)$,

Based on this rate and the traffic influx rate defined as $\rho=\lambda P_{s}$, a fraction of the packets generated at vTx $i$ will be transmitted towards vRx $j$, producing delays and packet dropping statistics over a given scheduling slot. For that reason a delay-sensitive RRM policy should take into account not only the finite delay of those packets successfully transmitted towards their destinations (for which queue dynamics are set to prioritize new incoming traffic), but also the interplay between delay and dropped packets enforced by the queuing policy.

The problem tackled in this work can be hence formulated as the design of the RRM policy $\{\bm{\Phi}(t_{s}),\bm{\varphi}^{t_{x}}(t_{s}),\bm{\varphi}^{r_{x}}(t_{s})\}$ for $t_{s}\in\mathcal{T}_{s}$ such that

where inequality (17b) indicates that no queue should overflow during the scheduling period at hand; Expressions (17c) through (17e) denote that vehicles are paired one-to-one; and inequalities (17f) through (17h) reflect the bounds imposed on the beamwidths to be allocated as per (4).

The above optimization problem is difficult to solve analytically and is computationally hard, especially in vehicular environments calling for low-complexity distributed solutions. For this reason we will decompose it into two problems: the vehicle pairing and the beamwidth optimization. Subsequently, tools from Matching Theory and from Swarm Intelligence are leveraged to account, respectively, for the optimization of $\bm{\Phi}(t_{s})$, and the selection of the beamwidths of both sides of each established mmWave V2V link (corr. $\bm{\varphi}^{t_{x}}(t_{s})$ and $\bm{\varphi}^{r_{x}}(t_{s})$). We will then explore the operational limits in terms of $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-0.5mu}\mkern 1.5mu_{i,j}^{sch}(t_{s})$ and $\Gamma^{\times}_{i}(t_{s})$ under different scheduling interval durations, traffic packet arrival rates and packet sizes. The ultimate goal of this study is to numerically assess the reliability of different RRM policies in mmWave V2V communications defined as the ratio of the number of packets $\Gamma_{i}^{\checkmark}(t_{s})\triangleq 1-\Gamma_{i}^{\times}(t_{s})$ of size $P_{s}$ successfully received at every receiver within a maximum delay $D_{max}^{\lambda}$.

III Proposed Scheme

Our objective in this work is to design a self-organizing mechanism to solve the vehicle-to-vehicle association problem, in a decentralized manner, in which vTxs and vRxs interact and decide to link to each other based on their utilities. To this end, Matching Theory , a Nobel Prize winning framework, offers a promising approach for resource management in wireless communications . As depicted schematically in Fig. 3, elements from Matching Theory are used for allocating mmWave V2V links in the setup at every scheduling slot $t_{s}$, with a previous learning process to capture essential information required for the matching game. Learning and matching are then followed by an optimization phase that allocates transmission and reception beamwidths for the matched pairs. Finally, beam alignment is performed. Prior to defining the matching game itself, we will first introduce the framework and specify the utility functions for both sets of agents, as well as the learning process upon which utilities will be computed.

In order to properly address the fundamentals of this mathematical framework, several definitions must be first done and particularized for the problem at hand:

A matching game is defined by two sets of players ($\mathcal{I}_{j}(t),\mathcal{J}_{i}(t)$) and two preference relations $\succ_{i}$, $\succ_{j}$, allowing each player $i\in{\mathcal{I}_{j}(t)}$, $j\in{\mathcal{J}_{i}(t)}$ to accordingly rank the players in the opposite set.

The output of a matching game is a matching function $\bm{\Phi}(t)=\{\phi_{i,j}(t)\}$ that bilaterally assigns players $\bm{\phi}_{i}(t)\triangleq\{j\in\mathcal{J}_{i}(t):\phi_{i,j}(t)=1\}$ and $\bm{\phi}_{j}(t)\triangleq\{i\in\mathcal{I}_{j}(t):\phi_{i,j}(t)=1\}$ such that $|\bm{\phi}_{j}(t)|=q_{j}$ and $|\bm{\phi}_{i}(t)|=q_{i}$ are fulfilled. Notice here that $q_{i}$ and $q_{j}$ represent the quota of the player which, for a one-to-one matching game, $q_{i}=q_{j}=1$.

A preference $\succ$ is a complete, reflexive and transitive binary relation between the players in $\mathcal{I}_{j}(t)$ and $\mathcal{J}_{i}(t)$. Therefore, for any vTx $i$ a preference relation $\succ_{i}$ is defined over the set of vRx $\mathcal{J}_{i}(t)$ such that for any two vRx $(m,n)\in\mathcal{J}_{i}(t)\times\mathcal{J}_{i}(t)$ with $m\neq n$, and two matchings $\bm{\Phi}(t)$ and $\bm{\Phi}^{\prime}(t)$ so that $\bm{\phi}_{i}(t)=m$ and $\bm{\phi}_{i}^{\prime}(t)=n$:

Similarly, for any vRx $j$ a preference relation $\succ_{j}$ is defined over the set of vTx $\mathcal{I}_{j}(t)$ such that for any two vTx $(k,l)\in\mathcal{I}_{j}(t)\times\mathcal{I}_{j}(t)$ with $k\neq l$, and two matchings $\bm{\Phi}(t)$ and $\bm{\Phi}^{\prime}(t)$ so that $\bm{\phi}_{j}(t)=k$ and $\bm{\phi}_{j}^{\prime}(t)=l$:

where $U_{vTx}^{i,m}(t)$ and $U_{vRx}^{k,j}(t)$ denote the utility of vRx $m$ for vTx $i$ and the utility of vTx $k$ for vRx $j$, correspondingly.

A matching is not stable if for a given match $\bm{\phi}_{i}(t)=j$ and $\bm{\phi}_{j}(t)=i$, a blocking pair $(i^{\prime},j^{\prime})$ such that $i,i^{\prime}\in\mathcal{I}_{j}(t)$ and $j,j^{\prime}\in\mathcal{J}_{i}(t)$ satisfying $\bm{\phi}_{i}(t)\neq j^{\prime}$, $\bm{\phi}_{j}(t)\neq i^{\prime}$ and $j^{\prime}\succ_{i}j$, $i^{\prime}\succ_{j}i$ exists. That is, if for a given match two players prefer to be matched to each other rather than to their current matched partners. A matching is considered pairwise stable if no such blocking pair exists.

From an algorithmic point of view, Gale-Shapley’s Deferred Acceptance algorithm (DA, ) provides a polynomial time converging solution for one-to-one canonical matchings i.e., those matching games where preferences of players are not influenced by any other player’s decisions. To this end DA employs an iterative process which finds a stable mapping from the elements of the set of transmitters in the system at every scheduling period to the elements of the set of feasible receivers. The process relies on the ordering of the preference list that each player on either side compiles over the players from the other set. Let us remark here that DA ensures pairwise stability (as per Definition 4), but is not necessarily optimal for all players in the game. The traditional form of the algorithm is optimal for the initiator of the proposals whereas the stable, suitor-optimal solution may or may not be optimal for their reviewers. Interestingly for the application tackled in this paper, DA does not require a centralized controller as the players involved do not need to observe the actions or preferences of other players.

Unfortunately, the existence of interdependencies between the players’ preferences (referred to as externalities) makes DA unsuitable as the ranking of preferences lying at its core dynamically changes as the matching evolves. Externalities also pose a great challenge to ensure stability in the matching.

III-B Utility Formulation

To produce the V2V link allocation that leads to minimum system-wide average delay, participants in the game – namely, vTxs and vRx in the vehicular scenario at a given scheduling slot – will determine the utilities perceived towards each other in such a way that this information is captured and used to identify the set of players that offer better delay profiles. The baseline for the formulation of utilities in both vTxs and vRxs will be the $\alpha$-fair utility function expressed, for $\alpha\geq 0$ and $x\in\{vTx,vRx\}$, as

where $\alpha=2$ guarantees a weighted minimum proportional delay fairness, and $\omega_{x}$ allows bringing problem-specific information into the utilities. At this point we recall that $\mathcal{J}_{i}(t_{s})$ and $\mathcal{I}_{j}(t_{s})$ denote the subsets of feasible vRxs for vTx $i$ and feasible vTxs for vRx $j$ at a given scheduling time $t_{s}\in\mathcal{T}_{s}$, respectively. With this notation in mind, we define the weighted $\alpha$-fair utility function for vTx $i\in\mathcal{I}(t_{s})$ over vRxs $\mathcal{J}_{i}(t)$ as

where we remark that for notational simplicity we will use $U_{vTx}^{i,j}\left(t_{s}\right)$ instead of $U_{vTx}^{i,j}\left(t_{s},\bm{\Phi}(t_{s})\right)$ even though the implicit dependence of the utility on $\bm{\Phi}(t_{s})$. Similarly, the utility of vRx $j\in\mathcal{J}(t_{s})$ over $I_{j}(t_{s})$ vTxs for a given matching $\bm{\Phi}(t_{s})$ will be given by

so that the system welfare $\mbox{S}(t_{s},\bm{\Phi}(t_{s}))$ to be maximized is

By including in the expressions of the above utilities –e.g. through weights $\omega_{vTx}^{i,j}(t_{s})$ and $\omega_{vRx}^{j,i}(t_{s})$– the traffic influx rate $\rho=\lambda P_{s}$, the nexus between above utility functions and the fitness in (17) is straightforward. As a result, the above formulated utility functions will reflect the load of the V2V link in terms of the number of transmission slots to serve $\lambda P_{s}$ bits with rate $r_{i,j}(t_{s},\bm{\Phi}(t_{s}))$. Therefore, the maximization of the system-wide welfare in turn minimizes the fitness in Expression (17a).

We finally define weights $\omega_{vTx}^{i,j}(t_{s})$ and $\omega_{vRx}^{j,i}(t_{s})$ so that under the same other conditions, vTxs are encouraged to select those vRxs moving along the highway at similar speeds –as that implies links being less prone to misalignment events– whereas vRxs will choose those vTxs with longer queues in order to alleviate the system. By denoting the relative speed of vTx $i$ and vRx $j$ averaged over the transmission slot $t_{s}\in\mathcal{T}_{s}$ as $\mkern 1.5mu\overline{\mkern-1.5mu\Delta v\mkern-0.5mu}\mkern 1.5mu_{i,j}(t_{s})$, and the status of queue $i$ at time $t_{s}$ as $Q_{i}(t_{s},\bm{\Phi}(t_{s}))$, the proposed weights for the above utility functions are expressed as

where $i\in\mathcal{I}(t_{s})$, $j\in\mathcal{J}(t_{s})$, and $|\mkern 1.5mu\overline{\mkern-1.5mu\Delta v\mkern-0.5mu}\mkern 1.5mu|_{\max}$ and $Q_{\Theta}$ represent normalization terms. In the utility (25) we extend the notation in (7) as ${Q}_{i}(t_{s},\bm{\Phi}(t_{s}))$ to denote the queue status at vTx $i$ and time $t_{s}$ when it is paired to vRx $j$ under matching $\bm{\Phi}(t_{s})$.

III-C CSI/QSI Information Learning Procedure

The evolution of the V2V system dynamics can be described by CSI and QSI as per (1) and (7), respectively. As the system evolves, V2V links should be dynamically enforced/released, beamwidths selected and beam steering triggered. However, CSI between devices and QSI at every vTx can only be measured locally and in a distributed fashion. In order to design a CSI/QSI aware long-term RRM policy and yet reduce the exchange of control information, vRxs will collect and process information on measured channel conditions for all transmission slots within a scheduling interval, and exchange it just before the beginning of a new scheduling period. This procedure also holds in the case of vTxs in regards to their QSI estimations.

Upon matching and beam alignment at scheduling slot $t_{s}-N$, we assume that every vehicle is able to detect and track vTxs and vRxs in its vicinity $\forall t^{\prime}\in(t_{s}-N,t_{s}]$, which can be done by resorting to standard techniques or more elaborated approaches as in . During every transmission interval within the scheduling period at hand, random matchings between vehicles in the vicinity of one another are agreed and set over a mmWave control channel deployed in parallel to the main communication beam. The purpose of this control channel is to allow sampling the CSI of every receiver $j\in\mathcal{J}_{i}(t_{s}-N)$ in the group when it receives information from a certain transmitter $i\in\mathcal{I}_{j}(t_{s}-N)$. This is accomplished by matching at random every single receiver in the system at time $t^{\prime}$ with any of the transmitters within its neighborhood. From a series of pilot transmissions in this random matching, every receiver $j\in\mathcal{J}(t_{s}-N)$ infers, based on the received power and by virtue of its knowledge of the relative position and transmit power of the transmitter $i$ to which it is paired and other vehicles nearby, the channel gain $g_{i,j}^{c}$ as per (1) and therefrom, an SINR estimation as per (6). Once this is done, the receiver stores the estimated SINR along with the time instant at which it was produced, and an identifier of the transmitter to whom it was linked to. This process is performed for every receiver in the system and over all transmission slots $t^{\prime}\in(t_{s}-N,t_{s}]$. As a result, all receivers at the end of the scheduling slot have stored a list with entries $\{t^{\prime},i,\mbox{SINR}_{j}(t^{\prime})\}$, with $\mbox{SINR}_{j}(t^{\prime})$.

To learn an estimate $\mkern 1.5mu\overline{\mkern-1.5mur\mkern-0.5mu}\mkern 1.5mu_{i,j}^{est}(t_{s})$ of the average rate that can be expected for the matched pair $(i,j)$ over the next scheduling period, we will inspect the behavior of this rate metric in the recent past (i.e. the previous scheduling period). Yet, instead of treating all samples equally, those more recent in time will be emphasized so as to lessen the impact of older ones . Based on this rationale, $\mkern 1.5mu\overline{\mkern-1.5mur\mkern-0.5mu}\mkern 1.5mu_{i,j}^{est}(t_{s})$ will be computed as

where for $\tau_{i,j}(t^{\prime})$ calculation, equal parameter values to those used for the main communication channel are adopted. Values for weights $W(t^{\prime},i)$ will be set such that $W(t^{\prime},i)\neq 0$ if and only if it exists an entry $\{t^{\prime},i,\mbox{SINR}_{j}(t^{\prime})\}$ in the CSI samples acquired by receiver $j$, $W(t^{\prime},i)\leq W(t^{\prime\prime},i)$ if $t^{\prime}\leq t^{\prime\prime}$ and imposing $\sum_{t^{\prime}\in(t_{s}-N,t_{s}]}W(t^{\prime},i)=1$ for any $i$ to which receiver $j$ may have been associated to all along the link exploration process in the previous scheduling period. Once rates $\mkern 1.5mu\overline{\mkern-1.5mur\mkern-0.5mu}\mkern 1.5mu_{i,j}^{est}(t_{s})$ have been estimated at receiver $j$ $\forall i\in\mathcal{I}_{j}(t_{s})$, their values are disseminated to its neighboring transmitters, which are now able to infer the average dynamics under which their queue can be flushed. Now that externalities have been removed from the estimated rates of the system, the average queue status at vTx $i$ when communicating to vRx $j$ is not subject to other matched pairs, and can be estimated as $\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-0.5mu}\mkern 1.5mu_{i,j}(t_{s})=P_{s}/\mkern 1.5mu\overline{\mkern-1.5mur\mkern-0.5mu}\mkern 1.5mu_{i,j}^{est}(t_{s})$. By inserting this estimated CSI/QSI information in Expressions (21) and (22), the final utilities to construct the proposed matching game are

i.e. as a result of the link exploration and learning mechanism, the final utilities for vTxs and vRxs will no longer change during the formation of the game; the V2V mmWave link allocation problem can be cast as a one-to-one canonical matching game and solved by applying the DA algorithm as detailed in Algorithm 1.

III-D Beamwidth Allocation using Swarm Intelligence

Once vTxs and vRxs have been paired by virtue of the matching game explained above and following Fig. 3, an optimal allocation of beamwidths $\bm{\varphi}^{t_{x}}(t_{s})$ and $\bm{\varphi}^{r_{x}}(t_{s})$ for the scheduling slot $t_{s}\in\mathcal{T}_{s}$ is performed by using Swarm Intelligence, a family of computational methods capable of efficiently dealing with convex and non-convex hard optimization problems. To this end, Swarm Intelligence relies on systems of interacting agents governed by simple behavioral rules and inter-agent communication mechanisms, such as those observed in certain insects and animal species. In particular we will focus on the so-called Particle Swarm Optimization (PSO ), which has been recently utilized to allocate resources in mmWave 5G networks .

Algorithmically the PSO-based beamwidth allocation scheme iteratively updates a $K$-sized swarm of candidate solutions $\{\mathbf{S}\}_{k=1}^{K}$, which for the problem at hand will be expressed as $\mathbf{S}_{k}=\bm{\varphi}_{k}^{t_{x}}(t_{s}),\bm{\varphi}_{k}^{r_{x}}(t_{s})$ with $k\in\{1,\ldots,K\}$ and $\zeta\triangleq|\mathbf{S}_{k}|$ equal to the number of effective mmWave links established after the matching phase. The algorithm starts by assigning a fixed beamwidth (5°) to all beamwidths in $\mathbf{S}_{k}$, and by setting a velocity vector $\mathbf{V}_{k}=\{V_{k}^{1},\ldots,V_{k}^{\zeta}\}$ per every candidate solution with inputs initially drawn uniformly at random from the range [5°, 45°]. The quality of the produced solutions is measured in terms of the average data rate computed over the active mmWave links in the system at time $t_{s}$. The PSO optimization procedure continues by refining the velocity vector based on its previous value, the best value of $\mathbf{S}_{k}$ found by the algorithm until the iteration at hand (denoted as $\mathbf{S}_{k}^{\ast}=(S_{k}^{1,\ast},\ldots,S_{k}^{\zeta,\ast})$), and the global best solution $\mathbf{S}_{\triangleright}=\{S_{\triangleright}^{1},\ldots,S_{\triangleright}^{\zeta}\}$ of the entire swarm as

with $s\in\{1,\ldots,\zeta\}$. Once the velocity vector has been updated, the value of every candidate solution $\mathbf{S}_{k}$ is updated as $\mathbf{S}_{k}\leftarrow\mathbf{S}_{k}+\mathbf{V}_{k}$, from which the best candidates for every particle in the swarm (i.e. $\mathbf{S}_{k}^{\ast}$) and the global best candidate $\mathbf{S}_{\triangleright}$ are recomputed and updated if necessary. Parameters $\varpi$ (inertia), $\eta$ and $\xi$ permit to drive the search behavior of this heuristic, whereas $r_{\eta}$ and $r_{\xi}$ are realizations of a uniform random variable with support $$. This process is repeated for a fixed number of iterations$\mathcal{I}$.

IV Simulation Setup and Results

In order to assess the performance of the proposed scheme comprehensive computer experiments have been performed over a 500 meter-long highway segment with 6 lanes of 3m width each. Vehicles are assumed to move in the same direction at constant speeds of –leftmost to rightmost lane– 140, 130, 125, 110, 90, and 70 km/h. Vehicles are either cars (80%) or trucks (20%), with cars drawn uniformly at random from a set of 5 different models, each with varying lengths and widths. Four scenarios with traffic densities of $\{70,90,130,180\}$ vehicles/km will be considered in the experiments and, hereafter, referred to as LOW, MID, HIGH and ULTRA. In order to fix the vehicle density at every scenario, vehicles leaving the segment will trigger the process for new ones to join in, which will be done by prioritizing least crowded lanes, and by guaranteeing a minimum distance to the preceded vehicle. Upon their entrance to the road, vehicles will be declared as transmitters (vTx) or receivers (vRx) with equal probability. Disregarding the role of those vehicles leaving the system, the new ones will be endorsed as vTx or vRx indistinctly.

According to Table II, the highway road scenario has been simulated for a total time of 30000 ms, with transmission intervals of $T_{t}=2$ ms and scheduling intervals $T_{s}\in\{20,50,100,200,500\}$ ms. To assess the impact of queue dynamics under different configurations several packet arrival rates and sizesNote that packet sizes of $P_{s}=3200$ and $P_{s}=2097144$ bits are in line with the specifications for the DSRC safety messages length and the 802.11ad maximum payload , respectively. are considered.

As shown in Fig. 3, two variants of our V2V allocation method will be considered for discussion:

Fixed-beamwidth weighted $\alpha$-fair matching (WAF), in which the aforementioned deferred acceptance matching algorithm is applied every $T_{s}$ ms considering the learned utilities as per (27) and (28). In this case transmit and receive beamwidths of the mmWave channels are kept equal for every link. In particular beamwidths of 5∘, 45∘ and 360∘ will be considered.

PSO weighted $\alpha$-fair matching (PSO), similar to the scheme above but incorporating the beamwidth optimization phase explained in Section III-D. As detailed therein, this optimization phase is based on the interplay between alignment delay and the throughput in mmWave communications. In all cases the PSO approach uses $K=30$ particles, $\varpi=0.5$, $\eta=\xi=1.5$ and $\mathcal{I}=50$ iterations. As opposed to the WAF approach, this scheme requires a central controller (e.g. a RSU) to coordinate the selection of transmission and reception beamwidths for each vehicle pair. Nevertheless it is of interest to explore this solution to address more realistic scenarios subject to more frequent misalignment events between pairs.

Simulation results for the above approaches will be compared to those produced by 2 different baseline schemes contributed in , namely:

Minimum-distance based pairing (MIND), by which every vTx in the system at a given scheduling slot tries to pair with its closest vRx that has not been paired yet. Pairing is conducted in increasing order of the distance from the vehicle to the beginning of the highway segment. Pairing is renewed as in our framework, i.e. every $T_{s}$ ms.

Asynchronous long-term pairing (ASYN), by which a restrictive distance-based pairing is triggered every time a new vehicle enters the highway segment. Specifically, two vehicles are paired if 1) they are eligible for pairing, i.e. still single and located within the first 20 meters of the highway segment; and 2) they are in the same or adjacent lanes. Once vehicles are associated, the pair remains unchanged until one of them leaves the segment, forcing the other vehicle to be unmatched while on track.

In all the above methods matching and pairing strategies will be subject to coverage constraints arriving from $R_{c}$. Thus, unpaired vTx/vRx might stem from asymmetries in the number of vTx and vRx at a given time slot. Moreover, coverage constraints might yield singleton vTxs and vRxs due to an infeasible association between remaining candidates.

Before proceeding further with the analysis let us remark here that a proper interpretation of the obtained results should simultaneously consider delay and reliability statistics. The reason lies in the stringent packet dropping policy adopted in this work, which deducts from the delay calculation as per (10) packets not fulfilling a delay below $D_{\max}^{\lambda}$ set for simulations such that $D_{\max}^{\lambda}=1/\lambda$. In this context, packets in queues with associated transmission rates matching or exceeding the traffic influx rate will contribute to delay statistics, whereas those in queues with slower rates will be more likely to be dropped. Therefore, as the number of packets successfully transmitted within $D_{\max}^{\lambda}$ decreases so does the number of transmissions contributing to queue average delay calculations that will be, in any case, upper bounded by $D_{\max}^{\lambda}$. Another indicator that should be considered when evaluating the goodness of all pairing approaches in this benchmark is the number of effectively matched vehicles. In this regard, it can be expected that the ASYN method fails to pair as many vehicles as the rest of the schemes, with notable differences that will be quantified next. Finally, we restrict the discussion to some representative $(P_{s},\lambda)$ combinations: $(3200\text{ bits},1/2\text{ packets/ms})$, characterizing intensive short-length messages transmissions that are common in safety related V2X communications scenarios; and $(2097144\text{ bits},1/20\text{ packets/ms})$ and $(2097144\text{ bits},1/60\text{ packets/ms})$, which model long packets arriving at a lower rate as for infotainment applications.

In the remaining of this subsection we will concentrate our discussion towards different purposes. To begin with, the effect of the beamwidth selection will be analyzed through Fig. 4. Therein the rate and delay per packetFor all methods with fixed beamwidths the beam alignment delay is given in (3) and implicitly included in the delay computations. Cumulative Density Functions (CDF) are plotted under ASYN, MIND, and WAF methods for fixed and PSO beamwidths in ULTRA scenario. If we have a closer look to the rate CDF from Fig. 4(a) and compare it with the CDF from Fig. 4(c) the latter shows much longer tails. Serving longer packets even with lower traffic arrival rates implies an increased system utilization –defined as the ratio of slots where vTxs are engaged in transmission– and consequently a higher interference which degrades the measured SINR and the link rate. Therefore, the increased delays in Fig. 4(d) as compared to those of Fig. 4(b) cannot be merely attributed to the increased serving time expected for longer packets. It can be concluded from these plots that narrow beams and PSO-optimized beams render better delay and rate results than any other considered beamwidths. This outperforming behavior holds not only for the plots shown here, but also for other simulated cases not shown in the paper for the sake of brevity. Based on this rationale, from this point onwards discussions will be restricted to the methods with narrow beams and the PSO method.

The discussion follows through Fig. 5, which further exposes the combined effect of increasing traffic arrival rates on the average delay (Fig. 5(a) and Fig. 5(c)) and on the average ratio of successful transmissions (Fig. 5(b) and Fig. 5(d)) under LOW, MID, HIGH, and ULTRA vehicle density scenarios. The effect of the queue dropping policy on the delay is evinced in these plots; while, as expected, the ratio of successful transmissions severely decreases as the traffic arrival rate becomes more demanding, the average delay decreases disregarding the utilized scheme. In other words, those cases where the degradation of the average delay with increasing values of $\lambda$ is not sharp reflect a better resiliency of the system with respect to the traffic arrival rate. However, it must be interpreted along with the ratio of successful transmissions of the method at hand. This being said, from the plots in Fig. 5 it can be observed that our proposed schemes feature the lowest dropping ratio and the most notable delay resiliency for the most demanding setting (ULTRA vehicle density, $P_{s}=3200$). As the density becomes lower, performance gaps become smaller, to the point where ASYN offers the highest success ratio for the LOW density scenario. However, the number of vTx paired by the ASYN approach is around $25$% of the overall number of vTx, whereas for the remaining schemes this number is around $60$%, increasing to levels above $90$% in scenarios with higher density. When turning to longer sized packets, dropping ratios increase significantly (more than one order of magnitude).

We now focus the discussion on Table IV which shows, for the ULTRA vehicle density case, $N=50$, $\lambda=1/T_{t}$ and $P_{s}=3200$, the ratio of scheduling periods $t_{s}\in\mathcal{T}_{s}$ over the entire simulation with an average delay $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-0.5mu}\mkern 1.5mu_{i,j}^{sch}(t_{s})$ as per (17a) and a packet dropping ratio $\Gamma_{i}^{\times}(t_{s})$ as per (11) –averaged over $t\in[t_{s},t_{s}+NT_{t})$– below different upper bounds. For a better understanding of this table, Fig. 6(a) depicts, for every scheme in the benchmark, the average delay and packet dropping ratio of every scheduling period as a scatter plot. The statistics shown in Table IV correspond to the number of points (i.e. scheduling periods) for each matching method that jointly meet upper constraints in both axes. For instance, we can observe that $44.67$% of the total scheduling periods simulated for the ASYN scheme and the ULTRA dense scenario achieve an average delay below $0.1$ ms and a packet dropping ratio below $1$%. Likewise, Table IV shows the statistics obtained for $P_{s}=2097144$ bits and $\lambda=1/30\cdot T_{t}$ over the same ULTRA dense scenario, computed from the scatter plot in Fig. 6(b). Thresholds have been adjusted for each table discussed in this section to ensure that meaningful statistics are produced for comparison.

These tables reveal interesting insights: when dealing with small-sized packets (low $P_{s}$) arriving at the queues of the vTx at a high rate (high $\lambda$) the WAF dominates under loose constraints on the packet dropping ratio (i.e. $10$%), whereas it is the PSO approach which is the outperforming method as the restriction on the number of dropped packets becomes more stringent. This changing behavior can be explained by the side benefit derived from the beamwidth optimization performed in PSO: narrower beamwidths would penalize the overall delay (but this penalty is restricted to the first transmission slot of every scheduling period) whereas allocating wider beamwidths make the mmWave channel more resilient against misalignments between already paired vehicles. This ultimately yields lower dropping statistics, as reflected in the table.

A similar observation can be drawn from the statistics obtained for $P_{s}=2097144$ bits and $1/\lambda=1/30\cdot T_{t}$ packets/s. In general PSO outperforms the rest of the baselines in the benchmark. Nonetheless, an interesting transition is noted for average delay bounds below $0.1$: WAF becomes the dominating scheme and the performance of PSO degrades significantly. The reason for this effect is that a high value of $1/\lambda$ yields long times between transmission events, hence a lower probability that packets are dropped for all schemes in the benchmark. However, once a packet arrives at an empty queue, it takes more time to flush it through the mmWave channel due to their bigger size. It follows that, for low delay thresholds narrow beamwidths are more effective for delivering the packet to its destination, disregarding whether they are suboptimal for the delay of the scheduling slot. Indeed the PSO scheme fails to meet a minimum average delay of $0.05$ ms for any of its scheduling periods, as opposed to the rest of schemes (all of them with $5^{\circ}$ beamwidth), for which the WAF scheme meets this bound with a packet dropping ratio below $0.1$% in more than $49$% of its scheduling intervals.

V Conclusions and Future Research Directions

This paper has presented a novel distributed association and beam alignment framework for mmWave V2V networks based on matching theory and swarm intelligence. Specifically we have formulated tailored utility functions for the matching game that capture 1) the relative dynamics between vTxs and vRxs in the scenario; 2) the channel and queuing dynamics learned from the past and 3) the particularities of mmWave communications, such as directionality, blockage and alignment delay. This set of utilities is fed to a deferred acceptance algorithm, which allows for pairing transmitting and receiving vehicles in a distributed manner. The matching-based association is followed by an optimization procedure that allocates transmit and receive beamwidths for each established V2V link. Simulation results confirm the expected good performance of our framework over a comprehensive number of configurations for a highway multi-lane scenario with varying vehicle densities.

Future research will be directed towards assessing the performance of this hybrid approach in multi-vUE configurations and in non-linear road networks subject to more likely misalignments between vehicles. In particular we will delve into the interplay among the scheduling period, the packet arrival statistics and the density of vehicles in real scenarios, for which we expect that the beamwidth optimization presented in this research work will render notable performance gains.

References