Caching Strategies Based on Information Density Estimation in Wireless Ad Hoc Networks5(2011)

ABSTRACT:

Data caching strategy for ad hoc networks whose nodes exchange information items in a peer-to-peer fashion. Data caching is a fully distributed scheme where each node, upon receiving requested information, determines the cache drop time of the information or which content to replace to make room for the newly arrived information. These decisions are made depending on the perceived “presence” of the content in the nodes proximity, whose estimation does not cause any additional overhead to the information sharing system.

We devise a strategy where nodes, independent of each other, decide whether to cache some content and for how long. In the case of small-sized caches, we aim to design a content replacement strategy that allows nodes to successfully store newly received information while maintaining the good performance of the content distribution system. Under both conditions, each node takes decisions according to its perception of what nearby users may store in their caches and with the aim of differentiating its own cache content from the other nodes’.

The result is the creation of content diversity within the nodes neighborhood so that a requesting user likely finds the desired information nearby. We simulate our caching algorithms in different ad hoc network scenarios and compare them with other caching schemes, showing that our solution succeeds in creating the desired content diversity, thus leading to a resource-efficient information access.

PROJECT PURPOSE:

Peer-to-peer system could come in handy, if used in conjunction with cellular networks, to promote content sharing using ad hoc networking among mobile users. For highly popular content, peer-to-peer distribution can, indeed, remove bottlenecks by pushing the distribution from the core to the edge of the network.

However, a cache-all-you-see approach is unfeasible, because it would swamp node storage capacity with needless data that were picked up on the go several techniques of efficiently caching information in wireless ad hoc networks.

PROJECT SCOPE: 

However, the solution that was proposed is based on the formation of an overlay network composed of “mediator” nodes, and it is only fitted to static connected networks with stable links among nodes. These assumptions, along with the significant communication overhead needed to elect “mediator” nodes, make this scheme unsuitable for the mobile environments that we address. A complete framework for information retrieval and caching in mobile ad hoc networks, and it is built on an underlying routing protocol and requires the manual setting of a network wide “cooperation zone” parameter. Note that assuming the presence of a routing protocol can prevent the adoption of the scheme in in highly mobile networks.

PRODUCT FEATURES:

v  However, our simulations over a wide range of network and application parameters show that the performance of the caching algorithms.

v  Presents a distributed implementation based on an approximation algorithm for the problem of cache placement of multiple data items under memory constraint.

v  The result is the creation of content diversity within the nodes neighborhood so that a requesting user likely finds the desired information nearby.

v  We simulate our caching algorithms in different ad hoc network scenarios and compare them with other caching schemes, showing that our solution succeeds in creating the desired content diversity, thus leading to a resource-efficient information access.

INTRODUCTION:

Ad hoc networks are multi hop wireless networks of small computing devices with wireless interfaces. The computing devices could be conventional computers (for example, PDA, laptop, or PC) or backbone routing platforms or even embedded processors such as sensor nodes. The problem of optimal placement of caches to reduce overall cost of accessing data is motivated by the following two defining characteristics of ad hoc networks. First, the ad hoc networks are multi hop networks without a central base station. Thus, remote access of information typically occurs via multi hop routing, which can greatly benefit from caching to reduce access latency. Second, the network is generally resource constrained in terms of channel bandwidth or battery power in the nodes. Caching helps in reducing communication, this results in savings in bandwidth, as well as battery energy. The problem of cache placement is particularly challenging when each network node has a limited memory to cache data items.

In this paper, our focus is on developing efficient caching techniques in ad hoc networks with memory limitations. Research into data storage, access, and dissemination techniques in ad hoc networks is not new. In particular, these mechanisms have been investigated in connection with sensor networking peer-to-peer networks mesh networks world wide Web and even more general ad hoc networks. However, the presented approaches have so far been somewhat “ad hoc” and empirically based, without any strong analytical foundation. In contrast, the theory literature abounds in analytical studies into the optimality properties of caching and replica allocation problems. However, distributed implementations of these techniques and their performances in complex network settings have not been investigated. It is even unclear whether these techniques are amenable to efficient distributed implementations.

Our goal in this paper is to develop an approach that is both analytically tractable with a provable performance bound in a centralized setting and is also amenable to a natural distributed implementation. In our network model, there are multiple data items; each data item has a server, and a set of clients that wish to access the data item at a given frequency. Each node carefully chooses data items to cache in its limited memory to minimize the overall access cost. Essentially, in this article, we develop efficient strategies to select data items to cache at each node. In particular, we develop two algorithms—a centralized approximation algorithm, which delivers a 4-approximation (2-approximation for uniform size data items) solution, and a localized distributed algorithm, which is based on the approximation algorithm and can handle mobility of nodes and dynamic traffic conditions. Using simulations, we show that the distributed algorithm performs very close to the approximation algorithm. Finally, we show through extensive experiments on ns2 that our proposed distributed algorithm performs much better than a prior approach over a broad range of parameter values. Ours is the first work to present a distributed implementation based on an approximation algorithm for the general problem of cache placement of multiple data items under memory constraint.

Data caching strategy for ad hoc networks whose nodes exchange information items in a peer-to-peer fashion. Data caching is a fully distributed scheme where each node, upon receiving requested information, determines the cache drop time of the information or which content to replace to make room for the newly arrived information. These decisions are made depending on the perceived “presence” of the content in the nodes proximity, whose estimation does not cause any additional overhead to the information sharing system.

We devise a strategy where nodes, independent of each other, decide whether to cache some content and for how long. In the case of small-sized caches, we aim to design a content replacement strategy that allows nodes to successfully store newly received information while maintaining the good performance of the content distribution system. Under both conditions, each node takes decisions according to its perception of what nearby users may store in their caches and with the aim of differentiating its own cache content from the other nodes’. The result is the creation of content diversity within the nodes neighborhood so that a requesting user likely finds the desired information nearby. We simulate our caching algorithms in different ad hoc network scenarios and compare them with other caching schemes, showing that our solution succeeds in creating the desired content diversity, thus leading to a resource-efficient information access.

SYSTEM ANALYSIS:

PROBLEM DEFINITION:

Mobile environment can be classified as message-based, directory-based, hash based, or router-based data source is, Hybrid Cache might not be a good option.

The cache array routing protocol is the most notable hash based cooperative caching protocol.

EXISTING SYSTEM:

v  Existing cooperative caching schemes for the Web environment can be classified as message-based, directory-based, hash based, or router-based.

v  The cache array routing protocol is the most notable hash based cooperative caching protocol. The rationale behind CARP constitutes load distribution by hash routing among Web proxy cache arrays.

v  A mobile node doesn’t know whether the data source or some other nodes serve its request. If multiple data sources exist, or if the mobile node doesn’t know where the data source is, Hybrid Cache might not be a good option.

v  In addition, caching nodes outside the path between the requesting node and the data source might not be able to share cache information with the requesting node.

LIMITATIONS OF EXISTING SYSTEM:

v  Existing cooperative caching schemes for the Web environment can be classified as message-based, directory-based, hash based, or router-based.

v  The cache array routing protocol is the most notable hash based cooperative caching protocol. The rationale behind CARP constitutes load distribution by hash routing among Web proxy cache arrays.

PROPOSED SYSTEM:

v            We simulate our caching algorithms in different ad hoc network scenarios and compare them with other caching schemes, showing that our solution succeeds in creating the desired content diversity, thus leading to a resource-efficient information access.

v  Data caching strategy for ad hoc networks whose nodes exchange information items in a peer-to-peer fashion. These decisions are made depending on the perceived “presence” of the content in the nodes proximity, whose estimation does not cause any additional overhead to the information sharing system.

v  However, the solution that was proposed is based on the formation of an overlay network composed of “mediator” nodes, and it is only fitted to static connected networks with stable links among nodes.

v  We proposes a complete framework for information retrieval and caching in mobile ad hoc networks, and it is built on an underlying routing protocol and requires the manual setting of a network wide “Caching zone” These assumptions, along with the significant communication overhead needed to elect “mediator” nodes, make this scheme unsuitable for the mobile environments.

ADVANTAGES OF PROPOSED SYSTEM:

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage.

Data for information retrieval and caching in mobile ad hoc networks, and it is built on an underlying routing protocol and requires the manual setting of a network wide “Caching zone”

MODULES ANALYZED:

According to the analysis three modules has been traced out in the design of work.  The modules are as follows.

1. SELF-ORGANIZING
2. SELF-ADDRESSING (MANET)
3. INTEGRATED CACHE-ROUTING
4. LOCALIZED CACHING POLICY
5. DISTRIBUTED CACHING ALGORITHM

MODULE DESCRIPTION:

SELF-ORGANIZING:

Multiple Data’s for cache placement of multiple data items in ad hoc networks. In the first approach, each node caches the items most frequently accessed by itself; the second approach eliminates replications among neighboring nodes introduced by the first approach; the third approach require one or more “central” nodes to gather neighborhood information and determine caching placements. The first two approaches are largely localized, and hence, would fare very badly when the percentage of client nodes in the network is low, or the access frequencies are uniform. In other related works, discuss placement of “transparent” caches in tree networks.

SELF-ADDRESSING:

A multi-hop ad hoc network can be represented as an undirected the nodes in the network and E are the set of weighted edges in the graph. Two network nodes that can communicate directly with each other are connected by an edge in the graph. The edge weight may represent a link metric such as loss rate, delay, or transmission power. For the cache placement problem addressed in this article, there are multiple data items and each data item is served by its server (a network node may act as a server for more than one data items). Each network node has limited memory and can cache multiple data items subject to its memory capacity limitation. The objective of our cache placement problem is to minimize the overall access cost. Below, we give a formal definition of the cache placement problem addressed in this system.

INTEGRATED CACHE-ROUTING:

• Nearest-caching tables can be used in conjunction with any underlying routing protocol to reach the nearest cache node, as long as the distances to other nodes are maintained by the routing protocol.

• However, note that maintaining cache-routing tables instead of nearest-cache tables and routing tables doesn’t offer any clear advantage in terms of number of messages transmissions.

• We could maintain the integrated cache-routing tables in the similar vein as routing tables are maintained in mobile ad hoc networks. Alternatively, we could have the servers periodically broadcast the latest cache lists. In our simulations, we adopted the latter strategy, since it precludes the need to broadcast Add Cache and Delete Cache messages to some extent.

LOCALIZED CACHING POLICY:

• The caching policy of DCA is as follows. Each node computes benefit of data items based on its “local traffic” observed for a sufficiently long time. The local traffic of a node i includes its own local data requests, nonlocal data requests to data items cached at i, and the traffic that the node i is forwarding to other nodes in the network.

• A node decides to cache the most beneficial (in terms of local benefit per unit size of data item) data items that can fit in its local memory. When the local cache memory of a node is full, the following cache replacement policy is used.

• In particular, a data item is newly cached only if its local benefit is higher than the benefit threshold, and a data item replaces a set of cached data items only if the difference in their local benefits is greater than the benefit threshold.

HARDWARE AND SOFTWARE REQUIREMENTS:

HARDWARE REQUIREMENTS:

•         System                        :           Pentium IV 2.4 GHz.

•         Hard Disk                   :           40 GB.

•         Floppy Drive   :           1.44 Mb.

•         Monitor           :           15 VGA Colour.

•         Mouse             :           Logitech.

•         Ram                 :           512 Mb.

SOFTWARE REQUIREMENTS:

•         Operating system        :  Windows XP.

•         Coding Language       :  JDK 1.6

•         Tools                           :  Eclipse 3.3