A Reliable Broadcast Protocol in Vehicular Ad Hoc Networks

Abstract

Periodical broadcasts of individual vehicle's safety information such as velocity and acceleration are critical in vehicular ad hoc networks (VANETs). However, current contention-based media access control (MAC) protocols cannot guarantee high performance in high density VANETs. In this paper, we propose a MAC protocol based on s-disjunct code to achieve reliable and real-time broadcasts via assigning a channel to each vehicle as the vehicle enters the network. Our protocol is adaptive as vehicles are required to adjust their communication ranges according to the network density in order to avert the interference among them. We conduct an extensive simulation study, and our results indicate that the proposed scheme can successfully achieve the requirements of the dedicated short range communication (DSRC) standard, that is, to broadcast safety information 10 times per second. Even at a high vehicle density, our scheme still guarantees that the success rates of both transmission and reception are greater than 95%, and the collision rates of access collision and merging collision are lower than 10 collisions/period.

1. Introduction

A vehicular ad hoc network (VANET) consists of a collection of vehicles communicating with each other or with road side units (RSUs) by wireless networking techniques. Each vehicle is equipped with an onboard unit (OBU) that includes a global position system (GPS) device. The major purpose of VANETs is to provide safety information such as collision avoidance and traffic jam prediction to vehicles in the network [1]. Other services such as entertainment and social networking can also be supported by VANETs. Because of the critical safety issues, the United States Federal Communication Commission has allocated 75 MHz spectrum from 5.850 GHz to 5.925 GHz to the dedicated short-range communication (DSRC) standard, which is specifically designed for short-range to medium-range automotive communication use.

The DSRC standard divides the 75 MHz spectrum space into seven 10 MHz channels. The one in the middle is the control channel while the other six are service channels. Safety information is periodically broadcasted to neighboring vehicles through the control channel 10 times/second. But not the whole 100 ms period is used for safety information broadcasts: half of this period is used by the other six service channels. The safety information and control information altogether need to be sent out within 50 ms [2, 3]. However, the MAC protocol of DSRC adopts the contention mechanism, which is called carrier sense multiple access with collision avoidance (CSMA/CA). This protocol performs well only when the node density is low. When the density increases, frequent transmission collisions occur due to the relatively limited time period and the contention-based mechanism. Based on real experiments, [4] has shown that there is a gray zone phenomenon for VANETs, which means that a good reception (package deliver rate (PDR) > 80%) is not always guaranteed.

Reliably broadcasting safety information to neighboring nodes is a big challenge, especially in the case of high node density. Although a lot of previous work has focused on this problem, most of it marginally increase some aspects of the performance. As Section 2 describes, contention-based protocols aim at achieving a larger throughput and a lower transmission delay, while schedule-based protocols focus on improving transmission reliability. Nevertheless, neither of these two categories of solutions to date has addressed scalability problems at scenarios when node density in the network is high.

Motivated by this situation, we present a MAC protocol based on s-disjunct code. In this protocol, each node is assigned a codeword locally and independently according to its current GPS location. Our proposed algorithm assigns a node a transmission channel according to its codeword. In order to adapt to high node density we propose a transmission range control algorithm based on the number of nodes in the communication range of a vehicle. The analysis and simulation results show that our protocol achieves considerable performance improvements, with the success rates of transmission and reception greater than 95%. The contributions of this paper are outlined as follows.

• (1)

We first propose a distributed codeword allocation algorithm, which assigns a codeword to each vehicle based on its current location.

(2)

We then present a channel assignment algorithm based on s-disjunct code. Theoretical analysis of this algorithm is provided to derive the probabilities of merging collision and access collision.

(3)

We next design a transmission range control algorithm, which can dynamically adjust the coverage range of a vehicle to reduce interference.

(4)

We finally conduct an extensive simulation study to verify the performance of our protocol. The results demonstrate high success rates in transmission and reception while keeping a low collision probability.

The rest of the paper is organized as follows. Section 2 summarizes the related work. Section 3 presents our system model and Section 4 details the three algorithms. Section 5 analyzes the performance of the channel allocation algorithm and Section 6 presents our simulation results. At last, Section 7 draws our conclusion.

2. Related Work

Reliable broadcast has been extensively studied. The proposed approaches are either contention-based (such as CSMA/CA) or schedule-based (such as time division multiple address (TDMA) and frequency division multiple access (FDMA)).

Several contention-based approaches proposed for VANETs [5–8] focus on optimizing the channel contention mechanisms and channel parameters. Artimy et al. [7] have built a math model to simulate the relationship between vehicle density and velocity to estimate the vehicle density and proposed an algorithm to dynamically change the transmission range based on the estimated density. Rawat et al. [8] have proposed an approach that not only adjusts the transmission range according to node density but also tunes enhanced distributed channel access (EDCA) parameters to achieve a larger throughput and a lower transmission delay. However, these studies cannot completely solve the reliable broadcast problem, because they are still based on the contention mechanism, and suffer from serious contention problems when the node density is very high.

The main idea of schedule-based mechanisms is to avoid contention collisions of the nodes in the network by designing a schedule algorithm [9–12]. Farnoud and Valaee [9] have compared the positive orthogonal code- (POC-) based broadcast algorithm with the synchronous p-persistent retransmission (SPR) and the synchronous fixed retransmission (SFR) algorithms. For POC-based broadcast, nodes in the network repeatedly broadcast information to guarantee broadcast reliability; thus the protocol wastes a lot of network resource due to repetition. Choi et al. [10] have proposed the concept of location division multiple access (LDMA), in which a time period is divided into many slots and each time slot is assigned to a node located at a certain location. This approach can mitigate the broadcast storm problem but is not appropriate for periodically broadcasting control information.

Omar et al. [12] have presented an algorithm called VeMAC which is also based on TDMA. All the slots in VeMAC are divided into three sets (left, right, and infrastructure); and each node chooses a channel from its corresponding set to access. Additionally this approach uses the RTS/CTS mechanism to tackle the hidden terminal problem. The result demonstrates a good performance in success rate and collision rate. However, our simulation study indicates that when the node density is high, the performance clearly degrades. Because VANETs must operate in high densities, dense scenarios are an important area that should be considered when designing algorithms for better performance.

s-disjunct code has been used for channel allocation in previous work [13, 14]; but those algorithms fit stationary networks better than dynamic networks as every node in the network is assumed to have a code before joining in the network and the code will never change. This does not fit VANETs, where nodes are always moving. Motivated by the heuristics in [14], we develop algorithms in this paper that are applicable to VANET environments.

To address the problems in high density scenarios, we propose a protocol that is based on s-disjunct code to assign channels and tunes transmission range according to node density. Our protocol incorporates both the schedule-based approach and the contention-based approach to achieve a better performance.

3. System Model

In this section, we introduce the underlying network model, assumptions, and the terminologies employed in this paper.

3.1. Basic Framework

We consider a vehicular ad hoc network with $\left|V\right|$ vehicles (also called nodes). Each vehicle is assumed to be equipped with a GPS receiver or be able to obtain its location information from any technique [15]. Based on the DSRC standard, the band width of the control channel is 10 MHz, which can be divided into Q orthogonal (nonoverlapping) subchannels: $k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_Q$ . We assume each node is equipped with Q radio interfaces for data reception and one additional interface for data transmission. This is a practical assumption due to the low cost of radios nowadays. Each radio can access any subchannel and the footprint of the radio is a disk resulted from the equipped omnidirectional antenna.

Safety information is sent every 100 milliseconds in the control channel, required by the DSRC standard. The 100 milliseconds are shared by both safety information and nonsafety information. Although the problem of time allocation to safety information has been discussed in [16], there is not a fixed subinterval value. It is advised to change according to the node density and the reliability requirement. But the node density is always changing, and it is hard to coordinate the subintervals of all the nodes in the network to the same value. So it is necessary to set a fixed subinterval value to all the nodes in the network. Currently, the standard [17] fixes the default value of safety information broadcast subinterval as $\mathrm{50}$ milliseconds. So we take the default value as the safety information broadcast subinterval in this paper. However, it can be changed in some other scenarios. Each subchannel of the control channel can be shared by multiple nodes in time domain, which means that 50 ms can be partitioned into multiple time slots and these slots can be accessed by different nodes without collision. A virtual channel is defined to be a time slot in a subchannel which is part of the control channel in VANETs. If the number of slots in every 50 ms is L and the number of subchannels is Q, the number of virtual channels is $N=Q\times L$ . For simplicity, we call a “virtual channel” a “channel” in the rest of the paper.

For each node, the N virtual channels are partitioned into primary channels and secondary channels. A node is linked with a binary column vector called a channel codeword, which is used to mark primary channels and secondary channels: “ $\mathrm{1}$ ” represents a primary channel and “ $\mathrm{0}$ ” represents a secondary channel. For example, a node with the vector ${\overrightarrow{c}}_u=(\mathrm{1,1},\mathrm{1,0},\mathrm{0,0},\mathrm{0,0},\mathrm{0,0}{)}^T$ indicates that channels $k_{\mathrm{1}}$ , $k_{\mathrm{2}}$ , and $k_{\mathrm{3}}$ are its primary channels and channels $k_{\mathrm{4}}$ , $k_{\mathrm{5}}$ , $k_{\mathrm{6}}$ , $k_{\mathrm{7}}$ , $k_{\mathrm{8}}$ , $k_{\mathrm{9}}$ , and $k_{\mathrm{10}}$ are its secondary channels. Nodes prefer primary channels to secondary channels and in general the number of primary channels is smaller than that of the secondary channels for any node.

It is required that, for any two different codewords $c_i$ and $c_j$ , there are at least two channels $k_{\mathrm{1}}$ and $k_{\mathrm{2}}$ such that $k_{\mathrm{1}}$ is primary to i but secondary to j and $k_{\mathrm{2}}$ is primary to j but secondary to i. Take ${\overrightarrow{c}}_i=(\mathrm{1,1},\mathrm{1,0},\mathrm{0,0},\mathrm{0,0},\mathrm{0,0}{)}^T$ and ${\overrightarrow{c}}_j=(\mathrm{0,1},\mathrm{1,1},\mathrm{0,0},\mathrm{0,0},\mathrm{0,0}{)}^T$ , for instance; channel $k_{\mathrm{1}}$ and channel $k_{\mathrm{4}}$ are such channels for i and j, respectively.

In our study, the network can be modeled by a directed graph $G(V,E,\mathcal{C})$ , where V represents network nodes, E represents directed links among nodes, and $\mathcal{C}$ is an $N\times \left|V\right|$ matrix with each column being a channel codeword associated with a node in V. For a node $u\in V$ , we use $\mathcal{N}(u)$ to denote u's interferers whose communication coverage areas overlap with that of u.

3.2. s-Disjunct Code

Given a binary $N\times t$ matrix $\mathcal{X}$ , the ith $(\mathrm{1}\le i\le t)$ column of $\mathcal{X}$ is denoted as $\mathcal{X}(i)$ , where $\mathcal{X}(i)=(x_{\mathrm{1}}(i),x_{\mathrm{2}}(i),x_{\mathrm{3}}(i),\dots ,x_N(i){)}^T$ . The BoolSum of $\mathcal{X}(i)$ and $\mathcal{X}(j)$ , denoted by $\mathcal{X}(i)\vee \mathcal{X}(j)$ , is also a binary vector of length N, shown as $Y=(y_{\mathrm{1}},y_{\mathrm{2}},y_{\mathrm{3}},\dots ,y_N{)}^T$ , where

$$\begin{array}{cc}& y_n=\left\{\begin{array}{cc}\mathrm{0},\hfill & x_n\left(i\right)=x_n\left(j\right)=\mathrm{0}\hfill \\ \mathrm{1},\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{s}.\hfill \end{array}\right.\end{array}$$

(1)

If $\mathcal{X}(i)\vee \mathcal{X}(j)=\mathcal{X}(i)$ holds, $\mathcal{X}(i)$ covers $\mathcal{X}(j)$ .

Definition 1 (s-disjunct code).

A binary matrix $\mathcal{X}$ defines s-disjunct code if and only if the Boolean sum of any s-subset of columns of $\mathcal{X}$ does not cover any other column of $\mathcal{X}$ that is not in s-subset [18, 19].

Take the $\mathrm{2}$ -disjunct code shown in ∗ as an example; the BoolSum of the first two codewords $\mathcal{X}(\mathrm{1})$ and $\mathcal{X}(\mathrm{2})$ cannot cover any other codeword in $\mathcal{X}$ except $\mathcal{X}(\mathrm{1})$ and $\mathcal{X}(\mathrm{2})$ . An example of a 2-disjunct code is as follows:

$$\begin{array}{cc}\left(\ast \right)& \left(\begin{array}{cccccccccc}\mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\end{array}\right).\end{array}$$

(*)

We define the column weight as

$$\begin{array}{cc}& w_i={\displaystyle \sum }_{k=\mathrm{1}}^N{x}_k\left(i\right)\end{array}$$

(2)

and the row weight as

$$\begin{array}{cc}& r_j={\displaystyle \sum }_{k=\mathrm{1}}^t{x}_j\left(k\right).\end{array}$$

(3)

Based on the characteristic of s-disjunct code, [14] derived the following important property.

Property 1.

Given s-disjunct code $\mathcal{X}$ , let z be any designated codeword in $\mathcal{X}$ and let S be any subset of no more than s columns not including z. There exists at least one index i, such that the ith element in z is “ $\mathrm{1}$ ” and the ith element of any codeword in S is “ $\mathrm{0}$ .”

This property motivates us to build a mapping between the code $\mathcal{C}$ in the network $G(V,E,\mathcal{C})$ and s-disjunct code $\mathcal{X}$ . In other words, we can use $N\times t\hspace{0.17em}\hspace{0.17em}s$ -disjunct code $\mathcal{X}$ as the channel code, where N represents the number of channels and t stands for the number of available codewords. Any column of code $\mathcal{X}$ is an available codeword assigned to a node in network G. Note that $\mathrm{1}/\mathrm{0}$ still stands for a primary or secondary channel of node u; column weight $w_i$ means the number of primary channels that node i has and row weight $r_k$ means the number of nodes in G using channel k as a primary channel. In the following of this paper, we use s-disjunct code $\mathcal{X}$ as a code matrix $\mathcal{C}$ .

3.3. Main Idea

We focus on channel assignment to mitigate interference among channels and maximize the network capability by using s-disjunct code. Given that every node has a copy of the codeword matrix $\mathcal{X}$ , a node picks up a codeword from $\mathcal{X}$ according to its current location and ID (e.g., vehicle's plate). At Section 4.1, we propose an algorithm to assign codewords to nodes randomly.

Then each node chooses an available channel based on its channel codeword and the current channel status, as shown in Section 4.1. Each node maintains two tables: the one-hop neighbor table and the two-hop neighbor table, which contains the one-hop and two-hop neighborhood information, respectively. Note that due to the distinct transmission ranges of the nodes, the one-hop neighbor set of node u includes those nodes sending messages successfully to u. The information consists of node IDs, their codeword indexes, and their current transmission channels. The one-hop neighbor table and the codewords of the nodes are broadcasted with safety information every time. On the contrary, the two-hop neighbor table shall be updated once a node receives its neighbors’ one-hop neighbor tables. When a collision happens, the colliding nodes release their current channels and choose new channels based on their codewords.

At last, an algorithm is proposed at Section 4.3. Nodes adjust transmission ranges to control the number of nodes in their coverage ranges. In the next section, we describe the three algorithms in detail.

4. s-Disjunct Code Based MAC Protocol

This section introduces the codeword distribution algorithm and shows how to link s-disjunct code to the channel allocation algorithm. A communication range control algorithm is finally proposed to reduce the interference among neighboring nodes.

4.1. Codeword Distribution

Let $G(V,E,\mathcal{X})$ be a vehicular ad-hoc network with $\left|V\right|$ nodes and let $\mathcal{X}$ be s-disjunct code for the network. Every codeword in $\mathcal{X}$ has an index i and we use $\mathcal{X}(i)$ to denote the ith codeword in $\mathcal{X}$ . Any node u in this network has a copy of the code $\mathcal{X}$ .

Each node chooses a codeword from $\mathcal{X}$ when it comes into the network and the codeword is changed with its location. Each node only needs to know its current GPS location based on which to determine the codeword to use. Thus the algorithm is distributed.

A large city area is divided into a number of small grids with the size of several hundred square meters. Although GPS location information is usually with an error of several meters, a node can still locate itself to a grid accurately. The codeword set $\mathcal{X}$ is divided into M subsets that do not intersect. Let $S_m\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le m\le M)$ be the mth subset. For $\forall i,j$ , $\mathrm{1}\le i$ , $j\le M$ , and $i\ne j$ , we have $S_i\cap S_j=\varnothing$ . Each grid is assigned a codeword subset $S_m$ . Any node in the grid chooses one codeword from $S_m$ . Next, we introduce how to map grids to subsets and present the algorithm for a node to choose a codeword from a subset $S_m$ .

4.1.1. Segment Generation

We divide a large area (such as a city or a state) to a number of small grids with length L, as illustrated in Figure 1(a). Additionally, we divide M subsets to a 2-dimensional array A with m rows and m columns, where $m^{\mathrm{2}}\le M$ , as shown in Figure 1(b). Each element denoted by $A_{ij}$ in A stands for a subset of codewords and the codeword number in each subset is $t/m^{\mathrm{2}}$ . Next, we show how to map a 2D grid to a 2D array, as shown in Figure 1(c).

Figure 1

Segment generation.

Let ${\mathrm{0}}^{\circ }$ longitude (namely meridian) and ${\mathrm{0}}^{\circ }$ latitude (namely equator) be reference lines. Given a node's GPS location (latitude, longitude), its distance to the equator is

$$\begin{array}{cc}& \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}{\mathrm{e}}_e=\frac{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}-{\mathrm{0}}^{°}}{\mathrm{36}{\mathrm{0}}^{°}}\times \mathrm{2}\pi R^{\prime },\end{array}$$

(4)

where $R^{\prime }$ means the radius of the meridian. Its distance to the meridian is

$$\begin{array}{cc}& \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}{\mathrm{e}}_m=\frac{\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}-{\mathrm{0}}^{°}}{\mathrm{36}{\mathrm{0}}^{°}}\times \mathrm{2}\pi R\cos \left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}\right),\end{array}$$

(5)

where R is the radius of the equator. The number of segments from the equator to this node is

$$\begin{array}{ll}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_e& =⌈\frac{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}{\mathrm{e}}_e}{L}⌉\\ & =⌈\frac{\left(\left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}-{\mathrm{0}}^{°}\right)/\mathrm{36}{\mathrm{0}}^{°}\right)\times \mathrm{2}\pi R^{\prime }}{L}⌉,\end{array}$$

(6)

where $⌈a⌉$ is the minimum integer that is not smaller than a. This means the node is at the $(\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_e)$ th grid with the equator as reference. Similarly, the number of segments from the meridian to this node is

$$\begin{array}{l}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_m\\ =⌈\frac{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}{\mathrm{e}}_m}{L}⌉\\ =⌈\frac{\left(\left(\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}-{\mathrm{0}}^{°}\right)/\mathrm{36}{\mathrm{0}}^{°}\right)\times \mathrm{2}\pi R\cos \left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}\right)}{L}⌉.\end{array}$$

(7)

Then the corresponding subset $A_{ij}$ in array A is chosen according to $(\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_e)$ and $(\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_m)$ . Intuitively, we should do a modulo operation on $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_m$ or $\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_e$ :

$$\begin{array}{cc}& i=\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_e\%m+\mathrm{1},\\ j=\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_m\%m+\mathrm{1}.\end{array}$$

(8)

4.1.2. Codeword Selection

Once a node has already known codeword subset to choose, it does a hash operation on its plate number and the output of the hash operation is the index of the codeword in $A_{ij}$ subset. The output domain of the hash function is at the range of $[\mathrm{0},t/m^{\mathrm{2}}]$ and the hash function performs randomly. Each node may find a proper index with the smallest probability of collisions. Based on the rules, the best case is that any two codewords used in the area of $(mL{)}^{\mathrm{2}}$ are different at any time instance. But there is still a collision probability. Take 8-bit Pearson hash function as an example; we can get the average number of collisions when there are n(1~100) nodes to choose codewords simultaneously. The function input is any 5-digit decimal number generated randomly and this number is considered as a plate number. Its output is a decimal number ranging from 0 to 255 as the index in a codeword subset. Figure 2 reports the number of collisions averaged over 100 runs when two or three nodes with different plate numbers hashed to the same value. One can see that when the number of nodes is less than 60, there exists no more than 4 pairs of collisions. When the number of nodes is more than 60, there are more collisions for both two vehicles and three vehicles. The average number of collisions for three vehicles is less than 1 sometimes, which means that collisions for three vehicles do not happen usually. Since each node has several primary channels to choose, two nodes may avoid choosing the same primary channel, even though their plate numbers are hashed to the same value; thus code collisions do not affect our algorithm too much.

Figure 2

The number of collisions for two or three nodes.

4.2. Channel Allocation Algorithm

In this section, we present the channel allocation algorithm shown in Algorithm 1 for broadcast. Each node u in G has a codeword $\mathcal{X}(u)$ , according to the description in the last section. Let $\mathcal{N}(u)$ be the one-hop and two-hop neighbors of u and their codewords are denoted by $\mathcal{X}(\mathcal{N}(u))$ . Node u at a time instance only takes one codeword and it knows the codewords and transmission channels of $\mathcal{N}(u)$ . Denote the channels currently occupied by $\mathcal{N}(u)$ by $\mathrm{C}\mathrm{H}(O)$ . Let $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)$ be its currently used channel and let $\mathrm{C}\mathrm{H}(u)$ be the channel assigned to node u to be used in the next time period.

Algorithm 1: Channel allocation of broadcast for node u.

Input: Codewords $$\mathcal{X}(u)$$ , $$\mathcal{X}(\mathcal{N}(u))$$ , $$\text{CH}(O)$$ , $${\text{CH}}_{\mathrm{c}}(u)$$

Output: $$\text{CH}(u)$$ , the channel assigned to u.

(1) function   $$\text{CH}(u)$$ = ChannelSelect( $$\mathcal{X}(u)$$ , $$\mathcal{X}(\mathcal{N}(u))$$ , $$\text{CH}(O)$$ , $${\text{CH}}_{\mathrm{c}}(u))$$

(2)   $${\text{CH}}_{\mathrm{1}}(u)$$ ← $$Channels(BoolSum(\mathcal{X}(\mathcal{N}(u)\cup \left\{u\right\}))\oplus BoolSum(\mathcal{X}(\mathcal{N}(u))))$$   ⊳ Find the set of primary channels

    of u that are secondary to all nodes in $$\mathcal{N}(u)$$ .

(3)  if   $${\text{CH}}_{\mathrm{1}}(u)\ne \mathrm{\varnothing }$$   then

(4)    $$\text{CH}(u)=SelectAChannel({\text{CH}}_{\mathrm{1}}(u),{\text{CH}}_{\mathrm{c}}(u))$$

(5)  else

(6)    $${\text{CH}}_{\mathrm{2}}(u)$$ ← $$Channels(\mathcal{X}(u))\cap \overline{\text{CH}(O)}$$   ⊳ Find the set of available primary channels for u.

(7)   if   $${\text{CH}}_{\mathrm{2}}\ne \mathrm{\varnothing }$$   then

(8)     $$\text{CH}(u)$$ = $$SelectAChannel({\text{CH}}_{\mathrm{2}}(u),{\text{CH}}_{\mathrm{c}}(u))$$

(9)   else

(10)     $${\text{CH}}_{\mathrm{3}}(u)$$ ← $$Channels(\mathcal{X}(u))$$ with the smallest row weight ⊳ Find the set of primary channels

      with the least row weight

(11)      $$\text{CH}(u)$$ = $$SelectAChannel({\text{CH}}_{\mathrm{3}}(u),{\text{CH}}_{\mathrm{c}}(u))$$

(12)   end if

(13)  end if

(14) end function

(15) function   $$\text{CH}(u)$$ = SeclectAChannel $$({\text{CH}}_i(u)$$ , $${\text{CH}}_{\mathrm{c}}(u))$$

(16)  if   $${\text{CH}}_{\mathrm{c}}(u)\in {\text{CH}}_i(u)$$   then

(17)    $$\text{CH}(u)={\text{CH}}_{\mathrm{c}}(u)$$   ⊳ Verify whether its current channel belongs to $${\text{CH}}_i(u)$$

(18)  else

(19)    $$\text{CH}(u)$$ ← $$RandomlyChooseOneFrom({\text{CH}}_i(u))$$

(20)  end if

(21) end function

Intuitively, u should choose those channels not being used by any of its interferers. At the beginning, u should choose a channel that is secondary to $\mathcal{N}(u)$ from its primary channel set. If such a channel can not be found, choose a primary channel that is not used by $\mathcal{N}(u)$ currently. If all of the primary channels of u are used, a channel with the least row weight of $\mathcal{N}(u)$ should be chosen at last.

The basic idea of Algorithm 1 is sketched below.

• (1)

Given $\mathcal{X}(u)$ and $\mathcal{X}(\mathcal{N}(u))$ , BoolSum of $\mathcal{X}(\mathcal{N}(u)\cup \{u\})$ and BoolSum of $\mathcal{X}(\mathcal{N}(u))$ are first calculated. Then the set of channels $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ which are from the primary channel set of node u but secondary to all nodes in $\mathcal{N}(u)$ can be obtained. In addition, channels in $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ cannot be used by $\mathcal{N}(u)$ . If $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}\ne \varnothing$ , verify whether $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)\in \mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ holds. If so, assign $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)$ to $\mathrm{C}\mathrm{H}(u)$ ; otherwise, randomly assign one channel of $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ to u.

(2)

If $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}=\varnothing$ , compute the set of channels $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ which are primary to node u and currently not being used by $\mathcal{N}(u)$ . If $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}\ne \varnothing$ , check whether $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)\in \mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ holds. If so, assign $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)$ to $\mathrm{C}\mathrm{H}(u)$ ; otherwise, randomly choose one from $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ to allocate to u.

(3)

If $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}=\varnothing$ , calculate the set $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ in its own primary channels, in order to get the channel with the least row weight of $\mathcal{X}(\mathcal{N}(u))$ . Then if $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)\in \mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ , assign $\mathrm{C}{\mathrm{H}}_{\mathrm{c}}(u)$ to $\mathrm{C}\mathrm{H}(u)$ ; if not, randomly assign one channel of $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ to u.

Example 2.

Take s-disjunct code in ∗ as an example. Give a network with three nodes $\{x,y,z\}$ whose codewords are, respectively, $\mathcal{X}(x)=\mathcal{X}(\mathrm{2})$ , $\mathcal{X}(y)=\mathcal{X}(\mathrm{3})$ , and $\mathcal{X}(z)=\mathcal{X}(\mathrm{4})$ and whose current channels are, respectively, $\mathrm{3}$ , $\mathrm{4}$ , and $\mathrm{5}$ . Then node u whose current channel is $\mathrm{1}$ joins the network and x, y, and z become u's neighbors. According to Algorithm 1, u calculates $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}=\varnothing$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}=\{\mathrm{1,2}\}$ . Because u's current channel $\mathrm{1}\in \{\mathrm{1,2}\}$ , $\mathrm{C}\mathrm{H}(u)=\{\mathrm{1}\}$ , which means that channel $\mathrm{1}$ should be assigned to node u.

Remark 3.

First, a node prefers its primary channels to its secondary channels. Second, after a node obtains the nonempty channel set ( $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ , or $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ ), it first checks whether its currently used channel is in the set. If yes, its currently used channel should be allocated to u instead of randomly choosing a new channel from the set.

4.3. Communication Range Control

Each road may have different vehicle densities due to nodes’ mobility. When the density is considerably high, the capacity of control channel is not adequate for a large amount of vehicles to access. At such a high density, a node only needs to transmit its information to the nodes close to itself. At this subsection, we propose an algorithm to control the transmission range of each node with a purpose of reusing the network space and decreasing the interference.

The idea of dynamic transmission range control was first proposed by [7], which is based on vehicle's stop time to estimate density and tune transmission range. In our algorithm, we use a more direct and lighter algorithm to achieve the objective. First, we define node density K as

$$\begin{array}{cc}& K=\frac{\text{Current\hspace{0.17em}\hspace{0.17em}Number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Nodes}}{\text{Maximum\hspace{0.17em}\hspace{0.17em}Number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Nodes}}.\end{array}$$

(9)

In order to estimate the current number of nodes in a designated area, each node should count the nodes in its vicinity within the minimum transmission range $R_{\mathrm{m}\mathrm{i}\mathrm{n}}$ according to the information received from its neighbors. The maximum number of nodes can be estimated as follows. Assume that the safety driving distance $D_s$ between two consecutive cars is known (it is got from observations and statics) and given the minimum transmission range, the maximum number of nodes within this range can be computed as $R_{\mathrm{m}\mathrm{i}\mathrm{n}}\ast L/D_s$ (L is the number of lanes obtained from the local digital map). Then

$$\begin{array}{cc}& K=\frac{\text{Current\hspace{0.17em}\hspace{0.17em}Number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Nodes}}{R_{\mathrm{m}\mathrm{i}\mathrm{n}}\ast L/D_s}.\end{array}$$

(10)

Therefore, the transmission range is calculated by the following equation:

$$\begin{array}{cc}& \mathrm{T}\mathrm{R}=\max \left\{R_{\mathrm{m}\mathrm{a}\mathrm{x}}\ast \left(\mathrm{1}-K\right),R_{\mathrm{m}\mathrm{i}\mathrm{n}}\right\},\end{array}$$

(11)

where

• (i)

  $\mathrm{T}\mathrm{R}$ is the calculated transmission range,

• (ii)

  $R_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the maximum transmission range,

• (iii)

  K is the ratio of the number of nodes to the maximum number of nodes that can be accommodated within the minimum transmission range area.

In our algorithm the minimum transmission range $R_{\mathrm{m}\mathrm{i}\mathrm{n}}$ is defined in order to guarantee network connection. If the transmission range computed from (11) is smaller than $R_{\mathrm{m}\mathrm{i}\mathrm{n}}$ , the computed one should be dropped and $R_{\mathrm{m}\mathrm{i}\mathrm{n}}$ should be chosen.

5. Performance Analysis

Based on the channel allocation algorithm proposed in Section 4, one can see that there are two cases which may cause collisions, as studied in [12]. First, when a node moves from one part of the network to another part, its currently used channel may conflict with other nodes’ channels. These nodes are going to be its neighbors, and this case is called merging collision as shown in Figure 3(a): node z is going into the two-hop area of x and they do not know each other's current channel; therefore z may use the same channel as x, which may result in a merging collision. The other one is that when two nodes are already within the communication range of each other, they may access the same time slot simultaneously. This is called access collision, illustrated in Figure 3(b): nodes x and z are in each other's two-hop range, and they may access the same channel at the same time, causing the access collision.

Figure 3

Collision cases.

In this section, we first derive the probability distribution of channel allocation and then analyze the probabilities of access collisions and merging collisions.

5.1. Probability Distribution of Channel Allocation

In this subsection, we derive the probability of a node u choosing a channel from $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ , and $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ , denoted as $P(\mathrm{C}{\mathrm{H}}_{\mathrm{1}})$ , $P(\mathrm{C}{\mathrm{H}}_{\mathrm{2}})$ , and $P(\mathrm{C}{\mathrm{H}}_{\mathrm{3}})$ . $\mathcal{N}(u)$ is u's complete interferer set and $\mathcal{X}(\mathcal{N}(u))$ is different from $\mathcal{X}(u)$ . We start with the following theorem.

Theorem 4.

If $\left|\mathcal{N}\left(u\right)\right|\le s$ holds for a node u, then $P(C{H}_1)=\mathrm{1}$ for u.

Proof.

According to the characteristic of s-disjunct matrix, if $\left|\mathcal{N}\left(u\right)\right|\le s$ , there is always a row in which $\mathcal{X}(u)$ is “ $\mathrm{1}$ ” but all the others are “ $\mathrm{0}$ .” So $\mathcal{X}(u)$ can not be covered by the $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ and such a channel can always be found in this condition.

Theorem 5.

If $\left|\mathcal{N}\left(u\right)\right|<w_u$ holds for a node u, then $P(C{H}_1)+P(C{H}_2)=\mathrm{1}$ and $P(C{H}_3)=\mathrm{0}$ for u.

Proof.

If the number of u's neighbors is less than the column weight of $\mathcal{X}(u)$ , there is at least one of the primary channels not being used by $\mathcal{N}(u)$ . Thus, $P(\mathrm{C}{\mathrm{H}}_{\mathrm{1}})+P(\mathrm{C}{\mathrm{H}}_{\mathrm{2}})=\mathrm{1}$ and $P(\mathrm{C}{\mathrm{H}}_{\mathrm{3}})=\mathrm{0}$ .

Next we will give the probability upper bound of $P(\mathrm{C}{\mathrm{H}}_{\mathrm{1}})$ , when $\left|\mathcal{N}\left(u\right)\right|>s$ . Let $\left|\mathcal{N}\left(u\right)\right|$ be $s^{\prime }$ , and let t be the total number of codewords in $\mathcal{X}$ , namely, $\left|\mathcal{X}\right|$ . Let $r_i$ stand for the ith row weight of all the t codewords. The probability that the ith row of $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ is value “ $\mathrm{0}$ ” is

$$\begin{array}{cc}& P\left(\mathrm{r}\mathrm{o}{\mathrm{w}}_i=\mathrm{0}\right)=\frac{\left(\begin{array}{c}t-s^{\prime }\\ r_i\end{array}\right)}{\left(\begin{array}{c}t\\ r_i\end{array}\right)}.\end{array}$$

(12)

On the contrary, the probability of the ith row of $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ being “ $\mathrm{1}$ ” is

$$\begin{array}{cc}& P\left(\mathrm{r}\mathrm{o}{\mathrm{w}}_i=\mathrm{1}\right)=\mathrm{1}-P\left(\mathrm{r}\mathrm{o}{\mathrm{w}}_i=\mathrm{0}\right)\end{array}$$

(13)

which means that there is at least one “ $\mathrm{1}$ ” in $\mathrm{r}\mathrm{o}{\mathrm{w}}_i$ for $\mathcal{N}(u)$ .

For a code $\mathcal{X}$ with N rows, there are ${(}_m^N)$ distinct patterns to choose m rows from $\mathcal{X}$ . Let $(k\hspace{0.17em}|\hspace{0.17em}m)\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le k\le {(}_m^N))$ denote the kth pattern of choosing m rows from $\mathcal{X}$ . The rows chosen are denoted by $\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_{\mathrm{1}}},\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_{\mathrm{2}}},\dots ,\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_m}$ and the others are $\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_{m+\mathrm{1}}},\dots ,\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_N}$ . In the kth pattern, the probability that these m rows of $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ are all value “ $\mathrm{1}$ ” is denoted as $P(\mathrm{a}\mathrm{l}\mathrm{l}\_\mathrm{o}\mathrm{n}\mathrm{e}\left|k\right|m)$ :

$$\begin{array}{ll}P\left(\mathrm{a}\mathrm{l}\mathrm{l}\_\mathrm{o}\mathrm{n}\mathrm{e}\left|k\right|m\right)& ={\displaystyle \prod }_{i=\mathrm{1}}^{m}P\left(\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_i}=\mathrm{1}\right)\\ & ·{\displaystyle \prod }_{j=m+\mathrm{1}}^{N}P\left(\mathrm{r}\mathrm{o}{\mathrm{w}}_{k_j}=\mathrm{0}\right).\end{array}$$

(14)

The probability of $\mathcal{X}(u)$ being covered by $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ under the condition that $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ has m “ $\mathrm{1}$ ” is

$$\begin{array}{l}P\left(\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\hspace{0.17em}|\hspace{0.17em}m\right)\\ ={\displaystyle \sum }_{k=\mathrm{1}}^{\left(\begin{array}{l}N\\ m\end{array}\right)}\left[P\left(\mathrm{a}\mathrm{l}\mathrm{l}\_\mathrm{o}\mathrm{n}\mathrm{e}\left|k\right|m\right)·{\displaystyle \prod }_{j=m+\mathrm{1}}^N\left(\frac{t-s^{\prime }-r_{k_j}}{t-s^{\prime }}\right)\right].\end{array}$$

(15)

As m ranges from $w_{\mathrm{m}\mathrm{a}\mathrm{x}}$ to N, the probability that $\mathcal{X}(u)$ is covered by $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ is

$$\begin{array}{cc}& P\left(\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\right)={\displaystyle \sum }_{m=w_{\mathrm{m}\mathrm{a}\mathrm{x}}}^{N}P\left(\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\hspace{0.17em}|\hspace{0.17em}m\right),\end{array}$$

(16)

where $w_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the maximum column weight of codeword in $\mathcal{X}(\mathcal{N}(u))$ . If $\mathcal{X}(u)$ is not covered by $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}\ne \varnothing$ . The probability that u can choose a channel from $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ is

$$\begin{array}{cc}& P\left(\mathrm{C}{\mathrm{H}}_{\mathrm{1}}\right)=\mathrm{1}-P\left(\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\right).\end{array}$$

(17)

If $\mathcal{X}(u)$ is covered by $\mathrm{B}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{S}\mathrm{u}\mathrm{m}(\mathcal{X}(\mathcal{N}(u)))$ , but all the primary channels of u is used by $\mathcal{X}(\mathcal{N}(u))$ , its probability is

$$\begin{array}{l}P\left(\mathrm{n}\mathrm{o}\mathrm{t}\_\mathrm{a}\mathrm{l}\mathrm{l}\_\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{d}\right)\\ ={\displaystyle \sum }_{m=w_{\mathrm{m}\mathrm{a}\mathrm{x}}}^N\left[P\left(\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\hspace{0.17em}|\hspace{0.17em}m\right)·\left(\mathrm{1}-\frac{\left(\begin{array}{l}{s}^{\prime }\\ w_u\end{array}\right)}{\left(\begin{array}{l}m\\ w_u\end{array}\right)}\right)\right].\end{array}$$

(18)

The probability of $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}\ne \varnothing$ is

$$\begin{array}{cc}& P\left(\mathrm{C}{\mathrm{H}}_{\mathrm{2}}\right)=\left\{\begin{array}{cc}\mathrm{1}-P\left(\mathrm{C}{\mathrm{H}}_{\mathrm{1}}\right),\hfill & s^{\prime }<w_u\hfill \\ P\left(\mathrm{n}\mathrm{o}\mathrm{t}\_\mathrm{a}\mathrm{l}\mathrm{l}\_\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{d}\right),\hfill & s^{\prime }\ge w_u.\hfill \end{array}\right.\end{array}$$

(19)

At last, the probability that node u chooses a channel from $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ is

$$\begin{array}{cc}& P\left(\mathrm{C}{\mathrm{H}}_{\mathrm{3}}\right)=\left\{\begin{array}{cc}\mathrm{0},\hfill & s^{\prime }<w_u\hfill \\ \mathrm{1}-P\left(\mathrm{C}{\mathrm{H}}_{\mathrm{1}}\right)-p\left(\mathrm{C}{\mathrm{H}}_{\mathrm{2}}\right),\hfill & s^{\prime }\ge w_u.\hfill \end{array}\right.\end{array}$$

(20)

5.2. Probability of Collisions

If a node u comes into a new part of the network with $\left|\mathcal{N}\left(u\right)\right|$ nodes in u's two-hop vicinity, the channel used by u may conflict with channels used by $\mathcal{N}(u)$ . Let $s^{\prime }$ denote $\left|\mathcal{N}\left(u\right)\right|$ and assume that u is using its primary channel. According to our algorithm, there will be $s^{\prime }$ channels currently being used by $\mathcal{N}(u)$ . If there is a merging collision, u's primary channels must overlap with the channels used by $\mathcal{N}(u)$ and the number of overlapping channels ranges from $\mathrm{1}$ to $\mathrm{m}\mathrm{i}\mathrm{n}\{s^{\prime },w_u\}$ . The probability that there are i overlapping channels is

$$\begin{array}{cc}& P\left(\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{a}\mathrm{p}=i\right)=\frac{\left(\begin{array}{c}{s}^{\prime }\\ i\end{array}\right)·\left(\begin{array}{c}N-s^{\prime }\\ w_u-i\end{array}\right)}{\left(\begin{array}{c}N\\ w_u\end{array}\right)}.\end{array}$$

(21)

The merging collision occurs when u chooses a channel from one of the overlapping channels to transmit. Therefore the probability of merging collision is

$$\begin{array}{l}P\left(\mathrm{M}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\right)\\ ={\displaystyle \sum }_{i=\mathrm{1}}^{\min \left\{s^{\prime },w_u\right\}}P\left(\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{a}\mathrm{p}=i\right)·\frac{i}{w_u}\\ ={\displaystyle \sum }_{i=\mathrm{1}}^{\min \left\{s^{\prime },w_u\right\}}\frac{\left(\begin{array}{l}{s}^{\prime }\\ i\end{array}\right)·\left(\begin{array}{l}N-s^{\prime }\\ w_u-i\end{array}\right)}{\left(\begin{array}{l}N\\ w_u\end{array}\right)}·\frac{i}{w_u}.\end{array}$$

(22)

Next we compute the probability of access collisions. A node u may select a channel used by another node. Due to the feature of s-disjunct code, the number of overlapping channels ranges from $\mathrm{1}$ to $w_u-\mathrm{1}$ (assume the column weights of all the codewords of its neighbors are the same here, denoted by w); therefore, the probability is

$$\begin{array}{cc}& P\left(\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\right)={\displaystyle \sum }_{i=\mathrm{1}}^{w-\mathrm{1}}\frac{\left(\begin{array}{c}w\\ i\end{array}\right)\left(\begin{array}{c}N-w\\ w-i\end{array}\right)·i}{w^{\mathrm{2}}\left(\begin{array}{c}N\\ w\end{array}\right)}.\end{array}$$

(23)

This probability is very small, and levels off to zero. When there are $s^{\prime }$ neighbors who are updating channels at the same time, the collision probability of node u is

$$\begin{array}{cc}& P\left(\mathrm{A}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\right)=\mathrm{1}-{\left(\mathrm{1}-P\left(\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\right)\right)}^{s^{\prime }}.\end{array}$$

(24)

Take a $\mathrm{96}\times \mathrm{364}$ 2-disjunct code with column weight 3 as an example. Figure 4(a) shows the probabilities that node u chooses a channel from $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ , and $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ , respectively, with the change of the number of neighbors. When the number of interferers is smaller than s, $P(\mathrm{C}{\mathrm{H}}_{\mathrm{1}})$ is 1. While $\left|\mathcal{N}\left(u\right)\right|$ increases, $P(\mathrm{C}{\mathrm{H}}_{\mathrm{1}})$ decreases and $P(\mathrm{C}{\mathrm{H}}_{\mathrm{2}})$ and $P(\mathrm{C}{\mathrm{H}}_{\mathrm{3}})$ increase.

Figure 4

Analysis result.

Figure 4(b) describes the probabilities of merging collisions and access collisions. We find that the probability of merging collision is increasing linearly, because when the number of node u's interferers grows, the overlapping probability increases. Therefore, it chooses an overlapping channel with a larger probability. The collision probability is small when the number of neighbors is very small. In practice, every node should try to use its current channel unless the computed channel set forces it to change. Most of time, a node's channel should not change frequently, and the number of nodes that change channels simultaneously is thus small. In conclusion, when $\mathcal{N}(u)$ is smaller than some threshold, it maintains a high probability of choosing a channel from $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ and $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ and thus results in a low collision probability.

6. Simulations

6.1. Simulation Scenario and Parameters

We simulate our protocol in two scenarios by Matlab. One is a two-way road scenario with each direction having two lanes. The other is a city grid layout consisting of three horizontal and three vertical roads with each direction having only one lane, shown as in Figures 5(a) and 5(b).

Figure 5

Simulation scenario.

The parameter settings are reported in Table 1. For both scenarios, we validate our protocol on different densities. The highway road is divided into $\mathrm{7}$ segments with a length of 150 m. Each segment has its own related codeword set consisting of 256 codewords. The city grid is divided into $\mathrm{9}$ segments with a dimension of 150 m × 150 m. Each segment has a codeword set of 256 codewords too. Each vehicle is generated randomly and travels at an average speed with a small fluctuation. In the highway scenario, when a vehicle reaches one end of the highway road, it reenters the road from the other end, in order to keep the same number of vehicles on the road during the simulation time. To prevent the merging collision when a vehicle reenters the road, we assume that a vehicle at a distance d to one end can communicate with vehicles within the distance $(R-d)$ to the other end (R is the communication range and $d<R$ ). In the city grid scenario, any vehicle at the intersection randomly chooses a direction to travel, and it can communicate with other vehicles within its communication range of each direction. However, a node not at the intersection area of a street can only communicate with nodes within its transmission range of the same street, due to building obstacles.

Table 1

Simulation parameters.

Parameter	Highway value	City value
Road length	1 km	430 m
Number of horizontal roads	—	3
Number of vertical roads	—	3
City block area	—	200 m × 200 m
Number of city blocks	—	4
Lane width	5 m	5 m
Lanes per direction	2	1
Segment area	150 m × 20 m	150 m × 150 m
Mean velocity	100 km/h	50 km/h
Velocity standard deviation	20 km/h	10 km/h
Number of vehicles	40~280 (step = 40)	150~600 (step = 50)
Modulation technique	QPSK	QPSK
Coding rate	1/2	1/2
Data rate per channel	6 Mbps	6 Mbps
Data rate per subchannel	0.125 Mbps	0.125 Mbps
Minimum transmission range	70 m	50 m
Maximum transmission range	150 m	150 m
Period time	100 ms	100 ms
Subchannel per period	96	96
Data packet size	300 bytes	300 bytes
Code amount per segment	256	256
Simulation time	120 s	120 s

Following the DSRC standard, safety information is sent through the control channel and its frequency band is 10 MHz. The 10 MHz channel is divided into $\mathrm{48}$ subchannels. Several modulation techniques and coding rates are suggested by the standard. However, previous work and industry experiments show that QPSK with 1/2 coding rate and 6 Mbps data rate perform better overall, and this is the default value in the current industry practice; thus such settings are adopted in our simulation study. The maximum transmission range is 150 m for both scenarios, and the minimum transmission range is set to 50 m.

The maximum size of a safety message should not exceed 200 B according to the industry suggestion. In this paper we set the packet size to be 300 B to incorporate future applications with large message requirements. Transferring a 300 B message in a subchannel costs 19.2 ms. During the $\mathrm{50}$  ms transmission time, only 2 messages can be transmitted; and thus 50 ms can be divided into $\mathrm{2}$ slots. Therefore the number of virtual subchannels in a period is $\mathrm{48}\times \mathrm{2}=\mathrm{96}$ .

We construct a 96 × 2304 s-disjunct code, which is assigned to $\mathrm{7}$ segments with each having $\mathrm{256}$ codewords in the highway scenario and to $\mathrm{9}$ segments with each having $\mathrm{256}$ codewords in the city grid scenario. From the previous test, we observe that $\mathrm{256}$ codewords are adequate for the nodes in a 150 m length road or a 150 m × 150 m area because such an area or road segment can accommodate at most 50~60 vehicles in practice. Our simulation time is set to 120 s. At the beginning of the simulation, each node is stationary until it gets its own channel. Then all the nodes start to move and timing starts. We divide 1 s into $\mathrm{10}$ periods and each vehicle sends one packet at each period. The wireless channels are ideal and the only reason of transmission failure is channel collision. We also implement VeMac [12] ( $\tau =\mathrm{0}$ and $\tau =\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}$ ) in the same road topologies and compare their performance with that of our design.

Some metrics for evaluating the network performance are defined as follows.

• (a)

Success rate of Tx is the average ratio of successful transmissions to the total transmissions per period. Here a successful transmission is achieved when a node is transmitting at channel c; no other node in its two-hop neighborhood using the same channel c is transmitting.

(b)

Success rate of Rx is the average ratio of successfully received packets to the total packets per period. The total packets include the successfully received packets and the dropped packets due to channel collisions for all nodes in the network.

(c)

Rate of merging collisions is the average number of merging collisions per period.

(d)

Rate of access collisions is the average number of access collisions per period.

6.2. Simulation Result

6.2.1. Highway Scenario

Figures 6(a) and 6(b) show the access collision rate and the merging collision rate of all the three protocols. When the number of vehicles is no more than $\mathrm{200}$ , all the access collision rates are very low, no more than $\mathrm{5}$ collisions/period. But with the number of nodes increases from 200 to 280, the access collision rate for VeMac increases quickly, especially for the case of VeMac $t=\mathrm{0}$ .

Figure 6

The collision rates in the highway scenario.

In Figure 6(b), s-disjunct has the largest merging collision rate all the time. VeMac ( $t=\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}$ ) has the lowest merging collision rate as a node can only use its own slot set of its driving direction in this protocol. When a merging collision occurs, s-disjunct protocol can use neighboring code information to choose a channel, so that the probability of access collisions is low. But if a merging collision occurs in VeMac, more access collisions may happen, due to its characteristic of randomly choosing channels. s-disjunct produces excellent results in terms of access collisions which drive the low total collision results. The total collision rate affects the success rate of Rx and Tx.

As shown in Figures 7(a) and 7(b), with the increase of the number of nodes in the network, the success rates for all protocols are decreasing, and 200 is an inflection point for this scenario. Under this threshold, the Tx success rate of s-disjunct is a little lower than the other two, with the Rx success rate almost the same. However, if the number of nodes is larger than 200, the Tx success rate and the Rx success rate of s-disjunct protocol are still kept higher than 95%, with the others dropped to as low as 81% and 72%. In terms of Rx and Tx success rates, we think that the Rx success rate is more significant than the Tx success rate. Therefore, s-disjunct protocol shows better scalability and performance in high node density case. In addition, the success rates of s-disjunct do not differ from those of the others too much when the vehicle density is low, which can be acceptable.

Figure 7

The success rates of Rx and Tx in the highway scenario.

6.2.2. City Grid Scenario

From both Figures 8(a) and 8(b), one can see that our s-disjunct protocol has lower merging collision rate and access collision rate than VeMac protocols ( $t=\mathrm{0}$ and $t=\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}$ ). That is because nodes near junctions are tending to generate merging collisions when they meet nodes using the same slot set or switch to another street with the same slot set. But this is not the case in the highway scenario as there is no intersection. A higher merging collision rate causes a higher access collision rate, for instance, as high as 350 collisions/period and 400 collisions/period, especially in the high node density case. However, the access collision rate is kept lower than 10 collisions/period for s-disjunct protocol. Therefore counting both the access collisions and the merging collisions, our s-disjunct protocol suffers less collisions than the other two protocols.

Figure 8

The collision rates in city grid.

Figures 9(a) and 9(b) describe the Tx success rate and Rx success rate for the three protocols in the city grid scenario. The inflection point is about 350 vehicles. With the number of vehicles less than 350, the Tx success rates of the two VeMac protocols are slightly larger than that of s-disjunct and the Tx success rates for all the protocols are above 95%, while the Rx success rates are almost the same. But when the number of vehicles grows, the Tx and Rx success rates of s-disjunct are both kept above 95%. On the contrary, the ones for the VeMac protocols fall down quickly, reaching $\mathrm{75}\%$ . Therefore, for both scenarios, s-disjunct protocol performs well and the Rx success rate can be higher than $\mathrm{95}\%$ , even at the high vehicle density case. When the density is very high, it is hard to achieve the $\mathrm{95}\%$ PDR, but it can still outperform current protocols, such as VeMAC. This is a high improvement.

Figure 9

The success rates of Rx and Tx in city grid.

7. Conclusion

In this paper, we present an algorithm based on s-disjunct code to allocate communication channels to nodes in a VANET. A distributed code assignment algorithm is proposed in order for each node to get the corresponding codeword. We also design a communication range control algorithm to dynamically change the transmission range based on the node density of the network. Theoretical analysis and simulation results show that our protocol can achieve a very high transmission and reception rate at a low collision rate. In the future, we will consider the more practical scenario to validate the performance when communication channels might be affected by other factors (e.g., noise, fading and shadowing).