Print Email Download

Paid Writing Services

More Free Content

Get Your Own Essay

Order Now

Instant Price

Search for an Essay


Literature Review About AD HOC Wireless Networks Computer Science Essay

Wireless mobile ad hoc network is a marvelous technology which will take over the world of communication in next few decades. It can be applied to verity of fields like military, research, commercial and personal. It does not need fixed infrastructure hence easy to deploy. Ad hoc network is dynamic; network’s topology keeps on changing as nodes are not fixed in one place. Nodes need dynamic routing protocols to forward packets to each other. Destination Sequenced Distance Vector (DSDV), Temporary Ordered Routing Algorithm (TORA), Dynamic Source Routing (DSR) and Ad Hoc On-Demand Distance Vector (AODV) are few such protocols [1].

To increase performance of ad hoc network, nodes should cooperate and trust each other for packet routing. And by default routing protocols will consider all the nodes to collaborate. Node in network performs the role of a host as well as a router. But not all nodes are trustworthy; few factors will lead them to misbehave and drop the packets. Throughput of the network will degrade if misbehaving nodes are included in the route. Adding few processes and technologies over the routing protocols will help in achieving a good ad hoc network.

This literature review is an insight of how to increase throughput and decrease overhead of the ad hoc wireless network.

Routing Algorithms

This literature review mainly deals with two protocols: DSR and AODV. Current section will give an insight of these protocols. Josh, David, David B, Yih-Chun, and Jorjeta [1] say DSR does two things:

Route Discovery

Route Maintenance

To start communication nodes obtain source route by broadcasting ROUTE REQUEST packet through the network. ROUTE REQUEST is then answered with ROUTE REPLY packet by destination or any intermediate node which knows the route to destination. This is route discovery. In route maintenance, the packet sender detects if the network topology has changed. DSR maintains additional information in packet header: nodes through which a packet must pass to reach the destination. This will decrease the additional overhead of maintaining and advertising routing table information for every node.

AODV is combination of DSR and DSDV. It adopts the on-demand routing mechanism of DSR and hop-by-hop routing strategy of DSDV. A node using AODV broadcasts a ROUTE REQUEST message to its neighbors. It is flooded in the network until it reaches destination. The destination generates ROUTE REPLY packet that includes the hops that are necessary for reaching the destination and the sequence number of the destination most recently seen by the node that generates REPLY. [1]

Routing Problems faced my Ad Hoc network

By default ad hoc network uses all nodes for routing and forwarding the packets. But not all nodes are obedient or trustworthy. Nodes that fail to forward packets to other nodes can be designated as misbehaving or malicious or selfish nodes. There can be N number of factors for a node to misbehave. Yih-Chun and Adrina [2] state few of the factors; to save its battery life node simply drops the packet, node has been tampered by an attacker to cause a flawed packet forwarding, the attacker overloads the network with worthless traffic which may lead to memory and energy consumption of the node and when a legitimate transaction requires the resources they are unavailable.

The simulation in [3] shows that the throughput decreased by 16% - 32% in the presence of 10% - 40% misbehaving nodes. But the impact of loss is high on the individual nodes which try to pass the packets through a misbehaving node.

To discover destination routing protocols will flood the whole network with query request packets. The intermediary nodes will broadcast the query packets to its neighbors. The flooding and broadcasting of packets will cause a significant amount of overhead in the network. The increased overhead will reduce throughput of the network [4]. DSR and AODV perform well when compared to the hop-by-hop protocols, DSDV and TORA. But improvising some more technologies on top of them will give robustness and better performance.

Performance level of the path from source to destination decreases drastically even if the path has one misbehaving node [5]. Therefore misbehaving nodes have to be avoided for better performance and throughput. Next section gives different approaches to avoid misbehaving nodes to increase throughput and decrease overhead of the ad hoc wireless network.

approaches

Throughput and overhead are measured in different simulations with nodes moving in two speeds: moderate and high. Sergio, Giuli, Kavin and Mary [3] used watchdog to identify the misbehaving nodes and pathrater to help DSR protocol select the route with no such nodes. The watchdog on a node listens to neighboring nodes’ transactions to check if the packet is forwarded. If the node fails to forward the packets repeatedly it is designated as misbehaving node. The pathrater uses this information to calculate the rate of the path.

Sergio, Giuli, Kavin and Mary [3] noted the effects on the throughput when watchdog reports false positives. From their study they concluded that these techniques improved throughput by 17% in existence of 40% selfish nodes in moderate speed and 27% in high speed.

Figure 1

Fabio, Stefano, and Antonio [6] illustrated the mechanism of watchdog. In Figure 1 solid line represents packet transmission and dotted line represents acknowledgments. After sending a packet to N2, N1 observes if N2 is forwarding the packet to N3. If packet is forwarded N1 will increment the counter for packet sent or else it will conclude that N2 dropped the packet.

Figure 2

Watchdog observes not only its own transmissions but also the transmissions of other nodes within a particular range. In Figure 2 N1 is observing the transaction between N2 and N4. If N2 fails to forward the packet sent by N4 it is blacklisted as a misbehaving node.

Yih-Chun and Adrina [2] say that misbehaving nodes can be avoided by selecting routes depending on the previous successful packet forwarding performances. Feedback on successful packet delivery can be obtained from transport layers’ selective acknowledgment or from end-to-end network layer message. [2] also proposed that misbehaving nodes can be avoided by forwarding the packets only through those nodes which are in trust relationship. Trust relationship can be formed by sharing encrypted keys.

Robert and Samir [4] described how network congestion and routing overhead caused by the flooding technique can be reduced by using preexisting routing history to limit the flooding region. Query localization protocol proposed in [4] assumes that the nodes do not move fast from each other. To estimate the region in which the destination might be present it uses prior routing histories and only that region is flooded with the query packets. Limiting the flood region will a particular region will decrease the overhead caused by the routing protocols.

Fabio, Stefano, and Antonio [6] detected ad hoc network’s misbehaving nodes by using trust model. This model along with watchdog is applied on AODV. The trust model checks the trustworthiness of the nodes by directly studying the actions of the node and by gathering trust values given by other nodes. The models’ detection power is good even in the presence of nodes which give false trust values.

Poonam, Garg and Misra [7] introduced a “trust based multi-path dynamic source routing” (TMDSR) protocol which aims to avoid misbehaving nodes, decrease routing overhead and improve the throughput of ad hoc network. When the route discovery packet reaches the node from which the destination is just one hop away, TMDSR will let the nodes unicast the packet instead of broadcasting it. This will reduce the overhead and increase the throughput of the network.

Poonam, Garg and Misra [7] proposed that “secure and efficient route to destination can be calculated using weighted average of the number of nodes in the route and their trust values." Each node maintains trust table to store the trust values of the neighbor. These trust values are appended to the route discovery packets as it propagates through the network. The destination adds to the response packet the number of nodes in the path through which it received the route discovery packet.

Michal and Isabelle [8] say that the nodes can be bribed to participate in the route. They call it as virtual currency mechanism. The sending nodes have to pay for sending the packets and intermediary node will be rewarded for forwarding those packets. This mechanism is used with routing protocol. Each node in the route puts forward the price it wants to receive. Estimate of the price depends on battery life, load etc. Each proposed price is given a timeout: number of packets it wants to forward. This price and timeout is appended to route reply packet from the destination. The price expires when the counter for number of packets forwarded come to zero.

The path selected by single routing protocol is not always cheap for this reason [8] proposed to use multiple route discovery algorithms. And this is applied to nuggets model. Sprite gives the security for the virtual money from tampering.

Syed, Saroj, Varsha, and Ravi [5] propose Reputation-Trust (RT) system and algorithm. This RT system is applied on watchdog and pathrater system to make it more efficient. Each node of the network maintains a Reputation-Trust table where it stores the reputation and trust values of all local nodes. When a misbehaving node is found the RT system updates the table with the information given by the neighbors and watchdog. This RT table is used by pathrater to help routing protocols to pick a secure path.

Lei, Li, Liu, Zhang, and Linsha [9] proposed a distributed algorithm which detects and punishes the selfish dropping of packets by nodes. In dynamic ad hoc network the topology changes constantly. If a node frequently drops the request packets of other nodes then its own request packet will be dropped by others. This is called tit-for-tat. The only way it can send its packets is by forwarding others’ packets. [9] uses the game theory tool to analyze the performance and effectiveness of the algorithm.

Conclusion

This literature review is about the techniques which are used along with routing protocols to improve the throughput and decrease the overhead of the ad hoc network. In a network by default the routing protocols will consider all nodes to forward the packets but some nodes misbehave by dropping them. Watchdog, pathrater, encryption keys, Query localization, virtual currency, TMDSR, Reputation-Trust model and punishing the misbehaving nodes are few of the techniques which maximize the throughput of the ad hoc network by choosing the path which is free of misbehaving nodes.

Print Email Download

Share This Essay

Did you find this essay useful? Share this essay with your friends and you could win £20 worth of Amazon vouchers. One winner chosen at random each month.

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays

Need help with your essay?

We offer a bespoke essay writing service and can produce an essay to your exact requirements, written by one of our expert academic writing team. Simply click on the button below to order your essay, you will see an instant price based on your specific needs before the order is processed:

Order an Essay - via our secure order system!