Mobile Ad Hoc Network

Introduction

What is Mobile Ad Hoc Network?

With rapid development of wireless technology, the Mobile Ad Hoc Network (MANET) has emerged as a new type of wireless network. MANET is a collection of wireless mobile nodes (e.g. laptops) that dynamically function as a network without the use of any existing infrastructure and centralized administration. It is an autonomous system where each node operates not only as an end system but also as a router to forward packets for other nodes. Since the nodes in MANET move around, the wireless links break and re-establish frequently. Furthermore, most of mobile nodes are resource limited in computing capability and battery power and therefore traditional computing content routing protocols are not suitable for MANET. Several ad hoc routing protocols have been proposed for each node acting as router and maintaining routing information. There are many other applications of MANET. For examples, MANET can be used to provide emergency Services when the network is impaired due to the damaging of existing infrastructure [8]. Computer scientists have predicted a world of ubiquitous computing in which computers will be all around us, constantly performing mundane tasks to make our lives a little easier. These ubiquitous computers connect in mobile ad hoc mode and change the environment or react to the change of the environment where they are suited. MANET is also found useful in the so-called sensor dust network to coordinate the activities and reports of a large collection of tiny sensor devices which could offer detailed information about terrain or environmental dangerous conditions.

Problem Statement and Motivation

Most current ad hoc routing protocols assume that the wireless network is benign and every node in the network strictly follows the routing behavior and is willing to forward packets for other nodes. Most of these protocols cope well with the dynamically changing topology. However, they do not address the problems when misbehavior nodes present in the network.A commonly observed misbehavior is packet dropping. In a practical MANET, most devices have very limited computing and battery power while packet forwarding consumes a lot of such resources. Thus some of the mobile devices would not like to forward the packets for the benefit of others and they drop packets not destined to them. On the other hand, they still make use of other nodes to forward packets that they originate. These misbehaved nodes are very difficult to identify because we cannot tell that whether the packets are dropped intentionally by the misbehaved nodes or dropped due to the node having moved out of transmission range or other link error. Packet drop significantly decreases the network performance.Traditional security mechanisms are generally not suitable for MANET because:

1. The network lacks central infrastructure to apply traditional security mechanism such as access control, authentication and trusted third party.
2. Limited bandwidth, battery lifetime, and computation power prohibits the deployment of complex routing protocols or encryption algorithms. New security models or mechanisms suitable for MANET must be found.
3. Network topologies and memberships are constantly changing. Thus new intrusion detection system and entity recognition mechanisms that are suitable for mobile ad hoc networks must be designed to avoid or mitigate the behavior to the networks.

Trust management systems have been recently introduced as a security mechanism in MANET. In a trust management system, a communicating entity collects evidence regarding competence, honesty or security of other network participants with the purpose of making assessment or decisions regarding their trust relationships. Here trust

Objective and Sub-tasks

means the confidence of an entity on another entity based on the expectation that the other entity will perform a particular action important to the trustor, irrespective of the ability to monitor or control that other entity . For example, a trust-based routing protocol can collect the evidence of nodes misbehaving, form trust values of the nodes and select safest routes based on the trust metrics.Reputations systems are often seen as a derivation of trust management system. In the reputation system, an entity forms its trust on another entity based not only on the selfobserved evidence but also on the second hand information from third parties. One of the influential reputation systems is the DSR protocol. In the trust management system, reputation system and other trust-based systems, route selection is based on the sending node's prior experience with other nodes in the network. Its opinions about how other entities are honest are constantly changing. Thus, we call the trust management systems and their derivations as dynamic feedback mechanisms. The dynamic feedback mechanisms are usually applied on the current ad hoc routing protocols to rate the trust about other nodes in the network and make routing decisions based on the trust matrix, which is formed according to the evidence collected from previous interactions. By incorporating the dynamic feedback mechanism in the routing protocol, misbehaved nodes are identified and avoided to forward packets. In this way,misbehavior can be mitigated.

Objective and Sub-tasks

The primary objective of this thesis is to Investigate the state of the art of dynamic feedback mechanisms and protocols analyze, implement and evaluate DSR protocols to see how it improves the network performance and what are the side effects of introducing the mechanism to the mobile ad hoc network. Following tasks must be done to achieve the primary objective.

1. Study the preliminary knowledge that is required to carry out the main tasks. For example, to understand DSR protocol one must have some knowledge of Bayesian analysis; to do performance analysis one must learn the methodologies of conducting performance analysis and processing simulation data.
2. Investigate security issues of mobile ad hoc network and current dynamic feedback mechanisms or protocols that are used to solve or mitigate the issues.
3. Investigate and learn how to use the network simulation tool. There are several popular network simulation tools available and we need to choose the one that best suits our needs. The selected network simulator should be studied so that we can use it as platform to implement protocol and conduct simulations.
4. Analyze and implement the DSR protocol based on Dynamic Source Routing protocol (DSR); evaluate the network performance.

Structure of the Report

Since we have almost gone through the chapter one, we only briefly present the content of the subsequent chapters in this section.

1. Preliminary Information
2. State of the Art
3. Analysis
4. Design
5. Implementation and Tests Performance
6. Analysis
7. Conclusion and Future Work

Preliminary information

we have introduced the MANET. This chapter presents other preliminary information and concepts that will be used in other parts of the thesis. Firstly four general modes of routing operations are introduced and compared. The DSR protocol, which is used as underlying routing protocol in the thesis, is explained in detail. Secondly Bayesian estimation and Beta function are explained to pave the way for the analysis of the reputation model of DSR in the chapter 4. Thirdly some techniques regarding simulation and performance analysis are presented. Finally, several popular network simulation tools are discussed and compared.

Mobile Ad Hoc Network Routing Protocols

Nowadays there are various routing protocols proposed for the MANET. The most popular ones are DSDV (Destination-Sequenced Distance Vector), TORA (Temporally- Ordered Routing Algorithm), DSR (Dynamic Source Routing) and AODV (Ad-hoc On Demand Distance Vector). These routing protocols can be categorized in different routing operation modes.

Mode of Routing Operations

These two modes concern whether or not nodes in an ad hoc network should keep track of routes to all possible destinations, or instead keep track of only those destinations of immediate interest Proactive protocols store route information even before it is needed. This kind of protocols has advantage that communications with arbitrary destination experience minimal delay. However it also suffers from the disadvantage that additional control traffic is needed to continually update stale route information. This could significantly increase routing overhead especially for the MANET where the links are often broken. Reactive protocols, on the contrary, acquire routing information only when it is actually needed. However, the latency of the communication increases tremendously especially when a node communicates to another at the first time.

Source routing vs. Hop-by-hop routing

These two modes concern whether the source node decides the route for a packet to be forwarded to the destination or the intermediate nodes are allowed to decide the next hop until the packet arrives at the destination. In the source routing protocols, the source node decides the route and puts the route information in the packet header. All the intermediate nodes forward the packet along the route faithfully. This kind of protocols has advantage that the intermediate nodes are not required to maintain the routing information. But it suffers from the disadvantage that the packet size grows because of source routing information carried in each packet. In the hop-by-hop routing protocols, it is sufficient for the source to know only how to get to the "next hop" and intermediate nodes find their own next-hops until the destination. In contrast to source routing protocols, hop-by-hop routing protocols do not increase packet size but they requires all the intermediate nodes to maintain routing information.

Table 2-1 Categories of routing protocols

has compared the performance of these four routing protocols . The results show that DSR has best throughput performance (above 95%) at all mobility rates and movement speeds. Thus we will use DSR as basic routing protocol in this thesis.

The Dynamic Source Routing Protocol (DSR)

John et al. proposed the dynamic source routing protocol (DSR) [1] which is a routing protocol for use in multi-hop wireless ad hoc networks of mobile nodes. DSR is an ondemand protocol, in which route are only discovered when data need to be transmitted to a node where no route has yet been discovered. The advantage of this on-demand routing protocol is that there are not any periodic routing advertisement and reducing the routing overhead. DSR is also a source routing protocol, allowing multiple routes to any destination and allows each sender to select and control the routes used in routing the packets. DSR is composed of the two main mechanisms: "Route Discovery" and "Route Maintenance" which are explained below.

Route Discovery

Route Discovery aims at finding routes from a source node to destination. Figure 2-1 illustrates the procedure of Route Discovery. When a source node S wants to send a data packet to some destination node D, it first searches its route cache to find whether there is a route to D. If there is no route to D, then S will initiate a Route Discovery and send out Route Request message which is propagated to all the nodes within its transmission range. At the mean time, it saves the data packet in its send buffer. The Route Request message contains the addresses of source node and destination node, a unique route request identifier and a route record which records all the intermediate nodes that this route request packet has traveled through. S appends itself to the beginning of the route record when it initiates the message. When a node receives the Route Request message, it compares the destination address in the message with its own address to judge whether itself is the destination node. If it is not, it will append its own address in the route record and propagate the message to other nodes. If the node is the destination node, it will send a Route Reply message to the source node and the message contains the source route record which is accumulated when the Route Request message is forwarded along its way to the destination. When the destination sends the Route Reply, if it uses MAC protocols such as IEEE 802.11 that require a bidirectional link, it just reverse the source route record and use it as route to send Route Reply to the source node. Otherwise it should find the route by searching its route cache or sending out a Route Request which piggybacks the Route Reply for the source node. When the source node receives the Route Reply message, it puts the returned route into its route cache. From then on all the packets destined to the same destination will use this route until it is broken.

Route Maintenance

Since the ad hoc network is dynamic and the topology of the network changes frequently, the existing routes maintained by nodes in their route cache are often broken. After forwarding a packet, a node must attempt to confirm the reachability of the next-hop node. If the node does not receive any confirmation from the next hop during a certain period of time, it will retransmit the packet. If after a maximum number of retransmission it still does not receive any confirmation, it will think the link to the next hop is broken and will send a Route Error message to the source node. DSR proposes three acknowledge mechanisms to confirm that data can flow over the link from that node to the next hop:

• Link-layer acknowledgement which is provided by MAC layer protocol such as IEEE 802.11.
• Passive acknowledgement in which a node hears the next-hop node forwarding the packet and thus confirms the reachability of the link.
• Network-layer acknowledgement in which a node sends an explicit acknowledgement request to its next-hop node.

Passive Acknowledgement

Passive Acknowledgement (PACK) is important in DSR protocol because it is used to detect whether the next hop forwards the packet or drops it. We explain it in detail in this section. Passive acknowledgement is used with the assumption that:

• Network links operates bi- directionally.
• The network interface is in the "promiscuous mode". When a node taps a new packet in "promiscuous mode" after it originates or forwards a packet, it consider it as an acknowledgement of the first packet if both of following check success.
• The Source Address, Destination Address, Protocol, Identification, and Fragment Offset fields in the IP header of the two packets MUST match.
• If either packet contains a DSR Source Route header, both packets MUST contain one, and the value in the Segments Left field in the DSR Source Route header of the new packet MUST be less than that in the first packet.
• If no matched packet is found during PACK timeout, the node will consider the link between the next hop and itself is broken and will send Route Error message to the source node.

Additional features

DSR has additional features such as replying to route requests using cached routes, caching overheard routing information, packet salvaging and flow state extension and etc. We will introduce them in section 4.1 and discuss how they will impact the performance of network, how they will interact with DSR and whether they will be enabled in our simulation.

Performance Analysis Techniques

This section introduces the performance analysis techniques and methodologies that will be used in the performance evaluation.

Factors and Primary Factors

There are many parameters that will influence the simulation results and need to be carefully chosen in the simulations. Some parameters are chosen based on experience values or the conditions of the network we want to simulate. Others need to be tuned to optimize the network performance. We distinguish the two kinds of parameters as follows:

• Factors are the variables that affect the simulation result and have several alternatives. Normally they are decided based on experience.
• Primary factors are the factors whose effects need to be quantified. This kind of factors usually needs to be adjusted through simulation.

Data Measurement

The key step of the network performance analysis is to interpret the simulation result and summarize the characteristic of the network. To avoid the inaccurate simulation results due to an extreme scenario, we usually run simulations on several different scenarios. The data set of these simulations are called sample. A single number must be presented to give the key characteristic of the sample and this single number is called an average of the data. There are three alternatives to summarize a sample Mean is obtained by taking the sum of all observations and dividing this sum by the number of observations in the sample. Median is obtained by sorting the observations in an increasing order and taking the observation that is in the middle of series. If the number of the observations is even, the mean of the middle two values is used as a median. Mode is obtained by plotting a histogram and specifying the midpoint of the bucket where the histogram peaks.

Confidence Interval for the Mean

In our performance evaluation, the main objective is to compare the simulation results of DSR and Standard DSR to see whether there is any performance improvement. However, most simulation results are random in some degree due to the particularity of the node movement scenarios and we cannot tell whether the two systems are different. One way to minimize the random effect is to repeat the simulations with different scenarios as many times as possible and get a large sample space. Unfortunately, due to the time limitation we cannot conduct many simulations. points out that using confidence interval we can tell whether the two systems are different with smaller sample space. The confidence interval for the mean can be calculated using If the confidence intervals of the simulation results of the two systems have no overlap, then we can claim the two systems are different and one system is superior or inferior to the other. GloMoSim's source and binary code can be downloaded only by academic institutions for research purposes. Commercial users must use QualNet, the commercial version of GloMoSim.

OPNET Modeler

OPNET Modeler is commercial network simulation environment for network modeling and simulation. It allows the users to design and study communication networks, devices, protocols, and applications with flexibility and scalability [30]. It simulates the network graphically and its graphical editors mirror the structure of actual networks and network components. The users can design the network model visually.The modeler uses object-oriented modeling approach. The nodes and protocols are modeled as classes with inheritance and specialization. The development language is C.

Comparison

When choosing a network simulator, we normally consider the accuracy of the simulator. Unfortunately there is no conclusion on which of the above three simulator is the most accurate one. David Cavin et al. has conducted experiments to compare the accuracy of the simulators and it finds out that the results are barely comparable [31]. Furthermore, it warns that no standalone simulations can fit all the needs of the wireless developers. It is more realistic to consider a hybrid approach in which only the lowest layers (MAC and physical layers) and the mobility model are simulated and all the upper layers (from transport to application layers) are executed on a dedicated hosts (e.g. cluster of machines). Although there is no definite conclusion about the accuracy of the three network simulators, we have to choose one of them as our simulation environment. We compare the simulators using some metrics and the results are summarized After comparing the three simulators, we decide to choose ns2 as network simulator in our thesis because

• Ns2 is open source free software. It can be easily downloaded and installed.
• The author of the thesis has used ns2 in another network related course and gotten familiar with the simulation. Ns2 uses TCL and C++ as development languages for which the author has some programming experience.
• The author of the DSR protocol has conducted simulation on GloMoSim and gotten performance results. We want to do the simulation on a different simulation to form comparison.

State of the Art

In this chapter we will introduce the start of the art security solutions in MANET with emphasis on dynamic feedback mechanisms. Firstly, we will present the general security issues/requirements of MANET to pave the way for the future investigation. Then we will discuss the state of the art security mechanisms for MANET such as payment system,trust management system, reputation system, etc. Finally, we will summarize all the security solutions we discussed in this chapter.

Security Issues in Mobile Ad Hoc Network

Due to lack of central infrastructural and wireless links susceptible to attacks, security in ad hoc network has inherent weakness. In section 1.2 we have discussed the reasons why mobile ad hoc network imposes security challenges that cannot be solved by traditional security mechanisms. In this section, we present the general security properties required by ad hoc network. Following are general security properties regarding ad hoc network Confidentiality: The confdiantiality property is to protect certain information from unauthorized disclosure. The information includes not only the application data that send over the routing protocol, but also the routing information itself as well as network topology and geographical location. Integrity: The integrity ensures that the transmitted message and other system asset are modified only by authorized parties. In the routing level, it requires all nodes in the network following correct routing procedure. The main challenge of ensuring integrity is that without central infrastructure and powerful computing capabilities, it is difficult to apply existing cryptography and key management systems. Availability: The availability property requires that the services or devices are exempt from denial of service, which is normally done by interruption, network or server overload. Typical examples or denial of service attack are radio jamming, in which a misbehaved node transmit radio to interference other nodes' communications, and battery exhaustion, in which a misbehaved node interact with a node for no other purpose than to consume its battery energy. Authentication: The authentication property requires that the communication entity's identification is recognized and proved before communication starts. Access control: This property requires restricting resources, services or data to special identities according to their access rights or group membership. Non-repudiation: This property ensures that when data are sent from sender to receiver, the sender cannot deny that he has sent the data and the receiver cannot deny that he has received the data. Mobile nodes may conduct different misbehavior for different purposes. Po-Wah Yau classifies the misbehaved nodes into following categories. Failed nodes are simply those unable to perform an operation; this could be because power failure and environmental events. Badly failed nodes exhibit features of failed nodes but they can also send false routing messages which are a threat to the integrity of the network. Selfish nodes are typified by their unwillingness to cooperate as the protocol requires whenever there is a personal cost involved. Packet dropping is the main attack by selfish nodes. Malicious nodes aim to deliberately disrupt the correct operation of the routing protocol, denying network service if possible. These four types of misbehaved nodes actually can be categorized in two aspects: whether their misbehaviors are intentional or unintentional, and the severity of the results.

Payment Systems

Payment systems provide economic incentives for the cooperation in MANET. They consider that each node in MANET is its own authority and tries to maximize the benefits it gets from the network. Thus each node tends to be selfish, dropping packets not destined to them but make use of other nodes to forward their own packets. The purpose of payment systems is to encourage the cooperation within the MANET by economic incentives. There are several variations of payment systems proposed.

Nuglets

Nuglets is a virtual currency mechanism for charging (rewarding) server usage (provision). Nodes that use a service must pay for it (in nuglets) to nodes that provide the service. A typical service is packet forwarding which is provided by intermediate nodes to the source and the destination of the packet. Therefore either the source or the destination should pay for it. There are two models for charging for the packet forwarding service: the Packet Purse Model (PPM) and the Packet Trade Model (PTM). In the Packet Purse Model, the sender pays for the packet. It loads the packet with a number of nuglets when sending the packet. Each intermediate forwarding node acquires some nuglets from the packet that covers its forwarding costs. If a packet does not have enough nuglets to be forwarded, then it is discarded. If there are nuglets left in the packet once it reaches destination, the nuglets are lost. In the Packet Trade Model, the destination pays for the packet. Each intermediate node "buys" the packet from previous one for some nuglets and "sells" it to the next one for more nuglets until the destination "buys" it. Either of the two models has advantages and disadvantages. While the Packet Purse Model deters nodes from sending useless data and avoids the network overloading, the Packet Trade Model can lead to an overload of the network and the destination receives packets it does not want. On the other hand, in the Packet Purse Model it is difficult to estimate the number of nuglets that are required to reach a given destination. But thePacket Purse Model does not need to consider this problem. To take advantages of the two models and avoid the disadvantages, a hybrid model is suggested. In this model, the sender loads the packet with some nuglets before sending it.The packet is handled according to the Packet Purse Model until it runs out of nuglets. Then it is handled according to the Packet Trade Model until the destination buys it.

Counter

To address the problems encountered by the nuglets approach such as difficulty in estimating pre-load nuglets and possible network overload, another payment approach based on credit counter is suggested. In this approach, the current state of each node is described by two variables b and c, where b is the remaining battery power and cstands for the value of its nuglet counter. More precisely, b is the number of packets that the node can send using its remaining energy and c is the number of packets a node canoriginate. A node can originate a number of packets N only when the condition c=N holds. When a node forwards a packet, nuglet counter c is increased by one and b is reduced by one. Thus in order to originate packets, each node must earn credits by forwarding packets. The counter solution requires tamper resistant hardware security module.

Spirit

S. Zhong et al. proposed Sprite [19], a credit-based system for MANET. As opposed to Nuglets or Counter they do not require tamper-proof hardware to prevent the fabrication of payment units. Instead, they introduce a central Credit Clearance Service (CCS). The basic scheme of the system is as follows. When a node receives a message the node keeps a receipt of the message and reports to the CCS when the node has a fast connection to Credit Clearance Service (CCS). The CCS then determines the charge and credits to each node involved in the transmission of a message, depending on the reported receipts of a message. In this scheme, the sender charges money. A node that has forwarded a message is compensated, but the credit that a node receives depends on whether or not its forwarding action is successful. Forwarding is considered successful if and only if the next node on the path reports a valid receipt to the CCS.

Discussion on the Payment Systems

The payment systems we describe in above sections either assumes a tamper resistant hardware module is available to ensure that the behavior of the node is not modified or requires a central authority server to determine the charge and credit to each node involved in the transmission of a message. Tamper resistant hardware may not be appropriate for most mobile devices because it demands advanced hardware solution and increases the cost of the devices. Lacking of central authority server is right the inherent property of MANET that causes security challenges so it is also not appropriate. Furthermore, all the approaches described above suffer from locality problems [20] that nodes in different locations of the network will have different chances for earning virtualcurrency, which may not be fair for all nodes. Usually nodes at the periphery of the network will have less chance to be rewarded.

Reputation System

Reputation systems have emerged as a way to reduce the risk entailed in interactions among total strangers in electronic marketplace. Centralized reputation systems have been adopted by many on-line electronic auctions such as eBay to collect and store reputation ratings from feedback providers in a centralized reputation database. Decentralized reputation systems used by MANET, on the other hand, do not use centralized reputation database. Instead, in these reputation systems, each node keeps the ratings about other node and updating the ratings by direct observation of the behaviorsof neighboring nodes or second hand information from other trusted nodes. Identifies three goals for reputation systems:

• To provide information to distinguish between a trust-worthy principal and an untrustworthy principals.
• To encourage principals to act in a trustworthy manner
• To discourage untrustworthy principals from participating in the service the reputation mechanism is present to protect.

Most of the reputation systems in MANET are based on trust management system. Trust is such a subjective and dynamic concept that different entities can hold different opinions on it even while facing the same situation. Trust management system can work without reputation system. For example, a mobile node can form opinion about other nodes by direct experience with the nodes.We can unify reputation system and trust management system to dynamic feedback mechanisms. Former one is a global reputation system and mobile nodes share their own experiences of interaction with other nodes. The later one is a local reputation system in which mobile nodes rating the trustability of other nodes based on its own observation.

DSR

DSR is a reputation system aiming at coping with misbehavior in MANET. The idea is to detect the misbehaved nodes and isolate them fromcommunication by not using them for routing and forwarding and by not allowing the misbehaved nodes to use itself to forward packets. DSR stands for Cooperation Of Nodes: Fairness In Dynamic Ad-hoc Network. It usually works as an extension to on demand routing protocols. With DSR each node has four components: Monitor, Reputation System, Trust Manager and Path Manager. These components interact with each other to provide and process protocol information. Figure 3-2 illustrates the architecture of the DSR components based on DSR protocol. Monitor is responsible for gathering firsthand information about the behavior of other nodes in the network. This is achieved by observing and detecting various attacks. A typical misbehavior is packet dropping. The monitor detect it by an enhanced Passive Acknowledge mechanism. The monitor can also detect other attacks such as message modification and fabrication through overhearing the packets forwarded by next hop. Reputation System is the core component of DSR. It is responsible for maintaining reputation rating about other nodes in the network. The reputation rating about other nodes is updated based on the firsthand information observed by the node or the secondhand information published by other nodes. Reputation System decides whether to accept secondhand information and how much the information is incorporated to update reputation ratings. Based on reputation ratings, Reputation System identifies misbehaved nodes. Trust Manager maintains the trust rating about other nodes in the network. Trust rating represents a node's opinion about how honest another node is as an actor in the reputation system. It is used as an alternative way to decide whether to accept second hand information. The benefit of using trust is to speed up the detection of misbehaved nodes. Path Manager performs actions once a misbehaved node is identified, e.g. deletion of paths containing misbehaved nodes, action on receiving request for a rout containing a misbehaved node in the source route, etc. With DSR each node collects two major types of information about other nodes which it has communicated or heard about in the network: first-hand information and second-hand information. Based on the information the reputation rating is updated. To have an accurate estimation of misbehavior, Bayesian estimation is employed to form reputation ratings and making other decisions. DSR distinguishes trust from reputation. For each node, reputation rating represents how well a node behaves while trust rating represents how honest a node is.Reputation rating is used to decide whether the node is regular or misbehaved, while trust rating is used to decide whether the node is trustworthy or not as a recommender. Following description illustrates how DSR works to mitigate the misbehavior in the network. When a node sends a packet to its neighboring node which is supposed to forward the packet, the node detects whether the neighboring node forwards the packets by listening the packet in a promiscuous mode, which is called Passive Acknowledgement. If it hears the packet is forwarded, it updates the first-hand information and increases the reputation rating about the neighboring node. If it doesn't hear the packet within a certain time, it thinks the neighboring node misbehaves and decreases its reputation rating. Whenever the reputation rating about another node is updated, the node will identify whether it is misbehaved node or not by comparing the reputation rating with a misbehaved threshold. The identified misbehaved nodes will be reported to Path Manager which will take further actions. Every node periodically spreads the firsthand information it has collected to its neighboring nodes. If a node receives the published firsthand information and thinks the source of the information is trustable, it will incorporate the information to update the reputation ratings it keeps. It is very important to know that with DSR a node only forwards or responds to nodes with good behavior. In this way, it isolates misbehaved node by bearing grudges to it.

CORE

Similar to DSR, CORE (COllaborative REputation mechanism) also provides a mechanism to enforce node cooperation based on a collaborative monitoring technique. However, CORE is different from DSR in reputation model and the way to spread rumor. Three types of reputations are used in the CORE.

• Subjective reputation of a target node is the reputation calculated directly from a subject's observation of the target node's behavior.
• Indirect reputation is evaluated only considering the direct interaction between a subject and its neighbors.
• Function reputation is the subjective and indirect reputation calculated with respect to different functions such as forwarding a data packet, reply route request. The final reputation information is combined from the three reputations with different weight associated to the functional reputation value.

CORE consists of two basic components:

• Reputation Table (RT) is a data structure stored in each network entity, keeping the reputation data pertaining to the nodes in the network.
• The Watchdog mechanism (WD) is used to detect misbehaved nodes. With CORE only positive rating factors are distributed among the entities to avoid a misbehaving entity to distribute false information about other entities in order to initiate a denial of service (DoS) attack.

OCEAN

Both DSR and CORE use second-hand information which is subject to false accusations and requires a node maintaining trust relationship with other nodes. On the contrary, Sorav Bansal and Mary Baker proposed OCEAN (Observation-based Cooperation Enforcement in Ad Hoc Networks) which only uses direct first-hand observations of neighboring nodes' behavior.With OCEAN, each node has five components: NeighborWatch is used to observe the behavior of the neighboring nodes. It can detect whether the next hop sends the packet successfully or not by Passive Acknowledgement. RouteRanker maintains a rating for each of neighboring nodes. The rating is initialized to neutral and is incremented or decremented on receiving positive or negative events respectively from the NeighborWatch component. Once the rating of a node falls below a threshold the node is put into a fault list and is avoided to be used to forward packets. Rank-Based Routing applies the information from NeighborWatch in the actual selection of routes. To avoid routes containing nodes in the faulty list, an avoid list is added to DSR Route Request Packet (RREQ). On re-roadcasting the RREQ, each node can add its own avoid list to the packet. The nodes receiving the RREQ will check the avoid list in RREQ and decide whether to suppress the packet or reply with Route Reply. Malicious Traffic Rejection rejects all the traffic from nodes it considers misleading so that a node is not able to relay its own traffic under the guise of forwarding it on somebody else's behalf. Second Chance Mechanism allows nodes previously considered misleading to become useful again since a node may "misbehave" due to accidental link error. The misleading node is removed from the faulty list after a fix period of observed inactivity.

LARS

Jiangyi Hu proposed a simple reputation based scheme, called LARS (Locally Aware Reputation System) to mitigate misbehavior and enforce cooperation [26]. Different from global reputation based schemes, with LARS each node X only keeps the reputation values of all its one-hop neighbors N(X). The reputation values are updated based on the direct observation of the neighbors. If the reputation value of a neighbor node M is under threshold, then M is considered by X as misbehaved node. X will notify its neighbors about M's misbehavior by initiating a warning message. To avoid false accusation, conviction of the uncooperative node is co-signed by m different nodes, where m-1 is an upper bound on the number of malicious nodes in the one-hop neighborhood. If the warning message is verified, it is then broadcasted to the k-hop neighborhood and M's khop neighbors become aware of its misbehavior and refuse to serve for it.

Discussion on the Reputation Systems

Although different in reputation model and detailed implementation, all the reputation systems we have introduced have three common parts:

• All the systems detect misbehavior using mechanisms similar to Passive Acknowledgement.
• All the systems maintain reputation ratings about all or part of other nodes in the network and identify misbehaved nodes.
• All the systems react to the misbehaved nodes. Besides the systems introduced in this section, there are many other reputation systems for MANET. Basically they can be classified into following categories:
• Global reputation system in which each node knows reputation value of every othernode in the network. This is achieved by exchange indirect reputation message among the network. DSR and CORE are examples of global reputation system.
• Local reputation system in which each node only keeps the reputation value of its neighboring nodes. Instead of distributing reputation value or information periodically, the local reputation systems usually update reputation value based on its own observation. points out following disadvantages of global reputation systems Each node maintains reputation values of every other node, which costs a lot of storage. Disseminate reputation information greatly increases the volume of network traffic.
• The decision and incorporating second hand information consumes addition computation.
• The reputation information could be modified, replayed or accidentally lost during transmission. Hu thinks that the global systems are unnecessary due to above disadvantages. Although the reasons he analyzed may exist, the author of the thesis cannot totally agree with his negative conclusion about the global reputation system. To judge whether a system is good or not depends on how well it can mitigate misbehavior and improve the network performance. If the system can identify the misbehaved node precisely and send the packet successfully at the minimum tries, then the cost of above factors can be compensated.

Watchdog and Pathrater

Marti et al proposes two techniques that improve throughput in an ad hoc network in the present of misbehaved nodes [27].The watchdog method is used for each node to detect misbehaving nodes in the network. When a node sends a packet to next hop, it tries to overhear the packet forwarded by next hop. If it hears that the packet is forwarded by next hop and the packet matches the previous packet that it has sent itself, it considers the next hop behaves well. Otherwise it considers the next hop misbehaves. The pathrater uses the knowledge about misbehaving nodes acquired from watchdog to pick the route that is most likely to be reliable. Each node maintains a trust rating for every other node. When watchdog detects a node is misbehaving, the trust rating of the node is updated in negative way. When a node wants to choose a safe route to send packets, pathrater calculates a path metric by averaging the node ratings in the path. Marti et al implemented the solutions on DSR protocol using ns2 as simulation environment. The simulation result shows the throughput of the network could be increased by up to 27% in a network where packet drop attack happens. However routing overhead is also increased by up to 24%.

Trust-based Routing

In his master's thesis, Lennart Conrad developed an improved trust-based routing DSR [14]. With the trust-based routing DSR each node keeps the trust value of all other nodes. Different from most reputation solutions which uses passive acknowledgement to detect whether neighboring node has forwarded a packet or not, trust-based DSR uses an explicit acknowledgement packet sent by the receiver to confirm that the packet has been forwarded by all the nodes along the route successfully. If the sender receives the acknowledgement packet within a timeout, it will increase the trust values of all the nodes along the route. Otherwise it will decrease the trust values. Then a node will choose a most trustful route when it has to send a packet. The main contribution of Lennart's solution is that he proposed alternative trust value updating and route selection strategies. The simulation results show significant improvement in throughput compared to regular DSR.

Cryptography

Several cryptography based routing protocols have been proposed based on the modification of existing ah hoc network routing protocols. Ariadne and Key Management System are among them.

Ariadne

Ariadne [28] is a cryptographic based security solution for on-demand routing protocol, for example, DSR. It prevents attacks of compromising routing information or Denial of Service in ad hoc network. Instead of using traditional symmetric protocols such as RSA, Ariadne primarily uses the TESLA broadcast authentication protocol for uthenticating routing messages. The advantage of TESLA is that it is not computing intensive and it only add a single message authentication code (MAC) to a message for broadcast authentication, which is very important for resource limited mobile devices. Ariadne mainly authenticates packets containing Route Request, Route Reply and Route Error to prevent misbehaved nodes changing route information. Ariadne's authentication mechanisms only check whether the route information is compromised but do not detect whether the messages are dropped. To thwarting such routing misbehavior, it uses feedback about which packets were successfully delivered. The feedback can be received either through an extra end-to-end network layer message, or by exploiting properties of transport layer such as TCP. When there are multiple routes to a single destination, Ariadne sends more fraction of packets along the route with betteroverall feedback for the nodes in it. Ariadne assumes

• Network link is bidirectional
• All nodes have loosely synchronized clocks
• One of following keys to be set up: TESLA, pairwise shared secret keys or digital signatures.

Key Management System -- Threshold Cryptography

Using cryptographic schemes to protect routing information and data traffic usually requires a key management service. Zhou et al proposes a key management system which adopts a publish key infrastructure to distribute keys. They use a so-called (n, t + 1) n=3t+1 threshold cryptography scheme which allows n servers to share the key management responsibility operations, e.g. create a digital signature, so that any t + 1 parties can perform this operation jointly but it is infeasible for at most t parties to do so, even by collusion. With threshold cryptography, each server has a public/private key pair. All nodes in the system know the public key of the service and trust any certificates signed using corresponding private key. The scheme divides the private key k of the service into n shares, assigning one share to each server. Then with t + 1 correct partial signatures the combiner is able to compute the signature for the certificate. However compromised servers cannot generate correctly signed certificates because there are at most t of them.

Discussion on the Cryptography Systems

Comparing to other security mechanisms such as payment systems and reputation systems, the cryptography systems has the advantage that it can cope well with Denial of Service attack and any form of message modification and fabrication. However, the cryptography by itself cannot effectively deal with packet drop attack. Furthermore, most of the cryptography systems assumes key distribute system available, which is the weakness of mobile ad hoc network.

Artificial Immune System - an Intrusion Detection System

Slavisa and Jean proposed an artificial immune system [14] [32], which analogs natural Immune System (IS) of human, to detect misbehavior in MANET. The natural IS has two components, innate IS and adaptive IS. The innate IS is hard-wired to detect and destroy non-self cells that contain or do not contain specific patterns on their surface. Human skin is an example of innate IS. The adaptive IS detects the non-self cells and "learns" the patterns of the cells and thus can quickly response next time. The idea of the artificial immune system is to map the natural IS elements to a detection system in MANET. For examples, the body of the human is mapped to the entire mobile ad-hoc network; Self cells are mapped to well behaving nodes and non-self cells are mapped to misbehaving nodes; Antigen is mapped to a sequence of observed DSR protocol events recognized in sequence of packet headers, i.e. "data packet sent", "data packet received", etc. The simulation shows a good detection capability. However, it is premature to draw general purpose conclusion about the performance of the AIS approach and more investigation need to be done in this area.

Summary

This section has introduced the general security issues in the MANET and various solutions that have been proposed. The solutions can be classified to several categories, payment system, reputation system, trust-based system and cryptographic system. Each system has its own advantages and disadvantages. Payment systems serve as an incentive to provide a well-defined service. They are easy to understand and implement. However, to ensure the payment not to be modified by misbehaved nodes, tamper-proof hardware and trusted third parties may have to be required. Furthermore payment systems assume that every node forwards the packets and they are not good at mitigating misbehavior. Reputation systems aim at encouraging good behavior and punishing misbehaved nodes. They can be further classified into global reputation systems and local reputation systems. Global reputation systems use secondhand information and can speed up detecting the misbehaved nodes. However, distributing the reputation information periodically increases the network overhead. Local reputation systems do not publish the reputation information and mostly use direct information about other participants in the network. They are more lightweight but may be slow at detecting misbehaved nodes. Trust-based systems are very similar to the local reputation systems in some aspects, except that it only uses firsthand information it has learned in the previous interactions with other misbehaved nodes. Furthermore, trust-based systems are different from local reputation systems in that it never influences the other entities decision by its own reputation ratings. Cryptographic systems can detect attacks that the other three systems cannot do, e.g denial of service (DoS). However, the systems assumes key distribute system available, which is normally not available in mobile ad hoc network. We also introduced an intrusion detection system, artificial immune system, which simulates human's immune system to detect attacks. The mechanism is still in the initial stage and it is not clear whether it is efficient in a real or simulated system.

Analysis

In this chapter, we analyze the most important features, models and existing problems in the DSR protocol, DSR protocol and ns2. These features, models and problems will impact the software design and performance evaluation. We also make assumptions and define the name convention that will be used in the following chapters.

Analysis of DSR Protocol

Apart from the basic functions of DSR protocol that has been introduced in section 2.1, we are also interested in some additional features of DSR. These features will impact the network performance especially after the integration with DSR. We will analyze these features and decide whether they will be enabled or not in our project.In the following section, we call the DSR protocol as standard DSR and the DSR fortified DSR protocol as DSR.

The Importance of Route Redundant

All the dynamical feedback mechanisms investigated in chapter 3 rely on inherent redundancies - multiple routes available to a single destination. As long as there are enough good nodes and alternative routes, packets can go around those misbehaved nodes and arrive at a destination. Thus increasing the number of available routes to the same destination is very important. The route cache is used to store routes in the standard DSR. When a node gets a new route, either by initiating a new route discovery or by overhearing a packet which contains route information, it adds the route into the route cache. When the node wants to send a packet to a destination node, it searches a shortest route to the destination in theroute cache. If no route is found, the node will send out a Route Request to find new routes.With standard DSR, a node selects a shortest route to the destination from the route cache. In DSR, however, it works in different way. Rather than calculating the shortest hops, a node selects the route which contains no misbehaved nodes. The more alternative routes available in route cache, the more possibility that a node can find a qualified route. Thus when we decide whether to enable a DSR optional feature or not, we use thefollowing criteria: The additional feature should be enabled if it can increase the number of routes discovered or cached. Otherwise it should be disabled.

Only Forwarding the First Route Request Message

When a node initiates a Route Discovery, it broadcasts the Route Request message to all its neighboring nodes and these neighboring nodes will append its address to the address list of the message and propagate the copy of the message to their own neighbors. There will be message flooding if the Route Request is forwarded unlimitedly. To mitigate the problem, DSR protocol specifies that a node should only forward the first copy of the same Route Request message it receives. Figure 4-1 illustrates why the propagation of Route Request should be controlled. The intermediate node A receives a Route Request message for the first time and forwards it to B (see the dashed arrow). B forwards the Route Request to its neighboring nodes (see the dashed-dotted arrow). A receives the Route Request a second time and drops it. If the propagation of Route Request message is not controlled, A will forward the message again to B (see the dotted arrow) and the message will be forwarded endlessly. Figure 4-2 illustrates another scenario of Route Request propagation control. To discover a route to the destination E, the source node S broadcasts a Route Request message to its neighboring nodes A, B and C. The node D receives the three copies of Route Request message from node A, B and C. (We assume D receives the first copy from B.) If D forwards all the three copies of the Route Request to E, then the number of packets is tripled compared with the case that D only forwards the Route Request it receives from B. Thus in this case, DSR requires that D only forwards the first Route Request and discards the other two. This feature, however, limits the number of routes found in each Route Discovery. It will impact the performance of DSR as explained in the section 4.1.1. If B is a misbehaved node, then the route S A  BA  C A D will be discarded in route selection and it turns out that S has to initiate another route discovery. Thus the feature has two contradictory consequences in our project: enabling the feature will increase the number of Route Discovery; disabling the feature will cause message flooding. Since message flooding can cause much more serious problem we think it is reasonable for the feature to be applied.

Caching Overheard Routing Information

In DSR a node overhearing a packet should add all usable routing information from that packet to its own route cache. DSR specifies two ways for a node to overhear the routing information:

1. One way is that when the node is participating in forwarding a packet containing source route option or route error information, the node can update the information into its own route cache. This is a mandatory DSR feature.
2. The other way is an optional feature. If a node is in promiscuous mode and can snoop any packets sent by its neighbors, it will update the route information contained in the snooped packets into the route cache. The second way can increase the number of routes discovered. This becomes especially important in a network where misbehaved nodes present because the more the routes are available, the more possibilities there are safe routes. Thus we will enable this feature in our implementation.

Replying to Route Requests Using Cached Routes

DSR allows a node receiving a Route Request for which it is not the target to reply with the route found in its own route cache. In the Route Reply, this node appends the source route to the target node obtained from its own route cache after a sequence of hops over which the route request has been forwarded to it. After the node sends out the Route Reply, it will not propagate the Route Request any further. Figure 4-3 illustrates the scenario of replying to Route Request using cached routes. Source node S initiates a Route Request to find routes to destination D. When B receives the Route Request, it searches its route cache and finds a route B A  C A  D to the destination D. Then B concatenates the route with the accumulated source route S A  A in the Route Request and sends the Route Reply to source node S. Node B will not broadcast the route request further in this case. This feature, however, will decrease the number of routes discovered. For example, if B does not reply the route request with the cached routes and instead forwards the route request to node C, E, and F. Then we can get two additional routes: S A  A A  B A  E A  D, S A  A A  B A  F A  D. (As seen in Figure 4-3, the dashed lines indicates the routes could be found). But with this feature we can only get one route. Thus, we will disablethis feature.

Route Request Hop Limit

In DSR, each Route Request message contains a "hop limit" that may be used to limit the number of intermediate nodes allowed to forward the Route Request. DSR allows a ring search feature to discover routes. In the ring search mode, the source node sends out a Route Request with hop limit zero, which means only the neighboring nodes can receive the Route Request. If no route was found in the first round of route discovery, the hop limit will be increased to allow the Route Request to be forwarded to greater range of nodes. This feature can save the routing overhead in case the destination node is one of the neighbors of the source node. However, it will also limit the number of the routes being discovered and thus will be disable in our project.

Packet salvaging

When an intermediate node forwarding a packet detects that the next hop for that packet is broken and if the node has another route to the destination in its route cache, the node will salvage packet by using the new route instead of discard it. To avoid the packet to be salvaged endlessly, a counter is maintained in the packet to count the number of times that it has been salvaged. The packet salvaging feature can increase the number of packets arriving at the destination. However, since the node which salvages the packet changes the source route header, we should be very careful when using passive acknowledgement to detect the packet modification in DSR protocol. If a node receives a PACK packet and finds the salvage value is changed, it should not compare the source route with the original one.

Automatic Route Shortening (Gratuitous Route Reply)

DSR allows a source route to be automatically shortened if one or more intermediate nodes become unnecessary. As shown in Figure 4-4, source node S sends a packet to destination node D along the source route S A  A A  B A  C A  D. If C snoops the packet forwarded by A and finds itself on the source route but it has not explicitly receives the packet, C can confirm that node B is not necessary to participate in the forward and can be deleted from the source route. Then C sends a gratuitous route reply to notify source node S that there is a shortened route S A  A A C A  D. The automatic route shortening feature can save the time for a packet to be delivered to a destination. Particularly, in a network where misbehaved nodes present, the shorter route means less possibility that the route contains misbehaved node. Thus we enable this feature in our project.

DSR Flow State Extension

Since the draft version 9, DSR has added a new feature called "flow state" to allow the routing of the most packets without an explicit source route header in the packet. In this feature, when a sending node has discovered a source route, the node can establish a flow along the route which allows each node along the route to forward the packet to the next hop based on the node's own local knowledge of the flow along which this packet is being routed. The feature ignificantly reduces the overhead of the protocol because data packet need not carry source route along the way. owever, we will not enable this feature in our project. The reason is that the flow state is a new feature and its impact on the DSR is unknown. DSR has no specification about how to deal with it. Furthermore we want to compare our simulation result with that of Sonja reported in her Ph.D thesis [7] which does not support flow state.

Other Features

DSR provides other additional features to improve the performance of a MANET. For examples, a node will handle the queued packets in Network Interface Queue and Maintenance Buffer if it detects the next-hop link of the route of the packet is broken; when a node receives a route error it usually spreads the message to other nodes by piggybacking the route error information in the next route request packet. These features have little impact on the performance of DSR and we will not discuss them in detail.

Analysis of DSR Protocol

In this section we will analyze the state chart of DSR to pave the way for software design. We will discuss the misbehavior detection and data representation that affects the implementation. We will also discuss the network verhead introduced by DSR which is one of the tasks of performance analysis.

States and Events

As introduced in section 3.3.1, there are five modules in DSR: DSR, Monitor,Reputation system, Trust manager and Path manager. These modules are interrelated together to provide and process all kinds of information. The modules also interact with DSR to send and receive packets. Figure 4-5 shows the interactions between the modules of DSR and DSR in each node. The ovals within each module represent the most important states of the module and the arrow lines indicate events or message between the states. The dashed lines describe how the first hand information is collected. When a node I receives a packet in the promiscuous mode from another node j within the DSR module, it passes the tapped packet to the Monitor to detect whether it is the PACK packet. If it is, the ratings about j will be updated. If the reputation rating is greater than misbehaved threshold, it will inform Path manager to delete all the paths that contains the node j from the route cache of node i. The dotted lines describe how second hand information published by the other nodes is handled. As seen in the figure, when node i receives published information it passes the information to the Reputation system to decide whether it should be accepted. If the information is accepted, the ratings about node j are updated. If the reputation rating after updating exceeds tolerance threshold, all the paths that containing the node j will be deleted from Path manager. The dashed-dotted line describes that a node periodically publishes the reputation ratingsit has about other nodes in the network. As seen, reputation system periodically calls theDSR to send out the firsthand information.

Detection of Misbehavior

Misbehavior detection is an important part of DSR. In this section we will introduce how DSR detects various misbehaviors. We will also analyze what kinds of misbehaviors cannot be detected by DSR.

Improved Passive Acknowledgement

Section 2.1.2 introduces the Passive Acknowledgement mechanism specified by DSR. DSR protocol uses the Passive Acknowledgement not only for an indication of the correct reception at the next hop but also to detect whether a node forwards packets that it is supposed to forward or not. In DSR the passive acknowledgement is improved so that it can have capability to detect more misbehavior types other than dropping packets. When a node overhears a packet, it checks following fields to see whether the packet matches the one it has sent previously.

• IP header: The TTL value must be decremented by one and only one.
• Route reply option: All fields
• Route error option: All fields
• Source route option: If the salvage value is unchanged, all fields except Segs Left; If the salvage flag changed, we only check Type, Last Hop External, First Hop External and Segs Left.
• Forged route error: a node can detect it, if the unreachable address in the routeerror option is its own.

If any one of above fields does not match, the next hop node is considered misbehaved and its reputation rating is updated in favor of misbehaving. Otherwise, reputation rating is updated in favor of honest.

Detectable Misbehavior

Generally the misbehaved nodes can be classified into two categories. One is the selfish nodes which drop packets only for the purposes of saving battery since transmission consumes energy. The other is the evil nodes which may intentionally drop, modify or fabricate packets. The later one could cause much more serious problems. For examples, by modifying a data packet, incorrect information will be sent to destination; by sending forged routing packets, an evil node can create a so-called black hole, a node where all packets are discarded or lost. Whatever the purposes of the attackers, DSR can effectively detect drop, modification and fabrication attacks through the PACK echanism. If a node does not hear the next hop forwards its packet within PACK timeout, it knows the next hop drops the packet. If the packet a node hears is different from the original one, it knows the next hop modifies the packet. If a node hears a packet which indicating the node participated to forward or originate but actually it does not, it know the next hop fabricates the packet. Furthermore DSR can detect if a node tries to tell big lie by publishing inaccurate information about other nodes. For example, when a node j publishes its first hand information about node k, it may tell a big lie and publishes opposite information which deviates from k's actual behavior. DSR can detect this by performingdeviation test. When node i receives the published information from j, it compares the information with the reputation rating it has about k. If the difference exceeds the threshold, i thinks j is lying and reject the information. Furthermore, i updates the trust rating of j in favor of untrustworthiness. In this way any dishonest will be detected.In summary, DSR can effectively detect following types of attack: packet dropping attack, modification attack, fabrication attack and big liars.

Undetectable Misbehavior

Although DSR is effective in detecting and mitigating the security problems such as dropping packets and big liar, there are also some types of attacks that DSR cannot efficiently cope with. Here we present some of these attacks.

Stealth attack

In the previous section we have discussed how DSR detects big liars. However, node j can make so called stealth attack, in which j tells small lies about node k so that it can pass the deviation test and gradually change the reputation rating of k kept by i. DSR cannot effectively detect the stealth attack.

Collusion

In the network if a certain number of nodes collude and publish similar false information about another node, then the node receiving the information cannot detect this. Figure 4-6 illustrates this. Suppose node i has no direct experience with k but receives published information from neighborhoods A, B, and C. If the neighborhoods collude and tell false information about k, then i will gradually believe what it is told and forms false opinion about k. When i moves to a new place where new neighbors tells correct information about k, i will not believe them.

Denial of service

If a node sends out a great number of packets to another node in a burst, that node will keep busy with handling the packets so that it cannot send packets of its own. The packets from other nodes also can not arrive at the node because they cannot get the medium to transfer the packets. DSR cannot detect such kind of attack.

False Detection

As stated in section 4.2.2.1, DSR enhances the Passive Acknowledgement mechanism to confirm the reception of the packet at the next hop and to detect if the next hop fails to forward packets. However, the mechanism of Passive Acknowledge has limitation and can cause false detection. That is, the next hop is regarded as misbehaving because the previous hop fails to hear the next hop forwards the packet but actually it does. The false detection may be caused by transmission collision or the limited transmission range. Following two diagrams depict how the problems happen. Figure 4-7 illustrates the false detection caused by transmission collision. The node A has sent a packet "a" to B and is expecting that B will forward the packet to C. When B forwards the packet "a" to C, the transmission collides at A with another packet "x" from node X. Then A can not hear the forwarded packet "a" and it thinks B drops the packet. Figure 4-8 illustrates the false detection caused by limited transmission range. Node A has sent a packet "a" to B and is expecting that B will forward the packet to C. At the mean time A moves out of the transmission range of B. When B forwards the packet "a", C receives it but A can never hear it. Then A thinks B drops the packet.

Bearing Grudges

One of the major features of DSR is to mitigate misbehavior by bearing grudges to the nodes identified as misbehaved nodes. On the other hand bearing grudge can also serve as incentive for nodes to behave well and thus improve network performance. Following are the possible ways to bear grudge to the misbehaved nodes.

1. Do not select a route containing misbehaved nodes to forward a packet.
2. Do not forward data packets originated from misbehaved nodes.
3. Alert the source node when finding a misbehaved node in the source route of the packet that is forwarded.
4. Do not forward or reply Route Requests originated from misbehaved nodes.
5. Do not forward or reply Route Request when misbehaved node(s) are present in the source route.
6. Do not forward or accept Route Error, Gratuitous Route Reply or other routing information originated from misbehaved nodes.

We think item (1), (2), (4), (6) are reasonable ways to bear grudge to misbehaved nodes. However (3) and (5) will not be adopted because the node forwarding a packet should not apply its own subject opinion in deciding whether the packet should be dropped. All the nodes only publish firsthand information but not their opinions! On the other hand, if the node does not forward the packet, it will be considered misbehaved by its previous hop.

Data Representation

According to DSR protocol, each node stores three types of data about any other nodes it has Communicated or heard about in the network. They are

• First hand information Fi,j: representing the node i's view of node j's behavior as an actor in the network.
• Reputation rating R i,j: representing the opinion formed by node i about node j's behavior as an actor in the network.
• Trust rating T i,j: representing node i's opinion about how honest node j is as an actor in the reputation system.

At first glance, it seems that the three types of data are redundant. They are actually different. First hand information only indicates direct observation about other nodes' behavior while reputation rating is a node's opinion of another node which is formed based on first hand information or secondhand information. Furthermore, DSRdistinguishes reputation from trust. The former indicates a node's opinion on how honest another node is as a forwarder and the later indicates how honest another node is as a recommender. All the three types of data are represented in the form of Beta distribution( ( a,AŸ) which has been explained in section 2.2.2. They are initialized as (1, 1), which means in the node i's initial view about node j there are fifty percent possibility for j to misbehave or tell a lie. The updating of the three types of data can be depicted by Figure 4-9:

Overhead

DSR protocol causes overhead in three aspects: message overhead, storage overhead and computation overhead.

Message overhead

With DSR protocol, a node publishes first hand information periodically with a TTL of 1. The size of the overhead depends on the publishing timer that each node uses as well as the size of the public rating option. The structure of the public rating option is shown in Figure 4-10. DSR can cause other implicit routing overhead. Since DSR sends a packet only when safe routes are found, a node may need to send more Route Requests to discover safe routes.

Storage overhead

Each node stores three types of ratings: Ri,j, Fi,j, Tk,j. about other nodes that it has communicated or heard about. Each of the rating consists of two parameters of Beta function as well as the association to the node ID.

Computation overhead

Since the cost of internal computation in terms of energy consumption is negligible compared to the cost of a transmission or storage, we will not discuss further here.

Analysis of Network Simulator (ns2)

In this section we will present a problem existing in ns2 and analyze the packet drop reasons of DSR which are the basis of the performance evaluation.

A Performance Problem

The latest ns2 version 2.28 has a serious performance problem when testing with DSR. Searching from the ns-2 email archive [5] shows that the throughput of ns2 after version 2.1b9+ is 10 times worse than that of the previous versions. The throughput is especially bad when there are lots of messages in the network. Evaluation simulations have been conducted for DSR at different packet rates. The simulations run on ns-2.28 with 50 nodes in the area of 1000 A—1000 m2 at different packet rate. Packet rate means how many packets are sent in one second time. For each packet rate five scenarios were tested and the results are the mean of the throughputs of the five scenarios. The network bandwidth is 2 Mb/s. The simulation results are shown in Figure 4-11. As seen, the throughput is more than 90% when the packet rate is 2 packets per second. When the packet rate is ncreased to 4 packets per second, the throughput decreases to less than 45%. By analyzing the trace file, we found that the reason why the throughput deteriorates when packet rate increases is that there are so many packets in the network that most of packets are dropped due to IFQ full. Normally IFQ is full because the network is overloaded so that the link layer cannot grab the transmission medium to send out the packets buffered in the queue. But in our tests the maximum data packets is 6.4k (2 p/s A— 64 bytes A— 50 nodes) and it cannot exceed 2Mbs bandwidth even plus routing overhead is counted. Currently no one could explain this and the investigation of the reason is out of the scope of the project. This performance problem could more seriously impact the throughput of CONFIDANT because the protocol introduces overhead by publishing first hand information and send additional routing packets as analyzed in section 4.2.5. Thus our compromised solution is to use the lower packet rate to mitigate the impact.

Packet Drop Reasons

The main task of the performance analysis is not only to interpret the simulation results but also to explain why throughputs are improved or decreases. In most cases we need to investigate where and why packets are dropped. By investigating the ns2 documents, and source code, we summarize the several types of packet drop that play important roles in the simulation. These packet drop reasons are listed in Table 4-1.

Name Convention

In CONFIDANT protocol, a node classifies the other nodes in the network either as misbehaving or honest based on its reputation rating about those nodes. The identified misbehaved node may actually be a normal one. To avoid confusion when we describe the nature of the nodes, we define following name conventions about the nodes in the aspects of reality and opinion. We define nodes in reality as follows:

• Evil node: a node that intentionally drops packet.
• Normal node: a node behaves as the routing protocol specifies. We define nodes in the opinion of other nodes as follows:
• Misbehaved node: a node is considered misbehaving by another node. A misbehaved node may be actually a normal node but is misidentified.
• Good node: a node is considered normal by another node. A good node may be actually an evil node but is misidentified.

Assumptions

Assumptions about Mobile Ad Hoc Network

Since the CONFIDANT protocol relies on Passive Acknowledgement mechanism to detect nodes that fail to forward packets, we assume following items about the mobile ad hoc network.

• The wireless communication between any two nodes is bi-directional.
• The network interface of any node is in the promiscuous mode. In this way, a node is able to find out whether the next node forwards the packet if both of them are still in the transmission range of one each.

Assumptions about Misbehaved Nodes

As discussed in section 4.2.2.2, CONFIDANT can detect dropping attacks, modification attacks and fabrication attacks. Due to the time limitation, we only simulate dropping attacks in this project. In the dropping attack, an evil node could drop all the packets it is supposed forward or destined to itself. It could also be partial dropping, which is restricted to specific types, e.g data packets or routing packets containing Route Error. When we simulate the evil nodes, we want to maximize the bad effect of evil nodes in the network and see whether CONFIDANT can mitigate the problems. Based on this guideline, we make following assumptions about evil nodes.

• The primary interest for evil nodes is to drop data packet since dropping data packet can have more serious consequence than dropping routing packets in general. The purpose of the routing protocol is to enable the data packets exchange between any communication ends in the network. Dropping data packets will also decrease the network throughput significantly.
• Evil nodes drop Route Replies or Route Errors that are not destined to them.
• Evil nodes forward Route Requests. Dropping Route Requests is meaningless for evil nodes if its main target is to drop the data packets. In the mobile ad hoc network where dynamic routing protocol is used, the source node can often find alternative routes to the destination. Thus blocking a route by dropping Route Request may lead to opposite consequence: the data packets will be forwarded by safe routes. Figure 4-12 explains the scenario.

Node S wants to send data packet to destination node D. It initiates a Route Request which is broadcast to its neighbors A and B. Suppose B is evil node. If B drops the Route Request, the route S A  B A  D would never be returned to S. Instead route S A  B A  D will be used. Thus B will not have chances to receive data packets from S. Since the primary interest for evil nodes is the data packet, we assume B should not drop Route Request. Evil nodes reply Route Request destined to themselves because their aim is to drop messages sent to other nodes but they don't want to lose any message destined to themselves.

Summary

This chapter serves as the software requirement analysis in the view of software development process. In the chapter we have analyzed DSR protocol, CONFIDANT protocol and ns2 simulator regarding the problems that will impact our software design, implementation and performance evaluation. The analysis of DSR focuses on deciding whether to enable the additional features or not. First of all a criteria is set saying that the enabled features should increase the cached routes as much as possible. Then each additional feature is discussed based on the criteria.Table 4-2 summarizes our analysis about the features We then analyzed the CONFIDANT protocol. A state machine is given to describe the states and events in CONFIDANT components. The attack detection mechanism is introduced and a discussion about what kinds of attack can be detected or cannot be detected is elaborated. CONFIDANT maintains three types of information so we analyzed the mathematical representation of the information. Ns2 is the development and simulation environment of our project. We discussed the potential problem existing in ns2 and proposed a solution. The packet drop reasons are also investigated for future use. Finally, we make some assumptions and name conventions which will be used in the thesis.

Design

This chapter presents the software design of the CONFIDANT forties DSR. First an overall architecture is introduced. Then the class diagrams of CONFIDANT modules, DSR modules and the combination of them are explained in detail. The class diagrams present the static view of the software. We also use sequence chart to describe the dynamic behavior of the modules. Finally we present the design of trace and parser which serves as utility functions in the project.

Framework and Modules

CONFIDANT fortified DSR protocol is composed of several modules that interact with one another to mitigate misbehavior and improve the network performance. We have analyzed the state machine of the modules in section 4.2.1. Here we present an architecture overview of the modules which gives better description of the component layers of the software and the relationship between them.Figure 5-1 shows the major modules of CONFIDANT fortified DSR. Monitor is responsible for registering packets which are sent by a node and supposed to be forwarded by the next hop, detecting whether the PACK packet contains any form of attack and whether next hop drops packet. It also reports the first hand information to Reputation System. Reputation System maintains the reputation ratings of other nodes based on the selfobserved first-hand information as well as second-hand information published by other nodes. It is responsible for identifying the misbehaved nodes and reports them to PathManager. Trust Manager maintains the trust ratings of other nodes and decide whether these nodes are trustful when they act as recommenders in the network. It provides an alternative way to decide whether to accept the incoming second-hand information. Path manager is responsible for maintaining cached routes and selecting a safe route which contains no misbehaved nodes. It also takes actions when misbehaved nodes are identified, e.g. remove the routes containing misbehaved nodes from cache. DSR is the underlying dynamic source routing protocol. It is responsible for discovering the routes, sending and receiving packets in the routing level and tapping packets in the promiscuous mode. Trace & statistics are utility functions for logging and statistics. The logged information is the simulation result that will be analyzed in performance evaluation.

Data Structures

Figure 5-2 is the class diagram of CONFIDANT which is designed based on the architecture displayed in Figure 5-1. As seen, each module of CONFIDANT in Figure 5-1 corresponds to one or more classes in Figure 5-2. In the following sections we will explain in details how the classes are designed for the functionalities of each module.

Monitor

We divide Monitor into two sub-modules. One is the core monitor which serves as the interface to DSR and controls the main logic within the module. The other one is the detector which is responsible for detecting various attacks. As shown in Figure 5-3, Detector class is an abstract class which provides the interface to detect attacks. It has several inherited classes each of which detects different type of attacks. The classes work in following way. When the program starts, the core-monitor is instantiated. Then instances of different detectors are registered at the core-monitor. When a node sends a packet, it registers the packet in the core-monitor so that the monitor knows that the node wants to verify whether next hop forwards the packet. When the core-monitor receives a tapped packet, it checks whether it is a PACK packet. If it is, the core-monitor calls the detectors to detect whether there are any forms of attack. The advantage of creating polymorphic detector classes instead of using a single comprehensive Detector class is to make the system extendable. Different types of attack can be added easily without causing a lot of changes in the existing system. Apart from handling tapped packets heard from next hops, Monitor also keeps a PACK timeout for each registered sent packet and periodically checks whether next hops fail to forward the packet. If no PACK data is heard within PACK timeout then the Monitor will consider the next hop drops the packet and report this information to the Reputation System. In ns2, every packet is associated with a so-called uid, which is the abbreviation of unique identification. We utilize the uid to judge whether a tapped packet is the PACK packet that the node is waiting for. When a node sends a packet to its next hop, it registers the packet in Monitor. When the node receives a packet from next hop, it compares the uid of the received packet with that of the registered one. If the uids are the same, it thinks the received packet is the PACK packet. Otherwise, it is not.

ReputationSystem

The class ReputationSystem corresponds to Reputation System module. The primary function of the class is to handle the firsthand information given by Monitor and second hand information published by other nodes. The class is also responsible for implementing mathematical models for firsthand information ratings, reputation ratings, Bayesian mean and deviation test. ReputationSystem handles two timeout events. One is the inactivity timeout event for which firsthand information and reputation ratings are faded according to fading factor. The other is the publishing timeout event for which the firsthand information is published. Last but not the least, after each updating of a node's reputation rating, ReputationSystem examines the mean reputation value of the node and determine whether it is misbehaving. If any misbehavior node is identified or redampted, the information will be reported to PathManager.

TrustManager

The class TrustManager corresponds to TrustManager module. The primary function of TrustManager is to provide an alternative way to decide whether to accept second hand information. The class maintains trust ratings about other nodes. The rating indicates whether a node is trustworthy to be a recommender. The class works in following way. Whenever ReputationSystem conducts deviation test about node i, TrustManager updates the trust rating of i. If the result is positive, the rating is updated in favor of trustworthiness. Otherwise, it is updated in favor of untrustworthiness. When node i receives secondhand information about node j, ReputationSystem queries about whether j is trustworthy from TruatManager and then decides whether to accept it.

PathManager

The class PathManager corresponds to Path Manager module. It maintains the route cache of DSR. It provides interface to ReputationSystem so that reputation system can inform it when misbehaved nodes are identified or redempted. Since the Path Manager deals with cached route very closely, we extend PathManager from RouteCache class with additional methods (see Figure 5-6). CONFIDANT requires that when a misbehaved node is identified, Path Manager should delete all the routes containing the misbehaved nodes. Instead of deleting routes immediately, in our design we mark the routes and keep them in the cache until route cache is full. When a node searches a route in the route cache, Path Manager only selects safe routes which contains no misbehaved nodes.

Existing DSR Components in ns-2

The simulator version ns2.28 that we are going to use already contains the implementation of DSR. The existing DSR components are expressed in Figure 5-7 As shown in the Figure 5-7, the core class of the DSR module is DSRAgent class. Each node has one instance of DSRAgent. The class inherits from two parent classes.

• The Agent class, through which the DSR is hocked to the ns-2 and runs as routing protocol.
• The Tap class, through which DSR can receive the packets in the promiscuous mode.

Each DSRAgent instance contains one instance of RouteCache. The RouteCache is an abstract class from which various route cache classes inherit to apply different route maintenance strategies. Mobicache is the default route cache of DSR. Each DSRAgent instance also contains one instance of RequestTable. As we analyzed in section 3.1, a node should only forwards the first copy of same Route Request message it receives. The purpose of RequestTable is to judge whether the node has received the same Route Request before. It records the Route Request packets that a node has processed so that the same Route Request will not be forwarded many times. Hdr_sr is a header file containing the definitions of all types of DSR option headers.SRPacket wraps the structures of routing packets or data packets and provide easy accessmethod to get and set the source route.

Combining CONFIDANT and DSR

The combined class diagram of CONFIDANT and DSR can be seen in the Figure 5-8. CONFIDANT interfaces with DSR in the following situations.

• When DSR sends out a packet, it registers the packet in Monitor by calling Monitor->registerSentPacket(packet).
• When DSR taps a packet, it calls Monitor->handleTap(packet) which compares the tapped packet with the ones that registered. The packets are uniquely identified by the uid. If the uids of the two packets are the same the tapped packet is considered a PACK packet and the original sent packet is removed from the buffer. Monitor then further call etectors to detect whether there are any forms of misbehavior.
• When DSR receives a packet which contains first hand information published by other nodes, it passes the information to ReputationSystem by calling handleSecondhandInfo(info).
• When ReputationSystem wants to publish first hand information, it passes the information to DSR. DSR then creates a packet containing the publishing header option and sends out the packet.
• When DSR needs a route to send packet to destination, it calls PathManager- >findRoute() which searches the route cache to find a route containing no misbehaved node. If no safe route is available, DSR will initiate a Route Discovery.

Dynamic Behavior

In the CONFIDANT protocol, we concern about following major behaviors:

• Handle first hand information
• Publish first hand information
• Handle second hand information published by other nodes
• Bear grudge to misbehaved nodes We will explain these scenarios using sequence chart in this section.

Handle First Hand Information

Figure 5-9 illustrates how the first hand information is collected. Three parts of message sequences are involved in this scenario. They are:

• Register the packets sent
• Handle tapped packets
• Handle PACK timeout

Register the sent packets. When a node sends a packet, if it wants to check the passive acknowledgement from the next hop, it registers the packet in the monitor by calling Monitor->registerSentPacket(packet) so that the packet can be compared with the PACK packet later. Handle tapped packets. When a node taps a packet in the promiscuous mode, it calls Monitor->handleTap(packet) to check whether it is a PACK packet that the node is expecting. The Monitor searches the packTable and if it finds a packet with the same uid as that of the tapped packet, it considers it as a PACK packet. It then calls Detector->detector(packet) to check whether the packet is modified maliciously and gets the behavior of the next hop. Finally it calls the methods of ReputationSystem to update the first hand information rating and reputation rating. Handle PACK timeout. If the Monitor does not detect the PACK packet within certain timeout, it will consider the next hop as misbehaved and call ReputationSystem to update the first hand information and reputation rating.

Publish First Hand Information

In this scenario, each node periodically broadcasts its firsthand information about other nodes to all the neighboring nodes. When PUBLISH_TIMEOUT expired, the ReputationSystem call the DSRAgent to send out the publishing firsthand information packet. The TTL of the packet is set 1 so that only the neighboring nodes can receive the information and avoid flooding the packets to the whole network.

Handle Second Hand Information

When DSRAgent receives a public packet, it gets the firsthand information about several other nodes. It calls ReputationSystem.handleSecondhandInfo(rating) several times to handle each of the information. ReputationSystem first conducts deviationTest(). If the result of the deviation test is positive, the information will not be acceped. Otherwise, the reputation rating of the node will be updated. Then the reputation mean value will be compared with the misbehaving threshold to judge whether it is a misbehaved node. If it is, the node will be added to the misbehaving list maintained by PathManager. Otherwise it is removed from the misbehaving list. Whatever the result of the deviation test is, trust rating of the node which publishes the information will be updated.

Bear Grudge

When DSRAgent receives a packet, it queries PathManager about whether the originator of the packet is misbehaved by calling PathManager->isMisbehavedNode(packet.source). If it is misbehaved, and it satisfies the condition of the bearing grudge policy analyzed in section 4.2.3, then the packet will be dropped.

Trace and Parser

When running the simulations, some information about the mobile nodes must be logged for the purpose of performance evaluation. For example, to analyze the good throughput, we need to log how many data packets are sent from good nodes and how many are received. To analyze the misbehaved node identification rate, we need to log how many nodes are identified by each node during certain period of time and whether they are identified correctly. We use two different ways to log the information for different modules.

• Ns-2 trace function. DSRAgent uses ns-2 trace function to log packets that are sent, received or dropped. The trace function also logs other detailed information such as the originator and destination of the packets as well as the reason of packet dropping.
• C++ iostream function. All the CONFIDANT modules use C++ iostream to log the information in text file.

As shown in Figure 5-13, DSRAgent logs the packet sending and receiving information using ns2 trace function and CONFIDANT modules logs information using C++ iostream functions. After the simulation finishes, DSRParser parses the log files and get statistic data. The reason why ns2 trace function is not used by CONFIDANT modules is that to use the ns2 trace function, the class must be extended from the Agent class which is not necessary for CONFIDANT related classes. All the trace files are normal text files and can be parsed to give statistic results. DSRParser is designed to parse the file and Figure 5-14 shows the class diagram. The methods of DSRParser are explained as follows. parseTrace() - the method is used to parse the DSR trace file. parseRouteStats - the method is used to parse the trace file of the cached routes. parseReputationMean() - the method is used to parse the trace file of reputation mean value of nodes. parseMisbehaviorIdentify() - the method is used to parse the trace file of identified misbehaved nodes.

Summary

This chapter gives the design of the software from the high level architecture to the detailed class design of the modules. The design covers following modules:

• The Monitor module handles attack detection and reports firsthand information.
• The Reputation System module maintains and updates the reputation rating based on the reported firsthand
• information and secondhand information. It also distributes the firsthand information periodically.
• The Trus tManager module maintains the trust rating and judges whether a node is trustworthy or not.
• The Path Manager module maintains the route cache, responsible for selecting and deleting routes.

Following major dynamic behaviors of CONFIDANT are described:

• Handle first hand information
• Publish first hand information
• Handle second hand information published by other nodes
• Bear grudge to misbehaved nodes The chapter also presents the solution for trace and parser.

Implementation and Tests

The CONFIDANT protocol, parsers and simulations script are developed in three different computer languages of C++, Java and TCL. In this chapter, we briefly introduce the special language features and methods employed in the implementation.

Using C++ Standard Template

The three types of ratings kept by each node are dynamic. The sizes of the ratings cannot be decided at the compilation time but instead grow at run time. The rating of a node is indexed and searched by its network ID. To support the dynamic, scalable and quickly searchable features of ratings, the C++ Standard Template Library (STL) such as map, list and iterator are used. Following pseudo code give an example of how to use map to represent firsthand information. map<nsaddr_t, Rating*> firsthandinfo_t; //define the firsthand information table map<nsaddr_t, Rating*>::iterator it; //create an iterator it = firsthandinfo_t.find(address); //search the rating of a node if (it != firsthandinfo_t.end()) //If the rating is found { (it->second)->updateRating(alpha, 1-alpha); //update the rating } As seen in the above code, the firsthand information rating is defined as STL map class. Each element in the map contains a (index, rating) pair. When we want to search the rating of a node, the STL iterator class is used to find the rating corresponding to the given network ID.

Implementing Simulation Script

The ns2 simulator is started with an Otcl script which configures all the simulator related parameters such as the number of nodes, the routing protocol, the size of the simulated network area, etc. The script is implemented by tailoring a template for the general mobile ad hoc network. Please refer to Appendix K.10 for the source code.

Simulation Batch File

In our performance analysis, there are large number of simulations need to be done. Take the example of the simulations for evaluating throughputs of CONFIDANT, we need to test 5 different level percentages of evil nodes on 5 different scenarios each. If each simulation takes about half an hour, then it takes 5 A— 5 A— 0.5h = 12.5 hours for the simulations. It would be a tedious job if the developer monitors the computer for 12.5 hours and manually set up for each simulation. A better way is to implement a batch file so that the simulations can be executed automatically even during night. For this purpose shell batch files are developed which can be seen in the Appendix K.11 and K.12.

Test

We conducted following functional test for the system.

• The publish firsthand information are sent periodically and received correctly.
• Forwarding or dropping packets are detected.
• Firsthand information ratings, reputation ratings and trust ratings are updated in the correct way.
• The evil nodes drop certain types of packets.
• Misbehaved nodes are identified and routes containing these nodes are avoided.
• Normal nodes bear grudge to the misbehaved nodes.

The output can be generated for verification when the CONFIDANTVERBOSE and CONFIDANTDEBUG are set on in the hdr_confidant.h file. The tests have been conducted with a simple network. For example, only six nodes are presented in a network with range of 250m A— 250m. The number of packets sent is limited so that they can be easily tracked.

Summary

In this chapter we describe detailed implementation methods and language features by illustrating examples. We also discussed the functional test cases and the test context we used in testing. For detailed source code and configuration files please refer to Appendix K.

Performance Analysis

This chapter evaluates the performance of the CONFIDANT protocol. We first design the metrics for the performance evaluation. Then we introduce the important factors related to the network simulator, DSR and CONFIDANT. We conduct preliminary simulations to optimize the primary factors of CONFIDANT. After that simulations with different percentages of the evil nodes are conducted and the results are compared with that of standard DSR. Finally we analyze the performance of some variations of CONFIDANT.

Metrics

Throughputs and evil drop rate

Throughput is the most important metrics in our performance evaluation. Since the purpose of CONFIDANT is to improve the throughput for good nodes while bearing grudges to evil nodes, we evaluate the throughputs of good nodes and evil nodes separately. For simplicity, we call them good throughput and evil throughput. The goal of the CONFIDANT protocol is to increase the good throughput while decrease the evil throughput as much as possible.The formula used to calculate the good throughput is expressed in Equation 7-1. where evil packets are the packets orginiated by evil nodes. We also use evil drop rate to evaluate how effective CONFIDANT is to mitigate packet drop attack. Evil drop rate means how much packets are dropped by evil nodes compared to the total number of packet dropped. Equation 7-3 is used to calculate the evil drop rate.

Overhead

CONFIDANT introduces network overhead by publishing firsthand information periodically. The quantity of the overhead depends on the publish timeout. CONFIDANT may also increase Route Request message since it uses stricter route selection strategy. There are two factors in calculating overhead, the number of packets and the size of an individual packet. These two values cannot be simply multiplied since sending off a packet and transmitting a packet have different cost. Due to the time limitation we only consider the number of packets in our evaluation.

Misbehavior identification rate

In this performance analysis, we evaluate how much percentage of misbehaved nodes are identified in the network. The rate reflects how effective CONFIDANT is in identifying misbehaved nodes. To evaluate the identification rate, the average number of identified misbehaved nodes should be calculated periodically.

False positive and negative

As analyzed in section 4.2.2.4, sometimes a good node will be considered as misbehaving. We call this false positive. On the other hand, some evil nodes cannot be identified and are considered as normal nodes. This is called false negative. The false positive rate and false negative rate reflect how effective CONFIDANT is in identifying misbehaved nodes.

Simulation strategy

To form the comparison, simulations are conducted for Standard DSR, CONFIDANT and other modified versions of CONFIDANT. The outcomes of the simulations are compared to see whether the CONFIDANT have improvement or deterioration over the standard DSR in perspectives of the metrics, and whether the variations of CONFIDANT has different impact on the network performance. The most important factors that impact the simulation results are the topology and traffic connections of the network. To dynamically simulate the network, following files are generated randomly and automatically to get different topology and traffic pattern. A  Node-movement scenario - specify how mobile nodes move in the network. E.g. the number of nodes participating in the network, the position of each node, the maximum speed of the movement. Traffic pattern - specify how a node sends packets to another. E.g, the packet sent rate, the application protocol and the size of packet. Ns2 provides automation tools to generate the different node-movement scenario files and the traffic pattern files. The commands that are used to generate the files can be found in Appendix H. Once the files are generated, the topology and the traffic connections are deterministic. That means, the results are the same for any simulations that use the same pair of node-movement scenario and traffic pattern files. To ensure that the simulation results are not gained by using an exaggerated positive scenario, five different node-movement scenarios are used to do the simulations in consecutive for each comparison. The result is obtained by calculating the mean of five simulation results. For each simulation, a certain percentage of the nodes participating in the network are simulated as evil nodes. To form the comparison, these evil nodes are pre-defined instead of randomly selected.

Simulation of Evil Nodes

Most of the simulations in this project are conducted with 50 mobile nodes in the network. Among the 50 nodes, a minimum of 0% and maximum of 80% evil nodes are used. In the simulations, every node is associated with a unique network ID which ranges from 0 to 49. The evil nodes are simulated in this way. 40 out of the 50 nodes are pre-defined as candidate evil nodes. The network IDs of these 40 nodes are not contingent or sequential. When a certain number of evil nodes are supposed to be present in the network, for example 20 nodes, the first 20 nodes out of the 40 candidates are selected to act as evil nodes. The rest of the nodes behave normally even they are candidate evil nodes. Although there are various types of attacks on DSR, we concentrate on simulating packet drop attack for the purpose of performance evaluation because its impact on the network performance can be measured directly. The types of packets that are dropped by evil nodes are specified in section 4.4.2.

Parameters

As discussed in section 2.3.1, there are two categories of parameters in the simulations, factors and primary factors. Factors can be determined through theoretic analysis or experience while primary factors have to be tested and tuned during simulations. This section describes the factors and their values we have chosen. In the next section we will explain how primary factors are decided by analyzing simulation results.

Ns2 Related Parameters

Table 7-1 lists the most important ns2 related parameters and the values that will be used in the simulations. Most of the values are the same with those Sonja used in her thesis [7] so that the results of simulations can be compared. However the value of transmission rate, packet size and maximum speed are different. The reason why these parameters are chosen differently is explained in the section 4.3.1 As seen in the table, Constant Bit Rate (CBR) is chosen as the application protocol because it is simple and it makes the results easier to analyze. 50 nodes are present in the area of 1000 A— 1000 m2. Among the 50 nodes, 30 nodes are connected to send CBR packets to one another. The simulation lasts 900s so that enough packets are sent to eliminate any deviations. Normally two network bandwidths are available for wireless network, 2 Mbps and 11 Mbps. Since the transmission rate is 2 packet/s and packet size is 64 byte, the traffic cannot exceed 2Mbps even routing overhead are counted. Thus 2 Mbps is chosen as available bandwidth.

DSR Related Parameters

Table 7-2 lists the most important parameters related to DSR protocol. The parameter names are the same with those used in the source code. The reasons why certain values are chosen for them have already analyzed in section 4.1.

CONFIDANT Related Parameters

Table 7-3 lists the parameters related to CONFIDANT protocol. The parameter names are the same as those used in the source code. As shown in the table, all the parameters have to be tested and determined in the simulations. The parameters in this table are very important because they will directly impact the performance of CONFIDANT and even slight variation will change the results of the evaluation. As introduced in section 2.3.1, these parameters are called primary factors. We will tune these primary factors in the following section

Estimation of Primary Factors

As presented in the previous section, there are several very important factors of CONFIDANT. The values of these factors should be adjusted to get the best network performance. Through tuning the primary factors, we can also see how these factors impact the performance. In the subsequent sections, several reasonable values are chosen to be tested for each factor. For each value, five simulations are executed consecutively for different scenarios and the results are the mean of the outcome of the five simulations unless otherwise specified.

Estimation of Misbehaved Threshold

The purpose of misbehaved threshold is to distinguish misbehaved nodes from good ones. (Equation 4-6 describes the usage of the misbehaved threshold.) So the threshold should be less than the mean reputation value of most evil nodes and higher than that of most good nodes. The estimated values for other primary factors can be seen in the Table 7-4 To estimate the threshold value we take several steps to analyze the simulation results and approximate the value to the best selection.

Step 1: Analyze average mean reputation value

We first conduct a simulation to analyze the mean reputation value of each node. This step has following purposes.

1. Prove that there exists a misbehaved threshold that can distinguish misbehaved nodes from normal nodes. It requires that the intervals of the mean reputation values of misbehaved nodes and normal nodes do not overlap.
2. Select the range of misbehaved threshold so that the reasonable values will be tested to get the best simulation result.

In CONFIDANT, each node keeps reputation rating about any other nodes that it has communicated or heard about in the network. The mean reputation value is calculated according to Equation 2-4 and it indicates whether a node misbehaves or not when compared with misbehaved threshold. If the mean reputation value of a node is greater than the misbehaved threshold, it is considered as misbehaved node. Otherwise it is considered as normal node. It is meaningless if we look at the mean reputation value of only a few nodes due to the deviation. A better way is to analyze the average mean reputation value of any node stored by all other 49 nodes. As discussed in section 2.3.2, there are three alternative methods to calculate the average of sample data. Which one to use depends on the nature of data set and what is of interest to the user. Before analyzing the data we don't know which one should be used. However if the reputation system works in a correct way, the results of the three methods should look similar. Thus we calculate the average using all three methods and compare them. The results of the simulation are shown in Figure 7-1. Because of the space limitation, here we only present the average mean reputation values of the first 20 nodes. The results for all the 50 nodes can be seen in the Appendix F. As seen in the figures, the mean, median and mode of the mean reputation values look very similar. That means any one of the three kinds of values is meaningful to be used as the average. The modes for a few nodes are missing in the figure because there are several possible values for each of the modes and the word processing tool just doesn't know how to display them. But after checking the data source, those values are very similar to mean or median of the same node. As seen in the figure, the average mean reputation values of the misbehaved nodes are mostly higher than 0.8 while the values of good nodes are lower than 0.5. In our simulation the actual evil nodes in the simulation are 1, 3, 5, 7, 10, 11, 16, 19, etc. The figure shows that the mean reputation values higher than 0.8 absolutely match the actual evil nodes. This result proves the purpose 1) and also provides basis for choosing an appropriate range to tune the misbehaved threshold further. After analyzing average mean reputation values for more scenarios, we have found that the misbehaved threshold should be a value greater than 0.8.

Step 2: Adjust misbehaved threshold

Having estimated a gross range, we conduct more simulations to choose the best misbehaved threshold. Figure 7-2 shows the good throughput and evil throughput at different misbehaved threshold. We can see that the lower the threshold, the lower both the good and evil throughputs. Thresholds 0.85 and 0.9 are more favorable because the evil throughputs are very low while good throughputs are medium

Step 3: Analyze the misbehaved identification rate and false negative rate

Now we have narrowed our selection within two values, 0.85 and 0.9. We further analyze the misbehaved identification rate and false negative rate to decide which one to choose. Figure 7-3 shows the misbehaved identification rate for different misbehaved threshold. Figure 7-4 shows the false negative rate at different time. We can see that the identification rate of threshold 0.9 is slightly higher than that of threshold 0.85. However, in Figure 7-4, the threshold 0.9 has lower false negative rate. Thus we choose 0.9 as misbehaved threshold.

Cite this page