[attachment=11520]
ABSTRACT
Abstract—Data caching can significantly improve the efficiency of information access in a wireless ad hoc twork by reducing theaccess latency and bandwidth usage. wever, designing efficient distributed caching algorithms is ontrivial when network nodeshave limited memory. In this article, we consider the cache placement problem of nimizing total data access cost in ad hoc networkswith multiple data items and nodes with limited memory pacity. The above optimization problem is known to be NP-hard. Definingbenefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers asolution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenableto localized distributed implementation, which is shown via simulations to perform close to the approximation lgorithm. Our distributedalgorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) anddemonstrate that it significantly outperforms another existing caching echnique (by Yin and Cao [33]) in all important performancemetrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller
INTRODUCTION
AD hoc networks are multihop wireless networks ofsmall computing devices with wireless interfaces. Thecomputing devices could be conventional computers (forexample, PDA, laptop, or PC) or backbone routing platformsor even embedded processors such as sensor nodes.The problem of optimal placement of caches to reduceoverall cost of accessing data is motivated by the followingtwo defining characteristics of ad hoc networks. First, the adhoc networks are multihop networks without a central basestation. Thus, remote access of information typically occursvia multihop routing, which can greatly benefit from
caching to reduce access latency. Second, the network isgenerally resource constrained in terms of channel bandwidthor battery power in the nodes. Caching helps in
reducing communication, which results in savings inbandwidth, as well as battery energy. The problem of cacheplacement is particularly challenging when each networknode 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 [14], [26], peer-to-peer networks [1
[18], mesh networks [17], world wide Web [25], and even
more general ad hoc networks [12], [33]. 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 (see, for example, [3]).
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 approachthat is both analytically tractable with a provable performancebound in a centralized setting and is also amenableto 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 uniformsize
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 [10] 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
4.0 Modules Analyzed
According to the analysis three modules has been traced out in the design of work. The modules are as follows.
• Self-Organizing
• Self-Addressing
• Self-Routing
• delete the path update table in each node
4.2 Proposed System
 Each node cache the items most frequently accessed by itself.
 Eliminate replications among neighboring nodes
 Creation of stable groups to gather neighborhood inform and determine caching placements.
 Each node act as a server
 Server maintains nearest cache node and
 Server nearest cache node by using routing protocol
 First save data item on local space
 IF any other items are exist that will be replace.