Every year more than 30,000 people die from car crashes in the U.S. [1]. To reduce the accident probability, as well as to alleviate traffic congestion and realize autonomous driving, vehicle-to-vehicle (V2V) communication has been regarded as a key component of future intelligent transportation systems. With the V2V communication capability, a vehicle can broadcast its signaling messages and the critical data from its sensors (GPS, LiDAR, etc.) to those vehicles in its proximity, so that the distributed vehicles can realize intelligent driving and navigational decisions. Such decisions will not only reduce car crash probability and improve transportation efficiency but will also increase fuel efficiency and enhance passenger comfort.
To enable V2V communication in large-scale vehicular networks, many communication and networking techniques have been studied and some of them have been standardized. The Dedicated Short Range Communications (DSRC) technique is the most popular one. It has been commercially used in H. Zeng some real-world transportation systems (see, e.g., [2], [3], [4]). DSRC is based on the IEEE 802.11p standard, which uses the CSMA protocol for medium access control (MAC) [5]. Since CSMA is notorious for its poor delay performance in medium access, it cannot offer any delay guarantee for V2V communication. Moreover, the medium access delay of CSMA grows exponentially with the vehicular density due to its exponential back-off mechanism, making it unsuited for delay-critical applications in dense vehicular networks.
To improve the delay performance of V2V communication, two approaches have been explored. The first one is to improve the medium access efficiency by employing TDMA-like MAC protocols through forming dynamic vehicular clusters (e.g., [6], [7], [8]), with the aim of emulating the medium access mechanism in centralized networks. This approach, however, requires tremendous communication overhead among the vehicles to obtain network topology information for cluster formation and cluster head election. Given the large overhead, it is not clear if this approach is practical in real vehicular networks [6]. The other approach is to enable collisionembracing transmissions in vehicular networks. Although a plethora of collision-embracing protocols were proposed for IEEE 802.11 networks [9], [10], [11], [12], most of them are limited to semi-stationary Wi-Fi networks, which have wired backbone connection and network-wide synchronization. These protocols cannot be applied to vehicular networks due to their high mobility and dynamic network topology. Recently, Das et al. [13] proposed a collision-embracing protocol for V2V communication. This protocol relies on repetitive transmissions to decode a data packet and, therefore, cannot offer delay guarantee for packet delivery.
In this paper, we present VehCom, a fully distributed message broadcast scheme for V2V communication networks to guarantee packet medium access delay while minimizing packet loss rate by leveraging recent advances in MIMO technology. We consider a vehicular network as shown in Fig. 1, where each vehicle wants to periodically broadcast its fresh messages to the vehicles in its communication range. In such a network, VehCom has been designed based on the following two observations. First, multiple antennas can be easily installed on a vehicle for radio signal transmission and reception, thanks to the large physical size of a vehicle and the significant advancement of RF technology in the past decades. Second, in practice, V2V communication is typically used for the exchange of critical information, which is actually limited in real systems (e.g., 100 Bytes per message). A small-size packet is sufficient for a message in V2V communication. These two observations underpin the design of VehCom.
VehCom is a joint MAC and PHY design. At the MAC layer, each vehicle broadcasts a message packet of time duration τ in every T seconds. In practice, τ is much less than T (τ T ) due to the small size of message packets. The time period T can be selected from a set of predefined values based on the message priority. Once a vehicle completes the packet transmission, it always switches to the reception mode to receive the packets from its neighboring vehicles. Due to the lack of inter-vehicle time synchronization, the packets from different vehicles collide over the air inevitably, and the collision probability depends on the value of τ /T . If every receiving vehicle can successfully decode all the packets in collision, then the delay of a packetfoot_0 is bounded by T .
At the PHY layer, if the packet collision occurs, the receiving vehicles should be capable of decoding the collided packets. Toward achieving this capability, we resort to a joint design of MAC and PHY layers. At the MAC layer, we employ a special frame structure for packet transmission. This frame structure is of a fixed time duration (i.e., τ ) and has preambles at the beginning and the end of a frame. At the PHY layer, we propose an asynchronous packet reception (APR) algorithm to decode the collided packets by leveraging a vehicle' multiple antennas. The key idea of APR is spatial signal projection. In contrast to existing packet decoding algorithms, which first perform channel estimation and then perform signal detection, APR does not require channel estimation. Instead, it uses the collided preamble(s) in the desired packet to adapt a spatial filter for signal detection in the presence of interference from other packets. Our analysis shows that, for a vehicle with M antennas, APR can perfectly recover M collided packets in zero-noise environments.
Given the independence of its MAC protocol, VehCom guarantees the message delay by each vehicle's message broadcast period (T ). We then focus on the study of its message/packet loss rate. 2 We study the packet loss rate at the PHY and MAC layers separately, and the overall packet loss rate will be the sum of those two rates. At the PHY layer, we implement our APR algorithm on a vehicular wireless testbed and measure the packet loss rate via field tests. At the MAC layer, we formulate the packet loss problem and derive a closed-form expression of the packet loss rate in different networks. Particularly, we examine a large-scale vehicular network where i) each vehicle is equipped with four antennas, ii) each vehicle has 240 vehicles in its communication range, and iii) each vehicle broadcasts a 624-bit packet over 10 MHz spectrum in every 100 ms (guaranteed delay). Our analytical and experimental results show that the packet loss rate is less than 3.9% on parking lots, less than 4.1% on local roads, and less than 6.2% on highways.
This paper advances the state-of-the-art of V2V message broadcast for vehicular networks in the following respects:
• A new packet reception algorithm: It allows a vehicle with M antennas to decode M asynchronous collided packets. • A V2V message broadcast scheme: It guarantees the medium access delay for each vehicle's messages while minimizing the message/packet loss rate. • Experimental and analytical validation: Our field tests and analytical studies confirm the feasibility of our design in real-world wireless vehicular networks. The remainder of this paper is organized as follows. Section II surveys the related work. Section III states the problem, and Section IV offers an overview of VehCom. Section V presents an asynchronous packet reception algorithm. Section VI analytically studies the MAC-layer packet loss rate, and Section VII experimentally studies the PHY-layer packet loss rate. Section VIII presents the overall results and our discussions. Section IX concludes this paper.
We first survey the industrial efforts in the development of vehicular communication systems and then survey the research efforts in the study of V2V communications. DSRC: DSRC is the main solution used for vehicular communications in transportation systems [14]. It is based on IEEE 802.11p [5]. DSRC uses CSMA as its MAC protocol, which is a collision-avoiding paradigm for medium access. While CSMA is easy to implement, it is notorious for its inefficiency in the delay and throughput performances [15], [16], [17]. This is because maintaining a collision-free environment induces a large amount of airtime overhead in distributed networks. Even if the vehicles are equipped with multiple antennas, only one of the vehicles can transmit at a time. Due to the lack of intervehicle synchronization, collision-embracing transmission of multiple vehicles is not supported by DSRC in vehicular networks. Cellular Vehicle-to-Everything (C-V2X): C-V2X, an alternative to 802.11p, is a 3GPP standard describing a technology to achieve the vehicle-to-everything communication requirements [18], [19], [20], [21], [22], [23]. Pre-commercial C-V2X deployments have recently gained considerable momentum with support from multiple automakers. C-V2X uses 4G LTE or 5G mobile cellular connectivity to send and receive messages from a vehicle to other vehicles, pedestrians, or traffic lights in its surroundings. In C-V2X, communications between a vehicle and another object (e.g., vehicle, pedestrian, traffic light, or base station) are reliant on the resource allocation at a cellular base station, which serves as a central controller for the whole network. So far, C-V2X is limited to the collision-avoiding communication paradigm and does not support collisionembracing transmission in C-V2X networks. Vehicular Communication Protocols: In addition to the industrial developments, research efforts have been invested to improve communication efficiency of vehicular networks. CSMA-like collision-avoiding distributed protocols [24], [25], [26], [27], [28], [29], [30], [31], [32] lead to an inefficient spectrum utilization and a poor delay performance that grows exponentially with the number of network nodes, making them inadequate for many vehicular applications [6], [7], [8], [33]. Some protocols [34], [35], [36] have emulated a TDMA-like centralized solution to avoid packet collision by forming dynamic clusters. Nevertheless, these protocols require additional information about the network topology for cluster formation and cluster-head election, leading to a significant communication overhead and causing serious performance degradation [6], [33]. Theoretical work [37], [38] studied the delay performance of 802.11 MAC protocol in ad hoc and vehicular networks and provided insights on the design of delay-guaranteed protocols. However, these works are limited to collision-avoiding medium access networks. Many collision-embracing MAC protocols [9], [10], [11], [12] were proposed for Wi-Fi and cellular networks. They leverage the wired backbone connection and the large coherence time to provide superior performance. Such luxuries, however, are not affordable in vehicular networks due to the fast movement of vehicles.
Recently, Das et al. [13] presents CoReCast, a collisionembracing protocol for V2V communications. CoReCast takes advantage of wireless channel diversity to retransmit a packet multiple times. At a receiving vehicle, it combines the multiple copies of the signals to decode the packets. As CoReCast is reliant on packet retransmissions for successful packet delivery, it is inefficient in packet latency and spectral efficiency. VLC Technology for Vehicular Networks: Recently, visible light communications (VLC) technology has received many research efforts and been used for vehicular communications. For example, [39] proposed and tested VLC for vehicular communications in transportation systems. However, VLC is limited to point-to-point communications and has not been applied to large-scale vehicular networks. Our design differs from the existing VLC results in vehicular networks.
Consider a large-scale autonomous (self-driving) transportation system with dense vehicles. If every vehicle can periodically broadcast its GPS data (and other critical safety data) to its neighboring vehicles, then all vehicles will have fresh knowledge about the location of the vehicles in their proximity. Such fresh knowledge can be leveraged in many aspects to enhance the driving safety. Inspired by such a case, we investigate the strategies of time-critical message broadcast in a large-scale vehicular ad hoc network. We focus on safety-related applications in our design, which typically have a limited amount of data per message. Data-intensive non-safety applications such as real-time video navigation and on-board entertainment are beyond the scope of our work. This is because safety and non-safety applications in vehicular networks tend to be supported by different schemes on different spectrum bands. For example, in DSRC, channel 172 (5.855GHz-5.865GHz) is allocated for safety applications (critical safety of life), while channels 174 and 176 (5.865GHz-5.885GHz) are allocated for general services. Network Settings and Objective: Consider a large-scale (infinite-scale) vehicular network as shown in Fig. 1. Each vehicle periodically broadcasts messages to those vehicles in its proximity to exchange data for safety applications. Since safety-related data in transportation systems is typically of small size, the messages of broadcast tends to be small (e.g., hundreds of bits). The radio transmitter on a vehicle has a limited transmit power and thus can only broadcast packets to the vehicles in its proximity as illustrated in Fig. 1. If two vehicles are beyond their communication range, they cannot hear each other due to the significant path loss. Since a vehicle is constrained by neither radio size nor radio energy consumption, it is easy to install multiple radio antennas on a vehicle. We assume all vehicles are equipped with the same number of antennas, which is denoted by M .
Our objective is to design a delay-guaranteed message broadcast scheme for the safety applications in a large-scale vehicular network while minimizing the packet loss rate. We note that maximizing spectral efficiency is not our main objective, as safety applications typically have a small amount of data. We also note that we only consider one-hop V2V message broadcast in this paper. Multi-hop V2V communication and network-level routing strategies are beyond the scope of this work. Challenges and our Approach: Vehicular ad hoc networks as shown in Fig. 1 have several salient features: a large number of widely distributed nodes, fast node movement, highly dynamic network topology, and lack of network infrastructure. Centralized medium access protocols (e.g., TDMA and OFDMA), which can achieve delay guarantee for medium access, are not suited for vehicular networks due to their above features. A distributed MAC protocol is needed for V2V communication in vehicular ad hoc networks. CSMA is such a distributed MAC protocol, but it is notorious for its poor delay performance. Therefore, pursuing medium access delay guarantee is a challenging problem. To address this challenge, we resort to a joint design of MAC and PHY layers. Particularly, we exploit the recent advances in MIMO technology and design a powerful receiver to decode asynchronous packets from uncoordinated transmitting vehicles. Such a design will reduce the packet loss rate for unsynchronized message broadcast in vehicular ad hoc networks.
VehCom is a cross-layer design for V2V communications in vehicular ad hoc networks. In what follows, we first present our MAC protocol and then outline our PHY design.
A Periodical Transmission Scheme: In vehicular networks, achieving a network-wide time synchronization for medium access (packet transmission) is extremely hard due to the fast movement of vehicles and the highly dynamic network topology. A vehicle may be equipped with GPS. However, GPS can only provide the vehicle with a reference clock for packet transmission. It cannot compensate for the radio signal propagation delay and the timing jitter caused the hardware/software imperfection. Therefore, we propose a fully distributed MAC protocol for the vehicles to perform packet transmission. Denote V as the set of all vehicles in the network. Denote unif orm(a, b) as a function that generates a random number uniformly distributed in [a, b). The proposed MAC protocol for periodical packet broadcasting is presented as follows:
MAC Protocol 1: For every vehicle i ∈ V, it broadcasts a small packet of time duration of τ at time
Fig. 2 illustrates this MAC protocol for a set of vehicles. Several remarks on this MAC protocol are in order.
• First, the periodically broadcasting packets at a vehicle are typically used to carry the critical messages related to driving safety. Such messages are typically small. We assume that all vehicles use the same packet length for message broadcasting, and denote τ as the time duration of all packets. Then, we have τ T i , i ∈ V, as illustrated in Fig. 2. • Second, the time period T i at vehicle i ∈ V is selected from a set of predefined values, which corresponds to different message priorities. A vehicle can choose a value from the predefined set based on the priority of its packet. A small value of T i should be chosen for the packets of high priority, while a large value of T i should be chosen for the packets of low priority. • Third, we assume that the vehicles' radio works in halfduplex mode. 3 Once a vehicle completes the packet transmission, it immediately switches to the reception mode to receive the packets from its neighboring vehicles. Due to the lack of inter-vehicle synchronization, the packets from different vehicles may collide over the air, and the collision probability is dependent on the value of τ /T i , i ∈ V. If every receiving vehicle can successfully decode all the packets in collision, then the medium access delay of a packet is bounded by T i . In real systems, it is impossible to successfully decode all the packets. The packet loss rate will be analyzed later. A New Frame Structure: For a receiving vehicle, it will receive packets free of collision; it will also receive packets in collision. To enhance the receiving vehicle's capability of decoding the collided packets, we propose a new frame format for packet transmission. As we shall see later, this new frame format will enable our PHY design to decode the collided packets. Fig. 3 depicts the new frame format for packet transmission in VehCom. It is a modified version of IEEE 802.11p frame format [5]. The only difference is that a postamble called Rear Training Field (RTF) is appended to the end of an IEEE 802.11p frame. Below we describe each part of the frame. of its valid subcarriers. In VehCom, RTF will be used for packet detection. One may have a concern about the communication airtime overhead incurred by the RTF in the new frame format. We address this concern by the following two justifications. First, RTF comprises only three OFDM symbols. The airtime overhead is even smaller than that in an 802.11n HT frame. Second, as we shall see later, the presence of RTF makes it possible to decode collided packets for a receiver. In other words, RTF will eliminate the need for transmitter-side coordination and, therefore, conserve a large amount of overhead for coordination at the MAC layer.
For a receiving vehicle at one time instance, it may receive one packet free of collision or multiple packets in collision. If it receives one packet free of collision, then it is easy to decode the packet. If it receives multiple packets in collision, then it is very challenging to decode those packets. This is because the transmitting vehicles are not coordinated and, as a result, the packets are asynchronous in the time domain. Fig. 4 shows some examples of packet collision at a receiving vehicle. It is evident that the packet collision pattern varies over time and the collision pattern is hard to predict. We note that, although multi-packet detection has been well studied (e.g., MU-MIMO [40], successive interference cancellation or SIC, and NOMA [41]), existing techniques may not be suited for large-scale vehicular ad hoc networks. For example, MU-MIMO is limited to synchronous networks where multiple packets are aligned in both time and frequency domains. Such alignments are extremely hard to achieve in vehicular ad hoc networks. SIC and NOMA are limited to the scenarios where different packets have significantly different signal power (≥ 6 dB) at all receivers. Nevertheless, a largescale vehicular ad hoc network may not have the luxury to meet this requirement. Therefore, these multi-packet detection techniques are not suited for vehicular ad hoc networks. In the next section, we present a new algorithm to decode asynchronous packets for a receiving vehicle by leveraging its multiple antennas.
V. ASYNCHRONOUS PACKET RECEPTION Consider a receiving vehicle in the vehicular network as shown in Fig. 1. Denote V tx = {1, 2, • • • , N tx } as the set of transmitting vehicles in its communication range at the current moment. When V tx = ∅, there is no packet transmission. When |V tx | = 1, there is only one packet to decode (no collision). When |V tx | ≥ 2, there exist multiple packets in collision. Fig. 5(a) shows the concurrent transmission. Since there is no inter-vehicle coordination, the received packets at the receiving vehicle may misalign in the time domain, as illustrated in Fig. 5(b). In what follows, we presents an algorithm to decode the collided packets.
Our design is an extension of MU-MIMO detection, which is widely used for decoding synchronous packets. It exploits the spatial degrees of freedom provided by the receiving vehicle's antennas to cancel the inter-packet interference and recover the packets. In the spatial domain, a receiving vehicle with M antennas can decode at most M packets in collision. If more than M packets collide, our design cannot handle this case and those packets are lost. In the rest of this section, we focus on the case where M ≥ N tx . To decode packet P 1 in Fig. 5(b), the interference from other packets (i.e., P 2 , P 3 , • • • , P Ntx ) must be properly handled. From Fig. 5(b) we can see that, if a packet's payload is interfered by other packets, then its preamble or postamble must be interfered by those packets. This is because all the packets are of the same length. Based on this observation, we exploit the interfered preamble/postamble to train a spatial filter and then use the constructed filter to cancel interference and recover the packet. This is the basic idea of our design.
For ease of exposition, we first relax the packet detection problem in Fig. 5(b) to that in Fig. 5(c). We focus on decoding packet P 1 when it is fully interfered by other packets. The resultant detection algorithm can be used to decode the packets in Fig. 5(b) as it has less interference among the packets.
Consider the packet detection problem in Fig. 5(c). If we have the knowledge of global channels, then it is easy to decode the packets. We could use the well-known MMSE MIMO detector to decode the packets. Specifically, we could construct the detector by letting
and then decode packet P 1 by letting ŝ1 = g 1 y, where R 1 (•) is an operator that returns the first row of a matrix; h ∈ C M ×Ntx is the compound global channel; I is an identify matrix of proper dimension; y ∈ C M ×1 is the received signal of the packets in collision; and ŝ1 ∈ C is the estimated signal of packet P 1 . In vehicular networks, however, it is extremely hard to estimate the global channel h due to the time misalignment of the collided packets. Therefore, it is challenging to decode the collided packets. To address this challenge, we propose a modified MMSE detector that does not require explicit channel knowledge.
Let r s denote the correlation of s, i.e., r s = E[ss H ], where s ∈ C Ntx×1 is the vector of signals from all transmitting vehicles. Let r w denote the correlation of w, i.e., r w = E[ww H ], where w ∈ C M ×1 is the vector of noise at the receiver. To remove the channel requirement in the packet detector, we perform the derivation as follows:
where [•] † is the pseudo-inverse operator.
We now summarize the proposed packet detection algorithm as follows:
Algorithm 1 (Packet Detection): To decode a collided packet P i , a receiving vehicle first constructs an MIMO detector by
and then uses the constructed detector to decode packet P i by ŝi (l) = g i y(l), where si (l) and ỹ(l) are the transmitted and received preamble/postamble signals of packet P i ; and ŝi (l) and y(l) are the estimated and received payload signals of packet P i .
It is evident that this packet detection algorithm does not require channel knowledge. Rather, it uses the received signal of packets in collision and the preamble/postamble in the packet to decode the signals. We note that, although the above packet detection algorithm is designed to decode packet P 1 in Fig. 5(c), it can be used to decode packet P i in Fig. 5(b). This is because the network in Fig. 5(b) has less interference than that in Fig. 5(c).
Zero-Noise Case: Suppose that the wireless channels between two vehicles remain unchanged during the time period of a packet. Then, we have the following lemma: Lemma 1: If M ≥ N tx and L ≥ N tx , then the packet detection method can perfectly decode the asynchronous collided packets in zero-noise scenarios (i.e., ŝi (l) = s i (l) for
The proof of Lemma 1 is given in Appendix. Lemma 1 shows the superior performance of the proposed algorithm in zeronoise network scenarios. In real vehicular networks, where the noise is not zero, it is hard to quantify the performance of the proposed packet detection algorithm. Therefore, we resort to simulation.
Nonzero-Noise Case: While it is impossible to simulate all scenarios, we consider a case where a vehicle is receiving packets from four vehicles as shown in Fig. 6(a). Due to the lack of synchronization, the four packets are misaligned in time, as shown in Fig. 6(b). For simplicity, we assume that these four packets experience the same path loss and independent Gaussian fading channels when impinging on the receiving vehicle. To decode the four asynchronous packets, we apply our proposed APR detector in Alg. 1 at the receiving vehicle. We measure the EVM of the decoded signal from these four packets to quantify the capability of the APR detector. As a comparison baseline, we consider an artificial case where those four packets are perfectly aligned as shown in Fig. 6(c). In this case, we assume that the receiving vehicle has perfect channel knowledge and applies MMSE detector to decode those four packets. Fig. 6(d
In practice, the packet is not transmitted over a narrowband wireless channel but over broadband wireless channel through OFDM modulation. To decode the packets, we can apply the proposed detection algorithm on each individual OFDM subcarrier. When decoding the signal on an OFDM subcarrier, we can take advantage of the reference signals on its neighboring subcarriers for the construction of the detector in (2), illustrated in Fig. 7. The rationale behind this operation is that the adjacent subcarriers have very similar wireless channels and therefore have very similar detector filters.
In VehCom, it is evident that the delay of vehicle i's packets is less than T i , where T i is vehicle i's broadcast time period, i ∈ V. However, vehicle i may not be capable of successfully decoding every packet from the vehicles in its communication range. Packet loss takes place at both MAC and PHY layers:
• Packet Loss at the MAC Layer: At the MAC layer, packet loss occurs at a vehicle, say vehicle i, in two cases: i) Vehicle i is equipped with half-duplex radio and it is in transmission mode. In this case, vehicle i will loss all the packets from the vehicles within its communication range. ii) The number of collided packets is beyond vehicle i's decoding capability. Specifically, when the number of collided packets is greater than M , vehicle i cannot decode those packets and packet loss occurs.
• Packet Loss at the PHY Layer: At the PHY layer, packet loss takes place due to the unreliability of wireless channels. We consider the case where vehicle i is in reception mode and the number of collided packets is less than or equal to M . Still, vehicle i may fail to decode the packet from a transmitting vehicle due to unreliable channels (e.g., deep fading, blockage, etc.) in real-world wireless environments. For VehCom, its total (overall) packet loss rate is the summation of its packet loss rates at the MAC and PHY layers. To explore its overall packet loss rate, we will study its packet loss rates at the MAC and PHY layers separately. Specifically, we will first analytically study its packet loss rate at the MAC layer, and then experimentally study its packet loss rate at the PHY layer. In what follows, we will focus on the study of its packet loss rate at the MAC layer when the vehicles broadcast their packets using homogeneous and heterogeneous time periods. The experimental study of its packet loss rate at the PHY layer will be presented in Section VII.
For ease of exposition, we introduce the following notational symbols. We denote V i as the set of vehicles in vehicle i's communication range, i ∈ V. We also denote N i as the cardinality of V i , i.e., N i = |V i |.
We consider the case where all the vehicles use the same parameter for their periodical transmission, i.e., T i = Γ for i ∈ V. In this case, we study the failure probability of vehicle i decoding the packets from a transmitting vehicle in its communication range, say vehicle j ∈ V i . When vehicle j broadcasts a packet, vehicle i may fail to decode this packet in the following two events:
• Event 1: Vehicle i is transmitting when vehicle j is transmitting. Since vehicle i in transmission mode, it cannot receive the packet from vehicle j. The probability of this event is 2τ /Γ. • Event 2: Vehicle i is not transmitting when vehicle j is transmitting, but its receives more than M packets in collision. The probability of the event that vehicle i is not transmitting when vehicle j is transmitting is 1 -2τ /Γ. The probability of the event that vehicle i receives more than M packets can be expressed as
Ni-1 k
Jointly considering these two events, the failure probability of vehicle i decoding the packets from a transmitting vehicle can be written as:
where p(N i ) is vehicle i's packet loss rate at the MAC layer when it has N i vehicles in its communication range. Impacts of Parameters τ , Γ, and M : Apparently, parameters τ , Γ, and M have significant impacts on the performance of VehCom. To study their impacts, we calculate the packet loss rate of VehCom in the networks with different parameters. Fig. 8 presents the packet loss rate that we calculated based on (3). We can see that the packet loss rate of VehCom decreases as the value of τ decreases. This is because the V2V communications with a smaller packet size have a smaller probability of packet collision, leading to a smaller packet loss rate. We can also see that the packet loss rate decreases as the value of Γ increases. Similarly, this is because the V2V communications with a larger broadcast time period have a smaller probability of packet collision, thereby reducing the packet loss rate. Finally, we can see that the packet loss rate decreases as the value of M increases. This is because a vehicle equipped with more antennas is capable of decoding more packets in collision, thereby lowering the packet loss rate. Although these observations are from a specific case, they actually can be applied to generic vehicular networks.
In the above study, we assumed that all the vehicles have the same time period (100 ms) for packet broadcast. We now extend our study to the case where the vehicles have different delay requirements for their packet delivery. To prioritize packet transmission, we define three delay requirements as follows:
• Low-Priority Vehicles (Γ 1 = 100 ms). For the majority of vehicles, they are in this priority category. The vehicles in this category broadcast one packet every 100 ms. • Medium-Priority Vehicles (Γ 2 = 30 ms). In a vehicular network, a small subset of vehicles have medium priority for packet transmission. For example, a police car in mission or an ambulance vehicle are in this category. These vehicles broadcast one packet every 30 ms. • High-Priority Vehicles (Γ 3 = 10 ms). A very small subset of vehicles have high priority for their packet broadcast. For example, when a vehicle suddenly brakes in an emergence circumstance, it broadcasts a packet every 10 ms. Consider a vehicle i ∈ V in Fig. 1. Recall that V i is the set of vehicles in its communication range and
Suppose that vehicle i has priority level l for packet broadcast, i.e., T i = Γ l with l ∈ {1, 2, 3}. We now study the probability of the event that vehicle i fails to decode the packet from vehicle j ∈ V i . The event can be considered in the following two cases:
• Case 1: Vehicle i itself is transmitting. In this case, vehicle i cannot receive the packet from vehicle j. The probability of this case is 2τ /Γ l , l ∈ {1, 2, 3}.
• Case 2: Vehicle i is not transmitting, but it receives more than M packets. Denote q j (K 1 , K 2 , K 3 ) as the probability that vehicle j's packet collides with M or more packets. Then, the probability of this event is
as the probability of the event that vehicle i fails to decode the packet from vehicle j ∈ V i . Since the above two events are independent, we have
Calculating q j (K 1 , K 2 , K 3 ) in ( 4) is not straightforward. Its expression dependent on vehicle j's priority for packet transmission. For ease of exposition, we introduce three binary variables A f , f ∈ {1, 2, 3}, to indicate vehicle j's priority. Specifically, we define
(5) Based on the above definition, we know that, excluding vehicle j, the number of vehicles in K f is (K f -A f ), f ∈ {1, 2, 3}. We now consider the probability of the event that vehicle j's packet collides with k f packets from the vehicles in K f . The probability of this event can be written as
Since all the vehicles transmit packets independently, we have
where I(k 1 , k 2 , k 3 ) is an indicator function defined as follows:
Denote p i (K 1 , K 2 , K 3 ) as the probability of the event that vehicle i fails to decode the packets from the vehicles in its communication range. Based on ( 4) and ( 6), vehicle i's packet loss rate is bounded by
where (A 1 , A 2 , A 3 ) = (1, 0, 0) and Γ l is vehicle i's periodical transmission window (10 ms, 30 ms, or 100 ms). In this derivation, (a) follows from the definition of packet loss probability; (b) follows from (4); and (c) follows from (6) and the fact that q j (K 1 , K 2 , K 3 ) reaches its maximum value when (A 1 , A 2 , A 3 ) = (1, 0, 0).
In this section, we evaluate the packet loss rate at the PHY layer for a vehicular network via experimentation. We consider the case where the number of collided packets is less than or equal to the number of a vehicle's antennas (M ), and aim to estimate the packet loss rate via field tests. An ideal evaluation methodology is to implement VehCom on a large number of vehicles and measure the packet loss rate in real-world transportation systems. However, we do not have the luxury to evaluate our design in this way. Therefore, we focus on the asynchronous packet reception technique at the PHY layer. We implement it on a small vehicular wireless testbed and measure the packet loss rate by emulating the packet collision environments.
We have built a prototype of this asynchronous packet reception scheme on a USRP-based wireless testbed. We set up a V2V communication network as shown in Fig. 9(a). This network consists of three vehicles. Two vehicles carry 4 radio transmitters (each carrying two transmitters), and one vehicle carries a radio receiver equipped with four antennas. At each radio transmitter, the data packets are assembled using the frame structure in Fig. 3, with a fixed transmit power of 20 dBm. A packet consists of 20 OFDM symbols and its time duration is 160 µs. The carrier frequency is 2.49 GHz and the bandwidth is 10 MHz. The four radio transmitters are completely independent, and their transmission strategy is illustrated in Fig. 9(b). This transmission strategy can emulate all the possible patterns of packet collision. The receiving vehicle is equipped with a four-antenna radio receiver, which needs to decode four collided packets from the four independent transmitters on the two vehicles. Fig. 10 shows a picture of our vehicular testbed. Packet Parameters: The frame format in Fig. 3 is used for the packet broadcast at the four transmitters. Each packet (frame) has 20 OFDM symbols: 4 for preamble, 3 for postamble, and 13 for payload. An OFDM symbol has 64 subcarriers: 4 for pilot to correct phase, 48 for payload to carry information, and the rest for zeros. Each packet uses QPSK and LDPC 1/2 Fig. 10: A vehicular testbed consisting of three vehicles. coding rate for its payload. With this modulation and coding scheme, a packet carries 624 bits. Periodical Broadcast: To evaluate a vehicle's capability of decoding asynchronous packets, we emulate a packet collision environment using the four transmitters. Specifically, we let each transmitter periodically broadcast a packet, with a waiting time T w ∼ unif orm(0, τ ), where τ = 160 µs is the time duration of a packet. That is, for a transmitter, whenever it completes a packet transmission, it waits for a random amount of time T w and then broadcasts a packet again. Since the time gap between two consecutive packets is less than τ , a packet always collide with the packets from other three vehicles, and the collision pattern varies over time, as shown in Fig. 9. This broadcast strategy makes sure that there are four packets colliding in the air.
In our tests, the receiver decodes the packets from the four independent transmitters. We calculate the packet loss rate by recording the total number of transmitted packets at the four transmitters and the number of successfully decoded packets at the receiver. At the receiver, we use the cyclic redundancy check (CRC) embedded in each packet to determine if this packet is successfully decoded. In addition, we measure the error vector magnitude (EVM) of the decoded packets at the receiver. Mathematically, the EVM of packet i is calculated by
), where s i the original signal of packet i and ŝi is the estimated version of s i at the receiver. Recall that QPSK and LDPC with 1/2 coding rate are used for packet transmission. Per [5], if the EVM of a packet is less than -10 dB, the packet is very likely to be successfully decoded; otherwise, the packet is very unlikely to be decoded. Therefore, we extrapolate the packet loss rate based on the measured EVM at the receiver. In our tests, we use -10 dB as the threshold to estimate the packet loss rate based on the measured EVM. Compared to the direct calculation of packet loss rate, the measured EVM offers more information about the performance of asynchronous packet reception algorithm.
A Case Study: We examine one case in the parking lot as shown in Fig. 11. The vehicles are moving at 5 mph. The communications of the three vehicles in Fig. 11 is illustrated in Fig. 9(a), where vehicles 1 and 3 carry four transmitters and vehicle 2 carries one receiver. At the receiver, our observation on the decoded signals confirms that a packet from one transmitter always collides with the packets from other three transmitters, as illustrated in Fig. 9(b). Fig. 12 shows the constellation diagram of the decoded packets from the four transmitters. We can see that the achieved EVM of the decoded four packets is less than -10 dB (the EVM threshold for successful packet decoding). This means that the receiver can successfully decode the packets from the four transmitters, regardless their collision patterns.
Measured EVM in Three Scenarios: We have driven the three vehicles in three different scenarios: parking lots at 5 mph (UofL Blue Parking Lot), local road at 35 mph (Eastern Parkway at Louisville), and highway at 60 mph (I-65 at Louisville Section). We collect the EVM results at the receiver (vehicle 2) and plot the cumulative distribution function (CDF) of the collected EVM. Fig. 13 shows the measured EVM of the decoded packets. Recall that we use -10 dB as the threshold to estimate the successful packet decoding. The experimental results show that the packet error rate is 2.9% at the parking lot with 5 mph, 3.1% on local roads with 35 mph, and 5.2% on highway with 60 mph. The extrapolated packet loss rates are consistent with those we calculated based on our decoding results.
As we explained in Section VI, the overall packet loss rate is attributed to both MAC and PHY layers. Mathematically, the overall packet loss rate, which is denoted by p overall , can be expressed as:
where p mac and p phy are the MAC-layer and PHY-layer packet loss rates, respectively. p mac has been analytically studied in Section VI, while p phy has been experimentally obtained in Section VII. Specifically, p phy = 2.9% on parking lot, p phy = 3.1% on local roads, and p phy = 5.2% on highway. In what follows, we show some numerical results of overall packet loss rate via case studies.
A Case Study of Homogeneous Periodical Broadcast: We consider a large-scale vehicular network where each vehicle is equipped with M antennas. Each of the vehicles persistently broadcasts a packet of τ time duration in every Γ time period. In this vehicular network, we examine a vehicle's MAC-layer and overall packet loss rate in the following settings:
• Γ = 100 ms. Per [42], the safety application of V2V communications is specified to be 100 ms. We therefore let Γ = 100 ms, which should be able to meet the delay requirements for most applications. • M = 4. Each vehicle is equipped with four antennas.
Since vehicle has no constraint on their size, power consumption, and cost, it is reasonable to install four antennas on each vehicle. Using the proposed packet detection algorithm, the vehicle is capable of decoding up to four packets in collision.
Based on (3), we first calculate MAC-layer packet loss rate with respect to the vehicle density (i.e., the number of vehicles in vehicle i's communication range, denoted by N i ). Fig. 14(a) shows our results. We can see that the packet loss rate at the MAC layer is 0.2% when each vehicle has 60 vehicles in its communication range, 0.3% when each vehicle has 120 vehicles in its communication range, 0.6% when each vehicle has 180 vehicles in its communication range, and 1.0% when each vehicle has 240 vehicles in its communication range.
Then, we calculate the overall packet loss rate based on (3) and our experimental results. Fig. 14(b) plots our results, and Table I shows the numerical data in some scenarios. We can see that the overall packet loss rate is less than 6.2% when N i ≤ 240. A Case Study of Prioritized Periodical Broadcast: In this case study, we consider a large-scale vehicular network where each vehicle is equipped with four antennas. Vehicle i persistently broadcasts a packet of τ time duration in every T i ∈ {Γ 1 , Γ 2 , Γ 3 } time period, where τ = 160 µs, Γ 1 = 100 ms, Γ 2 = 30 ms, and Γ 3 = 10 ms. We assume that the network has 85% low-priority vehicles (Γ 1 ), 10% mediumpriority vehicles (Γ 2 ), and 5% high-priority vehicles (Γ 3 ).
For this vehicular network, we first develop an upper bound of the MAC-layer packet loss rate by calculating max i∈K l p i (K 1 , K 2 , K 3 ) in ( 8), l = 1, 2, 3. Fig. 15(a) plots our results. As the figure shows, when the vehicle is performing high-priority broadcast with periodical window Γ 3 , it has the highest packet loss rate. This is because a significant portion of its airtime is used for transmitting, reducing the time for packet reception due to the half-duplex radio. The problem can be resolved by using full-duplex radio, which is expected to be available for commercial application in the near future. Then, we calculate the overall packet loss rate on parking lot, local road, and highway. Fig. 15(b-d) plot our results, and Table II shows the numerical data in some scenarios. As shown in the table, the overall packet loss is bounded by 9.0% when N i ≤ 120, regardless of traffic priority.
While many V2V communication schemes have been proposed in literature, most of them are centralized schemes requiring network-wide coordination and synchronization (see Section II). It is unfair to compare distributed VehCom with
Packet Length: In our design, we assumed that all the packets have the same length (time duration). This assumption can be realized in real networks through frame segmentation and/or padding. It can simplify the receiver's implementation as the APR detector can be used to decode all packets. If the network must support packets of different lengths, then APR and SIC can be used to decode the packets. Consider Fig. 17 for example. In Fig. 17(a) and (b), both packets can still be decoded using APR. In Fig. 17(c), the short packet can be decoded using APR, and the long packet can be decoded using SIC. Scalability of VehCom: VehCom tackles the scalability issue by design. It allows every vehicle to periodically broadcast messages to the vehicles in its proximity, regardless of the network size and the total number of vehicles in the network. Moreover, VehCom is a fully distributed message broadcast scheme. It requires neither coordination nor time alignment among the vehicles in the network. Therefore, VehCom can be applied to any-size (infinite-size) vehicular networks. Tradeoff of Delay and Packet Loss Rate: The above case study shows that, for a dense vehicular network where each vehicle has 180 vehicles in its communication range, a vehicle may suffer from as high as 9.9% packet loss rate on highways if it broadcasts a packet in every 10 ms. If an application requires lower packet loss rate, retransmission can be used to achieve the trade-off between packet delay and packet loss rate. If the vehicle repeats a packet twice in its broadcast, Fig. 17: Decoding packets of different lengths using APR and SIC.
then the packet loss rate is reduced to (9.9%) 2 = 0.98%, and the packet delay is guaranteed to be less than 20 ms. If the vehicle repeats a packet for three times in its broadcast, then the packet loss rate is reduced to (9.9%) 3 = 0.097%, and the packet delay is guaranteed to be less than 30 ms. Adjustment of Communication Range: It is evident that, when the delay bound is given, the packet loss rate for a vehicle depends on the network density (the number of vehicles in its communication range). If the vehicular network is super dense (e.g., in New York downtown), the vehicles may have more than 200 vehicles in its communication range when they use their maximum radio power for packet broadcast. In such a case, the vehicles may have an unsatisfactory packet loss rate. To tackle this issue, the vehicles can adjust their radio transmission powers to change their communication ranges. Specifically, when a vehicle suffers from a high packet loss rate, it can decrease its transmission power. When a vehicle detects a low packet loss rate, it can increase its transmit power. This makes sense in real vehicular networks, as a vehicle only needs to talk with those vehicles in its vicinity to avoid vehicle collision. Acknowledgment Mechanism: If needed, VehCom can easily support an acknowledgment mechanism to achieve reliable packet delivery. Recall that VehCom allows every vehicle to broadcast a message in every T second. Referring to Fig. 1, suppose that vehicle A wishes to receive an ACK packet from vehicle C for its broadcast message. Then, it can set the pre-defined ACK bit in its broadcast message. For vehicle C, if it successfully decodes the message from vehicle A, it broadcasts an ACK packet to vehicle A, and the average time of acknowledgment is T . If vehicle C fails to decode the message, it will not broadcast an ACK packet. After a certain time of waiting (e.g., 2T ), vehicle A considers the packet loss and re-transmission is performed. Resilience to Jamming Attacks: Radio jamming is a type of interference from malicious users. As we showed before, VehCom is capable of decoding packets in the face of unknown interference. Therefore, VehCom is resilient to jamming attacks. For instance, if a four-antenna vehicle suffers from jamming attacks from one source, it is still capable of decoding up to three asynchronous packets; if it suffers from jamming attack from two sources, it is capable of decoding up to two asynchronous packets; and so forth. Considering the openness of vehicular wireless environments, this capability plays a key role in the design of robust vehicular communication systems.
In this paper, we presented a fully distributed message broadcast scheme, called VehCom, for large-scale V2V communication networks. The enabler of VehCom is a new packet reception technique for a vehicle's radio receiver, which is realized through a joint MAC and PHY design by taking advantage of multiple antennas on a vehicle. This technique makes it possible for a vehicle to decode asynchronous collided packets from its neighboring vehicles. With this new technique, the vehicles can periodically broadcast their packets in a collision-embracing environment while maintaining their packet loss at an acceptable rate. We have validated VehCom in a vehicular network where each vehicle is equipped with four antennas and has 240 vehicles in its communication range. Our experimenatal and analytical results show that, when each vehicle broadcasts a 624-bit packet every 100 ms, the packet loss rate is less than 3.9% on parking lots, less than 4.1% on local roads, and less than 6.2% on highways.
Given that M ≥ N tx , h is a square or tall/thin matrix. In real-world environments, the wireless channels are randomly distributed. Therefore, h is of full column rank.
Denote s(l) as the signals at all the transmitting vehicles that correspond to reference OFDM symbol l in a packet from vehicle i, 1 ≤ l ≤ L and 1 ≤ i ≤ N tx . Recall that, due to the lack of inter-vehicle synchronization, the signals from other vehicles are interference for vehicle i. Then, we can write the transmit signal as: s(l) = [I 1 , • • • , I i-1 , si (l), I i+1 , • • • , I Ntx ] T , where si is the signal from vehicle i and I j is interference from vehicle j, 1 ≤ j ≤ N tx and j = i.
Recall that r is the correlation matrix of s(l), i.e., r = L l=1 s(l)s(l) H . Then, we know r is an N tx × N tx Hermitian matrix. Given that L ≥ N tx , it is easy to construct the reference signals for the transmitters so that the entries in s(l) are linearly independent with each other. Therefore, we have that r is of full rank. Define r i as the ith column of r, i.e., r i = L l=1 s(l)s i (l) H . Then, we have r † r i = 1 i , where 1 i is an N tx × 1 vector with its ith element being 1 and others being 0.
Based on the definitions of h and s(l), we have ỹ(l) = hs(l) in the zero-noise environments. Then, the constructed detector g i can be rewritten as:
where (a) follows from the assumption that noise is zero; (b) follows from the definitions of r and r i ; (c) follows from the facts that h has full column rank and r has full rank; (d) follows from the fact that h has full column rank; and (e) follows from the fact that r has full rank.
Based on (10), we have ŝi (l) = g H i y(l) = 1 H i h † hs(l)
= 1 H i s(l) = s i (l), (11) where (a) follows from the fact that h † h = I (since h has full column rank). We therefore conclude that, if M ≥ N tx and L ≥ N tx , the packet detection method can perfectly decode the asynchronous collided packets in zero-noise scenarios. This completes our proof.
The delay of a packet includes medium access delay, propagation delay, and processing delay. Compared to medium access delay, propagation and processing delays are negligible. In this paper, we consider medium access delay only.
In VehCom, one message is carried by a single packet. We therefore use message and packet interchangeably in the rest of the paper.
Although full-duplex radio has been significantly progressed, it has not be used in real-world systems. So we consider half-duplex radio in this work. VehCom can be easily extended to vehicular networks with full-duplex radio.