ABSTRACT

Vehicular Ad Hoc Network (VANET) is a new paradigm of wireless network. Reliable and efficient unicast and multicast routing protocols are critical for VANETs. As a possible solution, opportunistic routing (OR) has received much attention recently. This paper focuses on the aspect of soft security by building trust opportunistic forwarding model in VANET. It incorporates the trust mechanism into OR to enhance the security of routing in resisting malicious attacks. In this paper, we proposed a trusted minimum cost opportunistic unicast routing protocol (TMCOR) and a multicast routing protocol (TMCOM). The simulation results show TMCOR and TMCOM have good throughput, average delay and security gains compared with existing protocols.

1. Introduction

Vehicular Ad Hoc Network (VANET) is becoming an active research area in recent years. VANET is a multihop mobile network designed to offer a wide range of road applications such as safety warning, congestion avoidance and mobile infotainment [1]. VANET has particularly important applications in sparse and rural areas because of the lack of fixed communication infrastructure. That is the reason why routing algorithms appropriate for these circumstances and the design of such a routing protocol is challenging [2,3].

Recently, opportunistic routing has been increasingly recognized by more and more researchers. Opportunistic routing can deal with the lossy, unreliable and varying link quality. The main idea of opportunistic routing is that multiple nodes can potentially be served as the nexthop forwarders instead of pre-selecting a single specific node to be the next-hop forwarder. Once the current node transmits a packet via a single-hop broadcast, all the candidate nodes that have received the packet will determine which one or ones would actually forward the packet according to some criteria (e.g. the one that is closest to the destination will perform the forwarding while the rest will simply drop the packet). As a result, opportunistic routing can take advantage of the potentially numerous unreliable wireless links to forward packet. The most distinct character that opportunistic routing differs from traditional routing is that it exploits the broadcast nature of wireless medium and defers to the forwarder nodes after packet transmissions. This can cope with unreliable and unpredictable wireless links.

There are two main benefits in the opportunistic routing. First, opportunistic routing can combine multiple weak links into one strong link. Second, a traditional routing has to trade off between link quality and the amount of progress that each transmission makes. Opportunistic routing exploits these occurrences to skip some hops and increases the throughput at the same time.

In this paper, we present a trust model based on the concept of trust degree and apply this model to opportunistic routing in VANET. Our model builds a trust relationship for each node with all its neighbors and recommended trust degree. The recommendations improve the trust evaluation process for nodes.

2. Related Work

Biswas and Morris introduced the novel ExOR [4] protocol and showed that network nodes can achieve superior performance than the traditional forwarding by opportunistically forwarding the received data packets [5-8]. introduced several opportunistic routings in wireless networks. Mingming Lu et al. proposed an efficient opportunistic routing [9] and an opportunistic routing algebra based on utility [10]. K. Zeng et al. [11] analyzed the end-to-end throughput of opportunistic routing in multirate and multi-hop wireless networks, and introduced a multi-rate geographic opportunistic routing in wireless ad hoc networks [12]. [13] analysed the efficacy of opportunistic routing. [14] introduced an opportunistic routing in multi-radio, multi-channel and multi-hop wireless networks. In [15], Chachulski et al. introduced the MORE opportunistic routing protocol to address issues in ExOR and achieved high throughput in wireless networks. When nodes have malicious behavior, the adoption of such opportunistic routing protocols might reduce network throughput. [16,17] incorporated the concept of trust into VANET including many trust model and secure routing protocols.

The researches on the trust model in MANET have been extensively performed for a wide range of applications in many areas, such as peer-to-peer computing and E-commerce. Sun et al. [18] proposed a trust model based on entropy. [19] suggested a semiring-based trust model. Peng et al. [18,20] advised a trust model based on Bayesian theory. [21] introduced a trust management framework for mobile ad hoc networks.

There are many scholars who focus on secure and trust routing, which can be mainly classified into two categories: cryptographic technique and non-cryptographic technique. The cryptographic technique mainly focuses on traditional safety mechanisms called hard security strategy. These traditional safety mechanisms are not efficient in confidentiality and authentication in VANET. The other non-cryptographic technique is taken into account as auxiliary way to ensure the soft security of routing. There are some solutions to this issue. Watchdog and Pathrater mechanism [22] are two extensions to the DSR algorithm. Sprite [23] is a simple, cheat-proof, credit-based system for MANET.

On the traditional concept in a network, multicast transmission is a transmission from a single source to a group of destination nodes, and multicast transmission in VANET is normally a transmission from a single source to multiple destinations within a specific geographic region. One of the earliest multicast routing protocols in MANET is called On-Demand Multicast Routing Protocol (ODMRP). By maintaining and using a mesh topology, ODMRP provides path redundancy in forwarding multicast packets to all destination nodes. Another routing protocol is Adaptive Demand-Driven Multicast Routing (ADMR) protocol, ADMR uses tree topology in creating multicast trees or links between the sources, receivers and forwarding nodes [24]. [25] proposed a multicast routing and wavelength assignment in WDM networks. And [26] focused on QoS Multicast Routing in Ad Hoc Networks.

3. Trust Opportunistic Forwarding Routing

This paper integrates quantitative analysis of cost and the secure factor in opportunistic routing. We can adequately utilize the merits of opportunistic routing and make up the security deficiency of opportunistic routing with trust mechanism, which can be further considered as a guideline to design a high trust VANET.

3.1. Degree of Trust

Trust in entities is based on the fact that the trusted entity will not act maliciously. Trust has the following characteristics: it is subjective (different nodes may have different perceptions of the same node’s trustworthiness), asymmetric (two nodes don’t need to have similar trust in each other) and time dependent (it grows and decays over a period of time and it is based on previous similar experiences with the same party). In VANET, a trust relationship that formed from direct interactions can be characterized as direct trust. A trust relationship or a potential trust relationship built from recommendations by a trusted node or a chain of trusted nodes, which create a trust path, is called indirect trust. Moreover, the use of recommendations can speed up the convergence of the trust evaluating process. In this paper, the total trust relationship among nodes also contains these two parts.

Definition 1 Direct trust degree is used to indicate that node i directly observes its neighbor node j with past direct interactions periodically, which is introduced with multiple constraints: time aging factor, reward factor and penalty factor.

The penalty factor is used to distinguish the impact of successful and failed interactions for the evaluation of trust. The successful interaction means the neighbor node not only transmits a packet to its all next-hops, but also forwards devotedly (correct modification if required). The failed interaction means the neighbor node does not forward correctly by launching black hole attacks, greyhole attacks and modification attacks. The purpose of concerning the reward and penalty factor is to encourage cooperation within a VANET by providing some measurements to the benevolent and cooperating nodes. So, direct trust degree can be calculated as follows denoted by:

(1)

where:, TF is a time aging factor, which represents that the trust fades with time during the period, that is,. RF is a reward factor, which denotes the positive impact for the trust in successful interactions during the time period. PF is a penalty factor, which denotes the negative impact for the trust in failure interactions during the time period. So, RF and PF satisfy the following conditions:,. is the period between the current time and the time of last interaction and between node i and node j. s and f denote the amount of successful or failed interactions during the time period, respectively. S and F are the forwarding successful probability or failed probability respectively. Furthermore, ,., RF and PF can be determined according to the practical requirement.

Definition 2 Similarity is referred to the level of similar judging and recommendation ability between node i and node k to some neighbor node for their trust relationship.

When node i and k show the higher similarity, they will have the same opinion towards a node, that is, the two nodes have the same recommendation ability for computation of trust degree Here, let s(i, k) denote the similarity of node i and k, its formula is as follows:

(2)

Obviously,. Where CN(i, k) denotes the number of common neighbor nodes for nodes i and k. T^d(k, u) and T^d(i, u) denote the direct trust degree of node i, k to u respectively. and denote the average direct trust degree of node i and node k that are put on their common neighbor nodes in CN(i, k) respectively.

From Formula (2), we can calculate the similarity between node i and its neighbor nodes. According to all the similarities between node i and its neighbor nodes, we select the most similar nearest-neighbors (the similarity between two nodes should satisfy a certain threshold τ, we can choose appropriate τ according to the practical application scenario, such as τ ≥ 0.6). The m most similar nearest-neighbors are sorted in descending order by similarity. The higher of the similarity of neighbors, the more reliable and trusted they give the recommendation information. So, the trust degree between node i and j can be computed indirectly by node i and the m most similar nearest-neighbors. That is, we can calculate indirect trust degree by the nodes’ similarity as below.

Definition 3 Indirect trust degree is used to represent the recommendation trust degree by most similar nearest-neighbors. Combining the direct trust degree of most similar nearest-neighbors, we can describe the recommendation trust level more reliably, truthfully and precisely.

We can achieve the formula of T^r(i, j) as:

(3)

So, Formula (3) should satisfy the condition obviously:.

The neighbor nodes’ recommendations improve the trust evaluation process for nodes that do not succeed in observing their neighbors due to resource constraints or link outages. The ability of assessing the trust degree of each node using indirect trust degree by recommendations brings several advantages. Firstly, a node can detect and isolate malicious behaviors, avoiding to relay packets to malicious behaviors. Secondly, cooperation is stimulated by selecting the neighbors with higher trust levels to relay packets.

Considering the above mentioned direct trust degree and indirect trust degree, we put the whole trust degree definition as follows.

Definition 4 Trust degree denotes the sum of direct and indirect trust degree between nodes. It is computed as follows:

(4)

where T(i, j) denotes the trust degree between node i and j. α and β denote the corresponding weighting factors for T^d(i, j) (direct trust degree) and T^r(i, j) (indirect trust degree), they can be determined by practical situation (α + β = 1). If the current situation of network is prone to estimate the direct trust, we can set up the condition: 1 > α > β > 0. The interactions between nodes are not frequent and every node may not be familiar with each other during the initializing phase of network. The indirect trust degree is not the key point to be evaluated, so the network only considers the direct trust degree for trust degree (α = 1, β = 0). As the network performs consistently in some periods, the trust relationship will be formed from direct trust along with indirect trust. The detailed algorithm is proposed in Section 4.

3.2. Cost of Opportunistic Routing

Definition 5 The cost of a single routing is referred to as an existing feasible opportunistic routing. Let R denote all existing opportunistic routing from node s to d, and is a route in R.

denote the trust forwarding list. The cost of r relative to R denoted by C_r, the sum of the fore link costs in r.

(5)

where J(i) denotes trust neighbor forwarding list of node i Î r. It is important to emphasize that the cost of a single routing depends on the R (that it traverses) because each consecutive fore link cost d_i,J(i) depends on the entire trust neighbor forwarding list J(i) rather than on the effective forwarder in J(i) that is used.

Because the single route r may suffer from some influences such as interference of wireless channel, dynamic topology and remaining energy consumption of each node, etc. The r emerges with a certain probability, denoted by p(r). The broadcast nature of wireless network can generate the |R| size of opportunistic routing. So, the cost of opportunistic routing can be calculated by COR(R).

Definition 6 The cost of opportunistic routing COR(R) is the sum of all existing feasible routing cost with an emerging probability across the opportunistic routing. Thus COR(R) is expressed as:

(6)

COR(R) denote the cost of opportunistic routing in network. p(r) can be estimated by a number of factors such as the non-deterministic outcome of link layer transmissions, network layer protocol mechanisms and the topology of the network. These depend on the practical conditions of the network (congestion situation, packet sending rate and interference of channels and so on).

3.3. Trust Opportunity Forwarding Mechanism

From the above mentioned definitions, we can derive the minimum cost opportunistic routing by choosing the optimal forwarder and prioritize each node in its trust forwarding list by calculating its cost distance to destination. It can ensure that there is a trust minimum cost routing in all potential routes, and it can also avoid the malicious nodes joining the forwarding list and making malicious attacks. We express the trust opportunistic forwarding mechanism as:

where the whole trust nodes is comprised of the trust neighbor forwarding list J_r Î R(i) of each node i in an existing route r. Let T(i, k) denote the trust degree of between node i and k, k in J_r Î R(i), T(i, k) ≥ T_threshold. T_threshold represents the trust threshold of network. Furthermore, the node that has the higher trust degree and the lowest cost to reach the destination in the J_r Î R(i) is selected as the actual forwarder. As the COR(R) achieves the minimum gradually, trust forwarding list can be formed by selecting the forwarding nodes from the trust neighbor forwarding list of each node in this minimal cost routing.

4. Unicast Routing Protocol TMCOR

We describe the algorithm of Calculating Trust Degree and Updating Direct Trust Degree. We assume that all link delivery probabilities can be evaluated by sending probe packets in the period T. The two algorithms can compute and update the trust degree among nodes in a distributed way. The detailed process is showed in Algorithms 1 and 2.

The basis of protocol TMCOR is Trusted Minimumcost OR, which is depicted in Algorithm 3. A Filtering NeighborMNodes algorithm (see Algorithm 4) is planned by preventing the malicious nodes or links from being added in trust neighbor forwarding list of node i. The algorithm of Minimum-cost OR (G, d) can obtain the minimum cost route of each node from itself to d in G.

The function EXTRACT-LEAST-COST in Minimumcost OR (G, d) indicates that a node having minimal cost to d can be selected from the current node sets. In addition, we also keep a trust forwarding list for each node, which stores the nodes as the candidates for the next hops to d. Let S denote the set of nodes that have a shortest opportunistic routing. Q is a priority queue, which stores the nodes that have a shortest opportunistic routing and is keyed by their D_i .The algorithm is described in detail in Algorithm 3.

5. Multicast Routing Protocol TMCOM

The purpose of the multicast routing protocol is to efficiently disseminate the message to all appointed vehicles in a timely manner. The problem of finding the routing paths resulting in minimum total required transmissions area while ensuring timely delivery, can be defined as a delay-constrained minimum Steiner tree problem [27]. We can use the Algorithms 1 and 2 to calculate Trust Degree and Updating Direct Trust Degree in TMCOM. We can also apply the Algorithm 3 to prevent the malicious nodes or links from being added in trust neighbor forwarding list of node i. The algorithm of TMCOM is depicted in Algorithm 5. The algorithm of Minimumcost OR (G, d) can obtain the minimum cost route of each multicast node from itself to d in G. The delay constraint function for a pair of vehicles then can be defined as:

(7)

where d_a(i, j) is the actual distance between vehicles i and j, which can be calculated using Cartesian coordinate that get from GPS, d_b is the braking distance of each vehicle, , v is the speed of the vehicle, t_R is the reaction time of the driver, and α is the maximum deceleration. Let P(s, r) be the set of all possible paths in G from node s to node r. The delay constraint for node r for the path p is the minimum of the sum of the delay constraint for each pair [27]:

(8)

The core of the multicast protocol is to calculate the multicast tree. The algorithm is depicted in Algorithm 5.

6. Simulation and Analysis

6.1. Simulation Environment

Our simulations are based on the IEEE 802.11b of MAC layer, which is included in the NS2. The vehicles move from a random starting point to a random destination along the road (the speed is uniformly distributed between 0 - 20 m/s). The transport protocol is User Datagram Protocol (UDP). Traffic sources are Constant-BitRate (CBR). The source and destination pairs are randomly spread over the entire network. The packet generating rate is 4 CBR. The number of sources is 10 in the network. These scenario files are generated by the scene generator of the simulator. The mobility model is a random way point model in a rectangular field. Each simulation is done in the presence of 1 ~ 20 malicious nodes. The other related parameters are listed in Table 1.

6.2. Adversary Model

We simulate the following two types of malicious attacks:

1) Black Hole Attack. The malicious node dumps all data packets that are supposed to forward in this attack. It participates in the process of establishing routes, which is initiated by other nodes to maintain the links connectivity;

2) Gray Hole Attack. The gray hole attack is similar to the black hole attack. The malicious node selectively forwards data packets at random interval. In this paper, we assume that the malicious nodes can randomly drop data packets with a dropping ratio in the range of 0.4 - 0.8.

6.3. Result Analysis@NolistTemp# 6.3.1. Performance Metrics@NolistTemp# We will evaluate the performance of our TMCOR scheme comparing with the classic ExOR protocol in terms of throughput, average end-to-end delay, and security-gains. 1) Throughput: the number of packets transmitted per unit time from the source node to the destination; 2) Average end-to-end delay: the total average delay caused by all the packets that are successfully transmitted; 3) Security-gains: in the aspect of resisting the malicious attacks, the increment of security performance caused by adopting the way.

6.3.2. Results and Analysis

In the following paragraphs we evaluate the performance of TMCOR scheme comparing with ExOR in terms of three metrics: throughput, average end-to-end delay, security-gains.

Figure 1 shows the throughput of the two protocols with different number of malicious nodes. The results show that throughputs of the two protocols are progressively reducing with the number of malicious nodes increasing. However, the throughput of TMCOR scheme (from 176 KB/s to 60 KB/s) is a little higher than ExOR protocol (from 160 KB/s to 40 KB/s). This is because the TMCOR scheme reduces the attack of the malicious node by judging and comparing its trust degree value to prohibit it to join the network.

Figure 2 shows that the security-gains of the TMCOR are increasing with the number of malicious nodes increasing. We measure the security-gains as (TMCORTExOR)/TExOR where TMCOR and TExOR denote the network lifetime of the two protocols respectively. The network lifetime is also referred to the longest running time interval as the network suffering from the malicious attacks. The simulation results are shown in Figure 2. When the number of malicious nodes is 20, the security-gains attain the maximum 0.85. Because the effective trust mechanism can identify the malicious nodes and prohibits it to be the actual forwarder. Therefore, the connectivity of network can be further enhanced and the process of delivery packets can be effectively performed.

In Figure 3, we evaluate the average delay of the two protocols as a function of the speed of nodes. As shown in Figure 3, TMCOR scheme achieves a higher average delay than ExOR by 21.9%. This is because TMCOR cost additional delay overhead of ExOR such as collecing information of trust degree, updating the trust degree et al.

Figure 4 is the each data point continuous simulation run 10 times after the average results, can see, TMCOM, MORE, ODMRP three protocols with multicast membership increase its throughput decreased gradually, this is because the increase in the number of multicast members with the average successful transmission time is on the increase, and that the throughput of the three protocols slightly reduce. The throughput of TMCOM scheme