CMTG: A Content-Based Mobile Tendency Geocast Routing Protocol in Urban Vehicular Networks

Abstract

Efficient dissemination of messages is a vital solution to the vehicular communications and applications. Geocast, delivering messages to a few specific areas, has become an important issue with the accelerating development of the location-based services in vehicular networks. Different from the conventional geocast schemes focusing on the static target areas, in this paper, we propose a content-based mobile tendency geocast (CMTG) routing protocol for urban vehicular networks from the delay tolerant networks (DTNs) perspective to better deal with the high mobility and transient connectivity issues. The target roads of dissemination depend on the preferred tendency and path of message, based on the determination to the message's expected propagating roads. And vehicle decides whether to relay the messages carried to other encountered vehicles by calculating the mobile tendency to the source location of message. The robustness and adaptability of protocol are also proved theoretically. Extensive performance comparisons with other protocols are conducted to show the advantages of CMTG.

1. Introduction

Vehicular applications fall into two broad categories of safety and comfort [1]. Transportation safety is critical among these applications. Event notifications about road incidents on the move such as accidents, collision warning, and obstacles on lanes are some good examples. The vehicular ad hoc networks (VANETs) are a promising and important networking technique for building the Intelligent Transportation System (ITS) [2]. However, VANETs more depend on infrastructure and make use of an existing end-to-end path between a data source and its destination. And it is difficult to guarantee the end-to-end connectivity due to high mobility and frequently changing topologies in vehicular networks. The existing work has proposed the “store-carry-forward” mechanism in delay tolerant networks (DTNs) [3] to forward packets, and the packets may be cached at intermediate nodes. So DTNs can be a good solution to the problems of vehicle-to-vehicle communication in vehicular networks, such as large scale, frequent disconnection communication, long unavoidable delays, limited bandwidth, power constraints, and high bit fault rates [4, 5].

Efficient dissemination in vehicular networks has been addressed using data aggregation techniques [6]. Asynchronous communication paradigm such as event-based middleware is also essential to support anonymous coordination of nodes in such heterogeneous and mobile environments [7]. However, these schemes ignore that the message has its own targets of interest. We now give an example to illustrate this characteristic. If an accident occurs, the massage of the accident will be forwarded to vehicles that will soon travel to the site of the incident instead of noticing other vehicles. We can also consider the scenario of an emergency vehicle that announces its arrival at a crowded place as it advances on the road. The key challenge when building a large-scale content-based message dissemination system for such highly mobile networks is the transmission among relays to reach an interested group of receivers [1]. Efforts have been made to create efficient multicast communication in vehicular networks. However, the complexity increases with larger group thus limiting the scalability of maintaining group membership and efficient event delivery. Hence, location based context-awareness is important for improving the accuracy and performance of event dissemination in such vehicular environments. Furthermore, even if the vehicles are in the same geographical area, they can be in different target groups of the specific event messages because of the factors such as different mobile directions. This has not been concerned by the existing studies. If we are able to determine and take advantage of this feature, we can reduce a lot of overhead in vehicular networks. Therefore, in order to achieve accurate dissemination of messages, the key challenge is to determine the target groups of the message explicitly when the message is generated and then dynamically determine whether the vehicle is in the target groups based on the current message and the movement of vehicle when the message is forwarded.

Based on the above discussion we propose a geocast routing protocol, called content-based mobile tendency geocast (CMTG), for data dissemination in vehicular networks that integrates content-based middleware system with the geocast routing protocol. The protocol consists of a scheme for determining the vehicle mobile tendency based on the position and direction of vehicle and a strategy for selecting message to be transmitted according to the target groups of the message and the mobile tendency of the encounter vehicles. Firstly, we analyze the propagation characteristics of the messages in vehicular networks and classify the messages according to the target roads of the message dissemination. Secondly, we design a scheme to estimate the mobile tendency of a vehicle. Thirdly, we propose a strategy for deciding whether to forward the message based on whether the vehicle is in the message's target roads and when the vehicle encounters another one. Finally, we also discuss the message queues management. The contribution of this paper is mainly twofold.

• (i)

  We consider the content of messages disseminated in vehicular networks and classify them according to their expected propagation paths. Then, different routing strategies are designed for each type of messages.

• (ii)

  We propose a dynamic method of multicast group based on mobile tendency. Each vehicle will determine whether the encountered ones are in the target groups of its message. It can eliminate the overhead of maintaining the geographic multicast areas.

The CMTG scheme can be used to improve the disseminated efficiency of message in Internet of Vehicles. And its applications will also become research hotspots.

The rest of the paper is organized as follows. Section 2 presents brief reviews on the related work. Section 3 introduces the network model and other related concepts. Section 4 reveals the details of the proposed CMTG scheme. Via analysis and simulations, the performance of CMTG is evaluated in Section 5. Finally, we conclude our paper in Section 6.

2. Related Work

In this section, we provide an overview of recent related works on data dissemination in vehicular networks. The motivation to develop specific dissemination protocols in this area is that traditional approaches for general mobile ad hoc networks are not suitable in such a highly dynamic environment [8, 9]. Thus, geographic addressing and routing protocols specific for vehicular networks are being proposed, as well as other data dissemination approaches. At the same time, the DTN technology has also been further applied in vehicular networks to handle frequent disconnections.

2.1. Geocast Routing Protocols

Position-based or geographic routing protocol makes routing decisions based on the positional information, where the source sends a packet to the destination using its geographic position rather than using the network address. Such protocol requires that each node is able to obtain its location and the locations of its neighbors through GPS assistance or other localization techniques. Geocast is a routing protocol providing multihop wireless communication over an autonomous mobile environment and delivers messages to certain geographic location or region. Initially proposed for mobile ad hoc networks (MANETs), it quickly found adaptation for other networks including VANETs [10]. The existing geocast routing protocols in VANETs include IVG [11], Abiding Geocast [12], DRG [13], DG-CastoR [14], Mobicast [15], DTSG [16], Constrained Geocast [17], and GeoMob [18]. These protocols differ in message and memory complexities, in robustness and abilities to deliver geocast packets in partially partitioned networks. However, the nodes in geographic area are not classified according to their movement in these protocols, which may cause problems as we discussed in Section 1.

2.2. Content-Based Dissemination Protocols

Several works have emphasized different aspects that should be considered when designing a suitable dissemination strategy. For example, Nittel et al. [19] highlight three elements: (1) the time elapsed since new data are available until the network stabilizes; (2) the best distribution area around the event originator; and (3) the lifetime of the data. Based on these considerations, several specific dissemination protocols have been proposed. Xu et al. [20] develop an opportunistic exchange mechanism inspired by the field of epidemiology, where vehicles with a certain piece of information act as “disease carriers” by “contaminating” the nearby vehicles along their routes. Wischhof et al. [21] propose a segment-oriented data abstraction and dissemination approach for comfort applications, where the broadcast interval is dynamically adapted to avoid overloading and favor the propagation of significant changes. At the same time, it has been shown that the Publish/Subscribe (P/S) communication model is well suited as a model for a wired, data-centric content-based routing network [7, 22]. The earliest P/S systems were type based where each event is labelled by a publisher and consumers subscribe to all events [23]. Type based systems use hierarchies that suit typed messages but deploying serialization is difficult. Besides, a versatile application does not involve typing or objects [24]. Hence a combination of classification and content based filtering may be an extensible approach. Some of the common and important content-based P/S systems are GRYPHON, SIENA, ELVIN, and KERYX, which are scalable to wide area networks [25]. Yet for all that, the type based system simplifies the handling of message content, which is similar to our work.

2.3. DTN Routing Protocols

Delay tolerant networks enable communications where the source to destination connectivity cannot be always sustained [3]. Vehicular network is a typical DTN. Since nodes are highly mobile, in this type of network, they suffer from frequent disconnections. To overcome this, packet delivery is augmented by allowing nodes to store the packets when there is no contact with other nodes, to carry the packets for some distances until meeting with other nodes, and to forward based on some metrics on nodes’ neighbors [26]. The VADD, GeOpps, and GeoSpray are notable DTN vehicular routing protocols. Vehicle-assisted data delivery (VADD) [27] is a vehicular routing strategy aimed at improving routing in disconnected vehicular networks by the idea of “store-carry-forward” based on the use of predictable vehicular mobility. Geographical opportunistic routing (GeOpps) [28] takes advantage of the suggested routes of vehicles’ navigation system to select vehicles that are likely to move closer to the final destination of a packet. And GeoSpray [29] takes routing decisions based on geographical location data and combines a hybrid approach between multiple-copy and single-copy schemes. During the travel of vehicles, if there is another vehicle that has a shorter estimated arrival time, the packet will be forwarded to that vehicle. The process repeats until the packet reaches the destination. The minimum delay used by VADD is indirectly obtained by selecting the next forwarding node whose path's nearest point is closest to the destination. GeOpps requires navigation information to be exposed to the network; thus, privacy such as vehicle's whereabouts might be an issue [26]. When it comes to GeoSpray, first, it starts with a multiple-copy scheme, spreading a limited number of bundle copies, in order to exploit alternative paths. Then, it switches to a forwarding scheme, which takes advantage of additional contact opportunities. In order to improve resources utilization, it clears delivered bundles across the network nodes. However, they are all unicast with only one destination node.

Compared with the existing works, this paper has the following features. (1) It provides an efficient mechanism to deliver messages according to the vehicles mobile tendency, instead of purely based on geographic information. (2) It allows a vehicular user not only to subscribe the messages of interest but also to designate a vehicle group of message notification by prescribing the predetermined path and tendency of messages. (3) It takes full advantage of the “store-carry-forward” mechanism to solve the problem of network fragmentation, so that vehicles make it possible that the communication can still be established even the connection between source and destination is not always sustained.

3. Preliminaries

This section introduces our network model and the classification of messages. The basic proposed idea of CMTG routing protocol and the application examples are also described.

3.1. Network Model

In this study, we assumed that all vehicles drive in a multilane road one segment by one segment with a single direction. So we can define and describe the basic concepts, such as road, vehicle, and message.

3.1.1. Road

First of all, we define a location in vehicular networks as

$$\begin{array}{cc}& location=(longitude,latitude)\\ LOCATION::=\{pp=location\}.\end{array}$$

(1)

At present, we only consider the longitude and latitude, without the altitude, in our study. The location is used to locate the position of roads, vehicles, messages, and so on.

Generally, vehicles are moving in the middle of roads. Then, the road is denoted as

$$\begin{array}{ll}& road=\left(i{d}_r,locatio{n}_b,locatio{n}_e,directio{n}_r,width\right)\\ locatio{n}_b\in LOCATION\\ locatio{n}_e\in LOCATION\\ directio{n}_r\in \{Anterograde,Retrograde,Bidirectional\}\\ ROAD::=\{rr=road\}.\end{array}$$

(2)

We can take advantage of the initial position (location _b ) and the final position (location _e ) to distinguish a road uniquely. We can also determine whether a location is located in a road according to the calculation of relative position and width of the road on the assumption that the road topology is known. We denote the locate activity and location activity as

$$\begin{array}{cc}& {\phi }^{locate}:location\times road⟶\{True,False\}\\ {\phi }^{location}:location\times ROAD⟶road.\end{array}$$

(3)

The beginning and ending of road have been identified by location _b and location _e . And the region of road can also be confirmed with the width of road. So we can know whether a location point is on the road through calculating whether the point is within the region. The activity is denoted by φ ^locate . We are able to determine that a location belongs to which road in the collection ROAD by φ ^location through the φ ^locate .

It means that any place, in the field of roads, can be located in one road with the activity φ ^location . We can also utilize the φ ^locate and φ ^location to determine whether the two locations are in the same road by φ ^side :

$$\begin{array}{cc}& {\phi }^{side}:location\times location\times ROAD⟶UBIETY\\ UBIETY::=\left\{Same,Opposite,Unknown\right\}.\end{array}$$

(4)

There are three basic positional relationships between two locations in the roads: same road, denoted as same, opposite roads, denoted as opposite, and otherwise, defined as unknown.

We define the direction of road to distinguish it from the reverse one. The direction of road is based on the traffic: the anterograde road allows vehicles to move from the initial position to the final position of this road segment; if the traffic direction is from the final position to the initial position in the road segment, the road direction will be set as retrograde; of course, the direction of two-way road is bidirectional. Figure 1 shows the examples of anterograde road, the retrograde road, and the bidirectional road.

Figure 1

Examples of different types of roads.

In urban environments, most roads are two-way multilane. And the opposite roads are important to assist to spread messages. The activity φ ^opposite is denoted as

$$\begin{array}{cc}& {\phi }^{opposite}:\left\{\begin{array}{cc}roa{d}_{Anterograde}\times ROAD⟶roa{d}_{Retrograde}\hfill & \hspace{0.17em}\hfill \\ roa{d}_{Retrograde}\times ROAD⟶roa{d}_{Anterograde}\hfill & \hspace{0.17em}\hfill \\ roa{d}_{Bidirectional}\times ROAD⟶roa{d}_{Bidirectional}.\hfill & \hspace{0.17em}\hfill \end{array}\right.\end{array}$$

(5)

In the examples of roads illustrated in Figure 1, the road _AB and road _CD are opposite to each other. And the opposite road of road _EF is itself, because it is a bidirectional road.

3.1.2. Vehicle

The attributes of vehicle can be classified into two categories, mobility attributes and communication attributes. Our research is mainly concerned about current location, direction, speed, and other mobility information of vehicle. The communication information of vehicle, such as transmission radius, bandwidth, and buffer size are also as records. The vehicle is denoted as

$$\begin{array}{ll}& vehicle=(i{d}_v,locatio{n}_v,directio{n}_v,speed,comm\_info)\\ locatio{n}_v\in LOCATION\\ directio{n}_v\in \{Forward,Backward,Stationary\}\\ comm\_info=\left(radius,bandwidth,buffer\right)\\ VEHICLE::=\left\{v\mid v=vehicle\right\}.\end{array}$$

(6)

There are three kinds of driving directions which can be adopted when the vehicles move on the road segment based on the lane direction. Most vehicles drive along their lanes, defined as forward; there are also special circumstances, such as backward and stationary, illustrated in Figure 1.

The good communication attributes are able to guarantee the quality of dissemination, while the mobility attributes are also useful for assisting the message dissemination in our study. At the same time, we can use the moving state of the vehicle to determine the relationship between the vehicle and a specified location. Such tendency can be defined as

$$\begin{array}{cc}& {\phi }^{tendency}:vehicle\times location⟶TENDENCY\\ TENDENCY::=\left\{Tended,Deflected,Unknown\right\}.\end{array}$$

(7)

This means that for every vehicle we can calculate the tendency to any location. This tendency is divided into three categories: tended, deflected, and unknown, to the specified location with activity φ ^tendency . If the vehicle is forwarding to that location, its tendency is defined as tended; on the contrary, if the vehicle moves from the location, its tendency is defined as deflected; otherwise, its tendency is defined as unknown.

3.1.3. Message

Message is an important part of the communication system, especially for the content-based dissemination protocol in vehicular networks. Before describing the message we first analyze the propagation characteristics of the message. There are about four different basic directions of message dissemination in a two-way multilane road illustrated in Figure 2.

Figure 2

Basic directions of message dissemination.

Figure 2 shows the dissemination of message in a two-way road. The message spreads in four directions: forward on current road (Type 1), backward on current road (Type 2), backward on opposite road (Type 3), and forward on opposite road (Type 4). Of course, the message can also be forwarded in multiple directions simultaneously. Obviously, the forward dissemination will influence the vehicles that deviated from the source location of message, and the backward dissemination will influence the vehicles that tend to the source location of message. We can use the path and tendency preferences of message to classify the disseminations of message, illustrated in Table 1.

Table 1

The classification of message.

Path	Tended (backward)	Deflected (forward)	Irrelevant (both)
Same	②	①	①, ②
Opposite	③	④	③, ④
Both	②, ③	①, ④	①, ②, ③, ④

The path preferences of message are mainly composed of three kinds. The same path message only spread in the current road. On the contrary, the opposite path message only spread in the opposite road. Otherwise, defined as both, the message has no preferences for roads, and all positional relationships in set UBIETY are its preferences.

The tendency preferences of message are mainly composed of three kinds. The tended message means that recipients are the vehicles which tend to the location of message. The deflected message, on the contrary, tends to spread to those vehicles far away from the message's location. Otherwise, defined as irrelevant, the message has no preferences for tendency. In other words, all tendencies in set TENDENCY are its preferences. Hence, the message in our study is denoted as

$$\begin{array}{ll}& message=\left(\phantom{quot{a}_{change}}i{d}_m,locatio{n}_m,source,TENDENC{Y}_m,PAT{H}_m,\right.\\ \left.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}range,ttl,quot{a}_{change},priority,size,content\right)\\ locatio{n}_m\in LOCATION\\ source\in LOCATION\\ TENDENC{Y}_m\in TENDENC{Y}^{*}\\ PAT{H}_m\in UBIET{Y}^{*}\\ content=\left(topic,tim{e}_{occur},description\right)\\ MESSAGE::=\left\{m\mid m=message\right\}.\end{array}$$

(8)

The message attributes contain current source location, spread trends, spread paths, source location, range of influence, time to live, message type, quota of change, message priority, message size, and message content. The current source location where the vehicle enters the road is recorded as location _m , while the source represents the location where the message happened. The range symbolizes the expected range of message transmission. The ttl means the time to live for the message. The quota _change of message controls the number of roads where the message disseminates. We also use priority and size to tell the importance and size of a message. The content of a message will be encapsulated in the packet and will be resolved in the application layer.

3.1.4. Target Roads of a Message

Now, we can denote the expected recipients of a message m with activities φ ^tendency and φ ^side as $E_m$ :

$$\begin{array}{ll}& E_m\\ ::=\left\{\phantom{{\phi }^{side}\left(locatio{n}_v,locatio{n}_m,ROAD\right)}v\mid v\in VEHICLE,\right.\\ \hspace{0.5em}\hspace{1em}\hspace{0.5em}\hspace{1em}{\phi }^{tendency}\left(v,locatio{n}_m\right)\in TENDENC{Y}_m\\ \left.\hspace{0.5em}\hspace{1em}\hspace{0.5em}\hspace{1em}\wedge \hspace{0.17em}{\phi }^{side}\left(locatio{n}_v,locatio{n}_m,ROAD\right)\in PAT{H}_m\right\}.\end{array}$$

(9)

However, in the actual road environment, restricted by road construction and other reasons, the target recipients will be much less than the expected recipients of a message.

We can easily draw the conclusion that the message has the characteristics of the target roads according to the expected recipients of message. In other words, the vehicles in these roads will become the recipients of the message. The target roads and target vehicles are denoted as

$$\begin{array}{ll}& T{R}_m::=\left\{\phantom{{\phi }^{locate}(locatio{n}_v,r)}r\mid r\in ROAD,\right.\\ \hspace{0.5em}\hspace{1em}\hspace{0.5em}\forall v\left(\left(v\in VEHICLE\wedge {\phi }^{locate}(locatio{n}_v,r)\right.\right.\\ \hspace{1em}\hspace{0.5em}\hspace{0.5em}\hspace{0.5em}\hspace{1em}\hspace{0.5em}\left.\left.\left.=True\phantom{{\phi }^{locate}}\right)⟶v\in E_m\right)\right\}\\ T{V}_m::=\left\{\phantom{{\phi }^{location}}v\mid v\in VEHICLE,\right.\\ \hspace{1em}\hspace{0.5em}\left.{\phi }^{location}\left(locatio{n}_v,ROAD\right)\in T{R}_m\right\}.\end{array}$$

(10)

The vehicles on same side of two-way road are same in tendency. And for the bidirectional road, it can be regarded as two overlap roads. Each road contains the vehicles that have the same mobile tendency. All the vehicles located in the target roads are the recipients of message. They will accept the message when they get it.

3.1.5. Forwarding Roads of a Message

In order to let the message's spread complete more quickly in the target roads, we also set up the forwarding roads and forwarding vehicles of the message to help the delivery referring to the idea of Mobicast [15]. These are defined as follows:

$$\begin{array}{l}F{R}_m::=\left\{\phantom{{\phi }^{location}}r\mid r\in ROAD,\right.\\ \hspace{0.5em}\hspace{1em}\left.{\phi }^{opposite}\left(r\right)\ne r\wedge {\phi }^{opposite}\left(r\right)\in T{R}_m\right\}\\ F{V}_m::=\left\{\phantom{{\phi }^{location}}v\mid v\in VEHICLE,\right.\\ \hspace{0.5em}\hspace{1em}\left.{\phi }^{location}\left(locatio{n}_v,ROAD\right)\in F{R}_m\right\}.\end{array}$$

(11)

Similar to the target roads, every forwarding road also contains the vehicles that have the same mobile tendency. In most cases, the forwarding road and the target road are opposite. Moreover, the forwarding roads could be cancelled when the message has no preferences for tendency and path.

Obviously, the target roads and forwarding roads are usually divided by the road centerlines in two-way multilane roads. However, illustrated in Figure 3, the target road and forwarding road cannot be divided simply by the road centerline in the bidirectional road. Instead the division should be based on the mobile tendency of vehicles.

Figure 3

The TR _m and FR _m in bidirectional road.

3.2. Problem Definition

The ultimate goal of CMTG routing protocol is to achieve message dissemination to all vehicles driving along the prescribed roads in the network. We use “target roads,” denoted as TR _m , to represent the roads where message m should be delivered. When the vehicles get in touch with others, whether they receive or relay the messages stored on other vehicles is decided by the setting of routing strategy, denoted by

$$\begin{array}{cc}& {\phi }^{route}:vehicle\times message⟶STRATEGY\\ STRATEGY::=\left\{Accept,Carry,Ignore\right\}.\end{array}$$

(12)

There are three kinds of routing activity that will be used for every message when the vehicle receives messages from other vehicles. The mobile tendency of vehicle and the preferential tendency of message will jointly determine the activity: accept, carry, or ignore. If the vehicle is located in target roads of the message, it will accept the message. If it is located in forwarding roads of the message, it will carry the message. Otherwise, the message will be ignored.

At the same time, we also need to process the messages carried in vehicle when the vehicle's movement changed, denoted by

$$\begin{array}{l}{\phi }^{manage}:message\times ROADCHANGE\\ ⟶MANAGEMENT.\\ ROADCHANGE::=\{〈i,j〉\mid i,j\in ROAD,i\ne j\}\\ MANAGEMENT::=\left\{Change,Drop,None\right\}.\end{array}$$

(13)

The purpose of buffer management is to reduce overhead. There are also three kinds of management activity that will be used for every message when the vehicle checks its messages. The vehicle will deal with the message queues when it changes roads. If the vehicle goes out from the target roads and forwarding roads of message, it will drop the message. Otherwise, a few attributes of the message will be changed.

3.3. Application Example

Many interesting and useful applications on VANETs can be supported by our CMTG routing protocol, such as emergency warning, Location Based Service (LBS), and video advertisement [30]. For example, our CMTG routing protocol can be effectively used for those VANETs applications for emergency warning as illustrated in Figures 4 and 5.

Figure 4

Example of accident warning message.

Figure 5

Example of emergency vehicle message.

Figure 4 shows that an accident message m occurred on the road, and a warning message is sent to all vehicles that will tend to the accident place to avoid the accident. Figure 5 shows an emergency vehicles message m that notifies the vehicles in front to give way. Obviously, the tendency preference of accident message is tended. Vehicles forward to this message will become the target ones and avoid the accident. While the tendency preference of emergency vehicle message is deflected, Vehicles away from this message will become the target ones and help to spread the message more quickly.

As illustrated in Figures 4 and 5, the target vehicles located at TR _m and the vehicles assisted the spread of message located in FR _m . And all vehicles have the delay-tolerant capability. When there is no connection, the vehicles will carry the message until the connection is established and then restart the forwarding process.

In our study, many messages are not only disseminated on the road where the message generated but also going to forward towards the crossed roads, as shown in Figures 4 and 5. So, we set a threshold in order to control the number of turns. Its quota will be cut down when the message is forwarded to the branch roads, until the quota is used up. The CMTG also need to process the messages buffer in the queues when the vehicle is moved to the other roads. Figures 4 and 5 all show that the location _m of message will be changed, when the message is forwarded to other roads. It means that the location _m of message will be set to $m^{\prime }$ , instead of m. It is because the tendency is more simple and more accurate to be determined based on the location of $m^{\prime }$ instead of m in the forks.

In addition, the message's coverage depends not only on the roads relied the type and tendency of message but also on the transmission range based on the message source and the range of message. It means that the messages can only be forwarded on the specific roads within the scope of influence.

4. CMTG Routing Protocol

In this section, we propose our content-based mobile tendency geocast routing protocol in city scenario via moving vehicles. Generated from the source node, a message will be disseminated towards the targeted roads. Particularly, the messages carried in vehicles are going to estimate the relative mobile tendency with encountered vehicles, when the vehicles enter the communication radius of each other. Then, the protocol will decide a routing action based on the relative mobile tendency between the message's location and the encountered vehicle. It will also change the message's attributes when the vehicle changes its movement. Hence, the routing strategy is the core of the proposed protocol, the estimation of mobile tendency is the prerequisite, and the management of message is an important supplement.

4.1. Mobile Tendency Estimation

In the actual applications, the complex positioning and navigation software equipped in the vehicle can be used to determine its mobile tendencies and changes in road accurately. However, considering the universality of the protocol, the GPS positioning and direction information is only used to determine the tendencies and changes in our study.

If the encountered vehicle's mobile information is known, such information is utilized. The direction of movement is the main information considered. It can be used to calculate the mobile trend towards the message's location by assessing the angle between these two vectors: the position vector of message's source, denoted as ${\mathit{V}}_{\text{node-source}}$ , and the direction vector of vehicle, denoted as ${\mathit{V}}_{\text{direction}}$ . The scope of angle between vectors is [ $0,\hspace{0.17em}\pi$ ]. We can distinguish the different directivities between the vectors according to the magnitude of the included angle. As mentioned in the previous section, the mobile tendency can be divided into three kinds: tended, deflected, and unknown. By contrast, there are also three kinds of relationship between the vector directions, defined as parallel, reverse, and crossed. In practice, we cannot regulate the movement of vehicles on the basis of strict mathematical definition. We can only approximate that the relationship between the mobile directions is one of the three mentioned types. At the same time, two parameters, ${\alpha }_{\text{max-}//}$ and ${\alpha }_{\text{min-}\perp }$ , are set to estimate the directivity relationship of the vectors. The determination of directivity is illustrated in Figure 6.

Figure 6

The determination of directivity based on the direction angles.

Figure 6 shows the relationship between the angle's magnitude and the directivity of the two vectors. If the angle is in [ $0,{\alpha }_{\text{max-}//}$ ], the directions are parallel. The relationship between the directions is reverse when the angle is in [ $\pi -{\alpha }_{\text{max-}//},\pi$ ]. And there is a crossed range: [ ${\alpha }_{\text{min-}\perp },\pi -{\alpha }_{\text{min-}\perp }$ ]. In order to obtain more realistic and robust protocol, there are also two gradual ranges being set, such as ( ${\alpha }_{\text{max-}//},{\alpha }_{\text{min-}\perp }$ ) and ( $\pi -{\alpha }_{\text{min-}\perp },\pi -{\alpha }_{\text{max-}//}$ ), and if the angle is in these ranges, the directivity will be alternative from what the two adjacent ranges represent. The Binary Discrete Choice Model (BDCM) is used to choose what kind of relationship between the two directions when the angle is in gradual ranges. The direction of movement is not equal when the vehicle driving on the road. It is difficult to predict the next movement if the included angle is in these ranges, but there are only two possible results, so that we use the BDCM to make a choice. The magnitude of angle is the explanatory factor for the dependent variable in our study. Based on our actual experience, the probability is positively related to the angle of yaw. So we would like to establish the Probit Model, detailed in the next section, to predict the directional choice.

Algorithm 1 shows the method to determine directional relationships between these two vectors. After the directivity is determined, the tendency is easily estimated as illustrated in Algorithm 2.

Algorithm 1: Directivity.

(1) PROCEDURE  DIRECTIVITY(angle   $$source$$ , angle   $$objective$$ )

(2)  angle   $$alpha=\pi -\left|\right|objective-source|-\pi |$$

(3)  IF   $$alpha$$   IN   $$[\mathit{0},{\alpha }_{\max -//}]$$   THEN

(4)   RETURN   $$PARALLEL$$

(5)  ELSE  IF   $$alpha$$   IN  ( $${\alpha }_{\max -//},{\alpha }_{\min -\perp }$$ )  THEN

(6)   Probit Model choice between $$PARALLEL$$ and $$CROSSED$$

(7)  ELSE  IF   $$alpha$$   IN   $$[{\alpha }_{\min -\perp },\pi -{\alpha }_{\min -\perp }]$$   THEN

(8)   RETURN  CROSSED

(9)  ELSE  IF   $$alpha$$   IN   ( $$\pi -{\alpha }_{\min -\perp },\pi -{\alpha }_{\max -//}$$ )  THEN

(10)   Probit Model choice between $$CROSSED$$ and $$REVERSE$$

(11)  ELSE  IF   $$alpha$$   IN   $$[\pi -{\alpha }_{\max -//},\pi ]$$   THEN

(12)   RETURN   $$REVERSE$$

(13)  END  IF

(14) END  PROCEDURE

Algorithm 2: Tendency.

(1) PROCEDURE  TENDENCY(vehicle  v, location  l)

(2)  Get the direction angle from vehicle v to the target location l in

(3)  angle  a

(4)  Get the direction angle of vehicle v at current time in

(5)  angle  b

(6)  IF   $$Directivity(a,b)$$ is PARALLEL  THEN

(7)     RETURN  TENDED

(8)  ELSE  IF   $$Directivity(a,b)$$ is REVERSE  THEN

(9)     RETURN  DEFLECTED

(10)  ELSE

(11)     RETURN  UNKNOWN

(12)  END  IF

(13) END  PROCEDURE

Algorithm 2 shows that the directional relationships between the two directions are one to one correspondence with the mobile tendencies. If the travel direction parallels to the azimuth vector that is from the vehicle location to the message's source location, the vehicle will be tended to the message. On the contrary, the tendency will be deflected when this relationship is reverse. And the crossed relationship means that the tendency is unknown.

4.2. Message Routing Strategy

After we get the mobile tendency of vehicle, we can compare it with the tendencies tagged on the message. And the result of the comparison will be used as the basis for determining which road the vehicle located in, illustrated in Algorithm 3.

Algorithm 3: Related road.

(1) PROCEDURE  RELATEDROAD(message  m, vehicle  v)

(2)  tendency  vtend = Tendency(v, m.location)

(3)  Get the positional relationship between vehicle v and

(4)  message m in path  vpath

(5)  Get the opposite of vtend in tendency  ovtend

(6)  Get the opposite of vpath in path  ovpath

(7)  IF  vtend  IN  m.tendencies  &&  vpath  IN  m.paths  THEN

(8)   RETURN  TARGET

(9)  ELSE  IF  ovtend  IN  m.tendencies  &&

(10)   ovpath  IN  m.paths  THEN

(11)   RETURN  FORWARDING

(12)  ELSE

(13)   RETURN  IRRELEVANT

(14)  END  IF

(15) END  PROCEDURE

Algorithm 3 shows that, if the vehicle's tendency is one of the message's tendencies and the positional relationship between vehicle and message belongs to the preferences of message, the encountered vehicle is in the target roads of message. If the opposite tendency and opposite path of the vehicle are part of the message's tendencies and paths, the encountered vehicle is in the forwarding roads of message. Otherwise, the vehicle is in the irrelevant roads of message. After that, the routing strategies can be decided as illustrated in Algorithm 4.

Algorithm 4: Routing strategy.

(1) PROCEDURE  ROUTINGSTRATEGY(message  m, vehicle  v,

(2) vehicle  u)

(3)  IF   $$Validation(m,v)$$ is FALSE  THEN

(4)   v drops m

(5)  ELSE

(6)   IF   $$RelatedRoad(m,u)$$ is TARGET  THEN

(7)    u accepts m

(8)   ELSE  IF   $$RelatedRoad(m,u)$$ is FORWARDING  THEN

(9)    u carries m

(10)   ELSE

(11)    u ignores m

(12)   END  IF

(13)  END  IF

(14) END  PROCEDURE

Algorithm 4 shows that, if the vehicle is located in the target roads of message, as a receiver, it will accept the message and then relay it to other vehicles. If the vehicle is out of the target roads of message, it is not the recipient of message. But sometimes the oncoming vehicles are more easily to complete the delivery of message. Although these vehicles are not in the target roads, the message will still be forwarded to them. As the helpers, these vehicles will carry the message and then also relay it to other vehicles. In this case, the vehicle must be located in the forwarding roads of message. In other cases, the encountered vehicle will ignore the message.

As a general rule, there are only two driving directions unless the vehicles go into the intersection or emergency accidents on the road. And these special cases will not be taken into consideration with message routing, but the intersection scenario will be considered in the buffer management later.

4.3. Buffer Management

To be realistic, we assume that each vehicle carries a limited size buffer on board and has limited wireless transmission bandwidth. Thus, when two vehicles encounter, only part of the messages in the buffer can be transmitted at one contact. To effectively utilize the buffer space and each contact opportunity, the buffer management of our routing scheme involves the following mechanisms.

First, the management of buffer decides which overdue messages should be dropped in order to save storage space. The time to live, transmission range, and changed quota will be verified before the message is forwarded to other vehicles, illustrated in Algorithm 5.

Algorithm 5: Validation.

(1) PROCEDURE  VALIDATION(message  m, vehicle   $$\mathrm{\nu }$$ )

(2) IF  m.ttl is over  THEN

(3)   RETURN  FALSE

(4)  END  IF

(5)  IF $$\hspace{0.17em}\hspace{0.17em}\left|\right|m.source-v.location\left|\right|>m.range$$   THEN

(6)   RETURN  FALSE

(7)  END  IF

(8)  IF   $$m.quota$$ is over  THEN

(9)   RETURN  FALSE

(10)  END  IF

(11)  RETUEN  TRUE

(12) END  PROCEDURE

Second, the message will only exist in its target roads and its forwarding roads according to the characteristics of the protocol. The messages in the buffer are going to change if the vehicle moves to the other roads, illustrated in Algorithm 6. For example, the message will be dropped if its carriers go out of the target roads and forwarding roads or just be exchanged in queues when the vehicle moves from the target roads to the forwarding roads or in turn from the forwarding roads to the target roads. At the same time, in order to calculate the mobile tendency more accurately, the quota and location must be changed when the vehicle turns to another road.

Algorithm 6: Buffer management.

(1) PROCEDURE  BUFFERMANAGEMENT(vehicle  v)

(2) FOR  m  IN  v.queues  DO

(3)   IF   $$Validation(m,v)$$ is FALSE  THEN

(4)    v drops m

(5)   ELSE

(6)    IF  v turns to another road  THEN

(7)      $$m.location=v.location$$

(8)      $$m.quota=m.quota-\mathit{1}$$

(9)    END  IF

(10)    IF   $$RelatedRoad(m,v)$$ is TARGET  THEN

(11)     v accepts m

(12)    ELSE  IF   $$RelatedRoad(m,v)$$ is

(13)     FORWARDING  THEN

(14)     v carries m

(15)    ELSE

(16)     v drops m

(17)    END  IF

(18)   END  IF

(19)  REPEAT

(20)  v sorts v.queues

(21) END  PROCEDURE

Third, each vehicle prioritizes the messages in the transmission queues. When vehicle v encounters u, v may have more than one message suitable to be forwarded to u. Before the transmission starts, v first sorts the messages in its transmission queues according to the priority of message in descending order. Of course, the queues will be also sorted after the roads changed.

The estimation of vehicle turns to other roads in Algorithm 6 also takes advantage of the method shown in Figure 6 and Algorithm 1. The only difference is the changing in vectors and parameters. We focus on the angle between the two vectors of vehicle's direction at different moments. The other two parameters, ${\delta }_{\text{max-}//}$ and ${\delta }_{\text{min-}\perp }$ , are set up to replace the ${\delta }_{\text{max-}//}$ and ${\delta }_{\text{min-}\perp }$ . According to the estimation results, if the directivity relationship is parallel, the vehicle continues to drive on the original road; if the result is reverse, the vehicle turns around on the original road; if it is crossed, the vehicle turns to another road.

5. Performance Evaluation

In order to evaluate the performance of the proposed CMTG protocol, we analyze some important factors in this protocol, and then we compare it with some popular benchmarks, the IVG scheme [11] and Epidemic scheme [31].

5.1. Performance Analysis

We calculated the degree of tolerance to the road bend in this section. It can be used to measure the adaptability of the protocol. At the same time, the Probit Model is detailed. It makes the protocol more robust.

5.1.1. Bent Tolerance

Without complex positioning and navigation software, the CMTG protocol can only use the GPS to determine the mobile tendencies and changes in road of the vehicle. The mobile status of vehicle and message's source location are used to determine the mobile tendency of vehicle in this work. This is a microscopic method without any global information. As we mentioned earlier, we assume that the road is relatively straight but actually not. This protocol takes advantage of the distributed dynamic method that needs not maintain complete roads information. So the roads can be not absolutely straight, but the curvature is also limited.

As illustrated in Figure 7, we assume that the vehicle i, carrying the message m, drives in the curved road SE from the entrance S at time $t-1$ . At time t, it encounters the oncoming vehicle j with a distance of D. Their locations are A and B, respectively. And the current source location of the message location _m has been marked at S when the vehicle i entered the road SE. The determination of whether i and j are both on the same road depends on the magnitude of the angle α between $BS$ and ${\mathit{V}}_j$ .

Figure 7

The simplified model of curved road segment.

The geometric relationships between direction angle and road are

$$\begin{array}{cc}& \theta =\mathrm{2}\alpha \\ L=2R\sin \alpha .\end{array}$$

(14)

For the straight road, the oncoming vehicle j will certainly tend to the source location S. In other words, if the angle θ is small, the road $SB$ will be deemed to be a straight road. Hence, in order to ensure that the road $SB$ is still straight in the view of vehicle j, there must be

$$\begin{array}{cc}& \alpha \le {\alpha }_{\text{max-}//}\\ D\le L.\end{array}$$

(15)

${\alpha }_{\text{max-}//}$ is the maximum angle which is regarded as parallel between the two directions. And the radius of communication should not exceed the length of the road. So, we can get the limitations of curvature, denoted by

$$\begin{array}{cc}& \theta \le \mathrm{2}{\alpha }_{\text{max-}//}\\ R\ge \frac{D}{\mathrm{2}\sin {\alpha }_{\text{max-}//}}.\end{array}$$

(16)

When it comes to the change in roads, as illustrated in Figure 7, we also assume that the vehicle i drives to location E at time $t+1$ ; its yaw angle is δ compared with it first in the road at time $t-1$ . If $\delta >{\delta }_{\text{min-}\perp }$ , that means the vehicle i has left the road $SE$ and entered the next road starting from the location E.

If we assign ${\delta }_{\text{min-}\perp }\le 2{\alpha }_{\text{max-}//}$ , when $\delta \le {\delta }_{\text{min-}\perp }$ , $\delta =\theta \le 2{\alpha }_{\text{max-}//}$ , it means that the road segment can be treated as straight road; when $\delta >{\delta }_{\text{min-}\perp }$ , it means that the vehicle has entered another road. Therefore, if the curved roads meet these conditions in urban environment, the protocol will work well.

5.1.2. Probit Model

A key point in the CMTG protocol is the determination of mobile tendency, and the selection of moving direction decides the tendency. As we mentioned earlier, we would like to establish the Probit Model to predict the directional choice when the angle is in gradual ranges.

In statistics, the Probit Model is a type of regression where the dependent variable can only take two values, for example, 0 or 1. The probability of observing a 0 or 1 in any case depends on one or more explanatory variables. The Probit Model is described as

$$\begin{array}{ll}& P_i=Prob(Y_i=\mathrm{1}\mid x)\\ =Prob[u_i>-({\beta }_{\mathrm{0}}+{\displaystyle \sum }_{j=\mathrm{1}}^k{\beta }_j{X}_{ij})]\\ =\mathrm{1}-F[-({\beta }_{\mathrm{0}}+{\displaystyle \sum }_{j=\mathrm{1}}^k{\beta }_j{X}_{ij})].\end{array}$$

(17)

In this paper, the dependent variable is the directivity. There are also two scenarios: parallel or crossed, crossed or reverse, depending on the magnitude of angle. The explanatory variable is the angle. The model will be described as

$$\begin{array}{cc}& Y_i=F^{-\mathrm{1}}\left(P_i\right)={\beta }_{\mathrm{0}}+{\beta }_{\mathrm{1}}ANGL{E}_i+{\mu }_i\end{array}$$

(18)

The ANGLE _i denotes the angle between two directions; ${\beta }_0$ and ${\beta }_1$ are parameters to be estimated. And $Y_i$ will be described as

$$\begin{array}{cc}& Y_i=\left\{\begin{array}{cc}\mathrm{1},\hfill & crossed\hfill \\ \mathrm{0},\hfill & parallel\hfill \end{array}\right.\end{array}$$

(19)

when the ANGLE _i is in ( ${\alpha }_{\text{max-}//},{\alpha }_{\text{min-}\perp }$ ); it is described as

$$\begin{array}{cc}& Y_i=\left\{\begin{array}{cc}\mathrm{1},\hfill & crossed\hfill \\ \mathrm{0},\hfill & reverse\hfill \end{array}\right.\end{array}$$

(20)

when the ANGLE _i is in ( $\pi -{\alpha }_{\text{min-}\perp },\pi -{\alpha }_{\text{max-}//}$ ).

Finally, we can train the model via real data, and then we use it to predict the results more accurately.

5.2. Simulation Evaluation

In order to evaluate the performance of our protocol we created a mobility model to simulate the vehicle behavior on the road. This mobility model is implemented by means of the Opportunistic Network Environment (ONE) simulator, which is a popular DTN simulator [32].

5.2.1. Simulation Setup

The goal of our simulations is to understand how the CMTG protocol performs compared with other routing protocols under urban road environments.

Existing methods for geographical multicast in DTNs are few and have different assumptions, so comparison is difficult. We can only implement these multicast protocols, illustrated in Table 2, DT-IVG, Epidemic Broadcast (EB), and Direct Broadcast (DB), in the ONE simulator, which are evaluated in terms of the metrics [30].

• (i)

  The dissemination successful rate (DSR) is the number of vehicles located in TR _m which can successfully receive the messages, divided by the total number of vehicles in TR _m .

• (ii)

  The extra overhead rate (EOR) is the total number of packets that all vehicles transmitted and not delivered, divided by the total number of packets that all vehicles transmitted.

• (iii)

  The packet delivery delay (PDD) is the average time that a message is sent from the source vehicle to the target vehicle in TR _m .

Table 2

The compared protocols.

Protocol name	Description
DT-IVG	It is a variant of IVG protocol in DTNs. The nodes can carry the messages and only relay the copies to the farthest one when the communication link is established.
Epidemic Broadcast	It is one of the basic protocols in DTNs. The nodes carry the messages and relay them to all the nodes on the other end of the communication.
Direct Broadcast	It is another basic protocol in DTNs. The nodes carry the messages and only deliver them to the target nodes.

The simulation parameters are given in Table 3. Roads are absolutely straight and vehicles are along the road under random waypoint model. Simulation area is set as 3 km × 2 km with 500 vehicles in it. The network grid-like patterns of roads set up a road every 50 meters. Each node moves at a speed between 5 and 15 meters per second and waits at the waypoint for a random period of time between 0 and 2 minutes. Each node has a communication range of 50 meters, transmits message at 256 kbps, and has a buffer size of 50 MB. Messages are generated randomly by every node every 50 to 70 seconds, with a size randomly chosen between 500 kB and 1 MB. The preferential tendencies and paths of messages are also random. This setup allows for a resource-constrained environment. And each simulation runs for 1000 seconds.

Table 3

Simulation parameters.

Item	Value
Area size	3 km × 2 km
Simulation time	1000 s
Vehicle number	500
Vehicle speed	5~15 m/s
Communication radius	50 m
Transmission rate	256 kbps
Vehicle buffer size	50 MB
Message size	500 kB~1 MB

5.3. Results Analysis

The dissemination successful rate (DSR) is the most important indicator to evaluate the performance of a routing protocol. The changing of DSR over time is also a measurement of the transmission efficiency in geocast. The simulation results of the dissemination successful rate (DSR) changing over time are shown in Figure 8.

Figure 8

The DSR changing over time.

Figure 8 shows that the DSR rise as time evolves. This can be used to represent the propagation velocity of the various protocols. The Epidemic Broadcast takes advantage of all the vehicles as the relays to rebroadcast the dissemination message, and it is the fastest one to completely cover the target area using about 400 seconds. The Direct Broadcast only uses the source vehicle to disseminate message; it is the slowest one and does not cover the target area during the simulation time. The DT-IVG makes use of the farthest vehicle to relay message; then, it is faster than the DB. But it is slower than the EB, since these relays may leave the target area of message. The CMTG utilize just the vehicles in target roads and forwarding roads to relay message. It is faster than the DT-IVG, because its relays are more reliable than what the DT-IVG used. But it is still slower than the EB to completely cover the target area with spending about 600 seconds.

In order to evaluate the overhead performance of these protocols, we change the vehicle number from 100 to 1000. In different network densities, the packet overhead rates are simulated. The simulation results of the extra overhead rate (EOR) under various vehicle numbers are given in Figure 9.

Figure 9

The EOR under various vehicle numbers.

Figure 9 shows that the EOR change as the vehicle number evolves. It can be used to measure the efficiency of these protocols. The overhead of Epidemic Broadcast is also the largest, because all vehicles take part in the dissemination of message; however, most of them are not the target nodes. The overhead of EB is costly for improving the transmission speed. On the contrary, the Direct Broadcast costs the minimal overhead. It is accurate in every delivery without extra cost. Of course, its DSR is the lowest. Although only using the faster vehicles as the relays, the EOR of DT-IVG is still high. This is because the network density is still sparse in the vehicular networks. The number of vehicles in the same communication link is small, and almost every node is the fast one. At the same time, the DT-IVG does nothing when the relay goes out of the target areas; this will cause more extra cost. Compared with the DT-IVG, the CMTG, considering more conditions about the actual roads, reduces a huge amount of overhead. The selected relay is often the target vehicle. And the dissemination is also controlled in the target roads and the forwarding roads. The EOR of CMTG is about 0.5 for the vehicles in forwarding roads.

The distributed of packet delivery delay (PDD) can also be used to measure the dissemination efficiency of routing protocol. A large number of CMTG messages are generated randomly in the simulation scenario, and then the PDD will be counted and after that we can get the distribution. The results of the distribution of the PDD are shown in Figure 10.

Figure 10

The distribution of PDD.

Figure 10 shows the delay distribution of delivered messages. Although the numbers of delivery message are different in these protocols, the distribution of delay can also be used to measure the speed of delivery. The difference between this result and what Figure 10 showed is that a large number of messages are generated in this scenario and many of them will be discarded without the controlling of copies, just like what EB and DT-IVG do. The CMTG disseminates the messages in their target roads and forwarding roads and deletes the copies out of them. Hence, it can guarantee that 80% of the messages are delivered to the target node in 300 seconds. For the same purpose, the DB protocol takes about 550 seconds. Although the EB protocol is faster in the transmission of a single message, the average delay could not be kept at a lower level with more messages loss. The delay distribution of EB protocol is relatively uniform, as the DT-IVG dose, according to the results.

In conclusion, our protocol, considering the conditions of actual roads, is a more suitable candidate in urban vehicular networks. It reduces the extra overhead effectively without slowing down the speed of dissemination and ensures that most of deliveries occur in a relatively short time.

6. Conclusion

This paper proposed a content-based mobile tendency geocast routing protocol (CMTG) for urban vehicular networks. The protocol takes advantage of the vehicle movement state to determine whether the vehicle tends to the source location of message or not and then compares the tendency with the message's preferred tendency to determine whether to accept or forward the message. The different propagation characteristics are taken into consideration to disseminate the messages, and the relevant areas are computed dynamically, so that the overhead of maintaining the geographic multicast areas is eliminated. In performance evaluation, the robustness and adaptability of the proposed protocol are proved theoretically. Finally, our simulation results illustrated the efficiency of the proposed protocol. Through the extensive performance comparisons with other protocols, we can observe the advantages of CMTG in terms of the average message delivery ratio and the average delay.

In the simulation, we assume that the road is straight, the relationship between vehicle and road is accurately, and these are difficult to guarantee in the real environment; we will also research further on these problems.