This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
What are MANETs and why are they so interesting. How do the routing protocols operate in this kind of networks. This chapter gives an overview of these as well as a study to understand which routing protocol is better to use for each environment.
MANETS: DEFINITION AND ORIGIN
Mobile Ad-Hoc networks or MANET networks are mobile wireless networks, capable of autonomous operation. Such networks operate without a base station infrastructure. The nodes cooperate to provide connectivity. Also, a MANET operates without centralized administration and the nodes cooperate to provide services.
Figure illustrates an example of Mobile Ad-Hoc network.
In a MANET there is no form of centralized administration. All nodes can perform as hosts and as routers. Also the nodes are mobile. Hence, the topology changes constantly.
MANETs can communicate with different networks that are not ad-hoc. Therefore, they can communicate with wired networks creating hybrid networks. In the ad-hoc networks, the mobility of the nodes makes that the topology changes continuously. Hence, a specific dynamic routing protocol for MANETs which discovers and maintains the routes, and deletes the obsolete routes continuously is necessary.
The routing protocols for MANETs try to maintain the communication between a pair of nodes (source-destination) in spite of the position and velocity changes of the nodes. To achieve that, when those nodes are not directly connected, the communication is carried out by forwarding the packets, by using the intermediate nodes.
Currently there is research on the behaviour of a lot of those routing protocols and the IETF (Internet Engineering Task Force) is working on the standardisation of some of them. The protocols that are in experimental phase RFC (Request For Comments) include DYMO (Dynamic MANET On demand Routing Protocol) [DYMO_06], OLSR [OLSR_03], AODV [AODV_03], DSR (Dynamic Source Routing) [DSR_04] and TBRPF (Topology Dissemination Based on Reverse Path Forwarding) [TBRPF_04].
The origin of MANETs begins in the 70's for the military necessity of the interconnection of different hosts. This type of networks was implanted to avoid the need of a central base of communications. With these networks it was expected to transmit information in a fast and stable way as well as to cover the major part of the possible range without the necessity of having a previous infrastructure.
AD-HOC NETWORKS: CHARACTERISTICS AND PROBLEMS:
The main characteristic of MANETs is that the hosts use wireless medium. In addition, they can move freely. Therefore, the network topology is changing constantly and they do not need any previous infrastructure to be used.
Another characteristic is that the hosts perform as routers.
There are some problems in ad-hoc networks as stated below.
The TCP (Transmission Control Protocol) is a connection oriented protocol, and it is designed for wired networks. In these networks the data loss rate is very small, hence, the reliability is high. When a packet loss is detected in the wired networks it is to a large extent because of the network congestion and TCP reduces the data emission rate. On the other hand, in wireless networks the main problem is not the congestion, but the data loss is because in these networks there is a greater data error rate.
This is why TCP reduces the sending rate when it is actually not necessary, making worst the performance of the MANET.
For a better operation of this protocol there are improvements, for example New Reno [rfc3782], SACKs (Selective Acknowledgment Options) [rfc2018], ELN (Explicit Loss Notifications) [rfc3135] that can be used in the wireless networks to improve the performance of TCP.
The TCP/IP architecture is chosen for the compatibility with the Internet, but this architecture is not the best for MANETs. It has been demonstrated that there are other architectures better to this kind of networks.
Currently, there is no mechanism to realize the auto configuration, as for example in the DHCP (Dynamic Host Configuration Protocol) existing in the fixed or infrastructure networks.
TOPOLOGY AND ROUTING:
The nodes mobility makes the topology change continuously and therefore the nodes create and delete links dynamically.
The routing is not the same as in the wired networks. In wired networks routers are the central elements. In MANETs, there is no such element, but all the nodes can perform as a router, transmitter or receiver element. Hence, the routing is made by the node executing a specific routing protocol for MANETs.
Each time there is a greater tendency to use wireless devices. Thus, there are a lot of applications for these networks. Hereafter are some of the most important.
â€¢ Military applications. The origin of these networks was from the military application. There are a lot of applications in the battle fields difficult to access where there is no previous infrastructure. These networks can be made between tanks, planes, and other mobile elements.
â€¢ Difficult access networks. These applications are realized in places where it is not possible or not economic to install a wired network, because of the ground topology. In this case, it is more convenient to use an Ad-Hoc network.
â€¢ Emergency service. These applications are necessary in natural disaster cases (hurricanes, flooding, etc.), since it is not possible to have at one's disposal a wired network or a previous infrastructure.
â€¢ Mesh networks. The Mesh networks are Ad-Hoc networks where different nodes are connected by a point to point topology, and intermediate nodes are used to reach the destination if this is not in the coverage area. The main application is the communication between big cover areas by means of hops.
In Latin, ad hoc means "for this," further meaning "for this purpose only." MANET is built on the fly where a number of mobile nodes work in cooperation without the engagement of any centralized access point or any fixed infrastructure. Mobile ad hoc network is type of Infrastructure less based networks. It means Ad-hoc wireless networks; however do not need any infrastructure to work. Each node can communicate directly with other nodes, so no access point controlling medium access is necessary. Nodes within an ad hoc network can only communicate if they can reach each other physically, i.e., if they are within each other's radio range or if other nodes can forward the message. Nodes from the two networks shown in Fig 1.1 cannot, therefore, communicate with each other if they are not within the same radio range.
Figure 1.1: Ad Hoc Network
In ad-hoc networks, the complexity of each node is higher because every node has to implement medium access mechanisms, mechanisms to handle hidden or exposed terminal problems, and perhaps priority mechanisms, to provide a certain quality of service. This type of wireless networks exhibits the greatest possible flexibility as it is, for eg. , needed for unexpected meetings, quick replacements of infrastructure or communication scenarios far away from any infrastructure. Consequently, such networks have dynamic, sometimes rapidly changing, random, multi hop topologies which are composed of relatively bandwidth constrained wireless links, limited battery power etc. Therefore, the objective of mobile ad hoc networking is to support robust and efficient operation in mobile wireless networks by incorporating routing functionality into the mobile nodes.
Throughout the history of ad hoc networks they have also been called network on demand or mesh networks. Although given these names they are of similar operational ideas. The ad hoc networks have been on the research desk for a long time but have recently gained more interest. The military applications of such networks have seeded new interest into the research community. The name ad hoc networking is used trying to demilitarize the jargon. Initially this type of networking was researched by the military and was called packet radio.
Mobile ad hoc network nodes are furnished with wireless transmitters and receivers using antennas, which may be highly directional (point-to-point), Omni directional (broadcast), probably steerable, or some combination thereof . At a given point in time, depending on positions of nodes, their transmitter and receiver coverage patterns, communication power levels and co-channel interference levels, a wireless connectivity in the form of a random, multihop graph or "ad hoc" network exists among the nodes. This ad hoc topology may modify with time as the nodes move or adjust their transmission and reception parameters.
Mobile Ad hoc Network has numerous salient characteristics:
Dynamic topologies: Nodes are free to arbitrarily move; i.e. network topology may change randomly and rapidly at unpredictable times.
Bandwidth-constrained variable capacity links: The bandwidth of wireless communications after accounting for the effects of multiple access, fading, noise, and interference conditions is often much less than a radio's maximum transmission rate. The major effect of the relatively low link capacity of MANET is due to the occurrence of congestion in the network. As compared to the wired networks, the bandwidth of links in MANET is significantly lower.
Heterogeneous network: The mobile nodes in ad hoc network have dissimilar radio transmission (downstream) and radio receiving (upstream) frequencies.
Energy-constrained operation: Nodes have limited battery life, processing power and storage capabilities. Hence, limited number of applications and services can be supported by the mobile system, which obviously impedes the technological advancement of highly complex applications.
Limited radio range: MANETs have limited radio range due to limited transmission power.
Limited security: Mobile wireless networks are generally more prone to security threats as compared to fixed networks. There is an increased possibility of eavesdropping, spoofing, and denial-of-service attacks.
These are the various characteristics of mobile ad hoc network which make it different from wired and infrastructure based networks.
1.3 WHEN IS AD HOC NEEDED
There exists numerous occasions where an infrastructure is not available. Now a day the need or use of ad hoc networks is increasing tremendously. Therefore in this section we will present some of the example scenarios where ad hoc networks might come in handy. The basic ideas are possible commercial usages exemplified by Perkins .
1.3.1 Emergency services
Anywhere when there is an emergency there is a need to co-ordinate the rescue personnel. This is commonly solved using hand held or vehicle mounted radios. However, what about the infrastructure that may have been damaged and is no longer in operation? To quickly get things going again the use of ad hoc networks can automatically fix this. This might not be such a big problem in small fires or so, but when larger areas are hit by a natural disaster it can be important to quickly be able to communicate. By using ad hoc networks to set up a network infrastructure it is simply a matter of placing out a couple of mobile routers which makes it easy and fast.
In many situations the need for connecting and exchanging information between participants of a conference or some other meeting is clear. Usually there is a great need for collaboration and since the home network environment is not available there is a need for other solutions. There are usually available networks for the participants to use but this might imply very large round trips for the data using for example Mobile IP [15, 16].
1.3.3 Home networking
Given that the use of wireless computers and appliances keeps on growing in the home environment the need for helping out administrating this is also expanding. Using the techniques of ad hoc networks that configures themselves is truly something that would be of great help. Also, if the computers are used at more places than at home, at the office or school maybe, there is a still larger administrative burden that must be kept down.
1.3.4 Personal area networks
Many objects that are tightly coupled to a single person can take advantage of being connected to each other forming a personal area network. The network itself is most definitely mobile since people tend not to stay around for long in one spot. This makes the use of ad hoc in personal area networks less needed. However, when getting connected to another personal area network (PAN) the connections between people's devices might be wanted. In this case there is definitely a need for ad hoc networking support.
1.3.5 Embedded systems
As more and more machines everywhere is in need for communicating different things to the surroundings a need for ad hoc networking arises. One can think of objects that can respond to changes in the environment and together with other devices perform different scenarios depending on the current context. It might be a toy with built in networking capabilities that can interact with the home computer to lookup some data at the Internet or a connected phone that can turn down the volume of the stereo and TV when there is an incoming call. Some researchers are thinking about ubiquitous computing, where we will have computers connected to each other performing tasks depending on changing environment all around us. It is hard to see every possible use of this technology at the current time, but new services and applications will surely benefit of having ad hoc network support.
Using tiny devices that are able to gather different information such as temperature, concentrations of different chemicals and gases, vibrations, and so on can be of importance in accidents and emergency situations. Constructing these sensors so that when turned on they form an ad hoc network and report back to a well known data collecting node they can be of great importance. For example in the case of a gas leak, instead of sending rescue personnel into the dangerous area these sensors can be dropped from an air plane or helicopter. The use of the gathered data can be helpful in devising a plan to take care of the situation.
In the military field there can of course be a lot of applications for these kinds of data collecting devices.
The following are the advantages of MANET:
They provide access to information and services regardless of geographic position.
These networks can be set up at any place and time.
Mobile users are provided with access to real-time information even when they are away from their home or office.
Setting up a wireless system is easy and fast and it eliminates the need for pulling out the cables through walls and ceilings.
Network can be extended to places which can not be wired.
Wireless networks offer more flexibility and adapt easily to changes in the configuration of the network.
The following are the disadvantages of MANET:
Interference due to weather, other radio frequency devices, or obstructions like walls.
Limited resources and physical security.
Intrinsic mutual trust vulnerable to attacks.
Lack of authorization facilities.
Volatile network topology makes it hard to detect malicious nodes.
The total Throughput is affected when multiple connections exists.
Security protocols for wired networks cannot work for ad hoc networks.
Research Question about Routing Protocols
Our goal in this thesis is to evaluate the performance of Proactive and Reactive WN protocols. These protocols have different behaviors with respect to wireless routing perspective. The main problem is to choose the reliable, efficient and correct routing protocol for WN. The main questions arise for the evaluation of these problems. First question is which routing protocol provides a better performance in Wireless networks? This will give the overall performance of each routing protocol. Secondly, what factors influence the performance of these routing protocols? Finally, we address the main key differences in these routing protocols. To answer all these questions, we will model some of WN scenarios with different parameters. The performance evaluation of these protocols such as, AODV, DSR and OLSR will be carried out with respect to parameters such as delay, network load and throughput. We will simulate these scenarios based on the above mentioned parameters and evaluate from the results which of the protocols is best suitable for WN.
Objective of this research is to find some specific solution of above described problems.
OVERVIEW OF ROUTING PROTOCOL
MANET is a collection of mobile nodes that can communicate with each other without the use of predefined infrastructure or centralized administration, self-organize and rapidly deploy capability. There are some major issues and sub-issues involving in MANET such as routing, multicasting/broadcasting, location service, clustering, mobility management, TCP/UDP, IP addressing, multiple access, radio interface, bandwidth management, power management, security, fault tolerance, and standards of products. Ad hoc is a Latin expression which means "for this purpose". Unlike conventional cellular wireless networks that need an expensive infrastructure to support mobility, MANETs do not need the expensive or wired infrastructure. In some situations, the traditional wireless network that needs a fixed network infrastructure, with base station or access points is not applicable or not suitable to be used e.g. in military missions or temporary networks like conferences. In such situations we need a fast deployment and self-organized network that will be used just for specific purpose for specific period of time. Wireless ad hoc networks can be classified in two types: single-hop and multi-hop networks. When there are no intermediate nodes between the source and the destination we call the network a single-hop network. For example, a laptop communicates with other devices like a PDA or a video camera using Bluetooth. Although in this research we only focus on the On-demand-driven reactive routing protocols. The routing protocols in MANET may generally be categorized as: (i) table-driven/proactive and (2) source-initiated (demand-driven)/reactive. In proactive routing protocols, such as the optimized link state routing (OLSR) , nodes obtain routes by periodic exchange of topology information. In reactive routing protocols, such as the ad hoc on demand distance vector (AODV) protocol [19, 20], nodes find routes only when required. The existing ad hoc routing protocols (AODV) [19, 20], (DSR) , RDMAR, MAC and 802.11 , typically assume a trusted and cooperative environment. As a result, a malicious attacker can readily become a router and disrupt network operations by intentionally disobeying the protocol specifications.
Routing in MANETs
To enable communication within a MANET, a routing protocol is required to establish routes between participating nodes. Because of limited transmission range, multiple network hops may be needed to enable data communication between two nodes in the network. Since MANET is an infrastructure less network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network [1, 3]. There are frequent unpredictable topological changes in these networks, which makes the task of finding and maintaining routes as difficult. Conventional routing protocols based on distance vector or link state algorithms cannot be applied here, since the amount of routing related traffic would waste a large portion of the wireless bandwidth, and such discovered routes would soon become obsolete due to mobility of nodes [3, 4, 5].
In MANETs mobile nodes share the same frequency channel thereby limiting the network capacity. Thus one of the highly desirable properties of a routing protocol for MANETs is that it should be bandwidth efficient.
Other Routing Protocols Suggested for MANETs
Several routing protocols have been proposed for MANETs, which differ in the approach used for discovering a new route and maintaining a know MANET route when nodes move. These protocols can be broadly classified as
(a) proactive routing protocols such as DSDV , FSR , WRP [8, 9], CGSR , GSR  etc.
(b) on-demand routing protocols such as DSR [12, 13, 14], AODV [15, 16], TORA [17, 18], ABR  etc.
In the proactive routing protocols nodes continuously search for routing information within the network, so that when a route is needed it is already available. While in the on-demand routing protocols a route is searched when it is needed. In the proactive routing protocols as compared to the on-demand routing protocols, a constant propagation of routing information is involved, which incurs substantial routing related traffic. Moreover such protocols require each mobile node to maintain routes to each possible target in the MANET, which most likely exceeds the requirements of any node and thus the routing overhead expended in establishing such unrequired routes is wasted. Since bandwidth is a scarce resource in MANETs, these limitations imposed by proactive routing protocols make them less attractive as compared to on-demand routing protocols in a bandwidth constrained MANET environment. ZRP  presents a hybrid behavior of proactive and reactive routing schemes which has advantages and disadvantages of both the schemes, depending on the value chosen for zone radius parameter used to limit the scope of proactive scheme. The on-demand routing protocols suggested for MANETs, such as Dynamic Source Routing (DSR) Protocol [12, 13], Ad-Hoc On-Demand Distance Vector (AODV) Routing [15, 16], Temporally Ordered Routing Algorithm (TORA) [17, 18] and Associability Based Routing (ABR)  etc., basically make use of broadcast based methods for route discovery. They differ in their routing packet formats, data structures maintained by each node, various optimizations applied in route discovery and in their approach for maintaining routes. In a broadcast based method, when an originator node wants to send data packets to a target node, and it does not have a valid route to this target node, it broadcasts a route request packet to its neighbors. These neighbors forward the route request packet to their neighbors and this process goes on until either the target node or an intermediate node with a valid route to target node is located. Each node receiving a particular route request packet broadcasts it only once to its neighbors, and it discards the subsequent receptions of the same route request packet, to minimize routing overhead. Duplicate receptions are detected using sequence numbers associated with route request packets. This method of route discovery floods the entire network with the route request packets thus this method of route discovery is also called Flooding Method. The shortcoming of Flooding Method is that it floods the entire network with the route.
A request even when the target node is just a few hops away from the originator node. An improvement over the Flooding Method, as suggested by the authors of AODV Routing  to reduce the wastage of bandwidth of a MANET, is the Expanding Ring Method. In the Expanding Ring Method, the originator node initially uses a time to live (TTL) field equal to some constant in the route request packet and initiates the route discovery as before. When no valid route is received by the originator node within a certain timeout interval, it increments the TTL field of route request packet and reinitiates route discovery process. This process goes on till a valid route is received by the originator node or up to a maximum number of retries. Expanding Ring Method although better than the Flooding Method in terms of overall bandwidth utilization of MANET, is still not a very efficient method, as it still wastes a lot of bandwidth due to redundant link traversals. In fact Expanding Ring Method is sometimes more expensive than Flooding Method, e.g. when the originator node and target node lie at opposite extremes of the network.
This wastage of bandwidth in case of Flooding Method and Expanding Ring Method is because each participating node normally receives route request packets from all its neighbors and except for the first one all subsequent receptions are redundant. Thus although these methods of route discovery are simple in operation but this simplicity comes at the cost of wasting valuable bandwidth.
Mobile Ad-Hoc Network (MANET) is a collection of mobile nodes (hosts) which communicate with each other via Mobile links either directly or relying on other nodes as routers. Each node moves and operates in a distributed peer-to-peer mode and generating independent data and acting as a router to provide multi-hop communication. MANET is ideally suited for potential applications in civil and military environments, such as responses to hurricane, earthquake, tsunami, terrorism and battlefield conditions. Therefore, security is an important aspect in such critical applications. The operation of MANETs does not depend on pre existing infrastructure or base stations. Network nodes in MANETs are free to move randomly. All network activities such as discovering the topology and delivering data packets have to be executed by the nodes themselves either individually or collectively. The Structure may vary from small, static to a large mobile network. There are two types of MANETs- closed and open. In a closed MANETs all mobile nodes cooperate with each other towards a common goal. In an open MANETs different mobile nodes with different goals share their resources in order to ensure global connectivity. The overall goal of the security solutions for MANETs is to provide security services including authentication, confidentiality, integrity, anonymity and availability to the mobile users. In order to achieve this goal for the security solution should provide complete protection spanning of the entire protocol stack. We can categorize MANETs security in 5 layers, such as Application layer, Transport layer, Network layer, Link layer, and Physical layer. However, we only focus on the network layer, which is related to security issues to protect the ad-hoc routing and forwarding protocols. From the security design perspective the MANETs have no clear line of defense unlikely wired networks that have dedicated routers each mobile node in an ad hoc network may function as a router and forward packets for other peer nodes and Mobile channel is accessible to both legitimate network users and malicious attackers. As a result, the boundary that separates the inside network from the outside world becomes blurred.
ROUTING ATTACKS IN MANETS
The malicious node(s) can attack in MANET using different ways, such as sending fake messages several times, fake routing information, and advertising fake links to disrupt routing operations. In the following subsection, current routing attacks and its countermeasures against MANET protocols are discussed in detail.
Flooding attack - In flooding attack, attacker exhausts the network resources, such as bandwidth and to consume a node's resources, such as computational and battery power or to disrupt the routing operation to cause severe degradation in network performance. For example, in AODV protocol, a malicious node can send a large number of RREQs in a short period to a destination node that does not exist in the network. Because no one will reply to the RREQs, these RREQs will flood the whole network. As a result, all of the node battery power, as well as network bandwidth will be consumed and could lead to denial-of-service. A simple mechanism proposed to prevent the flooding attack in the AODV protocol . In this approach, each node monitors and calculates the rate of its neighbors' RREQ. If the RREQ rate of any neighbor exceeds the predefined threshold, the node records the ID of this neighbor in a blacklist. Then, the node drops any future RREQs from nodes that are listed in the blacklist. The limitation of this approach is that it cannot prevent against the flooding attack in which the flooding rate is below the threshold. Another drawback of this approach is that if a malicious node impersonates the ID of a legitimate node and broadcasts a large number of RREQs, other nodes might put the ID of this legitimate node on the blacklist by mistake. In , the authors show that a flooding attack can decrease throughput by 84 percent. The authors proposed an adaptive technique to mitigate the effect of a flooding attack in the AODV protocol. This technique is based on statistical analysis to detect malicious RREQ floods and avoid the forwarding of such packets. Similar to , in this approach, each node monitors the RREQ it receives and maintains a count of RREQs received from each sender during the preset time period. The RREQs from a sender whose RREQ rate is above the threshold will be dropped without forwarding. Unlike the method proposed in , where the threshold is set to be fixed, this approach determines the threshold based on a statistical analysis of RREQs. The key advantage of this approach is that it can reduce the impact of the attack for varying flooding rates.
Black hole attack - In a black hole attack, a malicious node sends fake routing information, claiming that it has an optimum route and causes other good nodes to route data packets through the malicious one. For example, in AODV, the attacker can send a fake RREP (including a fake destination sequence number that is fabricated to be equal or higher than the one contained in the RREQ) to the source node, claiming that it has a sufficiently fresh route to the destination node. This causes the source node to select the route that passes through the attacker. Therefore, all traffic will be routed through the attacker, and therefore, the attacker can misuse or discard the traffic. Figure 1 shows an example of a black hole attack, where attacker A sends a fake RREP to the source node S, claiming that it has a sufficiently fresher route than other nodes. Since the attacker's advertised sequence number is higher than other nodes' sequence numbers, the source node S will choose the route that passes through node A.
figure1 black hole attack.png
Figure 2.1: Black hole attack on AODV
The route confirmation request (CREQ) and route confirmation reply (CREP) is introduced in  to avoid the black hole attack. In this approach, the intermediate node not only sends RREPs to the source node but also sends CREQs to its next-hop node towards the destination node. After Receiving a CREQ, the next-hop node looks up its cache for a route to the destination. If it has the route, it sends the CREP to the source. Upon receiving the CREP, the source node can confirm the validity of the path by comparing the path in RREP and the one in CREP. If both are matched, the source node judges that the route is correct. One drawback of this approach is that it cannot avoid the black hole attack in which two consecutive nodes work in collusion, that is, when the next-hop node is a colluding attacker sending CREPs that support the incorrect path. In , the authors proposed a solution that requires a source node to wait until a RREP packet arrives from more than two nodes. Upon receiving multiple RREPs, the source node checks whether there is a shared hop or not. If there is, the source node judges that the route is safe. The main drawback of this solution is that it introduces time delay, because it must wait until multiple RREPs arrive. In another attempt , the authors analyzed the black hole attack and showed that a malicious node must increase the destination sequence number sufficiently to convince the source node that the route provided is sufficiently enough. Based on this analysis, the authors propose a statistical based anomaly detection approach to detect the black hole attack, based on differences between the destination sequence numbers of the received RREPs. The key advantage of this approach is that it can detect the attack at low cost without introducing extra routing traffic, and it does not require modification of the existing protocol. However, false positives are the main drawback of this approach due to the nature of anomaly detection.
Link spoofing attack - In a link spoofing attack, a malicious node advertises fake links with non-neighbors to disrupt routing operations. For example, in the OLSR protocol, an attacker can advertise a fake link with a target's two-hop neighbors. This causes the target node to select the malicious node to be its MPR. As an MPR node, a malicious node can then manipulate data or routing traffic, for example, modifying or dropping the routing traffic or performing other types of DoS attacks. Figure 2 shows an example of the link spoofing attack in an OLSR MANET. In the figure, we assume that node A is the attacking node, and node T is the target to be attacked. Before the attack, both nodes A and E are MPRs for node T. During the link spoofing attack, node A advertises a fake link with node T's two-hop neighbor, that is, node D. According to the OLSR protocol, node T will select the malicious node A as its only MPR since node A is the minimum set that reaches node T's two-hop neighbors. By being node T's only MPR, node A can then drop or withhold the routing traffic generated by node T.
FIGURE2 LINK SPOOL ATTACK.png
Figure 2.2: Link spoofing attack
A location information-based detection method is proposed  to detect link spoofing attack by using cryptography with a GPS and a time stamp. This approach requires each node to advertise its position obtained by the GPS and the time stamp to enable each node to obtain the location information of the other nodes. This approach detects the link spoofing by calculating the distance between two nodes that claim to be neighbors and checking the likelihood that the link is based on a maximum transmission range. The main drawback of this approach is that it might not work in a situation where all MANET nodes are not equipped with a GPS. Furthermore, attackers can still advertise false information and make it hard for other nodes to detect the attack. In , the authors show that a malicious node that advertises fake links with a target's two-hop neighbors can successfully make the target choose it as the only MPR. Through simulations, the authors show that link spoofing can have a devastating impact on the target node. Then, the authors present a technique to detect the link spoofing attack by adding two-hop information to a HELLO message. In particular, the proposed solution requires each node to advertise its two-hop neighbors to enable each node to learn complete topology up to three hops and detect the inconsistency when the link spoofing attack is launched. The main advantage of this approach is that it can detect the link spoofing attack without using special hardware such as a GPS or requiring time synchronization. One limitation of this approach is that it might not detect link spoofing with nodes further away than three hops.
Wormhole attack - A wormhole attack  is one of the most sophisticated and severe attacks in MANETs. In this attack, a pair of colluding attackers record packets at one location and replay them at another location using a private high speed network. The seriousness of this attack is that it can be launched against all communications that provide authenticity and confidentiality. Figure2. 3 shows an example of the wormhole attack against a reactive routing protocol. In the figure, we assume that nodes A1 and A2 are two colluding attackers and that node S is the target to be attacked. During the attack, when source node S broadcasts an RREQ to find a route to a destination node
FIGURE 3 WORM HOLE ATTACK.png
Figure 2.3: Wormhole attack on reactive routing
D, its neighbors C and E forward the RREQ as usual. However, node A1, which received the RREQ, forwarded by node C, records and tunnels the RREQ to its colluding partner A2. Then, node A2 rebroadcasts this RREQ to its neighbor H. Since this RREQ passed through a high speed channel, this RREQ will reach node D first. Therefore, node D will choose route D-H-C-S to uncast an RREP to the source node S and ignore the same RREQ that arrived later. As a result, S will select route S-H-D that indeed passed through A1 and A2 to send its data. In , packet leashes are proposed to detect and defend against the wormhole attack. In particular, the authors proposed two types of leashes: temporal leashes and geographical leashes. For the temporal leash approach, each node computes the packet expiration time, te, based on the speed of light c and includes the expiration time, te, in its packet to prevent the packet from traveling further than a specific distance, L. The receiver of the packet checks whether or not the packet expires by comparing its current time and the te in the packet. The authors also proposed TIK, which is used to authenticate the expiration time that can otherwise be modified by the malicious node. The main drawback of the temporal leash is that it requires all nodes to have tightly synchronized clocks. For the geographical leash, each node must know its MANET position and have loosely synchronized clocks. In this approach, a sender of a packet includes its current position and the sending time. Therefore, a receiver can judge neighbor relations by computing distance between itself and the sender of the packet. The advantage of geographic leashes over temporal leashes is that the time synchronization needs not to be highly tight. In , the authors offer protection against a wormhole attack in the OLSR protocol. This approach is based on location information and requires the deployment of a public key infrastructure and time-stamp synchronization between all nodes that is similar to the geographic leashes proposed in . In this approach, a sender of a HELLO message includes its current position and current time in its HELLO message. Upon receiving a HELLO message from a neighbor, a node calculates the distance between itself and its neighbor, based on a position provided in the HELLO message. If the distance is more than the maximum transmission range, the node judges that the HELLO message is highly suspicious and might be tunneled by a wormhole attack. In , the authors propose a statistical analysis of multipath (SAM), which is an approach to detect the wormhole attack by using multipath routing. This approach determines the attack by calculating the relative frequency of each link that appears in all of the obtained routes from one route discovery. In this solution, a link that has the highest relative frequency is identified as the wormhole link. The advantage of this approach is that it introduces limited overhead when applied in multipath routing. However, it might not work in a non-multipath routing protocol, such as a pure AODV protocol.
Colluding misrelay attack - In colluding misrelay attack, multiple attackers work in collusion to modify or drop routing packets to disrupt routing operation in a MANET. This attack is difficult to detect by using the conventional methods such as watchdog and path rater . Consider the case where node A1 forwards routing packets for node T. In the figure, the first attacker A1 forwards routing packets as usual to avoid being detected by node T. However, the second attacker A2 drops or modifies these routing packets. Another authors discuss this type of attack in OLSR protocol and show that a pair of malicious nodes can disrupt up to 100 percent of data packets in the OLSR MANET.
Colluding misrealy attack.png
Figure2.4: Colluding misrealy attack
A conventional acknowledgment-based approach might detect this type of attack in a MANET, especially in a proactive MANET, but because routing packets destined to all nodes in the network require all nodes to return an ACK, this could lead to a large overhead, which is considered to be inefficient. In, the author proposes a method to detect an attack in which multiple malicious nodes attempt to drop packets by requiring each node to tune their transmission power when they forward packets. As an example, the author studies the case where two colluding attackers drop packets. The proposed solution requires each node to increase its transmission power twice to detect such an attack. However, this approach might not detect the attack in which three colluding attackers work in collusion. In general, the main drawback of this approach is that even if we require each node to increase transmission power to be K times, we still cannot detect the attack in which K + 1 attackers work in collusion to drop packets. Therefore, further work must be done to counter against this type of attack efficiently.
2.1 DETAIL OF ROUTING IN AD HOC NETWORKS
AnÂ ad hoc routing protocolÂ is a convention, or standard, that controls how nodes decide which way toÂ routeÂ packetsÂ between computing devices in aÂ mobile ad-hoc network. InÂ ad hoc networks, nodes do not start out familiar with the topology of their networks; instead, they have to discover it. The basic idea is that a new node may announce its presence and should listen for announcements broadcast by its neighbors. Each node learns about nodes nearby and how to reach them, and may announce that it, too, can reach them.
In the case of a mobile ad hoc network the topology is highly dynamic. This leads to quickly changing link states. Some links get broken while other links are created by other pairs of routers as is depicted in figure 1.2 on the following page. In this picture the mobile host 1 (MH1) is moving from the vicinity of MH2. As it gets closer to MH7 and MH8 new links are established to these hosts.
Figure 2.5: Ad Hoc Network of mobile nodes
These characteristics are different from the one that appears in most wired networks. The routing algorithms used in the wired case have problems with topology changes, and if these happen often the problems are just getting worse. Another problem that arises in wireless networks that is not as common in wired routing is the asymmetrical links. That is, one node can reach another but the return path is not the same. Some ad hoc routing algorithms described below handles this and some do not.
Since the advent of Defense Advanced Research Projects Agency (DARPA) packet radio networks in the early 1970s, numerous protocols have been developed for ad hoc mobile networks. Such protocols must deal with the typical limitations of these networks reviewed by E.M. Royer, et. al.. This includes high power consumption, low bandwidth, and high error rates. As shown in Figure 2.6, these routing protocols may generally be categorized as:
â€¢ Source-initiated (demand-driven)
Figure 2.6: Classification of Ad Hoc Routing protocols
Solid lines in this figure represent direct descendants, while dotted lines depict logical descendants. Despite being designed for the same type of underlying network, the characteristics of each of these protocols are quite distinct. The following sections describe the protocols and categorize them according to their characteristics.
2.1.1 Table driven routing protocols
The table-driven approach is similar to the connectionless approach of forwarding data packets, with no regard to when and how frequently such routes are desired. It relies on an underlying routing table update mechanism that involves the constant propagation of routing information. Here, a route to every other node in ad hoc network is always available, regardless of whether or not it is needed. The following sections discuss some of the existing table-driven ad hoc routing protocols.
Destination Sequenced Distance Vector (DSDV)
Wireless Routing Protocol (WRP)
1. Destination Sequenced Distance Vector (DSDV): The Destination- Sequenced Distance-Vector Routing protocol (DSDV) described by C. E. Perkins and P. Bhagwat  is a table-driven algorithm based on the classical Bellman-Ford routing mechanism . The improvements made to the Bellman-Ford algorithm include freedom from loops in routing tables. In the distance vector routing protocol, each mobile node maintains a routing table containing a list of all possible destinations, the number of hops required to reach the destination. However, in addition to the above mentioned data structures, DSDV maintains the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from the new ones and thus avoids the formation of loops. However, the routing table updates are periodically transmitted throughout the network in order to maintain consistency in the table. The routing table updates can be sent in two ways, i.e., full dump type and incremental update type. A full dump type packet sends the complete routing table to its neighbors and can span many packets whereas in an incremental update, only those entries from the routing table are sent that have a metric change since the last update and it must fit in a packet.
From the above discussion, it can be observed that that DSDV needs to address the following two issues:
The control message overhead is O (n*n). This limits the possible size of the ad hoc network.
Excessive memory and bandwidth is caused, as each node needs to maintain a complete list of routes to each node in the network.
2. Wireless Routing Protocol (WRP): The wireless routing protocol (WRP) proposed by S. Murthy and J. J. Garcia-Luna-Aceves , similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. To counter the count-to-infinity problem and to enable faster convergence, it employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node. Since WRP, like DSDV, maintains an up-to-date view of the network, every node has a readily available route to every destination node in the network. It differs from DSDV in table maintenance and in the update procedures. While DSDV maintains only one topology table, WRP uses a set of tables to maintain more accurate information. The tables that are maintained by a node are the following: distance table (DT), routing table (RT), link cost table (LCT), and a message retransmission list (MRL).
In fact, every node in the network maintains four tables: Distance table, Routing table, Link Cost table and Message Retransmission List (MRL):
The Distance table of a node "x" contains the distance of each destination node "y" via each neighbor "z" of "x".
The Routing table of node "x" contains the distance of each destination node "y" from node "x", the predecessor and the successor of node "x" on this path. It also has a tag that identifies whether the entry is a simple path, a loop or invalid. Storing of predecessor and successor in the table helps in detection of loops.
The Link-Cost table contains cost of link to each neighbor of the node and the number of timeouts since an error-free message was received from that neighbor.
The MRL contains information to let a node know which of its neighbor has not acknowledged its update message and to retransmit update message to that neighbor.
Each node exchange routing tables with their neighbors using update messages periodically as well as on link changes. The nodes present on the response list of update message (formed using MRL) are required to acknowledge the receipt of update message. On receiving an update message, the node modifies its distance table and looks for better paths using new information. In case, any new path is found, the information is relayed back to the original nodes so as to update their tables.
The two broad issues identified in WRP can be highlighted as:
A lot of memory is required as each node needs to maintain the routing table of all its direct neighbors, in addition to its own.
The protocol consumes substantial amount of processing for calculating the update to the routing table since all the routing tables from its direct neighbors are used in the calculation.
22.214.171.124 Comparison of various table-driven routing protocols
Based on important characteristics and parameters of routing protocol, the various table-driven ad hoc routing protocols have been compared in Table 2.1. It can be observed that the time and communication complexity of these protocols is very high and requires periodic messaging for determining the up-to-date network topology, thus causing network congestion. The next section discusses several routing protocols based on on-demand-driven approach.
Uni/non uni Protocol
Table 2.1 Comparison of various Table-driven routing protocols
2.1.2 On demand routing protocols
In the on-demand routing protocol, routing information is acquired only when it's needed. No fully consistent routing tables are maintained; hence whenever a node wants to communicate with another node, it initiates a specific route discovery process to obtain a valid route. On average, on-demand protocols have been found to perform better than table-driven protocols, even though there are some scenarios where characteristics of a table-driven solution outperform the on-demand approaches. The various on demand driven based routing protocols are as follows:
Dynamic Source Routing (DSR)
Ad Hoc On Demand Distance Vector Routing (AODV)
1. Dynamic Source Routing Protocol (DSR)
D. B. Johnson and D. A. Maltz prposed DSR , where each mobile node is required to maintain a route cache that contains the source routes of which the mobile is aware. The node updates entries in the route cache as and when it learns about new routes. The protocol consists of two phases: route discovery and route maintenance.
The route discovery process initiates whenever the source node wants to send a packet to some destination. Firstly, the node consults its route cache to determine whether it already has a route to the destination or not. If it finds that an unexpired route to the destination exists, it makes use of this route to send the packet. On the other hand, if the node does not have such a route, it initiates route discovery by broadcasting a route request packet (RREQ). The RREQ contains the address of the source and the destination, and a unique identification number as well. Each node that receives the packet checks whether it knows of a route to the destination. If it does not, it appends its own address to the route record of the packet and forwards the packet along to its neighbors as shown in Fig. 2.4. However, in case it finds a route, a route reply packet (RREP) containing the optimal path is transmitted back to the source node through the shortest route. To limit the number of route requests propagated, a node processes the RREQ only if it has not already seen the packet and its address is not present in the route record of the packet. As the RREQ propagates through the network, the route record is formed. A mobile node only forwards the route request if the node has not yet seen the request and if the node's address does not already appear in the route record so that number of route request packets is controlled. A route reply is generated when either the route request reaches the destination itself, or when it reaches an intermediate node that knows the un-expired route to the destination. By the time the packet reaches either the destination or such an intermediate node, it contains a route record yielding the sequence of hops taken.
Figure 2.7: Creation of record route in DSR
An analysis on discussion on DSR leads to emergence of five major issues:
Inefficient usage of bandwidth: The packet header size increases with route length due to source routing
Node must support parsing of variable packet header size.
Sometimes nodes use stale/incorrect routes due to absence of sequence number
Route caching becomes ineffective with high mobility.
Since a route has to be entirely discovered prior to the actual packet transmission, the initial search latency may degrade the performance of interactive applications (e.g., distributed database queries).
2. Ad hoc On-demand Distance Vector Routing (AODV)
AODV as stated by C. E. Perkins and E. M. Royer  is an augmentation of the DSDV and DSR protocol. It borrows the basic on demand mechanism of route discovery and route maintenance from DSR, besides the use of hop-by-hop routing, sequence number, and periodic beacons from DSDV. AODV minimizes the number of required broadcasts by creating routes only on demand basis. The protocol consists of two basic phases: (a) route discovery and (b) route maintenance.
The route discovery process initiates whenever a node desires to send a packet and does not have a valid route to destination. Firstly, the source node broadcasts a RREQ packet to its neighbors. The neighbors in turn broadcast the packet to their neighbors until it reaches an intermediate node that has route information about the destination or it reaches the destination itself.
Figure 2.8: Route Request (RREQ)
The RREQ packet shown in fig. 2.5 uses sequence number to ensure that the routes are loop free. During the process of forwarding the RREQ packet, intermediate nodes record in their route tables the address of the neighbor from which the first copy of the RREQ is received.
Figure 2.9: Route Reply (RREP)
This information is used to construct the reverse path for the RREP packet. As the RREP packet traverses back to the source, the nodes along the path enter the forward route into their tables. If the source moves, it can easily reinitiate route discovery process to the destination. If one of the intermediate nodes move, then the neighboring realizes the link failure and send a link failure notification to their upstream neighbors and so on until the source node is notified. The source node may then choose to re-initiate route discovery for that destination.
Advantages and limitations
AODV uses a distance vector algorithm with some extensions to provide routing in On-Demand Ad Hoc networks, which has less control message overhead
It provides loop-free routing.
AODV could be used effectively for large Ad Hoc networks not scale well for large networks
126.96.36.199 Comparison of various on-demand-driven routing protocols
Based on the important characteristics and parameters of routing protocol as explained above, the on-demand-driven ad hoc routing protocols have been compared in Table 2.2
Table 2.2 Comparison of various On-demand-driven routing protocols
Uni/non uni Protocol
In the light of above discussion, it can be observed that there is an inevitable need for designing a loop free, effective utilization of battery power and bandwidth, faster route convergence, optimized metrics, robust and scalable routing protocol for ad hoc network. These issues have been considered before proposing later in the thesis an efficient, self adjusting routing protocol having all the desirable properties of routing protocol for high network performance. Recent advancements in portable computing and wireless technologies have opened up exciting possibilities for the future of mobile ad hoc networking.
A Mobile Ad-Hoc Network (MANET) is an infrastructure less collection of mobile nodes that can arbitrarily change their geographic locations such that these networks have dynamic topologies which are composed of bandwidth constrained wireless links. MANET nodes are equipped with wireless transmitters and receivers. At a given time depending on the nodes positions and their transmitter and receiver coverage patterns and transmission power levels, a wireless connectivity in the form of a random, multi hop graph or ad-hoc network exists between the nodes. This ad-hoc topology may change with time as the nodes move or change their transmission and reception parameters . The current applications of MANETs are in defense operations, emergency search and- rescue operations, meetings and conventions and other scenarios where quick sharing of information is desired without any fixed infrastructure available . But in future there could be many more commercial applications of these networks.
Mobile Ad Hoc Networking (MANET) has become an exciting and important technology in recent years because of the rapid proliferation of wireless devices. Providing adequate security measures for MANET is a challenging task. The currently suggested routing protocols cope well with the dynamic topology, but usually offer little or no security measures. No single standard protocol captures common security threats and provides guidelines to make routing protocol secure
The reactive protocols were specifically designed for use in multi-hop wireless mobile ad hoc networks. The REACTIVE protocol does not require any existing network infrastructure or central administration and is completely self-organizing.
Secure Ad hoc Routing
There exist several proposals that attempt to architect a secure routing protocol for ad hoc networks, in order to offer protection against the attacks mentioned in the previous section. These proposed solutions are either completely new stand-alone protocols, or in some cases incorporations of security mechanisms into existing ones. As we will see, the design of these solutions focuses on providing countermeasures against specific attacks, or sets of attacks. The following routing protocols are extension to REACTIVE to provide security.
ARIADNE Reactive Protocols
Ariadne is a secure on-demand ad hoc routing protocol based on REACTIVE proposed by Y. C. Hu, A. Perrig, and D. Johnson . The security of Ariadne relies on the secrecy and authenticity of keys stored in nodes. Ariadne relies on the following keys to be set up, depending on which authentication mechanism is used:
If pair wise shared secret keys are used, we assume a mechanism to set up the necessary n(n+1)/2 keys in a network with n nodes.
If TESLA is used, we assume a mechanism to set up shared secret keys between communicating nodes, and to distribute one authentic public TESLA key for each node.
If digital signatures are used, we assume a mechanism distribute one authentic public key for each node.
The Ariadne protocol also specifies a mechanism for securing route maintenance, which ensures the validity of route error messages concerning broken links in the ad hoc network. A node that generates a route error includes TESLA authentication details in the message. Therefore, every node that forwards the route error towards the destination of the message is able to authenticate it. The intermediate nodes buffer the route error message and its authentication does not take place until the node that generated it discloses the key.
Ariadne provides end-to-end security mechanisms for ad hoc routing. Ariadne utilizes a message authentication code in order to authenticate routing table entries. The most important requirement of Ariadne is the existence of clock synchronization in the ad hoc network. The basic Ariadne protocol can be disrupted by wormhole attacks, but an extension developed by the authors can be utilized to secure against it.
ARAN was proposed by Sanzgiri et al in 2002  , targeting to combat attacks including unauthorized participation, spoofed route signaling, alteration of routing messages, replay attacks, etc. Similar to other secure routing protocols, ARAN is also a security adds on over on-demand routing protocols. It provides authentication, message integrity and non-repudiation as part of minimal security policy for ad hoc environment. ARAN is a security scheme, which can be applied to any on-demand routing protocols. It takes the advantages of PKI based digital signature scheme to provide security features including authentication, message integrity and non-repudiation.
ARAN consists of three stages: a preliminary certification process, a mandatory end-to-end authentication stage and an optional stage providing secure shortest path. To deploy these three stages, ARAN requires the use of a trusted certificate server T and public key cryptography. Each node, before entering the network, must request a certificate from T, and will receive exactly one certificate after securely authenticating their identities to T.
Unauthorized participation: ARAN participants accept only packets that have been signed with a certified key issued by the trusted authority. In practice, many single-hop 802.11 deployments are already using VPN certificates; this is the case on the UMass campus. Mechanisms for authenticating users to a trusted certificate authority are numerous; a significant list is provided by Schneier. The trusted authority is also a single point of failure and attack, however, multiple redundant authorities may be used (e.g., as by Zhou and Haas ). Spoofed Route Signaling: Since only the source node can sign with its own private key, nodes cannot spoof other nodes in route instantiation. Similarly, reply packets include the destination node's certificate and signature, ensuring that only the destination can respond to route discovery. This prevents impersonation attacks where either the source or destination nodes are spoofed.
Fabricated Routing Messages: Messages can be fabricated only by nodes with certificates. In that case, ARAN does not prevent fabrication of routing messages, but it does offer a deterrent by ensuring non-repudiation. A node that continues to inject false messages into the network may be excluded from future route computation.
Alteration of Routing Messages: ARAN specifies that all fields of RDP and REP packets remain unchanged between source and destination. Since both packet types are signed by the initiating node, any alterations in transit would be immediately detected by intermediary nodes along the path, and the altered packet would be subsequently discarded. Repeated instances of altering packets could cause other nodes to exclude the errant node from routing, though that possibility is not considered here. Thus, modification attacks are prevented.
Securing Shortest Paths: We believe there is no way to guarantee that one path is shorter than another in terms of hop count. Tunneling attacks are possible in ARAN as they are in any