Balancing the Tradeoffs between Query Delay and Data Availability in MANETs
[
attachment=56101]
Abstract
In mobile ad hoc networks (MANETs), nodes move freely and link/node failures are common, which leads to frequent
network partitions. When a network partition occurs, mobile nodes in one partition are not able to access data hosted by nodes
in other partitions, and hence significantly degrade the performance of data access. To deal with this problem, we apply data
replication techniques. Existing data replication solutions in both wired or wireless networks aim at either reducing the query
delay or improving the data availability, but not both. As both metrics are important for mobile nodes, we propose schemes to
balance the tradeoffs between data availability and query delay under different system settings and requirements. Extensive
simulation results show that the proposed schemes can achieve a balance between these two metrics and provide satisfying
system performance.
INTRODUCTION
In mobile ad hoc networks (MANETs), since mobile
nodes move freely, network partition may occur,
where nodes in one partition cannot access data held
by nodes in other partitions. Thus, data availability
(i.e., the number of successful data accesses over
the total number of data accesses) in MANETs is
lower than that in conventional wired networks. Data
replication has been widely used to improve data
availability in distributed systems, and we will apply
this technique to MANETs [1]. By replicating data at
mobile nodes which are not the owners of the original
data, data availability can be improved because
there are multiple replicas in the network and the
probability of finding one copy of the data is higher.
Also, data replication can reduce the query delay since
mobile nodes can obtain the data from some nearby
replicas. However, most mobile nodes only have limited
storage space, bandwidth and power, and hence
it is impossible for one node to collect and hold all
the data considering these constraints. By taking these
issues into consideration, we expect that mobile nodes
should not be able (or willing) to replicate all data
items in the network (more discussions in Appendix
A.)
DATA REPLICATION
Data replication has been extensively studied in the
Web environment and distributed database systems
(See Appendix B in the supplemental material for
detailed literature review). However, most of them
either do not consider the storage constraint or ignore
the link failure issue. Before addressing these issues
by proposing new data replication schemes, we first
introduce our system model.
In a MANET, mobile nodes collaboratively share
data. Multiple nodes exist in the network and they
send query requests to other nodes for some specified
data items. Each node creates replicas of the data
items and maintains the replicas in its memory (or
disk) space. During data replication, there is no central
server that determines the allocation of replicas,
and mobile nodes determine the data allocation in a
distributed manner.
Reliable Grouping (RG) Scheme
OTOO only considers one neighboring node when
making data replication decisions. RN further considers
all one-hop neighbors. However, the cooperations
in both OTOO and RN are not fully exploited. To
further increase the degree of cooperation, we propose
the reliable grouping (RG) scheme which shares
replicas in large and reliable groups of nodes, whereas
OTOO and RN only share replicas among neighboring
nodes. The basic idea of the RG scheme is that it
always picks the most suitable data items to replicate
on the most suitable nodes in the group to maximize
the data availability and minimize the data access
delay within the group.
Simulation Results
Experiments were run using different workloads and
system settings. The performance analysis presented
here is designed to compare the effects of different
workload parameters such as Zipf parameter, network
size, radio range, memory size and node mobility (due
to the space limitation, the effects of different mobility
models are provided in Appendix G). For each workload
parameter (e.g., the mean update arrival time or
the mean query generate time), the mean value of
the measured data is obtained by collecting a large
number of samples such that the confidence interval
is reasonably small. In most cases, the 95% confidence
interval for the measured data is less than 10% of the
sample mean.
CONCLUSIONS
In MANETs, due to link failure, network partitions
are common. As a result, data saved at other nodes
may not be accessible. One way to improve data availability
is through data replication. In this paper, we
proposed several data replication schemes to improve
the data availability and reduce the query delay. The
basic idea is to replicate the most frequently accessed
data locally and only rely on neighbor’s memory
when the communication link to them is reliable.