Stable Clustering Algorithm for Routing Establishment in Vehicular Ad-Hoc Networks

Abstract

With regard to the complex and varied urban scenes in Vehicular Ad-Hoc Network, such as the vehicle nodes with fast speed, unstable links and frequent changes in network topology, this paper proposed a stable clustering algorithm to establish routing for VANET. In this algorithm, clustering was first formed according to the Similar Neighbor Node Table. Then on the basis of the Highest Connectivity Algorithm, parameters such as position and speed of the node were introduced to calculate the Selection Priority which were used to produce the preferred and the alternative cluster head node. The introduction of alternative cluster head nodes improved the stability of clustering to a certain extent. Finally, the clustering was established and maintained for six special scenarios. Compared with the traditional clustering algorithm in VANET, it had the characteristics of lower end-to-end delay, higher packet delivery rate and lower change rate of preferred cluster head nodes, which greatly improved the communication quality of VANET.

1 Introduction

People increasingly place their hope of alleviating or even completely solving traffic problems on intelligent transportation system and vehicle self-organizing network technology [1]. The Vehicular Ad-hoc Networks (VANET) builds a centerless, multi-hop, self-organizing mobile communication network with many nodes [2, 3]. And clustering algorithm is the key content that determines the performance of the VANET [4].

However, at present, there is no clear standard for the routing protocol or clustering algorithm in VANET industry. The clustering algorithm in VANET usually draws lessons from the clustering algorithm in the Mobile Ad-hoc Network (MANET). The representative algorithms are: Minimum ID Algorithm (ID-Lowest) [5], Highest Connectivity Algorithm (HC) [6], WCA [7], AOW [8], ALM [9] and so on. The advantages of ID-Lowest are as follows: the implementation process is simple and convenient; the change rate of cluster head nodes is low. However, its shortcomings are also obvious: because only the minimum ID is considered as the cluster head, it will be unfair and unstable, and there is no good maintenance mechanism to manage clustering. The HC [6] is similar to ID-Lowest. The disadvantage of HC is that if there is no limit on the number of members in the cluster, it can be a lot. If the number of clusters becomes smaller, then the channel utilization will become very low, the throughput will decrease rapidly.

Although VANET and MANET have some similarities, there are still some differences between VANET in traffic roads. In this paper, according to the characteristics of urban traffic conditions, and its research and analysis, a stable clustering algorithm is designed, which is more suitable for VANET. Compared with HC, ID-Lowest and other clustering algorithms, it has smaller preferred cluster head node change rate and more lasting preferred cluster head node maintenance time, which improves the packet delivery rate, reduces the topology change rate, and can reduce the network transmission delay. The packet delivery rate is improved, which greatly improves the communication quality in the VANET.

2 Scenario of the Stable Clustering Algorithm

As shown in Fig. 1, in a road section with three lanes, a cluster was formed because vehicles a, b and c were close, and their average speed was similar. Because the speed of vehicle h was fast, even if it was added to the cluster, it would get out of the cluster quickly, so the vehicle h was excluded from the cluster. Similarly, vehicles d, e, f and g formed a cluster. Because the average speed of i was slow, it was also excluded from cluster. Vehicle i needed to find other vehicles to form a cluster. Based on this clustering idea, it designs a stable clustering algorithm, which can effectively reduce the network size in the urban scene, reduce the change rate of network topology, and improve the communication quality of the network.

Fig. 1.

The cluster of vehicles in local road sections

3 Mechanism of the Stable Clustering Algorithm

In this stable clustering algorithm, it is assumed that all vehicle nodes in the VANET can get the following information:

• The direction, speed, the longitude and latitude of the location and other information of the vehicle by related devices, such as GPS, on-board sensor devices, etc.

• The HELLO messages used to maintain the topology of the network from the vehicle nodes in their communication range.

• The Beacon message within limited number of hops which includes vehicle ID, position, direction, speed and speed standard deviation, etc.

3.1 Clustering for the Similar Neighbor Nodes

In the range of communication between vehicular nodes, the neighbor vehicle nodes obtain each other’s basic information through Beacon message. Only the vehicle nodes whose driving speed is within a certain confidence interval are selected to form a similar cluster of neighbor vehicle nodes. The traffic roads in the city will be quite straight and regular. In order to facilitate analysis, only the vehicles driving in the same direction are selected to form a cluster. It is defined that vehicle node m has the following related parameters:

• ${\text{j}}$: the number of neighbor vehicle nodes of the vehicle node m;

• $\Delta T$: the sampling period of obtaining the speed of the vehicle node;

• $v_{m} \left( t \right)$, $\sigma_{m}^{v}$: the speed at a certain t time and the standard deviation of speed;

• $\bar{v}_{m}$: the average speed over the periodic sampling interval;

• $\sigma_{max}^{v}$: the maximum standard deviation of speed in neighbor nodes;

• $V_{min}^{mj}$, $V_{max}^{mj}$: the minimum and maximum driving speed of vehicle nodes;

• $\mu$: the adjustable coefficient of the size of the speed range.

The vehicle node m records its speed in the time interval $\Delta T$. Calculate the average speed and the standard deviation of the vehicle node m:

$$ \bar{v}_{m} = \frac{1}{\Delta T}\mathop \sum \nolimits_{t = 0}^{\Delta T} v_{m} \left( t \right) $$

(1)

$$ \upsigma_{m}^{v} = \sqrt {\frac{1}{\Delta T}\mathop \sum \nolimits_{t = 0}^{\Delta T} \left( {v_{m} \left( t \right) - \bar{v}_{m} } \right)^{2} } $$

(2)

Since it is assumed that the number of neighbor vehicle nodes of the vehicle node m is j, the vehicle node m needs to find a maximum speed standard deviation among the (j + 1) vehicle nodes. Calculate the maximum speed standard deviation:

$$ \sigma_{max}^{v} = max\left\{ {\sigma_{m}^{v} ,\sigma_{k}^{v} |k = 1, 2, \ldots , j} \right\} $$

(3)

The confidence interval is used to exclude a few vehicle nodes whose speed is very different from that of most vehicle nodes. On the basis of (3), an adjustable coefficient μ is introduced, and the minimum and the maximum speed of vehicle nodes in the confidence interval of Gaussian Mixture Model can be obtained:

$$ V_{min}^{mj} = \bar{v}_{m} - \mu \sigma_{max}^{v} $$

(4)

$$ V_{max}^{mj} = \bar{v}_{m} + \mu \sigma_{max}^{v} $$

(5)

The value of μ can be adjusted according to the average speed of the vehicle and the actual traffic environment. From the properties of the Model, the range of the confidence interval and the value of the adjustable coefficient μ can be obtained (Fig. 2):

Fig. 2.

The confidence probability of Gaussian Mixture Model

$$ \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} {P\left\{ {\left| {X - \bar{v}_{m} } \right| < c} \right\} = 2\varPhi \left( {\frac{c}{\sigma }} \right) - 1 } \\ {P\left\{ {\left| {X - \bar{v}_{m} } \right| < 2.58\mu } \right\} = 2\varPhi \left( {\frac{2.58\mu }{\sigma }} \right) - 1 \approx 99\% } \\ \end{array} } \\ {\begin{array}{*{20}c} {P\left\{ {\left| {X - \bar{v}_{m} } \right| < 1.96\mu } \right\} = 2\varPhi \left( {\frac{1.96\mu }{\sigma }} \right) - 1 \approx 95\% } \\ {P\left\{ {\left| {X - \bar{v}_{m} } \right| < 1.64\mu } \right\} = 2\varPhi \left( {\frac{1.64\mu }{\sigma }} \right) - 1 \approx 90\% } \\ \end{array} } \\ \end{array} } \right. $$

(6)

It can be obtained from (6) that some special nodes can be excluded by selecting the appropriate confidence interval. After the confidence interval is set, all the vehicle nodes that satisfy the driving speed in the interval $V_{min}^{mj} \le V_{j}^{mj} \le V_{max}^{mj}$ are formed into a new set in the neighbor table. Then a similar neighbor node table (SNNT) is created to store and record the information of all vehicle nodes in this collection.

3.2 Selection of Preferred Cluster Head Node

The parameters such as the number of neighbor vehicle nodes, speed and position spacing are modeled as a Gaussian Mixture Model. When the number of neighbor vehicle nodes is larger and the driving speed and vehicle position spacing are closer to the average value of the overall vehicle nodes in the table, the greater the selection priority (SP), the greater the probability that the vehicle node will become the preferred cluster head. It is defined that vehicle node m has the following related parameters:

• $h$, $v_{m}$: the number of vehicle nodes in SNNT and the speed of the vehicle node m;

• $v_{n}$: the speed of each vehicle node in the SNNT, n = 1, 2, …, h;

• $\bar{v}_{mean}$: the average speed of vehicle nodes in SNNT;

• $x_{m}$, $y_{m}$: the position parameter of the vehicle node m;

• $x_{n}$, $y_{n}$: the location parameters of each vehicle node in SNNT.

• $P_{n}$, $\bar{P}_{mean}$: the Euclidean distance and the average Euclidean distance between m and the vehicle nodes in the SNNT;

• $\sigma_{v}$, $\sigma_{p}$: the standard deviation of the speed and the Euclidean distance P in SNNT;

• ${N}_{v} {,N}_{p}$ : the normalization of the speed and the Euclidean distance P;

• $SP$: the selection priority of the preferred cluster head node.

Calculate the average speed of vehicle nodes, the Euclidean distance and the average of Euclidean distance between m and the vehicle nodes in its SNNT:

$$ \bar{v}_{mean} = \frac{1}{h}\mathop \sum \nolimits_{n = 1}^{h} v_{n} $$

(7)

$$ P_{n} = \arccos \left( {\left( {\sin \left( {Lat_{m} ){ \sin }(Lat_{n} } \right)} \right) + \left( {\cos \left( {Lat_{m} } \right)\cos \left( {Lat_{n} } \right)\cos \left( {Lng_{m} - Lng_{n} } \right)} \right)} \right) *R $$

(8)

$$ \bar{P}_{mean} = \frac{1}{h}\mathop \sum \nolimits_{n = 1}^{h} P_{n} $$

(9)

In (8), Lng and Lat represent longitude and latitude, respectively. By using the Z-score standardization method, it is necessary to calculate the standard deviation of speed and Euclidean distance of vehicle nodes in SNNT:

$$ \sigma_{v} = \sqrt {\frac{1}{h}\mathop \sum \nolimits_{n = 1}^{h} \left( {v_{n} - \bar{v}_{mean} } \right)^{2} } $$

(10)

$$ \sigma_{p} = \sqrt {\frac{1}{h}\mathop \sum \nolimits_{n = 1}^{h} \left( {P_{n} - \bar{P}_{mean} } \right)^{2} } $$

(11)

Then, the normalization of speed and Euclidean distance can be calculated:

$$ N_{v} = \left( {v_{m} - \bar{v}_{mean} } \right)/\sigma_{v} $$

(12)

$$ N_{p} = \left( {P_{n} - \bar{P}_{mean} } \right)/\sigma_{p} $$

(13)

Finally, the selection priority of m is calculated:

$$ SP = \frac{h}{{e^{{\left( {\left| {N_{v} } \right| + \left| {N_{p} } \right|} \right)}} }} = \frac{h}{{e^{{\left( {\left| {\frac{{v_{m} - \bar{v}_{mean} }}{{\sigma_{v} }}} \right| + \left| {\frac{{P_{n} - \bar{P}_{mean} }}{{\sigma_{p} }}} \right|} \right)}} }} $$

(14)

3.3 Selection of Alternative Cluster Head Node

After the cluster is formed, the most suitable cluster member should be selected as the alternative cluster head node, which makes the cluster structure more stable during the period of maintenance. It is defined that vehicle node m has the following related parameters:

• ${H}_{n}$, $N$: the Nth cluster and the number of member nodes in the cluster;

• $\phi_{p}$: a set of neighbor vehicle nodes of a member node in a cluster;

• $\mu_{i}$, $\theta_{i}$: the ID of member node in cluster, i is a sort index in the range of 1 – N;

• $C\left( {\mu_{i} } \right)$: the coverage cardinality of member nodes in a cluster;

• $\eta \left( {\theta_{i} } \right)$, $p$: the SP of member nodes in a cluster and a member node in the cluster.

The coverage cardinality (CC) represents the number of same nodes in the cluster as the neighbor vehicle nodes of a member node p:

$$ CC_{p } = \left\{ {\left| {{H}_{n} \cap \phi_{p} } \right|,\;\;\forall p \in {H}_{n} } \right\} $$

(15)

Define a set $\Phi _{{I_{C} }}$, which consists of the $C\left( {\mu_{i} } \right)$ of all the member nodes in the cluster ${H}_{n}$, with a total of N member nodes:

$$ \Phi _{{I_{C} }} = \left\{ {C\left( {\mu_{1} } \right), C\left( {\mu_{2} } \right), C\left( {\mu_{3} } \right), \ldots , C\left( {\mu_{N} } \right)} \right\} $$

(16)

The ID $\mu_{i}$ of all the member nodes in the cluster is sorted within the set $\Phi _{{I_{C} }}$. As i gets bigger and bigger, the CC $C\left( {\mu_{i} } \right)$ are sorted from large to small, corresponding to the ID $\mu_{i}$ of the member node. The sort set of the member node ID can be represented as:

$$ I_{C} = \left\{ {\mu_{1} , \mu_{2} , \mu_{3} , \ldots , \mu_{N} |C\left( {\mu_{k} } \right) \ge C\left( {\mu_{j} } \right), \forall k\; <\; j} \right\} $$

(17)

The ID $\theta_{i}$ of all the member nodes in the cluster are sorted in the set $\upeta\left( {\theta_{i} } \right)$. As i gets bigger and bigger, the SP of all the member nodes in the cluster ${H}_{n}$ are sorted from large to small. The sort set $I_{P}$ of the member node ID can be represented as:

$$ I_{P} = \left\{ {\theta_{1} , \theta_{2} , \theta_{3} , \ldots , \theta_{N} |\upeta\left( {\theta_{k} } \right) \ge\upeta\left( {\theta_{j} } \right), \forall k\; <\; j} \right\} $$

(18)

A new alternative cluster head node has to meet the following two conditions: the vehicle node with a larger CC $C\left( {\mu_{i} } \right)$ in (17), that is, the member node in the front of the set; the SP $\upeta\left( {\theta_{i} } \right)$ of the selected vehicle node is greater than a set threshold $\eta_{T}$. This threshold is selected in the set $I_{P}$ of (18) and satisfies the following formula:

$$ \eta_{T} = \eta \left( {\theta_{i} } \right)\quad i = 1, 2, \ldots , N $$

(19)

Therefore, a new alternative cluster head node is represented as follows:

$$ CH_{B} = \arg max\left\{ {\mu_{i} | \upeta\left( {\mu_{i} } \right) \ge \eta_{T} } \right\} $$

(20)

3.4 Maintenance of Neighbor Cluster

The maintenance of neighbor cluster is summarized into the following six scenarios, and targeted treatment is made to make the cluster stable.

• 1. The member nodes in the cluster are separated from the cluster: the ordinary member node in the cluster fails to receive HELLO message of the separated node, all the information of the node is deleted from its SNNT and the topology structure is updated. The separated node will clear the SNNT and change the state to the undetermined state, and regenerate the Beacon message to request to join other clusters.

• 2. The alternative cluster head node is separated from cluster: the member node in the cluster initiates the selection process of the alternative cluster head node and immediately selects a new alternative cluster head node.

• 3. The preferred cluster head node is separated from cluster: the alternative cluster head node immediately becomes the preferred cluster head node and manages all the members of the cluster. And then re-select an alternative cluster head node.

• 4. The merging of neighbor clusters: the two preferred cluster head nodes exchange information through Beacon messages, and then calculate the degree D of dissimilarity between the two nodes. When D is smaller than a certain threshold, the cluster merge is carried out.

  $$ {\text{D}} = \theta_{d} \frac{{\left| {d_{cb} } \right|}}{{d_{com} }} + \theta_{v} \frac{{\left| {v_{cb} } \right|}}{{v_{c} }} $$

  (21)

• 5. Adding the undetermined vehicle nodes to the cluster: when an undetermined vehicle node u is in the communication range of a cluster, u will send its Beacon message to the preferred cluster head node of the cluster. After receiving the message, the preferred cluster head node H calculates D, according to (21), between itself and u, and then decides whether to accept u or not.

• 6. Re-establishment of cluster: the preferred cluster head node needs to obtain the vehicle node information from the SNNT, and then calculates its SP according to the (14). Finally, according to the (22), it is decided whether the vehicle node continues to be the preferred cluster head node:

  $$ SP = \frac{h}{{e^{{\left( {\left| {\frac{{v_{m} - {\bar{\text{v}}}_{\text{mean}} }}{{\sigma_{v} }}} \right| + \left| {\frac{{P_{n} - \bar{P}_{mean} }}{{\sigma_{p} }}} \right|} \right)}} }} < \frac{\pi h}{{4e^{{\left( {\left| {\frac{1}{{\sigma_{v} }}} \right| + \left| {\frac{1}{{\sigma_{p} }}} \right|} \right)}} }} $$

  (22)

4 Simulation and Result Analysis

A routing protocol, the Stable Clustering-Based Routing Protocol in Vehicular Ad-Hoc Networks (SCBR), is proposed based on the stable clustering algorithm which is simulated and tested with the NS2 and the VanetMobiSim.

The driving speeds of vehicle nodes are 5, 10, 15, 20, 25 and 30 m/s, respectively. The number of vehicle nodes is set to 200. According to the simulation results, the influence of different vehicle node speed on the performance index is evaluated.

As shown in Fig. 3, when the number of vehicle nodes is the same, the speed of vehicle nodes has little effect on the end-to-end delay. The main factors affecting the end-to-end delay are the distribution and density of vehicle nodes, the average number of packets forwarding hops and the routing algorithm mechanism of the protocol. When a routing error occurs, the CBRP protocol can be repaired locally, so the end-to-end delay is lower than that of the AODV protocol. The stable clustering algorithm of SCBR protocol can improve the stability of communication link and clustering structure, and ensure that the data packet can reach the destination node successfully. Therefore, using the SCBR protocol, the driving speed of the vehicle node has the least effect on the end-to-end delay.

Fig. 3.

The effect of speed on end-to-end delay

As shown in Fig. 4, when the vehicle node speed increases, the packet delivery rate of AODV decreases the fastest, while the SCBR decreases more slowly, which is less affected by the vehicle node speed. The main reason is that even when the vehicle nodes are driving at high speed, as long as they can maintain relative stillness with the neighbor vehicle nodes, the cluster structure can be relatively stable and the vehicle nodes can communicate with each other normally. Compared with AODV and CBRP, SCBR has higher packet delivery rate, and its performance index is the best.

Fig. 4.

The effect of speed on packet delivery rate

5 Conclusion

SCBR protocol based on stable clustering algorithm proposed has good performance compared with other relative protocols in urban traffic roads. Clustering algorithm for suburban or high-speed environment could be further studied in the future so that the protocol could be applied to multiple environments simultaneously.