11-12-2012, 06:27 PM
MINIMUM DISTANCE PACKET FORWARDING FOR SEARCH APPLICATIONS IN MOBILE ADHOC NETWORKS
MINIMUM DISTANCE PACKET.doc (Size: 2.33 MB / Downloads: 48)
ABSTRACT
This paper introduces a message forwarding algorithm for search applications within mobile ad hoc networks that is based on the concept of selecting the nearest node from a set of designated nodes. The algorithm, which is called Minimum Distance Packet Forwarding (MDPF), uses routing information to select the node with the minimum distance. The goal of the proposed algorithm is to minimize the average number of hops taken to reach the node that holds the desired data. Numerical analysis and experimental evaluations using the network simulation software ns2 were performed to derive the lower and upper bounds of the confidence interval
for the mean hop count between the source node of the data request, on one hand, and the node that holds the desired data and the last node in the set of search nodes, on the other hand. In the experimental evaluation, the performance of MDPF was compared to that of Random Packet Forwarding (RPF) and Minimal Spanning Tree Forwarding (MSTF). The results agreed with the numerical analysis results and demonstrated that MDPF offers significant hop count savings and smaller delays when compared to RPF and MSTF.
INTRODUCTION
In a Mobile Ad Hoc Network (MANET), mobile devices (nodes) may be spread over a large area where access to external data is achieved through one or more access points (APs). However, not all nodes have a direct link with these APs. Instead, they rely on other nodes that act as routers to reach them. In certain situations, the APs may be located at the extremities of the MANET, where reaching them could be costly in terms of delay, power consumption, and bandwidth utilization. Additionally, the access point may connect to a costly resource (e.g., a satellite link), or an external network that is susceptible to intrusion. For such reasons and others that concern data availability and response time, MANET applications should check for the existence of the desired data inside the network before attempting to connect to the external data source. An example would be a node that is searching for data that have been requested before by other nodes and are now cached and available to the rest of the nodes. Another example is where there is a group of nodes that have data which may be of interest to other nodes and are willing to share them. These scenarios and others suggest that efficient data search techniques be developed for allowing mobile nodes to find the desired data if it exists in the MANET quickly and with minimum power consumption. Given how ad hoc wireless networks work, searching performance relies on the efficiency of employed routing strategies. Actually, one the biggest challenge in MANETS lies in the creation of efficient routing techniques [1].
Routing protocols are responsible for finding an efficient path between any two nodes in the network that wish to communicate, and for routing data messages along this path. The path must be chosen so that network throughput is maximized and message delay and other undesirable events are minimized. Two main types of routing protocols exist: source routing and destination routing. Destination routing itself is classified into two types: distance-vector routing, used in the RIP Internet protocol [2], and link-state routing, used in the OSPF Internet protocol [3]. Relevant to our work are the Destination-Sequenced Distance Vector (DSDV) and the Ad hoc On-demand Distance Vector (AODV) protocols, which are distance-vector routing protocols designed for MANET environments. With such protocols, a node maintains a routing table and a distance vector. The table contains the neighbor along the shortest path to each destination in the network, while the vector has the distance (number of hops) of this path. In high mobility scenarios, the paths from sources to destinations will become non optimal (i.e., not the shortest paths) until the routing tables are updated.
FRAMEWORK OVERVIEW
The idea behind MDPF is to use routing table information for visiting nodes in the order of shortest distance (hop counts). As implied, this requires valid routing information, which could be handled through a proactive routing protocol such as the DSDV protocol or an on-demand reactive routing protocol, like AODV. We make the assumption that the set of nodes that hold the search information is known to all nodes in the wireless network, and we refer to these nodes as the search nodes, or SNs. We emphasize though that a requesting node which is interested in a particular data item does not usually know which specific SN holds the location of the data item, and therefore, it must search for it in the SNs.