Reliable Communication in Cooperative Ad hoc Networks

1. Introduction

Although nowadays wireless networks are a regular and familiar framework for sharing information among devices, the way in which these nets are organized and managed is evolving day by day due to the requirements of the scenarios in which they are deployed. Since those first experiments carried out by the WECA (Wireless Ethernet Compatibility) association in late 90s, the application areas and use cases in where wireless communications are applied has been changing.

Many of the wireless networks that we use daily at home, at the office or when se use a cellular are based on those first approaches, in which an Access Point is needed to have connectivity. These setups are called ‘Infrastructure Mode’ and use a fixed and wired backbone to address information from the source AP to the destination AP. But in some situations these networks are limited by their own nature due to their need for an AP, a base station, some routers or switches and so on. It is in these scenarios where a ‘’Infrastructure-less Mode’’ can overcome these drawbacks, allowing the nodes of a network to routing and forwarding information for other nodes, without relying on centralized administrator. These types of networks are called wireless ad hoc networks [1].

Figure 1.

Infrastructure based networks (left) and Ad hoc networks (right)

Now, if we have into consideration the current trends in technology, it can be said that mobility and ubiquity are common characteristics to all the new gadgets launched to the market. Users want to be online anytime and everywhere and to obtain information from all the surrounding elements. Then, we talk about Mobile Ad hoc Networks (MANETs), that is, wireless networks with a dynamic shape, a shifting number of nodes, a defined bandwidth and other characteristics, where the nodes can be any kind of devices with communications and networking capability that communicate with each other without a centralized coordinator [2]. In this scenario, each node can play the role of a router, hosting the network topology dynamically, because as it was mentioned above, the shape and the topology of the net can change as well as the nodes on it. The main characteristics of MANETs can be summarized as follows [3]:

• Dynamic topologies: network topology can change quickly due to the nodes can move freely in the net.

• Bandwidth constrains: compare with wired networks, the capacity of a MANET is relatively small and also it is sensitive to interferences, noise, and signal fading effect.

• Energy constrains: although many of the nodes can be plugged to the power line or they can be equipped with big batteries, some of them use small power supplies, so during the network design it is necessary to consider how to save power in order to assure the stability and longevity of the network.

• Limited physical security: although the decentralized nature of MANETs provides robustness against the single points of failure, these nets must be protected against eavesdropping, spoofing, and the injection of malicious data attacks.

In this context, thanks to the rapid increase and improvement of the mobile computing a wide set of wireless devices have proliferated, making possible that traditional hardware as digital cameras, thermostats, cooking ovens or washing machines are provided with communications and computing functionalities so they can be part of a MANET. This new paradigm is known as Internet of Things [4], that is, a scenario in which all the objects beyond computers, mobiles or touch screens have the ability of generating, sharing and processing information in a pervasive manner [5]. With all of this, technologies must have evolved to new standards, architectures, protocols, hardware, services and facilities that will make possible a control of the way in with all the nodes access to the net to share their information.

One scenario that represents perfectly the characteristics and it is a perfect case of study of MANETs is the Vehicular Ad hoc Networks (VANETs), a subset of MANETs, which creates wireless networks between vehicles [6]. In a VANET each vehicle is a moving node which creates wireless networks with surrounding vehicles [7], thanks to the On-Board Unit (OBU), a hardware with communications and computing capabilities that allows drivers to receive information about events that can affect his driving. Then, the main function of the OBU is to exchange information with other vehicles or Road Side Units (RSUs), elements located at the infrastructure that act as gateways between the VANET and other networks or agents as Traffic Management Centers (TMC). These centers are placed far away the VANET and play an important role in the applications developed in the area of VANETs, coordinating the information that is shared among VANETs that are deployed in different geographical areas.

In VANETs they can be distinguish two types of links: vehicular-to-vehicular communication (V2V), based on an Ad hoc architecture, vehicles exchange directly messages without a central coordinator; and vehicle-to-infrastructure or infrastructure-to-vehicle (V2I or I2V), where the messages are shared between the vehicles and the RSUs. VANETs are designed for a huge range of cooperative applications, that is, services that provide information to the drivers thanks to the data shared among all the vehicles on the net. These can be safety and non-safety applications, which allow several added services as infotainment, traffic management, toll payment, and geographical based services and so on [8]. That is, VANETs make possible to deploy applications that help to improving the transport services and traffic conditions using collaborative systems based on V2X Ad hoc networks.

Figure 2.

Vehicular Ad hoc Network Scenario

This introduces the definition of Intelligent Transport Systems, where each vehicle is a sender, a receiver and a router at the same time, so it can broadcast the information to the VANET, which uses this information to provide these safety and non-safety services to the drivers. The OBU is the hardware in charge of processing these data and it also enables these short range wireless ad hoc networks (the coverage area is around 300 meters) but it also must dispose other systems that permit to report position information such as Global Positioning System (GPS) or a Differential Global Positioning System (DGPS) receiver if more accuracy position information is required. This information is quite important because most of the services that are available in a VANET depend on the geographical position of the source and the destination. Table 1 presents a classification of ITS applications that can be deployed using the VANET architecture [9].

Category	Applications	Uses cases
Active safety applications	Cooperative driving assistance applications	Emergency vehicle warning; Slow vehicle indication; Intersection collision warning; Motorcycle approaching indication; Emergency electronic brake lights; Wrong way driving warning; Stationary vehicle - accident; Stationary vehicle - vehicle problem; Traffic condition warning; Signal violation warning; Roadwork warning; Collision risk warning
Efficiency applications	Traffic management; Road monitoring	Regulatory / contextual speed limits notification; Traffic light optimal speed advisory; Enhance routing; Road conditions sensing (rain, visibility, wind, hazardous location, road adhesion)
Infotainment applications	Contextual information; Entertainment	Point of Interest notification; Automatic access control and parking management; ITS local electronic commerce; Media downloading; Insurance and financial services; Fleet management; Loading zone management

Table 1.

ITS applications on VANETs

These applications can be deployed on urban or motorway scenarios, each one with its own particularities. In an urban scenario, many of the times there is not line of sight between the nodes so fading and communication disruptions are frequents. In a motorway, the high density of vehicles can overload the radio channels in which the VANETs work. Yes, although maybe users are not aware about that, the radio spectrum (the physical interface used by wireless communications networks) is a limited resource that it must be shared among all OBUs and RSUs that shape the VANET. Commonly, ISM (Industrial Scientific Medical) radio bands with frequency ranges 2.40–2.4835 GHz and 5.15–5.875 GHz are used by wireless networks for license-free communications [10]. The definition of these standards is crucial in order to attend the increase on the demand of the spectrum channels and to make possible that different networks can coexist in the same radio band.

Although WLAN (IEEE 802.11a/b/g/n) could be the technology used in VANETs, most of the applications included at Table 1 require time-critical communications, a continuous handover among different RSU in V2I/I2V links, and as these standards use CSMA (Carrier Sense Multiple Access), so many of the nodes cannot have success in channel access due to the high density of some scenarios. Due to the limitations of these standards in mobile scenarios as VANETs, a new extension has been developed: IEEE 802.11p, designed specifically for vehicular environment in which high reliability and low delay characteristics are mandatory. This new standard, known as Dedicated Short Range Communication (DSRC) uses the physical layer of IEEE 802.11a working on the 5.9 GHz band and quality of service enhancements of IEEE 802.11e. Network and transport layers are in the scope of WAVE (Wireless Access in the Vehicular Environment) standard which defines the protocols and services that support multi-channel wireless connectivity between IEEE 802.11 Wireless Access in Vehicular Environments devices [11].

Once the access to the medium is defined under the frame of the IEEE 802.11p standard, in a situation in which many nodes have information to transmit to different destinations in a network that is geographically distributed, it is quite important to determine the protocols that allow to organize the addressing of the information and to assure that all the nodes have the chance of transmitting and receiving data. The nature of MANETs, and specifically of VANETs implies that the maintenance, management and routing task of the network must be done by all the nodes, making these kind of networks more difficult or more complex to other wireless networks. Therefore, advances techniques of management and arrangement should be applied to organize the network and assure its effective implementation and its fairness and reliability for all the nodes.

In the next sections of these chapter are analyzed the main techniques used to disseminate data in VANETs, with an special emphasis in clustering, a control scheme that can take into consideration the speed and distance difference among neighboring nodes in the VANET to group them in order to assure a stable cluster structure and then enhance the stability of the network topology.

2. Data dissemination algorithms

Data dissemination in VANETs has recently received considerable attention. Due to the unique characteristics of VANET, the implementation of reliable data dissemination among vehicles has encountered many challenges. Information dissemination in VANETs provides drivers a way to be aware in real-time of everything that is happening in their surroundings. A wide range of information can be disseminated, including traffic and road conditions, closure and detour information, incident information, emergency alerts, and driver advisories.

Information dissemination schemes in VANETs are commonly categorized into two different groups, according to the type of ITS application: safety and non-safety. During the last years, research community has focused their studies more on safety applications which are highly demanding in terms of message delay and present a challenging field of study. Although in safety applications the frequency of messages is low, the message delay is a key factor because a safety message, e.g., an emergency vehicle warning, has to reach a maximum number of nodes in a given area within a very short time interval, because after this time interval, the message essentially becomes useless.

However, in non-safety applications the message delay loses importance since the message could be useful for a longer time interval, even up to several minutes, e.g., for disseminating traffic road conditions. On the other hand, the frequency of these messages is much higher in this type of applications.

Therefore, data dissemination in VANET is a challenge for the deployment of cooperative services and applications because the dissemination routing protocol has to be suitable both for safety and non-safety applications, and it also has to be aware of the vehicular environment challenges as the high mobility of nodes and the extremely dynamic network topology. Therefore, the design of an efficient information dissemination routing protocol for VANETs is very crucial.

The function of a routing protocol in Ad-Hoc network is to establish routes between different nodes and the main requirement is to achieve minimal communication time with minimum consumption of network resources. The main reasons that make so difficult the design of these routing protocols are the highly dynamic nature of VANETs due to the high mobility of the nodes, and the need to operate efficiently with limited resources, such as network bandwidth. Moreover, routing protocols in VANETs, and generally in every Ad-hoc Networks, are not so good in scalability due to frequently changing network topology, lack of predefined infrastructure and limited radio communication range. In the literature, four categories of dissemination routing protocols for VANETs which are presented: position-based, broadcast, geocast and cluster-based.

Broadcast routing is commonly used in ITS applications in VANETS because it guarantees that every vehicle will receive the message. The simplest way to implement a broadcast service is flooding in which each node re-broadcasts messages to all of its neighbors except the one it got this message from. Flooding performs relatively well for a limited small number of vehicles and is easy to be implemented. Furthermore, this protocol is very reliable in safety applications but it consumes high bandwidth and resources, and it can also provoke a broadcast storm when the number of nodes in the network increases. If multi-hop communications are implemented as each node receives and broadcasts the message almost at the same time, this routing protocol generates contentions and collisions and high bandwidth consumption.

However, there are many studies where they use broadcast, but they design an approach to avoid broadcast storm. In [12], Yang et. al propose a V2V communication protocol for Cooperative Collision Warning application. In this approach when a vehicle has an incident, it becomes an abnormal vehicle (AV) and starts broadcasting periodically Emergency Warning Messages (EWMs), with its geographical position, speed and direction to its surrounding vehicles. If this incident provokes that more vehicles have to stop and, therefore, they become also AV, only one of them is going to send the EWMs to avoid the broadcast storm. In [13], Ferrari et. al use broadcasting protocol with multi-hop communication but to avoid the broadcast storm not every vehicle forward the received messages, only the farthest vehicles from the source forward it.

Figure 3.

Broadcasting routing protocol

In the position-based routing protocol the forwarding dissemination decisions are based on location information. This approach makes sense because in VANETs the movements of the vehicles are usually restricted in just bidirectional movements constrained along roads and streets, and the geographical location information of vehicles is taken from street maps, traffic models or even more prevalent navigational systems on-board the vehicles. This protocol is commonly used with multi-hop communications and therefore, nodes usually forward the packet to a node that is geographically closest to the destination. The main advantages of this routing protocol are:

• It does not require routing tables

• Traffic overhead may be small

• Supports delivery of packets to a geographical area, called geocasting

For example, as it is shown in Figure 4, if one vehicle has an accident the information will be only be necessary for the vehicles that are behind the damaged vehicle, not for the ones that are not going to drive again though the point the accident has happened.

Figure 4.

Position-based routing protocol

However, to use this location-based routing protocol in a built-up city environment is very challenging, due to vehicles are distributed in an irregularly way because they usually are more concentrated on some principal roads than others and the road patterns define their mobility and add difficulty in the signal reception because of the radio obstacles such as high-rise buildings which may lead VANETs unconnected. Furthermore, in general, topology-based routing protocols are considered not to scale in networks with more than several hundred nodes [14].

In order to position-based routing protocol could work, vehicles should send periodically beacon messages to announce their position and enable other nodes to maintain a one-hop neighbor table. This approach is scalable and resilient to topology changes since it does not need routing discovery and maintenance; however, periodic beaconing creates a lot of congestion in the network [15]. This beaconing frequency can be configured according to different scenarios or traffic situations, but if this beaconing frequency is not enough the inaccuracy of position information is higher and a neighbor selected as a next hop may no longer be in transmission range implying to a significant decrease in the packet delivery rate.

Therefore, the key ideas we have to take into account to select one position-based routing protocol are:

• Loop-freedom: routing protocols should be inherently loop-free and should avoid recovery strategies using timeouts of old packets and memorizing packets that have been seen before

• Distributed operation

• Path strategy

• Metrics

• Memorization

• Guaranteed delivery

• Scalability

• Robustness

There are three different kinds of position-based protocols which are restricted directional flooding, greedy and hierarchical routing protocols. The most used routing position-based protocol is the greedy in which they use forwarding to route packets from a source to the destination. This strategy do not establish and maintain the routes between the source and the destination; on the other hand, a source node define the approximate position of the destination and add this data in the data packet and selects the next hop depending on the optimization criteria of the algorithm; for example, as it is shown in Figure 5, one criteria could be the closest neighbor to the destination [16],[17]. In the same way, each intermediate node selects a next hop node until the packet reaches the destination, as it is shown in Figure 4 Position-based routing protocol.

Figure 5.

Greedy routing protocol

The main characteristics of Greedy algorithms are:

• Loop free

• Localized information

• Single path strategy

• Metric: Hop count

• No memory

• No guarantee of delivery

• Scalable

• Somewhat robust

In restricted directional flooding, the sender will broadcast the packet to all single hop neighbors towards the destination. The node which receives the packet checks whether it is within the set of nodes that should forward the packet (according to the used criteria). If it is, it will forward the packet. Otherwise the packet will be dropped. In restricted directional flooding, instead of selecting a single node as the next hop, several nodes participate in forwarding the packet in order to increase the probability of finding the shortest path and to be robust against the failure of individual nodes and position inaccuracy.

Figure 6.

Restricted directional flooding routing protocol

The main characteristics of Restricted Directional Flooding are:

• Not loop free

• Localized operation

• Path strategy: flooding / multipath

• Metric: Hop count

• Memory

• No guarantee of delivery

• Not scalable

• Not robust

The third forwarding strategy is to form a hierarchy in order to scale to a large number of mobile nodes. This strategy tries to reduce the complexity of the information each vehicle has to handle and also improves the scalability of the network. The two main strategies used to combine nodes location and hierarchical network structures are the zone-based routing and the dominating set routing [18].

Geocast routing is a location-based routing but in a multicast way, so each message is broadcasted to every vehicle inside a defined area. In Figure 7 it is shown that the defined area are the vehicles which receive the yellow messages. Geocast can be implemented with a multicast service by simply defining the multicast group to be the certain geographic region.

Figure 7.

Geocast routing protocol

Most geocast routing methods are based on directed flooding, which tries to limit the message overhead and network congestion of simple flooding by defining a forwarding zone and restricting the flooding inside it. With this routing protocol we consume less network resources than broadcast routing but we also guarantee that every vehicle will receive the message. However, we continue having the broadcast storm problem unless we only use one-hop communications. Geocast routing is divided into three types which are: Routing with simple flooding, direct flooding and no flooding [19].

The Geocast routing based on simple flooding was not created for geocast routing but it is used as a basic unit and for the comparison with other protocols. In this method, the source vehicle delivers the packet to all other nodes in the network and all receivers have to check whether they are within the destination area. This is a very straightforward approach but is not a well-organized approach. In this approach, information of location is not used.

In the Geocast routing based on direct flooding the packet is forwarded to a defining region called “forwarding zone”. In this approach a packet is only forwarded to forwarding zone by the source node and not to all nodes in the network. In other words, this protocol is based on flooding but avoids flooding the whole network by defining a forwarding zone, and therefore, outside the forwarding zone the packet is discarded. There are two types of forwarding zone, the first one is the rectangular forwarding zone and the other one is distance-based forwarding zone.

The Geocast routing without Flooding is a simple geocast routing protocol that uses a regular unicast routing protocol between the sender and the destination region. Inside the destination region, flooding can be used, as well as any other routing protocol that can be independent of the protocol used outside the destination region, but the main difference is that it does not use flooding outside the forwarding zone.

But the most used routing protocol for vehicular environment is the cluster-based, where vehicles are grouped into different clusters according to some parameters. These parameters differ from one algorithm to another and are the key factor to build stable clusters. Some of those parameters could be the location, speed or inter-vehicle distance. Other parameters, as the IEEE 802.11p wireless coverage area of each vehicle, could affect in the size of clusters which could vary from one cluster to another in the same network depending on the location of nodes.

Therefore, clusters are virtual groups selected by a clustering algorithm where at least there is Cluster Head (CH) and some Cluster Members (CMs). The main advantage of cluster-based solution is that it can achieve good scalability for large networks, but, on the other hand, the delay and overhead involved in the formation and maintenance of clusters has to be taken into consideration.

The highway, urban, city and intersection scenarios require different characteristics for selection of CHs and for formation of clusters.

Figure 8.

Clustering routing protocol

The cluster-based routing solution could be designed in three different ways depending on how vehicles discover the CH. It could be in a proactive, reactive or hybrid way. In the proactive solution beacon messages are constantly broadcast and flooded among vehicles since every vehicle should maintain updated their neighbor table to know which the next hop node toward a certain destination is. The advantage of the proactive routing protocols is that there is no route discovery since route to the destination is maintained in the background and is always available upon lookup. Despite its good property of providing low latency for real-time applications, the periodically beacon sending for the maintenance of the neighbor table requires a significant part of the available bandwidth, especially in highly mobile VANETs.

In the reactive approach the configuration phase is initiated by the vehicle because it starts a communication when it needs to communicate with another vehicle. It maintains only the routes that are currently in use, thereby reducing the burden on the network. Reactive routings typically have a route discovery phase where query packets are flooded into the network in search of a path. The phase completes when a route is found.

In a mixed approach vehicles also send periodic proactive beacon messages to have the neighbor table updated but they are also able to create a new communications on demand when they need to send any message to another vehicle.

To sum up, it is not very obvious which is best routing protocol for data dissemination in VANETs because it depends on application and the characteristics of the scenario like the position of the vehicles, speed, direction of movement, potential communication duration and potential number of communication neighbours, among others. Therefore, research community should continue researching on the development of new dissemination data routing protocols.

3. Clustering algorithms

Clustering is a technique for grouping vehicles in the geographical vicinity together, making the network more robust and scalable. Under a cluster structure from Figure 9, vehicles may be assigned a different status or function, such as cluster head (CH), gateway (GV), or cluster member (CM). A CH normally serves as a local coordinator for its cluster, performing intra-cluster transmission arrangement, data forwarding, and so on. A GV is a non-CH vehicle with inter-cluster links, so it can access neighboring clusters and forward information between clusters an RSUs. A CM is usually called an ordinary vehicle, which is a non-CH vehicle without any inter-cluster links.

Figure 9.

(a) Highway and (b) City scenario.

Cluster-based solutions may be a realistic approach in supporting reliable and scalable multi-hop communication for VANETs [20]. Clustering has been shown to effectively reduce data congestion [26], and can support Quality of service (QoS) requirements [21] for both delay-tolerant (e.g. road/weather information) and delay-intolerant (e.g. safety messages). According to [22] clustering provides three basic benefits.

• Spatial reuse of network resources.

• Emergence of a virtual backbone.

• Improved network stability and scalability from the viewpoint of regular CMs.

Clustering can be done in a centralized or decentralized way. In centralized way, RSU elect CHs and forms clusters based on periodic message. As a fixed infrastructure, the RSU should be fully utilized to collect information and use this information to perform central control. It acts as backbone of all data transmissions. However, it does not work in network where there are no RSUs. Decentralized clustering is based on the ”hello message” exchange between the vehicle and it forms clusters and elects its CHs. Additionally, most protocols only use peer to peer communication to gather and transmit information, so those data can hardly be converged and processed in centralization. This is further discussed in detail in coming section.

3.1. Infrastructure centric clustering

Infrastructure based clustering is a centralized clustering where it gathers information from all the vehicles in the road, including speed, direction, positions, and further traffic related information. Infrastructure divides vehicles in the road into different cluster groups, it coordinates in the election of CH, routing of packets and allocation of the channel to its CMs. As a fixed infrastructure, it computes the collected information to perform central control. Moreover, using V2V clustering some algorithms require additional devices for computation to fulfill the aim, which will raise the vehicles cost and reduce the feasibility of algorithms. Infrastructure based clustering is used to solve the above-mentioned shortcomings and to achieve high stability. Overall, the amount of data to be sent is comparatively small (the position, speed, direction of each vehicle), but the communication reliability is vital.

Some approaches shown in Table 2 uses infrastructure for centralized channel allocation in order to reduce channel allotment time and control overhead. It can be seen infrastructure divides the spectrum allocated to a particular area into prefixed overlapping spatial clusters. The medium in each cluster is divided into time slots and each time slot is allocated to a vehicle in accordance to the priority of the message and availability of the time slot. However, due to centralized allotment the reliability and fairness is lowered. In another approach, infrastructure allocates channels to the moving vehicles based on their clusters and enables channel reuse in non-adjacent clusters. The infrastructure broadcast is heard by all the neighboring vehicles in the infrastructure region and this solves the issue of hidden/exposed vehicles. Furthermore, broadcast helps to avoid contention and results in efficient utilization of the allocated bandwidth. The lack of contention for channel acquisition and priority list at the infrastructure allows the protocol to ensure predictable delivery of safety messages. Nevertheless, these types of algorithms may not scale at high density and would not function in ad hoc mode in regions where there are no infrastructures.

Protocols	CH election	Cluster Formation	MAC	Scenario	Simulator	Pros	Cons
CMAC [23]	RSU is CH	Speed, relative distance and direction.	FDMA	Highway	MOVE, SUMO and; NS-2	Predictable; and reliable.	Density not considered. Require RSUs. Low bandwidth utilization in sparse traffic
Ranjeet; Singh; [24]	RSU is CH for all clusters	Static cluster; formation	TDMA	Intersections	NCTUns	End to End delay is reduced.	Require RSUs all time. Reliability lowered in high speed scenarios.

Table 2.

Comparison between various infrastructures based protocols.

Vehicular motion are confined to strait jacket roads and travels at high velocity and the enter/exit infrastructure area in short interim’s of time. At a given period of time, the total number of vehicles in an infrastructure area can vary significantly from a small density of vehicles to a large density of vehicles in a very short interim of time. Algorithms must be distributed or should require partial infrastructure assistance with an efficient hand-off from one infrastructure to another to meet these attributes. The vehicular movement is predetermined to road structure and directional antenna would be suitable for communication via infrastructures. The vehicle broadcast radio frequencies with transmission channels, each one considered as a common medium over which two neighboring vehicles cannot transmit simultaneously because a transmission collision occurs. So, in order to efficiently share the medium, MAC protocol is needed and is beset by contention delay. However, a protocol must ensure that safety messages are delivered within a prescribed time frame. The protocol must not suffer without the hidden/exposed terminal or deafness problem to ensure reliable message delivery. Although the infrastructure is an extra, it will be furnished on the highways extensively and applied in VANET in the near future. Therefore, compared with great and lifelong benefit, the infrastructures expense is of trifling importance at all. The efficient cluster based MAC and routing protocols can provide a more stable communication than a solution using V2V clustering. The optimum protocol should that take the advantages of fixed infrastructure and optimize the problem.

3.2. V2V based clustering

V2V based clustering is a decentralized clustering where clusters are formed based on communication between vehicles. Additionally, the CH election will be based on V2V communication. There are several advantages of using V2V-centric clustering as compared with the infrastructure-centric VANETs. V2V-centric clustering can avoid the short communication link period, high frequent hand-offs, fast channel fading, etc., that are caused by the high relative-speed difference between the fixed infrastructure and the fast-moving vehicles. Finally, the V2V-centric clustering performs better in active safety applications, which only requires exchanging messages among one hop vehicles within their transmission range.

V2V communications are expected to significantly improve transportation safety and mobility on the road. Several applications of V2V communications have been identified, from safety and warning applications, up to traffic control and driver assistance applications. In infrastructure centric clustering, all the communications is done via the infrastructure which causes a lot of control overhead and additional delay. Furthermore, it would be very cost intensive to build an infrastructure based communication all along the road structure. The V2V based clustering technique avoids the use of stationary base stations by building up VANETs, where all vehicles in a common transmission radius can exchange messages. However, CH selection carried out through V2V communications has some shortcomings, e.g., highly complex protocols, large computation and communication cost, need of additional devices and so on. Another important issue is that the connection between two adjacent CHs may be lost due to vehicles high speed, which drastically reduces the link quality. The hidden terminal problem where two vehicles are outside of each other’s transmission radius, but both attempt to transmit to a vehicle that is within the radius of both. This issue is likely in pure V2V scenarios where there is no centralized communication system. The result of the hidden terminal problem is data collisions. By enabling vehicles to transmit/receive messages with each other via V2V as well as with infrastructure communications, VANETs could contribute to more safer and congestion free roads by providing correct and timely message to neighboring vehicles and other related departments.

3.3. Clustering in layers

Clustering can simplify essential functions like bandwidth utilization, routing, and channel access. In MAC layer, it can provide a fairer and reliable channel access to all vehicles in network. This can lead to increase in the reliability of packets and scalability of the network. In network layer, clustering for routing can find the closest vehicles to intended destination. Furthermore, it reduces the number of broadcast and flooding messages in the network. In addition, the overhead for clustering is reduced if the same scheme is used for MAC and routing.

3.3.1. Clustering in MAC layer

Introducing a cluster scheme already on the MAC layer additionally provides the possibility of a fairer medium access. When clustering applied in VANETs, it brings interesting research point such as broadcast storm that occurs when several vehicles are passing at a specific region at the same time, causing network congestion, packet collisions and delays in the medium access layer. A cluster-based MAC scheme is needed in V2V communication to overcome the lack of specialized hardware for infrastructure and the mobility to support network stability and channel utilization. In this case the CH can take over the responsibility to assign bandwidth to the CMs and therefore even QoS support can be improved. As the bandwidth can be assigned centrally fewer collisions have to be expected which consequently increases the reliability.

Many researchers have proposed cluster based multi-channel medium access control protocols to improve the performance and reliability of VANETs. In these protocols, clustering is used to limit channel contention and provide fair channel access within the cluster. On the other hand, multi-channel is used to increase the network capacity by the spatial reuse of the network resources and reduce the effect of the hidden terminal problem. Moreover, to optimize the communication range and the cluster size is very difficult especially in a highly dynamic environment such as VANETs. However, in order to overcome this situation some approaches divide the service area into a set of region units, and limit the number of vehicles in each region unit for the contentions of radio channels. Each region unit is then associated with a non-overlapping radio channel pool. Since the number of vehicles in each region unit is limited, the contention period is reduced and the throughput is increased. However, these types of approach have low bandwidth utilization in case of sparse traffic. Some of clustering algorithms try to minimize the total number of clusters by creating hierarchical clusters with a diameter of at most four hops. In this section of the chapter, we compare well known cluster based MAC protocols in Table 3.

Protocol	CH Election	Cluster Formation	MAC	Scenario	Simulator	Pros	Cons
HCA; [25]	Maximum number of messages received from cluster relays is the CH.	Maximal; distance between a; CH and CM is two hops.	TDMA	City	OMNeT++,; SUMO	End to End delay reduced.	Overhead and packet loss is increased.; Do not consider the direction of movement.
Zaydoun; [26]	Vehicle nearer to middle of the cluster is the CH.	Not Specified	TDMA	City	C++ with graphical interface.	Support both safety and non-safety applications.	Not suitable for high traffic.; High overhead.
Xi Zhang [27]	No reception of a message longer than a particular; time units from a; CH, then it elects itself as CH.	RSS > threshold.	TDMA; in CMs-; CHs,; CSMA/CA; CHs-; CHs	Highway	Simone; 2000	Reduces data-congestion and supports safety messages.	High overhead and complex algorithm.; Require two transceivers
CBMAC [28]	CH is based on waiting period of Hello messages to neighbors.	Undecided state to CM based on reception of one CH messages.	TDMA	City	I-V; Communication; Based; on; Traffic; Modeling.	Minimizes the hidden terminal problem.	Does not select a stable CH during initial CH election.
RCM; [29]	No CH	Geographical area. Vehicles are assigned to different channel pools.	TDMA	Highway	A. law el al	Reduced contention and throughput is increased.	Low bandwidth utilization in sparse scenarios.
TCMAC; [30]	Lane weight, average distance, maximum number of neighbors, and average distance level.	Not specified	TDMA	Highway	Ns-3	Channel utilization, scalability, avoids hidden terminal problem, decreases collisions and packet drops.	Cannot be used for safety applications, it is delay intolerant.
CFIVC; [31]	Random after relaying one packet to ordinary node.	According to speed.	CDMA,; MCSCDMA	Not simulated	Not simulated	Avoids data collisions.	It neglects any condition that might affect the maximum speed achievable by the vehicle nodes.

Table 3.

Comparison between various cluster based MAC protocols.

The MAC layer is divided into different cycles and each cycle is divided into contention based or contention free. In the current literature, several MAC protocols have been proposed to VANETs. Some of the well-known MAC protocols are ADHOC MAC [32], SDMA [33], VeMAC [34], DMMAC [35], STDMA [36], VeSOMAC [37] etc. These protocols are proposed for various scenarios and have many drawbacks such as hidden terminal problem, time unbounded, unreliability etc. There is a need for new MAC protocol in VANETs that can provide mobility (i.e., the MAC protocol should support vehicles to leave and join inter-vehicle communications at high speed), delay bounded (i.e., the communication must be delay bounded and real-time), scalability (i.e., VANET should scale itself according to the number of vehicles present), bandwidth efficiency (i.e., the radio resource should be utilized in an efficient and fair manner), cost (i.e., for cost-efficient and reliable communications, VANET should be fully decentralized), and fairness (i.e., every vehicle should get a fair chance to get the radio channel).The challenge of successfully deploying VANET services is to ensure timely and reliable data delivery for mobile vehicles.

3.3.2. Clustering in network layer

In network layer clustering, a virtual network infrastructure must be created through the clustering of vehicles sharing similar characteristics in order to provide scalability. Routing protocols for VANETs mostly based on periodical broadcast messages to reveal their positions and traffic information to neighbors. Nevertheless, deterioration of routing performance is anticipated in urban areas due to high density of vehicles in the network. Basically, excessive broadcast messages as well as broadcast overhead may increase, resulting packet losses (due to collision) and significant routing performance deterioration. Information transfer or dissemination needs multi hop communications. When exchanging information between vehicles, there are network issues that must be addressed, including the hidden terminal problem, high density, high node mobility, and data rate limitations.

In multi-hop data forwarding method, the key problem is selecting the relay/CH for data routing. Most of the relay/CH selection method presented is more suitable for highway scenarios. In a city environment, the widely adopted method is the store-carry-forward scheme. Reactive protocols find routes on-demand. If a node wants to communicate with a node to which it has no route, the routing protocol will try to establish the shortest route between them. Here there is significant delay in determining the route. Proactive (table-driven) protocol, which is based on the exchange of control packets and it is continuously updating the reachability information in the routing table, so routes are immediately available when requested but there is high overhead in maintaining updated periodic routing tables and also maintains the routes that are not going to be used. Hybrid protocol is combination of proactive and reactive protocol. It is also known as cluster based routing. It is a convenient way for developing efficient routing scheme in VANETs. In Table 4 we compare between various cluster based routing protocols proposed in VANETs.

Protocols	Cluster or CH	Scenario	Simulator	Pros	Cons
TMRC [38]	Direction of vehicle after crossing the intersection	Intersection	NCTUns	Computed optimal length of cluster in an intersection.	Cluster overheads and delays are increased.
RMAC; [39]	Speed, location, and direction	Highway	Ns-2	Stable and less cluster; reconfigurations	Collisions and unreliable.
VWCA; [40]	Number of neighbors,; the direction, the entropy, and the distrust value parameters	Not simulated	Not simulated	Predictability and reliability is increased.	Volatility of dynamic transmission range
MOBIC; [41]	Variance of relative mobility with each of its neighbour’s.	Random	Ns-2	Reduces the cluster reconfiguration by delaying re-clustering for a certain period of time. To avoid accidental contacts between CHs.	Few neighbour nodes; move differently, the; method still results in dramatic increase in the variance.
AMACAD [42]	Relative distance, speed between neighbour’s and distance between vehicle and destination.	Urban	Java; JDeveloper; 10G	Increases the cluster and CH lifetime.	Problem with knowing the final destination a priori as drivers usually do not use navigation system for known routes.
MCDRIVE [43]	First vehicle in the direction is elected as CH	Intersections	NCTUns	Cluster stability is improved in intersections.	Increased overhead and delay.
APROVE [44]	Minimum distance; and minimum relative; velocity between each; CH and its CMs.	Highway	Ns-2,; VanetMobiSim	Cluster overhead and; re affiliation are reduced	It doesn’t consider destination of vehicles.; Not mention about CH election. Not suitable for intersections
ALM [45]	Variance in relative mobility	Box topology	SUMO,; SIDE/; SMURPH	Considers relative mobility to increase stability.	No direction of movement and position is considered for cluster formation. Overhead increased.
DBC [46]	Connection graph density, link quality, traffic conditions, node reputation and movement prediction.	Urban	JiST/; SWANS++; VanetMobiSim	Suitable for both sparse and dense traffic.	The destination of vehicles, speed of vehicles is not taken into account that increases the overhead.
Maslekar [47]	Location and direction of vehicles.	Intersections	NCTUns	Cluster stability is improved in intersections	Overhead and delay increased.
Maslekar [48]	The direction which the vehicle will take after crossing intersection. The CH is at the front of cluster.	Intersections	NCTUns	Improved the influence of overtaking within the clusters. accurate density estimation within the clusters.	Overhead and delay increased.

Table 4.

Comparison between various cluster based routing protocols.

3.4. CH election

CH selection is important to increase protocol reliability, scalability and delay. In some of CH selection algorithms proposed takes into account the destination of vehicles, including the current location, speed, direction, relative destination and final destination of vehicles as parameter to arrange the clusters. Many researchers have proposed CH election scheme based on ID. Each node is assigned a unique ID, and the node with the lowest ID in its two-hop neighborhood is elected to be the CH. Some algorithms calculate these ID based on the variance of relative mobility of a mobile node with each of its neighbors, where a small value of variance indicates the mobile node is moving relatively less than its neighborhood. Additionally, other approaches consider vehicles having a longer trip are more qualified for being elected as CHs.

A vehicle, which would travel longer time, is assigned higher priority; hence, at the very beginning of starting its travel, the expected travel time of a vehicle is calculated and announced using its desired driving speed and the geographic information system once its driver sets the destination. Te stability of the system is improved by electing the vehicles having a longer trip as the CHs. Furthermore, to avoid elected CHs losing connectivity with their neighbors very soon, the eligibility of a vehicle should decrease quickly when its velocity has big difference from the average speed. Thus, a vehicle with large speed deviation is assigned lower priority.

Another type of CH election scheme is based on connectivity level (estimating graph density), link quality (SNR), relative node position and the prediction of this position in the future, and node reputation. The vehicle which is near to that anchor point is elected as CH. Furthermore, some approaches assign generic weight to vehicles based on the position and other set of vehicle parameters like connectivity, mobility, RSS etc. The vehicle with the highest weight is elected as the CH amongst the neighbors. However, since the vehicles are highly dynamic in nature the position of the vehicles change very fast and hence may induce a computational overhead in calculating the weight associated with the vehicles.

In some of the clustering algorithm first vehicle entering into the cluster region is initialized as the CH. It changes from CH to CM due to the discovery of a closer CH, or until the last member of the cluster passes the intersection. However, CH stability is reduced due to distance between vehicle to intersection and due to different directions of vehicles. In some other schemes, the CH selection should resemble like a natural model of location references. CH re-election only occurs when two CHs move within range of one another for a certain contention interval. When a CM moves out of range of its CH, it joins any current CH in its neighborhood, or forms a new cluster. However, in the case in which few neighbor nodes move differently, the method still results in dramatic increase in the variance.

3.5. Cluster formation

Cluster formation is really important to avoid cluster reconfigurations. Some of the cluster formation techniques are based on position based clustering. In these types of protocols, each road is divided into cells and in each cell some anchor points are defined. The cluster structure is determined by the geographic position of the vehicle. Another type of position based algorithm is based on hierarchical and geographical data collection and dissemination mechanism. The cluster formation is based on the position of the vehicles at a particular segment instead of the individual positions. However, this type of protocols incurs more overheads for V2V and V2I communication. In some other approaches, each vehicle entering into the network collects the neighbor vehicles information, assuming precedence to each vehicle and polls each vehicle individually (according to precedence) to check whether it is CH or not and then joins the cluster. Also every vehicle in the network collects 2-hop neighbor’s information along with 1-hop neighbor’s information from the CH through periodic polling. These two information collection leads to more overhead in V2V communication.

Some clustering algorithms estimate the future mobility of nodes predicting the probability that the current neighborhood of a mobile node will remain the same. The drawback of the prediction method is the lack of accuracy in some cases. In some of clustering algorithms, the clusters are formed based on mobility metric and the signal power detected at the receiving vehicles on the same directed pathway. Through such method this type of protocol helps in forming stable clusters. However, it does not consider the losses prevalent in the wireless channel. In practical scenario effects of multi path fading are bound to affect the cluster formation method and thus the stability. These effects of multi path fading are taken into account in the density based clustering algorithm. The cluster formation is based on the weight metric which takes into consideration the link quality and the traffic conditions. It can be seen that the stability is improved compared to other approaches.

In some clustering approaches considers the behavior of the vehicles, using the speed and direction parameters.

The cluster formation is based on direction of vehicle at the approaching intersection. In other approach, cluster is formed based on distance and direction of vehicle it takes after crossing the junction. Some of the research enforces a weight cluster mechanism with a backup manager. These algorithms operate in similar way. Algorithms consider the position, direction, speed and range of the nodes to perform the algorithm. On the other hand, some takes into consideration the number of neighbors based on the dynamic transmission range, the direction of vehicles, the entropy, and the distrust value parameters. They works with an adaptive allocation of transmission range (AATR) technique, where hello messages and density of traffic around vehicles are used to adaptively adjust the transmission range among them. The destination of the vehicles is used as a parameter to arrange clusters.

In some approaches, the cluster formation interval is constant, which implies a synchronous creation of clusters. This does not allow for effective cluster reorganization. The directional based clustering algorithm are based on the following mobility metrics (a) moving direction (b) leadership duration (c) projected distance variation of all the neighboring vehicles over time. In practical scenario effects of multi path fading are bound to affect the cluster formation method and thus the stability. Some approaches take into account the destination of the vehicles to arrange the clusters and implements an efficient message mechanism to respond in real time and avoid global re-clustering. There might be a problem with knowing the final destination a priori as drivers usually do not use navigation system for known routes. Some algorithms are proposed for calculating the density of vehicles in a particular region around the junction. Moreover, other algorithms groups vehicles into clusters based on the competitive learning Hebb neural network. A suitable solution to prolong the cluster lifetime, stability, fairness, avoid congestion and overhead considering the vehicular behavior is essential.

3.6. Challenges of clustering

One of the numerous challenges clustering algorithms in VANETs is the mobile and dense communication topology. The main problem in clustering is the control overhead introduced to elect the CH and to maintain a stable cluster. The cluster structure assures the scalability of VANETs, where high mobility of the moving vehicles within the road causes lots of challenges to face. Location services might not provide the needed accuracy everywhere or will not be available at all so more work is needed on location independent clustering solutions. Providing highly accurate digital maps that are needed by some solutions presents a challenging task and could slow down the implementation so advantages and disadvantages of map based solutions should be researched.

In many papers the correlations between the transmission range and the VANETs density, packet transmit rate, packet size, data rate and channel conditions have been researched. However, the different network simulators should also be evaluated and presented with all the relevant parameters including MAC, transmission range, packet size, bit rate etc. Since each vehicle in the VANET has its own view of the network density and channel conditions, finding the optimal network parameters is difficult. The research should focus to the optimization of cluster size and transmission range that maintains a high VANET stability and reliability, increases the life time of a connection link, and at the same time decreases the time required for a safety message to reach its intended destination. Presented clustering protocols are designed for different aims e.g. overhead minimization, fast cluster creation, cluster stability, etc. The most important parameter among them is the cluster stability. Their tradeoffs and effects between them should also be analyzed and presented.

The vehicles with relatively high mobility, can pose difficulties for flat networks stability. Many of the presented protocols use metrics derived from the same input parameters where among them position and radio signal strength(RSS) are the most important. More research effort should be put in defining and ranking the aims that clusters and clustering protocols should try to achieve. One of the goals is to optimize the mean number of created clusters and the number of CHs at each time step.

For performance evaluations of clustering protocols common parameters used are cluster stability, CH election, cluster size, cluster delay, cluster reconfiguration and cluster overhead etc. These terms are quite generic so their definition and explanation with VANET specifics is needed to provide consistency between different researches. More focus should be put on evaluation of those common parameters to highlight the most useful ones, merge similar ones etc. This would help researchers to concentrate their research on extending and designing the most prospective ones. Fair comparison of different clustering protocols is a hard task due to non-existent standard testing procedures and scenarios so more work and standardization is needed in this area. The characteristics of different scenarios of VANETs and different parameters are explained in detail in later sections.

3.7. Scenarios

In highway scenarios, it is widely recognized that traffic generally follow a platoon pattern according to traffic flow theory. Vehicles in a platoon generally move with similar velocities and are likely to sustain a stable wireless communication in clusters. The clusters are independently controlled and dynamically reconfigured as the vehicles moving. Congestion can occur in highways during an accident so the clustered protocols should be designed to effectively reduce data congestion in high density scenarios, and satisfying QoS requirements. Furthermore, the design of cluster protocol should also consider the market penetration of vehicles enabled with OBU´s. In some cases, there can be a large number of vehicles in road that are not enabled with OBU´s. This creates a large gap between vehicles and resulting in poor communication. The future clustering protocols should consider all the characteristics of highway scenarios.

A large number of the available cluster based MAC and routing protocols are purposed for highway environments and does not address the various requirements of the city and urban traffic environments. In city environments, intersections play important roles for information exchange. The vehicle that crosses the intersection before actually receiving a message is defined as the unstable vehicle. As the intersection area is comparatively small and the probability of change of direction is very high, it will be risky to choose an unstable vehicle as the CH from these clusters. Moreover, during rush hours of day intersections are usually the bottlenecks.

Vehicles in intersection can take any of the direction Straight (S), Right (R), Left (L) and U-Turn (U) respectively. All the incoming vehicles of two road segments of intersection may be blocked by the red signal, whereas vehicles on the other two road segments flow until the green signal is on. When a vehicle crosses the intersection without having another vehicle arrive at the intersection, a disconnection may occur. Such a situation arises only when a fleet of vehicles has crossed the intersection and when another fleet of vehicles has not been arrived at the intersection. Based on the motion of vehicles, some approaches form clusters S, R, L and U on a particular lane. The created clusters consist of vehicles moving in the same direction. Within the same cluster the vehicles communicate with each other and elect a CH that is responsible for calculating the number of vehicles in its cluster. This information will help to avoid constant cluster reconfigurations and overhead by creating another cluster.

For intersection collision avoidance, the amount of traffic generated by vehicles can be determined by a number of factors such as the cluster size, the number of intersection per cluster, the number of vehicles per intersection per cluster, the size of messages, and the transmission interval.

3.8. Cluster size

The size of the cluster is a crucial parameter. To optimize the cluster size is very difficult especially in a highly mobile environment such as VANETs. One of the goals of optimal protocol is to optimize the number of CMs to decrease the end to end delay of messages. If the cluster size is decreased, the channel contention within each cluster decreases. However, the number of CHs is increased, so that the resulting virtual network formed by these CHs will become more complex. There is then a tradeoff between the cluster size and the number of CHs. Cluster size is variable according to vehicle density, speed and required minimum bandwidth or QoS where parameters can be predefined or provided on the fly from vehicle sensors and application profiles.

The cluster size can be controlled by a predefined transmission range between a CH and its CMs. Optimal cluster size and hence the transmission range that maintains a high VANET reliability, stability and scalability, increases the life time of a communication link, and at the same time reduces the end to end delay for a safety message to reach its intended destination. Optimal cluster size is both related to the radio transmission power and vehicle traffic density. Therefore, cluster size may limit radio efficiency and throughput. For the cluster protocols, we have so far assumed that transmission power is fixed and is uniform across the VANET. There are different methods to reduce the cluster size by reducing transmission power. There is different power control protocols proposed but most of them are oscillating because of the fast varying vehicles densities in VANETs. Selection of optimal power control algorithm and vehicular densities will reduce the end to end delay, reliability and fairness.

Optimal cluster size is also determined by the correlation between spatial reuse of the medium (which leads to small numbers) and end to end delay minimization (which lead to large numbers). Other parameters also apply, such as geographical area and power consumption.

3.9. Stability

Stable clusters are important for a reliable and efficient information exchange. Stable clustering techniques decrease the control overhead of cluster reconfigurations and led to an efficient hierarchical VANET topology. The main condition for stability is the duration of residence´s times of a cluster and its CHs. Stability is also defined by long CH lifetime, and long CM lifetime.

3.9.1. Cluster stability

Cluster stability is based on the selection of suitable CMs to ensure greater cluster lifetimes by reducing cluster re-configuration events. Cluster stability also depends on the different vehicle densities. To be able to form stable clusters of one hop vehicles, vehicular movements should be taken in to account. Speed and location data transfer is a usual procedure in most of the cluster-based routing protocols. Nevertheless, this needs two additional communication rounds (for speed, location and relative stability data transfer) and stationary assumption of vehicles prior to cluster creation. Cluster stability can be defined as the average number of cluster changes throughout the simulation and the percentage of time in which vehicles were CMs, represented as association time. In practical environment effects of multi path fading are bound to affect the cluster creation method and thus stability. In some cases, nodes in cluster are linked to cluster rather than CH. This increase furthers the cluster stability.

3.9.2. CH stability

The time during which a node is in the state of a CH determines stability. It is the mean time duration of the nodes, remaining its leadership role as CHs. Long CH lifetime implies, few changes and good stability. The information is disseminated by groups enhancing the communication delay, reliability, low data delivery and congestion issues, making the vehicular networks accurate and efficient. CH stability can be affected by different factors such as merging, distance between CHs, exit from the road etc. In VANETs, merging collisions can happen among vehicles moving in the same direction due to acceleration or deceleration, it is more likely to occur among vehicles moving in opposite directions (approaching each other) or between a vehicle and a stationary RSU since they approach each other with a much higher relative velocity as compared to vehicles moving in the same direction. The high mobility of the shifting nodes within the networks causes lots of challenges to face and affects stability.

If vehicles are changing their state very often in intersection scenarios and stay only for short times in the CH state, CH stability is low. In some of intersection based approaches the first vehicle to enter the intersection region in a particular direction is elected as CH to improve stability. Furthermore, some cluster-based routing algorithms, the selection of CH are based on willingness factor which defines the relative stability of a node. CH stability is also based on the threshold distance between the two CHs. Optimal distance between two CHs should be obtained.

3.9.3. Cluster delay

Cluster delay means the time required for sending one message from source to destination (it can be here from CM to the RSU or vice versa). The delay parameter is very crucial for safety applications. The end to end delay can be minimized by selecting proper cluster size, selection of proper MAC protocol to reduce the channel access time, selection of stable CH nearer to the RSU, a selection of proper routing algorithm between CH transmissions. The number of the formed clusters is important to reduce the end to end delay for message transmission.

3.9.4. Cluster reconfiguration

The frequent cluster reconfiguration generates tremendous communication load, which significantly reduces available bandwidth for message dissemination. Cluster reconfiguration is needed in some cases when the CH leaves the group or numbers of CMs are below the threshold or the distance between two CH is below the threshold. In some approaches, if the distance between two CH nodes is detected less than the particular threshold, the cluster with fewer CMs is dismissed to reduce communication overheads while it’s CMs join other clusters. One can expect that a larger dismiss threshold leads to a higher rate of CH changes and higher probability of cluster reconfiguration. The threshold determines the rate of cluster reconfiguration, and also, depends on the radio transmission range and vehicular densities. Larger transmission provides longer distance for CHs to detect each other, and therefore, more frequent cluster reconfigurations occur. Additionally, some algorithm elects backup CH to avoid cluster reconfigurations. However, most of the protocols are not fit for different traffic situations. The aim should be to design protocol with less cluster reconfiguration in various scenarios.

3.9.5. Cluster throughput

Data rate transfer that gives the total number of received packets at the destination out of total transmitted packets. An access collision happens when two or more CHs within two hops of each other attempt to acquire the same available time slot.

3.9.6. Cluster overhead

Clustering requires explicit clustering-related information exchanged between node pairs. Clusters cannot be formed or maintained by non-clustering-related messages, such as routing information or data packets. The main challenge in clustering is the communication overhead introduced to formation and maintenance of a stable cluster, and elects its stable CH. Most of the recently proposed protocols discuss mainly on how CHs are selected. The control overhead for the creation and reconfigurations of clusters have not been considered completely. There have been not many papers that analyze analytically the control overhead incurred in hierarchical routing. Furthermore, the overhead is bound by a constant per vehicle per time step, avoiding expensive re-clustering chain reactions; hence, this overhead increases with the number of nodes. Since a CH acts as a coordinator in a cluster, if it is absent for any reason, the clustering architecture has to be reconfigured; this will significantly increase the message overhead.

Communication complexity represents the total amount of clustering-related message exchanged for the cluster formation. For clustering schemes with ripple effect, the communication complexity for the re-clustering in the cluster maintenance phase may be the same as that in the cluster formation phase. But for those with no ripple effect, the communication complexity of re-clustering should be much lower. From analysis of different clustering protocols, we believe that a more efficient way to form a stable network structure, with reduced overhead, are that a vehicle should be associated to a cluster and not to a CH. Indeed, replacing CH is considered only as an incremental update and does not require a whole reconfiguration of the cluster structure; this will definitively increase the lifetime of the clustering architecture. The resulting clusters are stable and exhibit long average CM duration, long average CH duration, and low average rate of CH changes. The cluster creation and maintenance overhead should be calculated to be compared with non-clustering algorithms in terms of the reliability, fairness, and scalability of the algorithms. By optimizing cluster stability, cluster reconfiguration, number of clusters and cluster size can reduce the overhead caused in clustering.

4. Conclusions

In this chapter, we have surveyed in-depth of the challenges of reliable communication for cooperative ad hoc networks especially VANETS. First we have provided state of the art of ad hoc networks and various types of ad hoc networks.

In a scenario where nodes are moving fast and the topology of the network is changing continuously, the big challenge is to keep connected all the nodes and give all of the them resources to transmit and receive information in real time. In VANETs, dissemination algorithms provide to the drivers mechanisms to be aware in real-time of events that are happening in their surroundings: traffic and road conditions, closure and detour information, incident information, emergency alerts, and driver advisories. Clustering is an approach that divides the nodes of the network in groups of vehicles according to common characteristics as their position or speed, in order to create a more robust and scalable network. This structure can be a realistic approach to support reliable and scalable multihop communications in a mobile network as a VANET

This chapter focused on identifying the research trend of the cluster based MAC and routing techniques that have been recently proposed for V2I and V2V communications. Furthermore, we discussed the advantages and disadvantages of various MAC protocols that have been developed recently. Moreover, we have presented a comprehensive review of the cluster based routing protocols for inter-vehicle and vehicle-to-infrastructure communication. Cluster based routing protocol is the most appropriate technique for developing reliable, scalable and predictable routing protocols in VANETs. However, due to the distinctive attributes of V2V and V2I communications, it raises several open issues and areas for research, such as fairer usage of network resources and channel access. Because of varying vehicle density and varying speed of vehicles makes communication reliability, a challenging issue.

Our research group is focusing on developing data dissemination and cluster based protocols by identifying common characteristics and parameters to improve cluster lifetime, communication link among vehicles, and channel access. We have also discussed some important issues that must be addressed for safety and non-safety applications. Future protocols need to effectively consider these problems while fully exploiting the distinctive distributive and ad hoc nature of these networks to meet real time applications.

Acknowledgments

The authors would like to thank the EU Intelligent Cooperative Sensing for Improved traffic efficiency (ICSI) project (FP7-ICT-2011-8) for its support in the development of this work.