A Distance-Aware Safety-Related Message Broadcasting Algorithm for Vehicular Networks

Abstract

A new distance-aware broadcasting algorithm was proposed to enhance the propagation distance in the latency time of safety-related message broadcasting. The IEEE 802.11p standard states that if the medium is detected as idle, a station would defer its transmission within a backoff time to avoid collisions with other stations. The backoff times follow uniform distribution over [0, CW]. In this way, fairness among all the stations can be guaranteed. However, propagation distance was ignored and in safety-related message broadcasting fairness is not the most important issue. In the proposed algorithm, the lengths of backoff times are generated from a nonuniform distribution. They are related with the distances between the source station and its forwarding stations. The farthest forwarding station has the highest probability to forward messages. Performance of the proposed algorithm is analyzed by using a 2D Markov chain. Analytical and simulation results demonstrate that the proposed algorithm can enhance the performance of safety-related message broadcasting in terms of propagation distance, which is reflected by the successful transmission probability. The proposed algorithm does not need additional waiting time, RTS/CTS, and ACK, therefore having better compatibility with the IEEE 802.11p standard than earlier distance-aware algorithms.

1. Introduction

Vehicular network is envisaged as a key component for providing safety and comfort in Intelligent Transportation Systems (ITS), which is a main application domain of the Smart City [1]. It serves as one of the most important enabling technologies to implement a plenty of applications related to vehicles, drivers, passengers, and pedestrians. These applications are the goals of a group of researchers and leading consortiums, such as C2C-CC (Car 2 Car Communication Consortium), ETSI (European Telecommunications Standards Institute), ISO CALM (Communications, Air-interface, Long and Medium range), ARIB (Association of Radio Industries and Businesses), IEEE 802.11, and IEEE WAVE standardizations. They aim to assist drivers with safety, to specify the operation of vehicles, and to manage vehicle traffic as well as other information [2–4].

The IEEE 802.11p task group [5] is working with the IEEE 1609 WAVE standard family [6] on a set of specifications to permit communication in the rapidly changing vehicular networks. The operating frequency is fixed in the DSRC (Dedicated Short Range Communication) band of 5.85–5.925 GHz. Within this range, one control channel (CCH) is reserved for system control and safety-related messages, while up to six service channels (SCHs) are used to exchange other data. WAVE further defines a channel access scheme. The access time is divided into synchronization intervals with a fixed length of 100 ms, consisting of equal-length alternating CCH and SCH intervals, as shown in Figure 1. During the CCH interval, all vehicular devices must tune on the CCH frequency for safety-related and system control data exchange, while, during the SCH interval, all vehicular devices switch to one of the SCH frequencies. At the beginning of each interval, a 4 ms long guard time is set to account for radio switching delay and timing inaccuracy in the devices. Coordination between channels depends on a global time reference—Coordinated Universal Time (UTC), while coordination between stations depends on a global position reference, both of which are provided by a global navigation satellite system.

Figure 1

Channel division in the IEEE 1609 WAVE standard.

In vehicular networks, broadcasting is a frequently used method to deliver messages. Safety-related applications rely on broadcasting, such as sharing emergency information, traffic-warning messages, road data, and announcements. These techniques are widely utilized to decrease the probability of traffic accidents. In these applications, two significant issues should be paid attention to. The first one is maximum latency time. Most safety-related messages only have a maximum latency time of 100 ms [4]. When this time passes, the message is worthless for the receiver. The second one is propagation distance of safety-related messages. The larger the propagation distance is, the more users the broadcasting can reach. In the IEEE WAVE standard, during the CCH interval, the activities on all SCHs are interrupted, and vice versa. It does not consider propagation distance. So, it is essential to increase the propagation distance of safety-related message broadcasting in a short CCH interval.

If the chosen forwarding station is farthest from the source station, the propagation distance would be enhanced. In the backoff mechanism of the IEEE 802.11p standard, each station will uniformly choose the backoff time in every backoff stage. In this way, fairness among all the stations can be guaranteed. However, this backoff mechanism ignored the propagation distance. It also means that the farthest forwarding station does not have the higher priority to forward messages. In safety-related message broadcasting, fairness of data transmission is not the most important issue.

2. Related Works

Some earlier works have addressed message broadcasting in vehicular networks. Some of them can be categorized into the distance-aware approach [7–12], in which the farthest station was chosen as the forwarding station. In [7], a scheme called UMB (Urban Multihop Broadcast) was proposed. In this scheme, forwarding stations choose black-burst lengths proportional to the distances of their segments. In [8], a binary-partition-based approach was proposed, which repetitively divides the area inside the propagation distance to obtain the farthest possible segment. In [9], a distributed forwarding selection scheme was proposed which guaranteed that a unique forwarding was selected to reliably forward the emergency message in the desired propagation direction. In [10], the authors proposed three probabilistic flooding techniques to solve the broadcast storm problem in vehicular networks. The solutions were denoted as weighted p-persistence, slotted 1-persistence, and slotted p-persistence schemes. Although these algorithms could select the farthest station as the forwarding station, they did not consider the fact that the channel would switch in 50 ms in the WAVE standard. Moreover, these algorithms need to add RTS/CTS, packet acknowledgment in the broadcasting of IEEE 802.11p standard. In [11, 12], a time reservation-based forwarding station selection algorithm was proposed. All stations in the communication range of a forwarding station randomly choose their waiting time within a given time window. This algorithm may add delay because of using the additional waiting time.

In [13], a variable CCH interval multichannel medium access control scheme was proposed, which could dynamically adjust the length ratio of CCH and SCH to enhance the saturated throughput of SCH and reduce the transmission delay of data packets, while maintaining the prioritized transmission of critical safety information on CCH. In [14], the authors modeled periodic broadcasting over the control channel in the IEEE 802.11p standard with a multichannel architecture. In [15], an analytical model for the performance evaluation of safety-related message dissemination in vehicular ad hoc networks with two priority classes was presented. These works rarely considered propagation distance.

In normal broadcasting techniques (broadcasting techniques which were released in the IEEE 802.11p standard [5, 14]), all stations have the same priority to forward messages. This would lead to frequent collisions among neighboring stations and reduce propagation distance in a short interval. The occurrence of disorderly collisions comes from the backoff mechanism in the MAC layer. Some earlier works have proposed improved backoff mechanisms through adjusting backoff window sizes but ignored propagation distance. In [16], the authors claimed that the parameters in the IEEE 802.11p MAC protocol could lead to undesired throughput performance because the backoff window sizes were not adaptive to the dynamics of the numbers of vehicles. Two algorithms were proposed which need exact information about the number of concurrent communicating vehicles to calculate the optimal window size. However, the exact number of concurrent communicating vehicles was difficult to obtain in real environments. In [17], Karamad and Ashtiani proposed a modified MAC scheme to assure fair access for vehicle-to-roadside communications. Although this scheme was developed for roadside unit- (RSU-) based communications, they gave an alternative interpretation of fairness. A modified access scheme based on the IEEE 802.11 distributed coordination function (DCF) was proposed. It determined the probability of transmission through changing the minimum contention window size. It is not suitable for safety-related applications.

In this paper, a new distance-aware safety-related message broadcasting algorithm which is compatible to the IEEE 802.11p and WAVE standard is proposed. The proposed algorithm aims at the successful transmission probability of the farthest forwarding station, in order to improve the propagation distance of safety-related message broadcasting. A 2D Markov model is formulated to analyze the performance of the proposed algorithm. This algorithm has the following merits. First, it is built on the locations of forwarding stations and does not need RTS/CTS and packet acknowledgment in broadcasting. Second, it adopts the synchronization intervals in the WAVE standard and does not need additional waiting time. Third, it is very simple and easy to implement in practice.

The remainder of this paper is organized as follows. In Section 3, the safety-related message broadcasting system model is briefly described. In Section 4, the distance-aware safety-related message broadcasting algorithm is provided. In Section 5, performance analysis of the proposed algorithm by using a 2D Markov chain is illustrated. Section 6 presents the simulation results and Section 7 gives some concluding remarks.

3. System Model

There are various types of vehicular networks, depending on the locations of vehicles and their connections. We consider a general safety-related message broadcasting system, as shown in Figure 2. When a vehicle (source station) experiences an emergency, the station on it sends a safety-related message to the stations on surrounding vehicles. It is assumed that the communication channels are ideal and the hidden terminal problem does not exist. Thus, all the surrounding stations in one-hop range could receive the message at the same time. To expand the coverage of safety-related message broadcasting, the stations in one-hop range further forward the message. We use an example to illustrate the forwarding process of multihop broadcasting in this paper. When the source station S broadcasts a safety-related message, the receiver ∂ (potentially relay station) receives and decodes the message in one-hop range. Then, it computes the time from when the message is generated by S until the time when it is received by ∂. If the time is less than the maximum latency time of the current safety-related message, ∂ will be the relay station in the next hop. It begins to compete forwarding the safety-related message. Repeat the process in the next turn until it reaches the maximum latency time of the current safety-related message. If the forwarding station is farthest from the source station in the above-mentioned process, the propagation distance would be enhanced (e.g., the propagation distance of ∂th station is larger than the αth station and the βth station, when Sth is the source station). The station which gains the right to access the channel would be the one to forward the message. The probability to get right to access the channel is reflected by the probability of successful transmission in each slot time. The right to access the channel is coordinated by the Enhanced Distribution Coordination Access (EDCA) mechanism in the MAC layer of the IEEE 802.11p standard.

Figure 2

Safety-related message broadcasting in a vehicular network.

There are four different access classes (ACs) in EDCA. Each AC has a queue where messages from different applications are queued based on their priorities. The packets from different ACs will contend internally and the winner will contend externally with those from other vehicles in the network. It is clear that warning messages in safety-related applications will use AC 3 since it has the highest priority based on the contention parameters of the CCH. Each class has different Arbitration Inter Frame Space Number (AIFSN) to ensure less waiting time for higher-priority class.

The vehicles will broadcast two types of messages: safety-related messages and status messages. The safety-related messages contain warning information, while the status messages are sent periodically to all vehicles within one-hop range and contain vehicle state information such as speed, position, and direction. Two radios are mounted on a vehicle. The first radio is used to sense the CCH, while the second one executes the backoff process. The safety-related messages will use AC 3 since it has the highest priority, while status messages will use AC 0. Therefore, internal collisions inside each station are treated by the scheduler inside that station [18, 19]. Internal contentions are not considered in this work.

Our focus is to design a message broadcasting algorithm and analyze the broadcasting propagation distance under emergency conditions through the successful transmission probability of the farthest forwarding station. To facilitate the analysis, some assumptions are made.

• (1)

The mobility of stations is not considered in the CCH interval. 50 ms is a very short time. So, we think that the locations of the stations do not change during the CCH interval.

(2)

Each message that is not successfully transmitted in a CCH interval is dropped from the MAC layer buffer at the end of every CCH interval, because most safety-related messages should obey a maximum latency of 100 ms.

4. Message Broadcasting Algorithm

The message broadcasting starts when a safety-related message is generated and is sent by a source station. All the stations in one hop-range can receive the message and are able to forward the message. If the medium was detected as idle, each forwarding station would select a random backoff time from $[\mathrm{0},CW]$ . Normally, the backoff times follow uniform distribution. In our work, they follow a non-uniform distribution and are determined by the distances between the source station and each forwarding station. The detail of the proposed algorithm is summarized in Algorithm 1.

Algorithm 1: Flowchart of the message broadcasting algorithm.

  // The process is executed by a forwarding station when it has received the safe-related message

  (denoted by the ∂th station).

  // $d_{\partial }$ : Distance between the source station and the forwarding station.

  // ${\gamma }_{\partial }$ : Normalized distance between the source station and the forwarding station.

  // R: Radius of one-hop propagation distance.

  // $W_i$ : Contention window in the ith backoff stage.

  // $X_{\partial }^i$ : Probability vector for generating the initial value of the backoff counter in the ith backoff stage.

  // k: Initial value of the backoff counter.

(1)  Perform carrier sense of the channel.

(2)  If the channel idle time is greater than $AIFSN$ ,

(3)   Compute $d_{\partial }$ as $d_{\partial }=\sqrt{(x_s-x_{\partial }{)}^{\mathrm{2}}+(y_s-y_{\partial }{)}^{\mathrm{2}}}$ ,

(4)   Compute ${\gamma }_{\partial }$ as ${\gamma }_{\partial }=\left(\mathrm{2}{d}_{\partial }/R\right)-\mathrm{1}$ .

(5)   Update $W_i$ .

(6)   Compute $X_{\partial }^i$ as

     $X_{\partial }^i=\left[X_{\partial }^i\left(\mathrm{0}\right),X_{\partial }^i\left(\mathrm{1}\right),\dots ,X_{\partial }^i\left(k\right),\dots ,X_{\partial }^i\left(W_i-\mathrm{2}\right),X_{\partial }^i\left(W_i-\mathrm{1}\right)\right]$ .

(7)   Generate k as $k=leerand(X_{\partial }^i(k))$ , where $leerand(·)$ is a user-defined function for generating random numbers

    with probability.

(8)   Decrease the value of the backoff counter by 1 in every idle slot time.

(9)   If the value of the backoff counter is equal to 0, begin to forward the safety-related message and detect collision

    in the physical layer.

(10)   If there is a collision, enter the next backoff stage and go back to Step  5.

   Else

    The forwarding is successful and go back to Step  1,

   End

   Else

   Go back to Step  8,

   End

  Else

   Go back to Step  1,

  End

In the proposed algorithm, when a forwarding station wants to send the safety-related message, it would sense an ideal channel firstly until the channel idle time is greater than $AIFSN$ . Then, the forwarding station generates a random initial value of the backoff counter $k_i$ in the ith backoff stage and wait for $k_i$ slot times before it could use the channel, where $AIFSN$ is the value set by each MAC protocol in EDCA. The forwarding station would decrease the value of its backoff counter if it senses an idle channel in any slot time. When the value of its backoff counter reaches zero and no other station has the same status, the forwarding station captures the channel and sends the message successfully; otherwise, the forwarding station enters the next backoff stage. (The collision detection in Step 9 of Algorithm 1 is done by the first radio. When the value of the backoff counter is equal to 0, the second radio forwards the message. Then, the first radio receives, decodes, and computes the checksum. If the checksum is right, the forwarding is successful. Else if the checksum is wrong, the relay stations would detect the collision and the forwarding fails.) ${\gamma }_{\partial }$ is normalized distance between the source station and the forwarding station, which is used to compute the probability vector $X_{\partial }^i$ . This vector is then used to generate the initial value $k_i$ in the ith backoff stage. We have $k_i\in [\mathrm{0},W_i-\mathrm{1}]$ and $W_i={\mathrm{2}}^i\times W,\hspace{0.17em}\hspace{0.17em}i\in (\mathrm{0},m)$ , where W is the minimum $CW$ size $C{W}_{\min }$ . At the first transmission attempt of a packet, $W=C{W}_{\min }$ [5, 18]. Figure 3 shows the backoff procedure of the IEEE 802.11p standard. In the proposed algorithm, we introduce distance to control the selection of the initial value of the backoff counter, which reflects the right to access the channel in each forwarding station. This notion has not been pursued in earlier distance-aware algorithms.

Figure 3

Backoff procedure of the IEEE 802.11p standard.

5. Performance Analysis

The performance of safety-related message broadcasting in terms of propagation distance can be reflected by the successful transmission probability of the farthest forwarding station in a short time. Therefore, we assess the propagation distance under emergency conditions through the successful transmission probability. A 2D Markov chain is formulated to model the backoff procedure and derive the successful transmission probability for each forwarding station. Markov chain has been widely used to analyze the probability of successful transmission, delay, and throughput in wireless networks. For example, the successful transmission probability of the DCF mechanism in IEEE 802.11a/b and the EDCA mechanism in IEEE 802.11p was computed by using Markov chain [13, 19, 20]. In our analytical model, probability vector $X_{\partial }^i$ is introduced, which is computed by distance and used to control the selection of the initial value of the backoff counter. This factor has not been addressed in earlier Markov chain models.

First, we would discuss about $X_{\partial }^i$ , as shown in Algorithm 1. Then, we would analyze the successful transmission probability. We select the ∂th forwarding station in the discussion for notation convenience. $X_{\partial }^i$ is the probability vector for generating the initial value of the backoff counter in the ith backoff stage. To get a higher successful transmission probability of the farthest forwarding station, we pose two reasonable constraints on $X_{\partial }^i$ . (1) The forwarding station which is farthest from the source station has the highest probability. (2) The sum of the probabilities is equal to 1.

Many functions can satisfy the above two constraints, for example, the power function $X_{\partial }=A(k{)}^{-{\gamma }_{\partial }}-B$ , the logarithmic function $X_{\partial }=A(k)\text{lg}(\mathrm{1}-{\gamma }_{\partial })$ , and the linear function $X_{\partial }^i=A(k){\gamma }_{\partial }+B$ . The unknown parameters $A(k)$ and B can be computed from the above two constraints. For simplicity, we design a linear function

$$\begin{array}{cc}& X_{\partial }^i\left(k\right)=\frac{\mathrm{2}{\gamma }_{\partial }}{W_i\left(\mathrm{1}-W_i\right)}\times k+\frac{\mathrm{1}+{\gamma }_{\partial }}{W_i}.\end{array}$$

(1)

Proof.

See Appendix A.

In the following, the successful transmission probability for a forwarding station in an arbitrary slot time will be derived. The 2D Markov chain which is used to represent the dynamic behavior of the backoff process in the MAC layer is shown in Figure 4. In this Markov chain, each state is represented by a tuple $\{s_{\partial }(t),b_{\partial }(t)\}$ , where $b_{\partial }(t)$ is the stochastic process representing the backoff counter and $s_{\partial }(t)$ is the backoff stage at the time constant t in the ∂th station. A station would attempt to transmit a packet whenever the backoff counter $b_{\partial }(t)$ is zero, regardless of the backoff stage $s_{\partial }(t)$ . Moreover, it would decrease the value of its backoff counter $b_{\partial }(t)$ , if it captures an idle channel in any slot time. Let $(i,k)$ represent the event of being in the state $\{s_{\partial }(t)=i,b_{\partial }(t)=k\}$ and $P_{\partial }(i,k\mid j,l)$ the probability of transition from state $\{s_{\partial }(t)=j,b_{\partial }(t)=l\}$ to state $\{s_{\partial }(t+\mathrm{1})=i,b_{\partial }(t+\mathrm{1})=k\}$ .

Figure 4

A 2D Markov chain for the dynamic backoff process.

The one-step transition probabilities in the 2D Markov chain are written as

$$\begin{array}{cc}& P_{\partial }\left(i,k\mid i,k+\mathrm{1}\right)=\mathrm{1},\hspace{1em}i\in \left(\mathrm{0},m\right),\hspace{0.17em}k\in \left(\mathrm{0},W_i-\mathrm{2}\right),\\ P_{\partial }(\mathrm{0},k\mid i,\mathrm{0})=(\mathrm{1}-p_{\partial })\times X_{\partial }^{\mathrm{0}}\left(k\right),\hspace{1em}i\in \left(\mathrm{0},m\right),\hspace{0.17em}k\in \left(\mathrm{0},W_{\mathrm{0}}-\mathrm{1}\right),\\ P_{\partial }(i,k\mid i-\mathrm{1,0})=p_{\partial }\times X_{\partial }^i\left(k\right),\hspace{0.5em}\hspace{0.5em}i\in \left(\mathrm{1},m\right),\hspace{0.17em}k\in \left(\mathrm{0},W_i-\mathrm{1}\right),\\ P_{\partial }\left(m,k\mid m,\mathrm{0}\right)=p_{\partial }\times X_{\partial }^m\left(k\right),\hspace{1em}k\in \left(\mathrm{0},W_m-\mathrm{1}\right).\end{array}$$

(2)

To make the analysis tractable, we have assumed that each packet collides with constant and independent probability at each transmission attempt, regardless of the number of retransmissions. The first line in (2) accounts for the fact that, at the beginning of each slot time, the value of the backoff counter is decreased. The second line in (2) accounts for the fact that a new packet transmission following a successful packet transmission starts when the value of the backoff counter reaches zero. The other lines model the backoff process after an unsuccessful transmission. In particular, as shown by the third line of (2), when an unsuccessful transmission occurs at the backoff stage $i-\mathrm{1}$ , the value of the backoff counter increases, and a new initial value of the backoff counter $k_i$ is generated from the range $(\mathrm{0},W_i-\mathrm{1})$ . The probability vector for generating the initial value of the backoff counter is $X_{\partial }^i$ . The fourth line accounts for the fact that once the backoff stage reaches m, it will not increase in subsequent packet transmissions and the probability vector for generating the initial value of the backoff counter is $X_{\partial }^m$ .

Let $b_{i,k}={\lim }_{t\to \infty }{P}_{\partial }(s_{\partial }(t)=i,b_{\partial }(t)=k)$ , $i\in (\mathrm{0},m)$ , be the stationary distribution of the Markov chain. We know that the probability of a state is equal to the sum of probabilities in one-step transfer to that state in stationary distribution. Thus, we can obtain the relationship between $b_{i,\mathrm{0}}$ , $b_{m,\mathrm{0}}$ , and $b_{\mathrm{0,0}}$ as [19, 20]

$$\begin{array}{cc}& b_{i,\mathrm{0}}=p_{\partial }^i\times b_{\mathrm{0,0}},\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\in \left(\mathrm{0},m\right),\end{array}$$

(3)

$$\begin{array}{cc}& b_{m,\mathrm{0}}=\frac{p_{\partial }^m}{\mathrm{1}-p_{\partial }}\times b_{\mathrm{0,0}}.\end{array}$$

(4)

Owing to the chain regularities, for each $k\in (\mathrm{0},W_i-\mathrm{1})$ , we have

$$\begin{array}{l}{b}_{i,k}=\left[\sum _{q=k}^{W_i-\mathrm{1}}‍X_{\partial }^i\left(q\right)\right]\times p_{\partial }^i\times b_{\mathrm{0,0}},\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\in \left(\mathrm{0},m\right),\\ b_{m,k}=\left[\sum _{q=k}^{W_m-\mathrm{1}}‍X_{\partial }^m\left(q\right)\right]\times p_{\partial }^m\times b_{\mathrm{0,0}}\\ +\left[\sum _{q=k}^{W_m-\mathrm{1}}‍X_{\partial }^m\left(q\right)\right]\times \frac{p_{\partial }^m}{\mathrm{1}-p_{\partial }}\times b_{\mathrm{0,0}}.\end{array}$$

(5)

Proof.

See Appendix B.

By using (5), the normalization condition ${\sum }_{i=\mathrm{0}}^m{\sum }_{k=\mathrm{0}}^{W_i-\mathrm{1}}{b}_{i,k}=\mathrm{1}$ can be rewritten as

$$\begin{array}{l}\mathrm{1}=\sum _{i=\mathrm{0}}^m‍\sum _{k=\mathrm{0}}^{W_i-\mathrm{1}}‍b_{i,k}\\ =\sum _{i=\mathrm{0}}^m‍\left[\sum _{k=\mathrm{0}}^{W_i-\mathrm{1}}\hspace{0.17em}‍\sum _{q=k}^{W_i-\mathrm{1}}‍X_{\partial }^i\left(q\right)\right]\times p_{\partial }^i\times b_{\mathrm{0,0}}\\ +\sum _{k=\mathrm{0}}^{W_i-\mathrm{1}}‍\hspace{0.17em}\sum _{q=k}^{W_i-\mathrm{1}}‍X_{\partial }^m\left(q\right)\times \frac{p_{\partial }^m}{\mathrm{1}-p_{\partial }}\times b_{\mathrm{0,0}}.\end{array}$$

(6)

Using (1) and (6), we get

$$\begin{array}{l}\mathrm{1}=\frac{b_{\mathrm{0,0}}}{\mathrm{2}}\\ \times \{\left[W_{\mathrm{0}}\sum _{i=\mathrm{0}}^m‍{\left(\mathrm{2}{p}_{\partial }\right)}^i+\frac{{\left(\mathrm{2}{p}_{\partial }\right)}^m}{\mathrm{1}-p_{\partial }}\times \frac{\mathrm{1}}{\mathrm{1}-p_{\partial }}\right]-{\gamma }_{\partial }\\ \hspace{1em}\hspace{0.5em}\hspace{1em}\times \left[W_{\mathrm{0}}\times \left(\frac{\mathrm{1}}{\mathrm{3}}\times \sum _{i=\mathrm{0}}^m‍{\left(\mathrm{2}\times p_{\partial }\right)}^i+\frac{\mathrm{1}}{\mathrm{3}}\times \frac{{\left(\mathrm{2}\times p_{\partial }\right)}^m}{\mathrm{1}-p_{\partial }}\right)\right]\}.\end{array}$$

(7)

Proof.

See Appendix C.

From (7), when ${\gamma }_{\partial }=\mathrm{0}$ , by using (1), we can get $X_{\partial }^i(k)=1/W_i$ . It means that the initial value of the backoff counter is uniformly chosen in the range $(\mathrm{0},W_i-\mathrm{1})$ . Equation (7) can be further simplified as follows:

$$\begin{array}{cc}& \mathrm{1}=\frac{b_{\mathrm{0,0}}}{\mathrm{2}}\times \left[W_{\mathrm{0}}\sum _{i=\mathrm{0}}^m‍{\left(\mathrm{2}{p}_{\partial }\right)}^i+\frac{{\left(\mathrm{2}{p}_{\partial }\right)}^m}{\mathrm{1}-p_{\partial }}\times \frac{\mathrm{1}}{\mathrm{1}-p_{\partial }}\right].\end{array}$$

(8)

Therefore, this expression of (7) is more general than the ones in [19, 20].

The successful transmission probability ${\tau }_{\partial }$ of the ∂th station can be expressed as

$$\begin{array}{cc}& {\tau }_{\partial }=\sum _{i=\mathrm{0}}^m‍b_{i,\mathrm{0}}=\frac{b_{\mathrm{0,0}}}{\mathrm{1}-p_{\partial }}.\end{array}$$

(9)

In the above equation, ${\tau }_{\partial }$ depends on $p_{\partial }$ , which is still unknown. To get the value of ${\tau }_{\partial }$ , we should get $p_{\partial }$ first. Note that $p_{\partial }$ is the probability of each packet colliding in each slot time in the backoff process. It also means that $p_{\partial }$ is the probability that more than one station transmit in the same slot time. So we can write another expression of $p_{\partial }$ as follows (to simplify the notation, we assume that there are only three stations in channel contending, which are ∂th station, the αth station, and the βth station):

$$\begin{array}{cc}& p_{\partial }=\mathrm{1}-\left(\mathrm{1}-{\tau }_{\alpha }\right)\times \left(\mathrm{1}-{\tau }_{\beta }\right).\end{array}$$

(10)

Equations (7), (9), and (10) represent a nonlinear system with four unknown parameters ${\tau }_{\partial }$ , ${\tau }_{\alpha }$ , ${\tau }_{\beta }$ , and $p_{\partial }$ . We cannot solve it directly. So, we list the other two parameters $p_{\alpha }$ and $p_{\beta }$ . In this way, we can get the equations about $p_{\alpha }$ , $p_{\beta }$ , ${\tau }_{\alpha }$ , and ${\tau }_{\beta }$ . Then, we use the Newton Iterative Method to solve the six unknown parameters with six equations. Now, we get the successful transmission probability for the ∂th station (the detail of the nonlinear equations is given in Appendix D).

6. Simulation Results

We do simulations under three different conditions and evaluate the performance of the proposed algorithm. In the first case, the locations of the forwarding stations follow uniform distribution. In the second case, the locations of the forwarding stations still follow uniform distribution but the starting point of message forwarding in the CCH interval follow Poisson distribution. In the third case, the locations of the forwarding stations follow non-uniform distribution.

Without loss of generality, the lowest IEEE 802.11p data rate 3 Mbps is chosen to privilege robustness and reliability. The packet length is 1000 bits to account for additional security overhead. The contention window size is in the range 15~512 ( $C{W}_{\min }=\mathrm{15}$ and $C{W}_{\max }=\mathrm{512}$ ). Note that broadcast packets are not acknowledged in the IEEE 802.11p standard. The other system parameters are listed in Table 1.

Table 1

Simulation parameters.

Parameter	Value
Slot time	16 μs
SIFS	32 μs
AIFSN	2
EIFS	188 μs
Guard interval	4 ms
CCH interval	50 ms
MAC header	256 bit
PHY header	192 bit

There are eleven stations in the vehicular network. The normalized distance vector between the source station and the forwarding stations is denoted by γ. First, we simulate the case where the locations of the forwarding stations follow uniform distribution. The normalized distance vector γ is generated as

$$\begin{array}{c}\gamma =[{\gamma }_{\mathrm{1}},{\gamma }_{\mathrm{2}},{\gamma }_{\mathrm{3}},{\gamma }_{\mathrm{4}},{\gamma }_{\mathrm{5}},{\gamma }_{\mathrm{6}},{\gamma }_{\mathrm{7}},{\gamma }_{\mathrm{8}},{\gamma }_{\mathrm{9}},{\gamma }_{\mathrm{10}},{\gamma }_{\mathrm{11}}]\\ =[\mathrm{1,0.8,0.6,0.4,0.2,0},-\mathrm{0.2},-\mathrm{0.4},-\mathrm{0.6},-\mathrm{0.8},-\mathrm{1}].\end{array}$$

(11)

Figure 5 shows the successful transmission probability for a forwarding station in a randomly chosen slot time. The horizontal axis denotes the index of the stations. It is observed that, with a longer distance from the source station, the successful transmission probability in a randomly chosen slot time is higher. The theoretical results match the simulation results well for most stations. We also see that some station's successful probabilities (simulation) have a big fluctuation around the theoretical results (e.g., no. 4, 9, and 10). The reason is that the random number generator in MATLAB is not completely random.

Figure 5

Successful probability for a forwarding station transmits in a randomly chosen slot time.

From Figure 5, it is clear that the absolute successful transmission probability for the farthest forwarding station ( $\gamma =\mathrm{1}$ ) is $\mathrm{2.5}\%$ higher than the nearest forwarding station ( $\gamma =-\mathrm{1}$ ) in one-hop range from the source station in our proposed algorithm. The relative successful transmission probability is $\mathrm{81}\%$ higher. The absolute successful transmission probability for the farthest forwarding station ( $\gamma =\mathrm{1}$ ) in the proposed algorithm is $\mathrm{1.5}\%$ higher than that in the uniform distribution algorithm. The relative successful transmission probability is $\mathrm{37}\%$ higher.

Next, we simulate the second case as mentioned above. Figure 6 shows the successful transmission probability for a forwarding station in the CCH interval. We do a 5000-time Monte Carlo simulation. It is clear that the successful transmission probability increases as the distance increases between the source station and the forwarding station in the CCH interval.

Figure 6

Successful transmission probability for a forwarding station in the CCH interval.

From Figure 6, it is clear that the absolute successful transmission probability for the farthest forwarding station ( $\gamma =\mathrm{1}$ ) is $\mathrm{20}\%$ higher than the nearest forwarding station ( $\gamma =-\mathrm{1}$ ) in one-hop range from the source station in our proposed algorithm. The relative successful transmission probability is $\mathrm{44}\%$ higher. The absolute successful transmission probability for the farthest forwarding station ( $\gamma =\mathrm{1}$ ) in the proposed algorithm is $\mathrm{10}\%$ higher than that in the uniform distribution algorithm. The relative successful transmission probability is $\mathrm{18}\%$ higher.

Figure 7 shows the results in the third simulation case. From Figure 7, we could get two important remarks. First, when all the stations have the same distance from the source station, the contention is fair. The successful transmission probability is almost equal to the one in the uniform distribution algorithm. Second, when the locations lie in two or three groups, the contention is fair inside groups and the priority is different among different groups. So, the proposed algorithm can adapt to the location distribution of forwarding stations.

Figure 7

Successful transmission probability for a forwarding station in the CCH interval, when the locations of the stations follow nonuniform distribution.

7. Conclusion

A distance-aware message broadcasting algorithm has been designed for safety-related applications in vehicular networks. A 2D Markov chain was used to analyze the performance of the proposed algorithm. The results indicate that the proposed algorithm can provide better performance than the uniform distribution broadcasting algorithms in successful transmission probability of the farthest forwarding station, thus enhancing the propagation distance. Furthermore, the proposed algorithm has better compatibility with the IEEE 802.11p and WAVE standard than earlier distance-aware algorithms and is easy to implement in practice.