Destination Based Stable Clustering Algorithm and Routing for VANET

Affiliation(s)

School of Communication and Information Engineering, Chongqing University of Post and Telecommunication, Chongqing, China.

School of Communication and Information Engineering, Chongqing University of Post and Telecommunication, Chongqing, China.

Abstract

Now in modern telecommunication, one of the big topic research is a Vehicle Ad-hoc Network “VANET” (V2V). This topic is one of an “issues of the day” because research has problematic topic due to its many application-questions, what we need to solve: avoid collisions, any accidents on a way, and notifications about congestions on the road, available car parking, road-side commercial-business ads, and etcetera. These like application forms creating big delay constraining’s*i.e.* the instant data should reach the destination within certain time limits. Therefore, we need a really efficient stable clustering method and routing in vehicle ad-hoc network which will be resistant to network delays and meets network requirements. The methods are proposed in the paper for optimization VANETs data traffic as well as to minimizing delay. First, here is presented, a stable clustering algorithm based on the destination, contextually take into consideration various physical parameters for cluster formation such as location of the vehicle and its direction, vehicle speed and destination, as well as a possible list of interests of the vehicle. And also the next main process is to depend on these “five parameters” we can calculate the “Cluster Head Eligibility” of each car. Second, based on this “Cluster Head Eligibility”, described cluster head selection method. Third, for efficient communication between clusters, present a routing protocol based on the “destination”, which considered an efficient selecting method of next forwarding nodes, which is calculated by using “FE” metric.

Now in modern telecommunication, one of the big topic research is a Vehicle Ad-hoc Network “VANET” (V2V). This topic is one of an “issues of the day” because research has problematic topic due to its many application-questions, what we need to solve: avoid collisions, any accidents on a way, and notifications about congestions on the road, available car parking, road-side commercial-business ads, and etcetera. These like application forms creating big delay constraining’s

Keywords

VANET, Vehicle Ad-Hoc Network, Stable Clustering Algorithm, Destination Based Clustering, Efficient Routing

VANET, Vehicle Ad-Hoc Network, Stable Clustering Algorithm, Destination Based Clustering, Efficient Routing

1. Introduction to Research Work

Since MANET technology was originally taken on the basis of VANET technology, it does not meet some of the unaccounted network parameters that are necessary for VANET—such as topology flexibility and high network mobility, rather frequent disconnection of network or nodes from the network and delays due to geographical routing. The routing protocol in VANET must comply with the above important parameters in the network—be flexible and eliminate delays to minimize the total traffic in the network.

In order to solve these problems and to improve the previously proposed works.

In the paper, presented effective solutions for stable efficient communication between vehicles in VANET:

1) A stable clustering algorithm based on the destination, which contextually takes into consideration the important parameters, for formation of the cluster, such as: “location” and “destination” of the vehicle, the “direction” of the vehicle and the “speed” of the vehicle, in addition a possible list of interests of each vehicle [1]. Based on these key parameters necessary for clustering, we know that means the list of interests of each individual vehicles will unit (group) them in a cluster with similar interests, and this means that each member of the clusters will have supposedly similar common interests within the cluster, such as: interest in some information, about the presence of parking lots, accident notifications, information about traffic jams, etc. Accordingly, each cluster will have its own list of interests. When a cluster head (CH) receives a message from a connected new cluster member, it checks if other (vehicles) members in the cluster are interested in the message or not. If the vehicles have the same interests inside the cluster and they are interested, the cluster head will send a request (message) to the cluster members (CM). Otherwise, if there is no interest in the cluster, the message will be redirected to the next CH node without spreading the “unnecessary message” inside the “uninterested cluster” [2] [3]. This will prevent the irrelevant distribution of unnecessary information in the cluster and network, which is very important.

2) Then, for these clusters which are formed on the basis of “five” parameters, a description of the efficient improved routing protocol based on the destination is proposed to improve communication between the clusters in the VANET network. In the clustering, the destinations of vehicles in the formation of the cluster are of particular importance. As a result, we know that “each cluster” must have some kind of destination specific to this particular cluster, which is determined from the destinations of the members of this cluster (the destinations of each vehicle are in the cluster). If a cluster head wants to forward a message, it needs to select the most suitable cluster heads near it in order to forward the message further. The cluster head, when will select the head of neighbor clusters (next node) suitable for it, takes into consideration such characteristics as the possible direction of the neighbor cluster heads, and their possible destination. When a message arrives at the cluster head, it will calculate the direction of transmission (DT) from the positional coordinates of the incoming message and then accordingly will know the possible target location (TL) of the message sender CH. After, should using the “cosine similarity” formula, it calculates the transmission directions of the received message and checks for similarities with the directions of the neighbor cluster heads located nearby. About this in detail in 4th part of this work. In exactly the same way still check target location of a messages with the destination addresses of neighbor CH. The head of a neighbor cluster which has similar direction to the direction of transmission of the message, and which position to destination is nearby to the target location of the message is selected to transfer the message, to the desired addressee of the message. To select the next node for forward massages is enough to perform by calculating the FE (Forward Eligibility) metric. The nearest node whose FE metric result is maximum should be chosen as the next possible forwarding node.

3) To test cluster stability and routing efficiency, a simulation was done. In simulation work, taking into consideration the modeling process, technical factors such as delivery ratio, delivery delay, loss-percentages, etc. The results are compared with a known method like cluster-based routing scheme (CBR) and a traditional broadcasting scheme. And the simulation results show significantly good results in terms of routing stability due to better cluster stability. And its efficient work when choosing the next forwarding nodes is improved by computing FE metric. Simulation results and analysis of the results presented in Section 5.

The following parts of my work are as follows. In the next section give examples of the many previously proposed routing methods in VANET. In Chapter 2, the principles of the cluster and basic parameters of clustering. In Chapter 3, the process of selecting a cluster head by calculating CH “eligibility”. Chapter 4 provides a description of the proposed routing for the based on “FE metric” which depend at “five parameters” forming stable cluster. Chapter 5 provides analysis of the test results. In conclusion, a summary in Chapter 6.

Relative Works

The following are examples of the most common routing methods for VANET from previously proposed works that were considered in this work:

1) Diagonal dynamic Intersection Routing (DIR)—Here a protocol that is made on a geographical basis. Here in DIR routing is done through a series of diagonal intersections that are constructed between the source and destination [4]. The sending node sends data packets one by one to the first intersection, then to the second intersection, and so on until the last intersection until it is forwarded to the target location. There can be many sub-paths between diagonal intersections for optimal message forwarding, therefore a sub-path with a minimum delay is selected here.

2) Cluster-Based Routing (CBR)—selects the optimal route based on its current location, destination location, and the maximum of the minimum average throughput of SCSR. But transmitting node, without detecting the route, just consider life time, forwards the message to the neighboring cluster node whose geographical position has a minimum angle with the destination of the data packet when it sends the message to the target location, and this process is repeated periodically until the TL receives the message [5].

3) Cluster Head based Routing Protocol (CHBRP)—Cluster stability and maintaining it, is an important goal that clustering algorithms try to achieve and it is considered as a measure of performance of a clustering algorithm, further selecting the proper cluster head is crucial to maintain the stability of the clustered network. To achieve, this paper proposes a combination of bully algorithm and Lamport timestamp for selecting the better cluster head and also for Cluster head switching in an efficient way for better performance in the stability of VANET nodes [6]. But is not consider (effective) selecting moment of next forward nodes.

4) Position-based Routing (GPSR)—is a position based routing method was introduced. This GPSR implies that each vehicle knows its position using the global positioning system (GPS) and it selects the optimal node among its neighbors when the node “k” wants to forward the message. The choice of the optimal neighboring node is based on the target location of the message and the positions of neighboring nodes “k”. To transfer the message, the next node “k” with the smallest distance from the target location is selected as the next optimal node. Or he sends a message around the perimeter of the region if the GPSR adheres to a local minimum [7].

5) Cluster-based Directional routing (CDR): In cluster-based directional routing and in most of routing methods a sending node forwards the message to the neighboring cluster head, which direction of message transmission is similar to the direction of movement of the neighbor cluster head [8]. That is, using their position coordinates and the target location of the message, the node combs the direction of transmission of the message.

The above GPSR and CBR and similar routing methods are not effective because they have disadvantages such as not taking into account the direction of neighboring nodes when choosing the optimal next forwarding nodes for message transfer, and not having a suitable cluster that can be an effective solution, this is impossible. And cluster-based directional routing does not take into account an important parameter as the destination of neighboring nodes when choosing the next forwarding node. Since the destination in the DIR was not taken into account when forming the cluster, it creates additional delays when making decisions in the routing process. Taking into account all these shortcomings, which may adversely affect the efficiency of the routing process, an algorithm based on the destination is proposed.

2. Based on the “Five Parameters” a Stable Cluster

In this version of clustering, which is based on five contextually take into consideration parameters (Figure 1), the formation of a cluster i.e. the combination of vehicles to creating communication groups, comes from such parameters as:

1) The location. With the help of location-aware devices, each vehicle must give its own position at the moment or at a certain point in time on the road,

Figure 1. Cluster parameters.

and this is easily solved by using technology that we know of as a global positioning system. Next, each vehicle must also have an on-board unit (OBU) that determines its current location when receiving a signal from a GPS device. In order for vehicles located next to each other to group together and create a cluster, a minimum distance between them is required, therefore, the location of the vehicle is defined as paired values as “Location_{x}” and “Location_{y}” (Chapter 3).

2) The direction. The ability to accurately determine the directions of vehicles is given to us by means of data from a GPS device. According to the differences of the last two coordinates, we identify a possible direction. It will be presented in form as (Direction_{v}). For the possible formation of a cluster of vehicles, they should have approximately the same direction. If the direction of the cluster members more similar, it’s mean life-time of the cluster going to be longer and it’s the more stable cluster.

3) The speed. Vehicle speed is easily detected by the on-board unit installed in the vehicle. Below will be presented as (Speed v). For vehicles forming or already in the same cluster, members of this cluster must have a minimum speed difference. It also affects the dynamic stability of the cluster and nodes.

4) Destination. With the help of location-aware devices, each vehicle must give its own position at the moment or at a certain point in time on the road, and this is easily solved by using technology that we know of as a global positioning system and presented in the form (Destination_{x}, Destination_{y}). Here we need two ways to determine the destination of the vehicle, the first is the final destination (FD) of each vehicle, which is determined by GPS. And the second, the relative destination (RD), which is determined relative to some reference point, that is, the point that along the way most of the vehicles from the group. Based on this, we can conclude that this will be the common point of the group and we can call it the relative destination of the “stable cluster”. Therefore, the probability that a group of vehicles or perhaps a cluster will reach this point is very high. Vehicles that are in the neighborhood at the time of the organization of the possible cluster and in order for them to become numb in the group, it is enough that their destinations are close in distance between their destinations or routes along the path to a relative destination.

5) List of interests. Each vehicle has its own interests (Figure 2) depending on the interests and wishes of the drivers of the transport system and passengers [1]. Interests may differ as interests about the availability of nearby places like gas stations, parking spaces, cafes and restaurants. And some vehicles can only have interests about car traffic jams and accidents on road etc. The list of interests can be installed (loaded) into the on-board unit of the vehicle and can be in the form of a specific table that includes special “combinations of constant digits” which can be selected or excluded from the list. Having such an opportunity greatly simplifies the task of clustering.

I use a vector to represent the interests of the vehicle and “K” the vector of interests of each vehicle [1] [9] in the form:

$P{K}_{I}=\left(P{K}_{1},P{K}_{2},P{K}_{3},\cdots ,P{K}_{n}\right)$ (1)

Here PK_{I}—means to which extent a cluster member is interested in certain type of information “I” (expressed in fractions or percent). for example, a combination of numbers [0, 1, 1], imagine that this may mean that the vehicle is not interested in information about accidents but is interested in information about parking and traffic jams. Vehicles must have the same interest lists so that vehicles are in the same cluster. To determine the similarities between the lists of interests of vehicles, the formula “cosine similarity” is used [9].

On the basis of the above basic “five parameters” groups are formed among vehicles (Cluster). Each cluster has a group representative known as the head of the cluster. CH will support the common interests of vehicles in the group, that is, support the cluster. Its role in the cluster is very important for cluster stability, and the process of choosing CH requires an effective solution. During the route from the location to the destination, CH must intelligently sort the cluster members, exclude and accept them into the cluster, and most importantly CH must effectively assign CH if he leaves from the cluster. When a CH receives a message, it first checks to see if the vehicles inside the cluster are interested in the message or not. This message will be of this kind of proposal for exchanging data with each other, that is, a request to join the cluster. If their interests coincide and vehicles within the cluster are interested, CH will send a message to

Figure 2. Visual example of “Interests list”.

all other cluster members and synchronization is successful. Otherwise, if their interests do not coincide and the vehicles within the cluster are not interested, this means the cluster does not have common interests. Further, without distributing an unnecessary message within the cluster, in order to minimize irrelevant network transmissions within the cluster, the message will be forwarded to next other CH [3].

3. Process of Clustering and Selection of the Cluster Head

Based on the above “five parameters”, a cluster is formed from the group of vehicles. Cluster—consists of two or more vehicles moving in approximately the same direction and grouped in order to create a communication network. Each cluster has a representative of the cluster, known as the head of the cluster, and cluster members. CH will support vehicle grouping, that is, support cluster duration and stability. During a route, CH must sort within the cluster to exclude and accept CM. Also, CH should, if necessary, choose the next possible CH.

To effectively solve the problem when choosing CH from cluster members, an algorithm is used to select CH is based on the “weight of overall similarity” with the rest of the cluster members. That is, the sum of the values that depend on every different parameters. In which each node (CM), depending on these parameters, calculates its own “weight” (sum). And that member of the cluster with the maximum weight whose results are close and convenient for all other members will be chosen as the head of the cluster [10] [11]. The selection of a cluster head includes:

1) The first thing to do is that each vehicle receives its own parameters from its on-board device—location, direction, speed, destination and a list of interests that are needed at the clustering stage.

2) Each vehicle defines its neighboring vehicles, the direction of which is similar to it.

3) After determining neighbors with a similar direction, each vehicle exchanges data, sends/receives its clustering parameters.

4) After the vehicle receives clustering data from each of its neighbors, a list is created for each vehicle, a neighbor with its data parameters as: identifier of the neighboring vehicle, speed, and its location and destination, and compatibility list of interests (CI). Here, the cosine similarity formula is also used to calculate the compatibility of the list of interests [1] [9]. Using the following Equation (2), CI is calculated between the vehicles “X” and “Y”:

$I{C}_{X,Y}=\frac{{\displaystyle \underset{k=1}{\overset{n}{\sum}}p{x}_{k}p{y}_{k}}}{\sqrt{{\displaystyle \underset{k=1}{\overset{n}{\sum}}p{x}_{k}^{2}{\displaystyle \underset{k=1}{\overset{n}{\sum}}p{y}_{k}^{2}}}}}$ (2)

5) Each cluster member, after maintaining a list of similarity of interests for each neighboring vehicle, determines its own value for choosing the “CH eligibility”, that is, it calculates the cluster header acceptability value (CHE), Equation (3):

$CH{E}_{k}=\frac{A{C}_{k}}{A{D}_{k}A{V}_{k}AR{D}_{k}}$ (3)

AD_{k} is the average distance between the vehicle “k” and each of its neighbors “j” [9] [12]. The AD_{k} parameter must be minimal to increase the CHE value of the vehicle. The AD_{k} parameter is determined by Equation (4):

$A{D}_{k}=\frac{{\displaystyle {\sum}_{J}\sqrt{{\left({x}_{j}-{x}_{k}\right)}^{2}+{\left({y}_{j}-{y}_{k}\right)}^{2}}}}{N}$ (4)

Here (x_{k}, y_{k},), (x_{j}, y_{j}) is the position of the vehicles “k” and “j”, and “N” is the number of neighbor vehicles.

AV_{k}-average of the differences between speed of the vehicle “k” and each of its neighbors “j” and which should be minimal for efficiency [1] [9] [12] [13], calculated by Equation (5):

$A{V}_{k}=\frac{{\displaystyle {\sum}_{J}\left|{\nu}_{k}-{\nu}_{j}\right|}}{N}$ (5)

Here v_{k}, v_{j} means, the Velocity of vehicles “k” and “j”.

AC_{k}-average of compatibility of the interests between vehicle “k” and each of its neighbor “j” [9] [14]. The result should be maximum for maximum CHE value, calculated by Equation (6):

$A{C}_{k}=\frac{I{C}_{kj}}{N}$ (6)

ARD_{k}-average distance of a vehicle “k” and each of its neighbors “j” between a relative destination [15], calculated by Equation (7):

$AR{D}_{k}=\frac{{\displaystyle {\sum}_{J}\sqrt{{\left({x}_{j}-{x}_{k}\right)}^{2}+{\left({y}_{j}-{y}_{k}\right)}^{2}}}}{N}$ (7)

Here (x_{j}, y_{j}) and (x_{k}, y_{k}) means coordinates of RD of vehicles “k” and “j”. The result should be minimum for maximum CHE value.

6) After calculating the CHE value, each cluster member exchanges CHE data from OBU.

7) After receiving data with CHE values from all of its neighbors, each vehicle selects a leader, that is, a vehicle having a maximum CHE value. From its list regarding its data parameters. As its cluster head. Thus, each car selects its cluster head with respect to its parameters. Each CH will have a table of all cluster members, which contains all vehicle identifiers within the cluster. If a group happens multi-hop clustering, can form sub-cluster heads [16]. For each information of interest, if more than 50% of the vehicles in the cluster are interested in information, this means this type of information becomes interesting for the cluster.

The process of clustering and selection of the cluster head occurs as follows:

1) The first step, each vehicle from its on-board devices processes the data of the clustering parameter (Figure 3). Here LI—data from the list of interests presented in the form of a vector as [1, 1, 0], which can indicate certain (separate for each) interests of each transport. For example: this vehicle is interested in information about traffic accidents and traffic jams, but is not interested in information about the presence of specific places such as a gas station, restaurants and shops etc.

2) The second step, based on Equation (2), each vehicle in the group exchanges data with its neighbors and checks the compatibility of the list of interests for each of its neighboring vehicles.

3) Following using Equation (3) from these parameters from each of its neighbors, the vehicle calculates its CHE value (Figure 4).

The maximum value will be selected as CH with a value equal to “3.13” (Figure 5). Therefore, the next highest value equal to “2.73” will be a substitute for the head of the cluster (sub-CH).

Figure 3. Preliminary information about the vehicle.

Figure 4. Cluster head eligibility eigenvalue on each vehicle. Used to determine CH.

Figure 5. Cluster head selection with the maximum value of CHE.

4. “FE” Based Routing Protocol

In the previous stages (Sections 2 and 3) of this work, we described the formation of a cluster based on the so-called “five parameters” of vehicles: taking into account the location, direction and speed of the vehicle, and its destination, as well as a list of interests of each vehicle. As a result, vehicles are grouped into a cluster with the same directions and destination. Therefore, we can confidently say that each cluster has its own direction and destination, which depends on the direction and destination of the cluster members. And therefore, based on this, it is assumed that the cluster destination is the CH destination. My proposed routing protocol, which can be called a destination-based protocol, which is suitable for destination-based clustering algorithms that take into consideration the direction of the cluster or CH. Here, in my case, in order to select the next CH node (CH of the next node) for forwarding, two parameters are also taken, this is the destination of CH and the direction of CH. That is, CHs perform the role of nodes for the next forwarding.

That is, to forward the message to the next node:

Each forwarding message should have a certain transmission direction and target location [7]. The DT vector is calculated in this way (Equation (8)). Let’s imagine that if “k” is a node having sends a message with position coordinates (x_{k}, y_{k}) and with target location is (x_{tl}, y_{tl}).

$DT=\left({x}_{k}-{x}_{tl},{y}_{k}-{y}_{tl}\right)$ (8)

Also, each CH “h” should have a vector of speed calculated by Equation (9):

${V}_{h}={v}_{h}\stackrel{^}{i}+{v}_{h}\stackrel{^}{j}$ (9)

From the above form, we see: the direction of transmission shows that if their cosine similarity (consider with CH direction “h”) is greater than > 0. It means the value of DT is similar to the direction of the CH “h”. To Calculation the similarity of DT and V_{h} by Equation (10):

$Similarit{y}_{h}=\mathrm{cos}\theta =\frac{DT\cdot {V}_{h}}{\left|DT\right|\left|{V}_{h}\right|}$ (10)

In addition, each cluster head “h” should have its own destination, therefore (Destination X_{h}, Destination Y_{h}). And here the difference is the distance between the destination CH of the target location (x_{tl}, y_{tl}) and is computed using Equation (11):

$\Delta {D}_{h}=\sqrt{{\left({x}_{tl}-Dest{X}_{h}\right)}^{2}+{\left({y}_{tl}-Dest{Y}_{h}\right)}^{2}}$. (11)

5. Routing Principles

This section describes the routing steps of this protocol based on the destination:

1) If the actual node “a” wants to send a message to the next destination node “b”, it first needs to send to the CH “k”, transmit the target location TL (x_{tl}, y_{tl}) in the form of messages.

2) Then the CH “k” should check if TL is inside the cluster or not. If CH “k” finds TL inside the cluster, it forwards the message to TL well, or TL does not appear inside the cluster and it does not find, then it selects the CH of the next neighboring cluster “h” to forward the message.

3) When selecting a CH to forward the next node, a CH “k” uses the directions and destinations of its neighboring CHs. Using Equation (8) he determines the direction of transmission of the message, after using Equation (10) he calculates the similarity of DT and V_{h} (Similarity_{h}) for every CH “h” of the neighboring node, witch speed is V_{h}. After, using Equation (11) it determines the distance between the target location and destination
$\Delta {D}_{h}$ for every CH “h” from a neighboring node.

4) Based on the results of calculating Similarity_{h} and
$\Delta {D}_{h}$ for each CH “h” of the neighboring node, the CH of the node “k” makes a calculation of the FE metric “forwarding eligibility” for each CH “h” of the neighboring node (cluster), which determines the advantage of forwarding in Equation (12):

$FE=\frac{Similarit{y}_{h}}{\Delta {D}_{h}}\times 100$ (12)

5) The CH of a neighboring node with the highest (maximum) FE value, is will selected as the next forwarder node.

6) And so on, as described above, the received message CH “k” should check if TL is inside the cluster or not. If CH “k” finds TL inside the cluster, it forwards the message to TL well, or TL does not appear inside the cluster and it does not find, then it using FE selects the CH of the next neighboring cluster “h” to forward the message, process should be repeated.

Figure 6 shows the “k” node with the location (5, 6) and it has coordinates of the target location (65, 100). And three neighboring cluster head nodes. The first of which is a neighboring cluster node with a speed (55, 65) and with a destination (85, 100) and another cluster head node with a speed (35, 25) and with a destination (55, 95). And the third head node of the cluster with speed (0, −100) and with destination (100, −100).

From Figure 7 we see how the node “k” calculates the FE metric using coordinates and taking into consideration the speed of movement for each of its neighbors.

Figure 6. Example parameters for calculating the FE metric.

Figure 7. The value of the FE metric on each neighboring CH node.

Here, in this case, the node with the maximum FE value of 3.76 will have to be selected as our next cluster forwarding node. It is this node that will be the optimal next forwarding node, because it was chosen taking into consideration the speed and destination of the other head node of the cluster, depending on the above parameters.

On the contrary, for example, other routing methods that do not take into consideration an important parameter like speed based on their current position may choose the next forwarding node with an FE value of 2.57, which may not always be effective. Well, or they can choose as the next forwarding node, the first node with the value FE < 0, if the direction of transmission and the TL are not taken into account.

The routing process presented in this paper will be described in detail below. Therefore, a flow diagram will be presented to easily explain this routing.

If the actual node “A” receives a message from cluster members or from another cluster (node), it forwards the message to CH. The head of the cluster first checks to see if the target location is inside the cluster or not. If the target location is inside the cluster, then CH sends the message directly to the target location. Otherwise, if the target location does not appear inside the cluster, then the head of the cluster selects the next neighboring CH forwarding node calculating FE metrics based on the above parameters. Upon receiving the message, the next neighboring CH forwarding node also determines and checks the location of the target within the cluster. If he also does not find the target location in his cluster, he again calculates the FE selects the next CH forwarding node with the highest FE and forwards the message, and so the process will repeat until the vehicle with the desired target location receives the message. Figure 8 shows a scheme of this routing procedure.

6. Simulation Methods

Simulation is an important step in implementing new technology in VANET. There are two components of VANET simulation:

1) Traffic Simulator—In order to analyze VANET characteristics and protocols, traffic simulators are required to generate position and movement

Figure 8. Routing scheme.

information of a single entity in VANET environment [17].

2) Network Simulator—To test and figure out the operability of VANET, a good network simulator should possess some features including a comprehensive mode, efficient routing protocols like AODV (ad hoc on demand distance vector), and communication standards like IEEE 802.11 [p] and IEEE 1609 specifications [17].

6.1. Testing Parameters

To test the operability of my proposed cluster for stability and to verify the performance of this routing scheme based on the destination, made in the cluster based on contextually taken “5 parameters”, two types of simulators are used:

1) “Simulation of Urban Mobility” (SUMO)—the most popular traffic simulator used in VANET—the first very good simulator that I came across on the Internet and I can confidently recommend it to anyone who is looking for such a simulator. This is a great good simulator easy to use, which simulates the movement of vehicles on the streets, simulates traffic. It was great for simulating my cluster operation. SUMO has many functions that make it a very useful traffic simulator, such as multi-lane streets with changing lanes, a lot of different vehicle models and representing networks with many streets, which is especially useful for connecting with many other applications, as well as with a network simulator ns2 which I used and many other applications which can work (combine the results) with SUMO [18].

2) And also a very famous multi-functional network simulator “ns2”, which simulates a diverse network between vehicles [19].

Simulation parameters, date’s from applications and their descriptions screenshot of the results with values.

During the simulation, parameters with the following values were set: type of clustering—K-hop clustering with the given parameter K = {1, 2}, node speed set in the range of 100 m/s - 500 m/s and a packet with a data size of 1500 bits, and also the type of protocol (MAC Protocol) is 802.11. p. The set time for simulation is 100 seconds. The parameters specified in the modeling process are presented below in Table 1.

In this simulation work, taking into consideration the modeling process, technical factors such as delivery ratio, delivery delay, loss-percentages, etc. The results are compared with a cluster-based routing scheme (CBR) and a traditional broadcasting scheme.

6.2. Analysis of the Results

1) Calculation of “delivery ratio”. In Figure 9, it is found that delivery ratio that the delivery ratio should decrease if vehicles increase speeds. Delivery ratio is checked in three speed modes—100 m/s and 200 m/s and 500 m/s. Calculations of “delivery ratio” for different vehicle speeds were carried out in routing based on destination, routing based on a cluster (CBR) and in the broadcasting scheme.

2) Calculation of “packet delivery delay”. In Figure 10, based on the calculation of packet delivery delay, it was found that packet delay increases with increasing vehicle speed. Since, as the speed of vehicles increases, the connection between nodes changes (calculated for different speeds of vehicles).

3) Calculation of the “loss percentage”. In Figure 11, it’s clear that the loss

Figure 9. Effect of vehicle speed on delivery ratio.

Table 1. Simulation parameters.

Figure 10. Effect of vehicle speed on delivery delay.

Figure 11. Effect of vehicle speed on loss percentage.

percentage (%) should increase with increasing speed of vehicles and the percentage of losses is calculated in the range of 100 m/s - 500 m/s, for different changing speeds of vehicles for routing based on destination, for routing based on cluster and broadcasting.

Based on the prominent results of the above graphs, we see that our destination-based routing scheme is more efficient in terms of delivery coefficient, delivery delay, and packet drops, etc. than the cluster-based routing scheme and the traditional broadcasting scheme. It can be concluded that in this routing scheme, the choice of the next forwarding node calculated FE metrics, and this calculation was stable due to the clustering system, which was based on the weight of the “5 parameters” during the selection of the cluster head. This is what helped in the efficient selection of the following forwarding nodes (Figure 7).

7. Conclusions

Most cluster-based routing (CBR) methods when selecting a node in order to determine the next forwarding node use for example only the current location of the node and its neighboring nodes. Not taking into consideration the direction of transmission or the speed of movement of the cluster members, the location and destination, as well as the interests of each member of the cluster, it was not possible to achieve such an effective result in routing as was done in this work. In this work, it was these parameters that helped to efficiently sort the cluster members, and in choosing the effective cluster head based on the weight (sum) of the basis of the values on “five parameters”. Qualitative selection of the cluster head within the cluster with the calculation of the CHE value for each of the cluster members. Also, taking into account FE metrics, the calculation of the highest values among neighboring cluster heads, which were later used as the next forwarding nodes. All of these technical important parameters increase accuracy and minimize incidental routing failures. Without considering such important parameters, routing may not always be optimal when choosing the next forwarding node. Because in some cases, when in a certain period of time, the node can be closer and also at a slight angle to the target location, then it can move further away from the target location, changing its direction later. This results in an inefficient or even incorrect choice of the next forwarding node, thereby disrupting the efficiency of the routing process.

In this work, in the routing process with specific consideration of such important parameters as the direction of the node and the destination of the node, thereby determining the optimal node when choosing the next forwarding node by calculating the FE metric, we have achieved the lowest total delay and increased delivery coefficient for transmitting a message from one node to another.

Cite this paper

Azat, B. and Hong, T. (2020) Destination Based Stable Clustering Algorithm and Routing for VANET.*Journal of Computer and Communications*, **8**, 28-44. doi: 10.4236/jcc.2020.81003.

Azat, B. and Hong, T. (2020) Destination Based Stable Clustering Algorithm and Routing for VANET.

References

[1] Harrabi, S., Ben, J.I. and Ghedira, K. (2016) A Novel Clustering Algorithm Based on Agent Technology for VANET. Journal of Network Protocols and Algorithms, 8, 1-19.

https://doi.org/10.5296/npa.v8i2.8434

[2] Aravindhan, K. and Dhas, C.S.G. (2018) Destination-Aware Context-Based Routing Protocol with Hybrid Soft Computing Cluster Algorithm for VANET. Springer-Verlag, Berlin.

https://doi.org/10.1007/s00500-018-03685-7

[3] Paridel, K., Mantadelis, T., Yasar, A.U.H., Preuveneers, D.J., Vanrompay, G.Y. and Berbers, Y. (2012) Analyzing the Efficiency of Context-Based Grouping on Collaboration in VANETs with Large Scale Simulation. Springer-Verlag, Berlin.

https://doi.org/10.1007/s12652-012-0115-1

[4] Satyajeet, D., Deshmukh, A.R. and Dorle, S.S. (2016) Heterogeneous Approaches for Cluster Based Routing Protocol in Vehicular Ad Hoc Network (VANET). International Journal of Computer Applications, 134, 1-8.

https://doi.org/10.5120/ijca2016908080

[5] Abuashour, A. and Michel, K. (2017) Performance Improvement of Cluster-Based Routing Protocol in VANET. IEEE Access, 5, 15354-15371.

https://doi.org/10.1109/ACCESS.2017.2733380

[6] Dharmawardena, P.K. and Wang, Z. (2017) Cluster Head Selection Based Routing Protocol for VANET Using Bully Algorithm and Lamport Timestamp. International Journal of Computer Theory and Engineering, 9, 218-222.

https://doi.org/10.7763/IJCTE.2017.V9.1141

[7] Goel, N., Dhyani, I. and Sharma, G. (2016) An Acute Position Based VANET Routing Protocol. IEEE International Conference on Micro-Electronics and Telecommunication Engineering, Ghaziabad, 22-23 September 2016.

https://doi.org/10.1109/ICMETE.2016.109

[8] Anas, A.T. (2018) VANET Routing Protocols and Architectures an Overview. Journal of Computer Science, 14, 423-434.

https://doi.org/10.3844/jcssp.2018.423.434

[9] Tal, I. and Muntean, G.M. (2012) User-Oriented Cluster-Based Solution for Multimedia Content Delivery over VANETs. IEEE International Symposium on Broadband Multimedia Systems & Broadcasting, Seoul, 27-29 June 2012, 1-5.

https://doi.org/10.1109/BMSB.2012.6264290

[10] Matthias, R., Andronache, B.A. and Rothkugel, S. (2010) WACA: A Hierarchical Weighted Clustering Algorithm Optimized for Mobile Hybrid Networks. Cluster Computing, 5, 193-204.

[11] Hadded, M., Muhlethaler, P., Zagrouba, R., Laouiti, A. and Saidane, L.A. (2015) Using Road IDs to Enhance Clustering in Vehicular Ad Hoc Networks. Proceedings of International Wireless Communications & Mobile Computing Conference, Dubrovnik, 24-28 August 2015, Article ID: 01211450.

https://doi.org/10.1109/IWCMC.2015.7289097

[12] Shea, C., Hassanabadi, B. and Valaee, S. (2009) Mobility-Based Clustering in VANETs Using Affinity Propagation. Proceedings of the 28th IEEE Conference on Global Telecommunications, Honolulu, 30 November-4 December 2009, 4500-4505.

https://doi.org/10.1109/GLOCOM.2009.5425236

[13] Arkian, H.R., Atani, R.E., Pourkhalili, A. and Kamali, S. (2015) A Stable Clustering Scheme Based on Adaptive Multiple Metric in Vehicular Ad-Hoc Networks. Journal of Information Science and Engineering, 31, 361-386.

[14] Raut, C.M. and Devane, S.R. (2018) QoS Enhancement Using Intelligent Cluster Head Selection Routing Technique in Vehicular Ad Hoc Networks in Case of RSU Failure. IEEE International Conference on Advanced Networks and Telecommunications Systems, Indore, 16-19 December 2018, 1-17.

https://doi.org/10.1109/ANTS.2018.8710167

[15] Morales, M.M.C., Haw, R., Cho, E.J. and Hong, C.S. (2012) An Adaptable Destination-Based Dissemination Algorithm Using a Publish/Subscribe Model in Vehicular Networks. Journal of Computing Science and Engineering, 6, 227-242.

https://doi.org/10.5626/JCSE.2012.6.3.227

[16] Chen, Y.Z., Fang, M.Y., Shi, S., Guo, W.Z. and Zheng, X.H. (2015) Distributed Multi-Hop Clustering Algorithm for VANETs Based on Neighborhood Follow. EURASIP Journal on Wireless Communications and Networking, 2015, 1-12.

https://doi.org/10.1186/s13638-015-0327-0

[17] Traffic and Network Simulation Environment. TranNS.

http://trans.epfl.ch

[18] Simulation of Urban Mobility. SUMO.

http://sumo.sourceforge.net

[19] Network Simulator.

http://www.nsnam.org