22-10-2011, 09:52 PM
Check out the attachment for review document for Caching Strategies Based on Information Density Estimation in Wireless Ad Hoc Networks, IEEE 2011 JAVA PROJECT
22-10-2011, 09:52 PM
17-03-2012, 02:47 PM
Guest
25-03-2012, 11:01 AM
what is the methodology used in this project?pls send the report of methodology.
18-02-2013, 10:18 AM
Caching Strategies Based on Information Density Estimation in Wireless Ad Hoc Networks
[attachment=51258]
Abstract
We address cooperative caching in wireless networks,
where the nodes may be mobile and exchange information in a
peer-to-peer fashion. We consider both cases of nodes with largeand
small-sized caches. For large-sized caches, 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.
INTRODUCTION
PROVIDING information to users on the move is one of the
most promising directions of the infotainment business,
which rapidly becomes a market reality, because infotainment
modules are deployed on cars and handheld devices. The ubiquity
and ease of access of third- and fourth-generation (3G
or 4G) networks will encourage users to constantly look for
content that matches their interests. However, by exclusively
relying on downloading from the infrastructure, novel applications
such as mobile multimedia are likely to overload the
wireless network (as recently happened to AT&T following
the introduction of the iPhone [1]). It is thus conceivable
that a 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 [2].
RELATED WORK
Several papers have addressed content caching and content
replacement in wireless networks. In the following sections, we
review the works that aremost related to this paper, highlighting
the differences with respect to the Hamlet framework that we
propose.
Cooperative Caching
In [9], distributed caching strategies for ad hoc networks are
presented according to which nodes may cache highly popular
content that passes by or record the data path and use it to
redirect future requests. Among the schemes presented in [9],
the approach called HybridCache best matches the operation
and system assumptions that we consider; we thus employ
it as a benchmark for Hamlet in our comparative evaluation.
In [10], a cooperative caching technique is presented and shown
to provide better performance than HybridCache. 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. The
work in [11] 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 networkwide “cooperation zone” parameter. Note
that assuming the presence of a routing protocol can prevent
the adoption of the scheme in [11] in highly mobile networks,
where maintaining network connectivity is either impossible
or more communication expensive than the querying/caching
process. Furthermore, the need of a manual calibration of
the “cooperation zone” makes the scheme hard to configure,
because different environments are considered. Conversely,
Hamlet is self contained and is designed to self adapt to network
environments with different mobility and connectivity features.
Data Replication
Although addressing a different problem, some approaches
to data replication are relevant to the data caching solution
that we propose. One technique of eliminating information
replicas among neighboring nodes is introduced in [21], which,
unlike Hamlet, requires knowledge of the information access
frequency and periodic transmission of control messages to
coordinate the nodes’ caching decisions. In [5], the authors
propose a replication scheme that aims at having every node
close to a copy of the information and analyze its convergence
time. However, unlike Hamlet, the scheme implies a significant
overhead and an exceedingly high convergence time, thus
making it unsuitable for highly variable networks. Finally, the
work in [22] adopts a cross-layer approach to data replication
in mobile ad hoc networks, where network-layer information on
the node movement path helps to trigger the replication before
network partitioning occurs.
SYSTEM OUTLINE AND ASSUMPTIONS
Hamlet is a fully distributed caching strategy for wireless
ad hoc networks whose nodes exchange information items in
a peer-to-peer fashion. In particular, we address a mobile ad
hoc network whose nodes may be resource-constrained devices,
pedestrian users, or vehicles on city roads. Each node runs an
application to request and, possibly, cache desired information
items. Nodes in the network retrieve information items from
other users that temporarily cache (part of) the requested items
or from one or more gateway nodes, which can store content or
quickly fetch it from the Internet.
We assume a content distribution system where the following
assumptions hold: 1) A number I of information items is
available to the users, with each item divided into a number C
of chunks; 2) user nodes can overhear queries for content and
relative responses within their radio proximity by exploiting the
broadcast nature of the wireless medium; and 3) user nodes
can estimate their distance in hops from the query source and
the responding node due to a hop-count field in the messages.
Although Hamlet can work with any system that satisfies the
aforementioned three generic assumptions, for concreteness,
we detail the features of the specific content retrieval system
that we will consider in the remainder of this paper.
HAMLET FRAMEWORK
The Hamlet framework allows wireless users to take caching
decisions on content that they have retrieved from the network.
The process that we devise allows users to take such decisions
by leveraging a node’s local observation, i.e., the node’s
ability to overhear queries and information messages on the
wireless channel. In particular, for each information item, a
node records the distance (in hops) of the node that issues the
query, i.e., where a copy of the content is likely to be stored,
and the distance of the node that provides the information.
Based on such observations, the node computes an index of the
information presence in its proximity for each of the I items.
Small-Sized Caches: Content Replacement
When equipped with a small-sized cache, nodes cannot store
all content that they request but are forced to choose which
items to keep and which items to discard every time newly retrieved
data fill up their memory. In this case, computing cache
drop times is clearly not a solution, because the lingering of
items in cache is primarily determined by the rate of reception
of new content. Therefore, in the presence of limited dedicated
storage resources, we exploit the information presence estimate
to define a content replacement policy that favors a balanced
distribution of data over the network so that all content is as
“close” as possible to a requesting node.
SIMULATION SCENARIOS AND METRICS
We tested the performance of Hamlet through ns2 simulations
under the following three different wireless scenarios:
1) a network of vehicles that travel in a city section (referred to
as City); 2) a network of portable devices carried by customers
who walk in a mall (Mall); and 3) a network of densely and
randomly deployed nodes with memory limitations (memoryconstrained
nodes). The three scenarios are characterized by
different levels of node mobility and network connectivity.
In the City scenario, as depicted in Fig. 4, vehicle movement
is modeled by the intelligent driver model with intersection
management (IDM-IM), which takes into account car-to-car
interactions and stop signs or traffic lights [27]. We simulated
a rather sparse traffic, with an average vehicle density of
15 veh/km over a neighborhood of 6.25 km2. The mobility
model settings, forcing vehicles to stop and queue at intersections,
led to an average vehicle speed of about 7 m/s (i.e.,
25 km/h). We set the radio range to 100 m in the vehicular
scenario, and by analyzing the network topology during the
simulations, we observed an average link duration of 24.7 s and
a mean of 45 disconnected node clusters concurrently present
over the road topology. The City scenario is thus characterized
by scattered connectivity and high node mobility.
EVALUATION WITH SMALL-SIZED CACHES
We now evaluate the performance of Hamlet in a network
where a node cache can accommodate only a small portion of
the data that can be retrieved in the network. As an example,
consider a network of low-cost robots that are equipped with
sensor devices, where maps that represent the spatial and temporal
behavior of different phenomena may be needed by the
nodes and have to be cached in the network. We thus consider
the memory-constrained scenario introduced in Section V and
employ the Hamlet framework to define a cache replacement
strategy, as detailed in Section IV.
In such a scenario, the caching dynamics of the different information
items become strongly intertwined. Indeed, caching
an item often implies discarding different previously stored
content, and as a consequence, the availability of one item in
the proximity of a node may imply the absence of another item
in the same area. Thus, in our evaluation, it is important to consider
a large number of items, as well as to differentiate among
these items in terms of popularity. We consider an overall pernode
query rate Λ = 0.1 and sets of several hundreds of items.
We assume that popularity levels qi are distributed according
to the Zipf law, which has been shown to fit popularity curves
of content in different kinds of networks [29].
CONCLUSION
We have introduced Hamlet, which is a caching strategy for
ad hoc networks whose nodes exchange information items in
a peer-to-peer fashion. Hamlet is a fully distributed scheme
where each node, upon receiving a 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 node’s proximity, whose estimation
does not cause any additional overhead to the information
sharing system. We showed that, due to Hamlet’s caching of
information that is not held by nearby nodes, the solving probability
of information queries is increased, the overhead traffic
is reduced with respect to benchmark caching strategies, and
this result is consistent in vehicular, pedestrian, and memoryconstrained
scenarios.
[attachment=51258]
Abstract
We address cooperative caching in wireless networks,
where the nodes may be mobile and exchange information in a
peer-to-peer fashion. We consider both cases of nodes with largeand
small-sized caches. For large-sized caches, 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.
INTRODUCTION
PROVIDING information to users on the move is one of the
most promising directions of the infotainment business,
which rapidly becomes a market reality, because infotainment
modules are deployed on cars and handheld devices. The ubiquity
and ease of access of third- and fourth-generation (3G
or 4G) networks will encourage users to constantly look for
content that matches their interests. However, by exclusively
relying on downloading from the infrastructure, novel applications
such as mobile multimedia are likely to overload the
wireless network (as recently happened to AT&T following
the introduction of the iPhone [1]). It is thus conceivable
that a 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 [2].
RELATED WORK
Several papers have addressed content caching and content
replacement in wireless networks. In the following sections, we
review the works that aremost related to this paper, highlighting
the differences with respect to the Hamlet framework that we
propose.
Cooperative Caching
In [9], distributed caching strategies for ad hoc networks are
presented according to which nodes may cache highly popular
content that passes by or record the data path and use it to
redirect future requests. Among the schemes presented in [9],
the approach called HybridCache best matches the operation
and system assumptions that we consider; we thus employ
it as a benchmark for Hamlet in our comparative evaluation.
In [10], a cooperative caching technique is presented and shown
to provide better performance than HybridCache. 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. The
work in [11] 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 networkwide “cooperation zone” parameter. Note
that assuming the presence of a routing protocol can prevent
the adoption of the scheme in [11] in highly mobile networks,
where maintaining network connectivity is either impossible
or more communication expensive than the querying/caching
process. Furthermore, the need of a manual calibration of
the “cooperation zone” makes the scheme hard to configure,
because different environments are considered. Conversely,
Hamlet is self contained and is designed to self adapt to network
environments with different mobility and connectivity features.
Data Replication
Although addressing a different problem, some approaches
to data replication are relevant to the data caching solution
that we propose. One technique of eliminating information
replicas among neighboring nodes is introduced in [21], which,
unlike Hamlet, requires knowledge of the information access
frequency and periodic transmission of control messages to
coordinate the nodes’ caching decisions. In [5], the authors
propose a replication scheme that aims at having every node
close to a copy of the information and analyze its convergence
time. However, unlike Hamlet, the scheme implies a significant
overhead and an exceedingly high convergence time, thus
making it unsuitable for highly variable networks. Finally, the
work in [22] adopts a cross-layer approach to data replication
in mobile ad hoc networks, where network-layer information on
the node movement path helps to trigger the replication before
network partitioning occurs.
SYSTEM OUTLINE AND ASSUMPTIONS
Hamlet is a fully distributed caching strategy for wireless
ad hoc networks whose nodes exchange information items in
a peer-to-peer fashion. In particular, we address a mobile ad
hoc network whose nodes may be resource-constrained devices,
pedestrian users, or vehicles on city roads. Each node runs an
application to request and, possibly, cache desired information
items. Nodes in the network retrieve information items from
other users that temporarily cache (part of) the requested items
or from one or more gateway nodes, which can store content or
quickly fetch it from the Internet.
We assume a content distribution system where the following
assumptions hold: 1) A number I of information items is
available to the users, with each item divided into a number C
of chunks; 2) user nodes can overhear queries for content and
relative responses within their radio proximity by exploiting the
broadcast nature of the wireless medium; and 3) user nodes
can estimate their distance in hops from the query source and
the responding node due to a hop-count field in the messages.
Although Hamlet can work with any system that satisfies the
aforementioned three generic assumptions, for concreteness,
we detail the features of the specific content retrieval system
that we will consider in the remainder of this paper.
HAMLET FRAMEWORK
The Hamlet framework allows wireless users to take caching
decisions on content that they have retrieved from the network.
The process that we devise allows users to take such decisions
by leveraging a node’s local observation, i.e., the node’s
ability to overhear queries and information messages on the
wireless channel. In particular, for each information item, a
node records the distance (in hops) of the node that issues the
query, i.e., where a copy of the content is likely to be stored,
and the distance of the node that provides the information.
Based on such observations, the node computes an index of the
information presence in its proximity for each of the I items.
Small-Sized Caches: Content Replacement
When equipped with a small-sized cache, nodes cannot store
all content that they request but are forced to choose which
items to keep and which items to discard every time newly retrieved
data fill up their memory. In this case, computing cache
drop times is clearly not a solution, because the lingering of
items in cache is primarily determined by the rate of reception
of new content. Therefore, in the presence of limited dedicated
storage resources, we exploit the information presence estimate
to define a content replacement policy that favors a balanced
distribution of data over the network so that all content is as
“close” as possible to a requesting node.
SIMULATION SCENARIOS AND METRICS
We tested the performance of Hamlet through ns2 simulations
under the following three different wireless scenarios:
1) a network of vehicles that travel in a city section (referred to
as City); 2) a network of portable devices carried by customers
who walk in a mall (Mall); and 3) a network of densely and
randomly deployed nodes with memory limitations (memoryconstrained
nodes). The three scenarios are characterized by
different levels of node mobility and network connectivity.
In the City scenario, as depicted in Fig. 4, vehicle movement
is modeled by the intelligent driver model with intersection
management (IDM-IM), which takes into account car-to-car
interactions and stop signs or traffic lights [27]. We simulated
a rather sparse traffic, with an average vehicle density of
15 veh/km over a neighborhood of 6.25 km2. The mobility
model settings, forcing vehicles to stop and queue at intersections,
led to an average vehicle speed of about 7 m/s (i.e.,
25 km/h). We set the radio range to 100 m in the vehicular
scenario, and by analyzing the network topology during the
simulations, we observed an average link duration of 24.7 s and
a mean of 45 disconnected node clusters concurrently present
over the road topology. The City scenario is thus characterized
by scattered connectivity and high node mobility.
EVALUATION WITH SMALL-SIZED CACHES
We now evaluate the performance of Hamlet in a network
where a node cache can accommodate only a small portion of
the data that can be retrieved in the network. As an example,
consider a network of low-cost robots that are equipped with
sensor devices, where maps that represent the spatial and temporal
behavior of different phenomena may be needed by the
nodes and have to be cached in the network. We thus consider
the memory-constrained scenario introduced in Section V and
employ the Hamlet framework to define a cache replacement
strategy, as detailed in Section IV.
In such a scenario, the caching dynamics of the different information
items become strongly intertwined. Indeed, caching
an item often implies discarding different previously stored
content, and as a consequence, the availability of one item in
the proximity of a node may imply the absence of another item
in the same area. Thus, in our evaluation, it is important to consider
a large number of items, as well as to differentiate among
these items in terms of popularity. We consider an overall pernode
query rate Λ = 0.1 and sets of several hundreds of items.
We assume that popularity levels qi are distributed according
to the Zipf law, which has been shown to fit popularity curves
of content in different kinds of networks [29].
CONCLUSION
We have introduced Hamlet, which is a caching strategy for
ad hoc networks whose nodes exchange information items in
a peer-to-peer fashion. Hamlet is a fully distributed scheme
where each node, upon receiving a 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 node’s proximity, whose estimation
does not cause any additional overhead to the information
sharing system. We showed that, due to Hamlet’s caching of
information that is not held by nearby nodes, the solving probability
of information queries is increased, the overhead traffic
is reduced with respect to benchmark caching strategies, and
this result is consistent in vehicular, pedestrian, and memoryconstrained
scenarios.