Trust Formulization in Dynamic Source Routing Protocol Using SVM

Published Online July 2014 in MECS

With the rapid development of wireless communication devices such as mobile phones, laptops, Personal Digital Assistants (PDAs), navigators, cordless phones and gaming consoles, people mostly depend upon the wireless ad-hoc networked to the inherent vulnerability of wireless ad-hoc network [1], several new security mechanisms are required to be developed to efficiently protect them. Now a day’s most of the researches are an emphasis on the network security. Recently, a few key management schemes have been proposed to ensure secure communication over MANET but these techniques are not more suitable for MANET because they required some centralized administration mechanism or trusted [2] third party to issue digital certificate or observe network traffic. The centralized trusted third party actually violates the nature of selforganization. This paper focuses on the detection of malevolent nodes on the bases of behavior of nodes in DSR routing protocol (DSR is well recognized and popular reactive protocol used in mobile ad-hoc network.) [3] with the help of support vector machine. This work can help to distinguish ‘‘normal’’ against ‘‘intrusive’’ behavior efficiently. This paper uses well-known SVM based classification algorithm and uses categorized datasets obtained from a simulated environment.

The idea of trust is started when the watchdog applied to the DSR routing protocol. Trust between the nodes can be computed by several methods such as cryptography, soft computing, and fuzzy logic prediction rules some of these methods are described in the section 3.

The experiments have been accomplished with datasets produced under numerous traffic conditions regarding the network mobility and the number of malicious nodes. This paper also represents a comparison of several DSR that provides the secure routing in MANET.

In Section 2 we present the motivation of our work. Section 3 presents an analysis of related work. Section 4 describes SVM based misbehavior detection. Section 5 explains the details of the experimental setup and Section 6 presents the results obtained. Finally, we conclude in Section 7.

• II.    Motivation

• A.    Ad-hoc Network

Mobile ad-hoc network is a decentralized and an infrastructure less type of network in which each node can communicate with every other node within the transmission range and each node in MANET [4] are mobile. In MANET when a node needs to be transmitted a packet (data/control) to another node that does not belong in its one hop neighbor, then it has to rely to the intermediate node to forward the packet to the destination this mechanism is known as multi hop. Current investigation [5-6] designates that the wireless ad hoc network is more vulnerable than the conventional wired and wireless networks due to its underlying features of open medium, dynamic network topology, limited bandwidth, distributed cooperation and limited energy resources. Thus, well-organized routing protocols [7] are required in order to enhance the communication paths. Several routing protocols have been proposed for MANET. They are mainly classified into two categories proactive and reactive routing protocol, former is the table driven routing protocol in it all the routes to destinations or for other nodes are pre-determined and preserved by the episodic update process and in proactive routing protocol routes are created on the fly or when needed. These all protocols suffer from attacks from malicious nodes because these traditional routing protocols do not encompass any security mechanism. For securing routing in recent a new class of routing protocol has been proposed called trust based routing protocol [8].

• B.    Trust in Ad-hoc Network

The inherent nature of MANETs provokes the appearance of new security hazards, while some existing weaknesses in wired networks are emphasized. To secure MANET from such hazards notion of trust has come in the field of MANET security. Trust is a more complex subject in physiological environment and it is influencing of assumptions, expectations, behaviors, environments, and other factors [9].

• III.   Related Work

Mobile ad hoc networks show new vulnerabilities to malevolent attacks or rejection of collaboration due to their characteristics. To secure the MANET a new class of security mechanism has been proposed, which are based on trust. Several trust models have been proposed which are used in the conjunction with routing protocol.

Liu et. al. [4] has been proposed a trust model in which each node detects an attack from malicious nodes in its radio range. For this model information about the attacker is propagated through the data packet instead of control packet, thus it decreases the control packet overhead. The drawback of this model is that interrupting transmission may cause undesirable results. Xia. et. al. [2] Proposed a trust management model based on fuzzy logic, this trust model is divided into two parts: subjective trust evaluation model and trusted routing model. This model correlates the MANET network as the directed graph where each node in MANET is connected by direct link and each node assigns some weight value. Throughput of the network is increased when this model is used for trust computation. All the models described above uses single scaling factor for the calculation of trust and these all models are relay on a well define the threshold to identify the possible misbehavior. A smart attacker can easily adjust this threshold value by changing its behavior from time to time. To overcome these problems Wenjia Li [10] proposed a misbehavior detection model based on support vector machine. The support vector machine is a classifier and use to detect the misbehavior. SVM do not rely on any pre-define normal behavioral pattern, nor does it require a pre-defined threshold to discriminate regular behavior from anomalous behavior.

• A. Several secure DSR routing protocol

Marti et. al. [11] has been proposed watchdog and pathrather mechanism. In this mechanism each node in the MANET network contains a watchdog which monitors the behavior of its immediate neighbor and pathrather avoid routing through malicious nodes this protocol dose nothing to penalize these nodes and suffer from a black hole attack. Ariadne [12] uses one of the following three mechanisms: shared keys between all pairs of nodes, Shared secret keys between communicating nodes combined with broadcast authentication and digital signature for authentication of the routing message. Ariadne needed some centralized authority and is not more suitable for mobile Ad-hoc network. CHENG Yong et. al. [1] proposed a trusted dynamic source routing protocol which is an extension to the DSR routing protocol. This protocol employs the idea of Trust Network Connect (TNC) to protect the MANET. TDSR uses two modules: basic DSR routing protocol and the trust model. TE-DSR has been proposed by N. Bhalaji [7] in which trust enhanced routing is applied to the basic DSR routing protocol. There are mainly three components in the TE-DSR: trust Unit, monitor and the router. Unit trust is responsible for monitoring the trust score and it is further divided into three parts: Initializer, Upgrader and Administrator. The initializer module is used to assign a trust value for new unknown mobile node in the MANET. Upgrader module is responsible for upgrading of trust. The Administer is used to store all the trust information. X. Li et. al. [13] proposed a protocol in which trust is mainly classified into three parts: node historical trust, node current trust and the route trust. Multi- criteria decision making method (like AHP theory) is used for the calculation of historical trust. There are so many trust factors that define the trust such as direct trust, recommendation, an incentive function and active degree. Node current trust is computed by the fuzzy prediction rule. By analyzing all the strength and weakness of previous trust models Xui et. al. [14] proposed trust based dynamic source routing protocol. This protocol is an extension to the FTDSR protocol. For this protocol node historical trust is calculated using the single scalar value i.e. Packet forwarding ratio (ratio of packets forwarded correctly to the total number of packets forwarded from source to destination). By applying fuzzy theory node current trust is computed.

Since malicious nodes can do great destruction to MANET routing, a great number of security solution has been proposed to identify and alleviate those misbehaviors from a variety of perspectives. Most of these previously discussed trust management techniques are based on a well-defined threshold. But it is not possible to set an appropriate threshold a smart adversary can easily adjust this threshold and for all of these methods trust is computed with single scalar parameter. All of these problems can be overcome by STDSR, which uses a support vector machine algorithm in which multidimensional Trust management scheme is applied that evaluate the trustworthiness of DSR nodes, from the multiple perspectives [15].

• IV.    SVM Based Misbehavior Detection

Support vector machine is the collection of supervised learning techniques which are primarily used for classification and regression analysis. It is mainly used for small sample data and it is not complex for data dimension. Therefore SVM algorithms are suitable to the characteristics of the m-dimensional heterogeneous and uneven data sets into single dimensional data sets [16]. Given a training datasets, ( x , y ) where x and y is the input and output space respectively and i=1 to n is the i-th dimension of trustworthiness for nodes. y ∈ {-1, +1}

It finds the hyper planes that have a maximum margin: w.x = b

Where w is a normal vector and b is a threshold.

In order to find the optimal hyper plane, it solves following convex optimization problem,

w2      nmm{ 2 +c ∑1=1ξi}

y_i (w. x_i +b) ≥ 1- ξ _i , ξ _i ≥ 0

Here c is a penalty constant that control the trade off the empirical error ξ and the margin.

The equation (1) can be handled by using following Lagrange equation

Maximize L ( α ) = n     nn

∑ α _i - ∑∑ α _i α _j y _i y _j K( x _j , x _i )       (2)

i = 1              i = 1 j = 1

n

Subjected to ∑ y α =0, and 0 ≤ α ≤ c for all 1 ≤ i = 1

i ≤ n

Where,

K ( x , x ) = Kernel function

α =Lagrange multipliers

To satisfy Kuhn-Tucker (KKT), x must correspond 0

n

≤ α ≤ c and ∑ y α =0 and they are called as support i = 1

vectors.

With the help of equation (2) we can get [1]

n w = ∑αi yi xi i=1

Thus the decision function can be represented as

SVM is more suitable for misbehavior detection than other method. In supervised learning, a

SMS is trained firstly, then this trained machine is used to predict the new data set.

• A. Training of SVM classifier

SVM classifier is trained with SVM train function. The syntax used is

SVMstruct = svmtrain(data, groups, Kernel_function, rbf )

The inputs are,

Data -data is represented as matrix of data points, where row represents one observation and column represents other observation.

Groups -it is the column vector of each corresponding row. Groups must have two types of entries either logical or cell array with two values.

Kernel function - It is used to map the training data set to the kernel space [17].The default kernel function is the dot product. There are several types of kernel function such as linear (meaning dot product), quadratic, polynomial (default value is 3), ‘rbf’ (Gaussian Radial Basis Function kernel with a default scaling factor, sigma, of 1) kernel function etc.

• V.   Proposed Work

This section describes a novel support vector machine based trusted dynamic source routing protocol, which uses ‘Trust Prediction’ concept and is extended from the source routing mechanism Wenjia Li et. al. [10] uses a new concept to categorize the node on their behavior and trust is computed through the Support Vector Machine. In this method trust between nodes is maintained with the help of behavior metrics such as Packet Drop ratio, packet modification ratio and packet misroute ratio. The proposed scheme used instead of packet drop ratio.

• A.    Proposed SVM based Trust Prediction Method

Support vector machine based method is basically used for detection of malicious nodes and to restrict the data transmission through these nodes. To evaluate performance in the following metrics is used by SVM-Packet Delivery Ratio (PDR), Packet Misroute Ratio (PMIR), Packet Modification Ratio (PMR) and Control overhead CO.

• B.    Detection of Malicious Nodes using Behavior Metrics

For each specified input SVM receives a set of input data. In this proposed method. SVM collects all the behavior of each node in the network and then compare it with the threshold value T. All of the nodes are classified either trusted or untrusted with the help of the SVM classifier integrating with MANET.

• C.    Proposed Algorithm

  n

  f (x, α ,b) = { ± } = sign ( ∑ y _i α_i K(x, x_j ) +b)

  i = 1

  
  

• 1)    Gather all the metrics using NS-3 and save as an XML file.

• 2)    Extract DSR routing transmission and control data (in .XML file) using DOM (Dynamic Object Module) and feed as an input in SVM.

Our proposed work has been checked the route reliability into two phases –

• a) Path based on the Behavior of the Node (Relay) b) Cooperation of the node i.e. Determining Selfishness

These two phases have novelty in our proposed mechanism. The key thing about using these in conjunction is to strengthen the trustworthiness of the route and minimizing the false rate of the prediction of the route before delivery of the packet in MANET using DSR protocol.

a) Path based on the Behavior of the Node (Relay)

• 3)    Calculate PDrp, PDR, PMR, PMIR, Delay, CO

• 4)    Compare the calculated parameter

• >    if PDR >= .7 then no-operation

Mark route as “TRUSTED”

• >    else

• •    if (PDR>=0. 5 && PMR <0.65) &&

Mark route as “UNTRUSTED”

> else

• •   if((PDR<0.5&&PMR>=0.6)||PDR<0.5&

Mark route as “UNTRUSTED”

• > else

Mark route as “TRUSTED”

• b) Cooperation of the node i.e. Determining Selfishness

• 5) For i=0 to n ( n= number of nodes present in the MANET topology)

• >    if (pdr [I] <= 0.5 &&Co [i] >0.25) Then node [i] = S ( S = Selfish Node) then:

goto step [4]

• >    else node [i] = T ( T = Trusted Node)

Mark route as “TRUSTED”

• VI.   Experimental Setup

• A.    Metrics for Simulation

In our proposed work, following metric will be used for computing the trust value and then classify the nodes using machine learning approach such as SVM (Support Vector Machine)-

• 1)    PDR (Packet Delivery Ratio)-

• PDR = (No. of pktsTransmitted)

  /(Total no. of Incoming pkts)

• 2)    Packet Drop Ratio (PDrp)

PDrp = (No. of pkt Drop)

/(Total No. of incoming packets)

• 3)    Packet Misroute Rate (PMIR)

The ratio between the numbers of packet misroute to the total no of packet forwarded to the destination.

PMIR =

No. of pkts misrouted Total No. of packets forwarded

• 4)    Packet Modification Ratio (PMR)

It is the proportion of the total number of packet modified to the total number of incoming packets.

PMR =

No. of pkts modified Total No. of incoming packets

• 5)    Path Optimality (PO)

It is the ratio between the total numbers of Hopes in the shortest path to the one of the Hope in the path taken by a data packet.

• 6)    CO (Control Overhead)

It is a measure of the total number of routing packets sends by a node.

The proposed method is modest and provides fast and rapid response to a suspicious or compromised node. Figure 1 shows the flow of our proposed method.

Support Vector --

XML

Z3E

Save

T: Trusted Node, M: Malicious Node

Fig. 1. SVM based Reorganization System

• B.    Simulation Parameters and Result Analysis

0.8 0.7

NS3 simulator version (3.18) is mostly used to evaluate the performance of all the routing protocols in different conditions [18]. In this simulation experiment, total simulation time is taken 600 Sec. and there are total 30 nodes in the network. Traffic is being carried using UDP datagram, and the size of packet is 512 bytes and random waypoint mobility model is used for simulation.

Table 1. Fixed simulation parameters

Parameter	Value
Simulation time	600s
Number of nodes	30
Map size	1000m*1000m
Mobility model	Random way point
Traffic type	UDP
Transmission radius	250 m
Packet size	512 Bytes
Connections	10
Connection rate	4 pkts/s
Pause time	5 Sec

Figure 2 shows the SVM based classification of trusted and untrusted nodes. A node can be well classified with proposed STDSR because it uses SVM based classification and it classified nodes into two categories: trusted and untrusted node.

+■ T

*- UT о Support Vectors

Fig. 2. SVM Based Classification of Nodes

Fig. 3. Graph for Rate of Untrusted node with enhancement of mobility and malicious node

Figure 3 illustrates that the detection ratio of TDSR and TSR increases with node speed. When the interaction among nodes increases gradually, then it is observed that nodes move faster. This leads to a higher detection ratio of malicious nodes. Performance of STDSR is better than TDSR, TSR1 and TSR2 because it uses SVM based classification for detection of malicious nodes.

Table 2. Detection of untrusted nodes versus max. Speed of nodes

Max. Speed in m/Sec	Rate of detection of untrusted node
	TDSR	TSR1	TSR2	STDSR
0	83	86	87	90
5	83.5	90.05	92	91
10	84	91.35	92	92
15	84.5	91	95	93
20	86	92.21	92	94
25	87	92.5	93	95
30	88	93	94	96

Advantage of STDSR over TDSR when node speed is 0 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR       90 - 83

TDSR     ∗ 100 = |  83  | ∗ 100 = 8.4337

Advantage of STDSR over TDSR when nodes Speed is 5 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR        91 - 83.5

TDSR    ∗100=|  83.5  | ∗ 100 = 8.952

Advantage of STDSR over TDSR when nodes Speed is 10 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR       92 - 84

TDSR     ∗ 100 = |  84  | ∗ 100 = 9.52

Advantage of STDSR over TDSR when nodes Speed is 15 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR        93 - 84.5

TDSR    ∗100=|  84.5  | ∗ 100 = 10.05

Advantage of STDSR over TDSR when nodes Speed is 20 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR       94 - 86

TDSR     ∗ 100 = |  86  | ∗ 100 = 9.30

Advantage of STDSR over TDSR when nodes Speed is 25 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR       95 - 87

TDSR     ∗ 100 = |  87  | ∗ 100 = 9.19

Advantage of STDSR over TDSR when nodes Speed is 30 m/Sec

Advantage of STDSR over TDSR =

STDSR - TDSR       96 - 88

TDSR    ∗ 100 = |  88  | ∗ 100 = 9.09

In the similar way advantage of STDSR over TDS1 and TSR2 is calculated and the results shown in the table 3.

Table 3. Overall Performance Gain of STDSR with mobility

Max. Speed in m/Sec	Overall Performance Gain of STDSR
	STDSR Over TDSR	STDSR over TSR1	STDSR over TSR2
0	8.4337	4.651	3.44
5	8.982	1.054	1.086
10	9.52	0.711	0
15	10.05	2.197	2.105
20	9.30	1.941	2.173
25	9.19	2.702	2.150
30	9.09	3.225	2.127

Table 3 shows the overall % gain of support vector machine based trusted dynamic source routing protocol (STDSR) and it is analyzed that STDSR is more suitable for detection of malicious node when compared with the TDSR and TSR protocol.

Figure 4 also shows that the detection ratio of STDSR, TDSR and TSR with varying number of malicious nodes. And result shows that the detection rate of malicious nodes decreasing with the increasing number of malicious nodes. It shows that at high mobility STDSR works well then the TDSR and TSR because it uses the SVM based classification of nodes.

TDSR

TSR1

TSR2

STDSR

Fig. 4. Graph for Rate of Untrusted node with enhancement of malicious node

Table 4. Detection of untrusted nodes versus no. of malicious nodes

No. of malicious nodes	Rate of detection of untrusted node
	TDSR	TSR1	TSR2	STDSR
0	97	99	99	99
2	92	96	96	97
4	86	91	92	93
6	84	91	92	92
8	80	84	86	87

Advantage of STDSR over TDSR when no. of malicious node= 0

Advantage of STDSR over TDSR =

STDSR - TDSR       99 - 97

TDSR    ∗100=|  97  | ∗ 100 = 2.062

Advantage of STDSR over TDSR when no. of malicious node= 2

Advantage of STDSR over TDSR =

STDSR - TDSR       97 - 92

TDSR    ∗100=|  92  | ∗ 100 = 5.438

Advantage of STDSR over TDSR when no. of malicious nodes= 4

Advantage of STDSR over TDSR =

STDSR - TDSR       93 - 86

TDSR    ∗100=|  86  |∗100=8.14

Advantage of STDSR over TDSR when no. of malicious nodes= 6

Advantage of STDSR over TDSR =

STDSR - TDSR       92 - 84

TDSR    ∗100=|  84  | ∗ 100 = 9.524

Advantage of STDSR over TDSR when no. of malicious nodes= 4

Advantage of STDSR over TDSR =

STDSR - TDSR       87 - 80

TDSR     ∗ 100 = |  80  | ∗ 100 = 8.75

In the similar way advantage of STDSR over TDS1 and TSR2 is calculated and the results shown in the table 5.

Table 5. Overall Performance Gain of STDSR with no. of malicious nodes

No. of Malicious Nodes	Overall Performance Gain of STDSR
	STDSR Over TDSR	STDSR over TSR1	STDSR over TSR2
0	2.062	0	0
2	5.438	1.042	1.042
4	8.14	2.198	1.087
6	9.524	1.098	0
8	8.75	3.571	1.163

Table 5 shows the overall % gain of support vector machine based trusted dynamic source routing protocol (STDSR) and it is analyzed that STDSR is more relevant for detection of malicious node when related with the TDSR and TSR protocol.

• VII.    Conclusion

This paper introduced support vector machine based DSR protocol for safeguarding routing in mobile ad-hoc network and it is examining that performance of STDSR increases in some performance indicator such as detection ratio with the variation of mobility and number of malicious nodes, and in future this proposed protocol can be used to show that the performance of STDSR increases in some other parameter such as a packet delivery ratio, average end to end delay, and throughput.

• VIII.   Future Work