On-demand Misbehavior Detection for Vehicular Ad Hoc Network

Abstract

Maintaining communication links of an established communication path that extends between source and destination nodes is a significant challenge in Vehicular Ad Hoc Networks due to movement of the vehicles. Operations of Vehicular Ad Hoc Network rely on the collaboration of participating nodes to route data for each other. A critical requirement on the nodes is to cooperate with each other for successful data transmission. Thus, the impact of malicious and selfish users must be detected to ensure the operations of Vehicular Ad Hoc Network. In this article, we proposed On-demand Misbehavior Detection technique for vehicle-to-vehicle communication. We adapt two location-based routing protocols, Contention-Based Forwarding and Connectionless Approach for Streets, to our On-demand Misbehavior Detection. Various experiments are conducted to show the effectiveness and efficiency of the proposed On-demand Misbehavior Detection technique. The simulation and analytical results showed that the proposed technique is very effective in detecting misbehaving nodes.

Introduction

In recent years, wireless technology is widely adapted to many areas. In particular, vehicular network, also known as Vehicular Ad Hoc Network (VANET), is a core technology for next-generation intelligent transportation systems (ITS) and major part of smart city research. A VANET provided communication connections for vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) where each vehicle is assumed to equip with a vehicular communication system.^1–3 However, maintaining communication links of an established communication path that extends between source and destination nodes is a significant challenge in vehicular networks due to movement of the vehicles. In particular, such communication links are often broken under a high-mobility environment.

Many more advanced routing techniques have been developed for vehicular networks in recent years. ⁴ To aid the process of establishing and maintaining communication connections, location information (i.e. via Global Positioning System (GPS)) is used in some of the routing techniques. For example, in the location-based approach, each forwarder selects the next forwarding node by comparing the positions of all its neighbors to a destination by a source or an intermediate node. This position information is obtained through periodic broadcasts from neighboring nodes. Some of the location-based approaches are Connectionless Approach (CLA), Contention-Based Forwarding (CBF), Greedy Perimeter Stateless Routing (GPSR), and Trajectory-Based Forwarding (TBF).

Although establishing and maintaining communication links are important tasks in VANET, many works^5–8 have pointed out that the impact of malicious and selfish users must also be carefully investigated. In most of VANET routing protocols, all vehicles (often called nodes) are required to participate in the routing and data forwarding process. However, it is vulnerable to malicious attacks due to lack of infrastructure and centralized administration. Malicious users can drop, modify, or misroute data packets. The purpose of the malicious node is to attack network using various intrusive techniques. As the result, the availability and robustness of the network are severely compromised.

In this article, we introduce an On-demand Misbehavior Detection (OMD) scheme for VANET. Our technique supports detecting misbehaving nodes in the location-based routing protocols under high-mobility environments. In OMD scheme, each node maintains its own Reputation Score (RS) and determines any misbehaving nodes based on other node’s RSs. Many works^5–7,9–11 have been published to combat such problems—misbehaving nodes are detected, and a routing algorithm is employed to avoid and penalize misbehaving nodes. These techniques, however, cannot be applied to the following: (1) location-based routing protocols, since any node in the general direction toward the destination node can potentially help forward the data packets and (2) highly dynamic environment, since nodes (e.g. vehicles) are moving in high speed.

The primary contributions of this article are as follows: (1) we introduce OMD for location-based routing protocols in VANET, (2) we apply the OMD method to two of location-based routing protocols, CBF and Connectionless Approach for Street (CLA-S), and (3) we present simulation and analytical results to show that OMD can successfully detect malicious nodes without false accusation to maintain the good performance of the network.

The remainder of this article is organized as follows. We briefly discuss related works in section “Related works.” The proposed OMD is introduced in section “OMD for VANET.” In section “Experimental results,” we present our experiments with simulation and analytical results. Finally, we conclude this article and discuss future works in section “Conclusion and future work.”

Related works

There are many routing protocols designed to relay data in vehicle network (VANET) and mobile ad hoc network (MANET), for example, Ad hoc On-Demand Distance Vector (AODV), ¹² CBF, ¹³ CLA, ¹⁴ Destination-Sequenced Distance Vector (DSDV), ¹⁵ Dynamic Source Routing (DSR), ¹⁶ GPSR, ¹⁷ Mercury-Like Routing (MLR), ¹⁸ Optimized Link State Routing (OLSR), ¹⁹ and TBF. ²⁰ Early generation routing protocol establish communication link by maintaining routing information in a routing table at each node, for example, DSDV. In DSR and AODV, a source node uses route request to establish a hop-by-hop route between itself and a destination before sending data. In high-mobility environment as VANET, the established route expires quickly, and the source needs to reissue another expensive network wide route request after sending only a few data packets via the previous route.

To reduce networking overhead (i.e. flooding route discovery packets), location information is used, that is, location-based approach. Rather than using the expensive control overhead to pre-establish each link, location-based approaches (e.g. CLA, CBF, GPSR, MLR, and TBF) compare the position of neighboring nodes to a destination and select the next hop to forward the packet. In TBF, each forwarder selects the next forwarding node by comparing the positions of all its neighbors with the trajectory defined by a source. In GPSR, each forwarding node makes a greedy decision by selecting a neighbor that is geographically closest to the packet’s destination as the next hop. In CBF and CLA, nodes allow to dynamically participating in a forwarding of data by comparing its current location with headers of the data (see Figure 1), which contain location information of a source, a destination, and a previous forwarded node. To address obstacle problems in a city environment, many modified versions of routing protocols^21–24 are proposed.

Figure 1.

Dynamic data forwarding in CBF and CLA.

Establishing and maintaining communications links between V2V and V2I are important tasks. However, many works^5–8,25 have pointed out that the impact of malicious and selfish users must also be carefully investigated. The purpose of malicious node is to attack network using various intrusive techniques. In general, nodes in an ad hoc type of network (e.g. MANET and VANET) can exhibit Byzantine behaviors. That is, they can drop, modify, or misroute data packets. As a result, the availability and robustness of the network are severely compromised. Many papers^{5–7,9–11,26} have been published to combat such problems. In general, misbehaving nodes are detected, and a routing algorithm is employed to avoid and penalize misbehaving nodes.

Buttyan and Hubaux ⁶ proposed “nuggets” that serve as a per-hop payment in every packet to encourage nodes to corporate to forward for other nodes. Similarly, Michiardi and Molva ¹⁰ proposed a collaborative reputation and monitoring technique called CORE that keeps track of other entities’ collaboration using reputation. In Buchegger and Boudec, ⁵ a CONFIDANT protocol propagates the bad reputation of node to more than one node. To avoid malicious nodes in their routes, Marti et al. ⁹ modified DSR with a “watchdog” for detection of malicious behavior, and a “pathrater” for trust management and routing policy to rate every path is used. However, misbehaving nodes can adopt any selective dropping strategy to avoid being detected. To address selective packet dropping attach, Audit-based Misbehavior Detection (AMD) ¹¹ is proposed. AMD integrates reputation management, trustworthy route discovery, and identification of misbehaving nodes based on behavioral audits. Nevertheless, the above-mentioned approaches do not punish malicious nodes that do not cooperate, but rather relieves them from the burden of forwarding for other. In other words, the malicious nodes are rewarded in their behavior. Jiang et al. ⁷ proposed a finite state model to penalize the misbehavior nodes and allow them to rejoin only if the behavior improved. However, protocols are not suitable to large-scale and high-mobility networks as in VANET.

In VANET, a number of misbehaving and malicious node detection techniques have also been proposed. The detection schemes are classified into two general types: ⁸ Data-centric and Node-centric. Data-centric approach focuses on verifying the correctness of the data transmitted among nodes to detect misbehaviors. By detecting abnormal activities in data forwarding process, node-centric approach emphasizes on identifying the malicious nodes that are responsible for misconducts. Ghosh et al. ²⁶ focus on post-crash notification application and identify the root cause of the misbehavior. Ho et al. ²⁷ proposed a Collaboration Enforce Technique by detecting data forwarding process among neighboring nodes to maintain network connectivity. Kim and Bae ²⁸ proposed Misbehavior-Based Reputation Management scheme to detect and filter false data with outlier detection method and misbehaving node risk value. The approach evicts misbehaving nodes with their global eviction algorithm.

In Daeinabi and Rahbar, ²⁹ a Detection of Malicious Vehicles (DMV) algorithm is proposed to discover malicious nodes by observing duplicates and drop received packets. Each node is tagged with a distrust value and monitored by the allocated verifier nodes. In Wahab et al., ³⁰ cooperative watchdog approach based on Dempster–Shafer Theory is proposed. It combines with Quality of Service–Optimized Link State Routing (QoS-OLSR) cluster algorithm to maintain stability and QoS to reduce number of selfish nodes. In Bißmeyer, ³¹ a Module-Based Misbehavior Detection is proposed with Kalman filter to identify different mobility data plausibility violations which are based on a physical mobility model for vehicles. Vehicle position can be predicted using previously received position information. When a new message is received, the predicted position can be compared with the stated position whereupon large deviations are suspicious, hence may result in misbehavior detection. To improve over the work by Daeinabi and Rahbar ⁴ and Wahab et al., ²⁹ the work by Kadam and Limkar ³⁰ detects and prevents malicious nodes from VANET which reduces the impact of black hole attack.

However, in highly dynamic environment (e.g. vehicles move in high speed), the performance of proposed approaches is reduced due to nodes’ high mobility. This article proposed a node-centric detection scheme called OMD which combines two of the location-based approaches, CBF ¹³ and CLA, ¹⁴ for OMD in VANET.

OMD for VANET

In a general location-based routing protocol, it follows three steps: Location Discovery (LD), Location Reply (LR), and Data Forwarding. For LD, the source node will broadcast an LD packet that contains source node ID, destination node ID, location of the source node, and a unique request ID to determine the location of destination. The LD packet will propagate (i.e. broadcast) the unit when it reaches the destination node. When the destination node receives the LD packet, it will reply with LR packet. The LR packet includes the location of the source node and the location of the destination node. When an intermediate node receives an LR packet, its forwarding procedure will determine whether it needs to forward the packet by comparing its current location with the location of the source. Similarly, when a node receives a data packet, its Data Forwarding procedure also makes a decision based on the location information inside of data packet and its current location. To reduce broadcast storm problem, different delay values are applied to the Data Forwarding procedure. All the abbreviations used in this section are listed in Table 1.

Table 1.

Abbreviation to definition.

Abbreviation	Definition
Avg_RS	Average Reputation Score
CA	Certificate Authority
CBF	Contention-Based Forwarding
CLA	Connectionless Approach
CLA-S	Connectionless Approach for Street
CRL	Certificate Revocation List
D_Distn	Distance between node n and the center of the destination cell
Distn	Distance between node n and the center of the cell of previous relaying node
F_Count	Number of packets that are forwarded
FR_Count	Number of packets that are in forwarding request procedure
LD	Location Discovery
LD_Count	Number of LD packet initiated by a node
LR	Location Reply
OMD	On-demand Misbehavior Detection
RS	Reputation Score

In OMD, each node keeps its reputation by counting the following: (1) number of LD packet (LD_Count) that initiated by itself, (2) number of packets (FR_Count) that are in forwarding request procedure (i.e. received and waiting for forward), and (3) number of packets that are forwarded (F_Count). The three reputation counters are maintained and verified using security credentials, digital signature, or cryptographic to authenticate the counter information. For the authenticity and integration of the reputation counters, a public/private key cryptographic is applied with a trusted Certificate Authority (CA) ³² that initializes and certificates keys for every node in the network with a Certificate Revocation List (CRL). Nevertheless, any secure cryptosystem can be applied to our system. However, managing and establishing a secure network is beyond the scope of this article.

Reputation update

OMD updates the three reputation counters as follows:

1. When a node initiates an LD packet, it increments its LD_Count by one.

2. When a non-destination node receives a new (never seemed) packet, it increments its FR_Count by one.

3. When a node forwards a packet, it increments its F_Count by one.

In a location-based routing protocol, every node needs to consistently participate in a forwarding process. Thus, the ratio of F_Count to FR_Count will be similar between neighboring nodes. However, a misbehaving node can intentionally drop packets by modifying its own routing protocol. In this case, the misbehaving node will have much lower forwarding ratio (i.e. F_Count to FR_Count) compared to its neighboring nodes. We call this forwarding ratio as RS. Flowchart for reputation update is shown in Figure 2.

Figure 2.

Flowchart for reputation update.

When a node i initiates an LD packet, the RS is included in the packet header. If a node j received i’s LD packet, j will determine whether i might have misbehaved as follows:

1. Node j compares its own Reputation Score (RS_j) with i’s Reputation Score (RS_i).

2. If RS_j*Threshold > RS_i, node j will ask its neighboring nodes for their RSs. Threshold is set to 0.8 which allows 20% of RS difference between i and j.

3. Node j calculates the average RS (Avg_RS) of its neighboring nodes.

4. If j’s Avg_RS > RS_i, node j initiates OMD procedure.

5. Otherwise, if RS_i ≥ RS_j*Threshold or RS_i ≥ Avg_RS, node j will forward node i’s LD packet (see Figure 3 for the flowchart of forwarding process for LD packet).

Figure 3.

Flowchart for forwarding LD packet.

OMD procedure

Our OMD procedure has two states: Listening state and Detecting state. When a detection node d initiated its OMD procedure, d first enters the Listening state to determine whether a suspected node s is being misbehaving and other nodes also initiated OMD procedure against s. Note that many neighboring nodes of s can enter listening state. In this state, node d acts as follows:

1. It waits for a random period of time (i.e. delay timer).

2. If d hears a detection packet from another node, n resets its delay timer and listens to see whether node s forwards the detection packet.

3. If the detection packet has been forwarded by s, n exits the OMD procedure and forwards the LD packet from s.

4. Otherwise, d will enter the Detecting state when its delay timer ended.

Similarly, other nodes that are in the listen state due to s will exit their OMD procedure if they hear the detection packet forwarded by s. Different routing protocols have different delay timer value settings (see sections “OMD for CBF” and “OMD for CLA-S”).

In the Detecting state, node d generates a detection packet based on the location of the suspected node s. Detection packet is similar to regular data packet that contains the location information of source node and destination node. In general, the location of the source node is behind d, and the location of the destination node is behind s. According to different routing techniques, different detection packets can be created based on the specification of the routing protocol. We will discuss more in detail on the detection packet generation for CBF and CLA in the next section. Next, d starts to detect the suspected node s as follows:

1. d broadcasts the generated detection packet and waits for a random period of time (i.e. delay timer). All the neighboring nodes of s that are in Listening or Detecting state will wait and listen for s to forward the packet.

2. If d waited until the end of the delay timer and did not receive the detection packet forwarded by s, node d will repeat Step 1 two more times.

3. If d hears the detection packet forwarded by s, d exits the OMD procedure and forwards s’ LD packet.

4. Otherwise, d marks s as a misbehaving node and punishes s by discarding s’ LD packets.

Misbehaved node s can rejoin the network until its Reputation Score (RS_s) is similar to its neighboring nodes. Thus, s will need to forward for others in order to increase its RS_s until either RS_s ≥ RS_others*Threshold or RS_s ≥ Avg_RS. Flowchart for OMD procedure is shown in Figure 4.

Figure 4.

Flowchart for OMD procedure.

Notice that any node can activate the OMD procedure if it suspects that a node is being misbehaved. If a node is identified as a misbehaving node, other nodes will punish the misbehaving node by dropping its LD packet. Nodes that received (and drop) a misbehaving node’s LD packet will not update their FR_Count. This will limit the misbehaving node to take the advantage of the network resource. Other nodes will forward all other packets (e.g. data packets, other node’s LD and LR packets) from a misbehaving node. The only way that a misbehaving node m can rejoin the network is to contribute to the forwarding process for others. By forwarding for others, node m will increase its F_Count_m and RS_m. Once RS_m ≥ Avg_RS or RS_i, other nodes will forward m’s LD packet.

OMD for CBF

In this article, we modified two location-based routing protocols, CBF ¹³ and CLA-S, ²¹ with OMD procedure. In CBF, a node forwards a packet as a single-hop broadcast to all of its neighbors, which then compete with each other for the “right” to forward the packet. During this contention period, the forwarding node determines which node is suitable as the next hop for the packet. The node that wins the contention suppresses the other nodes and establishes itself as the next forwarding node. The contention is based on the distance of the nodes to the destination that is greedily minimizing the remaining distance to the destination (see Figure 5).

Figure 5.

Contention-Based Forwarding (CBF).

For the contention period in CBF, a timer is used to compete the right to forward. The timer t(P) is selected as follows

$$t\left(P\right)=T(1-P)$$ (1)

where T is the maximum delay, and P is the progress that minimized the distance to the destination.

To generate a detection packet that is similar to a data packet in CBF, a detection node d will use the suspected node s’ location information included in the LD packet sent by s. Using s’ location information, d can generate the detection packet with a fake destination node’s location behind s and a source node’s location behind d. Therefore, if s is not a misbehaving node, it will forward the detection packet.

OMD for CLA-S

In CLA-S, the streets are divided into small “virtual cells.” Those virtual cells are divided according to intersections and blocks (see Figure 6). With LD procedure, source discovers the location of the destination. Using destination location, the source computes and selects a list of grid cells that form a path between the source and destination. Nodes within the path will forward the packet toward the destination.

Figure 6.

Connectionless Approach for Street (CLA-S).

Similar to CBF, the forwarding procedure selects a node farther away from the source and closer to the destination node when forwarding packets. A delay timer is used to determine the next forwarding hop. The delay of a node n is computed as follows

$$\mathrm{DELA}{Y}_n=|\frac{\alpha }{2·D\_\mathrm{Dis}{t}_n}-\frac{\alpha }{2·\mathrm{Dis}{t}_n}|$$ (2)

where α is a maximum delay constant in µs, D_Dist_n is the distance between node n and the center of the cell denoted by the Destination Cell ID in the packet header, and Dist_n is the distance between node n and the center of the cell denoted by the Current Cell ID (cell of previous relaying node m) in the packet header (see Figure 7).

Figure 7.

Delay timer for CLA-S.

In OMD procedure for CLA-S, a detection node d will use the location information of a suspected node s to generate a detection packet with a fake destination node in CLA-S. In Figure 6, for example, if node d is located at Cell A and node s is located at Cell B, then the fake destination node’s location will be in Cell C. Therefore, node s will most likely forward the detection packet.

Experimental results

In this section, we discuss the setting of our experiments, implemented schemes, performance metrics, and the performance results.

Simulation setting

All experiments were conducted using NS-3. ³³ Road network and traffic model are generated using Simulation of Urban MObility (SUMO) ³⁴ with different traffic patterns according to Chiao ³⁵ with average of 50 vehicles. Simulation is running under Ubuntu 14.04 LTS with Linux OS. We use IEEE 802.11p ¹ WAVE ³ provided by NS-3 for wireless interface. Each node has a radio range of about 250 m. Traffic applications are constant-bit-rate sessions involving 1/10 of all nodes. Each data packet is 512 bytes. Multiple simulation runs (20 runs per setup on average) were conducted for each scenario, and the collected data were averaged over those runs with a 95% confidence interval.

The field configuration is an area of 900 × 900 m² field with each road segment of 300 m. Roads and intersections are shown in Figures 8 and 9. The field configuration simulated a part of Taipei (see Figure 9). Using SUMO, we input traffic data set from those roads in Figure 9’s blue-dotted lines with traffic data according to Chiao ³⁵ with average of 50 vehicles. For the experiment for CLA, each road segment is assigned a cell ID, Virtual Router # (i.e. VR1–VR24) as shown in Figure 8.

Figure 8.

Street field configuration.

Figure 9.

Traffic data from part of Taipei City.

Implemented schemes

To verify the effectiveness of our OMD, three schemes are compared: Reference scheme, Defenseless scheme, and proposed OMD scheme.

• In the Reference scheme, all nodes collaboratively relay data for each other (i.e. no misbehaving nodes).

• In the Defenseless scheme, a certain fraction of nodes is misbehaving as they failed to participate in forwarding procedure. In other words, these nodes discard any packets not destined at them. No detection or prevention mechanism is implemented so that the network is totally “defenseless.”

• In OMD scheme, misbehaving nodes are detected and punished. Two location-based routing protocols (i.e. CBF and CLA) are compared (see Table 2).

Table 2.

Two routing protocols under three schemes.

	Defenseless	OMD
CBF	CBF-DL	CBF-OMD
CLA	CLA-DL	CLA-OMD

OMD: On-demand Misbehavior Detection; CBF: Contention-Based Forwarding; CLA: Connectionless Approach; DL: Defenseless.

Performance metrics

In the experiments, we evaluated OMD under six performance metrics: Misbehaving node detection ratio (MDR), False accusation ratio (FAR), Packet delivered ratio (PDR), Control overhead ratio (COR), End-to-end delay (EED), and Initiate detection ratio (IDR):

• MDR is the number of misbehaving nodes that was correctly identified to the total number of misbehaving nodes.

• FAR is the number of OMD that incorrectly accused that a node is misbehaved to the overall number of misbehaving nodes.

• PDR is the number of data packets received by destinations to the number of data packets generated by Constant bit rate (CBR) source.

• COR is the number of routing packets (LD and LR packets) and the number of detection packets transmitted per distinct data packet delivered to a destination.

• EED is the total delay time (in ms) from a sender to a destination. EED included route discover latency, queuing delays, retransmission delay, and propagation and transmission delay. In addition, the measurement also detects and processes misbehaving node delay, but does not include the sessions that belong to misbehaving nodes. The misbehaving nodes’ sessions will include additional delay due to penalty from OMD scheme.

• IDR is the number of nodes that initiated its OMD procedure and entered Detection state per LD packet generated by misbehaving node.

Results on misbehaving node detection

In this experiment, we varied the number of misbehaving nodes (i.e. 5%, 10%, 20%, and 30% of the total number of nodes) and the speed of nodes (i.e. 10, 15, 20, and 25 m/s). In Figure 10, the MDR results show that OMD is very effective in both CBF and CLA. With the speed up to 25 m/s, OMD still achieved about 80% of correctly detected misbehaving nodes. We notice that with increase in speed, OMD’s performance of MDR is decreased. Under high mobility, a misbehaving node can move out of communication range (or make a turn at a street) of a detection node before the detection node initiates the OMD procedure. Nevertheless, the performance MDR is only decreased about 15%.

Figure 10.

Misbehaving node detection ratio (MDR).

Results on false accusation

The FAR of proposed OMD is shown in Table 3. In all the node mobility scenarios, the FAR is under 10% of the total number of nodes identified by OMD as misbehaving nodes. By inspecting simulation’s log files, only about two to three nodes were false accused under all simulation configurations. Similar to MDR, we observed that when the FAR is higher, the speed of nodes increased. This is due to the fact that the detection node started the OMD procedure and the suspected node moved out the detection node’s radio range. Since the detection node did not hear any detection packets been forward back from the suspected node, the detection node falsely accused the suspected node as a misbehaving node. In the case of MDR, the detection nodes missed detecting misbehaving nodes because it did not initiate the OMD procedure before the suspected node, that is, the actual misbehaving node, moved out the detection node’s radio range.

Table 3.

False accusation ratio (FAR).

Speed (m/s)		10		15		20		25
Routing protocol		CBF-OMD	CLA-OMD	CBF-OMD	CLA-OMD	CBF-OMD	CLA-OMD	CBF-OMD	CLA-OMD
Number of misbehaving nodes	5%	1%	1%	2%	2%	3%	2%	4%	5%
	10%	1%	2%	1%	3%	2%	3%	4%	4%
	20%	3%	4%	4%	4%	7%	6%	7%	7%
	30%	5%	5%	6%	6%	8%	7%	9%	8%

OMD: On-demand Misbehavior Detection; CBF: Contention-Based Forwarding; CLA: Connectionless Approach.

Results on packet delivery

In this experiment, a malicious node that can recognize itself is being punished when LD packets of the node has been dropped four consecutively times. Once the malicious nodes recognized that they have been punished, they will participate in forwarding data to rejoin the network. Two location-based routing protocols, CBF and CLA, are modified with our OMD scheme. As before, we varied the speed of nodes (i.e. 10, 15, 20, and 25 m/s), but the number of misbehaving nodes is set to 30% of the total number of nodes.

The Reference scheme showed the performance of CBF and CLA when no misbehaving nodes presented in the network. Both CBF and CLA have achieved above 85% of PDR. When we introduced 30% of misbehaving nodes in the network, the performance dropped very quickly in the Defenseless scheme (CBF-DL and CLA-DL, see Figure 11). With OMD scheme, both CBF-OMD and CLA-OMD are almost able to recover the packet delivery rate to the original performance with about 5% of differences compared with the Reference scheme.

Figure 11.

Packet delivery ratio (PDR).

Results on control overhead

In this experiment, we set the number of misbehaving nodes to 30%. In Figure 12, the Reference scheme (i.e. no misbehaving nodes) showed the control overhead of the routing protocol of CBF and CLA. In the Defenseless scheme, we observed that the COR is increased for about 10–25 packets due to the misbehaving nodes dropping packets (e.g. routing and data packet). This causes the need to frequently re-establish route by re-broadcast routing packets and re-sent data packets. In the OMD scheme, the COR is also increased for about 3–15 packets which is due to the detection packets. This is inevitable for detecting misbehaving nodes. As we increase the speed from 10 m/s (or 22 mile/h) to 25 m/s (or 56 mile/h), the number of detection packets is also increased. This is due to the fact that some of suspect nodes moved out of the detection node’s radio range and thus cause more nodes to initiate OMD procedure to send more detection packets.

Figure 12.

Control overhead ratio (COR).

Notice that speed of nodes affects four performance metrics (MDR, FAR, PDR, and COR) and all three schemes (Reference, Defenseless, and OMD). High mobility of mobile host causes frequent and unpredictable changes between communication connections between nodes. Thus, maintaining communication links of an established communication path is a significant challenge in vehicular networks.

Results on EED

We report the results of EED in Figure 13 with 30% of misbehaving nodes. We observed that the additional EED is incurred by initiating OMD procedure. In OMD procedure, if a node d suspects that another node s is being misbehaved, d suspends the forwarding process of s’ LD packet. According to Table 3, more than 90% of the delay is due to the misbehaving nodes. The effect of misbehaving nodes is also showed in the Defenseless scheme (CBF-DL and CLA-DL). With OMD, misbehaving nodes are unable to utilize the network resources once they are identified. In average, the delay is only increased by 10 ms compared to the Reference scheme. This is due to the fact that other nodes can continue to forward data packets, while one node is detecting a misbehaving node.

Figure 13.

End-to-end delay (EED).

Results on IDR

In this experiment, the total number of nodes in the network increased from 50, 100, 150, to 200. The number of misbehaving nodes is 30% of the total number of nodes. The results on the number of nodes that activated OMD procedure and initiated Detection state, that is, IDR, are shown in Figure 14. The results showed the effect of the IDR performance on both number of nodes and speed of nodes. When the number and the speed of nodes increased, the number of nodes that initiated Detection procedure also increased. However, we observed that the node speed has more effect on the IDR. We observed that the node speed has more effect on the IDR. In average, only 8 nodes initiated detection per LD packet generated by misbehaving node when there are 200 nodes in the network.

Figure 14.

Initiate detection ratio (IDR).

Performance analysis

To validate the simulation results, we performed analytical analysis as in Ho and Chen. ²² The analytical model and the results are presented in this section.

Problem formulation

We consider a set V of n = |V| mobile nodes (e.g. n vehicles) in a network field. Each mobile node has a unique ID $v_i\in \{v_1,v_2,\dots ,v_n\}$ . The portion of the hybrid network that consists of only the mobile nodes and client gateways can be modeled as a probabilistic directed graph

$$G=(V,L,D)$$ (3)

where a vertex $v_i\in V$ denotes a mobile node or a client gateway, an edge $l_{v_i,v_j}\in L$ denotes a communication link from node $v_i$ to node $v_j$ , and a delivery ratio $d_{v_i,v_j}\in D$ for link $l_{v_i,v_j}$ . Delivery ratio is the probability that a packet is successfully received in a single transmission along the link. If the link contains misbehaved node, the successful delivery ratio is zero. We assume that the delivery ratios are constant,^36,37 and link failures are statistically independent. ¹¹

Analytical model

Our analysis focuses on data relay performed by the mobile nodes toward or from the client gateways. Let $s,d\in V$ be the source and destination nodes of a packet transmission, respectively. R is the set of all possible communication routes between any two nodes in V. The function $f:V\times V\to R$ maps a source node $s\in V$ and a destination node $d\in V$ to a data forwarding route, $R_{s,d}\in R$ , between s and d as follows

$$\begin{array}{cc}\multicolumn{1}{c}{R_{s,d}=}& \{(s=r_0,r_1,r_2,\dots ,r_N,r_{N+1}=d)\hfill \\ \multicolumn{1}{c}{}& |\mathrm{dist}(r_i,d)<\mathrm{dist}(r_{i+1},d)\hfill \end{array}\}$$ (4)

where r₀ is the source node; r₁, …, r_N are the N intermediate nodes; r_N + 1 is the destination node; and $\mathrm{dist}(r_i,d)$ is the hop distance between node r_i and the destination node d. In other words, $R_{s,d}$ is an ordered set, with the sequence of nodes that form the forwarding route for the data packets. This ordered set is a result of the proposed OMD scheme with CBF and CLA presented in section “OMD for VANET.” We have $|R_{s,d}|=N+2$ .

Given in equation (4), we can define the set of communication links (i.e. edges) between s and d as follows

$$L_{s,d}=\{l_{r_i,r_j}\in L|r_i,r_j\in R_{s,d}\mathrm{and}i<j\}$$ (5)

The set $L_{s,d}\subseteq L$ comprises the set of links that allow the data packets to traverse toward the destination d. Since link failures are statistically independent, the probability for a packet received by $r_j$ from $r_i$ is as follows

$$p_{r_i,r_j}=\{\begin{array}{cc}{d}_{r_i,r_j}\sum _{k=j+1}^{N+1}(1-d_{r_i,r_k})\hfill & \forall i\le j\hfill \\ \multicolumn{1}{c}{0}& \forall i>j\hfill \end{array}$$ (6)

where $r_i,r_j\in R_{s,d}$ , and $d_{r_i,r_j}$ is the delivery ratio of $l_{r_i,r_j}$ . Based on equation (6), the matrix $P_{s,d}\in [0,1{]}^{(N+2)\times (N+2)}$ can be constructed as follows

$$P_{s,d}=\left[\begin{array}{cccc}{p}_{r_0,r_0}\hfill & p_{r_0,r_1}\hfill & \cdots \hfill & p_{r_0,r_{N+1}}\hfill \\ \multicolumn{1}{c}{0}& p_{r_1,r_1}\hfill & \cdots \hfill & p_{r_1,r_{N+1}}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & \dots \hfill & p_{r_{N+1},r_{N+1}}\hfill \end{array}\right]$$ (7)

With the probabilistic directed graph G and the parameters defined above, we introduce the overlay graph G_s,d (see Figure 15(a)) as follows

$$G_{s,d}=(R_{s,d},L_{s,d},P_{s,d})$$ (8)

Figure 15.

Routing tree: (a) overlay graph and (b) routing tree.

Analytical derivation of the average transmission number

By exploring all the branches of the tree in Figure 15(b), the average number of transmissions, after some simple algebraic manipulation, is as follows

$${\overline{n}}_{s,d}=\sum _{i=1}^{\infty }{\left(p_{\mathrm{s},\mathrm{s}}\right)}^{i-1}[i{p}_{s,d}+p_{s,r}\sum _{j=1}^{\infty }(i+j)p_{r,d}{\left(p_{r,r}\right)}^{j-1}]$$ (9)

With the notable relation $\sum _{n=0}^{+\infty }n{x}^n=x/(x-1{)}^2$ and $\sum _{n=0}^{+\infty }{x}^n=1/1-x$ , if $|x|<1$ and after some algebraic manipulation, the closed form for equation (9) can be obtained as follows

$${\overline{n}}_{s,d}=\frac{1}{1-p_{s,s}}[\frac{p_{s,d}}{1-p_{s,s}}+\frac{p_{s,r}{p}_{r,d}}{1-p_{r,r}}(\frac{1}{1-p_{s,s}}+\frac{1}{1-p_{r,r}})]$$ (10)

According to Cacciapuoti et al., ³⁸ the recursive closed form for the average number of transmission can be expressed as follows

$${\overline{n}}_{s,d}=\frac{1}{1-p_{s,s}}\left[\begin{array}{c}1+\sum _{k=1}^N{p}_{s,r_k}{\overline{n}}_{r_k,d}\hfill \end{array}\right]$$ (11)

where

$${\overline{n}}_{r_k,d}=\frac{1}{1-p_{r_k,r_k}}\left[\begin{array}{c}1+\sum _{l=1}^N{p}_{r_k,r_l}{\overline{n}}_{r_l,d}\hfill \end{array}\right]$$ (12)

To validate the correctness of the simulation of the OMD scheme (i.e. CBF-OMD and CLA-OMD), we compare the simulation results with the results from the closed-form expression of the analytical framework. Nodes are randomly placed in the street topology, as shown in Figure 8, with source, destination, and misbehaving nodes randomly selected. The misbehaving node is 30% of the total number of nodes. The analytical and simulation results are plotted in Figure 16. We can observe a good correlation between the simulation and the theoretical results. This confirms the correctness of our simulation.

Figure 16.

Average transmission number.

Analysis on overhead and number of detection nodes

Similar to Ho et al., ²⁷ on analyzing the number of detection nodes, we assume that a misbehaving node is stationary and no obstacle (e.g. buildings) within the network. Therefore, the maximum number of neighboring nodes in the Detection state is six nodes (see Figure 17). With buildings, the number of neighboring nodes will be less then six nodes. If a malicious node is moving at speed of 20 m/s, then the moving range (i.e. a circle with radius of r) within the maximum delay time (t = 2 s) of the Detection Mode is as follows

$$r=\mathrm{speed}*\mathrm{time}=20(\mathrm{m}/\mathrm{s})*2\left(\mathrm{s}\right)=40\left(\mathrm{m}\right)$$ (13)

With the radio range of a node being 250 m, the radius of circular area of the maximum area of neighboring nodes that can activate Detection Mode is as follows

$$r\prime =r+\mathrm{radio}\mathrm{range}=40\left(\mathrm{m}\right)+250=290\left(\mathrm{m}\right)$$ (14)

Therefore, the maximum number of neighboring nodes in the Detection state is increased to seven nodes without considering any buildings (see Figure 18). To move out of the range of these seven nodes, a misbehavior node needs to move a distance of 250 (m) + 290 (m) = 540 (m). If moving speed is 20 (m/s), time to move out the area covered by the seven nodes is 27 s. Therefore, the upper bound for IDR is about seven nodes per 27 s. This also confirmed with our simulation results in Figure 14 where IDR is between 7 and 8 nodes at speed 20 (m/s). In addition, it is also confirmed that the results of COR increased between 11 and 13 packets compared between Reference scheme and OMD scheme at speed of 20 (m/s) (see Figure 12).

Figure 17.

Number of detection nodes needed per malicious node at 0 (m/s).

Figure 18.

Number of detection nodes needed per malicious node at 20 (m/s).

Conclusion and future work

In this article, we proposed an OMD to support location-based routing protocols for VANET. In OMD scheme, number of LD packet (LD_Count), forwarding request packets (FR_Count), and forwarded packet (F_Count) are used to calculate node’s RS. Nodes detect each other for any misbehavior based on the RS. If a node is suspected as a misbehaving node, others will initiate OMD procedure to determine whether the suspected node is actually misbehaved. We extended two location-based routing protocols (i.e. CBF and CLA) with our OMD. Various experiments are conducted to study the effectiveness of OMD scheme. The simulation results showed that the proposed technique is able to effectively identify any misbehaving nodes with slightest false accusation (i.e. about 2–3 nodes) under different settings. In addition, we showed that two location-based routing protocols with extension of OMD (CBF-OMD and CLA-OMD) are able to recover the effect of misbehaving nodes. As a result, the network throughput (i.e. PDR) is greatly improved compared to the Defenseless scheme.

For the future work, there are several directions that we intend to explore. First, we noticed that mobility will reduce the performance of OMD. We would like to investigate the effect of the speed with mobility aware detection technique. For example, if a node is under high mobility, OMD should be able to adjust its detection procedure, for example, frequency or number of detection packets. In addition, we intend to investigate on different network densities to see the effect to our OMD. Third, the threshold value for initiating the detection procedure should be analyzed under a real network condition. Different areas might be experiencing different network conditions, for example, interference, high workload, and link congestion. The threshold value will need to be adjusted according to the different network conditions.