Vehicular Ad hoc Network (VANET) is a sub-family of Mobile Ad hoc Network (MANET). The principal goal of VANET is to provide communications between nearby nodes or between nodes and fixed infrastructure. Despite that VANET is considered as a subclass of MANET, it has for particularity the high mobility of vehicles producing the frequent changes of network topology that involve changing of road and varying node density of vehicles existing in this road. That‘s why, the most proposed clustering algorithms for MANET are unsuitable for VANET. Various searches have been recently published deal with clustering for VANETs, but most of them are focused on minimizing network overhead value, number of created clusters and had not considered the vehicles interests which defined as any related data used to differentiate vehicle from another. In this paper, we propose a novel clustering algorithm based on agent technology to improve routing in VANET.
1 Introduction
VANET is a particular class of MANET that provide communications between nearby vehicles, and between vehicles and fixed bases stations situated in communication environment as illustrated in Fig. 1.
Fig. 1
VANET’s environment
×
The main purpose of VANET is to supply, firstly, the prevention and the road safety. The VANET can improve the road accident prevention, by alerting the driver of a dangerous situation. Secondly, VANET provide the traffic optimization, the car traffic can be largely improved due to the sharing of the data collected by vehicles. A car can, for example, be warned of a traffic jam.
Anzeige
So, we can classify these applications into two main categories:
Safety applications like collision or obstacle alert, road conditions warning, merge assistance, deceleration warning, etc. where the main emphasis is on timely dissemination of safety critical alerts to nearby vehicles.
Confort applications such as accessing emails, web browsing, audio and video streaming where the emphasis is on the availability of high bandwidth stable internet connectivity.
With the wireless technology becoming pervasive and cheap, the majority of vehicles have information concerning the outside environment constraints such as the map of the regions to be visited and the density of traffic on the road, etc. All this precious information can be exploited by the vehicles to get an adaptive decision about the choice of a suitable path.
Furthermore, the moving vehicles can share information with the other vehicles to increase routing security. However, due to the mobility of the vehicles, it is hard to find the precise target for sending the information. This is due to the fact that with an increase in the density of the vehicles, collected information may not be accurate as the vehicles may change their position from a particular area. Consequently, a robust routing protocol is needed and required.
It has been demonstrated that clustering improves the performance of the VANETs and can be utilized in numerous applications as intelligent transportation systems (ITS) [1]. A lot of clustering algorithms for VANET have been developed. While most of these algorithms use the MANET clustering algorithms to form and maintain the clusters.
Anzeige
Therefore, these algorithms do not produce a stable clustering structure and the chosen path may not be the best. In cluster based routing protocols, vehicles form a cluster for managing a particular region. Because the vehicles may disappear or change the cluster to which they belong, their position also changes and links between vehicles can quickly disappear.
Consequently, to ensure uninterrupted route, the vehicles must be intelligent to be suitable for network environment and take autonomously the best decision when unexpected problem occurs such as topology changing, accident, traffic jam, varying in density of nodes based on the available information.
In this paper, we propose a new approach for cluster based routing algorithm. Each vehicle in the VANET is characterized by a defined interest as looking for parking space, accessing to Internet, accident alert etc. This paper presents two contributions: The first one is when an accident occurs on the road, the information about this accident should not be sent to each vehicle in the network but only to those nodes which are interested in receiving such data. Consequently the vehicle that detected the accident must send an alert message only for the nodes which are interested with this information.
So, we have to cluster the nodes by taking the interest or context information of the vehicles into account in order to optimize the information flow between nodes and decrease overall network traffic deployment.
The second contribution of this work is that the vehicle should be able to perceive the road and act autonomously in response to the accident alert message from the surrounding environment and take the best decision. It must be also intelligent to avoid accident problem and react quickly to events that may occur on environment communication. Since VANET has become an interesting research topic, several technologies have been proposed to overcome routing problem such as artificial intelligence [2], neural networks [3]. However, given that agent technology takes into account the aspects of cooperation, autonomy, distribution and intelligence [4], it has demonstrated a good behavior in a distributed and highly dynamic environments [5]. Consequently, we believe that assigning agent properties to vehicles may be appropriate to solve the afore-mentioned problems and improve routing performance in VANET.
Agent technology is a field of computer science that is concerned with developing environment aware software agents that use intelligent algorithms allowing them to sense and respond to their environment, and taking, autonomously, an adaptive decisions [4].
The rest of this paper is structured as follows. Section 2 presents the difference between MANET and VANET to highlight the using of MANET’s routing protocol for VANET. Section 3 reviews related work. In Sect. 4, we introduce the proposed algorithm. The simulation results are discussed in Sect. 5. Finally, Sect. 6 concludes the paper with a summary of the presented approach and presents our future work.
2 The Differences Between MANET and VANET Networks
Despite the fact that VANET is a specific application of MANET, several studies have demonstrated that routing protocols designed for MANET are inadequate and have poor performance if they are used without any modification or improvement [6]. MANET is a set of nodes interconnected based on radio communication. These networks are a fully distributed nature and totally dynamic, in which each node must be able to configure itself without the need for any centralized management or no infrastructure previously deployed [7].
MANETs has no fixed infrastructure and they rely instead on ordinary nodes to perform message routing and network management functions. However, several characters such as driver behavior, the absence of constraint of energy, the availability of reliable location information, frequent changes in network topology due to the high mobility of vehicles make VANET behave differently from MANET. These unique network features can provide broken communication links between vehicles. Due to the design goals of MANET’s routing protocols are not valid for high mobility networks, they cannot be directly applied in VANET [7]. The Table 1 summarizes the differences between MANET and VANET [8].
Table 1
Comparative study of MANET and VANET features
Network features
VANET
MANET
Network topology
Always changing
May change
Mobility of nodes
Very high (up to 200 km/h)
Walking speed (up to 8 km/h)
Density of nodes
Very high (limitless)
Utmost 1000 nodes
Constraint of energy
Absent
Limited
Nodes movement
Irregular
Regular
Trajectory of node
Road network (predictable)
Randomly
Stability route
Route can quickly disappear
More stable route
So, based on the above characteristics, we can justify the requirement to design a routing algorithm distinct from the traditional routing protocols.
3 Related Work
In recent years, several works reported in the literature deal with routing in VANETs among which the cluster-based routing protocols that show good prospects.
The authors in [9] proposed a multi-hop based cluster technique in order to progress stability. This method allows vehicles to choose their routes from one-hop neighbors. However, due to the mobility of nodes, it is hard to find the precise target for sending information.
In [10] the authors proposed a novel mobility-based clustering technique considering node mobility as metric for cluster formation process. Nevertheless, according to this method, all nodes make their cluster head decisions every clustering time seconds. Due to the instability of communications links, those decisions may not be the best.
In [11], the authors presented a stable cluster method in VANET based on speed and connectivity degree among nodes. Even that, the simulation results showed that the proposed scheme performs better in terms of cluster formation time and cluster life time, in our opinion, the maintenance process can take a lot of time because the vehicles can quickly disappear or change their cluster.
In [12], the authors developed another clustering method with an idea of taking only the public car as metric to form a group of vehicles. Nonetheless, this method is unsuitable in case where there is no public car.
VMaSC [13] is a novel clustering solution where the node that has the least mobility value will be selected as a cluster head. This approach based only on mobility value that requires a similar mobility patterns.
In [14], the authors studied the inter cluster communication and it used a double cluster head idea. The given method attempted to minimize energy consumption while energy constraint is a critical challenge for MANET and not for VANET.
The proposed approaches [15, 16] are based on GPS system to form stable groups. They take into consideration location and mobility of nodes as two metrics that cannot be the ideal features due to the dynamic network topology.
In [17], the author presented a cluster-based routing algorithm to solve the broadcasting storm. In this method the cluster head is the faster vehicle. When an accident occurs, vehicle broadcasts an alert message includes the identifier and the location of the vehicle involving the accident. In this way, any vehicle can receive the notification even if it is not concerned by this alert which can increase network traffic.
In [18], the authors proposed a routing protocol for VANET to construct the route based on the traffic load, the density of the vehicle and the distance to the destination. The proposed method is based on junction geographic routing technique that sends massages along the routes. However, the main routing decision is made before junctions.
In order to solve the problem of the mobility, a new mobility routing protocol for VANETs on the basis of a fixed direction at a high mobility value is published in [19]. The vehicle adopts this presented approach can obtains an IP address from the VANET via V2V architecture. But, due to the high mobility of nodes, we think that, an address conflict problem may be happen.
In [20], the authors proposed a new cluster-chain construction method. In this scheme, the authors considered, only, the distance from a cluster head to its neighbor as a factor to select the cluster head.
A localization method is presented in [21] where each vehicle evaluates its position based on a message that broadcasted by pairs of road side units (RSUs). This study attempted to develop routing performance based on localization of the vehicles that are currently on the road and their direction as well which are not guaranteed metrics in a highly dynamic environment.
An efficient clustering algorithm for clustering in VANETs is proposed in [22]. The authors considered different factors such as entropy, the direction of vehicle and the number of neighbors to perform the clustering of vehicles in an exact area. But like various clustering approach, this given solution used the GPS system.
The work proposed in [23] describes an adaptive connectivity aware routing in VANETs. The authors demonstrated the choice of the optimal path based on collecting data from diverse regions. Due to the fact that the density of nodes is varying, the collected information may not be precise.
However, in these studies one of the vehicles which are cluster head takes all the decisions on behalf of the other vehicles. Consequently, as the topology changes, these decisions may become not valid.
The most of aforementioned clustering approaches seek to minimize network overhead as well as number of cluster heads, and so on. We consider that all this is of secondary importance and that the principal aim must be the uninterrupted links between vehicles and avoiding the dropped packets as possible even at the highest overhead value.
Due to the mobility of nodes in VANETs, the backbone must be continuously reconstructed in a timely fashion, so the research on more distributed, adaptive and intelligent protocol becomes more than critical. For that, agent technology has become an exciting and promising research area for vehicular ad-hoc.
Previously [24], we proposed an idea of cluster-based architecture by integrating the agents. However, in this paper, we will improve the given architecture as well as study performance based on simulation results.
4 Proposed Clustering Algorithm
In this section, a Novel Clustering Algorithm Based on Agent Technology denoted (NCABAT) is presented to deal with routing in VANETs. Our approach is motivated, firstly, by the fact to assign agent properties to vehicles.
Secondly, we have to cluster the nodes by taking the context information of the vehicles into account in order to optimize the information flow between nodes and decrease overall network traffic deployment.
In [25], the authors defined the context as any related data that can be used to differentiate the situation of vehicles (such as vehicle identifier (ID), geographical location. left Lane, Right Lane etc.).
4.1 Agent Technology
The problem we address here is the intrinsic properties of VANETs that make MANET’s routing protocols unsuitable for VANET. In fact, routing protocol for this type of networks must be robust to ensure route stability and uninterrupted communication. The needed protocol must also be intelligent and to avoid dropping packets, the required method must react quickly to events that may occur such as topology changing or varying in density of nodes.
The idea of using agent technology for routing in vehicular networks has recently been explored in some works [26‐28].
Agent technology is a new paradigm from the field of artificial intelligence. An agent is an autonomous entity, real or abstract, which is able to perceive the environment in which they operate and dynamically react to the incumbent states that may occur.
An agent is capable to communicate with others agents in order to achieve its goals for which it was designed [4]. An agent has two special properties: orthogonal and mandatory characters which distinguish them from the traditional programs. The orthogonal properties are mobile, believable, communicative and learner. The mandatory properties are autonomous, reactive, proactive and temporally continuous. Consequently, a routing protocol based on this program seems appropriate to solve the afore-mentioned problems.
4.2 NCABAT Overview
As shown in Fig. 2, the main goal of the given approach is to divide the vehicles of VANETs into different disjoint groups where each vehicle is replaced by an agent. In our approach, we mainly focus on how to form a cluster where all agents have the same contextual information rather than how to select the main elements of each cluster. In literature, the term “contextual information” or “context” have different interpretations.
Fig. 2
Cluster structure in NCABAT
×
In our solution, we consider that the vehicular interest is the character that can differentiate a vehicle from another. Indeed, in a communication environment, each vehicle has its purpose; it resorts to internet, either to buy a ticket for parking space, play games online, move to right or move to left etc. So, all these routing wishes define the vehicular interests. Each cluster has three vital agents which are:
Cluster-head-agent It is the manager of its cluster. It has the responsibility of providing connection for its neighboring agents.
Context-agent It is an agent responsible for collecting the context information. In other words, when an agent comes within a transmission-range distance, from a nearby cluster-head, the context-agent checks if it has the same interest.
Optimization-agent To minimize messages and traffic congestion, the messages must be communicated to the concerned cluster which is formed on a contextual information basis. Optimization-agent is the vehicle that can listen to the different vehicles of two adjacent clusters and provide communication between them.
4.3 Cluster Formation Procedure
In our approach, each agent enters the network in a “non-clustered” state. To declare its existence to its neighbors, every agent transmits its routing data which represents a unique and different identifier (ID), routing interest and current state.
Upon receiving this data, each agent compares its own interest with its neighbor’s. If it is the same context and if an agent distinguishes that its own (ID) is the lowest of all its neighbors, as it can be seen in line 9 of pseudo-algorithm 1, the agent changes its state to “cluster-head-agent”.
×
But if its own (ID) is the highest as shown in line 8 of the below code, then it declares itself as “context-agent”.
×
To ensure interconnections among neighbor clusters, the optimization-agent is the vehicle that is located in the nearest position to the neighboring cluster-head-agent. The simplest method to determine the nearest neighbor is the coordinates (X, Y) determined by the GPS system.
Indeed, we assume that the vehicle which has the highest value of Y will be elected according to the peudo-algorithm 3, by the cluster-head agent, as an optimization-agent. The other agents in the cluster which have one-hop link to the cluster-head-agent are called the Ordinary Cluster Members (OCM).
×
To inform its neighbors, each elected agent must broadcast a message containing its new state, its ID as well as the identifier of its clusters (ID_Cluster) (as shown in Fig. 2). In spite of the fact that the topology of VANET is dynamic, the network topology can be changed over time. As a result, cluster maintenance is needed. In our approach, the cluster formation procedure will be triggered when a vehicle leaves a cluster and moves to another neighboring cluster or when a “non-clustered” agent enters the network looking to join a cluster.
4.4 Routing Scenario
In this section, we demonstrate the importance of taking into account the context information. Otherwise, the message would not be delivered to all neighboring agents, but only for the nodes which are interested with this packet. The idea behind this choice is to improve the routing performance based on a multicast technique rather than a broadcast mode. As shown in Fig. 3, each agent in the cluster 1 is interested in the Left line.
Fig. 3
Broadcast routing
×
We assume that V3 was already informed by a vehicle on the left lane about an accident problem. So, if we don’t take the context into consideration, V3 broadcasts the message to the next hop neighbors. In addition, agents blindly rebroadcast every message they receive without applying additional control mechanisms. This method is called “Flooding” [29]. This process continues until the request packet reaches all neighboring agents.
As a result, even-though the agents of cluster 2 are not concerned by the accident alert, they have received the message which can increase the network traffic and decrease the routing performance.
According to our approach, the alert message must be routed to the interested agents. Consequently, agent V3 forwards the packets to the next hop along the way to the cluster-head-agent. The cluster-head-agent forwards the packet to its optimization agent which in turn, will forward it to the concerned neighboring agents. This process continues until the request packet reaches either an intermediate agent or the destination agent itself as illustrated in the Fig. 4.
Fig. 4
NCABAT message dissemination
×
In the following code, we demonstrate the process of sending an alert message presented in the above figure.
×
5 Simulation Results and Performance Comparison
This section presents the performance evaluation of our approach. The proposed approach has been simulated using JADE Frameword (Java Agent DEvelopment) [30].
To prove the usefulness of context information, we are chosen to compare the performance of our approach against the multicast routing protocols MAODV (Multicast Adhoc On-demand Vector) [31].
The only reason to choose this protocol from the different routing protocols, that it is the most attractive one based on a study proposed in [32] that compared MAODV with ODMRP [33] and ADMR [34] routing protocols. Indeed, according to this comparative study, MAODV routing protocol outperforms better than ODMRP and ADMR routing protocols in terms of end-to end delays, throughput and packet delivery ratio.
Lots of scenarios were carried out to evaluate our approach. We also intend to study the influence of increasing the network size on the performance of NCABAT as well as MAODV. The performance metrics used for our evaluation were the average of end-to-end delay, throughput and Packet Deliver Ratio (PDR).
The average of end-to-end delay defines all the delays caused during the routing process such as transmission/re-transmission delays at the MAC layer, transfer delay, route discovery delay.
Throughput is described as the total number of received packets at destination out of total simulation time. The throughput is the more important metric because we are concerned about the number of transmitted messages.
The Packet deliver ratio (PDR) is defined as the rate of the number of delivered packets to the best destination.
5.2 Results Analysis
5.2.1 Throughput
Figure 5 illustrates the results of measured throughput for two previously discussed methods depending on the number of agents. The results depict more efficient behavior of our approach NCABAT in comparison with MAODV when the number of vehicles grows.
Fig. 5
Throughput versus number of vehicles
×
As depicted from Fig. 5, throughput value of MAODV algorithm increases progressively from approximately 200 byte/s at 10 vehicles to 700 byte/s at 50 vehicles and remain stale with increase in the density of vehicles.
However, the throughput of our approach increases from 1400 to 1800 byte/s. Then, it remains almost constant at [25, 35] vehicles. But, it becomes higher again and reaches 3100 byte/s at 60 vehicles.
5.2.2 Average End to End Delay (EED)
Figure 6 depicts the average of end-to-end delay measured with increasing in the number of vehicles. We can notice that at [0, 20] vehicles and although the decrease of end-to-end delay value of NCABAT from 5 to 3%, MAODV outperforms our approach NCABAT. Nevertheless, when the number of vehicles grows, our approach demonstrates good scalability.
Fig. 6
Average of end-to-end delay (EDD) versus number of vehicles
×
In fact, at [40,60] vehicles, our approach decreases to reach 1.7% however, the average of end-to-end delay of MAODV increases from 3% at 40 vehicles to 7% at 60 vehicles.
5.2.3 Packet Delivery Ratio (PDR)
As it can be seen from the Fig. 7, up to 50 vehicles, the performance of the packet delivery ratio for MAODV is better than our approach. But, when the number of vehicles increases to be 60 vehicles, our approach outperforms MAODV.
Fig. 7
Packet delivery ratio (PDR) versus number of vehicles
×
Table 3 summarizes the performance of our approach against MAODV routing protocol.
Table 3
Numerical comparison of MAODV and our approach
Number of vehicles is equal to 10
Number of vehicles is equal to 60
MAODV
NCABAT
MAODV
NCABAT
Throughput (byte/s)
200
1400
700
3100
Average End to End Delay (EED)
3%
4.5%
7%
1.7%
Packet Delivery Ratio (PDR)
6%
2%
3%
4%
6 Conclusion
VANETs possess exceptional network features that distinguish them from MANETs such as highly dynamic topology. From the above mentioned characteristics, it is evident that MANETs clustering algorithms have difficulties in finding stable routing paths in VANETs. Therefore, clustering techniques should be designed to adapt to the VANET environment. These algorithms must take into account all vehicle dynamics.
In this paper, we have proposed a new clustering algorithm based on agent technology. Our main objective is to describe agent properties to vehicles with the purpose of improving traditional schemes in terms of performance. Unlike most previous works, our clustering algorithm tends to group vehicles sharing the same context information (context) during the cluster formation process.
The simulation results show that our approach NCABAT performs well compared to MAODV in terms of throughput, average of end to end delay and packet delivery ratio with increasing in the number of vehicles.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
