Application-based taxonomy for routing protocols according to traffic density in VANET (Ducourthial & Khaled, 2009)
One of the new networking concepts which was born during the last decade is the communication between cars using short range wireless solutions, known as VANET (Vehicular Ad hoc NETwork). Despite the significant research efforts the VANET are still in the infancy and so far there are no implementations. In fact the VANET concept imposes a lot of serious problems, which so far have been resolved only partially. The most important problem is the intermittent connectivity of VANET nodes caused by high mobility of cars. The high dynamics of cars combined with usage of short range communications make the connectivity among the cars very unstable, so even the best effort service cannot be guaranteed. Of course, the communication quality differs in cities during traffic jams (where we may obtain dense and stable networks) from one in highways (where the VANET network is sparse and the topology is highly dynamic). Due to the variety of communication scenarios it is very hard to predict the generic transport characteristics of VANET networks. It is worth to mention that there have been created many routing protocols for VANET. Unfortunately, most of them are focused on specific scenarios only. Another VANET problem deals with the definition of services suitable for these networks. VANET can be used for safety applications (this is the primary goal), for driving support information services (information about parking places, points-of-interest, etc.) and, in some concepts, it can offer classic Internet services including high quality media streaming. Of course, the above mentioned VANET problem with highly unreliable communication will limit the service portfolio in the same way as it is observed in other networks. It has to be noted however, that in VANET the diversity of communication quality is enormous; in some situations high quality links of high throughput can be created (in case of parked cars) but at the other extreme there is highly intermittent communication which enables only the exchange of short messages between the nodes (the highway case). The next VANET specific problem is related to the identification of service recipients and the way in which the information is disseminated among them. It has to be noted that the client-server model, very popular in the Internet, has only limited or even no usage in VANET, because such networks are generally server-less. Using node address for service delivery also has limited usage, because it characterizes neither a node nor its service requirements. The classic unicast communication has very limited usage as well. The range controlled broadcast, multicast (if groups are identified) or anycast in some cases are better suited for, and in many (though not all) cases the geocasting is a solution of choice.
A very important problem concerns the incremental deployment of VANET and is linked to VANET business model. There is no doubt that the deployment of such networks will progress gradually, and it is expected that VANET nodes will be built in cars by car vendors. That way only new cars will be equipped with VANET nodes and it will take years before almost all cars will have them on board. Of course, such slow deployment creates several important issues; in the beginning the VANET nodes density will be extremely low resulting in sporadic communication only. On the other hand, in coming years, due to the technology progress, new and more advanced VANET concepts can be developed. The last problem calls for an open approach to VANET architecture that is able to accommodate new concepts on the component basis.
In this chapter we present a unified architectural VANET framework, called CARAVAN (Context-AwaRe Architecture for VANET), which is aimed to cope with all problems mentioned above. This framework is able to simultaneously handle different communication schemes (including disruption tolerant networking), to deal with rich service portfolio adapted to communication limitations, and to accommodate most of algorithmic concepts designed for VANET. The unified framework behavior and adaptation is driven by contexts (context-aware approach). Contexts are related to service/application requirements, communication ability, mobility vectors and the mutual space-time relations of cars/nodes. In the proposed approach the communication scheme is based on multiple protocols. The selection of the protocol is made accordingly to the quality and stability of links that typically depend on the distance between the nodes and on the mobility vectors. The heart of the proposed concept is the context engine which processes context coming from different layers of the architecture.
In Section 2 of this chapter a short introduction to VANET which will help in the understanding of the proposed solution is presented. Section 3 contains the related work and short review of main algorithmic concepts which are applicable to VANET. Section 4 is the main part of this chapter and it contains the CARAVAN concept description together with the description of its implementation and sample use case. Section 5 concludes the chapter.
2. Vehicular ad hoc networks
Vehicular ad hoc networks (VANETs) have recently become an important research area with contributions split between government and industrial consortia, as well as the academic community. Current efforts focus on the design of a new set of vehicular applications and services improving the comfort and security of the driving experience. The specification of this type of mobile networks enables many new possibilities, but from the other side it creates many non-trivial challenges. This section is a very short introduction to VANET. Much more detailed descriptions of VANETs can be found in (Olariu & Weigle, 2009) and (Moustafa & Zhang, 2009).
Vehicular ad hoc networks can be considered as a special case of mobile ad hoc networks (MANETs). However, there are several important factors, which make this type of networks specific and which allow to treat them as a separate category. Here are the fundamental VANET features:
Very high dynamics of nodes resulting in fast topology changes. As the communication devices are installed inside vehicles, the network nodes are much more mobile and they move with much higher speeds. Vehicles are restricted to move using roads and to abide by the traffic rules, so some mobility patterns can be observed and some statistical mobility models for VANET have been designed (Härri et al., 2006).
Information about the current position, movement direction, current velocity, city map and planned movement trajectory of VANET nodes is available, as more and more vehicles are equipped with GPS devices and navigation systems.
VANETs impose lack of energy constraints, higher computational power and practically unlimited memory capacity, in comparison to some other ad hoc networks (especially to sensor networks).
VANET networks are usually of very large size (case of traffic jams) but also may exist in a form of many small, neighboring networks with a high probability of splitting and joining.
There is a big diversity of VANET services and applications, and one-to-one communication is less important than some intelligent broadcast (for example geocast) required by most safety related applications.
Besides the scenarios when vehicles communicate only with each other (sometimes called Vehicle to Vehicle (V2V) or Car to Car (C2C) communication) there exist two other scenarios which also distinguish VANETs from MANETs. Some research studies consider a case of communication between vehicles and fixed roadside equipment (Vehicle to Infrastructure (V2I) or Car to Infrastructure (C2I)). Such communication can be used for Internet access or in some new vehicular applications, e.g., vehicles exchanging data with a service station while being in repair. Last scenario is a hybrid case when vehicles can be treated as relays to increase the range of ground services.
2.2 Services and applications
VANET services and applications differ significantly from the classic ones known from MANETs. Possibly the most important group of services, which makes research studies on VANETs increasingly popular, are those related to driving safety. Safety applications include among others: current traffic reports dissemination, road obstacles warning (accidents, works and other unusual situations), driving maneuvers assistance (vehicles overtaking, lane changing) or traffic-aware trajectory planning.
Another group of applications which can gain popularity among road users are infotainment services. The most basic ones are related to advertising – distributing information about free hotels rooms, restaurants offers, discounts in stores, etc.. Gasoline prices, information about free parking spaces of the nearest service station can also be disseminated. Probably such services will have to be extended by some publish/subscribe mechanisms, so that driver is not spammed with a number of unwanted messages. Some infotainment services can be also useful for pedestrians – e.g., buses can estimate time of arrival at the bus stop using knowledge about traffic conditions and then distribute this information to the waiting passengers.
Some one-to-one services can also be considered, but probably they can be applied only in the limited range because of highly intermittent communication. Much more applications will be based on the intelligent context-aware data dissemination.
2.3 VANET related projects
Vehicular ad hoc networks are a hot topic nowadays, so many researchers are involved in national and international consortia leading great number of projects related to different challenges in this area. The best known consortia are Car 2 Car Communication Consortium (C2C-CC) (Baldessari et al., 2007) in Europe, Vehicle Safety Consortium (VSC), Collision Avoidance Metrics Partnership (CAMP), Vehicle Infrastructure Integration Consortium (VIIC) in United States and Advanced Safety Vehicle (ASV) in Japan. The Intelligent Car Initiative (Reding, 2006) is one of the biggest initiatives of the European Union which aim is to investigate the potential of information and communication technologies in improving life quality – also by development of intelligent vehicular systems in order to make cars smarter and safer. Here is a short list of selected projects related to VANETs:
FleetNet (Franz et al., 2001) – a pioneer research project investigating the direct communication between cars,
Network on Wheels (NoW) (Festag et al., 2008) – the successor of FleetNet which aimed at developing an open communication platform designed for safety, traffic efficiency and infotainment purposes,
PReVENT (Schulze et al., 2005) – a R&D project on the use of different technologies to help the driver to avoid an accident with two main issues being investigated – wireless local danger warning and intersection safety,
Co-operative Vehicle-Infrastructure Systems (CVIS) (Mietzner, 2007) – another R&D which is focused on providing methods for continuous V2I communication and cooperative services in order to increase road safety and traffic efficiency,
SAFESPOT (Giulio, 2007) – a project designing Safety Margin Assistant which should help to detect in advance the dangerous situations and to make a driver more aware of the environment surrounding,
SeVeCom (Leinmüller et al., 2006) – a project focusing on the security and privacy issues in vehicular communication.
Beside pure research oriented projects trying to resolve particular problems there is also whole big branch of consortia involved in regulation and standardization activities. Car-to-Car Communication Consortium composed of about 50 partners is working on the industry standard for vehicular communication using wireless LAN technology. An institution playing a major role is the European Telecommunications Standard Institute (ETSI) with a new technical committee for Intelligent Transport Systems (TC ITS). Different working groups are focusing on application requirements, architectural and cross-layer issues, transport and network, media and related issues, and security. CEN is the European Committee for standardization – it is a private and non-profit organization which works on such issues as electronic fee collection, dedicated short-range communication (DSRC) and identification of vehicles. Another standardization works are done by ISO and Internet Engineering Task Force (IETF).
A comprehensive review of the VANET related European consortia, projects and standardization activities can be found in (Le et al., 2009).
3. VANET supporting concepts – state of the art
The characteristics of the VANET listed in Section 2.1 call for a specific approach to VANET. It should consider proper routing in very dynamic network, content dissemination, service specific issues and finally a security and privacy. In fact some concepts developed for mobile ad hoc networks (MANET) that have been studied for a long time can be reused and adapted to VANET, however some VANET specific properties may require completely new approach. This chapter provides a short overview of the most popular concepts which were developed for VANET. This overview is very important in the context of the CARAVAN that has been designed in order to obtain the synergy by integration and dynamic selection of the already developed VANET algorithms.
3.1 Routing protocols
The detailed survey of routing protocols in the context of vehicular networks can be found in (Ros et al., 2009), which has been a main guide for creating this review.
The design of the routing protocols for VANET is especially challenging task due to the high mobility of nodes, large network size and the intermittent communication. The first attempts base on the usage of routing protocols developed for mobile ad hoc networks (MANET). These protocols can be divided into four groups – proactive, reactive, hybrid and geographic routing. In proactive routing, the paths between all pair of nodes are determined in advance, i.e., before they are needed. The most popular proactive protocol is Optimized Link State Routing (OLSR) (Clausen & Jacquet, 2003) in which the nodes discover network topology using beacon messages. Knowing the topology each node computes the shortest paths to all possible destinations and stores the next hops in its routing table. OLSR is a good approach for dense, small and relatively static networks, thus it can be applied to stable groups of VANET nodes. The reactive routing protocols try to find the path to the destination only when it is needed. Two most known protocols belonging to this category are Dynamic Source Routing (DSR) (Johnson et al., 2001) and Ad hoc On Demand Distance Vector (AODV) (Perkins & Royer, 1999). The first one finds a path to the destination by broadcasting route request messages into the network. Each node forwarding the request updates it by adding itself to the path. When the message achieves the destination it contains the complete path. The DSR protocol includes some optimization and the path maintenance procedures. Each packet sent from the source to the destination stores the path in its header – this is a big drawback in large networks, where routes are usually long. The AODV protocol uses quite similar approach but the paths are stored in the routing tables of the nodes instead in packets themselves. Each node builds such table whenever it is possible by storing next hop nodes on the paths to the destinations. The mechanism of the sequence numbers in route request packets guarantees loops freedom. Reactive protocols can handle well the dynamic topologies. Unfortunately, they are not well suited for large static networks, thus they can be used in limited ranges in city scenarios with increased nodes density, but not necessarily in case of traffic jams.
The main representative of hybrid routing protocols category is Zone Routing Protocol (ZRP) (Haas & Pearlman, 2001). All nodes have assigned their own zone including all neighbors that are at most k hops away, where k is a protocol parameter, which can vary depending on external conditions. Inside this zone the proactive Intra-Zone Routing Protocol (IARP) is used while to communicate with peripheral nodes the reactive Inter-Zone Routing Protocol (IERP) applies. This approach splits the network into interconnected zones, which provides increased scalability. Unfortunately, the criterion for the network split (i.e., the hop distance) has limited value in VANET.
The protocols belonging to the categories mentioned above can be used in vehicular networks, but they do not match well all possible VANET communication scenarios. The main drawbacks of these protocols are: scalability, incorrect assumption about full network connectivity and extensive use of flooding, that leads to high consumption of network resources and increases the contention to medium access as well as communication latency. Another important issue is that the paths established in VANET are usually valid only for short period of time, as a result of high mobility of nodes. These protocols usually do not take into account the VANET specific features, such as the access to information about the geographic position, city maps, node trajectories, mobility constraints and possibilities to predict the movement of nodes in the near future that is based on mobility patterns. However, there are also so called geographic routing protocols that use the information listed above.
The first geographic routing protocols were simple greedy algorithms. In Greedy Scheme (GS) (Finn, 1987) approach the forwarding node as a successor chooses a node assuring the greatest progress. In Compass Routing (CR) (Kranakis et al., 1999) protocol the idea is very similar but the choice is based on the smallest angle between the line to the destination and the line to the neighboring node. The Most Forward within R (MFR) (Takagi & Kleinrock, 1984) approach deals with loops problem which can occur in the previous concepts. One of the most important solutions in this category is Greedy-Face-Greedy (GFG) (Frey & Stojmenovic, 2006) protocol, which uses some simple geometrical properties of planar graphs. The nodes transform the network connections graph using some localized planarization algorithm and then they try to follow adjacent faces intersecting the line to the destination. These protocols form a good foundation for further work on geographic routing protocols optimized for vehicular networks.
Another group of geographic routing protocols can be characterized as source routing. The Geographic Source Routing (GSR) (Lochert et al., 2003) protocol tries to use a street map to find the shortest path with Dijkstra algorithm. The route is represented by a list of streets intersections. Then greedy forwarding is used to deliver packets between junctions on the list. The Spatial Aware Routing (SAR) (Reichardt et al., 2002) is a modification of GSR which deals with a local maximum problem (it appears when there is no node to which we can forward a message and make a progress). SAR introduces buffering of packets in nodes which are not able to forward immediately. Such nodes wait a predefined time for the suitable successor before dropping a packet. The next protocol named Anchor based Street and Traffic Aware Routing (A-STAR) (Seet et al., 2004) makes use of information about road traffic and tries to find a path consisting of road segments with the greatest possible traffic density. The Connectivity Aware Routing (CAR) (Naumov & Gross, 2007) protocol is based on similar idea of building a path using crossroads instead of nodes, but it achieves a goal without a map access. During the route finding phase the nodes which are close to the crossroads add their locations to the created path (so called anchor points). Moreover, such nodes create dynamic guards in the neighborhood of anchor points which are later used during packet forwarding.
The next set of geographic routing protocols is represented by Greedy Perimeter Coordination Routing (GPCR) (Lochert et al., 2005). As in CAR protocol there is no assumption on the street map data. The nodes which are near the junctions become coordinators and using beacon messages they build virtual topology graph with streets as edges and junctions as vertices. When such coordinator receives a message to forward, it makes a decision about the correct street to push it there.
Table 1 taken from (Ducourthial & Khaled, 2009) clearly shows that there is no single routing protocol that is suitable for all vehicular scenarios. Not all of them are mentioned in the presented short summary of the routing solutions. Reader will find a nice survey of the protocols in the book chapter mentioned above.
|Traffic Kind||Communication Kind|
|Adapted to sparse networks||Epidemic, MDDV, VADD||Epidemic, MDDV, VADD||Epidemic, MDDV, VADD|
|General||AODV, DSR, OLSR||DREAM, GSR, MGF, MORA, MURU||DRG, GAMER, IVG, LBM, MGF||RBM, TRADE||DREAM|
|Adapted to dense networks||CBRP, HSR,||CAR, GPCR, GPSR||GeoGRID||LBF, OABS, ODAM, SB, OTIS, UMB|
3.2 Location services
There is a silent assumption of many geographic routing protocols that nodes know the destination position. Depending on the applications, the requirements for location can vary considerably. Node position data and sometimes street topology obtained from GPS navigation system are usually sufficient. Other techniques for obtaining position of nodes include dead reckoning, which works well for short periods of GPS unavailability, cellular localization and relative distributed ad hoc localization. For many services information such as maximum range or direction of message propagation is enough. For the others – especially based on one-to-one communication – quite detailed knowledge is required. Some protocols (like GSR) find the destination node by flooding route request messages and only if this phase ends with success they can use their geographic properties. Other protocols use various independent location service mechanisms. For example in the CarTalk2000 project (Reichardt et al., 2002) nodes position is distributed only to nodes within a given number of hops. Researchers involved in FleetNet project proposed Grid Location Service (Li et al., 2000) using some nodes as “location servers”, and Reactive Location Service (Käsemann et al., 2002), finding position of destination on demand. The V-Grid (Gerla et al., 2006) approach is based on two complementary location services – one in infrastructure network and the second in vehicular network. Node looking for destination position has to communicate with the nearest fixed infrastructure point providing location information.
Nodes clustering algorithms are useful in order to identify “similar” or close in terms of the predefined clustering metric nodes and form their groups (clusters). Clustering in the routing enables partitioning of the whole network into smaller subnetworks, thus in some cases resolves the scalability problem of routing. In dynamic networks clustering helps to identify the regions of relatively stable topology. Having a partition of the network nodes different protocols can be used for the communication inside the clusters and outside of them (hierarchical routing). Examples of routing protocols that use clusters are Clustered OLSR (COLSR) (Ros & Ruiz, 2007) and Directional Propagation Protocol (DPP) (Little & Agarwal, 2005). There also exist pure clustering algorithms such as Modified Distributed and Mobility Adaptive Clustering (Modified DMAC) (Wolny, 2008) or Density Based Clustering (DBC) (Kukliński & Wolny, 2009), both of which use mobility patterns and nodes behavior prediction to form stable clusters. Another possible application of clustering technique is the automatic identification of user groups that can be interested in the same kind of services.
In conclusion, the clustering technique is a powerful mechanism and can have various applications in VANET.
3.4 Content dissemination
One of the biggest challenges in vehicular networks, besides the high mobility of the nodes causing constant topology changes, is the intermittent communication. In such environment it is extremely difficult to achieve a reliable content dissemination between the nodes. In VANET it is very common that the path between the source and the destination is not only unstable (has very short lifetime), but often it simply does not exist. Due to the high dynamics of nodes and the use of short range communication of VANET radio interfaces a permanent communication between the nodes cannot be guaranteed. A possible solution to this problem is the usage of some roadside fixed infrastructure or some additional communication channel, e.g., cellular networks. Such solutions have some obvious drawbacks like limited range (the first approach) and high costs (the second one). Another possible way of dealing with this problem is to use the Delay-Tolerant Networks (DTN) approach. DTNs are the main research topic of the Delay-Tolerant Networking Research Group (Fall & Farrell, 2002), which is focused on the application of DTN to satellite communications. DTN also has easily observable disadvantage, because it can be applied only for services which are not delay aware. Fortunately, in many potential VANET applications longer delays are perfectly acceptable – just to mention infotainment and traffic control services or even some safety ones, e.g., when the nodes have to spread information about some road obstacles.
The main idea of DTN is to aggregate messages into so called bundles. Bundles can be stored in nodes buffers when the immediate forwarding is not possible and forwarded later, when the communication is established again. This communication paradigm sometimes is described as store-carry-forward, which means that nodes have a possibility to place bundles in their local buffers and then carry them until a proper node, to which the bundle should be forwarded, is found. In case when no destination node is reached in a specific period of time, the bundle is discarded. It is clear that DTN forwarding decisions are more or less effective depending on the quality of information about network topology and mobility vector of nodes. DTN routing protocols can be split into deterministic and stochastic ones. Their common goal is to maximize delivery probability while minimizing the delay. Some deterministic DTN protocols assume that almost full knowledge about the network and its future topology evolution is given, sometimes even with the possibility to affect nodes behavior in order to optimize communication. Such assumption does not make sense in vehicular networks. A category of protocols which best suits the vehicular environment can be described as passive stochastic routing protocols. Epidemic Routing (ER) (Vahdat & Becker, 2000) is an exemplary protocol belonging to this group. The idea is trivial – nodes carrying the bundles forward them whenever it is possible. This protocol works well in networks with large buffers, long interaction between nodes and low network load. In such a case the Epidemic Routing assures minimal delays and high success rates. It is the most popular benchmark for performance evaluation of newly designed algorithms. Another popular DTN routing protocol is called Spray and Wait (Spyropoulos et al., 2005) – this time the number of forwarded bundle copies is limited by a certain threshold. Moreover, there is also a Wait phase, during which nodes try to deliver bundle straight to the destination. If they do not succeed the new Spray phase begins. The interesting observation is that with increasing network density the lower copies threshold is needed for the same protocol performance. A slightly different solution is used in Probabilistic Routing Protocol using History of Encounters and Transitivity (PROPHET) (Lindgren et al., 2004), where nodes estimate probability of delivering message to each possible destination.
Research studies on DTN routing protocols for VANET resulted in a development of several new concepts. The Vehicle Assisted Data Delivery (VADD) (Zhao & Cao, 2008) uses knowledge about stree topology, mean traffic density, average and maximum speed on each each street in order to select a path with the smallest expected delivery delay – for example in case when there is no direct connection between source and destination the node will try to select streets with higher nodes speed and density so that vehicles carrying packets can do it faster. Motion Vector Scheme (MoVe) (Lebrun et al., 2005) is a solution which uses information about neighbors velocities to choose node which makes the biggest progress towards destination. Geographic Opportunistic Routing for Vehicular Networks (GeOpps) (Leontiadis & Mascolo, 2007) is a trajectory-based protocol which uses the vehicular mobility patterns properties as well as assumption that each node knows its complete trajectory from the navigation system.
A more detailed survey of DTN solutions for VANET can be found in (Shao et al., 2009). There is no doubt, that DTN is a viable content delivery solution which can not be ignored in VANET.
3.5 Context aware mechanisms
In the descriptions of VANET related concepts presented in the previous sections there is one common property of the majority of presented solutions – i.e., the use of the knowledge about the network, nodes environment and the mobility, in order to make optimized decisions. The collected information concerning the node itself as well as the network can be treated as node context. Using contexts led us to so called Context-Aware Networks paradigm. In case of VANET the Node Context may consists of, among others, node position, velocity vector, neighborhood information, street topology together with information such as vehicles density or speed limits, planned movement trajectory, communication capabilities, services in use and many more. All this context data can be used by the routing protocols to increase their performance. In VANET we may also use the context-awareness for efficient data dissemination. On the context basis we may use message addressing instead of node addressing; the message destination is described by the context, e.g., location or maximum distance from the source, not by a destination or identifier (e.g., the IP address). The message context can also include information about time validity of the message, priority or service requirements, e.g., whether it is delay tolerant or not.
One of the interesting approaches to data dissemination is called Conditional Transmissions technique (Ducourthial et al., 2007). Authors assume that most of the applications require in fact broadcast communication and the receiver can be described by some set of conditions. As the consequence to deal with highly dynamic environment the conditional addressing is considered instead of network addressing, the path maintaining instead of traditional unicast and the conditional transmissions instead of broadcast. Each application can use its own conditions (e.g., the geographic information, the time-related information, the trajectory related information, the node identity related information, any combination of the above or even more) to define destination nodes. Conditional transmission service has been implemented (it is called HOP) and in some simple scenarios it has proved to behave better than many existing routing protocols.
3.6 Security and privacy
Security and privacy issues – although it is a topic of great importance, especially as far as safety services are concerned – have not gained yet a big attention in VANET research community. Insecure safety services can lead to a counter effect. Gaps in privacy data protection can result in poor driver interest. Without going into details, there is a possible attack classification, which shows the challenges in designing security system for vehicular networks. It should be resistant to both internal and external attacks, where internal attacks are those by authenticated users and they can be the most dangerous ones. Another distinction is on intentional and unintentional attacks, with the second type caused usually by communication errors. There exist active (modification of network traffic) and passive (captured data used for later unauthorized use) attacks. We can also split attacks into independent and coordinated ones. The main security challenges for vehicular networks include real-time constraints, data consistency liability, low tolerance for errors, key distribution and high mobility of the nodes. Some security requirements which should be at least taken into account are: availability, message integrity, confidentiality, source authentication, mutual authentication, authorization and access control, non-repudiation and privacy protection. The outlined issues are only a short introduction into the problems which should be resolved before wider deployment of VANET.
A good introduction into a security related issues in VANETs together with a comprehensive list of references can be found in (Tchepnda et al., 2009).
This section presents CARAVAN, the unified VANET framework, which is able to accommodate most of the existing VANET mechanisms and use them in an optimal way. The first version of the concept was defined in (Kukliński et al., 2010). This framework is component based thus enables independent modification of every component functionality without the necessity to redesign other components or the overall architecture. In the proposed framework the usage of a specific mechanism is tuned individually to the node’s environment and service requirements. The component based architecture enables easy deployment of new applications which can use well-defined, lower level services offered to the application platform.
There are several observations which led us to the development of the framework:
The communication quality and reliability in VANET may take extremely different values that depend on node’s specific situation. For example on the highways the combination of high mobility of nodes and the short range of radio coverage (50 – 300 metres) leads to the intermittent communication of low quality, but during traffic jams we may obtain stable links being able to handle HDTV services.
There are car mobility models which can be used to predict car positions. Moreover, most cars are equipped with GPS or navigation systems, thus the information about car position, direction, speed and even about the travel destination is generally available to every node and can be disseminated to node neighbors. This information can be used for the proper selection of the communication scheme and services offered to a node.
There is an easy way to determine the proximity of nodes or their communication ability. It can be done using periodic transmission of HELLO messages. That way it is possible to discover neighbors and nodes density. These HELLO messages and responses may contain the position of the node and the mobility vector. Subsequent analysis of this data can lead to the identification of the longevity and the quality of the possible communication links between the nodes and their potential belonging to groups (clusters), which can be formed. Such clusters may provide relatively stable intra-cluster communication. Thus the group membership can be used for communication purposes (selecting the communication scheme or protocol), but it is not limited to. From the service point of the view nodes proximity (group membership) has an important value – it is possible that group members can be interested in the same or similar set of services. So, the identification of the relative positions of nodes has an important impact on nodes communications abilities and on their potential interest in services. In such model every node can be treated as an isolated node, group membership candidate (during the group membership inclusion procedure) or a group member. For every node category a different communication and service scenario can and should be applied.
There have been many routing protocols designed for VANET in order to resolve the problem of communication reliability. It can be improved by the specific mechanism of the routing protocols, applying clustering, or the multi-path routing. All the mentioned mechanisms can improve reliability, but still a lack of communications in case of sparse networks can be observed, and the intermittent communication still may occur in case of high speed moving cars. Thus, we cannot guarantee the existence of permanent communication. The disruption tolerant networking paradigm (DTN) which uses store-carry-forward mechanism seems to be a good solution for handling temporary lack of communication. The information about nodes mobility vectors and even the destination (GPS and navigation based) makes VANET a good candidate for efficient implementation of DTN. Additionally, DTN enabled cars which do not belong to any stable group of cars (cluster) can play an important role of mules, which can carry on the information between the groups, thus such an isolated node plays a positive role in the overall communication model. In conclusion, the communication capability of every node can be different for groups of nodes (clusters) and for isolated nodes. The communication protocol should take into account the individual node state. At present, there is no single approach which is able to handle all the mentioned cases. That observation has led to the conclusion that for every node a local environment (number of other nodes, topology stability, and group membership) should determine the protocol which is used for data exchange or content delivery.
In a very conservative approach the number of VANET services is limited to driving safety applications only. These simple services usually transmit short local messages, which should be geocasted or broadcasted. In more advanced service scenario we may think about the inclusion of video services, voice services and all other, Internet-like services. The real-time services, like video or voice based, require higher communications QoS guarantees which in VANET networks are hard to fulfill in general. However, there are some cases, for example the one-hop communication in which the communication ability of VANET goes beyond the most demanding services. In the opposite case, the DTN example, no real-time services are possible at all. This observation leads to the well-known conclusion that the service offer is limited by network transport capabilities, but this conclusion in the mentioned case has more dramatic meaning that in the classic, wired networks – the variance of the network QoS is much, much bigger. So, before the services will be offered to the end users, their communication ability has to be checked first. It is obvious that these communications properties will change over time, in some cases pretty rapidly.
Due to the distributed nature of VANET networks there is a lack of special nodes (servers) which can help in service offering. Because of that, the nodes do not have a list of the “preferred” addresses and the (IP) addresses of their neighbors have for them very limited usefulness – what is the reason to communicate with them? What is represented by an IP address? There is, of course, a set of messages which can be delivered to all nodes in a specific area, but such geocasting should not be used for all services. In some situations, the car driver can indicate which service he or she is looking for, but the mechanism of service selection by the end-user should be kept at the very minimum level – the end-user should not be attacked by new services, but he should be well informed only about these services on which he is really interested in. It means that the end-user should have a possibility to indicate which services are interested for him at the specific moment. In that context the publish-subscribe mechanism can be applied. The variety of possible services in terms of their QoS requirements and the dissemination range and type make the classical IP service not adequate for VANET.
All of the observations presented above have led to the conclusion that it is unrealistic to cover all the possible network configurations, communication issues and service scenarios by a single approach. The communications and services should be adapted according to nodes density, mobility, relative mobility, group membership and user preferences. In order to cope with all these problems the best solution is a rich set of well-defined tools that are appropriately selected accordingly to the environment status and/or to service preferences. In the proposed unified framework there are multiple sets of tools and the choice of the appropriate one depends on the set of node contexts. The overall behavior of the nodes is individually controlled by the Cross-context Processing Engine, which receives and sends context from different components of the architecture.
4.2 CARAVAN design
As it was outlined in section 3, a rich selection of algorithms has been developed for VANET in order to cope with different problems. Unfortunately, so far there is no single approach which enables to use them as components of a bigger system. The main idea of the proposed framework is to collect a set of algorithms (tools) that are useful in different VANET situations and for a specific application, nodes density and mobility select appropriate set of them on a per node basis. Such individual and dynamic selection of tools provides obvious profits, but it imposes a new problem related to the criteria of algorithms selection and the way in which this process is implemented.
The discussion presented in the previous sections has shown that the communication ability of every node depends on the node mobility, the number of nodes in the neighborhood and their mobility vectors. The information about the node such as its current and averaged position, speed and direction and node track can be obtained from GPS. More information about the future node position and the final destination can be taken from the navigation system (if available and active). The GPS and navigation system provide the information about nodes position expressed in absolute coordinates. However, the information about the relative position of the nodes is very useful as well. Such information can be retrieved by processing the GPS data but can be also obtained directly when the neighboring nodes should respond to request sent over the radio channel (for example beacon messages). Using this mechanism we can determine in a very simple way the local density of nodes and using time averaging of responses we may find good candidates to create a cluster (Kukliński & Wolny, 2009). There is no doubt that for the estimation of the absolute and relative position of nodes, for creating clusters a plethora of algorithms exists, thus the proposed framework should be able to accommodate them. The information about the nodes mobility, their mutual communication relation and about nodes clusters is of great importance for routing as well as for services. This is the reason why in the framework we decided to introduce an independent component which offers to other elements of the framework the preprocessed information about nodes mobility, clusters etc. We named this component the Mobility Layer. The internal elements of the Mobility Layer are not fixed, however they should perform all the functions described above. In the proposed framework the context-aware approach is used. In-line with this philosophy the output of the Mobility Layer is the Mobility Context.
In Section 3.1 a short overview of different MANET and VANET routing protocols has been presented. Every of the described protocols has both advantages and deficiencies. Some of them are well suited for stable network topologies, other work efficiently in a sparse, but not in a dense network. These observations has led to the conclusion that in the proposed framework every node (or group of nodes) should select the routing protocol accordingly to the node mobility and neighborhood density. In the proposed framework the set of different routing protocols and content dissemination mechanisms (including DTN) composes the Connectivity Layer. The selection of the routing protocol for a specific node is based on the Mobility Context and on the service requirements. These service requirements and properties are exposed by another component of the framework that is the Application Layer. The Mobility and Application contexts have impact on the selection of the appropriate routing protocol; however they of course have no impact on the quality of the obtained connectivity. This connectivity is characterized by the Connectivity Context, which is exposed by the Connectivity Layer.
The Application Layer generates contexts that describe the applications and user requirements, but it also adapts the applications to the connectivity, quality and mobility information.
In the CARAVAN all the contexts of the Mobility Layer, the Connectivity Layer and the Application Layer are processed by the Context Processing Engine (CPE). The CPE is a heart of the proposed framework and it is responsible for the dynamic selection of the tools to the overall context that characterize node mobility, connectivity possibility and service requirements and restrictions. The details of implementation of CARAVAN are presented in the subsequent sections.
4.3 CARAVAN software architecture
The CARAVAN is composed of three functional layers, focused on mobility, connectivity and application. The internal behavior of layer components is controlled and described by a set of key parameters, represented as context information. This information is exchanged bidirectionally between the layers by applying cross-layer context adaptation. Transferring significant contexts in a unified format transversally between the layers facilitates the optimization of both important intra-layer operations, as well as the overall performance of an architecture based on this framework (e.g., selecting the best routing or forwarding scheme according to mobility information).
The entire framework is driven by context data exchange and decisions based on it, so node internal architecture can be defined around the idea of context exchange in a layered approach, by emphasizing the three key components – mobility, connectivity and application. Each component features mechanisms for processing context and feeds it to a cross-layer component which centralizes all of the context data (including that from the other components). The cross-layer component makes intelligent decisions and then feeds back key input context, influencing the behavior of the component. Such architecture can be applied to all types of entities, such as unclustered nodes, clusters and roadside infrastructure nodes. The architecture driven by context information exchange is based on:
a layered functional structure centered on mobility, connectivity and application,
a cross-layer transversal interaction, in order to optimize intra-layer and overall system performance,
a relatively simple architecture, ideal for adding new functionality to improve intralayer operations.
This generic architecture for the Abstract Node (AN) being the basic entity inside the proposed framework is depicted in Figure 2. In order to enable incremental upgrades, an implementation calls for a modular design to be derived from the defined framework and applied to the AN.
4.4 Abstract node description
As mentioned in the previous section, we are applying a modular design for the AN. This design is based on a hierarchy of modules (see Figure 2), implementing specific functions related to mobility, connectivity and application.
4.4.1 High-Order Modules
The proposed abstract node architecture has a hierarchical structure and consists of a Context Processing Engine (CPE) and three dedicated High-Order Modules (HOMs). HOMs, together with CPE, create a fixed core. Each of the HOMs, specifically the Mobility Context Module (MCM), Connectivity Context Module (CCM) and Application Context Module (ACM) correspond to a different layer of the framework and is functionally separated from the other modules. There is no direct transfer between them – the only way to communicate with each other is a bi-directional exchange of context information with the CPE using the same established interface in all three cases. The CPE performs a context adaptation and enables the cross-layer transfer of the relevant data in order to perform in the most suitable way. A dedicated Context Manager (CM) in each of the HOMs and a Translation Logic (TL) in CPE are directly responsible for data exchange between the top level modules. They all are also involved in the core logic of their parent modules. The typical communication looks as follows – the TL receives a context information from specific CMs, then it does some data processing, e.g., translation of the received data into some unified language, and afterwards it feeds the other modules with a newly obtained information according to their needs. Due to a single module gathering context information from all functional planes and its proper processing and distribution, it can be helpful in selecting some specific behaviors inside a particular HOM, e.g., choosing the routing/forwarding mechanism best suitable to a certain node mobility information.
4.4.2 Low-Order Modules
In addition to the above HOMs there exists the second tier of the modules hierarchy which are called Low-Order Modules. They are introduced into the framework to make it easily extensible by enabling a possibility of adding new mechanisms and algorithms, e.g., new routing schemes or new data dissemination mechanisms. Such approach allows the integration of the existing VANET concepts and leads to the diversity of choices in order to increase the overall performance of the system. LOMs are by design exchangeable user-defined modules which provide specific VANET algorithms. Each of the LOMs has to be attached to one of the HOMs depending on its destination for mobility, connectivity or application layer.
As it was already mentioned the fixed core of the architecture consisting of the CPE and three HOMs secures the integrity of the framework together with a functional separation between the defined layers. The role of the LOMs is to allow a flexible definition of new algorithms and their integration into the overall logic of the system. This makes the proposed architecture open – also for the many existing VANET solutions. An important fact is that all LOMs are built on a common internal definition of the generic module, called the Abstract Module (AM), which is presented in the bottom part of Figure 2. Due to this fact, all LOMs can be integrated into framework and handled in a very similar way.
The Abstract Module definition assumes the use of a simple interface to exchange data between LOM and the parent top level module. As the whole architecture is built around the idea of context-awareness, also in this case the exchanged data can be seen as some specific context encoded using some generic format. Depending on its role in the system the LOM can provide context information to the system or require such information. However, in most cases the LOM can do the both. The capabilities of each module together with its needs are registered in the system using a built-in Driver during a module initialization phase. If all the needs are fulfilled, which means the LOM can be fed with the required input context information; the module is ready to work. The received data are processed by the Core Logic and the proper output context information is provided as the result. The Core Logic implements the algorithm or mechanism for which the module is intended, e.g., a routing scheme or a scheduling mechanism. The processing part of the module can be constrained by a set of adjustable internal parameters.
The majority of developed LOMs implement functions related to one of the three HOMs corresponding to one of the three functional layers, although it is possible to define a LOM for some particular CPE functionality, such as scheduling of DTN bundles. Therefore the most typical connection will be between low and high order modules. LOMs are plugged in the proper Context Manager, so the role of the Context Manager is to register such LOM inside the TL of CPE and to manage all of the LOMs connected to it. This means the CM is actively involved in the HOM logic and the context processing is not focused on CPE, but rather it is distributed in the core of the framework with some of the decisions being shifted to the CMs.
4.5 High Order Modules description
The defined framework features three functional layers built on the importance of mobility, connectivity and application context information. As described in the previous section, each of these three layers has a corresponding High-Order Module in the module hierarchy defining the Abstract Node architecture.
4.5.1 Mobility Context Module
The Mobility Context Module is responsible for processing of nodes mobility data. Among its functionalities there is the network topology discovery. Whenever it is appropriate it can group the network nodes into a set of clusters, obtaining this way a topology composed of virtual entities called Abstract Nodes. When a clustering is not performed in the network, each Abstract Node will correspond to one real node. This HOM monitors a set of mobility parameters, such as geographical position and velocity vectors, as well as the neighboring nodes behavior and inter-nodes dependencies.
As the framework is thought to be mobility driven this module is of great importance. The collected and processed context mobility data can be used for many purposes. First of all some clustering algorithm can be fed with this data to optimize its operations. Clusters of nodes can be treated as virtual Abstract Nodes with their own mobility contexts defined for example in relation to distinguished real node being a cluster head.
The mobility context of the node itself and of the neighborhood can be used to make some movement prediction. Such information, distributed among the other modules using a Context Manager connected with a Translation Logic has a potentially great value for routing and forwarding schemes – especially those dealing with delay tolerant networking. An important advantage is that introducing MCM allows making all mobility context related data gathering and processing only once in a single dedicated place for many different protocols and mechanisms.
4.5.2 Connectivity Context Module
The Connectivity Context Module is presented in the Figure 3. The main goal of this module is providing connectivity between the virtual Abstract Nodes created in MCM. This means the module is responsible for routing and forwarding functionalities. The routing functionality uses a logic implemented in the Routing Manager (RM) which finds routes to particular network destinations using the best Routing Scheme selected from the available ones. The Context Manager managing all the connected LOMs participates in this selection process. The forwarding duties are performed by the Forwarding Manager (FM) which makes the decisions such as selecting the right forwarding scheme and choosing the next hop. The choices are depended on many factors, e.g., application context containing the information about QoS requirements. There is also some additional custody transfer mechanism implemented by the dedicated Custody Manager to support disruption-tolerant forwarding. Moreover, the CCM cares about its local routing table to be up-to-date. Another important group of the module duties is computing the performance metrics related to routing or even DTN forwarding and providing this data as a connectivity context to other modules.
4.5.3 Application Context Module
The Application Context Module implements functions similar to those included in the Application Layer in the OSI stack. It is closest to the end user of the system and it interacts with some applications. New context based services can be defined and integrated in a similar way, by using LOMs.
One of key issues in implementing the proposed architecture is the addressing of nodes and services, especially if there is the requirement of enabling disruption-tolerant communication between the nodes. In the case of the highly dynamic vehicular environment, most applications involve a kind of controlled broadcast of information and there is little need for unicast applications.
In this case, assigning a constant address to the node is irrelevant. The address of the destination is not known and is not bound to the source, since the destination is constantly on the move. To address the groups of destination nodes characterized by high mobility, much more important is the context information related to location and neighborhood of the group, as well as its structure and interaction with other groups. In a dynamic network the services are context-addressable, hence the importance of context information exchange between modules.
4.5.4 Context Processing Engine
The Context Processing Engine which internal architecture is shown in Figure 4 is the most crucial part of the framework. It is a module where majority of system intelligence is hidden, which gathers and scatters important context information from and to the three HOMs and which manages a local Repository in which the context data is stored. The output data from the other modules is continuously monitored, filtered and processed, not to mention that sometimes future predictions are made in order to improve specific functions inside HOMs, e.g., the prediction related to the node mobility pattern can help to optimize routing and forwarding. CPE feeds the other modules with the context data according to their requirements reported in the initial registration phase. Hence, a registration is a moment when a set of rules and dependencies in relation to the already registered LOMs is created. These rules are then used to store and manage context data to meet the requirements of the newly attached LOM. Another area of responsibilities of CPE is scheduling of DTN bundles which is performed by a Scheduling Manager, while DTN bundles are queued and stored in the Repository.
The Translation Logic included in CPE adapts the received information and delivers it to the proper Context Module for being handled. The TL has some basic logic which makes use of Context Ontology (CO) engine. Use of ontology concept is necessary because an open architecture allows attaching many different LOMs which exchange data in many possibly different formats, so that translation into one formal context information representation is needed. The CO consists of a set of keywords, rules and structures for describing context data and all context relations using a common ”language” which can be easily understandable and interpreted by the Context Managers. Usually the three representations are used. The CO approach allows for integration of new solutions into the framework which can be expressed using contexts, even if the offered capabilities were not available in the beginning stage of the designed system based on the framework.
Context in the presented framework is not just a set of external constraints on the system for a given instance. It is redefined to model every piece of information, be it internal control data, instance related data or external data. Building context information is done in accordance with the implemented ontology. Defining such a CO is in fact adding a new ”template” to the architecture itself, which becomes context-aware, making it more robust.
Inside the CPE the Scheduling Manager is responsible for choosing the best Scheduling Scheme for DTN bundles before passing them to the CCM. There exists a possibility to integrate new scheduling schemes in the form of LOMs attached directly to the Scheduling Manager. The selection of a particular scheduling scheme, together with the context information monitoring and adaptation are part of a broader cognitive functionality inside the CPE, specifically the capability of the system to behave differently according to the given external context and learn from previous experiences.
To implement the architecture in a real network, other functions will need to extend the CPE logic, such as security functions related to data validation and user authorization, as well as convergence components to support inter-working with multiple communication stacks for different radio technologies. Although these functionalities are not yet handled, they are very important issues related to VANET and need to be solved in the future.
4.6 Interface description
A challenge in implementing the new system architecture is the design of the interfaces for data exchange between modules. Useful parameters and data are adapted to context information and passed between entities, to ensure compatibility and inter-working between them. The most important interfaces are described in Table 2.
|CM generic interface||Bi-directional generic interface for exchanging context information with Context Managers – both between a HOM and the CPE, specifically between a CM and the TL and between HOM and attached LOMs.|
|Bundle transfer interface||Aside from the standard CM-TL generic interface, there is also a second bi-directional interface between CPE and CCM, for sending and receiving DTN bundles. It is up to the CPE to provide the necessary adaptation of the Application Data Units (ADUs) to the bundles.|
|External I/O interface||The AN external I/O interface is responsible for physical communication with other devices in the network. This bi-directional interface connects to the CPE.|
|ADU transfer interface||Aside from the standard CM-TL generic interface, there is also a second bi-directional interface between the ACM and CPE, for sending and receiving ADUs (Application Data Units).|
All the listed interfaces are quite simple which allows for easier framework expansions by user developed modules. This simplicity can be assured due to context-aware design of CARAVAN.
4.7 CARAVAN – a sample use case
To make the CARAVAN concept easier to understand a sample use case is presented in this section. As it is shown in Figure 5, the sample system built on the framework has following Low Order Modules attached:
Topology Discovery Module (TDM) – the mobility layer module which uses GPS device and beacon messages to gather mobility context data of the node itself and from the neighboring nodes,
Density Based Clustering Module (DBCM) – the mobility layer module implementing DBC clustering algorithm, responsible for assigning roles of cluster visitors, cluster candidates and cluster members to neighboring nodes, for finding stable groups of nodes, for selecting clusterhead node being a cluster representative, and for choosing nodes being cluster border gateways,
Optimized Link State Routing Module (OLSRM) – the connectivity layer module which makes sure that the routing tables for intra-cluster communication are up to date using OLSR routing protocol,
Ad hoc On Demand Distance Vector Module (AODVM) – the connectivity layer module implementing AODV routing protocol for short range communication with nodes connected using the stable paths,
Epidemic Routing Module (ERM) – the connectivity layer module which is used by context-aware services that can deal with longer delays,
File Transfer Protocol Module (FTPM) – the application layer module allowing data transfer between node with a stable connection using FTP protocol,
Obstacles Warning Assistant Module (OWAM) – the application layer module which warns other vehicles about road obstacles to increase driving safety.
All the Low Order Modules are connected using the generic CM interface for bi-directional exchange of the context data. Each of the modules has to be previously registered in the system using the built-in driver. For example the TDM will advertise itself that it is able to provide necessary nodes position and mobility data with no requirements for system input. The DBCM as the input needs some data generated by the TDM and as the output it offers information about nodes relations such as identification of stable clusters and about nodes which are bad candidates for cluster members, for example because they are moving faster than the group (however, this makes them potential candidates for passing data in DTN forwarding schemes). There can be observed dependence between DBCM and TDM. Due to the registration phase and the logic embedded in the top level modules, every such LOMs dependence can be tuned. The DBCM requires only at specified intervals and only some subset of data which TDM is able to provide. Hence, the TDM knows that there is no point to deliver neither more data nor to do it more frequently than it is needed. Of course, a demand for context data can vary in time as it depends on activity of different modules. The discussion on the relationship between the DBCM and TDM is also a good opportunity to clarify another introduced concept of Translation Logic inside CPE and ontologies. Let us consider the case when DBCM modules need velocity vectors of neighboring nodes for proper work and when TDM is able to provide information about direction and speed of nodes movement. Although it is not exactly the same, there exists a very simple one-to-one correspondence between these notions. Such rule can be easily encoded in the ontology and therefore the translation can be easily done in TL.
Similar dependencies occur between the other modules in the presented sample system – e.g., FTP data transfer can be applied only when a stable connection is detected, so it is possible inside the cluster (OLSR routing protocol is used) or in the traffic jam (AODV routing protocol is used). The OWAM module is designed to warn about obstacle the drivers which are moving towards it – so in this case the delay-tolerant forwarding can be applied combined with the context-aware (in a given direction) data dissemination. The best candidates for passing messages, that is nodes which are moving quickly in a right direction, can be selected using context information from TDM and DBCM.
It should be clear that the presented system can be easily extended by other modules implementing new applications or vehicular services, as well as new protocols to allow a selection of the most suitable solution depending on both external and internal circumstances in order to optimize the overall system performance.
In this chapter a new approach to VANET has been proposed. The main idea of the proposal is to integrate many VANET concepts into a common framework and use them on the dependency of the service requirements, connectivity properties and node mobility characteristics. In the proposed framework context-aware approach is used. Contexts are related to service/applications requirements, communications ability, mobility vectors of cars/nodes and the mutual space-time relations between them. The usage of contexts provides high level of adaptability and flexibility. In the CARAVAN we defined three layers: the Mobility Layer, the Connectivity Layer and the Application Layer. Such functional decomposition of the architecture provides ability to incremental modification of every layer via adding or modifying layer internal components without the necessity of the redesign of other components of the architecture. In fact the operations which are most influential on the system behavior are performed by the Cross-Context Processing Engine, i.e., the component that is responsible for the selection of appropriate tools for a specific, overall context. The presented software oriented view together with a sample use case give some clues how the CARAVAN can be implemented and deployed to make vehicular networks idea closer to the reality.
Authors would like to gratefully thank Zygmunt Wereszczyński from Orange Labs Poland for his invaluable help.