ECCT: An Efficient-Cooperative ADHOC MAC for Cluster-Based TDMA System in VANETs

Abstract

In VANETs, a clustering algorithm can be used to partition the network into smaller segments. Therefore, the clustering algorithms provide not only limited channel contention but also fair channel access within the cluster. In addition, they also increase spatial reuse in VANETs and efficient control for the network topology. The main concern in the clustering algorithm is the cluster stability. The major challenge is to elect a cluster head and to maintain the membership of member nodes in a highly dynamic and a fast-changing topology. Therefore, the major criterion for cluster formation is to form a stable cluster. In this paper, a clustering algorithm to affect organization and cooperative ADHOC MAC for cluster-based TDMA system in VANETs (ECCT) is proposed. The cooperation is used to help a cluster head update each neighbor cluster's information which helps each cluster head to avoid collision when two clusters move into each other's cluster's transmission range. This efficiently utilizes a time slot. We use the lowest-ID algorithm to achieve organization. The analytical and simulated results show that not only the average number of time slots for electing a cluster head but also total number of time slots before data can be successfully transmitted is less than the existing cluster-based TDMA system and IEEE 802.11p.

1. Introduction

Vehicular Ad hoc NETwork (VANET) consists of moving vehicles creating a very dynamical network. VANET is one of the special types of Mobile Ad hoc NETworks (MANET) but it does not have an existing infrastructure or centralized administration. VANET supports many applications in safe entertainment and vehicle traffic optimization. A typical VANET is classified into a set of vehicles equipped with communication device, that is, Global Positioning System (GPS) receiver, called On-Board Unit (OBU), and a set of stationary units along roads, called Road Side Units (RSUs). Based on OBU and RSU, VANET has two essential communications: Vehicle-to-Vehicle (V2V) and Vehicle-to-RSU (V2R). To support V2V and V2R communications, the United States Federal Communication Commission (FCC) dedicated 75 MHz radio spectrum in the 5.9 GHz band for Dedicated Short Range Communications (DSRC) spectrum [1]. The DSRC spectrum is divided into seven 10 MHz channels: six Service CHannels (SCHs) and one Control CHannel (CCH), as shown in Figure 1. A sync interval (SI) comprises a CCH interval (CCHI), 50 milliseconds, and SCH Interval (SCHI), 50 milliseconds. Both CCHI and SCHI have guard interval 4 milliseconds to switch between the CCH and the SCH, as shown in Figure 1.

Figure 1

DSRC spectrum allocation.

One important service is the high priority safety application proposed for VANETs. Each vehicle broadcasts its information within one-hop neighborhood [2] for the V2V applications such as precash, blind spot warning, emergency electronic brake light, and cooperation forward collision avoidance [3]. In V2R application, such as the curve speed and traffic signal violation warnings, RSUs broadcast to all vehicles which approach them [4]. To support the high priority safety application in VANET, the Medium Access Control (MAC) protocol is designed to provide efficient broadcast services. For instance, HER-MAC [5] supports more reliability in the safety message broadcast and efficiency in the service channel utilization. E-VeMAC [6] solves the parallel transmission problem in the VeMAC protocol.

In VANET, vehicle (also called node) frequently enters or leaves transmission range of neighbor nodes. Therefore, frequent connections and disconnections are observed by the vehicles which creates the high mobility model of VANET. To limit the mobility, in VANET, vehicles are organized into clusters with at least one Cluster-Head (CH) node. CH is responsible for coordination tasks of a cluster. VANET is divided into networks of smaller and more stable clusters. Thus, vehicles moving in a similar pattern form a cluster which affect less the mobility model compared to the whole network.

VANET is particular case of MANETs. The differences with MANET are variable network density, large-scale networks, predictable mobility model, and rapid topology changes. Many clustering algorithms proposed in MANET are not suitable for VANET because of these properties. Many clustering algorithms for MANET and VANET are proposed [7]. VANET clustering algorithms focus mostly only on position and direction of vehicle and are derived from MANET. Therefore, to enhance the stability, clustering algorithms need to be refined in order to account for location, direction, and speed.

The major concerns in designing the cluster-based MAC protocol for VANETs are delay bounds (i.e., limited time), bandwidth efficiency (i.e., the network resource), mobility (i.e., vehicles leave and join cluster at high speed), scalability (i.e., high and low density scenarios), and fairness (i.e., every vehicle should get a fair chance to access the channel). Employing clustering algorithm in IEEE 802.11p degrades the performance especially when the number of nodes increases in a cluster. To improve the transmission efficiency as the number of nodes increases, recently a cluster-based TDMA is proposed, such as in [8–10]. A CH needs to be selected to serve as the network coordinator in a cluster-based TDMA. The elected CH is responsible for allocating time slots for data exchange among its cluster members (CMs). CMs can avoid collision and achieve fairness due to careful scheduling of time slots. In this paper, we propose a new clustering algorithm to elect CH faster than existing clustering algorithms by using the lowest-ID algorithm.

In cluster-based TDMA system, two clusters move into the transmission range of each other due to the dynamic nature of VANETs. The vehicles using the same time slots can collide at the intersection area. Cooperation avoids collision by utilizing an idle time slot to forward a packet transmitted by a cluster head to each neighboring cluster head. In this paper, by using idle time slots for cooperative relay transmission, the ECCT can avoid collision, increase the lifetime of cluster head, and avoid reorganizing a new cluster when the gateway did not overhear the cluster head packet.

The rest of the paper is organized as follows. Section 2 presents the relation works. Section 3 gives information about cluster-based TDMA system. Section 4 is dedicated to presenting the lowest-ID algorithm used to elect CH. Section 5 presents cooperative MAC protocol for intercluster communications. The analytical and simulated results are presented in Section 6 and we conclude and suggest some future works in Section 7.

2. Related Work

To support Quality-of-Service (QoS) for timely delivery of real-time data and increase the throughput for non-real-time traffic over Vehicle-to-Vehicle (V2V) in VANET, Su and Zhang [11] and Su and Chen [10] develop the cluster-based multichannel communications scheme based on the infrastructure-free VANET environments. The Cluster Range Control (CRC) (channel 172) is used for CMs to broadcast their packets on their predefined slots. The Intercluster Control (ICC) (channel 178) uses CSMA/CA technique for CHs to broadcast their cluster information, as shown in Figure 2. The scheme [11] reduces data congestion and supports QoS for real time of safety message while efficiently utilizing wireless bandwidth over V2V network. However, this scheme only has 4 channels (channels 176, 180, 182, and 184) to exchange data in intravehicle communications.

Figure 2

Time structure in ICC and CRC channels.

Ding and Zeng [9] proposed a clustering-based multichannel V2V communication system to provide traffic accident avoidance mechanism. This system employs a self-organized cluster by assuming two different channels: multiple control channels and a single data channel. The elected CH is a highest candidate probability node. Unfortunately, the author did not address time slots in TDMA.

Sheu and Lin [8] proposed a cluster-based TDMA (CBT) system for intervehicle communications. When the CM increases, the waiting time to elect CH is less than IEEE 802.11p. However, this system applies in the small-sized cluster. A TDMA time slots and MAC-frame format in slot 0 is depicted in Figure 3.

Figure 3

Time structure in [8].

In TDMA system in VANETs, due to the fact that the number of time slots of a frame is constant, the TDMA MAC protocols may lead to wastage of time slots. The wastage of time slots occurs when there are not enough nodes in a neighborhood to use all the time slots of a frame. In addition, upon a transmission failure, the source node has to wait until the next frame for retransmission, even if the channel is idle during unreserved time slots. In CAH-MAC [12], neighboring nodes cooperate by utilizing unreserved time slots, for retransmission of a packet which failed to reach the target receiver due to a poor channel condition. Using CAH-MAC protocol, the packet transmission delay (PTD) and packet dropping rate (PDR) decrease through mathematical analysis and computer simulation [13]. However, in the presence of relative mobility among nodes, cooperative collision occurs between reservation packets from the nodes attempting to reserve the unreserved time slot and the cooperative transmission. An enhanced CAH-MAC (eCAH-MAC) [14], the cooperative relay transmission phase, is delayed, so that cooperative collisions can be avoided and time slots can be efficiently reserved. For cooperating in clustering VANETs, a novel cooperative MAC [15] and a multichannel cooperative clustering-based MAC [16] are proposed. Each node in CAH-MAC in its own time slot transmits a packet, as shown in Figure 4. On the other hand, a novel cooperative MAC [15] and a multichannel cooperative clustering-based MAC [16] add an ACK domain in the header packet. The ACKs in this domain will help the CH and CMs to verify the reception of a packet, as shown in Figure 5. By using this structure, a novel cooperative MAC [15] can improve the reliability of broadcasting and multichannel cooperative clustering-based MAC [16] can improve the reliability of transmission and provision QoS for different application in VANETs.

Figure 4

Structure of a packet in CAH-MAC.

Figure 5

Structure of a packet in clustering VANETs.

In [17], we presented a new scheme to elect CH which inherited the time division in TDMA frame and MAC-frame format [8]. We used the lowest-ID algorithm to reduce average number of time slots to electing a CH. Therefore, the cluster is efficiently organized. In this paper, we use cooperative MAC for intercluster communication to avoid the collision when two clusters move to the transmission range of each other.

3. Cluster-Based TDMA System

3.1. Cluster Communications

In intravehicle communications, cluster-based TDMA system uses simple transmit-and-listen scheme to quickly elect CH and it allows each CM to randomly choose each time slot for bandwidth request (BR) without limiting the number of CMs. The transmit-and-listen scheme means that a node will occupy a time slot if and only if only a node transmits a HELLO packet and others receive this packet. In [8], CBT algorithm is proposed. A node is elected to be a CH if and only if a node gets random “1” and all others get random “0” (“1” means sender; “0” means receiver). When a CH is elected, all other nodes use the same transmit-and-listen scheme to randomly choose time slots for bandwidth request (BR) without limiting the number of CMs. In a cluster, CH announces its cluster information to CMs. Upon receiving CH's packet, CMs know about CH's MAC address and the other CMs in a cluster. CMs can transmit data together without collision by announcing a broadcast data packet on their assigned time slots.

A cluster structure has at least one CH. In Figure 6, CH communicates with CMs within its transmission range $(R)$ . The range of a cluster is defined by r such as $r\le R$ . CMs must elect a CH which satisfies the longest lifetime and creates a stable cluster.

Figure 6

Intra- and intercluster communications.

3.2. TDMA Time Slots

To propose cluster-based TDMA system, we design TDMA time slot structure and the associated MAC-layer frame format, as shown in Figure 7. Slots $\{\mathrm{0,1}\}$ operate with two different purposes. Nodes broadcast HELLO packets to form a cluster-based TDMA system, until a CH is elected. The elected CH algorithm is discussed in the next section. Once a cluster-based TDMA is formed, an elected CH broadcasts a slot-allocation map (SAM) including cluster head packet (CHP) to its CMs, and CMs will assign their time slots for transmitting data.

Figure 7

A new time structure.

In Figure 7, CHP is comprised of the following fields:

• (1)

CH MAC address (6 bytes): the MAC address of a CH.

(2)

CH slot number allocated (1 byte): the ID of the CH's allocation slot.

(3)

Inform cooperation (7 bytes): CH informs the helper node and the idle slot to transmit when there is more than one helper node.

(4)

CM MAC address (6 bytes): the MAC address of a CM.

(5)

Slot numbers allocated (1 byte): the ID (from 1 to $n-\mathrm{1}$ ) of the allocation slot.

(6)

CRC (4 bytes): to protect CHPs.

For each CM, they broadcast HELLO packets during their assigned time slots to announce their existences, as shown in Figure 8. If a node is an initial node, it only broadcasts its ID address. Upon receiving this packet, the CH can handle CMs and know about CM's ID addresses and allocated CM's slot number. If a node hears more than one CHP packet from CHs, it becomes a gateway node (GW). Once it detects multiple CHs, GW compares the CH's ID addresses and it decides belonging to a CH which has lower ID among multiple CHs.

Figure 8

A HELLO packet structure.

4. Efficient Organization by Using the Lowest-ID Algorithm to Elect CH

The operation of the lowest-ID algorithm to elect CH is as follows:

• (1)

In the initial state, each time slot uses mechanism to access the medium which is Distributed Coordination Function (DCF).

(2)

For each packet transmission, the backoff time is uniformly chosen in the range (0, CW). The value CW is called contention window.

(3)

When the backoff time reaches zero, a node transmits a HELLO packet as shown in Figure 10.

(4)

The received nodes compare their ID with the source's ID. They know its ID is lower or greater than source's ID. Then, we have two ID sets: lower and greater sets. Because we use the lowest-ID algorithm, the lower set is chosen and the greater set is dismissed. Nodes with higher ID than the sender do not participate in CH selection process anymore.

(5)

All nodes in the lower set will attempt to become a CH in the next time slot using the DCF mechanism.

(6)

This step will repeat from step [3–5] until no node transmits at the current time slot, t.

(7)

A node broadcasts a HELLO packet in time slot $t-1$ where the current time slot is denoted by t. In the current time slot t, there is no activity. Finally, in time slot $t+1$ , the node is promoted as a cluster head.

The operation that CMs choose time slots for bandwidth request is the same as the the operation of the lowest-ID algorithm to elect CH. Hence, a node exists in one of the four states: initial, quasi-CH, CH, and CM, as shown in Figure 9.

Figure 9

State transition of intracluster communications.

Figure 10

The procedure for becoming a quasi-CH.

5. Cooperative MAC Protocol for Intercluster Communications

We assume that the source and destination nodes are in the transmission range of a helper node. Each node can receive the packet transmitted by other nodes in the one-hop neighbors. For increasing the lifetime of the cluster, each node in a cluster has to move in the same direction [7–10]. Because a node in the VANET moves in and out of the cluster very frequently, a node which is moving in the opposite direction of a CH can be affected to a stable cluster. To improve stability of a cluster, each cluster in two different directions uses a different CDMA. Consider S and D nodes as the source and destination nodes with the sth and dth time slots and node C as the helper node. Cooperation decision and cooperative relay transmission are performed only if all the following conditions are satisfied.

(1) The Helper Successful Receives a Packet for Retransmission. A helper node must receive the packet successfully from the source node S during the sth time slot.

(2) A Destination Node Is Source's Neighbors. Helper node can relay packet if node D is within its transmission range. Hence both the source node S and destination node D must be listed as one-hop neighbors in node C's neighbor-table.

(3) There Is an Available Time Slot. Helper node, when satisfying conditions (1)-(2), can offer and perform cooperation if there exists at least one reservation time slot which it can transmit.

In addition, from [18], for a certain node x, the following sets are defined:

• (i)

$N(x)$ : the set of IDs of the one-hop neighbors of node x on the control channel.

(ii)

$T(x)$ : the set of time slots that node x must not use on the control channel in the next frame.

If the preceding conditions are satisfied, the helper node C offers cooperation to the source and destination and the cooperative transmission is performed in the time slot c. We consider a scenario depicted in Figure 12. Two clusters are moving in the same direction and there exist CMs in the boundary of a cluster's transmission range, as shown in Figure 12(a). Upon receiving a HELLO packet transmitted by node e, node b adds node e into its neighbor-table, $e\in N(b)$ , as shown in Figure 12(b). Because node e does not exist in the d's cluster head packet (CHP), node b knows node e belongs to a neighbor cluster. When a cluster moves into the transmission range of a neighbor cluster, nodes using the same time slots collide. The CH cannot receive a HELLO packet transmitted by them. The CH knows that they moved out of a cluster and CH does not include their information to CHP. Because they did not receive CHP packet, they will reorganize to form a new cluster. If cluster head used the same time slot with neighbor cluster head, the packets transmitted by CHs will be collided. The CMs did not receive the CHP packet. They know CH moved out of a cluster. They will reorganize to form a new cluster. To avoid this collision, the cluster head must need to know the neighbor cluster's information (slot-allocation map). To achieve this goal, node b offers cooperation to node e, depicted in Figure 12(c). Node b includes the unreserved time slot(s) into a HELLO packet, $o(b)\not\subset T(b)$ . Upon receiving the b’ packet, node e checks $o(b)$ and its $T(e)$ . If there are two or more potential helper nodes, the collision may occur at the destination node. To avoid this collision, destination node will transmit a cooperation acknowledgement (C-ACK) and cluster cooperation acknowledgement (D-ACK) during selected unreserved time slot, as shown in Figure 13. A C-ACK packet is used between cluster members and D-ACK packet is used between CH and cluster member. In C-ACK and D-ACK, the destination node puts the ID of the first potential helper which offered cooperation to accept cooperation. Transmission of C-ACK and D-ACK from the destination node forces other potential helpers to suspend their transmissions, thus avoiding any possible collision. If it is satisfied, ( $o(b)\not\subset T(e)$ ), node e transmits C-ACK with two unavailable time slots. One time slot is for receiving cooperation and one time slot (i.e., $k\mathrm{t}\mathrm{h}\in o(b)$ ) is for retransmitting to reach its CH. When node h, a node e's cluster head, overhears this cooperation from node e, it receives d's CHP in time slot $k\mathrm{t}\mathrm{h}$ transmitted by node e, as shown in Figure 12(d). The scheme is depicted in Figure 12(e) and Figure 13 following the time slot. Once node CH h receives the d's CHP, node h will re-assign time slot of cluster member to avoid collision when two clusters move into each other's cluster's transmission range. Finally, the nodes using the same time slot in intersection area of two clusters do not collide, as shown in Figure 12(f).

In the other scenario, if node CH x uses the same time slot with CH y, node x switches to a free time of 2 time slots allocated for transmitting CHP. Based on this condition, CH of 3-hop neighbor set can reuse 2 time slots for transmitting CHP, as shown in Figure 11. If node x’ CM uses same time slot with node y’ CM, node x will assign a new time slot and include its into CHP to broadcast. Once CMs receive CHP transmitted by its CH, CMs will update its cluster information and whether or not to change CH's time slot.

Figure 11

Reusing time slots of cluster heads in a TDMA frame.

Figure 12

Information exchange in the ECCT.

Figure 13

Information exchange in the ECCT follows time slots.

6. Numerical and Simulation Results

The parameters are listed in Table 1. See [19] for details and general description of the IEEE 802.11 MAC protocol; each node transmits with probability τ:

$$\begin{array}{cc}& \tau =\frac{\mathrm{2}}{CW+\mathrm{1}}.\end{array}$$

(1)

Let $P_{\mathrm{t}\mathrm{r}}$ be the probability that there is at least one transmission in the considered slot time:

$$\begin{array}{cc}& P_{\mathrm{t}\mathrm{r}}=\mathrm{1}-{\left(\mathrm{1}-\tau \right)}^K.\end{array}$$

(2)

The probability, $P_s$ , that a transmission occurring on the channel is successful is given by the probability that exactly one node transmits on the channel, with the condition of the fact that at least one node transmits:

$$\begin{array}{cc}& P_s=\frac{K\tau {\left(\mathrm{1}-\tau \right)}^{K-\mathrm{1}}}{P_{\mathrm{t}\mathrm{r}}}=\frac{K\tau {\left(\mathrm{1}-\tau \right)}^{K-\mathrm{1}}}{\mathrm{1}-{\left(\mathrm{1}-\tau \right)}^K}.\end{array}$$

(3)

Table 1

Simulation parameters.

Parameter	Meaning
t	Number of TDMA frames
n	Number of slots in a TDMA frame
K	Number of nodes on cluster
$${\text{PERM}}_c^d$$	The permutation of selecting d from c
$$L_{\text{CHP}}$$	CHP size of cluster
R	Transmission bit rate (Mbps)
$$T_s$$	Duration of a slot

The scheme of the lowest-ID algorithm is depicted in Figure 17. In the first state, we have K nodes attempting to be a cluster head. In the first time slot, one node transmits a HELLO packet. Upon receiving this packet, K nodes are divided into two sets: $K_a$ and $K_b$ ( $K_a$ : lower set; $K_b$ : greater set). In time slot $i\mathrm{t}\mathrm{h}$ , the lowest-ID node transmits a HELLO packet. After this time slot, no node transmits a HELLO packet in the $(i+1)\mathrm{t}\mathrm{h}$ time slot. The lowest-ID node will broadcast CHP packet in the $(i+2)\mathrm{t}\mathrm{h}$ time slot. Based on this figure, we can calculate the average time $E[X]$ slots required for the electing a CH. Note that an extra slot is added to the average, since our scheme has one slot for guarding time slot.

Theorem 1.

The average time $E[X]$ slots required for the electing a CH are

$$\begin{array}{cc}& \frac{K}{P_s}\le E\left[X\right]\le \frac{\mathrm{1}}{P_s}{\displaystyle \sum }_{j=\mathrm{0}}^{K-\mathrm{1}}\left(K-j\right).\end{array}$$

(4)

Proof.

Let $P_i$ be the probability that a node in the lower set $K_{a_i}$ transmits successfully on the channel in $i\mathrm{t}\mathrm{h}$ time slot, defined as $P_i$ = P[exactly node a transmits on the channel $\hspace{0.17em}|\hspace{0.17em}$ node a is chosen] · P[node a is chosen]. Since the node transmitting on the channel is independent from the chosen node, we have $P_i$ = P[exactly node a transmits on the channel] · P[node a is chosen] as

$$\begin{array}{cc}& P_i=\frac{\mathrm{1}}{K_{a_i}}{P}_s,\end{array}$$

(5)

where $K_{a_i}$ is depicted in Figure 17. Let x be the time slots in which CH is successfully elected. The election of CH fails for the first $x-\mathrm{1}$ time slots and finally succeeds at the $x\mathrm{t}\mathrm{h}$ time slot

$$\begin{array}{cc}& P_x=\frac{\mathrm{1}}{K_{a_x}}{P}_s.\end{array}$$

(6)

We have the average time $E[X]$ slots required for electing a CH as

$$\begin{array}{cc}& E\left[X\right]=E\left[t_{\mathrm{1}}+t_{\mathrm{2}}+\cdots +t_m\right]+\mathrm{1}\\ =E\left[t_{\mathrm{1}}\right]+E\left[t_{\mathrm{2}}\right]+\cdots +E\left[t_m\right]+\mathrm{1},\end{array}$$

(7)

where $t_{\mathrm{1}},t_{\mathrm{2}},\dots ,t_m$ are the number of time slots required for 1st, 2nd to mth nodes. Lowest-ID node a is mth node, as shown in Figure 14. The probability density function of $P_{\mathrm{1}}$ can be expressed as

$$\begin{array}{cc}& f_{\mathrm{1}}\left(x\right)={\left(\mathrm{1}-P_{\mathrm{1}}\right)}^{t_{\mathrm{1}}-\mathrm{1}}{P}_{\mathrm{1}},\end{array}$$

(8)

where $P_{\mathrm{1}}$ is the probability of successful transmission of the first node. The average time $E[t_{\mathrm{1}}]$ slots required for transmission of the first node can compute as

$$\begin{array}{cc}& E\left[t_{\mathrm{1}}\right]={\displaystyle \sum }_{t_{\mathrm{1}}=\mathrm{1}}^{\infty }x{f}_{\mathrm{1}}\left(x\right)=\frac{\mathrm{1}}{P_{\mathrm{1}}}.\end{array}$$

(9)

Similar to $t_{\mathrm{1}}$ , we can compute $E[X]$ as

$$\begin{array}{cc}& E\left[X\right]=\frac{\mathrm{1}}{P_{\mathrm{1}}}+\frac{\mathrm{1}}{P_{\mathrm{2}}}+\cdots +\frac{\mathrm{1}}{P_m}+\mathrm{1}={\displaystyle \sum }_{i=\mathrm{0}}^m\frac{\mathrm{1}}{P_i}+\mathrm{1},\\ E\left[X\right]={\displaystyle \sum }_{i=\mathrm{1}}^m{P}_i+\mathrm{1}={\displaystyle \sum }_{i=\mathrm{1}}^m\frac{K_{a_i}}{P_s}+\mathrm{1}=\frac{\mathrm{1}}{P_s}{\displaystyle \sum }_{i=\mathrm{1}}^m{K}_{a_i}+\mathrm{1}.\end{array}$$

(10)

From (10), based on the value m, we have another value of $E[X]$ . If a lowest-ID node transmits HELLO packet in the interval $t_1$ , we have $E[X{]}_{\mathrm{m}\mathrm{i}\mathrm{n}}=K/P_s$ . In the worst case, each time slot a highest-ID node in the lower set transmits HELLO packet, a lowest-ID node transmits HELLO packet after K times. In this case, we have $E[X{]}_{\mathrm{m}\mathrm{a}\mathrm{x}}={\sum }_{j=\mathrm{0}}^{K-\mathrm{1}}(K-j)/P_s$ . For example, in Figure 15, we have 4 nodes to electing a CH. We can compute $E[X{]}_{\mathrm{m}\mathrm{i}\mathrm{n}}=\mathrm{4}/P_s$ and $E[X{]}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{10}/P_s$ . With a variable of K nodes, we have a set of average number of time slots for electing a CH, depicted in Figure 16.

Figure 14

The time slots required for electing a CH.

Figure 15

A tree diagram of 4 nodes.

Figure 16

A set of average number of time slots for electing a CH.

Figure 17

The schedule of the lowest-ID algorithm.

After CH is elected, CMs will assign their time slots to transmit data. To calculate the average number of time slots required for the successful BR, we take an average number of $E[X]$ , as $E[X]=(E[X{]}_{\mathrm{m}\mathrm{i}\mathrm{n}}+E[X{]}_{\mathrm{m}\mathrm{a}\mathrm{x}})/\mathrm{2}$ . In the first frame, it requires $E[x]$ time slots to elect a CH; there remain $(n-⌈E[x]⌉)$ time slots for bandwidth request. For $(K-\mathrm{1})$ CMs, there is a total of $(n-⌈E[x]⌉{)}^{K-\mathrm{1}}$ different combination. There are ${\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{M}}_{K-\mathrm{1}}^{(n-⌈E[x]⌉)}$ cases for all the $(K-\mathrm{1})Ns$ to achieve successful bandwidth in the first TDMA frame. Let $N_{\mathrm{F}\mathrm{B}\mathrm{R}}^i$ be the average number of failed bandwidths which can be expressed as

$$\begin{array}{l}{N}_{\mathrm{F}\mathrm{B}\mathrm{R}}^i\\ =\left\{\begin{array}{ll}\left(K-\mathrm{1}\right)-{\displaystyle \sum }_{j=\mathrm{1}}^{K-\mathrm{1}}\frac{{\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{M}}_j^{\left(n-⌈E\left[x\right]⌉\right)}}{{\left(n-⌈E\left[x\right]⌉\right)}^j};\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}n=\mathrm{2},\hfill \\ N_{\mathrm{F}\mathrm{B}\mathrm{R}}^{i-\mathrm{1}}-{\displaystyle \sum }_{j=\mathrm{1}}^{N_{\mathrm{F}\mathrm{B}\mathrm{R}}^{i-\mathrm{1}}}\frac{{\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{M}}_j^n}{n^j};\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}n=\mathrm{3,4}\dots ,t.\hfill \end{array}\right.\end{array}$$

(11)

Thus, we can compute the probability of successful BR issued from $(K-\mathrm{1})$ CMs by using the ith TDMA frame, denoted by $P_{\mathrm{B}\mathrm{R}}^i$ :

$$\begin{array}{cc}& P_{\mathrm{B}\mathrm{R}}^i=\left\{\begin{array}{cc}\frac{{\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{M}}_{K-\mathrm{1}}^{\left(n-⌈E\left[x\right]⌉\right)}}{{\left(n-⌈E\left[x\right]⌉\right)}^{K-\mathrm{1}}}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}n=\mathrm{1},\hfill \\ \frac{{\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{M}}_{N_{\mathrm{F}\mathrm{B}\mathrm{R}}^i}^n}{n^{N_{\mathrm{F}\mathrm{B}\mathrm{R}}^i}}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}n=\mathrm{2,3},\dots ,t.\hfill \end{array}\right.\end{array}$$

(12)

Let $E[y]$ be the average number of time slots required for the successful BR. Derive (12); we can compute as

$$\begin{array}{ll}E\left[y\right]& =P_{\mathrm{B}\mathrm{R}}^{\mathrm{1}}\left(n-⌈E\left[x\right]⌉\right)\\ & +\left({\displaystyle \sum }_{i=\mathrm{2}}^t\left(i\ast P_{\mathrm{B}\mathrm{R}}^i\coprod _{j=\mathrm{1}}^{i-\mathrm{1}}\left(\mathrm{1}-P_{\mathrm{B}\mathrm{R}}^j\right)\right)\right)\ast n.\end{array}$$

(13)

After BR request, the CH must broadcast CHP packet to inform toward its CMs. Referring to Figure 7, we can calculate the number of slots required for CH in a cluster to broadcast CHP packet and denote $S_{\mathrm{S}\mathrm{A}\mathrm{M}}$ as

$$\begin{array}{cc}& S_{\mathrm{S}\mathrm{A}\mathrm{M}}=\frac{\left(\mathrm{63}\ast K+\mathrm{32}\right)/R}{T_s}=\frac{\mathrm{56}\ast K+\mathrm{32}}{T_s\ast R}.\end{array}$$

(14)

After CH broadcasts CHP packet, a CM can deliver its data over the designated time slots. It can transmit single slot or multislots. Let $E[z]$ be the average number of time slots required for the waiting before a CM can begin to transmit its data. We can derive it from

$$\begin{array}{cc}& E\left[z\right]=\left\{\begin{array}{cc}\frac{{\sum }_{t=\mathrm{0}}^K\hspace{0.17em}\hspace{0.17em}}{K}=\frac{K-\mathrm{1}}{\mathrm{2}};\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\mathrm{u}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}\hspace{0.17em}\hspace{0.17em}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{e}\text{-}\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{t},\hfill \\ \frac{\left(\left(\mathrm{1}+N_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}\right)/\mathrm{2}\right){\sum }_{t=\mathrm{0}}^K\hspace{0.17em}\hspace{0.17em}}{K}=\frac{\left(\mathrm{1}+N_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}\right)\left(K-\mathrm{1}\right)}{\mathrm{4}};\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\mathrm{u}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{g}\hspace{0.17em}\hspace{0.17em}\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\text{-}\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{t},\hfill \end{array}\right.\end{array}$$

(15)

where $N_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}$ is maximum number of requested time slots of a CM. Eventually, we can compute the average number of time slots counting the time electing a CH to the time when a node is ready to transmit its data from

$$\begin{array}{cc}& S=E\left[X\right]+E\left[y\right]+S_{\mathrm{S}\mathrm{A}\mathrm{M}}+E\left[z\right].\end{array}$$

(16)

To evaluate our proposal and CBT in [8], we use MATLAB to compute and simulate the average number of time slots for electing a CH, the average number of time slots required for BR, and average number of time slots counting the time electing a CH to the time when a node is ready to transmit its data. We ran the simulation 100 times to obtain the mean value of the final performance metric. We choose R = 18 Mbps, which is one of the rates supported by the IEEE 802.11p OFDM physical layer for the 5 Ghz, $T_s$ = 0.35 ms [20]. We change the number of CMs in a cluster from 2 to 10. When the number of CMs in a cluster equals 2, 4, and 6, the average number of time slots for electing a CH in both systems is the same. But when the number of CMs increases, our proposal requires time slots less than CBT and IEEE 802.11p. At 10-sized CMs in a cluster, our proposal about 12 time slots and CBT requires 103 time slots, as shown in Figure 18. We observe that the simulation result of our proposal belongs to interval $[E[x{]}_{\mathrm{m}\mathrm{i}\mathrm{n}}$ ; $E[x{]}_{\mathrm{m}\mathrm{a}\mathrm{x}}]$ and set of average number of time slots for electing CH is lower than IEEE 802.11p.

Figure 18

Average number of time slots for electing a CH.

When the number of CMs in a cluster equals 2, 4, and 6, both our proposal and CBT are the same time slots required to assign BR. But when the number of CMs increases, our proposal requires time slots less than CBT, as shown in Figure 19. Because the average number of time slots for electing a CH in our proposal is less, the number of free time slots remains more in the first frame and CMs can assign BR in the first frame more than CBT.

Figure 19

Average number of time slots for bandwidth request.

We can compute the average number of time slots counting the time electing a CH to the time when a node is ready to transmit its data. When the number of CMs in the cluster increases, the total number of time slots also increases. As shown in Figure 20, the total number of time slots in our proposal is less than that in CBT for different cluster sizes. Our proposed scheme elects a CH faster, and thus there are more free time slots remaining in the first frame. Therefore, the CMs can assign BR faster than CBT to transmit data.

Figure 20

Total number of time slots required before data transmissions.

7. Conclusion

In this paper, a novel algorithm to elect a CH for cluster-based TDMA system in VANET is proposed. By using the lowest-ID algorithm, not only the average number of time slots for electing a cluster head but also total number of time slots before data can be successfully transmitted is less than the existing cluster-based TDMA system and IEEE 802.11p. For intercluster communication, we use cooperation ADHOC MAC for VANETs to avoid collision when two clusters move into each other's transmission range. The cluster head knows a neighbor cluster's information and reassigns cluster members’ time slots before two clusters intersect together. If two or more nodes in boundary of two clusters transmission ranges use the same time slot, the broadcast safety application packets transmitted from a cluster do not reach to another cluster because the collision takes place. As the future work, we are going to extend our proposal by considering variable speed models and enhance our current work to help the node in the boundary of two clusters transmission ranges to avoid the collision when they use the same time slot.