Classification of Selfish and Regular Nodes Based on Reputation Values in MANET Using Adaptive Decision Boundary ()
1. Introduction
Ad hoc wireless networks utilize multi-hop radio relaying and operate without support of any fixed infrastructure. This makes the routing complex compared to other networks. Nodes must communicate to each other regarding information about other nodes. A node can transmit and receive data, as well as act as a router for routing packets for other nodes. A node forwards packet in an ad hoc network using the routing algorithms presented in [1-7]. Attacks are a challenge for the ad hoc routing protocols. Some of the attacks are modification, fabrication, wormhole attack (tunneling), blackhole attack, denial of service attack, invisible node attack, sybil attack, rushing attack and non-cooperation. To short out these attacks some secured routing protocols are developed these are Ariadne [1], ARAN (Authenticated Routing for Ad hoc Networks) [2,3], SEAD (Secure Efficient Ad hoc Distance vector routing) [4], SRP (Secure Routing Protocol)
[5] etc. Most of the attacks based on manipulations of routing data can be detected by the use of a secure routing protocol like Ariadne, ARAN, and others [6,7]. However these secure routing protocols fail when nodes drop packets of other nodes, as they concentrate only on the detection or modifications of routing data but noncooperation (selfishness) is still in its natal stage. To deal with selfishness we have so many solutions in reputation based model such as Watchdog and Pathrater [8], CONFIDANT [9,10], CORE [11], OCEAN [12] and others [13-18]. These solutions [8-18] reduce selfishness but a cooperative network is still affected because these models have a stricter isolation policy. In a cooperative network if nodes are isolated from routing and forwarding using lesser reputation value then it will damage the entire network or cause network failure. In this paper we have proposed a mathematical model using an adaptive decision boundary which classifies nodes in two classes: (selfish and regular nodes) as well as it assigns the grade to individual nodes. The grade is computed by counting how much passes the algorithm takes to classify a node and it is used to define the punishment strategy as well as enhance the reputation definition of traditional reputation based mechanisms [8-18]. This paper is organized as follows. Section 2 describers the background and related work. Section 3 presents the mathematical model for the classification of nodes in MANET. Section 4 gives the experimental analysis in which we have used indigenous tool written in “C” language for classification of node, grade assignment and punishment definition. We verified it with different experimentations. Section 5 concludes the paper.
2. Background and Related Work
Mobile wireless network, capable of autonomous operation operates without base station or infrastructure. In this network nodes cooperate with each other to provide connectivity and operate without centralized administration. But when nodes drop packets of others due to honest or malicious causes they are called selfish nodes [19]. A node is called selfish if it drops packets of others due to either honest causes such as collisions, channel errors, or buffer overflows or maliciously such as to save its energy or bandwidth, blackhole or wormhole attack, network congestion. A selfish Node degrades efficiency of packet transfer and accelerates the packet delivery time and packet loss rate and finally creates Network Partitioning. To enforce cooperation and to minimize battery usage Md. Amir Khusru AKhtar and G. Sahoo [20] proposed a novel methodology for securing adhoc network using friendly group model in which they used two NIC cards to partition a MANET into many friendly groups/ subnets. This model enforces cooperation because it minimizes battery usage which is the genuine cause of selfishness but this model is not suitable for all applications.
For the intrusion detection in MANET a classification algorithms was proposed [21], it is an innovative approach but not validated with real world data. We have other methods [22,23] for the detection of selfish node but these proposed algorithms consumes more energy. Paper [24] defines a secure routing protocol with node selfishness resistance in MANETs but this protocol still consumes more energy.
We have lots of methods to detect selfish nodes that are categorized into incentive-based methods and reputation-based methods. The first mechanism discourages a node to become selfish by giving virtual money/credits when a node forward packets of others. These credits are required when a node want to send or receive its own packets. Another method [17] proposed by Buttayan and Hubaux uses virtual currency, called nuglets to detect a selfish node. In this method a nuglet counter is incremented monotonically when it forwards a packet for others. When a node wishes to send its own packet, then enough credits are required as the system checks for a certain threshold value otherwise it is not allowed to send packets. The limitation of this method is that it requires tamper proof hardware to maintain the nuglet.
On the other hand, the reputation-based methods detect a selfish node and take appropriate action by means of reputation system that detect and defines the rate a selfish node. In these mechanisms reputation is defined on the basis of participation seen by others [16]. The good reputation indicates honest participation in the network activity otherwise it is marked as selfish.
Since we are classifying a MANET on the basis of reputation values that is why we are focusing on “Reputation Based Mechanisms”. A survey of trust and reputation management systems in wireless communications [25] shows the current status of reputation based systems and its limitation in terms of energy usage and noncooperation.
The first method on detection of routing misbehavior was proposed by Marti et al. called the Watchdog and Pathrater [8]. It is to be used over the DSR [6] routing protocol to alleviate selfish and malicious routing misbehavior in MANET. Watchdog module is responsible for neighbor monitoring and identifying malicious and selfish nodes whereas Pathrater module evaluates the overall reputation of nodes and defines route by excluding the selfish or misbehaving nodes. In this mechanism a selfish node is rewarded instead of any punishment for the misbehavior.
The CONFIDANT protocol proposed by Buchegger et al. [9,10], in which the first module called Monitor that is responsible for observing and recording the misbehavior of neighboring nodes. The second module the reputation system is responsible for calculating the reputation of nodes on the strength of direct observation and indirect observation. The third module trust manager is collects warning messages from friends, and finally the fourth module the path manager defines the path for routing by excluding selfish nodes. In this protocol, each node monitors its neighborhood behavior and observed misbehavior is reported to the reputation system. If the misbehavior is not tolerable then it is reported to the path manager, and then the path manager excludes the nodes from the routing path and calculates new paths. This method has weaknesses due to inconsistent evaluation problem, for the reason that every node has different evaluations for the same node and has difficulty to identify correct selfish node. Another limitation is in terms of more battery power consumption for a node located in the center of network in comparison to situated at the periphery of the network.
The CORE protocol [11] proposed by Michiardi et al., uses three reputations (subjective, indirect and functional). This mechanism uses reputation table to maintain the reputation value for each node and the watchdog mechanism to observe that a requisite function is performed by the requested node or not. The reputation is defined on direct observation and on the basis of information provided by others nodes. The reputation value will facilitate a node to decide the selfishness of a requesting node and finally guide whether to serve or to decline the request.
A lot of research work [12-18] shows the usage of reputation value in the detection and exclusion of selfish node from a mobile adhoc network. All these methods have limitation due to its stricter punishment strategy because they isolate the nodes from routing activity on the basis of lower reputation value and thus reduce the overall strength of nodes in the network. Since a cooperative network is based on the nodes strength and thus the network does not perform better.
3. Proposed Work
3.1. Adaptive Decision Boundary
In this paper, we are showing a classification model based on Adaptive Decision Boundary [26] that classifies a network into selfish and regular nodes as well as it assigns grade to individual nodes. The grade is computed by counting how many passes are required to classify a node and it is used to define the punishment strategy as well as enhances the reputation definition of traditional reputation based mechanisms [8-18]. The punishment strategy is defined in section 3.5. This model works fine with the existing routing protocols and solutions. We have assumed a leader node in our work which is responsible for defining an adaptive decision boundary explained in section 4.1.
In this work an adhoc network is classified into two classes selfish and regular. The classification of nodes reputation values modeled mathematically using Adaptive Decision Boundary [26]. We have defined a linear decision boundary to classify nodes reputation values into two classes in which a network has M features. Feature values are taken from reputation values and the discriminant function is of the form
(1)
The adaptive decision boundary D = 0 is the equation of the decision boundary and lying between the two classes (selfish and regular). The weights are w0, w1, …, wM are selected for better analysis of the network. Through this we classify a MANET with reputation values called feature values obtained from literature [9-16, 19,25]. A network with M feature values X = (X1, X2, …, XM) is classified in to two classes: regular class with reputation value 1 (if D ≥ 0) and selfish class-1 (if D < 0). Figure 1 shows the two classes (selfish and regular denoted as S and R respectively) which are separated by a straight line.
3.2. Problem Definition and Proposed Solution
In this paper we are classifying the selfish and regular nodes on the basis of reputation values in a MANET using adaptive decision boundary. The existing methods [8-18] have limitation due to its stricter punishment strategy because they isolate nodes from network participation having lesser reputation value and thus reduce the total strength of nodes in a network. The lesser number of nodes reduces network performance, degrades efficiency of packet transfer, accelerates the packet delivery time, enhances packet loss rate and creates Network Partitioning. That is why we have proposed this classification technique. The proposed solution to tackle this problem is described using the following steps
Step 1: Initially we have obtained the reputation values of all nodes in a network using existing reputation system as defined in [8-12].
Steps 2: After that true class or desired value of a node is defined as defined in section 3.3.
Steps 3: Then nodes are classified into selfish and regular classes based on reputation values by using the algorithm 3.4. Further, the number of passes is used to define grade.
Step 4: Finally punishment criteria are defined on the basis of grade. For example we have included medium grade (GMED) selfish nodes in network participation with proper warning messages and low (GLOW) grade nodes are excluded form network participation. The punishment criterion is defined in section 3.5.
3.3. Defining True Class or Desired Value
In this model we are assuming the true class or desired value (d) by +1 and by −1. A +1 value indicates a regu-
Figure 1. Nodes reputation values are linearly separable.
lar class and −1 denotes a selfish class. The true class of a node is defined on the basis of minimum number of passes to classify in true classes +1 or −1 on the basis of nodes reputation value shown in Figure 2.
For example, on the basis of reputation value a node of a MANET takes 20 passes to classify in selfish class and 30 passes for regular class. The selfish class takes minimum number of passes to classify, so in this example the node is classified in selfish class and d = −1.
The classification, true class definition and grade calculation is performed by executing adaptive_decision_ boundary() function. This function counts how many passes are required to match the value of d with Discriminant “D” and it finds the true class on the basis of minimum number of passes. Then the grade is defined using Table 1 and it is used to define the punishment criteria explained in section 3.5.
3.4. “C” Language Function for the Classification of Nodes in a MANET Using Single Numeric Feature
In this section we are presenting the adaptive decision boundary algorithm to classify selfish and regular nodes based on reputation values in MANET.
Figure 2. Flowchart showing nodes true class calculation.
Table 1. Grade assignment and punishment crieteria.
/* Classification using Adaptive decision boundary */
adaptive_decision_boundary() {
do{
for(i=1;i<=2;i++){
if(i%2==1)
{++s; j=0;}
else
{++r; j=1;}
d=a[j][2];
x=a[j][1];
D=w0+w1*x;
if(D>=0) D=1;
else D=-1;
if(D!=d){
++r;
w0=w0+c*d*k;
w1=w1+c*d*x;}
if(r>s)
{tc=-1; pass=s;}
else
{ tc=1; pass=r;}
}
}while(D!=d);
if(pass <= 10)
strcpy(grade,"High");
else if(pass <= 30)
strcpy(grade,"Medium");
else if(pass > 30)
strcpy(grade,"Low"); }
3.5. Grade Calculation and Punishment Criteria
Grade is calculated by counting how many passes the algorithm takes to classify. Table 1 shows the number of passes, grade of a node and punishment criteria.
whereGHIGH: High grade GMED: Medium grade GLOW: Low grade
4. Experimental Analysis
4.1. Experimental Assumption
The experimental analysis is based on section 3. To find an adaptive decision boundary to classify nodes of a MANET reputation values are taken into consideration. We have taken a network of sixteen nodes with one leader node as given in Figure 3.
The leader node is an intelligent node of the adhoc network, which has good knowledge of the network and having high computation capability to process and maintain the history of the transaction and responsible for calculation of reputation value in the network. A leader node could be a captain’s laptop in a battle zone. The leader node calculates the adaptive decision boundary to classify a network from the gathered reputation values [8-18] of nodes in the network and then assign grades. On that basis of grade punishment criterion is defined as given in Table 1.
The leader node maintains the reputation table as defined in Table 2. We have taken node identification number (ID), x denotes one dimensional feature or reputation value and d is the true class or desired value for a node obtained using the code defined in section 3.4.
4.2. Result and Discussion
We have classified nodes into two classes selfish and re-
Figure 3. A MANET of sixteen nodes with a leader node.
gular using the solution defined in section 3.2 into two classes using the following parameters.
d: true class or desired value defined in section 3.3.
D: discriminant function defined in section 3.1.
w0 and w1: small random values used to speedup the classification.
c: a positive constant that controls the step size for reputation adjustment needed for classification.
k: a positive constant denoting average absolute reputation value in the problem required to minimize the number of passes.
Choosing the correct c and k values will minimize number of passes to classify as defined in [26].
Figure 4 shows the output generated using code given in section 3.4 by processing Table 2. The constant c and k both chosen to be 1. Initially the weights for w0 and w1 are initialized with 0. The output shows the classification of first two nodes with attributes No_of_passes, I denote node number, x is the reputation value, d the true class, new w0 and w1 the small random values and the discriminant D. We have also shown how many passes are required to classify a node into regular or selfish classes and the equivalent grade. Further, grade is used to define the punishment criteria as given in Table 1.